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 (8)

• Cooperative Game Theory Approaches for Network Partitioning
• LINE: Large-scale Information Network Embedding
• Hierarchical structure and the prediction of missing links in networks
• Proceedings of the 29th International Conference on Machine Learning (ICML-12)
• Deep Convolutional Networks on Graph-Structured Data
• Graph Evolution: Densification and Shrinking Diameters
• DynGEM: Deep Embedding Method for Dynamic Graphs
• Deep Coevolutionary Network: Embedding User and Item Features for Recommendation

Cited by in corpus (291)

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