Back

Graph Embedding Techniques, Applications, and Performance: A Survey

Palash GoyalEmilio Ferrara

article2017Knowledge-Based Systems1,827 citations

Surveys major graph embedding techniques across factorization, random walks, and deep learning models, providing empirical performance comparisons on standard benchmarks alongside an open-source Python library with unified implementations.

Listen

Modern digital and scientific systems generate vast networks of connected data, ranging from biological protein interactions to social and communication networks. Analyzing these large systems is essential for discovering patterns, recommending relevant content, and predicting behavior. However, traditional analytics that operate directly on massive network structures face severe computational bottlenecks and require overly complex algorithms.

To address this challenge, the article evaluates methods that convert network structures into compact numerical vectors—a process known as node-level graph embedding. The objective was to provide a systematic taxonomy of existing techniques, benchmark their empirical performance across diverse tasks, analyze their sensitivity to operational parameters, and release an open-source library to unify their deployment.

Techniques were categorized into three main families: matrix factorization, random walk sampling, and deep learning architectures. The authors benchmarked representative algorithms across one synthetic and six real-world datasets, spanning social networks, scientific collaboration archives, and biological interaction data. Performance was measured on four core operational tasks: network reconstruction, two-dimensional visualization, link prediction, and node classification.

Key findings demonstrate that no single embedding technique excels across all network applications. First, deep neural networks (such as SDNE) and high-order factorization methods (such as HOPE) significantly outperformed other techniques in exact network reconstruction and unobserved link prediction, where SDNE achieved more than a two- to three-fold accuracy gain on certain collaboration and biological graphs when properly tuned. Second, biased random walk methods (specifically node2vec) achieved superior accuracy in classifying node labels across social and biological networks by capturing both immediate communities and broader structural roles. Third, increasing the dimension of the embedding space improved reconstruction fidelity but led to severe overfitting and performance drops in predictive tasks for specific datasets. Finally, performance proved highly sensitive to task-specific parameter tuning, directly invalidating the idea that a single universal embedding can serve all downstream tasks equally well.

These results show that deploying graph representations can dramatically lower downstream computing costs by enabling standard predictive models to replace specialized network algorithms. However, this strategy introduces operational trade-offs: organizations must align their choice of embedding algorithm with their specific objective. Prioritizing community detection or link prediction requires preserving connection proximities, while role-based classification demands capturing structural equivalence.

Decision-makers should choose embedding models tailored strictly to their end goals: random walk approaches for demographic or functional classification, and deep neural models or high-order factorization for link recommendation and network summarization. Before operational deployment, teams must conduct disciplined parameter tuning and validation to avoid overfitting. Future initiatives should focus on improving the interpretability of deep neural models and extending representations to dynamically evolving networks.

Confidence in these findings is high for static network topologies and standard classification or link prediction pipelines. However, readers should exercise caution when extrapolating these benchmarks to dynamic networks or domains containing rich, unstructured node attributes, as the empirical evaluations primarily focused on static structural topologies.

Information Sciences InstituteUniversity of Southern Californiacommunication networksdeep learningfactorization methodsgraph embeddingsnetwork representation learninggraph factorization
arXiv: 1705.02801palash1992/GEM
Cover for Graph Embedding Techniques, Applications, and Performance: A Survey

Abstract

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 this https URL), which provides all presented algorithms within a unified interface to foster and facilitate research on the topic.

Topics

communication networksdeep learningfactorization methodsgraph embeddingslibrariespythonrandom walksocial networksbipartite graphsnetwork architecture

Keywords

graph embeddingsnetwork representation learninggraph factorizationgraph auto-encodersnode embeddingsgraph clusteringlink predictionnetwork classificationgraph reconstruction performancegraph visualization

Table of Contents

  • 1 Introduction
  • 1.1 Challenges
  • 1.2 Our contribution
  • 1.3 Organization of the survey
  • 2 Definitions and Preliminaries
  • 3 Algorithmic Approaches: A Taxonomy
  • 3.1 Graph Embedding Research Context and Evolution
  • 3.2 A Taxonomy of Graph Embedding Methods
  • 3.3 Factorization based Methods
  • 3.3.1 Locally Linear Embedding (LLE)
  • 3.3.2 Laplacian Eigenmaps
  • 3.3.3 Cauchy Graph Embedding
  • 3.3.4 Structure Preserving Embedding (SPE)
  • 3.3.5 Graph Factorization (GF)
  • 3.3.6 GraRep
  • 3.3.7 HOPE
  • 3.3.8 Additional Variants
  • 3.4 Random Walk based Methods
  • 3.4.1 DeepWalk
  • 3.4.2 node2vec
  • 3.4.3 Hierarchical Representation Learning for Networks (HARP)
  • 3.4.4 Walklets
  • 3.4.5 Additional Variants
  • 3.5 Deep Learning based Methods
  • 3.5.1 Structural Deep Network Embedding (SDNE)
  • 3.5.2 Deep Neural Networks for Learning Graph Representations (DNGR)
  • 3.5.3 Graph Convolutional Networks (GCN)
  • 3.5.4 Variational Graph Auto-Encoders (VGAE)
  • 3.6 Other Methods
  • 3.6.1 LINE
  • 3.7 Discussion
  • 4 Applications
  • 4.1 Network Compression
  • 4.2 Visualization
  • 4.3 Clustering
  • 4.4 Link Prediction
  • 4.5 Node Classification
  • 5 Experimental Setup
  • 5.1 Datasets
  • 5.2 Evaluation Metrics
  • 6 Experiments and Analysis
  • 6.1 Graph Reconstruction
  • 6.2 Visualization
  • 6.3 Link Prediction
  • 6.4 Node Classification
  • 6.5 Hyperparameter Sensitivity
  • 7 A Python Library for Graph Embedding
  • 8 Conclusion and Future Work
  • References

Knowls

  1. Knowl 1 — Taxonomy and Computational Complexity of Graph Embedding Methods

    data/table

    Graph embedding methods map graph vertices to a low-dimensional vector space Rd\mathbb{R}^d (d≪∣V∣d \ll |V|) while preserving structural properties. Algorithmic approaches are categorized into factorization-based, random walk-based, deep learning-based, and miscellaneous techniques, with computational complexity and preserved proximities summarized below:

    Category Method Time Complexity Properties Preserved
    Factorization LLE O(∣E∣d2)O(|E|d^2) Local neighborhood linearity
    Factorization Laplacian Eigenmaps O(∣E∣d2)O(|E|d^2) 1st1^{\text{st}} order proximity
    Factorization Graph Factorization (GF) O(∣E∣d)O(|E|d) 1st1^{\text{st}} order proximity
    Factorization GraRep O(∣V∣3)O(|V|^3) 1−kth1 - k^{\text{th}} order proximities
    Factorization HOPE O(∣E∣d2)O(|E|d^2) 1−kth1 - k^{\text{th}} order proximities
    Random Walk DeepWalk O(∣V∣d)O(|V|d) Higher-order proximity
    Random Walk node2vec O(∣V∣d)O(|V|d) 1−kth1 - k^{\text{th}} order proximities, structural equivalence
    Deep Learning SDNE O(∣V∣∣E∣)O(|V||E|) 1st1^{\text{st}} and 2nd2^{\text{nd}} order proximities
    Deep Learning DNGR O(∣V∣2)O(|V|^2) 1−kth1 - k^{\text{th}} order proximities
    Deep Learning GCN O(∣E∣d2)O(|E|d^2) 1−kth1 - k^{\text{th}} order proximities
    Miscellaneous LINE O(∣E∣d)O(|E|d) 1st1^{\text{st}} and 2nd2^{\text{nd}} order proximities

    Early spectral dimensionality reduction algorithms required O(∣V∣2)O(|V|^2) or O(∣V∣3)O(|V|^3) operations, rendering them unscalable for large graphs. Modern techniques leverage graph sparsity to achieve linear complexity in the number of edges (O(∣E∣d)O(|E|d) or O(∣E∣d2)O(|E|d^2)) or vertices (O(∣V∣d)O(|V|d)).

  2. Knowl 2 — Graph Embedding and Multi-Order Proximities

    definition

    Let G=(V,E)G = (V, E) be a graph with vertex set V={v1,…,vn}V = \{v_1, \dots, v_n\} and edge set E={eij}i,j=1nE = \{e_{ij}\}_{i,j=1}^n, represented by an adjacency matrix S∈Rn×nS \in \mathbb{R}^{n \times n} where sij≥0s_{ij} \ge 0 denotes edge weight (sij=sjis_{ij} = s_{ji} for undirected graphs, and sij=0s_{ij} = 0 if (vi,vj)∉E(v_i, v_j) \notin E).

    • First-order proximity: The immediate edge weight sijs_{ij} between nodes viv_i and vjv_j. A non-zero weight indicates direct similarity.
    • Second-order proximity: The similarity between the neighborhood first-order proximity vectors si=[si1,…,sin]s_i = [s_{i1}, \dots, s_{in}] and sj=[sj1,…,sjn]s_j = [s_{j1}, \dots, s_{jn}] of nodes viv_i and vjv_j. Nodes with similar neighborhoods possess high second-order proximity even if no direct edge connects them.
    • Higher-order proximity: Proximity defined via multi-step path metrics, including the Katz Index, Rooted PageRank, Common Neighbors, and Adamic-Adar score.
    • Graph Embedding: A mapping function f:vi↦yi∈Rdf: v_i \mapsto y_i \in \mathbb{R}^d for all i∈{1,…,n}i \in \{1, \dots, n\}, where d≪∣V∣d \ll |V|, such that ff preserves a chosen proximity measure on GG in the embedding space.

  3. Knowl 3 — High-Order Proximity Preserved Embedding (HOPE)

    model/method

    High-Order Proximity Preserved Embedding (HOPE) learns directed graph node representations by factorizing a higher-order similarity matrix SS into source and target embeddings Ys,Yt∈R∣V∣×dY_s, Y_t \in \mathbb{R}^{|V| \times d} by minimizing:

    min⁡Ys,Yt∥S−YsYtT∥F2\min_{Y_s, Y_t} \|S - Y_s Y_t^T\|_F^2

    where ∥⋅∥F\|\cdot\|_F denotes the Frobenius norm. HOPE expresses common proximity matrices (such as Katz Index, Rooted PageRank, Common Neighbors, and Adamic-Adar) in the generalized form S=Mg−1MlS = M_g^{-1} M_l, where both MgM_g and MlM_l are sparse matrices.

    By leveraging the sparsity of MgM_g and MlM_l, HOPE solves the low-rank approximation via generalized Singular Value Decomposition (SVD) with time complexity O(∣E∣d2)O(|E|d^2), enabling scalable preservation of asymmetric transitivity and high-order proximity.

  4. Knowl 4 — Structural Deep Network Embedding (SDNE)

    model/method

    Structural Deep Network Embedding (SDNE) utilizes a deep autoencoder architecture to jointly preserve first-order and second-order graph proximities through a semi-supervised objective function.

    1. Second-Order Proximity (Unsupervised): For each node viv_i, the autoencoder takes its adjacency row sis_i as input and reconstructs it as s^i\hat{s}_i. To handle high network sparsity, the reconstruction loss penalizes reconstruction errors on non-zero edges more heavily: L2nd=∑i=1∣V∣∥(s^i−si)⊙bi∥22\mathcal{L}_{2nd} = \sum_{i=1}^{|V|} \|(\hat{s}_i - s_i) \odot b_i\|_2^2 where ⊙\odot is the Hadamard product, bij=1b_{ij} = 1 if sij=0s_{ij} = 0, and bij=β>1b_{ij} = \beta > 1 if sij>0s_{ij} > 0.

    2. First-Order Proximity (Supervised): Applied to the bottleneck latent representations yi,yj∈Rdy_i, y_j \in \mathbb{R}^d to penalize connected vertices mapped far apart: L1st=12∑i,j=1∣V∣sij∥yi−yj∥22\mathcal{L}_{1st} = \frac{1}{2}\sum_{i,j=1}^{|V|} s_{ij} \|y_i - y_j\|_2^2

    3. Joint Objective: SDNE minimizes Lmix=L2nd+αL1st+νLreg\mathcal{L}_{mix} = \mathcal{L}_{2nd} + \alpha \mathcal{L}_{1st} + \nu \mathcal{L}_{reg}, where Lreg\mathcal{L}_{reg} is an ℓ2\ell_2-norm parameter regularizer.

  5. Knowl 5 — Large-Scale Information Network Embedding (LINE)

    model/method

    Large-scale Information Network Embedding (LINE) optimizes two separate objective functions to preserve first-order and second-order proximities:

    • First-Order Proximity: For undirected edge (vi,vj)∈E(v_i, v_j) \in E with weight WijW_{ij}, the joint probability modeled by embeddings Yi,Yj∈RdY_i, Y_j \in \mathbb{R}^d is: p1(vi,vj)=11+exp⁡(−⟨Yi,Yj⟩)p_1(v_i, v_j) = \frac{1}{1 + \exp(-\langle Y_i, Y_j \rangle)} The empirical probability is p^1(vi,vj)=Wij∑(u,v)∈EWuv\hat{p}_1(v_i, v_j) = \frac{W_{ij}}{\sum_{(u, v) \in E} W_{uv}}. LINE minimizes the Kullback-Leibler (KL) divergence KL(p^1,p1)\mathrm{KL}(\hat{p}_1, p_1), yielding the objective: O1=−∑(i,j)∈EWijlog⁡p1(vi,vj)O_1 = -\sum_{(i, j) \in E} W_{ij} \log p_1(v_i, v_j)

    • Second-Order Proximity: Models the conditional probability of context node vjv_j generated by node viv_i as p2(vj∣vi)=exp⁡(⟨Yj′,Yi⟩)∑k=1∣V∣exp⁡(⟨Yk′,Yi⟩)p_2(v_j | v_i) = \frac{\exp(\langle Y'_j, Y_i \rangle)}{\sum_{k=1}^{|V|} \exp(\langle Y'_k, Y_i \rangle)}, where YiY_i is the node representation and Yj′Y'_j is the context representation. The empirical distribution is p^2(vj∣vi)=Wijdi\hat{p}_2(v_j | v_i) = \frac{W_{ij}}{d_i} where did_i is node out-degree, and the objective minimizes ∑idiKL(p^2(⋅∣vi),p2(⋅∣vi))\sum_{i} d_i \mathrm{KL}(\hat{p}_2(\cdot|v_i), p_2(\cdot|v_i)) via negative sampling in O(∣E∣d)O(|E|d) time.

  6. Knowl 6 — node2vec Biased Random Walk Algorithm

    model/method

    node2vec extends the Skip-Gram architecture of DeepWalk by using second-order biased random walks that interpolate between Breadth-First Search (BFS) and Depth-First Search (DFS). Given a random walk that has traversed edge (t,v)(t, v) and is currently at node vv, the unnormalized transition probability πvx\pi_{vx} to neighbor x∈Vx \in V is πvx=αpq(t,x)⋅wvx\pi_{vx} = \alpha_{pq}(t, x) \cdot w_{vx}, where wvxw_{vx} is the edge weight and the bias term αpq(t,x)\alpha_{pq}(t, x) is defined as:

    αpq(t,x)={1pif dtx=01if dtx=11qif dtx=2\alpha_{pq}(t, x) = \begin{cases} \frac{1}{p} & \text{if } d_{tx} = 0 \\ 1 & \text{if } d_{tx} = 1 \\ \frac{1}{q} & \text{if } d_{tx} = 2 \end{cases}

    where dtxd_{tx} is the shortest path distance between nodes tt and xx (dtx∈{0,1,2}d_{tx} \in \{0, 1, 2\}).

    • Return parameter pp: Controls the likelihood of immediately revisiting the node tt. High values discourage backward steps, reducing local 2-hop redundancy.
    • In-out parameter qq: Controls exploration outward versus inward. Low qq (<1< 1) encourages DFS-like exploration, sampling diverse structural neighborhoods to capture structural equivalence. High qq (>1> 1) biases the walk toward BFS-like local exploration, clustering nodes within the same local community (homophily).

  7. Knowl 7 — Graph Factorization (GF) Objective

    model/method

    Graph Factorization (GF) obtains node embeddings Y∈R∣V∣×dY \in \mathbb{R}^{|V| \times d} in O(∣E∣d)O(|E|d) time by factorizing the graph adjacency matrix over observed edges rather than all possible node pairs. The objective function is:

    ϕ(Y,λ)=12∑(i,j)∈E(Wij−⟨Yi,Yj⟩)2+λ2∑i∈V∥Yi∥22\phi(Y, \lambda) = \frac{1}{2} \sum_{(i, j) \in E} \left(W_{ij} - \langle Y_i, Y_j \rangle\right)^2 + \frac{\lambda}{2} \sum_{i \in V} \|Y_i\|_2^2

    where WijW_{ij} is the adjacency edge weight between nodes viv_i and vjv_j, Yi∈RdY_i \in \mathbb{R}^d is the ii-th row of YY, ⟨Yi,Yj⟩\langle Y_i, Y_j \rangle is the inner product YiYjTY_i Y_j^T, and λ\lambda is a regularization coefficient.

    Restricting the summation to observed edges (i,j)∈E(i, j) \in E provides scalability, but because graph adjacency matrices are generally indefinite, the loss function minimum is strictly greater than 0 even when embedding dimensionality d=∣V∣d = |V|.

  8. Knowl 8 — Evaluation Metrics for Graph Embedding

    equation

    Graph embedding models are evaluated across reconstruction, link prediction, and node classification using the following formulations:

    1. Precision at kk (Pr@k\text{Pr}@k): Pr@k=∣Epred(1:k)∩Eobs∣k\text{Pr}@k = \frac{|E_{\text{pred}}(1:k) \cap E_{\text{obs}}|}{k} where Epred(1:k)E_{\text{pred}}(1:k) are the top kk ranked edge predictions by embedding proximity, and EobsE_{\text{obs}} is the target set (all network edges EE for reconstruction, or hidden test edges for link prediction).

    2. Mean Average Precision (MAP): MAP=1∣V∣∑i=1∣V∣AP(i),AP(i)=∑kPr@k(i)⋅I(Epred,i(k)∈Eobs,i)∣{k:Epred,i(k)∈Eobs,i}∣\text{MAP} = \frac{1}{|V|} \sum_{i=1}^{|V|} \text{AP}(i), \quad \text{AP}(i) = \frac{\sum_{k} \text{Pr}@k(i) \cdot \mathbb{I}\left(E_{\text{pred}, i}(k) \in E_{\text{obs}, i}\right)}{|\{k : E_{\text{pred}, i}(k) \in E_{\text{obs}, i}\}|} where AP(i)\text{AP}(i) is average precision for node viv_i, and I(⋅)\mathbb{I}(\cdot) is the indicator function.

    3. Macro-F1 (for multi-label classification over label set L\mathcal{L}): Macro-F1=1∣L∣∑l∈LF1(l)\text{Macro-F1} = \frac{1}{|\mathcal{L}|} \sum_{l \in \mathcal{L}} \text{F1}(l)

    4. Micro-F1 (aggregating global true positives TP(l)TP(l), false positives FP(l)FP(l), and false negatives FN(l)FN(l)): Micro-F1=2⋅P⋅RP+R,P=∑l∈LTP(l)∑l∈L(TP(l)+FP(l)),R=∑l∈LTP(l)∑l∈L(TP(l)+FN(l))\text{Micro-F1} = \frac{2 \cdot P \cdot R}{P + R}, \quad P = \frac{\sum_{l \in \mathcal{L}} TP(l)}{\sum_{l \in \mathcal{L}} (TP(l) + FP(l))}, \quad R = \frac{\sum_{l \in \mathcal{L}} TP(l)}{\sum_{l \in \mathcal{L}} (TP(l) + FN(l))}

  9. Knowl 9 — Empirical Performance on Graph Reconstruction and Link Prediction

    empirical result

    Comparative evaluation of 128-dimensional node embeddings across synthetic (SYN-SBM) and real networks (PPI, AstroPh, Hep-th, BlogCatalog, YouTube) demonstrates:

    • Graph Reconstruction: SDNE and HOPE consistently achieve the highest reconstruction precision and MAP across datasets. SDNE achieves near-perfect reconstruction even in low dimensions (d=16d=16) through its non-linear autoencoder decoder. node2vec exhibits poor reconstruction precision due to non-linear manifold mapping that does not directly invert to edge distances. For all methods, reconstruction MAP increases monotonically with embedding dimension dd.
    • Link Prediction: Preserving higher-order proximity is critical. HOPE maintains high link prediction MAP across all datasets. SDNE outperforms baseline factorization methods at lower dimensions but degrades on PPI when d>8d > 8. Unlike reconstruction, link prediction performance saturates or deteriorates with higher embedding dimensions on datasets such as BlogCatalog and PPI due to overfitting to observed training edges.

  10. Knowl 10 — Empirical Performance on Node Classification: Homophily vs. Structural Equivalence

    empirical result

    In multi-label node classification (evaluated via one-vs-rest logistic regression across training splits from 10% to 90% on BlogCatalog, PPI, and SYN-SBM):

    • node2vec achieves the highest Micro-F1 and Macro-F1 scores on real-world networks (BlogCatalog and PPI), significantly outperforming Graph Factorization, SDNE, HOPE, and Laplacian Eigenmaps. This advantage arises because real-world labels correlate both with community structure (homophily) and structural roles (structural equivalence), which node2vec simultaneously captures.
    • On synthetic graphs with pure community block structure (SYN-SBM) and no functional structural roles, community-preserving spectral and factorization methods (Laplacian Eigenmaps, HOPE, SDNE) outperform node2vec.
    • Increasing embedding dimensionality beyond d=128d=128 yields diminishing returns or slight degradation in classification F1 scores, while simple community graphs (SYN-SBM) require only d=8d=8 to achieve maximal classification performance.

  11. Knowl 11 — Hyperparameter Sensitivity across Graph Embedding Methods

    empirical result

    Downstream task performance depends heavily on method hyperparameters:

    • Graph Factorization Regularization (λ\lambda): Lower λ\lambda optimizes graph reconstruction but leads to overfitting on observed links. Prediction tasks (link prediction and node classification) improve as λ\lambda increases up to an intermediate optimum (10−110^{-1} on Hep-th and PPI) before deteriorating under excessive regularization.
    • HOPE Attenuation Factor (β\beta): Controls higher-order path decay in the Katz index. On networks with weak community structure (PPI, Hep-th), link prediction requires larger β\beta (2−42^{-4}) to capture distant connections, whereas graph reconstruction is maximized at low β\beta (2−62^{-6}). On tightly clustered networks (SYN-SBM), increasing β\beta reduces performance across all tasks.
    • SDNE Observed Edge Weight: Governs the penalty ratio between observed and unobserved links. Tuning this parameter yields a greater than 3-fold MAP increase in link prediction for Hep-th and a 2-fold increase for PPI, while node classification accuracy remains relatively stable.
    • node2vec Bias Parameters (p,qp, q): Lower in-out parameter qq (promoting DFS exploration and structural equivalence) maximizes node classification accuracy on PPI and Hep-th, whereas higher qq (promoting BFS exploration and local community clustering) maximizes link prediction MAP.

  12. Knowl 12 — GEM: Graph Embedding Methods Software Library

    model/method

    GEM (Graph Embedding Methods) is an open-source Python framework providing a unified and modular interface for node embedding algorithms and standardized downstream evaluations on both weighted and unweighted graphs.

    • Implemented Algorithms: Locally Linear Embedding (LLE), Laplacian Eigenmaps (LE), Graph Factorization (GF), HOPE, SDNE, and node2vec (wrapping an optimized C++ implementation).
    • Evaluation Pipelines: Modular evaluation modules for graph reconstruction, link prediction (with configurable train/test edge splitting), multi-label node classification (using one-vs-rest logistic regression via LIBLINEAR), and 2D graph visualization via t-SNE and PCA.
    • Edge Scoring: Flexible similarity metrics including cosine similarity, Euclidean distance, and neural decoder reconstruction.

Coverage note — Brief mentions of variant algorithms from related literature (e.g., TADW, DDRW, TriDNR, ARE, VGAE) without dedicated experimental benchmarking were omitted in favor of detailed knowls for the primary evaluated methods, taxonomy, and empirical findings.

References

  1. 1.A. Theocharidis, S. Van Dongen, A. Enright, T. Freeman, Network visualization and analysis of gene expression data using biolayout express3d, Nature protocols 4 (2009) 1535–1550.
  2. 2.L. C. Freeman, Visualizing social networks, Journal of social structure 1 (1) (2000) 4.
  3. 3.R. F. i Cancho, R. V. Sol'e, The small world of human language, Proceedings of the Royal Society of London B: Biological Sciences 268 (1482) (2001) 2261–2265.
  4. 4.J. Leskovec, J. Kleinberg, C. Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD) 1 (1) (2007) 2.
  5. 5.D. Liben-Nowell, J. Kleinberg, The link-prediction problem for social networks, journal of the Association for Information Science and Technology 58 (7) (2007) 1019–1031.
  6. 6.S. Bhagat, G. Cormode, S. Muthukrishnan, Node classification in social networks, in: Social network data analytics, Springer, 2011, pp. 115–148.
  7. 7.C. H. Ding, X. He, H. Zha, M. Gu, H. D. Simon, A min-max cut algorithm for graph partitioning and data clustering, in: International Conference on Data Mining, IEEE, 2001, pp. 107–114.
  8. 8.L. v. d. Maaten, G. Hinton, Visualizing data using t-sne, Journal of Machine Learning Research 9 (2008) 2579–2605.
  9. 9.A. Azran, The rendezvous algorithm: Multiclass semi-supervised learning with markov random walks, in: Proceedings of the 24th international conference on Machine learning, 2007, pp. 49–56.
  10. 10.S. Baluja, R. Seth, D. Sivakumar, Y. Jing, J. Yagnik, S. Kumar, D. Ravichandran, M. Aly, Video suggestion and discovery for youtube: taking random walks through the view graph, in: Proc. 17th int. conference on World Wide Web, 2008, pp. 895–904.
  11. 11.S. Bhagat, I. Rozenbaum, G. Cormode, Applying link-based classification to label blogs, in: Proceedings of WebKDD: workshop on Web mining and social network analysis, ACM, 2007, pp. 92–101.
  12. 12.Q. Lu, L. Getoor, Link-based classification, in: ICML, Vol. 3, 2003, pp. 496–503.
  13. 13.P. Jaccard, Etude comparative de la distribution florale dans une portion des Alpes et du Jura, Impr. Corbaz, 1901.
  14. 14.L. A. Adamic, E. Adar, Friends and neighbors on the web, Social networks 25 (3) (2003) 211–230.
  15. 15.A. Clauset, C. Moore, M. E. Newman, Hierarchical structure and the prediction of missing links in networks, Nature 453 (7191) (2008) 98–101.
  16. 16.H. C. White, S. A. Boorman, R. L. Breiger, Social structure from multiple networks. i. blockmodels of roles and positions, American journal of sociology 81 (4) (1976) 730–780.
  17. 17.N. Friedman, L. Getoor, D. Koller, A. Pfeffer, Learning probabilistic relational models, in: IJCAI, 1999, pp. 1300–1309.
  18. 18.D. Heckerman, C. Meek, D. Koller, Probabilistic entity-relationship models, prms, and plate models, Introduction to statistical relational learning (2007) 201–238.
  19. 19.Y. Zhou, H. Cheng, J. X. Yu, Graph clustering based on structural/attribute similarities, Proceedings of the VLDB Endowment 2 (1) (2009) 718–729.
  20. 20.J. Shi, J. Malik, Normalized cuts and image segmentation, IEEE Transactions on pattern analysis and machine intelligence 22 (8) (2000) 888–905.
  21. 21.A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, A. J. Smola, Distributed large-scale natural graph factorization, in: Proceedings of the 22nd international conference on World Wide Web, ACM, 2013, pp. 37–48.
  22. 22.J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, Q. Mei, Line: Largescale information network embedding, in: Proceedings 24th International Conference on World Wide Web, 2015, pp. 1067–1077.
  23. 23.D. Wang, P. Cui, W. Zhu, Structural deep network embedding, in: Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, ACM, 2016, pp. 1225–1234.
  24. 24.M. Ou, P. Cui, J. Pei, Z. Zhang, W. Zhu, Asymmetric transitivity preserving graph embedding, in: Proc. of ACM SIGKDD, 2016, pp. 1105–1114.
  25. 25.M. Belkin, P. Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, in: NIPS, Vol. 14, 2001, pp. 585–591.
  26. 26.S. T. Roweis, L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science 290 (5500) (2000) 2323–2326.
  27. 27.S. Cao, W. Lu, Q. Xu, Grarep: Learning graph representations with global structural information, in: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, ACM, 2015, pp. 891–900.
  28. 28.B. Perozzi, R. Al-Rfou, S. Skiena, Deepwalk: Online learning of social representations, in: Proceedings 20th international conference on Knowledge discovery and data mining, 2014, pp. 701–710.
  29. 29.A. Grover, J. Leskovec, node2vec: Scalable feature learning for networks, in: Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, ACM, 2016, pp. 855–864.
  30. 30.S. Cao, W. Lu, Q. Xu, Deep neural networks for learning graph representations, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016, pp. 1145–1152.
  31. 31.T. N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, arXiv preprint arXiv:1609.02907.
  32. 32.D. Luo, F. Nie, H. Huang, C. H. Ding, Cauchy graph embedding, in: Proceedings of the 28th International Conference on Machine Learning (ICML-11), 2011, pp. 553–560.
  33. 33.B. Shaw, T. Jebara, Structure preserving embedding, in: Proceedings of the 26th Annual International Conference on Machine Learning, ACM, 2009, pp. 937–944.
  34. 34.C. F. Van Loan, Generalizing the singular value decomposition, SIAM Journal on Numerical Analysis 13 (1) (1976) 76–83.
  35. 35.S. Yan, D. Xu, B. Zhang, H.-J. Zhang, Q. Yang, S. Lin, Graph embedding and extensions: A general framework for dimensionality reduction, IEEE transactions on pattern analysis and machine intelligence 29 (1) (2007) 40–51.
  36. 36.I. T. Jolliffe, Principal component analysis and factor analysis, in: Principal component analysis, Springer, 1986, pp. 115–128.
  37. 37.A. M. Mart'ınez, A. C. Kak, Pca versus lda, IEEE transactions on pattern analysis and machine intelligence 23 (2) (2001) 228–233.
  38. 38.J. B. Tenenbaum, V. De Silva, J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, science 290 (5500) (2000) 2319–2323.
  39. 39.J. B. Kruskal, M. Wish, Multidimensional scaling, Vol. 11, Sage, 1978.
  40. 40.X. He, P. Niyogi, Locality preserving projections, in: Advances in neural information processing systems, 2004, pp. 153–160.
  41. 41.M. Brand, Continuous nonlinear dimensionality reduction by kernel eigenmaps, in: IJCAI, 2003, pp. 547–554.
  42. 42.A. M. Mart'ınez, A. C. Kak, Non-negative graph embedding, IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR) 23 (2) (2008) 1–8.
  43. 43.Y.-Y. Lin, T.-L. Liu, H.-T. Chen, Semantic manifold learning for image retrieval, in: Proceedings of the 13th annual ACM international conference on Multimedia, ACM, 2005, pp. 249–258.
  44. 44.C. Yang, Z. Liu, D. Zhao, M. Sun, E. Y. Chang, Network representation learning with rich text information., in: IJCAI, 2015, pp. 2111–2117.
  45. 45.S. Chang, W. Han, J. Tang, G.-J. Qi, C. C. Aggarwal, T. S. Huang, Heterogeneous network embedding via deep architectures, in: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2015, pp. 119–128.
  46. 46.C. Tu, W. Zhang, Z. Liu, M. Sun, Max-margin deepwalk: Discriminative learning of network representation., in: IJCAI, 2016, pp. 3889–3895.
  47. 47.D. Zhang, J. Yin, X. Zhu, C. Zhang, Homophily, structure, and content augmented network representation learning, in: Data Mining (ICDM), 2016 IEEE 16th International Conference on, IEEE, 2016, pp. 609–618.
  48. 48.X. Huang, J. Li, X. Hu, Label informed attributed network embedding, in: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, ACM, 2017, pp. 731–739.
  49. 49.M. E. Newman, A measure of betweenness centrality based on random walks, Social networks 27 (1) (2005) 39–54.
  50. 50.F. Fouss, A. Pirotte, J.-M. Renders, M. Saerens, Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Transactions on knowledge and data engineering 19 (3).
  51. 51.H. Chen, B. Perozzi, Y. Hu, S. Skiena, Harp: Hierarchical representation learning for networks, arXiv preprint arXiv:1706.07845.
  52. 52.B. Perozzi, V. Kulkarni, S. Skiena, Walklets: Multiscale graph embeddings for interpretable network classification, arXiv preprint arXiv:1605.02115.
  53. 53.Z. Yang, J. Tang, W. W. Cohen, Multi-modal bayesian embeddings for learning social knowledge graphs., in: IJCAI, 2016, pp. 2287–2293.
  54. 54.J. Li, J. Zhu, B. Zhang, Discriminative deep random walk for network classification., in: ACL (1), 2016.
  55. 55.S. Pan, J. Wu, X. Zhu, C. Zhang, Y. Wang, Tri-party deep network representation, Network 11 (9) (2016) 12.
  56. 56.Z. Yang, W. W. Cohen, R. Salakhutdinov, Revisiting semi-supervised learning with graph embeddings, arXiv preprint arXiv:1603.08861.
  57. 57.M. Niepert, M. Ahmed, K. Kutzkov, Learning convolutional neural networks for graphs, in: Proceedings of the 33rd annual international conference on machine learning. ACM, 2016.
  58. 58.Y. Bengio, A. Courville, P. Vincent, Representation learning: A review and new perspectives, IEEE transactions on pattern analysis and machine intelligence 35 (8) (2013) 1798–1828.
  59. 59.J. Bruna, W. Zaremba, A. Szlam, Y. LeCun, Spectral networks and locally connected networks on graphs, arXiv preprint arXiv:1312.6203.
  60. 60.M. Henaff, J. Bruna, Y. LeCun, Deep convolutional networks on graphstructured data, arXiv preprint arXiv:1506.05163.
  61. 61.D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, R. P. Adams, Convolutional networks on graphs for learning molecular fingerprints, in: Advances in neural information processing systems, 2015, pp. 2224–2232.
  62. 62.Y. Li, D. Tarlow, M. Brockschmidt, R. Zemel, Gated graph sequence neural networks, arXiv preprint arXiv:1511.05493.
  63. 63.M. Defferrard, X. Bresson, P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering, in: Advances in Neural Information Processing Systems, 2016, pp. 3844–3852.
  64. 64.W. L. Hamilton, R. Ying, J. Leskovec, Inductive representation learning on large graphs, arXiv preprint arXiv:1706.02216.
  65. 65.T. N. Kipf, M. Welling, Variational graph auto-encoders, arXiv preprint arXiv:1611.07308.
  66. 66.D. P. Kingma, M. Welling, Auto-encoding variational bayes, arXiv preprint arXiv:1312.6114.
  67. 67.K. Hornik, M. Stinchcombe, H. White, Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks, Neural networks 3 (1990) 551–560.
  68. 68.T. Feder, R. Motwani, Clique partitions, graph compression and speeding-up algorithms, in: Proceedings of the twenty-third annual ACM symposium on Theory of computing, 1991, pp. 123–133.
  69. 69.P. M. Pardalos, J. Xue, The maximum clique problem, Journal of global Optimization 4 (3) (1994) 301–328.
  70. 70.Y. Tian, R. A. Hankins, J. M. Patel, Efficient aggregation for graph summarization, in: Proceedings of the SIGMOD international conference on Management of data, ACM, 2008, pp. 567–580.
  71. 71.H. Toivonen, F. Zhou, A. Hartikainen, A. Hinkka, Compression of weighted graphs, in: Proc. 17th international conference on Knowledge discovery and data mining, 2011, pp. 965–973.
  72. 72.S. Navlakha, R. Rastogi, N. Shrivastava, Graph summarization with bounded error, in: Proceedings of the international conference on Management of data, ACM, 2008, pp. 419–432.
  73. 73.J. Rissanen, Modeling by shortest data description, Automatica 14 (5) (1978) 465–471.
  74. 74.D. Jungnickel, T. Schade, Graphs, networks and algorithms, Springer, 2005.
  75. 75.E. R. Gansner, S. C. North, An open graph visualization system and its applications to software engineering, Software Practice and Experience 30 (11) (2000) 1203–1233.
  76. 76.G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry 4 (5) (1994) 235–282.
  77. 77.P. Eades, L. Xuemin, How to draw a directed graph, in: Visual Languages, 1989., IEEE Workshop on, IEEE, 1989, pp. 13–17.
  78. 78.I. Herman, G. Melançon, M. S. Marshall, Graph visualization and navigation in information visualization: A survey, IEEE Trans on visualization and computer graphics 6 (1) (2000) 24–43.
  79. 79.K. Pearson, Liii. on lines and planes of closest fit to systems of points in space, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 2 (11) (1901) 559–572.
  80. 80.M. E. Newman, M. Girvan, Finding and evaluating community structure in networks, Physical review E 69 (2) (2004) 026113.
  81. 81.X. Xu, N. Yuruk, Z. Feng, T. A. Schweiger, Scan: a structural clustering algorithm for networks, in: Proceedings 13th international conference on Knowledge discovery and data mining, 2007, pp. 824–833.
  82. 82.S. White, P. Smyth, A spectral clustering approach to finding communities in graphs, in: Proceedings of the 2005 SIAM international conference on data mining, SIAM, 2005, pp. 274–285.
  83. 83.L. Lü, T. Zhou, Link prediction in complex networks: A survey, Physica A: Statistical Mechanics and its Applications 390 (6) (2011) 1150–1170.
  84. 84.M. Al Hasan, M. J. Zaki, A survey of link prediction in social networks, in: Social network data analytics, 2011, pp. 243–275.
  85. 85.L. Katz, A new status index derived from sociometric analysis, Psychometrika 18 (1) (1953) 39–43.
  86. 86.K. Yu, W. Chu, S. Yu, V. Tresp, Z. Xu, Stochastic relational models for discriminative link prediction, in: NIPS, 2006, pp. 1553–1560.
  87. 87.J. Neville, D. Jensen, Iterative classification in relational data, in: Proc. Workshop on Learning Statistical Models from Relational Data, 2000, pp. 13–20.
  88. 88.D. W. Hosmer Jr, S. Lemeshow, R. X. Sturdivant, Applied logistic regression, Vol. 398, John Wiley & Sons, 2013.
  89. 89.A. McCallum, K. Nigam, et al., A comparison of event models for naive bayes text classification, in: AAAI-98 workshop on learning for text categorization, Vol. 752, Citeseer, 1998, pp. 41–48.
  90. 90.Y. J. Wang, G. Y. Wong, Stochastic blockmodels for directed graphs, Journal of the American Statistical Association 82 (397) (1987) 8–19.
  91. 91.W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of anthropological research 33 (4) (1977) 452–473.
  92. 92.L. Tang, H. Liu, Relational learning via latent social dimensions, in: Proceedings of the 15th international conference on Knowledge discovery and data mining, ACM, 2009, pp. 817–826.
  93. 93.L. Tang, H. Liu, Scalable learning of collective behavior based on sparse social dimensions, in: Proceedings of the 18th ACM conference on Information and knowledge management, ACM, 2009, pp. 1107–1116.
  94. 94.J. Gehrke, P. Ginsparg, J. Kleinberg, Overview of the 2003 kdd cup, ACM SIGKDD Explorations 5 (2).
  95. 95.J. Leskovec, A. Krevl, SNAP Datasets: Stanford large network dataset collection, http://snap.stanford.edu/data (2014).
  96. 96.B.-J. Breitkreutz, C. Stark, T. Reguly, L. Boucher, A. Breitkreutz, M. Livstone, R. Oughtred, D. H. Lackner, J. Bähler, V. Wood, et al., The biogrid interaction database: 2008 update, Nucleic acids research 36 (suppl 1) (2008) D637–D640.
  97. 97.H. Dai, Y. Wang, R. Trivedi, L. Song, Deep coevolutionary network: Embedding user and item features for recommendation.
  98. 98.P. Goyal, N. Kamra, X. He, Y. Liu, Dyngem: Deep embedding method for dynamic graphs.
  99. 99.L. Zhu, D. Guo, J. Yin, G. Ver Steeg, A. Galstyan, Scalable temporal latent space inference for link prediction in dynamic social networks, IEEE Transactions on Knowledge and Data Engineering 28 (10) (2016) 2765–2777.
  100. 100.P. W. Holland, K. B. Laskey, S. Leinhardt, Stochastic blockmodels: First steps, Social networks 5 (2) (1983) 109–137.

Citation

MLA
Goyal, P., and E. Ferrara. “Graph Embedding Techniques, Applications, and Performance: A Survey”. Knowledge-Based Systems, vol. 151, 2018, pp. 78–94, https://doi.org/10.1016/j.knosys.2018.03.022.
APA
Goyal, P., & Ferrara, E. (2018). Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 151, 78–94. https://doi.org/10.1016/j.knosys.2018.03.022
Chicago
Goyal, P., and E. Ferrara. 2018. “Graph Embedding Techniques, Applications, and Performance: A Survey”. Knowledge-Based Systems 151: 78–94. https://doi.org/10.1016/j.knosys.2018.03.022.
Harvard
Goyal, P. and Ferrara, E. (2018) “Graph embedding techniques, applications, and performance: A survey”, Knowledge-Based Systems, 151, pp. 78–94. Available at: https://doi.org/10.1016/j.knosys.2018.03.022.
Vancouver
1. Goyal P, Ferrara E (2018) Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems 151:78–94

BibTeX

@article{Goyal_2018, title={Graph embedding techniques, applications, and performance: A survey}, volume={151}, ISSN={0950-7051}, url={http://dx.doi.org/10.1016/j.knosys.2018.03.022}, DOI={10.1016/j.knosys.2018.03.022}, journal={Knowledge-Based Systems}, publisher={Elsevier BV}, author={Goyal, Palash and Ferrara, Emilio}, year={2018}, month=July, pages={78–94} }
Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF