通过子图搜索实现鲁棒社区发现与异常节点识别
SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search
- 在子图空间中寻找符合模型假设的结构以估计参数
- 可在真实复杂网络中准确恢复社区结构并定位异常节点
- 适合处理偏离理想模型的现实图数据，如社交或生物网络
社区发现是图分析中的基础任务，现有方法常依赖于随机块模型（SBM）拟合观测网络。然而，真实图数据很少严格服从理想化的模型假设，因此鲁棒算法至关重要——即使数据偏离分布也能恢复模型参数。本文提出SubSearch，通过在子图空间中搜索与模型假设高度一致的子结构，实现对SBM参数的鲁棒估计。该方法同时具备异常检测能力，可精准识别导致图偏离模型的异常节点，超越了简单删去高连接度节点等传统手段。在合成数据和真实世界数据集上的大量实验验证了其有效性。
原文摘要 · Abstract (English)
Community detection is a fundamental task in graph analysis, with methods often relying on fitting models like the Stochastic Block Model (SBM) to observed networks. While many algorithms can accurately estimate SBM parameters when the input graph is a perfect sample from the model, real-world graphs rarely conform to such idealized assumptions. Therefore, robust algorithms are crucial-ones that can recover model parameters even when the data deviates from the assumed distribution. In this work, we propose SubSearch, an algorithm for robustly estimating SBM parameters by exploring the space of subgraphs in search of one that closely aligns with the model's assumptions. Our approach also functions as an outlier detection method, properly identifying nodes responsible for the graph's deviation from the model and going beyond simple techniques like pruning high-degree nodes. Extensive experiments on both synthetic and real-world datasets demonstrate the effectiveness of our method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。