Continuous Partitioning for Graph-Based Semi-Supervised Learning

We thank the reviewer for their constructive comments. We address reviewer comments below and will edit the final version of the paper according to the reviewer’s comments.

Motivation of CutSSL In contrast to Laplace learning, which is degenerate in the low-label rate regime, we start with a framework that is nondegenerate, even without any labels (min cut, stated in eq (4)) and derive a nonconvex continuous relaxation that incorporates label information. To show the relaxation is exact (eq (9)), we prove two statements (propositions 3.1 and 3.2). First (proposition 3.1), we show that at integer solutions (valid cuts), the relaxation coincides with the combinatorial problem, i.e., the min cut with respect to the relaxation is the min cut with respect to the combinatorial problem. Next (proposition 3.2), we show that (1.) local minima of the relaxation are integer-valued and (2.) the number of local minima can be controlled (and is via our framework) to prevent a badly behaved optimization problem with many spurious local minima. Thus the global minimum of the relaxation is exactly the min cut.

To provide additional motivation for CutSSL, we provide the experiment below. We show that in the absence of labels purely unsupervised graph cut-based methods (e.g. Spectral Clustering (SC)) yield a graph cut / partition such that the resulting clusters are well-aligned with the labels. To demonstrate this, we calculate a partition using both SC and a graph cut solution to equation 8 (‘cut’), i.e.this is CutSSL in the absence of labels. To evaluate the alignment of the clusters yielded by the cut with the labels, we solve a linear sum assignment problem using the true labels to find the best permutation of cluster assignments. This assignment of clusters to classes shows that the graphs cut are relatively well-aligned with the class labels in contrast to Laplace learning (LP) which degenerates in the low label rate regime (i.e. just a single label per-class). Thus, cut-based techniques work since they are derived from a fundamentally non-degenerate framework and our CutSSL augments the multi-way graph partition with labeled nodes.

Clarification of the term Continuous Partitioning Thank you for pointing out this issue. We will clarify this term in the final version. To be precise, we design a continuous relaxation of the combinatorial partitioning problem with label constraints. This term is typically used in the numerical optimization and partitioning community [1, 2], but is perhaps not as well-known in a machine learning context. We will clarify this term in the final version.

[1] Pardalos, Continuous Approaches to Discrete Optimization Problems, Nonlinear Optimization and Applications, 1996. [2] Discrete Optimization via Continuous Relaxation, Symposium on Bridging Continuous and Discrete Optimization

Clarification of the class and label imbalance and notation To clarify, an imbalance in the class distribution refers to an imbalance in the number of samples for each class. A label imbalance refers to an imbalance in the number of samples that are labeled for each class. Note that the expression for the variable $B$ is given in equation (3).

Choice of $s$ Thanks for pointing this out. This is an important question to address and we will provide additional clarification in the final version of our paper. We highlight a result that appears in the main text and several experiments presented in the appendix of our paper. In particular, the choice of $s$ is governed by Proposition 3.2, which provides an upper bound on the choice of $s$ that guarantees recovery of integer-valued solutions (for intuition see figure 1). A trivial lower-bound is given by one convex relaxation of the problem ($s = 0$). Given the upper and lower-bound, we construct a homotopy path, a sequence of solutions $X(s)$ that vary in $s$. In practice, we choose a linear or geometric sequence s between $0$ and the upper bound. Many times, the upper bound need not be reached to recover a solution that is very close to integer (see Figure 6.b in the appendix). Likewise, we demonstrate that in practice, one can take a very coarse sequence of $s$. This result is presented and discussed in Figure 6 in appendix C.5. In fact, to reproduce the results in the main text, only a single nonzero data-dependent value of s is used (i.e. the homotopy path consists of constructing solutions for $s = 0$ and $s = 0.1$).

Additional references Thanks for notifying us of this missing review. We have added it to our paper. It will appear in the final version.

We thank the reviewer for their positive comments. Below we comment on the choice of the hyperparameter $s$.

Choice of s Thanks for pointing this out. This is an important question to address and we will provide additional clarification in the final version of our paper. We highlight a result that appears in the main text and several experiments presented in the appendix of our paper. In particular, the choice of $s$ is governed by Proposition 3.2, which provides an upper bound on the choice of $s_T$ that guarantees recovery of integer-valued solutions (for intuition see figure 1). A trivial lower-bound is given by one convex relaxation of the problem ($s_0 = 0$). Given the upper and lower-bound, we construct a homotopy path, a sequence of solutions $X(s_t)$ that vary in $s_t$. In practice, we choose a linear or geometric sequence s between $0$ and the upper bound (e.g. determined by that $d$ parameter). Many times, the upper bound need not be reached to recover a solution that is very close to integer (see Figure 6.b in the appendix). Likewise, we demonstrate that in practice, one can take a very coarse sequence of $s$. This result is presented and discussed in Figure 6 in appendix C.5. In fact, to reproduce the results in the main text, only a single nonzero data-dependent value of s is used (i.e. the homotopy path used for the main experiments consists of constructing a pair of solutions for $s = 0$ and $s = 0.1$).

Generally, convergence can be measured according to proximity to an integer solution. E.g., if $X(s_t)$ is the CutSSL solution with respect to $s_t$, let $Proj_B(X(s_t))$ be the projection onto the set of feasible binary matrices (those binary matrices with one "1" in each row and with column sum $m$). Then, convergence has been reached if $||X(s_t) - Proj_B(X(s_t))||_F$ is sufficiently small.

We thank the reviewer for their careful reading of our work and for their positive and constructive comments and for appreciating the significance of our work. We address reviewer questions and suggestions below.

Choice of S We refer to the response to all authors. In summary, Proposition 3.2 provides an upper bound on the choice of $s$ that guarantees recovery of integer-valued solutions. A lower-bound is given by one convex relaxation ($s = 0$). Given the upper and lower-bound, we construct a homotopy path, a sequence of solutions $X(s)$ that vary in $s$. Empirically, the upper bound need not be reached to recover a solution that is very close to integer and that in practice, one can take a very coarse sequence (Figure 6 in appendix C.5.)

Connection to mean-shift Laplace learning and Proposition 4.1 This is an interesting and important question. We agree that a more careful analysis needs to be conducted to derive conditions on the parameters of the problem for the solutions to (17) and cutSSL for $s=0$ to be close (we “show” this experimentally, see the paragraph below (17)). To summarize, we derive a connection between a special case of our framework and Laplace learning (proposition 4.1). This connection bridges our method with existing literature on Laplace learning. In particular, note that mean-shift Laplace learning is a reasonable approximation of CutSSL only in the case where $s \approx 0$. When $s$ is sufficiently large, the approximation does not hold. The indefiniteness of the quadratic yields an unbounded problem. We will clarify this in the final version of the paper.

Regarding the bound, we believe that the fact that the approximation does not hold to be of interest. The purpose of the bound is to explore an existing way to address the degeneracy of Laplace learning: the mean-shifted Laplace learning. Our perspective of this algorithm as a heuristic for solving (17) results in (1.) a characterization of the degeneracy as a rank-1 perturbation of the solution to (17) and (2.) a simple improvement on the mean-shift heuristic. Note that the degenerate term (equation 32 in appendix B) grows as the amount of labeled data diminishes resulting in a larger gap between (17) and mean-shift laplace learning.

Label/class imbalance performance We agree that investigating guarantees for label and class imbalance performance is an important future direction. The main barrier to developing these theoretical results is nonconvexity and a dependence on the graph, the underlying labeling of the vertices, and the distribution of provided labels. In the future we plan to explore equivalent reparameterizations of the problem, e.g. a convex objective over a nonconvex set. We agree with the reviewer’s comment on the placement of the experiments for label/class imbalance and we will move these results to the main text in the final version of the paper.

Additional questions We thank the reviewer for carefully reading our work. We appreciate the detailed questions. We will add additional clarification to the final version of the paper.

Estimation of the cardinality constraint: In many situations, a prior may be obtained on the class distribution (e.g. using the provided labels). However, in general these may not necessarily be known. In this case, a typical assumption is that the classes are balanced (i.e. a uniform cardinality constraint). In the case that one does not have exact estimate of the prior, it would be interesting to investigate a variation of our problem which alters the cardinality constraint with upper and lower bounds: i.e. $m - \epsilon<= X^\top 1_n <= m + \epsilon$.

Thresholding Laplace learning: In our paper we provide an alternative characterization to the degeneracy in prop 4.1 that was originally rigorously studied in (Calder et al., Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates, 2020). This degeneracy results in predictions that are constant at low label rates. We should clarify that there are several ad-hoc heuristics that can be applied to map continuous valued predictions to discrete predictions, although thresholding is almost always the default choice. Although it is possible that alternative heuristics might perform better in the degenerate regime, we show specifically that thresholding is a poor choice (see figure 4 in the appendix) as it tends to make constant predictions.

Connection to spectral graph theory: Thanks for pointing this out. This is an important question to address. At a high level, both spectral partitioning methods and our method rely on two different continuous relaxations of the combinatorial graph partitioning problem (4). In fact, the set of valid cuts can exactly be characterized as the intersection of two sets: the feasible set of (8) (this is the one we do optimization over) and the set of orthogonal matrices. Informally, problem (5) is related to finding the binary matrix satisfying the cardinality constraint whose projection onto the orthogonal complement of 1 is closest to the eigenspace of the smallest nonzero eigenvalue of graph Laplacian.

(8) and (9): They are equivalent by proposition 3.1.

Smallest choice of $s$: Given the graph Laplacian $L = D - W$, the smallest $s$ satisfies the conditions for prop 3.1 is given by the expression $(s-1)(D_{ii}+D_{jj}) \geq 2w_{ij})$. One can compute the smallest $s$ analytically by computing the expression $1 + \max_{ij}2w_{ij} / (D_{ii} + D_{jj})$. This expression involves a simple element wise division and scan, taking $O(|E|)$ linear time in the number of edges of the graph / nonzero entries of $W$.

Convergence rates for ADMM: we clarify that while global convergence is thoroughly established, the convergence rate of ADMM for nonconvex problems is an ongoing research area. Under certain convexity and smoothness assumptions, ADMM converges linearly which we expect to hold for our problem.

Thanks for investing time and for providing valuable feedback! We appreciate the suggestions and questions and your help with improving the quality of our paper. To follow-up on the choice of $s=0.1$, we compute the smallest values of $s$ that guarantee integer solutions on MNIST, FashionMNIST, and CIFAR10 (using the equation provided in the rebuttal). We will provide a more detailed experiment in the final version of the paper to explore the effect of the labeling.

It can be seen that these values are approximately on the order of $0.1$ (the value that we adopt in the main table in the paper) and agree with the results provided in the appendix (Figures 6b and 7c). Note that we also evaluate larger values of s, (i.e. s=0.5, 1.0, etc.) in the appendix. In practice, we note that (1.) generally a choice of $s$ that is smaller than the bound yields solutions close enough to integer and (2.) the effect of the concave term (i.e. larger $s$ inducing more bad local minima) and the computational overhead of running CutSSL on larger sequences of $s$ need to be considered. This tradeoff is explored in Figure 6b in the appendix and these results (notably the robustness of CutSSL to coarse sequences of $s$ and $s$ smaller than the bound) motivated our choice of $s=0.1$ for the results presented in the main text. We will clarify this in the final version of the paper.

Thank you again for the high-quality review. We would be happy to address any remaining issues, or clarify sources of confusion.

We thank the reviewer for their positive and constructive comments and for appreciating the significance and originality of our work. We address reviewer questions and suggestions below.

Theoretical analysis in low-label rate regime We agree that this is an interesting and important direction. To be clear, In this paper, we make three formal mathematical statements. In contrast to Laplace learning, which is degenerate in the low-label rate regime, we start with a framework that is nondegenerate, even without any labels, but combinatorial problem (min cut, stated in eq (4)) and derive a nonconvex continuous relaxation that incorporates label information. To show the relaxation is exact (eq (9)), we prove two statements (propositions 3.1 and 3.2). First (proposition 3.1), we show that at integer solutions (valid cuts), the relaxation coincides with the combinatorial problem, i.e., the min cut with respect to the relaxation is the min cut with respect to the combinatorial problem. Next (proposition 3.2), we show that (1.) local minima of the relaxation are integer-valued and (2.) the number of local minima can be controlled (and is via our framework) to prevent a badly behaved optimization problem with many spurious local minima. Thus the global minimum of the relaxation is exactly the min cut.

However, a precise statement about the quality of the solutions recovered by CutSSL is beyond the scope of this work. Such a statement would need to take into account the topology of the network, the true labeling of all the vertices, and the distribution of the provided labels and additionally address the underlying nonconvexity of the problem. In a future work we plan to explore equivalent reparameterizations of the problem, e.g. a convex objective over a nonconvex set.

GNN-based methods In tables 2 and 8 we included a comparison to a recent GNN-based method designed for low-label rate semi-supervised learning (GraphHop, Xie et al. 2023). We also compare to SOTA method Poisson MBO (Calder et al. 2020) and show we out-perform both methods, with ~30% improvement of CutSSL compared to GraphHop. We will include comparison to additional GNN-based methods in the final version.

Runtime analysis We highlight additional results that appear in the main text and appendix of our paper. In particular, in table 2 of section 5 of the main text and Table 8 in Appendix C4 we provide the average runtime over 100 trials on the large-scale OGB-Arxiv and OGBN-Products benchmarks. While a marginal increase in computation cost of CutSSL is apparent, when compared to classic Laplace and Poisson learning methods, we emphasize that the cost is small and is vastly superior compared to PoissonMBO and the GNN-based method GraphHop. The price of each iteration of ADMM is very cheap due the well-conditioned nature of the subproblems (see section 3.3 for more details).

Choice of hyperparameter / sensitivity We highlight a result that appears in the main text and several experiments presented in the appendix of our paper. In particular, the choice of $s$ is governed by Proposition 3.2, which provides an upper bound on the choice of $s$ that guarantees recovery of integer-valued solutions (for intuition see figure 1). A trivial lower-bound is given by one convex relaxation of the problem ($s = 0$). Given the upper and lower-bound, we construct a homotopy path, a sequence of solutions $X(s)$ that vary in $s$. In practice, we choose a linear or geometric sequence s between $0$ and the upper bound. Many times, the upper bound need not be reached to recover a solution that is very close to integer (see Figure 6.b in the appendix). Likewise, we demonstrate that in practice, one can take a very coarse sequence of $s$. This result is presented and discussed in Figure 6 in appendix C.5. In fact, to reproduce the results in the main text, only a single nonzero data-dependent value of s is used (i.e. the homotopy path consists of constructing solutions for $s = 0$ and $s = 0.1$).

Beyond KNN-Graphs Thanks for this suggestion. This is an interesting direction for future work. We note that in Table 10 in appendix C.5, we provide an ablation for various choices of k. As mentioned in the appendix, the relative performance remains consistent (i.e., CutSSL continues to outperform the other methods). One very interesting observation is that for CutSSL, the accuracy tends to improve with the value of $k$, although it’s possible that the accuracy could deteriorate for larger values of $k$. In the table below we evaluate the effect mechanism used to construct the graph on MNIST. First, we evaluate two variants of weighting edges of the KNN-based method adopted in the main text. Singular refers to weights of the form $w_{ij} = 1/||x_i - x_j||$, where $x_i$ and $x_j$ are the features of the $i$-th and $j$-th data points. Uniform refers to $w_{ij} = 1$, i.e. an unweighted graph. In the third column, we evaluate a more sophisticated method for graph construction based on Non-Negative kernel regression (NNK) [1]. As opposed to the KNN-based methods, which only consider the distance (or similarity) between the query and the data, the NNK-based method takes into account the relative position of the neighbors themselves. Note that our CutSSL out-performs Poisson-MBO for the different graph weighting methods and NNK construction.
We thank the reviewer for this suggestion and we will add this experiment to the supplement in the final version of the paper.

[1] Shekkizhar and Ortega, Neighborhood and Graph Constructions using Non-Negative Kernel Regression, ICASSP, 2020