Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work presents novel theoretical tools for data-driven algorithm design. In particular, the authors generalise a dispersion-based analysis from intervals to axis-aligned paths of arbitrary dimension. 

Using these new results, the authors study graph-based semi-supervised learning from a data-driven perspective and achieve strong bounds in the online and PAC setting. Their goal is to perform well on a fixed distribution of semi-supervised problem instances (or minimising the regret in the online setting) by selecting the most appropriate graph from a parametrised graph family (in particular: threshold graphs and graphs with edge weights given by the polynomial or RBF kernel). Many additional results, such as first experiments and lower bounds, are discussed.
main_review: This is a very interesting and important work studying semi-supervised learning from a data-driven perspective. It opens up many interesting follow-up questions and makes one interested in reading more on that topic. It is an important contribution to the problem of learning / constructing the graph for semi-supervised learning. 

Even though some parts (section 1, 2 and the first paragraph of section 4 with Theorem 5) are very well-written, the main technical sections of this work are quite dense and sometimes hard to follow. Notation and concepts are sometimes not well introduced and discussed. E.g., the $G(r)$ (and related) are not formally introduced. 

Also, the proposed algorithms are only very briefly described. The notation and details are not really clear. Algorithm 2 is not referenced from the main text.

Some more related previous papers could be discussed in more depth, in particular previous theoretical results on graph construction such as
* Maier, Markus, Ulrike Von Luxburg, and Matthias Hein. "Influence of graph construction on graph-based clustering measures." NIPS. Vol. 1025. 2008.

and, for example, the discussions in:
* Liu, Wei, Junfeng He, and Shih-Fu Chang. "Large graph construction for scalable semi-supervised learning." ICML. 2010.
* Jebara, Tony, Jun Wang, and Shih-Fu Chang. "Graph construction and b-matching for semi-supervised learning." Proceedings of the 26th annual international conference on machine learning. 2009.

Some additional minor comments:

* line 41: $L+U$, why not use the common notation $L\cup U$.
* line 69: $G(\rho)$ where $\rho$ corresponds to a semi-supervised learning (SSL) algorithm. However later the authors rather use e.g., $G(r)$ or $G(\sigma)$ to denote the parameter to construct the graph and not the SSL algorithm itself. This is a little bit confusing. It would also help a lot to properly define $G(r)$, $G(\sigma)$, and $G(\tilde{\alpha})$,e.g., in Def. 1.
* line 103: Is it allowed to have the same examples in $L$ and $U$?
* In line 113, the authors call $d$ a similarity function (which would be large for similar examples), but seem to use it rather as a distance/metric (small for similar examples)
* line 116: Why not use the more commonly used term $\varepsilon$-neighbourhood graph ($\varepsilon$-NN) instead of "threshold graphs". The name threshold graphs is also used to describe a particular unweighted graph family.
* line 206: What embeddings do the authors mean here?
* The set $C$ used in algorithm 1 and 2 is not defined nor described. Algorithm 1: Two dots ".." in line 6. Missing "dp" in line 9.
* line 237: typo in "existin", -> "exist in"
* line 408: reference: missing "ö" in Schölkopf. Also: the year seems to be wrong, the book was published in 2006, and is the ISBN really required?
* a conclusion paragraph would be nice.
limitations_and_societal_impact: The authors do not discuss any limitations. In my opinion, there are some topics, which the authors might address:
* Is it possible to get similar bounds for (one of the most commonly used similarity graph) $k$-nearest neighbour graphs ($k$-NNs)? Why do the authors have restricted their results to the other three types (threshold, polynomial, RBF)?
* Do the results still hold when using other classification algorithms, e.g., learning with local and global (Zhou, et al. 2004) or GCNs?
* This work mostly focuses on setting the edge-weights (or filtering edges) of the graph given feature-based distances. There might be scenarios where restricting the whole graph family (e.g., to trees) is more reasonable than just setting the weights. 
* The double exponential dependence on $p$ in Theorem 3 seems to be problematic. Please, discuss why this is theoretically / asymptotically not an issue. Also mention this in the main text, instead of hiding the "constant" in the $O(\cdot)$. It seems to severely limit the practicability of these bounds. 


The authors only briefly discuss societal impact. However, this is completely fine for such a conceptual and theoretical work
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors suggest using repeated problem instances to learn input graphs for graph-based semi-supervised algorithms. They extend the concept of dispersion of one-dimensional algebraic polynomials to an arbitrary number of dimensions in order to provide uniform convergence guarantees for the gaussian graph kernel in unweighted offline training and a generalization bound for weighted graphs. They also offer a threshold graph approach for online training under the dispersity assumption that includes assurances in the form of a constraint on the algorithm's regret across repetitions. Finally, they show that the suggested offline technique leads to minimal regret across a large number of repetitions T.
main_review: The paper is well written however there are a number of issues making that the paper is not ready for publication:
limitations_and_societal_impact: Overall remarks:
*Theorem3 is not self-content.
* There are no comments on Theorem4's inequality: What does this outcome (inequality) imply?
* The argument over how to test the dispersion assumption in the sequence of high-dimensional loss functions of graph parameters in practice is unclear.
* The dataset size, n, is maintained relatively modest (n=100) compared to the size of the benchmark datasets that were utilized, most likely due to the high time complexity of the optimization process for learning the graph parameters (MNIST, CIFAR, Omnigot).
* The low generalization of the optimal parameter values determined via transductive training, as shown in the experimental part, might be explained by the limited sample size used in training.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a data driven approach to construct graph for graph-based semi-supervised classification task. The authors realize the graph quality is important to learning performance and they aim to update the hyper-parameter when new samples come. They present the algorithms for two cases, online and distributional settings.
main_review: Originality: The task of updating hyper-parameter for creating graph is new. The method seems an extension of Balcan's work, but shows some novelty as focusing on different tasks. The related works are properly cited and major contributions are nicely stated.
 
Quality: I have some concerns by reading this paper.
1. If the number of data (L+U) is already large at time of t, the necessity of updating the hyper-parameter for the same domain instances are reduced? So I would like to know if the same domain indicates that data are drew from the identical distribution. If so, it strictly not online learning.
2. It is observed that a target labeling tau is used for computing the loss l_A (line 111).  What is target labeling? Is it side-information compared to the regularized loss (line 43)? Because I have found tau is used in algorithm (step 7 in Alg 1)
3. For the online setting, it seems every time a new sample comes the whole graph will be updated. Is it practical in real case? How about updating a small fraction of entries of w?
4. I am new to regret loss. Is regret estimated from hindsight?
5. Can we say regret in Fig 3(b) converges to the optimal parameter within 50 iterations?
6. Some equations and symbols. Check inequality line 131; rho \in P (line 108) but rho \in C (line 131); definition of \bar{U} (line 191), etc.
7. I think it is better to say "graph-based SSL" in title.

Clarity: The submission clearly written except some typos.

Significance: As graph based semi-supervised learning is not popular for today's research due to its intrinsic limitations, the extension of the main theory from Balcan et al. for this task is not very interesting for me. But this paper is still valuable for some readers in the community. 
limitations_and_societal_impact: The authors have pointed out one limitation of this work (line 460).
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose to learn the underlying graphs for graph-based semi-supervised learning problems. So far, graph-based SSL usually grounds on KNN-like graphs where distances are computed according to some measure. The present paper now learns the parameters of the measures (kernels) as well as a threshold to determine whether an edge is present or not. 
main_review: This is a very interesting paper that introduces solid theoretical results that may have an impact in domains different from SSL. The derivations heavily build on different results by Balcan and colleagues and render the technical contribution very strong and convincing, including novel regret bound, algorithms, as well as generalization guarantees in probabilistic scenarios. The appendix is very helpful and gives many additional insights. 

I appreciate the authors response. 
limitations_and_societal_impact: Yes in terms of limitations, there are no societal aspects.
review_title: null

Meta-review: The reviewers generally consider this a strong theoretical submission that should be accepted despite a few shortcomings in the experiments. The author feedback clarified a few open questions and should be incorporated in the final version. The reviewers appreciated the solid theoretical work with impact to graph-based semi-supervised learning and beyond.
Decision: Accept (Oral)