PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Network Embedding

Peng Cui, Xiao Wang, Jian Pei, Wenwu Zhu

arXiv:1711.08752v1cs.SI

TL;DR

Network embedding addresses the challenge of representing and analyzing large, complex networks, where explicit graph structures hinder parallel processing and standard machine-learning methods. This survey categorizes and reviews embedding methods by preserved information, evaluates their applications and resources, and identifies future directions; it concludes that structure and property preservation forms the foundation, while motifs and other complex structures remain insufficiently modeled.

  • Problem

    Large-scale network analysis needs concise representations because explicit graph structures create computational, parallelization, and machine-learning challenges.

  • Method

    The paper surveys network embedding methods by categorizing preserved information into structure and properties, side information, and advanced task-specific information.

  • Results

    The survey concludes that structure and property preservation is foundational, with side and advanced information further supporting network applications.

  • Takeaways & Limitations

    Network embedding methods can be organized into a framework that progressively incorporates network structure, properties, side information, and domain-specific knowledge.

  • Takeaways & Limitations

    Existing methods do not fully consider particular higher-order structures such as network motifs and more complex local node structures.

Abstract

from arXiv · show

Network embedding assigns nodes in a network to low-dimensional representations and effectively preserves the network structure. Recently, a significant amount of progresses have been made toward this emerging network analysis paradigm. In this survey, we focus on categorizing and then reviewing the current development on network embedding methods, and point out its future research directions. We first summarize the motivation of network embedding. We discuss the classical graph embedding algorithms and their relationship with network embedding. Afterwards and primarily, we provide a comprehensive overview of a large number of network embedding methods in a systematic manner, covering the structure- and property-preserving network embedding methods, the network embedding methods with side information and the advanced information preserving network embedding methods. Moreover, several evaluation approaches for network embedding and some useful online resources, including the network data sets and softwares, are reviewed, too. Finally, we discuss the framework of exploiting these network embedding methods to build an effective system and point out some potential future directions.

1 Introduction

Large-scale networks are difficult to represent and analyze with explicit graph structures because they impose computational, communication, and machine-learning barriers. Network embedding addresses these challenges by learning low-dimensional node vectors while preserving relationships and supporting inference tasks.

  • Challenges of Traditional Representation: Large networks represented as graphs face high computational complexity because many analysis algorithms require iterative or combinatorial operations over explicit edges.Shortest-path computation may require enumerating many possible paths between nodes.
  • Challenges of Traditional Representation: Explicit edge coupling makes traditional network representations difficult to parallelize and distribute, increasing communication costs across servers.The achievable speed-up depends on the topological characteristics of the underlying graphs.
  • Challenges of Traditional Representation: Traditional network representations are poorly suited to standard machine-learning methods because nodes are dependent rather than independent vectors, while adjacency rows are extremely high-dimensional.This high dimensionality makes subsequent network processing and analysis difficult in large graphs.
  • Network Embedding: Network embedding learns low-dimensional vectors that encode topological and structural characteristics while replacing explicit relationships with distances in vector space.The karate club network illustrates this transformation through a two-dimensional embedding.
  • Goals of Network Embedding: Network embedding aims both to reconstruct the original network and to support inference tasks such as link prediction, important-node identification, and node-label inference.Reconstruction alone can overfit observed links and fail to infer unseen links, as illustrated by SVD-based embeddings.
  • Survey Scope: The survey reviews state-of-the-art network embedding methods, organizes their preserved information, evaluates application scenarios, and identifies future research directions.Its coverage includes structure and property preservation, side information, advanced information preservation, datasets, and codes.

2 Categorization and The Models

The survey categorizes network embedding methods by the information they preserve and relates their models to different representation-learning goals. It covers structure and properties, side information, advanced task-specific information, and matrix-factorization, random-walk, and neural approaches.

  • Categorization: Network embedding methods are categorized into structure and property preserving methods, methods using side information, and advanced information preserving methods.The categorization is based on the types of information preserved in the embedding.
  • Categorization: Traditional graph embedding mainly emphasizes network reconstruction, whereas this survey focuses on recent network embedding methods designed to support network inference.The categorization structure is presented as an overview of the related works.
  • Information Preserved: Network structures and properties provide foundational information for inference, while side information and advanced task information can further characterize relationships and target applications.Examples of side information include node content, labels, attributes, and node types.
  • Advanced Information Preserving Network Embedding: Advanced information preserving methods use supervised or pseudo-supervised signals to optimize representations toward particular target problems, including node classification with labels.An end-to-end design can use network structure as input, labels as supervision, and embeddings as a latent layer.
  • Common Models: Matrix factorization, random walks, and deep neural networks are common model families, and their combinations can produce new network embedding solutions.Matrix factorization learns low-rank spaces, random walks identify neighborhoods through co-occurrence, and neural models provide nonlinear mappings.
  • Common Models: Random-walk methods borrow the Word2Vector analogy by treating nodes as words, paths as sentences, and co-occurring nodes as neighborhoods.DeepWalk and Node2Vec are representative methods in this family.

3 Network Embedding v.s. Graph Embedding

Graph embedding and network embedding both map graphs or networks into low-dimensional vector spaces, but they differ in objectives, assumptions, and data sources. The section reviews classical graph embedding methods before contrasting them with network embedding focused on network inference.

  • Graph embedding maps a graph into a low-dimensional vector space and has a substantial classical literature.
  • Classical graph embedding methods: Isomap constructs a neighborhood graph, computes graph shortest-path distances, and applies multidimensional scaling to obtain representations that approximately preserve geodesic distances.Its key limitation is the high complexity of computing pairwise shortest paths.
  • Classical graph embedding methods: LLE reconstructs each entry from its neighbors and optimizes a low-dimensional mapping that preserves neighborhood structure.
  • Classical graph embedding methods: Laplacian eigenmaps construct a neighborhood graph, weight its edges with a heat kernel, and obtain node representations by minimizing a Laplacian objective under a nontriviality constraint.The reviewed graph embedding literature extends these methods by considering different characteristics of constructed graphs.
  • Network embedding versus graph embedding: Unlike graph embedding, network embedding targets both network reconstruction and network inference, generally operates on naturally formed networks, and defines node proximity according to the analytic task.The survey therefore focuses mainly on network embedding methods designed to support network inference.

4 Structure and Property Preserving Network Embedding

Structure- and property-preserving methods learn low-dimensional representations that retain neighborhood, high-order proximity, community, and network-specific property information. The literature increasingly combines multiple structural signals and nonlinear models, while property preservation remains challenging.

  • Network structures: Network structures include neighborhood structure, high-order node proximity, and community structure.
  • Neighborhood Structures and High-order Node Proximity: DeepWalk preserves neighbor structures through short random walks and Skip-Gram representations.
  • Neighborhood Structures and High-order Node Proximity: Node2vec uses second-order random walks to interpolate between breadth-first and depth-first neighborhood sampling.
  • Neighborhood Structures and High-order Node Proximity: LINE preserves first- and second-order proximities, while GraRep additionally captures k-step proximities for global node representations.
  • Deep and property-preserving methods: SDNE combines a deep autoencoder with first- and second-order proximity objectives, emphasizing reconstruction errors on observed edges.
  • Summary: Most methods preserve high-order structure, whereas property-preserving methods remain lightly studied because embedding and network spaces differ heterogeneously at the property level.

5 Network Embedding with Side Information

Side-information methods augment network topology with node content, labels, attributes, or heterogeneous node and edge types. They learn representations by jointly modeling structural relations and these additional information sources.

  • Overview: Side information comprises node content and node or edge types, complementing network structure in embedding.
  • Node content and labels: MMDW incorporates node labels into DeepWalk-derived matrix factorization while jointly optimizing an SVM max-margin classifier.
  • Node content and labels: Document-network models jointly represent network structure and topic-space information associated with document nodes.
  • Node content and labels: TADW incorporates text through matrix factorization, but its high computational cost and unordered attribute features lose semantic information.
  • Node content and labels: Some models jointly enhance representations with network structure, node content, and node labels, while LANE combines their affinity matrices spectrally.
  • Heterogeneous networks: Heterogeneous-network methods map different node types into common spaces or preserve typed relations using classification, smoothness, deep embedding, or meta-path proximity.

6 Advanced Information Preserving Network Embedding

Advanced information-preserving methods tailor network embeddings to supervised or pseudo-supervised tasks such as diffusion prediction, cascade prediction, anomaly detection, and network alignment. These approaches combine structural representation learning with task-specific objectives or domain knowledge.

  • Overview: Advanced information is supervised or pseudo-supervised information tied to a specific analytic task.
  • Information diffusion: Diffusion-prediction embeddings model observed cascades as heat diffusion and learn latent positions whose kernels explain infection timing.
  • Cascade prediction: DeepCas predicts cascade-size increments end to end by sampling paths from cascade graphs instead of using hand-crafted cascade and network features.
  • Anomaly detection: Anomaly-detection embeddings encode node-community correlations and identify nodes connecting to diverse communities through learned anomalousness measures.
  • Network alignment: Network-alignment methods densify paired networks, preserve their structures, and learn linear or nonlinear mappings consistent with observed anchor links.
  • Summary: These methods generally preserve network structure while connecting node representations to target tasks through domain-specific information.

7 Network Embedding in Practice

This section surveys commonly used network datasets, benchmarks, and evaluation tasks for developing network embedding methods. Real-world datasets are grouped into social, citation, language, and biological networks, with variants potentially differing across studies.

  • Real-world network datasets: Network embedding evaluations commonly use social, citation, language, and biological networks.The survey organizes real-world datasets into four groups according to network nature.
  • Social networks: BlogCatalog, Flickr, YouTube, and Twitter provide examples of social-network datasets based on online user relationships or contacts.The listed datasets represent blogger relationships, photo-sharing contacts, video-sharing users, and Twitter users.
  • Citation networks: DBLP, Cora, and Citeseer provide citation-network datasets involving authors, papers, or scientific publications.Cora additionally associates publications with word-presence vectors.
  • Language and collaboration networks: ArXiv is described as a collaboration network, while Wikipedia is described as a word-cooccurrence network.These datasets represent language or information derived from online sources.
  • Biological networks: PPI represents pairwise physical interactions between proteins in yeast.It is presented as a biological-network dataset.

Node Classification

Node classification uses learned low-dimensional node representations to classify nodes with unknown labels from a subset of labeled nodes. The survey reports applications across multiple network categories and describes node classification as an effective use of network embedding.

  • Node Classification: Node classification classifies unlabeled nodes using a network embedding learned from the network and known node labels.The described procedure first embeds the network, then uses labeled nodes to classify the remaining nodes.
  • Evaluation metrics: Micro-F1 and Macro-F1 are commonly used metrics for evaluating multi-label node classification.Macro-F1 is defined from per-label F1 values, while Micro-F1 aggregates true positives, false positives, and false negatives across labels.
  • Evaluation settings: Multi-label classification has been tested on social, citation, language, and biological datasets.Examples include BlogCatalog, Flickr, YouTube, DBLP, Cora, Citeseer, Wikipedia, and PPI.
  • Evaluation settings: DeepWalk, GraRep, SDNE, node2vec, and LANE evaluate node classification on social-network datasets including BlogCatalog and Flickr.The cited studies use these embedding methods to assess classification performance on social networks.
  • Conclusion: Network embedding methods have been widely applied across networks and demonstrated effectiveness for node classification.This is the survey’s summary conclusion for the task.

Link Prediction

Link prediction estimates whether an edge exists between two nodes using observed network structure and node representations. The survey describes similarity-based scoring, standard ranking metrics, diverse datasets, and effective performance across network types.

  • Link Prediction: Link prediction estimates the likelihood of an edge between two nodes from observed network structure.It is presented as a fundamental network-analysis problem.
  • Embedding-based scoring: Node embeddings support link prediction by enabling node similarity estimates through inner products or cosine similarity.Higher similarity indicates a higher propensity for the two nodes to be linked.
  • Evaluation metrics: Precision@k and Mean Average Precision are commonly used to evaluate link prediction performance.The accompanying notation defines ranked nodes and observed edges for precision@k.
  • Evaluation settings: Link prediction evaluations use citation, social, and biological networks, including ArXiv, DBLP, Twitter, Facebook, Epinions, Slashdot, and PPI.The cited studies apply different embedding methods across these network categories.
  • Conclusion: Extensive experiments demonstrate that network embedding can tackle link prediction effectively across various networks.The survey attributes this suitability to embedding methods’ ability to capture inherent network structures.

Node Clustering

Node clustering divides network nodes into groups whose within-cluster similarity exceeds between-cluster similarity, using learned node representations with standard clustering methods. The survey reports testing across social, citation, and document networks and characterizes network embedding as effective for this task.

  • Node Clustering: Node clustering groups nodes so that nodes within a cluster are more similar than nodes in different clusters.Network embeddings provide low-dimensional representations on which methods such as Kmeans can operate directly.
  • Evaluation metrics: Accuracy and normalized mutual information are frequently used to evaluate clustering performance on graphs and networks.Accuracy measures the percentage of correctly assigned labels, while NMI uses mutual information between clusterings.
  • Evaluation settings: Node clustering evaluations use social, citation, and document networks, including Facebook, YELP, DBLP, and 20-NewsGroup.The survey also describes a social-blogging network constructed from TF-IDF features and following behaviors.
  • Conclusion: Network embedding has become an effective method for solving node clustering problems across different network types.The conclusion follows the survey’s reported testing of embedding-based clustering on multiple networks.

Network Visualization

Network embedding supports visualization by placing network nodes in a low-dimensional space where structure and similarity can be inspected. Visualization can reveal community structure and node centrality in complex networks.

  • Network embedding generates meaningful two-dimensional layouts that make sophisticated network structure easier to inspect.Applying visualization tools such as t-SNE to learned node representations helps users see a network's overall structure.
  • In SDNE visualizations, documents appear as points whose colors encode their labels.
  • Similar nodes are positioned closer than dissimilar nodes, preserving intrinsic network structure in the low-dimensional visualization.

Open Source Software

The survey provides a collection of links to source code for various network embedding methods.

  • Table 2 collects links to source code for various network embedding methods.

8 Conclusions and Future Research Directions

The survey frames structure- and property-preserving embedding as the foundation for incorporating machine learning, side information, and advanced domain knowledge. It identifies open directions involving richer structures, information sources, applications, dynamic networks, and alternative embedding spaces.

  • Conclusions and framework: Structure- and property-preserving embedding is foundational because information loss in the embedding space can harm subsequent analytic tasks.The framework then supports machine learning, side-information integration, and incorporation of advanced domain knowledge.
  • More Structures and Properties: Existing methods do not fully account for some real-world structures, including network motifs, complex local structures, and hyperedges.The survey specifically identifies hypernetwork embedding as important for some real applications.
  • More Structures and Properties: How power-law degree distributions affect embedding performance and how to improve representations for minority nodes remain largely unexplored.
  • The Effect of Side Information: The assumption that network structure and side information agree may not hold in real applications, while the two information sources may be complementary.Low correlation between them may degrade embedding performance.
  • More Advanced Information and Tasks: Meta structures offer a higher-order constraint beyond meta paths and suggest a direction for heterogeneous information network embedding.
  • More Advanced Information and Tasks: Future work should design embeddings for specific applications by integrating their distinctive domain knowledge as advanced information.The survey mentions rumor detection and social-tie inference as example targets.
  • Dynamic Network Embedding: Most existing methods target static networks, so evolving networks require approaches that avoid repeatedly rerunning embeddings at each timestamp.Repeated execution is time-consuming and may not meet real-time processing demands.
  • More Embedding Spaces: Exploring non-Euclidean target spaces, including hyperbolic space, is another research direction for network embedding.Hyperbolic assumptions can naturally reflect heterogeneous degree distributions and strong clustering.
Loading 1711.08752v1…