Main track accepted papers (Montreal)

137: Responsibility Gap in Collective Decision Making
Authors: Pavel Naumov, Jia Tao
Location: Montreal | Day: August 21st | Time: 10:00 | Session: KRR: Learning and reasoning
Show Abstract
The responsibility gap is a set of outcomes of a collective decision-making mechanism in which no single agent is individually responsible. In general, when designing a decision-making process, it is desirable to minimise the gap.

The paper studies the class of mechanisms for which the gap is empty and proposes a concept of an elected dictatorship. It shows that, in a perfect information setting, the gap is empty if and only if the mechanism is an elected dictatorship. It also proves that in an imperfect information setting, the class of gap-free mechanisms is positioned strictly between two variations of the class of elected dictatorships.
173: Enhancing Sampling Protocol for Point Cloud Classification Against Corruptions
Authors: Chongshou Li, Pin Tang, Tianrui Li, Yuheng Liu, Xinke Li
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: AI Ethics, Trust, Fairness (3/3)
Show Abstract
Established sampling protocols for 3D point cloud learning, such as Farthest Point Sampling (FPS) and Fixed Sample Size (FSS), have long been relied upon. However, real-world data often suffer from corruptions, such as sensor noise, which violates the benign data assumption in current protocols. As a result, these protocols are highly vulnerable to noise, posing significant safety risks in critical applications like autonomous driving. To address these issues, we propose an enhanced point cloud sampling protocol, PointSP, designed to improve robustness against point cloud corruptions. PointSP incorporates key point reweighting to mitigate outlier sensitivity and ensure the selection of representative points. It also introduces a local-global balanced downsampling strategy, which allows for scalable and adaptive sampling while maintaining geometric consistency. Additionally, a lightweight tangent plane interpolation method is used to preserve local geometry while enhancing the density of the point cloud. Unlike learning-based approaches that require additional model training, PointSP is architecture-agnostic, requiring no extra learning or modification to the network. This enables seamless integration into existing pipelines. Extensive experiments on synthetic and real-world corrupted datasets show that PointSP significantly improves the robustness and accuracy of point cloud classification, outperforming state-of-the-art methods across multiple benchmarks.
221: A Structural Complexity Analysis of Hierarchical Task Network Planning
Authors: Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems.
258: Deep Opinion-Unaware Blind Image Quality Assessment by Learning and Adapting from Multiple Annotators
Authors: Zhihua Wang, Xuelin Liu, Jiebin Yan, Jie Wen, Wei Wang, Chao Huang
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Computer Vision (3/3)
Show Abstract
Existing deep neural network (DNN)-based blind image quality assessment (BIQA) methods primarily rely on human-rated datasets for training. However, collecting human labels is extremely time-consuming and labor-intensive, posing a significant bottleneck for practical applications. To address this challenge, we propose a Deep opinion-Unaware BIQA model by learning and adapting from Multiple Annotators, termed DUBMA, thereby eliminating the need for human annotations. Specifically, we first generate a large-scale set of distorted image pairs and then assign relative quality rankings using existing full-reference IQA models. The resulting dataset is subsequently employed for training our DUBMA.
Due to the inherent discrepancies between synthetic and real-world distortions, a domain shift may occur. To address this, we propose an outlier-robust unsupervised domain adaptation approach leveraging optimal transport. This strategy effectively reduces the gap between synthetic and real-world distortion domains, thereby boosting the model’s adaptability and overall performance. Extensive experiments show that DUBMA outperforms existing opinion-unaware BIQA methods in terms of prediction accuracy across multiple datasets.
282: Poisoning-based Backdoor Attacks for Arbitrary Target Label with Positive Triggers
Authors: Binxiao Huang, Ngai Wong
Location: Montreal | Day: August 21st | Time: 10:00 | Session: CV: attacks
Show Abstract
Poisoning-based backdoor attacks expose vulnerabilities during the data preparation phase of deep neural network (DNN) training. The DNNs trained on the poisoned dataset will be embedded with a backdoor, making them behave well on clean data while outputting malicious predictions whenever a trigger is applied. To exploit the abundant information contained in the input-to-label mapping, our scheme utilizes the network trained from the clean dataset as a trigger generator to produce poisons that significantly raise the success rate of backdoor attacks versus conventional approaches. Specifically, we introduce a new categorization of triggers inspired by adversarial techniques and propose a multi-label and multi-payload Poisoning-based backdoor attack with Positive Triggers (PPT), which strategically manipulates inputs to align them closer to the target label in the feature space of benign classifiers. Once the classifier is trained on the poisoned dataset, we can generate an input-label-aware trigger to make the infected classifier predict any given input to any target label with a high possibility. Through extensive experiments under both dirty-label and clean-label settings, we demonstrate empirically that the proposed attack achieves a high attack success rate without sacrificing accuracy across various datasets, including SVHN, CIFAR10, GTSRB, and Tiny ImageNet. Additionally, the PPT attack can elude a variety of classical backdoor defenses, proving its effectiveness.
303: INT: Instance-Specific Negative Mining for Task-Generic Promptable Segmentation
Authors: Jian Hu, Zixu Cheng, Shaogang Gong
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Computer vision (2/3)
Show Abstract
Task-generic promptable image segmentation aims to achieve segmentation of diverse samples under a single task description by utilizing only one task-generic prompt. Current methods leverage the generalization capabilities of Vision-Language Models (VLMs) to infer instance-specific prompts from these task-generic prompts in order to guide the segmentation process. However, when VLMs struggle to generalise to some image instances, predicting instance-specific prompts becomes poor. To solve this problem, we introduce Instance-specific Negative Mining for Task-Generic Promptable Segmentation (INT). The key idea of INT is to adaptively reduce the influence of irrelevant (negative) prior knowledge whilst to increase the use the most plausible prior knowledge, selected by negative mining with higher contrast, in order to optimise instance-specific prompts generation. Specifically, INT consists of two components: (1) instance-specific prompt generation, which progressively fliters out incorrect information in prompt generation; (2) semantic mask generation, which ensures each image instance segmentation matches correctly the semantics of the instance-specific prompts. INT is validated on six datasets, including camouflaged objects and medical images, demonstrating its effectiveness, robustness and scalability.
332: A Primal-dual Perspective for Distributed TD-learning
Authors: Han Dong Lim, Donghwan Lee
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Reinforcement Learning (2/2)
Show Abstract
The goal of this paper is to investigate distributed temporal difference (TD) learning for a networked multi-agent Markov decision process. The proposed approach is based on distributed optimization algorithms, which can be interpreted as primal-dual ordinary differential equation (ODE) dynamics subject to null-space constraints. Based on the exponential convergence behavior of the primal-dual ODE dynamics subject to null-space constraints, we examine the behavior of the final iterate in various distributed TD-learning scenarios, considering both constant and diminishing step-sizes and incorporating both i.i.d. and Markovian observation models. Unlike existing methods, the proposed algorithm does not require the assumption that the underlying communication network structure is characterized by a doubly stochastic matrix.
384: Smart Contracts for Trustless Sampling of Correlated Equilibria
Authors: Togzhan Barakbayeva, Zhuo Cai, Amir Goharshady, Karaneh Keypoor
Location: Montreal | Day: August 21st | Time: 10:00 | Session: GTEP: Noncooperative games
Show Abstract
Correlated equilibria are a standard solution concept in game theory and generalize Nash equilibria. In a 2-player non-cooperative game in which player i has action set A_i, a correlated equilibrium is a self-enforcing probability distribution σ over A_1 * A_2. Specifically, when a strategy profile (s_1, s_2) in A_1 * A_2 is sampled according to σ, each player i can observe their own component s_i, but not the other player’s component. Knowing s_i and σ, player i cannot increase their expected payoff by defecting and playing a strategy s’_i different from s_i. Correlated equilibria are ubiquitous and crucial in mechanism design, including in the design of blockchain-based protocols which aim to incentivize honest behavior.

A correlated equilibrium depends on a centralized and impartial oracle, often called the ”external signal” in game theory literature, to sample a strategy profile and disclose each player’s component to them, while keeping the other player’s component secret. However, there is currently no trustless method to achieve this on the blockchain without centralization or relying on trusted third-parties.

In this work, we address this challenge and provide two novel protocols, one based on oblivious transfer and the other based on zkSNARKs to replace the public signal with a smart contract. We prove that our approaches are secure and provide the desired privacy properties of a correlated equilibrium, while also being efficient in terms of gas usage and thus affordable in practice.
474: Towards a Unified View of Social Laws with Instantaneous Actions
Authors: Alexander Tuisov, Evgeny Mishlyakov, Alexander Shleyfman, Erez Karpas
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Planning and Scheduling (4/5)
Show Abstract
Multiple agents operating in a shared environment can interfere with each other’s ability to reach their goals. One of the approaches to address this issue is enacting a social law – a set of rules that restricts some possible behaviors of the agents. A social law is considered robust if it guarantees that each agent can achieve its goal independently of the actions of other agents. Recent work has shown how to verify that a given social law, encoded in an MA-STRIPS formalism, is robust by compilation to classical planning. Follow-up work presented an extended compilation which can handle numeric multi-agent planning. In this paper, we present a new compilation, which can handle both classical and numeric multi-agent planning formalisms, as well as any other multi-agent planning formalism with instantaneous actions, in which action preconditions can be negated using first-order logic with equality. This opens the door to using social laws in even richer planning formalisms. Our empirical evaluation shows that the added expressivity of the new compilation does not hurt its performance, and it achieves comparable performance to the previous state-of-the-art compilations.
475: L2M2: A Hierarchical Framework Integrating Large Language Model and Multi-agent Reinforcement Learning
Authors: Minghong Geng, Shubham Pateria, Budhitama Subagdja, Lin Li, Xin Zhao, Ah-Hwee Tan
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Agent-based and Multi-agent Systems (2/3)
Show Abstract
Multi-agent reinforcement learning (MARL) has demonstrated remarkable success in collaborative tasks, yet faces significant challenges in scaling to complex scenarios requiring sustained planning and coordination across long horizons. While hierarchical approaches help decompose these tasks, they typically rely on hand-crafted subtasks and domain-specific knowledge, limiting their generalizability. We present L2M2, a novel hierarchical framework that leverages large language models (LLMs) for high-level strategic planning and MARL for low-level execution. L2M2 enables zero-shot planning that supports both end-to-end training and direct integration with pre-trained MARL models. Experiments in the VMAS environment demonstrate that L2M2’s LLM-guided MARL achieves superior performance while requiring less than 20% of the training samples compared to baseline methods. In the MOSMAC environment, L2M2 demonstrates strong performance with pre-defined subgoals and maintains substantial effectiveness without subgoals – scenarios where baseline methods consistently fail. Analysis through kernel density estimation reveals L2M2’s ability to automatically generate appropriate navigation plans, demonstrating its potential for addressing complex multi-agent coordination tasks.
482: SetKE: Knowledge Editing for Knowledge Elements Overlap
Authors: Yifan Wei, Xiaoyan Yu, Ran Song, Hao Peng, Angsheng Li
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Natural Language Processing (2/2)
Show Abstract
Large Language Models (LLMs) excel in tasks such as retrieval and question answering but require updates to incorporate new knowledge and reduce inaccuracies and hallucinations.
Traditional updating methods, like fine-tuning and incremental learning, face challenges such as overfitting and high computational costs.
Knowledge Editing (KE) provides a promising alternative but often overlooks the Knowledge Element Overlap (KEO) phenomenon, where multiple triplets share common elements, leading to editing conflicts.
We identify the prevalence of KEO in existing KE datasets and show its significant impact on current KE methods, causing performance degradation in handling such triplets.
To address this, we propose a new formulation, Knowledge Set Editing (KSE), and introduce SetKE, a method that edits sets of triplets simultaneously.
Experimental results demonstrate that SetKE outperforms existing methods in KEO scenarios on mainstream LLMs. Additionally, we introduce EditSet, a dataset containing KEO triplets, providing a comprehensive benchmark.
487: Asymptotic Fair Division: Chores Are Easier Than Goods
Authors: Pasin Manurangsi, Warut Suksompong
Location: Montreal | Day: August 21st | Time: 11:30 | Session: GTEP: Fair division
Show Abstract
When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where m chores are allocated to n agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that m >= 2n, and moreover, m must be at least n+Theta(n) in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as m = omega(1), and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.
493: Not in My Backyard! Temporal Voting Over Public Chores
Authors: Edith Elkind, Tzeh Yuan Neoh, Nicholas Teh
Location: Montreal | Day: August 19th | Time: 11:30 | Session: GTEP: Computational social choice (1/2)
Show Abstract
We study a temporal voting model where voters have dynamic preferences over a set of public chores—projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.
497: Probabilistic Analysis of Stable Matching in Large Markets with Siblings
Authors: Zhaohong Sun, Tomohiko Yokoyama, Makoto Yokoo
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Game Theory and Economic Paradigms
Show Abstract
We study a practical centralized matching problem which assigns children to daycare centers.
The collective preferences of siblings from the same family introduce complementarities, which can lead to the absence of stable matchings, as observed in the hospital-doctor matching problems involving couples. Intriguingly, stable matchings are consistently observed in real-world daycare markets, despite the prevalence of sibling applicants.

We conduct a probabilistic analysis of large random markets to examine the existence of stable matchings in such markets. Specifically, we focus on scenarios where daycare centers have similar priorities over children, a common characteristic in real-world markets. Our analysis reveals that as the market size approaches infinity, the likelihood of stable matchings existing converges to 1.

To facilitate our exploration, we refine an existing heuristic algorithm to address a more rigorous stability concept, as the original one may fail to meet this criterion. Through extensive experiments on both real-world and synthetic datasets, we demonstrate the effectiveness of our revised algorithm in identifying stable matchings, particularly when daycare priorities exhibit high similarity.
517: ExpertDiff: Head-less Model Reprogramming with Diffusion Classifiers for Out-of-Distribution Generalization
Authors: Jee Seok Yoon, Junghyo Sohn, Wootaek Jeong, Heung-Il Suk
Location: Montreal | Day: August 19th | Time: 11:30 | Session: ML: Difussion Models
Show Abstract
Vision-language models have achieved remarkable performance across various tasks by leveraging large-scale multimodal training data. However, their ability to generalize to out-of-distribution (OOD) domains requiring expert-level knowledge remains an open challenge. To address this, we investigate cross-domain transfer learning approaches for efficiently adapting diffusion classifiers to new target domains demanding expert-level domain knowledge. Specifically, we propose ExpertDiff, a head-less model reprogramming technique that optimizes the instruction-following abilities of text-to-image diffusion models via learnable prompts, while leveraging the diffusion classifier objective as a modular plug-and-play adaptor. Our approach eliminates the need for conventional output mapping layers (e.g., linear probes), enabling seamless integration with off-the-shelf diffusion frameworks like Stable Diffusion. We demonstrate the effectiveness of ExpertDiff on the various OOD datasets (i.e., medical and satellite imagery). Furthermore, we qualitatively showcase ExpertDiff’s ability to faithfully reconstruct input images, highlighting its potential for both downstream discriminative and upstream generative tasks. Our work paves the way for effectively repurposing powerful foundation models for novel OOD applications requiring domain expertise.
547: Joint-Perturbation Simultaneous Pseudo-Gradient
Authors: Carlos Martin, Tuomas Sandholm
Location: Montreal | Day: August 21st | Time: 10:00 | Session: GTEP: Noncooperative games
Show Abstract
We study the problem of computing an approximate Nash equilibrium of a game whose strategy space is continuous without access to gradients of the utility function.
Lack of access to gradients is common in reinforcement learning settings, where the environment is treated as a black box, as well as equilibrium finding in mechanisms such as auctions, where the mechanism’s payoffs are discontinuous in the players’ actions.
To tackle this problem, we turn to zeroth-order optimization techniques that combine pseudo-gradients with equilibrium-finding dynamics.
Specifically, we introduce a new technique that requires a number of utility function evaluations per iteration that is constant rather than linear in the number of players.
It achieves this by performing a single joint perturbation on all players’ strategies, rather than perturbing each one individually.
This is very important for many-player games, especially when the utility function is expensive to compute in terms of wall time, memory, money, or other resources.
We evaluate our approach on various games, including auctions, which have important real-world applications.
Our approach yields a dramatic improvement in performance in terms of the wall time required to reach an approximate Nash equilibrium.
567: Integrating Independent Layer-Wise Rank Selection with Low-Rank SVD Training for Model Compression: A Theory-Driven Approach
Authors: Yifan Guo, Alyssa Yu
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
In recent years, with the rise of large language models, model sizes have grown dramatically, garnering attention for their remarkable performance but also raising concerns about the substantial computational and communication resources they require. This has created significant challenges in fine-tuning or re-training models on devices with limited computing and memory resources. Efficient model compression through low-rank factorization has emerged as a promising solution, offering a way to balance the tradeoff between compression ratio and prediction accuracy. However, existing approaches to low-rank selection often rely on trial-and-error methods to determine the optimal rank, lacking theoretical guidance and incurring high computational costs. Furthermore, these methods typically treat low-rank factorization as a post-training process, resulting in suboptimal compressed models. In this paper, we design a novel approach by integrating rank selection into the low-rank training process and performing independent layer-wise rank selection under the guidance of a theoretical loss error bound. Specifically, we first conduct a comprehensive theoretical analysis to quantify how low-rank approximations impact the training losses. Building on these insights, we develop an efficient layer-wise rank search algorithm and seamlessly incorporate it into low-rank singular value decomposition (SVD) training. Our evaluation results on benchmark datasets demonstrate that our approach can achieve high prediction accuracy while delivering significant compression performance. Furthermore, our solution is generic and can be extended to broader learning models.
598: FissionVAE: Federated Non-IID Image Generation with Latent Space and Decoder Decomposition
Authors: Chen Hu, Hanchi Ren, Jingjing Deng, Xianghua Xie, Xiaoke Ma
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Federated Learning
Show Abstract
Federated learning is a machine learning paradigm that enables decentralized clients to collaboratively learn a shared model while keeping all the training data local. While considerable research has focused on federated image generation, particularly Generative Adversarial Networks, Variational Autoencoders have received less attention. In this paper, we address the challenges of non-IID (independently and identically distributed) data environments featuring multiple groups of images of different types. Non-IID data distributions can lead to difficulties in maintaining a consistent latent space and can also result in local generators with disparate texture features being blended during aggregation. We thereby introduce FissionVAE that decouples the latent space and constructs decoder branches tailored to individual client groups. This method allows for customized learning that aligns with the unique data distributions of each group. Additionally, we incorporate hierarchical VAEs and demonstrate the use of heterogeneous decoder architectures within FissionVAE. We also explore strategies for setting the latent prior distributions to enhance the decoupling process. To evaluate our approach, we assemble two composite datasets: the first combines MNIST and FashionMNIST; the second comprises RGB datasets of cartoon and human faces, wild animals, marine vessels, and remote sensing images. Our experiments demonstrate that FissionVAE greatly improves generation quality on these datasets compared to baseline federated VAE models.
611: Data Poisoning Attack Defense and Evolutionary Domain Adaptation for Federated Medical Image Segmentation
Authors: Min Hyuk Kim, Seok Bong Yoo
Location: Montreal | Day: August 21st | Time: 10:00 | Session: CV: attacks
Show Abstract
Federated learning has significant demonstrated potential in medical image segmentation to protect data privacy by retaining local data. However, its application is still hindered by two critical challenges: 1) the retained data poisoning attacks that severely compromise the accuracy of the global segmentation model and 2) domain gaps among clients, undermining its generalizability. To address these issues, we propose AdaShield-FL, a data poisoning attack defense and evolutionary domain adaptation for federated medical image segmentation. AdaShield-FL incorporates a disentangled reconstruction and segmentation module that purifies data in the k-space domain to mitigate the effects of adversarial attacks iteratively. Moreover, it introduces a data poisoning attack detection mechanism that analyzes abnormal patterns in training loss sequences to identify malicious clients. This method also aligns local and global covariance matrices via evolutionary optimization to minimize the domain gap efficiently. The experimental validation on cardiac magnetic resonance imaging datasets demonstrates the robustness and superior performance of AdaShield-FL compared with other federated learning methods.
674: Noise Optimized Conditional Diffusion for Domain Adaptation
Authors: Lingkun Luo, Shiqiang Hu, Liming Chen
Location: Montreal | Day: August 19th | Time: 15:00 | Session: CV: Difusion models
Show Abstract
Pseudo-labeling is a cornerstone of Unsupervised Domain Adaptation (UDA), yet the scarcity of High-Confidence Pseudo-Labeled Target Domain Samples (hcpl-tds) often leads to inaccurate cross-domain statistical alignment, causing DA failures. To address this challenge, we propose Noise Optimized Conditional Diffusion for Domain Adaptation (NOCDDA), which seamlessly integrates the generative capabilities of conditional diffusion models with the decision-making requirements of DA to achieve task-coupled optimization for efficient adaptation. For robust cross-domain consistency, we modify the DA classifier to align with the conditional diffusion classifier within a unified optimization framework, enabling forward training on noise-varying cross-domain samples. Furthermore, we argue that the conventional N(0,I) initialization in diffusion models often generates class-confused hcpl-tds, compromising discriminative DA. To resolve this, we introduce a class-aware noise optimization strategy that refines sampling regions for reverse class-specific hcpl-tds generation, effectively enhancing cross-domain alignment. Extensive experiments across 5 benchmark datasets and 29 DA tasks demonstrate significant performance gains of NOCDDA over 31 state-of-the-art methods, validating its robustness and effectiveness.
686: Efficient Visual Representation Learning with Heat Conduction Equation
Authors: Zhemin Zhang, Xun Gong
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Computer Vision (1/3)
Show Abstract
Foundation models, such as CNNs and ViTs, have powered the development of image representation learning. However, general guidance to model architecture design is still missing. Inspired by the connection between image representation learning and heat conduction, we model images by the heat conduction equation, where the essential idea is to conceptualize image features as temperatures and model their information interaction as the diffusion of thermal energy. Based on this idea, we find that many modern model architectures, such as residual structures, SE block, and feed-forward networks, can be interpreted from the perspective of the heat conduction equation. Therefore, we leverage the heat equation to design new and more interpretable models. As an example, we propose the Heat Conduction Layer and the Refinement Approximation Layer inspired by solving the heat conduction equation using Finite Difference Method and Fourier series, respectively. The main goal of this paper is to integrate the overall architectural design of neural networks into the theoretical framework of heat conduction. Nevertheless, our Heat Conduction Network (HcNet) still shows competitive performance, e.g., HcNet-T achieves 83.0% top-1 accuracy on ImageNet-1K while only requiring 28M parameters and 4.1G MACs. The code is publicly available at: https://github.com/ZheminZhang1/HcNet.
705: MonoMixer: Marrying Convolution and Vision Transformer for Efficient Self-Supervised Monocular Depth Estimation
Authors: Zhiyong Chang, Yan Wang
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Computer vision (2/3)
Show Abstract
Self-supervised monocular depth estimation that does not require hard-to-source depth labels for training has been widely studied in recent years. Due to its significant and growing needs, many lightweight but effective architectures have been designed for edge devices. Convolutional Neural Networks (CNNs) have shown its extraordinary ability in monocular depth estimation. However, their limited receptive field stints existing methods to reason only locally, inhibiting the effectiveness of the self-supervised paradigm. Recently, Transformers has achieved great success in estimating depth maps from monocular images. Nevertheless, massive parameters in the Transformers hinder the deployment to edge devices. In this paper, we propose MonoMixer, a brand-new lightweight CNN-Transformer architecture with three main contributions: 1) The details-augmented (DA) block employs graph reasoning unit to capture abundant local details, resulting depth prediction at a higher level of precision. 2) The self-modulate channel attention (SMCA) block adaptively adjust the channel weights of feature maps, aiming to emphasize the crucial features and aggregate channel-wise feature maps of different patterns. 3) The global-guided Transformer (G2T) block integrates global semantic token into multi-scale local features and exploit cross-attention to encode long range dependencies. Furthermore, experimental results demonstrate the superiority of our proposed MonoMixer both at model size and inference speed, and achieve state-of-the-art performance on three datasets: KITTI, Make3D and Cityscapes. Specifically, our proposed MonoMixer outperforms
MonoFormer by a large margin in accuracy, with about 95 % fewer parameters.
720: The Proportional Veto Principle for Approval Ballots
Authors: Daniel Halpern, Ariel D. Procaccia, Warut Suksompong
Location: Montreal | Day: August 19th | Time: 11:30 | Session: GTEP: Computational social choice (1/2)
Show Abstract
The proportional veto principle, which captures the idea that a candidate vetoed by a large group of voters should not be chosen, has been studied for ranked ballots in single-winner voting. We introduce a version of this principle for approval ballots, which we call flexible-voter representation (FVR). We show that while the approval voting rule and other natural scoring rules provide the optimal FVR guarantee only for some flexibility threshold, there exists a scoring rule that is FVR-optimal for all thresholds simultaneously. We also extend our results to multi-winner voting.
722: Towards Robust Deterministic and Probabilistic Modeling for Predictive Learning
Authors: Xuesong Nie, Haoyuan Jin, Vijayakumar Bhagavatula, Xiaofeng Liu
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Computer Vision (1/3)
Show Abstract
Predictive modeling of unannotated spatiotemporal data presents inherent challenges, primarily due to the highly entangled visual dynamics in real-world scenes. To tackle these complexities, we introduce a novel insight through Disentangling Deterministic and Probabilistic (DDP) modeling. We note a key observation in spatiotemporal data where low-level details typically remain stable, whereas high-level motion frequently exhibits dynamic variations. The core motivation involves constructing two distinct pathways in the latent space: a deterministic path and a probabilistic path. The probabilistic path begins by defining the motion flow, which explicitly describes complex many-to-many motion patterns between patches, and models its probabilistic distribution using a motion diffuser. The deterministic path incorporates a spectral-aware enhancer to retain and amplify visual details in the frequency domain. These designs ensure visual consistency while also capturing intricate long-term motion dynamics. Extensive experiments demonstrate the superiority of DDP across diverse scenario evaluations.
750: scSiameseClu: A Siamese Clustering Framework for Interpreting Single-cell RNA Sequencing Data
Authors: Ping Xu, Zhiyuan Ning, Pengjiang Li, Wenhao Liu, Pengyang Wang, Jiaxu Cui, Yuanchun Zhou, Pengfei Wang
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
Single-cell RNA sequencing (scRNA-seq) reveals cell heterogeneity, with cell clustering playing a key role in identifying cell types and marker genes. Recent advances, especially graph neural networks (GNNs)-based methods, have significantly improved clustering performance. However, the analysis of scRNA-seq data remains challenging due to noise, sparsity, and high dimensionality. Compounding these challenges, GNNs often suffer from over-smoothing, limiting their ability to capture complex biological information. In response, we propose scSiameseClu, a novel Siamese Clustering framework for interpreting single-cell RNA-seq data, comprising of 3 key steps: (1) Dual Augmentation Module, which applies biologically informed perturbations to the gene expression matrix and cell graph relationships to enhance representation robustness; (2) Siamese Fusion Module, which combines cross-correlation refinement and adaptive information fusion to capture complex cellular relationships while mitigating over-smoothing; and (3) Optimal Transport Clustering, which utilizes Sinkhorn distance to efficiently align cluster assignments with predefined proportions while maintaining balance. Comprehensive evaluations on seven real-world datasets demonstrate that scSiameseClu outperforms state-of-the-art methods in single-cell clustering, cell type annotation, and cell type classification, providing a powerful tool for scRNA-seq data interpretation.
787: Tackling Long-Tailed Data Challenges in Spiking Neural Networks via Heterogeneous Knowledge Distillation
Authors: Moqi Li, Xu Yang, Cheng Deng
Location: Montreal | Day: August 20th | Time: 10:00 | Session: ML: Spiking Neural Networks
Show Abstract
Spiking Neural Networks (SNNs), inspired by the behavior of biological neurons, have gained significant research interest for resource-constrained edge devices and neuromorphic hardware due to their use of binary spike signals for inter-unit communication with low power consumption. However, the absence of research on spiking neural networks on long-tailed data has severely limited the deployment and application of this emerging network in practical scenarios. To fill this gap, this paper proposes a long-tail learning framework based on spiking neural networks, named LT-SpikingFormer, to alleviate the distribution bias between head and tail classes. LT-SpikingFormer adopts a widely trained Convolutional Neural Network to construct a heterogeneous knowledge distillation paradigm, offering balanced and reliable prior knowledge. Moreover, a multi-granularity hierarchical feature distillation objective is proposed to leverage cross-layer local features and network global predictions to facilitate refined information distillation to optimize the network, specifically for the performance of the tailed classes. Extensive experimental results demonstrate that our method performs well on several benchmark datasets.
899: Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals
Authors: Isaac Stone, Nathan R. Sturtevant, Jonathan Schaeffer
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Search
Show Abstract
Among the most popular games played worldwide, Bridge stands out for having had little AI progress for over 25 years. Ginsberg’s Partition Search algorithm (1996) was a breakthrough for double-dummy Bridge play, allowing a program to reason about sets of states rather than individual states. Partition Search supports the current state of the art for both bidding and cardplay. In the time since, virtually no progress has been made in Bridge bidding. Inspired by Ginsberg’s idea, this paper presents Setrograde Analysis, a new set-based algorithm for perfectly solving Bridge hands. Using this approach, we have solved all 7-trick (28-card) hands — 10^30 states, which can be reduced to 10^17 unique states using preexisting techniques. This was done by considering five orders of magnitude fewer sets than the traditional state-based Retrograde Analysis algorithm. This work suggests that the entire 13-trick (52-card) state space can be solved with modern technology using this new approach.
The 7-trick computation represents the largest endgame database to date in any game.
900: Exploring the Trade-Offs: Quantization Methods, Task Difficulty, and Model Size in Large Language Models From Edge to Giant
Authors: Jemin Lee, Sihyeong Park, Jinse Kwon, Jihun Oh, Yongin Kwon
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Natural Language Processing (1/2)
Show Abstract
Quantization has gained attention as a promising solution for the cost-effective deployment of large and small language models. However, most prior work has been limited to perplexity or basic knowledge tasks and lacks a comprehensive evaluation of recent models like Llama-3.3.
In this paper, we conduct a comprehensive evaluation of instruction-tuned models spanning 1B to 405B parameters, applying four quantization methods across 13 datasets.
Our findings reveal that (1) quantized models generally surpass smaller FP16 baselines, yet they often struggle with instruction-following and hallucination detection; (2) FP8 consistently emerges as the most robust option across tasks, and AWQ tends to outperform GPTQ in weight-only quantization;
(3) smaller models can suffer severe accuracy drops at 4-bit quantization, while 70B-scale models maintain stable performance;
(4) notably, \textit{hard} tasks do not always experience the largest accuracy losses, indicating that quantization magnifies a model’s inherent weaknesses rather than simply correlating with task difficulty; and (5) an LLM-based judge (MT-Bench) highlights significant performance declines in Coding and STEM tasks, though it occasionally reports improvements in reasoning.
914: Vi3D-LLaMA: Observe and Understand the 3D Scene with A Video Sequence
Authors: Yingjie Wang, Jiajun Deng, Yao Li, Houqiang Li, Yanyong Zhang
Location: Montreal | Day: August 21st | Time: 15:00 | Session: CV: videos
Show Abstract
Current 3D Multimodal Large Language Models (3D MLLMs) leverage explicit 3D input, e.g., point clouds, to understand the 3D world and enable spatial reasoning. These explicit 3D data are usually obtained through reconstruction or additional depth sensors, affecting the model’s scalability and deployment. In this work, we take a different stance and introduce Vi3D-LLaMA, a powerful MLLM operating without point cloud or depth data. Instead, we explore how to capture and interpret 3D scenes directly from RGB video sequences. The core idea of this work is to empower the video MLLM with the capability of understanding the 3D world from two aspects: (1) 3D-Aware Geometric Encoding: Camera parameters and a frustum-based 3D position encoder are used to transform video representations into 3D-aware tokens, enabling implicit modeling of 3D structures with RGB frames. (2) Fine-Grained Semantic Enhancement: High-resolution (HR) images are progressively incorporated into the video representation through a lightweight HR adapter, facilitating video tokens with semantic details. We conduct extensive experiments and demonstrate that Vi3D-LLaMA, using only RGB data, can achieve comparable results with state-of-the-art 3D MLLMs. Additionally, we benchmark our method on the new VSI-Bench, showing consistent improvement over the video MLLM baseline.
948: Verified Certificates via SAT and Computer Algebra Systems for the Ramsey R(3,8) and R(3,9) Problems
Authors: Zhengyu Li, Conor Duggan, Curtis Bright, Vijay Ganesh
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Constraint Satisfaction and Optimization (2/3)
Show Abstract
The Ramsey problem R(3,k) seeks to determine the smallest value of n such that any red/blue edge coloring of the complete graph on n vertices must either contain a blue triangle (3-clique) or a red clique of size k. Despite its significance, many previous computational results for the Ramsey R(3,k) problem such as R(3,8) and R(3,9) lack formal verification. To address this issue, we use the software MathCheck to generate certificates for Ramsey problems R(3,8) and R(3,9) (and symmetrically R(8,3) and R(9,3)) by integrating a Boolean satisfiability (SAT) solver with a computer algebra system (CAS). Our SAT+CAS approach significantly outperforms traditional SAT-only methods, demonstrating an improvement of several orders of magnitude in runtime. For instance, our SAT+CAS approach solves R(3,8) (resp., R(8,3)) sequentially in 59 hours (resp., in 11 hours), while a SAT-only approach using state-of-the-art CaDiCaL solver times out after 7 days. Additionally, in order to be able to scale to harder Ramsey problems R(3,9) and R(9,3) we further optimized our SAT+CAS tool using a parallelized cube-and-conquer approach. Our results provide the first independently verifiable certificates for these Ramsey numbers, ensuring both correctness and completeness of the exhaustive search process of our SAT+CAS tool.
1048: 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ć
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Uncertainty in AI
Show 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.
1151: Exploring the Frontiers of Animation Video Generation in the Sora Era: Method, Dataset and Benchmark
Authors: Yudong Jiang, Baohan Xu, Siqian Yang, Mingyu Ying, Jing Liu, Chao Xu, Siqi Wang, Yidi Wu, Bingwen Zhu, Yue Zhang, Jinlong Hou, Huyang Sun
Location: Montreal | Day: August 21st | Time: 11:30 | Session: CV: Benchmarks
Show Abstract
Animation has gained significant interest in the recent film and TV industry. Despite the success of advanced video generation models like Sora, Kling, and CogVideoX in generating natural videos, they lack the same effectiveness in handling animation videos. Evaluating animation video generation is also a great challenge due to its unique artist styles, violating the laws of physics and exaggerated motions. In this paper, we present a comprehensive system, AniSora, designed for animation video generation, which includes a data processing pipeline, a controllable generation model, and an evaluation benchmark. Supported by the data processing pipeline with over 10M high-quality data, the generation model incorporates a spatiotemporal mask module to facilitate key animation production functions such as image-to-video generation, frame interpolation, and localized image-guided animation. We also collect an evaluation benchmark of 948 various animation videos, with specifically developed metrics for animation video generation. Our entire project is publicly available on https://github.com/bilibili/Index-anisora/tree/main
1273: Differentiable Prompt Learning for Vision Language Models
Authors: Zhenhan Huang, Tejaswini Pedapati, Pin-Yu Chen, Jianxi Gao
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Large Language Models
Show Abstract
Prompt learning is an effective way to exploit the potential of large-scale pre-trained foundational models. Continuous prompts parameterize context tokens in prompts by turning them into differentiable vectors. Deep continuous prompts insert prompts not only in the input but also in the intermediate hidden representations. Manually designed deep continuous prompts exhibit a remarkable improvement compared to the zero-shot pre-trained model on downstream tasks. How to automate the continuous prompt design is an underexplored area, and a fundamental question arises, is manually designed deep prompt strategy optimal? To answer this question, we propose a method dubbed differentiable prompt learning (DPL). The DPL method is formulated as an optimization problem to automatically determine the optimal context length of the prompt to be added to each layer, where the objective is to maximize the performance. We test the DPL method on the pre-trained CLIP. We empirically find that by using only limited data, our DPL method can find deep continuous prompt configuration with high confidence. The performance on the downstream tasks exhibits the superiority of the automatic design: our method boosts the average test accuracy by 2.60% on 11 datasets compared to baseline methods. Besides, our method focuses only on the prompt configuration (i.e. context length for each layer), which means that our method is compatible with the baseline methods that have sophisticated designs to boost the performance. We release our code in https://github.com/Zhenhan-Huang/Differentiable-Prompt-Learn.
1288: CompLex: Music Theory Lexicon Constructed by Autonomous Agents for Automatic Music Generation
Authors: Zhejing Hu, Yan Liu, Gong Chen, Bruce X. B. Yu
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Multidisciplinary Topics and Applications (2/2)
Show Abstract
Generative artificial intelligence in music has made significant strides, yet it still falls short of the substantial achievements seen in natural language processing, primarily due to the limited availability of music data. Knowledge-informed approaches have been shown to enhance the performance of music generation models, even when only a few pieces of musical knowledge are integrated. This paper seeks to leverage comprehensive music theory in AI-driven music generation tasks, such as algorithmic composition and style transfer, which traditionally require significant manual effort with existing techniques. We introduce a novel automatic music lexicon construction model that generates a lexicon, named CompLex, comprising 37,432 items derived from just 9 manually input category keywords and 5 sentence prompt templates. A new multi-agent algorithm is proposed to automatically detect and mitigate hallucinations. CompLex demonstrates impressive performance improvements across three state-of-the-art text-to-music generation models, encompassing both symbolic and audio-based methods. Furthermore, we evaluate CompLex in terms of completeness, accuracy, non-redundancy, and executability, confirming that it possesses the key characteristics of an effective lexicon.
1303: Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation
Authors: Yifan Zhang, Pascal Bercher
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Planning and Scheduling (2/5)
Show Abstract
This paper investigates fundamental aspects of Hierarchical Task Network (HTN) planning by systematically exploring recursive arrangements of primitive task networks. Working within a general framework that aligns with recently identified ACKERMANN-complete HTN problems, we map the computational complexity across various recursive configurations, revealing a rich complexity landscape. Through a novel proof technique that we call selective action nullification with state preservation, we demonstrate that even a highly restricted class of regular HTN problems remains PSPACE-complete, establishing a profound connection to classical planning. We hope these findings contribute to a deeper and broader understanding of the theoretical foundations of HTN planning.
1333: Initial Models and Serialisability in Abstract Dialectical Frameworks
Authors: Lars Bengel, Matthias Thimm
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
We introduce initial models for abstract dialectical frameworks (ADFs) as a notion of minimal justifiable valuations and based on that, generalise the concept of serialisability of argumentation semantics to ADFs. In particular, we show that the characteristic operator-based semantics for ADFs can be characterised through serialisation sequences, which are, essentially, decompositions of a model into a series of initial models, representing a more fine-grained view into why a model is acceptable wrt. the semantics. We also analyse the computational complexity of tasks related to initial models.
1350: Airdrop Games
Authors: Sotiris Georganas, Aggelos Kiayias, Paolo Penna
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Game Theory
Show Abstract
Launching a new blockchain system or application is frequently facilitated by a so called airdrop, where the system designer chooses a pre-existing set of potentially interested parties and allocates newly minted tokens to them with the expectation that they will participate in the system — such engagement, especially if it is of significant level — facilitates the system and raises its value and also the value of its newly minted token, hence benefiting the airdrop recipients. A number of challenging questions befuddle designers in this setting, such as how to choose the set of interested parties and how to allocate tokens to them. To address these considerations we put forward a game theoretic model for such airdrop games. Our model can be used to guide the designer’s choices based on the way the system’s value depends on participation (modeled by a “technology function” in our framework) and the costs that participations incurs. We identify both bad and good equilibria and identify the settings and the choices that can be made where the designer can influence the players towards good equilibria in an expedient manner.
1372: Approximate Lifted Model Construction
Authors: Malte Luttermann, Jan Speller, Marcel Gehrke, Tanya Braun, Ralf Möller, Mattis Hartwig
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Uncertainty in AI
Show 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.
1379: The Role of Video Generation in Enhancing Data-Limited Action Understanding
Authors: Wei Li, Dezhao Luo, Dongbao Yang, Zhenhang Li, Weiping Wang, Yu Zhou
Location: Montreal | Day: August 21st | Time: 15:00 | Session: CV: videos
Show Abstract
Video action understanding tasks in real-world scenarios often suffer from data limitations. In this paper, we address the data-limited action understanding problem by bridging data scarcity. We propose a novel method that leverages a text-to-video diffusion transformer to generate annotated data for model training. This paradigm enables the generation of realistic annotated data on an infinite scale without human intervention. We proposed the Information Enhancement Strategy and the Uncertainty-Based Soft Target tailored to generate sample training. Through quantitative and qualitative analyzes, we discovered that real samples generally contain a richer level of information compared to generated samples. Based on this observation, the information enhancement strategy was designed to enhance the informational content of the generated samples from two perspectives: the environment and the character. Furthermore, we observed that a portion of low-quality generated samples might negatively affect model training. To address this, we devised an uncertainty-based label-smoothing strategy to increase the smoothing of these low-quality samples, thereby reducing their impact. We demonstrate the effectiveness of the proposed method on four datasets and five tasks, and achieve state-of-the-art performance for zero-shot action recognition.
1383: GRAML: Goal Recognition As Metric Learning
Authors: Matan Shamir, Reuth Mirsky
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Planning and Scheduling (3/5)
Show Abstract
Goal Recognition (GR) is the problem of recognizing an agent’s objectives based on observed actions.
Recent data-driven approaches for GR alleviate the need for costly, manually crafted domain models.
However, these approaches can only reason about a pre-defined set of goals, and time-consuming training is needed for new emerging goals.
To keep this model-learning automated while enabling quick adaptation to new goals, this paper introduces GRAML: Goal Recognition As Metric Learning.
GRAML frames GR as a deep metric learning problem, using a Siamese network composed of recurrent units to learn an embedding space where traces leading to the same goal are close, and those leading to different goals are distant.
This metric is particularly effective for adapting to new goals, even when only a single example trace is available per goal.
Evaluated on a versatile set of environments, GRAML shows speed, flexibility, and runtime improvements over the state-of-the-art GR while maintaining accurate recognition.
1453: Explaining Black-box Model Predictions via Two-level Nested Feature Attributions with Consistency Property
Authors: Yuya Yoshikawa, Masanari Kimura, Ryotaro Shimizu, Yuki Saito
Location: Montreal | Day: August 21st | Time: 10:00 | Session: ML: Explainable/Interpretable machine learning
Show Abstract
Techniques that explain the predictions of black-box machine learning models are crucial to make the models transparent, thereby increasing trust in AI systems.
The input features to the models often have a nested structure that consists of high- and low-level features, and each high-level feature is decomposed into multiple low-level features.
For such inputs, both high-level feature attributions (HiFAs) and low-level feature attributions (LoFAs) are important for better understanding the model’s decision.
In this paper, we propose a model-agnostic local explanation method that effectively exploits the nested structure of the input to estimate the two-level feature attributions simultaneously.
A key idea of the proposed method is to introduce the consistency property that should exist between the HiFAs and LoFAs, thereby bridging the separate optimization problems for estimating them.
Thanks to this consistency property, the proposed method can produce HiFAs and LoFAs that are both faithful to the black-box models and consistent with each other, using a smaller number of queries to the models.
In experiments on image classification in multiple instance learning and text classification using language models, we demonstrate that the HiFAs and LoFAs estimated by the proposed method are accurate, faithful to the behaviors of the black-box models, and provide consistent explanations.
1523: The Devil is in Fine-tuning and Long-tailed Problems: A New Benchmark for Scene Text Detection
Authors: Tianjiao Cao, Jiahao Lyu, Weichao Zeng, Weimin Mu, Yu Zhou
Location: Montreal | Day: August 21st | Time: 11:30 | Session: CV: Benchmarks
Show Abstract
Scene text detection has seen the emergence of high-performing methods that excel on academic benchmarks. However, these detectors often fail to replicate such success in real-world scenarios. We uncover two key factors contributing to this discrepancy through extensive experiments. First, a Fine-tuning Gap, where models leverage Dataset-Specific Optimization (DSO) paradigm for one domain at the cost of reduced effectiveness in others, leads to inflated performances on academic benchmarks. Second, the suboptimal performance in practical settings is primarily attributed to the longtailed distribution of texts, where detectors struggle with rare and complex categories as artistic or overlapped text. Given that the DSO paradigm might undermine the generalization ability of models, we advocate for a Joint-Dataset Learning (JDL) protocol to alleviate the Fine-tuning Gap. Additionally, an error analysis is conducted to identify three major categories and 13 subcategories of challenges in long-tailed scene text, upon which we propose a Long-Tailed Benchmark (LTB). LTB facilitates a comprehensive evaluation of ability to handle a diverse range of long-tailed challenges. We further introduce MAEDet, a self-supervised learningbased method, as a strong baseline for LTB. The code is available at https://github.com/pd162/LTB.
1555: BankTweak: Adversarial Attack Against Multi-Object Trackers by Manipulating Feature Banks
Authors: Woojin Shin, Donghwa Kang, Daejin Choi, Brent Byunghoon Kang, Jinkyu Lee, Hyeongboo Baek
Location: Montreal | Day: August 21st | Time: 10:00 | Session: CV: attacks
Show Abstract
Modern multi-object tracking (MOT) predominantly relies on the tracking-by-detection paradigm to construct object trajectories. Traditional MOT attacks primarily degrade detection quality in specific frames only, lacking efficiency, while state-of-the-art (SOTA) approaches induce persistent identity (ID) switches by manipulating object positions during the association phase, even after the attack ends. In this paper, we reveal that these SOTA attacks can be easily counteracted by adjusting distance-related parameters in the association phase, exposing their lack of robustness. To overcome these limitations, we propose BankTweak, a novel adversarial attack targeting feature-based MOT systems to induce persistent ID switches (efficiency) without modifying object positions (robustness). BankTweak exploits a critical vulnerability in the Hungarian matching algorithm of MOT systems by strategically injecting altered features into feature banks during the association phase. Extensive experiments on MOT17 and MOT20 datasets, combining various detectors, feature extractors, and trackers, demonstrate that BankTweak significantly outperforms SOTA attacks up to 11.8 times, exposing fundamental vulnerabilities in the tracking-by-detection framework.
1571: Circuit-Aware d-DNNF Compilation
Authors: Vincent Derkinderen, Jean-Marie Lagniez
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
Boolean circuits in d-DNNF (determinstic Decomposable Negation Normal Form) enable tractable probabilistic inference, motivating research into compilers that transform arbitrary Boolean circuit into this form. However, d-DNNF compilers commonly require the input to be in conjunctive normal form (CNF), which means that a user must first convert their Boolean circuit into CNF. In this work, we argue that d-DNNF compilation would substantially benefit from reasoning over the original input circuit’s structure, rather than solely relying on its CNF representation. To this end, we adapt an existing compiler and implement an optimisation that becomes more readily available once we reason over the input circuit: the identification and elimination of don’t care variables. We empirically demonstrate the effectiveness of this approach, achieving a significant improvement in both the number of solved instances and the size of the resulting circuits.
1579: Cyclic Vision-Language Manipulator: Towards Reliable and Fine-Grained Image Interpretation for Automated Report Generation
Authors: Yingying Fang, Zihao Jin, Shaojie Guo, Jinda Liu, Zhiling Yue, Yijian Gao, Junzhi Ning, Zhi Li, Simon Walsh, Guang Yang
Location: Montreal | Day: August 21st | Time: 10:00 | Session: AI Ethics, Trust, Fairness (2/3)
Show Abstract
Despite significant advancements in automated report generation, the opaqueness of text interpretability continues to cast doubt on the reliability of the content produced. This paper introduces a novel approach to identify specific image features in X-ray images that influence the outputs of report generation models. Specifically, we propose Cyclic Vision-Language Manipulator (CVLM), a module to generate a manipulated X-ray from an original X-ray and its report from a designated report generator. The essence of CVLM is that cycling manipulated X-rays to the report generator produces altered reports aligned with the alterations pre-injected into the reports for X-ray generation, achieving the term “cyclic manipulation”. This process allows direct comparison between original and manipulated X-rays, clarifying the critical image features driving changes in reports and enabling model users to assess the reliability of the generated texts. Empirical evaluations demonstrate that CVLM can identify more precise and reliable features compared to existing explanation methods, significantly enhancing the transparency and applicability of AI-generated reports.
1585: Zero-shot Generalist Graph Anomaly Detection with Unified Neighborhood Prompts
Authors: Chaoxi Niu, Hezhe Qiao, Changlu Chen, Ling Chen, Guansong Pang
Location: Montreal | Day: August 21st | Time: 15:00 | Session: DM: Graph Data Mining
Show Abstract
Graph anomaly detection (GAD), which aims to identify nodes in a graph that significantly deviate from normal patterns, plays a crucial role in broad application domains. However, existing GAD methods are one-model-for-one-dataset approaches, i.e., training a separate model for each graph dataset. This largely limits their applicability in real-world scenarios. To overcome this limitation, we propose a novel zero-shot generalist GAD approach UNPrompt that trains a one-for-all detection model, requiring the training of one GAD model on a single graph dataset and then effectively generalizing to detect anomalies in other graph datasets without any retraining or fine-tuning. The key insight in UNPrompt is that i) the predictability of latent node attributes can serve as a generalized anomaly measure and ii) generalized normal and abnormal graph patterns can be learned via latent node attribute prediction in a properly normalized node attribute space. UNPrompt achieves a generalist mode for GAD through two main modules: one module aligns the dimensionality and semantics of node attributes across different graphs via coordinate-wise normalization, while another module learns generalized neighborhood prompts that support the use of latent node attribute predictability as an anomaly score across different datasets. Extensive experiments on real-world GAD datasets show that UNPrompt significantly outperforms diverse competing methods under the generalist GAD setting, and it also has strong superiority under the one-model-for-one-dataset setting. Code is available at https://github.com/mala-lab/UNPrompt.
1596: Guaranteed Top-Adaptive-K in Recommendation
Authors: Nitin Bisht, Xiuwen Gong, Guandong Xu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Machine Learning (1/4)
Show Abstract
Recommender systems (RS) are crucial in offering personalized suggestions tailored to user preferences. While conventionally, Top-K recommendation approach is widely adopted, its reliance on fixed recommendation sizes overlooks the diverse needs of users, leading to some relevant items not being recommended or vice versa. While recent work has made progress, they determine K by searching over all possible recommendation sizes for each user during inference. In real-world scenarios, with large datasets and numerous users with diverse and extensive preferences, this process becomes computationally impractical. Moreover, there is no theoretical guarantee of improved performance with the personalized K. In this paper, we propose a novel framework, Top-Adaptive-K, which determines dynamic K-prediction set size for each user efficiently and effectively. Generally, the framework formulates the recommendation problem within the Conformal Risk Control paradigm and proposes the loss function based on user utility functions. A novel greedy optimization algorithm, K-Adapt, is designed to efficiently learn prediction sets. Theoretical analysis is provided to ensure recommendation performance by establishing upper bounds on the expected risk. Extensive experiments on multiple datasets demonstrate that the Top-Adaptive-K framework outperforms baseline methods in both performance and time efficiency, offering a guaranteed solution to the fixed Top-K challenges.
1600: Polynomial-Time Relational Probabilistic Inference in Open Universes
Authors: Luise Ge, Brendan Juba, Kris Nilsson
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Uncertainty in AI
Show 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.
1625: CASA: CNN Autoencoder-based Score Attention for Efficient Multivariate Long-term Time-series Forecasting
Authors: Minhyuk Lee, Hyekyung Yoon, MyungJoo Kang
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: time series, sequences and signals
Show Abstract
Multivariate long-term time series forecasting is critical for applications such as weather prediction, and traffic analysis. In addition, the implementation of Transformer variants has improved prediction accuracy. Following these variants, different input data process approaches also enhanced the field, such as tokenization techniques including point-wise, channel-wise, and patch-wise tokenization. However, previous studies still have limitations in time complexity, computational resources, and cross-dimensional interactions. To address these limitations, we introduce a novel CNN Autoencoder-based Score Attention mechanism (CASA), which can be introduced in diverse Transformers model-agnosticically by reducing memory and leading to improvement in model performance. Experiments on eight real-world datasets validate that CASA decreases computational resources by up to 77.7%, accelerates inference by 44.0%, and achieves state-of-the-art performance, ranking first in 87.5% of evaluated metrics. Our code is available at https://github.com/lmh9507/CASA.
1626: Evaluating and Mitigating Linguistic Discrimination in Large Language Models: Perspectives on Safety Equity and Knowledge Equity
Authors: Guoliang Dong, Haoyu Wang, Jun Sun, Xinyu Wang
Location: Montreal | Day: August 21st | Time: 10:00 | Session: AI Ethics, Trust, Fairness (2/3)
Show Abstract
Large language models (LLMs) typically provide multilingual support and demonstrate remarkable capabilities in solving tasks described in different languages. However, LLMs can exhibit linguistic discrimination due to the uneven distribution of training data across languages. That is, LLMs struggle to maintain consistency when handling the same task in different languages, compromising both safety equity and knowledge equity. In this paper, we first systematically evaluate the linguistic discrimination of LLMs from two aspects: safety and quality, using a form of metamorphic testing. The metamorphic relationship we examine is that LLMs are expected to deliver outputs with similar semantics when prompted with inputs that have the same meaning. We conduct this evaluation with two datasets based on four representative LLMs. The results show that LLMs exhibit stronger human alignment capabilities with queries in English, French, Russian, and Spanish compared to queries in Bengali, Georgian, Nepali and Maithili. Moreover, for queries in English, Danish, Czech and Slovenian, LLMs tend to produce responses with a higher quality compared to the other languages. Upon these findings, we propose LDFighter, a similarity-based voting method, to mitigate the linguistic discrimination in LLMs. We comprehensively evaluate LDFighter against a spectrum of queries including benign, harmful, and adversarial prompts. The results show that LDFighter significantly reduces jailbreak success rates and improves response quality. All code, data, and the technical appendix are publicly available at: \url{https://github.com/dgl-prc/ldfighter}.
1675: A Game-Theoretic Perspective on Inconsistency Handling
Authors: Yakoub Salhi
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
This paper introduces a game-theoretic framework for restoring consistency in propositional bases. The process is modeled as an interactive dialogue between two agents: a Proponent, who seeks to isolate a unique, consistent subset by posing strategic questions, and an Opponent, who aims to obstruct that goal through adversarial responses. We show that this framework provides a foundation for quantifying the effort involved in restoring consistency, revealing a connection between this effort and entropy in information theory. Focusing on the case where consistency is achieved by isolating a single maximal consistent subset, we establish links between the structure and number of such subsets and the existence of winning strategies. Finally, we demonstrate how the quantified restoration effort can serve as a basis for measuring inconsistency.
1691: Deep Learning-Based Pedestrian Simulation with Limited Real-World Training Data: An Evaluation Framework
Authors: Vahid Mahzoon, Abigail Liu, Slobodan Vucetic
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Agent-based and Multi-agent Systems (2/3)
Show Abstract
Simulating pedestrian movement is important for applications such as disaster management, robotics, and game design. While deep learning models have been extensively used on related problems, their use as pedestrian simulators remains relatively unexplored. This paper aims to encourage more research in this direction in two ways. First, it proposes an evaluation framework that is applicable to both traditional and deep learning based simulators. Second, it proposes and evaluates several ideas related to input representation, choice of neural architecture, exploiting knowledge-based simulators in data poor regimes, and repurposing trajectory prediction models. Our extensive experiments provide several useful insights for future research in pedestrian simulation. The code is available at https://github.com/vmahzoon76/DL-Crowd-Sim.
1712: Asymptotic Analysis of Weighted Fair Division
Authors: Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Game Theory and Economic Paradigms
Show Abstract
Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Omega(n log n / log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / (1 – \mu) for the transition from non-existence to existence, where \mu in (0,1) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = omega(sqrt{r}), where r denotes the ratio between the two weights.
1736: Knowledge Editing for Multi-Hop Question Answering Using Semantic Analysis
Authors: Dominic Simon, Rickard Ewetz
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Natural Language Processing (2/2)
Show Abstract
Large Language Models (LLMs) require lightweight avenues of updating stored information that has fallen out of date. Knowledge Editing (KE) approaches have been successful in updating model knowledge for simple factual queries but struggle with handling tasks that require compositional reasoning such as multi-hop question answering (MQA). We observe that existing knowledge editors leverage decompositional techniques that result in illogical reasoning processes. In this paper, we propose a knowledge editor for MQA based on semantic analysis called CHECK. Our framework is based on insights from an analogy between compilers and reasoning using LLMs. Similar to how source code is first compiled before being executed, we propose to semantically analyze reasoning chains before executing the chains to answer questions. Reasoning chains with semantic errors are revised to ensure consistency through logic optimization and re-prompting the LLM model at a higher temperature. We evaluate the effectiveness of CHECK against five state-of-the-art frameworks on four datasets and achieve an average 22.8% improved MQA accuracy.
1781: EDyGS: Event Enhanced Dynamic 3D Radiance Fields from Blurry Monocular Video
Authors: Mengxu Lu, Zehao Chen, Yan Liu, De Ma, Huajin Tang, Qian Zheng, Gang Pan
Location: Montreal | Day: August 21st | Time: 15:00 | Session: CV: videos
Show Abstract
The task of generating novel views in dynamic scenes plays a critical role in the 3D vision domain. Neural Radiance Fields (NeRFs) and 3D Gaussian Splatting (3DGS) have shown great promise in this domain but struggle with motion blur, which often arises in real-world scenarios due to camera or object motion. Existing methods address camera motion blur but fall short in dynamic scenes, where the coupling of camera and object motion complicates multi-view consistency and temporal coherence. In this work, we propose EDyGS, a model designed to reconstruct sharp novel views from event streams and monocular videos of dynamic scenes with motion blur. Our approach introduces a motion-mask 3D Gaussian model that assigns each Gaussian an additional attribute to distinguish between static and dynamic regions. By leveraging this motion mask field, we separate and optimize the static and dynamic regions independently. A progressive learning strategy is adopted, where static regions are reconstructed by jointly optimizing camera poses and learnable 3D Gaussians, while dynamic regions are modeled using an implicit deformation field alongside learnable 3D Gaussians. We conduct both quantitative and qualitative experiments on synthetic and real-world data. Experimental results demonstrate that EDyGS effectively handles blurry inputs in dynamic scenes.
1837: A General Framework for Representing Controlled Natural Language Sentences and Translation to KR Formalisms
Authors: Simone Caruso, Carmine Dodaro, Marco Maratea, Alice Tarzariol
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
Languages for Knowledge Representation and Reasoning, such as ASP, CP, and SMT, excel at solving some complex problems, but encoding them into a higher-level language may be more profitable, leaving these formalisms as targets for solving. Recent studies aim to convert controlled natural languages into formal representations, yet these solutions are often tailored to specific languages and require significant effort.
This paper introduces a general framework that generates grammars for target representation languages, enabling the translation of problems stated in CNL into formal representations. The related system, CNLWizard, offers a flexible, high-level approach to defining desired grammars, significantly reducing the time and effort needed to create custom grammars. Finally, we demonstrate the system’s effectiveness through an experimental analysis.
1839: Multi Objective Quantile Based Reinforcement Learning for Modern Urban Planning
Authors: Lukasz Pelcner, Leandro Soriano Marcolino, Matheus Aparecido do Carmo Alves, Paula A. Harrison, Peter M. Atkinson
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Agent-based and Multi-agent Systems (3/3)
Show Abstract
We present a novel Multi-Agent Reinforcement Learning approach to understand and improve policy development by land-shaping agents, such as governments and institutional bodies. We derive the underlying policy decisions by analyzing the land and developing an intelligent system that proposes optimal land conversion strategies. The aim is an efficient method for allocating residential spaces while considering the dynamic population influx in different regions, jurisdictional constraints, and the intrinsic characteristics of the land. Our main goal is to be sustainable, preserving desirable land types such as forests and fluvial lands while optimizing land organization. We introduce an attractiveness metric that quantifies the proximity to different land types and other factors to optimize land usage. It distinguishes two types of agents: “top-down” agents, which are policymakers and shareholders, and “bottom-up” agents representing individuals or groups with specific housing preferences. Our main objective is to create a synergistic environment where the top-down policy meets the bottom-up preferences to devise a comprehensive land use and conversion strategy. This paper, thus, serves as a pivotal reference point for future urban planning and policy-making processes, contributing to a sustainable and efficient landscape design model.
1861: Most Probable Explanation in Probabilistic Answer Set Programming
Authors: Damiano Azzolini, Giuseppe Mazzotta, Francesco Ricca, Fabrizio Riguzzi
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Uncertainty in AI
Show 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.
1880: Sanitizing Backdoored Graph Neural Networks: A Multidimensional Approach
Authors: Rong Zhao, Jilian Zhang, Yu Wang, Yinyan Zhang, Jian Weng
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
Graph Neural Networks (GNNs) are known to be prone to adversarial attacks, among which backdoor attack is a major security threat. By injecting backdoor triggers into a graph and assigning a target class label to nodes attached to the triggers, the attacker can mislead the GNN model trained on the poisoned graph to classify test nodes attached with a trigger to the target class. To defend against backdoor attacks, existing defense methods rely on anomaly detection in feature distribution or label transformation. However, these approaches are incapable of detecting in-distribution triggers or clean-label attacks that do not alter the class label of target nodes. To tackle these threats, we empirically analyze triggers from a multidimensional aspect, and our analysis shows that there are clear distinctions between trigger nodes and normal ones in terms of node feature values, node embeddings, and class prediction probabilities. Based on these findings, we propose a Multidimensional Anomaly Detection framework (MAD) that can effectively minimize the impact of triggers by pruning away anomalous nodes and edges. Extensive experiments show that at the cost of slight loss in clean classification accuracy, MAD achieves considerably lower attack success rate as compared to state-of-the-art backdoor defense methods.
1923: Bidirectional Search while Ensuring Meet-In-The-Middle via Effective and Efficient-to-Compute Termination Conditions
Authors: Yi Wang, Eyal Weiss, Bingxian Mu, Oren Salzman
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Search
Show Abstract
In bidirectional heuristic search, the meeting-in-the-middle property (MMP) and the theory of must-expand pairs (MEP) have driven significant recent developments in search efficiency. However, these methodologies typically terminate the search based on minimal priority metrics in the forward and backward open lists, requiring exploration of all potentially better solutions and potentially incurring substantial computational burden. In this paper, we investigate the reasons that contribute to the potential inefficiency in MM , and introduce a tighter termination condition that enables earlier termination without exhaustive exploration while still ensuring both MMP and optimality. This results in a highly efficient bidirectional search algorithm.
Experimental comparisons demonstrate that our algorithm outperforms MM in terms of running time by at least two orders of magnitude and is on par or better compared to A*, highlighting its potential in a wide range of applications.
1932: Contrastive Unlearning: A Contrastive Approach to Machine Unlearning
Authors: Hong kyu Lee, Qiuchen Zhang, Carl Yang, Jian Lou, Li Xiong
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MTA: Security and privacy
Show Abstract
Machine unlearning aims to eliminate the influence of a subset of training samples (i.e., unlearning samples) from a trained model. Effectively and efficiently removing the unlearning samples without negatively impacting the overall model performance is challenging. Existing works mainly exploit input and output space and classification loss, which can result in ineffective unlearning or performance loss. In addition, they utilize unlearning or remaining samples ineffectively, sacrificing either unlearning efficacy or efficiency.
Our main insight is that the direct optimization on the representation space utilizing both unlearning and remaining samples can effectively remove influence of unlearning samples while maintaining representations learned from remaining samples. We propose a contrastive unlearning framework, leveraging the concept of representation learning for more effective unlearning. It removes the influence of unlearning samples by contrasting their embeddings against the remaining samples’ embeddings
so that their embeddings are closer to the embeddings of unseen samples.
Experiments on a variety of datasets and models on both class unlearning and sample unlearning showed that contrastive unlearning achieves the best unlearning effects and efficiency with the lowest performance loss compared with the state-of-the-art algorithms. In addition, it is generalizable to different contrastive frameworks and other models such as vision-language models. Our main code is available on github.com/Emory-AIMS/Contrastive-Unlearning
1978: Equitable Mechanism Design for Facility Location
Authors: Toby Walsh
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
We consider strategy proof mechanisms for facility location which maximize equitability between agents. As is common in the literature, we measure equitability with the Gini index. We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities for one or more facilities. We propose instead computing approximation ratios of the complemented Gini index of utilities, and consider how well both deterministic and randomized mechanisms approximate this. In addition, as Nash welfare is often put forwards as an equitable compromise between egalitarain and utilitarian outcomes, we consider how well mechanisms approximate the Nash welfare.
1990: Bridging Local and Global Knowledge via Transformer in Board Games
Authors: Yan-Ru Ju, Tai-Lin Wu, Chung-Chin Shih, Ti-Rong Wu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
Although AlphaZero has achieved superhuman performance in board games, recent studies reveal its limitations in handling scenarios requiring a comprehensive understanding of the entire board, such as recognizing long-sequence patterns in Go. To address this challenge, we propose ResTNet, a network that interleaves residual and Transformer blocks to bridge local and global knowledge. ResTNet improves playing strength across multiple board games, increasing win rate from 54.6% to 60.8% in 9×9 Go, 53.6% to 60.9% in 19×19 Go, and 50.4% to 58.0% in 19×19 Hex. In addition, ResTNet effectively processes global information and tackles two long-sequence patterns in 19×19 Go, including circular pattern and ladder pattern. It reduces the mean square error for circular pattern recognition from 2.58 to 1.07 and lowers the attack probability against an adversary program from 70.44% to 23.91%. ResTNet also improves ladder pattern recognition accuracy from 59.15% to 80.01%. By visualizing attention maps, we demonstrate that ResTNet captures critical game concepts in both Go and Hex, offering insights into AlphaZero’s decision-making process. Overall, ResTNet shows a promising approach to integrating local and global knowledge, paving the way for more effective AlphaZero-based algorithms in board games. Our code is available at https://rlg.iis.sinica.edu.tw/papers/restnet.
2001: Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints
Authors: Yu Cong, Chao Xu, Yi Zhou
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Constraint Satisfaction and Optimization (3/3)
Show Abstract
We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all time. The application originally comes from assigning coupons to users of the ride-sharing apps, where each user can have a limit on the number of coupons been assigned. We consider a more general form, where the coupons for each user forms a matroid, and the coupon assigned to each user must be an independent set. We show the entire trade-off curve can be maintained approximately in near real time.
2041: Privacy Preserving Solution of DCOPs by Local Search
Authors: Shmuel Goldklang, Tal Grinshpoun, Tamir Tassa
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Constraint Satisfaction and Optimization (1/3)
Show Abstract
One of the main reasons for solving constraint optimization problems in a distributed manner is maintaining agents’ privacy. Several studies in the past decade devised privacy-preserving versions of Distributed Constraint Optimization Problem (DCOP) algorithms. Some of those algorithms were complete, i.e., finding an optimal solution, while others were incomplete. The main advantage of the incomplete approach is in its scalability to large problems. One of the important incomplete paradigms for solving DCOPs is local search. Yet, so far no privacy-preserving algorithm for solving DCOPs by means of local search was devised. We present P-DSA, a privacy-preserving implementation of the classical local-search algorithm DSA that preserves topology, constraint, and assignment/decision privacy. Comparing its performance to that of P-Max-Sum, which is another privacy-preserving implementation of an incomplete DCOP algorithm, shows that P-DSA is significantly more scalable and issues much better solutions than P-Max-Sum. Therefore, P-DSA emerges as a suitable solution for practitioners addressing large-scale DCOPs with privacy considerations.
2050: fairGNN-WOD: Fair Graph Learning Without Complete Demographics
Authors: Zichong Wang, Fang Liu, Shimei Pan, Jun Liu, Fahad Saeed, Meikang Qiu, Wenbin Zhang
Location: Montreal | Day: August 21st | Time: 11:30 | Session: ETF: Fairness and diversity
Show Abstract
Graph Neural Networks (GNNs) have excelled in diverse applications due to their outstanding predictive performance, yet they often overlook fairness considerations, prompting numerous recent efforts to address this societal concern. However, most fair GNNs assume complete demographics by design, which is impractical in most real-world socially sensitive applications due to privacy, legal, or regulatory restrictions. For example, the Consumer Financial Protection Bureau (CFPB) mandates that creditors ensure fairness without requesting or collecting information about an applicant’s race, religion, nationality, sex, or other demographics. To this end, this paper proposes fairGNN-WOD, a first-of-its-kind framework that considers mitigating unfairness in graph learning without using demographic information. In addition, this paper provides a theoretical perspective on analyzing bias in node representations and establishes the relationship between utility and fairness objectives. Experiments on three real-world graph datasets illustrate that fairGNN-WOD outperforms state-of-the-art baselines in achieving fairness but also maintains comparable prediction performance.
2066: Steady-State Strategy Synthesis for Swarms of Autonomous Agents
Authors: Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
The steady-state synthesis aims to construct a policy for a given MDP D such that the long-run average frequencies of visits to the vertices of D satisfy given numerical constraints. This problem is solvable in polynomial time, and memoryless policies are sufficient for approximating an arbitrary frequency vector achievable by a general (infinite-memory) policy.

We study the steady-state synthesis problem for multiagent systems, where multiple autonomous agents jointly strive to achieve a suitable frequency vector. We show that the problem for multiple agents is computationally hard (PSPACE or NP hard, depending on the variant), and memoryless strategy profiles are insufficient for approximating achievable frequency vectors. Furthermore, we prove that even evaluating the frequency vector achieved by a given memoryless profile is computationally hard. This reveals a severe barrier to constructing an efficient synthesis algorithm, even for memoryless profiles. Nevertheless, we design an efficient and scalable synthesis algorithm for a subclass of full memoryless profiles, and we evaluate this algorithm on a large class of randomly generated instances. The experimental results demonstrate a significant improvement against a naive algorithm based on strategy sharing.
2106: Accurate Sublayer Pruning for Large Language Models by Exploiting Latency and Tunability Information
Authors: Seungcheol Park, Sojin Lee, Jongjin Kim, Jinsik Lee, Hyunjik Jo, U Kang
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Natural Language Processing (2/2)
Show Abstract
How can we accelerate large language models (LLMs) without sacrificing accuracy? The slow inference speed of LLMs hinders us to benefit from their remarkable performance in diverse applications. This is mainly because numerous sublayers are stacked together in LLMs. Sublayer pruning compresses and expedites LLMs via removing unnecessary sublayers. However, existing sublayer pruning algorithms are limited in accuracy since they naively select sublayers to prune, overlooking the different characteristics of each sublayer.
In this paper, we propose SPRINT (Sublayer Pruning with Latency and Tunability Information), an accurate sublayer pruning method for LLMs. SPRINT accurately selects a target sublayer to prune by considering 1) the amount of latency reduction after pruning and 2) the tunability of sublayers. SPRINT iteratively prunes redundant sublayers and swiftly tunes the parameters of remaining sublayers. Experiments show that SPRINT achieves the best accuracy-speedup trade-off, exhibiting up to 23.88%p higher accuracy on zero-shot commonsense reasoning benchmarks compared to existing pruning algorithms.
2157: TsCA: On the Semantic Consistency Alignment via Conditional Transport for Compositional Zero-Shot Learning
Authors: Miaoge Li, Jingcai Guo, Richard Yi Da Xu, Dongsheng Wang, Xiaofeng Cao, Zhijie Rao, Song Guo
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
Compositional Zero-Shot Learning (CZSL) aims to recognize novel state-object compositions by leveraging the shared knowledge of their primitive components. Despite considerable progress, effectively calibrating the bias between semantically similar multimodal representations, as well as generalizing pre-trained knowledge to novel compositional contexts, remains an enduring challenge. In this paper, our interest is to revisit the conditional transport (CT) theory and its homology to the visual-semantics interaction in CZSL and further, propose a novel Trisets Consistency Alignment framework (dubbed TsCA) that well-addresses these issues. Concretely, we utilize three distinct yet semantically homologous sets, i.e., patches, primitives, and compositions, to construct pairwise CT costs to minimize their semantic discrepancies. To further ensure the consistency transfer within these sets, we implement a cycle-consistency constraint that refines the learning by guaranteeing the feature consistency of the self-mapping during transport flow, regardless of modality. Moreover, we extend the CT plans to an open-world setting, which enables the model to effectively filter out unfeasible pairs, thereby speeding up the inference as well as increasing the accuracy. Extensive experiments are conducted to verify the effectiveness of the proposed method. The code is available at https://github.com/keepgoingjkg/TsCA.
2229: POLO: An LLM-Powered Project-Level Code Performance Optimization Framework
Authors: Jiameng Bai, Ruoyi Xu, Sai Wu, Dingyu Yang, Junbo Zhao, Gang Chen
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: MTA: Software engineering
Show Abstract
Program performance optimization is essential for achieving high execution efficiency, yet it remains a challenging task that requires expertise in both software and hardware.
Large Language Models (LLMs), trained on high-quality code from platforms like GitHub and other open-source sources, have shown promise in generating optimized code for simple snippets. However, current LLM-based solutions often fall short when tackling project-level programs due to the complexity of call graphs and the intricate interactions among functions. In this paper, we emulate the process a human expert might follow when optimizing project-level programs and introduce a three-phase framework POLO (PrOject-Level Optimizer) to address this limitation.
First, we profile the program to identify performance bottlenecks using an iterative weighting algorithm.
Next, we conduct structural analysis by scanning the project and generating a graph that represents the program’s structure.
Finally, two LLM agents collaborate in iterative cycles to rewrite and optimize the code at these hotspots, gradually improving performance.
We conduct experiments on open-source and proprietary projects. The results demonstrate that POLO accurately identifies performance bottlenecks and successfully applies optimizations. Under the O3 compilation flag, the optimized programs achieved speedups ranging from 1.34x to 21.5x.
2257: Improved Rank Aggregation Under Fairness Constraint
Authors: Diptarka Chakraborty, Himika Das, Sanjana Dey, Alvin Hong Yao Yan
Location: Montreal | Day: August 21st | Time: 11:30 | Session: ETF: Fairness and diversity
Show Abstract
Aggregating multiple input rankings into a consensus ranking is essential in various fields such as social choice theory, hiring, college admissions, web search, and databases. A major challenge is that the optimal consensus ranking might be biased against individual candidates or groups, especially those from marginalized communities. This concern has led to recent studies focusing on fairness in rank aggregation. The goal is to ensure that candidates from different groups are fairly represented in the top-k positions of the aggregated ranking.

We study this fair rank aggregation problem by considering the Kendall tau as the underlying metric. While we know of a polynomial-time approximation scheme (PTAS) for the classical rank aggregation problem, the corresponding fair variant only possesses a quite straightforward 3-approximation algorithm due to Wei et al., SIGMOD’22, and Chakraborty et al., NeurIPS’22, which finds closest fair ranking for each input ranking and then simply outputs the best one.

In this paper, we first provide a novel algorithm that achieves (2+ε)-approximation (for any ε > 0), significantly improving over the 3-approximation bound. Next, we provide a 2.881-approximation fair rank aggregation algorithm that works irrespective of the fairness notion, given one can find a closest fair ranking, beating the 3-approximation bound. We complement our theoretical guarantee by performing extensive experiments on various real-world datasets to establish the effectiveness of our algorithm further by comparing it with the performance of state-of-the-art algorithms.
2323: Simulating Misinformation Diffusion on Social Media Through CoNVaI: A Textual- and Agent-Based Diffusion Model
Authors: Raquel Rodríguez-García, Roberto Centeno, Álvaro Rodrigo
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Agent-based and Multi-agent Systems (2/3)
Show Abstract
Misinformation has experienced increased online diffusion, leveraging strategies, such as emotional manipulation, to influence users’ opinions. Efforts are underway to develop tools to mitigate its effects, such as misinformation propagation models used to simulate the diffusion of information. There are different approaches within these models, although, they show a significant limitation by disregarding the content of the information shared, crucial to the diffusion. We consider it the central aspect of modeling information dissemination. To this end, we focus on Agent-Based Modeling due to its suitability to simulate the complex interactions and heterogeneous behaviors observed on social media. We base our approach on a state-of-the-art Agent-Based Model that we modify and extend to account for the texts of the messages shared, focusing on two aspects that influence agents’ decisions: i) the novelty of the content and; ii) its diffusion and behavior over time. To determine whether this content proves informative, we conduct an empirical evaluation using social media data from Twitter. Based on our experimental results, we observe that our textual-based approach reflects information diffusion more realistically than the state of the art, reducing the error regarding real diffusion.
2347: Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
Authors: Martin Bullinger, Matan Gilboa
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Game Theory
Show Abstract
We study coalition formation in the framework of hedonic games. These games model the problem of partitioning a set of agents having a preference order over the coalitions they can be part of. A partition is called popular if it does not lose a majority vote among the agents against any other partition. Unfortunately, hedonic games need not admit popular partitions. We go further and settle the complexity of the existence problem concerning popularity in additively separable and fractional hedonic games by showing that it is Sigma_2^p-complete in both cases. We are thus the first work that proves a completeness result of popularity for the second level of the polynomial hierarchy.
2416: Strategies, Credences, and Shannon Entropy: Reasoning about Strategic Uncertainty in Stochastic Environments
Authors: Wojciech Jamroga, Michał Tomasz Godziszewski, Aniello Murano
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Agent-based and Multi-agent Systems (3/3)
Show Abstract
Multi-agent systems (MAS) often include multiple layers of uncertainty. One source comes from agents’ limited ability to observe their environment, while another arises from the unpredictability of natural events and the actions of other agents, which, though uncertain, can be estimated through experiments or past experiences.
A central focus in MAS is the agents’ ability to achieve their goals.For intelligent agents, these goals are often epistemic,
involving the acquisition of partial or complete knowledge about a crucial fact A. Many such properties can be expressed using PATLK, an extension of probabilistic alternating-time temporal logic (PATL) with knowledge operators, or PATLC that extends PATL with probabilistic beliefs.

In many scenarios, however, the goal of the players is not to achieve high confidence about A being true, but rather to reduce their uncertainty about A (be it true or false). Similarly, in scenarios where the goal is to keep A secret, the outsiders’ uncertainty about A should be maintained above a certain threshold. To capture such properties, we introduce PATLH, a logic extending PATL with information-theoretic modalities based on Shannon entropy.The logic enables the specification of agents’ capabilities concerning the uncertainty of a player about a given set of facts. We define it over multi-agent systems with stochastic transitions and probabilistic imperfect information, capturing two key uncertainties: the agents’ partial observability of their environment and the stochastic nature of state transitions. As technical results, we compare the epistemic and information-theoretic extensions of PATL with respect to their expressiveness, succinctness, and complexity of model checking.
2424: SALE-MLP: Structure Aware Latent Embeddings for GNN to Graph-free MLP Distillation
Authors: Harsh Pal, Sarthak Malik, Rajat Patel, Aakarsh Malhotra
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
Graph Neural Networks (GNNs), with their ability to effectively handle non-Euclidean data structures, have demonstrated state-of-the-art performance in learning node and graph-level representations. However, GNNs face significant computational overhead due to their message-passing mechanisms, making them impractical for real-time large-scale applications. Recently, Graph-to-MLP (G2M) knowledge distillation has emerged as a promising solution, utilizing MLPs to reduce inference latency. However, existing methods often lack structural awareness (SA), limiting their ability to capture essential graph-specific information. Moreover, some methods require access to large-scale graphs, undermining their scalability. To address these issues, we propose SALE-MLP (Structure-Aware Latent Embeddings for GNN-to-Graph-Free MLP Distillation), a novel graph-free and structure-aware approach that leverages unsupervised structural losses to align the MLP feature space with the underlying graph structure. SALE-MLP does not rely on precomputed GNN embeddings nor require graph during inference, making it efficient for real-world applications. Extensive experiments demonstrate that SALE-MLP outperforms existing G2M methods across tasks and datasets, achieving 3–4% improvement in node classification for inductive settings while maintaining strong transductive performance.
2428: Unveiling the Power of Noise Priors: Enhancing Diffusion Models for Mobile Traffic Prediction
Authors: Zhi Sheng, Daisy Yuan, Jingtao Ding, Qi Yan, Xi Zheng, Yue Sun, Yong Li
Location: Montreal | Day: August 19th | Time: 11:30 | Session: ML: Difussion Models
Show Abstract
Accurate prediction of mobile traffic,i.e., network traffic from cellular base stations, is crucial for optimizing network performance and supporting urban development. However, the non-stationary nature of mobile traffic, driven by human activity and environmental changes, leads to both regular patterns and abrupt variations. Diffusion models excel in capturing such complex temporal dynamics due to their ability to capture the inherent uncertainties. Most existing approaches prioritize designing novel denoising networks but often neglect the critical role of noise itself, potentially leading to sub-optimal performance. In this paper, we introduce a novel perspective by emphasizing the role of noise in the denoising process. Our analysis reveals that noise fundamentally shapes mobile traffic predictions, exhibiting distinct and consistent patterns. We propose NPDiff, a framework that decomposes noise into prior and residual components, with the prior derived from data dynamics, enhancing the model’s ability to capture both regular and abrupt variations. NPDiff can seamlessly integrate with various diffusion-based prediction models, delivering predictions that are effective, efficient, and robust. Extensive experiments demonstrate that it achieves superior performance with an improvement over 30%, offering a new perspective on leveraging diffusion models in this domain. We provide code and data at https://github.com/tsinghua-fib-lab/NPDiff.
2481: Improved Approximation Ratio for Strategyproof Facility Location on a Cycle
Authors: Krzysztof Rogowski, Marcin Dziubiński
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Game Theory and Economic Paradigms
Show Abstract
We study the problem of design of strategy-proof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of n agents. We show that there exists an SP mechanism that attains an approximation ratio of 7/4 with respect to the sum of costs of the agents, thus improving the best known upper bound of 2 – 2/n in the cases of n ≥ 5. The mechanism obtaining the bound randomizes between two mechanisms known in the literature: the Random Dictator (RD) and the Proportional Circle Distance (PCD) mechanism of Meir (2019). To prove the result, we propose a cycle-cutting technique that allows for estimating the problem on a cycle by a problem on a line.
2483: Online Planning in MDPs with Stochastic Durative Actions
Authors: Tal Berman, Ronen I. Brafman, Erez Karpas
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Planning and Scheduling (2/5)
Show Abstract
Stochastic planning problems are typically modeled as Markov Decision Processes, in which actions are assumed to be instantaneous and applied sequentially. Yet, real-world actions often have durations and are applied concurrently. This paper presents an online planning approach that can deal with durative actions with stochastic outcomes. Our approach relies on Monte Carlo Tree Search with a new backpropagation procedure and temporal reasoning techniques that address the need to not only choose which action to execute, but also when to execute it. We also introduce a novel heuristic that combines reasoning about time and probabilities. Overall, we present the first online planner for stochastic temporal planning, solving a richer problem representation than previous work while achieving state-of-the-art empirical results.
2488: Non-expansive Fuzzy ALC
Authors: Stefan Gebhart, Lutz Schröder, Paul Wild
Location: Montreal | Day: August 21st | Time: 10:00 | Session: KRR: Learning and reasoning
Show Abstract
Fuzzy description logics serve the representation of vague knowledge, typically letting concepts take truth degrees in the unit interval. Expressiveness, logical properties, and complexity vary strongly with the choice of propositional base. The Łukasiewicz propositional base is generally perceived to have preferable logical properties but often entails high complexity or even undecidability. Contrastingly, the less expressive Zadeh propositional base comes with low complexity but entails essentially no change in logical behaviour compared to the classical case. To strike a balance between these poles, we propose non-expansive fuzzy ALC, in which the Zadeh base is extended with Łukasiewicz connectives where one side is restricted to be a rational constant, that is, with constant shift operators. This allows, for instance, modelling dampened inheritance of properties along roles. We present an unlabelled tableau method for non-expansive fuzzy ALC, which allows reasoning over general TBoxes in EXPTime like in two-valued ALC.
2508: KP-PINNs: Kernel Packet Accelerated Physics Informed Neural Networks
Authors: Siyuan Yang, Cheng Song, Zhilu Lai, Wenjia Wang
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
Differential equations are involved in modeling many engineering problems. Many efforts have been devoted to solving differential equations. Due to the flexibility of neural networks, Physics Informed Neural Networks (PINNs) have recently been proposed to solve complex differential equations and have demonstrated superior performance in many applications. While the L2 loss function is usually a default choice in PINNs, it has been shown that the corresponding numerical solution is incorrect and unstable for some complex equations. In this work, we propose a new PINNs framework named Kernel Packet accelerated PINNs (KP-PINNs), which gives a new expression of the loss function using the reproducing kernel Hilbert space (RKHS) norm and uses the Kernel Packet (KP) method to accelerate the computation. Theoretical results show that KP-PINNs can be stable across various differential equations. Numerical experiments illustrate that KP-PINNs can solve differential equations effectively and efficiently. This framework provides a promising direction for improving the stability and accuracy of PINNs-based solvers in scientific computing.
2540: An Inverse Optimization Approach to Contextual Inverse Optimization
Authors: Yasunari Hikima, Naoyuki Kamiyama
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: Machine Learning 6/8
Show Abstract
Contextual Inverse Optimization (CIO) is a generalized framework of the predict-then-optimize approach, also referred to as decision-focused learning or contextual optimization, aiming to learn a model that predicts the unknown parameters of a nominal optimization problem using related covariates without compromising the solution quality. Unlike the predict-then-optimize approach, which assumes access to datasets containing realized unknown parameters, CIO considers a setting where only historical optimal solutions are available. Previous work has primarily focused on CIO under linear programming problems and proposed methods based on optimality conditions. In this study, we propose a general algorithm based on inverse optimization as a more general approach that does not require optimality conditions. To validate its effectiveness, we apply the proposed method to multiple CIO problems and demonstrate that it performs comparably to or better than existing predict-then-optimize methods, even without ground-truth unknown parameters.
2571: Multi-Agent Corridor Generating Algorithm
Authors: Arseni Pertzovskiy, Roni Stern, Roie Zivan, Ariel Felner
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
In this paper, we propose the Multi-Agent Corridor Generating Algorithm (MACGA) for solving the Multi-agent Pathfinding (MAPF) problem, where a group of agents need to find non-colliding paths to their target locations. Existing approaches struggle to solve dense MAPF instances. In MACGA, the agents build corridors, which are sequences of connected vertices, from current locations towards agents’ goals, and evacuate other agents out of the corridors to avoid collisions and deadlocks. We also present the MACGA+PIBT algorithm, which integrates the well-known rule-based PIBT algorithm into MACGA to improve runtime and solution quality. The proposed algorithms run in polynomial time and have a reachability property, i.e., every agent is guaranteed to reach its goal location at some point. We demonstrate experimentally that MACGA and MACGA+PIBT outperform baseline algorithms in terms of success rate, runtime, and makespan across diverse MAPF benchmark grids.
2587: RoLocMe: A Robust Multi-agent Source Localization System with Learning-based Map Estimation
Authors: Thanh Dat Le, Lyuzhou Ye, Yan Huang
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Agent-based and Multi-agent Systems (3/3)
Show Abstract
This paper addresses the source localization problem by introducing RoLocMe, a multi-agent reinforcement learning system that integrates SkipNet – a skip-connection-based RSS estimation model – with parallel Q-learning. SkipNet predicts RSS propagation of the entire search region, enabling agents to explore efficiently. The agents leverage dueling DQN, value decomposition, and λ-returns to learn cooperative policies. RoLocMe converges faster and achieves at least 20% higher success rates than existing methods in dense and sparse reward settings. A drop-one ablation study confirms each component’s importance and RoLocMe’s effectiveness for larger teams.
2590: Diffusion-aware Censored Gaussian Processes for Demand Modelling
Authors: Filipe Rodrigues
Location: Montreal | Day: August 19th | Time: 11:30 | Session: ML: Difussion Models
Show Abstract
Inferring the true demand for a product or a service from aggregate data is often challenging due to the limited available supply, thus resulting in observations that are censored and correspond to the realized demand, thereby not accounting for the unsatisfied demand. Censored regression models are able to account for the effect of censoring due to the limited supply, but they don’t consider the effect of substitutions, which may cause the demand for similar alternative products or services to increase. This paper proposes Diffusion-aware Censored Demand Models, which combine a Tobit likelihood with a graph-based diffusion process in order to model the latent process of transfer of unsatisfied demand between similar products or services. We instantiate this new class of models under the framework of GPs and, based on both simulated and real-world data for modeling sales, bike-sharing demand, and EV charging demand, demonstrate its ability to better recover the true demand and produce more accurate out-of-sample predictions.
2591: Towards Fairness with Limited Demographics via Disentangled Learning
Authors: Zichong Wang, Anqi Wu, Nuno Moniz, Shu Hu, Bart Knijnenburg, Xingquan Zhu, Wenbin Zhang
Location: Montreal | Day: August 20th | Time: 10:00 | Session: AI Ethics, Trust, Fairness (1/3)
Show Abstract
Fairness in artificial intelligence has garnered increasing attention due to concerns about discriminatory AI-based decision-making, prompting the development of numerous mitigation approaches. However, most existing methods assume that demographic information is readily available, which may not align with real-world scenarios where such information is often incomplete. To this end, this paper tackles the pervasive yet overlooked challenge of developing fair machine learning algorithms with limited demographics. Specifically, we explore leveraging limited demographic information to accurately infer missing demographics while simultaneously evaluating and optimizing model fairness. We argue that this approach better aligns with common real-world socially sensitive scenarios involving limited demographics. Extensive experiments on three benchmark datasets highlight the effectiveness of the proposed method, surpassing state-of-the-art with significant gains in fairness while maintaining comparable utility.
2597: Imitation Learning via Focused Satisficing
Authors: Rushit N. Shah, Nikolaos Agadakos, Synthia Sasulski, Ali Farajzadeh, Sanjiban Choudhury, Brian Ziebart
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Robotics
Show Abstract
Imitation learning often assumes that demonstrations are close to optimal according to some fixed, but unknown, cost function.
However, according to satisficing theory, humans often choose acceptable behavior based on their personal (and potentially dynamic) levels of aspiration, rather than achieving (near-) optimality. For example, a lunar lander demonstration that successfully lands without crashing might be acceptable to a novice despite being slow or jerky.
Using a margin-based objective to guide deep reinforcement learning, our focused satisficing approach to imitation learning seeks a policy that surpasses the demonstrator’s aspiration levels—defined over trajectories or portions of trajectories—on unseen demonstrations without explicitly learning those aspirations. We show experimentally that this focuses the policy to imitate the highest quality (portions of) demonstrations better than existing imitation learning methods, providing much higher rates of guaranteed acceptability to the demonstrator, and competitive true returns on a range of environments.
2614: Human-Readable Neuro-Fuzzy Networks from Frequent Yet Discernible Patterns in Reward-Based Environments
Authors: John Wesley Hostetter, Adittya Soukarjya Saha, Md Mirajul Islam, Tiffany Barnes, Min Chi
Location: Montreal | Day: August 21st | Time: 10:00 | Session: KRR: Learning and reasoning
Show Abstract
We propose self-organizing and simplifying neuro-fuzzy networks (NFNs) to yield transparent human-readable policies by exploiting fuzzy information granulation and graph theory. Deriving from social network analysis, we retain only the frequent-yet-discernible (FYD) patterns in NFNs and apply them to reward-based scenarios. The effectiveness of NFNs from FYD patterns is shown in classic control and a real-world classroom using an intelligent tutoring system to teach students.
2619: Interval Selection with Binary Predictions
Authors: Christodoulos Karavasilis
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Planning and Scheduling (4/5)
Show Abstract
Following a line of work that takes advantage of vast machine-learned data to enhance online algorithms with (possibly erroneous) information about future inputs, we consider predictions in the context of deterministic algorithms for the problem of selecting a maximum weight independent set of intervals arriving on the real line. We look at two weight functions, unit (constant) weights, and weights proportional to the interval’s length. In the classical online model of irrevocable decisions, no algorithm can achieve constant competitiveness. In this setting, we show that a simple algorithm that is faithful to the predictions is optimal, and achieves an objective value of at least OPT – η, with η being the total error in the predictions, both for unit, and proportional weights.
When revocable acceptances (a form of preemption) are allowed, the optimal deterministic algorithm for unit weights is 2k-competitive, where k is the number of different interval lengths. We give an algorithm with performance OPT − η (and therefore 1-consistent), that is also (2k + 1)-robust. For proportional weights, there is an optimal (2φ + 1)-competitive algorithm, where φ is the golden ratio. We present an algorithm with parameter λ > 1 that is 3λ / (λ – 1) -consistent, and (4λ^2 + 2λ) / (λ – 1)-robust. Although these bounds are not tight, we show that for λ > 3.42 we achieve consistency better than the optimal online guarantee, while maintaining bounded robustness.
We conclude with some experimental results on real-world data that complement our theoretical findings, and show the benefit of prediction algorithms for online interval selection, even in the presence of high error.
2632: Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problems
Authors: Junyang Cai, Serdar Kadioğlu, Bistra Dilkina
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Constraint Satisfaction and Optimization (2/3)
Show Abstract
Mixed-integer programming (MIP) is a powerful paradigm for modeling and solving various important combinatorial optimization problems. Recently, learning-based approaches have shown a potential to speed up MIP solving via offline training that then guides important design decisions during the search. However, a significant drawback of these methods is their heavy reliance on offline training, which requires collecting training datasets and computationally costly training epochs yet offering only limited generalization to unseen (larger) instances. In this paper, we propose Balans, an adaptive meta-solver for MIPs with online learning capability that does not require any supervision or apriori training. At its core, Balans is based on adaptive large-neighborhood search, operating on top of an MIP solver by successive applications of destroy and repair neighborhood operators. During the search, the selection among different neighborhood definitions is guided on the fly for the instance at hand via multi-armed bandit algorithms. Our extensive experiments on hard optimization instances show that Balans offers significant performance gains over the default MIP solver, is better than committing to any single best neighborhood, and improves over the state-of-the-art large-neighborhood search for MIPs. Finally, we release Balans as a highly configurable, MIP solver agnostic, open-source software.
2637: Combining Deep Reinforcement Learning and Search with Generative Models for Game-Theoretic Opponent Modeling
Authors: Zun Li, Marc Lanctot, Kevin R. McKee, Luke Marris, Ian Gemp, Daniel Hennes, Paul Muller, Kate Larson, Yoram Bachrach, Michael P. Wellman
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Agent-based and Multi-agent Systems (3/3)
Show Abstract
Opponent modeling methods typically involve two crucial steps: building a belief distribution over opponents’ strategies, and exploiting this opponent model by playing a best response. However, existing approaches typically require domain-specific heurstics to come up with such a model, and algorithms for approximating best responses are hard to scale in large, imperfect information domains.


In this work, we introduce a scalable and generic multiagent training regime for opponent modeling using deep game-theoretic reinforcement learning. We first propose Generative Best Respoonse (GenBR), a best response algorithm based on Monte-Carlo Tree Search (MCTS) with a learned deep generative model that samples world states during planning. This new method scales to large imperfect information domains and can be plug and play in a variety of multiagent algorithms. We use this new method under the framework of Policy Space Response Oracles (PSRO), to automate the generation of an offline opponent model via iterative game-theoretic reasoning and population-based training. We propose using solution concepts based on bargaining theory to build up an opponent mixture, which we find identifying profiles that are near the Pareto frontier. Then GenBR keeps updating an online opponent model and reacts against it during gameplay. We conduct behavioral studies where human participants negotiate with our agents in Deal-or-No-Deal, a class of bilateral bargaining games. Search with generative modeling finds stronger policies during both training time and test time, enables online Bayesian co-player prediction, and can produce agents that achieve comparable social welfare and Nash bargaining score negotiating with humans as humans trading among themselves.
2712: Viral Marketing and Convergence Properties in Generalised Voter Model
Authors: Abhiram Manohara, Ahad N. Zehmakan
Location: Montreal | Day: August 19th | Time: 11:30 | Session: GTEP: Computational social choice (1/2)
Show Abstract
Consider a social network where each node (user) is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of connections, individuals with no initial opinion, and users who are reluctant to update. To address these issues, we introduce a generalisation of the voter model.

We study the problem of selecting a set of seed blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP-hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms.

We also prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the convergence period (size of the stationary configuration) is bounded by the highest common divisor of cycle lengths in the network.
2719: Hybrid Mesh-Gaussian Representation for Efficient Indoor Scene Reconstruction
Authors: Binxiao Huang, Zhihao Li, Shiyong Liu, Xiao Tang, Jiajun Tang, Jiaqi Lin, Yuxin Cheng, Zhenyu Chen, Xiaofei Wu, Ngai Wong
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Computer Vision (3/3)
Show Abstract
3D Gaussian splatting (3DGS) has demonstrated exceptional performance in image-based 3D reconstruction and real-time rendering. However, regions with complex textures require numerous Gaussians to capture significant color variations accurately, leading to inefficiencies in rendering speed. To address this challenge, we introduce a hybrid representation for indoor scenes that combines 3DGS with textured meshes. Our approach uses textured meshes to handle texture-rich flat areas, while retaining Gaussians to model intricate geometries. The proposed method begins by pruning and refining the extracted mesh to eliminate geometrically complex regions. We then employ a joint optimization for 3DGS and mesh, incorporating a warm-up strategy and transmittance-aware supervision to balance their contributions seamlessly.Extensive experiments demonstrate that the hybrid representation maintains comparable rendering quality and achieves superior frames per second FPS with fewer Gaussian primitives.
2761: Accelerating Adversarial Training on Under-Utilized GPU
Authors: Zhuoxin Zhan, Ke Wang, Pulei Xiong
Location: Montreal | Day: August 21st | Time: 10:00 | Session: Machine Learning (4/4)
Show Abstract
Deep neural networks are vulnerable to adversarial attacks and adversarial training has been proposed to defend against such attacks by adaptively generating attacks, i.e., adversarial examples, during training. However, adversarial training is significantly slower than traditional training due to the search for worst attacks for each minibatch. To speed up adversarial training, existing work has considered a subset of a minibatch for generating attacks and reduced the steps in the search for attacks. We propose a novel adversarial training acceleration method, called AttackRider, by exploring under-utilized GPU hardware to reduce the number of calls to attack generation without increasing the time of each call. We characterize the extent of under-utilization of GPU for given GPU and model size, hence the potential for speedup, and present the application scenarios where this opportunity exists. The results on various machine learning tasks and datasets show that AttackRider can speed up state-of-the-art adversarial training algorithms with comparable robust accuracy. The source code of AttackRider is available at https://github.com/zxzhan/AttackRider.
2816: Rethinking Graph Contrastive Learning Through Relative Similarity Preservation
Authors: Zhiyuan Ning, Pengfei Wang, Ziyue Qiao, Pengyang Wang, Yuanchun Zhou
Location: Montreal | Day: August 21st | Time: 15:00 | Session: DM: Graph Data Mining
Show Abstract
Graph contrastive learning (GCL) has achieved remarkable success by following the computer vision paradigm of preserving absolute similarity between augmented views. However, this approach faces fundamental challenges in graphs due to their discrete, non-Euclidean nature — view generation often breaks semantic validity and similarity verification becomes unreliable. Through analyzing 11 real-world graphs, we discover a universal pattern transcending the homophily-heterophily dichotomy: label consistency systematically diminishes as structural distance increases, manifesting as smooth decay in homophily graphs and oscillatory decay in heterophily graphs. We establish theoretical guarantees for this pattern through random walk theory, proving label distribution convergence and characterizing the mechanisms behind different decay behaviors. This discovery reveals that graphs naturally encode relative similarity patterns, where structurally closer nodes exhibit collectively stronger semantic relationships. Leveraging this insight, we propose RELGCL, a novel GCL framework with complementary pairwise and listwise implementations that preserve these inherent patterns through collective similarity objectives. Extensive experiments demonstrate that our method consistently outperforms 20 existing approaches across both homophily and heterophily graphs, validating the effectiveness of leveraging natural relative similarity over artificial absolute similarity.
2863: Learning from Logical Constraints with Lower- and Upper-Bound Arithmetic Circuits
Authors: Lucile Dierckx, Alexandre Dubray, Siegfried Nijssen
Location: Montreal | Day: August 21st | Time: 10:00 | Session: Machine Learning (4/4)
Show Abstract
An important class of neuro-symbolic (NeSy) methods relies on knowledge compilation (KC) techniques to transform logical constraints into a differentiable exact arithmetic circuit (AC) that represents all models of a logical formula. However, given the complexity of KC, compiling such exact circuits can be infeasible. Previous works in such cases proposed to compile a circuit for a subset of models. In this work, we will show that gradients calculated on a subset of models can be very far from true gradients. We propose a new framework that calculates gradients based on compiling logical constraints partially in not only a lower-bound circuit but also an upper-bound circuit. We prove that from this pair of ACs, gradients that are within a bounded distance from true gradients can be calculated. Our experiments show that adding the upper-bound AC also helps the learning process in practice, allowing for similar or better generalisation than working solely with fully compiled ACs, even with less than 150 seconds of partial compilation.
2982: DiffFERV: Diffusion-based Facial Editing of Real Videos
Authors: Xiangyi Chen, Han Xue, Li Song
Location: Montreal | Day: August 19th | Time: 15:00 | Session: CV: Difusion models
Show Abstract
Face video editing presents significant challenges, requiring precise preservation of facial identity, temporal consistency, and background details. Existing methods encounter three major challenges: difficulty in achieving accurate facial reconstruction, struggles with challenging real-world videos and reliance on a crop-edit-stitch paradigm that confines editing to localized facial regions. In response, we introduce DiffFERV, a novel diffusion-based framework for realistic face video editing that addresses these limitations through three core contributions. (1) A specialization stage that extends large Text-to-Image (T2I) models’ general prior to faces while retaining their broad generative capabilities. This enables robust performance on non-aligned and challenging face images. (2) Temporal modeling, implemented through two distinct attention mechanisms, complements the specialization stage to ensure joint and temporally consistent processing of video frames. (3) Finally, we present a holistic editing pipeline and the concept of preservation features, which leverages our model’s enhanced priors and temporal mechanisms to achieve faithful edits of entire video frames without the need for cropping, excelling even in real-world scenarios. Extensive experiments demonstrate that DiffFERV achieves state-of-the-art performance in both reconstruction and editing tasks.
2996: On Middle Grounds for Preference Statements
Authors: Anne-Marie George, Ana Ozaki
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Knowledge Representation and Reasoning (3/4)
Show Abstract
In group decisions or deliberations, stakeholders are often confronted with conflicting opinions. We investigate a logic-based way of expressing such opinions and a formal general notion of a middle ground between stakeholders. Inspired by the literature on preferences with hierarchical and lexicographic models, we instantiate our general framework to the case where stakeholders express their opinions using preference statements of the form ‘I prefer ‘a’ to ‘b’’, where ‘a’ and ‘b’ are alternatives expressed over some attributes, e.g., in a trolley problem, one can express I prefer to save 1 adult and 1 child to 2 adults (and 0 children). We prove theoretical results on the existence and uniqueness of middle grounds. In particular, we show that, for preference statements, middle grounds may not exist and may not be unique. We provide algorithms for deciding the existence and finding middle grounds.
3008: Interpretable DNFs
Authors: Martin C. Cooper, Imane Bousdira, Clément Carbonnel
Location: Montreal | Day: August 21st | Time: 10:00 | Session: ML: Explainable/Interpretable machine learning
Show Abstract
A classifier is considered interpretable if each of its decisions has an explanation which is small enough to be easily understood by a human user. A DNF can be seen as a binary classifier kappa over boolean domains. The size of an explanation of a positive decision taken by a DNF kappa is bounded by the size of the terms in kappa, since we can explain a positive decision by giving a term of kappa that evaluates to true. Since both positive and negative decisions must be explained, we consider that interpretable DNFs are those kappa for which both kappa and its complement can be expressed as DNFs composed of terms of bounded size. In this paper, we investigate the family of k-DNFs whose complements can also be expressed as k-DNFs. We compare two such families, namely depth-k decision trees and nested k-DNFs, a novel family of models. Experimental evidence indicates that nested k-DNFs are an interesting alternative to decision trees in terms of interpretability and accuracy.
3033: Relational Decomposition for Program Synthesis
Authors: Céline Hocquette, Andrew Cropper
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Knowledge Representation and Reasoning (2/4)
Show Abstract
We introduce a relational approach to program synthesis. The key idea is to decompose synthesis tasks into simpler relational synthesis subtasks. Specifically, our representation decomposes a training input-output example into sets of input and output facts respectively. We then learn relations between the input and output facts. We demonstrate our approach using an off-the-shelf inductive logic programming (ILP) system on four challenging synthesis datasets. Our results show that (i) our representation can outperform a standard one, and (ii) an off-the-shelf ILP system with our representation can outperform domain-specific approaches.
3049: Wisdom from Diversity: Bias Mitigation Through Hybrid Human-LLM Crowds
Authors: Axel Abels, Tom Lenaerts
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: AI Ethics, Trust, Fairness (3/3)
Show Abstract
Despite their performance, large language models (LLMs) can inadvertently perpetuate biases found in the data they are trained on. By analyzing LLM responses to bias-eliciting headlines, we find that these models often mirror human biases. To address this, we explore crowd-based strategies for mitigating bias through response aggregation. We first demonstrate that simply averaging responses from multiple LLMs, intended to leverage the “wisdom of the crowd", can exacerbate existing biases due to the limited diversity within LLM crowds. In contrast, we show that locally weighted aggregation methods more effectively leverage the wisdom of the LLM crowd, achieving both bias mitigation and improved accuracy. Finally, recognizing the complementary strengths of LLMs (accuracy) and humans (diversity), we demonstrate that hybrid crowds containing both significantly enhance performance and further reduce biases across ethnic and gender-related contexts.
3061: Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives
Authors: Giuseppe De Giacomo, Yong Li, Sven Schewe, Christoph Weinhuber, Pian Yu
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Planning and Scheduling (1/5)
Show Abstract
The temporal logics LTLf+ and PPLTL+ have recently been introduced to express objectives over infinite traces. These logics are appealing because they match the expressive power of LTL on infinite traces while enabling efficient DFA-based techniques, which have been crucial to the scalability of reactive synthesis and adversarial planning in LTLf and PPLTL over finite traces. In this paper, we demonstrate that these logics are also highly effective in the context of MDPs. Introducing a technique tailored for probabilistic systems, we leverage the benefits of efficient DFA-based methods and compositionality. This approach is simpler than its nonprobabilistic counterparts in reactive synthesis and adversarial planning, as it accommodates a controlled form of nondeterminism ("good for MDPs") in the automata when transitioning from finite to infinite traces. Notably, by exploiting compositionality, our solution is both implementation-friendly and well-suited for straightforward symbolic implementations.
3074: LTLf+ and PPLTL+: Extending LTLf and PPLTL to Infinite Traces
Authors: Benjamin Aminof, Giuseppe De Giacomo, Sasha Rubin, Moshe Y. Vardi
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Planning and Scheduling (1/5)
Show Abstract
We study two logics, LTLf+ and PPLTL+, to express properties of infinite traces, that are based on the linear-time temporal logics LTLf and PPLTL on finite traces. LTLf+/PPLTL+ use levels of Manna and Pnueli’s LTL safety-progress hierarchy, and thus have the same expressive power as LTL. However, they also retain a crucial characteristic of reactive synthesis for the base logics: the game arena for strategy extraction can be derived from deterministic finite automata (DFA). Consequently, these logics circumvent the notorious difficulties associated with determinizing infinite trace automata, typical of LTL synthesis. We present optimal DFA-based technique for solving reactive synthesis for LTLf+ and PPLTL+. Additionally, we adapt these algorithms to optimally solve satisfiability and model-checking for these two logics.
3078: Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs
Authors: Maris F. L. Galesloot, Roman Andriushchenko, Milan Ceska, Sebastian Junges, Nils Jansen
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Planning and Scheduling (5/5)
Show Abstract
Partially observable Markov decision processes (POMDPs) model specific environments in sequential decision-making under uncertainty. Critically, optimal policies for POMDPs may not be robust against perturbations in the environment. Hidden-model POMDPs (HM-POMDPs) capture sets of different environment models, that is, POMDPs with a shared action and observation space. The intuition is that the true model is hidden among a set of potential models, and it is unknown which model will be the environment at execution time. A policy is robust for a given HM-POMDP if it achieves sufficient performance for each of its POMDPs. We compute such robust policies by combining two orthogonal techniques: (1) a deductive formal verification technique that supports tractable robust policy evaluation by computing a worst-case POMDP within the HM-POMDP, and (2) subgradient ascent to optimize the candidate policy for a worst-case POMDP. The empirical evaluation shows that, compared to various baselines, our approach (1) produces policies that are more robust and generalize better to unseen POMDPs, and (2) scales to HM-POMDPs that consist of over a hundred thousand environments.
3096: Responsibility Anticipation and Attribution in LTLf
Authors: Giuseppe De Giacomo, Emiliano Lorini, Timothy Parker, Gianmarco Parretti
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Agent-based and Multi-agent Systems (2/3)
Show Abstract
Responsibility is one of the key notions in machine ethics and in the area of autonomous systems. It is a multi-faceted notion involving counterfactual reasoning about actions and strategies. In this paper, we study different variants of responsibility for LTLf outcomes based on strategic reasoning. We show a connection with notions in reactive synthesis, including the synthesis of winning, dominant, and best-effort strategies. This connection provides a strong computational grounding of responsibility, allowing us to characterize the worst-case computa- tional complexity and devise sound, complete, and optimal algorithms for anticipating and attributing responsibility.
3108: MsRAG: Knowledge Augumented Image Captioning with Object-level Multi-source RAG
Authors: Yuming Qiao, Yuechen Wang, Dan Meng, Haonan Lu, Zhenyu Yang, Xudong Zhang
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Machine Learning (2/4)
Show Abstract
Language-Visual Large Models (LVLMs) have made significant strides in enhancing visual understanding capabilities. However, these models often struggle with knowledge-based visual tasks due to constrains in their pre-training data scope and timeliness. Existing Retrieval-Augmented Generation (RAG) methods can effectively solve the problem but primarily rely on user queries, limiting their applicability in scenarios without explicit language input. To overcome these challenges, we introduce MsRAG, a knowledge-augmented captioning framework designed to effectively retrieve and utilize external real-world knowledge, particularly in the absence of user queries, and perform dense captioning for subjects. MsRAG comprises three key components: (1) Parallel Visual Search Module. It retrieves fine-grained object-level knowledge using both online visual search engines and offline domain-knowledge databases, enhancing the robustness and richness of retrieved information. (2) Prompt Templates Pool. The prompt pool dynamically assigns appropriate prompts based on retrieved information, optimizing LVLMs’ ability to leverage relevant data under complex RAG conditions. (3) Visual-RAG Alignment Module, which employs a novel visual prompting method to bridge the modality gap between textual RAG content and corresponding visual objects, enabling precise alignment of visual elements with their text-format RAG content. To validate the effectiveness of MsRAG, we conducted a series of qualitative and quantitative experiments. The evaluation results demonstrate the superiority of MsRAG over other methods.
3128: Beyond the Known: Decision Making with Counterfactual Reasoning Decision Transformer
Authors: Minh Hoang Nguyen, Linh Le Pham Van, Thommen George Karimpanal, Sunil Gupta, Hung Le
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Machine Learning (1/4)
Show Abstract
Decision Transformers (DT) play a crucial role in modern reinforcement learning, leveraging offline datasets to achieve impressive results across various domains. However, DT requires high-quality, comprehensive data to perform optimally. In real-world applications, the lack of training data and the scarcity of optimal behaviours make training on offline datasets challenging, as suboptimal data can hinder performance. To address this, we propose the Counterfactual Reasoning Decision Transformer (CRDT), a novel framework inspired by counterfactual reasoning. CRDT enhances DT’s ability to reason beyond known data by generating and utilizing counterfactual experiences, enabling improved decision-making in unseen scenarios. Experiments across Atari and D4RL benchmarks, including scenarios with limited data and altered dynamics, demonstrate that CRDT outperforms conventional DT approaches. Additionally, reasoning counterfactually allows the DT agent to obtain stitching abilities, combining suboptimal trajectories, without architectural modifications. These results highlight the potential of counterfactual reasoning to enhance reinforcement learning agents’ performance and generalization capabilities.
3271: LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming
Authors: Sicheol Sung, Aditi, Dogyu Kim, Yo-Sub Han, Sang-Ki Ko
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: MTA: Software engineering
Show Abstract
Automated Test Case Generation (ATCG) is crucial for evaluating software reliability, particularly in competitive programming where robust algorithm assessments depend on diverse and accurate test cases. However, existing ATCG methods often fail to meet complex specifications or generate effective corner cases, limiting their utility. In this work, we introduce Context-Free Grammars with Counters (CCFGs), a formalism that captures both syntactic and semantic structures in input specifications. Using a fine-tuned CodeT5 model, we translate natural language input specifications into CCFGs, enabling the systematic generation of high-quality test cases. Experiments on the CodeContests dataset demonstrate that CCFG-based test cases outperform baseline methods in identifying incorrect algorithms, achieving significant gains in validity and effectiveness. Our approach provides a scalable and reliable grammar-driven framework for enhancing automated competitive programming evaluations.
3331: AdvGrasp: Adversarial Attacks on Robotic Grasping from a Physical Perspective
Authors: Xiaofei Wang, Mingliang Han, Tianyu Hao, Cegang Li, Yunbo Zhao, Keke Tang
Location: Montreal | Day: August 21st | Time: 10:00 | Session: AI Ethics, Trust, Fairness (2/3)
Show Abstract
Adversarial attacks on robotic grasping provide valuable insights into evaluating and improving the robustness of these systems. Unlike studies that focus solely on neural network predictions while overlooking the physical principles of grasping, this paper introduces AdvGrasp, a framework for adversarial attacks on robotic grasping from a physical perspective. Specifically, AdvGrasp targets two core aspects: lift capability, which evaluates the ability to lift objects against gravity, and grasp stability, which assesses resistance to external disturbances. By deforming the object’s shape to increase gravitational torque and reduce stability margin in the wrench space, our method systematically degrades these two key grasping metrics, generating adversarial objects that compromise grasp performance. Extensive experiments across diverse scenarios validate the effectiveness of AdvGrasp, while real-world validations demonstrate its robustness and practical applicability.
3368: Reasoning About Causal Knowledge in Nondeterministic Domains
Authors: Shakil M. Khan, Yves Lespérance, Maryam Rostamigiv
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Knowledge Representation and Reasoning (3/4)
Show Abstract
Reasoning about causality and agent causal knowledge is critical for effective decision-making and planning in multi-agent contexts. Previous work in the area generally assumes that the domain is deterministic, but in fact many agents operate in nondeterministic domains where the outcome of their actions depends on unpredictable environment reactions. In this paper, we propose a situation calculus-based framework for reasoning about causal knowledge in nondeterministic domains. In such domains, the agent may not know the environment reactions to her actions and their outcomes, and may be uncertain about which actions caused a condition to come about. But she can perform sensing actions to acquire knowledge about the state and use it to gain knowledge about causes. Our formalization recognizes sensing actions as causes of both physical and epistemic effects. We also examine how regression can be used to reason about causal knowledge.
3373: Inference of Human-derived Specifications of Object Placement via Demonstration
Authors: Alex Cuellar, Ho Chit Siu, Julie A Shah
Location: Montreal | Day: August 21st | Time: 10:00 | Session: Humans and AI
Show Abstract
As robots’ manipulation capabilities improve for pick-and-place tasks (e.g., object packing, sorting, and kitting), methods focused on understanding human-acceptable object configurations remain limited expressively with regard to capturing spatial relationships important to humans. To advance robotic understanding of human rules for object arrangement, we introduce positionally-augmented RCC (PARCC), a formal logic framework based on region connection calculus (RCC) for describing the relative position of objects in space. Additionally, we introduce an inference algorithm for learning PARCC specifications via demonstrations. Finally, we present the results from a human study, which demonstrate our framework’s ability to capture a human’s intended specification and the benefits of learning from demonstration approaches over human-provided specifications.
3385: Optimal Transport on Categorical Data for Conterfactuals Using Compositional Data and Dirichlet Transport
Authors: Agathe Fernandes Machado, Ewen Gallic, Arthur Charpentier
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Machine Learning (1/4)
Show Abstract
Recently, optimal transport-based approaches have gained attention for deriving counterfactuals, e.g., to quantify algorithmic discrimination. However, in the general multivariate setting, these methods are often opaque and difficult to interpret. To address this, alternative methodologies have been proposed, using causal graphs combined with iterative quantile regressions or sequential transport to examine fairness at the individual level, often referred to as "counterfactual fairness." Despite these advancements, transporting categorical variables remains a significant challenge in practical applications with real datasets. In this paper, we propose a novel approach to address this issue. Our method involves (1) converting categorical variables into compositional data and (2) transporting these compositions within the probabilistic simplex of the Euclidean space. We demonstrate the applicability and effectiveness of this approach through an illustration on real-world data, and discuss limitations.
3388: KIPPO: Koopman-Inspired Proximal Policy Optimization
Authors: Andrei Cozma, Landon Harris, Hairong Qi
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
Reinforcement Learning (RL) has made significant strides in various domains, and policy gradient methods like Proximal Policy Optimization (PPO) have gained popularity due to their balance in performance, training stability, and computational efficiency. These methods directly optimize policies through gradient-based updates. However, developing effective control policies for environments with complex and non-linear dynamics remains a challenge. High variance in gradient estimates and non-convex optimization landscapes often lead to unstable learning trajectories. Koopman Operator Theory has emerged as a powerful framework for studying non-linear systems through an infinite-dimensional linear operator that acts on a higher-dimensional space of measurement functions. In contrast with their non-linear counterparts, linear systems are simpler, more predictable, and easier to analyze. In this paper, we present Koopman-Inspired Proximal Policy Optimization (KIPPO), which learns an approximately linear latent-space representation of the underlying system’s dynamics while retaining essential features for effective policy learning. This is achieved through a Koopman-approximation auxiliary network that can be added to the baseline policy optimization algorithms without altering the architecture of the core policy or value function. Extensive experimental results demonstrate consistent improvements over the PPO baseline with 6–60% increased performance while reducing variability by up to 91% when evaluated on various continuous control tasks.
3405: Improved MMS Approximations for Few Agent Types
Authors: Parnian Shahkar, Jugal Garg
Location: Montreal | Day: August 21st | Time: 11:30 | Session: GTEP: Fair division
Show Abstract
We study fair division of indivisible goods under the maximin share (MMS) fairness criterion in settings where agents are grouped into a small number of types, with agents within each type having identical valuations. For the special case of a single type, an exact MMS allocation is always guaranteed to exist. However, for two or more distinct agent types, exact MMS allocations do not always exist, shifting the focus to establishing the existence of approximate-MMS allocations. A series of works over the last decade has resulted in the best-known approximation guarantee of 3/4 + 3/3836.

In this paper, we improve the approximation guarantees for settings where agents are grouped into two or three types, a scenario that arises in many practical settings. Specifically, we present novel algorithms that guarantee a 4/5-MMS allocation for two agent types and a 16/21-MMS allocation for three agent types. Our approach leverages the MMS partition of the majority type and adapts it to provide improved fairness guarantees for all types.
3408: On the Discrimination and Consistency for Exemplar-Free Class Incremental Learning
Authors: Tianqi Wang, Jingcai Guo, Depeng Li, Zhi Chen
Location: Montreal | Day: August 21st | Time: 10:00 | Session: Machine Learning (4/4)
Show Abstract
Exemplar-free class incremental learning (EF-CIL) is a nontrivial task that requires continuously enriching model capability with new classes while maintaining previously learned knowledge without storing and replaying any old class exemplars. An emerging theory-guided framework for CIL trains task-specific models for a shared network, shifting the pressure of forgetting to task-id prediction. In EF-CIL, task-id prediction is more challenging due to the lack of inter-task interaction (e.g., replays of exemplars). To address this issue, we conduct a theoretical analysis of the importance and feasibility of preserving a discriminative and consistent feature space, upon which we propose a novel method termed DCNet. Concretely, it progressively maps class representations into a hyperspherical space, in which different classes are orthogonally distributed to achieve ample inter-class separation. Meanwhile, it also introduces compensatory training to adaptively adjust supervision intensity, thereby aligning the degree of intra-class aggregation. Extensive experiments and theoretical analysis verified the superiority of DCNet. Code is available at https://github.com/Tianqi-Wang1/DCNet.
3409: Situational-Constrained Sequential Resources Allocation via Reinforcement Learning
Authors: Libo Zhang, Yang Chen, Toru Takisaka, Kaiqi Zhao, Weidong Li, Jiamou Liu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Machine Learning (1/4)
Show 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.
3441: LEKA: LLM-Enhanced Knowledge Augmentation
Authors: Xinhao Zhang, Jinghan Zhang, Fengran Mo, Dongjie Wang, Yanjie Fu, Kunpeng Liu
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Large Language Models
Show Abstract
Humans excel in analogical learning and knowledge transfer and, more importantly, possess a unique understanding of identifying appropriate sources of knowledge. From a model’s perspective, this presents a unique challenge. If models could autonomously retrieve knowledge relevant for transfer or decision-making to solve problems, they would transition from passively acquiring to actively accessing and learning from knowledge. However, filling models with knowledge is relatively straightforward—it simply requires more training and accessible knowledge bases. The more complex task is teaching models about which knowledge can be analogized and transferred. Therefore, we design a knowledge augmentation method, LEKA, for knowledge transfer that actively searches for suitable knowledge sources that can enrich the target domain’s knowledge. This LEKA method extracts key information from the target domain’s textual information, retrieves pertinent data from external data libraries, and harmonizes retrieved data with the target domain data in feature space and marginal probability measures. We validate the effectiveness of our approach through extensive experiments across various domains and demonstrate significant improvements over traditional methods in automating data alignment and optimizing transfer learning outcomes.
3445: New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets
Authors: Siddharth Prasad, Ellen Vitercik, Maria-Florina Balcan, Tuomas Sandholm
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Constraint Satisfaction and Optimization (1/3)
Show Abstract
Sequence-independent lifting is a procedure for strengthening valid inequalities of an integer program. We generalize the sequence-independent lifting method of Gu, Nemhauser, and Savelsbergh (GNS lifting) for cover inequalities and correct an error in their proposed generalization. We obtain a new sequence-independent lifting technique—piecewise-constant (PC) lifting—with a number of important properties. We derive a broad set of sufficient conditions under which PC lifting yields facets—the first characterization of facet-defining sequence-independent liftings that are efficiently computable from the underlying cover. Finally, we demonstrate via experiments that PC lifting can be a useful alternative to GNS lifting. We test PC lifting atop a number of novel cover inequality generation routines, which prove to be effective in experiments with CPLEX. PC lifting delivers strong numerical properties making it practically relevant for integer programming solvers.
3456: Distance Preservation Games
Authors: Haris Aziz, Hau Chan, Patrick Lederer, Shivika Narang, Toby Walsh
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Game Theory
Show Abstract
We introduce and analyze distance preservation games (DPGs). In DPGs, agents express ideal distances to other agents and need to choose locations in the unit interval while preserving their ideal distances as closely as possible. We analyze the existence and computation of location profiles that are jump stable (i.e., no agent can benefit by moving to another location) or welfare optimal for DPGs, respectively. Specifically, we prove that there are DPGs without jump stable location profiles and identify important cases where such outcomes always exist and can be computed efficiently. Similarly, we show that finding welfare optimal location profiles is NP-complete and present approximation algorithms for finding solutions with social welfare close to optimal. Finally, we prove that DPGs have a price of anarchy of at most 2.
3496: ASCENT-ViT: Attention-based Scale-aware Concept Learning Framework for Enhanced Alignment in Vision Transformers
Authors: Sanchit Sinha, Guangzhi Xiong, Aidong Zhang
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: ETF: Explainability and interpretability
Show Abstract
As Vision Transformers (ViTs) are increasingly adopted in sensitive vision applications, there is a growing demand for improved interpretability. This has led to efforts to forward-align these models with carefully annotated abstract, human-understandable semantic entities – concepts. Concepts provide global rationales to the model predictions and can be quickly understood/intervened on by domain experts. Most current research focuses on designing model-agnostic, plug-and-play generic concept-based explainability modules that do not incorporate the inner workings of foundation models (e.g., inductive biases, scale invariance, etc.) during training. To alleviate this issue for ViTs, in this paper, we propose ASCENT-ViT, an attention-based, concept learning framework that effectively composes scale and position-aware representations from multiscale feature pyramids and ViT patch representations, respectively. Further, these representations are aligned with concept annotations through attention matrices – which incorporate spatial and global (semantic) concepts. ASCENT-ViT can be utilized as a classification head on top of standard ViT backbones for improved predictive performance and accurate and robust concept explanations as demonstrated on five datasets, including three widely used benchmarks (CUB, Pascal APY, Concept-MNIST) and two real-world datasets (AWA2, KITS). An appendix of the paper with more comprehensive results is available at https://arxiv.org/abs/2501.09221.
3603: STLSP: Integrating Structure and Text with Large Language Models for Link Sign Prediction of Networks
Authors: Lijia Ma, Haoyang Fu, Zhijie Cao, Xiongnan Jin, Qiuzhen Lin, Jianqiang Li
Location: Montreal | Day: August 21st | Time: 15:00 | Session: DM: Graph Data Mining
Show Abstract
Link Sign Prediction (LSP) in signed networks is a critical task with applications in recommendation systems, community detection, and social network analysis. Existing methods primarily rely on graph neural networks to exploit structural information, often neglecting the valuable insights from edge-level textual data. Furthermore, utilizing large language models (LLMs) for LSP faces challenges in reliability and interpreting graph structures. To address these issues, we propose a novel STLSP framework that integrates signed networks’ \underline{S}tructural and \underline{T}extual information with LLMs for the \underline{LSP} task. STLSP leverages structural balance theory to generate node embeddings that capture positive and negative relationships. These embeddings are transformed into natural language representations through clustering techniques, allowing LLMs to utilize the structural context fully. By integrating these representations with edge text, STLSP improves the accuracy and reliability of the LSP task. Extensive experiments conducted on five real-world datasets demonstrate that STLSP outperformed state-of-the-art baselines, achieving an 8.7% improvement in terms of accuracy. Moreover, STLSP shows robust performance across various LLMs, making it adaptable to different computational environments. The code and data are publically available at https://github.com/sss483/STLSP.
3693: Beyond Symmetry in Repeated Games with Restarts
Authors: Henry Fleischmann, Kiriaki Fragkia, Ratip Emin Berker
Location: Montreal | Day: August 21st | Time: 10:00 | Session: GTEP: Noncooperative games
Show Abstract
Infinitely repeated games support equilibrium concepts beyond those present in one-shot games (e.g., cooperation in the prisoner’s dilemma). Nonetheless, repeated games fail to capture our real-world intuition for settings with many anonymous agents interacting in pairs. Repeated games with restarts, introduced by Berker and Conitzer, address this concern by giving players the option to restart the game with someone new whenever their partner deviates from an agreed-upon sequence of actions. In their work, they studied symmetric games with symmetric strategies. We significantly extend these results, introducing and analyzing more general notions of equilibria in asymmetric games with restarts. We characterize which goal strategies players can be incentivized to play in equilibrium, and we consider the computational problem of finding such sequences of actions with minimal cost for the agents. We show that this problem is NP-hard in general. However, when the goal sequence maximizes social welfare, we give a pseudo-polynomial time algorithm.
3726: ShortcutProbe: Probing Prediction Shortcuts for Learning Robust Models
Authors: Guangtao Zheng, Wenqian Ye, Aidong Zhang
Location: Montreal | Day: August 21st | Time: 10:00 | Session: Machine Learning (4/4)
Show Abstract
Deep learning models often achieve high performance by inadvertently learning spurious correlations between targets and non-essential features. For example, an image classifier may identify an object via its background that spuriously correlates with it. This prediction behavior, known as spurious bias, severely degrades model performance on data that lacks the learned spurious correlations. Existing methods on spurious bias mitigation typically require a variety of data groups with spurious correlation annotations called group labels. However, group labels require costly human annotations and often fail to capture subtle spurious biases such as relying on specific pixels for predictions. In this paper, we propose a novel post hoc spurious bias mitigation framework without requiring group labels. Our framework, termed ShortcutProbe, identifies prediction shortcuts that reflect potential non-robustness in predictions in a given model’s latent space. The model is then retrained to be invariant to the identified prediction shortcuts for improved robustness. We theoretically analyze the effectiveness of the framework and empirically demonstrate that it is an efficient and practical tool for improving a model’s robustness to spurious bias on diverse datasets.
3731: Approximated Behavioral Metric-based State Projection for Federated Reinforcement Learning
Authors: Zengxia Guo, Bohui An, Zhongqi Lu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Federated Learning
Show Abstract
Federated reinforcement learning (FRL) methods usually share the encrypted local state or policy information and help each client to learn from others while preserving everyone’s privacy. In this work, we propose that sharing the approximated behavior metric-based state projection function is a promising way to enhance the performance of FRL and concurrently provides an effective protection of sensitive information. We introduce FedRAG, a FRL framework to learn a computationally practical projection function of states for each client and aggregating the parameters of projection functions at a central server. The FedRAG approach shares no sensitive task-specific information, yet provides information gain for each client. We conduct extensive experiments on the DeepMind Control Suite to demonstrate insightful results.
3743: GarmentDiffusion: 3D Garment Sewing Pattern Generation with Multimodal Diffusion Transformers
Authors: Xinyu Li, Qi Yao, Yuanda Wang
Location: Montreal | Day: August 19th | Time: 15:00 | Session: CV: Difusion models
Show Abstract
Garment sewing patterns are fundamental design elements that bridge the gap between design concepts and practical manufacturing. The generative modeling of sewing patterns is crucial for creating diversified garments. However, existing approaches are limited either by reliance on a single input modality or by suboptimal generation efficiency. In this work, we present GarmentDiffusion, a new generative model capable of producing centimeter-precise, vectorized 3D sewing patterns from multimodal inputs (text, image, and incomplete sewing pattern). Our method efficiently encodes 3D sewing pattern parameters into compact edge token representations, achieving a sequence length that is 10 times shorter than that of the autoregressive SewingGPT in DressCode. By employing a diffusion transformer, we simultaneously denoise all edge tokens along the temporal axis, while maintaining a constant number of denoising steps regardless of dataset-specific edge and panel statistics. With all combination of designs of our model, the sewing pattern generation speed is accelerated by 100 times compared to SewingGPT. We achieve new state-of-the-art results on DressCodeData, as well as on the largest sewing pattern dataset, namely GarmentCodeData. The project website is available at https://shenfu-research.github.io/Garment-Diffusion.
3756: Learning Advanced Self-Attention for Linear Transformers in the Singular Value Domain
Authors: Hyowon Wi, Jeongwhan Choi, Noseong Park
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Large Language Models
Show Abstract
Transformers have demonstrated remarkable performance across diverse domains. The key component of Transformers is self-attention, which learns the relationship between any two tokens in the input sequence. Recent studies have revealed that the self-attention can be understood as a normalized adjacency matrix of a graph. Notably, from the perspective of graph signal processing (GSP), the self-attention can be equivalently defined as a simple graph filter, applying GSP using the value vector as the signal. However, the self-attention is a graph filter defined with only the first order of the polynomial matrix, and acts as a low-pass filter preventing the effective leverage of various frequency information. Consequently, existing self-attention mechanisms are designed in a rather simplified manner. Therefore, we propose a novel method, called Attentive Graph Filter (AGF), interpreting the self-attention as learning the graph filter in the singular value domain from the perspective of graph signal processing for directed graphs with the linear complexity w.r.t. the input length. In our experiments, we demonstrate that AGF achieves state-of-the-art performance on various tasks, including Long Range Arena benchmark and time series classification. Code is available at https://github.com/hyowonwi/agf.
3758: Automated Superscalar Processor Design by Learning Data Dependencies
Authors: Shuyao Cheng, Rui Zhang, Wenkai He, Pengwei Jin, Chongxiao Li, Zidong Du, Xing Hu, Yifan Hao, Guanglin Xu, Yuanbo Wen, Ling Li, Qi Guo, Yunji Chen
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Machine Learning (2/4)
Show Abstract
Automated processor design, which can significantly reduce human efforts and accelerate design cycles, has received considerable attention. While recent advancements have automatically designed single-cycle processors that execute one instruction per cycle, their performance cannot compete with modern superscalar processors that execute multiple instructions per cycle. Previous methods fail on superscalar processor design because they cannot address inter-instruction data dependencies, leading to inefficient sequential instruction execution.

This paper proposes a novel approach to automatically designing superscalar processors using a hardware-friendly model called the Stateful Binary Speculation Diagram (State-BSD). We observe that processor parallelism can be enhanced through on-the-fly inter-instruction dependent data predictors, reusing the processor’s internal states to learn the data dependency. To meet the challenge of both hardware-resource limitation and design functional correctness, State-BSD consists of two components: 1) a lightweight state-selector trained by simulated annealing method to detect the most reusable processor states and store them in a small buffer; and 2) a highly precise state-speculator trained by BSD expansion method to predict the inter-instruction dependent data using the selected states. It is the first work to achieve the automated superscalar processor design, i.e. QiMeng-CPU-v2, which improves the performance by about 380x than the state-of-the-art automated design and is comparable to human-designed superscalar processors such as ARM Cortex A53.
3805: Dividing Conflicting Items Fairly
Authors: Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda
Location: Montreal | Day: August 21st | Time: 11:30 | Session: GTEP: Fair division
Show Abstract
We study the allocation of indivisible goods under conflicting constraints, represented by a graph. In this framework, vertices correspond to goods and edges correspond to conflicts between a pair of goods. Each agent is allocated an independent set in the graph. In a recent work of Kumar et al. (AAMAS, 2024), it was shown that a maximal EF1 allocation exists for interval graphs and two agents with monotone valuations. We significantly extend this result by establishing that a maximal EF1 allocation exists for any graph when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number n >= 3 of agents. All of our results for goods also apply to the allocation of chores.
3863: Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory
Authors: Huy Q. Ngo, Mingyu Guo, Hung X. Nguyen
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MTA: Security and privacy
Show Abstract
Security vulnerabilities in Windows Active Directory (AD) systems are typically modeled using an attack graph and hardening AD systems involves an iterative workflow: security teams propose an edge to remove, and IT operations teams manually review these fixes before implementing the removal. As verification requires significant manual effort, we formulate an Adaptive Path Removal Problem to minimize the number of steps in this iterative removal process. In our model, a wizard proposes an attack path in each step and presents it as a set of multiple-choice options to the IT admin. The IT admin then selects one edge from the proposed set to remove. This process continues until the target t is disconnected from source s or the number of proposed paths reaches B. The model aims to optimize the human effort by minimizing the expected number of interactions between the IT admin and the security wizard. We first prove that the problem is #P-hard. We then propose a set of solutions including an exact algorithm, an approximate algorithm, and several scalable heuristics. Our best heuristic, called DPR, can operate effectively on larger-scale graphs compared to the exact algorithm and consistently outperforms the approximate algorithm across all graphs. We verify the effectiveness of our algorithms on several synthetic AD graphs and an AD attack graph collected from a real organization.
3973: Advancing Community Detection with Graph Convolutional Neural Networks: Bridging Topological and Attributive Cohesion
Authors: Anjali de Silva, Gang Chen, Hui Ma, Seyed Mohammad Nekooei, Xingquan Zuo
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
Community detection, a vital technology for real-world applications, uncovers cohesive node groups (communities) by leveraging both topological and attribute similarities in social networks. However, existing Graph Convolutional Networks (GCNs) trained to maximize modularity often converge to suboptimal solutions. Additionally, directly using human-labeled communities for training can undermine topological cohesiveness by grouping disconnected nodes based solely on node attributes. We address these issues by proposing a novel Topological and Attributive Similarity-based Community detection (TAS-Com) method. TAS-Com introduces a novel loss function that exploits the highly effective and scalable Leiden algorithm to detect community structures with global optimal modularity. Leiden is further utilized to refine human-labeled communities to ensure connectivity within each community, enabling TAS-Com to detect community structures with desirable trade-offs between modularity and compliance with human labels. Experimental results on multiple benchmark networks confirm that TAS-Com can significantly outperform several state-of-the-art algorithms.
4070: Balancing Invariant and Specific Knowledge for Domain Generalization with Online Knowledge Distillation
Authors: Di Zhao, Jingfeng Zhang, Hongsheng Hu, Philippe Fournier-Viger, Gillian Dobbie, Yun Sing Koh
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Computer Vision (3/3)
Show Abstract
Recent research has demonstrated the effectiveness of knowledge distillation in Domain Generalization. However, existing approaches often overlook domain-specific knowledge and rely on an offline distillation strategy, limiting the effectiveness of knowledge transfer. To address these limitations, we propose Balanced Online knowLedge Distillation (BOLD). BOLD leverages a multi-domain expert teacher model, with each expert specializing in a specific source domain, enabling the student to distill both domain-invariant and domain-specific knowledge. We incorporate the Pareto optimization principle and uncertainty weighting to balance these two types of knowledge, ensuring simultaneous optimization without compromising either. Additionally, BOLD employs an online knowledge distillation strategy, allowing the teacher and student to learn concurrently. This dynamic interaction enables the teacher to adapt based on student feedback, facilitating more effective knowledge transfer. Extensive experiments on seven benchmarks demonstrate that BOLD outperforms state-of-the-art methods. Furthermore, we provide theoretical insights that highlight the importance of domain-specific knowledge and the advantages of uncertainty weighting.
4074: Dynamic Higher-Order Relations and Event-Driven Temporal Modeling for Stock Price Forecasting
Authors: Kijeong Park, Sungchul Hong, Jong-June Jeon
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: time series, sequences and signals
Show Abstract
In stock price forecasting, modeling the probabilistic dependence between stock prices within a time-series framework has remained a persistent and highly challenging area of research. We propose a novel model to explain the extreme co-movement in multivariate data with time-series dependencies. Our model incorporates a Hawkes process layer to capture abrupt co-movements, thereby enhancing the temporal representation of market dynamics. We introduce dynamic hypergraphs into our model adapting to higher-order (groupwise rather than pairwise) relationships within the stock market. Extensive experiments on real-world benchmarks demonstrate the robustness of our approach in predictive performance and portfolio stability.
4098: Counterfactual Strategies for Markov Decision Processes
Authors: Paul Kobialka, Lina Gerlach, Francesco Leofante, Erika Ábrahám, Silvia Lizeth Tapia Tarifa, Einar Broch Johnsen
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: ETF: Explainability and interpretability
Show Abstract
Counterfactuals are widely used in AI to explain how minimal changes to a model’s input can lead to a different output.
However, established methods for computing counterfactuals typically focus on one-step decision-making, and are not directly applicable to sequential decision-making tasks.
This paper fills this gap by introducing counterfactual strategies for Markov Decision Processes (MDPs).
During MDP execution, a strategy decides which of the enabled actions (with known probabilistic effects) to execute next.
Given an initial strategy that reaches an undesired outcome with a probability above some limit, we identify minimal changes to the initial strategy to reduce that probability below the limit.
We encode such counterfactual strategies as solutions to non-linear optimization problems, and further extend our encoding to synthesize diverse counterfactual strategies.
We evaluate our approach on four real-world datasets and demonstrate its practical viability in sophisticated sequential decision-making tasks.
4105: Facets in Argumentation: A Formal Approach to Argument Significance
Authors: Johannes K. Fichte, Nicolas Fröhlich, Markus Hecher, Victor Lagerkvist, Yasir Mahmood, Arne Meier, Jonathan Persson
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
Argumentation is a central subarea of Artificial Intelligence (AI) for modeling and reasoning about arguments.
The semantics of abstract argumentation frameworks (AFs) is given by sets of arguments (extensions) and conditions on the relationship between arguments, such as stable or admissible.
Today’s solvers implement tasks such as finding extensions, deciding credulously or skeptically acceptance, counting, or enumerating extensions.
While these tasks are well charted, the area between decision and counting/enumeration and fine-grained reasoning requires expensive reasoning so far.
We introduce a novel concept (facets) for reasoning between decision and enumeration.
Facets are arguments that belong to some extensions (credulous) but not to all extensions (skeptical).
They are most natural when a user aims to navigate, filter, or comprehend specific arguments, according to their needs.
We study the complexity and show that tasks involving facets are much easier than counting extensions.
Finally, we provide an implementation, and conduct experiments to demonstrate feasibility.
4158: Verifying Quantized Graph Neural Networks is PSPACE-complete
Authors: Marco Sälzer, Francois Schwarzentruber, Nicolas Troquard
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Knowledge Representation and Reasoning (3/4)
Show Abstract
In this paper, we investigate verification of quantized Graph Neural Networks (GNNs), where some fixed-width arithmetic is used to represent numbers.
We introduce the linear-constrained validity (LVP) problem for verifying GNNs properties, and provide an efficient translation from LVP instances into a logical language. We show that LVP is in PSPACE, for any reasonable activation functions. We provide a proof system. We also prove PSPACE-hardness, indicating that while reasoning about quantized GNNs is feasible, it remains generally computationally challenging.
4198: Rethinking Federated Graph Learning: A Data Condensation Perspective
Authors: Hao Zhang, Xunkai Li, Yinlin Zhu, Lianglin Hu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Federated Learning
Show Abstract
Federated graph learning is a widely recognized technique that promotes collaborative training of graph neural networks (GNNs) by multi-client graphs.However, existing approaches heavily rely on the communication of model parameters or gradients for federated optimization and fail to adequately address the data heterogeneity introduced by intricate and diverse graph distributions. Although some methods attempt to share additional messages among the server and clients to improve federated convergence during communication, they introduce significant privacy risks and increase communication overhead. To address these issues, we introduce the concept of a condensed graph as a novel optimization carrier to address FGL data heterogeneity and propose a new FGL paradigm called FedGM. Specifically, we utilize a generalized condensation graph consensus to aggregate comprehensive knowledge from distributed graphs, while minimizing communication costs and privacy risks through a single transmission of the condensed data. Extensive experiments on six public datasets consistently demonstrate the superiority of FedGM over state-of-the-art baselines, highlighting its potential for a novel FGL paradigm.
4210: A Neuro-Symbolic Framework for Sequence Classification with Relational and Temporal Knowledge
Authors: Luca Salvatore Lorello, Marco Lippi, Stefano Melacci
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: time series, sequences and signals
Show Abstract
One of the goals of neuro-symbolic artificial intelligence is to exploit background knowledge to improve the performance of learning tasks. However, most of the existing frameworks focus on the simplified scenario where knowledge does not change over time and does not cover the temporal dimension. In this work we consider the much more challenging problem of knowledge-driven sequence classification where different portions of knowledge must be employed at different timesteps, and temporal relations are available. Our extensive experimental evaluation compares multi-stage neuro-symbolic and neural-only architectures, and it is conducted on a newly-introduced benchmarking framework. Results not only demonstrate the challenging nature of this novel setting, but also highlight under-explored shortcomings of neuro-symbolic methods, representing a precious reference for future research.
4234: GATES: Cost-aware Dynamic Workflow Scheduling via Graph Attention Networks and Evolution Strategy
Authors: Ya Shen, Gang Chen, Hui Ma, Mengjie Zhang
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Planning and Scheduling (1/5)
Show Abstract
Cost-aware Dynamic Workflow Scheduling (CADWS) is a key challenge in cloud computing, focusing on devising an effective scheduling policy to efficiently schedule dynamically arriving workflow tasks, represented as Directed Acyclic Graphs (DAG), to suitable virtual machines (VMs). Deep reinforcement learning (DRL) has been widely employed for automated scheduling policy design. However, the performance of DRL is heavily influenced by the design of the problem-tailored policy network and is highly sensitive to hyperparameters and the design of reward feedback. Considering the above-mentioned issues, this study proposes a novel DRL method combining Graph Attention Networks-based policy network and Evolution Strategy, referred to as GATES. The contributions of GATES are summarized as follows: (1) GATES can capture the impact of current task scheduling on subsequent tasks by learning the topological relationships between tasks in a DAG. (2) GATES can assess the importance of each VM to the ready task, enabling it to adapt to dynamically changing VM resources. (3) Utilizing Evolution Strategy’s robustness, exploratory nature, and tolerance for delayed rewards, GATES achieves stable policy learning in CADWS. Extensive experimental results demonstrate the superiority of the proposed GATES in CADWS, outperforming several state-of-the-art algorithms. The source code is available at: https://github.com/YaShen998/GATES.
4256: Simulate, Refine and Integrate: Strategy Synthesis for Efficient SMT Solving
Authors: Bingzhe Zhou, Hannan Wang, Yuan Yao, Taolue Chen, Feng Xu, Xiaoxing Ma
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: MTA: Software engineering
Show Abstract
Satisfiability Modulo Theories (SMT) solvers are crucial in many applications, yet their performance is often a bottleneck. This paper introduces SIRISMT, a novel framework that employs machine learning techniques for the automatic synthesis of efficient SMT-solving strategies. Specifically, SIRISMT targets at Z3 and consists of three key stages. First, given a set of training SMT formulas, SIRISMT simulates the solving process by leveraging reinforcement learning to guide its exploration within the strategy space. Next, SIRISMT refines the collected strategies by pruning redundant tactics and generating augmented strategies based on the subsequence structure of the learned strategies. These refined strategies are then fed back into the reinforcement learning model. Finally, the refined and optimized strategies are integrated into one strategy, which can be directly plugged into modern SMT solvers. Extensive evaluations show the superior performance of SIRISMT over the baseline methods. For example, compared to the default Z3, it solves 26.8% more formulas and achieves up to an 86.3% improvement in the Par-2 score on benchmark datasets. Additionally, we show that the synthesized strategy can improve the code coverage by up to 11.8% in a downstream symbolic execution benchmark.
4257: Dynamic Network Discovery via Infection Tracing
Authors: Ben Bals, Michelle Döring, Nicolas Klodt, George Skretas
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
Researchers, policy makers, and engineers need to make sense of data from spreading processes as diverse as
rumor spreading in social networks, viral infections, and water contamination.
Classical questions include predicting infection behavior in a given network or deducing the network structure from infection data.
Most of the research on network infections studies static graphs, that is, the connections in the network are assumed to not change.
More recently, temporal graphs, in which connections change over time, have been used to more accurately represent real-world infections, which rarely occur in unchanging networks.
We propose a model for temporal graph discovery that is consistent with previous work on static graphs and embraces the greater expressiveness of temporal graphs.
For this model, we give algorithms and lower bounds which are often tight. We analyze different variations of the problem, which make our results widely applicable and it also clarifies which aspects of temporal infections make graph discovery easier or harder.
We round off our analysis with an experimental evaluation of our algorithm on real-world interaction data from the Stanford Network Analysis Project and on temporal Erdős-Renyi graphs.
On Erdős-Renyi graphs, we uncover a threshold behavior, which can be explained by a novel connectivity parameter that we introduce during our theoretical analysis.
4276: COGRASP: Co-Occurrence Graph Based Stock Price Forecasting
Authors: Zhengze Li, Zilin Song, Tingting Yuan, Xiaoming Fu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
Forecasting stock prices is complex and challenging. Uncovering correlations among stocks has proven to enhance stock price forecasting. However, existing correlation discovery methods, such as concept-based methods, are slow, inaccurate, and limited by their reliance on predefined concepts and manual analysis. In this paper, we propose COGRASP, a novel approach for stock price forecasting that constructs stock co-occurrence graphs automatically by analyzing rapidly updated sources such as reports, newspapers, and social media. Besides, we aggregate forecasts across multiple timescales (i.e., long-, medium-, and short-term) to capture multi-timescale trends fluctuations, thereby enhancing price forecasting accuracy. In experiments with real-world open-source stock market data, COGRASP outperforms state-of-the-art methods.
4308: Sketch Decompositions for Classical Planning via Deep Reinforcement Learning
Authors: Michael Aichmüller, Hector Geffner
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Planning and Scheduling (2/5)
Show Abstract
In planning and reinforcement learning, the identification of common subgoal structures across problems is important when goals are to be achieved over long horizons. Recently, it has been shown that such structures can be expressed as feature-based rules, called sketches, over a number of classical planning domains. These sketches split problems into subproblems which then become solvable in low polynomial time by a greedy sequence of IW(k) searches. Methods for learning sketches using feature pools and min-SAT solvers have been developed, yet they face two key limitations: scalability and expressivity. In this work, we address these limitations by formulating the problem of learning sketch decompositions as a deep reinforcement learning (DRL) task, where general policies are sought in a modified planning problem where the successor states of a state s are defined as those reachable from s through an IW(k) search. The sketch decompositions obtained through this method are experimentally evaluated across various domains, and problems are regarded as solved by the decomposition when the goal is reached through a greedy sequence of IW(k) searches.
While our DRL approach for learning sketch decompositions does not yield interpretable sketches in the form of rules, we demonstrate that the resulting decompositions can often be understood in a crisp manner.
4332: Localizing Before Answering: A Benchmark for Grounded Medical Visual Question Answering
Authors: Dung Nguyen, Minh Khoi Ho, Huy Ta, Thanh Tam Nguyen, Qi Chen, Kumar Rav, Quy Duong Dang, Satwik Ramchandre, Son Lam Phung, Zhibin Liao, Minh-Son To, Johan Verjans, Phi Le Nguyen, Vu Minh Hieu Phan
Location: Montreal | Day: August 21st | Time: 11:30 | Session: CV: Benchmarks
Show Abstract
Medical Large Multi-modal Models (LMMs) have demonstrated remarkable capabilities in processing medical multi-modal data. However, they are prone to hallucinations, often generating content that conflicts with true sources. In this work, we reveal a critical limitation in current medical LMMs: a lack of localization reasoning, where models rely on shortcuts from language or irrelevant visual regions instead of focusing on pathological areas when answering disease-related queries. To address this, we introduce HEAL-MedVQA (Hallucination Evaluation via Localization in Medical VQA), a novel large-scale benchmark for evaluating the localization ability and hallucination robustness of LMMs. HEAL-MedVQA features (i) two innovative evaluation protocols to assess visual and textual shortcut learning, and (ii) a dataset of 67K VQA pairs, annotated by doctors with anatomical segmentation masks for pathological regions. To improve visual reasoning, we propose the Localize-before-Answer (LobA) framework, which trains LMMs to localize target regions of interest and self-prompt to emphasize segmented pathological areas, generating grounded and reliable answers. Experimental results demonstrate that our approach significantly outperforms state-of-the-art biomedical LMMs on the challenging HEAL-MedVQA benchmark, advancing robustness in medical VQA.
4372: Seeking Proxy Point via Stable Feature Space for Noisy Correspondence Learning
Authors: Yucheng Xie, Songyue Cai, Tao Tong, Ping Hu, Xiaofeng Zhu
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Computer Vision (3/3)
Show Abstract
To meet the growing demand for cross-modal training data, directly collecting multimodal data from the Internet has become prevalent. However, such data inevitably suffer from Noisy Correspondence. Previous works focused on recasting soft labels to mitigate noise’s negative impact. We explore a novel perspective to solve this problem: pursuing proxy representation for noisy data to enable reliable feature learning. To this end, we propose a novel framework: Seeking Proxy Point via Stable Feature Space (SPS). This framework employs a fine-grained partitioning strategy to obtain a high-confidence reliable set. By imposing intermodal cross-transformation consistency constraints and intramodal metric consistency constraints, a stable feature space is constructed.
Building on this foundation, SPS seeks proxy points for noisy data, enabling even noisy data to be accurately embedded into appropriate positions within the feature space. Combined with partial alignment for partially matched data pairs, SPS ultimately achieves robust learning under Noisy Correspondence. Experiments on three widely used cross-modal datasets demonstrate that SPS significantly outperforms previous methods. Our code is available at https://github.com/C-TeaRanger/SPS.
4488: A Fine-Grained Complexity View on Propositional Abduction – Algorithms and Lower Bounds
Authors: Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt
Location: Montreal | Day: August 21st | Time: 10:00 | Session: KRR: Learning and reasoning
Show Abstract
The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for SigmaP2- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a SigmaP2-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.
4494: A Case for Validation Buffer in Pessimistic Actor-Critic
Authors: Michał Nauman, Mateusz Ostaszewski, Marek Cygan
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Reinforcement Learning (2/2)
Show Abstract
In this paper, we investigate the issue of error accumulation in critic networks updated via pessimistic temporal difference objectives. We show that the critic approximation error can be approximated via a recursive fixed-point model similar to that of the Bellman value. We use such recursive definition to retrieve the conditions under which the pessimistic critic is unbiased. Building on these insights, we propose Validation Pessimism Learning (VPL) algorithm. VPL uses a small validation buffer to adjust the levels of pessimism throughout the agent training, with the pessimism set such that the approximation error of the critic targets is minimized. We investigate the proposed approach on a variety of locomotion and manipulation tasks and report improvements in sample efficiency and performance.
4504: Language-Conditioned Open-Vocabulary Mobile Manipulation with Pretrained Models
Authors: Shen Tan, Dong Zhou, Xiangyu Shao, Junqiao Wang, Guanghui Sun
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Robotics
Show Abstract
Open-vocabulary mobile manipulation (OVMM) that involves the handling of novel and unseen objects across different workspaces remains a significant challenge for real-world robotic applications. In this paper, we propose a novel Language-conditioned Open-Vocabulary Mobile Manipulation framework, named LOVMM, incorporating the large language model (LLM) and vision-language model (VLM) to tackle various mobile manipulation tasks in household environments. Our approach is capable of solving various OVMM tasks with free-form natural language instructions (e.g. "toss the food boxes on the office room desk to the trash bin in the corner", and "pack the bottles from the bed to the box in the guestroom"). Extensive experiments simulated in complex household environments show strong zero-shot generalization and multi-task learning abilities of LOVMM. Moreover, our approach can also generalize to multiple tabletop manipulation tasks and achieve better success rates compared to other state-of-the-art methods.
4544: Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
Authors: Andreas Göbel, Nicolas Klodt, Martin S. Krejca, Marcus Pappik
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
4566: ILIF: Temporal Inhibitory Leaky Integrate-and-Fire Neuron for Overactivation in Spiking Neural Networks
Authors: Kai Sun, Peibo Duan, Levin Kuhlmann, Beilun Wang, Bin Zhang
Location: Montreal | Day: August 20th | Time: 10:00 | Session: ML: Spiking Neural Networks
Show Abstract
The Spiking Neural Network (SNN) has drawn increasing attention for its energy-efficient, event-driven processing and biological plausibility. To train SNNs via backpropagation, surrogate gradients are used to approximate the non-differentiable spike function, but they only maintain nonzero derivatives within a narrow range of membrane potentials near the firing threshold—referred to as the surrogate gradient support width gamma. We identify a major challenge, termed the dilemma of gamma: a relatively large gamma leads to overactivation, characterized by excessive neuron firing, which in turn increases energy consumption, whereas a small gamma causes vanishing gradients and weakens temporal dependencies. To address this, we propose a temporal Inhibitory Leaky Integrate-and-Fire (ILIF) neuron model, inspired by biological inhibitory mechanisms. This model incorporates interconnected inhibitory units for membrane potential and current, effectively mitigating overactivation while preserving gradient propagation. Theoretical analysis demonstrates ILIF’s effectiveness in overcoming the gamma dilemma, and extensive experiments on multiple datasets show that ILIF improves energy efficiency by reducing firing rates, stabilizes training, and enhances accuracy. The code is available at github.com/kaisun1/ILIF.
4574: Keypoints as Dynamic Centroids for Unified Human Pose and Segmentation
Authors: Niaz Ahmad, Jawad Khan, Kang G. Shin, Youngmoon Lee, Guanghui Wang
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Computer vision (2/3)
Show Abstract
The dynamic movement of the human body presents a fundamental challenge for human pose estimation and body segmentation. State-of-the-art approaches primarily rely on combining keypoint heatmaps with segmentation masks, but often struggle in scenarios involving overlapping joints during pose estimation or rapidly changing poses for instance-level segmentation. To address these limitations, we leverage Keypoints as Dynamic Centroid (KDC), a new centroid-based representation for unified human pose estimation and instance-level segmentation. KDC adopts a bottom-up paradigm to generate keypoint heatmaps for easily distinguishable and complex keypoints, and improves keypoint detection and confidence scores by introducing KeyCentroids using a keypoint disk. It leverages high-confidence keypoints as dynamic centroids in the embedding space to generate MaskCentroids, allowing for the swift clustering of pixels to specific human instances during rapid changes in human body movements in a live environment. Our experimental evaluations focus on crowded and occluded cases using the CrowdPose, OCHuman, and COCO benchmarks, demonstrating KDC’s effectiveness and generalizability in challenging scenarios in terms of both accuracy and runtime performance. Our implementation is available at https://sites.google.com/view/niazahmad/projects/kdc.
4589: Concurrent Planning and Execution Using Dispatch-Dependent Values
Authors: Andrew Coles, Erez Karpas, Eyal Shimony, Shahaf Shperberg, Wheeler Ruml
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Planning and Scheduling (2/5)
Show Abstract
Agents operating in the real world must cope with the fact that time passes while they plan.
In some cases, such as under tight deadlines, the only way for such an agent to achieve its goal is to execute an action before a complete plan has been found. This problem is called Concurrent Planning and Execution (CoPE). Previous work on CoPE relied on a value function that assumes search will finish before actions are executed, causing the agent to be overly pessimistic in many situations.
In this paper, we define a new value function that takes into account the agent’s ability to dispatch actions incrementally. This allows us to devise a much simpler algorithm for concurrent planning and execution. An experimental evaluation on problems with time pressure shows that the new method significantly outperforms the previous state-of-the-art.
4614: Instantiation-based Formalization of Logical Reasoning Tasks Using Language Models and Logical Solvers
Authors: Mohammad Raza, Natasa Milic-Frayling
Location: Montreal | Day: August 20th | Time: 14:00 | Session: KR: Logic
Show Abstract
Robustness of reasoning remains a significant challenge for large language models, and addressing it is essential for the practical applicability of AI-driven reasoning systems. We introduce Semantic Self-Verification (SSV), a novel approach that addresses the key challenge in combining language models with the rigor of logical solvers: to accurately formulate the reasoning problem from natural language to the formal language of the solver. SSV uses a consistency-based approach to produce strong abstract formalizations of problems using concrete instantiations that are generated by the model and verified by the solver. In addition to significantly advancing the overall reasoning accuracy over the state-of-the-art, a key novelty that this approach presents is a feature of verification that has near-perfect precision over a significant coverage of cases, as we demonstrate on open reasoning benchmarks. We propose such *near-certain reasoning* as a new approach to reduce the need for manual verification in many cases, taking us closer to more dependable and autonomous AI reasoning systems.
4691: Online 3D Gaussian Splatting Modeling with Novel View Selection
Authors: Byeonggwon Lee, Junkyu Park, Khang Truong Giang, Soohwan Song
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Computer Vision (1/3)
Show Abstract
This study addresses the challenge of generating online 3D Gaussian Splatting (3DGS) models from RGB-only frames. Previous studies have employed dense SLAM techniques to estimate 3D scenes from keyframes for 3DGS model construction. However, these methods are limited by their reliance solely on keyframes, which are insufficient to capture an entire scene, resulting in incomplete reconstructions. Moreover, building a generalizable model requires incorporating frames from diverse viewpoints to achieve broader scene coverage. However, online processing restricts the use of many frames or extensive training iterations. Therefore, we propose a novel method for high-quality 3DGS modeling that improves model completeness through adaptive view selection. By analyzing reconstruction quality online, our approach selects optimal non-keyframes for additional training. By integrating both keyframes and selected non-keyframes, the method refines incomplete regions from diverse viewpoints, significantly enhancing completeness. We also present a framework that incorporates an online multi-view stereo approach, ensuring consistency in 3D information throughout the 3DGS modeling process. Experimental results demonstrate that our method outperforms state-of-the-art methods, delivering exceptional performance in complex outdoor scenes.
4721: Discrete Budget Aggregation: Truthfulness and Proportionality
Authors: Ulrike Schmidt-Kraepelin, Warut Suksompong, Markus Utke
Location: Montreal | Day: August 21st | Time: 15:00 | Session: GTEP: Computational social choice (2/2)
Show Abstract
We study a budget aggregation setting where voters express their preferred allocation of a fixed budget over a set of alternatives, and a mechanism aggregates these preferences into a single output allocation. Motivated by scenarios in which the budget is not perfectly divisible, we depart from the prevailing literature by restricting the mechanism to output allocations that assign integral amounts. This seemingly minor deviation has significant implications for the existence of truthful mechanisms. Specifically, when voters can propose fractional allocations, we demonstrate that the Gibbard-Satterthwaite theorem can be extended to our setting. In contrast, when voters are restricted to integral ballots, we identify a class of truthful mechanisms by adapting moving-phantom mechanisms to our context. Finally, we show that while a weak form of proportionality can be achieved alongside truthfulness, stronger proportionality notions derived from approval-based committee voting are incompatible with truthfulness.
4730: VeRecycle: Reclaiming Guarantees from Probabilistic Certificates for Stochastic Dynamical Systems after Change
Authors: Sterre Lutz, Matthijs T.J. Spaan, Anna Lukina
Location: Montreal | Day: August 21st | Time: 10:00 | Session: AI Ethics, Trust, Fairness (2/3)
Show Abstract
Autonomous systems operating in the real world encounter a range of uncertainties. Probabilistic neural Lyapunov certification is a powerful approach to proving safety of nonlinear stochastic dynamical systems. When faced with changes beyond the modeled uncertainties, e.g., unidentified obstacles, probabilistic certificates must be transferred to the new system dynamics. However, even when the changes are localized in a known part of the state space, state-of-the-art requires complete re-certification, which is particularly costly for neural certificates. We introduce VeRecycle, the first framework to formally reclaim guarantees for discrete-time stochastic dynamical systems. VeRecycle efficiently reuses probabilistic certificates when the system dynamics deviate only in a given subset of states. We present a general theoretical justification and algorithmic implementation. Our experimental evaluation shows scenarios where VeRecycle both saves significant computational effort and achieves competitive probabilistic guarantees in compositional neural control.
Code — https://github.com/SUMI-lab/VeRecycle
Extended version — https://doi.org/10.48550/arXiv.2505.14001
4772: A Symmetric Relative-Error Loss Function for Intermittent Multiscale Signal Modelling
Authors: Sergio M. Vanegas Arias, Lasse Lensu, Fredy Ruiz Palacios
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: time series, sequences and signals
Show Abstract
Multiscale signals represent a formidable modelling challenge in Machine Learning as the ubiquitous Mean Squared Error loss function neglects signal behaviour at smaller values. Several scale-equalizing error metrics have been devised to tackle this problem, amongst which the Mean Absolute Percentage Error (MAPE) remains the most widely used due to its simplicity and interpretability. However, by its very definition, MAPE introduces three major issues: asymptotic behaviour at zero-target values, asymptotic gradient behaviour at zero error, and accuracy loss for large signal scales. We address these limitations by proposing the Symmetric Mean Arctangent Squared Percentage Error (SMASPE), which builds up from the Mean Arctangent Absolute Percentage Error (MAAPE) and leverages a mathematically smoother definition along with user-provided signal bounds to extend its functionality. The numerical properties of SMASPE are explored, and its performance is tested in two real-life cases for deterministic and stochastic optimization. The experiments show a clear advantage of the proposed loss function, with an improvement of up to 42% with respect to MAAPE in terms of Mean Absolute Error for deep learning models when appropriate bounds are selected.
4777: Decentralized Online Learning by Selfish Agents in Coalition Formation
Authors: Saar Cohen, Noa Agmon
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Game Theory and Economic Paradigms
Show Abstract
Coalition formation involves self-organized coalitions generated through strategic interactions of autonomous selfish agents. In online learning of coalition structures, agents’ preferences toward each other are initially unknown before agents interact. Coalitions are formed iteratively based on preferences that agents learn online from repeated feedback resulting from their interactions. In this paper, we introduce online learning in coalition formation through the lens of distributed decision-making, where self-interested agents operate without global coordination or information sharing, and learn only from their own experience. Under our selfish perspective, each agent seeks to maximize her own utility. Thus, we analyze the system in terms of Nash stability, where no agent can improve her utility by unilaterally deviating. We devise a sample-efficient decentralized algorithm for selfish agents that minimize their Nash regret, yielding approximately Nash stable solutions. In our algorithm, each agent uses only one utility feedback per round to update her strategy, but our algorithm still has Nash regret and sample complexity bounds that are optimal up to logarithmic factors.
4783: GraphProt: Certified Black-Box Shielding Against Backdoored Graph Models
Authors: Xiao Yang, Yuni Lai, Kai Zhou, Gaolei Li, Jianhua Li, Hang Zhang
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: AI Ethics, Trust, Fairness (3/3)
Show Abstract
Graph learning models have been empirically proven to be vulnerable to backdoor threats, wherein adversaries submit trigger-embedded inputs to manipulate the model predictions.
Current graph backdoor defenses manifest several limitations: 1) dependence on model-related details, 2) necessitation of additional fine-tuning, and 3) reliance on extra explainability tools, all of which are infeasible under stringent privacy policies.
To address those limitations, we propose GraphProt, a certified black-box defense method to suppress backdoor attacks on GNN-based graph classifiers. Our GraphProt operates in a model-agnostic manner and solely leverages graph input.
Specifically, GraphProt first introduces designed topology-feature-filtration to mitigate graph anomalies. Subsequently, subgraphs are sampled via a formulated strategy integrating topology and features, followed by a robust model inference through a majority vote-based subgraph prediction ensemble.
Our results across benchmark attacks and datasets show GraphProt effectively reduces attack success rates while preserving regular graph classification accuracy.
4863: A Logic-based Framework for Decoding Enthymemes in Argument Maps Involving Implicitness in Premises and Claims
Authors: Victor David, Anthony Hunter
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
Argument mining is a natural language processing technology aimed at identifying the explicit premises and claims of arguments in text, and the support and attack relationships between them. To better understand, and automatically analyse, the argument maps that are output from argument mining, it would be desirable to instantiate the arguments in the argument map with logical arguments. However, most real-world arguments are enthymemes (i.e. some of the premises and/or claim are implicit), which need to be decoded (i.e. the implicit aspects need to be identified). A key challenge is to decode enthymemes so as to respect the support and attack relationships in the argument map. addressing the problem of identifying the missing premises and/or claim, and discerning the relationships between them. To address this, we present a novel framework, based on default logic, for representing arguments including enthymemes. We show how decoding an enthymeme means identifying the default rules that are implicit in the premises and claims. We then show how choosing a decoding of the enthymemes in an argument map can be formalized as an optimization problem, and that a solution can be obtained using MaxSAT solvers.
4877: Inconsistency Handling in DatalogMTL
Authors: Meghyn Bienvenu, Camille Bourgaux, Atefe Khodadaditaghanaki
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: KR: ontologies
Show Abstract
In this paper, we explore the issue of inconsistency handling in DatalogMTL, an extension of Datalog with metric temporal operators. Since facts are associated with time intervals, there are different manners to restore consistency when they contradict the rules, such as removing facts or modifying their time intervals. Our first contribution is the definition of relevant notions of conflicts (minimal explanations for inconsistency) and repairs (possible ways of restoring consistency) for this setting and the study of the properties of these notions and the associated inconsistency-tolerant semantics. Our second contribution is a data complexity analysis of the tasks of generating a single conflict / repair and query entailment under repair-based semantics.
4895: Integrating Answer Set Programming and Large Language Models for Enhanced Structured Representation of Complex Knowledge in Natural Language
Authors: Mario Alviano, Lorenzo Grillo, Fabrizio Lo Scudo, Luis Angel Rodriguez Reiners
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
Answer Set Programming (ASP) and Large Language Models (LLMs) have emerged as powerful tools in Artificial Intelligence, each offering unique capabilities in knowledge representation and natural language processing, respectively.
In this paper, we combine the strengths of the two paradigms with the aim of improving the structured representation of complex knowledge encoded in natural language.
In a nutshell, the structured representation is obtained by combining syntactic structures extracted by LLMs and semantic aspects encoded in the knowledge base.
The interaction between ASP and LLMs is driven by a YAML file specifying prompt templates and domain-specific background knowledge.
The proposed approach is evaluated using a set of benchmarks based on a dataset obtained from problems of ASP Competitions.
The results of our experiment show that ASP can sensibly improve the F1-score, especially when relatively small models are used.
4923: Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation
Authors: Marianne Defresne, Jayanta Mandi, Tias Guns
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Constraint Satisfaction and Optimization (1/3)
Show Abstract
Real-life combinatorial optimization problems often involve several conflicting objectives, such as price, product quality and sustainability. A computationally-efficient way to tackle multiple objectives is to aggregate them into a single-objective function, such as a linear combination. However, defining the weights of the linear combination upfront is hard; alternatively, the use of interactive learning methods that ask users to compare candidate solutions is highly promising. The key challenges are to generate candidates quickly, to learn an objective function that leads to high-quality solutions and to do so with few user interactions. We build upon the Constructive Preference Elicitation framework and show how each of the three properties can be improved: to increase the interaction speed we investigate using pools of (relaxed) solutions, to improve the learning we adopt Maximum Likelihood Estimation of a Bradley-Terry preference model; and to reduce the number of user interactions, we select the pair of candidates to compare with an ensemble-based acquisition function inspired from Active Learning. Our careful experimentation demonstrates each of these improvements: on a PC configuration task and a realistic multi-instance routing problem, our method selects queries faster, needs fewer queries and synthesizes higher-quality combinatorial solutions than previous CPE methods.
4929: Learning Probabilistic Temporal Logic Specifications for Stochastic Systems
Authors: Rajarshi Roy, Yash Pote, Dave Parker, Marta Kwiatkowska
Location: Montreal | Day: August 20th | Time: 14:00 | Session: KR: Logic
Show Abstract
There has been substantial progress in the inference of formal behavioural specifications from sample trajectories, for example using Linear Temporal Logic (LTL). However, these techniques cannot handle specifications that correctly characterise systems with stochastic behaviour, which occur commonly in reinforcement learning and formal verification. We consider the passive learning problem of inferring a Boolean combination of probabilistic LTL (PLTL) formulas from a set of Markov chains, classified as either positive or negative. We propose a novel learning algorithm that infers concise PLTL specifications, leveraging grammar-based enumeration, search heuristics, probabilistic model checking and Boolean set-cover procedures. We demonstrate the effectiveness of our algorithm in two use cases: learning from policies induced by RL algorithms and learning from variants of a probabilistic model. In both cases, our method automatically and efficiently extracts PLTL specifications that succinctly characterize the temporal differences between the policies or model variants.
4930: InnateCoder: Learning Programmatic Options with Foundation Models
Authors: Rubens O. Moraes, Quazi Asif Sadmine, Hendrik Baier, Levi H. S. Lelis
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: LLM applications
Show Abstract
Outside of transfer learning settings, reinforcement learning agents start their learning process from a clean slate. As a result, such agents have to go through a slow process to learn even the most obvious skills required to solve a problem. In this paper, we present InnateCoder, a system that leverages human knowledge encoded in foundation models to provide programmatic policies that encode “innate skills” in the form of temporally extended actions, or options. In contrast to existing approaches to learning options, InnateCoder learns them from the general human knowledge encoded in foundation models in a zero-shot setting, and not from the knowledge the agent gains by interacting with the environment. Then, InnateCoder searches for a programmatic policy by combining the programs encoding these options into larger and more complex programs. We hypothesized that InnateCoder’s way of learning and using options could improve the sampling efficiency of current methods for learning programmatic policies. Empirical results in MicroRTS and Karel the Robot support our hypothesis, since they show that InnateCoder is more sample efficient than versions of the system that do not use options or learn them from experience.
4935: X-KAN: Optimizing Local Kolmogorov-Arnold Networks via Evolutionary Rule-Based Machine Learning
Authors: Hiroki Shiraishi, Hisao Ishibuchi, Masaya Nakata
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: S: Evolutionary computation (2/2)
Show Abstract
Function approximation is a critical task in various fields. However, existing neural network approaches struggle with locally complex or discontinuous functions due to their reliance on a single global model covering the entire problem space. We propose X-KAN, a novel method that optimizes multiple local Kolmogorov-Arnold Networks (KANs) through an evolutionary rule-based machine learning framework called XCSF. X-KAN combines KAN’s high expressiveness with XCSF’s adaptive partitioning capability by implementing local KAN models as rule consequents and defining local regions via rule antecedents. Our experimental results on artificial test functions and real-world datasets demonstrate that X-KAN significantly outperforms conventional methods, including XCSF, Multi-Layer Perceptron, and KAN, in terms of approximation accuracy. Notably, X-KAN effectively handles functions with locally complex or discontinuous structures that are challenging for conventional KAN, using a compact set of rules (average 7.2 rules). These results validate the effectiveness of using KAN as a local model in XCSF, which evaluates the rule fitness based on both accuracy and generality. Our X-KAN implementation and an extended version of this paper, including appendices, are available at https://doi.org/10.48550/arXiv.2505.14273.
4936: A Unifying Framework for Semiring-Based Constraint Logic Programming With Negation
Authors: Jeroen Spaans, Jesse Heyninck
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Constraint Satisfaction and Optimization (3/3)
Show Abstract
Constraint Logic Programming (CLP) is a logic programming formalism used to solve problems requiring the consideration of constraints, like resource allocation and automated planning and scheduling.
It has previously been extended in various directions, for example to support fuzzy constraint satisfaction, uncertainty, or negation, with different notions of semiring being used as a unifying abstraction for these generalisations. None of these extensions have studied clauses with negation allowed in the body.
We investigate an extension of CLP which unifies many of these extensions and allows negation in the body. We provide semantics for such programs, using the framework of approximation fixpoint theory, and give a detailed overview of the impacts of properties of the semirings on the resulting semantics. As such, we provide a unifying framework that captures existing approaches and allows to extend them with a more expressive language.
4956: Bimodal Depth-First Search for Scalable GAC for AllDifferent
Authors: Sulian Le Bozec-Chiffoleau, Nicolas Beldiceanu, Charles Prud’homme, Gilles Simonin, Xavier Lorca
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Constraint Satisfaction and Optimization (2/3)
Show Abstract
We propose a version of DFS designed for Constraint Programming, called bimodal DFS, that scales to both sparse and dense graphs. It runs in O(n + ~m) time, where ~m is the sum, for each vertex v, of the minimum between the numbers of successors and non-successors of v.
Integrating it into Régin’s GAC algorithm for the AllDifferent constraint results in faster performance as the problem size increases, outperforming a GPU-accelerated version.
In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.
4959: Argument-based Multi-Issue Negotiation
Authors: Thalya Fossey, Jean-Guy Mailly, Pavlos Moraitis
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Agent-based and Multi-agent Systems (2/3)
Show Abstract
Automated negotiation aims at finding agreements between agents with conflicting goals. Existing utility-based approaches guarantee agents satisfaction with negotiation outcomes, especially in multi-issue negotiations
where concession mechanisms lead to win-win results. However, they lack explainability and do not consider agents’ beliefs. On the other hand, argument-based approaches provide reasons for accepting or rejecting offers but do not include utility modeling for offers or enable concession mechanisms in multi-issue settings. We propose a novel hybrid approach combining both types of approaches.
The utility-based component enables agents to make concessions on complex negotiation objects to achieve win-win outcomes, while the argumentation component ensures that accepted offers align with the agents’ personal argumentation theories. These theories represent their beliefs, encoding various profiles, ethical considerations, social norms, or legal principles.
4987: EnergyCompress: A General Case Base Learning Strategy
Authors: Fadi Badra, Esteban Marquer, Marie-Jeanne Lesot, Miguel Couceiro, David Leake
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Knowledge Representation and Reasoning (2/4)
Show Abstract
Case-based prediction (CBP) methods do not learn a model of the target decision function but instead perform an inference process that depends on two similarity measures and a reference case base. This paper proposes a strategy, called EnergyCompress, to learn an effective case base by selecting relevant cases from an initial set. Use of EnergyCompress decreases CBP inference time, through case base compression, and also increases prediction performance, for a wide variety of CBP algorithms. EnergyCompress relies on the proposition of a general formulation of the CBP task in the framework of energy-based models, which leads to a new and valuable characterization of the notion of competence in case-based reasoning, in particular at the source case level. Extensive experimental results on 18 benchmark datasets comparing EnergyCompress to 5 reference algorithms for case base maintenance support the benefit of the proposed strategy.
4997: From End-to-end to Step-by-step: Learning to Abstract via Abductive Reinforcement Learning
Authors: Zilong Wang, Jiongda Wang, Xiaoyong Chen, Meng Wang, Ming Ma, ZhiPeng Wang, Zhenyu Zhou, Tianming Yang, Wang-Zhou Dai
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
Abstraction is a critical technique in general problem-solving, allowing complex tasks to be decomposed into smaller, manageable sub-tasks. While traditional symbolic planning relies on predefined primitive symbols to construct structured abstractions, its reliance on formal representations limits applicability to real-world tasks. On the other hand, reinforcement learning excels at learning end-to-end policies directly from sensory inputs in unstructured environments but struggles with compositional generalization in complex tasks with delayed rewards. In this paper, we propose Abductive Abstract Reinforcement Learning (A2RL), a novel neuro-symbolic RL framework bridging the two paradigms based on Abductive Learning (ABL), enabling RL agents to learn abstractions directly from raw sensory inputs without predefined symbols.
A2RL induces a finite state machine to represent high-level, step-by-step procedures, where each abstract state corresponds to a sub-algebra of the original Markov Decision Process (MDP). This approach not only bridges the gap between symbolic abstraction and sub-symbolic learning but also provides a natural mechanism for the emergence of new symbols. Experiments show that A2RL can mitigate the delayed reward problem and improve the generalization capability compared to traditional end-to-end RL methods.
4998: Language-Based Bayesian Optimization Research Assistant (BORA)
Authors: Abdoulatif Cissé, Xenophon Evangelopoulos, Vladimir V. Gusev, Andrew I. Cooper
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: Machine Learning 6/8
Show Abstract
Many important scientific problems involve multivariate optimization coupled with slow and laborious experimental measurements. These high-dimensional searches can be defined by complex, non-convex optimization landscapes that resemble needle-in-a-haystack surfaces, leading to entrapment in local minima. Contextualizing optimizers with human domain knowledge is a powerful approach to guide searches to localized fruitful regions. However, this approach is susceptible to human confirmation bias. It is also challenging for domain experts to keep track of the rapidly expanding scientific literature. Here, we propose the use of Large Language Models (LLMs) for contextualizing Bayesian optimization (BO) via a hybrid optimization framework that intelligently and economically blends stochastic inference with domain knowledge-based insights from the LLM, which is used to suggest new, better-performing areas of the search space for exploration. Our method fosters user engagement by offering real-time commentary on the optimization progress, explaining the reasoning behind the search strategies. We validate the effectiveness of our approach on synthetic benchmarks with up to 15 variables and demonstrate the ability of LLMs to reason in four real-world experimental tasks where context-aware suggestions boost optimization performance substantially.
5005: Synthesising Minimum Cost Dynamic Norms
Authors: Natasha Alechina, Brian Logan, Giuseppe Perelli
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MAS: Formal verification, validation and synthesis
Show Abstract
A key problem in the design of normative multi-agent systems is the cost of enforcing a norm (for the system operator) or complying with the norm (for the system users). If the cost is too high, ensuring compliant behavior may be uneconomic, or users may be deterred from participating in the MAS. In this paper, we consider the problem of synthesizing minimum cost dynamic norms to satisfy a system-level objective specified in Alternating Time Temporal Logic with Strategy Contexts (ATLsc∗). We show that synthesizing a dynamic norm under a bound on the cost of any prohibited set of actions has the same complexity as synthesizing arbitrary norms. We also show that synthesizing norms that minimize the average cost of the prohibited set of actions is unsolvable; however, synthesizing ε-optimal norms is possible.
5010: Think Twice Before Adaptation: Improving Adaptability of DeepFake Detection via Online Test-Time Adaptation
Authors: Hong-Hanh Nguyen-Le, Van-Tuan Tran, Dinh-Thuc Nguyen, Nhien-An Le-Khac
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MTA: Security and privacy
Show Abstract
Deepfake (DF) detectors face significant challenges when deployed in real-world environments, particularly when encountering test samples deviated from training data through either postprocessing manipulations or distribution shifts. We demonstrate postprocessing techniques can completely obscure generation artifacts presented in DF samples, leading to performance degradation of DF detectors. To address these challenges, we propose Think Twice before Adaptation (T2A), a novel online test-time adaptation method that enhances the adaptability of detectors during inference without requiring access to source training data or labels. Our key idea is to enable the model to explore alternative options through an Uncertainty-aware Negative Learning objective rather than solely relying on its initial predictions as commonly seen in entropy minimization (EM)-based approaches. We also introduce an Uncertain Sample Prioritization strategy and Gradients Masking technique to improve the adaptation by focusing on important samples and model parameters. Our theoretical analysis demonstrates that the proposed negative learning objective exhibits complementary behavior to EM, facilitating better adaptation capability. Empirically, our method achieves state-of-the-art results compared to existing test-time adaptation (TTA) approaches and significantly enhances the resilience and generalization of DF detectors during inference.
5026: Online Housing Market
Authors: Julien Lesca
Location: Montreal | Day: August 21st | Time: 15:00 | Session: GTEP: Computational social choice (2/2)
Show Abstract
We study an online variant of the celebrated housing market problem, where each agent owns a single house and seeks to exchange it based on her preferences. In this online setting, agents may arrive and depart at any time, meaning not all agents are present in the housing market simultaneously. We extend the well-known serial dictatorship and top trading cycle mechanisms to the online scenario, aiming to retain their desirable properties, such as Pareto efficiency, individual rationality, and strategy-proofness. These extensions also seek to prevent agents from strategically delaying their arrivals or advancing their departures. We demonstrate that achieving all these properties simultaneously is impossible and present several variants that achieve different subsets of these properties.
5050: Unsupervised Feature Transformation via In-context Generation, Generator-critic LLM Agents, and Duet-play Teaming
Authors: Nanxu Gong, Xinyuan Wang, Wangyang Ying, Haoyue Bai, Sixun Dong, Haifeng Chen, Yanjie Fu
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Data Mining
Show Abstract
Feature transformation involves generating a new set of features from the original dataset to enhance the data’s utility. In certain domains like material performance screening, dimensionality is large and collecting labels is expensive and lengthy. It highly necessitates transforming feature spaces efficiently and without supervision to enhance data readiness and AI utility. However, existing methods fall short in efficient navigation of a vast space of feature combinations, and are mostly designed for supervised settings. To fill this gap, our unique perspective is to leverage a generator-critic duet-play teaming framework using LLM agents and in-context learning to derive pseudo-supervision from unsupervised data. The framework consists of three interconnected steps: (1) Critic agent diagnoses data to generate actionable advice, (2) Generator agent produces tokenized feature transformations guided by the critic’s advice, and (3) Iterative refinement ensures continuous improvement through feedback between agents. The generator-critic framework can be generalized to human-agent collaborative generation, by replacing the critic agent with human experts. Extensive experiments demonstrate that the proposed framework outperforms even supervised baselines in feature transformation efficiency, robustness, and practical applicability across diverse datasets. Our code is publicly available at https://github.com/NanxuGong/LPFG.
5065: Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths
Authors: Stefan Funke, Daniel Koch, Claudius Proissl, Christian Staib, Felix Weitbrecht
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Planning and Scheduling (4/5)
Show Abstract
We consider the problem of quickly providing strong lower bounds for the planar Euclidean shortest path (ESP) problem. Such lower bounds are crucial for guiding the search in A* type approaches or for proving quality guarantees for algorithms that compute approximate solutions.
Our contributions are two-fold: we show how to simplify ESP instances such that computing and storing a visibility graph becomes feasible while distances within the simplified instance are guaranteed to constitute lower bounds for the original problem instance. Furthermore we show how to precompute a space efficient data structure that allows to perform distance queries on visibility graphs within few microseconds with negligible space overhead.
5079: MS-DPPs: Multi-Source Determinantal Point Processes for Contextual Diversity Refinement of Composite Attributes in Text to Image Retrieval
Authors: Naoya Sogi, Takashi Shibata, Makoto Terao, Masanori Suganuma, Takayuki Okatani
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Computer Vision (1/3)
Show Abstract
Result diversification (RD) is a crucial technique in Text-to-Image Retrieval for enhancing the efficiency of a practical application. Conventional methods focus solely on increasing the diversity metric of image appearances. However, the diversity metric and its desired value vary depending on the application, which limits the applications of RD. This paper proposes a novel task called CDR-CA (Contextual Diversity Refinement of Composite Attributes). CDR-CA aims to refine the diversities of multiple attributes, according to the application’s context. To address this task, we propose Multi-Source DPPs, a simple yet strong baseline that extends the Determinantal Point Process (DPP) to multi-sources. We model MS-DPP as a single DPP model with a unified similarity matrix based on a manifold representation. We also introduce Tangent Normalization to reflect contexts.
Extensive experiments demonstrate the effectiveness of the proposed method.
5099: Constrained Preferential Bayesian Optimization and Its Application in Banner Ad Design
Authors: Koki Iwai, Yusuke Kumagae, Yuki Koyama, Masahiro Hamasaki, Masataka Goto
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: Machine Learning 6/8
Show Abstract
Preferential Bayesian optimization (PBO) is a variant of Bayesian optimization that observes relative preferences (e.g., pairwise comparisons) instead of direct objective values, making it especially suitable for human-in-the-loop scenarios. However, real-world optimization tasks often involve inequality constraints, which existing PBO methods have not yet addressed. To fill this gap, we propose constrained preferential Bayesian optimization (CPBO), an extension of PBO that incorporates inequality constraints for the first time. Specifically, we present a novel acquisition function for this purpose. Our technical evaluation shows that our CPBO method successfully identifies optimal solutions by focusing on exploring feasible regions. As a practical application, we also present a designer-in-the-loop system for banner ad design using CPBO, where the objective is the designer’s subjective preference, and the constraint ensures a target predicted click-through rate. We conducted a user study with professional ad designers, demonstrating the potential benefits of our approach in guiding creative design under real-world constraints.
5140: Why the Agent Made that Decision: Contrastive Explanation Learning for Reinforcement Learning
Authors: Rui Zuo, Simon Khan, Zifan Wang, Garrett Ethan Katz, Qinru Qiu
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: ETF: Explainability and interpretability
Show Abstract
Reinforcement learning (RL) has demonstrated remarkable success in solving complex decision-making problems, yet its adoption in critical domains is hindered by the lack of interpretability in its decision-making processes. Existing explainable AI (xAI) approaches often fail to provide meaningful explanations for RL agents, particularly because they overlook the contrastive nature of human reasoning—answering "why this action instead of that one?" To address this gap, we propose a novel framework of contrastive learning to explain RL selected actions, named VisionMask. VisionMask is trained to generate explanations by explicitly contrasting the agent’s chosen action with alternative actions in a given state using a self-supervised manner. %It is trained using a contrastive self-supervised learning manner, leveraging the relationships between state features and action dynamics to produce intuitive and actionable insights.
We demonstrate the efficacy of our method through experiments across diverse RL environments, evaluating it in terms of faithfulness, robustness and complexity. Our results show that VisionMask significantly improve human understanding of agent behavior while maintaining accuracy and fidelity. Furthermore, we present examples illustrating how VisionMask can be used for counterfactual analysis. This work bridges the gap between RL and xAI, paving the way for safer and more interpretable RL systems.
5152: SEP: A General Lossless Compression Framework with Semantics Enhancement and Multi-Stream Pipelines
Authors: Meng Wan, Rongqiang Cao, Yanghao Li, Jue Wang, Zijian Wang, Qi Su, Lei Qiu, Peng Shi, Yangang Wang, Chong Li
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Data Mining
Show Abstract
Deep-learning-based lossless compression is of immense importance in real-world applications, such as cold data persistence, sensor data collection, and astronomical data transmission. However, existing compressors typically model data using single-byte symbols as tokens, which makes it hard to capture the inherent correlations and cannot effectively utilize the parallel capabilities of GPU and multi-core CPU. This paper proposes SEP, a novel lossless compression framework for most time-series backbone neural networks. We first introduce a semantic enhancement module to capture the complex intra-patch relationships of binary byte streams. To improve the compression speed, we design multi-stream pipelines that dynamically assign parallel tasks to GPU streams and multi-cores. We further propose a novel GPU memory optimization strategy, which reuses GPU memory by a shared pool across streams. We conduct experiments on seven real-world datasets and the results demonstrate that our SEP framework outperforms state-of-the-art compressors with an average speed improvement of 30.0% and an average compression ratio gain of 5.1%, which is further elevated to 7.6% with the use of pre-training models. The GPU memory footprint is reduced by as high as 63.1% and by an average of 36.2%. The source code is available at: https://github.com/damonwan1/SEP.
5163: In-context Learning Demonstration Generation with Text Distillation
Authors: Wuyuqing Wang, Erkun Yang, Zilan Zhou, Cheng Deng
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Large Language Models
Show Abstract
In-context learning (ICL), a paradigm derived from large language models (LLMs), holds significant promise but is notably sensitive to the choice of input demonstrations. While numerous methodologies have been developed to select the optimal demonstrations from existing datasets, our work alternatively proposes to generate representative demonstrations through a Distillation-based Demonstration Generation (DDG) framework.
Specifically, our approach aims to generate demonstrations that encapsulate the essential attributes of the target dataset. Rather than optimizing these demonstrations directly, we design a generative model and try to refine it by minimizing the discrepancies between the calculative models trained on generated demonstrations and the original datasets respectively. Additionally, we leverage a teacher-student framework to stabilize the training process and improve the quality of the synthesized samples. Extensive experiments conducted across ten prevalent text datasets demonstrate that our DDG method substantially outperforms existing state-of-the-art methodologies. Our code will be available at https://github.com/wwyq1/DDG.
5338: Federated Stochastic Bilevel Optimization with Fully First-Order Gradients
Authors: Yihan Zhang, Rohit Dhaipule, Chiu C. Tan, Haibin Ling, Hongchang Gao
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Federated Learning
Show Abstract
Federated stochastic bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning. However, most existing federated stochastic bilevel optimization algorithms require the computation of second-order Hessian and Jacobian matrices, which leads to longer running times in practice. To address these challenges, we propose a novel federated stochastic variance-reduced bilevel gradient descent algorithm that relies solely on first-order oracles. Specifically, our approach does not require the computation of second-order Hessian and Jacobian matrices, significantly reducing running time. Furthermore, we introduce a novel learning rate mechanism, i.e., a constant single-time-scale learning rate, to coordinate the update of different variables. We also present a new strategy to establish the convergence rate of our algorithm. Finally, the extensive experimental results confirm the efficacy of our proposed algorithm.
5361: Witnesses for Answer Sets of Basic Logic Programs
Authors: Yisong Wang, Xianglong Wang, Zhongtao Xie, Thomas Eiter
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: KRR: Logic programming
Show Abstract
Explanation plays an important role in the decisions of both symbolic and neural network-based AI systems. Logic programs under answer set semantics (ASP) have been a typical declarative reasoning and problem-solving paradigm that has extensive applications in various AI domains. In this paper, we consider the issue of explanation for logic programs with abstract constraint atoms (c-atoms) under SPT-answer set semantics. Such c-atoms are general enough to capture complex constructors of logic programs, including aggregates, and the SPT-answer sets exclude circular justifications that other semantics have. We propose a minimal reduct for logic programs with c-atoms that yields a new semantic characterization of SPT-answer sets, and then introduce an extension of resolution for clauses with c-atoms. As we show, every atom in an SPT-answer set enjoys an extended resolution proof from the minimal reduct of its logic program. Finally, we present minimal sufficient subsets of logic programs
(witnesses) to structure such an extended resolution proof for an atom in an SPT-answer set. Our results contribute to the justification of answer sets and provide a basis for explainability of ASP-based applications.
5377: CABIN: Debiasing Vision-Language Models Using Backdoor Adjustments
Authors: Bo Pang, Tingrui Qiao, Caroline Walker, Chris Cunningham, Yun Sing Koh
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: AI Ethics, Trust, Fairness (3/3)
Show Abstract
Vision-language models (VLMs) have demonstrated strong zero-shot inference capabilities but may exhibit stereotypical biases toward certain demographic groups. Consequently, downstream tasks leveraging these models may yield unbalanced performance across different target social groups, potentially reinforcing harmful stereotypes. Mitigating such biases is critical for ensuring fairness in practical applications. Existing debiasing approaches typically rely on curated face-centric datasets for fine-tuning or retraining, risking overfitting and limiting generalisability. To address this issue, we propose a novel framework, CABIN (Causal Adjustment Based INtervention). It leverages a causal framework to identify sensitive attributes in images as confounding factors. Employing a learned mapper, which is trained on general large-scale image-text pairs rather than face-centric datasets, CABIN may use text to adjust sensitive attributes in the image embedding, ensuring independence between these sensitive attributes and image embeddings. This independence enables a backdoor adjustment for unbiased inference without the drawbacks of additional fine-tuning or retraining on narrowly tailored datasets. Through comprehensive experiments and analyses, we demonstrate that CABIN effectively mitigates biases and improves fairness metrics while preserving the zero-shot strengths of VLMs. The code is available at: https://github.com/ipangbo/causal-debias
5386: Constrained Sequential Inference in Machine Learning Using Constraint Programming
Authors: Virasone Manibod, David Saikali, Gilles Pesant
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Constraint Satisfaction and Optimization (1/3)
Show Abstract
Sequence models in machine learning often struggle to exhibit long-term structure. We consider this problem at inference time in the context of enforcing constraints that are not necessarily featured in the dataset on which the generative model was trained. The difficulty lies in imposing previously-unseen structure while staying close to the training dataset. It is particularly hard for long-term structure, which requires balancing foresight over many yet-to-be generated tokens and the immediacy of next-token predictions from the sequence model. We address this problem by introducing our neurosymbolic framework GeAI-BLAnC. The learned probabilities of the sequence model are mixed in with the marginal probabilities computed from a constraint programming / belief propagation framework applied to a constraint programming model expressing the desired structure.
The next predicted token is then selected from the resulting probability distribution. Experiments in the context of molecule and music generation show that we can achieve the structure imposed post-training without straying too much from the structure of the dataset learned during training.
5415: Counterfactual Explanations for Continuous Action Reinforcement Learning
Authors: Shuyang Dong, Shangtong Zhang, Lu Feng
Location: Montreal | Day: August 21st | Time: 10:00 | Session: ML: Explainable/Interpretable machine learning
Show Abstract
Reinforcement Learning (RL) has shown great promise in domains like healthcare and robotics but often struggles with adoption due to its lack of interpretability. Counterfactual explanations, which address “what if” scenarios, provide a promising avenue for understanding RL decisions but remain underexplored for continuous action spaces. We propose a novel approach for generating counterfactual explanations in continuous action RL by computing alternative action sequences that improve outcomes while minimizing deviations from the original sequence. Our approach leverages a distance metric for continuous actions and accounts for constraints such as adhering to predefined policies in specific states. Evaluations in two RL domains, Diabetes Control and Lunar Lander, demonstrate the effectiveness, efficiency, and generalization of our approach, enabling more interpretable and trustworthy RL applications.
5539: MultiDreamer3D: Multi-concept 3D Customization with Concept-Aware Diffusion Guidance
Authors: Wooseok Song, Seunggyu Chang, Jaejun Yoo
Location: Montreal | Day: August 19th | Time: 15:00 | Session: CV: Difusion models
Show Abstract
While single-concept customization has been studied in 3D, multi-concept customization remains largely unexplored. To address this, we propose MultiDreamer3D that can generate coherent multi-concept 3D content in a divide-and-conquer manner. First, we generate 3D bounding boxes using an LLM-based layout controller. Next, a selective point cloud generator creates coarse point clouds for each concept. These point clouds are placed in the 3D bounding boxes and initialized into 3D Gaussian Splatting with concept labels, enabling precise identification of concept attributions in 2D projections. Finally, we refine 3D Gaussians via concept-aware interval score matching, guided by concept-aware diffusion. Our experimental results show that MultiDreamer3D not only ensures object presence and preserves the distinct identities of each concept but also successfully handles complex cases such as property change or interaction. To the best of our knowledge, we are the first to address the multi-concept customization in 3D.
5546: On the Power of Optimism in Constrained Online Convex Optimization
Authors: Haobo Zhang, Hengquan Guo, Xin Liu
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: Machine Learning 6/8
Show Abstract
This paper studies the constrained online convex optimization problem (COCO) where the learner makes sequential decisions within a constrained set. We present Optimistic-COCO, an adaptive gradient-based algorithm that incorporates optimistic design with the Lyapunov optimization technique. The proposed algorithm achieves strong theoretical guarantees: 1) Optimistic-COCO provides a tight gradient-variation regret bound and constant constraint violation; 2) Optimistic-COCO is environment-agnostic, utilizing adaptive learning rates that rely solely on causal information. These results resolve an open question posed in prior work regarding whether an adaptive algorithm can achieve problem-dependent regret and constant constraint violation in COCO. We establish these robust guarantees through carefully designed adaptive parameters and a refined multi-step Lyapunov drift analysis. Experimental results further validate our theoretical findings, demonstrating the practical efficacy of the proposed algorithm.
5551: A SAT-based Method for Counting All Singleton Attractors in Boolean Networks
Authors: Rei Higuchi, Takehide Soh, Daniel Le Berre, Morgan Magnin, Mutsunori Banbara, Naoyuki Tamura
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Constraint Satisfaction and Optimization (3/3)
Show Abstract
Boolean networks (BNs) are widely used to model biological regulatory networks. Attractors here hold significant meaning as they represent long-term behaviors such as homeostasis and the results of cell differentiation. As such, computing attractors is of critical importance to guarantee the validity of a model or to assess its stability and robustness. However, this problem is quite challenging when it comes to large real-world models. To overcome the limits of state-of-the-art BDD-based or ASP-based enumeration approaches, we introduce a SAT-based approach to compute fixed points (singleton attractors) of BN and exhibit its merits for counting the number of singleton attractors of large-scale benchmarks well established in the literature.
5567: On Definite Iterated Belief Revision with Belief Algebras
Authors: Hua Meng, Zhiguo Long, Michael Sioutis, Zhengchun Zhou
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Knowledge Representation and Reasoning (1/4)
Show Abstract
Traditional logic-based belief revision research focuses on designing rules to constrain the behavior of revision operators. Frameworks have been proposed to characterize iterated revision rules, but they are often too loose, leading to multiple revision operators that all satisfy the rules under the same belief condition. In many practical applications, such as safety critical ones, it is important to specify a definite revision operator to enable agents to iteratively revise their beliefs in a deterministic way. In this paper, we propose a novel framework for iterated belief revision by characterizing belief information through preference relations. Semantically, both beliefs and new evidence are represented as belief algebras, which provide a rich and expressive foundation for belief revision. Building on traditional revision rules, we introduce additional postulates for revision with belief algebra, including an upper-bound constraint on the outcomes of revision. We prove that the revision result is uniquely determined given the current belief state and new evidence. Furthermore, to make the framework more useful in practice, we develop a particular algorithm for performing the proposed revision process. We argue that this approach may offer a more predictable and principled method for belief revision, making it suitable for real-world applications.
5581: Navigating Social Dilemmas with LLM-based Agents via Consideration of Future Consequences
Authors: Dung Nguyen, Hung Le, Kien Do, Sunil Gupta, Svetha Venkatesh, Truyen Tran
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
Artificial agents with the aid of large language models (LLMs) are effective in various real-world scenarios but struggle to cooperate in social dilemmas. When making decisions under the strain of selecting between long-term consequences and short-term benefits in commonly shared resources, LLM-based agents often exploit the environment, leading to early depletion. Inspired by the concept of consideration of future consequences (CFC), which is well-known in social psychology, we propose a framework to enable the ability to consider future consequences for LLM-based agents, which results in a new kind of agent that we term the CFC-Agent. We enable the CFC-Agent to act toward different levels of consideration for future consequences. Our first set of experiments, where LLM is directly asked to make decisions, shows that agents considering future consequences exhibit sustainable behaviour and achieve high common rewards for the population. Extensive experiments in complex environments showed that the CFC-Agent can manage a sequence of calls to LLM for reasoning and engaging in communication to cooperate with others to resolve the common dilemma better. Finally, our analysis showed that considering future consequences not only affects the final decision but also improves the conversations between LLM-based agents toward a better resolution of social dilemmas.
5678: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
Authors: Benjamin Doerr, Martin S. Krejca, Andre Opris
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: S: Evolutionary computation (2/2)
Show Abstract
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order Ω(n² log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n²), improving over the previous estimate of O(n² log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(n^(k+1)) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2,3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.
5681: Outstanding Orthodontist: No More Artifactual Teeth in Talking Face
Authors: Zibo Su, Ziqi Zhang, Kun Wei, Xu Yang, Cheng Deng
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Computer vision (2/3)
Show Abstract
Audio-driven talking face synthesis (TFS) enables the creation of realistic speaking videos by combining a single facial image with a speech audio clip. Unlike other facial features that naturally deform during speech, teeth represent unique rigid structures whose shape and size should remain constant throughout the video sequence. However, current methods often produce temporal inconsistencies and artifacts in the teeth region, resulting in a less realistic appearance of the generated videos. To address this, we propose OrthoNet, a plug-and-play framework designed to eliminate unrealistic teeth effects in audio-driven TFS. Our method introduces a Detail-oriented Teeth Aligner module, designed to preserve teeth details and adapt to their shape. It works with a Memory-guided Teeth Stabilizer that integrates a long-term memory bank for global teeth structure and a short-term memory module for local temporal dynamics. Through this framework, OrthoNet acts like an orthodontist for existing Audio2Video methods, ensuring that teeth maintain natural rigidity and temporal consistency even under varying degrees of teeth occlusion. Extensive experiments demonstrate that our method makes the teeth in generated videos appear more natural during speech, significantly enhancing the temporal consistency and structural stability of audio-driven video generation.
5788: ChronoFact: Timeline-based Temporal Fact Verification
Authors: Anab Maulana Barik, Wynne Hsu, Mong Li Lee
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Natural Language Processing (1/2)
Show Abstract
Temporal claims, often riddled with inaccuracies, are a significant challenge in the digital misinformation landscape. Fact-checking systems that can accurately verify such claims are crucial for combating misinformation. Current systems struggle with the complexities of evaluating the accuracy of these claims, especially when they include multiple, overlapping, or recurring events. We introduce a novel timeline-based fact verification framework that identify events from both claim and evidence and organize them into their respective chronological timelines. The framework systematically examines the relationships between the events in both claim and evidence to predict the veracity of each claim event and their chronological accuracy. This allows us to accurately determine the overall veracity of the claim. We also introduce a new dataset of complex temporal claims involving timeline-based reasoning for the training and evaluation of our proposed framework. Experimental results demonstrate the effectiveness of our approach in handling the intricacies of temporal claim verification.
5810: Iterated Belief Change as Learning
Authors: Nicolas Schwind, Katsumi Inoue, Sébastien Konieczny, Pierre Marquis
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Knowledge Representation and Reasoning (1/4)
Show Abstract
In this work, we show how the class of improvement operators — a general class of iterated belief change operators — can be used to define a learning model. Focusing on binary classification, we present learning and inference algorithms suited to this learning model and we evaluate them empirically. Our findings highlight two key insights: first, that iterated belief change can be viewed as an effective form of online learning, and second, that the well-established axiomatic foundations of belief change operators offer a promising avenue for the axiomatic study of classification tasks.
5817: Lazy Testing of Machine-Learning Models
Authors: Anastasia Isychev, Valentin Wüstholz, Maria Christakis
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: MTA: Software engineering
Show Abstract
Checking the reliability of machine-learning models is a crucial, but challenging task. Nomos is an existing, automated framework for testing general, user-provided functional properties of models, including so-called hyperproperties expressed over more than one model execution. Nomos aims to find model inputs that expose “bugs”, that is, property violations. However, performing thousands of model invocations during testing is costly both in terms of time and money (for metered APIs, such as OpenAI’s).

We present LaZ (pronounced “lazy”), an extension of Nomos that automatically minimizes the number of model invocations to boost the test throughput and thereby find bugs more efficiently. During test execution, LaZ automatically identifies redundant invocations—invocations where the model output does not affect the final test outcome—and skips them, much like lazy evaluation in certain programming languages. This optimization enables a second one that dynamically reorders model invocations to skip the more expensive ones. As a result, LaZ finds the same number of bugs as Nomos, but does so median 33% and up to 60% faster.
5868: StarFT: Robust Fine-tuning of Zero-shot Models via Spuriosity Alignment
Authors: Younghyun Kim, Jongheon Jeong, Sangkyung Kwak, Kyungmin Lee, Juho Lee, Jinwoo Shin
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
Learning robust representations from data often requires scale, which has led to the success of recent zero-shot models such as CLIP. However, the obtained robustness can easily be deteriorated when these models are fine-tuned on other downstream tasks (e.g., of smaller scales). Previous works often interpret this phenomenon in the context of domain shift, developing fine-tuning methods that aim to preserve the original domain as much as possible. However, in a different context, fine-tuned models with limited data are also prone to learning features that are spurious to humans, such as background or texture. In this paper, we propose StarFT (Spurious Textual Alignment Regularization), a novel framework for fine-tuning zero-shot models to enhance robustness by preventing them from learning spuriosity. We introduce a regularization that aligns the output distribution for spuriosity-injected labels with the original zero-shot model, ensuring that the model is not induced to extract irrelevant features further from these descriptions. We leverage recent language models to get such spuriosity-injected labels by generating alternative textual descriptions that highlight potentially confounding features. Extensive experiments validate the robust generalization of StarFT and its emerging properties: zero-shot group robustness and improved zero-shot classification. Notably, StarFT boosts both worst-group and average accuracy by 14.30% and 3.02%, respectively, in the Waterbirds group shift scenario, where other robust fine-tuning baselines show even degraded performance.
5893: Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games
Authors: Diodato Ferraioli, Giovanna Varricchio
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Game Theory
Show Abstract
In this work, we consider the design of Non-Obviously Manipulable (NOM) mechanisms, mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games: Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences over coalitions are determined by aggregating such scores.
This aggregation results in a utility function for each agent, which enables the evaluation of outcomes via the utilitarian social welfare.
We first prove that, when scores can be arbitrary, every optimal mechanism is NOM; moreover, when scores are limited in a continuous interval, an optimal mechanism that is NOM exists.
Given the hardness of computing optimal outcomes in these settings, we turn our attention to efficient and NOM mechanisms. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that asymptotically match the best-known approximation achievable in polynomial time.
Finally, we focus on discrete scores, where the compatibility of NOM with optimality depends on the specific values.
Therefore, we initiate a systematic analysis to identify which discrete values support this compatibility and which do not.
5905: Performance Guaranteed Poisoning Attacks in Federated Learning: A Sliding Mode Approach
Authors: Huazi Pan, Yanjun Zhang, Leo Yu Zhang, Scott Adams, Abbas Kouzani, Suiyang Khoo
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Federated Learning
Show Abstract
Manipulation of local training data and local updates, i.e., the poisoning attack, is the main threat arising from the collaborative nature of the federated learning (FL) paradigm. Most existing poisoning attacks aim to manipulate local data/models in a way that causes denial-of-service (DoS) issues. In this paper, we introduce a novel attack method, named Federated Learning Sliding Attack (FedSA) scheme, aiming at precisely introducing the extent of poisoning in a subtle controlled manner. It operates with a predefined objective, such as reducing global model’s prediction accuracy by 10%.
FedSA integrates robust nonlinear control-Sliding Mode Control (SMC) theory with model poisoning attacks. It can manipulate the updates from malicious clients to drive the global model towards a compromised state, achieving this at a controlled and inconspicuous rate. Additionally, leveraging the robust control properties of FedSA allows precise control over the convergence bounds, enabling the attacker to set the global accuracy of the poisoned model to any desired level. Experimental results demonstrate that FedSA can accurately achieve a predefined global accuracy with fewer malicious clients while maintaining a high level of stealth and adjustable learning rates.
5912: Improving Efficiency of Answer Set Planning with Rough Solutions from Large Language Models for Robotic Task Planning
Authors: Xinrui Lin, Yangfan Wu, Huanyu Yang, Yuting Huang, Yu Zhang, Jianmin Ji, Yanyong Zhang
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: KRR: Logic programming
Show Abstract
Answer Set Programming (ASP) planning can be used to refine the rough solutions generated by Large Language Models (LLMs) to handle specific restrictions of actions, i.e., reconstruct the rough solutions to be executable, for robotic task planning. However, it is still challenging to efficiently solve ASP programs that have multiple variables with large domains, which prevents the above application of ASP planning from real-world task planning problems. In this paper, we consider how to reduce the domains of variables without losing possible solutions for ASP planning, while given these rough solutions from LLMs. Based on the above reduction, we introduce CLMASP, an approach that couples LLMs with ASP for robotic task planning. We evaluate CLMASP on the VirtualHome platform for common indoor tasks, demonstrating a significant improvement in the executable rate from under 10% to nearly 90% and reducing average ASP planning time from over 2 hours to under 5 seconds. Code is available at https://github.com/CLMASP/CLMASP.
5960: Solving Copyright Infringement on Short Video Platforms: Novel Datasets and an Audio Restoration Deep Learning Pipeline
Authors: Minwoo Oh, Minsu Park, Eunil Park
Location: Montreal | Day: August 21st | Time: 15:00 | Session: CV: videos
Show Abstract
Short video platforms like YouTube Shorts and TikTok face significant copyright compliance challenges, as infringers frequently embed arbitrary background music (BGM) to obscure original soundtracks (OST) and evade content originality detection. To tackle this issue, we propose a novel pipeline that integrates Music Source Separation (MSS) and cross-modal video-music retrieval (CMVMR). Our approach effectively separates arbitrary BGM from the original OST, enabling the restoration of authentic video audio tracks. To support this work, we introduce two domain-specific datasets: OASD-20K for audio separation and OSVAR-160 for pipeline evaluation. OASD-20K contains 20,000 audio clips featuring mixed BGM and OST pairs, while OSVAR160 is a unique benchmark dataset comprising 1,121 video and mixed-audio pairs, specifically designed for short video restoration tasks. Experimental results demonstrate that our pipeline not only removes arbitrary BGM with high accuracy but also restores OSTs, ensuring content integrity. This approach provides an ethical and scalable solution to copyright challenges in user-generated content on short video platforms.
6089: Requirement Patterns for Engineering Multiagent Interaction Protocols
Authors: Amit K. Chopra, Samuel H. Christie V., Munindar P. Singh
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Agent-based and Multi-agent Systems (2/3)
Show Abstract
An interaction protocol specifies how the member agents of a decentralized multiagent system may communicate to satisfy their respective stakeholders’ requirements. We focus on information protocols, which are fully declarative specifications of interaction and support asynchronous communication. We offer Mambo, an approach for protocol design. Mambo identifies common patterns of requirements, provides a notation to express them, and a verification procedure. Mambo incorporates heuristics to generate small internal representations for efficiency. Experimental results demonstrate Mambo’s effectiveness on practical protocols.
6159: First-Order Coalition Logic
Authors: Davide Catta, Rustam Galimullin, Aniello Murano
Location: Montreal | Day: August 20th | Time: 14:00 | Session: KR: Logic
Show Abstract
We introduce First-Order Coalition Logic (FOCL), which combines key intuitions behind Coalition Logic (CL) and Strategy Logic (SL). Specifically, FOCL allows for arbitrary quantification over actions of agents. FOCL is interesting for several reasons. First, we show that FOCL is strictly more expressive than existing coalition logics. Second, we provide a sound and complete axiomatisation of FOCL, which, to the best of our knowledge, is the first axiomatisation of any variant of SL in the literature. Finally, while discussing the satisfiability problem for FOCL, we reopen the question of the recursive axiomatisability of SL.
6179: Optimal Distributed Training With Co-Adaptive Data Parallelism in Heterogeneous Environments
Authors: Lifang Chen, Zhichao Chen, Liqi Yan, Yanyu Cheng, Fangli Guan, Pan Li
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
The computational power required for training deep learning models has been skyrocketing in the past decade as they scale with big data, and has become a very expensive and scarce resource. Therefore, distributed training, which can leverage distributed available computational power, is vital for efficient large-scale model training. However, most previous distributed training frameworks like DDP and DeepSpeed are primarily designed for co-located clusters under homogeneous computing and communication conditions, and hence cannot account for geo-distributed clusters with both computing and communication heterogeneity. To address this challenge, we develop a new data parallel based distributed training framework called Co-Adaptive Data Parallelism (C-ADP). First, we consider a data owner and parameter server that distributes data to and coordinates the collaborative learning across all the computing devices. We employ local training and delayed parameter synchronization to reduce communication costs. Second, we formulate a data parallel scheduling optimization problem to minimize the training time by optimizing data distribution. Third, we devise an efficient algorithm to solve this scheduling problem, and formally prove that the obtained solution is optimal in the asymptotic sense. Experiments on the ImageNet100 dataset demonstrate that C-ADP achieves fast convergence in heterogeneous distributed training environments. Compared to Distributed Data Parallel (DDP) and DeepSpeed, C-ADP achieves 21.6 times and 26.3 times improvements in FLOPS, respectively, and a reduction in training time of about 72% and 47%, respectively.
6190: FedCPD:Personalized Federated Learning with Prototype-Enhanced Representation and Memory Distillation
Authors: Kaili Jin, Li Xu, Xiaoding Wang, Sun-Yuan Hsieh, Jie Wu, Limei Lin
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Federated Learning
Show Abstract
Federated learning, as a distributed learning framework, aims to develop a global model while preserving client privacy. However, heterogeneity of client data leads to fairness issues and reduced performance. Techniques like parameter decoupling and prototype learning appear promising, yet challenges such as forgetting historical data and limited generalization persist. These methods also lack local insights, with locally trained features prone to overfitting, which affects generalization in global parameter aggregation. To address these challenges, we propose FedCPD, a personalized federated learning framework. FedCPD maintains historical information, reduces information loss, and increases personalization through hierarchical feature distillation and cross-layer feature fusion. Moreover, we utilize representation techniques like prototype contrastive learning and prototype alignment to capture diverse client data features, thus improving model generalization and fairness. Experiments show FedCPD outperforms state-of-the-art models, enhancing generalization by up to 10.40% and personalization by up to 4.90%, highlighting its effectiveness and superiority.
6216: Block Circulant Adapter for Large Language Models
Authors: Xinyu Ding, Meiqi Wang, Siyu Liao, Zhongfeng Wang
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Large Language Models
Show Abstract
Fine-tuning large language models (LLMs) is difficult due to their huge model size. Recent Fourier domain-based methods show potential for reducing fine-tuning costs.
We propose a block circulant matrix-based fine-tuning method with a stable training heuristic to leverage the properties of circulant matrices and one-dimensional Fourier transforms to reduce storage and computation costs.
Experiments show that our method uses 14× less number of parameters than VeRA, 16× smaller than LoRA and 32× less FLOPs than FourierFT, while maintaining close or better task performance.
Our approach presents a promising way in frequency domain to fine-tune large models on downstream tasks.
6303: On Temporal ASP with Eager Unfoldable Operators
Authors: Thomas Eiter, Davide Soldà
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
Temporal Equilibrium Logic (TEL) extends Answer Set Programming (ASP) with linear-time temporal operators (LTL), enabling reasoning about dynamic systems. However, TEL enforces strong minimization criteria that may preclude intuitive models. Liveness formulas, for instance, tend to fail to have infinite equilibrium models, as TEL minimization postpones satisfaction forever. We address this limitation by introducing eager temporal operators (eager Until, eager Release, etc.), and present non-disjunctive temporal programs (NDTP) as a framework for modeling dependencies, inertia, and non-determinism. The fragment of tight temporal programs (TTP), which can be recognized efficiently based on automata techniques for loop detections, guarantees polynomial encodability into LTL. Practical examples, such as request-grant protocols and user permissions in distributed systems, illustrate the applicability of our approach.
6309: DFCA: Disentangled Feature Contrastive Learning and Augmentation for Fairer Dermatological Diagnostics
Authors: Pengcheng Zhao, Xiaowei Ding
Location: Montreal | Day: August 21st | Time: 11:30 | Session: ETF: Fairness and diversity
Show Abstract
With the increasing integration of AI in medical research and applications, the issue of fairness has become as critical as diagnostic accuracy. In dermatology diagnosis, the challenge of class-imbalanced data, which is sometimes limited and contains demographic attributes, results in an imbalanced and insufficient representation within the feature space of deep learning models. Besides, feature entanglement within deep learning models confuses skin tone and disease condition information, impairing model performance among vulnerable groups. Moreover, feature entanglement often constrains the efforts to mitigate unfairness, entailing a trade-off between fairness and diagnostic accuracy. This paper introduces the Disentangled Feature Contrastive learning and Augmentation framework (DFCA), aiming to enhance fairness in dermatological diagnoses without compromising accuracy. Initially, DFCA disentangles skin images into disease related and skin-tone features. Subsequently, the two sets of features are projected into normalized spaces for contrastive learning, each modeled by a mixture of von Mises-Fisher (vMF) distributions. DFCA then samples from these vMF distributions to inversely augment the feature space. To further evaluate the fairness-accuracy balance, we propose a new metric, the Accuracy-Fairness Balance Degree (AFBD). Extensive experiments demonstrate that DFCA significantly improves both fairness and accuracy compared to state-of-the-art methods.
6383: Generalized Safe Conditional Syntax Splitting of Belief Bases
Authors: Lars-Phillip Spiegel, Jonas Haldimann, Jesse Heyninck, Gabriele Kern-Isberner, Christoph Beierle
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Knowledge Representation and Reasoning (2/4)
Show Abstract
Splitting techniques in knowledge representation
help focus on relevant parts of a belief base and
reduce the complexity of reasoning generally. In
this paper, we propose a generalization of safe conditional syntax splittings that broadens the applicability of splitting postulates for inductive inference from belief bases. In contrast to safe conditional syntax splitting, our generalized notion supports syntax splittings of a belief base ∆ where the
subbases of ∆ may share atoms and nontrivial conditionals. We illustrate how this new notion overcomes limitations of previous splitting concepts,
and we identify genuine splittings, separating them
from simple splittings that do not provide benefits
for inductive inference from ∆. We introduce adjusted inference postulates based on our generalization of conditional syntax splitting. We evaluate
several inductive inference operators with respect
to these postulates, and show that generalized safe
conditional syntax splitting is a strictly stronger requirement for inductive inference operators, covering more syntax splitting applications.
6392: Robustness in Single-Audience Value-based Abstract Argumentation: Complexity Results
Authors: Bettina Fazzinga, Sergio Flesca, Filippo Furfaro
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
We address the context of Single-Audience Value-Based Abstract Argumentation Framework (AVAF),
where the arguments are labeled with the social values that they promote and
the activation/deactivation of the attacks depends on the audience profile
(expressed as a set of preferences between the social values).
Herein, we introduce a new notion of robustness for measuring the sensitivity of the outcome of the reasoning to the extent of changes in the audience profile.
In particular, for a set of arguments S or a single argument a, we define the robustness degree
of the status of S or a as the maximum number k* of deletions/insertions of preferences
from/into the audience profile that are tolerable, in the sense that S remains an extension
(or a non-extension) or a accepted (or unaccepted) after performing at most k* deletions/insertions.
We introduce the decision problems related to the computation of the robustness degree and focus on thoroughly investigating their computational complexity.
6400: UltraModel: A Modeling Paradigm for Industrial Objects
Authors: Haoran Yang, Yinan Zhang, Qunshan He, Yuqi Ye, Jing Zhao, Wenhai Wang
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
As Industrial 4.0 unfolds and digital twin technology rapidly advances, modeling techniques that can abstract real-world industrial objects into accurate and robust models, referred to modeling for industrial objects (MIO) tasks, have become increasingly crucial. However, existing works still face two major limitations. First, each of these works primarily focuses on modeling a specific industrial object. When the industrial objects change, the proposed methods often struggle to adapt. Second, they fail to fully consider latent relationships within industrial data, limiting the model’s ability to leverage the data and resulting in suboptimal performance. To address these issues, we propose a novel modeling paradigm tailored for MIO tasks, named UltraModel. Specifically, a twin model graph module is designed to construct a customized graph based on the mechanisms of industrial objects and employ graph convolution to generate high-dimensional representations. Then, a multi-scale feature abstraction module and a spatial attention-based feature fusion module are proposed to complement each other in performing multi-scale feature abstraction and fusion on high-dimensional representations. Finally, the outputs are obtained by processing the fused representations through a feedforward network. Experiments on two different industrial objects demonstrate our UltraModel outperforms existing methods, offering a novel perspective for addressing industrial modeling challenges.
6407: Co-Learning of Strategy and Structure Achieves Full Cooperation in Complex Networks with Dynamical Linking
Authors: Xiaoqing Fan, Chin-wing Leung, Paolo Turrini
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Agent-based and Multi-agent Systems (1/3)
Show Abstract
Social dilemmas are an important benchmark to study the emergence of cooperation among autonomous learning agents and impressive results were recently achieved in two-player games by reinforcement learning agents equipped with a partner selection module. However, the same cannot be said for games on networks. When surrounded by many other defectors, cooperators suffer harsher punishments and find it hard to replicate, making mass defection quickly take over. The frameworks studied so far for the emergence of cooperation in social dilemmas on networks have shown the key role of dynamical linking, the capacity of agents to select their own neighbours, but they have also relied on hard-wired heuristics, such as imitation dynamics, designed to favour cooperation. In this paper, we remove this constraint and study a population of agents that can autonomously learn whether to cooperate or defect with any of their neighbours in a social dilemma, as well as whether to form or sever social ties with others. Building on a seminal framework for the emergence of cooperation in complex social networks with dynamical linking, we implement our agents as Sarsa learners with Boltzmann exploration and equipped with partner selection actions. We show, for the first time, that these agents can reach a fully cooperative society without requiring ad-hoc heuristics. In doing so, we confirm the fundamental role of timescales, the relative speed at which strategy and structure updates occur, for the emergence of cooperation, highlighting the intricate interplay between network dynamics and decision-making in agent societies.
6434: MCD-CLIP: Multi-view Chest Disease Diagnosis with Disentangled CLIP
Authors: Songyue Cai, Yujie Mo, Liang Peng, Yucheng Xie, Tao Tong, Xiaofeng Zhu
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Computer vision (2/3)
Show Abstract
Pre-trained methods for multi-view chest X-ray images have demonstrated impressive performance in chest disease diagnosis, but there are still some limitations that need to be addressed. Firstly, many pre-trained methods require full fine-tuning pre-trained models to induce significant computational resource usage and the prior knowledge destruction. Secondly, many pre-trained methods cannot efficiently balance consistency and complementarity among views, leading to information loss and performance degradation. To tackle these issues, we propose MCD-CLIP, a CLIP-based multi-view chest disease diagnosis method. It uses visual prompts and a Prompt-Aligner to align prompts across views, along with the additional text representation for efficient transfer. Moreover, we employ Adapters to disentangle the image representation, maintaining consistency and complementarity from different views. Experimental results on the chest X-ray dataset demonstrate that MCD-CLIP achieves comparable or better performance on a variety of tasks with 94.31% fewer tunable parameters compared to state-of-the-art methods. The source codes are released at https://github.com/YuzunoKawori/MCD-CLIP.
6494: EDGE: Efficient Data Selection for LLM Agents via Guideline Effectiveness
Authors: Yunxiao Zhang, Guanming Xiong, Haochen Li, Wen Zhao
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Natural Language Processing (1/2)
Show Abstract
Large Language Models (LLMs) have shown remarkable capabilities as AI agents. However, existing methods for enhancing LLM-agent abilities often lack a focus on data quality, leading to inefficiencies and suboptimal results in both fine-tuning and prompt engineering. To address this issue, we introduce EDGE, a novel approach for identifying informative samples without needing golden answers. We propose the Guideline Effectiveness (GE) metric, which selects challenging samples by measuring the impact of human-provided guidelines in multi-turn interaction tasks. A low GE score indicates that the human expertise required for a sample is missing from the guideline, making the sample more informative. By selecting samples with low GE scores, we can improve the efficiency and outcomes of both prompt engineering and fine-tuning processes for LLMs. Extensive experiments validate the performance of our method. Our method achieves competitive results on the HotpotQA and WebShop and datasets, requiring 75% and 50% less data, respectively, while outperforming existing methods. We also provide a fresh perspective on the data quality of LLM-agent fine-tuning.
6601: Approximation Fixpoint Theory as a Unifying Framework for Fuzzy Logic Programming Semantics
Authors: Pascal Kettmann, Jesse Heyninck, Hannes Strass
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: KRR: Logic programming
Show Abstract
Fuzzy logic programming is an established approach for reasoning under uncertainty. Several semantics from classical, two-valued logic programming have been generalized to the case of fuzzy logic programs. In this paper, we show that two of the most prominent classical semantics, namely the stable model and the well-founded semantics, can be reconstructed within the general framework of approximation fixpoint theory (AFT).

This not only widens the scope of AFT from two- to many-valued logics, but allows a wide range of existing AFT results to be applied to fuzzy logic programming. As first examples of such applications, we clarify the formal relationship between existing semantics, generalize the notion of stratification from classical to fuzzy logic programs, and devise “more precise” variants of the semantics.
6603: Participatory Budgeting Project Strength via Candidate Control
Authors: Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat
Location: Montreal | Day: August 21st | Time: 15:00 | Session: GTEP: Computational social choice (2/2)
Show Abstract
We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Equal-Shares, but there are natural cases with polynomial-time algorithms. We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments on real-life PB instances.
6614: An Approach to Quantify Plans Robustness in Real-world Applications
Authors: Francesco Percassi, Sandra Castellanos-Paez, Romain Rombourg, Mauro Vallati
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Planning and Scheduling (3/5)
Show Abstract
Automated planning systems are increasingly deployed in real-world applications, often characterised by uncertainty and noise stemming from sensors, actuators, and environmental conditions. Under such circumstances, improving the deployability of generated plans requires assessing their robustness to varying conditions, thereby reducing the need for costly replanning. Replanning can be computationally intensive and may hinder the practical applicability of planning systems. In many domains, such as urban traffic control or underwater exploration, it is often sufficient for plans to reach an acceptable region rather than the exact goal.

A key distinction in this context lies between valid plans (which achieve the intended goal under ideal conditions) and executable plans (which remain feasible under uncertainty or perturbation). This paper formalises the notion of execution-invariant planning tasks, in which plans are robust to noise and uncertainty. To foster the adoption of automated planning in real-world settings, we propose a statistical framework for evaluating plan robustness, offering a quantifiable measure of a plan’s ability to reach a goal within a specified tolerance under diverse perturbations or uncertainty. We validate our approach in two real-world domains, demonstrating its effectiveness.
6615: Human Motion Capture from Loose and Sparse Inertial Sensors with Garment-aware Diffusion Models
Authors: Andela Ilic, Jiaxi Jiang, Paul Streli, Xintong Liu, Christian Holz
Location: Montreal | Day: August 19th | Time: 15:00 | Session: CV: Difusion models
Show Abstract
Motion capture using sparse inertial sensors has shown great promise due to its portability and lack of occlusion issues compared to camera-based tracking.
Existing approaches typically assume that IMU sensors are tightly attached to the human body.
However, this assumption often does not hold in real-world scenarios.
In this paper, we present a new task of full-body human pose estimation using sparse, loosely attached IMU sensors.
To solve this task, we simulate IMU recordings from an existing garment-aware human motion dataset.
We developed transformer-based diffusion models to synthesize loose IMU data and estimate human poses based on this challenging loose IMU data.
In addition, we show that incorporating garment-related parameters while training the model on simulated loose data effectively maintains expressiveness and enhances the ability to capture variations introduced by looser or tighter garments.
Experiments show that our proposed diffusion methods trained on simulated and synthetic data outperformed the state-of-the-art methods quantitatively and qualitatively, opening up a promising direction for future research.
6632: How to Resolve Envy by Adding Goods
Authors: Matthias Bentert, Robert Bredereck, Eva Deltl, Pallavi Jain, Leon Kellerhals
Location: Montreal | Day: August 21st | Time: 15:00 | Session: GTEP: Computational social choice (2/2)
Show Abstract
We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomial-time algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. Notably, although not every instance admits an envy-free solution, our approach allows us to efficiently determine, in polynomial time, whether a solution exists—an aspect that is both theoretically interesting and far from trivial.
6660: Combining MORL with Restraining Bolts to Learn Normative Behaviour
Authors: Emery A. Neufeld, Agata Ciabattoni, Radu Florin Tulcan
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Knowledge Representation and Reasoning (2/4)
Show Abstract
Normative Restraining Bolts (NRBs) adapt the restraining bolt technique (originally developed for safe reinforcement learning) to ensure compliance with social, legal, and ethical norms. While effective, NRBs rely on trial-and-error weight tuning, which hinders their ability to enforce hierarchical norms; moreover, norm updates require retraining. In this paper, we reformulate learning with NRBs as a multi-objective reinforcement learning (MORL) problem, where each norm is treated as a distinct objective. This enables the introduction of Ordered Normative Restraining Bolts (ONRBs), which support algorithmic weight selection, prioritized norms, norm updates, and provide formal guarantees on minimizing norm violations. Case studies show that ONRBs offer a robust and principled foundation for RL-agents to comply with a wide range of norms while achieving their goals.
6682: Proactive Data-driven Scheduling of Business Processes
Authors: Francesca Meneghello, Arik Senderovich, Massimiliano Ronzani, Chiara Di Francescomarino, Chiara Ghidini
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Planning and Scheduling (1/5)
Show Abstract
Proactive scheduling creates robust offline schedules that optimize resource utilization and minimize job flow times. This work addresses scheduling challenges in business processes,
often encountered in service systems, which differ from traditional applications like manufacturing due to inherent uncertainties in activity durations, and human resource availability. We model the business process scheduling problem (BPSP) as a variation of stochastic resource-constrained multi-project scheduling (RCMPSP), and apply process mining to infer unknown parameter values from historical event data. To overcome the randomness in activity durations, we transform the problem into its deterministic counterpart, and prove that the latter provides a lower bound on the Makespan of the stochastic problem. Our approach integrates data-driven Monte Carlo simulation with constraint programming to generate proactive schedules that guarantee, with high probability, that the Makespan remains below a predefined threshold. We evaluate our approach using synthetic datasets with varying levels of uncertainty and size. In addition, we apply the approach to a real-world dataset from an outpatient cancer hospital, demonstrating its effectiveness in optimizing the process Makespan by an average of 5% to 14%.
6687: Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem
Authors: Duc-Cuong Dang, Aneta Neumann, Frank Neumann, Andre Opris, Dirk Sudholt
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: S: Evolutionary computation (2/2)
Show Abstract
Quality diversity (QD) algorithms, an extension of evolutionary algorithms, excel at generating diverse sets of high-quality solutions for complex problems in robotics, games, and combinatorial optimisation. Despite their success, the underlying mechanisms remain poorly understood due to a lack of a theoretical foundation. We address this gap by analysing QD algorithms on the all-pairs-shortest-paths (APSP) problem, a classical planning task that naturally seeks multiple solutions. Using Map-Elites, a prominent QD approach, we leverage its ability to evolve solutions across distinct regions of a behavioural space, which for APSP corresponds to all pairs of nodes in the graph.

Our analysis rigorously demonstrates that evolutionary algorithms using Map-Elites efficiently compute shortest paths for all node pairs in parallel by exploiting synergies in the behavioural space. By appending edges to an existing shortest path, mutation can create optimal solutions in other regions of the behavioural space. Crossover is particularly effective, as it can combine optimal paths from two regions to produce an optimal path for a third region simply by concatenating two shortest paths. Finally, refining the parent selection to facilitate successful crossovers exhibits significant speed-ups compared to standard QD approaches.
6699: The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)
Authors: Renzhong Deng, Weijie Zheng, Benjamin Doerr
Location: Montreal | Day: August 19th | Time: 11:30 | Session: S: Evolutionary computation (1/2)
Show Abstract
This work conducts a first theoretical analysis studying how well the NSGA-III approximates the Pareto front when the population size N is less than the Pareto front size. We show that when N is at least the number Nr of reference points, then the approximation quality, measured by the maximum empty interval (MEI) indicator, on the OneMinMax benchmark is such that there is no empty interval longer than ⌈(5-2√2)n/(Nr-1)⌉. This bound is independent of N, which suggests that further increasing the population size does not increase the quality of approximation when Nr is fixed. This is a notable difference to the NSGA-II with sequential survival selection, where increasing the population size improves the quality of the approximations. We also prove two results indicating approximation difficulties when N<Nr. These theoretical results suggest that the best setting to approximate the Pareto front is Nr=N. In our experiments, we observe that with this setting the NSGA-III computes optimal approximations, very different from the NSGA-II, for which optimal approximations have not been observed so far.
6701: Minimizing Polarization and Disagreement in the Friedkin–Johnsen Model with Unknown Innate Opinions
Authors: Federico Cinus, Atsushi Miyauchi, Yuko Kuroki, Francesco Bonchi
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
The bulk of the literature on opinion optimization in social networks adopts the Friedkin–Johnsen (FJ) opinion dynamics model, in which the innate opinions of all nodes are known: this is an unrealistic assumption.
In this paper, we study opinion optimization under the FJ model without the full knowledge of innate opinions. Specifically, we borrow from the literature a series of objective functions, aimed at minimizing polarization and/or disagreement, and we tackle the budgeted optimization problem, where we can query the innate opinions of only a limited number of nodes.
Given the complexity of our problem, we propose a framework based on three steps: (1) select the limited number of nodes we query, (2) reconstruct the innate opinions of all nodes based on those queried, and (3) optimize the objective function with the reconstructed opinions. For each step of the framework, we present and systematically evaluate several effective strategies. A key contribution of our work is a rigorous error propagation analysis that quantifies how reconstruction errors in innate opinions impact the quality of the final solutions.
Our experiments on various synthetic and real-world datasets show that we can effectively minimize polarization and disagreement even if we have quite limited information about innate opinions.
6719: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II
Authors: Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, Mohammed Lagmah
Location: Montreal | Day: August 19th | Time: 11:30 | Session: S: Evolutionary computation (1/2)
Show Abstract
Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of σ-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.
6750: FedHAN: A Cache-Based Semi-Asynchronous Federated Learning Framework Defending Against Poisoning Attacks in Heterogeneous Clients
Authors: Xiaoding Wang, Bin Ye, Li Xu, Lizhao Wu, Sun-Yuan Hsieh, Jie Wu, Limei Lin
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Data Mining
Show Abstract
Federated learning is vulnerable to model poisoning attacks in which malicious participants compromise the global model by altering the model updates. Current defense strategies are divided into three types: aggregation-based methods, validation dataset-based methods, and update distance-based methods. However, these techniques often neglect the challenges posed by device heterogeneity and asynchronous communication. Even upon identifying malicious clients, the global model may already be significantly damaged, requiring effective recovery strategies to reduce the attacker’s impact. Current recovery methods, which are based on historical update records, are limited in environments with device heterogeneity and asynchronous communication. To address these problems, we introduce FedHAN, a reliable federated learning algorithm designed for asynchronous communication and device heterogeneity. FedHAN customizes sparse models, uses historical client updates to impute missing parameters in sparse updates, dynamically assigns adaptive weights, and combines update deviation detection with update prediction-based model recovery. Theoretical analysis indicates that FedHAN achieves favorable convergence despite unbounded staleness and effectively discriminates between benign and malicious clients. Experiments reveal that FedHAN, compared to leading methods, increases the accuracy of the model by 7.86%, improves the detection accuracy of poisoning attacks by 12%, and enhances the recovery accuracy by 7.26%. As evidenced by these results, FedHAN exhibits enhanced reliability and robustness in intricate and dynamic federated learning scenarios.
6756: On Independence and SCC-Recursiveness in Assumption-Based Argumentation
Authors: Lydia Blümel, Anna Rapberger, Matthias Thimm, Francesca Toni
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
We introduce a notion of conditional independence in (flat) assumption-based argumentation (ABA), where independence between (sets of) assumptions amounts to the presence of information about one set of assumptions not impacting the acceptability of another. We study general properties, computational complexity, and the relation to independence in abstract argumentation. In light of the high computational complexity of deciding independence, we introduce sound methods for checking independence in polynomial time via two different routes: the first utilizes the strongly connected components (SCCs) of the instantiated abstract argumentation framework; the second exploits the structure of the ABA framework directly. Along the way, we introduce the notion of SCC-recursiveness for ABA.
6759: Boosting Visual Knowledge-Intensive Training for LVLMs Through Causality-Driven Visual Object Completion
Authors: Qingguo Hu, Ante Wang, Jia Song, Delai Qiu, Qingsong Liu, Jinsong Su
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: CV: multimodal LLMs
Show Abstract
Large Vision-Language Models (LVLMs) have experienced significant advancements in recent years. However, their performance still falls short in tasks requiring deep visual perception, such as identifying subtle differences between images. A potential cause is the scarcity of visual knowledge in popular instruction-tuning corpora, resulting in inadequate visual perception and reasoning capabilities. To address this challenge, we introduce a self-improvement framework grounded in a novel visual knowledge-intensive task, Causality-driven Visual object Completion (CVC). This task requires LVLMs to infer the masked object in an image based on its causal relationships with the other visible information. We first obtain rich examples cheaply through our automated instance construction pipeline, without relying on sophisticated LVLMs (e.g., GPT-4V) or human assistance. Then, LVLMs effectively self-improve through trial and error learning using these created instances. Our experiments demonstrate substantial gains across four challenging specialized tasks and four widely-used comprehensive benchmarks. Especially on specialized tasks, our method achieves an average improvement of 5.4% and 4.0% compared to the corresponding baselines when utilizing LLaVA-1.5-7B and LLaVA-1.5-13B, respectively. Code and the supplementary file are available at https://github.com/XMUDeepLIT/CVC.
6761: A Finite-State Controller Based Offline Solver for Deterministic POMDPs
Authors: Alex Schutz, Yang You, Matías Mattamala, Ipek Caliskanelli, Bruno Lacerda, Nick Hawes
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Planning and Scheduling (5/5)
Show Abstract
Deterministic partially observable Markov decision processes (DetPOMDPs) often arise in planning problems where the agent is uncertain about its environmental state but can act and observe deterministically. In this paper, we propose DetMCVI, an adaptation of the Monte Carlo Value Iteration (MCVI) algorithm for DetPOMDPs, which builds policies in the form of finite-state controllers (FSCs). DetMCVI solves large problems with a high success rate, outperforming existing baselines for DetPOMDPs. We also verify the performance of the algorithm in a real-world mobile robot forest mapping scenario.
6770: Tree-of-AdEditor: Heuristic Tree Reasoning for Automated Video Advertisement Editing with Large Language Model
Authors: Yuqi Zhang, Bin Guo, Nuo Li, Ying Zhang, Shijie Wang, Zhiwen Yu, Qing Li
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Planning and Scheduling (3/5)
Show Abstract
Video advertising has become a popular marketing strategy on e-commerce platforms, requiring high-level semantic reasoning like selling point discovery, narrative organization. Previous rule-based methods struggle with these complex tasks, and learning-based approaches demand large datasets and high training costs. Recently, Large Language Models have opened incredible opportunities for advancing intelligent video advertisement editing. However, Input-output (IO) prompting and Chain-of-Thought (CoT) struggle to adapt to the nonlinear thinking hierarchy of video editing, where editors iteratively select shots or revert them to explore potential editing solutions. While Tree-of-Thought (ToT) offers a conceptual structure that mirrors this hierarchy, it falls short in aligning with effective video advertising strategies and lacks robust fact-checking mechanisms. To address these, we propose a novel framework, Tree-of-AdEditor (ToAE), which constructs a reasoning tree to mimic human editors, and incorporates domain-specific theories and heuristic fact-checking to identify optimal editing solutions. Specifically, motivated by effective advertisement principles, we develop a "local-global" mechanism to guide LLM in both the shot level and sequence level decision-making. We introduce a visual incoherence pruning module to provide external heuristic fact-checking, ensuring visual attractiveness and reducing computation costs. Quantitative experiments and expert evaluation demonstrate the superiority of our method compared to baselines.
6781: Quantifying the Self-Interest Level of Markov Social Dilemmas
Authors: Richard Willis, Yali Du, Joel Z. Leibo, Michael Luck
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Agent-based and Multi-agent Systems (3/3)
Show Abstract
This paper introduces a novel method for estimating the self-interest level of Markov social dilemmas.
We extend the concept of self-interest level from normal-form games to Markov games, providing a quantitative measure of the minimum reward exchange required to align individual and collective interests.
We demonstrate our method on three environments from the Melting Pot suite, representing either common-pool resources or public goods.
Our results illustrate how reward exchange can enable agents to transition from selfish to collective equilibria in a Markov social dilemma.
This work contributes to multi-agent reinforcement learning by providing a practical tool for analysing complex, multistep social dilemmas.
Our findings offer insights into how reward structures can promote or hinder cooperation, with potential applications in areas such as mechanism design.
6797: Constrained Serial Dictatorships Can Be Fair
Authors: Sylvain Bouveret, Hugo Gilbert, Jérôme Lang, Guillaume Méroué
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Game Theory and Economic Paradigms
Show Abstract
When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence).
Agents who come earlier in the sequence have a larger choice of items; however, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question.
We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling.
Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model.
We conclude with experimental results showing how the optimal sequence is impacted by various parameters.
6838: Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity
Authors: Jiehua Chen, Martin Durand, Christian Hatschka
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Game Theory and Economic Paradigms
Show Abstract
We investigate multi-organizational scheduling problems, building upon the framework introduced by Pascual et al. in 2009. In this setting, multiple organizations each own a set of identical machines and sequential jobs with distinct processing times. The challenge lies in optimally assigning jobs across organizations’ machines to minimize the overall makespan while ensuring no organization’s performance deteriorates. To formalize this fairness constraint, we introduce individual rationality, a game-theoretic concept that guarantees each organization benefits from participation. Our analysis reveals that finding an individually rational schedule with minimum makespan is ΘP2-hard, placing it in a complexity class strictly harder than both NP and coNP. We further extend the model by considering an alternative objective: minimizing the sum of job completion times, both
within individual organizations and across the entire system. The corresponding decision variant proves to be NP-complete. Through comprehensive parameterized complexity analysis of both problems, we provide new insights into these computationally challenging multi-organizational scheduling scenarios.
6841: A Logic of General Attention Using Edge-Conditioned Event Models
Authors: Gaia Belardinelli, Thomas Bolander, Sebastian Watzl
Location: Montreal | Day: August 20th | Time: 14:00 | Session: KR: Logic
Show Abstract
In this work, we present the first general logic of attention. Attention is a powerful cognitive ability that allows agents to focus on potentially complex information, such as logically structured propositions, higher-order beliefs, or what other agents pay attention to. This ability is a strength, as it helps to ignore what is irrelevant, but it can also introduce biases when some types of information or agents are systematically ignored. Existing dynamic epistemic logics for attention cannot model such complex attention scenarios, as they only model attention to atomic formulas. Additionally, such logics quickly become cumbersome, as their size grows exponentially in the number of agents and announced literals. Here, we introduce a logic that overcomes both limitations. First, we generalize edge-conditioned event models, which we show to be as expressive as standard event models yet exponentially more succinct (generalizing both standard event models and generalized arrow updates). Second, we extend attention to arbitrary formulas, allowing agents to also attend to other agents’ beliefs or attention. Our work treats attention as a modality, like belief or awareness. We introduce attention principles that impose closure properties on that modality and that can be used in its axiomatization. Throughout, we illustrate our framework with examples of AI agents reasoning about human attention, demonstrating how such agents can discover attentional biases.
6871: Optimizing Parameters of Quantum Circuits with Sparsity-Inducing Coordinate Descent
Authors: Rudy Raymond, Zichang He
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: Machine Learning 6/8
Show Abstract
Parameterized Quantum Circuit (PQC) is a family of structured quantum circuits that consists of quantum gates whose parameters are optimized with classical computers. With the quest for a potential speedup, there is a need to run larger quantum circuits, which in turn results in the arduous task of parameter optimization. In this paper, we propose a generic method, called Rotolasso, that utilizes sparsity-inducing coordinate descent (CD) to optimize parameters of a PQC for balancing its accuracy and the number of parameterized gates. The use of CD allows significant reduction in the number of quantum circuit runs, and the sparsity in the model leads to simpler and faster PQCs, both of which are important ingredients to overcome limitations of near-term quantum devices. We provide theoretical analyses and demonstrate experiments showing the effectiveness of Rotolasso to solve instances of combinatorial optimization problems.
6876: A Non-Interventionist Approach to Causal Reasoning Based on Lewisian Counterfactuals
Authors: Carlos Aguilera-Ventura, Xinghan Liu, Emiliano Lorini, Dmitry Rozplokhas
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Knowledge Representation and Reasoning (3/4)
Show Abstract
We present a computationally grounded semantics for counterfactual conditionals in which i) the state in a model is decomposed into two elements: a propositional valuation and a causal base in propositional form that represents the causal information available at the state; and ii) the comparative similarity relation between states is computed from the states’ two components. We show that, by means of our semantics, we can elegantly formalize the notion of actual cause without recurring to the primitive notion of intervention. Furthermore, we provide a succinct formulation of the model checking problem for a language of counterfactual conditionals in our semantics. We show that this problem is PSPACE-complete and provide a reduction of it into QBF that can be used for automatic verification of causal properties.
6890: Α Descent-based Method on the Duality Gap for Solving Zero-sum Games
Authors: Michail Fasoulakis, Evangelos Markakis, Georgios Roussakis, Christodoulos Santorinaios
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Game Theory
Show Abstract
We focus on the design of algorithms for finding equilibria in 2-player zero-sum games. Although it is well known that such problems can be solved by a single linear program, there has been a surge of interest in recent years for simpler algorithms, motivated in part by applications in machine learning. Our work proposes such a method, inspired by the observation that the duality gap (a standard metric for evaluating convergence in min-max optimization problems) is a convex function for bilinear zero-sum games. To this end, we analyze a descent-based approach, variants of which have also been used as a subroutine in a series of algorithms for approximating Nash equilibria in general non-zero-sum games.
In particular, we study a steepest descent approach, by finding the direction that minimises the directional derivative of the duality gap function.
Our main theoretical result is that the derived algorithms achieve a geometric decrease in the duality gap until we reach an approximate equilibrium. Finally, we complement this with an experimental evaluation, which provides promising findings. Our algorithm is comparable with (and in some cases outperforms) some of the standard approaches for solving 0-sum games, such as OGDA (Optimistic Gradient Descent/Ascent), even with thousands of available strategies per player.
6896: A Sequent Calculus for Answer Set Entailment
Authors: Thomas Eiter, Tobias Geibinger
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: KRR: Logic programming
Show Abstract
Answer Set Programming (ASP) is a popular nonmonotonic formalism used for common-sense reasoning and problem-solving based on stable model semantics. Equilibrium logic is a generalisation of ASP for arbitrary propositional theories and thus provides a logical characterisation of the nonmonotonic stable model semantics. In difference to classical logic, which can be defined via proof or model theory, nonmonotonic reasoning formalisms are defined via their models exclusively. Equilibrium logic is no exception here, as it has no proper proof-theoretic axiomatisation. Besides this being a theoretical imbalance, it also has consequences regarding notions of justification and explainability. In this work, we fill this gap by providing a sequent calculus for answer set entailment. Our calculus builds upon ideas from existing calculi for other nonmonotonic formalisms and utilises calculi for the logic of here and there, which is the underlying base logic of equilibrium logic. We show that the calculus is sound and complete and discuss pitfalls as well as alternative axiomatisations. Finally, we address how our approach can be of use for explainability in ASP.
6901: Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy
Authors: Mingfeng Li, Weijie Zheng, Benjamin Doerr
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: S: Evolutionary computation (2/2)
Show Abstract
Different from single-objective evolutionary algorithms, where non-elitism is an established concept, multi-objective evolutionary algorithms almost always select the next population in a greedy fashion. In the only notable exception, a stochastic selection mechanism was recently proposed for the SMS-EMOA and was proven to speed up computing the Pareto front of the bi-objective jump benchmark with problem size n and gap parameter k by a factor of max{1,2^(k/4)/n}. While this constitutes the first proven speed-up from non-elitist selection, suggesting a very interesting research direction, it has to be noted that a true speed-up only occurs for k ≥ 4log(n), where the runtime is super-polynomial, and that the advantage reduces for larger numbers of objectives as shown in a later work. In this work, we propose a different non-elitist selection mechanism based on aging, which exempts individuals younger than a certain age from a possible removal. This remedies the two shortcomings of stochastic selection: We prove a speed-up by a factor of max{1,Θ(k)^(k-1)}, regardless of the number of objectives. In particular, a positive speed-up can already be observed for constant k, the only setting for which polynomial runtimes can be witnessed. Overall, this result supports the use of non-elitist selection schemes, but suggests that aging-based mechanisms can be considerably more powerful than stochastic selection mechanisms.
6902: The Core of Approval-Based Committee Elections with Few Seats
Authors: Dominik Peters
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Game Theory and Economic Paradigms
Show Abstract
In an approval-based committee election, the goal is to select a committee consisting of k out of m candidates, based on n voters who each approve an arbitrary number of the candidates. The core of such an election consists of all committees that satisfy a certain stability property which implies proportional representation. In particular, committees in the core cannot be "objected to" by a coalition of voters who is underrepresented. The notion of the core was proposed in 2016, but it has remained an open problem whether it is always non-empty. We prove that core committees always exist when k ≤ 8, for any number of candidates m and any number of voters n, by showing that the Proportional Approval Voting (PAV) rule, proposed by Thiele in 1895, always satisfies the core when k ≤ 7 and always selects at least one committee in the core when k = 8. We also develop an artificial rule based on recursive application of PAV, and use it to show that the core is non-empty whenever there are m ≤ 15 candidates, for any committee size k ≤ m and any number of voters n. These results are obtained with the help of computer search using linear programs.
6913: Are Large Language Models Fluent in Declarative Process Mining?
Authors: Valeria Fionda, Antonio Ielo, Francesco Ricca
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Knowledge Representation and Reasoning (4/4)
Show Abstract
Recent advancements in AI have made LLMs valuable tools for automating the interpretation of textual descriptions of business processes and for converting formal process specifications into natural language. However, there are no practical methodologies or systematic assessments to ensure these automatic translations are faithful. This paper proposes a novel approach, based on an auxiliary bidirectional translation task, to assess LLMs performance quantitatively; also, it also empirically evaluates the performance of state-of-the-art LLMs for bidirectional translations between natural language and declarative formal process specifications. The results reveal substantial variability in performance among the LLMs, highlighting the importance of LLM selection and confirming the need for a robust method for assessing LLMs’ outputs.
6919: Heterophily-Aware Personalized PageRank for Node Classification
Authors: Giuseppe Pirrò
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
Node classification in heterophilous graphs, where connected nodes often have different characteristics, which presents a significant challenge. We introduce HAPPY, which combines heterophily-aware random walks with targeted subgraph extraction. Our approach enhances Personalized PageRank by incorporating both label and feature diversity into the random walk process. Through theoretical analysis, we demonstrate that HAPPY effectively captures both homophilous and heterophilous relationships. Comprehensive experiments validate our method’s state-of-the-art performance across challenging heterophilous benchmarks.
6926: What Can We Learn From MIMO Graph Convolutions?
Authors: Andreas Roth, Thomas Liebig
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
Most graph neural networks (GNNs) utilize approximations of the general graph convolution derived in the graph Fourier domain. While GNNs are typically applied in the multi-input multi-output (MIMO) case, the approximations are performed in the single-input single-output (SISO) case. In this work, we first derive the MIMO graph convolution through the convolution theorem and approximate it directly in the MIMO case. We find the key MIMO-specific property of the graph convolution to be operating on multiple computational graphs, or equivalently, applying distinct feature transformations for each pair of nodes. As a localized approximation, we introduce localized MIMO graph convolutions (LMGCs), which generalize many linear message-passing neural networks. For almost every choice of edge weights, we prove that LMGCs with a single computational graph are injective on multisets, and the resulting representations are linearly independent when more than one computational graph is used. Our experimental results confirm that an LMGC can combine the benefits of various methods.
6933: Curriculum Abductive Learning for Mitigating Reasoning Shortcuts
Authors: Wen-Da Wei, Xiao-Wen Yang, Jie-Jing Shao, Lan-Zhe Guo
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Machine Learning (2/4)
Show Abstract
Abductive Learning (ABL), a prominent neural-symbolic learning algorithm, integrates perception models with logical reasoning via intermediate symbolic concepts, substantially improving the interpretability and generalization of AI systems. However, a significant challenge in this domain is the issue of reasoning shortcuts, where the system achieve high final prediction accuracy but generate incorrect intermediate concept inferences, severely
undermining ABL’s interpretability and generalization capabilities. Current mitigation methods to this problem often neglect potential correlations among training samples, leading to suboptimal performances. This paper innovatively reveals that simple samples can facilitate the learning of intermediate concepts in complex samples, prompting our proposed method Curriculum Abductive Learning (CurABL) technique. This approach employs a curriculum training strategy, integrating a knowledge transfer mechanism from simple to complex samples, effectively addressing the issue of reasoning shortcuts. Comprehensive experimental results demonstrate that the CurABL method substantially improves the ABL framework’s capability to extract intermediate concepts especially in difficult tasks and accelerates the training convergence rate, thus markedly enhancing its robustness against reasoning shortcuts.
6938: GCNT: Graph-Based Transformer Policies for Morphology-Agnostic Reinforcement Learning
Authors: Yingbo Luo, Meibao Yao, Xueming Xiao
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Robotics
Show Abstract
Training a universal controller for robots with different morphologies is a promising research trend, since it can significantly enhance the robustness and resilience of the robotic system. However, diverse morphologies can yield different dimensions of state space and action space, making it difficult to comply with traditional policy networks. Existing methods address this issue by modularizing the robot configuration, while do not adequately extract and utilize the overall morphological information, which has been proven crucial for training a universal controller. To this end, we propose GCNT, a morphology-agnostic policy network based on improved Graph Convolutional Network (GCN) and Transformer. It exploits the fact that GCN and Transformer can handle arbitrary number of modules to achieve compatibility with diverse morphologies. Our key insight is that the GCN is able to efficiently extract morphology information of robots, while Transformer ensures that it is fully utilized by allowing each node of the robot to communicate this information directly. Experimental results show that our method can generate resilient locomotion behaviors for robots with different configurations, including zero-shot generalization to robot morphologies not seen during training. In particular, GCNT achieved the best performance on 8 tasks in the 2 standard benchmarks.
6940: Toward Reliable Scientific Hypothesis Generation: Evaluating Truthfulness and Hallucination in Large Language Models
Authors: Guangzhi Xiong, Eric Xie, Corey Williams, Myles Kim, Amir Hassan Shariatmadari, Sikun Guo, Stefan Bekiranov, Aidong Zhang
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: LLM applications
Show Abstract
Large language models (LLMs) have shown significant potential in scientific disciplines such as biomedicine, particularly in hypothesis generation, where they can analyze vast literature, identify patterns, and suggest research directions. However, a key challenge lies in evaluating the truthfulness of generated hypotheses, as verifying their accuracy often requires substantial time and resources. Additionally, the hallucination problem in LLMs can lead to the generation of hypotheses that appear plausible but are ultimately incorrect, undermining their reliability. To facilitate the systematic study of these challenges, we introduce TruthHypo, a benchmark for assessing the capabilities of LLMs in generating truthful scientific hypotheses, and KnowHD, a knowledge-based hallucination detector to evaluate how well hypotheses are grounded in existing knowledge. Our results show that LLMs struggle to generate truthful hypotheses. By analyzing hallucinations in reasoning steps, we demonstrate that the groundedness scores provided by KnowHD serve as an effective metric for filtering truthful hypotheses from the diverse outputs of LLMs. Human evaluations further validate the utility of KnowHD in identifying truthful hypotheses and accelerating scientific discovery. Our data and source code are available at https://github.com/Teddy-XiongGZ/TruthHypo.
6948: Cap-and-Penalize: Competitive Mechanisms for Multi-Phase Regularized Online Allocation
Authors: Seyedehkimia Alaviyar, Faraz Zargari, John Tyler, Yunwei Ryan Li, Xiaoqi Tan
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Game Theory and Economic Paradigms
Show Abstract
This paper introduces a novel mechanism for online allocation with multi-phase, non-separable regularizers, termed Cap-and-Penalize (CnP), inspired by real-world applications such as cap-and-tax policies in carbon pricing. The CnP regularizer models a multi-phase cost structure, imposing a monotone convex penalty when total allocation exceeds a predefined level (soft cap) and enforcing a strict limit (hard cap) beyond which allocation is prohibited. Our contributions are twofold: (1) we propose an online mechanism for CnP-regularized allocation without per-step resource constraints, which operates as a simple and intuitive posted-price mechanism, but achieves the best-possible guarantee among all possible online algorithms; (2) we tackle the more complex setting with per-step resource constraints by decomposing the regularizer into local components, yielding a similar mechanism with time-dependent marginal pricing functions. To establish the tightness of our results in both settings, we introduce a representative function-based approach that transforms the lower-bound proof into the problem of solving an ordinary differential equation with boundary conditions. We believe that this technique has the potential to be applied to other similar online optimization problems.
6952: Grounding Methods for Neural-Symbolic AI
Authors: Rodrigo Castellano Ontiveros, Francesco Giannini, Marco Gori, Giuseppe Marra, Michelangelo Diligenti
Location: Montreal | Day: August 21st | Time: 11:30 | Session: ML: Neurosymbolic AI
Show Abstract
A large class of Neural-Symbolic (NeSy) methods employs a machine learner to process the input entities, while relying on a reasoner based on First-Order Logic to represent and process more complex relationships among the entities. A fundamental role for these methods is played by the process of logic grounding, which determines the relevant substitutions for the logic rules using a (sub)set of entities.
Some NeSy methods use an exhaustive derivation of all possible substitutions, preserving the full expressive power of the logic knowledge, but leading to a combinatorial explosion of the number of ground formulas to consider and, therefore, strongly limiting their scalability. Other methods rely on heuristic-based selective derivations, which are generally more computationally efficient, but lack a justification and provide no guarantees of preserving the information provided to and returned by the reasoner.
Taking inspiration from multi-hop symbolic reasoning, this paper proposes a parametrized family of grounding methods generalizing classic Backward Chaining. Different selections within this family allow to obtain commonly employed grounding methods as special cases, and to control the trade-off between expressiveness and scalability of the reasoner.
The experimental results show that the selection of the grounding criterion is often as important as the NeSy method itself.
6965: Efficient Algorithms for Electing Successive Committees
Authors: Pallavi Jain, Andrzej Kaczmarczyk
Location: Montreal | Day: August 21st | Time: 15:00 | Session: GTEP: Computational social choice (2/2)
Show Abstract
In a recently introduced model of successive committee elections, for a given set of ordinal or approval preferences one aims to find a sequence of a given length of “best” same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.
6970: Beyond the Map: Learning to Navigate Unseen Urban Dynamics Using Diffusion-Guided Deep Reinforcement Learning
Authors: Monu Nagar, Debasis Das
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Robotics
Show Abstract
Vision-based motion planning is a crucial task in Autonomous Driving (AD). Recent advancements in urban AD show that integrating Imitation Learning (IL) with Deep Reinforcement Learning (DRL) improves decision-making to be more like humans. However, IL methods depend on expert demonstrations to learn the optimal policy. The main drawback of this approach is the assumption that expert demonstrations are always optimal, which is not always true in real-world settings. This creates challenges in adapting to diverse weather conditions and dynamic traffic scenarios, often resulting in higher collision rates and increased risks to pedestrian safety. To address these challenges, we propose a Diffusion-Guided Deep Reinforcement Learning (DGDRL) framework that integrates a diffusion model with a Soft Actor-Critic DRL method to effectively mitigate environmental uncertainties and enable self-learning beyond the training maps for new tasks. This framework follows a novel modified partially observable Markov decision process (mPOMDP) to choose optimal action from original and diffusion-generated observations, ensuring that the policy behavior remains consistent with the current action. We use the CARLA NoCrash benchmark to train and evaluate the proposed framework. The method is validated in diverse urban environments (e.g., empty, regular, and dense) across multiple towns. Additionally, we compare our model against state-of-the-art techniques to ensure robustness and generalizability to new environments. The project page and code are available at the link https://autovisionproject.github.io/project/.
6973: Optimal Metric Distortion for Matching on the Line
Authors: Aris Filos-Ratsikas, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, Alexandros A. Voudouris
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Game Theory and Economic Paradigms
Show Abstract
We study the distortion of one-sided and two-sided matching problems on the line. In the one-sided case, n agents need to be matched to n items, and each agent’s cost in a matching is their distance from the item they were matched to. We propose an algorithm that is provided only with ordinal information regarding the agents’ preferences (each agent’s ranking of the items from most- to least-preferred) and returns a matching aiming to minimize the social cost with respect to the agents’ true (cardinal) costs. We prove that our algorithm simultaneously achieves the best-possible approximation of 3 (known as distortion) with respect to a variety of social cost measures which include the utilitarian and egalitarian social cost. In the two-sided case, where the agents need be matched to n other agents and both sides report their ordinal preferences over each other, we show that it is always possible to compute an optimal matching. In fact, we show that this optimal matching can be achieved using even less information, and we provide bounds regarding the sufficient number of queries.
6975: Optimal Capacity Modification for Stable Matchings with Ties
Authors: Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar
Location: Montreal | Day: August 21st | Time: 15:00 | Session: GTEP: Computational social choice (2/2)
Show Abstract
We consider the Hospitals/Residents (HR) problem in the presence of ties in preference lists of hospitals. Among the three notions of stability, viz. weak, strong, and super stability, we focus on strong stability. Strong stability is appealing both theoretically and practically; however, its existence is not guaranteed. In this paper, our objective is to optimally augment the quotas of hospitals to ensure that a strongly stable matching exists in the modified instance. Such an augmentation is guaranteed to exist when resident preference lists are strict. We explore two natural optimization criteria: (i) minimizing the total capacity increase across all hospitals (MINSUM) and (ii) minimizing the maximum capacity increase for any hospital (MINMAX). We show that the MINSUM problem admits a polynomial-time algorithm, whereas the MINMAX problem is NP-hard. We prove an analogue of the Rural Hospitals theorem for the MINSUM problem. When each hospital incurs a cost for a unit increase in its quota, the MINSUM problem becomes NP-hard, even for 0/1 costs. In fact, we show that the problem cannot be approximated to any multiplicative factor. We also present a polynomial-time algorithm for optimal MINSUM augmentation when a specified subset of edges is required to be included in the matching.
6978: Beyond Winning Strategies: Admissible and Admissible Winning Strategies for Quantitative Reachability Games
Authors: Karan Muvvala, Qi Heng Ho, Morteza Lahijanian
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MAS: Formal verification, validation and synthesis
Show Abstract
Classical reactive synthesis approaches aim to synthesize a reactive system that always satisfies a given specification. These approaches often reduce to playing a two-player zero-sum game where the goal is to synthesize a winning strategy. However, in many pragmatic domains, such as robotics, a winning strategy does not always exist, yet it is desirable for the system to make an effort to satisfy its requirements instead of "giving up." To this end, this paper investigates the notion of admissible strategies, which formalize "doing-your-best", in quantitative reachability games. We show that, unlike the qualitative case, memoryless strategies are not sufficient to capture all admissible strategies, making synthesis a challenging task. In addition, we prove that admissible strategies always exist but may produce undesirable optimistic behaviors. To mitigate this, we propose admissible winning strategies, which enforce the best possible outcome while being admissible. We show that both strategies always exist but are not memoryless. We provide necessary and sufficient conditions for the existence of both strategies and propose synthesis algorithms. Finally, we illustrate the strategies on gridworld and robot manipulator domains.
6988: Counterfactual Explanations Under Model Multiplicity and Their Use in Computational Argumentation
Authors: Gianvincenzo Alfano, Adam Gould, Francesco Leofante, Antonio Rago, Francesca Toni
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
Counterfactual explanations (CXs) are widely recognised as an essential technique for providing recourse recommendations for AI models.
However, it is not obvious how to determine CXs in model multiplicity scenarios, where equally performing but different models can be obtained for the same task.
In this paper, we propose novel qualitative and quantitative definitions of CXs based on explicit, nested quantification over (groups) of model decisions.
We also study properties of these notions and identify decision problems of interest therefor.
While our CXs are broadly applicable, in this paper we instantiate them within computational argumentation where model multiplicity naturally emerges, e.g. with incomplete and case-based argumentation frameworks.
We then illustrate the suitability of our CXs for model multiplicity in legal and healthcare contexts, before analysing the complexity of the associated decision problems.
6990: Rule-Guided Reinforcement Learning Policy Evaluation and Improvement
Authors: Martin Tappler, Ignacio D. Lopez-Miguel, Sebastian Tschiatschek, Ezio Bartocci
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Reinforcement Learning (2/2)
Show Abstract
We consider the challenging problem of using domain knowledge to improve deep reinforcement learning policies. To this end, we propose LEGIBLE, a novel approach, following a multi-step process, which starts by mining rules from a deep RL policy, constituting a partially symbolic representation. These rules describe which decisions the RL policy makes and which it avoids making. In the second step, we generalize the mined rules using domain knowledge expressed as metamorphic relations. We adapt these relations from software testing to RL to specify expected changes of actions in response to changes in observations. The third step is evaluating generalized rules to determine which generalizations improve performance when enforced. These improvements show weaknesses in the policy, where it has not learned the general rules and thus can be improved by rule guidance. LEGIBLE supported by metamorphic relations provides a principled way of expressing and enforcing domain knowledge about RL environments. We show the efficacy of our approach by demonstrating that it effectively finds weaknesses, accompanied by explanations of these weaknesses, in eleven RL environments and by showcasing that guiding policy execution with rules improves performance w.r.t. gained reward.
7002: SPoRt – Safe Policy Ratio: Certified Training and Deployment of Task Policies in Model-Free RL
Authors: Jacques Cloete, Nikolaus Vertovec, Alessandro Abate
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
To apply reinforcement learning to safety-critical applications, we ought to provide safety guarantees during both policy training and deployment. In this work we present novel theoretical results that provide a bound on the probability of violating a safety property for a new task-specific policy in a model-free, episodic setup: the bound, based on a ‘maximum policy ratio’ that is computed with respect to a ‘safe’ base policy, can also be more generally applied to temporally-extended properties (beyond safety) and to robust control problems. We thus present SPoRt, which also provides a data-driven approach for obtaining such a bound for the base policy, based on scenario theory, and which includes Projected PPO, a new projection-based approach for training the task-specific policy while maintaining a user-specified bound on property violation. Hence, SPoRt enables the user to trade off safety guarantees in exchange for task-specific performance. Accordingly, we present experimental results demonstrating this trade-off, as well as a comparison of the theoretical bound to posterior bounds based on empirical violation rates.
7005: Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator
Authors: Abderrahim Bendahi, Benjamin Doerr, Adrien Fradin, Johannes F. Lutzeyer
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Search
Show Abstract
The move-acceptance hyper-heuristic was recently shown to be able to leave local optima with astonishing efficiency (Lissovoi et al., Artificial Intelligence (2023)). In this work, we propose two modifications to this algorithm that demonstrate impressive performances on a large class of benchmarks including the classic CLIFF_d and JUMP_m function classes. (i) Instead of randomly choosing between the only-improving and any-move acceptance operator, we take this choice via a simple two-state Markov chain. This modification alone reduces the runtime on JUMP_m functions with gap parameter m from 𝛺(n²ᵐ⁻¹) to O(nᵐ⁺¹). (ii) We then replace the all-moves acceptance operators with the operator that only accepts worsenings. Such a, counter-intuitive, operator has not been used before in the literature. However, our proofs show that our only-worsening operator can greatly help in leaving local optima, reducing, e.g., the runtime on Jump functions to O(n³ log n) independent of the gap size. In general, we prove a remarkably good runtime of O(nᵏ⁺¹ log n) for our Markov move-acceptance hyper-heuristic on all members of a new benchmark class SEQOPT_k, which contains a large number of functions having k successive local optima, and which contains the commonly studied JUMP_m and CLIFF_d functions for k=2.
7011: A-I-RAVEN and I-RAVEN-Mesh: Two New Benchmarks for Abstract Visual Reasoning
Authors: Mikołaj Małkiński, Jacek Mańdziuk
Location: Montreal | Day: August 21st | Time: 11:30 | Session: CV: Benchmarks
Show Abstract
We study generalization and knowledge reuse capabilities of deep neural networks in the domain of abstract visual reasoning (AVR), employing Raven’s Progressive Matrices (RPMs), a recognized benchmark task for assessing AVR abilities. Two knowledge transfer scenarios referring to the I-RAVEN dataset are investigated. Firstly, inspired by generalization assessment capabilities of the PGM dataset and popularity of I-RAVEN, we introduce Attributeless-I-RAVEN (A-I-RAVEN), a benchmark with 10 generalization regimes that allow to systematically test generalization of abstract rules applied to held-out attributes at various levels of complexity (primary and extended regimes). In contrast to PGM, A-I-RAVEN features compositionality, a variety of figure configurations, and does not require substantial computational resources. Secondly, we construct I-RAVEN-Mesh, a dataset that enriches RPMs with a novel component structure comprising line-based patterns, facilitating assessment of progressive knowledge acquisition in transfer learning setting. We evaluate 13 strong models from the AVR literature on the introduced datasets, revealing their specific shortcomings in generalization and knowledge transfer.
7020: Advancing Generalization Across a Variety of Abstract Visual Reasoning Tasks
Authors: Mikołaj Małkiński, Jacek Mańdziuk
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Machine Learning (2/4)
Show Abstract
The abstract visual reasoning (AVR) domain presents a diverse suite of analogy-based tasks devoted to studying model generalization. Recent years have brought dynamic progress in the field, particularly in i.i.d. scenarios, in which models are trained and evaluated on the same data distributions. Nevertheless, o.o.d. setups that assess model generalization to new test distributions remain challenging even for the most recent models. To advance generalization in AVR tasks, we present the Pathways of Normalized Group Convolution model (PoNG), a novel neural architecture that features group convolution, normalization, and a parallel design. We consider a wide set of AVR benchmarks, including Raven’s Progressive Matrices and visual analogy problems with both synthetic and real-world images. The experiments demonstrate strong generalization capabilities of the proposed model, which in several settings outperforms the existing literature methods.
7030: HGEN: Heterogeneous Graph Ensemble Networks
Authors: Jiajun Shen, Yufei Jin, Kaibu Feng, Yi He, Xingquan Zhu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: ML: Reinforcement learning (1/2)
Show Abstract
This paper presents HGEN that pioneers ensemble learning for heterogeneous graphs. We argue that the heterogeneity in node types, nodal features, and local neighborhood topology poses significant challenges for ensemble learning, particularly in accommodating diverse graph learners. Our HGEN framework ensembles multiple learners through a meta-path and transformation-based optimization pipeline to uplift classification accuracy. Specifically, HGEN uses meta-path combined with random dropping to create Allele Graph Neural Networks (GNNs), whereby the base graph learners are trained and aligned for later ensembling. To ensure effective ensemble learning, HGEN presents two key components:1) a residual-attention mechanism to calibrate allele GNNs of different meta-paths, thereby enforcing node embeddings to focus on more informative graphs to improve base learner accuracy, and 2) a correlation-regularization term to enlarge the disparity among embedding matrices generated from different meta-paths, thereby enriching base learner diversity. We analyze the convergence of HGEN and attest its higher regularization magnitude over simple voting. Experiments on five heterogeneous networks validate that HGEN consistently outperforms its state-of-the-art competitors by substantial margin. Codes are available at https://github.com/Chrisshen12/HGEN.
7033: On Integrating Logical Analysis of Data into Random Forests
Authors: David Ing, Said Jabbour, Lakhdar Saïs
Location: Montreal | Day: August 20th | Time: 10:00 | Session: AI Ethics, Trust, Fairness (1/3)
Show Abstract
Random Forests (RFs) are one of the most popular classifiers in machine learning. RF is an ensemble learning method that combines multiple Decision Trees (DTs), providing a more robust and accurate model than a single DT. However, one of the main step of RFs is the random selection of many different features during the construction phase of DTs, resulting in a forest with various features, which makes it difficult to extract short and concise explanations. In this paper, we propose integrating Logical Analysis of Data (LAD) into RFs. LAD is a pattern learning framework that combines optimization, Boolean functions, and combinatorial theory. One of its main goals is to generate minimal support sets (MSSes) that discriminate between different groups of data. More precisely, we show how to enhance the classical RF algorithm by randomly choosing MSSes rather than randomly choosing feature subsets that potentially contain irrelevant features for constructing DTs. Experiments on benchmark datasets reveal that integrating LAD into classical RFs using MSSes can maintain similar performance in terms of accuracy, produce forests of similar size, reduce the set of used features, and enable the extraction of significantly shorter explanations compared to classical RFs.
7034: Assessing the Exposure to Public Knowledge in Policy-Protected Description Logic Ontologies
Authors: Gianluca Cima, Domenico Lembo, Lorenzo Marconi, Riccardo Rosati, Domenico Fabio Savo
Location: Montreal | Day: August 20th | Time: 14:00 | Session: KR: Logic
Show Abstract
We propose a general framework for assessing the exposure of sensitive knowledge in policy-protected knowledge bases (KBs), where knowledge is represented as logical theories and data protection policies are defined declaratively using epistemic dependencies. The framework models scenarios in which confidential parts of the KB may be publicly known due to security breaches. We study two fundamental decision problems: determining whether the exposed knowledge violates the data protection policy (leakage), and whether there exists a secure view of the KB that complies with the policy. We analyze the computational complexity (specifically, data complexity) of these problems, focusing on the DL-Lite_R and EL_\bot Description Logics. Our findings show that, for DL-Lite_R with restricted forms of policy, both the problems can be efficiently solved through query rewriting methods. For EL_\bot, we establish conditions for tractable computational bounds. Our results highlight the potential of this framework for practical applications in confidentiality-preserving knowledge management.
7051: Online Resource Sharing: Better Robust Guarantees via Randomized Strategies
Authors: David X. Lin, Daniel Hall, Giannis Fikioris, Siddhartha Banerjee, Éva Tardos
Location: Montreal | Day: August 21st | Time: 15:00 | Session: Agent-based and Multi-agent Systems (3/3)
Show Abstract
We study the problem of fair online resource allocation via non-monetary mechanisms, where multiple agents repeatedly share a resource without monetary transfers. Previous work has shown that every agent can guarantee 1/2 of their ideal utility (the highest achievable utility given their fair share of resources) robustly, i.e., under arbitrary behavior by the other agents. While this 1/2-robustness guarantee has now been established under very different mechanisms, including pseudo-markets and dynamic max-min allocation, improving on it has appeared difficult.

In this work, we obtain the first significant improvement on the robustness of online resource sharing. In more detail, we consider the widely-studied repeated first-price auction with artificial currencies. Our main contribution is to show that a simple randomized bidding strategy can guarantee each agent a 2 – √2 ≈ 0.59 fraction of her ideal utility, irrespective of others’ bids. Specifically, our strategy requires each agent with fair share α to use a uniformly distributed bid whenever her value is in the top α-quantile of her value distribution. Our work almost closes the gap to the known 1 – 1/e ≈ 0.63 hardness for robust resource sharing; we also show that any static (i.e., budget independent) bidding policy cannot guarantee more than a 0.6-fraction of the ideal utility, showing our technique is almost tight.
7059: Featured Argumentation Framework: Semantics and Complexity
Authors: Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Irina Trubitsyna
Location: Montreal | Day: August 19th | Time: 15:00 | Session: KRR: Argumentation
Show Abstract
Dung’s Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning tasks more intuitive and/or expressive. We present a novel extension of AF called Featured AF (FAF), where each argument has associated a set of features expressed by means of unary and binary facts.
In such a context, a query is expressed by means of a conjunctive relational calculus formula which is evaluated over the extensions of the FAF.
Then, this framework is further expanded into the so-called Extended FAF (EFAF), where a first-order logic formula (FOL) is used for reasoning over `feasible’ subframeworks that satisfy the FOL formula and minimally differ from the original framework. We investigate the computational complexity of verification and acceptance problems under several semantics and show that incomplete AF (iAF) frameworks, including correlated iAF and constrained iAF, are special cases of EFAF.
7066: Efficient and Rigorous Model-Agnostic Explanations
Authors: Joao Marques-Silva, Jairo A. Lefebre-Lobaina, Maria Vanina Martinez
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Constraint Satisfaction and Optimization (2/3)
Show Abstract
Explainable artificial intelligence (XAI) is at the core of trustworthy AI. The best-known methods of XAI are sub-symbolic. Unfortunately, these methods do not give guarantees of rigor. Logic-based XAI addresses the lack of rigor of sub-symbolic methods, but in turn it exhibits some drawbacks. These include scalability, explanation size, but also the need to access the details of the machine learning model. Furthermore, access to the details of an ML model may reveal sensitive information. This
paper builds on recent work on symbolic model-agnostic XAI, which is based on explaining samples of behavior of a blackbox ML model, and proposes efficient algorithms for the computation of explanations. The experiments confirm the scalability of the novel algorithms.
7070: Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It
Authors: Denis Antipov, Benjamin Doerr
Location: Montreal | Day: August 19th | Time: 11:30 | Session: S: Evolutionary computation (1/2)
Show Abstract
Randomized search heuristics (RSHs) are known to have a certain robustness to noise. Mathematical analyses trying to quantify rigorously how robust RSHs are to a noisy access to the objective function typically assume that each solution is re-evaluated whenever it is compared to others. This aims at preventing that a single noisy evaluation has a lasting negative effect, but is computationally expensive and requires the user to foresee that noise is present (as in a noise-free setting, one would never re-evaluate solutions).
In this work, we conduct the first mathematical runtime analysis of an evolutionary algorithm solving a single-objective noisy problem without re-evaluations. We prove that the (1+1) evolutionary algorithm without re-evaluations can optimize the classic LeadingOnes benchmark with up to constant noise rates, in sharp contrast to the version with re-evaluations, where only noise with rates O(n⁻²log n) can be tolerated.
This result suggests that re-evaluations are much less needed than what was previously thought, and that they actually can be highly detrimental. The insights from our mathematical proofs indicate that this similar results are plausible for other classic benchmarks.
7122: Rewarding Explainability in Drug Repurposing with Knowledge Graphs
Authors: Susana Nunes, Samy Badreddine, Catia Pesquita
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Humans and AI: Interpretable Models
Show Abstract
Knowledge graphs (KGs) are powerful tools for modelling complex, multi-relational data and supporting hypothesis generation, particularly in applications like drug repurposing. However, for predictive methods to gain acceptance as credible scientific tools, they must ensure not only accuracy but also the capacity to offer meaningful scientific explanations.

This paper presents a novel approach REx, for generating scientific explanations based in link prediction in knowledge graphs. It employs reward and policy mechanisms that consider desirable properties of scientific explanation to guide a reinforcement learning agent in the identification of explanatory paths within a KG. The approach further enriches explanatory paths with domain-specific ontologies, ensuring that the explanations are both insightful and grounded in established biomedical knowledge.

We evaluate our approach in drug repurposing using three popular knowledge graph benchmarks. The results clearly demonstrate its ability to generate explanations that validate predictive insights against biomedical knowledge and that outperform the state-of-the-art approaches in predictive performance, establishing REx as a relevant contribution to advance AI-driven scientific discovery.
7124: A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update
Authors: Andre Opris
Location: Montreal | Day: August 19th | Time: 11:30 | Session: S: Evolutionary computation (1/2)
Show Abstract
The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III of when and why it performs well are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(n^(k+d/2)+ N n ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size N is in 2^(O(n)) and at least (2n/d+1)^(d/2). Notably, NSGA-III is faster than NSGA-II by a factor of N/n^(d/2) for N=omega(n^(d/2)) . We also show that a stochastic population update provably guarantees a speedup of order (k/b)^(k-1) in the runtime where b>0 is a constant. Besides a paper of Wietheger and Doerr (PPSN 2024), this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved.
7142: Continuous-Time Reward Machines
Authors: Amin Falah, Shibashis Guha, Ashutosh Trivedi
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Reinforcement Learning (2/2)
Show Abstract
Reinforcement Learning (RL) is a sampling-based method for sequential decision-making, in which a learning agent iteratively converges toward an optimal policy by leveraging feedback from the environment in the form of scalar reward signals.
While timing information is often abstracted in discrete-time domains, time-critical learning applications—such as queuing systems, population processes, and manufacturing systems—are naturally modeled as Continuous-Time Markov Decision Processes (CTMDPs).
Since the seminal work of Bradtke and Duff, model-free RL for CTMDPs has become well-understood. However, in many practical applications, practitioners possess high-quality information about system rates derived from traditional queuing theory, which learning agents could potentially exploit to accelerate convergence. Despite this, classical RL algorithms for CTMDPs typically re-learn these parameters through sampling.
In this work, we propose continuous-time reward machines (CTRMs), a novel framework that embeds reward functions and real-time state-action dynamics into a unified structure.
CTRMs enable RL agents to effectively navigate dense-time environments while leveraging reward shaping and counterfactual experiences for accelerated learning.
Our empirical results demonstrate CTRMs’ ability to improve learning efficiency in time-critical environments.
7157: Finding Possible Winners in Spatial Voting with Incomplete Information
Authors: Hadas Shachnai, Rotem Shavitt, Andreas Wiese
Location: Montreal | Day: August 19th | Time: 11:30 | Session: GTEP: Computational social choice (1/2)
Show Abstract
We consider a spatial voting model where both candidates and voters are positioned in the d-dimensional Euclidean space, and each voter ranks candidates based on their proximity to the voter’s ideal point. We focus on the scenario where the given information about the locations of the voters’ ideal points is incomplete; for each dimension, only an interval of possible values is known. In this context, we investigate the computational complexity of determining the possible winners under positional scoring rules. Our results show that the possible winner problem in one dimension is solvable in polynomial time for all k-truncated voting rules with constant k. Moreover, for some scoring rules for which the possible winner problem is NP-complete, such as approval voting for any dimension or k-approval for two or more dimensions, we give an FPT algorithm parameterized by the number of candidates. Finally, we classify tractable and intractable settings of the em weighted possible winner problem in one dimension, and resolve the computational complexity of the weighted case for all two-valued positional scoring rules when d=1.
7161: Implicitly Aligning Humans and Autonomous Agents through Shared Task Abstractions
Authors: Stéphane Aroca-Ouellette, Miguel Aroca-Ouellette, Katharina von der Wense, Alessandro Roncone
Location: Montreal | Day: August 21st | Time: 10:00 | Session: Humans and AI
Show Abstract
In collaborative tasks, autonomous agents fall short of humans in their capability to quickly adapt to new and unfamiliar teammates. We posit that a limiting factor for zero-shot coordination is the lack of shared task abstractions, a mechanism humans rely on to implicitly align with teammates. To address this gap, we introduce HA^2: Hierarchical Ad Hoc Agents, a framework leveraging hierarchical reinforcement learning to mimic the structured approach humans use in collaboration. We evaluate HA^2 in the Overcooked environment, demonstrating statistically significant improvement over existing baselines when paired with both unseen agents and humans, providing better resilience to environmental shifts, and outperforming all state-of-the-art methods.
7190: Decomposing Inconsistencies: Marginal Contributions and Pooling Techniques
Authors: Christian Straßer, Badran Raddaoui, Said Jabbour
Location: Montreal | Day: August 19th | Time: 11:30 | Session: Knowledge Representation and Reasoning (1/4)
Show Abstract
Inconsistency measures quantify the degree of conflict within a set of propositions. They can be broadly categorized into global measures, which assess the overall inconsistency of a set, and local measures, which evaluate the contribution of single formulas to the overall inconsistency. This paper investigates the relationship between these two classes of measures through the lens of marginal contributions and pooling mechanisms. We propose a systematic framework for deriving local inconsistency measures from global ones by employing notions of marginal contributions inspired by cooperative game theory, including Shapley and Banzhaf values. Conversely, we explore methods for constructing global inconsistency measures by
aggregating local contributions using various pooling techniques. A key research question arises: which combinations of marginal contribution notions (maC) and pooling mechanisms (P) are compatible? Compatibility is defined such that, given a global measure I, applying (P) to the marginal contributions derived from I yields the same result as directly applying I, and vice versa. We analyze this compatibility condition and identify specific pairs of methods, (maC) and (P), that satisfy it across various inconsistency frameworks. Our findings provide a deeper understanding of the interplay between global and local inconsistency measures, providing a foundation for designing principled and interpretable inconsistency evaluation methods in logic-based systems.
7201: Efficient Counterexample-Guided Fairness Verification and Repair of Neural Networks Using Satisfiability Modulo Convex Programming
Authors: Arya Fayyazi, Yifeng Xiao, Pierluigi Nuzzo, Massoud Pedram
Location: Montreal | Day: August 21st | Time: 11:30 | Session: ETF: Fairness and diversity
Show Abstract
Ensuring fairness is essential for ethical decision-making in various domains. Informally, a neural network is considered fair if and only if it treats similar individuals similarly in a given task.
We introduce FaVeR (Fairness Verification and Repair), a framework for efficiently verifying and repairing pre-trained neural networks with respect to individual fairness properties.
FaVeR ensures fairness via iterative search of high-sensitivity neurons and backward adjustment of their weights, guided by counterexamples generated from fairness verification using satisfiability modulo convex programming. By addressing fairness at the neuron level, FaVeR minimizes the impact of neural network repair on the overall performance. Experimental evaluations on common fairness datasets show that FaVeR achieves a 100% fairness repair rate across all models, with accuracy reduction of less than 2.27%. Moreover, its significantly lower average runtime makes it suitable for practical applications.
7224: Coalition Obstruction Temporal Logic: A New Obstruction Logic to Reason About Demon Coalitions
Authors: Davide Catta, Jean Leneutre, Vadim Malvone, James Ortiz
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MAS: Formal verification, validation and synthesis
Show Abstract
In multi-agent systems, especially in cybersecurity, the dynamic interplay between attackers and defenders is crucial to the security and resilience of the system. Traditional methods often assume static game models and fail to account for the strategic adaptation of the environment to the actions of the players. This paper presents Coalition Obstruction Temporal Logic (COTL), a formal framework for analyzing defender coalitions in dynamic game scenarios. Within this framework, defenders, conceptualized as demons, can actively obstruct attackers by selectively disabling certain actions in response to perceived threats. We establish the formal semantics of COTL and propose a model checking algorithm to verify complex security properties in systems with evolving adversarial dynamics. The utility of the framework is demonstrated through its application to a coalition of defenders that collaboratively defend a system against coordinated attacks.
7230: Sample-Efficient Behavior Cloning Using General Domain Knowledge
Authors: Feiyu Zhu, Jean Oh, Reid Simmons
Location: Montreal | Day: August 20th | Time: 14:00 | Session: Machine Learning (3/4)
Show Abstract
Behavior cloning has shown success in many sequential decision-making tasks by learning from expert demonstrations, yet they can be very sample inefficient and fail to generalize to unseen scenarios. One approach to these problems is to introduce general domain knowledge, such that the policy can focus on the essential features and may generalize to unseen states by applying that knowledge. Although this knowledge is easy to acquire from the experts, it is hard to be combined with learning from individual examples due to the lack of semantic structure in neural networks and the time-consuming nature of feature engineering. To enable learning from both general knowledge and specific demonstration trajectories, we use a large language model’s coding capability to instantiate a policy structure based on expert domain knowledge expressed in natural language and tune the parameters in the policy with demonstrations. We name this approach the Knowledge Informed Model (KIM) as the structure reflects the semantics of expert knowledge. In our experiments with lunar lander and car racing tasks, our approach learns to solve the tasks with as few as 5 demonstrations and is robust to action noise, outperforming the baseline model without domain knowledge. This indicates that with the help of large language models, we can incorporate domain knowledge into the structure of the policy, increasing sample efficiency for behavior cloning.
7248: RetroMoE: A Mixture-of-Experts Latent Translation Framework for Single-step Retrosynthesis
Authors: Xinjie Li, Abhinav Verma
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Multidisciplinary Topics and Applications (1/2)
Show Abstract
Single-step retrosynthesis is a crucial task in organic synthesis, where the objective is to identify the reactants needed to produce a given product. In recent years, a variety of machine learning methods have been developed to tackle retrosynthesis prediction. In our study, we introduce RetroMoE, a novel generative model designed for the single-step retrosynthesis task. We start with a non-symmetric variational autoencoder (VAE) that incorporates a graph encoder to map molecular graphs into a latent space, followed by a transformer decoder for precise prediction of molecular SMILES strings. Additionally, we implement a simple yet effective mixture-of-experts (MoE) network to translate the product latent embedding into the reactant latent embedding. To our knowledge, this is the first approach that frames single-step retrosynthesis as a latent translation problem. Extensive experiments on the USPTO-50K and USPTO-MIT datasets demonstrate the superiority of our method, which not only surpasses most semi-template-based and template-free methods but also delivers competitive results against template-based methods. Notably, under the class-known setting on the USPTO-50K, our method achieves top-1 exact match accuracy comparable to the state-of-the-art template method, RetroKNN.
7257: A Logic-Based Approach to Causal Discovery: Signal Temporal Logic Perspective
Authors: Nasim Baharisangari, Yucheng Ruan, Chengcheng Zhao, Zhe Xu
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: time series, sequences and signals
Show Abstract
Causal discovery in time-series datasets is critical for understanding complex systems, especially when the \textit{effectiveness} of causal relationships depends on both the \textit{duration} and \textit{magnitude} of the cause. We introduce a novel framework for causal discovery based on \textbf{Signal Temporal Logic (STL)}, enabling the extraction of interpretable causal diagrams (STL-CD) that explicitly capture these temporal dynamics. Our method first identifies statistically meaningful time intervals, then infers STL formulas that classify system behaviors, and finally employs transfer entropy to determine direct causal relationships among the formulas. This approach not only uncovers causal structure but also identifies the temporal persistence required for causal influence—an insight missed by existing methods. Experimental results on synthetic and real-world datasets demonstrate that our method achieves superior structural accuracy over state-of-the-art baselines, providing more informative and temporally precise causal models.
7268: Partially Observable Reference Policy Programming
Authors: Edward Kim, Hanna Kurniawati
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Planning and Scheduling (5/5)
Show Abstract
This paper proposes Partially Observable Reference Policy Programming, a novel anytime online approximate POMDP solver which samples meaningful future histories very deeply while simultaneously forcing a gradual policy update. We provide theoretical guarantees for the algorithm’s underlying scheme which say that the performance loss is bounded by the average of the sampling approximation errors rather than the usual maximum; a crucial requirement given the sampling sparsity of online planning. Empirical evaluations on two large-scale problems with dynamically evolving environments—including a helicopter emergency scenario in the Corsica region requiring approximately 150 planning steps—corroborate the theoretical results and indicate that our solver considerably outperforms current online benchmarks.
7307: FairSMOE: Mitigating Multi-Attribute Fairness Problem with Sparse Mixture-of-Experts
Authors: Changdi Yang, Zheng Zhan, Ci Zhang, Yifan Gong, Yize Li, Zichong Meng, Jun Liu, Xuan Shen, Hao Tang, Geng Yuan, Pu Zhao, Xue Lin, Yanzhi Wang
Location: Montreal | Day: August 20th | Time: 10:00 | Session: AI Ethics, Trust, Fairness (1/3)
Show Abstract
Real‐world datasets usually contain multiple attributes, making it essential to ensure fairness across all of them simultaneously. However, different attributes may vary in difficulty, and no existing approaches have effectively addressed this issue. Consequently, an attribute‐adaptive strategy is needed to achieve fairness for all attributes.
Multi‐task Learning (MTL) leverages shared information to optimize multiple tasks concurrently, while Sparsely‐Gated Mixture‐of‐Experts (SMoE) can dynamically allocate computational resources to the most needed tasks. In this work, we formulate multi‐attribute fairness issue as an MTL problem and employ SMoE to achieve desirable performance across all attributes simultaneously.

We first analyze the feasibility and find the potentiality by formalizing multi-attribute fairness problem into a MTL problem and mitigating it by using SMoE. However, vanilla SMoE could lead to over-utilization problem which causes sub-optimal performance. We then proposed an innovative SMoE framework for multi-attribute fair image classification, which further improves multi-attribute fairness by redesigning the MoE layer and routing policy with fairness consideration. Extensive experiments demonstrated the effectiveness. Taking a DeiT-Small as the backbone, we achieve 77.25% and 86.01% accuracy on the ISIC2019 and CelebA dataset respectively with Multi-attribute Predictive Quality Disparity (PQD) score of 0.801 and 0.787, beating current state-of-the-art methods Muffin, InfoFair and MultiFair.
7317: Learning Optimal Oblique Decision Trees with (Max)SAT
Authors: Florent Avellaneda
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Constraint Satisfaction and Optimization (3/3)
Show Abstract
Decision trees are widely used in machine learning for their interpretability and effectiveness in classification tasks. Traditional axis-parallel decision trees partition data using single-feature thresholds at each node, but they often struggle to represent complex, non-axis-aligned decision boundaries efficiently. This limitation can result in unnecessarily large and less interpretable trees. Oblique decision trees address this limitation by using linear combinations of features at each node, allowing a more natural representation of complex decision boundaries while maintaining interpretability through sparse linear combinations. However, learning optimal oblique decision trees poses a significant computational challenge, as existing methods predominantly rely on suboptimal greedy heuristics. In this paper, we propose a novel approach to learning globally optimal oblique decision trees by reformulating the problem as a (Max)SAT instance. By leveraging state-of-the-art (Max)SAT solvers, our method efficiently explores the solution space to identify optimal trees. Experiments on benchmark datasets demonstrate that our approach generates optimal oblique decision trees within reasonable computational time for small to medium-sized datasets.
7432: RepObE: Representation Learning-Enhanced Obfuscation Encryption Modular Semantic Task Framework
Authors: Limei Lin, Jinpeng Xu, Xiaoding Wang, Liang Chen, Sun-Yuan Hsieh, Jie Wu
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Machine Learning (1/4)
Show Abstract
Model inversion and adversarial attacks in semantic communication pose risks, such as content leaks, alterations, and prediction inaccuracies, which threaten security and reliability. This paper introduces, from an attacker’s viewpoint, a novel framework called RepObE (Representation Learning-Enhanced Obfuscation Encryption Modular Semantic Task Framework) to secure semantic communication. This framework employs dynamic encryption during semantic extraction and feature transmission to hinder attackers from reconstructing data through eavesdropping, thus strengthening system privacy. To combat image communication task challenges, we propose a prototype adversarial collaborative alignment training approach enhanced by representation learning. This method extracts and encodes semantic features while using dynamic perturbation and robust optimization to improve system resilience against adversarial threats. The approach ensures reliable semantic communication in complex environments, maintaining performance while countering attacks using feature obfuscation, adversarial training, and representation learning. Experimental results demonstrate that our method surpasses existing techniques by more than 2% in resisting model inversion attacks on classification tasks. Visually, our method excels with minimal decipherable images for attackers. It also shows a 3% to 5% improvement in countering adversarial attacks on classification tasks.
7495: Fine-Grained and Efficient Self-Unlearning with Layered Iteration
Authors: Hongyi Lyu, Xuyun Zhang, Hongsheng Hu, Shuo Wang, Chaoxiang He, Lianyong Qi
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MTA: Security and privacy
Show Abstract
As machine learning models become widely deployed in data-driven applications, ensuring compliance with the ‘right to be forgotten’ as required by many privacy regulations is vital for safeguarding user privacy. To forget the given data, existing re-labeling based unlearning methods employ a single-step adjustment scheme that revises the decision boundaries in one re-labeling phase. However, such single-step approaches lead to coarse-grained changes in decision boundaries among the remaining classes and impose adverse effects on the model utility. To address these limitations, we propose ‘Self-Unlearning with Layered Iteration (SULI),’ a novel unlearning approach that introduces a layered iteration strategy to re-label the forgetting data iteratively and refine the decision boundaries progressively. We further develop a ‘Selective Probability Adjustment (SPA)’ technique, which uses a soft-label mechanism to promote smoother decision-boundary transitions. Comprehensive experiments on three benchmark datasets demonstrate that SULI achieves superior performance in effectiveness, efficiency, and privacy compared to the state-of-the-art baselines in both class-wise and instance-wise unlearning scenarios. The source code is released at https://github.com/Hongyi-Lyu-MQ/SULI.
7503: Run Like a Neural Network, Explain Like k-Nearest Neighbor
Authors: Xiaomeng Ye, David Leake, Yu Wang, David Crandall
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Machine Learning (1/4)
Show Abstract
Deep neural networks have achieved remarkable performance across a variety of applications. However, their decision-making processes are opaque. In contrast, k-nearest neighbor (k-NN) provides interpretable predictions by relying on similar cases, but it lacks important capabilities of neural networks.
The neural network k-nearest neighbor (NN-kNN) model is designed to bridge this gap, combining the benefits of neural networks with the instance-based interpretability of k-NN. However, the initial formulation of NN-kNN had limitations including scalability issues, reliance on surface-level features, and an excessive number of parameters. This paper improves NN-kNN by enhancing its scalability, parameter efficiency, ease of integration with feature extractors, and training simplicity.
An evaluation of the revised architecture for image and language classification tasks illustrates its promise as a flexible and interpretable method.
7513: M^2LLM: Multi-view Molecular Representation Learning with Large Language Models
Authors: Jiaxin Ju, Yizhen Zheng, Huan Yee Koh, Can Wang, Shirui Pan
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: LLM applications
Show Abstract
Accurate molecular property prediction is a critical challenge with wide-ranging applications in chemistry, materials science, and drug discovery. Molecular representation methods, including fingerprints and graph neural networks (GNNs), achieve state-of-the-art results by effectively deriving features from molecular structures. However, these methods often overlook decades of accumulated semantic and contextual knowledge. Recent advancements in large language models (LLMs) demonstrate remarkable reasoning abilities and prior knowledge across scientific domains, leading us to hypothesize that LLMs can generate rich molecular representations when guided to reason in multiple perspectives. To address these gaps, we propose M^2LLM, a multi-view framework that integrates three perspectives: the molecular structure view, the molecular task view, and the molecular rules view. These views are fused dynamically to adapt to task requirements, and experiments demonstrate that M^2LLM achieves state-of-the-art performance on multiple benchmarks across classification and regression tasks. Moreover, we demonstrate that representation derived from LLM achieves exceptional performance by leveraging two core functionalities: the generation of molecular embeddings through their encoding capabilities and the curation of molecular features through advanced reasoning processes.
7517: Category-aware EEG Image Generation Based on Wavelet Transform and Contrast Semantic Loss
Authors: Enshang Zhang, Zhicheng Zhang, Takashi Hanakawa
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Multidisciplinary Topics and Applications (2/2)
Show Abstract
Reconstructing visual stimuli from EEG signals is a crucial step in realizing brain-computer interfaces. In this paper, we propose a transformer-based EEG signal encoder integrating the Discrete Wavelet Transform (DWT) and the gating mechanism. Guided by the feature alignment and category-aware fusion losses, this encoder is used to extract features related to visual stimuli from EEG signals. Subsequently, with the aid of a pre-trained diffusion model, these features are reconstructed into visual stimuli. To verify the effectiveness of the model, we conducted EEG-to-image generation and classification tasks using the THINGS-EEG dataset. To address the limitations of quantitative analysis at the semantic level, we combined WordNet-based classification and semantic similarity metrics to propose a novel semantic-based score, emphasizing the ability of our model to transfer neural activities into visual representations. Experimental results show that our model significantly improves semantic alignment and classification accuracy, which achieves a maximum single-subject accuracy of 43%, outperforming other state-of-the-art methods. The source code is available at https://github.com/zes0v0inn/DWT_EEG_Reconstruction/.
7518: Escaping Saddle Point Efficiently in Minimax and Bilevel Optimizations
Authors: Wenhan Xian, Feihu Huang, Heng Huang
Location: Montreal | Day: August 20th | Time: 14:00 | Session: ML: Machine Learning 6/8
Show Abstract
Hierarchical optimization is attracting significant attentions as it can be applied to a broad range of machine learning tasks. Recently, many algorithms are proposed to improve the theoretical results of minimax and bilevel optimizations. Among these works, a core issue that has not been well studies is to escape saddle point and find local minimum. In this paper, thus, we investigate the methods to achieve second-order optimality for nonconvex minimax and bilevel optimization. Specifically, we propose a new algorithm named PRGDA without the computation of second order derivative of the primal function. In nonconvex-strongly-concave minimax optimization, we prove that our algorithm can find a second-order stationary point with the gradient complexity that matches state-of-the-art result to find first-order stationary point. To our best knowledge, PRGDA is the first stochastic algorithm that is guaranteed to obtain the second-order stationary point for nonconvex minimax problems. In nonconvex-strongly-convex bilevel optimization, our method also achieves better gradient complexity to find local minimum. Finally, we conduct two numerical experiments to validate the performance of our new method.
7585: Attractor-based Closed List Search: Sparsifying the Closed List for Efficient Memory-Constrained Planning
Authors: Alvin Zou, Muhammad Suhail Saleem, Maxim Likhachev
Location: Montreal | Day: August 22nd | Time: 11:30 | Session: Search
Show 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.
7601: Incentivizing Safer Actions in Policy Optimization for Constrained Reinforcement Learning
Authors: Somnath Hazra, Pallab Dasgupta, Soumyajit Dey
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Reinforcement Learning (2/2)
Show Abstract
Constrained Reinforcement Learning (RL) aims to maximize the return while adhering to predefined constraint limits, which represent domain-specific safety requirements. In continuous control settings, where learning agents govern system actions, balancing the trade-off between reward maximization and constraint satisfaction remains a significant challenge. Policy optimization methods often exhibit instability near constraint boundaries, resulting in suboptimal training performance. To address this issue, we introduce a novel approach that integrates an adaptive incentive mechanism in addition to the reward structure to stay within the constraint bound before approaching the constraint boundary. Building on this insight, we propose Incrementally Penalized Proximal Policy Optimization (IP3O), a practical algorithm that enforces a progressively increasing penalty to stabilize training dynamics. Through empirical evaluation on benchmark environments, we demonstrate the efficacy of IP3O compared to the performance of state-of-the-art Safe RL algorithms. Furthermore, we provide theoretical guarantees by deriving a bound on the worst-case error of the optimality achieved by our algorithm.
7706: Contamination Budget: Trade-offs Between Breadth, Depth and Difficulty
Authors: Behzad Mehrbakhsh, Fernando Martínez-Plumed, José Hernández-Orallo
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: Natural Language Processing (1/2)
Show Abstract
Contamination in large language models (LLMs), and machine learning more broadly, refers to the inclusion of equal –or very similar– examples in both training and test sets. This phenomenon usually translates into better test performance. Here we explore when this contamination is performed intentionally, for purposes that can be malicious (e.g., get better scores in evaluations) or benevolent (e.g., fix some mistakes). These interventions, usually in the form of fine-tuning memorisations, come with a budget in the size of the fine-tuning dataset. Several trade-offs appear between the breadth of the intervention (how many examples to be memorised), its depth (how many repetitions of each example) and the difficulty of the examples. By studying several LLMs and datasets, we observe some monotonic behaviour (more difficult items require more depth to be `fixed’) but also some non-monotonic phenomena (very high depth levels have negative effects on non-contaminated examples). This suggests that trade-offs should be found not only in terms of the budget but also according to model specifics, the task and the item difficulty at hand.
7733: Robult: Leveraging Redundancy and Modality-Specific Features for Robust Multimodal Learning
Authors: Duy A. Nguyen, Abhi Kamboj, Minh N. Do
Location: Montreal | Day: August 20th | Time: 10:00 | Session: Multidisciplinary Topics and Applications (2/2)
Show Abstract
Addressing missing modalities and limited labeled data is crucial for advancing robust multimodal learning. We propose Robult, a scalable framework designed to mitigate these challenges by preserving modality-specific information and leveraging redundancy through a novel information-theoretic approach. Robult optimizes two core objectives: (1) a soft Positive-Unlabeled (PU) contrastive loss that maximizes task-relevant feature alignment while effectively utilizing limited labeled data in semi-supervised settings, and (2) a latent reconstruction loss that ensures unique modality-specific information is retained. These strategies, embedded within a modular design, enhance performance across various downstream tasks and ensure resilience to incomplete modalities during inference. Experimental results across diverse datasets validate that Robult achieves superior performance over existing approaches in both semi-supervised learning and missing modality contexts. Furthermore, its lightweight design promotes scalability and seamless integration with existing architectures, making it suitable for real-world multimodal applications.
7783: Adaptive Gradient Learning for Spiking Neural Networks by Exploiting Membrane Potential Dynamics
Authors: Jiaqiang Jiang, Lei Wang, Runhao Jiang, Jing Fan, Rui Yan
Location: Montreal | Day: August 20th | Time: 10:00 | Session: ML: Spiking Neural Networks
Show Abstract
Recent advancements have focused on directly training high-performance spiking neural networks (SNNs) by estimating the approximate gradients of spiking activity through a continuous function with constant sharpness, known as surrogate gradient (SG) learning. However, as spikes propagate within neurons and among layers, the distribution of membrane potential dynamics (MPD) will deviate from the gradient-available interval of fixed SG, hindering SNNs from searching the optimal solution space. To maintain the stability of gradient flows, SG needs to align with evolving MPD. Here, we propose a novel adaptive gradient learning for SNNs by exploiting MPD, namely MPD-AGL. It fully accounts for the underlying factors contributing to membrane potential shifts and establishes a dynamic association between SG and MPD at different timesteps to relax gradient estimation, which provides a new degree of freedom for SG learning. Experimental results demonstrate that our method achieves excellent performance at low latency. Moreover, it increases the proportion of neurons that fall into the gradient-available interval compared to fixed SG, effectively mitigating the gradient vanishing problem. Code is available at https://github.com/jqjiang1999/MPD-AGL.
7802: Variety-Seeking Jump Games on Graphs
Authors: Lata Narayanan, Jaroslav Opatrny, Shanmukha Tummala, Alexandros A. Voudouris
Location: Montreal | Day: August 21st | Time: 10:00 | Session: GTEP: Noncooperative games
Show Abstract
We consider a class of jump games in which agents of different types occupy the nodes of a graph aiming to maximize the variety of types in their neighborhood. In particular, each agent derives a utility equal to the number of types different from its own in its neighborhood. We show that the jump game induced by the strategic behavior of the agents (who aim to maximize their utility) may in general have improving response cycles, but is a potential game under any of the following four conditions: there are only two types of agents; or exactly one empty node; or the graph is of degree at most 2; or the graph is 3-regular and there are two empty nodes. Additionally, we show that on trees, cylinder graphs, and tori, there is always an equilibrium. Finally, we show tight bounds on the price of anarchy with respect to two different measures of diversity: the social welfare (the total utility of the agents) and the number of colorful edges (that connect agents of different types).
7822: NeSyA: Neurosymbolic Automata
Authors: Nikolaos Manginas, George Paliouras, Luc De Raedt
Location: Montreal | Day: August 21st | Time: 11:30 | Session: ML: Neurosymbolic AI
Show Abstract
Neurosymbolic (NeSy) AI has emerged as a promising direction to integrate
neural and symbolic reasoning. Unfortunately, little effort has been given
to developing NeSy systems tailored to sequential/temporal problems. We identify
symbolic automata (which combine the power of automata for temporal reasoning
with that of propositional logic for static reasoning) as a suitable formalism for
expressing knowledge in temporal domains. Focusing on the task of sequence classification
and tagging we show that symbolic automata can be integrated with neural-based
perception, under probabilistic semantics towards an end-to-end differentiable model.
Our proposed hybrid model, termed NeSyA (Neuro Symbolic
Automata) is shown to either scale or perform more accurately than previous
NeSy systems in a synthetic benchmark and to provide benefits in terms of generalization
compared to purely neural systems in a real-world event recognition task.
Code is available at: https://github.com/nmanginas/nesya
7835: Identifying Drivers of Predictive Aleatoric Uncertainty
Authors: Pascal Iversen, Simon Witzke, Katharina Baum, Bernhard Y. Renard
Location: Montreal | Day: August 21st | Time: 10:00 | Session: ML: Explainable/Interpretable machine learning
Show Abstract
Explainability and uncertainty quantification are key to trustable artificial intelligence. However, the reasoning behind uncertainty estimates is generally left unexplained. Identifying the drivers of uncertainty complements explanations of point predictions in recognizing model limitations and enhancing transparent decision-making. So far, explanations of uncertainties have been rarely studied. The few exceptions rely on Bayesian neural networks or technically intricate approaches, such as auxiliary generative models, thereby hindering their broad adoption. We propose a straightforward approach to explain predictive aleatoric uncertainties. We estimate uncertainty in regression as predictive variance by adapting a neural network with a Gaussian output distribution. Subsequently, we apply out-of-the-box explainers to the model’s variance output. This approach can explain uncertainty influences more reliably than complex published approaches, which we demonstrate in a synthetic setting with a known data-generating process. We substantiate our findings with a nuanced, quantitative benchmark including synthetic and real, tabular and image datasets. For this, we adapt metrics from conventional XAI research to uncertainty explanations. Overall, the proposed method explains uncertainty estimates with little modifications to the model architecture and outperforms more intricate methods in most settings.
7847: Maximum Entropy Softmax Policy Gradient via Entropy Advantage Estimation
Authors: Jean Seong Bjorn Choe, Jong-kook Kim
Location: Montreal | Day: August 21st | Time: 15:00 | Session: ML: Reinforcement Learning (2/2)
Show Abstract
Entropy Regularisation is a widely adopted technique that enhances policy optimisation performance and stability. Maximum entropy reinforcement learning (MaxEnt RL) regularises policy evaluation by augmenting the objective with an entropy term, showing theoretical benefits in policy optimisation. However, its practical application in straightforward direct policy gradient settings remains surprisingly underexplored. We hypothesise that this is due to the difficulty of managing the entropy reward in practice. This paper proposes Entropy Advantage Policy Optimisation (EAPO), a simple method that facilitates MaxEnt RL implementation by separately estimating task and entropy objectives. Our empirical evaluations demonstrate that extending Proximal Policy Optimisation (PPO) and Trust Region Policy Optimisation (TRPO) within the MaxEnt framework improves optimisation performance, generalisation, and exploration in various environments. Moreover, our method provides a stable and performant MaxEnt RL algorithm for discrete action spaces.
7888: Approximate Verification of Strategic Abilities under Imperfect Information Using Local Models
Authors: Damian Kurpiewski, Wojciech Jamroga, Yan Kim
Location: Montreal | Day: August 21st | Time: 10:00 | Session: MAS: Formal verification, validation and synthesis
Show Abstract
Verification of strategic ability under imperfect information is challenging, with complexity ranging from NP-complete to undecidable. This is partly because traditional fixpoint equivalences fail in this setting. Some years ago, an interesting idea of fixpoint approximation was proposed for model checking of ATL_ir, i.e., the logic of strategic ability for agents with imperfect information and imperfect recall.
In this paper, we propose a new variant of the approximation, that uses the agent’s local model rather than the global model of the system. We prove correctness of the construction, and demonstrate its effectiveness through experimental results on scalable models of voting.
7895: Abstraction Heuristics for Classical Planning Tasks with Conditional Effects
Authors: Martín Pozo, Jendrik Seipp
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Planning and Scheduling (2/5)
Show Abstract
In planning tasks, conditional effects model action outcomes that depend on the current state of the world. Conditional effects are a crucial modeling feature since compiling them away can cause an exponential growth in task size. However, only a few admissible heuristics support them. To add abstraction heuristics to this set, we show how to compute projections, Cartesian abstractions and merge-and-shrink abstractions for tasks with conditional effects. Our experiments show that these heuristics are competitive with, and often surpass, the state-of-the-art for conditional-effect tasks.
7934: Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions
Authors: Ángel Aso-Mollar, Diego Aineto, Enrico Scala, Eva Onaindia
Location: Montreal | Day: August 19th | Time: 15:00 | Session: Planning and Scheduling (2/5)
Show Abstract
In automated planning, control parameters extend standard action representations through the introduction of continuous numeric decision variables. Existing state-of-the-art approaches have primarily handled control parameters as embedded constraints alongside other temporal and numeric restrictions, and thus have implicitly treated them as additional constraints rather than as decision points in the search space. In this paper, we propose an efficient alternative that explicitly handles control parameters as true decision points within a systematic search scheme. We develop a best-first, heuristic search algorithm that operates over infinite decision spaces defined by control parameters and prove a notion of completeness in the limit under certain conditions. Our algorithm leverages the concept of delayed partial expansion, where a state is not fully expanded but instead incrementally expands a subset of its successors. Our results demonstrate that this novel search algorithm is a competitive alternative to existing approaches for solving planning problems involving control parameters.
8016: A Datalog Rewriting Algorithm for Warded Ontologies
Authors: Davide Benedetto, Marco Calautti, Hebatalla Hammad, Emanuel Sallinger, Adriano Vlad-Starrabba
Location: Montreal | Day: August 22nd | Time: 10:00 | Session: KR: ontologies
Show Abstract
Existential rules, a.k.a. tuple-generating dependencies (TGDs), form a well-established formalism for specifying ontologies. In particular, the warded language is a well-behaved fragment of TGD-based ontologies, striking a good balance between expressive power and computational complexity of answering Ontology-Mediated Queries (OMQs). The theoretical foundations of answering OMQs over warded ontologies are by now well-understood, but to the best of our knowledge, very few efforts exist that exploit such a rich theory for building practical query answering algorithms. Our goal is to fill the above gap by designing a novel Datalog rewriting algorithm for OMQs over warded ontologies which is amenable to practical implementations, as well as providing an implementation and an experimental evaluation, with the aim of understanding how key input parameters affect the performance of this approach, and what are its limits when combined with off-the-shelf Datalog-based engines.
8023: Towards Safer Pretraining: Analyzing and Filtering Harmful Content in Webscale Datasets for Responsible LLMs
Authors: Sai Krishna Mendu, Harish Yenala, Aditi Gulati, Shanu Kumar, Parag Agrawal
Location: Montreal | Day: August 20th | Time: 10:00 | Session: AI Ethics, Trust, Fairness (1/3)
Show Abstract
Large language models (LLMs) have become integral to various real-world applications, leveraging massive, web-sourced datasets like Common Crawl, C4, and FineWeb for pretraining. While these datasets provide linguistic data essential for high-quality natural language generation, they often contain harmful content, such as hate speech, misinformation, and biased narratives. Training LLMs on such unfiltered data risks perpetuating toxic behaviors, spreading misinformation, and amplifying societal biases which can undermine trust in LLM-driven applications and raise ethical concerns about their use. This paper presents a large-scale analysis of inappropriate content across these datasets, offering a comprehensive taxonomy that categorizes harmful webpages into Topical and Toxic based on their intent. We also introduce a prompt evaluation dataset, a high-accuracy Topical and Toxic Prompt (TTP), and a transformer-based model (HarmFormer) for harmful content filtering. Additionally, we create a new multi-harm open-ended toxicity benchmark (HAVOC) and provide crucial insights into how models respond to adversarial toxic inputs. Our work offers insights into ensuring safer LLM pretraining and serves as a resource for Responsible AI (RAI) compliance.
Disclaimer: This paper includes potentially offensive content due to the nature of the research.
8064: DGExplainer: Explaining Dynamic Graph Neural Networks via Relevance Back-propagation
Authors: Yezi Liu, Jiaxuan Xie, Yanning Shen
Location: Montreal | Day: August 21st | Time: 15:00 | Session: DM: Graph Data Mining
Show Abstract
Dynamic graph neural networks (dynamic GNNs) have demonstrated remarkable effectiveness in analyzing time-varying graph-structured data. However, their black-box nature often hinders users from understanding their predictions, which can limit their applications. In recent years, there has been a surge in research aimed at explaining GNNs, but most studies have focused on static graphs, leaving the explanation of dynamic GNNs relatively unexplored. Explaining dynamic GNNs presents a unique challenge due to their complex spatial and temporal structures. As a result, existing approaches designed for explaining static graphs are not directly applicable to dynamic graphs because they ignore temporal dependencies among graph snapshots. To address this issue, we propose DGExplainer, which offers a reliable explanation of dynamic GNN predictions. DGExplainer utilizes the relevance back-propagation technique both time-wise and layer-wise. Specifically, it incorporates temporal information by computing the relevance of node representations along the inverse of the time evolution. Additionally, for each time step, it calculates layer-wise relevance from a graph-based module by redistributing the relevance of node representations along the back-propagation path. Quantitative and qualitative experimental results on six real-world datasets demonstrate the effectiveness of DGExplainer in identifying important nodes for link prediction and node regression in dynamic GNNs.
8068: What Makes You Special? Contrastive Heuristics Based on Qualified Dominance
Authors: Rasmus G. Tollund, Kim G. Larsen, Alvaro Torralba
Location: Montreal | Day: August 21st | Time: 11:30 | Session: Planning and Scheduling (4/5)
Show Abstract
In cost-optimal planning, dominance pruning methods discard states during the search that are dominated by others. However, the binary nature of pruning fails to exploit information when we cannot prove that a state is fully dominated. To this end, we introduce qualified dominance, an automatic method that given a pair of states s,t synthetizes a finite state automaton that represents a language of plans from s that are dominated by t. This not only explains why s cannot be pruned, but also can be used to improve the heuristic function to guide the search. This results in a new type of heuristic, which we call contrastive heuristics, that are dependent on the search performed so far. We provide the theoretical foundation for showing that contrastive heuristics can be used to find optimal plans even when their more informative estimates are not admissible.
8088: Maximin Share Guarantees for Few Agents with Subadditive Valuations
Authors: George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, Alkmini Sgouritsa
Location: Montreal | Day: August 21st | Time: 11:30 | Session: GTEP: Fair division
Show Abstract
We study the problem of fairly allocating a set of indivisible items among a set of agents. We consider the notion of (approximate) maximin share (MMS) and we provide an improved lower bound of 1/2 (which is tight) for the case of subadditive valuations when the number of agents is at most four. We also provide a tight lower bound for the case of multiple agents, when they are equipped with one of two possible types of valuations. Moreover, we propose a new model that extends previously studied models in the area of fair division, which will hopefully give rise to further research. We demonstrate the usefulness of this model by employing it as a technical tool to derive our main result, and we provide a thorough analysis for this model for the case of three agents. Finally, we provide an improved impossibility result for the case of three submodular agents.
8227: Evolvable Conditional Diffusion
Authors: Zhao Wei, Chin Chun Ooi, Abhishek Gupta, Jian Cheng Wong, Pao-Hsiung Chiu, Sheares Xue Wen Toh, Yew-Soon Ong
Location: Montreal | Day: August 19th | Time: 11:30 | Session: ML: Difussion Models
Show Abstract
This paper presents an evolvable conditional diffusion method such that black-box, non-differentiable multi-physics models, as are common in domains like computational fluid dynamics and electromagnetics, can be effectively used for guiding the generative process to facilitate autonomous scientific discovery. We formulate the guidance as an optimization problem where one optimizes for a desired fitness function through updates to the descriptive statistic for the denoising distribution, and derive an evolution-guided approach from first principles through the lens of probabilistic evolution. Interestingly, the final derived update algorithm is analogous to the update as per common gradient-based guided diffusion models, but without ever having to compute any derivatives. We validate our proposed evolvable diffusion algorithm in two AI for Science scenarios: the automated design of fluidic topology and meta-surface. Results demonstrate that this method effectively generates designs that better satisfy specific optimization objectives without reliance on differentiable proxies, providing an effective means of guidance-based diffusion that can capitalize on the wealth of black-box, non-differentiable multi-physics numerical models common across Science.