TL;DR
This paper challenges the common understanding that Graph Neural Networks (GNNs) are inherently limited by "oversmoothing" as they get deeper. The authors propose that the issue isn't a fundamental flaw of GNNs, but rather a failure of the learning process to find "proper" weights. They introduce WeightRep, a novel method to dynamically adjust these weights during training, enabling GNNs to avoid oversmoothing even with infinite layers.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) have become incredibly powerful for analyzing graph-structured data, finding applications in everything from social networks to drug discovery. However, a persistent problem is "oversmoothing": as GNNs get deeper (more layers), the representations of nodes tend to become too similar, leading to a significant drop in performance. This has led many to believe that GNNs are best used with only a few layers. Previous explanations for oversmoothing have largely focused on the message-passing mechanism itself, assuming that deeper propagation inevitably leads to feature collapse. This paper questions this assumption, suggesting that the role of learnable weights has been overlooked or underestimated.
Methods
The core of this paper is a theoretical re-evaluation of oversmoothing from the perspective of GNN weights. The authors first analyze GNNs in three scenarios:
- Without weights: They show that without weight transformations, oversmoothing is indeed inevitable, with node representations converging to a single value.
- With random weights: They demonstrate that random weight initialization, even with standard schemes like Xavier, leads to a collapse in representation quality, contributing to oversmoothing.
- With freely learnable weights: This is where the key insight lies. The authors theoretically prove that for vanilla GNNs (like GCN), there exist ideal weights that can prevent oversmoothing, even after infinite propagation steps. This suggests oversmoothing is a learning problem, not a structural one.
To address this learning challenge, they propose Weight Reparameterization (WeightRep). This method dynamically constructs input-dependent weights for each layer. Essentially, it aims to maintain these "ideal" weights throughout the training process, ensuring that node representations remain distinct. WeightRep is described as a special normalization layer, similar in spirit to LayerNorm but adapted for graph structures.
Datasets
The paper evaluates WeightRep on nine common graph node classification datasets:
- Homophily benchmarks: Cora, CiteSeer, Pubmed, Computers, Photo, CoauthorCS, CoauthorPhysics.
- Heterophily benchmarks: Wikipedia Chameleon, Wikipedia Squirrel.
These datasets vary in graph size and feature type, providing a comprehensive evaluation across different graph characteristics.
Key Insights and Ideas
- Oversmoothing is a learning problem, not a structural doom: The most significant insight is that GNNs can escape oversmoothing if their weights are learned correctly. This shifts the focus from the inherent limitations of graph propagation to the challenges of optimization.
- The overlooked power of weights: The paper highlights that previous analyses often neglected or made simplifying assumptions about GNN weights, leading to the conclusion that oversmoothing was unavoidable.
- Existence of "ideal" weights: The theoretical proof that ideal weights exist for vanilla GNNs to avoid oversmoothing is a crucial finding. It suggests that the problem lies in the optimizer's ability to find these weights.
- WeightRep as a practical solution: The proposed WeightRep method provides a concrete mechanism to guide the learning process towards these ideal weights, effectively mitigating oversmoothing.
- Beyond simple normalization: While WeightRep shares similarities with normalization techniques, its input-dependent nature and focus on maintaining feature distinctiveness offer a novel approach to the oversmoothing problem.
Key Results
- Significant performance improvements: WeightRep consistently outperforms vanilla GCNs and GCNs with standard normalization techniques (LayerNorm, PairNorm, ContraNorm) across various depths and datasets.
- Effectiveness on deeper GNNs: The method shows substantial gains even for deeper GCNs (e.g., 4 and 8 layers), where vanilla GCNs typically suffer severe performance degradation. For instance, on Cora, WeightRep improved 4-layer GCN performance by 5.50% and 8-layer GCN by 55.12%.
- Mitigation of dimensional collapse: Theoretical analysis and experimental results suggest that WeightRep also helps prevent dimensional collapse, a related issue where features might lie in a low-dimensional subspace.
- Acceptable computational cost: While slightly slower than vanilla GCN and PairNorm, WeightRep's additional computational complexity is manageable and linearly dependent on the number of nodes, making it practical for large graphs.
Limitations and Future Work
- Optimizer limitations: The authors acknowledge that while ideal weights exist, current optimizers may still struggle to find them perfectly, especially with non-linear activation functions. This suggests that further research into optimization strategies for GNNs could be beneficial.
- Beyond oversmoothing: The paper notes that even with WeightRep, some performance degradation can occur with extreme depths. This indicates that oversmoothing might not be the sole cause of performance issues in deep GNNs, and other factors like the difficulty of finding discriminative features might play a role. The authors suggest further study on these additional factors for future work.
- Hyperparameter sensitivity: While WeightRep is shown to be robust to the power exponent
p, further exploration of other hyperparameters and their impact could be valuable.
Summary updated