  Graph Neural Networks often struggle with long-range information propagation
and in the presence of heterophilous neighborhoods. We address both challenges
with a unified framework that incorporates a clustering inductive bias into the
message passing mechanism, using additional cluster-nodes. Central to our
approach is the formulation of an optimal transport based implicit clustering
objective function. However, the algorithm for solving the implicit objective
function needs to be differentiable to enable end-to-end learning of the GNN.
To facilitate this, we adopt an entropy regularized objective function and
propose an iterative optimization process, alternating between solving for the
cluster assignments and updating the node/cluster-node embeddings. Notably, our
derived closed-form optimization steps are themselves simple yet elegant
message passing steps operating seamlessly on a bipartite graph of nodes and
cluster-nodes. Our clustering-based approach can effectively capture both local
and global information, demonstrated by extensive experiments on both
heterophilous and homophilous datasets.
