Learning-Based Approaches for Graph Problems: A Survey

Kai Siong Yow, Siqiang LuoarXiv 2022 · DOI · arXiv

Abstract

Traditionally, solving NP-hard graph problems like subgraph isomorphism and community detection has relied on computationally expensive exhaustive search algorithms. This survey examines the recent shift toward machine learning-based methodologies, specifically Graph Neural Networks (GNNs) and Reinforcement Learning (RL). These approaches offer significant advancements in efficiency, often achieving speedups of up to 1,000x, while maintaining high accuracy and scalability for massive real-world networks.

Introduction

Extracting meaningful patterns from graphs is a fundamental task in modern data science, with applications ranging from drug discovery and chemical analysis to social network monitoring and fraud detection. However, many of these tasks—such as finding a specific query graph within a larger network—are computationally "hard" (NP-complete or NP-hard).

Classical algorithms typically utilize backtracking and enumeration. While effective for small-scale data, these methods struggle to scale as networks grow to millions of nodes and edges. The emergence of "learning-based" solutions addresses this bottleneck by using learned representations to approximate answers or by using intelligent agents to guide traditional search processes.

Taxonomy of Learning-Based Methods

The survey categorizes 21 distinct learning models across five primary problem domains: Subgraph Isomorphism Counting, Subgraph Matching, Maximum Common Subgraph, Community Detection, and Community Search.

Taxonomy of learning-based methods for subgraph problems.

As shown in the table above, these models leverage various training paradigms:

  • Graph Neural Networks (GNNs): These are used to generate structural embeddings. Models like DIAMNet and NeurSC predict subgraph counts directly from these vectors, bypassing explicit search.
  • Reinforcement Learning (RL): RL agents, such as those in RL-QVO and McSplit+RL, learn optimal node-visiting sequences to prune search trees effectively.
  • Active and Meta-Learning: These techniques address data scarcity. ALSS uses active learning to identify informative subgraphs for labeling, while CGNP employs meta-learning for few-shot community search.

Problem Definition: Subgraph Matching

A core challenge discussed is Subgraph Matching, where the objective is to identify if a query graph $G_q$ exists within a larger corpus graph $G_c$.

Example of a corpus graph $G_c$ with a highlighted subgraph matching a query structure.

In Figure 2, the blue edges represent a successful match of a query structure within the larger corpus graph $G_c$. Learning-based models like NeuroMatch treat this as an embedding problem: if the embedding of $G_q$ is "contained" within the embedding of a neighborhood in $G_c$, a match is likely. This geometric approach is significantly faster than node-by-node verification.

Key Insights and Performance

The survey highlights several critical breakthroughs:

  1. Representation vs. Search: Shifting from explicit enumeration to vector-space representation allows for near-instantaneous pattern identification.
  2. Heuristic Optimization: RL-based agents can discover search strategies that outperform human-designed "greedy" heuristics, particularly in million-scale graphs.
  3. Theoretical Foundations: The effectiveness of GNNs is linked to their expressiveness, which is theoretically bounded by the Weisfeiler-Lehman (WL) graph isomorphism test.

Empirical results demonstrate the power of these methods. DIAMNet achieved speedups between 10x and 1,000x over the traditional VF2 algorithm. Similarly, NeuroMatch proved to be 100x faster than exact matching algorithms while maintaining superior accuracy over previous approximate techniques.

Limitations and Future Outlook

Despite these successes, several challenges remain:

  • Generalization: Models often struggle when applied to graph topologies significantly different from their training data.
  • Theoretical Guarantees: Unlike classical algorithms, many ML models lack provable approximation ratios.
  • Dynamic Graphs: Most current research focuses on static graphs, whereas real-world data (e.g., social media feeds) is often directed and evolves over time.

The authors conclude that the most promising future direction lies in hybrid systems—combining the speed and intuition of machine learning with the provable correctness of classical algorithmic frameworks.

Summary updated

Abstract

A subgraph is constructed by using a subset of vertices and edges of a given graph. There exist many graph properties that are hereditary for subgraphs. Hence, researchers from different communities have paid a great deal of attention in studying numerous subgraph problems, on top of the ordinary graph problems. Many algorithms are proposed in studying subgraph problems, where one common approach is by extracting the patterns and structures of a given graph. Due to the complex structures of certain types of graphs and to improve overall performances of the existing frameworks, machine learning techniques have recently been employed in dealing with various subgraph problems. In this article, we present a comprehensive review on five well known subgraph problems that have been tackled by using machine learning methods. They are subgraph isomorphism (both counting and matching), maximum common subgraph, community detection and community search problems. We provide an outline of each proposed method, and examine its designs and performances. We also explore non-learning-based algorithms for each problem and a brief discussion is given. We then suggest some promising research directions in this area, hoping that relevant subgraph problems can be tackled by using a similar strategy. Since there is a huge growth in employing machine learning techniques in recent years, we believe that this survey will serve as a good reference point to relevant research communities.
BibTeX
@misc{yow2022learning,
  author = {Kai Siong Yow and Siqiang Luo},
  title = {{Learning-Based Approaches for Graph Problems: A Survey}},
  year = {2022},
  eprint = {2204.01057},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.01057},
}
Figure