K-hop path between two nodes for a heterogeneous graph

Questions
#1

Given two nodes, how to find the k-hop path between them?

#2

Hi yudizhangzyd, I am wondering why do you need this util? Do you want to get all k-hop path (with nodes in order) or just the number of k-hop path? Thanks.

#3

Networkx has API to get all the simple paths given two nodes all_simple_paths — NetworkX 3.0 documentation . You can then filter the k-hop paths upon that.

#4

Hi frozenbugs, all paths is what I want.

#5

I found it is not easy to convert dgl a heterogeneous graph to Networkx graph, does dgl provide such function? Would to_homogeneous and to_networkx work?

#6

It is indeed not supported but we could add that! The question we have is what is the proper/most-intuitive way to represent a heterogeneous graph in networkx? We’d be really appreciated if you could give us a simple example.

#7

That’s a good question. In my case, my heterogeneous graph is actually a relational graph. So nodes can have different types (such as human, address, phone number, etc) and I don’t care about the edges, perhaps just set different node attributes in networkx?
Not sure if that would be scalable very well.

#8

Yes, I think setting node/edge attributes is the simplest. For example, to create a user-item graph with two relations “follow” and “like”:

Idea 1 Set the “type” attributes of nodes and edges.

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_node(0, type="user")
>>> G.add_node(1, type="user")
>>> G.add_node(2, type="user")
>>> G.add_node(3, type="item")
>>> G.add_node(4, type="item")
>>> G.add_edge(0, 1, type="follow")
>>> G.add_edge(0, 2, type="follow")
>>> G.add_edge(2, 0, type="follow")
>>> G.add_edge(0, 3, type="like")
>>> G.add_edge(0, 4, type="like")
>>> G.add_edge(2, 4, type="like")

Idea 2 Set the “triples” edge attribute (rdflib’s practice)

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge(0, 1, triples=("user", "follow", "user"))
>>> G.add_edge(0, 2, triples=("user", "follow", "user"))
>>> G.add_edge(2, 0, triples=("user", "follow", "user"))
>>> G.add_edge(0, 3, triples=("user", "like", "item"))
>>> G.add_edge(0, 4, triples=("user", "like", "item"))
>>> G.add_edge(2, 4, triples=("user", "like", "item"))

BTW, as a workaround for now, you can construct such networkx graph using DGL’s to_homogeneous API to relabel all the nodes to IDs starting from 0. Below is a pseudo-code to implement idea 2:

import dgl
import networkx as nx

hg = ...  # your heterogeneous graph
g = hg.to_homogeneous()  # relabel all the nodes to IDs from 0
src, dst = g.edges()
etype_id = g.edata[dgl.ETYPE]
G = nx.DiGraph()
for u, v, etid in zip(src, dst, etype_id):
    triples = hg.canonical_etypes[etid]
    G.add_edge(u, v, triples=triples)
#9

Thanks, yeah this workaround seems to be a good solution for now. I guess this can be wrapped in a function for future generalizations. :grinning:

#10

Created a feature request to Github for tracking: Support converting heterogeneous graph to NetworkX graph · Issue #5443 · dmlc/dgl · GitHub

#11

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.