acceptodds
Under review as a conference paper at ICLR 2027

Certifying Pairwise Readouts under Rank-Two Representation Uncertainty

Abstract

In graph-based decision systems, some node representations may be missing when a score must be compared with a threshold. Certifying the decision then requires a bound over all admissible completions. We study this problem for nonnegative weighted sums of pairwise inner products. Unknown vectors vary independently in the unit cube, with coordinatewise-bounded orthogonal residuals from a supplied rational rank-two subspace; observed vectors lie in that subspace. In a computable small-radius regime, we construct the exact projected domain and ordered sets of projected candidates, reducing their coupled optimization to a polynomial-size minimum-cut problem. Feasible lifting provides a witness and a quadratic-width interval for the original maximum, whose first-order perturbation coefficient is exactly recoverable. Thresholding the second-order coefficient is strongly NP-complete in a fixed sixteen-dimensional geometry, even with a unique zero-radius optimizer. At every fixed sufficiently small positive rational radius in that geometry, maximum-value thresholding remains strongly NP-complete and maximization admits no fully polynomial-time approximation scheme unless . Exact comparisons on constructed instances quantify certificate quality, while coupled multi-label examples demonstrate the role of joint optimization. As an application, a monotone deviation certificate supports selecting vectors to fix at reference values. Together, these results separate efficient certification from exact residual optimization in the rank-two uncertainty model.

Primary area:
learning theory
Keywords:
representation uncertainty, threshold certification, partial identification, pairwise readout, computational complexity, perturbation analysis, minimum cut, low-rank structure

Reviews

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

This paper studies the maximization of nonnegative weighted sums of pairwise inner products, where unknown vectors lie close to a common rank-two subspace. In particular, the objective is max⁡b1,…,bg(∑i<jwij⟨bi,bj⟩+∑i⟨hi,bi⟩)\max_{b_1,\ldots,b_g} \left(\sum_{i<j} w_{ij}\langle b_i,b_j\rangle + \sum_i \langle h_i,b_i\rangle\right), where wij≥0w_{ij}\geq 0 and hi∈S∩R≥0nh_i\in S\cap\mathbb R_{\geq 0}^n. Each vector satisfies bi∈[0,1]nb_i\in[0,1]^n and ∥(I−P)bi∥∞≤ε\|(I-P)b_i\|_\infty\leq\varepsilon, where PP projects onto the rank-two subspace SS. The paper shows that this problem can be solved in polynomial time with O(ε2)O(\varepsilon^2) additive approximation using minimum cut. The paper also shows that the first-order change in the optimal value can be computed efficiently, while computing the second-order term is NP-hard. Moreover, exact optimization remains NP-hard even for a fixed positive ε\varepsilon. Finally, the paper extends the algorithm to a certified disclosure problem.

Critical strengths
  • For the optimization problem considered in this paper, the authors provide a comprehensive theoretical analysis. They give a polynomial-time algorithm with an additive O(ε2)O(\varepsilon^2) approximation guarantee and also prove NP-hardness results for exact optimization. These results provide a clear understanding of the computational tractability and hardness of the problem.
Critical weaknesses
  • The paper does not provide a detailed motivation for the problem it studies. In particular, the proposed model seems rather restrictive, as it assumes that all unknown vectors lie close to a common rank-two subspace. It would be helpful if the authors could provide concrete examples and discuss when such assumptions are reasonable.
  • The presentation of this paper is difficult to follow and can be improved significantly, especially in the abstract and introduction. Many technical concepts are introduced without sufficient intuition, making it difficult to understand the model considered in this paper, the main ideas, and the contributions. I suggest the authors improve the presentation by explaining the problem setting and the main results more clearly.
Questions for authors

See the above question

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

The paper studies the problem of certifying decision made from a graph-based system, specifically decisions arising from node representations, in the presence of some missing node representations. It assumes that missing node representation vectors are sufficiently close the a two-dimensional subspace and that the observed node representations live in that two-dimensional space, presumably to make the analysis and computation feasible. They consider certificates of the decision threshold by optimization over the missing node representations through checking if any alternatives to the missing data could make a similarity-based graph score (inner products of node representations) exceed a given fixed threshold. By projecting the missing node representation optimization problem to the two-dimensional subspace, the authors can provide bounds on the graph score, computable in polynomial time. The paper also contain results on the computational aspects within the problem setting, such as the NP-hardness of computing a second order correction term in the distance from the two-dimensional subspace of the unknown node representations.

Critical strengths

The main strength is the contribution in terms of theoretical results regarding the certification of similarity-based graph scores of graph-based systems in the presence of missing node representations. It could plausibly be applied to graph learning systems where missing data results in some unknown node representations, which is a problem of relevance. The analysis of computational hardness of the projected optimization problem gives insights into the difficulty of the general problem.

Critical weaknesses

A highly critical weakness of the paper is regarding its presentation and writing. I found the paper very hard to comprehend with poorly or unexplained terminology and no real discussion around the meaning, intuition or implication of the various theorems and propositions. For instance, both the abstract and introduction are written in a way that might be comprehensible when one already understands what the paper is about, but for a first time reader it is not understandable at all. As an example, the authors write in introduction:

"Observed vectors lie in that subspace and induce nonnegative linear terms. The subspace and radius specify the admissible completions. At zero radius, nominal optimization maximizes the score over all exact-subspace completions; positive radius introduces additional residual directions."

Before studying and understanding the math in later sections, it is not clear what is meant by the induced linear terms or what this radius is referring to.

The paper is in most part formal mathematics without much discussion around it, making it hard for the reader to assess its applicability and relevance.

A second second critical weakness about the applicability of the contributions of the paper. Assumptions are stated but not properly motivated or discussed, making it harder to judge the broadness and relevance of the results. It could be a valuable result to show that the problem remains NP hard even under unreasonable simplifying assumptions, but to provide theoretical guarantees in terms of bounds under too many limiting assumptions are of less interest, in my opinion. There is little experimental evidence and it is not clear if the artificial setting considered generally reflect what we would expect to observe in real graph systems. A weakness of the approach compared to, e.g., the McCormick baseline could be applicability beyond the restrictive assumptions made in the paper.

Questions for authors

Given the lack of discussion around the assumptions made and the meaning of the theoretical results, my main questions are the following:

  1. How is the assumption of considering node representations in a two-dimensional (or close to) justified? Do the assumptions hold for many or some real-world graphs?
  2. Where are the proofs for the theorems? This is not clearly stated and not even clear from browsing through the appendix.
  3. The experiments are done on a synthetically created graphs. Is it specifically created such that node representations lie close to a two-dimensional subspace? Is McCormick's approach more generally applicable when this does not hold?

A question that does not affect my rating of the paper:

Given the difficulty of solving the optimization problem exactly, or even providing bounds, would a more probabilistic approach be of interest? This might produce a certificate that is valid with high probability.

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

Summary of the model and the formulation

The paper studies the quadratic optimization problem J(b1,⋯ ,bg)=∑1≤i<j≤gwij⟨bi,bj⟩+∑i=1g⟨hi,bi⟩J(b_1, \cdots, b_g)=\sum_{1\leq i<j \leq g}w_{ij}\langle b_i,b_j\rangle+\sum_{i=1}^g\langle h_i,b_i\rangle with given wij≥0w_{ij}\ge0 and hi∈[0,∞)nh_i \in [0,\infty)^n. It arises in studying graph based decision systems G=([ℓ],E)G=([\ell], E) with some node representations b1,⋯ ,bg∈Rnb_1, \cdots, b_g \in \mathbb{R}^n missing. So, a natural way to identify the missing feature vectors b1,⋯ ,bg∈Rnb_1, \cdots, b_g \in \mathbb{R}^n (or be able to determine whether any admissible completion could exceed a threshold) is to consider maximizers of a suitably chosen score function arg⁡max⁡b1,⋯ ,bg∈XJ(b1,⋯ ,bg)\arg \max_{b_1, \cdots, b_g \in \mathcal{X}} J(b_1, \cdots, b_g), where the optimizing set X\mathcal{X} is constructed based on the observed node representations bg+1,⋯ ,bℓb_{g+1}, \cdots, b_{\ell}. The authors assume that bg+1,⋯ ,bℓ∈[0,∞)nb_{g+1}, \cdots, b_{\ell} \in [0,\infty)^n, and define S=S= span (bg+1,⋯ ,bℓb_{g+1}, \cdots, b_{\ell}). They also assume that SS has dimension 22 with hi=∑j=g+1ℓwijbj∈S∩[0,∞)nh_i =\sum_{j=g+1}^{\ell} w_{ij}b_j\in S \cap [0,\infty)^n. Finally, the paper makes a choice of X\mathcal{X} as the ε\varepsilon fattening of SS in a certain ℓ∞\ell_{\infty} norm (for algorithmic reasons) restricted to the unit cube, Kε=b∈[0,∞)n:∣(I−P)b∣∞≤εK_{\varepsilon}=\\{b\in [0,\infty)^n:\\|(I-P)b\\|_\infty\le\varepsilon\\} ∩[0,1]n\cap [0,1]^n, where PP the orthogonal projector onto SS.

Summary of the results and contributions

Writing Uε=max⁡b1,⋯ ,bg∈KεJ(b1,⋯ ,bg)U_{\varepsilon} = \max_{b_1, \cdots, b_g \in K_{\varepsilon}} J(b_1, \cdots, b_g) for the original optimization and Vε=max⁡b1,⋯ ,bg∈PKεJ(b1,⋯ ,bg)V_\varepsilon= \max_{b_1, \cdots, b_g \in PK_{\varepsilon}} J(b_1, \cdots, b_g) for optimization over the projection PKεPK_\varepsilon of KεK_{\varepsilon} onto SS, the authors establish in Theorem 1 an exact polynomial-time algorithm for computing VεV_\varepsilon within a computable geometric radius ε∈(0,εB(S)]\varepsilon \in (0, \varepsilon_B(S)]. Starting from a suitable (projected) solution b1,⋯ ,bg∈PKεb_1, \cdots, b_{g} \in PK_{\varepsilon}, they also provide a (lifted) solution b1lift,⋯ ,bglift∈Kεb_1^{\text{lift}}, \cdots, b_{g}^{\text{lift}} \in K_{\varepsilon} satisfying the bounds Vε−nWε2≤J(b1lift,⋯ ,bglift)≤Uε≤Vε+nWε2V_{\varepsilon}- nW\varepsilon^2 \leq J(b_1^{\text{lift}}, \cdots, b_{g}^{\text{lift}}) \leq U_{\varepsilon} \leq V_{\varepsilon} + nW\varepsilon^2, with W=∑i<jwijW=\sum_{i<j}w_{ij}.

The paper further proves in Theorem 2 the exact quadratic formula Uε=U0+Λε+Γε2U_\varepsilon=U_0+\Lambda\varepsilon+\Gamma\varepsilon^2 for ε∈[0,ε0]\varepsilon \in [0, \varepsilon_0] for some polynomially computable ε0\varepsilon_0. The first-order coefficient Λ\Lambda is polynomial-time computable, whereas thresholding Γ\Gamma is strongly NP-complete, even for fixed rational subspace SS in R16\mathbb R^{16} and a unique nominal optimizer. Finally it shows in Theorem 3 that thresholding UεU_\varepsilon at every fixed sufficiently small positive rational radius is also strongly NP-complete, and the corresponding maximization problem admits no FPTAS unless P = NP. Thus the central contribution is a separation between tractable projected certification and first-order sensitivity, and intractable residual optimization at second order.

Critical strengths
  1. Constructive certification with an explicit error bound. Under the stated model assumptions and within a computable small-radius regime, Theorem 1 gives a polynomial-time algorithm for the projected maximum (Vε)(V_{\varepsilon}), together with a feasible lift and an interval containing the original maximum (Uε)(U_\varepsilon) of width at most (2nWε2)(2nW\varepsilon^2). The construction combines an explicit description of the projected domain, an optimum-preserving geometric restriction, and a minimum-cut reduction, while allowing an unrestricted number of unknown vectors. In my opinion, the contribution is algorithmic since it provides both attainable witnesses and quantitative guarantees for threshold decisions.

  2. A precise distinction between first-order sensitivity and second-order computational difficulty. Theorem 2 establishes the exact local identity (Uε=U0+Λε+Γε2)(U_\varepsilon=U_0+\Lambda\varepsilon+\Gamma\varepsilon^2), with (Λ)(\Lambda) exactly computable in polynomial time, whereas thresholding (Γ)(\Gamma) is strongly NP-complete in a constructed fixed sixteen-dimensional geometry, even with a unique nominal optimizer. Theorem 3 further establishes hardness at every sufficiently small fixed positive rational radius in that geometry. These results provide a meaningful theoretical explanation of how efficient recovery of the first-order response can coexist with computationally difficult residual optimization.

Critical weaknesses

Insufficiently established significance of the formulation

The main results rely on a particular combination of assumptions: a supplied two-dimensional subspace, nonnegative interaction weights and native fields, cube constraints, and a coordinate-dependent residual tube. In my opinion, the paper does not sufficiently motivate why these assumptions should hold together in an important machine learning problem, or explain how the subspace, coordinates, and uncertainty radius would be justified when representations are genuinely missing.

The graph-score example and disclosure formulation make the framework concrete, but I found the connection to established applications insufficiently developed. Alternatively, a stronger explanation of the theoretical significance of this structural regime, and of which assumptions are essential to the tractability–hardness distinction, would help establish the broader contribution.

This concern is central to my recommendation. Although the paper establishes precise mathematical results, I remain unconvinced that the importance of the problem setting and the broader insight provided by these results are sufficiently established for acceptance.

Questions for authors
  1. Why do you consider the supplied subspace SS to be two-dimensional, since my understanding is that you begin with a graph G=([ℓ],E)G= ([\ell],E) on ℓ\ell vertices and every vertex has an associated feature vector bi∈Rnb_i\in \mathbb{R}^n for all i∈[ℓ]i\in [\ell]. Now, a subset of the feature vectors b1,⋯ ,bgb_1, \cdots, b_g are unknown, and rest of the known feature vectors bg+1,⋯ ,bℓb_{g+1}, \cdots, b_{\ell} generate SS defined as S=S= span(bg+1,⋯ ,bℓb_{g+1}, \cdots, b_{\ell})? This means apriori, we should keep the dimension of SS (in fact SS itself) as a free parameter in the formulation of the theory and not a fixed number 2, because for a given graph we have to compute it by looking at span(bg+1,⋯ ,bℓ)b_{g+1}, \cdots, b_{\ell}), or unless the authors could show that there are natural classes of actual problems of interest where S has dimension 22.

  2. Why do you require the feature vectors b1,⋯ ,bℓb_1, \cdots, b_{\ell} to be non-negative componentwise and bounded above by 1, since my understanding is that for a given graph G=([ℓ],E)G= ([\ell],E), feature vectors b1,⋯ ,bℓb_1, \cdots, b_{\ell} can have in general arbitrary structure and unbounded norm. More precisely, just restricting to the known feature vectors bg+1,⋯ ,bℓb_{g+1}, \cdots, b_{\ell}, The quantity M=max⁡g+1≤i≤ℓ∣bi∣∞M = \max_{g+1 \le i \le \ell} \\|b_i\\|_{\infty} depends on the problem, and it is not clear a priori whether dividing b1,…,bgb_1, \ldots, b_g by MM resolves this issue?

  3. Why do you focus on KεK_{\varepsilon} or equivalently ℓ∞\ell_{\infty} perturbations of SS, since the problem formulation does not need that, as my understanding is that overall it becomes very difficult for me as a reviewer to move forward in the presentation of the paper, where the authors make abrupt assumptions without providing any justification while formulating the problem, and as is clear to me, the formulation does not require any of these restrictions?

  4. Why do you consider the specific quadratic function J(B)J(B) and require wij≥0w_{ij} \geq 0, since my understanding is that no specific class of problems of actual interest has been provided in the paper while motivating that J(B)J(B) appears naturally in many cases?

  5. It is worth emphasizing more prominently than in lines 101-104 that the linear term ∑i=1g⟨hi,bi⟩\sum_{i=1}^g \langle h_i, b_i \rangle with known hih_i for i∈[g]i\in [g], is of the form hi=∑j=g+1ℓwijbjh_i= \sum_{j =g+1}^{\ell} w_{ij}b_j, since my understanding is that the original score function J(B,Bc)=∑1≤i<j≤ℓwij⟨bi,bj⟩J(B,B^c)= \sum_{1\leq i <j \leq \ell} w_{ij} \langle b_i, b_j \rangle is more intutitive and reduces to J(B)J(B) where we drop the terms that does not involve b1,⋯ ,bgb_1, \cdots, b_g, as the rest of the variables bg+1,⋯ ,bℓb_{g+1}, \cdots, b_{\ell} are already known.

  6. What exactly is the degree of the polynomial, when the notion of polynomial time is mentioned in Theorem 1 for computing εB(S)\varepsilon_B(S), since my understanding is that in practice, on needs to be able to choose a smaller ε\varepsilon? Make sure to mention the order of the degree of the polynomial whenever you discuss polynomial time computability of a quantity (such as VεV_{\varepsilon}), and alongside elaborate it in what sense it polynomial time, what the inputs are while computing the order of the polynomial.

  7. Is BliftB^{\text{lift}} polynomial time computable, and what is the order of the polynomial? Please also elaborate the meaning of the term polynomial encoding length in Theorem 1 as its not immediate what it means to me, and I believe to many who are not familiar with the notations and languages used within the field of computational complexity theory. Make sure to elaborate the meaning of a similar language or a term used in the paper to make it self contained.

  8. Could the authors make detailed remarks on how the results including Theorems 1, 2, 3 would quantitatively change as one changes the assumptions of the model. For example, make sure to discuss the consequences to Theorems 1, 2, 3 once you violate one of the following wij≥0w_{ij}\geq 0 or b1,⋯ ,bg∈[0,1]nb_1, \cdots, b_g \in [0,1]^n or KεK_{\varepsilon} or ℓ∞\ell_{\infty} geometry or dim (SS) =2=2. Make sure to do it quantitatively, that how the results would change as a function of dim (SS), or as a function MM if b1,⋯ ,bg∈[−M,M]nb_1, \cdots, b_g \in [-M,M]^n, or when one uses a geometry different from ℓ∞\ell_{\infty} or allows negative weights wijw_{ij}.

  9. Why is the dependence on ε\varepsilon abrupt in Theorem 1, equivalently what happens when ε≥εB(S)\varepsilon \geq \varepsilon_B(S) and why so? Also in my opinion, rewrite Equations 4 and 5 together as Vε−nWε2≤J(Blift)≤Uε≤Vε+nWε2V_{\varepsilon} - nW\varepsilon^2 \leq J(B^{\text{lift}}) \leq U_{\varepsilon} \leq V_{\varepsilon} + nW\varepsilon^2.

  10. Make sure to provide intuition on why VεV_{\varepsilon} is polynomial time computable whereas UεU_{\varepsilon} is not? Similarly, how should one think of constructing BliftB^{\text{lift}} starting with VεV_{\varepsilon} or more precisely the optimizers of VεV_{\varepsilon}?

  11. Could the authors provide complete Lean proofs of the all results claimed in the paper, and comment on how much effort was put into making this paper human readable?

  12. Could the authors provide conceptual explanation of the Theorems and about proof organization. I found the central arguments difficult to reconstruct from the main text. Could the authors provide a clearer roadmap explaining why the projected problem admits a minimum-cut reduction, how a projected optimizer is lifted, and how the residual choices generate second-order hardness despite a unique nominal optimizer? More explicit statements of the key geometric insights, followed by the technical verification, would make the contribution substantially easier to assess.

  13. Could the authors comment on how much effort was put into making this paper human readable, in terms of motivating the problem, explaining the intuition behind the assumptions and each of the theorems presented in the paper?

  14. Could the authors explain what was the core research idea that motivated them to write the paper (lines 496-497)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.