Tackling Oversmoothing in GNN via Graph Sparsification: A Truss-based Approach
This addresses a key limitation in GNNs for graph analytics tasks, offering an incremental improvement by integrating sparsification into existing methods.
The paper tackles the oversmoothing problem in Graph Neural Networks (GNNs) by proposing a truss-based graph sparsification model that prunes edges in dense regions to prevent excessive mixing of node representations, and it significantly improves performance in graph classification tasks across various baseline GNN models.
Graph Neural Network (GNN) achieves great success for node-level and graph-level tasks via encoding meaningful topological structures of networks in various domains, ranging from social to biological networks. However, repeated aggregation operations lead to excessive mixing of node representations, particularly in dense regions with multiple GNN layers, resulting in nearly indistinguishable embeddings. This phenomenon leads to the oversmoothing problem that hampers downstream graph analytics tasks. To overcome this issue, we propose a novel and flexible truss-based graph sparsification model that prunes edges from dense regions of the graph. Pruning redundant edges in dense regions helps to prevent the aggregation of excessive neighborhood information during hierarchical message passing and pooling in GNN models. We then utilize our sparsification model in the state-of-the-art baseline GNNs and pooling models, such as GIN, SAGPool, GMT, DiffPool, MinCutPool, HGP-SL, DMonPool, and AdamGNN. Extensive experiments on different real-world datasets show that our model significantly improves the performance of the baseline GNN models in the graph classification task.