MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks
This addresses the need for effective pooling methods in graph neural networks, especially for heterophilic graphs, but appears incremental as it builds on existing MAXCUT and pooling concepts.
The paper tackled the problem of computing MAXCUT in attributed graphs to enable hierarchical graph pooling in Graph Neural Networks, resulting in a sparse, trainable end-to-end layer that is particularly suitable for heterophilic graphs.
We propose a novel approach to compute the MAXCUT in attributed graphs, i.e., graphs with features associated with nodes and edges. Our approach works well on any kind of graph topology and can find solutions that jointly optimize the MAXCUT along with other objectives. Based on the obtained MAXCUT partition, we implement a hierarchical graph pooling layer for Graph Neural Networks, which is sparse, trainable end-to-end, and particularly suitable for downstream tasks on heterophilic graphs.