TL;DR
This paper investigates whether Graph Neural Networks (GNNs), which typically focus on local graph structures, benefit from incorporating global structural information. The authors demonstrate that injecting global information significantly improves performance on various graph-related tasks and introduce a novel, practical regularization technique (RWR-Reg) that achieves substantial accuracy gains without increasing model complexity.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) have achieved state-of-the-art results in many graph-structured data tasks. However, a common limitation of GNNs, particularly those based on the message-passing framework, is the "over-smoothing" and "over-squashing" problem. This occurs when information from distant nodes gets diluted as the network depth increases, forcing practical GNNs to use only a few layers. Consequently, these models primarily leverage local neighborhood information and may miss crucial global structural patterns within the graph. While the theoretical limitations of GNNs have been studied, the practical necessity of global structural information for real-world applications remains an open question. This paper aims to empirically address this by injecting global information into GNNs and evaluating its impact.
Methods
The authors explore three main strategies for injecting global structural information into GNNs:
- Adjacency Matrix: Directly providing the GNN with the full adjacency matrix, effectively concatenating each node's connectivity information to its feature vector. This allows models to reason about node connectivity at a higher level.
- Random Walks with Restart (RWR): Utilizing RWR to generate a vector for each node that captures its global relationship with all other nodes in the graph. This vector is then concatenated with the node's feature vector. RWR is known to capture global graph structure.
- RWR Regularization (RWR-Reg): A novel regularization technique that encourages nodes with similar RWR scores (indicating similar global relationships) to have similar embeddings. This is formulated as an additional loss term during training.
The paper also introduces a theoretical connection between RWR and the 1-Weisfeiler-Leman (1-WL) algorithm, suggesting that RWR can enhance a graph's distinguishability, which is a key capability for GNNs.
Datasets
The paper uses standard benchmark datasets for its evaluations:
- Node Classification: Cora, Pubmed, Citeseer.
- Graph Classification: ENZYMES, PROTEINS, D&D.
- Triangle Counting: TRIANGLES dataset.
Key Insights and Ideas
- Global Information is Crucial: Contrary to the common practice of relying solely on local neighborhoods due to GNN limitations, this work empirically shows that global structural information significantly benefits GNN performance across various tasks.
- RWR-Reg is a Practical Solution: While directly injecting adjacency matrices or RWR vectors can be computationally expensive or impractical for large graphs, the proposed RWR-Reg regularization technique offers a way to leverage global information effectively without increasing model complexity or inference time.
- RWR Enhances Graph Distinguishability: The theoretical link between RWR and the 1-WL algorithm provides a strong rationale for why RWR is effective, suggesting it helps GNNs distinguish between non-isomorphic graphs more efficiently.
- Even Advanced Models Benefit: The study reveals that even sophisticated GNN architectures like DiffPool and k-GNN, designed for complex graph tasks, show notable improvements when global information is injected, highlighting a fundamental limitation in current GNN designs.
Key Results
- Node Classification: Injecting RWR features alone provides up to a 2% accuracy gain. The RWR-Reg term further boosts performance, leading to an average gain of up to 7.5% across models and datasets.
- Graph Classification: The impact of global information is even more pronounced here, with adjacency matrix injection alone providing up to an 11% boost. RWR-Reg also yields significant improvements.
- Triangle Counting: RWR features and RWRReg provide substantial benefits, with improvements of up to 19%, especially when generalizing to graphs of unseen sizes.
- RWR-Reg Performance: Using only the RWR-Reg term (without explicit RWR features) leads to an average performance increase of over 5% across all tested models and tasks, demonstrating its practical utility.
- RWR Sparsification: The paper shows that sparsifying the RWR matrix (keeping only top-K weights) can reduce memory usage while still providing significant accuracy improvements (average 3.2% increase) over models without global information.
Limitations and Future Work
- Scalability of Direct Injection: Directly injecting adjacency matrices or RWR vectors can be computationally prohibitive for very large graphs due to increased input size and model parameters.
- RWR Matrix Storage: While RWR-Reg is efficient, storing the full RWR matrix during training can still be a memory bottleneck for extremely large graphs. The paper addresses this with sparsification.
- Practical Implementation of RWR-Reg with GAT: The authors note challenges in naively applying RWR-Reg to GATs due to their attention mechanism, requiring a modified approach to align RWR-Reg with attention weights.
- Future Work: The paper suggests exploring more efficient methods for computing RWR and its regularization, as well as investigating the impact of global information on other graph-related tasks and GNN architectures. The theoretical connection to 1-WL also opens avenues for further research into GNN expressivity.
Summary updated