Latent Graph Inference with Limited Supervision
Authors: Jianglin Lu
Yi Xu
Huan Wang
Yue Bai
Yun Fu
Venue: NeurIPS 2023 poster (2023)
Keywords: Latent Graph Inference
CUR Matrix Decomposition
Graph Neural Networks

Abstract: Latent graph inference (LGI) aims to jointly learn the underlying graph structure and node representations from data features. However, existing LGI methods commonly suffer from the issue of supervision starvation, where massive edge weights are learned without semantic supervision and do not contribute to the training loss. Consequently, these supervision-starved weights, which determine the predictions of testing samples, cannot be semantically optimal, resulting in poor generalization. In this paper, we observe that this issue is actually caused by the graph sparsification operation, which severely destroys the important connections established between pivotal nodes and labeled ones. To address this, we propose to restore the corrupted affinities and replenish the missed supervision for better LGI. The key challenge then lies in identifying the critical nodes and recovering the corrupted affinities. We begin by defining the pivotal nodes as k-hop starved nodes, which can be identified based on a given adjacency matrix. Considering the high computational burden, we further present a more efficient alternative inspired by CUR matrix decomposition. Subsequently, we eliminate the starved nodes by reconstructing the destroyed connections. Extensive experiments on representative benchmarks demonstrate that reducing the starved nodes consistently improves the performance of state-of-the-art LGI methods, especially under extremely limited supervision (6.12% improvement on Pubmed with a labeling rate of only 0.3%).

Latent Graph Inference with Limited Supervision
Jianglin Lu Xu' Huan Wang's Yue Bai' Yun Ful
Department of Electrical and Computer Engineering, Northeastern University "Khoury College of Computer Science, Northeastern University Project Page: http://jangiinSSAgggiuubiLLLLLLL
Abstract
Latent graph inference (LGI) aims to jointly learn the underlying graph structure and node representations from data features. However, existing LGI methods com- monly suffer from the issue of supervision starvation, where massive edge weights are learned without semantic supervision and do not contribute to the training loss. Consequently, these supervision-stait starree weights, which may determine the predictions of testing samples, cannot be semantically optimal, resulting in poor generalization. In this paper, we observe that this issue is actually caused by the graph sparsification operation, which severely destroys the important connections established between pivotal nodes and labeled ones. address this, we propose restore the corrupted affinities and replemish the missed supervision for better LGI. The key challenge then lies in identifying the critical nodes and recovering the corrupted affinities. We begin by defining the pivotal nodes k-hop starved nodes, which can be identified based on a given adjacency matrix. Considering the high computational burden, further present more efficient alternative inspired by CUR matrix decomposition. Subsequently, we eliminate the starved nodes by reconstructing the destroyed connections. Extensive experiments representative benchmarks demonstrate that reducing the starved nodes consistently improves the performance of state-of-the-ard LGI methods, especially under extremely limited supervision (6. 12% improvement on Pubmed with a labeling rate of only 0.3%).
Introduction
Graph neural networks (GNNs) [8, 12, 23,33) have recently received considerable attention due to their strong ability handle complex graph-structured data. GNNs consider each data sample as node and model the affinities between nodes as the weights of edges. The edges as a whole constitute the graph structure or topology of the data. By integrating the graph topology into the training process of representation learning, GNNs have achieved remarkable performance across wide range of tasks, such as classification [19,37], clustering [31, 40), retrieval [5,43] 43], and recognition [35,44],
Although effective, existing GNNs typically require prior graph to learn node representations, which poses a major challenge when encountering incomplete or even missing graphs. This limitation has spurred the development of latent graph inference (LGI) [7, 10, 17, 22, 32], also known graph structure learning [9, 24, 39, 42]. LGI aims to jointly learn the underlying graph and discriminative node representations solely from the features of nodes in an end-to-end fashion. By adaptively learning the graph topology, LGI models are empowered with great ability to remove noise and capture more complex structure of the data 113,26,27,47] Consequently, LGI emerges promising research topic with a broad range of applications, such as point cloud segmentation [41], disease prediction [6], multi-view clustering [31], and brain connectome representation [18].
*Corresponding author: Jiangl bangglinnu@outloo.ccom
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, many LGI methods suffer from a so-called supervision starvation (SS) problem [10], where a number of edge weights are learned without any semantic supervision during the graph inference stage. Specifically, given a k-layer GNN, if a node and all of its predefined neighbors (from 1- to k-hop) are unlabeled, the edge weights between this node and its neighbors will not contribute the training loss and cannot be semantically optimal after training. This will lead to poor generalization performance since these under-trained weights are inevitably used to make predictions for testing samples. In this paper, we discover that the SS problem is actually caused by the graph sparsification operation, which severely destroys the important connections established between pivotal nodes and labeled ones. Based on this observation, propose to restore the destroyed connections and replenish the missed supervision for better LGI.
Specifically, we first define the pivotal nodes as k-hop starved nodes. Then, the SS problem can be transformed into a more manageable task of eliminating starved nodes. We propose to identify the k-hop starved nodes based on the k-th power of given adjacency matrix. After identification, we can diminish the starved nodes by incorporating a regularization adjacency matrix into the initial one. However, the above identification approach suffers from high computational complexity due to matrix multiplication. For example, given 2-layer GNN, identifying 2-hop starved nodes requires at least On")), where n denotes the number of nodes. To address this, we present more efficient alternative solution inspired by CUR matrix decomposition [2.3]. We find that with appropriate column and row selection, the U matrix obtained through CUR decomposition of the initial adjacency matrix is actually a zero matrix. Thus, we can eliminate the starved nodes by reconstructing the U matrix.
Although recovering the U matrix encourages more supervision, such strategy may cause potential issue we call weight contribution rate decay. In other words, the weight contribution rate (WCR) of non-starved nodes decays as the number of starved nodes increases, resulting in a final latent graph that heavily relies on the regularization one. To tackle this issue, we propose two simple strategies, i.e., decreasing the WCR of starved nodes and increasing the WCR of non-starved nodes (see Sec. 3.3 for details). The main contributions of this paper can be summarized as follows:
We identify that graph sparsification is the main cause of the supervision starvation (SS) problem in latent graph inference (LGI). Therefore, we propose to restore the affinities corrupted by the sparsification operation to replenish the missed supervision for better LGI.
By defining k-hop starved nodes, we transform the SS issue into a more manageable task of removing starved nodes. Inspired by CUR decomposition, we propose a simple yet effective solution to determine the starved nodes and diminish them using a regularization graph.
The proposed approach is model-agnostic and can be seamlessly integrated into various LGI models. Extensive experiments demonstrate that eliminating the starved nodes consistently enhances the statc-of-the-ard LGI methods, particularly under extremely limited supervision.
2 Preliminaries
2.1 Notations
Let Ass A.j. Aij. and A k denote the i-th row, the j-th column, the element at the i-th row and j-th column, and the k-th power of the matrix A, respectively. Let 1, represent an n-dimensional column vector with all elements being 1. Let Lx- (A) be an element-wise indicator function that sets Aij to 1 if it is positive, and 0 otherwise. Conversely, l (A) sets Aij to 0 if it is positive, and 1 otherwise.
2.2 Latent Graph Inference
(Latent Graph Inference). Given a graph G(V, X) containing n nodes V (Vi....,Vy, and a feature matrix X gaxd with each row X,; E gd representing the d- dimensional attributes of node V,, latent graph inference (LGI) aims to simultaneously learn the underlying graph topology encoded by an adjacency matrix A E Raxn and the discriminative d' "-dimensional node representations Z E guxd' based on X. where the learned A and Z are jointly optimal for certain downstream tasks T given a specific loss function L.
Definition 1
In general, an LGI model mainly consists of a latent graph generator P B x R that generates adjacency matrix A based on the node features X, and node encoder Fo (X, (X.A):

---

Raxd + Rnxd' that learns discriminative node representations Z based on X and the learned A. In practice, Fe typically implemented using k-layer GNN, while P can be realized through different strategies such as full parameterization [17, (6], MLP [10, 25], or attentive network [4, 15]. In this paper, we adopt the most common settings from existing LGI literature [4, 10, 13, 25, 46], considering TT as the semi-supervised node classification task and C as the cross-entropy loss.
2.3 Supervision Starvation
To illustrate the supervision starvation problem [10], we consider general LGI model M consisting of a latent graph generator Ps and node encoder Fe. For simplicity, we ignore the activation function and assume that Fe is implemented using a 1-layer GNN, i.e., Fe = CNN (X, A; O), where P (X). For each node X the corresponding node representation Z; learned by the model M can be expressed as:
Z: A,
Σ A jEQ
+
(I)
where Ω {ii ([]]Rt(A), 1} and As, =P (X:: Xz:).
Consider the node classification loss:
[C] Y Z.j = Σ Yu I. = Σ Yn Yn, In 1E
(E Xy: )0) -
min - A
(2)
TEV.
TEV.
JEN
where 3/2 represents the set of indexes of labeled nodes and |C| denotes the size of label set. For Vi E VL. E Q, A. is optimized via backpropagation under the supervision of label Y,:. For vi & Vz. however, if j & VL for Vj E Ω Ai will receive no supervision from any label and, as result, cannot be semantically optimal after training. Consequently, the learning models exhibit poor generalization as the predictions of testing nodes inevitably rely on these supervision-staree starveed weights. This phenomenon is referred to as supervision starvation (SS), where many edge weights are learned without any label supervision. It is easy to infer that this issue also persists in k-layer GNN.
We may ask why this problem arises? fact, the SS problem is caused by a common and necessary post-processing operation known as graph sparsification, which is employed in the majority of LGI methods [10, 28, 46] generate a sparse latent graph. To be more specific, graph sparsification adjusts the initial dense graph to sparse one through the following procedure:
Aij. if Aij E top-x(A.) Aij 0,
otherwise,
where top-k(A (A.) denotes the set of the top x values in A;: After this sparsification operation, a significant number of edge weights are directly erased, including the crucial connections established between pivotal nodes and labeled nodes. Another question that may arise is: how many important nodes or connections suffer from this problem? We delve into this question in the next section.
3 Methodology
3.1 Identification & Elimination of Starved Nodes
We first introduce the definitions of k-hop starved node and the corresponding k-hop starved weight.
Definition 2 (k-hop Starved Node). Given graph G(V, X) consisting of n. nodes V = (Vi...., Vn and the corresponding node featuress for a k-layer graph neural network GNN (X; +) with network parameters O the unlabeled node V; is a k-hop starved node if. for Vk E {1,..,, k}. VV, E (i),), where (i) () is the set of k-hop neighbors of V,, Vg is unlabeled. Specifically, O-hop starved nodes are defined as the unlabeled nodes?.
Based on Definition 2, we can define the k-hop starved weight as follows.
2 Here, want clarify that self connectios are considered when defining k-hop neighbors.
3

---

Definition 3 (k-hop Starved Weight). If an edge exists between nodes Vi and Vj, the associated edge weight Aij is a k-hop starved weight if both of the V, and V, qualifies as (k - hop starved nodes'.
According to the definition presented, it is evident that k-hop starved weights are precisely the ones that receive no semantic supervision from labels. As result, to address the SS problem, our focus should be on reducing the presence of k-hop starved nodes. The following theorem illustrates how we can identify such nodes based on a given initial adjacency matrix.
Theorem Given a sparse adjacency matrix A E R with self-connections generated on graph G(V, X) by latent graph inference model with k-layer graph neural network GNN; (X; O), the node Vi is a k-hop starved node, if 3j E n.....,np. such that [Ag (A)],, = 1, and for dj (i [ (A) [1+ (A)li = -.......uu (A)]ž 13, V3 unlabeled.
Proof. Please refer to the supplementary material for details.
To provide an intuitive perspective, we use two
real-world graph datasets, namely Cora (2708 nodes) and Citeseer (3327 nodes), as examples. We calculate the number of k-hop starved nodes for k = 1, 2, 3.4, 4, based on their original graph topology. Fig. shows the statistical results for the Coral40, Cora390, Citesser120, 120, and Cite- seer370 datasets, where the suffix number rep- resents the number of labeled nodes. From Fig. 1, we observe that as the value of l: increases, the number of starved nodes decreases. This can be explained by the fact that as & increases, the nodes have more neighbors (from 1- to k- hop), and the possibility of having at least one labeled neighbor increases. Adopting deeper GNN (larger k)) can thus mitigate the SS prob- lem. However, it is important to consider that deeper GNNs result in higher computational consumption and may lead to poorer general- ization performance [1, 2, 30]. Furthermore, as shown in Fig. 1, even with 4- GNN, there are still hundreds of 4-hop starved nodes the Citesser120. Therefore, we believe that employing a deeper GNN is not the optimal solution to resolve the SS problem
3000
Cora140
Number of Starved Nodes
Cora390
2500
Citeseer120
Citeseer370
2000
1500
1000
hohop
2-hop
3-hop
4hhop
K-hop
Figure I: Illustration of k-hop starved nodes on different datasets. Obviously, the number of k-hop starved nodes decreases as the value of & increases.
In fact, Theorem implicitly indicates how alleviate the SS problem. Intuitively, straightforward solution is to ameliorate the given adjacency matrix in order to reduce the number of starved nodes. This can be accomplished simply by reconstructing the connections between starved nodes and the labeled ones. Technically, we can achieve this by adding a regularization adjacency matrix B to A:
Ā A A aB
(4)
where À is the refined adjacency matrix, B models the recovered affinities between staved nodes and labeled ones, and a is balanced parameter that controls the contribution of and B. According to Theorem 1, we can identify the starved nodes based on A and replenish the missed supervision through B. thereby preventing À from being starved. Specifically, for each starved node V,, we can search for at least one closest labeled node Vj. and restore at least one connection between V/j and where can be arbitrarily chosen from the set of
V, for j (i) Ui) such that [Ig+ [ (1,2,... ....... A... Although this strategy is effective, it may be computationally complex. Even with small value of k. the computational cost of identifying k-hop starved nodes based on Theorem is prohibitively expensive. For example, when identifying 2-hop starved nodes, the time complexity of computing A alone reaches (n²)) In the next section, we will propose a more efficient solution.
e Note that, l-yayrr GNN, k-hop starved node also qualifics as (A- - 1)- starved node.
We discuss this further in the supplementary material.

---

3.2 CUR Decomposition Makes Better Solution
Inspired by CUR matrix decomposition [2.3], we propose an efficient alternative approach to identify the starved nodes. We first present the definition of CUR matrix decomposition.
Definition 4 (CUR Decomposition [2]). Given Q E RR of rank = raan Q), rank parameter k p. and accuracy parameter 0 < < 1, construct column matrix C Tx with columns from Q row matrix R E R x with r rows from Qu and intersection matrix U E Rxx with c, r, and
rank U) being as small as possible, in oder to reconstruct Q within relative-error:
QQQ
CUR (1 + e)llQ Qulle-
(5)
Here, Q2 - - E Rexm is the best rank l matrix obtained via the singular value decompo- sition (SVD) Q
With the definition of CUR decomposition, we can find a more efficient solution to identify the starved nodes. The following theorem demonstrates how we can accomplish this goal.
Theorem 2. Given spurse adjacency matrix A E B=x* with self-connections generated on graph g(V, X), construct C A|; col [ol_mask]] E R where col_
only positive values corresponding to c labeled nodes, and R = A mol_mask E {0. 132 contains row row_mask 1- E {0, 1)". Then, (a) = ||oow_mash col col_mask]
RR with O E TRxxe [Vili R8+}, where RM4 E N" indicates the set of indexes of positive elements from row _ask, and (c) for each i E RM4,
where 0 is
matrix, (b) the set of 1-hop starved nodes Seti(r)
V, is a 2-hop starved node if. for Vj satisfying [Lg] (R)]is 1, E RM+.
Proof. Please refer to the supplementary material for details.
Theorem 2 provides more efficient alternative for identifying k-hop starved nodes for k 21, In fact, the column matrix C models the relationships between all nodes and c labeled nodes, the row matrix R models the affinities between r 1-hop starved nodes and the whole nodes, and the intersection matrix U models the strength of connections between r 1-hop starved nodes and e labeled nodes. Theorem 2 states that U O, indicting that there no connections between the starved nodes and the labeled ones. Based on this observation, we propose a simpler approach to reduce the number of starved nodes. Specifically, we rebuild the intersection matrix to ensure that the reconstructed U o 0². Consequently, Eq. (4) can be rewritten as:
Á A oB A af' (Ü.n).
(6)
where function I(Ü,n) n)) extends the matrix Ú E Rr to an n x matrix by padding r rows of zeros and c columns of zeros the corresponding positions.
The question now turns to how reconstruct the intersection matrix U. For simplicity, we directly adopt the same strategy used in constructing A. Specifically, for each row i of U, we establish a connection between V; and V, for Vj E CM+, where CM_ E No represents the set of indexes of positive elements from col_mask. We then assign weights to these connections based on their distance. Note that, if we ensure each row of has at least one weight greater than O, there will be и-hop starved nodes for VK 1. This means that we do not need feed the k-hop starved nodes satiated, simply feeding k-hop ones for VK < k makes h-hopp starved nodes cease to exist. In addition, compared with the time complexity of O(dn2) ) to construct A, the time complexity of reconstructing Ú is (dre). The additional computational burden is relatively negligible since e < n.
3.3 Weight Contribution Rate Decay
Directly replenishing the additional supervision encoded in Ú by Eq. (6) may cause a potential issue we refer to as weight contribution rate decay. To understand this issue, we consider the j-th column
'In fact, with the reconstructed Ü, we can set Q CÜR as the regularization B. It is, of course, sensible and feasible. However, potential drawback is that the reconstruction of Q requires matrix multiplications of three matrices, which is time-coneen consumin.. Unexpectedly, we find that only constructing matrix Ú is enough to solve the SS problem since it models the relationships between 1-hop starved nodes and labeled ones.
5

---

vector A, of A for j E CM,. We define the weight contribution rates (WCR) of non-starved nodes p- and the WCR of starved nodes P+ as:
ENERY, Ai Aj
EiERn, Aij A.j
LigRn, Aij
EieRM, aU,
p- = P+ P==1-p=11
(7)
Ei Aij
E,
From Eq. (7), we observe that the WCR of non-starved nodes p- decays the number of starved nodes increases (i.e., 0+ increases). This means that p. becomes negligible if there are numerous starved nodes. As result, the j-th column vector A, of A for j CM+ heavily relies the j-th column vector U of the reconstructed intersection matrix U. This outcome is not desirable since the regularization imposed should not dominate significant portion of the final adjacency matrix. Recalling our initial objective of properly refiiigg the original latent graph to replenish the missed supervision, we will design two simple strategies to relieve this issue.
Decrease P4: On the one hand, we can decrease the WCR of starved nodes p+ by selecting only T(T < c) labeled nodes the supplementary adjacent points for each 1-hop starved node. This results in a sparse intersection matrix U. For this strategy, we present the following proposition: Proposition 1. Suppose that we randomly select out of e labeled nodes the supplementary adjacent points for each 1-hop starved node. If there are r 1-hop starved nodes, then Vj E CM+, Eier, aU., S P4. where P+ = P+ with only a probability of (Z)
we have P+- E.Ao
Proof. Please refer to the supplementary material for details.
Increase p.. On the other hand, we can improve the WCR of non-starved nodes p- by magnifying the weights of non-starved nodes. Specifically, Q E gaxe, where its c columns correspond to the labeled nodes and Q2, for vi E RM,. For vi & RM,, establish connections between the node V/2 and r(r labeled nodes Vj. and assign the corresponding weights Qı using similar strategy as constructing U. By adding the additional regularization matrix Q, the refined adjacency matrix Å can be expressed as:
construct an additional regularization matrix
Â = A + (r (ū.n) ((n)++(Q..))
(8)
Similarly, for this strategy, we have the following proposition:
Proposition 2. Suppose that randomly select out of c labeled nodes the supplementary adjacent points for each non-starved node. If there are r 1-hop starved nodes, then for Vjj E CK4, we
have p_ Eign, A. Eigor A, + Eipar, Qis A.A. (1-2) 2) m
2 p_, where p_ = =P- with only a probability of
A.A Qu
Proof. Please refer to the supplementary material for details.
3.4 End-to-End Training
Note that the proposed approach is model-agnostic and can be seamlessly integrated into existing LGI models. In Sec. 4, we will apply our design to state-of-the-art L.I methods [4, 10, 13, 46] and compare its performance with the original approach. Therefore, we follow these methods and implement the node encoder Fo using a 2-layer GNN. Then, we calculate the cross-entropy loss Coe between the true labels Y and the predictions Z, as well as a graph regularization loss Creg on A:
[c]
min L = Loe + 7hrg
Σ
Σ
ij In Zij + YLrgg
iEVL j=1
According to different LGI methods, the graph regularization loss Lreg can be different, such as Dirichlet energy [4] and self-supervision [10] (see supplementary material for more details). For fairness, in the experiments, we will adopt the same graph regularization loss as the comparison methods.
where 7 is balanced parameter and = Fo A) softmax AA AAx*)

---

Table 1: Test accuracy (%) of the baselines (M) and our CUR extension versions (M U and M R) on various datasets with different labeling rates (marked bold), where "OOM" indicates out of memory. The highest and second highest results are marked in red and blue, respectively.
Models / datavets
oighn arsv
Cora390
Coral 40
Cleeser370
Cieever120
Pubmed
of labeled 7 nodes
90941/16943
390/2708
1402278
37013527
1203527
60/9717
Labeling rate
53.70%
14.40%
5.17%
11.12%
3.61%
0.30%
GUN+KNN
55.15
0.33
67.94 + 0.29
73.28
0.22
E 0.53
0.05
GUN+KNN. U (ours)
55.82
+ 0.11
72.82 + 0.21
68.18
0.44
73.68 4: 0.10
69.74 + 0.54
74.12 = 0.32
GON+KNN R (ours)
55.86 0.10
72.92 0.28
68.12
0.48
73.66
0.14
69.90 + 0.68
74.78 0.17
GCN&KNN
0OM
72.16
68.76
1.20
77.28
0.64
68.64 + 1.14
0OM
GON&KNN U (ours)
0OM
73.04 0 0.20
70.16
78:40 0.44
70.52 + 1.04
0OM
GCN&KKNN__L (ours)
73.20
0.30
0OM
TDGL
00M
74.00 4 0.38
70,74 0.50
7,10
69.24 + 0.19
DOM
IDGL_U (ours)
0OM
74.54 + 0.52
70.82
0:49
7.14
69.32 = 0.39
0OM
IDGL_ R (ours)
0OM
74.48 0.47
71.14 0.22
0.15
69.86
0.50
0OM
LCGS [13]
0OM
72.02 J. 0.37
69.88 1 0,66
1
72.30
1 0.33
OOM
LCGS, (ours)
70.04
0..4
72.38 +
00M
LCGS_K R (ours)
0OM
72.22 : 0.45
70.14 0.64
0,36
72.40
+ 0.42
0OM
GRCN [46]
00M
73.34 -
68.86 0.25
0.23
71.24
0.19
69.24
0.20
GRCN_ (ours)
0OM
74.10 0.25
69.44 0.34
73.88 0.34
71.54
0.31
72.80 0,99
GRCN R (ours)
0OM
0.22
69.56
74,22 0.113
71.64
0.41
72.82 1.03
SLAPS [TO]
35.46 0.12
76.62 0.83
74.26:0.53
7.32
70.66
0.97
14.86 0.79
SLAPS U. (ours)
55.68 0.09
76.94 1. 0.42
74.56 0.21
74.82 1. 0.27
71.68 1 0.47
76.74
0.59
SLAPS_ R (ours)
56.11 + 0.15
76.82
0.19
75.00 0.49
74.90
72.36
77.12 = 0.77
Experiments
4.1 Experimental Settings
Baselines, As mentioned earlier, the proposed regularization module can be easily integrated into most existing LGI methods. To evaluate its effectiveness,
select representative LGI methods as baselines, including IDGL [4], GRCN [46], SLAPS [10], and LCGS [13]. We also consider two additional baselines marked as GCN+KNN [10, 19] and GCN&KNN [4, 19]. GCN+KNN is two-step method that first constructs KNN graph based on feature similarities and then feeds the pre-constructed graph a GCN for training. GCN&KNN
an end-to-end method that learns the latent graph and network parameters simultaneously. For methods that require a prior graph, we use the same KNN graph as in GCN+KNN, For GCN&KNN, we simply adopt the Dirichlet energy [4] as the graph regularization loss.
Datasets. Following the common settings of existing LGI methods [4, 10, 13, 46]. we conduct experiments on four well-known benchmarks: Cora, Citeseer, Pubmed [19,34], and ogbn-arxiv [14]. For detailed dataset statistics, please refer to the supplementary material. For all datasets, we only provide the original node features for training. To test the performance under different labeling rates, for the Cora and Citeseer datasets, add half of the validation samples to the training sets, resulting in Cora390 and Citeseer370, where the suffix number represents the total number of labeled nodes.
Implementation. We compare the above baselines with their corresponding CUR extension versions. Specifically, we consider two CUR extensions termed M. U and M_R R. (M refers to the baseline), where the former adopts the sparse intersection matrix U as the regularization, and the latter combines Ü and Q together (see Sec. 3.3 for details). In experiments, we practically select the t closest labeled nodes as supplementary adjacent points for each row of Ü and Q. For postprocessing operations on the graph, such as symmetrization and normalization [4, 10], we follow the baselines and adopt the same operations for fairness. We select the values of 7 and a from the sets {10, 15, 20, 25, 30, 50} and (0.01, 0.1, 1.0, 10, 50, 100). respectively. For other hyperparameters such as learning rate and weight decay, follow the baselines and use the same settings. For each method, we record the best testing performance and report the average accuracy of five independent experiments, along with the corresponding standard deviation.
4.2 Comparison Results
Table presents the comparison results on all used datasets. It is evident that our proposed CUR extensions consistently outperform the corresponding baselines, demonstrating the effectiveness of eliminating starved nodes. When considering the labeling rates of different datasets listed in the third row of Table 1, we observe that the lower the labeling rate, the greater the performance
7

---

Iran lase GRES kull
Lose Val
Than
Losu Valle
Tesn Losi SUMF (6.8))
Lioe DIT CON mZ
TextAcc (RCL)) hondd
Aec
3TH--5M KSM
Teut Ace CLaY
Acc: 2CN-22N (OUAT
20
20
50
2008
1000
10h
600
175
-14
10 100
(a) GCN+KNN
(b) GRCN
(c) SLAPS
Figure 2: Training loss (left vertical axis) and testing accuracy (right vertical axis) curves of GCN+KNN, GRCN, SLAPS, and their corresponding CUR extensions on the Pubmed dataset.
Table 2: Number of k-hop starved nodes (k E {1, 2}) on various datasets when selecting different number of neighbors (r) in graph sparsification operation.
Number of neighbors (7)
10
20
Datasets
Coral40
Citeseer| 20
Pubmed
Cora140
Citeseerl 120
Pubmed
T-hop starved nodes
I,625
2,268
19,076
993
1,577
18,478 12,843
2-hop starved nodes
100
299
16,756
0
0
improvement achieved by our methods. Notably, on the Pubmed dataset with an extremely low labeling rate of 0.30%, the accuracy of our proposed methods (M_R) increase by 6. 6.12%. 3.58%, and 2.26% compared to the basic models (M) of GCN+KNN, GRCN, and SLAPS, respectively. This is because the lower the labeling rate, the more starved nodes exist in the dataset (see Fig, 1 for an example). Our proposed methods aim to restore the destroyed affinities between starved nodes and labeled nodes, enabling us to leverage the semantic supervision missed by baselines, thereby achieving superior performance with extremely limited supervision.
Fig. 2 displays the training loss and testing accuracy curves of GCN+KNN, GRCN, SLAPS, and their CUR extensions on the Pubmed dataset. We omit the curves for the first 200 epochs of SLAPS because, during this stage, SLAPS focuses solely on learning the latent graph through an additional self-supervision task without involving the classification task. From Fig. 2, we observe that our proposed CUR extensions achieve higher testing accuracy compared to their corresponding baselines. In comparison with the CUR extensions of GCN+KNN, the CUR extensions of GRCN and SLAPS exhibit relatively stable accuracy results as the training epoch increases. This stability can be attributed to GRCN and SLAPS jointly learning the latent graph and network parameters in an end-to- manner, whereas GCN+KNN pre-constructs KNN graph and maintains fixed graph during training without optimization. For GRCN, our proposed CUR extensions demonstrate lower training loss and higher testing accuracy, further indicating their improved generalization by removing starved nodes. Additionally, we observe relatively unstable training loss for the CUR extensions of SLAPS. The potential reason is that SLAPS introduces an additional graph regularization loss through self-supervision task, while its CUR extensions aim to reconstruct the destroyed connections in the latent graph. As result, the training process for the self-supervision task can exhibit some instability,
4.3 Discussion
We would like to explore the question that why our proposed methods yield a slight improvement on the Cora and Citeseer datasets, while achieving a substantial improvement on the Pubmed dataset. As shown in Table 2, when t = 10, there are 100 and 299 2-hop starved nodes on the Coral 140 and Citeseer 120 datasets, respectively. However, when
20, there are no 2-hop starved nodes on the Coral40 and Citeseer1 20 datasets, and the number of h-hop starved nodes also sharply decreases. In this scenario, since the comparison baselines all utilize a 2-layer GNN, they are unaffected by 2-hop starved nodes and only minimally affected by 1-hop starved nodes. Consequently, our methods result only slight improvements over the baselines on the Coral I 40 and Citeseer 120 datasets. On the other hand, when = 20, there are still 12, 843 2-hop starved nodes present on the Pubmed dataset. Since we effectively eliminate these starved nodes without requiring additional graph convolutional layers, our methods provide notable benefits on this dataset with extremely low labeling rate.
8

---

Table 3: Test accuracy (%) of our proposed CUR extensions for GCN+CNN, GRCN, and SLAPS
when eliminating different number of staved nodes on the Pubmed dataset.
Staved nodes (%)
100
80
60
40
20
10
0
UCN-KNN_U
68.06 0.05
69.42
70.20
0.22
71.52
0.15
72.40
0.27
73.04
0.29
74.12
0.32
GCN-KNN_R
69.12 1 0.33
69.46
0.22
70.46
0.1.9
71.90
13.24
0.05
74.00 0.14
74.78
0.17
GRONL
70.24
72.34400.33
72.86470.55
73.04
7.72
7..56-0..77
72.80
70.20
7..54:10.8
0.37
72.80
72.80 0.74
SLÄPS D
74,86 0.79
7626
76.66
7.33
76.7
76.32
76.54
SLAPS_R
75.64 + 0.45 76.44 + 1.27
76.52 +: 0.18
76.50
1450::122
1.22
76.38 0.45
76.70 +: 0.59
7.77
Table 4: Parameter sensitivity of T when applying our proposed method to GCN+CNN, GRCN, and SLAPS the Pubmed dataset. The baseline results indicate the accuracy the original methods.
The value of y GON+KNN
bascline (0)
10
20
23
30
50
68.66
71.86
72.92
1.12:..33 0.32
73.76
GCN+KNN R
68.66 0.05
73.10
+: 0.09
73.90
- 0.14
74.02
+ 0.10
74.56
14.564:000
0.12
74.78
0.17
14.62
0.12
GRON_
6020
11.92
4 0.8
12.56
0.77
72.64
1:3
72.80
0.90
f2.56
T.02
T1.50
T.13
72.12
72.54
7280
72.82
72.44
71.86
SLAPS_ D
14.86
15.98
76.50
1 0.87
13.58
0.90
76.88
T.6
16.74.0..50
0.50
13.08
0.89
SLAPS_R
74.86
76.00
+ 1.17
76.48
0.69
76.40
+ 0.48
77.12
0.77
76.38
0.33
76.50 = 0.59
Table 5: Parameter sensitivity of when applying proposed method to GCN+CNN, GRCN, and
SLAPS on the Pubmed dataset. The baseline results indicate the accuracy the original methods.
The value
buseline
0.01
0.1
1.0
10
50
100
GON+KNN U
68.66
10:0000 0.03
68.04
+ 0.05
67.96
= 0.08
68.
0.10
69.92
- 0.12
12.70 2 0.06
14.12
00..0.33 0.32
GON+KNN_R
0.05
67.96
0.30
67.90
GRCN_D [
69.27 1.20
69.24
I 0.10
69.72
_ 0.19
71.92 1 0.2
72.60
0.94
5..52.33.99
59.74
= 6.74
GRCN
0.220
0.20
69.24
0.10
69.66
+ 0.22
71.94
0.22
7: 1.03
68.98
1: 4.05
60.34
6.50
SLÄPS U
74.86 0.79
74.8%
0.90
74.48
- 0.72
74.94
0.8
76.26
0.80
76.74
0.550
76.08
= 0.7
SLAPS R
74.86 1 0.79
74.62
1: 1.51
74.32
1 0.83
74.76
1 0.71
76.22
1: 0.55
0.77
76.74
0.68
4.4
Ablation Study
In this subsection, we aim to explore and answer the following questions.
How many starved nodes should be eliminated? The results shown in Table 1 indicate that elim- inating all starved nodes contributes to the performance improvement of the baselines. It is im- portant to understand the relationship between the number of starved nodes removed and the cor- responding performance improvement of the baselines. To investigate this, we randomly remain 10%, 20%, 40%, 60%, 80% starved nodes and evaluate the performance of GCN+CNN, GRCN, and SLAPS accordingly. The results on the Pubmed dataset are summarized in Table 3. We find that, for GCN+KNN, smaller number of starved nodes leads to higher testing accuracy. For GRCN and SLAPS,, however, we need to check the number of starved nodes to obtain optimal performance.
How affects the performance. Table 4 shows that the selection of 7 slightly differentiates the performance of our proposed methods. In general, a larger value of 7 leads to a higher improvement in performance. However, when is set too large, such as 50, the performance starts to degrade. This degradation occurs due to the introduction of incorrect labels when 7 exceeds a certain threshold.
How a affects the performance. Table presents the sensitivity of parameter a on the Pubmed dataset. It is observed that a relatively larger value of a, such as 10 50, leads to a significant improvement in performance. This finding further emphasizes the effectiveness of our proposed regularization methods in enhancing the performance of existing LGI models.
5 Related Work
Latent Graph Inference. Given only the node features of data, latent graph inference (LGI) aims to simultaneously learn the underlying graph structure and discriminative node representations from the features of data [10, 24,39), 39]. For example, Jiang et al. [15] propose to infer the graph structure by combining graph learning and graph convolution in a unified framework. Yang al. [45] model the topology refinement as a label propagation process. Jin et al. [16] explore some intrinsic properties of the latent graph and propose robust I.GI framework to defend adversarial attacks on graphs. Though effective, these methods require a prior graph to guide the graph inference process. Controversially,

---

some methods have been proposed to directly infer an optimal graph from the data. For example, Franceschier al. [11] regard the LGI problem as bilevel program task and learn discrete probability distribution on the edges of the latent graph. Norcliffe-Browe Brown et al. [29] focus on visual question answering task and propose to learn an adjacency matrix from image objects so that each edge is conditioned on the questions. Fatemi et al. [10] propose a self-supervision guided LGI method, called SLAPS, which yields supplementary supervision from node features through an additional self-supervision task. Our method is totally different from SLAPS as provide supplementary supervision directly from the true labels. More importantly, our method is model-agnostic and can be easily integrated into most existing LGI methods.
CUR Matrix Decomposition. The CUR decomposition [2, 3] of a matrix Q R R= aims to find a column matrix C E R with a subset of с < m columns of Q, and a row matrix R. Rexm with a subset of < n rows of Q, as well as an intersection matrix U E Reer such that the matrix multiplication of CUR approximates Q. Unlike the SVD decomposition of Q. the CUR decomposition obtains actual columns and rows of Q which makes it useful in various applications [20, 28]. In method, instead of seeking optimal matrix approximation, CUR decomposition to identify and eliminate the starved nodes. The extracted intersection matrix U is then reconstructed and served better latent graph inference. To the best of our knowledge, we are the first to introduce CUR matrix decomposition into the field of graph neural networks.
employ
regularization term to provide supplementary supervision for
6 Conclusion
In this paper, we analyze the common problem of supervision starvation (SS) in existing latent graph inference (LGI) methods. Our analysis reveals that this problem arises due to the graph sparsification operation, which destroys numerous important connections between pivotal nodes and labeled ones. Building upon this observation, we propose to recover the corrupted connections and replenish the missed supervision for improved graph inference. To this end, we begin by defining k-hop starved nodes and transform the SS problem into a more manageable task of reducing starved nodes. Then, we present two simple yet effective solutions to identify the starved nodes, including a more efficient method inspired by CUR matrix decomposition. Subsequently, we eliminate the starved nodes by constructing and incorporating a regularization graph. In addition, we propose two straightforward strategies to tackle the potential issue known as weight contribution rate decay. Extensive experiments conducted on representative benchmarks demonstrate that our proposed methods consistently enhance the performance of state-of-the-art LGI models, particularly under extremely limited supervision.
7 Acknowledgments and Disclosure of Funding
We are very grateful to Bahare Fatemi for her valuable discussion of our work. We thank the anonymous NeurlPS reviewers for providing us with constructive suggestions improve our paper. This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-23-1-0090.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference Learning Representations, 2021.
[2] Christos Boutsidis and David P. Woodruff. Optimal cur matrix decompositions. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, page 353-362, 2014.
[3] HanQin Cai, Keaton Hamm, Longxiu Huang, and Deanna Needell. Robust cur decomposition: Theory and imaging applications. SIAM Journal on Imaging Sciences, 14(4):1422-150,, 2021.
[4] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Advances in Neural Information Processing Systems, pages 19314-19326. 2020.
[5] Yudong Chen, Sen Wang. Jianglin Lu, Zhi Chen, Zheng Zhang, and Zi Huang. Local graph convolutional networks for modsl hashing. Proceedings of the 29th ACM International Conference Multimedia, pages 1921-1928, 2021.
10

---

[6] Luca Cosmo, Anees Kazi, Seyed- Ahyead Ahmadi, Nassir Navab, and Michael Bronstein. Latent- graph learning for disease prediction. In Medical Image Computing and Computer Assisted Intervention, pages 643-653, 2020.
[7] Haitz Sáez de Ocáriz Borde, Ances Kazi, Federico Barbero, and Pietro Lio. Latent graph inference using product manifolds. In The Eleventh International Conference on Learning Representations, 2023.
[8] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference Learning Representations, 2020.
[9] Bahare Fatemi, Sami Abu-EI-Haija, Anton Tsitsulin, Mehran Kazemi, Dustin Zelle, Neslihan Bulut, Jonathan Halcrow, and Bryan Perozzi. Ugsl: A unified framework for benchmarking graph structure learning. In the 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML) the 40 th International Conference on Machine Learning, 2023.
[10] Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. In Advances in Neural Information Processing Systems, pages 22667-22681, 2021.
[1I] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Proceedings of the 36th International Conference on Machine Leamiing pages 1972-1982, 2019.
[12] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
[13] Minyang Hu, Hong Chang, Bingpeng Ma, and Shiguang Shan. Learning continuous graph structure with bilevel programming for graph neural networks, In Proceedings of the Thirty-Firs International Joint Conference on Artificial Intelligence, pages 3057-3063, 2022.
[14) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs In Advances in Neural Information Processing Systems, pages 22118-2213,, 2020.
[15] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph Saamingg-oonoouttion Computer Vision and Pattern Recognition, 2019.
networks. In Proceedings of the IEEE/CVF Conference on
[16] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 66-74, 2020.
[17] Ances Kazi, Luca Cosmo, Seyed-Ahmen Ahmad Ahmadi, Nassir Navab, and Michael M. Bronstein. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions Puttern Analysis and Machine Intelligence, 45(2): 1616- 2023.
[18] Byung-Hooe Kim, Jong Chul Ye, and Jae-Jin Kim. Learning dynamic graph representation of brain connectome with spatio-temporal attention. In Advances in Neural Information Processing Systems, pages 4314-4327, 2021.
[19] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[20] Changsheng Li, Xiangfeng Wang, Weishan Dong, Junchi Yan, Qingshan Liu, and Hongyuan Zha. Joint active learning with feature selection via cur matrix decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1186)133 2019.
[21] Qimai Li, Zhichao Han, and Xiao-ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[22] Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, 2018
[23] Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. In Advances in Neural Information Processing Systems, pages 9720-9733, 2021.
11

---

[24] Xin Liu, Jiayang Cheng, Yangqiu Song, and Xin Jiang. Boosting graph structure learning with dummy nodes. In Proceedings of the 39th International Conference on Machine Learning. pages 17704-13716, 2022.
[25] Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, page 1392 1403, 2022.
[26] Jianglin Lu, Jingxu Lin, Zhihui Lai, Hailing Wang, and Jie Zhou. Target redirected regression with dynamic neighborhood structure. Information Sciences, 544:564-584 2021.
[27] Jianglin Lu, Hailing Wang, Jie Zhou, Yudong Chen, Zhihui Lai, and Qinghua Hu. Low-rank adaptive graph embedding for unsupervised feature extraction. Pattern Recognition, 113:107758, 2021.
[28] Michael W. Mahoney and Petros Drineas. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):697-702, 2009.
[29] Will Koroliife-Brown, Stathis Vafcias, and Sarah Parisot. Learning conditioned graph structures for interpretable visual question answering. In Advances in Neural Information Processing Systems, 2018.
[30] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, 2020.
[31] ErLin Pan and Zhao Kang. Multi-view contrastive graph clustering. In Advances in Neural Information Processing Systems, pages 21 2148-2159, 2021.
[32] Xingyue Pu, Tianyue Cao, Xiaoyun Zhang, Xiaowen Dong, and Siheng Chen. Learning to learn graph topologies. In Advances in Neural Information Processing Systems, pages 4249-4263 2021.
[33] Víctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, pages 9323 9002-9332222 2021.
[34] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93, 2008.
[35] Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu. Skeleton- based action recognition with directed graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
[36] Qingyun Sun, Jianxin Li,
Hao Peng, Jia Wu, Xingcheng Fu, Cheng Ji, and Philip S Yu. Graph structure learning with variational information bottleneck. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4165-4174, 2022.
[37] Petar Velickovic, Guillem Cueurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. star, 1050(20): 48550, 2017.
[38] Ruijia Wang. Shuai Mou, Xiao Wang. Wanpeng Xiao, Qi Ju. Chuan Shi, and Xing Xie. Graph structure estimation neural networks. In Proceedings of the Web Conference 2021, page 342-353, 2021.
[39] Yaohua Wang, Fangyi Zhang, Ming Lin, Senzhang Wang, Xiuyu Sun, and Rong Jin. Robust graph structure learning over images via multiple statistical tests. In Advances in Neural Information Processing Systems, 2022.
[40] Yaohua Wang, Yaobin Zhang, Fangyi Zhang, Senzhang Wang, Ming Lin, YuQi Zhang, and Xiuyu Sun. Ada-NETS: Face clustering via adaptive neighbour discovery in the structure space. In International Conference on Learning Representations, 2022.
[41] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (log), 38(5):1-12, 2019.
[42] Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In Advances in Neural Information Processing Systems, 2022.
12

---

[43] Ruiqing Xu, Chao Li, Junchi Yan, Cheng Deng, and Xianglong Liu. Graph convolutional network hashing for cross modal retrieval. Proceedings of the Twenty-Eighth International Joint Conference Artificial Intelligence, pages 982-988, 2019.
[44] Yi Xu, Lichen Wang, Yizhou Wang, and Yun Fu. Adaptive trajectory prediction via transferable gnn. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 6520-650 6,31, 2022.
[45] Liang Yang, Zesheng Kang, Xiaochun Cao, Di Jin, Bo Yang. and Yuanfang Guo. Topology opti- mization based graph convolutional network. In Proceedings of the Twenty-Eighth International
Joint Conference on Artificial Intelligence, pages 4054-4061, 2019.
[46] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In Machine Learning and Knowledge Discovery in Databases, pages 378-393, 2021.
[47] Yaig Zhang, XiMing Xing, and Liang Liu. Dualgraph: graph-based method for reasoning about label noise. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9654 9663, 2021.
13

---

Appendix
A Proof of Theorem
A.1 Proof of Theorem
Proof. To simplify the proof, let us assume that A = 12+ (A) {0, 1 Consider node V,. If V,. Now, if (A²);; A A.j it means that there exists an 1-hop neighbor of V, that is also the 1-hop neighbor of V, indicating that node V is one of the 2-hop neighbors of V₁ Similarly, if (A*);; (A) A, = 1. it signifies that there exists a 2-hop neighbor of V; that also the 1-hop neighbor V,, implying that node V, is one of the 3-hop neighbors of V,. By extension, if (A AA²); ))
Aij 1, implies that node V one of the 1-hop neighbors
implies that node Vj the one of h-hop neighbors of V, Based this observation, for Vj {i (A) IU(A)) = Iu... (UA...((A)::)
1}. if node Vi is unlabeled, it indicates that all the x-hop neighbors of V; for k E {l...., k} are unlabeled nodes. Therefore, according to Definition 1, node qualifies as k-hop starved node.
Illustration of Theorem 1. To provide a clearer under- standing. we present an example illustrate the process of identifying k-hop starved nodes based on the given adja- nodes,
3
cency matrix. Fig. depicts graph consisting with 2 labeled and 4 unlabeled. The edges between the nodes are shown in the figure, with all edge weights set to 1 for simplicity. To identify the k-hop starved nodes, we need determine
1
Labeled
Unlabelad
k-hop neighbors for each node. The steps below demonstrate the identification process of k-hop neighbors based on the given graph in Fig. 3, where the k-hop neighbors for each node are listed at the end of each row of the corresponding matrices:
Figure 3: A simple graph consisting of nodes with 2 labeled and 4 unlabeled.
1
2
3
5
6
1
0
1
(V3, V/3)
2
1
1
0
(Vs, V2)
Identifying 1-hop neighbors based on A
3
1
1
0
0
(V1, 22,V2,1 Vo)
4
0
1
0
(V2)
5
0
0
(V))
1
0
0
(Vg)
Since nodes V22 and Va are labeled, we identify the 1-hop starved nodes as
[V1, VG, Vol.
1
2
3
4
5
6
0
2
(V2, Vo)
2
3
2
2
0
1
(V,, Vo)
Identifying 2-hop neighbors based on A
1
(V4, V3))
4
0
2
1
2
0
0
(Vg)
0
2
(V/)
2
0
0
2
(V1, V2)
Now, identify 2-hop starved nodes from the set
{Vi, Vs,
Vo)
(VG)-
2
3
5
6
7
1
(V))
3
7
5
(V/)
Identifying 3-hop neighbors based on 3
7
10
3
(Ø)
4
1
5
4
0
(V1, Vo)
5
0
4
(V2, Vo)
6
3
3
6
1
4
(Va V.)
"Note that, applying the function 1x (-) A does affecc the proof process.
14

---

We observe that there are no 3-hop starved nodes.
2
3
4
5
6
1
19
11
20
12
10
(0)
2
11
19
20
12
4
10
(Ø)
Identifying 4-hop neighbors based on A
3
20
20
30
10
10
16
(0)
4
4
12
10
1
4
(V))
5
12
10
9
(V4)
6
10
10
16
4
10
(Ø)
We observe that there are no 4-hop starved nodes.
Note that, a node identified as k-hop starved node also considered as (I: - 1)-hop starved node,
exemplified by node Vg. Consequently, if there no k--opp starved nodes present, it follows that there are no (k: + hhp starved nodes.
A.2 Proof of Theorem 2
Proof. Given that C = A[; col_mask] E R C models the affinities between all nodes and c labeled nodes. Consequently, if (row_ (row_mask); LR- (CL.); 1, indicating that (C1c); = can deduce that there are no labeled 1-hop neighbors of node V,. As a result, node V2 belongs to the of 1-hop starved nodes, denoted Set, (r) [Vili RM.,), J. Additionally, it follows that U = A'row_mast col [_mask]] = Rr Considering R = A row A[row__mas mask,;] E R=x", where R models the affinities between the r 1-hop starved nodes and all nodes, we can examine each i E RM, (where RM, denotes the indexes of all 1-hop starved nodes). If all 1-hop neighbors of Vi (ie., V/j satisfying g+ [R)]ij = are 1 1-hop starved nodes (i.e., j E RM+)), then node V, qualifies as
2-hop starved node.
Illustration of Theorem To facilitate understanding, we continue using Fig. 3 as an example for illustration. According to Theorem 2, the corresponding C, U, R matrices are as follows:
4
1
0
0
1
2
3
5
6
2 4
2
1
1
0
1
C:
1
0
R
1
0
0
0
;
U
5
0
4
1
1
0
0
1
0
6
0
0
Based on the C. matrices, we can determine that row_mask = 1,,0,0,,,1, TJT, RM, {1, 5, 6), the 1-hop starved nodes are V1, V/, Vo, and the 2-hop starved node is V/.
A.3 Proof of Proposition
Proof. Recall that 0. Eicre aD.,
and 0+ Eican aU,, For Vj CM4, if we randomly
Σ, A;
Σ. A,,
select out of labeled nodes the supplementary adjacent points for each 1-hop starved node V,,
then the probability Ü. > is Considering the j-th column (j E CM4), if Σ. aU.; EiERN. aU (i.e., 2+ = p+ ). it means that all the 1-hop starved nodes V; (for i E RM4) select V, as the supplementary adjacent point. Since there are r 1-hop starved nodes, the probability of p+ = P+
E.em ab.,
< pt, where P+ = p+ with only a (²)". Moreover, since < c, we have P+ = E. probability of (!)².
A.4 Proof of Proposition 2
Proof. Recall that P_ Engm, A Eieu, Qu and p_ E.eu, A. For Vj CM4, Σ. Aay Eigu, randomly select out of labeled nodes the supplementary adjacent points for each non-starved
Σ. A,
15

---

Table 6: Detailed description of the datasets used in experiments.
Dataset Statistic
Nodes
Edges
Features
Classes
Labeling Rate
ogbn-arxiv
169,343
1,166,243
128
40
53.70%
Cora 140
2,708
5,429
1,433
7
5.17%
Cora390
2,708
5,429
1,433
7
14.40%
CiteseerI 20
3,327
4,732
3,703
6
3.61% %
Citeseer370
3,327
4,732
3,703
6
11.12%
Pubmed
19,717
44,338
500
3
0.30%
node, then the probability of Qú = E1 Considering the j-th column (j E CM.)), = p-). ) it means that all the non-starved nodes V; (for & RM.,) do not select Vj as the supplementary adjacent point. Since there are 1-hop starved nodes, the probability of
Ligns, Qiy
(i.e, p-
P_ p- is (1 - = Moreover, since Σ; Aij Eiesn, A. (RM++ r)), have p- 2 p- where p_ p_ with only probability of (1 2) =
B Experimental Settings
B.1 Dataset Description
Table 6 provides comprehensive overview of the datasets used in our experiments, including various statistical characteristics. Please refer to the table for detailed information regarding the datasets. Note that, the original edge features are not used in the experiments our goal is to infer latent graph from the node features of the datasets.
B.2 Baselines
In our experiments, utilize publicly available code repositories provided by the respective authors and follow the hyperparameter settings outlined in their papers [4, 10, 13, 19, We rerun the codes for all the methods and record the best testing accuracy. Below, summarize the implementation details and provide the code links for each of the used methods:
GCN+KNN [19]: https//githab.com/kkiii/yggg
GCN&KNN [19]: htgs://giihub.com/ttp///yyys
For GCN&KNN, we implement the codes by ourselves. For simplicity, we adopt the following Dirichlet energy [4] as the graph regularization loss:
1 2n
Greg
A 1 X
IDGL [4]: http://gthab.ccm//nghhaa///..1.
GRCN [46]: http://giinubcoom///uussssssCCC
SLAPS [10]: http://ghhhacoomBBBeelllllssssss
Note that, SLAPS is multi-task-based approach that involves training additional self-supervision task for latent graph inference. To ensure computational efficiency, we set the maximum number of epochs to 1000 for ogbn-arxiv dataset. We adopt the following denoising autoencoder loss as the graph regularization loss [10]:
Grog F F(Xiday GNN [X, A; (oNMone
where idr the selected indices, and the binary cross-entropy loss the mean-squared error loss [10]. LCGS [13]: https:/giitub.oom/ummmycCCC
16

---

Table 7: Accuracy, parameters and FLOPs of SLAPS when using different number of GNN layers.
Layers
Accuracy
Parameters
FLOPs
74.86 + 0.79
645.76K
12.70G
4
70.24 + 1.58
680.90K
13.39G
8
41.18 + 0.88
751.17K
14.76G
C Further Discussions
C.1 Deeper GNNs
Why using deeper GNNs is not an optimal solution? This is because using deeper will bring up new issues as illustrated below. First, although increasing GNN 4 layers reduces the number of starved nodes from near 3, 000 to near 500 for the Citeseer 20 dataset, the number of starved nodes still accounts for nearly 15%. In fact, the number of starved nodes depends the labeling rate of nodes, the graph sparsification process, and so on. How to select the number of layers of GNNs reduce the starved nodes for different datasets and different LGI methods is not easy. Second, deeper GNNs typically provide inferior performance. To allow a k-hop starved node receive information from labeled nodes, the GNNs need to have at least + 1 layers. However, as the number of layers k: increases, the GNNs may still fail to propagate supervision information from labeled nodes to h-hopp starved nodes due to the wver-squahhing issue [1]. Moreover, deeper GNNs will make the oversmoothing problem [10. 21] ] be even more severe. Empirically, we test the SLAPS method on the Pubmed dataset using a different number of layers, and the corresponding accuracies can be seen in Table 7. As we can see, the accuracy of SLAPS with 8-layer GNN is extremely low, demonstrating that the generalization of GNNs cannot be guaranteed by simply increasing the number of layers. Moreover, deeper GNNs make the model more complexity. Table 7 lists the number of parameters and the float point operations (FLOPs) of SLAPS method with 2, 4, and 8-layer GNNs. We observe that as the number of layers increases, both the number of parameters and the FLOPs increase. In fact, the majority of existing LGI methods typically only adopt 2-layer GNNs for effectiveness and efficiency.
several factors, including
C.2 Degree Distribution
Why introducing connections between labeled and unlabeled nodes helps the models? We provide a basic insight to answer this question. As we know, an unlabeled node must belong to a specific class, and in the node classification task, a specific class must have some labeled nodes. As result, we can derive the prior assumption that a good classification model will make an unlabeled node closer to some labeled nodes of the same class. That is why we select the closest labeled nodes as the supplementary adjacent points for the starved nodes. If we compulsorily add such connections between the unlabeled node and its closest labeled nodes, the prior information will be exploited during training. helping the models work better. It is worth noting that introducing connections between labeled and unlabeled nodes can lead to a substantial rise in the degrees of labeled nodes. A potential question is that whether altering the distribution of node degrees will have an adverse effect on the model. To be honest, we have not yet observed any adverse effects from the current experimental results. Nevertheless, it is still worth exploring whether the divergence in degree distributions will potentially hinder the model's performance. What the exact relationship is between the degree distributions and the model's performance in latent graph inference task is difficult and open question that deserves in-depth exploration.
C.3 Definition of Regularization Graph
Why selecting k = to define the regularization graph between k-hop starved nodes and labeled ones? In fact, we can set any value for l define the regularization graph. However, if set ie > 1, there will be potential issue. For illustration, let us set k = 3 and eliminate the 3-hop starved nodes by adding the regularization graph. In this case, 1-hop and 2-hop starved nodes will still exist since only 3-hop starved nodes are removed. To address this, simple solution is to directly set l: 1 to define the regularization graph. Why only setting l: = works? According to the definition of starved nodes, we know that a k-hop starved node also qualifies (k 1)-hop starved node. Therefore, if
17

---

Table 8: Test accuracy (%) of different models corresponding to the best validation performance.
GCN+KNN GCN+KNN U
67.28 + 0.38
GRCN
68.62 0.19
SLAPS
74.50 + 0.33
72.76 + 0.29
GRCN U
72.30 0.95
SLAPS U
76.00 + 0.41
GCN+KNN_R
72.98 + 0.31
GRCN_R
72.14 0.79
SLAPS_R
76.86 + 0.83
we eliminate 1-hop starved nodes then all m-hop starved nodes for m > will eliminated. Due to the effectiveness and simplicity, therefore select lt 1.
C.4 Generalization Performance
To show the results of the models corresponding to the best validation performance, we conduct more experiments the Pubmed dataset. and the experimental results are listed in Table 8. As we can our methods still improve the baselines, which further indicates their effectiveness.
D Limitation
identify k-hop starved nodes for k: 1. Additionally, based Theorem and CUR matrix decomposition, we demonstrate the identification of k-hop starved nodes for & [1,2]. How identify k-hop starved nodes for an interesting direction for further investigation. Nevertheless, it is worth noting that by eliminating all k-hop starved nodes, there will be k-hop starved nodes for Vk к. Consequently, we think that only identifying k-hop starved nodes for k E {1,2} is sufficient and efficient to address the problem of supervision starvation.
According Theorem
based CUR decomposition remains
18


Reviews:
[{"review_id": "B18MoqskiC", "reviewer": "Reviewer_Qcor", "summary": "The paper introduces a model-agnostic enhancement for current LGI (latent graph inference) methods, aiming to address the assumed issue of unlearned features in a substantial number of nodes and edges, which are believed to negatively impact LGL's generalization performance. It proposes to learn a weighted residual graph, focusing on unlabeled nodes without labeled neighbors and intending to link them with some labeled nodes. Additionally, the proposed method applies a sparsity constraint to the residual graph, preventing significant alterations to the underlying graph topology learned from the base LGI model. Finally, the paper evaluates the effectiveness of this approach by integrating it with several prior LGI models, and finds modest improvements in standard graph learning tasks.", "questions": "1. Could the authors provide further elaboration on why the k-hop starved edges are defined as \"having at least one endpoint being a $k$-hop starved node\"? If the main objective is to identify edges whose weights are not trained in a $k$-layer GNN, wouldn't a more appropriate definition be \"both endpoints are $(k-1)$-hop starved nodes\"? (0-hop starved = unlabeled)\n\n2. Could the authors provide an analysis of why adding connections between 1-hop starved nodes and labeled nodes improves the model's generalization? It appears that while introducing supervision signals to some unlabeled nodes, these additional connections to the labeled nodes may make them less \"similar\" to the unlabeled nodes. For example, the degree distribution of labeled and unlabeled nodes might be similar in the original dataset, but after the structural modifications proposed in the paper, the labeled nodes may exhibit significantly higher degrees than the unlabeled nodes. Wouldn't such divergence in the distribution of labeled and unlabeled nodes negatively impact the model's generalization? An explanation of these potential effects would help clarify the benefits and implications of the proposed structural modifications.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper's strength lies in its investigation of the important problem of optimizing the structure for neighborhood aggregation in graph neural networks. It introduces a method that addresses the issue of \"supervision starvation\" by adding labeled neighbors to initially supervision-starved nodes, which is demonstrated to bring benefit to existing LGI methods, especially on larger graphs.", "weaknesses": "1. The paper's proposed method shows moderate improvements, with limited statistical significance on small graphs (Cora and Citeseer). Larger graphs display more significant enhancements. The relationship between improvement and graph size should be explored for better insights. Further improvements for small graph scenarios are needed.\n\n2. The paper lacks clarity in explaining the generation of the residual adjacency matrix. The emphasis on the relationship with CUR decomposition should be weaken since the learning criteria for weights in matrix $\\tilde{U}$ are unrelated to reconstructing the target matrix $Q$. Furthermore, the method of selecting \"supplementary adjacent points\" from the labeled nodes for each 1-hop starved node remains unclear. The authors should be aware that \"randomly selecting a subset of $\\tau$ nodes from $c$ labeled nodes\" is a different statistical event compared to \"picking each labeled node at a probability of $\\frac{\\tau}{c}$\". Improved explanations of these aspects are necessary to avoid confusion and strengthen the paper's presentation.\n\n3. The paper lacks significant theoretical and technical novelty. Certain modeling choices are presented without adequate theoretical justification to demonstrate their importance or sensitivity analysis to show their insignificance. Specifically, the content in the paper should be enriched or reorganized to address the following research questions: (1) the reasons and mechanisms behind the significance of k-hop starved nodes in training a GNN through semi-supervised learning (i.e., why they are pivotal nodes), and (2) a comprehensive evaluation of the advantages and disadvantages of selecting k=1 to define the residual bipartite graph between k-hop starved nodes and labeled nodes, emphasizing how the benefits outweigh any drawbacks. Addressing these questions would enhance the paper's contributions and strengthen its overall impact in the field.\n\nGiven the aforementioned issues, a major revision of the current version of the paper is recommended before acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the Reviewer for providing detailed comments. We address your concerns as below.**\n\n**W 1:  Graph size**. \nWe would like to clarify that there is no direct relationship between improvement and graph size. We kindly remind the Reviewer that our method aims to eliminate starved nodes so as to utilize the missed supervision for better LGI. That means the improvement is directly related to the starved nodes, not the graph size. Besides, the number of starved nodes does not depend on the graph size but on the labeling rate of nodes and the graph sparsification process. As listed in Table 1, the results also do not show more enhancements on larger graphs and less improvement on smaller graphs. For example, SLAPS_R obtains a 1.7% improvement on Citeseer120 (nodes: 3,327, labeling rate: 3.61%) while only getting a 0.65% improvement on ogbn-arxiv (nodes: 169,343, labeling rate: 53.70%). Therefore, we think that exploring the relationship between improvement and graph size may not be sensible.\n\n**W 2: Generation of residual matrix**. The generation of matrix $B$ can be seen in Line 195-203, Sec 3.2. In fact, we do not generate $B$ directly. Instead, we generate a smaller matrix $\\widetilde U$ first and then obtain $B$ by padding some rows and columns of zeros (see Eq. 6).  \n**Matrix $Q$**. We would like to clarify that $Q$ is not the learning target, and we do not aim to reconstruct the matrix $Q$. $Q$ is only used in Definition 4 of “CUR Matrix Decomposition”. What we really want is the matrix $U$, which helps us identify and reduce the starved nodes.  \n**Selection method**. As stated in Line 269, Sec 4, we select $\\tau$ closest labeled nodes as the supplementary adjacent points. How to measure the distances depends on what baselines we used.  \n**Probability**. We need to clarify that we do not “pick each labeled node at a probability of $\\frac{\\tau}{c}$”. Instead, we “randomly select $\\tau$ nodes from $c$ labeled nodes” for each starved node. These two statements are totally different. In Proposition 1, we state “If there are $r$ 1-hop starved nodes, then for any $j \\in CM_+$”, which means we consider the relationships between $r$ 1-hop starved nodes and one labeled node here. For any specific labeled node, say LN, if we randomly select $\\tau$ nodes from $c$ labeled nodes for a 1-hop starved node, the probability of the node LN being selected is $\\frac{\\tau}{c}$. Obviously, this is totally different from the statement “pick each labeled node...” since we only consider one labeled node here.  \n\n**W 3: Novelty**. In this paper, we identify that graph sparsification is the main cause of the SS problem, which is not explored by existing LGI methods. To address this issue, we propose to replenish the missed supervision for better LGI. Specifically, we first give a novel definition of starved nodes. Then, to identify the starved nodes, we design two simple solutions in Secs. 3.1 and 3.2 respectively. The starved nodes can be further diminished by our proposed regularization graphs. However, there still exists a potential issue we called weight contribution rate decay in Sec 3.3. That’s why we provide two modeling choices: M_U and M_R.  \n**Reason**. k-hop starved noses are pivotal since we can tackle the SS problem directly by eliminating these nodes. In the SS problem, a number of edge weights are learned without any semantic supervision, which leads to poor generalization because the under-trained weights are used for the predictions of testing samples. If we eliminate the starved nodes, the missed supervision can be replenished to guide the learning and updating of these weights.  \n**Definition of residual graph**. In fact, we can set any value for k to define residual graphs. However, if we set k>1, there will be a potential issue. For example, if we set k=3 and eliminate the 3-hop starved nodes, 1-hop and 2-hop starved nodes may still exist. To address this, a simple solution is to set k=1 to define the residual graph. Why only setting k=1 works? According to the definition of starved nodes, we know that a k-hop starved node also qualifies as a (k-1)-hop starved node. Therefore, if we eliminate 1-hop starved nodes then all m-hop starved nodes for m>1 will be eliminated, as stated in Line 203. Due to the effectiveness and simplicity, we select k=1.\n\n**Q 1:  Definition of starved edge**. Given a k-layer GNN, if one endpoint of an edge is a k-hop starved node, the weight of this edge is learned without any semantic supervision. This is because the k-hop neighbors of this node are all unlabeled, while a k-layer GNN can only aggregate signals from k-hop neighbors. According to this analysis, “both endpoints are (k-1)-hop starved nodes” is not a correct definition for k-hop starved edges. We kindly suggest the Reviewer check Definition 2 again for the meaning of k-hop starved nodes.\n\n**Q 2:  Generalization**. This question is essentially asking why eliminating starved nodes helps the model make better predictions for testing samples. As we stated in Line 100, Sec. 2.3, for a general LGI model, a number of edge weights are learned without any semantic supervision and cannot be semantically optimal after training. As a result, the model will exhibit poor generalization since the under-trained weights are used for the predictions of testing samples. Our methods replenish the missed supervision to guide the learning and updating of the under-trained weights, thus making better predictions. Besides, structural modification is necessary for LGI methods since we have absolutely no idea what the real structure of the data looks like. A good LGI model needs to infer a good latent structure from node features. The degree distribution is not a useful indicator that affects the generalization of a model. For example, when using full parameterization as the graph generator for SLAPS [9], all nodes have the same degrees. In this case, SLAPS can still obtain good or even better performance, as shown in [9]."}, {"review_id": "5VR1Z876IF", "reviewer": "Reviewer_Qy2b", "summary": "This paper proposes a new method for the latent graph inference problem. The motivation of the new method is the existence of supervision starvation nodes caused by graph sparsification operation. To reduce the number of supervision starvation nodes, the authors propose a CUR matrix decomposition based method to add an additional adjacency matrix to the original sparse adjacency matrix with some constraints. The extensive experimental results show that the proposed idea is effective on various datasets and different base models. ", "questions": "see above", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper is well written. It is easy to follow the idea and understand the motivation and methodology design.\n2.\tAlthough the method is simple, it is effective and with sufficient analysis. \n3.\tThe performance looks promising. \n", "weaknesses": "The reason why some nodes may receive no supervision is also because of the only one-layer GNN. If there are multiple layers of GNNs, the supervision information will propagate in the graph to achieve semi-supervised training, which is the core of most of GNNs. If there are multiple layers of GNNs, is that still reasonable to define ‘supervision starvation’? In Line 155, why is deeper GNN not an optimal solution to reduce the starving nodes? From the Figure 1, we can see that increasing GNN to 4 layers could reduce the starving nodes from near 3,000 to only near 500. \n\nSince matrix A is dynamically generated from a latent graph generator, will the U or Q dynamically change as well? Are they dependent on generated A? If so, is that differentiable?  \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We really appreciate the Reviewer’s approval and constructive comments. We address your concerns as below.**\n\n**W 1**: Thank you for the constructive comments. We respond to this question in the following aspects:  \n**Reason**. The reason why some nodes may receive no supervision is not because of the only one-layer GNNs. As stated in Line 105, Sec. 2.3, *graph sparsification is the main cause of the supervision starvation problem in LGI*. In other words, graph sparsification leads to some nodes being unable to receive supervision signals. Although increasing the number of layers of GNNs can alleviate this problem to some extent, starved nodes may still exist in multilayer GNNs, as shown in Figure 1.  \n**Multilayer GNNs**. Yes, it is still reasonable to define \"supervision starvation\" if there are multiple layers of GNNs. Let us explain. To allow a k-hop starved node to receive information from labeled nodes, the GNNs need to have at least k+1 layers. However, as the number of layers increases, the number of nodes in each node’s receptive field grows exponentially, and the exponentially-growing amount of information needs to be squashed into a fixed-length vector. This will cause a so-called over-squashing issue [1], where crucial messages (supervision information here) fail to reach their distant destinations (starved nodes). That means, *as k increases, the GNNs may still fail to propagate supervision information from labeled nodes to k-hop starved nodes*. Therefore, we think it is still reasonable to define \"supervision starvation\" even if there are multiple layers of GNNs.  \n**Optimal Solution**. Using deeper GNNs is not an optimal solution to the SS problem since it will bring up new issues, as illustrated below. **First**, although increasing GNN to 4 layers reduces the number of starved nodes from near 3,000 to near 500 for the Citeseer120 dataset, the number of starved nodes still accounts for nearly $15%$. In fact, the number of starved nodes depends on several factors, including the labeling rate of nodes, the graph sparsification process, and so on. *How to select the number of layers of GNNs to reduce the starved nodes for different datasets and different LGI methods is not easy*. **Second**, *the generalization of GNNs cannot be guaranteed by simply increasing the number of layers*. Deeper GNNs typically provide inferior performance due to over-smoothing [9][20] or over-squashing issues [1]. Empirically, we test the SLAPS method on the Pubmed dataset using a different number of layers, and the corresponding accuracies can be seen in the table below. **Moreover**, *as the number of layers increases, both the number of parameters and the float point operations (FLOPs) increase*. Following the above experiments, the number of parameters and the FLOPs for 2, 4, and 8-layer models are listed in the same table below. In fact, most LGI methods only adopt 2-layer GNNs for effectiveness and efficiency. We will add more discussion on this in our final version.\n\n| **Layers** | **Accuracy** | **Parameters** | **FLOPs** |\n|:--------:|:--------------:|:--------------:|:-------------:|\n| **2**| 74.86 ± 0.79 | 645.76K | 12.70G |\n| **4**| 70.24 ± 1.58 | 680.90K | 13.39G |\n| **8**| 41.18 ± 0.88 | 751.17K | 14.76G |\n\n\n**W 2:  U and Q**.\nYes, U and Q will dynamically change as well. In fact, the values of U and Q can be obtained by different methods. For simplicity, we directly adopt the same strategy as in generating A. In this simple setting, U and Q depend on the generated A. Of course, they are both differentiable. "}, {"review_id": "E4wTZ0tIuz", "reviewer": "Reviewer_tzHX", "summary": "The paper proposes a method for latent graph inference (aka graph structure learning) based on the idea of mitigating the supervision starvation problem present when jointly learning the underlying graph structure and node representations. The paper claims that the supervision starvation problem is caused by the sparsifier operation present in many existing models in the literature. It further proposes to recover (some) starved edges to resolve the issue and shows that reducing the number of starved edges consistently improves the performance on multiple benchmarks.", "questions": "Q1: Can you elaborate more on what models M_U and M_R are referring to? My understanding so far is that M_U is referring to Equation 6 and M_R is referring to Equation 8.\n\nQ2: Can you explain what edge weights have been used on both existing and starved edges? Is this the real-valued edge from the output of the graph generator for both type of edges? \n\nQ3: What type of graph generators has been used to obtain the results in Table 1?", "limitations": "One limitation of the model is that Theorem 2 only works for k of 1 and 2. For many academic datasets, using one or two layers of GNNs is enough. However, in many real-world applications, deeper GNNs are needed to send the long-range dependencies. The paper does not provide any insights on how the idea can be extended for higher values of ks.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of latent graph inference and the supervision starvation problem present in many existing approaches are important directions that are recently gaining more and more attention. The paper proposes an approach to identify the starved edges and add them back to the graph structure that is backed up by CUR decomposition and theoretical results. The final analysis shows the proposed strategy improves the performance of state-of-the-art LGI methods. The method is shown to be more effective when supervision is less.", "weaknesses": "W1: One main weakness of the model is that the results are obtained using the average of the top five best testing performances. I understand that this setup was fixed across multiple baselines and datasets but to measure the generalization of the model, I would expect the results to be an average over testing performance of the models corresponding to the best validation performance. This is especially important as the charts in Figure 2 show a lot of instabilities in the test loss of multiple models.\n\nW2: the proposed model adds some edges to the graph structure and compares itself to the base model without those edges. I suggest adding a baseline as the base model + random edges to make sure the performance obtained is not just because there are more edges present.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We really appreciate the Reviewer’s valuable comments. We address your concerns as below.**\n\n**W 1:  Best validation performance**.\nWe thank the Reviewer for this important suggestion, and we agree that the setting you mentioned is more reasonable. *To show the results of the models corresponding to the best validation performance, we conduct more experiments on the Pubmed dataset, and the experimental results are listed below*. As we can see, our methods still improve the baselines, which further indicates their effectiveness. Besides, we think the instability phenomenon depends on the baselines we used. For GRCN, its curves are stable. Although GCN+KNN and SLPAS show some instabilities in the loss and accuracy curves, *for all the methods, the testing accuracy curves of our models lie above the baselines*, further demonstrating the effectiveness of our models.\n\nThe performance of the models corresponding to the best validation performance:\n|    |   |    |   |    |    |\n|---|---|---|---|---|---|\n| **GCN+KNN**      | 67.28 ± 0.38 | **GRCN**     | 68.62 ± 0.19 | **SLAPS**      | 74.50 ± 0.33  |\n| **GCN+KNN_U** | 72.76 ± 0.29 | **GRCN_U** | 72.30 ± 0.95 | **SLAPS_U** | 76.00 ± 0.41  |\n| **GCN+KNN_R** | 72.98 ± 0.31 | **GRCN_R** | 72.14 ± 0.79 | **SLAPS_R** | 76.86 ± 0.83  |\n\nThe performance of the models corresponding to the best testing performance:\n|    |   |    |    |   |    |\n|---|---|---|---|---|---|\n| **GCN+KNN**      | 68.66 ± 0.05 | **GRCN**     | 69.24 ± 0.20 | **SLAPS**      | 74.86 ± 0.79 |\n| **GCN+KNN_U** | 74.12 ± 0.32 | **GRCN_U** | 72.80 ± 0.99 | **SLAPS_U** | 76.74 ± 0.59 |\n| **GCN+KNN_R** | 74.78 ± 0.17 | **GRCN_R** | 72.82 ± 1.03 | **SLAPS_R** | 77.12 ± 0.77 |\n\n**W 2: Random eges**.\nThank you for this constructive suggestion. We add a baseline as the base model + random edges and conduct more experiments. The GCN+KNN and SLAPS methods are selected for experiments since they can work on all datasets. The number of random edges depends on the number of added edges in our methods. Following the experimental setting, we conduct five independent experiments and report the average accuracy along with the corresponding standard deviation as below. From the results, *we observe that adding random edges cannot guarantee performance improvement*. Therefore, we can make sure that the performance obtained by our methods is not just because there are more edges present. \n\n| **Datasets** | **ogbn-arxiv** | **Cora390** | **Cora140** | **Citeseer370** | **Citeseer120**  | **Pubmed** |\n|---|---|---|----|---|---|---|\n|**GCN+KNN**                    | 55.15 ± 0.11 | 72.82 ± 0.39 | 67.94 ± 0.29 | 73.28 ± 0.23 | 69.68 ± 0.53 | 68.66 ± 0.05 | \n|**GCN+KNN_RandEdge** | 54.31 ± 0.15 | 72.68 ± 0.13 | 67.76 ± 0.33 | 72.34 ± 0.29 | 68.86 ± 0.76 | 68.46 ± 0.16 |\n|**GCN+KNN_U (ours)**     | 55.82 ± 0.11 | 72.82 ± 0.21 | 68.18 ± 0.44 | 73.68 ± 0.10 | 69.74 ± 0.54 | 74.12 ± 0.32 |\n|**GCN+KNN_R (ours)**     | 55.86 ± 0.10 | 72.92 ± 0.28 | 68.12 ± 0.48 | 73.66 ± 0.14 | 69.90 ± 0.68 | 74.78 ± 0.17 |\n|**SLAPS**                          | 55.46 ± 0.12 | 76.62 ± 0.83 | 74.26 ± 0.53 | 74.32 ± 0.56 | 70.66 ± 0.97 | 74.86 ± 0.79 |\n|**SLAPS_RandEdge**       | 55.35 ± 0.50 | 76.68 ± 0.56 | 73.44 ± 0.67 | 74.08 ± 0.74 | 71.08 ± 0.81 | 74.10 ± 1.32 |\n|**SLAPS_U (ours)**           | 55.68 ± 0.09 | 76.94 ± 0.42 | 74.56 ± 0.21 | 74.82 ± 0.27 | 71.68 ± 0.47 | 76.74 ± 0.59 |\n|**SLAPS_R (ours)**           | 56.11 ± 0.15 | 76.82 ± 0.19 | 75.00 ± 0.49 | 74.90 ± 0.42 | 72.36 ± 0.49 | 77.12 ± 0.77 |\n\n**Q 1: M_U and M_R**.\nThank you for pointing this out. In Line 268, M_U adopts the sparse intersection matrix $\\hat U$ as the regularization, while M_Q combines $\\hat U$ and $Q$ together. That means M_U refers to Equation 6 with a sparse $U$ (not $\\widetilde U$ but $\\hat U$, to solve the weight contribution rate decay issue), and M_R refers to Equation 8 with $\\hat U$. We will make this statement more clear in the final version. \n\n**Q 2: Edge weights**. \nYes. In fact, all the latent graph inference methods use real-valued edge weights from the output of their graph generators. The edge weights are calculated based on their designed distance functions. The smaller the distance between nodes, the larger the corresponding edge weights. For fairness and simplicity, we also use real-valued weights for the starved edges. \n\n**Q 3: Graph generators**.\nIn the experiments, the type of graph generators depended on the baselines we used. For instance, in IDGL, the graph generator utilizes a weighted cosine similarity function as the metric function [4]. LCGS uses dual-normalization as the graph construction method [12]. For GRCN, we adopt a kNN graph [43]. And for SLAPS, we use the MLP-kNN generator, which corresponds to a multi-layer perceptron followed by the kNN operation [9]. \n\n**L 1: Extend for higher values of k**.\nWe thank the Reviewer for this valuable comment. As we stated in the supplementary, how to identify k-hop starved nodes for k>2 based on CUR decomposition remains an interesting direction for further investigation. Since we submitted this manuscript, we have been trying to solve this challenge. And now, we successfully come up with a solution. According to the definition of starved nodes, we know that a k-hop starved node also qualifies as a (k-1)-hop starved node. Therefore, we can iteratively identify k-hop starved nodes based on (k-1)-hop starved nodes. We use k=3 for illustration. Suppose that $rowmask$ is a $n$-dimensional mask vector where only the indexes of 2-hop starved nodes are marked as $1$ and $RM_+$ is the set of indexes of positive elements from $rowmask$. Then, we can obtain $R=A[rowmask, :]$. For each row $i$ of $R$, $V_i$ is a 3-hop starved node if, for all $j$ that satisfies $1_{\\mathbb{R}^+}(R_{ij}=1)$, $j \\in RM_+$. Based on the iterative strategy, we can solve the problem for higher values of ks. "}, {"review_id": "ma5YivhGYI", "reviewer": "Reviewer_se4r", "summary": "The paper points common LGI methods suffer from the issue of `supervision starvation`.\nIt also observes this issue is actually caused by the graph sparsification operation.\nTo address this problem, the paper proposes to restore the corrupted affinities and replenish the missed supervision.\nIt presents the `CUR matrix decomposition` to reduce the computational burden and eliminates the starved nodes by reconstructing the destroyed connections\nThe method is model-agnostic and can be seamlessly integrated into existing LGI methods.\nExtensive experiments show promising results.", "questions": "1) The $L_{reg}$ should have a clear mathematical form in paper in Equal 9.\n\n2) The authors are encouraged to discuss more about SoTA GNNs [15,23,37,40] since the proposed approach is model-agnostic.\nThe reviewer is curious why these methods were mentioned in Section1 but not compared in experiments.", "limitations": "The LGI is a common task in graph learning and all experiments are conducted on public and popular datasets.\nThe reviewer see no negative societal impact and limitations of this work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Originality.\nThe identifies graph sparsification is the main cause of the supervision starvation (SS) in LGI.\nThe paper is solid in analyzing problems with insights.\n\n2) Quality.\nThis method is supported by both theoretical (Theorem 1, 2) and experimental aspects, having strong persuasiveness.\n\n3) Clarity.\nThe paper is well written and organized.\n\n4) Significance.\nLGI is a common task graph learning. This method can be potentially applied in many situations.", "weaknesses": "1) The paper should clearly explain why using `CUR Decomposition` is more efficient.\nThe experimental results only show a higher accuracy, but does not reflect the efficiency.\nSo this advantage is not well supported.\n\n2) The section3.2 and 3.3 are not easy to follow. \nThe reviewers and potential readers may prefer a popular version.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We really appreciate that the Reviewer recognizes our contributions and originality, and gives us useful suggestions. We give our response below**.\n\n**W 1: Why CUR Decomposition is more efficient**.\nThank you for this important comment. As stated in Lines 48-53, Sec. 1, when we say “more efficient”, we mean that using CUR Decomposition (the method proposed in Sec. 3.2) to identify the starved nodes is more efficient in comparison with the method based on the k-th power of a given adjacency matrix (the method proposed in Sec. 3.1). To support this point, we conduct more experiments to compare the time performance of these two methods. The experimental results on running time are listed below. As we can see, using CUR Decomposition is more efficient than the method based on the k-th power of the adjacency matrix, especially on the larger Pubmed dataset.\n\n| **Datasets** | **Cora140** | **Cora390** | **Citeseer120** | **Citeseer370** | **Pubmed** |\n|-----------|--------------|------------|---------------|--------------|----------------|\n| **k-th power of adjacency matrix**   |     1.10      |     1.05       |      1.65         |      1.67         |    296.81   |\n| **CUR Decomposition**                   |     0.21      |     0.22       |      0.35         |      0.36         |      11.68   |\n\n**W 2: Revise sections 3.2 and 3.3**. \nWe thank the Reviewer for pointing this out. To better illustrate Theorem 2, we provide a simple example in the supplementary material. In addition, we will double polish these sections to make them easy to follow.\n\n**Q 1: Clear form of L_reg**.\nThank you for this helpful suggestion. As stated in Sec. 3.4, different LGI methods adopt different graph regularization loss $L_{reg}$. For example, IDGL adopts the following Dirichlet energy as the graph regularization loss [4]:\n$$L_{reg} = \\frac{1}{2n^2} \\sum_{i,j}A_{ij}||x_i-x_j||^2 = \\frac{1}{n^2} tr(X^TLX).$$\nSLAPS designs the following denoising autoencoder loss as the graph regularization loss [9]:\n$$L_{reg} = F(X_{idx}, GNN_{DAE}(\\widetilde X, A; \\theta_{GNN_{DAE}})_{idx}).$$\nWe will add clear mathematical forms for these different regularization losses and give more discussion in the final version.\n\n**Q 2: Discuss more about SOTA GNNs**.\nWe thank the Reviewer for this comment. We think [15][23] cannot be regarded as latent graph inference methods since they do not infer latent graphs solely based on the node features. More specifically, [15] requires a prior graph as the input and then modifies the prior graph structure based on the sparsity and low-rank assumptions. The main goal of this method is to tackle the adversarial attack problem rather than infer a good latent graph from scratch. [23] aims to solve the graph comparison problem based on graph kernels and graph neural networks. This method also does not involve the inference of latent graphs. Besides, [37] proposes a robust similarity measure based on the B-Attention mechanism for multiple clustering and ReID tasks, and [40] designs a Transformer model that scales all-pair message passing to large node classification graphs. These two methods do not involve the graph sparsification operation and thus do not encounter the supervision starvation problem. In summary, these methods [15, 23, 37, 40] are different from the latent graph inference methods used in our experiments. We will discuss more about these methods in the final version."}, {"review_id": "wkRAC7khwT", "reviewer": "Reviewer_6cu2", "summary": "The authors figure out that the graph sparsification operation results in the supervision starvation problem in latent graph inference (LGI). They propose to identify k-hop starved nodes and diminish the starved nodes by incorporating a regularization adjacency matrix into the initial one. They further reduce the computational cost by using CUR matrix decomposition and tackle the weight contribution rate decay problem via some simple strategies. The effectiveness of the proposed method is validated on well-known benchmarks.\n\nUpdate after rebuttal:\nThe authors have addressed my concern through the rebuttal. The score remains unchanged.", "questions": "In Eq. (4), the refined matrix $\\widetilde{\\mathbf{A}}$ becomes a weighted adjacency matrix when the positive parameter $\\alpha \\neq 1$. Will tuning $\\alpha$ help with methods developed for unweighted graphs?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. This paper is well-written and easy to follow.\n2. This paper identifies the supervision starvation problem for LGI.\n3. The proposed method is well-motivated and theoretically justified.\n4. The proposed method is model-agnostic and can be seamlessly integrated into various LGI models.\n5. The empirical results are significant on benchmarks.", "weaknesses": "From the analysis in Section 4.2, the proposed method may be sensitive to the hyper-paramters $\\tau$ and $\\alpha$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We really appreciate that the Reviewer identifies our contributions and provides constructive comments. We address your concerns as below**.\n\n**W 1:  Parameter sensitivity**. \nThank you for this valuable comment. In Sec. 4.2, we discussed how $\\tau$ and $\\alpha$ affect performance. In our method, $\\tau$ determines the number of labeled nodes that will be connected by each starved node, and $\\alpha$ balances the contribution between the initial adjacency matrix and the regularization one. As we can see from Table 3, our proposed method is not very sensitive to $\\tau$. For different baselines, our method can obtain the best performance when $\\tau$ belongs to $\\lbrace 25, 30 \\rbrace$. Therefore, we can set the same $\\tau$ for different baselines. From Table 4, we found that the performance is relatively sensitive to $\\alpha$. In fact, this is because the value of $\\alpha$ depends more on the baseline we used. For GCN+KNN, a larger $\\alpha$ leads to better performance. The potential reason is that the pre-constructed graph in GCN+KNN cannot be optimized. Therefore, enlarging $\\alpha$ will make the regularization graph contribute more to the final loss and achieve more improvement. For GRCN and SLAPS, since the initial graph is revised by node embeddings or updated by self-supervision signals, a moderate value of $\\alpha$ needs to be set to achieve a balance between the initial graph and the regularization one. We will add more discussion on this point in the final version.\n\n**Q 1:  Unweighted graphs**.\nThank you for asking this constructive question. In fact, all the latent graph inference methods generate weighted graphs with real-valued edge weights (the matrix $A$ is real-valued) from their graph generators. Therefore, $\\widetilde A$ is always a weighted adjacency matrix, no matter how we set the value of $\\alpha$. The values of edge weights are basically calculated based on different distance functions designed by different baselines. Typically, the smaller the distance between nodes, the larger the corresponding edge weights. To test whether turning $\\alpha$ helps for unweighted graphs, we use SLAPS as an example to conduct more experiments. Specifically, we change the original graph generator of SLPAS to generate an unweighted graph and test its performance on the Pubmed dataset. Then, we tune the value of $\\alpha$ and test the corresponding performance of the SLPAS_U and SLAPS_R methods. The experimental results are listed below. As we can see, for unweighted graphs, our method can still improve the baseline of SLPAS. However, the performance improvement is not sensitive to the value of $\\alpha$ since the learned graphs are unweighted.\n\n| **$\\alpha$** | **baseline(0)** | **0.01** | **0.1** | **1.0** | **10** | **50** | **100** |\n|-------|-------------|------|---------|------|----|----|-----|\n| **SLAPS_U** | 66.02 ± 1.47 | 68.26 ± 1.23 | 68.68 ± 1.04 | 68.72 ± 1.30 | 68.72 ± 1.30 | 68.72 ± 1.30 | 68.72 ± 1.30 | \n| **SLAPS_R** | 66.02 ± 1.47 | 68.28 ± 1.20 | 68.34 ± 0.85 | 68.64 ± 1.21 | 68.64 ± 1.21 | 68.64 ± 1.21 | 68.64 ± 1.21 | "}]

Author rebuttal:

Meta-review: After discussions with the authors, all five reviews ultimately leaned on the side of acceptance, although two of the five reviewers consired the work only weakly or borderline acceptable. 

Several aspects of the work were appreciated:

+ The problem of optimizing the neighborhood aggregation structure in graph neural networks was considered important (Qcor,tzHX,se4r).

+ The supervision starvation problem was considered an important direction (tzHx,6cu2).

+ The method was considered well-motivated and its model-agnostic nature was appreciated (6cu2)

+ The method was considered effective (Qy2b,tzHX) with promising performance (Qy2b,6cu2)

+ The analysis was considered solid (se4r) and sufficient (Qy2b)

+ The theoretical support was appreciated (se4r,6cu2)

+ The paper was considered well written by some reviewers (Qy2b,se4r,6cu2)

However, multiple concerns were also raised:

- The performance improvement was considered only moderate (Qcor) and more investigation of relationship to graph size and improvements for small graphs were desired (Qcor)

- The paper was considered to lack theoretical and technical novelty (Qcor)

- Better theoretical justification of some modeling choices and their sensitivity was desired (Qcor)

- Using average of top-5 testing performances (not testing performance of models having top validation performance) was considered problematic (tzHX)

- Comparison to state of the art GNNs was desired (se4r). Authors provided some results in a rebuttal.

- Comparing only to a base model without any added edges was considered problematic, and comparison to make sure performance is not just due to more edges was desired (tzHX). Authors provided some new results on this in a rebuttal.

- Lack of clarity in some technical details was criticized (Qcor), and some sections were considered hard to follow (se4r)

- Some technical questions regarding reasonability of supervision starvation and its relationship to semisupervised learning, especially in multi-layer GNNs, remained (Gq2b)

- There was concern about sensitivity to hyperparameters and performance on unweighted graphs (6cu2). Authors provided some discussion and results in a rebuttal.

- More explanation of efficiency improvements was desired (Se4r). Authors provided some additional results in a rebuttal.
Despite discussion with authors, concerns regarding generalization (Qcor), effect of graph size (Qcor), reasonability of the supervision starvation concept (Qy2b), comparison to state of the art GNNs (se4r), and some technical details (Qcor) seemed to partly remain.

Overall, although some concerns still remain, it seems there may be enough merits to the work that it could be presented at NeurIPS.
Decision: Accept (poster)