From Node Embedding To Community Embedding∗

arXiv:1610.09950v2 [cs.SI] 14 Sep 2017

Vincent W. Zheng1 , Sandro Cavallari2 , Hongyun Cai1 , Kevin Chen-Chuan Chang3 , Erik Cambria2
1
Advanced Digital Sciences Center, Singapore;
2
Nanyang Technological University, Singapore;
3
University of Illinois at Urbana-Champaign, USA
{vincent.zheng, hongyun.c}@adsc.com.sg, sandro001@e.ntu.edu.sg,
kcchang@illinois.edu, cambria@ntu.edu.sg
Abstract
In this paper, we introduce a new setting for
graph embedding, which considers embedding
communities instead of individual nodes. Community embedding is useful as a natural community
representation for applications, and it provides
an exciting opportunity to improve community
detection. Specifically, we see the interaction
between community embedding and detection
as a closed loop, through node embedding. On
the one hand, we rely on node embedding to
generate good communities and thus meaningful
community embedding. On the other hand, we
apply community embedding to improve node
embedding through a novel community-aware
higher-order proximity. This closed loop enables
us to improve community embedding, community
detection and node embedding at the same time.
Guided by this insight, we propose ComE, the first
community embedding method so far as we know.
We evaluate ComE on multiple real-world data
sets, and show ComE outperforms the state-of-theart baselines in both tasks of community prediction
and node classification. Our code is available
at
https://github.com/andompesta/
nodeembedding-to-communityembedding.

1

Introduction

Traditionally, graph embedding focuses on individual nodes,
which aims to output a vector representation for each node
in the graph, such that two nodes “close” on the graph have
similar vector representations in a low-dimensional space.
Such node embedding has been shown very successful in
preserving the network structure, and significantly improving a wide range of applications, including node classification
[Cao et al., 2015; Perozzi et al., 2014], node clustering [Tian
et al., 2014; Yang et al., 2016], link prediction [Grover and
Leskovec, 2016; Ou et al., 2016], graph visualization [Tang
et al., 2015; Wang et al., 2016] and more [Fang et al., 2016;
Niepert et al., 2016].
∗

This is a technical report for paper [Cavallari et al., 2017].

Community Detection
③

①

Node Embedding

Community Embedding
②

Figure 1: Close loop for community detection & embedding.
In this paper, we study a new setting for graph embedding, which focuses on embedding communities. Generally, a
“community embedding” is a representation for a community
in a low-dimensional space. Since a community is a group
of densely connected nodes, a community embedding cannot simply be a vector representation like a node embedding.
Instead, a community embedding should be a set of random
variables, for a distribution characterizing how the community member nodes spread in the low-dimensional space. For
instance, if we consider multivariate Gaussian as the distribution, then a community embedding consists of a mean and a
covariance. Surprisingly, despite the success of node embedding, the concept of community embedding is still missing in
the literature (more discussions in Sect. 2).
Community embedding is useful. As a representation of
community, it naturally supports community-level applications, such as visualizing communities to help generate insights for graph analysis, finding similar communities to assist community recommendation and so on. Besides, it also
provides an exciting opportunity to improve community detection. Specifically, to find a useful community embedding,
we first need to have a good community. Since recent graph
embedding has shown to be an effective way for graph analytics, we wish to leverage node embedding to find good
communities. Most recent node embedding methods such as
DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015]
and node2vec [Grover and Leskovec, 2016] focus on preserving first-order and/or second-order proximity, which can ensure two nodes directly linked or sharing “context” to have
similar embeddings. But they are not aware of community
structures, as shown in Fig. 2(b)–2(d), where we visualize the
node embedding for these methods on Zachary’s karate club
graph [Zachary, 1977]. Thus a simple pipeline approach to
first detect communities and then aggregate their nodes’ embeddings as community embedding (i.e., ¬ in Fig. 1) is limited due to suboptimal detection. Community embedding can
avoid such a limitation– suppose we already have some community embedding, then we can come back to optimize the

(a) Karate club graph

(b) DeepWalk

(c) LINE

(d) node2vec

(e) ComE (ours)

Figure 2: Graph embedding of the Zachary’s karate club graph in a 2D space. In (b)–(e), we input the same data to different
methods for graph embedding. For each node, we sample 10 paths, each of which has a length of 80. We set context window
size as 5 and negative sampling size as 5. In LINE, we use mean pooling of the first-order proximity embedding and the
second-order proximity embedding for each node. In node2vec, we set p = 0.25, q = 0.25. In ComE, we set α = 1, β = 1. In
(e), we also plot the community embeddings as four eclipses, characterizing the distribution of four detected communities.
node embedding (i.e., ­ in Fig. 1), by “squashing” the nodes
to scatter closely near their community centers. The resulting
node embedding thus becomes community-aware and hopefully improves the community detection (i.e., ® in Fig. 1).
In Fig. 2(e), we show a promising result to have communityaware node embedding and better communities, with the help
of community embedding.
To close the loop between community detection and community embedding is non-trivial. A shown in Fig. 1 ­, we try
to use community embedding to guide node embedding, but
it is not clear how to do it. There is work on using node embedding to improve community detection [Cao et al., 2015;
Kozdoba and Mannor, 2015; Tian et al., 2014]. But there is
very little work on the other way around using explicit community information to enhance node embedding [Yang et al.,
2016], and it needs extra supervision of must-links to enforce
the community in node embedding.
Our insight for addressing the community embedding
feedback is to see community embedding as providing a
novel community-aware higher-order proximity, such that
two nodes in the same community can be close in the lowdimensional space. In contrast with first-order proximity and
second-order proximity, community embedding does not require two nodes to be directly linked or share many “contexts” for being close. There is little work on higher-order
proximity [Cao et al., 2015; Ou et al., 2016], and they all
rely on embedding a higher-order adjacency matrix, which
can easily have a quadratic number of non-zero entries. As
a result, their computation can be expensive. Besides, their
higher-order proximity does not explicitly model community. Another advantage of seeing community embedding as
a higher-order proximity is that, we can combine it with the
first-order and the second-order proximity for node embedding through the well-established neural network framework.
Guided by the above insight, we propose ComE, the first
Community Embedding model for graph analytics. To represent a community, we are inspired by the Gaussian Mixture
Model [Bishop, 2006] to see each community as a Gaussian
component. Thus we formulate a community embedding as
a tuple of a mean vector indicating the center of a commu-

nity and a covariance matrix indicating the spread of its members in a low-dimensional space. To realize the closed loop in
Fig. 1, we develop an iterative inference algorithm for ComE.
On the one hand, given node embeddings, we can detect and
embed the communities, such that a good community assignment and a good community embedding should explain the
node embedding well. On the other hand, given community
assignment and community embedding, we can optimize the
node embedding by enforcing all different orders of proximity. As shown in Sect. 4, our inference algorithm’s complexity is linear to the graph size.
We summarize our contributions as follows.
• To the best of our knowledge, we are the first to introduce
the concept of community embedding to graph analytics.
• We identify that communty embedding can improve community detection, thus closing the loop between them.
• We contribute a novel ComE model to close the loop and a
scalable inference algorithm to detect communities and infer
their embeddings at the same time.
• We evaluate ComE on three real-world data sets. It improves the state-of-the-art baselines by at least 2.5%–7.8%
(NMI) and 1.1%–2.8% (conductance) in community detection, 9.52%–43.5% (macro-F1) and 6.9%–19.4% (micro-F1)
in node classification.

2

Related Work

There has been an increasing amount of graph data, ranging from social networks such as Twitter to various information networks such as Wikipedia. An important question in
graph analytics is how to represent a graph. Graph embedding
is a popular graph representation framework, which aims to
project a graph into a low-dimensional space for further applications [Tenenbaum et al., 2000; Perozzi et al., 2014].
In terms of the target to embed, most graph embedding
methods focus on nodes. For example, earlier methods, such
as MDS [Cox and Cox, 2000], LLE [Roweis and Saul, 2000],
IsoMap [Tenenbaum et al., 2000] and Laplacian eigenmap
[Belkin and Niyogi, 2001], typically aim to solve the leading eigenvectors of graph affinity matrices as node embedding. Recent methods typically rely on neural networks to

learn the representation for each node, with either shallow architectures [Xie et al., 2016; Tang et al., 2015; Grover and
Leskovec, 2016] or deep architectures [Niepert et al., 2016;
Wang et al., 2016; Chang et al., 2015]. Other than node embedding, there is some attempt to learn edge embedding in a
knowledge base [Luo et al., 2015] or proximity embedding
between two possibly distant nodes in a general heterogeneous graph [Liu et al., 2017]. But there is no community
embedding so far as we know.
In terms of the information to preserve, most graph embedding methods try to preserve first-order proximity and/or
second-order proximity [Perozzi et al., 2014; Grover and
Leskovec, 2016; Tang et al., 2015; Wang et al., 2016]. Some
recent attempts consider higher-order proximity, by factorizing a higher-order node-node proximity matrix by PageRank
or Katz index [Cao et al., 2015; Ou et al., 2016]. Hence their
higher-order proximity is based on the graph reachability via
random walk, where the notion of community is missing. In
contrast, our community embedding tries to preserve all the
first-, second- and community-aware higher-order proximity.
In terms of interaction between node and community,
there are a few graph embedding models that use node embedding to assist community detection [Tian et al., 2014;
Kozdoba and Mannor, 2015], but they do not have the notion of community in their node embedding. There is little
work that allows community feedback to guide the node embedding [Yang et al., 2016], but it lacks the concept of community embedding and its community feedback requires extra
supervision on must-links. In contrast, we optimize node embedding, community embedding and community detection in
a closed loop, and let them reinforce each other.

3

Problem Formulation

As input, we are given a graph G = (V, E), where V is the
node set and E is the edge set. Traditional graph embedding
aims to learn a node embedding for each vi ∈ V as φi ∈ Rd .
In this paper, we introduce the concept of community embedding. Suppose there are K communities on the graph
G. For each node vi , we denote its community assignment
as zi ∈ {1, ..., K}. Motivated by Gaussian Mixture Model
(GMM), we represent each community as a Gaussian component, which is characterized by a mean vector indicating
the community center and a covariance matrix indicating its
member nodes’ spread. Formally, we define:
Definition 1 A community k’s embedding (where k =
1, 2, ..., K) in a d-dimensional space is a set of random variables (ψ k , Σk ), where ψ k ∈ Rd is the mean and Σk ∈ Rd×d
is the covariance for a multivariate Gaussian distribution.
As output, we aim to learn both the community embedding
(ψ k , Σk ) for each community k ∈ {1, ..., K} and the node
embedding φi for each node vi ∈ V on the graph G.
Next, we model the closed loop in Fig. 1.

3.1

Community Detection and Embedding

Given node embedding, one straightforward way to detect
communities and learn their embedding is to take a pipeline
approach. For example, as shown in Fig. 1, one can first
run K-means to detect communities, and then fit a Gaussian

mixture for each community. However, such a pipeline approach lacks a unified objective function, thus hard to optimize later with node embedding. Alternatively, we can do
community detection and embedding together in one single
objective function based on Gaussian Mixture Model. That is,
we consider each node vi ’s embedding φi as generated by a
multivariate Gaussian distribution from a community zi = k.
Then, for all the nodes in V , we have the likelihood as
Q|V | PK
(1)
i=1
k=1 p(zi = k)p(vi |zi = k; φi , ψ k , Σk ),
where p(zi = k) is the probability of node vi belonging to
community k. For notation simplicity, we denote p(zi = k)
PK
as πik ; thus we have πik ∈ [0, 1] and k=1 πik = 1. In community detection, these πik ’s indicate the mixed community
membership for each node vi , and they are unknown. Besides,
p(vi |zi = k; φi , ψ k , Σk ) is a multivariate Gaussian distribution defined as follows
p(vi |zi = k; φi , ψ k , Σk ) = N (φi |ψ k , Σk ).

(2)

In community embedding, the (ψ k , Σk )’s are unknown. By
optimizing Eq. 1 w.r.t. πik ’s and (ψ k , Σk )’s, we achieve community detection and embedding at the same time.

3.2

Node Embedding

Traditionally, node embedding focuses on preserving first- or
second-order proximity. For example, to preserve first-order
proximity, LINE [Tang et al., 2015] enforces two neighboring
nodes to have similar embedding by minimizing
P
O1 = − (vi ,vj )∈E log σ(φTj φi ),
(3)
where σ(x) = 1/(1 + exp(−x)) is a sigmoid function.
To preserve second-order proximity, LINE and DeepWalk
[Perozzi et al., 2014] both enforce two nodes sharing many
“contexts” (i.e., neighbors within ζ hops) to have similar embedding. In this case, each node has two roles: a node for
itself and a context for some other nodes. To differentiate
such roles, LINE introduces an extra context embedding for
each node vj as φ0j ∈ Rd . Denote Ci as the set of contexts
for node vi . Then LINE adopts negative sampling [Mikolov
et al., 2013] to define a function for measuring how well vi
generates each of its contexts vj ∈ Ci as
m
P
T
T
∆ij = log σ(φ0 j φi )+
Evl ∼Pn (vl ) [log σ(−φ0 l φi )], (4)
t=1

where vl ∼ Pn (vl ) denotes sampling a node vl ∈ V as a
“negative context” of vi according to a probability Pn (vl ).
3/4
We set Pn (vl ) ∝ rl as proposed in [Mikolov et al., 2013],
where rl is vl ’s degree. In total, there are m negative contexts. Generally, maximizing Eq. 4 enforces node vi ’s embedding φi to best generate its positive contexts φ0j ’s, but not
its negative contexts φ0l ’s. Then we can minimize the following objective function to preserve the second-order proximity:
P
P
O2 = −α vi ∈V vj ∈Ci ∆ij ,
(5)
where α > 0 is a trade-off parameter.

3.3

Closing the Loop

In order to close the loop in Fig. 1, we need to enable the feedback from community detection and community embedding
to node embedding. Suppose we have identified the mixed
community membership πik ’s and the community embedding
(ψ k , Σk )’s in Sect. 3.1. Then we can re-use Eq. 1 to enable such feedback, by seeing the node embedding φi ’s as
unknown. Effectively, optimizing Eq. 1 w.r.t. φi ’s enforces
the nodes φi ’s within the same community to get closer to
the corresponding community center ψ k . That is, two nodes
sharing a community are likely to have similar embedding.
Compared with the first- and second-order proximity, this design introduces a new community-aware higher-order proximity to node embedding, which is useful for community detection and embedding later. For example, in Fig. 2(a), node
3 and node 10 are directly linked, but node 3 is closer to the
blue-green community, whereas node 10 is closer to the redyellow community. Therefore, by only preserving first-order
proximity, we may not tell their community membership’s
difference well. For another example, node 9 and node 10
share a number of one-hop and two-hop neighbors, but compared with node 10, node 9 is closer to the blue-green community. Therefore, by only preserving second-order proximity, we may not tell their community membership’s difference
well, as shown in Fig. 2(b) and Fig. 2(d).
Based on the closed loop, we will optimize community
detection, community embedding and node embedding together. We have three types of proximity to consider for node
embedding, including first-, second- and higher-order proximity. In general, there are two approaches to combine different types of proximity for node embedding: 1) “concatenation”, e.g., LINE first separately optimizes O1 and O2 , then it
concatenates the two resulting embedding for each node into
a long vector as the final output; 2) “unification”, e.g., SDNE
[Wang et al., 2016] learns a single node embedding for each
node to preserve both first- and second-order proximity at the
same time. In this paper, to encourage the node embedding
to unify multiple types of proximity, we adopt the unification approach, and leave the other approach as future work.
Consequently, based on Eq. 1, we first define the objective
function for community detection and embedding, as well as
enforcing the higher-order proximity for node embedding as:
PK
β P|V |
O3 = − K
(6)
i=1 log
k=1 πik N (φi |ψ k , Σk ),
where β ≥ 0 is a trade-off parameter. Denote Φ = {φi },
Φ0 = {φ0i }, Π = {πik }, Ψ = {ψ 0k } and Σ = {Σk } for
i = 1, ..., N, k = 1, ..., K. Then, we also unify the first- and
second-order proximity for node embedding, thus reaching
the ultimate objective function for ComE as
L(Φ, Φ0 , Π, Ψ, Σ) = O1 (Φ) + O2 (Φ, Φ0 ) + O3 (Φ, Π, Ψ, Σ).
(7)
Our final optimization problem becomes:
(Φ∗ , Φ0∗ , Π∗ , Ψ∗ , Σ∗ ) ←

arg min

L(Φ, Φ0 , Π, Ψ, Σ),

∀k,diag(Σk )>0

(8)
where diag(Σk ) returns the diagonal entries of Σk . We particularly introduce a constraint of diag(Σk ) > 0 for each
k ∈ {1, ..., K} to avoid the singularity issue of optimizing L.

Similar to Gaussian Mixture model ([Bishop, 2006], there exists degenerated solutions for optimizing L without any constraint. That is, when a Gaussian component collapses to a
single point, the diag(Σk ) becomes zero, which makes O3
become negative infinity.

4

Inference

We decompose the optimization of Eq. 8 into two parts, and
take an iterative approach to solve it. Specifically, we consider iteratively optimizing (Π, Ψ, Σ) with a constrained minimization given (Φ, Φ0 ), and optimizing (Φ, Φ0 ) with an unconstrained minimization given (Π, Ψ, Σ). Empirically, this
iterative optimization algorithm converges quickly with a reasonable initialization; e.g., we initialize (Φ, Φ0 ) by DeepWalk
results in our experiments. We report the convergence in
Sect. 5.3. Next we detail this iterative optimization.
Fix (Φ, Φ0 ), optimize (Π, Ψ, Σ). In this case, Eq. 7 is simplified as the negative log-likelihood of a GMM. According
to [Bishop, 2006], we can optimize (Π, Ψ, Σ) by EM, and
obtain a closed-form solution as
πik =
ψk =

(9)

1
Nk

P|V |

1
Nk

P|V |

i=1

γik φi ,

(10)

γik (φi − ψ k )(φi − ψ k )T ,
(11)
P
|V |
i |ψ k ,Σk )
and Nk = i=1 γik .
= PK πikπN (φ
0 N (φ |ψ 0 ,Σ 0 )

Σk =
where γik

Nk
|V | ,

i=1

k0 =1

ik

i

k

k

Fix (Π, Ψ, Σ), optimize (Φ, Φ0 ). In this case, Eq. 7 is simplified as optimizing the node embedding with three types of
proximity. Due to the summation within the logarithm term
of O3 , it is inconvenient to compute the gradient of φi . Thus
we try to minimize an upper bound of L(Φ, Ψ, Σ) instead:
β P|V | PK
(12)
O30 = − K
i=1
k=1 πik log N (φi |ψ k , Σk ).
It is easy to prove that O30 (Φ; Π, Ψ, Σ) ≥ O3 (Φ; Π, Ψ, Σ),
P|V |
PK
due to log-concavity i=1 log k=1 πik N (φi |ψ k , Σk ) ≥
P|V | PK
i=1
k=1 log πik N (φi |ψ k , Σk ). As a result, we define
L0 (Φ, Φ0 ) = O1 (Φ) + O2 (Φ, Φ0 ) + O30 (Φ; Π, Ψ, Σ),
and thus L0 (Φ, Φ0 ) ≥ L(Φ, Φ0 ). We optimize L0 (Φ, Φ0 ) by
stochastic gradient descent (SGD). For each vi ∈ V , we have
P
T
∂O1
(13)
(i,j)∈E σ(−φj φi )φj ,
∂φi = −

P
0T
0
∂O2
vj ∈Ci σ(−φj φi )φj
∂φi = −α

Pm
T
+ t=1 Evl ∼Pn (vl ) [σ(φ0l φi )(−φ0l )] , (14)
∂O30
∂φi

=

β
K

PK

k=1

πik Σ−1
k (φi − ψ k ).

(15)

We also compute the gradient for context embedding as

P
0T
∂O2
vi ∈V δ(vj ∈ Ci )σ(−φj φi )φi
∂φ0j = −α

Pm
0T
+ t=1 Evl ∼Pn (vl ) [δ(vl = vj )σ(φl φi )(−φi )] . (16)

Algorithm 1 ComE
Require: graph G = (V, E), #(community) K, #(paths per
node) γ, walk length `, context size ζ, embedding dimension d, negative context size m, parameters (α, β).
Ensure: node embedding Φ, context embedding Φ0 , community assignment Π, community embedding (Ψ, Σ).
1: P ← SamplePath(G, `);
2: Initialize Φ and Φ0 ;
3: for iter = 1 : T1 do
4:
for subiter = 1 : T2 do
5:
Update πik , ψ k and Σk by Eq. 9, Eq. 10 and Eq. 11;
6:
for all edge (i, j) ∈ E do
7:
SGD on φi and φj by Eq. 13;
8:
for all path p ∈ P do
9:
for all vi in path p do
10:
SGD on φi by Eq. 14;
11:
SGD on its context φ0j ’s within ζ hops by Eq. 16;
12:
for all node vi ∈ V do
13:
SGD on φi by Eq. 15;
Algorithm and complexity. We summarize ComE in Alg. 1.
In line 1, for each vi ∈ V , we sample γ paths starting from vi
with length ` on G. In lines 4–5, we fix (Φ, Φ0 ) and optimize
(Π, Ψ, Σ) for community detection and embedding. In lines
6–13, we fix (Π, Ψ, Σ) and optimize (Φ, Φ0 ) for node embedding. Specifically, we update node embedding by first-order
proximity (lines 6–7), second-order proximity (lines 8–11)
and community-aware higher-order proximity (lines 12–13).
We analyze time complexity of Alg. 1. Path sampling
in line 1 takes O(|V |γ`). Parameter initialization in line 2
takes O(|V | + K). Community detection and embedding
in line 5 takes O(|V |K). Node embedding w.r.t. first-order
proximity in lines 6–7 takes O(|E|). Node embedding w.r.t.
second-order proximity in lines 8–11 takes O(|V |γ`). Node
embedding w.r.t. community-aware higher-order proximity
in lines 12–13 takes O(|V |K). In total, the complexity is
O(|V |γ`+|V |+K +T1 ×(T2 |V |K +|E|+|V |γ`+|V |K)),
which is linear to the graph size (i.e., |V | and |E|).

5

Experiments

We want to quantitatively evaluate community embedding.
Firstly, as an important application of community embedding,
we evaluate the resulting community detection (Sect. 5.1).
Secondly, as the loop between community detection and embedding is closed through node embedding, we also evaluate
the resulting node embedding. In particular, following the
previous work [Perozzi et al., 2014; Tang et al., 2015], we
consider node classification (Sect. 5.2). Finally, we study our
model’s convergence and parameter sensitivity (Sect. 5.3).
1

Data sets. We use three public data sets , as listed in Table 1.
Evaluation metrics. In community detection, we use both
conductance [Kloster and Gleich, 2014] and normalized mu1
Available at http://socialcomputing.asu.edu/pages/datasets and
https://snap.stanford.edu/node2vec/POS.mat.

Table 1: Data sets.
#(node) #(edge) #(node labels) labels per node
BlogCatalog 10,312 333,983
39
single-label
Flickr
80,513 5,899,882
195
single-label
Wikipedia
4,777 184,812
40
multi-label

tual information (NMI) [Tian et al., 2014]. In node classification, we use micro-F1 and macro-F1 [Perozzi et al., 2014].
Baselines. We design baselines to answer two questions: 1) is
it necessary to model community detection, community embedding and node embedding together? 2) is it necessary to
enable the feedback from community embedding to community detection through node embedding? To answer the first
question, we introduce a simple pipeline approach.
• Pipeline: it first detects communities by GMM based on the
graph adjacency matrix. Then, it uses LINE to generate firstand second-order node embedding. Finally, it fits a multivariate Gaussian in each community based on its member nodes’
embedding as the community embedding.
To answer the second question, we apply the state-of-theart methods to generate node embedding, based on which we
further use GMM to detect and embed communities.
• DeepWalk [Perozzi et al., 2014]: it models second-order
proximity for node embedding.
• LINE [Tang et al., 2015]: it models both first- and secondorder proximity for node embedding.
• node2vec [Grover and Leskovec, 2016]: it extends DeepWalk by exploiting homophily and structural roles.
• GraRep [Cao et al., 2015]: it models random walk based
higher-order proximity for node embedding.
• SAE [Tian et al., 2014]: it uses sparse auto-encoder, which
is shown to share a similar objective as spectral clustering, on
the adjacency matrix for node embedding.
We try to compare with all baselines on all data sets, using the codes released by their authors. However, we cannot
produce results for node2vec and GraRep on Flickr due to unmanageable out-of-memory errors on a machine with 64GB
memory. Thus we exclude them from comparison on Flickr.
Parameters and environment. In DeepWalk, node2vec and
ComE, we set γ = ζ = 10, ` = 80, m = 5. In node2vec, we
set p = q = 0.25 according to the best results in [Grover and
Leskovec, 2016]. We set the embedding dimension d = 128
for all methods. We set K as the number of unique labels in
each data set. We run experiments on Linux machines with
eight 3.50GHz Intel Xeon(R) CPUs and 16GB memory.

5.1

Community Detection

In community prediction, our goal is to predict the most likely
community assignment for each node. Since our data sets are
labeled, we set the number of communities K as the number of distinct labels in the data set. As an unsupervised
task, we use the whole graph for learning embeddings and
then predicting communities for each node. Note that in
Wikipedia, one node has multiple labels, thus we predict the

0.14680751
0.14531306
0.06142352

0.148046 0.148102 0.148127 0.148247

0.14827

0.85
0.8
BlogCatalog

Flickr

Wiki_top1

Wiki_top2

Wiki_top3

Macro-F1
Macro-F1

ComE

0.3

NMI

Pipeline
0.2

DeepWalk
LINE

0.1

node2vec
0
BlogCatalog

Flickr

top N (N = 1, 2, 3) communities for each node, the results
are denoted as Wiki topN (N = 1, 2, 3) in Fig. 3.
We compare ComE with the baselines for community prediction. We set α = 0.1, β = 0.01 in ComE for all three data
sets. As the baselines do not consider community in their
embeddings, for fair comparison, we apply GMM over all
the methods’ node embedding outputs for community prediction. As shown in Fig. 3, ComE is consistently better than the
baselines in terms of both conductance and NMI. Specifically,
ComE improves the best baseline in all data sets by relative
1.1%–2.8% (conductance) and 2.5%–7.8% (NMI). This improvement suggests that, for community prediction, modeling
community together with node embedding is better than doing them separately. Note that we do not calculate NMI for
Wikipeida as it is multilabel dataset.

5.2

0.15
0.1
0.05
0.1
0
2%

Macro-F1

0.15

Figure 3: Results on community prediction. The smaller conductance is, the better. The bigger NMI is, the better.

Node Classification

In node classification, our goal is to classify each node into
one (or more) labels. We follow [Perozzi et al., 2014] to first
train the embeddings on the whole graph, then randomly split
10% (BlogCatalog and Wikipedia) and 90% (Flickr) of nodes
as test data, respectively. We use the remaining nodes to train
a classifier by LibSVM (c = 1 for all methods) [Chang and
Lin, 2011]. We repeat 10 splits and report the average results.
We compare ComE with the baselines for node classification. We set α = 0.1, β = 0.01 for BlogCatalog
and Wikipedia, and α = 0.1, β = 0.1 for Flickr. We
vary the number of training data to build the classifiers
for each method’s node embeddings. As shown in Fig. 4,
ComE is generally better than the baselines in terms of both
macro-F1 and micro-F1. Specifically, ComE improves the
best baselines by relatively 9.52%–43.5% (macro-F1) and
6.9%–19.4% (micro-F1), when using 70% (BlogCatalog and
Wikipedia) and 8% (Flickr) of nodes for training. Our student t-tests show that all the above relative improvements are
significant over the 10 data splits, with one-tailed p-values always less than 0.01. It is interesting to see ComE improves
the baselines on node classification, since community embedding is after all unsupervised and it does not directly optimize
the classification loss. This suggests that the higher-order

0.3
0.2
0.1
10% 30% 50% 70% 90%

Flickr

0.2
0.15

4%

6%

2%
0.6

0.05

0.1
0.05
30%

10% 30% 50% 70% 90%

ComE
node2vec

Pipeline
GraRep

Flickr

0.35
0.3
0.25
0.2
0.15
0.1

8% 10%

Wikipeida

0
010%

BlogCatalog

0.4

0.2
0.15
0.1
0.05
0.2
0
10% 30% 50% 70% 90%

GraRep
SAE

BlogCatalog
Micro-F1

0.9

BlogCatalog

0.25
0.25

Micro-F1

0.95

10%
0.324547
0.276034
0.298288
0.281179

Micro-F1

Micro‐F1
2%
4%
6%
8%
0.308316 0.31426 0.318657 0.321737
0.243765 0.260712 0.268505 0.27267
0.28304 0.289691 0.293584 0.295397
0.268847 0.276569 0.278948 0.281262

ComEmbed
Pipeline
DeepWalk
LINE
node2vec
GraRep
SAE

1

Conductance

0.005

Macro-F1

node2vec
GraRep
SAE

4%

6%

8% 10%

Wikipedia

0.4
0.2

50%

0
70%
90%
10% 30% 50% 70% 90%

DeepWalk
SAE

LINE

Figure 4: Results on node classification. The bigger macroF1 and micro-F1 are, the better.
proximity from community embedding does contribute to a
better node embedding.

5.3

Model Study

We test different values for the model parameters α and β. As
shown in Fig. 5, generally α = 0.1 gives the best results for
community prediction and node classification. This suggests
keeping an appropriate trade off for the second-order proximity in the objective function is necessary. β = 0.1 is generally
the best for both tasks. In general, when α and β are within
the range of [0.001, 1], the model performance is quite robust.
We further validate the convergence and efficiency of ComE.
As shown in Fig 6, the loss of ComE (normalized by |V |)
converges quickly within a few iterations and the processing
time of ComE is linear to the graph size (i.e., |V | and |E|).

6

Conclusion

In this paper, we study the problem of embedding communities on graph. The problem is new because most graph
embedding methods focus on individual nodes, instead of a
group of nodes. We observe that community embedding and
node embedding reinforce each other. On one hand, a good
community embedding helps to get a good node embedding,
because it preserves the community structure during embedding. On the other hand, a good node embedding also helps
to get a good community embedding, as clustering is then
done over the nodes with good representations. We jointly
optimize node embedding and community embedding. We
evaluate our method on the real-world data sets, and show
that it outperforms the state-of-the-art baselines by at least
2.5%–7.8% (NMI) and 1.1%–2.8% (conductance) in community prediction, 9.52%–43.5% (macro-F1) and 6.9%–19.4%

0.88

0.87
0.87

0.3

NMI

0.4

0.85

0.88

0.83

0.87
0.87
0.81

0.85

0.850.001

0.86

0.01

0.1

1

0.840.83

[Belkin and Niyogi, 2001] Mikhail Belkin and Partha
Niyogi. Laplacian eigenmaps and spectral techniques for
embedding and clustering. In NIPS, pages 585–591, 2001.

0.30.1
0.2

0.25

0.01

0.1

0.84

0.15

0.25
0.82

0.01

Macro-F1

0.1
0.83
0.2

0.81
0.05
0.15
0.82
0.001
0.001

0.001

0.1
0.45
0.001

1

0.1 0.01 1

Macro-F1

0.81
0.85

0.830.20.001

0.1

References

0.40.2

0.860.89

NMI

Conductance
Conductance
Macro-F1
Conductance
Macro-F1
Conductance

0.89

0.01

α (BlogCatalog)
β (Flickr)

0.1

0.1

1

1

0.35

0.45

0.25

0.35 0.001
0.1 0.01

0.81
0.25
0.05
α (BlogCatalog)
β (BlogCatalog)
0.001
0.1
0.001
0.001 0.01
0.1 0.01 1

β (Flickr)

0.01

α (Wikipedia)

β (BlogCatalog)
α (Wikipedia)

0.1

11

α (Flickr)
0.1
11
β (Wikipedia)

0.01

α (Flickr)
β (Wikipedia)

Figure 5: Impact of the parameters α and β. By default, α =
0.1, β = 0.1.

BlogCatalog

1200

Time (Seconds)

Time
(Seconds)
Loss

1200
Convergence
1000
300
800
200
600
400
100
200
0
0
1 2 3 4 5 6 7 8 9 10
25%
Iteration 50%

Flickr

Efficiency

800
400
0
25%
75% 50%

75% 100%
Data Percentage 100%

Wikipedia

Figure 6: Model’s Convergence and Efficiency
(micro-F1) in node classification.

[Bishop, 2006] Christopher M. Bishop. Pattern Recognition
and Machine Learning (Information Science and Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA,
2006.
[Cao et al., 2015] Shaosheng Cao, Wei Lu, and Qiongkai
Xu. Grarep: Learning graph representations with global
structural information. In CIKM, pages 891–900, 2015.
[Cavallari et al., 2017] Sandro Cavallari, Vincent W. Zheng,
Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. Learning community embedding with community detection and node embedding on graphs. In CIKM, 2017.
[Chang and Lin, 2011] Chih-Chung Chang and Chih-Jen
Lin. Libsvm: A library for support vector machines. ACM
Trans. Intell. Syst. Technol., 2(3):27:1–27:27, May 2011.
[Chang et al., 2015] Shiyu Chang, Wei Han, Jiliang Tang,
Guo-Jun Qi, Charu C. Aggarwal, and Thomas S. Huang.
Heterogeneous network embedding via deep architectures.
In KDD, pages 119–128, 2015.
[Cox and Cox, 2000] Trevor F. Cox and M.A.A. Cox. Multidimensional Scaling, Second Edition. Chapman and
Hall/CRC, 2 edition, 2000.
[Fang et al., 2016] Hanyin Fang, Fei Wu, Zhou Zhao, Xinyu
Duan, Yueting Zhuang, and Martin Ester. Communitybased question answering via heterogeneous social network learning. In AAAI, pages 122–128, 2016.
[Grover and Leskovec, 2016] Aditya Grover and Jure
Leskovec.
node2vec: Scalable feature learning for
networks. In KDD, 2016.
[Kloster and Gleich, 2014] Kyle Kloster and David F. Gleich. Heat kernel based community detection. In KDD,
pages 1386–1395, 2014.
[Kozdoba and Mannor, 2015] Mark Kozdoba and Shie Mannor. Community detection via measure space embedding.
In NIPS, pages 2890–2898, 2015.
[Liu et al., 2017] Zemin Liu, Vincent W. Zheng, Zhou Zhao,
Fanwei Zhu, Kevin Chen-Chuan Chang, Minghui Wu, and
Jing Ying. Semantic proximity search on heterogeneous
graph by proximity embedding. In AAAI, 2017.
[Luo et al., 2015] Yuanfei Luo, Quan Wang, Bin Wang, and
Li Guo. Context-dependent knowledge graph embedding.
In EMNLP, pages 1656–1661, 2015.
[Mikolov et al., 2013] Tomas Mikolov, Ilya Sutskever, Kai
Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed
representations of words and phrases and their compositionality. In NIPS, pages 3111–3119, 2013.
[Niepert et al., 2016] Mathias Niepert, Mohamed Ahmed,
and Konstantin Kutzkov. Learning convolutional neural
networks for graphs. In ICML, pages 2014–2023, 2016.

[Ou et al., 2016] Mingdong Ou, Peng Cui, Jian Pei, Ziwei
Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In KDD, pages 1105–1114, 2016.
[Perozzi et al., 2014] Bryan Perozzi, Rami Al-Rfou, and
Steven Skiena. Deepwalk: Online learning of social representations. In KDD, pages 701–710, 2014.
[Roweis and Saul, 2000] Sam T. Roweis and Lawrence K.
Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000.
[Tang et al., 2015] Jian Tang, Meng Qu, Mingzhe Wang,
Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Largescale information network embedding. In WWW, pages
1067–1077, 2015.
[Tenenbaum et al., 2000] Joshua B. Tenenbaum, Vin
de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction.
Science, 290(5500):2319–2323, 2000.
[Tian et al., 2014] Fei Tian, Bin Gao, Qing Cui, Enhong
Chen, and Tie-Yan Liu. Learning deep representations for
graph clustering. In AAAI, pages 1293–1299, 2014.
[Wang et al., 2016] Daixin Wang, Peng Cui, and Wenwu
Zhu. Structural deep network embedding. In KDD, pages
1225–1234, 2016.
[Xie et al., 2016] Ruobing Xie, Zhiyuan Liu, Jia Jia, Huanbo
Luan, and Maosong Sun. Representation learning of
knowledge graphs with entity descriptions. In AAAI, pages
2659–2665, 2016.
[Yang et al., 2016] Liang Yang, Xiaochun Cao, Dongxiao
He, Chuan Wang, Xiao Wang, and Weixiong Zhang. Modularity based community detection with deep learning. In
IJCAI, pages 2252–2258, 2016.
[Zachary, 1977] Wayne W. Zachary. An information flow
model for conflict and fission in small groups. Journal
of Anthropological Research, 33(4):452–473, 1977.

