IEEE Computational Intelligence Magazine - August 2019 - 39

Sandro Cavallari
School of Computer Science and Engineering,
Nanyang Technological University, SINGAPORE
Erik Cambria
School of Computer Science and Engineering,
Nanyang Technological University, SINGAPORE
Hongyun Cai
Advanced Digital Sciences Center, SINGAPORE
Kevin Chen-Chuan Chang
Department of Computer Science, University of
Illinois at Urbana- Champaign, USA
Vincent W. Zheng
Advanced Digital Sciences Center, SINGAPORE

Embedding Both Finite and Infinite Communities on Graphs
Abstract

n this paper, we introduce a new setting for graph embedding, which
considers embedding communities
instead of individual nodes. We find that
community embedding is not only useful
for community-level applications such as
graph visualization but also provide an
exciting opportunity to improve community detection and node classification.
Specifically, we consider the interaction
between community embedding and
detection as a closed loop, through node
embedding. On the one hand, node
embedding can improve community
detection since the detected communities

are used to fit a community embedding.
On the other hand, community embedding can be used to optimize node
embedding by introducing a community-aware high-order proximity. However,
in practice, the number of communities
can be unknown beforehand; thus we
extend our previous Community
Embedding (ComE) model. We propose
ComE+, a new model which handles
both: the unknown truth community
assignments and the unknown number of
communities present in the dataset. We
further develop an efficient inference
algorithm for ComE+ for keeping complexity low. Our extensive evaluation

©ISTOCKPHOTO.COM/AELITTA

Digital Object Identifier 10.1109/MCI.2019.2919396
Date of publication: 17 July 2019

Corresponding Author: Vincent W. Zheng (Email:
vincent.zheng@adsc-create.edu.sg).

shows that ComE+ improves the stateof-the-art baselines in various application
tasks, e.g., community detection and
node classification.
I. Introduction

Graphs are a representational framework
for many real-world applications, e.g.,
social media analytics, user's interest diffusion, knowledge representation and
extraction, protein interaction, and others. Analyzing such graphs is a key factor
to take strategic decisions. Thus, it has
received significant attention in the last
few decades. Traditionally, graph embedding, which aims to represent a graph
structure on a d-dimensional space preserving some predefined graph's properties, became a popular technique to
extract the hidden knowledge present in
such a rich structure. However, to date
research has primarily focused on a
node level representation where each
node is associated to a vector, such that
two "related" nodes have similar vector
representations [1].
While most of the previous works
focus on the microscopic architectures
formed between nodes [2]-[9], in this
paper, we also focus on preserving the
communities structures formed by densely connected nodes. Community embedding is useful for many community-level

AUGUST 2019 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

http://www.ISTOCKPHOTO.COM/AELITTA

IEEE Computational Intelligence Magazine - August 2019

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