In order to support the real-time interaction with LLMs and the instant search or the instant recommendation on social media, it becomes an imminent problem to build a k-NN graph or an indexing graph for the massive number of vectorized multimedia data. In such scenarios, the scale of the data or the scale of the graph may exceed the processing capacity of a single machine. This paper aims to address the graph construction problem of such scale via efficient graph merge. For the graph construction on a single node, two generic and highly parallelizable algorithms, namely Two-way Merge and Multi-way Merge are proposed to merge subgraphs into one. For the graph construction across multiple nodes, a multi-node procedure based on Two-way Merge is presented. The procedure makes it feasible to construct a large-scale k-NN graph/indexing graph on either a single node or multiple nodes when the data size exceeds the memory capacity of one node. Extensive experiments are conducted on both large-scale k-NN graph and indexing graph construction. For the k-NN graph construction, the large-scale and high-quality k-NN graphs are constructed by graph merge in parallel. Typically, a billion-scale k-NN graph can be built in approximately 17h when only three nodes are employed. For the indexing graph construction, similar NN search performance as the original indexing graph is achieved with the merged indexing graphs while requiring much less time of construction.

In this paper, we study two different problems that investigate relations between given vertices$s$and$t$. The first problem is to generate the$k$-hop-constrained$s$-$t$path graph, i.e., the subgraph consisting of all paths from$s$to$t$, where each path is not longer than$k$s.t.$s$and$t$appear only once. To solve the first problem, we propose theA-BiBFS$^{++}$t++method enhanced with the reduced neighbor index and an approximate vertex grouping strategy. The second problem is to generate the$k$-hop-constrained$s$-$t$simple path graph, i.e., the subgraph consisting of all$k$-hop-constrained simple paths from$s$to$t$, which is proved to be NP-hard on directed graphs. Based onA-BiBFS$^{++}$t++, we propose theEVEmethod to tackle the second problem, which exploits the paradigm of edge-wise examination rather than exhaustively enumerating all simple paths. Extensive experiments show that bothA-BiBFS$^{++}$s++andEVEsignificantly outperform all baselines. Moreover, by takingEVEas a built-in block, state-of-the-art for hop-constrained simple path enumeration can be accelerated by up to an order of magnitude.

This paper explores parallel computing systems for efficient subgraph query processing in large graphs. We investigate how to take advantage of the inherent parallelism of parallel computing systems for both intraquery and interquery optimization during subgraph query processing. Rather than relying on widely-used hash-based methods, we utilize and extend locality sensitive hashing methods. For intraquery optimization, we use the structures of both the data graph and subgraph query to design a query-constraint locality sensitive hashing method named QCMH, which can be used to merge multiple tasks during a single subgraph query processing. For interquery optimization, we propose a query locality sensitive hashing method named QMH, which can be used to detect common subgraphs among different subgraph queries, thereby merging multiple subgraph queries. Our proposed methods can reduce the redundant computation among multiple tasks duringa single subgraph query processing or multiple queries. Extensive experimental studies on large real and synthetic graphs show that our proposed methods can improve query performance compared to state-of-the-art methods by 10% to 50%.

Existing Graph Neural Network (GNN) training frameworks have been designed to help developers easily create performant GNN implementations. However, most existing GNN frameworks assume that the input graphs are static, but ignore that most real-world graphs are constantly evolving. Though many dynamic GNN models have emerged to learn from evolving graphs, the training process of these dynamic GNNs is dramatically different from traditional GNNs in that it captures both the spatial and temporal dependencies of graph updates. This poses new challenges for designing dynamic GNN training frameworks. First, the traditional batched training method fails to capture real-time structural evolution information. Second, the time-dependent nature makes parallel training hard to design. Third, it lacks system supports for users to efficiently implement dynamic GNNs. In this paper, we present NeutronStream, a framework for training dynamic GNN models. NeutronStream abstracts the input dynamic graph into a chronologically updated stream of events and processes the stream with an optimized sliding window to incrementally capture the spatial-temporal dependencies of events. Furthermore, NeutronStream provides a parallel execution engine to tackle the sequential event processing challenge to achieve high performance. NeutronStream also integrates a built-in graph storage structure that supports dynamic updates and provides a set of easy-to-use APIs that allow users to express their dynamic GNNs. Our experimental results demonstrate that, compared to state-of-the-art dynamic GNN implementations, NeutronStream achieves speedups ranging from 1.48X to 5.87X and an average accuracy improvement of 3.97%.

With the rapid growth of graph scale, challenges emerge for subgraph search when the data graph cannot reside in the memory of a single machine. It is important to develop practical algorithms to answer subgraph queries in distributed systems and has attracted extensive attention in recent years. The existing join-based algorithms are natively supported in many distributed engines, but they often suffer from a large number of invalid intermediate results and duplicate computation. The exploration-based algorithms minimize invalid intermediate results, while they are likely to produce results of exponential size. In this paper, we propose an efficient hybrid subgraph matching framework that integrates the advantages of both join-based and exploration-based paradigms. We formulate a novel decomposition for the query graph, namely sketch tree, which can reduce invalid intermediate results and avoid duplicate computation. We implement the proposed algorithm in the Pregel + system and optimize the communication cost powered by the sketch tree. Extensive experiments on real graphs demonstrate that our proposed algorithm significantly outperforms the state-of-the-art join-based and exploration-based methods.