Answers are grounded in this paper and cite their sources.
This method reduces computation errors by over 80% in graph alignment, indicating promising potential for graph analysis.
Graph Edit Distance (GED) is a widely recognized metric for measuring graph similarity, yet its NP-complete nature poses challenges for fast and accurate computation. This paper introduces FGWAlign, an Optimal Transport (OT)-based approach for graph alignment and GED computation. We take the first step to theoretically demonstrate and that computing GED can be transformed into optimizing a particular OT variant—the Fused Gromov-Wasserstein distance. Tailored to the GED problem structure, we further implement three key enhancements to the standard FGW solver: (1) a random exploration scheme to better locate the global optimum, (2) a diverse projection strategy for post-processing the transportation plan to escape local optima, and (3) a novel extension to accommodate multi-relational graphs with edge labels. With O (| V || E |) time complexity and O (| V | 2 ) space complexity, where | V | and | E | are the maximum number of nodes and edges between the two compared graphs, FGWAlign achieves a superior balance of efficiency, accuracy, and scalability. Empirical results show that, compared with 12 representative GED computation methods across different categories on 4 real-world graph datasets, FGWAlign reduces computation errors by over 80% and achieves 15–60× speedup. It also demonstrates promising resutls on downstream applications including labeled graph alignment and graph-level anomaly detection, highlighting its versatility. FGWAlign opens up promising avenues for future applications in graph data management.
No takes yet. Share an insight, caveat, or question.
Tang et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: