TL;DR
This paper introduces an Argumentation Graph Neural Network (AGNN) that learns to predict whether arguments are accepted within abstract argumentation frameworks. AGNN achieves near-perfect accuracy across various semantics and scales to much larger frameworks than it was trained on, demonstrating the power of deep learning for complex symbolic reasoning tasks.
What Problem Does This Paper Address?
Abstract argumentation theory, a cornerstone of defeasible reasoning, deals with how to determine the "acceptability" of arguments in a system where arguments can attack each other. This involves defining formal semantics (like preferred, grounded, stable) that specify which sets of arguments (extensions) are considered valid. However, computing these extensions and determining argument acceptability is computationally expensive, often requiring specialized solvers for each problem and semantics. This paper aims to bridge the gap between computationally intensive symbolic methods and the efficiency of deep learning by developing a neural network that can learn to predict argument acceptance directly from the structure of argumentation frameworks.
Methods
The core of the paper is the Argumentation Graph Neural Network (AGNN). AGNN treats an argumentation framework as a graph where arguments are nodes and attacks are directed edges. It employs a message-passing mechanism:
- Initialization: Each argument node is assigned a learned embedding.
- Message Passing: In each iteration, nodes exchange learned messages with their neighbors (arguments they attack or are attacked by).
- Update: Nodes update their embeddings based on incoming messages and their previous state using a Recurrent Neural Network (RNN). This iterative process allows the network to refine its understanding of an argument's status by considering its relational context.
- Readout: After a set number of message-passing steps, a readout function (an MLP) maps the final node embeddings to a probability score between 0 and 1, indicating the likelihood of the argument being accepted. This score is then rounded to make a binary accept/reject decision.
A novel aspect is the use of two distinct message functions ($M^s$ and $M^t$) to differentiate between messages sent from a source node and messages received by a target node, allowing for a more nuanced representation of attack relationships. For extension enumeration, AGNN is adapted to predict "constructive acceptance," guiding a search procedure to find valid extensions.
Datasets
The authors generated a large dataset of argumentation frameworks using established generators from the International Competition on Computational Models of Argumentation (ICMA). They created a training set of one million AFs with 5-25 arguments and test/validation sets of 1000 AFs each with 25 arguments. Ground-truth labels were obtained using the µ-toksia solver. For scaling experiments, larger AFs with up to 200 arguments were generated.
Key Insights and Ideas
- Learning Relational Inference: AGNN demonstrates that deep learning models, specifically GNNs, can learn complex relational inference patterns inherent in symbolic reasoning tasks like argumentation.
- Generalization Beyond Training: The model shows remarkable generalization capabilities, accurately predicting acceptance in frameworks significantly larger than those seen during training, simply by running more message-passing iterations.
- Encoding Semantic Principles: Analysis of AGNN's behavior reveals it learns to implicitly encode fundamental principles of argumentation semantics (e.g., defense, conflict-freeness) into its message-passing algorithm, mirroring the logic of established symbolic algorithms.
- Unified Architecture: A single AGNN architecture can handle various argumentation semantics and different types of problems (acceptance and enumeration), reducing the need for specialized solvers.
Key Results
- High Accuracy: AGNN achieved near-perfect prediction accuracy (MCC scores between 0.997 and 1.00) for credulous and skeptical acceptance across preferred, stable, and grounded semantics. For complete semantics, it also performed exceptionally well.
- Scalability: AGNN's performance continued to improve on larger AFs (up to 200 arguments) with more message-passing steps, indicating its ability to scale beyond its training distribution.
- Extension Enumeration: AGNN achieved high precision and recall (e.g., 1.00 precision and 0.998 recall for preferred semantics) in enumerating extensions, demonstrating its utility in solving more complex argumentation problems.
- Low Prediction Error: For problems where AGNN achieved perfect classification, the mean absolute error (MAE) was extremely low (e.g., 3e-6), indicating high confidence in its predictions.
Limitations and Future Work
- Theoretical Guarantees: While AGNN provides excellent empirical results, it does not offer the same theoretical guarantees as symbolic algorithms.
- Extension Enumeration for Complete Semantics: The search procedure for complete semantics had lower recall because complete extensions can be subsets of other complete extensions, a limitation that could be addressed with verification algorithms.
- Future Directions: The authors suggest exploring AGNN for dynamic argumentation, where arguments or attacks are added/removed, and investigating how AGNN can learn to enforce specific argument acceptabilities. They also aim to explore its application in other symbolic domains.
Summary updated