Spectral Algorithms Optimally Recover Planted Sub-structures
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Previous works by Abbe, Fan, Wang and Zhong (2020) and by Dhara, Gaudio, Mossel and Sandon (2022) showed the optimality for community detection in the Stochastic Block Model (SBM), as well as in a censored variant of the SBM. Here we show that this optimality is somewhat universal as it carries over to other planted substructures such as the planted dense subgraph problem and submatrix localization problem, as well as to a censored version of the planted dense subgraph problem.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. …
Tensor DecompositionTensor Clustering with Planted Structures: Statistical Optimality and Computational Limits
This paper studies the statistical and computational limits of high-order clustering with planted structures. We focus on two clustering models, constant high-order clustering (CHC) and rank-one higher-order clustering (…
ClusteringOptimal Spectral Recovery of a Planted Vector in a Subspace
Recovering a planted vector $v$ in an $n$-dimensional random subspace of $\mathbb{R}^N$ is a generic task related to many problems in machine learning and statistics, such as dictionary learning, subspace recovery, princ…
Dictionary LearningPlanted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
Multiple methods of finding the vertices belonging to a planted dense subgraph in a random dense $G(n, p)$ graph have been proposed, with an emphasis on planted cliques. Such methods can identify the planted subgraph in …
Graph Neural NetworkPAC learningStrong Consistency, Graph Laplacians, and the Stochastic Block Model
Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stocha…
ClusteringCommunity DetectionStochastic Block Model