Semi-supervised learning with max-margin graph cuts

In plain words

Labeling data is expensive, so usually you have a few labeled examples and many unlabeled ones. This paper's method first spreads the known labels across a graph that connects each point to its nearest neighbours, so that points that are close to each other tend to receive the same label. Each point ends up with a score: a score near zero means the method is unsure, and a score whose size is close to one means it is confident.

Second, it trains a standard max-margin classifier (a support vector machine) on only the points whose scores are confident enough. The classifier can use a kernel to draw curved boundaries. The method is convex in both steps.

The authors compare it with manifold regularization of SVMs, which instead pushes the classifier itself toward smoothness over the graph. On a toy problem and three public tables of data, the authors report that their method usually gives fewer errors than that baseline.

TL;DR

• Two stages: a regularized harmonic function labels every point on a k-NN graph §2 eq. 5 eq. 6; then a hinge-loss, kernelised max-margin classifier is fit only on points with |score| ≥ ε §3 eq. 7 eq. 8.
• The inference stage is convex, which is why the method avoids the non-convex hat-loss of semi-supervised SVMs §4.1.
• Author-reported: lower misclassification than manifold-regularized SVMs in 29 of 36 UCI settings (3 datasets, 4 label fractions, 3 kernels) fig. 4.
• A generalization bound is proved §5, but the authors say it is not used to pick the parameters; they tune on a validation fold §5.1.
• No official code found.

Problem

Semi-supervised learning should use unlabeled data, but the two standard max-margin approaches have drawbacks. Semi-supervised SVMs with the hat loss on unlabeled points are non-convex and only approximately solvable §4.1. Manifold regularization of SVMs is convex, but the authors show that with a restricted function class (linear, or cubic kernels on their toy problem) its smoothness penalty can fail to find the correct boundary: for the two-cluster example, its discriminator does not change with the manifold weight, so it cannot separate the clusters for any setting (in the linear case analysed) §4.3 §6.1 fig. 2.

The paper's assumptions: the graph is built from the features (k-NN with Gaussian weights) §6.2; labels are binary for the classifier; the labeled set is small (1 to 10 percent of the training data in the experiments) fig. 4.

Method

Overview. The method has two steps §3. Step 1 computes a regularized harmonic function on the data graph, which gives each point a real-valued score ℓ_i. The sign of ℓ_i is an inferred label and |ℓ_i| is a confidence §2 eq. 4. Step 2 trains a max-margin discriminator with hinge loss on the inferred labels, but only over points with |ℓ_i| ≥ ε §3 eq. 7. The parameter ε is a threshold on confidence. The regularizer γ_g on the graph controls how fast confidence decays with the number of hops from labeled points §2. Setting γ_g = 0 gives the ordinary harmonic solution; γ_g = ∞ gives supervised SVM §2 §3.

Step 1: regularized harmonic function §2.

1. Let W be the matrix of pairwise similarities w_ij, L = D − W the graph Laplacian, and l, u the labeled and unlabeled index sets §2. The text uses ℓ for the vector of scores, which equals the observed label on labeled points.
2. Solve the quadratic program in eq. 5 with the labeled entries fixed. Its closed form is eq. 6: the unlabeled scores solve a linear system with matrix (L_uu + γ_g I), which is sparse when W is sparse §3.
3. The paper also gives the random-walk view with a sink probability of γ_g / (d_i + γ_g) at each step §2 eq. 3. This is interpretation only.

Step 2: max-margin discriminator §3.

4. Keep the labeled and unlabeled examples i with |ℓ_i*| ≥ ε. Use sgn(ℓ_i*) as their label §3 eq. 7.
5. Minimize the hinge losses over these examples plus γ times the RKHS norm squared eq. 7. The hinge loss is V(f, x, y) = max{1 − y f(x), 0} §3.
6. By the representer theorem, the optimum has the form eq. 8: a kernel expansion over the kept examples only. Optimize the coefficients α over those examples, not over all n points §3.

# Max-margin graph cuts  [§3] [eq. 5] [eq. 6] [eq. 7] [eq. 8]
# Input:  points (n, K); labels observed where labeled is True
# Output: alpha (len(kept),); f(x) = sum_i alpha_i k(x_i, x) over kept

def max_margin_graph_cuts(points, labels, labeled, gamma, gamma_g, eps):
    # Sparse, weighted 5-nearest-neighbour graph  [§6.2]
    weights = knn_adjacency(points, num_neighbors=5)
    # Solve (L_uu + gamma_g I) scores_u = W_ul scores_l  [eq. 6]
    scores = regularized_harmonic(weights, labels, labeled, gamma_g)
    # Labeled points keep their observed label, so they pass  [eq. 5]
    # Keep only examples whose inferred label is confident  [§3] [eq. 7]
    kept = [i for i in range(len(points)) if abs(scores[i]) >= eps]
    # Hinge-loss kernel classifier on kept points with inferred signs  [eq. 7]
    alpha = fit_hinge_classifier(
        points[kept], sign(scores[kept]), gamma)
    # alpha indexes kept points only (representer form)  [eq. 8]
    return alpha, kept

Key equations, as written in the paper:

\min_{\boldsymbol{\ell} \in \mathbb{R}^n} \ \boldsymbol{\ell}^\top (L + \gamma_g I) \boldsymbol{\ell} \quad \text{s.t.} \quad \ell_i = y_i \ \text{for all } i \in l eq. 5

\boldsymbol{\ell}_u = (L_{uu} + \gamma_g I)^{-1} W_{ul} \boldsymbol{\ell}_l eq. 6

\min_{f \in \mathcal{H}_K} \ \sum_{i : |\ell_i^*| \geq \epsilon} V(f, \mathbf{x}_i, \operatorname{sgn}(\ell_i^*)) + \gamma \|f\|_K^2 eq. 7

f^*(\mathbf{x}) = \sum_{i : |\ell_i^*| \geq \epsilon} \alpha_i^* k(\mathbf{x}_i, \mathbf{x}) eq. 8

Here ℓ* is the solution of eq. 5 and V is the hinge loss. The paper's synthetic test uses the same algorithm with linear, cubic and RBF kernels fig. 2.

Relaxed (soft-label) variant, used only in the analysis §5. For the bound, the paper replaces the hard constraints by a quadratic penalty: minimize (ℓ − y)ᵀ C (ℓ − y) + ℓᵀ L ℓ, where C_ii = c_l on labeled points and c_u otherwise, and y_i = 0 on unlabeled points eq. 16. The bound assumes c_l = 1 and c_l > c_u §5, Lemma 2. The experiments do not use this variant; the authors say so explicitly §7.

Hyperparameters

Results

Author-reported. Setup: 3 UCI ML repository datasets (letter recognition, digit recognition, image segmentation), converted to binary problems; misclassification errors in percent, averaged over all binary problems in each dataset; labeled fraction L from 1 to 10 percent; linear, cubic and RBF kernels; baselines are SVM (supervised) and MR (manifold regularization of SVMs) §6.2 fig. 4.

Full table as printed in the paper fig. 4. Bold marks the lowest error in each three-method group, as in the original.

• Headline: max-margin graph cuts (GC) beat MR in 29 of 36 settings §6.2 fig. 4. Counting the table gives the same 29 of 36.
• Authors note the lowest errors are usually at linear and cubic kernels, and that GC improves most over MR in those settings §6.2.
• Synthetic problem (two labeled points, two clusters): GC gives max-margin boundaries that interpolate from supervised to semi-supervised as γ_g decreases; MR with linear or cubic kernels cannot separate the clusters for any γ_u; with the RBF kernel MR and GC look similar §6.1 fig. 2. This is qualitative; no error numbers are given for the toy problem.
• Thresholding ε: in the UCI setting it lowers training and test error in the authors' runs, shown for three letter problems averaged over 50 random label draws (1 percent labeled) §5.2 fig. 3. This is not part of the table above.
• No standard deviations or confidence intervals are reported for the table.

Paper vs code

No official code.

Searched: the paper and the arXiv metadata contain no code link or project page. GitHub repository search (five queries: "max-margin graph cuts", the title words with "harmonic", "kveton max-margin", and "max-margin graph cut" within org IntelLabs): no results. No discrepancies were checked.

Pitfalls

• Hard vs soft labels. The bound is proved for the soft-label relaxation eq. 16 with c_l = 1 and c_l > c_u, but all experiments use the hard-constrained solution eq. 5 eq. 6. The authors list whether the theory's setting helps as an open question §7. Implement the hard version to reproduce the tables.
• γ_g and ε are redundant. The authors say many (γ_g, ε) pairs give the same result. For UCI they fix ε = 1e-6 and tune only through γ and γ_u §5.2 §6.2.
• Edge cases of the threshold. |ℓ_i| ≥ ε with ε = 0 keeps points whose score is exactly 0, which has no inferred sign. Fig. 3 uses ε = 0, and the paper does not say how the sign of a zero score is taken.
• Scaling of the objective. Eq. 7 sums the hinge losses (no 1/n factor) and adds γ‖f‖². The paper does not say how this maps to LIBSVM's cost parameter C, so γ cannot be copied into another SVM solver directly. Check the scale by reproducing one row of the table.
• Bias term. The linear analysis uses f(x) = α₁x₁ + α₂x₂ with no intercept §4.3 eq. 11. Whether the experimental SVMs include a bias is not stated.
• Edge weight scale. σ is "the mean of their standard deviations", and whether this is over labeled or all points is not stated. The graph also depends on K and σ, so a different σ changes which points are confident.
• k-NN symmetry. The graph is 5-NN, but symmetrization and tie handling are not stated. The Laplacian and the harmonic system assume a symmetric W §2.
• Multi-class. Digit has 45 one-vs-one problems (all class pairs); letter has 25 consecutive-letter pairs; image segmentation has 15 problems. The paper does not state the number of classes, so the image-segmentation count cannot be checked from the text. How binary outputs are combined into a multi-class prediction is not stated; errors are averaged over binary problems §6.2.
• Kernel definitions. The "cubic" kernel's form (for example, offset and scaling) is not given. Only the RBF width is specified §6.2.
• Stability bound scaling. The bound is O(n_l^{-1/2}) only when β = O(1/n_l), which the authors state needs γ_g = Ω(n_l^{3/2}) §5.1. The bound contains λ_M(L), the largest eigenvalue of the Laplacian, and the paper does not bound it in terms of n. The authors also say the bound is not used to set γ_g.
• Risk and VC dimension. Lemma 1 needs the VC dimension h of the function class §5, Lemma 1, which the paper does not compute for the kernel classes used in experiments.
• Figure vs table. The results table is typeset inside a figure environment (Figure 4) fig. 4. Cite it as a figure.
• Averaging and variance. The UCI table reports averages over binary problems and folds, with no spread. The 50-draw averaging is used only for fig. 3 fig. 3.
• MR baseline details. MR is taken from "the implementation of Belkin et al." §6.1. The paper does not restate MR's kernel, solver or hyperparameters, so a faithful reproduction needs that implementation.
• Lower-bound step. In Lemma 2's proof, the inequality (λ_m(L) + γ_g + 1)² ≥ γ_g² + 1 is used to replace the denominator. This is valid, but it makes β's bound looser than the proof's exact expression [§5, Lemma 2].

Lineage

• Builds on: harmonic function solution on graphs, Zhu, Ghahramani and Lafferty (2003) §2; its eigenvalue view of the regularized version, Smola and Kondor (2003) §2; stability of transductive algorithms, Cortes et al. (2008) §5.
• Compared against: manifold regularization of SVMs, Belkin, Niyogi and Sindhwani (2006) §4.2 §6.1; semi-supervised SVMs with hat loss, Bennett and Demiriz (1999) §4.1; supervised SVM §6.2.
• Superseded by: none known from content in this wiki.
• The paper cites no arXiv identifiers for these works and none is linked here.