Flexible Graph Similarity Computation With A Proactive Optimization Strategy

• URL: http://arxiv.org/abs/2504.06533v2
• Date: Thu, 15 May 2025 08:42:50 GMT
• Title: Flexible Graph Similarity Computation With A Proactive Optimization Strategy
• Authors: Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Dongsheng Li,
• Abstract summary: Graph Edit Distance (GED) offers a principled and flexible measure of graph similarity.<n>GED quantifies the minimum cost needed to transform one graph into another with customizable edit operation costs.<n>Existing methods struggle with adapting to varying operation costs.<n>We propose GEN, a novel learning-based approach for flexible GED approximation.
• Score: 22.212014309562427
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• GEDAN: Learning the Edit Costs for Graph Edit Distance [0.4866486451835401]
  We present a novel Graph Neural Network framework that approximates Graph Edit Distance (GED) using both supervised and unsupervised training.<n>A core component of our architecture is the integration of a Generalized Additive Model, which allows the flexible and interpretable learning of context-aware edit costs.
  arXiv  Detail & Related papers  (2025-08-05T05:44:28Z)
• Regularized Adaptive Graph Learning for Large-Scale Traffic Forecasting [5.212619320601785]
  We propose a Regularized Adaptive Graph Learning (RAG) model for traffic prediction.<n>We show that RAGL consistently outperforms state-of-the-art methods in terms of prediction accuracy and exhibits competitive computational efficiency.<n> experiments on four large-scale real-world traffic datasets show that RAGL consistently outperforms state-of-the-art methods in terms of prediction accuracy and exhibits competitive computational efficiency.
  arXiv  Detail & Related papers  (2025-06-08T14:58:27Z)
• Learning Partial Graph Matching via Optimal Partial Transport [2.4378101048225735]
  We propose a novel framework for partial graph matching inspired by optimal partial transport. Our approach formulates an objective that enables partial assignments while incorporating matching biases. Our method can achieve efficient, exact solutions within cubic worst case time complexity.
  arXiv  Detail & Related papers  (2024-10-22T05:56:57Z)
• Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning [17.85404473268992]
  Graph unlearning aims to eliminate the influence of nodes, edges, or attributes from a trained Graph Neural Network (GNN)<n>Existing graph unlearning techniques often necessitate additional training on the remaining data, leading to significant computational costs.<n>We propose a two-stage training-free approach, Erase then Rectify (ETR), designed for efficient and scalable graph unlearning.
  arXiv  Detail & Related papers  (2024-09-25T07:20:59Z)
• Generalized Exponentiated Gradient Algorithms and Their Application to On-Line Portfolio Selection [13.075438411817117]
  This paper introduces a novel family of generalized exponentiated gradient (EG) updates derived from an Alpha-Beta divergence regularization function. As an illustration of their applicability, we evaluate the proposed updates in addressing the online portfolio selection problem (OLPS) using gradient-based methods.
  arXiv  Detail & Related papers  (2024-06-02T07:56:30Z)
• 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)
• ALF: Adaptive Label Finetuning for Scene Graph Generation [116.59868289196157]
  Scene Graph Generation endeavors to predict the relationships between subjects and objects in a given image. Long-tail distribution of relations often leads to biased prediction on coarse labels, presenting a substantial hurdle in SGG. We introduce one-stage data transfer pipeline in SGG, termed Adaptive Label Finetuning (ALF), which eliminates the need for extra retraining sessions. ALF achieves a 16% improvement in mR@100 compared to the typical SGG method Motif, with only a 6% increase in calculation costs compared to the state-of-the-art method IETrans.
  arXiv  Detail & Related papers  (2023-12-29T01:37:27Z)
• PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection [65.24854366973794]
  Node-level graph anomaly detection (GAD) plays a critical role in identifying anomalous nodes from graph-structured data in domains such as medicine, social networks, and e-commerce. We introduce a simple method termed PREprocessing and Matching (PREM for short) to improve the efficiency of GAD. Our approach streamlines GAD, reducing time and memory consumption while maintaining powerful anomaly detection capabilities.
  arXiv  Detail & Related papers  (2023-10-18T02:59:57Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Adaptive Top-K in SGD for Communication-Efficient Distributed Learning [14.867068493072885]
  This paper proposes a novel adaptive Top-K in SGD framework that enables an adaptive degree of sparsification for each gradient descent step to optimize the convergence performance. numerical results on the MNIST and CIFAR-10 datasets demonstrate that the proposed adaptive Top-K algorithm in SGD achieves a significantly better convergence rate compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-10-24T18:33:35Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Fundamental Limits of Communication Efficiency for Model Aggregation in Distributed Learning: A Rate-Distortion Approach [54.311495894129585]
  We study the limit of communication cost of model aggregation in distributed learning from a rate-distortion perspective. It is found that the communication gain by exploiting the correlation between worker nodes is significant for SignSGD.
  arXiv  Detail & Related papers  (2022-06-28T13:10:40Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  We investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO) We show that the proposed algorithm can minimize the adaptive regret with switching cost in every interval.
  arXiv  Detail & Related papers  (2022-05-02T08:48:22Z)
• GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
  Graph Contrastive Learning (GCL) has shown promising performance in graph representation learning (GRL) without the supervision of manual annotations. This paper proposes an effective graph complementary contrastive learning approach named GraphCoCo to tackle the above issue.
  arXiv  Detail & Related papers  (2022-03-24T02:58:36Z)
• Efficient Dynamic Graph Representation Learning at Scale [66.62859857734104]
  We propose Efficient Dynamic Graph lEarning (EDGE), which selectively expresses certain temporal dependency via training loss to improve the parallelism in computations. We show that EDGE can scale to dynamic graphs with millions of nodes and hundreds of millions of temporal events and achieve new state-of-the-art (SOTA) performance.
  arXiv  Detail & Related papers  (2021-12-14T22:24:53Z)
• 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)
• A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
  We propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the Travelling Salesman Problem (TSP) GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour.
  arXiv  Detail & Related papers  (2020-07-09T17:23:55Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

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.