mlsanityData to 14 Oct 2026

Homomorphism Counts as Structural Encodings for Graph Learning

arXiv 2410.18676 ↗First posted 24 Oct 2024cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary textitgraph inductive biases to condition the model on graph structure. In this work, we propose textitmotif structural encoding (MoSE) as a flexible and powerful structural encoding framework based on counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE to random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-art performance on a widely studied molecular property prediction dataset.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 47 of its 70 references that are in the map. First posted on arXiv 24 Oct 2024.

Builds on

47 of 70 references.

References · 47

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  5. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  8. 2020Benchmarking Graph Neural Networkscited by 680
  9. 2020A Generalization of Transformer Networks to Graphscited by 661
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  11. 2019Graph Transformer Networkscited by 523
  12. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
35 more
  1. 2019Provably Powerful Graph Networkscited by 389
  2. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  3. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 329
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  5. 2022Long Range Graph Benchmarkcited by 263
  6. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  7. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  8. 2020Random Features Strengthen Graph Neural Networkscited by 186
  9. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  10. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  11. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  12. 2023Exphormer: Sparse Transformers for Graphscited by 170
  13. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  14. 2019On the Universality of Invariant Networkscited by 152
  15. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  16. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  17. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 85
  18. 2019GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulationcited by 75
  19. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  20. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  21. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  22. 2022Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logical Queriescited by 39
  23. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  24. 2024Graph Transformers: A Surveycited by 32
  25. 2020Graph Homomorphism Convolutioncited by 27
  26. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  27. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 20
  28. 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
  29. 2023Expressive Sign Equivariant Networks for Spectral Geometric Learningcited by 15
  30. 2017Homomorphisms Are a Good Basis for Counting Small Subgraphscited by 14
  31. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  32. 2023PlanE: Representation Learning over Planar Graphscited by 11
  33. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  34. 2023On the Power of the Weisfeiler-Leman Test for Graph Motif Parameterscited by 6
  35. 2019Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithmcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 3.

7 papers.

  1. 2025Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphscited by 1
  2. 2025Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networkscited by 1
  3. 2026Measuring Structure in Graph Benchmark Datasets Using Graph Invariantscited by 1
  4. 2026Incorporating Deep Learning Design in Database Queriescited by 1
  5. 2025On The Expressive Power of GNN Derivativescited by 0
  6. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  7. 2026DISSOLVR: An Interpretable and Fast Framework for Aqueous and Organic Solubility Predictioncited by 0