Contextual Stochastic Block Models
We provide the first information theoretic tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our work bridges recent theoretical breakthroughs in the detection of latent community structure without nodes covariates and a large body of empirical work using diverse heuristics for combining node covariates with graphs for inference. The tightness of our analysis implies in particular, the information theoretical necessity of combining the different sources of information. Our analysis holds for networks of large degrees as well as for a Gaussian version of the model.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees
Real-world networks often come with side information that can help to improve the performance of network analysis tasks such as clustering. Despite a large number of empirical and theoretical studies conducted on network…
ClusteringStochastic Block ModelContextual Stochastic Block Model: Sharp Thresholds and Contiguity
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 gra…
Community DetectionmodelStochastic Block ModelOptimal Inference in Contextual Stochastic Block Models
The contextual stochastic block model (cSBM) was proposed for unsupervised community detection on attributed graphs where both the graph and the high-dimensional node information correlate with node labels. In the contex…
Community DetectionNode ClassificationStochastic Block ModelContextual Blocking Bandits
We study a novel variant of the multi-armed bandit problem, where at each time step, the player observes an independently sampled context that determines the arms' mean rewards. However, playing an arm blocks it (across …
BlockingNovel ConceptsRecommendation SystemsContextual Text Detection
Most existing scene text detectors focus on the detection of characters or words which capture partial textual messages only in most cases due to the missing of contextual information. For a better understanding of text …
Text Detection