Association for the Advancement of Artificial Intelligence: AAAI Publications
Not a member yet
26155 research outputs found
Sort by
Scalable Quantum-Inspired Optimization Through Dynamic Qubit Compression
No full textHard combinatorial optimization problems, often mapped to Ising models, promise potential solutions with quantum advantage but are constrained by limited qubit counts in near-term devices. We present an innovative quantum-inspired framework that dynamically compresses large Ising models to fit available quantum hardware of different sizes. Thus, we aim to bridge the gap between large-scale optimization and current hardware capabilities. Our method leverages a physics-inspired GNN architecture to capture complex interactions in Ising models and accurately predict alignments among neighboring spins (aka qubits) at ground states. By progressively merging such aligned spins, we can reduce the model size while preserving the underlying optimization structure. It also provides a natural trade-off between the solution quality and size reduction, meeting different hardware constraints of quantum computing devices. Extensive numerical studies on Ising instances of diverse topologies show that our method can reduce instance size at multiple levels with virtually no losses in solution quality on the latest D-wave quantum annealers
Generalizing Constraint Models in Constraint Acquisition
No full textConstraint Acquisition (CA) aims to widen the use of constraint programming by assisting users in the modeling process. However, most CA methods suffer from a significant drawback: they learn a single set of individual constraints for a specific problem instance, but cannot generalize these constraints to the parameterized constraint specifications of the problem. In this paper, we address this limitation by proposing GenCon, a novel approach to learn parameterized constraint models capable of modeling varying instances of the same problem.
To achieve this generalization, we make use of statistical learning techniques at the level of individual constraints.
Specifically, we propose to train a classifier to predict, for any possible constraint and parameterization, whether the constraint belongs to the problem.
We then show how, for some classes of classifiers, we can extract decision rules to construct interpretable constraint specifications. This enables the generation of ground constraints for any parameter instantiation.
Additionally, we present a generate-and-test approach that can be used with any classifier, to generate the ground constraints on the fly.
Our empirical results demonstrate that our approach achieves high accuracy and is robust to noise in the input instances
Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems
No full textVariable ordering heuristics (VOH) play a central role in solving Constraint Satisfaction Problems (CSP). The performance of different VOHs may vary greatly when solving the same CSP instance, so identifying an efficient candidate VOH for a given CSP has been a key issue in the community. In this study, we propose a prediction-based approach to adaptively select efficient VOHs for different CSPs from a set of candidates. Our work demonstrates that efficient candidate VOHs can be identified by learning from the topology of search trees. Specifically, we propose to represent the topology of a binary search tree by the sequence of the Numbers of Positive Decisions (NPD) made before each failure occurs. Based on the representation, we predict the total failure number of a search tree from its beginning part. When solving a CSP, we run a probing procedure to obtain the NPD sequences generated by candidate VOHs and select an efficient one for the resolution according to the prediction results. Our experiments show that the Long Short Term Memory model and Gradient Boosting Decision Tree models trained with the search trees sampled from easy instances are effective in identifying efficient VOHs for hard instances. The models capture some common structure properties hidden in the search trees of different problems. Our approach outperforms the state-of-the-art adaptive VOHs in terms of the number of solved instances and the PAR2 score of runtime
Spatiotemporal-aware Trend-Seasonality Decomposition Network for Traffic Flow Forecasting
No full textTraffic prediction is critical for optimizing travel scheduling and enhancing public safety, yet the complex spatial and temporal dynamics within traffic data present significant challenges for accurate forecasting. In this paper, we introduce a novel model, the Spatiotemporal-aware Trend-Seasonality Decomposition Network (STDN). This model begins by constructing a dynamic graph structure to represent traffic flow and incorporates novel spatio-temporal embeddings to jointly capture global traffic dynamics. The representations learned are further refined by a specially designed trend-seasonality decomposition module, which disentangles the trend-cyclical component and seasonal component for each traffic node at different times within the graph. These components are subsequently processed through an encoder-decoder network to generate the final predictions. Extensive experiments conducted on real-world traffic datasets demonstrate that STDN achieves superior performance with remarkable computation cost. Furthermore, we have released a new traffic dataset named JiNan, which features unique inner-city dynamics, thereby enriching the scenario comprehensiveness in traffic prediction evaluation
Towards Global-Topology Relation Graph for Inductive Knowledge Graph Completion
No full textKnowledge Graphs (KGs) are structured data presented as directed graphs. Due to the common issues of incompleteness and inaccuracy encountered during construction and maintenance, completing KGs becomes a critical task. Inductive Knowledge Graph Completion (KGC) excels at inferring patterns or models from seen data to be applied to unseen data. However, existing methods mainly focus on new entities, while relations are usually randomly initialized. To this end, we propose TARGI, a simple yet effective inductive method for KGC. Specifically, we first construct a global relation graph for each topology from a global graph perspective, thus leveraging the in-variance of relation structures. We then utilize this graph to aggregate the rich embeddings of new relations and new entities, thereby performing KGC robustly in inductive scenarios. This successfully addresses the excessive reliance on the degree of relations and resolves the high complexity and limited scope of enclosing subgraph sampling in existing fully inductive algorithms. We conduct KGC experiments on six inductive datasets using inference data where entities are entirely new and new relations at 100 percent, 50 percent, and 0 percent radios. Extensive results demonstrate that our model accurately learns the topological structures and embeddings of new relations, and guides the embedding learning of new entities. Notably, our model outperforms 15 SOTA methods, especially in two fully inductive datasets
Spatial-Temporal Heterogenous Graph Contrastive Learning for Microservice Workload Prediction
No full textWith the widely adoption of microservice architecture in the cloud computing industry, accurate prediction of workloads, especially CPU cores, can support reasonable resource allocation, thereby optimizing the resource utilization of the system. However, workload prediction is challenging in two dimensions. In the temporal dimension, workload series 1) has non-stationary characteristics, leading to poor predictability; 2) has a multi-periodic nature with entangled temporal patterns; 3) may be influenced by dynamic system states like response time and number of requests. In the spatial dimension, when regarding microservices as nodes in a distributed system, there is no topology caused by physical connections, but exists complex similarity dependencies. Extracting robust spatial features from these dependencies presents difficulties.
To address these, we propose STEAM, a Spatio Temporal Heterogenous Graph Contrastive Learning for Microservice Workload Prediction. STEAM leverages non-stationary decomposition self-attention to extract temporal features from non-stationary and multi-periodic workload series, while the decoupled embedding is used to capture system state information of microservices. By treating microservices as nodes and constructing a similarity graph, STEAM effectively models the similarity relationships between microservices. To reduce the prior interference caused by the similarity threshold and improve the robustness, STEAM constructs two heterogeneous augmentation views and uses contrastive learning to extract the shared consistent spatial features. The multi-scale learning is adopted to model the long- and short-term temporal features, forming a spatio-temporal stacking structure.
Experiments on two datasets, including MS dataset obtained from Ant Group, which is one of the world’s largest cloud service providers, demonstrate the superiority of STEAM
K-ON: Stacking Knowledge on the Head Layer of Large Language Model
No full textRecent advancements in large language models (LLMs) have significantly improved various natural language processing (NLP) tasks. Typically, LLMs are trained to predict the next token, aligning well with many NLP tasks. However, in knowledge graph (KG) scenarios, entities are the fundamental units and identifying an entity requires at least several tokens. This leads to a granularity mismatch between KGs and natural languages. To address this issue, we propose K-ON, which integrates KG knowledge into the LLM by employing multiple head layers for next k-step prediction. K-ON can not only generate entity-level results in one step, but also enables contrastive loss against entities, which is the most powerful tool in KG representation learning. Experimental results show that K-ON outperforms state-of-the-art methods that incorporate text and even the other modalities
Bridging Traffic State and Trajectory for Dynamic Road Network and Trajectory Representation Learning
No full textEffective urban traffic management is vital for sustainable city development, relying on intelligent systems with machine learning tasks such as traffic flow prediction and travel time estimation. Traditional approaches usually focus on static road network and trajectory representation learning, and overlook the dynamic nature of traffic states and trajectories, which is crucial for downstream tasks. To address this gap, we propose TRACK, a novel framework to bridge traffic state and trajectory data for dynamic road network and trajectory representation learning. TRACK leverages graph attention networks (GAT) to encode static and spatial road segment features, and introduces a transformer-based model for trajectory representation learning. By incorporating transition probabilities from trajectory data into GAT attention weights, TRACK captures dynamic spatial features of road segments.
Meanwhile, TRACK designs a traffic transformer encoder to capture the spatial-temporal dynamics of road segments from traffic state data. To further enhance dynamic representations, TRACK proposes a co-attentional transformer encoder and a trajectory-traffic state matching task. Extensive experiments on real-life urban traffic datasets demonstrate the superiority of TRACK over state-of-the-art baselines. Case studies confirm TRACK’s ability to capture spatial-temporal dynamics effectively
Event2Tracking: Reconstructing Multi-Agent Soccer Trajectories Using Long-Term Multimodal Context
No full textSoccer is a rich testbed for studying multi-agent adversarial systems. In this work we focus on the task of reconstructing the noisy trajectories of soccer agents (players and the ball). Previous works that model the behaviours of agents in soccer are limited in two respects: (i) they only focus on short-term context windows (less than or equal to 10 seconds) which are not suitable for reconstructing trajectories impacted by long-term noise, and (ii) they exclusively rely on trajectory context, and do not leverage soccer's auxiliary data streams that can provide additional context. Our Event2Tracking model addresses these limitations. First, our architecture models soccer's long-term structure by processing long-term trajectories (60 seconds in duration). Secondly, our architecture is multimodal. Specifically, it fuses soccer tracking data with event data (which specifies the high-level semantic events that transpire in a game), providing rich context that cannot strictly be inferred from the raw trajectories. We evaluate our method empirically using a reconstruction loss metric. Compared to state-of-the-art approaches, our method substantially improves the accuracy of the ball's and players' reconstructed trajectories
From Your Block to Our Block: How to Find Shared Structure Between Stochastic Block Models over Multiple Graphs
No full textStochastic Block Models (SBMs) are a popular approach to modeling single real-world graphs. The key idea of SBMs is to partition the vertices of the graph into blocks with similar edge densities within, as well as between different blocks. However, what if we are given not one but multiple graphs that are unaligned and of different sizes? How can we find out if these graphs share blocks with similar connectivity structures?
In this paper, we propose the shared stochastic block modeling (SSBM) problem, in which we model n graphs using SBMs that share parameters of s blocks. We show that fitting an SSBM is NP-hard, and consider two approaches to fit good models in practice. In the first, we directly maximize the likelihood of the shared model using a Markov chain Monte Carlo algorithm. In the second, we first fit an SBM for each graph and then select which blocks to share. We propose an integer linear program to find the optimal shared blocks and to scale to large numbers of blocks, we propose a fast greedy algorithm. Through extensive empirical evaluation on synthetic and real-world data, we show that our methods work well in practice