Multi-separator polyhedral consistency loss
Implementation & benchmark of arXiv:2608.16861 — The canonical facets of multi-separator polytopes
Source paper: The canonical facets of multi-separator polytopes arXiv:2608.16861 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Add valid-inequality penalties to a segmentation model that predicts both node cut probabilities and pairwise separation probabilities. The penalties enforce that a predicted pair cannot be separated without an appropriate vertex separator, and that local path and intersection relations among pair predictions remain feasible. This supplies structural supervision even when only sparse or noisy pair labels are available.
Formulas
Mathematical statement
For a graph G=(V,E), x_v in [0,1] denotes the predicted indicator that vertex v is separated, and x_f in [0,1] denotes the predicted indicator that interaction f={p,q} is separated. If C is an f-connector, meaning every p-q path intersects C, the connector inequality is x_f <= sum_{v in C} x_v. If S is an f-separator, meaning deleting S disconnects p and q, the separator inequality is 1-x_f <= sum_{s in S}(1-x_s). For an f-path P=(V_P,E_P) in the interaction graph, the paper proves x_f <= sum_{e in E_P} x_e - sum_{v in V_P\setminus f} x_v; x_e is the pair variable associated with edge e and the subtraction accounts for overlaps at internal vertices. For four distinct vertices v_1,v_2,w_1,w_2 with graph edges {v_1,v_2},{w_1,w_2} and all four interaction variables present, the intersection inequality is x_{v_1w_2}+x_{v_2w_1} <= x_{v_1w_1}+x_{v_2w_2}. For a valid inequality a(x)<=b, use the differentiable violation [a(x)-b]_+^2. The paper proves validity for every exact binary feasible assignment; the neural adaptation applies the same inequalities to soft probabilities as a regularizer.
Implementation notes
Integrate the loss after the network prediction heads. Use a CNN or graph neural network producing node logits a_v and pair logits b_f; convert them to probabilities x_v=sigmoid(a_v) and x_f=sigmoid(b_f). Build a sparse image graph with 4- or 8-neighbor edges and let F contain graph edges plus sampled long-range pairs. For every minibatch, generate constraints as follows. First, sample short simple graph paths P between endpoints of selected interactions and add relu(x_f - sum_e x_e + sum_v_internal x_v)^2. Second, compute approximate minimal vertex cuts using breadth-first search or a small node-capacitated max-flow routine and add relu(1-x_f-sum_s(1-x_s))^2. Third, enumerate local endpoint rectangles and add relu(x_v1w2+x_v2w1-x_v1w1-x_v2w2)^2. Average the penalties and multiply by lambda_poly, ramping lambda_poly from zero during the first 5-10 epochs. Pseudocode: xv=sigmoid(node_logits); xf=sigmoid(pair_logits); L=L_supervised; for f,P in paths: L+=lam*relu(xf[f]-sum(xf[e] for e in P.edges)+sum(xv[v] for v in P.internal))**2; for f,S in cuts: L+=lam*relu(1-xf[f]-sum(1-xv[s] for s in S))**2; for I in rectangles: L+=lam*relu(xf[I.parallel1]+xf[I.parallel2]-xf[I.cross1]-xf[I.cross2])**2; backprop(L). Graph search estimates candidate constraints; the inequality coefficients are fixed by the paper. First test on BSDS500 or a synthetic 64x64 grid with touching objects, using a U-Net with node and pair heads, against cross-entropy plus ordinary pairwise smoothness. Measure boundary F1, Rand error, pair calibration, and the fraction of held-out inequalities violated. Success means better instance separation and lower violation rate at equal parameter count and training FLOPs.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.