Gradient Scarcity in Graph Learning with Bilevel Optimization
Authors: Hashem Ghanem
Samuel Vaiter
Nicolas Keriven
Venue: Accepted by TMLR ()

Abstract: Gradient  scarcity emerges when learning graphs by minimizing a loss on a subset of nodes under the semi-supervised setting. It consists in edges between unlabeled nodes that are far from the labeled ones receiving zero gradients. The phenomenon was first described when jointly optimizing the graph and the parameters of a shallow Graph Neural Network (GNN) using a single loss function. In this work, we give a precise mathematical characterization of this phenomenon, and prove that it also emerges in bilevel optimization. While for GNNs gradient scarcity occurs due to their finite receptive field, we show that it also occurs with the Laplacian regularization as gradients decrease exponentially in amplitude with distance to labeled nodes, despite the infinite receptive field of this model. We study several solutions to this issue including latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, and reducing the graph diameter by optimizing for a larger set of edges. Our empirical results validate our analysis and show that this issue also occurs with the Approximate Personalized Propagation of Neural Predictions (APPNP), which approximates a model of infinite receptive field.

Published in Transactions on Machine Learning Research (06/2024)
Gradient Scarcity in Graph Learning with Bilevel Optimization
Hashem Ghanem
hashemghonem224 @gmail com
Institut de Mathématiques de Bourgogne, CNRS, Université de Bourgogne, France
Samuel Vaiter CNRS & Université Côte d' d'Azur, Laboratoire J. A. Dieudonné
vanuul..
Nicolas Keriven
dicolas.kertuenBeent
CNRS TRISA Institut de Recherche en Informatique et Systèmes Aléatoires
Reviewed on OpenReview: https: // opwprevvee.e........mmme net/ ptt/formm? id= 101JTIsVY
Abstract
Gradient scarcity emerges when learning graphs by minimizing loss on a subset of nodes under the semi-supervised setting. It consists in edges between unlabeled nodes that are far from the labeled ones receiving zero gradients. The phenomenon was first described when jointly optimizing the graph and the parameters of shallow Graph Neural Network (GNN) using single loss function. In this work, we give a precise mathematical characterization of this phenomenon, and prove that it also emerges in bilevel optimization. While for GNNs gradient scarcity occurs due to their finite receptive field, we show that it also occurs with the Laplacian regularization as gradients decrease exponentially in amplitude with distance to labeled nodes, despite the infinite receptive field of this model. We study several solutions to this issue including latent graph learning using a Seaph-to-Graphee model (G2G), graph regularization impose a prior structure on the graph, and reducing the graph diameter by optimizing for larger of edges. Our empirical results validate our analysis and show that this issue also occurs with the Approximate Personalized Propagation of Neural Predictions (APPNP), which approximates model of infinite receptive field.
1 Introduction
Semi-supervised learning is learning from datasets comprising both labeled and unlabeled points. This problem is usually handled with extra assumptions on the data. The main one, called homophily, refers to the fact that "ncarby" points are likely to have similar labels (Wang & Zhangl 2006). Morcover, points in many applications represent entities that are naturally linked to each other, e.g., in biology (Liu et al. 2018) or social media (Liben-Nowell & Kleinberg] 2003). There again, linked entities are likely to share the same label, which underlines the importance of exploiting the links when solving semi-supervised learning problems. Consequently, varions graph-base based methods have been developed for auni-supervised learning.
One issue with such methods is that their performance is highly dependent on the graph quality. This issue poses & significant challenge as real-world graphs are inherently noisy, significantly degrading the performance and leading to sub-optimal solutions. Many graph learning algorithms have thus been proposed in the literature to overcome this issue. Among these methods, mainstream approach is to optimize the graph structure by means of optimizing the performance in the downstream task.
This approach involves generating a graph that, when used by a graph-based method, minimizes some la- beling loss function. However, graph-based methods themselves require an optimization process to minimize labeling loss function too. This problem can be formulated in two different manners. In the joint opti- mization formulation, single loss function is used to assess both the graph and the graph-based model,

---

Published in Transactions on Machine Learning Research (06/2024)
and both objects are optimized simultancously. In the bilevel optimization formulation, each of the graph and the graph-based model is assessed by its own loss function. In this scenario, the graph loss function takes in input the optimized graph-based model trained while fixing the graph, i.e., we have a constrained optimization problem where the constraint involves the output of another optimization problem. In both cases, the optimization is usually handled using gradient- methods.
For shallow Graph Neural Networks (GNNs); Fatemi et al. (202)) show that joint optimization leads to gradient scarcity. It refers to the fact that connections between unlabeled nodes "far" from the labeled ones receive zero gradients, i.e., they receive no supervision during the optimization and are not learned. This is due to the finite receptive field of message- passing GNNs, which is defined as the neighborhood range captured by a node during the message passing phase. In this work, we focus on bilevel optimization and prove that gradient scarcity also occurs for shallow GNNs, despite the additional dependency between the parameters in this setting. We also show that this issue emerges with other graph-based models. We do that theoretically and empirically for the Laplacian- based label propagation, which, unlike GNNs, has an infinite receptive field, and empirically for the Approximate Personalized Propagation of Neural Predictions (APPNP) (Gasteiger et al. 2018), which approximates a model of infinite receptive field.
The rest of the paper is organized as follows. The rest of this section presents the considered graph-based models for semi-supervised learning, and the bilevel optimization framework. Section reviews related work. Sections 3 and | presents our theoretical analysis of gradient scarcity for shallow GNNs and the Laplacian regularization model, respectively. Section 5 proposes three strategies that can be used to mitigate this issue. We finally present our empirical results in Section G
1.1 Graph-based models for semi- supervuid learning
A graph G is pair (V, E), where V is a set of n nodes and C V is set of edges. We represent graph by its adjacency matrix A E Raxx, where A.j is the weight of the edge between nodes i.j. We denote by X E R=xp the feature matrix whose rows inchude the features of corresponding nodes.
Definition 1.1 (Distance between two nodes). We say that node i is k-hop from node j if the minimum number of edges forming path from i to j is k.
Definition 1.2 (Node distance to subset of nodes). A node i is said to be k-hop from subset of nodes if the minimum number of edges forming a path from i to a node in the subset is k. We further refer to the set of nodes that are at most k-hop from i by its k-hop neighborhood.
Definition 1.3 (Edge distance to subset of nodes). The distance of an edge (i.j) to a subset of nodes equals the minimum between the distance of i and the distance of to this subset.
We look at transductive supervipe learning problems, where we have set of points, subset of which is labeled, and the goal is to approximate the labeling function on unlabeled points. Formally, have (X Gobs, Yose), where Gors is the observed graph, Xobs are the observed node features (we will drop the subscript and write X in the rest of the paper) and Yobs E Ih" contains the labels of a subset of points Ver, i.e., it containes the labels at coordinates E Vir C V and, e.g., not-a-number "NaN" outside of Vyr. There are roughly two main strategics to solve semi-supervised learning problems. The first to propagate known labels using a regulorization process. Predicted labels read the following:
Yite (A) Earg min 1 Σ ((Y,, (Yobs)) +AR(YA)) VeV,
Miel YEB
where B is an admissible set, is usually a smooth loss function, R. is a regularization term, and À is a balancing parameter. In regression tasks, B is commonly the space R", and E is chosen to be the Mean Squared Error (MSE). Whilst in classification tasks, the i-th element Y, is not a scalar but rather a vector holding the probability distribution over classes. Formally, B- = (Y E RaxC Vi, Σe Y.e = 1, Vi,c, Y., 2 0), where C is the number of classes. In this case, L is the Categorical Cross Entropy (CCE) loss function.
In fact, graph regularization methods usually differ from each other by the choice of the regularization function R. A popular choice is the Laplacian regularization, (Slepcev & Thorpe! 2019 Pang & Cheung
2

---

Published in Transactions on Machine Learning Research (06/2024)
2017
R(Y, A) =
Σ 1
Ar, Y - Yzli
(2)
E
Note that here the node features X are not used.
The second main strategy in semi-supervised learning is to train a parametrie model Yw (X,, A) parameterized by the parameters W, such as GNNs. The objective reads:
YGNN(A) Yw- (X, A), where
1
W arg min
Σ
(X, A)) (Yota)s)
V
SeVer
In this paper, message-passing GNNs with sum aggregation (Morris et al 2019 The first layer is X X, propagated as
- 6 Wx"" + (b
(4)
where w w E Rd-ixx are learnable parameters, 6ddl E R& is learnable bias, di is the output dimensionality of the 1-th layer, 1, [ 1]T R"; and á non-linear function applied element- wise. The output Yw( (X, A) x is obtained after ls rounds of message passing, and the parameters are gathered as W = (w]" w b0
Another advanced example of parametric models is the Personalized Propagation of Neural Predictions (PPNP) and its fast approximation APPNP (Gasteiger el al. 2018), which enable an infinite receptive field unlike shallow GNNs such as the model in Eq. 4 Note that the Laplacian regularization model enjoys infinite receptive field well. In the presented material, analyze the gradient scarcity phenomenon for both GNNs and the Laplacian regularization, which is possible thanks to their simple models, and we empirically verify that it occurs with APPNP.
1.2 Joint and bilevel optimization for graph learning
We learn graph by learning its adjacency matrix. In the joint optimization setting, the graph and the graph- based model are optimized simultancously by minimizing single loss function, usually using a gradient-basct based algorithm. For instance, denoting by W the parameters GNN model, the joint optimization reads:
min A.W
Σ (X), EVV.
(5)
Ven
In this scenario, A and W are simultaneously updated in each iteration of the gradient-based algorithm.
In the bilevel optimization scenario, the graph has its own labeling loss function, which is a function of the optimized graph-based model. In the theoretical part of this paper, we analyze gradient scarcity under the bilevel optimization setting when the traph-based model is either a GNN or the Laplacian regularization. Therefore, we restrict the following formulation to these two cases. Given second set of labcled nodes Vout V distinct. from Vir, and set of admissible adjacency matrices A, the bilevel optimization cast
min Four(A)
Σ (AY(A); (Yas))))
(6a)
AEA
[onel
iEVout
s.t. Y(A) =aN)=Ya
Y(A) YRoe
(6b)
That is, the minimization the objective function Fouts called the outer optimization problem, involves (A),, which itself the result of an inner optimization problem, either equation over W equation ] over Y. The objective function Fous used optimize the graph, and the objective function F.,, is used optimize the graph-based model. Several models possible for A:
3

---

Published in Transactions on Machine Learning Research (06/2024)
Full learning: A= = [a, b)mxx is the set of all weighted adjacency matrices (generally with some bounds a, b on the weights). This choice necessarily leads to an impractical quadratic complexity on the minimization.
Edge refinement: the learned adjacency matrix has the same zero-pattern as the observed adjacency matrix, that is, we learn weights only on existing edges.
A = {A
A.j- when (Anhe) = 0}.
The complexity is proportional to the number of edges, generally less than quadratic in as graphs tend to be sparse, which makes edge refinement more scalable than the full learning setting.
Generalized edge refinement: same principle, but the zero-pattern is given by modification of the observed adjacency matrix. For instance, taking the zero-pattern of A'he yields an edge between nodes that are less than r-hop from each other in Gobs, where nodes and j are r-hop from each other if the length of the shortest path between them is r.
Latent graph learning: the learned graph is the output of parametric model, that takes input the node features and the observed graph: A = {A fo X)). We will refer to such models as Graph-to-Grap (G2G).
Both the inner and the outer problems are treated by gradient-based based algorithms. We refer to the outer gradient Fout, whether with respect to A or to 8, as hypergradient.
To our knowledge, the literature has yet to present benchmarks comparing the bilevel and joint frameworks in graph learning. However, we can distinguish two primary differences between them. Firstly, the bilevel framework treats the graph a hyper-parameter, while the joint framework perceives it in similar way to the GNN parameters. Secondly, the joint framework is more prone to overfitting. This issue is commonly addressed through graph regularization and similar techniques (Wang & Leskovec, 2020 Fatemi et al, 2021). Exploring further comparisons between these frameworks, particularly in terms of their performance and limitations, is an intriguing direction for our future research.
1.3 The resolution of the joint and the bilevel optimization problems
In fact, the solution of any of the two problems cannot. be exactly computed. For the joint optimization problem 5] the solution does not enjoy a closed-form expression that can be evaluated. In general, this problem addressed using gradient-based algorithms, where both A, W are updated at every iteration in order to converge to a "good" local minimum.
For the bilevel optimization problem f the problem is intractable since neither the solution of the inner problem nor its gradient w.r.l. A (or to 0 with G2G models) has closed-form expression that can be evaluated. To overcome this difficulty, we unroll (Gregor & LeCun 2010) Tin iterations of gradient-basee optimizer applied on the inner problem, then use higher-order Automatic Differentiation (AD) to trace these iterations and approximate the hypergradient. this work, we use the Higher package (Grefenstette et al. 2019) to perform the aforementione ioned aulomatic differentiation.
1.4 Contributions
Previous works observed gradient scarcity when optimizing the graph and a shallow GNN using joint op- timization. Indeed, a k-layer GNN computes the label of a node using information from r-hops far nodes with r S k. This label is then not function of edges connecting nodes outside this neighborhood, and the term in the labeling loss corresponding to this label returns mull gradients those distant edges. However, it is not straightforward how to extend this argument for bilevel optimization. Specifically, the previous discussion necossitates that the derivatives of the GNN paramcters w.r.t. the distant edges equal zero after every gradient-based update. This applies to the joint optimization setting by construction, but is not easy to prove in the bilevel optimization setting where additional dependency exists between the parameters of the problem. Morcover, if the problem holds in the bilevel optimization setting, the roles of Vi, and Vout need to be clarified. Another question is if this problem is mitigated by resorting to graph-based models with infinite receptive field, e.g., the Laplacann regularization and APPNP.
4

---

Published in Transactions on Machine Learning Research (06/2024)
In this work, we prove that hypergradient scarcity occurs under the bilevel optimization setting when adopting shallow GNNs as the graph-based model. We show that using a k-layer GNN induces null hypergradients on edges between nodes at least k-hop from labeled nodes in V For the Laplacian regularization, we prove that the problem persists, as hypergradients are exponentially damped with distance from labeled nodes. We empirically validate our findings and show that the problem occurs with the APPNP model as well. Then, we test three possible strategies to solve this issue: refining& power of the given adjacency matrix, graph regularization, and latent graph learning with G2G models. Furthermore, and overfitting, in the sense that solving the former does not necessarily resolve the latter. To the best of our knowledge, this is the first work that mathematically tackles the gradient scarcity problem in graph learning with bilevel oplimization, and examines the phenomenon for models with infinite receptive field.
empirically distinguish between hypergradient scarcity
2 Related work
Bilevel optimization has many applications like multi- task and meta learning (Bennett et al. 2006 Fla-
mary et al. 2014 Franceschi et al. 2018). See Coosonn et al. (2007) for a comprehensive review of applications.
Graph neural networks GNNs. Different GNNs implement different flavors of message passing. One of the simplest GNNs is the model in Eq. E (Morris et al.] 2019). Another influential version is the GCN model (Kipf & Welling, 2017), which simplifies the spectral convolution on graphs to a first-order approximation. Other popular variants include S²GC (Zhu & Koniusz, 2020), GNN-LF /HF (Zhu et al., 2021), graph autoencoders (GAFs) (Kipf& & Welling, 2016), graph generative adversarial worwsrks (Liu et al. 2019), etc. These models address different challenges, such as scalability, interpretability, and robustness.
A limitation of GNNs is their finite, usually small, receptive field, which cannot be increased by adding more layers due to the oversmoothing problem [Keriven 2022). One line of work to address this issue includes
deep GNNs, which can leverage higher number of layers
(Xu et al. 2018 Huang et al. 2018 Li et al. 2019
He et al. 20166a b. Ruiz et al., 2020 Zhang et al. 2022 A second line of work focuses on the way graph
information is exploited rather than on the model structure
(Wu et. al. 2019 Liu el al.
2020 Rossi et al.
2020 Li et al. 2020 For instance, PPNP, its approximation
2018 and PPRGo APPNP Gasteiger et al.
[Bocchesski et al. 2020) use the personalized PageRank (Page 1998) method to propagate node information
to the entire graph while avoiding the oversmoothing problem. PPNP and APPNP have produced state-of- the-art results on several node classification datasets. We later theoretically show that the GNN in Eq. (4) promotes the hypergradient scarcity problem when adopted in the bilevel framework. We empirically show the same for APPNP, even though it approximates infinite receplive field.
Graph learning. One simple learner is the K-Nearest Neighbors (k-NN) technique and its variants (Rwwei & Saul 2000 Tenenbaum et al.) 2000; Zhu et al. 2003), where a similarity metric is deployed to detect the most similar nodes to each node. Another line of research focused on assigning weights to observed edges or to edges constructed with N-NN-like methods using similarity metric (Gretton et al. [0066] Zhu ct al. 2003 Kapoor et al., 2005 Li et al., 2018). Locality-inducing methods optimize edge weights in given graph by promoting the assumption that each node can be produced by an edge-weighted sum of its neighbors (Saul & Roweis 2003 Wang & Zhang, 2006: Daitch et al. 2009). This methodology is usually noise sensitive and prone to overfitting as the number of edges is larger than the number of nodes (Qiao) ct al. 2018). maoothhnss-indducing methods learn a graph that promotes smoothness seen in node features (Hu et al.] 2013 Kalofolias 2016). This framework costs O(n2) so does not scale well However, some approximations roduced the complexity to O(n log(n)) (Kalofolias & Perraudin 2017).
Another mainstream approach is to optimize the graph such that it improves the labelling performance in the downstream task. Such works usually optimize together the graph and the graph- based model. [Stretcu ct al. (2019) proposed the deep model GAM, which is trained by penalizing the absence of an edge between nodes with the same label. Wang & Leskovee (2020) optimize the edge weights and a GNN model using joint optimization. To alleviate overfitting resulting from learning a large number of parameters, the authors regularize the graph using the label propagation model (Zhul 2005). Similarly, Fatcmi et al.) (2021) use an- other technique to regularize the graph. Attention mechanisms evaluate edge weights after every GNN layer based on node similarity (Luong et al. 2015: Vaswani et al. 2017 Veličković al.] 2018 Kim & Oh 2021
5

---

Published in Transactions on Machine Learning Research (06/2024)
The previous methods produced state-of-the-art results many node classification tasks. Here, we consider the graph learning problem when formulated as supervised bilevel optimization problem. Franceschi et al. (2019) adopted bilevel optimization to learn the parameters of Bernoulli probability distributions over inde- pendent random edges. This mothod produced competitive results but it includes learning n² paramoters which limits scalability. WWan & Kokel (2021) use the bilevel framework to sparsify observed graphs while keeping connected. Resulted graphs do not necessarily outperform the observed ones.
Gradient scarcity was identified by Fatemi et al. (2021) where the authors optimized the graph and shallow GNN model using joint optimization. The authors showed that when adopting k-layer GNN classifier (with h = 2 in their case), edges between unlabeled nodes do not reccive any supervision if they are at least 2-hop from labeled nodes. They referred to this issue as the supervision slarvation problem. They quantify the starvation for the special case of Brdös-Rényl graphs. Note that gradient scarcity and supervision starvation refer to the same phenomenon. This issue cannot be resolved by adding more layers to the GNN as more data and labels will be needed for training, and due the oversmoothing problem. To overcome this issue, authors proposed to regularize the graph by enforeing the assumption that good graph must also perform well in denoising node features.
That said, authors implicitly assumed no dependence between the GNN parameters and the graph when identifying gradient scarcity, which is the case in joint optimization but not in bilevel optimization. To the best of our knowledge, this issue has not yet been studied for the bilevel optimization setting. Moreover, it is not clear if this problem is resolved with graph-based models with infinite receptive field, e.g., the Laplacian regularization and APPNP. We treat both these topics in our work.
Liu ct al. [022) stated that optimizing both the graph and GNN model under the supervision of classi- fication task introduces reliance on available labels, bias in the edge distribution and even reduces the span of potential application tasks. Still, this statement is not accompanied with a theoretical justification. To overcome this problem, authors suggested to avoid label-based graph optimization, and proposed an unsu- pervised graph learning framework. Although the unsupervised framework proved effective and competed state-of-the-art methods, we believe that labels contain informative knowledge that not exploited when deploying unsupervised learners, and that better results are obtained by getting the best of both worlds.
3 Hypergradient scarcity with shallow GNNs
In this scction, we consider the bilevel optimization with the GNN model in Eq. 4 ie.. Y(A) = YANx(A) Yw- (A, We place ourselves under the edge refinement setting where we optimize the weight of every existing edge in Aose.
In Fatemi et al. 2021). the authors demonstrated that the predicted node label using a 2-layer GNN integrates information from nodes of distance less than two hops, i.e,, the label is not a function of edges connecting nodes at least 2-hop far away. Consequently, when optimizing the graph by minimizing the classification error of that label via a gradient-based algorithm, these edges receive zero-valued gradients. However, the authors used joint optimization where there is no dependency between W and A, i.e., Jw (A)= = O at every gradient-based iteration. This is not the case for bilevel oplimization. In this section, we first examine the joint optimization scheme, and prove the existence of the problem for generic number of layers k similar to Fatemi et al. (2021). For the bilevel optimization setting, we then prove that the optimized parameters W* are not a function of edges connecting nodes at least k-hop from nodes in Vyr. After that, we conclude that hypergradient scarcity holds in the bilevel sctting for edges connecting nodes at least k-hop from nodes in the wnion ViP U Vout.
3.1 Gradient scarcity for joint optimization
In this initial result, we assume that the parameters W do not depend on A, i.e., W is not a function of A. Indeed, by construction, this is the case after every maddient-based iteration f in the joint optimization setting, where we have aw, o, with W,, A, being the updated states of W, A at iteration f, respectively. This aA. hypothesis is not satisfied in the bilevel optimization setting, which we will address in subsequent sections. The next theorem shows gradient scarcity in the joint optimization setting by examining Yw (A, X).
6

---

Published in Transactions on Machine Learning Research (06/2024)
Theorem 3.1. Let Yw (A, be the output of k-layee GNN parameterized by W as in Eq. (4) Let J,j,u be such that nodes ř,j are at least k-hop from node u. Assume that BW 0. Then we have
BA..;
@(Yw)u =0 =0.
aA.j
Proof. The proof is done by induction k. For k 1, this is indeed the case since X X does not depend on A. and that Aig does not belong to the row A..: which is the only row in A that contributes in the value (x
Assume that the statement true for some arbitrary positive integer h, we show that it is also true for (k+1). If two nodes i are least 11+ far from node u, then clearly they are at least k-hop far from it too. Thus from the induction assumption, we have that (X (kk )u.: is independent of A.g. Also, W aw does not depend on As, since we assume HA;,; = 0. Therefore, (X Ju.: in Eq. (40 does not depend on Aij too.
In a similar way, if i are at least (I: + 1hp far from u, then they are at least k-hop far from any of its neighbors v where A., # O. Therefore, for all Au,o * 0, then 8(x1)) = 0. Morcover, .A.,, 0 since DA
aw!!-1l
we assume aw aA., 0. This makes (AX(*) (1tl )a.- = Au. X W [++ in Eq. (4) independent of A.j. This concludes the proof, a(Yw). 0(x(++3)) O. .Ai.
DA.,;
Note that the number of hops & that defines edges affected by gradient scarcity equals the number of the GNN layers k. That is, Thcorem 3.1 shows that the labels (Yw)a )a on training nodes u Ver are not a function of edges between nodes at least k-hop from these training nodes. Consequently, the gradient of the labeling loss function in Eq. (5) equals zero these edges.
3.2 The gradient of the optimized parameters
With the assumption that W is not a function of the adjacency matrix A, Theorem 3.1 states that edges between nodes at least k-hop from the training nodes receive supervision. However, in the bilevel op- timization scenario, after the first outer iteration W may depend on A. The next theorem shows that hypergradient scarcity still occurs in the bilevel optimization framework, as the "optimal" parameters used in practice are the result of a gradient- based algorithm. More prociscly, we consider a sequence
W+11 = W. - (W,, Vw, Fin)
(8)
where Qt is a smooth function. Note that W, does not necessarily converge towards the true optimal point W*
Theorem 3.2. Let A be an inpul graph to a k-lager GNN parometerized by W in Eq. 44) and We be the output obtained by optimizing equation g for W using gradient-bnsed ilerates sequence. Let i, be nodes that are at least k-hop from any node in Ver. Then, for all t e N, aW,(A)
OAi = 0
(9)
Proof. The proof is carried out by induction on the iteration index of the gradient-based optimizer. Denote by F., the objective function in equation 3 For = 0, Wo is the initialization of W which usually random and docs not depend on A. For t 2 we assume that aw,
2A.; 0 and prove this must be true for ++1 1. By differentiating Eq. SS w.rrt. Aij, and under the induction assumption, it is sufficient to show that aQ. Fin)
Fin)
to prove that 8W, (W.l1(A) O. Therefore, given the induction assumption and using the 8Ai
8Ai
chain rule, proving that a(V,,Fu.l 0 is sufficient to complete the proof. The gradient Vw, Fin writes:
BA.
Vw,Fun
1
Σ
Vw,ef VY, (x, (Yobe)u)
Verl

---

Published in Transactions on Machine Learning Research (06/2024)
might be a function of A through the terms W and For all E Vir: the term Vw, Vw. (X, (Yots)))
0 from the induction assumption, and, given that, we have ((Yw, (x.41) # from Theorem 3.1 Thus, we have for all u E Vir, dA,s Ww, é (X,A)) A)) (Yoba)u) = 0. This concludes
#
(Ywa (X, But aw,
J...,
OA.,)
the proof of Eq. 99 as gives 8(Vw, Fin) O. 8A
One notes that Theorem 3.2 still applics when the joint optimization problem 5 is augmented with a regu- larization term that regularizes the graph as in Wann & Leskoved (2020); Fatemi et al. (2021) for instance. For that this term does not affect updates performed on the parameters W. In this work, we are interested in studying the gradient scarcity phenomenon seen in the gradient the labeling loss term as in Eq. (5) Thercfore, we do not consider such regularization terms in our analysis. However, we will see in Sections and 0 hat graph regularization one effective technique to alleviate gradient scarcity.
3.3 Hypergradient scarcity
Finally, we put the two previous results Logether. The next theorem states that within the bilevel optimiza- tion framework, edges between nodes at least k-hop from nodes in Va, U Vout receive zero hypergradients. Theorem 3.3. Let Yw be a k-layer GNN following the model Assume that the inner optimizalion problem is solved with a gradient-basce algorithm as in Eq. 81. Then, for any pair of nodes i. at least k-hop from nodes in Vont U Ven, we have 0f
0.
UA.,
Proof. Directly from Theorem 3.2 we have that aW.(A) = since i,j are at least k-hop far from nodes in AA...
Vir. This makes possible apply Theorem 3.1 to get that Vu E Vouti a(Yw,), O, as i, are at least 8A
k-hop far from nodes in Vour and @W.(A) = This concludes the proof as Four penalizes the classification error only on nodes in Vout-
JA.,;
Theorem 3.3 shows that the hypergradient scarcity problem emerges when solving edge refinement tasks: if two nodes are at least k-hop far from nodes in Vour U Vtr in Aoha, the edge in between receives no hypergradients. In Section 5 we will examine several strategics to mitigate this phenomenon.
4 Hypergradient scarcity with the Laplacian regularization
In the previous section, we have seen how the finite receptive field of shallow GNNs directly induces the hypergradient scarcity problem. We now examine hypergradient scarcity when (AA) Y Reg with the Laplacian regularization 2 Indeed, in this case the inner model does not have finite receptive field, in the sense that in general 0Y () + 0 for all i.j, unlike the shallow GNN case proven by Theorem 3.1
-A.,,
Surprisingly, we show that hypergradient scarcity still occurs in some sense. More preciscly, we prove that the magnitude of hyperrradients decreases exponentially with the sum of the distance to Ver and the distance to Vout-
To proceed, we consider regression downstream tasks as the inner minimizer Y(A) enjoys a closed-form expression in this case. Recall that in these lasks, we employ the MSE loss as in Eqs. 1 and 6 Let S.n E R' be the diagonal selection matrix whose entries equal if the corresponding node is Ver and 0 otherwise, the solution Y (A) reads:
S., Yous Y(A) = (5:m. +
where S.n = S.n i = |.-1 |2] P..L- L(A) D A the Laplacian of the graph, and D is the diagonal degree
matrix that includes node degrees on the diagonal: D., = E, Ad,. For simplicity from now on, we denote
B 5., + AL. Then, we write (AA) as:
Y(A) 1 Y
(10)
8

---

Published in Transactions on Machine Learning Research (06/2024)
It is well-defined thanks to the following result.
Lemma 4.1. Assume that the gruph is connected. The eigenvalues Ma of B sotisfy, for all i:
0 < Munin S S Puna S
|Verl + 22
(11)
Given that, state the main result of this scction.
Theorem 4.2. Let nodes i,j be at least k-hop from Vout, and q-hop from Ver- Then we have:
F Fout AAij
/
Voual + Pmin v Vir
Yout
2
Vo00 (1 - 1))+t
(12)
Pmin
Ver
E
where μ = Pmia and yoo = |Yobelloe
Since both Pmins Maxx are strictly positive, as shown the proof Section 4.3
then < μ Therefore, Thcorem 4.2 states that the magnitude of the hypergradient exponentially damped in speed that is least proportional to (1= leading to form of hypergradient scarcily.
The rest of this section is dedicated to proving Lemma 4.1 and Theorem 4.2 We express Y (A) as Neumann scries, then we bound the derivative of terms in the resulted scries, and by extension the hypergradient.
4.1 Neumann series expansion and the proof of Lemma 4.1
In the first step, we re-write the inverse of B using Neumann series. We first need to prove that ||- B < (see e.g., Stewart (1998)), where I E R=** is the identity matrix. Remark that the eigenvalues of I - B are where /4n are the eigenvalues B. Assuming the graph is connected, the ordered eigenvalues
Ln of L satisfy:
0 = v1 < U2 S un 2
(13)
The last inequality holds because || < 2dmax I Fl. where dmax is the maximum degree of the graph. Let uI,..., Un be the eigenvectors of L, where u x 1, is associated to 0.
Proof of Lemma 4.1 We have ||S < 1//Vee and || s 2 so by a triangular inequality the upper bound is proved.
Using the eigendecompositionn of L and recalling that is = 0, for any æ E IR":
x Bx Ax LL + x Sin
A Σ (a ) + Eiev, xf
Verl
which, minimized over the unit sphere, gives the expression of Pmnnn It is immediate that Mmin 2 0. We prove that this value is strictly positive. Indeed, x Bx 0 implies that x Six 0 and therefore 0 for i E Vi,, but also that Lx = 0 and therefore that x I,, which implies that a = 0.
Let B = B/ Punax, with cigenvalues ps/ Hm///max2 i = =,,,.. I,...,n. We have for all d:
S - Mi/Umax S 1 u<1
where / Pmax
Therefore,
Neumann expansion to express B-1 1 follows:
B-1 B-1 - By Y(A) (
BB" n-1 Mmax S, Yohs
(14)
7=0
r=0
We denote by T, the r-th term in Y(A::
T, (I B)" M'ma S.n Yous
(15)

---

Published in Transactions on Machine Learning Research (06/2024)
Note that since ||Sm Yobell Σ v Yobslloo
we have:
Yoo
T S
(16)
Pmax V
Moreover, since B has the same zero-pattern than A (except on the diagonal), if u is more than r hops from Ver, we get (T,) = 0.
where y/oc ||oobsll and 1 μ. Similarly, ||Y(A))
S
Mmin [
4.2 Gradient of (Tr)u
In the second step, we derive the formula of the gradient of (T,), w.r.t. A, and derive a bound on its magnitude function of r, the distance to Vir, and &s the distance to Vout- For >> 0, the gradient of the u-th coefficient in T, w.r.t. I B is:
V V-
((I -B)--)
x ((I - (I-B)) - M S,n Y Yobs))
by the product rule of differentiation, and we have
V (T,)(Ta)u Σ ((I--B)-)) (Th-1)T
Using that B I
L(S, in
AL), we have
Mmax
A
V (T
V (Tr)
Mmax
(11 (1I-B) (Th-1)
(17)
Pmax
Finally, by deriving L w.r.l. Aiy
a(Tr)u
X
Σ (II-B) (Th-1);
(18)
0Aij
E Mmax
+ + - -(I-B)r- (T (Th-1)s
(II-B)- B)r-))
us (Th-1)
-(I - -II-B)- B)r-~) (Th-1))
which allows us to prove the following.
Lemma 4.3. Let i, such that: i,j are at least k-hop from u, and at least g-hop from Vin. Then:
O(T,),.
t kr
(19)
AA,;
(r q k)v--1 otherwise.
Eluaane (Vrl
Proof. Recall that (T.) 0 if is more than r-hop from Vey. Similarly, (aI B)- 0 if and i are more than r-hop from each other. Hence, the term ((I - h)r (Tn-1); appearing in Eq. (18) equals 0 if r r-h l or h < q, and bounded by (Pmax V -brr) yoo otherwise. In similar way for the other terms in Eq. 18 we get that the sum runs over the indices that satisfy q < r- which is either
none if q + k r, or q k terms otherwise, which concludes the proof.
10

---

Published in Transactions on Machine Learning Research (06/2024)
4.3 Proof of Theorem 4.2
We finally examine the hypergradient, and prove an exponential damping rale of its magnilude with the cumulated distance to Ver and Vour-
Definition 4.1 (Node cumulated distance to two subsets of nodes). The cumulated distance of node to two subsets of nodes Ver, Vout equals g + k, where q, k are the distances of to Ver, Vouts respectively.
Definition 4.2 (Edge cumulated distance to two subsets of nodes). The cumulated distance of an edge (i,j) to two subsets of nodes Ver, Vout equals the minimum between the cumulated distance of and the cumulated distance of j to the subsets Vor, Vout-
- Il where Sout is the diagonal selection matrix whose diagonal entries equal 1 if the corresponding node is in Vout and 0 otherwise, we have:
Considering Fou Sut (Y (A)-Yooao
0F
(A), )T S out (Y Yobs)
2(
0A.)
0A
ÖT aAir
Soul (Y((YY()) - -ooss
Using a triangular inequality, the bound on |X and that || Youell S V Vout Uoo we get:
+ pmin / / Vouc!
S (Y Yobe) S
yoo
Mmin
By incorporating the resulting inequality in bounding the hypergradient, and by noticing that Sout S we have:
Fost 0Aij
1 + Mmin / /er Vout
OT,
y0o
I Sot
Pmin [vrl
& AAij
==0
1 + Pmii Vtr
Vout!
Σ
((TT)) 0A..
2
Y000
Pmin
(vel
T=U
AuE Vout
Using Lemin
4.3 and the hypotheses on and j, for u in Vouts the term
a(T.) aA,
is 0f < g 1, and
bounded by
El Vivi (r - y k:)u-1 otherwise. Hence:
Dag
0F iAi
Voutl + Mmin v Ver Vout
22
Amin Ver E|
(r q k)v--1. r=g+b41
Then we see that for v < 1 we have
2 D8th E r
Σ
(r- (r-q (r-q-k)u'* (
r=
and Σ 0 rv--1
n which concludes the proof.
[1-
5 Alleviating hypergradient scarcity
In this section, we review strategics mitigate hypergradient scarcity. However, it is important that we make distinction between resolving this issue and resolving the overfitting problem. Indeed, if gradient
11

---

Published in Transactions on Machine Learning Research (06/2024)
scarcity is also caused by the limited quantity of available labeled data, it is important to avoid confusion with traditional overfitting. In particular, while traditional overfitting is generally reduced by adding more training data, gradient scarcity is still observed when optimizing edges for from labeled nodes regardless of the dataset size and the number of labels. We study several strategies to mitigate hypergradient scarcity in the bilevel setting, but we emphasize that they might not lead to better generalization error altogether.
Generalized edge refinement by optimizing A As hypergradient scarcity observed on edges connecting nodes distant from the labeled ones, natural fix is to reduce this distance. One way to do that is by refining edges in a power of Aobe, as the matrix Albs includes r-edge long connections between nodes, In our experiments, we adopt A abs as this notably expands the graph but does not achieve the extreme case where the result is a complete graph.
Graph regularization. Graph regularization is used to impose a prior structure on the learned graph, by adding a regularization term to Four to penalize graphs with undesirable properties. For instance, Kalofolias (2016) propose the regularization term -71, log A1,, for some y to penalize low-degree nodes. We use this choice in the experiments, but note that imposing task-related priors and regularization terms could lead to better performance. This will be the topic of future work.
G2G for edge refinement. The third fix we suggest is latent graph learning using G2G models. In the outer problem, we propose to replace optimizing edge weights by optimizing the parameters of a G2G model to predict similarity between nodes. Let 0 be the weights of this model, and Ag be its output graph, the G2G model we adopt (Ae)ss = a((x; - xx))?, where the square function is applied entrywise, a : RR + is Multi-Layer Perceptron (MLP) model consisting of ko2G layers, each is of the form:
x = (x + (b
where will E Rdh-ixd blll E Rd are learnable parameters, and di is the output dimensionality of the l-th layer. The parameters are gathered as (W|"l b kore
6 Experiments
Wg use the real-world citation networks Cora LL & Getoor 2003), CiteSecr (Bhattacharya & Gctoor 2007,, and PubMed (Namata et al. 2012), and two other synthetic datasets to validate our findings. The first synthetic datasct, called synthetic dataset 1, is designed for the Laplacian regularization scenario. The second one is binary classification dataset that can be used for the three considered graph-based models. Due to the paradigm behind construction, we call it the cheaters dataset.
Synthetic datasct 1: the purpose of this dataset is to validate our findings regression problems, particularly with the Laplacian regularization 2 in the inner problem. We sample i.i.d. latent variables X E R=*x as the node features uniformly at random from [0, 1] with n = 1536, p = 2. The ground-truth graph A is constructed s.t. (A*) = if || - X, < a, and 0 otherwise. a is set to 0.06 s.t. the number of edges approximates n log n. Two distinct procedures were employed to sample the nodes that comprise Vir, leading two distinct realizations of the dataset as illustrated in Fig. [top). The first procedure randomly samples 100 nodes from the set V, hence V,, is well-spread, whereas the second procedure selects the 100 nodes with the smallest Euclidean distance to the point (0.5, 0.5), thus V,, is concentrated in a small neighborhood in this case. In both cases, we randomly sample 25 nodes from V to construct Vout- The remaining nodes are equally divided between the validation and the test sets. Then, each node i in Ver is labeled as follows:
1X -1X 2(b:2)
-1X
(You)); = <(e
e 2(0:2)
+
200.2
where 01 a2 ag are randomly sampled from [0, 1J2, and Ç is a scaling factor such that labels lie in [0, 1]. By this construction, the prior that the labeling function on the graph smooth is met, and the Laplacian regularization can be applied as in Eq. [
'Qur Python implementation available http:///ggtta...//aaaaaaaaaaaaea
acaarittyyrrap__eeriinn learning
12

---

Published in Transactions on Machine Learning Research (06/2024)
We use the Laplacian regularization model to generate labels for other nodes. That is, we plug the labels of Vir and A in Eq. ( with À and the solution holds the sought-for labels. This way, the ground-truth graph actually plays a role in labeling nodes in Vou and in the validation set.
The noisy observed graph is built upon random weights
(Aobslis = Ei.j (Ar)())) where E.p ~ ((0,
Experiments on this dataset are done with the Laplacian regularization in the inner problem as in Eq.
Hmin =9.99 *V2
Hmin =0.78 *V2
1e-5
1e-5
Magnitude of hypergradient
8
Magnitude of hypergradient
3
6
2-
4
1
2.
10 LD
0.0
2.5
5.0
7.5
10.0
5
10
15
Cumulated distance to Vrr and Vout
Cumulated distance to Vir and Vout
Figure 1: Hypergradient scarcity observed when solving the edge refinement task with the bilevel optimization framework. We run the experiments on the synthetic dataset 1, while adopting the Laplacian regularization in the inner problem. Top: illustration of the graph. The training nodes V,, are circled in red, the colors correspond the distance Ver. The eigenvalue Pmin is given as ratio of the smallest positive eigenvalue of with respect to the sum of distances to Ver and Vout- Left: the training set Ver is well-spread thereby aligned with the high-frequency eigenvectors of the graph, resulting
L. Vout is randomly sampled from V but not shown here. Bottom: Hypergradient magnitude @F
high Pmin- The decrease of the hypergradients is sharp with the distance. Right: V,, is aligned with the low-frequency eigenvectors of the graph, resulting in low pmin- The decrease of hypergradients magnitude not as sharp the previous case.
The cheaters dataset: the purpose of this dataset is to validate our findings classification problems, particularly with the shallow GNN g in the inner problem, and to validate the efficiency of the proposed stralegies to alleviate hyperraddient scarcity. Nodes in this graph represent sludents in an exam classroom. Setting n = 256, p = 10, the i. features X 256x are sampled uniformly at random from [o, 1]. For node i, X, represents the position of the according student the classroom. For visualization purposes, we enumerate nodes following the ascending order of X.u. The remaining features of a student represent questions. However, students tend to cheat
the grades s/he is capable of scoring in the corresponding
13

---

Published in Transactions on Machine Learning Research (06/2024)
x10
10-2
10
50-
8
50-
10
10-5
100
6 100-
10
-0
4 150-
-10-6
100
200
2 200
- 10 4
- 10-3
250
250
10-2
100
200
0
100
200
Figure 2: Hypergradient scarcity observed when solving the edge refinement task with the bilevel optimization Tramework. We run the experiment on the cheaters dataset, and use a 2-layer GNN as a classifier following the model Left: graph initialization. Right: hypergradient an arbitrary outer iteration, namely 9, It is clear that the hypergradient on edges between unlabeled nodes far from the ones in Vout U Ver equals zero. Recall that Vr {0, ...
1,,.,,...3............ 32) U (224..... 255) and Vous (96..... 160).
with their neighbors in the graph. The ground-truth graph A is constructed as follows:
(A' ).j = exp [-||x i.o X,,018/20
The observed graph Aobs is drawn from a random model as
(Aobs ~ Ber ((A"),)
We set a = 0.027 s.t. the number of edges in Aobs approximates n nlog Students cheat such that their grades Ygrade after the exam are
Ggrade = A' A'X,,
A student passes the exam if his grade greater than a threshold T, i.e., (Yobs): if (Y (rrede)) ) > 7 and 0 otherwise. We put t 60 that approximately half of the students pass the exam. Ver includes nodes in (188...,//8J ... n1, i.e., near the two ends of the 1-dimensional class. Vout (3n/8,.... .inn/,....,,./88 5n/8), i.e., centered around the middle of the class. Remaining nodes are equally divided into a validation and a
test set. Experiments on this dataset are done with a 2-layer GNN classifier following the model 4
Real-world dataset: we validate our findings on the Cora (Lu Getoor 2003 CiteSeer (Bhattacharya & Getoor 2007), and PubMed (Namata al. 2012) datasets. These are citation datasets, where nodes represent research publications described by bag of words, and edges stand for citations. The task is to classify articles w.r.t. their topic. From the default vrain/valdaation/ ttattit split in Yang al. (2016); Kipf & Welling 2017), use the training set as the inner training set Ver, while we use half of the validation set as the outer training set Vout- The other half is kept as validation set as in Franceschi et al. 2001
Models: G2G and GNN models are implemented using Porcrch (Paszke & al. 2019) and PyTorch Geo- metric Feey & Lenssen 2019), respectively. The function in the G2G model an MT. with hidden layers of 16 ncurons for the cheaters dataset, and 1 hidden layer 32 neurons for the citation datasets. The GNN model following Eq. (4) has 1 hidden layer of 8 neurons for the cheaters dataset and 16 neurons for the citation datasets. To compute the node embeddings for the APPNP model, we use MLP with hidden layer. The hidden and the output layers contain 16 neurons. For the APPNP model, the number of power iterations is set to 20 and the teleport probability is set to 0.1. All hidden layers are followed by the ELU activation function (Clevert et al. 2015) The G2G output layer is followed by the sigmoid function. The output layer of GNN models is followed by the softmax function.
Setup: we use Adam (Kingma & Ba 2014] as the inner and the outer optimizer with the default parameters of Porcor,, except for the inner learning rate 7in and the outer one Nout, which are tuned from the set
14

---

Published in Transactions on Machine Learning Research (06/2024)
1.0
The mamber of refixed edges
Onter trining arearay
0.8
0.85
Test socmmryy
0.7
0.6
10*
DC+Ros
D0++Gm
BO
0.6-
0.4
BO:Rig
W Maput
BO+G
0.5-
BO+G23
0.2
BO+G2G
A.
100
150
50
100
150
0
50
100
150
Outer itentionn
Outer itenation
Outer ileration
(a)
(b)
(c)
Figure 3: Efficiincy of the proposed solutions to hypergradient scarcity w.r.t. the number of refined edges and the generalization capacity. An edge is considered well refined if its learned magnitude is larger than one percent of the maximum learned edge weight. The solutions are graph regularization with -1 log A1 RBg,, generalized edge refinement by refining edges in A (BO+Gen), and latent graph learning using G2G model (BO+G2G). (a): training accuracy on Vout- (b): mumber of refined edges. (c) test accuracy.
110-4,10 ...., 10.,00....000 The best values were 7inn Jost = 10-2 for the citation datasets. For the cheaters dataset, nout = 10 3 adopting a G2G model, while Yout = 10-2 in other cases, and Minn = 10-2. For the synthetic dataset 1, nout = 10-1 and yin = 10. We set Tin with a grid search. For the citation datasets, Tin- 500 adopting the Laplacian regularization, and Tin 100 otherwise. For the cheaters dataset, Ton = 200. For the synthetic dataset 1, Tin 500. The learnable parameters of the inner model are initialized at random after each outer iteration. We adopt the default initialization of PyTorch and PyTrrch Geometric for the parameters of the GNN models. In the Laplacian regularization scenario, the labels are initialized uniformly at random from [0, 1]. Except for the cheaters dataset, we initialize edge weights uniformly at random from [0, 1] when solving an edge refinement lask, and adopt the default initialization of Py for the G2G model when it is used. For the cheaters dataset, we initialize edge weights uniformly at random from 10-5, * [0. 1] in edge refinement tasks, and multiply the default initialization of the last layer of the G2G model by 10-5 s.t. its output edges at the first iteration of small magnitude. We adopt this strategy for this dataset to measure the level of hypergradient scarcity, which we do by counting the number of learned edges whose magnitude is greater than chosen threshold. We set the number of outer iterations Tout to 150 for synthetic datasets and to 300 for citation datasets. We select the graph (or the G2G parameters) with the highest. validation accuracy. We set À = 1 in training when considering the Laplacian regularization, as we expect the bilevel framework to learn this parameter by scaling the learned adjacency matrix. When applying the Laplacian regularization fod with Anbs on the citation datasets, we y in the graph regularization term is to following grid search on the set {10 1002- 2.... 10).
after a grid search,
6.1 Hypergradient scarcity with the GNN model in Eq.
In this experiment, we consider 2-layer GNN classifier following the model in the bilevel framework. We solve the edge refinement task on the cheaters dataset, where E in Eqs. i and ( is the CCE function. Fig. [efft) depicts the initialization of the adjacency matrix. It also shows what edges are to be optimized, that is, edges whose initialization is nonzero. In Fig. righht) we show the hypergradient at the outer itcration 9, which is arbitrarily chosen. It is clear that edges between unlabeled nodes far from the ones in the union Vout Ver get no supervision during the training process. Recall that Vnr = 1..., 32} U (224..... 255} and Vout = (96.... ... 160}. This aligns with our findings, which state that edges between nodes at Icast 2-hop from nodes in Vone U Ver receive zero hypergradients. This, as seen in Fig. g leads to learned graph that overfits training nodes and even generalizes worse than A
15

---

Published in Transactions on Machine Learning Research (06/2024)
Table 1: Accuracies obtained on citation networks with the Bilevel Optimization framework (BO); the same framework optimizing G2G model (BO+G2G), and the same framework equipped with graph regularization (BO+Reg). We also benchmark against GAM (the result is reported from the according paper) and against Aubs Each experiment is repeated 5 times and the average accuracies are reported. For each dataset, the first line (in black) corresponds to the test accuracy, whereas the second line (in gray) corresponds to the training accuracy on Vout. The highest and second-highest test accuracies for each dataset are bolded. The training accuracy on Vr is higher than 96% in all experiments.
Auöa Lap
BO
BO+G2G
BO+Reg Lap
GNN
APPNP
GNN
Lap
APPNP
GNN
Lap
APPNP
GNN
APPNP
GAM
Cora
73.62
72.40
80.88
79.07
73.80
79.90
80.32
75.76
79.96
80.76
76.45
82.10
84.8
77.50
74.03
77.78
90.17
81.70
83.73
94.58
83.64
77.66
97.30
84.68
87.80
CiteSeer
62.48
54.00
70.08
68.10
53.00
71.01
70,80
54.72
71.82
70.60
55.10
71.50
72.20
75.94
57.74
72.76
81.44
74.09
61.96
70.42
PubMed
77.42
70.50
79.14
77.68
72.80
79.32
79.00
72.18
79.22
78.40
75.75
80.20
81.00
79.58
74.71
80.36
93.47
80.00
85.38
90.27
71.37
94.64
87.59
83.39
85.38
6.2 Hypergradient scarcity with the Laplacian regularization model
We here examine hypergradient scarcity when adopting the Laplacian regularization in the inner problem. We run the bilevel optimizer to solve the edge refinement task on the synthetic dataset 1. The dataset corresponds to a regression problem, so & in Eqg. [1 and (6) the MSE loss function.
In Fig. [bottoom, we plot the absolute value of hypergradients at the outer iteration 6 as function of the edge cumulated distance to Vi and Vout- One observes the hypergradient scarcity phenomenon, since hypergradients decay exponentially as the edge distance increases. This validates our analysis articulated in Theorem 4.2 In addition, we observed in practice that μ is nevertheless quite small, and that our bound in
4.2 is quite loose. Another observation is that the decrease rate is higher when Vtr is well-spread in the graph. Deriving a tighter bound on the magnitude of hypergradients and investigating the link between the distribution of labeled nodes and this bound will be the subject of future work.
Theorem
6.3 Testing solutions to mitigate hypergradient scarcity
We run our experiments on the cheaters dalaset using the 2-layer GNN 4
classifier. In each experiment, we run the bilevel optimization framework with one of the suggested fixes. We consider two criteria to measure the efficiency of cach solution, the first one is counting the number of refined edges. At any outer iteration, we say that an edge is refined if its learned weight is greater than one percent of the maximum learned edge weight at the same iteration. Recall that we initialize the graph/G2G with small parameters (Ns 10-5). The second criterion is the test accuracy, The first criterion assesses the ability alleviate hypergradient scarcity, while the second assesses the generalization to nodes unseen during training, and thus if the learned graph is meaningful.
Fig. 3 shows that all three fixes produce better results w.r.t. the first criterion, as the number of refined edges is larger at almost every iteration, with optimizing edges in A being the most efficient, and the G2G model and graph regularization having a similar performance. Moreover, one notices that this number decrcases with the iteration index when refining edges in Agts or A which expected as only a small portion of edges receive supervision; however this portion is larger when refining A
Regarding the second criterion, the G2G model and the graph regularization generalize well, as both combat hypergradient scarcity without increasing (or even by decrcasing) the number of parameters to learn. On the other hand, optimizing edges in A deteriorates performance in the test phase. A likely explanation is that by expanding the graph, we increase the number of parameters to learn, which means a more complex model that is more likely to overfit training nodes. This experiment illustrates that hypergradient scarcity is not the traditional overfitting related to data/label scarcity, and resolving it does not necessarily promote better generalization.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Cora
CiteSeer
PubMed
Hypergradient (GNN case)
10-3
10-3
10
10
10
10 6
0
3893689509
0
0
3
-10
10
-10
10-3
-10-3 3
-10-3
0
10
10
5
ED Vn, U Vint
ED to Va. U Vost
ED Via Von
Cora
CiteSeer
PubMed
10-3
10-3
Hypergradient (Laplacian case)
10-6
10
10
10
10
-10-3
10
50
100
250
500
10
FCD to Vin, Vouc
FCD to Va, Vout
FCD to Vnn Vout
Cora
CiteSoer
PubMed
10a
10"
Hypergradient (APPNP casc)
10
200
10
10 3
10
mine
10 6
10-6
0
-10
10
-10
Dr-
000
10
10-3
-100
100
10
ED to Vn, Vout
ED to Via U Vost
ED to Vin U Vout
Figure Hypergradient scarcity observed with citation networks when solving the edge refinement task under the bilevel optimization setting. Top: we depict the hypergradient as function of the Edge Distance (ED) to Vn U Vout when adopting the 2-layer GNN in Eq. (4h as the graph-based model. Middle: we depict the hypergradient adopting the Laplacian regularization model. Since our analysis in this sccnario necessitates the graph to be connected, we make the graph connected by iterating over its components, and connecting an arbitrary node in the current component to an arbitrary node in the next one. The number of added edges is 77 for Cora, 437 for CiteSeer, and 0 for PubMed. This is done only in the experiment dedicated for this figure. In the other experiments, the given graph considerod. Bottom: we depict the hypergradient a function of the Edge Distance (ED) to Vn, Voat when adopting the APPNP model. In all cases, we plot the hypergradient at the outer iteration 9.
function of the Edge Cumulated Distance (ECD) to the sets Vnn, Vout when
17

---

Published in Transactions on Machine Learning Research (06/2024)
6.4 Results real-world citation datasets
We use the bilevel optimization G for edge refinement on Cora, CiteSeer, and PubMed. The downstream task is a multi-label classification problem hence E is the CCE function. Fig. $ depicts the hypergradient on edges at outer iteration 9 as function of their distance to labeled nodes. For the Laplacian regularization case, that is the edge cumulated distance to Vtr and Vout- In the case of the GNN model in Eq. ( the edge distance is obtained by computing the distance of its endpoints to UUott then taking the minimum. For APPNP, we do not have any theorem that defines what distance metric to use to observe hypergradient scarcity. We thus use the same metric as in the previous GNN case. In accordance with our analysis, the figure displays a null hypergradient for distances greater than when using the GNN model in Eq. (4) while the Laplacian regularization scenario exhibits a hypergradient that diminishes exponentially with edge distance. Interestingly, APPNP exhibits a similar behavior the Laplacian regularization model, where the hypergradient is damped exponentially with the edge distance to Vir and Vout- This means that although to lesser degree than shallow GNNs, GNNs of infinite receptive field such as APPNP suffer from hypergradient scarcity, which is a new finding to the best of our knowledge.
Regarding the genoralization capacity evaluated using the test accuracy, Table shows that the bilevel framework (BO) outperforms Aohs when using the GNN model in Eq. (4), while it performs more or less the same when using the Laplacian regularization and APPNP models. This might be surprising as one would expect the bilevel framework to produce a more corrupted graph than Aobs due to hypergradient scarcity, and thus would lead to worse generalization, which is observed with the cheaters dataset in Fig, One possible justification for this is that node features are informative enough in these datasets to compensate for the corrupted graph. Another justification, especially in the case of the Laplacian regularization and APPNP, is the small diameter of the graph in these datasots, which limits the number of affected edges. For example, the percentage of edges with edge distance al most 2 is 77%, 63%, 35% for Cora, CiteSeer, and PubMed, respectively. For edge distance at most 3, the percentages are 95%, 80..86% This means that a great portion of edges are not affected by hypergradient scarcity. Hence, it normal that the learned graph perform similarly or better than the observed one. Conducting experiments on other datasets where the graph is of higher importance and of larger diameter is left for future work.
Next, we test the efficiency of the proposed solutions to hypergradient scarcity w.r.t. test accuracy, namely graph regularization and latent graph learning with G2G models. We do not consider learning a power of Aoba as the memory requirement goes beyond the limits we have access to. Table [ shows that both fixes yield signíficant improvements over Aots More importantly, both fixes consistently improve over the bilevel framework, notably the graph regularization fix. Since the impact of hypergradient scarcily is not severe in these datasets, we cannot claim that the improvement is due to alleviating hypergradient scarcity. However, we can claim that the fixes do not deteriorate the generalization capacity, and that they are more robust to overfitting than the bilevel framework. Designing a metric to measure the severity of hypergradient scarcity and the impact of the fixes on it is left for future work. We point out that the bilevel optimization framework with either fix does not achieve state-of-the-art results produced by GAM.
Finally, we notice that GNN models lead to significantly superior results in all scenarios. This is expected, the Laplaciann regularization promotes similarity between connected nodes but, unlike GNNs, is not supervised-basee method.
7 Conclusion
We studied hypergradient scarcity when deploying bilevel optimization in edge refinement tasks under the semi-supervised learning setting. This phenomenon consists in edges far from labeled nodes receiving zero hypergradicnts when optimizing the graph and the graph-based model to improve the labeling performance. We proved that this problem occurs for shallow GNN models. Replacing GNNs by the Laplacian regulariza- tion model does not resolve the issue; however, the phenomenon is less severe. We bounded the magnitude of hypergradients and proved that they are exponentially damped with distance to labeled nodes. To alle- viate hypergradient scarcity, we examined graph regularization, latent graph learning, and refining edges in a power of the observed adjacency matrix. Our experiments validated our findings, privileged the first two
18

---

Published in Transactions on Machine Learning Research (06/2024)
solutions over the latter, and showed that GNNs of infinite receptive field (e.g., APPNP) can suffer from hypergradient scarcity. Moreover, we showed that alleviating hypergradient scarcity does not necessarily alleviate overfitting.
Acknowledgments
The authors acknowledge the support of ANR Grava ANR-18-CCE40-0005 and ANR GRandMa ANR-21- CE23-0006.
References
Kristin P Bennett, Jing Hu, Xiaoyun Ji, Gautam Kunapuli, and Jong-Shi Pang. Model selection via bilevel optimization. In IJCNN, 2006.
Indrajit Bhattacharya and Lise Getoor. Collective entity resolution in relational data. ACM Trans. Knowl. Discov. Data, 1(1), 2007.
Aleksandar Bojehevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózem- berezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Dola Mining, pp. 2464 2473, 2020.
Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.0798) 2015.
Benoit Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Ann. Oper. Res., (:3(1) 2222255666.111 2007.
Samuel Daitch, Jonathan A Kelner, and Daniel A Spielman. Fitting graph to vector data. In Proceedings of the 26th annual international conference on machine learning, pp. 201-208, 2009.
Bahare Fatemi, Layla El Asri, and Scyed Mchran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. NewrIPS, 2021.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorrh Geometric. In ICLR Workshop on Represenlation Learning on Graphs and Munifolds, 2019.
Rémi Flamary, Alain Rakotomamonjy, and Gilles Gasso. Learning constrained task similarities in graph regularized multi-task learning. In Regularization, Optimization, Kernels, and Support Vector Machines, volume 103. Chapman and Hal//CRC, 2014.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel program- ming for hyperparameter optimization and meta-lcarning. ICML, 2018.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao Hc. Learning discrete structures for graph neural networks. In ICML, pp. 1972 1982, 2019.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 1.X.v:1810005999 2018.
Edward Grefenstette, Brandon Amos, Denis Yarats, Phu Mon Hiut, Artem Molchanov, Franziska Meier, Douwe Kiela, Kyunghyun Cho, and Soumith Chintala. Generalized inner loop meta-learning. arXiv preprint xrXio:1910.0 01 727, 2019.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th international conference on international conference on machine learning, pp. 399 406, 2010.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. kernel method for the two-sample-problem. Advances in newral information processing systems, 19, 2006.
19

---

Published in Transactions on Machine Learning Research (06/2024)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognilion, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings deep residual networks. Tn Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV 14, pp. 630 645. Springer, 2016b.
Chenhui Hu, Lin Cheng, Jorge Sepulcre, Georges El Fakhri, Yue M Lu, and Quanzheng Li. A graph theoretical regression model for brain connectivity learning of alzheimer's disease. In 2013 IEEE 10th International Symposium on Biomedical Imaging, pp. 616-619. IEEE, 2013.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph repre- sentation learning. Advances in neural information processing systems, 31, 2018.
Vassilis Kalofolias. How to learn a graph from smooth signals. In Artificial Intelligence and Statistics, pp. 920-929. PMLR, 2016.
Vassilis Kalofolias and Nathanaël Perraudin. Large scale graph learning from smooth signals. arXiv preprint arXiv:1710.055: 05654, 2017.
Ashish Kapoor, Hyungil Ahm, Yuan Qi, and Rosalind Picard. Hyperparameter and kernel learning for graph based semi-supervised classification. Advonces in neural information processing systems, 18, 2005.
Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. In NewrIPS, 2022.
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self- supervision. In ICLR, 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. arXiv preprinl crXiv:1611.07300 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICI.R, 2017.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep enns?
In Proceedings of the IEEE/CVE international conference computer vision, pp. 9267-92677777 2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding-design provably more pow-
erful guns for structural representation learning. arXiv preprint (.Xix:2009.00140 pp. 61, 2020.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge management, pp. 556 559, 2003.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 338-348, 2020.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, 31, 2018.
Weiyi Liu, Pin-Yu Chen, Fucai Yu, Toyotaro Suzumura, and Guangmin Hu. Learning graph topological features via gan. IEEE Access, 7:21834 21843, 2019.
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. Tn WWW, 2022.
20

---

Published in Transactions on Machine Learning Research (06/2024)
Qing Lu and Lise Getoor. Link-based classification. In ICML, 2003.
Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches to attention-based neural machine translation. In EMNLP, 2015.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp. 1, 2012.
Lawrence Page. The pagerank citation ranking: Bringing order to the web. technical report. Stanford Digital Library Technologies Project, 1998, 1998.
Jiahao Pang and Gene Cheung. Graph laplacian regularization for image denoising: Analysis in the contin- uous domain. IEEE Transactions on Image Processing, 26(4):1770 1785, 2017.
Adam Paszke and al. Pytorch: An imperative style, high-performance deep learning library. In NearIPS. 2019.
Lishan Qiao, Limei Zhang, Songean Chen, and Dinggang Shen. Data-driven graph construction and graph learning: A review. Neurocomputing, 312:336 351, 2018
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti.
Sign: Scalable inception graph neural networks. arXio preprint arXiv:2004.11198, 7:15, 2020.
Sam T Roweis and Lawrence K Saul. Nonlincar dimensionality reduction by locally lincar embodding. Science, 290(5500):2323 2326, 2000.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Gated graph recurrent neural networks. IEEE Trans- actions on Signal Processing, 68:6303 6318, 2020.
Lawrence Saul and Sam T Roweis. Think globally, locally: unsupervised learning of low dimensional manifolds. Journal of machine learning research, 4(Jun):119 155, 2003.
Dejan Slepcev and Matthew Thorpe. Analysis of p-laplacian regularization in semisupervised learning. SIAM Journal on Mathematical Analysis, 51)3)20885 2120, 2019.
Gilbert W Stewart. Matriz algorithms: volume 1: basic decompositions. SIAM, 1998.
Otilia Stretcu, Krishnamurthy Viswanathan, Dana Movshovitz-Attias, Emmanouil Platanios, Sujith Ravi, and Andrew Tomkins. Graph agreement. models for semi-supervised learning. NewrIPS, 2019.
Joshua B Tenenbaum, Vin de Silva, and John Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(550)) 2323, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NewrIPS, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph Attention Networks. ICLR, 2018.
Guihong Wan and Harsha Kokel. Graph sparsification via meta-learning. DLG@ AAAI, 2021.
Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. In ICML, 2006.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propagation. arXiv preprint ar 06:::200200675: 2020.
21

---

Published in Transactions on Machine Learning Research (06/2024)
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 0861-6877 PMT.R, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference machine learning, pp. 5453 5462. PMLR, 2018.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedinggs of the 33rd International Conference on Internalional Conference Machine Learning Volume 48, ICML'16, pp. 40-48, JMLR.org, 2016.
Chun- Yang Zhang, Zhi-Liang Yao, Hong- Yu Yao, Feng Huang, and CL Philip Chen. Dynamic representation learning via recurrent graph neural networks. IEEE Transactions on Systems, Man, and Cybernetios: Systems, 53)2))1284 1297, 2022.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International conference on learning representations, 2020.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, 1215-1226, 2021.
Xiaojin Zhu, Semi-supervised learning with graphs. Carnegie Mellon University, 2005.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912 919, 2003.
22


Reviews:
[{"review_id": "gh3yCIogtp", "reviewer": "Reviewer_2MfE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- Clarity: the paper is presented in a clear way and the material is motivated well\n- Experiments: The experiments presented are rather comprehensive and they match well in terms of evaluating and supporting the claims made in the theoretical part of the paper\n- Theory: the theoretical portion of the paper is 1. presented clearly 2. to the best of my knowledge, correct 3. sufficiently deep and relevant. \n\nTo the best of my knowledge, the results presented are sound, and the topic is of relevance to the audience of TMLR. \n\n- There are no real obvious weakness in the paper...all the bases are covered pretty well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors demonstrate the phenomenon of gradient scarcity in the bilevel optimization setting where separate loss functions are used for each of the graphs and the model. They show that gradient scarcity occurs not just because of finite receptive fields, but also in Laplacian regularization. They investigate several solutions and produce empirical results to validate their theoretical analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main potential small issue is that the authors choose to study a specific problem in a very specific setting. If would be great if the authors could add a paragraph or two expanding on and giving context to the importance of the bilevel-optimization setting in comparison to other settings. \n\nI have no other requested changes. I recommend acceptance.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L00oNFPyfp", "reviewer": "Reviewer_TBy1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper provides comprehensive background information and clear illustrations, enabling readers unfamiliar with gradient scarcity in graph learning to quickly grasp the concepts discussed.\n2. The paper's approach is both natural and principled, supported by extensive theoretical analysis.\n3. The results pertaining to the Approximate Personalized Propagation of Neural Predictions (APPNP) appear promising.\n\nWeaknesses:\nThe paper is fundamentally solid, yet I recommend some revisions to enhance its structure and clarity.\n\n1. The introduction is formally correct in defining the tasks, but incorporating natural language and visual aids could make the paper more engaging.\n2. The section on related work contains excessive content on GNNs and graph learning, much of which is general and appears redundant, particularly in contrast to the short introduction of bilevel optimization.\n3. In the tables, employing color coding or bold text could help emphasize key results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates the issue of gradient scarcity in graph learning under semi-supervised conditions, where edges between distant unlabeled nodes receive zero gradients. This phenomenon, initially identified in shallow Graph Neural Networks (GNNs) using a single loss function, is mathematically characterized and shown to also occur in bilevel optimization. Despite infinite receptive fields in models like those using Laplacian regularization, gradient scarcity persists due to exponential decreases in gradient amplitude with distance from labeled nodes. Various solutions are explored, including latent graph learning and graph regularization. Empirical results validate these findings and indicate that gradient scarcity also affects models like Approximate Personalized Propagation of Neural Predictions (APPNP), suggesting its prevalence across different graph learning models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the Weanknesses part.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "o5m6wyTWSM", "reviewer": "Reviewer_pERT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I find this work ambitious and with many very interesting contributions. Firstly, the addressed problem is quite challenging, and the authors provide a clear response to it. The theorems are understandable (though not necessarily straightforward; they require significant formalization effort, blending bilevel optimization and graph theory). Additionally, I find the experiments convincing; they pinpoint a problem, which is the gradient scarsity even for models with larger receptive fields. Moreover, the authors have made an effort to make the article well-written. The related work section is also very comprehensive, which is pleasing.\n\nFor all these reasons, I am convinced that this work is of interest to the TMLR community and the broader ML community.\n\nHowever, I have some remarks/suggestions on certain points that seem unclear to me and which, I think, should be further detailed (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This article focuses on gradient scarsity (specifically, the phenomenon where edges between two nodes cannot be learned if these two nodes are too far from the nodes in the training set because they receive zero gradient) and proposes several contributions. Firstly, it explains that this problem is linked to the fact that Graph Neural Networks (GNNs) have a finite receptive field. Secondly, it theoretically demonstrates the problem of gradient sparsity for two graph structure learning models: joint optimization and bilevel optimization. In the latter case, the contribution is twofold: first, when the inner problem involves predicting labels using a GNN, and second, when the inner problem involves predicting labels through propagation with Laplacian regularization. In this latter case, the authors show that the gradient is not zero but decreases exponentially fast. Furthermore, it empirically demonstrates that this problem also occurs for models with larger receptive fields.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Suggestions for Section 1.2:\n\nWhen defining the bilevel problem, I believe it would be helpful to add some comments indicating that the problem resolution is impossible, and that in practice, a fixed number of gradient descent iterations is used for the inner problem. This would better justify the use of gradient descent (eq (7)) for Theorem 3.2 later on. I find eq (7) a bit out of context if one is not too familiar with bilevel problem resolution. This discussion comes too late in the \"Bilevel optimization\" paragraph of the experiment section.\n\n- Confusion between weights and GNN weights:\n\nI suggest referring to the weights of the GNN as \"parameters\" in the paper to distinguish them from the weights of the graph. There are a few places where this could lead to confusion or at least require some mental gymnastics that could be avoided (especially \"In this first result, we will assume that the weights $W$ do not depend on A, which is the case in joint optimization\").\n\n- Regarding Theorem 3.1:\n\nThis theorem is very interesting. It already formally proves that the classical case exhibits gradient scarsity. However, there are three points that deserve discussion:\n\n    - The joint problem $\\min_{A,W}$ does not have any particular regularization on $A$: this does not seem very standard to me. I believe the theorem could be easily generalized to any differentiable regularization on the adjacency matrix ($A$ would still not depend on $W$).\n    - I think the fact that $A$ does not depend on $W$ deserves some explanation. Simply stating that, ideally, we minimize a certain $G(W)$ where $G(W) = \\min_A F(A, W)$ and thus $W$ does not depend on $A$.\n    - In relation to the previous point: it seems to me that this is still an idealized case; in practice, we sometimes do alternating minimization, so, if I'm not mistaken, $W$ depends on the current ‘‘$A$''. Can the authors discuss this point?\n    - I find the distinction between $k$-hop and $k$-layer a bit confusing: does the theorem really require that the nodes be at $k$-hop where $k$ is exactly the number of layers?\n\n- Regarding Theorem 3.2:\n\nIn the proof, I think it would be beneficial to explain the chain rule a bit more to pedagogically explain that \"By the chain rule, proving that [...] is sufficient to complete the proof.\"\n\n- Regarding the experiments:\n\nOverall, I find the experiments convincing. However, I think they lack discussion. I particularly think of the \"Synthetic dataset 1\" experiment: it is presented without describing its purpose or conclusion. We understand that the phenomenon of gradient scarsity is accentuated when the nodes in $V_{tr}$ are less concentrated. But in the second case, \"The decrease of hypergradients magnitude is not as sharp as the previous case\" is not discussed, for example. Why is this the case?\n\nThere are also some ambiguities in the definitions: \"the distance to $V_{tr}$\" is ambiguous (sum of the distances? average distance? minimal distance? we understand that it is the cumulative distance with the legend, but the text is a bit ambiguous). I think a formal definition would help clarify this. The same goes for the \"Edge distance to $V_{tr} \\cup V_{out}$\".\n\n- Other small remarks:\n  - In the abstract, I find the sentence \"It consists in edges between unlabeled nodes that are far from the labeled ones receiving zero gradient\" for describing the gradient scarsity not very clear. I think it should be reformulated.\n  - I think $\\theta$ should be $W$ at the end of page 3.\n  - I think $(1-u)^{q+k}$ should be $(1-\\mu)^{q+k}$ on page 8.\n  - In Figure 4: why display the gradient instead of just its norm as in Figure 1? (this unnecessarily overloads the figure).\"", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper study the problem of gradient scarcity (zero gradients) that appears when learning graphs with objective value only on a subset of the nodes. The paper show that this problem occurs also with bilevel optimization and that gradients remains small with an exponential attenuation even when using Laplacian regularization. The authors the discuss different approaches to mitigate the problem and illustrate their findings in numerical experiments.

All reviewers found the paper well written and of high quality with significant contributions with theoretical results and numerical experiments in support of those results. The few comments and requests for clarification were all answered in the reply and corresponding modifications were done in the submission. All reviewers recommended an acceptance during the discussion.

Due to the quality of the paper that brings novel understanding on the way information is propagated (or not) in graph learning the AE recommends a feature certification.
Decision: Accept (poster)