# A Simple yet Effective Method for Graph Classification

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 42 references that are in the map.
- First posted on arXiv 6 Jun 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [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)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Anonymous Walk Embeddings](https://mlsanity.com/paper/1805.11921/) (2018)
- [Deep Constraint-based Propagation in Graph Neural Networks](https://mlsanity.com/paper/2005.02392/) (2020)

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

- [Structural Entropy Guided Graph Hierarchical Pooling](https://mlsanity.com/paper/2206.13510/) (2022)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [HiTIN: Hierarchy-aware Tree Isomorphism Network for Hierarchical Text Classification](https://mlsanity.com/paper/2305.15182/) (2023)
- [Hierarchical State Abstraction Based on Structural Information Principles](https://mlsanity.com/paper/2304.12000/) (2023)
- [Graph Out-of-Distribution Generalization with Controllable Data Augmentation](https://mlsanity.com/paper/2308.08344/) (2023)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [SEGA: Structural Entropy Guided Anchor View for Graph Contrastive Learning](https://mlsanity.com/paper/2305.04501/) (2023)
- [NC-NCD: Novel Class Discovery for Node Classification](https://mlsanity.com/paper/2407.17816/) (2024)
- [Rumor Detection on Social Media with Temporal Propagation Structure Optimization](https://mlsanity.com/paper/2412.08316/) (2024)
- [Molecular Graph Contrastive Learning with Line Graph](https://mlsanity.com/paper/2501.08589/) (2025)
- [Structural Entropy Guided Unsupervised Graph Out-Of-Distribution Detection](https://mlsanity.com/paper/2503.03241/) (2025)
- [Structure-Sensitive Graph Dictionary Embedding for Graph Classification](https://mlsanity.com/paper/2306.10505/) (2023)
- [Uncovering Capabilities of Model Pruning in Graph Contrastive Learning](https://mlsanity.com/paper/2410.20356/) (2024)
- [Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression](https://mlsanity.com/paper/2601.08187/) (2026)

## Abstract (arXiv)

In deep neural networks, better results can often be obtained by increasing the complexity of previously developed basic models. However, it is unclear whether there is a way to boost performance by decreasing the complexity of such models. Intuitively, given a problem, a simpler data structure comes with a simpler algorithm. Here, we investigate the feasibility of improving graph classification performance while simplifying the learning process. Inspired by structural entropy on graphs, we transform the data sample from graphs to coding trees, which is a simpler but essential structure for graph data. Furthermore, we propose a novel message passing scheme, termed hierarchical reporting, in which features are transferred from leaf nodes to root nodes by following the hierarchical structure of coding trees. We then present a tree kernel and a convolutional network to implement our scheme for graph classification. With the designed message passing scheme, the tree kernel and convolutional network have a lower runtime complexity of O(n) than Weisfeiler-Lehman subtree kernel and other graph neural networks of at least O(hm). We empirically validate our methods with several graph classification benchmarks and demonstrate that they achieve better performance and lower computational consumption than competing approaches.