GraDE: A Graph Diffusion Estimator for Frequent Subgraph Discovery in Neural Architectures

Yikang Yang, Zhengxin Yang, Minghao Luo, Luzhou Peng, Hongxiao Li, Wanling Gao, Lei Wang, Jianfeng ZhanarXiv 2026 · DOI

TL;DR

This paper introduces GraDE, a novel framework for discovering frequent subgraph patterns (motifs) in neural architectures. GraDE leverages graph diffusion models to efficiently estimate subgraph typicality, overcoming the computational limitations of traditional methods and significantly improving the accuracy and scalability of motif discovery, especially for larger subgraphs.

What Problem Does This Paper Address?

Finding recurring subgraph patterns, or "network motifs," in neural architectures is crucial for understanding, optimizing, and designing them. However, this task is notoriously challenging due to a fundamental trade-off: enumeration-based methods are accurate but computationally prohibitive for larger subgraphs, while sampling-based methods are faster but suffer from a sharp decline in discovery capability as subgraph size increases. This is because the exponentially growing search space leads to sparse and unrepresentative samples, making it difficult to identify truly frequent patterns. GraDE aims to bridge this gap by providing a computationally feasible and highly accurate approach to frequent subgraph discovery.

Methods

GraDE's core innovation is the Graph Diffusion Estimator (GraDE), which repurposes graph diffusion models for subgraph frequency estimation. Instead of directly counting subgraphs, GraDE uses a trained diffusion model to assign a "typicality score" to any given subgraph. This score is derived from the model's learned distribution of valid subgraphs and serves as a reliable surrogate for subgraph frequency.

The framework operates in three stages:

  1. Subgraph Sampling: A representative subset of subgraphs is collected from the target architecture distribution. This is a pluggable component, allowing for various established sampling algorithms (e.g., Rand-ESU, Rand-FaSE, NRS).
  2. Estimator Construction: A graph diffusion model (specifically, a variant of DisCo) is trained on the sampled subgraphs to learn their underlying structural distribution. This trained model becomes the GraDE estimator.
  3. Beam Search: A beam search strategy is employed to discover frequent subgraphs. It iteratively expands candidate subgraphs and uses the GraDE estimator to score their typicality, pruning less promising candidates and efficiently exploring the search space. This approach replaces expensive subgraph counting with fast model inference.

Datasets

The paper evaluates GraDE on a combination of synthesized and real-world datasets:

  • Synthesized Datasets:
    • NAS-Bench-101
    • NAS-Bench-201
    • NAS-Bench-301
  • Real-world Dataset:
    • Younger (a newly introduced dataset of neural architectures)
    • NAS-Bench-NLP

Key Insights and Ideas

  • Diffusion Models as Frequency Surrogates: The most significant insight is that the generative probability assigned by a graph diffusion model to a subgraph can effectively serve as a proxy for its frequency. This is because these models learn the underlying distribution of "typical" or "valid" subgraphs.
  • Bridging Accuracy and Scalability: GraDE successfully navigates the accuracy-scalability trade-off by combining the representational power of diffusion models with an efficient beam search strategy. This allows for the discovery of large-scale frequent patterns that are intractable for traditional methods.
  • Robustness to Sparse Sampling: The GraDE estimator performs well even with sparse sampling densities (as low as 0.1), a critical advantage given the exponential growth of the subgraph search space. This means it can achieve high accuracy without requiring an overwhelming number of samples.
  • Modular Design: The sampling module is pluggable, allowing GraDE to benefit from various existing subgraph sampling algorithms.

Key Results

  • Superior Ranking Accuracy: GraDE achieves significantly higher ranking accuracy compared to sampling-based baselines, with Spearman's rank correlation coefficient improving by up to 114% on synthesized datasets and 33% on the real-world Younger dataset.
  • Discovering Large-Scale Frequent Patterns: The framework successfully discovers large-scale frequent patterns, achieving up to 30× higher median frequency than sampling-based methods for larger subgraphs (k ≥ 10).
  • Computational Efficiency: GraDE is computationally feasible, especially compared to exact enumeration, which becomes prohibitive for larger subgraphs. The runtime analysis shows that while sampling time increases with subgraph size, training and search costs grow modestly.
  • Robustness: The performance of GraDE is stable across different sampling methods, demonstrating its robustness.

Limitations and Future Work

  • Computational Cost of Sampling: While GraDE significantly mitigates computational costs, the subgraph sampling step can still become expensive for very large subgraph sizes.
  • Future Work: The authors suggest extending GraDE to more diverse graph domains. They also highlight the potential for integrating domain-specific constraints into the search process, which can further enhance efficiency and guide the discovery towards relevant structures. The case study on Younger demonstrates how discovered patterns can be directly translated into practical building blocks for neural network design.

Summary updated

Abstract

Finding frequently occurring subgraph patterns or network motifs in neural architectures is crucial for optimizing efficiency, accelerating design, and uncovering structural insights. However, as the subgraph size increases, enumeration-based methods are perfectly accurate but computationally prohibitive, while sampling-based methods are computationally tractable but suffer from a severe decline in discovery capability. To address these challenges, this paper proposes GraDE, a diffusion-guided search framework that ensures both computational feasibility and discovery capability. The key innovation is the Graph Diffusion Estimator (GraDE), which is the first to introduce graph diffusion models to identify frequent subgraphs by scoring their typicality within the learned distribution. Comprehensive experiments demonstrate that the estimator achieves superior ranking accuracy, with up to 114\% improvement compared to sampling-based baselines. Benefiting from this, the proposed framework successfully discovers large-scale frequent patterns, achieving up to 30$\times$ higher median frequency than sampling-based methods.
BibTeX
@misc{yang2026grade,
  author = {Yikang Yang and Zhengxin Yang and Minghao Luo and Luzhou Peng and Hongxiao Li and Wanling Gao and Lei Wang and Jianfeng Zhan},
  title = {{GraDE: A Graph Diffusion Estimator for Frequent Subgraph Discovery in Neural Architectures}},
  year = {2026},
  eprint = {2602.03257},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.03257},
}
Figure