Computational argumentation has gained considerable attention in recent years. Various areas have been addressed, such as extracting arguments from natural language texts into a structured form in order to store them in an argument base, determining stances for arguments with respect to topics, determination of inferences from statements, and much more. After so much progress has been made in the isolated tasks, in this paper we address the next level and aim to advance the automatic generation of argument graphs. To this end, we investigate various unsupervised methods for constructing the graphs and measure the performance with diferent metrics on three diferent datasets. Our implementation is publicly available on GitHub under the permissive MIT license.
In this paper, we explore several unsupervised methods to create argument graphs and evaluate these on three datasets which are completely diferent in structure as well as in size and domain. Since our code is publicly available on GitHub under the permissive MIT license, interested researchers can build upon our work and use these methods as a baseline.1 Each of them expects a set of ADUs as input to produce a fully connected tree structure where each node is an ADU. As such, we can ignore the original text of an argument—which may not always be available anyway—and leave the detection of ADUs to future work. We assume that each ADU supports/attacks exactly one other ADU and that there exists one ADU acting as the root of an argument graph—the so-called major claim.
Our contributions are the following: (i) Seven algorithms for constructing argument graphs in pseudocode together with a reference implementation in Python. (ii) A set of metrics for evaluating our argument graphs each focused on diferent aspects. (iii) An experimental evaluation on three diverse datasets that may be used as a baseline for future work.
Next, we discuss related work in section 2. In particular, we address similarities and diferences to our work. In section 3 we describe the seven methods we use utilizing pseudo code and in section 4 we discuss the evaluation setup and results. In section 5 we conclude the paper and provide starting points for future work.
The general approach for argument graph construction in the literature is based on the utilization
of information extracted in the previous tasks. Following the concept of claim-premise model [
Stab and Gurevych [
Similar approaches are implemented by Persing and Ng [
–––––– –––––––––––––––––––– ––––––– ––––––– –––––––
–––––––
––––––––––––
–––
–––– ––
––––
––––
––––
opinions) from argumentative statements and utilize these features to connect argument
structures into the final argument graph. We refer the interested reader to the surveys conducted by
Lawrence and Reed [
In this section we will introduce our algorithms for constructing argument graphs from a given set of ADUs. In addition to the aforementioned implementations in Python (used for our evaluation in section 4), we also provide pseudocode for each of them to aid understanding implementing them in other languages.
Before diving in, we will first define some common symbols used in the pseudocode. All algorithms are passed a set of ADUs = {1, . . . , } where each ∈ is string. We denote the ADU being major claim of an argument graph as mc ∈ . Each algorithm returns this major claim mc together with a list of relations = {1, . . . , }. Each relation = (prem, claim) ∈ × is a tuple containing a premise prem that is connected to a claim claim via an inference. Some of our proposed algorithms make use of clustering methods where = {1, . . . , } denotes the set of clusters that forms a partition of . Each cluster ∈ is defined as a set of ADUs (i.e., ⊆ ).
We also use some functions that are crucial for most of the algorithms. Each ADU ∈ has a feature vector that can be accessed using the function vec() and is defined via a embedding model. This vector space makes it possible to compute a centroid for each cluster at its center point. These vectors are also used to compute the cosine similarity between ADUs—as an abbreviation, we use the function sim(, ) = cos(vec(), vec( )).
Our algorithms are able to predict the central major claim mc without any further information. In addition, it is also possible to set mc manually. For details on that matter we refer the interested reader to our reference implementation mentioned above.
Agglomerative With algorithm 3.1, we present a graph construction strategy that is based on agglomerative clustering and retains its hierarchical structures throughout the construction prem Algorithm 3.1 Agglomerative-clustering-based algorithm for constructing argument graphs. ← {{ ← ∅ while || > 1 do , ← ifnd the two most similar clusters in ◁ Ordered s.t. || < | | prem ← root of smaller cluster [] merge ← [] root ADU of larger cluster claim ← ADU of larger cluster ∈ having the highest similarity to premise delete entries , of sets and ← ∪ {(prem, claim)} ← ∪ Merge(Clusters , ) ← ∪ {merge} mc ← root node of relations return , mc process. The graph construction strategy utilizes a selection metric based on cosine similarity between embedding representations of ADUs to mimic an hypothetical concept of relatedness. The hypothesis follows the idea that more similar ADUs have a higher chance to target the same topics and thus provide related argumentative information. Each of the argumentative components starts within its own cluster (algorithm 3.1). Clusters are iteratively merged on the basis of a given criterion—in our case, average linkage. From the pair of most similar clusters, we identify the smaller and larger cluster. For the purpose of constructing more dense argument graphs structures, we consider the size of the clusters to be merged. The smaller cluster proposes the root of its respective sub-graph as premise (algorithm 3.1). Then, from the larger cluster we identify the ADU that maximizes the similarity to the previously identified premise and denote it as claim. Finally, we draw a relation from premise to claim (algorithm 3.1) which connects the sub-graphs of the two respective clusters. We update our lists and continue the iteration. Merging is repeated a total of − 1 times and per step only two clusters are merged until all ADUs are in the same cluster. Finally, we are left with a single connected argument graph. Density Algorithm 3.2 is a cluster-based approach that uses Hdbscan [13, 14] internally. Hdbscan is optimized for scenarios with a high density of data points as well as noisy data—both of which are relevant for embeddings of natural language texts. First, the underlying algorithm is run (algorithm 3.2) to construct the hierarchical/tree-based cluster structure. The following steps are diferent for natural clusters—that is, a cluster containing actual ADUs—and synthetic clusters—that is, a cluster with a single element that is not part of the set of ADUs and thus only created to allow nesting of other clusters. In the former case (algorithm 3.2), we define the claim to be the ADU having the highest similarity to all others and create relations between it and the remaining premises. In the latter case, we first need to resolve connections between two synthetic clusters that have no natural cluster as a direct child. More specifically, this means 9 mc ← claim
∪ {(prem, claim)} for all prem ∈ ′ ← contract connections between two synthetic clusters having no natural clusters for all synthetic clusters synt ∈ tree do ◁ Now, we can connect the nested clusters ← ∪ {(claim ofnat, claim ofsynt)} return , mc that we remove two relations from the hierarchical cluster structure tree and replace it with a single relation (algorithm 3.2). We then can continue by connecting the claims of the synthetic clusters to the claims of the natural clusters (algorithm 3.2).
Divide The main idea behind algorithm 3.3 is to divide it into smaller subproblems, solve them individually, and aggregate these solutions later on—the so-called divide and conquer approach [15]. More specifically, we use a relatively straightforward clustering algorithm— Means [16]—to divide the set of ADUs into smaller chunks (algorithm 3.3). This procedure is recursively executed until there are at most leaf ADUs in a cluster (algorithm 3.3). This hyperparameter may be set to an arbitrary value, but in our experiments, we set it to 3 since most argumentation schemes [17] are composed of one claim and two premises. Within each cluster, we select the ADU being most similar to all remaining ones to be the claim, the others are used as premises for that claim. The -Means algorithm expects a fixed number corresponding to the number of clusters that shall be created. We run the algorithm using a range of diferent ’s and utilize the well-known silhouette score [18] to determine the optimal number of clusters. In order to limit the computational overhead of this approach in some extent, we restrict the maximum value for to half the number of available ADUs. At the end, we receive one argument graph where each branch corresponds to a recursive function call.
Flat Algorithm 3.4 is mainly implemented as a baseline/comparison algorithm and is
borrowed from Lenz et al. [
Order The idea of algorithm 3.5 is that we sort ADUs based on their similarity to the major claim and process them in that order with some degree of freedom. This uses the assumption that ADUs being similar to the major claim should be connected to it as claims. More precisely, Algorithm 3.3 Divide-based algorithm for constructing argument graphs.
1 procedure Divide(ADUs , Centroid ← 3)
NULL, Maximum number of leaf nodes leaf ← ← ∅ if = NULL then
← arithmetic mean of vec() for all ∈ claim ← ∈ having the highest similarity to all other ADUs ← ∖ {claim} if || ≤ leaf then return × { claim}, claim
◁ Termination criterion for recursive calls ◁ Connect all remaining ADUs to the claim claim min ← 2 ◁ We need at least two clusters . . . max ← max(|| ÷ 2, min) + 1 ◁ . . . and at most half the number of ADUs opt ← value of ∈ [min, max] resulting in the highest silhouette score for all centroids ′ ∈ KMeans(, opt) do ′ ← subset of where each ∈ is assigned to centroid ′ ′, ′claim ← Divide(′, ′) ◁ Call function on subset of ADUs ← ∪ ′ ∪ {(′claim, claim)} return , claim Algorithm 3.4 Flat algorithm for constructing argument graphs.
1 procedure Flat(ADUs ) 2 ← ∅ 3 mc ← ∈ having the highest similarity to all other ADUs 4 for all ∈ ∖ {mc} do 5 ← ∪ {(, mc)} 6 return , mc we select the candidate in the -neighborhood (algorithm 3.5) as premise that maximizes the similarity between claim and premise for each queued claim. The selected premise is then removed from the queue and connected to the claim. Finally, we update the variables and continue the iteration until all ADUs are connected to one graph structure. The approach is applied TOP-DOWN and is viable from any arbitrary major claim position.
Random The purpose of algorithm 3.6 is to serve as an evaluation baseline. We do not consider similarities at all, but follow a completely random approach. Consequently, the major claim is chosen randomly (algorithm 3.6). For all remaining ADUS, we randomly select one that is not yet assigned together with one that is part of the graph (algorithm 3.6). Sim Algorithm 3.7 may be viewed as a more simplistic version of Order. In essence, we leave out the sorting step of ADUs to the major claim. We start by selecting the ADU having the highest similarity to all others as the major claim (algorithm 3.7). Then, we iterate over the Algorithm 3.5 Ordering-based algorithm for constructing argument graphs. ′ ← { mc} while || > 0 do
prem, claim ← pair of ADUs in × ′ having the highest similarity ◁ s.t. Constraint(prem, claim) holds Algorithm 3.6 Random algorithm for constructing argument graphs.
1 procedure Random(ADUs ) 2 ← ∅ 3 mc ← random() 4 ← ∖ {mc} , ′ ← { mc} 5 while || > 0 do 6 prem, claim ← 7 ← ∪ {(prem, claim)} 8 ← ∖ {prem} , ′ ← 9 return , mc random( × ′)
′ ∪ {prem} remaining ADUs (algorithm 3.7) and compute the similarity between all ADUs that are not part of the graph to the ones already added by constructing the cross product of the sets and ′ (algorithm 3.7). A new relation is then created between the two ADUs selected in the previous step (algorithm 3.7) until all ADUs are connected.
Having presented our proposed algorithms for constructing argument graphs, we will now conduct an experimental evaluation with the goal of discussing the advantages as well as the drawbacks of them. We will briefly describe our experimental setup, present the results, and discuss them afterwards.
Algorithm 3.7 Similarity-based algorithm for constructing argument graphs. prem, claim ← ← ∪ {(prem, claim)} ← ∖ {prem} ′ ← ′ ∪ {prem}
pair of ADUs in × ′ having the highest similarity 11
return , mc
In order to obtain meaningful results, we evaluated our algorithms on a total of three datasets.
The first is the Microtexts dataset from Peldszus and Stede [19] as ofered by the AIFdb project. 2
This comprises a total of 110 argument graphs, each containing 4 ADUs on average. The second
dataset by Stab and Gurevych [
As measures for graphs yield diferent scores depending on the goal, we use multiple:
1. The duration ms (measued in ms) needed to reconstruct the graph.
2. The graph edit similarity simedit that computes the number edit of operations needed to
transform one graph to another.3 We transform this distedit to a similarity score in [
| ∪ | simmc(1, 2) = {︃1, if mc(1) = mc(2), 0, otherwise.
(2) (3) (4) (5) (6) (7)
We implemented the project with Python4 and seeded random states with the integer 0 to get deterministic results. We also created a Docker container that makes it straightforward to reproduce our results. For the computation of the embeddings we use the popular library spaCy. We conduct experiments using the standard model en_core_web_lg based on plain word embeddings as well as the more advanced en_core_web_trf utilizing transformer-based embeddings.5 To parse the argument graph corpora, we utilize the arguebuf library [22].
with mc() being the major claim of argument graph . 5. The metric simdepth is based on the average tree depth [21] that is a visual indicator whether the vertical structure of two graphs overlaps. It is defined as simdepth(1, 2) = 1 −
|depth(1) − depth(2)| max(depth(1), depth(2)) with depth() denoting the average tree depth of an argument graph . 6. Similar to simdepth, the metric simbreadth functions as a visual indicator of a graph’s horizontal structure. We determine the mean average error of the number of nodes each graph has on each level and define the operators level() for retrieving the number of nodes on level of argument graph as well as levels() for determining the total levels of graph . Using = max(levels(1), levels(2)) and the equation we can now define simdepth as
distbreadth(1, 2) = ∑︁ |level(1) − level(2)| ,
=1 simbreadth(1, 2) = 1 −
distbreadth(1, 2) ∑︀le=v1els(1) level(1) s t x e t o r c i M s y a s s E o l a i K
Since the creation of these rather complex graph structures is quite subjective [23], quantitative results as shown in table 1 only tell a part of the story. To complement our findings, fig. 2 shows 4https://github.com/recap-utr/argmining-clustering 5https://spacy.io/ (e.g., Density) that still look rather similar to the original.
In this paper, we have successfully implemented a series of unsupervised algorithms for constructing highly structured argument graphs from an unordered set of ADUs. In addition, we introduced metrics that assess diferent properties of the resulting graphs and provide a comprehensive numerical view on the results. Lastly, we have demonstrated that our approaches create vastly diferent graphs from the same input data. The construction of argument graphs still is a rather subjective topic where even humans may not share the same opinion. Thus, the least our algorithms provide is a diferent perspective on the internal structure of an argument. We consider Density to be the most promising algorithm as it produces rather consistent result even for vastly diferent corpora. In future work it may be worth investigating whether the availability of multiple argument graphs of the same source has a positive impact on the understandability of an argument for certain types of users. Another area of improvement is the detection of the correct major claim which could be solved using a binary classifier trained on this task. Such approaches could then in turn be combined with our proposed algorithms to achieve even better results. [13] R. J. G. B. Campello, D. Moulavi, J. Sander, Density-Based Clustering Based on Hierarchical Density Estimates, in: J. Pei, V. S. Tseng, L. Cao, H. Motoda, G. Xu (Eds.), Advances in Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, Springer, 2013, pp. 160–172. doi:10.1007/978-3-642-37456-2_14. [14] L. McInnes, J. Healy, S. Astels, Hdbscan: Hierarchical density based clustering, The Journal of Open Source Software 2 (2017) 205. URL: http://joss.theoj.org/papers/10.21105/joss.00205. doi:10.21105/joss.00205. [15] D. R. Smith, The design of divide and conquer algorithms, Science of Computer Programming 5 (1985) 37–58. URL: https://www.sciencedirect.com/science/article/pii/ 0167642385900036. doi:10.1016/0167-6423(85)90003-6. [16] J. MacQueen, Some methods for classification and analysis of multivariate observations, in: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, 1967, pp. 281–297. URL: https://projecteuclid. org/ebooks/berkeley-symposium-on-mathematical-statistics-and-probability/ Some-methods-for-classification-and-analysis-of-multivariate-observations/chapter/ Some-methods-for-classification-and-analysis-of-multivariate-observations/bsmsp/ 1200512992?tab=ChapterArticleLink. [17] D. Walton, C. Reed, F. Macagno, Argumentation schemes, Cambridge University Press, 2008. [18] P. J. Rousseeuw, Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, Journal of Computational and Applied Mathematics 20 (1987) 53–65. URL: https://www.sciencedirect.com/science/article/pii/0377042787901257. doi:10.1016/ 0377-0427(87)90125-7. [19] A. Peldszus, M. Stede, Joint prediction in mst-style discourse parsing for argumentation mining, in: L. Màrquez, C. Callison-Burch, J. Su, D. Pighin, Y. Marton (Eds.), Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, Lisbon, Portugal, September 17-21, 2015, The Association for Computational Linguistics, 2015, pp. 938–948. URL: https://doi.org/10.18653/v1/d15-1110. doi:10.18653/v1/d15-1110. [20] P. Jaccard, The Distribution of the Flora in the Alpine Zone, New Phytologist 11 (1912) 37– 50. URL: https://nph.onlinelibrary.wiley.com/doi/abs/10.1111/j.1469-8137.1912.tb05611.x. doi:10.1111/j.1469-8137.1912.tb05611.x. [21] J. Nešetřil, P. Ossona de Mendez, Bounded Height Trees and Tree-Depth, in: J. Nešetřil, P. Ossona de Mendez (Eds.), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, Springer, 2012, pp. 115–144. URL: https://doi.org/10.1007/ 978-3-642-27875-4_6. doi:10.1007/978-3-642-27875-4_6. [22] M. Lenz, R. Bergmann, User-Centric Argument Mining with ArgueMapper and Arguebuf, in: Computational Models of Argument, volume 353 of Frontiers in Artificial Intelligence and Applications, IOS Press, Cardif, Wales, 2022, pp. 367–368. URL: https://ebooks.iospress. nl/doi/10.3233/FAIA220176. doi:10.3233/FAIA220176. [23] L. Dumani, M. Biertz, A. Witry, A.-K. Ludwig, M. Lenz, S. Ollinger, R. Bergmann, R. Schenkel, The ReCAP Corpus: A Corpus of Complex Argument Graphs on German Education Politics, in: 2021 IEEE 15th International Conference on Semantic Computing (ICSC), 2021, pp. 248–255. doi:10.1109/ICSC50631.2021.00083.