Source-linked AI summary
A Survey on Graph Structure Learning: Progress and Opportunities
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du, Jieyu Zhang, Qiang Liu, Carl Yang, Shu Wu
TL;DR
GNNs depend on graph structures that are often incomplete, noisy, or otherwise inadequate for reliable representation learning and system understanding. This survey organizes Graph Structure Learning around jointly optimizing graph structures and representations, presents a general pipeline and three method categories, and reviews applications and open challenges. Its synthesis highlights unresolved issues involving heterogeneous graphs, heterophily, sparse attributes, scalability, and limited supervision.
Problem
GNNs are sensitive to incomplete, noisy, or task-inadequate graph structures, while existing GSL techniques had not been systematically reviewed across research communities.
Method
The survey formulates a general GSL pipeline, categorizes methods as metric-based, neural, or direct, and reviews applications and future directions.
Results
The survey synthesizes recent GSL progress across structure-modeling approaches, applications, common techniques, challenges, and research directions.
Takeaways & Limitations
GSL provides a framework for studying jointly learned graph structures and representations while connecting methods across domains and research communities.
Takeaways & Limitations
Current GSL work remains limited for heterogeneous and heterophilous graphs, sparse attributes, large-scale data, and settings with limited supervision.
Abstract
from arXiv · showhide
Graphs are widely used to describe real-world objects and their interactions. Graph Neural Networks (GNNs) as a de facto model for analyzing graphstructured data, are highly sensitive to the quality of the given graph structures. Therefore, noisy or incomplete graphs often lead to unsatisfactory representations and prevent us from fully understanding the mechanism underlying the system. In pursuit of an optimal graph structure for downstream tasks, recent studies have sparked an effort around the central theme of Graph Structure Learning (GSL), which aims to jointly learn an optimized graph structure and corresponding graph representations. In the presented survey, we broadly review recent progress in GSL methods. Specifically, we first formulate a general pipeline of GSL and review state-of-the-art methods classified by the way of modeling graph structures, followed by applications of GSL across domains. Finally, we point out some issues in current studies and discuss future directions.
1 Introduction
GNNs exploit graph structure and attributes but are vulnerable to incomplete, noisy, and adversarially perturbed graphs. Graph Structure Learning addresses these issues by jointly learning optimized structures and representations, while supporting interpretability and system understanding across domains.
- Incomplete, noisy, or adversarially perturbed graph structures can produce unreliable GNN predictions and representations.
- GNNs aggregate neighborhood information recursively, so small structural noise can propagate and degrade representations across many nodes.
- GSL can help uncover important subgraphs or features underlying GNN predictions, especially in safety-critical applications such as healthcare.
- GSL jointly learns an optimized graph structure and its corresponding representations for downstream tasks.
- The survey formulates a general GSL pipeline, reviews graph-structure modeling approaches, discusses applications, and outlines future research directions.
2 Preliminaries
GSL seeks optimized adjacency matrices and graph representations through trainable structure learners and GNN encoders. Its pipeline constructs or receives a graph, models and refines connectivity, propagates information, and iterates these stages while categorizing structure learners into metric-based, neural, and direct approaches.
- 2.1 Problem Formulation: GSL simultaneously learns an optimized adjacency matrix A⋆ and graph representations Z⋆ for downstream tasks.
- 2.1 Problem Formulation: A typical GSL model combines a GNN encoder for embeddings with a structure learner that models edge connectivity.
- 2.2 Graph Structure Learning Pipeline: Most GSL models use three stages: graph construction, graph structure modeling, and message propagation.
- 2.2 Graph Structure Learning Pipeline: Metric-based methods derive edge weights from pairwise embedding metrics, neural methods infer them with expressive networks, and direct methods optimize adjacency entries directly.
- 2.2 Graph Structure Learning Pipeline: After structure modeling, a GNN propagates features over the optimized adjacency matrix to produce refined node embeddings.
- 2.2 Graph Structure Learning Pipeline: Structure modeling and message propagation are commonly repeated because the resulting representations help refine edge weights iteratively.
3 Graph Regularization
Graph regularization encodes desired properties of learned graphs, including sparsity, smoothness, connectivity, and community preservation. These constraints guide structure learning but can have limited control or computationally difficult objectives.
- Sparsity: Sparsity regularization discourages noisy, task-irrelevant edges by penalizing nonzero adjacency entries.The ℓ0-norm directly counts nonzero elements, but ℓ1-norm and continuous relaxations are used because ℓ0 minimization is generally NP-hard.
- Smoothness: Smoothness regularization favors graphs where node-feature signals change gradually across adjacent nodes.The associated Laplacian objective penalizes edges connecting distant feature rows and can yield sparse edge sets.
- Connectivity: Connectivity regularization uses a logarithmic barrier to keep node degrees positive.Its coefficient scales the solution but does not directly control individual-edge sparsity, so it is combined with sparsity regularizers when that control is needed.
- Community Preservation: Community preservation uses low-rank regularization to remove potentially noisy cross-community edges and preserve densely connected components.Because rank minimization is hard, the nuclear norm is commonly optimized as a tractable surrogate.
4 Graph Structure Modeling
Graph structure modeling methods learn an intermediate graph through metric-based, neural, or direct approaches, followed by optional postprocessing. These categories differ in how they parameterize edge connections and optimize the adjacency structure.
- Overview: GSL methods are organized into three structure-modeling categories that obtain an intermediate graph optimized for downstream tasks.Postprocessing can then produce the final learned graph structure.
- Metric-based Approaches: Metric-based approaches compute edge weights from similarities between node features or embeddings.Kernel functions support end-to-end training, while examples use Gaussian, inner-product, cosine, diffusion, or multiple kernels.
- Neural Approaches: Neural approaches use parameterized networks to model edge weights from node features and representations.Attention-based variants assign coefficients to neighboring nodes, dynamically amplifying or attenuating existing connections into a learned adjacency matrix.
- Neural Approaches: Transformer-like graph models propagate messages between all nodes and treat the given graph as a soft inductive bias.This full-attention design provides flexibility to discover new relations beyond local neighborhoods.
- Direct Approaches: Direct approaches optimize adjacency entries as free variables alongside GNN parameters, offering flexibility without relying on node representations.They commonly use graph regularizers, explanation losses, bilevel optimization, or probabilistic edge models, but adjacency optimization can be difficult.
5 Applications
GSL is applied across domains where graphs are incomplete, imperfect, artificial, or constructed from limited structural assumptions. Applications include language, vision and medical imaging, and scientific discovery.
- Scope: Across real-world applications, GSL is relevant when the available graph structure is incomplete or imperfect.The survey reviews such applications across multiple domains rather than treating graph construction and graph generation as identical problems.
- Natural language processing: In natural language processing, GSL constructs word graphs from semantic and syntactic patterns to obtain fine-grained linguistic representations.Applications include query-document matching and relation extraction.
- Computer vision and medical imaging: In computer vision and medical imaging, GSL recovers or constructs useful topologies for few-shot learning, point-cloud analysis, and imaging data.These learned structures support classification, segmentation, and scene-graph-related tasks.
- Scientific discovery: In scientific discovery, GSL addresses artificial graph structures used to represent biological and chemical interactions.Examples include recovering long-range protein contacts and weighting molecular skeletons to optimize compound properties.
6 Challenges and Future Directions
Current GSL research remains constrained by graph diversity, attribute availability, computational cost, and reliance on task-relevant supervision. Future work targets heterogeneous and heterophilous graphs, sparse-feature settings, scalable methods, and principled self-supervised learning.
- Beyond homogeneity: Most existing GSL studies focus on homogeneous graphs, leaving structure learning for heterogeneous graphs with complex node and edge relations largely open.
- Beyond homophily: Similarity-based edge modeling assumes homophily, but many real-world graphs, including chemical and molecular graphs, exhibit strong heterophily.Further progress is needed on strategies for learning heterophilous graph structures.
- Learning structures in absence of rich attributes: Existing methods commonly depend on rich node attributes, so their performance may degrade on benchmarks with sparse or absent features.Sequential recommendation is cited as a setting where only user-item interactions may be available.
- Increasing scalability: Pairwise node-embedding similarity creates high computational complexity that hinders applying GSL methods to large-scale datasets.Increasing scalability is identified as a direction for further research.
- Towards task-agnostic structure learning: Most GSL work requires task-relevant supervision, while limited high-quality labels can deteriorate the quality of learned graph structures.Self-supervised methods such as SLAPS and SUBLIME have been explored, but their relation to GSL objectives still lacks principled understanding.
7 Concluding Remarks
The survey reviews GSL concepts, methods, applications, and challenges to organize existing research. It aims to deepen understanding of GSL and guide future algorithm development.
- The survey formulates a general GSL pipeline and categorizes methods into metric-based, neural, and direct approaches.It also summarizes structure-modeling techniques and discusses applications across domains.
- The survey outlines current challenges and future research directions intended to expand understanding and guide GSL algorithm development.