Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
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_review: A solid and inspiring theoretical work. Novel use cases are introduced based on theoretical grounding and are justified by promising empirical results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

(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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strong points:
1.	The 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
2.	Showing an upper bound in  Thm 2 on the deterministic proposal with respect to the cross entropy loss is a valuable result.

Weak points:
1.	Motivation: 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? 
2.	The 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?
3.	The 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?
4.	My 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.
5.	There are some missing important references on the subject of label propagation in graph and the incorporation of label data:
a.	Regularization on Graphs with Function-adapted Diffusion Processes Arthur D. Szlam, Mauro Maggioni, Ronald R. Coifman; 9(55):1711−1739, 2008.
6.	Many 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?

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

main_review: ### Strengths (+) & Weaknesses (–)

(+) 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.

(+)  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.

(+) 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.

(–) Some further emphasis/credit should be given to https://arxiv.org/pdf/2009.03509.pdf who (I believe) first proposed the label trick.

(–) 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.

(–) 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).

(–) 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

$ \frac{1}{n} \sum_{i \in D_{tr}} \ell (y_i, [P(Y_{tr} - Y_i W]_i ) $.

Could you please tell me what I'm missing/failing to see here? Thanks.

More 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.

(–) For Table 2, R^2 value should be used to evaluate regression.

(–) 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.

### Questions:

- 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.
- In remark 4, if the regularization is shut off why is there "no chance for overfitting"? 
- 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?

Some less important nitpicks:
- typo in remark 2 "insure" → "ensure"
- inconsistency in use of parentheses vs square brackets in (4) and (5)

summary_of_the_review: The paper has strengths and tackles an important problem, but needs further work on the points mentioned above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper focus on the label trick.
The label tricks is a method for graph-based semi-supervised learning.
In this setting, we have some labeled data points and some unlabeled data points, the goal is to label the unlabeled data.
The data points can form vertices of a graph, with edges built based on similarity of the points (eventually with a weighting scheme).
Labels can be diffused along the graph to label unlabeled data thanks to graph Laplacian.
A 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.
The 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.

Eventually 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.

The paper tries to understand what the label trick is about by looking at simple models.
It also discussed on its novel-case of applications.

main_review: Strength:
- 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.
- This paper is relatively easy to follow and well-written

Weaknesses:
- 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. 
- The paper is lacking rigor as I will detail later.
- 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.
- 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?
Also, 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.?


Notes

page 1:
1/ 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).
For 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.

page 2:
1/ It would be nice to explain more clearly the graph formalism. For example:
Each 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. 

2/ "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.
 
3/ 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.
Also 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.

page 3:
1/ There is a mistake with P \approx PY on the second paragraph. 
Also 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).

2/ "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}.

page 4:
1/ "model from (…)”: the parenthesis should be removed

2/ 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.

3/ What is P in Eq.(3), P was defined as “a propagation matrix”, how is it fixed here?

Appendix:
There is several overboxes, please check the log file when compiling latex.

References formatting:
ArXiv -> journal and conference publications

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.
I think this stream of research is valuable but this is too early for publication.
review_title: null

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)