PaperlayerView exact revision on arXiv

Source-linked AI summary

Arabesque: A System for Distributed Graph Mining - Extended version

Carlos H. C. Teixeira, Alexandre J. Fonseca, Marco Serafini, Georgos Siganos, Mohammed J. Zaki, Ashraf Aboulnaga

arXiv:1510.04233v1cs.DC

TL;DR

Graph mining requires exploring very large numbers of subgraphs, a workload not well matched to conventional distributed analytics platforms. Arabesque automates distributed embedding exploration with a high-level filter-process model and applies it to three graph-mining problems. Its implementations scale to trillions of embeddings, while the system uses canonicality, ODAG storage, and aggregation optimizations to reduce redundant work and resource costs.

  • Problem

    Graph mining must explore exponentially many subgraphs and identify patterns meeting user-defined interestingness criteria, creating a scalability challenge for distributed processing.

  • Method

    Arabesque is a distributed embedding-exploration system with a filter-process API that lets applications process explored embeddings and decide which should be extended.

  • Results

    Arabesque implements frequent subgraph mining, motif counting, and clique finding, scales to trillions of embeddings, and achieves orders-of-magnitude lower running time than centralized baselines.

  • Takeaways & Limitations

    Embedding exploration provides a scalable and concise foundation for distributed graph-mining workloads, including some first available distributed solutions.

  • Takeaways & Limitations

    Arabesque assumes automorphism invariance in user-defined functions to prune equivalent embeddings, and TLV-based exploration can be two orders of magnitude slower than TLE.

Abstract

from arXiv · show

Distributed data processing platforms such as MapReduce and Pregel have substantially simplified the design and deployment of certain classes of distributed graph analytics algorithms. However, these platforms do not represent a good match for distributed graph mining problems, as for example finding frequent subgraphs in a graph. Given an input graph, these problems require exploring a very large number of subgraphs and finding patterns that match some "interestingness" criteria desired by the user. These algorithms are very important for areas such as social net- works, semantic web, and bioinformatics. In this paper, we present Arabesque, the first distributed data processing platform for implementing graph mining algorithms. Arabesque automates the process of exploring a very large number of subgraphs. It defines a high-level filter-process computational model that simplifies the development of scalable graph mining algorithms: Arabesque explores subgraphs and passes them to the application, which must simply compute outputs and decide whether the subgraph should be further extended. We use Arabesque's API to produce distributed solutions to three fundamental graph mining problems: frequent subgraph mining, counting motifs, and finding cliques. Our implementations require a handful of lines of code, scale to trillions of subgraphs, and represent in some cases the first available distributed solutions.

1 Introduction

Graph mining is difficult to scale because interesting subgraphs can grow exponentially, while conventional graph-processing paradigms do not readily express these workloads. Arabesque addresses this gap with distributed embedding exploration, a filter-process API, and scalable implementation techniques.

  • Motivation: Pregel’s “think like a vertex” paradigm supports linear-algebra-style graph analytics but cannot readily formulate an important class of graph mining algorithms.These algorithms require exploring patterns and their embeddings rather than updating only vertex-local state.
  • Motivation: Graph mining workloads discover structure- and label-based patterns, but their possible subgraphs can be exponential in graph size.This creates an explosion in computation and intermediate state, making moderately large graphs difficult to process.
  • Arabesque: Arabesque introduces automatic subgraph exploration and a “think like an embedding” paradigm for distributed graph mining.An embedding is a subgraph instance of a more general pattern template.
  • Arabesque: Its filter-process model systematically visits embeddings, passes them to applications, and lets user-defined filter and process functions control processing and outputs.The application can also determine whether an embedding should be further extended.
  • Applications: Arabesque implements distributed solutions for frequent subgraph mining, motif counting, and clique finding, including some of the first distributed solutions available.The API is intended to simplify graph-mining algorithm design and automate distributed execution.
  • Scalability: Coordination-free work sharing, embedding storage, and pattern-based aggregation techniques support scalable exploration across workers.The system uses embedding canonicality to reduce redundant work and communication, and ODAGs to store embeddings efficiently.
  • Evaluation: Arabesque scales to hundreds of cores, reduces running time by orders of magnitude over centralized baselines, and analyzes trillions of embeddings.It is implemented as a layer on Apache Giraph, allowing graph computation and graph mining to share infrastructure.

2 Graph Mining Problems

Graph mining enumerates connected, labeled subgraph patterns and evaluates their embeddings against user-defined interestingness criteria. Arabesque covers variants including frequent subgraph mining, motif mining, clique mining, and related matching tasks.

  • Terminology: An embedding is a subgraph of the input graph, while a pattern is an arbitrary graph matched through label-preserving structural isomorphism.Automorphic embeddings contain the same vertices and edges and are treated as equivalent duplicates.
  • Characterization: Graph mining takes a labeled input graph and enumerates patterns whose embeddings satisfy user-specified interestingness criteria.Patterns are evaluated by listing their matching embeddings and filtering out uninteresting ones.
  • Problem scope: Arabesque targets connected graph patterns with vertex-induced or edge-induced embeddings, across single graphs, graph collections, exact matching, and approximate matching.Graph mining also includes variants such as frequent, dense, and frequency-distribution mining.
  • Frequent subgraph mining: Frequent subgraph mining finds patterns occurring at least a minimum number of times, using anti-monotonic support to stop extending infrequent patterns.Because a supergraph cannot be more frequent than a subgraph, infrequency permits pruning extensions.
  • Motif mining: Motif mining extracts non-isomorphic connected patterns with vertex-induced embeddings and their frequency distribution, without a minimum frequency threshold.The task is inherently exponential and is typically restricted by pattern size.
  • Clique mining: Clique mining enumerates complete subgraphs, where every vertex connects to all other vertices; maximal and frequent cliques are extensions of this task.A k-vertex clique has degree k − 1 at every vertex.

3 The Filter-Process Model

Arabesque formalizes distributed graph mining as systematic embedding exploration controlled by user-defined filter and process functions. Its model supports parallel execution while exploiting automorphism invariance and anti-monotonicity to reduce redundant exploration.

  • 3 The Filter-Process Model: Arabesque organizes computation as repeated exploration steps that expand an initial embedding set and pass candidate embeddings to application-defined functions.The process continues until no embeddings remain for further exploration.
  • 3 The Filter-Process Model: The filter function selects embeddings for processing, while the process function examines selected embeddings and produces user-defined outputs.Selected embeddings are normally retained for the next exploration step unless termination or filtering prevents further extension.
  • 3 The Filter-Process Model: Arabesque distributes embeddings across servers and worker threads, executing each exploration step as a Bulk Synchronous Parallel superstep.This distribution is transparent to applications, which operate through the filter-process abstraction.
  • 3 The Filter-Process Model: Optional aggregation functions filter and process embeddings using information aggregated across embeddings generated in the same exploration step.Aggregation supports tasks such as computing pattern frequency while preserving the model's embedding-level exploration.
  • 3 The Filter-Process Model: Completeness requires every embedding passing the relevant filters to contribute its process and aggregation outputs.This guarantee depends on user-defined functions satisfying the model's stated properties.
  • 3 The Filter-Process Model: Automorphism invariance enables pruning equivalent embeddings, while anti-monotonicity allows pruning all extensions of a rejected embedding.These properties reduce redundant work and exploration space when they hold for the application functions.
  • 3.2 Alternative Paradigms: Think Like a Vertex and Think Like a Pattern: Compared with TLV and TLP approaches, TLE makes embeddings the explicit exploration unit rather than assigning state to vertices or patterns.TLV can overload highly connected vertices and duplicate messages, while pattern partitioning can create load imbalance around popular patterns.

4 Arabesque: API, Programming, and Implementation

Arabesque exposes graph mining through a compact API centered on filter, process, and optional aggregation functions. The paper implements frequent subgraph mining, motif counting, and clique finding with short application programs and a BSP-based runtime.

  • 4.1 Arabesque API: Arabesque applications implement filter and process functions, with optional aggregationFilter and aggregationProcess functions for aggregate-based decisions and outputs.All functions access a local read-only copy of the graph, and process writes results through Arabesque's output mechanism.
  • 4.1 Arabesque API: The API supports framework-managed output, map/reduce-style aggregation, aggregate reads, and output aggregation to the distributed filesystem.Pattern keys receive specific optimizations during aggregation.
  • 4.1 Arabesque API: A terminationFilter can stop exploration after a predefined condition, such as reaching a maximum embedding size.Arabesque applies this optimization after processing an embedding and before adding it to the next frontier.
  • 4.2 Programming with Arabesque: The three example applications are implemented in very few lines of code compared with specialized state-of-the-art algorithms.The examples cover frequent subgraph mining, motif counting, and clique finding.
  • 4.2 Programming with Arabesque: Frequent subgraph mining aggregates vertex-mapping domains by pattern, computes support as the minimum domain size, and filters patterns below the support threshold.Surviving embeddings are output through aggregationProcess.
  • 4.2 Programming with Arabesque: 280 lines implement frequent subgraph mining, including 212 lines for domain and support handling, versus 5,443 lines in the GRAMI baseline.The comparison concerns Java code size for the application and its centralized evaluation baseline.
  • 4.2 Programming with Arabesque: Motif counting exhaustively explores embeddings to a maximum size, groups them by pattern, and sums counts for each motif.The implementation uses vertex-based exploration and sends pattern counts to reducers.
  • 4.2 Programming with Arabesque: Clique finding prunes any embedding that is not a clique because none of its extensions can be cliques, then outputs the surviving embeddings.The implementation uses vertex-based exploration and checks connectivity of each newly added vertex.

5 Graph Exploration Techniques

Arabesque makes distributed graph exploration scalable through coordination-free canonicality checks, compact ODAG storage, and two-level pattern aggregation. These techniques reduce redundant work, represent many embeddings compactly, and limit expensive graph-isomorphism computations.

  • 5.1 Coordination-Free Exploration Strategy: Canonicality checks select one embedding from each automorphic set without coordination, preventing redundant work across distributed workers.The check is applied before filter and process functions, and canonical embeddings satisfy uniqueness and extendibility properties.
  • 5.1 Coordination-Free Exploration Strategy: Arabesque incrementally checks canonicality by extending a canonical parent embedding and visiting vertices in increasing-order exploration order.The linear-time check rejects non-canonical candidates before the next exploration step.
  • 5.2 Storing Embeddings Compactly: ODAGs collapse same-depth nodes representing the same graph vertex, trading extra filtering work for substantially lower embedding-storage space.ODAGs can encode spurious paths, which are removed using canonicality and application-defined filtering criteria.
  • 5.2 Storing Embeddings Compactly: O(N^k) possible size-k embeddings can be represented by ODAGs with O(k · N^2) size, or O(N^2) when k is constant.ODAGs store edges between k arrays rather than storing every embedding separately.
  • 5.4 Two-Level Pattern Aggregation for Fast Pattern Canonicality Checking: Two-level pattern aggregation computes cheap quick patterns locally before applying graph isomorphism only to the much smaller set of quick patterns.This avoids graph-isomorphism computation for a very large number of candidate embeddings.

6 Evaluation

Arabesque is evaluated on a 20-server cluster against alternative paradigms and centralized implementations. It achieves strong single-thread efficiency, scales across servers and graph-mining workloads, and processes trillions of embeddings, while exposing workload- and graph-dependent bottlenecks.

  • Alternative Paradigms: TLV and TLP: TLV does not scale beyond 5 servers on CiteSeer FSM because embeddings must be replicated and high-degree vertices receive disproportionate expansion work.CiteSeer’s scale-free structure aggravates these hotspots.
  • Alternative Paradigms: TLV and TLP: 300+ seconds versus 7 seconds: TLV is two orders of magnitude slower than Arabesque for CiteSeer FSM, exchanging 120 million versus 137 thousand messages.The comparison uses the same support and graph setup.
  • Alternative Paradigms: TLV and TLP: 3 seconds versus hundreds of seconds: TLP-based GRAMI is faster than TLV but has extremely limited scalability and cannot improve over the centralized algorithm.Its workers are limited by the small number of frequent patterns and graph skew.
  • Arabesque: The TLE Paradigm: Arabesque matches or exceeds most centralized single-thread implementations, while GRAMI’s advantage disappears when actual frequent embeddings must be discovered.Arabesque’s user-defined functions consume insignificant CPU time, leaving exploration details available for system-level optimization.
  • Arabesque: The TLE Paradigm: Arabesque scales to many servers, but applications generating more intermediate state and patterns scale less; FSM scales less than Cliques, with Motifs between them.FSM transmits many embeddings later discarded by aggregation, whereas Cliques has one pattern per step and fewer embeddings.
  • Arabesque: The TLE Paradigm: ODAGs remain advantageous despite communication and scalability costs because removing them can increase execution time up to 4 times.ODAG compression reduces network transmission, serialization, and garbage-collection overhead.
  • Arabesque: The TLE Paradigm: 21 versus 218 billion graph-isomorphism computations: two-level optimization sharply reduces work for Motifs on Youtube.The number of quick patterns is close to the number of actual canonical patterns.

7 Related Work

Related work spans centralized, distributed, and parallel graph-mining methods. Existing distributed FSM approaches largely target multiple input graphs, leaving the single-large-graph setting more difficult and less covered.

  • Centralized Algorithms: Centralized graph-mining methods include gSpan for frequent subgraph mining, GRAMI for single large graphs, motif-frequency methods, and Bron–Kerbosch for maximal cliques.The section distinguishes the greater complexity of finding multiple instances within one input graph.
  • Distributed and Parallel Approaches: MPI, MapReduce, and GPU approaches have addressed distributed or parallel FSM, but they focus on multiple input graphs rather than a single large graph.The paper identifies the multiple-graph case as simpler than mining one large graph.

8 Conclusions

The conclusion argues that distributed graph mining requires a different design perspective rather than straightforwardly distributing centralized algorithms. Arabesque combines scalability with a simple API for building efficient distributed graph-mining solutions.

  • Conclusions: Distributing graph-mining tasks is far from trivial because adapting centralized algorithms through TLV or TLP can create scalability issues.The authors state that distribution requires a mental shift in how these problems are approached.
  • Conclusions: Arabesque is designed from scratch as a distributed graph-mining framework that combines scalability with a user-friendly API for non-experts.The authors report that the API supports highly efficient solutions that scale and perform well.

Appendix

The appendix formalizes canonical embeddings and proves that the verification algorithm recognizes them, that the definition is unique and extendible, and that Arabesque’s exploration is complete under stated filter properties.

  • Canonical embeddings: Definition 1 characterizes canonical vertex-induced embeddings through three properties governing the initial vertex, connectivity, and vertex ordering.The appendix focuses on vertex-based exploration; the edge-based case is stated to be analogous.
  • Verification: Algorithm 2 returns true if and only if the embedding satisfies Definition 1, established by induction on embedding length.The base case checks the smallest vertex identifier, while the inductive step verifies the remaining properties for an extension.
  • Canonical embeddings: Definition 1 satisfies uniqueness and extendibility, so every embedding has a single canonical representation that can be extended consistently.The uniqueness proof constructs a canonical automorphic embedding and rules out two canonical embeddings by contradiction.
  • Completeness: For each embedding e with φ(e) ∧ α(e) = true, Algorithm 1 adds π(e) and β(e) to O.The completeness proof uses canonical automorphisms, automorphism-invariant filters, anti-monotonicity, connectedness, and extendibility to reach the target embedding.
Loading 1510.04233v1…