Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN

Wei Huang (RIKEN AIP) · Hanchen Wang (University of Technology Sydney) · Dong Wen (University of New South Wales) · SHAOZHEN MA (University of New South Wales) · Wenjie Zhang (the university of new south wales) · Xuemin Lin (Shanghai Jiaotong University)

benchmark datasetsbipartite graph matchingedit pathgenerative diffusion modelgraph edit distanceground-truth supervisionhigh-quality node matchinghybrid ged solverinterpretabilitymatching-based ged solvernode matchingnp-hard problempreference-aware discriminatorsolution qualityunsupervised gan

Graph Edit Distance (GED) is a fundamental graph similarity metric widely used in various applications. However, computing GED is an NP-hard problem. Recent state-of-the-art hybrid GED solver has shown promising performance by formulating GED as a bipartite graph matching problem, then leveraging a generative diffusion model to predict node matching between two graphs, from which both the GED and its corresponding edit path can be extracted using a traditional algorithm. However, such methods typically rely heavily on ground-truth supervision, where the ground-truth node matchings are often costly to obtain in real-world scenarios. In this paper, we propose GEDRanker, a novel unsupervised GAN-based framework for GED computation. Specifically, GEDRanker consists of a matching-based GED solver and introduces an interpretable preference-aware discriminator. By leveraging preference signals over different node matchings derived from edit path lengths, the discriminator can guide the matching-based solver toward generating high-quality node matching without the need for ground-truth supervision. Extensive experiments on benchmark datasets demonstrate that our GEDRanker enables the matching-based GED solver to achieve near-optimal solution quality without any ground-truth supervision.