The Challenge of Oversmoothing
Graph Neural Networks (GNNs) are powerful tools for learning on graph-structured data, but they are notoriously difficult to scale. As more layers are added, GNNs suffer from a phenomenon known as oversmoothing: node features become increasingly similar until they are indistinguishable, causing model performance to plummet.
Traditionally, researchers have quantified oversmoothing using "energy-like" metrics, such as Dirichlet energy, which measures the similarity of neighboring node features. However, these metrics have a critical blind spot. They typically only show significant decay in extremely deep (e.g., 100+ layers), untrained networks. In practice, real-world GNNs often experience severe performance degradation at much shallower depths—sometimes with as few as 10 layers—while Dirichlet energy remains deceptively high. If our metrics do not signal trouble until long after the model has failed, they are inadequate for understanding or preventing the problem.
A Dimensionality Perspective: Rank-Based Metrics
To address this gap, the authors advocate for measuring the dimensionality of the feature space rather than merely the similarity of neighboring nodes. Oversmoothing is not just about nodes becoming "similar"; it is about the entire feature matrix losing its expressivity and collapsing into a low-dimensional subspace.
The paper proposes using two continuous relaxations of the matrix rank:
- Numerical Rank ($NumRank$): The ratio of the Frobenius norm squared to the spectral norm squared.
- Effective Rank ($Erank$): An entropy-based measure of the distribution of singular values.
Unlike traditional energy metrics, these rank-based measures are scale-invariant. They focus on the relationship between features regardless of their absolute scale, making them robust against exploding or vanishing features.
Theoretically, the authors provide a unifying perspective using nonlinear activation eigenvectors. They prove that for a broad family of GNN architectures—including linear models and those with non-negative weights and activations—the numerical rank of feature representations is mathematically guaranteed to collapse to one as depth increases.
Empirical Evidence: Rank vs. Accuracy
The authors conducted an extensive numerical evaluation across diverse graph architectures (GCN and GAT) and datasets, including homophilic graphs (Cora, Citeseer, Pubmed), heterophilic graphs (Squirrel, Chameleon, Amazon Ratings), and large-scale datasets (OGB-Arxiv).
The most striking takeaway is the strong correlation between rank-based metrics and actual classification accuracy. Much of the existing literature relies on "effectively untrained" networks with small weight initializations. When GNNs are properly trained, traditional energy metrics often fail to correlate with accuracy. Rank-based metrics, however, remain highly predictive.
Across almost all datasets and architectures, Effective Rank ($Erank$) demonstrated a remarkably high Pearson correlation with accuracy, averaging 0.91. In contrast, Dirichlet energy often showed poor or even negative correlation. For instance, in experiments with GCNs on the Cora dataset, accuracy dropped significantly by layer 10. During this drop, Dirichlet energy remained relatively stable, while the Effective Rank showed a sharp, corresponding decline, serving as an accurate early warning system. Furthermore, rank-based metrics continued to track performance degradation accurately even when complex components like BatchNorm, LayerNorm, or bias terms were added—elements that often "break" traditional oversmoothing metrics.
Limitations and Future Directions
While rank-based metrics offer a significant improvement over energy-based ones, the authors acknowledge a fundamental limitation: a low rank is a sure sign of oversmoothing and poor performance, but a high rank does not guarantee good performance. For example, a matrix of random noise has a very high rank but contains no useful information for classification. Therefore, rank is a necessary, but not sufficient, condition for a healthy GNN.
Looking forward, these rank-based metrics hold promise beyond just measurement. They could potentially be utilized as regularizers during training. By penalizing models when their feature rank begins to collapse, researchers could design deeper, more stable, and more expressive GNN architectures.