Source-linked AI summary
Enumerating Subgraph Instances Using Map-Reduce
Foto N. Afrati, Dimitris Fotakis, Jeffrey D. Ullman
TL;DR
Finding every instance of a sample graph in a large data graph is computationally intensive and useful in network analysis. The paper develops single-round map-reduce methods that combine query-based communication strategies with partitioned computation, and reports algorithms efficient in both communication and computation costs.
Problem
Finding all instances of a sample graph in a very large data graph is computationally intensive and has applications including social-network and biomolecular-network analysis.
Source: §1 · p. 1, §1.1 · p. 2Method
The paper translates sample graphs into conjunctive queries and combines communication-efficient query evaluation with partitioned reducer computation in single-round map-reduce algorithms.
Source: §1.3 · p. 3, §2 · p. 4, §3.2 · p. 10Results
The authors report single-round algorithms that detect all instances of a given sample graph and are efficient in both communication and computation costs.
Source: §8 · p. 35Takeaways & Limitations
The algorithms apply to instance-finding problems in social, threat-detection, and biomolecular networks.
Source: §1.1 · p. 2, §8 · p. 35The paper does not address labeled nodes or edges or directed graphs, though it says many techniques carry over straightforwardly.
Source: §8 · p. 36
Abstract
from arXiv · showhide
The theme of this paper is how to find all instances of a given "sample" graph in a larger "data graph," using a single round of map-reduce. For the simplest sample graph, the triangle, we improve upon the best known such algorithm. We then examine the general case, considering both the communication cost between mappers and reducers and the total computation cost at the reducers. To minimize communication cost, we exploit the techniques of (Afrati and Ullman, TKDE 2011)for computing multiway joins (evaluating conjunctive queries) in a single map-reduce round. Several methods are shown for translating sample graphs into a union of conjunctive queries with as few queries as possible. We also address the matter of optimizing computation cost. Many serial algorithms are shown to be "convertible," in the sense that it is possible to partition the data graph, explore each partition in a separate reducer, and have the total computation cost at the reducers be of the same order as the computation cost of the serial algorithm.
1 Introduction
The paper develops single-round map-reduce algorithms for finding all instances of a sample graph in a large data graph, targeting communication and reducer computation costs. It outlines applications, query-based communication methods, and conditions for matching serial computation complexity.
1 Introduction
- The task is computationally intensive: find every instance of a specified sample graph in a very large data graph using one map-reduce round.The paper distinguishes communication cost from computation cost, focusing on data sent to reducers and time spent by reducers.Source: §1 · p. 1
1.1 Applications
- Subgraph instances support social-network analysis, including relating community evolution to sample-graph frequency, and biomolecular-network research.Labeled or directed network queries, such as finding interconnected people meeting specified conditions, are also considered, with extensions to the methods described as straightforward.Source: §1.1 · p. 2
1.2 Measures of Complexity
- Communication cost measures data transferred from mappers to reducers, while computation cost is total mapper and reducer time; mapper work is proportional to communication cost.The paper therefore focuses its computation-cost discussion on reducers.Source: §1.2 · p. 2
1.3 Outline of the Paper and Contributions
- The paper translates arbitrary sample graphs into conjunctive queries, simplifies them using automorphisms and edge orientations, and evaluates them together in one map-reduce round.For fixed-length cycles, it also gives a method that generates fewer queries than the general method; for computation, it identifies a condition under which partitioning makes a serial algorithm convertible, with lower bounds met by convertible algorithms and more efficient options for bounded-degree data graphs.Source: §1.3 · pp. 3–4
1.4 Related Work
- Prior work covered cycle detection and counting, approximate counting, and triangle-finding; this paper addresses exact enumeration and extends triangle map-reduce methods to arbitrary subgraphs.The paper also relates its single-relation joins to a multiway-join output-size bound, matching it for all input sizes except rounding errors.Source: §1.4 · p. 4
2 Triangles and Multiway Joins
The section treats single-round triangle enumeration as a multiway-join problem and compares partition-based and join-based algorithms. Ordering nodes by bucket lowers communication while retaining the serial algorithm’s order of computation.
2.1 The Partition Algorithm of Suri and Vassilvitskii
- Partition uses about b^3/6 reducers and has O(m^3/2) total work under random edge distribution, matching the cited best serial running time.For large b, its communication cost is approximately 3bm/2; within-partition edges can be copied too often, causing duplicate triangle counts.Source: §2.1 · p. 5
2.2 The Multway-Join Algorithm
- The multiway-join mapping uses b^3 reducers and communication cost m(3b−2); ordering tuples ensures each triangle is discovered once.Each edge is mapped for the E(X,Y), E(Y,Z), and E(X,Z) join roles.Source: §2.2 · pp. 5–6
2.3 Ordering Nodes by Bucket
- Ordering nodes by bucket permits only sorted bucket triples, using about b^3/6 reducers and b copies per edge while preserving O(m^3/2) total reducer work.A triangle is assigned to the reducer for its nodes’ buckets in sorted order.Source: §2.3 · pp. 6–7
2.4 Comparison of Triangle-Finding Algorithms
- 3/2 and 1.65: Section 2.3’s algorithm beats Partition and Section 2.2, respectively, in communication cost.Computation costs are similar, but Partition counts some triangles more than once and requires extra work to compensate.Source: §2.4 · p. 7, Figure 1 · p. 8, Figure 2 · p. 8
3 Sample Graphs and Conjunctive Queries
This section formulates subgraph matching as conjunctive queries (CQs), whose edge subgoals encode sample-graph edges and arithmetic comparisons enforce node orders. It reduces redundant queries using sample-graph automorphisms and shared edge orientations.
3 Sample Graphs and Conjunctive Queries
- Arithmetic comparisons constrain multiway joins to avoid duplicate instances, and the paper represents these joins-plus-selections as conjunctive queries.Each CQ has a variable for every sample-graph node and an E subgoal for every edge.Source: §3 · p. 8
3.1 Generating CQ’s from Orderings
- For each node ordering, the CQ includes an E subgoal per sample-graph edge and consecutive-variable inequalities enforcing that ordering.For the square, three CQs suffice despite 24 possible node orders.Source: §3.1 · p. 9
3.2 Exploiting Automorphisms
- For a p-node sample graph S, one CQ per class in the quotient of the symmetric group by S’s automorphism group finds every instance exactly once.The authors note that sample graphs are typically small and most small graphs have nontrivial automorphisms.Source: §3 · p. 9, §3.2 · p. 10
3.3 Exploiting Edge Orientations
- When generated CQs share edge orientations, OR-combining their arithmetic conditions merges them; for the lollipop, twelve symmetry-reduced CQs collapse to six orientations.The lollipop’s 24 node orders reduce to twelve under its two automorphisms; two of the eight possible orientations are impossible.Source: §3.3 · pp. 11–12
4 Evaluation of CQ’s with Optimal Communication Cost
This section develops methods for minimizing map-reduce communication when evaluating conjunctive queries for sample graphs, deriving share assignments and extending variable-oriented optimization to broader graph structures. It also examines combining queries and bucket-oriented processing, including its communication-cost comparison with generalized Partition.
4 Evaluation of CQ’s with Optimal Communication Cost
- An undirected single-join approach with duplicate elimination is never superior to variable-oriented processing and can be worse.The section also contrasts separate-CQ, variable-oriented, and bucket-oriented evaluation; separate-CQ processing never dominates the others.Source: §4 · p. 13
4.1 Optimization of Single CQ’s
- For a single CQ, communication cost sums each subgoal’s relation size multiplied by the shares of variables absent from it; the optimum equalizes specified subsets of terms.The optimization approach reviews and.Source: §4.1 · pp. 13–14
4.2 Regular Sample Graphs
- For a regular sample graph with p nodes and k reducers, the optimal assignment gives all nodes equal shares.Theorem 4.1 applies to cycles, complete graphs, and hypercubes; hashed ordering can leave many reducers unused, significantly lowering edge replication. For CQ instances enforcing a node order, Theorem 4.2 counts useful reducers under a shared hash function and hash-then-identifier ordering.Source: §4.2 · p. 15
4.3 Variable-Oriented Processing
- For variable-oriented processing, edges appearing in both orientations double the corresponding relation size, and the square example’s optimal shares need only satisfy x = z and y = 2w.These constraints do not uniquely determine the shares, but choices satisfying them and wxyz = k achieve the same optimal communication cost.Source: §4.3 · p. 16
4.3.1 Variable-Oriented Processing for Regular Sample Graphs
- For regular sample graphs meeting either stated S1/S2 edge-pattern condition, optimal shares are equal within each set, with S1 shares twice S2 shares.Source: §4.3.1 · p. 17
- For a cycle using the standard CQ ordering, X1 receives half the share assigned to each other node.For the six-node example, X1 has share 5 while the other nodes each have share 10, using 500,000 reducers.Source: §4.3.1 · p. 17
4.3.2 More Details on Variable-Oriented Processing
- The general variable-oriented method equates Lagrangian sums formed from each node’s incident edges, whose terms are 1/(xy) or 2/(xy) depending on edge orientation.For analysis, it groups edges used in both orientations into H and partitions nodes by whether they are adjacent only to H edges, to both edge types, or only to edges outside H.Source: §4.3.2 · pp. 17–18
- In a case where S2 is an independent set covering every edge, optimal variable shares assign S1=a, S3=a/2, and S2=z=a.The section presents replication-per-input-tuple results for optimized variable shares and notes that communication cost varies across situations.Source: §4.3.2 · p. 21
4.4 Advantage of Variable-Oriented Processing
- Combining all queries for a sample graph has communication cost no greater than splitting them into subgroups.The queries have the same relational subgoals up to argument reordering; the theorem recommends one hash function for the whole group.Source: §4.4 · pp. 21–22
4.5 Bucket-Oriented Processing
- Bucket-oriented processing uses the same bucket count for every variable, sacrificing bucket-count optimization so each edge is distributed in only one orientation.Which approach is better depends on how far the equal-bucket choice is from optimal and how many query subgoals use arguments in both directions.Source: §4.5 · pp. 22–23
- For arbitrary sample graphs, the bucket-oriented method beats the generalization of Partition; its advantage decreases as p increases, and the ratio is always greater than 1 but approaches 1 as p, the number of sample-graph nodes, grows.Source: §4.5 · p. 23
5 Conjunctive Queries for Cycles
The cycle queries are built by grouping edge orientations into run sequences and using cycle symmetries to avoid redundant queries. The algorithm’s query group discovers every cycle once and is minimum, with a prime-length upper bound illustrated by seven-node cycles.
5 Conjunctive Queries for Cycles
- Cycle orientations become alternating runs of up and down edges, beginning with up and ending with down, with an even number of runs.Run lengths are positive integers summing to the cycle length.Source: §5 · pp. 23–24
5.1 Automorphisms and Run Sequences
- For C5, symmetry reductions leave three queries, for orientations udddd, uuddd, and uduud.The reductions remove equivalent run sequences under cyclic shifts and flips.Source: §5.1 · pp. 24–25
5.2 Algorithm for Finding Cycles Using Runs and Orientation
- The algorithm’s conjunctive queries discover each cycle once, and the constructed group is minimum.It selects one basic query from each class under flips and cyclic shifts.Source: §5.2 · pp. 26–27
5.3 An Upper Bound on the Number of CQ’s and Some Examples
- For prime p, the bound (2p −2)/(2p) is unconditional; for p = 7, the minimum query count is 9.For p = 6, periodicities and palindromes raise the bound to 7, matching the minimum.Source: §5.3 · p. 28
6 Map-Reduce Computation Cost
The paper studies reducer computation cost and when partitioning a data graph preserves a serial algorithm’s total work. It gives a convertibility condition and shows how convertible algorithms can be combined through sample-graph decomposition.
6 Map-Reduce Computation Cost
- The computation-cost analysis focuses on reducers because mapper computation is proportional to communication cost.The total work across reducers is compared with the running time of the serial algorithm.Source: §6 · p. 28
6.1 Convertible Algorithms
- A serial algorithm running in O(n^αm^β) is convertible when α + 2β is at least the number of sample-graph nodes.The mapping hashes sample-graph nodes into b buckets and sends edges to reducers whose bucket lists contain both endpoints.Source: §6.1 · p. 29
6.2 Decomposition of Sample Graphs
- If convertible algorithms enumerate two induced subgraphs in O(n^αᵢm^βᵢ), their combination is convertible with running time O(n^αm^β).The combined exponents are α = α₁ + α₂ and β = β₁ + β₂.Source: §6.2 · p. 30
- Decomposition into edges and odd cycles yields matching serial and map-reduce computation bounds for graphs in that family.The paper gives odd-cycle enumeration in O(m^p/2) time and states that the resulting algorithm is convertible.Source: §6.2 · p. 31
7 Optimal Serial Algorithms for General Sample Graphs
The section develops serial enumeration algorithms and shows how their computation bounds can transfer to map-reduce. It covers odd-cycle-based methods, graph decompositions, bounded-degree data graphs, and a refined analysis for 5-way joins over differently sized relations.
7 Optimal Serial Algorithms for General Sample Graphs
- With maximum degree at most √m, every connected p-node sample graph has a convertible enumeration algorithm running in O(mp/2) time.The section states that this meets known bounds for general data graphs.Source: §7 · p. 31
7.1 Odd-Length Hamilton Cycles
- An odd p-node sample graph containing a Hamilton cycle has a (0, p/2)-algorithm, built from properly ordered 2-paths and edges.Properly ordered 2-paths can be generated in O(m3/2) time.Source: §7.1 · pp. 31–32
7.2 General Sample Graphs
- Decomposing a sample graph into isolated nodes, edges, and odd-Hamilton-cycle subgraphs, plus connecting edges, yields a convertible enumeration algorithm.The decomposition should minimize isolated nodes.Source: §7.2 · p. 33
7.3 Data Graphs of Bounded Maximum Degree
- For connected p-node samples in data graphs of maximum degree ∆, enumeration takes O(m∆^(p−2)); the bound is essentially tight.A ∆-regular tree contains Θ(m∆^(p−2)) instances of a p-node star under the stated conditions.Source: §7.3 · pp. 33–34
7.4 Joins for binary relations of different sizes
- For binary relations of different sizes, single-relation bounds are tight, but sharper multiway-join bounds remain open beyond the analyzed 5-cycle case.In one stated case, the upper and lower bounds meet at n1n5n3.Source: §7.4 · pp. 34–35
8 Conclusions and Open Problems
The paper reports single-round MapReduce algorithms for enumerating sample-graph instances, efficient in communication and computation. It identifies unresolved scope and optimization questions, including labeled or directed graphs and alternatives to minimizing conjunctive queries with multiway joins.
8 Conclusions and Open Problems
- The paper gives single-round MapReduce algorithms to detect all instances of a sample graph, efficient in communication and computation costs.The stated application scope includes social networks, threat detection, and biomolecular networks.Source: §8 · p. 35
- Labeled-node, labeled-edge, and directed-graph cases remain unaddressed, though the authors expect many techniques to carry over and note that smaller automorphism groups may increase the number of conjunctive queries.They expect provably convertible algorithms in all or almost all cases, while noting that mapping schemes may require thought.Source: §8 · p. 36
- Other query-generation algorithms may produce fewer conjunctive queries or evaluate query collections more efficiently than the methods considered.The authors also raise alternatives to multiway joins, including multi-round MapReduce for collections with common subexpressions.Source: §8 · p. 36
- The authors ask whether data-graph restrictions beyond degree limits can yield better convertible algorithms.Source: §8 · p. 36
- Whether convertibility extends to other classes of MapReduce problems remains an open question.Source: §8 · p. 36