Estimation of Graphlet Counts in Massive Networks

IEEE Transactions on Neural Networks and Learning Systems (TNNLS)

Publication date: January 1, 2019

Ryan A. Rossi, Rong Zhou, Nesreen K. Ahmed

Graphlets are induced subgraphs of a large network and are important for understanding and modeling complex networks. Despite their practical importance, graphlets have been severely limited to applications and domains with relatively small graphs. Most previous work has focused on exact algorithms, however, it is often too expensive to compute graphlets exactly in massive networks with billions of edges, and finding an approximate count is usually sufficient for many applications. In this work, we propose an unbiased graphlet estimation framework that is (a) fast with large speedups compared to the state-of-the-art, (b) parallel with nearly linear-speedups, (c) accurate with less than 1% relative error, (d) scalable and space-efficient for massive networks with billions of edges, and (e) effective for a variety of real-world settings, as well as estimating global and local graphlet statistics (e.g., counts). On 300 networks from 20 domains, we obtain <1% relative error for all graphlets. This is vastly more accurate than existing methods while using less data. Moreover, it takes a few seconds on billion edge graphs (as opposed to days/weeks). These are by far the largest graphlet computations to date.

Research Area:  Adobe Research iconAI & Machine Learning