FIT-GNN: Faster Inference Time for GNNs that ‘FIT’ in Memory Using Coarsening
Authors: Shubhajit Roy
Hrriday Ruparel
Kishan Ved
Anirban Dasgupta
Venue: Accepted by TMLR ()

Abstract: Scalability of Graph Neural Networks (GNNs) remains a significant challenge. To tackle this, methods like coarsening, condensation, and computation trees are used to train on a smaller graph, resulting in faster computation. Nonetheless, prior research has not adequately addressed the computational costs during the inference phase. This paper presents a novel approach to improve the scalability of GNNs by reducing computational burden during the inference phase using graph coarsening. We demonstrate two different methods -- Extra Nodes and Cluster Nodes. Our study extends the application of graph coarsening for graph-level tasks, including graph classification and graph regression. We conduct extensive experiments on multiple benchmark datasets to evaluate the performance of our approach. Our results show that the proposed method achieves orders of magnitude improvements in single-node inference time compared to traditional approaches. Furthermore, it significantly reduces memory consumption for node and graph classification and regression tasks, enabling efficient training and inference on low-resource devices where conventional methods are impractical. Notably, these computational advantages are achieved while maintaining competitive performance relative to baseline models.

Published in Transactions on Machine Learning Research (03/2026)
FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening
Shubhajit Roy" Indian Institute of Technology Gandhinagar
royshubhejit@iitgnnocc.
Hrriday Ruparel* Indian Institute of Technology Candhinagar
tawidaag.rapprrekkiittg..mm
Kishan Ved
kishan. veriainneediiign.....
Indian Institute of Technology Gandhinagar
Anirban Dasgupta
anärbandg@iitgn.cm in
Indian Institute of Technology Gandhinagar
Reviewed on OpenReview: oppereveep net/ forum? id- 7yr7778
Abstract
Scalability of Graph Neural Networks (GNNs) remains significant challenge. To tackle this, methods like coarsening, condensation, and computation trees are used to train on smaller graph, resulting in faster computation. Nonetheless, prior research has not ade- quately addressed the computational costs during the inference phase. This paper presents a novel approach to improve the scalability of GNNs by reducing computational burden dur- ing the inference phase using graph coarsening. We demonstrate two different methods Extra Nodes and Cluster Nodes. Our study extends the application of graph coarsening for graph-level tasks, including graph classification and graph regression. We conduct extensive experiments on multiple benchmark datasets to evaluate the performance of our approach. Our results show that the proposed method achieves orders of magnilude improvements in single-node inference time compared to traditional approaches. Furthermore, it signifi- cantly reduces memory consumption for node and graph classification and regression tasks, enabling efficient training and inference on low-resource devices where conventional methods impractical. Notably, these computational advantages achieved while maintaining competitive performance relative to baseline models.
1
Introduction
Graph Neural Networks (GNNs) have demonstrated remarkable versatility and modeling capabilities. How- ever, several challenges still hinder their widespread applicability, with scalability being the most significant concern. This scalability issue affects both the training and inference phases. Previons research has sought mitigate the high training computation cost by using three broad categories of methods: Training every iteration on sampled subgraph Training on coarsened graph generated from coarsening algorithm 3. Training synthetic graph that mimics the original graph. Unfortunately, these smaller graphs only be utilized for training purposes and have not alleviated the computational burden during inference since the method mentioned above requires the whole graph during the inference phase. Consequently, for larger graphs, not only do inference times increase, but memory consumplion may also exceed limitations.
To mitigate the high computational cost associated with the inference phase, we decompose the original graph G into collection of subgraphs G. = {G1, "e.....Gr], This transformation yiclds substantial
"Equal contribution

---

Published in Transactions on Machine Learning Research (03/2026)
improvements in inference efficiency, achieving up to x00x speedup for single-node prediction. Moreover, it significantly reduces memory consumption by as much 100x -thereby enabling scalable inference on large-scale graphs comprising millions of edges. We provide a theoretical characterization of the upper bound on the expected size of subgraphs under which our method's time and space complexity remain superior to that of the baselines. Notably, we observe that conventional methods often fail to perform inference on large graphs due to memory constraints, whereas our approach remains effective and scalable in such scenarios.
While partitioning the graphs into subgraphs seems to be a naive transformation, it comes with the cost of information loss corresponding to the edges removed. We overcome this loss by appending additional nodes in the subgraphs using two different methods- - Extra Nodes and Cluster Nodes that respectively append neighboring nodes or representational nodes corresponding to neighboring clusters. These additional nodes resulted in equivalent or better performance in terms of accuracy and error compared to baselines. Our contributions are summarized as follows:
1. We reduce inference time and memory by applying graph coarsening to partition graphs into subgraphs, mitigating information loss through Extra Node and Cluster Node strategics.
2. We provide theoretical analysis of our approach, establishing lower inference computational complexity compared to baselines.
3. Our method scales well to extremely large graphs that baselines fail to process, while consistently deliv- cring strong performance on 13 real-world datasets.
Training GNN
Training FIT-GNN
Input
Coarsenins Alascithe
Loss
Loss
Weight I pulate
Weight Updatt
Sabgraphs Sequence
H
Ourpur
GYN Model
Model
GIN
Chipar
What is the prodiction for Nade f?
CNN Model
Modil
Outpat
Inferencing GNN
Inferencing FIT-GNN
Figure 1: The Figure shows the overall pipeline of our proposed method and its comparison with traditional training and inference of GNNs. This pipcline is made for node-level tasks.
2 Related Work
The aim of reducing computational costs has been approached through various methods. Research by
Chiang et al. (2019) and Zeng et al. (2020) uses subgraph sampling technique, where small subgraph is sampled at each training iteration for GNN training. Other methods, including layer-wise sampling
and mini-batch training, have been explored by Chen et al. 2018a b); Cong et al. (2020 : Zou et al. (0019)
Additionally, Fahrbach et al. (220)) introduced a coarsening algorithm based on Schur complements to create
ISGGC applied GNNs to coarsened graphs, reducing nodes and edges to lower training time. Kumarr al.
node embeddings in large graphs, while Huang et al. (2021)
(0023) Joly & Keriven (2024); Kataria et al.
(2024]: 3 Dickens et al.) )2024) also proposed different coarsening algorithms for scalable training approaches.
Jin et al. (2021) [GCOND] | Wang et al. (2024) [GC-SNTK] presented algorithms to generate synthetic graph that mimics the original graph. However, their approach generates model-specific synthetic graphs that require training on the whole dataset, which defeats the purpose of reducing computational burden. Gupta et al. (2225) [BONSA] addressed this issue by looking into computational trees and training on just. the relevant computational trees. However, these approaches do not docrease inference time since the inference phase takes the whole graph as input. Xue al. (2023) shifted the training process to subgraph- level, using coarsening algorithms to split the graph into k-subgraphs and recommending multi-device
2

---

Published in Transactions on Machine Learning Research (03/2026)
training approach. In the graph-level task, Jin et al. 2022 [DSSCON]] and Xu et al. 2023 KIDD
tackled the graph classification problem following up the approach of GCOND) and GC-SNTK. However, the graph regression problem was not explored in this direction.
3 Preliminaries
Given undirected graph G (V),,,,W) V is the vertex set, E is the edge set, X E Raxd is the feature matrix, and W is the edge weight matrix. Let =V|= be the number of nodes and E = m be the number of edges. Let A E R= be the adjacency matrix of G where Ai is the edge weight between nodes V; and R; and d; is the degree of the node v. DE Rax" is a diagonal degree matrix with ith diagonal element as d, We denote (1,) as the j-hop neighbourhood of node &q V. Graph Neural Network: Graph Neural Network is a neural network designed to work for graph-structured data. The representation of each node in the graph is updated recursively by aggregation and transforming the node representations of its neighbors. Kipl & Welling (2017) introduced Graph Convolutional Network (GCN) follows:
Graph Notations:
= - =(D (0000))))))))
(1)
where ( is the node representation after layers, Á = A + D = D
the identity matrix of same dimension A. Wi() is the learnable parameter and is non-linear activation function.
Graph Coarsening and Graph Partitioning: Loukas (019 discussed multiple coarsening algorithms which create a coarsened graph G' = (V', E', W')
from a given graph G = (V, E, X, W). We refer the vertex set V' = =fo 1/ ug..... v44} G' as coarsened nodes. Given a coarsening ratio E 1], we have Z. We can interpret it creating disjoint partitions, C₁ C2. ..... Ck. from a graph of n nodes. Mathematically, we create a partition matrix P {0, 1]nxk, where P. if and only if node o Cy. X' = - X is the coarsened node representation. A'= A corresponding degree mairix D' = P DP. SGGC (Huang al. 2021 b used normalized partition malrix P = PC- 2, where C' is defined as diagonal matrix with diagonal entries Cj [Cyl.j = 1.2...,
k = In rJ.
AP is the adjacency matrix of G'. Similarly, the
Along with G², we create a set of disjoint subgraphs G3 = [G1, ...., G&} corresponding to the partitions C₁, C2...., Cs. The number nodes in each partition C, is denoted by n,, Each subgraph G, is the induced subgraph of formed by the nodes in C.. A; and D; are the adjacency and degree matrix of G; respectively.
G.
G.
Cluster Nndrs
Extra Nodies
Ga
G:
Gr
G,
Figure 2: Figure showing the comparison between the Extra Node Method and the Cluster Node Method of appending additional nodes in G1, G2, G3.
4 Methodology
In SGGC, graph G reduced to G' using partition matrix P generated from the coarsening algorithm. The labels for the coarsened graph are y' arg max(PTY), where the label matrix of storing the one-hot encoding of the label of each node for the node classification task. Training carried out on
3

---

Published in Transactions on Machine Learning Research (03/2026)
the coarsened graph G' using Y' the label information. While this approach is novel, essential label information is lost. For instance, suppose a node v' E G" is combination of U2 0k E G where N;;"; th are test nodes. Let us assume that the classes of UG, ej, Uh are 0,0,2 respectively. arg max will take the majority label and assign class O to v'. Hence, the model will be trained to predict only the class 0, leading to the discarding of the quantification of the model's performance on predicting less represented nodes.
Similarly, explore another node-level task, such as node regression, aggregation functions such as the mean of regression targets wouldn't be appropriate because they lose the variance of the targets. To mitigate label information loss, thus motivating us to follow a subgraph-level training process.
original label information without any aggregation function like arg max or mean,
However, partitioning the graph inlo subgraphs leads to a loss of neighborhood information at the periphery of subgraphs. To tackle this, we append nodes in two ways after partitioning:
Extra Nodes: Adding the 1-hop neighbouring nodes, namely Extra Nodes, in each subgraph G. denoted by Ec.. Xue et al. (2023) introduced this approach to reduce information loss after partitioning. We add unit weight edge if two nodes in Eg. are connected in G. Node embedding of v E &g, is zv E X.
&a. = U (uEVV::EETE DEG,
G.).
(2)
Cluster Nodes: Although adding 1-hop neighboring nodes in the subgraph helps recover lost infor- mation after partition, for multi-layered GNN models, information loss will persist. Instead of adding the neighboring nodes, we will add Cluster Nodes, which represent the neighboring clusters, denoted by Ca.- Liu et al. (2024) introducod this method to add nodes in the graph instcad of adding to separate subgraphs. They also added cross-cluster edges among these Cluster Nodes and proposed a subgraph sampling-based method on the modified graph. In our work, add cross-cluster edges. For each node E Ca,, the node embedding =t
Ca.
U (t: #0, DEEa,
(3)
Figure [ ratustrates appending these additional nodes using these approaches. The dashed line shows which nodes are added as part of these additional nodes. For subgraph-level training, specifically for node-level tasks, the newly appended nodes do not contribute to the weight update as the loss is not backpropagated based on the predictions of these nodes. This is done since the appended nodes might contain information from the test nodes. Therefore, boolean array mask; is created for each subgraph G, such that True is set for nodes that actually belong the subgraph G; (not as an Extra Node or Cluster Node) and are training nodes; otherwise, False.
Lemma 4.1. Models with layer of GNN cannol distingwish belween G and G2 when Extra Nodes method is used. (Proof in Appendir A.1
Using the Cluster Nodes approach to append additional nodes to subgraphs is better for two reasons:
From Equation 2 and 3 can say that E, 1E,,1 2 Ca, This is because, using Extra Nodes, we add all the neighboring nodes. However, using Cluster Nodes, we only add one representative node for each neighboring cluster. Hence, the time taken to train and infer these modified subgraphs with Cluster Nodes is at most that with Extra Nodes.
Lemina 4.1 shows that the Extra Nodes approach reduces the information loss due to partitioning for 1 Layer of GNN. However, with multiple layers of GNN, longer dependencies are not captured. In contrast, the Cluster Nodes approach overcomes this by computing a single Cluster Node's representation as a combination of features of all the nodes present in the corresponding cluster. This results in sharing further node information 1-hop. Additionally, the transfer of information from one cluster to another is captured.

---

Published in Transactions on Machine Learning Research (03/2026)
Algorithm Training GNN (Train on 9,)
Require: G EV E) Labels Y; Node-Model M; Loss & Number of Layers L
1: Apply coarsening algorithm on G, and output normalized partition matrix P.
2: Construct G. = (V1, FL, X1), (22,, F2, X2)...... (V FL, Xx)} using P:
3: Append additional nodes then
4: Append Êg, Ca, each G.
Based method of appending nodes
5: end if
6: Coustruct mask for each subgraph Mask (maska, maska, on maskk);
7: Coustruct label matrix (Y1, Y2...., xx for 9s
8: < [: YClllected <
9: for each subgraph G; G. do
10: O M(, A,, Dj, X));
D Algorithm
11: O.append( O, mask(]);
12: YCallected appendd( Yj mask:]);
13: end for
14: Los8 = E(O, YCollected):
13: Train M to minimize Loss;
4.1 Node-level Task
We use Algorithm with L number of layers to create standard GNN model M for node-level tasks. While we use Algorithm 3 to train a model on the coarsened graph G', we propose Algorithm to train model on the set of subgraphs Gg. Algorithm D utilizes the partition matrix P generated by the coarsening algorithm to construct and train on the coarsened graph G' and the coarsened label information Y'. On the other hand, our proposed Algorithm [ uses the same partition matrix P to construct and train on subgraphs G, using original label information Y. For the node classification task, arg max is used for creating Y' for G' and CrossEn as a loss function. For the node regression task, we do not create G'. Mean Absolute Error (MAE) used as the loss function.
4.2 Graph-level Task
For given graph G E D, create G" and G. = I set of subgraphs, we use Algorithm 5 to create model that trains on G' and Algorithm 2 to create a model that trains on G.. We use the CrossEntropy loss function for the graph classification task and the Mean Absolute Error (MAE) for the graph regression task.
Since G' is a single graph and G, is a
Algorithm 2 Graph-Moodel-G
Require: G. = [G1, G2.....G. G+3; Number Layers I.;
1: X
+
2: for each subgraph G; E Go do
3: for j to L do
4: x(6) = (D, + A, D. + x 1)1-))
D. Equation
5: end for
6: X.stack(X(")) (1)
Stack along row axis
7: end for
8: X MaxPooling(X)
9: X
return
4.3 Time and Space Complexity
In Equation the matrix dimensions and w0 has dimensions (d d). Time complexity for one layer of GNN computation is O + nd)). If we take layers, then the total time OLLnd Lnd?). The space complexity is O( Lnd + Ld²). When we compute on sparse graph, the time complexity 0(m + Lnd?) and space complexity is O O m + Lnd + Ld).. The complexity is based on GCN. For other architectures like GAT (Veličković et al. 2018), the complexity changes.
follows: Ā has dimensions (n (n),,, X is of dimensions (n d).
5

---

Published in Transactions on Machine Learning Research (03/2026)
Table 1; Training and inference time and space complexity FIT-GNN compared to classical and SGGC approaches.
Time Complexity
(b) Space Complexity
Train
Inference
Train
Inference
Classical SGGC
nd + ndd
nd + n2d nd? n²d
Classical SGGC
n² + nd + de
n² + nd - d²
kd + k
1²2 + kd de
n² + nd - d²
kd2e + k2d
122 + kd + dl
FIT-GNN
D nndd + k.,"")
FIT-GNN
dl + max;= [7 R.dd]
+ >
RRdd R.
max Im? + 7zd0]
SGGC improved the time and space complexity (Table 1 for training the network by reducing the number of nodes from n to However, the inference time and space complexity remain the same.
Let us compare three different models. One is the classical model, where no coarsening or partitioning is done; the second is SGGC, where training is performed on smaller graph G' and inference G; the third is approach, FIT-GNN, where both training and inference performed on G..
The inference time complexity of our model is (E [ndd + n,dd)), where ñ; = n, + di and oi is the number of additional nodes appended in each subgraph. Table D compares different approaches.
Lemma 4.2. The inference time complerity O (Et + oi) (n: + di)dH1) is at most On nd²)
if Emm; + Φ.] S v _ + Var(n; + 6x) - 4, where E(n, + di) is the expected number of nodes in each modified subgraph and Var(n; + (b)) is the variance of number nodes in each modified subgraph.
Proof. We can expand our inference time complexity as follows:
k
(m4 d.) + (mg + o.)d ndd + dd
Σ
n + d
i=
Now, define expected number of nodes in each subgraph E[n]] 1 Σ n4 = = = (since k =n) and
expected number of additional nodes appended in each subgraph E[o:] == E di. We also define the variances and covariance,
k Σ n E(n,},, Var(ø.) = k 1=1
k -E(o,,
Var(n:) = 1:
Σ o.
Cov Φb) = Cov ==
Onn E(ds IE
7: i=1
We can also write,
k
Var(m:+ + (1)
Σ
(n: + oz)²
(E + B(o.1) = Var(n:) + Var(d:) + 2Cov(ns, (i)
1:
i=1
Using the definitions above, we can say:
k
4 +
Σ (n+ + 2.) (n4 + o,)d nd? +
Σ
n
+ Σ
Σ n + d
1=1
1=1
1=1
nal + d (k(Var(n,)) E(n.}?) + k(Var().) [(d,)3) + 24 2o:(Cooonii Φi) + E| [(bb]) + dkE[
1 - +Var( o 27Cor di) 2E + rdB[ = nd + nd >Var(n:) +
= ndd + nd
rB(os]] + (2 rd) + + Var(n: + ②2)

---

Published in Transactions on Machine Learning Research (03/2026)
Given, Elm; + Ø. S / + - far(;++0) E(Ø.] S
+ + =- -Varnn; + 0;) - -2 +
Using this, we can say the following:
(nn+ d (nt + oi)d nd + +nd rB]dd] (2 + rd) +Var + (z) 1
c
d
Var(m, + + + d2
1
d
2 ( d + / v
S nd + nd
+
+
+
+
4
r
r
4
p2
r
2 r
1
d
1
+2v
A
-
rdv rd
+
+ r Var(n;; + +i)
-
2
7)
2 /
d²
(where
+
+ n
Var(n; + *,)) = A)
4
= nd + 2
Hence, [i=1((n;+ + d (n, + S n2d + ndf [(n;
Corollary 4.3. E[Ø:] has positive upper bound when Var(n; + 6.) I " ,2
Proof. From Lemma 4.2 we know the upper bound of B(o.] is v
12 4
Var(n ( :)-
Tf
d2
Var(n; + +a) (5 + +) 2 O, then we can say the following:
4
d
d
( + 2 0
de
n d + r
d 1 + r
Var(n + +
Var(n, +0,)
)
4
r
Var(n; + +Ø))= 5
n
2
For a given graph, when the above conditions are satisfied, our approach has better inference time and space complexity than other approaches. From Corollary 4.3 we can understand that it is idcal to have similarly sized subgraphs. For more details on time and space complexity, refer to Section C in the Appendix.
5 Experiments
Let training on the coarsened graph G' be referred to as Gc-train, subgraph-level training as Gs-train, and subgraph-level inference process Gs-infer. Once we have constructed G' and Gs, train FIT-GNN in 4 different setups:
Ge-train-to-Gs-train Train the GNN model on G' as per Algorithm 3 then use the learned weight initialization for subgraph-level training and final inference on G.. We examine whether pretraining G' (which requires less time) followed by fine-tuning on G. for fewer epochs can improve performance.
Ce-train-to-Gs-iiffrr Train the GNN model on G' as per Algorithm 3 then infer on G, using the learned weights. We explore whether training solely on the G' is sufficient for inference on G.- This setting presents computationally efficient option, allowing users with limited resources to obtain results close to the best reported.
Gs-train-to--Gs-infor Perform subgraph-level training and inference on g..
Ge-train-to-Go-inffr. Unlike node-level tasks, for graph-level tasks, inference can be done directly on G' because the label corresponds to the entire graph and not to individual nodes. Therefore, even with reduced graph representation, meaningful inference is possible. Therefore, in this setup for graph-level tasks only, we train and infer on G'.
7

---

Published in Transactions on Machine Learning Research (03/2026)
All four setups can be applied to graph-level tasks. For the node classification task, we apply all setups except Pestrain-to-Ge-nnee For the node regression lask, we only perform -ssrinn-tt-G--nferr because a coarsened graph is not created for node regression datasets.
Dataset descriptions and details related to hyperparameters, device configuration, and key packages used for the experiments are in Section and Source code: ?
Boaaa/oooooSuuttt/iaFiiae FFIT-GNN
Table 2: Datasets and corresponding splits used in our experiments. 'c' denotes the number of classes in node classification datasets. Public split "fixed" by Yang et al. (2016) is used for Cora, Citeseer, and PubMed. For the "random" split, we use 20 nodes per class for training, 30 per class for validation, and the rest for lesting. For QM9, we follow Gilmer et al. (0117) and predict one property from each broad category: dipole moment (n), HOMO-LUMO gap (EHOMO ELUMO), zero-point vibration energy (ZPVE), and atomization energy (UO) at 298.15K.
Task
Dataset (Reference)
Train
Val
Test.
Chameleon Rozemberezki et al.
2021
30%
20%
50%
Node Regression
Crocodile Rozemberczki al. Squirrel
2021
30%
20%
50%
Rozemberezki et al.
2021
30%
20%
50%
Cora
MMcClllu et al.
2000
20 x c
30 x
Rest
Citeseer Giles et al..]
1998
20 c
30
Rest
Pubmed Sen et al.
2008
20 x e
30 x c
Rest
Node Classification
Couuthor Physics
Shchur
2018
e
30 x
Rest
DBLP (Tang et al.
2008
20 x
30 x
Rest
OGBN- Products
Hi et al.
2020
x e
30 x
Rest
QM9 Wu et al.
2018
50%
25%
25%
Graph Regression
ZINC (Sabset)
Bonbaaell et al.
2018
50%
25%
23%
PROTEINS Morris et al.
2020
50%
25%
25%
Graph Classification
AIDS Morris et al. 2020
50%
25%
25%
6 Result and Analysis
6.1 Model Performance
Table 4 shows the results for node classifi- cation accuracy (mean and standard deviation of the top 10 accura- cies) with coarsening ratios 0.3 and 0.5 using the Cluster Nodes approach. Comparison with other coarsening ratios in Table 12 Results show that the accuracy is comparable the baselines. Fig- ure 3eewshww the comparison of performance between different experi- mental setups for different methods of appending nodes on the Cora dataset. From the Figure, we observe that Cettrriinnt----tralll offers the best result among the three experimenaal setups for the node classification task. For the 'None' method of appending nodes, where no additional nodes are added to cach subgraph, we notice that it performs poorly compared other methods, indicating that the Extra Node and Cluster Node methods indeed provide additional information for better empirical perfor- mance. We also observe in the 'None' method that, with an increase in the coarsening ratio, the performance drops. This is because, as the coarsening ratio increases, the size of cach subgraph gets smaller, hence more edges are cut due to partitioning, leading lo more information loss. For the Ge-train-to-GG-innee method, we observe that the performance drops as the coarsening ratio increases. This can be argued because of the change the distribution of the coarsened graph and the set of subgraphs. When training on G,, the distribution in the train and test sets is similar, hence attaining better performance. While comparing the methods of appending nodes, infer that the Cluster Node method is performing similarly compared to
Node Classification:
Table 3: Results on OGBN-Products, FIT-GNN model uses a coarsening ra- tio 0.5. variation_ meairionnneiggbohhoodsd coarsening algorithm used. 00M means Out Of Memory.
Full [Lno al. 2024 SGGC
0.823 + 0.001
OOM
GCOND BONSAI
00M
0OM
FIT-GNN
0.894
0.000
8

---

Published in Transactions on Machine Learning Research (03/2026)
Table 4: Results for node classification tasks with accuracy as the metric (higher better). We use the Cluster Nodes method append additional nodes subgraphs and Gs-train-to-Gs-infer experimental setup. variation neighborhoods coarsening algorithm is used.
Methods
Models
Reduction
Dataset
Ratão (r)
Come
Chleseer
Pabmed
DBLP
Physica
GCN
1.0
0.821 + 0.002
0.706 + 0.002
0.768 + 0.020
0.724 +: 0.002
0.933
0.000
Full
GAT
1.0
0.809 + 0.004
0. 7.700 + 0.003
0,740 + 0.004
0.713 +: 0.004
0.909 + 0.008
0.3
0.808 + 0,003
0. 0.700 + 0.001
0.773 = 0.002
0.737 :: 0.011
0.928 = 0.003
GCN
SGGC
0.5
0.808
0.001
0.716 0.002
0. 793 0 002
0.733 0.008
0.931 + 0.004
0.686 0.010
0.635 0.021
0.773 :: 0.002
0.626 0.028
0.870 0.016
GAT
0.5
0.641 0.026
0.633 0.024
0.683 0.024
0.604 0.047
0.842 + 0.018
0.806 0.003
0.722 0.001
0.779 = 0.002
0.748 0.001
0.876 0.011
GCN
GCOND
0.808 0. 0.004
730 + 0.007
0.773 = 0.004
0.755 0.002
0.804 + 0.005
GAT
0.3
0.5419 0. 0,080
0.628 0.095
0,370 = 0.079
0.481 0.034
OOM
0.059
0.501 0.085
0.400 + 0.044
0.464 0.030
OOM
0.722 0.011
0.585
0.003
0.538 = 0.103
0.683 = 0. 0.039
0.798 = 0.007
GCN
BONSAI
0.701 0.012
0.001 0.666
0.670 0.084
0.049
0.832 0.016
GAT
0.6 0.680 0.014
0.566
0.003
0.540 = 0.096
0.665 0.027
0.791 = 0.010
0.006
0.579 0.004
0.523 0.133
0.681
0.025
0.812 0.016
0.3
0.800
0. 003
0.679 + 0.003
0.754 + 0.001
0.786 +: 0.001
0,82 = 0.000
GCN
FIT-GNN
0.5
829
0.002
D. 0.668 + 0.003
0,761 = 0.004
0.700 ::000::0 0.001
0.926 - 0.000
0.3
0.761
+ 0.001
0. 0.655 0.005
0.754 = 0.002
0.771 # 0.002
0.885 = 0.004
GAT
0.5
0.792 + 0.003
0.669 + 0.004
0.760 + 0.003
0.720 0.002
0. 0.885 + 0.003
FTT CNN Perforance acress Ciffercnt Experimental Setups, Additional Node Types and Coarsening Ratios Dataset Cora, Coarsening Method - Varist on Nelghborhaods
0.3
Top Aetuney
0.53
Rone
Eotra
Dhutter
Mbre
Extra
Custer
None
Eabra
Ouattr
infer
jnfor
Figure 3: The plot shows the ablation study conducted on the Cora dataset to determine which experimental setup performs better than the others. The plot also compares different methods of appending nodes to the subgraphs and how performance changes with varying coarsening ratios. variation neighborhoods coarsening algorithm is used.
the Extra Nodes method, if not better. Table 3 shows results on the OGBN-Products dataset. We use the result by Luo et al. (2024) for the full graph setting, which used the OGBN's standard split, while the split used in our work is detailed in Table 2
9

---

Published in Transactions on Machine Learning Research (03/2026)
Table 5: This table shows the normalized MAE loss (lower better) for node regression task on dif- ferent datasets with GG--ine experiment setup and Cluster Nodes method. varia- tion neighborhoods coarsening algorithm is used.
Dataset
Methods
Models
Reduction Ratio (r)
Chamelcon
Crocodile
Squirrel
GCN
1.0
0.852 1: 0.001
0.854
0.000
0.802 0.000
Full
GAT
1.0
0.846 + 0.002
0.850
0.000
0.805 +: 0.001
SAGE
1.0
0.848
0.002
0.850
0.000
0.804 0.000
GIN
1.0
0.843 1. 0.000
0.852
0.000
0.796 T 0.000
0.1
0.496 + 0.005
0.364
0.001
0.663 0.003
0.3
0.531 + 0.006
0.369
0.002
0.682 + 0.002
GCN
0.5
0.531 + 0.004
0.371
0.001
0.722 0.002
0.7
0.536 + 0.009
0.368 0.003
0.696 0.002
0.1
0.582 +: 0.029
0.395 D. 0.022
0.734 + 0.019
0.3
0.537 + 0.021
0.383 = 0.020
0.724 = 0.020
GAT
0.5
0.556 + 0.018
0.386 0.018
0.728 + 0.023
FIT-GNN
0.7
0.576 + 0.018
0.395 0.012
0.746 + 0.020
0.1
0.506 + 0.006
0.309 = 0.014
0.589 = 0.003
0.3
0.489 + 0.003
0.315 = 0.001
0.602 + 0.008
SAGE
0.5
0.484
0.004
0.317 0,001
0.618 0.002
0.7
0.539 + 0.009
0.323 0.000
0.621 + 0.004
0.1
0.769 + 0.101
0.722 0.098
0.795 + 0.018
0.3
0.808 + 0.056
0.697 = 0.122
1.796
GIN
0.5
0.810 = 0.062
0.730 0.091
0.786 + 0.032
0.7
0.792 1 0.089
0.779 0.102
0.791 1 0.009
Node Regression: Table presents the node regression error (mean and standard deviation of the lowest 10 MAE). Interestingly, our results demonstrate that utilizing localized subgraphs for inference (FIT-GNN) significantly improves performance compared to full-graph inference. To investigate this counterintuitive performance leap, we conducted a rigorous ablation study (Appendix G Our analysis indicates that this improvement is driven by the structural properties of the input data during inference rather than the training regime itself. First, partitioning the graph creates localized contexts that statistically more homogencous; we observed that the label standard deviation within individual subgraphs is drastically lower than the global variation, presenting a simpler optimization landscape for the model. Second, while coarsening (e.g., at a ratio of r = 0.5) causes a vast majority of nodes to lose a significant portion of their distant 2nd-hop neighborhood, this structural loss actually acts as implicil adversarial pruning. In these specific heterophilic graphs, long-range information often introduces noise or adversarial signals. By filtering out this noise through coarsening, the model able to fully exploit the low-variance local structures, ultimately leading to the observed reduction in regression error.
Graph Regression: Table t shows the results for the graph regression task on ZINC (Subset) and QM9 dataset. All the results show that the FIT-GNN model's performance is better than the baselines. It is also observed that a lower coarsening ratio yields better loss, which implies that the model performs better on molecular graphs when the subgraph size is large. We observe that finer subgraphs lose out on global information about the molccule, which necessary for the prediction. Similarly, the performance degrades in the Gc-train-to-Ger Go--frr setup, where we infer on the coarsened graphs. This is because, when graph is reduced to a smaller graph, the individual node information is lost, which is crucial since, in graphs representing different molecules, components formed by different atoms result in different properties of the molecule.
Graph Classification: Table shows graph classification results on AIDS and PROTEINS datasets, where training and inference are done on G'. For basclines like DOSCOND and KIDD, we use 'Graph per class", whereas we use 'Reduction Ratio (r)' as a metric to denote how these algorithms reduce the size of training data. DOSCOND and KIDD propose to generate synthetic graphs that mimic the training data distribution.
10

---

Published in Transactions on Machine Learning Research (03/2026)
Table 6: Results on Graph Regression with MAE as metric (lower better); We use Extra node and Gs-
train-to-Gs-infer as experimental setup. variation cetrrion_nnigbbohhoode coarsening algorithm is used.
Dataset
Methods
Models
Reduction Ratio (r)
ZINC (Subsct)
QM9 (a)
QM9 (Aej
QM9 (ZPVE)
QM9 (UATOMM)
GCN
0.855
1.073
GAT
1.066
Full
SAGE
10
0.685
0.885
L015
1.109
1.076
GIN
0.748
0.925
L.033
1.126
1.078
0.1
0.625
0.713
1.223
0.447
1.223
GCN
0.3
0.573
0.708
0.975
0.473
1.220
0.5
0.645
0.702
1.153
0.485
1.179
0.7
0.651
0.715
1.189
0.456
1.240
0.1
0.574
0.705
0.940
0.464
0.524
0.3
0.652
0.708
1.066
0.528
0.564
GAT
0.5
0.620
0.693
1.227
0.475
0.561
FIT-GNN
0.7
0.703
0.1
0.735
0.726
0 739
0.526
0.905
SAGE
0.3
0.671
0.748
0.711
0.602
0.588
0.5
0.695
0.739
0.747
0.606
0.833
0.7
0.645
0.722
0.677
0.659
1.005
0.644
0.726
0.746
0.494
0.856
GIN
0.723
0.761
0.854
0.5
0.631
0.725
0.848
0.737
1.058
Therefore, to cover all the graphs in the dataset appropriately, this approach generates {1, 10, 50} graphs per class. However, the graph size kept similar to the graph size in the training set. These approaches also don't cover the test set. Compared to these basclines, our approach transforms each graph into set of subgraphs and a coarsened graph based on reduction ratio. As a result, each graph in the training set and test set gets reduced. From our results, we see that FIT-GNN outperforms all the baselines.
Table 14 and 15 present the ablation study on various coarsening algorithms for all the aforementioned tasks. variation_nnighborhoone neighborhoods coarsening algorithm yields consistently
From the results, we observe that variation better results compared others.
Table 7: Results on Graph Classification with accuracy as metric (higher is better). We use the extra nodes method and Ge-train-to-Ge-infer as experimental setup. algebraic JC coarsening algorithm is used.
Methods
Models
Graph per class
Dataset
Methods
Models
Reduction (r)
Datasel
AIDS
PROTEINS
AIDS
PROTEINS
GCN
1.0
0.788
0,710
GCN
10
0.666
0.647
Full
1.0
0.802
50
0.518
0.656
SAGE
1.0
0.770
0.813
DOSCOND
1.0
0.800
1
0.608
0.652
0.1
0.810
0.783
50
0.729
0.657
GCN
0.3
0.5
0.844
0.836
0.696
K26
1
0.389
0.416
0.7
0. 0.793
0.783
GCN
10
0.236
0.659
0.784
GAT
0.3
0.793
0.522
1
0.441
0.416
0.810
GAT
10
0.225
0.685
FIT-GNN
0.7
0.739
0.522
KIDD
50
0.218
0.671
0.793
SAGE
0.3
0.828
0.696
0.793
SAGE
10
0.361
0.650
0.7
0.819
0.526
50
0,283
0.673
0.1
0.819
0.652
GIN
1
0.759
0.412
GIN
0.3
0.5
0.828
0.793
0.783
0.178
50
0.634
0.674
0.7
0.819
0.739
11

---

Published in Transactions on Machine Learning Research (03/2026)
6.2 Inference Time and Memory
As mentioned in Section 4.3 our inference lime is less than the standard GNN if certain conditions are met. In Table [aa and 8b we club all baseline models into one, since all baselines are inferred on the whole graph. We empirically show the reduction time and space by our FIT-GNN model during inference. For recording the inference time, we use the Python time package to calculate the difference in time before and after the inference step. In Table Sa we show the average time to predict for 1000 queries (Prediction for
Table 8: Inference time (sec) (Lower is better) comparison for Node-Tevel tasks and Graph-Tevel tasks. We show single-node prediction time using two different coarsening ratios for Node-Level tasks. Here, used Cluster Nodes. We used Ge-train-to-Gc-infer experimental setup for the graph-level tasks.
(a) Node-Level Tasks
FIT-GNN
(b) Graph-Level Tasks
Dataset
Baselines
0.1
0.3
FIT-GNN
Chameleon
0.0027
0.0016
0.0014
Squirrel
0.0081
0.0017
0.0014
Dataset
Baselines
0.3
r 0.5
Crocodile
0.0070
0.0015
0.0015
ZINC (subset)
0.00184
0.00184
0.00190
Cora
0.0026
0.0019
0.0020
QM9
0.00173
0.00180
0.00191
Citeseer
0.0031
0.0018
0.0019
AIDS
0.00163
0.00155
0.00163
Pubmed
0.0012
0.0019
0.0018
PROTEINS
0.00165
0.00160
0.00163
DBLP
0.0063
0.0020
0.0018
Physics Couuthor
0.0252
0.0020
0.0017
OGBN-Proce Products
0.1762
0.0017
0.0016
GPU Memory (MB, log stale)
10a
LDFIT-GNN r == 0.1
UDFIT-GNN r= 0.3
UDFIT-GNN r= 0.5
DDFIT-GNN 0.7
lo
Baseline
109
10
Chamclcea
Crocodilc
Squizrel
Cora
Citeseer
Pubmed
DBLP
Plysies
OGBN
Dataset
Figure 4: GPU memory consumption in MegaBytes (MB) (log scale) for FIT-GNN (Cluster Node) at different reduction ratios and Bascline, during inference. Citrationnneggbborboe
coarsening algorithm is used.
Node 0;) in the Baseline and FIT-GNN models for node regression and classification tasks. The baseline model processes the entire graph, increasing inference time, especially for large graphs. In contrast, the FIT-GNN model only requires the relevant subgraph, resulting faster predictions. For larger datasets like OGBN-Products, baseline inference not feasible with our computational capacity. Therefore, to show comparison, we take subset of OGBN-Products with 165000 nodes and 4340428 edges with respect to which we up 100x speedup in inference time. Section [ elaborates more the inference time for datasets with larger number of nodes. Traditional methods fail to infer for very large datasets due to memory constraints. However, our approach enables inference on the whole graph. Figure g and Table 13 show the detailed comparison of memory consumplion for different datasets for both Extra Nodes and Cluster Nodes methods, along with the baseline memory, which highlights that the FIT-GNN model uses up 100x less memory than the Bascline. Figure T shows the time taken to coarsen for different coarsening ratios for the Cora dataset. As the coarsening ratio increases, the time also increases, since the number of subgraphs increases.
12

---

Published in Transactions on Machine Learning Research (03/2026)
Table 8b compares the inference time of graph classification and graph regression tasks. We predict for randomly selected 1000 graphs from the test split. The table shows how our method is comparable and sometimes faster than the Baseline. Also, we observe that the inference time increases with a higher coars- ening ratio. Because with a higher coarsening ratio, the number of nodes G' increases, resulting in more edges. Overall, the inference time and memory for all the lasks mentioned are drastically less than the basclines while maintaining the performance.
7 Conclusion
In this paper, have focused on inference time and memory and presented way to utilize existing graph coarsening algorithms for GNNs. We have provided theoretical insight corresponding to the number of nodes in the graph for which the FIT-GNN model reduces the time and space complexity. Empirically, we have shown that our method is comparable to the uncoarsened Baseline while being orders of magnitude faster in terms of inference time and consuming a fraction of the memory. Future directions include extending the FIT-GNN mothodology to dirccted, weighted, heterogencous, and temporal graphs, alongside tackling data- intensive real-world challenges like weather forecasting. Theoretically, we aim quantify the information loss for the Cluster Node method, investigate its connection to Extra Nodes, and explore novel strategies beyond both to further mitigate graph partitioning loss.
8 Acknowledgment
Anirban Dasgupta acknowledges the support by SERB MATRICS and SERB CRG grants and the support from N Rama Rao Chair Professorship.
References
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942 122-500. PMLR, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An ef- ficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 257 266. Association for Computing Machinery, 2019. ISBN 9781450362016.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, pp. 1393-1403. Association for Computing Machinery, 2020. ISBN 9781450379984.
Charles Dickens, Edward Huang, Aishwarya Reganti, Jiong Zhu, Karthik Subbian, and Danai Koutra. Graph coarsening via convolution matching for scalable graph neural network training. In Companion Proceedings of the ACM Web Conference 2024, WWW '24, pp. 1502-1510, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400701126. doi: 10. 10.1145//5899335.6665 365199. URL https: //doi 1tt.1111533593338 3651920
Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, and Chi Wang. Faster graph em- beddings via coarsening. In international conference on machine learning, pp. 2953 2963. PMLR, 2020.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citescer: an automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, DL '98, pp. 89-98. Association for Computing Machinery, 1998. ISBN 0897919653.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 2263-1277 Pmlr; 2017.
Rafael Cómez-Bombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Looato, Benjamín Sänchez-Lengeling Dennis Sheberla, Jorge and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268 276, 2018.
Timothy D Hirzel, Ryan P Adams,
Mridul Gupta, Samyak Jain, Vansh Ramani, Hariprasad Kodamana, and Sayan Ramu. Bonsai: Gradient- free graph condensation for node classification. In The Thirteenth International Conference on Learning Representations, 2025.
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 Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20. Curran Associates Inc., 2020. ISBN 9781713829546.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD 221, pp. 675 684. Association for Computing Machinery, 2021. ISBN 9781450383325.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In International Conference on Learning Representations, 2021.
Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge ACM, August 2022. doi: 10.1145/ 10.1145/3534678.38 3534698.3539429
Discovery and Data Mining, KDD '22 pp.
URL http::/dp.dc.cc doi www.dd........oo.e 1eeeee111/3334460 3539999
Antonin Joly and Nicolas Keriven. Graph coarsening with message-pasingg guarantees. Advances in Neural Information Processing Systems, 37:114902 114927, 2024.
Mohit Kataria, Sandeep Kumar, and Jayadeva. Uge: Universal graph coarsening. In A. Glober- son, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Ad- vances in Newral Information Processing Systems, volume 37, pp. 63057 63081. Curran As- sociates, Inc., 2024. URL https://prroceednggs neurips cc.ppperrcppprr...pmpp wttpcppp.eilleee/eeeeeeaaaacpepe fiees//pper/200///iee 7330000f000777777777fffff.0..010 orgp://cceeooooooroeoeeeoee-eeer wonferenceeeeeeoooooonooooo
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.
Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar. Featured graph coarsening with similarity guarantees. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learn- ing, volume 202 of Proceedings of Machine Learning Research, pp. 17953-1191 77953-17975. PMLR, 23 29 Jul 2023.
Juncheng Liu, Bryan Hooi, Kenji Kawaguchi, Yiwei Wang, Chaosheng Dong, and Xiaokui Xiao. Scalable and effective implicit graph neural networks on large graphs. In The Twelfth International Conference on Learning Represenlations, 2024.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20(116):1 42, 2019.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic GNNs are strong basclines: Reassessing GNNs for node classification. In The Thirty-eight Conference on Neunal Information Processing Systems Datasets and Benchmarks Track 2024. URL http::///ggaaaciiiaeeee///mmm/mr
14

---

Published in Transactions on Machine Learning Research (03/2026)
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the con- struction of internet portals with machine learning. Information Retrieval, 3(2): 163, Jul 2000. ISSN
1573-7659.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop Graph Represenlation Learning and Beyond (GRL+ 2020), 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 92)) 2021.
Prithviraj Sen, Galileo Namala, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collec- tive classification in network data. Al Magazine, 29(3):93, Sep. 2008.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference Knowledgge Discovery and Dala Mining, KDD '08, pp. 990 998. Association for Computing Machinery, 2008. ISBN 9781605581934.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio, Graph attention networks. In International Conference on Learning Representations, 2018.
Lin Wang, Wenqi Fan, Jiatong Li, Yao Ma, and Qing Li. Fast graph condensation with structure- neural tangent kernel. In Proceedings of the ACM Web Conference 2024, pp. 4439 4448, 2024.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Ancesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, (12):513-530,, 2018.
Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hanghang Tong, Kernel ridge regression-based graph dataset distillation. In Proceedings of the 29th ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, KDD '23, pp. 2850 2861, New York, NY, USA, 2023. URL
Association for Computing Machinery. ISBN 9798400701030. doi: 10.1145 00144/5/558005.35599 3599398.
https://doi.org// 10. http://...rrrr...11///5588888330 /155/1140355 3599398
Zihui Xue, Yuedong Yang, and Radu Marculescu. Sugar: Efficient subgraph-level training via resource-aware graph partitioning. IEEE Transactions on Computers, 32(11):3167-311 2023.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML'16, pp. 40 48. JMLR.org, 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representa- tions, 2020.
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. Tn Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 11249 11259, 2019.
15

---

Published in Transactions on Machine Learning Research (03/2026)
Appendix
A More on Extra Nodes and Cluster Nodes
A.1
Extra Nodes
Lemma 4.1
Models with layer of GNN cannot distinguish between G and 93 when Extra Nodes method
is used.
Proof. There are sets of nodes G2 as follows:
The set of nodes with 1-hop neighbours in Ge.
The set Sn of nodes with not all 1-hop neighbors in G2
Let 7 be the nunber of nodes whose information does not get passed after 1 layer of GNN for G,
- U M v(G))
BES2
Now;
U {uE (uEV: G+)=00 =0
JES:
Also, Ec.
U {ue (() G
vESp
Ec, Iz
Hence, when Extra Nodes is used, Layer GNN model cannot distinguish and G..
To undorstand the information loss when taking Layers of GNN, we divide G3 into 3 sets nodes.
S₁= Nodes with 1-hop and 2-hop neighbours in Gi.
Sy: Nodes with 1-hop neighbours in G₁ but Eu in 2-hop neighbourhood that not in G,.
Sz: Node where Ee in 1-hop and 2-hop neighbourhood that is not in G,,
Let 7 be the number of nodes whose information doesn't 't get passed on after 2 layer of GNN for G..
I
U (2(e) V(G.) BESa
When we use Extra Nodes, the information loss can be written as follows:
z = U N2(1) - V(G.) Ea, UvE
The above entity will depend on the density of the subgraphs formed and the number of connections cach subgraph shares with each other. An algorithm with an objective to reduce this entity for all subgraphs will lose the least. amount of information when Extra Nodes method is used.
16

---

Published in Transactions on Machine Learning Research (03/2026)
A.2 Cluster Nodes
Given partition matrix P, the features of the coarsened node are X' PTX. Given normalized partition matrix, the features of node v E G' is the one of the functions f used to create the features of the clustor node from C..
average of the features of nodes in C. This is
Previously, according to Lemma there is no information loss when using the layer of GNN and Extra Nodes method. It was also easy quantify in terms of the number of nodes. However, it is different for Cluster Nodes. Let discuss the issues first.
Only weighted version of node information is shared with the subgraph. Suppose vey Ua E G; is connected to ta tb E Gy. Then the information contributed by these nodes is du duzytdsra Here dp represents the degree of node Up, and Tp represents the feature of node Upp-
2, dp
Other node information will also be shared which is Ep dp
This will capture further dependencies.
E,
The performance of Cluster Node will depend on some distance or similarity metric between Tes Fa and f(C)).
B More Algorithms
Algorithm 3 Training GNN (Train on G') (Hang et al.) 2021
Require: G= (V. E, X): Labels Y; Node Model M; Loss & Number of Layers I
1: Apply coarsening algorithm on G. and output normalized partition matrix P.
2: Construct Coarsened graph G' using P;
3: Construct feature matrix for G' by X PTX; X;
4: Construct labels for G' by Y arg m Y):
5: (L, A', A','',X')
Algorithm
6: Loss = (OOYY);
7: Train M to minimize Loss;
Algorithm 4 Node-Model(L, A,
Require: Number of Layers A; D; x
1: == 1
do
2: X a A - (1((1)
Equation
3: end for
4: = (())
5: return Z
Algorithm 5 Graph-Moodel-"((LAA A','', X')
Require: Number of Layers A'; D'; x²
1: for 1 to do
x()==o(Dr 2
2:
b Equation
3: end for
4: X MaxPooling (2))
5: Z = (W)(4
6: return Z
C More on Time and Space complexity
C.1 Comparison with Baseline
In Lemma
4.2 provide the conditions that need be satisfied for better space and time complexities.
17

---

Published in Transactions on Machine Learning Research (03/2026)
For node-level tasks, to obtain lower FIT-GNN inference time complexity as compared to classical GNN, want the following as per asymptotic analysis,
Baseline vs. Single-Node Inference:
Ti nd
max m d n.d
(4)
Basellnn Complexity
FIT-GNN Complexity
Baseline vs. Full-Graph Inference:
n&d+ + nd
[m: + 6.) (n, + o.)
(5)
Bazeline Complexity
PIT-GNN Complexity
Feasibility Analysis on Different Datasets for Different Coarsening Rat Coarsening Method: veriation_ neiighburhoods
cor Graph Infenene))
Gragh inferenca)
pubmedd (ful Grach inferecee
3Nc (ful Grach infrreze)
2X.12M
3+330
Oor perpatnn
3
069
12"
10"
3-110
Coppestiin 022
654107
1274 (Gingle hode Interence)
Cherser (Sigle Node intermne)
24bmed (Single Nize Intwenoe)
d2b (Singl Node Infernnc))
Eaoire
1417
10
12"
30'
30
107
10'
30
10
25
18"
10
Styge
(Sigle
(Siggle
30-
127
30t
Coarses 0g.00
Figure 5: The figure shows the feasibility of inference methods for different node-level dutasets against coars ening ratios. Two important inference setups for each dataset: single-node inference with the computational cost
(max;(mn 2d ni ) + n), and full-graph inference with computational cost O [ (ni + nn,))) are compared against the baseline (classical GNN) computational cost of O (n"2 + ndd). The coarsening method used is varia- tion. neighborhoods. Both axes are logarithmic scale (base 10).
18

---

Published in Transactions on Machine Learning Research (03/2026)
Figure 5 demonstrates the feasibility of our FIT-GNN method for different coarsening ratios with regards to full-graph inference time complexity. We empirically compute the LHS (baseline is classical GNN) and RHS of the Inequality | and 5 for various coarsening ratios and plot the results for multiple datasets. The coarsening algorithm used is variation__eighbootie
We make the following inferences:
1. There is clear dataset-dependent computationnll-oss trade-off across different coarsening ratios. Moreover, the minimum inference time for our approach occurs at different coarsening ratios for different datasets.
2. Under single-node inference setup, FIT-GNN demonstrates increasingly superior inference lime per- formance as compared to classical GNN with increasing coarsening ratio. This is because the indi- vidual subgraph sizes decrease with increasing coarsening ratio.
We observe lower inference time complexity of Cluster Node method as compared to Extra Node method under both inference sctups. This is expected as |Ca, S |Ea,1, Vi E (I,)....,k).
C.2 Preprocessing Time Complexity
A comparative analysis of our preprocessing (coarsening) overhead against other state-of-the-art scaling methods has been conducted. As shown in the Table 9 below, our preprocessing time complexity is compa- rable to, and often faster than, existing SOTA methods. Thus, even when end-to-end latency is considered, FIT-GNN maintains efficiency advantage.
Table 9: Asymptotic time complexities for different methods. N is the number of nodes in the original graph, M is the number of edges and C is the number of classes; rest of the symbols follow notation defined in Section 3 and 4 Blue and Red indicate CPU and GPU respectively the hardware used for computation. Full Graph setup indicates testing on all the test nodes in graph while Single Node setup represents testing for a single test node.
Method
Preprocessing
Training
Inference (Full Graph)
Inference (Single Node)
Model-Agnostic
SGGC
M N
Add kd
N'd Nd
N'd Na
C(N2 + 1P)d +C(N + k)d
GCOND
IPd kd
Nad+ Nd
Nad Na
BONSAI
M M+N N
1dd kd?
Nºd No
N + Nd
kd k2d
FIT-GNN
M+N
+ E (edd
ΣL Si m.d
max,(nçd n.d")
We further extend our complexity analysis the practical scenario, where new test node is introduced to the graph G. This setting is critical for real-world applications where graphs evolve dynamically. We compare three distinct inference strategies for this new node:
Full Graph: Construct Gnew by adding u to the original full graph G and infer on Gnew using the pre-trained network.
Sample only the 2nd-hop neighborhood of from and infer using the pre-trained network (assuming 2-layer architecture).
2nd-hop Neighborhood:
FIT-GNN Subgraph: Assign a a relevant subgraph G; (e.g., the one containing the majority of its 1st-hop neighborhood) and append the necessary Extra /Ctuter nodes. Inference is then performed strictly within the modified subgraph G;
We present the time complexity comparison for these methods the Table I0 below. The most significant advantage of the FIT-GNN approach that inference complexity depends solely on the subgraph size n; (ng & n). In contrast, the Full Graph approach remains tied the global parameter n due the necessity of accessing the full adjacency matrix.
19

---

Published in Transactions on Machine Learning Research (03/2026)
Table 10: Time complexity of different inference strategies when a new node v is added to graph G
Inference Strategy
Preprocessing Complexity
Inference Complexity
Notes
Full Graph
O(1)
O("'d + +dd))
Computationally expen- sive; requires processing the entire graph for one new node.
2nd-hop Neighborhood (VV()))))))
(
[V(()] is the number of nodes in J-hop neighbor- hood. A is the maximum degree in graph.
FIT-GNN Subgraph
O(k)
Assuming has maximum neighhors in G; which has many nodes.
Dataset Description
(a) Summary of datasets used for Graph classification
(b) Summary of datasets used for Graph regression
Dataset
Number of Average
Graphs
Nodes
Average
Edges
Features
Classes
Dataset
Number of Average
Graphs
Nodes
Average
Features
Number of Targots
PROTEINS
1113
72
Q49
13833
8
18
19
AIDS
2000
7
16
38
2
ZINC (subsct)
10000
25
(c) Summary of datasets used for Node classification
(d) Summarr of datasels used for Node regression
Dataset
Nodes
Edges
Features
Classes
Number of
Dataset
Nodes
Edges
Features
Coro
2708
5278
1433
Targets
Cileseer
4552
3703
Chameleon
2277
31396
128
Pubmed
19717
44324
500
Squirrel
5201
198423
128
DBLP
17716
52867
1639
Crocodile
11631
170845
128
Physics
34493
247962
8415
Cousthor
CCBN-Produch
24-190299
6185914H 40
100
47
E Experiment Details (Parameters and Device Configuration)
For node classification and node regression tasks, we use Adam Optimizer with a learning rate of 0.01 and L2 regularization with 0.0005 weight. We use Adam Optimizer with learning rate of 0.0001 and Le regularization with 0.0005 weight for graph-level tasks. We set epochs to 20 and the number of layers of GCN to 2 for training. We set the hidden dimensions for each layer of GCN to 512.
The device configurations are Intel(R) Xeon(R) Gold 5120 CPU @ 2.20GHz, 256GB RAM, NVIDIA A100 40GB GPU. We use Pytorch Geometric to train our models.
F
Results
Table 12 presents the results on the node classification task with all the coarsening ratios (0.1, 0.3, 0.5, 0.7). (oooaaannCCCCangggggggg We did not compare our experiments with methods such as Cluster-GCN (Chiang et al. 2019 because the method focuses on redueing training time by sampling subgraphs for several iterations. During the inference phase, however, it still performs inference the entire graph. Consequently, its inference performance would be at most comparable to that of standard GCN.
Figure 6 shows the time comparison for creating the subgraphs for Cora Dataset for different coarsening ratios. It is observed that the None method takes the least amount of time, which is intuitive since the subgraphs are not appended with additional nodes. For the Extra Node Method, the time increases since the subgraph size increases as new nodes are appended. For Cluster Node, we observe the maximum time taken since we not only looking at the neighboring nodes that lost due to partition, but also
20

---

Published in Transactions on Machine Learning Research (03/2026)
Table 12: Results for node classification tasks with accuracy as the metric (higher is better), We use the Cluster Nodes method to append additional nodes to subgraphs and to--trainto----innfe as experimental setup. varia- tion neighborhoods coarsening algoritlu is used.
Methods
Models
Reduction Ratio (r)
Dataset
Gora
Citeseer
Polmned
DBLP
Physios
Full
GCN
1.0
0,821 # 0.002
0.706 = 0.002
0.768 = 0.020
0.721 + 0.002
0,933 = 0.000
GAT
0,809
0.004
0.700
0.003
0.740 0.004
0.713 0.004
0.1
0.752 1: 0,002
0.704 1: 0.003
0.730 0.01M
0.728 0.019
0.892 0.010
GCN
0.3
0,808 # 0.003
0.700 = 0.001
0.773 = 0.002
0.737 + 0.011
0,928 = 0.003
0.5
0.808 + 0.001
0.716 + 0.002
0. 798
0.002
0.733 0.008
0.901 0.004
SGGC
0,805
0.002
0.711
0.003
0.786
0.003
0.1
0,630 + 0.001
0.605 = 0.022
0.689 0.033
0.606 0.017
0,851 1 0.008
0.3
0.686 1. 0.010
0.635 0.021
0.773 0.002
0.626 0.028
0,870 0.016
GAT
0.611
0.635
0.683
0.60M
0.7
0.643 1 0.019
0.570 a 0.041
0.733 0.023
0.613 1 0.018
0.851 0.026
0.1
0.789 + 0.003
0.676 + 0.020
0.785 = 0.003
0.718 + 0.007
0.894 0.008
0.3
0,806 0.003
0.722 0.0011
0.779 0.002
0.718 0.001
0.876 0.011
GCN
0.5
0.808
0.004
730 0.007
0.773 0.004
0.755 0.002
0,804 0.005
GCOND
0.7
0.793 4: 0.000
0.680 4: 0.012
0.775 A: 0.002
0.751 1 0.0000
0.914 0.004
0.1
0.637 = 0.067
0.553 = 0.116
0.511 = 0.079
0.475 0.057
OOM
0.3
0.549 1. 0.080
0.628 1. 0.095
0.370 0.079
0.481 0.034
0OM
GAT
0.5
0.712 # 0.059
0,501 = 0.008
0.409 = 0.014
O. 464 1: 0.030
00M
0.7
0.706 + 0.062
0.453 = 0.118
0,416 0.036
0. 4.462 0.033
0OM
0.1
0.729 0.008
0.576 0.006
0.600 0.098
0.639 0.031
0.822 0.014
0.3
0.722 # 0.011
0.585 = 0. 0.003
0.538 = 0.
0. 0.683 + 0.039
0.798 = 0.00T
GCN
0.5
0.701 + 0.012
0.008 0.001
0.670 0.084
0.702 0.049
0.832 0.016
BONSAI
0.7
0.705 1 0.009
0.582 0.007
0.474 0.020
0.68N 0.023
0.844 0.015
0.1
0.686 + 0.004
0.689 +: 0.002
0.446 = 0.014
0.642 + 0.015
0.803 0.005
GAT
0.3
0,680
0.014
0.568 0.003
0.540 0.096
0.010
0.5
0.683 = 0.006
0.579 0..00L
0,522 0.133
0.681 0.025
0.812 0.016
0.7
0.703 1. 0.010
0.594 1. 0.002
0.497 L. 0.028
0. 0.705.. 1 0.047
0.799 0.010
0.790
0.004
0,701
0.757 0.0022
0. 0.755 0.001
0.000
GCN
0.3
0,800
0.003
0.679
0.003
0.754 0.001
786
0.00
0.5
828
0.002
0.669 0.003
0.761 0.004
0.700 0.001
0.926 0.000
FIT-GNN
0.7
0,813
1 0.002
0.664 =: 01.001
0.756 =: 0.002
0.746 1 0.001
0.925 1 0.000
0.1
0.773 = 0.021
0.691 = 0.003
0.737 = 0.0122
0.729 0.010
0.887 0.003
GAT
0.3
0.761
0.004
0.655 00.00
0.754 0.002
0.771 0.002
0.885 0.004
0.5
0.792
= 0.003
0.669 = 0..001
0.760 = 0.003
0.720 1: 0.002
0.885 = 0.008
0.7
0.797
0.003
0.002 003
0.739 0.002
0.739 0.002
0.903 0.003
keeping a track of the cluster to which these neighboring nodes belong, corresponding to which, we add the cross-cluster edges.
Coarsaning Time Coarsoni 1g Razle
Doteset: cora, Coarsening Method: varistion, neighborhoodss
Clister Extia Nrukk
0.2
5.
Thre
0.
3.5
Figure 6: The plot shows how the coarsening time varies for the Cora dataset for different coarsening ratios using different methods of appending nodes to the subgraphs. variation Seciaatoo__nigghoohhoooooo coarsening algorithm is used.
Table 13 shows the maximum GPU memory consumption during inference for different datasets with different coarsening ratios and methods of appending nodes. Note that this memory consumption is to store the graph and the weight matrix in the memory only.
21

---

Published in Transactions on Machine Learning Research (03/2026)
Table 13: Summary of maximum GPU memory consumption during inference of datasets used for node-level tasks. All units are MegaBytes (MB)
FIT-GNN
Dataset
Appending Nodes
Baseline
0.1
0.3
0.5
T= 0.7
Cluster Node
0.201
0.235
0.277
0.418
Chameleon
2.078
Extra Node
0.622
0.622
0.622
0.564
Cluster Node
1.127
1.132
1.654
1.779
Crocodile
10.937
Extra Node
4.586
4.586
4.586
4.586
Cluster Node
1.436
1.532
1.815
2.869
Squirrel
8.614
Extra Node
7.190
7.190
7.190
7.190
Cluster Node
1.249
0.618
0.661
0.827
Cora
14.992
Extra Node
1.906
1.103
0.970
0.970
Cluster Node
30.097
2.048
1.195
1.607
Citeseer
47.170
Extra Node
30.097
2.490
1.835
1.835
Cluster Node
0.584
0.542
0.544
0.546
Pubmed
39.166
Extra Node
0.778
0.562
0.562
0.562
Cluster Node
5.785
2.803
1.761
1.875
DBLP
112.514
Extra Node
28.271
6.008
2.308
2.207
Cluster Node
22.911
12.481
12.767
13.688
Physics Coauthor
1115.079
Extra Node
41.066
19.936
19.936
19.936
Cluster Node
28.399
2840.706
To validate the of Vvariation neighborhoods" a coarsening algorithm for all the results presented, we show ablation study for different coarsening algorithms in Table 14 and 15
Table 14: The table shows the FIT-GNN ablation study compare various coarsening methods on Cora and Chameleon datasets, and the metrics for each dataset accuracy (higher the better) and normalized MAE (lower the better), respectively.
Cora
Chemeloon
Coarsening Method
0.1
0.3
0.1
0.3
variation_neighboeee neighborhoods
algebraic_.Je variation
0.790 = 0.004
0.800 + 0.003
0.496 = 0.005
0.489 = 0.003
0.827 0.006
0.804
0.003
0.544 0.005
0.504 0.003
kron
0.758 + 0.004
0.800 + 0.002
0.571 + 0.004
0.580 0.013
heavy__er _dge
0.736 = 0.012
0.773 = 0.006
0.372 + 0.002
0.531 + 0.002
variation_ _dges
0.484 = 0.006
0.471 = 0.012
0.513 + 0.003
0.542 + 0.005
mariation_cliquee
0.751 i: 0.012
0.801 1 0.009
0.674 1 0.009
0.679 0.008
Table 15: The table shows the FIT-GNN ablation study to compare various coarsening methods on PROTEINS and ZINC (subset) datasels. The metric for PROTEINS dataset accuracy (higher is better), and for the ZINC (subset) is normalized MAE (lower is better)
PROTEINS
ZINC (subset)
Coarsening Method
0.3
0.5
0.3
0.5
variation neighborhoods
0.652
0.739
0.573
0.620
algebraic_JC kron
0.826
0.739
0.823
0.810
0.522
0.652
0.663
1.201
heavy_ edge
0.565
0.609
2.114
1.227
variation eariation_edgees
0.652
0.565
1.548
1.883
variation _cattion_cliquuss
0.696
0.652
0.689
0.742
22

---

Published in Transactions on Machine Learning Research (03/2026)
G Detailed Ablation Study on Node Regression Performance
To understand the counterintuitive performance gains observed in node regression tasks when using FIT- GNN, we conducted a comprehensive ablation study, Specifically, we isolated the source of the performance gap to determine why restricting inference to localized subgraphs outperforms full-graph inference.
G.1 Impact of Inference Input Training Regime
Our first objective was to determine whether the performance gain stemmed from the training methodology itself or the structure of the input data (subgraphs) during inference. We evaluated two distinct setups on the Crocodile dataset using GCN convolutional layer:
Setup A: Train on subgraphs - Infer on the full graph.
Setup B: Train on the full graph Infer the full graph
Table 16: Comparison of training and inference setups to isolate the source of performance gains.
Train Setup
Inference Setup
Mean Absolute Error (MAE)
Full Graph
Full Graph
0.852
Subgraphs
Full Graph
0.865
Subgraphs (FIT-GNN) Subgraphs
0.364
As shown in Table 16 the performance of Sctup A and Sctup B is nearly identical, indicating that training on subgraphs alone does not account for the drastic MAE reduction. The substantial performance leap in FIT-GNN only occurs when subgraphs are used as the inference input, confirming that the local structural input drives the improvement.
G.2 Subgraph Optimization Landscape
We further hypothesized that partitioning the graph into subgraphs presents simpler optimization landscape for the model. To quantify this, we compared the variation of labels locally (within individual subgraphs) versus globally across the entire graph. We computed the Label Standard Deviation for node regression datasets and Label Entropy for node classification datasets.
Table 17: Comparison of global label variation versus average local subgraph variation.
Dataset
Metric Used
Global Variation
Subgraph Variation (Avg)
Cora
Entropy
1.8311
0.1245
Citescer
Entropy
1.7533
0.1572
Chameleon
Standard Deviation
2.1329
0.0689
Squirrel
Standard Deviation
1.7639
0.1284
The results in Table demonstrate that the variation of labels within individual subgraphs is drastically lower than the global variation. By coarsening the graph, we creale local contexts that statistically more homogeneous, allowing the GNN to specialize more effectively and navigate smoother optimization landscape during inference.
G.3 Structural Information Loss and Implicit Adversarial Pruning
Finally, we investigated the role of structural information loss. Using coarsening ratio of 0.5, we empirically computed the fraction of the 2nd-hop neighborhood lost. for each node.
23

---

Published in Transactions on Machine Learning Research (03/2026)
ciaeser theet. let fraet (1:1664)
teant) fractin 1961
teet Practicn (1:1334)
traini: fraction tn 12-1
200
1256
59
Iean to
mean les ticiie
rear tachaado
Flaat
Pracle
(a) Citeseer (Classification)
(b) Cora (Classification)
3001
6.1
Tactor
(c) Squirrel (Regression)
(d) Chameleon (Regression)
Figure 7: Histograms detailing the fraction of the 2nd-hop neighborhood lost for each node at coarsening ratio of r = 0.5. distinct difference in distribution is visible between classification (a, b) and regression (c, d) datasets.
Obsorvations and Intorpretation: The histograms Figure reveal stark contrast between task types. In the node classification datasets (Cora, Citeseer), a significant number of nodes relain their 2nd- hop neighborhood entirely (lost fraction close to 0). Conversely, in the node regression datasets (Squirrel, Chamcloon), the vast majority of nodes losc a highly significant portion of their 2nd-hop neighborhood (lost fraction close to 1).
Given the superior performance FIT-GNN on these regression tasks, we interpret this structural loss as form of implicit adversarial pruning. specific heterophilic graphs, long-range information (such as hop-hop neighbors) acts as noise an adversarial signal. The coarsening algorithms utilized by FIT-GNN implicitly filter out this distant noise. This pruning allows the model to fully exploit the low-variance, highly homogeneous local structures identified in Section G thereby drastically reducing regression error.
24


Reviews:
[{"review_id": "3FfINOuqaK", "reviewer": "Reviewer_MkPi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of high inference time and memory consumption in GNNs on large graphs. In contrast to prior work that focuses on reducing training cost, the paper explicitly targets inference efficiency. The proposed FIT-GNN framework applies graph coarsening to partition a graph into subgraphs and performs both training and inference on these subgraphs. To reduce information loss caused by partitioning, the method introduces two strategies, Extra Nodes and Cluster Nodes. The approach is evaluated on node-level and graph-level tasks, including classification and regression.\n\nA key strength of the paper is its clear focus on inference scalability, which is practically important but less studied than training efficiency. The work provides a theoretical analysis of time and space complexity and extensive experiments across many datasets, including very large graphs where baseline methods fail due to memory limits. The results show large reductions in inference time and memory usage while maintaining competitive predictive performance. \n\nA limitation is that the method depends on the choice of coarsening algorithm and coarsening ratio, which introduces additional hyperparameters. In addition, the conceptual difference from earlier partition-based methods could be stated more explicitly to avoid confusion.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims are supported by both theoretical and empirical evidence. \nThe paper derives conditions under which subgraph-based inference has lower time and space complexity than standard full-graph inference. \nThe experimental section evaluates the method on a wide range of benchmarks and tasks, and reports inference time, memory usage, and predictive performance.", "audience_yn": "Yes", "audience_explanation": "The paper is relevant to researchers and practitioners interested in scalable graph learning and deployment of GNNs in resource-constrained settings.", "requested_changes": "1. The paper would benefit from a clearer and more explicit comparison with Cluster-GCN. While Cluster-GCN is cited, the authors should clearly state that it mainly improves training scalability and still requires full-graph inference, whereas FIT-GNN reduces both training and inference cost. (critical)\n\n2. The complexity analysis is largely presented using dense-matrix formulations and GCN-style computation. A clearer discussion of sparse implementations and how the conclusions extend to other common architectures, such as GraphSAGE or GIN, would improve clarity and practical relevance. (critical)\n\n3. The paper could offer more practical guidance on how to choose the coarsening ratio and coarsening algorithm for new datasets, based on the empirical observations already reported. (non-critical)\n\n4. The presentation of the methodology and analysis could be streamlined to improve readability. (non-critical)\nSuch as in Section 4.3 and the associated appendices.", "broader_impact_concerns": "The paper focuses on computational efficiency and does not raise notable ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ah6425h3vm", "reviewer": "Reviewer_HnZE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary\nThe paper proposes a framework to make GNN inference computationally efficient, measured in terms of time and memory, by performing inference on a part of the total graph. The idea is to run both training and inference on a set of subgraphs obtained by applying a graph coarsening method to the original graph, rather than using coarsening only to speed up training, as in prior work. \nSpecifically, as partitioning cuts inter-subgraph edges, the method augments each subgraph with additional context via two existing strategies: Extra Nodes and Cluster Nodes. During training, the method trains a standard GNN by looping over subgraphs and computing the loss only on training nodes in each subgraph. In the experimental section, the paper evaluates multiple training and inference regimes, assesses the methods on node and graph classification and regression tasks across various datasets, and provides a time/memory complexity analysis and a theoretical condition. \n\nStrengths\n- The method is simple and straightforward; it essentially uses existing methods to partition the graph, adds boundary context, and then trains and infers on subgraphs. Moreover, two different graph coarsening methods (Extra Nodes, Cluster Nodes) are ablated and discussed.  \n- The method seems to scale to cases where baselines lead to out-of-memory problems; for example, Table 5 shows that on OGBN-Products, different baseline methods lead to out-of-memory while the proposed approach still runs and achieves good accuracy. The paper also reports clear empirical memory savings; specifically, Table 13 shows large reductions in peak GPU memory during inference. \n\nWeaknesses\n- My first major concern is the novelty of the approach. The contribution is incremental, as the core coarsening algorithms (Extra Nodes and Cluster Nodes) have already been proposed before for training GNNs. It seems the new angle is to use these for inference-time scaling and to package them together across tasks. \n- Another major concern revolves around clarity, notation, and, in general, the presentation quality of the manuscript. The paper is not always clear; for example, the description of the Extra Nodes and Cluster Nodes methods—including the clarity of Figure 2—is quite brief and unclear. The notation is also not helping improve clarity; for example, in Section 3.1, G is a weighted undirected graph, and W is the edge-weight matrix. However, later in the same section, the notation for an adjacency matrix is used, which indicates a binary, unweighted graph. The notation using an unweighted graph is then used in Section 3.2, equation (1). Also, k=n×r, k∈Z: the round, floor, or ceiling function should be used. Moreover, the writing is dense, explanations are limited, and pointers to Algorithms, Tables, and figures are scattered throughout the paper, making it difficult to understand the training and inference process of the proposed approach.\n- Continuing from my previous comment, the theoretical analysis in Section 3.1 is also quite convoluted; for example, it is not clear how the time and space complexities are calculated in Table 1. Moreover, the notation in this section is not clear, and the proof contains no explanations that walk the reader through the proof.  \n- The paper presents several experiments, but the reasoning and explanations of the observed results are missing. For node regression, the method’s MAE is dramatically lower than the full GNN across multiple model ratios in Table 3. That seems unusual for a method that changes computation locality; it may be correct, but it deserves deeper analysis to rule out confounds (normalization, split differences, leakage assumptions, hyperparameter mismatches). \n- It is not clear whether the preprocessing time to coarsen the graph is factored into the complexity analysis; as far as I understand, the evaluation largely focuses on runtime and memory after subgraphs are formed. If this is the case, this preprocessing time should be added to the inference time. In fact, as shown in Figure 6, the coarsening time increases with the coarsening ratio and also the storage of various subgrains, leading to increased complexity.", "claims_and_evidence_yn": "No", "claims_explanation": "While the paper reports promising reductions in inference time and memory, several claims lack sufficiently clear and convincing evidence. In particular, the theoretical analysis and complexity tables are difficult to verify due to unclear notation and an opaque proof, and the empirical results lack the analysis needed to justify findings. Moreover, the reported inference efficiency appears to exclude costs such as coarsening time and subgraph construction overhead, which are directly relevant to the claimed inference-time gains. \n\nThe manuscript needs a thorough clean-up so the method is easy to follow; this also includes notation and explanations. In particular, the description of Extra Nodes and Cluster Nodes (and Figure 2) should be expanded and rewritten for readability, and the notation should be made consistent. The text should also be streamlined, reducing density and improving the explanation of the method. Basically, the paper should clearly present the proposed training and inference strategies (against the SoTA) and provide the technical details needed to understand the contribution. On the theoretical analysis, Section 3.1 should be rewritten to make the complexity claims verifiable. The derivation of Table 1 should be explained step by step, with clearly stated assumptions, and the proof (including Lemma 4.2) should include explanatory text that guides the reader through the argument rather than presenting algebra without interpretation.\n\nThe paper should include an analysis that explains the key trends and validates that the results are not due to confounds. In particular, the unusually large gains in node regression (Table 3) relative to the full GNN warrant deeper discussion, so the reader can trust that the improvements stem from the proposed inference/training approach.\n\nFinally, in the inference-time claims, it should be made clear whether coarsening time and subgraph construction (and storage) overhead are included; if they are not, they should be accounted for in the reported inference cost.", "audience_yn": "No", "audience_explanation": "Although the paper addresses an important practical issue, the current manuscript does not present the ideas and evidence with enough clarity and rigor for the findings to be reliably interpreted. The incremental novelty and unclear theoretical and empirical claims might limit the interest of the TMLR audience.", "requested_changes": "The paper should more clearly articulate what is technically new beyond reusing existing coarsening ideas (Extra Nodes / Cluster Nodes) and applying them at inference time. This requires clearer positioning against the state of the art and a stronger statement of the method's technical advantages over prior work.", "broader_impact_concerns": "I do not have major broader-impact concerns. The work aims at reducing inference time and memory for GNNs, which is generally beneficial.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cWYxD2I0TL", "reviewer": "Reviewer_UgrG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies an important problem of scalable graph neural networks. The authors propose a novel approach by reducing computational burden during the inference phase using graph coarsening. Experiments show the effectiveness of the proposals.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims are supported by extensive experiments.", "audience_yn": "Yes", "audience_explanation": "Graph neural networks are widely studied by existing methods in the machine learning area.", "requested_changes": "1. It would be better to include theoretical computational complexity analysis, i.e., space and time complexities.\n2. It is suggested to include more experiments regarding efficiency, such as training time, inference time, and FLOPs.\n3. The future work seems to be very general. It would be better to provide more specific descriptions.", "broader_impact_concerns": "It would be better to include a subsection to show how this paper can advance the GNN area, and even the machine learning area.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)