How to load a networkx graph into GraKel

[sbonner0]

Hi There,

I'm trying to understand how one would use ones own graph data with GraKel via networkx and I am having some issues.

For example the following example code will fail:

H2O = scipy.sparse.csr_matrix(([1, 1, 1, 1], ([0, 0, 1, 2], [1, 2, 0, 0])), shape=(3, 3)) G = nx.from_scipy_sparse_matrix(H2O) graph = grakel.graph_from_networkx(G) sp_kernel.fit_transform(graph)

With this rather strange error:

AttributeError: 'int' object has no attribute 'nodes'

Any help you could provide on how to use custom data with GraKel would be most helpful! Is it required that graphs must have labels on the vertices and edges to be used?

[giannisnik]

Dear @sbonner0 ,

Thank you for your interest in GraKeL.

The graph_from_networkx() function transforms an iterable of NetworkX objects to an iterable of GraKeL's internal graph representations. Therefore, instead of: graph = grakel.graph_from_networkx(G) you should use the following: graph = grakel.graph_from_networkx([G])

Note also that GraKeL contains implementations of kernels between graphs (i.e., kernels that compare graphs to each other). Therefore, feeding a single graph to the fit_transform() function will just produce a single number (i.e., the kernel value between the input graph and itself). Furthermore, the shortest path kernel expects the input graphs to contain node labels. If they do not, you should set the parameter with_labels=False.

[sbonner0]

Great thanks, this works now! It might be worth updating your documentation on your webpage to make this a bit more clear for everyone.

As an aside, how many graphs and at what scale would you expect the kernels to be able to work on? For example, I have a set of 50,000 graphs of 100,000 vertices each, would you expect that I would be able to use GraKel to process this?

[giannisnik]

Dear @sbonner0 ,

Your graphs are very large. Most benchmark datasets contain graphs with up to thousands of nodes (i.e., two orders of magnitude smaller than your graphs). If your graphs are unlabeled, then you can use the graphlet kernel (but you need to make sure that you set the number of samples to some large value). If your graphs are also sparse, then I guess that the Weisfeiler-Lehman subtree kernel and the shortest path kernel can also handle your dataset. You can give it a try.

With regards to the number of graphs, 50,000 is quite a large number. This would correspond to a 50,000 X 50,000 gram matrix which may not fit in your main memory. Therefore, I would suggest that you use the Nystrom method and generate a low-dimensional representation for each graph (see the corresponding section here: https://ysig.github.io/GraKeL/dev/user_manual/longer_introduction.html).

[sbonner0]

This is great, thanks for all your help and work on GraKel.

[safreita1]

Hi @giannisnik ,

I have a similar setup--many undirected large graphs with no attributes--and had a question regarding the use of the Weisfeiler-Lehman subtree and the shortest path kernel setup. I have a list of networkx graphs that I'm sending to:

graphs = graph_from_networkx(nx_graphs)

then initializing the kernel as:

gk = GraphKernel(kernel=[{"name": "subtree_wl"}, {"name": "shortest_path", "normalize": True, "with_labels": False}])

and then finally calling:

gk.fit_transform(x_train)

However, I'm running into an error "AttributeError: 'NoneType' object has no attribute 'values'" in line 110, in parse_input for (label, frequency) in iteritems(Counter(itervalues(L))):

Any ideas what I'm doing wrong here?

[giannisnik]

Hi @safreita1 ,

The problem is that WL expects the nodes of the graphs to be annotated with discrete labels. To run the kernel, you can just assign the same discrete label to all the vertices. See for instance the following example:

G1 = nx.cycle_graph(3)
nx.set_node_attributes(G1, {0:'a', 1:'a', 2:'a'}, 'label')

G2 = nx.cycle_graph(4)
nx.set_node_attributes(G2, {0:'a', 1:'a', 2:'a', 3:'a'}, 'label')

G3 = nx.cycle_graph(5)
nx.set_node_attributes(G3, {0:'a', 1:'a', 2:'a', 3:'a', 4:'a'}, 'label')

nx_graphs = [G1, G2, G3]

graphs = graph_from_networkx(nx_graphs, node_labels_tag='label')

gk = GraphKernel(kernel=[{"name": "weisfeiler_lehman", "n_iter": 5}, {"name": "shortest_path"}], normalize=True)
K = gk.fit_transform(graphs)

The above code computes the WL shortest path kernel. It is not clear to me if you want to compute this kernel or if you want to compute the WL subtree kernel and separately, the shortest path kernel. Note that the latter can be computed even if the nodes of the graphs are unlabeled.

[safreita1]

Thanks for the great example @giannisnik!

My primary goal is a kernel that can work with many large graphs (e.g., 50k nodes). Now that I'm re-reading your post a few messages above, I realize that you were probably saying you can use either the Weisfeiler-Lehman subtree kernel or the shortest path kernel to handle a dataset this large.

For the graphlet kernel, would the default parameters suffice or do you recommend a specific setup?

[giannisnik]

Dear @safreita1 ,

These graphs are indeed very large. These kernels have mainly been applied to much smaller graphs. But if the graphs are sparse, I guess that some kernels can handle them. See below how you can compute the two kernels: the shortest path kernel and the WL subtree kernel.

graphs = graph_from_networkx(nx_graphs)

sp_kernel = GraphKernel(kernel=[{"name": "shortest_path", "with_labels": False}], normalize=True)
K = sp_kernel.fit_transform(graphs)
print(K)

graphs = graph_from_networkx(nx_graphs, node_labels_tag='label')

wl_subtree_kernel = GraphKernel(kernel=[{"name": "weisfeiler_lehman", "n_iter": 5}, {"name": "subtree_wl"}], normalize=True)
K = wl_subtree_kernel.fit_transform(graphs)
print(K)

With regards to the graphlet kernel, since the graphs are very large, it would be infeasible to extract all graphlets. Thus, you need to perform sampling as follows.

graphs = graph_from_networkx(nx_graphs)

graphlet_kernel = GraphKernel(kernel=[{"name": "graphlet_sampling", "sampling": {"n_samples":100}}], normalize=True)
K = graphlet_kernel.fit_transform(graphs)
print(K)

Note that the above code samples 100 graphlets of size from 3 to 5 from each graph. In your case, since the graphs are very large, 100 samples is not enough. You should sample a much larger number of graphlets. Note also that as you increase the number of samples, the running time of the kernel also increases.

[safreita1]

Thank you for all your assistance, it's been incredibly helpful. Great job on this library!