Efficient Subgraph Matching on Billion Node Graphs

By Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, Jianzhong Li. Proceedings of the VLDB Endowment, 2012

425 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/9447b4502eed007a117e4ba87278407ca3d7b354

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

POIROT: Aligning Attack Behavior with Kernel Audit Records for Cyber Threat Hunting (2019, methodology): “Prior works have incorporated novel optimization techniques, graph indexing, and query processing methods [19, 62, 71] to support timely attack investigations.”
Large Language Models on Graphs: A Comprehensive Survey (2023, background): “These graph reasoning tasks include inferring connectivity [6], shortest path [7], subgraph matching [8], and logical rule induction [18].”
Efficient Subgraph Matching by Postponing Cartesian Products (2016, background): “While the above techniques are based on the depth-first paradigm that is shown as the most efficient strategy to conduct subgraph matching on a single computer, the problem of subgraph matching has also been investigated in a distributed environment [11, 16, 18], where the join paradigm has been dem”
FENNEL: streaming graph partitioning for massive scale graphs (2014, background): “It is also worth noting a separate line of work whose goal is to optimize small dynamic graph queries [34, 50, 55].”
A Distributed Graph Engine for Web Scale RDF Data (2013, methodology): “We conduct comprehensive experimental studies on real life, web scale RDF data to demonstrate the effectiveness of our approach.”
Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network (2018, background): “There also exist efficient algorithms to mine frequent subgraph patterns and match subgraph instances [9, 31].”
Trinity: a distributed graph engine on a memory cloud (2013, methodology): “Here, the size of the graph ranges from 1 million to 128 million nodes, average node degree is 16, average query size is 10 (nodes), and queries are generated using two random methods, DFS and RANDOM [32].”
Similarity Search in Graph Databases: A Multi-Layered Indexing Approach (2017, background): “Graph similarity search relies on some graph proximity function that models the similarity of graphs, and the most referenced one is graph edit distance (GED) due in particular to its generality and broad applicability [36], [37], [24], [27], [35], [32], [8], [7].”