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

• URL: http://arxiv.org/abs/2506.01977v1
• Date: Fri, 16 May 2025 03:45:31 GMT
• Title: Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN
• Authors: Wei Huang, Hanchen Wang, Dong Wen, Shaozhen Ma, Wenjie Zhang, Xuemin Lin,
• Abstract summary: Graph Edit Distance (GED) is a fundamental graph similarity metric widely used in various applications.<n>Recent state-of-the-art hybrid GED solver has shown promising performance.<n>We propose GEDRanker, a novel unsupervised GAN-based framework for GED computation.
• Score: 29.471035994169323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 labels 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 with an effective training strategy to guide the matching-based GED solver toward generating high-quality node matching without the need for ground-truth labels. 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.

Related papers

• Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics [59.07903030446756]
  Graph neural networks are highly vulnerable to distribution shifts on graphs.<n>We present Gadget, the first framework for non-IID graph data.<n> Gadget can be seamlessly integrated with existing graph DA methods to handle large shifts on graphs.
  arXiv  Detail & Related papers  (2025-05-19T05:03:58Z)
• GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code [11.73546901244934]
  Graph Edit Distance (GED) is a widely used metric for measuring similarity between two graphs.<n> neural methods have achieved improved approximation quality compared to non-neural approaches.<n>GRAIL employs a novel combination of large language models (LLMs) and automated prompt tuning to generate a program that is used to compute GED.
  arXiv  Detail & Related papers  (2025-05-04T14:14:24Z)
• DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching [32.853086706407986]
  The Graph Edit Distance (GED) problem aims to compute the minimum number of edit operations required to transform one graph into another.<n>In this paper, we present a novel approach, DiffGED, that leverages generative diffusion model to solve GED and recover the corresponding edit path.
  arXiv  Detail & Related papers  (2025-03-24T00:03:16Z)
• Computing Approximate Graph Edit Distance via Optimal Transport [16.327678462502668]
  Given a graph pair $(G1, G2)$, graph edit distance (GED) is defined as the minimum number of edit operations converting $G1$ to $G2$.<n>GEDIOT is based on inverse optimal transport that leverages a learnable Sinkhorn algorithm to generate the coupling matrix.<n>GEDGW, models GED computation as a linear combination of optimal transport and its variant, Gromov-Wasserstein discrepancy, for node and edge operations.
  arXiv  Detail & Related papers  (2024-12-25T09:55:14Z)
• GeoMix: Towards Geometry-Aware Data Augmentation [76.09914619612812]
  Mixup has shown considerable success in mitigating the challenges posed by limited labeled data in image classification. We propose Geometric Mixup (GeoMix), a simple and interpretable Mixup approach leveraging in-place graph editing.
  arXiv  Detail & Related papers  (2024-07-15T12:58:04Z)
• EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance with Generalized Edit Costs [20.3519249026886]
  Graph Edit Distance (GED) is preferred for measuring inter-graph distance.<n>GED computation is hindered by NP-hardness.<n>Unsupervised methods often face challenges in providing accurate approximations.
  arXiv  Detail & Related papers  (2024-02-08T18:23:05Z)
• MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation [12.437507185260577]
  The exact Graph Edit Distance (GED) computation is known to be NP-complete. We present a data-driven hybrid approach MATA* for approximate GED computation based on Graph Neural Networks (GNNs) and A* algorithms.
  arXiv  Detail & Related papers  (2023-11-04T09:33:08Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Combinatorial Learning of Graph Edit Distance via Dynamic Embedding [108.49014907941891]
  This paper presents a hybrid approach by combing the interpretability of traditional search-based techniques for producing the edit path. Inspired by dynamic programming, node-level embedding is designated in a dynamic reuse fashion and suboptimal branches are encouraged to be pruned. Experimental results on different graph datasets show that our approach can remarkably ease the search process of A* without sacrificing much accuracy.
  arXiv  Detail & Related papers  (2020-11-30T17:41:02Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.