arXiv:2511.03068v1 Announce Type: new
Abstract: For far too long, expressivity of graph neural networks has been measured emph{only} in terms of combinatorial properties. In this work we stray away from this tradition and provide a principled way to measure similarity between vertex attributed graphs. We denote this measure as the emph{graph homomorphism distortion}. We show it can emph{completely characterize} graphs and thus is also a emph{complete graph embedding}. However, somewhere along the road, we run into the graph canonization problem. To circumvent this obstacle, we devise to efficiently compute this measure via sampling, which in expectation ensures emph{completeness}. Additionally, we also discovered that we can obtain a metric from this measure. We validate our claims empirically and find that the emph{graph homomorphism distortion}: (1.) fully distinguishes the texttt{BREC} dataset with up to $4$-WL non-distinguishable graphs, and (2.) emph{outperforms} previous methods inspired in homomorphisms under the texttt{ZINC-12k} dataset.
These theoretical results, (and their empirical validation), pave the way for future characterization of graphs, extending the graph theoretic tradition to new frontiers.