Efficient Global Message Passing for Heterophilous Graphs

We investigate Graph Neural Networks (GNNs) on heterophilous graphs for node classification. To address the scarcity of useful local information in heterophilous neighborhood, it is often essential to explore global interactions. However, many existing methods in this endeavor are computationally expensive and may suffer from issues like oversquashing. In addition, earlier studies show that GNNs can be outperformed by Multi-Layer Perceptrons on heterophilous graphs, indicating insufficient exploitation of node feature information. To address these limitations, we propose Prototype Mediated GNN (PM-GNN), a novel framework which efficiently captures global feature information using class prototypes. PM-GNN learns multiple class prototypes for each class from raw node features with a soft k-means clustering mechanism. These prototypes are then transferred onto node embeddings via explicit message passing, bypassing local neighborhoods and mitigating oversquashing. PM-GNN can scale to large graphs, outperforming strong baselines on multiple heterophilous datasets.