# A simple yet effective baseline for non-attributed graph classification

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2018.

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

- [On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs](https://mlsanity.com/paper/2107.01495/) (2021)
- [Self-supervised Graph Neural Networks without explicit negative sampling](https://mlsanity.com/paper/2103.14958/) (2021)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Joint Embedding of Structural and Functional Brain Networks with Graph Neural Networks for Mental Illness Diagnosis](https://mlsanity.com/paper/2107.03220/) (2021)
- [Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels](https://mlsanity.com/paper/2104.02995/) (2021)
- [Meta-Weight Graph Neural Network: Push the Limits Beyond Global Homophily](https://mlsanity.com/paper/2203.10280/) (2022)
- [Motif Graph Neural Network](https://mlsanity.com/paper/2112.14900/) (2021)
- [MOOMIN: Deep Molecular Omics Network for Anti-Cancer Drug Combination Therapy](https://mlsanity.com/paper/2110.15087/) (2021)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [XFL: Naming Functions in Binaries with Extreme Multi-label Learning](https://mlsanity.com/paper/2107.13404/) (2021)
- [A Comparison of Graph Neural Networks for Malware Classification](https://mlsanity.com/paper/2303.12812/) (2023)
- [Application of Graph Neural Networks and graph descriptors for graph classification](https://mlsanity.com/paper/2211.03666/) (2022)
- [SamGoG: A Sampling-Based Graph-of-Graphs Framework for Imbalanced Graph Classification](https://mlsanity.com/paper/2507.13741/) (2025)
- [Capsule Graph Neural Networks with EM Routing](https://mlsanity.com/paper/2110.09039/) (2021)
- [CellTypeGraph: A New Geometric Computer Vision Benchmark](https://mlsanity.com/paper/2205.08166/) (2022)
- [Observe Locally, Classify Globally: Using GNNs to Identify Sparse Matrix Structure](https://mlsanity.com/paper/2309.02442/) (2023)
- [Multi-Attractor GNNs: Set-Valued Expressivity Beyond Unique Equilibria](https://mlsanity.com/paper/2609.35274/) (2026)

## Abstract (arXiv)

Graphs are complex objects that do not lend themselves easily to typical learning tasks. Recently, a range of approaches based on graph kernels or graph neural networks have been developed for graph classification and for representation learning on graphs in general. As the developed methodologies become more sophisticated, it is important to understand which components of the increasingly complex methods are necessary or most effective. As a first step, we develop a simple yet meaningful graph representation, and explore its effectiveness in graph classification. We test our baseline representation for the graph classification task on a range of graph datasets. Interestingly, this simple representation achieves similar performance as the state-of-the-art graph kernels and graph neural networks for non-attributed graph classification. Its performance on classifying attributed graphs is slightly weaker as it does not incorporate attributes. However, given its simplicity and efficiency, we believe that it still serves as an effective baseline for attributed graph classification. Our graph representation is efficient (linear-time) to compute. We also provide a simple connection with the graph neural networks. Note that these observations are only for the task of graph classification while existing methods are often designed for a broader scope including node embedding and link prediction. The results are also likely biased due to the limited amount of benchmark datasets available. Nevertheless, the good performance of our simple baseline calls for the development of new, more comprehensive benchmark datasets so as to better evaluate and analyze different graph learning methods. Furthermore, given the computational efficiency of our graph summary, we believe that it is a good candidate as a baseline method for future graph classification (or even other graph learning) studies.