Accurate and Scalable Graph Neural Networks via Message Invariance
Authors: Zhihao Shi
Jie Wang
Zhiwei Zhuang
Xize Liang
Bin Li
Feng Wu
Venue: ICLR 2025 Poster (2025)
Keywords: Subgraph Sampling
Graph Neural Networks
Topological Compensation
Message Invariance
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose an accurate and fast subgraph sampling method, namely, topological compensation (TOP), which obtains the outputs of the whole message passing solely through MP-IB, without the costly MP-OB.

Abstract: Message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications. For a sampled mini-batch of target nodes, the message passing process is divided into two parts: message passing between nodes within the batch (MP-IB) and message passing from nodes outside the batch to those within it (MP-OB). However, MP-OB recursively relies on higher-order out-of-batch neighbors, leading to an exponentially growing computational cost with respect to the number of layers. Due to the neighbor explosion, the whole message passing stores most nodes and edges on the GPU such that many GNNs are infeasible to large-scale graphs. To address this challenge, we propose an accurate and fast mini-batch approach for large graph transductive learning, namely topological compensation (TOP), which obtains the outputs of the whole message passing solely through MP-IB, without the costly MP-OB. The major pillar of TOP is a novel concept of message invariance, which defines message-invariant transformations to convert costly MP-OB into fast MP-IB. This ensures that the modified MP-IB has the same output as the whole message passing. Experiments demonstrate that TOP is significantly faster than existing mini-batch methods by order of magnitude on vast graphs (millions of nodes and billions of edges) with limited accuracy degradation.

Published as a conference paper at ICLR 2025
ACCURATE AND SCALABLE GRAPH NEURAL NET- WORKS VIA MESSAGE INVARIANCE
Zhihao Shi Jie Wang"1, Zhiwei Zhuang ', Xize Liang ' Bin Li Feng Wu
MoE Key Laboratory of Brain- inspired Intelligent Perception and Cognition, University of Science and Technology of China
ABSTRACT
Message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications. For sampled mini-batch of target nodes, the message passing process is divided into two parts: message passing between nodes within the batch (MP1B) and message passing from nodes outside the batch to those within it (MPoB). However, MPов recursively relies on higher-order out-of-bate neighbors, leading to an exponentially growing computational cost with respect the number of layers. Due to the neighbor explosion, the whole message passing stores most nodes and edges on the GPU such that many GNNs are infeasible to large-scale graphs. To address this challenge, we propose an accurate and fast mini-batch approach for large graph transductive learning. namely topological compensation (TOP), which obtains the outputs of the whole message passing solely through MP without the costly MP The major pillar of TOP is a novel concept of message invariance, which defines message- invariiant transformations to convert costly MPоR into fast MP This ensures that the modified MP has the same output as the whole message passing. Experiments demonstrate that TOP is significantly faster than existing mini-bat batch methods by order of magmitude on vast graphs (millions of nodes and billions of edges) with limited accuracy degradation.
INTRODUCTION
Message passing-basse based graph neural networks (GNNs) have been successfully applied to many practical applications involving graph-structured data, such as social network prediction (Hamilton
ct al.
2017 Kipf & Welling 2017 Deng et al., 2019), chip design Geng et al. (2025b):
: Bai et al.
(2025
Wang et al. (2024b c). combinatorial optimization Geng et al. 2023a 2025a
Liu al.
2025
2023 2024
Wang et al. (0233 2024a); Ling et al. (2024), drug reaction (Do et al. 2019
Duvenaud et al.] 2015: Geng al.] 2023b). and recommendation systems (Ying et al. 2018 Fan
et al..9 The key idea of GNNs is to iteratively update the embeddings of each node hased on its local neighborhood. Thus, as these iterations progress, each node embedding encodes more and more
information from further reaches of the graph (Hamilton) 2020 Chap. 5).
However, training GNNs on a large-scale graph is challenging due to the well-known neighbor explosion problem. Specifically, the embedding of node at the 1-th GNN layer depends on the embeddings of its local neighborhood at the (1 1)-th GNN layer. Thus, around the target mini-batch nodes, these message passing iterations of L-layer GNN form tree structure by unfolding their L-hop neighborhoods (Hamilton) 2020 Chap. 5), whose size exponentially increases with the GNN depth L (see Figure ((a)). The exploded source neighborhoods may contain most nodes in the large-scale graph, leading to expensive computational costs (Shi et al. 2024).
To alleviate this problem, recent graph sampling techniques approximate the whole message passing with the small size of the source neighborhoods (Ma & Tang Chap. 7). For example, node-wise
(Hamilton et al. 2017:
Chen et al. 2018a| BBliin & Catalyurek] 2023) and layer-wise (Chen et al.]
2018b; Zou et al. 2019 Huang et al. (0118) sampling recursively sample a small set of local neighbors
over message passing layers. The expectation of the recursive sampling obtains the whole message passing and thus the recursive sampling is accurate and provably convergent (Chen et al. 2018a).
"Corresponding author; drewangx@ustc.edd

---

Published as a conference paper at ICLR 2025
Inpux 1
Input
MP
Output
Output
Original GNNs
(b) Subgraph Sampling
f
Input
x0
x0
Mini-batch selection
Output
x1
Message passing
Topological compensation
(c) TOP
Figure 1: Mini-batch processing of original GNNs, subgraph sampling, and TOP. Given a mini-batch, the computational costs of original GNNs exponentially increase with GNN depth (a). To address this challenge, many subgraph sampling methods preserve message passing between the in- batch nodes (MPis) and eliminate message passing from out-of-batch neighbors to the in-hatch nodes (MP0B) to reduce the computational costs (b). However, the final embeddings of subgraph sampling usually different from the result of the original GNNs. By noticing the message invariance h4 = h + 0 h2 + 1- ha, TOP converts MP 14 + Uy into MPI8 Vts + ity without approximation errors in the example (c).
Different from the recursive fashion, subgraph sampling (Chiang al. 2019 Zeng et al. 2020 Fey
et al. 202T Zeng el al., 2021) adopts cheap and simple one-shot sampling fashion, i.c., sampling the same subgraph induced by a mini-batch for different GNN layers. It preserves message passing between in-batch nodes (MP1s) and eliminates message passing from out-of-batch neighbors to in-batch nodes oM)) achieving a linear complexity with respect to the number of GNN layers.
Nonetheless, accuracy and efficiency are two important but conflicting factors for existing graph sampling techniques. Specifically, accurate recursive sampling maintains the whole message passing at the expense of efficiency, while fast one-shot sampling eliminates MPов at the expense of accuracy. This motivates us to develop an accurate and fast mini-batch method for GNNs to approximate the outputs of the whole message passing solely through MP with marginal errors.
In this paper, we first propose a novel concept of message invariance, which defines message-invariant transformations to convert MPo8 into MP18, ensuring that the modified MP has the same output as the whole message passing. Figure T shows a motivating example for message invariance, where converting MPоB 04 - i/3 to MP 03 - 12 (the red edge) does not affect the output of GNNs. Although the resulting subgraphs are different from the original graph, the in-batch embeddings and corresponding computation graphs are always the same. We conduct extensive experiments to show the approximation of message invariance is effective in various real-world datasets (see Section 5.2)
Inspired by the message-invariant transformations, we propose a fast subgraph sampling method, namely topological compensation (TOP), which is applicable to various real-world graphs. Specifi- cally, TOP estimates the message invariance using a linear transformation, which learns the linear independence between embeddings of the in- batch nodes and their out-of-batch neighbors. In Figure I. the out-of-batch embedding of n4 linear combination of the in-batch embeddings of (v1, V2, it) with coefficients (0, 0. 1). We estimate the coefficients using simple and efficient linear regression on sampled basic embeddings (e.g. the embeddings in GNNs with random initialization). We further show that TOP achieves the convergence rate of ())= to reach an e-approximate stationary point (see Theorem 5.1). which is significantly faster than (( -6) of existing subgraph sampling methods (Shi al.) (023). We conduct extensive experiments graphs with various sizes to demonstrate that TOP is significantly faster than existing mini-bated methods with limited accuracy degradation (see
Figures and
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
In this section, we discuss some works related to our proposed method.
Node-wise sampling. Node-wise sampling (Hamilton et al. 2017 Chen al. 201 Yu et al. 2022) aggregates messages from a subset of uniformly sampled neighborhoods at each GNN layer, which decreases the bases in the exponentially increasing dependencies. The idea is originally proposed in GraphSAGE (Hamilton et al., 2017). VR-GCN (Chen et al.) 2018a) further alleviates the bias and variance by historical embeddings, and then shows that its convergence rate to reach an e-approximate stationary point is N O( "), where N denotes the number of iterations in Theorem 2 in (Chen et al. 2018a). GraphFM-IB further alleviates the staleness of the historical embeddings based on the idea of feature momentum. Although the node-wise sampling methods achieve the convergence rate of O( their computational complexity at each step is still exponentially increasing due to the neighborhood explosion issue.
Layer-wise sampling. To avoid the exponentially growing computation of node-wise sampling, layer-wise sampling (Chen et al. 20186 Zou et al. 2019; Huang et al. 2018)) samples fixed number of nodes for each GNN layer and then uses importance sampling (IS) to reduce variance. However, the optimal distribution of IS depends on the up-to-date embeddings, which are expensive. To tackle this problem, FastGCN (Chen et al. 2018b) proposes to approximate the optimal distribution of IS by the normalized adjacency matrix. Adapt (Huang et al. 2018) proposes a learnable sampled distribution to further alleviate the variance. Nevertheless, nodes independently in each GNN layer, the sampled nodes from two consecutive layers may be connected (Zou al. 2019). Thus, LADIES (Zou et al., 2019) consider the dependency of sampled nodes between layers by one step forward. By combining the advantages of node-win wide-wise and layer-wise sampling approaches using Poisson sampling, LABOR (Balin & Catalyurek] 2023) significantly accelerates convergence under the same node sampling budget constraints.
the above-mentioned methods sample
Subgraph sampling. Subgraph sampling methods sample a mini-batch and then construct the subgraph based on the mini-batch (Ma & Tang [222]] Chap. 7). Thus, we can directly run GNNs on the subgraphs. One the major challenges is to efficiently encode neighborhood information of the subgraph. To tackle this problem, one line of subgraph sampling is to design subgraph samplers to alleviate the enter-connectivity between subgraphs. For example, CLUSTER-GCN (Chiang et al. 2019) propose subgraph samplers based on graph clustering methods (e.g., METIS (Karypis & Kumar 1998) and Graclus (Dhillon et al. 2007) and GRAPHSAINT propose edge, node, or random- walk based samplers. SHADOW (Zeng al. 2021) proposes to extract the L-hop neighbors of mini-batch and then select an important subset from the L-hop neighbors. IBMB (Gasteiger et al. 2022) proposes novel subgraph sampler where the subgraphs are induced by the mini-batches with high influence scores, such as personalized PageRank scores. Another line of subgraph sampling is to design efficient compensation for the messages from the neighborhood based existing subgraph samplers. For example, GAS (Fey et al.] (202T) proposes historical embeddings to compensate for messages in forward passes and LMC {Shi et al. (023) further proposes historical gradients
to compensate for messages in backward passes. GraphFM-OB (Yu et al. 2022) alleviates the staleness of the historical embeddings based on the idea of feature momentum. Besides the traditional
optimization algorithm, SubMix (Abu-El-Haija et al., 2023) proposes a novel saaming-to-opiiing method for subgraph sampling, which parameterizes subgraph sampling as a convex combination of several heuristics and then learns to accelerate the training of subgraph sampling.
PRELIMINARIES
We first introduce notations in Section 3.1
Then, we introduce graph neural networks and the
neighbor explosion issue in Section 3.2
3.1 NOTATIONS
A graph g = (V, 8) is defined by a set of nodes V = {1, (1.2....,.)) and a set of edges & among these nodes. Let (i.j) E denote an edge going from node E V to node j E V. Let (B, Ba) denote the set of edges jii e Bi,j E B,, (i.j) e E) from B, to B2. Let NG = (i E ()( e E} denote the neighborhood of node i. Let Wu (UiesWG) U denote the neighborhoods of mini-batch 8 with
3

---

Published as a conference paper at ICLR 2025
itself. Let -Vg Wus B denote the out-of-batch neighbors of the mini-batch B. We recursively define the set of k--opp neighborhoods as N3 = =N with N = Na. The adjacency matrix is A ==*=
with A, = if (i and Au 0 otherwise. Given sets S (ip (ip))=1, S2 (14)) the submatrix S2 satisfies szlp. ip.Jg- For positive integer T., [T.] denotes (1....,A}.
Let the boldface character x; E Rd denote the feature node with dimension dN. Let h, E Re be the d-dimensional embedding of the node i. Let X = (X1, xx,.,,,.) e RTxd= and H (ha, bu,..., hn,) E [exx We also denote the node features and embeddings of a mini-batch E kl and Hs E R respectively.
B (ix)k= by XE = (
xi)s)) x11 (............
3.2 GRAPH CONVOLUTIONAL NETWORKS
For simplicity of the derivation, we present our algorithm with graph convolutional networks (GCNs) (Kipf & Welling 2017). However, algorithm is also applicable to arbitrary message passing- based GNNs (see Appendix
A graph convolution layer is defined
( ((++1) (H()), Á) = oZ (1+ (1+1) (()) = or oAH W() EI+1)E
(1)
where (D- (A- matrix (D... = E. A..) The initial node feature is H X, is activation function, and W())
is the normalized adjacency matrix and D is the in-degree
L-1 trainable weight matrix. For simplicity, denote the GNN parameters (W") Jizo by W. Thus, GCNs take node features and the normalized adjacency matrix (X, A) input
(L) GCN(G, A),
where GCN = f(l) f( f()).
The neighbor explosion issue is mainly due to feature propagation Z(+1) ( Specifically, the mini-batch embeddings at the +1+ 1)-th layer
H Ll (1-1) B
NB [Z) (wO) a (AB.NS w()
recursively depend on H Ng at the 1-th layer. Thus, the dependencies of nodes (i.e., H.[) depends on ( are exponentially increasing with respect to the number of layers L due to ((W))) O B deg mmax) with the maximum degree degmax-
MESSAGE INVARIANCE
In this section, elaborate message invariance in detail. We first present the definition of message invariance in Section 4.1 We then provide a case study for message invariance in Section 4.2
4.1 MESSAGE INVARIANCE
We first separate the mini-batch feature propagation in Equation 2 into two parts, i.c.,
Z (1+1)
A + AB.NE
H
MP
MPоB
where MP and MPOв denote message passing between the in-batch nodes and message passing from their out-of-batch neighbors to the in-batch nodes respectively.
To avoid the recursive dependencies induced by MPOB, we first introduce a novel concept (global) message invariance, which bridges the gap between costly MP and fast MP
Definition 4.1 (Message invariance). We say that a transformation RB + RWglid message-
invariant if it satisfies
H NS
(H
for any GNN parameters W.
wg- |A
4

---

Published as a conference paper at ICLR 2025
Given the message invariance, the composition of the original MP operator Äs,Ng Rl Rloxxd and the transformation g : R - RlAllxd leads to a new MPB operator (As.vgg)
Rloid xd + Blxd, Thus, the mini-batch feature propagation becomes
Z ((+1)
A A
(5)
MP
MP
which independent of the neighborhood embeddings H Therefore, the message-invariant .gg. transformation, y avoids the recursive dependencies and expensive costs of out-of-batch neighbors.
4.2 CASE STUDY FOR MESSAGE INVARIANCE
Due to the arbitrariness of graph structures and the nonlinearity of GNNs, the formula of the message- invariant transformation g is usually unknown. Here we provide a case study for a specific form of g by simplifying the graph structures the GNN architectures. The case study will motivate estimate the message-invariant transformation in Section 5.1
4.2.1 MESSAGE INVARIANCE ON GRAPH WITH SYMMETRY
The first example is shown in Figure where the node features are finite and the GNN architectures are arbitrary. Due to the permutation equivariance of GNNs, the nodes in the graph are categorized into Si {ui, 02, Us, 06} and 82 {us, v4 where the nodes in the same set are isomorphic to each other. The embeddings of isomorphic nodes are always the same, regardless of the GNN architectures. Therefore, the message-invariant transformation is
h (1) (h !1) h2 hn 0 h h + 1
Notably, the selection mnini-batcher does require considering the symmetry of the graph in Figure If the mini-batch B consists of two nodes 22 and vs from S; and S2 respectively, then finding is still easy by h; 1 h + 0 h and h = 0- h + 1 h (?) In the example, the condition for the existence of the message-invariant transformation is that the mini-batch B contains at least one node from each of S, and Sz.
The example discusses small graph with six nodes, while many real-world graphs contain millions of nodes. From a probabilistic perspective, the sets S₁ and S2 represent two peaks of the data distribution. Then, the condition becomes that the mini-bater features and their neighborhood structures). These frequent node inputs are also sampled with a high probability under large enough batch size. Thus, the message-invarisnn transformation is easy to find in large-scale graphs. We provide the detailed formulation and theory in Appendix F
contains the most frequent node inputs (the node
4.2.2 MESSAGE INVARIANCE FOR LINEAR GNNS
We use linear GNNs (Xu et al. 2021 Wang & Zhang 2022) as the second example, which simplifies the GNN architectures without restricting the graph structures. Linear GNNs use an identity mapping the activation function. For linear GNNs H A' (') (1) the linear dependence
between embeddings ( is equal to the linear dependence between the corresponding parameter-free features A Specifically, if the 1-hop features x(6) (Ä XX)x is full-column-ran matrix, then Rx Then, the linear dependence between there exists a coefficient matrix R such that X embeddings is
X !1) O ... W(- RX (0)
W (( RH
Thus, the invsaintnnvariaat transformation g in Equation g1 is linear transformation for the coefficient matrix R.
For non-linear GNNs, the relation between embeddings of the in-batch nodes and their out-of out-of-batch neighbors may be non-linear. Nonetheless. on the real-world datasets, the linear message-invariamt invariant transformation has achieved marginal approximation errors in practice as shown in Section 5.2
5

---

Published as a conference paper at ICLR 2025
5 TOPOLOGICAL COMPENSATION
In this section, we present the details of the proposed topological compensation framework (TOP). First, introduce the formulation of TOP inspired by the case study of message invariance in [ection[5.1] Then, based on the linear estimation of TOP, we conduct experiments to demonstrate that the message invariance significantly reduces the discrepancy between MP and the whole message passing in Section 3.2 Finally, we analyze the convergence of TOP in Section 5.3
5.1 FORMULATION OF TOPOLOGICAL COMPENSATION
Inspired by the linear message-invarrant transformation the case study Section 4.2 we propose to model message invariance H by H & RH where the coefficient matrix
Formulation.
E |IN are the weights of linear combinations of the in-batch embeddings of H Combining the approximation and the mini-batch feature propagation (3) leads to
Z zZt1 A AB.Ng RH
(As,8 + AA H
(6)
MPIR
where we call A As.gg R the topological compensation (TOP), The topological compensation
implements the message invariance by adding weighted edges to the induced subgraph ÅB.8. Then, TOP directly runs a GCN on the modified subgraph as follows
(T) GCN(X AB.S s + 0AB,8). B
The formulation of TOP makes it easy to incorporate the existing subgraph sampling methods.
Estimation of topological compensation. To reduce the discrepancy between the modified MP in Equation (6) and the whole message passing 3 we estimate R. by
min
RHg Huglle:
R
where H denotes the basic embeddings and || || is the Frobenius norm. The basic embeddings reflect the similarity between nodes.
Selection of basic embeddings. Before the training, we select the basic embeddings of GNN at random initialization by H(M)(vand) (H.)) (1.rand) ..... (F.nd)))) E (x +114 where W(rand) are the randomly initialized parameters and ((rrand) are the corresponding embeddings the j-th layer. The basic embeddings are the concatenation of all embeddings at different layers.
An appealing feature of H(W(rand)) ) is that they can identify the 1-WL indistinguishable node pairs by Theorem E.3 in Appendix The property ensures that the learned is message-invariant graphs with symmetry or large- scale graphs like the first motivating example in Section 4.2.1
The linear message-inee message-invariant invariant transformation with the basic embeddings ((W((radd) is very accurate on weal-world datasets as shown in Section [.2] Thus, we estimate TOP in the pre-processing phase and then reuse it during the training phase for efficiency in our experiments. When TOP based on H(W((and)) suffers from high errors, a solution is to update using the up-to-date embeddings H(W())) the t-th training step.
5.2 MEASURING MESSAGE INVARIANCE IN REAL-WORLD DATASETS.
In this section, we conduct experiments to demonstrate that the message invariance significantly reduces the discrepancy between MP and the whole message passing many real-world datasets. To ensure the robustness and generalizability of TOP in practice,
provide more results in Tables 7 and 8 including more experiments on heterophilous graphs and experiments under various subgraph samplers. The whole experiments are conducted on five GNN models (GCN, GAT, SAGE, GCNII, and PNA) and eight datasets (Ogbn-arxiv, Reddit, Yelp, Ogon-products, amazon-ratings, minesweeper, questions, and questions).
Measuring message invariance in real-world datasets. We first train GNNs by the full-batch gradient descent for each dataset. Then, we measure the discrepancy between MP and the whole

---

Published as a conference paper at ICLR 2025
Relative Errort 360
CLUSTER 23
Relative Errost 56)
Relative Eroort
CAS
20
IOP
20
40
Subgraph ratio 188/15
Subgraph ratio |AM/ (96)
Subgraph ratio |dl/ (96
(a) Oghn-arxiv GCN
(b) Ogbn-arxiv GAT
(c) Ogbn-products & SAGE
72
96
Test Accuracy
Test Accuracy
AcCuracy13))
64.6
69
64.4
68
64.2
67
Tul-belchh CLUSTER
Tul-balich
batch
QUUSTER
64.0
GA5
638
Subgraph ratio IAWDi (9))
Subgraph ratio (8/[1]
Subgraph ratio 18/1
(d) Ogbn-arxiv SAGE
(e) Reddit & GCNII
(1) Yelp & GCNII
Figure 2: Measuring the message invariance in real-world datasets. The output of TOP is very close to the whole message passing (denoted by Full-batch). Please refer to Table 3 in Appendix C. for more results.
message passing (denoted by Full-batch) by relative approximation errors and accuracy degradation. The relative approximation errors and accuracy degradation are defined by
H
(.))) B.
H
2 B;
11:))
b
1
and
ace H B.
(L,+)
YB.)) acc(H Ys.),
HL.
where we run the whole message passing (i.e., Full-batch) to obtain H e and Y is the matrix consist- ing the node labels. We partition the graph into 200 clusters and then sample in (20, 40, 60, 80, 100) clusters to construct subgraphs. If we decrease the batch size b, then the ratio of messages in MPов increases and thus MPо becomes important.
Our baselines include two subgraph sampling methods using MP (i.e., CLUSTER (Chiang et al. 2019) and GAS (Fey al.) (202T). We introduce these baselines in Appendix A We report the test accuracy vs. subgraph ratio in Figure The relative approximation errors of TOP are less than 5% and the test accuracy of TOP very close to Full-batch under different batch sizes.
5.3 CONVERGENCE OF TOP
Based on message invariance (4) we develop the convergence analysis TOP this section. The assumption of Theorem 5.1 is widely used in convergence analysis (Shi et al. 2023 Chen et al. 2018a Sa
Yu et al. 2022). All proofs are provided in Appendix D
Theorem 5.1. Let L(W)= = Evey ((((4) (B)/BB) and dw = Vw EXER E(h( (L.TOP) yb/BBBB be the loss of the full ball-batch method and the gradient of TOP respectively, where é is the loss function and y is the label of node i. Assume that (1) the optimal value E inf L(W) is finite (2) at the k-th iteration, a batch of nodes V is uniformly sampled from V function Ww C. is --Lipschitz with y (4) norms CW and |dwll2 are bounded by G 1. With the learning rate ( and the training step O(e-A), TOP then finds an e-stationary solution such that (()) [|]]] e after running for N iterations, where R is uniformly selected from [N].
The convergence rate N Aa is the same as the standard SGD Nesterov 2013 Fang al. 2018). Notably, the convergence rate of TOP is faster than that of LMC (Shi et al. 2023) (i.c.,
N = (( -)),, as TOP avoids the staleness issue of the historical embeddings and gradients of LMC.
7

---

Published as a conference paper at ICLR 2025
Table I: Statistics of the datasets in our experiments. "#" denotes the number and "Avg. degree" denotes the average degree. The task is node classification, which a standard task to evaluate the scalability on the large-scale graph (Chiang et al. 2019: Zeng et al. 2020 Fey et al. 2021
Dataset
#Classes
Total #Nodes
Total #Edges
Avg. degree
Train/Val/Tess
Reddit
41
232,965
11,606.919
49.8
0.660/0.1000 240
Yelp
50
716,847
6,997,410
9.8
0.750/0. 100
Oghn-arxiv
40
169,343
1,157,799
6.9
0.537/0. 1.537/0.176/0.25 76/0.288
Ogbn-products
47
2,449.029
61,859,076
25.3
1110/00.20/0..0
Oghn-papers 100M 100M
172
111,059,956
1,615,685,872
14.6
0.780/0.080000 140
6 EXPERIMENTS
We first compare the convergence and efficiency of TOP with the state-of-the-an subgraph sampling methh are the most related baselines-in Section Then, we compare the convergence and efficiency of TOP with the state-of-the-an node/layer-wise sampling methods in Section 6.2
More experiments are provided in Appendix C
6.1 COMPARISON WITH SURGRAPH SAMPLING
Datasets. We evaluate TOP on five datasets with various sizes (i.e., Reddit (Hamilton et al. 2017). Yelp (Zeg et al. 2020). Ogbn-arxiv, Ogbn-produse and Ogbn-papers (Hu ct al. 2020)) These datasets contain at least 100 thousand nodes and one million edges. Notably, Ogbn-paperr is very large, containing 100 million nodes and 1.6 billion edges. They have been widely used in
previous works (Fey et al. 2021 Zeng et al. 2020 Hamilton et al. 2017 Chiang et al. [219 Chen
et 20188 b). Table I summarizes the statistics of the datasets. We also conduct experiments
heterophilous graphs in Appendix C.7
Subgraph samplers. On the small and medium datasets (i.e., Ogbn-arxiv, Reddit, and Yelp), follow CLUSTER (Chiang et al. 2019) and GAS (Fey et al., (02T) to sample subgraphs based on METIS (see Appendix[A.I], Specifically, we first use METIS partition the original graph into many clusters and then sample a cluster of nodes to generate a subgraph. On the large datasets (i.e., brbbn-products and Ogbn-papers), as the METIS algorithm is too time-consuming (Zeng et al.. 2020), we uniformly sample nodes to construct subgraphs. More experiments under various subgraph samplers are provided in Appendix C.8
Baselines and implementation details. Our baselines include subgraph sampling (CLUSTER (Chiang et al., 2019p, SAINT (Zeng et al., 2020). and GAS (Fey et al. (02T)). We also compare TOP with IBMB (Gasteiger et al., (022) in Appendix
recent subgraph sampling method focused on the design of subgraph samplers, which is orthogonal to TOP (see Section 2). We implement TOP,
CLUSTER, SAINT, and GAS based on the codes and toolkits of GAS (Fey et al. (02T) to ensure
fair comparison. We introduce these baselines in Appendix A We evaluate CLUSTER, GAS, SAINT,
and TOP based on the same GNN backbone, including the widely used GCN (Kipf & Welling 2017)
and GCNII (Chen et al. 2020). We implement GCN and GCNII following (Fey et al. 202 1) and
(Hamilton et al. (017)) .. Due space limitation, we present the results with more GNN backbones
(c.g. SAGE (Hamilton et al. 2017), and GAT (Veličković et al. (018)) in Appendix C.3
We run all
experiments in this section on a single GeForce RTX 2080 Ti (11 GB), and Intel Xeon CPU E5-2640
v4. For other implementation details, please refer to Appendix B
Figure shows the convergence curves (test accuracy vs. runtime (s)) of TOP, CLUSTER, GAS, SAINT, and Full-batch (i.e. full-batch gradient descent with the whole message passing). We provide the convergence curves (test accuracy vs. epochs) in Appendix C We use sliding window to smooth the curves in Figure 3 as the test accuracy is unstable. We ran each experiment five times. The solid curves correspond the mean, and the shaded regions correspond to values within plus or minus one standard deviation of the mean. The convergence curves consider the runtime of pre-processing.
Results on small datasets. On the small datasets (i.c., Ogbn-arxiv and Reddit), the subgraph ratio |B| /IV is up to 50%, where [B] and | denote the sizes of subgraphs and the whole graph respectively. The large ratio shows that the subgraph contains much information about the whole graph. According to Figure 3(a) TOP is significantly faster than Full-batch CLUSTER. GAS, and SAINT without sacrificing accuracy. Further, TOP stably resembles the full batch performance on the Ogbn-arxiv and Reddit datasets, while CLUSTER, GAS, and SAINT unstable. The standard
8

---

Published as a conference paper at ICLR 2025
ogbn-arxiv
50%
Reddit & 50%
ogon-products &
4%
TOP
TOa
0.90
TOP Dremces and redist
Test/Acc
0.72
OKS
Test/Acc
0.97
5AS
Test/Ace
0.85
0.80
0.66
CLUSTOS
0.95
0.75
0.68
0.65
0.66
20
60
300
400
250
500
750
1000
1250
Runtime (s)
Runtime (s)
Runtime (s)
Reddlt & I TM
50%
Yelp TT 12.5%
ogbn-papers
1%
0.97
0.65
0.75
70+
TOP
velld
0.64
0.70
CLUNDWS anstien realn)
Test/Acc
0.96
(Bst/Acc
0.63
Test/Ace
0.65
0.62
0.00
0.61
0.94
0.60
0.55
0.59
Runtime
Runtime
Runtime (s)
(a) GCN on small datasets
(b) GCNI on medium datasets
(c) GCNII on large datasets
Figure 3: Convergence curves (test accuracy vs. runtime (s)) of subgraph sampling. We use the
default [B] and [V] which denote the sizes of subgraphs and the whole graph
in GAS Fey et al. 2021).
Full-aa GAS
Relative Runtime
Relative Memory
0.5
0.5
ReddR GCN
Reddit
Yelp GCNII
ogbn-products GCNII
Reddi:
Reddit
Yelp GCNII
oghn- products
GCNI
GCN
GENI
GCNI
(a) Relative runtime per epoch
(b) Relative memory consumption
Figure 4: Relative runtime per epoch and relative memory consumption. Please refer to Table in Appendix C.4 for more results.
deviation of CLUSTER, GAS, and SAINT is large such that the mean test accuracy is lower than the full-batch performance, as they are difficult to encode all available neighborhood information of the subgraph. Specifically, CLUSTER and SAINT do not take MPоB into consideration and GAS uses stale historical embeddings to approximate MPов-
Results on medium datasets. On the medium datasets (i.e., Reddit, and Yelp), the subgraph ratio |B||||| decreases from 50% to 12.5% due to GPU memory limitations. Thus, Full-batch runs out of GPU memory the Yelp dataset. Compared with GCN, the nonlinearity of GCNII becomes strong due to the large model capacity of GCNIL. Under the strong nonlinearity, TOP is still significantly faster than CLUSTER, GAS, and SAINT on the Yelp dataset with low subgraph ratio [B /IV] according to Figure 3(b) Moreover, TOP is significantly faster than GAS and Full-batch on the Reddit dataset. Although the mean convergence curses of TOP and CLUSTER similar on the Reddit dataset, the low standard deviation demonstrates that TOP is more stable than CLUSTER.
and Ogbn-papers: the subgraph ratio |B||||| is very low due to GPU memory limitations. By noticing that the large number of valid and test nodes in the large datasets useless for TOP, we remove the valid and test nodes from sampled subgraphs. For an ablation study, we report CLUSTER without valid and test nodes in the sampled subgraphs. We do not remove the valid and test nodes for GAS, as GAS requires updating the historical embeddings a large number of historical embeddings, GAS runs out of CPU memory on the Ogbn-paper dataset. According to Figure B(c) TOP is significantly faster than CLUSTER and GAS by several orders of magnitude. Moreover, the valid and test nodes in subgraphs are important for CLUSTER, as these valid and test nodes likely to be the neighbors of the training nodes. The valid and test nodes in
Results on large datasets. On the large datasets (i.c..
the valid and test nodes alleviate the staleness issue. Due to

---

Published as a conference paper at ICLR 2025
0.4
egbn-products
0.9
Reddit
og mabb--nco
sabon
0.90
0:00
0.00
8004
0.58
Runtime
50
100
123
338
Runtime
43
60
350
120
Runtime
5- 73 100 12. 153
(a) Memory.
(b) Runtime Products.
(c) Runtime on Reddit.
(d) Runtime on Arxiv.
Figure 5: Memory consumption and convergence curves of TOP and node/layer-wist sampling.
subgraphs increase the ratio of messages in MI for CLUSTER. TOP does not depend on the valid and test nodes due to its effective topological compensation.
Memory and runtime. We report the GPU memory consumption and the runtime per epoch in Figure 3 TOP is significantly faster and more memory-efficien than GAS on all datasets, as TOP does not require pulling and pushing historical embeddings frequently. Especially, the speedup of TOP against GAS is up to 11x on the Ogbn-product dataset, which is one order of magnitude. We analyze the computational complexity of TOP Appendix and give the detailed costs of pre-processing and training in Appendix C.S
6.2 COMPARISON WITH NODE/LAYER-WE SAMPLING
Baselines and implementation details We compare TOP with node-wise and layer-wise sampling methods including neighbor sampling (NS) (Hamilton et al. 2017) and LABOR (Balin & Catalyurek 2023) in Figure 5 where LABOR combines the advantages of node-wise and layer-wise sampling to accelerate convergence. Unlike subgraph sampling, node/layer-wise sampling mainly focuses on the certain SAGE model (Hamilton et al. 2017). We run NS and LABOR by the official implementation of LABOR (Balin & Catalyurek 2023). The reported runtime includes the runtime of pre- pre-processing. We run experiments in this section on single A800 card.
Hyperparameters. For TOP, we uniformly sample nodes to construct subgraphs. To ensure fair comparison, TOP follows the GNN architectures, data splits, training pipeline, learning rate, and hyperparameters of LABOR (Balin & Catalyurek 2023). We adjust the batch size of TOP such that the memory consumption of TOP is similar to LABOR.
Memory. We first evaluate the GPU memory consumption in terms of the number of GNN layers in Figure 5(a) We increase the number of GNN layers from two to seven. The GPU memory of NS and LABOR increases exponentially with the number of GNN layers, and thus they are difficult to apply to deep GNNs (e.g. GCNII with six layers in Figure 3). The GPU memory of both CLUSTER (Chiang et al. 2019) and TOP increases linearly with the number of GNN layers, corresponding with the computational complexity in Table 2 The GPU memory of CLUSTER is slightly larger than TOP, as CLUSTER uses the layer-wise inference (like GAS, see Appendix AA3)) in the evaluation phase while TOP only uses the mini-batch information (see Equation (6))
Convergence curves. We further report the convergence curves of TOP, NS, and LABOR in Figures 5(b) ((C) and 5(d) We have included the pre-processing time of TOP in the figures. Although NS and LABOR do not require pre-pre pre-processing TOP finally outperforms NS and LABOR due to its powerful convergence. The speedup of TOP against NS and LABOR more than 2x on all datasets.
7 CONCLUSION
In this paper, we propose an accurate and fast subgraph sampling method, namely topological compensation (TOP), based on a novel concept of message invariance. Message invariance defines message-invariant transformations that convert expensive message passing acted on out-of-batch neighbors (MPon) into efficient message passing acted on in-batch nodes (MP1)). Based on the message invariance, the proposed TOP uses efficient MP with limited performance degradation. Experiments demonstrate that TOP significantly faster than existing mini-batch methods by order of magnitude on vast graphs (millions of nodes and billions of edges) with limited performance degradation. While our experiments focus on message-invare and simple GNNs, non-linear message-invariann transformation needs to be empirically evaluated for more GNNs with more complex aggregation. In the future, we plan to generalize our ideas to more GNNs or graph transformers with global communication.
transformation for some common
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we provide key information from the main text and Appendix as follows.
T and We also provide the detailed implementation of TOP in Appendix B See Appendix B.3 for the hyperparameters TOP.
Algorithm. We provide the pseudocode of TOP in Algorithms
2. Theoretical Proofs. We provide all proofs in Appendix D
3. Source Code. The code of TOP is available on GitHub at httpp::/ggthuu..... MTRALab-USTC/IOO
4. Experimental Details. We provide the detailed experimental settings in Section and Appendix B
ACKNOWLEDGMENTS
The authors would like to thank all the anonymous reviewers for their valuable suggestions. This work supported by the National Key R&D Program of China under contract 20222D01 and the National Nature Science Foundations of China grants U23A20388 and 62021001.
REFERENCES
Sami Abu- Eae--E-HHHe El-Haija, Joshua V. Dillon, Bahare Fatemi, Kyriakos Axiotis, Neslihan Bulut, Johannes Gasteiger, Bryan Perozzi, and Mohammadhosscin Bateni. Submix: Learning mix graph sampling heuristics. In Robin J. Evans and Ilya Shpitser (eds.), Proceedings of the Thirty-Ninth Conference on Uncertainty Artificial Intelligence, volume 216 Proceedings of Machine Learning Research, pp. 1-10. PMLR, 31 Jul-04 Aug 2023. URL http::: wttppa/w......pp.....eeeeeee prwss/v21s1 abu Mou-el-haal Ja html
mlr.
Yingi Bai, Jie Wang, Lei Chen, Zhihai Wang. Yufci Kuang, Mingxuan Yuan, Jianye HAO, and Feng Wu. graph enhanced symbolic discovery framework for efficient eircuit synthesis. In The Thirteenth International Conference on Learning Representations, 2025. URL https
7/openreview. / Ftte//ooommmm--GGnNeeeCC
Muhammed Fatih Balin and Umit Catalyurek. Layer-neighbor sampling defusing neighborhood explosion in GNNs. In Thirth-seventh Conference on Neural Information Processing Systems, 2023.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp- 942-950. PMLR, 10-15 Jul 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations, 2018b. URL https::/
net/ www.mooiddooooooo F
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research. pp. 1725-1735. PMLR, 13-18 Jul 2020. URL chen20v. htmll
mlr press/1199
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp- 257-266, 2019.
Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Learning dynamic context graphs for predicting social events. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1007-1016, 2019.

---

Published as a conference paper at ICLR 2025
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE Trans. Pattern Anal. Mach. Intell., 29(1 nov 2007. ISSN 0162-8828. doi: 10.1 10.110//PAMM.2007.1111 2007.111
ottp://:///.i.../1........ TPAMI
Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis (eds.), Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 750-760. ACM, 2019. doi: 10.145/55922503330998.. URL https::/ 3292500 3330958
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. Lawrence. D. Lee, M. Sugiyama, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 28, Curran Asso- ciates, Inc., 2015. URL htt.httts:///pooeeeeeeee iww..eerse.innn................. mwwrips....... www.rrewwi......arrrereee cc/paper files/paper:
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, WWW 119, pp. 417-426, 2019.
Cong Fang. Chris Junchi Li. Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.. 2018. URL https: http:://///pp.ooceiinss..os www.iinggnnnuuuurie www.ips. cc/paper filess/paerr22118 FLle//5083334722e000ee23333333
Paper..
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3294-3304. PMLR, 18-24 Jul 2021. URL
pre.s..ppes...emmm.. v139 http:////////22.aatmmm fey21a.html
Johannes Gasteiger, Chendi Qian, and Stephan Günnemann. Influence-based mini-batching for graph neural networks. In The First Learning on Graphs Conference, 2022. URL. https
//openreview. net forum d=b
Zijie Geng, Xijun Li, Jie Wang, Xiao Li, Yongdong Zhang, and Feng Wu. A deep in- stance generative framework for milp solvers under limited data availability. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neu- ral Information Processing Systems, volume 36, pp. 26025-2608
Curran Associates, Inc.. 2023a. URL htttps:// neurips hewrips.cc/papp.... cc/paper F1les//aper:/223/ file/ 711e//227555acc55a2aaaaaaaaaa Papprr/eeeeeeteeeeoeeoeeeeeeeeee wonppppeer-aafeeeceee.e.
SaSFFF44888004440 8:04
Zijie Geng, Shufang Xie, Yingce Xia, Lijun Wu, Tao Qin, Jie Wang, Yongdong Zhang, Feng Wu, and Tie-Yar Yan Liu. De novo molecular generation via connection-aware motif mining. In The Eleventh International Conference on Learning Representations, 2023b. URL https:
/openreview net. otw.rrreeeee.eeeteooomeeedo..... forum?id=Q__ex. 8
Zijie Geng, Jie Wang, Xijun Li, Fangzhou Zhu, Jianye HAO, Bin Li, and Feng Wu. Differentiable inte- ger linear programming. In The Thirteenth International Conference on Learning Representations, 2025a.
http::::///ppereviiieee o
Zijie Geng, Jie Wang, Ziyan Liu, Siyuan Xu, Zhentao Tang, Shixiong Kai, Mingxuan Yuan, Jianye
HAO, and Feng Wu. LaMPlace: Learning to optimize cross-stage metries in macro placement. In The Thirteenth International Conference on Learning Representations, 2025b. (thhtp
net./ htt.a//wwweee.eeeeoooooooooooooo
12

---

Published as a conference paper at ICLR 2025
N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic
algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2)217-28) 2011. doi: 00.11370090771800 URL PRLL:ttp:///01..og/111.01 01770/00000001110000000007111110
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1035,
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159; 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, pp. 221 18-22133, 2020.
Wenbing Huang, Tong Zhang. Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bisa-BBanchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL httttpps://prooeeednnngoo nwwrreur........ htwp:/nsnnnnnr....ppeppeeeeeerre http:/pppp//.////11111111 Paper. pdf
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359-392, 1998.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR (Poster). OpenReview.net, 2017.
Haotian Ling, Zhihai Wang, and Jie Wang. Learning stop cut generation for efficient mixed-integer linear programming, Proceedings of the AAAI Conference on Artificial Intelligence, 38(18)20079 20767, Mar. 2024. doi: 10.1609/aaii w38i18..000000 30064. URL http:: htt.://oooaaaaaaoo............ php/
30064
Haoyang Liu, Yufei Kuang, Jie Wang, Xijun Li, Yongdong Zhang, and Feng Wu. Promoting generalization for exact solvers via adversarial instance augmentation, 2023. URL https
13161
Haoyang Liu, Jie Wang. Wanbo Zhang, Zijie Geng, Yufei Kuang, Xijun Li, Bin Li, Yongdong Zhang, and Feng Wu. MILP-studio: MILP instance generation via block structure decomposition. In The Teirth-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:: /tttps://openrviit
net / forum forum?id=w4330 21==W33RTOVV
Haoyang Liu, Jie Wang. Zijie Geng, Xijun Li, Yuxuan Zong, Fangzhou Zhu, Jianye HAO, and Feng Wu. Apollo-MILP: An alternating prediction-correction neural solving framework for mixed-integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025, httpst::: wwppp/eeeeeee..c/oo//o wwt.:/iwwweeeeeee...eme.ee.eeeee Bttp:ummidmmEOooPDDOO.
Yao Ma and Jiliang Tang. Deep Learning Graphs. Cambridge University Press, 2021.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4663-4673 PMLR, 09-15 Jun 2019. URL https: htttps://proceedinng mlr. w.l.ppress/ve v9 wttps///vvvmmuuphyyyee html
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are really making progress? In The Eleventh International Conference on Learning Representations, 2023. URL https
//openreview.o / forumm wtt.rmmmmmitt.to0fffo5a
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. CoRR, abs/2004.1 1198, 2020.
URL htRlhtt::: //arxt/axxi .rg. attp://ss/20000 11198
13

---

Published as a conference paper at ICLR 2025
Zhihao Shi, Xize Liang, and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In International Conference on Learning Representations, 2023. URL
net/ Iorum?id=5VBBAS
Zhihao Shi, Jie Wang, Fanghua Lu, Hanzhu Chen, Defu Lian, Zheng Wang, Jieping Ye, and Feng Wu. Label deconvolution for node representation learning on large-scale attributed graphs against learning bias. IEEE Transactions Pattern Analysis and Machine Intelligence, 46 (6(12):11) 1273- doi: 10.1099/TAAMI.2244.4444900
11286, 2024.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learming Representations, 2018.
Jie Wang, Zhihai Wang. Xijun Li, Yufei Kuang. Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning to cut via hierarchical sequence/set model for efficient mixed-integer programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-17, 2024a. doi: 10.1 109/TTAA...22443337777111
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In Kama- lika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 23341-23366 PMLR, 17-23 Jul 2022. URL fttt::://procedingg
m www.m....p....... 62 wang html
Zhihai Wang, Xijun Li. Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In The Eleventh International Conference Learning Representations, 2023. URL
net/ fertt/formm?aa0 ?id forum?id-2obb4P9bRe 2ob4c
Zhihai Wang, Lei Chen, Jie Wang, Yinqi Bai, Xing Li, Xijun Li, Mingxuan Yuan, Jianye Hao, Yongdong Zhang, and Feng Wu. A circuit domain generalization framework for efficient logic synthesis in chip design. Forty-first International Conference on Machine Learning. PMLR, 2024b.
Zhihai Wang, Jie Wang, Qingyue Yang. Yinqi Bai, Xing Li. Lei Chen, Jianye HAO, Mingxuan Yuan, Bin Li, Yongdong Zhang, and Feng Wu. Towards -eneereerttion logic synthesis: A scalable neural circuit generation framework. In The Thirty-eigtth Annual Conference on Neural Information Processing Systems, 2024c. URL hnttps://oppnreet
nwt. fort//forum? http://oronntd/t//hooooooo d=ZYNYhh
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of PMLR, 09-15 Jun 2019. URL
Proceedings of Machine Learning Research, pp. wwt.:smmm..pppeee. wwwpseessvve... / 9e html
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Keyulu Xu, Mozhi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11592- 1602. PMLR, 18-24 Jul 2021. URL https: / http://///ceeeeeeo ngs ml pre.s / 39 xu httl
14

---

Published as a conference paper at ICLR 2025
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD '18, pp. 974-983, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355520. doi: 10.1145/3219819.32298 3219999, UR.https:://do http///00...0000..1....... 3219819. 3219890
Haiyang Yu, Limei Wang, Bokun Wang. Meng Liu, Tianbao Yang. and Shuiwang Ji. GraphFM: Improving large-scale GNN training via feature momentum. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning mlr
Research, pp. 2226684-5770.. PMLR, 17-23 Jul 2022. URL press/v162/yne wu2l//22ll2/2ggggogo htmml
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020. URL / wttp:eewwwwwwweeernneeeee
net BJdJemmmp-dBBBBBBBBBBeB
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL wtwpt:tt///tt/ http::::/oppereeiiiiieeee/ net forum?
Id3_IY3_ 10=_IY3_4ps$0 3p3_4p
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bue, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL
neurips. .ew.pppps.sinne................. /ttp////ea.ac/////////////////// ffle/
15

---

Published as a conference paper at ICLR 2025
A BACKGROUND OF SUBGRAPH SAMPLING
Subgraph sampling a general mini-batch framework for wide range GNN architectures. For example, subgraph sampling directly GCN the subgraph induced by mini-batch B
R GCN(X8, Norm Norm(AB,5).
where Norm()) normalizes the adjacency matrix of the subgraph As.8. For example, CLUSTER- GCN (Chiang al. 2019) and GraphSAINT Zeng et al. 2020) use Norm(A8,8) As,8 and Norm( A8,8) Dg. B As, s,8 respectively.
Compared with the whole message passing Equation T. subgraph sampling drops the edges Ng + B from the original graph As.ve, leading to significant approximation errors. Thus, the mini- batch selection of subgraph sampling aims to minimize the graph cut from a topological similarity perspective, i.e.,
min (AB,B. O) AB. min [
where O E gl8iX| is matrix. Notably, connected graph cannot be divided into two disjointed subgraphs without dropping edges, the optimal value (7) is always positive in the connected graph.
To minimize the graph cut [. the cluster-based samplers (Chiang et al. 2019 Fey et al. 2021
Shi et al., 2023 Yu et al. 2022) first adopt graph clustering (e.g., METIS (Karypis Kumar 1998) and Graclus (Dhillon et al. (007)) to partition the large-scale graph into {B] . B,, with small [VV, and then sample a subgraph induced by B.. Besides, the random-walk based sampler (Zeng et al., 2020) first uniformly samples root nodes and then generates random walks B starting from the root nodes, which decreases the graph cut (Ma Tang 2021 Chap. 7).
A.1 METIS
METIS is a widely used graph clustering technique (Chiang al. 2019 Fey et al. 2021). Graph clustering aims to construct partitions over the nodes graph such that intra- links within clusters occur much more frequently than inter-links between different clusters (Karypis & Kumar 1998). Intuitively, this results that neighbors of a node are located in the same cluster with high probability. METIS minimizes the graph cut from a topological similarity perspective, i.e. Equation ( main- tain enough information in the original graph, thus reducing the accesses of inaccurate compensation made by the subgraph sampling method, making the computation faster and more accurate.
However, METIS algorithm is too time-consuming (Zeng et al. 2020) on large datasets (e.g. Ogbn- products and Ogbn-papers). Thus, uniformly sample nodes to construct subgraphs of large datasets.
A.2 HISTORICAL EMBEDDINGS
GAS (Fey et al. 202I) further compensates for the messages from the out-of-batch neighbors by historical embeddings, which are defined by
(1+1) z
A B
A
H
(8)
MP
Bias
where H are historical embeedings. GAS pulls historical embeddings from RAM or hard drive storage, making it significantly faster and more memory-efficiet than the methods computing real up-to-date embeddings.
However, the historical embeddings suffer from large approximation errors due to the staleness issue (Fey et al. 2021 Yu et al. 2022 Shi al. 2023). Specifically, GAS updates the historical embeddings in each mini-batch batch average once per epoch and keeps their values between two consecutive updates of the mini-batch historical embeddings. Thus, if the size of the sampled subgraphs is significantly smaller than the whole graph, the update of historical embeddings is infrequent due to very low node sampling probability, leading to large approximation errors of GAS. Moreover, the number of
16

---

Published as a conference paper at ICLR 2025
the out-of- battoff-bcchhtc neighbors is more than that of the nodes in the mini-batch subgraph on large-scale graphs (see Table in (Fey et al. 2021)), pulling a large number of historical embeddings still expensive.
A.3 LAYER-WISE INFERENCE EVALUATION PHASE
To ensure the exact inference results the large graphs, graph sampling usually adapts layer- wise inference, which iteratively updates all node emheddings at each layer without dropping edges. Specifically, the nodes are partitioned into mini-batches with batch size [B), denoted Bi, ..,.. Bn. At the (-th layer, layer-wise inference traverses all mini-baches by
H 1++)) B,
AB.NN,) for E (1, = GCN(H Ni.
Then, layer-wise inference iteratively updates ((++1) on the entire graph based on the previous embeddings (
We. is exact, and the adjacency matrix As. (((+1) is also exact. Since the model is computed aggregates all the neighbor information. Therefore, Vs;
For each computation within batch, the input H
layer-wise, each layer's (++1) is exact. As result, the final output of the model is exact inference results.
Due to the fact that this layer- layer-wise inference requires the computation of large amount of data beyond the evolution dataset, it can lead to potential computational redundancy, resulting in signif- icant computational overhead. TOP does not use this layer-wise inference in experiments, which significantly saves computational costs.
B IMPLEMENTATION DETAILS
B. TOP FOR VARIANT GNNS
We also extend TOP to the message passing framework for variant message passing-based GNNs. The 1-th layer of GNNs is defined
((+1) h = ((+1)
(1.0) ((11))))) sEx:)
(9)
where H.... }} denotes the multiset. We separate the neighborhood information Equation 9 the multiset into two parts
h ((+1)) 1(1-1) h [[D5)] ieNinE u ((
11 ff )
11 b (1)
JENiNE U(r
(10)
where r, is the j-th of the coefficient matrix R. Equation (10 does not depend on the out-of-batch neighborhood information, achieving linear computational complexity. We estimate the coefficient matrix R by
min R
HNg
RHgles
(11)
We provide more details for the estimation of R in Appendix B.4
B.2 IMPLEMENTATION OF GCNII
We follow the implementation of GAS Fey et al. 2021), which introduces the jumping knowledge connection (Xu et al. 2018) to accelerate the convergence (Xu et al. (00T)) for some GNN models.
17

---

Published as a conference paper at ICLR 2025
Table Time and space complexity per gradient update of full-batch gradient descent with whole message passing (Full-batch) CLUSTER (Chiang et al. 2019), GAS (Fey et al. 2021),
LMC (Shi al. 2023), and TOP.
Method
Time complexity
GPU Memory
Neighborhood Compensation
Full-batch
O + [V)d))
CLUSTER
Oo [ (Bd) )
(LL O (de L|B(d)
GAS and LMC
O O(L(degmax Bdd d))
TOP
(L Bld [d 1-)))
((L)B]d)
We first run GCNII Chen al. 2020) to generate embeddings H for each GNN layer Then, we compute the final embeddings by the jumping knowledge connection (Xu et 2018)
M Moutptt
MLP (H)))
B
where MLP is a multi-layer perceptron. We find the best hyperparameters a, of GCNII by grid search on the Ogbn-prodeee products and Ogbn-papen dataset.
B.3 HYPERPARAMETERS
Comparison with subgraph sampling. To ensure fair comparison, we follow the GNN architec- tures, the data splits, training pipeline, and hyperparameters of GCN and PNA in (Fey et al. 2021) We search the best hyperparameters of GCNII, GAT, and SAGE for TOP, CLUSTER, and GAS in the same set.
Comparison with node/laver-wise sampling. We run NS and LABOR by the official implemen- of LABOR (Balin & Catalyurek] (002)) and corresponding hyperparameters, For TOP, uniformly sample nodes to construct subgraphs. To ensure fair comparison, TOP follows the data splits, training pipeline, learning rate, and hyperparameters of LABOR (Balin & Catalyurek 2023). We adapt the batch size of TOP such that the memory consumption of TOP is similar to LABOR.
B.4 FAST ESTIMATION OF COEFFICIENT MATRIX
We compute the coefficient matrix by solving Equation H RH If the size of the subgraph [B] is large, then solving the linear equation ( N/g RH is expensive. As the rank of Ha less than the hidden dimension d << [B], there exists low-rank matrix decomposition such that
W/
Hg T
where Q R Blik has orthogonal columns. 2 is hyperparameter. We use = all experiments. We use the proto-aloooneoooo algoorth (Halko et al. 2011) to efficiently compute Q. By letting = RQQ E RIVE Equation becomes
min (H)) A RiQ Hg)|FF
(12)
Further, we uniformly sample small set S with |S| = k from B to reduce the costs by
min YYsH) AB.vg Q Hs) R
which is equivalent to
min AB (Hwg R(Q
Since H& usually the full-column-rant matrix, we can compute I by R HNy (Q) and then save aAg = As.vg R in the pre-processing phase, where is the Moore-Penrose inverse of
18

---

Published as a conference paper at ICLR 2025
Q,s Hs. At the training phase, Equation (6) becomes
z (1+1) A + OAb(Q.H
(13)
where 0A R xk Qs R and H g The time complexity of the second temm in
Equation 13 is O(B)k + kdd, which is significantly lower than that in Equation 6 i... d))
as [8] >> d.
The analysis for message passing-based GNNs similar.
B.5 DECREASE APPROXIMATION ERRORS BY MORE BASIC EMBEDDINGS
By concatenating N basic embeddings at different random initialization, we can estimate R by (H(((rand) ((WWrandd) ),.... H(WWHWWWWW (WW(aad)) )) E R=x(T+1)xX, which decreases the approximation
emrors as N increases.
B.6 COMPLEXITY ANALYSIS
summarize TOP in Algorithms 1 and 2 TOP first pre-processes the topological compensation by
Algorithm D and then reuses the topological compensation during the training phase.
Algorithm Pre-processing phase of TOP
1: Input: Mini-batches {B, (B.)m
2: Compute H()) with model at random initialization.
3: for = 1, ..., m do
4: Compute Qs, by the proto-algorithm.
5: Compute R by solving Equation (12
6: Compute AAg, As..gg R
7: end for
8: Save (Qs; 1 and (aA 8, 1
Im and A0 AB,) 1 9: Output: J
Algorithm 2 Training phase of TOP
1: Input: Mini-batches (B:) (Qs, )m and (0As, a.
2: for I....,N N do
3: Randomly sample B, from (B.)²
4: Initialize H (D) XB.
5: for - 0,
1 do
Compute H (1+1) o (A + (0As, Q% H w())
6:
7: end for
8: Compute the mini-batch loss
9: Update parameters by backward propagation
end for
As the costs of pre-processing are marginal, compare the computational complexity of the training phase in Table TOP compensates for the neighborhood messages with the least time and memory complexity among existing subgraph sampling methods.
C MORE EXPERIMENTS
C.I MEASURING MESSAGE INVARIANCE IN REAL-WORLD DATASETS.
We conduct extensive experiments on four real-world datasets with five GNN backbones to demon- strate that the message invariance holds in real-world datasets. Table 3] shows that the relative approximation errors of TOP are less than 5% and the test accuracy TOP Is very close to the whole message passing.
19

---

Published as a conference paper at ICLR 2025
Table 3: Message invariance in real-world datasets. TOP approximates the whole message passing
solely through MP with marginal approximation errors.
Relative approximation errors
Test accuracy degradation
Dataset
GNN
Methods
10%
20%
30%
40%
50%
10%
20%
30%
40%
50%
CLUSTER
23.8%
20.2%
18.0%
15.8%
12.1%
5.03%
3.67%
2.99%
2.66%
1.40%
GCN
GAS
17.1%
15.3%
14.1%
12.8%
9.9%
0.80%
0.78%
0.58%
0.61% % 0.33%
TOP
3,5%
2.8%
2.4%
2.2%
1.6%
0.15%
0.10
0.15%
0.12%
0.13%
CLUSTER 13.5%
11.5%
10.2%
9.0%
6.9%
4.72%
3.60%
2.99%
2.38%
1.90%
GCNI
GAS 9.6%
8.8%
8.1%
7.3%
6.0%
2.37%
2.06%
1,88%
1.67%
1,46%
Ogbn-arxiv
TOP
2,5%
2.3%
2.0%
1.8%
1.4 %
0.42%
0.28%
0.35%
0.17%
0.18%
CLUSTER 15.58%
13.08%
11.08%
9.91% %%
7.06%
4.37%
3.69%
3.04%
1.91% 2.80%
SAGE
GAS 24.77%
20.97%
16. 80%
16.02%
10.47%
6.84%
4.83%
3,98%
3.75%
1.77%
TOP
4.38%
3.69%
3.21 %
2.89%
2.03%
0.08%
0.11%
0.01%
0.10 % 0.00%
CLUSTER
23.37%
20.22%%
18.00%
16.27%
12.67%
5.99%
4.34%
3.73%
3.09%
2.04%
GAT
GAS 14.96%
13.47%
12.51%
11.53%
9.08%
1.17%
0.97%
0.89%
0.80%
0.67%
TOP
3.41%
2.99%
2.56%
2.30 %
1.63%
0.15%
0.16%
0.10%
0.08%
0.08%
CLUSTER
29.20%
22%
10%
18%10%
16.02%
11.53%
3.85%
3.05%
2.34%
1.88%
1.14%
GCN
GAS
27.13%
23.87%
21.07%
18. 69%6
15. 15.00%
1.27%
1.22%
0.82%
0. 1..8% 0.49%
TOP
0.78%
0.65%
0.55%
0.53%
0.39%
0.09%
0.09%
0.08%
0.06%
0.03%
CLUSTER
25.32%
19.62%
16.45%
14. 944
11. .229%
4.79%
3,59%
2.45%
2. 2.78%
1.46%
GCNII
GAS 32.87%
30.74%
27.52%
26.00%
23.05%
7.76%
5.82%
4.4 1%
4.5 %%
2.77% %
Reddit
TOP
4.54%
4.75%
5.22%
3.62%
2.58%
0.33%
0.41%
0.54%
0.3 1%
0.30%
CLUSTER 10.74%
7.58%
6.80%
5.35%
3,44%
3.84%
2.85%
2.60%
2. 2.1%% 1.37%
SAGE
GAS 7.03%
5.95%
5.64%
3.43%
1.90%
0.94%
0.60%
0.79%
0.4 % 0.43%
TOP
1.31%
1.10%
1.05%
0.85%
0.61%
0,27%
0.21%
0.19
0.11%
CLUSTER
24.13%
21.40%
18 60%
70%
13.60 13.60%
4.16%
3.20%
1.76%
1.43%
1.13%
PNA
GAS
22.39%
20. 16%
18.77%
16.54%
13.38%
2.60%
2.49%
1.74%
1.64%
0.72%
TOP
13.01%
11.18%
10.48%
9.35%
7.42%
1.48%
1.28%
0.76%
0.97%
0.62%
CLUSTER 5.74%
4.48%
3.82%
3.25%
2.38%
0.89%
0.57%
0.45%
0.34%
0.21%
GCNII
GAS 7.36%
6.52%
5.84%
5.15%
4.01%
1.08%
0,93%
0.77%
0.
0.64%
0.50%
TOP
1.36%
1.24%
1.14%
1.05%
0.86%
0.13%
0.
0.09%
0.08%
0.05%
Yelp
CLUSTER 15.55%
12.53%
10.85%
9.35%
6.99%
1.13%
0.87%
0.66%
0.56%
0.35%
SAGE
GAS
5.21%
4.65%
4,19%
3.85%
2.96%
0.77%
0.62%
0.59%
0.53%
0.40%
TOP
2.41% 5%
2.18%
2.02%
1.84%
1.54%
0.07%
0.07%
0.05%
0.04%
0.04%
CLUSTER 9.55%
8.50%
7.43%
6.91%
5.34%
1.67%
1.67%
1.67%
1.67%
1.67%
Ogbn-products SAGE
GAS
2.44%
2.18%
1.91% %
1.80%
1.37%
0.37%
0.34%
0.31%
0.27%
0.19%
TOP
0.86%
0.73%
0.63%
0.58%
0.44%
0.17%
0.14%
0.12%
0.11%
0.11%
CLUSTER
17.86%
14.66%
12.67%
11.22%
8.48%
3.68%
2.83%
2.24%
1 1.97%
1.33%
Average
GAS
15.54%
13.88%
12.40%
11.19%
8.83%
2.36%
1.88%
1.52%
1.41%
0.88%
TOP
3.46%
3.05%
2.85%
2.45%
1.86%
0.31%
0.27%
0.22%
0.20%
0.15%
20

---

Published as a conference paper at ICLR 2025
ogbn-arxiv &
[n| [3]
= 50%
Reddit &
|
50%
ogbn-products
4%
0.98
[3
0.90
TT
0.74
0.97
Ton
0.85
TO7
Feroue anstie reams
Test/Acc
0.72
SIGNT
Test/Acc
Test/Ace
0.80
0.70
0.75
0.95
0.70
0.94
0.05
9.66
Epochs
Epochs
Epochs
Reddit & = 50%
Yelp &
18 = 12.5%
ogon-papers &
1%
0.97
0.65
0.75
0.84
CLUSTOn inmove and'eestrdon
Test/Acc
Test/Acc
0.65
Test/Acc
0.65
0.62
3.95
0.61
0.55
0.84
0.60
0.59
1.00
200
300
400
50
100
150
200
20
100
Epochs
Epochs
Epochs
(a) GCN on small datasets
(b) GCNII on medium datasets
(c) GCNII+JK on large datasets
Figure 6: Convergence curves (test accuracy vs. epoch). [B] and | denote the sizes of subgraphs and the whole graph respectively.
C.2 CONVERGENCE CURVES (TEST ACCURACY vs. EPOCHS)
We provide the convergence curves (test accuracy vs. epochs) in Figure 6 the test accuracy of the full-batch gradient descent (GD) every two steps rather than per epoch, as GD performs backward backpropagation once per epoch while other methods perform backward backpropagation twice per epoch on the Ogbn-arxiv and Reddit datasets. The convergence curves of TOP are close to GD) on the Ogbn-arxiv and Reddit datasets, while other subgraph sampling methods fail to resemble the full-batch performance on the Ogbn-arxiv dataset. Moreover, TOP significantly accelerates the convergence on the medium and large datasets, e.g., Yelp, Ogbn-products, and Ogbn-papers.
Notably, we report
C.3 TOP ON ARCHITECTURE VARIANTS
We compare subgraph sampling methods (including TOP, CLUSTER (Chiang et al. 2019). GAS (Fey al. 2021). SAINT (Zeng al., (2020), and IBMB Gasteegeer et al.) ) on more GNN architectures (i.c., GAT (Veličković et al. 2018) and SAGE (Hamilton et al.) 2017 in Figure 7 TOP is faster than the existing subgraph sampling methods on GAT and SAGE architectures due to its powerful convergence and high efficiency. The experiments demonstrate that TOP is a general framework for different GNN architectures.
GCN
GAT
SAGE
0.76
AccuraCh
00.74
Accuracy
0.70
S951 54C
Accuracy
065
SAMI
0.72
13M2
0.65
13F0
6.70
0.50
0.68
Runtime (s)
Runtime (5)
Runtime (s)
(a) TOP with GCN
(b) TOP with GAT
(c) TOP with SAGE
Figure 7: Convergence curves (test accuracy vs. runtime (s)) on more GNN architectures (I.c., GAT (Veličković et al., 2018) and SAGE (Hamilton et al. 2017)).
21

---

Published as a conference paper at ICLR 2025
Table Efficiency of the full-batch gradient descent (Full-batch), GAS, TOP. R. and M, denote the runtime epoch and memory consumption of the algorithm respectively.
Runtime
Roa2
Memory (MB))
Moxs Mroe
Full-batch
GAS
TOP
Troz
Full-baich
GAS
TOP
Oghn-ardiv
GCN
50.05
84672
0.63
0.35
01.33
1.07
2463.03
1566.80
1071.22
1.46
Reddit
GCN
30.05
116483
2.05
1.33
0.91
1.45
2796. 30
2444.23
1.344778
1.33
Reddit
GCNI
50.0%
116483
3.21
1.94
1.49
1.50
8240.20
5500 85
3837.90
1.44
GCNI
00M
6752.80
Ogbm products
C.4 RELATIVE RUNTIME PER EPOCH AND RELATIVE MEMORY CONSUMPTION
We report relative runtime per Epoch and relative Memory Consumption in Table 4 As the graph size increases, the subgraph ratio [B||||| decreases. TOP enjoys the least runtime and memory consumption among the baselines.
C.5 COST OF PRE-PROCESSING AND TRAINING
We report the cost of pre-processing and training experiments in Table On the small and medium datasets (i.e., Ogbn-arxiv. REDDIT, and YELP), the total time of different methods is similar and TOP achieves the least GPU consumption most experiments. On the large datasets (i.e. Ogbn-products) TOP is significantly faster and more memory-efficient than existing subgraph sampling methods, as can remove the valid and test nodes from the sampled subgraph without significant performance degradation. Specifically, Equation (6) compensates the neighborhood information from the valid and test nodes based on the mini-batch training nodes. However, the valid and test nodes in subgraphs are important for CLUSTER, these valid and test nodes likely to be the neighbors of the training nodes. Directly removing these nodes without any compensation results in significant performance degradation (see Figures and (). Besides, GAS needs update the historical embeddings of valid and test nodes many times, leading to expensive computational costs.
Table 5: The cost of pre-processing and training.
GNN & Dataset
Methods
Pre-processing time (s)
Training time (s)
Total Time (S)
Memory (MB)
GraphSAINT
0.0
122.0
122.0
1144.1
CLUSTER
1.7
92.8
94.5
1312.0
GCN & arxiv
GAS
3.0
105.0
108
1566.9
ТOP
5.0
99.0
104.0
1071.3
GraphSAINT
0.0
114.5
114.5
1716.2
SAGE
CLUSTER
1.6
93.3
94.9
1450.1
GAS
3.0
107.8
110.7
1616.1
TOP
5.3
98.9
104.1
1110.2
GraphSAINT
0.0
63.3
63.3
2060.9
CLUSTER
1.7
43.7
2253.6
GAT & arxiv
GAS
3.0
$2.8
3025.9
TOP
4.4
58.7
63.1
3177.9
GraphSAINT
0.0
387.6
387.6
1398.2
CLUSTER
14.9
351.7
366.7
1955.2
GCN REDDIT
GAS
16.6
532.0
548
2444.3
TOP
20.1
364.0
384.1
1334.8
GraphSAINT
0.0
672.0
672.0
3935.2
CLUSTER
14.7
595.0
609.7
4242.2
GCNII & REDDIT
GAS
17.4
776.0
793.4
$509.9
TOP
21.2
596.0
617.2
3837.9
GraphSAINT CLUSTER
0.0
1648.6
1648.6
6011.7
12.6
1871.6
1884.2
5940.4
GCNII & YELP
GAS
17.3
2145.0
2162.3
6752.9
TOP
25.3
1990.0
2015.3
2231.8
CLUSTER
35,5
3964.4
3999,9
2048.7
GCNII+JK products
GAS
45,5
7068.0
7113.55
6574.4
TOP
35.8
604.0
639.8
1406.6
CLUSTER
0.00
1007.42
1007.42
1526.91
JC papers
TOP
144.53
1094.01
1238.54
1560.34
22

---

Published as a conference paper at ICLR 2025
Table 6: Prediction Performance. Bold font indicates the best result and underline indicates the second best result.
# nodes # edges
169K 1.2M
89K 450K
2.4M
111M
61.9M
1.6B
Ogbn-arxiv acc
Flickr
Ogbn-producee products acc
Ogbn-papers acc
Method
acc
NS-SAGE
71.49
50.10
78.70 80.70
67.06
CLUSTER-GCH
48.10
78.97
GraphSAINT
51.10
79.08
SHADOW-GAT
72.74
53.52
80.71
67.08
SGC
48.20
63.29
SIGN
51.40
80.52
66.06
GD-GCNII
72.83
55.28
OOM
OOM
BUUSTRR-GNNI
72.39
55.33
79.62
51.73
GAS-GCNII
72.50
55.42
79.99
OOM
TOP-GCNII 72.52 1: 0.34
55.21 0.46
81.96 +: 0.24
67.21 0.12
C.6 PREDICTION PERFORMANCE ON VARIOUS GRAPHS
Datasets. We report the prediction performance of TOP on four datasets, i.c., Flickr (Zeng et al. 2020), Ogbn-arxiv, Ogbn-products and Ogbn-papers (Hu al. 2020), where the two challenging large datasets (i.e., Ogbn-product products and Ogbn-papers papers (Hu et al. 2020)) contain at least 100 thousand nodes and one million edges. As shown by Table as the batch size is significantly lower than the size of the whole graph, the convergence of mini-batch methods under small batch sizes becomes very important.
Baselines and implementation details. Our baselines are from the OGB leaderboards (Hu et al. 2020), including node-wise sampling methods (GraphSAGE (Hamilton et al. 2017), subgraph- -ise wise sampling methods (CLUSTER-GCH) GCN in the original paper (Chiang et al. 2019), GraphSAINT (Zeng) et al. 2020), SHADOW Zeng et al. (021) and GAS (Fey et al. (021)), precomputing methods (SGC (Wu et al., 2019) and SIGN (Rossi al.) 2020 ). The GNN backbones of these baselines are different, as more scalable methods usually use more advanced but more memory-come connurin GNN backbones. Due to the differences in GNN backbones, frameworks, weight initialization, and optimizers in the baselines, we report CLUSTER-GCNT and GAS-GCNII for ablation studies. The hyperparameter settings are the same as Section 6.1 The results of the baselines are taken from the referred papers and the OGB leaderboards.
Prediction performance. We report the prediction performance of TOP in Table On the small datasets (i.e., the ogbn-arxiv and flickr datasets), which have fewer than 170k nodes, the prediction performance several subgraph sampling methods (CLUSTER, GAS, and TOP) is comparable to gradient descent (GD), they can use a large subgraph ratio /VV the small dataset (e.g. 50% used in GAS), such that the sampled subgraphs are close to the whole graph. On the large datasets (i.e., the ogbn- pronn-cs and ogbn-papers datasets), as the large subgraph ratio may suffer from the out-of-GPU memory issue, we use a small subgraph ratio (less than 4%). However, the small subgraph ratio increases the ratio of missing messages in MPоB for CLUSTER and results in the severe staleness issue for GAS (the update of historical embeddings in GAS is infrequent due to very low node sampling probability). The accuracy of TOP is larger than other baselines, it compensates the messages in MPоR by the message-invarant trasformation g and relies solely on up-to-date embeddings, thus avoiding the staleness issue of the historical embeddings.
C.7 EXPERIMENTS ON HETEROPHILOUS GRAPHS
The message invariance still holds on heterophilous graphs. To verify our claim, we conduct experiments on five heterophilous graphs (i.e., roman-empire, amazon- moazzon-ratings... minesweeper, tolokers, and questions) provided by the recent heterophilous benchmark (Platonov et al.) (023), shown in Table 7 We set the subgraph ratio to be 50%, as the heterophilous graphs (10k-50k nodes) significantly smaller than the homophilic graphs (200k- 1 2000k nodes) in Section 6 On the
23

---

Published as a conference paper at ICLR 2025
heterophilous graphs, although a node may be very different from its neighbors, the neighbors may be similar to other nodes in the subgraph. Notably, the message-invariang transformation in Equation 4 does not restrict that the embedding of an in-batch node should be similar to its neighborhood embeddings, and thus the message-invarian transformation is able to approximate the neighborhood emheddings by other nodes in the subgraph.
Table Approximation errors of TOP, CLUSTER, and TOP on heterophilous graphs.
Heterophilous Graph CLUSTER
GAS
TOP
amazon-ratings 54.53%
4.14%
1.36%
1.02%
minesweeper
19.68%
3.12%
questions roman-empire
20.25%
9.54%
4.90% %
5.42%
1.65%
0.88%
Figure 8 further reports the convergence curves of TOP, CLUSTER, and GAS on the homophily datasets. From 7 the approximation errors of TOP are significantly lower than CLUSTER and GAS on minesweeper, tolokers, and questions. Accordingly, TOP is also significantly faster than CLUSTER and GAS on the three datasets.
amaszon-rating
2.00
0.00
tolokers
questions
202
Runtime
10
Runtime
Runtime (4)
Runtima
Runtime
Figure 8: Convergence curves of TOP, CLUSTER, and GAS on real-world heterophilous graphs.
C.8 EXPERIMENTS UNDER VARIOUS SUBGRAPII SAMPLERS
We conduct experiments to demonstrate that TOP consistently brings performance improvement for various subgraph samplers. We first evaluate the relative approximation errors of TOP, CLUSTER, and GAS under METIS, Random, GraphSAINT (Zeng et al. 2020). and SHADOW (Zeng et al. 2021 sampling in Table g The results demonstrate that TOP significantly alleviates approximation errors by integrating different subgraph sampling techniques. Specifically, different subgraph sampling techniques are designed to encourage the connections between the sampled nodes with trade-off for efficiency. METIS aims to directly achieve this goal, while it may be more time-consuming than other sampling techniques. Random sampling is the fastest sampling baseline among them, while it does not consider the connections between the sampled nodes. Thus, Random sampling significantly amplifies the approximation errors of CLUSTER and GAS, while TOP is robust under Random, GraphSAINT, and SHADOW sampling.
Table 8: Message invariance in real-world datasets with various subgraph samplers.
Relative Approximation Errors
Dataset
GNN
Methods
Random SAINT SHADOW METIS
CLUSTER
30.02%
15.79%
12.49%
12.10%
Ogbn-arxiv
GCN
GAS 45.29%
9,89%
ТOP
7.61%
5.94%
3.41%
1.58%
CLUSTER 25.91%
22.22%
21.32%
3.44%
Reddit
SAGE
GAS 13.91%
1.90%
ТOP
3.10%
1.45%
1.27%
0.61%
CLUSTER
4.87%
1.13%
0.91%
2.38%
Yelp
GCNII
GAS
7.86%
4.01% 40%%
TOP
2.68%
0.74%
0.64%
0.86%
24

---

Published as a conference paper at ICLR 2025
Figure ftruhhr shows the convergence eurves of TOP, CLUSTER, and GAS under Random sampling. Due to the accurate and fast message passing of TOP, TOP significantly outperforms CLUSTER and GAS in terms of accuracy and converge speeds. By integrating the results with Figures ((a) and 3(b)
the performance improvement of TOP consistent for various subgraph sampling methods.
ogbn-arxiv & GCN
Reddit & SAGE
Yelp & GCNII
0.72
TOP CLUSTER
0.98
TCP CUUSTER
TDP
CLUSTER
Test/Acc
CAS
Test/Acc
0.97
GAS
Test/Acc
GLSS
0.70
0.6
0.68
0.5
10
200
400
Runtime (s)
Runtime (s)
Runtime (s)
Figure 9: Convergence curves of TOP, CLUSTER, and GAS under the Random sampler.
C.9 DISTANT NODES ARE ESSENTIAL FOR PREDICTION
Datasets. We generate a cycle graph with 500,000 nodes and 1,000,000 edges. The node features are randomly sampled from 0, 1 and the task is to fit the label propagation algorithm, i.e., X, 0.9 X AX,-1 + (1 0.9) x Xo for 1 1,2, .... 10, where Xo denotes the node features and A denotes the adjacency matrix. The label Y is normalized by X10/ / Training, validation, and test node ratios are set at 0.8, 0.1, and 0.1, respectively. We use the mean squared error (MSE) to evaluate the prediction results.
Model. We train a ten-layer GCNII to ensure the model can capture sufficient information used in the label propagation algorithm.
Subgraph sampler. As the METIS sampling encourages the connections between the sampled nodes, node, and its most ten-th neighbors appear simultaneously in the subgraph. To remove the high-order information in the subgraph, we instead uniformly randomly sample nodes to construct the subgraph. We partition the whole graph into 200 TOP, and Full-batch respectively. CLUSTER trains GNNs using only in-batch nodes and Full-batch trains GNNs using the whole graph.
and train three GNNs by CLUSTER,
Performance. We run the trained GNNs on the subgraphs induced by [ Table reports the average ratio of subsampled nodes (1 | / and MSE of the above- mentioned methods.
1. CLUSTER performs significantly worse than full-batch-whie trains GNNs with distant nodes-by order of magnitude (A = 10). Thus, the feature vectors of distant nodes are essential for prediction for the ogbn-arxiv dataset.
2. The curve (MSE vs. k) of TOP is similar to Full-batch, and both of them achieve the highest MSE at 2. Thus, TOP's good performance is due to its ability to capture information about distant nodes, similar to Full-batch.
3. The MSE of CLUSTER is lower than TOP and Full-batch when k < 6, demonstrating that GNNs trained by CLUSTER may overfit the distribution of sampled subgraphs.
D PROOF FOR CONVERGENCE
We first show that TOP based on Equation provides unbiased gradients. We assume that subgraph 3 is uniformly sampled from V. When the sampling is not uniform, we use the normalization technique (Zeng al. 2020) enforce the assumption.
Theorem D.1. Suppose that the message invariant transformations exist and the subgraph
B is uniformly sampled from V. The iterative message passing of Equations (5) and H (++1)
(z (1 (0) leads to unbiased mini-batch gradients dw such that
E(dw] V.L.
25

---

Published as a conference paper at ICLR 2025
Table 9: Distant Nodes are Essential for Prediction.
k-hop
MSE (CLUSTER)
MSE (TOP)
MSE(Full-batch)
0
94.99%
0.021441
0.25521
0.281997
2
75.22%
0,004819
0,406065
0.579234
4
55.84%
0.000702
0.105431
0.235721
36.85%
0.001173
0.038446
0.009939
8
18.24%
0.001388
0.000132
0.000049
10
0.00%
0.001396
0.000045
0,000040
Proof. Given any mini-batch B, the embeddings H of TOP are the same as that of SGD due to Wgg =(H for any GNN parameters W Thus, their total objective functions of C CroP the same.
H
If iOP is biased, then the expected gradient WwCr # C. Thus, there exists c > 0 and Wo such that (ror(W)) L(W) while Cror(Wo vv,, 4(W- <Vw, L) due different directional derivatives (Vw,C, L, Cror) * Cl which contradicts to L = Cror. The unbiasedness holds immediately.
D.1 PROOF OF THEOREM 5
CONVERGENCE GUARANTEES TOP
In this subsection, we give the convergence guarantees of TOP. The proof follows the proof of Theorem Appendix C.4 of (Chen al. 2018a).
Proof. As VC is --piscchitz, we have
((V(+)))
= =(Wit))+ + ['' (VL(M)))) + +(p(K+)) w(x))), - at Mik) -W1k)
- -c(W()) + (VL(MV))) M((+))
+ +16' (VL(N()) + ((WU(+))) - -W())) vL(M(()), (V(++) wok)) dt
$ ((W()))) + (VL(M)))) MU(H+)) - Mik)
+ // |VLCME + ((D(++1) - -MDR))) - vC(W(()) (211) -00 dt
< =(W(A)) (VL(M)()) MU(H+1) wwnt) f'' ((lI 1 ae
-(W(+)) + (VL(M))()) W((+11) - mi(t)) 2 [nlaat)) - -001
Notice that the update formula of With is
((++1) = wi() (k)
where d is the gradient of TOP at the k-th iteration and we select < 3. Let (R) aW VL((())) then
((M((+1)
s L(WD() + (VC(W())) (((+1) - W(()) -W0+)) ? - wocki
2
=((D()) - - ((0)) + 7²² [1d _l
=((D()) 1 77) (V A (k))
11(1
117 /L(M(())))
719 11 (
26

---

Published as a conference paper at ICLR 2025
By taking the expectations of both sides, we have
B|C(W(+t))] -
< - -111 (())) - 7
2 |
+ "
A (3) |
By the properties of the expectations and Theorem D.1 we have
B( A = (((V VL(MV()))
( [V V -V2())())))
0,
which leads to
[[[(()()))]] - ((C(()(()
711
n2
|B ]B
)13)
572
A0 (A) [13]
1811
2
2
- 27 1 M| s ((C((()) E[C((((+)))))
18 A (8)
12]]
2
By summing up the above inequalities for & [V]] and dividing both sides by Nv
) we have
L(V()) E[C(M((+))
17y
k=
EI
A
N
Nn )
2 177
N
-(w()) - -L" m
=k=1 A
Nn(1 ))) 2 m
N
By noticing that
N
Ell
V ((
b = E| C
V L(N(
R
N
and
( = 1lll - v
< 4G
we have
Ell 1I = ((W())) -
4G m
+ 2 -
N7(1 12)
If 1 < 3,, 7= O(N-)) we have
V [|]) 2(C(W(() -L")
+ +GG = 1 ON-
Nn
Therefore, by letting ((C()()))=5 + 80 -(N $), Theorem 5.1 follows immediately.
No
E ENCODING SYMMETRY IN GRAPHS VIA TOP
In this section, we show that the embeddings of GNNs at random initialization can encode the symmetry in the original graph, which is specific node similarity.
27

---

Published as a conference paper at ICLR 2025
Notations For brevity, N, = u (i) denotes the neighborhood of node i with itself. We recursively define the of neighborhoods within k-hops N We--1 with N NN, For Theorem E.4 we
denote all the possible embeddings at the 1-th layer by E(0) (h h ..... ()) ). where ( the number of different embeddings at the (-th layer, 7 E [r]]-
is
Motivation for the symmetry. We first motivate the basic embeddings from the graph isomorphism perspective. The 1 i-dimensional Weisfeiler-Lehman test (i.e., 1-WL test) (Weisfeiler & Leman 1968)
widely used to distinguish whether two nodes or graphs are isomorphic.
Given initial node feature/representation h!!), at the /-th iterations, 1-WL test for GCNs updates the node representation hy h('-)) based the local neighborhood by
Hash( NH))
(14)
Following (Xu et al. 2019). we show the connections between GNNs and 1-WL test in Lemma E.1
Without loss of generality, we present the theories for the GCN version. Extending them to other GNNs easy.
Lemma E.1. Given graph 9 EV. and GNN, nodes i,j E V are indistinguishable under I iterations of the 1-WL test, then there holds
for all GNN parameters.
Proof. As j are indistinguishable under iterations of 1-WL test, have h!") h29 Notice that the function Hash is injective, we have
(1h--1) ( E. u and -V
Then, we can know that
{(h ( P PEN.. a, a E N.1) , .eNN,,ENN,
and (1W u Ni}) = =(IW.,,uENN))
which is equivalent to ((h6-2) . p N ((h(-2) ,q N3 and
Recursively, we have
,4 e N3 and -
[1h00) P E N = (thl) ( and HWW. N }}.
By xx = h and incorporating the equations above, we can know that
(1(xp, Aup), - .P . N A.g) .9 e N
Thus, have
H N 00 N. . N
w - N N w(l)) (()) N
H (1-1)
o A
( w((-2) a (A
(1 2(l-21) = H (1-1)
N.
N.N? No
N, N N₂
N,
H o A - ( ((11) A ト N
( ((l-1)) H."'
N,
for all GNN parameters.
28

---

Published as a conference paper at ICLR 2025
However, many GNNs are less expressive than the 1-WL test, is difficult find 1-WL isomorphic node pairs by detecting the embeddings in GNNs. Fortunately, TOP does not require as strong expressiveness the 1-WL test. For two nodes, do not need to identify whether they are 1-WL isomorphic, but only need to identify whether they are indistinguishable by GNNs.
Definition E.2. (Isomorphism under GNNs). Given initial node feature/representation H(") at the 1-th iteration, node pairs (1.j) isomorphic if they are indistinguishable under / iterations of GNNs, Le. H H for all GNN parameters.
From the definition E.2 if two nodes isomorphic under iterations of GNNs, then their embeddings at the 1-th layer are the same for all GNN parameters. Therefore, given two indistinguishable nodes under I iterations of GNNs,
one to extrapolate the other without any bias.
Finding isomorphic node pairs. We estimate the coefficient matrix R by solving Problem 12 with H(Wrond) are the embeddings of GNNs at random initialization. Intuitively, neural network random initialization is likely to be a hash function, as it maps different inputs to different vectors in the high dimensional space. The hash function can detect isomorphic node pairs with the same embeddings. We show this by the following theorem.
Theorem E.3. Assume that the activation function is the LeakyRe function and GCNs are ran- domly initialized. If node pairs (i.5) are not isomorphic, then H (C.rand) o H(lraa)) with probability one.
Proof. Suppose node pairs (i,j) are not isomorphic. For / 1, we have
a (Á, = H!" H o (A (A, (
Since the activation function LeakyReI.U is injective, we have Y,xW(0) * A
leading to
o + X,X.
Thus, we have
X (lrad)) * A X.X (0.raad)
H (randd) = 0 (.. # XA (0.aadd))) = H (Irond)
for all GCN parameters.
For / similar the case of | we have
À 22 2) (1 * A (1-1) A, (12
We only need prove that (W e Rddd A, a -AH
Ar a (AHH
Null set in gdxd For simplicity, we denote TT = A. ST A, and (H Thus. A, (AHH-22W((3)) A, a(AH" ((AH--2((-)))) ((1-2)) is equivalent to (a 3) (BB((22)) = O
Notice that
(xx) ((x))) = [r, if 2 0 kr, if <
where & E R is the negative slope with the default value 1e-2.
Then we can know that
(a(BW(-2)) a
Σ B w((-2))
Σ oue Bus Bu 2
where u [n], E [d]] our orrk
29

---

Published as a conference paper at ICLR 2025
Therefore,
"
d
((a- ()(o))aooBlll-ll (BW((
Σ
au Ba)
Σ
Juy Bas W!l-2) su
a=1
8=1
d
Σ
w
Jue PuoBuola - -Bu).
==1
Let You Eu=i Oue Buslu - Bb) E and 7 = (You) E Ruudd Then
((a- () o
equivalent to
w(l
() 2) Yov ((a - B) =((a-B))(BW(()))) =0
for all v E [d].
However, for all value of dae since the isomorphism of node pairs (i.j). As result, for dwe fixed, the solution to E W!l ? 7 d x d - at most.
[d] forms subspace in gdxd with the dimension
Thus, the set (W(i-2) Rddd [. (AH 2) w() A, (AHH 2) w(t 2)) is contained by the union of several subspaces in gdxd with the dimension x d 1 at most, which means is a Null set in Raxd
Therefore, H. (.rand)) * H
(rrand) with probability one.
From Theorem such that H (Lrand)
E.3 for an out-of-batch node .Ng. if randomly initialized GCNs detect B (!rand) then node pairs (V.j) probably isomorphic. Thus, we can estimate 12 that R; = e, Moreover, the estimation probably leads to a zero approximation error at node j since H e; H
the solution R to Problem
0 H holds for all GCN parameters.
In practice, the ratio of the indistinguishable node pairs increases the batch size [B] increases. The following theorem shows that the approximation error of TOP decreases to zero if the batch size [8] large enough.
Theorem E.4. Assume that is uniformly selected from V, the initial features X are sampled from finite set, the number of different embeddings is bounded by t, and [B] 2 Bu & t tlog( Lte="), Then, there exists the coefficient matrix R such that Hag RHg with probability O(e) for any GCN parameters.
Proof. By Theorem if for any out-of-batch node there exists isomorphic in-batch node i E B, then we can easily find the coefficient matrix R with R, = es such that H = RHg.
+
As result, only need to estimate the probability of the existence of such in bn-batch node i. Notice that, if for all E [4]. ((H.). B}} contains all the embeddings in g0), then the existence follows immediately. Thus, we estimate the probability of E c ((H!), E B}}, VI E [2] as lower bound.
By considering the contrary, for [B] fixed, we have
p(E() c ( v B3) BI) = 1 - p(E of (H.)) ve B}} [B)
1 -1-(33 $ ((H!), B}} [B]
(
> 1 Σ
p(h $ (HH)) B)} [B)).
30

---

Published as a conference paper at ICLR 2025
Notice that e and p(hl & ((H)) e B]) [B]) (1 2 (1 2)188, have
p(E c (H UE B}} [B] 2 Σ
p(h $ ((H v E B}} [B)
#=1
(0)
2 Σ (1 1 [
2 - (11 - } )18
which leads to
p(E c (( (EB)), vI e [4] [B] p(3 & (HH,) e EBB) (B))
Σ p(E & ((H BE B)))
2 1 - Lt(1 ) BI
By the condition of the batch size [B], we know that
B 2 t
log (ttE
log(Lte-1)
-oo((1 - 1)
logi !LtE
leading to
p(E c (H
B}}, e [4] BI) 2 1 - Lt(1
7 1
logoo log, (Lie
2 1 - Lt(1
= =1-5.
Thus, we have
M
p(E() C ((H,), B),, AI e [4])
Σ
((E() c ((
AI E [Z]] [B))((())
B
|
Σ (1- ()
18 = Ba
Therefore, the probability of the existence of the coefficient matrix R
p p2 ( c ((HH) v E B}}, VI e [4]) 2 1-E,
which means p = OEe).
Remark E.5. The assumption of discrete features in Theorem E.4 is widely used to analyze expres- siveness (Xu et al. 2019 Murphy et al. 2019). In real-world graphs with continuous features, finding the exactly indistinguishable node pairs difficult. For example, the probability of sampling two points with the same value from the Gaussian distribution is zero. Fortunately, Equation (12) still achieves small approximation errors in practice. To verify this claim, we empirically demonstrate that TOP compensates for neighborhood messages well in Figure 2 in Section 5.2
31

---

Published as a conference paper at ICLR 2025
F LIMITATIONS AND BROADER IMPACTS
In this paper, we propose a novel subgraph-wise sampling method to accelerate the training of GNNs on large-scale graphs, i.e., TOP. The acceleration of TOP is due the assumption message invariance. We have conducted extensive experiments to demonstrate that the message invariance holds various datasets. However, is still possible that the message invariance assumption does not hold in certain datasets and complex GNN models.
Moreover, this work promising many practical and important scenarios such as search engines, recommendation systems, biological networks, and molecular property prediction. Nonetheless, this work may have some potential risks. For example, using this work in search engine and recommendation systems to over-mine the behavior of users may cause undesirable privacy disclosure.
32


Reviews:
[{"review_id": "Wp9zI5nAHz", "reviewer": "Reviewer_74yw", "summary": "The paper presents Topological Compensation (TOP), a method for improving mini-batch scalability in Graph Neural Networks (GNNs) by leveraging message invariance. Traditional mini-batch methods often face computational challenges due to dependency on out-of-batch neighbors, especially with deeper GNN layers. The proposed approach replaces costly message-passing operations between in-batch and out-of-batch nodes with a mThe concept of message invariance is innovative and addresses a critical bottleneck in GNN mini-batch processing. Converting MP-OB to MP-IB is well-motivated and theoretically sound. The experimental validation is robust, covering various GNN models (e.g., GCN, GAT) and datasets with different characteristics. essage-invariant transformation that effectively approximates these operations without sacrificing accuracy.", "questions": "1- Would TOP benefit from combining message invariance with other sampling techniques to further improve scalability or accuracy?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The concept of message invariance is innovative and addresses a critical bottleneck in GNN mini-batch processing. Converting MP-OB  to MP-IB is well-motivated and theoretically sound.", "weaknesses": "For large datasets, transformers based architechtures are very used for these datasets. Can your theoritical analysis be extended to GNN which doesnt follow the message passing scheme, for example GraphGPS?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HRBDSLtwXa", "reviewer": "Reviewer_xxsU", "summary": "The authors propose a new graph subsampling technique based on the concept of message invariance. They describe message invariance in definition 4.1: which states that the feature vectors of nodes that are not inside the current mini-batch can be recovered via some unknown transformation of the feature vectors in the subsampled batch.", "questions": "- Why is it reasonable to assume that the transformation g (related to message invariance) can be approximated by a linear projection (as stated in line 280)? If such a transformation exists, wouldn't it likely be highly non-linear? Did this originate based on the linear GNN example? Is there a way of at least learning a non-linear transformation and letting the network figure it out by itself rather than imposing linearity by construction? 1) Provide more justification for why a linear approximation is reasonable, beyond just the linear GNN example 2) Discuss the limitations of assuming linearity and how this may impact performance 3) Consider exploring non-linear transformations and compare performance to the linear case\n\n- Some baselines in the large graph representation learning literature train on stochastically subsampled graphs on GPU, but at inference time they do prediction using all nodes in the graph on CPU. In such cases, the model would actually see out of batch nodes at inference time. Any thoughts? 1) Discuss how your method compares to or could be adapted for approaches that use full graphs at inference time, 2) Consider evaluating your method in both subsampled and full graph inference settings\n\n\n- Could the authors conduct a synthetic experiment in a controlled setting where they ensure that feature vectors of distant nodes are essential for prediction and empirically demonstrate the following:\n\n   1. Train the model using only in-batch nodes and demonstrate that this approach performs significantly worse than training with distant nodes (which, due to subsampling, are likely out of batch).\n   \n   2. Train with the proposed framework and test the number of subsampled nodes and the average n-hop distance required to include in-batch nodes to recover performance.\n\nI would suggest running this on graphs with a manageable number of nodes that can fit on a GPU, yet are sparse and high in diameter. \n\nI would be happy to raise my score if the authors can show message invariance in a more controlled environment.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Message invariance seems like an interesting new idea.\n- The authors give a couple of theoretical examples for simple problems (using linear GNNs) in which message invariance holds. I understand that generalizing this to include non-linearities can be very difficult.\n- Their method is more computationally efficient than other baselines.", "weaknesses": "- I am unsure whether message-invariance exists. The method proposed by the authors, see for example equation 6, could also be interpreted as a graph rewiring of the subsampled nodes of the induced subgraph. Good performance could come from rewiring and alleviation of other known issues in GNNs such as over-squashing for instance, rather than due to learning message-invariance.\n- The large graph datasets that the authors use tend to be quite local. Rather than message-invariance, it could just be the case that the features of far away nodes are irrelevant for the final prediction (there is no long-range dependency). Hence using only features of nearby nodes may be enough.\n- It would be interesting to see how this technique affects the performance of graph transformers such as SGFormer (https://arxiv.org/pdf/2306.10759) which are designed for large scale graphs and which allow for global communication.\n- This is minor, but the first time I read the abstract I found it quite confusing, particularly the second sentence. Also, mentioning in the abstract that your method is particularly targeting large graph transductive learning would be good.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "75H47zi63M", "reviewer": "Reviewer_oD2v", "summary": "This work considers the problem of message-passing in large graphs, where a sampled mini-batch of nodes, $\\mathcal{B}$, aggregates information from exponentially growing neighborhood sizes, $\\mathcal{N}\\_{\\mathcal{B}}^c = \\mathcal{N}\\_{\\mathcal{B}} \\setminus \\mathcal{B}$. To tackle the inefficiency and/or limited performance of existing sampling based methods designed to tackle this problem, a technique called *Tological Compensation* (TOP) is presented, which captures information from out-of-batch neighbors, while limiting the message-passing to the in-batch nodes.\n\nThe authors start by hypothesizing an invariant structure in the node representations, such that the hidden representations satisfy $\\mathbf{H}^{(l)}\\_{\\mathcal{N}\\_{\\mathcal{B}}^c} \\approx \\mathbf{R} \\mathbf{H}^{(l)}\\_{\\mathcal{B}}$, for some linear transformation $\\mathbf{R} \\in \\mathbb{R}^{|\\mathcal{N}\\_{\\mathcal{B}}^c| \\times |\\mathcal{B}|}$ learnt during pre-processing. This allows information from $\\mathcal{N}\\_{\\mathcal{B}}^c$ to be efficiently incorporated into a message passing scheme over just $\\mathcal{B}$. Specifically, they augment the original propagation matrix as $\\tilde{\\mathbf{A}}\\_{\\mathcal{B},\\mathcal{B}} + \\tilde{\\mathbf{A}}\\_{\\mathcal{B},\\mathcal{N}\\_{\\mathcal{B}}^c} \\mathbf{R}$, and then simply propagate messages over $\\mathcal{B}$.\n\nOn a range of large real-world datasets (169K-111M nodes, 1.1M-1.6B edges), they demonstrate that TOP can stay competitive with the full-batch gradient descent, and outperforms other baselines. They also show that, at convergence, the approximation error in node representations using TOP is less than 5%, adding support for the invariant structure in the node representations. Theoretically, they show that the convergence rate of TOP is $\\mathcal{O}(\\epsilon^{-4})$, same as node-wise sampling algorithms, and better than $\\mathcal{O}(\\epsilon^{-6})$ rate for subgraph sampling algorithms.", "questions": "1. Do you have any comments on the regularization effect of stochastic sampling methods, and why TOP outperforms them on test-sets despite (seemingly) not having any regularization mechanism?\n\n2. In Definition 4.1, am I correct to assume that by \"for any GNN parameters $\\mathcal{W}$\", you mean 'for all $\\mathcal{W}$' and not 'for a given $\\mathcal{W}$'?\n\n3. Definition 4.1 says $g$ needs to satisfy $\\mathbf{H}^{(l)}_{\\mathcal{N}\\_{\\mathcal{B}}^c} = g(\\mathbf{H}^{(l)}\\_{\\mathcal{B}})$. Is that supposed to be $\\forall l\\in[L]$ and $\\forall \\mathcal{B}\\subset \\mathcal{V}$?\n\n4. I don't quite understand the argument in the paragraph starting at line 246. Can you elaborate?\n\n5. In section 4.2.2, how valid is the assumption on full column-rank of the convolved feature matrices? \n\n6. The objective near line 262, $\\\\\\|\\mathbf{Z}^{(l)}\\_{\\mathcal{N}\\_{\\mathcal{B}}^c}-\\mathbf{R}\\mathbf{Z}^{(l)}\\_{\\mathcal{B}}\\\\\\|$, what is $l$ here and what is $\\mathcal{B}$?\n\n7. The second equality near line 264, that need not be true unless the minimum of the objective $\\min\\_{\\mathbf{R}} \\\\\\|\\mathbf{Z}^{(l)}\\_{\\mathcal{N}\\_{\\mathcal{B}}^c}-\\mathbf{R}\\mathbf{Z}^{(l)}\\_{\\mathcal{B}}\\\\\\| = 0$. Is it 0 because of the full column-rank?\n\n8. In the computation of $\\mathbf{R}$ in line 294, what is $\\mathcal{B}$ supposed to be?\n\n9. Am I correct to understand that the proof of Theorem 5.1 only uses the unbiasedness of TOP gradients, as shown in Theorem D.1? Doesn't the part after that closely follow the proof of Theorem 2 in Appendix C.4 of Chen et al. (2018a)? If so, this should be emphasized; continue to keep it in the appendix for completeness, though.\n\n10. Possible typos (correct me if I am wrong; in that case, I may have read the related parts wrongly):\n  - In definition 4.1, $g$ should be a map from $\\mathbb{R}^{|\\mathcal{B}|\\times d}$ to $\\mathbb{R}^{|\\mathcal{N}_{\\mathcal{B}}^c|\\times d}$.\n  - In line 258, supposed to be $\\mathbf{Z}^{(l)}\\_{\\mathcal{B}}$ instead of $\\mathbf{X}^{(l)}\\_{\\mathcal{B}}$.\n  - The objective near line 262 should be $\\\\\\|\\mathbf{Z}^{(l)}\\_{\\mathcal{N}\\_{\\mathcal{B}}^c}-\\mathbf{R}\\mathbf{Z}^{(l)}\\_{\\mathcal{B}}\\\\\\|$.\n  - In line 294, $\\bar{\\mathbf{H}}\\_{\\mathcal{N}\\_{\\mathcal{B}}^c}$ instead of $\\bar{\\mathbf{H}}\\_{\\mathcal{N}\\_{\\mathcal{B}}}$.\n  - In line 1269, $\\bar{\\mathbf{H}}\\_{\\mathcal{N}\\_{\\mathcal{B}}^c}$ instead of $\\bar{\\mathbf{H}}\\_{\\mathcal{N}\\_{(\\mathcal{B})^c}}$.\n  - In line 1300 (and others below), $\\mathbf{d}\\_{\\mathcal{W}^{(k)}}$ instead of $\\mathbf{d}\\_{\\mathcal{W}}^{(k)}$.\n  - Not completely sure, but the second expression in line 1314 seems to be a typo (I can understand what was intended, though).\n  - In line 1320 (and following), $\\mathcal{W}^{(1)}$ instead of $\\mathcal{W}^1$; similarly for $\\mathcal{W}^{N+1}$ and $\\mathcal{W}^R$.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The idea of using an invariant structure to approximate messages from out-of-batch nodes to in-batch nodes is unique and interesting.\n\n2. It boasts an $\\mathcal{O}(N^{-4})$ convergence rate in the number of iterations $N$, equal to node sampling methods (Section 5.3).\n\n3. The message invariance structure is demonstrated in some dummy cases (Section 4.2), and then validated via experiments (Section 5.2). As simple as a linear approximation is competitive on several large datasets, outperforming several baselines (Section 6).\n\n4. The memory cost of the method scales very slowly with the number of layers in the GNN, unlike other baselines compared (Figure 5).\n\n5. The variance of this method is also low (Figure 3), making it a reliable choice.", "weaknesses": "My rating for the work is low right now primarily because the presentation can be significantly improved. I also includes suggestions here, since I think some of them are weaknesses in the manuscript.\n\n1. The citation (Ma & Tang, 2021), near line 46, is a book on graph deep learning, which is too general. I assume you wish to direct the reader to chapter 7 in it. It would be helpful to specify that along with the citation.\n\n2. There seems to be some inconsistency in the definition of the edge set and corresponding matrices: if $(i,j) \\in \\mathcal{E}$ denotes an edge from $i$ to $j$, then $\\mathcal{N}\\_i$ is the out-neighborhood of node $i$, i.e. the nodes it *sends messages to* (not receives from), which I believe is not the intended definition. Similarly, $\\mathbf{A}\\_{ij} = 1$ if $(i,j) \\in \\mathcal{E}$, then the $i^{\\text{th}}$ row of $\\mathbf{A}$ whether nodes *receive messages from* node $i$ (which makes the GCN definition in equation (1) wrong). Also, you should mention that $\\mathbf{D}$ is the in-degree matrix. Of course, all this can be avoided by assuming you're working with undirected graphs, but it will be more helpful to make the notation consistent for directed graphs.\n\n3. The estimation of topological compensation is arbitrary: Definition 4.1 requires $g$ to satisfy $\\mathbf{H}^{(l)}_{\\mathcal{N}\\_{\\mathcal{B}}^c} = g(\\mathbf{H}^{(l)}\\_{\\mathcal{B}})$, $\\forall \\mathcal{W}$, but the estimation of $\\mathbf{R}$ is based on a randomly initialized parameter set. Again, there is no validation for the claim that this method is \"very accurate\", since the evaluation is on a single set of (learned) parameters. I do see that an alternative protocol proposed is to update $\\mathbf{R}$ when the approximation errors increase, but that disagrees with Definition 4.1 (as I understand it, see questions).\n\n4. The assumption of topological invariance in the node representations seems to be very strong, especially for it to hold for all layers ($\\forall l\\in[L]$) and for all parameter sets ($\\forall \\mathcal{W}$). It is also not verified in real-world settings. Figure 2(a)-(c) show that the *final node representations* are close to the full-batch representations *at the end of training*, i.e. for the set of learned parameters, and for a single layer; the assumption behind the theoretical motivation is much stronger.\n\n5. About Figure 2, low relative error at the end of training is not sufficient empirical support for the claim of existence of invariance in node features; although, competitive performance on a range of benchmarks does provide a convincing argument. I recommend a rewording of the manuscript such that soundness is prioritized.\n\n6. It is very hard to figure out the exact algorithm behind TOP, eg. how $\\mathbf{R}$ is computed, partly because of the typos (see below for a non-exhaustive list). It becomes clear only in Section 5.1 (even then some questions remain). An algorithm block at some point might help with navigation, but I believe some restructuring is needed to improve clarity.\n\n7. The architectures presented in the main text -- GCN and GCNII -- do not represent a wide class of GNNs. It will be more convincing to move the results for one of GAT or GraphSAGE to the main text, and one of GCN or GCNII to the appendix.\n\n8. There is no discussion on the depth of the networks used in Section 6 -- since this method is designed to tackle the problem of exponentially growing neighborhoods, which is especially problematic when using deep networks for large graphs, it is important to understand how the performance is affected by the network depth.\n\n9. For long-range tasks (which are the primary targets for learning with deep GNNs), it is important to capture long-range information. Since TOP estimates the message-invariant transformation $\\mathbf{R}$ using only the input features of the batch-neighborhood, followed by message-passing with the 1-neighborhood of the batch, I believe it fails to capture any information from nodes 2-hops or further away (except, possibly, that learnt by $\\mathbf{R}$ during pre-processing).\n\n10. Since TOP is expected to have a fast convergence rate, I was hoping to see the plots of loss/accuracy against the number of iterations. The authors do present plots against physical time in Figure 3 and Figure 5, where TOP is competitive or much faster than other algorithms. However, Figure 4 shows that the per-epoch time of TOP is much smaller, implying that in the same physical time, it can get in more optimization steps. For that reason, I am interested in the plots of performance metrics against number of iterations or number of epochs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5jI66i3Fhl", "reviewer": "Reviewer_sVt9", "summary": "This paper presents a new strategy for message passing graph neural network applied to sub-graphs. The author defines a new way to approximate the contribution from out of bach neighbors from in batch neighbors. They demonstrate both the accuracy of their method and its speed of convergence through numerous experiments.", "questions": "- l18: \"stores most nodes on the GPU\" : in my opinion issues comes more from gradient descent on very large batch of edges rather than nodes?\n- l132: \"accelerates convergence\" with what speed? what complexity?\n- Why this choice of norm? Why not using the $p$-Shatten norm which is often used for demonstration related to optimization and matrixes norms.\n- l281: Did you made experiments by adding non-linearity in the formulation of $\\mathbf{R}$ ?\n- l308: How do you decide when to update the embeddings exactly? It would also be nice to add the improvements of accuracy when using updated embeddings in the experiments.\n- Can we study what $\\mathbf{R}$ looks like?\n- l792: Did you try any method related to points cloud such as FPS/FPS++ ?\n- Can't we remove $-\\mathcal{L}^{*}$ from the inequalities l1323 and below?\n\n**Changes**\n\n- the norm is never defined properly, or no mention of Frobenius is found\n- l26: \"without accuracy degradation\" : seems like it should be \"with limited accuracy degradation\"\n- I find the Figure 1 not very clear, especially without the explanations that come after. I think displaying more clearly the in and out of batch nodes would help a lot.\n- Range of integer are usually denotted as $\\llbracket 1, L\\rrbracket$\n- l187: It would be a nice addition to add a footnote that makes $\\mathbf{A}^k$ appears in the equality, to explain directly the neighbors explosion\n- l224: \"expensive costs of [out of batch] neighborhood embeddings\"\n- l264: Either spend some time to explain why the 2 equality can be considered an equality wrt. $\\mathbf{R}$, or change it to an approximation.\n- l292/3: Same, or replace \"same output\"\n- Theorem 5.1 l364 is not very well presented, especially regarding the assumptions. I know its surely about the page limits, but the theorem would benefit a lot from 4/5 extra lines for clarity. \n- The conclusion doesn't mention any limitations. \n- typo in \"hyperparameter\" l902\n- l944: the algorithm doesn't mention how and when recomputing embeddings and $\\mathbf{R}$\n- l1127: typo in the bold choice for the last 2 raws.\n- l1298: The introduction of $\\eta$ should also specify we choose  $\\eta \\neq 2/\\gamma$\n- l1318: Either add an extra line or a sentence about the re-ordering and telescoping\n\n**Additional comments**\n\n- I find the notation MP-IB, MP-OB a bit difficult to read in the manuscript. Wouldn't something like $MP_{\\text{in}}$ be easier?\n- I find the notion of \"basic\" embeddings not very well chosen. Just talk about sampled embeddings, or precise random embeddings if they were used before any training?\n- l234 - 244: it feels like we already had enough explanations regarding this and that it could be skipped or skimmed.\n- I am unsure about the organization of section 5. It feels like we want to read about the embeddings as fast as possible.\n- l286: $\\Delta$ is usually used for differences. It feels like the compensation could be mor easily understood as a boundary, and thus denote it $\\partial\\mathbf{A}$.\n- Section B.4 - l900: I think the section would benefit a lot from a few lines to remind what the proto-algorithm is.\n- Proof l1268-1274 is not very clear. It could really gain from more explanations.\n- l1476-1478 is not very clear. It could really gain from more explanations.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper is both well-written and well-organized. It finds a good balance between the theoretical settings, simple examples, detailed experiments and adding the necessary details in the appendix.\n\n- The idea of message invariance is simple while yielding impressive results.\n\n- The experiments regarding message invariance are comprehensive, with enough comparisons and demonstrate very impressive results.\n\n- More importantly, the convergence curves offer good results, in particular when knowing about the differences in loss of accuracy with the other methods.", "weaknesses": "- Some figures and explanations lack a lot of clarity\n\n- The comparisons with other methods lack more recent algorithms. It seems it would benefit a lot from 1 or 2 extra comparison with a more recent approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)