Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure

• URL: http://arxiv.org/abs/2510.00402v1
• Date: Wed, 01 Oct 2025 01:27:41 GMT
• Title: Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure
• Authors: Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Menghan Jia, Dongsheng Li,
• Abstract summary: Subgraph matching is challenging as it necessitates time-consuming searches.<n>Recent Graph Neural Network (GNN)-based approaches address this issue by employing GNN encoders to extract graph information.<n>We propose NC-Iso, a novel GNN architecture for neural subgraph matching.
• Score: 22.57636502076737
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Subgraph matching is challenging as it necessitates time-consuming combinatorial searches. Recent Graph Neural Network (GNN)-based approaches address this issue by employing GNN encoders to extract graph information and hinge distance measures to ensure containment constraints in the embedding space. These methods significantly shorten the response time, making them promising solutions for subgraph retrieval. However, they suffer from scale differences between graph pairs during encoding, as they focus on feature counts but overlook the relative positions of features within node-rooted subtrees, leading to disturbed containment constraints and false predictions. Additionally, their hinge distance measures lack discriminative power for matched graph pairs, hindering ranking applications. We propose NC-Iso, a novel GNN architecture for neural subgraph matching. NC-Iso preserves the relative positions of features by building the hierarchical dependencies between adjacent echelons within node-rooted subtrees, ensuring matched graph pairs maintain consistent hierarchies while complying with containment constraints in feature counts. To enhance the ranking ability for matched pairs, we introduce a novel similarity dominance ratio-enhanced measure, which quantifies the dominance of similarity over dissimilarity between graph pairs. Empirical results on nine datasets validate the effectiveness, generalization ability, scalability, and transferability of NC-Iso while maintaining time efficiency, offering a more discriminative neural subgraph matching solution for subgraph retrieval. Code available at https://github.com/liuzhouyang/NC-Iso.

Related papers

• Multi-View Subgraph Neural Networks: Self-Supervised Learning with Scarce Labeled Data [24.628203785306233]
  We present a novel learning framework called multi-view subgraph neural networks (Muse) for handling long-range dependencies. By fusing two views of subgraphs, the learned representations can preserve the topological properties of the graph at large. Experimental results show that Muse outperforms the alternative methods on node classification tasks with limited labeled data.
  arXiv  Detail & Related papers  (2024-04-19T01:36:50Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Pose-Graph Attentional Graph Neural Network for Lidar Place Recognition [16.391871270609055]
  This paper proposes a pose-graph attentional graph neural network, called P-GAT. It compares keynodes between sequential and non-sequential sub-graphs for place recognition tasks. P-GAT uses the maximum spatial and temporal information between neighbour cloud descriptors.
  arXiv  Detail & Related papers  (2023-08-31T23:17:44Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  We propose a novel graph contrastive learning method, termed Mixed Graph Contrastive Network (MGCN)<n>In our method, we improve the discriminative capability of the latent embeddings by an unperturbed augmentation strategy and a correlation reduction mechanism.<n>By combining the two settings, we extract rich supervision information from both the abundant nodes and the rare yet valuable labeled nodes for discriminative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  We show that a well-known graph algorithm, Label Propagation, combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities.
  arXiv  Detail & Related papers  (2022-05-19T08:34:34Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  We introduce GNNRank, a modeling framework compatible with any GNN capable of learning digraph embeddings. We show that our methods attain competitive and often superior performance compared with existing approaches.
  arXiv  Detail & Related papers  (2022-02-01T04:19:50Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  We show that in typical heterphilous graphs, the edges may be directed, and whether to treat the edges as is or simply make them undirected greatly affects the performance of the GNN models. We develop a model that adaptively learns the directionality of the graph, and exploits the underlying long-distance correlations between nodes.
  arXiv  Detail & Related papers  (2021-11-19T08:54:21Z)
• Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
  Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data. Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks. In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
  arXiv  Detail & Related papers  (2020-11-19T06:03:35Z)
• Neural Subgraph Matching [57.05893848555512]
  NeuroMatch is an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch is 100x faster than existing geometric approaches and 18% more accurate than existing subgraph matching methods.
  arXiv  Detail & Related papers  (2020-07-06T22:06:38Z)

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.