Subgraph Counting: Color Coding beyond Trees

Venkatesan T. Chakaravarthy, Michael Kapralov, Prakash Murali, Fabrizio Petrini, Xinyu Que, Yogish Sabharwal, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysis. Many important special cases (e.g. triangle counting) have received significant attention. Color coding is a very general and powerful algorithmic technique for subgraph counting. Color coding has been shown to be effective in several applications, but scalable implementations are only known for the special case of tree queries (i.e. queries of treewidth one). In this paper we present the first efficient distributed implementation for color coding that goes beyond tree queries: ouralgorithm applies to any query graph of treewidth 2. Since tree queries can be solved in time linear in the size of the data graph, our contribution is the first step into the realm of color codingfor queries that require superlinear worst case running time. This superlinear complexity leads to significant load balancing problems on graphs with heavy tailed degree distributions. Our algorithm works around high degree nodes in the data graph, and achieves very good runtime and scalability on a diverse collection of data and query graph pairs. We also provide a theoretical analysis of our algorithmic techniques, exhibiting asymptotic improvements in runtime on random graphs with power law degree distributions, a popular model for real world graphs.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE 30th International Parallel and Distributed Processing Symposium, IPDPS 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2-11
Number of pages10
ISBN (Electronic)9781509021406
DOIs
StatePublished - Jul 18 2016
Externally publishedYes
Event30th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016 - Chicago, United States
Duration: May 23 2016May 27 2016

Publication series

NameProceedings - 2016 IEEE 30th International Parallel and Distributed Processing Symposium, IPDPS 2016

Conference

Conference30th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016
Country/TerritoryUnited States
CityChicago
Period5/23/165/27/16

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Keywords

  • Approximate counting
  • Motif counting
  • Parallel algorithm

Fingerprint

Dive into the research topics of 'Subgraph Counting: Color Coding beyond Trees'. Together they form a unique fingerprint.

Cite this