# Tree Decomposed Graph Neural Network

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 25 Aug 2021.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Self-supervised Learning on Graphs: Deep Insights and New Direction](https://mlsanity.com/paper/2006.10141/) (2020)
- [Batch Virtual Adversarial Training for Graph Convolutional Networks](https://mlsanity.com/paper/1902.09192/) (2019)
- [Deep Graph Neural Networks with Shallow Subgraph Samplers](https://mlsanity.com/paper/2012.01380/) (2020)
- [A Simple Spectral Failure Mode for Graph Convolutional Networks](https://mlsanity.com/paper/2010.13152/) (2020)

## Built on by (most cited first, 30 of 35)

- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage](https://mlsanity.com/paper/2206.03426/) (2022)
- [Simplifying approach to Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2111.06748/) (2021)
- [Local Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2109.03856/) (2021)
- [AutoReproduce: Automatic AI Experiment Reproduction with Paper Lineage](https://mlsanity.com/paper/2505.20662/) (2025)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applications](https://mlsanity.com/paper/2308.16375/) (2023)
- [Distance-wise Prototypical Graph Neural Network in Node Imbalance Classification](https://mlsanity.com/paper/2110.12035/) (2021)
- [On Structural Explanation of Bias in Graph Neural Networks](https://mlsanity.com/paper/2206.12104/) (2022)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Collaboration-Aware Graph Convolutional Network for Recommender Systems](https://mlsanity.com/paper/2207.06221/) (2022)
- [Road Network Representation Learning: A Dual Graph based Approach](https://mlsanity.com/paper/2304.07298/) (2023)
- [MGNN: Graph Neural Networks Inspired by Distance Geometry Problem](https://mlsanity.com/paper/2201.12994/) (2022)
- [A Piece-wise Polynomial Filtering Approach for Graph Neural Networks](https://mlsanity.com/paper/2112.03499/) (2021)
- [The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs](https://mlsanity.com/paper/2406.12539/) (2024)
- [Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shifts](https://mlsanity.com/paper/2408.09490/) (2024)
- [GCNH: A Simple Method For Representation Learning On Heterophilous Graphs](https://mlsanity.com/paper/2304.10896/) (2023)
- [Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks](https://mlsanity.com/paper/2312.16418/) (2023)
- [Disambiguated Node Classification with Graph Neural Networks](https://mlsanity.com/paper/2402.08824/) (2024)
- [Detecting Socially Abnormal Highway Driving Behaviors via Recurrent Graph Attention Networks](https://mlsanity.com/paper/2304.11513/) (2023)
- [Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection](https://mlsanity.com/paper/2403.10339/) (2024)
- [Hierarchical and Contrastive Representation Learning for Knowledge-aware Recommendation](https://mlsanity.com/paper/2304.07506/) (2023)
- [Augmenting Textual Generation via Topology Aware Retrieval](https://mlsanity.com/paper/2405.17602/) (2024)
- [GPNet: Simplifying Graph Neural Networks via Multi-channel Geometric Polynomials](https://mlsanity.com/paper/2209.15454/) (2022)
- [Cloud-RAIN: Point Cloud Analysis with Reflectional Invariance](https://mlsanity.com/paper/2305.07814/) (2023)
- [Tackling Oversmoothing in GNN via Graph Sparsification: A Truss-based Approach](https://mlsanity.com/paper/2407.11928/) (2024)
- [Gauge-Equivariant Graph Networks via Self-Interference Cancellation](https://mlsanity.com/paper/2511.16062/) (2025)
- [Phishing the Phishers with SpecularNet: Hierarchical Graph Autoencoding for Reference-Free Web Phishing Detection](https://mlsanity.com/paper/2603.01874/) (2026)
- [Attention-based graph neural networks: a survey](https://mlsanity.com/paper/2605.08679/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have achieved significant success in learning better representations by performing feature propagation and transformation iteratively to leverage neighborhood information. Nevertheless, iterative propagation restricts the information of higher-layer neighborhoods to be transported through and fused with the lower-layer neighborhoods', which unavoidably results in feature smoothing between neighborhoods in different layers and can thus compromise the performance, especially on heterophily networks. Furthermore, most deep GNNs only recognize the importance of higher-layer neighborhoods while yet to fully explore the importance of multi-hop dependency within the context of different layer neighborhoods in learning better representations. In this work, we first theoretically analyze the feature smoothing between neighborhoods in different layers and empirically demonstrate the variance of the homophily level across neighborhoods at different layers. Motivated by these analyses, we further propose a tree decomposition method to disentangle neighborhoods in different layers to alleviate feature smoothing among these layers. Moreover, we characterize the multi-hop dependency via graph diffusion within our tree decomposition formulation to construct Tree Decomposed Graph Neural Network (TDGNN), which can flexibly incorporate information from large receptive fields and aggregate this information utilizing the multi-hop dependency. Comprehensive experiments demonstrate the superior performance of TDGNN on both homophily and heterophily networks under a variety of node classification settings. Extensive parameter analysis highlights the ability of TDGNN to prevent over-smoothing and incorporate features from shallow layers with deeper multi-hop dependencies, which provides new insights towards deeper graph neural networks. Code of TDGNN: http://github.com/YuWVandy/TDGNN