PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, Ser-Nam Lim

arXiv:2110.14446v1cs.LGcs.SIstat.ML

TL;DR

Non-homophilous graph learning lacks large, diverse benchmarks and scalable methods, limiting evaluation beyond small datasets. The paper introduces larger datasets, benchmarks existing approaches, and proposes LINKX, a simple minibatch-compatible model. LINKX significantly outperforms other methods on the proposed datasets, while the study remains limited to transductive node classification and does not directly generalize to inductive classification.

  • Problem

    Non-homophilous graph learning lacks large, high-quality datasets across applications, while existing scalable methods and minibatching techniques perform poorly in this setting.

  • Method

    The paper collects diverse large non-homophilous datasets, benchmarks graph learning and minibatching methods, and introduces LINKX, which separately embeds adjacency and node features before combining them.

  • Results

    LINKX significantly outperforms other methods on the proposed datasets and avoids the minibatch performance degradation observed for other methods.

  • Takeaways & Limitations

    The datasets provide tools for evaluating scalable learning on non-homophilous graphs and motivate further research in this underexplored area.

  • Takeaways & Limitations

    The study focuses on transductive node classification; LINKX does not directly generalize to inductive node classification, and link prediction is left for future work.

Abstract

from arXiv · show

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.

1 Introduction

The paper identifies a lack of large, diverse benchmarks and scalable methods for non-homophilous graph learning, then introduces LINKX as a simple response.

  • Motivation: Non-homophilous graph learning lacks large, high-quality datasets spanning diverse applications.Existing evaluations rely on small datasets with narrow application coverage and high train/test-split variance.
  • Contributions: The paper collects diverse large non-homophilous datasets and benchmarks 14 graph learning methods with 3 minibatching techniques.The datasets cover wider application areas and different complex label-topology relationships than prior benchmarks.
  • Scalability challenges: Existing scalable methods and graph minibatching techniques substantially degrade performance in non-homophilous settings.Methods such as SGC, C&S, and GraphSAINT perform poorly despite strong results on many homophilous benchmarks.
  • LINKX: LINKX separately embeds adjacency and node features, combines them with multilayer perceptrons, and supports minibatched training and inference.The method generalizes node-feature MLP and LINK regression while avoiding the performance degradation observed with other minibatch methods.
  • LINKX: The paper reports that LINKX achieves excellent results for non-homophilous graphs while addressing minibatching issues.Its design is presented as simple to train and evaluate in minibatched fashion.

2 Prior Work

Prior work includes GNNs, scalable graph methods, and graph sampling techniques, but many rely on homophily or incur scalability costs in non-homophilous settings.

  • Graph representation learning: Many GNNs use neighborhood aggregation or low-pass filtering that implicitly relies on homophily.These mechanisms smooth features across graph topology and often fail to generalize on non-homophilous graphs.
  • Scalable methods: Scalable graph learning methods often exploit homophily to achieve strong performance with simple, inexpensive models.The same methods are unable to achieve comparable performance in non-homophilous settings.
  • Graph sampling: Graph sampling methods scale GNNs by sampling nodes or subgraphs before neighborhood aggregation.These approaches address the absence of ordinary i.i.d. minibatching in graph learning.
  • Non-homophilous methods: Non-homophilous GNNs use strategies including geometric aggregation, mixed adjacency powers, signed propagation weights, and deeper networks.These methods include Geom-GCN, MixHop, GPR-GNN, GCNII, and H2GCN.
  • Non-homophilous methods: Higher-order neighborhoods, separated ego and neighbor information, and multiscale graph information strengthen non-homophilous performance but reduce scalability.These recurring design choices require additional overhead.
  • Datasets: Widely used graph benchmarks are predominantly homophilous, leaving no comparable high-quality benchmark suite for non-homophilous methods.Citation networks and most Open Graph Benchmark node-classification datasets tend to be homophilous.

3 Datasets for Non-Homophilous Graph Learning

The paper develops larger, more diverse non-homophilous benchmarks, improves homophily measurement, and defines tasks across social, citation, patent, and Wikipedia graphs.

  • Existing datasets: Prior non-homophilous benchmarks are very small, ranging from 180–250 nodes for Cornell, Texas, and Wisconsin to 7,600 nodes for Actor.Their evaluation also suffers from high variance across train/test splits.
  • Homophily measurement: The paper argues that edge homophily is sensitive to class count and class imbalance, which can make its interpretation misleading.Under label-independent random wiring, expected edge homophily depends on class proportions and can be high for imbalanced classes.
  • Homophily measurement: The proposed metric measures excess homophily relative to a null model with randomly wired edges.It captures presence of homophily but does not distinguish among different non-homophilous relationships.
  • Homophily measurement: The metric lies in [0, 1], with 1 corresponding to a fully homophilous graph and approximately 0 expected when edges are independent of labels.Class-wise positive deviations from the null expectation mitigate class-imbalance effects.
  • Proposed datasets: The paper extends prior datasets and introduces tasks with node features and labels for social networks, citation networks, patents, and Wikipedia.Examples include gender, account, explicit-content, publication-year, patent-year, and page-view prediction.
  • Proposed datasets: The proposed datasets are up to 384x larger in nodes and 1398x larger in edges than prior non-homophilous datasets.Their homophily measures, model performance, and compatibility matrices indicate non-homophilous structure.

4 LINKX: A New Scalable Model

LINKX is a scalable node-classification model for non-homophilous graphs that separately embeds adjacency and node features before combining them. Its design supports simple minibatching while avoiding repeated graph propagation in later layers.

  • LINKX targets scalable node classification in non-homophilous settings using MLPs and linear transformations.
  • Motivation from two simple baselines: LINK regression uses adjacency columns as node features, relating each node’s prediction to two-hop paths through its neighbors.The logit sums learned weights associated with one-hop neighbors, producing a two-hop interpretation.
  • LINKX: LINKX separately embeds adjacency A and node features X, then mixes their hidden representations with a linear transformation, skip connections, and nonlinearities.This extends LINK with node-feature information while preserving separate adjacency and feature signals.
  • Design rationale: Separating adjacency and feature embeddings makes LINKX resemble a fusion architecture that treats graph structure and node features as separate modalities.
  • Complexity Analysis: LINKX avoids edge-dependent costs in later layers because adjacency is compressed into hidden vectors after its first linear mapping.Additional MLP layers add O(d^2) cost rather than requiring graph propagation across |E| edges.
  • Simple minibatching: LINKX supports standard i.i.d. node minibatching because graph information enters through adjacency-matrix columns used as features.
  • Complexity Analysis: Higher-order neighborhoods and additional hidden embeddings can increase the computational or memory overhead of non-homophilous methods.H2GCN’s squared adjacency can make memory requirements intractable even for medium-sized graphs.

5 Experiments

Experiments on large non-homophilous datasets compare simple methods, GNNs, and minibatching strategies under shared evaluation splits. LINKX performs strongly in full-batch settings and retains its advantage with simple node minibatching, while graph sampling degrades competing methods.

  • Experimental setup: Experiments use full-batch and minibatch training, with large datasets imposing substantial GPU-memory limits on model size.All graph-based methods run out of memory on the wiki dataset even on 24 GB GPUs, so wiki appears only in minibatching results.
  • Methods: The benchmark evaluates graph-agnostic baselines, node-feature-agnostic methods, scalable methods, and representative GNN minibatching approaches.
  • Training and evaluation: Performance is reported over five shared random 50/25/25 train/validation/test splits, using ROC-AUC for the class-imbalanced genius dataset.
  • Full-Batch Results: The proposed datasets provide better run-to-run stability than earlier datasets, while non-homophilous GNNs usually perform well but not universally.
  • Full-Batch Results: Homophily-based SGC and C&S typically perform relatively poorly, although two-hop variants generally improve over one-hop counterparts.
  • Full-Batch Results: The larger benchmarks expose a sharper scalability–performance tradeoff, with some methods encountering memory issues.
  • Full-Batch Results: LINKX achieves superior performance on all datasets by combining LINK’s graph-topology strength with node features when they add information.
  • Minibatching Results: Cluster-GCN and GraphSAINT sampling substantially degrade competing methods relative to full-batch training on the proposed datasets.

6 Discussion and Conclusion

The paper introduces large-scale non-homophilous datasets and LINKX, a simple scalable method that significantly outperforms other methods on these datasets. It also identifies transductive node classification and broader societal impacts as important boundaries and considerations.

  • The paper proposes high-quality non-homophilous datasets and benchmarks simple baselines and graph representation learning methods across them.
  • LINKX significantly outperforms other methods on the proposed datasets, providing a scalable method for non-homophilous graph learning.
  • The work is limited to transductive node classification, while inductive node classification and link prediction remain outside its demonstrated scope.
  • The datasets and LINKX could support malicious-node detection in social and transaction networks where non-homophilous structures are present.
  • Potential negative consequences include misuse by powerful actors, disparate effects across intersectional groups, and privacy risks from online user-information collection.

Checklist

The checklist records reproducibility, asset documentation, ethics, and evaluation reporting, while the paper also introduces tools for measuring label-topology relationships and characterizing non-homophilous datasets.

  • Checklist: The authors report providing code, data, reproduction instructions, training details, and standard deviations across multiple experimental runs.
  • Checklist: The paper states that existing assets are cited, licenses are documented, and proposed datasets and reproducing code are included in supplementary materials.
  • Checklist: The authors state that they discuss consent, personally identifiable information, offensive content, and potential negative societal impacts where applicable.
  • Measuring Homophily: Compatibility matrices capture finer label-topology details than a single scalar, with H_kl measuring the proportion of edges from class k to class l.
  • Measuring Homophily: The proposed datasets exhibit varied structures, including lower-triangular citation patterns, rank-based wiki links, and gender-related heterophily in Pokec.
  • Measuring Homophily: The introduced scalar measure is intended to better capture homophily than existing metrics when compatibility matrices are unwieldy.

A.2 Homophilous Data Statistics

The paper contrasts widely used homophilous benchmarks with diverse datasets exhibiting other label-topology relationships, while noting that dataset scale and context differ substantially across collections.

  • Homophilous datasets: Cora, CiteSeer, PubMed, ogbn-arXiv, and ogbn-products are highly homophilous, with diagonally dominant compatibility matrices and high homophily measures.
  • Homophilous datasets: The collected OEIS dataset remains homophilous across time-period classes because related entries tend to cite one another.
  • Dataset comparisons: Previously used non-homophilous datasets are much smaller and may contain class imbalance that makes edge homophily misleading.
  • Dataset contexts: The proposed datasets represent contexts including gender relations, web connections, malicious nodes, temporal citations, biological structures, and online-user attributes.
  • Dataset contexts: Developing methods that handle non-homophilous structures is important for future applications across these varied contexts.

A.5 Class-Imbalance and Metrics

The appendix examines class imbalance and higher-order neighborhoods, showing that edge homophily can be misleading while the proposed metric remains stable and two-hop homophily is comparable or higher.

  • Class-Imbalance and Metrics: Edge homophily increases as classes become more imbalanced, whereas the proposed measure remains mostly constant on label-independent random graphs.The random graphs use Erdős-Rényi edges independent of randomly assigned labels, with two classes, 100 nodes, and edge probability .25.
  • Higher-Order Neighborhoods: The two-hop neighborhood definition uses nodes exactly two hops away and compares same-class neighbors with the reference node.The appendix presents the corresponding count and normalization terms for the sampled estimate.
  • Higher-Order Neighborhoods: Two-hop node homophily is estimated by sampling k = 500 nodes while retaining each sampled node’s original two-hop neighborhood.The resulting two-hop measure is mostly similar to or somewhat higher than standard one-hop node homophily.

B Experimental Details

The experiments evaluate numerous graph methods under full-batch and minibatch settings, using tuned hyperparameter grids and method-specific training configurations. LINKX separately embeds adjacency and node features, and this generally outperforms direct concatenation.

  • Full-Batch Training: Full-batch experiments select hyperparameters by validation performance using method-specific grids, with default AdamW, weight decay .001, and learning rate .01.GNNs generally use dropout .5 and BatchNorm in each layer unless otherwise stated.
  • Methods and Grids: The evaluated methods include MLP, LINK, LINKX, label propagation, SGC, C&S, GCN variants, GAT variants, APPNP, H2GCN, MixHop, GPR-GNN, and GCNII.The study reports experiments with 14 graph learning methods and three graph minibatching techniques.
  • LINKX: LINKX uses one-layer linear mappings for MLPA and MLPX, with hidden dimension d ∈ {16, 32, 128, 256} and one to three MLPf layers.The method separately embeds adjacency A and features X rather than directly concatenating them.
  • Minibatching Setup: Minibatch training fixes GNN hidden dimension to 128, while MLP, LINK, and LINKX use standard minibatches with batch size n/10.Cluster-GCN partitions graphs into 200 parts, and GraphSAINT uses node or random-walk subgraph sampling.
  • Training Cost: Across minibatch training, MLP, LINK, and LINKX process about 50n total nodes, compared with 500n for Cluster-GCN.The reported training budgets differ substantially across the minibatching methods.

C.2 Minibatching experiments

The minibatching experiments compare homophilous and non-homophilous labels on the same arXiv graph. GraphSAINT shows more substantial degradation with non-homophilous labels, while higher-order structure and smaller GNN–MLP gaps help explain the difficulty.

  • Homophilous vs Non-Homophilous: GraphSAINT’s percent relative test-accuracy error is more substantial for non-homophilous arXiv-year labels than homophilous ogbn-arXiv labels.The comparison uses the same ogbn-arXiv graph with two different label sets.
  • Homophilous vs Non-Homophilous: Cluster-GCN shows mostly comparable minibatching degradation between the homophilous and non-homophilous arXiv experiments.This contrasts with the stronger difference observed for GraphSAINT.
  • Possible Mechanisms: Higher-order neighborhood information can be important for non-homophilous classification, but minibatching can make preserving that structure difficult.This provides one proposed explanation for poor minibatch performance in these settings.
  • Possible Mechanisms: Similar relative minibatching error can still be more detrimental in non-homophilous graphs because GNNs often have a smaller advantage over topology-agnostic MLPs.MLPs trained with i.i.d. node minibatches do not face much performance degradation.

C.3 Experiments on Prior Datasets

Experiments on prior small non-homophilous datasets use fixed splits and selected reruns for comparison, but the appendix finds these evaluations noisy and weakly informative about broader method rankings. LINKX performs well on datasets with thousands of nodes but falls short on the tiniest graphs.

  • Prior-Dataset Evaluation: The prior-dataset comparison uses the 10 fixed splits from Pei et al., with reruns for methods lacking official-split results or evaluations on specific datasets.GPR-GNN and GCNII required reruns under the comparison protocol.
  • Results: LINKX performs well on datasets with thousands of nodes but falls short on the tiniest datasets.The appendix cautions that performance on these small benchmarks is noisy and highly dependent on hyperparameter grid selection.
  • Results: Method rankings on prior small datasets do not necessarily transfer to the proposed large non-homophilous datasets.MixHop performs best among the reported non-homophilous GNNs on the new datasets but poorly on the prior ones, while H2GCN shows the opposite pattern.
  • Scalability: H2GCN achieves excellent performance on the proposed datasets but runs out of memory on even medium-sized datasets because of its design choices.This illustrates a scalability limitation despite strong benchmark performance.
  • Homophilous Datasets: LINKX is also evaluated on Cora, Citeseer, and Pubmed using standard 48/32/20 train, validation, and test proportions.These experiments concern homophilous datasets and use the LINKX hyperparameter grid from the appendix.

D.2 Dataset Properties

The benchmark spans social, academic, patent, and Wikipedia graphs, with node features and classification labels tailored to each application. The wiki dataset additionally uses a documented crawl, text embeddings, and page-view quintiles.

  • Social networks: Penn94 and Pokec are friendship networks whose nodes represent users or students and whose labels are reported gender.Penn94 uses university-student attributes, while Pokec derives features from profile information.
  • Academic papers: arXiv-year labels arXiv papers by posting year using title-and-abstract word2vec features and five approximately balanced classes.Directed edges represent citations.
  • Patents: snap-patents represents US utility patents with citation edges, metadata features, and five classes defined by patent grant time.
  • Online platforms: genius predicts whether users are marked on a song-lyrics annotation network, while twitch-gamers predicts whether Twitch channels have explicit content.The genius labels include accounts marked “gone,” and Twitch features include account activity and metadata.
  • Wikipedia: wiki links Wikipedia articles, uses averaged title-and-abstract GloVe embeddings, and partitions 60-day page views into five classes.The graph was collected by breadth-first search and cleaned by pruning edges involving pages outside the article subset.
Loading 2110.14446v1…