Source-linked AI summary
A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications
Hongyun Cai, Vincent W. Zheng, Kevin Chen-Chuan Chang
TL;DR
Graph analytics spans many graph types and applications but often has high computation and space costs. This survey formalizes graph embedding, organizes prior work by problem settings and techniques, and reviews applications and future directions. It concludes that graph embedding techniques have broad coverage, while specific approaches retain scalability or representation limitations.
Problem
Graph analytics supports diverse applications, but existing methods often suffer high computation and space costs across varied graph settings.
Method
The survey formally defines graph embedding and synthesizes the literature through taxonomies based on problem settings and embedding techniques.
Results
Deep learning methods cover three input-graph types and all four embedding-output types, while edge reconstruction applies broadly except to constructed graphs and whole-graph embedding.
Takeaways & Limitations
The survey organizes graph embedding applications and proposes four future research directions spanning computational efficiency, problem settings, techniques, and applications.
Takeaways & Limitations
Matrix factorization can be time- and space-consuming because proximity-matrix construction or eigendecomposition limits efficiency and scalability for large graphs.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Graph embedding addresses the computational and spatial costs of graph analytics by mapping graph information into low-dimensional vectors. This survey organizes the field by problem settings and techniques, reviews applications, and identifies future directions.
- Graph analytics supports applications including node classification, node clustering, node recommendation, and link prediction across diverse real-world graphs.
- Most graph analytics methods incur high computation and space costs, motivating efficient alternatives such as graph embedding.
- Graph embedding preserves graph information in low-dimensional vectors representing nodes, edges, substructures, or whole graphs.
- The survey categorizes graph embedding literature by problem settings and techniques, linking different settings to their challenges and solutions.
- It analyzes techniques and applications, categorizes applications as node-, edge-, and graph-related, and suggests four future research directions.
2 PROBLEM FORMALIZATION
This section formalizes graph embedding and the graph concepts used to describe its inputs, preserved properties, and outputs. It defines proximity measures and illustrates embeddings at multiple graph granularities.
- 2.1 Notation and Definition: A graph is represented as G = (V, E), with nodes and edges optionally assigned node and edge types.
- 2.1 Notation and Definition: Homogeneous graphs have one node type and one edge type, whereas heterogeneous graphs contain multiple node types and/or edge types.
- 2.1 Notation and Definition: Knowledge graphs represent entities and relations as typed directed subject-property-object triples, making them heterogeneous graphs.
- 2.1 Notation and Definition: First-order proximity measures direct connection strength through edge weight, while second-order proximity compares the similarity of node neighborhoods.
- 2.1 Notation and Definition: Higher-order proximity extends neighborhood-based similarity recursively and may also use measures such as Katz Index, Rooted PageRank, or Adamic Adar.
- 2.1 Notation and Definition: Graph embedding converts G into d-dimensional space, where d ≪ |V| and graph properties are preserved as much as possible.
- 2.1 Notation and Definition: The output may be one vector for a whole graph or a set of vectors representing nodes, edges, or substructures.
3 PROBLEM SETTINGS OF GRAPH EMBEDDING
This section organizes graph embedding by input and output settings, showing that each setting preserves different information and poses distinct challenges. It covers homogeneous, heterogeneous, auxiliary-information, and task-driven output scenarios.
- Overview: Graph embedding settings consist of an input graph and an output representation, with different input types requiring different information to be preserved.The survey divides inputs into homogeneous, heterogeneous, auxiliary-information, and constructed graphs, and outputs into node, edge, hybrid, and whole-graph embeddings.
- Homogeneous Graph: Homogeneous graph embedding must preserve diverse connectivity patterns when only structural information is available.Weights and directions provide additional structural information; for example, higher edge weight or bidirectional connectivity can imply greater embedding proximity.
- Heterogeneous Graph: Heterogeneous graph embedding must model global consistency across object types while accounting for imbalances between those types.Different node and edge types may be embedded into a common space, creating consistency and data-skewness challenges.
- Graph with Auxiliary Information: Auxiliary information extends graph structure with labels, attributes, node features, propagation data, or knowledge-related information.Labels can guide separation, attributes may be discrete or continuous, and node features can include text or images.
- Graph Embedding Output: Embedding outputs are task driven: node, edge, hybrid, and whole-graph vectors support analyses at corresponding granularities.Node embeddings support node clustering and classification, while edge embeddings can support relation, missing-link, or interaction prediction.
4 GRAPH EMBEDDING TECHNIQUES
This section categorizes graph embedding methods by the graph properties they seek to preserve and the insights used to define similarity. It then explains how those properties are quantified and optimized in the embedded space.
- Technique Taxonomy: Graph embedding techniques represent graphs in low-dimensional spaces while preserving as much graph property information as possible.The preserved property may concern nodes, edges, substructures, or whole graphs.
- Technique Taxonomy: The technique taxonomy explains both the insight behind each embedding method and the procedure used to solve its embedding problem.This links the chosen graph property to the corresponding optimization or embedding formulation.
- Technique Taxonomy: Different algorithms differ in their notions of similarity and in how they preserve those similarities in the embedded representation.The survey abstracts the insight behind each technique and describes how its target graph property is quantified.
4.1 Matrix Factorization
Matrix factorization embeds graph properties such as node similarity or proximity by factorizing a matrix or solving a graph-Laplacian eigenproblem. These methods preserve structural, geometric, or auxiliary information while supporting transductive and inductive settings.
- Matrix factorization overview: Matrix factorization represents graph properties as matrices and factorizes them to obtain low-dimensional node embeddings.Typical inputs include graphs constructed from non-relational high-dimensional features, while homogeneous graphs are also supported.
- Graph Laplacian eigenmaps: Graph Laplacian eigenmaps minimize weighted distances between embeddings of similar nodes under a normalization constraint.The weights W encode pairwise similarity, L = D − W is the graph Laplacian, and yT Dy = 1 removes arbitrary scaling.
- Graph Laplacian eigenmaps: The optimal embeddings are eigenvectors associated with the maximum eigenvalues of Wy = λDy.For the inductive formulation, the corresponding generalized eigenproblem uses XWXT a = λXDXT a.
- Graph Laplacian eigenmaps: Existing Laplacian-eigenmap studies differ mainly in how they calculate pairwise similarity W and whether they use a linear embedding function.Variants construct Euclidean or KNN similarities, learn W with semidefinite programming, or incorporate labels and attributes.
- Node proximity matrix factorization: Node-proximity factorization seeks a rank-d approximation of W, commonly using SVD and the largest d singular values with corresponding singular vectors.The resulting representation may use node embeddings alone or concatenate node and context embeddings when preserving asymmetry.
- Node proximity matrix factorization: Matrix-factorization methods also include regularized Gaussian and low-rank variants that add constraints or regularizers to the factorization objective.These approaches are summarized as a separate family of node-proximity matrix factorization methods.
4.2 Deep Learning
Deep learning graph embedding applies neural models either to random-walk paths or directly to whole graphs and proximity matrices. Across these approaches, the survey observes broad coverage of graph inputs and embedding outputs, with efficiency approximations addressing expensive softmax normalization.
- Deep learning overview: Deep learning graph embedding uses either sampled graph paths or whole graphs as input.The survey divides deep-learning methods according to whether random-walk paths are used.
- Random-walk graph embedding: DeepWalk samples truncated random walks, treats nodes as words in sentences, and applies SkipGram to preserve path-carried graph properties.SkipGram maximizes co-occurrence probabilities within a context window of size w.
- Random-walk graph embedding: The full softmax probability is expensive because its normalization sums inner products over every node in the graph.Hierarchical softmax and negative sampling are used to approximate the full softmax.
- Random-walk graph embedding: Hierarchical softmax reduces SkipGram time complexity from O(|V |2) to O(|V |log(|V |)) by evaluating only a root-to-leaf path.A binary tree assigns nodes to leaves, replacing enumeration of all nodes with path evaluation.
- Random-walk graph embedding: Negative sampling distinguishes target neighbors from noise using logistic regression and has time complexity O(K|V |).K is the number of sampled negative nodes, drawn from a noise distribution Pn(vi).
- Random-walk graph embedding: Path-based studies extend DeepWalk by changing random-walk sampling, preserved proximity, or sequence models such as LSTM and GRU.Some methods use meta-path-based walks or ranking losses for node-sequence embedding.
- Whole-graph graph embedding: Whole-graph methods apply autoencoders, CNNs, and other neural architectures directly to graphs or their proximity matrices.Autoencoders reconstruct inputs through nonlinear encoder-decoder mappings, while CNN-based methods either reformat graphs or generalize models to non-Euclidean domains.
- Summary: Deep learning methods cover three input-graph types and all four embedding-output types identified by the survey.The survey attributes their wide use to robustness and effectiveness.
4.3 Edge Reconstruction based Optimization
Edge reconstruction optimization learns graph embeddings by making embedded-node relationships reproduce observed edges or node proximities. Its variants use probability maximization, proximity-distance minimization, or margin-based ranking, and are applicable to most graph settings except non-relational and whole-graph embeddings.
- Overview: Edge reconstruction objectives seek embeddings that re-establish observed graph edges or preserve observed node proximity.Methods either maximize edge-generation probability or minimize reconstruction losses.
- Maximizing Edge Reconstruction Probability: Probability-based methods maximize the likelihood of observed first-order or second-order proximities.First-order proximity concerns directly connected nodes, while second-order proximity models conditional generation or random-walk relationships.
- Minimizing Distance-based Loss: Distance-based methods minimize discrepancies between embedding-derived and empirically observed node proximities.First-order empirical proximity uses normalized edge weights, while second-order proximity uses transition probabilities based on node degree.
- Minimizing Margin-based Ranking Loss: Margin-based ranking loss places each node closer to relevant nodes than to irrelevant nodes.The margin γ controls the enforced separation between positive and negative similarity scores.
- Knowledge Graph Embedding: Knowledge graph methods rank true relational triplets above false triplets using relation-specific energy or matching functions.One example represents relations as translations, with score ∥h + r − t∥_l1; methods differ in their choice of fr(h,t).
- Summary: Edge reconstruction applies to most graph embedding settings, but the survey reports no use for manually constructed non-relational edges or whole-graph embedding.The survey attributes this boundary to the weak intuition of reconstructing manually defined edges and the focus on directly observed local edges.
4.4 Graph Kernel
Graph kernels embed whole graphs as vectors of counts for decomposed elementary substructures, enabling graph comparison through vector inner products. Different kernels use graphlets, subtree patterns, or random walks and paths to capture global graph properties.
- Core Representation: Graph kernels represent each graph as a vector of counts of elementary substructures.Two graphs are compared using the inner product of their representation vectors.
- Graphlet: Graphlets are induced, non-isomorphic subgraphs whose normalized occurrence counts form the embedding dimensions.The i-th coordinate records the frequency of graphlet Gi in the graph.
- Subtree Patterns: Weisfeiler-Lehman kernels iteratively relabel nodes using their labels and neighboring labels to encode subtree patterns.Each generated multiset label is compressed and reused in the next iteration.
- Random Walks: Random-walk and path kernels represent graphs by frequencies of observed walks or paths.For shortest paths, dimensions correspond to triplets containing endpoint labels and path length.
- Summary: Graph kernels are designed for whole-graph embedding because they capture global properties of complete graphs.The survey describes their typical inputs as homogeneous graphs or graphs with auxiliary information.
4.5 Generative Model
Generative-model graph embedding treats graph structure and, in some methods, node semantics as generated by latent variables. The resulting embeddings either occupy the latent semantic space directly or use latent semantics to integrate auxiliary information into another embedding space.
- Overview: Generative models define joint distributions over input features and class labels conditioned on model parameters.LDA exemplifies this approach by modeling documents as topic distributions and topics as word distributions.
- Direct Latent Embedding: Some methods directly embed nodes as latent-variable vectors in a space whose structure explains the observed graph.An LDA-like model, for example, embeds locations in a latent space for a location-based social network.
- Semantic Integration: Other methods use generative latent semantics from node descriptions alongside graph structure to determine embeddings.A unified framework jointly performs topic modeling and graph embedding, restricting triplet representations to a semantic subspace.
- Comparison: The two directions differ in whether the embedding space itself is the latent space or latent space merely integrates multiple information sources.In the latter case, latent semantics help embed the graph into another space.
- Summary: Generative models support both node and edge embedding, with inputs commonly including heterogeneous graphs or graphs with auxiliary information.Their use of node semantics motivates these input settings.
4.6 Hybrid Techniques and Others
Hybrid techniques combine multiple embedding objectives or techniques to preserve different information sources. Other approaches embed graphs using distances to prototypes or landmarks, extending graph embedding beyond the main technique categories.
- Hybrid Techniques: Some studies jointly optimize complementary objectives, such as edge-based ranking with attribute-based matrix factorization.Other combinations add matrix-factorization regularization or combine sentence embedding with friendship-relation ranking.
- Other Approaches: Graph embedding can also use distances to prototype graphs or shortest-path distances to landmark nodes.Landmark-based methods embed additional nodes by matching distances to selected landmarks with real shortest paths.
4.7 Summary
The survey compares five graph embedding technique categories by their advantages and disadvantages. Their trade-offs involve global versus local structure, efficiency and scalability, representation flexibility, and data requirements.
- Matrix factorization captures global pairwise similarities but can be inefficient and unscalable for large graphs.Its proximity-matrix construction or eigendecomposition is time- and space-consuming.
- Deep learning automatically identifies representations from complex graph structures and can exploit neighborhood structure through sampled paths.The survey distinguishes deep learning with and without random walks for modeling graph structures.
- Edge reconstruction is more efficient but may lack awareness of global graph structure because it trains on directly observed local information.Its objectives use observed edges or ranking triplets.
- Graph kernel methods efficiently produce one graph vector for graph-level analytics, but bag-of-structure representations contain redundancy and can become exponentially dimensional and sparse.These limitations arise because substructures are not independent and larger substructures expand the embedding dimension.
- Generative models unify graph structure and node attributes in a latent semantic space, but distributional assumptions and training-data needs limit their suitability for small graph collections.The survey notes that fitting a proper model may require substantial training data.
5 APPLICATIONS
Graph embedding supports node-, edge-, and graph-related analytics by converting graph elements or whole graphs into vectors that can be processed efficiently. Applications include classification, clustering, recommendation, link and entity prediction, graph comparison, visualization, and domain-specific tasks.
- Node-related applications: Node embeddings support classification, clustering, and top-K recommendation by applying classifiers or traditional clustering methods to vector representations.Recommendation targets include research interests, items, images, friends, and documents.
- Edge-related applications: Knowledge graph embeddings enable entity ranking and triplet classification by scoring missing entities or determining whether a relation triplet is correct.These tasks operate on triplets of the form <h, r, t>.
- Edge-related applications: Graph embeddings help infer missing links by preserving network proximity and structural similarity, including semantically typed links in heterogeneous graphs.Examples include predicting friendship relations and schoolmate links.
- Graph-related applications: Whole-graph and node-level embeddings support graph classification and graph-level similarity, while two-dimensional node embeddings support colored graph visualization.Graph-level examples include chemical compounds, organic molecules, and protein structures.
- Specific application scenarios: Domain-specific applications span knowledge graphs, multimedia networks, information propagation, social-network alignment, and image analysis.Examples include extracting relational facts, recovering missing multimedia-triplet components, predicting cascade growth, matching accounts, and image classification or segmentation.
6 FUTURE DIRECTIONS
The survey identifies future work in computation efficiency, dynamic problem settings, structure-aware techniques, and cross-source applications. It emphasizes scalable methods for graph inputs, evolving graphs, richer structural information, and common spaces across modalities or platforms.
- Computation: Graph embedding architectures need alternative efficiency solutions because graph inputs lack the grid structure exploited by conventional GPU-optimized deep learning.Large-scale graph-processing computational paradigms are suggested as one possible direction.
- Problem settings: Dynamic graphs remain a promising setting because real-world graph structures and node or edge information can evolve over time.Evolution may add or remove nodes and edges or change their associated information.
- Techniques: Edge reconstruction methods should incorporate richer structures than individual edges, including paths, trees, and subgraph patterns.The survey contrasts local first- and second-order proximity with long-range interactions and reports subgraph-augmented paths outperforming simple paths for semantic search.
- Applications: Graph embedding can place data from different sources, platforms, or views into a common space for direct comparison and cross-modal retrieval.Examples include content-based image retrieval and keyword-based image or video search.
7 CONCLUSIONS
The survey reviews graph embedding through taxonomies of problem settings and techniques, then summarizes applications and proposes four future research directions. It organizes the field around the challenges posed by different inputs and the ways techniques address them.
- The survey defines graph embedding, introduces four input and four output types, and summarizes challenges for each problem setting.It also categorizes techniques by their advantages and disadvantages.
- It reviews embedding techniques by explaining the insights behind them rather than only listing prior solutions.The resulting analysis is intended to guide future research.
- The survey covers graph embedding applications and proposes future directions in computation efficiency, problem settings, techniques, and application scenarios.