Recently, there has been an increasing interest in extending Dung's framework with probability theory, leading to the Probabilistic Argumentation Framework (PAF), and with supports in addition to attacks, leading to the Bipolar Argumentation Framework (BAF). In this paper, we introduce the Conditional Probabilistic Bipolar Argumentation Framework (CPBAF), which extends Probabilistic and Bipolar AF by allowing conditional probabilities on arguments, attacks, and on (possibly cyclic) supports. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for CPBAF where cycles with an odd number of attacks are forbidden.

Link prediction algorithms for multilayer networks are in principle required to effectively account for the entire layered structure while capturing the unique contexts offered by each layer. However, many existing approaches excel at predicting specific links in certain layers but struggle with others, as they fail to effectively leverage the diverse information encoded across different network layers. In this paper, we present MoE-ML-LP , the first Mixture-of-Experts (MoE) framework specifically designed for multilayer link prediction. Building on top of multilayer heuristics for link prediction, MoE-ML-LP synthesizes the decisions taken by diverse experts, resulting in significantly enhanced predictive capabilities. Our extensive experimental evaluation on real-world and synthetic networks demonstrates that MoE-ML-LP consistently outperforms several baselines and competing methods, achieving remarkable improvements of +60% in Mean Reciprocal Rank, +82% in Hits@1, +55% in Hits@5, and +41% in Hits@10. Furthermore, MoE-ML-LP features a modular architecture that enables the seamless integration of newly developed experts without necessitating the re-training of the entire framework, fostering efficiency and scalability to new experts, paving the way for future advancements in link prediction.

Abstract Polarization is common in social systems, where individuals tend to form cohesive groups that oppose each other. Signed networks, with positive edges representing agreement and negative edges representing disagreement, provide a natural model for studying such dynamics. The 2-Polarized-Communities problem ( 2pc ) was recently introduced to detect a single pair of polarized communities by maximizing a Rayleigh quotient that balances intra-community agreement and inter-community disagreement. However, real signed networks usually host multiple, coexisting axes of conflict, often with communities that overlap. Existing extension of 2pc to multiple communities or find-and-remove heuristics, either rely on the restrictive assumption that every polarized community is in conflict with all the others, or enforce disjoint solutions–thus failing to capture the nuanced structures observed in real networks. In this paper, we introduce the Diverse top-k-pc problem, which is the first principled formulation of top- k polarized communities with controlled overlap. Our formulation extends the 2pc polarity objective by incorporating diversity terms directly into the denominator of the Rayleigh quotient, yielding a generalized objective that jointly promotes polarity and diversity. We design a greedy sequential algorithm that solves a generalized eigenvector problem at each step, efficiently discovering diverse polarized pairs. Experiments on both real-world and synthetic signed networks demonstrate that our approach identifies multiple meaningful and overlapping pairs of polarized communities, outperforming natural baselines while scaling to large graphs.

Signed networks represent interactions among users (nodes), with edges labeled as positive for friendly relations and negative for antagonistic ones. The 2-Polarized-Communities ( 2pc ) combinatorial optimization problem seeks two disjoint polarized communities in a signed network, so as to satisfy three conditions: most edges within each community are positive, most edges between communities are negative, and the number of edges satisfying these conditions is high compared to the number of nodes in the communities. The Densest Subgraph ( ds ) problem in unsigned networks consists in finding a subgraph that exhibits maximum ratio between number of edges and number of nodes. Although the 2pc problem intuitively suggests finding a dense subgraph, no prior work has explored the implicitly optimized density measure or algorithmic methods from the rich, yet distinct, literature on the ds problem (in unsigned networks) and applied them to 2pc . This work bridges this gap by formally establishing a link between the two problems and introducing a highly efficient and effective greedy algorithm inspired by ds methods to solve 2pc . Experimental results on synthetic and real datasets demonstrate the superior performance of our method compared to competing approaches in terms of both accuracy and efficiency.

Explainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we focus on local post-hoc explainability queries within the semifactual `even-if' thinking and their computational complexity among different classes of models, and show that both linear and tree-based models are strictly more interpretable than neural networks. After this, we introduce a preference-based framework enabling users to personalize explanations based on their preferences, both in the case of semifactuals and counterfactuals, enhancing interpretability and user-centricity. Finally, we explore the complexity of several interpretability problems in the proposed preference-based framework and provide algorithms for polynomial cases.

Link prediction has traditionally been studied in the context of simple graphs, although real-world networks are inherently complex as they are often comprised of multiple interconnected components, or layers. Predicting links in such network systems, or multilayer networks, require to consider both the internal structure of a target layer as well as the structure of the other layers in a network, in addition to layer-specific node-attributes when available. This problem poses several challenges, even for graph neural network based approaches despite their successful and wide application to a variety of graph learning problems. In this work, we aim to fill a lack of multilayer graph representation learning methods designed for link prediction. Our proposal is a novel neural-network-based learning framework for link prediction on (attributed) multilayer networks, whose key idea is to combine (i) pairwise similarities of multilayer node embeddings learned by a graph neural network model, and (ii) structural features learned from both within-layer and across-layer link information based on overlapping multilayer neighborhoods. Extensive experimental results have shown that our framework consistently outperforms both single-layer and multilayer methods for link prediction on popular real-world multilayer networks, with an average percentage increase in AUC up to 38%. We make source code and evaluation data available at https://mlnteam-unical.github.io/resources/.

Dealing with controversial information is an important issue in several application contexts. Formal argumentation enables reasoning on arguments for and against a claim to decide on an outcome. Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in argument-based reasoning. Key aspects of the success and popularity of Dung's framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, we first explore two intuitive semantics based on Kleene and Lukasiewicz logics, respectively, for AF augmented with (strong) constraints—the resulting argumentation framework is called Constrained AF (CAF). Then, we propose a new argumentation framework called Weak constrained AF (WAF) that enhances CAF with weak constraints. Intuitively, these constraints can be used to find “optimal” solutions to problems defined through CAF. We provide a detailed complexity analysis of CAF and WAF, showing that strong constraints do not increase the expressive power of AF in most cases, while weak constraints systematically increase the expressive power of CAF (and AF) under several well-known argumentation semantics.

Active learning is focused on minimizing the effort required to obtain labeled data by iteratively choosing fresh data samples for training a machine learning model. One of the primary challenges in active learning involves the selection of the most informative instances for labeling by an annotation oracle at each iteration. A viable approach is to develop an active learning strategy that aligns with the performance of a meta-learning model. This strategy evaluates the quality of previously selected instances and subsequently trains a machine learning model to predict the quality of instances to be labeled in the current iteration. This paper introduces a novel approach to learning for active learning, wherein instances are chosen for labeling based on their potential to induce the most substantial change in the current classifier. We explore various strategies for assessing the significance of an instance, taking into account variations in the learning gradient of the classification model. Our approach can be applied to any classifier that can be trained using gradient descent optimization. Here, we present a formulation that leverages a deep neural network model, which has not been extensively explored in existing learning-to-active-learn methodologies. Through experimental validation, our approach demonstrates promising results, especially in scenarios where there are limited initially labeled instances, particularly when the number of labeled instances per class is extremely limited.

Abstract Signed graphs are a model to depict friendly (positive) or antagonistic (negative) interactions (edges) among users (nodes). 2-Polarized-Communities (2pc) is a well-established combinatorial-optimization problem whose goal is to find two polarized communities from a signed graph, i.e., two subsets of nodes (disjoint, but not necessarily covering the entire node set) which exhibit a high number of both intra-community positive edges and negative inter-community edges. The state of the art in 2pc suffers from the limitations that (i) existing methods rely on a single (optimal) solution to a continuous relaxation of the problem in order to produce the ultimate discrete solution via rounding, and (ii) 2pc objective function comes with no control on size balance among communities. In this paper, we provide advances to the 2pc problem by addressing both these limitations, with a twofold contribution. First, we devise a novel neural approach that allows for soundly and elegantly explore a variety of suboptimal solutions to the relaxed 2pc problem, so as to pick the one that leads to the best discrete solution after rounding. Second, we introduce a generalization of 2pc objective function – termed $$\gamma $$ γ -polarity – which fosters size balance among communities, and we incorporate it into the proposed machine-learning framework. Extensive experiments attest high accuracy of our approach, its superiority over the state of the art, and capability of function $$\gamma $$ γ -polarity to discover high-quality size-balanced communities.

Dung’s Argumentation Framework (AF) has been extended in several directions. An interesting extension, among others, is the Epistemic AF (EAF) which allows representing the agent’s belief by means of epistemic constraints. In particular, an epistemic constraint is a propositional formula over labeled arguments (e.g. in(a), out(c)) extended with the modal operators K and M that intuitively state that the agent believes that a given formula is certainly or possibly true, respectively. In this paper, focusing on EAF, we investigate the complexity of the possible and necessary variants of three canonical problems in abstract argumentation: verification, existence, and non-empty existence. Moreover, we explore the relationship between EAF and incomplete AF (iAF), an extension of AF where arguments and attacks may be uncertain. Our complexity analysis shows that the verification problem in iAF can be naturally reduced to the verification in EAF, while it turns out that a similar result cannot hold for the necessary (non-empty) existence problem.

Abstract Given a graph whose edges are assigned positive-type and negative-type weights, the problem of correlation clustering aims at grouping the graph vertices so as to minimize (resp. maximize) the sum of negative-type (resp. positive-type) intra-cluster weights plus the sum of positive-type (resp. negative-type) inter-cluster weights. In correlation clustering, it is typically assumed that the weights are readily available. This is a rather strong hypothesis, which is unrealistic in several scenarios. To overcome this limitation, in this work we focus on the setting where edge weights of a correlation-clustering instance are unknown, and they have to be estimated in multiple rounds, while performing the clustering. The clustering solutions produced in the various rounds provide a feedback to properly adjust the weight estimates, and the goal is to maximize the cumulative quality of the clusterings. We tackle this problem by resorting to the reinforcement-learning paradigm, and, specifically, we design for the first time a Combinatorial Multi-Armed Bandit (CMAB) framework for correlation clustering. We provide a variety of contributions, namely (1) formulations of the minimization and maximization variants of correlation clustering in a CMAB setting; (2) adaptation of well-established CMAB algorithms to the correlation-clustering context; (3) regret analyses to theoretically bound the accuracy of these algorithms; (4) design of further (heuristic) algorithms to have the probability constraint satisfied at every round (key condition to soundly adopt efficient yet effective algorithms for correlation clustering as CMAB oracles); (5) extensive experimental comparison among a variety of both CMAB and non-CMAB approaches for correlation clustering.

A major challenge in active learning is to select the most informative instances to be labeled by an annotation oracle at each step. In this respect, one effective paradigm is to learn the active learning strategy that best suits the performance of a meta-learning model. This strategy first measures the quality of the instances selected in the previous steps and then trains a machine learning model that is used to predict the quality of instances to be labeled in the current step.In this paper, we propose a new approach of learning-to-active-learn that selects the instances to be labeled as the ones producing the maximum change to the current classifier. Our key idea is to select such instances according to their importance reflecting variations in the learning gradient of the classification model. Our approach can be instantiated with any classifier trainable via gradient descent optimization, and here we provide a formulation based on a deep neural network model, which has not deeply been investigated in existing learning-to-active-learn approaches. The experimental validation of our approach has shown promising results in scenarios characterized by relatively few initially labeled instances.

We study two novel clustering problems in which the pairwise interactions between entities are characterized by probability distributions and conditioned by external factors within the environment where the entities interact. This covers any scenario where a set of actions can alter the entities' interaction behavior. In particular, we consider the case where the interaction conditioning factors can be modeled as cluster memberships of entities in a graph and the goal is to partition a set of entities such as to maximize the overall vertex interactions or, equivalently, minimize the loss of interactions in the graph. We show that both problems are NP-hard and they are equivalent in terms of optimality. However, we focus on the minimization formulation as it enables the possibility of devising both practical and efficient approximation algorithms and heuristics. Experimental evaluation of our algorithms, on both synthetic and real network datasets, has shown evidence of their meaningfulness as well as superiority with respect to competing methods, both in terms of effectiveness and efficiency.

Community detection and evolution has been largely studied in the last few years, especially for network systems that are inherently dynamic and undergo different types of changes in their structure and organization in communities. Because of the inherent uncertainty and dynamicity in such network systems, we argue that temporal community detection problems can profitably be solved under a particular class of multi-armed bandit problems, namely combinatorial multi-armed bandit (CMAB). More specifically, we propose a CMAB-based methodology for the novel problem of dynamic consensus community detection, i.e., to compute a single community structure that is designed to encompass the whole information available in the sequence of observed temporal snapshots of a network in order to be representative of the knowledge available from community structures at the different time steps. Unlike existing approaches, our key idea is to produce a dynamic consensus solution for a temporal network to have unique capability of embedding both long-term changes in the community formation and newly observed community structures.