PaperlayerView exact revision on arXiv

Source-linked AI summary

Peregrine: A Pattern-Aware Graph Mining System

Kasra Jamshidi, Rakesh Mahadasa, Keval Vora

arXiv:2004.02369v1cs.DCcs.DB

TL;DR

Graph-mining systems often ignore the patterns they mine, leading to costly exploration and difficult expression of complex tasks. PEREGRINE uses patterns to guide mining, and the authors report substantial performance gains and billion-scale capability on one machine.

  • Problem

    Existing graph-mining systems are largely pattern-unaware, which limits efficient exploration and makes complex mining tasks difficult to express.

    Source: §1 · p. 2, §2.2.2 · p. 4

  • Method

    PEREGRINE treats graph patterns as first-class constructs and analyzes their structure to guide exploration toward relevant subgraphs.

    Source: §1 · p. 2

  • Results

    PEREGRINE outperforms state-of-the-art by several orders of magnitude with up to 8× fewer CPU cores, and handles billion-scale tasks on one machine where others fail on eight-machine clusters or large SSDs.

    Source: §8 · p. 15

  • Takeaways & Limitations

    Pattern-based programming lets users directly express complex mining use cases, including advanced structural constraints.

    Source: §8 · p. 15

    The evaluation excludes AutoMine because its source code was unavailable.

    Source: §6.1 · p. 10

Abstract

from arXiv · show

Graph mining workloads aim to extract structural properties of a graph by exploring its subgraph structures. General purpose graph mining systems provide a generic runtime to explore subgraph structures of interest with the help of user-defined functions that guide the overall exploration process. However, the state-of-the-art graph mining systems remain largely oblivious to the shape (or pattern) of the subgraphs that they mine. This causes them to: (a) explore unnecessary subgraphs; (b) perform expensive computations on the explored subgraphs; and, (c) hold intermediate partial subgraphs in memory; all of which affect their overall performance. Furthermore, their programming models are often tied to their underlying exploration strategies, which makes it difficult for domain users to express complex mining tasks. In this paper, we develop Peregrine, a pattern-aware graph mining system that directly explores the subgraphs of interest while avoiding exploration of unnecessary subgraphs, and simultaneously bypassing expensive computations throughout the mining process. We design a pattern-based programming model that treats "graph patterns" as first class constructs and enables Peregrine to extract the semantics of patterns, which it uses to guide its exploration. Our evaluation shows that Peregrine outperforms state-of-the-art distributed and single machine graph mining systems, and scales to complex mining tasks on larger graphs, while retaining simplicity and expressivity with its "pattern-first" programming approach.

1 Introduction

PEREGRINE addresses the inefficiency and limited expressivity of graph-mining systems that are unaware of the patterns they mine. It uses pattern-aware exploration and pattern-based programming, and the authors report strong performance against existing systems.

1 Introduction

  • Pattern-unaware systems perform unnecessary exploration and expensive checks, retain intermediate subgraphs, and make complex mining tasks difficult to express.The paper identifies these as consequences of systems being largely oblivious to the patterns being mined.Source: §1 · pp. 1–2
  • PEREGRINE analyzes patterns to generate an exploration plan, then uses it to find relevant subgraphs while avoiding unnecessary exploration and canonicality and isomorphism checks.The authors also state that it does not maintain intermediate partial subgraphs in memory.Source: §1 · p. 2
  • Its programming model treats graph patterns as first-class constructs and supports advanced structural constraints through ANTI-EDGE and ANTI-VERTEX abstractions.PEREGRINE uses pattern semantics to generate exploration plans.Source: §1 · p. 2
  • A single 16-core PEREGRINE machine outperforms distributed systems running on eight 16-core machines and significantly outperforms RStream on the same machine.The authors also report that it scales to large graphs and complex tasks that other systems could not handle.Source: §1 · p. 2

2 Background & Motivation

Graph mining covers several subgraph-finding tasks, but existing systems can incur costly exploration and checks, retain large intermediate state, and constrain how users express tasks. PEREGRINE instead exposes patterns to users and uses them to guide mining.

2.1 Graph Mining Overview

  • A match is a subgraph isomorphic to a pattern; edge-induced matches need only include pattern edges, while vertex-induced matches include all input-graph edges incident on matched vertices.Symmetries can yield multiple mappings for the same subgraph, so a canonical match represents each automorphic set.Source: §2.1 · p. 2

2.2.1 Performance.

  • Stepwise exploration creates invalid intermediates and costly checks; Figure 1 reports over a billion clique partial matches versus about 3.5 million cliques, and about 101GB memory for Arabesque.The paper also reports that holding partial and complete matches can exceed main-memory capacity as patterns or graphs grow.Source: Figure 1 · p. 3, §2.2.1 · pp. 3–4

2.1 Graph Mining Overview

  • Common tasks include motif counting, frequent subgraph mining, clique counting, and constrained pattern matching; graph-mining workflows select patterns, match them, then aggregate results.Frequent subgraph mining finds frequent labeled patterns; constrained matching can require specified vertices not to be adjacent.Source: §2.1 · p. 3

2.2 Issues with Graph Mining Systems

  • Pattern-unaware systems demand computation and memory while making high-level expression of mining programs difficult.The paper attributes these limitations to existing systems' lack of pattern awareness.Source: §2.2 · p. 3

2.2.2 Programmability.

  • Existing systems make programs difficult to write because users must specify validation, extension, and processing, while complex structural constraints are hard to express.AutoMine's multiplicity algorithm for avoiding over-counting cannot be used when enumerating patterns.Source: §2.2.2 · p. 4

2.3 Overview of PEREGRINE

  • PEREGRINE analyzes patterns to plan symmetry breaking and core-substructure matching, then explores recursively and extends partial matches by adjacency-list intersections without intermediate canonicality or isomorphism checks.It also orders matching by vertex degree to reduce load imbalance and supports on-the-fly aggregation and early termination.Source: §2.3 · p. 4
  • PEREGRINE treats patterns as first-class program objects and adds anti-edges for strict disconnection and anti-vertices for absence of a common neighbor.Users can declare, generate, modify, and query patterns, then perform user-defined operations on matches.Source: §2.3 · p. 4

3 PEREGRINE Programming Model

PEREGRINE makes graph patterns first-class so users can state what to find separately from what to do with matches. Its pattern-aware model supports structural constraints, different match semantics, and mining programs for common tasks.

3.1 PEREGRINE Patterns

  • PEREGRINE treats patterns as first-class constructs, separating the structures to find from operations on their matches.Patterns can be loaded or generated and extended, with an interface to access and modify their graph structure; anti-edges and anti-vertices express advanced structural constraints.Source: §3 · p. 5, §3.1 · p. 5

3.1.1 Anti-Edges.

  • An anti-edge requires its matched data vertices to be disconnected, allowing patterns to express constraints between vertex pairs.For example, it can identify unrelated people who have at least two mutual friends.Source: §3.1.1 · p. 5

3.1.2 Anti-Vertices.

  • An anti-vertex requires the absence of a data vertex matching its neighbors, expressing constraints across shared neighborhoods that anti-edges alone cannot express.Examples include two matched vertices with no common neighbors, or a matched vertex with no neighbors beyond specified matches.Source: §3.1.2 · p. 5

3.1.3 Edge-Induced and Vertex-Induced Patterns.

  • Vertex-induced matches are encoded as edge-induced matches of a pattern augmented with anti-edges between every nonadjacent vertex pair.Frequent subgraph mining uses edge-induced matches, while motif counting requires vertex-induced matches; the programming model expresses both without separately defining an exploration strategy.Source: §3.1.3 · pp. 6–7

3.2 Pattern-Aware Mining Programs in PEREGRINE

  • Mining programs express or load patterns, invoke matching, and run a user-defined function on each match; count() increments a counter.The illustrated use cases include motif counting, frequent subgraph mining, clique counting, pattern matching, and existence queries.Source: §3.2 · p. 7

3.2.1 FSM: Anti-Monotonicity & Label Discovery.

  • Frequent subgraph mining uses PEREGRINE’s MNI support and anti-monotonicity to prune infrequent patterns before extending the remaining frequent patterns.Dynamic label discovery starts from unlabeled or partially labeled patterns and returns labeled matches, enabling iterative discovery of larger frequent labeled patterns.Source: §3.2.1 · p. 7

3.2.2 Existence Queries.

  • Existence queries can stop exploration dynamically once their required condition is met.For a global clustering coefficient bound, the program counts 3-stars and then triangles, stopping when the triangle count suffices; a clique query stops at the first match.Source: §3.2.2 · p. 7

4 Pattern-Aware Matching Engine

PEREGRINE analyzes a pattern to build an exploration plan that directly matches canonical subgraphs without per-match canonicality checks. Anti-edges and anti-vertices add structural constraints that require special handling during matching and symmetry breaking.

4.1 Directly Matching A Given Pattern

  • The engine derives an exploration plan from the pattern, using its minimum connected vertex cover as a core and partial orders to break symmetries.The partial ordering is formed by enumerating pattern automorphisms and ordering symmetric vertex pairs until only the identity automorphism satisfies the ordering.Source: §4.1 · p. 7
  • Matching orders enumerate valid total orderings of the core, enabling traversal by increasing data-vertex ids without canonicality checks.Each matching order is a remapped ordered view of the core; matching its valid sequences yields corresponding core matches.Source: §4.1 · p. 8

4.2 Matching Anti-Edges

  • Anti-edges are checked by set difference on endpoint adjacency lists, and one endpoint is included in the vertex cover so its adjacency list is available.Anti-edges are excluded from partial-order generation because they verify absent edges rather than generate traversals or automorphic matches.Source: §4.2 · p. 8

4.3 Matching Anti-Vertices

  • Anti-vertex constraints are checked after all true vertices are matched, while anti-vertices remain outside the pattern core.Their asymmetries must still inform symmetry breaking; ignoring them can prune valid matches, so the algorithm treats their anti-edges differently when computing automorphisms.Source: §4.3 · pp. 8–9

5 PEREGRINE: Pattern-Aware Mining

PEREGRINE launches independent mining tasks from data vertices and uses a pattern-derived plan to match only the requested structures. It also uses degree-aware traversal, early stopping, and asynchronous aggregation to manage work and results.

5.1 Pattern-Aware Processing Model

  • Each mining task starts at a data vertex and follows matching orders, using sorted adjacency lists and binary search to generate candidates that satisfy the total ordering.Completed core matches are extended with adjacency-list intersections for true edges and differences for anti-edges, then sent to the user callback.Source: §5.1 · p. 9

5.2 Early Pruning for Dynamic Load Balancing

  • High-to-low matching orders and degree-based vertex ordering prune some explorations from high-degree tasks while preserving the total number of matches.Tasks are processed from highest-degree starting vertices to reduce stragglers, though dynamic workload imbalance is not eliminated.Source: §5.2 · p. 9

5.3 Early Termination for Existence Queries

  • For existence queries, a thread can call stopExploration() when the required condition is observed, prompting other threads to stop and return aggregated local values.Source: §5.3 · p. 9

5.4 On-the-fly Aggregation

  • On-the-fly aggregation provides global updates during mining, allowing early termination and support-threshold decisions while other patterns continue matching.An asynchronous aggregator thread combines available thread-local values while matching threads remain non-blocking.Source: §5.4 · p. 9

5.5 Implementation Details

  • The implementation dynamically distributes vertex-starting tasks among C++ threads, which maintain exploration state including candidate sets for each pattern vertex.For support values, it aggregates bitmap domains by logical OR and uses compressed Roaring bitmaps to reduce memory use.Source: §5.5 · p. 10

6 Evaluation

Across the evaluated graph-mining workloads, PEREGRINE generally outperforms the compared systems, with exceptions and workload-specific trade-offs. Its evaluation also examines constrained mining, symmetry breaking, scalability, resource use, and load balance.

6.2 Comparison with Breadth-First Enumeration

  • PEREGRINE outperforms Arabesque and RStream by at least an order of magnitude on motif counting, clique counting, and FSM except FSM, while RStream runs out of memory on FSM and some Mico clique workloads.Arabesque on eight nodes can be faster for FSM at high support thresholds, but lower thresholds bring memory failures from intermediate matches and aggregation values.Source: §6.2 · pp. 10–11

6.3 Comparison with Depth-First Enumeration

  • PEREGRINE is faster than Fractal by at least an order of magnitude across most applications; 4-cliques on Patents took under a second versus over 200 seconds for Fractal.On equal single-node resources, Mico FSM is up to 2.6× faster, and PEREGRINE scales to larger datasets where Fractal does not; it also handles thousands of patterns on Mico and Patents.Source: §6.3 · p. 12

6.4 Comparison with Purpose-Built Algorithms

  • PEREGRINE is 3× to 77× faster than G-Miner for 3-clique counting and 6× to 131× faster for p2 matching on Mico and Patents.G-Miner is faster on Orkut p2 matching because it indexes labels during preprocessing, but those indexes prevented it from handling Friendster even with 240GB disk space.Source: §6.4 · p. 12

6.5 Mining with Constraints in PEREGRINE

  • PEREGRINE matches triangle patterns excluding those contained in a 4-clique in under a minute on Orkut and under eight minutes on Friendster, and completes vertex-induced chordal-square matching on all datasets.Anti-edge matching requires set differences of adjacency lists, described as twice as many operations as the sum of their sizes.Source: §6.5 · p. 12

6.6 PEREGRINE’s Pattern-Aware Runtime

  • Symmetry breaking improves 4-motif performance by an order of magnitude on Mico and Patents; without it, Orkut 4-motifs did not finish matching one size-4 pattern within five hours.For FSM, symmetry breaking improves performance 3× by avoiding redundant aggregation writes and reads per unique match.Source: §6.6 · p. 13, Figure 10 · p. 13
  • Most 4-motif execution time is spent intersecting adjacency lists to complete matches, while matching the core pattern takes an insignificant share of total time.The core traversal is fully guided by valid total orderings, whereas non-core vertices have less ordering guidance and often require more intersections.Source: §6.6 · p. 13

6.7 System Characteristics

  • PEREGRINE scales linearly to 48 threads; 48 physical cores yield 41× speedup, compared with 30× using 24 physical cores and 48 threads.Hyper-threading helps hide memory latency only to an extent, and 48-core execution incurs 86GB of cross-NUMA traffic versus 4.9MB at 24 cores.Source: §6.7 · pp. 13–14, Figure 12 · p. 14
  • PEREGRINE uses less peak memory than the compared systems and observes up to 71 ms difference in thread completion times while matching p1 across datasets.Clique and motif pattern size does not affect its memory use; FSM uses more memory because of support-calculation domain maps.Source: §6.7 · p. 14

7 Related Work

Prior graph-mining work spans general-purpose systems, task-specific solutions, pattern-matching systems, and graph-processing frameworks. The paper positions PEREGRINE as the first general-purpose graph-mining system to use pattern-awareness in both its programming and processing models.

General-Purpose Graph Mining Systems

  • PEREGRINE is presented as the first general-purpose graph-mining system to leverage pattern-awareness in its programming and processing models.Source: §7 · p. 14
  • General-purpose systems offer broad exploration frameworks, but remain not fully pattern-aware, leading to unnecessary exploration and computation, resource demands, and difficulty expressing complex tasks.Fractal uses symmetry breaking for pattern matching, but not for FSM or motif counting; AutoMine also lacks symmetry breaking in its use cases.Source: §7 · p. 14

Purpose-Built Graph Mining Solutions

  • Purpose-built systems target particular tasks, including approximate graphlet counts, small-motif counting, clique and plex listing, and frequent subgraph mining.The cited work also includes distributed FSM systems and systems for analyzing small graphs with large edge-attribute sets.Source: §7 · pp. 14–15

Pattern Matching Systems

  • Pattern-matching research includes out-of-core and cache-friendly triangle counting, distributed triangle counting, and systems for matching arbitrary or large patterns.Other approaches join small patterns into larger ones, prune vertices, handle dynamic graphs, optimize query plans, or support resource-aware graph querying.Source: §7 · p. 15

Graph Processing Systems

  • Graph-processing systems typically compute values at vertices and edges, a decomposition the paper says is unsuitable for graph-mining use cases focused on substructures.Source: §7 · p. 15

8 Conclusion

PEREGRINE combines pattern-aware subgraph exploration with a pattern-based programming model and ANTI-EDGE and ANTI-VERTEX abstractions for structural constraints. The evaluation reports orders-of-magnitude gains and billion-scale tasks handled on a single machine under conditions where existing systems fail.

8 Conclusion

  • Its pattern-based programming model treats patterns as first-class constructs, and ANTI-EDGE and ANTI-VERTEX express advanced structural constraints for complex pattern programs.Source: §8 · p. 15
  • PEREGRINE outperforms existing state-of-the-art systems by several orders of magnitude, even with up to 8× fewer CPU cores.Source: §8 · p. 15
  • PEREGRINE handles resource-intensive graph-mining tasks on billion-scale graphs on one machine, while state-of-the-art systems fail with an eight-machine cluster or large SSDs.Source: §8 · p. 15
Loading 2004.02369v1…