Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods

By Derek Lim, Felix Hohne, Xiuyu Li, Sijia Huang, Vaishnavi Gupta, Omkar Bhalerao, Ser-Nam Lim. Neural Information Processing Systems, 2021

492 citations recorded by the source corpus.

Many widely used datasets for graph machine learning tasks have generally been homophilous, where nodes with similar labels connect to each other. Recently, new Graph Neural Networks (GNNs) have been developed that move beyond the homophily regime; however, their evaluation has often been conducted on small graphs with limited application domains. We collect and introduce diverse non-homophilous datasets from a variety of application areas that have up to 384x more nodes and 1398x more edges than prior datasets. We further show that existing scalable graph learning and graph minibatching techniques lead to performance degradation on these non-homophilous datasets, thus highlighting the need for further work on scalable non-homophilous methods. To address these concerns, we introduce LINKX -- a strong simple method that admits straightforward minibatch training and inference. Extensive experimental results with representative simple methods and GNNs across our proposed datasets show that LINKX achieves state-of-the-art performance for learning on non-homophilous graphs. Our codes and data are available at https://github.com/CUAI/Non-Homophily-Large-Scale.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/089bb1ecce75936eda1890f8e40a56d4c811dd33

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Management Science and Operations Research

Citations in the corpus

Revisiting Heterophily For Graph Neural Networks (2022, background): “Structure information channel and residual connection Besides the filtered features, some recent SOTA models additionally use graph structure information, i.e., MLP✓(A), and residual connection to address heterophily problem, e.g., LINKX [25] and GloGNN [24].”
A critical look at the evaluation of GNNs under heterophily: are we really making progress? (2023, methodology): “To ﬁx these issues, Lim et al. (2021) propose another homophily measure.”
Is Homophily a Necessity for Graph Neural Networks? (2021, background): “Due to this neighborhood aggregation mechanism, several existing works posit that many GNNs implicitly assume strong homophily and homophily is critical for GNNs to achieve strong performance on SSNC (Zhu et al., 2020b;a; Chien et al., 2021; Maurya et al., 2021; Halcrow et al., 2020; Lim et al., 202”
Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks (2021, background): “The second limitation of GCNs is their poor performance on heterophilous graphs (Pei et al., 2019; Lim et al., 2021), which—unlike homophilous graphs—have many neighboring nodes that belong to different classes (Newman, 2002).”
Finding Global Homophily in Graph Neural Networks When Meeting Heterophily (2022, methodology): “Meanwhile, we run the experiments of 6 large-scale datasets on a single Tesla V100 GPU with 32G memory and use AdamW as the optimizer following (Lim et al., 2021).”