High-dimensional vector similarity search (HVSS) is critical for many data processing and AI applications. However, traditional HVSS methods often require extensive data access for distance calculations, leading to inefficiencies. Triangle-inequality-based lower bound pruning is a widely used technique to reduce the number of data access in low-dimensional spaces but becomes less effective in high-dimensional settings. This is attributed to the ''distance concentration'' phenomenon, where the lower bounds derived from the triangle inequality become too small to be useful. To address this, we propose TRIM, which enhances the effectiveness of traditional triangle-inequality-based pruning in high-dimensional vector similarity search using two key ways: (1) optimizing landmark vectors used to form the triangles, and (2) relaxing the lower bounds derived from the triangle inequality, with the relaxation degree adjustable according to user's needs. TRIM is a versatile operation that can be seamlessly integrated into both memory-based (e.g., HNSW, IVFPQ) and disk-based (e.g., DiskANN) HVSS methods, reducing distance calculations and disk access. Extensive experiments show that TRIM enhances memory-based methods, improving graph-based search by up to 90% and quantization-based search by up to 200%, while achieving a pruning ratio of up to 99%. It also reduces I/O costs by up to 58% and improves efficiency by 102% for disk-based methods, while preserving high query accuracy. Our source code is available at https://github.com/petrizhang/TRIM.

Reverse$k$nearest neighbor search$(\mathbf{R}k\mathbf{NNS})$plays an important role in various data processing and analysis tasks, seeking to pinpoint data considering the query data$q$among their$k$nearest neighbors. As large models gain popularity, processing high-dimensional vectors has become more and more widespread. However, existing$\mathbf{R}k\mathbf{NNS}$solutions face inefficiency when handling large-scale high-dimensional vectors due to their sensitivity to data dimensions and sizes during index construction or the verification of numerous candidate results in the query phase. Motivated by these challenges and the inherent intricacies of high-dimensional data processing, in this paper, we study an approximate version of the$\mathbf{R}k\mathbf{NNS}$problem$(\mathbf{R}k\mathbf{ANNS})$for high-dimensional vectors, aiming to offer efficient and practical solutions. To this end, we propose a new proximity-graph-based index called HAMG, which enables finding the query results within$k$hops from$q$. We also present a user-friendly query algorithm on HAMG that can adaptively adjust the search scope based on the desired query recall of users. To further enhance the query process, two pruning strategies are proposed to reduce the number of candidates requiring verification. Extensive experiments validate that HAMG scales well for data dimensions and sizes, and our query algorithm improves query efficiency by up to two orders of magnitude while maintaining comparable query accuracy against existing approaches.

Information networks generally exhibit three characteristics, namely dynamicity, heterogeneity, and node attribute diversity. However, most existing network embedding approaches only consider two of the three when embedding each node into low-dimensional space. Adding to such an existing approach a technique of processing the remaining characteristic can easily cause incompatibility. One solution to process the three characteristics together is to treat the dynamic heterogeneous attributed network (DHAN) as a temporal sequence of heterogeneous attributed network (HAN) snapshots. For example, existing graph convolutional networks (GCNs)-based DHAN embedding approaches embed the HAN snapshots to get static representations offline, and then dynamically capture temporal dependencies between adjacent snapshots online to maintain fresh representations of the DHAN. However, those approaches encounter the convergence problem when stacking multiple convolutional layers to capture more topological information. Some other existing approaches dynamically update the representations of HAN snapshots online, neglecting the efficiency requirement of online scenarios and the temporal dependencies between snapshots. To address the two issues, we propose a new framework called Dynamic Heterogeneous Attributed Network Embedding (DHANE), consisting of a static model MGAT and a dynamic model NICE. MGAT captures more topological information while maintaining GCN convergence by performing metagraph-based attention in each convolutional layer. NICE preserves network freshness while reducing the computational load of the update by only examining network changes and updating their embedding representations. Extensive experiments show that DHANE achieves up to 27× speedup and 9.1-26.4% higher accuracy on several real dynamic heterogeneous attributed networks for online classification.

This paper presents an efficient and scalable framework for Range Filtered Approximate Nearest Neighbors Search (RF-ANNS) over high-dimensional vectors associated with attribute values. Given a query vector q and a range [ l, h ], RF-ANNS aims to find the approximate k nearest neighbors of q among data whose attribute values fall within [ l, h ]. Existing methods including pre-, post-, and hybrid filtering strategies that perform attribute range filtering before, after, or during the ANNS process, all suffer from significant performance degradation when query ranges shift. Though building dedicated indexes for each strategy and selecting the best one based on the query range can address this problem, it leads to index consistency and maintenance issues. Our framework, called UNIFY, constructs a unified Proximity Graph-based (PG-based) index that seamlessly supports all three strategies. In UNIFY, we introduce SIG, a novel S egmented I nclusive G raph, which segments the dataset by attribute values. It ensures the PG of objects from any segment combinations is a sub-graph of SIG, thereby enabling efficient hybrid filtering by reconstructing and searching a PG from relevant segments. Moreover, we present H ierarchical S egmented I nclusive G raph (HSIG), a variant of SIG which incorporates a hierarchical structure inspired by HNSW to achieve logarithmic hybrid filtering complexity. We also implement pre- and post-filtering for HSIG by fusing skip list connections and compressed HNSW edges into the hierarchical graph. Experimental results show that UNIFY delivers state-of-the-art RF-ANNS performance across small, mid, and large query ranges.

Knowledge graphs (KGs) play a vital role in enhancing search results and recommendation systems. With the rapid increase in the size of KGs, they are becoming inaccurate and incomplete. This problem can be solved by the KG completion methods, of which graph attention network (GAT)-based methods stand out because of their superior performance. However, existing GAT-based KG completion methods often suffer from overfitting issues when dealing with heterogeneous KGs, primarily due to the unbalanced number of samples. Additionally, these methods demonstrate poor performance in predicting the tail (head) entity that shares the same relation and head (tail) entity with others. To solve these problems, we propose GATH, a novel GAT -based method designed for H eterogeneous KGs. GATH incorporates two separate attention network modules that work synergistically to predict the missing entities. We also introduce novel encoding and feature transformation approaches, enabling the robust performance of GATH in scenarios with imbalanced samples. Comprehensive experiments are conducted to evaluate GATH’s performance. Compared with the existing state-of-the-art GAT-based model on Hits@10 and MRR metrics, our model improves performance by 5.2% and 5.2% on the FB15K-237 dataset and by 4.5% and 14.6% on the WN18RR dataset, respectively.