HEX-GNN: Hierarchical EXpanders for Node Classification

Graph Neural Networks (GNNs) are efficient in learning expressive representations of structured data such as graphs. Recent studies have been focused on addressing heterophily, a common phenomenon in real-world networks, which challenges the homophilic assumption that nodes of the same class are more likely to connect, thus limiting the applicability of conventional GNNs in tasks like node classification. However, existing methods designed for dealing with heterophily still lack effectiveness in some typical heterophilic datasets. Furthermore, finding the optimal combination of node features and graph topology under the heterophilic regime is still an open issue. In this paper, we propose an adaptive GNN architecture for dealing both with homophilic and heterophilic datasets. This architecture leverages the power of expander graphs as a means of effective message propagation (the underlying mechanism of GNNs). In short, we selectively densify the GNN at different hierarchical orders and then find the optimal combination of embeddings. Finally, we test this new approach by performing experiments over different state-of-the-art datasets with a wide range of levels of heterophily and a wide range of sizes.