Papers › Nass: A New Approach to Graph Similarity Search
Nass: A New Approach to Graph Similarity Search
Jongik Kim
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
In Syntology View this paper on Syntology: its repositories, every harvested function with whether it ran, its licence and the call to fetch it.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections