Parallel Index-Based Structural Graph Clustering and Its Approximation
Parallel Index-Based Structural Graph Clustering and Its Approximation
复制标题
DOI：
10.1145/3448016.3457278
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Tom Tseng;Laxman Dhulipala;Julian Shun
中科院分区：
文献类型：
--
作者：
Tom Tseng;Laxman Dhulipala;Julian Shun
SCAN（Structural Clustering Algorithm for Networks）是一种研究得很好、应用广泛的图聚类算法。然而，对于大型图，顺序SCAN变体非常慢，并且并行SCAN变体不能在具有不同SCAN参数设置的查询之间有效地共享工作。由于SCAN的用户经常探索许多参数设置来找到好的聚类，因此值得预先计算一个索引来加速查询。本文在GS*-Index的基础上提出了一种实用的、可证明有效的并行索引SCAN算法。我们的并行算法通过使用整数排序改进了顺序算法的渐近工作。它也是高度并行的，实现了索引构建和聚类查询的对数跨度（并行时间）。此外，我们应用局部敏感哈希（LSH）设计一种新的近似SCAN算法，并证明其聚类行为的保证。我们提出了一个实验评估我们的算法在大型现实世界的图形。在一个48核的机器上，我们的并行索引结构实现了50- 151倍的加速比GS*-Index的建设。事实上，即使在单线程上，我们的索引构造算法也比GS*-Index快。我们的并行索引查询实现在一系列SCAN参数值上实现了GS*-Index查询的5- 32倍加速，并且我们的实现总是比ppSCAN（一种最先进的并行SCAN算法）更快。此外，我们的实验表明，应用LSH的结果在更快的索引建设，同时保持良好的聚类质量。
SCAN (Structural Clustering Algorithm for Networks) is a well-studied, widely used graph clustering algorithm. For large graphs, however, sequential SCAN variants are prohibitively slow, and parallel SCAN variants do not effectively share work among queries with different SCAN parameter settings. Since users of SCAN often explore many parameter settings to find good clusterings, it is worthwhile to precompute an index that speeds up queries. This paper presents a practical and provably efficient parallel index-based SCAN algorithm based on GS*-Index, a recent sequential algorithm. Our parallel algorithm improves upon the asymptotic work of the sequential algorithm by using integer sorting. It is also highly parallel, achieving logarithmic span (parallel time) for both index construction and clustering queries. Furthermore, we apply locality-sensitive hashing (LSH) to design a novel approximate SCAN algorithm and prove guarantees for its clustering behavior. We present an experimental evaluation of our algorithms on large real-world graphs. On a 48-core machine with two-way hyper-threading, our parallel index construction achieves 50--151× speedup over the construction of GS*-Index. In fact, even on a single thread, our index construction algorithm is faster than GS*-Index. Our parallel index query implementation achieves 5--32× speedup over GS*-Index queries across a range of SCAN parameter values, and our implementation is always faster than ppSCAN, a state-of-the-art parallel SCAN algorithm. Moreover, our experiments show that applying LSH results in faster index construction while maintaining good clustering quality.