GRAIN: Multi-Granular and Implicit Information Aggregation Graph Neural Network for Heterophilous Graphs

Graph neural networks (GNNs) have shown significant success in learning graph representations. However, recent studies reveal that GNNs often fail to outperform simple MLPs on heterophilous graph tasks, where connected nodes may differ in features or labels, challenging the homophily assumption. Existing methods addressing this issue often overlook the importance of information granularity and rarely consider implicit relationships between distant nodes. To overcome these limitations, we propose the Granular and Implicit Graph Network (GRAIN), a novel GNN model specifically designed for heterophilous graphs. GRAIN enhances node embeddings by aggregating multi-view information at various granularity levels and incorporating implicit data from distant, non-neighboring nodes. We also introduce an adaptive graph information aggregator that efficiently combines multi-granularity and implicit data, significantly improving node representation quality, as shown by experiments on 13 datasets covering varying homophily and heterophily. GRAIN consistently outperforms 12 state-of-the-art models, excelling on both homophilous and heterophilous graphs. Introduction Graph Neural Networks (GNNs) (Welling and Kipf 2016) are a specialized class of deep neural networks designed to process and analyze graph-structured data. GNNs capitalize on the inherent properties of graphs, where entities are represented as nodes and their relationships as edges, to effectively capture complex interdependencies between entities. By employing iterative message-passing and aggregation mechanisms, GNNs iteratively update each node's representation by combining its features with those of its neighbors. This process enables GNNs to learn sophisticated and informative embeddings that are highly effective for a variety of graph-based machine learning tasks, such as node classification (He et al. 2024), link prediction (Lu et al. 2023), and graph classification (Zhao et al. 2024), often surpassing the performance of traditional neural networks. GNNs have also demonstrated remarkable success across a broad spectrum of real-world applications, including social network analysis (Zhang et al. 2022), recommendation systems (Agrawal et al. 2024), and drug discovery* Corresponding author. However, the primary reason GNNs excel in many tasks--their reliance on the homophily assumption--also presents a significant limitation.