IEEE Computational Intelligence Magazine - August 2019 - 45

limit, we skip the derivation details, and
summarize the updates for each variational parameter in q(W, K ) as2:

Algorithm I Inference algorithm for ComE+.

Input: graph G = (V, E ) , variational parameter k, #(paths per node) c, walk length
, , context size g, embedding dimension d, negative context size m,
parameters (a, b ).
Output: node embedding U, context embedding Ul , community embed-

;V ;

c k, 1

= 1 + / p i, k,
i =1
;V ;

c k, 2

=t + /

K

/

(12)
p i, j,

(13)

i = 1 j = k +1

;V ;

B k = e / p i, k + 1 o I
i =1

;V ;

+ / p i, k (z i - x k) (z i - x k)T , (14)
i =1

x k =e I +B k

-1

-1

;V ;

;V ;

c k / p i, k o e B k-1c k / p i, k z i o,
i =1

i =1

(15)
;V ;

c k = 2 + o + / p i, k ,

(16)

i =1

k

p i, k

? e K (ck,1, ck,2) + j/=1 K (c j,1, c j,2) +Eq [log p (zi ; zi = k)] ,
(17)

where we define K (c l, 1, c l, 2 ) = W(c l, 1) W(c l, 1 + c l, 2 ), given W($) as a digamma
function.
Fix q, optimize (U, Ul ) . We use
MAP estimation to learn the node embedding, given O 1 and O 2 as the likelihood
+l
terms and O ComE
as the prior term for
3
z i 's. Optimizing O 1 and O 2 is straightforward and is similar to ComE's inference.
Specifically, for each v i ! V, we have:
2O 1 =-/
T
v (- z j z i ) z j ,
(i, j) ! E
2z i

(18)

2O 2 =-a / v(-zlT z ) zl
i
j
j
;
2z i
v j ! Ci
m

+ / E vl + Pn (vl) [v(zllT z i)(-zll )]E.
t =1

(19)

We also compute the gradient for
context embedding as:
2O 2 =- a / d (v ! C ) v(-zlT z ) z
i
i
i
j
; j
2zlj
vi ! V
m

+ / E vl + Pn (vl)[d (v l =v j) v(zllT z i)(-z i)]E .
t =1

(20)

+l
Instead, optimizing O ComE
requires
3
some more simplification. In Eq. 11,
only the last term depends on z i 's; thus
+l
we can simplify O ComE
as:
3
2
The full derivation can be found at the following link:
http://sentic.net/derivation.pdf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

ding posterior distribution q
P ! SamplePath(G, , );
Initialize U and Ul by DeepWalk [3] with P;
for iter =1: T1 do
for subiter =1: T2 do
Optimize q (W, K ) by Eq. 12-17 given U;
end
foreach edge ( i, j ) ! E do
SGD on z i and z j by Eq. 18;
end
foreach path p ! P do
foreach v i in path p do
SGD on z i by Eq. 19;
SGD on zlj 's within g hops by Eq. 20;
end
end
foreach node v i ! V do
SGD on z i by Eq. 21;
end
end

O 3ComE+m(U) =?

b

;V ;

;V ;

/ Eq[ log p(z i ;} z , R z )
K
b

i

i

i =1

K

/ / p i,k · 12 (z i -x k)T(B k-1c k)(z i -x k)

K i =1 k =1

(21)

and compute the gradient over
+m
b
2 O ComE
3
=
2z i
K

zi

as:

K

/ p i,k (B k-1 c k) (z i - x k).

k =1

(22)

Finally, we have the total gradient for
each z i defined as:
ComE+m
2Ll 2O 1 2O 2 2O 3
=
+
+
. (23)
2z i
2z i
2z i
2z i

Algorithm and complexity. We
summarize the inference algorithm of
ComE+ in Alg. 1. In line 1, for each
v i ! V, we sample c paths starting from
v i with length , on G. In line 2, we initialize (U, Ul ) by DeepWalk.
In lines 4-5, we fix (U, Ul ) and optimize q(W, K ) for community detection
and embedding. In lines 6-11, we fix
q(W, K ) and optimize (U, Ul ) for node

embedding. We analyze the complexity
of Alg. 1.
Path sampling in line 1 takes O ( ;V ; c,).
Parameter initialization by DeepWalk in
line 2 takes O ( ;V ; ). Optimizing the variational parameters q(W, K ) in line 5
takes O ( ;V ; K ). Node embedding w.r.t.
first-order proximity in lines 7 takes
O ( ; E ; ). Node embedding w.r.t. secondorder proximity in lines 9-11 takes
O ( ;V ; c,). Node embedding w.r.t.
community-aware high-order proximity in lines 12-13 takes O ( ;V ; K ).
In total, the complexity of Alg. 1 is
O ( ;V ; c, + ;V ; +T1 # (T2 ;V ; K + K +
; E ; + ;V ; c, + ;V ; K )), which is still linear to the graph size (i.e., ;V ; and ; E ; ).
V. Experiments

In this section, we evaluate ComE+ on
six real-world datasets under two application tasks, including node classification
and community detection3. Compared
3

Due to space limitation: 1) the graph visualization performance, 2) the ComE clustering results, 3) the complete set of node classification experiments and 4) impact
of some parameters like a, b and the embedding size
are reported at the following link: http://sentic.net/
node-classification.pdf

AUGUST 2019 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

45
http://www.sentic.net/ http://www.sentic.net/derivation.pdf
IEEE Computational Intelligence Magazine - August 2019

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