Embedding Both Finite and Infinite Communities on Graphs [Application Notes]

Sandro Cavallari, Erik Cambria, Hongyun Cai, Kevin Chen-Chuan Chang, Vincent W. Zheng

Research output: Contribution to journalArticle

Abstract

In 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 shows that ComE+ improves the stateof- the-art baselines in various application tasks, e.g., community detection and node classification.

Original languageEnglish (US)
Article number8764640
Pages (from-to)39-50
Number of pages12
JournalIEEE Computational Intelligence Magazine
Volume14
Issue number3
DOIs
StatePublished - Aug 2019

Fingerprint

Graph in graph theory
Visualization
Community Detection
Vertex of a graph
Community
Unknown
Graph Embedding
Low Complexity
Closed-loop
Proximity
Baseline
Assignment
Optimise
Higher Order
Evaluation
Interaction
Model

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Artificial Intelligence

Cite this

Embedding Both Finite and Infinite Communities on Graphs [Application Notes]. / Cavallari, Sandro; Cambria, Erik; Cai, Hongyun; Chang, Kevin Chen-Chuan; Zheng, Vincent W.

In: IEEE Computational Intelligence Magazine, Vol. 14, No. 3, 8764640, 08.2019, p. 39-50.

Research output: Contribution to journalArticle

Cavallari, Sandro ; Cambria, Erik ; Cai, Hongyun ; Chang, Kevin Chen-Chuan ; Zheng, Vincent W. / Embedding Both Finite and Infinite Communities on Graphs [Application Notes]. In: IEEE Computational Intelligence Magazine. 2019 ; Vol. 14, No. 3. pp. 39-50.
@article{1573c51d86004034bebd6c0aa96fc16d,
title = "Embedding Both Finite and Infinite Communities on Graphs [Application Notes]",
abstract = "In 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 shows that ComE+ improves the stateof- the-art baselines in various application tasks, e.g., community detection and node classification.",
author = "Sandro Cavallari and Erik Cambria and Hongyun Cai and Chang, {Kevin Chen-Chuan} and Zheng, {Vincent W.}",
year = "2019",
month = "8",
doi = "10.1109/MCI.2019.2919396",
language = "English (US)",
volume = "14",
pages = "39--50",
journal = "IEEE Computational Intelligence Magazine",
issn = "1556-603X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "3",

}

TY - JOUR

T1 - Embedding Both Finite and Infinite Communities on Graphs [Application Notes]

AU - Cavallari, Sandro

AU - Cambria, Erik

AU - Cai, Hongyun

AU - Chang, Kevin Chen-Chuan

AU - Zheng, Vincent W.

PY - 2019/8

Y1 - 2019/8

N2 - In 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 shows that ComE+ improves the stateof- the-art baselines in various application tasks, e.g., community detection and node classification.

AB - In 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 shows that ComE+ improves the stateof- the-art baselines in various application tasks, e.g., community detection and node classification.

UR - http://www.scopus.com/inward/record.url?scp=85069786703&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069786703&partnerID=8YFLogxK

U2 - 10.1109/MCI.2019.2919396

DO - 10.1109/MCI.2019.2919396

M3 - Article

AN - SCOPUS:85069786703

VL - 14

SP - 39

EP - 50

JO - IEEE Computational Intelligence Magazine

JF - IEEE Computational Intelligence Magazine

SN - 1556-603X

IS - 3

M1 - 8764640

ER -