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

Yonatan Sverdlov, Yair Davidson, Nadav Dym, Tal Amir

TL;DR

This paper introduces FSW-GNN (Fourier Sliced-Wasserstein Graph Neural Network), the first architecture that is fully bi-Lipschitz with respect to standard Weisfeiler-Lehman (WL) equivalent graph metrics. By guaranteeing that graph distances are proportionally preserved in the embedding space, FSW-GNN fundamentally mitigates the notorious issues of oversmoothing and oversquashing, leading to dramatic performance gains in long-range graph learning tasks.

What Problem Does This Paper Address?

Message Passing Neural Networks (MPNNs) are the workhorses of graph machine learning, but they suffer from a fundamental theoretical and practical limitation. Theoretically, their ability to distinguish between different graph structures is capped by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. Even when architectures are designed to be "WL-equivalent" (meaning they can theoretically separate any graphs the WL test can), they often fail in practice.

The culprit? A lack of stable distance preservation. Standard MPNNs are not lower-Lipschitz, meaning they can map completely distinct, WL-separable graphs to nearly identical, numerically indistinguishable feature vectors. As networks grow deeper to pass information across large graphs, this geometric collapse manifests as two well-known phenomena:

  • Oversmoothing: Node features become highly similar and lose their distinctiveness.
  • Oversquashing: Information from distant nodes gets compressed and lost during aggregation.

This paper tackles this gap by developing a GNN that guarantees a stable, two-sided geometric mapping (bi-Lipschitzness), ensuring that distances in the output space faithfully reflect structural distances in the input space.

Methods

The core innovation of FSW-GNN lies in its message aggregation mechanism, which replaces simple sum or max pooling with a Fourier Sliced-Wasserstein (FSW) Embedding.

The FSW aggregation process operates in three main steps:

  1. Projection & Sorting: The multiset of neighboring node features is projected onto a set of direction vectors and sorted.
  2. Quantile Function Representation: The sorted scalars are transformed into a step-like quantile function. This step makes the representation size-agnostic, treating the neighborhood effectively as a probability distribution.
  3. Fourier Cosine Transform: A variant of the Fourier transform (cosine transform) is applied to the quantile function and sampled at specific frequencies to produce the final, fixed-length embedding vector. Finally, the cardinality (size) of the neighborhood is appended to ensure that graphs with identical feature proportions but different sizes remain distinguishable.
Figure 2: The quantile func- tion for three different multi- sets

By leveraging this mathematically rigorous embedding, the authors prove that FSW-GNN is bi-Lipschitz with respect to both the Doubly Stochastic (DS) metric and the Tree Mover’s Distance (TMD). Unlike its predecessor SortMPNN, FSW-GNN does not require a priori knowledge of the maximum neighborhood size and naturally supports non-integer edge weights.

Datasets

The authors evaluated FSW-GNN across three distinct categories of benchmarks:

  • Synthetic Long-Range Tasks: NeighborsMatch and Graph Transfer tasks (comprising CliquePath, Ring, and CrossRing topologies) designed specifically to test a model's resistance to oversquashing over controlled problem radii.
  • Transductive Node Classification: Standard benchmarks including Cora, Citeseer, PubMed, Chameleon, Squirrel, Actor, Cornell, Texas, and Wisconsin.
  • Graph Classification/Regression: The Long Range Graph Benchmark (LRGB) datasets (peptides-func and peptides-struct), alongside MUTAG and Protein datasets.

Key Insights and Ideas

  • Injectivity is Not Enough: Simply ensuring a GNN function is injective (like GIN) doesn't prevent numerical collapse. We need quantitative stability guarantees (bi-Lipschitz bounds) to ensure graphs remain distinct under finite-precision floating-point arithmetic.
  • Neighborhoods as Distributions: By treating a node's neighborhood as a continuous distribution via quantile functions rather than a discrete multiset, FSW-GNN elegantly bypasses the need for zero-padding, making it truly scalable and flexible.
  • Fixing the Architecture, Not the Graph: Traditional methods combat oversquashing by altering the graph topology (e.g., virtual nodes or graph rewiring). FSW-GNN proves that long-range information bottlenecks can be solved purely through better mathematical design of the aggregation layers, preserving the original graph structure.

Key Results

FSW-GNN shines brightest in long-range scenarios where standard GNNs completely break down.

Long-Range Performance

On the NeighborsMatch problem, FSW-GNN maintains a perfect 100% accuracy up to the maximum tested radius of 8, whereas standard models like GCN, GIN, and GAT collapse to near 0% accuracy as the radius exceeds 4 or 5.

Figure 1: FSW-GNN handles tasks with large radius better than standard MPNNs, which are more prone to oversmoothing and oversquashing. Task taken from [3]

Similarly, in Graph Transfer tasks across various topologies (CliquePath, Ring, CrossRing), FSW-GNN is the only model that achieves 100% accuracy across all tested layer depths (up to 15 layers).

Figure 3: Performance comparison of MPNN models across the CliquePath, Ring, and CrossRing graph transfer tasks as presented in [27].

Standard Benchmarks

While optimized for long-range stability, FSW-GNN remains highly competitive on standard transductive learning tasks, outperforming GCN, GAT, and Sort-MPNN in 6 out of 9 standard datasets.

Table 1: Learning accuracy comparison across different benchmarks and models.

Limitations and Future Work

Despite its strong theoretical and empirical showing, FSW-GNN has a few limitations:

  • Computational Overhead: The sorting and Fourier transform steps introduce a slightly higher runtime complexity compared to simple sum or mean pooling.
  • Extreme Ranges: While it dramatically extends the effective depth of MPNNs, the authors note that performance still begins to deteriorate when the problem radius exceeds 20.
  • Theoretical Constants: The paper proves the existence of bi-Lipschitz constants, but explicitly calculating or optimizing these constants for specific architectures remains an open direction for future work.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sverdlov2025fsw,
  author = {Yonatan Sverdlov and Yair Davidson and Nadav Dym and Tal Amir},
  title = {{FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network}},
  booktitle = {LOG},
  year = {2025},
  url = {https://openreview.net/forum?id=zVXZK5JRHB},
}
Figure