Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

• 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.Source: Introduction · p. 1
• 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.Source: Introduction · pp. 1–2
• 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.Source: Introduction · p. 2
• 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.Source: Introduction · p. 2
• 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.Source: Introduction · p. 2

• Kernel methods historically dominated supervised learning on graphs by mapping graphs into a Hilbert space.Source: Related Work · p. 2
• 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.Source: Related Work · p. 2
• GNNs achieved state-of-the-art performance on graph-classification benchmarks and applications including protein interactions, recommender systems, and quantum molecular analysis.Source: Related Work · p. 2
• Before this paper, theoretical work on GNNs was sparse, including studies of Laplacian smoothing, shared Hilbert spaces with graph kernels, and approximation capabilities.Source: Related Work · p. 2

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.Source: Notation and Background · p. 3

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.Source: Weisfeiler-Leman Algorithm · p. 3
• 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.Source: Weisfeiler-Leman Algorithm · p. 3
• The k-WL generalization colors k-tuples rather than individual nodes and defines tuple neighborhoods by replacing one component with every graph node.Source: Weisfeiler-Leman Algorithm · p. 3
• 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.Source: Weisfeiler-Leman Algorithm · p. 3

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.Source: Graph Neural Networks · pp. 3–4
• Whole-graph representations can be formed by summing node representations, while model parameters are optimized end-to-end with classification or regression objectives.Source: Graph Neural Networks · p. 4

• 1-GNNs are no more powerful than 1-WL for distinguishing non-isomorphic graphs or subgraphs.Source: Relationship Between 1-WL and 1-GNNs · p. 4
• There are parameter choices under which 1-GNNs match 1-WL exactly, including the simple architecture with linearly independent label encodings.Source: Relationship Between 1-WL and 1-GNNs · p. 4
• 1-GNNs extend 1-WL with trainable representations that can adapt to learning tasks and handle continuous node features.Source: Relationship Between 1-WL and 1-GNNs · p. 4
• Both approaches can assign identical colors to all nodes in a triangle and a 4-cycle and cannot capture properties such as triangle counts.Source: Shortcomings of Both Approaches · p. 4

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.Source: k-dimensional Graph Neural Networks · p. 4
• Each k-set receives an initial one-hot feature encoding its labeled induced subgraph’s isomorphism type before subsequent layers update its representation.Source: k-dimensional Graph Neural Networks · pp. 4–5
• Local k-GNNs omit global subset neighborhoods to improve scalability and reduce overfitting, while their evaluation cost depends on graph size, k, and sparsity.Source: k-dimensional Graph Neural Networks · p. 5
• k-GNNs have the same graph-distinguishing power as set-based k-WL under suitable parameter initialization.Source: k-dimensional Graph Neural Networks · p. 5

Hierarchical Variant

• Hierarchical k-GNNs initialize k-level messages with features learned by lower-dimensional GNNs, recursively combining representations from dimensions 1 through k.Source: Hierarchical Variant · p. 5, Figure 1 · p. 5, k-dimensional Graph Neural Networks · p. 5
• The hierarchical formulation is theoretically equivalent in representational capacity to standard k-GNNs while providing a natural inductive bias for graphs with hierarchical structure.Source: Hierarchical Variant · p. 5

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.Source: Datasets · p. 5, Table 1 · p. 6, Results and Discussion · p. 7

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.Source: Results and Discussion · p. 7

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.Source: Results and Discussion · p. 7

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.Source: Datasets · p. 6, Table 2 · p. 6, Results and Discussion · p. 7
• 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.Source: Results and Discussion · p. 7

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.Source: Results and Discussion · p. 7

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.Source: Conclusion · p. 7

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.Source: Conclusion · p. 7
• 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.Source: Conclusion · p. 7

Empirical findings

• The experimental study shows that k-GNNs consistently outperform 1-GNNs.Source: Conclusion · p. 7

Appendix

• The appendix provides proofs for Theorem 1, Theorem 2, Proposition 3, and Proposition 4.Source: Appendix · p. 10

Proof setup

• Theorem 1 is proved for an arbitrary iteration and pair of nodes in a single graph.Source: Proof of Theorem 1 · p. 10

Base case

• The base case follows because the initial node coloring is chosen consistently with the graph labels.Source: Proof of Theorem 1 · p. 10

Induction step

• The induction hypothesis gives equal current node features and equal multisets of neighboring features for the two nodes.Source: Proof of Theorem 1 · p. 10
• Identical inputs to the merge and aggregation functions force equal next-step GNN features, completing the theorem.Source: Proof of Theorem 1 · p. 10

• Theorem 6 asserts that, for every iteration t ≥ 0, suitable weights and a 1-GNN architecture exist for a labeled graph.Source: Proof of Theorem 2 · p. 10
• The proof proceeds from graphs with a uniform initial color to graphs with arbitrary node colors.Source: Proof of Theorem 2 · p. 10
• The colored-graph extension uses a slightly adapted but equivalent version of 1-WL.Source: Proof of Theorem 2 · p. 10

1-WL and GNN refinement

• The refinement operator ΓG maps the previous coloring to the updated coloring in the 1-WL process.Source: Uncolored Graphs · p. 10

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.Source: Uncolored Graphs · pp. 10–11

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.Source: Uncolored Graphs · pp. 12–13

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.Source: Uncolored Graphs · p. 13

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.Source: Colored Graphs · p. 13
• 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.Source: Colored Graphs · p. 14

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.Source: Adaptation to the ReLu activation… · pp. 14–15

Higher-order GNNs

• For k ≥ 2, every k-GNN update is bounded by the corresponding k-WL refinement for all iterations.Source: Proofs of Proposition 3 and… · p. 15
• 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.Source: Proofs of Proposition 3 and… · p. 15