MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts

Junda Ye, Zhongbao Zhang, Li Sun, Siqiang LuoarXiv 2025 · arXiv · OpenReview

Abstract

While graph neural networks (GNNs) have achieved great success in learning from graph-structured data, their reliance on local, pairwise message passing restricts their ability to capture complex, high-order subgraph patterns, leading to insufficient structural expressiveness. Recent efforts have attempted to enhance structural expressiveness by integrating random walk kernels into GNNs. However, these methods are inherently designed for graph-level tasks, which limits their applicability to other downstream tasks such as node classification. Moreover, their fixed kernel configurations hinder the model's flexibility in capturing diverse subgraph structures. To address these limitations, this paper proposes a novel Mixture of Subgraph Experts (MoSE) framework for flexible and expressive subgraph-based representation learning across diverse graph tasks. Specifically, MoSE extracts informative subgraphs via anonymous walks and dynamically routes them to specialized experts based on structural semantics, enabling the model to capture diverse subgraph patterns with improved flexibility and interpretability. We further provide a theoretical analysis of MoSE's expressivity within the Subgraph Weisfeiler-Lehman (SWL) Test, proving that it is more powerful than SWL. Extensive experiments, together with visualizations of learned subgraph experts, demonstrate that MoSE not only outperforms competitive baselines but also provides interpretable insights into structural patterns learned by the model.

Introduction

Most modern Graph Neural Networks (GNNs) rely on Message Passing (MPNNs), where nodes update their states by aggregating information from immediate neighbors. While effective, this approach has a fundamental theoretical limit: it cannot distinguish certain non-isomorphic graphs (the 1-WL limit). Specifically, MPNNs struggle to "see" higher-order structures like triangles, cliques, or complex cycles.

To address this, researchers have explored Random Walk Kernels (RWK), which compare input graphs to a set of "hidden" template graphs. However, these methods are often computationally expensive, rigid in their use of fixed-size templates, and primarily limited to graph-level classification. MoSE (Mixture of Subgraph Experts) overcomes these hurdles by treating subgraph pattern recognition as a dynamic routing problem.

Methodology

The MoSE framework introduces a flexible architecture designed to identify complex structural motifs efficiently. The process consists of three core components:

  1. Anonymous Walk Subgraph Extraction: Instead of simple neighborhood aggregation, MoSE uses anonymous walks—paths that ignore specific node IDs to focus purely on the shape of the walk. This allows the model to reconstruct local ego-graphs and capture frequent structural motifs more effectively.
  2. Subgraph-aware Gating Network: Acting as a "router," this network analyzes the topology of the extracted local subgraph and dynamically assigns it to the most relevant experts. Unlike standard Mixture of Experts (MoE) routers, this mechanism is specifically topology-aware.
  3. Mixture of Subgraph Experts: The model maintains $K$ different experts, each specializing in "hidden graphs" of different sizes. A differentiable version of the Random Walk Kernel allows these experts to learn structural "probes" through standard backpropagation.
The MoSE framework architecture, illustrating the flow from input graph to downstream task classification.

Theoretical analysis confirms that MoSE is more expressive than the Subgraph Weisfeiler-Lehman (SWL) Test, placing it high on the hierarchy of graph learning power.

Experimental Evaluation

MoSE was evaluated on a comprehensive suite of 19 datasets, including real-world bio/chem datasets (MUTAG, D&D, NCI1), social networks (IMDB, REDDIT), and both homophilic and heterophilic node classification networks.

As shown in the performance comparison below, MoSE consistently outperforms or matches state-of-the-art baselines across various benchmarks. For instance, it achieved a top accuracy of 62.5% on the ENZYMES dataset and 92.1% on REDDIT-BINARY.

Performance comparison of MoSE against state-of-the-art Graph Kernels (GK), MPNNs, and GK-based Neural Networks.

Beyond accuracy, MoSE demonstrates superior efficiency. Compared to other RWK-based models, it achieved an average 10.84% performance boost while simultaneously reducing runtime by approximately 30%. This scalability allows MoSE to handle node-classification tasks on graphs with tens of thousands of nodes, such as Pubmed.

Key Insights and Interpretability

  • Efficiency through Specialization: By using experts of different sizes, MoSE avoids the "redundant node" problem. Simple local structures are routed to small-scale experts, saving computation.
  • Handling Heterophily: MoSE performs exceptionally well on heterophilic graphs where connected nodes often have different labels. Its ability to recognize structural context (the "shape" of the neighborhood) provides a discriminative signal that simple neighbor aggregation lacks.
  • Visual Interpretability: Because the "hidden graphs" are learnable, they can be visualized. Learned experts reveal distinct, recognizable motifs like stars, triangles, and dense clusters, providing transparency into the model's decision-making process.

Conclusion

MoSE represents a significant step forward in making GNNs both more expressive and more efficient. By combining the flexibility of Mixture of Experts with the structural depth of Random Walk Kernels, it provides a robust framework for diverse graph tasks. Future work will focus on scaling MoSE to industrial-scale graphs and integrating the framework with Graph Transformers.

Summary updated

Abstract

While graph neural networks (GNNs) have achieved great success in learning from graph-structured data, their reliance on local, pairwise message passing restricts their ability to capture complex, high-order subgraph patterns. leading to insufficient structural expressiveness. Recent efforts have attempted to enhance structural expressiveness by integrating random walk kernels into GNNs. However, these methods are inherently designed for graph-level tasks, which limits their applicability to other downstream tasks such as node classification. Moreover, their fixed kernel configurations hinder the model's flexibility in capturing diverse subgraph structures. To address these limitations, this paper proposes a novel Mixture of Subgraph Experts (MoSE) framework for flexible and expressive subgraph-based representation learning across diverse graph tasks. Specifically, MoSE extracts informative subgraphs via anonymous walks and dynamically routes them to specialized experts based on structural semantics, enabling the model to capture diverse subgraph patterns with improved flexibility and interpretability. We further provide a theoretical analysis of MoSE's expressivity within the Subgraph Weisfeiler-Lehman (SWL) Test, proving that it is more powerful than SWL. Extensive experiments, together with visualizations of learned subgraph experts, demonstrate that MoSE not only outperforms competitive baselines but also provides interpretable insights into structural patterns learned by the model.
BibTeX
@misc{ye2025mose,
  author = {Junda Ye and Zhongbao Zhang and Li Sun and Siqiang Luo},
  title = {{MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts}},
  year = {2025},
  eprint = {2509.09337},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.09337},
}
Figure