Enumerating Subgraph Instances Using Map-Reduce

Abstract

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 (EDBT 2010) 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 work at the reducers be of the same order as the work of the serial algorithm. For data graphs of unrestricted degree, we show that there are convertible algorithms whose running time is of the same order as the lower bounds on number of occurrences of the sample graph that were provided by Noga Alon (1981 IJM). We also offer better convertible algorithms when the degree of nodes in a data graph of m nodes is limited to √m.