CONE: Community Oriented Network Embedding

Carl Yang, Hanqing Lu, Kevin Chen-Chuan ChangarXiv 2017 · arXiv

TL;DR

CONE (Community Oriented Network Embedding) challenges the long-standing assumption that communities must be dense or homogeneous clusters. By using a deep learning framework that combines Recurrent Neural Networks (RNNs) for node content and random walks for network structure, it learns to identify complex "social patterns" from just a few labeled examples, significantly outperforming traditional unsupervised methods.

What Problem Does This Paper Address?

For decades, community detection has relied on two heuristic assumptions: edge density (nodes in a community are tightly packed) and node homogeneity (nodes in a community are similar).

The authors argue—and demonstrate through data analysis—that these assumptions are often wrong. Consider a research group: a professor (the "star" center) might be connected to many students, but those students might not interact with each other at all (low density). Furthermore, the professor and students have very different ages and roles (low homogeneity).

The Professor-Student social pattern illustrating low density and low homogeneity.

Traditional algorithms like MinCut or BigClam struggle here because they are looking for "clumps" rather than "patterns." CONE addresses this by moving from unsupervised heuristics to a supervised embedding approach that learns what a community "looks like" from ground-truth examples.

Methods

CONE is an end-to-end deep learning architecture designed to capture "fuzzy" social patterns. Its pipeline consists of three main components:

  1. Content Expressive Layer (RNN): Instead of simple feature vectors, CONE uses LSTMs to process node attributes (like tweets or profile info). This allows the model to handle high-dimensional, noisy, and sequential data, capturing the "signatures" of different social roles.
  2. Structure Aware Layer (Random Walk Regularization): To capture the "shape" of the network, the model uses $k$-step random walk transition probabilities. This recomputes a node's embedding based on its local neighborhood, effectively "collecting" information from nearby nodes to identify structures like stars or bridges.
  3. Community Oriented Layer (Softmax Supervision): The model is trained using a small set of example communities. It uses a point-wise softmax prediction with cross-entropy loss. This forces nodes belonging to the same community to have similar embeddings in the latent space, allowing the model to "memorize" and then "recognize" similar social patterns elsewhere in the network.

Datasets

The researchers evaluated CONE on three real-world datasets:

  • Facebook: 10 ego-networks with 4,039 nodes. This is a high-quality dataset where communities (social circles) were manually labeled by users.
  • Twitter: A larger dataset of 973 ego-networks (81,306 nodes) where communities were derived from user-created friend lists.
  • Flickr: A network of 35,313 nodes where communities are defined by user-joined groups and attributes are image tags.

Key Insights and Ideas

  • The "Aha!" Moment on Heuristics: The authors show that in the Facebook ground-truth data, many communities actually have very low density. This proves that "machine-generated" ground truths used in other papers (which rely on density) have created a circular logic that CONE finally breaks.
Density distributions of ground-truth communities versus traditional detection algorithms.
  • Patterns over Proximity: Traditional embedding methods (like DeepWalk) try to make nearby nodes similar. CONE realizes that two nodes don't need to be "similar" in content to be in the same community; they just need to fit into a recognized structural pattern (like the Professor/Student relationship).
  • Weak Supervision is Enough: One of the most surprising findings is how little data CONE needs. On the Twitter dataset, the model's performance converged after seeing only 6% of the labeled communities.

Key Results

CONE consistently outperformed both traditional community detection algorithms and modern network embedding baselines:

  • Massive Gains on Facebook: CONE achieved a 30% relative improvement in F1 and Jaccard scores over the next best baseline (CESNA). This is attributed to the high-quality human labels in the Facebook data, which allowed CONE to learn genuine social patterns.
  • Robustness to Noise: On the Flickr and Twitter datasets, where content is high-dimensional and "messy," CONE’s RNN-based approach allowed it to maintain a lead over methods that use simpler attribute models.
  • Pattern Discovery: In case studies, CONE successfully identified "co-star" patterns (multiple centers connected to the same group) across different parts of a network, a feat that unsupervised baselines failed to replicate.

Limitations and Future Work

  • Dependency on Labels: While CONE requires very little supervision, it still requires some ground-truth communities to start the learning process.
  • Computational Overhead: The use of RNNs and $k$-step random walk matrices is more computationally intensive than simple heuristic methods, though the authors note it is easily parallelizable on GPUs.
  • Dynamic Networks: The paper focuses on static snapshots of networks. Extending this to dynamic, rapidly evolving social networks remains an open challenge.

Summary updated

Abstract

Detecting communities has long been popular in the research on networks. It is usually modeled as an unsupervised clustering problem on graphs, based on heuristic assumptions about community characteristics, such as edge density and node homogeneity. In this work, we doubt the universality of these widely adopted assumptions and compare human labeled communities with machine predicted ones obtained via various mainstream algorithms. Based on supportive results, we argue that communities are defined by various social patterns and unsupervised learning based on heuristics is incapable of capturing all of them. Therefore, we propose to inject supervision into community detection through Community Oriented Network Embedding (CONE), which leverages limited ground-truth communities as examples to learn an embedding model aware of the social patterns underlying them. Specifically, a deep architecture is developed by combining recurrent neural networks with random-walks on graphs towards capturing social patterns directed by ground-truth communities. Generic clustering algorithms on the embeddings of other nodes produced by the learned model then effectively reveals more communities that share similar social patterns with the ground-truth ones.
BibTeX
@misc{yang2017cone,
  author = {Carl Yang and Hanqing Lu and Kevin Chen-Chuan Chang},
  title = {{CONE: Community Oriented Network Embedding}},
  year = {2017},
  eprint = {1709.01554},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.01554},
}
Figure