Distributed Representation of Subgraphs

Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, B. Aditya Prakash

Abstract

Traditional graph representation learning focuses on embedding individual nodes into vector spaces. However, many network analysis tasks, such as community detection and cascade analysis, are inherently subgraph-centric. We present Sub2Vec, an unsupervised framework that learns low-dimensional representations of arbitrary subgraphs. By adapting paragraph vector models from natural language processing, Sub2Vec preserves local structural proximity—the principle that subgraphs sharing significant nodes, edges, and paths should reside closely in the embedding space. Experimental results demonstrate that Sub2Vec significantly outperforms node-based baselines, achieving up to a 4x improvement in community detection tasks.

Introduction

Most existing graph embedding techniques, such as DeepWalk and Node2Vec, are designed to represent individual nodes. While effective for node-level classification, these methods often fail to capture the collective structural properties of groups of nodes. This limitation is particularly evident in tasks where the unit of analysis is a subgraph. The primary challenge addressed by this work is the lack of a scalable, unsupervised method to represent subgraphs as continuous vectors while maintaining their structural relationships.

Methods

Sub2Vec treats subgraphs as "paragraphs" and nodes as "words," leveraging the conceptual framework of Paragraph Vectors (Doc2Vec). The algorithm introduces two primary architectures:

  1. Sub2Vec-DM (Distributed Memory): This model predicts a target node by considering both the subgraph identifier and the node's local neighborhood.
  2. Sub2Vec-DBON (Distributed Bag of Nodes): Similar to the Skip-gram architecture, this variant predicts the entire neighborhood of nodes given only the subgraph identifier.

Subgraph Truncated Random Walks

To handle the non-linear nature of graphs, Sub2Vec employs Subgraph Truncated Random Walks. Unlike standard random walks that traverse the entire network, these walks are strictly confined within the boundaries of a specific subgraph. This process effectively "linearizes" the subgraph's structure into sequences suitable for neural language models.

The Sub2Vec framework: from a network G to learned subgraph embeddings.

The theoretical foundation of Sub2Vec is rooted in matrix factorization; the objective function is shown to be equivalent to factorizing a matrix where entries represent the overlap of paths between subgraphs.

Experimental Evaluation

The researchers evaluated Sub2Vec across diverse real-world datasets, including social networks (WorkPlace, HighSchool, Facebook), web networks (WebKB, PolBlogs), and co-authorship networks (Astro-PH, DBLP).

Key Results

  • Community Detection: Sub2Vec consistently outperformed traditional baselines like Louvain and Node2Vec. In dense interaction networks, it achieved F-1 scores up to 4x higher than competing methods.
  • Link Prediction: The model showed significant gains in predicting future edges, particularly in sparse networks where common neighbors provide a strong structural signal.
  • Scalability: The algorithm's complexity grows linearly with the number of subgraphs, making it applicable to large-scale networks such as YouTube.
  • Interpretability: Qualitative analysis using t-SNE visualizations of DBLP subgraphs revealed that related research topics (e.g., "SVM" and "classification") naturally cluster together in the embedding space.

Discussion and Future Work

Sub2Vec excels at capturing Local Proximity, which relies on overlapping nodes and edges. However, this focus presents limitations in extremely sparse networks where such overlap is minimal. Future research directions include incorporating Structural Proximity (similarity in shape/topology regardless of node identity) and Positional Proximity (similarity in global network location) to create even more robust subgraph representations.

Summary updated

Abstract

Network embeddings have become very popular in learning effective feature representations of networks. Motivated by the recent successes of embeddings in natural language processing, researchers have tried to find network embeddings in order to exploit machine learning algorithms for mining tasks like node classification and edge prediction. However, most of the work focuses on finding distributed representations of nodes, which are inherently ill-suited to tasks such as community detection which are intuitively dependent on subgraphs. Here, we propose sub2vec, an unsupervised scalable algorithm to learn feature representations of arbitrary subgraphs. We provide means to characterize similarties between subgraphs and provide theoretical analysis of sub2vec and demonstrate that it preserves the so-called local proximity. We also highlight the usability of sub2vec by leveraging it for network mining tasks, like community detection. We show that sub2vec gets significant gains over state-of-the-art methods and node-embedding methods. In particular, sub2vec offers an approach to generate a richer vocabulary of features of subgraphs to support representation and reasoning.
BibTeX
@misc{adhikari2017distributed,
  author = {Bijaya Adhikari and Yao Zhang and Naren Ramakrishnan and B. Aditya Prakash},
  title = {{Distributed Representation of Subgraphs}},
  year = {2017},
  eprint = {1702.06921},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.06921},
}
Figure