S\(^3\)GND: An Effective Learning-based Approach For Subgraph Similarity Search Under Generalized Neighbor Difference Semantics (technical Report)

Abstract

Subgraph similarity search over large-scale graphs is a fundamental task that retrieves subgraphs similar to a given query graph from a data graph, and it plays a crucial role in real applications such as protein discovery, social network analysis, and recommendation systems. While prior works on subgraph similarity search studied various graph similarity metrics, in this paper, we propose a novel graph similarity semantics, \textit\{generalized neighbor difference\} (GND), that accounts for both the keyword-set relationships between vertices and edge-weight differences. We formulate the problem of \textit\{subgraph similarity search under the generalized neighbor difference semantics\} (S\(^3\)GND), which retrieves those subgraphs similar to a query graph \(q\) under GND semantics. To efficiently tackle the S\(^3\)GND problem, we propose an effective learning-based approach, which constructs a keyword hypergraph from the data graph, and trains a \textit\{hypergraph neural network\} (H

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keywen2026s

Related papers

• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• Sub-gmn: The Neural Subgraph Matching Network Model (2021)6.34
• SEGMN: A Structure-enhanced Graph Matching Network For Graph Similarity Learning (2024)2.26
• Hierarchical Graph Matching Network For Graph Similarity Computation (2020)0.00
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• Hierarchy-aware Neural Subgraph Matching With Enhanced Similarity Measure (2025)1.20
• Deep Graph Similarity Learning: A Survey (2019)13.97
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30