tvayer / fgw Goto Github PK

View Code? Open in Web Editor NEW

93.0 93.0 15.0 9.84 MB

Code for Optimal Transport for structured data with application on graphs

Python 100.00%

fgw's People

Contributors

Stargazers

Watchers

Forkers

stjordanis emdadulsadik panispani ghazalehsafari mfouda laplacekorea phycomlab zdk123 milenabel qinghaoliang duykhuongnguyen jgridleymldl pandadada123 gob1thaasan hamzatnicofam

fgw's Issues

Problems with the distance matrices

Thanks for this great package for FGW!

But there may be some bugs with the distance matrices C1 and C2. I tried a graph in the dataset BZR, and some entries in C1 seem to be not correct.

Here are the codes.

import numpy as np
import os,sys
sys.path.append(os.path.realpath('../lib'))

from graph import graph_colors,draw_rel,draw_transp,Graph,wl_labeling
from ot_distances import Fused_Gromov_Wasserstein_distance,Wasserstein_distance
import copy
from data_loader import load_local_data,histog,build_noisy_circular_graph
import matplotlib.pyplot as plt
import networkx as nx
import ot

dataset_n='bzr'
path='../data/'
X,label=load_local_data(path,dataset_n,wl=0) 
G1=X[0]
g1=G1.nx_graph

G2 = copy.deepcopy(G1)

vmin=-5
vmax=20 # the range of color

plt.figure(figsize=(8,5))
draw_rel(g1,vmin=vmin,vmax=vmax,with_labels=True,draw=False)

dgw=Fused_Gromov_Wasserstein_distance(alpha=1,features_metric='hamming_dist',method='shortest_path').graph_d(G1,G2)

The graph G1 I get is

I also slightly changed the following two lines to draw this graph properly.

FGW/lib/graph.py

Line 355 in 3d2128a

val_map[k]=cpick.to_rgba(v)

FGW/lib/graph.py

Line 379 in 3d2128a

 nx.draw(G,pos,with_labels=True,labels=nx.get_node_attributes(G,'attr_name'),node_color = colors) 

Change them to:

val_map[k]=cpick.to_rgba(sum(pow(np.array(v),2)))

and

 nx.draw_networkx(G,pos,node_color = colors)

The distance matrix (30 * 30) of this graph can be checked. The first line of it is:

0	1	1	1	2	2	3	3	2	4	3	2	5	5	5	4	6	6	5	4	6	6	7	7	8	8	7	9	8	7

where the third entry "1" indicates the shortest path length between node 1 and node 3, but we can see from the graph that this length should be "2".

I would appreciate any comments you may have!

node attributes

Did you actually try to use node attributes in your work?
Current code doesn't allow for that, expecting discreet node labels only:
labels = np.zeros(len(l_aux), dtype=np.int32), so the moment I try to upload a dataset with attributes, the code crashes..
I wrote a workaround where I use labels as strings to put node features there, but not sure if it is feasible to do since node attributes are very different...

Non-zero Gromov distance on identical graphs

Thanks for this excellent package, it's a very cool method.

However, I've noticed what may be a technical bug where on some graphs, where I have found a non-zero Gromov distance even when the underlying graphs are identical. I suspect there may some inherent structural basis behind the observation since some random graphs always seem to reach 0 and other structures never do.

Some code based on the graph_transport ipython notebook:

import numpy as np
import os,sys
sys.path.append(os.path.realpath('../lib'))
from graph import graph_colors,draw_rel,draw_transp,Graph,wl_labeling
from ot_distances import Fused_Gromov_Wasserstein_distance,Wasserstein_distance
import copy
from data_loader import load_local_data,histog,build_noisy_circular_graph
import matplotlib.pyplot as plt
import networkx as nx

nxgr = nx.generators.turan_graph(8,2)
n = len(nxgr.nodes)
g1 = Graph(nxgr)
g2 = Graph(nxgr)
## some random, unimportant, node features
g1.add_attibutes({i: v for i,v in enumerate(np.random.randint(0,2,n))})
g2.add_attibutes({i: v for i,v in enumerate(np.random.randint(0,2,n))})

plt.figure(figsize=(5,4))
vmin=0
vmax=1

# plots are nice!
draw_rel(g1.nx_graph,draw=False,vmin=vmin,vmax=vmax,with_labels=False)
draw_rel(g2.nx_graph,draw=False,vmin=vmin,vmax=vmax,with_labels=False,shiftx=5,swipx=True)
plt.title('Two graphs. Color indicates the label')
plt.show()

Fused_Gromov_Wasserstein_distance(alpha=1,features_metric='dirac',method='shortest_path', verbose=True).graph_d(g1,g2)

Output is:

It.  |Loss        |Delta loss
--------------------------------
    0|8.750000e-01|0.000000e+00
    1|5.074625e-01|-3.675375e-01|9.900000e-01
    2|5.000750e-01|-7.387504e-03|9.900000e-01
    3|5.000007e-01|-7.424625e-05|9.900000e-01
    4|5.000000e-01|-7.424996e-07|9.900000e-01
    5|5.000000e-01|-7.425000e-09|9.900000e-01
    6|5.000000e-01|-7.425049e-11|9.900000e-01

I've found a few other examples on random graphs (e.g. trees) that don't seem to reach zero either.

I would appreciate and look forward to your thoughts on this.

illustration of FGW on trees

In the section 4.1, you mention an example about trees, and how can I process the FGW on trees?
May you release the relevant code about 4.1? It will be really helpful!

G.node is deprecated networkx v2

The tree_transport.ipynb is failing with

File ~/Repos/FGW/lib/graph.py:187, in Graph.all_matrix_attr(self, return_invd)
    186 def all_matrix_attr(self,return_invd=False):
--> 187     d=dict((k, v) for k, v in self.nx_graph.node.items())
    188     x=[]
    189     invd={}

AttributeError: 'Graph' object has no attribute 'node'

See the relevant change in the networkx docs: https://networkx.org/documentation/stable/release/migration_guide_from_1.x_to_2.0.html
https://github.com/tvayer/FGW/blob/master/lib/graph.py#L187

tvayer / fgw Goto Github PK

fgw's People

Contributors

Stargazers

Watchers

Forkers

fgw's Issues

Problems with the distance matrices

node attributes

Non-zero Gromov distance on identical graphs

illustration of FGW on trees

G.node is deprecated networkx v2

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent