Abstract
Abstract Argumentation (AA) provides a formal framework for modeling debates, but modifying these frameworks to achieve specific logical outcomes—known as the enforcement problem—is computationally intensive. This paper introduces EGNN, a Graph Neural Network trained via Reinforcement Learning to perform enforcement. By framing the problem as sequential decision-making, EGNN learns to modify attack relations to satisfy target extensions with minimal changes. Experimental results demonstrate that EGNN generalizes to larger, unseen graphs and maintains near-constant inference time, significantly outperforming traditional symbolic solvers on high-complexity tasks.
Introduction
In Abstract Argumentation, debates are represented as directed graphs where nodes are arguments and edges represent attacks. Determining which arguments are "accepted" depends on various logical semantics. However, as new information arises, one may need to enforce the acceptance of a specific set of arguments by adding or removing attack relations.
Enforcement is a challenging optimization problem. Depending on the semantics used, it can range from NP-complete to $\Sigma^P_3$ in complexity. While symbolic solvers are traditionally used, they often struggle with scalability and high-complexity semantics. This work proposes a Deep Reinforcement Learning (DRL) approach to learn efficient heuristics for this task.
Methodology: The EGNN Approach
The authors treat enforcement as a sequential decision-making problem. An agent interacts with an Argumentation Framework (AF) environment, selecting "flips" (adding or removing edges) to reach a target state.
Reinforcement Learning Framework
- Agent: A Deep Q-Network (DQN) that observes the graph structure.
- Reward: A step-wise penalty of $-1$ encourages the agent to find the shortest path (minimal changes) to a valid enforcement state (reward $0$).
- Verification: A fast symbolic solver acts as a "logical oracle," verifying if the target arguments are accepted under the chosen semantics.
Architecture
Standard Graph Neural Networks often fail in this domain due to varying graph scales and the need for global reasoning. The proposed EGNN architecture utilizes a multi-statistical aggregator (incorporating MEAN, MAX, MIN, and STD) instead of simple summation. This allows the network to distinguish discrete signals more effectively across different graph sizes and densities.
Experimental Evaluation
The model was trained on small synthetic AFs (3-10 arguments) and tested on larger instances (up to 50 arguments) across various semantics, including stable ($stb$), complete ($com$), and preferred ($prf$).
Efficiency and Scalability
One of the primary advantages of the learned heuristic is its runtime stability. While symbolic solvers experience exponential growth in computation time as the problem difficulty (the enforcement ratio) increases, EGNN's inference time remains nearly constant.
As shown in the figure above, for semantics like Cred_stb and Cred_com, the symbolic solver's performance degrades significantly as the ratio of arguments to be enforced changes. In contrast, EGNN maintains a low, stable runtime.
Performance and Optimality
The model's ability to generalize was tested on graphs significantly larger than those seen during training.
The results in the table indicate that EGNN consistently solves 100% of instances for smaller graphs (10-20 nodes) and maintains high success rates for 50-node graphs where symbolic solvers begin to fail. While symbolic solvers are guaranteed to find the absolute minimum number of changes (Ratio = 1.000), EGNN achieves near-optimal results, typically staying within a small factor of the theoretical minimum. For the most complex tasks at the 50-node scale, EGNN's approximation ratio reached approximately 4.5x, highlighting an area for future improvement.
Conclusion
EGNN represents the first end-to-end learning approach for the enforcement problem in abstract argumentation. By combining the strengths of DRL with a robust GNN architecture, the model provides a scalable, efficient alternative to symbolic solvers. Future work will focus on closing the optimality gap for very large graphs and exploring more complex reward functions to further minimize the number of required modifications.
Summary updated