DS-Span: Single-Phase Discriminative Subgraph Mining for Efficient Graph Embeddings

• URL: http://arxiv.org/abs/2511.17419v1
• Date: Fri, 21 Nov 2025 17:17:51 GMT
• Title: DS-Span: Single-Phase Discriminative Subgraph Mining for Efficient Graph Embeddings
• Authors: Yeamin Kaiser, Muhammed Tasnim Bin Anwar, Bholanath Das, Chowdhury Farhan Ahmed, Md. Tanvir Alam,
• Abstract summary: DS-Span is a single-phase discriminative subgraph mining framework.<n>It unifies pattern growth, pruning, and supervision-driven scoring within one of the search space.<n>It generates more compact and discriminative subgraph features than prior multi-stage methods.
• Score: 0.7340017786387767
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph representation learning seeks to transform complex, high-dimensional graph structures into compact vector spaces that preserve both topology and semantics. Among the various strategies, subgraph-based methods provide an interpretable bridge between symbolic pattern discovery and continuous embedding learning. Yet, existing frequent or discriminative subgraph mining approaches often suffer from redundant multi-phase pipelines, high computational cost, and weak coupling between mined structures and their discriminative relevance. We propose DS-Span, a single-phase discriminative subgraph mining framework that unifies pattern growth, pruning, and supervision-driven scoring within one traversal of the search space. DS-Span introduces a coverage-capped eligibility mechanism that dynamically limits exploration once a graph is sufficiently represented, and an information-gain-guided selection that promotes subgraphs with strong class-separating ability while minimizing redundancy. The resulting subgraph set serves as an efficient, interpretable basis for downstream graph embedding and classification. Extensive experiments across benchmarks demonstrate that DS-Span generates more compact and discriminative subgraph features than prior multi-stage methods, achieving higher or comparable accuracy with significantly reduced runtime. These results highlight the potential of unified, single-phase discriminative mining as a foundation for scalable and interpretable graph representation learning.

Related papers

• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• A Multi-scale Graph Signature for Persistence Diagrams based on Return Probabilities of Random Walks [1.745838188269503]
  We explore the use of a family of multi-scale graph signatures to enhance the robustness of topological features. We propose a deep learning architecture to handle this set input. Experiments on benchmark graph classification datasets demonstrate that our proposed architecture outperforms other persistent homology-based methods.
  arXiv  Detail & Related papers  (2022-09-28T17:30:27Z)
• Let Invariant Rationale Discovery Inspire Graph Contrastive Learning [98.10268114789775]
  We argue that a high-performing augmentation should preserve the salient semantics of anchor graphs regarding instance-discrimination. We propose a new framework, Rationale-aware Graph Contrastive Learning (RGCL) RGCL uses a rationale generator to reveal salient features about graph instance-discrimination as the rationale, and then creates rationale-aware views for contrastive learning.
  arXiv  Detail & Related papers  (2022-06-16T01:28:40Z)
• Improved Dual Correlation Reduction Network [40.792587861237166]
  We propose a novel deep graph clustering algorithm termed Improved Dual Correlation Reduction Network (IDCRN) By approximating the cross-view feature correlation matrix to an identity matrix, we reduce the redundancy between different dimensions of features. We also avoid the collapsed representation caused by the over-smoothing issue in Graph Convolutional Networks (GCNs) through an introduced propagation regularization term.
  arXiv  Detail & Related papers  (2022-02-25T07:48:32Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Recognizing Predictive Substructures with Subgraph Information Bottleneck [97.19131149357234]
  We propose a novel subgraph information bottleneck (SIB) framework to recognize such subgraphs, named IB-subgraph. Intractability of mutual information and the discrete nature of graph data makes the objective of SIB notoriously hard to optimize. Experiments on graph learning and large-scale point cloud tasks demonstrate the superior property of IB-subgraph.
  arXiv  Detail & Related papers  (2021-03-20T11:19:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.