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.

本研究致力于解决社区检测中在可信核心结构遭受敌对攻击的问题，提出了第一个针对此情况的验证鲁棒性保证方法，并通过在多个真实世界图上的地面实验对方法进行了评估。