Graph Representational Learning: When Does More Expressivity Hurt Generalization?
A family of premetrics that capture different degrees of structural similarity between graphs are introduced and relate these similarities to generalization, and consequently, the performance of expressive GNNs are related.