Tiered Sampling: An Efficient Method for Counting Sparse Motifs in Massive Graph Streams
Tiered Sampling: An Efficient Method for Counting Sparse Motifs in Massive Graph Streams
复制标题
分层采样：一种计算海量图流中稀疏图案的有效方法
DOI：
10.1145/3441299
复制
发表时间：
2021
影响因子：
3.6
通讯作者：
Upfal, Eli
中科院分区：
文献类型：
--
作者：
Stefani, Lorenzo De;Terolli, Erisa;Upfal, Eli
我们介绍了分层采样，一种新的技术，用于估计稀疏图案的计数在大规模的图形，其边缘观察到的流。我们的技术只需要一个单一的数据通过，并使用固定的大小M，这可以是幅度小于边的数量的内存。我们的方法解决了具有挑战性的任务，计数稀疏图案子图模式，有一个低概率出现在一个样本ofMedges在图中，这是最大的数据量可用于算法在每一步。为了获得计数的无偏和低方差估计，我们将可用内存划分为储层样本的层（层）。虽然基础层是边缘的标准储集层样本，但其他层是所需基序的子结构的储集层样本。通过存储更多的频繁子结构的主题，我们增加了概率检测到的稀疏主题，我们正在计数的出现，从而减少方差和误差的估计。虽然我们专注于设计和分析的算法，用于计数4-团，我们提出了一种方法，它允许generalizingTiered Sampling获得高质量的估计出现的任何子图的兴趣，同时由于感兴趣的模式的特定属性减少了分析工作。我们提出了一个完整的分析分析和广泛的实验评估，我们提出的方法使用合成和真实世界的数据。我们的研究结果表明，我们的方法在获得高质量的近似的4和5团的大型图形使用非常有限的内存量，显着优于单边样本方法计数稀疏图案在大规模的图形。
We introduceTiered Sampling, a novel technique for estimating the count of sparse motifs in massive graphs whose edges are observed in a stream. Our technique requires only a single pass on the data and uses a memory of fixed sizeM, which can be magnitudes smaller than the number of edges.Our methods address the challenging task of counting sparse motifs—sub-graph patterns—that have a low probability of appearing in a sample ofMedges in the graph, which is the maximum amount of data available to the algorithms in each step. To obtain an unbiased and low variance estimate of the count, we partition the available memory into tiers (layers) of reservoir samples. While the base layer is a standard reservoir sample of edges, other layers are reservoir samples of sub-structures of the desired motif. By storing more frequent sub-structures of the motif, we increase the probability of detecting an occurrence of the sparse motif we are counting, thus decreasing the variance and error of the estimate.While we focus on the designing and analysis of algorithms for counting 4-cliques, we present a method which allows generalizingTiered Samplingto obtain high-quality estimates for the number of occurrence of any sub-graph of interest, while reducing the analysis effort due to specific properties of the pattern of interest.We present a complete analytical analysis and extensive experimental evaluation of our proposed method using both synthetic and real-world data. Our results demonstrate the advantage of our method in obtaining high-quality approximations for the number of 4 and 5-cliques for large graphs using a very limited amount of memory, significantly outperforming the single edge sample approach for counting sparse motifs in large scale graphs.