GenAI4ELab/papercli-papers huggingface dataset:
Two Views of Constrained Differential Privacy: Belief Revision and Update
Authors: Likang Liu; Keke Sun; Chunlai Zhou; Yuan Feng
Venue: AAAI 2023 (main)

Abstract: In this paper, we provide two views of constrained differential private (DP) mechanisms. The first one is as belief revision.  A constrained DP mechanism is obtained by standard probabilistic conditioning, and hence can be naturally implemented by Monte Carlo algorithms.  The other is as belief update.  A constrained DP is defined according to l2-distance minimization postprocessing or projection and hence can be naturally implemented by optimization algorithms.  The main advantage of these two perspectives is that we can make full use of the machinery of belief revision and update to show basic properties for constrained differential privacy especially some important new composition properties.  Within the framework established in this paper, constrained DP algorithms in the literature can be classified either as belief revision or belief update.  At the end of the paper, we demonstrate their differences especially in utility on a couple of scenarios.
Copyright-Certified Distillation Dataset: Distilling One Million Coins into One Bitcoin with Your Private Key
Authors: Tengjun Liu; Ying Chen; Wanxuan Gu
Venue: AAAI 2023 (main)

Abstract: The rapid development of neural network dataset distillation in recent years has provided new ideas in many areas such as continuous learning, neural network architecture search and privacy preservation. Dataset distillation is a very effective method to distill large training datasets into small data, thus ensuring that the test accuracy of models trained on their synthesized small datasets matches that of models trained on the full dataset. Thus, dataset distillation itself is commercially valuable, not only for reducing training costs, but also for compressing storage costs and significantly reducing the training costs of deep learning. However, copyright protection for dataset distillation has not been proposed yet, so we propose the first method to protect intellectual property by embedding watermarks in the dataset distillation process. Our approach not only popularizes the dataset distillation technique, but also authenticates the ownership of the distilled dataset by the models trained on that distilled dataset.
DHGE: Dual-View Hyper-Relational Knowledge Graph Embedding for Link Prediction and Entity Typing
Authors: Haoran Luo; Haihong E; Ling Tan; Gengxian Zhou; Tianyu Yao; Kaiyang Wan
Venue: AAAI 2023 (main)

Abstract: In the field of representation learning on knowledge graphs (KGs), a hyper-relational fact consists of a main triple and several auxiliary attribute-value descriptions, which is considered more comprehensive and specific than a triple-based fact. However, currently available hyper-relational KG embedding methods in a single view are limited in application because they weaken the hierarchical structure that represents the affiliation between entities. To overcome this limitation, we propose a dual-view hyper-relational KG structure (DH-KG) that contains a hyper-relational instance view for entities and a hyper-relational ontology view for concepts that are abstracted hierarchically from the entities. This paper defines link prediction and entity typing tasks on DH-KG for the first time and constructs two DH-KG datasets, JW44K-6K, extracted from Wikidata, and HTDM based on medical data. Furthermore, we propose DHGE, a DH-KG embedding model based on GRAN encoders, HGNNs, and joint learning. DHGE outperforms baseline models on DH-KG, according to experimental results. Finally, we provide an example of how this technology can be used to treat hypertension. Our model and new datasets are publicly available.
Automated Verification of Propositional Agent Abstraction for Classical Planning via CTLK Model Checking
Authors: Kailun Luo
Venue: AAAI 2023 (main)

Abstract: Abstraction has long been an effective mechanism to help find a solution in classical planning. Agent abstraction, based on the situation calculus, is a promising explainable framework for agent planning, yet its automation is still far from being tackled. In this paper, we focus on a propositional version of agent abstraction designed for finite-state systems. We investigate the automated verification of the existence of propositional agent abstraction, given a finite-state system and a mapping indicating an abstraction for it. By formalizing sound, complete and deterministic properties of abstractions in a general framework, we show that the verification task can be reduced to the task of model checking against CTLK specifications. We implemented a prototype system, and validated the viability of our approach through experimentation on several domains from classical planning.
Efficient Answer Enumeration in Description Logics with Functional Roles
Authors: Carsten Lutz; Marcin Przybyłko
Venue: AAAI 2023 (main)

Abstract: We study the enumeration of answers to ontology-mediated queries
when the ontology is formulated in a description logic that supports
functional roles and the query is a CQ. In particular, we show that
enumeration is possible with linear preprocessing and constant delay
when a certain extension of the CQ (pertaining to functional roles)
is acyclic and free-connex acyclic. This holds both for complete answers and
for partial answers. We provide matching lower bounds for the
case where the query is self-join free.
Distributed Spectrum-Based Fault Localization
Authors: Avraham Natan; Roni Stern; Meir Kalech
Venue: AAAI 2023 (main)

Abstract: Spectrum-Based Fault Localization (SFL) is a popular approach for diagnosing faulty systems. SFL algorithms are inherently centralized, where observations are collected and analyzed by a single diagnoser. Applying SFL to diagnose distributed systems is challenging, especially when communication is costly and there are privacy concerns. We propose two SFL-based algorithms that are designed for distributed systems: one for diagnosing a single faulty component and one for diagnosing multiple faults. We analyze these algorithms theoretically and empirically. Our analysis shows that the distributed SFL algorithms we developed output identical diagnoses to centralized SFL while preserving privacy.
Multi-Level Wavelet Mapping Correlation for Statistical Dependence Measurement: Methodology and Performance
Authors: Yixin Ren; Hao Zhang; Yewei Xia; Jihong Guan; Shuigeng Zhou
Venue: AAAI 2023 (main)

Abstract: We propose a new criterion for measuring dependence between two real variables, namely, Multi-level Wavelet Mapping Correlation (MWMC). MWMC can capture the nonlinear dependencies between variables by measuring their correlation under different levels of wavelet mappings. We show that the empirical estimate of MWMC converges exponentially to its population quantity. To support independence test better with MWMC, we further design a permutation test based on MWMC and prove that our test can not only control the type I error rate (the rate of false positives) well but also ensure that the type II error rate (the rate of false negatives) is upper bounded by O(1/n) (n is the sample size) with finite permutations. By extensive experiments on (conditional) independence tests and causal discovery, we show that our method outperforms existing independence test methods.
Learning Interpretable Temporal Properties from Positive Examples Only
Authors: Rajarshi Roy; Jean-Raphaël Gaglione; Nasim Baharisangari; Daniel Neider; Zhe Xu; Ufuk Topcu
Venue: AAAI 2023 (main)

Abstract: We consider the problem of explaining the temporal behavior of black-box systems using human-interpretable models. Following recent research trends, we rely on the fundamental yet interpretable models of deterministic finite automata (DFAs) and linear temporal logic (LTL_f) formulas. In contrast to most existing works for learning DFAs and LTL_f formulas, we consider learning from only positive examples. Our motivation is that negative examples are generally difficult to observe, in particular, from black-box systems. To learn meaningful models from positive examples only, we design algorithms that rely on conciseness and language minimality of models as regularizers. Our learning algorithms are based on two approaches: a symbolic and a counterexample-guided one. The symbolic approach exploits an efficient encoding of language minimality as a constraint satisfaction problem, whereas the counterexample-guided one relies on generating suitable negative examples to guide the learning. Both approaches provide us with effective algorithms with minimality guarantees on the learned models. To assess the effectiveness of our algorithms, we evaluate them on a few practical case studies.
Editing Boolean Classifiers: A Belief Change Perspective
Authors: Nicolas Schwind; Katsumi Inoue; Pierre Marquis
Venue: AAAI 2023 (main)

Abstract: This paper is about editing Boolean classifiers, i.e., determining how a Boolean classifier should be modified when new pieces of evidence must be incorporated. Our main goal is to delineate what are the rational ways of making such edits. This goes through a number of rationality postulates inspired from those considered so far for belief revision. We give a representation theorem and present some families of edit operators satisfying the postulates.
Implementing Bounded Revision via Lexicographic Revision and C-revision
Authors: Meliha Sezgin; Gabriele Kern-Isberner
Venue: AAAI 2023 (main)

Abstract: New information in the context of real life settings usually is accompanied by some kind of supplementary information that indicates context, reliability, or expertise of the information's source.
Bounded Revision (BR) displays an iterated belief revision mechanism that takes as input a new information accompanied by a reference sentence acting as supplementary information, which specifies the depth with which the new input shall be integrated in the posterior belief state. The reference sentence specifies which worlds in the prior belief state are affected by the change mechanism. We show that Bounded Revision can be characterized by three simple, yet elegant postulates and corresponds to a special case of a lexicographic revision, which inherits all relevant features of BR. Furthermore, we present methodological implementations of BR including conditional revision with c-revisions, making it directly usable for conditional revision tools.
Multi-Aspect Explainable Inductive Relation Prediction by Sentence Transformer
Authors: Zhixiang Su; Di Wang; Chunyan Miao; Lizhen Cui
Venue: AAAI 2023 (main)

Abstract: Recent studies on knowledge graphs (KGs) show that path-based methods empowered by pre-trained language models perform well in the provision of inductive and explainable relation predictions. In this paper, we introduce the concepts of relation path coverage and relation path confidence to filter out unreliable paths prior to model training to elevate the model performance. Moreover, we propose Knowledge Reasoning Sentence Transformer (KRST) to predict inductive relations in KGs. KRST is designed to encode the extracted reliable paths in KGs, allowing us to properly cluster paths and provide multi-aspect explanations. We conduct extensive experiments on three real-world datasets. The experimental results show that compared to SOTA models, KRST achieves the best performance in most transductive and inductive test cases (4 of 6), and in 11 of 12 few-shot test cases.
Learning to Break Symmetries for Efficient Optimization in Answer Set Programming
Authors: Alice Tarzariol; Martin Gebser; Konstantin Schekotihin; Mark Law
Venue: AAAI 2023 (main)

Abstract: The ability to efficiently solve hard combinatorial optimization problems is a key prerequisite to various applications of declarative programming paradigms. Symmetries in solution candidates pose a significant challenge to modern optimization algorithms since the enumeration of such candidates might substantially reduce their performance.

This paper proposes a novel approach using Inductive Logic Programming (ILP) to lift symmetry-breaking constraints for optimization problems modeled in Answer Set Programming (ASP). Given an ASP encoding with optimization statements and a set of small representative instances, our method augments ground ASP programs with auxiliary normal rules enabling the identification of symmetries using existing tools, like SBASS. Then, the obtained symmetries are lifted to first-order constraints with ILP. 
We prove the correctness of our method and evaluate it on real-world optimization problems from the domain of automated configuration. Our experiments show significant improvements of optimization performance due to the learned first-order constraints.
On Undisputed Sets in Abstract Argumentation
Authors: Matthias Thimm
Venue: AAAI 2023 (main)

Abstract: We introduce the notion of an undisputed set for abstract argumentation frameworks, which is a conflict-free set of arguments, such that its reduct contains no non-empty admissible set. We show that undisputed sets, and the stronger notion of strongly undisputed sets, provide a meaningful approach to weaken admissibility and deal with the problem of attacks from self-attacking arguments, in a similar manner as the recently introduced notion of weak admissibility. We investigate the properties of our new semantical notions and show certain relationships to classical semantics, in particular that undisputed sets are a generalisation of preferred extensions and strongly undisputed sets are a generalisation of stable extensions. We also investigate the computational complexity of standard reasoning tasks with these new notions and show that they lie on the second and third level of the polynomial hierarchy, respectively.
Neurosymbolic Reasoning and Learning with Restricted Boltzmann Machines
Authors: Son N. Tran; Artur d'Avila Garcez
Venue: AAAI 2023 (main)

Abstract: Knowledge representation and reasoning in neural networks has been a long-standing endeavour which has attracted much attention recently. The principled integration of reasoning and learning in neural networks is a main objective of the area of neurosymbolic Artificial Intelligence. In this paper, a neurosymbolic system is introduced that can represent any propositional logic formula. A proof of equivalence is presented showing that energy minimization in restricted Boltzmann machines corresponds to logical reasoning. We demonstrate the application of our approach empirically on logical reasoning and learning from data and knowledge. Experimental results show that reasoning can be performed effectively for a class of logical formulae. Learning from data and knowledge is also evaluated in comparison with learning of logic programs using neural networks. The results show that our approach can improve on state-of-the-art neurosymbolic systems. The theorems and empirical results presented in this paper are expected to reignite the research on the use of neural networks as massively-parallel models for logical reasoning and promote the principled integration of reasoning and learning in deep networks.
Materialisation-Based Reasoning in DatalogMTL with Bounded Intervals
Authors: Przemysław A. Wałęga; Michał Zawidzki; Dingmin Wang; Bernardo Cuenca Grau
Venue: AAAI 2023 (main)

Abstract: DatalogMTL is a powerful extension of Datalog with operators from metric temporal logic (MTL), which has received significant attention in recent years. In this paper, we investigate materialisation-based reasoning (a.k.a. forward chaining) in the context of DatalogMTL programs and datasets with bounded intervals, where partial representations of the canonical model are obtained through successive rounds of rule applications. Although materialisation does not naturally terminate in this setting, it is known that the structure of canonical models is ultimately periodic. Our first contribution in this paper is a detailed analysis of the periodic structure of canonical models; in particular, we formulate saturation conditions whose satisfaction by a partial materialisation implies an ability to recover the full canonical model via unfolding; this allows us to compute the actual periods describing the repeating parts of the canonical model as well as to establish concrete bounds on the number of rounds of rule applications required to achieve saturation. Based on these theoretical results, we propose a practical reasoning algorithm where saturation can be efficiently detected as materialisation progresses, and where the relevant periods used to evaluate entailment of queries via unfolding are efficiently computed. We have implemented our algorithm  and our experiments suggest that  our approach is both scalable and robust.
Efficient Extraction of EL-Ontology Deductive Modules
Authors: Hui Yang; Yue Ma; Nicole Bidoit
Venue: AAAI 2023 (main)

Abstract: Because widely used real-world ontologies are often complex and large, one important challenge has emerged: designing tools for users to focus on sub-ontologies corresponding to their specific interests. To this end, various modules have been introduced to provide concise ontology views. This work concentrates on extracting deductive modules that preserve logical entailment over a given vocabulary. Existing deductive module proposals are either inefficient from a computing point of view or unsatisfactory from a quality point of view because the modules extracted are not concise enough. For example, minimal modules guarantee the most concise results, but their computation is highly time-consuming, while ⊥⊤∗-modules are easy to compute but usually contain many redundant items. To overcome computation cost and lack of quality, we propose to compute two kinds of deductive modules called pseudo-minimal modules and complete modules for EL-ontology. Our deductive module definitions rely on associating a tree representation with an ontology, and their computation is based on SAT encoding. Our experiments on real-world ontologies show that our pseudo-minimal modules are indeed minimal modules in almost all cases (98.9%), and computing pseudo-minimal modules is more efficient (99.79 times faster on average) than the state-of-the-art method Zoom for computing minimal modules. Also, our complete modules are more compact than ⊥⊤∗-modules, but their computation time remains comparable. Finally, note that our proposal applies to EL-ontologies while Zoom only works for EL-terminologies.
Visually Grounded Commonsense Knowledge Acquisition
Authors: Yuan Yao; Tianyu Yu; Ao Zhang; Mengdi Li; Ruobing Xie; Cornelius Weber; Zhiyuan Liu; Hai-Tao Zheng; Stefan Wermter; Tat-Seng Chua; Maosong Sun
Venue: AAAI 2023 (main)

Abstract: Large-scale commonsense knowledge bases empower a broad range of AI applications, where the automatic extraction of commonsense knowledge (CKE) is a fundamental and challenging problem. CKE from text is known for suffering from the inherent sparsity and reporting bias of commonsense in text. Visual perception, on the other hand, contains rich commonsense knowledge about real-world entities, e.g., (person, can_hold, bottle), which can serve as promising sources for acquiring grounded commonsense knowledge. In this work, we present CLEVER, which formulates CKE as a distantly supervised multi-instance learning problem, where models learn to summarize commonsense relations from a bag of images about an entity pair without any human annotation on image instances. To address the problem, CLEVER leverages vision-language pre-training models for deep understanding of each image in the bag, and selects informative instances from the bag to summarize commonsense entity relations via a novel contrastive attention mechanism. Comprehensive experimental results in held-out and human evaluation show that CLEVER can extract commonsense knowledge in promising quality, outperforming pre-trained language model-based methods by 3.9 AUC and 6.4 mAUC points. The predicted commonsense scores show strong correlation with human judgment with a 0.78 Spearman coefficient. Moreover, the extracted commonsense can also be grounded into images with reasonable interpretability. The data and codes can be obtained at https://github.com/thunlp/CLEVER.
DNG: Taxonomy Expansion by Exploring the Intrinsic Directed Structure on Non-gaussian Space
Authors: Songlin Zhai; Weiqing Wang; Yuanfang Li; Yuan Meng
Venue: AAAI 2023 (main)

Abstract: Taxonomy expansion is the process of incorporating a large number of additional nodes (i.e., ''queries'') into an existing taxonomy (i.e., ''seed''), with the most important step being the selection of appropriate positions for each query.
Enormous efforts have been made by exploring the seed's structure.
However, existing approaches are deficient in their mining of structural information in two ways: poor modeling of the hierarchical semantics and failure to capture directionality of the is-a relation.
This paper seeks to address these issues by explicitly denoting each node as the combination of inherited feature (i.e., structural part) and incremental feature (i.e., supplementary part).
Specifically, the inherited feature originates from ''parent'' nodes and is weighted by an inheritance factor.
With this node representation, the hierarchy of semantics in taxonomies (i.e., the inheritance and accumulation of features from ''parent'' to ''child'') could be embodied.
Additionally, based on this representation, the directionality of the is-a relation could be easily translated into the irreversible inheritance of features.
Inspired by the Darmois-Skitovich Theorem, we implement this irreversibility by a non-Gaussian constraint on the supplementary feature.
A log-likelihood learning objective is further utilized to optimize the proposed model (dubbed DNG), whereby the required non-Gaussianity is also theoretically ensured.
Extensive experimental results on two real-world datasets verify the superiority of DNG relative to several strong baselines.
Quality-Aware Self-Training on Differentiable Synthesis of Rare Relational Data
Authors: Chongsheng Zhang; Yaxin Hou; Ke Chen; Shuang Cao; Gaojuan Fan; Ji Liu
Venue: AAAI 2023 (main)

Abstract: Data scarcity is a very common real-world problem that poses a major  challenge to data-driven analytics. Although a lot of data-balancing approaches have been proposed to mitigate this problem, they may drop some useful information or fall into the overfitting problem. Generative Adversarial Network (GAN) based data synthesis methods can alleviate such a problem but lack of quality control over the generated samples. Moreover, the latent associations between the attribute set and the class labels in a relational data cannot be easily captured by a vanilla GAN. In light of this, we introduce an end-to-end self-training scheme (namely, Quality-Aware Self-Training) for rare relational data synthesis, which generates labeled synthetic data via pseudo labeling on GAN-based synthesis. We design a semantic pseudo labeling module to first control the quality of the generated features/samples, then calibrate their semantic labels via a classifier committee consisting of multiple pre-trained shallow classifiers. The high-confident generated samples with calibrated pseudo labels are then fed into a semantic classification network as augmented samples for self-training. We conduct extensive experiments on 20 benchmark datasets of different domains, including 14 industrial datasets. The results show that our method significantly outperforms state-of-the-art methods, including two recent GAN-based data synthesis schemes. Codes are available at https://github.com/yaxinhou/QAST.