Source-linked AI summary
Breaking the Limits of Message Passing Graph Neural Networks
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, Paul Honeine
TL;DR
MPNNs are efficient on sparse graphs but limited by 1-WL expressive power and unable to capture some graph distinctions and substructures. The paper designs spectrally parameterized, receptive-field-masked convolution supports, yielding greater-than-1-WL theoretical power and experimental performance comparable to 3-WL models while retaining locality and linear sparse computation.
Problem
MPNNs retain linear sparse-graph complexity but cannot distinguish some 1-WL-equivalent graphs or count certain substructures.
Method
The paper designs convolution supports as nonlinear functions of graph eigenvalues and applies receptive-field masks to obtain localized spectral MPNNs.
Results
The proposed models are theoretically more powerful than 1-WL and experimentally as powerful as 3-WL models for graph distinction and substructure counting.
Takeaways & Limitations
The approach combines spatial locality, sparse linear complexity, and richer spectral output profiles without feature engineering or node permutations during training.
Takeaways & Limitations
The method has a 3-WL-like limit and fails to distinguish strongly regular graphs that are 3-WL equivalent.
Abstract
from arXiv · showhide
Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$, consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks.
1. Introduction
MPNNs are computationally efficient on sparse graphs but are theoretically limited to 1-WL, motivating methods that increase expressive power while preserving locality and efficiency.
- Motivation: MPNNs have linear memory and computational complexity on sparse graphs, enabling applications to large sparse graphs.Their convolution supports and neighborhood propagation remain sparse.
- Motivation: Maximum-power MPNNs embed 1-WL-equivalent non-isomorphic graphs identically and cannot solve some graph combinatorial problems.This establishes a theoretical expressive-power ceiling at the first-order Weisfeiler-Lehman test.
- Prior approaches: Higher-order models reach 3-WL expressive power, but they use higher-order relations and non-local updates that weaken locality.The cited approaches include PPGN and hierarchical message passing over node tuples.
- Prior approaches: Randomized or uniquely labeled features preserve linear complexity but require many training samples and slow convergence.Handcrafted preprocessing features instead require domain expertise and feature selection.
- Contribution: The proposed spectral convolution uses nonlinear eigenvalue functions and receptive-field masks to provide locality, linear complexity, greater-than-1-WL power, and spectral flexibility.The paper reports experimental parity with PPGN and the ability to distinguish some 1-WL-equivalent graphs and count previously inaccessible substructures.
2. Generalization of Spectral and Spatial MPNN
Spectral and spatial GNN layers can be expressed within a common MPNN framework, differing primarily in how they construct convolution supports.
- Common framework: A graph is represented by an adjacency matrix A, node features X, and a Laplacian L derived from adjacency and degree matrices.The Laplacian may be combinatorial or normalized.
- Spectral layers: Spectral GNNs filter graph signals through the Laplacian eigendecomposition using a learnable eigenvalue-based function.The filtering operation is xflt = Udiag(Ω(λ))U^T x.
- Common framework: Both spectral and spatial GNNs fit the MPNN form, with convolution supports determining how node features propagate.Trainable layer weights are applied to representations propagated through the supports.
- Spectral layers: Spectral supports can be written as C(s) = Udiag(Φs(λ))U^T when designed through eigenvalue functions.This places spectral filtering inside the generalized support formulation.
- Efficiency: Sparse convolution supports give MPNNs linear memory and computational complexity in the number of nodes for sparse graphs.Sparse matrix multiplication takes time linear in the number of edges, and therefore in nodes under sparsity.
3. Characterization of Weisfeiler-Lehman
The paper uses MATLANG operation sets to characterize graph expressive power and connect matrix-language equivalence with different Weisfeiler-Lehman tests.
- WL characterization: Graph universality concerns distinguishing every pair of non-isomorphic graphs, while WL tests provide a practical expressive-power characterization.WL equivalence supplies sufficient but not complete evidence of graph isomorphism.
- WL characterization: For k ≥ 2, higher-order WL tests generally become more discriminative, although 2-WL is not more powerful than 1-WL.The Folklore WL convention relates higher-order WL and FWL orders differently.
- WL characterization: The paper distinguishes WL and FWL terminology because prior studies use different order conventions.This clarification prevents conflating equivalent tests with different naming schemes.
- MATLANG: MATLANG links operation dictionaries to WL tests, with expressive power varying according to the included operations.The paper introduces matrix operations and sentences as the formal language for this comparison.
- MATLANG: L1 characterizes 1-WL equivalence, L2 is strictly stronger than L1 but weaker than 3-WL, and L3 characterizes 3-WL equivalence.Adding +, ×, and elementwise custom functions does not further increase the expressive power of the corresponding language.
4. How Powerful are MPNNs?
Theoretical analysis shows that standard MPNNs are limited to 1-WL, while Chebnet can exceed that limit under an eigenvalue condition and higher-order operations enable broader graphlet counting.
- MPNN expressive power: Standard MPNNs including GCN, GAT, GraphSage, and GIN are not more powerful than the 1-WL test.GIN is identified as exactly 1-WL-powerful, while the others are known to be weaker or no stronger.
- Chebnet: Chebnet is more powerful than 1-WL for non-regular graph pairs with unequal maximum Laplacian eigenvalues, but not otherwise.Its distinguishing ability therefore depends on the spectral condition.
- Chebnet: Chebnet distinguishes the Decalin and Bicyclopentyl graphs despite their 1-WL equivalence because their normalized Laplacian maximum eigenvalues differ.The figure provides a concrete example of the theorem’s condition.
- Graphlet counting: The analyzed graphlets comprise 3-star, triangle, tailed triangle, and 4-cycle patterns.These structures are used to evaluate substructure-counting capability.
1 . Theorem 4.
The paper characterizes which graphlet patterns MPNNs can count at different Weisfeiler–Lehman expressive-power levels. 1-WL-equivalent models are limited to 3-stars, whereas 3-WL-equivalent models can count all illustrated graphlets.
- Triangle and 4-cycle graphlets can be counted using sentences in L+.
- Tailed triangle graphlets can be counted using sentences in L+.
- Node degrees are included as node features because an MPNN may fail to learn them without an appropriate convolution support.The number of 3-stars centered on a node can then be derived directly from its degree.
5. MPNN Beyond 1-WL
This section develops GNNML models that extend MPNN expressiveness beyond 1-WL while retaining sparse, localized computation. GNNML3 uses spectral convolution supports to learn power-series combinations and experimentally approaches 3-WL capability, with limits similar to 3-WL.
- Model definitions: GNNML1 is exactly as powerful as the 1-WL test, while GNNML3 is designed to reach 3-WL equivalence experimentally.
- Beyond 1-WL: Trace and element-wise multiplication are required to move beyond 1-WL, because they enable operations on powers of graph supports.
- Beyond 1-WL: MPNNs preserve linear time and memory complexity by multiplying representations with sparse supports, but they do not retain explicit powers needed for trace or element-wise multiplication.
- Limitations of the construction: The power-based support construction requires preprocessing, tuning the necessary adjacency power, and normalization because powered supports become densely filled with high values.
- Spectral supports: GNNML3 designs convolution supports as nonlinear spectral functions of normalized-Laplacian or adjacency eigenvalues, expressible as power series.
- Spectral supports: Different spectral design parameters produce different power-series combinations, whose element-wise products are learned before receptive-field masking sparsifies the supports.
- Spectral supports: Spectral filter functions can target different frequency bands, allowing the model to learn graph-signal properties dependent on the spectrum.
- Limitations: The proposed method has a limit similar to 3-WL: it fails to distinguish strongly regular graphs characterized by degree and common-neighbor counts.
6. Experimental Results
The experiments evaluate expressive power, substructure counting, spectral filtering, and downstream performance. GNNML3 matches 3-WL behavior on several tasks, while Chebnet and GNNML3 show strong spectral performance.
- Evaluation scope: Experiments test graph distinguishability, substructure counting, spectral filtering, and downstream graph tasks across multiple datasets.The study compares GCN, GAT, GIN, Chebnet, GNNML1, GNNML3, and PPGN using 1-WL and 3-WL baselines.
- Expressive power: 312 of more than 61M graph8c pairs are 1-WL equivalent, while none are 3-WL equivalent; sr25 contains strongly regular graphs with 3-WL-equivalent pairs.The graph8c, sr25, and EXP datasets probe whether models distinguish graph pairs that WL tests cannot separate.
- Expressive power: GNNML1 and GIN approach the 1-WL limit on graph8c, whereas Chebnet exceeds that limit by detecting pairs with different maximum eigenvalues.On EXP, Chebnet distinguishes pairs with different maximum eigenvalues, while fixing λmax = 2 reduces its performance to that of MPNNs.
- Substructure counting: 3-WL models count the tested graphlets and approximate the custom function with result < 10^-3, while 1-WL-equivalent models generally cannot.The findings are consistent with the theoretical results; GNNML1 and Chebnet provide better custom-function approximation than other MPNNs.
- Spectral expressive power: Chebnet and GNNML3 give the best results across spectral tests, covering low-pass, high-pass, and band-pass behavior.GNNML1 learns high-pass effects relatively well, while Chebnet and GNNML3 generalize band-pass effects through spectral-domain convolutions.
- Downstream tasks: PPGN and GNNML3 perform better on Zinc12K, while Chebnet and GNNML3 perform significantly better on the image-based MNIST-75 task.GNNML3 achieves comparable results on MUTAG, ENZYMES, PROTEINS, and PTC in the reported TU-dataset evaluation.
7. Conclusion
The paper concludes that its proposed MPNN surpasses the 1-WL expressive limit while retaining efficient computation and broad spectral ability. Its main boundary is that it remains unable to distinguish graph pairs that are equivalent under 3-WL.
- Conclusion: The proposed MPNN is theoretically more powerful than 1-WL and experimentally as powerful as 3-WL models for graph distinction and substructure counting.It achieves these results without feature engineering or node permutations during training.
- Conclusion: The method extends spectral expressive ability beyond low-pass filtering, supporting broader frequency-dependent graph-signal relationships.The conclusion identifies spectral expressiveness as a separate advantage beyond graph-isomorphism and substructure-counting performance.
- Efficiency: GNNML3 uses linear memory and time complexity in the number of nodes, whereas PPGN requires quadratic memory and cubic time complexity.The comparison is presented as the principal complexity advantage over the 3-WL-equivalent PPGN baseline.
B.2. Theorem.2
The theorem shows that ChebNet convolution supports can exceed 1-WL expressive power when graph Laplacian eigenvalue information prevents their reduction to operations captured by 1-WL. The construction also represents broad spectral filters as Laplacian power series.
- ChebNet is no more powerful than 1-WL when tested graph Laplacians have the same maximum eigenvalue.
- Different maximum eigenvalues make ChebNet’s second support graph-dependent, preventing its expression with one constant coefficient.
- A contradiction proves that one-layer ChebNet can distinguish 1-WL-equivalent, non-regular graphs with different maximum eigenvalues.
- Adding 0.01I reduced graph8c’s undistinguished 1-WL-equivalent pairs from 44 to 19.The remaining 19 pairs had identical maximum eigenvalues; the original 25 additional failures were regular graphs.
- Operations express graph patterns including 3-stars, triangles, 4-cycles, and tailed triangles, with MLPs implementing required elementwise functions.
- The proposed convolution support is a Laplacian power series when every derivative of the frequency response is nonzero, as for exp(.).
C. L1 Equivalent Graphs
Examples show ChebNet distinguishing L1-equivalent graphs through differing Laplacian spectra, while trace-based comparisons fail on cospectral L2-equivalent graphs. An L3 operation separates the latter pair.
- Decalin and Bicyclopentyl are L1-equivalent and therefore indistinguishable by 1-WL.
- Their maximum Laplacian eigenvalues are 2.0 and 1.8418, producing different second ChebNet supports.
- The resulting outputs are −9.9327 and −9.9269, so ChebNet projects the graphs to different points.
- The graphs have matching traces through the fourth adjacency power but differ at the fifth, showing they are not L2 equivalent.
- The Figure 5 pair is non-isomorphic, L2 equivalent, cospectral, and 4-regular.
- An L3 sentence yields 6032 versus 5872, distinguishing the Figure 5 graphs and showing they are not L3 equivalent.
E. L3 Equivalent Graphs
The strongly regular graphs in Figure 6 are cospectral and 3-WL equivalent, so L3 sentences cannot distinguish them. Distinguishing them requires a 3-order relationship that mimics 3-FWL or 4-WL.
- The Figure 6 strongly regular graph pair has equal normalized-Laplacian eigenvalues and is cospectral.
- Because the graphs are 3-WL equivalent, no sentence in L3 distinguishes them.
- Distinguishing the pair requires mimicking 3-FWL or 4-WL through a 3-order relationship between nodes.
- The 3-order representation uses 8 connectivity states for three-node pairs plus one diagonal state, totaling 9 states.
- Summing selected elements of the three-dimensional squared adjacency provides a distinguishing operation for the pair.
F. Result of TU Datasets
Table 5 evaluates the models with 10-fold cross-validation on four molecular graph datasets and an additional ENZYMES setting with continuous atom features.
- Table 5 reports 10-fold cross-validation on MUTAG, ENZYMES, PROTEINS, and PTC molecular datasets.Nodes represent atoms, edges represent atomic bonds, and the base datasets use one-hot atom features without edge features.
- Adding 18-length continuous atom features raised graph-agnostic MLP performance on ENZYMES from 30.8% to 70.6%.
- The continuous ENZYMES features contain at least part of the structural information according to the reported MLP comparison.
G. Datasets and Application Details
The evaluation covers multiple graph datasets and task types, using controlled training settings and implementations of standard MPNN and higher-order baselines. Experimental models use node features, spectral initialization for GNNML3, and a tensor-based PPGN representation.
- Evaluation scope: Four task types are evaluated: graph isomorphism, graph regression, node regression, and n-class graph classification.The experiments use node features only, including one-hot discrete labels and continuous features; available edge features are not used.
- Datasets: The study uses datasets including Graph8c, Sr25, EXP, random graphs, 2D-Grid, Band-Pass, Zinc12K, Mnist-75, and TU benchmarks.The TU benchmarks include PROTEINS, ENZYMES, MUTAG, and PTC.
- Training setup: All models use roughly 30K trainable parameters, with 2–5 layers and tuned convolution-kernel counts, learning rates, weight decay, and dropout.Adam optimization and ReLU activations are used unless otherwise specified.
- Spectral models: GNNML3 initializes edge features through eigendecomposition of the normalized Laplacian, except for Zinc12K and substructure-counting tasks, which use the adjacency matrix.Its initial convolution supports use Gaussian frequency profiles with bandwidth b = 5, uniformly sampled spectral bands, and an identity all-pass support.
- Baselines: The comparison includes Chebnet, GCN, GIN, GAT, PPGN, GNNML1, and GNNML3 implementations, with standard MPNN layers tested through PyTorch Geometric.Baseline MPNNs begin with node features, update node representations, and apply graph readout followed by fully connected layers.
- Higher-order baseline: PPGN represents adjacency, edge features, and diagonalized node features in a 3-dimensional tensor before higher-order updates.The implementation pads graphs to the maximum size, masks valid diagonal and off-diagonal entries, and therefore retains O(n^2) intermediate memory usage.