Nonparametric Teaching for Graph Property Learners
Authors: Chen Zhang
Weixin Bu
Zeyi Ren
Zhengwu Liu
Yik Chung WU
Ngai Wong
Venue: ICML 2025 spotlightposter (2025)
Keywords: Nonparametric Teaching
Graph Property Learning
Functional Gradient Descent
Primary area: general_machine_learning->everything_else

Abstract: Inferring properties of graph-structured data, *e.g.*, the solubility of molecules, essentially involves learning the implicit mapping from graphs to their properties. This learning process is often costly for graph property learners like Graph Convolutional Networks (GCNs). To address this, we propose a paradigm called Graph Nonparametric Teaching (GraNT) that reinterprets the learning process through a novel nonparametric teaching perspective. Specifically, the latter offers a theoretical framework for teaching implicitly defined (*i.e.*, nonparametric) mappings via example selection. Such an implicit mapping is realized by a dense set of graph-property pairs, with the GraNT teacher selecting a subset of them to promote faster convergence in GCN training. By analytically examining the impact of graph structure on parameter-based gradient descent during training, and recasting the evolution of GCNs—shaped by parameter updates—through functional gradient descent in nonparametric teaching, we show *for the first time* that teaching graph property learners (*i.e.*, GCNs) is consistent with teaching structure-aware nonparametric learners. These new findings readily commit GraNT to enhancing learning efficiency of the graph property learner, showing significant reductions in training time for graph-level regression (-36.62\%), graph-level classification (-38.19\%), node-level regression (-30.97\%) and node-level classification (-47.30\%), all while maintaining its generalization performance.

Nonparametric Teaching for Graph Property Learners
Chen Zhang'
Weixin Bu
Zeyi Ren Zhengwu Liu'
Yik-Chung Wu
Ngai Wong'
Abstract
Inferring properties of graph-structured data, e.g. the solubility of molecules, essentially involves learning the implicit mapping from graphs to their properties. This learning process is often costly for graph property learners like Graph Con- volutional Networks (GCNs). To address this, we propose a paradigm called Graph Neural Teaching (GraNT) that reinterprets the learning process through novel nonparametrie teaching perspective. Specifically, the latter offers theo- retical framework for teaching implicitly defined (i.e., nonparametric) mappings via example selec- tion. Such an implicit mapping is realized by a dense set graph-property pairs, with the GraNT teacher selecting subset of them to promote faster convergence in GCN training. By analyti- cally examining the impact of graph structure on parameter-basee gradient descent during training, and recasting the evolution of GCNs scaNeed by parameter thhoues-throughh functional gradient descent in nonparametric teaching, we show for the first time that teaching graph property learners (i.e., GCNs) is consistent with teaching structure- aware nonparametric learners. These new findings readily commit GraNT to enhancing learning ef- ficiency of the graph property learner, showing significant reductions in training time for graph- level regression (-36.62%), graph-level classifica- tion (-38. 19%), node-level regression (-30.97% and node-level classification (-47.30%), all while maintaining its generalization performance.
G
Figure I: An illustration of the implicit mapping f between graph G' and its property f" (G), where f denotes the mapping of the initial graph property learner, e.g., initial- ized GCN.
2017; Chami et al., 2022). The vertices, or nodes, contain individual features, while the edges link these nodes and capture the structural information, collectively forming complete graph. Graph properties can be categorized as either node-level or graph-level! For example, the node cat- egory is node-level property in social network graphs (Fan et al., 2019), while the solubility of molecules is a graph- level property in molecular graphs (Ramakrishnan al., 2014). Inferring these graph properties essentially involves learning the implicit mapping from graphs to these prop- erties (Hamilton et al.. 2017). An intuitive illustration of this mapping is provided in Figure 1. As representative graph property learner, the Graph Convolutional Network (GCN) (Defferrard et al., 2016; Kipf & Welling, 2017) has shown strong generalizability, delivering impressive perfor- mance across various fields such as social networks (Min et al., 2021; Li et al., 2023), quantum chemistry (Gilmer et al., 2017; Mansimov al., 2019), and biology (Stark et al., 2006; Burkhart et al., 2023).
1. Introduction
However, the learning process of the implicit mapping -iep the training-can be quite expensive for GCNs, partic- ularly when dealing with large-scale graphs (Liu et al., 2022a). For example, learning node-level properties in real- world e-commerce relational networks involves millions of
Graph-structured data, commonly referred to as graphs, are typically represented by vertices and edges (Hamilton et al.,
'Equal contribution 'Department of Electrical and Elec- tronic Engineering, The University of Hong Kong. HKSAR, China *Reversible Inc. Correspondence to: Chen Zhang <czhango@@ sechang6@commect.hkie connect.hku.hks: Ngai Wong www.ng@occ....htt....
'This paper adopts a graph-level focus in its discussion un- less otherwise specified, with node-level considered as a multi- dimensional generalization.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Our project page available github. 10/ http://ppwlicttttoo groph_proortye weweeeererrrraaneeeeeeeee .hmml.

---

Nonparametric Teaching for Graph Property Learners
nodes (Robinson et al., 2024). In the case of graph-level property learning tasks, the scale can become prohibitively large (Hu et al., 2021). As result, there is a pressing need to reduce training costs and improve the learning efficiency.
learning, specifically by selecting graphs with the largest discrepancy between their property true values and the GCN outputs. Lastly, we conduct extensive experiments to val- idate the effectiveness of GraNT in a range of scenarios, covering both graph-level and node-level tasks. Our key contributions are listed as follows:
Recent studies on nonparametric teaching (Zhang et al., 2023b;a; 2024a) offer a promising solution to the above problem. Specifically, nonparametric teaching provides a theoretical framework for efficiently selecting examples when the target mapping (i.e., either function or model) being taught is nonparametrie, i.e., implicitly defined. It builds on the idea of machine teaching (Zhu, 2015; Zhu designing a training set (dubbed
We propose GraNT, a novel paradigm that interprets graph property learning within the theoretical context of non- parametric teaching. This enables the use of greedy algo- rithms from the latter to effectively enhance the learning efficiency of the graph property learner, GCN.
et al., (001))involvingg the teaching set) to help the learner rapidly converge to the target functions- relaxes the assumption of target func- tions being parametric (Liu et al., 2017; 2018), allowing for the teaching of nonparametric (viz. non-closed-fom form target functions, with a focus on function space. Unfortu- nately, these studies focus solely on regular feature data and overlook the structural aspects of the inputs, resulting in dif- data
We analytically examine the impact of graph structure on parameter- based gradient descent within parameter space, and reveal the consistency between the evolution of GCN driven by parameter updates and that under functional gra- dient descent in nonparametric teaching. We further show that the dynamic GNTK, stemming from gradient descent on the parameters, converges to the structure-aware canon- ical kernel of functional gradient descent. These connect nonparametrie teaching theory to graph property learn- ing, thus expanding the applicability of nonparametric teaching in the context of graph property learning.
ficulty when the inputs are irregular structures that include both features and structure (Chami et al., 2022). Moreover, the update of GCN is gen- erally carried out through gradient descent in parameter space, leading
gap compared to the functional gradi- ent descent used in nonparametric teaching within function space (Zhang et al., 2023b;a; 2024a). These call for more examination prior to the adoption of nonparametric teaching theory in the context of graph property learning.
We demonstrate the effectiveness of GraNT through ex- tensive experiments in graph property learning, covering regression and classification at both graph and node levels. Specifically, GraNT saves training time for graph-level re- gression (-36.62%), graph-level classification node- regression (-30.97%) and node-level classi- fication (-47.30%) while upkeeping its generalization performance.
To this end, we systematically explore the impact of graph structure GCN gradient-based training in both param- eter and function spaces. Specifically, we analytically ex- amine the impact of the adjacency matrix, which encodes the graph structure, on parameter-based gradient descent within parameter space, and explicitly show that the param- eter gradient maintains the same form when the graph size is scaled. The structure-awast aware update in parameter space drives the evolution of GCN, which can be expressed us- ing the dynamic graph neural tangent kernel (GNTK) (Du et al., 2019; Krishnagopal & Ruiz, 2023), and is then cast into function space. We prove that this dynamic GNTK converges to the structure- aware canonical kernel utilized in functional gradient descent, suggesting that the evolution of GCN under parameter gradient descent is consistent with that under functional gradient descent. Therefore, is natu- ral to interpret the learning process of graph properties via the theoretical lens of nonparametric teaching: the target mapping is realized by dense set of graph-property pairs, and the teacher selects a subset of these pairs to provide to the GCN, ensuring rapid convergence of this graph property learner. Consequently, to enhance the learning efficiency of GCN, we introduce a novel paradigm called GraNT, where the teacher adopts counterpart of the greedy teaching al- gorithm from nonparametric teaching for graph property
2. Related Works
Graph property learning. Due to the versatility of graphs in modeling diverse data types (Chami et al., 2022), there has been recent surge of research interest on graphs (Xia et al., 2021), especially attempts of learning implicit map- ping from graph data to interested properties (Guo et al., 2021; Zhuang et al., 2023; Cao et al., 2023) for diverse downstream tasks, such as those related to proteins (Fout et al., 2017: Gligorijevié et al., 2021) and molecular finger- prints (Duvenaud et al., 2015). There have been various efforts to the Iearner design for better mapping learning, such as the GCN learner (Defferrard et al., 2016; Kipf & Welling, 2017), which borrows the idea of convolutional neural networks used in image tasks (LeCun et al., 2015), and the graph attention network, which applies the attention operation (Veličković et al., 2018), and to the learning ef- ficiency (Chen et al., 2018; Liu et al., 2022b; Zhang et al., 2023c), such as normalization (Cai et al., 2021), graph de- composition (Xue et al., 2023) and lazy update (Narayanan et al., 2022). Differently, we approach graph property
2

---

Nonparametric Teaching for Graph Property Learners
learning from a fresh perspective of nonparametric teach- ing (Zhang et al., 2023b;a) and adopt corresponding ver- sion of the greedy algorithm to enhance the training effi- ciency of GCN.
is captured by its adjacency matrix A E R allowing the graph to be concisely represented G (X, A) E G. The property of the graph is denoted by y E V, where is scalar for graph-level properties (i.e. 3 S R) and vector for node-level properties (i.e., 3/ _ )R A set containing m elements is written as {at}m. If {a: ]m E {ai)n holds, then (ax) Jaim Im represents a subset of {a:},. of size m, with in- dices E N₂. A diagonal matrix with elements a1.-.. am is denoted by diag((1, (11." amn), and if all m entries identical, it is simplified as diag(a;
Nonparametric teaching. Machine teaching (Zhu, 2015; Zhu et al., 2018) focuses on designing a teaching set that enables the learner to quickly converge to a target model function. It can be viewed as the reverse of machine learn- ing: while machine learning seeks to learn mapping from a given training set, machine teaching aims to construct the set based on a desired mapping. Its effectiveness has been demonstrated across various domains, including crowd- sourcing (Singla et al., 2014; Zhou et al., 2018), robust- ness (Alfeld et al., 2017; Ma et al., 2019; Rakhsha et al., 2020), and computer vision (Wang et al., 2021; Wang & Vasconcelos, 2021). Nonparametric teaching (Zhang al., 2023b;a) advances iterative machine teaching (Liu et al., 2017; 2018) by broadening the parameterized family of target mappings to include a more general nonparametric framework. In addition, the practical effectiveness of this theoretical framework has been confirmed in improving the efficiency of multilayer perceptrons (MLPs) when learning implicit mappings from signal coordinates their corre- sponding values (Sitzmann et al., 2020; Tancik et al., 2020; Luo et al., 2023; 2024; 2025; Zhang et al., 2024a). Neverthe- less, the limited focus on the structural aspects of the input in these studies makes it difficult to directly apply their findings to general tasks involving graph-structured data (Hamilton et al., 2017: Chami et al., 2022). This work systematically examines the impact of graph structure and highlights the alignment between the evolution of GCN driven by parame- ter updates and that guided by functional gradient descent in nonparametric teaching. These insights, for the first time, broaden the scope of nonparametric teaching theory in graph property learning and position our GraNT as a means to im- prove the learning efficiency of GCN.
Consider KGG G') G G + R as a symmetric and positive definite graph kernel (Vishwanathan et al., 2010). It can also be written as K(G, = (G')") = K (G), and for simplicity, (-(+) can be abbreviated to KG. The reproducing kernel Hilbert space (RKHS) H as- sociated with K(G, G') is defined as the closure of the linear span (J ((-) Σi= a (G, ),a, E RR E N. G. E G), equipped with the inner product (f.g)x = Eij (G., G2), where - ES by Ka, (Liu & Wang, 2016; Zhang et al., 2023b;a). Rather than assuming the ideal case with closed-form solution f", we consider the more practical scenario where the realization of f* is given (Zhang al., 2023b;a; 2024a). For simplicity, we assume the function is scalar-valued, aligning with the focus on the graph level in this discussion". Given the target mapping / G + y/ it uniquely returns yr for the corresponding graph Gj such that y; = (G,). With the Riesz-Fréchet representation theorem (Lax, 2002: Schölkopf et al., 2002; Zhang et al., 2023b), the evaluation functional is defined as follows:
Definition Let H be a reproducing kernel Hilbert space with a positive definite graph kernel KG H. where G G. The evaluation functional Ec(:) H + R is defined with the reproducing property as follows:
Fa(s)= (J, (J,K)))) = f(G), ((()) E H.
(1)
3. Background
Additionally, for a functional F H + I. the Fréchet derivative (Coleman, 2012; Liu, 2017; Zhang et al., 2023b) of F is given as follows:
Let G(n)) = (V,E) be graph, where V de- notes the set of n vertices (nodes) and È denotes the set of edges. The d-dimensional feature vector is denoted as [ri]a- = (II,..., ,ra) E Rdd where the entries xy are in- dexed by i E Na (N. = [1..... dd)). For simplicity, this
Notation. 2
Definition 2. (Fréchet derivative in RKHS) The Fréchet derivative of a functional F: ; H + R at f E H. denoted by V F(F(),, is implicitly defined by F(f + <g) F(f) + (V, egyn + o(e) for any g E H and R. This
feature vector may be denoted as æc The collection of fea- ture vectors for all nodes is represented by n x d feature matrix X (abbreviated as X). The i-th row and j-th column of this matrix, corresponding to the i-th node and j-th feature, are denoted by X (i.) and X (s.)). respectively. Equivalently, these can be expressed as e, X and Xe,, where e; is basis vector with its i-th entry equal to 1 and all other entries equal to O. The structure of the graph (())
derivative is also function in H.
Graph convolutional network (GCN) is proposed to learn the implicit mapping between graphs and their proper- ties (Kipf & Welling, 2017; Xu et al., 2018). Specifically, a L-layer GCN GG = x (2) resembles a L-layer MLP,
II nonparametric teaching, extending from scalar-valued func- tions to vector-valued ones, which pertains node-level properties, is a well-established generalization Zhang et al., 2023a.
AA notation table is provided in Appendix A.
3

---

Nonparametric Teaching for Graph Property Learners
with the key difference being the feature aggregation at the start of each layer, which is based on the adjacency matrix A (Wu al., 2019; Krishnagopal & Ruiz, 2023).
Lemma 3. (Chain rale for functional gradients) For differ- entiable functions G(F) R + IR that depend on function- als F(f): H + I., the expression
aG(F(f)) VFF(F) V)G(F(()) = OF(f)
x = a (IA 1)ax (0 NL-1
(7)
x(4) = (A 1) x (L--1) W()),
(2)
is typically referred to the chain rule.
Lemma 4. The gradient of the evaluation functional at the feature x, defined as Ex(f) = f(x) H - R. is given by V (J) = K (xx,)) ), where K(x, x') R. x Rd + R
where (()) is the weight matrix at layer é, with dimensions h1-1 x he, fy denotes the width of layer& & with hg = d, and Re denotes the convolutional order at the f-th layer. X x()) the input feature matrix, a represents activation function (e.g.. s.. ReLU), and p refers to the pooling operation (e.g.,
reprexents a feature-buut -aaed kernel.
4. GraNT
p(a) = 1 a for summation pooling).
Nonparametric teaching (Zhang et al., 2023b) is defined as a functional minimization over a teaching sequence D = _'x'''')..... (x",,
We begin by analyzing the effect of the adjacency matrix on parameter-based gradient descent. Then, by translating the evolution of GCN-driven by structure-aware updates in parameter space space-into function space, we show that the evolution of GCN under parameter gradient descent aligns with that under functional gradient descent. Lastly, we present the greedy GraNT algorithm, which efficiently se- lects graphs with steeper gradients improve the learning efficiency of GCN.
where the input æ e Rd represents regular feature data without considering struc- ture, with the set of all possible teaching sequences denoted as D:
D' = arg argminM(ff,F x DED
s.t. A(D)
(3)
4.1. Structure-aware update in the parameter space
The formulation above involves three key components: M which quantifies the disagreement between ff and f (e.g., L2 distance in RKHS M(f*, = I|f ll)) card(-), which represents the cardinality of the teaching sequence D regularized by a constant X, and A(D), which refers to the learning algorithm used by the learners, typically employing empirical risk minimization:
In GCNs, the structural information of graphs is captured through feature aggregation, expressed as (A + 1)* X, as shown in Equation 2. The use of (A + I)a limits the flexibility in learning aggregated hidden features, a(AA r)" XW). because it applics the same weights to features aggregated from different convolutional orders within a sin- gle layer. This paper considers more flexible GCNs, where the weights for features aggregated from different convo- lutional orders within a single layer are handled indepen- dently (Krishnagopal & Ruiz, 2023). Before presenting the detailed formulation, we introduce the concatenation oper- ation ① and define [<] = D A' = =I [1A A A=-1), an n X Kn matrix. By unfolding the aggregated features at different orders and assigning them distinct weights (Krish- nagopal & Ruiz, 2023), the flexible GCN can be expressed
f arg min Ee-P(e)) (I(f(z), FEH
(4)
with convex (w.nt. f) loss L. which is optimized using functional gradient descent:
ga+z - 1 -
(5)
where t 0, 1...., is the time step, 17 > 0 represents the learning rate, and G denotes the functional gradient computed at time t.
x (8) = (A diag X (6- (6-1); w(()) ,e N (()) =
<p)) (Almeldiag x (L. (1-1): (1m)) w(h)).
To derive the functional gradient, given by
(8)
G(C, = Fen (DCUr) 0f Ka, )
Here, the notations are consistent with those in Equation 2, with the exception that W(C is the weight matrix of size kghh-1 x hr. Figure 2 presents an example that illustrates the workflow of this flexible GCN.
(6)
Zhang et al., 2023b;a introduce the chain rule for functional gradients (Gelfand et al., 2000) (see Lemma 3) and use the Fréchet derivative to compute the derivative of the evalua- tion functional in RKHS (Coleman, 2012) (cf. Lemma 4).
Let the column vector 0 E R represent the weights of all layers in a flattened form, where m denotes the total number of parameters in the GCN. Given a training set of size N,
4

---

Nonparametric Teaching for Graph Property Learners
(GG,yy))GG G. G, N. gradient descent (Ruder, 2016) is expressed as follows:
N. the parameter update using
Flexible GCN
Feature Matrix
Nodo
X
o 0
VoL(Jo (G.), y:).
3
Due to the sufficiently small learning rate 7, the updates are tiny over several iterations, which allows them to be treated as a time derivative and then converted into a differential equation (Du et al., 2019):
Graph & (X.
Nodes
2
0
80 0t N.
@C(Sor (G.).bb) 0fe (G:)
T Of (G.) a
Xtt
(10)
Adjacency Matrix A
The term 0fo(C) (with the indexes omitted for simplicity), which indicates the direction for updating the parameters, can be written more specifically as
Weights
- Feature Aggregation
Of)(G) a0
() OWL))
OX
OX
Concatenation
(1-1 (L)
X fa(C)
(:11
(6
Figure 2: A workflow illustration of a two-layer flexible GCN with a four-node graph G as input.
1)-th layer
(
(
(11)
with ā = 0a(A ding x 3 Wil)
ow() (1) Ow
Orange indicates
(..1)
(1.h1)
dlke ( (()) w
(.a)
the first layer, green denotes the second layer, and 1, in purple corresponds to the summation pooling". When using
the first layer
Here, each term represents the derivative of output (L) w.r.t. weight column vectors. In contrast to derivatives with regular features as inputs, where the derivatives are indepen- dent across features, the adjacency matrix A dictates feature aggregation in these derivatives in a batch manner, where each feature of single node is treated individually (Du al., 2019). To clearly demonstrate, an analytical and explicit manner, how A directs structure-aware updates in the parameter space, we present example involving the derivative of a two-layer GCN with summation pooling:
ReL.U as the activation function, à A A (x))g((((())))) (x)) =
(A [s diag (X (0); k1)). The derivation can be found in Appendix A.2.
(
When the convolutional order is reduced to 1 for all layers, meaning structural information is excluded, the GCN gradi- ent computed for single input graph exactly matches that of the MLP when applied to a batch composed of the node features. This suggests that the structure-award parameter- based gradient more general than the one used in MLPs, indicating that this work can be seen as a generalization of Zhang et al., 2024a. Furthermore, from the explicit expres- sions in Equations 13 and 14, it can be observed that the gradient of GCN does not depend on the size of the input graph (i.e., the number of nodes). Instead, it depends on the feature dimension and convolutional order. In other words, the parameter gradient retains the same form even when the input graph size n is scaled.
(G) 00
(2) (2)
O (2)
ax (2)
(12)
2W
Ow (1)
(w (1)
(11)
(1h2))
where the term
aw is given by
ax
Kan
Kal
(iag(a((A) A1m disl
(Alis) diag x (0) (K))
(13)
4.2.
The functional evolution of GCN
size: 1x
The structure-aware update in the parameter space drives the functional evolution of So which captures how fe changes in response updates in can be derived using Taylor's theorem as follows:
and for i N,y . the term
(W is
8x (2)
This variation of fa.
(())
size Ko
à Inldding (0) :m)) -1) w (2)
(Amhutha)
f(0'+)) f(0') (Vaf(0'), 0 - -8 + + +1 0¹), (15)
[nc)
(14)
8. Alilldiag (x00) (2)
(C- (aahs)
"Without the pooling operation, it corresponds the scenario where the graph property considered at the node level.
Size: 1X ho
5

---

Nonparametric Teaching for Graph Property Learners
where f(0') = Jot- In a manner similar the transforma- tion of parameter updates, it can be rewritten in differential form (Zhang et al., 2024a):
This suggests that GNTK, which incorporates structural information, serves as a dynamic alternative the structure- aware canonical kernel in functional gradient descent with graph inputs, making the GCN's evolution through param- eter gradient descent align with that in functional gradient descent (Kuk, 1995; Du et al., 2019; Geifman et al., 2020), This functional insight bridges the teaching of the graph property learner, GCN, with that of structure-aware non- parametric learners, while also simplifying further analysis (e.g., convex functional L preserves its convexity with respect to So from a functional perspective, but is typically nonconvex when considering 0). By leveraging the func- tional insight and employing the canonical kernel (Dou & Liang, 2021) instead of GNTK (which should be considered alongside the remainder), it aids in deriving sufficient reduc- tion concerning L in Proposition 6, with the proof deferred to Appendix B.
0fo: 01
Of(0')
a8
ag
+0
(16)
00
0t
a1
(*)
By plugging in the specific parameter updates, i.e., Equa-
tion 10, into the first-order approximation term (+) of this variation, we get
ffat or
+ (C (g)(
N (G.. I
D
(17) Ø
where the symmetric and positive definite Kg (G.,
(G,) (f ) (see the detailed derivation in Ap-
pendix A.3). Due to the inclusion of nonlinear activation functions in f(0), the nonlinearity of f()) with respect to l causes the remainder o(8++1 6¹) to be nonzero. In a subtle difference, Jacot al., 2018; Du et al., 2019; Krish- nagopal & Ruiz, 2023 apply the chain rule directly, giving less attention to the convexity of L with respect to 0. This leads to the oorst- approximation being derived as the variation, with Kg being referred to as the graph neural tangent kernel (GNTK). It has been shown that the GNTK stays constant during training when the GCN width is as- sumed to be infinite (Du et al., 2019; Krishnagopal & Ruiz, 2023). However, in practical applications, there is need for the GCN width to be infinitely large, which leads to investigate the dynamic GNTK (Figure 5 in Appendix A.3 provides an example of how GNTK is computed).
Proposition 6. (Sufficient Loss Reduction) Suppose the convex loss C Lipschitz smooth with a constant T >> O, and the structure-aware canonical kernel is bounded above by constant 7 >> O. the learning rate vn satisfies nj S $1/(277), then it follows that a sufficient reduction in C is guaranteed, as shown by
Oc 01
17
1
N
(c( vi)
2
(21)
2
N
(G.)
This demonstrates that the variation of L over time is capped by negative value, meaning it decreases by at least the mag- nitude of this upper bound as time progresses, guaranteeing convergence.
Consider describing the variation of fe E H from a high- level, functional perspective (Zhang et al., 2024a). Using functional gradient descent, it can be expressed as:
4.3. GraNT algorithm
ofo 0t = - (G..))
Building on the insights regarding the effect of the adjacency matrix, which captures the graph structure, on parameter- based gradient descent, as well as the consistency between teaching GCN and nonparametric learner, we introduce the GraNT algorithm. This algorithm seeks to increase the steepness of gradients to improve the learning efficiency of GCN. By interpreting the gradient as a sum of the projec- 0f.
(18)
where the functional gradient is given by:
ff (G.))) -
[K( -xx- (19) Slr(CC))
The asymptotic relationship between GNTK and the structure-aware canonical kernel (Vishwanathan et al., 2010; Zhang et al., 2024a) in the context of functional gradient is given in Theorem 5 below, with the proof in Appendix B.
tions of dc(fe.f' onto the basis (K(G,, +))x N. increasing the gradient can be achieved by simply maximizing the (.)).. without the need to cal-
projection coefficient afo(G.) culate the norm of the basis (G, (Wright, 2015; Zhang et al., 2024a). This suggests that selecting graphs that either maximize [CC(f or correspond to larger components of {C(fo.f" 2/e
Theorem 5. For a convex loss C and a given training set ((.., y: G E G, y: E v/) N. the dynamic GNTK, derived from gradient descent on the parameters of a GCN, con- verges pointwise the structure-awar canonical kernel in the dual functional gradient with respect to the input graphs. Specifically, the following holds:
(fe(G.)
can effectively increase the gradi-
ent, which implies
[L(fo(G.) v:) (Se(G,)
lim Ka (G., K(G,, NN. 1-00
(20)
(..).. = arg max
(22)
m
6

---

Nonparametric Teaching for Graph Property Learners
Algorithm 1 GraNT Algorithm
without GraNT
without GraNT
Target mapping f realized by a dense set of graph- property pairs, initial GCN foo, the size of selected training set N, small constant > 0 and maximal iteration number T.
Input:
with GraNT (B)
with GraNT (B)
Valdation Loxs
with GraNT (S)
Validation MAE
w GraNT (S)
Set for < fop, t 00
wide 2000
- while L < T and ( 2 do
Wellookk Time (e)
Wallpiak Time (9)
ZINC Loss.
(b) ZINC MAE.
The teacher selects m teaching graphs:
without
/* (Graph-level) Graphs corresponding
24
with GraNT (B)
to the m largest (G.) - f
Vallowio Loss
with GraNT (9)
Valicaioon ROC
{G;) ( = arg max II]fo= (G.) - (G.)
W thot GraNi
** (Node level) Graphs associated with
with GraNT (B)
with GraNT (S)
the m largest -/xa):)-/((a]lll
+/
Wallclokk Time (A)
Weldocx Time (4)
(G.)m* = arg max ((G.)y
(c) gelg-molhiv Loss.
(d) ogbg-molhiv ROC-AUC.
Figure 3: Validation set performance for graph-level tasks:
with Frobenius norm || 1|2..
ZINC (regression) and ogbg-molhiv (classification).
Provide {G.)m" to the GCN learner.
comparable testing performance. Detailed settings are given in Appendix C.
The learner updates for based received (Gi)m":
// Parameter-based gradient descent.
Given the common practice of training GCN in batches, i.e., graphs are fed in batches, it is both natural and intuitive to implement GraNT at the batch level. This involves selecting batches that exhibit the largest average discrepancy between the actual properties and the corresponding GCN outputs, re- ferred to as GraNT (B). Meanwhile, another variant, called GraNT (S), selects single graph with the largest discrepan- cies within each batch in proportion, then reorganizes the selected graphs into new batches.
0r 00 0r
m EG.e(G)).. Vol(f
2
Set + t+1.
end
From a functional standpoint, when handling a convex loss functional L. the norm of the partial derivative of L with respect to fo, represented as || ( [/ is positively corre-
lated with I 1|x. As So progressively converges S*,
Graph-level tasks. We evaluate GraNT using several widely recognized benchmark datasets as follows:
|| [&C(f) || diminishes (Boyd et al., 2004; Coleman, 2012). This relationship becomes especially noteworthy when C is strongly convex with a larger convexity constant (Kakade & Tewari, 2008; Arjevani et al., 2016). Leveraging these insights, the GraNT algorithm selects graphs by
QM9 (Wu et al., 2018): 130k organic molecules graphs with quantum chemical properties (regression task);
ZINC (Gómez-Bombarell et al., 2018): 250k molecular graphs with bioactivity and solubility chemical properties (regression task);
[G.
arg max mrg [G...
(23)
ogbg-molhiv (Hu al., 2020): 41k molecular graphs with HIV inhibitory activity properties (binary classification task):
The pseudo code, including the node-level version, is pro- vided in Algorithm 1.
ogbg- gggg-molpcha (Hu et al., 2020): 438k molecular graphs with bioactivity properties (multi-task binary classifica- tion task).
5. Experiments and Results
We start by evaluating GraNT on graph-level regression and classification tasks, then proceed to validate it on node- level tasks. The overall results the test set shown in Table 1, which clearly highlights the effectiveness of GraNT in graph property learning: it reduces training time by 36.62% for graph-level regression, 38.19 38.19% 19% for graph- level classification, 30.97% for node-Ievel regression, and 47.30% for node-level classification, all while maintaining
To clearly illustrate the practical efficiency of GraNT, we plot the wallclock time versus loss/metric curves. This is done by conducting validation after each training epoch, i.e., performing an evaluation on the validation dataset after each training process. Specifically, we display the validation set loss and the typical Mean Absolute Error (MAE) for ZINC in Figure (a) and (b), respectively. In both plots,
7

---

Nonparametric Teaching for Graph Property Learners
GraNT
Dataset
Time (s)
Loss 4
MAE +
ROC-AUCT 1
AP
QM9
9654.81
2.0444
0.0051110.009
ZINC
33033.82
3.1160
0.0040+000004
ogbg-molhh
2163.50
0.1266
0.7572++0.0005
X
ogbg-molpe
130191.26
0.0577
0.3270=000000
gen-reg
3344.78
0.0086
0.0007
gen-cls
11662.25
0.1314
0.9150=0.0024
QM9
6392.26 (-33.79%)
2.0436
0.0051=0.0009
ZINC
20935.2 (-36.62%)
3,1165
0.0048=0.0004
ogbg-molhiv
1457.39 (-32.64%)
0.1238
0.7676110.0036
B
oghg-molpcha
80465.06 (-38.19%)
0.0577
gen-reg
2308.97 (-30.97%)
0,0086
0.00071100001
gen-cls
6145.72 (-47.30%)
0.1314
4.9157+000011
QM9
7076.37 (-26.71%)
2.0443
0.0051=0.0009
ZINC
22265.83 (-32.60%)
3.1170
0.0048=0.0004
ogbg-molhiv
1597.69 (-26.15%)
0.1421
0.7705-000027
s
ogbg-molpcba
89858.65 (-30.98%)
0.0575
0.335110.0025
gen-reg
2337.46 (-30.12%)
0.0086
0.0007=0.0001
gen-cls
8171.21 (-29.93%)
0.1313
0.915710.0014
Table Training time and testing results across different benchmarks. GraNT (B) and GraNT (S) demonstrate similar testing performance while significantly reducing training time compared the "without GraNT", across graph-level (QM9, ZINC, ogbg-moo mooliv, ogbg- ogbg-molpoce molpcba) and node-level (gen-reg, gen-cls) datasets, for both regression and classification tasks.
Time (s)
MAE
Time (s)
ROC-AUC
Ar-33Drraph/ (Subedi al., 2024)
9200.27
0.7991
GCN (Kipf & Welling, 2017)
2888.80
0.7385
Virtulrtual Node (Kipf & Welling, 2017)
3083.16
0.7608
AL-3DGraphF (Subedi al., 2024)
9364.74
0.4719
GMoE-GCN (Wang al., 2023)
3970.16
0.7536
AL-3DGraph (Subedi et al., 2024)
12601.77
0.1682
GMoE-GIN (Wang al., 2023)
3932.06
0.7468
GraNT (B)
6392.26
0.0051
GDeR-GCN (Zhang et al., 2024b)
1772.23
0.7261
GraNT (S)
7076.37
0.0051
GDeR-PNAl (Zhang al., 2024b)
5088.88
0.7616
GraNT
1457.39
0.7676
: 1r=5e-5, batch_size=256 which matches GraNT settings. Ir=5c-4, batch_size=256.
GraNT (S)
1597.69
0.7705
1: Satch_size=Si retain, ratio=0.7.
; 1r=5-44, batch size=32, which corresponds to the default settings used in the provided code for that paper.
Table 3: Comparison of GraNT with recent efficient methods on the ogbg-molhiv dataset.
Table 2: Comparison of GraNT with active sorming-based methods the QM9 dataset.
once the wallclock time reaches approximately 500s. How- ever, the curves appear relatively jagged, which be at- tributed the label imbalance in this benchmark dataset. This imbalance also explains why, even when the validation loss decreases significantly, the ROC-AUC curve does not rise to a higher range. The detailed numerical results for training time and testing performance are provided Ta- ble 1. The comparisons between GraNT and recent SOTA methods are shown in Table for QM9 and Table for ogbg-molhiv.
that the curves for GraNT (B) and GraNT (S) span about two-thirds of the width of the "without GraNT" curve, with both the loss and MAE for GraNT decreasing at faster rate than those for the "without GraNT" case. Moreover, GraNT (B) takes slightly less time to terminate than GraNT (S). This is because GraNT (S) selects teaching graphs from each batch, which can add extra operational time compared to GraNT (B) that uses direct batch selection.
Figures (c) and (d) show the loss and the commonly used ROC-AUC curves on the validation set, respectively. for ogbg-molhiv. Both plots clearly highlight the superiority of GraNT over the "without GraNT". In addition, Figure 3 (d) shows that the ROC-AUC values of GraNT (B) and GraNT (S) consistently exceed that of "without GraNT"
Node-level tasks. We also assess GraNTT for node-level property learning using synthetic data. Specifically, we utilize the graphon, a typical limit object of convergent sequence of graphs (Xu et al., 2021: Xia et al., 2023), to generate two synthetic datasets: gen-reg (containing 50k
8

---

Nonparametric Teaching for Graph Property Learners
without GraNT
without GraNT
without GraNT
GraNT (B)
GraNT (B)
20
with GraNT (B)
with GraNT (S)
Voltotton MAl
with GraNT (S)
Valldation Lows
with GraNT (S)
Validatien
withuut GraNT
GraNT (B)
E0011
GraNT (S)
Walldook Time (9) (a) gen-reg Loss.
Wallelock Time 151
Wallelock Time (5)
Walllloc Time 1S)
(b) gen-reg MAE.
(c) gen-cls Loss.
(d) gen-clss ROC-AUC.
Figure 4: Validation set performance for node-level tasks: gen-reg (regression) and gen-cls (classification).
graphs) for regression and gen-cls (containing 50k graphs) for classification.
variations of GraNT for different graph property learners, such as graph attention networks (Veličković et al., 2018 8). Moreover, exploring the practical applications of GraNT to improve the efficiency of data-driven methods (Henaff, 2020; Touvron et al., 2021; Müller et al., 2022) within the field of graph property learning offers promising opportuni- ties for future progress, particularly in fields like molecular biology and protein research.
Figures 4 (a) and (b) illustrate the validation loss and MAE curves for gen-reg, respectively. From both plots, it is clear that GraNT reached convergence more quickly in terms of wallclock time compared to the "without GraNT", highlight- ing its efficiency.
Figure (c) and (d) show the validation loss and ROC-AUC for gen-cls, respectively. Both plots demonstrate that GraNT requires less wallclock time converge compared to the "without GraNT". Furthermore, although this dataset is generated with imbalanced labels, similar to boogmm, there is a notable difference: when the validation loss is low, the corresponding ROC-AUC exceeds 0.9, which is a relatively high value. This underscores the effectiveness of GraNT. The detailed numerical results for training time and testing performance are shown in Table 1.
Impact Statement
Recent interest in learning implicit mappings from graph data to specific properties has grown significantly, especially in science-related fields, driven by the ability of graphs to model diverse types of data. This work focuses on improv- ing the learning efficiency of implicit graph property map- pings through novel nonparametrie teaching perspective, which has the potential positively impact graph-related fields and society. Furthermore, it connects nonparametric teaching theory with GCN training, expanding its applica- tion in graph property learning. As result, it also holds promise for valuable contributions to the nonparametric teaching community.
All experimental results demonstrate that GraNT (B) and GraNT (S) offer significant time-saving benefits while main- taining comparable generalization performance, and in some cases, even outperforming the "without GraNT". Further ex- perimental results, including result plots for QM9 and oghg- molpcba, training curves for the aforementioned datasets, and additional validations on the AMD device, can be found in Appendix C.
Acknowledgements
We thank all anonymous reviewers for their constructive feedback, which helped improve our paper. We also thank Yikun Wang for his helpful discussions. This work is supported in part by the Theme-based Research Scheme (TRS) project T45-701/22-R of the Research Grants Council (RGC), Hong Kong SAR, and in part by the AVNET-HKU Emerging Micmellectronics & Ubiquitous Systems (EMUS) Lab.
6. Concluding Remarks and Future Work
This paper proposes GraNT, a novel paradigm that enhances the learning efficiency of graph property learner (GCN) through nonparametric teaching theory. Specifically, GraNT reduces the wallelock time needed to learn the implicit map- ping from graphs to properties of interest by over 30%, while maintaining comparable test performance, as shown through extensive experiments. Furthermore, GraNT estab- lishes a theoretical connection between the evolution a GCN using parameter-basel gradient descent and that of function using functional gradient descent in nonparametric teaching. This connection between nonparametrie teaching theory and GCN training broadens the potential applications of nonparametric teaching in graph property learning.
References
Alfeld, S., Zhu, X., and Barford, P. Explicit defense actions against test-set attacks. In AAAI, 2017. 3
Arjevani, Y., Shalev-Shwarte S.,, and Shamir, O. On lower and upper bounds in smooth and strongly convex opti- mization. The Journal of Machine Learning Research, 17 (1):4303 434303-4353, 2016." 7
In future work, it would be interesting to investigate other

---

Nonparametric Teaching for Graph Property Learners
Bengio, Y., Louradour, J., Collobert, R., and Weston, Curriculum learning. In ICML., 2009. 20
Geifman, A., Yadav, A., Kasten, Y., Galun, M., Jacobs, D., and Ronen, B. On the similarity between the laplace and neural langent kernels. In NeurlPS, 2020. 6
Boyd, S., Boyd, S. P., and Vandenberghe, L. Convex opti- mization. Cambridge university press, 2004." 7
Gelfand, I. M., Silverman, R. A., et al. Calculus of varia- lions. Courier Corporation, 2000. 4
Burkhart, J. G., Wu, G., Song, X., Raimondi, F., McWeeney, S., Wong, M. H., and Deng, Y. holloyyinsspiee graph neural network encodes reactome and reveals biochemical reactions of disease. Patterns, 4(7), 2023.
Gilmer, J., Schoenholz, S., Riley, F., Vinyals, O., and
Dahl, E. Neural message passing for quantum chem- istry. In ICML, 2017.
Cai, T., Luo, S., Xu, K., He, D., Liu, T.-y, and Wang, L. Graphnorm: principled approach accelerating graph neural network training. In ICML., 2021.
Gligorijevic, V., Renfrew, P. D., Kosciolek, T., Leman, J. K., Berenberg, D., Vatanen, T., Chandler, C., Taylor, B. C., Fisk, I. M., Vlamakis, H., et al. Structure- protein function prediction using graph convolutional networks. Nature communications, 12(1):3168, 2021.
Cao, K. Phothilimthana, M., Abu-Ei Eaa--E--aaa,,, S., Zelle, D., Zhou, Y., Mendis, C., Leskovec, J., and Perozzi, B. Learn ing large graph property prediction via graph segment training. In NeurlPS, 2023.
Gómez-Bombarelli, R., Wei, J. N., Duvenaud, D., Hermández-Lobato J. M., Sánchez-Lengeling B., She- berla, D., aaauilera-parraguuire J., Hirzel, T. D., Adams, R. P., and Aspuru-Guzik, A. Automatic chemical de- sign using a data-driven continuous representation of molecules. ACS central science, 4(2):268-276, 2018. URL https: : / //nncc...//////////////////// docking org.
Chami, I., -bajaa, S., Perozzi, B., Ré, C., and Mur- phy, K. Machine learning graphs: A model and com- prehensive taxonomy. Journal of Machine Learning Re- 3,
search, 23(8)) 2022.
Chen, J., Ma, T., and Xiao, C. Fastgen: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018. 2
Guo, Z., Zhang, C., Yu, W., Herr, J., Wiest, O., Jiang, M., and Chawla, N. V. Few-shot graph learning for molecular property prediction. In WWW, pp. 2559-25555 2569,,257744 2021. 2
Coleman, R. Calculus on normed vector spaces. Springer Science & Business Media, 2012. 7,
Hamilton, W. L., Ying, R., and Leskovec, J. Repre- sentation learning on graphs: Methods and applica- tions. IEEE Data Engineering Bulletin, 40:52-74, 2017. URL https::t//// //tps:///pp... semanticscholar org/CorpusID:321535 1,3
Defferrard, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks graphs with fast localized spectral filtering. In NeurlPS, 2016. 1,2
Dou, X. and Liang. T. Training neural networks as learning data-adaptive kernels: Provable representation and ap- proximation benefits. Journal of the American Statistical Association, 116(535):507--152) 2021.
Henaff, O. Data-efficient image recognition with contrastive
predictive coding. In ICML, 2020.
Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. R. Improving neural networks by preventing co-adaptation of feature detectors. arxiv 2012.
Du, S. S., Hou, K., Salakhutdinov, R. R., Poczos, B., Wang, R., and Xu, K. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In NeurlPS, 2019. 2, 5, 6,
arXiv preprint arviv 007.0580. 2012. 20
Hu, W., Fey, M., Zitnik, M. Dong, Y., Ren, H. Liu, B., Catasta, M., and Leskovec, J. Open graph bench- mark: Datasets for machine learning on graphs. booktitle, 2020. URL httts:/s:/ /ttttps://oo //obb. stan ford edu/ docs/ graphprop. 7
Duvenaud, D. K., Maclaurin. D., Iparraguirre, J., Bom- barell, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. Convolutional networks on graphs for learning molecular fingerprints. In NeurIPS, 2015.
Hu, W., Fey, M., Ren, H. Nakata, M., Dong. Y., and Leskovec, J. Ogb-Isc: A large-scale challenge for ma- chine learning on graphs. In NeurIPS Datasets and Bench- marks Track, 2021.
Fan, W. Ma, Y.. Li, Q., He, Y., Zhao, E., Tang. J., and Yin, D. Graph neural networks for social recommendation. In Www, 2019.
Fout, A., Byrd, J., Shariat, B., and Ben-Hur, A. Protein interface prediction using graph convolutional networks. In NewrIPS, 2017. 2
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In NeurlPS, 2018. 6
10

---

Nonparametric Teaching for Graph Property Learners
Kakade, S. M. and Tewari, A. On the generalization ability of online strongly convex programming algorithms. In NeurIPS, 2008.
Luo, Z., Rocha, A., Shi, B., Guo, Q., Li, H., and Wan, R. The nerf signature: Codebook-aided watermarking for neural radiance fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025. 3
Kipf. T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017. 1, 8,8
Ma, Y., Zhang, X., Sun, W., and Zhu, J. Policy poisoning in batch reinforcement learning and control. In NeurlPS, 2019. 3
Krishnagopal, and Ruiz, L. Graph neural tangent kemel: Convergence on large graphs. In ICMI, 2023. 4, 6,
Mansimov, E.,, Mahmood, O., Kang, S., and Cho, K. Molec- ular geometry prediction using a deep generative graph neural network. Scientific reports, 91))22038, 2019. 1
Kuk, A. Y. Asymptotically unbiased estimation in general- ized linear models with random effects. Journal of the Royal Statistical Society Series B: Statistical Methodol- ogy, 57(2):395 1995. 6
Min, S., Gao, 7., Peng. J., Wang, L.., Qin, K. and Fang. B. Stgsn-a spatial- graph neural network frame- work for time-evolving social networks. Knowledge- Based Systems, 21 106746, 2021.
Lax. P. D. Functional analysis, volume 55. John Wiley & Sons, 2002. 3
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. nature, 521(7553):436 444, 2015.
Müller, T., Evans, A., Schied, C., and Keller, A. Instant neural graphies primitives with multiresolution hash encoding. ACM transactions on graphics (TOG), 41(4): 1-15, 2022. 9
Li, X., Sun, L., Ling, M., and Peng. Y. survey of graph neural network based recommendation in social networks.
Neurocomputing, 549: 126441, 2023. 1
Narayanan, S. D., Sinha, A., Jain, P., Kar, P., and SELL- AMANICKAM, S. Iglu: Efficient gen training via lazy updates. In ICLR, 2022. 2
Liu, Q. Stein variational gradient descent as gradient flow. In NeurlPS, 2017. 3
Liu, Q. and Wang. D. Stein variational gradient descent:
Rakhsha, A., Radanovic, G., Devidze, R., Zhu, X., and Singla, A. Policy teaching via environment poisoning: Training-time adversarial attacks against reinforeement learning. In ICML, 2020.
A general purpose bayesian inference algorithm. In NeurlPS, 2016.
Liu, W., Dai, B., Humayun, A., Tay, C., Yu, C., Smith, L. B., Rehg. J. M., and Song, L. Iterative machine teaching. In ICML, 2017. 2,3
Ramakrishnan, R., Dral, P. O., Rupp. M., and Von Lilienfeld, O. A. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
Liu, W. Dai, B., Li, X., Liu, Z., Rehg, J., and Song, L. Towards black-box iterative machine teaching. In ICML, 2018. 2,3
Robinson, J., Ranjan, R., Hu, W., Huang, K., Han, J., Dobles, A., Fey, M., Lenssen, J. E., Yuan, Y., Zhang, Z., et al. Relbench: A benchmark for deep learning on re- lational databases. In NeurlPS Datasets and Benchmarks Track, 2024. 2
Liu, X., Yan, M., Deng, L., Li, G., Ye, X., Fan, D., Pan, S., and Xie, Survey on graph neural network accelera- tion: An algorithmic perspective. Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22. IJAAI, 2022a. Survey Track.
Proceedings of the
Ruder, S. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.047477 2016.
Liu, X., Yan, M., Deng, L., Li, G., Ye, X., Fan, D., Pan, S., and Xie, Survey on graph neural network acceleration: An algorithmic perspective. In IJCAI, 2022b. Survey Track. 2
Schölkopf, B., Smola, A. J., Bach, F., et al. Learning with kernels: support vector machines, regularization, opti- mization, and beyond. MIT press, 2002.
Luo, Z., Guo, Q., Cheung, K. C., See, S., and Wan, R. Copymeerf: Protecting the copyright of neural radiance fields. In ICCV, 2023. 3
Singla, A., Bogunovic, I., Bartók, G., Karbasi, A., and Krause, A. Near-optimally teaching the crowd to classify. ICML,, 2014. 3
Luo, Z., Shi, B., Li, H., and Wan, R. Imaging interiors: An implicit solution to electromagnetic inverse scattering problems. In ECCV, 2024. 3
Sitzmann, V., Martel, J., Bergman, A., Lindell, D., and Wet- zstein, G. Implicit neural representations with periodic activation functions. In NewrIPS, 2020.

---

Nonparametric Teaching for Graph Property Learners
Stark, C., Breitkreutz, B.-J., Reguly, T., Boucher, L., Bre- itkreutz, A., and Tyers, M. Biogrid: general reposi- tory for interaction datasets. Nucleic acids research, 34 (suppl_ (eel__)):S5 1):D5)))DD5555
Xu, H., Luo, D., Carin, L.,, and Zha, H. Learning graphons via structured gromov-wasserstein barycenters. In AAAI, 2021. 8,22
2006.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2018.
Subedi, R., Wei, L.,, Gao, W., Chakraborty, S., and Liu, Y. Empowering active learning for 3d molecular graphs with geometric graph isomorphism. In NeurIPS, 2024. 8
Xue, Z., Yang, Y., and Marculescu, R. Sugar: Efficient subgraph-leve training via resource- graph parti- tioning. IEEE Transactions on Computers, 2023. 2
Tancik, M., Srinivasan, P., Mildenhall, B., Fw..oorioohoeeiiie S., Raghavan, N., Singhal, U., Ramamoorthi, R., Barron, J., and Ng, R. Fourier features let networks learn high frequency functions in low dimensional domains. In NeurIPS, 2020. 3
Zhang, C.,, Cao, X., Liu, W., Tsang, I., and Kwok, J. Non- parametric teaching for multiple learners. In NeurIPS, 2023a. 2, 2,3,4
Touvron, H., Cord, M., Douze, M.. Massa, F., Sablayrolles, A., and Jégou, H. Training data-efficient image trans- formers & distillation through attention. In ICML, 2021.
Zhang, C.,, Cao, X., Liu, W. Tsang, I., and Kwok, J. Non- parametric iterative machine teaching. In ICML, 2023b. 2, 3,4
Zhang, C., Luo, S. T.S., Li, L., Wu, Y-C.., and Wong, N. Nonparametric teaching of implicit neural representations. In ICML, 2024a. 2, 3, 5, 6, 20
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In ICLR, 2018. 2,9
Zhang, G., Dong, H., Li, Z., Chen, D., Wang, K., Chen, T. Liang, Y., Cheng, D., Wang, K., et al. Gder: Safeguard- ing efficiency, balancing. and robustness via prototypical graph pruning. In NeurIPS, 2024b. 8
Vishwanathan, S. V. N., Schraudolph, N. N., Kondor, R., and Borgwardt, K. M. Graph kernels. The Journal of Machine Learning Research, 11:1201-124: 2010. 3, 6
Wang, H., Jiang, Z., You, Y., Han, Y., Liu, G., Srinivasa, J., Kompella, R., Wang, Z., et al. Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling. In NeurlPS, 2023. 8
Zhang, S., Sohrabizadeh, A., Wan, C., Huang, Z., Hu, Z., Wang, Y., Cong, J., Sun, Y., et al. A survey on graph neural network acceleration: Algorithms, systems, and customized hardware. arXiv preprint arXiv:2306. /4052, 2023c. 2
Wang, P. and Vasconcelos, N. A machine teaching frame- work for scalable recognition. In ICCV, 2021.
Zhou, Y., Nelakurthi, A. R., and He, Unlearn what you have learned: Adaptive crowd teaching with exponen- tially decayed memory learners. In SIGKDD, 2018. 3
Wang, P., Nagrecha, K., and Vasconcelos, N. Gradient- based algorithms for machine teaching. In CVPR, 2021.
Zhu, X. Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In AAAI, 2015. 2,3
Wright, J. Coordinate descent algorithms. Mathematical programminng 151(1):3-34, 2015.
Zhu, X., Singla, A., Zilles, S., and Rafferty, A. N.
Wu, F., Souza, A., Zhang. T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In ICML, 2019. 4
An overview of machine teaching. arXiv preprint 2018. 2,
Zhuang, X., Zhang, Q. Wu, B., Ding, K., Fang, Y., and Chen, H. Graph sampling-based meta-learning for molec- ular property prediction. In IJCAI, 2023.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2:5113-530, 2018. URL http:/ http:///aaauuuummmmcmcm
Xia, F. Sun, K., Yu, S., Aziz, A., Wan, L., Pan, S., and Liu, H. Graph learning: A survey, IEEE Transactions on Artificial Intelligence, 102- 2021. 2
Xia, X., Mishne, G., and Wang. Y. Implicit graphon neural representation. In AISTAT, 2023. 22
12

---

Appendix
A. Additional Discussions
A.1. Notation Overview
Notation
Description
G(n) - (V,8)
Graph with n vertices and edge set
Set vertices (nodes) in the graph Set of edges in the graph d-dimensional feature vector with entries x;
&
Simplified notation for [æi]a
Xaxd
Feature matrix of all nodes (n d)
X (1.)
i-th row of X (feature vector of node i)
X (i.))
j-th column of X (feature across nodes)
e,
i-th basis vector (1 at i-th position, elsewhere)
A
Adjacency matrix of graph ((m)
G A)
Representation of graph with feature matrix and adjacency matrix
G
Collection of all graphs
y
Property of the graph (scalar or vector)
y
Space of graph properties (R or IR)) Set of m elements
{a:tm
diag(a1,.... 4m)
Diagonal matrix with elements A1 4m Diagonal matrix with m repeated entries a Set of natural numbers from 1 to d Positive definite graph kernel funetion Reproducing kernel Hilbert space (RKHS) defined by K Target mapping from G to ) Property f" (G+) of graph G₁
diag(a;m)
NJ fI. .d]
G")
H
f
Table 4: Summary of Key Notations.
A.2. The derivation of structure-aware updates in the parameter space.
Let's focus on the derivative of a two-layer GCN with summation pooling:
T
(G)
0x
0x (2)
Ox (2)
(24)
00
(
ow (3.1)
aw (1)
(s.A1)
the second layer
layer
Using the chain rule, we can calculate the derivative of (o(G) w.r.t. the second-layer weights (2),, which is a vector of size Kehy, as follows:
0x
01. ATAAl (maa) d X (1) K22) (2(2)
@2
(2(2)
1 [Ka] diag (1),
32) (22
size: Nin Kigh1
1
1mal
diag(o (A diag X (0), (())
(25)
size: nXKaR
size: 1x
13

---

Nonparametric Teaching for Graph Property Learners
The derivative of (o) w.r.t. the first-layer weights more complex. For í E Nb
ox (2)
01 A diag( X 2 Peee
:K2) W(2)
ow 11)
ow
(1)
Kg
size: Kg X
01 T A Akkal diag( X (1) eg k2) diag(e, [ K2) (
aw(!) (1))
size: Max1
size: Man
( (2)
(i-bith))
01 T Almal diag( x Besii2 K2)
W (2)
(1-h1
aw
size: Kanx1
X e, W (i-h+thi)
01 T lmal
x e. (e- (a-k1+
(W (1.)
ax (( (2)
aw (i-bxtha)
60
1 [ma)
ax w (igh1))
aw
GA
size: Kooho
δ A Iaaldag X ;0) W (i-hi+hi)
[Kal
(26)
Almil (x (K))
w
(e-hi twahs)
size: 1x hi
with ā Bo ding x pe Ww(
Orange marks the first-layer elements, green colors the second-layer elements, and
aAtiildia( x ps) w
I_ in purple refers to the summation pooling. If we use ReLU the activation function, à A (mlldiag( X (0); x1)
(A Inlldaa (0), ki)).
For the GCN shown in Figure 2, the derivative, i.e., Equation 25 is specified with Ki, = 3, 2 as
size: 2n 2/1
0x
diag(a (3 diag X (0) ())
(27)
OW (2)
size: 2
size: 1x 2/,
3ho
(2)
A (3] diag (x W
(28)
ow
A diag (x(())) W
size: 2
(1+b))
size: 1x3ho
When graph input into GCN, the adjacency matrix A governs the operations between nodes, ensuring the update is structure-awes aware by performing row-wise operations on the feature matrix. Meanwhile, the weight matrix W controls how the features are processed, by performing column-wise operations on the feature matrix.
14

---

Nonparametric Teaching for Graph Property Learners
Feature Matrix Xixtt Nodes
1
X
2
Fenture Marrix, Xyxd
1
Sides
Kg
X
My
Graph G ((()) (X',4)
Graph G(3) 4)
Nodes
2
3
4
0
1
Nodes
2
3
"Luee cpe
X(1
2
1
1
4Tch ano
26:00
3
2
Swika
4
3
X
Kg
Adjacency Matrix A'
Kg
Adjacency Matrix A
Weights
+
Comble
26 sw
Feature Aggregation
aiecoy
D Concatcnation
x fo
x = (C()
Figure 5: Graphical illustration GNTK computation: (o) ((a)) =
@fa(G)
Ofa(G")
aw (W + +...4 (1.) (1.)
( @fa(G")
00
00
(fe(G)
afe(G")
&felG)
(fa(G))
8fe(G) Ofa('))
aw (
@w
awe
(w (w
(1gh1) (1gh1)
A.3. Graph Neural Tangent Kernel (GNTK)
By substituting the parameter evolution (Equation 10)
a0 To (G.), y:)
ffr (G:)
(29)
Øt
N
Of (G.)
into the first-order approximation term (x) of Equation 16, obtains
(.)
7y
TC(ff (G.) (G.).
3R)
a (G.))
=
00
N
Ofe G.)
00
IN
N
7
T0C(for (G.), yi)
(-)
Of (Gi)
N
(G.)
00
00
N
(G.). (G.), yi)
K
(5f=(()
Ofor (G.)
7
N
Of (G.)
00
00
7
aL(S (G, (G.). y:)
[Ko (G. +lx+
(30)
N
ffrr (G.)
which derives Equation 17
ffe- "
TOC(Sor (G.),
00
[K (G&, 1) + o
(31)
at N 0fo (G.)
Øt
where the symmetric and positive definite Kor (G. == (G.) 0.fr(:)
is referred to as graph neural tangent kernel (GNTK) (Du et al., 2019; Krishnagopal & Ruiz, 2023). Figure illustrates the GNTK calculation process. simple terms,
80
80
15

---

Nonparametric Teaching for Graph Property Learners
examining model's behavior by focusing on the model itself, rather than its parameters, often involves the use of kernel functions.
It can be observed that the quantity ( 50
representing the partial derivative of the GCN with respect to its parameters,
present in K (G., (G.)
(-)e())
is determined by both the structure and the specific parameters 0*, but does
80
00
(G.) relies not only on the GCN structure and specific 0', but also on the input graph. If the input for (C,)(C.) is not specified, the GNTK simplifies to general form K (ts :). When a specific 30
not depend on the input graphs. The other term
89
graph G, is defined as the input for Ofat())
30 These are in line with the kernel used in functional gradient descent. By providing the input graph G., one coordinate of Kg is fixed, causing the GCN to update along Ka (G, based on the magnitude of (G.) This process aligns with the 50
30 GNTK becomes a scalar as Kg (G., G₁) (f (G.) (G,)(G,))
30
core principle functional gradient descent. In summary, both the GNTK and the canonical kernel are consistent their mathematical formulation and show alignment in how they affect the evolution of the corresponding GCN. Furthermore, Theorem highlights the asymptotic connection between the GNTK and the canonical kernel used in functional gradient descent.
16

---

Nonparametric Teaching for Graph Property Learners
B. Detailed Proofs
Before providing the detailed proofs, we first introduce the gradient of an evaluation functional Ec(f).
Lemma 7. The gradient of an evaluation functional Eg(f) f(G) H R V y Kg.
Proof of Lemma Let us define a function by adding small perturbation eg (E E R,g H) to f H. so that o= f + cg. since RKHS closed under addition and scalar multiplication. Therefore, for an evaluation functional
Fa[s] J(G H R, evaluate & at G as
Ea[Ø]
Eols + eg]
= Eclf] + +E
+ (elf) +0
(32)
Recall implicit definition of Fréchet derivative RKHS (see Definition 2) FGll + eg) = Fols] (V Foll).g)) (())
follows from Equation that have the gradient of evaluation functional y Kg.
Proof of Theorem By describing the evolution of GCN in terms of parameter variations and from high-level perspective within the function space, we obtain
ac(so (. Ofo (G.)
TC (G:))
(DFo
ofor())
10'
[K(G,
+
(33)
N
0fa((
00
00
Öt.
N
After the reorganization, we get
ac(fa (G.). (K(G,,)) Kg (G,, )1 =0
100
(34)
N (G.)
01
By inserting the evolution of the parameters
OC 0g:
7
TD (G:). (:)
(G:) Og
11
(35)
N
(fo(GG))
into the remainder, we have
7 (CCJ).(G.),.)) [K(G.,.) K (G., 31l = (-N Ta[(So (G.), 0f (G.)
(G.
(36)
N (G,)
00
N
When training a GCN with convex loss L. which is convex concerning fo but often not with regard to 0, we have the limit of the vector lim (G.)) = Since the right side the equation a higher order infinitesimal than the left, preserve this equality, leads us the conclusion that
(G.)
lim [K(G,,)) Kg. (G,, )1 0.
(37)
This means that for each G (GiNN, GNTK converges pointwise to the canonical kernel.
Proof of Proposition 6 By recalling the definition of the Fréchet derivative in Definition 2, the convexity of L implies that
0L
Oc
fo 0t
<
(38)
0fott
17

---

Nonparametric Teaching for Graph Property Learners
By identifying the Fréchet derivative of ac and the evolution of fer, the right-hand side term E be represented 05
E (gt+1,
H
[ (G,), Vi)
aL(fo (G.),
1KGll,.Ka [KG.lyv
N2
Of (G.)
Ofe (G:)
NN H
aC(fou+ (G))
af (G.), 3:) 0f (G:)
(IKG.IN [KG.lN)
N
Ofg--1 (G:)
OC (G:). y:)
@G(Sor+1 (G.),
K
(39)
N
Ofe: (G:)
afr+a (G+)
where = K/N, and K is an N x N symmetric, positive definite matrix with elements K KG;; G2) positioned at the i-th row and j-th column. For convenience, we adopt the simplified notation that a term in Equation 39 can be rewritten as
= 01,0 ((Jor: Gt). The final
17
10 C(for G.)) K 10 C(fa 1; ,;G.)l
N
1)
10 C(vr; (lv;), K (( + [0,, ((ot; [(or;
[0,, ((o:; G.))
N
1
10,, C(fo: G.)
K ;(fo:)))))))
=
N
1
10 f(fe; G.)) K ([0 L( [(J+:r [0,, [(o.
N
1I
10 C(for; G:) K [0g C(for; G:)) N
N
N (10 F(Sott1; G:)) T C(Sor; G+) (Uoo;
1I
K. (10fuc F( G.)] N - -[ffo G:)]
(40)
The last term in Equation 40 above can be further detailed as
( ((Jom:: G.) _ [0,,, C( G.) - 10 C(Jorn;; (.)o G.)
N
K (10 ((Jo+:;; G+)] N [0 C(sor; G.)
7
(10 C(Jomn: G.)) 10,, C(for; Gi) xx) K ((onn;;) [(fo. x)
N
T (0 C(Sort1; G.)) K (10)m)) [(Se++1; Gi)l ((l(((((GG))
N
7 C(for1:; G.) 8/ C(fer; G.)] N K 10 C(fart1; Gi) - -o,, C(for: G:)]]
1I
(10 C(fo+;; GT)) - 10,,, [(for; G.Il:) K [[oot 1 10 [(fo; Gior;
N
" + 4N [01 C(Jor: G:)) K [0,,, C(So;; G:))
(41)
Since K is positive definite, it is apparent that
[0 ((fort: G.) N 2 C(for G.) K (10 ((fon: (
1
1 1/ C(for: G.ll
N
non-negative term. Hence, by combining Equations 39, 40, and 41, obtain
3m 4N
= <
[(for; Gi) K 10 L(for; G:))
L(fo:;
11 [oraes C(Jort Gt) 0, L(Ser G.)] R [0 L(Se+t;; G.) - 0j [(for: G.)ly
(42)
18

---

Nonparametric Teaching for Graph Property Learners
Based on the definition of the evaluation functional and the assumption that L is Lipschitz smooth with constant > 0. the term in the final part of Equation 42 is bounded above
Blrtr [(fori;; 0g C(for: G.)]] N K
[o [(fo+1;; G.) 0% [(for Gi);;
(DL(fu)) OC(Ser
)} K DG. (DL(fon) OL(sor)
EG,
(Joo
0fgrt1
7² [EG, (fert) fo.)) ) K (EG, (fert So:))N
72 (Ifores - for) [K<GllN K ([KGiNN (feett f)
"MaaN,,KKa.lN, K (IKaily [KailT)
12y22 10), F(Sor: G.)]
[Ofgr C(Se:: G:)]N- (43)
N
N
Under the assumption that the canonical kernel is bounded above by a constant y > 0, we have (Kaaly Mitell,,KKallle (KaIN)H I (11,,117)).
and
K S N (1L|N, [1]))
As result, ! is bounded above by
N
[1|w XUX.
N Σ Cifo; Gi)
Σ
for C(fo;
N
1 [(fo: G.)
(44)
N
Meanwhile, the final term in Equation 43 is also bounded above:
(KKoN (Ka.lT) (KK.l,,KK:ll),
(KK,,,, (oo,lN,KK,,I1) [Ka.k)x,
7² 10 C(Sor G.)r;
K.
[05 C(for; G.)l
N
N
N
N
S
11
22
Y
Sz C(foc; Gt)
K.
y
Σ
0.ee C(for;
N
N
N
1
12232
N
N N
Σ
0111 C(ff: Gi)
Σ 1/ 11 C(fo: Gi)
N
N
1m1
N
122273
N
2
Σ
0z L(Jo;; Gi)
(45)
N
Hence, by combining Equations 42, 43, 44, and 45, we derive
s mm m (3- -
.p)2))
(
1
Σ
Oja [Woo; Gi) (lo:::::)))
(46)
N
which means
Qc Ōt
5 117
33 (3-
Σ
0z L(Soc; Gi)
(47)
Therefore, if < 2 it follows that
Oc <
1
Σ
Dzg 05e [[or; [(or(())
2²
1/7
1
N
aL(So: (G:),
(48)
0t
2
N
N
Ofo(Gr (G:)
19

---

Nonparametric Teaching for Graph Property Learners
C. Experiment Details
This section outlines the experiment details, covering the experimental setup, supplementary results, and brief analysis of graph-level and node-level tasks on benchmark datasets.
C.1. Experimental Setup
Device Setup. We mainly conduct experiments using NVIDIA Geforce RTX 3090 (24G).
Dataset Splitting. The train val test split configurations for the benchmark datasets are provided in Table
Dataset
train
validation
test
QM9
110000
10000
10831
ZINC
220011
24445
5000
ogbg-molhiv
32901
4113
4113
ogbg-molpeba 350343
43793
43793
gen-reg
30000
10000
10000
gen-cls 30000
10000
10000
Table Dataset splitting for the benchmark datasets.
Hyperparameter Settings. The key hyperparameter settings for all benchmark datasets listed in Table 6. The analysis of the hyperparameter, start-ratio, under GraNT(B) is provided in Table 7.
Dataset
x-list
batch-size
start-ratio (GraNT)
epochs
QM9
0.00005
[3, 2]
256
0.05
750
ZINC
0.0004
[5, 4, 21
256
0.05
1000
ogbg-molhiv
0.01
[,,
500
0.1
600
oghg-molpcha
0.015
3,
128
0.1
800
gen-reg
0.0002
[3, 2]
100
0.05
250
gen-cls
0.0002
[4.
200
0.05
500
Table 6: Key hyperparameter settings for the benchmark datasets, with the "start-ratio" specified for GraNT.
Dataset
Metric
0.05
0.1
0.2
0.4
0.8
full
MAE
0.0051
0.0053
0.0053
0.0053
0.0053
0.0051
QM9
Training time (s)
6392.26
6974.30
7918.51
10828.
14081.66
9654.81
ROC-AUC
0.7546
0.7676
0.7652
0.7618
0.7592
0.7572
ogbg-molhiv
Training time
1362.09
1457.39
1719.43
2157.05
3173.92
2163.5
ROC-AUC
0.9157
0,9156
0.9156
0.9156
0.9156
0.9150
gen-cls
Training time (s)
6145.72
6237.92
6939.95
9459.22
13153.81
11662.25
Table 7: Performance comparison w.r.f. "start-ratio" for different datasets.
C.2. Graph-level Tasks
We train the GCN using GraNT (B), GraNT (S), and the "without GraNT", all under a common experimental setup for graph-level tasks. For GraNT (B) and GraNT (S), we adopt a curriculum learning strategy (Bengio et al., 2009; Zhang al., 2024a). Intuitively, at the start of training, the model is undertrained and undergoes significant changes, which calls for more frequent selection by the teacher but with small subsets to help the learner better digest the provided graphs; in contrast, by the end of training, the model stabilizes and is able digest large subsets. Specifically, the selection interval progressively widens over 50 stages, beginning from the first epoch and gradually extending to the maximum interval. The initial selection ratios are predefined (i.e., the "start-ratio" hyperparameter) for each benchmark dataset. Additionally, for agbg-molhiv and molppba, we use the ReduceLROnF lateau (Hinton et al., 2012) as the learning rate scheduler, with the 'Ir' values in Table representing the initial learning rate. Besides, we activate the learning rate restarting scheme whenever new selection action is initiated. More experimental results and brief analysis are provided below.
20

---

boog-molpeba are provided in Nonparametric Teaching for Graph Property Learners
without GraNT
without GraNT
5.0
0.0070
with GraNT (B)
with GraNT (B)
Validation Loss
45
with GraNT (S)
Validation MAE
0.0065
with GraNT (S)
4.0
0,0050
3.5
0.0095
3.0
0.0050
28
0.0045
200
0
2000
4000
6000
8000
10000
0.0040
2000
4000
5000
9030
10000
Wallclock Time (s)
Wallclock Time (s)
(a) Validation Loss.
(b) Validation MAE.
Figure 6: Validation set performance of graph-level tasks on QM9 (regression).
without GraNT
without GraNT
with GraNT (B)
0.006
with GraNT (B)
Training Loss
with GraNT (S)
Training MAE
with GraNT (S)
0.007
0.005
2000
4000
6000
8000
10000
4000 6000
10000
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training MAE.
Figure 7: Training set performance of graph-level tasks on QM9 (regression).
First, we show the validation and training performance for the regression task on QM9 in Figure 6 and Figure 7, along with the training performance for the regression task on ZINC in Figure 8. For the classification tasks, the training performance on molliy is displayed in Figure 9. Moreover, the validation / training performance Figure 10 and Figure 1,, respectively.
For QM9, as shown in Figure 6, GraNT (B) and GraNT (S) require less time than "without GraNT" and show a quicker decline in validation loss and MAE curves. In the early stages, the curves follow a nearly linear trend. This occurs because the learning rate is small, allowing the model to learn simple features and adjust its parameters gradually at the beginning. As the optimizer moves through the parameter space with steady steps, the model begins capture more complex features, resulting in shift nonlinear phase in the validation loss and MAE In Figure the training loss and MAE curves show significant fluctuations early on, which can be attributed to the frequent selection process. This requires the model to rapidly learn and adapt to new teaching graphs. Over time. the curves take on a step-like shape, suggesting that the selection process is stabilizing and the model has become adequately adaptive. Similarly, the training loss and MAE curves for ZINC in Figure display similar However, is worth mentioning that GraNT (B) and GraNT (S) cut down the training time by around 3.5 hours for ZINC compared to "without GraNT", all while maintaining similar performance.
For ogbg-molhiv, as shown in Figure 9, the training ROC-AUC curve for GraNT (B) and GraNT (S) fluctuates due to the underlying data imbalance. However, the overall trend and final results align with expectations, even surpassing the "without GraNT" curve. To showcase the generalizability and scalability of GraNT, we further evaluate it on the large-scale multi-classification benchmark dataset molppba, which is 10 times larger than the oglg- dataset. Figure 10 shows that the validation AP (Average Precision) curves for GraNT (B) and GraNT (S) consistently outperform the "without GraNT" curve in the mid-to-late stages. Additionally, it is notable that GraNT (B) and GraNT (S) reduce the training time by approximately 13.8 hours compared to the "without GraNT" setup. These results further emphasize GraNT's ability to
21

---

Nonparametric Teaching for Graph Property Learners
6.0
without GraNT
without GraNT
0.0075
5.5
with GraNT (B)
with GraNT (B)
Training Loss
5.0
with GraNT (S)
Training MAE
0.0070
with GraNT (S)
0.0065
0.0060
4.0
0.0055
3.5
0.0050
3.0
0
6000
10003
15000
20000
25000
30003
5000
10000
15000
20000 25000
30003
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training MAE.
Figure 8: Training set performance of graph-level tasks on ZINC (regression).
0.90
1.2
without GraNT
0.86
with GraNT (B)
1.0
Training ROC-AUC
0.80
Training Loss
with GraNT (S)
0.8
0.70
0.6
0.66
without GraNT
0.60
with GraNT (B)
0.56
0.2
with GraNT (S)
0.50
500
1000
1500
2000
500
1000
1500
2000
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training ROC-AUC.
Figure 9: Training set performance of graph-level tasks on ogbg-molhiv (classification).
enhance training time efficiency on large-scale and complex datasets, particularly in the fields of chemistry and biomedical sciences. Additionally, the training loss and AP curves are shown Figure 11.
Furthermore, on the AMD Instinct MI210 (64GB) device, we also validate the effectiveness of GraNT for graph-level tasks on the QM9 dataset, highlighting its cross-device effectiveness. As illustrated in Figure 12, GraNT (B) and GraNT (S) converge more quickly than "without GraNT," showing a faster decline in validation loss and MAE. Roughly speaking, GraNT (B) and GraNT (S) save more than 40% of the time compared to "without GraNT" while achieving comparable results. The training curves are displayed in Figure 13.
C.3. Node-level Tasks
We train the GCN with GraNT (B), GraNT (S), and "without GraNT" using standard experimental setup for node-level tasks, while applying the same curriculum learning strategy used in graph-level tasks. To evaluate GraNT on synthetic data, we utilize graphon (Xu et al., 2021; Xia et al., 2023) to create the gen-reg and gen-cls datasets. Specifically, we set the resolution the synthetic graphon to 1000 1000, which produces graphs that can be easily aligned by arranging the node degrees in strictly increasing order. Additionally, each graph contains approximately 100 nodes, with a total of 50k graphs across both datasets. Lastly, use a 2-layer GCN with specific initialization assign regression properties or classification labels to each node, while the dimension of node features in all graphs is set to 40.
The training performance results for gen-reg and gen-cls are shown in Figure 14 and Figure 15. In particular, Figure 14 clearly demonstrates that GraNT converges more quickly in terms of wallclock time compared to "without GraNT," which initially drops faster. This faster initial drop may occur because, for gen-reg, training on all the graphs provides sufficient information about the implicit mapping from graphs to their properties, resulting in better validation performance in the early
22

---

Nonparametric Teaching for Graph Property Learners
1.0
0.36
without GraNT
0.8
with GraNT (B)
0.30
Validation Loss
with GraNT (S)
0.8
Validation
0.25
0.4
without GraNT
with GraNT (B)
with GraNT (S)
0
20000
40303
50000
50000
100000
120030 20000
40030
ECOOO 80000 100000 12000 Wallclock Time (s)
Wallclock Time
Validation Loss.
(b) Validation AP.
Figure 10: Validation set performance of graph-level tasks on ogbg-molpcba (multi-task classification).
without GraNT
with GraNT (B)
0.6
Training Loss
with GraNT (S)
0.5
Training
0.25
0.4
0.3
0.20
without GraNT
with GraNT (B)
0.1
with GraNT (S)
20000
40000
60000
60000
100000
129000
20000
40000
60000 60000 100000 120000 Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training AP.
Figure 11: Training set performance of graph-level tasks on ogbg-molpete molpeba (multi-task classification).
epochs, even though it requires more computational time. Over time, GraNT selects more representative teaching graphs (those with larger gradients), gradually accumulating enough information for the implicit mapping. In Figure 15, GraNT (B) takes the least time and shows faster decline in the training loss curve compared GraNT (S), while also reaching the final ROC-AUC results more quickly. Additionally, the training ROC-AUC curve exhibits significant oscillations early on, which can be attributed to the frequent selection of a diverse set of teaching graphs and the label imbalance.
In addition, we conduct experiments on node-level tasks with the gen-cls dataset using the AMD Instinct MI210 (64GB) device, further showcasing cross-device generalizability of GraNT. Specifically, GraNT (B) and GraNT (S) save about one-third of the time compared without GraNT, while achieving even better performance. The validation and training performance results are shown in Figure 16 and Figure 17, respectively. As observed, when the loss curves flatten their lowest points, the final validation and training ROC-AUC curves for GraNT (B) and GraNT (S) surpass those of the "without GraNT" baseline, highlighting GraNT's effectiveness in improving performance while reducing time consumption.
23

---

Nonparametric Teaching for Graph Property Learners
without GraNT
0.014
without GraNT
50
with GraNT (B)
with GraNT (B)
Validation Loss
4.5
with GraNT (S)
Validation MAE
0.013
with GraNT (S)
4.0
0.012
3.5
0.011
0.010
25
0.099
2.0
0.088
10930
Wallclock Time (s)
Wallclock Time (s)
(a) Validation Loss.
(h) Validation MAE.
Figure 12: Validation set performance of graph-level tasks for QM9 (regression) on AMD device.
without GraNT
without GraNT
with GraNT (B)
with GraNT (B)
0,018
Training Loss
with GraNT (S)
Training MAE
with GraNT (S)
0.014
0.010
20000 25000
5000
13000
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training MAE.
Figure 13: Training performance of graph-level tasks for QM9 (regression) on AMD device.
0.176
without GraNT
without GraNT
with GraNT (B)
with GraNT (B)
0.150
0,0030
Training Loss
with GraNT (S)
Training MAE
with GraNT (S)
0.125
0.0025
0.0020
0.075
0.0015
0.050
0.028
0.0010
0.000
500
1000
1500
2000
2500
3000
3500
500
1000
1500
2003
2500
3000
3500
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training MAE
Figure 14: Training set performance of node-level tasks on gen-reg (regression).
24

---

Nonparametric Teaching for Graph Property Learners
without GraNT
0.90
with GraNT (B)
Training ROC-AUG
Training Loss
with GraNT (S)
0.86
1.5
without GraNT
with GraNT (B)
with GraNT (S)
0.70
2000
4000
6000
3000
10030
12000
2000
4000
6000
8000
10000
12000
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training ROC-AUC.
Figure 15: Training set performance of node-level tasks on gen-cls (classification).
without GraNT
0.65
with GraNT (B)
Validation ROC-AUC
0.80
Validation Loss
1.50
with GraNT (S)
1.25
0.75
1.00
0.70
0.75
0.85
without GraNT
with GraNT (B)
0.60
with GraNT (S)
0.5
500
1000
1500
2000
2500
3000
500
1000
1600
2000
2500
3000
Wallclock Time (s)
Wallclock Time (s)
(a) Validation Loss.
(b) Validation ROC-AUC.
Figure 16: Validation set performance of node-level tasks for gen-cls (classification) on AMD device.
without GraNT
0.85
1.75
with GraNT (B)
Training ROC-AUC
0.80
Training Loss
1.50
with GraNT (S)
0.78
0.70
0.75
without GraNT
0.50
with GraNT (B)
0.25
with GraNT (S)
0
500
1000
1500
2000
2500
3000
500
1000
1900
2000
2500
3000
Wallclock Time (s)
Wallclock Time (s)
(a) Training Loss.
(b) Training ROC-AUC.
Figure 17: Training set performance of node-level tasks gen-cls (classification) on AMD device.
25


Reviews:
[{"review_id": "vdaIiOIoiw", "reviewer": "Reviewer_WzeW", "summary": "In this paper, the authors innovatively introduce a training paradigm termed Graph Nonparametric Teaching (GraNT) designed for graph property learners. Their main idea is to reinterpret the training of GCNs through the lens of nonparametric teaching, which selects training examples (graphs) strategically to accelerate learning. The authors demonstrate that parameter-based gradient descent updates in GCNs align with functional gradient descent in nonparametric teaching. Experiments show that the proposed approach can reduce training time to some extent across various graph-level and node-level tasks (regression and classification) without sacrificing much generalization performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the useful comments. We are deeply appreciative of the reviewer’s efforts to improve our paper. We take all comments seriously and try our best to address every raised concern. We sincerely hope that our response resolves your concerns.\n\n**[W1]** Thank you for your helpful feedback in improving our paper. Below, we present a comparison of GraNT with the recent works GMoE [1] and GDeR [2]. Our results demonstrate that GraNT outperforms these approaches in both training time and specific metrics. \n\nWe will include a more detailed discussion of this comparison in the revision.\n\n**ogbg-molhiv**\n|  | GMoE-GCN [1] | GMoE-GIN [1] | GDeR-GCN$^\\alpha$[2] | GDeR-PNA$^\\alpha$ [2] | GCN [3] | GCN+virtual node[3] | GraNT (B)  | GraNT (S)  |\n|---|------|----|----|----|----------|------|-------|------------|\n| Training Time |  3970.16  |  3932.06   |   1772.23   |   5088.88   | 2888.80 | 3083.16 | 1457.39 | 1597.69 |\n| ROC-AUC  |  0.7536  |   0.7468   |    0.7261   |  0.7616  | 0.7385 | 0.7608 | 0.7676  |  0.7705 |\n\n$^\\alpha$: batch_size=500, retain_ratio=0.7.\n\n**QM9**\n|   | MOAT$^\\gamma$  [4]   |  AL-3DGraph$^\\delta$ [5] |  AL-3DGraph$^\\zeta$ [5] |  AL-3DGraph$^\\tau$ [5]   |  GraNT (B)   | GraNT (S)   |\n|---|------|--------|-----|------|-------|-------|\n| Training Time |  69000  |     9200.27 | 9364.74 | 12601.77  |     6392.26  |  7076.37 |\n|   MAE      |  0.0236  |     0.7991 | 0.4719  | 0.1682  |    0.0051 | 0.0051 |\n\n$^\\gamma$: The training time is calculated as time_per_epoch * epochs = 92 * 750. The MAE value reported is from the paper.\n\n$^\\delta$: lr=5e-5, batch_size = 256, which matches our settings.\n\n$^\\zeta$: lr=5e-4, batch_size = 256.\n\n$^\\tau$: lr=5e-4, batch_size = 32, which corresponds to the default settings used in the provided code for that paper.\n\n[1] Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling. – NeurIPS’23.\n\n[2] GDeR: Safeguarding efficiency, balancing, and robustness via prototypical graph pruning. – NeurIPS’24.\n\n[3] Semi-supervised classification with graph convolutional networks. – ICLR’17.\n\n[4] Graph Prompting for 3D Molecular Graphs. - CIKM’24.\n\n[5] Empowering Active Learning for 3D Molecular Graphs with Geometric Graph Isomorphism. – NeurIPS’24.\n\n**[W2]** Thanks for your help in improving our paper. We have included the results with standard deviations for all validations. This demonstrates that the proposed GraNT not only achieves training time efficiency with theoretical justification but also exhibits stability. We will fix it.\n\n| GraNT | Dataset         | MAE ↓      | ROC-AUC ↑       | AP ↑       |\n|-------|-----------------|------------|-----------------|------------|\n| ✗     | QM9            | 0.0051$\\pm$0.0009 | -               | -          |\n| ✗     | ZINC           | 0.0048$\\pm$0.0004   | -              | -          |\n| ✗     | ogbg-molhiv    | -          | 0.7572$\\pm$0.0005       | -          |\n| ✗     | ogbg-molpcba   | -          | -               | 0.2579$\\pm$0.0058     |\n| ✗     | gen-reg        | 0.0007$\\pm$0.0001     | -               | -          |\n| ✗     | gen-cls        | -          | 0.9150$\\pm$0.0024        | -          |\n| ✓ (B) | QM9            | 0.0051$\\pm$0.0009     | -               | -          |\n| ✓ (B) | ZINC           | 0.0048$\\pm$0.0004     | -               | -          |\n| ✓ (B) | ogbg-molhiv    | -| 0.7676$\\pm$0.0036          | -          |\n| ✓ (B) | ogbg-molpcba   | -| -               | 0.2580$\\pm$0.0026 |\n| ✓ (B) | gen-reg        | 0.0007$\\pm$0.0001     | -               | -          |\n| ✓ (B) | gen-cls        | -          | 0.9157$\\pm$0.0013      | -          |\n| ✓ (S) | QM9            | 0.0051$\\pm$0.0009     | -               | -          |\n| ✓ (S) | ZINC           | 0.0048$\\pm$0.0004     | -               | -          |\n| ✓ (S) | ogbg-molhiv    | -| 0.7705$\\pm$0.0027      | -          |\n| ✓ (S) | ogbg-molpcba   | -| -               | 0.2579$\\pm$0.0047     |\n| ✓ (S) | gen-reg        | 0.0007$\\pm$0.0001    | -               | -          |\n| ✓ (S) | gen-cls        | -          | 0.9157$\\pm$0.0014      | -          |\n\n**[W3]** Thanks for your help in improving our paper. The analysis of the hyperparameter, start ratio, under GraNT(B) is outlined below:\n\nWe will include a more detailed discussion in the revision.\n\n|Dataset| Start_Ratio | 0.05 | 0.1  | 0.2  | 0.4  | 0.8  | full |\n|---|-------|------|-------|-------|-------|-------|-------|\n| QM9 | MAE   | 0.0051 | 0.0053 | 0.0053 | 0.0053 | 0.0053 | 0.0051 |\n| QM9 | Training time (s) | 6392.26 | 6974.30 | 7918.51 | 10828.18 | 14081.66| 9654.81 |\n| ogbg-molhiv | ROC-AUC | 0.7546 | 0.7676 | 0.7652 | 0.7618| 0.7592 | 0.7572|\n| ogbg-molhiv | Training time (s) | 1362.09 | 1457.39 | 1719.43 | 2157.05 | 3173.92| 2163.5 |\n| gen-cls | ROC-AUC | 0. 9157| 0.9156 | 0. 9156| 0.9156| 0.9156| 0.9150|\n| gen-cls | Training time (s) | 6145.72 | 6237.92 | 6939.95 | 9459.22 | 13153.81 | 11662.25 |\n\n**[Typo]** Thanks for pointing it out. We will fix it in the revision.", "claims_and_evidence": "The main claims are supported by both analytical derivations and extensive experimental validation across multiple datasets (e.g., QM9, ZINC, ogbg-molhiv, ogbg-molpcba).", "methods_and_evaluation_criteria": "The method is logically sound. The evaluation criteria make sense to me.", "theoretical_claims": "I didn't check completely the proof in the appendix. But it appears to me that the proof is well-presented.", "experimental_designs_or_analyses": "The experiment setup makes sense, but is not sufficient. I indeed have some concerns regarding the experiment as what will be elaborated below.", "relation_to_broader_scientific_literature": "The paper is well-positioned within the literature of graph neural networks.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- The theoretical integration of nonparametric teaching into graph property learning is original.\n\n- Experiments are performed on some large-scale graph benchmarks.\n\n- The presentation is clear and well-written. \n\n- Detailed derivations and additional results are provided in the appendix.\n\n**Weaknesses:**\n\nI do have some major concerns regarding the experiments of this paper.\n\nFirst of all, the comparative experiments are far from sufficient. The authors are suggested to compare GraNT with more GNNs. Also, it is known that the results on some datasets, such as ZINC, are sometimes unstable (see the benchmark paper [a]). It is suggested that the std be reported for the related results. This is critical because it can demonstrate whether the performance of GraNT is consistently better, especially given the method's reliance on gradient magnitude for teaching graph selection, which might be sensitive to label distribution imbalance and impact stability.\n\n[a] Benchmarking Graph Neural Networks.\n\nFurthermore, there is limited exploration of the algorithm's sensitivity to hyperparameters, such as the number of selected graphs in GraNT.", "other_comments_or_suggestions": "Minor typo: \n- Page 6, Line 295: “GNKT” should be corrected to “GNTK”.", "questions_for_authors": "Please address my aforementioned major concerns on paper experiments, such as insufficient comparative experiments and lack of stability analysis.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xIW8XfvgCd", "reviewer": "Reviewer_7pFN", "summary": "This paper presents GraNT (Graph Nonparametric Teaching), a novel framework that improves the learning efficiency of graph property learners (GCNs) using nonparametric teaching.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the encouraging comments and constructive suggestions. We sincerely thank the reviewer's efforts for helping us improve the paper. We hope that our response resolves your concerns.\n\n**[W3]** Very thoughtful question! We believe the idea and analysis behind GraNT have significant potential for broader extensions. As a fundamental neural network architecture for graph property learning, analyzing GCNs is an essential step in applying nonparametric teaching within this context before exploring further extensions. As mentioned in the Concluding Remarks and Future Work section, exploring other GNNs beyond GCN could be an intriguing direction. This could involve examining the core mechanisms of specific GNNs through the GNTK theory. Some relevant works on GNTK that might be insightful are [1,2]. However, this is outside the scope of the current paper and will be addressed in future work. In response to your curiosity, we have applied the GraNT algorithm to GIN [3] on the ogbg-molhiv dataset and will include additional discussion on this in the revised version.\n\n|   |   GIN [3] w/o GraNT    |   GIN [3] w/ GraNT (B)   | GIN [3] w/ GraNT (B)   |\n|---|--------------|-----------|--------------|\n| Training Time |  1446.91  |  982.66 (-32.09%)   |     965.37 (-33.28%)  |\n|   ROC-AUC  | 0.7694   |  0.7714  |     0.7705 |\n\n[1] Graph neural tangent kernel: Convergence on large graphs. – ICML’23.\n\n[2] Graph neural tangent kernel: Fusing graph neural networks with graph kernels. -NeurIPS’19.\n\n[3] How powerful are graph neural networks?. – ICLR’19.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Not sure if this proposed approach can be applied to more GNNs beyond GCN.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "1. Long training times due to slow convergence are common in many machine learning tasks, particularly in AI4Science applications, as explored in this paper. Therefore, I believe the proposed approach's improvement in learning efficiency is highly valuable.\n\n2. Section 4 is well-structured, progressing logically from theoretical analysis to algorithm design, making the presentation clear and effective.\n\n3. Graph Convolutional Networks (GCNs) are a fundamental GNN architecture, but more advanced GNNs have been developed with improved expressivity, scalability, and the ability to capture complex graph structures. Examples include MPNN, GAT, GIN, Graph Transformer Networks, as well as high-order and equivariant GNNs. These architectures are now more commonly used for complex regression and classification tasks at both graph and node levels, often requiring even longer training times. I’m curious whether the proposed approach can also be applied to these more advanced GNNs beyond GCN.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "Im7mcuP2J4", "reviewer": "Reviewer_2c6k", "summary": "The paper introduces GraNT, a novel paradigm that applies nonparametric teaching principles to accelerate the training of graph property learners (specifically GCN). By establishing a theoretical link between traditional parameter-based gradient descent and functional gradient descent, the authors design a greedy algorithm that selects a subset of graphs—those with the largest prediction discrepancies—to expedite convergence. Extensive experiments on both graph-level and node-level tasks across several benchmark datasets demonstrate that GraNT significantly reduces training time while preserving generalization performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for many constructive comments. We are deeply appreciative of the reviewer’s efforts to help us improve our paper. We take all comments seriously and try our best to address every raised concern. We sincerely hope that our response can resolve your concerns. Any follow-up questions are welcome. \n\n**[Theoretical Claims]** Sorry for the confusion. We would like to clarify that the theoretical analysis does not rely on the GCN being limited to two layers; it can be of any depth. Additionally, our empirical validation includes experiments with different depths and widths, as shown in Table 4. We agree with the reviewer that expanding the theoretical framework and empirical validation to more recent architectures would enhance the broader applicability of the work. We also believe that the concept and analysis behind GraNT have significant potential for wider extensions. Analyzing GCNs is an important foundational step in applying nonparametric teaching for graph property learning, which paves the way for further advancements. However, this is beyond the scope of the current paper and will be explored in future research. In response to your inquiry, we have applied the GraNT algorithm to GIN [1] on the ogbg-molhiv dataset and will provide further discussion on this in the revised version.\n\n|   |   GIN [1] w/o GraNT    |   GIN [1] w/ GraNT (B)   | GIN [1] w/ GraNT (B)   |\n|---|--------------|-----------|--------------|\n| Training Time |  1446.91  |  982.66 (-32.09%)   |     965.37 (-33.28%)  |\n|   ROC-AUC  | 0.7694   |  0.7714  |     0.7705 |\n\n**[Experimental Designs Or Analyses]** Thank you for your constructive feedback. We present comparisons of GraNT with recent works [2-6] below. Our results show that, with theoretical justification, GraNT outperforms these methods in terms of both training time and specific metrics. We will provide further discussion on this in the revised version to better emphasize the context and contributions of our work.\n\n**ogbg-molhiv**\n|  | GMoE-GCN [2] | GMoE-GIN [2] | GDeR-GCN$^\\alpha$[3] | GDeR-PNA$^\\alpha $ [3] | GCN [4] | GCN+virtual node[4] | GraNT (B)  | GraNT (S)  |\n|---|------|----|----|----|----------|------|-------|------------|\n| Training Time |  3970.16  |  3932.06   |   1772.23   |   5088.88   | 2888.80 | 3083.16 | 1457.39 | 1597.69 |\n| ROC-AUC  |  0.7536  |   0.7468   |    0.7261   |  0.7616  | 0.7385 | 0.7608 | 0.7676  |  0.7705 |\n\n$^\\alpha$: batch_size=500, retain_ratio=0.7.\n\n**QM9**\n|   | MOAT$^\\gamma$  [5]   |  AL-3DGraph$^\\delta$ [6] |  AL-3DGraph$^\\zeta$ [6] |  AL-3DGraph$^\\tau$ [6]   |  GraNT (B)   | GraNT (S)   |\n|---|------|--------|-----|------|-------|-------|\n| Training Time |  69000  |     9200.27 | 9364.74 | 12601.77  |     6392.26  |  7076.37 |\n|   MAE      |  0.0236  |     0.7991 | 0.4719  | 0.1682  |    0.0051 | 0.0051 |\n\n$^\\gamma$: The training time is calculated as time_per_epoch * epochs = 92 * 750. The MAE value reported is from the paper.\n\n$^\\delta$: lr=5e-5, batch_size = 256, which matches our settings.\n\n$^\\zeta$: lr=5e-4, batch_size = 256.\n\n$^\\tau$: lr=5e-4, batch_size = 32, which corresponds to the default settings used in the provided code for that paper.\n\n[1] How powerful are graph neural networks?. – ICLR’19.\n\n[2] Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling. – NeurIPS’23.\n\n[3] GDeR: Safeguarding efficiency, balancing, and robustness via prototypical graph pruning. – NeurIPS’24.\n\n[4] Semi-supervised classification with graph convolutional networks. – ICLR’17.\n\n[5] Graph Prompting for 3D Molecular Graphs. - CIKM’24.\n\n[6] Empowering Active Learning for 3D Molecular Graphs with Geometric Graph Isomorphism. – NeurIPS’24.\n\n**[Essential References Not Discussed]** Sorry for the confusion. We would like to clarify that the discussion on learning efficiency (Chen et al., 2018; Liu et al., 2022b; Zhang et al., 2023c) is included in the Related Works section, covering topics like normalization (Cai et al., 2021), graph decomposition (Xue et al., 2023), and lazy updates (Narayanan et al., 2022). We will enhance the presentation and include more detailed discussion in the revised version.\n\n**[W1]** Thank you for your suggestions. We would like to clarify that this paper is algorithmic in nature, introducing GraNT, a novel paradigm that improves the learning efficiency of graph property learners (GCNs) through nonparametric teaching. Our implementation leverages the PyG graph library, which is designed to optimize compilation efficiency, a concern that is independent of the main focus of our work.\n\n**[W2]** We have included the pseudocode in Algorithm 1, which outlines the core idea of our implementation, and our experiments are based on this. Detailed experimental settings and implementation specifics can be found in Appendix C. The code and data will be made available.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes. The paper effectively bridges nonparametric teaching with GCN training, offering a fresh perspective by interpreting the evolution of GCNs through the lens of functional gradient descent.", "theoretical_claims": "The overall proof seems correct. Yet, I didn't go through the details.\n\nThe issue is that the proofs are primarily based on (two-layer) GCNs, a special case of a relatively old baseline. Extending the theoretical framework and empirical validation to more recent architectures (e.g., Graph Attention Networks) would strengthen the claim of general applicability and broaden the impact of the work.", "experimental_designs_or_analyses": "The current evaluation compares only different variants of GraNT. Including comparisons with established efficient GNN models and state-of-the-art GNNs would better contextualize the contributions and highlight the advantages of the proposed method.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "One major issue of this paper is that while the author claims to solve the efficiency, non of the efficient GNN papers are discussed nor compared.", "other_strengths_and_weaknesses": "Although the paper claims that training GCNs is costly, it would be more compelling if it detailed how current efficient graph libraries (e.g., DGL, PyG) fall short in addressing these challenges. A more comprehensive discussion of experimental settings and implementation specifics would clarify how GraNT overcomes these limitations.\n\nBesides, the code and data are not available.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces graph nonparametric teaching to address the slow learning of standard graph property learners. Specifically, the approach introduces a theoretical framework for implicit mappings of properties via example selection. Theoretical and empirical results show the efficacy of the approach as compared to standard graph property learning approaches. The reviewers all agree that the paper is interesting, makes a novel contribution, and opens new directions for further research.
Decision: Accept (spotlight poster)