Reliable Time Prediction in the Markov Stochastic Block Model
We introduce the Markov Stochastic Block Model (MSBM): a growth model for community based networks where node attributes are assigned through a Markovian dynamic. We rely on HMMs' literature to design prediction methods that are robust to local clustering errors. We focus specifically on the link prediction and collaborative filtering problems and we introduce a new model selection procedure to infer the number of hidden clusters in the network. Our approaches for reliable prediction in MSBMs are not algorithm-dependent in the sense that they can be applied using your favourite clustering tool. In this paper, we use a recent SDP method to infer the hidden communities and we provide theoretical guarantees. In particular, we identify the relevant signal-to-noise ratio (SNR) in our framework and we prove that the misclassification error decays exponentially fast with respect to this SNR.
Code (1)
Tasks
ClusteringCollaborative FilteringCommunity DetectionLink PredictionModel SelectionPredictionStochastic Block ModelSimilar Papers 제목 키워드 기반
High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time hig…
Matching and mixing: Matchability of graphs under Markovian error
We consider the problem of graph matching for a sequence of graphs generated under a time-dependent Markov chain noise model. Our edgelighter error model, a variant of the classical lamplighter random walk, iteratively c…
Graph MatchingScalable MCMC for Mixed Membership Stochastic Blockmodels
We propose a stochastic gradient Markov chain Monte Carlo (SG-MCMC) algorithm for scalable inference in mixed-membership stochastic blockmodels (MMSB). Our algorithm is based on the stochastic gradient Riemannian Langevi…
Variational InferenceEstimating the number of clusters of a Block Markov Chain
Clustering algorithms frequently require the number of clusters to be chosen in advance, but it is usually not clear how to do this. To tackle this challenge when clustering within sequential data, we present a method fo…
ClusteringStochastic Block ModelSolving Robust Markov Decision Processes: Generic, Reliable, Efficient
Markov decision processes (MDP) are a well-established model for sequential decision-making in the presence of probabilities. In robust MDP (RMDP), every action is associated with an uncertainty set of probability distri…
Decision MakingSequential Decision Making