IEEE Computational Intelligence Magazine - August 2019 - 42

K = 2 and embed the two overlapping
communities in the 2D space.
We summarize our contributions as
follows:
❏ We contribute with a comprehensive
literature review and complexity
analysis summarized in Tab. I.
❏ We further extend ComE to ComE+
to better handle the unknown number of communities for community
embedding. To the best of our knowledge, this is the first node embedding
model able to automatically infer the
number of communities from the
data distribution while preserving
this structure during the embedding process.
❏ We designed a new variational inference model for ComE+ while maintaining the inference algorithm
complexity as low as O ( ;V ; + ; E ; ).
❏ We evaluate ComE+ on seven public
real-world datasets with various
application tasks. We relatively
improve state-of-the-art baselines
across datasets by at least 0.3%-17.1%
(Conductance) and 0.8%-6.7%
(NMI) in community detection,
0.8%-25.4% (Macro-F1) and 0.3%-
34.7% (Micro-F1) in node classification. Detailed settings for these
improvements are reported in Sec. V.
II. Related Work

As our task uses graphs as input, we
first review the literature on graph
embedding. Then we review the literature on community detection since it is
our key notion. Finally, as we use a
Bayesian definition for community
embedding, we review the literature on
Bayesian embedding.
A. Graph Embedding

Most graph embedding work focuses
on nodes [28]-[30]. For example, earlier
methods, such as Laplacian eigenmap
[31] and IsoMap [32], aim to preserve
first-order proximity by extracting leading eigenvectors of a graph affinity
matrix. Recent work starts to exploit
deep learning to learn node representations. For example, DeepWalk [3], models second-order proximity based on
path sampling, and it has an inference

42

complexity of O ( ;V ; log ;V ; ). Node2Vec [13] extends DeepWalk with a
controlled path sampling process, which
requires an additional O ( ;V ; a 2 ) factor
where a is the average degree of the
graph. LINE [16] and SDNE [17] preserve both first- and second-order
proximity at the price of a higher complexity with O ( a ; E ; ) and O ( a ;V ; ),
respectively. Both metapath2vec [19]
and struct2vec [18] consider secondorder proximity for node embedding.
GraRep [2] and HOPE [33] preserve
high-order proximity by learning node
embedding from multi-step Katz index
matrix or PageRank matrix. Particularly, GraRep runs Singular Value Decomposition (SVD), which requires
O ( ;V ;3 ) in general. Compared with our
ComE and ComE+, the above work
neither explicitly detects nor represents
the communities.
Community structure is an important network property, yet it is underexplored in graph embedding. For example,
SAE [6] builds a normalized similarity
matrix with complexity O ( ; E ; ), and
learns node embedding by reconstructing the matrix by stacked Auto-Encoder
with O ( ;V ;) complexity. It further
applies K-means clustering to detect the
communities. DNR [7] constructs a
modularity matrix from the graph with
O ( ;V ;2 ) complexity, then it applies
stacked Auto-Encoder on the matrix
with must-link supervision to generate
node embedding. PRUNE [20] constructs a Pointwise Mutual Information
(PMI) matrix to model global node
ranking and first-order proximity by
O ( ; E ; ). Both the PMI matrix and the
edge representation are argued to
implicitly preserve the community
structure as well as the second-order
proximity. There is limited work on
explicitly modeling communities i n
g r a p h e m b e d d i n g . Fo r e x a m p l e,
M-NMF [15] constructs the modularity
matrix with O ( ;V ;2 ) complexity, then
applies non-negative matrix factorization to learn node embedding and
detect communities together with
O ( ;V ;2 ) again. Compared with our
work, M-NMF uses the modularity as a
distance metric and embeds each com-

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2019

munity with a vector instead of a distribution; thus it is unable to fully characterize
the community. Finally, refer to [1] for a
comprehensive survey on graph embedding methods.
B. Community Detection

Community detection aims to discover
groups of nodes in a graph, such that the
intra-group connections are denser than
the inter-group ones [34]. Most of existing work first embeds the nodes in a
low-dimensional space by either feature
engineering, graph embedding or linear
coding [35]. Then they apply clustering,
e.g., spectral clustering [12], Laplacian
regularized GMM [36] or neural networks [6], [14], on the nodes for community detection. Despite the success of
these methods, their results are suboptimal since their node embedding
does not explicitly consider the community structure.
Recent work advances community
detection by exploiting rich types of
interaction on a social network such as
content [37], attributes [38] and information diffusion [39]. Additionally, some
methods exploit opportunities of coupling community detection with other
tasks, such as hole spanner detection
[40] or social role detection [41]. Comparatively, we are different in that: 1) we
particularly consider graph embedding,
whereas the above community detection
work generally does not; 2) we focus on
the most basic graph setting where we
have a homogeneous graph as input,
whereas some community detection
work may require additional inputs of
the graph.
C. Bayesian Embedding

Most graph embedding tries to embed a
node into a "point" vector space [3], [42].
As a community has to characterize both
what its member nodes are and how
they spread, we consider a Bayesian definition of community embedding. That is:
we define each community embedding
as a distribution rather than a point in
the low-dimensional space. Little work
considers Bayesian embedding. For
example, GenVector [43] embeds each
social network user and each word as a
IEEE Computational Intelligence Magazine - August 2019

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