2015 BeyondTrianglesADistributedFram

• (Elenberg et al., 2015) ⇒ Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. (2015). “Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783413

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Beyond+Triangles%3A+A+Distributed+Framework+for+Estimating+3-profiles+of+Large+Graphs
• http://dl.acm.org/citation.cfm?id=2783258.2783413&preflayout=flat#citedby

Quotes

Author Keywords

• 3-profiles; distributed applications; graph algorithms; graph analytics; graph engines; graph sparsifiers; graphlab; motifs

Abstract

We study the problem of approximating the 3-profile of a large graph. 3-profiles are generalizations of triangle counts that specify the number of times a small graph appears as an induced subgraph of a large graph. Our algorithm uses the novel concept of 3-profile sparsifiers: sparse graphs that can be used to approximate the full 3-profile counts for a given large graph. Further, we study the problem of estimating local and ego 3-profiles, two graph quantities that characterize the local neighborhood of each vertex of a graph.

Our algorithm is distributed and operates as a vertex program over the GraphLab PowerGraph framework. We introduce the concept of edge pivoting which allows us to collect 2-hop information without maintaining an explicit 2-hop neighborhood list at each vertex. This enables the computation of all the local 3-profiles in parallel with minimal communication.

We test our implementation in several experiments scaling up to 640 cores on Amazon EC2. We find that our algorithm can estimate the 3-profile of a graph in approximately the same time as triangle counting. For the harder problem of ego 3-profiles, we introduce an algorithm that can estimate profiles of hundreds of thousands of vertices in parallel, in the timescale of minutes.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 BeyondTrianglesADistributedFram	Ethan R. Elenberg Karthikeyan Shanmugam Michael Borokhovich Alexandros G. Dimakis			Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs				10.1145/2783258.2783413		2015