# Document Classification via Stable Graph Patterns and Conceptual AMR Graphs

Eric George Parakal, Egor Dudyrev, Sergei Kuznetsov, Amedeo Napoli

► To cite this version:

Eric George Parakal, Egor Dudyrev, Sergei Kuznetsov, Amedeo Napoli. Document Classification via Stable Graph Patterns and Conceptual AMR Graphs. CONCEPTS 2024 - 1st International Joint Conference on Conceptual Knowledge Structures, Universidad de Cádiz, Sep 2024, Cádiz, Spain. pp.286-301, 10.1007/978-3-031-67868-4_19. hal-04974939

HAL Id: hal-04974939

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

Submitted on 3 Mar 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>

Distributed under a Creative Commons Attribution 4.0 International License
Document Classification via Stable Graph
Patterns and Conceptual AMR Graphs

Eric George Parakal¹[0000-0002-2059-1608]

Egor Dudyrev¹,²[0000-0002-2144-3308]

Sergei O. Kuznetsov¹[0000-0003-3284-9001]

Amedeo Napoli²[0000-0001-5236-9561]

¹ National Research University Higher School of Economics, Pokrovsky Blvd, 11,
Moscow, 109028, Russia

{eparakal,skuznetsov}@hse.ru

² Université de Lorraine, CNRS, LORIA, 54000 Nancy, France

{egor.dudyrev,amedeo.napoli}@loria.fr

**Abstract.** This paper proposes an approach and an associated system based on pattern structures, aimed at the classification of documents represented as graphs. The representation of documents relies on *Abstract Meaning Representation* (AMR) document graphs. Given a set of AMR document graphs, the system learns characteristic graph patterns, that can be reused by an aggregate rule classifier to predict the class of a document. The selection of the most stable graph patterns is based on the gSOFIA algorithm and the Δ-stability measure. In the experiments, two document datasets are considered for validating the approach. The first includes documents belonging to 10 different newsgroups and the second contains sports news articles belonging to 5 topical areas. The results in terms of the macro-averaged F₁ scores, are quite satisfactory and show that the approach is well-founded and useful.

**Keywords:** Pattern Structures · Document Classification · Natural Language Processing · Abstract Meaning Representation.

# 1 Introduction

Formal Concept Analysis (FCA) [10] can be used for knowledge discovery and processing [7,19,20] tasks, as well for tasks related to Natural Language Processing (NLP) such as text classification [5]. Considering the latter, texts can be represented as graphs using methods such as conceptual graphs [21], parse thickets [8] and Abstract Meaning Representation (AMR) graphs [1]. Afterwards, the analysis of graph data can be performed using pattern structures [9] or a specific extension of FCA such as Graph-FCA [6].

Following this line, the purpose of this paper is to classify a collection of texts represented as graphs, using pattern structures, which allows a monitoring of the classification process. For doing so, texts are first transformed into AMR graphs, and are then classified by means of a specific classifier, thereby providing
an explainable and conceptual method for solving the problem of document classification.

More precisely, a document consists of a set of sentences which are repre-
sented as AMR graphs. A classifier based on the gSOFIA algorithm [4] is applied
on a training set of documents represented as AMR graphs, to discover a set of
characteristic features, that are actually stable graph patterns. Afterwards, these
features are reused by an aggregate rule classifier for predicting the classes of
test or new documents. The class of a document refers to its topical area, e.g.,
*history, food, sport, etc.*

In [18] we proposed an “intrinsically interpretable document classifier”, which provided explanations for document classification, in terms of significant keyword clusters. Then, we proposed a preliminary version of an explainable document classifier [14] trained on document graphs, to improve the performance and the explainability of the document classification process.

In this paper, we considerably develop this preliminary approach to explain-
able conceptual document classification, using AMR graphs, graph pattern struc-
tures, concept stability, and a set of concept penalties. The latter are used to
control and tune the classification process. Moreover, this paper precisely de-
scribes the transformation and classification of documents, with the following
contributions:

- A detailed discussion and algorithm for the document-to-AMR graph con-
  version process.

- An overview of the gSOFIA algorithm, which is used to efficiently mine stable graph pattern concepts.

- The construction of an aggregate rule classifier that reuses the graph pattern concepts discovered by gSOFIA, along with seven different concept penalties for tuning the classification of a test document.

- A series of experiments based on two document classification datasets, where the performance of the aggregate rule classifier is compared to some other baseline Machine Learning (ML) models, such as SVM, logistic regression, and a Graph Convolutional Network (GCN).

This paper is organized as follows: Section 2 presents the basics of pattern
structures, the stability of concept intents, as well the gSOFIA algorithm, Sec-
tion 3 explains the methodology and the workflow supporting the document
classification process, Section 4 discusses in detail the experiments related to
document classification and finally, Section 5 concludes the paper.

## 2 Background

2.1 Basic Definitions

First we give some definitions [9,12] related to pattern structures and their pro-
jections.
**Definition 1.** Let $G$ be a set, called a set of objects, let $(D, \sqcap)$ be a meet-semilattice of potential object descriptions and let $\delta: G \to D$ be a mapping. Then $(G, \underline{D}, \delta)$, where $\underline{D} = (D, \sqcap)$, is called a pattern structure, provided that the set

$$ \delta(G) := \{\delta(g) \mid g \in G\} $$

generates a complete subsemilattice $(D_\delta, \sqcap)$ of $(D, \sqcap)$, i.e., every subset $X$ of $\delta(G)$ has an infimum $\sqcap X$ in $(D, \sqcap)$ and $D_\delta$ is the set of these infima.

In this paper descriptions are sets of graphs and intersection $\sqcap$ is based on taking maximal common subgraphs.

**Definition 2.** If $(G, \underline{D}, \delta)$ is a pattern structure, the derivation operators are mappings

$$ A^{\diamond} := \sqcap_{g \in A} \delta(g) \quad \text{for all } A \subseteq G $$

$$ d^{\diamond} := \{g \in G \mid d \sqsubseteq \delta(g)\} \quad \text{for all } d \in D $$

The elements of $D$ are called patterns and are ordered by subsumption $\sqsubseteq$

$$ c \sqsubseteq d: \iff c \sqcap d = c $$

**Definition 3.** A pattern concept of $(G, \underline{D}, \delta)$ is a pair $(A, d)$ satisfying

$$ A \subseteq G, d \in D, A^{\diamond} = d \text{ and } A = d^{\diamond} $$

where $A$ is called the pattern concept extent and $d$ is called the pattern concept intent. The set of all pattern concepts ordered according to the inclusion of concept extents, forms the pattern concept lattice.

**Definition 4.** A projection $\psi$ of a pattern set $D$ is a mapping $\psi: D \to D$ on the partial order $(D, \sqsubseteq)$, which is a kernel (interior) operator, i.e., $\psi$ is monotone $((x \sqsubseteq y) \to (\psi(x) \sqsubseteq \psi(y)))$, contractive $(\psi(x) \sqsubseteq x)$, and idempotent $(\psi(\psi(x)) = \psi(x))$.

A broad class of projections retain the similarity operation $\sqcap$, i.e., $\psi((d_1) \sqcap (d_2)) = \psi(d_1) \sqcap \psi(d_2)$, among them are projections that respect order ideals and the so-called o-projections [3].

## 2.2 Concept Stability

For a concept $(A, d)$, the intentional stability [13] is the probability that $d$ remains closed upon removing a subset of objects from $A$, with equal probability.

**Definition 5.** The (intentional) stability of a pattern concept $(A, d)$ is

$$ \mathrm{Stab}(A, d) = \frac{|\{C \subseteq A \mid C^{\diamond} = d\}|}{2^{|A|}} $$
## 2.3 The gSOFIA Algorithm for Mining Graph Patterns

The number of graph pattern concepts that can be obtained from a context, can be exponentially large and the process of graph mining is computationally expensive. This necessitates the use of different measures for selecting the most interesting graph pattern concepts. The gSOFIA algorithm uses the stability measure of a pattern concept, defined in subsection 2.2.

The concept's stability reflects the independence of its concept intent, of the objects in its extent. A more stable concept is more likely to have its graph pattern intent be reproduced in various subsamples of a dataset and therefore, is more likely to be found in an unrelated dataset from the same population. Consider two closed graph patterns p and q, such that $p \subseteq q$. $\Delta(p, q)$ is defined as $\Delta(p, q) = |p^{\diamond} \setminus q^{\diamond}|$, which allows $Stab(p)$ to be bounded as follows:

$$1 - \sum_{q \succ p} 2^{-\Delta(p,q)} \leq Stab(p) \leq 1 - 2^{-\Delta(p,q)}$$

The upper bound of stability ranks graph patterns in the same way as $\Delta(p) = \min_{q \succ p} \Delta(p, q)$, which is called the Δ-stability measure, or simply the Δ-measure.

An important property of stability, its upper bound, and Δ-stability is that their values cannot decrease when passing from an original pattern structure to its projection. More formally, let $(D, \sqcap)$ be a pattern structure and $(\psi(D), \sqcap)$ be a projected pattern structure w.r.t. some projection $\psi$. Then for a pattern concept $(A, d)$, we have $\psi(d)^{\diamond} = A$, i.e., the concept extent A is not changed by $\psi$ and it is still a concept extent in the obtained projected pattern structure [3]. Hence,

$$Stab(A, d) \leq Stab(A, \psi(d)).$$

Similar relations hold for the upper bound of stability and Δ-stability. This property is called projection monotonicity. The gSOFIA algorithm mines graph patterns with Δ-stability above a threshold $\theta$ using projection monotonicity in the reverse way, which can be called “antiprojection antimonotonicity.”

The gSOFIA algorithm iteratively expands smaller graph patterns to larger ones so that at each step the initial graph pattern is a projection of the resulting graph pattern. Supposing that $d_0 \in \mathcal{D}$ is a graph pattern from the set of possible patterns $\mathcal{D}$ (the pattern space), then for a given graph pattern $d$, the projection $\psi_i: \mathcal{D} \to \mathcal{D}$ returns the graph pattern it was generated from, i.e., $\psi_i(d_i) = d_{i-1}$ for all $1 \leq i \leq k$.

# 3 Methodology

## 3.1 Overview

The set of all the training documents belonging to a class c is denoted by {$g_{ic}^{train}$}. The document-to-graph conversion algorithm converts every set of training documents of each class, to their respective set of document graphs, i.e., their graph
descriptions {$\delta(g_{ic}^{train})$}. The gSOFIA algorithm is applied to each set $\delta(g_{ic}^{train})$, to mine for the set of stable graph pattern concepts, which is a subset of $\mathcal{L}_c$, that denotes the lattice of graph pattern concepts of the class c.

A test document $g_i^{test}$ to be classified, is first mapped to its graph description $\delta(g_i^{test})$. The aggregate rule classifier notes the specific concepts of $\mathcal{L}_c$, whose graph patterns are subsumed by $\delta(g_i^{test})$. An aggregate score $S^{\mathcal{L}_c}$ is cumulatively incremented each time $\delta(g_i^{test})$ subsumes a graph pattern of a concept inside $\mathcal{L}_c$. This is performed for every class to obtain a set of aggregate score {$S^{\mathcal{L}_c}$}, i.e., one aggregate score per class. $g_i^{test}$ is then classified as belonging to the class with the highest $S^{\mathcal{L}_c}$.

Thus, the document classifier has the following stages:

1. Document-to-graph conversion: The document classifier requires that all documents for each class, are first converted to their respective document graphs. The DOCTOGRAPH algorithm constructs a document graph by modifying, refining and then merging the AMR graphs of the sentences, present in a document.

2. Mining stable graph pattern concepts: The gSOFIA algorithm mines the document graphs of the training documents of every class, to obtain a set of stable graph pattern concepts associated with each class. The minimum support threshold is varied depending on the class, to obtain a diverse and representative set of concepts.

3. Aggregate rule classification: The aggregate rule classifier uses the mined set of concepts of every class, to classify a test document, via the graph subsumption relation.

## 3.2 Document-to-Graph Conversion

**Algorithm 1 DOCTOGRAPH**

**Input:** a document $g_i$
**Output:** a graph description $\delta(g_i)$
$T_i \leftarrow \text{findSentences}(g_i)$
**for all** $t_{ji} \in T_i$ **do**
    AMR$_{ji} \leftarrow \text{AMRParser}(t_{ji})$
    MOD$_{ji} \leftarrow \text{ModifyGraph}(\text{AMR}_{ji})$
    REF$_{ji} \leftarrow \text{refineGraph}(\text{MOD}_{ji})$
**end for**
$\delta(g_i) \leftarrow \text{mergeGraphs}(\{\text{REF}_{ji}\})$
**return** $\delta(g_i)$

For the document classifier, AMR graphs are the most suitable for obtaining graph representations of documents, because they ensure that texts that are similar in meaning, have AMR graphs with similar topology, even if the original
texts are not similarly worded. Using AMR graphs to construct the document graphs ensures that when mining for stable graph pattern concepts, intra-class document graph intersection is maximized, whereas inter-class document graph intersection is minimized.

This explains why AMR graphs are more compatible with pattern structures, rather than more widely used document graph representation methods such as syntactic graphs or knowledge graphs. However, this does not mean that the documents graphs are pure AMR graphs. Due to the presence of variables that act as internal vertices, mining pure AMR graphs for stable graph pattern concepts can result in unnecessary overlap between the concept intents, of various classes.

Given a document $g_i$, the DOCTOGRAPH algorithm obtains its graph description $\delta(g_i)$. This is done by modifying, refining and then merging the set of AMR graphs {$AMR_{ji}$}. Each $AMR_{ji}$ is generated via the AMRParser procedure for each of the sentences $t_{ji}$, of every $g_i$. We use the amrlib library[^1] trained on the parse_xfm_bart_base[^2] sentence-to-graph model, for the AMRParser procedure.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** An example of two AMR graphs $AMR_{11}$ and $AMR_{21}$, corresponding to individual sentences, which are modified, refined and then merged to obtain the graph description $\delta(g_1)$.</figcaption></figure>

Since each $AMR_{ji}$ is generated independently, it is often the case that internal vertices with the same name can be instances of two different entities. Let us consider the example shown in Fig. 1, $AMR_{11}$ and $AMR_{21}$ are the AMR graphs of the first and second sentences, respectively of a document having the following two sentences: "A mammal typically cannot fly by itself. Bats are the only flying mammal."

In $AMR_{11}$ the internal vertex $b$ is an instance of *by-oneself*, whereas in $AMR_{21}$, $b$ is an instance of *bat*. This problem is not restricted to only sentences within the

<footnote n="1">1 https://github.com/bjascob/amrlib</footnote>

<footnote n="2">2 https://github.com/bjascob/amrlib-models</footnote>
same document and instead, can occur between documents as well. Consequently, the gSOFIA algorithm can mine spurious concepts, as *b* will be considered as a common vertex between two graphs, when it should not be. These spurious concepts will adversely affect the document classification performance of the aggregate rule classifier. To solve this problem, the set {AMR<sub>ji</sub>} will have to be modified, yielding the set of modified graphs {MOD<sub>ji</sub>}.

<caption>**Algorithm 2 MODIFYGRAPH**</caption>

**Input:** an AMR graph AMR<sub>ji</sub>
**Output:** a modified graph MOD<sub>ji</sub> of AMR<sub>ji</sub>
    MOD<sub>ji</sub> ← φ
    E<sub>j</sub> ← ALLEdges(AMR<sub>ji</sub>)
    **for all** e<sub>j</sub> ∈ E<sub>j</sub> **do**
        **if** relation(e<sub>j</sub>) ≠ "instance" **then**
            MOD<sub>ji</sub> ← addEdgeALLedges(head(e<sub>j</sub>), relation(e<sub>j</sub>), findInstance(tail(e<sub>j</sub>)))
        **end if**
    **end for**
    **return** MOD<sub>ji</sub>

The MODIFYGRAPH algorithm replaces all of the internal vertices of each AMR<sub>ji</sub>, with their respective instance entities via the findInstance procedure, before discarding the internal vertices themselves. Each edge e<sub>j</sub> of a MOD<sub>ji</sub>, is uniquely identified by the following triple: (head(e<sub>j</sub>)), relation(e<sub>j</sub>), tail(e<sub>j</sub>)), where head(e<sub>j</sub>) is the source vertex, relation(e<sub>j</sub>) is the edge label and tail(e<sub>j</sub>) is the target vertex. The uniqueness of the edge triple ensures that a modified graph will not have multiple copies of the same edge.

The triple also allows the modified graphs to be directed, have parallel edges between a pair of vertices and also allows the vertices themselves, to have self-looping edges. This is aimed at minimizing the information loss suffered during the document-to-graph conversion phase. Additionally, these modifications allow us to circumvent the restrictions that gSOFIA has, regarding directed graphs with parallel edges and self-loops (see subsection 3.3).

Each MOD<sub>ji</sub> is then refined by converting all of its vertex labels to lower case and then lemmatizing them, via the refineGraph procedure, to yield the set of refined graphs {REF<sub>ji</sub>}.

This is done to maximize intra-class document graph intersection. Finally, the set of all {REF<sub>ji</sub>} are merged, without allowing for duplicate edges, by the mergeGraphs procedure to yield δ(g<sub>i</sub>).

Fig. 2 gives an example of three documents g<sub>1</sub>, g<sub>2</sub>, and g<sub>3</sub>, represented by their respective graph descriptions. Fig. 3 demonstrates examples of various definitions stated in subsection 2.1 obtained from the documents shown in Fig. 2.

## 3.3 Mining Stable Graph Pattern Concepts

The gSOFIA algorithm uses canonically ordered frequent graph patterns to grow the Δ-stable graph patterns. The frequent graph patterns can be obtained using
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** There are three objects (documents) $g_1, g_2$ and $g_3$, with their respective graph descriptions $\delta(g_1), \delta(g_2)$ and $\delta(g_3)$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** (a) The graph pattern concept intent $\{g_1, g_2\}^{\circ}$ is obtained by intersecting the graph descriptions of the documents $g_1$ and $g_2$, here $\{g_1, g_2\}^{\circ} \supseteq \delta(g_3)$, so $\{g_1, g_2\}^{\circ\circ} = \{g_1, g_2\}$ (b) The graph pattern $d$ is subsumed by all document graph descriptions $\delta(g_1), \delta(g_2)$, and $\delta(g_3)$, so $d = \{g_1, g_2, g_3\}^{\circ}$ (c) The projection $\psi_4$, which returns the sets of 4-paths, is applied to $\delta(g_3)$.</figcaption></figure>

either the gSpan [22] or the Gaston [17] algorithms. The implementation of the gSOFIA algorithm<fnref n="3" /> used in this paper, uses the Gaston algorithm, which cannot work with directed graphs, graphs having parallel edges and self-loops.

As mentioned in subsection 3.2, our algorithm circumvents this restriction by using a unique triple for each edge of a modified graph $MOD_{j1}$. The triple encodes edge directionality and also differentiates edges that have the same vertices, but different relations between them. The vertex and the edge labels (in the form of the triples), are saved for each class, during the construction of its graph pattern concept lattice $L_c$. The saved vertex and edge labels are used to reconstruct the graph patterns from the graph pattern concept lattice, during the classifier's next phase. All graph patterns of the graph pattern concepts present in $L_c$, have a $\Delta$-stability that exceeds the threshold $\theta$.

## 3.4 Aggregate Rule Classification

**Aggregate Score Calculation** We use the graph patterns of the stable concepts mined in the previous subsection to classify documents based on their document graph representations. This subsection describes how we make a prediction for a test object $g_{test}$.

<footnote n="3">³ https://github.com/AlekseyBuzmakov/FCAPS</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 4. An example of a description of a test object $g_{test}$, that is to be classified as belonging to one of the three classes: sports, business or food.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5. An example of a three concept lattices $\mathcal{L}_{sports}$, $\mathcal{L}_{business}$ and $\mathcal{L}_{food}$, along with their respective concepts that are used to classify $g_{test}$.</figcaption></figure>

Given the set of graph pattern concept lattices {$\mathcal{L}_c$} of every class and a $g_{test}$, the aggregate rule classifier generates a set of aggregate scores {$S^{\mathcal{L}_c}$}, one $S^{\mathcal{L}_c}$ for each class. The test object is then classified as belonging to the class with the highest aggregate score.

$$S^{\mathcal{L}_c} = \frac{1}{|\mathcal{L}_c|} \sum_{(A_c, d) \in \mathcal{L}_c} \frac{\sum_{p_i \in d} \text{support}(p_i) \times \text{\#size}(p_i)}{\text{penalty}((A_c, d))} [d \sqsubseteq \delta(g_{test})] \quad (1)$$

The aggregate rule classifier (equation (1)) scores the likelihood (though not a formal likelihood) of $g_{test}$ to belong to a class c. In order to do so, the classifier compares the graph description $\delta(g_{test})$ of $g_{test}$, with the graph patterns of the concepts present in $\mathcal{L}_c$, that are mined from the training documents of each class. The scoring procedure consists of three main parts. First, the scoring procedure iterates through every concept $(A_c, d) \in \mathcal{L}_c$ and filters the concepts that cover
the test object $g_{test}$, i.e., those concepts, whose subgraphs $p_i$ present in their graph pattern $d$, are all subsumed by $\delta(g_{test})$.

Then, for every filtered concept ($A_c, d$), the procedure increases the overall score by the fraction of $\sum_{p_i \in d} \text{support}(p_i) \times \text{\#size}(p_i)/\text{penalty}((A_c, d))$ that favors the concepts whose subgraphs describing many objects of class $c$ ($\text{support}(p_i) = |p_i|$) and disapproves the concepts with high penalties (the latter will be discussed further below). The size of a subgraph is computed as the number of its vertices. Finally, after summing up the $(\text{support} \times \text{\#size})/\text{penalty}$ fractions of every concept in $\mathcal{L}_c$ that describes $d$, the scoring procedure normalises the overall score by the number of iterated concepts $|\mathcal{L}_c|$. Thus, we diminish the effect of various classes $c$ having various amount of mined concepts $\mathcal{L}_c$.

## 3.5 Example

The working of the aggregate rule classifier is explained using the example shown in Fig. 4 and Fig. 5. Here, we slightly abuse the notation (along standard FCA lines [10]) and do not use braces for singleton sets. Supposing there is a $g_{test}$ that is to be classified as belonging to one of the three classes: sports, business or food. Each class has its own graph pattern concept lattice, containing two graph pattern concepts, e.g., $\mathcal{L}_{sports}$ has two concepts sports1 and sports2. Here, sports1 is an example of concept whose graph pattern has two maximal common subgraphs $p_1^{sports1}$ and $p_2^{sports1}$. The graph patterns of the concepts, along with their respective penalties and supports, as well as supports of their subgraphs are also written.

We can see that for $\mathcal{L}_{sports}$, both of the graph patterns of its concepts are subsumed by $\delta(g_{test})$, i.e., $\delta(\text{sports}_1) \subseteq \delta(g_{test})$ and $\delta(\text{sports}_2) \subseteq \delta(g_{test})$. Thus, according to equation (1), the aggregate score $S^{\mathcal{L}_{sports}}$ for the sports class is calculated below as

$$ \frac{1}{|\mathcal{L}_{sports}|} \left( \frac{\text{support}(p_1^{\text{sports}_1}) \times \text{\#size}(p_1^{\text{sports}_1}) + \text{support}(p_2^{\text{sports}_1}) \times \text{\#size}(p_2^{\text{sports}_1})}{\text{penalty}(\text{sports}_1)} + \frac{\text{support}(p_1^{\text{sports}_2}) \times \text{\#size}(p_1^{\text{sports}_2})}{\text{penalty}(\text{sports}_2)} \right) = \frac{1}{2} \left( \frac{16 \times 3 + 18 \times 2}{4} + \frac{14 \times 2}{3} \right) = 15.16 $$

For $\mathcal{L}_{business}$, only the graph pattern of its first concept is subsumed by $\delta(g_{test})$, i.e., $\delta(\text{business}_1) \subseteq \delta(g_{test})$ but $\delta(\text{business}_2) \supseteq \delta(g_{test})$. The aggregate score $S^{\mathcal{L}_{business}}$ for the business class is then calculated below as

$$ \frac{1}{|\mathcal{L}_{business}|} \left( \frac{\text{support}(p_1^{\text{business}_1}) \times \text{\#size}(p_1^{\text{business}_1})}{\text{penalty}(\text{business}_1)} \right) = \frac{1}{2} \left( \frac{7 \times 3}{5} \right) = 2.1 $$

For $\mathcal{L}_{food}$, neither of the graph patterns of its concepts are subsumed by $\delta(g_{test})$, i.e., $\delta(\text{food}_1) \supseteq \delta(g_{test})$ and $\delta(\text{food}_2) \supseteq \delta(g_{test})$. So the aggregate score $S^{\mathcal{L}_{food}}$ for the food class is calculated to be 0. Since $S^{\mathcal{L}_{sports}}$ is higher than $S^{\mathcal{L}_{business}}$ and $S^{\mathcal{L}_{food}}$, $\delta(g_{test})$ is classified as belonging to the class sports.
## 3.6 Concept Penalties

A concept of class c is penalised if its graph pattern is subsumed by the descriptions of training documents from the other classes $C \setminus \{c\}$, called counterexamples. We also define seven different ways of weighting these counterexamples for a concept (including one baseline), if the previously mentioned subsumption condition is satisfied.

The first weighting method defined in equation (2), penalizes concepts based on the cumulative sum of the sizes of the subgraphs, present in their graph patterns (here size is computed as the number of vertices of a subgraph) and the number of counterexamples of these concepts. Obviously, the probability of a larger graph pattern being subsumed is lower than that of a smaller graph pattern being subsumed.

$$ penalty_1((A_c, d)) = |d^{\circ} \setminus A_c| \sum_{p_i \in d} \#\text{size}(p_i) \quad (2) $$

The second weighting method defined in equation (3), penalizes concepts based on the inverse of the number of vertices present, in the description of the training document graph, that subsumes their respective graph pattern. We are lenient if a training document graph description with a larger number of vertices subsumes the graph pattern of a concept, but harsh otherwise.

$$ penalty_2((A_c, d)) = \sum_{g \in d^{\circ} \setminus A_c} \frac{1}{\#\text{size}(\delta(g))} \quad (3) $$

The third weighting method defined in equation (4), computes the inverse of the absolute difference, between the highest vertex degrees of the description of the training document graph, and the subgraph having the highest vertex degree in a graph pattern. This weighting method is used as a heuristic for the similarity of the description of the training document graph, and the graph pattern. We try not to penalize large differences in the highest vertex degrees, but do punish small differences. This is aimed at penalizing heavy similarities between the concept graph patterns and the training document graphs.

$$ penalty_3((A_c, d)) = \sum_{g \in d^{\circ} \setminus A_c} \frac{1}{|\max.degree(p_i | p_i \in d) - \max.degree(\delta(g))|} \quad (4) $$

The fourth weighting method defined in equation (5) computes the penalty for a concept $(A_c, d)$ from the penalties of edges found in its graph pattern $d$. Every edge $e$ in $d$ is penalised w.r.t. the number of times it is found in a counterexample of any other description $\tilde{d}$ containing edge $e$. For the sake of simplicity, we slightly abuse the notation and write $e^{\circ}$ to represent the support of edge $e$, i.e., a subset of objects whose descriptions contain edge $e$. This is aimed at penalizing concepts at the most granular level. All our weighting methods aim to cluster the graph pattern concepts according to their respective classes, so that they can also help in clustering the test documents similarly.
$$ 
\begin{aligned}
\text{penalty}_4((A_c, d)) &= \sum_{e \in \text{edges}(d)} \text{edge\_penalty}(e) \\
\text{where } \text{edge\_penalty}(e) &= \sum_{\tilde{c} \in C} \sum_{(A_{\tilde{c}}, \tilde{d}) \in \mathcal{L}_{\tilde{c}}} \left| e^{\diamond} \setminus G_{\tilde{c}} \right|
\end{aligned}
\qquad (5) $$

The fifth weighting method defined in equation (6) counts the total number of training objects, whose graph descriptions $\delta(g)$ contain the graph pattern $d$ (so $d$ is subsumed by $\delta(g)$). Note that such a penalty, combined with the support and size of a concept $(A_c, d)$ in the fraction $(\text{support} \times \#\text{size})/\text{penalty}$ from equation (1), results in measuring the weighted probability of finding objects of class $c$ among all the objects described by $d$.

$$ \text{penalty}_5((A_c, d)) = |d^{\diamond}| \qquad (6) $$

The sixth weighting method defined in equation (7) penalizes a concept based on the number of subgraphs present in its graph pattern, and the number of counterexamples that the concept has.

$$ \text{penalty}_6((A_c, d)) = |d^{\diamond} \setminus A_c| |d| \qquad (7) $$

Finally, we compare the efficiency of every proposed penalty with the baseline penalty that equals to 1 for any concept:

$$ \text{penalty}_{\text{baseline}}((A_c, d)) = 1 \qquad (8) $$

## 3.7 Operational Modes

The aggregate scoring mechanism described above, demonstrates that the aggregate rule classifier uses the graph patterns of intents belonging to stable concepts, to classify document graphs. This is considered as the aggregate rule classifier's default mode of operation. For the sake of versatility, the aggregate rule classifier is also configured to operate in the following two modes:

1. Frequent subgraphs mode: Instead of using the set of graph pattern concepts lattices, the aggregate rule classifier trains using the set of frequent subgraphs of every class $c$, $F_c$. These frequent subgraphs are an additional output from the Gaston algorithm, obtained during the operation of the gSOFIA algorithm. The graph pattern of a frequent subgraph $f_i^c \in F_c$, is penalized and used in the calculation of the aggregate score, in the same manner as the graph patterns of a concept intent. An important distinction is that a frequent subgraph only contains a singleton graph pattern, unlike a concept intent.

2. Equivalence classes mode: The frequent subgraphs of a class can be used to construct the equivalence class of its graph patterns, $\dot{E}_c$. An equivalence class satisfies the following condition: for any two patterns $d_i$ and $d_j$; such that $i \neq j$
$j$ and $\{d_i, d_j\} \in \dot{E}_c$, $d_i^{\diamond\diamond} = d_j^{\diamond\diamond}$. Similar to a concept intent, an equivalence class can also contain multiple subgraphs. Thus, an equivalence class can then used in the same manner that a concept is used by the aggregate rule classifier, for classifying documents.

# 4 Experiments and Results

Since it is computationally expensive to operate the document classifier, the benchmarking of its document classification performance requires the use of small datasets. The first dataset [2], referred to here as the 10 newsgroups dataset, contains 1000 documents belonging to 10 classes. The first dataset is a subset of a larger dataset consisting of newsgroup documents [16]. The second dataset [11], referred to here as the BBC sport dataset, includes 737 documents that belong to 5 classes. These documents are obtained from the BBC Sport website, and are related to sports news articles.

We also compare our document classifier to three baseline models. The first two models, SVM and logistic regression, train using the TF-IDF vectorized texts of the documents. The third model is a simple four layer GCN that is trained to classify the document graphs. It has a hidden channel size of 64 and learning rate of 0.01. The GCN uses the word2vec algorithm [15] trained on the Google News dataset to obtain 300-dimensional vertex embeddings, for the document graphs.

Referring to the example in Fig. 1, we use pre-trained word2vec embeddings for vertex labels such as mammal and bat in the document graph description $\delta(g_1)$. For vertex labels such as fly-01 that are predicates, we use the word2vec embedding of their word suffix, i.e., fly. Vertices are assigned an unknown token vector embedding, if their vertex labels are not found in the pre-trained word2vec embeddings. The source code for all classifiers is provided in the on-line repository$^4$.

<table><caption>**Table 1.** Table describing the document classification performances of the baseline models, in terms of the macro-averaged $F_1$ score.</caption><thead><tr><th>Dataset</th><th>Logistic regression</th><th>GCN</th><th>SVM</th></tr></thead><tbody><tr><td>10 newsgroups</td><td><strong>0.9502</strong></td><td>0.8478</td><td>0.8018</td></tr><tr><td>BBC sport</td><td>0.9732</td><td>0.8906</td><td><strong>0.9733</strong></td></tr></tbody></table>

Table 1 shows that both baseline models using the TF-IDF vectorized texts of the documents as input, demonstrate good document classification performance. Logistic regression in particular demonstrates exemplary classification performance. The comparatively superior document classification performance of the baseline models is because they train directly on text data, and thus

<footnote n="4">⁴ https://github.com/ericparakal/stable-AMR-graphs-document-classifier</footnote>
do not suffer much information loss compared to the other models, which were trained on the document graphs. The GCN model's decent classification performance proves that despite its rather crude vertex embedding strategy, and the lack of edge embeddings, the topological information encoded in the document graphs alone, is sufficient to classify the documents. This proves the veracity of the document-to-graph conversion algorithm.

<table><caption>**Table 2.** Table describing the document classification performance, in terms of the macro-averaged $F_1$ score, of our aggregate rule classifier for all penalties, while operating in its default mode of operation.</caption><thead><tr><th>Dataset</th><th>penalty<sub>baseline</sub></th><th>penalty<sub>1</sub></th><th>penalty<sub>2</sub></th><th>penalty<sub>3</sub></th><th>penalty<sub>4</sub></th><th>penalty<sub>5</sub></th><th>penalty<sub>6</sub></th></tr></thead><tbody><tr><td>10 newsgroups</td><td>0.6425</td><td>0.7303</td><td>0.7004</td><td>0.7004</td><td>0.2096</td><td>0.6946</td><td><strong>0.7398</strong></td></tr><tr><td>BBC sport</td><td>0.7884</td><td><strong>0.9503</strong></td><td>0.8855</td><td>0.8858</td><td>0.6829</td><td>0.8732</td><td><strong>0.9503</strong></td></tr></tbody></table>

A trend observed in Table 2 and Table 3 is that both in its default and equivalence classes mode of operation, the aggregate rule classifier suffers from having to ensure that each subgraph of a graph pattern is subsumed, as a prerequisite condition during the calculation of the aggregate scores and penalties. The excessive strictness of this prerequisite condition, reduces the number of concepts and equivalence classes that could have been potentially used for document classification. However, as seen in Table 4, this is not the case when the aggregate rule classifier operates in the frequent subgraphs mode.

<table><caption>**Table 3.** Table describing the document classification performance, in terms of the macro-averaged $F_1$ score, of our aggregate rule classifier for all penalties, while operating in its equivalence classes mode of operation.</caption><thead><tr><th>Dataset</th><th>penalty<sub>baseline</sub></th><th>penalty<sub>1</sub></th><th>penalty<sub>2</sub></th><th>penalty<sub>3</sub></th><th>penalty<sub>4</sub></th><th>penalty<sub>5</sub></th><th>penalty<sub>6</sub></th></tr></thead><tbody><tr><td>10 newsgroups</td><td>0.6714</td><td><strong>0.7957</strong></td><td>0.7735</td><td>0.7750</td><td>0.3244</td><td>0.7876</td><td>0.7739</td></tr><tr><td>BBC sport</td><td>0.7414</td><td>0.9227</td><td>0.9046</td><td>0.8941</td><td>0.5437</td><td>0.9084</td><td><strong>0.9300</strong></td></tr></tbody></table>

All of the three tables demonstrate that for the most part, using more sophisticated and granular penalties such as penalties 2, 3 and 4 result in poorer document classification performance. For nearly both of the datasets and almost across all of the modes of operation, simple penalties such as penalty 1, 5, and 6 demonstrate superior document classification performance.

Another trend observed across all tables, is that better document classification performances are observed for the BBC sport dataset compared to the 10 newsgroups dataset. This is because unlike the BBC sport dataset, the texts of the documents present in the 10 newsgroups dataset are irregular, as well as being neither properly punctuated nor formatted. AMR parsers are fragile to irregular text and also require that the sentences of a text are properly separated.
If these conditions are not met, there could be information loss in the resulting AMR graphs.

<table><caption>**Table 4.** Table describing the document classification performance, in terms of the macro-averaged $F_1$ score, of our aggregate rule classifier for all penalties, while operating in its frequent subgraphs mode of operation.</caption><thead><tr><th>Dataset</th><th>penalty<sub>baseline</sub></th><th>penalty<sub>1</sub></th><th>penalty<sub>2</sub></th><th>penalty<sub>3</sub></th><th>penalty<sub>4</sub></th><th>penalty<sub>5</sub></th><th>penalty<sub>6</sub></th></tr></thead><tbody><tr><td>10 newsgroups</td><td>0.7412</td><td>0.8246</td><td>0.8017</td><td>0.7767</td><td>0.6266</td><td><strong>0.8287</strong></td><td>0.8021</td></tr><tr><td>BBC sport</td><td>0.7013</td><td>0.9300</td><td>0.9300</td><td>0.9187</td><td><strong>0.9436</strong></td><td>0.8639</td><td>0.9300</td></tr></tbody></table>

# 5 Conclusion

We have demonstrated that graph pattern structures in combination with conceptual AMR graphs could be successfully applied to the task of document classification. Stable graph pattern concepts were mined from the document graphs using the gSOFIA algorithm based on projection monotonicity w.r.t. $\Delta$-stability. An aggregate rule classifies a test document using the mined concepts, the graph subsumption relation, various concept penalties, while operating in three different modes.

The document classification performance of the document classifier was demonstrated on two datasets, in comparison with three baseline models. The document classifier demonstrated relatively good classification performance and offers much better explainability. As demonstrated in [14], the graphs patterns can be leveraged to provide intermediate explanations in terms of significant subgraphs, and nal explanations in terms of sentences.

**Acknowledgments.** The work of Sergei O. Kuznetsov was supported by the Russian Science Foundation under grant 22-11-00323 and performed at HSE University, Moscow, Russia. Egor Dudyrev and Amedeo Napoli are carrying out this research work as part of the French ANR-21-CE23-0023 SmartFCA Research Project.

# References

1. Banarescu, L., Bonial, C., Cai, S., Georgescu, M., Griffitt, K., Hermjakob, U., Knight, K., Koehn, P., Palmer, M., Schneider, N.: Abstract Meaning Representation for Sembanking. In: Proceedings of LAW@ACL. pp. 178–186. ACL (2013)

2. Baxter, J.: (10)dataset text document classification (2020), https://www.kaggle.com/datasets/jensenbaxter/10dataset-text-document-classification

3. Buzmakov, A., Kuznetsov, S.O., Napoli, A.: Revisiting Pattern Structure Projections. In: Proceedings of ICFCA. pp. 200–215. LNCS 9113, Springer (2015)
4. Buzmakov, A., Kuznetsov, S.O., Napoli, A.: Efficient Mining of Subsample-Stable Graph Patterns. In: Proceedings of ICDM. pp. 757–762. IEEE (2017)

5. Cimiano, P., Hotho, A., Staab, S.: Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis. Journal of Artificial Intelligence Research 24, 305–339 (2005)

6. Ferré, S., Cellier, P.: Graph-FCA: An extension of Formal Concept Analysis to Knowledge Graphs. Discrete Applied Mathematics 273, 81–102 (2020)

7. Ferré, S., Huchard, M., Kaytoue, M., Kuznetsov, S.O., Napoli, A.: Formal Concept Analysis: From Knowledge Discovery to Knowledge Processing. In: A Guided Tour of Artificial Intelligence Research (Vol. II), pp. 411–445. Springer (2020)

8. Galitsky, B.A., Kuznetsov, S.O., Usikov, D.: Parse Thicket Representation for Multi-sentence Search. In: Proceedings of ICCS. pp. 153–172. LNCS 7735, Springer (2013)

9. Ganter, B., Kuznetsov, S.O.: Pattern Structures and Their Projections. In: Proceedings of ICCS. pp. 129–142. LNCS 2120, Springer (2001)

10. Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations. Springer (1999)

11. Greene, D., Cunningham, P.: Practical Solutions to the Problem of Diagonal Dominance in Kernel Document Clustering. In: Proceedings of ICML. pp. 377–384. ACM Press (2006)

12. Kaytoue, M., Codocedo, V., Buzmakov, A., Baixeries, J., Kuznetsov, S.O., Napoli, A.: Pattern Structures and Concept Lattices for Data Mining and Knowledge Processing. In: Proceedings of ECML-PKDD. pp. 227–231. LNCS 9286, Springer (2015)

13. Kuznetsov, S.O., Makhalova, T.P.: On interestingness measures of formal concepts. Information Sciences 442-443, 202–219 (2018)

14. Kuznetsov, S.O., Parakal, E.G.: Explainable Document Classification via Pattern Structures. In: Proceedings of IITI. pp. 423–434. Springer (2023)

15. Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. In: ICLR (Workshop Poster) (2013)

16. Mitchell, T.: 20 newsgroups (1999), http://kdd.ics.uci.edudatabases/20newsgroups/20newsgroups.html

17. Nijssen, S., Kok, J.N.: The gaston tool for frequent subgraph mining. In: GraBaTs. Electronic Notes in Theoretical Computer Science, vol. 127, pp. 77–87. Elsevier (2004)

18. Parakal, E.G., Kuznetsov, S.O.: Intrinsically interpretable document classification via concept lattices. In: FCA4AI@IJCAI. CEUR Workshop Proceedings, vol. 3233, pp. 9–22. CEUR-WS.org (2022)

19. Poelmans, J., Ignatov, D.I., Kuznetsov, S.O., Dedene, G.: Formal Concept Analysis in knowledge processing: A survey on applications. Expert Systems with Applications 40(16), 6538–6560 (2013)

20. Poelmans, J., Kuznetsov, S.O., Ignatov, D.I., Dedene, G.: Formal Concept Analysis in knowledge processing: A survey on models and techniques. Expert Systems with Applications 40(16), 6601–6623 (2013)

21. Sowa, J.F.: Conceptual Graphs. In: Handbook of Knowledge Representation, pp. 213–237. Elsevier (2008)

22. Yan, X., Han, J.: gSpan: Graph-Based Substructure Pattern Mining. In: Proceedings of ICDM. pp. 721–724. IEEE (2002)