Exact Subgraph Isomorphism Network for Predictive Graph Mining

• URL: http://arxiv.org/abs/2509.21699v1
• Date: Thu, 25 Sep 2025 23:49:26 GMT
• Title: Exact Subgraph Isomorphism Network for Predictive Graph Mining
• Authors: Taiga Kojima, Masayuki Karasuyama,
• Abstract summary: We propose Exact subgraph Isomorphism Network (EIN), which combines the exact subgraph enumeration, neural network, and a sparse regularization.<n>EIN has sufficiently high prediction performance compared with standard graph neural network models.
• Score: 6.926467730065948
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the graph-level prediction task (predict a label for a given graph), the information contained in subgraphs of the input graph plays a key role. In this paper, we propose Exact subgraph Isomorphism Network (EIN), which combines the exact subgraph enumeration, neural network, and a sparse regularization. In general, building a graph-level prediction model achieving high discriminative ability along with interpretability is still a challenging problem. Our combination of the subgraph enumeration and neural network contributes to high discriminative ability about the subgraph structure of the input graph. Further, the sparse regularization in EIN enables us 1) to derive an effective pruning strategy that mitigates computational difficulty of the enumeration while maintaining the prediction performance, and 2) to identify important subgraphs that contributes to high interpretability. We empirically show that EIN has sufficiently high prediction performance compared with standard graph neural network models, and also, we show examples of post-hoc analysis based on the selected subgraphs.

Related papers

• Subgraph Aggregation for Out-of-Distribution Generalization on Graphs [29.884717215947745]
  SubGraph Aggregation (SuGAr) is designed to learn a diverse set of subgraphs that are crucial for OOD generalization on graphs.<n>Experiments on both synthetic and real-world datasets demonstrate that SuGAr outperforms state-of-the-art methods, achieving up to a 24% improvement in OOD generalization on graphs.
  arXiv  Detail & Related papers  (2024-10-29T16:54:37Z)
• Deep Generative Models for Subgraph Prediction [10.56335881963895]
  This paper introduces subgraph queries as a new task for deep graph learning. Subgraph queries jointly predict the components of a target subgraph based on evidence that is represented by an observed subgraph. We utilize a probabilistic deep Graph Generative Model to answer subgraph queries.
  arXiv  Detail & Related papers  (2024-08-07T19:24:02Z)
• Improving the interpretability of GNN predictions through conformal-based graph sparsification [9.550589670316523]
  Graph Neural Networks (GNNs) have achieved state-of-the-art performance in solving graph classification tasks. We propose a GNN emphtraining approach that finds the most predictive subgraph by removing edges and/or nodes. We rely on reinforcement learning to solve the resulting bi-level optimization with a reward function based on conformal predictions.
  arXiv  Detail & Related papers  (2024-04-18T17:34:47Z)
• Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
  Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. We propose a Self-Interpretable Graph aNomaly dETection model ( SIGNET) that detects anomalous graphs as well as generates informative explanations simultaneously.
  arXiv  Detail & Related papers  (2023-10-25T10:10:07Z)
• Stochastic Subgraph Neighborhood Pooling for Subgraph Classification [2.1270496914042996]
  Subgraph Neighborhood Pooling (SSNP) jointly aggregates the subgraph and its neighborhood information without any computationally expensive operations such as labeling tricks. Our experiments demonstrate that our models outperform current state-of-the-art methods (with a margin of up to 2%) while being up to 3X faster in training.
  arXiv  Detail & Related papers  (2023-04-17T18:49:18Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• 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)
• On Explainability of Graph Neural Networks via Subgraph Explorations [48.56936527708657]
  We propose a novel method, known as SubgraphX, to explain graph neural networks (GNNs) Our work represents the first attempt to explain GNNs via identifying subgraphs explicitly.
  arXiv  Detail & Related papers  (2021-02-09T22:12:26Z)
• Graph Information Bottleneck for Subgraph Recognition [103.37499715761784]
  We propose a framework of Graph Information Bottleneck (GIB) for the subgraph recognition problem in deep graph learning. Under this framework, one can recognize the maximally informative yet compressive subgraph, named IB-subgraph. We evaluate the properties of the IB-subgraph in three application scenarios: improvement of graph classification, graph interpretation and graph denoising.
  arXiv  Detail & Related papers  (2020-10-12T09:32:20Z)

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.