# Graph Classification via Network Usable Information: From Representation Evaluation to Structure Selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 14 references that are in the map.
- First posted on arXiv 3 Jul 2026.

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

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time](https://mlsanity.com/paper/1807.07838/) (2018)
- [Automating Botnet Detection with Graph Neural Networks](https://mlsanity.com/paper/2003.06344/) (2020)
- [NetInfoF Framework: Measuring and Exploiting Network Usable Information](https://mlsanity.com/paper/2402.07999/) (2024)
- [A Comparison of Graph Neural Networks for Malware Classification](https://mlsanity.com/paper/2303.12812/) (2023)

## Abstract (arXiv)

We propose NetinfoGC, a framework for graph classification that extends the Network Usable Information (NUI) paradigm to graph-level learning. Unlike conventional graph neural network approaches that rely on end-to-end training of black-box embeddings, NetinfoGC constructs a family of permutation-invariant graph representations derived from propagation-based mechanisms and classical structural descriptors, including graph centrality measures. To evaluate representation quality, we introduce a training-free NUI estimation procedure based on clustering consistency with ground-truth labels, providing a proxy for task-relevant information without supervised learning. We further exploit the same representations using sparse-group LASSO regularization, enabling automatic selection of informative structural descriptors while suppressing redundant ones. Experiments on benchmark datasets show that classical centrality measures are highly competitive with learned propagation-based representations, and in several cases yield superior performance. Moreover, we observe a strong correlation between estimated NUI and downstream classification accuracy, validating NUI as an effective measure of representation utility. Overall, NetinfoGC provides a unified and interpretable framework for evaluating and exploiting graph representations without requiring end-to-end neural training.