Anomaly detection is one of the most significant tasks in industrial automatic maintenance, such as in distributed cloud systems. However, the implementation of existing anomaly detection methods is still challenging in (i) capturing the complex spatial and temporal correlations of multivariate time series, (ii) effectively adapting to the unsupervised condition, and (iii) generalizing across nodes in distributed systems. To address these challenges, we design a multi-perspective spatio-temporal attention model, called STAMP, which consists of a prediction module ST-ATTN, a reconstruction module AutoEncoder, and an adversarial optimizing module. Specifically, ST-ATTN leverages multiple attention mechanisms to perform spatio-temporal learning from both local and global perspectives, AutoEncoder is utilized to fit implicit representations, and the adversarial optimization module employs a min-max training strategy to enhance the learning capability. By introducing pre-training strategies, STAMP can be effectively adapted to distributed systems with a strong generalization ability. Furthermore, to cope with the practical unlabeled data conditions, we propose an unsupervised framework compatible with not only STAMP but also other advanced detection models. In this framework, a screening process is first conducted by traditional methods to generate a training set of pseudo-normal samples. Second, the models are trained and then used for detection. The framework can be further optimized by performing feature selection based on model-derived information for a better detectability. Extensive experiments in real-world datasets demonstrate that the proposed model and framework achieve superior performance when compared with baselines under both semi-supervised and unsupervised conditions. In particular, the detection framework has already been applied in Huawei's GaussDB (DWS) system.

Anomaly diagnosis is a fundamental problem in operation and maintenance of distributed cloud databases. Existing deep learning based methods solve this problem by classifying the anomalies with different root causes. However, since anomalies seldom occur, and anomalies with the same root cause may exhibit significantly different behaviors across different cloud database clusters, existing methods often lack sufficient training data, and they cannot generalize well from some clusters to others. Therefore, we take both anomaly and normal data into consideration, based on an observation that the discrepancy between the anomaly and normal data is relatively consistent compared to the behaviours of anomalies themselves. We design a Siamese Discrepancy Network (SDN) to learn representations of such discrepancy under the case that only a small amount of training data is available. In addition, a discrepancy-based diagnosis paradigm is proposed to construct training data for SDN and diagnose based on representations of discrepancy learned by SDN. Finally, we develop an anomaly interpretation method based on SDN, which accurately locates the symptom KPIs and root cause KPIs. Extensive experiments are conducted on both synthetic and real-world datasets. The experimental results demonstrate that the proposed method outperforms existing methods with respect to anomaly diagnosis and anomaly interpretation. In particular, the anomaly diagnosis framework has already been applied in Huawei's GaussDB (DWS) system.

Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces finds extensive applications in databases, information retrieval, recommender systems, etc. While graph-based methods have emerged as the leading solution for ANNS due to their superior query performance, they still face several challenges, such as struggling with local optima and redundant computations. These issues arise because existing methods (i) fail to fully exploit the topological information underlying the proximity graph G, and (ii) suffer from severe distribution mismatches between the base data and queries in practice. To this end, this paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query Awareness, as a lightweight and adaptive module atop the graph-based indexes to accelerate ANNS. Specifically, GATE formulates the critical problem to identify an optimal entry point in the proximity graph for a given query, facilitating faster online search. By leveraging the inherent clusterability of high-dimensional data, GATE first extracts a small set of hub nodes V as candidate entry points. Then, resorting to a contrastive learning-based two-tower model, GATE encodes both the structural semantics underlying G and the query-relevant features into the latent representations of these hub nodes V. A navigation graph index on V is further constructed to minimize the model inference overhead. Extensive experiments demonstrate that GATE achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.

Maximum Inner Product Search (MIPS) is a fundamental challenge in machine learning and information retrieval, particularly in high-dimensional data applications. Existing approaches to MIPS either rely solely on Inner Product (IP) similarity, which faces issues with local optima and redundant computations, or reduce the MIPS problem to the Nearest Neighbor Search under the Euclidean metric via space projection, leading to topology destruction and information loss. Despite the divergence of the two paradigms, we argue that there is no inherent binary opposition between IP and Euclidean metrics. By stitching IP and Euclidean in the design of indexing and search algorithms, we can significantly enhance MIPS performance. Specifically, this paper explores the theoretical and empirical connections between these two metrics from the MIPS perspective. Our investigation, grounded in graph-based search, reveals that different indexing and search strategies offer distinct advantages for MIPS, depending on the underlying data topology. Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS). To facilitate parameter tuning for optimal performance, we identify three statistical indicators that capture essential data topology properties and correlate strongly with parameter tuning. Extensive experiments on 12 real-world datasets demonstrate that MAG outperforms existing state-of-the-art methods, achieving up to 4x search speedup while maintaining adaptability and scalability.

Maximum Inner Product Search (MIPS) for high-dimensional vectors is pivotal across databases, information retrieval, and artificial intelligence. Existing methods either reduce MIPS to Nearest Neighbor Search (NNS) while suffering from harmful vector space transformations, or attempt to tackle MIPS directly but struggle to mitigate redundant computations due to the absence of the triangle inequality. This paper presents a novel theoretical framework that equates MIPS with NNS without requiring space transformation, thereby allowing us to leverage advanced graph-based indices for NNS and efficient edge pruning strategies, significantly reducing unnecessary computations. Despite a strong baseline set by our theoretical analysis, we identify and address two persistent challenges to further refine our method: the introduction of the P roximity Graph with S pherical P athway (PSP), designed to mitigate the issue of MIPS solutions clustering around large-norm vectors, and the implementation of A daptive E arly T ermination (AET), which efficiently curtails the excessive exploration once an accuracy bottleneck is reached. Extensive experiments reveal that our method is superior to existing state-of-the-art techniques in search efficiency, scalability, and practical applicability. Compared with state-of-the-art graph-based methods, it achieves an average 35% speed-up in query processing and a 3× reduction in index size. Notably, our approach has been validated and deployed in the search engines of Shopee, a well-known online shopping platform. Our code and an industrial-scale dataset for offline evaluation will also be released to address the absence of e-commerce data in public benchmarks.

Generating explanations for graph neural networks (GNNs) has been studied to understand their behaviors in analytical tasks such as graph classification. Existing approaches aim to understand the overall results of GNNs rather than providing explanations for specific class labels of interest, and may return explanation structures that are hard to access, nor directly queryable. We propose GVEX, a novel paradigm that generates Graph Views for GNN EXplanation. (1) We design a two-tier explanation structure called explanation views. An explanation view consists of a set of graph patterns and a set of induced explanation subgraphs. Given a database G of multiple graphs and a specific class label l assigned by a GNN-based classifier M, it concisely describes the fraction of G that best explains why l is assigned by M. (2) We propose quality measures and formulate an optimization problem to compute optimal explanation views for GNN explanation. We show that the problem is Σ2P-hard. (3) We present two algorithms. The first one follows an explain-and-summarize strategy that first generates high-quality explanation subgraphs which best explain GNNs in terms of feature influence maximization, and then performs a summarization step to generate patterns. We show that this strategy provides an approximation ratio of 1/2. Our second algorithm performs a single-pass to an input node stream in batches to incrementally maintain explanation views, having an anytime quality guarantee of 1/4-approximation. Using real-world benchmark data, we experimentally demonstrate the effectiveness, efficiency, and scalability of GVEX. Through case studies, we showcase the practical applications of GVEX.

Predicting the Origin-Destination (OD) traffic is a fundamental problem and of great significance in transportation research and civil engineering. There are three expectations for a good OD traffic predictor: 1) higher accuracy; 2) longer horizon; 3) better applicability. This paper proposes a Hybrid Spatio-Temporal Network (HSTN) model to predict OD traffic. The model emphasizes capturing more comprehensive spatial correlations among the sources of the traffic flows and temporal correlations between historical values and future prediction. HSTN is designed to have a Hybrid Spatial Module (HSM) and a Hybrid Temporal Module (HTM). HSM consists of three units to learn three types of spatial relationships and HTM consists of two units to quantity the influence of the input sequence on the target result. We evaluate HSTN on three real-world datasets of different travel modes in different cities. Results show that the proposed HSTN outperforms existing methods in both short-term and long-term predictions in all datasets.