PaperlayerView exact revision on arXiv

Source-linked AI summary

Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing

Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe

arXiv:2102.08786v3cs.LGcs.SI

TL;DR

Standard GNNs have limitations in detecting small subgraphs, while random-walk methods have also performed well in some applications. CRaWl uses random-walk subgraph features and 1D convolutions, and is reported to match state-of-the-art GNNs across benchmarks while having expressiveness incomparable with the Weisfeiler–Leman hierarchy.

  • Problem

    Standard GNNs are not good at detecting some small subgraphs, such as cycles of length 6, despite such subgraph distributions carrying relevant structural information.

    Source: §1 · p. 2

  • Method

    CRaWl extracts subgraph features from sliding windows along random walks, processes them with 1D convolutions, and pools the results into node embeddings.

    Source: §1 · p. 1

  • Results

    CRaWl matches or outperforms state-of-the-art GNNs on graph-level tasks, excels on long-range interactions, and has expressiveness incomparable with the Weisfeiler–Leman hierarchy.

    Source: §1 · p. 2, §6 · p. 18

  • Takeaways & Limitations

    By construction, CRaWl detects arbitrary substructures up to its local window size and extracts useful features from highly symmetrical graphs such as CSL graphs.

    Source: §6 · p. 18

    The expressiveness analysis defines indistinguishability through random-walk feature distributions, without considering how the 1D CNN processes those features.

    Source: §3 · p. 10

Abstract

from arXiv · show

We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRaWl operates fundamentally different from message passing graph neural networks. CRaWl layers extract and aggregate information on subgraphs appearing along random walks through a graph using 1D Convolutions. Thereby it detects long range interactions and computes non-local features. As the theoretical basis for our approach, we prove a theorem stating that the expressiveness of CRaWl is incomparable with that of the Weisfeiler Leman algorithm and hence with graph neural networks. That is, there are functions expressible by CRaWl, but not by GNNs and vice versa. This result extends to higher levels of the Weisfeiler Leman hierarchy and thus to higher-order GNNs. Empirically, we show that CRaWl matches state-of-the-art GNN architectures across a multitude of benchmark datasets for classification and regression on graphs.

1 Introduction

CRaWl combines random-walk subgraph features with 1D convolutions to update node embeddings, offering an approach distinct from message passing. The paper argues its expressiveness is incomparable with the Weisfeiler–Leman hierarchy and reports benchmark performance on par with advanced GNNs and graph transformers.

1 Introduction

  • CRaWl samples random walks, encodes subgraphs visible within sliding windows, processes them with 1D convolutions, and pools the results to update node embeddings.Its iterative node-feature updates make it compatible with GNN layers.Source: §1 · p. 1
  • CRaWl and GNNs are incomparable in expressiveness: each can distinguish graphs the other cannot, and CRaWl can distinguish graphs not distinguished by any k-dimensional Weisfeiler–Leman algorithm.The paper connects standard GNN expressiveness to the Weisfeiler–Leman characterization and extends its result to higher-order GNNs.Source: §1 · p. 2
  • CRaWl matches advanced message-passing GNNs and graph transformers across major graph-learning benchmarks and excels on long-range interactions.The introduction describes a comprehensive experimental analysis.Source: §1 · p. 2

1.1 Related Work

  • CRaWl targets settings where local structural features matter, encoding all edges among walk nodes rather than only cycle closures or backtracking.The introduction also notes that sliding-window subgraph sampling can yield meaningful patterns in sparse graphs.Source: §1 · p. 2, §1.1 · p. 3
  • Unlike Subgraph GNNs and Structure-Aware Transformers, CRaWl encodes local subgraph structure directly rather than processing subgraphs with a standard message-passing GNN.Its encoding is order-dependent and the sampled subgraph is random, while still providing complete structural information.Source: §1.1 · p. 3

2 Method

CRaWl processes random walks with convolutional neural networks to capture local and global graph structure. Its layers encode walklet subgraphs, transform their features with 1D convolutions, and pool walklet embeddings into node states; the paper also analyzes the resulting runtime trade-offs.

2 Method

  • CRaWl samples relatively long random walks and applies 1D CNNs to their features, allowing graph information to flow along walks.The resulting walklet embeddings update latent node states across layers.Source: §2 · pp. 3–4

2.1 Random Walk Features

  • The walk feature representation records node and edge features plus local identity and adjacency relations, so a window-sized CNN can access the full induced subgraph.The main experiments use non-backtracking uniform walks; window size must be at least 6 for molecular rings, with defaults of 8 or 16 for longer-range dependencies.Source: §2.1 · pp. 4–5

2.2 Architecture

  • Each layer applies a 1D CNN to walk features, averages embeddings of centered walklets into node states, then uses an MLP to produce updated embeddings.Stacked layers support graph-level prediction through global sum- or mean-pooling; CRaWl layers are compatible with message-passing layers, though combining them is left for future work.Source: §2.2 · pp. 5–6, Figure 2 · p. 6

Asymptotic Runtime

  • With default walk counts and lengths and constant window size, CRaWl scales as O(|E|), but its runtime exceeds a standard MPGNN layer and its quadratic dependence on window size can make it slower in practice.The paper reports that CRaWl is mostly slower than simple message-passing architectures and faster than the SAN graph transformer.Source: Asymptotic Runtime · p. 7

3 Expressiveness

This section examines CRaWl’s expressiveness relative to WL methods and bounded-path k-GNNs, using subgraph detection and constructed graph pairs to show both what CRaWl can distinguish and where its variants have limits.

3 Expressiveness

  • CRaWl’s added expressiveness comes from detecting small subgraphs and long-range interactions, whereas GNNs’ breadth-first aggregation detects features such as node degrees that walks may miss.The theoretical analysis focuses on subgraph detection, making its results independent of the number of GNN layers.Source: §3 · p. 7
  • For every k ≥1, CRaWl distinguishes some maximum-degree-3 graphs that k-WL cannot, while 1-WL distinguishes other maximum-degree-3 graphs that CRaWl with O(n) window size and path length cannot.The first direction uses window size and walk length O(k2); the second holds for graphs with n vertices.Source: §3 · p. 8
  • With window size polynomial in graphlet size, CRaWl is strictly more expressive than graphlet kernels, and the O(k2) window and walk length needed to exceed k-WL are moderate for feasible k ≤ 3.CRaWl’s graph-to-feature computation is isomorphism-invariant, and independently sampling more walks reduces its variance.Source: §3 · p. 8

3.1 Proof of Theorem 1 (1)

  • For every k ≥1, CRaWl distinguishes graphs of order O(k) from k-WL with probability at least 1 −(1/2)^m using window size and walk length O(k2).The proof assumes CNN filters can be arbitrary multilayer perceptrons; it uses k-WL-indistinguishable graph pairs and walks that visit every vertex.Source: §3.1 · pp. 10–12
  • With window size and path length O(k^2), CRaWl detects graph differences inaccessible to k-GNNs on arbitrary-size graphs, typically with k ≤ 3.Unlike the proof’s whole-graph walk, practical use on real-world graphs requires multiple walks to distinguish differences in walk distributions.Source: §3.1 · p. 12

3.2 Proof of Theorem 1 (2)

  • Although 1-WL distinguishes the constructed graph pairs, non-backtracking CRaWl with window o(n) cannot, regardless of walk length or sample count.Source: §3.2 · pp. 12–13
  • For the same pairs, CRaWl with walk length O(n) and n^O(1) samples cannot distinguish them, regardless of window size.A length-O(n) random walk visits both degree-3 endpoints with probability at most exp(−n/d), bounding the total variation distance between the walk-feature distributions by exp(−n/d).Source: §3.2 · p. 13
  • With sufficiently long paths, backtracking CRaWl may distinguish the same pairs even with constant-size windows, but quantitative details remain future work.The proposed intuition uses traversal-time distributions between the two degree-3 nodes.Source: §3.2 · p. 13

4 Experiments

CRaWl is evaluated across standard graph-learning benchmarks and long-range tasks, with comparisons to message-passing GNNs and other graph architectures. It performs strongly across datasets, including state-of-the-art results on the long-range benchmarks and perfect accuracy on pure CSL.

4 Experiments

  • The experiments draw on standard benchmark datasets and include additional TUDataset results and synthetic substructure-counting comparisons in Appendix B.The main benchmark collection includes datasets from Dwivedi et al. (2020), Hu et al. (2020), and Dwivedi et al. (2022).Source: §4 · p. 13

4.1 Datasets

  • The benchmarks span molecular prediction, image-derived graph classification, CSL graph isomorphism classification, and long-range image-segmentation and peptide tasks.They include MOLPCBA, ZINC, CIFAR10, MNIST, CSL, PASCALVOC-SP, PEPTIDES-FUNC, and PEPTIDES-STRUCT.Source: §4.1 · pp. 13–14

4.2 Experimental Setting

  • The reported default uses ℓ=50 training walks and s=8, while long-range tasks use s=16; reducing walks can help overfitting, and molecular tasks require s≥6 to detect aromatic rings.Evaluation uses ℓ=150 walks except MOLPCBA, which uses ℓ=100.Source: §4.2 · pp. 14–15

4.3 Baselines

  • Comparisons use literature and official-leaderboard results, excluding ensemble methods and models pretrained on additional data.The paper reports that baselines include architectures stronger than 1-WL, including Nested GIN.Source: §4.3 · p. 15, §4.4 · p. 15

4.4 Results

  • On ZINC, CRaWl reaches MAE 0.085 (~40% better than PNA), matches CIN and GIN-AK+ within standard deviation, ranks fourth on CIFAR10, and leads MOLPCBA.On MNIST, its performance is on par with PNA within standard deviation.Source: Table 1 · p. 14, §4.4 · p. 15
  • CRaWl achieves state-of-the-art results on all three long-range datasets, improving prior results by 13 percentage points on PASCALVOC-SP and 6 on PEPTIDES-FUNC, and attaining the lowest MAE on PEPTIDES-STRUCT.The reported comparison is against baselines from Dwivedi et al. (2022).Source: Table 2 · p. 15, §4.4 · p. 16
  • On pure CSL, CRaWl reaches 100% accuracy, while MPGNNs achieve at most 10%; 3WLGNN also approaches 100%.With Laplacian features that encode the solution, most approaches perform close to 100%.Source: §4.4 · p. 16, Table 3 · p. 16
  • CRaWl and subgraph GNNs effectively solve subgraph-counting tasks, whereas pure MPGNNs are theoretically and practically unable to count structures more complex than stars.The paper reports these additional counting results in Appendix B.4.Source: §4.4 · p. 16

5 Ablation Study

The ablations compare structural encodings and walk strategies on ZINC, MOLPCBA, and CSL, then examine window size and walk count on ZINC. Full structural encodings and non-backtracking walks perform best overall, while larger windows and more walks generally improve performance.

5 Ablation Study

  • The ablation compares feature-only and structurally encoded walk matrices under both walk strategies on ZINC, MOLPCBA, and CSL.The study uses five models with different seeds and reports their average performance and standard deviation; each walk strategy is evaluated independently.Source: §5 · pp. 16–17
  • Full structural encodings with non-backtracking walks perform best on ZINC and MOLPCBA, and are the only tested CSL variant to reach 100% accuracy.On MOLPCBA, the gain over using no structural encodings is marginal; the unencoded CSL variant can only guess because CSL has no node features.Source: §5 · p. 17, Table 4 · p. 17
  • Structural encodings measurably improve performance across the three datasets, though the improvement varies and MOLPCBA remains highly competitive using node and edge feature sequences alone.Intermediate identity-only and adjacency-only variants were tested on ZINC and CSL, but omitted for MOLPCBA to save computational resources.Source: §5 · pp. 16–17
  • Non-backtracking walks consistently outperform uniform walks, which tend to induce smaller subgraphs on sparse, limited-degree graphs because they often backtrack.The authors attribute significant performance losses across all three ablation datasets to this limitation on evaluating local substructures and long-range dependencies.Source: §5 · p. 17

5.1 Influence of s and m

  • On ZINC, test MAE improves monotonically with window size, with a pronounced gain from s = 4 to s = 6 and saturation around s = 8.The authors relate the sharp gain to benzene rings: windows smaller than 6 are insufficient to detect them.Source: §5.1 · pp. 17–18, Figure 4 · p. 18
  • On ZINC, larger walk counts reduce test MAE, but the gain from m = 0.8|V| to m = |V| is marginal; overall, larger s and m improve performance.The m ablation fixes walk length at ℓ = 150 during inference.Source: §5.1 · p. 18

6 Conclusion

CRaWl uses random walks and 1D CNNs, with expressiveness incomparable to the Weisfeiler-Leman hierarchy; its local window can detect arbitrary substructures.

6 Conclusion

  • CRaWl matches or outperforms state-of-the-art GNNs on graph-level tasks, and its expressiveness is incomparable to the Weisfeiler-Leman hierarchy.By construction, its local window can detect arbitrary substructures, including useful features in highly symmetrical CSL graphs.Source: §6 · p. 18
  • Potential extensions include alternate walk strategies, walk features, pooling functions, sequential models, node-level tasks, motif counting, and scaling to individual large graphs.The paper notes that node-level tasks and motif counting require scaling beyond many medium-sized graphs.Source: §6 · p. 18

A Model Details

  • Appendix A supplies additional CRaWl definitions, sampled-walk details, and the exact CNN architecture used in each layer.Source: A Model Details · p. 24

A.1 Random Walks

  • Non-backtracking walks exclude the previous node except at degree one, avoiding backtracking that slows sparse-graph traversal and interferes with long-range pattern discovery.Walk strategy is a hyperparameter, and non-backtracking usually performs better in the experiments.Source: §A.1 · p. 24

A.2 Convolution Module

  • Depthwise-separable 1D convolutions use pointwise and channelwise stages to simulate a kernel-k convolution with substantially less memory and runtime.An additional pointwise convolution increases expressiveness so the module can distinguish the binary patterns encoding identity and adjacency.Source: §A.2 · p. 24

A.3 Architecture

The experimental architecture stacks residual CRaWl layers, pools the resulting node embeddings, and applies a graph-level output network.

A.3 Architecture

  • The architecture stacks CRaWl layers with residual connections, then batch-normalizes and activates the node embeddings before global sum- or mean-pooling.Source: §A.3 · p. 25
  • A feedforward network with either one hidden layer or a single linear layer maps the pooled representation to a graph-level classification or regression output.Source: §A.3 · p. 25
  • CRaWl layers are compatible with conventional message-passing layers and virtual nodes, but combining CRaWl with message passing was left for future work.Virtual nodes were used in experiments whenever they improved validation performance.Source: §A.3 · p. 25

A.4 Hyperparameters

The appendix specifies experiment-specific walk and model settings, and explains how virtual-node updates are used between CRaWl layers.

A.4 Hyperparameters

  • The number of layers and hidden dimension were tuned to dataset parameter budgets; the default local window is 8 and rises to 16 on long-range datasets.Global pooling is mean or sum, and the output network is either a two-layer MLP or a linear transformation.Source: §A.4 · p. 25
  • Training walks use 50 steps and evaluation walks use 150; walk starts are sampled from each node with probability 1 by default, or 0.2 on MOLPCBA and long-range datasets.Source: §A.4 · p. 25
  • Figure 5 shows two 11-node cyclic skip-link graphs with skip distances 2 and 3.Source: Figure 5 · p. 26

A.5 Virtual Node

  • A virtual node aggregates all node states and sends updated global information back to nodes, but it is an intermediate update rather than a graph node and never appears in CRaWl walks.It is placed between CRaWl layers, except after the final layer.Source: §A.5 · p. 26

A.6 Cross Validation on CSL

The appendix describes the CSL cross-validation protocol and identifies the task as classifying skip-link graphs by isomorphism class.

A.6 Cross Validation on CSL

  • CSL uses five-fold cross-validation: three folds train the model, one supports validation and model selection, and the remaining fold tests it.The split follows the five-fold partition provided by Dwivedi et al. (2020).Source: §A.6 · p. 26
  • The CSL task is to classify example skip-link graphs by their isomorphism class.Source: §A.6 · p. 26
  • Table 7 provides extended CRaWl results across datasets, reporting cross-model deviation and internal-model deviation for each experiment.Source: Table 7 · p. 27

B Extended Results

Table 6 gives dataset statistics for the main paper’s datasets, followed by full-detail experimental results.

B Extended Results

  • Table 6 gives dataset statistics for all datasets used in the main paper.The section then provides experimental results in full detail.Source: B Extended Results · p. 27

B.1 Detailed Results

The detailed results quantify variability across training runs and sampled evaluation walks, and report that CRaWl’s runtime is comparable to advanced graph architectures.

B.1 Detailed Results

  • Table 7 reports performance on training, validation, and test data, and Table 9 presents accuracy on social datasets.The detailed results include both tables.Source: §B.1 · p. 27, Table 9 · p. 28

B.2 Runtime

  • CRaWl’s runtime per epoch does not differ much from common message-passing GNNs and has no disadvantage versus Graph Transformers or subgraph GNNs.Simpler architectures such as GCN can be faster on larger datasets; Table 8 reports average time per epoch.Source: Table 8 · p. 28, §B.2 · p. 28

B.1 Detailed Results

  • Across experiments, cross-model deviation is significantly larger than internal-model deviation, while trained CRaWl models still produce reliable high-quality predictions despite sampled-walk dependence.Internal-model deviation measures variation when one trained model is evaluated repeatedly on the same input; cross-model deviation measures variation in average performance across training runs.Source: §B.1 · pp. 27–28

B.3 Additional Experiments

On structure-only social graph benchmarks, CRaWl performs similarly to standard MPGNNs on COLLAB, trails most baselines on IMDB-MULTI, and outperforms reported baselines on REDDIT-BIN.

B.3 Additional Experiments

  • The evaluation covers COLLAB, IMDB-MULTI, and REDDIT-BIN, graph-classification datasets without node or edge features, so prediction relies on graph structure.The datasets represent scientific collaboration, actor/actress collaboration, and Reddit-user discussion graphs, respectively.Source: §B.3 · p. 28
  • The study uses stratified 10-fold cross-validation and selects the epoch with the highest mean test accuracy across runs, adopting the protocol for comparability despite its lack of a clean validation–test split.Training lasts 200 epochs on COLLAB and REDDIT-BINARY and 500 epochs on IMDB-MULTI, with learning-rate decay every 20 or 50 epochs, respectively.Source: §B.3 · p. 29
  • CRaWl performs similarly to standard MPGNNs such as GIN on COLLAB, is slightly less accurate than most baselines on IMDB-MULTI, and outperforms all reported baselines on REDDIT-BIN.GSN, which leads on COLLAB and IMDB-MULTI, is infeasible on REDDIT-BIN’s graphs with several thousand nodes.Source: §B.3 · p. 29

B.4 Counting Substructures

On synthetic subgraph-counting graphs, CRaWl and GNN-AK outperform simple MPGNNs, with different strengths across target subgraphs.

B.4 Counting Substructures

  • The benchmark is graph-level regression that counts triangles, tailed triangles, 3-stars, and 4-cycles, with test MAE reported for each target.CRaWl uses six layers, hidden dimension 256, window size 8, and averages results over four models trained with different seeds.Source: §B.4 · p. 29
  • CRaWl achieves the best results for star counting, while GNN-AK has the lowest MAE for triangles and 4-cycles; both outperform simple MPGNNs such as GCN and GIN.The reported comparison indicates different strengths for CRaWl and subgraph GNNs such as GNN-AK.Source: §B.4 · p. 29
  • The counting-task pattern aligns with the paper’s main experiment: CRaWl does better than subgraph GNNs on molecular data, while GIN-AK+ does better on vision datasets.Source: §B.4 · p. 30

C Additional Proof Details

The proof first uses universal MLP filters to distinguish CFI graphs, though that simple argument may require exponential size and runtime in k. A more careful construction gives a polynomial-size MLP, and the exponential-growth observation does not affect proof correctness or the comparison with k-WL.

C.1 Detailed construction of the polynomial-size MLP

  • The simple universality argument may require an MLP whose size and runtime grow exponentially in k, without affecting proof correctness.The passage says this is also no limitation in comparing CRaWl with k-WL, whose runtime likewise grows exponentially with k; only k ≤3 is practically significant.Source: §C.1 · p. 30
  • The universal CNN filter can memorize CFI graph feature matrices, allowing CRaWl to distinguish Gk from Hk when k-WL fails.This is the proof's initial argument before the more careful polynomial-size construction.Source: §C.1 · p. 30
  • A Boolean circuit distinguishing CFI graphs can be simulated by a ReLU MLP with polynomial overhead, yielding a polynomial-size MLP in k.CFI graphs are distinguishable in polynomial time, so polynomial-size circuits can decide whether an adjacency matrix represents a graph isomorphic to Gk.Source: §C.1 · p. 30
Loading 2102.08786v3…