Before revision: In this work, we focus on large graph similarity computation problem and propose a novel "embedding-coarsening-matching" learning framework, which outperforms state-of-the-art methods in this task and has significant improvement in time efficiency. Graph similarity computation for metrics such as Graph Edit Distance (GED) is typically NP-hard , and existing heuristics-based algorithms usually achieves a unsatisfactory trade-off between accuracy and efficiency.
After revision: The ability to compute similarity scores between graphs based on metrics such as Graph Edit Distance (GED) is typically NP-hard , and existing heuristics-based algorithms usually achieves a unsatisfactory trade-off between accuracy and efficiency.