Scalable MCMC for Mixed Membership Stochastic Blockmodels

이번 대학원 '베이지안 통계학' 수업에서 기말 프로젝트로 'Scalable MCMC for Mixed Membership Stochastic Blockmodels' 논문 발표를 맡게 되었다. 주 연구 주제인 Graph를 bayesian 접근으로 modeling을 한 논문이다. 

 

'Bayesian Graph Convolutional Neural Networks for semi-supervised classification'의 논문에 따르면, 기존 Graph Convolution Neural Network(GCN) 모델은 graph structure에 대한 uncertainty(불확실성)을 잘 다루지 못 한다는 한계점이 존재한다. 예를 들어, graph에 noisy data(-> spurious edges 존재 또는 실제로는 매우 강한 relationship를 가지고 있는데 edge가 존재하지 않는 경우)가 존재할 수 있다. 따라서,이 논문에서는 observed graph를 통해 a parametric family of random graph를 생성했다. a parametric family of random graph modeling 및 update는 Assortative Mixed Membership Stochastic Blockmodels(a-MMSB)와 Stochastic Gradient Markov Chain Monte Carlo(SG-MCMC) 방법을 통해 가능하다. a-MMSB를 SG-MCMC를 통해 update하는 과정을 제안한 논문이 'Scalable MCMC for Mixed Membership Stochastic Blockmodels'이다. 이제 이 논문을 통해 공부한 내용을 정리해 보고자 한다.

 

 1. Introduction

Probabilistic Graphical Models(Bayesian Graphical Models)는 매우 큰 수의 random variable 사이의 복잡한 relationship를 modeling하는데 편리하다. prior distribution을 정의하고 posterior distribution을 추론함으로써 model의 uncertainty를 고려할 수 있다. Bayesian Graphical Models의 큰 하위 클래스로 Latent Dirichlet Allocation(LDA)와 같은 topic model이 있다. 그렇다면, 과연 이 모델들 및 추론 과정에서 "big data"의 경우, 과연 잘 다룰 수 있는가? "big data"를 잘 다룰 수 있는 효율적인 알고리즘이  존재한다. Stochastic Variational Bayesian Inference(SVB)와 Stochastic Gradient Markov Chain Monte Carlo(SG-MCMC)이다. 이 두 가지 알고리즘은 모든 데이터를 다 사용하지 않고 데이터의 일부만 사용해 학습한다. 

"big data"의 가장 큰 클래스는 network이다. 예를 들어, social network의 경우, billions of edges와 tens of millions of nodes가 존재한다. 이 영역에서 가장 흥미로운 관점은 the discovery of communities densely connected groups of nodes(node들 사이의 community 발견)이다. community를 모델하는 대표적인 모델이 Mixed Membership Stochastic Blockmodel(MMSB)이다.

이 논문의 목적은 LDA에 SVB와 SG-MCMC를 적용한 것처럼 a-MMSB에 SVB와 SG-MCMC 알고리즘을 적용하는 것이다. SG-MCMC가 SVB보다 더 정확하고 속도가 빠르다고 한다.

 

 2. Assortative Mixed-Membership Stochastic Blockmodels(a-MMSB)

a-MMSB는 상대적으로 strong community를 가진 graph를 형성해준다. a-MMSB는 n개의 node를 가진  graph structure를 모델링하는 MMSB의 특수한 형태이다.

a-MMSB는 다음과 같은 가정을 한다.

즉, 각 node는 community set K인 k 차원의 확률 분포를 가진다. 각 node가 block(community, category)에 속할 확률분포이다. 만약, node a와 node b가 같은 community에 속할 경우, 두 node가 significantly 연결될 가능성(확률) 값이 존재한다.

다음은 a-MMSB의 algorithm이다.

위의 process에 대한 joint distribution(결합 확률분포)는 다음과 같다.

• 배타분포 = 0~1 사이의 값을 가지는 단일(univariate) 확률변수의 모형에 사용 → B_k ~ Beta(n)로 B_K는 probability
• 디리클레분포 : 0~1 사이의 값을 가지는 다변수(multivariate) 확률변수의 모형에 사용 → k개의 community에 속할 확률을 추정하는데 사용

우리가 추정해야 하는 모수는 beta와 pi이다. bayesian에서 모수를 추정하는 대표적인 방법으로 variational inference와 collapsed Gibbs Sampling algorithms이다. 하지만, 이 알고리즘들은 작은 규모의 데이터에서는 성공적으로 작동하지만, 큰 규모의 데이터인 경우 계산 속도 측면에서 효율적이지 않다. 이에 대한 해결방안으로 제시한게 Stochastic Variational Algorithm이다. SVB는 매 iteration마다 모든 node를 사용하지 않고 특정 node들만 사용해서 update한다.

 

 3. Stochastic Gradient MCMC Algorithms

논문에서 제시하는 알고리즘은 Stochastic Gradient Langevin Dynamics(SGLD)이다.

 

<SGLD의 definition>

Stochastic Gradient Langevin Dynamics(SGLD): optimization and sampling technique composed of characteristics from Stochastic Gradient Descent, a Robbins-Monro optimization algorithm, and Langevin dynamics, a mathematical extension of molecular dynamics models.

결국에는, SGLD는 optimization 및 sampling technique을 하는 알고리즘이다.

 

<Stochastic Gradient Descent(SGD)와의 공통점>

• SGLD는 SGD처럼 매 iteration마다 stochastic gradient estimator를 생성하는데 mini-batch만 사용한다.

 

<Stochastic Gradient Desent(SGD)와의 차이점>

• SGLD는 sampling 방법으로 Bayesian Learning을 사용할 수 있다.

 

<Langevin Dynamics와의 공통점>

• SGLD는 Langevin Dynamics와 같이 posterior distribution으로부터 sampling한다.

<Langevin Dynamics와의 차이점>

• likelihood gradient 부분에서 모든 데이터를 사용하는 것이 아닌 SGD처럼 mini-batch를 사용한다.

다음은 논문에서 제시한 SGLD update rule이다.

SGLD에서는 Metropolis-Hastings(MH) accept-regect test를 하지 않으며 Langevin Monte Carlo는 모든 node를 다 사용하기 때문에 수렴 속도가 O(N)인 반면, SGLD는 모든 node를 사용하지 않고 mini-batch D_n에 속하는 node만을 가지고 update하기 때문에 수렴 속도가 O(n)으로 LMC보다 수렴 속도가 더 빠르다.

 

이 논문에서 최종적으로 사용하는 update rule은 Stochastic Gradient Riemannain Langevin Dynamics(SGRLD)이다.

SGRLD는 SGLD의 하위클래스로 probability simplex로부터 sampling할 때 사용하는 알고리즘이다.

probability simplex는 standard simplex라고도 하며 디리클레 분포를 공부할 때 종종 보게 되는 단어이다. 정의는 다음과 같다.

probability simplex를 parameterise하는데는 다양한 방법이 있다. Reduced Mean, Expected Mean, Reduced Mean, Expanded Mean이 있다.

여기 논문에서는 expanded mean 방법을 사용했다.

 4. Scalable MCMC for a-MMSB

앞에서 말했듯이 우리가 추정해야 하는 모수는 2가지이다. local parameter인 pi와 global인 parameter인 beta이다. 두 모수 모두 probability simplex 공간 상에 있다. 따라서, SGRLD를 이용하며 더 효율적인 계산을 위해 계속해서 변형해 나갈 것이다.

4.1 Sampling the global parameter

 

• The expectation is w.r.t the posterior distribution of latent variables.
• computing the noramlization constant(Z_ab) -> can be redued O(K) computation

<Update rule for the global parameter>

Stratified sampling 방법으로 node pair를 sampling한다 했는데, Stratified Sampling에 대한 설명을 해보고자 한다.

데이터에는 노드와 연결된 edge의 수가 연결되지 않는 edge의 수다 훨씬 적다. (-> The number of links is much samaller than that of non-links). 이에 대하여 stratified sampling을 사용함으로써 gradient의 variance를 줄일 수 있다. random하게 선택된 node a로부터 link edge를 sampling할 지, non-link edge를 sampling할 지 0.5의 확률로 결정한다.

만약, node a로부터 link edge를 sampling할 경우에는 모든 link-edge를 sampling하는 반면, non-link edge를 sampling 할 경우에는 N/m만큼만 sampling한다. 

 

4.2 Sampling the local parameter

 

4.3 Scalable local updates for a large number of communities.

local update에서 만약, community의 수가 큰 경우, k가 큰 경우, 수렴 속도가 O(K|V_n|)으로 매우 비효율적이다. 해결방아능로 community를 3개의 집단으로 분리하는 것을 제안한다. -> the activate set, the candiate set, the bulk set.

3개의 집단으로 분리한 근거에는 2가지가 존재한다. 첫번째 이유는 sparsity이다. k가 매우 큰 경우, 한 node가 각 k번째 communtiy에 속할 확률 값이 매우 낮다. 따라서, 이를 bull set으로 분리하고 one-shot update를 해 computation을 감소시키고자 하는 것이다.

두번째 이유는 locality이다.

 

<One-shot update> -> Bull set

Bull set의 one-shot update에 대해 설명해 보고자 한다. Bull set에 속하는 모든 k번째 community들은 같은 값으로 한 번에 update된다. 기존의 모수 값들을 평균 값으로 대체함으로써 가능하다.

다음과 같이, bull set에 속하는 communities는 one-shot update를 하고, activate set 및 candidate set은 individually update를 한다.

이제, gradient 계산을 효율적으로 하기 위해 global parameter update에서 했듯이 local parameter update에서도 stratified sampling을 다음과 같이 할 것 이다.

최종적인 algorithm은 다음과 같다.

결론적으로, 이 논문에서의 핵심은 graph의 uncertainty 고려하며 상대적으로 강한 relationship을 가진 graph를 modeling하는데 a-MMSB을 통해 형성했으며 mini-batch 단위로 update를 하는 SG-MCMC를 통해 computation 효과를 얻을 수 있다는 것이다.

 

 

참고논문

• Scalable MCMC for Mixed Membership Stochastic Blockmodels.
• Stochastic Gradient Riemannian Langevin Dynamics on the Probability Simplex.