# Neural Trees for Learning on Graphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 78 references that are in the map.
- First posted on arXiv 15 May 2021.

## Builds on (most cited first, 30 of 48)

- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations](https://mlsanity.com/paper/1602.07332/) (2016)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Deep Visual-Semantic Alignments for Generating Image Descriptions](https://mlsanity.com/paper/1412.2306/) (2014)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [SPICE: Semantic Propositional Image Caption Evaluation](https://mlsanity.com/paper/1607.08822/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Scene Graph Generation by Iterative Message Passing](https://mlsanity.com/paper/1701.02426/) (2017)
- [Neural Motifs: Scene Graph Parsing with Global Context](https://mlsanity.com/paper/1711.06640/) (2017)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Visual Relationship Detection with Language Priors](https://mlsanity.com/paper/1608.00187/) (2016)
- [Few-Shot Learning with Graph Neural Networks](https://mlsanity.com/paper/1711.04043/) (2017)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Graph R-CNN for Scene Graph Generation](https://mlsanity.com/paper/1808.00191/) (2018)
- [3D Scene Graph: A Structure for Unified Semantics, 3D Space, and Camera](https://mlsanity.com/paper/1910.02527/) (2019)
- [Convolutional Mesh Regression for Single-Image Human Shape Reconstruction](https://mlsanity.com/paper/1905.03244/) (2019)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)

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

- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs](https://mlsanity.com/paper/2207.05006/) (2022)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Lumos: Heterogeneity-aware Federated Graph Learning over Decentralized Devices](https://mlsanity.com/paper/2303.00492/) (2023)
- [Learning High-level Semantic-Relational Concepts for SLAM](https://mlsanity.com/paper/2310.00401/) (2023)
- [Tree-Constrained Graph Neural Networks For Argument Mining](https://mlsanity.com/paper/2110.00124/) (2021)
- [Phishing the Phishers with SpecularNet: Hierarchical Graph Autoencoding for Reference-Free Web Phishing Detection](https://mlsanity.com/paper/2603.01874/) (2026)
- [Generation of High-Level Concepts in 3D Scene Graphs via Autoregressive Diffusion](https://mlsanity.com/paper/2608.28733/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have emerged as a flexible and powerful approach for learning over graphs. Despite this success, existing GNNs are constrained by their local message-passing architecture and are provably limited in their expressive power. In this work, we propose a new GNN architecture -- the Neural Tree. The neural tree architecture does not perform message passing on the input graph, but on a tree-structured graph, called the H-tree, that is constructed from the input graph. Nodes in the H-tree correspond to subgraphs in the input graph, and they are reorganized in a hierarchical manner such that the parent of a node in the H-tree always corresponds to a larger subgraph in the input graph. We show that the neural tree architecture can approximate any smooth probability distribution function over an undirected graph. We also prove that the number of parameters needed to achieve an ε-approximation of the distribution function is exponential in the treewidth of the input graph, but linear in its size. We prove that any continuous G-invariant/equivariant function can be approximated by a nonlinear combination of such probability distribution functions over G. We apply the neural tree to semi-supervised node classification in 3D scene graphs, and show that these theoretical properties translate into significant gains in prediction accuracy, over the more traditional GNN architectures. We also show the applicability of the neural tree architecture to citation networks with large treewidth, by using a graph sub-sampling technique.