论文标题
通过随机平滑进行对抗结构扰动的社区检测的认证鲁棒性
Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing
论文作者
论文摘要
社区检测在理解图形结构中起关键作用。但是，最近的一些研究表明，社区检测容易受到对抗结构扰动的影响。特别是，通过在图中添加或删除少量精心选择的边缘，攻击者可以操纵被检测到的社区。但是，据我们所知，尚无关于证明对这种对抗性结构扰动的鲁棒性的研究。在这项工作中，我们旨在弥合这一差距。具体而言，我们为对抗性结构扰动的社区检测提供了第一个认证的鲁棒性保证。给定一种任意的社区检测方法，我们通过随机扰动图形结构来构建一种新的平滑社区检测方法。从理论上讲，当攻击者添加/删除的边数时，我们从理论上表明，平滑的社区检测方法可证明将给定的任意节点集成到同一社区（或不同的社区）。此外，我们证明我们的认证鲁棒性很紧。我们还通过凭经验评估了与地面真相社区的多个现实图表的方法。
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.
