# Pattern-Based Graph Classification: Comparison of Quality Measures and Importance of Preprocessing

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 109 references that are in the map.
- First posted on arXiv 19 Jun 2025.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Shapley values for feature selection: The good, the bad, and the axioms](https://mlsanity.com/paper/2102.10936/) (2021)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Universal Graph Transformer Self-Attention Networks](https://mlsanity.com/paper/1909.11855/) (2019)
- [DGCNN: Disordered Graph Convolutional Neural Network Based on the Gaussian Mixture Model](https://mlsanity.com/paper/1712.03563/) (2017)
- [Peeling Bipartite Networks for Dense Subgraph Discovery](https://mlsanity.com/paper/1611.02756/) (2016)
- [Active Learning of Discriminative Subgraph Patterns for API Misuse Detection](https://mlsanity.com/paper/2204.09945/) (2022)
- [Contrast Pattern Mining: A Survey](https://mlsanity.com/paper/2209.13556/) (2022)
- [Pattern Mining for Anomaly Detection in Graphs: Application to Fraud in Public Procurement](https://mlsanity.com/paper/2306.10857/) (2023)

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

- [Exact Subgraph Isomorphism Network with Mixed L0,2 Norm Constraint for Predictive Graph Mining](https://mlsanity.com/paper/2509.21699/) (2025)

## Abstract (arXiv)

Graph classification aims to categorize graphs based on their structural and attribute features, with applications in diverse fields such as social network analysis and bioinformatics. Among the methods proposed to solve this task, those relying on patterns (i.e. subgraphs) provide good explainability, as the patterns used for classification can be directly interpreted. To identify meaningful patterns, a standard approach is to use a quality measure, i.e. a function that evaluates the discriminative power of each pattern. However, the literature provides tens of such measures, making it difficult to select the most appropriate for a given application. Only a handful of surveys try to provide some insight by comparing these measures, and none of them specifically focuses on graphs. This typically results in the systematic use of the most widespread measures, without thorough evaluation. To address this issue, we present a comparative analysis of 38 quality measures from the literature. We characterize them theoretically, based on four mathematical properties. We leverage publicly available datasets to constitute a benchmark, and propose a method to elaborate a gold standard ranking of the patterns. We exploit these resources to perform an empirical comparison of the measures, both in terms of pattern ranking and classification performance. Moreover, we propose a clustering-based preprocessing step, which groups patterns appearing in the same graphs to enhance classification performance. Our experimental results demonstrate the effectiveness of this step, reducing the number of patterns to be processed while achieving comparable performance. Additionally, we show that some popular measures widely used in the literature are not associated with the best results.