Flexible Graph Similarity Computation With A Proactive Optimization Strategy
This work addresses flexible graph similarity computation for applications like bioinformatics and social network analysis, representing an incremental improvement over existing learning-based methods.
The paper tackled the problem of adapting Graph Edit Distance (GED) approximation to varying operation costs and inefficient reactive mapping refinements, achieving up to 37.8% reduction in approximation error and 72.7% reduction in inference time compared to state-of-the-art methods.
Graph Edit Distance (GED) offers a principled and flexible measure of graph similarity, as it quantifies the minimum cost needed to transform one graph into another with customizable edit operation costs. Despite recent learning-based efforts to approximate GED via vector space representations, existing methods struggle with adapting to varying operation costs. Furthermore, they suffer from inefficient, reactive mapping refinements due to reliance on isolated node-level distance as guidance. To address these issues, we propose GEN, a novel learning-based approach for flexible GED approximation. GEN addresses the varying costs adaptation by integrating operation costs prior to match establishment, enabling mappings to dynamically adapt to cost variations. Furthermore, GEN introduces a proactive guidance optimization strategy that captures graph-level dependencies between matches, allowing informed matching decisions in a single step without costly iterative refinements. Extensive evaluations on real-world and synthetic datasets demonstrate that GEN achieves up to 37.8% reduction in GED approximation error and 72.7% reduction in inference time compared with state-of-the-art methods, while consistently maintaining robustness under diverse cost settings and graph sizes.