Introduction
Most Graph Neural Networks (GNNs) are inherently "short-sighted." Due to the local nature of message-passing mechanisms, these models typically only aggregate information from a node’s immediate neighborhood. While increasing the number of layers might seem like a solution to capture global structure, it often leads to detrimental effects such as over-smoothing—where node embeddings become indistinguishable—and over-squashing—where information from distant nodes is lost in a bottleneck.
Consequently, most practical GNNs are shallow (typically 2 to 5 layers), leaving them fundamentally incapable of capturing global graph properties like long-range connectivity or complex structural patterns. This paper investigates whether injecting global structural information can overcome these limitations and improve performance on common graph tasks.
Methodology
The authors propose three strategies to provide GNNs with a global perspective:
- Adjacency Matrix (AD): Concatenating a node's row from the adjacency matrix to its feature vector, providing a raw map of connectivity.
- Random Walk with Restart (RWR) Matrix: Concatenating RWR coefficients (similar to Personalized PageRank) to node features, offering a probabilistic measure of inter-node relationships across the entire graph.
- RWR + RWRReg: A novel regularization technique that penalizes the model if nodes with high RWR scores (global proximity) have significantly different embeddings.
Crucially, RWRReg is only applied during training. This ensures that the model remains efficient during inference, as it does not require additional parameters or expanded input features, yet it retains the benefits of having "learned" the global structure.
Experimental Setup
The proposed methods were evaluated across three distinct task categories:
- Node Classification: Benchmarked on the classic datasets Cora, Pubmed, and Citeseer.
- Graph Classification: Evaluated on biological and chemical datasets including ENZYMES, PROTEINS, and D&D.
- Structural Regression: Tested on the TRIANGLES dataset, where the goal is to count triangles—a task notoriously difficult for standard GNNs.
Key Results and Insights
The experimental results demonstrate that providing global context consistently closes performance gaps in state-of-the-art models like DiffPool and $k$-GNNs.
As shown in the node classification results, the RWR+RWRReg approach yields significant accuracy improvements. For instance, on the Cora dataset, a standard GCN's performance improved from 0.799 to 0.842. Similar trends were observed for GraphSage and GAT architectures, with RWRReg providing a consistent boost without increasing inference-time complexity.
In graph classification tasks, the impact was even more pronounced. On the ENZYMES dataset, the GCN model saw an accuracy jump from 57% to nearly 62%. Across all tasks and models, the RWRReg regularization alone resulted in an average accuracy improvement of over 5%.
Beyond raw accuracy, the study revealed that global information significantly aids generalization. On the TRIANGLES task, models injected with global context performed substantially better on larger, unseen graphs, reducing Mean Squared Error (MSE) by up to 19%. Theoretically, the authors showed that using RWR scores as initial "coloring" for the Weisfeiler-Leman (1-WL) algorithm allows it to converge in a single iteration, providing a formal justification for why RWR is so effective at distinguishing complex structures.
Limitations and Future Work
While effective, the approach faces scalability challenges. Pre-computing and storing RWR scores for "web-scale" graphs with millions of nodes can be memory-intensive, though the authors demonstrated that sparsification (keeping only "Top-K" scores) mitigates this. Future research could explore extending these techniques to dynamic graphs and automating the tuning of the regularization hyperparameter ($\lambda$).
Summary updated