A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications

Hongyun CaiVincent W. ZhengKevin Chen-Chuan Chang

article2017TKDE1,980 citations

Presents dual taxonomies that systematically categorize graph embedding problem settings and algorithmic solutions, clarifying how low-dimensional representations preserve network structure for downstream applications like node classification and link prediction.

Listen

Graph data structures are ubiquitous across vital digital applications, including social networks, e-commerce, citation networks, and knowledge bases. Analyzing these networks yields powerful insights for tasks such as customer recommendation, fraud detection, and automated categorization. However, traditional graph analytics suffer from severe computational bottlenecks and excessive memory consumption when processing large, complex networks. Graph embedding addresses these performance limits by transforming discrete, high-dimensional relational data into compact, low-dimensional continuous vectors while preserving core structural properties and contextual relationships.

The article provides a systematic and comprehensive evaluation of graph embedding techniques, formulations, and applications. Specifically, it establishes two structured taxonomies to categorize the field by problem settings (inputs and outputs) and underlying methodological techniques, while identifying current technological trade-offs and defining future research priorities.

To establish this framework, the article synthesizes extensive foundational literature across diverse operational domains. It structures graph embedding problem inputs into four distinct classes: homogeneous networks, complex heterogeneous networks, networks enriched with auxiliary data (such as textual metadata, labels, and propagation dynamics), and relational graphs constructed from non-relational features. Embedding outputs are mapped across four distinct operational granularities: individual nodes, edges or node pairs, hybrid substructures (subgraphs and communities), and whole graphs. The methodological solutions are systematically classified into matrix factorization, deep learning architectures, edge reconstruction optimization, graph kernels, and generative probabilistic models.

The core findings demonstrate that no single embedding technique is universally optimal, as each balances structural expressiveness against computational scalability. Matrix factorization effectively captures global node proximities but becomes computationally prohibitive on massive datasets due to resource-intensive matrix decomposition. Deep learning models provide high representational power; however, random walk approaches only capture local path contexts, while deep whole-graph networks require heavy computational resources due to non-grid graph topologies. Edge reconstruction methods offer faster training by optimizing observed links and triplets, but they inherently omit broader, global structural awareness. Graph kernels efficiently summarize entire graphs for classification, yet their dimensions grow exponentially with substructure size. Finally, generative models naturally integrate diverse data modalities into interpretable latent spaces, but they rely heavily on massive training volumes and hard-to-verify distributional assumptions.

These findings indicate that choosing a graph embedding strategy requires clear trade-offs between computational performance, implementation risk, and analytical scope. For enterprise applications, utilizing compact vector embeddings significantly lowers downstream storage overhead and processing latencies for machine learning workloads, including link prediction, classification, and cross-platform network alignment. Applying oversimplified local methods risks missing critical macro-network patterns, while deploying complex deep models without proper hardware acceleration can lead to unsustainable infrastructure costs.

Decision-makers and practitioners should align embedding models directly with operational task requirements, utilizing lightweight edge or random walk models for localized tasks and kernel or hierarchical methods for holistic graph-level decisions. Furthermore, research and development efforts should focus on resolving several critical gaps: improving hardware and computational efficiency for non-Euclidean deep architectures, creating scalable and incremental frameworks for dynamic and evolving real-time graphs, and incorporating broader substructure awareness beyond single-edge approximations into efficient embedding models.

The conclusions of the article are constrained by its focus on static network paradigms, as dynamic graph processing remains an open challenge. Additionally, the qualitative nature of this comparative literature survey means performance varies across specific real-world domain implementations. Nevertheless, the article provides high confidence and a solid architectural blueprint for navigating graph embedding technologies across modern data systems.

Advanced Digital Sciences Center University of Illinois Urbana-Champaign bipartite graphs classification computational efficiency graph embeddings network representation learning node embeddings

arXiv: 1709.07604

Paper: DeepWalk: online learning of social representations, Bryan Perozzi et al. (2014). DeepWalk establishes the foundational paradigm of learning continuous network representations using truncated random walks and language modeling techniques that modern graph embedding surveys categorize.
Paper: LINE: Large-scale Information Network Embedding, Jian Tang et al. (2015). LINE introduces explicit objective functions for preserving both first-order and second-order node proximity, forming a core benchmark in graph embedding taxonomies.
Paper: node2vec: Scalable Feature Learning for Networks, Aditya Grover et al. (2016). node2vec provides the flexible biased random walk framework essential for understanding how modern embedding methods balance local and global network neighborhood exploration.
Paper: Structural Deep Network Embedding, Daixin Wang et al. (2016). SDNE presents the deep neural autoencoder formulation for capturing highly non-linear first- and second-order graph structures evaluated extensively in the survey.
Paper: Graph Embedding and Extensions: A General Framework for Dimensionality Reduction, Shuicheng Yan et al. (2007). This seminal paper introduces the general graph embedding framework unifying classical dimensionality reduction techniques under graph preservation objectives.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). Laplacian Eigenmaps establishes the mathematical foundations of spectral graph embedding and neighborhood-preserving manifold learning.
Paper: Revisiting Semi-Supervised Learning with Graph Embeddings, Zhilin Yang et al. (2016). Planetoid provides the transductive and inductive semi-supervised embedding formulation that connects classic graph embeddings with modern neural classification pipelines.
Paper: Variational Graph Auto-Encoders, Thomas N. Kipf et al. (2016). VGAE introduces the variational autoencoder framework for unsupervised graph embedding and link prediction on attributed networks.
Paper: The Graph Neural Network Model, Franco Scarselli et al. (2009). This paper establishes the original recursive neural network formulation for processing graph topologies directly.

Paper: A Comprehensive Survey on Graph Neural Networks, Zonghan Wu et al. (2019). This survey expands upon traditional graph embedding taxonomies by providing a comprehensive structural overview of modern deep graph neural network architectures.
Paper: Graph Neural Networks: A Review of Methods and Applications, Jie Zhou et al. (2018). This review synthesizes the message-passing frameworks and applications that emerged as the successor paradigm to early graph embedding methods.
Paper: Graph Attention Networks, Petar Veličković et al. (2018). Graph Attention Networks enhance graph representation learning by dynamically weighting neighbor importance via self-attention mechanisms.
Paper: Graph Convolutional Neural Networks for Web-Scale Recommender Systems, Rex Ying et al. (2018). PinSage scales graph convolution and embedding techniques to multi-billion-node industrial web recommendation graphs.
Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). This work establishes the theoretical expressive limits of aggregation-based graph embedding and neural network models via the Weisfeiler-Lehman test.
Paper: Deep Graph Infomax, Petar Veličković et al. (2019). Deep Graph Infomax advances unsupervised graph embedding by maximizing mutual information between local node representations and global graph summaries.
Paper: A Survey on Knowledge Graphs: Representation, Acquisition, and Applications, Shaoxiong Ji et al. (2020). This survey extends embedding principles to multi-relational knowledge graphs, detailing advanced relational scoring functions and knowledge completion.
Paper: Open Graph Benchmark: Datasets for Machine Learning on Graphs, Weihua Hu et al. (2020). The Open Graph Benchmark provides standardized, large-scale benchmarks to address the real-world evaluation challenges highlighted in earlier graph embedding literature.

Cover for A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications

Abstract

Graph is an important data representation which appears in a wide diversity of real-world scenarios. Effective graph analytics provides users a deeper understanding of what is behind the data, and thus can benefit a lot of useful applications such as node classification, node recommendation, link prediction, etc. However, most graph analytics methods suffer the high computation and space cost. Graph embedding is an effective yet efficient way to solve the graph analytics problem. It converts the graph data into a low dimensional space in which the graph structural information and graph properties are maximally preserved. In this survey, we conduct a comprehensive review of the literature in graph embedding. We first introduce the formal definition of graph embedding as well as the related concepts. After that, we propose two taxonomies of graph embedding which correspond to what challenges exist in different graph embedding problem settings and how the existing work address these challenges in their solutions. Finally, we summarize the applications that graph embedding enables and suggest four promising future research directions in terms of computation efficiency, problem settings, techniques and application scenarios.

Topics

bipartite graphs classification computational efficiency directed graphs embedding problems general graph graph embeddings link prediction recommendation weighted graph

Keywords

graph embeddings network representation learning node embeddings graph representations graph kernels graph completion graph mining knowledge graph heterogeneous graph

I Introduction
I-A Our Contributions
I-B Organization of The Survey
II Problem Formalization
II-A Notation and Definition
III Problem Settings of Graph Embedding
III-A Graph Embedding Input
III-A1 Homogeneous Graph
III-A2 Heterogeneous Graph
III-A3 Graph with Auxiliary Information
III-A4 Graph Constructed from Non-relational Data
III-B Graph Embedding Output
III-B1 Node Embedding
III-B2 Edge Embedding
III-B3 Hybrid Embedding
III-B4 Whole-Graph Embedding
IV Graph Embedding Techniques
IV-A Matrix Factorization
IV-A1 Graph Laplacian Eigenmaps
IV-A2 Node Proximity Matrix Factorization
IV-B Deep Learning
IV-B1 DL based Graph Embedding with Random Walk
IV-B2 DL based Graph Embedding without Random Walk
IV-C Edge Reconstruction based Optimization
IV-C1 Maximizing Edge Reconstruction Probability
IV-C2 Minimizing Distance-based Loss
IV-C3 Minimizing Margin-based Ranking Loss
IV-D Graph Kernel
IV-E Generative Model
IV-E1 Embed Graph Into The Latent Semantic Space
IV-E2 Incorporate Latent Semantics for Graph Embedding
IV-F Hybrid Techniques and Others
IV-G Summary
V Applications
V-A Node Related Applications
V-A1 Node Classification
V-A2 Node Clustering
V-A3 Node Recommendation/Retrieval/Ranking
V-B Edge Related Applications
V-B1 Link Prediction
V-B2 Triple Classification
V-C Graph Related Applications
V-C1 Graph Classification
V-C2 Visualization
V-D Other Applications
VI Future Directions
VII Conclusions
References

Knowls

Knowl 1 — Formal Definition of Graph Embedding and Graph Proximities
definition
Let $G = (V, E)$ be a graph where $V$ denotes the set of vertices (nodes) and $E$ denotes the set of edges. The graph $G$ is associated with a node type mapping $f_v: V \to T^v$ and an edge type mapping $f_e: E \to T^e$ , where $T^v$ and $T^e$ denote the sets of node types and edge types, respectively. A homogeneous graph satisfies $|T^v| = |T^e| = 1$ , whereas a heterogeneous graph satisfies $|T^v| > 1$ or $|T^e| > 1$ . A knowledge graph is a directed heterogeneous graph whose edges represent subject-property-object fact triples $(h, r, t)$ with head entity $h \in V$ , relation $r \in E$ , and tail entity $t \in V$ .

Given an input graph $G = (V, E)$ and a target embedding dimensionality $d$ where $d \ll |V|$ , graph embedding maps $G$ into a $d$ -dimensional vector space such that structural information and graph properties are preserved. Graph embedding represents the graph as either a single $d$ -dimensional vector $y_G \in \mathbb{R}^d$ (for whole-graph embedding) or a set of $d$ -dimensional vectors $y_i, y_{ij}, y_{\hat{G}} \in \mathbb{R}^d$ representing node $v_i$ , edge $e_{ij}$ , or substructure $\hat{G} = (\hat{V}, \hat{E})$ with $\hat{V} \subseteq V, \hat{E} \subseteq E$ .

Graph properties to be preserved are formalized via proximity measures:
- First-Order Proximity: The direct local pairwise connection strength between node $v_i$ and node $v_j$ , defined by edge weight $A_{i,j}$ from adjacency matrix $A$ : $s^{(1)}_{ij} = A_{i,j}$ Let $s^{(1)}_i = [s^{(1)}_{i1}, s^{(1)}_{i2}, \dots, s^{(1)}_{i|V|}]$ denote the vector of first-order proximities between $v_i$ and all nodes in $V$ .
- Second-Order Proximity: The similarity between the 1-hop neighborhood structures of $v_i$ and $v_j$ : $s^{(2)}_{ij} = \text{CosineSimilarity}\left(s^{(1)}_i, s^{(1)}_j\right) = \frac{s^{(1)}_i \cdot s^{(1)}_j}{\|s^{(1)}_i\| \|s^{(1)}_j\|}$ Two nodes have non-zero second-order proximity if they share common adjacent neighbors, even if they have no direct connecting edge.
- Higher-Order Proximity: Recursively defined as the similarity between $(k-1)$ -th-order neighborhood representations $s^{(k-1)}_i$ and $s^{(k-1)}_j$ , or computed using graph reachability indices (e.g., Katz Index, Rooted PageRank, Adamic-Adar).
Knowl 2 — Taxonomy of Graph Embedding Problem Settings
model/method
The problem setting of graph embedding is categorized along two orthogonal dimensions: embedding input and embedding output.

1. Embedding Input Categories
- Homogeneous Graph: Nodes and edges belong to single uniform types ( $|T^v| = |T^e| = 1$ ), which may be weighted/unweighted and directed/undirected. Core Challenge: Capturing the diversity of structural connectivity patterns without auxiliary signals.
- Heterogeneous Graph: Contains multiple entity types ( $|T^v| > 1$ ) and/or multiple edge types ( $|T^e| > 1$ ), such as community question-answering networks (questions, answers, users), multimedia networks (images, text tags), and knowledge graphs. Core Challenge: Preserving global consistency across different object spaces while handling severe type imbalance and data skew.
- Graph with Auxiliary Information: Topological graph augmented by auxiliary data, including categorical labels, continuous or discrete node/edge attributes, unstructured node text/multimedia features, information cascade sequences, or knowledge base concepts. Core Challenge: Fusing unstructured, rich auxiliary features with network topology so that embeddings represent topological structure while remaining discriminative for auxiliary properties.
- Graph Constructed from Non-Relational Data: Input is non-relational feature data $X \in \mathbb{R}^{|V| \times N}$ , and relational edges are constructed via $K$ -nearest neighbor (KNN) graphs, pairwise feature kernels, spatial proximity, co-occurrence, or positive/negative feedback graphs. Core Challenge: Determining an optimal graph construction scheme that faithfully captures manifold geometry and encodes pairwise relations.
2. Embedding Output Categories
- Node Embedding: Maps each node $v_i$ to $y_i \in \mathbb{R}^d$ , preserving pairwise neighborhood proximity.
- Edge Embedding: Maps each edge $e_{ij}$ or node pair $(v_i, v_j)$ to $y_{ij} \in \mathbb{R}^d$ , capturing edge semantics and asymmetric/directed relation properties.
- Hybrid Embedding: Simultaneously embeds heterogeneous combinations of graph components (e.g., node + edge paths, node + community distributions represented as multivariate Gaussians).
- Whole-Graph Embedding: Maps an entire graph $G$ into a single vector $y_G \in \mathbb{R}^d$ for graph-level comparison, balancing expressiveness with computational tractability.
Knowl 3 — Transductive and Inductive Formulations for Graph Laplacian Eigenmaps
equation
Graph Laplacian eigenmaps preserve pairwise similarity by penalizing large embedding distances between similar nodes.

Let $W \in \mathbb{R}^{|V| \times |V|}$ be a pairwise similarity matrix where $W_{ij}$ measures the affinity between node $v_i$ and $v_j$ . Let $D$ be the diagonal degree matrix with $D_{ii} = \sum_{j \neq i} W_{ij}$ , and let $L = D - W$ denote the graph Laplacian matrix.

1. Transductive Formulation

For fixed training nodes, the embedding vector $y \in \mathbb{R}^{|V|}$ is obtained by minimizing the Laplacian quadratic form subject to a scale-normalization constraint: $y^* = \arg\min_{y^T D y = 1} \sum_{i \neq j} \|y_i - y_j\|^2 W_{ij} = \arg\min_{y^T D y = 1} y^T L y = \arg\max \frac{y^T W y}{y^T D y}$ The optimal embedding dimensions are given by the eigenvectors corresponding to the smallest non-trivial eigenvalues of the generalized eigenproblem $L y = \lambda D y$ (or equivalently the maximum eigenvalues of $W y = \lambda D y$ ).

2. Inductive Formulation

To embed unseen nodes with feature matrix $X \in \mathbb{R}^{|V| \times N}$ (where row $X_i$ is an $N$ -dimensional feature vector for $v_i$ ), a linear mapping $y = X^T a$ is defined with transformation vector $a \in \mathbb{R}^N$ : $a^* = \arg\min_{a^T X D X^T a = 1} \sum_{i \neq j} \|a^T X_i - a^T X_j\|^2 W_{ij} = \arg\min_{a^T X D X^T a = 1} a^T X L X^T a = \arg\max \frac{a^T X W X^T a}{a^T X D X^T a}$ The optimal transformation vectors $a$ are the eigenvectors corresponding to the maximum eigenvalues of the generalized eigenproblem: $X W X^T a = \lambda X D X^T a$
Knowl 4 — Node Proximity Matrix Factorization Formulation
equation
Node proximity matrix factorization computes low-dimensional embeddings by approximating a global proximity matrix $W \in \mathbb{R}^{|V| \times |V|}$ with the inner product of low-rank matrices.

Given the node proximity matrix $W$ (such as Katz Index, Personalized PageRank, Adamic-Adar, or Positive Pointwise Mutual Information (PPMI)), the optimization problem is formulated as: $\min_{Y, Y^c} \|W - Y (Y^c)^T\|_F^2$ where $Y \in \mathbb{R}^{|V| \times d}$ denotes the target node embedding matrix, $Y^c \in \mathbb{R}^{|V| \times d}$ denotes the context node embedding matrix, and $\|\cdot\|_F$ is the Frobenius norm.

An optimal rank- $d$ approximation is obtained via truncated Singular Value Decomposition (SVD): $W = \sum_{i=1}^{|V|} \sigma_i u_i (u^c_i)^T \approx \sum_{i=1}^d \sigma_i u_i (u^c_i)^T$ where $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_d$ are the top $d$ singular values, and $u_i, u^c_i$ are their corresponding left and right singular vectors. The embeddings are constructed as: $Y = \left[\sqrt{\sigma_1} u_1, \sqrt{\sigma_2} u_2, \dots, \sqrt{\sigma_d} u_d\right]$ $Y^c = \left[\sqrt{\sigma_1} u^c_1, \sqrt{\sigma_2} u^c_2, \dots, \sqrt{\sigma_d} u^c_d\right]$

If the proximity matrix is asymmetric, the final representation for node $v_i$ is formed by concatenating target and context vectors: $y_i = [Y_i, Y^c_i] \in \mathbb{R}^{2d}$ . For symmetric proximity, the representation is $y_i = Y_i \in \mathbb{R}^d$ .
Knowl 5 — Random-Walk-Based Deep Learning for Graph Embedding
model/method
Random-walk-based deep learning methods sample sequences of nodes from a graph via random walks and apply neural sequence models (such as SkipGram or Recurrent Neural Networks) to learn node and path representations.

1. SkipGram Objective Formulation

Given a sampled path sequence, SkipGram maximizes the log-probability of observing context neighborhood nodes within a window size $w$ conditioned on the center node embedding $y_i$ : $\min_y \sum_{v_i \in V} \sum_{-w \le j \le w, j \neq 0} -\log P(v_{i+j} \mid y_i)$ where the conditional probability is defined via the softmax function: $P(v_{i+j} \mid y_i) = \frac{\exp(y_{i+j}^T y_i)}{\sum_{k=1}^{|V|} \exp(y_k^T y_i)}$

2. Scalable Approximations

Computing the denominator requires $O(|V|)$ operations per step. Two approximation strategies are used:
- Hierarchical Softmax: Constructs a balanced binary tree with vertices assigned to leaves. The conditional probability is the product of path probabilities from root $b_0$ to leaf $b_{\lceil \log |V| \rceil} = v_{i+j}$ : $P(v_{i+j} \mid y_i) = \prod_{t=1}^{\lceil \log |V| \rceil} P(b_t \mid y_i) = \prod_{t=1}^{\lceil \log |V| \rceil} \sigma\left(y_{b_t}^T y_i\right)$ where $\sigma(x) = \frac{1}{1 + \exp(-x)}$ and $y_{b_t}$ is the parent node vector. This reduces time complexity from $O(|V|^2)$ to $O(|V| \log |V|)$ .
- Negative Sampling: Replaces the multi-class partition function with binary logistic regression distinguishing true context node $v_{i+j}$ from $K$ noise nodes drawn from noise distribution $P_n(v)$ : $\log P(v_{i+j} \mid y_i) \approx \log \sigma\left(y_{i+j}^T y_i\right) + \sum_{t=1}^K \mathbb{E}_{v_t \sim P_n}\left[\log \sigma\left(-y_{v_t}^T y_i\right)\right]$ This reduces complexity to $O(K |V|)$ .
3. Walk Sampling and Sequential Embeddings
- Sampling strategies range from uniform truncated walks (DeepWalk) to biased parameterized random walks balancing BFS and DFS exploration (node2vec), and meta-path-guided walks for heterogeneous graphs (metapath2vec).
- When paths encode directional semantics or information cascades (e.g., DeepCas), Long Short-Term Memory (LSTM) or Gated Recurrent Units (GRU) are used to aggregate node sequences into vector embeddings.
Knowl 6 — Random-Walk-Free Deep Neural Architectures for Graph Embedding
model/method
Random-walk-free deep graph embedding methods process full adjacency matrices, neighborhood subgraphs, or spectral representations using end-to-end multi-layer neural architectures.

1. Graph Autoencoders

Autoencoders employ non-linear encoder and decoder networks to minimize the reconstruction error of structural proximity matrices. The encoder maps an adjacency vector $A_i$ or PPMI vector of node $v_i$ to latent representation $y_i$ , while the decoder reconstructs the neighborhood $\hat{A}_i$ . Joint loss functions combine global reconstruction error with first-order Laplacian penalties to constrain connected nodes to have close latent representations.

2. Spectral Graph Convolutional Networks

Spectral approaches generalize Euclidean convolutions to graph domains using the graph Laplacian $L = D - W$ . By the Convolution Theorem, graph spectral convolution of signal $x \in \mathbb{R}^{|V|}$ with filter $g_\theta$ is defined as: $g_\theta \star x = U g_\theta(\Lambda) U^T x$ where $U$ is the matrix of orthonormal eigenvectors of normalized Laplacian $L_{\text{norm}} = I - D^{-1/2} W D^{-1/2} = U \Lambda U^T$ . To avoid expensive $O(|V|^3)$ eigendecompositions, filters are parameterized with truncated Chebyshev polynomials (ChebNet) or localized first-order approximations (GCN): $H^{(l+1)} = \sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)$ where $\tilde{A} = A + I_N$ , $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$ , $H^{(l)}$ is the layer $l$ activation matrix, and $W^{(l)}$ is the trainable weight matrix.

3. Spatial Graph Neural Networks

Spatial architectures perform neighborhood matching and feature aggregation directly in vertex space (e.g., MoNet, GNN, GGS-NNs), recursively propagating hidden states across neighboring nodes without relying on spectral decomposition.

4. Multi-Modal and Heterogeneous Deep Embeddings

Deep architectures accommodate multi-modal features by assigning specialized sub-networks (e.g., CNNs for image nodes, fully connected layers for text nodes) and mapping heterogeneous representations into a shared latent space.
Knowl 7 — Objective Formulations for Edge Reconstruction-Based Graph Embedding
equation
Edge reconstruction methods optimize node embeddings $y_i, y_j \in \mathbb{R}^d$ such that reconstructed edge probabilities closely match observed edge distributions.

1. Maximizing Edge Reconstruction Probability
- First-Order Proximity Likelihood: The joint probability of an undirected edge between $v_i$ and $v_j$ is parameterized by a sigmoid inner product: $p^{(1)}(v_i, v_j) = \frac{1}{1 + \exp(-y_i^T y_j)}$ The objective maximizes the total log-likelihood over all observed edges: $\mathcal{O}^{(1)}_{\max} = \sum_{e_{ij} \in E} \log p^{(1)}(v_i, v_j)$
- Second-Order Proximity Likelihood: The conditional probability of generating directed neighbor $v_j$ from $v_i$ is: $p^{(2)}(v_j \mid v_i) = \frac{\exp(y_j^T y_i)}{\sum_{k=1}^{|V|} \exp(y_k^T y_i)}$ Across a set of sampled end-to-end paths $\mathcal{P}$ : $\mathcal{O}^{(2)}_{\max} = \sum_{(v_i, v_j) \in \mathcal{P}} \log p^{(2)}(v_j \mid v_i)$
2. Minimizing Distance-Based Loss (KL-Divergence)

Instead of raw likelihood, the objective minimizes the KL-divergence between empirical graph probability distributions and model-predicted probabilities:
- First-Order Empirical Distribution: $\hat{p}^{(1)}(v_i, v_j) = \frac{A_{ij}}{\sum_{e \in E} A_e}$ . Minimizing KL-divergence yields: $\mathcal{O}^{(1)}_{\min} = -\sum_{e_{ij} \in E} A_{ij} \log p^{(1)}(v_i, v_j)$
- Second-Order Empirical Distribution: $\hat{p}^{(2)}(v_j \mid v_i) = \frac{A_{ij}}{d_i}$ , where $d_i = \sum_{k} A_{ik}$ is the degree/out-degree of $v_i$ . Minimizing KL-divergence yields: $\mathcal{O}^{(2)}_{\min} = -\sum_{e_{ij} \in E} A_{ij} \log p^{(2)}(v_j \mid v_i)$
Knowl 8 — Margin-Based Ranking Loss and Energy Formulations in Knowledge Graph Embedding
equation
Margin-based ranking objectives enforce that observed relationships or relevant node pairs receive higher similarity scores (or lower energy values) than unobserved or corrupted pairs by a predefined margin $\gamma > 0$ .

1. General Node Ranking Loss

For node $v_i$ with relevant node set $\mathcal{V}_i^+$ and irrelevant node set $\mathcal{V}_i^-$ : $\mathcal{O}_{\text{rank}} = \min \sum_{v_i^+ \in \mathcal{V}_i^+} \sum_{v_i^- \in \mathcal{V}_i^-} \max\left\{0, \gamma - s(v_i, v_i^+) + s(v_i, v_i^-)\right\}$ where $s(u, v)$ computes the similarity score between vector representations of $u$ and $v$ .

2. Knowledge Graph Embedding Triplet Loss

For knowledge graph fact triplets $(h, r, t) \in \mathcal{S}$ and corrupted triplets $(h', r, t') \in \mathcal{S}'$ (where head or tail entity is replaced by a random entity): $\mathcal{O}^{\text{kg}}_{\text{rank}} = \min \sum_{(h,r,t) \in \mathcal{S}} \sum_{(h',r,t') \in \mathcal{S}'} \max\left\{0, \gamma + f_r(h, t) - f_r(h', t')\right\}$ where $f_r(h, t)$ is a relation-specific energy distance function:
- TransE: $f_r(h, t) = \|h + r - t\|_{l_1 / l_2}$
- TransH: $f_r(h, t) = \|(h - w_r^T h w_r) + d_r - (t - w_r^T t w_r)\|_2^2$ , with hyperplane normal vector $w_r$ and relation translation vector $d_r$ .
- TransR: $f_r(h, t) = \|h M_r + r - t M_r\|_2^2$ , with entity-to-relation projection matrix $M_r$ .
- TransD: $f_r(h, t) = \|M_{rh} h + r - M_{rt} t\|_2^2$ , with dynamic mapping matrices $M_{rh} = r_p h_p^T + I$ and $M_{rt} = r_p t_p^T + I$ .
- DistMult / Bilinear: Uses a bilinear scoring function $s_r(h, t) = h^T W_r t$ with diagonal relation matrix $W_r$ .
- ComplEx: Extends embeddings to the complex domain $\mathbb{C}^d$ with score $\text{Re}\left(h^T W_r \bar{t}\right)$ , handling asymmetric relations.
Knowl 9 — Graph Kernel Methods for Whole-Graph Embedding
model/method
Graph kernels implement whole-graph embedding under the $R$ -convolution framework by recursively decomposing a structured graph $G$ into elementary "atomic" substructures and encoding the graph as a normalized frequency vector $y_G \in \mathbb{R}^d$ .

1. Elementary Substructure Decompositions
- Graphlet Kernel: Decomposes $G$ into counts of induced, non-isomorphic subgraphs of size $k$ (graphlets $\{G_1, G_2, \dots, G_d\}$ ). The vector $y_G$ contains the normalized frequencies of occurrence of each graphlet in $G$ .
- Weisfeiler-Lehman (WL) Subtree Kernel: Iteratively relabels nodes in a discrete-labeled graph by hashing multiset collections of neighbor labels. For $h$ relabeling iterations, $y_G$ is formed by concatenating $h$ count blocks, where the $i$ -th entry of block $j$ represents the frequency of label $i$ occurring in iteration $j$ .
- Random Walk and Shortest-Path Kernels: Decomposes $G$ into paths characterized as triplets $(l_i^s, l_i^e, n_i)$ , where $l_i^s$ and $l_i^e$ denote starting and ending vertex labels, and $n_i$ denotes path length. The $i$ -th dimension of $y_G$ records the frequency of triplet $i$ .
2. Methodological Trade-offs
- Advantages: Fast, explicit evaluation of whole-graph similarity vectors without requiring iterative nonlinear gradient descent.
- Limitations: Substructures are non-independent (size- $(k+1)$ graphlets contain size- $k$ graphlets as subgraphs, introducing redundancy). Furthermore, feature vector dimensionality grows exponentially with substructure size $k$ , resulting in high-dimensional sparsity.
Knowl 10 — Generative Models for Graph Embedding
model/method
Generative graph embedding models specify joint probability distributions relating graph structures, auxiliary attributes, and latent variables.

1. Direct Latent Semantic Space Embedding

Direct generative approaches view the observed graph as generated from a latent topic/activity distribution. For instance, in location-based social networks (LBSNs), locations (analogous to documents) contain check-in users (analogous to words) governed by latent activity topics. Each location is parameterized as a multinomial distribution over activities, and each activity has an attractiveness distribution over users. Node representations for users and locations are derived directly as parameter vectors in this shared latent activity space.

2. Incorporating Latent Semantics with Structural Embedding

Two-stage or joint generative frameworks integrate auxiliary text or descriptions with graph topology:
- Topic models (e.g., Latent Dirichlet Allocation) extract document-level semantic topic distributions from node text.
- Mapping functions or joint regularizers enforce that nodes close in topological embedding space share similar probability distributions in the latent topic subspace.
- In multi-relation knowledge graphs, Bayesian non-parametric infinite mixture models discover latent semantic relation sub-components, expressing multi-faceted relation vectors as mixture distributions.
3. Trade-offs

Generative embeddings provide direct semantic interpretability and natural multi-modal fusion. However, their parametric distributional assumptions are difficult to validate on arbitrary networks, and reliable parameter estimation requires large volumes of training data.

Knowl 11 — Comparative Trade-offs Across Graph Embedding Technique Categories

data/table

The five principal families of graph embedding techniques exhibit distinct computational and structural characteristics:

Technique Category	Advantages	Disadvantages
Matrix Factorization	Captures global node proximity statistics across the entire graph.	High space and time complexity for large matrix construction and eigendecomposition.
Deep Learning (with Random Walk)	Flexible and robust; scales linearly with sampled path tokens.	Overlooks global context outside sampled walk windows; sampling strategies are decoupled from optimization.
Deep Learning (without Random Walk)	End-to-end multi-layer non-linear modeling on non-Euclidean graphs.	High computation cost; cannot directly exploit regular 1D/2D grid GPU optimizations without specialized algorithms.
Edge Reconstruction	Highly scalable and efficient training via localized pairwise/triplet objectives.	Uses only localized observed edges or 1-hop ranking triplets; lacks awareness of global topology.
Graph Kernel	Efficient whole-graph vectorization via substructure count enumeration.	Substructures have high mutual dependence and redundancy; vector dimensionality grows exponentially with substructure size.
Generative Model	Inherently interpretable latent spaces; naturally unifies multi-source auxiliary text and topology.	Prior distribution assumptions are difficult to justify; requires massive training datasets to estimate parameters reliably.

This comparison demonstrates the fundamental trade-offs in graph representation learning: global matrix factorization offers exact global spectral properties at the cost of cubic scalability; deep learning provides rich non-linear capacity but introduces sampling or graph-convolution computational burdens; edge reconstruction provides linear scalability at the expense of global graph structure; graph kernels enable efficient whole-graph comparisons but suffer from feature explosion; and generative models provide semantic interpretability while requiring strong statistical assumptions and extensive data.

Knowl 12 — Taxonomical Mapping of Graph Embedding Applications
model/method
Graph embedding enables a wide spectrum of downstream graph analytics tasks categorized across three structural granularities:

1. Node-Related Applications
- Node Classification: Evaluates categorical labels of unobserved nodes by training classifiers (e.g., Support Vector Machines, Logistic Regression) on low-dimensional node vectors $y_i$ , or via joint end-to-end semi-supervised objectives.
- Node Clustering: Groups nodes into unsupervised clusters (e.g., using $k$ -means) based on vector distance in the embedding space.
- Node Recommendation / Proximity Retrieval: Recommends top- $K$ entities based on cosine similarity or inner product scores in the embedded space, including friend recommendation, item suggestion, expert retrieval in cQA, and entity ranking in knowledge graphs.
2. Edge-Related Applications
- Link Prediction: Predicts missing or unobserved edges by scoring candidate node pairs. Evaluated by Area Under the ROC Curve (AUC) against a hold-out test set with negative sampled non-edges.
- Graph Reconstruction: Reconstructs the complete set of original edges from learned node representations across all $|V| \times |V|$ candidate node pairs. Evaluated via Precision@K and Mean Average Precision (MAP).
- Triplet Classification: In knowledge graphs, classifies whether an unseen fact triplet $(h, r, t)$ is valid based on whether relation energy $f_r(h, t)$ falls below a threshold.
3. Graph-Related and Cross-Graph Applications
- Whole-Graph Classification: Assigns categorical labels to entire graphs (e.g., molecules, protein structures) by comparing whole-graph embedding vectors $y_G$ or matching sets of node vectors.
- Graph Visualization: Projects node embeddings into 2D or 3D coordinate space (via t-SNE or PCA) to visually inspect structural clustering and community segregation.
- Social Network Alignment: Maps and aligns user identity representations across disparate social networks to identify cross-platform matching accounts.
Knowl 13 — Open Challenges and Future Research Directions in Graph Embedding
limitation
Four major structural and methodological challenges define future directions for graph embedding research:
1. Computational Efficiency in Deep Architectures: Standard deep learning hardware (GPUs) is optimized for regular 1D sequences and 2D spatial grids. Irregular non-Euclidean graph topologies cannot leverage grid-based memory access and tensor operations directly. Scalable computational paradigms and parallel distributed graph engines must be integrated with deep graph neural network architectures.
2. Dynamic and Time-Varying Graph Embedding: Real-world networks undergo continuous structural mutations (addition/deletion of nodes and edges) and time-varying attribute shifts. Existing algorithms predominantly assume static networks. Dynamic graph embedding requires online, incremental update mechanisms that avoid full re-training while preserving temporal evolution patterns.
3. Structure-Aware Non-Deep Optimization: While deep neural networks capture non-linear path patterns, they incur heavy training costs. Edge reconstruction models are computationally efficient but remain restricted to localized 1-hop edges or single triplets. Developing non-deep, computationally lightweight optimization methods that incorporate high-order motifs, subtrees, and global path constraints remains an open technical challenge.
4. Unified Multi-View and Cross-Modal Representation: Heterogeneous data sources (cross-modal image-text-network graphs, multi-platform alignments) require unified latent spaces that preserve relational structure across disparate modalities and data schemas.

Coverage note — No substantial contributed material from the survey's taxonomies, mathematical formulations, technique comparisons, application landscape, or future research directions was omitted.

References

1.X. Wang, P. Cui, J. Wang, J. Pei, W. Zhu, and S. Yang, “Community preserving network embedding,” in AAAI, 2017, pp. 203–209.
2.F. Nie, W. Zhu, and X. Li, “Unsupervised large graph embedding,” in AAAI, 2017, pp. 2422–2428.
3.C. Zhou, Y. Liu, X. Liu, Z. Liu, and J. Gao, “Scalable graph embedding for asymmetric proximity,” in AAAI, 2017, pp. 2942–2948.
4.X. Wei, L. Xu, B. Cao, and P. S. Yu, “Cross view link prediction by learning noise-resilient representation consensus,” in WWW, 2017, pp. 1611–1619.
5.J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica, “Graphx: Graph processing in a distributed dataflow framework,” in OSDI, 2014, pp. 599–613.
6.Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein, “Distributed graphlab: A framework for machine learning and data mining in the cloud,” Proc. VLDB Endow., vol. 5, no. 8, pp. 716–727, 2012.
7.P. Kumar and H. H. Huang, “G-store: High-performance graph store for trillion-edge processing,” in SC, 2016, pp. 71:1–71:12.
8.N. Satish, N. Sundaram, M. M. A. Patwary, J. Seo, J. Park, M. A. Hassaan, S. Sengupta, Z. Yin, and P. Dubey, “Navigating the maze of graph analytics frameworks using massive graph datasets,” in SIGMOD, 2014, pp. 979–990.
9.Y. Bengio, A. C. Courville, and P. Vincent, “Representation learning: A review and new perspectives,” PAMI, vol. 35, no. 8, pp. 1798–1828, 2013.
10.A. Mahmood, M. Small, S. A. Al-Maadeed, and N. M. Rajpoot, ´ “Using geodesic space density gradients for network community detection,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 4, pp. 921–935, 2017.
11.P. Goyal and E. Ferrara, “Graph embedding techniques, applications, and performance: A survey,” CoRR, vol. abs/1705.02801, 2017.
12.N. S. S and S. Surendran, “Graph embedding and dimensionality reduction-a survey,” IJCSET, vol. 4, no. 1, pp. 29–34, 2013.
13.Z. Wang, J. Zhang, J. Feng, and Z. Chen, “Knowledge graph embedding by translating on hyperplanes,” in AAAI, 2014, pp. 1112–1119.
14.Y. Lin, Z. Liu, M. Sun, Y. Liu, and X. Zhu, “Learning entity and relation embeddings for knowledge graph completion,” in AAAI, 2015, pp. 2181–2187.
15.X. Zhao, A. Chang, A. D. Sarma, H. Zheng, and B. Y. Zhao, “On the embeddability of random walk distances,” PVLDB, vol. 6, no. 14, pp. 1690–1701, 2013.
16.B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in KDD, 2014, pp. 701–710.
17.T. Man, H. Shen, S. Liu, X. Jin, and X. Cheng, “Predict anchor links across social networks via an embedding approach,” in IJCAI, 2016, pp. 1823–1829.
18.T. Pimentel, A. Veloso, and N. Ziviani, “Unsupervised and scalable algorithm for learning node representations,” in ICLR, 2017.
19.D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in KDD, 2016, pp. 1225–1234.
20.S. Cao, W. Lu, and Q. Xu, “Grarep: Learning graph representations with global structural information,” in CIKM, 2015, pp. 891–900.
21.F. Tian, B. Gao, Q. Cui, E. Chen, and T. Liu, “Learning deep representations for graph clustering,” in AAAI, 2014, pp. 1293–1299.
22.S. Cao, W. Lu, and Q. Xu, “Deep neural networks for learning graph representations,” in AAAI, 2016, pp. 1145–1152.
23.A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola, “Distributed large-scale natural graph factorization,” in WWW, 2013, pp. 37–48.
24.Z. Jin, R. Liu, Q. Li, D. D. Zeng, Y. Zhan, and L. Wang, “Predicting user’s multi-interests with network embedding in health-related topics,” in IJCNN, 2016, pp. 2568–2575.
25.L. Liu, W. K. Cheung, X. Li, and L. Liao, “Aligning users across social networks using network embedding,” in IJCAI, 2016, pp. 1774–1780.
26.J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in WWW, 2015, pp. 1067–1077.
27.A. Grover and J. Leskovec, “Node2vec: Scalable feature learning for networks,” in KDD, 2016, pp. 855–864.
28.H. Fang, F. Wu, Z. Zhao, X. Duan, Y. Zhuang, and M. Ester, “Community-based question answering via heterogeneous social network learning,” in AAAI, 2016, pp. 122–128.
29.Z. Zhao, Q. Yang, D. Cai, X. He, and Y. Zhuang, “Expert finding for community-based question answering via ranking metric network learning,” in IJCAI, 2016, pp. 3000–3006.
30.H. Lu and M. Kong, “Community-based question answering via contextual ranking metric network learning,” in AAAI, 2017, pp. 4963–4964.
31.Z. Zhao, H. Lu, V. W. Zheng, D. Cai, X. He, and Y. Zhuang, “Community-based question answering via asymmetric multi-faceted ranking network learning,” in AAAI, 2017, pp. 3532–3539.
32.S. Chang, W. Han, J. Tang, G.-J. Qi, C. C. Aggarwal, and T. S. Huang, “Heterogeneous network embedding via deep architectures,” in KDD, 2015, pp. 119–128.
33.H. Zhang, X. Shang, H. Luan, M. Wang, and T. Chua, “Learning from collective intelligence: Feature learning using social images and tags,” TOMCCAP, vol. 13, no. 1, pp. 1:1–1:23, 2016.
34.X. Geng, H. Zhang, J. Bian, and T. Chua, “Learning image and user features for recommendation in social networks,” in ICCV, 2015, pp. 4274–4282.
35.F. Wu, X. Lu, J. Song, S. Yan, Z. M. Zhang, Y. Rui, and Y. Zhuang, “Learning of multimodal representations with random walks on the click graph,” IEEE Trans. Image Processing, vol. 25, no. 2, pp. 630–642, 2016.
36.K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor, “Freebase: A collaboratively created graph database for structuring human knowledge,” in SIGMOD, 2008, pp. 1247–1250.
37.J. Feng, M. Huang, Y. Yang, and X. Zhu, “GAKE: graph aware knowledge embedding,” in COLING, 2016, pp. 641–651.
38.F. Wu, J. Song, Y. Yang, X. Li, Z. M. Zhang, and Y. Zhuang, “Structured embedding via pairwise relations and long-range interactions in knowledge base,” in AAAI, 2015, pp. 1663–1670.
39.B. Shi and T. Weninger, “Proje: Embedding projection for knowledge graph completion,” in AAAI, 2017, pp. 1236–1242.
40.M. Ochi, Y. Nakashio, Y. Yamashita, I. Sakata, K. Asatani, M. Ruttley, and J. Mori, “Representation learning for geospatial areas using large-scale mobility data from smart card,” in UbiComp, 2016, pp. 1381–1389.
41.M. Ochi, Y. Nakashio, M. Ruttley, J. Mori, and I. Sakata, “Geospatial area embedding based on the movement purpose hypothesis using large-scale mobility data from smart card,” IJCNS, vol. 9, pp. 519–534, 2016.
42.Y. Zhao, Z. Liu, and M. Sun, “Representation learning for measuring entity relatedness with rich information,” in IJCAI, 2015, pp. 1412–1418.
43.C. Zhang, K. Zhang, Q. Yuan, H. Peng, Y. Zheng, T. Hanratty, S. Wang, and J. Han, “Regions, periods, activities: Uncovering urban dynamics via cross-modal representation learning,” in WWW, 2017, pp. 361–370.
44.Z. Liu, V. W. Zheng, Z. Zhao, F. Zhu, K. C. Chang, M. Wu, and J. Ying, “Semantic proximity search on heterogeneous graph by proximity embedding,” in AAAI, 2017, pp. 154–160.
45.H. Gui, J. Liu, F. Tao, M. Jiang, B. Norick, and J. Han, “Large-scale embedding learning in heterogeneous event data,” in ICDM, 2016, pp. 907–912.
46.Y. Dong, N. V. Chawla, and A. Swami, “metapath2vec: Scalable representation learning for heterogeneous networks,” in KDD, 2017, pp. 135–144.
47.J. Li, J. Zhu, and B. Zhang, “Discriminative deep random walk for network classification,” in ACL, 2016.
48.C. Tu, W. Zhang, Z. Liu, and M. Sun, “Max-margin deepwalk: Discriminative learning of network representation,” in IJCAI, 2016, pp. 3889–3895.
49.N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhorn, and K. M. Borgwardt, “Weisfeiler-lehman graph kernels.” Journal of Machine Learning Research, vol. 12, pp. 2539–2561, 2011.
50.G. Nikolentzos, P. Meladianos, and M. Vazirgiannis, “Matching node embeddings for graph similarity,” in AAAI, 2017, pp. 2429–2435.
51.S. Guo, Q. Wang, B. Wang, L. Wang, and L. Guo, “Semantically smooth knowledge graph embedding,” in ACL, 2015, pp. 84–94.
52.——, “SSE: semantically smooth embedding for knowledge graphs,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 4, pp. 884–897, 2017.
53.R. Xie, Z. Liu, and M. Sun, “Representation learning of knowledge graphs with hierarchical types,” in IJCAI, 2016, pp. 2965–2971.
54.H. Dai, B. Dai, and L. Song, “Discriminative embeddings of latent variable models for structured data,” in ICML, 2016, pp. 2702–2711.
55.M. Niepert, M. Ahmed, and K. Kutzkov, “Learning convolutional neural networks for graphs,” in ICML, vol. 48, 2016, pp. 2014–2023.
56.C. Yang, Z. Liu, D. Zhao, M. Sun, and E. Y. Chang, “Network representation learning with rich text information,” in IJCAI, 2015, pp. 2111–2117.
57.D. Zhang, J. Yin, X. Zhu, and C. Zhang, “Homophily, structure, and content augmented network representation learning,” in ICDM, 2016, pp. 609–618.
58.T. M. V. Le and H. W. Lauw, “Probabilistic latent document network embedding,” in ICDM, 2014, pp. 270–279.
59.H. Xiao, M. Huang, L. Meng, and X. Zhu, “SSP: semantic space projection for knowledge graph embedding with text descriptions,” in AAAI, 2017, pp. 3104–3110.
60.L. Yao, Y. Zhang, B. Wei, Z. Jin, R. Zhang, Y. Zhang, and Q. Chen, “Incorporating knowledge graph embeddings into topic modeling,” in AAAI, 2017, pp. 3119–3126.
61.Z. Wang and J. Li, “Text-enhanced representation learning for knowledge graph,” in IJCAI, 2016, pp. 1293–1299.
62.Z. Yang, W. W. Cohen, and R. Salakhutdinov, “Revisiting semi-supervised learning with graph embeddings,” in ICML, 2016, pp. 40–48.
63.C. Li, J. Ma, X. Guo, and Q. Mei, “Deepcas: An end-to-end predictor of information cascades,” in WWW, 2017, pp. 577–586.
64.N. Zhao, H. Zhang, M. Wang, R. Hong, and T. Chua, “Learning content-social influential features for influence analysis,” IJMIR, vol. 5, no. 3, pp. 137–149, 2016.
65.Z. Yang, J. Tang, and W. Cohen, “Multi-modal bayesian embeddings for learning social knowledge graphs,” in IJCAI, 2016, pp. 2287–2293.
66.F. M. Suchanek, G. Kasneci, and G. Weikum, “Yago: a core of semantic knowledge,” in WWW, 2007, pp. 697–706.
67.C. Bizer, J. Lehmann, G. Kobilarov, S. Auer, C. Becker, R. Cyganiak, and S. Hellmann, “Dbpedia - A crystallization point for the web of data,” J. Web Sem., vol. 7, no. 3, pp. 154–165, 2009.
68.C. Xiong, R. Power, and J. Callan, “Explicit semantic ranking for academic search via knowledge graph embedding,” in WWW, 2017, pp. 1271–1279.
69.B. Alharbi and X. Zhang, “Learning from your network of friends: A trajectory representation learning model based on online social ties,” in ICDM, 2016, pp. 781–786.
70.Q. Zhang and H. Wang, “Not all links are created equal: An adaptive embedding approach for social personalized ranking,” in SIGIR, 2016, pp. 917–920.
71.T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in ICLR, 2017.
72.S. Pan, J. Wu, X. Zhu, C. Zhang, and Y. Wang, “Tri-party deep network representation,” in IJCAI, 2016, pp. 1895–1901.
73.T. Hofmann and J. M. Buhmann, “Multidimensional scaling and data clustering,” in NIPS, 1994, pp. 459–466.
74.Y. Han and Y. Shen, “Partially supervised graph embedding for positive unlabelled feature selection,” in IJCAI, 2016, pp. 1548–1554.
75.M. Yin, J. Gao, and Z. Lin, “Laplacian regularized low-rank representation and its applications,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 38, no. 3, pp. 504–517, 2016.
76.M. Tang, F. Nie, and R. Jain, “Capped lp-norm graph embedding for photo clustering,” in MM, 2016, pp. 431–435.
77.M. Balasubramanian and E. L. Schwartz, “The isomap algorithm and topological stability,” Science, vol. 295, no. 5552, pp. 7–7, 2002.
78.F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. ` Bronstein, “Geometric deep learning on graphs and manifolds using mixture model cnns,” in CVPR, 2017.
79.J. Tang, M. Qu, and Q. Mei, “Pte: Predictive text embedding through large-scale heterogeneous text networks,” in KDD, 2015, pp. 1165–1174.
80.X. Ren, W. He, M. Qu, C. R. Voss, H. Ji, and J. Han, “Label noise reduction in entity typing by heterogeneous partial-label embedding,” in KDD, 2016, pp. 1825–1834.
81.S. Yan, D. Xu, B. Zhang, H. Zhang, Q. Yang, and S. Lin, “Graph embedding and extensions: A general framework for dimensionality reduction,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 29, no. 1, pp. 40–51, 2007.
82.C. Gong, D. Tao, J. Yang, and K. Fu, “Signed laplacian embedding for supervised dimension reduction,” in AAAI, 2014, pp. 1847–1853.
83.L. Sun, S. Ji, and J. Ye, “Hypergraph spectral learning for multi-label classification,” in KDD, 2008, pp. 668–676.
84.Y.-Y. Lin, T.-L. Liu, and H.-T. Chen, “Semantic manifold learning for image retrieval,” in MM, 2005, pp. 249–258.
85.A. Bordes, J. Weston, R. Collobert, and Y. Bengio, “Learning structured embeddings of knowledge bases,” in AAAI, 2011.
86.A. Bordes, N. Usunier, A. Garc´ıa-Duran, J. Weston, and ´ O. Yakhnenko, “Translating embeddings for modeling multi-relational data,” in NIPS, 2013, pp. 2787–2795.
87.A. Bordes, X. Glorot, J. Weston, and Y. Bengio, “A semantic matching energy function for learning with multi-relational data - application to word-sense disambiguation,” Machine Learning, vol. 94, no. 2, pp. 233–259, 2014.
88.P. Yanardag and S. Vishwanathan, “Deep graph kernels,” in KDD, 2015, pp. 1365–1374.
89.A. Bordes, S. Chopra, and J. Weston, “Question answering with subgraph embeddings,” in EMNLP, 2014, pp. 615–620.
90.V. W. Zheng, S. Cavallari, H. Cai, K. C. Chang, and E. Cambria, “From node embedding to community embedding,” CoRR, vol. abs/1610.09950, 2016.
91.S. F. Mousavi, M. Safayani, A. Mirzaei, and H. Bahonar, “Hierarchical graph embedding in vector space by graph pyramid,” Pattern Recognition, vol. 61, pp. 245–254, 2017.
92.W. N. A. Jr. and T. D. Morley, “Eigenvalues of the laplacian of a graph,” Linear and Multilinear Algebra, vol. 18, no. 2, pp. 141–145, 1985.
93.X. He and P. Niyogi, “Locality preserving projections,” in NIPS, 2003, pp. 153–160.
94.D. Cai, X. He, and J. Han, “Spectral regression: a unified subspace learning framework for content-based image retrieval,” in MM, 2007, pp. 403–412.
95.K. Q. Weinberger, F. Sha, and L. K. Saul, “Learning a kernel matrix for nonlinear dimensionality reduction,” in ICML, 2004.
96.K. Allab, L. Labiod, and M. Nadif, “A semi-nmf-pca unified framework for data clustering,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 1, pp. 2–16, 2017.
97.M. Chen, I. W. Tsang, M. Tan, and C. T. Jen, “A unified feature selection framework for graph embedding on high dimensional data,” IEEE Trans. Knowl. Data Eng., vol. 27, no. 6, pp. 1465–1477, 2015.
98.S. T. Roweis and L. K. Saul, “Nonlinear Dimensionality Reduction by Locally Linear Embedding,” Science, vol. 290, no. 5500, pp. 2323–2326, 2000.
99.L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Rev., vol. 38, no. 1, pp. 49–95, 1996.
100.B. Shaw and T. Jebara, “Structure preserving embedding,” in ICML, 2009, pp. 937–944.
101.M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu, “Asymmetric transitivity preserving graph embedding,” in KDD, 2016, pp. 1105–1114.
102.B. Shaw and T. Jebara, “Minimum volume embedding,” in AISTATS, 2007, pp. 460–467.
103.M. Nickel, V. Tresp, and H. peter Kriegel, “A three-way model for collective learning on multi-relational data,” in ICML. ACM, 2011, pp. 809–816.
104.J. H. Tianji Pang, Feiping Nie, “Flexible orthogonal neighborhood preserving embedding,” in IJCAI-17, 2017, pp. 2592–2598.
105.G. H. Golub and C. Reinsch, “Singular value decomposition and least squares solutions,” Numer. Math., vol. 14, no. 5, pp. 403–420, 1970.
106.X. Z. C. Z. Daokun Zhang, Jie Yin, “User profile preserving social network embedding,” in IJCAI, 2017, pp. 3378–3384.
107.N. Shervashidze, S. V. N. Vishwanathan, T. Petri, K. Mehlhorn, and K. M. Borgwardt, “Efficient graphlet kernels for large graph comparison,” in AISTATS, 2009, pp. 488–495.
108.T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” CoRR, vol. abs/1301.3781, 2013.
109.T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in NIPS, 2013, pp. 3111–3119.
110.S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Computation, vol. 9, no. 8, pp. 1735–1780, 1997.
111.K. Cho, B. van Merrienboer, D. Bahdanau, and Y. Bengio, “On the properties of neural machine translation: Encoder-decoder approaches,” CoRR, vol. abs/1409.1259, 2014.
112.M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, “Geometric deep learning: going beyond euclidean data,” CoRR, vol. abs/1611.08097, 2016.
113.J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” in ICLR, 2013.
114.M. Henaff, J. Bruna, and Y. LeCun, “Deep convolutional networks on graph-structured data,” CoRR, vol. abs/1506.05163, 2015.
115.M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in NIPS, 2016, pp. 3837–3845.
116.F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Trans. Neural Networks, vol. 20, no. 1, pp. 61–80, 2009.
117.D. Duvenaud, D. Maclaurin, J. Aguilera-Iparraguirre, R. Gomez- ´ Bombarelli, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in NIPS, 2015, pp. 2224–2232.
118.Y. Li, D. Tarlow, M. Brockschmidt, and R. S. Zemel, “Gated graph sequence neural networks,” in ICLR, 2016.
119.R. Khasanova and P. Frossard, “Graph-based isometry invariant representation learning,” in ICML, 2017, pp. 1847–1856.
120.G. Ji, S. He, L. Xu, K. Liu, and J. Zhao, “Knowledge graph embedding via dynamic mapping matrix,” in ACL, 2015, pp. 687–696.
121.G. Ji, K. Liu, S. He, and J. Zhao, “Knowledge graph completion with adaptive sparse transfer matrix,” in AAAI, 2016, pp. 985–991.
122.J. Wen, J. Li, Y. Mao, S. Chen, and R. Zhang, “On the representation and embedding of knowledge bases beyond binary relations,” in IJCAI, 2016, pp. 1300–1307.
123.R. Xie, Z. Liu, J. Jia, H. Luan, and M. Sun, “Representation learning of knowledge graphs with entity descriptions,” in AAAI, 2016, pp. 2659–2665.
124.H. Xiao, M. Huang, and X. Zhu, “From one point to a manifold: Knowledge graph embedding for precise link prediction,” in IJCAI, 2016, pp. 1315–1321.
125.Y. Jia, Y. Wang, H. Lin, X. Jin, and X. Cheng, “Locally adaptive translation for knowledge graph embedding,” in AAAI, 2016, pp. 992–998.
126.R. Socher, D. Chen, C. D. Manning, and A. Y. Ng, “Reasoning with neural tensor networks for knowledge base completion,” in NIPS, 2013, pp. 926–934.
127.M. Nickel, L. Rosasco, and T. Poggio, “Holographic embeddings of knowledge graphs,” in AAAI, 2016, pp. 1955–1961.
128.M. Y. C. Z. Muhao Chen, Yingtao Tian, “Multilingual knowledge graph embeddings for cross-lingual knowledge alignment,” in IJCAI, 2017, pp. 1511–1517.
129.H. Liu, Y. Wu, and Y. Yang, “Analogical inference for multirelational embeddings,” in ICML, 2017, pp. 2168–2178.
130.T. Trouillon, J. Welbl, S. Riedel, E. Gaussier, and G. Bouchard, “Complex embeddings for simple link prediction,” in ICML, 2016, pp. 2071–2080.
131.D. Haussler, “Convolution kernels on discrete structures,” University of California at Santa Cruz, Technical Report UCS-CRL-99-10, 1999.
132.S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borgwardt, “Graph kernels,” Journal of Machine Learning Research, vol. 11, pp. 1201–1242, 2010.
133.K. M. Borgwardt and H. Kriegel, “Shortest-path kernels on graphs,” in ICDM, 2005, pp. 74–81.
134.C. M. Bishop and J. Lasserre, “Generative or Discrimative? Getting the Best of Both Worlds,” in Bayesian Statistics 8, 2007, pp. 3–24.
135.D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent dirichlet allocation,” in NIPS, 2001, pp. 601–608.
136.H. Xiao, M. Huang, and X. Zhu, “Transg : A generative model for knowledge graph embedding,” in ACL, 2016.
137.Y. Luo, Q. Wang, B. Wang, and L. Guo, “Context-dependent knowledge graph embedding,” in EMNLP, 2015, pp. 1656–1661.
138.F. Zhang, N. J. Yuan, D. Lian, X. Xie, and W. Ma, “Collaborative knowledge base embedding for recommender systems,” in KDD, 2016, pp. 353–362.
139.Z. L. C. T. Cheng Yang, Maosong Sun, “Fast network embedding enhancement via high order proximity approximation,” in IJCAI, 2017, pp. 3894–3900.
140.Y. Lin, Z. Liu, and M. Sun, “Knowledge representation learning with entities, attributes and relations,” in IJCAI, 2016, pp. 2866–2872.
141.L. F. Ribeiro, P. H. Saverese, and D. R. Figueiredo, “Struc2vec: Learning node representations from structural identity,” in KDD, 2017, pp. 385–394.
142.J. A. Bullinaria and J. P. Levy, “Extracting semantic representations from word co-occurrence statistics: stop-lists, stemming, and svd,” Behavior Research Methods, vol. 44, no. 3, pp. 890–907, 2012.
143.O. Levy, Y. Goldberg, and I. Dagan, “Improving distributional similarity with lessons learned from word embeddings,” TACL, vol. 3, pp. 211–225, 2015.
144.J. Demmel, I. Dumitriu, and O. Holtz, “Fast linear algebra is stable,” Numerische Mathematik, vol. 108, no. 1, pp. 59–91, 2007.
145.R. C. Wilson, E. R. Hancock, E. Pekalska, and R. P. W. Duin, “Spherical and hyperbolic embeddings of data,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 36, no. 11, pp. 2255–2269, 2014.
146.F. D. Johansson and D. P. Dubhashi, “Learning with similarity functions on graphs using matchings of geometric embeddings,” in KDD, 2015, pp. 467–476.

Citation

MLA

Cai, H., et al. “A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications”. arXiv, 2017, http://arxiv.org/abs/1709.07604v3.

APA

Cai, H., Zheng, V. W., & Chang, K. C.-C. (2017). A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications. arXiv. http://arxiv.org/abs/1709.07604v3

Chicago

Cai, H., V. W. Zheng, and K. C.-C. Chang. 2017. “A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications”. arXiv. http://arxiv.org/abs/1709.07604v3.

Harvard

Cai, H., Zheng, V.W. and Chang, K.C.-C. (2017) “A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1709.07604v3.

Vancouver

1. Cai H, Zheng VW, Chang KC-C (2017) A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications. arXiv

BibTeX

@article{cai2017comprehensive,
  title = {A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications},
  author = {Cai, Hongyun and Zheng, Vincent W. and Chang, Kevin Chen-Chuan},
  year = {2017},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1709.07604v3},
  eprint = {1709.07604}
}

Metadata:arXiv

Access the Paper

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

Open PDF

A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Formal Definition of Graph Embedding and Graph Proximities

Knowl 2 — Taxonomy of Graph Embedding Problem Settings

1. Embedding Input Categories

2. Embedding Output Categories

Knowl 3 — Transductive and Inductive Formulations for Graph Laplacian Eigenmaps

1. Transductive Formulation

2. Inductive Formulation

Knowl 4 — Node Proximity Matrix Factorization Formulation

Knowl 5 — Random-Walk-Based Deep Learning for Graph Embedding

1. SkipGram Objective Formulation

2. Scalable Approximations

3. Walk Sampling and Sequential Embeddings

Knowl 6 — Random-Walk-Free Deep Neural Architectures for Graph Embedding

1. Graph Autoencoders

2. Spectral Graph Convolutional Networks

3. Spatial Graph Neural Networks

4. Multi-Modal and Heterogeneous Deep Embeddings

Knowl 7 — Objective Formulations for Edge Reconstruction-Based Graph Embedding

1. Maximizing Edge Reconstruction Probability

2. Minimizing Distance-Based Loss (KL-Divergence)

Knowl 8 — Margin-Based Ranking Loss and Energy Formulations in Knowledge Graph Embedding

1. General Node Ranking Loss

2. Knowledge Graph Embedding Triplet Loss

Knowl 9 — Graph Kernel Methods for Whole-Graph Embedding

1. Elementary Substructure Decompositions

2. Methodological Trade-offs

Knowl 10 — Generative Models for Graph Embedding

1. Direct Latent Semantic Space Embedding

2. Incorporating Latent Semantics with Structural Embedding

3. Trade-offs

Knowl 11 — Comparative Trade-offs Across Graph Embedding Technique Categories

Knowl 12 — Taxonomical Mapping of Graph Embedding Applications

1. Node-Related Applications

2. Edge-Related Applications

3. Graph-Related and Cross-Graph Applications

Knowl 13 — Open Challenges and Future Research Directions in Graph Embedding

References

Citation

BibTeX

Access the Paper