Overlapping community detection (OCD) is a fundamental graph data analysis task for extracting graph patterns. Traditional OCD methods can be broadly divided into node clustering and link clustering approaches, both of which rely solely on link information to identify overlapping communities. In recent years, deep learning-based methods have made significant advancements for this task. However, existing GNN-based approaches often face difficulties in effectively integrating link, attribute, and prior information, along with challenges like limited receptive fields and over-smoothing, which hinder their performance on complex overlapping community detection. In this paper, we propose a Weak-clique based Overlapping Community Detection method, namely WOCD, which incorporates prior information and optimizes the use of link information to improve detection accuracy. Specifically, we introduce pseudo-labels within a semi-supervised framework to strengthen the generalization ability, making WOCD more versatile. Furthermore, we initialize pseudo-labels using weak cliques to fully leverage link and prior information, leading to better detection accuracy. Additionally, we employ a single-layer Graph Transformer combined with GNN, which achieves significant performance improvements while maintaining efficiency. We evaluate WOCD on eight real-world attributed datasets, and the results demonstrate that it outperforms the state-of-the-art semi-supervised OCD method by a significant margin in terms of accuracy.

In dynamic graph analysis, research has predominantly focused on temporal link prediction (TLP) for unweighted links, with growing interest in predicting temporal link weights in recent years. Temporal weighted link prediction (TWLP) aims to estimate both the existence and the link weights, which is naturally formulated as a regression task. The long-tail distribution and short-term randomness of link weights pose significant challenges for TWLP. In this paper, we introduce SALT, a Structure-Aware Link modeling for Temporal weighted link prediction, which consists of Weighted Link Encoder (WLE) and Temporal Link State Space Module (TLSSM). WLE encodes each snapshot into link-centric embeddings with common neighbor information, and addresses the long-tail issue by leveraging weights to adjust the embedding distribution. Additionally, TLSSM is designed to handle short-term randomness in temporal modeling. On eight datasets, our model achieves average reductions of 19.86% in RMSE and 24.61% in MAE compared to state-of-the-art baselines.

As artificial intelligence technology continues to advance, artificial intelligence-generated content (AIGC) has begun to evolve towards generating complex and structured data, particularly graph data. As an important topic in many fields such as database, data mining, and machine learning, graph generation holds significant value for simulating complex relationships between entities and has shown vast potential for applications in fields such as molecular generation, drug design, and material discovery. In this context, AIGC technology for graph generation has received widespread attention. This tutorial outlines the latest developments in AIGC for graph generation. We categorize existing methods into two main types according to their objectives and motivations: similarity-based generation and function-driven generation. We first provide an overview of AIGC models for graph generation. Then, we conduct a thorough review of the existing works. Finally, we explore the current trends and future directions, discussing potential ways to integrate database and machine learning techniques for graph generation.

Trajectory similarity computation is critical to various spatial data-related applications. To date, many deep learning-based approaches have been proposed to approximate trajectory similarity. However, most of previous models focus on trajectories in Euclidean space, neglecting the information of road networks, which is an important prerequisite in many applications, such as traffic analytics, social recommendation. In this paper, we study the trajectory similarity learning over road networks. Different from previous task, trajectories over road networks contain richer and more complex information, e.g., the geographical and structure information of road networks. To this end, we propose SPGMT, a graph modeling based approach that leverages abundant structure and position information inherent in road networks for trajectory similarity learning. Particularly, our graph model learns informative node representations by simultaneously incorporating structure information of nodes from a local perspective and position information from a global perspective. This road network oriented module is the first proposal to learn from a broad context of graph topology. Afterwards, SPGMT designs a self-attention network and employs an LSTM to learn the sequential information from trajectories. We conduct experiments on real-life datasets to demonstrate the superiority of SPGMT in terms of effectiveness. Besides, additional study shows the flexibility and robustness of SPGMT.

Graph Edit Distance (GED) is a fundamental graph similarity metric widely used in various applications. However, computing GED is an NP-hard problem. Recent state-of-the-art hybrid GED solver has shown promising performance by formulating GED as a bipartite graph matching problem, then leveraging a generative diffusion model to predict node matching between two graphs, from which both the GED and its corresponding edit path can be extracted using a traditional algorithm. However, such methods typically rely heavily on ground-truth supervision, where the ground-truth node matchings are often costly to obtain in real-world scenarios. In this paper, we propose GEDRanker, a novel unsupervised GAN-based framework for GED computation. Specifically, GEDRanker consists of a matching-based GED solver and introduces an interpretable preference-aware discriminator. By leveraging preference signals over different node matchings derived from edit path lengths, the discriminator can guide the matching-based solver toward generating high-quality node matching without the need for ground-truth supervision. Extensive experiments on benchmark datasets demonstrate that our GEDRanker enables the matching-based GED solver to achieve near-optimal solution quality without any ground-truth supervision.

The k-clique structure in graphs has been investigated in various real-world applications, such as community detection in complex networks, functional module discovery in biological networks, and link spam detection in web graphs. Despite extensive research on k-clique enumeration, the large number of k-cliques in many graphs poses a challenge for practical application and computation. To address this, we explore the k-clique τ-cover problem, a generalization of the vertex cover problem. The problem aims to find a small set of vertices that can effectively represent all k-cliques in the graph. We prove the NP-hardness of finding the minimum k-clique cover. We propose a hierarchical solution that computes a small cover without enumerating k-cliques. Extensive experiments on real-world graphs verify the efficiency and effectiveness of our solution.

Abstract In the rapidly advancing field of graph-based applications, accurate graph similarity computing (GSC) has become increasingly important. However, due to the complexity of graph structures, this task remains a challenge because of the intricate calculations involved. To solve the limitations of existing works, this paper introduces the Interpretable Graph Fusion Model (), a novel framework designed to enhance the accuracy and efficiency of graph similarity computation. Specifically, our model can fully utilize graph structure information and comprehensively assess graph similarity at both fine-grained and coarse-grained levels, ultimately achieving more accurate predictions. Experimented extensively across four real-world datasets, demonstrates a significant improvement over existing SOTA methods to solve the GSC challenge. In numerous experimental tests, our model shows performance improvements in terms of MSE (Mean Squared Error), ranging from 4.66% to as much as 56.92% compared to the second-best method.

Subgraph counting is a fundamental problem in graph analytics with broad applications, yet remains computationally intractable due to its #P-hardness. To address this, numerous approximate solutions have been proposed, though they often suffer from limited efficiency and accuracy. In this paper, we introduce FlowSC, a novel approach that achieves both high accuracy and efficiency in subgraph counting. Our method starts with an enhanced candidate filtering algorithm, which significantly improves the pruning capability of bipartite graph-based techniques with minimal overhead. Building on this, we propose a bottom-up flow-learning model based on a new Graph Neural Network (GNN) architecture. By employing a carefully designed message-passing mechanism, the model explicitly controls the direction, range, and iterations of information flow, enabling a simulation of the candidate tree-based counting process. This mechanism is further empowered by a customized message aggregation technique, alongside a pretraining strategy that facilitates model training. Extensive experiments show that FlowSC can achieve up to 4 orders of magnitude improvement in accuracy and 3× improvement in efficiency over the baselines across datasets, while scaling to billion-edge graphs.

Machine learning techniques have been proposed to optimize the performance of graph databases in recent years. Due to the NP-hardness of graph database tasks and the complexity of graph data, traditional exact solutions usually encounter efficiency issues, while the performance of approximation solutions can be affected by issues like sampling failure and local optimality. Empowered by the inherent advantages of machine learning, the learning-based techniques show the generalization ability and better performance in many scenarios, including graph data management and graph query processing. Despite the efficiency and accuracy brought by machine learning techniques, machine learning for graph database models still face several critical challenges, including scalability and adaptability. In this tutorial, we first provide an in-depth survey of learning-based graph data management and query processing techniques published in recent database and data mining conferences to sketch the frontier of the research of Machine Learning for Graph Database. We also discuss the open challenges and provide future directions.

Along with the rapid technological and commercial innovation on e-commerce platforms, an increasing number of frauds cause great harm to these platforms. Many frauds are conducted by organized groups of fraudsters for higher efficiency and lower costs, also known as group-based frauds. Despite the high concealment and strong destructiveness of group-based fraud, no existing research can thoroughly exploit the information within the transaction networks of e-commerce platforms for group-based fraud detection. In this work, we analyze and summarize the characteristics of group-based frauds. Based on this, we propose a novel end-to-end semi-supervised Group-based Fraud Detection Network (GFDN) to support such fraud detection in real-world applications. In addition, we introduce a module namedTemporal Group Dynamics Analyzer(TGDA) that strengthens the ability to analyze temporal information on group fraudulent activity. Based on this, we built an enhanced model named TGFDN. Experimental results on large-scale e-commerce datasets from Taobao and Bitcoin trading datasets show our proposed model's superior effectiveness and efficiency for group-based fraud detection on bipartite graphs.

As the field of data science continues to evolve, bipartite graphs have emerged as a fundamental structure in numerous applications, drawing significant interest from both academic and industrial communities. Bipartite graphs are a specific type of graph consisting of two distinct sets of vertices, where connections only occur between vertices of different sets. Examples include e-commerce networks and biological networks. Analytics of bipartite graphs has become an important research topic in the era of big data. This tutorial aims to shed light on analysis methods for bipartite graphs, categorizing them into three areas: classical models, learning-based models, and application-driven models. We start by outlining the importance of bipartite graph analytics, and the unique challenges that need to be addressed. Then, we conduct a thorough review of existing works on bipartite graph analytics. We also compare and analyze the models and solutions in these works. Finally, we point out new research directions.

Supergraph search is a fundamental graph query processing problem. Supergraph search aims to find all data graphs contained in a given query graph based on the subgraph isomorphism. In other words, the goal is to determine if part of the query graph is the same as a smaller data graph. Existing algorithms construct the indices and adopt the filtering-and-verification framework, which is usually computationally expensive and can cause redundant computations. Recently, various learning-based methods have been proposed for a good trade-off between accuracy and efficiency for query processing tasks. However, to our knowledge, no learning-based method is proposed for the supergraph search task. In this paper, we propose the first learning-based method for similarity search on supergraph containment, named Neural Supergraph similarity Search (NSS). NSS first learns the representations for query and data graphs and then efficiently conducts the supergraph search on the representation space, the complexity of which is linear to the number of data graphs. The carefully designed Wasserstein discriminator and reconstruction network enable NSS to capture better the interrelation, structural and label information between and within the query and data graphs. Experiments demonstrate that the NSS is up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in query processing and is more accurate than the other learning-based solutions.

Finding the optimal Steiner Tree in graphs has been a critical combinatorial optimization challenge that finds widespread applications in network design. Despite its importance, finding the optimal Steiner Tree remains computationally expensive, especially for large graphs due to its NP-hard nature. Traditional approaches often suffer from high time complexity or poor approximation ratio. Machine learning approaches often leverage local graph structure information instead of global graph structure information, and often suffer from the generalization ability issues in practice. In this paper, we propose a novel reinforcement learning based framework to solve STP, in which we reformulate the classical Q-value computation to capture both global graph structure and deterministic information to search for the Steiner tree. Experiments on both synthetic and real-world datasets demonstrate that our framework exhibits better generalization ability compared to the existing machine learning methods, where our framework can be trained on the small graphs and generalize well to larger graphs and the graphs from different distributions.

Influence Maximization (IM) has promising applications in social network marketing and has been extensively researched over the past years. However, previous IM studies mainly focus on ordinary graphs rather than hypergraphs, where edges cannot accurately describe group interactions or relationships. To model group interactions, we investigate the IM problem on hypergraphs under the Susceptible–Infected spreading model with Contact Process dynamics (SICP) in this paper. In this paper, we proposed a probability distribution-based method, called Multi-hop Influence Estimation (MIE), which can accurately estimate the rank of influence expectation of nodes, to solve the IM problem on hypergraphs. Specifically, we compute the influence score for each node through a constrained Depth First Search (DFS) under a probability model, and then select seed node according to the influence score. In addition, by analysing the characteristics of the influence diffusion model, we find that the influence of a node is significantly related to its neighbourhood structure. Based on the observation, we propose a term named neighbourhood coefficient to describe the neighbourhood structure of a node. Further, an efficient and effective method, called Adaptive Neighbourhood Coefficient Algorithm (Adeff), is proposed to solve the IM problem on hypergraphs. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our proposed methods. Compared with the state-of-the-art approach, our proposed methods can achieve up to 450% improvement in terms of effectiveness.

Graph Attention Networks (GATs) and Graph Convolutional Neural Networks (GCNs) are two state-of-the-art architectures in Graph Neural Networks (GNNs). It is well known that both models suffer from performance degradation when more GNN layers are stacked, and many works have been devoted to address this problem. We notice that main research efforts in the line focus on the GCN models, and their techniques cannot well fit the GAT models due to the inherent difference between these two architectures. In GAT, the attention mechanism is limited as it ignores the overwhelming propagation from certain nodes as the number of layers increases. To sufficiently utilize the expressive power of GAT, we propose a new version of GAT named Layer-wise Self-adaptive GAT (LSGAT), which can effectively alleviate the oversmoothing issue in deep GAT and is strictly more expressive than GAT. We redesign the attention coefficients computation mechanism adaptively adjusted by layer depth, which considers both immediate neighboring and non-adjacent nodes from a global view. The experimental evaluation confirms that LSGAT consistently achieves better results on node classification tasks over relevant counterparts.

The interactions between structured entities play important roles in a wide range of applications such as chemistry, material science, biology, and medical science. Recently, graph-based methods have been exploited to effectively predict the interactions among structured entities. However, these methods usually only focus on structural information of the entities and are incapable of fully utilizing the interaction information between the entities. In this paper, we propose a Denoising Variational Graph of Graphs Auto-encoder (DVGGA) which follows the graph of graphs framework to capture both structural information in structured entities and interaction information among structured entities. With denoising criterion, DVGGA is able to capture the information from the useful structures of the local graph and address the overfitting issue caused by redundant substructures. Extensive experiments conducted on real-world datasets show that DVGGA outperforms the state-of-the-art structured entity interaction prediction methods.

Supergraph search is a fundamental graph query processing problem. Supergraph search aims to find all data graphs contained in a given query graph based on the subgraph isomorphism. Existing algorithms construct the indices and adopt thefiltering-and-verificationframework which is usually computationally expensive and can cause redundant computations. Recently, various learning-based methods have been proposed for a good trade-off between accuracy and efficiency for query processing tasks. However, to the best of our knowledge, there is no learning-based method proposed for the supergraph search task. In this paper, we propose the first learning-based method for similarity search on supergraph containment, named Neural Supergraph similarity Search (NSS).NSSfirst learns the representations for query and data graphs and then efficiently conducts the supergraph search on the representation space whose complexity is linear to the number of data graphs. The carefully designed Wasserstein discriminator and reconstruction network enableNSSto better capture the interrelation, structural and label information between and within the query and data graphs. Experiments demonstrate that theNSSis up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in terms of query processing and more accurate compared to the other learning-based solutions.

The requirement for appropriate ways to measure the similarity between data objects is a common but vital task in various domains, such as data mining, machine learning and so on. Driven by abundant real-world applications, many well-known similarity (distance) metrics are proposed to measure the pairwise similarity of data pairs, e.g., graph edit distance for graphs and dynamic time warping for time series. However, many similarity metrics suffer from the high time complexity. More specifically, most of the well-known similarity metrics often need quadratic time or even much more time to compute the ground truth similarity and some of them are proven to be NP-hard. With the development of deep learning techniques, there is an emerging research trend on the learning for similarity computation on various data types in the field of database (DB) and data mining, which is quite different with the metric learning studies in the machine learning (ML) literature. Specifically, the studies in the ML focus on the learning for semantic similarity in specific tasks, which is implicitly indicated by the training data, on the data in the feature space. While the studies in the DB literature usually consider the learning for well-defined similarity metrics (e.g., graph edit distance) on the data objects (e.g., graphs), such that it can benefit the similarity computation on data in terms of multiple aspects, such as computation time, metric quality and search heuristic, and the learned representation of data can also be naturally fed to downstream tasks. This survey paper provides a comprehensive review of similarity computation learning on several data types, including set, sequence and graph. Moreover, we first classify the learning-based approaches in terms of their learning target into three categories, i.e., similarity learning, cost matrix learning and search heuristic learning. Then we detail some representative approaches for each category on every data type, and analyze some key features that are utilized by these approaches. Finally, we discuss some challenges and future directions towards the learning for similarity learning on these data types.

Along with the rapid technological and commercial innovation on the e-commerce platforms, there are an increasing number of frauds that bring great harm to these platforms. Many frauds are conducted by organized groups of fraudsters for higher efficiency and lower costs, which are also known as group-based frauds. Despite the high concealment and strong destructiveness of group-based fraud, there is no existing research work that can thoroughly exploit the information within the transaction networks of e-commerce platforms for group-based fraud detection. In this work, we analyze and summarize the characteristics of group-based frauds, based on which we propose a novel end-to-end semi-supervised Group-based Fraud Detection Network (GFDN) to support such fraud detection in real-world applications. Experimental results on large-scale e-commerce datasets from Taobao and Bitcoin trading datasets show the superior effectiveness and efficiency of our proposed model for group-based fraud detection on bipartite graphs.

Abstract In recent years, how to prevent the widespread transmission of infectious diseases in communities has been a research hot spot. Tracing close contact with infected individuals is one of the most severe problems. In this work, we present a model called Follower Prediction Graph Network (FPGN) to identify high-risk visitors, which is known as follower prediction. The model is designed to identify visitors who may be infected with a disease by tracking their activities at the exact location of infected visitors. FPGN is inspired by the state-of-the-art temporal graph edge prediction algorithm TGN and draws on the shortcomings of existing algorithms. It utilizes graph structure information based on ( $$\alpha $$ α , $$\beta $$ β )-core, time interval statistics by using the statistics of timestamp information, and a GAT-based prediction module to achieve high accuracy in follower prediction. Extensive experiments are conducted on two real datasets, demonstrating the progress of FPGN. The experimental results show that FPGN can achieve the highest results compared with other SOTA baselines. Its AP scores are higher than 0.46, and its AUC scores are higher than 0.62.

Abstract Graphs have been widely adopted in various fields, where many graph models are developed. Most of previous research focuses on unipartite or homogeneous graph analysis. In this graphs, the relationships between the same type of entities are preserved in the graphs. Meanwhile, the bipartite graphs that model the complex relationships among different entities with vertices partitioned into two disjoint sets, are becoming increasing popular and ubiquitous in many real life applications. Though several graph classification methods on unipartite and homogenous graphs have been proposed by using kernel method, graph neural network, etc. However, these methods are unable to effectively capture the hidden information in bipartite graphs. In this paper, we propose the first bipartite graph-based capsule network, namely Bipartite Capsule Graph Neural Network (BCGNN), for the bipartite graph classification task. BCGNN exploits the capsule network and obtains information between the same type vertices in the bipartite graphs by constructing the one-mode projection. Extensive experiments are conducted on real-world datasets to demonstrate the effectiveness of our proposed method.

Subgraph matching is a fundamental problem in various fields that use graph structured data. Subgraph matching algorithms enumerate all isomorphic embeddings of a query graph$q$in a data graph G. An important branch of matching algorithms exploit the backtracking search approach which recursively extends intermediate results following a matching order of query vertices. It has been shown that the matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In recent years, many advanced techniques for query vertex ordering (i.e., matching order generation) have been proposed to reduce the unpromising intermediate results according to the preset heuristic rules. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms. Instead of using the fixed heuristics to generate the matching order, our model could capture and make full use of the graph information, and thus determine the query vertex order with the adaptive learning-based rule that could significantly reduces the number of redundant enumerations. With the help of the reinforcement learning framework, our model is able to consider the long-term benefits rather than only consider the local information at current ordering step. Extensive experiments on six real-life data graphs demonstrate that our proposed matching order generation technique could reduce up to two orders of magnitude of query processing time compared to the state-of-the-art algorithms.

Trajectory similarity computation is the cornerstone of many applications in the field of trajectory data analysis. To cope with the high time complexity of calculating exact similarity between trajectories, learning-based models have been developed for a good trade-off between the similarity computing time and the accuracy of the learned similarity. As each trajectory can be represented by a fixed-length vector regardless of the size of the trajectory, the similarity computation among the trajectories is highly time-efficient. Nevertheless, we observe that these learning-based models are designed based on recurrent neural networks (RNN), which cannot properly capture the correlations among the trajectories. Moreover, these learning-based models simply use the similarity scores of the pairs of trajectories in the training for a specific similarity metric, while a vital piece of information is neglected: the mappings of the points between two trajectories are readily available when the similarity score is calculated. These motivate us to design a new learning-based model, named TMN, based on attention networks, aiming to significantly improve the accuracy such that a better trade-off between the similarity computing time and the accuracy can be achieved. The proposed matching mechanism associates points across trajectories by computing attention weights of point pairs so that TMN learns to simulate similarity computation between the trajectory pair. Apart from taking interactions between trajectories into consideration, the sequential information of each individual trajectory is also considered, thereby making full use of spatial features of a pair of trajectories. We evaluate various approaches on real-life datasets under extensive trajectory distance metrics. Experimental results demonstrate that TMN outperforms state-of-the-art methods in terms of accuracy. Besides, ablation studies prove the effectiveness of our novel matching mechanism.

Subgraph counting is a fundamental graph analysis task which has been widely used in many applications. As the problem of subgraph counting is NP-complete and hence intractable, approximate solutions have been widely studied, which fail to work with large and complex query graphs. Alternatively, Machine Learning techniques have been recently applied for this problem, yet the existing ML approaches either only support very small data graphs or cannot make full use of the data graph information, which inherently limits their scalability, estimation accuracies and robustness.

Abstract As a fundamental data structure, graphs are ubiquitous in various applications. Among all types of graphs, signed bipartite graphs contain complex structures with positive and negative links as well as bipartite settings, on which conventional graph analysis algorithms are no longer applicable. Previous works mainly focus on unipartite signed graphs or unsigned bipartite graphs separately. Several models are proposed for applications on the signed bipartite graphs by utilizing the heuristic structural information. However, these methods have limited capability to fully capture the information hidden in such graphs. In this paper, we propose the first graph neural network on signed bipartite graphs, namely Polarity-based Graph Convolutional Network (PbGCN), for sign prediction task with the help of balance theory. We introduce the novel polarity attribute to signed bipartite graphs, based on which we construct one-mode projection graphs to allow the GNNs to aggregate information between the same type nodes. Extensive experiments on five datasets demonstrate the effectiveness of our proposed techniques.

Advances of the sensor and GPS techniques have motivated the proliferation of trajectory data in a wide spectrum of applications. Trajectory similarity computation is one of the most fundamental problems in trajectory analytics. Considering that the high complexity of similarity computation is usually a bottleneck for large-scale trajectory data analysis, there are many research efforts for reducing the complexity such as the approximate algorithms. However, most of them are proposed for only one or two specific similarity measures, and thus cannot support different similarity measures well. In this paper, we propose a deep learning based model, namely T3S, which embeds each trajectory (i.e., a sequence of points) into a vector (point) in a d-dimensional space, and hence can significantly accelerate the similarity computation between the trajectories. By applying recurrent and attention neural networks, T3S can capture various unique characteristics of the trajectories such as the ordering of the points, spatial and structural information. Furthermore, our learning based T3S can easily handle any trajectory similarity measures by adjusting its parameters through the training. Extensive experiments on two real-life datasets demonstrate the effectiveness and efficiency of T3S. T3S outperforms state-of-the-art deep learning based methods under four popular trajectories similarity measures.

Entity interaction prediction is essential in many important applications such as chemistry, biology, material science, and medical science. The problem becomes quite challenging when each entity is represented by a complex structure, namely structured entity, because two types of graphs are involved: local graphs for structured entities and a global graph to capture the interactions between structured entities. We observe that existing works on structured entity interaction prediction cannot properly exploit the unique graph of graphs model. In this paper, we propose a Graph of Graphs Neural Network, namely GoGNN, which extracts the features in both structured entity graphs and the entity interaction graph in a hierarchical way. We also propose the dual-attention mechanism that enables the model to preserve the neighbor importance in both levels of graphs. Extensive experiments on real-world datasets show that GoGNN outperforms the state-of-the-art methods on two representative structured entity interaction prediction tasks: chemical-chemical interaction prediction and drug-drug interaction prediction. Our code is available at Github.

Nearest Neighbor search has been well solved in low-dimensional space, but is challenging in high-dimensional space due to the curse of dimensionality. As a trade-off between efficiency and result accuracy, a variety of c-approximate nearest neighbor (c-ANN) algorithms have been proposed to return a c-approximate NN with confident at least δ. We observe that existing c-ANN search algorithms have some limitations on I/O efficiency when their indexes are resided on the external memory, which is critical for handling large scale high-dimensional data. In this paper, we introduce an incremental search based c-ANN search algorithm, named I-LSH. Unlike the previous LSH methods, which expand the bucket width in an exponential way, I-LSH adopts a more natural search strategy to incrementally access the hash values of the objects. We provide rigorous theoretical analysis to underpin our incremental search strategy. Our comprehensive experiment results show that, compared with state-of-the-art I/O efficient c-ANN techniques, our algorithm can achieve much better I/O efficiency under the same theoretical guarantee.