# Approximate isomorphism **URL:** \ **Category:** Usage\ **Tags:** R\ **Created:** [13 November 2020 02:43 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511 "2020-11-13T02:43:15Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![Song\_April](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/song_april/32/398_2.png) [@Song\_April](https://igraph.discourse.group/u/Song_April)\ **Post date:** [13 November 2020 02:43 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/1 "2020-11-13T02:43:15Z")
Can igraph identify approximate isomorphic graphs? also called inexact graph matching. Thanks in advance. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [13 November 2020 09:00 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/2 "2020-11-13T09:00:46Z")
The Mathematica interface (you tagged this question as `Mathematica`) cannot yet do this. The R interface has the `match_vertices` functions. It is at the moment only available in R. ---
**Author:** ![Song\_April](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/song_april/32/398_2.png) [@Song\_April](https://igraph.discourse.group/u/Song_April)\ **Post date:** [13 November 2020 15:35 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/3 "2020-11-13T15:35:26Z")
> [@szhorvat](#): > > match\_vertices Thanks for your response. I meant to tag R but somehow ended up in M interface. Sorry for the mistake. A follow up question: the match\_vertices function can only work for `A` and `B` of the same size. what I am actually looking for is: a graph similarity measure : minimum cost of edit path (sequence of node and edge edit operations) transforming graph G1 to graph isomorphic to G2. Reference: [networkx.algorithms.similarity.graph\_edit\_distance — NetworkX 2.2 documentation](https://networkx.org/documentation/networkx-2.2/reference/algorithms/generated/networkx.algorithms.similarity.graph_edit_distance.html#networkx.algorithms.similarity.graph_edit_distance) I was wondering if igraph can do the same thing. Thanks. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [13 November 2020 15:51 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/4 "2020-11-13T15:51:23Z")
At the moment, there is no such functionality in igraph. I guess you are looking for better performance than what networkx offers? The problem is NP-complete, so another exact implementation is unlikely to make much larger graphs feasible. Wikipedia says that there are some fast approximation algorithms. Personally, I do not have experience with these. I don’t know where one can find an implementation and how accurate they are. ---
**Author:** ![Song\_April](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/song_april/32/398_2.png) [@Song\_April](https://igraph.discourse.group/u/Song_April)\ **Post date:** [13 November 2020 16:05 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/5 "2020-11-13T16:05:03Z")
Thanks so much for your quick response. I appreciate that. I am actually trying to find such functionality in R, but networkx is only for python. But thanks for clarifying that igraph does not offer that for now. That helps. Hope you have nice day. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [13 November 2020 16:32 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/6 "2020-11-13T16:32:53Z")
Should you wish to contribute this functionality to igraph, it would be very welcome! Of course, it is far from a trivial task … Here are some tips you can try: - Pad the smaller graph with isolated vertices so its size matches the larger one, then use `match_vertices` - Sometimes it’s useful to characterize the “similarity” of two graphs indirectly, by computing a vector of several global graph properties for both graphs, then measuring the distance of these vectors. I would try spectral properties first. ---
**Author:** ![Song\_April](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/song_april/32/398_2.png) [@Song\_April](https://igraph.discourse.group/u/Song_April)\ **Post date:** [13 November 2020 16:49 UTC](https://igraph.discourse.group/t/approximate-isomorphism/511/7 "2020-11-13T16:49:53Z")
Thank you for your response. I wish I were able to contribute, but my knowledge on developing a functionality is basically zero. Also thanks for your suggestions. I will definitely try them.