PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Learning on Graphs: A Survey

Ziwei Zhang, Peng Cui, Wenwu Zhu

arXiv:1812.04202v3cs.LGcs.SIstat.ML

TL;DR

Deep learning on graphs remains difficult because graph structures, scales, and domain constraints differ substantially from those of grid-like data. The survey organizes existing approaches into five categories and systematically reviews their development, differences, compositions, applications, and future directions. It concludes by identifying compositionality, interpretability, robustness, and specialized models for understudied graph types as important open directions.

  • Problem

    Applying deep learning to graphs is difficult because graphs are irregular, can be very large, and may require interdisciplinary constraints that complicate model design and training.

  • Method

    The paper comprehensively surveys graph deep-learning methods, categorizing them into Graph RNNs, GCNs, GAEs, Graph RL, and graph adversarial methods while analyzing their differences and compositions.

  • Results

    The survey provides a development-history-based overview of graph deep-learning methods and summarizes their applications, implementations, and future research directions.

  • Takeaways & Limitations

    The paper identifies systematic composition of architectures, principled incorporation of interdisciplinary knowledge, interpretability, robustness, and models for understudied graph types as important research directions.

  • Takeaways & Limitations

    Systematically composing architectures and incorporating interdisciplinary knowledge remain open problems, while interpretability and robustness are still challenging for graph deep-learning models.

Abstract

from arXiv · show

Deep learning has been shown to be successful in a number of domains, ranging from acoustics, images, to natural language processing. However, applying deep learning to the ubiquitous graph data is non-trivial because of the unique characteristics of graphs. Recently, substantial research efforts have been devoted to applying deep learning methods to graphs, resulting in beneficial advances in graph analysis techniques. In this survey, we comprehensively review the different types of deep learning methods on graphs. We divide the existing methods into five categories based on their model architectures and training strategies: graph recurrent neural networks, graph convolutional networks, graph autoencoders, graph reinforcement learning, and graph adversarial methods. We then provide a comprehensive overview of these methods in a systematic manner mainly by following their development history. We also analyze the differences and compositions of different methods. Finally, we briefly outline the applications in which they have been used and discuss potential future research directions.

1 INTRODUCTION

Deep learning on graphs is challenging because graphs are irregular, heterogeneous, large-scale, and often constrained by interdisciplinary knowledge. This survey organizes the diverse methods into five categories and reviews their development, relationships, applications, and future directions.

  • Motivation: Graph analysis is difficult because graphs lack grid structure, vary in types and tasks, and may contain millions or billions of nodes and edges.These properties complicate convolution and pooling, require task-specific architectures, and motivate scalable models with preferably linear graph-size complexity.
  • Motivation: Graph models may also need domain knowledge, while constraints such as nondifferentiable chemical objectives complicate gradient-based training.The survey identifies interdisciplinary integration as both an opportunity and a model-design challenge.
  • Survey scope: The survey addresses a gap in systematic comparisons by categorizing methods according to their architectures and training strategies.The five categories are graph recurrent neural networks, graph convolutional networks, graph autoencoders, graph reinforcement learning, and graph adversarial methods.
  • Survey scope: The paper reviews methods through their development history, analyzes differences and composition, and outlines applications, libraries, and future research directions.Its appendix also provides a source-code repository, time-complexity analysis, and common applications.
  • Related work: This survey differs from earlier reviews by systematically covering diverse graph deep-learning methods rather than focusing only on selected architectures or applications.Related surveys emphasized geometric deep learning, graph networks, graph attention, GCNs, or adversarial attacks, while network embedding is treated as an application example.

2 NOTATIONS AND PRELIMINARIES

The paper defines graph notation, matrix preliminaries, modeling assumptions, and task categories for subsequent discussions. It distinguishes node-focused from graph-focused learning while noting that the distinction is conceptual rather than mathematically rigorous.

  • Notation: A graph is represented as G = (V, E), with N nodes, M edges, adjacency matrix A, node features F_V, and edge features F_E.Graphs may be directed or undirected and weighted or unweighted; the paper mainly considers unsigned graphs.
  • Preliminaries: For undirected graphs, the Laplacian is L = D − A, while P = D^-1A defines random-walk transition probabilities.The paper also defines eigendecomposition of L and k-step neighborhoods using shortest-path distance.
  • Model assumptions: Unless stated otherwise, model functions are differentiable so parameters can be learned through backpropagation with optimizers such as Adam.The notation also includes layer superscripts, feature dimensionalities, sigmoid, ReLU, and general nonlinear activations.
  • Task categories: Node-focused tasks concern individual nodes, whereas graph-focused tasks concern entire graphs.Examples include node classification and link prediction versus graph classification, graph-property estimation, and graph generation.
  • Task categories: The node-versus-graph distinction is conceptual rather than mathematically rigorous because some tasks involve mesoscopic structures or can be transformed between viewpoints.Community detection is an example of a mesoscopic task, and node-focused problems can sometimes use egocentric networks.

3 GRAPH RECURRENT NEURAL NETWORKS

Graph RNNs model recursive or sequential graph patterns through node states or a shared graph state. The survey covers their foundations, limitations, gated improvements, and applications to graph generation, dynamic graphs, and hybrid architectures.

  • Graph RNN overview: Graph RNNs divide into node-level and graph-level models, depending on whether states represent individual nodes or the entire graph.They are designed to capture recursive and sequential graph patterns.
  • Node-level RNNs: Early GNNs recursively encode each node with a low-dimensional state and use iterative state updates to produce task outputs.A special node can represent the whole graph for graph-focused tasks, followed by optimization of a task-specific objective.
  • Node-level RNNs: GNNs unify recursive neural networks and Markov chains, and their neighborhood-information exchange anticipates formulations used by later GCNs.This positions early GNNs as a conceptual foundation for subsequent graph architectures.
  • Node-level RNNs: Early GNNs require a contraction map for a unique solution and are computationally expensive because they need many iterations to reach stable states.The contraction requirement limits modeling ability, while repeated iterations increase computation.
  • Node-level RNNs: GGS-NNs replace recursive updates with GRUs, removing the contraction-map requirement and supporting modern optimization techniques.This is presented as a notable improvement over the original GNN formulation.
  • Graph-level RNNs: Graph-level RNNs use one RNN for the entire graph and support graph generation, dynamic-graph modeling, and combinations with GCNs or GAEs.Examples include hierarchical RNNs for autoregressive node and edge generation, time-aware LSTMs for evolving interactions, and LSTMs that extend information diffusion across GCN outputs.

4 GRAPH CONVOLUTIONAL NETWORKS

GCNs adapt convolutional ideas to irregular graphs through spectral or spatial operations, with later designs emphasizing efficiency, locality, and applicability across multiple graphs.

  • GCNs learn local and global graph patterns through designed convolution and readout functions, typically trained with task-specific losses.
  • Convolution operations: Graph convolutions comprise spectral methods based on graph Fourier representations and spatial methods based on node neighborhoods, with some overlap.
  • Spectral methods: Spectral convolution uses the graph Laplacian and learnable filters to transform node signals, aggregate information, and apply nonlinear transformations.
  • Spectral methods: Spectral filters face scalability and transferability limitations because eigendecomposition costs O(N^3), forward and backward passes cost at least O(N^2), and filters depend on each graph's eigenbasis.
  • The Efficiency Aspect: ChebNet replaces eigendecomposition with polynomial filters whose sparse computation costs O(KM) and whose representations depend only on K-step neighborhoods.
  • The Efficiency Aspect: Kipf and Welling's first-order GCN uses immediate neighbors and self-connections; stacking layers provides capacity similar to ChebNet and reportedly better results.
  • The Aspect of Multiple Graphs: For multiple graphs, PATCHY-SAN imposes fixed-size, ordered receptive fields through graph labeling, but its convolution depends heavily on a non-learned preprocessing procedure.
  • Frameworks: MPNNs unify spatial graph convolution through learned message and vertex-update functions, while variants add master nodes or towers and can achieve state-of-the-art molecular-property prediction.

4.2 Readout Operations

Graph readout operations aggregate node representations into graph-level representations while addressing order invariance and hierarchical structure. Methods range from simple statistics to differentiable clustering, pseudo-nodes, ordered pooling, and jumping connections.

  • Readout Operations: Readout operations aggregate node representations into a graph-level representation for graph-focused tasks.They are related to graph coarsening because coarsening can reduce a graph to a single representative node.
  • Order Invariance: Order-invariant readouts preserve the graph representation when node and edge indices are changed by a bijection.This requirement reflects the fact that graph structure should not depend on arbitrary node labeling.
  • Statistics: Summation, averaging, and max-pooling are simple order-invariant statistics, but first-moment statistics may fail to distinguish graphs with different node-representation distributions.Fuzzy histograms address this limitation by matching node representations to predefined bins and concatenating the resulting histograms.
  • Statistics: Fully connected readouts learn different weights for nodes but cannot guarantee order invariance.The method treats the concatenated node representations as inputs to a parameterized weighted sum.
  • Hierarchical Clustering: Hierarchical methods exploit graph structure by clustering nodes across resolutions, while DiffPool learns soft assignments jointly with graph convolutions.DiffPool repeatedly coarsens the graph from N nodes to one node, with soft assignments yielding O(N^2) time complexity in principle.
  • Other Methods: Other readout strategies impose node orders, add pseudo-nodes, use set2set, or aggregate information across layers with jumping connections.JK-Nets use concatenation, max-pooling, or LSTM attention to combine layer representations, and experiments reported improved performance for multiple GCNs.

5 GRAPH AUTOENCODERS

Graph autoencoders learn low-dimensional node representations by reconstructing graph-derived features or modeling node relationships. Variants preserve different notions of proximity, represent uncertainty with distributions, incorporate node attributes, and support inductive learning, but some approaches face quadratic complexity or structural assumptions.

  • Autoencoder foundations: Graph autoencoders treat adjacency-derived matrices as node features and use dimensionality reduction to learn low-dimensional representations.Their implicit assumption is that graphs have an inherent, potentially nonlinear low-rank structure.
  • Autoencoder foundations: SAE reconstructs transition-matrix features with multilayer perceptron encoder and decoder networks, while adding sparsity regularization.The representation dimensionality satisfies d ≪ N.
  • Autoencoder variants: SDNE preserves both first-order proximity between connected nodes and second-order proximity between nodes with similar neighborhoods.It adds a Laplacian eigenmaps term and uses weighted reconstruction of adjacency entries.
  • Limitations: DNGR has O(N^2) input construction, and VGAE has O(N^2) time complexity because it reconstructs the full graph.SAE also relies on an implicit low-rank graph structure, while its motivating connection between spectral clustering and singular value decomposition was mathematically incorrect.
  • Autoencoder variants: DRNE reconstructs low-dimensional node vectors by aggregating ordered, sampled neighborhoods with an LSTM, preserving regular equivalence and centrality measures such as PageRank.Neighborhoods are ordered by degree, and sampling prevents overlong LSTM memory for high-degree nodes.
  • Variational autoencoders: G2G, VGAE, and DVNE extend graph autoencoding with probabilistic node representations, using Gaussian distributions, variational learning, or Wasserstein distance.G2G orders KL divergences according to graph distance, while DVNE preserves first- and second-order proximity using Wasserstein distance.
  • Inductive learning: GC-MC, VGAE, and related models can support inductive learning when node attributes are incorporated into the encoder, including through GCNs.Edge information is used during parameter learning, allowing application to nodes unseen during training.

6 GRAPH REINFORCEMENT LEARNING

Graph reinforcement learning models graph problems as sequential or partially observable decision processes, enabling agents to learn from feedback for generation, prediction, classification, and reasoning tasks. These methods are particularly suited to objectives and constraints that are non-differentiable.

  • Overview: Graph RL is effective for feedback-driven tasks involving non-differentiable objectives and constraints.The survey reviews these methods as a distinct graph deep-learning category.
  • Graph generation: GCPN models molecular graph generation as a Markov decision process in which an RL agent adds nodes and edges.It combines link-prediction actions, domain-specific and adversarial rewards, and GCN-based node representations.
  • Graph generation: MolGAN generates complete molecular graphs directly rather than through sequential actions, working particularly well for small molecules.
  • Chemical prediction: GTPN uses an RL agent to select molecular node pairs and predict new bonding types, with immediate and terminal rewards for correctness.GCNs learn node representations and an RNN memorizes the prediction sequence.
  • Graph classification: GAM formulates random-walk graph classification as a partially observable Markov decision process, where the agent predicts the graph label and selects subsequent nodes.The reward is 1 for a correct prediction and −1 otherwise.
  • Knowledge-graph reasoning: DeepPath and MINERVA apply RL to knowledge-graph reasoning by predicting successive nodes and outputting paths toward target answers.DeepPath focuses on informative pathfinding, whereas MINERVA addresses question answering.

7 GRAPH ADVERSARIAL METHODS

Graph adversarial methods use adversarial training to improve graph generation, embedding, and semi-supervised learning, while adversarial attacks probe or degrade graph-model performance. The survey covers both generative adversarial frameworks and targeted or non-targeted attacks.

  • Adversarial training: GAN-based graph methods jointly train generators and discriminators through a minimax game, with generators producing samples intended to fool discriminators.Adversarial training is reviewed for graph generation and discriminative-model enhancement.
  • Adversarial training: GraphGAN improves graph embedding by generating negative node pairs whose similarities the discriminator should keep small.Original-graph pairs are assigned large similarities, while generated pairs are assigned small similarities.
  • Adversarial training: ANE adds GAN-based prior-distribution regularization to network-embedding methods such as DeepWalk.
  • Adversarial training: GraphSGAN generates fake nodes in density gaps between subgraphs to weaken propagation across clusters during semi-supervised learning.Its objective uses loss terms designed to place generated samples in those gaps at equilibrium.
  • Graph generation: NetGAN learns distributions of biased random walks with an LSTM-based GAN and uses them to generate graphs capturing global network patterns.
  • Adversarial attacks: Adversarial attacks modify graph structures or node attributes to induce targeted misclassification or reduce overall model performance.Nettack targets node classification, while later work studies structure-only, limited-information, and non-targeted attacks.

8 DISCUSSIONS AND CONCLUSION

The survey situates graph deep learning across diverse applications and emphasizes domain knowledge, model integration, and open challenges. Future directions include broader graph structures, compositional architectures, dynamic graphs, interpretability, and robustness.

  • Applications: Graph deep-learning methods are applied to social influence, recommendation, chemistry, biology, physics, disease and drug prediction, NLP, computer vision, and traffic forecasting.
  • Applications: Application-specific graph construction and architecture selection should incorporate domain knowledge, while graph models can serve as modules within CNN or NLP systems.The survey notes examples involving traffic forecasting, object detection, and syntactic constraints.
  • Implementations: Open libraries and collected source code make graph methods easier to learn, compare, and improve, with some implementations addressing distributed computing.
  • Future directions: Existing methods mainly focus on homogeneous graphs, leaving heterogeneous, signed, and hypergraph structures understudied.The survey identifies models for these structures as an important next step.
  • Future directions: Systematically composing existing architectures and integrating interdisciplinary knowledge principledly remain open problems, with AutoML suggested as one possible aid.Examples include using GCNs within graph autoencoders or graph reinforcement learning.
  • Future directions: Most existing methods focus on static graphs, motivating methods for evolving nodes, edges, features, and incremental updates.
  • Future directions: Interpretability is critical in risk-sensitive applications, while robustness remains important because many graph deep-learning models are sensitive to adversarial attacks.

APPENDIX A SOURCE CODES

The appendix catalogs source code for the methods discussed in the manuscript, including implementation details and authorship information.

  • The source-code collection lists method names and links for papers discussed in the manuscript.
  • It records the programming language and frameworks used by each implementation.
  • It indicates whether the original paper authors published the code.

APPENDIX B APPLICABILITY FOR COMMON TASKS

The appendix summarizes which models have been applied to six common graph-learning tasks, based on experiments reported in the original papers.

  • The applicability summary covers node clustering, node classification, network reconstruction, link prediction, graph classification, and graph generation.
  • Model applicability is assessed from whether the original papers reported experiments for each task.
  • The results provide a task-oriented comparison of graph-based deep learning models.

APPENDIX C NODE CLASSIFICATION RESULTS ON BENCHMARK DATASETS

This appendix reviews node-classification benchmarks and reports that fixed-split comparisons often show similar performance while potentially producing spurious conclusions. It therefore calls for more comprehensive evaluation setups.

  • Node classification is the most common task among graph-based deep learning models reviewed in the appendix.
  • The benchmark suite contains citation graphs, a Reddit discussion graph, and protein-protein interaction graphs with task-specific features and labels.
  • Cora, Citeseer, and PubMed use one graph for both training and testing, whereas Reddit and PPI use different training and testing graphs.
  • Many state-of-the-art methods achieve roughly comparable benchmark performance, with differences smaller than one percent under fixed dataset splits.
  • Fixed dataset splits can produce spurious comparisons, motivating more comprehensive evaluation setups.

APPENDIX D AN EXAMPLE OF GRAPH SIGNALS

The appendix introduces graph signals as node-indexed numerical values and uses their spectral representation to illustrate graph-signal smoothness and frequency.

  • A graph signal assigns one numerical value to each node of a graph.
  • Node features satisfying this requirement can be treated as graph signals, while both signal values and graph structure matter for analysis.
  • Eigenvectors associated with small eigenvalues represent smooth, low-frequency signals, while those associated with large eigenvalues represent non-smooth, high-frequency signals.

APPENDIX E TIME COMPLEXITY

The appendix reports theoretical time complexities primarily in terms of graph nodes N and edges M, omitting usually small constant factors. Across methods, complexity ranges from linear in M to quadratic or higher, with additional dependence on sampling, iterations, time slices, or approximation choices.

  • Scope: The analysis focuses on graph-size dependence, chiefly N and M, while omitting hidden dimensions and iteration counts treated as small constants.The reported values are theoretical, and exact algorithmic efficiency may depend on additional factors.
  • Additional factors: Several methods add explicit factors for iterations, pseudo-time, meta-path pairs, samples, walks, or paths, such as O(MI_f), O(MT), O(M_φ), and O(d_avg sT).DeepPath additionally reports O(s^2T) for its diversity constraint, while GAM and MINERVA use O(d_avg sT).
  • Graph-size dependence: Many graph convolutional and message-passing methods have O(M) complexity, including ChebNet, GNN variants, GAT, MPNNs, R-GCNs, and SGC.These costs commonly arise from computations over existing edges or adopted graph-convolution layers.
  • Sampling: Sampling-based methods report O(NsL), where s is sampled or maximum neighborhood size and L is the number of layers.This applies to GraphSAGE, GaAN, PinSage, StochasticGCN, FastGCN, and Adapt, with sampling performed in neighborhoods or layers depending on the method.
  • Model-specific costs: Complexity can vary with model design: GCPN and GraphGAN report O(MN), ANE adds O(N), DGNN reports O(Md_avg), and RMGCNN ranges from O(MN) to O(M) with approximation.Dynamic GCN reports O(Mt), reflecting one GCN execution per time slice; DVNE is stated as improvable from O(Md_avg) to O(M).
Loading 1812.04202v3…