自动学习图结构选择最优社区划分尺度,无需人工调参。
Robust Markov stability for community detection at a scale learned based on the structure
- 结合马尔可夫稳定性与预训练梯度提升模型自动选尺度
- 在10000个基准网络上训练,预测最优划分尺度
- 无需用户输入,结果比25种算法更优,适合各类图数据
社区检测是将图中节点聚类的无监督任务,广泛应用在多个领域。传统单尺度方法常难以获得鲁棒且合适的划分结果。现有算法PyGenStability通过优化多尺度马尔可夫稳定性函数,生成多个鲁棒划分,但当用户无法预知合适尺度时,缺乏系统方法从中选出最佳划分。本文提出的方法将马尔可夫稳定性框架与预训练机器学习模型结合,基于图结构自动选择合适尺度,获得一个鲁棒的单一分区。该尺度选择采用在10,000个基准网络上训练的梯度提升模型,使用手工特征与嵌入特征预测使输出划分最接近真实划分的尺度值。结合此方法的PyGenStabilityOne(PO)是一个无需超参数、无需用户干预的多尺度社区检测算法。与29种算法对比显示,PO在统计上显著优于25种方法,为社区检测算法选择提供了可靠基准,其准确、鲁棒且免调参的特点突出。
原文摘要 · Abstract (English)
Community detection, the unsupervised task of clustering nodes of a graph, finds applications across various fields. The common approaches for community detection involve optimizing an objective function to partition the nodes into communities at a single scale of granularity. However, the single-scale approaches often fall short of producing partitions that are robust and at a suitable scale. The existing algorithm, PyGenStability, returns multiple robust partitions for a network by optimizing the multi-scale Markov stability function. However, in cases where the suitable scale is not known or assumed by the user, there is no principled method to select a single robust partition at a suitable scale from the multiple partitions that PyGenStability produces. Our proposed method combines the Markov stability framework with a pre-trained machine learning model for scale selection to obtain one robust partition at a scale that is learned based on the graph structure. This automatic scale selection involves using a gradient boosting model pre-trained on hand-crafted and embedding-based network features from a labeled dataset of 10k benchmark networks. This model was trained to predicts the scale value that maximizes the similarity of the output partition to the planted partition of the benchmark network. Combining our scale selection algorithm with the PyGenStability algorithm results in PyGenStabilityOne (PO): a hyperparameter-free multi-scale community detection algorithm that returns one robust partition at a suitable scale without the need for any assumptions, input, or tweaking from the user. We compare the performance of PO against 29 algorithms and show that it outperforms 25 other algorithms by statistically meaningful margins. Our results facilitate choosing between community detection algorithms, among which PO stands out as the accurate, robust, and hyperparameter-free method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。