Source-linked AI summary
Efficient Subgraph Matching on Billion Node Graphs
Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, Jianzhong Li
TL;DR
The paper addresses subgraph matching when billion-node graphs cannot rely on super-linear indices or fit in one machine. It uses distributed in-memory graph exploration, query partitioning, selective joins, and parallel processing, reporting one- or two-second matching and scale-out to larger graphs.
Problem
Subgraph matching on billion-node graphs is difficult because super-linear indices are infeasible and web-scale graphs may not fit in a single machine.
Method
The method uses distributed in-memory graph exploration without graph-structure indices, partitions queries, limits joins to unavoidable cycles, and parallelizes processing.
Results
Subgraph matching on billion-node graphs can be completed within one or two seconds, with sub-linear scaling and scale-out through additional Trinity slaves.
Takeaways & Limitations
The approach demonstrates feasible online subgraph matching for web-scale graphs using lightweight indexing and distributed computation.
Takeaways & Limitations
Decomposing queries into small STwigs can generate many intermediary results and joins, while naive graph exploration can sometimes exceed join cost.
Abstract
from arXiv · showhide
The ability to handle large scale graph data is crucial to an increasing number of applications. Much work has been dedicated to supporting basic graph operations such as subgraph matching, reachability, regular expression matching, etc. In many cases, graph indices are employed to speed up query processing. Typically, most indices require either super-linear indexing time or super-linear indexing space. Unfortunately, for very large graphs, super-linear approaches are almost always infeasible. In this paper, we study the problem of subgraph matching on billion-node graphs. We present a novel algorithm that supports efficient subgraph matching for graphs deployed on a distributed memory store. Instead of relying on super-linear indices, we use efficient graph exploration and massive parallel computing for query processing. Our experimental results demonstrate the feasibility of performing subgraph matching on web-scale graph data.
1. INTRODUCTION
The paper targets subgraph matching on billion-node graphs, where existing super-linear indices and single-machine assumptions are infeasible. It replaces expensive indexing and joins with lightweight indexing, graph exploration, query optimization, and parallel processing.
- Motivation: Billion-node graphs arise in applications including social networks, web search, and genome sequencing.The paper cites Facebook's 800 million vertices and a web graph projected at 1 trillion vertices.
- Challenge: Existing graph-query methods commonly require super-linear index space or construction time, making them unrealistic at billion-node scale.The R-Join example requires O(n^4) index construction time, where n can be 10^9.
- Problem: The paper studies retrieving all subgraphs of a data graph G that are isomorphic to a query graph Q.Subgraph matching supports applications such as protein-interaction networks, knowledge bases, and program analysis.
- Approach: STwig avoids graph-structure indices, using only a linear-size, linear-construction-time label-to-vertex-ID index.The approach combines graph exploration with parallel processing on a distributed memory cloud of commodity machines.
- Approach: Query graphs are partitioned into subqueries, joins are retained only when unavoidable, and optimization orders STwigs using label frequency and node degree.The method also uses pipeline join processing for large intermediary results and avoids duplicate results across machines.
2. BACKGROUND
This section defines labeled-graph subgraph matching and introduces Trinity, a distributed memory cloud used to store and explore graphs too large for one machine.
- Subgraph matching: Subgraph matching retrieves every subgraph of a data graph that is isomorphic to a query graph.The formal definition requires label-preserving vertex correspondence and query-edge preservation.
- The Trinity memory cloud: Very large graphs cannot usually fit in one machine’s RAM, although random graph exploration benefits from memory storage.
- The Trinity memory cloud: Trinity combines the RAM of multiple machines into a unified address space and hides storage partitioning and message passing through APIs.
- The Trinity memory cloud: A 15-machine Trinity cluster explored an 800-million-node, 100-billion-edge graph’s 3-hop neighborhoods in under 100 milliseconds on average.The tested graph had Facebook-like size and an average degree of 130.
3. EXPLORATION VS. JOINS
The section contrasts join-based and exploration-based subgraph matching, motivating a hybrid method that uses exploration to avoid unnecessary join candidates without structural indexes.
- Exploration versus joins: Graph exploration can avoid structural indexes, reduce intermediary results, and require almost no join operations.
- Using join operations: Join-based matching decomposes queries, evaluates parts independently, and joins their results, but can generate many useless intermediary results.
- Using graph exploration: Exploration follows matching paths directly from identified nodes, obtaining results without generating and joining large intermediary sets.
- Using graph exploration: Naive exploration can be more expensive than joins, still require joins for some patterns, or perform poorly on dense path combinations.
- Hybrid approach: The proposed method uses joins as the query-plan skeleton and exploration to eliminate useless candidates during joining.
4. FRAMEWORK OF OUR APPROACH
The framework decomposes subgraph queries into two-level STwigs, matches them through memory-cloud graph access, and combines ordered exploration with joining while recognizing the cost of excessive intermediate results.
- Framework: The framework avoids indexing graph structure and decomposes each subgraph query into basic units called STwigs.
- Distributed execution: The framework processes STwigs through graph exploration and joining in a distributed parallel environment based on the Trinity memory cloud.
- STwig: An STwig is a two-level tree with a labeled root and a set of labeled child nodes.
- STwig matching: MatchSTwig finds root nodes by label, loads their neighbors, filters child nodes by label, and returns matching STwigs.
- Framework trade-off: Independently matching small STwigs can produce many results and make the final joins extremely costly.
1. Query Decomposition and STwig Ordering
The query is decomposed into STwigs and explored in a chosen linear order, with both choices affecting query-processing cost.
- Query Decomposition: Queries are decomposed into a set of STwigs, with multiple decompositions possible.The paper illustrates alternative decompositions and notes that one shown contains only three STwigs.
- Query Decomposition: Different STwig decompositions incur different query-processing costs.
- STwig Ordering: Rather than matching each STwig independently and joining results, the algorithm uses graph exploration.
- STwig Ordering: The STwigs are assigned a linear exploration order, q1, q2, · · · qk.
- STwig Ordering: The selected STwig ordering affects query-processing cost, motivating separate ordering strategies.
2. Exploration
The exploration phase processes an ordered sequence of STwigs, using previously found bindings to restrict later searches until all query nodes are bound.
- When a root is unbound, the system retrieves nodes with its label and restricts their child nodes using bindings from earlier STwigs.For q2, Index.getID(d) finds candidate roots, while Hb and Hc constrain eligible children.
- When an STwig root is already bound, exploration reuses those bound nodes instead of looking up all nodes with the root label.For q3, nodes in Hb serve as roots, after which child nodes labeled e and f are explored.
- Each STwig is processed in a predefined order, producing intermediary results G(q1), G(q2), ···, G(qk) until every query node is bound.Binding information identifies eligible data-graph nodes for subsequent STwigs but does not itself constitute complete answers.
3. Join
The join phase combines filtered STwig results across machines, optimizing join order and pipelining to limit intermediate-result size and communication.
- Join order is selected after all STwig results are generated because predetermined ordering can create unnecessarily large intermediate results.The system uses sample-based cost estimation and cost-based join-order selection.
- Block-based pipelined join divides the multi-way join into rounds so partial results are produced before the entire join completes.This addresses large intermediate results in the system’s memory-based setting.
- The distributed graph is randomly partitioned across machines, with local string indices mapping labels to local node IDs.Exploration is parallelized per machine, although checking labels of remote child nodes may incur network communication.
- Each machine joins locally generated STwig results with results fetched from other machines, then unions the distributed outputs into the final answer.The remote machines accessed for STwig qi are specified by its load set Fk,i.
- Load sets should keep final machine results disjoint and remain small to reduce duplicate handling and network communication.The head STwig uses an empty load set, while other load sets exclude machine pairs whose matches cannot join.
5. QUERY OPTIMIZATION
The optimization framework jointly decomposes queries, orders STwigs, and selects head and load sets. It uses selectivity-aware rules with provable approximation and communication properties.
- 5.1 Query Decomposition: Query decomposition seeks a minimum STwig cover because each additional STwig increases the number of joins and potential communication costs.The minimum STwig cover problem is polynomially equivalent to minimum vertex cover and therefore NP-hard.
- 5.2 STwig Order Selection: The revised decomposition selects connected edges and favors high-selectivity nodes, making later STwig roots more likely to be bound by prior results.Except for the first STwig, each generated root is a leaf of at least one previously processed STwig.
- 5.2 STwig Order Selection: The ranking function f(v)=deg(v) freq(v.label) favors nodes with more query neighbors and less frequent data-graph labels.Higher f-values guide edge selection and STwig ordering.
- 5.2 STwig Order Selection: Algorithm 2 runs in O(n2 log n) time for a query with n nodes.The bound includes computing and sorting f-values plus repeated edge-selection rounds.
- 5.2 STwig Order Selection: Algorithm 2 is a 2-approximate algorithm: its STwig cover contains at most twice as many STwigs as an optimal cover.The proof compares selected disjoint edges with the optimal cover and generates at most two STwigs per selected edge.
- 5.3 Head STwig and Load Set Selection: For distributed matching, the cluster graph bounds which machines can contribute compatible STwig matches, enabling load-set selection.Theorem 3 states DC(i,j) ≤ Dq(u,v), while Theorem 4 restricts machine k’s needed results to Fk,t.
6. EXPERIMENTAL EVALUATION
Experiments evaluate the approach on real and synthetic graphs, examining query size, density, graph size, label density, and parallel speed-up. The results report low response times, sub-linear scaling, and effective scale-out.
- Experiment setup: Experiments use real and synthetic data across two clusters, with queries generated by DFS traversal or random edge addition.The default synthetic query parameters are N=10 nodes and E=20 edges.
- Real-data query experiments: DFS query time rises significantly beyond seven nodes, while larger queries can reduce intermediate results under the exploration strategy.More STwigs and joins increase processing, but smaller intermediate results can reduce overall cost.
- Real-data query experiments: Random-query time is nearly linear in query-node count because larger queries add join operations while most STwig and join costs remain similar.The tested node count varies from 5 to 15, with edge count set to 2N.
- Real-data query experiments: 10 to 20 query edges have no significant impact on random-query time because the partition strategy keeps average STwig counts nearly unchanged.The resulting STwig and join counts remain close across the tested edge densities.
- Synthetic-data scalability: 400ms to 1800ms response times are observed as graph size grows from 1 million to 4 billion nodes at fixed average degree 16.The experiment reports no clear proportional relationship between response time and graph size.
- Synthetic-data scalability: Subgraph matching on billion-node graphs can be completed within one or two seconds, with sub-linear scaling in graph size and density and scale-out through additional Trinity slaves.Graphs reaching 1B nodes can also be loaded within a few hundred seconds.
7. RELATED WORK
Related work covers search-pruning, indexing, and parallel or distributed graph-processing approaches. The paper emphasizes that existing techniques face scalability or processing-model constraints for single large graphs.
- Scope: Subgraph matching research distinguishes queries over many small graphs from queries over one large graph, with this paper studying the latter.The single-large-graph setting is identified as more challenging because of graph size.
- Graph pattern matching: Search-pruning methods accelerate matching through pruning, but global pruning requires graph-wide information and is unsuitable for parallel processing on large graphs.The cited discussion also describes local pruning as an alternative used by some prior work.
- Graph pattern matching: Index-based methods use structures such as 2-hop labels, distance records, or neighborhood signatures, but their size and maintenance cost hinder scalability.The passage states that some index sizes exceed square complexity in the number of vertices.
- Parallel and distributed processing: Many distributed graph algorithms assume shared memory or favor adjacency-matrix processing, whereas subgraph matching is difficult to process on an adjacent matrix and real-world graphs are often sparse.The related-work discussion contrasts algorithmic parallelism with big-data settings.
8. CONCLUSIONS
The paper addresses billion-node subgraph matching without structural indices by combining subgraph joins, graph exploration, query optimization, parallelism, and pipeline joins. Experiments demonstrate scalability to billion-node graphs, while larger-scale validation remains future work.
- Conclusions: The approach avoids structural indices by combining subgraph join with graph exploration for billion-node subgraph matching.This targets prior methods requiring super-linear index size or construction time.
- Conclusions: Query optimization, parallel processing, and pipeline joins are used to improve processing and handle large intermediate results.The conclusion presents these as components of the proposed method.
- Conclusions: Experiments demonstrate that the method can scale to billion-node graphs.The authors identify trillion-scale experiments and larger-cluster transmission measurements as future work.