PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Embedding Techniques, Applications, and Performance: A Survey

Palash Goyal, Emilio Ferrara

arXiv:1705.02801v4cs.SIcs.LGphysics.data-an

TL;DR

Graph embedding research needs representations that preserve useful graph properties while remaining scalable and appropriately dimensional. This survey taxonomizes factorization, random-walk, and deep-learning methods, compares them across tasks, and provides GEM for unified access. It concludes that nonlinear models are promising for representing mixtures of community and structural equivalence, while scalability remains a constraint for some methods.

  • Problem

    Graph embedding must choose which properties to preserve, scale to large networks, and select dimensionality without excessive computational cost.

  • Method

    The survey taxonomizes factorization, random-walk, and deep-learning approaches, evaluates representative methods across tasks and datasets, and provides the GEM library.

  • Results

    Deep learning methods can model mixtures of community and structural equivalence, and SDNE achieved perfect reconstruction on the illustrated complete bipartite graph.

  • Takeaways & Limitations

    The survey identifies nonlinear models, network evolution, and synthetic-network generation as promising directions for graph embedding research.

  • Takeaways & Limitations

    Scalability approximations can introduce noise, and GraRep can require O(|V|^2) non-zero entries.

Abstract

from arXiv · show

Graphs, such as social networks, word co-occurrence networks, and communication networks, occur naturally in various real-world applications. Analyzing them yields insight into the structure of society, language, and different patterns of communication. Many approaches have been proposed to perform the analysis. Recently, methods which use the representation of graph nodes in vector space have gained traction from the research community. In this survey, we provide a comprehensive and structured analysis of various graph embedding techniques proposed in the literature. We first introduce the embedding task and its challenges such as scalability, choice of dimensionality, and features to be preserved, and their possible solutions. We then present three categories of approaches based on factorization methods, random walks, and deep learning, with examples of representative algorithms in each category and analysis of their performance on various tasks. We evaluate these state-of-the-art methods on a few common datasets and compare their performance against one another. Our analysis concludes by suggesting some potential applications and future directions. We finally present the open-source Python library we developed, named GEM (Graph Embedding Methods, available at https://github.com/palash1992/GEM), which provides all presented algorithms within a unified interface to foster and facilitate research on the topic.

1. Introduction

Graph embedding represents nodes in vector space to support graph-analysis tasks while preserving selected network properties. The survey organizes existing approaches, evaluates them across tasks, and provides GEM as a unified implementation library.

  • Graph analysis supports node classification, link prediction, clustering, and visualization across networks in biology, social sciences, and linguistics.
  • Graph embeddings represent networks in vector space while preserving properties, providing features that can replace complex models operating directly on graphs.
  • 1.1. Challenges: Choosing which graph property to preserve is difficult because performance may depend on the application and available distance metrics.
  • 1.1. Challenges: Embedding methods must scale to networks with millions of nodes and edges, especially when preserving global network properties.
  • 1.1. Challenges: Higher dimensions may improve reconstruction precision but increase time and space complexity, while lower dimensions can improve link prediction for locally focused models.
  • 1.2. Our contribution: The survey proposes a taxonomy, systematically compares models and hyperparameter sensitivity across datasets and tasks, and presents GEM with unified implementations.

2. Definitions and Preliminaries

The paper defines graphs through vertices, weighted edges, and adjacency matrices, then formalizes proximity and graph embedding. Embeddings map nodes to low-dimensional vectors while preserving a chosen proximity measure.

  • A graph G(V, E) consists of vertices and edges, with its adjacency matrix assigning non-negative weights to edges and zero to unconnected node pairs.
  • Edge weights measure first-order proximity, with larger weights indicating greater expected similarity between connected nodes.
  • Second-order proximity compares nodes through the similarity of their neighborhood structures rather than only their direct edge weights.
  • Graph embeddings map each node to a vector y_i in a dimension d much smaller than the number of vertices while preserving a graph proximity measure.
  • An embedding places nodes with stronger connection strength closer together in the embedding space when preserving first-order proximity.

3. Algorithmic Approaches: A Taxonomy

The survey organizes graph embedding methods into factorization, random-walk, and deep-learning categories, while tracing the field’s shift toward scalable techniques. Factorization approaches encode graph relationships in matrices or kernels and use methods such as eigenvalue decomposition, gradient descent, or generalized SVD to obtain embeddings.

  • Research evolution: Graph embedding research shifted from early dimensionality-reduction methods toward scalable techniques that exploit real-world network sparsity.Early methods such as Laplacian Eigenmaps and LLE had O(|V|^2) time complexity, motivating later scalable approaches.
  • Taxonomy: The survey’s taxonomy contains factorization-based, random-walk-based, and deep-learning-based approaches.It presents representative algorithms and characteristics for each category.
  • Factorization methods: Factorization methods represent node connections with matrices such as adjacency, Laplacian, transition-probability, or Katz-similarity matrices, then factorize them into embeddings.Positive semidefinite matrices can use eigenvalue decomposition, whereas unstructured matrices can use gradient descent.
  • Factorization methods: LLE models each node as a linear combination of its neighbors, constrains embedding variance and centering, and solves the resulting problem through eigenvectors of a sparse matrix.The solution uses the bottom d + 1 eigenvectors of (I − W)^T(I − W), discarding the smallest-eigenvalue eigenvector.
  • Factorization methods: Laplacian Eigenmaps keeps highly connected nodes close, whereas Cauchy Graph Embedding replaces its quadratic distance penalty to emphasize similar nodes.The survey notes that Laplacian Eigenmaps may fail to preserve local topology and describes Gaussian, Exponential, and Linear variants of the Cauchy approach.
  • Other approaches: Structure Preserving Embedding reconstructs the input graph from a positive semidefinite kernel, while other surveyed methods incorporate dimensionality reduction or node attributes.Attribute-aware examples include ARE, TADW, and HNE.
  • Factorization methods: Graph Factorization approximates adjacency-matrix factorization by summing over observed edges, while GraRep and HOPE preserve higher-order proximity through transition or similarity matrices.GraRep concatenates embeddings across proximity orders; HOPE uses similarity measures such as Katz Index and Rooted Page Rank with generalized SVD.

3.4. Random Walk based Methods

Random-walk methods learn node representations from sequences sampled on the graph, capturing higher-order proximity while offering options for navigating large or partially observed networks.

  • Random walks approximate graph properties such as centrality and similarity, making them useful for partially observed or very large graphs.
  • DeepWalk and node2vec: DeepWalk preserves higher-order proximity by maximizing the likelihood of context nodes appearing around each node in fixed-length random walks.
  • DeepWalk and node2vec: node2vec uses biased random walks to trade off breadth-first and depth-first searches, producing embeddings that can preserve community structure.
  • Extensions: HARP improves DeepWalk and node2vec initialization by coarsening the graph, embedding the coarsest hierarchy level, and using it to initialize finer levels.
  • Extensions: Walklets combines random walks with explicit distance modeling by skipping nodes in the walks, while other methods jointly learn network structure and node attributes.

3.5. Deep Learning based Methods

Deep learning methods use nonlinear neural architectures to embed graphs, including autoencoders that preserve network proximities, random-surfing representations, and graph convolutions for sparse graphs.

  • Deep autoencoders support nonlinear dimensionality reduction and have been applied to graph embedding by SDNE and DNGR.
  • Autoencoder methods: SDNE jointly preserves first- and second-order proximities through an autoencoder and a Laplacian-based penalty for separating similar vertices.
  • Autoencoder methods: DNGR combines random surfing, PPMI transformation, and stacked denoising autoencoders to produce node embeddings from probabilistic co-occurrence information.
  • Graph convolutional methods: SDNE and DNGR use global neighborhoods as input, which can be computationally expensive for large sparse graphs; GCNs address this by aggregating neighbor embeddings iteratively.
  • Graph convolutional methods: Graph-convolution approaches differ in whether their filters operate directly on graph structure or on the graph-Laplacian spectrum.
  • Variational autoencoders: Variational autoencoders with GCN encoders and inner-product decoders were evaluated for graph embedding and empirically improved performance over non-probabilistic autoencoders.

3.6. Other Methods

LINE models first- and second-order proximities with separate probability-based objectives, extending matrix-factorization ideas to preserve multiple notions of node similarity.

  • LINE explicitly defines separate functions for first- and second-order proximity and minimizes their combination.
  • For first-order proximity, LINE uses joint probability distributions, whereas Graph Factorization directly minimizes the difference between the adjacency matrix and embedding dot products.

3.7. Discussion

The discussion contrasts embedding methods by the graph properties they can represent: factorization methods are constrained, random walks offer tunable mixtures, and deep models can represent broader structural patterns.

  • An embedding that keeps connected nodes close can miss structural equivalence in a complete bipartite graph, whereas structurally equivalent nodes can form an interpretable representation.
  • Factorization methods cannot learn arbitrary functions such as network connectivity unless the relevant property is explicitly included in their objective.
  • Random-walk methods control the mixture of community and structural equivalence through walk parameters, while deep models can learn such mixtures by minimizing reconstruction error.
  • SDNE achieved perfect reconstruction of the complete bipartite graph by storing its structure in autoencoder weights.
  • The survey identifies general nonlinear models spanning broad function classes as a promising direction for graph embedding research.

4. Applications

Graph embeddings support network compression, visualization, clustering, link prediction, and node classification by representing graph structure in vector space.

  • Network compression: Graph embeddings can summarize networks by reconstructing the original graph from low-dimensional node representations.Representations in the order of 100s can reconstruct graphs with high precision.
  • Visualization: Dimensionality reduction methods such as PCA and t-SNE enable visualization of embedded nodes and network topology.Different embedding methods preserve different structures, affecting how visualizations should be interpreted.
  • Clustering: Clustering embeddings can reveal community structure or structurally equivalent nodes, but recent methods have rarely evaluated this task explicitly.Structure-based clustering targets dense subgraphs or nodes with similar roles, while attribute-based clustering uses node attributes.
  • Link prediction: Embeddings support link prediction by representing network dynamics and have outperformed traditional similarity-based methods on several datasets.Applications include collaboration, social, and biological networks, where missing or future links are predicted.
  • Node classification: Embeddings act as automatically extracted structural features for node classification and can predict missing labels with high precision.Evaluated domains include language, social, biological, and collaboration networks.

5. Experimental Setup

The experiments evaluate graph embedding methods on one synthetic and six real datasets using task-specific reconstruction, prediction, and classification metrics.

  • Implementation: The experimental system uses 32 CPU cores, 128 GB RAM, and an Nvidia Tesla K40C GPU for deep network models.Experiments ran on Ubuntu 14.04.4 LTS at 2.6 GHz.
  • Datasets: The evaluation uses one synthetic SBM graph and six real datasets spanning social, collaboration, and biological networks.The synthetic graph has 1024 nodes and 3 communities; real datasets include KARATE, BLOGCATALOG, YOUTUBE, HEP-TH, ASTRO-PH, and PPI.
  • Evaluation metrics: Precision@k and MAP evaluate graph reconstruction and link prediction, while micro-F1 and macro-F1 evaluate node classification.For reconstruction, observed edges are the full edge set; for link prediction, they are hidden edges.
  • Evaluation metrics: Precision@k measures the fraction of correct edges among the top k predictions.The observed edge set differs by task: full edges for reconstruction and hidden edges for link prediction.
  • Evaluation metrics: MAP averages node-level precision estimates, while macro-F1 averages label-level F1 scores and micro-F1 weights instances globally.These metrics provide separate evaluations for ranked edge recovery and multilabel classification.

6. Experiments and Analysis

Experiments compare embedding dimensions, reconstruction, visualization, link prediction, node classification, and hyperparameter sensitivity across multiple datasets and tasks.

  • Graph reconstruction: Reconstruction evaluates ranked node proximity using Precision@k on five random samples of 1024 nodes per dataset.Sampling limits the number of possible node pairs evaluated in large networks.
  • Graph reconstruction: At 128 dimensions, higher-order proximity methods generally outperform others, SDNE performs consistently well, and HOPE reconstructs effectively without extra parameters.Laplacian Eigenmaps performs exceptionally on SBM, while node2vec has low reconstruction precision.
  • Graph reconstruction: MAP generally increases with embedding dimension, although SDNE achieves high precision in 16 dimensions with decoder parameters.Higher dimensions can store more information, but exceptions occur.
  • Visualization: HOPE and SDNE separate SBM communities in visualization, while LE, GF, and LLE capture community structure to some extent.The comparison uses community labels to color nodes in t-SNE visualizations.
  • Visualization: Karate visualizations show that methods preserve different combinations of community structure, structural roles, and higher-order relationships.SDNE places the bridge node apart as a separate node type without implying disconnection.
  • Link prediction: Link-prediction performance can saturate or vary with dimension, and larger embeddings may overfit observed links rather than predict unobserved ones.Relative method performance also depends on embedding dimension.
  • Node classification: Node2vec outperforms other methods on node classification in the reported experiments, while other methods outperform it on SBM.Its preservation of homophily and structural equivalence may help when labels reflect both interests and social or biological ties.
  • Node classification: Node-classification performance often saturates or deteriorates beyond a dimension, with 8 dimensions sufficient for SBM and node2vec best on PPI and BlogCatalog at 128 dimensions.The authors associate these patterns with possible overfitting on training data.

7. A Python Library for Graph Embedding

GEM is an open-source Python library that unifies the surveyed graph embedding methods and evaluation tools for experimentation on weighted and unweighted graphs.

  • Library scope: GEM implements Locally Linear Embedding, Laplacian Eigenmaps, Graph Factorization, HOPE, SDNE, and node2vec through a unified interface.The library wraps node2vec’s C++ implementation with a Python interface.
  • Library scope: GEM supports weighted and unweighted graphs and provides evaluation interfaces for the four application tasks discussed in the survey.Its hierarchical, modular design supports testing methods on new datasets and developing new approaches.
  • Evaluation interface: The library supports multiple edge-reconstruction metrics, including cosine similarity, Euclidean distance, and decoder-based evaluation.For multilabel classification, it uses one-vs-rest logistic regression and supports other classifiers.

8. Conclusion and Future Work

The survey organizes graph embedding methods into factorization-, random-walk-, and deep-learning-based categories, evaluates them across applications, and identifies future research directions. It also introduces GEM as an open-source library for implementing and evaluating the surveyed methods.

  • The survey covers factorization-based, random-walk-based, and deep-learning-based graph embedding approaches.
  • It analyzes preserved structures, category-specific challenges, applications, and evaluation metrics across the surveyed methods.
  • The methods are empirically compared on applications using several publicly available real networks to characterize their strengths and weaknesses.
  • GEM provides implementations of the surveyed embedding methods and evaluation tasks including graph reconstruction, link prediction, node classification, and visualization.
  • Future directions include nonlinear models, graph evolution, and synthetic networks with real-world characteristics.
  • Deep learning models may produce compressed representations but have limited interpretability, motivating further work on interpreting learned embeddings.
Loading 1705.02801v4…