论文标题
通过简洁的颜色编码和自适应抽样进行更快的图案计数
Faster motif counting via succinct color coding and adaptive sampling
论文作者
论文摘要
我们在大图中解决了计算诱导连接子图的分布，AKA \ emph {graphlets}或\ emph {motifs}的问题。当前的最新算法通过利用Alon，Yuster和Zwick的颜色编码技术来估计图案通过均匀采样来计数。在这项工作中，我们通过引入一组算法优化和技术来扩展这种方法的适用性，以降低颜色编码的运行时间和空间使用并提高计数的准确性。为此，我们首先展示了如何优化颜色编码以有效地构建输入图中所有图形的代表性子样本的紧凑表。对于$ 8 $ node图案，我们可以在一小时内用$ 65 $ M节点和$ 1.8 $ b的边缘建造这样的桌子，这比最新的状态大于2000美元。然后，我们引入了一种新颖的自适应采样方案，该方案打破了均匀采样的“加性误差屏障”，可以保证乘法近似而不是添加剂。这使我们不仅可以计算最频繁的图案，而且可以计算一个极为罕见的主题。例如，在一个图上，我们准确地计算了近10.000美元的$ 8 $ 8 $节点图案，其相对频率很小，以至于均匀的采样实际上将需要几个世纪的时间才能找到它们。我们的结果表明，颜色编码仍然是可扩展基序计数的最有希望的方法。
We address the problem of computing the distribution of induced connected subgraphs, aka \emph{graphlets} or \emph{motifs}, in large graphs. The current state-of-the-art algorithms estimate the motif counts via uniform sampling, by leveraging the color coding technique by Alon, Yuster and Zwick. In this work we extend the applicability of this approach, by introducing a set of algorithmic optimizations and techniques that reduce the running time and space usage of color coding and improve the accuracy of the counts. To this end, we first show how to optimize color coding to efficiently build a compact table of a representative subsample of all graphlets in the input graph. For $8$-node motifs, we can build such a table in one hour for a graph with $65$M nodes and $1.8$B edges, which is $2000$ times larger than the state of the art. We then introduce a novel adaptive sampling scheme that breaks the "additive error barrier" of uniform sampling, guaranteeing multiplicative approximations instead of just additive ones. This allows us to count not only the most frequent motifs, but also extremely rare ones. For instance, on one graph we accurately count nearly $10.000$ distinct $8$-node motifs whose relative frequency is so small that uniform sampling would literally take centuries to find them. Our results show that color coding is still the most promising approach to scalable motif counting.
