Homomorphism distortion: A metric to distinguish them all and in the latent space bind them

• URL: http://arxiv.org/abs/2511.03068v1
• Date: Tue, 04 Nov 2025 23:29:59 GMT
• Title: Homomorphism distortion: A metric to distinguish them all and in the latent space bind them
• Authors: Martin Carrasco, Olga Zaghen, Erik Bekkers, Bastian Rieck,
• Abstract summary: We denote this measure as the emphgraph homomorphism distortion.<n>We show it can emphcompletely characterize graphs and thus is also a emphcomplete graph embedding.<n>We validate our claims empirically and find that the emphgraph homomorphism distortion: (1.) fully distinguishes the textttBREC dataset with up to $4$-WL non-distinguishable graphs, and (2.) emphoutperforms previous methods inspired in homomorphisms under the textttZINC-12
• Score: 14.333119698384523
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning [50.99881402425112]
  Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph-structured data.<n>Existing GNNs often struggle with heterophilic graphs, where connected nodes tend to have dissimilar features or labels.<n>We present a new and unexplored paradigm: directly increasing the graph homophily via a carefully designed graph transformation.
  arXiv  Detail & Related papers  (2026-02-06T23:14:10Z)
• Categorical Belief Propagation: Sheaf-Theoretic Inference via Descent and Holonomy [1.001355398440049]
  We develop a categorical foundation for belief propagation on factor graphs.<n>Message-passing is formulated using a Grothendieck fibration (int to catFG_) over polarized factor graphs.<n>We introduce HATCC, an algorithm that detects descent obstructions via holonomy on the factor nerve.
  arXiv  Detail & Related papers  (2026-01-08T00:03:11Z)
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs [50.99881402425112]
  Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph-structured data.<n>Existing GNNs often struggle with heterophilic graphs, where connected nodes tend to have dissimilar features or labels.<n>We present a new and unexplored paradigm: directly increasing the graph homophily via a carefully designed graph transformation.
  arXiv  Detail & Related papers  (2025-09-16T00:10:20Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  We present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.<n>An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  We propose fine-grained graph rationalization (FIG) for graph machine learning.<n>Our idea is driven by the self-attention mechanism, which provides rich interactions between input nodes.<n>Our experiments involve 7 real-world datasets, and the proposed FIG shows significant performance advantages compared to 13 baseline methods.
  arXiv  Detail & Related papers  (2023-12-13T02:56:26Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories.<n>We propose a novel GNN architecture whereby the emphforward pass explicitly depends on emphboth positive (as is typical) and negative (unique to our approach) edges.<n>This is achieved by recasting the embeddings themselves as minimizers of a forward-pass-specific energy function that favors separation of positive and negative samples.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• On the Equivalence of Graph Convolution and Mixup [70.0121263465133]
  This paper investigates the relationship between graph convolution and Mixup techniques. Under two mild conditions, graph convolution can be viewed as a specialized form of Mixup. We establish this equivalence mathematically by demonstrating that graph convolution networks (GCN) and simplified graph convolution (SGC) can be expressed as a form of Mixup.
  arXiv  Detail & Related papers  (2023-09-29T23:09:54Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond [36.5554915218563]
  Homophily is a graph property describing the tendency of edges to connect similar nodes; the opposite is called heterophily. There is no universally agreed-upon measure of homophily in the literature. We show that commonly used homophily measures have critical drawbacks preventing the comparison of homophily levels across different datasets.
  arXiv  Detail & Related papers  (2022-09-13T17:28:25Z)
• Node Copying: A Random Graph Model for Effective Graph Sampling [35.957719744856696]
  We introduce the node copying model for constructing a distribution over graphs. We show the usefulness of the copying model in three tasks. We employ our proposed model to mitigate the effect of adversarial attacks on the graph topology.
  arXiv  Detail & Related papers  (2022-08-04T04:04:49Z)
• Matching recovery threshold for correlated random graphs [9.12788494573002]
  For two correlated graphs which are independently sub-sampled from a common ErdHos-R'enyi graph $mathbfG(n, p)$, we wish to recover their emphlatent matching from the observation of these two graphs emphwithout labels. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.
  arXiv  Detail & Related papers  (2022-05-29T13:04:20Z)
• Not too little, not too much: a theoretical analysis of graph (over)smoothing [8.7314407902481]
  We analyze graph smoothing with emphmean aggregation, where each node successively receives the average of the features of its neighbors. We show that graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together.
  arXiv  Detail & Related papers  (2022-05-24T15:39:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.