United States

Answer Set Programming (ASP) is a problem modeling and solving framework for several problems in KR with growing industrial applications. Also for studies of computational complexity and deeper insights into the hardness and its sources, ASP has been attracting researchers for many years. These studies resulted in fruitful characterizations in terms of complexity classes, fine-grained insights in form of dichotomy-style results, as well as detailed parameterized complexity landscapes. Recently, this lead to a novel result establishing that for the measure treewidth, which captures structural density of a program, the evaluation of the well-known class of normal programs is expected to be slightly harder than deciding satisfiability (SAT). However, it is unclear how to utilize this structural power of ASP. This paper deals with a novel reduction from SAT to normal ASP that goes beyond well-known encodings: We explicitly utilize the structural power of ASP, whereby we sublinearly decrease the treewidth, which probably cannot be significantly improved. Then, compared to existing results, this characterizes hardness in a fine-grained way by establishing the required functional dependency of the dependency graph’s cycle length (SCC size) on the treewidth. Thereby, we do not only improve this dependency for a family of almost-tight programs, we also utilize the reduction for lower bounds that close the gap to existing upper bounds.

AAAI 2023

Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?

cycles

treewidth

logic programming

reduction

hardness

complexity

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

poster

A dramatic increase in real-world video volume with extremely diverse and emerging topics naturally forms a long-tailed video distribution in terms of their categories, and it spotlights the need for Video Long-Tailed Recognition (VLTR).
In this work, we summarize the challenges in VLTR and explore how to overcome them.
The challenges are: (1) it is impractical to re-train the whole model for high-quality features, (2) acquiring frame-wise labels requires extensive cost, and (3) long-tailed data triggers biased training.
Yet, most existing works for VLTR unavoidably utilize image-level features extracted from pretrained models which are task-irrelevant, and learn by video-level labels.
Therefore, to deal with such (1) task-irrelevant features and (2) video-level labels, we introduce two complementary learnable feature aggregators.
Learnable layers in each aggregator are to produce task-relevant representations, and each aggregator is to assemble the snippet-wise knowledge into a video representative.
Then, we propose Minority-Oriented Vicinity Expansion (MOVE) that explicitly leverages the class frequency into approximating the vicinity distributions to alleviate (3) biased training.
By combining these solutions, our approach achieves state-of-the-art results on large-scale VideoLT and synthetically induced Imbalanced-MiniKinetics200. 
With VideoLT features from ResNet-50, it attains 18% and 58% relative improvements on head and tail classes over the previous state-of-the-art method, respectively. 

Minority-Oriented Vicinity Expansion with Attentive Aggregation for Video Long-Tailed Recognition

Graph Neural Networks (GNNs) have emerged as the leading paradigm for solving graph analytical problems in various real-world applications. Nevertheless, GNNs could potentially render biased predictions towards certain demographic subgroups.  Understanding how the bias in predictions arises is critical, as it guides the design of GNN debiasing mechanisms. However, most existing works overwhelmingly focus on GNN debiasing, but fall short on explaining how such bias is induced. In this paper, we study a novel problem of interpreting GNN unfairness through attributing it to the influence of training nodes. Specifically, we propose a novel strategy named Probabilistic Distribution Disparity (PDD) to measure the bias exhibited in GNNs, and develop an algorithm to efficiently estimate the influence of each training node on such bias. We verify the validity of PDD and the effectiveness of influence estimation through experiments on real-world datasets. Finally, we also demonstrate how the proposed framework could be used for debiasing GNNs. Open-source code can be found at https://github.com/yushundong/BIND.

Interpreting Unfairness in Graph Neural Networks via Training Node Attribution

Exploration under sparse rewards is a key challenge for multi-agent reinforcement learning problems. One possible solution to this issue is to exploit inherent task structures for an acceleration of exploration. In this paper, we present a novel exploration approach, which encodes a special structural prior on the reward function into exploration, for sparse-reward multi-agent tasks. Specifically, a novel entropic exploration objective which encodes the structural prior is proposed to accelerate the discovery of rewards. By maximizing the lower bound of this objective, we then propose an algorithm with moderate computational cost, which can be applied to practical tasks. Under the sparse-reward setting, we show that the proposed algorithm significantly outperforms the state-of-the-art algorithms in the multiple-particle environment, the Google Research Football and StarCraft II micromanagement tasks. To the best of our knowledge, on some hard tasks (such as \texttt{27m\_vs\_30m}) which have relatively larger number of agents and need non-trivial strategies to defeat enemies, our method is the first to learn winning strategies under the sparse-reward setting.

Subspace-Aware Exploration for Sparse-Reward Multi-Agent Tasks

The use of counterfactual explanations (CFXs) is an increasingly popular explanation strategy for machine learning models. However, recent studies have shown that these explanations may not be robust to changes in the underlying model (e.g., following retraining), which raises questions about their reliability in real-world applications. Existing attempts towards solving this problem are heuristic, and the robustness to model changes of resulting CFXs is evaluated with only a small number of retrained models, failing to provide exhaustive guarantees. To this end, we propose ∆-robustness, the first notion to formally and deterministically assess the robustness (to model changes) of CFXs for neural networks. We introduce an abstraction framework based on interval neural networks to verify the ∆-robustness of CFXs against a possibly infinite set of changes to the model parameters, i.e., weights and biases. We then demonstrate the utility of this approach in two distinct ways. First, we  analyse the ∆-robustness of a number of CFX generation methods from the literature and show they unanimously host significant deficiencies in this regard. Second, we demonstrate how embedding ∆-robustness within existing methods can provide CFXs which are provably robust. 

Formalising the Robustness of Counterfactual Explanations for Neural Networks

OPRADI: Applying Security Game to Fight Drive under the Influence in Real-World

Although current Graph Neural Network (GNN) based models achieved good performances in Dialogue Intent Classification (DIC), they leave the inherent domain-specific knowledge out of consideration, leading to the lack of ability of acquiring fine-grained semantic information. In this paper, we propose a Knowledge-Enhanced Multifactor Graph (KEMG) Model for DIC. We firstly present a knowledge-aware utterance encoder with the help of a domain-specific knowledge
graph, fusing token-level and entity-level semantic information, then design a heterogeneous dialogue graph encoder by explicitly modeling several factors that matter to contextual modeling of dialogues. Experiment results show that our proposed method outperforms other GNN-based methods on a dataset collected from a real-world online customer service dialogue system on the e-commerce website.

Improving Dialogue Intent Classification with a Knowledge-Enhanced MultifactorGraph Model

In this video, I will share our work “Semi-Supervised Review-Aware Rating Regression”. In this work, we integrate the merits of both co-training and co-teaching towards the robust semi-supervised review-aware rating regression. CoT2 is a simple yet effective paradigm to exploit unlabelled data safely.

Semi-supervised Review-Aware Rating Regression (Student Abstract)

In this talk, we discuss measuring privacy leakage via graph reconstruction attack (GRA). We propose a GRA that recovers a graph's adjacency matrix from the representations via a graph decoder that minimizes the reconstruction loss between the partial graph and the reconstructed graph. We study three types of representations that are trained on the graph, i.e., representations output from graph convolutional network (GCN), graph attention network (GAT), and our proposed simplicial neural network (SNN) via a higher-order combinatorial Laplacian. Unlike the first two types of representations that only encode pairwise relationships, the third type of representation, i.e., SNN outputs, encodes higher-order interactions (e.g., homological features) between nodes. We find that the SNN outputs reveal the lowest privacy-preserving ability to defend the GRA, followed by those of GATs and GCNs, which indicates the importance of building more private representations with higher-order node information that could defend the potential threats, such as GRAs.

Measuring the Privacy Leakage via Graph Reconstruction Attacks on Simplicial Neural Networks (Student Abstract)

we have developed a system for repairing logic errors in C++ programs with machine learning. As you may know, logic errors can be particularly difficult to repair because they do not have diagnostic feedback from compilers, Syntax errors will have an error line report and feedback ​, but a Logic error has no compiler feedback​. And it also requires inferring over different ranges of code and involves tracking symbols across the whole program. Additionally, datasets about logic errors are not complete sometimes, as they should ideally include program specifications, source codes, test cases, error lines, and patches. To address these challenges, we introduced pseudocode information to assist in the localization and correction of logic errors. We constructed a powerful graph structure to connect symbols across the source code and its pseudocode, and then applied a graph neural network to localize and correct these errors. The results of our experiments show that our model was able to achieve 99.39% localization accuracy and 19.2% repair accuracy on the single logic error dataset using five-fold cross-validation.

Logic Error Localization and Correction with Machine Learning (Student Abstract)

The paper presents an attempt to bridge the gap between machine learning and symbolic reasoning. We build graph neural networks (GNNs) to predict the solution of the Maximum Satisfiability (MaxSAT) problem, an optimization variant of SAT. Two closely related graph representations are adopted, and we prove their theoretical equivalence. We also show that GNNs can achieve attractive performance to solve hard MaxSAT problems in certain distributions even compared with state-of-the-art solvers through experimental evaluation.

Premium content

Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?

Downloads

Next from AAAI 2023

Minority-Oriented Vicinity Expansion with Attentive Aggregation for Video Long-Tailed Recognition

Similar lecture

Inconsistent Cores for ASP: The Perks and Perils of Non-Monotonicity