Random Walk Graph Neural Networks

Giannis Nikolentzos, Michalis VazirgiannisNeurIPS 2020 · OpenReview

Graph Neural Networks (GNNs) have become the standard for machine learning on graph-structured data. However, most modern GNNs—specifically those in the Message Passing Neural Network (MPNN) family—act largely as black boxes. They iteratively aggregate local node features and compress them into dense vectors, obscuring the explicit structural interactions between vertices. This makes it incredibly difficult to understand what specific graph structures or motifs the model relies on to make its predictions.

Before the deep learning era, graph kernels were the standard. They directly compared graph structures (e.g., by counting matching subgraphs or random walks) and were highly interpretable. However, they relied on fixed, hand-engineered features and lacked the ability to learn task-specific representations end-to-end.

In "Random Walk Graph Neural Networks," the authors introduce a novel architecture (RWNN) that tackles this challenge, successfully combining the end-to-end representation learning of neural networks with the structural transparency of graph kernels.

The RWNN Architecture

The core innovation of the Random Walk Graph Neural Network lies in its first layer. Instead of standard fully-connected weight matrices, the first layer of an RWNN consists of $N$ trainable "hidden graphs." Both the adjacency matrices (defining the structure) and the node attributes of these hidden graphs are learnable parameters updated via backpropagation.

RWNN Architecture

To process an input graph, the model compares it against these $N$ hidden graphs using a differentiable $P$-step random walk kernel. This kernel counts the number of matching walks of length $p$ between the input graph and the hidden graphs. The resulting similarity scores are then passed into a standard fully-connected neural network to output a final prediction.

The Efficiency Trick: Computing random walks on the direct product of two graphs is notoriously memory and compute-intensive. To make this feasible, the authors leverage a mathematical property of the Kronecker product. This allows them to compute the kernel values without ever explicitly constructing the massive product graph, drastically reducing the computational time complexity.

Key Insights and Interpretability

The most significant advantage of RWNN is that it is interpretable by design. Because the network's parameters are actual graphs, researchers can directly visualize the weights after training. This provides an intuitive window into the structural motifs the model uses to distinguish between classes—an invaluable feature for high-stakes fields like drug discovery or materials science.

To test this, the authors created synthetic datasets by planting specific structural motifs (Caveman, Cycle, Grid, Ladder, Star) into random Erdös-Rényi graphs.

Learned Hidden Graphs

Visualizing the learned "hidden graphs" revealed that the network successfully reverse-engineered the planted motifs. For example, the model learned triangle structures to identify the Caveman dataset and 4-node cycles for the Grid dataset.

Quantitative Performance

Beyond interpretability, RWNN is highly competitive with state-of-the-art models. Evaluated across 10 standard public graph classification datasets (spanning chemo/bio-informatics and social interaction networks), the model demonstrated strong performance:

  • State-of-the-Art Results: RWNN outperformed all baselines—including strong GNNs like GIN and GraphSAGE, as well as traditional kernels like WL—on several datasets, notably achieving 89.2% accuracy on MUTAG and 90.4% accuracy on REDDIT-BINARY.
  • Comparison to GIN: RWNN offered absolute accuracy improvements over the popular GIN architecture of 4.5% on MUTAG, 2.3% on D&D, and 1.4% on PROTEINS.
  • The Power of Short Walks: Interestingly, the authors found that the 1-step RWNN (which only looks at walks of length 1, representing direct edges) often outperformed the 2-step and 3-step variants on real-world datasets. This suggests that simple, local connectivity is often the strongest signal for these specific benchmark tasks.

Limitations and Future Directions

While the computation scheme is heavily optimized, comparing graphs via random walks remains inherently more computationally demanding than standard message passing. Furthermore, the authors caution against "blind trust" in interpretable models; human expert supervision is still required to properly interpret the learned motifs in complex domains.

Looking forward, the authors plan to extend the RWNN architecture to unsupervised settings. By removing the reliance on labeled targets, the model could serve as a powerful, automated motif-discovery engine, uncovering the full spectrum of hidden structural features within complex graph data.

Summary updated

Abstract

In recent years, graph neural networks (GNNs) have become the de facto tool for performing machine learning tasks on graphs. Most GNNs belong to the family of message passing neural networks (MPNNs). These models employ an iterative neighborhood aggregation scheme to update vertex representations. Then, to compute vector representations of graphs, they aggregate the representations of the vertices using some permutation invariant function. One would expect the hidden layers of a GNN to be composed of parameters that take the form of graphs. However, this is not the case for MPNNs since their update procedure is parameterized by fully-connected layers. In this paper, we propose a more intuitive and transparent architecture for graph-structured data, so-called Random Walk Graph Neural Network (RWNN). The first layer of the model consists of a number of trainable ``hidden graphs'' which are compared against the input graphs using a random walk kernel to produce graph representations. These representations are then passed on to a fully-connected neural network which produces the output. The employed random walk kernel is differentiable, and therefore, the proposed model is end-to-end trainable. We demonstrate the model's transparency on synthetic datasets. Furthermore, we empirically evaluate the model on graph classification datasets and show that it achieves competitive performance.
BibTeX
@inproceedings{nikolentzos2020random,
  author = {Giannis Nikolentzos and Michalis Vazirgiannis},
  title = {{Random Walk Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=zJFMYfLX9Ow},
}
Figure