A Survey on Graph Representation Learning Methods

In plain words

A graph is a set of things and the links between them, such as people and their friendships. Most machine learning tools want a list of numbers per item, so graph methods first turn each node into a vector that captures where it sits in the network. Those vectors can then feed a classifier that guesses a node's label or a predictor that guesses whether two nodes should be linked.

This survey walks through the two main families of such methods. The older family builds vectors from simple tools: random walks through the graph, matrix factorization, and small neural networks. The newer family uses graph neural networks, which build each node's vector by repeatedly mixing in the vectors of its neighbours. The authors look at both kinds of graph, the ones that stay fixed and the ones that change over time.

The survey also lists the known weak points of graph neural networks, such as their trouble with deep stacks and with long-distance links, and it lists open research questions. It contains no new experiments, so it is a map of the field rather than a source of benchmark results.

TL;DR

• Survey, not a method: no experiments are run, and no method is trained or evaluated here §1 §6.
• Covers traditional node embedding (factorization, random walks, autoencoders, temporal point processes) and GNN-based embedding, for static and dynamic graphs §1 §3 §4.
• Lists nine GNN limitations (expressive power, over-smoothing, scalability, long-range dependencies, catastrophic forgetting, homophily, substructures, over-squashing, design space) with the proposed fixes §4.6.
• Authors state the survey covers over 300 papers from data mining, machine learning and AI venues §1.
• Use it to find the method family for a task and its named variants. Verify every number and every design detail in the original method papers, not here.

Problem

Adjacency matrices grow with the square of the node count, and hand-made graph features do not capture the whole structure §2.1. A graph embedding maps nodes (or edges, or subgraphs) into a space of dimension d much smaller than the number of nodes, while keeping similar nodes close §2.1.

Earlier surveys mostly cover static graphs and treat dynamic graphs only briefly, or cover dynamic graphs but only GNN-based methods §1. The authors aim to cover both traditional and GNN methods for both static and dynamic graphs in one place §1.

Method

This is a taxonomy. The organisation is as follows.

Definitions used throughout §2. A graph is a pair of nodes and edges. Adjacency, degree and Laplacian matrices are defined (L = D − A) §2. A node embedding maps each node to a d-dimensional vector that preserves node similarity. Edge and subgraph embeddings are usually built from node embeddings, for example with a Hadamard product or a mean §2.1. First-order proximity means directly connected nodes; second-order proximity means nodes with shared neighbours §3.1. A static graph is fixed. A dynamic graph is either a sequence of snapshots (discrete time) or a stream of timed events (continuous time) §3.2.

Traditional static methods §3.1:

1. Factorization: build a proximity matrix (adjacency, higher-order adjacency, Katz index, personalized PageRank, common neighbours, and others), then factorize it into node vectors §3.1.1 tab. 1.
2. Random walks: generate walks from each node, then train a skip-gram model on the walks so that co-occurring nodes get similar vectors. DeepWalk takes next steps uniformly; node2vec biases steps with two parameters p and q §3.1.2 eq. 2 eq. 3 eq. 4.
3. Non-GNN deep learning: autoencoders that reconstruct the adjacency matrix (SDNE, DNGR), and a variational autoencoder over the graph (VGAE) §3.1.3 eq. 7 eq. 8.

Traditional dynamic methods §3.2:

1. Aggregation: collapse snapshots into one graph (summing or weighting adjacency matrices), or embed each snapshot and combine the vectors over time, for example with a time-series model. Factorization of a node-by-node-by-time tensor also falls here §3.2.1.
2. Temporal random walks: walks that only follow edges with non-decreasing timestamps (CTDNE), updated walks after edge changes (EvoNRL), or snapshot-initialised node2vec (DynNode2vec) §3.2.2 eq. 9.
3. Non-GNN deep learning: snapshot-to-snapshot warm-started autoencoders (DynGEM), VGAE with a penalty that keeps consecutive latent variables close (Dyn-VGAE) eq. 10, and autoencoders over past adjacency matrices (dyngraph2vec) §3.2.3.
4. Temporal point processes: Hawkes-process models of when neighbours form (HTNE) eq. 11 eq. 12, two-process models of communication and association events (DyRep), and motif-based variants (MTNE) §3.2.4.
5. Other: DynamicTriad, which models the closing of open triads, with social-homophily and temporal-smoothness regularisers §3.2.5.

GNN basics §4.1. A GNN layer updates a node's state from its own state and an aggregate of its neighbours' states eq. 13. Stacking L layers gives each node a receptive field of L hops §4.1.1. Training can be supervised, semi-supervised or unsupervised; node, edge and graph tasks each add a head (classifier, pairwise scorer, or readout pooling) on top of the GNN §4.1.2. A node classification loss is typically cross-entropy over labelled training nodes eq. 14. The matrix form of a GCN-style layer is H(l+1) = σ(ÂH(l)W(l)) with  = D̃^(−1/2) à D̃^(−1/2) and à = A + I eq. 15 §4.1.2. The survey also explains the Weisfeiler–Lehman test, skip connections and receptive fields §4.1.3.

# Generic message-passing GNN  [§4.1.1] [eq. 13]
# Input:  node features x (N, d_in); adjacency A (N, N); depth L
# Output: node embeddings h (N, d)

def gnn_embed(x, A, L):
    # 1. Start every node from its input features  [§4.1.1]
    h = x                                      # (N, d_in)
    for layer in range(L):
        # 2. Aggregate neighbour states; the survey leaves
        #    f and g as learnable functions  [§4.1.1]
        messages = aggregate(g(h), A)          # (N, d)
        # 3. Combine each node's own state with its aggregate  [§4.1.1]
        h = f(h, messages)                     # (N, d)
    # 4. After L layers, h covers L-hop neighbourhoods  [§4.1.1]
    return h

Static GNNs §4.2:

1. Recurrent GNNs: the original GNN iterates node states to a fixed point eq. 16 §4.2.1. Gated GNNs replace this with a fixed number of GRU steps eq. 17. Implicit GNNs solve for an equilibrium directly §4.2.1.
2. Convolutional GNNs §4.2.2, in two families:
   • Spectral: graph Fourier transform and spectral filters. Spectral CNN learns the filter directly. GCN uses a first-order approximation with a renormalised adjacency §4.2.2. Other entries cover directional, elastic (l1 smoothing), framelet and simplified (SGC) variants.
   • Spatial: message passing over neighbours. GraphSAGE concatenates the node's own state with a mean, LSTM or max-pool over neighbours. GAT learns attention weights per neighbour. MPNN and the GN block give general frameworks that many models fit into. Others include GIN, which uses a sum aggregator, and BGNN, MAGNA, TinyGNN and cardinality-aware attention variants §4.2.2.

Spatial-temporal GNNs §4.3. RNN-based models combine graph convolution with recurrent cells (GCRN; a transformer-plus-GRU spatial-temporal model). CNN-based models use graph convolution with temporal convolutions, such as Graph WaveNet, which learns its adjacency matrix §4.3.1 §4.3.2. The fusion-graph model SFTGNN builds one graph joining spatial, temporal-similarity and time-adjacent links §4.3.2. Applications named: traffic, epidemic and sleep-stage forecasting §4.3.

Dynamic GNNs §4.4. Streaming GNNs train on new and existing changes as they arrive §4.4. TGAT adds a learned time encoding to graph attention, and CAW-N uses causal anonymous walks to score links §4.4. MTSN combines motif-preserving encoding with a temporal shift §4.4.

Limitations and fixes §4.6. For each limitation the survey names the cause and the proposed fixes, with a table of methods per topic:

• Expressive power: message passing is bounded by the WL test. Fixes include sum aggregation (GIN), identity-aware coloring, nested subgraph encoding and distance features §4.6.1 tab. 4.
• Over-smoothing: deep stacks make node vectors indistinguishable. Fixes include DropNode/DropEdge, mixed-order propagation (GRAND), and residual-style layer formulas that mix in the initial features, one with layer-wise weights α_l and β_l §4.6.2 tab. 5.
• Scalability: neighbour explosion. Fixes are neighbour sampling, layer sampling, graph sampling, linear models, reversible connections, vector quantisation and joint graph-and-model pruning §4.6.3 tab. 6.
• Long-range dependencies: transformer modules and implicit infinite-depth models (EIGNN) §4.6.4.
• Catastrophic forgetting: parameter-importance penalties (TWP) and experience replay (ER-GNN) §4.6.5.
• Homophily: models that separate node and neighbour embeddings and use higher-order neighbourhoods, for heterophilous graphs §4.6.6 tab. 7.
• Substructures: egonet-based pooling and similar fixes §4.6.7 tab. 8.
• Over-squashing: information from distant nodes is squeezed into fixed-length vectors; a fully-adjacent last layer is one proposed remedy §4.6.8.
• Design space: automated architecture search, for example GraphNAS with an RNN controller trained by reinforcement learning §4.6.9.

Real-world use §4.5 tab. 3. Table 3 lists systems that the authors say are deployed in production, for example travel-time prediction, recommendation and search ranking at several companies. Use this as a pointer to the systems, not as evidence of performance.

Open issues §5. Proposed directions include: fixing the newer limitations (over-squashing, dynamic and spatial-temporal settings); theory of optimisation and generalisation across graph sizes; PDE-based GNN design; using domain knowledge; learning with few labels (self-supervised and contrastive methods); and transferring vision and language architectures to graphs §5.

Hyperparameters

The survey runs no experiments and reports no training configuration, so no tuned values are given. The table lists the symbols that the survey defines without values.

Results

Survey: no experiments, so no benchmark numbers are reported here. The survey's own counts and listings:

Paper vs code

No official code. The paper links no repository, and the arXiv metadata has no code link. Searches for the authors' names as repository owners found none. A title-word search returned one repository from another group, which is not the authors' and was not used. Nothing is cloned.

Pitfalls

• Survey coverage is author-stated. The "over 300 papers" count and the claim that the survey is broader than earlier ones are the authors' statements; no list of inclusion criteria is given beyond venues and citation counts §1.
• Equation typos and unclear notation.
  • The graph factorization loss sums absolute differences |z_i^T z_j − a_ij| instead of squared differences §3.1.1 eq. 1. The survey does not say whether this is intended.
  • The SDNE first-order loss uses an element-wise absolute value §3.1.3 eq. 7.
  • The VGAE decoder is written as sigmoid(z_i^T, z_j), with a comma where a product is meant §3.1.3.
  • The GNN cross-entropy is written with unmatched parentheses and a sigmoid form that is binary, while the text describes multi-class node classification §4.1.2 eq. 14.
  • The HTNE base rate μ and influence α are both defined as |z_u − z_v|, with no sign or squaring stated §3.2.4 eq. 12. Check the original HTNE paper before implementing.
• Ambiguous names. The same acronym can name different methods (for example DANE and DNE appear in both static and dynamic rows of table 1). Check the arXiv id of any name before citing it tab. 1.
• Typos in the text. The variant list for dyngraph2vec names "dyngraph2vecAERNN" twice; the third variant is most likely dyngraph2vecRNN, but the text does not say so §3.2.3. Treat this as an inference.
• Table 1 is partly lumped. Some rows say "Methods in [citations]" without naming them, so the table is not a complete list tab. 1.
• Proximity definitions differ across methods. The survey mixes first-order and second-order proximity, adjacency, and learned proximity without a common normalisation. Compare methods only on the same benchmark and split, which this survey does not provide §2 §3.1.
• Node-level focus. The survey says most methods are node embedding methods; edge and subgraph embeddings are usually derived from node vectors §2.1.
• Dynamic-graph definitions. Snapshot methods and event-stream methods are not interchangeable. Converting one to the other changes what the model can see §3.2.
• Open issues are one author's view. The directions in §5 are the authors' selection, not a consensus.

Lineage

• Builds on: not applicable; this is a survey. It names the methods in table 1 and the foundational ones they discuss (for example DeepWalk, node2vec, GCN, GraphSAGE, GAT), none of which has a card here §3 §4 tab. 1.
• Compared against: other graph representation surveys cited in the introduction (for example the ones that cover static graphs only, or GNNs only) §1.
• Superseded by: not known from content on this wiki.