[FEA] Ego graphs

[cj2001]

Is your feature request related to a problem? Please describe.
It would be very helpful if cugraph could have the ability to calculate the ego graph to a provided radius, as is done in networkx via https://networkx.github.io/documentation/stable/reference/generated/networkx.generators.ego.ego_graph.html?highlight=ego_graph#networkx.generators.ego.ego_graph.

Describe the solution you'd like
Given a graph, the user would provide a series of required and optional values, just like networkx.generators.ego.ego_graph. From there, the method returns a subgraph of neighbors, centered at the given node, within a given radius.

Describe alternatives you've considered
This can be done in networkx but is rather slow, particularly if you want to do it for multiple target nodes. This would lend itself well to parallelization.

Task List
Unknown.

Additional context
None

[pgera]

If you only need the vertices in the resultant subgraph, you can currently use SSSP's output and filter any distance ranges in cudf. That does only out-neighbours though. If you need in-neighbours as well, you would need the extra step of running SSSP on the transpose graph. If the graph is unweighted, you can replace SSSP with BFS.

[BradReesWork]

Great request. We will get this added to our schedule.
A work-around would be to run BFS from the egonode, filter down to just the list of 1-hop neighbors. Then use that list, plus the edge node, to perform a Subgraph Extraction.

Since I have a personal bias towards ego-based community detection, getting ego-graphs is something that is on the roadmap.

[cj2001]

Great to hear that others might be interested in this feature! I have something that works just via numpy arrays out to a radius of 2. But sometimes you just need to be able to go beyond that, a la 6 Degrees of Kevin Bacon and want to be able to select in-neighbors, out-, or both.

[inc0]

A work-around would be to run BFS from the egonode, filter down to just the list of 1-hop neighbors. Then use that list, plus the edge node, to perform a Subgraph Extraction.

This would work, but (unless I'm mistaken) would perform a lot of unnecessary computation if it searches deeper than our ego goal.

Could we add something like max_depth argument to BFS? That + returning all searched steps would, in effect, give us ego graph.

[BradReesWork]

Added to release 0.11 for design dicussion

[geoHeil]

Has there been any progress? I would also love to see this feature!

In case it is helpful for someone else:

karate = pd.read_csv('karate.csv', header=None, sep=' ')
karate.columns = ['src', 'dst', 'weights']
karate = cudf.from_pandas(karate)

G_karate = cugraph.DiGraph() 
G_karate.from_cudf_edgelist(karate, source='src', destination='dst', edge_attr='weights', renumber=False)

# let's construct the EGO network of a user.
ego_id = 1
ego_network_level = 2
cudf_res = cugraph.bfs(G_karate, ego_id)
ego_candidates = cudf_res[cudf_res.distance <= ego_network_level].vertex
subG = cugraph.subgraph(G_karate, ego_candidates)

print("Subgraph")
print("\tNumber of Vertices: " + str(subG.number_of_vertices()))
print("\tNumber of Edges:    " + str(subG.number_of_edges()))


edges_g_sub = subG.view_edge_list()
edges_g_sub.head()

[geoHeil]

But: in the example above I get the expected output i.e. that the ego_id node is part of the output. However, for a directed graph (DiGraph):

ego_network_level = 2
cudf_res = cugraph.bfs(G, ego_id)
ego_candidates = cudf_res[cudf_res.distance <= ego_network_level].vertex

## it is still here
print(ego_candidates[ego_candidates.index == ego_id])

subG = cugraph.subgraph(G, ego_candidates)

print("Subgraph")
print("\tNumber of Vertices: " + str(subG.number_of_vertices()))
print("\tNumber of Edges:    " + str(subG.number_of_edges()))

edges_g_sub = subG.view_edge_list()

# but thy is it empty now?
edges_g_sub[(edges_g_sub.src == ego_id) | (edges_g_sub.dst == ego_id)]

an empty set is returned when querying for the ego_id vertex. What is wrong here?

cugraph.subgraph(G, cudf.Series([ego_id])).view_edge_list()

also returns an empty set even though:

there obviously are some edges for this ego node.

[geoHeil]

here is an example code.
I had to manually filter the edges - the subgraph operation somehow is NOT including the original ego node, even though it would be included in the candidate list.

karate = pd.read_csv('karate.csv', header=None, sep=' ')
karate.columns = ['src', 'dst', 'weights']
# display(karate.head())
karate = cudf.from_pandas(karate)

G_karate = cugraph.DiGraph() 
G_karate.from_cudf_edgelist(karate, source='src', destination='dst', edge_attr='weights', renumber=False)


# let's construct the EGO network of a user.
ego_id = 1

def make_ego_csv(level):
    cudf_res = cugraph.bfs(G_karate, ego_id)
    ego_candidates = cudf_res[cudf_res.distance <= level].vertex
    print(ego_candidates.shape)
    sub_edges_g = karate[(karate.src.isin(ego_candidates) | karate.dst.isin(ego_candidates))]
    sub_edges_g.columns = ['Source', 'Target', 'Weight']
    print(sub_edges_g.shape)
    if level > 1:
        sub_edges_g.drop(['Weight']).to_csv(f"ego_{level}_graph.csv", index=False)
    else:
        sub_edges_g.to_csv(f"ego_{level}_graph.csv", index=False)
        
    print('**********')

sub_edges_g = make_ego_csv(0)
make_ego_csv(1)
make_ego_csv(2)