IEEE Computational Intelligence Magazine - August 2019 - 44

- Draw z i + SBC (r);
- Draw z i + N (} z i, R z i ).
Specifically, we denote B(a, b) as a
Beta distribution, where a 2 0 and
b 2 0 are the parameters. We denote
W (A, o) as a Wishart distribution, with
a positive definite scale matrix A ! R d # d
and degrees of freedom o 2 d - 1. Denote I as a d # d dimensional identity
matrix. We denote t 2 0 and o 2 0 as
the hyper-parameters for the prior distributions of } k and R k respectively,
describing how many latent components to activate and how small the
Gaussian covariance can be. Additionally,
z i + SBC (r) is a stick-breaking construction, where given an infinite
dimensional vector r = [r 1, r 2, f], we
compute the mixture probability for
each community k as

ComE+ model we need to manage
MAP estimation and Bayesian inference
together. In general, there can be different approaches to Bayesian inference. For
example, [21], [43], [45] adopt a Markov
chain Monte Carlo (MCMC) methods;
to the other side [47] optimize the likelihood function by stochastic gradient
descent (SGD). In this work, we propose
to use a variational inference formulation as the objective function of
ComE+. However, we resort to variational inference to develop an analytical
form, which directly infers the posterior
distribution of the Gaussian random
variables and encodes the node embedding prior by N (} zi, R zi ). Specifically,
we introduce a variational distribution
q (W ) to approximate the posterior
p (W ; U; t, o), by minimizing the KLdivergence between them:

k -1

hk

= r k % (1 - r j), for k = 1, 2, f. (4)
j =1

Based on the resulting infinite dimensional vector h = [h 1, h 2, f], we draw
the community assignment indicator
z i ! {1, 2, f} for each node v i by a
multinomial distribution:
z i + Multi (h), for i = 1, f, ;V ;. (5)
For notation simplicity, we denote Z =
{z 1, f, z N } as the community assignments for N nodes and X = {(} 1, R 1),
(} 2, R 2), f} as the infinite community
embeddings. Finally, we denote W =
{r, X, Z} . Given the node embeddings
U for a graph G, the primary purpose
is to infer the posterior distribution
p (W ; U; t, o), which identifies community assignments and community embedding.
C. Closing the Loop

As for ComE, also in ComE+, we aim to
realize the closed loop shown in Fig. 1b,
yet in an infinite community setting.
Effectively, learning node embedding
requires a Maximum A Posteriori (MAP)
estimation, where we see O 1 (Eq. 1) and
O 2 (Eq. 3) as modeling the likelihood of
z i 's, and z i + N (} z i, R z i ) as modeling
the prior. In contrast, to handle the infinite number of communities, we need
Bayesian inference. Thus, to optimize the

44

KL (q(W ) ; p (W ; U; t, o))
q (W )
E
= E q ;log
p (W ; U; t, o)
= E q[ log q(W )] - E q[ log p (W ; U; t, o)]
= E q[ log q(W )] - E q[ log p (W, U ; t, o)]
(6)
+ log p(U ; t, o).
As log p(U ; t, o) does not depend on q,
minimizing Eq. 6 is equivalent to:
max
E q[ log p (W, U ; t, o)]
q
- E q [ log q(W )].

To jointly optimize node embedding
and community embedding, we exploit
a similar coordinated learning process
like the one proposed in ComE. That is,
we also apply iterative optimization
between (U, Ul ) and q. Given (U, Ul ),
optimizing q is to infer the infinite community embedding. Given q, optimizing
(U, Ul ) is to learn the node embedding
with all types of proximity.
Fix (U, Ul ), optimize q. For variational inference, we try to define q (W )
with a tractable form. Note that q (W )
is a distribution over an infinite set of
(r k, z k, } k, R k)'s. To make q (W ) tractable, we follow [27] to truncate q (W ) at
a value K, by setting q (r K = 1) = 1.
According to Eq. 4, we have all the
h k(r) = 0 for k 2 K . In so doing, K
only serves as a maximum number of
possible communities to be detected in
the graph. Due to this truncation, we
revise q (W ) as q(W, K ), where K is a
variational parameter. We will empirically evaluate the model performance
under different K values in the experiments. Then, we use mean-field approximation to factorize q(W, K ) as:
K

K

k =1

k =1

q(W, K ) = % q ck,1, ck,2(r k) % q xk(} k)
;V ;

K

(7)

Notice that p(W, U ; t, o) is the joint
probability describing our generative
process in Sec. III.B. Thus it naturally
includes the formulation of N (} zi, R zi ),
which can be used to optimize together
with O 1 and O 2 . To this end, we define
the objective function for inferring the
community embedding's posterior distribution, which also enables the higherorder proximity for node embedding as:
+
O ComE
=- b ^E q[ log p (W, U ; t, o)]
3
(8)
-E q[ log q(W )] h,

where b 2 0 is a trade-off parameter.
Finally, we define the overall objective
function for ComE+ as:
LComE+(U, Ul , q) =O 1(U) +O 2(U, Ul )
+O 3ComE+(U, q).
(9)

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2019

IV. Inference

% q B ,c (R k-1)% q
k k

k =1

pi

(z i), (10)

i =1

where we define q ck,1, ck,2(r k) as a Beta
distribution parameterized with c k, 1 2 0
and c k, 2 2 0, q xk(} k) as a multivariate
Gaussian distribution parameterized
with mean x k ! R d, q Bk, ck (R k-1 ) as a
Wishart distribution parameterized with
a positive definite scale matr ix
B -k 1 ! R d # d and degrees of freedom
c k 2 0, and q pi(z i) as a multinomial distribution parameterized with p i ! T
(where T is a simplex). With the truncated variational distribution q(W, K ),
we revise Eq. 8 as:
^E [ log p(W, U ; t, o)]
K q
- Eq[ log q(W, K )] h . (11)

+l
O ComE
(U, q) =3

b

+
Ultimately, we replace O ComE
in Eq.  9
3
ComE+l
with O 3
for inference. Due to space
IEEE Computational Intelligence Magazine - August 2019

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2019
