PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Learning: A Survey

Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, Huan Liu

arXiv:2105.00696v1cs.LGcs.AIcs.SI

TL;DR

Graph learning addresses machine learning on graph data, whose irregular and heterogeneous structure challenges conventional methods. This survey systematically reviews four categories of graph learning methods, their applications, and future directions. It provides a comprehensive overview spanning graph signal processing, matrix factorization, random walks, and deep learning.

  • Problem

    Graph data have irregular, heterogeneous structures that challenge conventional machine learning, while existing surveys do not provide a comprehensive overview of graph learning.

    Source: A. What is Graph Learning? · p. 2, B. Related Surveys · p. 3

  • Method

    The survey organizes graph learning methods into graph signal processing, matrix factorization, random walk, and deep learning categories and reviews their models, algorithms, applications, and research directions.

    Source: A. What is Graph Learning? · p. 1, §V · p. 15

  • Results

    The survey presents a comprehensive review of state-of-the-art graph learning methods and outlines applications in text, images, science, knowledge graphs, and combinatorial optimization.

    Source: C. Contributions and Organization · p. 3, §V · p. 15

  • Takeaways & Limitations

    Graph learning methods extract graph features for downstream tasks including node classification and link prediction, with applications across multiple domains.

    Source: §V · p. 15

    Graph signal processing methods have strict experimental-data requirements, require the whole graph as input, and have relatively poor scalability.

    Source: 4) Discussion · p. 7

Abstract

from arXiv · show

Graphs are widely used as a popular representation of the network structure of connected data. Graph data can be found in a broad spectrum of application domains such as social systems, ecosystems, biological networks, knowledge graphs, and information systems. With the continuous penetration of artificial intelligence technologies, graph learning (i.e., machine learning on graphs) is gaining attention from both researchers and practitioners. Graph learning proves effective for many tasks, such as classification, link prediction, and matching. Generally, graph learning methods extract relevant features of graphs by taking advantage of machine learning algorithms. In this survey, we present a comprehensive overview on the state-of-the-art of graph learning. Special attention is paid to four categories of existing graph learning methods, including graph signal processing, matrix factorization, random walk, and deep learning. Major models and algorithms under these categories are reviewed respectively. We examine graph learning applications in areas such as text, images, science, knowledge graphs, and combinatorial optimization. In addition, we discuss several promising research directions in this field.

IMPACT STATEMENT

Graph learning applies machine learning to graph-structured data, whose irregular, heterogeneous, and large-scale nature challenges conventional methods. This survey organizes graph learning approaches into four categories and reviews their applications and research directions.

B. Related Surveys

Existing surveys cover only parts of graph learning, whereas this survey provides a comprehensive overview organized around four theoretical categories. It also includes technical descriptions, applications, and future research directions.

  • Prior surveys mainly cover network embedding, deep learning-based representation, or selected graph-learning components rather than graph learning comprehensively.Source: B. Related Surveys · p. 3
  • This survey includes graph signal processing, which related NRL and GNN surveys do not cover.Source: B. Related Surveys · p. 3

C. Contributions and Organization

II. GRAPH LEARNING MODELS AND ALGORITHMS

The survey organizes graph learning models into four categories and introduces graph signal processing as a framework for analyzing signals on irregular graph domains. GSP represents graph signals and uses matrix-based shifts, spectral transforms, and frequency notions to extract implicit graph information.

  • The survey reviews graph learning through GSP, matrix factorization, random walks, and deep learning.Source: §II · pp. 3–4
  • GSP extends signal-processing concepts such as Fourier transforms and filtering to irregular graph domains.Graph signals assign values to vertices, enabling analysis of connectivity and similarity.Source: A. Graph Signal Processing · p. 4
  • GSP uses adjacency matrices or graph Laplacians as shifts that define graph filters and signal transformations.Adjacency-based methods use A, while Laplacian-based methods use L.Source: 1) Representation on Graphs · p. 4
  • Eigenvalue decomposition supplies graph Fourier representations, with eigenvectors forming the basis and the inverse eigenvector matrix providing the Fourier transform.The shift is decomposed as A = VΛV^-1, and F = V^-1.Source: 1) Representation on Graphs · p. 5
  • GSP frequency measures signal variation after shift filtering, while eigenvectors associated with different eigenvalues capture different graph-signal characteristics.The survey relates frequency to total variation and describes filtering with eigenvectors.Source: 1) Representation on Graphs · p. 5
  • Topology inference distinguishes partially known topology, solved through sampling and recovery, from unknown topology inferred from observed graph signals.Source: 1) Representation on Graphs · p. 5

2) Sampling and Recovery:

Graph sampling and recovery adapt classical signal-processing ideas to irregular graph domains. They select or aggregate observations and reconstruct missing or original graph signals using signal models, smoothness, interpolation, and iterative estimation.

  • Graph sampling reconstructs signals from observations collected on a subset of vertices.The problem is important when real-world graph data are large and sampling all vertices is costly.Source: 2) Sampling and Recovery · p. 5
  • Sampling and recovery generally separate into choosing sampling vertices and reconstructing the original signals.Source: 2) Sampling and Recovery · pp. 5–6
  • Selecting sampling observes a subset of vertices, whereas aggregation sampling uses observations from one vertex through sequential graph shifts.Source: 2) Sampling and Recovery · p. 6
  • Recovery methods include interpolation, least-squares reconstruction, Gaussian random-field inference, distributed tracking, and adaptive online estimation.Some methods handle time-varying signals or changing observation subsets.Source: 2) Sampling and Recovery · p. 6
  • Smoothness-based recovery infers missing low-frequency graph-signal values, while large-scale datasets may require random sampling because matrix decomposition is impractical.Source: 2) Sampling and Recovery · p. 6
  • Graph sampling methods address smooth, piece-wise constant, piece-wise smooth, and sparse graph signals.Different reconstruction schemes have been studied for different signal structures and injection patterns.Source: 2) Sampling and Recovery · p. 6

3) Learning Topology Structure from Data:

Topology learning estimates graph structure from data by using assumptions about signal generation and graph properties. The survey covers smoothness-constrained learning, GMRF precision estimation, diffusion models, temporal networks, and recommendation-oriented graph recovery.

  • Graph topology learning estimates graph Laplacians or graph structures from datasets, commonly under sparsity and smoothness assumptions.Smoothness constrains observed signals and provides a rationale for graph-signal modeling.Source: 3) Learning Topology Structure from Data · p. 6
  • GMRF-based methods learn graph topology by selecting graphs likely to generate signals resembling the observed signals.Several formulations treat the graph Laplacian as a precision matrix and optimize it under Laplacian constraints.Source: 3) Learning Topology Structure from Data · p. 6
  • A two-step GMRF framework first infers a topology and then estimates a generalized graph Laplacian with an error bound.The estimated matrix can be adjusted to satisfy requirements of different problems.Source: 3) Learning Topology Structure from Data · p. 6
  • Diffusion models infer topology by modeling continuous node influence on neighboring nodes and often assuming independently identically distributed signals.Source: 3) Learning Topology Structure from Data · p. 7
  • Temporal graph-learning methods model time and space dependencies with autoregressive processes or jointly identify graph filters and input signals.Source: 3) Learning Topology Structure from Data · p. 7
  • Recommendation can be formulated as partial graph inference, with collaborative filtering viewed as a graph filter on user–item correlation networks.Source: 3) Learning Topology Structure from Data · p. 7

4) Discussion:

The discussion contrasts graph signal processing with matrix factorization as graph-learning approaches. It highlights GSP’s limited scalability and describes matrix factorization as a lower-dimensional representation strategy with transductive, inductive, and enhanced variants.

  • GSP has strict experimental-data requirements, needs the whole graph as input, and has relatively poor scalability.These limitations contribute to fewer real-world applications and potentially high computational complexity.Source: 4) Discussion · p. 7
  • Matrix factorization simplifies graph-characteristic matrices into lower-dimensional components that represent network relationships and support vertex embeddings.Source: B. Matrix Factorization Based Methods · p. 7
  • The survey distinguishes graph Laplacian matrix factorization from vertex proximity matrix factorization.Source: B. Matrix Factorization Based Methods · p. 7
  • Graph Laplacian factorization can be transductive, embedding training vertices only, or inductive, embedding vertices outside the training set.Source: 1) Graph Laplacian Matrix Factorization · p. 7
  • Later matrix-factorization models improve locality preservation, capture graph structure through local and global regression, or incorporate auxiliary information.Source: 1) Graph Laplacian Matrix Factorization · p. 7

2) Vertex Proximity Matrix Factorization:

Vertex proximity matrix factorization learns low-dimensional representations by decomposing proximity information, but it can require substantial memory and does not support supervised or semi-supervised training directly.

Discussion

  • Matrix factorization requires large memory when the decomposed matrices become large.Source: 3) Discussion · pp. 7–8
  • Matrix factorization algorithms are not applicable to supervised or semi-supervised tasks with the training process.Source: 3) Discussion · p. 8
  • Random walks generate node sequences that preserve original network relations and support low-dimensional vertex feature learning for downstream tasks.Source: C. Random Walk Based Methods · p. 8

2) Structure and Vertex Information Based Random Walks:

Random-walk methods extend network representation learning beyond topology by incorporating vertex information, structural identity, heterogeneous relations, and relational paths. These approaches include neural, semi-supervised, generative, and path-based models.

Knowledge graphs

Heterogeneous social networks

  • HIN2Vec embeds heterogeneous-network meta-paths with a neural representation-learning framework, whereas JUST uses jump-and-stay random walks without requiring optimal meta-path selection.Source: 3) Random Walks in Heterogeneous… · pp. 9–10

4) Random Walks in Time-varying Networks:

Time-varying network representation learning incorporates temporal dynamics so embeddings can reflect changing relationships and support unseen vertices. However, graph neural methods may remain limited to local information.

Discussion

  • Current graph neural methods learn local neighborhood information but cannot directly explore higher-order proximity and community structure.Source: 4) Random Walks in Time-varying Networks · p. 10
  • Random-walk methods introduce uncertain node relations, requiring more samples that significantly increase algorithmic complexity.Source: 5) Discussion · p. 10

D. Deep Learning on Graphs

Deep learning on graphs adapts convolutional and attention-based architectures to irregular graph domains through spectral and spatial approaches. The surveyed models address static, dynamic, vertex, and graph-level learning tasks.

Time Domain and Spectral Methods

  • Spectral graph CNNs use the graph Laplacian to generalize image-style convolution, with later methods reducing parameters through polynomial and Chebyshev approximations.Source: 1) Graph Convolutional Networks · p. 10

Space Domain and Spatial Methods

3) Graph Auto-Encoders:

Graph auto-encoders use GNN-based encoders and decoders to learn low-dimensional vertex representations by reconstructing neighborhood or structural information. Related graph-learning research also addresses graph generation, spatial-temporal dependence, and optimization challenges.

Graph Auto-Encoders

  • Graph auto-encoders embed network vertices into low-dimensional vectors using GNN structures.Encoders may use multilayer perceptrons or GCNs, while decoders reconstruct neighborhood statistics.Source: 3) Graph Auto-Encoders · p. 11
  • DNGR and SDNE learn embeddings from structural features, whereas DRNE can combine topology structure with content features.SDNE preserves first-order and second-order proximity through a stacked auto-encoder; DNGR employs PPMI.Source: 3) Graph Auto-Encoders · p. 11

Graph Generative Networks

  • Graph generative networks generate vertices and edges or other graph structures from observed graphs for domain-specific applications.Examples include generating semantic or knowledge graphs from sentences.Source: 4) Graph Generative Networks · p. 11

Graph Spatial-Temporal Networks

  • Graph spatial-temporal networks capture both global spatial structure and time-varying vertex inputs.In traffic networks, sensors provide continuously changing traffic speeds and edges reflect sensor-pair distances.Source: 5) Graph Spatial-Temporal Networks · p. 12

Discussion

  • Deep-learning-based graph learning optimizes objectives with gradient descent but may encounter local optima and vanishing gradients.These optimization issues can affect the performance of deep neural network representation-learning models.Source: 6) Discussion · p. 12

B. Text

The survey describes graph learning applications across text, images, science, and knowledge graphs. These applications use graph structure and learned representations for classification, reasoning, prediction, and other domain tasks.

Text

  • Textual data support graph-learning applications including text classification, sequence labeling, and sentiment classification.The survey motivates graph methods for textual sources such as web pages, emails, documents, books, and patents.Source: B. Text · p. 12

Images

  • Image-related applications include social relationship understanding, image classification, visual question answering, object detection, region classification, and semantic segmentation.Graph reasoning models use GGNNs to learn propagation mechanisms for social relationship understanding.Source: C. Images · pp. 12–13

Science

  • Graph learning models physical systems by representing objects as vertices and relations as edges, enabling prediction of physical dynamics.Interaction networks take objects and relationships as input, while visual interaction networks predict from pixels after learning object state codes.Source: D. Science · pp. 13–14
  • Science applications also include molecular fingerprints, protein interface prediction, and biomedical engineering.Neural graph fingerprints use GCNs to calculate molecular substructure feature vectors.Source: D. Science · p. 14

Knowledge Graphs

  • Knowledge-graph learning includes out-of-knowledge-base entity handling and embedding-based plausibility assessment.Translational distance models use relation-based translations, while semantic matching models compare latent entity and relation semantics.Source: E. Knowledge Graphs · p. 14

F. Combinatorial Optimization

Graph learning has been applied to combinatorial optimization problems such as TSP and MST, while the survey identifies dynamic, generative, fair, and interpretable graph learning as open directions. The conclusion frames the field as rapidly expanding across methods and applications.

Combinatorial Optimization

  • Deep neural networks, including GNN-based methods, have been applied to classical combinatorial problems such as TSP and MST.One TSP approach combines a parameterized reward pointer network with a strategy-gradient training module.Source: F. Combinatorial Optimization · p. 14

Future Directions

  • Dynamic graph learning remains an open direction because many existing algorithms target static networks, whereas networks such as traffic systems vary over time.The survey calls for methods that maintain good performance on dynamic graphs.Source: §IV · p. 14
  • Generative graph learning can combine generative and discriminative modeling for link prediction, network evolution, and recommendation.The approach alternates and iterates between the two model types through a game-theoretical min-max formulation.Source: §IV · p. 14
  • Fair graph learning is needed because learned vectors may capture sensitive information and reinforce network bias.The survey proposes integrating fair metrics into graph-learning algorithms to address inherent bias.Source: §IV · p. 14
  • Graph-learning interpretability remains unresolved because models jointly incorporate graph structure and feature information in complex, black-box architectures.The survey highlights uncertainty about how drug discoveries are produced and why particular discoveries arise.Source: §IV · p. 14

Conclusion

  • The survey reviews graph signal processing, matrix factorization, random walk, and deep learning methods alongside applications in text, images, science, knowledge graphs, and combinatorial optimization.It also discusses future research directions and positions graph learning as a rapidly growing area.Source: §V · p. 15

Related papers

Loading 2105.00696v1…