dmlc / dmlc/dgl

[Feature Request] Support local (cluster) pooling for multi-level graph coarsening task

Open
#2,599 6 comments 1 reaction 1 assignee Claimed by @jermainewang View on GitHub
feature request
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.