acceptodds
Under review as a conference paper at ICLR 2027

Graph-based Semi-Supervised Learning in the Extreme Low-Label Regime

Abstract

Graph-based semi-supervised learning spreads a small set of labels across a graph whose edges encode similarity between data points, and it is the natural tool wherever annotation is costly but relations between samples are known. The underlying task is combinatorial, since each vertex must receive exactly one label and each class must retain its share of the vertices. Established methods relax those requirements, in the sense of losing tightness, solving a continuous surrogate and reading a labeling off it afterwards; we keep the problem discrete throughout. An auxiliary variable linearizes the quadratic objective, so that every iteration becomes a transportation problem with a totally unimodular constraint matrix, whose solution is integral without any rounding and meets the prescribed class sizes exactly. We prove that the iteration ascends monotonically, that the objective sequence converges, and that its limit points are stationary. Because the problem is non-convex, the initialization also matters, and we therefore unroll the iteration into a network whose ingredients are learned and which keeps the prescribed class sizes exact at inference. Our study is directed at the extreme low-label regime, where only a few labels per class are observed and where graph-based methods are most needed. On citation benchmarks in that regime the proposed method outperforms the state of the art in accuracy and labels each graph in a fraction of a second.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
discrete optimization, extreme low-label regime, graph-based semi-supervised learning

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_6qU3OpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes DASH SSL for graph-based semi-supervised learning in the extreme low-label regime. It uses an auxiliary-variable reformulation and integral transportation updates to optimize discrete label assignments under exact class-size constraints, and further unrolls the iteration into DASH-Net with learned diffusion and scheduling.

Critical strengths
  • The discrete formulation preserves one-hot assignments and exact class sizes.
  • The theoretical analyses establish monotonic objective improvement, convergence of objective values, and stationarity of fixed points for DASH SSL.
  • The experiments show generally competitive accuracy and efficient inference in the extreme low-label regime.
Critical weaknesses
  • The motivation is insufficiently explained, especially the connection between low-label degeneracy, thresholding errors, and class imbalance.
  • The paper is difficult to follow. The combinatorial formulation, relaxation tightness, and auxiliary-variable construction need clearer explanations.
  • The tuning-free claim is insufficiently justified, particularly regarding the architecture and training choices of DASH-Net.
  • Although the appendices provide additional analyses, the results and limitations deserve deeper discussion, particularly the gap between DASH SSL and DASH-Net and the varying effect of the Poisson supervision term.
  • The layout of the different components in Figure 1 is not sufficiently coordinated.
Questions for authors
  • Can the authors better explain the motivation and the relationship between low-label degeneracy and class imbalance?
  • Can the authors clarify the combinatorial formulation and explain how the auxiliary variable and transportation updates preserve discrete assignments?
  • Can the authors justify the tuning-free claim and explain how the architecture and training configuration are selected?
  • Can the authors provide a deeper discussion of the performance gap between DASH SSL and DASH-Net and the effect of the Poisson supervision term?
Reviewer_BEnWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies graph-based semi-supervised learning under extreme label scarcity with exact class-size constraints. The authors propose DASH SSL, which reformulates a discrete graph-cut problem into an alternating optimization procedure with integral transportation-LP updates. The paper establishes monotonic ascent and convergence guarantees for the fixed algorithm. It further introduces Poisson-based supervision and DASH-Net, a learned unrolling architecture incorporating graph filters, Sinkhorn transport, and adaptive damping. Experiments are conducted on three citation networks and three image benchmarks.

Critical strengths
  1. Exact class-size assignment. The transportation-based formulation guarantees integral assignments satisfying the prescribed class sizes without heuristic rounding. This is a useful property for graph-based SSL when class proportions are known.
  2. Informative supervision ablations. Tables S3–S4 demonstrate that replacing one-hop supervision with a Poisson-based field substantially improves the fixed algorithm in several low-label settings. These results provide useful evidence that the choice of supervision term is important under extreme label scarcity.
Critical weaknesses

After eliminating the auxiliary variable Q, the DASH SSL update takes the same form as Equation (10) and Algorithm 1 of CombCut, making the novelty of the fixed optimization algorithm and its associated guarantees unclear. Although DASH-Net introduces learned components, the paper should better distinguish these contributions from the existing discrete optimization framework. Poisson MBO (Calder et al., 2020), which combines Poisson propagation with graph-cut refinement and can incorporate class-size information, also deserves more direct discussion and comparison. Theorem 6 applies to Algorithm 1 but is not established for DASH-Net, and the node-dependent gating in Section 4.2 does not generally preserve intermediate column marginals, although the final assignment enforces them. Additionally, the Kronecker-product expressions in Appendix B appear inconsistent with the stated column-wise vectorization convention, which seems to be a correctable notation issue rather than a problem with the TU result itself. 2. Experimental protocol and attribution of performance improvements. Appendix D states that DASH-Net is trained on each benchmark graph using cross-entropy targets from vertices whose labels are not revealed within each episode, but does not specify whether these targets are disjoint from the final evaluation vertices. If they overlap, the comparison under the claimed 1–5 labels per class setting would require reconsideration, making clarification of the training split and total supervision budget essential. The experiments also use true class priors to determine class sizes, without evaluating sensitivity to estimated or misspecified priors. Furthermore, the authors apply component-wise centering to their Poisson supervision while noting in Appendix F that the Poisson Learning baseline uses global centering, which may affect comparisons on disconnected graphs. Finally, Table S1 does not evaluate Algorithm 1 with the stronger training-free PPR and balanced-transport initialization described in Appendix D, making it difficult to isolate the benefit of learned unrolling.

Questions for authors
  1. What is the precise algorithmic difference between DASH SSL and CombCut, and could Poisson MBO be included in the comparison?
  2. Are the ground-truth labels used in DASH-Net's episodic training disjoint from the evaluation vertices, and what is the total supervision budget?
  3. Could the authors evaluate the training-free PPR-based initialization, assess sensitivity to misspecified class priors, and compare Poisson Learning using the same component-wise centering?
Reviewer_RQ4YOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates semi-supervised learning on graphs under conditions of extremely limited labels, subject to cardinality constraints. The task is formulated as a non-convex quadratic integer optimization problem. The authors propose the DASH-SSL framework, which linearizes the objective function through the introduction of auxiliary variables. In each iteration, the framework solves a transportation subproblem with the totally unimodular property to directly obtain integer one-hot labels, thereby avoiding the loss of tightness typically incurred by rounding after continuous relaxation. While the paper proves the monotonicity and convergence of the DASH-SSL iterative process, the algorithm is only guaranteed to reach a stationary point rather than a global optimum, and it remains sensitive to initialization. To mitigate this sensitivity, the authors unroll the iterative process into a learnable network, DASH-Net. Experiments on the Cora, CiteSeer, and PubMed datasets demonstrate that while the original DASH-SSL does not outperform the baselines, DASH-Net achieves superior results. However, DASH-Net does not inherit the theoretical guarantees of DASH-SSL, and the study lacks fine-grained ablation experiments for its individual components. Furthermore, I think this SSL method requires graph topology and node similarities to be provided a priori, which limits its applicability in many real-world scenarios. Additionally, there is a minor issue that the citation format in this paper does not follow the ICLR template.

Critical strengths
  1. By leveraging the theoretical properties of total unimodularity, the authors directly derive integer-labeled solutions, thereby avoiding the need for the continuous relaxation and subsequent rounding steps typical of traditional methods. This design ingeniously preserves the tightness of the original combinatorial optimization problem and constitutes the core theoretical contribution of this paper.
Critical weaknesses
  1. The method proposed in this paper relies on the assumption of homophily, where graph edges are implicitly assumed to represent similarities between nodes. The title fails to mention this premise, which is somewhat misleading.
  2. The theoretical guarantees are valid only for fixed-iteration DASH-SSL. They do not carry over to the learnable DASH-Net after unrolling.
Questions for authors
  1. This method is based on the homophilic graph assumption. Should there be a discussion or experiments concerning heterophilic graphs, in order to align with the broad framing suggested by the title?
  2. DASH-Net introduces trainable parameters, do the original theoretical properties of DASH-SSL still hold during the training phase of DASH-Net? Could the authors provide a theoretical analysis of DASH-Net?
  3. DASH-Net demonstrates a significant performance improvement over DASH-SSL. Is this gain solely due to mitigating sensitivity to initialization? Furthermore, does the solution produced by DASH-Net still fall within the feasible solution space of DASH-SSL? Could the authors conduct ablation studies to disentangle the individual contributions of the learned diffusion operator, Sinkhorn relaxation, learnable damping gating?
  4. The method relies on a pre-fixed edge similarity matrix and accurate class cardinalities. In real-world scenarios, such priors are often noisy or biased. Could the authors provide additional experiments or analysis to assess model performance when the edge similarity matrix is ​​imprecise, or when the cardinality constraints do not match the true class distribution?
Reviewer_pTsJOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

Authors formulate graph-based semi-supervised learning as a discrete assignment problem with class sizes fixed in advance. The authors propose an iterative optimization method for this problem with monontiv convergence in objective values. They also propose a modification of the algorithm that replaces the update with a trained neural network ("unrolling").

Critical strengths

Authors study an interesting problem.

Critical weaknesses
  • unclear how problem (4) is relevant for ML applications. this formulation rests on a given/known graph structure. How do you get this graph structure in practice? How robust is your mehtod to errors/noise in the graph structure?

  • the motivation/justification for the alternating opt. approach used by Alg.1 is unelar

  • it seems Alg. 1 uses a tuning paramter, the epsilon. this contradicts the promise of "tuning free"

  • the details of training/validation of unrolled Alg.1 is not very clear ? how much does the choice of training set influcence the resulting performance on different datasets?

  • unclear how the numerical experiments relate to the theoretical findings of the paper.

Questions for authors

if you use LLM for text generation, pls avoid jargon/metaphores like

  • "An auxiliary variable linearizes the quadratic objective,..." how can a variable linearize an objective function?
  • "..and we therefore unroll the iteration into a network whose ingredients are learned and..."
  • "..too few to memorize a graph of the sizes considered here.."
  • "Extreme low-label regime"
  • "..and the tractability it buys is paid for in exactly that loss".
  • "...is what buys the accuracy Table 1 reports.."

Comments on the paper

2 comments
Area_Chair_XYwVOpenReview ↗

Reminder to engage in the discussion with Authors

Dear Reviewers,

Thank you for your effort in reviewing this submission. The authors’ responses to your comments have been available since November 9. Please take the time to read them if you have not done so, and engage in the discussion. In particular, please indicate whether your main concerns have been adequately addressed and raise any remaining questions as soon as possible, so that the authors have an opportunity to reply before the rebuttal period ends on November 18.

Best regards

AC of Submission 9472

Dear Reviewers,

The rebuttal period ends in less than two days. If you have not already done so, I kindly ask you to acknowledge the authors’ responses, and indicate whether your main concerns have been adequately addressed or further clarification is needed.

Thank you.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.