Community detection in censored hypergraph

• URL: http://arxiv.org/abs/2111.03179v1
• Date: Thu, 4 Nov 2021 22:03:20 GMT
• Title: Community detection in censored hypergraph
• Authors: Mingao Yuan, Bin Zhao, Xiaofeng Zhao
• Abstract summary: 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.
• Score: 8.790193989856403
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community detection refers to the problem of clustering the nodes of a network (either graph or hypergrah) into groups. Various algorithms are available for community detection and all these methods apply to uncensored networks. In practice, a network may has censored (or missing) values and it is shown that censored values have non-negligible effect on the structural properties of a network. In this paper, we study community detection in censored $m$-uniform hypergraph from information-theoretic point of view. We derive the information-theoretic threshold for exact recovery of the community structure. Besides, we propose a polynomial-time algorithm to exactly recover the community structure up to the threshold. The proposed algorithm consists of a spectral algorithm plus a refinement step. It is also interesting to study whether a single spectral algorithm without refinement achieves the threshold. To this end, we also explore the semi-definite relaxation algorithm and analyze its performance.

Related papers

• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
  We study a semi-supervised community detection problem in which the objective is to estimate the community label of a new node. We propose an algorithm that computes a structural similarity metric' between the new node and each of the $K$ communities. Our findings highlight, to the best of our knowledge, the first semi-supervised community detection algorithm that offers theoretical guarantees.
  arXiv  Detail & Related papers  (2023-06-01T19:02:50Z)
• ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness [70.60721571429784]
  We propose a new graph anomaly detection framework on attributed networks via substructure awareness (ARISE) ARISE focuses on the substructures in the graph to discern abnormalities. Experiments show that ARISE greatly improves detection performance compared to state-of-the-art attributed networks anomaly detection (ANAD) algorithms.
  arXiv  Detail & Related papers  (2022-11-28T12:17:40Z)
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection [0.0]
  Community detection aims to partition a network into clusters of nodes to summarize its large-scale structure. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model. Other methods are descriptive, dividing a network according to an objective motivated by a particular application. We present a solution that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model.
  arXiv  Detail & Related papers  (2022-10-17T15:38:41Z)
• A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
  We assess the empirical robustness of node embedding models to random and adversarial poisoning attacks. We compare edge addition, deletion and rewiring strategies computed using network properties as well as node labels. We found that node classification suffers from higher performance degradation as opposed to network reconstruction.
  arXiv  Detail & Related papers  (2022-09-16T17:20:23Z)
• Community-based anomaly detection using spectral graph filtering [2.320417845168326]
  This paper proposes a community-based anomaly detection algorithm using a spectral graph-based filter. In computational experiments, the proposed strategy, called SpecF, showed an outstanding performance in successfully identifying even discrete anomalies. We present a case study to validate the proposed method to study the dissemination of COVID-19 in the different districts of Sao Jos'e dos Campos, Brazil.
  arXiv  Detail & Related papers  (2022-01-24T20:02:22Z)
• Overlapping community detection in networks via sparse spectral decomposition [1.0660480034605242]
  We consider the problem of estimating overlapping community memberships in a network, where each node can belong to multiple communities. Our algorithm is based on sparse principal subspace estimation with iterative thresholding. We show that a fixed point of the algorithm corresponds to correct node memberships under a version of the block model.
  arXiv  Detail & Related papers  (2020-09-20T07:31:09Z)
• 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)
• Community detection in networks using graph embeddings [0.615738282053772]
  We test the ability of several graph embedding techniques to detect communities on benchmark graphs. We find that the performance is comparable, if the parameters of the embedding techniques are suitably chosen. This finding, along with the high computational cost of embedding a network and grouping the points, suggests that, for community detection, current embedding techniques do not represent an improvement over network clustering algorithms.
  arXiv  Detail & Related papers  (2020-09-11T07:49:21Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)
• Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing [81.71105567425275]
  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.
  arXiv  Detail & Related papers  (2020-02-09T18:39:39Z)

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.