Application-specific graph sampling for frequent subgraph mining and community detection
Application-specific graph sampling for frequent subgraph mining and community detection
复制标题
DOI：
10.1109/bigdata.2017.8258022
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Sumit Purohit;Sutanay Choudhury;L. Holder
中科院分区：
文献类型：
--
作者：
Sumit Purohit;Sutanay Choudhury;L. Holder
图挖掘是一种重要的数据分析方法，但随着输入图大小的增加而挣扎。如此大的图所带来的可扩展性和可用性挑战使得对输入图进行采样并减小其大小势在必行。采样中的关键挑战是确定适当的算法，以确保所得到的分析不会受到数据减少的严重影响。预测给定图和采样算法的预期性能下降也是有用的。在本文中，我们提出了不同的采样方法，如频繁子图挖掘（FSM）和社区检测（CD）的图挖掘应用程序。我们探讨了图的度量，如PageRank，三角形，多样性的样本图，并得出结论，对于异构图三角形和多样性比度为基础的指标表现更好。我们还提出了两个新的采样变化的目标图挖掘应用程序。我们目前的实证结果表明，知识的目标应用程序，沿着与输入图形的属性，可以用来选择最好的采样算法。我们还得出结论，性能下降是一个突然的，而不是渐进的现象，随着样本量的减少。我们提出的实证结果表明，性能下降遵循逻辑函数。原始数据集、采样算法的实施和结果可在线获取。1
Graph mining is an important data analysis methodology, but struggles as the input graph size increases. The scalability and usability challenges posed by such large graphs make it imperative to sample the input graph and reduce its size. The critical challenge in sampling is to identify the appropriate algorithm to insure the resulting analysis does not suffer heavily from the data reduction. Predicting the expected performance degradation for a given graph and sampling algorithm is also useful. In this paper, we present different sampling approaches for graph mining applications such as Frequent Subgrpah Mining (FSM), and Community Detection (CD). We explore graph metrics such as PageRank, Triangles, and Diversity to sample a graph and conclude that for heterogeneous graphs Triangles and Diversity perform better than degree based metrics. We also present two new sampling variations for targeted graph mining applications. We present empirical results to show that knowledge of the target application, along with input graph properties can be used to select the best sampling algorithm. We also conclude that performance degradation is an abrupt, rather than gradual phenomena, as the sample size decreases. We present the empirical results to show that the performance degradation follows a logistic function. Original Datasets, implementation of sampling algorithms, and results are available online.1