PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Representation Learning: A Survey

Daokun Zhang, Jie Yin, Xingquan Zhu, Chengqi Zhang

arXiv:1801.05852v3cs.SIcs.LGstat.ML

TL;DR

Large information networks make conventional analysis computationally expensive, while existing surveys provide limited multifaceted comparison and resource coverage. This paper surveys network representation learning through new taxonomies, algorithmic and complexity analyses, benchmark evaluations, and research directions. Its synthesis reports that content augmentation can substantially improve performance on attributed networks, while labeled methods can gain significantly with limited labels.

  • Problem

    Large information networks make analysis computationally expensive, and existing surveys lack multifaceted taxonomies, in-depth complexity and empirical comparisons, and resource summaries.

  • Method

    The survey categorizes NRL methods by learning setting, preserved information, mechanisms, and methodologies, then reviews algorithms, resources, evaluations, complexity, and future directions.

  • Results

    Content-augmented NRL performs much better than structure-only methods on attributed networks, while some supervised strategies achieve significant gains with 10% labeled vertices.

  • Takeaways & Limitations

    NRL research can be compared through shared taxonomies, benchmark protocols, empirical results, complexity analyses, and publicly available resources.

  • Takeaways & Limitations

    Current research mainly targets static, homogeneous networks, leaving dynamic and heterogeneous settings insufficiently studied.

Abstract

from arXiv · show

With the widespread use of information technologies, information networks are becoming increasingly popular to capture complex relationships across various disciplines, such as social networks, citation networks, telecommunication networks, and biological networks. Analyzing these networks sheds light on different aspects of social life such as the structure of societies, information diffusion, and communication patterns. In reality, however, the large scale of information networks often makes network analytic tasks computationally expensive or intractable. Network representation learning has been recently proposed as a new learning paradigm to embed network vertices into a low-dimensional vector space, by preserving network topology structure, vertex content, and other side information. This facilitates the original network to be easily handled in the new vector space for further analysis. In this survey, we perform a comprehensive review of the current literature on network representation learning in the data mining and machine learning field. We propose new taxonomies to categorize and summarize the state-of-the-art network representation learning techniques according to the underlying learning mechanisms, the network information intended to preserve, as well as the algorithmic designs and methodologies. We summarize evaluation protocols used for validating network representation learning including published benchmark datasets, evaluation methods, and open source algorithms. We also perform empirical studies to compare the performance of representative algorithms on common datasets, and analyze their computational complexity. Finally, we suggest promising research directions to facilitate future study.

1 INTRODUCTION

Network representation learning addresses the computational difficulty of analyzing large information networks by learning low-dimensional vertex representations that preserve network information. This survey organizes the field, evaluates representative methods and resources, and identifies future research directions.

  • Information networks span social, citation, telecommunication, and biological applications, but their scale can reach millions or billions of vertices.
  • At least quadratic-time spectral methods become difficult to scale to networks with millions of vertices.
  • NRL learns low-dimensional vertex vectors while preserving topology, content, and side information for conventional vector-based analysis.
  • Challenges: NRL must jointly preserve local and global structure, incorporate vertex content appropriately, and remain efficient under large-scale computational constraints.
  • Contributions: The survey proposes multifaceted taxonomies, reviews state-of-the-art algorithms, summarizes datasets and evaluation protocols, compares performance and complexity, and suggests six research directions.
  • Related Surveys and Differences: Existing surveys are limited by single-taxonomy views, insufficient complexity and empirical analysis, and incomplete summaries of datasets and open-source algorithms.

2 NOTATIONS AND DEFINITIONS

This section defines information networks, proximity notions, vertex representations, and their desired properties. It also frames representation learning as mapping network vertices into a low-dimensional space while preserving relevant similarities.

  • An information network G = (V, E, X, Y) contains vertices, edges, vertex attributes, and vertex labels, which may be sparse or partially unobserved.
  • Proximity: First-order proximity captures direct neighbor relationships, while second-order and high-order proximity capture increasingly global multi-step relations.
  • Proximity: Structural role proximity links distant vertices that occupy similar neighborhood roles, such as chain ends, star centers, or community bridges.
  • NRL learns f: v 7−→ r_v ∈ R^d so vertices similar in the original network are similar in the learned vector space.
  • Representations should be low-dimensional, informative, and continuous, preserving proximity from structure, attributes, and available labels.
  • Taxonomy: The taxonomy separates unsupervised from semi-supervised learning by label availability, then distinguishes structure-only methods from those augmented with node content.

3 CATEGORIZATION

The survey categorizes network representation learning by supervision, information sources, and algorithmic methodology, then compares the resulting categories and trade-offs.

  • Learning settings: NRL methods are first divided into unsupervised and semi-supervised settings according to whether vertex labels are available.
  • Information sources: Unsupervised methods preserve network structure alone or combine structure with vertex attributes, while semi-supervised methods additionally use vertex labels.
  • Methodologies: The survey organizes methods into five algorithmic categories and compares their advantages and disadvantages.
  • Algorithmic categories: Matrix factorization methods construct matrices encoding network structure or attributes but face memory and computational scalability bottlenecks on massive networks.
  • Algorithmic categories: Random-walk methods learn representations from vertex-context sequences, whereas edge-modeling methods learn directly from vertex-vertex connections.
  • Algorithmic categories: Edge-modeling methods are more efficient than matrix-factorization and random-walk methods but cannot capture global structure from observable connectivity alone.

4 UNSUPERVISED NETWORK REPRESENTATION LEARNING

This section reviews unsupervised network representation learning methods in two subsections and then compares their key characteristics across categories.

  • The section separates unsupervised network representation learning methods into two subsections.
  • It then summarizes the methods’ key characteristics.
  • Finally, it compares differences across the two categories.

4.1 Unsupervised Structure Preserving Network Representation Learning

Structure-preserving NRL methods learn low-dimensional vertex representations that retain network structure, categorized by microscopic, mesoscopic, and macroscopic properties. Unsupervised methods include random-walk, proximity-modeling, matrix-factorization, and deep-learning approaches.

  • Scope and categorization: Structure-preserving NRL represents vertices similarly when they are close in the original network space.The survey categorizes preserved structure into microscopic, mesoscopic, and macroscopic network properties.
  • Microscopic structure: Microscopic structure includes first-order, second-order, and high-order proximity among neighboring or contextually related vertices.First-order proximity captures direct connections, while second-order and high-order proximity capture shared neighbors and related contexts.
  • Random-walk methods: DeepWalk generates random-walk sequences and applies Skip-Gram so vertices sharing similar contexts receive nearby representations.Because random-walk contexts describe neighborhood structure, DeepWalk preserves second-order and high-order proximity.
  • Proximity-modeling methods: LINE explicitly models first-order and second-order proximity, then concatenates the resulting representations as the final embedding.Its two objectives model edge-level relationships and neighbor-conditioned context distributions.
  • Matrix-factorization and deep methods: GraRep captures high-order proximity through separate k-step representations and concatenates them, whereas SDNE combines second-order reconstruction with first-order proximity constraints.SDNE uses a semi-supervised deep autoencoder and includes regularization to prevent overfitting.
  • Flexible and directed-network methods: node2vec uses biased random walks that interpolate between BFS and DFS to preserve second-order and high-order proximity more flexibly.HOPE instead targets asymmetric high-order proximity in directed networks with separate source and target embeddings.

4.2 Unsupervised Content Augmented Network Representation Learning

Content-augmented NRL incorporates vertex attributes alongside network structure to improve representation learning. The survey groups methods by coupling content through matrix factorization, nonlinear mappings, or attribute-preserving constraints.

  • Motivation: Vertex attributes provide content-level evidence for similarity and can improve NRL when incorporated into the learning process.Examples include webpage text, paper content, and user metadata.
  • Matrix-factorization methods: TADW couples network structure with textual features through inductive matrix factorization and concatenates W with HT as the final representation.The matrix M carries vertex-transition probabilities, while T is the vertex textual feature matrix.
  • Homophily, structure, and content: HSCA adds a regularization term for directly connected vertices, integrating homophily with structural context and vertex content.Its final representation is the concatenation of W and HT, with λ and µ controlling trade-offs in the objective.
  • Nonlinear mappings: pRBM combines binary vertex attributes and link information by learning hidden representations whose edge-weighted interactions encourage connected vertices to be close.The model uses a paired Restricted Boltzmann Machine and an energy-based joint probability.
  • Nonlinear mappings: UPP-SNE applies a nonlinear kernel mapping to noisy, sparse, incomplete, and topic-inconsistent user profiles, supervised by network context.The profile vector is mapped through sinusoidal features, while a DeepWalk objective complements profiles with network structure.
  • Attribute-preserving constraints: PPNE jointly optimizes structure-driven and attribute-driven objectives so representations preserve random-walk context and vertex-attribute similarity.The attribute objective uses positive and negative vertices selected by attribute similarity.
  • Summary: The survey summarizes three content-integration strategies: inductive matrix factorization, nonlinear embedding mappings, and attribute-preserving constraints.TADW and HSCA use the first strategy; pRBM and UPP-SNE use the second; PPNE uses the third.

TION LEARNING

Semi-supervised NRL incorporates vertex labels into representation learning to improve discriminative power. The surveyed methods combine structural objectives with classification, label-relation, probabilistic, or staged learning mechanisms.

  • Vertex labels provide group or class information that can guide more informative and discriminative network representations.
  • Classification-loss strategies: DDRW jointly optimizes DeepWalk with an L2-loss Support Vector Classification objective for discriminative representations.
  • Classification-loss strategies: MMDW couples matrix-factorization DeepWalk with a multi-class Support Vector Machine objective.
  • Classification-loss strategies: TLINE simultaneously learns LINE representations and a multi-class SVM classifier from labeled and unlabeled vertices.It is claimed to retain LINE’s ability to handle large-scale networks with low time and memory cost.
  • Label-informed strategies: GENE models group labels probabilistically, while SemiNE first learns unsupervised representations and then tunes them to fit vertex labels.

5.2 Semi-supervised Content Augmented NRL

Content-augmented semi-supervised NRL combines network structure with vertex content and labels to learn representations tailored to classification and linked-document settings. The surveyed approaches use coupled objectives, relation modeling, classifier losses, or unified latent spaces.

  • Label and content augmentation aims to make representations more informative and customized for the underlying classification task.
  • Content and label integration: TriDNR jointly learns from network structure, vertex content, and vertex labels by coupling Paragraph Vector and DeepWalk objectives.The parameter α controls the trade-off between the objectives.
  • Content and label integration: LDE represents linked documents by modeling word-word-document, document-document, and document-label relations.
  • Classifier-based integration: DMF combines TADW with empirical classifier-loss minimization and alternately optimizes representations, textual factors, and classifier parameters.Its learned representations and linear classifier are used to classify unlabeled vertices.
  • Classifier-based integration: Planetoid jointly learns embeddings from structural-context prediction and label-aware classification using network structure, vertex attributes, and labels.
  • Unified latent representations: LANE embeds network proximity, attribute affinity, and label proximity into a unified latent representation through a two-stage procedure.

5.3 Summary

The survey groups semi-supervised NRL methods into three discriminative-learning strategies with different label requirements, overfitting risks, and generalization properties. Classifier fitting can work with sparse labels, whereas label-relation modeling and joint embedding better capture intra-class proximity.

  • Discriminative-learning strategies: The three strategies are classifier-loss fitting, label-relation modeling, and joint embedding of vertices and labels.
  • Discriminative-learning strategies: Classifier fitting directly separates categories in the embedding space, while label-relation modeling and joint embedding capture relationships between labels and representations.
  • Trade-offs: 10% labeled vertices can yield significant gains over unsupervised counterparts for classifier-fitting methods, but these methods are more prone to overfitting.Regularization and DropOut are often introduced to address this risk.
  • Trade-offs: Label-relation modeling and joint embedding require more labels but can better capture intra-class proximity, benefiting clustering and visualization.

6 APPLICATIONS

NRL embeddings support network classification, link prediction, clustering, visualization, recommendation, spatial-temporal analysis, and knowledge-graph search or completion. Across these applications, the learned low-dimensional representations are evaluated by how well they preserve useful structural, attribute, or relational information.

  • Application scope: Learned representations support vertex classification, link prediction, clustering, visualization, and recommendation through conventional vector-based algorithms.
  • Vertex classification: Network representation learning can automatically construct vertex features for unsupervised or semi-supervised vertex classification.
  • Link prediction: Learned representations enable link prediction for discovering missing or implicit interactions, and reported predictions outperform traditional similarity-based approaches on several networks.
  • Clustering: Unsupervised NRL methods followed by k-means clustering are used to evaluate representation quality, and pRBM outperformed original features for clustering.
  • Visualization: NRL embeds large networks into low-dimensional spaces that can be visualized with methods such as t-SNE in 2-D or 3-D.
  • Recommendation and spatial-temporal analysis: Spatial-temporal embeddings represent users, locations, and points of interest as dense vectors for similarity search and other analysis, alleviating data sparsity.
  • Knowledge graphs: Structured embeddings support knowledge-graph entity search and completion by representing entities as low-dimensional vectors and identifying missing relationships.

7 EVALUATION PROTOCOLS

The survey reviews benchmark datasets and network analytic tasks used to evaluate network representation learning, then compares representative algorithms, performance, and computational complexity. It reports that evaluation practices vary across studies, while content augmentation and optimization choices affect observed performance and scalability.

  • Benchmark Datasets: Benchmark datasets record network type, size, labels, multi-label status, and whether vertices have attributes.The survey compiles publicly available datasets used across network representation learning studies.
  • Evaluation Methods: Network reconstruction predicts known links from vertex representations using precision@k and MAP.Original network links provide the ground truth for this evaluation.
  • Evaluation Methods: Vertex classification trains classifiers on learned representations and evaluates performance on unlabeled vertices.Settings include binary-class, multi-class, and multi-label classification.
  • Evaluation Methods: Vertex clustering applies k-means to learned representations and measures community recovery with Accuracy and NMI.Communities serve as ground truth for assessing clustering quality.
  • Evaluation Methods: Link prediction removes some edges, learns representations from the remainder, and evaluates recovery using AUC and precision@k.This protocol tests whether representations support prediction of network evolution.
  • Empirical Comparison: Social and citation networks are frequent benchmarks, while vertex classification is the most common evaluation method.The survey notes inconsistent datasets and settings across prior empirical studies, motivating same-dataset benchmark experiments.
  • Empirical Comparison: On attributed networks, content-augmented methods outperform structure-only methods; UPP-SNE is best at 5% training, while TADW performs best overall at 50%.Among structure-only methods, node2vec leads at 5%; at 50%, M-NMF has the best Micro-F1 and DeepWalk the best Macro-F1.
  • Empirical Comparison: LINE achieves the best clustering performance on Amherst, Hamilton, Mich, and Rochester, whereas UPP-SNE performs best on Citeseer, Cora, and Facebook.The survey associates LINE with preserving first- and second-order proximity and UPP-SNE with nonlinear use of vertex attributes.

8 FUTURE RESEARCH DIRECTIONS

The survey identifies future directions involving task dependence, theory, dynamics, heterogeneous information networks, and signed networks. These directions address limits of task-independent, static, homogeneous, and conventional homophily-based representation learning.

  • Task-dependence: Task-specific NRL should preserve information critical to the target task, extending beyond classification to link prediction, community detection, and other tasks.The survey notes that most existing algorithms are task-independent and that task-specific work remains limited.
  • Theory: Theoretical analysis remains insufficient for explaining algorithm properties and the sources of good empirical results.Existing connections between DeepWalk, LINE, node2vec, and graph Laplacians do not replace the need for deeper analysis.
  • Dynamics: Dynamic networks challenge static embeddings because content drifts, vertices and edges change, and network size is not fixed.The survey describes research on dynamic network embedding as limited.
  • Heterogeneous Information Networks: Heterogeneous information networks require methods that capture semantic proximity across different entity and edge types in a coherent embedding space.The survey describes current research using metapaths or metastructures as being at an early stage.
  • Signed Networks: Signed networks require modeling positive and negative relationships because negative links prevent direct application of traditional homophily-based methods.Fully encoding both network structure and vertex attributes remains open.

9 CONCLUSION

The survey organizes network representation learning methods, evaluates their datasets, tasks, empirical performance, and complexity, and identifies promising extensions. Its taxonomy and comparative resources are intended to support understanding and further research.

  • Survey Scope: The survey categorizes NRL methods by unsupervised or semi-supervised settings, information sources, and methodologies.It reviews representative algorithms and compares their advantages and disadvantages.
  • Contributions: It summarizes evaluation protocols, empirical performance, computational complexity, available resources, and emerging research directions.The survey positions these analyses as resources for advancing network representation learning.
Loading 1801.05852v3…