GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks
Authors: Taraneh Younesian
Daniel Daza
Emile van Krieken
Thiviyan Thanapalasingam
Peter Bloem
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) learn to represent nodes by aggregating information from
their neighbors. As GNNs increase in depth, their receptive field grows exponentially, leading
to high memory costs. Several works in the literature proposed to address this shortcoming by
sampling subgraphs, or by using historical embeddings. These methods have mostly focused
on benchmarks of single-label node classification on homophilous graphs, where neighboring
nodes often share the same label. However, most of these methods rely on static heuristics
that may not generalize across different graphs or tasks. We argue that the sampling method
should be adaptive, adjusting to the complex structural properties of each graph. To this
end, we introduce GRAPES, an adaptive sampling method that learns to identify the set of
nodes crucial for training a GNN. GRAPES trains a second GNN to predict node sampling
probabilities by optimizing the downstream task objective. We evaluate GRAPES on various
node classification benchmarks involving homophilous as well as heterophilous graphs. We
demonstrate GRAPES’ effectiveness in accuracy and scalability, particularly in multi-label
heterophilous graphs. Additionally, GRAPES uses orders of magnitude less GPU memory
than a strong baseline based on historical embeddings. Unlike other sampling methods,
GRAPES maintains high accuracy even with smaller sample sizes and, therefore, can scale
to massive graphs. Our implementation is publicly available online.

Published in Transactions on Machine Learning Research (05/2025)
GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks
Taraneh Younesian Vrije Universiteit Amsterdom
t. m.y
Daniel Daza Amsterdam UMC
Emile van Krieken University of Edinburgh
Emile. von. Kwieken@edd.ac..... uk
Thiviyan Thanapalasingam University of Amsterdam
Laingamm@uuaa..m
Peter Bloem
p. w..blom@uu...
Vrije Universiteit Amsterdom
Reviewed on OpenReview: https: openreview. net/ formm? id= QIQ022242
Abstract
Graph neural networks (GNNs) learn to represent nodes by aggregating information from their neighbors. As GNNs increase in depth, their receptive field grows exponentially, leading to high memory costs. Several works in the literature proposed to address this shortcoming by sampling subgraphs or by using historical embeddings. These methods have mostly focused on benchmarks of single-label node classification on homophilous graphs, where neighboring nodes often share the same label. However, most of these methods rely on static heuristies that may not generalize across different graphs or tasks. We argue that the sampling method should be adaptive, adjusting to the complex structural properties of each graph. To this end, we introduce GRAPES, an adaptive sampling method that learns to identify the set of nodes crucial for training GNN, GRAPES trains a second GNN to predict node sampling probabilitics by optimizing the downstream task objective. We evaluate GRAPES on various node classification benchmarks involving homophilous as well as heterophilous graphs. We demonstrate GRAPES' effectiveness in accuracy and scalability, particularly in multi-label heterophilous graphs Additionally, GRAPES uses orders of magnitude less GPU memory than strong baseline based on historical embeddings. Unlike other sampling methods, GRAPES maintains high accuracy even with smaller sample sizes and, therefore, can scale to massive graphs. Our implementation is publicly available online.'
1 Introduction
Despite the broad range of applications of GNNs (Nettleton, 2013; Wu et al., 2022; Li et al., 2022; Kipf & Welling, 2016; Velickovic et al., 2017; Yun et al., 2019), scalability remains significant challenge (Serafini & Guan, 2021). Unlike traditional machine learning problems, where data is assumed to be i.i.d., the graph structure introduces dependencies between a node and its neighborhood. This complicates partitioning data into mini-batches. Additionally, the number of nodes that a GNN needs to process increases exponentially with the number layers (Ma et al., 2025).
Available https: http://ggttttbbtte com/ www.hh/w.commddaaaaccoaoeo grapes.

---

Published in Transactions on Machine Learning Research (05/2025)
1-hop node sampling
2-hop node sampling
gradient update
GNN
GNN
sampling
sampling
sampling
sampling
GNN classilier
cros-entropy
loss
policy
S
policy
2
classification reward
Figure 1: Overview of GRAPES. First, GRAPES processes target node (green) by computing node inclusion probabilitics on its 1-hop neighbors (shown by node color shade) with a sampling GNN. Given these probabilities, GRAPES samples k nodes. Then, GRAPES repeals this process over nodes in the 2-hop neighborhood. We pass the sampled subgraph to the classifier GNN for target node classification. Finally, GRAPES uses the classification loss to update the classifier GNN and to reward the sampler GNN.
Most current graph sampling methods use fixed heuristic to compute node inclusion probabilities: The sampling process is independent of the node features, graph structure, or the GNN task performance (Chen et al., 2018b; Zou et al., 2019; Zeng et al., 2019). For simple graphs like homophilous graphs (Zhu et al., 2020; Zheng et al., 2022; Zhao et al., 2023) where there is strong correlation between labels of a node and its neighbors, a fixed heuristic typically suffices. However, these methods fall short when applied to graphs in which only a few of the nodes in the neighborhood provide relevant information for the task at hand. Consequently, we study adaptive sampling, where the sampling method adapts dynamically to the task by learning which nodes should be included. Our adaptive sampling technique learns to sample by directly minimizing the classification loss of the downstream GNN. This differs from most existing graph sampling methods, which aim to approximate the full-batch GNN (Chen et al., 2018b; Zou et al., 2019; Zeng et al., 2019; Huang et al., 2018), opting for an indirect approach to achieve high accuracy.
We introduce a straightforward adaptive sampling method called Graph Adaptive Sampling (GRAPES). As illustrated in Figure 1, GRAPES samples a subgraph around the target nodes in series of steps. At cach step, a sampling policy GNN computes inclusion probabilities for the nodes neighboring the current subgraph, which the sampler uses to select a subset. Once the sampling is complete, the resulting subgraph is passed to second classifier GNN for classification. The classification loss is then backpropagated to train both GNNs.
To enable backpropagation through the sampling step, we need a gradient estimator. We compare a reinforeement learning (RL) approach and a GFlowNet (GFN) approach (Bengio et al., 2021a). Both approaches allow us to consider the sampling process and the GNN computation together and to train them concurrently. This allows the sampler to adapt based on factors like the node features, the graph structure, the sample size, and other contextual features.
In multi-class classification- where a node can be assigned only one of multiple classes- on homophilous graphs, even simple strategy like random sampling could be sufficient, since the neighborhood of a node contains nodes with similar labels (see Fig. 2a). In the case of multi-label classification, on the other hand, the number of possible labels assigned to a node is 122 where y is the unique set of labels. Furthermore, in heterophilous graphs, the relationship between the neighborhood of a node and its label more complex (see Fig. 2b). We argue that in such cases, a sampling policy that directly adapts to the propertics of the graph and the downstream task is crucial.
Therefore, in addition to the datasets commonly used in the literature, we evaluate GRAPES several heterophilous and/or multi-label graphs and demonstrate its effectiveness on these complicated graphs. Moreover, we spend significant. effort on the evaluation protocol for fairly testing graph sampling hods. In particular, we ensure that all sampling methods are evaluated under the same conditions and on the same GNN architecture eliminate any confounding factors and to ensure that any changes in performance can only be attributed to the sampling method. To the best of our knowledge, we are the first to perform such a rigorous comparison on twelve varied datasets.
2

---

Published in Transactions on Machine Learning Research (05/2025)
Binding
Areficial Intelligence Cognitive Science
Signal to t'ansduction
Regulation
Blosynthesis
(b)
Figure 2: The downstream task and the structural properties of the graph affect the strategy used for sampling. Fig. 2a shows citation network where articles citing each other are likely to belong to the same category. Fig. 2b shows a graph of interacting proteins, each with different biological functions.
Additionally, we provide thcorctical analysis indicating the effectiveness of adaptive sampling on a specific calegory of heterophilous graphs, where only subset of neighbors contains relevant information for an accurate node classification.
We evaluate GRAPES on several node classification tasks and find that
Performance. GRAPES achieves state-of-the-art performance in multi-label classification bench- marks over hetcrophilous graphs, while performing competitively multi-class classification on homophilous graphs.
Memory Efficiency. GRAPES uses orders of magnitude less GPU memory when compared with a strong baseline that relies historical embeddings for scaling GNN training.
Robustness.
comparison with other methods, GRAPES maintains good performance under exponential reductions in sample size.
2 Related Work
Fixed Sampling Policy: In this category, the sampling policy is independent of the training of the GNN and is based on fixed heuristic that does not involve any training. Given a set of target nodes, i.e. the nodes that are to be classified, node-wise sampling methods sample given number of nodes for each target node. GraphSage (Hamilton et al., 2017) is node-wise sampling method that randomly samples nodes. However, nodo-wise sampling can result nodes being sampled multiple times redundantly because they can be the neighbors of several nodes (Zou al., 2019). more efficient approach is layer-wise sampling, for example, FastGON (Chen et al., 2018b) and LADIES (Zou al., 2019). They aim minimize variance by sampling nodes in each layer with probabilities proportional to their degree. MVS-GNN (Cong et al., 2020) proposes fixed sampling policy with the aim of minimizing sampling variance by decoupling it into two components. The first component, embedding approximation variance, arises from neighbor sampling and is mitigated through the use of historical embeddings. The second component, stochastic gradient variance, results from mini- batchng and is addressed by incorporating the norm of the node gradients into the sampling process. Moreover, some techniques focus on sampling subgraphs each mini-batch, like GraphSAINT (Zeng et al., 2019) and ClusterGCN (Chiang et al., 2019). While these tochniques effectively scale GNNs to larger graphs, they do not adapt the sampling policy based on the GNN's performance on the task. In the graph signal processing community, the authors in (Geng et al, 2023) propose node sampling technique based on (Anis et al., 2016) to sample nodes for unique and stable graph signal reconstruction. However, this method is only applied to small graphs.
Learnable Sampling Policy: few methods learn the probability of including a node based on feedback from the GNN. AS-GCN (Huang et al., 2018) is a method that learns linear function that estimates the node probabilities layer-wise. Similarly, PASS (Yoon et al., 2021) learns mixture of a random distribution and a learned policy with RI. Like GRAPES, it is task-adaptive; however, its sampling probability uses
3

---

Published in Transactions on Machine Learning Research (05/2025)
bilinear similarity measure between neighboring node features, meaning the graph structure is not considered. FairSample Cong et al. (2023) is learnable sampling policy that borrows the PASS training mechanism that utilizes reinforcement learning to combine classification loss and a fairness loss to balance accuracy and fairness towards the underrepresented nodes. GNN-BS (Liu et al., 2020) formulates the nodc-wisc sampling problem as bandit problem and updates the sampling policy according lo reward function that reduces the sampling variance. SubMix (Abu-El-Haija et al., 2023) proposes a mixture distribution of sampling heuristics with learnable mixture weights. DSKReG (Wang et al., 2021) learns the relevance of items in a user-item knowledge graph by jointly optimizing the sampling strategy and the recommender model. The majority of these methods focus on variance reduction and fail to consider the classification loss, unlike GRAPES. We argue that adaptivity to the classification loss allows for sampling the influential nodes depending on the task and results in belter performance.
Other Scalable Methods: Authors of (You et al., 2022; Zhang et al., 2024) use graph lottery tickets climinate unnocessary edges, while DSpar (Liu et al., 2023) uses a simple Regree-based heuristic to sparsify the graph. Ruiz et al. (2023) proposes a method to transfer the weights of GNN trained on a mid-sized graph to larger graphs, given the graphon similarity between the graphs. Another group of papers uses historical embeddings of the nodes when updating the target nodes' emboddings (Chen et al., 201 Sa; Fey et al., 2021; Yu et al., 2022; Shi et al., 2023). GAS (Fey et al., 2021) approximates the embeddings of the 1-hop neighbors using the historical embeddings of those nodes learned in the previous training iterations. These methods reduce the GPU memory usage by training in mini-batches and learning from the 1-hop neighbors with the historical embeddings saved in CPU memory. Unlike GRAPES, they process the whole graph.
3 Background: GNN Training and Sampling
We first provide the necessary background about GNNs and graph sampling. Although our method is independent of the choice of GNN architecture, we limit our discussion to the GCN architecture for simplicity (Kipf & Welling, 2016).
Let 9 =V.8) be an undirected graph with list of N nodes fI...., and a set of edges E. The adjacency matrix A e E [0,1]NxN indicates a connection between a pair of nodes. Next, let Á D-1/2 --111AD---- 1/22 where À = A + I and where D is the degree matrix of Å. Let X R Nxf be the node embeddings and let Y be the labels for the target nodes V V, where V indexes the nodes with a label.
We consider a GCN with L layers. The output of the 1-h layer of the GCN is H = = -AH where w(I) is the weight, matrix of GCN layer I and a is a non-linear activation function. For a node i E V, this corresponds to the update
1 =a
Σ
Angh (1-11 A "w0)
JEN(UUU)
where N(i): V + 2 is the set of i's neighbors excluding i.
As the number of layers increases, the computation of the embedding of the node involves neighbors from further hops. As a result, the neighborhood size grows rapidly with the number of layers. We study how to sample the graph to overcome this growth. We focus on layer-wise sampling, common type of graph sampling approach (Chen et al., 2018b; Zou et al., 2019; Huang et al., 2018). First, we divide the target nodes into mini-batches of size b. Then, in each layer, we sample k nodes p( among the neighbors of the nodes in the previous layer using the sampling policy q. To make this precise, we will need some additional notation. The computation of the output of layer l is then:
for all i i K(),, N. =a (
Σ
A! n1 ((1))
(2)
jERU 2)
with D(- v(t) 9(V(1-1), (1(()1))2)(0)) ((00
where
4

---

Published in Transactions on Machine Learning Research (05/2025)
1. K(0) = vx0) is the set of target nodes in the current mini-batch, where V VV; adds the batch nodes y(o) to the sampled nodes Dio) to ensure
2. K() = vio U v(o) for all 1..... T.
self-loops between the batch nodes;
3. vL) C DV(K())) are the nodes sampled in layer I among the neighbors (V((l-))) of the nodes in K(--)), Note that yL) cannot contain nodes in K(l-1);
4. Á = DO0 A D(0 is computed from the adjacency matrix A containing the edges between
K() and K(-1),, and the corresponding degree matrix D To be precise, the entries 4 are 1 if and only if i E K E k((-1) and if there is an edge (i..) in the original graph, that is, A.j = 1; q is a sampling policy that samples the nodes D(U)
Existing layer-wise sampling methods, such as LADIES or Fast use a fixed heuristic to determine q, for instance, by computing node probabilities proportional to the node degrees. However, an adaptive method learns the distribution q instead.
4 Graph Adaptive Neighbor Sampling (GRAPES)
We introduce Graph Adaptive Sampling (GRAPES). GRAPES is a layer-wise and dayer-dependent adaptive sampling method that learns sampling policy that minimizes the training objective conditioned the input graph. In each layer 1, we sample subset vi) that is much smaller than the neighborhood of the previous layer. That is, | = < ((K(-)))), where again ( = y(") u v(t-1) adds the batch nodes to the sampled nodes of the previous layer. We use a second GNN to compute the inclusion probability for each node in (KK( In the remainder of this section, we describe our sampling policy and training methods for the sampling policy. Furthermore, Algorithm 1 shows one epoch of GRAPES in pseudocode.
4.1 Sampling policy
Next, we specify the sampling policy GNN GCNs(K(-))), which computes inclusion probabilities on the subgraph created from the nodes in ((I-)) and their neighbors A/l-1), The sampling policy q decomposes as q(V()),... (()) = l (VV (10) ...., v(-1)). We compute each factor (1)0)) ....., y(I-1) as a product of Bernoulli inclusion probabilities, given by GCNs, for each node i in the neighborhood N ((K(1-1)):
q(V())()) D(-
II
Bern(i E (())p)), = GCNS(KK
3
(EN 1)
In addition the regular embeddings X, the sampler GNN also has access to one-hot vector of length L 1 that records the value 1+1 for nodes sampled in layer / (with 1 recorded for the target nodes). This allows the sampler to differentiate between nodes sampled in different layers.
4.2 Sampling exactly k nodes
We have clear constraint on the number of nodes want to include in training: In Equation 2, we sample exactly k nodes without replacement. However, our sampling policy q(>()) (P))) ...., v(l11) consists of many independent Bernoulli distributions, and it is highly unlikely that we sample exactly k nodes from this distribution.
Instead, we use the Gumbel-Top-k trick (Vicira, 2014; Huijben et al., 2022), which selects a set of exactly k nodes Di0) by perturbing the log probabilities randomly and laking the top-k among those:
D top-k log + c, 6 Gumbel 1)
(4)
iEN(KU-n)
This guarantees a sample from ((V()) ..... ((1-)) k) that conditions on the number of nodes sampled.
Uulike the full-batch GCN, the adjacency matrix varies across layers when sampling because each layer involves different of nodes. Note also that, unlike the full-batch setting, message passing asymmetric: node may be updated from node j but not vice versa.
5

---

Published in Transactions on Machine Learning Research (05/2025)
While this results in a tractable and adaptive sampling procedure of exactly k nodes for the classifier GNN, we have not yet given method for learning the sampling policy. Unfortunately, a sampling operation, in this case, the top-k operation, provides no functional gradient (Mohamed et al., 2020). We will resort to simple methods from the reinforcement learning and GFlowNet literature to still be able to train the sampling policy, which we will explain next.
The choice of Bernoulli distribution for sampling node neighborhoods motivated by the idea that when conditioned target node, we can sample a node independent of other nodes in the neighborhood to maintain efficiency. Other assumptions could be more elaborate, such as sampling jointly pairs of nodes at time, but this would in turn increase the computational cost of computing probabilities and sampling. On the other hand, the Gumbel top-k trick allows us to sample exactly k elements without replacement, and while there are other applicable methods such as reservoir sampling, they are mathenatically equivalent (Huijben et al., 2022).
4.3 Training the Sampling Policy
We train the sampling policy to minimize the classification loss Le of the classifier GNN3, We use two methods to train the sampling policy GCNs: a reinforcement learning (RL) method and a GFlowNet (GFN) mod We also experimented with the which we observed not to perform well due to increased computation and high bias in the estimated gradients (see Appendix G).
estimator (Bengio et al., 2013) for learning in GRAPES,
REINFORCE (GRAPES-RL) In the REINFORCE- method, we use a simple REINFORCE estimator (Williams, 1992) to compute an unbiased gradient of the classification loss.
(X, Y, VO)) = Lo(X, K(0) K(()) log (((()))...... (()))
(5)
where we sample D(),... ((D) ~ g(v()) p(
k). Taking the derivative with respoct to the paramo- ters of results in the standard REINFORCE estimator. Note that this is an off-policy estimator since we sample from a conditioned on the number of samples with the Gumbel-Top-k trick, but compute gradients with respect to the distribution unconditioned on k. This is because computing likelihoods conditioned on k, although possible (Ahmed et al., 2023), is computationally expensive. We discuss this issue in more detail in Appendix A.
GFlow (GRAPES-GPN) from the GelowNet literature (Bengio et al., 2021b;a), which is known to perform well in off-policy settings (Malkin et al., 2022b).
The second method uses the Trajectory Balance loss (Malkin el al., 2022a)
(x) = Iog Z(2(0)) + ( ..... p140)110)
(6)
+ Lc(X, k00) ((.,,,,,K,. k(W))
where log z(V()) is a small GCN that predicts a scalar from the target nodes, and a tunable reward scaling hyperparameter. For a detailed derivation, see Appendix F.3. GFlowNets minimize objective that ensures sampling in proportion to the negalive classification loss, rather than minimizing it like in REINFORCE. This may have benefits in the exploratory behavior of the sampler, as it encourages the training of diverse sets of nodes, instead of only the single best set of nodes.
Memory complexity. Layer-wise sampling methods like GRAPES, FastGCN, and LADIES have a sampling space complexity of O(Dbk), where D is the maximum node degree, b is the batch size, l: is the sample size, and L is the number of layers. In GAS time complexity is (bk)) due to the use of historical embeddings, and memory complexity O(DbL + N) where N is the extra overhead for storing historical embeddings for the N nodes in the graph, which can be significantly larger than DbL.
GRRAPFS can extended other tasks, but we facus on node classification in the current work.

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm 1 One GRAPES epoch
Require: Graph 9, node embeddings X, node labels Y, larget nodes Vr, batch size b, sample size k, GCN for classification GCNc, and GCN for sampling policy GCNs.
1: Divide target nodes ve into batches v(0) of size b
2: for each batch v(0) do
3: (()) <- V(0)
4: for layer -= to L do
for node i in (V(((=1) do
pt - GCN 5 (111)1));
Compute probabilities of inclusion
G (u,
Sample Gumbel noise
8:
V t
logp: +
>> Get k best nodes (Eq. 4) Add target nodes
K vio) uv(l)
10:
lc + Lo(X, K ,...,
D. Compute classification loss
11:
Compute sampling policy loss Es from Eq. 5 or
12:
Update parameters of GCNs by minimizing is
13:
Update parameters of GCNc by minimizing lc
5
Theoretical Analysis
In this section, we provide theoretical insights on the performance difference between adaptive and non- adaptive samplers, and we prove that adaptive sampling can achieve higher accuracy than non-adaptive sampling for a specific category of heterophilous graphs. We show that if there exists specific crucial information among the neighbors, there are adaptive sampling methods that perfectly identify these neighbors, while non-adaptive sampling methods cannot distinguish them from the other neighbors.
Let G = EV,E) be undirected graph with set of N nodes V = (l,...,NN and a set of edges E E {eiz L.V
where eij denotes an edge between v and vg. Let X RxX be the node features and let Y == ( = be a set of node labels. The adjacency matrix A E {0,1) NxN indicates connection between pair of nodes. Let N(n;) (uylei E E) indicate the set of vs's neighbors and (1;); = (1yl((s,, vÿ) S L} indicate the L-hop neighborhood of us where I(v;, U3) indicate the shortest path between and ny. In the following definitions and theorems,, for simplicity, we consider the batch size of one.
Definition 1 (Neigbor sampling). A neighbor sampling method is a method that assigns scores to neighbors of target node, and for a given sampling budget K, samples K neighbors proportional to their score. An L-layer neighbor sampling method, for each layer I, assigns scores to the l-hop neighbors of a target node.
Definition (Featureless and feature-based sampling). An L-layer feature-lest sampling method is a neighbor sampling method in which the sampling score for each node v, is a function of only its L-hop neighborhood, i.e. s(v,) = (f where s(v;) is the sampling for node v; and g is the sampling function. In on Tayey feature- sampling method, the sampling function is function of the node features in addition to the L-hop neighborhood, that is, s(G;) = (1,,,X
In practice, all beature-based sampling methods are adaptive since the sampling methods learns the sampling score from the features, and all non-adaptive methods are featureless. Therefore, in this section, we refer to the sampling methods as adaptive and non-adaptive.
Random sampling is a non-adaptive sampler with a constant sampling score. LADIES and FastGCN are non-adaptive samplers whose sampling scores are proportional the node degrees. GraphSALNT-RW, ie., the random walk- based sampler of GraphSAINT, which we used in our experiments, is a non-adaptive sampler where the score correlates with how frequently node appears in L-hop neighborhoods, influenced by both the node's degree and its position in the graph. AS-GCN, PASS, and GRAPES are adaplive samplers.
Definition& 3 (Zhu et al. (2020)). Edge homophily is the ralio of edges that connect two nodes of the same label:
h Keeg E E :3: = 4/H
7

---

Published in Transactions on Machine Learning Research (05/2025)
In the next theorem, we show that the optimal adaptive and non-adaptive samplers perform differently for a certain category of graphs, with adaptive samplers perfectly sampling the influential neighbors and non-adaptive samplers sampling such nodes with a vanishing probability.
Theorem 1. There erist undirected graphs such that GCN with on L-layer adaptive sampler and sampling rale of K neighbors per node per layer can perform with perfect accuracy, whill GCNs with non-adaplive sampler can achieve an accuracy higher then chance level only with probability p S LK N
For the proof of this theorem, please refer to Appendix H. In the proof, we construct family of distributions over graphs where the presence of a single neighbor is essential for correct classification of targel node. Then, we show that only naature-based samplers, by learning from the node features, can sample those neighbors, while featureless samplers, with overwhelming probability, cannot. Since, in practice, all feature- based samplers are adaptive and, inversely, all non-adaptive samplers are featureless, we conclude that adaptive models can solve this task, while non-adaptive methods cannot.
Additionally, we show that such graphs heterophilous. Morcover, often, multi-label graphs are heterophilous because neighboring nodes are less likely to share the exact same set of labels. Even slight variations in the labels of neighboring nodes can lead to heterophily. Therefore, adaptive sampling met outperform non-adaptive ones in such graphs.
6 Experiments
Our experiments aim at answering the following research question: given a fixed sampling budget and GNN architecture, what is the effect of training with an adaptive policy for layer-wise sampling, in comparison with the related work? While several works in the literature of sampling for GNNs have focused classification benchmarks to demonstrate the performance of sampling algorithms, several confounding factors in their experimental setup prevent a proper understanding of whether the perceived performance improvements result from the sampling method itself. Examples of such confounding factors found in related work include using different architectures, like the GCN (Kipf & Welling, 2016) or GAT (Velickovic et al., 2017), different sizes for the hidden layers, number of layers, batch sizes, number of nodes sampled per layer, and the number of training epochs. These are factors independent of sampling algorithms that nonetheless affect the performance in the benchmarks. We present detailed overview of differences in the experimental setup of the related work in Table 4 in the appendix.
To better understand the effect of sampling algorithms, we thus carry out experiments on a fixed GCN architecture (Kipf & Welling, 2016) with two layers, a hidden size of 256, batch size of 256, sample size of 256 nodes per layer, and a fixed number of epochs per dataset (detailed in Appendix B). Under this setting, we compare GRAPES with the following basclines: a Random bascline that uses the same sctup as GRAPES but with uniform inclusion probabilities; FasIGCN (Chen et al., 2018b), LADIES (Zou al., 2019), GraphSAINT (Zeng et al., 2019), GAS (Fey et al., 2021), AS-GCN (Huang et al., 2018), and PASS Yoon et al. (2021). With this setup, we aim to control our experiments in way such that variations in performance can only be attributed to the sampling method.
For all baselines (except Random), we rely on their publicly available implementations. For all methods, we optimize the learning rate using the performance on the validation set. GRAPES requires selecting two additional hyperparameters: the learning rate for the sampling policy and, for GRAPES-GFN, the reward scaling parameter a. We tune these based the classification performance on the validation set. These hyperparameters are specific to sampling method and do not explicitly affect the learning capacity of the GCN classifier. We refer the reader to Appendix B for more details on hyerparrameter settings.
6.1 Datasets
Most methods in the literature of sampling in GNNs are evaluated on homophilous graphs (where the connected nodes are likely to have similar labels) and multi-class classification, where nodes are classifiod into one of several classes (in contrast to multi-label). To further understand the effect of sampling, we carry out experiments with helerophilous graphs, where nodes that are connected differ in their features and labels,
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 1: Fl fl--scors (%) for different sampling methods trained on homophilous graphs, for batch size of 256, and sample size of 256 per layer. We report the mean and standard deviation over 10 runs. The best values among the sampling baselines (all except GAS) are in bold, and the second best are underlined. MC stands for multi-class and ML stands for multi-label classification. OOM indicates out-of-memory.
Dataset
Cora MCC
Citeseer h 0.74 MC
Pubmed MC
Reddit h 0.78 MC
ogbu-arxiv 0.65 MC
ogbu-products h 0.81 MC
DBLP
Homophily
0.76
'Task
MI.
GAS
87.00 0.19
85.87
0.19
87.45 0.23
91.75 0.04
68.36 0.35
71.69
0.14
83.08 + 0.31
FasGGN
76.17 3.98
62.81
7.19
53.52 + 28.48
62.93
3.28
39.49
8.04
66.09
3.04
62.93 +: 3.28
LADIES
76.02 +: 11.69
63.48 1: 12:21
72.81 +: 17.67
59.30
2.69
43.52 1 8.03
68.08
1.95
59.97 10.45
GraphSAINT
87.28 + 0.49
77.28 + 0.67
87.45 + 0.75
91.47 # 0.94
63.54 + 1.75
67.66 + 0.69
77.09 + 0.56
AS-GCN
86,60 = 0.54
79.21 + 0.19
90.58 + 0.40
93.52 = 0.40
65.38 + 1.80
73.94 = 0.40
83.24 + 0.51
PASS
82.03 0.074
77.17 = 0.69
88.33 +: 0.45
OOM
58.32
1 0.05
OOM
54.40 1: 2.31
Random
0.52 78.29
94.16 0.06
70.47
0.24
GRAPES-RL (ours)
87.62 + 0.48
78.75
0.35
89.40 + 0.34
94.09
0.05
62.58
71-45 0.20
76.88 + 0.33
GRAPES-GFN (ous)
87,29 0.32
78.75 0.33
89.46
94.30 0.06
61.86
0.51
70.66 0.30
77.14 + 0.48
Rank
Table 2: F1-scores (%) for different sampling methods trained on heterophilous graphs for batch size of 256, and sample size of 256 per layer. We report the mean and standard deviation over 10 runs. The best values among the sampling basclines (all except GAS) are in bold, and the second best are underlined. MC stands for multi-class and ML. stands for multi-label classification. OOM indicates out of memory.
Dataset
Flickr
snap-patents h 0.22 MC
Yelp 0.22 ML
ogbn-proteins 0.15 MI
BlogCat
Homophily
h 0.31 MC
0.1 ML
Task
GAS
49.96 0.28
38.04 + 0.20
37.81 + 0.07
7.55 0.01
6.07 0.04
FastGCN
46.40 = 2.51
29.68 + 0.61
29.29 + 4.39
7.80 + 0.55
6.44 0.41
LADIES
47.19 3.42
29.09 + 1.88
18.92 + 3.18
4.31 + 0.11
6.74 0.67
GraphSAINT
48.01 + 1.44
28.01 + 0.57
34.68 + 0.70
9.94 + 0.07
6.89 + 0.96
AS-GCN
48.42 = 1.20
31.04 + 0.19
38.51 + 1.45
5.20 + 0.36
5.43 0.54
PASS
44.49 = 0.76
0OM 29.74 + 0.34
OOM
7.71 0.12
6.88 0.59
Random
49.39 0.23
40.63 + 0.13
10.82 + 0.05
7.13 + 0.97
GRAPES-RL (ours)
49.54 + 0.67
29.16 + 0.54
40.69 + 0.55
11.78 + 0.14
9.06 0.68
GRAPES-GFN (ours)
49.29 + 0.32
29.58 + 0.24
44.57 + 0.88
11.57 + 0.18
9.22 + 0.40
Rank
and multi-label datasets in which a node can be assigned one or more labels. As shown in the literature (Zhu et al., 2020; Zhao et al., 2023), we argue that node classification with GCN is more challenging on these datasets compared to multi-class classification on homophilous graphs, where an adaptive policy could be beneficial. In particular, we run experiments with the following datasets for the node classification task:
Homophilous graphs: citation networks (Cora, Citeseer, Pubmed with the "full" split) (Sen et al., 2008; Yang al., 2016), Reddit (Hamilton et al., 2017), ogbn-arxiv and ogbn-products (Hu al., 2020), and DBLP (Zhao et al., 2023).
Hetcrophilous graphs: Flickr (Zeng al., 2019), Yelp (Zeng et al., 2019), ogbn-protcins (Hu et al., 2020), BlogCat (Zhao et. al., 2023), and snap-palents (Leskovec & Krevl, 2014).
We included the edge homophily ratio (Zhu al., 2020) of all the datasots Table 1 and 2. For the multi-label datasets, we followed the same framework in (Zhao al., 2023) calculate their label homophily ratio. Statistics about the datasets be found in Appendix C.
9

---

GRAPES-12 Published in Transactions on Machine Learning Research (05/2025)
6.2 Results
Comparison with sampling methods We present the F1 scores of GCNs trained via sampling for GRAPES and the sampling- saasliin-basod basclines Table and 2. We observe that on the majority of hetcrophilous datascts, and all the heterophilous multi-label datasets, both variations of GRAPES achieve the highest Fl-score. As mentioned earlier, node classification on heterophilous graphs is a challenging task for GCNs, due to the diversity of the neighbor nodes' labels. Our results suggest that GRAPES ability to adapt the sampling policy to particular features of the data allows GRAPES to learn the complex patterns across the heterophilous datasets. Table 1 shows that on most homophilous graphs, AS-GCN achieves the highest F1-score, indicating the importance of adaptive sampling. However, unlike GRAPES, this method is only adaptive to the sampling variance and fails to outperform GRAPES on the heterophilous graphs. Moreover, our results show that PASS, another adaptive method, is unable compete with GRAPES and results in an out-of tifoofo-mmrryy error several large datasets. This is due to its node-wise sampling feature, which results in disconnected sampled graph.
FastGCN and LADIES, which use a fixed policy, fail to compete with the other methods in our experimental setup. They assign a higher probability to nodes with higher degroes. This hcuristic results in neglecting informative low-degree nodes, Although outperforming LADIES and FastGCN, GraphSAINT, which also uses fixed sampling policy, fails to outperform the more competitive baselines. We observe that on some datasets, Random sampling achieves comparable Fl-scorr to GRAPES and the baselines. This mainly happens on simple datasets, such homophilous graphs, indicating that on these graphs, a simple sampling approach is sufficient.
Comparison with a non-sampling scalable method GAS (Fey et al., 2021) is a non-sampling method that uses the historical embeddings of the 1-hop neighbors of the target nodes. We present classification results in Table 2, and we visualize memory usage in Fig. 3. While GAS has higher clas- sification Fi-scores for some datascts, GRAPES achieves comparable Fi-scores and significantly out- performs GAS for Yelp, ogbn-proteins, and BlogCat, all heterophilous multi-label graphs. Once again, these results indicate the effectiveness of the adaptivity of GRAPES in sampling influential nodes in complex graphs. For the memory usage, we compare GAS with AS-GCN and the GFlowNet version of GRAPES-32 and GRAPES-256, where 32 and 256 (the default value) indicate the sample size per layer.
The memory usage results show that, even with a large sam- ple size, GRAPES can use up to an order magnitude less GPU memory than GAS, especially for large datasets. In large, densely connected graphs such as Reddit, the 1-hop neighbor- hood can be massive. Then, the difference in memory use for GRAPES, which only sees small set of neighbors, and GAS, which uses all the neighbors, is significant. While GAS occa- sionally achieves higher F1-scores, it consistently demands more memory, indicating a potential compromise between accuracy and computational efficiency. In contrast, GRAPES strikes a balance, delivering comparable Fl-score with more modest memory footprints. In most cases, GRAPES also uses less memory than AS-GCN, another sampling-based baseline. In other cases, GRAPES uses more memory than AS-GCN which we attribute to the fact that there is an additional GNN in GRAPES for lcarning the sampling policy. Some variations are due to implementation details", though general we observe significant advantage of layer-wise sampling methods over historical embeddings.
Memory (MB) Log Scale
10
GRAPES-256
AS-GON
GAS
10p
Cara
Citeeses
Pubuned
Reddi
Flick
Yelp
ogbut-rdir
agla--poodart
Figure 3: GPU peak memory allocation (MB) for GAS, and GRAPES-GFN-32 and GRAPES-GFN-256.
GRAPES is robust to low sample sizes. A desirable property of sampling methods, in contrast with full-batch GNNs or methods like GAS (which relies on historical embeddings), is the ability to control the sample size to reduce memory usage as needed, To study this property, we show in Figure 4 the effects of
'We used PyTorch for our implementation, whereas AS-GCN implemented in Tensorflow, which manages GPU memory differently.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Reddit
Flickr
Yelp
ogbn-arxiv
Node Classifictiin FJ 11--soores
160
35
ASGCN
70
GRAPPS GRAPOS
30
45
25
64
Er
Fr
Sample Size (logarithuiic base-2)
Figure 4: Comparative analysis of classification accuracy across different sampling sizes for sampling baseline and GRAPES. We repeated each experiment five times: The shaded regions show the 95% confidence intervals.
ogln-products
DBLP
Moan Entropy
0.8
0.4
I-hop node sumpling
2 hop node sampling
0.0
16
20
30
1
50
60
10
80
90
100
11
20
50
60
10
80
50
100
Epoch
Epoch
Figure 5: Entropy for the ogbn-products and DBLP datascts. The mean is the entropy in bits of the node probability, averaged over nodes. The shaded region indicates the standard deviation the entropy over all nodes.
varying the sample size on Reddit, Flickr, Yelp, and ogbn-arxiv. Our results show that both the RL and GFN variants of GRAPES are robust to low sample size, and achieve strong performance with fewer sampled nodes needed than the baselines, enabling training GCNs on larger graphs while using less GPU memory. Random sampling also exhibits robustness to sample size for all datasets except Yelp, where accuracy drops in larger sample sizes. GRAPES-RI. shows the same behavior while performing slightly better than Random Yelp. AS-GCN and GraphSAINT show the largest dependence sample size, especially Flickr and Yelp.
GRAPES learns strong preferences over nodes. The ability to selectively choose influential nodes is a crucial property of GRAPES. Figure 5 shows the mean and standard deviation of base 2 entropy for the node preference probabilities for the two layers of GCNg for ogbn-products and DBLP for GRAPES-GEN The probabilities show preference towards particular nodes with a Bernoulli distribution. well-trained model must have high preference (probability close to 1) for some nodes and low preference (probability close to 0) for the rest. Therefore, would like low average entropy with high standard deviation. As the figure shows, the mean entropy in both layers decreases from almost and converges to value above 0, while the standard deviation incrcases. This indicates that for ogbn-products, the sampling policy initially assigned a probability near 0.5, indicating little preference. However, after several training epochs, GRAPES starts preferring some nodes, resulting in lower mean entropy. We observe similar behavior for most datasets (DBLP, BlogCat, Yelp, ogbn-arxiv, and ogbn-protcins). However, we observe that the sampling policy exhibits no preferences among the nodes for the other datasets. For more details about the other datasets, see Appendix D.
11

---

Published in Transactions on Machine Learning Research (05/2025)
7 Known Limitations and Future Work
Our experimental results show that GRAPES outperforms the baselines on some, but not all, heterophilous datasets. We provide a theoretical analysis that shows the effectiveness adaptive sampling on certain types of heterophilous graphs. Further analysis is required to understand which graph characteristics contribute to the performance gain observed with adaplive sampling methods such as GRAPES.
Morcover, in our experiments, we focused only on the problem of node classification. However, GRAPES is not tied to particular downstream task. GRAPES assumes access to tractable reward function (Bengio et al., 2021b). Therefore, GRAPES will be applicable for other graph-related tasks, like link prediction and unsupervised representation learning.
Additionally, there is room for a more thorough investigation of the properties of the subgraphs that GRAPES samples. The experiments at the end of Section 6.2 and in Appendix D are a first step towards this. We leave these directions for future work.
Another direction for future work is applying GRAPES to architectures designed to address heterophily, such as the ones proposed by Zhu et al. (2020); Abu-Fl-Haija et al. (2019). By leveraging GRAPES, these architectures could potentially overcome their scalability issucs.
8 Discussion, Broader Impacts, and Conclusion
We propose GRAPES, an adaptive graph sampling method based on reinforcement learning and GFlowNet,, facilitating the scalability of training GNNs on massive graphs. GRAPES samples subgraph of influential nodes by learning node preferences that adapt to classification loss, which depends on node features, GNN architecture, classification task, and graph topology. Our experiments demonstrate that GRAPES effectively selects nodes from large-scale graphs and achieves state-of-the-art performance in multi-label classification tasks on heterophilous graphs, while performing competitively for multi-class classification on homophilous graphs. Compared to the other sampling methods, GRAPES can maintain high classification accuracy even with lower sample sizes, indicating GRAPES' ability scale to larger graphs by sampling a small but influential set of nodes. GRAPES achieves comparable performance to GAS, while using up to an order of magnitude less memory.
Focus on Hctcrophily in Sampling. Previous works have overlooked the impact of sampling on heterophilous and multi-label graphs. To our knowledge, this is the first work to compare sampling effects on both homophilous and heterophilous graphs, where adaptive sampling is especially crucial due to the diversity among neighbors, making node selection vital for GNN accuracy.
Lack of Uniform Evaluation Protocol. Existing methods in the literature report performance on graph sampling under settings with different GCN architectures, regularization techniques, feature normalization strategies, and data splits, among other differences. These differences made it challenging to determine the benefits of each sampling method. This motivated us to implement unified protocol across all methods, where we keep the architecture fixed. We encourage future work to consider a similar methodology for fair evaluation, or an experimental review study, as is common in other areas of machine learning research on graphs (Shchur et al., 2018; Ruffinelli et al., 2019).
Broader Impacts. Our paper focuses on fundamental research to understand and advance sampling in largo-scale graphs. There may be multiple potential socictal consequences of our work, but there are none that can be easily predicted and specifically highlighted.
Acknowledgements
Taranch Youncsian was funded by Huawei DREAMS Lab. All content represents the opinion of the authors, which not necessarily shared nor endorsed by their respective employers and/or sponsors in Huawei DREAMS Lab. Daniel Daza. was partially funded by Flsevier's Discovery Lab. Emile Krieken was
12

---

Published in Transactions on Machine Learning Research (05/2025)
funded by ELIAI (The Edinburgh Laboratory for Integrated Artificial Intelligence), EPSRC (grant EP/W002876/1), We thank Michael Cochez and Ruud van Bakel for insightful discussions.
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazamin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21-29. PMLR, 2019.
Sami Abu-El-Haija, Joshua V Dillon, Bahare Fatemi, Kyriakos Axiolis, Neslihan Bulut, Johannes Gasteiger, Bryan Perozzi, and Mohammadhossein Bateni. Submix: Learning to mix graph sampling heuristics. In Uncertainty Artificial Intelligence, pp. 1 10. PMLR, 2023.
Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. SIMPLE: A gradient estimator for k-subset sampling. In The Eleventh International Conference Learning Representations, 2023.
Aamir Anis, Akshay Gadde, and Antonio Ortega. Efficient sampling set selection for bandlimited graph signals using graph spectral proxies. TEEE Transactions on Signal Processing, 64(14):3775-33 3789, 2016.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34:27381-27388 2021a.
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, abs/1306 bas//108.3432, 2013. URL http://arxix: http:://axxvv.orrgpp abs/1308.34r 3432.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. arXiv preprint wxXfv2211.00990 2021b.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL available from wandb.com.
Software
Jianfei Chen, Jun Zhu, and Te Song. Stochastic training of graph convolutional networks with variance roduction. In International Conference on Machine Learning, pp. 942-950. PMLR, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, ICLR 2018, Conference Truck Proceedings. OpenReview.no net, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gent An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data miningg pp. 257 266, 2019.
Weilin Cong, Rana Forsati, Mahunut Kandernir, and Mehrdad Mahdavi. Mininal 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, pp. 1393-1403, 2020.
Zicun Cong, Baoxu Shi, Shan Li, Jacwon Yang, Qi He, and Jian Pei. Fairsample: Training fair and accurato graph convolutional neural networks efficiently. IEEE Transactions on Knowledge and Dala Engineering, 36(4):1537-156) 2023.
Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. In Uncertainty in Artificial Intelligence, pp. 518-528. PMLR, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorrh Geometric, In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International conference machine learning, pp- 3294 3304. PMLR, 2021.
Wenhao Gao, Tianfan Fu, Jimeng Sun, and Connor Coley. Sample efficiency matters: a benchmark for practical molecular optimization. Advonces in Neurol Information Processing Systems, 35:21342 21357, 2022.
Haoyu Geng, Chao Chen, Yixuan He, Gang Zeng, Zhaobing Han, Hua Chai, and Junchi Yan. Pyramid graph neural network: graph sampling and filtering approach for multi-scale disentangled representations. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 518-530, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neurol Networks, 2(5):359 366, 1989. doi: 00.1006/0899-60888 (1880(89900000) URL https: //doi..or//// 1ttg//1.111 wwwrg//..111///// 10110111111000000000000 (89) 90020-8.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advonces in newral information processing systems, 33:22118-222 11112223,332 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems, 31, 2018.
Iris AM Huijben, Wouter Kool, Max B Paulus, and Ruud JG Van Sloun. A review of the gumbel-max trick and its extensions for discrete stochasticity in machine learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):1353 1371, 2022.
Moksh Jain, Emmanuel Bengio, Alex Hernandez-Garre Jarrid Rector-Brooks, Bonaventure FP Dossou, Chanakya Ajit Ekbote, Jie Fu, Tianyu Zhang, Michael Kilgour, Dinghuai Zhang, et al. Biological sequence design with gflownets. In International Conference on Machine Learning, pp. 9786-9801. PMLR, 2022.
Moksh Jain, Tristan Deleu, Jason Hartford, Chong-Haa Hao Liu, Alex Hernandez-Garcia, and Yoshua Bengio. Gftownets for Al-driven scientific discovery. Digital Discovery, 2(3):537-577, 2023.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900 6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ar preprint arXic:1609.0229 02907, 2016.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: 2014.
//snap. www.sorr..du..uuoooooo
Michelle M Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, 6(12):1353-133 1369, 2022.
Wenqian Li, Yinchuan Li, Zhigang Li, Jianye Hao, and Yan Pang. Dag maiters! gllownets enhanced explainer for graph neural networks. Xixiv preprint arXiv:2303.0 02448, 2023.
Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang, Le Song, and Yuan Qi. Bandit samplers for training graph neural networks. Advances in Neural Information Processing Systems, 33:6878-6888, 2020.
Zirui Liu, Kaixiong Zhou, Zhimong Jiang, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. Dspar: An embarrassingly simple strategy for efficient gnn training and inference via degree- Transactions Machine Learning Research, 2023.
based based sparsification.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Lu Ma, Zeang Sheng, Xunkai Li, Xinyi Gao, Zhezheng Hao, Ling Yang. Xiaonan Nie, Jiawei Jiang, Wentao Zhang, and Bin Cui. Acceleration algorithms in gnis: A survey. IEEE Transactions on Knowledge and Data Engineering, 2025.
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment in gflownets. Advances in Neural Information Processing Systems, 35:5955-5967, 2022a.
Nikolay Malkin, Salem Lahlou, Tristan Deleu, Xu Ji, Edward Hu, Katie E Everett, Dinghuai Zhang, and Yoshua Bengio. Gflownets and variational inference. In The Eleventh International Conference Learning Representations, 2022b.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. Journal of Machine Learning Research, 21:132:1-132:66 2020.
David F Nettleton. Data mining of social networks represented as graphs. Computer Science Review, 7:1 34, 2013.
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations, 2019.
Luana Ruiz, Luiz FO Chamon, and Alejandro Ribeiro. Transferability properties of graph neural networks. IEFE Transactions on Signal Processing, 2023.
Prithviraj Sen, Galileo Namala, Mustala Bilgie, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9)) 93, 2008.
Marco Serafini and Hui Guan. Scalable graph neural network training: The case for sampling, ACM SIGOPS Operating Systems Review, 55(1):68-74 16, 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network cvaluation. arXiv preprint arXiv:1811.0550 1.811.100866.. 2018.
Zhihao Shi, Xize Liang, and Jie Wang. Lmc: Fast training of gnns via subgraph sampling with provable convergence. arxiv preprint arXiv:2302. 00924, 2023.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20):10 48550, 2017.
Tim Vieira. Gumbel-max trick and weighted reservoir sampling, 2014. URL http://tiiniiiiirr .irraa.iittubbb.. /o/ http:///mmmmmmmmmaemaee - aanddd-e.ggtee---eeevv---aaaaaaa
blog//pstt/2014/88/011/////
Yu Wang, Zhiwci Liu, Ziwci Fan, Lichao Sun, and Philip S Yu. Dskreg: Differentiable sampling on knowledge graph for recommendation with relational gnn. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 5513-3517 2021.
Ronald J. Williams. Simple statistical gradient-following algorithns for connectionist. reinforcement learning. Machine Learning, 1992. ISSN 0885-6125. doi: 10.10077/b000992666.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: a survey. ACM Computing Surveys, 55(5):1-31) 2022.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp- 40-48. PMLR, 2016.
Minji Yoon, Théophile Gervet, Baoxu Shi, Sufeng Niu, Qi He, and Jaewon Yang. Performance-adaative sampling strategy towards fast and accurate graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 2046-2056, 2021.
Haoran You, Zhihan Lu, Zijian Zhou, Yonggan Fu, and Yingyan Lin. Early-bird gens: Graph-network co-optimization towards more efficient gen training and inference via drawing early-bird lottery tickets. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 36(8), pp. 8918, 2022.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Haiyang Yu, Limei Wang, Bokun Wang, Meng Liu, Tianbao Yang, and Shuiwang Ji. Graphfın: Improving large-scale gnn training via. feature momentum. In International Conference on Machine Learning, pp- 25684 25701. PMLR, 2022.
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. arXiv preprint arXiv:190.0044 04981, 2019.
Guibin Zhang, Kun Wang, Wei Huang, Yanwei Yue, Yang Wang, Roger Zimmermann, Aojun Zhou, Dawei Cheng, Jin Zeng, and Yuxuan Liang. Graph lottery ticket automated. In The Twelfth International Conference on Learning Representations, 2024.
Tianqi Zhao, Ngan Thi Dong, Alan Hanjalic, and Megha Khosla. Multi-label node classification on graph- structured data. Trans. Mach. Learn. Res., 2023, 2023.
Xin Zheng, Yi Wang, Yixin Liu, Ming Li, Miao Zhang, Di Jin, Philip S Yu, and Shirui Pan. Graph neural networks for graphs with heterophily: A survey, arXiv preprint arXiv:2202.07088, 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793 7804, 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. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pp. 11247-11256, 2019.
A Off-Policy Sampling Setup
In this Appendix, we discuss the technical and mathematical challenges around our setup that resulted in our off- off-policy learning setup. In each layer I of the GFlowNet, we aim to sample exactly k out of n nodes. An initially natural sctup would be to use the distribution over k-subsets of ((((-)) (Ahmed et al., 2023). Using Bayes theorem,
]| = k))()>()) D10) ....,)((-I))) ((-1))
(((-))))) k)) Eveen [[)' = k) k)
..., V(-1)))
When conditioned on k, q assigns O probability to sets of nodes y( that do not sample exactly k new nodes (that is, when [D0] * k).. However, this requires renormalizing the distribution, which is the function of the denominator term the right-hand side. Note that this sum is over an exponential number of elements, namely 2| ""), and naive computation clearly intractable. SIMPLE (Ahmed et al., 2023) provides an optimized dynamic programming algorithm for computing this normalization constant. However, it scales polynomially in (((() and k, and in our experiments, computing the normalizer is a bottleneck already for mid-sized graphs like Reddit.
Therefore, we decided to circumvent having to compute (())) DU-1),)) k) by sampling using the Gumbel-Top-k trick (Fquation 4) to ensure we always add exactly k nodes. However, we are now an off-policy sctting: The samples using Equation 4 are distributed by q(V(ippt)) ..... v(-)), k), not by q(V(D) ((0))) ..., v(-1)), and so we sample from a different distribution than the one we use to compute the loss. Previous work (Malkin et al., 2022b) showed that the Trajectory Balance loss is amenable to off-policy training without importance sampling and weighting without introducing high variance. This is important since importance weighting would require us to weight by (()())())) ..... ,...., (((()))((((())))))
v(-11, k),
reintroducing the need to compute (()))) V(I1)),)) ((-,), k).
The off- off-policy benefits of the Trajectory Balance loss provide a strong argument over more common Reinforce- ment Learning setups. Off-policy training in Reinforcement Learning usually requires importance weighting to be stable, which is not tractable in our setting.
16

---

Published in Transactions on Machine Learning Research (05/2025)
B Experimental Details
For all experiments, we used as architecture the Graph Convolutional Network (Kipf & Welling, 2016), with two layers, & hidden size of 256, a batch size of 256, and a sampling size of 256 nodes per layer. We implemented the GCNs in GRAPES via PyTorch Geometric (Fey & Lenssen, 2019). We train for 50 epochs on Cora, Citeseer, and Reddit; 100 epochs on BlogCat, DBLP, Flickr, ogbn-products, Pubmed, snap-patents, and Yelp; and 150 epochs on ogbn-arxiv and ogbn-proteins. The ogbn-proteins and BlogCat datasets do not contain node features, and instead we learn node embeddings for them of dimension 128 for ogbn-proteins, and 64 for BlogCat.
Our experiments were carried out in a single-node cluster setup. We conducted our experiments on a machine with Nvidia RTX A4000 GPU (16GB GPU memory), Nvidia A A100 (40GB GPU memory), and Nvidia RTX A6000 GPU (48GB GPU memory) and each machine had 48 CPUs, In total, we estimate that our experiments took 200 compute days.
B.1 Hyperparameter Tuning
We tune the hyperparameters of GRAPES using a random search strategy with the goal of maximizing the accuracy of the validation dataset. We used Weights and Biases for hyperparameter tuning 5. The best-performing hyperparameters for every dataset can be found in our repository https://anonymot 4open. www.eeeee/eeee////....... The following are the hyperparameters that we tuned: the learning rate of the GFlowNet, the learning rate of the classification GCN, and the scaling parameter a. We used the log uniform distribution to sample the aforementioned hyperparameters with the values from the following ranges, respectively, [le - 6, 1c 11e-22 2). [le - 6, le - 2], and [1c2, 1c6]. We kept the other hyperparameters, such as the batch size and hidden dimension of the GCN. We used the Adam optimizer (Kingma & Ba, 2014) for GCNc and GCNs.
We did a hyperparameter sensitivity analysis performed using Weights & Biases Biewald (2020) for training of GRAPES-GFN Yelp. Importance measures how strongly each parameter influences the validation accuracy (higher = more critical), while correlation shows the direction and magnitude of the lincar relationship (positive = increasing the parameter tends to increase the accuracy, negative the opposite). From the table below, byge. the learning rate for the classification GCN, has the strongest effect on accuracy and is negatively correlated, suggesting that higher learning rates can harm performance. Meanwhile, lrgf and a show smaller impacts and weaker corrclations, indicating that the model is less affected by changes these two parameters.
Table 3: Importance and correlation of configuration parameters for training GRAPES-GEN on Yelp.
Config Parameter
Importance
Correlation
Ir __
0.633
-0.610
Ir gf GCN)
0.280
0.055
a
0.087
0.097
B.2 Baselines
For a fair comparison, we adjusted the implementations of the baselines so that the only difference is the sampling methods and the rest of the training conditions are kept the same. In the following, we explain the details of the modifications to each of the basclines.
For LADIES, we used the official implementation, which also contains an implementation of GCN. We changed the nonlinear activation function from ELU to ReLU, and removed any linear layers after the two layers of the GCN, set dropout to zero, and disabled carly stopping. We also noticed that the original LADIES implementation divided the larget nodes into mini-balches, not from the entire graphs as we do,
/nttps://vandb..
17

---

Published in Transactions on Machine Learning Research (05/2025)
Table 4: Differences in experimental setups in related work, obtained from the original publications and their official implementations. "This indicates the total budget in terms of nodes sampled across all layers.
Fos (Chen al, 9018b) LADIRS
GrophSAINT (Zong
AS-GON (Huung al,, 2018)
GAS (Ray al., 2021)
Ardaltetiure
GCN
CCX
GCN
GCN otteatons (16,200) 2
GUN.OUNILGAAL (276, G12, 1824, 2048) 4. G1) (1.2 (1.22,,0.122.000)
GAA...A...PPPPEEEACC.. APPNEPNA
Hilde dae
(16, 125)
596
(126, 566, 312, 2045) 02, 5) (40), 512, T000) (4000) 9X00 9000) 2000
Number of lysrs
5
Batch sise
(336, 1084)
512 [5, 61, 517) 300
255
Nedes per layer
(100, (97)
[178, 955, 512) (90/000,200)
No sampling
Training epucits
[103, 900, 300;
2200, (0), 500, 1000)
but into random fragments. This means that LADIES and FastGCN do not see all the target nodes in the training data. We kept this setting unchanged because otherwise it would have siguificantly slowed down the training of these two methods.
For GraphSAINT, we noticed that the GNN consists of two layers of higher-order aggregators, which are a combination of GraphSage-mean (Hamillon et al., 2017) and MixHop (Abu-EI-Haijee et al., 2019), and linear classification layer at the end. Moreover, the original implementation of GraphSAINT is only applicable to inductive learning on the graphs, where the training graph only contains the training nodes and is entirely different from the validation and test graphs, where only the nodes from the validation set and test are available, respectively. We argue that in transductive learning, unlike inductive learning, the motivation to scale to larger graphs is higher since the validation and test nodes are also available during training, and therefore, the processed graph is larger. Finally, to keep all the configurations the same as GRAPES, we used PyTorch Geometric's function for GraphSAINT Random Walk sampler with depth two, which showed the best performance across the three variations of GraphSAINT. Therefore, we use the same GCN and data loader (transductive) ours and use GraphSAINT to sample subgraph of nodes for training. We use the node sampler setling since it is the only setting that allows specilying different sampling budgets, and therefore, can be compared to layer-wise methods with the same sampling budget. We also removed the early stopping and used the same number of epochs as GRAPES. Note that for Figure 4, we need to change the sample size while the Random Walk sampler can only sample equal to the batch size per layer. Therefore, for these experiments, we used the Node Sampler version of GraphSAINT, which allows us to change the sample size. For instance, for sample size 32 per layer, we set GraphSAINTTs Node Sampler's sample size to 256 + 32 + 32 320 to sample subgraph with 320 nodes. Please refer to repository for more details about the implementation of GraphSAINT.
For GAS, we used the original implementation. However, we changed the configuration of the GCN to have a two-layer GCN with 256 hidden units. We turned off dropout, batch normalization and residual connections in the GCN. We also removed early stopping for the training.
For AS-GCN we removed the attention mechanism used in the GCN classifier. Their method also uses attention in the sampler, which is separate from the classifier, we keep it.
For PASS, we changed the inference to full-batch to match the rest of the basclines. We set the parameter sampling_scop scope to 512, because in the original experiments of the paper, this value was set to twice the batch size. For Flickr, ogbn-arxiv, and ogbn-proteins, this value results in OOM; therefore, we set it to 128, 128, and 256, respectively. For the datasets that we report 00M in tables and 2, we tested all possible sampling_scop between 512 and 16.
C Dataset statistics
We present the statistics of the datasets used in our experiments in Table 5. The splits that we used for Cora, Citeseer, and Pubmed correspond to the "full" splits, in which the label rate is higher than in the "public" splits. For BlogCat, we take the average accuracy of all the mothods across the three available splits provided by (Zhao et al., 2023). For DBLP and snap-patents, we use the average of ten random splits because these two datasets had predefined splits.
18

---

Published in Transactions on Machine Learning Research (05/2025)
Table 5: Statistics of the datasets used our experiments. The label rate indicates the percentage of nodes used for training. ogbn-proteins and BlogCat do not contain node features, and instead, we learn embeddings for nodes in these datasets.
Dataset
Task
Nodes
Edges
Features
Classes
Label Rate (%)
Cora
multi-class
2,708
5,278
1,433
7
44.61
CiteSeer
multi-class
3,327
4,552
3,703
6
54.91
PubMed
multi-class
19,717
44,324
500
3
92.39
Reddit
multi-class
232,965
11,606,919
602
41
65.86
DBLP
multi-label
28,702
136,670
300
4
80.00
Flickr
multi-class
89,250
449,878
500
7
50.00
snap-patents
multi-class
2,923,922
27 27,945,092
269
5
50.00
Yelp
multi-label
716,847
6,977,409
300
100
75.00
ogbn-proteins
multi-label
132,534
79,122,504
112
65.30
BlogCat
multi-label 10,312
667,966
39
60.00
ogbn-arxiv
multi-class
169,343
1,157,799
128
40
53.70
ogbn-products
multi-class
2,449,029
61,859,076
100
47
8.03
D Entropy as Node preference measure
Figures and show the mean and standard deviation of entropy in base two of all the datasets. We calculate the mcan entropy as the following:
log)(p)) + (1 -0-ppp p.) .logg -p;)
(8)
where n is the number of neighbors of the nodes sampled in the previous layer and ps is the probability of inclusion for each node, which is the output of the GFlowNet. As the figures show, for certain small datasets (Cora, Citeseer, Pubmed, Flickr) the mean entropy is: 1) very close to 1, indicating that GRAPES prefers every nodes with the probability close to 0.5, or 2) close to but also with a low standard deviation, meaning that it oqually prefers the majority of the nodes with the probability or 0. On the contrary, for the large datasets (Reddit, Yelp, ogbn-arxiv, ogbn-groode prooupsrducts) by the end of training, the average entropy is lower than 1, with standard deviation around 0.3 indicating that GRAPES learns different preferences over different. nodes, some with a probability close 1, and some close to
We analyzed the label distribution of the sampled subgraphs via GRAPES-GE for Yelp, by counting the percentage of nodes having each label and calculating the difference between the original and sampled graphs, ie., percentage of nodes having label e in the original graph minus percentage of nodes having label e in the sampled graph. As shown in the figure, all the values are positive, indicating that a higher ratio of nodes have each label in the original graph. Moreover, this difference increases at the end of training. This means that among the 100 labels in Yelp, GRAPES prefers the nodes with fewer labels or that are even single-labcled. This may make the classification task easier and result in lower loss. Moreover, among the 100 classes, some are sampled the most and some the least. Figure 8 below shows this trend.
E GPU Memory usage comparison between GRAPES and GAS
We compared different variants of GRAPES, with different sample sizes (32, 256), with GAS (Fey et al., 2021), which non-sampling method. Figure 3 shows the GPU memory allocation (MB), on logarithmic scale for GRAPES-32. GRAPES-256, and GAS. The three graph methods exhibit distinct performance characteristics across various datasets. We used the max _aax__mmor____ allocated function in PyTorch to measure the GPU
19

---

Published in Transactions on Machine Learning Research (05/2025)
Cieeser
Cora
1.0g
0.8
Moan Entropy
0.55
1-hop node sampling
0.2
2-hop node sampling
0.4
10
15
20
25
30
35
50
10
15
20
25
30
35
45
50
Fliekr
ogbn-arxiv
1.0g
0.5
Moan Ennrrppy
0.4
0.2
0.4
100
30
75
90
106
150
oggn-proddcct
Pubmed
1.0g
Mean Entropy
0.4
0.2
0.0
100
Roddlt
Yelp
1.0
Moan Entropy
0.4
0.4
70
Epoch
Epoch
Figure 6: Combined entropy plots for Cileseer, Cora, Flickr, ogbn-arxiv, ogbn-products, Pubmed, Reddit, and Yelp showcasing the mean entropy. The shaded region indicates the standard deviation of the entropy across nodes. The plots compare 1-hop node sampling against. 2-hop node sampling.
memory allocation. Since this function measures the maximum memory allocation since the beginning of the program, where the memory measurement is done is not relevant.
F
GFlowNet details
This section provides additional details on GelowNets general and the GFlowNet version of GRAPES.
20

---

Published in Transactions on Machine Learning Research (05/2025)
BlogCat.
Emap-poteents
1.0
I-hop node sampling
Moan Entropy
0,34
2-hop node sampling
0.55
0.4
0.2
0.40
10
20
30
10
60
10
50
90
100
10
20
30
40
50
60
70
50
90
100
DBLP
oggn-pproteing
1.0
Moan Eahropy
0.8
0.5
0.4
0.40
10
20
30
50
60
50
100
15
30
45
60
90
105
120
135
150
Epoch
Epoch
Figure 7: Combined entropy plots for BlogCat, snap-patents, DBLP, and ogbn-proteins, showcasing the mean entropy across epochs. The shaded region indicates the standard deviation the entropy across nodes. The plots compare I-hop node sampling against 2-hop node sampling.
Original Sampled Epoch
Diff First Epoch vs Last Epoch
80
Original Graph
Difference Nodes having the (sbell%))
Fpoch
Sampled Graph
16
Dif' Last Epoch
70
60
12
50
10
having
30
20
0
20
40
60
80
100
20 40
60
80
100
Label
Label
Figure 8: Comparison of Label distributions between GRSAPES GFNN and the original graph for Yelp. The left figure shows the percentage of nodes in the last epoch of both graphs that have cach label. The right shows the difference between those percentages in the original graph and the sampled graph at the beginning and end training.
F.1 Generative Flow Networks
Generative Flow Networks (GFlowNets) (Bengio al., 2021a;b) generative models that sample from very large structured space. GFlowNets construct the structure in multiple generation steps. Compared to Reinforcement Learning approaches, GFlowNets learn to sample in proportion to a given reward function, while in Reinforcement Learning, reward functions are maximized. This feature of GFlowNets encourages sampling diverse sets of high-quality structures, instead of only considering the single best structure. GFlowNets have been used in several applications like molecule design and material science (Bengio et al., 2021a; Gao al., 2022: Jain et al., 2022), Bayesian structure learning (Deleu et al., 2022), scientific discovery (Jain al., 2023), and GNN explainability (Li et al., 2023). Similar to work, the latter utilizes Get to sample
21

---

Published in Transactions on Machine Learning Research (05/2025)
subgraphs. However, this method explains trained GNN and is not used to scale GNN training to large graphs.
F.2 GFlowNet and Trajectory Balance Loss
We first give a brief overview of GFlowNetts (Bengio el al., 2021a;b) and the trajectory balance loss (Malkin et al., 2022a). Let GF = (S, Sy, R) denote GFlowNet learning problem. Here, S is a finite set of states that forms a directed graph with A, a set of directed edges representing actions or transitions between states. So C S is the set of initial states, S, CS is the set of terminating states," and R S + R+ is the reward function defined on terminating states. At time 1, particular a E AA indicates the action taken to transition from state (t-11) to s(4), A trajectory T is a path through the graph from an initial state (()) to a terminating state s(n) E Sy: T == (s(0) +... + (())). A GelowNett is a neural network that learns to transition from an initial state (0)) to a terminating state where the reward R(s(m)) is given. The goal of the GFlowNet is to ensure that following the forward transition probabilities
lcads to final states Sy with probability in proportion to the reward R (Bengio et al., 2021a). The Trajectory Balance (TB) loss (Malkin et al., 2022a) is developed with this goal. For trajectory (s(0) -... - s( the TB loss is:
((s(0)) Ih= Pr (((t)))(((-1)) log R(s(m) I PB Pa( (((((11))(((1))
CTB(T)
where Z: Su - R2+ computes the total flow of the network from the starting state s(0) and Pp and Ps are the forward and the backward transition probabilities between the states, where both can be parameterized by a neural network (Malkin et al., 2022a).
F.3 GFlowNet Design: States, Actions, and Reward
Next, we explain our choice of Gr, that is, the states, actions, terminating states, and reward function, and the coupling of our GFlowNet with the sampling policy q. A state s(f-1) E 8 represents a sequence of sets of nodes 1(-- (y(0).... ..... (((-1) sampled so far. An action from s!-11) represents choosing k nodes without replacement among (())))))). This forms the set of nodes y(4) in the next layer. Therefore, in an T. layer GCN, we construct a sequence of L sets of nodes to reach a terminating state.
We define the optimal sampling policy as having the lowest classification loss in expectation. Therefore, a set of nodes with a lower classification loss than another set must have a higher probability. Our goal is to design Ge so that it learns the forward and backward transition probabilities proportional to a given reward. We define the reward function as below:
R(s(D) = R(V D(A)) exp(-a Lo(X,Y, K()) K(b))),
(10)
where Le is the classification loss and is scaling parameter, which we explain in Section F.4.
Forward Probability. The forward probability (r(( in GRAPES is the sampling policy ((V(0) (10)) .t....... ((-1)) defined in Section 4.1.
Backward Probability. Trajectory balance (Equation 9) also requires defining the probability of transi- tioning backwards through the states. The backward probability is a distribution over all parents of a state.
This distribution not required in our setup, as the state representation s(!) = (V(9) ...., D(0) saves the trajectory taken through GF to get to s!)) This means the graph for the GFlowNet learning problem OF is tree, each state s()) (VX0) ,..., (11 v() has exactly parent, namely g(-- (Vx(),.... ..... D(I-1)). (D("))...D'"II)),, 1 when we retrace the trajectory. We pass
Since each state has a single parent, we find that (n((((-1)) the information on when a node is added to the GFlowNet by adding an identifier to the nodes' embeddings that indicates in what layer it was sampled, as explained in Scction 4.1.
Technically, GFlowNets have unique source and terminal (or 'sink') states 8, and sy. The source state has an edge to initial states, and all terminating states have an edge the terminal state.
22

---

Published in Transactions on Machine Learning Research (05/2025)
Table 6: Comparison between GRAPES and variants using the straigh-tthrouge estimator (STE).
Cora
Flickr
ogbn-arxiv
Yelp
Best GRAPES
87.62 + 0.48
49.54 + 0.67
62.58 + 0.64
44.57 + 0.88
STE
87.95 + 0.18
46.33 = 1.39
61.95 + 0.32
37.29 + 0.15
STEN
87.03 + 0.35
46.29 + 1.47
60.13 + 0.41
15.63 + 0.10
Loss derivation Combining our setup with the trajectory balance loss (Equation 9), the GRAPES loss is
(cF (log 2(V(0)) 11 PF(5 (00)))))-)))))
(11)
R(s(0)
-log Z(V(0)) + Σ log (100000))) 1(1-1))+
(12)
x(n))²
a Lcl,
We model the initia-sstate-deeeedeet normalizer ()) in Equation with a trainable GCN, namely (V()). It predicts the normalizer conditioned on the target nodes given. It is trained together with GCN, by minimizing the trajectory balance loss.
We note that, like in GRAPES-RL, we use off-policy sampling from ((20)110) ...., 1(1-1) k)) to train the GFlowNet. See Appendix A for additional details.
F.4 Reward scaling
In our experiments, we noticed that with the bigger datasets, the GFlowNet is more affected by the log-probabilities than the reward from the classification GCNc. The reason that the term logg()()))
..... ..... v((-)) dominates LGEN is that log (()))) = EiEN(Ka-n) logp;, which sums over [(K(())) elements. Given a batch size of 256, this neighborhood can be as big as 52, 000 nodes, resulting in summing 52, 000 log-probabilities. The majority of the probabilities p; are values close to zero. Therefore, the above sum would be large negative number. Since the loss Le is, in our experiments, often quite close to zero, the log-probability and its variance dominate the loss. Therefore, we add the hyperparameter to the reward and tune it in our experiments.
G GRAPES and the straight-through estimator
The straight-througe estimator Bengio et al. (2013) (STE) has been proposed method for learning in computation graphs involving non-differentiable function f of an input æ, by replacing / with the identity in the backward pass during computation of the gradients.
In practice, applying the STE for learning in GRAPES requires ensuring that the gradients flow through the sampled nodes, for example by treating the top-k sampled nodes each layer as a mask which multiplies the messages from these nodes all their neighbors. Such a computation over all neighboring nodes defcats the purpose of sampling, increasing memory usage.
An alternative to keep memory usage low is to keep the gradients only for the top-k probabilities, though this results in a biased estimate of the gradient. We implemented two versions of this approach. In the first version (STE), we simply use the perturbed log probability (log probability plus the Gumbel noise) of the top-k nodes as additional weights for the classification GCN. In the second version, we normalized these weights to have a mean equal one (STEx). We present results Table 6. While in Cora the results are relatively similar to our implementation of GRAPES, as we experiment with larger graphs, there is a significant. drop in performance when employing either variant of the STE.
23

---

Published in Transactions on Machine Learning Research (05/2025)
H Proof of Theorem 1
H.1 Proof
In this section, we prove Theorem in section as follows:
Proof. Let G (V,E) be an undirected fully connected simple graph with an even number of nodes N, V (l...., a set of edges & = {eg i.j=i where Ei denotes an edge between e and Vy- Let Y= E and & be one partition of E, where & consists of N/2 edges with two conditions: 1) Caj E ε if and only if the first feature of nodes and V/ are equal, i.c. Eij E & + Ia 211, and 2) each node appears only at one edge in & The second condition implies that each value for the first feature appears only in the nodes connected by one edge in ε Le., for two distinct edges Eijs ENz E Et. 31 # Zik-
y {0, be the set of node labels and let X RNx be the node features. Let E,
For each edge Eij in Ei, sample Hı2 Berm(0.5) on {0.1). Then, set the node label yj to 222- That is, the label of each node is equal the second feature of its corresponding neighbor in & Since G is fully connected, the L-hop neighborhood for all nodes is V. Therefore, non-adaptive methods cannot prefer any node over another: GCN with a non-adaptive sampler can only achieve accuracy above chance by sampling K nodes such that for each target node, the neighbor with the same first feature is sampled. The probability (X
K The nominator indicates choosing the desired neighbor of sampling such neighbor is 1x=1) N-1
2 nodes. The denominator indicates choosing K nodes among N - 1 nodes (excluding the target node). Repeating the sampling for L layers, eliminating K nodes from the candidate neighbors for sampling for the next layer, will result in = --1 N-IK-1 < LK
connected to the target node in & and then choosing the remaining K - 1 nodes among the N -
However, there is a GCN with an adaptive sampler that classifies nodes with an accuracy of 100%. Specifically, such an adaptive sampler compares the first node feature of the neighbors with the target node us and then always samples the unique fy where Gi & Subsequently, it samples K K-1 additional neighbors randomly. If the sampler perfectly samples the informative neighbors in ε₁, we assume there exists GCN that can classify the target nodes correctly. We show construction of such GCN in section H.2. Figure 9 shows an example of such a graph with eight nodes and homophily ratio of 0.43.
In the above proof, we show that there are graphs for which there is performance gap between adaptive and non-adaptive samplers. Usually LK < N; therefore, the probability < LK N" for non-adaptive sampling methods to perform better than the chance level becomes very small. These graphs are heterophilous, with an expected homophily ratio equal to 0.5. We calculate this expectation below:
(m) + 1N (-
B(hg) E
mm (N,,0)))(NN0.5)
For that, need E ((H) E (m(m- -))). Because B(m) N and Var(m) NN we have
E(m(m- - 1)) = E(m 2 m) = =E(m²) - E(m) = Var(m) + (B(m))² E(m)
N
N
N N N
2
2
so we have
E
m
=
X
N
N
N N
2
8
24

---

Published in Transactions on Machine Learning Research (05/2025)
11
31
2/2
Us
MY
y4
X4
3
M6
Figure 9: An example of graph for Theorem 1 with eight nodes. Red edges belong to E,, features 2; and labels Yi are shown beside every node. For nodes U1 and we show the edge 612 as an example. As shown, the label of each node the second feature of its neighbor, where a red edge connects them. The edge homophily ratio
28 0.43.
Similarly, E (m) Nº-N. Therefore, the expected homophily ratio
N
Nº-N
E(hg)
=..5.
N
H.2 GCN Construction
In this section, we construct GON that can compute the classification rule assumed in the proof of Theorem 1. Let x; R be input feature vector of node is V. We construct GCN where the first layer computes a 4-dimensional vector for target node Us!
h (1) W
Σ
WiXj.
(13)
[(:e)]
Here, W, is the self-loop weight, and W, is the weight for the neighbors of target node. We define the following:
0
0 1
W1
W
(14)
0
0
0
0
1
For a given target node, the output of this layer is a vector h." E R where the first two values correspond to the larget node's features, and the other two values are the average of the features of its neighbors. The next layer implements the following function: if values 1 and h are the same, then the output is the second value of this vector, otherwise is zero. We denote this function as h(2) f(b")) E, which can be implemented with multi-layer perceptron due to its universal approximation properties (Hornik al., 1989). An MLP can be implemented in GCN by omitting the neighbors and using self-loop weight matrix only. The last layer of the GCN selects the average value in the neighborhood of a target node from the scalars computed by f, which can be computed using a simple GCN where the self-loop weight is set to zero: Ietelll EnjeN(..) h2 This output corresponds to the classification rule required for Theorem 1.
h (3)
25


Reviews:
[{"review_id": "z2U4c2iFuU", "reviewer": "Reviewer_3c9w", "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": "The paper is easy to follow and the idea is straightforward. The proposed method achieve good performance on the hard tasks (heterophilous graphs) compared to other sampling method, and can achieve comparable results to non-sampling method but with less memory cost. \n\nWeaknesses: \n1) the benchmark especially for homophilous graph seems to easy for GCN since in most cases, random sampling can achieve good or even better performance as well. \n2) Can we have more analysis for those worst cases, for example on snap-patents dataset where the proposed method achieve very poor performance? Also put that in the Sample Size plot to better understand why this \"adaptive\" failed.\n3) Based on the Sample Size plot, the performance of the proposed method aligns quite good with the random sampling, can we have a distribution comparison between the sampled nodes from these two method? Also can we have some plot to show the distribution shift of the sampled nodes during training to see whether the sampling policy really learns something interesting?", "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 introduce an new sampling method to that subsample the original graph thus making the training of GNN more efficient in either latency or memory. They call it adpative since the sampling policy can be learnt for different tasks. The sampling policy itself is a GCN (graph convolutional network) and is learnt jointly during the training. They achieve good F1-score on both homophilous and heterophilous  graphs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weakness.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nGaTj2BDZf", "reviewer": "Reviewer_TjT4", "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": "Strengths:\n1. Clear Structure and Expression. This paper is well-structured, clearly written, and easy to follow.\n2. New Adaptive Sampling Approach. GRAPES learns a task-aware sampling policy instead of relying on predefined heuristics. It introduces a secondary GCN to optimize node selection, allowing it to adaptively sample nodes based on task requirements.\n3. Significant Memory Efficiency. GRAPES demonstrates orders of magnitude lower GPU memory usage than methods like GAS, making it well-suited for large graphs.\n4. Rigorous Experimental Design. Unlike many prior works that compare methods using different architectures or hyperparameters, GRAPES evaluates all baselines under identical settings.\n\nWeaknesses:\n1. Lack of Clarity in Theoretical and Technical Contributions. The use of the downstream task objective to guide adaptive node sampling is a relatively straightforward approach, and it has been explored in prior works. For example, the Reinforce-based strategy used to train the sampling policy has already been applied in existing methods such as PASS (Yoon et al., 2021). While GRAPES introduces an adaptive approach that combines both Reinforce and GFlowNet-based training, this paper does not clearly articulate its novel theoretical contributions or explain how the proposed technique significantly differs from or improves upon these existing methods. \n2. Lack of Methodological Support for Key Claims. The manuscript states that existing methods are primarily designed for homophilous graphs and single-label classification. While the proposed method is evaluated on heterogeneous graphs and multi-label classification settings, it lacks essential theoretical justification and methodological considerations specifically tailored to these scenarios, making it unclear how the method inherently supports them beyond empirical results. Additionally, while the study highlights memory efficiency as a key strength, this aspect is only demonstrated through experimental results without a theoretical justification or complexity analysis. \n3. Lack of Explanation and Justification. This paper introduces Bernoulli inclusion probabilities and the Gumbel-Top-k trick as key components of the sampling process. However, it lacks a detailed explanation of why these specific techniques were chosen and how they compare to alternative methods. Given that there exist multiple ways to model adaptive node sampling, it is unclear why these particular approaches are the most suitable for the proposed framework. Additionally, while GFlowNet-based training is mentioned as an alternative to Reinforce, this paper does not provide a clear justification for why it is beneficial in this specific setting. \n4. Incomplete Literature Review. This paper provides a discussion of related works on graph sampling methods, but it does not sufficiently cover recent advancements in learnable sampling policies. Several relevant works that have been published in recent years are missing, such as \n[1] Cong, W., Forsati, R., Kandemir, M. and Mahdavi, M., 2020, August. 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 (pp. 1393-1403).\n[2] Cong, Z., Shi, B., Li, S., Yang, J., He, Q. and Pei, J., 2023. FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently. IEEE Transactions on Knowledge and Data Engineering.\nFor more relevant works, please refer to the following survey paper:\n[3] Ma, L., Sheng, Z., Li, X., Gao, X., Hao, Z., Yang, L., ... and Cui, B., 2024. Acceleration algorithms in gnns: A survey. arXiv preprint arXiv:2405.04114.\n5.Unconvincing Experimental Evaluation. The experimental evaluation lacks comprehensive validation for the following reasons:\n(1) Insufficient Baselines. The comparison primarily focuses on fixed sampling strategies and historical embeddings, but does not include adaptive sampling methods, which are the most relevant baselines. \n(2) Limited Performance Gains. The results indicate that GRAPES does not consistently outperform baselines: On homophilous graph datasets, GRAPES achieves only marginal improvements (0.1-0.4%) in two datasets, while performing worse than baselines in 5 out of 7 cases. On heterophilous graph datasets, the observed improvements are very weak (0.1-4%), and in some cases, GRAPES performs worse than competing methods. Given these results, the claimed advantages of GRAPES in accuracy and robustness are not well supported by empirical evidence. Further justification is needed.\n(3) Lack of Ablation Studies. This paper does not analyze the impact of key design choices, such as the sampling policy learning rate, depth of the sampling GNN, and architectural choices. An ablation study would help clarify the importance of these components and whether GRAPES’ performance depends on specific hyper-parameters.\n(4) No Parameter Sensitivity Analysis. This paper does not investigate how sensitive GRAPES is to hyper-parameters such as the sample size, training epochs, or reinforcement learning parameters. \n(5) Scalability to Other GNN Architectures. The experiments are conducted only on GCNs, which are not optimized for heterophilous graphs. To fully assess GRAPES’ generalizability, it should be evaluated on other GNN architectures, such as Graph Attention Networks (GAT) and Graph Transformer Networks.\n6.Questions. (1) Assumption Behind Bernoulli Inclusion Probability. The paper employs Bernoulli inclusion probabilities for node sampling, but it is unclear whether this choice is based on specific assumptions about the data distribution. Does the proposed method assume any underlying statistical properties of the graph structure? If so, how do these assumptions impact the generalizability of GRAPES across different types of graphs (e.g., homophilous vs. heterophilous)? (2) Memory Usage Discrepancy in Figure 3. In Figure 3, AS-GCN appears to use less memory than GRAPES in certain cases. However, this paper does not provide an explanation for this observation. Given that GRAPES is designed to reduce memory consumption through adaptive sampling, why does AS-GCN achieve lower memory usage in some datasets? Could this be due to differences in sampling efficiency, computational overhead, or batch processing techniques?", "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": "This paper proposes GRAPES, an adaptive graph sampling method for training Graph Neural Networks (GNNs) on large-scale graphs. Unlike conventional fixed-heuristic sampling techniques, GRAPES learns a node inclusion probability distribution through a secondary GNN, optimizing for the downstream node classification task. The method introduces two strategies for training this sampling policy: Reinforcement Learning (Reinforce-Based) and GFlowNet (Trajectory Balance Loss). \n\nThe key objectives of the work are to: Reduce GPU memory usage by sampling fewer but more influential nodes. Achieve high accuracy in node classification tasks, particularly in heterophilous and multi-label settings. Maintain robustness to decreasing sample sizes, allowing scalable training on large graphs. \n\nKey Findings: GRAPES not only outperforms existing methods in heterophilous graphs and multi-label classification but also significantly reduces memory consumption compared to historical embedding-based approaches such as GAS.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. A more in-depth discussion of the conceptual improvements, algorithmic novelty, and advantages over prior adaptive methods would strengthen the clarity of the paper's technical contributions.\n2. To improve clarity and credibility, the authors should explicitly explain how the method is designed to handle heterogeneous graphs and multi-label classification and provide theoretical insights into its claimed memory efficiency, such as analyzing computational complexity, memory footprint, or optimization mechanisms. \n3. A more thorough discussion, including theoretical justification or empirical comparisons with alternative techniques, would strengthen the paper’s contribution. Additionally, It would be helpful for the authors to elaborate on the advantages of GFlowNets in sampling policy optimization and provide empirical evidence demonstrating its superiority over alternative methods.\n4.  This paper should incorporate the recent adaptive sampling methods [1-3] mentioned above, which utilize learnable policies to dynamically optimize node selection.\n5. (1) Include adaptive sampling baselines for a more direct comparison. (2) Provide stronger evidence that GRAPES is consistently better across datasets. (3) Conduct ablation studies to identify the key factors driving performance. (4) Perform hyper-parameter sensitivity analysis to assess stability. (5) Test GRAPES on diverse GNN architectures to validate its generalizability.\n6. To address the concerns raised, the authors should explicitly clarify whether Bernoulli inclusion probabilities rely on specific assumptions about the data distribution or graph structure and analyze why AS-GCN consumes less memory than GRAPES in certain cases.", "broader_impact_concerns": "The broader impact section is not included in this article, and based on my assessment, there are no concerns regarding the ethical implications of this work that need to be addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GFee3GoI9m", "reviewer": "Reviewer_gVgU", "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": "Strengths:\n\n1. The method is well-written and easy to follow.\n\n2. The improvement of the efficiency of the proposed method is impressive.\n\nWeaknesses:\n\nPlease see the requested changes.", "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 proposes GRAPES, an adaptive sampling method for training GNN. This method trains on a second GNN to predict node sampling probabilities. The experiments show a strong performance of the proposed method on both homophilous and heterophilous graphs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The sampling is determined by another GCN. However, GCN emphasizes local information rather than global information. Therefore, I expect the sampling method to somehow also emphasize local information. However, the performance of the proposed method is improved on heterophilous graphs. I don't know why and more discussion is needed about this.\n\n2. The performance of Yelp in Figure 4 drops when the sample size increases, which seems counterintuitive as a different trend from other datasets. What is the reason?\n\n3. Figure 5 shows that the sampling finally prefers some particular nodes in the graph. It is not surprising. The most interesting thing would be what properties these preferred nodes have and how these nodes are related to the graph structure.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces GRAPES, an adaptive graph sampling method for training Graph Neural Networks (GNNs) on large-scale graphs. Unlike conventional fixed-heuristic sampling techniques, GRAPES learns a node inclusion probability distribution via a secondary GNN, optimizing for downstream node classification.

**Strengths**:

1. The paper is well-structured and easy to follow, with a straightforward and intuitive idea.

2. The proposed method achieves strong performance on challenging tasks (heterophilous graphs) compared to other sampling methods and delivers comparable results to non-sampling approaches while reducing memory costs.

3. Unlike many prior works that compare methods under varying architectures or hyperparameters, GRAPES evaluates all baselines under consistent settings.

**Weaknesses (Pre-Revision)**:

1. Lack of clarity in theoretical and technical contributions.

2. Insufficient methodological support for key claims.

3. Inadequate explanation and justification of design choices.

4. Need for further experimental explanations and results.

**Post-Revision Assessment**:

While the authors have addressed some concerns, one reviewer maintains a Leaning Reject stance due to two major unresolved issues:

1. Lack of Theoretical Justification and Interpretability. As acknowledged by the authors in their response, this paper primarily focuses on empirical results, yet several key findings lack sufficient theoretical grounding or interpretability. For example, the sampling process is determined by a secondary GCN, which primarily captures local information. Theoretically, this should result in strong performance on homophilous datasets; however, the method instead shows surprisingly good results on heterophilous datasets. Although the authors provide an explanation, it remains vague and does not convincingly justify this phenomenon.

2. Unconvincing and Inconsistent Experimental Results. The experimental results do not consistently demonstrate superiority over baseline methods, raising doubts about the effectiveness of the proposed approach. On homophilous graph datasets, the proposed method struggles to outperform the baselines in most cases, with only marginal performance gains (0.1-0.4%) where it does. On heterophilous graph datasets, the performance is slightly better, but the improvements remain limited (0.1-4%). Additionally, the experimental results indicate that on homophilous datasets, the proposed method performs similarly to random sampling, showing no significant advantage. In this case, using random sampling alone would achieve comparable results, calling into question the necessity of the proposed approach.

After careful consideration, I concur that these weaknesses remain. Thus, I recommend a minor revision with the following improvements:

1. The authors should provide a theoretical foundation to substantiate the claim that the proposed method is able to handle heterophilous and multi-label datasets, besides the experimental results. 

2. Moderate certain claims to ensure they align with the experimental results.

2. Add a limitations section to address potential constraints and broader impacts of the proposed method.
Decision: Accept (poster)