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

Lucas Potin, Rosa Figueiredo, Vincent Labatut, Christine Largeron

► To cite this version:

Lucas Potin, Rosa Figueiredo, Vincent Labatut, Christine Largeron. Pattern-Based Graph Classification: Comparison of Quality Measures and Importance of Preprocessing. ACM Transactions on Knowledge Discovery from Data (TKDD), 2025, 19 (6), pp.123. 10.1145/3743143. hal-05095757

HAL Id: hal-05095757

https://hal.science/hal-05095757v1

Submitted on 12 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Pattern-Based Graph Classification: Comparison of Quality Measures and Importance of Preprocessing

LUCAS POTIN, Laboratoire Informatique d'Avignon – UPR 4128, F-84911, France

ROSA FIGUEIREDO, Laboratoire Informatique d'Avignon – UPR 4128, F-84911, France

VINCENT LABATUT, Laboratoire Informatique d'Avignon – UPR 4128, F-84911, France

CHRISTINE LARGERON, Laboratoire Hubert Curien – UMR 5516, F-42023, France

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.

CCS Concepts: • **Computing methodologies** → **Supervised learning by classification**: *Network science*; • **Information systems** → *Data mining*.

Additional Key Words and Phrases: Graph Classification, Pattern Mining, Quality Measures, Empirical and Theoretical Comparison

**ACM Reference Format:**

Lucas Potin, Rosa Figueiredo, Vincent Labatut, and Christine Largeron. 2025. Pattern-Based Graph Classification: Comparison of Quality Measures and Importance of Preprocessing. *J. ACM* 37, 4, Article 111 (August 2025), 49 pages. https://doi.org/XXXXXXX.XXXXXXX

# 1 INTRODUCTION

Graph classification is a fundamental task in graph theory and machine learning, aiming at partitioning a graph collection into different categories, based on their structural and attribute features [89]. It finds application in diverse

Authors' addresses: Lucas Potin, lucas.potin@univ-avignon.fr, Laboratoire Informatique d'Avignon - UPR 4128, F-84911, Avignon, France; Rosa Figueiredo, rosa.figueiredo@univ-avignon.fr, Laboratoire Informatique d'Avignon - UPR 4128, F-84911, Avignon, France; Vincent Labatut, vincent.labatut@univ-avignon.fr, Laboratoire Informatique d'Avignon - UPR 4128, F-84911, Avignon, France; Christine Largeron, christine.largeron@univ-st-etienne.fr, Laboratoire Hubert Curien - UMR 5516, F-42023, Saint-Etienne, France.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

© 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Manuscript submitted to ACM
fields such as chemistry [45], API misuse detection [47], and supply chain optimization [97]. There are three main approaches to tackle this task: graph kernels, graph neural networks and subgraph mining.

Graph kernels [54, 55] allow measuring the similarity between all pairs of graphs based on predefined features. The resulting graph kernel matrix can then be used as a representation of the graph collection. Graph kernels have been applied in various domains. For instance, in bioinformatics for classifying chemical compounds and proteins by comparing their molecular structures [49] or in image classification [39]. This type of approach is highly flexible and can be adapted to different types of graphs [55]. In particular, it can handle graphs with varying sizes and structures, as well as attributed graphs.

Graph Neural Networks (GNN) [99, 106] leverage deep learning techniques to automatically learn graph representations. Typically, a GNN first initializes vertex embeddings based on their features. Through iterative message passing, the embedding of each vertex is updated by aggregating information from its neighbors. After several iterations, a readout function aggregates these final vertex embeddings into a single vector that represents the entire graph. The addition of a layer able to take advantage of these representations allows performing the graph classification task. Several algorithms have been proposed following this principle, notably DGCNN [96] and U2GNN [68], applied both to chemical compound and citation network classification.

Subgraph mining [38, 44] identifies specific subgraphs, called patterns, that frequently occur within the considered collection of graphs. Methods using subgraph mining convert the mined subgraphs into features and represent each graph as a binary vector, whose components indicate the presence or absence of these patterns [1]. These vector representations are then used to train a standard classifier. For instance, Potin et al. [73] use a Support Vector Machine to distinguish between fraudulent and lawful public procurement contracts, and Karbalaie et al. [48] use a Random Forest to distinguish malware from benign software.

It is worth stressing that all three approaches rely on specific fixed-size vector representations of the graphs, which are fetched to different types of classifiers. These representations exhibit different levels of interpretability. In this work, we focus on subgraph mining methods, because they provide better explainability than both other approaches. Indeed, patterns can be directly interpreted, providing insights into structural features that differentiate graph classes. However, the choice of the subgraphs selected as features should be made carefully: one wants to focus on patterns that have a high discriminative power with regard to the classification task.

To obtain patterns particularly related to a class, a common strategy is to mine all *frequent* patterns, and keep only the most discriminative [1]. This approach requires using a function, called a *quality measure* [63, 91], to assess how well each pattern distinguishes between classes. As we show later (Section 2), although quality measures have been extensively studied in the context of *tabular* data mining, their assessment in the context of graph pattern mining remains underexplored. Thus, existing surveys [16, 63, 91] provide only partial guidance, as, among other limitations, they primarily focus on patterns based on items, by opposition to subgraphs.

In this paper, we focus on evaluating the effectiveness of quality measures able to assess the discriminative power of subgraphs within the context of pattern-based graph classification. For the sake of concision and clarity, we make two important assumptions. First, we work within the context of *binary* classification. Indeed, many graph classification applications are based on two classes, often interpreted as the presence or absence of a particular characteristic, for instance, in chemistry with the absence or presence of chemical compounds [49], or in economics with the absence or presence of fraud [61, 73]. As a result, the majority of available benchmark datasets for graph classification contain two classes. In addition, most studies that deal with the multi-class situation transform it into a two-class case, using the one-vs-rest approach [33]. This may be due to most quality measures being designed to handle only two
classes [16, 24, 63, 91]. Second, we assume that the classes are balanced, i.e. contain the same number of graphs. This is a common methodological choice in the literature, justified by the fact that it allows a fair comparison of the quality measures, and avoids hiding correlations between equivalent measures [63].

We aim to address three research questions:

RQ1 Is it possible to achieve more compact graph representation without compromising classification performance?

RQ2 Do quality measures behave consistently across graph datasets?

RQ3 Can we identify quality measures that tend to perform better than others?

To answer these questions, we propose a two-step methodology: first, by comparing the way quality measures rank patterns, and second, by assessing how these rankings affect classification performance. This paper makes five main contributions.

(1) We review a comprehensive set of 38 quality measures, and propose a typology based on three mathematical properties from the literature, as well as an additional original one that we introduce to better characterize the measures.

(2) We constitute a benchmark of graph datasets, and propose a method based on the Shapley Value [82] to produce pattern rankings on these datasets that can be used as gold standard for classification evaluation.

(3) We design a preprocessing step relying on cluster analysis to improve the pattern-based representation of graphs, and assess its effect on graph classification and runtime.

(4) We evaluate the effectiveness of the selected measures experimentally, and compare them in terms of classification performance using our benchmark and gold standard.

(5) We release all datasets, code, and experimental results in an open-source repository<fnref n="1" /> to support reproducibility and further research.

The rest of the paper is organized as follows. Section 2 provides an overview of existing studies on quality measures in pattern mining, highlighting their current relevance, but also the limitations of these studies, particularly regarding graph data. Section 3 defines the problem, terminology and notations used throughout this article. Section 4 lists the quality measures considered in our experiments, and discusses their properties. Section 5 describes our methods and framework. In Section 6, we present our experimental protocol and discuss our results. Finally, we summarize our main findings in Section 7, and propose some perspectives.

## 2 RELATED WORK

*Relevance of Quality Measures.* Quality measures play a fundamental role in pattern mining, and this is especially true for graph pattern mining. In this context, they have been widely adopted for various tasks, such as graph classification, subgraph selection, and explainability. For instance, Kang and Lo [47] use the $\chi^2$ statistic [12] to identify discriminative subgraphs for API misuse detection, while Alam et al. [5] employ Information Gain [18] to select subgraphs that maximize the reduction of entropy, enhancing supervised graph embeddings.

Beyond subgraph selection, quality measures also play an essential role in graph mining algorithms. He et al. [41] introduce All-Confidence as an alternative to Lift [72] for mining credible attribute rules in dynamic attributed graphs. They argue that Lift is unreliable due to its lack of anti-monotonicity, which makes it less suitable for hierarchical rule evaluation. Similarly, Chowdhury et al. [17] analyze correlation in frequent subgraph mining, highlighting the limitations of the Confidence metric [3] in this context.

<footnote n="1">¹https://github.com/CompNet/gpQualMeasComp</footnote>
In the field of GNNs, quality measures contribute both to performance enhancement and explainability. For instance, Kikaj et al. [51] improve message-passing neural networks by selecting informative subgraphs using $\chi^2$ and Mutual Information [27]. Meanwhile, Veyrin-Forrer et al. [92] focus on GNN explainability, identifying characteristic subgraphs through a modified version of WRACC [58] within the gSpan framework, improving model interpretability.

But the impact of quality measures extends beyond graph pattern mining. Over the past five years, articles citing at least one of the quality measures assessed in this study have accumulated more than 15,000 citations per year according to GoogleScholar. These articles cover a wide range of applications, including analyzing cab customer behavior [32], predicting grocery stocking needs [10] or discovering play patterns in video games [66]. This widespread impact highlights the central role of quality measures in various domains. But whatever the context, a recurrent methodological challenge persists: selecting the most appropriate quality measure for the application at hand. This choice can only be made based on a thorough comparison between the many existing measures.

*Tabular Quality Measure Surveys.* A handful of studies have investigated quality measures but specifically in the field of tabular (or item-based) pattern mining [16, 24, 63, 91]. Among them, Chen et al. [16] cite 13 different measures, while Dong and Bailey [24] list 10. Both surveys essentially provide a description without pushing their analysis deeper, though. Ventura and Luna [91] go further by evaluating three mathematical properties for nine selected measures. Additionally, they analyze the relationships between each pair of measures, providing a structured comparison that highlights their dependencies and redundancies. Loyola-González et al. [63] take the most experimental approach when studying 33 different measures. Their work includes a correlation analysis between pairs of metrics with the goal of forming clusters of similar measures, providing insights into which measures capture redundant or complementary aspects of pattern quality.

Although two of these surveys [16, 91] briefly touch upon the topic of *graph* pattern mining, their focus remains limited to *contrast* subgraphs [87]. This concept refers to a subgraph that appears *only* in one class, and *never* in another. This makes it a distinguishing feature that helps to differentiate between classes. The main advantage of these subgraphs is their ability to provide clear and interpretable features that highlight the differences between classes. However, their very strict definition (exclusive presence in a single class) can sometimes result in overlooking more subtle and potentially useful patterns that show a strong but not absolute association with one class. Most quality measures are able to handle non-contrast subgraphs, so by focusing only on this specific type of graph patterns, these two articles provide a very incomplete comparison regarding graph pattern mining.

Because of the lack of dedicated studies, the selection of a quality measure for graph mining remains largely *ad hoc*. Researchers often adopt measures based on convention rather than a principled evaluation of their effectiveness for specific tasks. This issue is compounded by the fact that existing surveys provide only partial guidance on the choice of the most appropriate quality measure.

*Limitations of Existing Work.* First, existing surveys remain incomplete in their coverage of quality measures. Although Loyola-González et al. [63] present the widest range of quality measures among existing empirical studies, their analysis omits several essential measures, particularly those used in feature selection and classification, such as *FPR* [32] or *AbsSupDif* [86]. Another limitation of these surveys is that they do not cover more recent measures coming from the feature selection literature [11, 22, 84], which can also be used to assess the quality of patterns. Measures such as the *Gini Index*, *Entropy*, and *Fisher Score*, rely on statistical techniques that follow the same principle as quality measures: each pattern is assigned a score that indicates its discriminative power. In our work, we extend this scope by incorporating such feature selection measures into our evaluation, ensuring a more complete benchmark.
Second, there is a divide between theoretical and empirical approaches in existing surveys. Some studies provide a formal theoretical analysis based on mathematical properties of quality measures but lack empirical validation [24, 91]. Conversely, the most comprehensive study [63] proposes an empirical comparison but lacks a theoretical foundation to select the quality measure and discuss the experimental results. Without theoretical guarantees, the results are highly sensitive to dataset biases, limiting their generalizability. To address this issue, our study adopts a dual approach that combines theoretical and empirical evaluation. We use four fundamental mathematical properties to characterize the 38 quality measures considered in this article, while simultaneously validating their effectiveness on eight datasets from diverse domains of application.

Third, current evaluations lack a proper comparison against a ground truth. While Loyola-González et al. [63] propose an experimental setup to assess quality measures, their approach is based on a classification method that is a deliberate oversimplification compared to standard approaches. Specifically, this method assigns a class to each instance by applying a voting mechanism among the highest-scoring patterns. This strategy creates a strong dependency on individual patterns, which is likely to limit the overall classification performance, possibly making measure comparison less reliable. To overcome this limitation, we construct a gold standard based on the Shapley Value [82] to assess the quality measures, reducing the dependency on the classifier.

Finally, in addition to these limitations, an even more fundamental issue remains: existing studies do not specifically address the challenges posed by *graphs*, and this leads to several limitations. First, these experiments leverage some pattern mining algorithms that directly mine patterns closely linked to a specific class [34]. These methods are specific to *tabular* data; there is no counterpart able to handle *graphs*. Second, dealing with *tabular* data means ignoring certain types of patterns specific to *graphs*, such as *induced subgraphs* [46]. In this work, we adopt an approach that is exclusively focused on graph data, which allows us to consider the effect of mining induced graph patterns.

## 3 DEFINITIONS AND NOTATIONS

Our work relies on the most general definition of an attributed graph, i.e. with attributes on vertices as well as on edges.

*Definition 3.1 (Attributed Graph)*. An attributed graph is defined as a tuple $G = (V, E, X, Y)$ in which $V$ is the set of $n$ vertices, $E$ the set of $m$ edges of $G$, $X$ the $n \times d_V$ matrix whose row $x_i$ is the $d_V$-dimensional attribute vector associated with vertex $v_i \in V$, and $Y$ the $m \times d_E$ matrix whose row $y_i$ is the $d_E$-dimensional attribute vector associated with edge $e_i \in E$.

A non-attributed graph can be considered as a specific case of attributed graph, in which a single attribute is used to describe the vertices as well as the edges, with only one possible value, for example a weight equal to one on all edges. Consequently, the concepts and methods described in the following also apply to non-attributed graphs.

Let us consider a set $\mathcal{G} = \{G_1, ..., G_N\}$ of attributed graphs. Let us assume that each graph $G_i$ ($1 \le i \le N$) is associated with a label noted $t_i$ and defined in $\mathcal{L} = \{+, -\}$. The set $\mathcal{G}$ can therefore be split into two disjoint subsets, or classes: $\mathcal{G} = G^+ \cup G^- (G^+ \cap G^- = \emptyset)$, where $G^+$ is the subset of graphs in the positive class and $G^-$ is the subset of graphs in the negative class.

In this paper, we consider the problem that consists in classifying a graph from $\mathcal{G}$ as either positive or negative, based on its structure and attributes. We specifically focus on the case where these classes are balanced, i.e. $|\mathcal{G}^+| = |\mathcal{G}^-|$.

More particularly, we are interested in methods that rely on subgraphs to represent a graph and determine its class. These subgraphs, called *patterns*, are defined as follows:
**Definition 3.2 (Pattern).** Let $G = (V, E, X, Y)$ be an attributed graph. A graph $P$ is a pattern of $G$ if it is isomorphic to a subgraph $H$ of $G$, i.e. $\exists H \subseteq G : P \cong H$.

We consider that $P$ is a pattern of a set of graphs $\mathcal{G}$ when $P$ is a pattern of at least one of its graphs. In order to mine the frequent patterns of a set of graphs, several algorithms have been proposed such as gSpan [100], FFSM [43], or more recently TKG [29]. We do not go into detail about these algorithms, as they are outside the scope of this paper. For more information, we refer the interested reader to the survey of Güvenoglu and Bostanoglu [38].

Applying one of these algorithms results in a set of patterns of $\mathcal{G}$, noted $\mathcal{P}$. Graphs can then be described in terms of whether or not they contain these patterns. However, not every pattern holds the same level of relevance to the classification task. In particular, some patterns are evenly distributed over $\mathcal{G}^+$ and $\mathcal{G}^-$, and therefore provide no information allowing to discriminate between the classes.

To discriminate between the patterns they detect in the dataset, these algorithms typically leverage the notion of *graph support*.

**Definition 3.3 (Graph support).** The graph support of a pattern $P$ in a set $\mathcal{G}$, noted support($P, \mathcal{G}$), is the number of graphs in $\mathcal{G}$ that contain $P$ as a pattern: $\text{support}(P, \mathcal{G}) = |\{G \in \mathcal{G} : \exists H \subseteq G \text{ s.t. } P \cong H\}|$.

This support ranges from 0 to $|\mathcal{G}|$, as it simply indicates the presence or absence of a pattern in a graph, without considering how many times it appears in the graph. It is worth stressing that the notion of support is ambiguously defined in the Pattern Mining literature: it is sometimes the number of items containing the pattern [2], and sometimes the proportion of such items [62]. In the specific case of *graph* pattern mining, the former version appears to be the most consensual [29, 100], thus we use it in this paper.

In order to select only the most interesting patterns, a common method [37] consists in ranking them using a so-called *quality measure*.

**Definition 3.4 (Quality Measure).** Let $\mathcal{P}$ be the set of patterns occurring in a collection of graphs $\mathcal{G}$. A quality measure $q(P, \mathcal{G}^+, \mathcal{G}^-)$ associates a numeric value to each pattern $P \in \mathcal{P}$, indicating its power to discriminate between classes $\mathcal{G}^+$ and $\mathcal{G}^-$.

In this article, we use the notation adopted by Loyola-González et al. [62] to define a quality measure as a function of the considered pattern $P$ as well as both classes $\mathcal{G}^+$ and $\mathcal{G}^-$. In general, a high quality measure for a pattern indicates that it has a strong discriminative power. There exist many quality measures, which we review in Section 4. The main goal of this paper is to compare them.

Whatever the selected measure, it is possible to rank the patterns of $\mathcal{P}$ in order to obtain an ordered set noted $\mathcal{P}_r$.

From set $\mathcal{P}_r$, the $s$ most discriminative patterns ($s \le |\mathcal{P}|$) are selected to define $\mathcal{P}_s$, the subset of patterns used to represent each graph. It is necessary to choose $s$ carefully, in order to retain the patterns that are necessary and useful for the classification.

Although it is possible to directly use $\mathcal{P}_r$ (i.e. all available patterns) to represent the graphs, there are two major advantages with using a restricted subset. First, using fewer patterns reduces computation time. Second, previous work [102] has shown that reducing the size of the feature set used for classification may increase final performance. In order to select $\mathcal{P}_s$, it is therefore necessary to have an efficient way of distinguishing its patterns, using an adapted quality measure.

All the patterns in $\mathcal{P}_s$ are then used to build a matrix $\mathbf{H} \in \mathbb{R}^{|\mathcal{G}| \times s}$, where each row $\mathbf{h}_i$ is the vector-based representation of graph $G_i$ using the patterns in $\mathcal{P}_s$.
There are several possible approaches to create this representation. In this work, we focus on the most common one [1], which is called *binary representation*. According to this approach, for each graph $G_i \in \mathcal{G}$ and each pattern $P_j \in \mathcal{P}_s$, $h_{ij} = 1$ if this pattern $P_j$ is present in $G_i$ and $h_{ij} = 0$ otherwise. This vector representation can be used as input by common classifiers [15] to predict the class of each graph.

Matrix $H$ can also be viewed as a concatenation of columns instead of rows. Each column $h_{ij}$ represents a pattern $P_j$, as each value $h_{ij}$ indicates whether $P_j$ is present or absent from graph $G_i$. We call such vector the *footprint* of the pattern in $\mathcal{G}$.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Processing steps of a standard pattern-based graph classification framework.</figcaption></figure>

Figure 1 summarizes each step of the classification process described in this section. Function $f$ denotes the model obtained by training the classifier.

In this work, we compare quality measures to determine the best one for selecting the most discriminative set $\mathcal{P}_s$ from $\mathcal{P}$, as their performance is known to vary with both the task and the data [63]. The following section provides an overview of the different quality measures considered in the rest of this article.

# 4 QUALITY MEASURES

In this section, we first describe the measures selected to conduct our experiments (Section 4.1), before discussing some of their properties (Section 4.2).

## 4.1 Definitions

As mentioned in the introduction, the literature contains several papers that survey and compare quality measures designed for pattern-based classification [16, 24, 63, 91]. Similarly, in feature selection, several works have explored ranking methods for identifying discriminative features [11, 22, 84]. As is often the case, some measures appear in several reviews, such as GR in [16, 24, 63], and some measures appear under different names, like BRINS [63] & CONV [91], or CONF [63] & TPR [16]. After resolving these differences, we identify a total of 41 distinct measures among these seven surveys. It is worth stressing that all these measures were originally defined to characterize *general* patterns, identified in *tabular* (or item-based) data. However, their application to collections of graphs is straightforward for all but one, discussed below, by using the notion of graph support defined in Section 3 instead of the standard support [24].

Out of these 41 measures, we exclude three, which leaves us with 38 for our experiments. For the sake of comprehensiveness, the definition of the three discarded measures is provided in Appendix A.1. First, we discard GENQUOTIENT [16], because it requires the user to set a specific parameter. Moreover, using standard parameter values makes GENQUOTIENT
equivalent to other measures already present in our selection, such as WRACC. The second discarded measure is SUPMAXK [16], because it cannot handle graphs. Indeed, it requires considering each pattern as a set of separate items. Graph patterns can be seen as sets of vertices and edges, but the adaptation is not trivial. Third and finally, we exclude PVALUE [16], because its computation is unsuitable to large datasets. Moreover, it should be noted that, unlike all the other measures, FPR, GINI, and ENTROPY assign lower values to stronger discriminative power [16, 84]: we therefore reverse their rankings for the sake of consistency.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Simplified representation of a collection $\mathcal{G}$ constituted of six graphs, distributed over two classes $\mathcal{G}^+$ and $\mathcal{G}^-$, and described according to four patterns.</figcaption></figure>

Figure 2 provides a visual representation of an example used throughout this section to illustrate the concepts and quality measures described here. It shows a set of six graphs $\mathcal{G} = \{G_1, ..., G_6\}$, split in two classes $\mathcal{G}^+ = \{G_1, ..., G_3\}$ and $\mathcal{G}^- = \{G_4, ..., G_6\}$. This collection contains four distinct patterns $\mathcal{P} = \{P_1, ..., P_4\}$, symbolized by squares. The graphs are only represented in terms of which patterns they contain (solid squares) or not (empty squares). For example, $G_4$ contains only $P_2$ and $P_4$. In this example, $\text{support}(P_1, \mathcal{G}^+) = 3$, since $P_1$ is present in $G_1$, $G_2$, and $G_3$.

In the context of this paper, graph support can be tied to certain concepts from the classification field. Let us assume that, for a certain pattern $P$, graphs possessing $P$ tend to belong to class $\mathcal{G}^+$, whereas graphs not possessing $P$ tend to belong to class $\mathcal{G}^-$. According to the terminology of the Classification domain, such graphs possessing $P$ and belonging to $\mathcal{G}^+$ are called *True Positives* (TP) and those not possessing $P$ and belonging to $\mathcal{G}^-$ are called *False Negatives* (TN). On the contrary, a graph possessing $P$ but belonging to $\mathcal{G}^-$ is a *False Positive* (FP), and a graph not possessing $P$ but belonging to $\mathcal{G}^+$ is a *False Negative* (FN). Notation $\bar{P}$ expresses the absence of pattern $P$, therefore the following support values can be used to count these cases: $\text{support}(P, \mathcal{G}^+) \text{ (TP)}$, $\text{support}(\bar{P}, \mathcal{G}^-) \text{ (TN)}$, $\text{support}(P, \mathcal{G}^-) \text{ (FP)}$, and $\text{support}(\bar{P}, \mathcal{G}^+) \text{ (FN)}$.

The concept of graph support allows us to derive several probabilities that constitute the building blocks of the quality measures. For convenience, they are all gathered in Table 1. They can be interpreted as follows. Probability $p(P)$ is the proportion of graphs in $\mathcal{G}$ that contain $P$ at least once, i.e. the probability of drawing a graph containing $P$ in $\mathcal{G}$. It is simply a normalization of the support: in our example, we have $p(P_1) = 3/6$. Probability $p(\mathcal{G}^+)$ is the proportion of graphs in $\mathcal{G}$ that belong to the positive class, i.e. the probability of drawing a graph with label + in $\mathcal{G}$. As explained in Section 3, in the context of this paper, the classes are assumed balanced. Therefore, $p(\mathcal{G}^+) = p(\mathcal{G}^-) = 0.5$. Probability $p(P, \mathcal{G}^+)$ is the proportion of graphs in $\mathcal{G}$ which simultaneously belong to the positive class and contain pattern $P$. In our example, we have $p(P_4, \mathcal{G}^+) = 2/6$. Probability $p(\mathcal{G}^+ | P)$ is the proportion of positive graphs among the set of graphs containing pattern $P$. It can be seen as the ratio of the support of $P$ in $\mathcal{G}^+$ to the support of $P$ in $\mathcal{G}$. In our example, $p(\mathcal{G}^+ | P_4) = 2/5$. Probability $p(P | \mathcal{G}^+)$ is the proportion of graphs containing pattern $P$ among the set of positive graphs. Note that, because our classes are balanced, $|\mathcal{G}^+| = |\mathcal{G}|/2$, and thus $p(P | \mathcal{G}^+) = 2p(P, \mathcal{G}^+)$. In our example, $p(P_4 | \mathcal{G}^+) = 2/3$. Probability $p(\bar{P}, \mathcal{G}^+)$ is the proportion of graphs in $\mathcal{G}$ that simultaneously belong to the positive class and do not contain $P$. In our example, $p(\bar{P}_4, \mathcal{G}^+) = 1/6$, since only graph $G_2$ is in the positive class while not containing $P_4$. All these interpretations are also valid for $\mathcal{G}^-$, this time considering graphs of the negative class.
<table><caption>Table 1. Probabilities used to define the quality measures defined in Tables 2 and 3.</caption><thead><tr><th>Probability</th><th>Formula</th><th>Probability</th><th>Formula</th></tr></thead><tbody><tr><td>p(P)</td><td><div style="text-align: center;">support(P, G)</div><div style="text-align: center;">|G|</div></td><td>p(P̄)</td><td>1 - p(P)</td></tr><tr><td>p(G<sup>+</sup>)</td><td><div style="text-align: center;">|G<sup>+</sup>|</div><div style="text-align: center;">|G|</div></td><td>p(G<sup>-</sup>)</td><td>1 - p(G<sup>+</sup>)</td></tr><tr><td>p(P, G<sup>+</sup>)</td><td><div style="text-align: center;">support(P, G<sup>+</sup>)</div><div style="text-align: center;">|G|</div></td><td>p(P, G<sup>-</sup>)</td><td><div style="text-align: center;">support(P, G<sup>-</sup>)</div><div style="text-align: center;">|G|</div></td></tr><tr><td>p(P̄, G<sup>+</sup>)</td><td><div style="text-align: center;">|G<sup>+</sup>| - support(P, G<sup>+</sup>)</div><div style="text-align: center;">|G|</div></td><td>p(P̄, G<sup>-</sup>)</td><td><div style="text-align: center;">|G<sup>-</sup>| - support(P, G<sup>-</sup>)</div><div style="text-align: center;">|G|</div></td></tr><tr><td>p(G<sup>+</sup> | P)</td><td><div style="text-align: center;">support(P, G<sup>+</sup>)</div><div style="text-align: center;">support(P, G)</div></td><td>p(G<sup>+</sup> | P̄)</td><td><div style="text-align: center;">|G<sup>+</sup>| - support(P, G<sup>+</sup>)</div><div style="text-align: center;">|G| - support(P, G)</div></td></tr><tr><td>p(G<sup>-</sup> | P)</td><td><div style="text-align: center;">support(P, G<sup>-</sup>)</div><div style="text-align: center;">support(P, G)</div></td><td>p(G<sup>-</sup> | P̄)</td><td><div style="text-align: center;">|G<sup>-</sup>| - support(P, G<sup>-</sup>)</div><div style="text-align: center;">|G| - support(P, G)</div></td></tr><tr><td>p(P | G<sup>+</sup>)</td><td><div style="text-align: center;">support(P, G<sup>+</sup>)</div><div style="text-align: center;">|G<sup>+</sup>|</div></td><td>p(P | G<sup>-</sup>)</td><td><div style="text-align: center;">support(P, G<sup>-</sup>)</div><div style="text-align: center;">|G<sup>-</sup>|</div></td></tr><tr><td>p(P̄ | G<sup>+</sup>)</td><td><div style="text-align: center;">|G<sup>+</sup>| - support(P, G<sup>+</sup>)</div><div style="text-align: center;">|G<sup>+</sup>|</div></td><td>p(P̄ | G<sup>-</sup>)</td><td><div style="text-align: center;">|G<sup>-</sup>| - support(P, G<sup>-</sup>)</div><div style="text-align: center;">|G|</div></td></tr></tbody></table>

Tables 2 and 3 describe the 38 measures selected for this work. In order to ease the comparison, the formulas are all expressed using the concepts introduced before: graph support, and probabilities from Table 1. For each measure, column *Bounds* shows its lower and upper bounds, and column *Ref.* indicates the paper that originally introduced it. The four remaining columns state whether the measure possesses certain traits, which are discussed later.

Some of these measures take into account the total number of graphs, denoted $|G|$, in their formula. This is notably the case for PEARSON and $\chi^2$. Moreover, some measures are defined in relation to other measures: STRENGTH and COLSTR use GR and ACC respectively.

Most measures have fixed bounds: [0; 1] (14 measures), [-1; 1] (8), [0; 0.5] (2), [0; 2] (LIFT), [-0.25; 0.25] (LEVER), [-0.5; 0.5] (CCCONF). A few have a fixed lower bound, but do not have any upper bound, i.e. [0; +∞[ (7) or [-10; +∞[ (COLSTR). A few have a fixed upper bound, but do not have any lower bound, i.e. ] - ∞; 0] (INFGAIN) or ] - ∞; 1] (EXCEX). Only one has no bound at all, i.e. ] - ∞; +∞[ (MDISC). These differences have no effect on the experimental comparison that we perform later, as we consider how the measures *rank* the patterns, by opposition to comparing directly the scores obtained with these measures.

## 4.2 Properties

In their survey, Loyola-González et al. [63] propose a classification of quality measures into two categories:

* Those based on the notion of *Independence*. A pattern *P* is considered independent of the classes if $p(P, G^+) = p(P)p(G^+)$. The patterns considered as discriminative will then be those that deviate from such independence.

* Those based on the notion of *Equilibrium*. A pattern *P* is considered in equilibrium over the classes if $p(G^+ | P) = p(G^- | P)$. The patterns considered as discriminative will then be those that deviate from such equilibrium.
<table><caption>Table 2. Name and formula of the first 19 quality measures considered in this article, out of 38 in total. The 19 remaining measures are listed in Table 3. The four rightmost columns indicate the measure properties as discussed in the main text: Contrastivity (Co.), Jumpiness (Ju.), Class Symmetry (Cs.) and Pattern Symmetry (Ps.).</caption><thead><tr><th>Measure</th><th>Definition</th><th>Bounds</th><th>Ref.</th><th>Co.</th><th>Ju.</th><th>Cs.</th><th>Ps.</th></tr></thead><tbody><tr><td>ABSUPDIF</td><td>|p(P | G<sup>+</sup>) - p(P | G<sup>-</sup>)|</td><td>[0, 1]</td><td>[86]</td><td>-</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>ACC</td><td>p(P, G<sup>+</sup>) + p(P, G<sup>-</sup>)</td><td>[0, 1]</td><td>[53]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>BRINS</td><td>p(P)p(G<sup>-</sup>) / p(P, G<sup>-</sup>)</td><td>[0, +∞[</td><td>[14]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>CCONF</td><td>p(G<sup>+</sup> | P) - p(G<sup>+</sup>)</td><td>[-0.5, 0.5]</td><td>[59]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>CFACTOR</td><td>(p(P, G<sup>+</sup>)/p(P)) - p(G<sup>+</sup>) / (1 - p(G<sup>+</sup>))</td><td>[-1, 1]</td><td>[91]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>COLE</td><td>p(G<sup>+</sup> | P) - p(G<sup>+</sup>) / (1 - p(G<sup>+</sup>))</td><td>[-1, 1]</td><td>[8]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>COLSTR</td><td>(p(P, G<sup>+</sup>) + p(P, G<sup>-</sup>)) / (p(P)p(G<sup>+</sup>) + p(P)p(G<sup>-</sup>)) / (1 - p(P, G<sup>+</sup>) - p(G<sup>-</sup> | P))</td><td>-10, +∞[</td><td>[83]</td><td>-</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>CONF</td><td>p(G<sup>+</sup> | P)</td><td>[0, 1]</td><td>[3]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>COS</td><td>√p(G<sup>+</sup> | P)p(P | G<sup>+</sup>)</td><td>[0, 1]</td><td>[83]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>COVER</td><td>p(P | G<sup>+</sup>)</td><td>[0, 1]</td><td>[9]</td><td>-</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>DEP</td><td>|p(G<sup>-</sup>) - p(G<sup>-</sup> | P)|</td><td>[0, 0.5]</td><td>[53]</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>ENTROPY</td><td>-p(G<sup>+</sup> | P) log p(G<sup>+</sup> | P) - p(G<sup>-</sup> | P) log p(G<sup>-</sup> | P)</td><td>[0, 1]</td><td>[81]</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>EXCEX</td><td>1 - (p(G<sup>-</sup> | P)) / (p(G<sup>+</sup> | P))</td><td>-∞, 1]</td><td>[36]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>FISHER</td><td>(p(G<sup>+</sup> | P) - p(G<sup>-</sup> | P))<sup>2</sup> / (p(G<sup>+</sup> | P)(1 - p(G<sup>+</sup> | P)) + p(G<sup>-</sup> | P)(1 - p(G<sup>-</sup> | P)))</td><td>[0, +∞[</td><td>[28]</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>FPR</td><td>p(G<sup>+</sup> | P)</td><td>[0, 1]</td><td>[32]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>GAIN</td><td>p(P, G<sup>+</sup>)(log p(G<sup>+</sup> | P) - log p(G<sup>+</sup>))</td><td>[-1, 1]</td><td>[103]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>GINI</td><td>1 - p(G<sup>+</sup> | P)<sup>2</sup> - p(G<sup>-</sup> | P)<sup>2</sup></td><td>[0, 0.5]</td><td>[13]</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>GR</td><td>p(P | G<sup>+</sup>) / p(P | G<sup>-</sup>)</td><td>[0, +∞[</td><td>[25]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>INFGAIN</td><td>-log p(G<sup>+</sup>) + log p(G<sup>+</sup> | P)</td><td>-∞, 0]</td><td>[18]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

Under the assumption of balanced classes, however, the notions of *Independence* and *Equilibrium* are equivalent (cf. Appendix A.2), and this distinction is therefore irrelevant. Ventura and Luna [91] surveys seven other alternative mathematical properties proposed in the literature. However, they are designed in the context of association rule mining [104]. As a consequence, some of them are irrelevant, or do not apply to subgraph pattern mining. We describe all these properties and discuss them in Appendix A.3. Our analysis reveals that three of these properties (*Contrastivity*, *Class Symmetry* and *Pattern Symmetry*) are suitable to our case. In addition, we define another property (*Jumpiness*) in order to fully describe the quality measures. In the end, we propose to characterize each measure using these four
<table><caption>Table 3. Name and formula of the last 19 quality measures considered in this article, out of 38 in total. The 19 other measures are listed in Table 2.</caption><thead><tr><th>Measure</th><th>Definition</th><th>Bounds</th><th>Ref.</th><th>Co.</th><th>Ju.</th><th>Cs.</th><th>Ps.</th></tr></thead><tbody><tr><td>JACC</td><td>p(P, G<sup>+</sup>) / (p(P) + p(G<sup>+</sup>) - p(P, G<sup>+</sup>))</td><td>[0, 1]</td><td>[83]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>KLOS</td><td>√p(P, G<sup>+</sup>)(p(G<sup>+</sup> | P) - p(G<sup>+</sup>))</td><td>[0,1]</td><td>[52]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>LAP</td><td>(p(P, G<sup>+</sup>) + 1/|G|) / (p(P) + 2/|G|)</td><td>[0, 1]</td><td>[40]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>LEVER</td><td>p(P, G<sup>+</sup>) - p(P)p(G<sup>+</sup>)</td><td>[-0.25, 0.25]</td><td>[94]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>LIFT</td><td>(p(P, G<sup>+</sup>) / p(P)p(G<sup>+</sup>))</td><td>[0, 2]</td><td>[72]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>MDISC</td><td>log(p(P, G<sup>+</sup>)p(P, G<sup>-</sup>) / (p(P, G<sup>-</sup>)p(P, G<sup>+</sup>)))</td><td>-∞, +∞[</td><td>[7]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>MUTINF</td><td>Σ<sub>P<sub>i</sub>∈{P, P&#773;}</sub> Σ<sub>G<sub>i</sub>∈{G<sup>+</sup>, G<sup>-</sup>}</sub> p(P<sub>i</sub>, G<sub>i</sub>) log p(P<sub>i</sub>, G<sub>i</sub>) / (p(P<sub>i</sub>)p(G<sub>i</sub>))</td><td>[0, 1]</td><td>[27]</td><td>-</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>NETCONF</td><td>(p(G<sup>+</sup> | P) - p(G<sup>+</sup>)) / (1 - p(P))</td><td>[-1, 1]</td><td>[4]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>ODDSR</td><td>(p(P, G<sup>+</sup>)/(1 - p(P, G<sup>+</sup>))) / (p(P, G<sup>-</sup>)/(1 - p(P, G<sup>-</sup>)))</td><td>[0, +∞[</td><td>[83]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>PEARSON</td><td>(p(P, G<sup>+</sup>) - p(P)p(G<sup>+</sup>)) / √Np(P)p(G<sup>+</sup>)p(P&#773;)p(G<sup>-</sup>)</td><td>[-1, 1]</td><td>[70]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>RELRISK</td><td>(p(G<sup>+</sup> | P)) / (p(G<sup>+</sup> | P&#773;))</td><td>[0, +∞[</td><td>[6]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>SEBAG</td><td>(p(P, G<sup>+</sup>) / p(P, G<sup>-</sup>))</td><td>[0, +∞[</td><td>[80]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>SPEC</td><td>p(G<sup>-</sup> | P&#773;)</td><td>[0, 1]</td><td>[57]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>STRENGTH</td><td>GR(P, G<sup>+</sup>, G<sup>-</sup>) / (GR(P, G<sup>+</sup>, G<sup>-</sup>) + 1)p(P, G<sup>+</sup>)</td><td>[0, 1]</td><td>[32, 75]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>SUP</td><td>p(P, G<sup>+</sup>)</td><td>[0, 1]</td><td>[3]</td><td>-</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>SUPDIF</td><td>p(P | G<sup>+</sup>) - p(P | G<sup>-</sup>)</td><td>[-1, 1]</td><td>[63]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>WRACC</td><td>p(P)(p(G<sup>+</sup> | P) - p(G<sup>+</sup>))</td><td>[-1, 1]</td><td>[32, 58]</td><td>✓</td><td>✓</td><td>-</td><td>-</td></tr><tr><td>ZHANG</td><td>(p(P, G<sup>+</sup>) - p(P)p(G<sup>+</sup>)) / max{p(P, G<sup>+</sup>)p(G<sup>-</sup>), p(G<sup>+</sup>)p(P, G<sup>-</sup>)}</td><td>[-1, 1]</td><td>[105]</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>χ<sup>2</sup></td><td>N((p(P, G<sup>+</sup>)p(P&#773;, G<sup>-</sup>) - p(P, G<sup>-</sup>)p(P&#773;, G<sup>+</sup>)))<sup>2</sup> / (p(P)p(G<sup>+</sup>)p(P&#773;, G<sup>-</sup>))</td><td>[0, +∞[</td><td>[12]</td><td>-</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

properties, which we present below. The last four columns in Tables 2 and 3 indicate whether a measure possesses these properties (✓) or not (-).

*Contrastivity.* The concept of contrast has several slightly different meanings in the field of pattern mining [16, 24]. In the specific context of graph pattern mining, *contrast patterns* are subgraphs that belong specifically to the positive
class, and do not appear at all in the negative class [16, 24, 42]. Based on this notion designed to characterize patterns, we derive the property of *Contrastivity*, which aims at describing quality measures. Our idea is to distinguish between measures that assess the discriminative power of patterns depending only on their abundance in the positive class, and measures that also consider their scarcity in the negative class. Formally, this translates as follows:

**Definition 4.1 (Contrastivity).** A quality measure $q$ respects the *Contrastivity* property iff

$$ \forall P_i, P_j, [p(P_i, \mathcal{G}^+) = p(P_j, \mathcal{G}^+) \land p(P_i, \mathcal{G}^-) < p(P_j, \mathcal{G}^-)] \Rightarrow [q(P_i, \mathcal{G}^+, \mathcal{G}^-) > q(P_j, \mathcal{G}^+, \mathcal{G}^-)]. $$

This property is equivalent to PS3, the third property of Piatetsky-Shapiro [71], which we describe in Appendix A.3.1. As shown in Table 1, all the probabilities in the left term of Definition 4.1 rely on the same denominator, therefore this term can be simplified, and expressed using only support: $[\text{support}(P_i, \mathcal{G}^+) = \text{support}(P_j, \mathcal{G}^+) \land \text{support}(P_i, \mathcal{G}^-) < \text{support}(P_j, \mathcal{G}^-)]$. More intuitively, when two patterns have the same support in $\mathcal{G}^+$, a contrastive quality measure will favor the one possessing the smallest support in $\mathcal{G}^-$. In other words, measures that possess the *Contrastivity* property take into account *False Positives* as defined in Section 4.1.

Consider, for example, measure *COVER*, defined as $p(P | \mathcal{G}^+)$. By construction, if two patterns such as $P_1$ and $P_2$ in Figure 2 have the same support in $\mathcal{G}^+$ (here: 3), they have the same *COVER* score (here: 1), independently of their support in $\mathcal{G}^-$ (here: 0 and 2, respectively). Therefore, this measure does not possess the property of *Contrastivity*. Let us now consider measure *GR*, defined as $p(P | \mathcal{G}^+)/p(P | \mathcal{G}^-)$. If both patterns have the same support in $\mathcal{G}^+$, then their numerators are equal, and the pattern with the largest support in $\mathcal{G}^-$ gets the smaller ratio. Thus, *GR* respects the *Contrastivity* property.

It is worth stressing that this property treats both classes differently, and is not necessarily desirable, depending on the considered application. It is particularly the case if one gives as much importance to $\mathcal{G}^-$ as to $\mathcal{G}^+$. Assume that two patterns $P_i$ and $P_j$ are scarce in $\mathcal{G}^+$, but with the same support, and that they are common in $\mathcal{G}^-$, with different supports. Then, if the support of $P_i$ in $\mathcal{G}^-$ is higher than that of $P_j$, a contrastive quality measure will output a lower score for this pattern, when it is in fact more relevant than $P_j$ to distinguish both classes. This justifies additionally considering symmetry-related properties to fully characterize the measures: class symmetry, in particular, allows checking whether *Contrastivity* also applies from the perspective of the negative class.

*Jumpiness.* Previous works [60] have introduced the notion of *jumping emerging* pattern, which are patterns present in only one class. All such patterns are not necessarily interesting for classification: for example, a pattern appearing in a single graph is not very discriminative, overall. Nevertheless, some measures assign the same value to all emerging patterns, which makes it impossible to distinguish one jumping emerging pattern from another. As mentioned by Loyola-González et al. [63], this can lead to retaining a set of poorly discriminative patterns. Based on this observation, we define the property of *Jumpiness*, which concerns quality measures able to distinguish between jumping emerging patterns.

**Definition 4.2 (Jumpiness).** A quality measure $q$ respects the *Jumpiness* property iff

$$ \forall P_i, P_j, [p(\mathcal{G}^+ | P_i) = p(\mathcal{G}^+ | P_j) = 1 \land p(P_i, \mathcal{G}^+) > p(P_j, \mathcal{G}^+)] \Rightarrow [q(P_i, \mathcal{G}^+, \mathcal{G}^-) > q(P_j, \mathcal{G}^+, \mathcal{G}^-)]. $$

In other words, if all the occurrences of $P_i$ and $P_j$ belong to $\mathcal{G}^+$, then the most frequent of the two patterns gets a higher quality value. Consequently, measures possessing the *Jumpiness* property take into account *False Negatives* as defined in Section 4.1. In addition, a measure that does not respect this property ranks contrast subgraphs of the
positive class better than every other pattern, since contrast subgraphs are jumping emerging patterns. This property is original, it is not equivalent to any other from the literature (see Appendix A.3).

Consider $P_1$ and $P_3$ in our example from Figure 2, and quality measure $CONF$, i.e. $p(\mathcal{G}^+ | P)$. Both patterns occur only in $\mathcal{G}^+$, and $P_1$ is more frequent than $P_3$ (3 vs. 1). Yet, $CONF$ is 1 for both patterns, and consequently does not possess the *Jumpiness* property. Consider now measure $SUPDIF$, i.e. $p(P | \mathcal{G}^+) - p(P | \mathcal{G}^-)$. The antecedent of Definition 4.1 yields $p(P | \mathcal{G}^-) = 0$, as both patterns are only present in $\mathcal{G}^+$. Therefore, in this case the measure only depends on $p(P | \mathcal{G}^+)$ and respects the *Jumpiness* property.

*Class Symmetry.* In both previous properties, the positive and negative classes do not hold the same role. This is because in certain applications, users consider the positive class as the class of interest, and handle it differently from the negative class. Therefore, it can be interesting to distinguish these measures from those that make no difference between the classes. For this purpose, we define the *Class Symmetry* property, which concerns measures for which both classes are interchangeable.

*Definition 4.3 (Class Symmetry).* A quality measure $q$ respects the Class Symmetry property iff

$$ \forall P, q(P, \mathcal{G}^+, \mathcal{G}^-) = q(P, \mathcal{G}^-, \mathcal{G}^+) . $$

Our Class Symmetry is similar to T2b (Column Antisymmetry), the second variant of the second property defined by Tan et al. [83], except for the sign of the right-hand term (cf. Appendix A.3.2).

Consider $P_2$ in the example from Figure 2, and measure $CONF$, defined as $p(\mathcal{G}^+ | P)$. We have $CONF(P_2, \mathcal{G}^+, \mathcal{G}^-) = 0.6$ and $CONF(P_2, \mathcal{G}^-, \mathcal{G}^+) = 0.4$, therefore this measure is not class symmetric. Consider measure $DEP$ instead, which is defined as $|p(\mathcal{G}^-) - p(\mathcal{G}^- | P)|$. Using $p(\mathcal{G}^- | P) + p(\mathcal{G}^+ | P) = 1$, we can replace $p(\mathcal{G}^- | P)$ by $1 - p(\mathcal{G}^+ | P)$ in $DEP$, and get $|p(\mathcal{G}^-) - 1 + p(\mathcal{G}^+ | P)|$. Probabilities $p(\mathcal{G}^-)$ and $p(\mathcal{G}^+)$ also sum to one, which yields $| - p(\mathcal{G}^+) + p(\mathcal{G}^+ | P) | = |p(\mathcal{G}^+) - p(\mathcal{G}^+ | P)|$. In the end, $DEP(P, \mathcal{G}^+, \mathcal{G}^-) = DEP(P, \mathcal{G}^-, \mathcal{G}^+)$, and the property follows for this measure.

*Pattern Symmetry.* Classes can be characterized in terms of the presence of certain patterns, but also in terms of their absence. The *Pattern Symmetry* property concerns measures for which being absent from a class is as important as being present, when ranking the patterns.

*Definition 4.4 (Pattern Symmetry).* A quality measure $q$ respects the Pattern Symmetry property iff

$$ \forall P, q(P, \mathcal{G}^+, \mathcal{G}^-) = q(\bar{P}, \mathcal{G}^+, \mathcal{G}^-) . $$

Pattern Symmetry is similar to T2a (Row Antisymmetry), the second variant of the second property defined by Tan et al. [83], except for the sign of the right-hand term (cf. Appendix A.3.2). When performing frequent pattern mining, one identifies the patterns with the highest overall support. In this context, it may be interesting to distinguish between measures that treat similarly the presence and absence of patterns, from those that favor their presence.

Consider $P_2$ in the example from Figure 2, and measure $CONF$, defined as $p(\mathcal{G}^+ | P)$. We have $CONF(P_2, \mathcal{G}^+, \mathcal{G}^-) = 0.6$ and $CONF(\bar{P}_2, \mathcal{G}^+, \mathcal{G}^-) = 0$, therefore this measure is not pattern symmetric. Consider now measure $ABSUPDIF$, which is defined as $|p(P | \mathcal{G}^+) - p(P | \mathcal{G}^-)|$. By definition, $p(P | \mathcal{G}^+) + p(\bar{P} | \mathcal{G}^i) = 1$ for $G^i \in \{\mathcal{G}^+, \mathcal{G}^-\}$, therefore we get $|1 - p(\bar{P} | \mathcal{G}^+) - 1 + p(\bar{P} | \mathcal{G}^-)| = |p(\bar{P} | \mathcal{G}^+) - p(\bar{P} | \mathcal{G}^-)|$. As a consequence, $ABSUPDIF(P, \mathcal{G}^+, \mathcal{G}^-) = ABSUPDIF(\bar{P}, \mathcal{G}^+, \mathcal{G}^-)$, and this measure is pattern symmetric.
# 5 METHODOLOGICAL FRAMEWORK

The methods that we propose to assess the quality measures listed in Section 4 rely on two distinct comparisons, each one corresponding to a specific step of the graph classification pipeline described in Section 3 (see Figure 1). The first comparison is *direct*, as it focuses on the way the quality measures rank the patterns, i.e. Step 2. It entails a major methodological difficulty: distinct patterns may result in similar vector representation, and this should be accounted for when comparing rankings. For this purpose, we propose an additional pattern clustering step, denoted Step 1a, and described in Section 5.1. Its main effect is that the rest of the pipeline deals with only a subset of the original patterns, called *representatives*. Figure 3 shows the pipeline resulting from this modification, with the additional step in blue. We then discuss the appropriate correlation coefficients to compare pattern rankings in Section 5.2.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Processing steps of the extended framework, including the additional clustering step (1a), in blue.</figcaption></figure>

The second comparison is *indirect*, as it relies on a *task-driven evaluation* guided by the classification performance obtained after training (Step 5). The classifier training and its subsequent performance depend on the vector representation of the graphs, which is based itself on how the patterns are ranked using the quality measure, hence the indirect nature of this comparison. It is methodologically much simpler than ranking comparison, though, as it only requires standard classification performance measures, which we discuss in Section 5.3.

## 5.1 Clustering Step

In Section 3, we introduce the notion of footprint of a pattern: it corresponds to $h_{ij}$, the binary vector in which each value $h_{ij}$ indicates whether pattern $P_j$ is present or absent from graph $G_i$. At this stage, we consider $\mathcal{P}$, the full set of patterns detected at Step 1 (Pattern identification). Let us assume that two patterns $P_i$ and $P_j$ have the same footprint, i.e. $h_{i} = h_{j}$. In other words, these patterns appear in exactly the same graphs of $\mathcal{P}$, and are absent from exactly the same graphs, too. Consequently, they have the same discriminative power, independently of the considered measure. In summary, they are two different subgraphs (i.e. they may contain different vertices and edges) that are identical from the classification perspective. Thus, they are interchangeable in the pattern ranking produced at Step 2.

This behavior is an issue when comparing pattern rankings, as illustrated by Figure 4. Its left part shows a dataset constituted of four graphs. Step 1 results in the identification of six patterns $P_1, ..., P_6$. Some of them share the same footprint, as indicated by their colors. The right part of the figure shows the rankings obtained by three different quality measures ($q_1, q_2, q_3$). Patterns having the same footprint are likely to be placed consecutively in each ranking, but not necessarily in the same exact order. Measures $q_1$ and $q_2$ agree that the green footprint is the most discriminative, followed by the red and blue ones, but they differ in the way they rank patterns within a color group. As a consequence, using the top $k$ patterns of each ranking to train the classifier results in the exact same classification performance, as
<figure><img src="image_5.png" /><figcaption>Fig. 4. Illustration of the issue occurring when comparing rankings of patterns possessing similar footprints in the original framework.</figcaption></figure>

same-color patterns are interchangeable from the classification perspective. However, comparing the rankings with a measure such as Kendall's Tau (see Section 5.2.2) does not lead to a maximal similarity (here: $\tau = 0.47$). By comparison, the ranking obtained with the third quality measure $q_3$ places the red footprint before the green one, which is likely to affect the classification performance. However, it is more similar to $q_1$ in terms of rank correlation ($\tau = 0.60$), which constitutes an undesirable behavior.

In order to tackle this issue, we propose an additional Step 1a in the graph classification pipeline, which is detailed in Figure 5. The top part of the figure positions this step in the general pipeline, whereas the bottom part provides an example that we discuss throughout this section. Step 1a takes place before Step 2 (Pattern Ranking), and consists in performing a cluster analysis of the patterns identified at Step 1, in order to constitute groups of patterns with similar footprints. Grouping patterns with identical footprints is necessary to conduct proper ranking comparison, but we hypothesize that more relaxed groups could also be a way to reduce noise in $P_s$, the subset of patterns selected at Step 3 and used to build the vectors representing the graphs. For this reason, we do not focus only on strictly equal footprints, but also experiment with clusters that include patterns whose footprints are similar (and not necessarily identical).

<figure><img src="image_6.png" /><figcaption>Fig. 5. Detail of the pattern clustering process in our extended framework (Step 1a in Figure 3), in blue.</figcaption></figure>

We do not have any *a priori* idea of the number of clusters to expect, which rules out methods requiring the user to specify this as a parameter, such as k-means. Instead, we want to control how strict the method is when grouping patterns. Put differently, we want to specify how similar two patterns should be to be placed in the same cluster. For this reason, we adopt a standard hierarchical agglomerative method [35]. In such ascending methods, all clusters are
initially singletons, which are iteratively merged until only one cluster containing all the elements remains. The merged clusters are decided depending on the so-called *linkage criterion*, a function that computes the dissimilarity between two clusters based on the dissimilarity between their constituting elements. We use the *complete-linkage* criterion: the dissimilarity between two clusters corresponds to that of their most distant elements. In order to compare the elements themselves (i.e. the footprints), we select the Manhattan distance. Its advantage here is that its interpretation is straightforward: it corresponds to the number of graphs for which the compared patterns differ (i.e. one is present and the other absent). Combining the Manhattan distance and the complete-linkage in such a way is particularly suitable to our case. Indeed, it means that, for a given iteration, all the patterns belonging to the same cluster are *at most* as dissimilar as the last two merged clusters.

A hierarchical clustering method produces a *dendrogram*, i.e. a tree showing the successive partitions: from singleton clusters at the first level, to a single all-encompassing cluster at the top level. In our case, the second level corresponds to clusters containing patterns with strictly *identical* footprints, whereas higher levels gather *similar* footprints together. The higher the level, the larger the clusters, and the less similar their constituting patterns' footprints. Thus, selecting a level in the dendrogram amounts to controlling how similar the footprints need to be for the patterns to be considered as interchangeable. We find it convenient to characterize each level by its so-called *distance threshold*: the maximal distance allowed between two patterns belonging to the same cluster. In level 1, each pattern forms a cluster on its own; whereas in level 2, each cluster gathers patterns whose footprints are identical. In level 3, the distance between all patterns constituting a cluster is at most 1, meaning the patterns are present/absent from the same graphs but one. In level 4, this distance is at most 2, and so on.

The selection of the most appropriate level of the dendrogram is conducted empirically, which is why we discuss it later, in Section 6. Let us assume for now that we are able to pick the best level: at this stage, we have a partition of the pattern set $\mathcal{P}$, and we consider each of its clusters as a group of interchangeable patterns. Next, we compute the *medoid* of each cluster, i.e. the pattern that minimizes the total distance to the rest of its cluster [74]. We call this pattern the *representative* of the cluster. All the other patterns from the same cluster are considered interchangeable with their representative, therefore we can ignore them in the rest of the process. This makes it possible to reduce the dimension of the representation space, and consequently the processing costs. We build $\mathcal{P}_c$, the subset of $\mathcal{P}$ that only contains the representatives. This set is then used in the next step, which consists in ranking the patterns (Step 2). It is worth stressing that the obtained clusters are also interesting from the perspective of interpretation: they allow identifying patterns that are possibly very different structurally, but exhibit similar footprints, and are therefore characteristic of the same class.

In the example represented in the bottom half of Figure 5, the diagram associated to Step 1 represents a set of four graphs described by six patterns (the same as in Figure 4). The result of the cluster analysis is shown next to it: three groups of patterns noted $C_1, C_2$ and $C_3$. The next part of the example shows the selection of a representative (medoid) for each cluster: $P_1$ for $C_1$; $P_3$ for $C_2$; and $P_5$ for $C_3$. These three patterns constitute $\mathcal{P}_c$, which is fetched to Step 2 (ranking step) in order to produce $\mathcal{P}_r$ and go on with the standard process.

## 5.2 Ranking Evaluation

We now focus on our first method aiming at comparing the measures, which relies on the rankings they produce. The purpose of each quality measure is to rank the patterns depending on their hypothesized discriminative power. In order to assess the quality of such rankings, we need two resources: first, a gold standard, i.e. the ranking which is optimal for our classification task, and second, a coefficient able to assess the similarity between this gold standard and the
ranking estimated by a given quality measure. Moreover, this coefficient can be used to compare pairs of measures, through their rankings. To elaborate the ground truth, we propose an approach based on the Shapley Value, which we introduce in Section 5.2.1. To compare rankings, we select two tools, described in Section 5.2.2: Kendall's Tau, a very widespread rank correlation coefficient [50], and Rank-Biased Overlap [95], which is able to handle cases where the ranked objects are not exactly the same on both ranked lists.

### 5.2.1 Shapley Value.
The Shapley Value [82] (SV) originates from Game Theory. It was designed in the context of cooperative games, to assess the contribution of individual players among coalitions of players.

$$SV(p) = \sum_{S \subset S \setminus \{p\}} \frac{|S|! (|S| - |S| - 1)!}{|S|!} (f(S \cup \{p\}) - f(S)) \quad (1)$$

where $p$ is a player, $S$ is the set of all players, $S$ is used to consider all possible coalitions that exclude $p$, i.e. subsets of $S \setminus \{p\}$, and $f(X)$ is the so-called characteristic function, which assesses the contribution of coalition $X$. The right-hand factor is the difference between the contribution of a coalition $S$ with an additional player $p$ and the same coalition without $p$. One averages this quantity over all possible coalitions to compute the SV of $p$.

The SV was later used in machine learning, to perform feature selection, as it allows measuring how much individual features contribute to solving the task at hand [31]. For instance, suppose that one has a collection of data points, described by certain features, and that they leverage them to train a classifier. In this analogy, the features correspond to the players of the original definition, and $f$ is the measure used to assess classification performance. In this context, the SV is interpreted as a score that represents the impact of a feature on the final performance.

The main drawback of the SV is its algorithmic complexity, which requires considering all possible coalitions of players (or combinations of features): this prevents from computing it in many real-world situations [56]. For this reason, in practice, one generally computes an approximation. Several scores were designed specifically for machine learning applications, based on such approximations [20, 64, 65]. These approaches differ according to two aspects:

* **Explanation scope**: some methods such as SHAP [65] provide a local explanation, in the sense that each data point is treated separately. As a result, they assess the contribution of a feature relative to a data point. On the contrary, other methods such as SAGE [20] adopt a global approach, and characterize a feature relative to the whole dataset.

* **Explanation target**: some methods such as SHAP [65] aim to directly explain the value predicted by the machine learning model (e.g. a class), while others like SAGE [20] targets its performance, by explaining loss or accuracy.

In our case, we deal with a classification task, where the data point corresponds to graphs and their features to patterns. We want to assess the contribution of each pattern to the final classification performance. Therefore, we need an approach that has a global scope, and targets performance. For this reason, we select SAGE and use it to compute an approximation of the SV for each pattern. We then rank the patterns by decreasing SV: this constitutes our gold standard, i.e. our best approximation of the true ranking of patterns depending on their discriminative power.

### 5.2.2 Ranking Comparison.
In order to compare a pattern ranking estimated through a quality measure and the gold standard, we need a suitable coefficient. In a similar context, Loyola-González et al. [63] suggest using Kendall's Tau [50]. However, it has certain limitations, so we also use the Rank-Biased Overlap (RBO) as an alternative coefficient.

**Kendall's Tau.** This rank correlation coefficient applies to two rankings of the same set of elements. For each pair of elements that can be formed over this set, the rankings are considered as either concordant or discordant. Concordant
means that they both put the two elements in the same order, and discordant means the opposite. The coefficient is the difference between the proportions of concordant and discordant pairs.

In our case, the considered set is $P_s = \{P_1, ..., P_s\}$, and its constitutive elements are the s representative patterns obtained after the selection step (Step 3 in Figure 3). Let us note $r_1(P)$ and $r_2(P)$ the ranks assigned to pattern P according to the first and second rankings, respectively. Then Kendall's Tau is defined as:

$$ \tau = \frac{1}{s(s-1)/2} \sum_{1 \le i < j \le s} \operatorname{sgn}(r_1(P_i) - r_1(P_j)) \operatorname{sgn}(r_2(P_i) - r_2(P_j)), \quad (2) $$

where sgn is the signum function, which returns -1 if its argument is negative, and 1 if it is positive. As a consequence, the product located inside the sum is either -1 (discordance) or 1 (concordance). Kendall's Tau ranges from -1 (only discordant pairs, i.e. one ranking is the reverse of the other) to +1 (only concordant pairs, i.e. identical rankings).

We identify two limitations with Kendall's Tau. The first is that it requires both rankings to be defined over the exact same set of objects. In our experiments, there are some situations where this constraint is not respected. Second, Kendall's Tau gives the same importance to each rank. In our context, we ultimately want to select the top s patterns to perform the classification. Clearly, we want to give more importance to the best-ranked patterns when comparing the rankings: discordance for the top patterns is more serious than discordance for the bottom ones.

*Rank-Biased Overlap.* To tackle these limitations, we propose to use the *Rank-Biased Overlap* (RBO) [95] as an alternative to Kendall's Tau when comparing the rankings. Let us note $R_1(d)$ and $R_2(d)$ the d first patterns according to the two considered rankings. The RBO is originally defined to compare infinite lists, as follows:

$$ RBO_p = (1 - p) \sum_{d=1}^{+\infty} p^{d-1} \frac{|R_1(d) \cap R_2(d)|}{d}. \quad (3) $$

In our case, though, we compare rankings of finite sets, and the upper bound of the sum is s. Variable d is used to consider an increasing number of top-ranked patterns. Inside the sum, the right-hand factor is the proportion of patterns that both rankings put in the top d. The left-hand factor is a weight that decreases exponentially with d: it allows giving more importance to the best-ranked patterns when comparing the rankings. The magnitude of this importance is controlled through parameter p (0 < p < 1): a smaller p puts more emphasis on top patterns. The (1 - p) term is a normalizing factor. In the end, the RBO can be seen as the weighted average of overlaps between the rankings. The coefficient ranges from 0 (rankings containing completely different elements) to 1 (exactly the same rankings).

According to its authors [95], the advantage of the RBO over other correlation coefficients able to handle sets that do not completely overlap, such as Fagin's Intersection Metric [26], is that the RBO is monotonic with increasing s: if one ranking is a prefix of another, then increasing s will not lead to a decrease of the RBO. This avoids biases in very large sets, where numerous concordances or discordances in the tails of the rankings could otherwise take too much importance.

## 5.3 Classification Performance

To assess the performance of our classifier, we use three very standard metrics: Precision, Recall, and F1-Score [90], while focusing on the positive class. Let TP, FP and FN denote the numbers of True Positives, False Positives and False
Negatives, respectively. Precision and Recall are defined as:

$$Pre = \frac{TP}{TP + FP} \qquad (4)$$

$$Rec = \frac{TP}{TP + FN} \qquad (5)$$

In order to ease the comparison of our classification results, it is more convenient to summarize them under the form of a single value. For this purpose, we use the F1-Score, which is the harmonic mean of Precision and Recall:

$$F1 = 2 \frac{Pre \times Rec}{Pre + Rec} \qquad (6)$$

# 6 EXPERIMENTS

We devise a series of experiments seeking to answer the following three major questions:

* RQ1 Is it possible to achieve more compact graph representation without compromising classification performance?

* RQ2 Do quality measures behave consistently across graph datasets?

* RQ3 Can we identify quality measures that tend to perform better than others?

In the following, we first introduce the practical settings used for our experiments (Section 6.1). After that, we address Q1 first, by studying how clustering affects the number of representatives, the rankings obtained with the measures, and the classification performance (Section 6.2). We then tackle Q2, by assessing the correlation between the rankings produced by the considered quality measures (Section 6.3). Finally, we answer Q3, by studying how classification performance is affected by the considered quality measure (Section 6.4).

## 6.1 Experimental Settings

Let us first review the datasets as well as the pattern mining and cluster analysis tools used in our experiments. Our source code is written in Python and publicly available online<fnref n="2" />. Each dataset is also publicly available, as indicated below.

*Datasets.* Our selection of datasets is constrained by two aspects. First, graph datasets annotated for classification are much less common than their tabular counterparts. Second, our experimental protocol requires enumerating large numbers of patterns over the considered graph collections: this is computationally costly, especially in dense graphs [43]. For this reason, we favor attributed graphs, which ease this task, as they lead to fewer cases of subgraph isomorphisms. We identify eight datasets fitting these constraints:

* MUTAG<fnref n="3" /> [21], a dataset of nitroaromatic compounds. Each compound is represented as a graph, with vertices and edges modeling atoms and chemical bonds between them, respectively. Vertices are labeled by atom type and edges by bond type.

* PTC<fnref n="4" /> [88], a dataset of chemical compounds used in toxicity screening. Each compound is represented as a graph, as in MUTAG. Vertices are labeled by atom type.

* NCI1⁵ [93], a dataset of chemical compounds used in anti-cancer screening. Each compound is represented as a graph, as in the previous datasets. Vertices are labeled by atom type and edges by bond type.

<footnote n="2">²https://github.com/CompNet/gpQualMeasComp</footnote>

<footnote n="3">³https://www.philippe-fournier-viger.com/spmf/datasets/dang/mutag_graph.txt</footnote>

<footnote n="4">⁴https://www.philippe-fournier-viger.com/spmf/datasets/dang/ptc_graph.txt</footnote>

<footnote n="5">⁵https://www.philippe-fournier-viger.com/spmf/datasets/dang/nci1_graph.txt</footnote>
* D&D<fnref n="6" /> [23], a dataset of chemical compounds. Each compound is represented as a graph, as before. Vertices are labeled by amino acid type.

* AIDS<fnref n="7" /> [77], a dataset of chemical compounds tested for AIDS inhibition. Each compound is represented as a graph, as before. Vertices are labeled by atom type and edges by bond type.

* FOPPA<fnref n="8" /> [73], a dataset of public procurement contracts. Each set of contracts is represented as a graph, with vertices representing contractors and edges representing commercial relationships between them. Vertices are labeled according to contractor type, and edges are labeled by categories reflecting numbers of contracts.

* IMDb-BINARY<fnref n="9" /> [101] (IMDb), a dataset of movie collaboration graphs. Vertices model actors, and edges represent co-appearances in movies. Each vertex has an integer label with unspecified meaning.

* FRANKENSTEIN<fnref n="10" /> [69] (FRANK), a dataset of chemical compounds. This dataset has no label on vertices nor edges.

Table 4 summarizes the most important characteristics of these datasets. We perform under-sampling to obtain balanced classes whenever needed. The size of the datasets ranges from hundreds to thousands of graphs, while the numbers of possible values for vertex and edge attributes range from none to several tens. They are relatively homogeneous in terms of graph size though, except D&D whose graphs contain much more vertices and edges. The degree average and density are very heterogeneous, the latter ranging from 0.09 to 0.52. Similarly, the average clustering coefficient is very high in certain graphs (0.773 in IMDb) and very low in others (0.003 in NCI1). The chemical networks are sparser than the social networks, which is consistent with the literature [67]. FOPPA contains many bipartite graphs, for this reason the clustering coefficient is not defined on this dataset. Moreover, we compute its density using the formula defined for bipartite graphs [79]. The last row in the table shows the average number of unique patterns mined in the graphs, and also exhibits a high variability. For certain datasets (marked with a *), the pattern search is not exhaustive, because of computational limitations. In summary, our datasets exhibit a certain heterogeneity, and therefore our selection is illustrative because it covers a wide range of cases.

<table><caption>Table 4. Main characteristics of the eight graph datasets constituting our benchmark.</caption><thead><tr><th>Characteristic</th><th>MUTAG</th><th>PTC</th><th>NCI1</th><th>D&D</th><th>AIDS</th><th>FOPPA</th><th>IMDb</th><th>FRANK</th></tr></thead><tbody><tr><td>Number of graphs</td><td>188</td><td>344</td><td>4,110</td><td>1,178</td><td>2,000</td><td>660</td><td>1,000</td><td>4,337</td></tr><tr><td>Number of vertex label values</td><td>7</td><td>19</td><td>37</td><td>82</td><td>38</td><td>2</td><td>65</td><td>-</td></tr><tr><td>Number of edge label values</td><td>11</td><td>-</td><td>3</td><td>-</td><td>3</td><td>3</td><td>-</td><td>-</td></tr><tr><td>Average number of vertices</td><td>14.58</td><td>25.56</td><td>29.87</td><td>284.31</td><td>15.69</td><td>14.20</td><td>19.77</td><td>16.89</td></tr><tr><td>Average number of edges</td><td>19.79</td><td>15.03</td><td>32.30</td><td>715.66</td><td>16.20</td><td>14.91</td><td>96.39</td><td>17.87</td></tr><tr><td>Mean average degree</td><td>2.19</td><td>1.99</td><td>2.16</td><td>4.98</td><td>2.01</td><td>2.03</td><td>8.88</td><td>2.06</td></tr><tr><td>Average density</td><td>0.14</td><td>0.21</td><td>0.09</td><td>0.03</td><td>0.19</td><td>0.40</td><td>0.52</td><td>0.17</td></tr><tr><td>Average global clustering coefficient</td><td>0.000</td><td>0.008</td><td>0.003</td><td>0.458</td><td>0.007</td><td>-</td><td>0.773</td><td>0.010</td></tr><tr><td>Average number of unique patterns</td><td>156</td><td>120*</td><td>614*</td><td>3,361*</td><td>177*</td><td>528</td><td>106*</td><td>1,342*</td></tr></tbody></table>

<footnote n="6">⁶https://www.philippe-fournier-viger.com/spmf/datasets/dang/dd_graph.txt</footnote>

<footnote n="7">⁷https://chrsmrrs.github.io/datasets/docs/datasets/</footnote>

<footnote n="8">⁸https://doi.org/10.5281/zenodo.10879932</footnote>

<footnote n="9">⁹https://www.philippe-fournier-viger.com/spmf/datasets/dang/IMDb_binary_graph.txt</footnote>

<footnote n="10">¹⁰https://chrsmrrs.github.io/datasets/docs/datasets/</footnote>
For the sake of concision, we only focus on 6 of these 8 datasets when presenting our results in the rest of this section. The comprehensive results obtained for IMDb and FRANK are available in Appendix D, though. We defer them to the appendix because these results are very similar to those of AIDS and D&D, respectively.

**Pattern Mining.** To mine the patterns in the datasets (Step 1 of the pipeline, cf. Figure 3), we use the SPMF library [30], which provides a wide range of algorithms for pattern mining. We adopt the gSpan method [100], which is a well-known algorithm for mining frequent subgraphs. Mining patterns in graphs is a complex task, as the number of possible patterns is exponential in the number of vertices and edges. Therefore, on huge datasets, we limit the number of patterns to mine by setting a minimum support threshold. This threshold is the minimal number of graphs in which a pattern must appear to be considered as frequent.

<table><caption>Table 5. Number of patterns mined for each dataset presented in Table 4.</caption><thead><tr><th>Dataset</th><th>MUTAG</th><th>PTC</th><th>NCI1</th><th>D&D</th><th>AIDS</th><th>FOPPA</th><th>IMDb</th><th>FRANK</th></tr></thead><tbody><tr><td>Minimum support (% of graphs)</td><td>0</td><td>1</td><td>1</td><td>25</td><td>1</td><td>0</td><td>1</td><td>20</td></tr><tr><td>Minimum support (number of graphs)</td><td>1</td><td>4</td><td>42</td><td>277</td><td>20</td><td>1</td><td>10</td><td>837</td></tr><tr><td>Number of unique patterns</td><td>3,408</td><td>5,285</td><td>11,564</td><td>10,000</td><td>5,589</td><td>11,773</td><td>4,741</td><td>5,000</td></tr></tbody></table>

In general [1, 63], this minimal threshold for frequent pattern mining is selected empirically, and expressed as a percentage of the number of graphs contained in the dataset. It is often between 5% and 15% of the number of graphs [78, 86, 98]. It is worth mentioning that our work is agnostic to the specific method used to extract patterns, as we are primarily interested in how a given set of patterns is ranked. While different pattern mining techniques may produce different sets of patterns, our approach mitigates this variability by considering the complete enumeration of patterns (whenever feasible), and applying a common threshold otherwise.

We indicate this in Table 5, along with the raw graph count corresponding to the associated support. In practice, a value of 1 means that there is no minimum support threshold. Table 5 also shows the number of patterns identified in each dataset.

**Cluster Analysis.** To perform the hierarchical clustering (Step 1a, described in Section 5.1), we use the standard AgglomerativeClustering method of package sklearn<fnref n="11" />. In order to follow the protocol defined in Section 5.1, we set the following parameters:

* *metric*: set to precomputed, which allows proposing a custom function to compute the distance between patterns. In our case, this function implements the Manhattan distance between footprints.

* *linkage*: set to complete, i.e. use complete-linkage to assess the distance between clusters. As previously explained, this amounts to using the distance between the farthest elements of the considered clusters.

**Gold Standard.** The elaboration of the gold standard requires computing SAGE values (cf. Section 5.2.1). The original implementation is publicly available online<fnref n="12" />, however it is very time-consuming. Instead, we use LossSHAP<fnref n="13" />, an alternative implementation which is much faster. It only provides a local version of SAGE, though, which is why we compute an average over all patterns to obtain the global scores that we need.

<footnote n="11">¹¹https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html</footnote>

<footnote n="12">¹²https://github.com/iancovert/sage</footnote>

<footnote n="13">¹³https://shap.readthedocs.io/en/latest/</footnote>
## 6.2 Clustering Assessment

In this section, we present the results of the clustering step. It aims to group patterns with similar footprints, in order to reduce the number of patterns to consider without losing too much classification performance. We study the influence of clustering on the number of representatives (Section 6.2.1), on the rankings produced by the quality measures (Section 6.2.2), and on the classification performance (Section 6.2.3).

6.2.1 *Number of Representatives.* First, we discuss the number of representatives obtained by applying the clustering process with different clustering threshold values. Figure 6 shows the number of representatives identified for each dataset as a function of this threshold. The maximal Manhattan distance between two footprints corresponds to $|G|$, the number of graphs in the considered collection. In order to ease the comparison between datasets, we use this value to normalize the threshold and express it as a percentage (x-axis).

<figure><img src="image_7.png" /><figcaption>Fig. 6. Number of representatives as a function of the clustering threshold. Note the logarithmic scale of the y-axis. The red horizontal lines represent the original number of patterns detected in the datasets.</figcaption></figure>

In each plot, the red line indicates the initial number of patterns, i.e. without any clustering. Consider the strictest clustering, obtained by setting a threshold of 0%, i.e. by grouping only patterns with identical footprints: for certain datasets, the number of representatives is significantly lower than the initial number of patterns (note the logarithmic scale of the y-axis). There is a reduction in the number of patterns by approximately 63% for PTC, 92% for MUTAG and 44% for FOPPA. Meanwhile, NCI1, D&D and AIDS exhibit lower reduction rates, with 4%, 9% and 16% of the total number of patterns respectively. This is because pattern mining on these datasets is less comprehensive, and therefore the patterns mined are less redundant on average. In any case, the number of representatives decreases sharply as the clustering threshold increases, reaching a minimal value when there is only one cluster left.
Based on these results, it appears clearly that clustering allows for the reduction of the number of patterns to be processed later in the algorithm. We then seek to study whether it removes redundant patterns and improves the comparison of measure rankings, as intended.

### 6.2.2 Ranking Comparison.
As explained in Section 5.1, the goal of our clustering step is to enable a better comparison among the considered quality measures, by avoiding considering redundant patterns (i.e. patterns exhibiting similar footprints). The quality measures are computed only over the cluster representatives, instead of all detected patterns. The clustering threshold controls how similar the grouped patterns are, and is likely to affect the rankings obtained with the quality measures, and therefore their comparison.

In order to study the impact of this parameter on the rankings, we consider four threshold values (0%, 20%, 40% and 60%) and compute Kendall's Tau between the rankings produced with all pairs of quality measures. Each plot in Figure 7 represents the distribution of Tau obtained for one of the considered datasets. Each such plot exhibits four distributions corresponding to the four selected threshold values, and shown as histograms of different colors. For better readability, separate plots are available in Appendix B.1.

<figure><img src="image_8.png" /><figcaption>Fig. 7. Distribution of Kendall's Tau over all pairs of quality measures, for four values of the clustering threshold (0%, 20%, 40% and 60%). See Appendix B.1 for more plots.</figcaption></figure>

We observe three different outcomes. First, when a clustering is performed with a threshold of 0 (green histograms), Tau is close to 0 for all pairs of measures. This means that there is not much similarity between their rankings, and each measure consequently provides a unique ranking. Our assumption is that this is due to the presence of many patterns that are different but have similar footprints, which makes ranking *seemingly* dissimilar (see Section 5.1). Second, when increasing the threshold (red and orange histograms), Tau is distributed more uniformly, and some pairs
of measures are associated with a Tau close to 1. This means that these pairs of measures produce similar rankings from the perspective of footprints. The clustering step reveals this otherwise hidden similarity. Some pairs also exhibit low correlation values, though, which just means that some measures behave differently. Put differently, the measures form a few similarity classes (i.e. groups of measures leading to similar rankings). Third and finally, when the threshold gets very high (blue histograms), the correlation values get more extreme (close to -1 and 1). The relevant differences between the rankings produced by the measures are not captured anymore, and they are considered as highly similar or dissimilar by Tau. In other terms, there are only a very few (sometimes 1 or 2) similarity classes of measures.

Our results show that our clustering step has the expected effect: by removing the redundancy among patterns, it allows making more apparent the similarity between the rankings produced by the quality measures. On the one hand, performing a strict clustering by using a very low threshold means obtaining many small clusters of patterns with exactly the same footprint, which may not differ much from using all patterns. On the other hand, performing a very relaxed clustering based on a high threshold results in a few very large clusters, likely to gather patterns exhibiting very different footprints. This would excessively reduce the number of representatives, and provide an unreliable comparison between the measure rankings. The choice of the distance threshold is therefore crucial. We next propose a method to select the most appropriate value.

### 6.2.3 Classification Performance.
We turn to the evaluation of the clustering process in terms of classification performance. We perform the clustering process with different threshold values and keep all the resulting representatives. We then use them to build a vector representation of the graphs and train a classifier, before assessing its classification performance with the F1-Score. Our objective is to find the optimal threshold for the clustering step, meaning the one where classification performance is maximized with the smallest possible number of representatives. To ensure a fair evaluation, we use C-Support Vector Machines [19] as the classification model, as it is a widely used approach in this domain [76, 86]. This choice allows us to focus on the impact of the clustering process on classification, rather than on rather than on the nature of the classifier.

Each plot in Figure 8 shows the classification performance as a function of the clustering threshold, expressed as a percentage of the number of graphs in the dataset, as in Figure 6. For reference, the horizontal red lines show the performance obtained without any clustering. The vertical dotted black lines show the threshold values that are the best trade-off between minimizing the number of representatives and maximizing the classification performance.

We observe three distinct behaviors over the considered datasets. For MUTAG and PTC, increasing the threshold leads to a better classification performance, up to a point where it starts decreasing. These sweet spots correspond to our optimal thresholds, shown as vertical black lines. These results confirm that clustering helps to reduce the number of redundant patterns, and to retain only those that are relevant for classification. When compared to the performance obtained without any clustering (red lines), we even see some substantial improvement. For D&D and FOPPA, the classification performance initially stagnates, or only slightly improves, when increasing the threshold. After some point, it starts to decrease. In these cases, clustering improves classification performance (compared to the red lines), even if only slightly. In any case, it alleviates the computational cost by reducing the dimension of the vector representation. For these reasons, these points, shown as vertical black lines, also correspond to the best thresholds. Finally, for AIDS and NCI1, the classification performance decreases as soon as we increase the threshold. This means that clustering removes discriminative patterns essential for the classification right from the start. However, we do not notice any difference between the performance without clustering and with a threshold of 0, which implies that minimal clustering is still interesting, by reducing the number of total patterns. For this reason, our selected thresholds
<figure><img src="image_9.png" /><figcaption>Fig. 8. Classification performance (F1-Score) as a function of the clustering threshold. The vertical dotted black lines materialize the threshold values used in the rest of our experiments.</figcaption></figure>

values (black lines) are very low for these datasets. For all datasets, we observe a drastic decrease of the F1-Score when the threshold gets very high. Indeed, these values make it possible to group patterns with very different footprints in the same cluster, and therefore fail to maintain a comprehensive set of representatives for classification.

Based on our results, we can propose a rule of thumb to select the clustering threshold in case of a general dataset. Our recommended threshold amounts to approximately 20% of the total number of graphs in the dataset. This leads either to an improvement of the classification, or in the worst case achieves a performance very close to the optimum. This threshold constitutes a balance between computational efficiency and accuracy. However, it would be interesting to validate this heuristic on additional datasets to confirm its general applicability.

Now that the appropriate threshold values are identified, we can focus on comparing the measures based on the pattern rankings they produce.

## 6.3 Pairwise Comparison

We now perform a pairwise comparison of the measures described in Section 4. Our objective is to identify groups of measures that lead to similar pattern rankings. Following our method from Section 5, we first group the patterns depending on their footprint similarity, using the threshold identified in Section 6.2.3, and we then rank their representatives using each quality measure. Since all measures deal with the same representatives, we compare these rankings with Kendall's Tau. There is a certain level of variability depending on the dataset: Figure 9 presents a synthetic view of our results over all datasets. The matrix is symmetric, and each one of its rows and columns corresponds to one of the quality measures. Each element of this matrix represents the minimal rank correlation between two measures over all
datasets. A high value therefore indicates that the quality measures rank the representatives similarly regardless of the dataset. The detail of the correlations obtained for each dataset considered separately is provided in Appendix B.2.

<figure><img src="image_10.png" /><figcaption>Fig. 9. Minimal value of Kendall’s Tau over all datasets, for each pair of quality measures.</figcaption></figure>

Yellow blocks in the figure correspond to groups of measures with a minimal correlation *equal* to 1, meaning they produce *identical* rankings over all datasets. We identify six of these blocks:

(1) CONF, CFACTOR, GR, BRINS, COLE, LIFT; SEBAG, ZHANG, CCONF and INFGAIN;

(2) ACC, LEVER, WRACC and SUPDIF;

(3) Cos and STRENGTH;

(4) COVER and SUP;

(5) SPEC and FPR.

(6) DEP, GINI and FISHER

The rest of the measures do not exhibit such similarity, except punctually, for some datasets (e.g. PTC, see Appendix B.2).
The measures belonging to the same block rank the patterns in the exact same way, therefore they also lead to identical
classification performances. For this reason, in the rest of our experiments, we select only one measure to represent
each block, in order to simplify the presentation and discussion of our results.

The first block contains measures that do not possess the Jumpiness property (see Definition 4.2), and are based on
$p(G^+ | P)$. They favor patterns that do not appear in the negative class, regardless of their frequency in the positive
class. This block is represented in the rest of our results by GR.
The measures that form the second block also favor patterns that appear more frequently in positive than negative graphs, but they possess the Jumpiness property. As a result, they are able to order jumping emergent patterns among themselves, in contrast to Block 1. Block 2 is represented in the rest of our results by Acc.

The measures of the third block prioritize patterns that are more present in the positive class than in the negative class, with a high frequency of appearance overall. In contrast to Blocks 1 and 2, patterns that are only present in the positive class, but very infrequent, will not necessarily be ranked before more frequent patterns. This block is represented in the rest of our results by Cos.

The fourth block is constituted of measures that do not respect the Contrastivity property (see Definition 4.1), and are only based on $p(P, G^+)$. The presence of the pattern in the negative class no longer matters, compared to the other blocks. This block is represented in the rest of our results by SUP.

The measures of the fifth block prioritize patterns that are often absent from the negative class. Similarly to the first block, they favor patterns that never appear in the negative class, regardless of their frequency in the positive class. However, they also rank well patterns that appear only a few times in the negative class, even if they are infrequent in the positive class. This block is represented in the rest of our results by SPEC.

The measures composing the sixth block focus on patterns that exhibit a strong contrast between the positive and negative classes. However, unlike the other blocks, they also assign high scores to patterns where this contrast favors the negative class. This block is represented in the rest of our results by DEP.

Loyola-González et al. [63] carried out a similar experiment, but worked on tabular data rather than graphs. They mine the most frequent patterns from 61 datasets, keeping only those that are more present in the positive than in the negative class. The patterns obtained are then ranked with each quality measure, and the different rankings are compared using Kendall's Tau. Overall, their results are similar to ours, but diverge in the following aspects:

* EXCEX and DEP are not in the same block as GR.

* PEARSON and $\chi^2$ are not correlated.

* ODDSRATIO and MDISC are not correlated.

In addition to these differences, LEVER is not associated with the Acc block, but it would appear that this is due to a mistake in the definition of the formula in [63], compared with that used in the literature [94].

All these differences can be explained by the fact that in our case, some patterns are more present in the negative than in the positive class, unlike the study conducted by Loyola-González et al. [63], which only focuses on patterns more frequent in the positive class. As a result, some patterns that are often present in the negative class are well ranked by some scores (DEP, EXCEX, MDISC, $\chi^2$) and not so much by others (GR, ODDSRATIO, PEARSON).

At this stage, we have determined that some measures are so correlated that it is not worth examining all of them, and that we can focus only on a subset constituted of 21 measures instead of 38, in the rest of our experiments. We next compare the rankings obtained with this subset, to our gold standard ranking.

## 6.4 Gold Standard Comparison

We now compare the measures selected at the previous section with our gold standard, on two aspects. First, in terms of pattern ranking, by assessing the similarity between the ranking obtained with each quality measure and the ranking produced based on the gold standard (Section 6.4.1). Second, in terms of classification performance, by comparing the F1-Score obtained when using the top representatives according to each quality measure to represent the graph,
against the top representatives according to the gold standard (Section 6.4.2). In each case, we examine the impact of the
parameter *s*, which indicates the number of representatives used to represent the graphs and perform the classification.

**6.4.1 Ranking Comparison.** Let us first compare the rankings estimated using the quality measures to the gold standard one. Using each measure, we rank the representatives identified at the clustering step, and focus on the top *s* patterns. As a result, this list of *s* patterns may differ from one measure to the other, and also from the gold standard. For this reason, we cannot use Kendall’s Tau, and turn to the RBO instead (see Section 5.2.2). An RBO close to 1 indicates that the rankings share simultaneously the same elements and the same order.

Figure 10 shows the RBO obtained between quality measures and our gold standard, as a function of *s*, the number of representatives considered. To ease the comparison between the datasets, this quantity is expressed as a percentage of the total number of representatives. To improve readability, we only display the results for a selection of 8 quality measures of interest: ACC, COS, EXCEX, GR, MUTINF, SPEC, SUP and ABSSUPDIF. We decide to choose these eight measures because they provide an overall view of all observed behaviors. Full results are available in Appendix C.1. The staircase effect observed for some of the datasets (MUTAG, PTC) is due to the small number of representatives remaining after Step 3 of our process.

<figure><img src="image_11.png" /><figcaption>Fig. 10. RBO between the gold standard and the rankings obtained for the eight quality measure of interest, as a function of s, the number of top representatives considered. For all quality measures, see Appendix C.1.</figcaption></figure>

There is an overall trend: at some point, for all the measures, the RBO starts increasing with *s*, and keeps doing so until reaching the maximal *s* value considered. There seems to be some kind of convergence, for large *s* values. This can be explained by the fact that a greater *s* means more patterns, and therefore more chance to overlap with the gold standard. This results in a larger RBO, even if the patterns are not placed in the same order. Besides this similarity,

Manuscript submitted to ACM
the measures exhibit differences for smaller values of s. One can distinguish three types of behavior. The first one is the most common. It corresponds to measures that start with a zero RBO, before undergoing a regular increase with s (e.g. all the measures in Figure 10a). This means that the top patterns according to these measures are not those of the gold standard, but that they appear farther in the estimated rankings, when considering more patterns. From an operational perspective, these experimental results can help to select an appropriate value for parameter s, depending on the measure of interest. Indeed, the RBO of some measures starts increasing much later than others. For instance, in Figure 10a, SUP starts around 20%, when GR has a zero RBO until almost 50% of the patterns are considered.

The second type of behavior concerns only a few measures. They start strong, then see their RBO decrease, before reaching the increase discussed before (e.g. MUTINF in Figure 10f). Unlike the first type, these measures are good at identifying the top patterns, however they disagree with the gold standard regarding the patterns that come after. The third type of behavior is also followed by a few measures. They start from zero, have a strong increase at first, before undergoing a decrease, followed by the usual increase (e.g. ABSSUPDIF in Figure 10f). These are not good at detecting the top patterns, but manage to match the gold standard on the intermediary ones.

Many measures exhibit the same behavior across all datasets (ACC, COLSTR, GR, SUP...) but this is not truth for all of them. For example, MUTINF follows the first type of behavior on D&D (continuous increase), whereas it follows the second type (increase followed by stagnation) on NCI1. One can also distinguish measures in terms of how quick they approach the gold standard ranking. From this perspective, ABSSUPDIF is particularly efficient on all datasets, and SUP on datasets all but D&D. Alternatively, GR and ACC, the two measures representing the largest block of correlated measures found in Section 6.3, are not particularly close to the ranking obtained by the gold standard, regardless of the dataset.

### 6.4.2 Classification Comparison.
We now compare the measures to the gold standard in terms of classification performance. As before, we select the top *s* representatives identified by each quality measure, but this time we use them to build a representation of the graphs, train the classifier and compute the classification performance. The reference performance is obtained by proceeding similarly with the gold standard. Figure 11 shows the classification performance for each quality measure, expressed in terms of F1-Score, as a function of *s*, the number of representatives selected, expressed as a percentage as before. The dotted line represents the performance obtained using the gold standard ranking. We focus on the same eight measures of interest as before, while the full results are provided in Appendix C.2.

As expected, selecting the best representatives according to the gold standard leads to the fastest increase in F1-Score, for all datasets. This supports our decision to consider SAGE values as a good proxy for a ground truth, regarding pattern ranking. As one would expect, increasing the number of patterns used for classification generally leads to better performance, but it is not always the case. For instance, the F1-Score obtained for NCI1 and D&D quickly starts decreasing when using more than 4% and 13% of the representatives, respectively. And for AIDS and FOPPA, the F1-Score reaches a plateau after using only a fraction of the representatives: increasing *s* further leads to a higher computational cost without any improvement in terms of classification.

We observe two main behaviors among the measures. Some of them undergo a brutal increase in classification performance from the start, which then stays relatively stable when increasing *s* further. A good example is SUP in dataset D&D (Figure 11d). These measures are able to rank the most discriminative patterns first. The second behavior corresponds to a much more progressive increase with *s*. This is illustrated by GR in the same dataset. These measures require considering more patterns in order to capture the same level of discriminative power. Generally speaking, a larger *s* means using more patterns, which results in a higher classification performance for most measures. Indeed, the
<figure><img src="image_12.png" /><figcaption>Fig. 11. F1-Score as a function of the proportion of representatives selected, for each quality measure of interest, as well as the gold standard (dotted line). To visualize all quality measures, see Appendix C.2.</figcaption></figure>

specific ranking produced by a measure only affects which patterns are selected for the classification step. When many or all patterns are selected, this ranking is irrelevant. This explains why all measures end up with the same F1-Score for maximal s, despite possibly very low RBO scores (Figure 10).

The measures that produce rankings correlated to the gold standard, in terms of RBO, also perform well in terms of classification. For example, in the case of dataset D&D, (Figure 11d), ABSSUPDIF, SUP and EXCEX are the best measures both in terms of classification performance and RBO score. However, certain measures also get a good classification performance despite exhibiting only moderate RBO correlation with the gold standard. For instance, for dataset AIDS, (Figure 11e) all the measures except EXCEX and GR reach a comparably good F1-score, despite low RBO scores (Figure 10e).

Measures SUP and ABSSUPDIF are associated with good performances in all datasets and can be considered as safe choices, when no prior knowledge is available. This is due to the fact that ABSSUPDIF possesses the Class Symmetry property. Unlike measures that prioritize one class over the other, it evaluates patterns based on their frequency in both the positive and negative classes. In contrast, the results for GR and ACC are not among the best quality measures. This can be explained by the fact that the measures belonging to the block containing GR correspond to measures that do not respect the *Jumpiness* property. As a result, the patterns selected first only represent a few graphs, which implies that the measure follows the second behavior, synonymous with a slow and gradual increase and therefore a reduced performance. Measures belonging to the ACC block favor patterns that are more frequent in the positive than in the negative class, but neglect patterns with a higher frequency in the negative class. ABSSUPDIF, which considers the most frequent patterns in each of the two classes, obtains better results.
Among all measures, EXCEX produces the least effective rankings. While it possesses the *Contrastivity* property, it fails to satisfy *Jumpiness* and therefore suffers from the same issues as GR: it does not properly differentiate patterns that are exclusively present in the positive class. However, EXCEX presents an additional weakness: it is not directly expressed as a function of $p(G^+ | P)$. This formulation leads to unstable rankings, particularly when patterns have low support. This combination of factors explains why it systematically gives the lowest results in our benchmark.

# 7 CONCLUSION

In this work, we deal with the problem of pattern-based graph classification. We provide a comprehensive review of 38 quality measures proposed in the literature to assess the discriminative power of such patterns. We characterize these measures through four properties that are relevant to our task. We constitute a benchmark of graph datasets and elaborate gold standard rankings of their patterns by leveraging the Shapley value. We use these resources to empirically assess and compare the measures depending on two aspects: the way they rank the patterns, and their effect on classification performance. It turns out ABSSUPDIF and SUP give good results overall, when some measures commonly used in the literature, such as INFGAIN [85], are considerably less relevant. In addition, we propose a preprocessing step based on cluster analysis to decrease the number of patterns used during classification. These clusters are obtained by grouping patterns exhibiting similar footprints, i.e. that are present and absent from the same graphs. Not only does this step allow reducing the graph representation dimension and lowering the computational cost, but it also tends to improve the classification performance. These clusters are also interesting from the perspective of interpretation, as they correspond to groups of patterns that are possibly very different, but are characteristic of the same class. Finally, we also show empirically that restricting pattern mining to specific types of patterns, such as induced or closed ones, also results in a smaller selection of patterns for equal performance.

Our work opens several perspectives. It is limited to the case of balanced classes, so the first extension is straightforward: consider unbalanced classes, which requires handling an extra parameter, the level of imbalance, in order to study its effect. Similarly, our experiments focus on two-class datasets and measures: a second extension is to turn to the multiclass case. This means considering one-vs-all approaches to apply the same measures as in this survey, identifying other measures able to directly handle multiple classes, and finding multiclass datasets. Here too, there is an additional parameter, the number of classes, whose effect must be studied. A third and more indirect extension of our work is to compare the effectiveness of quality measures with methods that directly mine subsets of discriminative patterns, such as CORK [85]. In particular, it would be interesting to study how the patterns identified by such methods are distributed over our gold standard ranking. Fourth and finally, another research lead could be to work directly on the pattern mining method itself. Existing approaches are agnostic, in the sense they are independent of the final task (in our case, classification). As a consequence, they typically work by starting with small patterns and iteratively extending them. It could be interesting to develop a method tailored for classification, that would work on the pattern footprints rather than the patterns themselves.

# REFERENCES

[1] N. Acosta-Mendoza, A. Gago-Alonso, J. A. Carrasco-Ochoa, J. Francisco Martínez-Trinidad, and J. Eladio Medina-Pagola. 2016. Improving graph-based image classification by using emerging patterns as attributes. *Engineering Applications of Artificial Intelligence* 50 (2016), 215–225. https://doi.org/10.1016/j.engappai.2016.01.030

[2] C. C. Aggarwal, M. A. Bhuiyan, and M. A. Hasan. 2014. Frequent Pattern Mining Algorithms: A Survey. In *Frequent Pattern Mining*. Springer, Chapter 2, 19–64. https://doi.org/10.1007/978-3-319-07821-2_2
[3] R. Agrawal, T. Imieliński, and A. Swami. 1993. Mining association rules between sets of items in large databases. *ACM SIGMOD Record* 22, 2 (1993), 207–216. https://doi.org/10.1145/170036.170072

[4] K. Ahn and J. Kim. 2004. Efficient Mining of Frequent Itemsets and a Measure of Interest for Association Rule Mining. *Journal of Information and Knowledge Management* 03, 03 (2004), 245–257. https://doi.org/10.1142/s0219649204000869

[5] M. T. Alam, C. F. Ahmed, M. Samiullah, and C. K. Leung. 2021. Discriminating Frequent Pattern Based Supervised Graph Embedding for Classification. In *25th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (Lecture Notes in Computer Science, Vol. 12713)*. Springer, 16–28. https://doi.org/10.1007/978-3-030-75765-6_2

[6] K. Ali, S. Manganaris, and R. Srikant. 1997. Partial classification using association rules. In *3rd International Conference on Knowledge Discovery and Data Mining*. 115–118. https://dl.acm.org/doi/10.5555/3001392.3001412

[7] A. An and N. Cercone. 1998. ELEM2: A learning system for more accurate classifications. In *Conference of the Canadian Society for Computational Studies of Intelligence (Lecture Notes in Computer Science, Vol. 1418)*. Springer, 426–441. https://doi.org/10.1007/3-540-64575-6_68

[8] A. An and N. Cercone. 1999. An Empirical Study on Rule Quality Measures. In *International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing (Lecture Notes in Computer Science, Vol. 1711)*. Springer, 482–491. https://doi.org/10.1007/978-3-540-48061-7_59

[9] A. An and N. Cercone. 2001. Rule Quality Measures for Rule Induction Systems: Description and Evaluation. *Computational Intelligence* 17, 3 (2001), 409–424. https://doi.org/10.1111/0824-7935.00154

[10] V. Bandyopadhyaya and R. Bandyopadhyaya. 2021. Understanding the Impact of COVID-19 Pandemic Outbreak on Grocery Stocking Behaviour in India: A Pattern Mining Approach. *Global Business Review* 25, 3 (Feb. 2021), 750–770. https://doi.org/10.1177/0972150921988955

[11] M. C. Barbieri, B. I. Grisci, and M. Dorn. 2024. Analysis and comparison of feature selection methods towards performance and stability. *Expert Systems with Applications* 249 (2024), 123667. https://doi.org/10.1016/j.eswa.2024.123667

[12] S. D. Bay and M. J. Pazzani. 1999. Detecting change in categorical data: mining contrast sets. In *5th ACM SIGKDD international conference on Knowledge discovery and data mining*. 302–306. https://doi.org/10.1145/312129.312263

[13] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. 1984. *Classification And Regression Trees*. Routledge. https://doi.org/10.1201/9781315139470

[14] S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. 1997. Dynamic itemset counting and implication rules for market basket data. *ACM SIGMOD Record* 26, 2 (1997), 255–264. https://doi.org/10.1145/253262.253325

[15] C. C. Chang and C. J. Lin. 2011. LIBSVM: a library for support vector machines. *ACM Transactions on Intelligent Systems and Technology* 2, 3 (2011), 1–27. https://doi.org/10.1145/1961189.1961199

[16] Y. Chen, W. Gan, Y. Wu, and P. S. Yu. 2022. Contrast Pattern Mining: A Survey. *arXiv cs.DB* (2022), 2209.13556. https://arxiv.org/abs/2209.13556

[17] M. E. S. Chowdhury, C. F. Ahmed, and C. K. Leung. 2021. A New Approach for Mining Correlated Frequent Subgraphs. *ACM Transactions on Management Information Systems* 13, 1 (2021), 9. https://doi.org/10.1145/3473042

[18] K. W. Church and P. Hanks. 1990. Word association norms, mutual information, and lexicography. *Computational Linguistics* 16, 1 (1990), 22–29. https://aclanthology.org/J90-1003

[19] C. Cortes and V. Vapnik. 1995. Support-vector networks. *Machine Learning* 20, 3 (1995), 273–297. https://doi.org/10.1007/bf00994018

[20] I. Covert, S. M. Lundberg, and S.-I. Lee. 2020. Understanding Global Feature Contributions With Additive Importance Measures. In *34th Conference on Neural Information Processing Systems*. 17212–17223. https://proceedings.neurips.cc/paper_files/paper/2020/hash/c7bf0b7c1a86d5eb3be2c722cf2cf746-Abstract.html

[21] A. S. Debnath, R. L. Lopez, G. Debnath, A. Shusterman, and C. Hansch. 1991. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. *Journal of Medicinal Chemistry* 34, 2 (1991), 786–797. https://doi.org/10.1021/jm00106a046

[22] P. Dhal and C. Azad. 2021. A comprehensive survey on feature selection in the various fields of machine learning. *Applied Intelligence* 52, 4 (2021), 4543–4581. https://doi.org/10.1007/s10489-021-02550-9

[23] P. D. Dobson and A. J. Doig. 2003. Distinguishing Enzyme Structures from Non-enzymes Without Alignments. *Journal of Molecular Biology* 330, 4 (2003), 771–783. https://doi.org/10.1016/s0022-2836(03)00628-4

[24] 2012. *Contrast Data Mining: Concepts, Algorithms, and Applications*. Chapman and Hall/CRC. https://doi.org/10.1201/b12986

[25] G. Dong and J. Li. 1999. Efficient mining of emerging patterns: discovering trends and differences. In *5th ACM SIGKDD international conference on Knowledge discovery and data mining*. 43–52. https://doi.org/10.1145/312129.312191

[26] R. Fagin, R. Kumar, and D. Sivakumar. 2003. Comparing Top k Lists. *SIAM Journal on Discrete Mathematics* 17, 1 (2003), 134–160. https://doi.org/10.1137/s0895480102412856

[27] G. Fang, W. Wang, B. Oatley, B. Van Ness, M. Steinbach, and V. Kumar. 2011. Characterizing Discriminative Patterns. *arXiv cs.DB* (2011), 1102.4104. https://arxiv.org/abs/1102.4104

[28] R. A. Fisher. 1936. The use of multiple measurements in taxonomic problems. *Annals of Eugenics* 7, 2 (1936), 179–188. https://doi.org/10.1111/j.1469-1809.1936.tb02137.x

[29] P. Fournier-Viger, C. Cheng, J. Chun-Wei Lin, U. Yun, and R. U. Kiran. 2019. TKG: Efficient Mining of Top-K Frequent Subgraphs. In *International Conference on Big Data Analytics (Lecture Notes in Computer Science, Vol. 11932)*. Springer, 209–226. https://doi.org/10.1007/978-3-030-37188-3_13

[30] P. Fournier-Viger, J. C. W. Lin, A. Gomariz, T. Gueniche, A. Soltani, Z. Deng, and H. T. Lam. 2016. The SPMF Open-Source Data Mining Library Version 2. In *Joint European Conference on Machine Learning and Knowledge Discovery in Databases (Lecture Notes in Computer Science, Vol. 9853)*. Springer, 36–40. https://doi.org/10.1007/978-3-319-46131-1_8
[31] D. Fryer, I. Strumke, and H. Nguyen. 2021. Shapley Values for Feature Selection: The Good, the Bad, and the Axioms. *IEEE Access* 9 (2021), 144352–144360. https://doi.org/10.1109/access.2021.3119110

[32] A. M. Garcia-Vico, C. J. Carmona, P. Gonzalez, H. Seker, and M. J. Jesus. 2020. FEPSD: A Proposal for the Extraction of Fuzzy Emerging Patterns in Data Streams. *IEEE Transactions on Fuzzy Systems* 28, 12 (2020), 3193–3203. https://doi.org/10.1109/tfuzz.2020.2992849

[33] M. Garcia-Borroto, O. Loyola-Gonzalez, J. F. Martinez-Trinidad, and J. A. Carrasco-Ochoa. 2013. Comparing Quality Measures for Contrast Pattern Classifiers. In *18th Iberoamerican Congress on Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (Lecture Notes in Computer Science, Vol. 8258)*. Springer, 311–318. https://doi.org/10.1007/978-3-642-41822-8_39

[34] M. García-Borroto, J. F. Martínez-Trinidad, J. A. Carrasco-Ochoa, M. A. Medina-Pérez, and J. Ruiz-Shulcloper. 2010. LCMine: An efficient algorithm for mining discriminative regularities and its application in supervised classification. *Pattern Recognition* 43, 9 (2010), 3025–3034. https://doi.org/10.1016/j.patcog.2010.04.008

[35] J. E. Gentle, L. Kaufman, and P. J. Rousseuw. 1991. Finding Groups in Data: An Introduction to Cluster Analysis. *Biometrics* 47, 2 (1991), 788. https://doi.org/10.2307/2532178

[36] R. Gras, S. Ag Almouloud, M. Bailleul, A. Larher, M. Polo, H. Ratsimba-Rajohn, and A. Totohasina. 1996. *L'implication statistique, nouvelle méthode exploratoire de données*. La Pensée Sauvage. https://cir.rii.ac.jp/crid/1130282269046733952

[37] T. Guo and X. Zhu. 2013. Understanding the roles of sub-graph features for graph classification: an empirical study perspective. In *22nd ACM international conference on information and knowledge management*. ACM Press, 817–822. https://doi.org/10.1145/2505515.2505614

[38] B. Güvenoglu and B. E. Bostanoglu. 2018. A qualitative survey on frequent subgraph mining. *Open Computer Science* 8, 1 (2018), 194–209. https://doi.org/10.1515/comp-2018-0018

[39] Z. Harchaoui and F. Bach. 2007. Image Classification with Segmentation Graph Kernels. In *IEEE Conference on Computer Vision and Pattern Recognition*. 1–8. https://doi.org/10.1109/cvpr.2007.383049

[40] B. Harris. 1966. The Estimation of Probabilities: An Essay on Modern Bayesian Methods (I. J. Good). *SIAM Rev.* 8, 1 (1966), 118–119. https://doi.org/10.1137/1008024

[41] C. He, X. Chen, G. Chen, W. Gan, and P.Ô Fournier-Viger. 2024. Mining credible attribute rules in dynamic attributed graphs. *Expert Systems with Applications* 246 (2024), 123012. https://doi.org/10.1016/j.eswa.2023.123012

[42] A. Hellal and L. Ben Romdhane. 2016. Minimal contrast frequent pattern mining for malware detection. *Computers & Security* 62 (2016), 19–32. https://doi.org/10.1016/j.cose.2016.06.004

[43] J. Huan, W. Wang, and J. Prins. 2003. Efficient mining of frequent subgraphs in the presence of isomorphism. In *3rd IEEE International Conference on Data Mining*. https://doi.org/10.1109/icdm.2003.1250974

[44] C. Jiang, F. Coenen, and M. Zito. 2012. A survey of frequent subgraph mining algorithms. *The Knowledge Engineering Review* 28, 1 (2012), 75–105. https://doi.org/10.1017/s0269888912000331

[45] H. Jippo, T. Matsuo, R. Kikuchi, D. Fukuda, A. Matsuura, and M. Ohfuchi. 2019. Graph Classification of Molecules Using Force Field Atom and Bond Types. *Molecular Informatics* 39, 1-2 (2019), 1800155. https://doi.org/10.1002/minf.201800155

[46] A. Jüttner and P. Madarasi. 2018. VF2++ An improved subgraph isomorphism algorithm. *Discrete Applied Mathematics* 242 (2018), 69–81. https://doi.org/10.1016/j.dam.2018.02.018

[47] H. J. Kang and D. Lo. 2022. Active Learning of Discriminative Subgraph Patterns for API Misuse Detection. *IEEE Transactions on Software Engineering* 48, 8 (2022), 2761–2783. https://doi.org/10.1109/tse.2021.3069978

[48] F. Karbalaie, A. Sami, and M. Ahmadi. 2012. Semantic malware detection by deploying graph mining. *International Journal of Computer Science Issues* 9, 1 (2012), 373. https://www.researchgate.net/publication/257351721

[49] H. Kashima, K. Tsuda, and A. H. Inokuchi. 2003. Marginalized kernels between labeled graphs. In *20th international conference on machine learning*. 321–328. https://cdn.aaai.org/ICML/2003/ICML03-044.pdf

[50] M. G. Kendall. 1938. A new measure of rank correlation. *Biometrika* 30, 1-2 (1938), 81–93. https://doi.org/10.1093/biomet/30.1.2.81

[51] A. Kikaj, G. Marra, and L. De Raedt. 2024. Subgraph Mining for Graph Neural Networks. In *International Symposium on Intelligent Data Analysis (Lecture Notes in Computer Science, Vol. 14641)*. Springer, 141–152. https://doi.org/10.1007/978-3-031-58547-0_12

[52] W. Klösgen. 1996. *Explora: a multipattern and multistrategy discovery assistant*. American Association for Artificial Intelligence, 249–271. https://dl.acm.org/doi/10.5555/257938.257965

[53] Y. Kodratoff. 2001. Comparing Machine Learning and Knowledge Discovery in DataBases: An Application to Knowledge Discovery in Texts. In *Machine Learning and Its Applications: Advanced Lectures*. Lecture Notes in Computer Science, Vol. 2049. Springer, 1–21. https://doi.org/10.1007/3-540-44673-7_1

[54] N. M. Kriege, P. L. Giscard, and R. Wilson. 2016. On Valid Optimal Assignment Kernels and Applications to Graph Classification. In *30th International Conference on Neural Information Processing Systems*. 1623–1631. https://proceedings.neurips.cc/paper_files/paper/2016/hash/0efe32849d230d7f53049ddc4a4b0c60-Abstract.html

[55] N. M. Kriege, F. D. Johansson, and C. Morris. 2020. A survey on graph kernels. *Applied Network Science* 5 (2020), 6. https://doi.org/10.1007/s41109-019-0195-3

[56] I. Kumar, C. Scheidegger, S. Venkatasubramanian, and S. Friedler. 2021. Shapley Residuals: Quantifying the limits of the Shapley value for explanations. In *Advances in Neural Information Processing Systems*, Vol. 34. 26598–26608. https://proceedings.neurips.cc/paper_files/paper/2021/file/dfc6aa246e88ab3e32caeaecf433550-Paper.pdf
[57] N. Lavrač, P. Flach, and B. Zupan. 1999. Rule Evaluation Measures: A Unifying View. In *International Conference on Inductive Logic Programming (Lecture Notes in Computer Science, Vol. 1634)*. Springer, 174–185. https://doi.org/10.1007/3-540-48751-4_17

[58] N. Lavrač, B. Kavšek, P. Flach, and L. Todorovski. 2004. Subgroup Discovery with CN2-SD. *Journal of Machine Learning Research* 5 (2004), 153–188. https://www.jmlr.org/papers/v5/lavrac04a.html

[59] P. Lenca, P. Vaillant, B. and Meyer, and S. Lallich. 2007. Association Rule Interestingness Measures: Experimental and Theoretical Studies. In *Quality Measures in Data Mining*. Studies in Computational Intelligence, Vol. 43. Springer, 51–76. https://doi.org/10.1007/978-3-540-44918-8_3

[60] J. Li, G. Dong, and K. Ramamohanarao. 2000. Making Use of the Most Expressive Jumping Emerging Patterns for Classification. In *4th Pacific-Asia Conference on Knowledge Discovery and Data Mining (Lecture Notes in Computer Science, Vol. 1805)*. Springer, 220–232. https://doi.org/10.1007/3-540-45571-x_29

[61] P. Li, Y. Xie, X. Xu, J. Zhou, and Q. Xuan. 2022. Phishing Fraud Detection on Ethereum Using Graph Neural Network. In *4th International Conference on Blockchain and Trustworthy Systems (Communications in Computer and Information Science, Vol. 1679)*. Springer, 362–375. https://doi.org/10.1007/978-981-19-8043-5_26

[62] O. Loyola-González, M. A. Medina-Pérez, and K. R. Choo. 2020. A Review of Supervised Classification based on Contrast Patterns: Applications, Trends, and Challenges. *Journal of Grid Computing* 18, 4 (2020), 797–845. https://doi.org/10.1007/s10723-020-09526-y

[63] O. Loyola-González, M. García-Borroto, J. F. Martínez-Trinidad, and J. A. Carrasco-Ochoa. 2014. An empirical comparison among quality measures for pattern based classifiers. *Intelligent Data Analysis* 18, 6S (2014), S5–S17. https://doi.org/10.3233/ida-140705

[64] S. M. Lundberg, G. Erion, H. Chen, A. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S. Lee. 2020. From local explanations to global understanding with explainable AI for trees. *Nature Machine Intelligence* 2 (2020), 56–67. https://doi.org/10.1038/s42256-019-0138-9

[65] S. M. Lundberg and S. Lee. 2017. A Unified Approach to Interpreting Model Predictions. In *31st International Conference on Neural Information Processing Systems*. 4768–4777. https://doi.org/10.5555/3295222.3295230

[66] R. Mathonat, D; Nurbakova, J. F. Boulicaut, and M. Kaytoue. 2020. Anytime mining of sequential discriminative patterns in labeled sequences. *Knowledge and Information Systems* 63, 2 (Nov. 2020), 439–476. https://doi.org/10.1007/s10115-020-01523-7

[67] G. Mélançon. 2006. Just how dense are dense graphs in the real world?: a methodological note. In *AVI Workshop on Beyond time and errors: novel evaluation methods for information visualization*. 1–7. https://doi.org/10.1145/1168149.1168167

[68] D. Q. Nguyen, T. D. Nguyen, and D. Phung. 2022. Universal Graph Transformer Self-Attention Networks. In *Companion Proceedings of the Web Conference*. 193–196. https://doi.org/10.1145/3487553.3524258

[69] F. Orsini, P. Frasconi, and L. De Raedt. 2015. Graph invariant kernels. In *24th International Conference on Artificial Intelligence*. 3756–3762. https://doi.org/10.5555/2832747.2832773

[70] K. Pearson. 1896. Mathematical Contributions to the Theory of Evolution. III. Regression, Heredity, and Panmixia. *Philosophical Transactions of the Royal Society A* 187 (1896), 253–318. https://doi.org/10.1098/rsta.1896.0007

[71] G. Piatetsky-Shapiro. 1991. Discovery, analysis and presentation of strong rules. In *Knowledge Discovery in Databases*. AAAI Press, Chapter 13, 229–248. https://mitpress.mit.edu/9780262660709/knowledge-discovery-in-databases/

[72] G. Piatetsky-Shapiro and S. Steingold. 2000. Measuring lift quality in database marketing. *ACM SIGKDD Explorations Newsletter* 2, 2 (2000), 76–80. https://doi.org/10.1145/380995.381018

[73] L. Potin, R. Figueiredo, V. Labatut, and C. Largeron. 2023. Pattern Mining for Anomaly Detection in Graphs: Application to Fraud in Public Procurement. In *European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (Lecture Notes in Computer Science, Vol. 14174)*. 69–87. https://doi.org/10.1007/978-3-031-43427-3_5

[74] Sokal R. R. and C. D. Michener. 1958. A statistical method for evaluating systematic relationships. *University of Kansas science bulletin* 38 (1958), 1409–1438. http://www.citeulike.org/user/BioNica/article/5845721

[75] K. Ramamohanarao and H. Fan. 2007. Patterns Based Classifiers. *World Wide Web* 10, 1 (2007), 71–83. https://doi.org/10.1007/s11280-006-0012-7

[76] B. Rieck, C. Bock, and K. Borgwardt. 2019. A Persistent Weisfeiler-Lehman Procedure for Graph Classification. In *36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97)*. 5448–5458. https://proceedings.mlr.press/v97/rieck19a.html

[77] H. Riesen, Kand Bunke. 2008. IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning. In *Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition and Structural and Syntactic Pattern Recognition (Lecture Notes in Computer Science, Vol. 5342)*. Springer, 287–297. https://doi.org/10.1007/978-3-540-89689-0_33

[78] F. Rousseau, E. Kiagias, and M. Vazirgiannis. 2015. Text Categorization as a Graph Classification Problem. In *53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing*. 1702–1712. https://doi.org/10.3115/v1/p15-1164

[79] Ahmet Erdem Sariyüce and Ali Pinar. 2018. Peeling Bipartite Networks for Dense Subgraph Discovery. In *11 ACM International Conference on Web Search and Data Mining*. 504–512. https://doi.org/10.1145/3159652.3159678

[80] M Sebag and M Schoenauer. 1988. Generation of rules with certainty and confidence factors from incomplete and incoherent learning bases. In *European Knowledge Acquisition Workshop*, Vol. 88, 28. https://publica.fraunhofer.de/entities/event/b65b8403-dcf9-4edd-9ccd-2b066d3b6608/details

[81] C. E. Shannon. 1948. A Mathematical Theory of Communication. *Bell System Technical Journal* 27, 3 (1948), 379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

[82] L. S. Shapley. 1953. A Value for n-Person Games. In *Contributions to the Theory of Games*. Annals of Mathematics Studies, Vol. 28. Princeton University Press, Chapter 17, 307–318. https://doi.org/10.1515/9781400881970-018
[83] P. N. Tan, V. Kumar, and J. Srivastava. 2004. Selecting the right objective measure for association analysis. *Information Systems* 29, 4 (2004), 293-313.
https://doi.org/10.1016/s0306-4379(03)00072-3

[84] D. Theng and K. K. Bhoyar. 2023. Feature selection techniques for machine learning: A survey of more than two decades of research. *Knowledge and Information Systems* 66, 3 (2023), 1575-1637. https://doi.org/10.1007/s10115-023-02010-5

[85] M. Thoma, H. Cheng, A. Gretton, J. Han, H. Kriegel, and A. Smola. 2009. Near-optimal supervised feature selection among frequent subgraphs. In *SIAM International Conference on Data Mining*. 1076-1087. https://doi.org/10.1137/1.9781611972795.92

[86] M. Thoma, H. Cheng, A. Gretton, J. Han, H. P. Kriegel, A. Smola, L. Song, P. S. Yu, S. Yan, and K. M. Borgwardt. 2010. Discriminative frequent subgraph mining with optimality guarantees. *Statistical Analysis and Data Mining* 3, 5 (2010), 302-318. https://doi.org/10.1002/sam.10084

[87] R. M. H. Ting and J. Bailey. 2006. Mining Minimal Contrast Subgraph Patterns. In *SIAM International Conference on Data Mining*. 639-643. https://doi.org/10.1137/1.9781611972764.76

[88] H. Toivonen, A. Srinivasan, R. D. King, S. Kramer, and C. Helma. 2003. Statistical evaluation of the Predictive Toxicology Challenge 2000-2001. *Bioinformatics* 19, 10 (2003), 1183-1193. https://doi.org/10.1093/bioinformatics/btg130

[89] K. Tsuda and H. Saigo. 2010. Graph Classification. In *Managing and Mining Graph Data*. Advances in Database Systems, Vol. 40. Springer, 337-363. https://doi.org/10.1007/978-1-4419-6045-0_11

[90] C. J. van Rijsbergen. 1979. *Information Retrieval*. Butterworths. https://doi.org/10.1002/asi.4630300621

[91] S. Ventura and J. M. Luna. 2016. *Quality Measures in Pattern Mining*. Springer, 27-44. https://doi.org/10.1007/978-3-319-33858-3_2

[92] L. Veyrin-Forrer, A. Kamal, S. Duffner, M. Plantevit, and C. Robardet. 2022. In pursuit of the hidden features of GNN's internal representations. *Data & Knowledge Engineering* 142 (2022), 102097. https://doi.org/10.1016/j.datak.2022.102097

[93] N. Wale and G. Karypis. 2006. Comparison of Descriptor Spaces for Chemical Compound Retrieval and Classification. In *6th International Conference on Data Mining*. 678-689. https://doi.org/10.1109/icdm.2006.39

[94] G. I. Webb and S. Zhang. 2005. K-Optimal Rule Discovery. *Data Mining and Knowledge Discovery* 10, 1 (2005), 39-79. https://doi.org/10.1007/s10618-005-0255-4

[95] W. Webber, A. Moffat, and J. Zobel. 2010. A similarity measure for indefinite rankings. *ACM Transactions on Information Systems* 28, 4 (2010), 1-38. https://doi.org/10.1145/1852102.1852106

[96] B. Wu, Y. Liu, B. Lang, and L. Huang. 2018. DGCNN: Disordered graph convolutional neural network based on the Gaussian mixture model. *Neurocomputing* 321 (2018), 346-356. https://doi.org/10.1016/j.neucom.2018.09.008

[97] D. Wu, Q. Wang, and D. L. Olson. 2023. Industry classification based on supply chain network information using Graph Neural Networks. *Applied Soft Computing* 132 (2023), 109849. https://doi.org/10.1016/j.asoc.2022.109849

[98] J. Wu, S. Pan, X. Zhu, and Z. Cai. 2015. Boosting for Multi-Graph Classification. *IEEE Transactions on Cybernetics* 45, 3 (2015), 416-429. https://doi.org/10.1109/tycyb.2014.2327111

[99] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks. *IEEE Transactions on Neural Networks and Learning Systems* 32, 1 (2021), 4-24. https://doi.org/10.1109/tnnls.2020.2978386

[100] X. Yan and J. Han. 2002. gSpan: graph-based substructure pattern mining. In *IEEE International Conference on Data Mining*. 721-724. https://doi.org/10.1109/ICDM.2002.1184038

[101] P. Yanardag and S.V.N. Vishwanathan. 2015. Deep Graph Kernels. In *21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*. 1365-1374. https://doi.org/10.1145/2783258.2783417

[102] Y. Yang and T. O. Pedersen. 1997. A Comparative Study on Feature Selection in Text Categorization. In *14th International Conference on Machine Learning*. 412-420. https://doi.org/10.5555/645526.657137

[103] X. Yin and J. Han. 2003. CPAR: Classification based on Predictive Association Rules. In *SIAM International Conference on Data Mining*. 331-335. https://doi.org/10.1137/1.9781611972733.40

[104] C. Zhang and S. Zhang. 2002. *Association Rule Mining: Models and Algorithms*. Lecture Notes in Computer Science, Vol. 2307. Springer. https://doi.org/10.1007/3-540-46027-6

[105] S. Zhang and X. Wu. 2011. Fundamentals of association rules in data mining and knowledge discovery. *WIREs Data Mining and Knowledge Discovery* 1, 2 (2011), 97-116. https://doi.org/10.1002/widm.10

[106] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. 2020. Graph neural networks: A review of methods and applications. *AI Open* 1 (2020), 57-81. https://doi.org/10.1016/j.aiopen.2021.01.001

# A ADDITIONAL INFORMATION ABOUT QUALITY MEASURES

This appendix contains additional information related to the quality measures and their properties.

## A.1 Excluded Quality Measures

As explained in Section 4, we discarded three quality measures of the literature [16] from our experiments. The first one, GENQUOTIENT, requires the user to set a specific parameter value. The second, SUPMAXK, is designed for itemsets,
and cannot handle graphs natively. It could be possible to adapt it to this use case, but this is out of the scope of this paper. The third measure, PVALUE, is unsuitable to large datasets due to its computational cost.

<table><caption>Table 6. Name and formula of the three quality measures that appear in the literature [16], but that we discarded from our experiments.</caption><thead><tr><th>Quality Measure</th><th>Definition</th></tr></thead><tbody><tr><td>GEN QUOTIENT</td><td><div style="text-align: center;"><span style="display: inline-block; border-bottom: 1px solid black; padding-bottom: 1px;">p(P|G<sup>+</sup>)</span><span style="display: inline-block; padding-top: 1px;">p(P|G<sup>+</sup>)+g</span></div></td></tr><tr><td>SUPMAXK</td><td>p(P | G<sup>+</sup>) - max<sub>P<sub>i</sub> &isin; P</sub> p(P<sub>i</sub> | G<sup>-</sup>)</td></tr><tr><td>PVALUE</td><td><div style="text-align: center;"><span style="display: inline-block; border-bottom: 1px solid black; padding-bottom: 1px;">&sum;<sub>i=0</sub><sup>max(n<sub>12</sub>,n<sub>21</sub>)</sup> <span style="display: inline-block; padding-top: 1px;">t<sub>1</sub>!t<sub>2</sub>!|G<sup>+</sup>|!|G<sup>-</sup>|!</span></span><span style="display: inline-block; padding-top: 1px;">|G|!(n<sub>11</sub>+i)!(n<sub>12</sub>-i)!(n<sub>21</sub>-i)!(n<sub>22</sub>+i)|!</span></div></td></tr></tbody></table>

Table 6 provides their definitions, for the sake of completeness. In order to enhance the readability of the PVALUE formula, we note $n_{11}$ the support of P in $G^+$, $n_{12}$ the support of P in $G^-$, $n_{21}$ the support of $\bar{P}$ in $G^+$ and $n_{22}$ the support of $\bar{P}$ in $G^-$

## A.2 Balanced Classes and Independence / Equilibrium

As mentioned in Section 4.2, here is the proof that the properties of *Independence* and *Equilibrium* defined by Loyola-González et al. [63] are equivalent under the assumption that the considered classes are balanced.

*PROOF.* As explained in Section 4, *Independence* is defined as $p(P, G^+) = p(P)p(G^+)$, whereas *Equilibrium* is defined as $p(G^+ | P) = p(G^- | P)$. We want to show that, under the assumption that both classes have the same size, i.e. $|G^+| = |G^-|$, both properties are equivalent.

We first focus on proving *Independence* ⇒ *Equilibrium*. Starting with the definition of conditional probability applied to the positive class, we have

$$p(G^+ | P) = \frac{p(P, G^+)}{p(P)} \qquad (7)$$

Assuming independance yields

$$p(G^+ | P) = \frac{p(P)p(G^+)}{p(P)} \qquad (8)$$

$$= p(G^+) \qquad (9)$$

We use the definition of conditional probability on the negative class

$$p(G^- | P) = \frac{p(P, G^-)}{p(P)} \qquad (10)$$

Using the law of total probability, we have $p(P, G^+) + p(P, G^-) = p(P)$, and therefore

$$p(G^- | P) = \frac{p(P) - p(P, G^+)}{p(P)} \qquad (11)$$

$$p(G^- | P) = \frac{p(P) - p(P)p(G^+)}{p(P)} \qquad (12)$$

$$= 1 - p(G^+) \qquad (13)$$
Now, if $|\mathcal{G}^+| = |\mathcal{G}^-|$, then $p(\mathcal{G}^+) = 0.5$. Consequently,

$$p(\mathcal{G}^+ | P) = p(\mathcal{G}^- | P) = 0.5, \qquad (14)$$

and the *Equilibrium* property is verified.

We now turn to proving *Equilibrium* ⇒ *Independence*. On the one hand, the *Equilibrium* property states

$$p(\mathcal{G}^+ | P) = p(\mathcal{G}^- | P). \qquad (15)$$

On the other hand, we have

$$p(\mathcal{G}^+ | P) + p(\mathcal{G}^- | P) = 1. \qquad (16)$$

Combining (15) and (16) yields $p(\mathcal{G}^+ | P) = p(\mathcal{G}^- | P) = 0.5$. In addition, as shown before, $p(\mathcal{G}^+) = 0.5$, thus

$$p(P, \mathcal{G}^+) = p(\mathcal{G}^+ | P)p(P) \qquad (17)$$

$$= 0.5 \cdot p(P) \qquad (18)$$

$$= p(\mathcal{G}^+)p(P), \qquad (19)$$

and the *Independence* property is verified. □

## A.3 Additional Properties

Ventura and Luna [91] list seven properties defined to characterize quality measures in the context of association rule mining. The rules have the form $X \to Y$, where X and Y are itemsets. If we assume instead that X denotes the presence of a graph pattern P, and that Y denotes our positive class $\mathcal{G}^+$, then these rules can be considered as classification rules, and the properties can be applied to characterize the quality measures listed in Section 4.1. In the following, we first consider the three properties by Piatetsky-Shapiro [71] (Appendix A.3.1), then the four properties by Tan et al. [83] (Appendix A.3.2).

### A.3.1 Properties of Piatetsky-Shapiro.
We note PS1 the first property of Piatetsky-Shapiro [71]. It is defined as follows:

*Definition A.1 (PS1).* Let X and Y be two itemsets with no item in common. Quality measure q possesses Property 1 of Piatetsky-Shapiro [71] iff

$$q(X \to Y) = 0 \text{ when } p(X, Y) = p(X)p(Y).$$

In other words, the measure is zero when X and Y are independent. If we translate in terms of patterns and classes, we get $p(P, \mathcal{G}^+) = p(P)p(\mathcal{G}^+)$. This is equivalent to the *Independence* property of Loyola-González et al. [63], as described in Section 4.2.

The second property of Piatetsky-Shapiro [71], which we note PS2, is defined as:

*Definition A.2 (PS2).* Let X and Y be two itemsets with no item in common. Quality measure q possesses Property 2 of Piatetsky-Shapiro [71] iff

$$q(X \to Y) \text{ monotonically increases with } p(X, Y) \text{ when } p(X) \text{ and } p(Y) \text{ remain the same.}$$

In our case, for a given dataset, the classes are fixed and only the patterns can exhibit different distributions over the graphs. Therefore, $p(\mathcal{G}^+)$ (the counterpart of $p(Y)$) is constant, and only $p(P)$ (the counterpart of $p(X)$) can vary. If we translate the property in terms of patterns and classes, under a form comparable to our own properties from Section 4.2,
then we get

$$ \forall P_i, P_j, [p(P_i, \mathcal{G}^+) > p(P_j, \mathcal{G}^+) \text{ and } p(P_i) = p(P_j)] \Rightarrow [q(P_i, \mathcal{G}^+, \mathcal{G}^-) > q(P_j, \mathcal{G}^+, \mathcal{G}^-)]. \quad (20) $$

This property is very similar to our *Contrastivity* property from Section 4.2, with the difference that here we assume $p(P_i, \mathcal{G}^+) > p(P_j, \mathcal{G}^+)$ instead of $p(P_i, \mathcal{G}^+) = p(P_j, \mathcal{G}^+)$. Intuitively, the *Contrastivity* states that the quality measure must increase when one *deletes* a pattern occurrence from the negative class, whereas SP2 states that it must increase when one *switches* a pattern occurrence from the negative to the positive class.

Importantly, PS2 is mutually exclusive with *Class Symmetry* (cf. Section 4.2), i.e. a measure cannot simultaneously possess both properties. We provide a proof in Appendix A.4). In addition, a quality measure which verifies neither PS2 nor *Class Symmetry* is not particularly effective: it is not able to identify patterns that are very frequent in either the positive or the negative class. As a result, it is not necessary to consider both measures when describing quality measures. In this work, we focus on the *Class symmetry*.

The third property of Piatetsky-Shapiro [71], which we note PS3, is defined as:

*Definition A.3 (PS3).* Let X and Y be two itemsets with no item in common. Quality measure q possesses Property 3 of Piatetsky-Shapiro [71] iff

$q(X \to Y)$ monotonically decreases with $p(X)$ or with $p(Y)$ when $p(X, Y)$ and $p(Y)$ or $p(X)$ remain the same.

Same as before, in our case $p(Y)$ cannot change. If we translate this property in terms of patterns and classes, we get

$$ \forall P_i, P_j, [p(P_i) > p(P_j) \text{ and } p(P_i, \mathcal{G}^+) = p(P_j, \mathcal{G}^+)] \Rightarrow [q(P_i, \mathcal{G}^+, \mathcal{G}^-) < q(P_j, \mathcal{G}^+, \mathcal{G}^-)]. \quad (21) $$

If $P_i$ is more frequent than $P_j$ while they are equally frequent in $\mathcal{G}^+$, then $P_i$ is more frequent than $P_j$ in $\mathcal{G}^-$. Consequently, the property can be rewritten as

$$ \forall P_i, P_j, [p(P_i, \mathcal{G}^-) > p(P_j, \mathcal{G}^-) \text{ and } p(P_i, \mathcal{G}^+) = p(P_j, \mathcal{G}^+)] \Rightarrow [q(P_i, \mathcal{G}^+, \mathcal{G}^-) < q(P_j, \mathcal{G}^+, \mathcal{G}^-)]. \quad (22) $$

In the end, this property is equivalent to our *Contrastivity* property from Section 4.2.

### A.3.2 Properties of Tan et al.
The first property of Tan et al. [83] is related to the symmetry under variable permutation. We note it T1, and it is defined as

*Definition A.4 (T1).* Let X and Y be two itemsets with no item in common. Quality measure q is symmetric under variable permutation iff

$$ q(X \to Y) = q(Y \to X). $$

In our situation, this property does not apply since we focus only on classification rules, i.e. rules of the form $X \to Y$ (where X corresponds to a pattern and Y to a class). Thus, variable permutation is irrelevant.

The second property of Tan et al. [83] is related to the notion of antisymmetry in the following matrix, called *Table of relative frequencies* in [91]:

$$ \begin{bmatrix} p(X, Y) & p(X, \bar{Y}) \\ p(\bar{X}, Y) & p(\bar{X}, \bar{Y}) \end{bmatrix}. \quad (23) $$

This antisymmetry property has two variants. The first focuses on the rows of this matrix:

*Definition A.5 (T2a).* Let X and Y be two itemsets with no item in common. Quality measure q is antisymmetric under row permutation iff
$$q(\bar{X} \to Y) = -q(X \to Y).$$

If we translate to patterns and classes, we get

$$q(\bar{P}, \mathcal{G}^{+}, \mathcal{G}^{-}) = -q(P, \mathcal{G}^{+}, \mathcal{G}^{-}). \qquad (24)$$

This property is similar to our *Pattern Symmetry* property from Section 4.2, with the difference of the minus sign in the right-hand term.

The second variant of this second property focuses on the *columns* of the matrix:

**Definition A.6 (T2b).** Let X and Y be two itemsets with no item in common. Quality measure q is antisymmetric under column permutation iff

$$q(X \to \bar{Y}) = -q(X \to Y).$$

If we translate to patterns and classes, we get

$$q(P, \mathcal{G}^{-}, \mathcal{G}^{+}) = -q(P, \mathcal{G}^{+}, \mathcal{G}^{-}). \qquad (25)$$

This property is similar to our *Class Symmetry* property from Section 4.2, but like before, it differs in the minus sign present in the right-hand term.

The third property of Tan et al. [83] considers both types of permutations:

**Definition A.7 (T3).** Let X and Y be two itemsets with no item in common. Quality measure q is symmetric under simultaneous row and column permutations iff

$$q(\bar{X} \to \bar{Y}) = q(X \to Y).$$

If we translate to patterns and classes, we get

$$q(\bar{P}, \mathcal{G}^{-}, \mathcal{G}^{+}) = q(P, \mathcal{G}^{+}, \mathcal{G}^{-}). \qquad (26)$$

Note that this is not equivalent to possessing both T2a and T2b. For instance, in our selected measures, Acc does not respect T2a nor T2b, but it possesses T3.

Finally, the fourth property of Tan et al. [83], which we note T4, is called *Null-Invariance*. It concerns measures that do not vary when considering a new dataset with more records not containing X and Y. This property requires breaking class balance, so it is not relevant to our case.

## A.4 Mutual Exclusivity Between PS2 and Class Symmetry

As mentioned in Appendix A.3.1, here is the proof that property PS2 of Piatetsky-Shapiro [71] (cf. Appendix A.3.1) and *Class Symmetry* (cf. Section 4.2) are mutually exclusive.

**PROOF.** As mentioned in Appendix A.3.1 (20), property PS2 is defined as

$$\forall P_i, P_j, [p(P_i, \mathcal{G}^{+}) > p(P_j, \mathcal{G}^{+}) \text{ and } p(P_i) = p(P_j)] \Rightarrow [q(P_i, \mathcal{G}^{+}, \mathcal{G}^{-}) > q(P_j, \mathcal{G}^{+}, \mathcal{G}^{-})]. \qquad (27)$$

Moreover, *Class Symmetry* is defined as: $\forall P, q(P, \mathcal{G}^{+}, \mathcal{G}^{-}) = q(P, \mathcal{G}^{-}, \mathcal{G}^{+})$ (Definition 4.3). We reformulate this property under a more convenient form by using two distinct but class-symmetrical patterns $P_i$ and $P_j$:

$$\forall P_i, P_j, [p(P_i, \mathcal{G}^{+}) = p(P_j, \mathcal{G}^{-}) \text{ and } [p(P_i, \mathcal{G}^{-}) = p(P_j, \mathcal{G}^{+})] \Rightarrow [q(P_i, \mathcal{G}^{+}, \mathcal{G}^{-}) = q(P_j, \mathcal{G}^{+}, \mathcal{G}^{-})]. \qquad (28)$$
In the rest of our proof, we use two such class-symmetric patterns $P_1$ and $P_2$ defined as follows

$$ \mathrm{support}(P_1, \mathcal{G}^+) = \mathrm{support}(P_2, \mathcal{G}^-) = x \qquad (29) $$

$$ \mathrm{support}(P_1, \mathcal{G}^-) = \mathrm{support}(P_2, \mathcal{G}^+) = y, \qquad (30) $$

where $x > y$.

First, we show that if $q$ verifies PS2, then it is not class-symmetric, i.e. PS2 $\Rightarrow \neg$ Class Symmetry. Let us assume that $q$ is a quality measure satisfying P2. Using (29) and (30), we have

$$ p(P_1, \mathcal{G}^+) > p(P_2, \mathcal{G}^+) \qquad (31) $$

$$ p(P_1) = P(P_2) = (x + y)/|\mathcal{G}|. \qquad (32) $$

Consequently, according to PS2,

$$ q(P_i, \mathcal{G}^+, \mathcal{G}^-) > q(P_j, \mathcal{G}^+, \mathcal{G}^-). \qquad (33) $$

The antecedent of (28) is true for $P_1$ and $P_2$, but not its consequent. As a result, measure $q$ is not class-symmetric.

Second, we turn to showing Class Symmetry $\Rightarrow \neg$P2. Let us assume that $q$ is a quality measure that satisfies the Class Symmetry property. Then, given (29) and (30), we get

$$ q(P_1, \mathcal{G}^+, \mathcal{G}^-) = q(P_2, \mathcal{G}^+, \mathcal{G}^-). \qquad (34) $$

The antecedent of P2 is true for $P_1$ and $P_2$, but not its consequent. Therefore, $q$ does not possess the PS2 property. □

# B ADDITIONAL RESULTS REGARDING MEASURE COMPARISON

This appendix contains additional results related to the comparison of measures through their rankings, using Kendall's Tau.

## B.1 Separated Distribution Plots

Figures 12 (datasets MUTAG, PTC, and NCI1) and 13 (datasets D&D, AIDS, and FOPPA) represent the distribution of Kendall's Tau obtained for each dataset when comparing all 38 pairs of quality measures. They display the same information as Figure 7 from Section 6.2.2, except that each considered value of the clustering threshold (0, 20, 40 and 60 %) is shown as a separate plot, instead of putting them all in the same plot.

## B.2 Dataset Correlation Matrices

Figure 14 represents Kendall's Tau computed for each pair of the 38 quality measures. The differences with Figure 6.3 from Section 9 is that instead of showing the minimal correlation value over all datasets, this figure contains a distinct plot for each dataset.

# C ADDITIONAL RESULTS RELATED TO GOLD STANDARD COMPARISON

This appendix provides plots comparing all measures to the gold standard, in terms of ranking correlation (Appendix C.1) and classification performance (Appendix C.2). By comparison, the plots provided in the main article only focus on eight of these measures, for the sake of concision.
<figure><img src="image_13.png" /><figcaption>Fig. 12. Distribution of Kendall's Tau coefficient computed over all pairs of quality measure, for datasets MUTAG, PTC, and NCI1. Each row correspond to a different clustering threshold. The rest of the datasets are shown in Figure 13. The top row of Figure 7 from the main paper shows a column-wise collapsed version of these plots.</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Fig. 13. Distribution of Kendall's Tau coefficient computed over all pairs of quality measure, for datasets D&D, AIDS, and FOPPA. Each row correspond to a different clustering threshold. The rest of the datasets are shown in Figure 12. The bottom row of Figure 7 from the main paper shows a column-wise collapsed version of these plots.</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Fig. 14. Kendall's Tau for each pair of quality measures, shown separately for each dataset. Note that the color scale is not fixed over the plots, to improve contrast.</figcaption></figure>

## C.1 Ranking Comparison

Figures 15 and 16 show the RBO obtained between each measure and our gold standard, as a function of *s*, the number of representatives considered. These figures are extensions of Figure 10, this time displaying the full set of 38 quality measures.

## C.2 Classification Comparison

Figures 15 and 16 show the F1-Score obtained for each measure as well as our gold standard, as a function of *s*, the number of representatives considered. These figures are extensions of Figure 11, this time displaying all 38 quality measures.

# D ADDITIONAL RESULTS FOR TWO DATASETS

This appendix shows results obtained for two datasets that are not shown in the main paper, for the sake of concision: FRANK (Appendix D.1) and IMDb (Appendix D.2).

## D.1 FRANK Results

The results obtained for the FRANK dataset are not presented in the main article due to their similarity with D&D. Figure 19a and 19b correspond to the experiments from Section 6.2. Figure 19c shows Kendall's Tau correlation matrix, as in Section 6.3. Figures 19d, 19e, and 19f show comparisons with the gold standard in terms of RBO, similarly to
<figure><img src="image_16.png" /><figcaption>Fig. 15. RBO between the rankings obtained for each selected quality measure and the gold standard, as a function of s, the number of top representatives considered for datasets MUTAG, PTC and NCI1. The rest of the datasets are shown in Figure 16.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Fig. 16. RBO between the rankings obtained for each selected quality measure and the gold standard, as a function of s, the number of top representatives considered for datasets D&D, AIDS and FOPPA. The rest of the datasets are shown in Figure 15.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Fig. 17. F1-Score as a function of the proportion of representatives selected for each quality measure and gold standard for datasets MUTAG, PTC and NCI1. The rest of the datasets are shown in Figure 18)</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>Fig. 18. F1-Score as a function of the proportion of representatives selected for each quality measure and gold standard for datasets D&D, AIDS and FOPPA. The rest of the datasets are shown in Figure 17)</figcaption></figure>
what we do in Section 6.4.1. Figures 19g, 19h, and 19i show the classification performance in terms of F1-Score, as in Section 6.4.2.

<figure><img src="image_20.png" /><figcaption>Fig. 19. Experiments for the FRANK dataset.</figcaption></figure>

The main difference between this dataset and the others, in terms of results, is in the blocks of correlation quality measures identified using Kendall's Tau (Figure 19c), which are not exactly the same as for the other datasets:

* DEP and LAP are included in the GR block.

* SUPDIF is included in the Acc block.

* JACC is included in the Cos block.

* MUTINF, PEARSON and $\chi^2$ share a block together.

The overall classification performance is lower than for the other datasets, which can be explained by the absence of labels, resulting in a large number of generic patterns, present in many graphs regardless of class.
## D.2 IMDb Results

The results obtained for the IMDb dataset are not presented in the main article due to their similarity with those of AIDS. Figure 20a and 20b correspond to the experiments from Section 6.2. Figure 20c shows Kendall's Tau correlation matrix, as in Section 6.3. Figures 20d, 20e, and 20f show comparisons with the gold standard in terms of RBO, similarly to what we do in Section 6.4.1. Figures 20g, 20h, and 20i show the classification performance in terms of F1-Score, as in Section 6.4.2.

<figure><img src="image_21.png" /><figcaption>Fig. 20. Experiments for the IMDb dataset.</figcaption></figure>

The blocks of measures are identical to the general case. However, a difference can be observed regarding classification performance. Measure DEP achieves a better F1-score than our gold standard, despite a low RBO between the two. This is because our gold standard is only an approximation of the ground truth ranking, as it is based on an approximation of the Shapley Value (cf. Section 5.2.1).