Source-linked AI summary
Capturing Topology in Graph Pattern Matching
Shuai Ma, Yang Cao, Wenfei Fan, Jinpeng Huai, Tianyu Wo
TL;DR
Graph pattern matching needs an approach that is less restrictive and computationally cheaper than subgraph isomorphism while avoiding the topology loss and oversized match relations of graph simulation. The paper proposes strong simulation, enforcing duality and locality, and shows that it preserves topology, retains cubic-time computation, supports distributed matching, and produces bounded matches. Experiments on real-life and synthetic data verify the effectiveness and efficiency of the algorithms, while bounded-cycle matching remains intractable and cubic time remains expensive for large graphs.
Problem
Subgraph isomorphism is NP-complete and may have exponentially many matches, while graph simulation extensions can miss topology and return overly large match relations.
Method
Strong simulation revises graph simulation by enforcing duality for parent relationships and locality for diameter-based match neighborhoods.
Results
Strong simulation preserves graph topology, retains cubic-time computation, supports distributed evaluation, and finds bounded matches; experiments verify algorithmic effectiveness and efficiency.
Takeaways & Limitations
Strong simulation offers a topology-aware graph pattern-matching model that avoids excessive matches while remaining tractable and applicable to distributed graphs.
Takeaways & Limitations
Imposing bounded cycles would make pattern matching intractable, and cubic time remains too expensive for large graphs.
Abstract
from arXiv · showhide
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.
1. Introduction
Graph pattern matching needs a tractable alternative to subgraph isomorphism that still preserves graph topology and produces understandable matches. The paper introduces strong simulation to address these problems while retaining cubic-time computation and supporting distributed evaluation.
- Motivation: Subgraph isomorphism is NP-complete, can yield exponentially many matching subgraphs, and may be too restrictive for sensible matches.These properties hinder its applicability in emerging applications such as social networks and crime detection.
- Motivation: Simulation and its extensions have low complexity but may match graphs with drastically different structures and produce match relations too large to analyze.On LinkedIn, simulation can yield a 100GB result graph.
- Approach: Strong simulation enforces duality and locality to preserve parent relationships and eliminate excessive matches.For the running example, only Bio4 matches Bio in the pattern.
- Properties: Strong simulation preserves pattern and data-graph topology, yields linearly many bounded-diameter matches, and retains cubic-time computation.Each match has diameter bounded by the pattern diameter.
- Algorithms: Strong simulation supports distributed graph matching through locality and includes a quadratic-time query-minimization algorithm alongside its cubic-time computation algorithm.The distributed algorithm is motivated by the need to process massive graphs.
2. Strong Simulation
Strong simulation augments graph simulation with duality and locality. These conditions preserve relevant parent-child structure, confine matches to diameter-based neighborhoods, and retain tractable matching with focused match results.
- Definition: Strong simulation is defined by enforcing duality and locality on graph simulation.The conditions are intended to capture graph topology and eliminate excessive matches while retaining low polynomial-time complexity.
- Duality: Duality preserves both child and parent relationships between pattern and data graphs.It extends simulation, which preserves labels and child relationships.
- Properties: A unique maximum match relation exists for dual simulation, and a unique set of maximum perfect subgraphs exists for strong simulation.Strong simulation can also be extended with hop bounds and regular-expression edge constraints.
- Locality: Locality requires matches to lie within a ball whose radius is determined by the pattern diameter.The ball contains the nodes and edges needed to match the pattern, excluding distant irrelevant structures.
- Examples: For the running example, strong simulation maps Bio only to Bio4 and excludes an irrelevant long cycle from the match.The relevant match is contained in the ball centered at Bio4 with radius 3, the diameter of the pattern.
- Examples: Strong simulation returns focused matches in examples involving recommendations, mutual recommendations, and citation chains.It selects book2, P1-P3, and SN1-SN2, respectively, while avoiding the excessive matches returned by simulation.
3. Properties of Strong Simulation
The paper evaluates strong simulation against topology-preservation and bounded-match criteria, showing that it captures key structures while remaining tractable. It also identifies intractable extensions and contrasts the relative strength of matching notions.
- Comparative properties: Matching notions are ordered by strength as subgraph isomorphism, strong simulation, dual simulation, and graph simulation, with stronger notions preserving more topology.
- Topology preservation: Strong simulation preserves parent relationships and connectivity, unlike graph simulation in cases where connected patterns can match disconnected data.
- Topology preservation: Strong simulation preserves directed and undirected cycles, whereas graph simulation can map an undirected pattern cycle to a tree.
- Locality and bounded matches: Strong simulation has locality: each matched subgraph has diameter bounded by 2*dQ, enabling matching by inspecting bounded neighborhoods.
- Locality and bounded matches: The number of maximum perfect subgraphs under strong simulation is bounded by the number of nodes in the data graph, rather than being exponential as with subgraph isomorphism.
- Tractable boundary: Adding bounded-cycle constraints makes matching intractable, with the bounded cycle problem coNP-hard even when patterns contain a single cycle.
4. An Algorithm for Strong Simulation
The paper gives a cubic-time strong-simulation algorithm that examines local balls, then develops quadratic-time query minimization and filtering optimizations. Strong simulation also supports distributed evaluation through data locality.
- 4.1 A Cubic-time Algorithm: Theorem 5 establishes cubic-time computation for checking strong simulation and finding maximum perfect subgraphs.The Match complexity analysis gives O(|V|(|V|+(|Vq|+|Eq|)(|V|+|E|))) time.
- 4.2 Optimization Techniques: Theorem 6 gives a quadratic-time method to find a minimum pattern equivalent under strong simulation when balls use radius dQ.The minimization algorithm runs in O((|Vq|+|Eq|)^2) time.
- 4.1 A Cubic-time Algorithm: Strong simulation is computed by inspecting radius-dQ balls around each data-graph node and extracting maximum perfect subgraphs.Match invokes DualSim on each ball, then ExtractMaxPG returns the connected component containing the center when a match exists.
- 4.1 A Cubic-time Algorithm: The Match algorithm returns the set Θ of maximum perfect subgraphs after processing every radius-dQ ball in the data graph.For each ball, it computes Sw, extracts Gs, and adds nonempty results to Θ.
- 4.1 A Cubic-time Algorithm: DualSim iteratively removes candidate matches lacking corresponding outgoing or incoming edges, returning the maximum match relation Sw.Candidates are initialized by label equality and pruned until no changes remain or a pattern node has no matches.
- 4.2 Optimization Techniques: Algorithm minQ constructs a minimum equivalent pattern by computing dual simulation on Q itself, grouping equivalent nodes, and retaining necessary edges.Its output preserves the same results on every data graph, and the minimum equivalent pattern is unique up to isomorphism.
- 4.2 Optimization Techniques: Filtering and connectivity pruning reduce unnecessary processing by starting from border nodes and affected matches within each ball.The filtering method can leave only two balls to process in the illustrated example, while optimization techniques reduce average running time by 1/3.
- 4.3 Strong Simulation on Distributed Graphs: Strong simulation has data locality, bounding distributed data shipment to balls centered at nodes with direct neighbors outside their local partitions.This contrasts with graph simulation, whose distributed evaluation may require shipping all fragmented subgraphs to one site.
5. Experimental Study
Experiments on real-life and synthetic graphs show that strong simulation identifies sensible matches, preserves topology, limits match sizes, and scales efficiently, while optimization further reduces runtime.
- Match quality: Strong simulation identifies sensible matches missed by subgraph isomorphism and filters graph-simulation matches that do not make sense.In the tested examples, Match found a sensible Amazon match missed by VF2 and removed an excessive Sim match.
- Match quality: Match achieves 70%-80% closeness to VF2, outperforming Sim by up to 50%, TALE by up to 36%, and MCS by up to 23%.The additional 20%-30% of Match results not found by VF2 also contain sensible matches.
- Match size: All Match subgraphs have fewer than 50 nodes, and over 80% have fewer than 30 nodes on real-life and synthetic data.Sim instead returns single matched subgraphs with 103, 177, and 311 nodes on Amazon, YouTube, and synthetic data, respectively.
- Efficiency: Match and related algorithms scale well with graph size and density, whereas VF2 scales substantially worse and may fail to complete on large data graphs.Match and Match+ are slower than Sim, reflecting a runtime trade-off for better match quality.
- Efficiency: Optimization reduces Match+ runtime to consistently about two-thirds of Match runtime, while the overall experiments report at least a 33% reduction.The study used real-life Amazon and YouTube networks, synthetic graphs, and repeated tests on a 30-machine cluster.
6. Conclusion
The paper concludes that strong simulation captures graph topology while retaining cubic-time complexity and supporting locality for distributed evaluation. Future work targets richer edge constraints, stronger distributed algorithms, match ranking, and scalability beyond cubic time.
- Contributions: Strong simulation captures the topological structures of pattern and data graphs while retaining the cubic-time complexity of earlier graph-simulation extensions.The paper also reports that strong simulation demonstrates data locality for distributed evaluation.
- Future work: Future work includes regular expressions on edge types, better-performing distributed algorithms, ranking matches, and indexing or incremental methods for large graphs.The authors state that cubic time remains too expensive for large graphs.