Provably Powerful Graph Networks
Provably Powerful Graph Networks achieves guaranteed 3-WL power with matrix multiplication and reaches 90.55% on MUTAG.
Key Findings
Methodology
The paper first proves that k-order permutation-invariant/equivariant networks are at least as discriminative as k-WL. Its technical device is Power-sum Multi-symmetric Polynomials (PMPs), which uniquely encode vector multisets through finite-degree power sums. It then proposes a practical second-order architecture: feature-wise MLPs transform pairwise tensors, and matching channels are combined by matrix multiplication before invariant graph-level readout.
Key Results
- Theoretically, k-order networks distinguish every graph pair separated by k-WL. The reduced model implements 2-FWL, which is equivalent to 3-WL, and is therefore strictly stronger than 1-WL message passing. It separates the paper’s illustrative 1-WL-hard graphs, whose triangle counts are 0 and 12.
- On MUTAG, PTC, PROTEINS, NCI1, NCI109, COLLAB, IMDB-B, and IMDB-M, Ours 1 obtains 90.55%, 66.17%, 77.20%, 83.19%, 81.84%, 80.16%, 72.60%, and 50.00%, respectively. Ours 3 reaches 82.23% on NCI109, broadly competing with GIN and other strong baselines.
- A block uses O(n²) space and O(n³) time, versus approximately O(n³) space and O(n⁴) time for the full third-order model of Morris et al. The implementation uses three blocks, MLPs, skip connections, and an additional post-block MLP.
Significance
The work addresses a central tension in graph learning: message-passing networks scale well but are bounded by 1-WL, whereas higher-order architectures are more expressive but computationally expensive. It provides an explicit route to practical, invariant/equivariant graph learning with a formal 3-WL guarantee. For molecular, chemical, and social graphs, the model can exploit triangles, short cycles, and shared-intermediate-node patterns without explicitly enumerating all triples.
Technical Contribution
The first contribution establishes a formal correspondence between k-order networks and k-WL. The second introduces PMP multiset encoding: applying monomials x^α and summing over neighborhood elements yields a unique representation. The third rewrites 2-FWL aggregation as matrix multiplication after two feature transforms, W_{i1,i2,l}=Σ_j B_{j,i2}^β B_{i1,j}^γ. This reproduces the required tuple multiset while retaining only second-order tensors.
Novelty
Unlike GIN and standard message passing, the method does not merely strengthen a permutation-invariant aggregator. It composes two relations through a shared intermediate index using matrix multiplication. Compared with Morris et al.’s 1-2-3 GNN, it achieves provable 3-WL expressiveness with second-order storage and a simpler implementation. The authors present it as the first practical invariant/equivariant model with this guarantee.
Limitations
- Second-order storage still scales as n², and dense matrix multiplication becomes expensive for large graphs. The paper focuses on dense edge data and does not fully validate performance on industrial-scale sparse graphs.
- A formal 3-WL guarantee does not imply that finite-width networks trained by gradient descent will learn the corresponding refinement procedure. MLP capacity, optimization, initialization, and feature distributions remain important.
Future Work
The authors suggest generalized matrix multiplication for higher-order tensors, potentially matching k-FWL and therefore (k+1)-WL. Important next steps include sparse implementations, low-rank or approximate PMP encoding, scalable batching, and systematic studies of optimization and generalization. Evaluation should also expand to node-level prediction, dynamic graphs, and molecular tasks with continuous geometric attributes.
AI Executive Summary
Graph neural networks have largely been built around message passing: each node repeatedly aggregates information from its neighbors. Yet Morris et al. and Xu et al. showed that this family is no more discriminative than 1-WL color refinement. Consequently, structurally different graphs can receive identical representations. Higher-order networks offer more power, but explicit third-order tensors quickly become impractical.
Maron and colleagues first prove that k-order invariant/equivariant networks are at least as powerful as k-WL. They then introduce a compact second-order architecture that applies feature-wise MLPs and multiplies matching channels as matrices. This operation combines two relations through a shared intermediate node, implementing 2-FWL; because 2-FWL is equivalent to 3-WL, the model has a strict theoretical advantage over message passing. Power-sum Multi-symmetric Polynomials provide a principled, order-insensitive encoding of neighborhood multisets.
The model is tested on MUTAG, PTC, PROTEINS, NCI1, NCI109, COLLAB, IMDB-B, and IMDB-M. Ours 1 reaches 90.55%, 66.17%, 77.20%, 83.19%, 81.84%, 80.16%, 72.60%, and 50.00%, respectively; Ours 3 reaches 82.23% on NCI109. A block requires O(n²) space and O(n³) time, substantially lighter than a full third-order design. The broader contribution is therefore not simply another benchmark model, but a constructive compromise between provable structural sensitivity and implementable computation.
Deep Analysis
Background
Message-passing models include GCN, GraphSAGE, GAT, and GIN, and update nodes by neighborhood aggregation. Xu et al.’s GIN reaches the expressive ceiling of 1-WL, but 1-WL fails on many regular or symmetric graphs. Earlier work by Maron et al. characterized permutation-equivariant tensor layers and established universality only at very high order. This paper seeks stronger discrimination without that computational burden.
Core Problem
The task is to exceed 1-WL while preserving permutation invariance and practical complexity. WL refinement requires an exact representation of unordered neighborhood multisets. Summation loses multiplicity patterns, while sorting is difficult to implement robustly with equivariant layers. Full 3-WL-style models also require O(n³) storage and can incur O(n⁴) computation.
Innovation
The paper contributes three linked ideas. First, it proves that k-order networks can match k-WL discrimination. Second, it uses PMPs, p_α(X)=Σ_i x_i^α, to uniquely encode vector multisets. Third, it proposes a second-order matrix-multiplication network. By computing W=m1(B)·m2(B), it realizes the 2-FWL neighborhood pairing and therefore 3-WL power without explicit third-order tensors.
Methodology
- ��Graph encoding: B∈R^{n²×(e+1)} stores node colors on diagonal channels and adjacency in the final channel.
- ��Multiset encoding: an MLP approximates τ(x)=(x^α:|α|≤n), followed by coordinate-wise summation to form PMP features.
- ��General theorem: permutation-equivariant linear layers, pointwise nonlinearities, and invariant readout simulate k-WL updates.
- ��Practical block: MLPs m1 and m2 independently transform each pairwise feature; matching channels are multiplied as matrices; m3 supplies a skip connection; a final invariant layer and MLP produce the graph output.
- ��2-FWL simulation: each matrix entry sums products involving a shared index j, exactly encoding the paired multiset required by 2-FWL.
Experiments
The TensorFlow implementation uses three identical blocks. m1 and m2 are d-layer MLPs with b-dimensional hidden layers; m3 is the identity, and a post-block MLP m4 reduces parameters. Baselines include WL, FGSD, GIN, Invariant Graph Networks, CCN, DiffPool, and Morris et al.’s 1-2-3 GNN. The benchmarks cover molecular, chemical, and social graphs; evaluation reports graph-classification accuracy with standard deviations.
Results
Ours 1 obtains 90.55±8.70% on MUTAG, 66.17±6.54% on PTC, 77.20±4.73% on PROTEINS, 83.19±1.11% on NCI1, 81.84±1.85% on NCI109, and 80.16±1.11% on COLLAB. Ours 2 reaches 81.38±1.42% on COLLAB, above GIN’s 80.2±1.9%. The proof’s illustrative construction computes A³ and takes tr(A³), separating graphs with 0 versus 12 triangles.
Applications
The architecture is relevant to molecular property prediction, drug discovery, compound classification, chemical reaction analysis, and social-network graph classification. It is especially suitable when triangles, short cycles, common neighbors, or relational composition matter. Deployment requires pairwise tensors, so node count, memory, sparsity, and batching must be managed carefully.
Limitations & Outlook
O(n²) memory still limits very large graphs, while O(n³) multiplication can dominate runtime. The theorem assumes sufficiently expressive MLPs and concerns distinguishability, not guaranteed optimization success. Experiments emphasize graph-level tasks and provide limited evidence for massive sparse graphs or continuous geometric data. Sparse algebra, low-rank approximations, better scaling, and broader task evaluations are natural extensions.
Plain Language Accessible to non-experts
Imagine two cities represented only by their road maps. A basic investigator visits each intersection and asks, “How many nearby intersections are there, and what are they like?” If two cities give the same answers at every intersection, the investigator may declare them identical—even when their roads are arranged differently.
This paper gives the investigator a second tool. It checks whether two locations connect through the same middle intersection, much like discovering that two people share a friend. Matrix multiplication performs this check efficiently: one matrix records the first leg of a route, another records the second, and multiplying them counts compatible two-step combinations.
The system also has a careful way to record an unordered list of neighbors. Rewriting the same list in a different order does not change its meaning, just as rearranging ingredients on a shopping list does not change what you must buy. Finally, the model summarizes the whole city without caring how intersections were numbered.
This extra structural vision lets it detect triangles and related patterns that ordinary message passing misses. On MUTAG it reaches 90.55% accuracy. The trade-off is that it keeps information about every pair of intersections, so very large cities still require compression or sparse computation.
ELI14 Explained like you're 14
Think of a graph as a game map or a social-media network. A normal graph neural network asks every player, “Who are your friends, and what do they look like?” Then everyone updates their description. This works surprisingly well, but sometimes two totally different maps give exactly the same answers. The computer gets fooled!
This paper adds a clever detective move: check whether two places are connected through the same middle place. In social-media language, it asks whether two users share friends. Matrix multiplication is the fast calculator for this job. After several rounds, the model can notice triangles, short loops, and patterns made from several connected relationships.
There is another neat trick called PMP. Imagine writing down your classmates’ names and hobbies, but allowing the list to be shuffled. PMP makes a summary that stays the same after shuffling, while still keeping enough information to tell different groups apart. If the map’s location numbers are changed, the final answer also stays unchanged.
The results are strong: the model scores 90.55% on the MUTAG molecule dataset and 83.19% on NCI1. But there is a catch: it remembers information for every pair of places, so giant networks can become expensive. It is like a smarter detective with a very large notebook—powerful, but worth making lighter!
Glossary
Weisfeiler–Lehman test (WL graph isomorphism test)
A hierarchy of algorithms that repeatedly refines colors assigned to vertices or tuples. Two graphs are separated when their final color histograms differ.
The paper uses 1-WL, k-WL, and 2-FWL as expressive-power benchmarks.
Message-passing GNN
A graph model in which each node aggregates representations from neighboring nodes and updates its state. Its distinguishing power is bounded by 1-WL.
It is the principal baseline and theoretical limitation addressed by the paper.
Permutation equivariance
If node labels are permuted, an intermediate tensor is permuted in the corresponding way. This respects the fact that graph node names are arbitrary.
The proposed tensor layers and matrix multiplication satisfy this property.
Power-sum Multi-symmetric Polynomial (PMP)
A family of permutation-invariant polynomial features p_α(X)=Σ_i x_i^α. All terms with degree at most n uniquely encode a multiset of vectors.
PMPs provide the theoretical construction for WL-style neighborhood aggregation.
2-FWL
A refinement algorithm operating on ordered pairs of vertices and aggregating colors through a shared replacement index. It has the same discrimination power as 3-WL.
The practical network is proved expressive by simulating 2-FWL.
Matrix multiplication layer
An operation that sums products over a shared index between two pairwise feature matrices. It captures compositions of relations and two-step structural patterns.
It is the central quadratic operation, with O(n³) time complexity.
Open Questions Unanswered questions from this research
- 1 How to scale the second-order representation to million-node sparse graphs remains unresolved. Sparse multiplication, sampling, or low-rank methods are needed without destroying the 3-WL guarantee.
- 2 The theorem concerns representational distinguishability, not whether finite networks trained with gradient descent learn the refinement procedure. The roles of width, optimization, noise, and continuous features require analysis.
- 3 Evidence is limited for node-level prediction, dynamic graphs, and geometric molecular data; broader experiments and controlled ablations are still needed.
Applications
Immediate Applications
Molecular property prediction
Drug-discovery teams can encode atoms and bonds as a second-order tensor and use three matrix-multiplication blocks to predict activity, toxicity, or solubility. The architecture can exploit rings and shared atoms, but memory requirements should be checked before deployment.
Social-network classification
Platforms can classify communities or network types using user relations and node attributes. The model captures common friends and local cycles, while practical use requires sparse storage, privacy safeguards, and strategies for changing graphs.
Long-term Vision
Provably expressive graph-learning infrastructure
Combined with generalized matrix multiplication and sparse hardware, this approach could support theoretically controlled reasoning over knowledge graphs, chemical reactions, and complex relational systems. The main obstacles are scale, robustness, and training efficiency.
Abstract
Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressive power of graph neural networks (GNN). It was shown that the popular message passing GNN cannot distinguish between graphs that are indistinguishable by the 1-WL test (Morris et al. 2018; Xu et al. 2019). Unfortunately, many simple instances of graphs are indistinguishable by the 1-WL test. In search for more expressive graph learning models we build upon the recent k-order invariant and equivariant graph neural networks (Maron et al. 2019a,b) and present two results: First, we show that such k-order networks can distinguish between non-isomorphic graphs as good as the k-WL tests, which are provably stronger than the 1-WL test for k>2. This makes these models strictly stronger than message passing models. Unfortunately, the higher expressiveness of these models comes with a computational cost of processing high order tensors. Second, setting our goal at building a provably stronger, simple and scalable model we show that a reduced 2-order network containing just scaled identity operator, augmented with a single quadratic operation (matrix multiplication) has a provable 3-WL expressive power. Differently put, we suggest a simple model that interleaves applications of standard Multilayer-Perceptron (MLP) applied to the feature dimension and matrix multiplication. We validate this model by presenting state of the art results on popular graph classification and regression tasks. To the best of our knowledge, this is the first practical invariant/equivariant model with guaranteed 3-WL expressiveness, strictly stronger than message passing models.