such as simulated annealing approaches (SA), tabu-serch, genetic algorithms or evolutionary computing [4]. Quantum annealers and Fujitsu’s digital annealers1 can be used to find global minima by using quantum fluctuations . QUBO models are at the heart of experimentation with quantum computers built by D-Wave Systems.2
In this paper, we focus on the problem of enforcing an extension: an agent may be interested in determining arguments to be added to enforce the set of arguments they prefer. Such enforcement is helpful in many scenarios, particularly when considering an argumentative debate between several agents because the arrival of new arguments in the debate typically questions the existing extensions. However, in many other situations, no new arguments are available to explain the change, and one is forced to evaluate the arguments’ attacks on one another. Several of these problems have been proven NP-complete [5]; hence, they represent a perfect setting for proposing an encoding to QUBO as we advance in this work.
Some preliminary results on Abstract Argumentation and QUBO have been proposed in [6]. Section 2 reports necessary background information on Argumentation and QUBO, then Sect. 3 describes the encoding of extension-enforcing into QUBO. Section 4 highlights the interest in approximate solvers in Abstract Argumentation by introducing a dedicated international competition. While QUBO problems can also be solved with classical annealers, our ultimate interest is represented by using quantum annealers (as tested in [6]), or more in general, to bring Argumentation-related problems to the quantum world. Finally, Sect. 5 wraps up the paper with final thoughts and ideas about possible future work.
This section summarizes the necessary background information regarding Abstract Argumentation and QUBO.
An Abstract Argumentation Framework (AF, for short) [1] is a tuple ℱ = (A, ) where A is a set of arguments and is a relation ⊆ A × A. For two arguments , ∈ A, the relation means that argument attacks argument . An argument ∈ A is defended by ⊆ A (in ℱ ) if for each ∈ A such that there is some ∈ such that . A set ⊆ A is conflict-free (cf in ℱ ) if and only if there are no , ∈ with . is admissible (ad in ℱ ) if and only if it is conflict-free and each ∈ is defended by . Finally, the range of in ℱ , i.e., +, collects ℱ the same and the set of arguments attacked by : + = ∪ { ∈ A | ∃ ∈ : }. ℱ
The collective acceptability of arguments depends on the definition of diferent semantics [1]. Semantics determine sets of jointly acceptable arguments, called extensions, by mapping each ℱ = (A, ) to a set (ℱ ) ⊆ 2A, where 2A is the power set of A, and parametrically stands for any of the considered semantics. The extensions under complete (co), preferred (pr), semistable (sst), stable (st), and grounded (gr) semantics are defined as follows; given ℱ = (A, ) and a set ⊆ A: 1Fujitsu’s digital annealer: https://www.fujitsu.com/global/services/business-services/digital-annealer/. 2D-Wave website: https://www.dwavesys.com.
• Verification of an extension (VER- ): given ℱ = (A, ) and a set of arguments ⊆ A, is ∈ (ℱ )? • Credulous acceptance of an argument (DC- ): given ℱ = (A, ) and an argument ∈ A, is contained in some ∈ (ℱ )? • Skeptical acceptance of an argument (DS- ): given ℱ = (A, ) and an argument ∈ A, is contained in all ∈ (ℱ )? • Existence of an extension (EX- ): given ℱ = (A, ), is (ℱ ) ̸= ∅? • Existence of non-empty extension (NE- ): given ℱ = (A, ), does there exist ̸= ∅ such that ∈ (ℱ )?
In addition, the work in [7] presents the task of extension enforcement: we consider the objective to change the attack relationship of a framework ℱ = (A, ) such that a given set ⊆ A becomes (a subset of) an extension under a given semantics . In this case, the enforcement is argument-fixed , since only the attack relationship can be modified. Strict enforcement is satisfied if is a -extension, while in non-strict enforcement is only required to be a subset of a -extension. If we consider the Hamming distance of the changes, i.e., |∆ ′| = | ∖ ′| + |′ ∖ |, in [7] the authors impose a threshold |∆ ′| ≤ as a further parameter of these problems. The complexity of some of these problems is reported in Tab. 2.
Admissible Complete Preferred
Stable Grounded strict
P
P NP-c ∑︀2 -c NP-c non-strict
NP-c NP-c NP-c NP-c NP-c
A, and semantics , strict extension enforcement is * ∈
argmin ′∈enfst(ℱ,, ) |∆ ′| problem by considering non-strict enforcement (by defining enfnst ). where enfst (ℱ , , ) = {′|ℱ ′ = (A, ′), ∈ (ℱ ′)}. Similarly, we can define the same
Quadratic Unconstrained Binary Optimization (in short, QUBO) [8] is an important form of optimization problems which has recently gained great popularity because of fast solvers and dedicated computing devices, such as quantum and digital annealers. Hence, several optimization problems, in a large range of application domains, have been formulated as QUBO problems, to be solved by these new methods [8, 9]. diagonal matrix and consists in minimizing the function
QUBO has been intensively investigated and is used to characterize and solve many optimization problems. For example, it encompasses SAT Problems, Constraint Satisfaction Problems, Maximum Cut Problems, Graph Coloring Problems, Maximum Clique Problems, General 0/1 Programming Problems and many more [8]. There exist QUBO embeddings also for Support Vector Machines, Clustering algorithms, and Markov Random Fields [10].
A QUBO problem is defined in terms of binary variables 1, . . . , and a × upper =1 < () = ∑︁ , + ∑︁ , .
The diagonal terms , are the linear coeficients and the non-zero of-diagonal terms , are the quadratic coeficients. This can be expressed more concisely as
min ∈{0,1} where denotes the transpose of the vector .
The formulation of a discrete constrained optimization problem as QUBO requires the following steps: i) find a binary representation for the solutions, ii) define a penalization function, which penalizes unfeasible solutions (i.e., violating a constraint).
In [6], we proposed for the first time an encoding of two well-known NP-complete problems in Abstract Argumentation as QUBO problems: DC- and Exists- ¬∅, while the considered semantics was only co. Moreover, in [6], we solved this problem on some frameworks by directly implementing them using the D-Wave Ocean SDK. We used a SA algorithm and a real quantum annealer provided by the LeapTM Quantum Cloud Service.3
Concerning [6], by continuing on this research line, we have extended the encoding to all classical NP-complete problems highlighted in bold in Tab. 1. Moreover, we have empirically validated all the encodings by comparing the obtained results with the simulated annealing algorithm against ConArg [11], an exact solver using Constraint Programming.
In this section, we describe the basics of the encodings that lead to the model of the complete semantics, which will be at the core of enforcing complete extensions in Sect. 3.2.
We first assign to each argument an index, hence A = {1, . . . , }, where is the number of arguments. We use a set of binary variables 1, . . . , to represent a set of arguments: ∈ if and only if = 1. We denote by x the tuple (1, . . . , ) and by x ∈ {0, 1} a vector of possible values for 1, . . . , . Each semantics will be associated with a quadratic penalization function (or Pfunction for short) such that assumes its minimum value at x if and only if the corresponding set = { ∈ A : = 1} is an extension valid for .
Most of the argumentation semantics require admissible sets. Hence, we define a Pfunction , which enforces this property. is the sum of four terms and contains new additional variables. The first term forces the set to be conflict-free : = ∑︀ or . In fact, the value of corresponds to the number of self attacks in and its value is 0 if and only if is conflict-free.
The constraints to model the notion of defense are more complicated: we use a first set of additional variables 1, . . . , , denoting which arguments are attacked by : = 1 if and only if some argument of attacks . The variables 1, . . . , of the second set denote which arguments are defended by : = 1 if and only if is defended (from all the possible attacks) by some arguments of . For each argument , the Pfunction forces to be 1 if and only if is attacked by , i.e., = ⋁︀ .
Let ℎ be the number of attackers of and let 1, . . . , ℎ be their indices. If ℎ = 0, then is simply 0, while if ℎ = 1, then = ℎ1 : in these cases, we set = 0. If ℎ = 2, then = (, [1], [2]), where (, , ) = + + + − 2( + ) is the way of expressing as a quadratic function the constraint that the binary variable is the disjunction of the binary variables and , as shown in [12]. Finally, if ℎ > 2, then = (, [1], 1 ) + ( 1 , [2], 2 ) + . . . +( ℎ− 3, [ℎ− 2], ℎ− 2) + ( ℎ− 2, [ℎ− 1], [ℎ ]),, where 1 , . . . , ℎ− 2 are ℎ − 2 auxiliary binary variables.
The other Pfunction forces to be 1 if and only if is defended by , i.e., = ⋀︀ . If ℎ = 0, then is simply 1, while if ℎ = 1, then = ℎ1 : in these cases, = 0. If ℎ = 2, 3D-Wave Ocean SDK: https://github.com/dwavesystems/dwave-ocean-sdk. then = (, [1], [2]), where (, , ) = 3 + − 2( + ) is the way of expressing the conjunction = and as a quadratic function [12]. Otherwise, if ℎ > 2 then = (, [1], 1) + ( 1, [2], 2) + . . . + ( ℎ− 3, [ℎ− 2], ℎ− 2) + ( ℎ− 2, [ℎ− 1], [ℎ ]), where 1, . . . , ℎ− 2 are new ℎ − 2 auxiliary binary variables.
The number of auxiliary variables needed for this encoding is = 2 + 2 ∑︀ =1 max(ℎ − 2, 0), excluding the variables 1, . . . , . Note that, if ℎ = max ℎ, then = (ℎ). The ifnal term = ∑︀=1 (1 − ) forces each argument in to be defended by . Summing up, the Pfunction for admissible sets is = + ∑︀=1 + ∑︀=1 + . It is easy to prove that the minimum value of is 0, and the related values for x correspond to admissible sets. For the complete semantics, we need to add term to which forces all the arguments defended by to be elements of : = + ∑︀ =1(1 − ).
An important subject that emerged in the literature in the last years concerns changes in AFs. In particular, attention has been paid to the problem of enforcing a set of arguments, i.e., ensuring that is an extension (or a subset of an extension) of a given framework ℱ .
The task of extension enforcement can be formulated with similar techniques. Let us focus on the strict version of this problem, concerning the complete semantics (see Tab. 2). To simplify the notation, the arguments in the set are the first arguments 1, . . . , in A.
We use a first set of binary variables , for , = 1, . . . , . Each variable is 1 whether in the new attack relationship ′, attacks . Moreover, we use the binary variables , for = 1, . . . , , and , for = 1, . . . , , as in the encoding of the acceptance.
We define a Penalty function , which is zero if and only if is a complete extension under the attack relationship described by . is the sum of 5 terms.
The first term = ∑︀,=1 . enforces the set to be conflict-free, in fact when = 1, with , ≤ , we have a self attack in .
The second term is = ∑︀=1 ,, where ,, for each = 1, . . . , , enforces the constraint = ⋁︀
=1 , which means that = 1 if and only if the argument is attacked by some argument ∈ . This term is encoded in QUBO using auxiliary binary variables, similar to what is done for .
The third term is = ∑︀=1 ,, where ,, for each = 1, . . . , , enforces the constraint = ⋀︀=1( =⇒ ), which means that = 1 if and only if the argument ∈ is defended against all its attackers by some elements of . This term is encoded in QUBO using a new set of auxiliary variables to represent the implication ( =⇒ ), other than the same auxiliary variables used for .
The fourth term is simply ∑︀
=1(1 − ), which requires that all arguments in are defended, while the last term is ∑︀
=+1 , which add a penality for each argument defended by , but not belonging to .
The overall objective function to be minimized is = ∑︀ (1 − ) + ∑︀¬ + , where is a constant large, such that the minimum of is obtained for = 0.
In the literature, we find many computational techniques and practical implementations for solving problems related to formal argumentation in AI. We point the interested reader to the survey of participants and results achieved in ICCMA15 [13], ICCMA17 [14], and ICCMA19 [15]. ICCMA21 included a track for approximate approaches: only decision problems DC- and DS were considered diferent sub-tracks, such as ∈ {co, pr, st, sst}. Solvers were evaluated for accuracy, i.e., the ratio of correctly solved instances. The main motivation behind approximate algorithms over exact algorithms was their (potentially) lower execution time.
An approximate solver from ICCMA21 is HARPER++ by M. Thimm: such a solver can only determine the grounded extension of an input framework and then uses that to approximate results for DC and DS tasks. A positive answer to DS-gr implies a positive response to DC and DS for the other semantics. On the contrary, if an argument in the grounded extension attacks an argument, the answer to DC and DS is negative. According to [16], skeptical reasoning with any semantics generally overlaps with reasoning with the grounded semantics in many practical cases.
AFGCN, by Lars Malmqvist, competed in ICCMA21 as well. It uses a Graph Convolutional Network [17] to compute approximate solutions to DC and DS tasks for several semantics . The model is trained using a randomized training process using a dataset of AFs from previous ICCMA competitions to maximize generalization from the input frameworks. To speed up calculation and improve accuracy, the solver uses the pre-computed grounded extension as an input feature to the neural network.
As introduced in Section 1, our general goal is to study computational problems in Abstract Argumentation in the quantum world. QUBO represents the first approach to encoding and solving NP-complete problems on quantum annealers, as first accomplished in [ 6] on D-Wave annealers.
However, the optimization behind mapping QUBO models derived from an Argumentation problem to the architecture of quantum machines is still unexplored and challenging: several parameters need further investigation to exploit better the hardware and the connections among qubits, which are limited on D-Wave’s architectures. We need to leave this to future work.
We also would like to try encodings diferent from QUBO and compare other quantum platforms and their Python API, such as IBM Q and Google quantum, where qubits are diferently connected (less sparsely than D-Wave annealers). [1] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77 (1995) 321– 358. [2] P. Baroni, M. Caminada, M. Giacomin, An introduction to argumentation semantics, The
Knowledge Engineering Review 26 (2011) 365–410. [3] P. Hammer, S. Rudeanu, Boolean methods in operations research and related areas, ökonometrie und unternehmensforschung/econometrics and operations research, Springer, Berlin 1007 (1968) 978–3. [4] G. A. Kochenberger, J. Hao, F. W. Glover, M. W. Lewis, Z. Lü, H. Wang, Y. Wang, The unconstrained binary quadratic programming problem: a survey, J. Comb. Optim. 28 (2014) 58–81. [5] J. P. Wallner, A. Niskanen, M. Järvisalo, Complexity results and algorithms for extension enforcement in abstract argumentation, J. Artif. Intell. Res. 60 (2017) 1–40. [6] M. Baioletti, F. Santini, Abstract argumentation goes quantum: An encoding to QUBO problems, in: PRICAI 2022: 19th Pacific Rim International Conference on Artificial Intelligence, volume 13629 of LNCS, Springer, 2022, pp. 46–60. [7] S. Coste-Marquis, S. Konieczny, J. Mailly, P. Marquis, Extension enforcement in abstract argumentation as an optimization problem, in: International Joint Conference on Artificial Intelligence, IJCAI, AAAI Press, 2015, pp. 2876–2882. [8] F. W. Glover, G. A. Kochenberger, Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, 4OR 17 (2019) 335–371. [9] F. W. Glover, G. A. Kochenberger, M. Ma, Y. Du, Quantum bridge analytics II: qubo-plus, network optimization and combinatorial chaining for asset exchange, 4OR 18 (2020) 387–417. [10] S. Mücke, N. Piatkowski, K. Morik, Learning bit by bit: Extracting the essence of machine learning, in: R. Jäschke, M. Weidlich (Eds.), Proceedings of the Conference on "Lernen, Wissen, Daten, Analysen", volume 2454 of CEUR Workshop Proceedings, CEUR-WS.org, 2019, pp. 144–155. [11] S. Bistarelli, F. Rossi, F. Santini, Conarglib: an argumentation library with support to search strategies and parallel search, J. Exp. Theor. Artif. Intell. 33 (2021) 891–918. [12] I. Rosenberg, Reduction of bivalent maximization to the quadratic case, Cahiers du Centre d’Etudes de Recherche Opérationnelle 17 (1975) 71–74. [13] M. Thimm, S. Villata, The first international competition on computational models of argumentation: Results and analysis, Artif. Intell. 252 (2017) 267–294. [14] S. A. Gaggl, T. Linsbichler, M. Maratea, S. Woltran, Design and results of the second international competition on computational models of argumentation, Artif. Intell. 279 (2020). [15] S. Bistarelli, L. Kotthof, F. Santini, C. Taticchi, A first overview of iccma’19, in: Advances In Argumentation In Artificial Intelligence (AIxIA 2020), volume 2777 of CEUR Workshop Proceedings, CEUR-WS.org, 2020, pp. 90–102. [16] F. Cerutti, M. Thimm, M. Vallati, An experimental analysis on the similarity of argumentation semantics, Argument Comput. 11 (2020) 269–304. [17] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P. S. Yu, A comprehensive survey on graph neural networks, IEEE Trans. Neural Networks Learn. Syst. 32 (2021) 4–24.