Accepted Papers

In many real-world scenarios, interactions happen in a group-wise manner with multiple entities, and therefore, hypergraphs are a suitable tool to accurately represent such interactions. Various generative models have been proposed to explore fundamental mechanisms underlying hyperedge formation. However, most existing models do not account for node attributes, which can play a significant role in hyperedge formation. As a result, they fail to capture the interactions between structure and node attributes. To address this issue, we propose NoAH, a stochastic hypergraph generative model for attributed hypergraphs. NoAH utilizes the core–fringe node hierarchy to model hyperedge formation as a series of node attachments and determines attachment probabilities based on node attributes. We further introduce NoAHFit, a parameter learning procedure for fitting NoAH to a given real-world hypergraph. Through experiments, we show that NoAH with NoAHFit more accurately reproduces the structure–attribute interplay than baseline hypergraph generative models. Our code, supplementary materials, and datasets are provided at https://github.com/jaewan01/NoAH.

Graph Neural Networks (GNNs) have demonstrated remarkable proficiency in modeling data with graph structures, yet recent research reveals their susceptibility to adversarial attacks. Traditional attack methodologies, which rely on manipulating the original graph or adding links to artificially created nodes, often prove impractical in real-world settings. This paper introduces a novel adversarial scenario involving the injection of an isolated subgraph to deceive both the link recommender and the node classifier within a GNN system. Specifically, the link recommender is mislead to propose links between targeted victim nodes and the subgraph, encouraging users to unintentionally establish connections and that would degrade the node classification accuracy, thereby facilitating a successful attack. To address this, we present the LiSA framework, which employs a dual surrogate model and bi-level optimization to simultaneously meet two adversarial objectives. Extensive experiments on real-world datasets demonstrate the effectiveness of our method.

Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether the agent has a strategy ensuring a given specification with probability 1. This well-studied problem is known to be undecidable already for very simple omega-regular objectives, because of the difficulty of reasoning on uncertain events.
We introduce a revelation mechanism which restricts information loss by requiring that, almost surely, the agent has eventually full information about the current state. Our main technical results are to construct exact algorithms for two classes of POMDPs called weakly and strongly revealing. Importantly, the decidable cases reduce to the analysis of a finite belief-support Markov decision process. This yields a conceptually simple and exact algorithm for a large class of POMDPs.

Letting AI agents interact in multi-agent settings in- troduces significant complexity in predicting and interpreting their collective behavior, with pro- found implications for trustworthy AI adoption in research and society. We present FAIRGAME (Framework for AI Agents Bias Recognition us- ing Game Theory), an open-source framework that simulates game-theoretic scenarios with LLM- based agents to systematically uncover biases aris- ing from model choice, language, agent personal- ity, and more. Applied to the Prisoner’s Dilemma and Battle of the Sexes across four LLMs and five human languages, FAIRGAME reveals inconsis- tencies across LLM models and consistent devia- tions from game-theoretic predictions; it also quan- tifies LLM-specific behavioral tendencies through a novel scoring system. Our results show that LLMs draw on prior world knowledge beyond payoff ma- trices, and that language and personality signifi- cantly shape strategic outcomes, supporting the use of reproducible and controlled simulation pipelines to predict the interacting behavior of LLM agents.

Deep neural networks are vulnerable to adversarial examples, posing serious security risks. While GAN-based attacks such as AdvGAN enable fast adversarial example generation, they typically operate in a single step, limiting attack effectiveness and transferability. In this work, we propose PAR-AdvGAN, a progressive auto-regressive GAN framework that iteratively refines adversarial perturbations. By conditioning each iteration on the previous output, PAR-AdvGAN produces stronger, more transferable attacks while maintaining low visual distortion and high generation speed. Experiments on multiple models and datasets demonstrate that PAR-AdvGAN significantly outperforms baseline methods in attack success rate, achieving up to 335.5 frames per second, highlighting its practical efficiency for black-box attack scenarios.

Recommenders are significantly shaping online information consumption. While effective at personalizing content, these systems increasingly face criticism for propagating irrelevant, unwanted, and even harmful recommendations. Such content degrades user satisfaction and contributes to significant societal issues, including misinformation, radicalization, and erosion of user trust. Although platforms offer mechanisms to mitigate exposure to undesired content, these mechanisms are often insufficiently effective and slow to adapt to users' feedback. This paper introduces an intuitive, model-agnostic, and distribution-free method that uses conformal risk control to provably bound unwanted content in personalized recommendations by leveraging simple binary feedback on items. We also address a limitation of traditional conformal risk control approaches, i.e., the fact that the recommender can provide a smaller set of recommended items, by leveraging implicit feedback on consumed items to expand the recommendation set while ensuring robust risk mitigation. Our experimental evaluation on data coming from a popular online video-sharing platform demonstrates that our approach ensures an effective and controllable reduction of unwanted recommendations with minimal effort.

We present an industrial case on workforce allocation and scheduling in the aircraft manufacturing industry, where available teams need to be assigned to logistical operations. This application presents several challenges, such as the scale of the problem, the need for fair workload distribution, and the need for methods to mitigate unforeseen disruptions due to technical malfunctions or incompatible weather conditions. We compare different Constraint Programming (CP) models for the allocation and scheduling problems, with extra focus on modeling the workload balancing component. Additionally, we investigate automatic rescheduling methods for restoring feasibility after a disruption invalidates the precomputed schedule. Our results show that by using appropriate modeling techniques, the problem can be solved in reasonable time, thereby producing fair schedules. Additionally, we show how invalidated schedules can be restored efficiently to help human operators in resolving disruptions to the schedule.

Deep neural networks often rely on spurious correlations, i.e., superficial associations between non-causal features and prediction targets. While yielding high overall accuracy during training, such reliance degrades generalization on minority groups where these correlations break down. Existing methods mitigate this issue by using external group annotations or auxiliary deterministic models, but group annotations are costly to obtain and deterministic auxiliaries may fail to capture the full spectrum of biases learned by the model. We propose Evidential Alignment, a framework that leverages uncertainty quantification to identify and suppress spurious correlations without requiring group annotations. By transforming a biased ERM model from first-order to second-order risk minimization with a Dirichlet distribution and applying an evidential calibration step that reweighs samples by their epistemic uncertainty, Evidential Alignment debiases the model while preserving core features. We provide theoretical guarantees and demonstrate strong worst-group accuracy across diverse architectures and modalities.

We establish a correspondence between (fragments of) TEL^o, a temporal extension of the EL description logic with the LTL operator O^k, and some specific kinds of formal grammars, in particular, conjunctive grammars (context-free grammars equipped with the operation of intersection). This connection implies that TEL^o does not possess the property of ultimate periodicity of models, and further leads to undecidability of query answering in TEL^o, closing a question left open since the introduction of TEL^o. Moreover, it also allows to establish decidability of query answering for some new interesting fragments of TEL^o, and to reuse for this purpose existing tools and algorithms for conjunctive grammars.

The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies on multi-objective search with A* (MOA*) have demonstrated strong performance on challenging MOSP instances. This paper presents a novel search framework that enables efficient parallelization of MOA* through different objective orderings and a unique upper-bounding strategy that, in certain cases, allows the problem dimensionality to be reduced to one. Results demonstrate that the proposed framework can significantly improve the performance of MOA*, with speedups increasing proportionally to the number of objectives.

A fundamental task in multi-agent systems is to match n agents to n alternatives (e.g., resources or tasks). This is often done by eliciting agents' ordinal rankings over the alternatives rather than their exact numerical utilities. While this simplifies elicitation, the incomplete information leads to inefficiency, captured by a worst-case measure called distortion. Recent work shows that making just a few cardinal utility queries per agent can significantly improve the distortion, with Amanatidis et al. (SIDMA 2024) achieving O(sqrt(n)) distortion with two queries per agent. We generalize their result by achieving O(n^{1/λ}) distortion with λ queries per agent, for any constant λ, which is optimal up to a constant factor given a previous lower bound by Amanatidis et al. (JAIR 2022). We extend this finding to the general social choice problem of selecting one of m alternatives based on n agents' preferences, achieving O((min(n, m))^{1/λ}) distortion with λ queries per agent.

Rule-based languages lie at the core of several areas of central importance to databases and artificial intelligence such as deductive databases and knowledge representation and reasoning. Disjunctive existential rules (a.k.a. disjunctive tuple-generating dependencies in the database literature) form such a prominent rule-based language. The goal of this work is to pinpoint the expressive power of disjunctive existential rules in terms of insightful model-theoretic properties. More precisely, given a collection C of relational structures, we show that C is axiomatizable via a finite set R of disjunctive existential rules (i.e., C is precisely the set of models of R) iff C enjoys certain model-theoretic properties. This is achieved by using the well-known property of criticality, a refined version of closure under direct products, and a novel property called diagrammatic compatibility that relies on the method of diagrams.

Counterfactual explanations have become an important paradigm for improving the transparency of machine learning models by showing how small input changes can alter model outputs. While substantial progress has been made in generating such explanations, their evaluation remains insufficiently standardized, particularly for systems that produce ranked outputs rather than single-label predictions. Existing evaluation protocols in recommender systems commonly focus only on whether the top-1 recommendation changes after perturbation. We argue that this practice can lead to inconsistent and misleading conclusions, as the relative ranking of explanation methods may vary with changes in the quality of the underlying model.

In this work, we revisit the evaluation of counterfactual explanations from a ranking perspective. We propose extending top-1 evaluation to list-wise top-$k$ protocols that assess explanation effectiveness across multiple highly ranked outputs. Through experiments on multiple datasets, recommender architectures, and explanation methods, we show that top-$k$ evaluation substantially improves consistency and yields more reliable comparisons between competing explainers.

Our findings highlight a broader methodological lesson for explainable AI: when models return ranked results, explanation quality should be assessed using ranking-aware evaluation protocols rather than top-1 criteria alone.

Driving progress of AI models and agents requires comparing their performance on standardized benchmarks; for general agents, individual performances must be aggregated across a potentially wide variety of different tasks. In this extended abstract, we describe a ranking scheme inspired by social choice frameworks, called Soft Condorcet Optimization (SCO), to compute the optimal ranking of agents: the one that makes the fewest mistakes in predicting the agent comparisons in the evaluation data. This optimal ranking is the maximum likelihood estimate when evaluation data (which we view as votes) are interpreted as noisy samples from a ground truth ranking, a solution to Condorcet's original voting system criteria. SCO ratings are maximal for Condorcet winners when they exist, which we show is not necessarily true for the classical rating system Elo. In practice, SCO serves as an accurate approximation to the Kemeny-Young voting method, excels in the sparse data regime, and provides the best approximation to the optimal ranking compared to every baseline on a Diplomacy player ranking problem with 31,094 games and 52,958 agents.

Large Language Models are typically trained with next-turn rewards, limiting their ability to optimize for long-term interaction. As a result, they often respond passively to ambiguous or open-ended user requests, failing to help users reach their ultimate intents and leading to inefficient conversations. To address these limitations, we introduce CollabLLM, a novel and general training framework that enhances multiturn human-LLM collaboration. Its key innovation is a collaborative simulation that estimates the long-term contribution of responses using Multiturn-aware Rewards. By reinforcement fine-tuning these rewards, CollabLLM goes beyond responding to user requests and actively uncovers user intent and offers insightful suggestions--a key step toward more human-centered AI. We also devise a multiturn interaction benchmark with three challenging tasks such as document creation. COLLABLLM significantly outperforms our baselines with averages of 18.5% higher task performance and 44.3% improved interactivity by LLM judges. Finally, we conduct a large user study with 201 judges, where CollabLLM increases user satisfaction by 17.6% and reduces user spent time by 10.4%.

Large Language Models (LLMs) are often used in autonomous decision-making, where they have to sample options from vast action spaces.
Here we present a summary of the work studying the heuristics that guide this sampling process and show it resembles that of human decision-making: comprising a descriptive component (reflecting statistical norm) and a prescriptive component (implicit ideal encoded in the LLM). We show that the deviation of a sample from the statistical norm towards a prescriptive component consistently appears in concepts across diverse real-world domains. To further illustrate the theory, we demonstrate that concept prototypes in LLMs are affected by prescriptive norms, similar to the concept of normality in humans. This finding has implications in LLM based agentic systems, explaining their exploration behavior and biases in decision making.

Most of the widely used estimators of the average treatment effect (ATE) in causal inference rely on the assumptions of unconfoundedness and overlap. Unconfoundedness requires that the observed covariates account for all correlations between the outcome and treatment. Overlap requires the existence of randomness in treatment decisions for all individuals. Nevertheless, many types of studies frequently violate unconfoundedness or overlap; for instance, observational studies with deterministic treatment decisions, popularly known as Regression Discontinuity designs, violate overlap.

In this paper, we initiate the study of general conditions that enable the identification of the average treatment effect, extending beyond unconfoundedness and overlap. In particular, following the paradigm of statistical learning theory, we provide an interpretable condition that is sufficient and necessary for the identification of ATE. Moreover, this condition can be used to characterize other treatment effects, such as the average treatment effect on the treated (ATT), as well. To illustrate the utility of our condition, we present several well-studied scenarios where our condition is satisfied and, hence, we prove that ATE can be identified in regimes that prior works could not capture. For example, under mild assumptions on the data distributions, this holds for the models proposed by Tan (2006) and Rosenbaum (2002), and the Regression Discontinuity design model introduced by Thistlethwaite and Campbell (1960). For each of these scenarios, we also show that, under natural additional assumptions, ATE can be estimated from finite samples.

We believe these findings open new avenues for bridging learning-theoretic insights and causal inference methodologies, particularly in observational studies with complex treatment mechanisms.