Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
- URL: http://arxiv.org/abs/2011.09841v1
- Date: Sun, 15 Nov 2020 16:14:14 GMT
- Title: Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
- Authors: Chen Lu, Subhabrata Sen
- Abstract summary: We study community detection in the contextual block model arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME].
- Score: 5.735930507508431
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We study community detection in the contextual stochastic block model
arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME]. In arXiv:1807.09596
[cs.SI], the second author studied this problem in the setting of sparse graphs
with high-dimensional node-covariates. Using the non-rigorous cavity method
from statistical physics, they conjectured the sharp limits for community
detection in this setting. Further, the information theoretic threshold was
verified, assuming that the average degree of the observed graph is large. It
is expected that the conjecture holds as soon as the average degree exceeds
one, so that the graph has a giant component. We establish this conjecture, and
characterize the sharp threshold for detection and weak recovery.
Related papers
- Minimax Rates for the Estimation of Eigenpairs of Weighted Laplace-Beltrami Operators on Manifolds [7.639886528552829]
We study the problem of estimating eigenpairs of elliptic differential operators from samples of a distribution $rho$ supported on a manifold $M$.<n>We find that eigenpairs of graph Laplacians induce regularity manifold estimators with an error of approximation that, up to logarithmic corrections, matches our lower bounds.
arXiv Detail & Related papers (2025-05-30T19:19:25Z) - Testing Dependency of Weighted Random Graphs [4.0554893636822]
We study the task of detecting the edge dependency between two random graphs.
For general edge-weight distributions, we establish thresholds at which optimal testing becomes information-theoretically possible or impossible.
arXiv Detail & Related papers (2024-09-23T10:07:41Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
We study a random graph model for small-world networks which are ubiquitous in social and biological sciences.
For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
arXiv Detail & Related papers (2024-02-01T03:39:01Z) - arXiv4TGC: Large-Scale Datasets for Temporal Graph Clustering [52.63652741011945]
We build arXiv4TGC, a set of novel academic datasets for temporal graph clustering.
In particular, the largest dataset, arXivLarge, contains 1.3 million labeled available nodes and 10 million temporal edges.
The clustering performance on arXiv4TGC can be more apparent for evaluating different models.
arXiv Detail & Related papers (2023-06-08T06:37:04Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
Block model is a canonical random graph model for clustering and community detection on network-structured data.
No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold.
We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
arXiv Detail & Related papers (2022-05-24T00:03:25Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm.
We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
arXiv Detail & Related papers (2021-12-29T18:46:52Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree.
In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z) - Statistical and computational thresholds for the planted $k$-densest
sub-hypergraph problem [13.808053718325635]
We consider the problem of recovery a planted $k$-densest sub-hypergraph on $d$-uniform hypergraphs.
This fundamental problem appears in different contexts, e.g., community detection, average-case complexity, and neuroscience applications.
arXiv Detail & Related papers (2020-11-23T16:02:12Z) - Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
We consider the block model where connection between vertices is perturbed by some latent (and unobserved) random geometric graph.
The objective is to prove that spectral methods are robust to this type of noise, even if they are agnostic to the presence (or not) of the random graph.
arXiv Detail & Related papers (2020-11-09T10:15:40Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
We introduce a novel learning problem for dense subgraph discovery.
We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability.
We then design a more scalable algorithm with a theoretical guarantee.
arXiv Detail & Related papers (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z)
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.