PaperlayerView exact revision on arXiv

Source-linked AI summary

A Gentle Introduction to Deep Learning for Graphs

Davide Bacciu, Federico Errica, Alessio Micheli, Marco Podda

arXiv:1912.12693v2cs.LGcs.SIstat.ML

TL;DR

Deep learning for graphs lacks a unified, systematic treatment of its rapidly expanding literature. This paper presents a generalized local and iterative framework for graph representation learning, introduces reusable architectural building blocks, and identifies challenges and applications.

  • Problem

    Adaptive graph-processing models need a unified framework that highlights their similarities, differences, and novelties.

    Source: §8 · p. 41

  • Method

    The paper develops a generalized formulation of graph representation learning and introduces architectural building blocks for local, iterative structured-information processing.

    Source: §1 · p. 4

  • Results

    Under mild conditions, the formulation possesses universal approximation capabilities.

    Source: §4.1 · p. 25

  • Takeaways & Limitations

    The framework provides a consistent foundation for designing neural models for graphs and organizing adaptive graph-processing research.

    Source: §1 · p. 4, §8 · p. 41

    The paper notes trends and pitfalls in datasets and methodologies used to assess deep graph networks.

    Source: §8 · p. 41

Abstract

from arXiv · show

The adaptive processing of graph data is a long-standing research topic which has been lately consolidated as a theme of major interest in the deep learning community. The snap increase in the amount and breadth of related research has come at the price of little systematization of knowledge and attention to earlier literature. This work is designed as a tutorial introduction to the field of deep learning for graphs. It favours a consistent and progressive introduction of the main concepts and architectural aspects over an exposition of the most recent literature, for which the reader is referred to available surveys. The paper takes a top-down view to the problem, introducing a generalized formulation of graph representation learning based on a local and iterative approach to structured information processing. It introduces the basic building blocks that can be combined to design novel and effective neural models for graphs. The methodological exposition is complemented by a discussion of interesting research challenges and applications in the field.

1. Introduction

Graphs are ubiquitous, richly structured data, but their variable topology, discreteness, combinatorial complexity, and cyclic dependencies make learning expressive and computationally challenging. This tutorial provides a historically grounded, progressive introduction to graph representation learning through local iterative processing, architectural building blocks, tasks, challenges, and applications.

Motivation

  • Graphs represent compositional and relational data across chemistry, biology, social networks, and recommender systems, motivating adaptive deep learning models.Their richness and growing repositories have driven increased interest in models that process graphs adaptively.Source: §1 · pp. 1–2

Challenges

  • Graph learning must handle varying sizes and topologies, unavailable node ordering, discrete structure, combinatorial complexity, loops, and challenging message passing.These properties create expressiveness and computational-complexity challenges compared with vectorial data.Source: §1 · p. 2

Historical foundations

  • The earliest models to tackle processing cycles were the Graph Neural Network and the Neural Network for Graphs.Source: §1 · p. 3

Tutorial contribution

  • The paper provides a gentle, well-founded, consistent, and progressive tutorial introduction to neural networks for graphs, focusing on concepts and building blocks for assembling deep architectures.Source: §1 · p. 3

Methodological approach

  • Its top-down methodology begins with generalized graph representation learning and emphasizes local, iterative processing over global fixed-adjacency spectral approaches.The paper then develops graph convolutions, attention, sampling, pooling, and whole-structure aggregation as reusable architectural components.Source: §1 · p. 4

Paper roadmap

  • The paper proceeds from architectural building blocks to graph-learning tasks, cost functions, inductive biases, related approaches, research challenges, applications, and future directions.Its roadmap covers Sections 2–7 and concludes with final considerations and research hints.Source: §1 · p. 4

2. High-level Overview

This overview establishes graph notation and presents Deep Graph Networks as modular, local, iterative models that propagate information through variable-topology graphs to produce node and graph representations. It explains how permutation-invariant neighborhood processing diffuses context across graph regions and motivates feedforward and constructive architectures, including their differing training characteristics.

2.1. Mathematical Notation

  • The tutorial introduces graph notation for directed or undirected graphs, node and edge features, neighborhoods, and a general class allowing cyclic, acyclic, positional, and non-positional graphs.Undirected edges can be represented by two oppositely oriented arcs with identical features.Source: §2.1 · pp. 5–6

2.2. The Bigger Picture

  • Deep Graph Networks map an input graph to order-independent node states that can be computed in parallel and aggregated into a graph representation for node, edge, or graph tasks.The model focuses on learning node representations, while prediction components remain modular and task-specific.Source: Figure 2 · p. 7, §2.2 · p. 7
  • The tutorial organizes graph models into neural, Bayesian, and generative families, while emphasizing their shared reliance on local relations and iterative information diffusion.This taxonomy is illustrative rather than a strict compartmentalization of methodologies.Source: §2.2 · p. 8

2.3. Local relations and iterative processing of information

  • Local node-level processing handles graphs that vary in size and shape by reusing shared parameters across nodes, while also combining experience across graphs.The stationarity assumption reduces parameters but requires mechanisms that capture global graph structure.Source: §2.3 · p. 9
  • Permutation-invariant functions address graphs with variable neighborhood shape because their outputs remain unchanged when the neighborhood’s input elements are reordered, making them well suited to this setting.Source: §2.3 · pp. 9–10
  • Cyclic graphs create mutual dependencies that can form an infinite loop under parallel local processing, so node states are computed iteratively from neighbors’ previous-iteration states.Iterations incrementally refine node representations, but convergence remains a concern.Source: §2.3 · pp. 10–11
  • Iterative graph processing is implemented either with constraints that force convergence or by mapping successive iterations to independent deep-network layers.The symbol ℓ denotes either an iteration step or a layer through which nodes propagate information.Source: §2.3 · p. 11

2.4. Three Mechanisms of Context Diffusion

  • Message passing diffuses context through message dispatching to graph neighbors followed by state updates from incoming messages and possibly the current node state [48].Initial node states commonly use node feature vectors.Source: §2.4 · p. 11
  • Iterative message passing with local aggregation allows contextual information to travel across the graph, enabling nodes to acquire knowledge about wider surroundings and farther-away nodes rather than only immediate neighbors.Source: §2.4 · p. 12
  • Deep graph learning models can be partitioned by their diffusion mechanisms into recurrent, feedforward, and constructive approaches.Recurrent architectures treat iterative node-information processing as a dynamical system; Graph Neural Network and Graph Echo State Network representatives enforce convergence through contractive dynamics.Source: §2.4 · pp. 12–13
  • Feedforward models stack differently parameterized layers to compose local context, allowing node context to grow with depth up to the entire graph.Unlike recurrent diffusion, they manage cycle-induced dependencies without convergence constraints; this resembles convolutional receptive fields, although graph neighborhoods vary in size and node ordering is rarely fixed.Source: §2.4 · p. 13
  • Feedforward graph models are popular for their simplicity, efficiency, and performance, but deep end-to-end networks suffer gradient-related problems [77].The text identifies vanishing/exploding-gradient issues as a limitation of deep graph networks.Source: §2.4 · p. 14
  • Constructive architectures are feedforward models trained layer-wise; by design, deep networks avoid vanishing/exploding gradients, allowing context to propagate more effectively across layers and node states.Source: §2.4 · p. 14
  • Constructive models solve problems in a divide-et-impera fashion by incrementally splitting tasks into manageable sub-tasks; each layer addresses a sub-problem, and subsequent layers progressively use its result to solve the global task.Source: §2.4 · pp. 14–15

3. Building Blocks

This section presents common building blocks for local graph learning, focusing on neighborhood aggregation and pooling mechanisms for shaping graph representations. It covers graph coarsening and permutation-invariant aggregation as reusable components that can be combined into trainable graph models.

3. Building Blocks

  • Architectural building blocks impose biases that determine the representations graph models can compute, while providing ingredients that can be combined into effective architectures.The section emphasizes common components rather than a fully comprehensive formalization.Source: §3 · p. 15

3.1. Neighborhood Aggregation

  • Neighborhood aggregation uses permutation-invariant functions to combine node and neighbor information, with neighborhoods optionally expanded through sampling to bound computation.Sampling random subsets reduces aggregation cost for large dense graphs; GraphSAGE can use wider neighborhoods at additional but bounded computational cost.Source: §3.1 · pp. 15, 18
  • Neighborhood aggregation can incorporate discrete or continuous edge labels by weighting neighbor contributions, while attention assigns relevance scores to neighbors but is generally distinct from edge processing.Edge-aware mechanisms enrich node representations using relation information; attention instead produces weighted neighbor averages, and Graph Attention Network does not use edge information.Source: §3.1 · pp. 16–17

3.2. Pooling

  • Pooling reduces graph dimensionality after graph layers to discover important communities, encode them in representations, and lower computational costs; mechanisms are adaptive or topological.Adaptive pooling is trainable; Differentiable Pooling learns node clustering from embeddings produced by the previous layer.Source: §3.2 · p. 19
  • Pooling coarsens graphs by clustering nodes into supernodes or repeatedly contracting highly ranked edges, with adaptive assignments remaining differentiable.DNGN-based pooling produces a soft-membership matrix for graph recombination, while Edge Pooling ranks edges from incident-node embeddings and contracts them iteratively.Source: §3.2 · pp. 19–21
  • Top-k Pooling overcomes dense adjacency matrices by learning a projection vector to compute node-embedding scores via dot product, selecting top-ranked nodes, slicing the graph matrix accordingly, and using differentiable gating.Source: §3.2 · p. 20
  • Topological pooling uses graph structure and communities without adaptation, so it need not be differentiable and can be reused across multitask scenarios.GRACLUS performs spectral graph partitioning without adjacency eigendecomposition, while Non-negative Matrix Factorization Pooling [2] provides soft node clustering.Source: §3.2 · p. 21

3.3. Node Aggregation for Graph Embedding

  • For graph classification, node representations can be aggregated into a global graph embedding; because graph size is not fixed, aggregation must be permutation-invariant, commonly using identity with element-wise mean, sum, or max.Source: §3.3 · p. 21

4. Learning Criteria

This section surveys unsupervised and supervised learning criteria for graph representation tasks, including generative decoding of discrete, variable-size graph structures. It also characterizes local iterative models through their architectural and learning properties.

4.1. Unsupervised Learning

  • Unsupervised graph learning uses reconstruction, maximum-likelihood, clustering, mutual-information, and entropy-regularization criteria, often as task objectives or regularizers.Link prediction assumes homophily and is beneficial when neighboring nodes tend to share communities; entropy regularization encourages one-hot assignments and well-separated communities, while differentiable sparse pooling remains challenging.Source: §4.1 · pp. 23, 25, 26
  • Maximum-likelihood methods target the distribution of neighboring states; the Contextual Graph Markov Model constructs a deep network as a stack of simple Bayesian networks.Source: §4.1 · p. 25
  • Mutual-information methods such as Deep Graph Infomax distinguish original and corrupted graphs, but manually chosen corruption functions can bias learning.The discriminator uses a bilinear score over node and graph representations.Source: §4.1 · p. 26

4.2. Supervised Learning

  • Supervised graph learning separates node classification, graph classification, and graph regression, using cross-entropy or negative log-likelihood for classification and Mean Square Error for regression.Node classification may be inductive or transductive; graph-level prediction first aggregates node representations into a single graph representation, while benchmark procedures have faced reproducibility and experimental-setting problems.Source: §4.2 · pp. 26–27

4.3. Generative learning

  • Generative graph models address discrete, combinatorial, variable-size structures by decoding graphs from latent representations, using graph-level or node-level approaches.Graph-level decoders generate a probabilistic adjacency matrix in one shot but are generally not permutation invariant; node-level decoders condition adjacency generation on sampled node representations, are permutation invariant, and are more expensive.Source: §4.3 · pp. 28–30
  • Graph-level sampling can be nondifferentiable and non-permutation-invariant, whereas Gumbel-Softmax reparameterization offers a differentiable alternative and approximate matching can restore permutation invariance.When sampling adjacency entries or using approximate graph matching, reconstruction loss is computed on the probabilistic matrix because the actual reconstruction loss cannot be back-propagated.Source: §4.3 · p. 29
  • Generative auto-encoders explicitly learn a latent representation distribution, while generative adversarial networks implicitly learn to sample through jointly trained generator and discriminator functions.Auto-encoder objectives combine decoder reconstruction with a divergence that encourages a tractable prior, commonly an isotropic Gaussian N(0, I); adversarial models distinguish generated graphs from dataset graphs without directly manipulating P(g).Source: §4.3 · p. 30

4.4. Summary

  • The summary characterizes local iterative models by context diffusion, embedding computation, layer construction, approach type, and optional capabilities such as edge handling, pooling, neighbor attention, and sampling.Table 2 recaps the main DGN properties, with layers described as one, fixed, or adaptively determined and context referring to a layer’s context-diffusion method.Source: §4.4 · pp. 31–32

5. Summary of Other Approaches and Tasks

This section reviews graph-learning approaches beyond the paper’s mainly local and iterative taxonomy, covering kernels, spectral methods, random walks, adversarial robustness, and sequential graph generation. These approaches offer complementary capabilities but retain distinct limitations, including non-adaptivity, graph-shape dependence, adversarial vulnerability, and node-order dependence.

5.1. Kernels

  • Kernels provide long-standing graph-similarity methods but are non-local, non-adaptive, human-designed, and difficult to scale when datasets are large.They work particularly well when target properties are known, while Nonparametric Small Random Networks [117] reportedly outperform many DGNs and graph kernels on several tasks.Source: §5.1 · p. 33

5.2. Spectral methods

  • Spectral methods analyze adjacency and Laplacian matrices; Graph Convolutional Networks connect spectral theory with local, iterative graph processing.The Graph Fourier Transform uses the Laplacian eigenvector basis, while GCN layers truncate the Chebyshev expansion to obtain Hℓ+1 = σ(LHℓW).Source: §5.2 · pp. 33–34
  • Spectral filters can depend on a graph’s Laplacian, scale with node count, require eigendecomposition, and lack spatial localization, although Chebyshev truncation addresses these issues.Spectral techniques are generally intended for graphs with the same shape and different node labels.Source: §5.2 · p. 34

5.3. Random-walks

  • Random walks generate node embeddings by exploring graph neighborhoods; Node2Vec learns surrounding-node likelihoods while biasing walks toward depth-first or breadth-first exploration.DeepWalk models random walks as sentences, and later work uses walks for graph generation and links them formally to GCN diffusion.Source: §5.3 · pp. 34–35

5.4. Adversarial training and attacks on graphs

  • Adversarial training improves graph-model robustness by minimizing a min-max objective over original and perturbed graphs, including edge changes or adversarial node noise.The resulting loss space is smooth and preserves predictive power when graphs are perturbed; adversarial training for regularization is relatively new [37].Source: §5.4 · p. 35

5.5. Sequential generative models of graphs

  • Sequential graph generators model construction as actions and can generalize across very different training distributions, but they rely on a fixed node ordering.Architectures sequentially add nodes or edges using neural decision processes, autoregressive adjacency prediction, or paired Gated Recurrent Unit networks.Source: §5.5 · p. 36

6. Open Challenges and Research Avenues

The paper identifies underexplored research avenues for graph learning, spanning dynamic graphs, model bias-variance trade-offs, edge information, and hypergraph learning. Progress is constrained especially by limited large benchmarking datasets and incomplete theoretical characterizations.

6.1. Time-evolving graphs

  • Time-evolving graph learning generalizes static-graph techniques, but progress is currently limited by the lack of large datasets despite supervised [78] and unsupervised [141] proposals.Dynamic graph modeling remains an important extension of the surveyed methods.Source: §6.1 · pp. 36–37

6.2. Bias-variance trade-offs

  • Node aggregation mechanisms determine which structures a model can discriminate; Graph Isomorphism Network is theoretically as powerful as the 1-dim Weisfeiler-Lehman test and can overfit most applied datasets.Source: §6.2 · p. 37

6.3. A sensible use of edge information

  • Edge information is usually incorporated through weighted aggregation, leaving open whether context spreading should apply to edges and how its discriminative power should be characterized.Existing models using additional edge features include.Source: §6.3 · p. 37

6.4. Hypergraph learning

  • Hypergraph learning extends graph learning to edges connecting node subsets; recent methods [38] draw on local iterative processing, but scarce benchmarks hinder empirical evaluation.Benchmarking limitations affect hypergraph learning similarly to time-evolving graph research.Source: §6.4 · p. 37

7. Applications

Graph learning applies broadly across chemistry, social networks, language, security, spatio-temporal forecasting, and recommendation, often replacing flat or sequential representations with structured graph formulations. The paper also releases a software library for rigorous DGN experiments.

7. Applications

  • Graph learning can improve problems traditionally addressed with flat or sequential representations, and the authors release a library for rigorous DGN experiments.The application list is introductory and explicitly non-exhaustive.Source: §7 · p. 38

7.1. Chemistry and Drug Design

  • DGNs map molecular structures to biological outcomes, predict biological activity and chemical properties such as toxicity and solubility, identify structural similarities among compounds [32], detect drug side effects, and discover novel compounds.Source: §7.1 · p. 38

7.2. Social networks

  • Social graphs represent users and relations such as friendship or co-authorship, supporting node and graph classification for risks including misinformation and unhealthy behavior [91].They provide abundant user features but raise privacy and ethical concerns that limit public dataset availability.Source: §7.2 · p. 39

7.3. Natural Language Processing

  • In NLP, dependency parsers convert token sequences into trees or graphs so models capture syntactic and semantic [84] relations, including graph-to-sequence translation.This formulation incorporates dependencies from source and target sentences in neural machine translation.Source: §7.3 · p. 39

7.4. Security

  • Security applications include detecting compiler-equivalent programs, predicting bugs from augmented Abstract Syntax Trees, identifying obfuscation, and extracting Control Flow Graph features [87].These tasks make static code analysis a promising application avenue for graph learning.Source: §7.4 · pp. 39–40

7.5. Spatio-temporal forecasting

  • For evolving graphs, approaches combine a DGN for structural properties with a Recurrent Neural Network for temporal dependencies, forecasting traffic, recognizing actions, and modeling supply chains.The task requires capturing both dependencies between nodes and their temporal evolution.Source: §7.5 · p. 40

7.6. Recommender Systems

  • Recommender systems encode user-item relations as bipartite graphs, making recommendation equivalent to link prediction, but large-graph scalability motivates neighborhood sampling.User-user and item-item relations can instead be represented as standard undirected graphs; DGN recommender models include [92].Source: §7.6 · p. 40

8. Conclusions

The field of neural networks for graph processing has become a vibrant research area, but its rapid expansion has outpaced systematization and tracking of the literature. The paper identifies unified formalization, robust benchmarking, software support, and impactful applications as priorities for reaching maturity.

Future challenges

  • The field’s fast production of models and variants has created an expansive research phase with insufficient attention to systematization and early and recent literature.The paper argues that addressing these gaps is necessary for progress toward a maturity phase.Source: §8 · p. 41
  • A unified framework should formalize adaptive graph-processing models, highlight their similarities, differences, and novelties, and support higher-level reasoning about their theoretical and expressiveness properties.Source: §8 · p. 41
  • Rich and robust benchmarks are needed to assess models under fair, consistent, and reproducible conditions, especially given documented dataset and methodological pitfalls.Standardized data and methods are under development, including the Open Graph Benchmark.Source: §8 · p. 41
  • Widely adopted software packages, particularly PyTorch Geometric [39] and Deep Graph Library, support standardized graph interfaces and practical training with GPU compatibility and graph mini-batching.These tools facilitate development and help transfer standard deep-learning techniques to graph processing.Source: §8 · p. 41
  • Applications will signal methodological maturity when graph-processing research knowledge transfers into impactful innovation for society.Chemistry [18] and life sciences are identified as promising application areas.Source: §8 · p. 42

Appendix A. Acronyms Table

Appendix A provides a reference table of acronyms, their expanded model names, and associated references.

Appendix A. Acronyms Table

  • The acronym table lists each acronym alongside its model name and reference.Table A.3 is described as a reference table containing acronyms, their extended names, and associated references.Source: Table A.3 · p. 43, Appendix A · p. 43

Related papers

Loading 1912.12693v2…