Fast and Accurate Estimation of Typed Graphlets
Ryan A. Rossi, Anup B. Rao, Tung Mai, Nesreen K. Ahmed · Companion Proceedings of the Web Conference 2020 · 2020
Typed graphlets are small typed (labeled, colored) induced subgraphs and were recently shown to be the fundamental building blocks of rich complex heterogeneous networks. In many applications, speed is more important than accuracy, and it is sufficient to trade-off a tiny amount of accuracy for a significantly faster method. In this work, we propose fast and accurate estimators for typed graphlets. The typed graphlet estimation techniques naturally support general heterogeneous graphs with any arbitrary number of types, which include bipartite, k-partite, k-star, labeled graphs, and attributed networks as special cases. The experiments demonstrate the effectiveness of the typed graphlet estimation techniques.