GenAI4ELab/papercli-papers huggingface dataset:
Exact Algorithms with New Upper Bounds for the Maximum k-plex Problem
Authors: Jiongzhi Zheng; Mingming Jin; Kun He
Venue: IJCAI 2025 (main)

Abstract: The Maximum k-plex Problem (MKP) is a degree relaxation of the widely known Maximum Clique Problem. As a practical NP-hard problem, MKP has many important real-world applications, such as the analysis of various complex networks. Branch-and-bound (BnB) algorithms are a type of well-studied and effective exact algorithms for MKP, and the key for BnB algorithms is the bound design. Recent BnB MKP algorithms involve two kinds of upper bounds based on graph coloring and partition, respectively, that work in different perspectives and thus are complementary with each other. We first propose a new coloring-based upper bound, termed Relaxed Graph Color Bound (RelaxGCB), that significantly outperforms the previous coloring-based upper bound. Then we further propose another new upper bound, termed RelaxPUB, that incorporates RelaxGCB and a partition-based upper bound in a novel way, making use of their complementarity. We apply RelaxGCB and RelaxPUB to state-of-the-art BnB MKP algorithms and produce eight new BnB algorithms. Extensive experiments using diverse k values on hundreds of instances based on dense or massive sparse graphs demonstrate the excellent performance and robustness of our proposed methods.
A Reduction-Based Algorithm for the Clique Interdiction Problem
Authors: Chenghao Zhu; Yi Zhou; Haoyu Jiang
Venue: IJCAI 2025 (main)

Abstract: The Clique Interdiction Problem (CIP) aims to minimize the size of the largest clique in a given graph by removing a given number of vertices. The CIP models a special Stackelberg game and has important applications in fields such as pandemic control and terrorist identification. However, the CIP is a bilevel graph optimization problem, making it very challenging to solve. Recently, data reduction techniques have been successfully applied in many (single-level) graph optimization problems like vertex cover. Motivated by this, we investigate a set of novel reduction rules and design a reduction-based algorithm, RECIP, for practically solving the CIP. RECIP enjoys an effective preprocessing procedure that systematically reduces the input graph, making the problem much easier to solve. Extensive experiments on 124 large real-world networks demonstrate the superior performance of RECIP and validate the effectiveness of the proposed reduction rules.
Attractor-based Closed List Search: Sparsifying the Closed List for Efficient Memory-Constrained Planning
Authors: Alvin Zou; Muhammad Suhail Saleem; Maxim Likhachev
Venue: IJCAI 2025 (main)

Abstract: Best-first search algorithms such as A* and Weighted A* are widely used tools. However, their high memory requirements often make them impractical for memory-constrained applications, such as on-board planning for interplanetary rovers, drones, and embedded systems. One popular strategy among memory-efficient approaches developed to address this challenge is to eliminate or sparsify the Closed list, a structure that tracks states explored by the search. However, such methods often incur substantial overhead in runtime, requiring recursive searches for solution reconstruction. In this work, we propose Attractor-based Closed List Search (ACLS), a novel framework that sparsely represents the Closed list using a small subset of states, termed attractors. ACLS intelligently identifies attractor states in a way that enables efficient solution reconstruction while preserving theoretical guarantees on the quality of the solution. Furthermore, we also introduce a lazy variant, Lazy-ACLS, which defers the computation of attractor states until necessary, substantially improving planning speed. We demonstrate the efficacy of ACLS used in conjunction with A*, Weighted A*, and Dijkstra’s searches across multiple domains including 2D and 3D navigation, Sliding Tiles, and Towers of Hanoi. Our experimental results demonstrate that ACLS significantly reduces memory usage, maintaining only 9% of the states typically stored in a Closed list, while achieving comparable planning times and outperforming state-of-the-art approaches. Source code can be found at github.com/alvin-ruihua-zou/ACLS.
LP-Based Weighted Model Integration over Non-Linear Real Arithmetic
Authors: S. Akshay; Supratik Chakraborty; Soroush Farokhnia; Amir Goharshady; Harshit Jitendra Motwani; Đorđe Žikelić
Venue: IJCAI 2025 (main)

Abstract: Weighted model integration (WMI) is a relatively recent formalism that has received significant interest as a technique for solving probabilistic inference tasks with complicated weight functions. Existing methods and tools are mostly focused on linear and polynomial functions and provide limited support for WMI of rational or radical functions, which naturally arise in several applications. In this work, we present a novel method for approximate WMI, which provides more effective support for the wide class of semi-algebraic functions that includes rational and radical functions, with literals defined over non-linear real arithmetic. Our algorithm leverages Farkas’ lemma and Handelman's theorem from real algebraic geometry to reduce WMI to solving a number of linear programming (LP) instances. The algorithm provides formal guarantees on the error bound of the obtained approximation and can reduce it to any user-defined value epsilon. Furthermore, our approach is perfectly parallelizable. Finally, we present extensive experimental results, demonstrating the superior performance of our method on a range of WMI tasks for rational and radical functions when compared to state-of-the-art tools for WMI, in terms of both applicability and tightness.
Most Probable Explanation in Probabilistic Answer Set Programming
Authors: Damiano Azzolini; Giuseppe Mazzotta; Francesco Ricca; Fabrizio Riguzzi
Venue: IJCAI 2025 (main)

Abstract: Most Probable Explanation (MPE) is a fundamental problem in statistical relational artificial intelligence. In the context of Probabilistic Answer Set Programming (PASP), solving MPE is still an open research problem. In this paper, we present three novel approaches for solving the MPE task in PASP that are based on: i) Algebraic Model Counting, ii) Answer Set Programming (ASP), and iii) ASP with quantifiers (ASP(Q)). These approaches are implemented and evaluated against existing solvers across different datasets and configurations. Empirical results demonstrate that the novel solutions consistently outperform existing alternatives for non-stratified programs.
Polynomial-Time Relational Probabilistic Inference in Open Universes
Authors: Luise Ge; Brendan Juba; Kris Nilsson
Venue: IJCAI 2025 (main)

Abstract: Reasoning under uncertainty is a fundamental challenge in Artificial Intelligence. As with most of these challenges, there is a harsh dilemma between the expressive power of the language used, and the tractability of the computational problem posed by reasoning. Inspired by human reasoning, we introduce a method of first-order relational probabilistic inference that satisfies both criteria, and can handle hybrid (discrete and continuous) variables. Specifically, we extend sum-of-squares logic of expectation to relational settings, demonstrating that lifted reasoning in the bounded-degree fragment for knowledge bases of bounded quantifier rank can be performed in polynomial time, even with an a priori unknown and/or countably infinite set of objects. Crucially, our notion of tractability is framed in proof-theoretic terms, which extends beyond the syntactic properties of the language or queries. We are able to derive the tightest bounds provable by proofs of a given degree and size and establish completeness in our sum-of-squares refutations for fixed degrees.
Phenotypic Profile-Informed Generation of Drug-Like Molecules via Dual-Channel Variational Autoencoders
Authors: Hui Liu; Shiye Tian; Xuejun Liu
Venue: IJCAI 2025 (main)

Abstract: The de novo generation of drug-like molecules capable of inducing desirable phenotypic changes is receiving increasing attention. However, previous methods predominantly rely on expression profiles to guide molecule generation, but overlook the perturbative effect of the molecules on cellular contexts. To overcome this limitation, we propose SmilesGEN, a novel generative model based on variational autoencoder (VAE) architecture to generate molecules with potential therapeutic effects. SmilesGEN integrates a pre-trained drug VAE (SmilesNet) with an expression profile VAE (ProfileNet), jointly modeling the interplay between drug perturbations and transcriptional responses in a common latent space. Specifically, ProfileNet is imposed to reconstruct pre-treatment expression profiles when eliminating drug-induced perturbations in the latent space, while SmilesNet is informed by desired expression profiles to generate drug-like molecules. Our empirical experiments demonstrate that SmilesGEN outperforms current state-of-the-art models in generating molecules with higher degree of validity, uniqueness, novelty, as well as higher Tanimoto similarity to known ligands targeting the relevant proteins. Moreover, we evaluate SmilesGEN for scaffold-based molecule optimization and generation of therapeutic agents, and confirmed its superior performance in generating molecules with higher similarity to approved drugs. SmilesGEN establishes a robust framework that leverages gene signatures to generate drug-like molecules that hold promising potential to induce desirable cellular phenotypic changes. The source code and datasets are available at: https://github.com/hliulab/SmilesGEN.
Approximate Lifted Model Construction
Authors: Malte Luttermann; Jan Speller; Marcel Gehrke; Tanya Braun; Ralf Möller; Mattis Hartwig
Venue: IJCAI 2025 (main)

Abstract: Probabilistic relational models such as parametric factor graphs enable efficient (lifted) inference by exploiting the indistinguishability of objects. In lifted inference, a representative of indistinguishable objects is used for computations. To obtain a relational (i.e., lifted) representation, the Advanced Colour Passing (ACP) algorithm is the state of the art. The ACP algorithm, however, requires underlying distributions, encoded as potential-based factorisations, to exactly match to identify and exploit indistinguishabilities. Hence, ACP is unsuitable for practical applications where potentials learned from data inevitably deviate even if associated objects are indistinguishable. To mitigate this problem, we introduce the ε-Advanced Colour Passing (ε-ACP) algorithm, which allows for a deviation of potentials depending on a hyperparameter ε. ε-ACP efficiently uncovers and exploits indistinguishabilities that are not exact. We prove that the approximation error induced by ε-ACP is strictly bounded and our experiments show that the approximation error is close to zero in practice.
LLM-enhanced Score Function Evolution for Causal Structure Learning
Authors: Zidong Wang; Fei Liu; Qi Feng; Qingfu Zhang; Xiaoguang Gao
Venue: IJCAI 2025 (main)

Abstract: Causal structure learning (CSL) plays a pivotal role in causality and is often formulated as an optimization problem within score-and-search methods. Under the assumption of an infinite dataset and a predefined distribution, several well-established and consistent score functions have been shown to be both optimal and reliable for identifying ground-truth causal graphs. However, in practice, these idealized assumptions are often infeasible, which can result in CSL algorithms learning suboptimal structures. In this paper, we introduce L-SFE, a framework designed to automatically discover effective score functions by exploring the "score function space". L-SFE addresses this task from a bi-level optimization perspective. First, it leverages a Large Language Model (LLM) to interpret the characteristics of score functions and generate the corresponding code implementations. Next, L-SFE employs evolutionary algorithms along with carefully designed operators, to search for solutions with higher fitness. Additionally, we take the BIC as example and prove the consistency of the generated score functions. Experimental evaluations, conducted on discrete, continuous, and real datasets, demonstrate the high stability, generality and effectiveness of L-SFE.
Efficient Constraint-based Window Causal Graph Discovery in Time Series with Multiple Time Lags
Authors: Yewei Xia; Yixin Ren; Hong Cheng; Hao Zhang; Jihong Guan; Minchuan Xu; Shuigeng Zhou
Venue: IJCAI 2025 (main)

Abstract: We address the identification of direct causes in time series with multiple time lags, and propose a constraint-based window causal graph discovery method. A key advantage of our method is that the number of required conditional independence (CI) tests scales quadratically with the number of sub-series. The method first uses CI tests to find the minimum trek lag between two arbitrary sub-series, followed by designing an efficient CI testing strategy to identify the direct causes between them. We show that the method is both sound and complete under some graph constraints. We compare the proposed method with typical baselines on various datasets. Experimental results show that our method outperforms all the counterparts in both accuracy and running speed.
Two-stage Risk Control with Application to Ranked Retrieval
Authors: Yunpeng Xu; Mufang Ying; Wenge Guo; Zhi Wei
Venue: IJCAI 2025 (main)

Abstract: Practical machine learning systems often operate in multiple sequential stages, as seen in ranking and recommendation systems, which typically include a retrieval phase followed by a ranking phase. Effectively assessing prediction uncertainty and ensuring effective risk control in such systems pose significant challenges due to their inherent complexity. To address these challenges, we developed two-stage risk control methods based on the recently proposed learn-then-test (LTT) and conformal risk control (CRC) frameworks. Unlike the methods in prior work that address multiple risks, our approach leverages the sequential nature of the problem, resulting in reduced computational burden. We provide theoretical guarantees for our proposed methods and design novel loss functions tailored for ranked retrieval tasks. The effectiveness of our approach is validated through experiments on two large-scale, widely-used datasets: MSLR- Web and Yahoo LTRC.
Conditional Independent Test in the Presence of Measurement Error with Causal Structure Learning
Authors: Hongbin Zhang; Kezhou Chen; Nankai Lin; Aimin Yang; Zhifeng Hao; Zhengming Chen
Venue: IJCAI 2025 (main)

Abstract: Testing conditional independence is a critical task, particularly in causal discovery and learning in Bayesian networks. However, in many real-world scenarios, variables are often measured with errors, such as those introduced by insufficient measurement accuracy, complicating the testing process. This paper focuses on testing conditional independence in the linear non-Gaussian measurement error model, under the condition that measurement error noise follows a Gaussian distribution. By leveraging high-order cumulants, we derive rank constraints on the cumulant matrix and establish their role in effectively assessing conditional independence, even in the presence of measurement errors. Based on these theoretical results, we leverage the rank constraints of the cumulant matrix as a tool for conditional independence testing and incorporate it into the PC algorithm, resulting in the PC-ME algorithm — a method designed to learn causal structures from observed data while accounting for measurement errors. Experimental results demonstrate that the proposed method outperforms existing approaches, particularly in cases other methods encounter difficulties.
Situational-Constrained Sequential Resources Allocation via Reinforcement Learning
Authors: Libo Zhang; Yang Chen; Toru Takisaka; Kaiqi Zhao; Weidong Li; Jiamou Liu
Venue: IJCAI 2025 (main)

Abstract: Sequential Resource Allocation with situational constraints presents a significant challenge in real-world applications, where resource demands and priorities are context-dependent. This paper introduces a novel framework, SCRL, to address this problem. We formalize situational constraints as logic implications and develop a new algorithm that dynamically penalizes constraint violations. To handle situational constraints effectively, we propose a probabilistic selection mechanism to overcome limitations of traditional constraint reinforcement learning (CRL) approaches. We evaluate SCRL across two scenarios: medical resource allocation during a pandemic and pesticide distribution in agriculture. Experiments demonstrate that SCRL outperforms existing baselines in satisfying constraints while maintaining high resource efficiency, showcasing its potential for real-world, context-sensitive decision-making tasks.
SpeechHGT: A Multimodal Hypergraph Transformer for Speech-Based Early Alzheimer’s Disease Detection
Authors: Shagufta Abid; Dongyu Zhang; Ahsan Shehzad; Jing Ren; Shuo Yu; Hongfei Lin; Feng Xia
Venue: IJCAI 2025 (main)

Abstract: Early detection of Alzheimer's disease (AD) through spontaneous speech analysis represents a promising, non-invasive diagnostic approach. Existing methods predominantly rely on fusion-based multimodal deep learning, effectively integrating linguistic and acoustic features. However, these methods inadequately model higher-order interactions between modalities, reducing diagnostic accuracy. To address this, we introduce SpeechHGT, a multimodal hypergraph transformer designed to capture and learn higher-order interactions in spontaneous speech features. SpeechHGT encodes multimodal features as hypergraphs, where nodes represent individual features and hyperedges represent grouped interactions. A novel hypergraph attention mechanism enables robust modeling of both pairwise and higher-order interactions. Experimental evaluations on the DementiaBank datasets reveal that SpeechHGT achieves state-of-the-art performance, surpassing baseline models in accuracy and F1 score. These results highlight the potential of hypergraph-based models to improve AI-driven diagnostic tools for early AD detection.
DL-KDD: Dual-Lightness Knowledge Distillation for Action Recognition in the Dark
Authors: Chi-Jui Chang; Oscar Tai-Yuan Chen; Vincent S. Tseng
Venue: IJCAI 2025 (main)

Abstract: Human action recognition in dark videos is a challenging task for computer vision due to the low quality of the videos filmed in the dark. Recent studies focused on applying dark enhancement methods to improve the visibility of the video. However, such video processing results in the loss of critical information in the original (un-enhanced) video. Conversely, traditional two-stream methods are capable of learning information from both original and enhanced videos, but it can lead to a significant increase in the computational cost. To address these challenges, we propose a novel knowledge-distillation-based framework, named Dual-Lightness KnowleDge Distillation (DL-KDD), which simultaneously resolves the aforementioned issues by enabling a student model to obtain both original features and light-enhanced knowledge without additional complexity, thus improving the performance of the model and avoiding extra computational cost. Through comprehensive evaluations, the proposed DL-KDD, with only original video required as input during the inference phase, significantly outperforms state-of-the-art methods on the widely-used dark video datasets. The results highlight the excellence of our proposed knowledge-distillation-based framework for dark video human action recognition.
RF-DTR: A Multi-Stage DCT Token Regression Network for Progressive Rib Fracture Mask Refinement
Authors: ShouYu Chen; Liang Hu; JunTao Wang; Usman Naseem; Zhongyuan Lai; Qi Zhang
Venue: IJCAI 2025 (main)

Abstract: Rib fracture patterns are key indicators of trauma severity. Detecting and locating these fractures is a critical yet time-consuming task, especially in 3D imaging, due to their minute size and irregular geometries. Existing voxel-based spatial methods fail to capture frequency-domain variations inherent in imaging and do not replicate the progressive refinement process used by clinicians during manual annotation, leading to suboptimal results. We propose a novel regression network, RF-DTR, incorporating a gated regressor mechanism and operating entirely in the frequency domain to address these challenges. Specifically, we present an innovative spatial-frequency transform applied to volumes and corresponding masks. Furthermore, we introduce a Mahalanobis regularization technique to enhance the model and learn high-frequency DCT components relevant to clinical tasks. Finally, a hierarchical penalty is proposed to improve the confidence of the prediction. Extensive experiments confirm our method's superiority in handling complex, sparsely annotated medical imaging datasets.
Rethinking Remaining Useful Life Prediction with Scarce Time Series Data: Regression Under Indirect Supervision
Authors: Jiaxiang Cheng; Yipeng Pang; Guoqiang Hu
Venue: IJCAI 2025 (main)

Abstract: Supervised time series prediction relies on directly measured target variables, but real-world use cases such as predicting remaining useful life (RUL) involve indirect supervision, where the target variable is labeled as a function of another dependent variable. Trending temporal regression techniques rely on sequential time series inputs to capture temporal patterns, requiring interpolation when dealing with sparsely and irregularly sampled covariates along the timeline. However, interpolation can introduce significant biases, particularly with highly scarce data. In this paper, we address the RUL prediction problem with data scarcity as time series regression under indirect supervision. We introduce a unified framework called parameterized static regression, which takes single data points as inputs for regression of target values, inherently handling data scarcity without requiring interpolation. The time dependency under indirect supervision is captured via a parametrical rectification (PR) process, approximating a parametric function during inference with historical posteriori estimates, following the same underlying distribution used for labeling during training. Additionally, we propose a novel batch training technique for tasks in indirect supervision to prevent overfitting and enhance efficiency. We evaluate our model on public benchmarks for RUL prediction with simulated data scarcity. Our method demonstrates competitive performance in prediction accuracy when dealing with highly scarce time series data.