Community-enhanced Network Representation Learning for Network Analysis

Cunchao Tu, Hao Wang, Xiangkai Zeng, Zhiyuan Liu, Maosong SunarXiv 2016 · arXiv

Abstract

Network Representation Learning (NRL) typically focuses on local neighborhood structures, often overlooking global patterns such as community structures. We present Community-enhanced Network Representation Learning (CNRL), a framework that integrates global community information with local context to produce more discriminative node embeddings. By treating communities as latent "topics" within random walk sequences, CNRL effectively addresses the "local-sighted" limitation of existing methods. Our experiments demonstrate that CNRL significantly outperforms state-of-the-art models in vertex classification, link prediction, and community detection, particularly in sparse network scenarios.

Introduction

The goal of Network Representation Learning (NRL) is to map nodes into a low-dimensional vector space while preserving the network's structural properties. While popular methods like DeepWalk and LINE have shown success, they primarily capture local neighborhood information. This "local-sightedness" fails to account for global community structures—groups of nodes that are densely connected and often share functional or thematic similarities. This omission is especially detrimental for "long-tail" nodes with sparse local connections, where global context could provide critical missing information.

The CNRL Framework

CNRL addresses these limitations by drawing an analogy between network walks and natural language processing (NLP). In this paradigm, a random walk sequence is treated as a "sentence," a vertex as a "word," and a community as a "topic."

The CNRL framework workflow, illustrating the transition from random walks to community-enhanced vertex embeddings.

The framework consists of several key components:

  • Joint Learning: CNRL simultaneously optimizes the community distribution of each vertex and the embeddings for both vertices and communities.
  • Community Assignment: Each vertex in a sequence is assigned to a community using either a statistic-based approach (e.g., Gibbs sampling) or an embedding-based approach that calculates membership probability from learned vectors.
  • Extended Objective Function: The model adapts the Skip-Gram objective to predict a neighbor based on both the target vertex and its assigned community, effectively incorporating global priors.
  • Enhanced Representation: The final node embedding is a concatenation of its specific vertex vector and a "community vector," representing a weighted sum of its community memberships.

Experimental Evaluation

We evaluated CNRL on four real-world datasets: Cora, Citeseer, Wiki, and BlogCatalog. These datasets range from sparse citation networks to dense social networks, providing a robust testbed for the framework. No new benchmarks were introduced, but these represent a good mix of structural densities.

Key Results and Discussion

CNRL consistently outperformed baseline methods like DeepWalk and LINE across all tasks.

  • Vertex Classification: As shown in the performance plots, CNRL maintains high accuracy even when training data is extremely sparse (e.g., 10%). This confirms that global community information acts as a powerful regularizer for nodes with few local connections.
  • Link Prediction: In highly sparse graphs (80% edges removed), CNRL exhibited significantly higher resilience than traditional methods, with performance dropping by only 5% compared to 25% for baselines.
  • Community Detection: Using modified modularity as a metric, the embedding-based variant (E-CNRL) outperformed specialized community detection algorithms like BigCLAM, demonstrating the richness of the learned representations.

Conclusion and Future Directions

CNRL successfully bridges the gap between local neighborhood context and global community structure in network representation learning. By leveraging the "community-as-topic" analogy, it produces embeddings that are both locally precise and globally aware. Future work will explore the integration of node attributes (e.g., text or metadata), adaptation to semi-supervised settings, and extension to heterogeneous networks with multiple entity and relation types.

Summary updated

Abstract

Network representation learning (NRL) aims to learn low-dimensional vectors for vertices in a network. Most existing NRL methods focus on learning representations from local context of vertices (such as their neighbors). Nevertheless, vertices in many complex networks also exhibit significant global patterns widely known as communities. It's intuitive that vertices in the same community tend to connect densely and share common attributes. These patterns are expected to improve NRL and benefit relevant evaluation tasks, such as link prediction and vertex classification. Inspired by the analogy between network representation learning and text modeling, we propose a unified NRL framework by introducing community information of vertices, named as Community-enhanced Network Representation Learning (CNRL). CNRL simultaneously detects community distribution of each vertex and learns embeddings of both vertices and communities. Moreover, the proposed community enhancement mechanism can be applied to various existing NRL models. In experiments, we evaluate our model on vertex classification, link prediction, and community detection using several real-world datasets. The results demonstrate that CNRL significantly and consistently outperforms other state-of-the-art methods while verifying our assumptions on the correlations between vertices and communities.
BibTeX
@misc{tu2016community,
  author = {Cunchao Tu and Hao Wang and Xiangkai Zeng and Zhiyuan Liu and Maosong Sun},
  title = {{Community-enhanced Network Representation Learning for Network Analysis}},
  year = {2016},
  eprint = {1611.06645},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.06645},
}
Figure