acceptodds
Withdrawn from ICLR 2027

A Complete Complexity Dichotomy for Deciding Cluster In-Betweenness

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Unsupervised learning reads every object through a binary lens: inlier or outlier. Recent work adds a third primitive, the *in-between instance* (IBI): an object atypical for every cluster yet simultaneously compatible with several of them, and whose interest lies in *which* traits it inherits from *which* neighbouring group. Existing formulations answer this with a proximity predicate and a scalar score. We instead pose in-betweenness as an exact reconstruction question: can a bounded number of *actual* cluster members be selected so that, coordinate by coordinate, they reproduce a target? The selection is then itself the attribution. We formalize this as , a group-budgeted covering problem over symbolic data, and settle its complexity along five structural parameters: alphabet size , dimensionality , number of clusters , cluster size , target size . We obtain a complete dichotomy over all bounding regimes: solvable in polynomial time exactly when , or is bounded, each witnessed by a fixed-parameter algorithm and -complete otherwise. In-between detection is thus feasible precisely when one of three structural budgets is paid.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Computational Complexity, Parameterized Complexity, Clustering, In-Betweenness, Complexity Dichotomy

Reviews

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

The paper introduces Inbetween-Decision, a decision problem motivated by in-between instances (IBIs): objects that exhibit characteristics of multiple clusters. The main result classifies the problem under all 25=322^5=32 choices of which of five parameters are bounded: alphabet size σ\sigma, dimensionality δ\delta, number of clusters ν\nu, maximum cluster size ξ\xi, and target-set size τ\tau. The problem is polynomial-time solvable when the bounded parameters include one of σ,δ{\sigma,\delta}, ν,ξ{\nu,\xi}, or δ,τ{\delta,\tau}, and is NP-complete in the remaining regimes. The tractable cases admit fixed-parameter algorithms.

Overall, the paper is difficult to understand and I am unconvinced that the formulation captures the notion of in-betweenness used to motivate the work, or that its significance for machine learning has been adequately established. The broad claims about a third machine learning primitive make this gap more pronounced.

Critical strengths

The paper contains a coherent complexity classification for a symbolic covering problem.

Critical weaknesses
  1. The paper is difficult to read, particularly the abstract and introduction. Although the introduction mentions aligned symbolic feature vectors, the relationship between this setting and the clustering terminology is not sufficiently clear. The authors should clarify early on how clusters are represented, whether they are given as input, and what structural assumptions, if any, they satisfy. In particular, the question of selecting a bounded number of representatives to “exactly reconstruct a target object” coordinate by coordinate is difficult to interpret without a concrete explanation of the data model and reconstruction rule. Explaining these details upfront, and distinguishing this formulation from Euclidean or graph-based clustering, would substantially improve readability.

  2. I am not convinced by the opening claim that unsupervised learning views every object through a binary inlier/outlier distinction, or by the resulting presentation of IBI as a third machine learning primitive. These are much broader claims than the paper’s formal results support. The contribution is a complexity classification for a specific symbolic covering problem, not a demonstration that machine learning requires a new foundational primitive.

  3. I found the connection between the introductory motivation and the mathematical formulation difficult to follow. The paper mentions topic-bridging publications and some areas, while acknowledging that these motivating instances are continuous. It then moves to exact reconstruction over aligned symbolic coordinates without sufficiently explaining why this is the appropriate discrete counterpart for those applications.

Questions for authors

See weaknesses.

1 comment

With the help of the reviews we came to the conclusion that it is best to withdraw this submission, having the chance to substantially improve this work and resubmit it in future. At that point we'd like to thank the reviewer for the feedback. The connection between the motivation and the mathematical formulation is among the core points of improvement. Thank you for pointing that out.

Reviewer_efNxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies Inbetween-Decision, which asks whether a target set can be reconstructed coordinate-wise using budgeted selections of representatives from given clusters.

Critical strengths
  • The paper formalizes coordinate-wise reconstruction through VE-covering and budgeted representative selection. Using actual cluster members provides explicit witnesses showing which representatives supply the required symbols, supporting feature-level attribution.

  • The authors classify all 32 bounded-parameter regimes across alphabet size, dimensionality, number of clusters, maximum cluster size, and target size. Identifying three minimal tractable regimes and four maximal NP-complete regimes provides a systematic characterization of the proposed problem.

  • All three tractable regimes admit fixed-parameter algorithms, including fixed-parameter linear-time algorithms for {σ,δ}\{\sigma,\delta\} and {δ,τ}\{\delta,\tau\}. The complementary hardness reductions explain how difficulty persists under restricted parameters, particularly when dimensionality is fixed to three.

Critical weaknesses
  • The formal problem permits reconstruction from a single cluster, whereas Remark 17 distinguishes genuine in-betweenness by requiring that no single cluster can reconstruct the object on its own. Please qualify the corresponding claims in Table 1.

  • The technical novelty relative to related covering problems needs clearer discussion. The tractable cases use dynamic programming, type compression, and enumeration. Please explain which structural insights or hardness boundaries are specific to this formulation and identify the main technical challenges in establishing the complete classification.

  • The DNA-style examples illustrate the covering condition, but its application-level interpretation remains unclear.

  • In Appendix, the reverse direction of Proposition 6 should recover each variable's assignment from its local selection Ai′A_i', rather than membership in the global union A′A'. Identical vectors may occur across clusters, so local budgets do not imply the stated global membership restriction.

Questions for authors

see weaknesses.

  • Please clarify the main technical challenges in establishing the complete complexity classification and explain which parts require new ideas beyond standard dynamic programming and enumeration.
1 comment

With the help of the reviews we came to the conclusion that it is best to withdraw this submission, having the chance to substantially improve this work and resubmit it in future. At that point we'd like to thank the reviewer for the feedback. Here we take the motivation and highlighting and clarifying of the main technical challenges as points to improve.

Reviewer_4yQPOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces the Inbetween-Decision problem, which asks whether a budgeted selection of samples from given clusters can collectively cover every coordinate value required by a target set. This work analyze the problem using five parameters: alphabet size, vector dimension, number of clusters, maximum cluster size, and target set size. They classify all 32 combinations of parameter restrictions, providing FPT algorithms for three tractable parameter pairs and proving NP-completeness in all remaining cases via reductions from 3-CNF-SAT.

Critical strengths
  1. The paper provides a complete complexity classification across all 32 combinations of restrictions on five structural parameters. Rather than only proving that the general problem is NP-complete, it identifies which combinations of bounded parameters are sufficient for polynomial-time solvability.

  2. The paper is clearly presented, with both hardness proofs and explicit algorithms for the tractable cases. The examples help explain the main constructions.

Critical weaknesses

My expertise in this area is limited, so I raise one question based on my understanding. Section 3 (lines 181–190) formally defines Inbetween-Decision. As I understand it, this definition allows a single cluster to cover the target independently. Remark 17 explains that the problem captures the reconstruction aspect of in-betweenness, while a true in-between object additionally requires that no single cluster can reconstruct it alone. However, Remark 4 refers to the construction obtained by adding irrelevant clusters as a “true IBI setting.” This appears to ensure only that the input contains multiple clusters, not that contributions from multiple clusters are necessary. It is therefore unclear to me whether the use of “true IBI setting” in Remark 4 is consistent with the explanation in Remark 17. Could the authors clarify this distinction?

Questions for authors

Please see the Weaknesses.

1 comment

With the help of the reviews we came to the conclusion that it is best to withdraw this submission, having the chance to substantially improve this work and resubmit it in future. At that point we'd like to thank the reviewer for the feedback.

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

Related papers

Discussion (0)

Sign in to comment.