Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing

• URL: http://arxiv.org/abs/2002.03421v2
• Date: Tue, 15 Sep 2020 01:58:17 GMT
• Title: Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing
• Authors: Jinyuan Jia, Binghui Wang, Xiaoyu Cao, Neil Zhenqiang Gong
• Abstract summary: We develop the first certified robustness guarantee of community detection against adversarial structural perturbation. We theoretically show that the smoothed community detection method provably groups a given arbitrary set of nodes into the same community. We also empirically evaluate our method on multiple real-world graphs with ground truth communities.
• Score: 81.71105567425275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Private Online Community Detection for Censored Block Models [60.039026645807326]
  We study the private online change detection problem for dynamic communities, using a censored block model (CBM) We propose an algorithm capable of identifying changes in the community structure, while maintaining user privacy.
  arXiv  Detail & Related papers  (2024-05-09T12:35:57Z)
• Evading Community Detection via Counterfactual Neighborhood Search [10.990525728657747]
  Community detection is useful for social media platforms to discover tightly connected groups of users who share common interests. Some users may wish to preserve their anonymity and opt out of community detection for various reasons, such as affiliation with political or religious organizations, without leaving the platform. In this study, we address the challenge of community membership hiding, which involves strategically altering the structural properties of a network graph to prevent one or more nodes from being identified by a given community detection algorithm.
  arXiv  Detail & Related papers  (2023-10-13T07:30:50Z)
• A Comprehensive Review of Community Detection in Graphs [10.683947241960178]
  The study of complex networks has significantly advanced our understanding of community structures. Detecting communities in graphs is a challenging problem with applications in sociology, biology, and computer science. This review article delves into the topic of community detection in graphs, which serves as a thorough exposition of various community detection methods.
  arXiv  Detail & Related papers  (2023-09-21T06:04:06Z)
• Spatial-Frequency Discriminability for Revealing Adversarial Perturbations [53.279716307171604]
  Vulnerability of deep neural networks to adversarial perturbations has been widely perceived in the computer vision community. Current algorithms typically detect adversarial patterns through discriminative decomposition for natural and adversarial data. We propose a discriminative detector relying on a spatial-frequency Krawtchouk decomposition.
  arXiv  Detail & Related papers  (2023-05-18T10:18:59Z)
• Uncovering the Local Hidden Community Structure in Social Networks [20.467702194064525]
  We propose a new method that detects and boosts each layer iteratively on a subgraph sampled from the original network. We theoretically show that our method can avoid some situations that a broken community and the local community are regarded as one community in the subgraph.
  arXiv  Detail & Related papers  (2021-12-08T04:07:19Z)
• Self-Supervised Predictive Convolutional Attentive Block for Anomaly Detection [97.93062818228015]
  We propose to integrate the reconstruction-based functionality into a novel self-supervised predictive architectural building block. Our block is equipped with a loss that minimizes the reconstruction error with respect to the masked area in the receptive field. We demonstrate the generality of our block by integrating it into several state-of-the-art frameworks for anomaly detection on image and video.
  arXiv  Detail & Related papers  (2021-11-17T13:30:31Z)
• Community detection in censored hypergraph [8.790193989856403]
  We study community detection in censored $m$-uniform hypergraph from information-theoretic point of view. We propose a spectral-time algorithm to exactly recover the community structure up to the threshold. It is also interesting to study whether a single spectral algorithm without refinement the threshold.
  arXiv  Detail & Related papers  (2021-11-04T22:03:20Z)
• Hide and Seek: Outwitting Community Detection Algorithms [17.144388833011536]
  Community affiliation plays an important role in determining a node's contextual position in a network. This study focuses on hiding such sensitive communities so that the community affiliation of the targeted nodes can be concealed. We introduce NEURAL, a novel method that greedily optimize a node-centric objective function to determine the rewiring strategy.
  arXiv  Detail & Related papers  (2021-02-22T03:50:44Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  We study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection. We also check the performance impact of network prunings as an ancillary tactic to make hierarchical community detection more efficient.
  arXiv  Detail & Related papers  (2020-09-15T00:16:12Z)
• Adversarial Attack on Community Detection by Hiding Individuals [68.76889102470203]
  We focus on black-box attack and aim to hide targeted individuals from the detection of deep graph community detection models. We propose an iterative learning framework that takes turns to update two modules: one working as the constrained graph generator and the other as the surrogate community detection model.
  arXiv  Detail & Related papers  (2020-01-22T09:50:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.