# DeGNN: Characterizing and Improving Graph Neural Networks with Graph Decomposition

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2019.

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

- [Graph-ToolFormer: To Empower LLMs with Graph Reasoning Ability via Prompt Augmented by ChatGPT](https://mlsanity.com/paper/2304.11116/) (2023)
- [Syntax-BERT: Improving Pre-trained Transformers with Syntax Trees](https://mlsanity.com/paper/2103.04350/) (2021)

## Abstract (arXiv)

Despite the wide application of Graph Convolutional Network (GCN), one major limitation is that it does not benefit from the increasing depth and suffers from the oversmoothing problem. In this work, we first characterize this phenomenon from the information-theoretic perspective and show that under certain conditions, the mutual information between the output after l layers and the input of GCN converges to 0 exponentially with respect to l. We also show that, on the other hand, graph decomposition can potentially weaken the condition of such convergence rate, which enabled our analysis for GraphCNN. While different graph structures can only benefit from the corresponding decomposition, in practice, we propose an automatic connectivity-aware graph decomposition algorithm, DeGNN, to improve the performance of general graph neural networks. Extensive experiments on widely adopted benchmark datasets demonstrate that DeGNN can not only significantly boost the performance of corresponding GNNs, but also achieves the state-of-the-art performances.