# Tackling Oversmoothing in GNN via Graph Sparsification: A Truss-based Approach

arXiv: https://arxiv.org/abs/2407.11928 · HTML: https://mlsanity.com/paper/2407.11928/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 16 Jul 2024.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Graph-Coupled Oscillator Networks](https://mlsanity.com/paper/2202.02296/) (2022)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [Hierarchical Graph Pooling with Structure Learning](https://mlsanity.com/paper/1911.05954/) (2019)
- [Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2204.07321/) (2022)
- [Node Dependent Local Smoothing for Scalable Graph Learning](https://mlsanity.com/paper/2110.14377/) (2021)
- [Tree Decomposed Graph Neural Network](https://mlsanity.com/paper/2108.11022/) (2021)
- [Second-Order Pooling for Graph Neural Networks](https://mlsanity.com/paper/2007.10467/) (2020)
- [HyGNN: Drug-Drug Interaction Prediction via Hypergraph Neural Network](https://mlsanity.com/paper/2206.12747/) (2022)
- [Recommender systems based on graph embedding techniques: A comprehensive review](https://mlsanity.com/paper/2109.09587/) (2021)
- [Multi-grained Semantics-aware Graph Neural Networks](https://mlsanity.com/paper/2010.00238/) (2020)

## Built on by (most cited first, 1 of 1)

- [Cross-attentive Cohesive Subgraph Embedding to Mitigate Oversquashing in GNNs](https://mlsanity.com/paper/2603.27529/) (2026)

## Abstract (arXiv)

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.