Degree-based stratification of nodes in Graph Neural Networks

Ameen Ali, Hakan Cevikalp, Lior Wolf

Abstract

Despite much research, Graph Neural Networks (GNNs) still do not display the favorable scaling properties of other deep neural networks such as Convolutional Neural Networks and Transformers. Previous work has identified issues such as oversmoothing of the latent representation and have suggested solutions such as skip connections and sophisticated normalization schemes. Here, we propose a different approach that is based on a stratification of the graph nodes. We provide motivation that the nodes in a graph can be stratified into those with a low degree and those with a high degree and that the two groups are likely to behave differently. Based on this motivation, we modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods. To verify that this increase in performance is not only due to the added capacity, we also perform the same modification for random splits of the nodes, which does not lead to any improvement.

Introduction

Standard Graph Neural Networks (GNNs) typically apply a uniform set of weights to every node in a graph, regardless of its local connectivity or topological role. However, GNNs often suffer from a "paradox of depth": as the number of layers increases, node representations tend to converge to similar values, a phenomenon known as oversmoothing. This paper argues that treating all nodes as equal contributes to this issue. In most real-world graphs, "high-degree" nodes (hubs) reside within dense, well-defined clusters, while "low-degree" nodes often occupy the periphery or boundary regions where class labels may overlap. By forcing a single weight matrix to accommodate both stable hubs and ambiguous peripheral nodes, the model's expressive power is constrained.

Methodology: Degree-Based Stratification

The proposed solution is a "Degree-based Stratification" strategy that treats nodes differently based on their connectivity. The implementation follows a straightforward four-step process:

  1. Stratification: The degree of every node in the graph is calculated.
  2. Thresholding: A threshold ($\theta$) is used to partition nodes into two distinct groups: Low-Degree and High-Degree. This threshold can be determined automatically using techniques like Otsu’s method to identify natural gaps in the degree distribution.
  3. Dual Weight Matrices: Instead of a single weight matrix $W$ per layer, the architecture learns two separate matrices: $W_{low}$ and $W_{high}$.
  4. Modified Message Passing: During the update phase, the model applies the weight matrix corresponding to the node's degree group.

This modification is architecture-agnostic and was successfully integrated into GCN, GAT, and GraphSAGE models.

Experimental Setup

The method was evaluated on three benchmark citation networks:

  • Cora: 2,708 nodes, 5,278 edges, 7 classes.
  • CiteSeer: 3,327 nodes, 4,552 edges, 6 classes.
  • PubMed: 19,717 nodes, 44,338 edges, 3 classes.

In these datasets, nodes represent academic papers and edges represent citations, providing a standard testbed for node classification tasks.

Analysis and Key Insights

The Cluster Assumption and Oversmoothing

The authors hypothesize that decision boundaries should ideally lie in low-density regions. Low-degree nodes, which are more likely to reside in these regions, are critical for defining these boundaries. High-degree nodes are naturally more robust to oversmoothing because they are surrounded by many neighbors of the same class. By specializing weights for low-degree nodes, the model can better preserve their unique signals against the "washing out" effect of message passing.

Spectral Evidence

Analysis of the singular value spectrum of the adjacency matrices for the stratified groups reveals significant differences. Low-degree subgraphs exhibit a more uniform spectrum, suggesting that information propagates more slowly, which helps prevent the rapid collapse of representations. In contrast, high-degree subgraphs show a sharp decay in singular values, characteristic of dense, low-rank clusters.

Singular value spectrum for low-degree nodes in the Cora dataset, showing a more uniform distribution.
Singular value spectrum for high-degree nodes in the Cora dataset, showing a rapid decay characteristic of dense clusters.

Capacity vs. Topology

To ensure that performance gains were not simply due to increased parameter capacity, the authors conducted an ablation study using random node splits. Splitting nodes randomly into two groups actually decreased performance, confirming that the topological information captured by node degrees is essential to the success of the stratification strategy.

Key Results

The stratified approach consistently outperformed baseline GNNs across all tested datasets:

  • Accuracy Improvements: On CiteSeer, the GAT model's accuracy rose from 65.78% to 67.87%. On PubMed, GraphSAGE improved from 74.02% to 75.12%.
  • Universal Benefit: Accuracy improved for both low-degree and high-degree nodes. This suggests that specializing the weights allows the model to better fit both groups without compromising one for the other.
  • Robustness: While the optimal threshold $\theta$ typically fell between 2 and 5, the performance gains remained stable across a range of values.

Conclusion and Future Work

While the current binary split (low vs. high degree) provides significant gains, it represents a first step. Future work could explore finer-grained stratification or conditioning message passing on more complex local neighborhood features. Additionally, while the method introduces a hyperparameter $\theta$, automated selection methods mitigate the tuning burden. Overall, degree-based stratification offers a simple, effective way to improve GNN performance by acknowledging the heterogeneous roles nodes play in graph topology.

Summary updated

Abstract

Despite much research, Graph Neural Networks (GNNs) still do not display the favorable scaling properties of other deep neural networks such as Convolutional Neural Networks and Transformers. Previous work has identified issues such as oversmoothing of the latent representation and have suggested solutions such as skip connections and sophisticated normalization schemes. Here, we propose a different approach that is based on a stratification of the graph nodes. We provide motivation that the nodes in a graph can be stratified into those with a low degree and those with a high degree and that the two groups are likely to behave differently. Based on this motivation, we modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods. To verify that this increase in performance is not only due to the added capacity, we also perform the same modification for random splits of the nodes, which does not lead to any improvement.
BibTeX
@inproceedings{ali2023degree,
  author = {Ameen Ali and Hakan Cevikalp and Lior Wolf},
  title = {{Degree-based stratification of nodes in Graph Neural Networks}},
  booktitle = {ACML},
  year = {2023},
  url = {https://openreview.net/forum?id=srBGqVjAOd},
}
Figure