# Nass: A New Approach to Graph Similarity Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2020.

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

- [GraSP: Simple yet Effective Graph Similarity Predictions](https://mlsanity.com/paper/2412.09968/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of graph similarity search with graph edit distance (GED) constraints. Due to the NP-hardness of GED computation, existing solutions to this problem adopt the filtering-and-verification framework with a main focus on the filtering phase to generate a small number of candidate graphs. However, they have a limitation that the number of candidates grows extremely rapidly as a GED threshold increases. To address the limitation, we propose a new approach that utilizes GED computation results in generating candidate graphs. The main idea is that whenever we identify a result graph of the query, we immediately regenerate candidate graphs using a subset of pre-computed graphs similar to the identified result graph. To speed up GED computation, we also develop a novel GED computation algorithm. The proposed algorithm reduces the search space for GED computation by utilizing a series of filtering techniques, which have been used to generate candidates in existing solutions. Experimental results on real datasets demonstrate the proposed approach significantly outperforms the state-of-the art techniques.