TL;DR
This paper uses the Neural Tangent Kernel (NTK) to theoretically analyze Graph Neural Networks (GNNs). It provides a rigorous explanation for why row-normalized graph convolutions outperform symmetric ones, why linear GNNs can be as effective as ReLU-activated ones, and how depth and skip connections impact GNN performance, particularly concerning over-smoothing.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) have become a powerful tool for learning from graph-structured data. A core component of GNNs is the "graph convolution," which aggregates information from neighboring nodes. While symmetric normalization of the adjacency matrix has been the dominant choice for these convolutions, empirical studies suggest that row normalization can yield better results for node classification. Furthermore, it's been observed that linear GNNs can perform comparably to or even better than GNNs with non-linear activations like ReLU, a phenomenon that lacks a strong theoretical explanation. Despite the widespread use of GNNs, there's a need for a deeper theoretical understanding of how different architectural choices—specifically, the type of graph convolution, network depth, and activation functions—influence their representation power and performance, particularly in the context of over-smoothing.
Methods
The authors leverage the Neural Tangent Kernel (NTK) framework to analyze GNNs in an infinite-width limit. This approach allows them to derive a deterministic kernel that captures the behavior of wide neural networks trained with gradient descent, effectively bypassing the complexities of finite-width training and hyperparameter tuning. They analyze GNNs under a Degree Corrected Stochastic Block Model (DC-SBM), a random graph model that allows for distinguishing between different graph convolution operators and modeling various graph structures (homophilic, heterophilic, core-periphery). The core of their analysis involves deriving and comparing the population NTKs for different GCN architectures and convolution types, focusing on their ability to preserve "class information" (i.e., the underlying community structure).
Datasets
The theoretical findings are validated on:
- Cora: A widely used citation network dataset for node classification.
- Citeseer: Another citation network dataset.
The authors also use synthetic graphs generated from the Degree Corrected Stochastic Block Model (DC-SBM) to test their theoretical framework under controlled conditions.
Key Insights and Ideas
- Linear vs. ReLU: Linear GCNs capture class information as effectively as ReLU GCNs, challenging the conventional wisdom that non-linearity is always essential for complex representation learning in GNNs.
- Row Normalization Dominance: Row normalization ($S_{row}$) of the adjacency matrix preserves class structure better than symmetric normalization ($S_{sym}$) and other variants, especially in homophilic and heterophilic graphs. This explains its empirical success.
- Depth and Over-smoothing: Network depth leads to performance degradation due to over-smoothing, where node representations become indistinguishable. However, $S_{row}$ exhibits the slowest loss of class information with increasing depth.
- Skip Connections as a Cure: Skip connections effectively mitigate over-smoothing, allowing GNNs to retain class information even at infinite depth.
Key Results
- Theoretical Equivalence: Linear GCNs are shown to capture class information as well as, or even slightly better than, ReLU GCNs under the DC-SBM model.
- Convolutional Operator Ranking: The theoretical analysis suggests a preference order for graph convolutions in preserving class information: $S_{row} > S_{sym} > S_{col} > S_{adj}$. This is empirically validated on Cora and Citeseer datasets.
- Depth Impact: For vanilla GCNs, class separability (and thus performance) degrades exponentially with depth. This degradation is slowest for $S_{row}$.
- Skip Connection Efficacy: Skip connections (both Skip-PC and Skip-a) are shown to retain class information even at infinite depth, effectively eliminating the detrimental effects of over-smoothing.
- Empirical Validation: Theoretical findings are consistently supported by numerical experiments on both synthetic DC-SBM graphs and real-world datasets like Cora and Citeseer. For instance, on Cora, $S_{row}$ consistently shows clearer block structures than $S_{sym}$ in NTKs, reflecting better class information preservation.
Limitations and Future Work
- DC-SBM Assumption: The theoretical analysis relies on the DC-SBM model, which might be restrictive. While experiments on real datasets suggest the findings generalize, a formal characterization without this assumption is challenging.
- Orthonormal Features: The initial analysis assumes orthonormal features ($XX^T = I_n$), which simplifies the identification of convolution operator influences. Extending this to non-orthonormal features using Contextual Stochastic Block Models is suggested for further insights.
- Feature-Graph Interplay: The current work primarily focuses on graph structure. Analyzing the interplay between graph structure and node features more deeply is a promising direction.
- New Convolutions: The framework can be extended to analyze novel graph convolutions and other graph learning problems like link prediction.
- Class Separability Measure: While class separability is a good indicator, it doesn't always perfectly capture all trends observed in MSE and accuracy. Further research into alternative measures is suggested.
Summary updated