We aim at finding and understanding dependencies between linguistic structures which differ in terms of constraints and expressive power. It has been shown that studying dependencies between the argumentation structure (ARG) and the Rhetorical Structure Theory (RST ) is non-trivial and requires a fine methodology. In this paper, we propose to take advantage of the AOC-Poset structure to understand how the subgraphs alignements occur in a small corpus annotated in ARG and RST. We formalize the structures as graphs from which we extract both subgraphs and subgraphs alignments, matching those subgraphs which include the same text segments. Based on these extractions, we build a formal context where the objects are the texts and the attributes are the subgraphs and the subgraphs alignments. We show what we can learn from the dependencies between the structures by mining the AOC-Poset made of these attributes.
This paper experiments the use of AOC-Posets (also called Galois sub-hierarchies) to observe and explain how subgraphs coming from two parallel graph-based views of objects are aligned. Formal Concept Analysis and the partial order defined on formal concepts provides a very powerful framework for a fine-grained study of the relations between classes of objects. The experiment concerns a corpus dually annotated as graphs following two distinct theories of discourse and argumentation.
Several linguistic theories aim at annotating the discourse [
In this paper, we build subgraphs alignments from graphs coming from
annotations made using two distinct theories.The first one, called Rhetorical
Structure Theory3 [
Our corpus of texts has two views that can be represented as ARG and RST graphs, which are then decomposed into subgraphs. An alignment in a text is a pair (SRST , SARG) of subgraphs, where the SRST subgraph of the RST graph covers the same set of textual segment vertices as SARG, the subgraph of the ARG graph. If these alignments are frequent in the corpus, i.e they occur in more texts than a given threshold, it would highlight dependencies between the theories. However, alignments are rare and we are interested in understanding in depth which parts of the graphs are aligned, and what the ”elements” that prohibits other alignments are. We rely on AOC-Posets, a conceptual structure on object and attribute concepts that has the advantage of being smaller than the full concept-lattice, but still allows one to study dependencies between attributes in terms of subsumption, disjointedness or partial overlap between concepts.
In Section 2, we introduce the graphs built from the two theories and state our problem. In Section 3, we motivate and contextualize our work. In Section 4, we present our methodology and which relevant information on the alignments can be mined from the AOC-poset. Then, we present some results on a small corpus annotated with both ARG and RST and we conclude and present some future research. 2
Our goal is to understand what leads to subgraph alignments in a set of texts (objects) that have two distinct views as graphs, that we decompose into subgraphs (attributes). An alignment is a pair of subgraphs (one from the ARG graph, the other one from the RST graph) that cover the same segments of text. We take advantage of AOC-poset for finding dependencies, i.e highlighting alignments that frequently occur in the corpus, and for determining the situations in which alignments occur or do not occur. This section presents the structures on which we are working and states our problem. 3 Website of the RST: https://www.sfu.ca/rst/
The corpus from which we extract graphs is made of 112 argumentative texts written to answer a controversial question. For example, the text in Fig. 1 argues about the question “Should we continue to separate our waste for recycling?”. Each text has been analysed with two distinct goals: describing discourse and argumentation structures. This led to two distinct annotations, both relying on a single segmentation (in clauses or propositions) but using distinct sets of relations (6 in ARG and 26 in RST ) and distinct constraints. As an example in RST only adjacent segments may be related while there is not such constraint in ARG. This leads to structural differences in the graphs coming from each annotation and thus lack of isomorphism between them.
1. [It’s annoying and cumbersome to separate your rubbish properly all the time.] 2. [Three different bin bags stink away in the kitchen 3. and have to be sorted into different wheelie bins.] 4. [But still Germany produces way too much rubbish] 5. [and too many resources are lost 6. when what actually should be separated and recycled is burnt.] 7. [We Berliners should take the chance and become pioneers in waste separation!] (a) Fig. 2: RST (a) and ARG (b) graphs of the text in Fig. 1. Square nodes are textual vertices, and black round nodes are structural vertices.
Rhetorical Structure Theory The graphs built in RST (see Fig. 2a) aim at describing the intention of the writer about a reader. The annotation using this theory aims at relating adjacent segments of text through discourse relations – represented by labeled directed edges – thus forming bigger segments that are in turn linked to others. To do so, RST exploits two distinct types of relations.
Mononuclear relations involve two segments. They are directed, indicating that a segment (the source) is less important than the other (the target) (see segments 5 and 6 in Fig. 2a). Multinuclear relations link two or more segments of equal importance. We introduce structural vertices to represent these multinuclear relations in our graphs. They are distinguished from textual vertices that represent segments of text. For example, in Fig. 2 vertices 2 and 3 are in a multinuclear conj relation: they are thus related through the structural vertice to which they are directed. Then, the structural vertice is directed to textual vertice 1 in a mononuclear reason relation.
Argumentation Structure The graphs built in ARG (see Fig. 2b) aim at
describing how segments are linked by argumentative relations in order to defend
a stance. The annotation procedure proposed by [
We want to observe dependencies between (parts of) graphs coming from ARG and RST views. To do so, we observe if alignments between subgraphs are frequent in the sets of graphs, i.e if pairs of subgraphs that cover the same set of textual vertices are occurring frequently in the sets of graphs. For example, in Fig. 1 subgraphs SA and SR cover the same textual vertices set {1, 2, 3} and thus are aligned. If this alignment was frequent in the corpus, we would be able to interpret it as a dependency between SA and SR and further as a dependency between parts of the theories. However, due to the diversity in the annotations and the constraints imposed by the theories, these strict dependencies doesn’t occur. We are thus interested in dependencies of other types, for example, (1) if S1A is aligned to S1R in some texts but to S2R in some others, or (2) if S1A is aligned to S1R in some texts, to S2R in some others, but S1R is aligned to S1A in some texts and to S2A in some others.
Accuosto et al. [
In [
However, two graphs built on one text are usually not isomorphic and the sets of relations used to label the edges are different in size (6 in ARG and 26 in RST ). It could thus be interesting to go deeper in the analysis by considering alignments occurring at subgraph level.
For a more systematic comparison and for considering subgraph alignments
instead of individual edge alignments, authors in [
Formal Concept Analysis (FCA) [
We build AOC-Posets which is most of the time much smaller in size than
the full lattice. More precisely, it contains at most |A| + |O| concepts, while the
complete lattice may have up to 2min(|A|,|O|). AOC-Posets has been used as a
tool for different tasks. For example, [
Our methodology aims, in three steps, at representing the corpus as a formal context (see Fig. 3). We proceed at two different levels. First, at the text level, we extract all subgraphs and we build a pair of subgraphs if two subgraphs are aligned in the text, i.e. if they cover the same textual vertices. Then, we study the occurrences of alignments at the corpus level. We compare subgraphs and subgraphs alignments between texts: two subgraphs coming from two different texts are identical as long as their structure is identical, regardless of the label of the vertices. We introduce two constraints for the extraction of subgraphs to make sure that they involve at least two textual vertices and that they are always weakly connected subgraphs. We call them valid subgraphs. For example in Fig. 2a, the ARG subgraph which covers vertices {1, 2, 3} is valid while the one covering vertices {1, 2, 3, 4} is not.
Definition 2. A subgraph S = (Vt ∪ Vs, Es) is valid iff S is weakly connected and if |Vt| >= 2.
For each text ti ∈ T we extract all valid subgraphs of ARG i and RST i. We obtain 2 sets of subgraphs. In the second table of Fig. 3, triangles represent valid subgraphs and numbers inside represent the nodes covered by it.
ARGsubs = {Ax | Ax is a valid subgraph of an RST graph} RSTsubs = {Ry | Ry is a valid subgraph of an ARG graph} (1) (2)
Subgraphs that have an identical structure, ie that are similar subgraphs regardless of the vertices labels, have a similar label Ax or Ry assigned. For example in the second table of Fig. 3, the two yellow triangles represent subgraphs that have an identical structure, even if they cover different sets of vertices. The label A2 is thus assigned to each subgraph. These labeling of subgraphs serves as the basis for constructing the set of attributes. 4.2
From the sets of subgraphs obtained, we extract pairs of subgraphs (Ax, Ry) that are aligned in a text, i.e that cover same textual vertices. For example, in Fig. 2a, the ARG and RST subgraphs which covers the textual vertices {7, 4, 6} are aligned because they both cover the same vertices.
Definition 3. Given S1 = (Vt1 ∪ Vs1, E1) a subgraph of ARGsubs and S2 = (Vt2 ∪ Vs2, E2) a subgraph of RSTsubs, S1 and S2 are aligned in a text t iff Vt1 = Vt2.
On ARGsubs × RSTsubs, we define the subset of subgraphs that are aligned as follows:
AR = {(Ax, Ry) ⊆ ARGsubs × RSTsubs | ∃t ∈ T, Ax and Ry are aligned in t} (3) and the set of graphs singleton that are aligned as:
A = {Ax ∈ ARGsubs|∃Ry ∈ RSTsubs, (Ax, Ry) ∈ AR} R = {Ry ∈ RSTsubs|∃Ax ∈ ARGsubs, (Ax, Ry) ∈ AR} (4) (5)
Thus, a given text t may contain as an attribute a singleton Ax, and a singleton Ry. If the two subgraphs are aligned, it will also have the attribute (Ax, Ry). For example in Fig. 3, A2 is aligned with R2 in t1 because they both cover vertices 2,3, a pair (A2, R2) is thus introduced as an attribute for t1. In t112 however, A2 is aligned with R4 and the attribute (A2, R4) is thus introduced for this text. 4.3
We determine a formal context K, on the basis of the attributes extracted and built from the graphs. K := (G,M,I) where G = T is the set of objets (the texts) and M = {A ∪ R ∪ AR} is the set of attributes (the singleton subgraphs and the aligned pairs) and (g, m) ∈ I means that a text (an object ) g ∈ G has a subgraph and/or a subgraph alignment. 4.4
Explaining alignments among two sets of graphs can be seen as the problem
of finding subgraphs that co-occur in a set of objects described by them.
Formal Concept Analysis (FCA)[
The AOC-Poset structure relies on the partial order on the concepts
introducing at least an object (object concept ) or an attribute (attribute concept ). A
concept C introduces an object x (resp. attribute y) when x is in the extent of
C but not in any concept C0 < C (resp. C0 > C). While the full concept lattice
build from K contains 2120 concepts, the AOC-Poset contains only 379 and can
thus be used as a smaller alternative. We used the Hermes algorithm [
The order defined over the concepts of the AOC-Poset may help to observe in which way aligned attributes occur in the corpus. Fig. 4 shows some simplified possible cases (in reduced notation) that we may observe: a node represents a concept and its label gives its local intent.
{A, R} {(A, R)} {A, R, (A, R)} {A} {R} {R} {A} {A} {R} {A} {R} {(A, R)} {(A, R)} {(A, R)} {R, (A, R)} {A, (A, R)} (a) (b) (c) (d) (e) (f) (g) Fig. 4: Substructure of the AOC-Poset: concepts are rectangles labeled by their local intents.
Case 4a in Fig. 4 illustrates that A and R subgraphs may be used in the same texts without being necessarily aligned, contrary to case 4b, where subgraphs are always aligned when they are both used in the same texts. In 4c, the concepts introducing the singletons forming the alignments are incomparable, meaning that there exist some objects having only one of the singletons. Cases 4d (resp. 4e) correspond to cases where, in the texts having an A (resp. R) subgraph, some have also the R (resp. A) subgraph and a subset has both of them aligned. Cases 4f (resp. 4g) illustrates when an A schema is always aligned with an R schema (and thus can be interpreted as one theory that depends on another), and it can be seen as a specialization of the case 4e. 5.1
The corpus on which we built the formal context is made of 112 texts that we represented with both ARG and RST graphs having on average 6 textual vertices (min 3, max 13). After building the context with the methodology explained in the previous section, we got 2189 attributes in total, 1278 were singletons that could be aligned and 911 were pairs of aligned subgraphs. These pairs are built from 534 ARG subgraphs and 744 RST subgraphs. Among them, only 74 have a support greater than 1. The others correspond to the attributes that are specific to a text. We ignore them for simplicity.
Based on the definitions of the structures and especially the fact that RST uses a set of 26 distinct relations compared to 6 in ARG, it is likely that a unique ARG subgraph may be frequently aligned with several distinct RST subgraphs. However, proportions of ARG and RST alignments roughly followed the same distributions as we can see in Table. 1. 5.2
We classified each pair of subgraphs from the attributes set into the classes described in Fig. 4. Table 2 gives the number of attributes for each substructure in the AOC-Poset. We discuss here information learned from the structure of the AOC-Poset on alignments that have a support greater than 1.
Two subgraphs alignments (with a support > 1) correspond to the substructure 4f. Both are in fact introduced in the same concept (c3) (see Fig. 5) meaning that they occur exactly in the same texts. Concepts introducing a1 (c1) and a4 (c2) form a chain together with c3 while attributes r128 and r132 are introduced in c1. a1 is a subgraph of a4, however a1 and a4 are introduced in different concepts, meaning that a1 may be used in a different “environment” than the one of a4. r128 is a subgraph of r132, and they are introduced in the same concept so that all texts containing r128 also contains r132, meaning that the first is never used in another context than the latter. This observation is relevant according to the theories because the multinuclear list relation is always used to link at least two textual vertices.
1 supp 2 a1 1 list 2 evi 2 r128 1 1 supp supp 2 a4 list
list 2 evi 2 r132 3 3
Concept C1 a1 a4 Concept C2 Concept C3 r128, r132, (a4, r132), (a1, r128)
Four of the five alignments classified as 4e are in fact introduced in the same concept which is also a concept introducing two texts. This attribute-objectconcept highlights two texts that were annotated by the exact same structures in both ARG and RST. The five pairs are introduced in the concept as well as their ARG singletons. However, all RST attributes are introduced in greater concepts, meaning a dependency of ARG with RST but not of RST with ARG.
The substructures classified as 4c are the most frequently observed. Unfortunately, they correspond to cases where we cannot conclude to a unique relation between an ARG subgraph and a RST subgraph. Indeed, most of the time, both subgraphs are implied in more than one alignment, thus implying to study bigger substructure of the AOC-poset, as shown in Figure 6, to make conclusions. These more complex cases are not discussed here due to lack of space. {A2} {(A1, R2)} {(A1, R1)} {(A2, R1)} Fig. 6: AOC-Poset Substructure: rectangles show concepts with their local intents. 6
We proposed to approach the problem of finding and understanding alignments in a corpus of texts annotated following two distinct theories. The corpus used and the constraints coming from both theories led to a strong variability in terms of possible alignments between subgraphs. We proposed to represent the corpus as a binary context relating texts with subgraphs or pairs of subgraphs. We used AOC-Poset to highlight specificities in the annotations or generalities that can be used to draw conclusions about the dependencies between the two formalisms.
This work served as a first study on this problem and opens up different
possibilities for future work. We found characteristics on the corpus by
semiautomatically searching for specific structures on the concepts of the AOC-Poset.
This process could be later fully automated allowing a complete understanding
of the alignments occurring in the corpus. Some extension of FCA could also be
used for this problem. In particular, RCA [
Pattern Structures [
This work was supported partly by the french PIA project “Lorraine Universit´e d’Excellence”, reference ANR-15-IDEX-04-LUE.