Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration

Abstract

Graph similarity is critical in graph-related tasks such as graph retrieval, where metrics like maximum common subgraph (MCS) and graph edit distance (GED) are commonly used. However, exact computations of these metrics are known to be NP-Hard. Recent neural network-based approaches approximate the similarity score in embedding spaces to alleviate the computational burden, but they either involve expensive pairwise node comparisons or fail to effectively utilize structural and scale information of graphs. To tackle these issues, we propose a novel geometric-based graph embedding method called Graph2Region (G2R). G2R represents nodes as closed regions and recovers their adjacency patterns within graphs in the embedding space. By incorporating the node features and adjacency patterns of graphs, G2R summarizes graph regions, i.e., graph embeddings, where the shape captures the underlying graph structures and the volume reflects the graph size. Consequently, the overlap between graph regio

Stats

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

Related papers

• SEGMN: A Structure-enhanced Graph Matching Network For Graph Similarity Learning (2024)2.26
• Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
• Hierarchical Graph Matching Network For Graph Similarity Computation (2020)0.00
• Learning-based Efficient Graph Similarity Computation Via Multi-scale Convolutional Set Matching (2018)13.60
• S\(^3\)GND: An Effective Learning-based Approach For Subgraph Similarity Search Under Generalized Neighbor Difference Semantics (technical Report) (2026)0.00
• Deep Graph Similarity Learning: A Survey (2019)13.97
• Hierarchy-aware Neural Subgraph Matching With Enhanced Similarity Measure (2025)1.20
• VERSE: Versatile Graph Embeddings From Similarity Measures (2018)17.42