GenAI4ELab/papercli-papers huggingface dataset:
Practical Anytime Algorithms for Judicious Partitioning of Active Directory Attack Graphs
Authors: Yumeng Zhang; Max Ward; Hung Nguyen
Venue: IJCAI 2024 (main)

Abstract: Given a directed graph, a set of source nodes, a target node and a budget, we study the problem of maximizing the number of source nodes disconnected from the target node by removing edges not exceeding the budget. Our model is mainly motivated by a cyber security use case where we need to minimize the attack surface of a Windows Active Directory system. In these high-profile attacks, the attackers first compromise a source (i.e., a compromised user node) and then laterally move to a destination (i.e., a high-privileged admin node). Our aim is to minimize the number of users with a path to the admin. We first prove that the problem is NP-hard. Algorithms for exact optimality usually struggle to converge on graphs that approach real-world network scales and therefore are not practical for usage. In light of this, we study anytime algorithms that return an acceptable result whenever the algorithm is terminated, and can improve optimality by allowing longer computational time. We observe the source connectivity of directed graphs, based on which we propose a novel anytime algorithm---the spiral algorithm. We also develop two Monte Carlo Tree Search (MCTS) algorithms as a baseline to study the performance of typical anytime algorithms for our problem, and show that the spiral algorithm improves the optimality at a significantly faster speed and therefore exhibits better anytime behavior compared with MCTS.
Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
Authors: Yanhui Zhu; Samik Basu; A. Pavan
Venue: IJCAI 2024 (main)

Abstract: We present an evolutionary algorithm evo-SMC for the problem of Submodular Maximization under Cost constraints (SMC). Our algorithm achieves 1/2-approximation with a high probability 1-1/n within O(n2 K) iterations, where K denotes the maximum size of a feasible solution set with cost constraint B. To the best of our knowledge, this is the best approximation guarantee offered by evolutionary algorithms for this problem. We further refine evo-SMC and develop st-evo-SMC. This stochastic version yields a significantly faster algorithm while maintaining the approximation ratio of 1/2, with probability 1-epsilon. The required number of iterations reduces to O(nK log(1/epsilon)/p), where the user defined parameters p represents the stochasticity probability, and epsilon denotes the error threshold. Finally, the empirical evaluations carried out through extensive experimentation substantiate the efficiency and effectiveness of our proposed algorithms. Our algorithms consistently outperform existing methods, producing higher-quality solutions.
A New Paradigm for Counterfactual Reasoning in Fairness and Recourse
Authors: Lucius E.J. Bynum; Joshua R. Loftus; Julia Stoyanovich
Venue: IJCAI 2024 (main)

Abstract: Counterfactuals underpin numerous techniques for auditing and understanding artificial intelligence (AI) systems. The traditional paradigm for counterfactual reasoning in this literature is the interventional counterfactual, where hypothetical interventions are imagined and simulated. For this reason, the starting point for causal reasoning about legal protections and demographic data in AI is an imagined intervention on a legally-protected characteristic, such as ethnicity, race, gender, disability, age, etc. We ask, for example, what would have happened had your race been different? An inherent limitation of this paradigm is that some demographic interventions — like interventions on race — may not be well-defined or translate into the formalisms of interventional counterfactuals. In this work, we explore a new paradigm based instead on the backtracking counterfactual, where rather than imagine hypothetical interventions on legally-protected characteristics, we imagine alternate initial conditions while holding these characteristics fixed. We ask instead, what would explain a counterfactual outcome for you as you actually are or could be? This alternate framework allows us to address many of the same social concerns, but to do so while asking fundamentally different questions that do not rely on demographic interventions.
Anytime Sorting Algorithms
Authors: Emma Caizergues; François Durand; Fabien Mathieu
Venue: IJCAI 2024 (main)

Abstract: This paper addresses the anytime sorting problem, aiming to develop algorithms providing tentative estimates of the sorted list at each execution step. Comparisons are treated as steps, and the Spearman's footrule metric evaluates estimation accuracy. We propose a general approach for making any sorting algorithm anytime and introduce two new algorithms: multizip sort and Corsort. Simulations showcase the superior performance of both algorithms compared to existing methods. Multizip sort keeps a low global complexity, while Corsort produces intermediate estimates surpassing previous algorithms.
Individual Causal Structure Learning from Population Data
Authors: Wei Chen; Xiaokai Huang; Zijian Li; Ruichu Cai; Zhiyi Huang; Zhifeng Hao
Venue: IJCAI 2024 (main)

Abstract: Learning the causal structure of each individual plays a crucial role in neuroscience, biology, and so on. Existing methods consider data from each individual separately, which may yield inaccurate causal structure estimations in limited samples. To leverage more samples, we consider incorporating data from all individuals as population data. We observe that the variables of all individuals are influenced by the common environment variables they share. These shared environment variables can be modeled as latent variables and serve as a bridge connecting data from different individuals. In particular, we propose an Individual Linear Acyclic Model (ILAM) for each individual from population data, which models the individual's variables as being linearly influenced by their parents, in addition to environment variables and noise terms. Theoretical analysis shows that the model is identifiable when all environment variables are non-Gaussian, or even if some are Gaussian with an adequate diversity in the variance of noises for each individual. We then develop an individual causal structures learning method based on the Share Independence Component Analysis technique. Experimental results on synthetic and real-world data demonstrate the correctness of the method even when the sample size of each individual's data is small.
Online Learning of Capacity-Based Preference Models
Authors: Margot Herin; Patrice Perny; Nataliya Sokolovska
Venue: IJCAI 2024 (main)

Abstract: In multicriteria decision making, sophisticated decision models often involve a non-additive set function (named capacity) to define the weights of all subsets of criteria. This makes it possible to model criteria interactions, leaving room for a diversity of attitudes in criteria aggregation. Fitting a capacity-based decision model to a given Decision Maker is a challenging problem and several batch learning methods have been proposed in the literature to derive the capacity from a database of preference examples. In this paper, we introduce an online algorithm for learning a sparse representation of the capacity, designed for decision contexts where preference examples become available sequentially. Our method based on regularized dual averaging is also well fitted to decision contexts involving a large number of preference examples or a large number of criteria. Moreover, we propose a variant making it possible to include normative constraints on the capacity (e.g., monotonicity, supermodularity) while preserving scalability, based on the alternating direction method of multipliers.
Dirichlet-based Uncertainty Quantification for Personalized Federated Learning with Improved Posterior Networks
Authors: Nikita Kotelevskii; Samuel Horváth; Karthik Nandakumar; Martin Takac; Maxim Panov
Venue: IJCAI 2024 (main)

Abstract: In modern federated learning, one of the main challenges is to account for inherent heterogeneity and the diverse nature of data distributions for different clients. This problem is often addressed by introducing personalization of the models towards the data distribution of the particular client. However, a personalized model might be unreliable when applied to the data that is not typical for this client. Eventually, it may perform worse for these data than the non-personalized global model trained in a federated way on the data from all the clients. This paper presents a new approach to federated learning that allows selecting a model from global and personalized ones that would perform better for a particular input point. It is achieved through a careful modeling of predictive uncertainties that helps to detect local and global in- and out-of-distribution data and use this information to select the model that is confident in a prediction. The comprehensive experimental evaluation on the popular real-world image datasets shows the superior performance of the model in the presence of out-of-distribution data while performing on par with state-of-the-art personalized federated learning algorithms in the standard scenarios.
Proportion-based Sensitivity Analysis of Uncontrolled Confounding Bias in Causal Inference
Authors: Haruka Yoshida; Manabu Kuroki
Venue: IJCAI 2024 (main)

Abstract: Uncontrolled confounding bias causes a spurious relationship between an exposure variable and an outcome variable and precludes reliable evaluation of the causal effect from observed data.Thus, it is important to observe a sufficient set of confounders to reliably evaluate the causal effect.However, there is no statistical method for judging whether an available set of covariates is sufficient to derive a reliable estimator for the causal effect.To address this problem, we focus on the fact that the mean squared error (MSE) of the outcome variable with respect to the average causal risk can be described as the sum of "the conditional variance of the outcome variable given the exposure variable" and "the square of the uncontrolled confounding bias".We then propose a novel sensitivity analysis, namely, the proportion-based sensitivity analysis of uncontrolled confounding bias in causal effects (PSA) in which the sensitivity parameter is formulated as the proportion of "the square of the uncontrolled confounding bias" to the MSE, and we clarify some properties.We also demonstrate the applicability of the PSA through two case studies.
CausalNET: Unveiling Causal Structures on Event Sequences by Topology-Informed Causal Attention
Authors: Hua Zhu; Hong Huang; Kehan Yin; Zejun Fan; Hai Jin; Bang Liu
Venue: IJCAI 2024 (main)

Abstract: Causal discovery on event sequences holds a pivotal significance across domains such as healthcare, finance, and industrial systems. The crux of this endeavor lies in unraveling causal structures among event types, typically portrayed as directed acyclic graphs (DAGs). Nonetheless, prevailing methodologies often grapple with untenable assumptions and intricate optimization hurdles. To address these challenges, we present a novel model named CausalNET. At the heart of CausalNET is a special prediction module based on the Transformer architecture, which prognosticates forthcoming events by leveraging historical occurrences, with its predictive prowess amplified by a trainable causal graph engineered to fathom causal relationships among event types. Further, to augment the predictive paradigm, we devise a causal decay matrix to encapsulate the reciprocal influence of events upon each other within the topological network. During training, we alternatively refine the prediction module and fine-tune the causal graph. Comprehensive evaluation on a spectrum of real-world and synthetic datasets underscores the superior performance and scalability of CausalNET, which marks a promising step forward in the realm of causal discovery. Code and Appendix are available at https://github.com/CGCL-codes/CausalNET.
Automated Essay Scoring Using Discourse External Knowledge
Authors: Nisrine Ait Khayi; Vasile Rus
Venue: IJCAI 2024 (main)

Abstract: The Automated Essay Scoring (AES) task is an important NLP research problem given its significance for the education ecosystem. Recently, researchers started to apply a hybrid approach to this task. This hybrid approach incorporates into a deep learning model expert features that assess a particular dimension of the essay. Motivated by these successes, we propose to automatically assess essays using a hybrid approach that relies on external discourse knowledge. Our proposed model consists of using transformer-based embeddings to generate semantic representations of essays. Then, we incorporate several discourse features into these representations. Finally, we apply a linear classifier to generate the final score. To evaluate the effectiveness of this approach, we have conducted extensive experiments using the Automated Student Assessment Prize dataset (ASAP). The performance of the proposed model has been evaluated using the Quadratic Weighted Kappa (QWK) metric. The experimental results demonstrate the effectiveness of this approach in comparison with several existing solutions in literature.
Using Causal Inference to Investigate Contraceptive Discontinuation in Sub-Saharan Africa
Authors: Victor Akinwande; Megan MacGregor; Celia Cintas; Ehud Karavani; Dennis Wei; Kush R. Varshney; Pablo Nepomnaschy
Venue: IJCAI 2024 (main)

Abstract: Discontinuation rates vary by family planning method and across socio-economic contexts. Understanding these variations and their causes is paramount for developing and implementing policies aimed at curbing discontinuation rates. Randomized controlled trials (RCTs) are ideal for obtaining this information, but this design can be extremely expensive and logistically complex. The ongoing collection of comprehensive data sets, such as Demographic and Health Surveys (DHS data), when combined with machine learning methods, present an alternative and relatively cost-effective means of evidence gathering for policy development. Here, we use causal inference to estimate the effect of injectable contraceptive use on discontinuation over the 12-month period that follows its adoption. To that aim, we use retrospective observational data from seven sub-Saharan African countries captured by the DHS’ Contraceptive Calendar. We use machine learning methods to characterize data regions that share common covariate support. We find that the use of injectables increased the risk of discontinuation in four of the seven countries analyzed. Consistent with existing literature, we find that concerns with the side-effects of injectables appear to be the most frequent reason for discontinuation. However, these risks decreased after adjusting for socio-economic factors. As risk estimates may not apply uniformly within populations, we characterized the sub-populations for robust estimations by their geographical region, level of unmet needs, marital status, level of education, and age of first sex.
Transfer Learning Using Inaccurate Physics Rule for Streamflow Prediction
Authors: Tianshu Bao; Taylor Thomas Johnson; Xiaowei Jia
Venue: IJCAI 2024 (main)

Abstract: Accurate streamflow prediction is critical for ensuring water supply and detecting floods, while also providing essential hydrological inputs for other scientific models in fields such as climate and agriculture. Recently, deep learning models have been shown to achieve state-of-the-art regionalization performance by building a global hydrologic model. These models predict streamflow given catchment physical characteristics and weather forcing data. However, these models are only focused on gauged basins and cannot adapt to ungaugaed basins, i.e., basins without training data. Prediction in Ungauged Basins (PUB) is considered one of the most important challenges in hydrology, as most basins in the United States and around the world have no observations. In this work, we propose a meta-transfer learning approach by enhancing imperfect physics equations that facilitate model adaptation. Intuitively, physical equations can often be used to regularize deep learning models to achieve robust regionalization performance under gauged scenarios, but they can be inaccurate due to the simplified representation of physics. We correct such uncertainty in physical equation by residual approximation and let these corrected equations guide the model training process. We evaluated the proposed method for predicting daily streamflow on the catchment attributes and meteorology for large-sample studies (CAMELS) dataset. The experiment results on hydrological data over 19 years demonstrate the effectiveness of the proposed method in ungauged scenarios.
Empathy and AI: Achieving Equitable Microtransit for Underserved Communities
Authors: Eleni Bardaka; Pascal Van Hentenryck; Crystal Chen Lee; Christopher B. Mayhorn; Kai Monast; Samitha Samaranayake; Munindar P. Singh
Venue: IJCAI 2024 (main)

Abstract: This paper describes a newly launched project that will produce a new approach to public microtransit for underserved communities. Public microtransit cannot rely on pricing signals to manage demand, and current approaches face the challenges of simultaneously being underutilized and overextended. This project conceives of the setting as a sociotechnical system. Its main idea is to engage users through AI agents in conjunction with platform constraints to find solutions that purely technical conceptions cannot find. The project was specified over an intense series of discussions with key stakeholders (riders, city government, and nongovernmental agencies) and brings together expertise in the disciplines of AI, Operations Research, Urban Planning, Psychology, and Community Development. The project will culminate in a pilot study, results from which will facilitate the transfer of its technology to additional communities.
Functional Graph Convolutional Networks: A Unified Multi-task and Multi-modal Learning Framework to Facilitate Health and Social-Care Insights
Authors: Tobia Boschi; Francesca Bonin; Rodrigo Ordonez-Hurtado; Cécile Rousseau; Alessandra Pascale; John Dinsmore
Venue: IJCAI 2024 (main)

Abstract: This paper introduces a novel Functional Graph Convolutional Network (funGCN) framework that combines Functional Data Analysis and Graph Convolutional Networks to address the complexities of multi-task and multi-modal learning in digital health and longitudinal studies. With the growing importance of health solutions to improve health care and social support, ensure healthy lives, and promote well-being at all ages, funGCN offers a unified approach to handle multivariate longitudinal data for multiple entities and ensures interpretability even with small sample sizes. Key innovations include task-specific embedding components that manage different data types, the ability to perform classification, regression, and forecasting, and the creation of a knowledge graph for insightful data interpretation. The efficacy of funGCN is validated through simulation experiments and a real-data application. funGCN source code is publicly available at https://github.com/IBM/funGCN.
Fitness Activity Recognition Using a Novel Pressure Sensing Mat and Machine Learning for the Future of Accessible Training
Authors: Katia Bourahmoune; Karlos Ishac; Marc Carmichael
Venue: IJCAI 2024 (main)

Abstract: Physical inactivity is still a major problem contributing to a growing public health crisis despite a fast-expanding body of technological solutions and wellness research around fitness training. The inaccessibility of professional fitness training remains a leading cause of this gap for reasons encompassing socioeconomic factors, cultural and demographic barriers, and more recently the threat of global pandemics that disrupt traditional modes of staying physically active. Previous lines of work have explored using AI for fitness activity recognition from various sensing modalities such as computer vision, wearable sensors, and force and pressure sensors. However, these works are limited by their feasibility, deployability, and accessibility in real-world scenarios, in addition to the technical challenges faced by each modality for accurate and reliable activity recognition. In this paper, we propose an accessible system for gym activity recognition and correction focusing on foundational fitness activities using ML and a novel pressure sensing mat, and validate its deployability in a real-world use case in a natural gym setting. We present the detailed and previously under-investigated Centre of Pressure (COP) profile of four main gym activities in terms of several COP-related metrics specifically as targets for ML-based recognition tasks. Based on this, we identify COP displacement and COP balance measures as important features for ML-based recognition of these fitness activities for future research in this area. Furthermore, we compare the performance of several ML models in the activity recognition task, achieving 98.5% recognition accuracy using ML models suitable for real-time deployment. Finally, we demonstrate the feasibility of our system in a live real-world with use case in a natural gym environment.
VulnerabilityMap: An Open Framework for Mapping Vulnerability among Urban Disadvantaged Populations in the United States
Authors: Lin Chen; Yong Li; Pan Hui
Venue: IJCAI 2024 (main)

Abstract: Cities are crucibles of numerous opportunities, but also hotbeds of inequality. The plight of disadvantaged populations who are ``left behind'' within urban environments has been an increasingly pressing concern, which poses substantial threats to the realization of the UN SDG agenda. However, a comprehensive framework for studying this urban dilemma is currently absent, preventing researchers from developing AI models for social good prediction and intervention. To fill this gap, we construct VulnerabilityMap, a framework to meticulously dissect the challenges faced by urban disadvantaged populations, unraveling their vulnerability to a spectrum of shocks and stresses that are categorized through the prism of Maslow's hierarchy of needs. Specifically, we systematically collect large-scale multi-sourced census and web-based data covering more than 328 million people in the United States regarding demographic features, neighborhood environments, offline mobility behaviors, and online social connections. These features are further related to vulnerability outcomes from short-term shocks such as COVID-19 and long-term physiological, social, and self-actualization stresses. Leveraging our framework, we construct machine learning models that exhibit strong performance in predicting vulnerability outcomes from various disadvantage features, which shows the promising utility of our framework to support targeted AI models. Moreover, we provide model-based explainability analysis to interpret the reasons underlying model predictions, shedding light on intricate social factors that trap certain populations inside vulnerable situations. Our constructed dataset is publicly available at https://github.com/LinChen-65/VulnerabilityMap/.