Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The topic of the paper is label propagation with an additional weak supervision that provides noisy predictions for all unlabeled points. The main contributions are two-folded: 1) providing a novel theoretical error bound of label propagation, and 2) proposing a multiple source extension. For 1), the analysis provides more detailed insight about the test error bound, compared with existing studies, and 2) proposes combining a set of different weak supervisions by adaptively weighting them based on their estimated accuracy. Performance superiority is empirically shown on four benchmark datasets.
strength_and_weaknesses: Strength:
- As the authors claim, the theoretical analysis provides a novel insight for label propagation. Differences from conventional analysis (Belkin & Niyoki 2004) described in Sec3.2 are interesting (e.g., conventional analysis does not reflect label positions in the graph). Overall, I think this analysis is valuable.
- The paper is easy to follow, and the proposed method is easy to implement. Relations with wide range of existing studies are discussed.
- Empirical evaluation shows good performance, compared with other recent weakly supervised models for the same setting.

Weaknesses:
- Theoretical justification of the choice of alpha_j in the multiple source extension is not fully clear (the main theoretical analysis is only for single weak supervision, and for multiple source setting, for which a novel model is proposed in this paper, a full theoretical analysis that includes the effect of the alpha estimation is not provided). In particular, the probabilistic model in Sec4.2 is a bit strange for me. Since y is binary label and h(x) is first defined as a map from X to [0,1], an interpretation of the model h_j \sim N(y,\sigma(x)) is unclear. 
- The formulation of the proposed multiple source framework (3) itself is a bit straightforward. It is reasonable, but the technical novelty of this extension is not particularly strong. Further, compared with LPA+WL (single weak supervision), effectiveness of the multiple source extension is slight, empirically shown in Table1. The methodology of LPA+WL does not have particular novelty in my understanding (the objective function for the single supervision setting (1) is straightforward). In this sense, the performance superiority of the model newly proposed in this paper is not fully demonstrated.
- Although theoretical analysis is interesting, it is not reflected to the learning model and the algorithm, throughout the paper. Practical benefit of the theorem is not fully revealed.

Minor comments: 
- 'set alpha_j(x_i) = 0 when h_j makes a correct prediction' should be 'alpha_j(x_i) = 1'?
- 'h_j \sim N(y,sigma(x))' should be 'h_j \sim N(y,sigma_j(x))'? The former definition seems to have a common variance across all h_j. 
- Why w_ij does not exist in l(f) in Sec4.2?
clarity,_quality,_novelty_and_reproducibility: 
Clarity: Readability is fine. The paper is easy to follow. Illustrations help readers.

Quality: Technical quality is sufficiently good.

Novelty: Theoretical analysis contains a novel approach, while novelty on the multiple source extension is somewhat marginal.

Reproducibility: Experimental settings are sufficiently provided.
summary_of_the_review: For me, the paper is on the borderline, but I currently lean toward rejection. The theoretical analysis is interesting as written in 'strength', but it is only for the single supervision setting. On the other hand, the main methodological proposal of this paper is for the multiple information source setting. Nevertheless, the empirical results do not show clear performance superiority of the multiple source extension.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: They propose a novel analysis of the classical label propagation algorithm with an error bound. They also propose a framework to incorporate multiple sources of noisy information.
strength_and_weaknesses: This paper provides some interesting results, but there are some questions needed to be answered.
1.	Definition 1 is confused in this paper, the subset S?
2.	What is the relationship between Theorem 1 and Theorem 2? 
3.	In Theorem 2, you should give more details to introduce the generalization performance of the proposed method. 
4.	In your experimental settings, the setting of 𝜆 should be more clear. 
5.	Several mistakes need to be corrected. For example, 
a.	“Proof. (Sketch) The key idea of our proof is to upper bound each E_i for ...”, and there is an error in mathematical notation in this sentence. 
b.	“We note that this function…” This sentence also includes errors.
Therefore, I suggest that you should check your paper carefully to avoid similar mistakes. 

clarity,_quality,_novelty_and_reproducibility: 
The proposed methods are sound, and the three aspects are pretty good.


summary_of_the_review: In a word, the idea of the proposed model is useful to obtain a better performance, and the related theoretical support is sufficient. However, several detail issues are not clear in the proposed model, and some mistakes should be avoided.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides a "fine-grained" theory for the label propagation algorithm (LPA) in the presence of prior information. Unlike the existing theory, the new error bound takes into account the local geometric properties of the graph. The new error bound enables us to discriminate two geometrically different graphs with the same number of labeled nodes, while the existing bound cannot discriminate them. In addition to the new error bound, the existing framework for the LPA is extended to the setting where multiple sources of prior information are available. Finally, the superior performance of the proposed LPA with weak supervision was shown through numerical experiments.
strength_and_weaknesses: ##### Strengths
- The error bound that takes into account the geometric properties of the graph is novel.
- The proposed LPA with weak supervision allows us to use prior information from multiple sources.
- The effectiveness of the proposed method was demonstrated on various datasets.

##### Weaknesses
- The error bound depends on several parameters which need to be approximated in practice, as discussed in Section 6.
clarity,_quality,_novelty_and_reproducibility: Although the math part requires knowledge about graph theory, such as conductance, the implication of theoretical results is clearly explained. For example, the strength of the new error bound against the existing one is explained using three examples shown in Figure 2. 
The explanation in Section 4 could be improved. There are several new insights by extending the existing framework, but the impact compared with the existing works is a bit unclear to me.

It seems that the Dirichlet conductance from the recent study plays a vital role in Theorem 1. For the people who are not familiar with the study, some explanations/interpretations about the Dirichlet conductance would be helpful to understand this paper.

In the experiments, the average degree of the constructed Graph was set to 1. It seems a low value, and explanations for the value would improve the clarity of the paper.

In Theorem 4 in Appendix C, if explanations of the effect of t are provided, the clarity would be improved.

The error bound shown in this paper is novel. While the LPA framework in Section 4 is an extension of the existing framework, it is novel. It would be grateful if the authors could emphasize and clarify the contribution of the new framework while comparing the existing framework.

Regarding quality, the novel error bound provides more information than the existing spectral bounds. Moreover, the new LPA framework for incorporating information from multiple sources contributes to the study of LPA. It enables us to use weak labelers with LPA, and its usefulness was demonstrated in the experiments.

In Section 5 and Appendix G, the details of the experiments are provided. In addition, the code to replicate the experiments will be released publicly. The reproducibility is thus high.

summary_of_the_review: This paper introduced the novel error bound for the label propagation algorithm. The difference between the existing and new bounds is clearly explained. The experimental results showed the empirical superiority of the new framework for LPA. The reproducibility seems high.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides a new error bound of LPA with prior information and compares it with the conventional spectral bound. Then it proposes two strategies to design the prior information. The paper also conducts experiments, which compares with some weakly supervised methods and semi-supervised methods. The experimental results demonstrate the effectiveness of the proposed strategies.
strength_and_weaknesses: Strengths:
1. The paper proposes a new error bound for LPA, and provides an example to show its superiority compared with conventional spectral bound.
2. The paper is technically sound.
3. The experimental results are good. The authors also provide their codes of experiments.

Weaknesses and questions:
1. I'm a little confused about its weaklly supervised learning setting. To my knowledge, there are many kinds of weaklly supervised learning setting. For exmple, in some settings, only coarse-grained labels are given for the training data; in some settings, the given labels are sometimes not correct for the training data. What is the specific setting of this paper? From the experiments, it seems that the labels (or psuedolabels) of some data are not correct? If so, what is the difference between it and learning with noisy data? And maybe it needs to compare with such learning methods with noisy data.
2. The paper compares its bound with spectral bound and gives a case study to show its superiority, which is good. Since the form of the two bounds are quite different, I think it's hard to say which is tighter in general. It may be interesting if you could provide the cases when the proposed bounds fail or at least worse than the conventional one. It can tell the readers when should we use the proposed bound and when should not.
3. Why does Table 2 not report the results of GCN, CLL and so on?
clarity,_quality,_novelty_and_reproducibility: The paper has new theoretical results and is technically sound. The authors also provide the codes for reproducibility. Overall, the paper is well-written.
summary_of_the_review: Due to the strengths listed above, I recommend for Accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
This paper provides a novel theoretical analysis of the classical label propagation algorithm and establishes an error bound. The authors also incorporate multiple sources of noisy information. Experiments demonstrate the usefulness of the label propagation algorithm with weak supervision.

Strength:
Theory is insightful and empirical performance is promising.

Weakness:
The proposed algorithm is rather straightforward.

justification_for_why_not_higher_score: Since the proposed algorithm itself is rather straightforward, innovativeness is not high enough to recommend this work to spotlight or oral. 

As several reviewers pointed out, explanations in Section 4 are not clear enough and thus I suggest the authors to revise it based on the feedback from the reviewers.


justification_for_why_not_lower_score: I recommend the acceptance of this paper due to its technical soundness and empirical usefulness.
Decision: Accept: poster