aiqbench analysis
This paper proposes a (pseudo-)metric for attributed graphs, built on graph homomorphisms, that accounts for both structure and node features. Existing graph neural network expressivity analyses mostly ignore features, so this gives researchers a way to judge when graphs with similar features should count as similar. The authors claim the metric can be approximated efficiently, supports fine-grained graph distinction, and improves GNN predictions when used as a structural encoding. For ML readers, the practical question is whether those gains hold on standard benchmarks at reasonable computational cost.
Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs
arXiv:2511.03068v5 Announce Type: replace Abstract: 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 (pseudo-)metric by showing that i.) it can be efficiently approximated while retaining distinction capabilities, ii.) it provides a granular approach to graph distinction, and, iii.) it serves as a structural encoding, extending the concept of homomorphism-based descriptors to attributed graphs, thus improving the predictive capabilities of graph neural networks.
Abstract: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 (pseudo-)metric by showing that i.) it can be efficiently approximated while retaining distinction capabilities, ii.) it provides a granular approach to graph distinction, and, iii.) it serves as a structural encoding, extending the concept of homomorphism-based descriptors to attributed graphs, thus improving the predictive capabilities of graph neural networks.
Machine Learning (cs.LG)
arXiv:2511.03068 [cs.LG]
(or arXiv:2511.03068v5 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2511.03068 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 239 words
Related coverage
ERAlign: Energy-based Representation Alignment of GNNs and LLMs on Text-attributed Graphs
arXiv · Jun 10, 2026
Otap:Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories
arXiv · Jul 21, 2026
Bridging Academia and Industry: A Comprehensive Benchmark for Attributed Graph Clustering
arXiv · Oct 15, 2026
Formalizing and Mitigating Structural Distortion in LLM Attention for Zero-Shot Graph Reasoning
arXiv · Jun 16, 2026