Homomorphism distortion: A metric to distinguish them all and in the latent space bind them
This work addresses the limitation of combinatorial-based expressivity measures in graph neural networks, providing a new metric for graph similarity that could impact graph theory and machine learning applications, though it appears incremental as it builds on homomorphism concepts.
The authors tackled the problem of measuring similarity between vertex-attributed graphs by introducing graph homomorphism distortion, which they show can completely characterize graphs and serve as a complete graph embedding. They validated this empirically by fully distinguishing the BREC dataset with up to 4-WL non-distinguishable graphs and outperforming previous homomorphism-based methods on the ZINC-12k dataset.
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.