United States

In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-step the edge is available. Two vertices are connected if there is a path connecting them in which the edges are traversed in increasing order of their labels. We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time $a$ and the overall number of labels is minimum.

The problem, called  \emph{Minimum Aged Labeling} (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks, where carefully choosing the time-labels can significantly reduce infrastructure costs, fuel consumption, or greenhouse gases.

Problem MAL has previously been proved to be NP-complete on undirected graphs and APX-hard on directed graphs. 
In this paper, we extend our knowledge on the complexity and approximability of MAL in several directions. We first show that the problem cannot be approximated within a factor better than $O(\log n)$ when $a\geq 2$, unless $\text{P} = \text{NP}$, and a factor better than $2^{\log ^{1-\epsilon} n}$ when $a\geq 3$, unless $\text{NP}\subseteq \text{DTIME}(2^{\text{polylog}(n)})$, where $n$ is the number of vertices in the graph. Then we give a set of approximation algorithms that, under some conditions, almost match these lower-bounds. In particular, we show that the approximation depends on a relation between $a$ and the diameter of the input graph.

We further establish a connection with a foundational optimization problem on static graphs called \emph{Diameter Constrained Spanning Subgraph} (DCSS) and show that our hardness results also apply to DCSS.

AAAI 2025

Approximating Optimal Labelings for Temporal Connectivity

routing

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

technical paper

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Uncertainty quantification in travel time estimation (TTE) aims to estimate the confidence interval for travel time, given the origin (O), destination (D), and departure time (T). Accurately quantifying this uncertainty requires generating the most likely path and assessing travel time uncertainty along the path. This involves two main challenges: 1) Predicting a path that aligns with the ground truth, and 2) modeling the impact of travel time in each segment on overall uncertainty under varying conditions. We propose DutyTTE to address these challenges. For the first challenge, we introduce a deep reinforcement learning method to improve alignment between the predicted path and the ground truth, providing more accurate travel time information from road segments to improve TTE. For the second challenge, we propose a mixture of experts guided uncertainty quantification mechanism to better capture travel time uncertainty for each segment under varying contexts. Additionally, we calibrate our results using Hoeffding's upper-confidence bound to provide statistical guarantees for the estimated confidence intervals. Extensive experiments on two real-world datasets demonstrate the superiority of our proposed method. The code is available at https://anonymous.4open.science/r/DutyTTE-31D3/.

DutyTTE: Deciphering Uncertainty in Origin-Destination Travel Time Estimation

Large Language Models (LLMs) are increasingly being integrated into services such as ChatGPT to provide responses to user queries. To mitigate potential harm and prevent misuse, there have been concerted efforts to align the LLMs with human values and legal compliance by incorporating various techniques, such as Reinforcement Learning from Human Feedback (RLHF), into the training of the LLMs. However, recent research has exposed that even aligned LLMs are susceptible to adversarial manipulations known as Jailbreak Attacks. To address this challenge, this paper proposes a method called **Token Highlighter** to inspect and mitigate the potential jailbreak threats in the user query. Token Highlighter introduced a concept called $\mathtt{Affirmation}$ $\mathtt{Loss}$ to measure the LLM's willingness to answer the user query. It then uses the gradient of $\mathtt{Affirmation}$ $\mathtt{Loss}$ for each token in the user query to locate the jailbreak-critical tokens. Further, Token Highlighter exploits our proposed ***Soft Removal*** technique to mitigate the jailbreak effects of critical tokens via shrinking their token embeddings. Experimental results on two aligned LLMs (LLaMA-2 and Vicuna-V1.5) demonstrate that the proposed method can effectively defend against a variety of Jailbreak Attacks while maintaining competent performance on benign questions of the AlpacaEval benchmark. In addition,  **Token Highlighter** is a cost-effective and interpretable defense because it only needs to query the protected LLM once to compute the $\mathtt{Affirmation}$ $\mathtt{Loss}$ and can highlight the critical tokens upon refusal.

Token Highlighter: Inspecting and Mitigating Jailbreak Prompts for Large Language Models

Recent work has proposed automated red-teaming methods for testing the vulnerabilities of a given target large language model (LLM).  These methods use LLMs to uncover inputs that induce harmful behavior in a target LLM. In this paper, we study red-teaming strategies that enable a targeted security assessment. We propose an optimization framework for red-teaming with proximity constraints, where the discovered prompts must be similar to reference prompts from a given dataset. This dataset serves as a template for the discovered prompts, anchoring the search for test-cases to specific topics, writing styles, or types of harmful behavior. We show that established auto-regressive model architectures do not perform well in this setting. We therefore introduce a black-box red-teaming method based on text-diffusion models: Diffusion for Auditing and Red-Teaming (DART). DART modifies the reference prompt by perturbing it in the embedding space, directly controlling the amount of change introduced. We systematically evaluate our method by comparing its effectiveness with established methods based on model fine-tuning and zero- and few-shot prompting. Our results show that DART is significantly more effective at discovering harmful inputs in close proximity to the reference prompt.

Text-Diffusion Red-Teaming of Large Language Models: Unveiling Harmful Behaviors with Proximity Constraints

Prior work found that superhuman Go AIs like KataGo can be defeated by simple adversarial strategies. In this paper, we study if defenses can improve KataGo's worst-case performance. We test three natural defenses: adversarial training on hand-constructed positions, iterated adversarial training, and changing the network architecture. We find that though some of these defenses protect against previously discovered attacks, none withstand adaptive attacks.
In particular, we are able to train new adversaries that reliably defeat our defended agents by causing them to blunder in ways humans would not. Our results suggest that building robust AI systems is challenging even for superhuman systems in narrow domains like Go.

Can Go AIs Be Adversarially Robust?

We consider infinite-horizon Markov Decision Processes where parameters, such as transition probabilities, are unknown and estimated from data. The popular distributionally robust approach to addressing the parameter uncertainty can sometimes be overly conservative. In this paper, we utilize the recently proposed formulation, Bayesian risk Markov Decision Process (BR-MDP), to address parameter (or epistemic) uncertainty in MDPs. To solve the infinite-horizon BR-MDP with a class of convex risk measures, we propose a computationally efficient approach of approximate bilevel difference convex programming (ABDCP). The optimization is performed offline and produces the optimal policy that is represented as a finite state controller with desirable performance guarantees. We also demonstrate the empirical performance of the infinite-horizon BR-MDP formulation and proposed algorithms.

Approximate Bilevel Difference Convex Programming for Bayesian Risk Markov Decision Processes

Human-object contact (HOT) is designed to accurately identify the areas where humans and objects come into contact. Current methods frequently fail to account for scenarios where objects are frequently blocking the view, resulting in inaccurate identification of contact areas. To tackle this problem, we suggest using a perspective interaction HOT detector called PIHOT, which utilizes a depth map generation model to offer depth information of humans and objects related to the camera, thereby preventing false interaction detection. Furthermore, we use mask dilatation and object restoration techniques to restore the texture details in covered areas, improve the boundaries between objects, and enhance the perception of humans interacting with objects. Moreover, a spatial awareness perception is intended to concentrate on the characteristic features close to the points of contact. The experimental results show that the PIHOT algorithm achieves state-of-the-art performance on three benchmark datasets for HOT detection tasks. Compared to the most recent DHOT, our method enjoys an average improvement of 13\%, 27.5\%, 16\%, and 18.5\% on SC-Acc., C-Acc., mIoU, and wIoU metrics, respectively.

Precision-Enhanced Human-Object Contact Detection via Depth-Aware Perspective Interaction and Object Texture Restoration

It is widely known that state-of-the-art machine learning models, including vision and language models, can be seriously compromised by adversarial perturbations. It is therefore increasingly relevant to develop capabilities to certify their performance in the presence of the most effective adversarial attacks. Our paper offers a new approach to certify the performance of machine learning models in the presence of adversarial attacks with population level risk guarantees. In particular, we introduce the notion of $(\alpha,\zeta)$-safe machine learning model. We propose a hypothesis testing procedure, based on the availability of a calibration set, to derive statistical guarantees providing that the probability of declaring that the adversarial (population) risk of a machine learning model is less than $\alpha$ (i.e. the model is safe), while the model is in fact unsafe (i.e. the model adversarial population risk is higher than $\alpha$), is less than $\zeta$. We also propose Bayesian optimization algorithms to determine efficiently whether a machine learning model is $(\alpha,\zeta)$-safe in the presence of an adversarial attack, along with statistical guarantees. We apply our framework to a range of machine learning models — including various sizes of vision Transformer (ViT) and ResNet models — impaired by a variety of adversarial attacks, such as PGDAttack, MomentumAttack, GenAttack and BanditAttack, to illustrate the operation of our approach. Importantly, we show that ViT's are generally more robust to adversarial attacks than ResNets, and ViT-large is more robust than smaller models. Our approach goes beyond existing empirical adversarial risk-based certification guarantees. It formulates rigorous (and provable) performance guarantees that can be used to satisfy regulatory requirements mandating the use of state-of-the-art technical tools.

PROSAC: Provably Safe Certification for Machine Learning Models under Adversarial Attacks

Time series data, prevalent in fields like medical, e-commerce, finance, etc., is used for forecasting, such as predicting next quarter’s product demand based on past trends. However, some problems necessitate causal models to answer questions like “What the product demand would have been without a specific intervention (e.g., products with slower delivery time suppressed from the search results)?” 
Such questions require causal models to estimate unobserved counterfactual outcome. In this paper, we propose a novel Graph Causal Forecasting (GCF) model, that predicts the unobserved demand leveraging the relationship of a product with other similar products in the marketplace (spatial aspect), along with change in demand over time for each product (temporal aspect). The core idea is to estimate the counterfactual outcome using a synthetic control unaffected by the treatment. Our approach uses RGCN-dilated CNN based network, which leverages domain knowledge to automatically design a synthetic control during training. Using GCF for our demand forecasting problem, we achieve 75.3% lower MAPE compared to baseline. We use the forecasted values to recommend high demand products, in terms of our business metric (discussed later) which tracks the quality of these recommendations, we achieve a significant jump of 61.2%. Moreover, it adds 67.8% more high demand products to the marketplace, compared to existing model in production.
Deployment of GCF in 2023, led to +1399 bps improvement in number of products with a view from customers, and +310 bps improvement in number of products with a sale. We also compare GCF with state of the art forecasting methods on a semi-synthetic data, created by simulating a treatment on open source traffic data METR-LA. We achieve 30% lower MSE against TGCN, a time series forecasting approach and 30% lower MSE against CRN and 25% lower MSE against Google Causal Impact model, both of which are causal forecasting approaches.

GCF: Estimating Unobserved Demand Using Graph Causal Forecasting

Cotton is a critical agricultural product and industrial raw material, playing a key role in the national economies and people's living conditions, particularly in developing countries. However, cotton picking and processing often result in the contamination with various foreign fibers, such as hair, hemp rope, plastic film, and polypropylene rope. These contaminants are difficult to remove during textile processing and tend to break into small fragments, significantly reducing the quality of cotton products and negatively impacting the cotton industry. In this paper, we present an AI-enabled hardware-software integrated system--XCotton, for identifying and removing foreign fibers. Our system has been deployed in actual cotton production environments in the multiple regions in China, Central Asia, and Africa. XCotton achieves a cleaning efficiency of 1000kg/h, representing a 43% improvement, with only 14 kWh energy consumption (63% less). Moreover, XCotton brings significant business values to its manufacturer and clients. XCotton not only enhances the quality of cotton products but also contributes to the value-adding and upgrading of the cotton industry in developing regions, supporting economic growth and improving living conditions.

XCotton: Advancing AI-Enabled Hardware/Software Integrated System for Foreign Fiber Cleaning

In the domain of merchant-oriented risk control decisions within e-commerce, balancing the effectiveness of risk management with merchant satisfaction remains a critical challenge. Strict risk control strategies, while effectively mitigating risks, often lead to increased merchant dissatisfaction. Conversely, loose policies could enhance the merchant experience but raise the likelihood of incidents, potentially incurring substantial financial losses. Additionally, determining personalized risk control strategies for different merchants to achieve optimal overall risk management effectiveness is crucial. Given the high uncertainty in the outcomes of different risk control decisions, manual strategy allocation and real-time adjustments are commonly implemented in practice, leading to significant human and resource costs. In this work, we present a novel automated risk control decision framework that utilizes unbiased data-driven decision-making and dynamic optimization to automate the allocation and adjustment of risk control strategies. Our proposed solution adapts to various online business requirements, demonstrating exceptional risk management performance and significantly reducing overall costs. This approach has been extensively deployed and validated in Alibaba's risk control operations, achieving large-scale automated risk control decisions.

Downloads

Next from AAAI 2025

DutyTTE: Deciphering Uncertainty in Origin-Destination Travel Time Estimation

Similar lecture

Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2025

DutyTTE: Deciphering Uncertainty in Origin-Destination Travel Time Estimation

Similar lecture

Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule

Downloads