Abstract
Graph Neural Networks (GNNs) are powerful tools for graph-structured data but face a significant limitation: over-smoothing. As GNNs grow deeper, node embeddings tend to converge, losing discriminative power. We introduce ClusterDrop, a training-time augmentation module designed to combat over-smoothing by intelligently pruning "inter-class" edges. ClusterDrop utilizes learnable prototypes for efficient node clustering and leverages supervised signals to align these clusters with ground-truth classes. Our approach demonstrates superior performance across various benchmarks, particularly in deep GNN architectures, while maintaining computational efficiency.
Introduction
The "shallow" constraint of GNNs is a well-documented challenge. Adding layers often leads to node embeddings converging to identical values, a phenomenon known as over-smoothing. This renders the model ineffective for tasks like node classification. While topology augmentation (adding/removing edges) has been proposed, existing methods often rely on random dropping (DropEdge), rigid non-adaptive assumptions (GUIDE), or computationally heavy edge prediction (GAUG). There is a critical need for a method that can distinguish between intra-class edges (which preserve local smoothness) and inter-class edges (which cause global blurring) without excessive overhead.
Methodology: The ClusterDrop Framework
ClusterDrop is an intermediary module integrated into GNN layers during training. It operates through three primary mechanisms:
1. Prototype-Based Clustering
To avoid the high cost of traditional clustering algorithms like k-means, ClusterDrop employs a set of learnable "prototypes." Node embeddings are compared against these prototypes using cosine similarity. To prevent cluster collapse—where all nodes are assigned to a single cluster—the framework utilizes Optimal Transportation (via the Sinkhorn-Knopp algorithm) to ensure a uniform distribution of nodes across clusters.
2. Cluster-Guided Edge Dropping
Post-clustering, the model evaluates the Jensen-Shannon divergence between the cluster distributions of connected nodes. Edges connecting nodes with high divergence (likely belonging to different clusters) are assigned higher probabilities for removal. This targeted pruning effectively reduces problematic inter-class connectivity.
3. Supervised Smoothing via Anchors
In semi-supervised scenarios, ClusterDrop utilizes labeled nodes to establish "class anchors." A specialized loss function pulls cluster centers toward these anchors, ensuring that the learned clusters align with actual ground-truth classes, further refining the edge-dropping process.
Experimental Evaluation
ClusterDrop was evaluated on six benchmark datasets: Citation Networks (Cora, Citeseer, Pubmed), Wikipedia (Chameleon), Traffic (USA-Airport), and a large-scale graph (ogbn-arxiv). These datasets represent a wide range of modularity and structural characteristics.
Key Results
ClusterDrop consistently outperformed state-of-the-art (SOTA) methods across multiple backbones, including GCN, GraphSAGE, JKNet, and GAT.
- Resilience to Depth: In deep GCN experiments (up to 8 layers), ClusterDrop maintained high accuracy and cluster separation (Silhouette scores), whereas vanilla GCN performance dropped significantly.
- Scalability: Due to its linear time complexity relative to the number of nodes, ClusterDrop successfully scaled to the large ogbn-arxiv dataset, avoiding the memory issues common in edge-prediction models.
- Performance Gains: On the Chameleon dataset with a GCN backbone, ClusterDrop achieved 65.9% accuracy, a significant improvement over the vanilla GCN's 58.7%.
Discussion and Insights
The success of ClusterDrop stems from its ability to exploit the graph's inherent modularity. Even untrained GCNs capture some structural grouping, which ClusterDrop leverages to guide pruning. By using soft, weighted random sampling instead of hard deterministic pruning, the model remains robust to initial clustering errors. Furthermore, Theorem 1 in the paper provides theoretical backing, showing that removing inter-class edges allows node embeddings to converge to distinct class-specific directions even in deep networks.
Conclusion
ClusterDrop offers an efficient and effective solution to the over-smoothing problem in GNNs. By focusing on the removal of inter-class edges through prototype-based clustering and supervised anchors, it enables the training of deeper, more powerful GNNs. Its linear scalability and training-time-only nature make it a practical addition to the GNN practitioner's toolkit. Future work may explore extending this prototype logic to tasks like graph pooling and hierarchical representation learning.
Summary updated