Source-linked AI summary
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe
TL;DR
The paper addresses the limited theoretical understanding of GNNs and their relationship to the 1-WL heuristic. It shows that standard GNNs match 1-WL expressiveness and introduces higher-order k-GNNs, whose hierarchical variants improve performance across graph tasks.
Problem
Theoretical understanding of how GNNs encode graph structure and whether they offer advantages over 1-WL-based kernels remained limited.
Method
The paper theoretically relates GNNs to 1-WL and develops k-GNNs based on higher-dimensional WL, including hierarchical variants.
Results
Hierarchical k-GNNs consistently outperform traditional GNNs across graph classification and regression tasks, reducing QM9 mean absolute error by 54.45% on average across twelve tasks.
Takeaways & Limitations
Higher-order message passing captures structural information unavailable at the node level and supports stronger graph representations.
Takeaways & Limitations
Standard GNNs share 1-WL’s inability to distinguish all non-isomorphic graphs and to capture properties such as triangle counts.
Abstract
from arXiv · showhide
In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically -- showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the $1$-dimensional Weisfeiler-Leman graph isomorphism heuristic ($1$-WL). We show that GNNs have the same expressiveness as the $1$-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so-called $k$-dimensional GNNs ($k$-GNNs), which can take higher-order graph structures at multiple scales into account. These higher-order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher-order information is useful in the task of graph classification and regression.
Introduction
The paper examines GNNs theoretically through their relationship with the 1-WL heuristic, showing equivalent expressive power while identifying shared limitations. It then introduces higher-order k-GNNs and hierarchical variants to capture structural information at multiple granularities.
- GNNs provide trainable, end-to-end neighborhood aggregation using continuous feature vectors and neural networks.This makes their feature construction adaptable to data distributions and continuous node or edge information.
- The paper shows that GNNs cannot exceed 1-WL in distinguishing non-isomorphic graphs and can match its expressiveness with suitable initialization.This establishes a theoretical relationship between standard GNNs and the classical 1-WL heuristic.
- Because GNNs and 1-WL share expressive power, they also share the shortcomings characterized for 1-WL.The result transfers known limitations of the graph-isomorphism heuristic to GNNs.
- k-GNNs generalize GNNs by passing messages between subgraph structures, capturing information invisible to node-level message passing.The proposed higher-order architectures are based on the k-dimensional WL algorithm and are strictly more powerful than standard GNNs.
- Hierarchical k-GNNs combine representations learned at different granularities and consistently outperform traditional GNNs across graph classification and regression tasks.Across twelve QM9 graph regression tasks, the hierarchical model reduces mean absolute error by 54.45% on average.
Related Work
Prior graph-learning research was dominated by kernel methods and later expanded through graph neural networks. Despite strong empirical progress, theoretical analysis of GNNs remained limited before this work.
- Kernel methods historically dominated supervised learning on graphs by mapping graphs into a Hilbert space.
- Graph-kernel research developed random-walk, shortest-path, graphlet, assignment-based, spectral, and decomposition approaches.These approaches also emphasized scalability through explicit feature maps that avoid expensive Gram matrix computations.
- GNNs achieved state-of-the-art performance on graph-classification benchmarks and applications including protein interactions, recommender systems, and quantum molecular analysis.
- Before this paper, theoretical work on GNNs was sparse, including studies of Laplacian smoothing, shared Hilbert spaces with graph kernels, and approximation capabilities.
Preliminaries
The preliminaries define graphs, node colorings, and Weisfeiler-Leman procedures before introducing GNNs as differentiable neighborhood-aggregation architectures. Higher-dimensional WL operates on tuples and progressively increases graph-distinguishing power.
- Notation and Background: A graph is defined as a finite node set with an edge set, while node colorings assign labels or colors and induce refinement and equivalence relations.
- Weisfeiler-Leman Algorithm: The 1-WL algorithm iteratively computes node colorings from previous colorings and can terminate when the number of colors stops changing.It can test non-isomorphism when corresponding color counts differ, with termination guaranteed after at most max{|V(G)|, |V(H)|} iterations.
- Weisfeiler-Leman Algorithm: 1-WL is incomplete because it cannot distinguish all non-isomorphic graphs.The paper notes that it remains a powerful heuristic for a broad class of graphs.
- Weisfeiler-Leman Algorithm: The k-WL generalization colors k-tuples rather than individual nodes and defines tuple neighborhoods by replacing one component with every graph node.
- Weisfeiler-Leman Algorithm: Increasing k makes WL more powerful: for every k ≥ 2, some graphs are distinguishable by (k + 1)-WL but not by k-WL.The paper also notes that its variant differs slightly from the folklore k-WL while matching the folklore (k−1)-WL in power.
- Graph Neural Networks: A GNN begins with node features consistent with labels or arbitrary real-valued vectors, then repeatedly aggregates local neighborhood features through differentiable functions.The aggregation and merge functions may be arbitrary differentiable, permutation-invariant functions; the resulting architecture is called a 1-GNN.
- Graph Neural Networks: Whole-graph representations can be formed by summing node representations, while model parameters are optimized end-to-end with classification or regression objectives.
Relationship Between 1-WL and 1-GNNs
The paper establishes that 1-GNNs and 1-WL have equivalent graph-distinguishing power, while 1-GNNs remain adaptable to learning tasks and continuous node features. Consequently, 1-GNNs inherit the shortcomings of 1-WL.
- 1-GNNs are no more powerful than 1-WL for distinguishing non-isomorphic graphs or subgraphs.
- There are parameter choices under which 1-GNNs match 1-WL exactly, including the simple architecture with linearly independent label encodings.
- 1-GNNs extend 1-WL with trainable representations that can adapt to learning tasks and handle continuous node features.
- Both approaches can assign identical colors to all nodes in a triangle and a 4-cycle and cannot capture properties such as triangle counts.
k-dimensional Graph Neural Networks
k-GNNs generalize GNN message passing from nodes to k-node subgraphs, enabling higher-order structural processing. Hierarchical variants recursively combine representations across dimensions while preserving the theoretical capacity of standard k-GNNs.
- k-dimensional Graph Neural Networks: k-GNNs operate on k-element vertex subsets and use neighborhoods of subsets differing by one element, following a set-based k-WL construction.
- k-dimensional Graph Neural Networks: Each k-set receives an initial one-hot feature encoding its labeled induced subgraph’s isomorphism type before subsequent layers update its representation.
- k-dimensional Graph Neural Networks: Local k-GNNs omit global subset neighborhoods to improve scalability and reduce overfitting, while their evaluation cost depends on graph size, k, and sparsity.
- k-dimensional Graph Neural Networks: k-GNNs have the same graph-distinguishing power as set-based k-WL under suitable parameter initialization.
- Hierarchical Variant: Hierarchical k-GNNs initialize k-level messages with features learned by lower-dimensional GNNs, recursively combining representations from dimensions 1 through k.
- Hierarchical Variant: The hierarchical formulation is theoretically equivalent in representational capacity to standard k-GNNs while providing a natural inductive bias for graphs with hierarchical structure.
Experimental Study
The experiments compare hierarchical k-GNNs with graph kernels and 1-GNNs on graph classification and Q M9 regression. Hierarchical models match kernels on benchmark classification datasets and generally outperform 1-GNNs, although gains vary by target and parameter optimization contributes little.
- Kernel comparisons: Hierarchical k-GNNs are on par with graph kernels on graph classification benchmark datasets.The comparison uses established graph-kernel benchmark datasets with discrete node labels or no labels.
- GNN comparisons: The 1-2-3-GNN significantly outperforms the 1-GNN on all seven classification datasets.The 1-GNN is reported as the overall weakest method across all tasks.
- Aggregation optimization: Optimizing the aggregation function yields only slight gains on two of three datasets, while no optimization performs better on PROTEINS.The authors attribute this pattern to one-hot node labels supplying sufficient neighborhood information without learned aggregation.
- Q M9 regression: On eleven of twelve Q M9 targets, all hierarchical variants beat the 1-GNN baseline.Q M9 contains 133 385 small molecules and evaluates twelve energetic, electronic, geometric, and thermodynamic targets using mean absolute error.
- Q M9 regression: Additional structural information from k-GNN layers produces highly unequal gains across Q M9 targets.The results indicate that higher-order information does not benefit every regression task equally.
- Experimental caveat: k-GNN models use more parameters than 1-GNN models, but adding layers to match k-GNN parameter counts does not improve results.The models stack two additional GNN layers for each k; the parameter-matched extension did not perform better in any experiment.
Conclusion
The paper establishes theoretical limits for a wide class of GNNs and introduces k-GNNs as a stronger, hierarchical generalization. Experiments show that k-GNNs consistently outperform 1-GNNs, while future work targets task-specific layers.
- Theoretical findings: A wide class of GNN architectures cannot be stronger than the 1-WL in distinguishing non-isomorphic graphs.The paper also notes that GNNs retain the 1-WL’s distinguishing power while adapting to the data distribution.
- Model extension: k-GNNs generalize GNNs through the k-WL and are strictly stronger for distinguishing non-isomorphic graphs.The paper states that k-GNNs can distinguish more graph properties than ordinary GNNs.
- Model extension: Hierarchical k-GNNs exploit the hierarchical organization of most real-world graphs.The conclusion identifies task-specific k-GNN layers using expert knowledge in bioinformatics and cheminformatics as future work.
- Empirical findings: The experimental study shows that k-GNNs consistently outperform 1-GNNs.
Appendix
This appendix section announces proofs for four formal results without presenting their statements or arguments.
- Appendix: The appendix provides proofs for Theorem 1, Theorem 2, Proposition 3, and Proposition 4.
Proof of Theorem 1
The proof shows that matching 1-WL colors imply matching GNN feature representations at each iteration. It uses induction, with identical node colors and neighbor-color multisets producing identical aggregation inputs.
- Proof setup: Theorem 1 is proved for an arbitrary iteration and pair of nodes in a single graph.
- Base case: The base case follows because the initial node coloring is chosen consistently with the graph labels.
- Induction step: The induction hypothesis gives equal current node features and equal multisets of neighboring features for the two nodes.
- Induction step: Identical inputs to the merge and aggregation functions force equal next-step GNN features, completing the theorem.
Proof of Theorem 2
The proof establishes the theorem by induction, beginning with uniformly colored graphs and then extending the argument to colored graphs. The colored-graph extension is largely technical because the central idea appears in the uniform-color case.
- Theorem 6 asserts that, for every iteration t ≥ 0, suitable weights and a 1-GNN architecture exist for a labeled graph.
- The proof proceeds from graphs with a uniform initial color to graphs with arbitrary node colors.
- The colored-graph extension uses a slightly adapted but equivalent version of 1-WL.
Uncolored Graphs
For uncolored graphs, the construction makes GNN updates reproduce 1-WL refinement while preserving distinct row representations. This yields an end-to-end sequence of 1-GNN weights matching the modified 1-WL coloring at every iteration.
- 1-WL and GNN refinement: The refinement operator ΓG maps the previous coloring to the updated coloring in the 1-WL process.
- Iterated simulation: Once two vertices receive different colors, the modified refinement preserves their distinction in every later iteration.This follows because each refined color class partitions, or refines, the preceding color classes.
- 1-WL and GNN refinement: A suitable weight matrix transforms row-independent features into row-independent outputs equivalent to the 1-WL refinement.The construction encodes neighborhood counts by color class and uses a sign-based transformation.
- Iterated simulation: The resulting weights can be chosen as a sequence so that repeated GNN updates correspond to repeated applications of the modified refinement operator.The feature width can be padded to n columns when necessary.
Colored Graphs
For colored graphs, the paper extends the equivalence between GNN updates and 1-WL while preserving initial labels and linearly independent representations. It also shows that ReLU can implement the construction and establishes the higher-order k-GNN relationships to k-WL.
- Colored 1-WL equivalence: The colored-graph update retains initial labels so distinctions made at one iteration remain distinct at later iterations.The modified refinement operator incorporates previous colors into the update.
- Colored 1-WL equivalence: With linearly independent encodings of initial labels, the simple 1-GNN architecture is equivalent to 1-WL on colored graphs.The proof uses induction and shows that the GNN and refinement updates produce identical color classes.
- ReLU implementation: A two-fold ReLU construction simulates the sign activation, causing only a constant two-fold increase in the number of GNN layers.The construction uses successive ReLU transformations and adjustment layers.
- Higher-order GNNs: For k ≥ 2, every k-GNN update is bounded by the corresponding k-WL refinement for all iterations.
- Higher-order GNNs: A k-GNN can simulate set-based k-WL by applying 1-WL to an auxiliary graph with O(n^k) vertices representing k-element subsets.Auxiliary-graph vertices are connected when their subsets overlap in k−1 elements and are initially labeled by isomorphism type.