In this paper we introduce EqArgSolver, an argumentation solver using equational semantics. EqArgSolver is based on the prototype GRIS submitted to the first International Competition on Computational Models of Argumentation, but provides two major advancements over GRIS. Firstly, it uses the much more e cient discrete version of the Gabbay-Rodrigues Iteration Schema [7], and secondly, it requires at most 1/8 of the memory footprint per node used by GRIS. Experimental results show that EqArgSolver runs up to 12⇥ faster than GRIS and is able to handle a much larger class of argumentation graphs.
1. Introduction
One of the most important tasks in argumentation theory is the reasoning about
the status of arguments in a given argumentation framework hS, Ri. This can be
done according to several semantics mainly using the concepts of an extension or
a labelling function that assigns a label from {in, out, und} to each argument in
S. The two concepts are interchangeable, as an extension can be obtained from a
labelling function and vice-versa. A third way of giving semantics is via Gabbay’s
equational approach [
In [
One disadvantage of the use of the schema in the computation of argumentation semantics is the need to determine the values in the limit of the sequence. In a computer, this can only be approximated by iterating su ciently many times until one can be satisfied that the approximated values correspond to the values in the limit. With this in mind, GRIS performed relatively well as a proof of concept, but left open a number of theoretical and technical questions about the use of the schema in more intensive argument computation tasks.
In [
This paper describes the basic theoretical underpinnings of the discrete version of the schema and the technical details involved in its implementation in EqArgSolver. In experimental results, EqArgSolver performed up to 12⇥ faster than GRIS and was able to handle much larger argumentation networks.
As for GRIS, EqArgSolver can be used in the solution to the following classes
of problems. Given an argumentation network hS, Ri: to produce one or all of
the extensions of the network under the grounded and preferred semantics; and
given an argument X 2 S to decide whether X is accepted credulously or
sceptically according to one of these two semantics. Problems to EqArgSolver must
be submitted according to probo’s syntax (see [
The rest of the paper is organised as follows. Section 2 provides a basic
background, including the main theoretical underpinnings on which EqArgSolver is
based. Section 3 provides an overview of the implementation of EqArgSolver. This
is followed by a comprehensive example illustrating the computation steps in
Section 4. The performances of EqArgSolver and GRIS are compared in Section 5.
Finally, Section 6 concludes the paper giving some directions for future work.
2. Background
In [
Vi(X)) · min {1/2, 1
M Ai(X)} + Vi(X) · max {1/2, 1
M Ai(X)}
To facilitate the explanations in the rest of this paper, if V : S !7 [
Take the initial configuration of values V0 and for each i 0 and X 2 S,
let the value Vi+1(X) be calculated from Vi(X) according to the schema above.
In [
Obviously, in order to use the schema, one needs to find a way to determine the equilibrium values in a finite number of computations. In GRIS, each iteration i computes the values Vi(X) of all nodes X from the values Vi 1(X). The more one iterates, the more this value approximates the real value Ve(X). As a result, the number of nodes and edges in the network and the precision required in the approximation of the limit values all have a direct e↵ ect on GRIS’ overall execution time. Optimising the e ciency of the approximation of the value Ve(X) was hence an important objective of any future implementation using the equational semantics.
In [
Definition 2.1 Let N = hS, Ri be an argumentation framework and V0 be an assignment of values from {0, 1/2, 1} to the nodes in S. The Discrete GabbayRodrigues Iteration Schema is defined by the following system of equations (Td), where the value Vi+1(X) of each node in iteration i + 1 is defined in terms of the values of the nodes in iteration i as follows:
Vi+1(X) = 1
Y 2 Att(X){Vi(Y )} max (Td)
The following correspondence between numerical values and argument labels will prove useful.
Definition 2.2 (Caminada/Gabbay-Rodrigues Translation) A labelling function and a valuation function V can be inter-defined by identifying the value 1 with the label in, the value 0 with the label out, and the value 1/2 with the label und.
Caminada and Modgil’s algorithm [
In what follows, we will refer to a valuation V defined from a labelling function by V and to a labelling function obtained from a valuation V by V .
The discrete version of the schema can be used in several computational tasks. For instance, it allows to quickly check whether a given assignment yields a complete extension, as seen below.
Theorem 2.1 [7, Theorem 4] Let hS, Ri be an argumentation framework and Vi an assignment of values from {0, 1/2, 1} to the nodes in S. Vi is a complete labelling function if and only if Vi+1(X) = Vi(X), for all X 2 S.
Remember that there is a direct correspondence between the nodes assigned the label in by a complete labelling function and a complete extension. It is easy to see that the complexity of the checks in Theorem 2.1 is not higher than that of the checks performed using labelling functions and that the checks can be implemented in a single loop through all relevant nodes. However, the checks in Theorem 2.1 can be implemented very e ciently because of the arithmetic nature of the operations.
Gabbay and Rodrigues have shown in [
More details of the utilisation of the discrete schema are discussed in the
following section.
2.1. Using the Discrete Gabbay-Rodrigues Iteration Schema in the Computation
of Argumentation Semantics
It is well known that several semantics of an argumentation framework hS, Ri can
be computed by decomposing the network into layers [
For example, layer 0 of the network in Figure 1 contains the two non-trivial
SCCs SCC1 = {A, B} and SCC2 = {C, D} and the collection of trivial SCCs
SCC3 = {G} and SCC4 = {H}. Layer 1 contains the non-trivial SCC SCC5 =
{E, F }. The intuition here is that the computation of the statuses of the nodes in
a layer of higher order depends on the computation of the statuses of the nodes
in the layers of lower orders. In our example, one can see that the statuses of E
and F can only be computed given the statuses of B and C. The statuses of the
nodes in the trivial SCCs G and H can be computed in sequence within the same
layer. An excellent explanation of this technique can be found in [
A
B
E
F
C
D
G
H
In the computation of the grounded semantics, all that is needed in the calculation of the result of a non-trivial SCC C is the propagation of the results of the nodes in the previous layers on which C depends (if there are any). For example, since there are no prior dependencies in the SCCs in layer 0, the first SCCs involved in the computation of the semantics of the network of Figure 1 are SCC1, SCC2, SCC3 and SCC4. The only undisputed nodes in any network are the ones with no attackers. These get value in. The nodes in cycles at layer 0 all get value und. These values are then propagated down the layer until all nodes in the layer get a value.
With this in mind, the nodes in the non-trivial SCCs of layer 0 get the (unique) solution: A = und, B = und, C = und, D = und. Since G has no attackers, it gets value in. When this value is propagated to H, it gets value out, yielding the solution G = in, H = out for the trivial SCCs in layer 0.
In [
The schema guarantees a correspondence between the nodes in the grounded extension and those with final value 1.
Note that since the non-trivial SCCs in a layer are independent from each other, we can use Equation (Td) in each one of them independently3 to obtain all the partial solution(s) to a layer. The computation of layers of higher order pose no problems either. All that needs to be done is to propagate the final values of the nodes of lower order in a given solution to the nodes that they attack.
The example below illustrates these ideas.
Example 2.1 Consider SCC1 = {A, B} and give its nodes initial value 1/2 at iteration 0. The sequence of values in the discrete scheme immediately converges since the values of all nodes in the SCC remain the same at iteration 1. Therefore 1/2 is the final values of A and B. The reasoning for the SCC2 = {C, D} is the same with both nodes also getting final value 1/2.
Now consider the collection of trivial SCCs SCC3 and SCC4, whose nodes are also given initial value 1/2 at iteration 0. The value of G at iteration 1 becomes 1, whereas the value of H remains 1/2. At iteration 2, the value of G remains 1 and the value of H becomes 0. These values then remain the same at every 2The sequence will converge in time linear to the number of nodes in the SCC being computed. 3In fact, we could do this in parallel, although this is not currently used in EqArgSolver. successive iteration, giving final solution G = 1 and H = 0. This completes the computation of this layer.
Proceeding to layer 1, it is easy to see that E and F also get final value 1/2 and therefore the unique solution for the whole network is:
A = und, B = und, C = und, D = und, G = in, H = out, E = und, F = und This corresponds exactly to the grounded extension of the network.
Given a solution to a layer, the discrete schema correctly propagates the solution’s values to the appropriate nodes in a layer of higher order. For instance, in the calculation of the solution to layer 1, the relevant nodes in layer 0 are B and C. Therefore, given partial solution A = out ⌘ 0, B = in ⌘ 1, C = out ⌘ 0 and D = in ⌘ 1, we start the schema with initial values B = 1, C = 0, and E = F = 1/2. In iteration 1, we get that E = 0, F = 1/2. In iteration 2, we get E = 0 and F = 1. The values then converge and we get the final solution A = out ⌘ 0, B = in ⌘ 1, C = out ⌘ 0, D = in ⌘ 1, E = out ⌘ 0 and F = in ⌘ 1, which yields an extension.
The above ideas constitute the basis of the GR Grounder module (see Fig. 2).
A second module is responsible for generating preferred solutions. This works
basically by applying the grounder to a SCC and then checking whether nodes
with undecided values remain. If this is the case, then we may attempt to break
cycles down by making some nodes in the cycle in and then propagating the
results to layers of higher order. This component of the solver follows a similar
algorithm to that of Sanjay and Caminada [
As we mentioned in the Introduction, EqArgSolver is currently limited to the grounded and preferred semantics. The basic workflow for the computations involving problems in these semantics is depicted in Fig. 2, with the exception that in the grounded semantics, intermediate preferred solutions do not need to be generated and so the preferred solutions generator is not used and the partial preferred solutions data store only contains one solution. All solutions are kept in memory.
The solver receives a number of parameters as arguments in the command
line following probo’s syntax [
SCCs/ layers Layers argument partial solutions input problem problem specification
Validator graph file valid problem and graph Argument Acceptability checker
result Yes/No partial preferred solution pPreafretriraeld Psorleufteirorneds solutions partial solutions generator unbdaseecidsoeldutnioondses GR Grounder layer
SCCs previous layer
solutions base solutions
no more layers
Extensions solution generated in a skeptical decision problem (or “Yes” if the argument is accepted in a partial solution in a credulous decision problem).
We now detail some of the particularities in the computation of the grounded and preferred semantics.
Grounded Semantics. For the computation of the solutions to the problems involving the grounded semantics, the decomposition of the network into layers is not strictly necessary. The Grounder module based on Equation (Td) can be applied to the entire network at once and the nodes with equilibrium value 1 will correspond to its grounded extension. However, since the decomposition of the network into layers can be performed very e ciently in our implementation, this extra cost is o↵ set by gains obtained through the computation by layers in all but a few special cases. Our strategy for the grounded semantics is then to feed the result of each layer into the next layer’s computation until either all layers are computed (e.g., in an enumeration problem) or we reach the minimum necessary depth for an answer (e.g., in an argument acceptance check).
Preferred Semantics. As we have seen, the solution of problems involving the
preferred semantics involves the computation of partial network solutions for each
layer. Each of these solutions needs to be propagated and adequately combined.
The key point in EqArgSolver’s implementation is that after the grounder module
is invoked for a particular SCC (using all required values from previous layers),
some nodes in the SCC may still be left with value und. These nodes could
potentially be assigned the value 1 in a preferred extension. So our (naive)
implementation at this stage simply assigns the value 1 to all such nodes and then corrects
illegal values in a manner which is the numerical counterpart to the Caminada and
Modgil’s labelling-based algorithm [
There is still ample scope for optimisation. For instance, in decision problems, a careful analysis of the argument involved may identify partial solutions of particular interest without the need to generate all partial solutions (the blind generation of partial solutions can quickly exhaust resources in highly complex networks).
Solutions to the problems in the complete and stable semantics are not currently supported may also be computed with appropriate modifications. A quick and easy way to do so for the complete semantics is to generate all intermediate solutions by invoking the grounder module at key points (each invocation resulting in an intermediate complete extension). Similarly, a simple check at the end of the preferred solutions generation can identify if an extension is stable. Similarly, it can quickly abandon a partial solution when nodes are left with value und. These considerations will be taken into account in the development of the full version of EqArgSolver for the next international competition. 4. A Comprehensive Example This section provides a comprehensive example illustrating the ideas discussed so far. For this, the sample network shown in Figure 1 will be used again.
Initially, the graph is decomposed into SCCs and each SCC is assigned a layer. In this example, the decomposition generates two layers as explained in Section 2.1. These two layers are then processed as follows.
Phase 1: Apply the discrete version of the schema to the SCCs SCC1, SCC2 and SCC3 and SCC4 in layer 0 giving initial value 1/2 to all nodes.
The tables below show how the values of the nodes evolve through the iterations of the schema. The subscript i in Vi indicates the iteration number. A value in bold has converged and will no longer change. The computation can stop when all values in a SCC have converged.
A 1/2 B 1/2 V1 1/2 1/2
C 1/2 D 1/2
G 1/2 H 1/2
V1 1 1/2
V2 1 0
V3 1 0 V1 1/2 1/2
If the problem at hand only involves the grounded semantics, all we have to do next is to run the discrete schema again giving value 1/2 to all nodes in layer 1 and keeping the values computed above for the nodes in layer 0. It is easy to check that the values of E and F will remain 1/2. Since layer 1 is the last layer, this is the only solution and the grounded extension contains the only node with value 1, i.e., G. The upshot of all this is that, strictly speaking, there is no need to decompose the graph into layers in grounded semantics problems. The grounded extension can be computed for the whole graph by calculating the final values of all nodes in one fell swoop. In earlier experiments, the di↵ erence in execution time for the computation of the grounded extension with or without decomposition into layers was negligible. However, decomposition o↵ ers a definite advantage in decision problems involving large graphs and arguments appearing in shallow layers. Of course one can only identify the layer of an argument by performing the decomposition itself and since the decomposition algorithm is very e cient, this is the strategy used in EqArgSolver.
We now proceed to explain the steps taken for the preferred semantics. Phase 2: Generate partial preferred solutions to layer 0.
Some SCCs may still be left with undecided nodes after applying the discrete
schema to a layer. In this example, both SCC1 and SCC2 are left with undecided
nodes. For each such SCC, a version of Caminada and Modgil’s algorithm for
finding preferred extensions is then applied (see [
Note that for decision problems involving the acceptance of an argument belonging to layer 0 the correct answer can already be given without the need to proceed to layer 1.
Phase 3: Propagate the partial solutions found for layer 0 into layer 1. We say that we “ground” layer 1 with a base solution found for layer 0. The equations for the nodes in layer 1 are: Vi+1(E) = 1 max{Vi(B), Vi(F )}; and Vi+1(F ) = 1 max{Vi(C), Vi(E)}.
As before, the values of all nodes in the layer itself are initialised to 1/2, giving V0(E) = V0(F ) = 1/2. Since the equations involve nodes belonging to layer 0, they are computed using as initial values the final values of these nodes found in each partial solution to layer 0. These partial solutions are called the base solutions of the solutions to this layer. This yields S11–S41 below:
S11 V0 V1 V2 V3 B 0 0 0 0 C 1 1 1 1 E 1/2 1/2 1 1 F 1/2 0 0 0
S21 V0 V1 V2 B 0 0 0 C 0 0 0 E 1/2 1/2 1/2 F 1/2 1/2 1/2
S31 V0 V1 V2 B 1 1 1 C 1 1 1 E 1/2 0 0 F 1/2 0 0
S41 V0 V1 V2 V3 B 1 1 1 1 C 0 0 0 0 E 1/2 0 0 0 F 1/2 1/2 1 1 Phase 4: As before, for each solution to a SCC in layer 1 where undecided nodes remain, search for possible partial preferred solutions. Any solution found in this way needs to be “vertically” combined with the base solution that originated it.
In our example, only S21 leaves some nodes with undecided values in SCC SCC5 = {E, F }. There are 2 partial preferred solutions to this SCC with values E = 1 and F = 0, and E = 0 and F = 1, respectively. Combining them vertically with the solution S20 yields the two preferred solutions S21.1 and S21.2. The set of all preferred solutions with their corresponding preferred extensions is then given below. {A, C, E, G} {A, D, E, G} {A, D, F, G} {B, C, G} {B, D, F, G}
In the next section, we discuss the results of some experiments we have done
in order to compare the performance gain obtained via the use of the discrete
schema over its full-fledged version.
5. Empirical Evaluation
The performance of EgArgSolver was compared with that of GRIS’ using probo’s
benchmark suite [
All test results show a large performance gain of EqArgSolver over GRIS. The largest gains, as expected, are in the problems that depend more directly on the grounding module. In Figure 3, we can see that EqArgSolver is up to 12⇥ faster than GRIS both in enumeration and decision problems in the graphs
GRIS EqArgSolver
GRIS EqArgSolver 1400 1200 )s 1000 m ( ivTeg 860000 m A 400 200 0 250 200 ) (sem 150 iTgm 100 vA 50 0
GRIS EqArgSolver
GRIS EqArgSolver generated by probo’s Grounded generator. The execution time is slightly higher in the decisions problems, although not very significantly so.
Figure 4 shows the statistics for the enumeration problems in the grounded semantics (L) and for the decision problems in the preferred semantics (R) using graphs generated by probo’s SCC and Stable generators. There are still performance gains in all problems especially in the enumeration ones, but there is now less variation between GRIS and EqArgSolver in the decision problems. This is likely due to the fact that the types of graphs in this class of tests benefit less from gains in performance of the grounding module.
These preliminary results, admittedly over a small sample, are very
encouraging and serve to clearly demonstrate the advantages of using the discrete version
of the schema over its full-fledged version.
6. Conclusions and Discussion
With GRIS, we showed that we could successfully use numerical methods in the
solution of computational problems of traditional argumentation semantics. GRIS
used the full version of the Gabbay-Rodrigues Iteration Schema, put forward
in [
In [
We used the discrete version of the schema in the implementation of EqArgSolver and made a number of data representation improvements. For instance, given that the discrete version of the schema only uses the values {0, 1/2, 1}, we multiplied all equations by 2 in the implementation, shifting the values to the set {0, 1, 2}. This allowed us to use the smallest available native data type in C++, i.e., char, which is only 8 bits long (as opposed to GRIS’ double which is 8 bytes long). This allowed for an immediate 8-fold reduction in the memory requirements. In general, these improvements resulted in a vast gain in performance as described in Section 5.
There is, of course, much more work to be done. We need to incorporate intermediate checks in the generation of preferred extensions to deal with problems in the complete and stable semantics.
We have been running benchmarks over a much larger sample of graphs and have identified areas where performance can be improved. In particular, the search for a solution to some decision problems can be made more e cient, by carefully employing strategies specifically tailored to the problem at hand.
Finally, the computation of solutions to the problems in the preferred semantics can be further improved by designing a more e cient algorithm for maximisation of accepted nodes. This is currently work in progress.