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

arXiv: https://arxiv.org/abs/2509.09337 · HTML: https://mlsanity.com/paper/2509.09337/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 48 references that are in the map.
- First posted on arXiv 11 Sep 2025.

## Builds on (most cited first, 26 of 26)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2112.08679/) (2021)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Graph Mixture of Experts: Learning on Large-Scale Graphs with Explicit Diversity Modeling](https://mlsanity.com/paper/2304.02806/) (2023)
- [ASGN: An Active Semi-supervised Graph Neural Network for Molecular Property Prediction](https://mlsanity.com/paper/2007.03196/) (2020)
- [KerGNNs: Interpretable Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/2201.00491/) (2022)
- [Convolutional Kernel Networks for Graph-Structured Data](https://mlsanity.com/paper/2003.05189/) (2020)
- [Steps Toward Deep Kernel Methods from Infinite Neural Networks](https://mlsanity.com/paper/1508.05133/) (2015)
- [End-to-End Kernel Learning with Supervised Convolutional Kernel Networks](https://mlsanity.com/paper/1605.06265/) (2016)
- [GraphMoRE: Mitigating Topological Heterogeneity via Mixture of Riemannian Experts](https://mlsanity.com/paper/2412.11085/) (2024)
- [Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels](https://mlsanity.com/paper/2104.02995/) (2021)
- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman](https://mlsanity.com/paper/2306.03266/) (2023)
- [SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation](https://mlsanity.com/paper/2305.09958/) (2023)
- [Descriptive Kernel Convolution Network with Improved Random Walk Kernel](https://mlsanity.com/paper/2402.06087/) (2024)

## Built on by (most cited first, 3 of 3)

- [The Post-GCN Decade Revisited: Curvature-Stratified Evaluation of Relational Learning](https://mlsanity.com/paper/2606.06397/) (2026)
- [Adaptive Graph Mixture of Residual Experts: Unsupervised Learning on Diverse Graphs with Heterogeneous Specialization](https://mlsanity.com/paper/2510.21207/) (2025)
- [Scalable Heterogeneous Graph Learning via Heterogeneous-aware Orthogonal Prototype Experts](https://mlsanity.com/paper/2601.05537/) (2026)

## Abstract (arXiv)

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.