Graph Learning: A Survey

In plain words

Many real things are connected: people follow people, proteins bind proteins, papers cite papers, and facts link to other facts. A graph is the standard way to write such data down, as a set of things (nodes) and the links between them. Graph learning means training machine learning models on this kind of data.

This survey sorts the existing approaches into four families. Some treat the values on the nodes as a signal and borrow tools from signal processing. Some factor a table of node similarities into smaller pieces. Some take random walks through the graph and feed the walks to a text-style learner. The last family uses neural networks that pass information along the links. The survey then shows where these methods are used, from text and images to chemistry and knowledge bases, and ends with open problems such as changing graphs, fairness and explaining model decisions.

It is a map of the field, not a test of which method works best. It reports no experiments of its own.

TL;DR

A survey of graph learning with no experiments and no benchmark numbers. It groups methods into graph signal processing, matrix factorization, random walks and deep learning §1.3, then lists applications §3 and open issues §4. Use it to find the family and the cited papers for a graph problem. Do not use it to rank methods, and check the cited originals before relying on any detail.

Problem

Standard machine learning expects inputs on a regular grid or as vectors. Graph data lie in an irregular, non-Euclidean domain, so distances and convolutions do not carry over directly §1, item 1. Real networks are also often heterogeneous, with several vertex and edge types, and simple models that ignore those types lose information §1, item 2. Large social networks with millions of vertices need distributed algorithms §1, item 3. Traditional adjacency-matrix analysis is expensive at this scale, which motivates learning low-dimensional network representations §1.

The survey's stated gap is that earlier surveys each cover only part of the field, usually network embedding or GNNs, and few cover graph signal processing §1.2.

Method

The survey has no method of its own. It is a taxonomy. Section numbers here are arabic: §1 is the Introduction (I), §2 is Section II, §2.1 is II-A, §2.1.1 is II-A1, and so on; §3 is Applications (III) and §4 is Open Issues (IV). This follows the IEEE numbering that the source's document class produces. The compiled PDF was not checked, so the mapping is inferred from the LaTeX source.

Its four families are:

1. Graph signal processing (GSP) §2.1. Values on the vertices are graph signals. Classical tools such as filters, Fourier transforms and sampling are moved onto a graph, using either the adjacency matrix as the shift §2.1.1 or the Laplacian §2.1.1. Covered tasks are sampling and recovery of signals §2.1.2 and learning the topology from data §2.1.3.

2. Matrix factorization §2.2. A matrix of vertex similarities, such as a Laplacian or a proximity matrix, is factorized and the factors serve as embeddings. Covered: Laplacian-based methods, transductive and inductive, such as MDS-style and LPP-style variants §2.2.1, and factorization of proximity matrices, via SVD and related approaches §2.2.2.

3. Random walk based methods §2.3. Random walks turn a graph into node sequences, and a word-embedding model learns vectors from them §2.3.1. Variants add vertex attributes or labels §2.3.2, handle heterogeneous networks with meta-paths or knowledge-graph paths §2.3.3, or follow time-varying networks §2.3.4. The survey also covers GAN-based random-walk generators §2.3.2.

   PseudocodeCopy

   # Random-walk network representation learning  [§2.3.1]
   # Input:  graph; walks per vertex; walk length; embedding dimension
   # Output: one vector per vertex
   
   def random_walk_embedding(graph, walks_per_vertex, length, dim):
       # Generate node sequences with random walks; they act as sentences
       # [§2.3.1]
       walks = []
       for each vertex v, repeated walks_per_vertex times:
           walks.append(random_walk(graph, v, length))
       # Vertices play the role of words; feed the sequences to Word2vec
       # [§2.3.1]
       return word2vec(walks, dim)

   The survey does not give the walk settings for any method; they are inputs to be chosen. Node2vec biases the walk between breadth-first and depth-first moves §2.3.1.

4. Deep learning on graphs §2.4. Graph convolutional networks, with spectral filters §2.4.1 and their spatial variants; graph attention networks §2.4.2; graph auto-encoders, including variational ones §2.4.3; graph generative networks §2.4.4; and spatial-temporal networks §2.4.5. Table 2 tab. 2 lists each method's neural component and application.

Graph-level basics used throughout §2.1.1:

G = (V, E, W)       W is the adjacency matrix
D_ii = d_i          D is diagonal, d_i the degree of vertex i
L = D - W           graph Laplacian
L_norm = D^(-1/2) L D^(-1/2)   normalized Laplacian
s_out = H s_in      a filter H, written as a matrix product

Shift-invariant filters are defined as those that commute with the shift, AH = HA §2.1.1. The survey defines the frequency of a shift through a total variation formula, which is unnumbered in the source §2.1.1:

TV_{G} = \lVert v_k - \tfrac{1}{\lambda_{max}} A v_k \rVert_1

The survey's own categories are not a learning recipe. For each family the survey describes the idea and cites the originals; it gives no training loop, loss or schedule for any of them.

Hyperparameters

Not applicable. The paper runs no experiments and gives no training settings §1.3. The only numeric content is the dataset list in §3.1: Cora, PubMed, BlogCatalog, Wikipedia and PPI. It names them without sizes or splits.

Results

No experimental results. The paper says its contribution is a qualitative overview §1.3. The one summary table, Table 2 tab. 2, maps methods to neural components and application areas and gives no metrics. Table 1 tab. 1 only defines abbreviations.

Applications, as described §3:

• Text §3.2: text classification with GCN, GAT, Text GCN and sentence LSTMs; sequence labeling and semantic role labeling; neural machine translation.
• Images §3.3: social relationship understanding, image classification, visual question answering, and object detection.
• Science §3.4: physical systems (interaction networks §3.4), molecular fingerprints, and protein and biomedical prediction.
• Knowledge graphs §3.5: TransE and extensions, semantic matching models such as RESCAL and DistMult, and GNN-based knowledge base completion.
• Combinatorial optimization §3.6: travelling salesman and graph matching with neural solvers.

Paper vs code

No official code. The paper links only datasets and two third-party libraries in its footnotes: OpenKE and CogDL §3.1. Neither belongs to the authors. A GitHub repository search for "graph learning survey" returned only unrelated third-party lists and paper repositories, none owned by an author. A survey has no method to implement, so there is nothing to compare against code.

Pitfalls

• No ranking. The survey gives no numbers, so coverage says nothing about which method is better §1.3. Check each cited original before choosing one.
• Contradictory definition. The introduction says a graph learning model maps a graph directly to an output without projecting it into a low dimensional space §1.1. The same survey covers network representation learning, which does exactly that §1 §2.3.1.
• Total variation wording. The text says eigenvalues far from the largest give large frequencies, then says total variation tends to be low at larger frequency §2.1.1 fig. 4. The two statements conflict, so read the formula rather than the prose.
• Undefined degree. The paper says d_i is the degree of vertex i, without defining it further §2.1.1. The normalized Laplacian D^(-1/2) L D^(-1/2) needs D to be invertible. Isolated vertices, with zero degree, break it. The paper does not mention this.
• Directed graphs. Laplacian-based sampling and recovery theory covers only undirected graphs, and directed graphs use the adjacency matrix instead §2.1.2.
• Shift-invariance claim. The survey asserts, without a citation, that a shift-invariant filter can always be represented by the shift §2.1.1. The proof is not located in the paper.
• Table 2 is inconsistent. DCRNN, STGCN and ST-GCN each appear twice, once in the time domain group and again in the deep learning group tab. 2. The STGCN repeat has an empty application cell. Two labels look like typos: "SNLCN" and "Aws" tab. 2. Check the original papers before quoting names.
• Unsourced limits. The matrix factorization discussion says the methods need a lot of memory and do not apply to supervised training §2.2.3. No citation is given.
• Open issues conflict with the body. Section 4 says dynamic graph learning has rarely been studied §4. Section 2.3.4 reviews time-varying network embedding methods §2.3.4. The claim is about dynamic graph learning in general, but the wording is loose.
• Ambiguous terms. The text uses "NRL" for both random-walk embedding and spectral GCN methods §2.4.1. Check which is meant before searching.
• Figure credit. Figure 2 is credited to another paper fig. 2. This card reproduces no figure.

Lineage

• Builds on: nothing, as a survey. It positions itself against nine earlier surveys §1.2: Goyal and Ferrara (2018), Cai et al. (2018), Zhang et al. (2018, network representation learning), Nickel et al. (2016), Akoglu et al. (2015), Zhang et al. (2018, deep learning on graphs), Wu et al. (2019), Ortega et al. (2018) and Huang et al. (2018). None is on this wiki.
• Compared against: the same nine surveys §1.2.
• Superseded by: not stated.