mlsanityData to 7 Oct 2026

FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network

arXiv 2410.09118 ↗First posted 10 Oct 2024cs.LG cs.AIcited by 8

Not on the map. Why?

Abstract (arXiv)

Famously, the ability of Message Passing Neural Networks (MPNN) to distinguish between graphs is limited to graphs separable by the Weisfeiler-Lemann (WL) graph isomorphism test, and the strongest MPNNs, in terms of separation power, are WL-equivalent. However, it was demonstrated that the quality of separation provided by standard WL-equivalent MPNN can be very low, resulting in WL-separable graphs being mapped to very similar, hardly distinguishable outputs. This phenomenon can be explained by the recent observation that standard MPNNs are not lower-Lipschitz. This paper addresses this issue by introducing FSW-GNN, the first MPNN that is fully bi-Lipschitz with respect to standard WL-equivalent graph metrics. Empirically, we show that our MPNN is competitive with standard MPNNs for several graph learning tasks and is far more accurate in long-range tasks, due to its ability to avoid oversmoothing and oversquashing. Our code is available at https://github.com/yonatansverdlov/Over-squashing.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 45 of its 64 references that are in the map. First posted on arXiv 10 Oct 2024.

Builds on

45 of 64 references.

References · 45

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2019Strategies for Pre-training Graph Neural Networkscited by 964
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  11. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  12. 2017Residual Gated Graph ConvNetscited by 341
33 more
  1. 2022Long Range Graph Benchmarkcited by 258
  2. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  3. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  4. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  5. 2021Equivariant Subgraph Aggregation Networkscited by 154
  6. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  7. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 88
  8. 2021The Logic of Graph Neural Networkscited by 84
  9. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  10. 2022Ordered Subgraph Aggregation Networkscited by 57
  11. 2020Wasserstein Embedding for Graph Learningcited by 56
  12. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
  13. 2020word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Datacited by 38
  14. 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
  15. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 33
  16. 2023A graphon-signal analysis of graph neural networkscited by 29
  17. 2014Graph Matching: Relax at Your Own Riskcited by 27
  18. 2020Optimization of Graph Neural Networks with Natural Gradient Descentcited by 26
  19. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  20. 2017DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problemscited by 20
  21. 2022Permutation Invariant Representations with Applications to Graph Deep Learningcited by 20
  22. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  23. 2023HoloNets: Spectral Convolutions do extend to Directed Graphscited by 20
  24. 2024Spatio-Spectral Graph Neural Networkscited by 17
  25. 20221-WL Expressiveness Is (Almost) All You Needcited by 15
  26. 2023Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexescited by 15
  27. 2022Weisfeiler-Lehman meets Gromov-Wassersteincited by 14
  28. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
  29. 2024On dimensionality of feature vectors in MPNNscited by 6
  30. 2024Graph Neural Reaction Diffusion Modelscited by 6
  31. 2024Next Level Message-Passing with Hierarchical Support Graphscited by 5
  32. 2017Exact Recovery with Symmetries for the Doubly-Stochastic Relaxationcited by 3
  33. 2024Stability of sorting based embeddingscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 2.

8 papers.

  1. 2025Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 8
  2. 2025Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddingscited by 2
  3. 2025On the (Non) Injectivity of Piecewise Linear Janossy Poolingcited by 1
  4. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 1
  5. 2025Toward bilipshiz geometric modelscited by 1
  6. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1
  7. 2025Monotone and Separable Set Functions: Characterizations and Neural Modelscited by 0
  8. 2026Towards Metric-Faithful Neural Graph Matchingcited by 0