Introduction
Graph Neural Networks (GNNs) have become the standard for learning on graph-structured data. However, they suffer from a significant bottleneck known as "over-smoothing." As more layers are added to a GNN to capture long-range dependencies, node representations tend to converge toward a uniform mean, losing their individual characteristics. While techniques like DropEdge or PairNorm have been developed to mitigate this in node classification, they often fall short in graph classification tasks. This paper addresses this gap by proposing an entropy-based perspective on over-smoothing, focusing on preserving the structural "fingerprint" of graphs.
The Entropy Perspective on Over-smoothing
The core challenge in graph classification is maintaining the distinguishability of non-isomorphic graphs. Traditional anti-smoothing methods focus on increasing the Euclidean distance between node features. However, for graph-level tasks, it is more critical to preserve "key structural characteristics"—the complex, high-information parts of the graph.
As illustrated in Figure 4, graphs with higher structural entropy ($H(G)$) are more susceptible to losing their unique identities through smoothing. When these high-entropy regions are smoothed out, the model loses the ability to differentiate between structurally distinct graphs, leading to poor classification performance. The authors argue that protecting these specific areas is more efficient than trying to prevent smoothing across the entire graph.
The SDE Framework
To combat this, the authors introduce SDE (Sample and Discretize node features in high-Entropic regions). The SDE module is designed to identify and protect the most informative regions of a graph during the message-passing process.
The SDE pipeline, shown in Figure 5, consists of three primary innovations:
- Top-k Entropy Selection: The model calculates "depth-based subgraph entropy" for each node to identify structurally complex regions. The top-$k$ nodes with the highest entropy are prioritized for special treatment.
- Sampling and Discretization: To prevent these critical nodes from melting into a continuous average, the authors employ a Gumbel-Softmax trick. This allows for discrete sampling of node features during training, "hardening" the representations into distinct categories rather than letting them melt into a continuous average.
- Jensen-Shannon Divergence (JSD): A new metric is proposed to measure over-smoothing. Unlike traditional average distance metrics, JSD captures distributional nuances, providing a better indicator of how distinct node distributions remain across layers.
Experimental Evaluation
The SDE method was evaluated on seven standard benchmarks, including bioinformatics (MUTAG, PROTEINS, DD) and social networks (COLLAB, IMDB). Using GIN and GCN as backbones, SDE consistently outperformed state-of-the-art methods like ContraNorm and DropEdge.
For instance, on the PROTEINS dataset with a GIN backbone, SDE achieved an accuracy of 76.62%, surpassing the baseline GIN's 75.61%. Crucially, while standard GNN performance typically plummets after 8–10 layers due to over-smoothing, SDE maintained stable accuracy and high JSD values, demonstrating its effectiveness in deep architectures. Ablation studies further confirmed that protecting high-entropy regions is significantly more effective than protecting low-entropy ones.
Conclusion
By shifting the focus from node distance to structural entropy, the SDE method provides a robust solution to the over-smoothing problem in graph classification. Protecting high-information regions through discretization ensures that critical structural details are preserved even in deep networks. Future work may explore more advanced entropy measures, such as von Neumann entropy, or quantum-inspired methods to further refine the localization of critical graph structures.
Summary updated