Usage documentation? about gmatch4py HOT 13 CLOSED

Hi @bojan2110, sorry about the delay, I was on holidays 😎

I'm currently working on a Get Started page or a Jupyter Notebook, but for now, if you want to use algorithms like graph edit distances, here is an example:

import networkx as nx # Gmatch4py use networkx graph 
from gmatch4py.ged.graph_edit_dist import GraphEditDistance # For the GED using the munkres algorithm
g1=nx.complete_bipartite_graph(5,4) # Generate graphs
g2=nx.complete_bipartite_graph(6,4)

All Graph matching algorithms in Gmatch4py work this way:

• Each algorithm is associated with an object, each object having its specific parameters. In this case, the parameters are the edit costs (delete a vertex, add a vertex, ...)
• Each object is associated with a compare() function with two parameters. First parameter is a list of the graphs you want to compare, i.e. measure the distance/similarity (depends on the algorithm). Then, you can specify a sample of graphs to be compared to all the other graphs. To this end, the second parameter should be a list containing the indices of these graphs (based on the first parameter list). If you rather compute the distance/similarity between all graphs, just use the None value.

ged=GraphEditDistance(1,1,1,1) # all edit costs are equal to 1
result=ged.compare([g1,g2],None) 
print(result)

The output will be :

Out[10]:
array([[0., 7.],
       [7., 0.]])

This output result is "raw", if you wish to have normalized results in terms of distance (or similarity) you can use :

ged.similarity(result)
# or 
ged.distance(result)

Hope I am not too late 😨 I'm working on the documentation!

from gmatch4py.

Hi,
I have a simple code to compare the computed graph edit distance with GMatch4py and also the graph_edit_distance function in networkx.
my code is as follows:

import gmatch4py as gm
g1=nx.complete_graph(3)
g2=nx.complete_graph(4)
ged=gm.GraphEditDistance(1,1,1,1) # all edit costs are equal to 1
result=ged.compare([g1,g2],None)
print("GMatch4py output:\n", result)
print("networkx output:\n", nx.graph_edit_distance(g1,g2))

and the results are:

 [[0. 7.]
 [7. 0.]]
networkx output:
 4.0```
Would you please tell me what does each element of the output matrix of GMatch4py mean? Is 7 the edit distance computed by GMatch4py while the exact edit distance is 4? Is the performance and accuracy of GMatchpy low even for very small graphs or it is just an understanding miskate made by me?
Regards

from gmatch4py.

hi @Jacobe2169 , thanks so much for that detailed description! I am actually facing problems with the installation process, as it looks like the ged module is empty?
So typing >>> help(gmatch4py.ged), generates the following output:
Help on package gmatch4py.ged in gmatch4py:

NAME
gmatch4py.ged

PACKAGE CONTENTS

As a result I always get ModuleNotFoundError.
Do you have an idea what might be the cause for this?

Thanks again, and good luck with the documentation!

from gmatch4py.

hi @bojan2110,

A few hints :

• Did you import gmatch4py.ged correctly? It should be this way :

import gmatch4py.ged
help(gmatch4py.ged)

• Also, in case you did not know, ged is a submodule, so if you are looking for a specific algorithm documentation you can do this: help(gmatch4py.ged.graph_edit_dist)

from gmatch4py.

Hey @Jacobe2169,

I did exactly like that, and as you see from previous reply, the ged content is empty. So it looks like this submodule doesn't contain any algorithms. Since that is the case, the command you suggested help(gmatch4py.ged.graph_edit_dist) results in the following output:

AttributeError: module 'gmatch4py.ged' has no attribute 'graph_edit_dist'

For the installation, I did install cython as recommended. And followed the instruction in the readme.

from gmatch4py.

Hi @Jacobe2169 ,

Seems like the package is just fine now. Not sure if you made some updates, but anyway thanks for your tips.

I have one question regarding the algorithm itself. Does it actually work on labeled graphs? Performing this simple calculation

g1 = nx.DiGraph()
g1.add_nodes_from(['label1'])

g2 = nx.DiGraph()
g2.add_nodes_from(['label2'])

ged=GraphEditDistance(1,1,1,1) 
result=ged.compare([g1,g2],None)

I got an outcome of 0, while I expect 1.

print(result)
[[0. 0.]
 [0. 0.]]

Any thoughts on this?

from gmatch4py.

Hi @bojan2110,

Just pull a new version that correct this behaviour! But theoretically, you should have 2 ? A substitution is a two-step operation (deletion + addition)?

from gmatch4py.

Hi @Jacobe2169 ,

I would expect the value of 2, with the steps that you mentioned. Cool, just checked that its good now.

I have (yet) another question :)

g1 = nx.DiGraph()
g1.add_nodes_from([1,2])
g1.add_edge(1, 2)

g2 = nx.DiGraph()
g2.add_nodes_from([4])

ged=ged.GraphEditDistance(1,1,1,1) 
result=ged.compare([g1,g2],None)
print(result)

outputs

[[0. 2.]
 [2. 0.]]

while if we just change the order of the graphs in the compare method

result=ged.compare([g2,g1],None)

... the obtained result change to what I would say is correct (4 operations to go from one to another graph):

[[0. 4.]
 [4. 0.]]

I noticed that the order of the graph list in compare method matters, for the results. Is this correct?

from gmatch4py.

And you are totally right, this is weird! :) My mistake! Just push the last update! So now, it does not depend on the input order :) And you should see :

[[0. 2.]
 [4. 0.]]

from gmatch4py.

Cool! Looks better.
I am now facing a problem, testing the code on graphs I use for my research.
I give two graphs as input, g1 and g2. They have same nodes (with same labels), but the density of the graph is different. So I would expect the GED algoritm to take that into account.

In this specific case, number of edges at g1 is 105, while at g2 is 196.

However running the ged code results in:

[[0. 0.]
 [0. 0.]]

I think something is missing at the edge caluculation, cos running a simple example:

g1 = nx.DiGraph()
g1.add_nodes_from([1,2])
g1.add_edge(1, 2)

g2 = nx.DiGraph()
g2.add_nodes_from([1,2])

ged=ged.GraphEditDistance(1,1,1,1) 
result=ged.compare([g1,g2],None)
print(result)

also results in

[[0. 0.]
 [0. 0.]]

Hope that you find the comments useful! :)

from gmatch4py.

Hi @bojan2110,

Your comments help a lot! :) Just pushed the last update! I rechecked the whole algorithm to compute the edit costs, it should work! :)

from gmatch4py.

Yes! Perfect!

Working like expected now. Good like with the project, and finishing up the documentation :D

from gmatch4py.

Hi @bojan2110,

Just updated the GraphEditDistance algorithm (again !). You can check the results, it should be more coherent :)

from gmatch4py.