GenAI4ELab/papercli-papers huggingface dataset:
Identification of Causal Structure in the Presence of Missing Data with Additive Noise Model
Authors: Jie Qiao; Zhengming Chen; Jianhua Yu; Ruichu Cai; Zhifeng Hao
Venue: AAAI 2024 (main)

Abstract: Missing data are an unavoidable complication frequently encountered in many causal discovery tasks. 
When a missing process depends on the missing values themselves (known as self-masking missingness), the recovery of the joint distribution becomes unattainable, and detecting the presence of such self-masking missingness remains a perplexing challenge. Consequently, due to the inability to reconstruct the original distribution and to discern the underlying missingness mechanism, simply applying existing causal discovery methods would lead to wrong conclusions. In this work, we found that the recent advances additive noise model has the potential for learning causal structure under the existence of the self-masking missingness. With this observation, we aim to investigate the identification problem of learning causal structure from missing data under an additive noise model with different missingness mechanisms, where the `no self-masking missingness' assumption can be eliminated appropriately. 
Specifically, we first elegantly extend the scope of identifiability of causal skeleton to the case with weak self-masking missingness (i.e., no other variable could be the cause of self-masking indicators except itself). We further provide the sufficient and necessary identification conditions of the causal direction under additive noise model and show that the causal structure can be identified up to an IN-equivalent pattern. We finally propose a practical algorithm based on the above theoretical results on learning the causal skeleton and causal direction. Extensive experiments on synthetic and real data demonstrate the efficiency and effectiveness of the proposed algorithms.
Causal Discovery from Poisson Branching Structural Causal Model Using High-Order Cumulant with Path Analysis
Authors: Jie Qiao; Yu Xiang; Zhengming Chen; Ruichu Cai; Zhifeng Hao
Venue: AAAI 2024 (main)

Abstract: Count data naturally arise in many fields, such as finance, neuroscience, and epidemiology, and discovering causal structure among count data is a crucial task in various scientific and industrial scenarios. One of the most common characteristics of count data is the inherent branching structure described by a binomial thinning operator and an independent Poisson distribution that captures both branching and noise. For instance, in a population count scenario, mortality and immigration contribute to the count, where survival follows a Bernoulli distribution, and immigration follows a Poisson distribution. However, causal discovery from such data is challenging due to the non-identifiability issue: a single causal pair is Markov equivalent, i.e.,  X->Y and Y->X are distributed equivalent. Fortunately, in this work, we found that the causal order from X to its child Y is identifiable if X is a root vertex and has at least two directed paths to Y, or the ancestor of X with the most directed path to X has a directed path to Y without passing X. Specifically, we propose a Poisson Branching Structure Causal Model (PB-SCM) and perform a path analysis on PB-SCM using high-order cumulants. Theoretical results establish the connection between the path and cumulant and demonstrate that the path information can be obtained from the cumulant. With the path information, causal order is identifiable under some graphical conditions. A practical algorithm for learning causal structure under PB-SCM is proposed and the experiments demonstrate and verify the effectiveness of the proposed method.
A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the Same Skeleton
Authors: Vidya Sagar Sharma
Venue: AAAI 2024 (main)

Abstract: Causal DAGs (also known as Bayesian networks) are a popular tool for encoding
conditional dependencies between random variables. In a causal DAG, the random
variables are modeled as vertices in the DAG, and it is stipulated that every
random variable is independent of its non-descendants conditioned on its parents. It
is possible, however, for two different causal DAGs on the same set of random
variables to encode exactly the same set of conditional dependencies. Such
causal DAGs are said to be Markov equivalent, and equivalence classes of
Markov equivalent DAGs are known as Markov Equivalent Classes (MECs).
Beautiful combinatorial characterizations of MECs have been developed in the
past few decades, and it is known, in particular, that all DAGs in the same MEC
must have the same skeleton (underlying undirected graph) and v-structures (induced subgraph of the form a->b<-c).

These combinatorial characterizations also suggest several natural algorithmic
questions. One of these is: given an undirected graph G as input, how many
distinct Markov equivalence classes have the skeleton G? Much work has been
devoted in the last few years to this and other closely related problems.
However, to the best of our knowledge, a polynomial-time algorithm for the
problem remains unknown.

In this paper, we make progress towards this goal by giving a fixed parameter
tractable algorithm for the above problem, with the parameters being the
treewidth and the maximum degree of the input graph G. The main technical
ingredient in our work is a construction we refer to as shadow,
which lets us create a local description of long-range constraints imposed
by the combinatorial characterizations of MECs.
Learning Bayesian Network Classifiers to Minimize the Class Variable Parameters
Authors: Shouta Sugahara; Koya Kato; Maomi Ueno
Venue: AAAI 2024 (main)

Abstract: This study proposes and evaluates a new Bayesian network classifier (BNC) having an I-map structure with the fewest class variable parameters among all structures for which the class variable has no parent. Moreover, a new learning algorithm to learn our proposed model is presented. The proposed method is guaranteed to obtain the true classification probability asymptotically. Moreover, the method has lower computational costs than those of exact learning BNC using marginal likelihood. Comparison experiments have demonstrated the superior performance of the proposed method.
Bayesian Inference with Complex Knowledge Graph Evidence
Authors: Armin Toroghi; Scott Sanner
Venue: AAAI 2024 (main)

Abstract: Knowledge Graphs (KGs) provide a widely used format for representing entities and their relationships and have found use in diverse applications including question answering and recommendation.  A majority of current research on KG inference has focused on reasoning with atomic facts (triples) and has disregarded the possibility of making complex evidential observations involving logical operators (negation, conjunction, disjunction) and quantifiers (existential, universal).  Further, while the application of complex evidence has been explored in KG-based query answering (KGQA) research, in many practical online settings, observations are made sequentially.  For example, in KGQA, additional context may be incrementally suggested to narrow down the answer.  Or in interactive recommendation, user critiques may be expressed sequentially in order to narrow down a set of preferred items.  Both settings are indicative of information filtering or tracking tasks that are reminiscent of belief tracking in Bayesian inference.  In fact, in this paper, we precisely cast the problem of belief tracking over unknown KG entities given incremental complex KG evidence as a Bayesian filtering problem.  Specifically, we leverage Knowledge-based Model Construction (KBMC) over the logical KG evidence to instantiate a Markov Random Field (MRF) likelihood representation to perform closed-form Bayesian inference with complex KG evidence (BIKG).  We experimentally evaluate BIKG in incremental KGQA and interactive recommendation tasks demonstrating that it outperforms non-incremental methodologies and leads to better incorporation of conjunctive evidence vs. existing complex KGQA methods like CQD that leverage fuzzy T-norm operators. Overall, this work demonstrates a novel, efficient, and unified perspective of logic, KGs, and online inference through the lens of closed-form BIKG.
Exact, Fast and Expressive Poisson Point Processes via Squared Neural Families
Authors: Russell Tsuchida; Cheng Soon Ong; Dino Sejdinovic
Venue: AAAI 2024 (main)

Abstract: We introduce squared neural Poisson point processes (SNEPPPs) by parameterising the intensity function by the squared norm of a two layer neural network.
When the hidden layer is fixed and the second layer has a single neuron, our approach resembles previous uses of squared Gaussian process or kernel methods, but allowing the hidden layer to be learnt allows for additional flexibility.
In many cases of interest, the integrated intensity function admits a closed form and can be computed in quadratic time in the number of hidden neurons.
We enumerate a far more extensive number of such cases than has previously been discussed.
Our approach is more memory and time efficient than naive implementations of squared or exponentiated kernel methods or Gaussian processes.
Maximum likelihood and maximum a posteriori estimates in a reparameterisation of the final layer of the intensity function can be obtained by solving a (strongly) convex optimisation problem using projected gradient descent. 
We demonstrate SNEPPPs on real, and synthetic benchmarks, and provide a software implementation.
Inference and Learning in Dynamic Decision Networks Using Knowledge Compilation
Authors: Gabriele Venturato; Vincent Derkinderen; Pedro Zuidberg Dos Martires; Luc De Raedt
Venue: AAAI 2024 (main)

Abstract: Decision making under uncertainty in dynamic environments is a fundamental AI problem in which agents need to determine which decisions (or actions) to make at each time step to maximise their expected utility. Dynamic decision networks (DDNs) are an extension of dynamic Bayesian networks with decisions and utilities. DDNs can be used to compactly represent Markov decision processes (MDPs). We propose a novel algorithm called mapl-cirup that leverages knowledge compilation techniques developed for (dynamic) Bayesian networks to perform inference and gradient-based learning in DDNs. Specifically, we knowledge-compile the Bellman update present in DDNs into dynamic decision circuits and evaluate them within an (algebraic) model counting framework. In contrast to other exact symbolic MDP approaches, we obtain differentiable circuits that enable gradient-based parameter learning.
Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
Authors: Marcel Wienöbst; Benito van der Zander; Maciej Liśkiewicz
Venue: AAAI 2024 (main)

Abstract: Causal effect estimation from observational data is a fundamental task in empirical sciences. It becomes particularly challenging when unobserved confounders are involved in a system. This paper focuses on front-door adjustment – a classic technique which, using observed mediators allows to identify causal effects even in the presence of unobserved confounding. While the statistical properties of the front-door estimation are quite well understood, its algorithmic aspects remained unexplored for a long time. In 2022, Jeong, Tian, and Bareinboim presented the first polynomial-time algorithm for finding sets satisfying the front-door criterion in a given directed acyclic graph (DAG), with an O(n³(n+m)) run time, where n denotes the number of variables and m the number of edges of the causal graph. In our work, we give the first linear-time, i.e., O(n+m), algorithm for this task, which thus reaches the asymptotically optimal time complexity. This result implies an O(n(n+m)) delay enumeration algorithm of all front-door adjustment sets, again improving previous work by a factor of n³. Moreover, we provide the first linear-time algorithm for finding a minimal front-door adjustment set. We offer implementations of our algorithms in multiple programming languages to facilitate practical usage and empirically validate their feasibility, even for large graphs.
Neural Causal Abstractions
Authors: Kevin Xia; Elias Bareinboim
Venue: AAAI 2024 (main)

Abstract: The ability of humans to understand the world in terms of cause and effect relationships, as well as their ability to compress information into abstract concepts, are two hallmark features of human intelligence. These two topics have been studied in tandem under the theory of causal abstractions, but it is an open problem how to best leverage abstraction theory in real-world causal inference tasks, where the true model is not known, and limited data is available in most practical settings. In this paper, we focus on a family of causal abstractions constructed by clustering variables and their domains, redefining abstractions to be amenable to individual causal distributions. We show that such abstractions can be learned in practice using Neural Causal Models, allowing us to utilize the deep learning toolkit to solve causal tasks (identification, estimation, sampling) at different levels of abstraction granularity. Finally, we show how representation learning can be used to learn abstractions, which we apply in our experiments to scale causal inferences to high dimensional settings such as with image data.
Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users
Authors: Hantao Yang; Xutong Liu; Zhiyong Wang; Hong Xie; John C. S. Lui; Defu Lian; Enhong Chen
Venue: AAAI 2024 (main)

Abstract: We study the problem of federated contextual combinatorial cascading bandits, where agents collaborate under the coordination of a central server to provide tailored recommendations to users. Existing works consider either a synchronous framework, necessitating full agent participation and global synchronization, or assume user homogeneity with identical behaviors. We overcome these limitations by considering (1) federated agents operating in an asynchronous communication paradigm, where no mandatory synchronization is required and all agents communicate independently with the server, (2) heterogeneous user behaviors, where users can be stratified into latent user clusters, each exhibiting distinct preferences. For this setting, we propose a UCB-type algorithm with delicate communication protocols. Through theoretical analysis, we give sub-linear regret bounds on par with those achieved in the synchronous framework, while incurring only logarithmic communication costs. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
Causal-Driven Skill Prerequisite Structure Discovery
Authors: Shenbao Yu; Yifeng Zeng; Fan Yang; Yinghui Pan
Venue: AAAI 2024 (main)

Abstract: Knowing a prerequisite structure among skills in a subject domain effectively enables several educational applications, including intelligent tutoring systems and curriculum planning. Traditionally, educators or domain experts use intuition to determine the skills' prerequisite relationships, which is time-consuming and prone to fall into the trap of blind spots. In this paper, we focus on inferring the prerequisite structure given access to students' performance on exercises in a subject. Nevertheless, it is challenging since students' mastery of skills can not be directly observed, but can only be estimated, i.e., its latency in nature. To tackle this problem, we propose a causal-driven skill prerequisite structure discovery (CSPS) method in a two-stage learning framework. In the first stage, we learn the skills' correlation relationships presented in the covariance matrix from the student performance data while, through the predicted covariance matrix in the second stage, we consider a heuristic method based on conditional independence tests and standardized partial variance to discover the prerequisite structure. We demonstrate the performance of the new approach with both simulated and real-world data. The experimental results show the effectiveness of the proposed model for identifying the skills' prerequisite structure.
Deep Copula-Based Survival Analysis for Dependent Censoring with Identifiability Guarantees
Authors: Weijia Zhang; Chun Kai Ling; Xuanhui Zhang
Venue: AAAI 2024 (main)

Abstract: Censoring is the central problem in survival analysis where either the time-to-event (for instance, death), or the time-to censoring (such as loss of follow-up) is observed for each sample. The majority of existing machine learning-based survival analysis methods assume that survival is conditionally independent of censoring given a set of covariates; an assumption that cannot be verified since only marginal distributions is available from the data. The existence of dependent censoring, along with the inherent bias in current estimators has been demonstrated in a variety of applications, accentuating the need for a more nuanced approach. However, existing methods that adjust for dependent censoring require practitioners to specify the ground truth copula. This requirement poses a significant challenge for practical applications, as model misspecification can lead to substantial bias. In this work, we propose a flexible deep learning-based survival analysis method that simultaneously accommodate for dependent censoring and eliminates the requirement for specifying the ground truth copula. We theoretically prove the identifiability of our model under a broad family of copulas and survival distributions. Experiments results from a wide range of datasets demonstrate that our approach successfully discerns the underlying dependency structure and significantly reduces survival estimation bias when compared to existing methods.
DOGE-Train: Discrete Optimization on GPU with End-to-End Training
Authors: Ahmed Abbas; Paul Swoboda
Venue: AAAI 2024 (main)

Abstract: We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs. We use a combination of graph neural networks (GNN) and a Lagrange decomposition based algorithm. We make the latter differentiable for end-to-end training and use GNNs to predict its algorithmic parameters. This allows to retain the algorithm's theoretical properties including dual feasibility and guaranteed non-decrease in the lower bound while improving it via training. We overcome suboptimal fixed points of the basic solver by additional non-parametric GNN update steps maintaining dual feasibility. For training we use an unsupervised loss. We train on smaller problems and test on larger ones showing strong generalization performance with a GNN comprising only around 10k parameters. Our solver achieves significantly faster performance and better dual objectives than its non-learned version, achieving close to optimal objective values of LP relaxations of very large structured prediction problems and on selected combinatorial ones. In particular, we achieve better objective values than specialized approximate solvers for specific problem classes while retaining their efficiency. Our solver has better any-time performance over a large time period compared to a commercial solver.
Delegation-Relegation for Boolean Matrix Factorization
Authors: Florent Avellaneda; Roger Villemaire
Venue: AAAI 2024 (main)

Abstract: The Boolean Matrix Factorization (BMF) problem aims to represent a n×m Boolean matrix as the Boolean product of two matrices of small rank k, where the product is computed using Boolean algebra operations. However, finding a BMF of minimum rank is known to be NP-hard, posing challenges for heuristic algorithms and exact approaches in terms of rank found and computation time, particularly as matrix size or the number of entries equal to 1 grows.
In this paper, we present a new approach to simplifying the matrix to be factorized by reducing the number of 1-entries, which allows to directly recover a Boolean factorization of the original matrix from its simplified version. We introduce two types of simplification: one that performs numerous simplifications without preserving the original rank and another that performs fewer simplifications but guarantees that an optimal BMF on the simplified matrix yields an optimal BMF on the original matrix. Furthermore, our experiments show that our approach outperforms existing exact BMF algorithms.
An Interpretable Approach to the Solutions of High-Dimensional Partial Differential Equations
Authors: Lulu Cao; Yufei Liu; Zhenzhong Wang; Dejun Xu; Kai Ye; Kay Chen Tan; Min Jiang
Venue: AAAI 2024 (main)

Abstract: In recent years, machine learning algorithms, especially deep learning, have shown promising prospects in solving Partial Differential Equations (PDEs). However, as the dimension increases, the relationship and interaction between variables become more complex, and existing methods are difficult to provide fast and interpretable solutions for high-dimensional PDEs. To address this issue, we propose a genetic programming symbolic regression algorithm based on transfer learning and automatic differentiation to solve PDEs. This method uses genetic programming to search for a mathematically understandable expression and combines automatic differentiation to determine whether the search result satisfies the PDE and boundary conditions to be solved. To overcome the problem of slow solution speed caused by large search space, we propose a transfer learning mechanism that transfers the structure of one-dimensional PDE analytical solution to the form of high-dimensional PDE solution. We tested three representative types of PDEs, and the results showed that our proposed method can obtain reliable and human-understandable real solutions or algebraic equivalent solutions of PDEs, and the convergence speed is better than the compared methods. Code of this project is at https://github.com/grassdeerdeer/HD-TLGP.
Sampling for Beyond-Worst-Case Online Ranking
Authors: Qingyun Chen; Sungjin Im; Benjamin Moseley; Chenyang Xu; Ruilong Zhang
Venue: AAAI 2024 (main)

Abstract: The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison.  The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case.
This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online.  This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform.  We design an online algorithm with strong theoretical guarantees.  The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. 
Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.