Semi-supervised Community Detection via Structural Similarity Metrics
- URL: http://arxiv.org/abs/2306.01089v1
- Date: Thu, 1 Jun 2023 19:02:50 GMT
- Title: Semi-supervised Community Detection via Structural Similarity Metrics
- Authors: Yicong Jiang, Tracy Ke
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by social network analysis and network-based recommendation
systems, we study a semi-supervised community detection problem in which the
objective is to estimate the community label of a new node using the network
topology and partially observed community labels of existing nodes. The network
is modeled using a degree-corrected stochastic block model, which allows for
severe degree heterogeneity and potentially non-assortative communities. We
propose an algorithm that computes a `structural similarity metric' between the
new node and each of the $K$ communities by aggregating labeled and unlabeled
data. The estimated label of the new node corresponds to the value of $k$ that
maximizes this similarity metric. Our method is fast and numerically
outperforms existing semi-supervised algorithms. Theoretically, we derive
explicit bounds for the misclassification error and show the efficiency of our
method by comparing it with an ideal classifier. Our findings highlight, to the
best of our knowledge, the first semi-supervised community detection algorithm
that offers theoretical guarantees.
Related papers
- Enhancing Community Detection in Networks: A Comparative Analysis of Local Metrics and Hierarchical Algorithms [49.1574468325115]
This study employs the same method to evaluate the relevance of using local similarity metrics for community detection.
The efficacy of these metrics was evaluated by applying the base algorithm to several real networks with varying community sizes.
arXiv Detail & Related papers (2024-08-17T02:17:09Z) - Uncertainty in GNN Learning Evaluations: The Importance of a Consistent
Benchmark for Community Detection [4.358468367889626]
We propose a framework to establish a common evaluation protocol for Graph Neural Networks (GNNs)
We motivate and justify it by demonstrating the differences with and without the protocol.
We find that by ensuring the same evaluation criteria is followed, there may be significant differences from the reported performance of methods at this task.
arXiv Detail & Related papers (2023-05-10T10:22:28Z) - 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) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN)
In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries.
By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
arXiv Detail & Related papers (2022-06-06T14:26:34Z) - Robustness Certificates for Implicit Neural Networks: A Mixed Monotone
Contractive Approach [60.67748036747221]
Implicit neural networks offer competitive performance and reduced memory consumption.
They can remain brittle with respect to input adversarial perturbations.
This paper proposes a theoretical and computational framework for robustness verification of implicit neural networks.
arXiv Detail & Related papers (2021-12-10T03:08:55Z) - 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) - 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)
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.