Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
Authors: Derek Lim
Felix Matthew Hohne
Xiuyu Li
Sijia Linda Huang
Vaishnavi Gupta
Omkar Prasad Bhalerao
Ser-Nam Lim
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
homophily
graphs
datasets
benchmarks

Abstract: 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.

Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
Derek Lim" Cornell University al772@cornell.edu
Felix Hohne Cornell University fuh420cornell. edu
Xiuyu Li' Cornell University x12890cornel1.. edu
Sijia Linda Huang Cornell University sh8378cornell.. edu
Vaishnavi Gupta Cornell University
Omkar Bhalerao
Ser-Nam Lim Facebook AI sernam@gmail com
Cornell University
vg2229cornel1.com edu
opb7@cornel1.cm edu
Abstract
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 variety of application areas that have up to 384x more nodes and 1398x more edges than prior datasets. We further show that existing scal- able graph learning and graph minibatching techniques lead to performance degra- dation these non-homophilous datasets, thus highlighting the need for further work on scalable non-homophilous methods. To address these concerns, we intro- duce LINKX strong simple method that admits straightforward minibatch train- ing and inference. Extensive experimental results with representative simple meth- ods 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 httpp////ggthhhhcccco////////aoa Homophi htap:///oooooooppoipaaaaaaaaaeee Lyrger Scale
com
Introduction
Graph learning methods generate predictions by leveraging complex inductive biases captured in the topology of the graph [7]. large volume work in this area, including graph neural networks (GNNs), exploits homophily as strong inductive bias, where connected nodes tend to be similar to each other in terms labels 46 3. Such assumptions of homophily, however, do not always hold true. For example, malicious node detection, key application of graph machine learning, is known to be non-homophilous in many settings [55] B 25
Further, while new GNNs that work better in these non-homophilous settings have been developed their evaluation is limited to few graph datasets used by
82
4
15
58 (collected by 6ll 66 48 that have certain undesirable properties such as small size, narrow range of application areas, and high variance between different train/test splits [82] Consequently, method scalability has not been thoroughly studied in non-homophilous graph learning. In fact, many non-homophilous techniques frequently require more parameters and computational resources &2 [7], which is neither evident detrimental when they evaluated very small datasets, Even though scalable graph learning techniques do exist, these methods generally cannot
Pei et al.
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

be directly applied to the non-homophilous setting, as they oftentimes assume homophily in their construction
Non-homophily graphs also degrades proven graph learning techniques that have been instrumental strong performance in scalable graph learning. For instance, label propagation, personalized PageRank, and low-pass graph filtering have been used for scalable graph representation learning models, but these methods all assume homophily M7l evidence that existing minibatching techniques in graph learning
Moreover, we give empirical significantly degrade performance in non- oon-homophilous settings. In response, we develop novel model, LINKX, that addresses these concerns; LINKX outperforms existing graph learning methods on large-scale non- homophilous datasets and admits simple minibatching procedure that maintains strong performance.
IC
T6 77
To summarize, we demonstrate three key areas of deficiency as mentioned above, namely: (1) that there a lack of large, high-quality datasets covering different non-homophilous applications, (2) that current graph minibatching techniques and scalable methods do not work well non-homophilous settings, and (3) that prior non con-homophilous methods are scalable. To these ends, this paper makes the following contributions:
Dataset Collection and Benchmarking. We collect diverse series of large, non-homophilous graph datasets and define new node features and tasks for classification. These datasets are substantially larger than previous non-homophilous datasets, span wider application areas, and capture different types of complex label-topology relationships. With these proposed datasets, we conduct extensive experiments with 14 graph learning methods and graph minibatching techniques that broadly representative the graph machine learning model space.
Analyzing Scalable Methods and Minibatching, We analyze current graph minibatching tech- niques like GraphSAINT [77 in non-homophilous settings, showing that they substantially degrade performance in experiments. Also, we show empirically that scalable methods for graph learning do not perform well in non- non-homophilous settings - even though they achieve state-of-te the art results many homophilous graph benchmarks. Finally, demonstrate that existing non non-homophilous methods often suffer from issues with scalability and performance in large non non- homophiloppuu graphs, in large part due to a lack of study of large-scale non-homophilous graph learning.
like SGC and C&S 771
3
LINKX: strong, simple method. We propose simple method LINKX that achieves excellent results for non-homophilous graphs while overcoming the bbove-mentioned minibatching issues. LINKX works by separately embedding the adjacency A and node features X, then combining them with multilayer perceptrons and simple transformations, as illustrated in Figure || generalizes node feature MLP and LINK regression [79]. two baselines that often work well non-homophilous graphs. This method is simple to train and evaluate in minibatched fashion, and does not face the performance degradation that other methods do in the minibatch setting. We develop the model and give more details Section R
Adjacency Matrix
MLP
W
MLP,
MLP
Node Features
X
Figure 1: Our model LINKX separately embeds node features and adjacency information with MLPs, combines the embeddings together by concatenation, then uses a final MI. to generate predictions.

---

2
Prior Work
38 69 have demonstrated their Graph Representation Learning. Graph neural networks 2
utility on a variety of graph machine learning tasks. Most GNNs are constructed by stacking layers that propagate transformed node features, which are then aggregated via different mechanisms. The neighborhood aggregation used in many existing GNNs implicitly leverage homophily, so they often Indeed, wide range of GNNs operate as low-pass graph filters [53] 77 that smooth features over the graph topology, which produces similar representations and thus similar predictions for neighboring nodes.
fail to generalize on non-homophilous graphs 82 6
Scalable methods. A variety of scalable graph learning methods have been developed for efficient computation in larger datasets [77 [6 77
Many of these methods explicitly make T0 By leveraging this assumption, several simple, inexpensive models are able to achieve state-of-the-art performance homophilic datasets However, these methods are unable to achieve comparable performance in non-homophilous
28
32
20
[0]
use of an assumption of homophily in the data M
32
20
i 32 settings, show empirically in Section
Graph sampling. As node representations depend on other nodes in the graph, there are no simple minibatching techniques in graph learning there are for i.i.d. data. To scale to large graphs, one line of work samples nodes that are used in each layer of graph neural network 128 14
Another family of methods samples subgraphs of an input graph, then passes each subgraph through GNN to make a prediction for each node of the subgraph [66 76 77.. While these methods are useful for scalable graph learning, we show that they substantially degrade performance in our non-homphilous experiments (see Section 5
Non- Non-Homophilous methods. Various GNNs have been proposed to achieve higher performance in low-homophily settings [82, 44
Geom-GCY GCN [58] introduces geometric aggregation scheme, MixHop proposes a graph convolutional layer that mixes powers of the features learnable weights that can be positive and negative in allows deep graph convolutional networks with relieved oversmooth-
81
17
15
r
56 35
adjacency matrix, GPR-GNN feature propagation, GCNII 15
ing, which empirically performs better in non-homen non-homophilous settings, and HGGCN [22] shows that separation of ego and neighbor embeddings, aggregation in higher-order neighborhoods, and the combination of intermediate representations improves GNN performance in low-homophily.
There are several recurring design decisions across these methods that appear to strengthen per- formance in hoooohiipiluus settings: using higher-order neighborhoods, decoupling neighbor information from ego information, and combining graph information at different scales [82]. Many of these design choices require additional overhead (see Section thus reducing their scalability.
Datasets. The widely used citation networks Cora, Citeseer, and Pubmed 62
74
are highly
homophilous (see Appendix A
Recently, the Open Graph Benchmark 31 has provided
series of datasets and leaderboards that improve the quality of evaluation in graph representation learning; however, most of the node classification datasets tend to be homophilous, as noted in past work [22] and expanded upon in Appendix A.2 A comparable set of high-quality benchmarks to evaluate nonhhooophioou methods does not currently exist.
3 Datasets for Non-Homophilous Graph Learning
3.1 Currently Used Datasets
The most widely used datasets to evaluate non-homophilous graph representation learning methods were used by Pei et al. [58] (and collected by [6T 66 ) see our Table for statistics. However, these datasets have fundamental issues. First, they are very small - the Cornell, Texas, and Wisconsin datasets have between 180-250 nodes, and the largest dataset Actor has 7,600 nodes. In analogy to small (homophilic) datasets discussed in [x3] evaluation on the datasets of Pei et al. (8) is plagued by high variance across different train/test splits (see results in (82) ) The small size of these datasets may tend create models that are more prone to overfitting 21 which prevents the scaling up of GNNs designed for non-homophilous settings.
certain pitfalls of graph neural network evaluation
Peel 57 also studies node classification on network datasets with various types of relationships between edges and labels. However, they only study methods that act on graph topology, and thus their datasets do not necessarily have node features. We take inspiration from their work, by
3

---

testing on Pokec and Facebook networks with node features that we define, and by introducing other year-prediction tasks on citation networks that have node features.
3.2 An Improved Homophily Measure
Various metrics have been proposed to measure the homophily of a graph. However, these metrics are sensitive to the number of classes and the number of nodes in each class. Let G = (V, E) be a graph with n nodes, none of which are isolated. Further let each node u E V have a class label ku E {0, (0.1..... C C-11 1} for some number of classes C, and denote by C2 the set of nodes in class k.
The edge homophily g> is the proportion of edges that connect two nodes of the same class:
h H(u, v) E E: E: ky ko
(I)
E
Another related measure is what we call the node homophily [58] defined as V Evev
d, in
which du is the number of neighbors of node u, and a!!t)) the number of neighbors of u that have the same class label. We focus on the edge homophily (1) in this work, but find that node homophily tends to have similar qualitative behavior experiments.
The sensitivity of edge homophily to the number of classes and size of each class limits its utility. We consider a null model for graphs in which the graph topology is independent of the labels; suppose that nodes with corresponding labels are fixed, and include edges uniformly at random in the graph that are independent of node labels. Under this null model, a node E V would be expected have d(Hiw) / dd, 2 Ck., I/n as the proportion of nodes of the same class that they connect to 3 For a dataset with C balanced classes, would thus expect the edge homophily be around c so the interpretation of the measure depends on the number of classes. Also, if classes are imbalanced, then the edge homophily may be misleadingly large. For instance, if 99% of nodes were of one class, then most edges would likely be within that same class, so the edge homophily would be high, even when the graph is generated from the null model where labels are independent of graph topology. Thus, the edge homophily does not capture deviation of the label distribution from the null model.
We introduce metric that better captures the presence absence of homophily. Unlike the edge homophily, our metric measures excess homophily that is not expected from the above null model where edges are randomly wired. Our metric does not distinguish between different non-homophilous settings (such as heterophily or independent edges); we believe that there are too many degrees of freedom in oon-homophilou settings for single scalar quantity to be able distinguish them all. Our measure is given as:
Cc
h-
hi
h
n
where [a]+ max(a, 0), and h2 is the class wise homophily metric
Enecr (kw))
Evec, du
Note that h E [0, 1], with a fully homophilous graph (in which every node is only connected to nodes of the same class) having h = 1. Since each class-wise homophily metric húp only contributes positive deviations from the null expected proportion [Cal/n, the class-imbalance problem is substantially mitigated. Also, graphs in which edges are independent of node labels are expected to have h Rs 0, for any number of classes. Our measure h measures presence of homophily, but does not distinguish between the many types of possibly non- non-homophilous relationships. This is reasonable given the diversity of non non-homophilous relationships. For example, non non-homophil can imply independence of edges and classes, extreme heterophily, connections only among subsets of classes, or certain chemically biologically determined relationships. Indeed, these relationships are very different, and are better captured by more than one scalar quantity, such as the compatibility matrices presented in the appendix. Further discussion is given in Appendix A

---

Table 1: Statistics for previously used datasets from Pei et al. [S (collected by 66 the number of node classes. The highest number of nodes or edges overall are bolded.
66 48
#C is
Dataset
# Nodes
# Edges
# Feat.
C
Context
Edge hom.
(ours)
Chameleon
2,277
36,101
2.325
5
Wiki pages
.23
.062
Cornell
183
295
1,703
5
Web pages
.30
.047
Actor
7,600
29,926
931
5
Actors movies
.22
.011
Squireel
5,201
216,933
2,089
5
Wiki pages
.22
.025
Texas
183
309
1,703
5
Web pages
.11
.001
Wisconsin
251
499
1,703
5
Web pages
.21
.094
3.3
Proposed Datasets
Here, we detail the non-homophilous datasets that we propose for graph machine learning evaluation. Our datasets and tasks span diverse application areas. Penn94 67 Pokec [4 genius [ and twitch-gamers [60] are online social networks, where the task is to predict reported gender, certain account labels,
of explicit content user accounts. For the citation networks arXív-year Kil and snap-patents 42 !l the goal is to predict year of paper publication or the year that patent granted. The dataset wiki consists of Wikipedia articles, where the goal is predict total page views of each article. Detailed descriptions about the graph structure, node features, node labels, and licenses of each dataset are given in Appendix D.2
Most of these datasets have been used for evaluation of graph machine learning models in past work; make adjustments such modifying node labels and adding node features that allow for evaluation of GNNs in non-homophilous settings. We define node features for Pokec, genius, and snap-patents, and also define node labels for arXiv-year, snap-patents, and genius. Additionally, we crawl and clean the large-scale wiki dataset - new Wikipedia dataset where the task is to predict page views, which is non-homophilous with respect the graph of articles connected by links between articles (see Appendix D.3 This wiki dataset has 1,925,342 nodes and 303,434,800 edges, so training and inference require scalable algorithms.
Basic dataset statistics are given in Table 2 Note the substantial difference between the size of our datasets and those of Pei al. [58 in Table D datasets have up 384x more nodes and 1398x more edges. The homophily measures along with the lower empirical performance of homophily- assuming models (Section 5) and examination of compatibility matrices (Appendix A show that our datasets are indeed non-homophilous. As there is little study in large-scale non-homophilous graph learning, proposed large datasets strongly motivate the need for developing new, scalable approach that can accurately learn on oonhomoppiious graphs.
Table Statistics of our proposed non non-homophilous graph datasets. the number of distinct node classes. Note that our datasets come from more diverse applications areas and are much larger than those shown Table with up to 384x more nodes and 1398x more edges.
Dataset
Nodes
# Edges
Feat.
#
Class types
Edge hom.
(ours)
Penn94 41,554
1,362,229
gender gender pub year
.046
pokec
1,632,803
30,622,564
65
.445
.000
arXiv-ycar
169,343
1,166,243
128
.222
.272
snap-patents
2,923,922
13,975,788
269
time granted
.073
.100
genius
421,961
984,979
12
marked act.
.618
.080
twitch-gamers
168.114
6,797.557
mature content
.545
.090
wiki 1,925,342
303,434,860
600
views
.389
.107
LINKX: New Scalable Model
In this section, we introduce our novel model, LINKX, for scalable node classification non- homophilous settings. LINKX is built out of multilayer perceptrons (MLPs) and línear transforma- tions, thus making simple and scalable. also admits simple row-wise minibatching procedures that allow it to perform well on large non-homophilous graphs. As result, LINKX is able to
5

---

circumvent aforementioned issues of graph minibatching and non-homophilous GNNs in large-scale non-homophilous settings.
4.1 Motivation from two simple baselines
Here, we detail two simple baselines for node classification that we build on to develop LINKX.
MLP on node features. A naive method for node classification is ignore the graph topology and simply train an MLP on node features. For the same reason that the graph topology has more complicated relationships with label distributions in non-homophilous graphs, many GNNs are not able to effectively leverage the graph topology in these settings. Thus, MLPs can actually perform comparatively well on non-homophilous graphs achieving higher approximately equal performance to various GNNs [82].
simple baseline that only utilizes graph topology. In particular, we consider LINK regression, which trains logistic regression model in which each node's features are taken from a column of the adjacency matrix. Letting A E {0, 1 j be the binary adjacency matrix of the graph, and W E Rexn be a learned weight matrix, LINK computes class probabilities as
LINK regression on graph topology. On the other extreme, there is LINK 73
Y softmax( WA).
(4)
Let E {L..... n be a specific node, and let & E fl,..., eJ be specific class. Then, expanding the matrix multiplication, the log-odds of node belonging to class k is given by
(WA) Jou = Σ
Wku
(5)
VEN(UM
where (u)) contains the I-hop neighbors of In other words, the logit is given by the sum of weights kv across the h-hop neighbors of u. If a specific node v has many neighbors of class k. would expect with high probability that any neighbor of v is of class k. In this sense, LINK is like a 2-hop method: for a given node u, the probability of being in a given class is related to the class memberships of u's 2-hop neighbors in (()) for each neighbor v E (u). Related interpretations of LINK as a method acting on 2-hop paths between nodes are given by Altenburger and Ugander
then Wa kv is probably large,
Though it is simple and has been overlooked in the recent non-homophilous GNN literature, LINK has been found to perform well in certain node classification tasks like gender prediction in social networks B E A major reason why LINK does well in many settings is exactly because acts 2-hop method. For example, while 1 1-hop neighbors
often not so informative for gender prediction in social networks due to lack of homophily, 2-hop neighbors are very informative due to so-called "monophily," whereby many nodes have extreme preferences for connecting a certain class B. Beyond just gender prediction, we show Section that LINK empirically outperforms many models across the various application areas of the non-hooophilous datasets propose.
4.2 LINKX
We combine these two simple baselines through simple linear transformations and component-wise nonlinearities. Let X E R denote the matrix of node features with input dimension D, and let [h; hg] denote concatenation of vectors h, and h2. Then our model outputs predictions Y through the following mapping:
hy = MLPA(A) E ddx=
(6)
hx MLPx(X) E d
Y MLP, (a (Whh hx] hA + +xx))
(8)
in which d is the hidden dimension, W E Rdd22d is weight matrix, and is a component-we nonlinearity (which we take to be ReLU). We call our model LINKX, as it extends LINK with node feature information from the matrix X. A diagram of LINKX is given in Figure
First, LINKX computes hidden representations hY of the adjacency (extending LINK) and hx of the feature matrix (as in node-feature MLPs). Then it combines these hidden representations

---

through a linear transform W of their concatenation, with skip connections that add back in hA and hx to better preserve pure adjacency or node feature information. Finally, puts this combined representation through a non-linearity and another MLP to make a prediction.
Separating then mixing adjacency and feature information. LINKX separately embeds the adjacency A to hA and the features X into hx before mixing them for a few reasons. First, we note that this design is reminiscent of fusion architectures in multimodal networks, where data from different modalities are processed and combined in a neural network e4 7S]. In our setting, we can view adjacency information and node feature information as separate modalities. Since node feature MLPs and LINK do well independently on different datasets, this allows us to preserve their individual performance if needed. Ignoring hx information is similar to just using LINK, and ignoring hA information is just using an node feature MLP. Still, to preserve the ability to just learn a similar mapping to LINK or to a node feature MIP, we find that having the additive skip connections helps to get performance at least as good as either baseline. Our initial empirical results showed that simply concatenating adjacency and node features as input to a network does worse overall empirically (see Appendix
There are also computational benefits our design choices. Embedding A is beneficial for depth as adding more layers to the MLPs only gives an (dd) cost - depending only on the hidden dimension d- and thus does not scale in the number of edges |E] as when adding layers to pessage-passinng GNNs. This is because the graph information in A is already compressed to hidden feature vectors after the first linear mapping of MLPA, A. and we do not need to propagate along the graph in later steps. Moreover, this enables a sparse-dense matrix product to compute the first linear mapping of MLP A on A, which greatly increases efficiency as is typically very sparse for real-world graphs. Separate embeddings are key here, as this would not be possible if we for instance concatenated A and X when X is large and dense.
Simple minibatching. Message-passing GNNs must take graph topology into account when mini- batching with techniques such as neighbor sampling, subgraph sampling, or graph partitioning. However, LINKX does not require this, as it utilizes graph information solely through defining adjacency matrix columns as features. Thus, we can train LINKX with standard stochastic gradient descent variants by taking i.i.d. samples of nodes along with the corresponding columns of the adja- cency and feature matrix as features. This much simpler than the graph minibatching procedures for wvessage-passing GNNs, which require specific hyperparameter choices, have to avoid exponential blowup of number of neighbors per layer, and are generally more complex to implement (77]. In Section 5.3 we use the simple LINKX minibatching procedure for large-scale experiments that show that LINKX with this minibatching style outperforms GNNs with graph minibatching methods. This is especially important on the scale of the wiki dataset, where none of our tested methods other than MLP is capable of running on a Titan RTX GPU with 24 GB GPU RAM (see Section
4.3 Complexity Analysis
Using the above notation, a forward pass of LINKX has a time complexity of O (d)E) + nd L). in which d is the hidden dimension (which we assume to be on the same order as the input feature dimension D), L is the number of layers, n is the number of nodes, and |E| is the number of edges. We require (d El) cost for the first linear mapping of A and a (dd²) cost per layer for MLP operations on hidden features, for L total layers and each of n nodes.
As mentioned above, message passing GNNs have to propagate using the adjacency in each layer, so they have an L| term in the complexity. For instance, an L-layer GCN BS with d hidden dimensions has (d + naf2 L) complexity, as it costs (l) to propagate features in each layer, and O(dd?) to multiply by the weight matrix in each layer.
Non- hon-homophilous methods often make modifications to standard architectures that increase computa- tional cost, such as using higher-order neighborhoods or using additional hidden embeddings [82]. For instance, the complexity of MixHop [1 is ((K(LL) E + LddL)), which has an extra factor K that the number of adjacency powers to propagate with. The complexity of GCNII [15] is asymptotically the same as that of GCN, but in practice it requires more computations per layer due to residual connections and linear combinations, and also often achieves best performance with a large number of layers L. HGGCN [2 is significantly more expensive due to its usage of strict
7

---

two-hop neighborhoods, which requires it to form the squared adjacency A This makes the memory requirements intractable even for medium sized graphs (see Section 5
Experiments
We conduct two sets of experiments for node classification on our proposed comohooppsilous datasets. One set of experiments does full batch gradient descent training for all applicable methods. This of course limits the size of each model, as the large datasets require substantial GPU memory to train on. Our other set of experiments uses minibatching methods. As all graph-based methods run out of on 24 GB GPUs, only include wiki results in the minibatching
memory the wiki dataset, section. In all settings, our LINKX model matches or outperforms other methods.
Table 3: Experimental results. Test accuracy is displayed for most datasets, while genius displays test ROC AUC. Standard deviations are over 5 train/val/test splits. The three best results per dataset are highlighted. (M) denotes some (or all) hyperparameter settings run out of memory.
Pennt4
arKiv-year
stap-paeens
genius
wilch-games
73.61 0.40
62.37
+ 0.02
36.70 0.21
31.34 0.05
86,68 0
60.92 0.0T
Rop Ihhop
63.21 0.39
53.09
0.005
42. 3 0.I7
50.26
68.02
6277 5022
L Prru 2-hup
74.13 1: 0.46
76.76 + 0.03
46.07 + 0.15
38.61 1 0.07
67.01 1 0.20
63.86 1 0.24
LINK
0.49
80.54
+ 0,03
53.97
0.07
73.56 0.14
64.85
0.21
T-hop
66.79
0.27
53.61
= 0.17
32.83 = 0.13
30.31
0.06
82.36
0.37
68.37
0.15
SGC 2-hop
76.09 1: 0.45
62.81 + 1.42
32.27 0.06
29.09
= 0.09
62.10
0.14
59.91 : 0.21
C&S Lhopp
74.28
1.19
62.35
+ 0.06
44.51 + 0.16
35.55
0.05
82.93 = 0.15
64.86 + 0.27
hup
76.40 1:00::303 3.12
$1.09
0.09
49.78
0.26
08
65 05.03 0.16
GCN
82.47 0.277
75.43
+ 0.17
40.02
0.26
43.66
0.D4
87.42
0.37
62.18
0.26
GAT
81.53 4: 0.55
71.77 + 6.18 (M)
46.05
+ 0.51
45.3T
0.44 (M)
55.80
0.87
69.89 + 4.12
GUNIK
0.54
0.14
46,28
63.40 0.22
80.69
0.36
71.19
6.96 (M)
43.80
0.72
44.78
56.70
2.07
69:98
2.87
APPNP
74.33 :: 0.38
62.68 + 0.08
38.15
+ 0.26
32.19
0.07
85.36
0.62
60.97 + 0.10 [M)
B,GCN
[M]
(M)
45.09
3: 0.10
MixHop
53.47
0.71
81.07
0.16
51.81
0.17
52.16
90.58
65.64 0:27
GPR-GNN
81.38
0.16
78,63 1 0.05
45.07 1: 0.21
40.19
0.03
90.05 1: 0.31
61.89 1: 0.29
GUNU
82.92
0.59
78.94 + 0.11 (M)
47.21
4: 0.28
37.88
0.69 (M)
90.24 = 0.09
63.39
0.61
LINKX
84.71 3: 0.52
82.04 + 0:07
56.00
= 1:34
61.95 = 0.12
90.77 = 0.27
66.06 +: 0.19
5.1
Experimental Setup
Methods. We include both methods that are graph-agnostic and node-feature-agnosti as simple baselines. The
models of two-hop label propagation 57 and LINK (logistic regression on the adjacency matrix) (79 have been found to perform well in various non- homphoopp settings, but they have often been overlooked by recent graph representation learning work. Also, we include SGC 771 and C&S 32] as simple, scalable methods that perform well on homophilic datasets. We include a two-hop propagation variant of C&S in analogy with two-step label propagation. In ad- dition to representative general GNNs, we also include GNNs recently proposed for non-homophilous settings. The full list of methods is: Only node features: MLP 226.. Only graph topology: label
propagation (standard and two-hop) 80 57 LINK 79 Simple methods: SGC 771] C&S [32]
and their two-hop variants. General GNNs: GCN
BS
GAT (69,, jumping knowledge networks
(GCNJK, GATJK) 72, and APPNP 39. Non-homophilous methods: H₂GCN
82). MixHop [1.
GPR-GNN [77 GCNII [15.. and LINKX (ours).
Minibatching methods. We also evaluate GNNs with various minibatching methods. We take GC- NJK 722 and MixHop [I] as our base models for evaluation, as they are representative of many GNN design choices and MixHop performs very well full batch training. As other minibatching methods are trickier to make work with these models, we use the Cluster-GCN [16] and GraphSAINT [77] minibatching methods, which sample subgraphs. We include both the node based sampling and random walk based sampling variants of GIaP We compare these GNNs with MLP, LINK, and our LINKX, which use simple i.idd node minibatching.
Training and evaluation. Following other works in non-homophilous graph learning evaluation, we take high proportion of training nodes (22 58
[R] : we run each method on the same five random 50/25/25 train/val/test splits for each dataset. All methods requiring mundient-based optimization are run for 500 epochs, with test performance reported for the learned parameters of highest validation performance. We use ROC-AUC as the metric for the class-imbalanced genius dataset (about 80% of nodes are in the majority class), as it is less sensitive to class-imbalance than accuracy. For other datasets, we use classification accuracy as the metric. Further experimental details are in Appendix B
8

---

5.2 Full-Batch Results
Table lists the results of each method across the datasets that we propose. Our datasets reveal several important properties of non-homophilous node classification. Firstly, the stability of performance across runs better for our datasets than those of Pei et al. [58] (see X2 results). Secondly, as suggested by prior theory and experiments [82 though not necessarily on every dataset.
the non-homophilous GNNs usually do well
The core assumption of homophily in SGC and C&S that enables them to be simple and efficient does not hold on these non-homophilous datasets, and thus the performance of these methods is typically relatively low. Still, as expected, two-hop variants generally improve upon their one-hop counter-pane parts in these low- www-homohhlly settings.
One consequence of using larger datasets for benchmarks is that the tradeoff between scalability and learning performance of non-homophilous methods has become starker, with some methods facing memory issues. This tradeoff is especially important to consider in light of the fact that many scalable graph learning methods rely on implicit or explicit homophily assumptions 77] face issues when used in non-homophilous settings.
10 and thus
Finally, LINKX achieves superior performance all datasets, taking advantage of LINK's power, while also being able to utilize node features where they provide additional information.
5.3 Minibatching Results
Table 4: Minibatching results our proposed datasets. i denotes that 10 random partitions of the graphs are used for testing GraphSAINT sampling. (T) denotes that five runs takes 2 48 hours for a single hyperparameter setting. Best results up standard deviation are highlighted.
Ponn14
pokec
snap-pateurs
genius
twicch-games
wiki 1
Minibatch
74,26-00.55
62.14-2-0005
36 36.19--.111
22.96--081
82.35 +-0.38
61.01 61.01---006
37.38---0.21
LINK
81.61:00.34
GONIK-Clster
09.99:0.85
12.67:0.05
20.31
57.6240.31
85.04-:0.56
61.15:00116
(T)
GCNIK Sooee
72.80-0.45
63.68-40.55
44.04--222
26.97-00.10
80.96--0.09
59.00--0.25
44 44.86--0.19
GONIK-SAINTERW
72.29-0..9
65.0020111
47 07
03005:00000
81.04:0.114
59.22:0.27
47.30%:0000
MixHop-CClstter
75.79=0.44
4841:4031
81.12:4:010
62.95--0.00
MaaHop-SAINT-NOO
75.61
66.424-0.06
44.84--.118
27.45-0.111
81.06:1-0.08
59.8---0277
47.39--0.18
MisHop-SAINT-RRW
76.38=0.50
67.9220066
50 50.55::0.00
54.21200077
82.25:20.78
60 60139:00.16
49.15:2:026
LINKX Minibatch
84,50=00.55
81,2780038
53.74:00227
6027-60029
85.81
65344300199
59 39.00-00441
Our experimental results for minibatched methods on our proposed datasets are in Table + Since GraphSAINT does not partition the nodes of the graph into subgraphs that cover all nodes, we test on the full input graph for the smaller datasets and uniformly random partitions of the graph into 10 induced subgraphs for the larger datasets.
First, we note that both Cluster-GCN and GraphSAINT sampling lead to performance degradation for these methods on our proposed non-homophilous datasets. When compared the full-batch training results of the previous section, classification accuracy is typically substantially lower. Further experiments in Appendix C.2 give evidence that the performance degradation is often more substantial in non- non-homophilous settings, and provides possible explanations for why this may be the case.
On the other hand, LINKX does not suffer much performance degradation with the simple i...d node minibatching technique. In fact, it matches or outperforms all methods in this setting, often by a wide margin. Though LINK performs par with LINKX in arXiv-year and pokec, our LINKX model significantly outperforms on other datasets, again due to LINKX's ' ability to integrate node feature information. We again stress that the LINKX minibatching is very simple implement, yet it still substantially outperforms other methods. Consequently, LINKX is generally well-suited for scalable node classification across a broad range of non-homophilous settings, surpassing even specially designed non-homophilous GNNs with current graph minibatching techniques.
Discussion and Conclusion
In this paper, we propose new, high-quality non-homophilous graph learning datasets, and we benchmark simple baselines and representative graph representation learning methods across these datascts. Further, we develop LINKX: strong, simple, and scalable method for non-homophilous

---

classification. Our experiments show that LINKX significantly outperforms other methods on our proposed datasets, thus providing one powerful method in the underexplored area of scalable learning on non-homophilous graphs. We hope that our contributions will provide researchers with new avenues of research in learning on non-homophilous graphs, along with better tools to test models and evaluate utility of new techniques.
While we do find utility in our proposed datasets and LINKX model, this work is somewhat limited by only focusing on transductive node classification. This setting is the most natural for studying performance in the absence of homophily, since here we define homophily in terms of the node labels, and previous non-homophilous GNN work using the Pei et al. [58] data also studies this
setting exclusively [22 17. Using other Facebook 100 datasets besides Penn94 677 would allow for inductive node classification, but LINKX does not directly generalize to this setting. Our proposed datasets and model LINKX could be used for link prediction, but this left for future work.
Broader Impact. Fundamental research in graph learning on non-hooophilous graphs has the potential for positive societal benefit. As a major application, it enables malicious node detection techniques in social networks and transaction networks that are not fooled by fraudsters' connections to legitimate users and customers. This is a widely studied task, and past works have noted that non-homophilous structures are present in many such networks I 25 55 We hope that this paper provides insight on the homophily limitations of existing scalable graph learning models and help researchers design scalable models that continue to work well in the non- non-homophilous regime, thus improving the quality of node classification on graphs more broadly. As our proposed datasets have diverse structures and our model performs well across all of these datasets, the potential for future application of our work to important non-homophilous tasks is high.
Nevertheless, our work could also have potential for different types of negative social consequences. Nefarious behavior by key actors could be one source of such consequences. Nonetheless, we expect that the actors that can make use of large-scale social networks for gender prediction as studied in our work are limited in number. Actors with both the capability and incentive perform such operations probably mostly consist of entities with access to large social network data such as social media companies or government actors with auxiliary networks (50). Smaller actors can perform certain attacks, but this may be made more difficult by resource requirements such as the need for certain external information (50) or the ability to add nodes and edges before an anonymized version of a social network is released [ Furthermore, additional actors could make use of deanonymization
attacks
40 50 to reveal user identities in supposedly anonymized datasets.
Also, accidental consequences and implicit biases are a potential issue, even if the applications of the learning algorithms are benign and intended benefit society 77. Performance of algorithms may vary substantially between intersectional subgroups of subjects - as in the case of vision-based gender predictors [12] (and some have questioned the propriety of vision-based gender classifiers altogether). Thus, there may be disparate effects on different populations, so care should be taken to understand the impact of those differences across subgroups. Moreover, large datasets require computing resources, so projects can only be pursued by large entities at the possible expense of the individual and smaller research groups [.. This is alleviated by the fact that our experiments are each run on one GPU, and hence have significantly less GPU computing requirements than much current deep learning research. Thus, smaller research groups and independent researchers should find our work beneficial, and should be able to build on it.
Finally, the nature of collection of online user information also comes with notable ethical concerns. Common
policies are often ineffective in actually protecting user privacy [52]] Indeed, users may not actually have much choice in using certain platforms or sharing data due to social or economic reasons. Also, users are generally unable to fully read and understand all of the different privacy policies that they come across, and may not understand the implications of having their data available for long periods of time to entities with powerful inference algorithms. Furthermore, people may rely on obscurity for privacy [29], but this assumption may be ignored in courts of law, and it may be directly broken when data leaks or is released in aggregated form without sufficient privacy protections. Overall, while we believe that our work will benefit machine learning research and enable positive applications, we must still be aware of possible negative consequences.
10

---

Acknowledgements
We thank Abhay Singh, Austin Benson, and Horace He for insightful discussions. We also thank the rest of Cornell University Artificial Intelligence for their support and discussion. We thank Facebook AI for funding equipment that made this work possible.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pages 21-29, 2019.
[2] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework, 2019.
[3] Kristen M Altenburger and Johan Ugander. Monophily social networks introduces similarity among friends-of-friende Nature human behaviour, 2(4):284-290, 2018.
[4] Kristen M Altenburger and Johan Ugander. Node attribute prediction: An evaluation of within- versus across-network tasks. NewrIPS Workshop on Relational Representation Learning, 2018.
[5] Lars Backstrom, Cynthia Dwork, and Jon M. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW '07, 2007.
[6] Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2021.
[7] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Janchez-Gonzaler Vinicius Zambaldi. Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01266 2018.
[8] Abeba Birhane, Pratyusha Kalluri, Dallas Card, William Agnew, Ravit Dotan, and Michelle Bao. The values encoded in machine learning research, 2021.
[9] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond ow-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00779 2021.
[10] Aleksandar Bojchevski. Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464 2473, 2020.
[11) Adam Breuer, Roee Eilat, and Udi Weinsberg. Friend or faux: Graph-based early detection of fake accounts on social networks, 2020.
[12] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. Sorelle A. Friedler and Christo Wilson, editors, Proceedings of the 1st Conference Fairness, Accountability and Transparency, volume 81 of Proceedings of Machine Learning Research, pages 77-91. PMLR, 23-24 Feb 2018. URL https://
proceedings .ml...smmmr.....mmm wwwppres//veee /tt///////aaaaaae 18a. html
[13] Duen Horng Chau, Shashank Pandit, and Christos Faloutsos. Detecting fraudulent personalities in networks of online auctioneers. European conference on principles of data mining and knowledge discovery, pages 103-114. Springer, 2006.
[14] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference Learning Representations, 2018.

---

[15] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735. PMLR, 2020.
[16] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. pages 257-266, 2019.
[17] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
[18] Alex Chin, Yatong Chen, Kristen M. Altenburger, and Johan Ugander. Decoupled smoothing on graphs. In The World Wide Web Conference, pages 263-272, 2019.
[19] Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter, Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.0728500 2015.
[20] Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding. In International Conference Learning Representations, 2020.
[21] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint 2003::2033.0992, 2020.
[22] Paul Erdös and Alfréd Rényi On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
[23] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv; iete:000000222 2019.
[24] Konrad Gadzicki, Razieh Khamsehashari, and Christoph Zetzsche. Early late fusion in multimodal convolutional neural networks. In 2020 IEEE 23rd International Conference on Information Fusion (FUSION), pages 1-6. IEEE, 2020.
[25] Wolfgang Gatterbauer. Semi-supervised learning with heterophily. arXiv preprint arXiv:1412.3100, 2014.
[26] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning. MIT press Cambridge, 2016.
[27] Bronwyn H Hall, Adam B Jaffe, and Manuel Trajtenberg. The nber patent citation data file: Lessons, insights and methodological tools. Working Paper 8498, National Bureau of Economic Research, October 2001. URL httt::///ww.. nber wwtp:/nbeerrrrggpppeaeeeee wrg/papers/w8498
http://www.nbrr......
[28] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[29] Woodrow Hartzog and Frederic Stutzman. The case for online obscurity. California Law Review, 101(1):1-49, 2013. ISSN 000812211 htlp:ttp:////e http://www..stt...ooo//// jstor org/ wttaal//ea40....
[30] Michael Hay, Gerome Miklau, David Jensen, Donald Towsley, and Philipp Weis. Resisting structural identification in anonymized social networks. PVLDB, 1:102-114, 08 2008. doi: 10.14778/1453856 1453873.
[31] Weihua Hu. Matthias Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00687 2020.
[32] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models per-foroosms graph neural networks. In International Conference on Learning Representations, 2021.
12

---

[33] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448 456. PMIR, 2015.
[34] Junteng Jia and Austion R Benson. Residual correlation in graph neural network regression. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 588-598, 2020.
[35] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 148-156, 2021.
[36] Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations, 2021.
[37] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
[38] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017.
[39] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
[40] M. Zabovsky L. Takac. Data analysis in public social networks. International Scientific Conference & International Workshop Present Day Trends of Innovations, 2012.
[41] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap... http://saasssaaffooooooooooooo/a
stanf ord. edu/data June 2014.
[42] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery data mining, pages 177-187, 2005.
[43] Derek Lim and Austin R Benson. Expertise and dynamics within crowdsourced musical knowledge curation: A case study of the genius platform. In Proceedings of the International AAAI Conference on Web and Social Media, 2021.
[44] Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks, 2020.
[45] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference Learning Representattinss, 2018.
[46] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1)415-444, 2001.
[47] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. survey on bias and fairness in machine learning, 2019.
[48] Tom Mitchell al. The 4 universities data set, 1997. URL BoLhttp::// http:httpt///tt h/www//wwwwwc.o cs, cmu, edweeduuaaae /duu/ff// cs. cmu potu/pprjjecc/thheoo////wvw/
[49] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111-125, 2008. doi: 10. N0.1109/SP.2008.33
[50] Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In 2009 30th IEEE Symposium Security and Privacy, pages 173-187, 2009. doi: 10. 10.1109/SP.2009.22.
[51] Mark EJ Newman. Mixing patterns in networks. Physical review E, 67(2) 2003.
[52] Helen Nissenbaum. A contextual approach to privacy online. Daedalus, 140:32-48, 2011.
13

---

[53] Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low- filters. arXiv preprint arXiv:1955.09555 2019.
[54] Hoang NT, Takanori Maehara, and Tsuyoshi Murata. Stacked graph filter. arXiv preprint arXiv:2011.109% 2020.
[55] Shashank Pandit, Duen Horg Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th international conference on World Wide Web, pages 201-210, 2007.
[56] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performang deep learning library. Advances in Neural Information Processing Systems, 32:8026-80000 2019.
[57] Leto Peel. Graph-based semi-supervised learning for relational networks. In Proceedings of the 2017 SIAM International Conference on Data Mining, pages 435-443, SIAM, 2017.
[58] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuar Chang, Yu Lei, and Bo Yang. Geom-gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations, 2019.
[59] Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532-1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.1115/11/144-1100
[60] Benedek Rozemberezki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserving and structural role-based node embeddings. arXiv preprini arXiv:2101.088: 2021.
[61] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2)xcnab014, 2021.
[62] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3)993-93, 2008.
[63] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1eXivv/8/1.05000 2018.
[64] Neil JA Sloane. The on-line encyclopedia of integer sequences. In Towards mechanized mathematical assistants, pages 130-130. Springer, 2007.
[65] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15()):1229-198, 2014.
[66] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 807-816, 2009.
[67] Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks Physica A: Statistical Mechanics and its Applications, 391(16)4465-4188 2012.
[68] Nate Veldt, Austin R Benson, and Jon Kleinberg. Higher-order homophily is combinatorially impossible. arXiv preprint arXiv:2103.. 11888 2021.
[69] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[70] Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul
Kanakia. Microsoft Academic Graph: When experts are not enough. Quantitative Science Studies, 1(1):396 02 2020. ISSN 2641-3337. doi: 10.1 162//1s_aaaaeee a0002.. URL https
//doi Allii.ogg/ie 10. 1162 /a//////////////////////////// a_000
14

---

[71] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pages 6861-6871. PMLR, 2019.
[72] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462. PMI.R 2018.
[73] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks, arXiv preprint arXiv:2102.06400 2021.
[74] Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[75] Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983, 2018.
[76] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Accurate, efficient and scalable graph embedding. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 462-471. IEEE, 2019.
[77] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019.
[78] Jin Zeng, Yanfeng Tong, Yunmu Huang, Qiong Yan, Wenxiu Sun, Jing Chen, and Yongtian Wang. Deep surface normal estimation with hierarchical rgb-d fusion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6153-6162, 2019.
[79] Elena Zheleva and Lise Getoor. To join not to join: the illusion of privacy in social networks with mixed public and private user profiles. In Proceedings of the 18th international conference on World wide web, pages 53 3-1504 2009.
[80] Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in neural information processing systems, pages 321-323 2004.
[81] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. arXiv preprint 2rXiv:2009913566 2020.
[82] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
[83] Michael Zimmer. Facebook data of 1.2 million users from 2005 released: Limited expo- sure, but very problematic, Feb 2011. URL hattps://nit http://:///ichhhhiiiimeeeee org/2011/02/15/ facebook data- of 11-1-22 11-11-2000 2-millloonn.om.i..... users- from
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We have supported the claims in the main paper and appendix.
(b) Did you describe the limitations of your work? [Yes] See discussion conclusion Section K
15

---

(c) Did you discuss any potential negative societal impacts of your work? [Yes] See discussion / conclusion Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] We include our proposed datasets and our codes for reproducing the experimental results in the supplemental material.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5.1 and Appendix Section B
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We include standard deviation of performance metrics across multiple runs in Section S
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide GPU information in Appendix Section
4. If you using existing assets code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the creators of existing datasets and methods in the main paper. Also, Appendix B we cite codes that we used.
(b) Did you mention the license of the assets? [Yes] In Appendix D note the licenses of datasets, provided published work. Also, we include the license of open-source codes build off of in Appendix
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We include our proposed datasets along with codes for reproducing our results in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] We discuss this in Appendix D Most of the datasets were constructed and presented in previously published academic work. This mostly does not apply to the wiki dataset that we collect, it is encyclopedic in nature.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] In Appendix D we discuss this. Our datasets primarily numerical, they do not contain offensive content. To the best of our knowledge, our datasets do not contain personally identifiable content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "wsjYIPkl6Jn", "reviewer": "Reviewer_A2Hj", "summary": "The paper studies the performance of graph methods on heterophilous datasets. In particular, they propose several new graph datasets, a method for such datasets, and an evaluation of many graph methods on these new datasets. The paper is written in a clear and thorough manner, there is an exhaustive list of references and introduction makes a good job of motivating the problems studied in the paper. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper's contributions can be split into three parts: new datasets, new method, and empirical comparison. \n\n1. I have strong concerns about the datasets and their possible misuse in the future. In particular, 4 of the proposed datasets are social networks or alike, which could be used to train machine learning models for assessing properties of individuals or the communities involved in the network. Besides, the tasks of predicting properties such as gender could lead to the situation when the trained models discriminate certain groups of people. As one of the main paper's contributions are the new datasets, I am worried that such datasets could be used in many other future related works that would eventually lead to unfair treatment of people by the machine learning models. Creating a precedent in this work, could also lead other works to include datasets that mistreat people's interests. I think there is [a related track](https://neurips.cc/Conferences/2021/CallForDatasetsBenchmarks) on benchmark and datasets, where this work can get more support and feedback on the validity of the proposed datasets. \n\n2. The authors propose a new method called LINKX, which builds on a well-known method LINK. However, the previous LINK method was not used with node features and the authors propose to combine LINK embeddings with MLP embeddings on the node features. This allows the algorithm to scale easily to large datasets such as Wiki, whereas GNNs need more complex sampling solutions such as graphSAINT. \n\n3. The empirical comparison is done nicely across the proposed datasets and many graph models including vanilla GNNs, heterophilous GNNs, MLPs, LP, and others. However, I would like to see the performance of LINKX on other datasets, homophilous and heterphilous (see [here](https://arxiv.org/abs/2102.06462) for example) for the fair comparison. \n\nAfter rebuttal: Given a significant discussion between authors, reviewers, and ethics committee I tend to increase the score from 4 to 6. I still believe this paper would make a better fit to the dataset track of NeurIPS 2021. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As discussed above, one of the consequences of proposing real-world social networks and corresponding machine learning tasks of predicting properties of individuals (such as their gender) might be the misuse of the trained models on such datasets as well as promoting other works to propose datasets with sensitive information. As the field of GNNs mature, I can easily see how end users in the future use these models and datasets for the applications that treat unfairly certain groups of people (e.g. in credit scoring, institution admission, etc.). ", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "9JZBLsXHTJ", "reviewer": "Reviewer_coWt", "summary": "This paper proposes 7 new large heterophily graph datasets (up to 2 million nodes) and also provides a simple, scalable yet effective baseline LINKX which combines the information from topology and node features.\nThe paper extensively evaluates the datasets on various baselines, including typical GNNs and GNNs specifically designed for heterophily graphs. They find that many baselines cannot compete with the simple baseline LINKX and some of them run out of memory.\nIt also points out the minibatching problem and provides thorough results for fullbatch and minibatch training.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I appreciate the authors' effort in proposing large-scale heterophily graph datasets and along with a strong baseline LINKX.\nRecently, many researchers have looked at the performances of GNNs on heterophily graphs but most of them are testing their models on very small heterophily datasets. So this work will potentially have a great impact on the community.\nThe authors not only provide various baselines (including typical GNNs and GNNs specifically designed for heterophily graphs) but also provide thorough results for fullbatch and minibatch training.\n\nThis paper is well written and easy to follow.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have a few questions regarding the new datasets.\n1. From Table 3, it seems that GCN, in general, performs well than MLP in your heterophily datasets. It means, unlike the experiments did in small heterophily datasets, GCN can utilize graph structures in the new datasets. In the H2GCN paper, it mentions a similar situation for chameleon and squirrel datasets and points out that it is because those two datasets contain many nodes that share common neighbors. I am wondering for the heterophily datasets you provided, does this phenomenon occur in your datasets: nodes of same label share less connections but they share much more common neighbors than nodes from different classes. Can you also provide information on the 2-hop heterophily level, that is the portion of nodes from the same class in the 2-hop neighborhood but not the 1-hop neighborhood?\n2. Recent works also find degree distribution affect the performance of node classification task. I am wondering if you can also provide the information on degree distribution on those datasets?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1hr"}, "extra_text": {}}, {"review_id": "8rJ14UvDtNX", "reviewer": "Reviewer_yhQP", "summary": "The paper collects graph datasets that are not as homophile as the regular benchmarks for GNNs. Furthermore, it shows that a rather simple new baseline achieves quite good results compared to much more involved models / the SOTA. The paper presents important contributions to the community, is well and thoroughly written, related work is covered adequately, the experiments are overall thorough, and I have few to criticise. Altogether, I suggest to accept the paper.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As outlined above, I have few to critisize, I summarise the most important contributions below.\n\n- The collected (and sometimes adapted) datasets represent a useful set to move research in the field forward.\n\n- The paper actually introduces a new metric to measure homophily which is quite interesting since it overcomes issues with existing ones. I would strongly suggest to move parts of all the explanations in the appendix into the paper, especially the descriptions illustrating the latter issues. I personally consider this metric contribution at least as important as the new model.\n\n- The proposed approach is simple but effective which is quite nice, and the experiments over wiki show that such a solution was needed.\n\n- The appendix contains much additional information and insights.\n\n-------------------------------------------------------------\nQuestions & Smaller Comments\n-------------------------------------------------------------\n\nI wonder if the prediction of the year for the arxiv and patent data is a realistic task. Why would someone care about this in particular, and is it even possible to do this (ie do we expect enough variability in the data to derive such conclusions)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new bechmark for graph neural networks for non-homophilic graphs. This is an important aspect currently missing in existing datasets. The reviewers were generally positive about the paper, and most of the review comments raised ethics concerns which in the opinion of the AC have been properly addressed by the authors. The authors provided detailed responses in the rebuttal. We recommend acceptance. 
Decision: Accept (Poster)