Continuous Partitioning for Graph-Based Semi-Supervised Learning
Authors: Chester Holtz
Pengwen Chen
Zhengchao Wan
Chung-Kuan Cheng
Gal Mishne
Venue: NeurIPS 2024 poster (2024)
Keywords: graph learning
semi-supervised learning
Primary area: optimization
TL;DR: We propose to solve an exact nonconvex relaxation of a cut-based framework for graph-based semi-supervised learning at low label rates.

Abstract: Laplace learning algorithms for graph-based semi-supervised learning have been shown to produce degenerate predictions at low label rates and in imbalanced class regimes, particularly near class boundaries. We propose CutSSL: a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming, which provably obtains \emph{integer} solutions. Our framework is naturally motivated by an \emph{exact} quadratic relaxation of a cardinality-constrained minimum-cut graph partitioning problem. Furthermore, we show our formulation is related to an optimization problem whose approximate solution is the mean-shifted Laplace learning heuristic, thus providing new insight into the performance of this heuristic. We demonstrate that CutSSL significantly surpasses the current state-of-the-art on k-nearest neighbor graphs and large real-world graph benchmarks across a variety of label rates, class imbalance, and label imbalance regimes. Our implementation is available on Colab\footnote{\url{https://colab.research.google.com/drive/1tGU5rxE1N5d0KGcNzlvZ0BgRc7_vob7b?usp=sharing}}.

Continuous Partitioning for Graph-Based Semi-Supervised Learning
Chester Holtz
Pengwen Chen
Halicioğlu Data Science Institute University of California San Diego
Department of Applied Mathematics National Chung Hsing University South District, Taichung, Taiwan pengwen@email nchu.. edu. tw
La Jolla, CA chholtzQucsd.cmm edu
Zhengchao Wan Department of Mathematics University Missouri Columbia, MO zwan@missouri. edu
Chung- Kuan Cheng
Department of Computer Science University of California San Diego
La Jolla, CA ckchengducsd. edu
Gal Mishne
Halicioğlu Data Science Institute University of California San Diego
La Jolla, CA gmishneQucsd.co edu
Abstract
Laplace learning algorithms for graph-based semi-supervised learning have been shown to suffer from degeneracy at low label rates and imbalanced class regimes. Here, propose CutSSL: framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming, which provably obtains integer solutions. Our framework is naturally motivated by an exact quadratic relaxation of a pardinality-constralle
minimum-cut graph partitioning problem. Furthermore, we show our formulation is related to an optimization problem whose approximate solution is the mean-shifted Laplace learning heuristic, thus providing new insight into the performance of this heuristic. We demonstrate that CutSSL significantly surpasses the current ofte-ooftthearr on k-nearest neighbor graphs and large real- world graph benchmarks across a variety of label rates, class imbalance, and label imbalance regimes. Our implementation is available on githut
Introduction
In supervisde learning (SSL), a learner given access to partially-labeled training set consisting of labeled examples and unlabeled examples. The goal in this setting is to learn predictor that is superior a predictor that trained using the labeled examples alone. This framework is motivated by the high cost of obtaining annotated data on practical problems. For problems where very few labels are available, the geometry of the unlabeled data can be used significantly improve the performance of classic machine learning models. A seminal work in graph-based semi-supervised learning is Laplace learning 388 which seeks a harmonic function that extends provided labels over
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the unlabeled vertices (a harmonic extension of the labeled vertices). Laplace learning and its variants have been widely applied in semi-supervised and graph-structured learning [37 36 20].
However, recent work [26 I has demonstrated that 'vanilla' Laplace learning methods exhibit poor prediction errоr low label rates, primarily due to degenerate estimates
the decision cuundary-althougg this can be partially addressed in practice via a simple mean-shift of the predictions [TO.. Furthermore, in the context of classification, the labels often correspond to elements from a discrete set. In this setting, typically a thresholding operation is applied post hoc to the harmonic extension to map from continuous predictions the discrete set of labels. This thresholding can further exacerbate the aforementioned degeneracy. Furthermore, when class sizes are imbalanced, approximate heuristics are often employed ensure satisfaction of the volume cardinaardin)lytt) prior [TO, [9]. In particular, [19] apply efficient auction algorithms [5] to volume-constraing supervised learning. They do this by iteratively solving linearizations of a quadratic problem under volume and box constraints to reach a local solution. The authors claim convergence to a local solution due to monotonic decrease of the objective, although local solutions may be poor and convergence can be slow.
semi-
In this paper, we formulate aendinallty-constrainn program, generalization of the assignment problem. Notably, in contrast to semidefinite or spectral relaxations, our formulation is exact that has a 0 minimizer corresponding to a maximally smooth discrete label assignment. Furthermore, our method has connections to spectral graph partitioning and the mean-shift Laplace learning heuristic.
cumi-supervised learning as a nonconvex quadratic
Our method involves solving a sequence of quadratic programs via Alternating Direction Method of Multipliers (ADMM) 77), which exhibits robust convergence guarantees, having also been applied successfully to Quadratic Assignment Problems and similar Semi-Definit Program (SDP)-based relaxations of nonconvex Boolean constrained problems [24]. As we will show, the ADMM iterates can be solved efficiently, particularly when the underlying graph is sparsely connected.
Our contributions are as follows:
1. We introduce a framework derived from an exact formulation of a cardinality constrrind graph partitioning problem with supervision, non -eneeeeeeratee problem in the unlabeled data limit. We also prove sufficient conditions for exact recovery integer solutions.
2. Numerically, develop scalable and convergent iterative method based ADMM and demonstrate superior performance and scalability in low, medium, high, and imbalanced label rate and data regimes on k-NN graphs (MNIST, FaShion-MNIST, and Cifar- 10) as well as Planetoid citation networks and large-scale (160k-2.5M nodes) OGB graphs compared to state-of-the--s graph-based SSL algorithms.
3. We describe a connection to Laplace learning, and derive a simple and intuitive explanation for the efficacy of the mean-shift heuristic.
2 Preliminaries
In this section, review graph semi-supervised learning, Laplace learning, the combinatorial minimum cut problem, and an associated continuous extension.
2.1 Laplace learning
Let V = {ui, U2,..., var) denote the M vertices of the graph G with weight matrix W whose entries
my 2 0 are the edge weights between i and uy. We assume the graph is symmetric, i.e., way Wja-
We define the degree d, = Σÿ= Wij- Without loss of generality, we assume the first m vertices
l 1 {21, ....... Um } are assigned labels {y1.y2.... Nn .m
where 0 < m < M. In the context of k-class classification we take each y; to be one of the standard basis vectors (e), e e2,.... e2 of the form = (0. ...... 0, 1, 0, ... 0), i.e. a one-hot row vector. Let n denote the number of unlabeled vertices, i.e. n = M m. The problem of graph-based semi-supervised learning is to smoothly propagate the labels over the unlabeled vertices u {um+1, 2m.2..... UM

---

Given graph and set of labeled vertices, the solution of Laplace learning [38], is the minimizer of the following quadratic program with label constraints (Xo)) y/:
min XOERMXX
{ur(X] CXo) (Xo): - yi, i m)
(1)
where Xo RM C is the combinatorial graph Laplacian given by L = D- W, where D [lag(W1y/) a diagonal matrix whose clements are the node degrees, The prediction for vertex V/ determined by heuristic of thresholding the largest component of (Xo);;
arg max )- je(1....kk)
Note that Laplace learning is also called label propagation (LP) [39], since the Laplace equation asso- ciated with I can be solved by repeatedly replacing (Xo); with weighted average of its neighbors.
Let L = [ T4
Eut bu ] and Xo = [ where and correspond to labeled and unlabeled indices, respectively. For brevity, we denote X,, and Y Xx. The solution X satisfies the linear system
I X = -....
Although Laplace learning and related algorithms work well when the number of labeled examples is sufficient, these algorithms generally suffer from two drawbacks: (1.) they typically solve relaxation such that rather than predicting categorical values (e.g., binary one hot-encodings), they assign real value for each class. heuristic (usually thresholding) necessarily applied determine the predicted categorical label. (2.) In the low label rate regime, Laplace learning degenerates, yielding homogeneous predictions. Thus, thresholding results in poor prediction. In contrast, we propose an approach derived from non-degenerate problem and coupled with a method to ensure exact combinatorial predictions, removing the need for heuristic thresholding.
2.2
Graph partitioning
Given graph G = (W, V). consider the discrete, cardinality-conntrainne graph partitioning problem
min PCV Cut(P,
Σ Σ wij
s.t.
PP
mi
of
Critically, we note that this combinatorial problem is non-degenerate when m & n, if m2 < n, due to the cardinality constraint the solution [30). Algorithms and solutions to this problem have been thoroughly studied, particularly in the context of neighborhood graphs and for formulations that replace the constraint Pl my with penalty on the imbalance between partitions.
The applications of graph partitioning-insyne
methods to data science are well-known, particu- larly various relaxations of graph cut problems, including spectral methods [31 4) combinatorial algorithms [21 [3], and semi-definite programs (SDPs) [6 25). However, key drawbacks of these methods include the inexactness of the relaxation (spectral methods), high computational price due to a large number of constraints (SDPs), or slow convergence (combinatorial algorithms).
On the other hand, while exact continuous nonconvex formulations for graph partitioning have been studied [17], as far as we are aware, no attempts have been made to design efficient algorithms amenable to k-way partitioning of large-scale datasets with partial label information. In particular, the k-way graph cut generalization was studied in [77. The developed algorithms are based on a piecewise linear refinement of an initial, antinuuus-valued solution to one that is integer-valued and local minimizer of a certain nonconvex relaxation (Theorem 2.1 in their paper). These algorithms guarantee integer solution that exhibits valid cut with objective value greater than that of the continuous-valle extension used to initialize their method. However, note that these algorithms are prohibitively expensive, e.g., potentially requiring exhaustive search over 3"² feasible "path matrices".
2.3 Graph cuts and continuous quadratic programming
Here we restate the discrete graph partitioning problem in a form more amenable for continuous quadratic optimization, i.c. continuous optimization problem over R Later, we will see
3

---

that this problem bears similarities to the Laplace learning problem in that the two share the same objective, but the graph partitioning problem involves additional constraints.
For simplicity. we first introduce a bipartitioning framework, Vi(x) := {u; = 00, 0}. (x()) = {1z x = =1] characterized by binary vector E {0, 10,1 Equivalently, each binary vector determines an edge set Eg {i,,j) X; = 0, X; } connecting two subsets Vo(x), (x(x). The cardinality-constrii min-cut solution is the binary vector satistying 2, - m1
argmin min {(1as - -x Wx} x
arg
arg min x {0.1)* (G,)),,
Σ WNj-
(5)
The equality is due to both terms being equal, i.e. (IM x) T Wx = E(SEE Wij, over the set
of binary vectors. Next, note that when binary, (1M - x) TSx = for any diagonal matrix Hence, min-cut is equivalent to
((-M x) x
min
x (W + S)x
(6)
The theoretical aspects this perturbed problem were investigated in solve this problem was left as future work.
17 However, an algorithm to
For completeness, we review the nulti-partition generalization before proposing an efficient iterative scheme in Section 3 In particular, the choice of S is characterized in [[7 as way to provide tighter relaxation from the set of binary vectors the real-valued box set [0, 1jad Essentially, the term x' Sæ acts as regularizer. For instance, take S I. The maximizer of the quadratic x Sx = x x = | on the simplex {a E [0,1] : E.,, = 1} are the extreme points of the simplex, i.e. the one-hot vectors. Hager and Krylyuk 117 rigorously proved that the larger the entries of S, the tighter the relaxation, but the number of stationary points grows. The key condition that must be satisfied by S is stated in Theorem 2.1 of (17]: Sp + Sjj 2wny which ensures that the min-cut problem with cardinality constraint on V1 coincides with the following continuous quadratic optimization problem,
min (1M- - x)T(W>W" + S)x s. S = m. = [Vi MERM
(7)
Given S * Xns xn, an essential question is how to compute a solution to Note that no longer a convex problem. Intuitively, given some quadratic (e.g., parameterized by W) with a minimum in the interior of the simplex, perturbing W by results in a new, indefinite or concave quadratic with a minimum at vertex of the simplex.
Our proposed framework is based on constructing homotopy path, e.g. with S = sD for some parameter s in to find high-quality stationary points at extreme points of the simplex. In other words, our proposed method computes ar(s)) for some small sp. and then uses a(su) as initialization to reach xss) for a larger value s, until solutions are within some small radius e of an integral solution. By controlling the magnitude of s, we control the number of critical points that trap iterative methods.
We illustrate these principles in Figure [ where we visualize the level sets of the 2-d quadratic (x, = (ar 0.8)² various choices of Note that when s = O. the quadratic is convex and the minimum lies in the interior of the simplex. As s increases, the quadratic becomes indefinite, and eventually concave on the simplex (i.e. when s = 10). As s increases, the local minima on the simplex gravitate towards the "corners" (one-hot labels) until both "corners" become local minima in the extreme case.
0.2)2 s(x² + y²) the simplex {(x, y) E [0, 1] + y 1} for
3 Graph Partitioning for SSL
In this section, we generalize semi-supervised bi-partitioning (2-class SSL) to k-way partitioning (multi-class SSL). This yields constrained optimization problem over x k real-valued matrices. We generalize the previous framework to incorporate label information, introduce the conditions necessary for recovering binary-valued solutions, and develop our CutSSL algorithm.
3.1 Semi-supervised k-way partitioning
Before introducing label information, we transition from the bipartitioning to the k-way partitioning setting. The following maximization problem, introduced in [17], is interpreted as the maximization

---

Luplace leaming
211
1-05
5
220
Figure 1: Effect perturbing L by S on minimizers of (10 on the simplex. Shade level-curves denotes descent direction. Blue dots denote unique minimizers in the simplex. As the magnitude of perturbation increases, the minimzers gravitate towards the extreme points of the simplex.
of the sum of intra-partition edge weights.
tr(x T (W + S)X) s.t. X XERMX
1M m, X1, 1Ms X20 0.
(8)
Here, the entries of the vector m 1 denote the given cardinalities of each class and 1 M, the number of all examples.
To motivate the introduction of labels to the cardinality cardinality-constrinnee constrained cut problem, relate the objective of (8) with the perturbed Laplacian quadratic form:
Proposition 3.1 (Equivalent binary minimizers). Let Hg(X) = tr (C S)X) be the quadratic
form associated with the Laplacian, and let Gg be the objective of Then, we have that
Gs tr(X T (W S)
arg maammxGssM :X E 22 arg min (x( X e Ω
for all Xo E St where f (X Mxk Xi.j 10, X m).
Proof. Observe that
Hs(X) Gs())=--(X----- (X, D1vlh is constant and the minimizers and maximizers coincide.
The Laplace learning solution (3) alongside this proposition motivates the following Laplacian quadratic objective with perturbation S, which we term CutSSL. This is our key formulation.
[x(x):= = -r((X (Lu - S) tr(x' tr(xT (1
min X
(10)
s.t.
X m. X1x In, X> 0,
In practice for the homotopy path, we take S = sD, where we have for any feasible Xy f2
FX = Fo(Xa) > D1 x2 Fo(Xn) -|| Dm|]
Thus, any binary minimizer of (T0) with s brevity denote Lu,s Ln sD. For real-valued X, we have that the objective is F.(X) Fo(X) - - 1/ The quadratic term of the objective F, satisfies
also binary minimizer with 0. For
II, X,, tr(x ((1 s) W.) = 8) Σ (da):l/3,11 (x.,)s(X,,))))
Thus, we have the following natural interpretation:
When = 0, the objective mirrors Laplace learning.
When 0 < < 1, the constrained minimizer of the quadratic encourages solutions with predictions at unlabeled high-degree vertices to have small norm.
When 1, T.n.s could be indefinite or negative definite. The minimizers are extreme points of the feasible set and correspond exactly to labels.
5

---

When L..e satisfies a certain condition, recovery of exact binary solutions is guaranteed, i.c. the relaxation is exact if (s 1) + Dij) 2.. The following proposition characterizes the binary solutions to (T0) with respect to appropriate choice of 8. The proof is provided in the Appendix.
Proposition 3.2. Suppose s is chosen such that (Ln,a)is + (Lu,s)is < 2(Lu,)) for all pairs (i,j). Then every local minimizer (X) is 0 - solution.
Note that the condition is weaker than a negative definite condition of Lu,-- For instance, as + oo every extreme point of the feasible set of (TO) (every feasible 0 assignment) becomes local solution. With smaller 8, fewer these extreme points are local minimizers.
3.2 CutSSL algorithm
The problem introduced in (TOp is amenable to the alternating direction method of multipliers (ADMM) framework [], flexible approach solve non-smooth and nonconvex optimization problems by introducing "coupled" subproblems derived from a "splitting" of the primal variables. We consider the following "split" problem, introducing the variable T Roxk
((X.T))
1 tr(x (Lu,)) tr(x - B)
min X,TER=xM
2
(11)
X 1n m. X1 1n, T 0, x
Define the Lagrangian, G(X, A) to be the objective of the following problem:
trr(X x), - tr(x + + T (X - 1)) 1 - + - -1112
max min AER"X. x X.TER=X
(12)
s.t. X 1, = m X1 = In, 7 0.
In this instance, ADMM is implemented by searching for saddle points of G via the following iterates:
X(+1 arg min G(X,T,,A,) X 1n m, X1x 1n
XERIXE
741 arg min C( A.) s.t. T TERoxb
(13)
M+1 = A X T1+1
The first-order optimality conditions X are
X x= L= (B +T 1,,4 -221,)
(14)
where μn R and #22 E Ra are multipliers associated with the constraints XT1, m and X1; = 1, respectively, and Lu,- Lu,s I. The optimality conditions associated with (21
are recovered by applying the constraint X 1, m. Let Let -1, n- This yields
#1 c ( T A - -222) T
T. 1 1, m)
1 (B+ A 1,/4T ) In
(15)
1/2
The optimality condition for T yields
1 ; IIA X - = max(A, + Xx+1, 0)
T arg min T20
(16)
The algorithm is summarized in Algorithm
Detailed derivations provided in Appendix E.I

---

Algorithm CutSSL
Input: Laplacian L, labels B, initialization Xo Output: One-hot label predictions X
1: function ADMM(L.....
2: f- Xo
3: while not converged do
4: Xc+1 = T + T. 1n/41 1 1/ -A3
D A11 given by b Projection of update multipliers
15
5: T++1 <- max(A, A, + 0)
6:
A++1 A, X,41 Th+1
7:
end while
8: return Xx
9:
end function
3.3 Convergence and complexity of CutSSL
The convergence of the standard two-block ADMM for convex and nonconvex problems has been thoroughly established in the literature 6 8. Note that when s s =, 0, (IO) convex and the feasible set is non-empty. An optimal solution exists. The ADMM iterations for (1I) produce sequence {(X,, Ti, }.)]. where X, guaranteed to satisfy the equality constraints, the entries of T, are guaranteed to be positive and A, is the multiplier for equality constraint.
Generally, and as show in the Appendix, ADMM converges to a KKT point of [1] if and only if the objective, primal, and dual residuals converge
g as + co, i.e.
I++
||x T:lla,
rf [[
Tella
(17)
The iterations stop when the norms of these residuals within specified tolerance levels. cp 2 ed 2 O. One may speed up the empirical rate of convergence of ADMM by adjusting a step-size parameter associated with the Lagrangian. See the Appendix for details.
Partitioning poses a challenge from an optimization perspective, primarily due to the nonconvexity of the quadratic objective. For example, the Poisson MBO method (10) is locally convergent in the limit and incurs complexity R). where T is a bound on the number of iterations the procedure is run and O(R) (R) is the cost of solving Laplacian system. Likewise, the volume MBO method presented in [19] also claims local convergence and complexity ((oNV(loo(V + N)C) for some constant C. Preconditioned conjugate gradient
be applied to find solutions to Laplacian-like systems in nearly linear time (linear in M) (29]. Thus, the complexity of our method dominated by the primal variable update OTTR) (step 4 in Alg. 1
4 Mean-shifted Laplace learning
In the previous section, we introduced graph-cut-inspired framework for graph-based semi- supervised learning. Here we consider related problem formulation (10) such that we do not limit our solutions to lie on the simplex, and set s = 0. This is equivalent to imposing cardinality constraint Laplace learning (I]
- (OXTB) s.t. X
min XERWX
(18)
This comparison is justified with empirical evidence on MNIST, At solutions to (T)) with = 0, we observe (1.) the inequality constraints X > are inactive (2.) the multiplier μe associated with the constraint X1 = 1, has infinitesimal norm (empirically order of 10-9) (3.) the solutions to [8 and 11 differ in norm by tiny amount (order of 10 10-4).
We will show that an approximate solution to this problem a previously known heuristic, mean-shift Laplace learning. Our analysis of this problem provides new evidence to explain the empirical performance of this heuristic, while also revealing that is suboptimal in some sense.
While Laplace learning (3) exhibits excellent results at medium and higher label rates, recent work 10 has identified that the solution to the Laplace learning problem degenerates constant < M, i.c., as the number of unlabeled vertices is significantly larger than the number
7

---

of labeled vertices. Specifically, in the low label rate regime, X asymptotically depends only on the degrees of the labeled vertices of the graph in @ results in poor solution, concentrated on single class.
X Dw
de thus, thresholding as
In the nonasymptotic regime, however, X is not exactly a constant, and earlier work has demonstrated that shifting X such that the column- mennn are zero (i.e. the mean-shift) empirically corrects this issue. This is justified in Calder et al. 10 von Luxburg et al. 32 via a random walk argument.
4.1 Mean-shift as an approximate solution for cardinality-constraanedd SSL.
The problem in (8) is convex since the matrix L_ is a principal submatrix of L. a positive semidefinite matrix. Additionally, the set C. = (X X 1, m} convex and nonempty. Mean-shifted Laplace learning one heuristic to solve this problem, by performing the the following pair of steps:
1) Linearization: Solve L = B to get X. This is equivalent to vanilla Laplace learning.
2) Projection: Project X onto the set C.:
{
x = arg min
X 811 s.t. x
=m =m)
(19)
x
Applying Lagrange multipliers yields No = X.j - 1/2 ( Xis m,) Thus, mean-shift the
projection X when m 02-
This is only an approximate solution. However, is straightforward to characterize the optimal solutions of (18). which can be decomposed into the of two terms: X = Z + n 1, The first term associated with the solution to 18 for m = i... 1 Z 0. Denote the projection P= T of | tr 12 1 onto the set of n.x k matrices with mean-zero columns. Note that Z is the minimizer PL,Z"),,P))
tr(Z (PB)) and satisfies the system Z (PL,P))PB. The second term 11,m is a constant term to correct for the true value of m so that 1, = m. Thus, it is clear that to resolve the suboptimality of the mean-shift heuristic, one must apply mean-shift to the Laplace learning solution when the labels have been shifted. This can be solved with Projected Conjugate Gradient (PCG). In the following proposition, the mean-shif heuristic. Naturally, we expect that as the number of labeled vertices increases, the gap becomes smaller. The proof is provided in the appendix.
characterize optimal solutions to (18 in terms of
Proposition 4.1. Let X Runk be a solution to Laplace learning to 3), and X E Bank be the mean-shift heuristic (28) Let x² Lm)) X is a rank-one perturbution of & and ||X** XI
18). X Runk be the solution Ama (Lu) and tn 1,X. Then, Amn(ha)
|||
In the projection step, the rank-one perturbation 33) serves to adjust the column sum of X to satisfy the cardinality constraint implied by m. When thresholding continuous solutions integer predictions by comparing the entries in each row of X, the rank-one adjustment can play a crucial balancing role, particularly when m. the cardinalities of the predicted labels, are far from the prior cardinalities m. We emphasize that the term m exactly corresponds to the degeneracy of Laplace learning X.
Notably, in the low-label rate regime, the bound is dominated by the smallest eigenvalue of Tuus the denominator of <((T..). This term is intimately related to the number of labeled vertices, i.e. by interlacing [14] as well as the difference in cut and cut quality, by the above proposition. Generally, the bound gets smaller as the smallest eigenvalue of Ly increases, and this corresponds to the addition of labeled samples the label set.
In the appendix, we empirically confirm this in Fig 3 where we investigate solutions generated using the mean-shift Laplace learning heuristic and the true solution to (18) on MNIST label rates ranging from 1 per-class to 10 per-class.
Despite not resolving the issue of degeneracy in the theoretical sense of Calder et al. 11 we show in Sec. that solving (18) exactly via PCG consistently yields better results than the mean shift heuristic, at no additional computational cost. Intuitively, our analysis implics that shifting both the solution
8

---

and the labels is a superior heuristic. However, we note that while gains in accuracy of 2% are consistent in the very low label-rate regime, the improvement becomes marginal higher label rates. In contrast, we demonstrate that CutSSL, which avoids degenerate solutions via recovery of integer solutions, has consistent improvement performance across label rates.
Experiments
We evaluate our method on three image datascts: MNIST (12), Fashion-MNIST 33 and Cifar- 10 23 using pretrained autoencoders feature extractors as Calder al. [Q, see appendix for
details. We also evaluate cutSSL on various real-world networks, including the Cora citation network and the OGB [8] Arxiv and Product networks.
Table 1: Cifar-10. Average accuracy over 100 trials with standard deviation in brackets.
CIFAR-10 # LABELS PER CLASSS
1
5
10
4000
LAPLACE/LP [S
(1.3)
(2.6
(5.1
21.8 (7.4)
80.9 (0.0)
MEAN SHIFT LAPLACE/LP
(4.1)
(3.4)
(2.9)
57.0 (2.1)
81.0
EXACT LAPLACE/LP (OURS)
(4.3)
50.9
51.6
(7.9
81.1 (0.1(
LE-SSL 3
(6.1)
50.2
54.7
59.4)
80.1 (0.9)
SPARSE LP
(3.1
13.4
(8.4
(1.9)
(0.1)
POISSON I0
40.7 (5.5)
(3.9
53.8
58.3 (1.7)
80.3 (0.9)
VOLUME-MBO
50.1 (7.2)
53.8
59.2 (3.2)
75.1 (0.2)
POISSON-MBO
41.8 (6.5)
53.5 (4.4)
(3.2)
(2.2)
80.1 (0.3)
CUTSSL (OURS)
44.7 (5.9)
56.1 (3.7)
59.7 (3.1)
64.5 (1.7)
82.0 (0.2)
Image datasets We construct a graph over the latent feature space. We used all available data to construct the graph, with 70, 000 nodes for MNIST and Fashion-MNIST, and 60, 000 nodes for Cifar-10. 10. The graph was constructed
k-nearest neighbor graph with Gaussian edge weights given by Wiy = exp (-41je; - 2y || /d (v;)))) where v are the latent variables for image and (v:) is the distance in the latent space between e and its 1thh nearest neighbor. We used = 10 in all experiments and symmetrize W by replacing W with 1 {W + WT).
We compare to the state-of-the-ar unconstrained graph-based SSL algorithm Poisson Learning [10 as well variants based on the MBO procedure [9] to incorporate knowledge of class sizes. We include vanilla Laplace learning, Laplace learning with the mean-shift heuristic, and exact Laplace learning with relaxed cardinality constraints presented inspired from spectral relaxations of the min-cut problem. Laplacian Eigenmaps- [3] performs graph-base based SSL by learning linear predictor using the principal eigenvectors the graph Laplacian as features. We note that our method is directly comparable to Volume- and Poisson-MBO, which also incorporate knowledge of class sizes.
Section We also include method
Adopting a homotopy method implies that we solve a sequence of quadratic programs with 50 and use the associated solution initialize subsequent problem with > In practice, we set s = 0.1 for all experiments. The procedure presented in Alg. T is run for 100 iterations. In Table T we present the accuracy of our method on Cifar- 10 across various label rates (MNIST and IMNIST results are in the appendix). CutSSL outperforms all meth- ods across all label rates. In particular, we outperform the state-of-the-ar by 2.9% when only single sample from each class is provided and by 1.9% in the large label-rate regime.
Table 2: citation network with 169, 343 vertices and labels ("Rate=tr" means all train data).
OGBN-ARXIV, A 40
Acc. (RATE=1)
RUNTIME (S)
CUT (10")
Acc. (RATE=TR)
POISSON I00
45.72%
79.34
71.13
50.11%
GRAPHHOP- NN
34
27.36%
1878.39
94.16
34.47%
POISSON- -BO
10
46.94%
341.12
72.09
51.7%
CUTSSL (OURS)
52.37%
122.04
70.43
68.21 %

---

Table A co-purchasing network with >2M vertices and 47 labels ("Rate=tr" means all train data).
PRODUURO k = 47
Acc. (RATE=1)
RUNTIME (S)
CUT (10*)
AcC. (RATE=TR)
POISSON [0]
48.31%
113.91
117.21
52.14%
GRAPHHOP-NE NN
649
19.47%
3490.64
163.24
31.16%
P-LAPLACE 15
43.07%
91.01
132.93
52. %
POISsON-MBO 10
49.07%
412.01
91.13
56.31 %
CUTSSL (OURS)
54.22%
188.24
94.21
61.24 %
Citation networks In Figure plot accuracy and label rate for the Cora and Citeseer citation networks, demonstrating that our method gener- alizes beyond k-NN graphs. Notably, for Cora, we outperform PoissonMBO) by 7.5% label per class (see ap- pendix). We note that the trend per- sists across datasets and label rates. Interestingly, LE-SSL [3] performs significantly worse across label rates. This implies that searching near the set of binary vectors critical to achieving good predictors.
Laphce,LP
Mean-shitt LP
Paisson
Poeso-MM6O
Cu1SLL
9
380 20
(a) Cora
(b) Citeseer
Figure 2: Prediction accuracy citation networks.
Large-scale networks: To demonstrate the scalability of our method, we provide results at 1-label rate for OGB networks Arxiv (Table and Products (Table These networks contain up million vertices and 47 classes. We demonstrate state-of-the-an performance in this regime, with an improvement of 5% for both. Note that CutSSL also significantly outperforms graph neural network-basse method, GraphHop (34), designed for low label rates and which also exploits node feature information. CutSSL has double the accuracy with an order of magnitude less run-time.
Label/class imbalance: In the appendix, we also present results demonstrating performance under label and class imbalance. Our method exhibits superior robustness when either the label rate is imbalanced (different classes have different number of labels, see Tab. 5) or when the underlying partition sizes imbalanced (different classes have different number of samples, see Tab. 6
Additional experiments: In the appendix (section C.2 we demonstrate the efficacy of CutSSL at classifying samples with small "margin". This is in contrast to spectral and Laplace learning-ty ttype algorithms are known to produce predictions that "bleed" across the cut boundary. We conduct ablative studies on the graph construction and choice of S (section C.4) Convergence of CutSSL and recovery of integer solutions is empirically demonstrated in Figure
6 Conclusion
We have proposed novel formulation of graph-based semi supervised learning nonconvex continuous quadratic program that bears similarities to the mean-shift Laplace learning heuristic and graph cuts. We have presented an iterative method solve a sequence of these problems to recover discrete predictions. Numerically, we have demonstrated that our approach consistently outperforms state-of-the-an methods on semi-supervised learning problems at low, medium, and high label rates and in imbalanced class regimes. Future work includes a rigorous analysis of exact cut-based methods for graph- based semi- superviiee learning. Of particular interest are the asymptotic behavior and consistency of cut- out-based methods for graph-based SSL.
Acknowledgments and Disclosure of Funding
This work was partially funded by NSF award 221 2217058, an award from the W.M. Keck foundation,
and NSTC grant 110-2115-M-005-007--
10

---

References
[1] A. E. K. Alaoui. Asymptotic behavior of 6 p_p--dsed Laplacian regularization in semi-supervised learning. In Annual Conference Computational Learning Theory, 2016.
[2] R. Ando and Zhang. Learning on graph with Laplacian regularization. In B. Schölkopf. J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, vol- ume 19. MIT Press, 2006.
wwwpddiinnnnnnnnnnneeeeeee neurips.ce/ httpaa/s....ppppp/////////11111 ptcepppaer/200/ff1eee pdf
d87 cc685566666000544522277767686662
[3] M. Belkin and P. Niyogi. Using manifold structure for partially labelled classification. In Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS 02, page 953 333-960, Cambridge, MA, USA, 2002. MIT Press.
[4] M. Belkin and Niyogi. Laplacian eigenmaps for dimensionality reduction and data represen- tation. Neural Computation, 15:1373-1396, 2003.
[5] D. Bertsekas. The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14:105-123, 12 1988. doi: 10.1007/BFF01186476
[6] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. ISBN 0521833787.
[7] Boyd, N. Parikh, E. Chu, B, Peleato, and Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(): 1-122, jan 2011, I. ISSN 1935-8237. doi: 10. 15612200000001 Utt/htss:://ddl org/10
1561/2200000016
[8] S. Boyd, N. Parikh, Chu, B. Peleato, and J. Eckstein. 2011.
[9] Calder. Graphlearning python package, Jan. 2022. URL https://dol.org//0.
zenodo. 5850940)
[10] J. Calder, B. Cook, M. Thorpe, and D. Slepčev. Poisson learning: Graph based sume-super learning at very low label rates. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JMLR.org. 2020.
[11] Calder, D. Slepčev, and M. Thorpe. Rates of convergence for Laplacian semi-supervised learning with low labeling rates, 2020.
[12] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
[13] C. Fiduccia and R. Mattheyses. A linear-time heuristic for improving network partitions. In 19th Design Automation Conference, pages 175-181, 1982. doi: 1992
[14] Fisk. A very short proof of Cauchy's interlace theorem for eigenvalues of Hermitian matrices, 2005.
[15] M. Flores, J. Calder, and G. Lerman. Analysis and algorithms for p-hased semi-supervised learn- ing on graphs. Applied and Computational Harmonic Analysis, 60:77-122, 2022. ISSN 1063- 5203. doi: https://doi.co org/ 10. com/scienced
wwwp:wscieneee 1ttp//1..111./// 1016/j ac 2022.01 .004. URL http://wwww.cieeeedrreec...
[16] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42:1115-1145, 1995.
https://:://pp www.ntiischooooaa.aa.....aaaaaaa ortg/CorpsID:1177050 15794408
[17] W. W. Hager and Y. S. Krylyuk. Graph partitioning and continuous quadratic programming. SIAM J. Discret. Math., 12:500-523, 1999.
[18] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:221 18 18-22133, 2020.

---

[19] M. Jacobs, E. Merkurjev, and S. Esedoğlu. Auction dynamics: A volume constrained MBO scheme. Journal of Computaational Physics, 354:288-310, 2018. ISSN 0021-9991. doi: https:
//bb..ogg/00111111.....2001111.0
URL https://wwws
http://rrerttccccceieeeeeeeeeeee com/science/
articleepps//0021999117700000
[20] A. Jung, A. O. H. III, A. Mara, and S. Jahromi. Semi-supervised learning via sparse label propagation, 2016.
[21] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291-307, 1970. doi: 10. (1.002...588-7335..9970...... 1305.1990..
[22] D. P. Kingma and M. Welling. Auto-Encoding Variational Bayes. In 2nd International Conference Learning Representations, ICLR 2014, Banff, AB, Camada, April 14-16, 2014, Conference Track Proceedings, 2014.
[23] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. (0), 2009.
[24] A. Liao. Branch and bound via the alternating direction method of multipliers for the quadratic assignment problem). 2016. URL https://api swwanticscholiiiiocooo..oiioctce org org/CorpusID 160030080
[25] Ling and T. Strohmer. Certifying global optimality of graph cuts via semidefinite relaxation: A performance guarantee for spectral clustering. Found. Comput. Math., 20(3):367-421, jun 2020. ISSN 1615-3375. doi:
01007/000008-00-9442221 URL httLhtts:://dd org/10
1007/s10208 www.:-100-------001-01011- 010009199111111 09421-3
[26] B. Nadler, N. Srebro, and X. Zhou, Semi-supervised learning with the graph Laplacian: The limit of infinite unlabelled data. In Proceedings of the 22nd International Conference on Neural Information Processing Systems, NIPS 09, page 1330-1338, Red Hook, NY, USA, 2009. Curran Associates Inc. ISBN 9781615679119.
[27] Nocedal and J. Wright. Numerical Optimization. Springer, New York, NY, USA, 2e edition, 2006.
[28] S. Shekkizhar and A. Ortega. Graph construction from data by non-negative kernel regression. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3892-3896. 2020. doi: 10. 0011099CCASPP4407722000000095
[29] D. A. Spielman and S.-H. Teng. Nearly linear time algorithms for preconditioning and solv- ing symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications. 35(3):835-88) 885, 2014.
[30] N. G. Trillos, D. Slepcev, J. von Brecht, T. Laurent, and X. Bresson. Consistency of Cheeger and ratio graph cuts, 2014.
[31] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395-416, 2007,
[32] U. von Luxburg. A. Radl, and M. Hein. Hitting and commute times in large random neigh- borhood graphs. Journal of Machine Learning Research, 15551)1 2014.
URL
http:///all..org//ppprss/ss htte:/ppperr//ts///oouxrrrrrr
html
[33] H. Xiao, K. Rasul, and R. Vollgraf. mashion-mnist: novel image dataset for benchmarking machine learning algorithms. ArXiv, abs/1708.,7747, 2017.
[34] T. Xie, B. Wang, and C.-C. J. Kuo. Graphhop: An enhanced label propagation method for node classification. IEEE Transactions on Neural Networks and Learning Systems, 34(11): 9287-9301, 2023. doi: 11110//TNLSS220222.11115
[35] W. Zhang. S. Pan, S. Zhou, T. Walsh, and J. C. Weiss. Fairness amidst non-iid graph data: Current achievements and future directions, 2023.
[36] D. Zhou, O. Bousquet, T. N. Lal, Weston, and Schölkopf. Learning with local and global consistency. In NIPS, 2003.
12

---

[37] D. Zhou, J. Huang, and B. Schölkopf. Learning from labeled and unlabeled data on directed graph. In Proceedings of the 22nd International Conference on Machine Learning. ICML '05, page 1036-1043, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 1595931 1805. doi: 10. 10255111222111112222 1102482
Utt./ttts:///oi /tt.//..org//1.11/1111122.2.
[38] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the Twentieth International Conference on Interna- sional Conference on Machine Learning, ICML'03, page 912-919. AAAT Press, 2003. ISBN 1577351894.
[39] X. J. Zhu, Semi-supervised learning literature survey. Technical report, University of Wisconsin- Madison Department of Computer Sciences, 2005.
A Outline of appendix
The outline of the appendix is as follows: we first provide the proofs of the propositions presented in Sections 3 and Next, we provide additional experiments to demonstrate the efficacy of our method on other standard image and citation network benchmarks (FMNIST and FashionMNIST and Planetoid) and in the presence imbalanced labels. We also include an ablation study of S and the graph construction, and an evaluation of the cut objective for different methods. Additionally, we review two existing methods for eardinality-consrraine detailed derivations and variation of the algorithm presented in the main text which incorporates step size.
eemi-supervised learning. We also provide
B Proofs
Consider the CutSSL formulation:
F(X)= [tr(X
XX (Ir - S) - -tr(x B1}
min XERwx
2 subject to X m,
(20)
m, X1, 1,, X X 0.
The following proposition characterizes the binary solutions to (0) assuming appropriate choice of s. Proposition B.1 (Proposition 3.2). Suppose chosen such that (Lu,s)it + (Lu,s)ás < 2 2(L for all pairs (i. Then every local minimizer of F is a solution.
Proof. Suppose X is a non-binary optimal solution to (0 Assume that Xi, lies in (0, 1). The feasibility condition implies that both Xig and Xi Tie in the interval (0. 1) for some in and some in. Likewise, Xig.is (0, 1) for some i4. Repeat the argument, then there exists sequence of l nonzero entries in X, whose indices form a cycle, i.e., (i1, i2, ig.... it) and it in with I even. 5, .... The existence of cycle in X
That is, X,, (0, 1), X44424141
(0,1) for implies that we can construct X +cE feasible, where E is 0/1 matrix with Eig 1 and Eist200e11 = Clearly, we have that
E1, = 0 and E 1,- = O.
(21)
From the local optimality condition f(X EE) 2 f(X), with e - 0+, the necessary conditions indicate two conditions,
tr(ET (L - B))= 0, ur(E' LL, 2
(22)
for each E with cycle (f.....,4)) Since X a locally optimal solution, then Ly,eX B
#1 1 + Inju holds for some vectors μ1, p2, which ensures the condition tr(ET (Lu,,X .X - B)) = 0. However, according to the assumption (Lu,s) + (Lu,a)ii < 2(Lu, we have that
tr P(ELLu,s E) Σ 2(L,,))is 2 ((u,s)) <0
(23)
i.c., the conditions for local optimality violated.
13

---

Let C =
Ta Liu and Xo = [x]]] where and u correspond to labeled and unlabeled indices, Lut Lu
respectively. The solution X of the Laplace learning problem satisfies the linear system
, = B == -LWY.
(24)
Consider the cardinality constrained Laplace learning formulation
{ [(X) -2-22// tr(X L, -tr(xTB) BB}
min X X
(25)
s.t. X 1n = m
In the main text, we discussed that mean-shift Laplace learning a heuristic that recovers approximate solutions to the above convex problem for m O₃. The mean-shift heuristic corresponds to the following two-step procedure:
Linearization: Solve X, B to get X
2) Projection: Project X onto the orthogonal complement of 1, to get X = PX, where P =
7- 1,1,, First, provide detailed derivation of step 2.
We have
{
x arg min
x - - s.t. X 1, = m
(26)
Let m 0. Applying Lagrange multipliers to (19) in order solve step 2 yields
G(X,
マ || X1 + (x - m)
(27)
|| -211x
- X 111--
+ (X1) 1m
m with y R The solution (19 given by finding the l which satisfies the constraint, The partial
derivatives of the Lagrangian are
ag
(Xi, X1y) + 1y =0 X1j Xxg Pg
ax,₁
Applying the constraint E Xij = m, yields H4 = = ( X1s - m,). The projection of X onto C'm
xy= X
Xy m
(28)
Here, we characterize the connection between this heuristic and the cardinality problem. Proposition B.2 (Proposition 4.1). Let X E Raak be a solution to Laplace learning 18 X E
gaxk be the solution to (3), and X E Brnk be the mean-shift heuristic (8). Let R (L))
Annr (L..)
Ann (bu)
and in = 1T,, Then, X* is a rank-one perturbation of X and ||x XI| s k(Lu)
mm
m
Vn
|m
Consider the first order condition of 255
I B + 1,/4²
(29)
for some multiplier μ E R satisfying
m m= 11,) (B 11))
(30)
i.e. due the constraint X 1, m.
(L (B+ 1x T)
(L,) L 1nf4 1n
(31)
= =1(1, + b 11n)
14

---

25000
0.0
20000
labe deagrtmeer
323
15000
2031
10000
3000
rate
rate
Figure 3: (top) Reciprocal of the small eigenvalue of L,, (bottom) Label disagreements
The first order condition implies that X is determined by
X -L= 1,, (1, - 1,, + +1I - 11, b B
(32)
Let X denote the solution the classic Laplace learning problem: X L BT and m 1T
Also, let y = LT In and introduce the notation 1 LT In 1, y. Then, may show that X is rank-one perturbation of X,
X X= x= vmmm mm)
(33)
Informally, since L has a null vector 1,, (smallest eigenvalue 0), in the low-label rate regime, L,, is nearly singular and L,," 1,,11, corresponds a very large drift term.
Remark B.3. Denote the condition number of L, k(L.)) Amin (L.))
(my)(
It follows that
(( .m Tl] S 11
|bll -I1m- ml
k Lu) s
(34)
m ml
Remark B.4.
1 ||X - (X - ml] [1(1T)) ('ym") - m I)ll
- |mll|
K k(Lu)
m mn|
We note that M, the total number of vertices remains constant. . m, where the number of unlabeled vertices and m are the number of labeled vertices. The bound highlights the gap varies, with M fixed. As increases, decreases and k(I,)) increases (due to interlacing). Empirically, in Figure we plot the difference in integer-rounded predictions and the reciprocal of the smallest eigenvalue of L,, We note that the reciprocal of the smallest eigenvalue of L,, decays with the label rate, as does the difference in predictions.
C Additional Details and Experiments
In this section, we provide additional numerical evidence for the efficacy of our method.
See the Colab link provided the abstract for an implementation of the algorithm in Python and NumPy and the graphlearning package (9). All experiments were evaluated Colab instances. These instances were equipped with 2-core AMD EPYC 7B12 CPUs and 13 GB of ram.
We additionally explore failure cases of our method-ettt examples of data which our method incorrectly classifies; setting in which emphasizes imbalance in the label rate for each class; and an ablation study on the choice of the diagonal perturbation matrix S.
15

---

label-shift (acc 26 45)
prediction frequency
60000
vanilla (ace 16.1%)
mean (acc 94.19)
40000
20000
class label
Figure 4: Predicted label distribution on MNIST at label per class. Vanilla Laplace learning (orange) degenerate. The mean-shift heuristic (green) imposes a constraint on the predictions corresponding to balanced prior on the class distribution. Shifting the labels (blue) is insufficient to enforce the prior.
C.1 MNIST and Fashion-MNIST
For MNIST and Fushion-MNIST. used variational autoencoders with fully connected layers of sizes (784,400,20) and (784,400,35) respectively, followed by a symmetrically defined decoder. The autoencoder was trained for 100 epochs on each dataset. The autoencoder architecture, loss, and training are similar to Kingma and Welling [22
For each dataset, construct a graph over the latent feature space. We used all available data to construct the graph, with 70, 000 nodes for MNIST and for Cifar-10 10. The graph was constructed k-nearest neighbor graph with Gaussian edge weights given by
and 60, 000 nodes
Wiy- exp (-41lar zy 1211111112//// (d,)),))
where x; are the latent variables for image i, and du (zr)) is the distance in the latent space between c;; and its ttth nearest neighbor. We used 10 in all experiments and symmetrize W.
Table Average accuracy over 100 trials with standard deviation in brackets. Best is bolded.
MNIST # LABELS PER CLASS
3
5
10
4000
LAPLACE/LP 38
16.1 (6.2)
42.0 (12.4)
69.5 (12.2)
94.8 (2.1)
98.3 (0.0)
MEAN SHIFT LAPLACE/LP
(4.7)
95.7 (1.0)
(0.5)
96.7 (0.2)
98.2 (0.1)
POISSON [TO]
90.2
94.5(1.1)
(0.7)
96.7 (0.2)
97.2 (0.1)
VOLUME-MBO 19
(7.9
96.2
(6.6
96.7 (0.2)
96.9 (0.1)
POISSON-MBB 110
96.5 (2.6)
97.2 (0.1)
(0.1)
(0.1)
97.3 (0.0)
CUTSSL (S = s()
(0.1)
97.6 (0.1)
(0.1)
(0.6
98.1 (0.1)
CUTSSL sD)
97.5 (0.1)
97.6 (0.1)
97.7 (0.1)
97.7 (0.1)
(0.1)
FASHIONMNIST
LAPLACE/LP 38
(7.3)
(8.66
(7.7)
70.6
85.8 (0.1)
MEAN SHIFT LAPLACE/LP
(5.1)
(2.8
(2.5)
(1.4)
(0.2)
POISSON [T
60.8
69.6
72.4
75.2
82.4
VOLUME-MBO 19
54.7((.2)
66.1(3.3)
72.1
775.1 (1.4
POIsSON-MBO MBO 10
(5.7)
(2.9)
73.1
76.1
80.1
CUTSSL (S s/)
63.3 (4.8)
(2.1)
74.1
76.2
86.0 (0.1)
CUTSSL (S = sD)
64.3 (4.6)
71.9 (3.8)
71.5
76.6
86.1 (0.1)
In Table demonstrating improved classification accuracy and lower classification variance accross all datasets.
we present results at a variety of label rates on the MNIST and FashionMNIST datasets,
To demonstrate the degeneracy of Laplace learning and the mean shift heuristic in the low label regime, we visualize the distribution of class predictions for MNIST given I labeled sampled per class Figure 4 Vanilla Laplace learning predictions (orange) are concentrated on label '7', with very low prediction accuracy. Solving Laplace learning for shifted labels (blue) still shows an imbalanced class distribution, with slight increase in performance, whereas mean-shifted Laplace learning (green) exhibits balanced class predictions and a significant increase in performance.
16

---

CIFAR-10 We demonstrate the robustness of CutSSL to two versions of "imbalance": imbalance in the label distribution (Tab. 5 and imbalance in the underlying class distribution (Tab. Notably, our method exhibits superior robustness in both cases.
Table 5: Imbalanced label regime. Odd classes have 1 label, even classes have labels.
IMBALANCED LABELS
MNIST
CIFAR-10 FMNIST
LAPLACE/LPP
69.5
21.1
10.0
MEAN SHIFT LAPLACE
62.6
37.2
POISSON
91.1
65.1
44.6
POISSON-MBO
92.7
66.2
55.0
CUTSSL (OURS)
93.2
68.7
59.4
Table 6: Imbalanced class regime. There are 10 times as many samples for each even class than there are for the odd classes, and one labeled node for each odd class.
CLASS IMBALANCE
MNIST
FMNIST
LAPLACE/LP
54.7
38.6
18.4
MEAN SHIFT LP
92.5
64.3
42.8
POISSON
90.0
66.8
43.7
POIsSON-MBO
91.8
77.5
52.3
CUTSSL (OURS)
93.1
80.4
54.5
C.2
Graph learning identifies hard samples
Table 7: Accuracy of different method on the top 5%, 10%, 20% of samples with the smallest margin.
CIFAR- 10 MARGIN THRESHOLD
5%
10%
20%
100%
EXACT LAPLACE/LP
27.4
29.6 (4.3)
31.6 (4.1)
41.6 (4.3)
POISSON
(2.1)
28.5 (1.6)
30.1 (1.2)
40.7 (5.5)
CUTSSL (OURS)
36.2 (4.9)
43.2 (4.4)
44.5 (5.3)
44.7 (5.9)
Recall that Laplace learning solves a problem of the form
L lap B - T.
It is then necessary to map the continuous-valued predictions given by X1sp to elements in the label-set. Usually, the following post-hoc rounding step is performed:
((2) arg max (Xiap)iy-
IE.....,k
However, there one significant issue with this heuristic, as implied by proposition 4.1 in our paper. At low-label rates, L, is nearly singular and dominated by a large drift-term associated with the vector L. '1, This term is essentially a constant that is governed by the underlying graph and the distribution of the labeled vertices, but it can dominate any "useful" information and hinder the threshold heurstic. Notably, the extreme case, thresholding in the low label rate regime results in one class dominating the predictions. This is presented in figure 5, which demonstrates that when the column-argmax heuristic adopted a single class prediction dominates the rest.
This particular degeneracy is especially relevant for vertices near the decision boundary- e.g. vertices with corresponding rows in X1a that have small margin, where margin is defined
margin(i)
max Xin) jE(k]
max (Xisp) [E(
To illustrate this issue and how CUtSSI. addresses it, in Tab. we evaluate Laplace and Poisson learning (methods that produce contimuous-valud predictions) the Cifar- 10 dataset with one
17

---

sample labeled per class. We then consider the accuracy of each method on the top 5%, 10%. 20% of samples with the smallest margin. We see that CutSSL, which makes discrete predictions, performs much better on samples with small margin.
Here, provide examples of misclassified samples that lie the "boundary" of their respective partitions. The node boundary of a set V1 with respect to a set V2 is the set of vertices v in V1 such that for some vertex V2, there is an edge joining u to v. We show that the examples presented in Figure particularly in the top row for MNIST, correspond to digits which are messily written or easily confused (bottom, Fashion-MNISTY We hypothesize that these challenging samples lie on the cut- cut-boundan boundary between partitions.
loba Teciicio
9
7
2
b
3
5
7
?
(a)
(b)
Figure 5: a Random sample of misclassified images on the cut-boundary on MNIST. misclassi-
fied images the cut-boundary of Mnis..
C.3 Planetoid (Cora, Citeseer, Pubmed)
In the main text and earlier in the appendix, we provided numerical results on three popular image datasets. The graphs those datasets are constructed as kNN graphs. In this section, we evaluate our method on non-kNN graphs corresponding to citation networks, where the graph is given. In these networks, the vertices represent documents and their links refer to citations between documents, while the label corresponds to the topic of the document. Due to the smaller size of these graphs, we set 6 0.05. We show in Fig. 2 that our method continues to exhibit significant improvement, beyond the state-of-the-art on these graphs.
In T we again outperform competing methods across all datasets and label rates. For example, on Citeseer at 100 labels per class, we outperform Poisson-MBB by 9.4%.
We omit results on Volume-MBO [9 due to runtime errors when evaluating the method on these graphs.
C.4 Ablation study of S and cut objective and graph construction
The two underlying motivations of our work are that (1.) the graph-based machine learning setting necessitates the assumption that class structure is tied to the cut structure of the graph (2.) scarching for near-integer solutions when solving the semi-supervised partitioning problem is critical at low- label rates. We demonstrate this below by evaluating various choices of as well as evaluating the quality of the integer partitioning implied by the integer-rounded predictions made by various methods across datasets in T
Additionally, we discuss the choice of 5 = sD. is the primary hyperparameter of the CutSSL algorithm. As mentioned the main text, our choice of S is motivated from the perspective of regularization. A large enough choice of results in an indefinite or concave problem that has combinatorial number of local minima. By choosing an appropriate sequence of s, we can control the number of poor local minima. In Figure ((a) we demonstrate convergence with respect to the objective of (10) and (b) proximity to an integral solution with various choices s. In Figure 7 we plot various measures associated with three different sequences (sg, $1,..., ST [2] with 5g 0 and
s.
Sr 0.5. Each 8; is determined by s $t-1 + d for some fixed constant d. It can be seen that
rreaall that our algorithm works by finding solution to 10 given a particular and using this solution to initialize subsequent problem associated with s:-1
18

---

Table 8: Average aceuracy 100 trials evaluated the largest connected subgraph with standard deviation in brackets. Best bolded.
CORA # LABELS PER CLASS
10
100
LAPLACE/LP 38
21.8 (14.3)
37.6 (12.3)
51.3 (11.9)
66.9 (6.8)
81.8 (1.1)
MEAN SHIFT LAPLACE/LP
52.7 (7.6)
63.3 (6.3)
67.8 (4.8)
72.1 (2.7)
80.8 (1.1)
POISSON [0]
59.8 (7.9)
(5.8)
(2.1)
(1.8)
79.8 (1.0)
POISSON-MBO [O
59.9 (6.4)
69.1 (3.1)
72.4 (2.4)
74.3
79.2 (0.9)
CUTSSL (OURS)
67.4 (3.4)
73.2 (3.1)
75.8 (2.1)
78.7 (1.1)
85.4 (0.7)
CITESEER
LAPLACE/LP 38
(10.4)
47.6 (8.1)
(5.9
63.7
71.2
MEAN SHIFT LAPLACE/LP
56.8
56.8 (6.9)
(5.1)
71.2) (3.4)
POISSON [0]
(5.4)
(5.4)
62.7 (4.2)
(1.8)
69.4 (1.0)
POISSON-MBO 10
(8.0)
(3.2)
(1.7
63.1 (1.7)
(1.1)
CUTSSL (OURS)
(4.6)
63.4 (7.2)
66.9 (1.4)
68.1 (1.3)
76.4 (0.9)
PUBMED
LAPLACE/LP [3]
(8.88
35.7 (8.2)
(8.1)
(9.1)
(3.6)
MEAN SHIFT LAPLACE/LP
(11.1
(9.7)
(8.5
69.7
71.1)
POISSON [0]
(12.8)
(6.6)
(5.9
75.9) (3.4)
POISSON-MBO [0
(6.3
67.9 (3.4)
(3.6
76.2 (2.5)
CUTSSL (OURS)
63.1 (4.7)
70.4 (3.1)
72.8 (2.9)
74.1
78.3 (0.8)
Table 9: Average cut value, given by tr(X WX) over 100 trials evaluated with standard deviation brackets. Units are 10². Best is bolded.
MNIST # LABELS PER CLASS
1
3
5
10
MEAN SHIFT LAPLACE/LP
9.532 (141.1)
9.549 (78.3)
9.555 (49.0)
9.561 (20.5)
POISSON TT
9.539 (152.2)
9.553 (58.4)
9.557 (33.3)
9.560 (18.1)
POIssON-MBO 10
9.568 (62.5)
9.571 (1.9)
9.571 (3.2)
9.571 (2.5)
CUTSSL (OURS)
9.570 (35.8)
9.572 (5.0)
9.572 (10.9)
9.572 (1.3)
FASHIONMNIST
MEAN SHIFT LAPLACE/LP
103626.1 1 (234.3)
10.355 (158.8)
10.355 (149.5)
10.359 (112.3)
POISSON 100
10.355 (173.2)
10.352 (149.11
10.354 (145.7)
10.356 (106.5)
POISSON-MBO
10.383 (71.6)
10.387 (68.7)
10.383 (77.3)
10.385 (9T.89)
CUTSSL (OURS)
10.383 (71.2)
10.398 (70.5)
10.399 (69.5)
10.402 (42.5)
CIFAR-BB 10
MEAN SHIFT LAPLACE/L.P
7.031 (275.7)
7.910
7.011 (199.9)
7.010 (120.7)
POISSON 10]
7.0 (169.5)
6.987 (169.5)
6.993 (138.5)
6.995 (120.9)
POISSON-MBO 110
7.007 (113.8)
7.020 (47.7)
7.019 (39.2)
7,022 (46.2)
CUTSSL (OURS)
7.018 (47.6)
7.034 (40.9)
7.038 (37.8)
7.043 (17.1)
(L.) that s need not be chosen to exactly satisfy the condition in Proposition. 3.2 i.c. may be chosen
significantly less than the proposition implies recover integer solution. And (2.) our formulation reasonably robust to the choice of the sequence s, i.c. one only needs to select few values of on which to the algorithm (d can be chosen quite large). As mentioned in the main text, for our experiments we use sequences of length (i.e. 3 s).
In Table 10 we report the change in accuracy for various choices of the parameter kt, used in the (the value
construction of the underlying k-NN graph. The change is reported with respect to used in results reported in the rest of the experiments). Mean and standard deviation are provided in parenthesis over 100 trials. We observe some variation in the accuracy, however the results are mostly robust different choices of k. Notably, the relative performance remains consistent (i.c.,
19

---

5-00
1400
00
20000
1200
cut valuee
15000
1000
5000
0
20
40
60
80
100
Nteration
(a) objective of 10
(b) prediction values
Figure 6:
Cut value of class assignments with respect L. Striet descent is not guaranteed due to
nonconvexity. (b) Distribution over max; X, for various choices of on Cifar-10. Larger s leads to Boolean-valuee solutions.
dilance From 0/1 solut on
10.12
0-0.05
0=0.1
accuracy
10.38
10.36
10.34
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
(a)
(b)
(c)
Figure Comparison between different sequences of s MNIST. For various three sequences, we plot the cut objective (a), accuracy (b), and proximity to integral solution (c).
CutSSL continues to outperform the other methods). One very interesting observation is that for CutSSL, the accuracy tends improve with the value of k, although it's possible that the accuracy could deteriorate for larger values of k.
Table 10: Ablation study on neighborhood graph construction (choice of k)).
CIFAR- 10
100
EXACT LP
+1.00 (2.3)
-0.31 (2.1)
-0.47 (2.3)
POISSON
+0.30
-2.15
(2.3)
POisSON-MBO
-0.32 (2.7)
-0.55 (2.9)
-2.30 (3.1)
CUTSSL (OURS)
-0.21 (2.3)
+2.16
+0.64 (2.1)
In Table 11 we evaluate the effect mechanism used construct the graph MNIST. First, evaluate two variants of weighting edges of the KNN-based method adopted in the main text. Singular refers weights of the form Wiy 1/1 x 2y 1l2, where x; and xy are the features of the i-th and j-th data points. Uniform refers to wij = 1, i.c. an unweighted graph. In the third column, we evaluate more sophisticated method for graph construction based on Non-Negative kernel regression (NNK) (28). 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 out-performs Poisson-MBO for the different graph weighting methods and NNK construction.
D Details of Previous work
In this section, we provide further details on two state of the art methods for volume-preserving label refinement.
20

---

Table 11: Ablation study on neighborhood graph construction (choice of W'y)).
METHOD
(1.4) KNN (GAUSSIAN)
KNN (SINGULAR)
KNN (UNIFORM)
NNK
EXACT LP
91.0 (4.7)
89.7 (2.8)
89.8 (2.3)
91.7 (1.1)
POISSON-MBO
96.5 (2.6)
94.2 (2.9)
95.7
CUTSSL (OURS)
97.5 (0.1)
95.8 (2.6)
(2.0)
98.5
D.1 PoissonMBB 10
T0 propose graph-cut method to incrementally adjust a seed decision boundary so as to improve the label accuracy and account for prior knowledge of class sizes. The proposed method applies several steps of gradient descent on the graph-cut problem:
1 min _ [Vlllla + EI (u(z.) - uyl²
(35)
=1
More concretely, the time-spitting scheme that alternates gradient descent on two energy functionals employed:
1 1 Vull (xx)= E, (u):
Un 7) :((rg)
11
j=1
(36)
(u(2;) uz) E2(w) = =1
The first term E₁ corresponds to the Poisson learning objective. Gradient descent on the second term Ez, when 7 > is small, amounts to projecting each u(x;) E I2* to the closest label vector ej E Sz, while preserving the volume constraint (u) = b. This projection is approximated this by
the following procedure: Let Proj(Ss) R + Sy be the closest point projection, let $1, , > 0 be positive weights, and set
S
++ (xx)
Projs. ( sk)n (x:))
(37)
where diag(s1, .... 8&) is the diagonal matrix with diagonal entries 51, 8k. We use simple gradi- ent descent scheme to choose the weights 8,,..., 8g > 0 so that the volume constraint (u' ) = holds.
Note that Poisson MBO requires a fidelity parameter μr. two parameters Ninner and Nouters and time step parameter r, and additional clipping values Smin and Smaz-
D.2 VolumeMBO 19
The work of 19 provides an alternative way to enforce explicit class balance constraints with volume constrained MBO method based auction dynamics. Their method uses graph-cut based approach with Voronoi-cell based initialization.
More concretely, the solve volume-constrained cut problem via successive linearizations. Le.. each iteration of the algorithm necessitates finding a solution to the following problem:
max - WZ 2
(38)
21 1, 22 0, z
E
Algorithm derivations
Here, we describe algorithms referenced in the main text, including a projected CG method for solving (T8) and a variant of the ADMM method introduced to solve (8) that incorporates a step size parameter.
21

---

E.1 Detailed derivation of iterates X, P1, P2 in Sec. 3.2
Here, we provide the details on the derivations of the ADMM iterates and Lagrange multiplier updates Mi and A2.
First, define the Lagrangian, G(X, A,) to be the objective of the following problem:
max AERuX X,TER=x 2
min 11(X" Tu,,)) tr(x B)
(39)
+ tr tx -X-T))
2 || - -T'1
s.l. 1x1, 1, m, X1, = 1,; T 2 0.
The first-order optimality conditions on X are
0 L 3 (X T) 1 + p21x
(40)
x L= LB +T A-1,4 - p21)),
1,
where 14 R and #22 R are associated with the constraints X 1n m and X1, 1, respectively, and Lu,s La.e + I. The optimality conditions associated with (11 p2) are recovered by applying the constraint X 1, m.
X 1'1,
=B A - 1n/1 - 1211) 1 In
(41)
= =B - A 1244 -2211) L In
Let c = 1
Solving for pl,
+B+T-2 - - -221, u,s In - -m- m
(42)
and
141 = c [( + A 221 I m)
(43)
Similarly,
1, X1
= -[n]]
[ + (
- 1n44 - 1121% 1
(44)
I + A A 1 122 1)11
Solving for P2,
(B T A 1n - Lu, = k112
(45)
and
1/2 (B T A - 1, T) - Iiuss 1n
(46)
E,2 ADMM with adaptive step size for CutSSL
In this section, we introduce variation of the algorithm presented in the main text. Here, we augment the algorithm with an additional tunable parameter B. This parameter offers flexibility depending on structure of the problem. In particular, the update to X is characterized by a linear system with matrix Lu.s + 31. To ensure efficient computation of its inverse, 3 needs to be chosen sufficiently large. However, the price of large 3 is convergence an integer solution. This tradeoff needs to be carefully considered in the context of the graph and the label rate when selecting 3. For our experiments, choose 3 1.
One may speed up the empirical rate of convergence of ADMM-type algorithms by integrating an adaptive step-size with the quadratic dual term in the augmented Lagrangian.
First, introduce multipliers 141 E R U2 RR. v R and recall the Lagrangian associated with 20
1
uT (X 1, m) ttr X). G(X, pi, H2, v2, tr( XX,o)) tr B) po (X1: 1,,) (a:))-5(
(47)
22

---

The KKT condition of X in (7 is
V LugX 1nf4] - 12l 2 0,
(48)
and X.j = 0 must hold for those (i.j) with Vij > O.
As mentioned in the main text, ADMM is carried out reach saddle point of max minx,r 9pl T, A) where
3 1|x TIE
((X,7,A) = - 1r((XT T,, -trxx)))rxXX tx (T)) +
(49)
subject to
T 2 0, 01, = - X 1a
(50)
To implement the update of X, we observe that the optimality condition of X is
Lu,
1, - 122k 0
(51)
Decompose X. X Xo + X1, where X1 is the fixed matrix X, = n " This decomposition implies that Xo has sum-zero rows and columns, i.e. Xplı and Xo 1n determine Xo from
Hence, we can
Lo + 3X0 = ln44 + #222 L,,, - 3X + 3T A B.
(52)
Apply the projections = T- -1,1, / and P3 1x /k: to remove the column and row sums on both sides (to eliminate 141 and 112):
Xo = (PiLu, 3P)) Lu, - 3X, + 3T - B)
-
(53)
Next, the update of T and A proceed as before:
T - max(3 6 - A + X,)), A+ 3(x T)
(54)
Once ADMM converges, i.e., || - T|| 0, according 55 and T 2 O, have that Asj and Ag holds for Xij >> 0. Additionally. by (51). we have
L - B 1, 12l, =-200,
(55)
i... we reach a KKT point associated with the condition (48)
E.3 Projected Conjugate Gradient for Laplace learning with cardinality constraints
Consider the problem
min X XERaX [(x) tr( L, - tr(x B)
{
(56)
s.t. X 1 m
In practice, large-scale Laplacian linear systems are typically solved using preconditioned conjugate gradient. Given the associated -quality-oonstrained problem
min XX I,,X (X, B)
(57)
s.t. X 1, =
One practical modification conjugate gradient involves first choosing a feasible initialization Xo satisfying 1,, m and running projected conjugate gradient Chapter 16.3 [27], ensuring that intermediate residuals-updar directions-Ii the orthogonal complement of 1,, Termination determined according the residual.
23

---

Limitations and Broader Impact
Here, we list several limitations and briefly touch upon the broader socictal impact of our method.
Underlying graph structure: Much of this work relies the structure of the underlying graph. In this work, we explored the applicability of our method k-NN graphs, generated from neural network-derived features and citation networks.
The choice of S = sD is one heuristic that satisfies the conditions outlined in Hager's paper [7.. We are currently exploring the effect of different choices of S the convergence and overall efficacy of our method. Additionally, it is interesting to consider how the graph structure, number of unlabeled and labeled nodes might inform better choices of S.
Regarding the broader societal impact of our method, we have introduced a new method for graph learning that improves on the state of the art across multiple label-rate regimes. The development of such methods has positive and negative ramifications for civil liberties and human rights. While the positive ramifications are relatively clear-models which require less data are cheaper to train immediately obvious. The
and are generally "lower-impact" the negative consequences above question explored in greater detail in the context sume-supereised graph learning in Fairness Zhang et al. [35]. The principal claim made by Zhang et al. 351 is that when quantities of unlabeled data are provided, label propagation may be modified to improve faimesss
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We confirm that the claims made in the abstract and introduction are accurately justified by experiments and theoretical results presented in the main text.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have included a discussion on the limitations of our method in section Fin in the appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification: For each theoretical statement, we provide a complete proof in section in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have taken steps to ensure reproducibility, e.g. by providing the implemen- tation of the core algorithm and experimental setup in Colab.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: An implementation of the core algorithm and experimental setup is provided in a footnote in the abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Policy)lyyyyyyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppgpuuiiieeeee /otpc//uuuieeeeoeuuuuiiiiiii
(CodeSubiisss wwtauubmmsssooni ssiiiiolcccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details provided in section Cin the appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard deviations are provided for the statistics reported the main text.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The details of the computational resources are provided in section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://awwwwga.cccpaaaaaa//ctaaa
Answer: [Yes]
Justification: We confirm that the research conducted in the paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have included discussion of the broader impact of our work in section in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We standard image, citation, and product network benchmarks to evaluate our method.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We have included citations to benchmarks and code where appropriate.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
29

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Beyond code to reproduce method, have not introduced new assets in this work.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
30

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "vErFYzAHmo", "reviewer": "Reviewer_5yWx", "summary": "The paper introduces CutSSL, a novel framework for graph-based semi-supervised learning (SSL). The authors address the limitations of Laplace learning algorithms, particularly their poor performance at low label rates and in imbalanced class scenarios. CutSSL leverages continuous nonconvex quadratic programming to achieve integer solutions, inspired by a cardinality-constrained minimum-cut graph partitioning problem. The framework utilizes the ADMM for robust and efficient problem-solving.", "questions": "1. Can you provide some theoretical analysis on why the proposed method works when the label rate is low or unbalanced?\n\n2. How do recent GNN-based methods perform when compared with your proposed method?\n\n3. How long will the proposed method run on some ogbn datasets you used in the experiments?\n\n4. How sensitive is CutSSL to its hyperparameters? Could you provide an analysis or guidelines on setting these parameters?\n\n5. How does CutSSL perform on different types of graph construction methods beyond the kNN graphs tested in the paper, still using the MNIST datasets instead of the real-world graph datasets?", "limitations": "The authors have addressed some limitations of prior methods, particularly the degeneracy of Laplace learning at low label rates and in imbalanced class scenarios. However, the paper could benefit from a more detailed discussion of the following:\n\nRunning Time Overhead: The continuous nonconvex quadratic programming approach may introduce computational overhead. A comparison of actual computational costs with other methods would be useful.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality: The paper introduces a fresh approach to graph-based SSL by framing it as a continuous nonconvex quadratic programming problem, a novel perspective compared to traditional Laplace learning methods.\n\nQuality: The theoretical formulation is robust, and the use of ADMM for solving the quadratic programs is well-justified, offering solid convergence guarantees.\n\nClarity: The paper is well-structured and clearly explains the motivation, methodology, and contributions. The connection between their method and existing heuristics like mean-shifted Laplace learning is particularly insightful.\n\nSignificance: By addressing the degeneracy of Laplace learning at low label rates and in imbalanced settings, the paper tackles a significant challenge in SSL. The performance improvements on various benchmark datasets highlight the practical relevance of their approach.", "weaknesses": "Theoretical analysis: The paper would be better if more theoretical analysis could be provided on why the proposed method works when the label rate is extremely low or unbalanced. It is quite unclear on the theoretical motivation behind this proposed method.\n\nExperimental Validation: While the results are promising, the experimental setup could benefit from a more extensive comparison with a broader set of baseline methods. Including more recent graph-based SSL algorithms, especially those GNN-based methods would strengthen the empirical validation.\n\nScalability: Although the authors claim that their method scales well to large graphs, a detailed analysis of the actual runtime comparisons with other methods would be beneficial.\n\nParameter Sensitivity: The paper does not discuss the sensitivity of CutSSL to its hyperparameters. An analysis of how different parameter settings affect performance would help in understanding the robustness of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n***Theoretical analysis in low-label rate regime***\nWe 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.\n\nHowever, 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. \n\n***GNN-based methods***\nIn 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. \n\n***Runtime analysis***\nWe 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).\n \n***Choice of hyperparameter / sensitivity***\nWe 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$).\n\n***Beyond KNN-Graphs***\nThanks 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$. \nIn 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.  \nWe thank the reviewer for this suggestion and we will add this experiment to the supplement in the final version of the paper.\n\n| Method    | KNN (Gaussian) | KNN (Singular) |KNN (Uniform) |NNK |\n| -------- | ------- |------- |------- |------- |\n| Mean shift Laplace | 91.0 (4.7)    |  89.7 (2.8)  | 89.8 (2.3)    | 91.7 (1.1)    |\n| PoissonMBO | 96.5 (2.6) | 94.2 (2.9) | 95.7 (1.6) | 97.3 (1.4)  |\n| CutSSL    | 97.5 (0.1)    |  95.8 (2.6)    | 96.4 (2.0)    | 98.4 (1.5)    |\n\n[1] Shekkizhar and Ortega, Neighborhood and Graph Constructions using Non-Negative Kernel Regression, ICASSP, 2020", "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": "", "extra_scores": {}}, {"review_id": "PZylgakXCm", "reviewer": "Reviewer_Gcf5", "summary": "The paper proposes an approach for graph-based semi-supervised learning which is based on a cardinality-constrained extension of the classical Laplacian learning approach due to Zhu et al. Known theoretical limitations of standard Laplacian in the low-label rate regime motivates the approach. Theoretical properties of the approach are studied, including a sufficient condition for avoiding the need for rounding solutions and a practical optimization technique is provided for the cardinality-constrained Laplacian objective. Experiments demonstrate empirical advantage in the low-label rate regime without deterioration in standard regimes, and gains in the class imbalance regime. A connection is established to the mean-shift heuristic.", "questions": "- How can the cardinality constraints for different classes be known/estimated in practice?\n- Line 28: \"thresholding can further exacerbate the aforementioned degeneracy.\" Is there a reference or theoretical justification for this? Further elaboration on how thresholding exacerbates degeneracy would be helpful.\n- $0 − 1$ minimizer, solution, assignment $\\rightarrow$ $0$-$1$\n- Line 39-40, it would be good to summarize what the connection is.\n- What is the difference (if any) between formulations (8) and (9)?\n- Is the (smallest) $s$ satisfying Proposition 3.2 easy to compute practically?\n- Line 195: \"The convergence of the standard two-block ADMM for convex and nonconvex problems has been thoroughly established in the literature\". What is the relevant convergence rate for the current non convex problem?\n- Line 232: \"Our analysis of this problem provides new evidence to explain the empirical performance of this heuristic, while also revealing that it is suboptimal in some sense.\" Can you elaborate on this? Proposition 4.1 seems to imply that solutions of mean-shift heuristic are close to cardinality constrained Laplace learning (17).\n- Reference [8] is incomplete.", "limitations": "The authors note that a rigorous theoretical analysis of exact cut-based methods is missing and note more limitations in a dedicated section in the appendix.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper studies the fundamental problem of semi-supervised learning in important low label rate and class imbalance regimes, which have important practical consequences (excess unlabeled data does not become a disadvantage; fairness).\n- The overall approach is a principled extension of Laplace learning to cardinality constraints with optimization techniques for the resulting non-convex objective.\n- The experiments indicate practical usefulness of proposed approach.", "weaknesses": "- There is limited theoretical evidence for the claims that the proposed cardinality-constrained graph partitioning approach resolves the issues of low label rate and class imbalance.\n- $s$ seems to be an important hyperparameter in the approach but is set to a constant value 0.1 without adequate justification.\n- The connection to mean-shifted Laplace learning seems somewhat unclear. One, it is not clear if solution for (17) is close to CutSSL. Second the guarantees seem to be weak in the low-label rate regime (the bound connecting the two methods diverges in the regime of interest).\n- I find it surprising that label/class imbalance experiments are relegated to the appendix despite being a repeated claimed contribution, and also there does not seem to be theoretical evidence for better performance in this regime either.\n\n-----------------------------------------------------------------------------------------------------------------------------------------------------------\nPost-rebuttal: Some of the above concerns (role of $s$ and connection to mean-shifted Laplace learning) have been addressed in the rebuttal and I have increased my score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n***Choice of S***\nWe 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.)\n\n***Connection to mean-shift Laplace learning and Proposition 4.1***\nThis 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.\n\nRegarding 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. \n\n***Label/class imbalance performance***\nWe 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. \nWe 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. \n\n***Additional questions***\nWe 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.\n\n_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$.\n\n_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.\n\n_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.\n\n_(8) and (9):_ They are equivalent by proposition 3.1.\n\n_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$.\n\n_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.", "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": "", "extra_scores": {}}, {"review_id": "Ab878SgZId", "reviewer": "Reviewer_aiM6", "summary": "The paper considers the task of semi-supervised learning under cardinality constraints and proposes a framework based on a reformulation into a non-convex constrained quadratic program. The authors provide sufficient conditions for the exact recovery of integer solutions. Moreover, they present an algorithm called CutSSL which is based on the ADMM method to optimize the non-convex objective, which is shown to converge to a KKT point of their objective. \n\nThe paper also shows the connection of their framework to Laplace Learning, which provides an explanation for the efficacy of the commonly used mean-shift heuristic. The method is evaluated on three image datasets, citation networks as well as other large scale networks. The proposed approach consistently achieves superior results in terms of accuracy compared to the competing methods, while being in the same order of magnitude in terms of runtime compared to the fastest method.", "questions": "See weaknesses section.", "limitations": "The authors discuss limitations of the approach, regarding the dependence on the choice of underlying graph structure, in the appendix.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a new graph-based framework as well as an iterative algorithm which is widely applicable.  In the experiments, the approach is shown to consistently outperform state-of-the-art methods on a wide range of datasets including image datasets and large scale networks.", "weaknesses": "It was not clear to me how exactly the sequence of s values is chosen. In the experimental section it says that s=0.1. I assume this is a typo since it would mean that s is kept fixed after the first step. What is meant here, the maximal s value (denoted s_T in the appendix), or the difference between s values (denoted d in the appendix)? Also, is the sequence of s values chosen in advance or is there some criteria to stop increasing the s values?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments. Below we comment on the choice of the hyperparameter $s$.\n\n***Choice of s***\nThanks 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$).\n\nGenerally, 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.", "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": "", "extra_scores": {}}, {"review_id": "L7Um8tVfYV", "reviewer": "Reviewer_8RfG", "summary": "In this submission, authors proposed a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming.", "questions": "Please clarify the motivation and contribution problem mentioned above.", "limitations": "Some limiattions are discussed in appendix.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper studies the graph-based semi-supervised learning problem, which has attracted many attentions.  In this submission, authors proposed a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming. Experiments show that the proposed CutSSL framework significantly surpasses the current state-of-the-art on k-nearest neighbor graphs and large real-world graph benchmarks.", "weaknesses": "There are many problems in this article. The most problem is that the motivation and contribution are unclear. At the beginning of abstract, authors argue that Laplace learning algorithms for graph-based semi-supervised learning have been shown to suffer from degeneracy at low label rates and in imbalanced class regimes. Then, they propose the CutSSL, a framework for graph-based semi-supervised learning based on continuous nonconvex quadratic programming. Although experiments validate the superiority of the proposed CutSSL against competing method across a variety of label rates, class imbalance, and label imbalance regimes (by the way, what is the difference between class imbalance and label imbalance), I cannot find the relationship between the motivation and the technical design of CutSSL. Moreover, the meaning of the term \"Continuous Partitioning\" in title is also unclear. For the proposed CutSSL, according to the summarized contributions at the end of Section 1, the main contribution of CutSSL is the mathematical framework and its ADMM-based optimization algorithm. These contributions have little to do with the aforementioned motivation of this paper. From a technical point of view, the main contribution of the CutSSL is Eq.(9), where S=sD. Then, another contribution is how to optimize this formulation, which is presented in Section 3.2. Note that in Eq.(10), there are only two matrix parameters to be optimized (i.e., X and T), but it is hard to find throughout this paper that how to determine s and B. Similar problems exist in many places. Ref.[16] is the main reference of this paper, but do not rely on the notations or backgrounds in it too much. Besides, there is a recent review named ''Graph-Based Semi-Supervised Learning: A Comprehensive Review'' published in TNNLS is not mentioned in this paper, which means a literature review should be carefully conducted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n***Motivation of CutSSL***\nIn 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.\n\nTo 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.\n\n\n| Method    | MNIST | F-MNIST |  CIFAR10 | \n| -------- | ------- |------- |------- |\n| Laplace/LP |   16.1 (6.2)  | 18.4 (7.3)    | 10.4 (1.3)    | \n| CutSSL    | 97.5 (0.1)   |  64.3 (4.6)   | 44.7 (5.9)   | \n| Cut    |  95.9 (0.0)  |  62.7 (0.0)   | 41.1 (0.0)   | \n| SC    | 92.6  (0.0) |   60.5 (0.0)  |  35.3 (0.0)  | \n\n***Clarification of the term Continuous Partitioning***\nThank 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. \n\n[1] Pardalos, Continuous Approaches to Discrete Optimization Problems, Nonlinear Optimization and Applications, 1996.\n[2] Discrete Optimization via Continuous Relaxation, Symposium on Bridging Continuous and Discrete Optimization\n\n***Clarification of the class and label imbalance and notation***\nTo 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).\n\n***Choice of $s$***\nThanks 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$).\n\n\n***Additional references***\nThanks for notifying us of this missing review. We have added it to our paper. It will appear in the final version.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for carefully reading our work and for their constructive suggestions and comments. We have added individual responses and several additional experiments suggested by the reviewers. We will incorporate these in the final version of the paper. Below, we summarize the main contributions of the paper and expand on the choice of s parameter and introduce two new experiments based on discussions with the reviewers.

***Summary of contributions***
In contrast to Laplace learning, which is degenerate in the low-label rate regime, we consider a framework that is nondegenerate, even without any labels (the minimum cut problem 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.

Finally, 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. We consider guarantees about the generalization capability of our method to be an important future direction, but out of the scope of this work.

***Choice of $s$***
Several reviewers had questions regarding the choice of the $s$ parameter first introduced in equation 7 section 2.3. 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 of $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 experiments***
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 reviewers for this suggestion and we will add this experiment to the supplement in the final version of the paper.

| Method    | KNN (Gaussian) | KNN (Singular) |KNN (Uniform) |NNK |
| -------- | ------- |------- |------- |------- |
| Mean shift Laplace | 91.0 (4.7)    |  89.7 (2.8)  | 89.8 (2.3)    | 91.7 (1.1)    |
| PoissonMBO | 96.5 (2.6) | 94.2 (2.9) | 95.7 (1.6) | 97.3 (1.4)  |
| CutSSL    | 97.5 (0.1)    |  95.8 (2.6)    | 96.4 (2.0)    | 98.4 (1.5)    |

In the next experiment, we provide additional motivation for CutSSL. 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.

| Method    | MNIST | F-MNIST |  CIFAR10 | 
| -------- | ------- |------- |------- |
| Laplace/LP |   16.1 (6.2)  | 18.4 (7.3)    | 10.4 (1.3)    | 
| CutSSL    | 97.5 (0.1)   |  64.3 (4.6)   | 44.7 (5.9)   | 
| Cut    |  95.9 (0.0)  |  62.7 (0.0)   | 41.1 (0.0)   | 
| SC    | 92.6  (0.0) |   60.5 (0.0)  |  35.3 (0.0)  | 


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

Meta-review: This paper proposes to formulate the graph-based semi-supervised learning problem as a continuous nonconvex quadratic program which exactly recovers integer solutions under proper conditions. An ADMM-type algorithm is developed for model optimization, with actual performance and scalability evaluated under a wide spectrum of label rates and data regimes on k-NN graphs. Also, the proposed formulation has been shown to bear similarities to the mean-shift Laplace learning heuristic and graph cuts.

The paper received four detailed reviews. Three reviews are in favor of accepting this work, while one review is inclined to reject it. After discussions, the reviewers reached a majority consensus that the proposed continuous partitioning strategy for graph SSL is novel and interesting, and the experimental results validates the practical usefulness of approach. One of the reviewers expressed a major concern regarding the discrepancy between motivation of study and theoretical justifications of the problem formulation in Eq. (9), which the authors did not deny and I agree indeed has room for imrovement. Also, math seems less rigurous in some places. For an instance, in Line 160, the matrix-vector product $Sm$ looks problematic as $S \in R^{M\times M}$ and $m\in R^{k}$ are generally incompatible in size.

Based on the reviews, authors responses and post-rebuttal discussions, it was assessed that this submission makes a sufficiently novel and solid contribution to the addressed problem. So the resulting sentiment is that the paper can be accepted given room in the program. The authors are encouraged to address the issues raised in the reviews as much as possible in the revised paper.
Decision: Accept (poster)