Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs

A large driver of the complexity of graph learning is the interplay between structure and features.When analyzing the expressivity of graph neural networks, however, existing approaches ignore features in favor of structure, making it nigh-impossible to assess to what extent two graphs with close features should be considered similar.We address this by developing a new (pseudo-)metric based on graph homomorphisms.Inspired by concepts from metric geometry, our graph homomorphism distortion measures the minimal worst-case distortion that node features of one graph are subjected to when mapping one graph to another. We demonstrate the utility of our novel measure by showing that: 1) it can be efficiently approximated under some additional assumptions, 2) it provides a granular approach to graph distinction and 3) it serves as a structural encodings, extending the concept of homomorphism counts to atrributed graphs, which improve the predictive capabilities of graph neural networks.