Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing
Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing
复制标题
DOI：
10.1145/3366423.3380029
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Jinyuan Jia;Binghui Wang;Xiaoyu Cao;N. Gong
中科院分区：
文献类型：
--
作者：
Jinyuan Jia;Binghui Wang;Xiaoyu Cao;N. Gong
社区检测在理解图结构中起着关键作用。然而，最近的几项研究表明，社区检测容易受到对抗性结构扰动的影响。特别是，通过在图中添加或删除少量精心选择的边，攻击者可以操纵检测到的社区。然而，据我们所知，没有研究证明社区检测对这种对抗性结构扰动的鲁棒性。在这项工作中，我们的目标是弥合这一差距。具体来说，我们开发了第一个经过认证的社区检测对对抗性结构扰动的鲁棒性保证。在给定任意社团检测方法的基础上，通过随机扰动图的结构，建立了一种新的平滑社团检测方法。我们从理论上表明，平滑社区检测方法可证明组一个给定的任意一组节点到同一个社区（或不同的社区）时，由攻击者添加/删除的边缘的数量是有界的。此外，我们证明了我们的认证的鲁棒性是紧密的。我们还在多个真实世界的图形与地面真实社区上实证评估了我们的方法。
Community detection plays a key role in understanding graph structure. However, several recent studies showed that community detection is vulnerable to adversarial structural perturbation. In particular, via adding or removing a small number of carefully selected edges in a graph, an attacker can manipulate the detected communities. However, to the best of our knowledge, there are no studies on certifying robustness of community detection against such adversarial structural perturbation. In this work, we aim to bridge this gap. Specifically, we develop the first certified robustness guarantee of community detection against adversarial structural perturbation. Given an arbitrary community detection method, we build a new smoothed community detection method via randomly perturbing the graph structure. We theoretically show that the smoothed community detection method provably groups a given arbitrary set of nodes into the same community (or different communities) when the number of edges added/removed by an attacker is bounded. Moreover, we show that our certified robustness is tight. We also empirically evaluate our method on multiple real-world graphs with ground truth communities.