Why Propagate Alone? Parallel Use of Labels and Features on Graphs
Authors: Yangkun Wang
Jiarui Jin
Weinan Zhang
Yang Yongyi
Jiuhai Chen
Quan Gan
Yong Yu
Zheng Zhang
Zengfeng Huang
David Wipf
Venue: ICLR 2022 Poster (2022)

Abstract: One of the challenges of graph-based semi-supervised learning over ordinary supervised learning for classification tasks lies in label utilization.  The direct use of ground-truth labels in graphs for training purposes can result in a parametric model learning trivial degenerate solutions (e.g., an identity mapping from input to output).  In addressing this issue, a label trick has recently been proposed in the literature and applied to a wide range of graph neural network (GNN) architectures, achieving state-of-the-art results on various datasets.  The essential idea is to randomly split the observed labels on the graph and use a fraction of them as input to the model (along with original node features), and predict the remaining fraction.  Despite its success in enabling GNNs to propagate features and labels simultaneously, this approach has never been analyzed from a theoretical perspective, nor fully explored across certain natural use cases.  In this paper, we demonstrate that under suitable settings, this stochastic trick can be reduced to a more interpretable deterministic form, allowing us to better explain its behavior, including an emergent regularization effect, and motivate broader application scenarios.  Our experimental results corroborate these analyses while also demonstrating improved node classification performance applying the label trick in new domains.

Published as a conference paper at ICLR 2022
WHY PROPAGATE ALONE? PARALLEL USE OF LABELS AND FEATURES ON GRAPHS
Yangkun Wang", " .Jiaru Jin't, Weinan Zhang', Yongyi Yang" Jiuhai Chen Quan Gan', Yong Yu', Zheng Zhang', Zengfeng Huang', David Wipf 'Shanghai Jiao Tong University, Fuudn University, University of Maryland, 4 *Amazon daviwipf amazon. com
ABSTRACT
Graph neural networks (GNNs) and label propagation represent two interrelated modeling strategies designed to exploit graph structure in tasks such as node prop- erty prediction. The former is typically based on stacked message- nessage-passing layers that share neighborhood information to transform node features into predictive em- beddings. In contrast, the latter involves spreading label information to unlabeled nodes via a parameter-frre diffusion process, but operates independently of the node features. Given then that the material difference is merely whether features or labels are smoothed across the graph, it is natural to consider combinations of the two for improving performance. In this regard, we have recently proposed to use a randomly -eleeee portion of the training labels as GNN inputs, concatenated with the original node features for making predictions on the remaining labels. This so-called label trick accommodates the parallel use of features and labels, and is foundational many of the top-ranking submissions on the Open Graph Benchmark (OGB) leaderboard. And yet despite its wide-spread adoption, thus far there has been little attempt to carefully unpack exactly what statistical properties the label trick introduces into the training pipeline, intended or otherwise. To this end, we prove that under certain simplifying assumptions, the stochastic label trick can be reduced to interpretable, deterministic training objective composed of two factors. The first is data- fata-fitting term that naturally resolves potential label leakage issues, while the second serves regularization factor conditioned on graph structure that adapts to graph size and connectivity. Later, we leverage this perspective motivate broader range of label trick use cases, and provide experiments to verify the efficacy of these extensions.
INTRODUCTION
Node property prediction is ubiquitous task involving graph data with node features and/or labels, with wide range of instantiations across real-world scenarios such as node classification (Velickovic al., 2018) and link prediction (Zhang & Chen, 2018), while also empowering graph classification (Gilmer et al., 2017), etc. Different from conventional machine learning problems where there is typically no explicit non-iid structure among samples, nodes are connected by pre-specified edges, and a natural assumption is that labels and features vary smoothly over the graph. This smoothing assumption has inspired two interrelated lines of research: First, graph neural networks (GNNs) (Kipf & Welling, 2017; Hamilton et al., 2017; Li et al., 2018; Xu et al., 2018; Liao et al., 2019; Xu et al., 2019) leverage a parameterized message passing strategy to convert the original node features into predictive embeddings that reflect the features of neighboring nodes. However, this approach does not directly utilize existing label information beyond their influence on model parameters through training. Second, label propagation algorithms (LPA) (Zhu, 2005; Zhou et al., 2003; Zhang & Lee, 2006; Wang & Zhang, 2006; Karasuyama & Mamitsuka, 2013; Gong et al., 2017; Liu et al., 2019) spread label information via graph diffusion to make predictions, but cannot exploit node features.
As GNNs follow a similar propagation mechanism as the label propagation algorithm, the principal difference being whether features labels are smoothed across the graph, it is natural to consider combinations of the two for improving performance. Examples motivated by this intuition, at least to varying degrees, include APPNP (Klicpera al., 2019), Correct and Smooth (C&S) (Huang et al.,
Work done during internship at Amazon Web Services Shanghai AT Lab.

---

Published as a conference paper at ICLR 2022
2021), GCN-LPA (Wang & Leskovec, 2020), and TPN (Liu et al., 2019). While often effective, these methods are not all end-to-end trainable and easily paired with arbitrary GNN architectures. And in a related fashion Jia & Benson (2021) introduce elegant generative framework that unifies LPA and GNNs, although the parallel propagation of both features and labels is not explicitly considered.
Among these various combination strategies, our previously proposed label trick (Wang al., 2021) has enjoyed widespread success in facilitating the parallel use of node features and labels via a stochastic label splitting technique. In brief, the basic idea is use a randomly-selected portion of the training labels as GNN inputs, concatenated with the original node features for making predictions on the remaining labels during each mini-batch. The ubiquity of this simple label trick evidenced by its adoption across numerous GNN architectures and graph benchmarks (Sun & Wu, 2020; Kong et al., 2020; Shi et al., 2021; Li et al., 2021). And with respect to practical performance, this technique is foundational to many of the top-ranking submissions on the Open Graph Benchmark (OGB) leaderboard (Hu et al., 2020). For example, at the time of this submission, the top 10 results spanning multiple research teams all rely on the label trick, as do the top results from the recent KDDCUP 2021 I Large-Scale Challenge MAG240M-LSC (Hu et al., 2021).
And yet despite its far-reaching adoption, thus far the label trick has been motivated primarily as training heuristic without a strong theoretical foundation. Moreover, many aspects of its underlying operational behavior have not been explored, with non- non-trivial open questions remaining. For example, while originally motivated from a stochastic perspective, is the label trick reducible to a more transparent deterministic form that is amenable to interpretation and analysis? Similarly, are there any indirect regularization effects with desirable (or possibly undesirable) downstream consequences? And how do the implicit predictions applied by the model to test nodes during the stochastic training process compare with the actual deterministic predictions used during inference? If there is a discrepancy, then the generalization ability of the model could be compromised. And finally, are there natural use cases for the label trick that have so far flown under the radar and been missed? We take a step towards answering these questions via the following two primary contributions:
We prove that in certain restricted settings, the original stochastic label trick can be reduced to an interpretable, deterministic training objective composed of two terms: (1) data tata-fitting term that naturally resolves potential label leakage issues and maintains consistent predictions during training and inference. and (2) regularization factor conditioned graph structure that adapts to graph size and connectivity. Furthermore, complementary experiments applying the label trick broader class of graph neural network models corroborate that similar effects exists in more practical real-world settings, consistent with our theoretical findings.
Although in prior work the label trick has already been integrated within wide variety of GNN models, we introduce novel use-cases motivated by our analysis. This includes exploiting the label trick to: (i) train simple end-to-end variants of label propagation and C&S, and (ii) replace stochastic use cases of the label trick with more stable, deterministic analogues that are applicable GNN models with linear propagation layers such as SGC (Wu al., 2019), TWIRLS (Yang et al., 2021) and SIGN (Frasca et al., 2020). Empirical results on node classification benchmarks verify the efficacy of these simple enhancements.
Collectively, these efforts establish a more sturdy foundation for the label trick, and in doing so, help to ensure that is not underutilized.
2 BACKGROUND
Consider an undirected graph G = (V, with n = |V| nodes, the node feature matrix is denoted by X gaxd and the label matrix of the nodes denoted by Y E gax with d and e being the number of channels of features and labels, respectively. Let A be the (unweighted) adjacency matrix, D the degree matrix and S D AD- the symmetric normalized adjacency matrix. The symmetric normalized Laplacian L can then be formulated as L = I, - S. We also define a training mask
matrix as M Im 0
where w.L.o.g. we are assuming that the first m nodes, denoted Drr. form the training dataset. We use P to denote propagation matrix, where the specific P will be described in each context.
nxn
2

---

Published as a conference paper at ICLR 2022
2.1 LABEL PROPAGATION ALGORITHM
Label propagation is semi-supervise algorithm that predicts unlabeled nodes by propagating the observed labels across the edges of the graph, with the underlying smoothness assumption that two nodes connected by edge are likely to share the same label. Following Zhou et al. (2003); Yang et al. (2021), the implicit energy function of label propagation is given by
E(F) = (1 F Y or + + Xtr LF].
(I)
where F is the smoothed labels, Y = M ty Y is the label matrix of training nodes, and À E (0, 1) regularization coefficient that determines the trade-off between the two terms. The first term is fitting constraint, with the intuition that the predictions of good classifier should remain close to the initial label assignments, while the second term introduces a smoothness constraint, which favors similar predictions between neighboring nodes in the graph.
is not hard derive that the closed formed optimal solution of this energy function is given by
F" = PY, where P = (1 (I n AS) However, since the stated inverse is impractical to compute for large graphs, PY is often approximated in practice via P (1 A) > X Y From this expression, it follows that F can be estimated by the more efficient iterations (
P + (1 X) X) where F(0) = - and for each k; S smooths the training labels across the edges of the graph.
2.2 GRAPH NEURAL NETWORKS FOR PROPAGATING NODE FEATURES
In contrast to the propagation of labels across the graph, GNN models transform and propagate node features using a series of feed-forward neural network layers. Popular examples include GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton al., 2017), GAT (Velickovic et al., 2018), and GIN (Xu et al., 2019). For instance, the layer-wise propagation rule of GCN can be formulated as X (k+11) (SX (k) w(+) where (.) is an activation function such ReLU, X is the k-th layer node representations with X (0) X, and (k) a trainable weight matrix of the k-th layer. Compared with label propagation, GNNs can sometimes exhibit more powerful generalization capability via the interaction between discriminative node features and trainable weights.
2.3 COMBINING LABEL AND FEATURE PROPAGATION
While performing satisfactorily many circumstances, GNNs only indirectly incorporate ground- truth training labels via their influence on the learned model weights. But these labels are not actually used during inference, which can potentially degrade performance relative to label propagation, especially when the node features are noisy unreliable. Therefore, it is natural to consider the combination of label and feature propagation to synergistically exploit the benefits of both as has been proposed in Klicpera al. (2019); Liu et al. (2019); Wang & Leskovec (2020); Wang et al. (2021); Shi et al. )) Huang et al. (2021).
One of the most successful among these hybrid methods is previously proposed label trick (Wang et al., 2021), I), which can be conveniently retrofitted within most standard GNN architectures while facilitating the parallel propagation of labels and features in end-to-end trainable fashion. As mentioned previously, a number of top-perforning GNN pipelines have already adopted this trick, which serves establish its widespread relevance (Sun & Wu, 2020; Kong et al.. 2020; Li et al., 2021; Shi et al., 2021) and motivates our investigation of its properties herein. To this end, we formally define the label trick as follows:
Definition (label trick) The label trick is based on creating random partitions of the training data as in Drr Din UD out and Din nDout = 2, where node labels from Din are concatenated with the original features X and provided as GNN inputs (for nodes not in Din zero- sero-padding is used), while the labels from Dont serve in the traditional role as supervision. The resulting training objective then becomes
E splits
Σ IEDout
Sy: if Din.
9 otherwise for all i, the function J(X. Y sn: W) represents a message-passinge neural network with parameters W and the concate- nation of X and Yin as inputs, and e(.,.) denotes a point-wise loss function over one sample/noee. At inference time, we then use the deterministic predictor f[X, tri W]g for all test nodes & Der.
where Y E IR is defined row-wise Vin.s
3

---

Published as a conference paper at ICLR 2022
3 RELIABLE RANDOMNESS THOUGH THE LABEL TRICK
Despite its widespread adoption, the label trick has thus far been motivated as merely training heuristic without formal justification. To address this issue, we will now attempt quantify the induced regularization effect that naturally emerges when using the label trick. However, since the formal analysis of deep networks is challenging, we initially adopt the simplifying assumption that the function f from (2) is linear, analogous to the popular SGC model from Wu et al. (2019). For simplicity of exposition, in Sections 3.1 and 3.2 we will consider the case where no node features are present to isolate tabel-trick-speciffe phenomena. Later in Sections 3.3 and 3.4 we will reintroduce node features to present our general results, as well as considering nonlinear extensions.
3.1 LABEL TRICK WITHOUT NODE FEATURES
Assuming no node features X, we begin by considering the deterministic node label loss
L(W) = Σ Eyy,
(3)
LED
where [.] indicates the i-th row of matrix PY, tr W is linear predictor akin SGC, but with only the zero-padded training label matrix Yor as an input. Additionally, P here can in principle be any reasonable propagation matrix, not necessarily the one associated with the original label propagation algorithm. However, directly employing (3) for training suffers from potential label leakage issues given that a simple identity mapping suffices to achieve the minimal loss at the expense of accurate generalization to test nodes. Furthermore, there exists an inherent asymmetry between the predictions computed for training nodes, where the corresponding labels are also used as inputs to the model, and the predictions for testing nodes where no labels are available.
At a conceptual level, these issues can be resolved by the label trick, which case we introduce random splits of Dir and modify (3) to
L(W)= splita
E
Σ EVy: PY in Wl.]
())
IED
For each random split, the resulting predictor only includes the label information of D (through Y sn). and thus there is no unresolved label leakage issue when predicting the labels of Dout- In
practice, we typically sample the splits by assigning given node to Din. with some probability (0, 1); otherwise the node is set to Dout- It then follows that [.. = a/Dr, and EE| Y = a aYtr.
3.2 SELF-EXCLUDED SIMPLIFICAION OF THE LABEL TRICK
Because there exists an exponential number of different possible random splits, for analysis purposes (with later practical benefits as well) first consider simplified one-versus-all case whereby we enforce that |Douel = across all random splits, with each node landing with equal probability in Dout. In this situation, the objective function from (4) can be re-expressed more transparently without any expectation as
L(W)- = E splits
Σ (y
[PY sn W1.]
Σ DE
fy: [P(Y - Y.)Wl.)
spicits
iEDout
(5)
Eyy [P-C)Y,,,11)
Derl
iED
where Y; represents a matrix that shares the i-th row of Y and pads the rest with zeros, and C diag(P) P). This then motivates the revised predictor given by
f(Y (): (P-
(6)
Remark From this expression we observe the intuitive role that C plays blocking the direct puthway between each truining node input label to the output predicted label for that same node. In this way the predictor propagates the labels of each training node excluding üself,, and for both training and testing nodes alike, the predicted label of a node is only a function of other node labels. This resolves the asymmetry mentioned previously with respect to the predictions from (3).
Remark 2 It is generally desirable that candidate model produces the same predictions test nodes during training and inference to better ensure proper generalization. Fortunately, this is in fact the case when applying (6), which on test nodes makes the same predictions as label propagation. To see this, note that M, te (P- C)Y,,, . ,, te- where Mtc = I, Mrr tr is the diagonal mask matrix of test nodes and PY tr is the original label propagation predictor.
4

---

Published as a conference paper at ICLR 2022
Although ultimately (6) will serve as useful analysis tool below, it is also possible to adopt this predictor in certain practical settings. In this regard, C can be easily computed with the same computational complexity is needed approximate P as discussed in Section 2.1 (and for alternative propagation operators that are available explicitly, e.g., the normalized adjacency matrix, C' is directly available).
3.3 FULL EXECUTION OF THE LABEL TRICK AS A REGULARIZER
We are now positioned to extend the self-excluded simplification of the label trick to full execution with arbitrary random sampling, as well as later, the reintroduction of node features. For this purpose,
we first define Y out = Y tr Y in. and also rescale by a factor of 1/a to produce in = Y in a The latter allows us to maintain consistent mean and variance of the predictor across different sampling probabilities.
Assuming square enror (MSE) loss computed for each node via [(y. 9) 11 -2112 (later we consider categorical cross-entropy). our overall objective is to minimize
((W)
E spists
Σ
Ely.. [PY in wl.]
E
| out - - PY in W
(7)
splits
iED
where M out is a diagonal mask matrix defined such that out = Mout Y Y tr Y and the random splits follow a node-wise Bernoulli distribution with parameter as discussed previously. We then have the following:
Theorem Define r (diag( p" P) - -C= tr. Then the label trick loss from (7) satisfies
E [IY oot Mon PY in WIE = || (,,(P- W + - a [
I-
splits
(8)
Note that (diag(P"P)) P) C) is positive semi cemi-definite diagonal matrix, and hence its real square root will always exist. Furthermore, we can extend this analysis to include node features by incorporating the SGC-like linear predictor PXW, W. such that Theorem can then naturally be generalized as follows:
Corollary Under the same conditions Theorem 1, we add the node feature term PXW to the label-based predictor from (7), we have that
1
[IX out - M out PXW. M Mot PÝ W 21?
E
1 - a splits
M., (P- CJY W 1 + 1-
= Y tr - M,
TW 11
The details of the proofs of Theorem 1 and Corollary are provided in Appendix B.1. This then effectively leads to the more general, feature and label aware predictor
J(X,Y, Ytr:)) PXW, + +(P (P- CCY W
(10)
where W = (W., Wy). These theoretical results reveal a number of interesting properties regarding how the label trick behaves, which we summarize as follows:
Remark 3 Although the original loss involves an expectation over random data splits that is some- what difficult to interpret, based on (9), the label trick can be interpreted as inducing a deterministic objective composed of two terms: (i) The error accrued when combining the original node features with the self-exclude label propagation predictor from (6) to mitigate label leakage, and (ii An additional praph-depende
regularization factor the model weights associated with the labels that depends on a (more on this below). We can also easily verify from (10) that the model applies the same prediction to test nodes during both training and inference, consistent with Remark 2.
Remark 4 If the graph has edges, then there is chance for overfitting to labels and PTPP
(diag(P P) - cT) connected graph, the value T can be significantly larger, which can potentially provide beneficial regularization effect. Additionally, given that I also grows larger with graph size (assuming edges grow as well), [[TW, yl scales proportionately with the data fitting term, which is generally expected to increase linearly with the number of nodes. Hence (9) is naturally balanced problem size.
= O shuts off the superfluous regularization. In contrast, for fully
5

---

Published as a conference paper at ICLR 2022
Remark 5 The splitring probability in (9) controls the regularization strength. Specifically, when a tends to zero. fewer labels are used as input to predict a large number of output labels, which may be less reliable, and corresponds with adding larger regularization effect. Additionally, it means placing more emphasis on the original node features and downplaying the importance of the labels as input in (9), which explains the addition of a penalty on W, Conversely, when tends to one, more labels are used as input to predict the output and the model approaches the deterministic self-excluded 1, the loss mimics one random term from
label trick. Specifically, for random splits where (Pout] the self-excluded label trick summation, while for the splits when |Dout]= = O, the contribution to the expectation zero and therefore does not inftuence the loss. Splits with (Doua) > will have very low probubility, so this situation naturally corresponds with canceling out the regularization term. Later Section 3.4 we will extend these observations to general nonlinear models.
We now turn to the categorical cross cross-entropy loss, which is more commonly applied to node classi- could with
fication problems. While we can no longer compute closed-form simplifications MSE, it is nonetheless possible to show that the resulting objective when using the original label trick is an upper bound on the analogous objective from the self-excluded label trick. More specifically, we have the following (see Appendix B.3 for the proof):
Theorem Under the same conditions as Theorem and Corollary 1, if we replace the MSE loss with categorical pross-entropy we obtain the bound
E. splite
[CED.ue (Y out; PXW, + PY in (Y,,,) W,)
CED,, (Y tr, AXW.+(P-C)) W
(11)
where CEs(s,) denotes the sum of row-wise cross-entropy of S.
3.4 NONLINEAR EXTENSIONS
When we move towards more complex GNN models with arbitrary nonlinear interactions, it is no longer feasible establish explicit, deterministic functional equivalents of the label trick for general a. However, we can still at least elucidate the situation at the two extremes where a + 0 or a + 1 alluded to in Remark 5. Regarding the former, clearly with probability approaching one, Y in will always equal zero and hence the model will default to a regular GNN, effectively involving no label information as an input. contrast, for the latter we provide the following:
Theorem 3 Let (aNN(X,X) W) denote arbitrary GNN model with concatenated inputs X and Y. and Ely, ÿ training loss such that ΣieDout E(y., faNN Y Wk.) is bounded for all D out- It then follows that
lim
1
EE splits
Σ IED
Ely JGNN[X, Yn: on [h1]]] = Σ (Vv JaNN|X,Y -Y-YY;W), W..)
a
(12)
The proof is given in Appendix B.4, This result can be viewed as a natural generalization of (5), with one minor caveat: during training will exactly match the explicit function NX Yrr; W] applied at inference time. Indeed, each faNN [X, Y tr Y;; W] will generally produce slightly different predictions for all test nodes depending on i unless faNN is linear. But in practice this is unlikely to be consequential.
no longer guarantee that the predictor implicitly applied to test nodes
4 BROADER USE CASES OF THE LABEL TRICK
Although the label trick has already been integrated within wide variety of GNN pipelines, in this section we introduce three novel use-cases motivated by our analysis.
4.1 TRAINABLE LABEL PROPAGATION
In Sections 3.1 and 3.2 we excluded the use of node features to simplify the exposition of the label trick; however, analytical points aside, the presented methodology can also be useful in and of itself for facilitating simple, trainable label propagation baseline when we choose as in Section 2.1.
The original label propagation algorithm from Zhou et al. (2003) is motivated as parameter-free. deterministic mapping from a training label set to predictions across the entire graph. However, clearly the randomized label trick from Section 3.1, or its deterministic simplification from Section

---

In contrast, with the label trick, we can equip C&S with trainable weights to further boost performance. To this end, first split the training dataset into Di, and Dout before. Then multiply Published as a conference paper at ICLR 2022
3.2 can be adopted to learn label propagation weight matrix W. The latter represents reasonable enhancement that can potentially help to compensate for interrelated class labels that may arise, especially in multi-label settings. In contrast, the original label propagation algorithm implicitly assumes that different classes are independent. Beyond this, other entry points for adding trainable weights also feasible such as node-dependent edge-dependent weights (Wang & Leskovec, 2020), nonlinear weighted mappings (Kipf' & Welling, 2017), step-wise weights for heterophily graphs (Yamaguchi et al., 2016), weights for different node types for heterogeneous graphs (Schlichtkrull et al., 2018).
4.2 DETERMINISTIC APPLICATION TO GNNS WITH LINEAR PROPAGATION LAYERS
Many prevailing GNN models follow the architecture of message passing neural networks (MPNNs). Among these are efficient variants that share node embeddings only through linear propagation layers. Representative examples include SGC (Wu et al., 2019), SIGN (Frasca et al., 2020) and TWIRLS (Yang et al., 2021). We now show how to apply the deterministic label trick algorithm introduced in Section 3.2 with the aforementioned GNN methods.
We begin with a linear SGC model. In this case, we can compute -P- er beforehand as the self-excluded label information and then train the resulting features individually without graph information, while avoiding label leakage problems. And desired, we can also concatenate with the original node features. In this way, we have an algorithm that minimizes an energy function involving both labels and input features.
Additionally, for more complex situations where the propagation layers are not at the beginning of the model, the predictor can be more complicated such as f(X, Y; W)
h1 Σ> [Pho([X, Y Y.I..) = (P (h [x, Y)) Cho ([x, Y) + Cho(( oJ)), (13)
where 1. denotes the concatenation operation, P [Po. P P...... Pk-1] 1" is the integrated prop- agation matrix, C = [diag( Po), (P1).... diag Pk-1)] DiTTT ho and hy can be arbitrary node- independent functions, typically multi- multi-layer perceptrons (MLPs).
4.3 TRAINABLE CORRECT AND SMOOTH
Correct and Smooth (C&S) (Huang et al., 2021) is a simple yet powerful method which consists of multiple stages. A prediction matrix Y is first obtained whose rows correspond with prediction from a shallow node-wise model. is subsequently modified via two post-processing steps, correct and smooth, using two propagation matrices (Pe: Ps). where typically P; (1 XI, X,5)-1, i E {c, s). For the former, we compute the difference between the ground truth and predictions the training set as E = Yrr Yir and then form É - (P..E) as the correction matrix, where 7(.) is some owwindependent scaling function. The final smoothed prediction is formed as fc&s( (Y) = (Y tr + M,e + E)). This formulation is not directly amenable to end-to-end training because of label leakage issues introduced through Ytr-
E., (P.(( in i..).. the correction matrix with respect to Y ins with a weight matrix W c We also multiply the result after smoothing with another weight matrix W., Thus the predictor under this split is
froks((Y in, Y; W) PY in + (Mie + M out) (Y (M + Moa) Ein W...
W.)
=Po((Y in + (M Moat) ) Y +
(14)
where W = (W., c, W.} and W. W.W.. The objective function for optimizing W is L(W) = splits
Σ
e(y,, frcks( in: Y; Y:W))
(15)
RED
Since this objective resolves the label leakage issue, it allows end-to-end training of C&S with gradients passing through both the neural network layers for computing Y and the C&S steps. At times, however, this approach may have disadvantages, including potential overfitting problems or inefficiencies due to computationally expensive backpropagation. Consequently, an alternative option is to preserve the two-stage training. In this situation, the base prediction in the first stage is the same as the original algorithm; however, we can nonetheless still train the C&S module as post- post-processing step, with parameters as in (14).
7

---

Published as a conference paper at ICLR 2022
Table 2. R2 on node regression tasks with GBDT base model and regular/end- to-end C&S.
Table 1. Accuracy results (%) of label propagation and trainable label propagation.
Method
Label Propagation
Trainable Label Propagation
Method
C&S
Trainable C&S
Cora-full
66,44 +: 0.93
67.40 0.96
Pubmed
83.45 = 0.63
83,52 = 0.59
House
0.797 = 0.005
0.854 = 0,005
ArXiv
67.11 = 0.00
68.42 = 0.01
County
0.625 + 0.048
0.788 + 0.015
Products
74.24 # 0.00
75.61 # 0.21
VK
0.163 # 0.011
0.172 = 0.011
Avazu
0.405 = 0.036
0,413 = 0.033
EXPERIMENTS
As mentioned previously, the effectiveness of the label trick in improving GNN performance has already been demonstrated in prior work, and therefore, our goal here is not to repeat these efforts. Instead, this section we will focus on conducting experiments that complement our analysis from Section 3 and showcase the broader application scenarios from Section 4.
The label trick can actually be implemented in two ways. The first is the one that randomly splits the training nodes, and the second is the simpler version introduced herein with the deterministic one-versus-all splitting strategy, which does not require any random sampling. To differentiate the two versions, we denote the stochastic label trick with random splits by label trick (S), and the deterministic one by label trick (D). The latter is an efficient way to approximate the former with a higher splitting probability a, which is sometimes advantageous in cases where the training process is slowed down by high a. Accordingly, we conduct experiments with both, thus supporting our analysis with comparisons involving the two versions.
We use four relatively large datasets for evaluation, namely Cora-full, Pubmed (Sen et al., 2008), ogbn-arxiv and ogbn-products (Hu et al., 2020). For Cora-full and Pubmed, we randomly split the nodes into training, validation, and test datasets with the ratio of 6:2:2 using different random seeds. For ogbn-arxiv and ogbn-products, we adopt the standard split from OGB (Hu et al., 2020). We report the average classification accuracy and standard deviation after 10 runs with different random seeds, and these are the results on the test dataset when not otherwise specified. See Appendix C for further implementation details.
5.1 TRAINABLE LABEL PROPAGATION
We first investigate the performance of applying the label trick to label propagation as introduced in (2) in the absence of features, and compare it with the original label propagation algorithm. Table 1 shows that the trainable weights applied to the label propagation algorithm can boost the performance consistently. Given the notable simplicity of label propagation, this represents a useful enhancement.
5.2 DETERMINISTIC LABEL TRICK APPLIED TO GNNS WITH LINEAR LAYERS
We also test the deterministic label trick by applying to different GNN architectures involving linear propagation layers along with (13). Due to the considerable computational effort required to produce P and C' with large propagation steps for larger graphs, we only conduct tests on the Cora-full, Pubmed and ogbn-arxiv datasets, where the results are presented in Table 3.
Table 3. Accuracy results (%) with/without label trick (D).
Method
SGC
SIGN
TWIRLS
label trick (I)
x
X
X
Cora-full
65.87 # 0.61
65.81 + 0.69
68.54 = 0.76
68.44 # 0.88
70.36 0.51
70.40 0.71
Pubmed 85.02 = 0.43
85.23 = 0.57
87.94 + 0.52
88.09 + 0.59
89.81 4 0.56
90.08 0.52
ArXiv
69.07 # 0.01
70.22 + 0.03
69.97 = 0.16
70.98 # 0.21
72.93 # 0.19
73.22 0.10
From these results we observe that on Pubmed and ogbn-arxit the deterministic label trick boosts the performance consistently on different models, while on Cora-full, it performs comparably. This is reasonable given that the training accuracy on Cora-full (not shown) is close to 100%, in which case the model does not benefit significantly from the ground-truth training labels, as the label information is already adequately embedded in the model.
5.3 EFFECT OF SPLITTING PROBABILITY
In terms of the effect of the splitting probability a, we compare the accuracy results of a linear model and a three-layer GCN agbn-arxiv as shown in Figure 1. For the linear model, a serves
8

---

Published as a conference paper at ICLR 2022
74.1
73.0
72.5
73.8
labe trick (5)
Acturay (9)
Accunacy
22.0
labe trick (D)
78.6
label trick (5)
w/o trick
71.5
73.4
71.0
73.2
0.0
0.2
0.4
Figure/ 1. Validation accuracy varying a. Left: linear propagation of features & labels, Right: GCN.
regularization coefficient. More specifically, when tends to zero, the model converges to the one without the label trick, while when a tends to one, it converges to the case with the self-excluded label trick. For the the nonlinear GCN, has similar effect predicted by theory for the linear models. As a decreases, the model converges to that without the label trick. Moreover, larger a is preferable for linear models that may not require strong regularization like complex GNNs.
5.4 TRAINABLE CORRECT AND SMOOTH
We also verify the effectiveness of approach when applied to Correct and Smooth (C&S), as described in Section 4.3. Due to the significant impact of end-to-end training on the model, is not suitable for direct comparison with vanilla C&S for a natural ablation. Therefore, in this experiment, we train the C&S as post-processing steps. In Table 4, we report the test and validation accuracy, showing that our method outperforms the vanilla C&S on Cora-full and Pubmed. And for ogbn-arxiv and ogbn- bebn-ppodduts, the trainable C&S performs better in terms of validation accuracy while comparable vanilla C&S terms of test accuracy.
In principle, C&S can be applied to any base predictor model. To accommodate tabular node features, we choose use gradient boosted decision trees (GBDT), which can be trained end-to-end using methods such as Chen et al. (2022); Ivanov & Prokhorenkova (2021) combined with the label trick to avoid data leakage issues as we have discussed. For evaluation, we adopt the four tabular node regression data sets from Ivanov & Prokhorenkova (2021) and train using the approach from Chen et al. (2022). Results are shown in Table 2, where the label trick can significantly improve performance.
Table 4. Test and validation accuracy (%) of C&S and trainable C&S with MLP base predictor. Validation accuracy reported in parentheses.
Method
MLP
MLP+C&S
MLP+Trainable C&S
Cora-full
60.12 + 0.29 (61.09 0.39)
66.95 1.46 (68.26 1.24)
67.89 1.37 (69.09 + 1.25)
Pubmed
88.72 = 0.34 (89.25 +.266
89. 99.12 : 0.27 00.17)
89.76 (89.62 = 0.18)
ArXiv
71.48 = 0.15 (72.95 0.05)
73.05 0.35 (74.01 0.17)
73.03 0.18 (74.44 # 0.08)
Products
67.60 = 0.15 (87.07 0.05)
83.16 0.13 990.0
83.10 (91.99 # 0.07)
CONCLUSION
In this work we closely examine from theoretical prospective our recently proposed label trick, which enables the parallel propagation of labels and features and benefits various SOTA GNN architectures, and yet has thus far not be subject to rigorous analysis. In filling up this gap, we first introduce deterministic self-exeluded simplification of the label trick, and then prove that the full stochastic version can be regarded as introducing a regularization effect on the self-excluded label weights. Beyond this, we also discuss broader applications of the label trick with respect to: (i) Facilitating the introduction of trainable weights within graph-based methods that were previously either parameter-fie (c.g., label propagation) or not end-to-end (e.g.. C&S), and (ii) Eliminating the effects of randomness by incorporating self-excluded propagation within GNNs composed of linear propagation layers. We verify these applications and evaluate the performance gains against existing approaches multiple benchmark datasets.

---

Published as a conference paper at ICLR 2022
Acknowledgments.. The Shanghai Jiao Tong University Team is supported by Shanghai Municipal Science and Technology Major Project (201SHZZZZX1022 and National Natural Science Founda- tion of China (62076161, 62177033). We would also like thank Wu Wen Jun Honorary Doctoral Scholarship from Al Institute, Shanghai Jiao Tong University.
REFERENCES
Jiuhai Chen, Jonas Mueller, Vassilis N. loannidis, Soji Adeshina, Yangkun Wang, Tom Goldstein, and David Wipf. Convergent boosted smoothing for modeling graphdata with tabular node features. ICLR, 2022.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198, 2020.
2,7
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Chen Gong, Dacheng Tao, Wei Liu, Liu Liu, and Jie Yang. Label propagation via teaching-to-learn and learning-to-teach. IEEE Trans. Neural Networks Learn. Syst., 28(6): 2017.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30, 2017. 1,3
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems 33, 2020. 2, 8
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprint 10t::20033094330 2021. 2
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label prop- agation and simple models out-performs graph neural networks. In 9th International Conference on Learning Representations, 2021. 3.
Sergei Ivanov and Liudmila Prokhorenkova. Boost then convolve: Gradient boosting meets graph neural networks. In 9th International Conference Learning Representations, 2021. 9
Junteng Jia and Austin R Benson. A unifying generative model for graph learning algorithms: Label propagation, graph convolutions, and combinations. arXiv preprint arXiv:2 10/00330, 2021. 2
Masayuki Karasuyama and Hiroshi Mamitsuka. Manifold-based similarity adaptation for label propagation. In Advances in Neural Information Processing Systems 26, 2013.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, 2017. 1, 3, 19
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, 2019, 3,
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Flag: Adversarial data augmentation for graph neural networks. arXiv preprint arXiv:2010.09891, 2020. 2,
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In Proceedings of the 38th International Conference on Machine Learning, 2021. 3.3
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for supe-super learning. In Proceedings of the Second AAAI Conference on Artificial Intelligence, 2018.
10

---

Published as a conference paper at ICLR 2022
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In 7th International Conference on Learning Representations, 2019.
Yanbin Liu, Juho Lee, Minseop Park, Saehoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang. Learning to propagate labels: Transductive propagation network for few-shot learning. In 7th International Conference Learning Representations, 2019, 1,
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modcling relational data with graph convolutional networks. In The Semantic Web 15th Internationnal Conference, 2018. 7
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Ran Radd Collective classification in network data. Al Mag., 29(3):93-106, 2008. 8
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for sunervuper classification. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021. 2,
Chuxiong Sun and Guoshi Wu. Adaptive graph diffusion networks with hop-wise attention. arXiv preprint (rXX::20/2./5024, 2020. 2,3
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, In 6th International Conference on Learning Representations. 2018. 1,
Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. In Proceedings of the Twenty-Thine International Conference on Machine Learning, 2006.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propaga- tion. arXiv preprint arXiv:2002.06755, 2020. 2, 3,7
Yangkun Wang, Jiarui Jin, Weinan Zhang. Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint arXiv:2 103. 13355, 2021. 2, 3
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, 2019. 2, 2,4,
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, 2018. 1
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, 2019. 1,3
Yuto Yamaguchi, Christos Faloutsos, and Hiroyuki Kitagawa. CAMLP: confidence-award aware modulated label propagation. In Proceedings of the 2016 SIAM International Conference on Data Mining, pp.
513-521, 2016.7 7
Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. In Proceedings of the 38th International Conference on Machine Learning, 2021. 2, 3, 7, 19
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems 31, 2018.
Xinhua Zhang and Wee Sun Lee. Hyperparameter learning for graph based semi-supervised learning algorithms. In Advances in Neural Information Processing Systems 19, 2006.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances Neural Information Processing Systems 16, 2003. 3, 6
Xiaojin Jerry Zhu. Semi-super learning literature survey. In University of Wisconsin, Madison, Technical Report, 2005.
11

---

Published as a conference paper at ICLR 2022
A ADDITIONAL EXPERIMENTS
A.1 EFFECT OF TRAINING ACCURACY
Intuitively, the label trick introduces more information about the ground-trune trrnndd-rtthhha labels in the training set to the model. In this experiment, investigate the role of training accuracy in training with the label trick. We produce two new datasets by projecting the input features on Cora-full and Pubmed to 32 dimensions (i.e., Cora-full-32d and Pubmed-32d, respectively) via PCA. This is much more challenging task because less feature information is available for prediction. We train SGC, SIGN and TWIRLS under the same settings as in Table 3. The following tables show the test and training accuracy these datasets respectively, as well as results using original features as in Table 3. For each comparison, we use the same set of model hyperparameters with/without label trick, based on the best performance without label trick.
Table 5. Test accuracy (%) with/without label trick (D).
Method
SGC
SIGN
TWIRLS
label trick (D)
X
/
X
Cora-full-32d
55.63 # 0.53
62.37 = 0.87
55.10
62.05 # 0.47
58.57 0.48
61.74 + 0.46
Pubmed-32d
83.15 = 0,41
84.33 + 0.68
84.75 = 0.37
85.72 # 0.84
84.94 a 0.37
87.60 0.44
Cora-full
65,87 # 0.61
65.81 # 0.69
68.54 0.76
68.44 # 0.88
70.36 0.51
70.40 = 0.71
Pubmed
85.02 0.43
85.23 = 0.57
87.94
88.09
0.59
8
90.08
0.52
ArXiv
69.07 0.01
70.22 = 0.03
69.97 = 0.16
70.98 0.21
72.93 0.19
73.22 0.10
Table 6. Training accuracy (%) with/without label trick (D), Each comparison shares the model hyperparameters.
Method
SGC
SIGN
TWIRLS
label trick (D)
X
X
Cora-full-32d
$7.69
65.75
0.19
57.20 0.21
65.88
0.27
63.44 0.411
67.40 0.36
Pubmed-324 32d
83.43
84.74 0.17
0.19
86.05 0.19
8.22
88.43 0.26
Cora-full
95.31
97.59 # 0.12
99.78
99.99
99.95
99.76 0.05
Puhmed
8.113
85.69
= 0.23
0.12
9.17
0.30
97.48 0.28
ArXiv
71.66
74.94 + 0.01
7..26
74.94 0.08
8.19
85.08 0.12
From Tables 5 and 6, we can see that the degree to which the label trick can improve accuracy is directly related the training accuracy. When the training accuracy is near 100%, the label trick minimally benefits the model as the label information has already been adequately embedded in the model. However, when the training accuracy lower, the label trick can increase both the training and test accuracy significantly (once the variance from the dataset divisions is taken into account, please see Appendix A.2).
Moreover, for large-scale graphs it may be less likely that high accuracy or overfitting is experienced during training due to the generous number of available samples. So such cases, the label trick more likely to be effective.
A.2 EFFECT OF RANDOM DATASET DIVISION
Due to the random division of the dataset into training, validation and test dataset for Cora-full, Pubmed, and the regression datasets, the standard deviations across trials considerably higher than when using fixed splits. Consequently, for many of the results, the performance gap remains consistent across trials such that the improvement is actually still significant.
As an illustration, Table 7 presents the itemized, trial-to-tti to-iiiil results that were averaged to produce the Cora-full results presented earlier in Table 1. This reveals that the label trick consistently improves performance over different dataset splits even after careful tuning of the hyperparameters for the baseline model. This phenomena is similarly present in many of other experimental results.
12

---

Published as a conference paper at ICLR 2022
Table Trail-to-trail accuracy results (%) on Cora-full.
Trail
Label Propagation Trainable Label Propagation
63.52
67.57
2
65.77
66.03
3
64.84
66.28
4
66.00
66.23
5
68.
68.58
6
67.39
67.87
7
67.29
68.07
8
66.86
68.83
9
66.48
67.85
10
66.13
66.73
Overall
66.44 + 0.93
67.40 0.96
A.3 EFFECT OF REGULARIZATION FACTOR WITH SELF-EXCLUDED LINEAR PREDICTORS
In order to demonstrate the effect the theoretically-deet -eerived regularization factor in Theorem and Corollary 1, apply the regularizer to classification experiments involving the deterministic self-excluded linear predictors from Section 4.2. Figure 2 provides such an example using the Cora dataset and the TWIRLS linear predictor plus regularization is varied. Note that if, there is infinite penalty on the label weights which is equivalent to no labels; contrast the regularization factor is zero.
84.5
84.0
83.5
Accuracy
82.5
0.0
0.2
0.4
0.6
0.8
1.0
Figure 2.
Accuracy results varying regularization coefficient with corresponding a. When = 0. there is no actual label use.
From Figure 2 we observe that including labels plus the theoretically- regularization (with right value for a:) can indeed improve performance. This suggests that even with a classification loss (which only loosely aligns with the stated theorem/corollary assumption of MSE loss), the theory has some practical/predietive value in producing a useful regularization factor.
B PROOFS
B. PROOF OF THEOREM 1
We first define the mask matrix for input labels:
(iig(r.))
0
M sn
Bernoulli(a),
(16)
O
where a E (0, 1) is the label rate, and the mask matrix for output is defined as M out M Min Then the objective is
13

---

Published as a conference paper at ICLR 2022
L(W)
E splits
Y out
M PY in W[
E splits
Y out
- M out Mont PY in W
Y 1lt
[tr out
M Mour PY in W] + [|| Mot PY in W12]
splids
splits
a splits
2
E splits
|| out Y 1
E Ir
M out PM Y W]
eplits
|| out PM Y
a
splits
(17)
Next compute each term separately. For notational convenience, we denote the i-th row and j-th column entry of M, in by Mij.
1. For Esplits [I| M out Y er 1122), we have
E
M our Y orl
by out M oot MottYrr) vr] |tr
sptits
spiits
E eplits
|t Lrryy tr
M out (r]
E splits
[t|M out Y tY'''"
(18)
tr| E [M out Y ir Y splits
(1 a) Lr[M Y tr Y
= (1 a) tr(Y,, iy trl
= (1 - YY)l l1.
For Resplits [r ir tn
M out PM, in Y W]], since oout= = Mtr M.n. oz. we then have
E [tI M our PM Y W]]
sptits
E. [tr[ ont PM in Y, WY [r]
splits
-tr [M out PM Y WY
splits
= -tr [(M,, Mt. PM .r WY splits
(19)
tr((M,,, P [M.]] splite
M in PM Y, WY 8r.
splits
-tr((aM, PM,
E spits
A.MPM Y WY
-atr[M,, Y WYT ir
[ PM C.M..YY... WY
eplite
= =atr er W
[M PM Y., WY
sppits
Let us calculate Esptits M in PM. .n.. Since Mi, a diagonal matrix, we have
E [M in PM m = E [Ma,,; = a² Per + (a - Ct) splits
(20)
splits
where Pir = M, PM, and Ctr = diag P P..). Then we have
trl E splits
M PM, Y. WY a² tr P Y w + (a aa W].
(21)
14

---

Published as a conference paper at ICLR 2022
Therefore,
E [t| by M out PM in Y W]]
splits
= tr
- -
(22)
aaa tr (Pr. .,
3. For Esplits
[I| M out Y W [12] we have
E splits
[|| out PM Y or W
E [tr M in
p" M out M out PM in Y, W]
splits
E [t Y T in
p" M out PM in Y, W]
aplits
=trl E [
YT M P (M M PM Y cr W] ir
splits
in
(23)
=trl E [ Y M P" M PM "spiits
-tr E | Y M P M. PM, Y e W|
spliss
-r(W'Yy Y
E M p" M PM YY W.
br
spliss
tr|l"T Y
E
[ T P M PM W].
splits
Let us consider each term separately.
(a) To compute tr(WT Exptits diag( p } and then
M in
Pd M PM in Y WI. we first define Qu =
M PT PT P PM
Σ
MiMMi,PriPHy
splits
ij
sptita
m
E splits
M
Pks Pkj
(24)
p²pp" Ptr + (a a²)) diag p?.
12pp P or + (a a² (Q)h))
Therefore,
tr TT E [M. PT PM, splite
(25)
PP Y br W 1 (a a Y WI..
(b) To compute tr tr( TTT Espiits _ pT M PM, in Y W., we have that
E splits
M PT M
PM in
= E sptits
M
Ma
mm
(26)
M M Pa:P
eplits
For the diagonal entries, where = j. we have
Σ E MallPPs splits
a tnkii + (a - (a)=2)) -2) Pnai
(27)
k=1
and therefore,
diag
Mr,, in PT M., PM, = a² diag(P (2.) + (a c²)
splits
(28)
= a²Q² + (a - a Ct
15

---

Published as a conference paper at ICLR 2022
For the off-diagonal entries, where i & J. we have
Σ E MasM a² Σ splita
PurKiiPukjt ta (a + Par..iPPr..j)
(29)
and
E [ in P" M PM
spists
(30)
= [a P + (a² a²) (C Pn.
From (28) and (30), know that
E [M in P P iM] splits
(31)
3 Pe + -a" + -a-3a" 20")00 + - -C' + (.)
-a
Unfortunately because C., + Crr is not necessarily positive semi-definite, we cannot simplify the proof using the Cholesky decomposition. So instead we proceed as follows:
tr'w' Y
Y, W]
+ (a² - a diag (a (nn) (a-
=
+ +aa - a²) diag( P(rCrr))
y,
-t Y W ( - w'' diag( P Y W
+ - a²) a C + P,, W
+ +aa-3e + 2a
& C.y.
Y. + (a - a Q Y W + (a-3a- + )I Y W|) + ar) tr tr W
YT WY
+ P. Y.
(32)
Combining the three terms, get
[lI out PM in Y W E
splits
-a2-a") P W + 2a² 2 +a²)) Qur Y, W/1
aa) W Y +
W - 3 (a-332+2a²)]Ca W
(33)
The overall result L(W) is
I||Y out M PÝ in W
sptits
E M|I ont 11rl
[Ir M out PM Y W]]
spiits
splits
E
||| ond PM Y 1
a² sptits
(34)
(1 a) Y 1r 11 2(1 - a) Y (P C, W| +(1 (1- W
+ (-- - a) Q.. Y.. a) tr Pr
- ( 3+ - 20 C, W
16

---

Published as a conference paper at ICLR 2022
where Ctr (ir) and Qer diag( (0iggPP;))) p
Next compute | fr Mr C)Y,, W Since
Y -C. -IIP v. + -
(35)
we have that
or - ()
=|1Y + IPLY Jon
(36)
(n Cr + Crr Y W. - 22r (Por w.
Therefore,
1
E Y out
M Mou PY in W W [+]
a splits
= Y - 21r Y Y, W + 1
1- Q ,r
1- -r Y 1r Cr + C. 2a
2a-1 -1
+
a
a Q Y, W - Y W1.
=
Y - M (P- - - W W| +
(37)
Let U (diag( pd P) C) and r UY fr. Then we have
1
E
Y out PY in W
splits
1 1-a
= Y tr - PP- CJY W
MY, ir W/1
(38)
1-a
+|Y tr MPr WI
IUY,, ir W
1 a
|Y or - (P- C)Y, W
|
B.2 PROOF OF COROLLARY
We have that
E
Y out
Mont PXW, a M Mo in W v1
I a splits
1
E splits
||Y
M PY in W 1
1-
2 (r( P'
|| out PXW 2 M out PXW a
M oud PXW.
a
=I - (P - Cor Fr W 1-a a TW 1
+IM,, YT PXW, . 2t W ;
YI
(Prr - C
1-0
=| -VM.-M,,XHY - (Prr CC W 1
TW 1
1-a
= - PXW, - CC W w
TW y |
(39)
which proves the conclusion.
17

---

Published as a conference paper at ICLR 2022
B.3 PROOF OF THEOREM 2
We begin by noting that
E
M out PY, in W
E a splats
,, PY W
E
M in PY in y
splats
a splits
1
M P E M in Y rr W y splits
M in PM Y Wy,
splits
(40)
MY, br W. y y- (aPP aaC Cr
=11 (1-a)
-(1 W Yn
= M1 P C)Y W.
And then by Jensen's 's inequality we have
E [rossEntropy
Dout (Y Yott M out
PXW W.W + M oot PY in W g)
splats
2 CrossEntropy D... (Y Youts E
[M oud PXW. = M PY W vl)
(41)
splits
CrossEntropy (Y tr (1 a)] + - i)
Notice based on the nature of cross-entropy, i < a < 1, we have
CrossEntropy Z, 0:) 2) 2 (1 - =))oossFinrropy(, (2,
(42)
Therefore,
1
E [CrossEntropyy Doui
(Y out: PXW, x + PY, W,)
1 a splits
(43)
2 CrossEntropy D., (Y XW, + + (P ,,,,,,,))
B.4 PROOF OF THEOREM 3
Although the label trick splits are drawn randomly using an iid Bernoulli distribution to sample the elements be added either Dan or Dout, we can equivalently decompose this process into two parts. First, we draw 'Dout from binomial distribution P[[Douel] = Binom [m, 1 4-al a.). where m the number of trials and 1 a the success probability. And then we choose the elements to be assigned to Dont uniformly over the possible combinations (ppou.))
Given that when [Doutl there is no contribution the loss, we may therefore reexpress the lefthand side of (12), excluding the limit, as
Σ
Elyer SaNN Y in W]:3]
splits
iEDout
[|Doutt
1]
Σ
(Vr, [aNN[X,YY sii W[])
(44)
1-a
P[DowellPaueh
iEDout
P Dout
outl
1]
E
Σ
(yy SaNN (X, Y W[)]
1 a
P P[DeullPenc>1]
ieDaue
where it naturally follows that
E P P
Σ Ely: [ONN|X,Y Yi; W1.] :n:))]] =
ely, SONN - -
(45)
We also have that
P P|
> 1] Em (m) (1
m-i
Σ
m
m
(1 a) m-i
(46)
1 1 a
1-a
i
2=2
18

---

Published as a conference paper at ICLR 2022
and P| Dout - m(1 aaaa=1
ma m
(47)
Ox
- a
From these expressions, we then have that
lim Pi > 1] and lim 0-+1
P D = 1
171
(48)
1-a
And given the assumption that IEiEDON (VV sGNN X, in Wl:) B oo for some B, we
also have
Σ
(Vi JaNN Y
Yin: in: W|,)
B B, (49)
P Dout [Dout
[=1]
VEDoue
p Pour|
where the bound independent of a. Consequently.
D 1]
P
lim 0-1
E
Σ
(yo JaNN[X, Y. mn W).)
(50)
1-a
Doudl Dout
iED
such that when combined with the other expressions above, the conclusion
lim
E splits
Σ
(y
fGNN Y Mini (w::)))
Σ
m
(vo fGNN|X, -r- W):)
;Y;
iED
(51)
obviously follows.
C EXPERIMENTAL DETAILS
C.I TRAINABLE LABEL PROPAGATION
In Table I, we employ trainable label propagation with the same settings as the original label propagation algorithm, including the trade-off term À in (1) and the number of propagation steps. In the implementation, we set as 0.6 and use 50 propagation steps. We search the best splitting probability in the range of {0.05, 0.1,..., 0.1,...,0.95);
C.2 DETERMINISTIC LABEL TRICK APPLIED TO GNNs WITH LINEAR LAYERS
We use three models with linear propagation layers and simply choose specific set of hyperparam- eters and run the model on each dataset with or without label trick in Table 3. The hyperparameters for each model is described propagation layers and is set to (Yang et al., 2021). For SIGN, we sum up all immediate results instead of concatenating them to simplify the implementation and speed up training. Our SIGN model also use 5 propagation steps, and we tune the number of MLP layers from 1 or 2 on each dataset. And for SGC, the number of propagation steps is set to 3, and there one extra linear transformation after the propagation steps.
follows. For TWIRLS,
use 2 propagation steps for the linear
C.3 EFFECT OF SPLITTING PROBABILITY
To further present the effect of splitting probability in Figure 1, we use in the range of (0.00625, 0.0125, 0.025, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 0.9, 0.95, 0.975, 0.9875, 0.99375] to compare linear model (similar labels as input) with three-layer GCN (Kipf & Welling, 2017). Each model uses the same set of hyperparameters, except for the number of epochs, since when is close to zero one, the model requires more epochs to converge. For the linear model, is set to 0.9 and the number of propagation steps is 9. The GCN has 256 hidden channels and activation function of ReLUU.
trainable label propagation algorithm with features and
19

---

Published as a conference paper at ICLR 2022
C.4 TRAINABLE CORRECT AND SMOOTH
We begin by restating the predictor formulation of trainable Correct and Smooth in (14):
frcus(Y; = Pa(Y in + (M + M out) (Y + Ein W W)),,
=P(((Y in (M + M out) Y)W, P. M Ein
(52)
= Po((Y in + (M + onn)) W. + P.(M + M out) Ein W..
Y.
Note that the computation of Y, and Y. e does not involve any trainable parameters. Therefore, can compute them beforehand for each training split.
We now describe our experimental setup used to produce Table 4. We first trained an MLP with exactly the same hyperparameters as in Huang et al. (2021). For each splitting probability a E {0.1, ... 0.9), we generate 10 splits and precompute Y, and Y Then for each training epoch, we cycle over the set of Y, and Y
20


Reviews:
[{"review_id": "uvWfrSO5qu2", "reviewer": "Reviewer_RzBD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work is solid with rigorous formulation, theoretical justification, and novel use cases of the label trick. The authors derive general formulations for the label trick as regularizations in both regression and classification cases. The derivation is presented in a smooth way and provides several inspiring and insightful remarks and conclusions. The proposed use cases based on the theoretical are interesting and promising according to the empirical evaluations. Overall, I recommend acceptance due to the thorough analysis and potentially broader use cases inspired by the work. However, my assessment might be inaccurate due to my limited expertise in this topic.", "summary_of_the_paper": "The authors provide a thorough theoretical justification to the recently emerging and heuristically proposed label trick, i.e., adopting a random portion of node labels in the training set as the input node attributes. Specifically, the authors start from the simplest case of label trick and derive the general formulation of the label trick as a regularizer. Motivated by the theoretical analysis, the authors proposed novel use cases of the label trick in broader scenarios.", "summary_of_the_review": "A solid and inspiring theoretical work. Novel use cases are introduced based on theoretical grounding and are justified by promising empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kEr81JGclM3", "reviewer": "Reviewer_bkGb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths (+) & Weaknesses (–)\n\n(+) The problem that the authors tackle is fundamental/important. The community would benefit from research that connects the ideas of classical label propagation methods and message passing neural networks.\n\n(+)  The approach is well-motivated in that one main issue of the label trick is the undesirable solution of the identity mapping, but only keeping off-diagonal terms in the propagation matrix is a seemingly simple fix (whereas diagonal terms are fine for feature propagation). That is to say, Equation (10) makes intuitive sense.\n\n(+) The work expounds upon the use of the label trick, and is right in saying that it has been mainly used as a heuristic, seeing effective use. Studying it further is a worthwhile pursuit.\n\n(–) Some further emphasis/credit should be given to https://arxiv.org/pdf/2009.03509.pdf who (I believe) first proposed the label trick.\n\n(–) What is the intuition behind equation (3), namely why would one want to express the column space of $Y_{tr}$ by post-multiplying with a weight matrix $W$? I wonder similarly for the trainable Smoothing step in Correct & Smooth.\n\n(–) Given that the paper has some 'theoretical flavor' to it, we should see some comparison to other works that compare label and feature propagation (even if these propagations are not used in parallel), e.g., Jia & Benson 2021 (https://arxiv.org/pdf/2101.07730.pdf).\n\n(–) Some equations are unclear, and the subscript of $\\mathbb{E}_{splits}$ is vague/difficult to parse. I would appreciate some elaboration on Equation 5 in particular, how does one go from the second-last term to the last term? Since D_out has cardinality 1, should the expectation not be over a discrete uniform sample from $i \\sim \\{ 1 \\dots n \\}$, which would simplify to\n\n$ \\frac{1}{n} \\sum_{i \\in D_{tr}} \\ell (y_i, [P(Y_{tr} - Y_i W]_i ) $.\n\nCould you please tell me what I'm missing/failing to see here? Thanks.\n\nMore generally, the paper is at times hard to read due to it being notationally dense (particularly the excessive use of subscripts), and the stream of the 'Remarks'. I feel the paper could benefit from one more pass of re-writing.\n\n(–) For Table 2, R^2 value should be used to evaluate regression.\n\n(–) Section 4.1 is unclear and should have greater detail. For example, how is this procedure trained? What is the final model (is it just supervision on the Neumann series with a weight matrix instead of a propagation matrix)? Further, some reference should be given to other papers who learn/modify the adjacency/propagation matrix.\n\n### Questions:\n\n- Why isn't the deterministic label trick used for comparison in the right plot in Figure 1? Further, which GNN is used? I believe this is unspecified in Section 5.3.\n- In remark 4, if the regularization is shut off why is there \"no chance for overfitting\"? \n- If the derivation shows that we can eventually decompose with a regularization term in the deterministic case, is this used for results in Table 3? If it is not used (as it does not seem to be mentioned), why not?\n\nSome less important nitpicks:\n- typo in remark 2 \"insure\" → \"ensure\"\n- inconsistency in use of parentheses vs square brackets in (4) and (5)\n", "summary_of_the_paper": "The authors discuss the utilization of labels in graph neural networks (or conversely, the utilization of node features in collective classification algorithms, e.g., label propagation) for node prediction. It expounds on the stochastic 'label trick' whereby training labels are concatenated to node features and are then randomly masked to avoid trivial solutions. With simplifying assumptions (where there are no node features), they show that this procedure is reduced to minimizing fitting and regularization terms, which is used as motivation for a few practical methods.\n", "summary_of_the_review": "The paper has strengths and tackles an important problem, but needs further work on the points mentioned above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_jJtRFlX30", "reviewer": "Reviewer_n4P3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- It is nice to take a step back to tries to understand what might look like wizard engineering, and show that the labels tricks can be understood with some simple models.\n- This paper is relatively easy to follow and well-written\n\nWeaknesses:\n- This results in this paper are not really satisfactory. The background and motivations are not really well explained. And the duality between stochasticity of the label trick and the deterministic regularization is not really back-up by \"to-the-point\" experiments. \n- The paper is lacking rigor as I will detail later.\n- Some claims of the paper are weird to me, in particular, the way the graph is built should indeed use features knowledge. So graph-based Laplacian do leverage features (yet in an unsupervised way). Also if the node features are noisy or unreliable, which will downgrade the performance of GNN, I believe the graph structure than will also be noisy or unreliable for those nodes if the graph is build based on features similarity.\n- For a paper that seeks a theoretical explanation of the usefulness of the label trick. I do not have the impression to have learn a lot from it. For example, why self-excluded prediction do not work as well as full execution of the label trick?\nAlso, why the label trick is better than GNN with a Laplacian regularization akin Pfau et al. or Cabannes et al. with a MixUp regularization akin Lopez-Paz et al.?\n\n\nNotes\n\npage 1:\n1/ The readibility of the paper would be improved if the authors were to go straight to the point and more rigorous. For example of “straight to the point\", at line 4 in the introduction, the fact that labels and features vary smoothly over the graph and i.i.d. are two differents problems. And talking about i.i.d. samples is only adding confusion in the mind of the reader (at least in my mind).\nFor example of “rigorous\", in the abstract, talking about the identity mapping from input to output, I believe the authors talks about the transductive setting, in which the feature X is forgotten but a propagation rule is used, which can be null as explained for label leakage in Eq. (3). Clearly the \"identity mapping\" from inputs in R^d to outputs in R^c is not well defined.\n\npage 2:\n1/ It would be nice to explain more clearly the graph formalism. For example:\nEach node is linked to a input point x in R^d, and a label in R^c, from which we can form the node feature matrix (or design matrix) X and the label matrix of the nodes (or label matrix) Y. The graph is a undirected and edge have weights. The adjacency matrix is the matrix of weights (symmetric because the graph is undirected), thus S is symmetric. \n\n2/ \"Nodes connected by an edge […] are likely to share the same labels\". If the graph is weighted this depend on the weight. If the graph is unweighted, it should be specified.\n \n3/ Eq.(1) I believe the second F should be F_tr, otherwise, there is, using pythagoras a penalization pushing F towards zeros on testing data. A close form solution can still be written with this correct formulation as well as the power method. The fact that Y = 0 is an informative labels (e.g. because Y are logits) and that pushing F towards 0 does not bias the system should be specified.\nAlso it would be nice to specify F \\in R^{n \\times c}, and to specify also that this minimizing this objective can be done independently according to each coordinates of \\Y = \\R^c, if there is no constraints on F.\n\npage 3:\n1/ There is a mistake with P \\approx PY on the second paragraph. \nAlso the approximation can be written as an equality with an inifinite sum since \\lambda S is contracting (equality with a series being here understood as the convergence in any norm).\n\n2/ \"where […] P smooths the training labels” is weird since P is not used to defined F^(k). This observation should be written after the definition of P = (1 - \\lambda)(I - \\lambda S)^{-1}.\n\npage 4:\n1/ \"model from (…)”: the parenthesis should be removed\n\n2/ A note on SGC would be highly appreciated, as well as an explanation on the relevance of such a model. Space can be found by condensing section 3.2. and 3.3.\n\n3/ What is P in Eq.(3), P was defined as “a propagation matrix”, how is it fixed here?\n\nAppendix:\nThere is several overboxes, please check the log file when compiling latex.\n\nReferences formatting:\nArXiv -> journal and conference publications\n", "summary_of_the_paper": "The paper focus on the label trick.\nThe label tricks is a method for graph-based semi-supervised learning.\nIn this setting, we have some labeled data points and some unlabeled data points, the goal is to label the unlabeled data.\nThe data points can form vertices of a graph, with edges built based on similarity of the points (eventually with a weighting scheme).\nLabels can be diffused along the graph to label unlabeled data thanks to graph Laplacian.\nA other way to leverage a graph structure is to build a graph neural networks and learn parameters of this networks to match labels of labeled data.\nThe authors states that the first method is utilizing labels and the second method is utilizing features based on a graphical model. They say that both should be done simultaneously, and argue that this is what the label trick is doing.\n\nEventually known labels can used along with features as the input of a GNN, but if we only ask to match labels of labeled data, than a trivial mapping can be learnt (the identity from known labels to the labels of labeled data). Therefore it is smart to use a drop-out strategy where we hide few labels (in particular the ground-truth label) when we want to learn the labels of a labeled data. This is the label trick.\n\nThe paper tries to understand what the label trick is about by looking at simple models.\nIt also discussed on its novel-case of applications.\n", "summary_of_the_review": "Overall while having justifications of what people do in practice is nice, I think this paper fall short of providing a satisfactory analysis of the label tricks, especially since it does not rigorously explained it superiority compared to other methods.\nI think this stream of research is valuable but this is too early for publication.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "A2JdQaK5T7", "reviewer": "Reviewer_Ugm6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(1) The effectiveness of the label trick in improving GNN performance has already been demonstrated in prior work. Because of that, this paper does not repeat these efforts and instead tries to showcase the broader application scenarios from Sec 4. I understand this goal. However, results in the four application scenarios that the authors selected indicate little or no benefit of the label trick. In particular, closely examining, Sec 5.1-5.4 and Tables 1-4, I see that using the label trick gives performance comparable to the baseline methods. This happens in many (if not most) scenarios when I take into account the standard deviation across ten independent runs. \n\n(2) Following from the previous point, I would like to get more clarity on the role of label trick in GNN training. The study makes a very shallow remark that: \"For example, at the time of this submission, the top 10 results spanning multiple research teams all rely on the label trick, as do the top 3 results from the recent KDDCUP 2021 Large-Scale Challenge MAG240M-LSC.\" That is okay, however, it does not mean that the label trick necessarily leads to better performance. To be able to argue that, one would need to run an ablation study comparing top models from the Challenge with and without the label trick. Are there other desirable effects that made the label trick so popular (e.g., faster convergence, more robust training etc.)?", "summary_of_the_paper": "This paper examines the \"label trick\" which enables the parallel propagation of labels and features and benefits various SOTA GNN architectures. The label trick has not yet been rigorously analyzed and so this paper studies it from a theoretical perspective. It first introduces a self-excluded simplification of the label trick by applying an extreme splitting strategy. It then shows that the random splits of the label trick can be regarded as regularization of self-excluded label weights. The paper also discusses broader applications of the label trick in order a) to empower graph-based methods with trainable weights and b) to get rid of the randomness effect by incorporating self-excluded propagation within GNNs composed of linear propagation layers. ", "summary_of_the_review": "I appreciate the formal description of the label trick and the associated theoretical analysis. However, the novel use-cases motivated by that analysis are weak and empirical analysis on the role of the label trick is incomplete.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "4XnNui6h8Zc", "reviewer": "Reviewer_xaW4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n1.\tThe paper provides a relative new framework for GNNs where the stochastic label trick is replaced by a deterministic alternative which focuses on exclusion of self propagation, the alternative seems to be novel\n2.\tShowing an upper bound in  Thm 2 on the deterministic proposal with respect to the cross entropy loss is a valuable result.\n\nWeak points:\n1.\tMotivation: I still feel unconvinced on what are the reasons for replacing the non-deterministic label trick with a deterministic one, except of course under sampling. Is there a computation bottleneck as well? \n2.\tThe authors claim that prior use of the label trick has not been theoretically substantiated but what is the Deterministic advantage here in terms accuracy/ speed/ any other advantage?\n3.\tThe experimental validation leaves me a bit puzzled: except for the graph in Fig 1 there no actual comparison between the deterministic and SotA random label tricks. The authors instead focus on comparisons that are not directly related to what they propose in the paper (e.g. trainable vs non-trainable, with label trick vs without). Why is that so?\n4.\tMy main concern is that the experimental validation even for the experiments on the trainable version and use of the label trick is not convincing enough. I see that in some examples the difference between either the trainable label propagation vs the traditional one, as well as the use of the label trick do not show significant improvement (if at all) in particular when the STD is taken into account.\n5.\tThere are some missing important references on the subject of label propagation in graph and the incorporation of label data:\na.\tRegularization on Graphs with Function-adapted Diffusion Processes Arthur D. Szlam, Mauro Maggioni, Ronald R. Coifman; 9(55):1711−1739, 2008.\n6.\tMany of the algorithms mentioned are not fully understood and self-contained to be easily addressed by the reader, also what is the reference to C&S?\n", "summary_of_the_paper": "The paper proposes a deterministic version for the label trick in GNNs (and other graph frameworks), that is based on a self-exclusion operator for the propagation process in order to avoid label leakage. The authors propose some applications in other label propagation settings. Experiments are shown to compare with regular label propagation, with and without label trick, effect of regularization term in the deterministic setting vs randomized one.", "summary_of_the_review": "Some fundamental issues in the paper are preventing me from accepting this paper: the experimental validation is insufficient and unconvincing. The motivation for proposing the deterministic alternative to the label trick is not discussed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides the theoretical justification for the "label trick" (using labels in graph-based semisupervised learning tasks). The authors performed a thorough evaluation of their analysis, which constitutes an experimental contribution. The authors provided a rebuttal that the AC finds to have reasonably addressed the reviewers' concerns. We recommend acceptance.
Decision: Accept (Poster)