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:
- Sub2Vec-DM (Distributed Memory): This model predicts a target node by considering both the subgraph identifier and the node's local neighborhood.
- 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 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