LD2: Scalable Heterophilous Graph Neural Network with Decoupled Embeddings
Authors: Ningyi Liao
Siqiang Luo
Xiang Li
Jieming Shi
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural networks
Scalability
Heterophilous Graphs
Non-Homophily
TL;DR: We propose LD2 as a scalable heterophilous GNN with linear complexity and lightweight minibatch training.

Abstract: Heterophilous Graph Neural Network (GNN) is a family of GNNs that specializes in learning graphs under heterophily, where connected nodes tend to have different labels. Most existing heterophilous models incorporate iterative non-local computations to capture node relationships. However, these approaches have limited application to large-scale graphs due to their high computational costs and challenges in adopting minibatch schemes. In this work, we study the scalability issues of heterophilous GNN and propose a scalable model, LD2, which simplifies the learning process by decoupling graph propagation and generating expressive embeddings prior to training. Theoretical analysis demonstrates that LD2 achieves optimal time complexity in training, as well as a memory footprint that remains independent of the graph scale. We conduct extensive experiments to showcase that our model is capable of lightweight minibatch training on large-scale heterophilous graphs, with up to $15\times$ speed improvement and efficient memory utilization, while maintaining comparable or better performance than the baselines.

LD Scalable Heterophilous Graph Neural Network with Decoupled Embeddings
Ningyi Liao Nanyang Technological University 1ia000908e.. ntu. edu.sg
Siqiang Luo" Nanyang Technological University siqiang. luo@ntu. edu.sg
Xiang Li
Jieming Shi
East China Normal University Langliddase, ecnu. edu.
Hong Kong Polytechnic University j jimming. shi shi@polyu edu. edu.hk .hk
Abstract
Heterophilous Graph Neural Network (GNN) is a family of GNNs that special- izes in learning graphs under heterophily, where connected nodes tend have different labels. Most existing heterophilous models incorporate iterative non-local computations capture node relationships. However, these approaches have lim- ited application to large-scale graphs due to their high computational costs and challenges in adopting minibatch schemes. In this work, we study the scalability issues of heterophilous GNN and propose scalable model, LD", which simplifies the learning process by decoupling graph propagation and generating expressive embeddings prior to training. Theoretical analysis demonstrates that LD achieves training, as well as a memory footprint that remains independent of the graph scale. We conduct extensive experiments to showcase that our model is capable of lightweight minibatch training on large-scale hetcrophilous graphs, with up to 15x speed improvement and efficient memory utilization, while maintaining comparable or better performance than the baselines. Our code is available at: https: /ttitbbb thu.. com/ coon/gmmnl/LL2
optimal time complexity
Introduction
Graph Neural Networks (GNNs) combine graph management techniques and neural networks to learn from graph-structured data, and have shown remarkable performance diverse graph processing tasks, including node classification Common GNN models rely on the principle of homophily, which assumes that connected nodes tend to be similar to each other in terms of classes 77. This inductive bias introduces additional information from the graph structure and improves model performance in appropriate tasks (8]
2) link prediction [3] 4. and community detection [5] K
However, this assumption does not always hold in practice. A broad range of real- woal-wrldd graphs heterophilous, where class labels of neighboring nodes usually differ from the ego node [ In such cases, the aggregation mechanism employed by conventional GNNs, which only passes messages from node to its neighbors, may mix the information from non-homophilous nodes and cause them to be less discriminative. Consequently. the locality- based design is considered less advantageous or even potentially harmful in these applications [TO [T] Various solutions have been proposed to address the heterophily problem, giving rise to a class of specialized GNNs known as heterophilous GNNs. Common strategies to address heterophily include discovering multi-hop hop or global graph relations [22 13 14
15
16 17 and retrieving expressive node information through
enhanced network architectures
"Conrsponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Time and memory complexity of homophilous and honphoopppilous models with respect to precom- putation, training, and inference stages. "Batch" refers to the minibatch availability of the original model design. Training and inference memory indicate the GPU usage for storing and updating representation and weight matrices, while precomputation is mostly on RAM. Training and inference time complexity represent
the sanward-passiggg computational operations on respective node sets.
Model
Batch Pre. Mem. Training Mem.
Inference Mem.
Pre. Time Training Time
Inference Time
MLP
Y
OL +FF)
OfLnsP LF")
OilLnF")
GCN
0
N
+LLE++FF))
O[EnF LF2)
OilLonF ILrF*
O(LmE + L
GSAINT AN
O[LpIn,F + LF
OLEnF LF")
OilLpInF - IInF")
OiLmP + LnF")
APPNP 2
((m)
O[LnaF + LF9 + nms)
O[EnsF + LF + +.mm))
O(m)
OilLymE + -ImF
OLLynF InF
PPRGo
19
O(n/d)
O[IngF + L.F"
OLLnsP LFF)
Oim/5)
OiInF" + IInFF)
OinF" + LaF")
SOC
K0)
D(nF)
O(Ln,F+ + +
OLLnsF + LF
OLLymP)
OllLnF
O(LnF")
GPRGNN
106m)
O[LmF LF m))
OLEnF' LF* mn)
O(m)
OiLLymE + -1mg²))
O Lmpe)
GUNIK 21
Olhent + Lctt))
Othent + Lc
OfHamE + Hmn59)
Ottimt + Late)
MixHop
12
X
O[CLnF + CLF3)
O(CLnF CCLF))
OiLLyLaF' + (lmb")
OiLpLmF + Lit
LINKX
Olhemn + ho 4
OlbenaF Lot +
Oitmf + Haab")
Olmb + lmk?)
LD (ours)
((CuF))
O[LoneF+ Lef")
OlbeneF LeF")
O(LymF) OilLaF")
Ollaf")
Existing heterophilous GNNs are not scalable enough. Scalability has become prominent concern in GNN studies. The ever-increasing sizes of graph data nowadays can easily exceed the memory limit of devices such GPUs, rendering these models impractical for large-scale tasks [24 25 We observe that this issue is particularly critical in the context of heterophilous GNNs, due to an inherent conflict that most current models have not taken into account: heterophily-orientee designs usually rely on non-local information calculated by certain types of whole- -gappe operations. As the graph structure is involved, the time and memory overhead escalates substantially with the graph size. A recent investigation [26] reveals that all the evaluated full-graph GNNs run out of 24GB GPU memory when applied to the million-scale graph wiki (1.77M nodes, 243M edges), while minibatch strategies often result in performance loss. It is thus crucial to develop GNNs scalable to large graphs while retaining the capability for heterophily.
LD': a scalable solution via decoupling. In this work, we examine the scalability problem and propose LD², scalable GNN model for heterophilous graphs with www-Dimensional embeddings and Long-Distance aggregation. The model highlights simplicity by decoupling graph dependency from iterative computations and solely learning from a set of precomputed embeddings. Derived from node attributes and graph topology, these novel embeddings are capable of aggregating node relations of varying objectives and distances in the graph into low-dimensional features. To facilitate the decoupled scheme, we specifically propose an algorithm to efficiently estimate all embeddings before training, which enjoys time complexity only linear to the graph scale and guaranteed precision bound. After the precomputation, a simple but powerful multi-channel neural network is subsequently employed to learn from the extracted node features. Theoretical and empirical results showcase that the combination of embeddings effectively retrieves representations among heterophilous nodes. On the efficiency aspect, LD2 is advantageous in its scalable design, including the straightforward minibatch scheme, optimal training and inference times, and the superior memory utilization.
Our contribution. (1) We propose LD2 as scalable GNN under heterophily, which removes the reliance on iterative train-time full-graph computations. The model realizes theoretically optimized training, highlighting time complexity that is only linear to the number of nodes O(n) and memory overhead independent of the graph scale. To the best of our knowledge, LD² is the first model achieving such optimization in the context of heterophilous GNNs. (2) We design an array of feature and topology embeddings by applying multi-hop discriminative propagation, encoding expressive node representation within a compact size. An end-to-end precomputation algorithm is proposed for efficient embedding calculation with a linear complexity.
(3) We conduct comprehensive experiments to evaluate the efficacy and efficiency of LD2. On large-scale datasets, our model demonstrates 3-15x x faster minibatch training and inference, and up to 5x smaller memory footprint than state of the art, with comparable or better accuracy. Particularly, it completes training on the wiki dataset within 1 minute and inference in 0.1 seconds, demanding only 5GB of GPU memory.
2 Preliminary and Related Work
Graph Notation and Heterophily. In an undirected graph G = (V, E) with node set V and edge set F, the number of nodes, number of edges, and average degree are denoted by = [V] m = |E]. and = m/n, respectively. The neighhorhood of an ego node u E V the set N(() = (o|(u,,) v) E F.. and its degree d(u)= [W(,)). The diagonal degree matrix is D = diag(d(u,)) d(uu). ,d(u,))
2

---

The graph connectivity is represented by the adjacency matrix A E R We adopt the general
graph normalization scheme [1 62] with coefficients a, b E [0, 1] and Á D n "AD ? normalized adjacency matrix with self-loop edges is also frequently used, which is denoted as A D) - -I A) + D) D)- and the corresponding graph Laplacian matrix is L I - A. Each node u E V is represented by an F-dimensional attribute vector X X(),, which composes the attribute matrix X E RRaXF, The graph heterophily is measured by the node homophily score [1]] which is the average proportion of the neighbors with the same class of each node.
The
Vanilla and Sampling-based GNNs. We summarize our analysis of the time and memory complexity of related GNN models in Table [ In general, a GNN recurrently computes the node representation ()) in its (-th layer. For the vanilla GCN M. the model input is the attribute matrix H X,
and the layer representation is updated by H 04+1) = o (AA (HHW)))) = 0, 1,.............. .... .L - 1, where W is the trainable weight matrix each layer, (-)) is the activation function, and L is the number of layers. For simplicity we assume the feature size F to be constant in all layers. Previous research points out that the operation of dominating expense in both GCN training and inference is the graph propagation Á- H which can be regarded repetitive sparse matrix multiplications, resulting in total complexity OLLFF). The overhead for feature transformation by applying W is (LL These two procedures are iteratively performed for I epochs throughout training. In terms of memory usage. GCN typically requires O(LnF + LF²) space to store layer-wise node representations and weight matrices, respectively. For large-scale cases where n > F, the overhead of dense node representations F( becomes the primary term 24
K3 31
The above analysis indicates that the scalability bottleneck of GCN lies in the time complexity of graph propagation well as the memory overhead of full-graph representation. There is a large scope of GNNs attempting to address the issue by sampling techniques, which simplify the propagation by replacing the entire graph with subgraphs in minibatches P 27 33
For example, the widely-used GSAINT Pd incorporates Lp-hop random walk sampling, reducing the in-memory representation to O(pp where n, is the batch size. However, it is not applicable to the inference stage.
Full-graph Heterophilous GNNs, In the context of GNNs under heterophily, large number of models augment the spatial graph convolution to a full-graph scheme, relying upon the complete graph topology to compute inter-node relationships. For instance, H,GCN [3 and MixHop [12]
incorporate 2-hop propagation A (1), while GeomGCN 44 and GloGNN 22
exploit hierarchical
computation on non-local connections. These high-order calculations are shown to be effective in retrieving information beyond immediate neighbors, but come at the price of more complex propaga- tion operations. Another common practice for non-homophilous design is altering transformation to learn from multiple features, i.e. channels. MixHop 12 mixes its multi-hop representation as H(+1) of H w(()) ( ())) | HO W((), where (-11-) denotes matrix concatenation. GGCN 19 and ACM 200 select frequency- based filters expressed by ÁHW. (I A), IHW,, while GCNJK 21 records individual layer representations as channels. Denote the number of channels as C' and Le = L + C, employing multi-channel learning increases the memory budget for node representations and weight matrices by factor related to C Lo-
Alternatively, a line of approaches choose to apply learnable spectral filters for flexibility on non- homophilous data, deriving specific propagation in the spectral domain for various graphs. GPRGNN 17 generalizes the multi-hop propagation as T= = Σiz Á' which inevitably involves the entire adjacency matrix for acquiring weight factors 0, BernNet 34 and ChebNeill 35 respectively utilize L. Bernstein and Chebyshev polynomials with respect to L to approximate their spectral filters. These models focus relatively more on the expressiveness of graph propagation rather than the overall GNN architectural design, usually demanding additional cost for determining spectral filters and updating the learnable basis.
In spite of their advantageous capabilities, above full-graph designs hardly address the scalability bottleneck in GNN propagation, which can be observed from the O(n) or Ó()) terms their com- plexity. Recent studies also discover that heterophilous GNNs are naturally unsuitable for enforcing scalable training via sampling-based minibatching, since their distant or full-graph information is heavily overlooked in batches built on locality I.. Evaluations show that simply fitting these models to learn from induced subgraph samples causes performance degradation 26 Therefore, we believe these full-graph models targeting effectiveness are orthogonal to our study scalability.
3

---

Decoupled GNNs. As the scalability of GNN is closely tied to the graph propagation, promising approach to simplify the process is decoupling it from iterative training and efficiently computing in advance. The representative two-stage model SGC RC encodes graph information with X into an embedding matrix P = ur X, which is then input to a Multi-Layer Perceptron (T(2) MP.
further generalize the embedding aggregation. Such decoupled GNN is considered optimal for training efficiency, as its time complexity OmL))) is identical to the simple MLP B
36
32
2
However, applying the decoupling technique to heterophilous GNNs is non-trivial due to the full- graph relationships. To our knowledge, LINKX 2d is the only model conceptually similar this scheme, removing graph-relater propagation during training iterations and enabling solely node-wise minibatching. It exploits a simple architecture H MLP(X (X Wx ||AWa)), where the matrix A is used as an input feature in learning. The major drawback of this design is that it suffers from the O(nF) term model size and (mF)) term in forward time, hindering scalability to large graphs.
3 Method
In this section, we first present an overview of our LD" model, then respectively elaborate on the selection of the adjacency and feature embeddings. Lastly, an end-to-end scalable algorithm, namely Propp, is proposed to efficiently and concurrently compute all the embeddings.
3.1 LD A Decoupled Heterophilous GNN
In order to achieve superior time and memory scalability for heterophilous GNNs, we employ the concept of decoupling, which removes the dependency of graph adjacency propagation in training iterations. The main idea of our model is first generating embeddings from raw features including node attributes and adjacency in a precomputation stage. Then, these embeddings are taken as inputs learn representations by a simple neural network model. We embrace the multi-channel architecture 337 20) to enhance flexibility, where the input data a list consisting of embedding matrices [Pi, P2. ,,, Pc). P. Each embedding is separately processed and then merged in the network.
LD² utilizes diverse embeddings based on pure graph adjacency and node attributes, denoted as (A(A) and (x A), respectively, Both types of embeddings can be produced by our precompu- tation A Prop following Algorithm|| The initial layer of the LD2 network applies a separate linear transformation each embedding input, and the results are concatenated form the representation matrix. Lastly, an L-layer MLP is leveraged for the classification task. The high-level framework of
LD2 is depicted in Figure and can be expressed as follow:
Precompute: PA, Px = Propp X); Transform (L) = MLP(PAWA Px (1)
Training/Inference Complexity, Our decoupled model design enables a simple on-demand mini- batch scheme in training and inference, that only n, corresponding the batch nodes in the embedding matrices are loaded into GPU and processed by the network transformation. For LD with C' channels, the GPU memory footprint is therefore bounded by O(LensF + F*F.). is worth noting that such complexity does not depend on the graph scale or m. Consequently, the training freely configurable with an arbitrary GPU memory budget. Regarding computation operations, the time complexity of forward inference through the graph is O(LFF²), being just linear to n. As
Precomputation
Training/Inie Inference
Constunt 2-hop Adjucency Propagation
h-h
2-hop
R
X
Σ
A
P
MLP
1.2
0
Y
F
ArProp
H )
G
H
14
21
14
ΣA'
P
0)
PH
4)
WA
I-hop
L-hop
I-hop
1-hop
Approximate Propagation
Feature Embedding
Feature Transformation
Inverse hhhpp Laplacian Propagation
Figure 1: LDd framework: decoupled precomputation and training. Figure 2: Propagations under heterophily.

---

the model complexity only contain essential operations of MLP-like transformation on nodes in the graph with no additional expense, this the optimal scale with respect to the iterative training of GNN architectures.
3.2 Low-Dimensional Adjacency Embedding
Several studies reveal that, despite the feature information of nodes, the pure graph structure is equally or even more important in the context of heterophilous GNNs 1 14 261. Particularly, the most informative aspects are often associated with 2-hop neighbors, i.e., "neighbors of neighbors" of ego nodes.
3 proves that even under heterophily, the 2-hop neighborhood is expected to be homophily- dominant. also verifies that the 2-hop similarity is strongly relevant to GNN performance. We thence intend to explicitly model such topological information.
K
The 2-hop relation can be described by the 2-hop adjacency matrix A Note that as the sparse matrix A has m entries, the number of entries in A is at the scale of ((md), which indicates that directly applying 2-hop graph propagation in the training stage will demand even more expensive time and memory overhead to be scaled up. We instead propose an approximate scheme that seeks to prevent the 2-hop adjacency from explicit processing, and retrieves a low-dimensional but expressive embedding prior to training in the precomputation stage. In other words, we utilize the embedding to resemble 2-hop information which can be directly learned by the neural network transformation. Denote the F F-dimensional embedding matrix as PA E RaxF, We aim to minimize its approximation error in Frobenius norm (l) [[F)::
PA
arg min ||A2 P PER F
The solution to Eq. can be derived from the eigendecomposition of the symmetric matrix A?, that P7 = U| where = diagg(i, Xp) is the diagonal matrix with top-F eigenvalues a1 2 A2 2 ... 2 Ar. and U RRax the matrix consisting of corresponding orthogonal eigenvectors. The eigenvalues are also called frequencies of the graph, and large eigenvalues of the adjacency matrix refer to wwwffreueeccy signals in the graph spectrum.
Spectral Analysis. Let Az(u, u) be the entry (u, v) of matrix A². Its diagonal degree matrix is D2 = diag(dz(u)) (u.) d2 (un)), where da(u) = Evev Az(u, v). Denote (a( as the
F-dimensional adjacency embedding vector of node u. We show that the embedding matrix P defined by Eq. 2 also the solution to the following optimization problem:
PA
min PEROXE P MREV
Σ
A2(u, uMl,,))lP(v)) P(U)1
(3)
2E,,. This is because En,o Az(u, e) P(o)11 -2 d2(w)] - u,u A2(u, (())
2 tr(PPT D,P P A²P). As P D&P is fixed, finding the minimum of Eq. ( is equivalent to optimizing maxp P A of which the solution is exactly PA according to the property of
eigenvectors. Equation c3) implies that, 2-hop neighbors (u, v), E NNu), E N(l)) in the graph will share similar embeddings (u( and (1)
In fact, the low-dimensional embedding PI can interpreted as the adjacency spectral embedding of the 2-hop graph A², Graph spectral embedding is technique concerning the low-frequency spectrum of a graph, and employed tasks such as graph clustering [39]. As PA corresponds to the dominant eigenvalues of A², 2 the embedding provides an approximate representation of the 2-hop neighborhoods based on the overall graph topology. Alternatively, adjacency information solely as features input into the network like LINKX, PA correlates to the uncentered principal components of matrix A. Therefore, learning a linear transformation PAWA with weight matrix WA IR Px F in LD2 is the same expressive as the rank- approximation of AWAo AO in LINKX, where WAO E RR.FF. but with a less computational cost independent to the graph scale. Compared other works attempting to generate graph embeddings based graph geometric or similarity measures 40) 41 [4] 16 19 42]. our approach offers the advantages of lower dimensionality and efficient calculation demonstrated in Section 3.4
we regard the
3.3 Long-Distance Feature Embedding
Decoupling the node features through approximate propagation has been extensively studied in regular GNNs with various schemes 22
30
36
29
4 32 Nonetheless, these approaches are
5

---

based on the homophily assumption and focus on local neighborhoods. In order to apply decoupled propagation heterophilous graphs and exploit the multi-channel ability of our model, we formulate the general form of approximate propagation as the weighted sum of powers of propagation matrix applied to the imput feature, i.e., Px Σ I.''X. Examples of propagation matrix T include A and L, which respectively correspond to aggregative and discriminative operations.
LD2 utilizes the following channels jointly as input embeddings: (1) inverse summation of 1-hop
improved Laplacian propagations Px.HI T.P. Elp." (I+L) L)'X, (0) = 1, T = I+ L); (2) constant
summation of 2-hop adjacency propagations Px,12 Lp,L2 raw node attributes Px.0 = X.
1 Ein X (0c 1, T =)); (3)
Intuitively, the first two channels perform distinct topology- propagations on node feature X, and employ inverse or constant summation to aggregate multi-hop information, in contrast to the local decaying summation (0; -> when -> xc) commonly adopted in homophilous GNNs. Hence, such summations are suitable for retrieving long-range information under heterophily. The raw matrix X also directly used as one input channel to depict node identity, which is a ubiquitous practice known as the skip connection or all-pass filter in heterophilous GNNs 12
35
20 22
Illustrated in Figure 2 the inverse embedding Px, based on the intuition that, as neighbors tend to be different from the ego node, their features are also dissimilar. Hence in propagation, the embedding of the ego node should contain the previous embedding of itself, as well as the inverse of adjacent embeddings, which is exactly the interpretation of propagating node features by graph Laplacian matrix 1 = I- I-A, A, while an additional identity matrix is applied to balance the embedding distribution. The second embedding Px.12 performs a 2-hop propagation through the graph and aggregates the results of multi-scale neighbors. It echoes the earlier statement on the importance of 2-hop adjacency from the feature aspect. Note that for Px,L2, the employed adjacency matrix is A which escapes self-loops, since it is shown to be relatively favorable for capturing non-local homophily in multi-hop propagations compared with A
Spectral Analysis. Assume that (u)ll = P(u)] = 1. We first examine the following regular- ization problem optimizing the embedding P based on input X for homophilous graphs 43
PX. =
arg min
Σ B.VVV
- P(o)/d ((u))))lP())(((() |P
+
X p
(4)
Differentiating the objective function with respect to leads to (I -T-AN (I-A)P - X 0. Therefore the closed-form solution is , = (I -) Σi Á'x. In practical implementation, a limited Lp,u-hop summation is used instead due to the smooshho issue that the infinite form converges to identical node-wise embeddings. This Markov diffusion kernel Px.L = T. L'... A' X inves-
tigated in SCGC [R] as approach for balancing locality and multi-hop propagation, functioning as a low-pass filter to the signal X but also preserves high frequency. Its interpretation can be observed from Eq. 4 that it simultaneously minimizes the embedding difference of neighboring nodes as well as the approximation closeness to the input feature X.
To obtain the channel Px,L2 used in LD?, we introduce the now-frequency regularization preferably to 2-hop adjacency in the graph, as I-hop neighbors exhibit heterophily. Therefore, replacing A (u, v) in Eq. 44 with A2(u, (u, v) yields our constant 2-hop embedding Px,L2- It shares similar spectral properties with S²GC for acting as a low-pass filter in 2-hop neighborhoods, while maintaining certain long- distance knowledge thanks to the multi-scale aggregation. The other channel in feature embedding, i.e. the Laplacian propagation, can be derived as Px. (I + L) A x = (I + Px. Based on the above analysis, the embedding Px.L contains multi-hop neighborhood information, while (I + L) can be seen as the improved Laplacian operator extracting the figh-frequency components. The embedding Px, thus serves as high-pass filter focusing on discriminative structures in a non-local manner. In terms of spatial domain interpretation, such gighfreeuency information corresponds to the fine-gran -rained embedding differences between two nodes 18 46 It is noticeable that these three channels Px,122 Px, Px.o respectively represent low-pass, high-pass, and all-pass propagations through the graph while addressing heterophily. Combining them as inputs to the neural network benefits the model performance with expressive information at various distances including identity, local, and global perspectives.

---

3,4 Approximate Adjacency Propagation Precomputation
Conventionally, calculating the graph propagation Á P for an arbitrary feature matrix P is conducted by the sparse-dense matrix multiplication. However, such an approach does not recognize the property of the adjacency matrix Á, that it can be represented by the adjacency list of nodes, and non-zero values in its data solely determined by node degrees. Furthermore, since the propagation result is subsequently processed by the neural network, it is not necessary to be precise as the model is robust handle noisy data [46 477. We first define the precision bound for approximate embedding:
Definition 3.1 (Approximate Vector Embedding). Given relative error bound 0 < 1. norm threshold 8 O, and a failure probability O < Φ < 1, the estimation P()) an arbitrary embedding vector (u) should satisfy that, for each V with [| > 6, PP(() P(u)ll S e- [| with probability at least Ø.
Graph power iteration algorithm is the variant power iteration particularly applied for calculating powers of adjacency matrix A 48 In essence, the algorithm can be derived by maintaining a residue (u) that holds the current 1-hop propagation results for each node, and iteratively updating the next-hop residues of neighboring nodes R 1) (o), E (N)u) for all nodes u. For each iteration, the reserve (!)) is also added up and converges to underestimation of P.
We propose Algorithm | for our specific scenario, namely Approximate Adjacency Propagation (ArProp). Based on power iteration, our algorithm is greatly generalized to accommodate normalized adjacency, feature vectors for nodes, and limited number of hops. We show that the algorithmic output can be bounded by Definition 3..] For Lp iterations, denote the acceptable error per entry for push as 0p, the mase absolute error is |IP Pll.. S Σ f-1 Evev d(u)ōp LpmFipr
By setting 8p = c6/ L, the estimation P satisfies Definition 3.1
Approximate Feature Embedding. The feature embedding formed Px = ー 0,T X can be computed by iteratively applying graph power iterations to the initial residue (( = X. The implicit propagation behavior described by matrix T. For example, for Laplacian propagation T = I + LL to node u, the embeddings from the previous iteration are aggregated as ( (u) = 2n (u)
EveN(") (x)/dd (w) Even (()N(())(N) a (o) (v). Here ar v) is a propagation
(u,e)
factor for unifying the aggregation by T. that (z u) 2d (u, = -1, (u)) For propagation Á and A. the factor is a (u, v) 1 and (A(u, u) 1, 1,0. respectively.
In each iteration I, the reserve is updated after propagation according to the coefficient to sum up corresponding embeddings. Intuitively, one multiplication of A is equivalent to two iterations of A propagation. Hence for Px,12 there is l mod 2 0, 1, 0, 1, under the summation scheme
Algorithm A Prop:: Approximate Adjacency Propagation
Input: graph G. feature matrix X. max hop I.p, normalization factor b.
propagation factor cry, summation factor 0j push threshold 6p
Output: adjacency embedding PA. feature embedding Px
Pil8
R0(0) N(0, 1). R2(0)
X
2 from to Lp do
3
R(+1)) + 0, R(+1)
Propagation Eap
10
14
16
4
for all u E V such that (w)l > 8p do
(a) genius
5
for all E (u)) {x) do
R 11+1) (v) - R (1+11) (v) as, R (u)
6
(v) + R 1++) (v) ("())""())) R (u)
(7(a))
7
8
I mod and < Lp then
Pae Balio
PA orthonormslizer (2)
P.P Ma1
Px + Px + 8 R(
empty A !
11
16
Mie Propagaton Bop
PA PA (R) (((E))yTT PA 1/2
(b) pokec
Px + Px + 0ip R(pp)
Figure 3: Effect of embedding channels and propagation hops on accuracy.
PA, Px
7

---

in Algorithm ! Since all embeddings we consider are constant, that is, 0t E {0. 1), the reserve can be simply increased without the rescaling terms in more general cases such as [32
Approximate Adjacency Embedding. The adjacency embedding is represented by leading eigen- vectors PA- = U A 1/2, This eigendecomposition of A can be solved by the truncated power iteration 4 : Initialize the x F residue by i..d. Gaussian noise R N N(, 1). For each iteration 1, firstly multiply the residue by A as R (!-1) A R then, perform column wise normalization to the residue orthonormal ize (((++)) so that its columns are orthogonal to each other and of L2 norm 1. After convergence, the matrix satisfies A2R( = R(Le) A within the error bound, which leads to the estimated output Ù R((,)) PA- A///
Similarly, the 2-hop power iteration of PA can merged with those for Px with shared maximal iteration Lp, and orthonormalization is conducted every two A iterations. When the algorithm converges with error bound 6, the number of iteration follows I.p = (1oo((//))/ F/ - |rr+r/////// Arl)) By selecting proper values for F and 6, the algorithm produces satisfying results within I.p iterations.
Precomputation Complexity. Since A Prop serves as a general approximation for various adjacency- based propagations, the computation of all feature channels can be performed simultaneously in single run. The memory overhead of the algorithm is mainly the residue and reserve matrices for C embedding channels. which is OCCFF) in total. Note that A Propp precomputation performed in the main memory, and benefits from constranddd budget compared to GPU memory.
For each A Prop iteration, neighboring connections accessed for at most times. The time complexity of Algorithm 1 can thus be bounded by (LpmFF). In addition, its loops over nodes and features can be parallelized and vectorized reduce execution time. Moreover, the graph power iteration design is also amendable for further enhancements, such as reduction to sub-linear complexity [50 25 better memory utilization [5l 522, and precision-effiiencyy trade-offs [53
We leave these potential improvements on A Prop for future work.
Experimental Evaluation
We implement the LD2 model and evaluate its performance from the perspectives of both efficacy and scalability. In this section we highlight key empirical results compared to minibatch GNNs on large-scale heterophilous graphs, while parameter settings, further experiments, and subsequent discussions can be found in the Appendix.
4.1 Experiment Setting
Datasets. We mainly perform experiments on million-scale and above heterophilous datasets 26 55
for the transductive node classification task, with the largest available graph wiki (m = 243M)
included. Evaluations on more homophilous and heterophilous graphs can be found in Appendices
[ We leverage settings as per [26] such as the random train/test splits and the induced subgraph testing for GSAINT-sampling models.
Baselines. We focus on GNN models applicable minibatch training in our evaluation regarding scalability, and hence most full-batch networks mentioned in Section 2 are excluded in the main experiments, while more comprehensive results for both minibatch and full-batch models are in Appendices D and E Conventional baselines in the main experiments include MLP which only processes node attributes without considering graph topology, as well as PPRGo [ and SGC 30 representing decoupled schemes for traditional graph propagation. For GNNs under non-homophily, we investigate GCNJK-GS [2T] and MixHop-GS (12] where GSAINT random walk sampling [27 is utilized to empower the original backbone models for minibatching. LINKX is the decoupled heterophilous GNN proposed by 26). Simple i.i.d. node batching is adopted for decoupled networks. Explorations on the model settings are displayed in Appendix
Evaluation Metrics. We uniformly use classification accuracy on the test set to measure network effectiveness. Note that since the datasets are updated and the minibatch scheme is employed, results may be different from their original works. In order to evaluate scalability performance, we conduct repeated experiments and record the network training/inference time and peak memory footprint as efficiency metrics. For precomputed methods, consider the learning process combining both
8

---

Table Average test accuracy (%) of minibatch LD² and baselines on heterophilous datasets. "> 12h1" means the model requires more than 12h clock time to produce proper results. Respective results of the first and second best performances on each dataset are marked in bold and underlined fonts.
Dataset
genius
tolokers
arxiv-year
penn94
twitch-gamers
pokec
snap-patent
wiki
Nodes n
421,858
11,758
169,343
41,536
168,114 14 6,797,557
1,632,803
2,738,035
1,770,981
Edges m
922,864
1,038,000
1,157,799
1,362,220
22,301,964
13,967, ,999
242,507,069
F/ N.
12/2
10/2
128/5
4
7/2
65/2
269
/
MLP
82.47 20.06
73.38
#025
37.23
20.31
74.41
20.48
61.26
10.19
61.81 #0.07
23.03 11.48
35.64 10.10
PPRGo
79.81 20.00
78.16
20.00 39.35
20.12 58.75
#0.31
47.19 22
50.61 #0.04
(>12h)
(>12hh
SGC
79.85
71.16
#0.66 43.40
20.16 68.31
#0.27
57.05 #021
56.58 #0.06
37.70
28.12 20.08
GCNJK-GS
80.65
#0.07 74.41
+0.73 48.26
20.64 65.91
20.16
59.91
59.38 #0.21
33.64
20:05
42.95 #0.39
MixHop-GS
80.63 #0.04 77.47
+0.0 49.26
10.16 75.00
20.37
61.80
64.02 #0,2
34.73
10.15
45.52 #0.11
LINKX
82.51 +0.10
77.74
10.13 50.44
+0.30 78.63
20.25
64.15
68.64 08.64 20,6
52.69 +0.05
50.59 10.12
LD (ours)
85.31 +0.06 79.76 20 50.29 10.11 75.52 10.10
64.33 10.19
74.93 10.10
58.58 +0.34
52.91 10.16
Table Time and memory overhead of LDD and haselines on large-scale datasets. "Leamn". "Infer", and "Mem." respectively refer to minibatch learning and inference time (8) and peak GPU memory (GB). Precomputation time is appended when applicable. "> 12h" means the model requires more than 12h clock time to produce proper results. Respective results of the first and second best performances among heterophilous models per metric marked in bold and underlined fonts.
twitch-gamers
pokec
snap-patents
wiki
Dataset
Learn
Infer
Mem.
Learn
Infer
Mem.
Learn
Infer
Mem.
Learn
Infer
Mem.
MLP
6.36
0.02
0.61
47.86
0.11
13.77
27.39
0.28
9.33
133.55
0.62
18.15
PPRGo
10.66
15.88
0.41
9.64
121.95-5.11
2.69
3.82
(>12h)
(>12h)
SGC
0.09+0.74
0.01
0.28
L.058.08
0.01
0.28
4.94+3..54
0.01
0.42
12.66+7.98
0.01
0.52
GCNJK-GS
71.48
0.02
7.33
27.33
0.09*
9.03
19.02
0.23
9.21
95.52
0.69"
16.36
MixHop-GS
52.12
0.01
1.49
71.35
0.03*
12.91
45.2
0.16"
19.58
84.22
0.23"
16.28
LINKX
10.99
0.19
2.35
28.77
0.33
9.03
39.80
0.22
21.53
180.71
1.14
14.53
LD' (ours)
0.85-1.96
0.01
1.44
17.95+6118
0.01
3.82
31.32+6.96
0.02
3.96
18.12+
0.01
4.47
Inference time of GSAINT sampling is less precise since they are conducted on induced subgraphs smaller than the raw graph.
precomputation and training. Evaluations are conducted on machine with 192GB RAM, two 28-core Intel Xeon CPUs (2.2GHz), and an NVIDIA RTX A5000 GPU (24GB memory).
4.2 Performance Comparison
The main evaluations of LD² and baselines on 8 large heterophilous datasets are presented in Tables 2 and B for effectiveness and efficiency metrics, respectively. As an overview, our model demonstrates its scalability in completing training and inference with fast running speed and efficient memory utilization, especially on large graphs. At the same time, it achieves comparable or superior prediction accuracy against the state-of-the-art minibatch heterophilous GNNs on most datasets.
Time Efficiency. We first highlight the scalability performance of our LD² model. Specifically, compared to heterophilous benchmarks on the four largest graphs with million-scan scale data, LD speeds up the minibatch training process by 3-15 times, with an acceptable precomputation cost. Its inference time is also consistently below 0.1 seconds. The outstanding efficiency of LD2 is mainly attributed to the simple model architecture that removes graph- scale operations while ensuring rapid convergence. In contrast, the execution speeds of MixHop and LINKX are highly susceptible to node and edge sizes, given their design dependency the entire input graph. The extensive parameter space also causes them to converge slower, necessitating relatively longer training times. PPRGo shows limited scalability due to the costly post-transformation propagation. The superiority of LD² efficiency even holds when compared to simple methods such as MLP and SGC, indicating that the model favorable for incorporating extra heterophilous information with no significant additional overhead. The empirical results affirm that LD2 exhibits optimized training and inference complexity at the same level as simple models.
Memory Footprint LD2 remarkably reduces run-time GPU memory consumption. As the primary overhead only comprises the model parameters and batch representations, it enables flexible config- uration of the model size and batch size to facilitate powerful training. Even for the largest graph

---

wiki with n = 1.77M and F = 600, the footprint remains below 5GB under our hyperparameter settings. Other heterophilous GNNs, though adopting the minibatch scheme, experience high memory requirements and even occasionally encounter out-of-memory errors during experiments, as their space-intensive graph propagations are executed on the GPU. Consequently, when the graph scales up, they can only be applied with highly constrained model capacities to conserve space, potentially resulting in compromised performance.
Test Accuracy. With regard to efficacy, LD² achieves top testing accuracy out of heterophilous graphs and comparable performance on the remaining ones. It also consistently outperforms the sampling- based GCNJK and MixHop, well conventional GNNs. Particularly, by extracting embeddings from not only node features but pure graph topology as well, LD² obtains significant improvements over feature-based networks demonstrating the importance of pure graph information in heterophilous learning. We deduce that the relatively suboptimal accuracy on penn94 may be correlated with the difficulty of fitting one-hot encoding features into informative embeddings, as explored in Appendix G Consistent with the previous studies [26]. regular GNN baselines suffer from performance loss on most heterophilous graphs, while MLP achieves comparably high accuracy when node attributes are discriminative enough. For -omohhiopliuu models GCNJK and MixHop. the minibatch scheme hinders them from reaching higher results because of the neglect of their full-graph relationships.
datasets such genius, snap-patents, and wiki,
4.3 Effect of Parameters
To gain deeper insights into the multi-channel embeddings of LD2, in Figure S we explore the effect of embeddings channels and propagation hops which are critical to our model design, while more discussions on other parameters and factors are displayed in Appendix F
Embedding Channels. Lines in Figure 3 represent the results learning on separate inputs on two representative datasets genius and pokec. It can be observed that different graphs imply varying patterns when embedding channels and propagation hops are changed. For the genius dataset where raw node attributes already achieve an accuracy above 82%, applying the other two feature embeddings further improves the result. While the adjacency embedding alone shows secondary performance, integrating it with other channels proves beneficial. In comparison, on pokec, it is the inverse embedding Px. that becomes the key contributor. The empirical evaluation supports our design that by adopting multi-channel and heterophily-oriene learning both topology and feature for a more comprehensive understanding of the graph data.
embeddings, LD² benefits from
Propagation Hops. As elaborated in Section 3.4 propagation hops Lp determines the number of iterations in Algorithm 0 Particularly, for the approximate adjacency embedding PA. it also affects the convergence of decomposition. As shown by the brown dashdotted lines Figure g the accuracy typically becomes stable when I.p >> 8, indicating the utility of the fow-dimensional approximation in producing effective topology embedding within limited iterations. For the multi-channel scheme in general, as the graph scale increases, employing more propagation hops becomes ad advantagcous in capturing distant information. Aligned with our analysis, above observation validates that LD" is powerful in capturing implicit information of various frequencies and scales that is important in the presence of heterophily.
5 Conclusion
In this work, we propose LD?, a scalable GNN design for heterophilous graphs, that leverages long-distance propagation to capture non-local relationships among nodes, and incorporates low- dimensional yet expressive embeddings for effective learning. The model decouples full-graph dependency from the iterative training, and adopts an efficient precomputation algorithm for approxi- mating multi-channel embeddings. Theoretical and empirical evidence demonstrates its optimized training characteristics, including time efficiency with a complexity linear to (m)), and GPU memory independence from the graph size n and m. As noteworthy result, LD2 successfully applies to million-scale datasets under heterophily, with learning times as short as I minute and GPU memory expense below 5GB. We also recognize the current limitations of our work including potential accelerations for precomputation and adaptability to diverse feature patterns. Detailed limitations and broader impacts are addressed in the Appendix.
10

---

Acknowledgments and Disclosure of Funding
This research is supported by Singapore MOE AcRF Tier-2 funding (MOE-12FP201122-000) NTU startup grant (020948-0000)) and the Joint NTUU-eBank Research Centre on Fin'Tech. Xiang Li supported by National Natural Science Foundation of China No. 62202172 and Shanghai Science and Technology Committee General Program No. 22ZR 1419900. Jieming Shi is supported by Hong Kong RGC ECS No. 25201221 and National Natural Science Foundation of China No. 62202404. We also thank Yuyuan Song for contributing to the experiments in this paper.
References
[1] Kipf. T. N.. M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations: 2017.
[2] Hamilton, W.T.., R. Ying, J. Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025-1035. 2017.
[3] Zhang, M., Y. Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5 165-5155, 2018.
[4] Ying. R., R. He, K. Chen, et al. Graph convolutional neural networks for web-scale recommender systems. In Proceedingy of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 983. 2018.
[5] Al-Rfou, R., B. Perozzi, D. Zelle. Ddgk: Learning graph representations for deep divergence graph kemels. In The World Wide Weh Conference, pages 37-48. 2019.
[6] Chen, Z., Bruna, L. Li. Supervised community detection with line graph neural networks. 7th International Conference on Learning Representations, 2019.
McPherson, M., I.. Smith-LLvv.. J. M. Cook. Birds of feather: Homophily in social networks. Annual Review of Sociology, 27(1):115-44, 2001.
[8] Battaglia, P. W., J. B. Hamrick, V. Bapst, al. Relational inductive biases, deep learning, and graph networks. NVV.1880001260 2018
Altenburger, K. M., J. Ugander. Monophily in social networks introduces similarity among friends-of- friends. Nature Human Behaviour, 2(4):284-2) 2900 2018.
[10] Breucr, A., Eilat, U. Weinsberg. Friend faux: Graph-based early detection of fake accounts social networks. Proceedings of The Web Conference 2020, WWW '20, page 1287-1297. ACM, 2020.
[11] Zheng, X., Y. Liu, S. Pan, et al. Graph neural networks for graphs with heterophily: A survey, arXiv:2202.0708: 2022.
[12] Abu-Fl-Haija, S., B. Perozzi, A. Kapoor, et al. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. 36th International Conference on Machine Learning, vol. 97. PMLR, 2019.
[13] Zhu, J., M. Heimann, Y. Yan, et al. Beyond homophily in graph neural networks: Current limitations and effective designs. In 33rd Advances in Neural Information Processing Systems, page 12. 2020.
[14] Pei, H., B. Wei, K. C.-C. Chang, et al. Geom-gon gen: Geometric graph convolutional networks. International Conference on Learning Representations, 2020.
[15] Zhu, J., R. A. Rossi, A. Rao, et al. Graph neural networks with heterophily. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12 35(12)111166 166-11166,, 2021.
[16] Suresh, S., V. Budde, J. Neville, et al. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
[17] Chien, E., J. Peng, P. Li, et al. Adaptive universal generalized pagerank graph neural network. In 9th International Conference Learning Representations. 2021.
[18] Bo. D., X. Wang, C. Shi, et al. Beyond Iow- www-frquency information in graph convolutional networks. Proceedings of the AAAI Conference Artificial Intelligence, 35(5):3950-33) 3957, 2021.
11

---

[19] Yan, Y., M. Hashemi, K. Swersky, et al. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 22nd IEEE International Conference on Data Mining. 2022.
[20] Luan, S., C. Hua, Q Lu, et al. Revisiting heterophily for graph neural networks. In 36th Advances in Neural Information Processing Systems. 2022.
[21] Xu, K., C. Li, Y. Tian, et al. Representation learning on graphs with jumping knowledge networks. In 35th International Conference on Machine Learning, vol. 80. PMLR, 2018.
[22] Li, X., R. Zhu, Y. Cheng, et al. Finding global homophily in graph neural networks when meeting beterophily. In 39th International Conference on Machine Learning. 2022.
[23] Maurya, S. K., X. Liu, T. Murata. Simplifying approach to node classification in graph neural networks Journal of Computational Science, 62:101695, 2022.
[24] Peng, J. Z. Chen, Y. Shao, et al. Sancus: Staleness aware communication communiationn-gvodingg full-graph decentralized training in large-scale graph neural networks. Proceedings of the VLDB Endowment, 15(9):1937-199) 1950. 2022.
[25] Liao, N., D. Mo. S. Luo, al. Scara: Scalable graph neural networks with feature-oriented optimization. Proceedings of the VLDB Endowment, (5(11):3240-248 2022.
[26] Lim, D., Hohne, X. Li, et Large scale learning on non- homophilous graphs: New benchmarks and strong simple methods. In 34th Advances in Neural Information Processing Systems. 2021.
[27] Zeng, H., H. Zhou, A. Srivastava, et al. Graphsaint: Graph sampling based learning method. In International Conference on Learning Representations. 2019.
[28] Klicpera, J., A. Bojchevski, S. Günnemann. Predict then propagate: Graph neural networks meet personal- ized pagerank. 7th International Conference on Learning Representations, pages 1-15, 2019.
[29] Bojchevski, A., J. Klicpera, B. Perozzi, et al. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 1464-2473 ACM, 2020.
[30] Wu, F., A. Souza. Zhang, et al. Simplitying graph convolutional networks. In K. Chaudhuri, R. Salakhut- dinov, eds., Proceedings of the 36th International Conference on Machine Learning, vol. 97, pages 2019.
[31] Chen, M., Z. Wei, B. Ding, et al. Scalable graph neural networks via bidirectional propagation. 33rd Advances in Neural Information Processing Systems, 2020.
[32] Wang, H., M. He, Z. Wei, et al. Approximate graph propagation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1686-1696. ACM, 2021.
[33] Chiang, W.-L., X. Liu, S. Si, al. 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 20672666777 2019.
[34] Hc, M., Z. Wei, Z. Huang, et al. Bernnet: Learning arbitrary graph spectral filters via bemsstei approxima- tion. In 34th Advances in Neural Information Processing Systems. 2021.
[35] He, M., Z. Wei, J.RR Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. In 35th Advances in Neural Information Processing Systems. 2022.
[36] Gasteiger, S. Weißenberger, S. Günnemann. Diffusion improves graph learning. In 32nd Advances in Neural Information Processing Systems. 2019.
[37] Wang, X., M. Zhu, D. Bo, et al. Am-gen: Adaptive multi-channel graph convolutional networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, page 1243-1253. Association for Computing Machinery, 2020.
[38] Cavallo, A., C. Grohnfeldt, M. Russo, et al. 2-hop neighbor class similarity (2nes): A graph structural metric indicative of graph neural network performance. In 3rd Workshop on Graphs and More Complex Structures for Learning and Reasoning (GCLR) at AAAI 2023. 2022.
[39] Belkin, M., P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6)) 1396, 2003.
12

---

[40] Page, S. Brin, R. Motwani, et al. The pagerank citation ranking: Bringing order to the web. Tech. rep.. 1999.
[41] Liao, R., Z. Zhao, R. Urtasun, al. Lanezosnet: Multi-scale deep graph convolutional networks. In International Conference Learning Representations. 2019.
[42] Liu, H., N. Liao, S. Luo. Simga: A simple and effective heterophilous graph neural network with efficient global aggregation. arXiv e-prints, 2023.
[43] Zhu, H., P. Koniusz. Simple spectral graph convolution. In 9th International Conference on Learning Representations. 2021.
[44] Zhu, Z.. J. Peng, J. Li, et al. Spiking graph convolutional networks. In Proceedings of the 31 International Joint Conference Artificial Intelligence, pages 2434-2440. 2022.
[45] Ming, C. Wei, Z. Huang, et al. Simple and deep graph convolutional networks. In 37th International Conference on Machine Learning, vol. 119, pages 1703-1713. PMLR, 2020.
[46] Zhu, M., X. Wang, C. Shi, et al. Interpreting and unifying graph neural networks with optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226. ACM, 2021.
[47] Ma. Y., X. Liu, T. Zhao, et al. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pages 1202-1211, ACM, 2021.
[48] Berkhin, P. survey on pagerank computing. Internet Mathematics, 2(1):73-120) 2005.
[49] Golub, G. H., C. F. V. Loan. Power iterations. In Matrix Computations, chap. 8.2, pages 450 457. JHU Press, 2012.
[50] Wang, S., R. Yang, X. Xiao, al. Fora: Simple and effeetive approximate single-souree personalized pagerank. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Part F1296:505-514, 2017.
[51] Wang, K., S. Luo, D. Lin. River of return: Graph percolation embeddings for efficient knowledge graph reasoning. arXiv e-prints, 2023.
[52] Fang, A. Khan, S. Luo, al. Distributed graph embedding with information-orientee random walks. Proceedings of the VLDB Endowmen, 16(7):1643-1566 2023.
[53] Wu, H., Gan, Z. Wei, ct al. Unifying the global and local approaches: efficient power iteration with forward push. In Proceedings of the 2021 International Conference on Management of Data, vol. 1, pages 1996-2000 2006-200..20 2021.
[54] Mo, D., S. Luo. Agenda: Robust personalized pageranks in evolving graphs. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management. QLD, Australia, 2021.
[55] Oleg Platonov, Denis Kuznedelev, Michael Diskin, et al. A critical look at evaluation of gnns under heterophily: Are we really making progress? / International Conference on Learning Representations. 2023.
[56] Wang, X., M. Zhang. How powerful are spectral graph neural networks. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, S. Sabato, eds., Proceedings of the 39th International Conference on Machine Learning, vol. 162, pages 23341-23362. PMLR, 2022.
[57] Sen, P., G. Namata, M. Bilgic, et al. Collective classification in network data. Al Magazine, 29(3):93, 2008.
[58] Hu, W., M. Fey, M. Zimik, et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs. 33rd Advances in Neural Information Processing Systems, 2020.
[59] Ying, C., T. Cai, S. Luo, et al. Do transformers really perform bad for graph representation? In 34th Advances in Neural Information Processing Systems. 2021.
[60] Grover, A., J. Leskovee. Node2vee: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, page 855-864. ACMZ, 2016.
13


Reviews:
[{"review_id": "hYIo0w4Zil", "reviewer": "Reviewer_ZDfg", "summary": "The paper proposes a new graph neural network (GNN) model called LD2, which specifically targets learning on heterophilous graphs, where connected nodes have different labels. The authors argue that existing models for heterophilous graphs often require iterative full-graph computations, which can be computationally expensive and difficult to scale to larger graphs. In contrast, LD2 decouples graph propagation and generates expressive embeddings prior to training, resulting in a scalable and efficient model with optimal time complexity and a memory footprint that remains independent of the graph scale.\n", "questions": "1. It seems that the method has to precompute the embeddings for adajcencies, e.g. eigendecomposition in Section 3.2, is the model able to tackle the inductive settings?\n\n2. Can other methods for encoding structures act as adajcency embeddings? for example, the spatial encodings in Graphormer.\n\n3. In line 160, it says \"Particularly, the most informative aspects are often associated with 2-hop neighbors\", is this statement verified in some paper? The method design includes the 2-hop neighborhood. What about consider other hops of neighborhood? \n\n4. Can this method apply to heterogeneous graphs?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies the scalability issues of heterophilous GNN and propose a scalable model, LD2 which simplifies the learning process by decoupling graph propagation and generating expressive embeddings prior to training.\n\n2. Theoretical analysis demonstrates that LD2 achieves optimal time complexity in training, as well as a memory footprint that remains independent of the graph scale.\n\n3. Extensive experiments to showcase that the proposed model is capable of lightweight minibatch training on large-scale heterophilous graphs, with up to 15× speed improvement and efficient memory utilization, while maintaining comparable or better performance than the baselines.\n\n4. The paper is well-written and easy to follow.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Q1\n\nYes. Our proposed model LD2 is capable of handling inductive tasks. This can be implemented by conducting precomputation respectively on the training and inference graphs. After that, the feature transformation model can be easily trained on the precomputed embeddings of the training graph and then perform inductive inference based on the embeddings of the other graph.\n\nWe conduct additional experiments on the inductive datasets `protein-inductive` and `yelp-inductive` to evaluate the model capability. Results are shown in **Table II** in PDF. As a brief summary, LD2 achieves comparable accuracy with GCN-GS, while PPRGo fails to adapt such settings. Regarding efficiency, our model is 10-50x faster in training, which is in line with our complexity analysis as well as evaluation on minibatch homophilous baselines presented in **Table 12** in supplementary material.\n\n### Notes on *inductive datasets*\n\nTo the best of our knowledge, there is no existing inductive dataset specifically for heterophilous node classification. Hence we employ `protein-inductive` and `yelp-inductive` datasets, which are homophilous graphs. We follow the settings in [27] in Table II. The transductive versions of these two datasets are `protein` and `yelp`, which have already been evaluated in **Table 8-9** in supplementary material.\n\n### Notes on *inductive GNN models*\n\nTo the best of our knowledge, existing GNNs proposed for heterophilous graphs scarcely mention inductive capability or provide relevant implementations. Notably, some heterophilous models like LINKX contain structures determined by the input graph shape, preventing their application to inductive settings. In contrast, our model structure is independent of the graph size and is applicable to the task as described above. This is also the reason that Table II only includes comparisons with homophilous baselines GCN-GS [27] and PPRGo [29] that possess inductive implementations.\n\n## Q2\n\nWe conduct additional experiments on the performance of replacing the $A^2$ adjacency spectral embedding (ASE) with other types of structural embeddings in **Table IV** in PDF. Specifically, \"SPD\" denotes the shortest path distance used as spatial encodings in Graphormer [R1].\n\nThe results indicate that by using SPD, the model can only achieve suboptimal accuracy on `squirrel`, while exceeds time limit on `penn94` and `genius`. We explain this by the complexity of SPD. In the implementation of [R1], Floyd-Warshall algorithm is used, which has time complexity $O(n^3)$ and space complexity $O(n^2)$. According to Section 2 of our paper, this is not scalable to large graphs. In fact, in [R1] the approach is applied to graph regression on `PCQM4Mv2`, where the average graph size is only $n=14$ [R2]. Hence when applied to our datasets such as `penn94` and `genius`, the SPD calculation will be expensive.\n\nWe compare the advantages of our proposed ASE($A^2$) with other structural embeddings such as SPD from three aspects:\n\n* *Effectiveness*: As we analyzed in Section 3.2, ASE is able to capture structural information especially on the homophilous components of the 2-hop graph, while SPD is more specific to encode distance information of directly connected nodes, which is less suitable for heterophilous embedding.\n* *Memory efficiency*: ASE is a low-dimensional embedding of shape $n\\times F$, where the feature dimension $F$ is generally much smaller than the graph scale. This implies better scalability compared to SPD embedding which is a dense $n\\times n$ matrix.\n* *Time efficiency*: ASE also benefits from faster computation in our model as described in Section 3.4, which can be computed along with feature embeddings with a complexity linear to edge size $m$.\n\n[R1] Do Transformers Really Perform Bad for Graph Representation? NeurIPS 2021.\n\n[R2] OGB-LSC: A large-scale challenge for machine learning on graphs. 2021.\n\n## Q3\n\nYes, as stated in line 161, [13] proposes to exploit 2-hop information for heterophilous GNNs, and proves in its Theorem 2 that the 2-hop neighborhood is expected to be homophily-dominant even under heterophily. A recent paper [R3] also verifies that the 2-hop similarity is strongly relevant to GNN performance.\n\nTo empirically showcase the effectiveness of $A^2$, we also conduct additional experiments on the embeddings generated from other hops of neighborhood in **Table IV** in PDF. Specifically, we apply the same rank-$F$ approximation in Eq. (2) by replacing $A^2$ with $A$ and $A^3$, which are respectively denoted as ASE($A$) and ASE($A^3$).\nIt can be inferred that, on datasets where adjacency embedding $P_A$ is important such as `squirrel`, changing ASE to other hops significantly reduces the accuracy. On `penn94` and `genius`, the accuracy with 1- or 3-hop adjacency embedding is not better than solely learning on feature embeddings $P_X$ (whose performance is reported as pink lines in Figure 3 & 6 in supplementary material).\nIn addition, when the number of hops increases, the convergence of the decomposition in Algorithm 1 becomes slower, which leads to longer precomputation time. It is thence a theoretically and empirically reasonable choice to employ 2-hop neighborhood for adjacency embedding.\n\n[R3] 2-hop Neighbor Class Similarity (2NCS): A graph structural metric indicative of graph neural network performance. AAAI Workshop 2023.\n\n## Q4\n\nOur claimed contribution of this paper primarily centers on proposing a scalable GNN for heterophilous graphs. Therefore, the design for heterogeneous graphs is not the focus of this work. However, we do recognize that approaches exist for transferring GNN models on homogeneous graphs to accommodate heterogeneous information. For instance, [R4] proposes learning distinct weights for each individual relation type as a \"relational\" model. We believe this can be a potential direction for future exploration.\n\n[R4] Modeling relational data with graph convolutional networks. European Semantic Web Conference 2018."}, {"review_id": "1crYnbx55B", "reviewer": "Reviewer_K3oj", "summary": "This paper studies an important problem of graph learning on large-scale heterophily graphs.\nThe paper presents a novel approach LD2 model, decouples the embedding process from the convolutional process, allowing for more efficient and scalable learning.\nLD2 learns graphs under heterophily, which is particularly useful for large-scale graphs. \nExtensive experiments demonstrate the effectiveness of the proposed method compared to existing baselines.", "questions": " - Is it possible for the authors to make the code used in the experiments public? This would help ensure that the results are reproducible and would be a valuable resource for researchers interested in implementing the LD2 model.\n - Could the authors provide more detailed information on the underlying mechanisms of the LD2 model?\n- Could the LD2 model handle noisy or incomplete graph data? While the authors mention that the approach is robust to noise, it would be helpful to have a more detailed analysis of the model's performance under different levels of noise and incompleteness.\n\n", "limitations": "Limitations and potential improvements are discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses an important problem on large-scale heterophily graphs, which is especially important for large-scale datasets.\n- This paper propose a scalable graph learning method LD2 model, which decouples the embedding process from the convolutional process, and allows for more efficient and scalable learning.\n- The scalability problem is well defined, and the theoretical comparisons with previous works is clearly clarified. \n- Sufficient experiments show that LD2 is capable of lightweight minibatch training on large-scale heterophilous graphs, with up to 15× speed improvement and efficient memory utilization, while maintaining comparable or better performance than the baselines. \n- Experiments on several benchmark datasets demonstrate the effectiveness of the LD2 model compared to existing baselines, and the results show that the LD2 model outperforms existing methods in terms of both accuracy and scalability.", "weaknesses": "- The paper could benefit from a more detailed explanation of the LD2 model. While the authors provide some high-level descriptions of the model, it would be helpful to have a more in-depth explanation of the underlying mechanisms.\n- It is difficult to reproduce the results without access to the code used in the experiments. While the authors provide some details on the experimental setup, it would be helpful to have access to the code to ensure that the results are reproducible.\n\nI am willing to increase the score for this paper if my major concern about the reproducible problem is addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W2 & Q1\nYes. A preliminary version of the project code, example data, and reproducibility instructions has already been provided in **Section H** of the supplementary material. We have also sent the same link to the AC in a separate comment following the rebuttal policy.\n\n## W1 & Q2\nThe proposed LD2 model is a two-stage model as illustrated in Figure 1. In other words, its precomputation and feature transformation are decoupled as separated stages, as expressed in Eq. (1). We elaborate on the underlying mechanisms of the two stages respectively as following.\n\n### (1) Precomputation\n\nThe precomputation stage takes the input of graph adjacency matrix $A$ and node attribute matrix $X$, the output comprises four embedding matrices of shape $n\\times F$. The goal of precomputation is to retrieve useful information from graph structure and feature to form the embeddings, which are utilized in the subsequent feature transformation stage. The entire precomputation is described in Algorithm 1. Specifically, the computation involves propagations, i.e., multiplication by the sparse adjacency matrix $A$, along with subsequent operations according to different definitions, to acquire the four embeddings:\n\n* The adjacency embedding $P_A$ is computed by 2-hop power iteration, mainly multiplying $A$ twice to the initial embedding matrix in each iteration. After convergence, the embedding follows the expression $P_A = U |\\Lambda|^{1/2}$ as described in line 173.\n* The first feature embedding is expressed by $P_{X,H} = \\sum_{l=1}^{L} (I-A)^l X$ as in line 206. In this case, its precomputation is conducted by iteratively multiplying $(I-A)$ to the input matrix $X$ for $L$ times and summing up the results.\n* Similarly, the second feature embedding is $P_{X,L2} = \\sum_{l=1}^{L} A^{2l} X$ as in line 207. To acquire the embedding, we multiply $A$ to the input matrix $X$ for $2L$ times with summation.\n* The last embedding is exactly the input attribute matrix $P_{X,0} = X$.\n\n### (2) Feature transformation\n\nA neural network is applied to iteratively learn from the input embeddings. Firstly, an individual weight matrix is applied to each embedding matrix. Then the multiplication results are concatenated and fed into the remaining MLP layers. The model is trained by minimizing the loss associated with the classification task.\n\nWe also offer an interpretation from the spectral perspective, elucidating the expressiveness of decoupled propagation and our embedding designs from the viewpoint of graph signaling in **Section A** of the supplementary material.\n\n## Q3\n\nWe would like to address the question in two folds.\n\n### (1) Interpretation of the model robustness\n\nIn line 250 we claim that the model is robust to a certain level of noise introduced by propagation. The purpose of the statement is to support the utilization of approximate propagation, signifying that embeddings acquired by precomputation do not need to be precise, as they are further processed by the MLP model. Such property on robustness has been observed as an interpretation of GNN learning [41], wherein the learning objective is to recover a clean and smooth representation from the noisy input features. Models such as [29], [31], and [25] have already implemented approximate propagation within the context of homophilous GNN.\n\nIn our model, the precision of approximate propagation, which is the only source of computational noise, is controlled by the push threshold $\\delta_P$ as in Algorithm 1. As described in Section E.3 of the supplementary material, we set $\\delta_P=1\\times 10^{-5}$ for common experiments, which is relatively small compared to the scale of feature values standardized to Gaussian distribution $N(0,1)$.\n\n### (2) Evaluation on noisy data\n\nWe conduct additional experiments to evaluate the model performance under different levels of noise and incompleteness. The results are shown in **Table V** in the appended PDF file. We mainly consider three types of noises, which are analyzed respectively as following:\n\n* *Push threshold*: We vary the threshold $\\delta_P$ in Algorithm 1 to control the precision of propagation. A larger $\\delta_P$ implies less precise propagation ignoring small feature values, while $\\delta_P=10^{-5}$ is the original setting. It can be seen that by improving the precision, the final learning accuracy does not change significantly. It indicates that our setting of $\\delta_P=10^{-5}$ is sufficient for propagation and does not affect the learning performance.\n\n* *Edge removal*: We randomly remove a percentage of edges to generate an incomplete variant of the graph. The LD2 model is then applied to learn on the incomplete graph. The removal causes a negative impact on the accuracy. However, as the node attributes $X$ are kept unchanged under the noise, the model is still able to achieve a reasonable performance.\n\n* *Attribute noise*: We apply Gaussian noise with standard deviations proportional to the deviation of each feature dimension to the raw node attribute matrix $X$ before precomputation. This is more aggressive as the noise level is much larger than the scale of propagation precision.Consequently, the model suffers a more significant accuracy reduction. However, as the noise level increases, the model's performance converges towards the performance achieved by only learning the adjacency embedding $P_A$ (whose performance is reported as orange dashdotted lines in Figure 3 in the paper and Figure 6 in the supplementary material). This is because the adjacency information is unaffected under such kind of noise.\n\nOverall, we elaborate on the effectiveness of performing approximate propagation in LD2. The additional experiments also demonstrate the robustness of our model benefiting from learning both adjacency and feature information."}, {"review_id": "TrxMqo1inp", "reviewer": "Reviewer_aZqt", "summary": "This paper introduces a scalable decoupled model designed to address the challenges posed by large-scale heterophilous graph. \n\nThe model consists of two main components. In the first component, recognizing the effectiveness of $A^2$ in heterophilious graph, the model precomputes a matrix, denoted as $P_A$ in Equation (2), which serves as a representation of graph structure. This matrix is computed using a randomized eigendecomposition technique. In the second component, the authors leverage multiple hop-based coefficients of propagation to address the issue of long-range dependency. These coefficients are designed to capture information from nodes at different distances in the graph, allowing the model to effectively capture dependencies that span across multiple hops. Finally, the two components are combined, and the resulting representation is passed through an MLP to generate the final node representations. \n\nThe authors provide some theoretical support and conduct a complexity analysis to demonstrate the effectiveness and efficiency of the proposed model. The author also conducts extensive experiments to evaluate the performance of their model on heterophilious graphs with different scales. The model achieves outstanding performance compared to some popular baselines while minimizing the computational resources (GPU) required.", "questions": "1. What is the performance of the model on homophilous datasets? Is the performance comparable to some recent works?\n\n2. Will the model be implemented ordinarily, particularly when confronted with extremely large graphs such as Ogbn-Papers100M and real-world data with extremely high dimensions of node embedding?\n\n3. It is mentioned in the paper [1] that there are additional heterophilous datasets available. Therefore, conducting more comprehensive experiments on those datasets is necessary to strengthen the evaluation and analysis presented in this work.\n\n[1] Platonov O, Kuznedelev D, Diskin M, et al. A critical look at the evaluation of GNNs under heterophily: are we really making progress? ICLR, 2023.", "limitations": "The Effectiveness of randomized SVD when the propagation steps are limited is doubted.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors employ a technique to compress the graph structure $A^2$ into a low-rank format while preserving the principal components. This approach effectively reduces the computational cost associated with the training phase. \n2. The authors conduct various experiments to investigate the coefficients of propagation and successfully identify the optimal approach for handling heterophilous graphs.\n3. The theoretical time complexity of the model is excellent. The pre-computation phase is conducted once, and the training phase supports mini-batch processing. These properties guarantee the scalability of the model.\n4. The performance of the model surpasses the majority of the existing results, thereby confirming its effectiveness.", "weaknesses": "1. The contributions to address heterophily are limited as the involvement of the raw structure of a graph and multi-hop neighbors have already been proposed in LINKX and spectral GNNs.\n2. The method employed to reduce the dimensionality of the adjacency matrix, randomized SVD, is a commonly used approach. However, its performance heavily relies on the number of iterative rounds. The authors appear to merge the computational cost of SVD associated with the propagation step, which could potentially limit the effectiveness of the algorithm.\n3. The experiments conducted in this work exclude results from well-known homophilous datasets such as Cora, PubMed, and Ogbn-products. Since this model is specifically designed for heterophilous graphs, it should still maintain comparable results on homophilous datasets when compared to the mentioned baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1\nWe wish to highlight that our major contribution lies in proposing a GNN design that specifically targets the scalability issue under heterophily.\n\n* Our model achieves *improved time and memory complexity*. Compared to spectral GNNs, our design escapes the iterative and full-graph propagation. Compared to LINKX, our model removes the architectural dependence on graph size, thereby substantially enhancing scalability and minibatch capability.\n* We propose *novel and effective embeddings* with end-to-end precomputation. Different from spectral GNNs, our multi-hop calculation is in a one-time decoupled manner. Our adjacency embedding design specifically addresses the drawback of LINKX. As analyzed in line 192, it can effectively approximate the corresponding component in LINKX with significantly reduced computation cost.\n* Evaluations demonstrate LD2's *empirical performance on minibatching and scalability*. In comparison, the multi-hop representative MixHop encounters performance degradation brought by minibatching, while LINKX exhibits worse scalability such as RAM usage.\n\nA more detailed comparison with multi-hop GNNs and LINKX is offered in **Section B.2 & B.4** of supplementary material.\n\n## W2\nWe would like to address the concern of adjacency embedding calculation in two folds:\n\n### *Theoretical analysis* on convergence\n\nFor a general power iteration decomposing a matrix, its stopping criteria are usually both maximal iteration and error tolerance [R5]. In our Algorithm 1, they correspond to the maximal hop $L_P$ and the push threshold $\\delta_P$. Iterations required for convergence can be derived as in line 288. For a rough estimation, substituting our common setting $F=512$, $\\delta_P=10^{-5}$, and $\\lambda_{F+1}/\\lambda_{F}\\approx 10^{-1}$ can give an estimation of $O(10)$ iterations, which is of the same order with our propagation hop $L_P=20$.\n\nThe analysis can be supported by the spectrum distribution in **Figure 4** in supplementary material. A large number of datasets exhibit a rapid drop of eigenvalues for a certain rank $F$. When setting the embedding feature dimension close to or slightly larger than the proper rank, the computation is able to achieve favorable convergence of the leading components.\n\n### *Empirical effect* of propagation steps\n\nWe demonstrate empirical evidence on the effectiveness of approximate adjacency embedding by investigating test accuracy of solely learning on $P_A$. The performance is reported as orange dashdotted lines in **Figure 3 & 6**. Figure 3(b) is a representative example on `pokec`. It can be observed that for $L_P = 2$ and $4$ the accuracy is suboptimal, while for $L_P > 8$ the performance generally converges.\n\nIt is also noteworthy that during power iteration, leading components converge in fewer iterations. As the nature of neural networks tends to focus more on larger values in features, the leading components, representing low-frequency spectrum, can effectively embed structural information even when the entire matrix has not converged. More iterations are generally helpful in securing high-frequency information.\n\n[R5] Golub H., Loan V. Matrix Computations. pp 450-457. 2012.\n\n## W3 & Q1\nWe conduct comprehensive evaluation on 5 well-known homophilous datasets `protein`, `ogbn-arxiv`, `yelp`, `reddit`, and `ogbn-products` (named as `amazon`) in **Table 8, 9, 12, and 13** in supplementary material. We also conduct additional experiments on `cora` and `pubmed` in **Table I** in PDF. We compare the performance with 16 models. We refer the reviewer to the above tables for detailed results.\n\nWe conclude that LD2 is capable of attaining comparable efficacy and remarkable efficiency among homophilous datasets. Its minibatch performance generally surpasses both homophilous and non-homophilous competitors. Moreover, it demonstrates impressive scalability for learning time and memory, which is consistent with the main experiments. Notably, LD2 is the only model that does not exceed the memory limit on any datasets in full-batch settings.\n\n## Q2\nWe conduct additional experiments on `ogbn-papers100m`, which is the largest dataset available. Results are shown in **Table II** in PDF. It is worth mentioning that all 15 GNN-based baselines occur out of memory error on such a large graph. Although the dataset is homophilous, our LD2 model achieves reasonable accuracy with efficient time and memory usage.\n\nWith respect to embedding dimension, it can be inferred from **Table 1** that our model exhibits an $O(FF')$ complexity, where $F$ is raw node attribute dimension, and $F'$ is model hidden dimension. This is on par with other GNN models, that when the model architecture is fixed, this can be considered as a linear complexity with respect to $F$.\nOur experiments evaluate on datasets such as `penn94` with a large $F=4.8K$. Performance on these datasets with high embedding dimension satisfy our scalability analysis.\n\n## Q3\nWe conduct additional experiments on `roman-empire`, `minesweeper`, `amazon-ratings`, and `tolokers` proposed in [42]. Results are shown in **Table I** in PDF. These graphs are relatively small, comprising fewer than $30K$ nodes, compared to the large-scale ones in our main experiments. As mentioned in [42], these heterophilous datasets emphasize effectiveness rather than scalability, hence the main paper does not include them in our initial evaluation.\n\nWe observe that the efficiency and efficacy strengths of our LD2 model persist on these datasets. Specifically, the minibatch baselines undergo substantial performance degradation on `roman-empire` and `minesweeper` when compared to the full-batch results in [42]. We surmise that this is associated with the longer diameter and stronger non-local dependency of these two graphs. As we point out in Section 2, the exploitation of sampling strategy in these models results in information loss, which greatly hinders the performance on such heterophilous graphs."}, {"review_id": "qxTVsbxx0V", "reviewer": "Reviewer_4icY", "summary": "This paper aims to optimize the design of graph neural networks on large-scale heterophilous graphs. It proposes a new framework called LD2, which decouples the node feature embedding and topology embedding. By obtaining a low-dimensional adjacency embedding and long-distance feature embedding through pre-computing, it achieves a faster and better performance for the mini-batch training. ", "questions": "1. I do not quite understand the formula in line 270: $R^{(l+1)}(u) = R^{(l+1)}(u) + R^{(l)}(u)$, what does it mean?\n\n2. It looks like Line 4 of algorithm 1 contains a typo (shall be the union rather than an intersection).\n\n3. Why are the dataset statistics of snap-patents and wiki different from that in [1]?\n\n4. Why is the batch size of LD2 larger than LINKX in most datasets? And why is the performance of full-batch LINKX (Table 7) different from that in [1]? I am not sure if the authors reproduce the correct results of LINKX.\n\n[1] Lim, D., F. Hohne, X. Li, et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In 34th Advances in Neural Information Processing Systems. 2021", "limitations": "Yes, the authors carefully address them.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem studied by this paper is interesting, The model efficiency is not well-studied on the large-scale heterophilous graphs and this research is meaningful to the community.\n2. The paper is well-organized and clearly presented. The authors make a thorough time complexity analysis and give sound solutions. Each component of the model is explained with reasonable logic.\n3. The experimental results look promising, with a clear advantage in the test accuracy and computational cost. ", "weaknesses": "1. The comparison between LD2 and other models is not fair. The core component of LD2 is its precomputation stage. However, from its code, this part is implemented in C++ while other GNNs are implemented in Python.  The computation of $A^2$ and any operation involving it could be very expensive. Usually, $A^2$ could be $10$x or $100$x denser than $A$, and that is why most GNNs do not use it on large-scale graphs. Therefore, first, the time/space complexity for the precomputation of LD2 in Table 1 cannot reflect the actual computational cost (ignoring the difference between $A$ and $A^2$), and second, the time comparison between LD2 and other models is unfair due to the different programming languages.\n\n2. Although LD2 is claimed to be a scalable heterophilous GNN, its main contribution (precomputation) is closer to node embedding methods. LD2 combines and simplifies some existing techniques, which makes its contribution limited. I think the authors should also compare the embedding obtained from precomputation with some node embedding methods like node2vec. I expect there will be some tradeoff, but the discussion for this part is totally missing.\n\n3. The authors miss the baseline [1].\n\n[1] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Simplifying approach to node classification in graph neural networks. Journal of Computational Science, pp. 101695, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## W1\nThere are two concerns regarding comparison fairness. We would like to address them separately.\n\n### Time complexity of 2-hop propagation\n\nAs elaborated in line 275 & 287, we *do not explicitly compute the $A^2$ matrix* in propagation. Instead, we perform the $A$ multiplication twice to the embedding matrix to realize the 2-hop propagation. For each such sparse-dense matrix multiplication, the sparse adjacency matrix $A$ contains $m$ non-zero entries, and the dense matrix is of shape $n\\times F$. The time complexity for one 2-hop propagation is therefore $2mF$. When such propagation is performed $L_P$ times, the total complexity is bounded by $O(L_PmF)$ as we present in Table 1. The memory expense for storing variables is only $O(nF)$ for each channel.\n\n### Difference in programming languages\n\n* We would like to draw the reviewer's attention to the fact that the efficiency of our model *stems from improvements in complexity*. Specifically, by employing decoupling technique, we remove the iterative $O(IL_PmF)$ complexity from training, which is the primary contribution to scalable heterophilous GNN in this paper.\n* We argue that *experimental comparisons remain meaningful even when the programming languages differ*. For example, comparisons can be established between `pokec` and `wiki` of similar $n$, while `wiki` has 10x more edges $m$. **Table 3** displays that the training time of baselines models increases substantially on `wiki`: LINKX is 6x slower than on `pokec`, and GCNJK-GS is 3.5x slower, mainly due to the scale of $m$. In contrast, LD2 exhibits no significant change in training time and only a 1.5x slowdown in precomputation, which validates the enhanced efficiency. These comparisons are among the models themselves and hence independent of programming languages. However, the results still underscore our model's scalability.\n* In addition, most baseline implementations in experiments also exploit various acceleration techniques, such as CUDA matrix multiplication, high-performance libraries, and parallel computation. We believe that the comprehensive comparison — considering both theoretical analysis and experimental evaluation, as presented in our paper — is generally convincing.\n\n## W2\nWe would like to first clarify our contribution, then discuss the experiments on embedding methods.\n\n### Contribution of LD2 model\n\n* Different from plain *node embedding methods*, our precomputation process is particularly designed for GNN. Common node embedding algorithms are based on the sole graph structure. In comparison, we propose the Long-distance Feature Embeddings, which encode both graph topology and node attribute in accordance with the GNN propagation scheme.\n* Compared with *existing GNN techniques*, our embeddings specifically fit the decoupled architecture. We propose three non-trivial embeddings with an end-to-end precomputation. As the per-model comparison in **Section B** of supplementary material suggests, our decoupled embeddings are novel and different from existing approaches.\n* For the *GNN community*, we target the scalability issue of heterophilous GNNs, which is not well-studied in the literature. We introduce the decoupling technique and achieve improved time and memory complexity. LD2 is therefore contributive as a scalable GNN solution as a whole.\n\n### Experiments on node embedding\n\nWe conduct additional experiments by replacing the $A^2$ adjacency spectral embedding (ASE) with node2vec in **Table IV** in PDF.\nThe results indicate that the node2vec model can only achieve suboptimal accuracy on `squirrel` and `penn94`, while exceeds RAM limit on `genius`. The former performance can be explained by the local neighborhood representation of node2vec, which is less suitable for heterophily. The OOM error is associated with the $O(nd^2)$ space/time complexity of node2vec. We refer the reviewer to the response to reviewer ZDfg Q2 for a more detailed comparison.\n\n## W3\nWe conduct additional experiments on FSGNN [23] as **Table III** in PDF. The full-batch performance complements those in Table 7 & 11.\n[23] only evaluates small-scale graphs. On larger datasets in our experiment, the model exceeds the GPU memory limit due to the storage of all $L_P$ embeddings. Such $O(L_P nF)$ memory complexity proves to be less scalable.\n\n## Q1\nThe formula is extracted from line 6, Algorithm 1. Given that $LR=(I-A)R$, each node in propagation inherits the previous embedding to itself ($IR$), while updating its neighbors as $-AR$.\nIn the formula $R^{(l)}(u)$ denotes the embedding of $u$ before the current propagation, and $R^{(l+1)}(u)$ records the embeddings that has been propagated to $u$ from other nodes in the current iteration of propagation. When the propagation is applied to $u$, $R^{(l+1)}(u)$ is increased by the value of $R^{(l)}(u)$, which is the meaning of the formula.\n\n## Q2\nWe thank the reviewer for pointing out the typo. We will correct it in the revised version.\n\n## Q3\nWe deduce that the difference in node and edge size is caused by our data processing scheme, which removes the isolated nodes in the graph.\n\n## Q4\nWe directly utilize the code in [26] for reproducing LINKX. We reckon that the inconsistency may be caused by:\n* *Hyperparameter configuration*: As [26] does not provide the exact hyperparameters but only grid search scripts, configurations in our experiments are possibly different. Our exploration is reported in Table 5 in supplementary material.\n* *Batch size*: As described in Section C.4, we select batch size for each model to maximize GPU utilization, as we mainly focus on the scalability evaluation. LINKX is of relatively smaller batch size because of higher memory demands of model weights.\n* *Full-batch performance*: We inherit settings in Table 5 for full-batch evaluation to ensure the consistency of efficiency, which may not be the optimal settings for accuracy. Nonetheless, the comparison does not affect our main contribution of scalable minibatch GNN."}]

Author rebuttal:
We sincerely appreciate the valuable feedback and insightful comments from all our reviewers, and are delighted to see that our effort toward improving the scalability of heterophilous GNNs is acknowledged by the reviewers. We have exerted substantial effort to investigate and address all the issues raised. Below is a summary highlighting our major updates:

1. *New datasets*: We conduct additional experiments on *7 new datasets* in total. **Table I** in the appended PDF file displays the results on homophilous `cora` and `pubmed` as mentioned by reviewer aZqt Q1, as well as heterophilous `roman-empire`, `minesweeper`, `amazon-ratings`, and `tolokers` as suggested in Q3. These findings complement those in Table 1 and 2 in main paper and Table 6, 8, 10, 12 in the supplementary material.

2. *New settings*: We extend evaluations on inductive datasets `protein-inductive` and `yelp-inductive` as asked by reviewer ZDfg Q1. We also incorporate learning on the extremely large graph `ogbn-papers100m` in reviewer aZqt Q2. The results are shown in **Table II** in the appended PDF file.

3. *New baseline*: In **Table III** in the appended PDF file, we introduce FSGNN as required by reviewer 4icY W3. This supplements the full-batch evaluation in Tables 7 and 11 in the supplementary material.

4. *Performance of adjacency embedding schemes*: We explore alternative methods including node2vec (reviewer 4icY W2), spatial encoding (reviewer ZDfg Q2), and adjacency propagation in different hops (reviewer ZDfg Q3). The results on learning accuracy and computation efficiency are displayed in **Table IV** in the appended PDF file.

5. *Robustness against noise*: We investigate the model performance under noise and incompleteness as per reviewer K3oj's Q3. **Table V** in the appended PDF file evaluates different types and levels of noise including approximate propagation, edge removal, and attribute noise.

6. *Contribution and comparison*: In this paper, we propose the LD2 model that specifically targets the scalability issue under heterophily. We justify our novel contribution relative to other approaches and particularly address the comments from reviewer aZqt W1 and reviewer 4icY W2. We also feature the comparison of embedding designs in response to reviewer ZDfg Q2 and reviewer 4icY W2.

7. *Details in model design*: We provide additional details and explanations on the model design including the underlying mechanisms (reviewer K3oj W1 & Q2), convergence of adjacency embedding (reviewer aZqt W2), precomputation performance (reviewer 4icY W1), and implementation details (reviewer 4icY Q1-4).

\* Reference numbers are the same with those in the main paper by default.

Meta-review: The paper proposes a scalable model for large-scale heterophilous graphs, namely LD2,  which decouples graph propagation and generates expressive embeddings prior to training. All the reviewers agreed that this paper is well-written and easy to follow, and the idea of decoupling graph propagation and generating expressive embeddings prior to training is novel.  Although some reviewers point out some concerns about insufficient experiments and unclear technical details, the authors have done a very good job in responding to the concerns during the rebuttal phase. Overall, the paper is valuable for this community. Therefore, I recommend accepting the paper.
Decision: Accept (poster)