Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.05885 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918148997906432 |
|---|---|
| author | Bommakanti, Aditya Vonteri, Harshith Reddy Ranu, Sayan Karras, Panagiotis |
| author_facet | Bommakanti, Aditya Vonteri, Harshith Reddy Ranu, Sayan Karras, Panagiotis |
| contents | The need to identify graphs with small structural distances from a query arises in domains such as biology, chemistry, recommender systems, and social network analysis. Among several methods for measuring inter-graph distance, Graph Edit Distance (GED) is preferred for its comprehensibility, though its computation is hindered by NP-hardness. Optimization based heuristic methods often face challenges in providing accurate approximations. State-of-the-art GED approximations predominantly utilize neural methods, which, however: (i) lack an explanatory edit path corresponding to the approximated GED; (ii) require the NP-hard generation of ground-truth GEDs for training; and (iii) necessitate separate training on each dataset. In this paper, we propose EUGENE, an efficient, algebraic, and structure-aware optimization based method that estimates GED and also provides edit paths corresponding to the estimated cost. Extensive experimental evaluation demonstrates that EUGENE achieves state-of-the-art GED estimation with superior scalability across diverse datasets and generalized cost settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05885 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | EUGENE: Explainable Structure-aware Graph Edit Distance Estimation with Generalized Edit Costs Bommakanti, Aditya Vonteri, Harshith Reddy Ranu, Sayan Karras, Panagiotis Machine Learning The need to identify graphs with small structural distances from a query arises in domains such as biology, chemistry, recommender systems, and social network analysis. Among several methods for measuring inter-graph distance, Graph Edit Distance (GED) is preferred for its comprehensibility, though its computation is hindered by NP-hardness. Optimization based heuristic methods often face challenges in providing accurate approximations. State-of-the-art GED approximations predominantly utilize neural methods, which, however: (i) lack an explanatory edit path corresponding to the approximated GED; (ii) require the NP-hard generation of ground-truth GEDs for training; and (iii) necessitate separate training on each dataset. In this paper, we propose EUGENE, an efficient, algebraic, and structure-aware optimization based method that estimates GED and also provides edit paths corresponding to the estimated cost. Extensive experimental evaluation demonstrates that EUGENE achieves state-of-the-art GED estimation with superior scalability across diverse datasets and generalized cost settings. |
| title | EUGENE: Explainable Structure-aware Graph Edit Distance Estimation with Generalized Edit Costs |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2402.05885 |