# Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration

arXiv: https://arxiv.org/abs/2510.00394 · HTML: https://mlsanity.com/paper/2510.00394/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 1 Oct 2025.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics](https://mlsanity.com/paper/1705.07115/) (2017)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [Hyperbolic Entailment Cones for Learning Hierarchical Embeddings](https://mlsanity.com/paper/1804.01882/) (2018)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Probabilistic Embedding of Knowledge Graphs with Box Lattice Measures](https://mlsanity.com/paper/1805.06627/) (2018)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [Improving Local Identifiability in Probabilistic Box Embeddings](https://mlsanity.com/paper/2010.04831/) (2020)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Hyperbolic Disk Embeddings for Directed Acyclic Graphs](https://mlsanity.com/paper/1902.04335/) (2019)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)

## Built on by (most cited first, 1 of 1)

- [Revisiting the Generalization of Neural Graph Edit Distance Models](https://mlsanity.com/paper/2610.04644/) (2026)

## Abstract (arXiv)

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 regions can serve as an approximation of MCS, signifying similar node regions and adjacency patterns. We further analyze the relationship between MCS and GED and propose using disjoint parts as a proxy for GED similarity. This analysis enables concurrent computation of MCS and GED, incorporating local and global structural information. Experimental evaluation highlights G2R's competitive performance in graph similarity computation. It achieves up to a 60.0% relative accuracy improvement over state-of-the-art methods in MCS similarity learning, while maintaining efficiency in both training and inference. Moreover, G2R showcases remarkable capability in predicting both MCS and GED similarities simultaneously, providing a holistic assessment of graph similarity. Code available at https://github.com/liuzhouyang/Graph2Region.