Optimal 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 context of machine learning on graphs, the cSBM has been widely used as a synthetic dataset for evaluating the performance of graph-neural networks (GNNs) for semi-supervised node classification. We consider a probabilistic Bayes-optimal formulation of the inference problem and we derive a belief-propagation-based algorithm for the semi-supervised cSBM; we conjecture it is optimal in the considered setting and we provide its implementation. We show that there can be a considerable gap between the accuracy reached by this algorithm and the performance of the GNN architectures proposed in the literature. This suggests that the cSBM, along with the comparison to the performance of the optimal algorithm, readily accessible via our implementation, can be instrumental in the development of more performant GNN architectures.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionNode ClassificationStochastic Block ModelSimilar 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 ModelOptimality of variational inference for stochasticblock model with missing links
Variational methods are extremely popular in the analysis of network data. Statistical guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters…
parameter estimationStochastic Block ModelVariational InferenceStatistical Inference for Weighted Sample Average Approximation in Contextual Stochastic Optimization
Contextual stochastic optimization provides a framework for decision-making under uncertainty incorporating observable contextual information through covariates. We analyze statistical inference for weighted sample avera…
Decision MakingDecision Making Under UncertaintyStochastic OptimizationvalidOnline Statistical Inference for Contextual Bandits via Stochastic Gradient Descent
With the fast development of big data, it has been easier than before to learn the optimal decision rule by updating the decision rule recursively and making online decisions. We study the online statistical inference of…
Decision MakingMulti-Armed BanditsSequential Decision MakingEfficient inference in stochastic block models with vertex labels
We study the stochastic block model with two communities where vertices contain side information in the form of a vertex label. These vertex labels may have arbitrary label distributions, depending on the community membe…
Stochastic Block Model