dmlc / dmlc/dgl

subgraph API that supports specified src&dst nodes

Open
#4,113 3 comments 0 reactions 0 assignees View on GitHub
feature request
Dominant language
Python
Stars
14.3k
Forks
3.1k
PR merge metrics
No merged PRs in 30d

Description

## 🚀 Feature
Hi, as far as I know currently DGL doesn't support such a subgraph operation:
* input: graph $G$, certain source nodes set $S$ and destination nodes set $D$
* output: a subgraph that contains all edges (u,v) in $G$ with $u \in S$ and $v \in D$

From the perspective of underlying adjacency matrix, the proposed api supports arbitrary "rectangular" slice on the square adjacency matrix.

## Motivation

Some certain GNN sampling strategies require to build a subgraph with given src and dst nodes. For example, FastGCN independently chooses some nodes in each layer. When we have selected the nodes, we need to construct the message-passing subgraph for each layer with given src&dst nodes, then the proposed subgraph api can help.

## Implementation Details

Actually I have already implemented a naive `dgl.rect_subgraph(graph, src_nodes, dst_nodes` api in my own repo. I reused the `aten::CSRSliceMatrix` which already supports slicing adjacency matrix with given src&dst nodes with CUDA/CPP.

The proposed api can support the FastGCN sampler in #3849 (but it can actually do more).
If such api is considered worthy to be added, I am willing to contribute, thanks!

## Alternatives

## Pitch

## Additional context

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.