Graph generators are a powerful tool to provide benchmarks for various sub elds of KR (e.g. abstract argumentation, description logics, etc.) as well as other domains of AI (e.g. resources allocation, gossip problem, etc.). In this paper, we describe a new approach for generating graphs based on the idea of communities, i.e. parts of the graph which are densely connected, but with fewer connections between di erent communities. We discuss the design of an application named crusti_g2io implementing this idea, and then focus on a use case related to abstract argumentation. We show how crusti_g2io can be used to generate structured hard argumentation instances which are challenging for the fourth International Competition on Computational Models of Argumentation (ICCMA'21) solvers.
Graph-based models are widespread in many elds of Knowledge Representation and Reasoning,
including abstract argumentation [
However, until recently, there was an important lack of practical approach for computing
the solutions of argumentation problems. Although there were some algorithmic approaches
proposed in the literature, few pieces of software were actually available for the community.
This has changed (mainly) thanks to the organization of the First International Competition on
Computational Models of Argumentation (ICCMA), in 2015. Since then, some solvers have been
proposed, based either on original techniques dedicated to argumentation frameworks [
In this paper, we propose a new generation method for obtaining community-based graphs
and we apply it to abstract argumentation. Our approach is based on three components: we
rst generate an outer graph which gives a global skeleton for the structure of the generated
instance; then in each node of the outer graph, we generate an inner graph i.e. a community
of nodes; and nally when two nodes of the outer graph are connected, we use a linker to add
some relations between the corresponding inner graphs. We then show how our method can be
applied to generate structured, challenging graphs for argumentation purpose. The added value
of our approach compared to the previous ones lies in its ability to be generic and modular,
since any of the three components can be easily replaced by other versions. In particular, the
outer and inner graphs can be generated through classical generation models like Erdös-Rényi
[
The paper is organized as follows. We rst give some background on abstract argumentation in Section 2, and we introduce the inner/outer model in Section 3. Section 4 presents some related works. Necessary and relevant features of our framework are presented in Section 5, followed by some experiments in Section 6. Finally, Section 7 draws some conclusions and highlights avenues for future work.
An abstract argumentation framework (AF) [
Acceptability of arguments is usually evaluated thanks to the notion of extensions, i.e. sets of
collectively acceptable arguments. Various semantics exist for de ning extension [
Recall that reasoning with AFs is generally hard, with many classical problems at the rst or
second level of the polynomial hierarchy [
We propose a new approach for generating graphs that considers underlying graph structures. More precisely, an outer graph GGO that will be used as a skeleton for the instance is rst constructed from a graph generator GO. Then, each node of this graph is associated with a fresh inner graph (fresh in the sense where nodes of each inner graph are disjoint) built by another generator GI . In order to link inner graphs together, we successively consider each inner graph Gn rooted to a node n of GGO and add edges between it and the inner graphs Gn rooted to a node n when an edge exists in the outer graph between n and n . The nal graph is then the set of inner graphs together with the added edges. Interestingly, such generation process can handle both directed and undirected graphs (with the constraint that the inner graphs generator and the added edges involve edges of the same kind1). However, here we focus on the direcred case, since the goal is to generate argumentation frameworks. Formally, the function in charge of linking inner graphs together in the directed case is de ned as follows: De nition 1 (Directed linker). A linker over directed graphs is a mapping Ld such that, for any G1 = N1, E1 and G2 = N2, E2 : Ld(G1, G2) (N1 N2) (N2 N1).
1Note that the outer graph may be non-directed even when the nal graph is directed: the presence of directed edges may represent a “hierarchical” relation between the communities, while non-directed edges at this level mean that the communities are, in a way, equivalent. 1: GGO 2: for n 3: Gn 4: end for 5: L = 6: for (n, n ) E do 7: L L L (Gn, Gn ) 8: end for 9: return ( n N Nn), ( n N En)
L Algorithm 1 Inner/outer graph generation Input: an outer graph generator GO, an inner graph generator GI and a linker L Output: an inner/outer graph
N, E a GO-generated graph N do
Nn, En a GI -generated graph
Algorithm 1 formalizes our approach. The generation process starts with the generation of the outer graph, i.e. the graph which is used as the skeleton of the instance (line 1). Then, each node of this outer graph is associated with an inner graph which is built by the dedicated graph generator GI (line 3). The rest of the algorithm consists in building some links between the di erent inner graphs, with respect to the structure of the outer graph. To do so, for each edge in the outer graph, the inner graphs associated with the two outer graph nodes under consideration are passed to the linker (line 7); the resulting set of edges is stored. At the end, the algorithm returns the union of the inner graphs plus the edges returned by the linker, producing the nal inner/outer graph.
Our approach o ers the advantage of being exible and allows, for instance, to generate a community graph such that the outer graph is a tree (T ) and inner graphs are Erdös-Rényi graphs (ER). It is also possible to generate paths of Barabási-Albert (BA) graphs, or Watts-Strogatz (WS) graphs made of WS communities, etc.
Example 2. Let us illustrate the generation algorithm with GO = T , GI = ER, and L a function which returns a random set of edges between two graphs. An example of generation process is given at Figure 2. Figure 2a shows the outer graph, which is thus a (non-directed) balanced binary tree. Then, in each node of the tree, an inner graph is generated thanks to the Erdös-Rényi model (Figure 2b). Figure 2c shows the addition of edges between the inner graphs thanks to the linker. And nally, the resulting graph is shown at Figure 2d.
The next sections presents the application we developed to generate inner/outer graphs and
its application to generate AF benchmarks. There already exists tools for generating AFs from
random graph generators. But, from the best of our knowledge, these tools do not modify the
underlying graph generated by these models. In [
Graphs that also consider two additional random graph generator models, which are the Watts-Strogatz (WS) and Barabási-Albert (BA) models. For these two generators the random graphs are used as such. Our tool is much more general than the AFBenchGen family of AFs generators. Indeed, by considering the simple graph consisting in one node as outer graph, it is possible to have the exactly same behaviour.
In [
Once the outer graph has been generated, the inner graphs are linked as follows. For this generation model, the iteration over the set of edges (line 6 in Algorithm 1) is a breadth- rst graph traversal from the root to the leaves of the tree. For each inner graph associated with an outer node o, k nodes are randomly selected (k varies from 5 up to 12 for the benchmarks generated for the ICCMA’21 competition). The descendants {o1, . . . , om} of o are iteratively considered. For each oi, between 20% and 70% of the inner nodes contained in oi are randomly selected. Then, for each node n1 picked in o and with each node n2 picked in oi one of the attacks (n1,n2) or (n2,n1) is added randomly.
In this paper a slightly modi ed version of the tool proposed for generating the ICCMA’21 benchmarks has been considered. Inner graphs are only linked with their children (and not with any of their descendants). Moreover, a ratio of 20% has been considered for selecting the edges that are added between communities (instead of a ratio between 20% and 70% of the nodes).
We built a command line application called crusti_g2io, dedicated to the generation of inner/outer graphs. It is made available under the terms of the GNU GPLv3 on Github account of the Centre de Recherche en Informatique de Lens.2 We took advantage of the Rust programming language to provide an e cient, memory-safe application, even in parallel context. In addition, Rust allows crusti_g2io to be both an application and a library (the project in mainly a Rust library with additional code to create the application). Interestingly, Rust libraries can be turned into C libraries (static or dynamic) or be linked with them. This makes crusti_g2io able to use any library that can be turned into a C library or to be used itself with any program that can load C libraries, allowing for example Go and Python bindings.
The application can be used to generate both directed and undirected graphs. In the following, we describe how to use the application for directed graphs only; however, going from directed to undirected is as simple as replacing directed by undirected in the commands. me@PC:~/crusti_g2io generate-directed -o tree/10 -i er/100,0.5 -l min_incoming -x out.apx -f apx ![INFO ] [2023-03-03 10:54:39] crusti_g2io 0.1.0 [...] ![INFO ] [2023-03-03 10:54:39] generated a graph with 1000 nodes and 24882 edges ![INFO ] [2023-03-03 10:54:39] exiting successfully after 45.6625ms
The rst goal of crusti_g2io is to be easy to install and to use. The only requirement to use it is to have a Rust compiler installed (except of course if you were given an already compiled version); then, executing a standard release build command (cargo build –release) produces the executable (in the target/release directory on UNIX systems). The user can also use the cargo install command to compile and install the program on its computer.
From a user perspective, crusti_g2io is made to be used without looking at its documentation. Calling crusti_g2io -h, (or –help) shows the list of commands and what they do. Calling crusti_g2io with a command and a help ag displays the help message for this command. For example, calling crusti_g2io generate-directed -h explains what generate-directed does, gives its mandatory and optional options (along with their descriptions).
The goal of crusti_g2io is to generate a graph from an outer graph generator, an inner graph generator and a linker, and to output it using a graph output format. Thus, these exact four options form the exact set of mandatory options for the generate-directed command. Again, they can be recalled by typing crusti_g2io generate-directed -h in a terminal. Concerning the lists of the available graph generators, linkers and graph output formats, they can all be retrieved by a crusti_g2io command (respectively generators-directed, linkers-directed and display-engines-directed); calling these commands also indicates how to parameterize the generators, linkers or formats which need it. Figure 3 shows how to build a tree-like outer graph (-o) of 10 inner (-i) Erdös-Rényi graphs of 100 nodes with a probability of 0.5 where links (-l) are created between lowest degree nodes, and export (-x) it in the le out.apx using the apx format (-f). The required parameters for generators and linkers (when needed) are given after a slash and split by commas (see tree/10 and er/100,0.5 in the gure). Embedded graph generators include the famous Erdös-Rényi, Watts-Strogatz and Barabási-Albert models, trees and chains. Concerning the linkers, one is a random one, one links nodes with the least incoming edges, and the last one links the nodes with index 0 — which can have some meaning, in particular if a graph is initialized with a special value like in the Barabási-Albert model. Finally, The Graphviz DOT and GraphML formats are available, just like the abstract argumentation related format APX and DIMACS (from ICCMA 2023).
These generators, linkers and formats are a very small subset of what is o ered by the literature. This is the reason why we tried to make the addition of new content as easy as possible for developers. For example, to add a new generator, it is only required to create a structure that implements the four functions of the dedicated trait and to register it in the set of generators. Concerning the trait, the implementation of three functions out of four is straightforward as they respectively return the name of the generator to be used on the command line interface, the description of the generator, and the types of the expected parameters. The last function is the one dedicated to the generation of graphs: it takes as input the (checked) parameter values as given on the command line interface (i.e. the content following the slash) and returns a closure which takes a pseudo-random number generator (PRNG) and produces a graph. The registration of the new generator consist of adding an import statement and a single line of code. Adding a new linker requires a similar process, except that the closure takes a PRNG and two graphs, and returns a vector of edges. When invoking crusti_g2io, the graph can be printed out on the standard output (this is the default behaviour) or exported to a le. The default behavior mixes log messages and the graph; this can be prevented by hiding the log messages (e.g. by setting the corresponding option) or by exporting the graph to a le. Adding a new output format is similar to adding a new generator or linker.
Finally, crusti_g2io is made to produce reproductible results. By default, it uses an unpredictable random seed; in order to get reproductible results, the user can set the random seed with the -s option on the command line. Regardless of the fact the seed was speci ed or randomly speci ed, it is logged so the results can be reproduced. An e ort was made in order to mix reproducibility and the use of the full power of the computers, as the application computes the inner graphs and the links between these graphs in a parallel fashion. In order to get reproductible results, the program rst computes the outer graph using the global PRNG initialized with the provided seed. Then, each outer node is sequentially associated a random seed using the global PRNG. This way, each inner graph generation process can receive a PRNG which directly depends on the CLI-provided seed, enforcing the reproducibility of the generation for a given seed. The same approach is used for the linking process.
Now, we use crusti_g2io to generate structured AF instances. The goal is to generate overall
instances composed of multiple communities. In addition, we want to generate instances with
a large amount of small communities, but also instances with less communities of a greater
size. To achieve this, we aim at drawing the frontier between hard and too-hard instances for a
set of community sizes, densities and counts. In order to evaluate the di culty induced by the
generated argumentation graphs, we chose to compute extensions (putting acceptance queries
aside) to consider the whole graphs instead of problems that could be related to a reduced area
of the graph. We arbitrary selected a problem of the rst level of the polynomial hierarchy
(SE-ST: compute an extension for the stable semantics) and one of the second level (SE-PR:
compute an extension for the preferred semantics). For both tracks, we used the solvers that
got the best results at the ICCMA’21 competition, namely A-Folio-DPDB3 for the SE-ST track
and µ-Toksia [
In the rst part of our experiments, we sought which sizes of communities are small enough to be part of our graphs. We used crusti_g2io to generate single Erdös-Rényi graphs (by asking for an outer graph composed of a single node) with di erent number of nodes (from 100 to 1000) and probability for each edge to appear (0.1, 0.2 and 0.5). For each setting, we generated 10 di erent graphs by feeding the app with random seeds from 0 to 9; the computation times are averages of these 10 values, and a timeout of at least one makes the average be also timeout. We run experiments on machines equipped with Intel Xeon E5-2637 v4 processors and 128GB of RAM, and the timeout was xed to 600s, as in ICCMA’21. Table 1 shows some experimental results.
First, we can note that for a given number of nodes, instances are more di cult for lower Erdös-Rényi probability values. This may be explained by the lower number of constraints, making preferred extensions admit more arguments, and stable extensions less common. This hypothesis would require further investigation, but is o -topic here since we are only interested in the di culty of the instances.
Communities of 100 arguments seem easy for both SE-ST and SE-PR, whatever the probability setting. With a setting of 0.1, the problems begin to require multiple seconds to be solved for 200 nodes; this value should not be exceeded for instances involving several communities. A single community of 300 nodes cannot be solved in this context. With a setting of 0.2, the limit in terms of number of nodes to consider for multiple communities seems to be between 200 and 300; for this value, a single community requires more than 10 seconds for SE-ST, and more than 20s for SE-PR. A setting of 0.5 allows to generate instances with a single community of at least 1000 nodes. Interestingly we remarked that in this case, all instances admit stable extensions, which is not the case for the other probability settings. This indicates that these instances have a special structure that might make solvers work di erently on them. Finally, as expected, the SE-PR problem takes more time to be solved than SE-ST.
Now that we have bounds on the size of the communities to consider, we can experiment the di culty induced by the number of communities. We generated complete binary trees of Erdös-Rényi communities, where each community is linked to the ones associated with its children.
For this second experiment session, we considered Erdös-Rényi with nodes between 100 and 500 with the same three probability settings. We assumed the multiplicity of the communities 3https://github.com/gorczyca/dp_on_dbs/tree/competition
ER nodes
SE-ST (s)
SE-PR (s) 0,1 0,2 0,5 100 200 300 400 100 200 300 400 100 200 300 400 500 600 700 800 900 1000 0,01 3,13 — — 0,02 1,85 13,87 — 0,01 0,10 0,14 0,23 1,81 4,28 3,34 6,72 11,27 14,32 0,03 9,14 — — 0,02 4,13 22,91 — 0,02 0,07 0,37 4,11 13,97 16,56 41,23 74,41 141,24 67,37 would make the instances very hard for the 0.5 probability for more than 500 nodes per community. We considered (directed) outer tree heights from 3 to 9, making the outer graphs contain from 7 to 511 nodes. For each setting, 10 instances were generated with random seeds going from 0 to 9. We used to same machines and timeout than before. Figures 4 and 5 report the interesting parts of these new results. The plots on Figure 4 correspond to the results for the SE-ST track, while Figure 5 reports the results for SE-PR. For each gure, the three sub gures are each associated with a density setting (0.1, 0.2 and 0.5). For each sub gure, the average computation time is given on the y-axis, while the x-axis gives the number of communities; the lines gives the di erent community sizes.
We rst focus on the SE-ST results, given by the plots at Figures 4a, 4b and 4c. Concerning the results of µ-Toksia 2021 for the 0.1 probability setting (Figure 4a), we can observe that the problems are too easy when the number of nodes per community is lower than 200 (all solved in few seconds even for 511 communities) and too hard when it is above this value (such problems cannot be solved when there are more than 31 communities). Thus, this setting does not allow us to draw a clear frontier between the hard and the too-hard instances. This is also the case for the 0.5 probability setting (Figure 4c) for which the instances are surprisingly very di cult even for low values of community sizes and community counts. This is not an unexpected result since as noted below, these instances have a special structure that might prevent µ-Toksia to solve them. By the way, we discovered that µ-Toksia was not able to prove the absence of stable extension in any community-based instance with this density. If such instances are included in our benchmarks, then µ-Toksia may su er from this special kind of instances. Fortunately, the 0.2 case (Figure 4b) perfectly ts our needs of frontier as it shows multiple settings of community sizes and counts are solvable but di cult (hundreds of seconds required to solve) namely the sets of 511 communities of size 225, the sets of 255 communities of size 250 and the sets of 63 communities of size 275.
Now, we discuss the SE-PR results, given by the plots at Figures 5a, 5b and 5c. Just like for SE-ST, the 0.1 probability setting (Figure 5a) does not seem to be an interesting value for us since little changes in community sizes makes the di culty a lot higher: see e.g. the di erence between communities of 175 nodes — almost di cult instances when there are 511 of them — and 200 nodes — where instances are too di cult for 255 communities. Things are a little better for the 0.2 probability (Figure 5b) when considering communities of size between 225 and 300, but the real interesting setting in this case if the 0.5 probability (Figure 5c). In this case, we can nd at least three cases of di erent community sizes for which hard instances exist: the sets of 511 communities of 175 nodes, the sets of 255 communities of 300 nodes and the sets of 127 communities of 500 nodes.
To conclude this section, it is worth noting that crusti_g2io generated the instances very fast. For the graph generation, we took advantage of machines with a higher number of processor cores. We dedicated to each process an Intel Xeon Gold 6248 (a 20-cores processor) and 192GB of RAM. The biggest instances we considered are the ones with 511 communities of 500 nodes with a probability setting of 0.5, for which the graph admits 255500 nodes and more than 89 millions edges. For these instances, the graph generation itself took less than 4s each. A little longer was necessary to translate the graphs into argumentation frameworks and store them using the (verbose) APX format on the hard disk. With these additional translation and writing times, the average wall-clock time was 19.62s.
In this paper, we have de ned a new approach for generating (directed or non-directed) graphs based on the concept of communities, which are graphs where some subparts of the graph are highly connected, but are loosely related to other subparts. Our approach uses a so-called inner/outer template, i.e. we rst generate an outer graph representing the global structure of the graph, then in each node of the outer graph we generate an inner graph, and nally we use a linker to add edges between nodes of inner graphs which are connected in the outer graph structure. The proposed model is particularly generic and modular, since all the components (outer graph generator, inner graph generator and linker) can be replaced by other generators or linkers. Our model is particularly well suited for abstract argumentation, since large debates (i.e. large argumentation frameworks) can naturally be split into sub-debates which are only connected by a few arguments and attacks. We have described our opensource tool for the generation of graphs, and especially we have shown that this tool allows to generate meaningful argumentation framework instances with a level of di culty for standard computational problems which can be adapted thanks to the choice of some parameters.
Several avenues for future work can be highlighted. Regarding the tool, a natural development (a) SE-ST, E R probability of 0.1
(b) SE-ST, E R probability of 0.2 (c) SE-ST, E R probability of 0.5 direction is to design an even more generic framework, allowing several levels of nested graphs (i.e. the inner graph generator could generate graphs which also follow the inner/outer template). We also plan to improve the usability of the tool by describing the generation task in les (using e.g. the YAML or JSON format) instead of the command-line interface.
Regarding the issue of AF generation, we can improve the relevance of the tool by
incorporating linkers which make sense in the context of abstract argumentation frameworks (for
instance, we could add edges concerning in priority arguments which are skeptically accepted
w.r.t. some given semantics). Another interesting future work consists in proposing generation
models for more complex argumentation frameworks, which would require e.g. graphs with
di erent kinds of edges or arguments (to incorporate supports [
This work has been partly supported by the CPER DATA Commode project from the “Hauts-deFrance” Region, the ANR projects PING/ACK (ANR-18-CE40-0011) and AGGREEY (ANR-22CE23-0005).