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.

  • 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.

  • 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.

  • Takeaways & Limitations

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

  • Takeaways & Limitations

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

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.

  • Graph data represent relationships among entities in social, biological, patent, traffic, citation, and communication networks.
  • Graph learning extracts graph features into vectors that support downstream tasks such as node classification, link prediction, clustering, and recommendation.
  • The survey reviews graph signal processing, matrix factorization, random walk, and deep learning methods for graph learning.
  • Irregular graph domains prevent direct application of methods designed for regularly ordered text, audio, images, or sensor data.
  • Heterogeneous networks contain multiple vertex types and relationships, so simplifying them to direct connections can cause information loss.
  • Distributed algorithms can execute across multiple CPUs or GPUs to reduce running time for large networks.

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.
  • This survey includes graph signal processing, which related NRL and GNN surveys do not cover.
  • C. Contributions and Organization: It reviews state-of-the-art methods, application scenarios, and potential research directions across graph learning.
  • C. Contributions and Organization: The paper classifies mainstream graph learning methods from the perspective of theoretical models and supplies technical descriptions where appropriate.

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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Topology inference distinguishes partially known topology, solved through sampling and recovery, from unknown topology inferred from observed graph signals.

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.
  • Sampling and recovery generally separate into choosing sampling vertices and reconstructing the original signals.
  • Selecting sampling observes a subset of vertices, whereas aggregation sampling uses observations from one vertex through sequential graph shifts.
  • 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.
  • Smoothness-based recovery infers missing low-frequency graph-signal values, while large-scale datasets may require random sampling because matrix decomposition is impractical.
  • 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.

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.
  • 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.
  • 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.
  • Diffusion models infer topology by modeling continuous node influence on neighboring nodes and often assuming independently identically distributed signals.
  • Temporal graph-learning methods model time and space dependencies with autoregressive processes or jointly identify graph filters and input signals.
  • Recommendation can be formulated as partial graph inference, with collaborative filtering viewed as a graph filter on user–item correlation networks.

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.
  • Matrix factorization simplifies graph-characteristic matrices into lower-dimensional components that represent network relationships and support vertex embeddings.
  • The survey distinguishes graph Laplacian matrix factorization from vertex proximity matrix factorization.
  • Graph Laplacian factorization can be transductive, embedding training vertices only, or inductive, embedding vertices outside the training set.
  • Later matrix-factorization models improve locality preservation, capture graph structure through local and global regression, or incorporate auxiliary information.

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.

  • Matrix factorization learns graph structure from non-relational data and is applicable to homogeneous graphs by directly factorizing vertex proximity matrices.
  • SVD and related regularized or low-rank methods approximate vertex proximity in a low-dimensional space by minimizing reconstruction error.
  • Discussion: Matrix factorization requires large memory when the decomposed matrices become large.
  • Discussion: Matrix factorization algorithms are not applicable to supervised or semi-supervised tasks with the training process.
  • Random walks generate node sequences that preserve original network relations and support low-dimensional vertex feature learning for downstream tasks.

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.

  • TADW incorporates vertex text into DeepWalk, while MMDW uses vertex labels in a semi-supervised embedding model.
  • Struc2vec represents nodes with similar local structure, even when they differ in neighborhood and node labels.
  • Sub2Vec and graph2vec extend random-walk-based representation learning from vertices to arbitrary subgraphs and whole graphs.
  • GraphGAN combines generative and discriminative models in a minimax game, using random walks as the generator.
  • Knowledge graphs: PRA uses restart random walks to generate relational features and combines them with logistic regression, but cannot predict links without an existing path.
  • 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.

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.

  • Time-varying network representation learning must account for invalidated old relationships and newly appearing links.
  • CTDNE uses chronological random-walk paths that move forward in time to capture temporal characteristics of continuous-time dynamic networks.
  • GraphSAGE generates embeddings for unseen vertices from locally sampled neighborhood features instead of training an embedding for every vertex.
  • Discussion: Current graph neural methods learn local neighborhood information but cannot directly explore higher-order proximity and community structure.
  • Discussion: Random-walk methods introduce uncertain node relations, requiring more samples that significantly increase algorithmic complexity.

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.

  • Graph neural networks extend neural architectures to graphs by mapping graphs or vertices into an m-dimensional Euclidean space.
  • 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.
  • Space Domain and Spatial Methods: Spatial methods apply graph convolution directly in the graph domain, including vertex ordering, neural fingerprints, adaptive filters, and dynamic graph architectures.
  • Space Domain and Spatial Methods: Dynamic graph convolution can combine graph-convolution expansion with improved LSTM units to learn from graph structure and vertex features.
  • GNNs have attracted substantial attention since 2015 and are widely studied and used across fields.
  • Attention-based GNNs determine neighbor weights through attention, while gated attention networks use self-attention to assign different weights across heads.

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.
  • Graph Auto-Encoders: 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.
  • 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.
  • 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.
  • 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.

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.
  • 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.
  • 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.
  • Science: Science applications also include molecular fingerprints, protein interface prediction, and biomedical engineering.Neural graph fingerprints use GCNs to calculate molecular substructure feature vectors.
  • 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.

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.
  • 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.
  • Future Directions: 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.
  • Future Directions: 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.
  • Future Directions: 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.
  • 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.
Loading 2105.00696v1…