# Two-level Graph Neural Network

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 3 Jan 2022.

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

- [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 Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Directional Message Passing for Molecular Graphs](https://mlsanity.com/paper/2003.03123/) (2020)
- [3D Steerable CNNs: Learning Rotationally Equivariant Features in Volumetric Data](https://mlsanity.com/paper/1807.02547/) (2018)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Subgraph Neural Networks](https://mlsanity.com/paper/2006.10538/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Learning metrics for persistence-based summaries and applications for graph classification](https://mlsanity.com/paper/1904.12189/) (2019)
- [Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network](https://mlsanity.com/paper/2002.07206/) (2020)
- [edGNN: a Simple and Powerful GNN for Directed Labeled Graphs](https://mlsanity.com/paper/1904.08745/) (2019)
- [Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections](https://mlsanity.com/paper/1304.1548/) (2013)
- [Ring Reservoir Neural Networks for Graphs](https://mlsanity.com/paper/2005.05294/) (2020)

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

- [Graph Neural Networks in Vision-Language Image Understanding: A Survey](https://mlsanity.com/paper/2303.03761/) (2023)
- [Addressing Noise and Stochasticity in Fraud Detection for Service Networks](https://mlsanity.com/paper/2505.00946/) (2025)
- [PromptGCN: Bridging Subgraph Gaps in Lightweight GCNs](https://mlsanity.com/paper/2410.10089/) (2024)
- [Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs](https://mlsanity.com/paper/2412.08835/) (2024)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are recently proposed neural network structures for the processing of graph-structured data. Due to their employed neighbor aggregation strategy, existing GNNs focus on capturing node-level information and neglect high-level information. Existing GNNs therefore suffer from representational limitations caused by the Local Permutation Invariance (LPI) problem. To overcome these limitations and enrich the features captured by GNNs, we propose a novel GNN framework, referred to as the Two-level GNN (TL-GNN). This merges subgraph-level information with node-level information. Moreover, we provide a mathematical analysis of the LPI problem which demonstrates that subgraph-level information is beneficial to overcoming the problems associated with LPI. A subgraph counting method based on the dynamic programming algorithm is also proposed, and this has time complexity is O(n^3), n is the number of nodes of a graph. Experiments show that TL-GNN outperforms existing GNNs and achieves state-of-the-art performance.