Abstract
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.
Introduction: The Non-Euclidean Frontier
Traditional machine learning is typically designed for data that resides in Euclidean space, such as the regular grids of pixels in an image or the linear sequences of words in a sentence. However, much of the world's most complex and interesting data is connected in irregular, non-Euclidean structures known as graphs or networks. Examples include social media friendships, protein-protein interactions, and global traffic flows.
These structures are often massive and frequently heterogeneous, containing various types of nodes and edges. The primary challenge in graph learning is developing methods that can effectively extract features from these irregular relationships for tasks such as node classification, link prediction, and graph visualization.
Methodological Taxonomy
This survey categorizes the landscape of graph learning into four foundational methodological pillars, each providing a different lens through which to analyze networked data.
- Graph Signal Processing (GSP): This approach treats values on nodes as "signals" and extends classical signal processing concepts, like the Fourier Transform, to graphs. It focuses on sampling, recovery, and topology learning—the process of inferring the graph structure itself from observed data.
- Matrix Factorization: A classical technique that simplifies high-dimensional adjacency or Laplacian matrices into low-dimensional embeddings. Methods like Singular Value Decomposition (SVD) are employed to preserve vertex proximity within a latent space.
- Random Walk Based Methods: Algorithms such as DeepWalk and Node2vec treat a graph as a collection of "sentences" by performing random walks across nodes. By applying natural language processing (NLP) techniques like Word2vec to these sequences, they learn embeddings that capture local neighborhood structures.
- Deep Learning on Graphs: The most modern category, encompassing Graph Convolutional Networks (GCNs), which generalize convolutions to irregular domains; Graph Attention Networks (GATs), which learn to weigh the importance of different neighbors; and Graph Auto-encoders (GAEs) for unsupervised representation learning.
Key Insights and Evolution
A significant trend in the field is the shift from spectral methods (based on the graph's Eigen-decomposition), which are computationally expensive, to spatial methods that aggregate information from local neighborhoods. These spatial approaches are far more scalable for real-world applications.
Another key insight is that topology is not always given. In many cases, researchers have the data (signals) but not the underlying graph; "topology learning" is the critical task of discovering these hidden relationships. Furthermore, the introduction of attention mechanisms (as seen in GATs) allows models to ignore noisy connections and focus on the most relevant neighboring nodes for a specific task.
Applications and Results
Graph learning has demonstrated state-of-the-art performance across several domains:
- Text & Images: Graph methods outperform traditional techniques by explicitly modeling context and social relationships.
- Traffic & Science: In traffic forecasting, Spatio-Temporal Graph Networks capture both the physical road network and the temporal flow of vehicles.
- Combinatorial Optimization: Graph Neural Networks (GNNs) are increasingly used to solve NP-hard problems like the Traveling Salesman Problem (TSP) more efficiently than traditional heuristics.
Future Directions
The authors identify several critical open issues for future research:
- Dynamic Graph Learning: Moving beyond static graphs to models that can handle evolving networks in real-time.
- Generative Models: Improving the ability to generate realistic new graphs, which is vital for fields like drug discovery.
- Fairness and Interpretability: Ensuring algorithms do not reinforce inherent biases and making "black box" GNN models more transparent for high-stakes decision-making.
Summary updated