[Feature Request] Support local (cluster) pooling for multi-level graph coarsening task
- Dominant language
- Python
- Stars
- 14.3k
- Forks
- 3.1k
- PR merge metrics
- No merged PRs in 30d
Description
## 🚀 Feature
Support graph pooling operation on cliques.
## Motivation
Graph coarsening is common in tasks where we try to extract graph features from different scales. Usually, the input graph is partitioned into many small cliques and global pooling operations are performed in these cliques to obtain nodes in the output (coarser) graph. This global pooling on cliques, or local pooling on graphs, is also common in multi-level graph coarsening methods like [Metis](https://github.com/KarypisLab/METIS) and [Graclus](https://www.cs.utexas.edu/users/dml/Software/graclus.html). However, currently DGL does not support this operation.
An example (in PyG) can be found [here](https://github.com/rusty1s/pytorch_geometric/blob/master/examples/mnist_graclus.py#L38-L40)
## Alternatives
It is true that one can first convert graph in sparse representation into dense representation, then such a problem can be redefined as matrix multiplication problem: `X' = C^{T}X` and `A' = C^{T}AC` where `C \in \mathcal{R}^{N_{old} \times N_{new}}` is the assignment matrix. However, this is expensive for large and sparse graphs.
An implementation for PyG can also be found [here](https://github.com/rusty1s/pytorch_geometric/blob/452ada5cbcfa856d16ae6252ab429bb99f17947e/torch_geometric/nn/pool/max_pool.py#L46)
## Pitch
Given two tensor `c` and `x`, where element in `c` is a clique label for each node (which clique does this node belongs to) and `x` is node feature tensor. And also given the graph `g`. Output the coarser graph and node features.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.