Strong simulation: capturing topology in graph pattern matching

DOI10.1145/2528937MaRDI QIDQ2943564zbMATH OpenOpenAlexWikidataFDO

Authors Shuai Ma, Yang Cao, Wenfei Fan, Tianyu Wo, Jin-Peng Huai

Publication date 3 September 2015

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.0229

zbMATH Keywords

subgraph isomorphismdata localitystrong simulationgraph simulationdual simulation

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distributed algorithms (68W15)

Abstract: Graph pattern matching is often defined in terms of subgraph isomorphism, an NP-complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow pattern matching to be conducted in cubic-time. However, they fall short of capturing the topology of data graphs, i.e., graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this paper proposes a notion of strong simulation, a revision of graph simulation, for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of simulation, by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation, which allows us to effectively conduct pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using real-life data and synthetic data.

Recommendations

• Parallel algorithms for flexible pattern matching on big graphs
• Incremental graph pattern matching
• Simulation relations for pattern matching in directed graphs
• Directed Graph Pattern Matching and Topological Embedding
• SQL-based solution for fast graph similarity search

Cites work

• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Adding regular expressions to graph reachability and pattern queries
• An Algorithm for Subgraph Isomorphism
• Answering queries using views: A survey
• Distributed XML processing: theory and applications
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Incremental graph pattern matching
• Introduction to algorithms
• Managing and mining graph data
• Simulation-based minimization
• Strong simulation: capturing topology in graph pattern matching
• The syntenic diameter of the space of \(N\)-chromosome genomes

Cited in

(6)

• Size-fixed group discovery via multi-constrained graph pattern matching
• Linking entities across relations and graphs
• Simulation relations for pattern matching in directed graphs
• Strong simulation: capturing topology in graph pattern matching
• Rough approximations based on bisimulations
• Distributed graph pattern matching via bounded dual simulation

Describes a project that uses

Uses Software

• MapReduce
• igraph
• Gplag
• GraphLab
• Pregel
• TALE
• NeMa

This page was built for publication: Strong simulation: capturing topology in graph pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943564)