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 https://github.com/palash1992/GEM), which provides all presented algorithms within a unified interface to foster and facilitate research on the topic.

Submitted to Knowledge Based Systems for review

References in corpus (17)

• Finding and evaluating community structure in networks
• DeepWalk: Online Learning of Social Representations
• Cooperative Game Theory Approaches for Network Partitioning
• LINE: Large-scale Information Network Embedding
• Link Prediction in Complex Networks: A Survey
• Spectral Networks and Locally Connected Networks on Graphs
• Hierarchical structure and the prediction of missing links in networks
• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
• Proceedings of the 29th International Conference on Machine Learning (ICML-12)
• Deep Convolutional Networks on Graph-Structured Data
• Convolutional Networks on Graphs for Learning Molecular Fingerprints
• Learning Convolutional Neural Networks for Graphs
• Graph Evolution: Densification and Shrinking Diameters
• DynGEM: Deep Embedding Method for Dynamic Graphs
• Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
• Deep Coevolutionary Network: Embedding User and Item Features for Recommendation
• Multi-Modal Bayesian Embeddings for Learning Social Knowledge Graphs

Cited by in corpus (293)

• A Comprehensive Survey on Graph Neural Networks
• Graph Neural Networks: A Review of Methods and Applications
• Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks
• Simplicial Closure and higher-order link prediction
• graph2vec: Learning Distributed Representations of Graphs
• dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
• Graph Learning: A Survey
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
• Learning Graph Embedding with Adversarial Training Methods
• A Comprehensive Survey on Deep Graph Representation Learning
• Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey
• DynGEM: Deep Embedding Method for Dynamic Graphs
• An Overview of Deep Semi-Supervised Learning
• Graph Representation Learning: A Survey
• Metrics for Graph Comparison: A Practitioner's Guide
• 20 years of network community detection
• Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks
• Node Embedding over Temporal Graphs
• IntentGC: a Scalable Graph Convolution Framework Fusing Heterogeneous Information for Recommendation
• Knowledge Graphs in Manufacturing and Production: A Systematic Literature Review
• TTAGN: Temporal Transaction Aggregation Graph Network for Ethereum Phishing Scams Detection
• Neural Entity Linking: A Survey of Models Based on Deep Learning
• Progresses and Challenges in Link Prediction
• Graph Convolutional Networks for Graphs Containing Missing Features
• Social Media Polarization and Echo Chambers in the Context of COVID-19: Case Study
• A survey on the development status and application prospects of knowledge graph in smart grids
• Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• Representation Learning for Natural Language Processing
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• SpiderCNN: Deep Learning on Point Sets with Parameterized Convolutional Filters
• Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets
• Measuring and Improving the Use of Graph Information in Graph Neural Networks
• Learning Role-based Graph Embeddings
• Automated Machine Learning on Graphs: A Survey
• Adversarially Regularized Graph Autoencoder for Graph Embedding
• Principled approach to the selection of the embedding dimension of networks
• MODEL: Motif-based Deep Feature Learning for Link Prediction
• GEMSEC: Graph Embedding with Self Clustering
• What are the attackers doing now? Automating cyber threat intelligence extraction from text on pace with the changing threat landscape: A survey
• Trans4E: Link Prediction on Scholarly Knowledge Graphs
• A Survey of Adversarial Learning on Graphs
• Random Graph Modeling: A survey of the concepts
• Context-Aware Embeddings for Automatic Art Analysis
• Deep Graph Matching Consensus
• A Comparative Study for Unsupervised Network Representation Learning
• MultiVERSE: a multiplex and multiplex-heterogeneous network embedding approach
• CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding
• Community detection in networks using graph embeddings
• GloDyNE: Global Topology Preserving Dynamic Network Embedding
• Pairing Conceptual Modeling with Machine Learning
• A Broader Picture of Random-walk Based Graph Embedding
• Network Representation Learning: A Survey
• Causality-based CTR Prediction using Graph Neural Networks
• Hyperbolic Entailment Cones for Learning Hierarchical Embeddings
• TwHIN: Embedding the Twitter Heterogeneous Information Network for Personalized Recommendation
• Subgraph Neural Networks
• Review on Learning and Extracting Graph Features for Link Prediction
• Recommender systems based on graph embedding techniques: A comprehensive review
• Deep Neural Networks for Optimal Team Composition
• GLEE: Geometric Laplacian Eigenmap Embedding
• Zero-shot Node Classification with Decomposed Graph Prototype Network
• Small worlds and clustering in spatial networks
• Quantum Feature Maps for Graph Machine Learning on a Neutral Atom Quantum Processor
• Unbiased Graph Embedding with Biased Graph Observations
• Predicting Attributes of Nodes Using Network Structure
• Detecting the ultra low dimensionality of real networks
• DGL-KE: Training Knowledge Graph Embeddings at Scale
• BERTERS: Multimodal Representation Learning for Expert Recommendation System with Transformer
• Human Values and Attitudes towards Vaccination in Social Media
• Multivariate Relations Aggregation Learning in Social Networks
• Approximating Network Centrality Measures Using Node Embedding and Machine Learning
• Nine Quick Tips for Analyzing Network Data
• Graph Mining for Cybersecurity: A Survey
• Heterogeneous Network Representation Learning: A Unified Framework with Survey and Benchmark
• Finding Patient Zero: Learning Contagion Source with Graph Neural Networks
• Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge
• Network Structure Inference, A Survey: Motivations, Methods, and Applications
• POLE: Polarized Embedding for Signed Networks
• Capturing Edge Attributes via Network Embedding
• Network representation learning systematic review: ancestors and current development state
• A Survey on Dynamic Network Embedding
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
• Layered Graph Embedding for Entity Recommendation using Wikipedia in the Yahoo! Knowledge Graph
• Network Embedding: An Overview
• Zero-Shot Multi-View Indoor Localization via Graph Location Networks
• On the Use of ArXiv as a Dataset
• Hyperbolic Disk Embeddings for Directed Acyclic Graphs
• Learning Household Task Knowledge from WikiHow Descriptions
• Transition Propagation Graph Neural Networks for Temporal Networks
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation
• Finding shortest and nearly shortest path nodes in large substantially incomplete networks
• RMove: Recommending Move Method Refactoring Opportunities using Structural and Semantic Representations of Code
• Simplex2Vec embeddings for community detection in simplicial complexes
• HONEM: Learning Embedding for Higher Order Networks
• Learning Dynamic Embeddings from Temporal Interactions
• Automatic selection of clustering algorithms using supervised graph embedding
• Graph embeddings for Abusive Language Detection
• ExEm: Expert Embedding using dominating set theory with deep learning approaches
• Analysis of node2vec random walks on networks
• Data Correction and Evolution Analysis of the ProgrammableWeb Service Ecosystem
• TitAnt: Online Real-time Transaction Fraud Detection in Ant Financial
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• The Effects of Randomness on the Stability of Node Embeddings
• Large-Scale Network Embedding in Apache Spark
• DynamicGEM: A Library for Dynamic Graph Embedding Methods
• Using Neural Networks for Relation Extraction from Biomedical Literature
• SWAG: Item Recommendations using Convolutions on Weighted Graphs
• Hyperbolic Node Embedding for Signed Networks
• AliGraph: A Comprehensive Graph Neural Network Platform
• Walk-Steered Convolution for Graph Classification
• FairEGM: Fair Link Prediction and Recommendation via Emulated Graph Modification
• GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding
• Graph-Based Machine Learning Improves Just-in-Time Defect Prediction
• User Identity Linkage on Social Networks: A Review of Modern Techniques and Applications
• Deep Graph Similarity Learning: A Survey
• The Homophily Principle in Social Network Analysis
• Embedding and trajectories of temporal networks
• Effective and Efficient PageRank-based Positioning for Graph Visualization
• Adversarially Regularized Graph Attention Networks for Inductive Learning on Partially Labeled Graphs
• Benchmarks for Graph Embedding Evaluation
• Heterogeneous Graph Attention Network
• Marius: Learning Massive Graph Embeddings on a Single Machine
• GOSH: Embedding Big Graphs on Small Hardware
• Integrating Contextual Knowledge to Visual Features for Fine Art Classification
• NASGEM: Neural Architecture Search via Graph Embedding Method
• Model-based inexact graph matching on top of CNNs for semantic scene understanding
• Complex systems: features, similarity and connectivity
• ActiveHNE: Active Heterogeneous Network Embedding
• Rubik: A Hierarchical Architecture for Efficient Graph Learning
• Network Representation Learning: Consolidation and Renewed Bearing
• Consensus Clustering: An Embedding Perspective, Extension and Beyond
• FOBE and HOBE: First- and High-Order Bipartite Embeddings
• Simulation and Augmentation of Social Networks for Building Deep Learning Models
• Zoo Guide to Network Embedding
• Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
• Threat Detection and Investigation with System-level Provenance Graphs: A Survey
• Learning Ideological Embeddings from Information Cascades
• Reconstruction of multiplex networks via graph embeddings
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• motif2vec: Motif Aware Node Representation Learning for Heterogeneous Networks
• Hippocluster: an efficient, hippocampus-inspired algorithm for graph clustering
• Identifying Influential Brokers on Social Media from Social Network Structure
• Network Analytics for Anti-Money Laundering -- A Systematic Literature Review and Experimental Evaluation
• DyANE: Dynamics-aware node embedding for temporal networks
• Learning Topological Representation for Networks via Hierarchical Sampling
• Neural IR Meets Graph Embedding: A Ranking Model for Product Search
• An embedding-based distance for temporal graphs
• Network Embedding via Deep Prediction Model
• Privacy Attacks on Network Embeddings
• Random graphs and real networks with weak geometric coupling
• Benchmarking neural embeddings for link prediction in knowledge graphs under semantic and structural changes
• Attributed Network Embedding for Incomplete Attributed Networks
• Hebbian Graph Embeddings
• Word Embeddings for Entity-annotated Texts
• k-simplex2vec: a simplicial extension of node2vec
• Assessing Network Representations for Identifying Interdisciplinarity
• Towards a Flexible Embedding Learning Framework
• Exploring the Representational Power of Graph Autoencoder
• QUINT: Node embedding using network hashing
• Modeling Graphs with Vertex Replacement Grammars
• Deep Hypergraph U-Net for Brain Graph Embedding and Classification
• Model-free hidden geometry of complex networks
• Graph Convolutional Network-based Suspicious Communication Pair Estimation for Industrial Control Systems
• Deep Attention-guided Graph Clustering with Dual Self-supervision
• Off-Policy Evaluation of Probabilistic Identity Data in Lookalike Modeling
• On the Interpretability and Evaluation of Graph Representation Learning
• dynnode2vec: Scalable Dynamic Network Embedding
• DNN-based Speaker Embedding Using Subjective Inter-speaker Similarity for Multi-speaker Modeling in Speech Synthesis
• Latent Network Summarization: Bridging Network Embedding and Summarization
• Towards Interpretable Graph Modeling with Vertex Replacement Grammars
• Adversarial Attack on Network Embeddings via Supervised Network Poisoning
• InfDetect: a Large Scale Graph-based Fraud Detection System for E-Commerce Insurance
• Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey
• Flexible Attributed Network Embedding
• Initialization for Network Embedding: A Graph Partition Approach
• Heterogeneous network approach to predict individuals' mental health
• LaSER: Language-Specific Event Recommendation
• Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel $k$-means, and Heat Kernel
• Hypergraph Dissimilarity Measures
• Unsupervised Network Embedding for Graph Visualization, Clustering and Classification
• LNEMLC: Label Network Embeddings for Multi-Label Classification
• Time-Series Snapshot Network for Partner Recommendation: A Case Study on OSS
• Hyperbolic embedding of brain networks detects regions disrupted by neurodegeneration in Alzheimer's disease
• Permutohedral-GCN: Graph Convolutional Networks with Global Attention
• Preserving Local and Global Information for Network Embedding
• Adversarial Privacy Preserving Graph Embedding against Inference Attack
• Everything About You: A Multimodal Approach towards Friendship Inference in Online Social Networks
• ReLaText: Exploiting Visual Relationships for Arbitrary-Shaped Scene Text Detection with Graph Convolutional Networks
• EmbeddingTree: Hierarchical Exploration of Entity Features in Embedding
• Data-driven Smart Ponzi Scheme Detection
• Graph Embedding for Citation Recommendation
• Graph Embedding Based Hybrid Social Recommendation System
• Fast Sequence-Based Embedding with Diffusion Graphs
• Supervised Domain Adaptation using Graph Embedding
• Learning distributed representations of graphs with Geo2DR
• PINE: Universal Deep Embedding for Graph Nodes via Partial Permutation Invariant Set Functions
• Graph Neural Networks Including Sparse Interpretability
• Friendship is All we Need: A Multi-graph Embedding Approach for Modeling Customer Behavior
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks
• Merchant Category Identification Using Credit Card Transactions
• Adversarial Attack on Large Scale Graph
• Sampled in Pairs and Driven by Text: A New Graph Embedding Framework
• The Atlas for the Aspiring Network Scientist
• Dynamic Link Prediction Using Graph Representation Learning with Enhanced Structure and Temporal Information
• Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification
• SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements
• Predicting Feynman periods in ${\varphi }^4$-theory
• RETRO: Relation Retrofitting For In-Database Machine Learning on Textual Data
• Matrix Completion via Factorizing Polynomials
• Graph Embedding for Mapping Interdisciplinary Research Networks
• Empirical effect of graph embeddings on fraud detection/ risk mitigation
• Efficient Learning-based Graph Simulation for Temporal Graphs
• Citation importance-aware document representation learning for large-scale science mapping
• Language comparison via network topology
• Systematic comparison of graph embedding methods in practical tasks
• Local2Global: Scaling global representation learning on graphs via local training
• Generalized Modularity Embedding: a General Framework for Network Embedding
• Span-core Decomposition for Temporal Networks: Algorithms and Applications
• Investigating Robustness and Interpretability of Link Prediction via Adversarial Modifications
• Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering
• TEGDetector: A Phishing Detector that Knows Evolving Transaction Behaviors
• Neural Embeddings of Scholarly Periodicals Reveal Complex Disciplinary Organizations
• An Efficient Hybridization of Graph Representation Learning and Metaheuristics for the Constrained Incremental Graph Drawing Problem
• Symmetry-driven embedding of networks in hyperbolic space
• Bounded Projection Matrix Approximation with Applications to Community Detection
• ECHO: Encoding Communities via High-order Operators
• Effective Graph and Rank-based Contextual Embeddings for Textual and Multimedia Data
• Scalable Graph Embedding LearningOn A Single GPU
• Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling
• Robust Dynamic Network Embedding via Ensembles
• GAIN: Graph Attention & Interaction Network for Inductive Semi-Supervised Learning over Large-scale Graphs
• Laplacian Eigenmaps with variational circuits: a quantum embedding of graph data
• Dynamic Relational Inference in Multi-Agent Trajectories
• Knowledge Graphs Evolution and Preservation -- A Technical Report from ISWS 2019
• Embedding Symbolic Temporal Knowledge into Deep Sequential Models
• Representing Multi-Robot Structure through Multimodal Graph Embedding for the Selection of Robot Teams
• A Process for the Evaluation of Node Embedding Methods in the Context of Node Classification
• Single-Layer Graph Convolutional Networks For Recommendation
• Bot-Match: Social Bot Detection with Recursive Nearest Neighbors Search
• DINE: A Framework for Deep Incomplete Network Embedding
• Ensemble Node Embeddings using Tensor Decomposition: A Case-Study on DeepWalk
• About Graph Degeneracy, Representation Learning and Scalability
• Inductive Graph Embeddings through Locality Encodings
• Learning Robust Representations with Graph Denoising Policy Network
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees
• RECS: Robust Graph Embedding Using Connection Subgraphs
• Computational Human Dynamics
• Conversation-Based Multimodal Abuse Detection Through Text and Graph Embeddings
• Decoupling feature propagation from the design of graph auto-encoders
• Network Classifiers With Output Smoothing
• Compositional Network Embedding
• RUM: network Representation learning throUgh Multi-level structural information preservation
• RWNE: A Scalable Random-Walk-Based Network Embedding Framework with Personalized Higher-Order Proximity Preserved
• Customized Graph Embedding: Tailoring Embedding Vectors to different Applications
• Using Network Embeddings for Improving Network Alignment
• MANELA: A Multi-Agent Algorithm for Learning Network Embeddings
• Can x2vec Save Lives? Integrating Graph and Language Embeddings for Automatic Mental Health Classification
• DSSLP: A Distributed Framework for Semi-supervised Link Prediction
• Latent geometry emerging from network-driven processes
• Topology-Aware Hashing for Effective Control Flow Graph Similarity Analysis
• Bidirectional group random walk based network embedding for asymmetric proximity
• Your most telling friends: Propagating latent ideological features on Twitter using neighborhood coherence
• Network Representation Learning: From Traditional Feature Learning to Deep Learning
• A Literature Review of Recent Graph Embedding Techniques for Biomedical Data
• Temporal Graph Offset Reconstruction: Towards Temporally Robust Graph Representation Learning
• Toward Edge-Centric Network Embeddings
• Overlapping Spaces for Compact Graph Representations
• Learning Embeddings of Directed Networks with Text-Associated Nodes---with Applications in Software Package Dependency Networks
• Simplex Initialization: A Survey of Techniques and Trends
• Multi-Relation Aware Temporal Interaction Network Embedding
• A Survey on Role-Oriented Network Embedding
• Unsupervised Domain-adaptive Hash for Networks
• Visualising Argumentation Graphs with Graph Embeddings and t-SNE
• Hyperbolic embedding of multilayer networks
• Interpretable Network Representation Learning with Principal Component Analysis
• Topologically Regularized Data Embeddings
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling
• Analysis of 5G academic Network based on graph representation learning method
• Transformation of Node to Knowledge Graph Embeddings for Faster Link Prediction in Social Networks
• Spring-Electrical Models For Link Prediction
• A Method to Predict Semantic Relations on Artificial Intelligence Papers
• Graph Embedding Augmented Skill Rating System
• Scalable Graph Attention-based Instance Selection via Mini-Batch Sampling and Hierarchical Hashing
• Dynamic Joint Variational Graph Autoencoders
• Towards conceptual generalization in the embedding space
• A Structural Feature-Based Approach for Comprehensive Graph Classification
• Spread-gram: A spreading-activation schema of network structural learning
• Fast Haar Transforms for Graph Neural Networks