Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold
The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the recent years in sparser regimes. Yet, the current techniques still require diverging degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. This paper provides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-$k$ projection of a graphon in the $L_2$ metric if the top $k$ eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $n$ vertices. We present the first polyno…
Community DetectionStochastic Block ModelCommunity detection with the Bethe-Hessian
The Bethe-Hessian matrix, introduced by Saade, Krzakala, and Zdeborov\'a (2014), is a Hermitian matrix designed for applying spectral clustering algorithms to sparse networks. Rather than employing a non-symmetric and hi…
Community DetectionStochastic Block ModelSparse random hypergraphs: Non-backtracking spectra and community detection
We consider the community detection problem in a sparse $q$-uniform hypergraph $G$, assuming that $G$ is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the n…
Community DetectionDimensionality ReductionStochastic Block ModelRecovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E| \log^*|V|)$ Time
Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for oth…
Community DetectionStochastic Block ModelSemi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold
The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among whic…
ClusteringCommunity DetectionStochastic Block Model