betaFeedback

WorksComputer Science

Pattern-Based Matrix Analysis Under Permutations

Abstract

Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.

Introduction

A basic question in matrix analysis is what structure a matrix has. The standard answer is low-rank: the SVD gives the best rank-kk approximation and reveals latent linear factors. But many matrices are simple in another sense: after reordering rows and columns they show an interpretable geometric form, blocks, bands, chains or hierarchies. Seriation [4, 21], community detection [40, 30] and bandwidth minimization [16, 24] are usually studied separately yet share this intuition. Goldengorin and Krushinsky [ [27] make it precise: many combinatorial problems (LAP, TSP, linear ordering, matching, cut) reduce to finding a permutation that aligns a matrix with a geometric pattern, and fixing one permutation reduces the remaining search to a Linear Assignment Problem.

This paper turns that combinatorial idea into a matrix-analysis tool. A binary pattern mask MM specifies the target geometry; the pattern distance dM(A)d_M(A) is the off-pattern mass after the best row/column permutations. This viewpoint, which we call permutation-structural simplicity, complements low-rank approximation: a matrix may have clear geometric organization after reordering even when no low-rank model fits, and vice versa; the target geometry, the discrepancy measure and the search over permutations become independent ingredients of one formalism.

Contributions

  1. Pattern-based framework. We define the pattern distance dMd_M, the off-pattern Frobenius mass after optimal reordering, and use it to formalize permutation-structural simplicity.

40th Conference on Neural Information Processing Systems (NeurIPS 2026).

  1. Alternating LAP algorithm. An alternating procedure built on the auxiliary-matrix construction of Goldengorin and Krushinsky [ [27] performs exact one-sided updates of dMd_M in O(n3)O(n^3), applicable to any binary mask without changes to the solver.

  1. Pattern-plus-low-rank (PatLR) decomposition. A hybrid model combining permutation-structured fitting with a low-rank residual, with exact closed-form updates for both parts and a monotone alternating algorithm.

  1. Adaptive pattern selection. When the pattern is unknown, a simulated-annealing search jointly optimizes the pattern and the permutation against a density-normalized score.

  1. Experimental validation. On synthetic and real data the same algorithm recovers qualitatively different structures, scored by the metrics of latent ordering, consecutive ones and block recovery against the methods developed for them; on the attention heads of three transformers the same score gives labels with a shared depth profile.

Related Work

Structure after reordering. Several literatures study matrices that become simple once rows and columns are permuted, each around one geometry. Seriation seeks a Robinson order by spectral [[47, 4]] or convex [[21]] methods, with the consecutive-ones property [[9, 31]] and circular seriation [[46]] as its interval and cyclic forms. Community detection seeks block-diagonal structure, by modularity and spectral methods [[26, 57]] or under the stochastic block model, where belief propagation and its spectral linearizations are optimal near the detectability threshold [[30, 19, 34, 49]]. Bandwidth and profile reduction seek near-diagonal sparsity [[16, 25, 24]]; nestedness [[10]], bordered block-diagonal forms [[5]], chordal sparsity [[54]], core–periphery structure [[48]] and biclustering [[29]] are further such geometries (Table 2). Robust PCA separates a low-rank part from a sparse one [[11]] with no permutation; GoDec [[62]] alternates low-rank and sparse approximation, whereas PatLR restricts the support of the second component to a geometric mask under unknown permutations.

Pattern MMShapeClassical problemdMd_M in this paper
Order and locality
Diagonal†^\daggerδij\delta_{ij}Linear assignment (LAP)one LAP§§^{\S\S}
Banded (ww)†^\dagger∣i−j∣≤w\lvert i-j\rvert\le wSeriation, bandwidth min. [4, 16]NP-hard at w=1w=1, σ=π\sigma=\pi (App. § 10.5)
Anti-diagonal†^\daggeri+j=n+1i+j=n+1Reverse ordering (diagonal under column reversal)one LAP§§^{\S\S}
Cyclic band†^\daggermin⁡(∣i−j∣,n−∣i−j∣)≤w\min(\lvert i-j\rvert,n-\lvert i-j\rvert)\le wCircular seriation [46]–
Upper triangular†^\daggeri≤ji\le jLinear ordering / feedback arc set–^\P
2D grid stencil∥u−v∥1≤1\lVert u-v\rVert_1\le1 on a gridMesh / PDE orderings [24]–
Grouping and coupling
Block-diagonal (kk)†^\daggerkk diagonal blocksCommunity detection, SBM [30]NP-hard, Thm. 1
Block + band†^\daggerblocks ∪\cup bandModular networks with local structure–
Band-in-block†^\daggerblocks ∩\cap bandComposite target (§ 5.2)–
Bordered block-diagonalblocks + coupling borderDecomposition for parallel LA / LP [5]–
Core–peripheryJcc,Jcp,Jpc,0ppJ_{cc},J_{cp},J_{pc},0_{pp}Core–periphery structure [48]–
Block-triangularkk blocks, upper partDulmage–Mendelsohn decomposition [42]–††^{\dagger\dagger}
Hubs, nesting, intervals, localization
Arrowhead†^\daggerrow/col 0 + diagonalHub / sink structureO(n2)O(n^2) under σ=π\sigma=\pi (App. § 11.§ 3)
Ferrers (nested)†^\dagger1[j≤ri]1[j\le r_i], rr non-incr.Nestedness [10, 7]–♮^\natural
Interval envelope†^\dagger1[ℓi≤j≤ri]1[\ell_i\le j\le r_i]Consecutive ones, interval graphs [9, 37]–♮^\natural
Localized biclusterk×ℓk\times\ell rectangleSubmatrix localization, biclustering [29, 28]–
Hierarchy, branching, self-similarity, parity
Nested dissectionrecursive separatorsFill-reducing orderings [24]–
Clique treeoverlapping cliques on a treeChordal sparsity, GGMs [54]–
Kronecker supportK⊗qK^{\otimes q}Kronecker graphs [36]–
Checkerboard†^\daggeri+ji+j evenBalanced bisection (the 2-block mask under the even/odd relabeling)as 2 blocks‡^\ddagger
Local + stridedband ∪\cup periodic columnsSparse attention layouts [13]–

Table 2. Pattern dictionary: mask families, the structure they encode and the classical problem behind each (†\dagger: used in our experiments). The last column records only what this paper establishes about computing dMd_M (Theorem 1 and exact special cases); dashes: not analysed here.

A common optimization core. Goldengorin and Krushinsky [ [27] introduced patterns as a description of the input matrices of combinatorial optimization problems. For a fixed pattern the alignment is a Koopmans–Beckmann quadratic assignment problem [[33, 35, 12]], with two permutations a bilinear assignment problem [[15]], for which alternating LAP heuristics are studied by Sokol et al. [ [51]. Generic solvers are the FAQ heuristic [[55]] and Birkhoff-polytope relaxations [[21, 17, 38]]. In this paper the pattern is the interface between these literatures: the same solver serves every mask, and PatLR extends it with a low-rank residual.

Theory of Patterns

A pattern is a target structure (a band, block-diagonal, arrowhead, etc.), encoded by a binary mask M∈{0,1}n×nM \in\{0,1\}^{n \times n} marking the positions it allows; we use “pattern” for the structural hypothesis and “mask” for the matrix MM. A permutation π∈Sn\pi\in S_n maps an original index to its new position, (Pπ)ij=1{ι=π(j)}(P_\pi)_{ij}=1\{\iota=\pi(j)\}, so the (π,σ)(\pi,\sigma)-reordered matrix Aπ,σ:=PπAPσTA^{\pi,\sigma}:=P_\pi A P_\sigma^{\mathsf{T}} has entries Aijπ,σ=Aπ−1(i),σ−1(j)A^{\pi,\sigma}_{ij}=A_{\pi^{-1}(i),\sigma^{-1}(j)}; ΠM(X):=M⊙X\Pi_M(X):=M\odot X is the masking operator. For fixed row and column permutations the off-pattern mass is

dM(A;π,σ):=∥(I−ΠM)(Aπ,σ)∥F2=∑(i,j): Mij=0(Aijπ,σ)2.(1)d_M(A;\pi,\sigma):=\left\|(I-\Pi_M)(A^{\pi,\sigma})\right\|_F^2=\sum_{(i,j):\,M_{ij}=0}\left(A^{\pi,\sigma}_{ij}\right)^2. \tag*{(1)}

Definition 1 (Pattern distance). The pattern distance of A∈Rn×nA\in\mathbb{R}^{n\times n} from the mask M∈{0,1}n×nM\in\{0,1\}^{n\times n} is the smallest off-pattern mass over row and column permutations,

dM(A):=min⁡π,σ∈SndM(A;π,σ).(2)d_M(A):=\min_{\pi,\sigma\in S_n}d_M(A;\pi,\sigma). \tag*{(2)}

For A≠0A\ne0 the explained pattern variance vM(A):=1−dM(A)/∥A∥F2∈[0,1]v_M(A):=1-d_M(A)/\lVert A\rVert_F^2\in[0,1] is the fraction of matrix energy placed inside the pattern after optimal reordering. For symmetric matrices and for the attention matrices we also minimize over a common permutation, d~Mcom(A):=min⁡πdM(A;π,π)\tilde d_M^{\mathrm{com}}(A) := \min_{\pi} d_M(A; \pi, \pi) (the case σ=π\sigma= \pi), writing dM(A;π):=dM(A;π,π)d_M(A; \pi) := d_M(A; \pi, \pi) at a fixed π\pi; the restriction shrinks the feasible set, so d~Mcom(A)≥dM(A)\tilde d_M^{\mathrm{com}}(A) \ge d_M(A). The mask density is ρM:=∣M∣1/n2\rho_M := |M|_1/n^2 (∣M∣1|M|_1 the number of ones). dM(A)=0d_M(A) = 0 iff AA fits inside MM after some reordering, and under independent uniform row and column permutations a fraction ρM\rho_M of the energy lies inside the mask in expectation (Appendix § 10.§ 2).

Example (two notions of matrix simplicity). Pattern simplicity and low rank are independent: neither bounds the other. Let A=PS0P⊤A = PS_0P^\top with S0S_0 kk-block-diagonal, constant blocks of size b=n/kb = n/k and entries μ>0\mu> 0. The kk-block mask fits AA exactly, dM(A)=0d_M(A) = 0, while AA has kk equal singular values μb\mu b, so its best rank-rr approximation has squared Frobenius error (k−r)b2μ2(k-r)b^2\mu^2 for every r<kr < k: what the mask describes by its support, low rank describes only at rank kk. Conversely a generic rank-one uu⊤uu^\top, the simplest matrix for the SVD, fits no mask that leaves an entry out, dM(uu⊤)>0d_M(uu^\top) > 0. A matrix can thus be simple in one sense and not in the other, which is why Section 4 fits both parts jointly instead of choosing one.

Hardness

Theorem 1 (NP-hardness of pattern distance). Computing dM(A)d_M(A) exactly is NP-hard for the 2-block-diagonal mask, for independent (π,σ)(\pi,\sigma) as well as under σ=π\sigma= \pi.

Proof sketch. Reduction from Minimum Bisection [23] through the adjacency matrix of the graph with a heavy diagonal, which forces the row and column bisections to coincide; the band of width 1 under σ=π\sigma= \pi is NP-hard too, as a maximum-weight Hamiltonian path (Appendix § 10.5). Hardness is mask-specific: the arrowhead under σ=π\sigma= \pi and the diagonal and anti-diagonal masks with two permutations are solved exactly (Appendix § 11.§ 3).

Permutation ambiguities. An exact ordering need not be unique. If a noiseless signal is nonzero at every position allowed by the mask and zero elsewhere, all zero-error orderings differ only by symmetries of that mask (Appendix § 10.§ 6). Under a common row/column permutation these include the reversal of a banded order and arbitrary reorderings within blocks and among equal-sized blocks; for an arrowhead mask with n≥3n \ge3 the hub is identifiable, but the remaining indices have no identifiable order.

Algorithm 1 Alternating LAP (worked example in Appendix § 9.§ 2)

Require: A∈Rn×nA \in\mathbb{R}^{n \times n}, mask MM, iterations TT, restarts RR

  1. π^←\hat{\pi} \leftarrow Fiedler ordering

  2. for r=1,…,Rr = 1, \ldots, R do

  3. π0←π^\pi_0 \leftarrow\hat{\pi} if r=1r=1, else a random permutation; (π,σ)←(π0,π0)(\pi,\sigma) \leftarrow(\pi_0,\pi_0)

  4. for t=1,…,Tt = 1, \ldots, T do

  5. Qpcpc←∑i(1−Mip)(PπA)ic2Q^{\mathrm{pc}}_{p c} \leftarrow\sum_i(1-M_{i p})(P_\pi A)^2_{i c}; σ←LAP⁡(Q)\sigma\leftarrow\operatorname{LAP}(Q)

  6. Qpirow←∑j(1−Mpj)(APσT)ij2Q^{\mathrm{row}}_{p i} \leftarrow\sum_j(1-M_{p j})(A P_\sigma^{\mathsf T})^2_{i j}; π←LAP⁡(Qrow)\pi\leftarrow\operatorname{LAP}(Q^{\mathrm{row}})

  7. end for

  8. Update (π∗,σ∗)(\pi^*,\sigma^*) if F(π,σ)F(\pi,\sigma) improved; π^←\hat{\pi} \leftarrow best τ∈{π,π0,π^,σ}\tau\in\{\pi,\pi_0,\hat{\pi},\sigma\} by dM(A;τ,τ)d_M(A;\tau,\tau)

  9. end for

  10. for σ=π\sigma=\pi: EXCHANGE: apply pairwise swaps to π^\hat{\pi} while they lower dM(A;π^,π^)d_M(A;\hat{\pi},\hat{\pi})

  11. return best (π∗,σ∗)(\pi^*,\sigma^*), or π^\hat{\pi}

Alternating LAP

Computing dM(A)d_M(A) is a search over two permutations at once: since permutations preserve ∥⋅∥F\lVert\cdot\rVert_F, dM(A)=∥A∥F2−max⁡π,σ∑i,jMijAπ−1(i),σ−1(j)2d_M(A)=\lVert A\rVert_F^2-\max_{\pi,\sigma}\sum_{i,j}M_{ij}A^2_{\pi^{-1}(i),\sigma^{-1}(j)}, a bilinear assignment objective, a QAP under σ=π\sigma=\pi (NP-hard, Theorem 1). Building on the alternating LAP schemes of Goldengorin and Krushinsky [ [27] and Sokol et al. [ [51], we derive its assignment updates.

Lemma 1 (Column-separability). Fix πr\pi_r and let B=PπrAB=P_{\pi_r}A. With Qp,c:=∑i(1−Mi,p)Bi,c2Q_{p,c}:=\sum_i(1-M_{i,p})B^2_{i,c},

min⁡σ∈Sn∥(I−ΠM)(BPσT)∥F2=min⁡σ∈Sn∑cQσ(c),c,(3)\min_{\sigma\in S_n}\left\lVert(I-\Pi_M)(BP_\sigma^{\mathsf T})\right\rVert_F^2 = \min_{\sigma\in S_n}\sum_c Q_{\sigma(c),c}, \tag*{(3)}

a Linear Assignment Problem whose solution LAP⁡(Q)\operatorname{LAP}(Q) assigns each original column cc its position σ(c)\sigma(c). The row case is symmetric (Appendix § 10).

Here QQ is the auxiliary cost matrix of Goldengorin and Krushinsky [ [27]: Qp,cQ_{p,c} is the off-pattern cost of placing original column cc at position pp under the fixed row order; since these costs do not depend on where the other columns go, choosing the column permutation is exactly a linear assignment problem. Alternating the two one-sided problems gives Algorithm 1: from a spectral start (the Fiedler order [6]; Appendix § 12.§ 1), fix the rows and solve a column LAP, fix the columns and solve a row LAP, and repeat; random restarts guard against poor local minima. A step costs O(n3)O(n^3) (auxiliary matrix and Hungarian solver), a run O(RTn3)O(RTn^3) for RR restarts of TT iterations. Below, ALTLAP(A,M,T;(π0,σ0))(A,M,T;(\pi_0,\sigma_0)) denotes TT iterations of Algorithm 1 from (π0,σ0)(\pi_0,\sigma_0) (spectral start if the pair is omitted).

Proposition 1 (Monotone convergence). Each LAP sub-step is a global minimizer of the one-sided objective (Lemma 1), so the iterates satisfy F(π(t+1),σ(t+1))≤F(π(t),σ(t))F(\pi^{(t+1)},\sigma^{(t+1)})\leq F(\pi^{(t)},\sigma^{(t)}) with F(π,σ)=∥(I−ΠM)(PπAPσT)∥F2F(\pi,\sigma)=\left\lVert(I-\Pi_M)(P_\pi A P_\sigma^{\mathsf T})\right\rVert_F^2, and the FF-values stabilize after finitely many steps; if ties in the LAP are broken in favour of the current permutation, the iterates themselves stop at a coordinate-wise local minimum. For a common permutation the exchange phase strictly decreases dM(A;π,π)d_M(A;\pi,\pi) and stops at an order that no pairwise exchange improves.

Common permutation. For σ=π\sigma=\pi the two-sided iterate is rounded to one permutation and finished by an exchange descent on dM(A;π,π)d_M(A;\pi,\pi): the change of an exchange has a closed form, two matrix products score all n2n^2 exchanges, and improving ones are applied until none remains (Appendix § 12.§ 1). The LAP steps move whole rows and columns and stall on the ties {0,1}\{0,1\} input induces in QQ; the exchanges move one pair at a time and finish the descent (Appendix § 13.§ 1).

Variants. The lemma uses only that the cost is a sum of per-entry weights, so Algorithm 1 runs on any separable score ∑i,j(1−Mij)Wπ−1(i),σ−1(j)\sum_{i,j}(1-M_{ij})W_{\pi^{-1}(i),\sigma^{-1}(j)}: W=A∘AW=A\circ A is the pattern distance; W=AW=A (ALTLAP-lin) is the likelihood criterion for a mean shift rather than an energy contrast (§ 5.2).

Algorithm 2 PATLR: Safeguarded Pattern + Low-Rank Decomposition

Require: A∈Rn×nA \in\mathbb{R}^{n \times n}, mask MM, rank kk, outer iterations TT, LAP iterations TLAPT_{\mathrm{LAP}}

  1. (π,σ)←ALTLAP⁡(A,M,TLAP)(\pi,\sigma) \gets\operatorname{ALTLAP}(A,M,T_{\mathrm{LAP}}); X←0X \gets0; S←ΠM(PπAPσT)S \gets\Pi_M(P_\pi A P_\sigma^{\mathsf{T}})

  2. for t=1,…,Tt = 1,\ldots,T do

  3. B←Pπ(A−X)PσTB \gets P_\pi(A-X)P_\sigma^{\mathsf{T}}; S←ΠM(B)S \gets\Pi_M(B)

  4. X←SVD⁡k(A−PπTSPσ)X \gets\operatorname{SVD}_k(A-P_\pi^{\mathsf{T}}SP_\sigma)

  5. (π~,σ~)←ALTLAP⁡(A−X,M,TLAP;(π,σ))(\widetilde{\pi},\widetilde{\sigma}) \gets\operatorname{ALTLAP}(A-X,M,T_{\mathrm{LAP}};(\pi,\sigma))

  6. if dM(A−X;π~,σ~)<dM(A−X;π,σ)d_M(A-X;\widetilde{\pi},\widetilde{\sigma}) < d_M(A-X;\pi,\sigma) then (π,σ)←(π~,σ~)(\pi,\sigma) \gets(\widetilde{\pi},\widetilde{\sigma})

  7. S←ΠM(Pπ(A−X)PσT)S \gets\Pi_M(P_\pi(A-X)P_\sigma^{\mathsf{T}}) {re-synchronize SS with the accepted (π,σ)(\pi,\sigma)}

  8. end for

  9. return (π,σ),S,X(\pi,\sigma), S, X

Pattern + Low-Rank Decomposition

Formulation. The PatLR decomposition approximates PπAPσTP_\pi A P_\sigma^{\mathsf{T}} by a pattern-supported component SS (Sij=0S_{ij}=0 when Mij=0M_{ij}=0) and a low-rank component UVTUV^{\mathsf{T}} of rank ≤k\le k. Writing X=PπTUVTPσX=P_\pi^{\mathsf{T}}UV^{\mathsf{T}}P_\sigma for the low-rank part in the original coordinates, the objective is

inf⁡π,σ,S,X ∥Pπ(A−X)PσT−S∥F2s.t.S⊙(1−M)=0,rank⁡(X)≤k.(4)\inf_{\pi,\sigma,S,X}\ \left\|P_\pi(A-X)P_\sigma^{\mathsf{T}}-S\right\|_{\mathrm{F}}^2 \quad\text{s.t.}\quad S\odot(1-M)=0,\quad\operatorname{rank}(X)\le k. \tag*{(4)}

For fixed (π,σ,X)(\pi,\sigma,X) the optimal SS is the mask projection of the permuted residual, and substituting it back gives

min⁡S: S⊙(1−M)=0∥Pπ(A−X)PσT−S∥F2=dM(A−X;π,σ),(5)\min_{S:\,S\odot(1-M)=0}\left\|P_\pi(A-X)P_\sigma^{\mathsf{T}}-S\right\|_{\mathrm{F}}^2=d_M(A-X;\pi,\sigma), \tag*{(5)}

so PatLR looks for a low-rank component after whose removal the residual fits the pattern. Algorithm 2 alternates the two closed-form updates, SS by mask projection and XX by the rank-kk SVD of AA minus the pattern part, with a safeguarded permutation update: ALTLAP⁡(A−X,M,TLAP;(π,σ))\operatorname{ALTLAP}(A-X,M,T_{\mathrm{LAP}};(\pi,\sigma)) on the residual from the current pair is accepted only if it lowers dM(A−X;⋅)d_M(A-X;\cdot), and SS is then re-synchronized. For a common permutation the update takes the common-permutation output of Algorithm 1, sets σ=π\sigma=\pi and compares dM(A−X;π,π)d_M(A-X;\pi,\pi); Proposition 2 is unchanged. The infimum need not be attained and the split between SS and XX need not be unique: PatLR is a structured approximation model, scored by its reconstruction. Since π=σ=id\pi=\sigma=\mathrm{id} with S=0S=0 is feasible, the infimum never exceeds the rank-kk SVD error, and the example of § 2 shows that the gap can be large.

Proposition 2 (Monotone convergence of PATLR). For F(π,σ,S,X)=∥Pπ(A−X)PσT−S∥F2F(\pi,\sigma,S,X)=\left\|P_\pi(A-X)P_\sigma^{\mathsf{T}}-S\right\|_{\mathrm{F}}^2 subject to S⊙(1−M)=0S\odot(1-M)=0 and rank⁡(X)≤k\operatorname{rank}(X)\le k, Algorithm 2 yields a non-increasing sequence of FF-values, which therefore converges (Appendix § 11.§ 1). Because XX is continuous we do not claim finite termination or convergence of the iterates (S,X)(S,X) themselves; the algorithm stops at a tolerance ε\varepsilon on the decrease of FF or a capped iteration count.

Adaptive Pattern Selection

Pattern MM is rarely known a priori. We select it jointly with the permutations from a fixed vocabulary V={M1,…,MK}\mathcal{V}=\{M_1,\ldots,M_K\} by the density-normalized score (for A≠0A\ne0, ρM<1\rho_M<1)

s~M(A;π,σ):=dM(A;π,σ)∥A∥F2(1−ρM)3/2,s~M(A):=min⁡π,σs~M(A;π,σ).(6)\widetilde{s}_M(A;\pi,\sigma):=\frac{d_M(A;\pi,\sigma)}{\lVert A\rVert_{\mathrm{F}}^2(1-\rho_M)^{3/2}}, \qquad \widetilde{s}_M(A):=\min_{\pi,\sigma}\widetilde{s}_M(A;\pi,\sigma). \tag*{(6)}

The denominator is a reference against independent uniform row and column permutations, which place a fraction ρM\rho_M of the energy inside the mask in expectation (§ 2); its superlinear exponent penalizes dense masks beyond this coverage advantage. Under a common permutation the random-permutation reference also depends on the split of the energy between the diagonal and the off-diagonal entries (Appendix § 10.§ 2); the normalization is used as stated in both settings. Without noise a mask and every mask containing it score 00 alike, so the identified geometry need not be unique (Appendix § 11.§ 2). The default vocabulary has nine masks, blocks k∈{2,3,4,6}k\in\{2,3,4,6\}, bands w∈{1,2,4}w\in\{1,2,4\}, arrowhead and block+band (k=3,w=2)(k=3,w=2); any binary mask can be added.

Adaptive PatLR. Pattern and permutation are searched jointly by simulated annealing over V\mathcal{V} with Metropolis acceptance on s~M\tilde{s}_M (Algorithm 3, Appendix § 12.§ 2). The current (π,σ)(\pi,\sigma) is a warm start for any proposed pattern: good permutations for similar patterns are correlated, so a candidate Mj′M_j' is evaluated with ℓ=3\ell=3 LAP steps instead of a full ALTLAP run (exchange phase and PATLR only on the selected mask). After screening every mask with ℓ\ell LAP steps (O(Kℓn3)O(K\ell n^3)), the N=80N=80 search iterations cost O(N(1+ℓ)n3)O(N(1+\ell)n^3) independently of KK; in practice the selection costs about one PATLR call (Appendix § 13.8).

Experiments

Together, the experiments test whether one solver recovers different geometric structures, whether these structures complement low-rank approximation, and whether they can be selected and interpreted on real data. Unless stated otherwise we use a common row/column permutation (σ=π)(\sigma=\pi). We report our objective where the planted order is known and, where a task has its own literature, its metric alongside the methods developed for it. Comparisons are paired over 20 seeds with 95% bootstrap intervals; Figure 2 illustrates the outputs; setups, baselines and full grids are in Appendix § 13.

Figure 2. Outputs of the framework on one input of each kind (not a comparison). Top: the input in its given order; bottom: the order found by Alternating LAP for the named pattern (mask outlined in red), with the in-mask energy fraction 1−dM(A;π)/∥A∥F21-d_M(A;\pi)/\lVert A\rVert_F^2 before and after. The consecutive-ones column uses two permutations; the attention head is at n=128n=128 on a square-root colour scale; the last column is the PatLR reconstruction S+UV⊤S+UV^\top (rank 3) in the found order, with its explained variance.

Ordering Structures

Banded recovery (our objective). We first ask whether the generic solver optimizes the pattern distance as well as a general QAP solver and classical ordering heuristics do. On randomly permuted banded targets in a Gaussian and a sparse-graph regime, Table 1 reports the error reduction (ER, the fraction of the input’s off-pattern mass removed by the found order) of Alternating LAP next to reverse Cuthill–McKee [16] (RCM), Fiedler ordering plus greedy 2-swap (F+greedy) and QAP-FAQ [55]. Alternating LAP gives the largest reduction on the Gaussian inputs at every nn and on the sparse graphs at w=5w=5; FAQ is ahead by 0.04–0.06 on the sparse w=2w=2 graphs, where the ties induced by binary inputs stall the LAP steps and the exchange phase carries the fit (Appendix § 13.§ 1). RCM and GPS reduce the bandwidth, a criterion that saturates on noisy inputs, rather than the off-band mass (Appendix § 13.§ 2).

nnGauss w=2w=2 other RCMGauss w=2w=2 other F+gr.Gauss w=2w=2 dMd_M FAQGauss w=2w=2 dMd_M AltLAPGauss w=5w=5 other RCMGauss w=5w=5 other F+gr.Gauss w=5w=5 dMd_M FAQGauss w=5w=5 dMd_M AltLAPSparse w=2w=2 other RCMSparse w=2w=2 other F+gr.Sparse w=2w=2 dMd_M FAQSparse w=2w=2 dMd_M AltLAPSparse w=5w=5 other RCMSparse w=5w=5 other F+gr.Sparse w=5w=5 dMd_M FAQSparse w=5w=5 dMd_M AltLAP
300.030.840.600.870.070.980.840.980.230.450.730.670.410.780.880.91
1000.050.370.510.690.090.720.660.870.060.090.490.450.160.290.660.69
2000.030.140.460.610.080.330.610.750.020.030.360.300.090.100.520.53
5000.030.030.400.520.060.080.570.610.000.000.200.150.030.020.330.34

Table 1. Error reduction (ER; higher = better) on banded patterns, 20 seeds. RCM (via KNN sparsification on dense inputs) and F+greedy (Fiedler order plus greedy 2-SUM swaps) optimize other criteria; FAQ (three starts) and AltLAP (five restarts) both minimize dMd_M.

Latent ordering (Figure 3a). A lower pattern distance need not mean a more accurate order, so the remaining tasks are scored by their own metrics. Planted Robinson matrices, scrambled and noised, scored by Kendall ∣τ∣|\tau| against the planted order, next to spectral seriation [4] and the convex relaxation of [21]. Over 24 configurations one Alternating LAP run from the spectral order, with the band width set to the generator’s correlation length, improves on spectral seriation in 18 cells and matches or exceeds the convex relaxation in 19, the gain growing with noise and with nn; the exceptions are the cells at ℓ=25\ell=25, n=100n=100, where every method is near τ=1\tau=1, and one cell at ℓ=6\ell=6, n=100n=100 where the relaxation leads by 0.04 (Appendix Table 12).

Figure 3. Four classical tasks scored by their own metrics (means, 95% bootstrap intervals, 20 seeds). “Ours” is Alternating LAP on the mask of the task: (a) band of width 25 from the spectral order; latent ordering, n=300n=300, correlation length 25 (y-axis from 0.92). (b) staircase of interval length 12 from random restarts, with the same run on a random mask as control; noisy consecutive ones, 60 × 60. (c) equal-size block mask; sparse SBM, k=4k=4, mean degree 16, drawn as the error 1−ARI1-\mathrm{ARI} on a log axis (lower is better; dotted: detectability threshold). (d) block mask on the linear score, from random restarts and from the spectral partition; weighted planted partition, k=4k=4.

Consecutive ones (Figure 3b). The consecutive-ones property (every row an interval after a column order [9, 31]) is the staircase band in a rectangular matrix, fitted with independent row and column permutations (Appendix § 10.§ 1). On planted instances with flip noise, Alternating LAP from random restarts recovers the column order with a higher τ\tau and fewer edits than convex seriation on every seed at every noise level, while a random or a block mask of the same density recovers almost nothing: the gain is the geometry of the mask.

Circular seriation and the sensitivity of these fits to the mask width and to the generator are in Appendix § 13.§ 6, as are nested matrices, a boundary case: where the marginals already determine the order, the general optimizer does not improve over the specialized one.

Block Structures

We turn from order to grouping, where the block-mask objective is the likelihood criterion of the planted models; on the weighted matrices the solver runs on the linear score (AltLAP-lin, § 3).

Sparse and weighted block models (Figure 3c,Figure 3d). On the sparse SBM at the detectability scale (λ=1\lambda=1 the threshold [19]) the block-mask objective is the maximum-likelihood criterion [1], and two regimes appear: below λ≈1.5\lambda\approx1.5 a better criterion value does not give a better partition (Alternating LAP is below the Bethe Hessian in ARI, above it when started from its partition); above this regime Alternating LAP is competitive with the specialized methods, with the highest ARI in most cells, and at c≥16c \ge16 from λ=1.6\lambda=1.6 on it matches or exceeds the spectral baselines (Appendix Table 18). On a weighted planted partition the linear score is the likelihood criterion and AltLAP-lin is above spectral clustering from μ=0.35\mu=0.35 on (Appendix Table 19). The spectral baselines receive the true kk; our mask also assumes equal block sizes, and under unequal planted sizes, sizes estimated from a spectral partition recover most of the gap (Appendix Table 20).

Composite target: a band inside blocks. The band inside the blocks (Figure 2, third column) tests the joint refinement of communities and their internal order: two structural hypotheses combined in one mask and refined by one criterion. On 16 planted configurations we compare the natural pipeline, spectral clustering then seriation inside each cluster, with the same pipeline followed by one Alternating LAP pass on the composite mask, with block boundaries re-estimated from the order. The pass raises the error reduction on the target in every configuration, from a median 45% of the planted order’s value to 94%, keeps the blocks exact and improves the within-block order where the band is wide enough to determine it (w=3w=3); similar ER gains hold with convex seriation inside the clusters. From a cold start the composite mask alone recovers the blocks only in part: the pipeline supplies the start and the mask the target (Appendix Table 23).

Labelled networks. On four networks with published communities no single panel method is best; PatLR with rank 1 recovers the karate-club split exactly (Appendix Table 21).

Pattern + Low-Rank Decomposition

The experiments above test whether permutations reveal structure; we now ask whether representing it explicitly improves reconstruction beyond low rank. We measure denoising quality (DQ) =1−∥A^−Atrue∥F2∥Atrue∥F2=1-\frac{\lVert\hat{A}-A_{\mathrm{true}}\rVert_F^2}{\lVert A_{\mathrm{true}}\rVert_F^2} of reconstructions A^\hat{A} from Atrue+EA_{\mathrm{true}}+E (EE symmetric Gaussian), against SVD and Robust PCA, on planted matrices whose family is known (PatLR receives its mask).

Planted structure at SNR 1 (Figure 4). Seven pattern families at n=200n=200, each planted alone and together with a rank-3 component of equal energy, scrambled, with noise at SNR =∥Atrue∥F2/∥E∥F2=1=\lVert A_{\mathrm{true}}\rVert_F^2/\lVert E\rVert_F^2=1, so that the noisy input has DQ 0. On the pattern alone the mask removes most of the noise and the low-rank estimates little. On pattern plus low rank no single component suffices, and PatLR reconstructs the combined signal more accurately than either estimate alone on the masks of density ≤0.25\leq0.25. On the two half-dense masks every estimate that copies in the mask entries also copies their noise, and PatLR ends 0.03–0.04 below SVD (bound in Appendix § 13.4).

Figure 4. Denoising quality at SNR 1 (n=200n=200, 20 seeds, 95% bootstrap intervals; the noisy input has DQ 0). (a) Planted pattern. (b) Planted pattern plus a rank-3 component of equal energy. SVD at the rank that maximizes DQ; RPCA; the pattern alone (PatLR at rank 0); PatLR at rank 3; and PatLR with a random mask of the same density as control.

Two controls. A random mask of the same density, solver and rank stays 0.2–0.5 DQ below the planted mask (0.1–0.4 with the rank-3 component), but above the SVD level on the band and anti-diagonal masks. Part of the gain is therefore mass that a free permutation packs into ∣M∣\lvert M\rvert entries; the rest is the geometry. At matched nominal parameter budgets PatLR has a higher mean DQ than SVD and spectral co-clustering on all seven families (Appendix Table 10).

Real data. Where no truth is planted, Figure 2 shows the decomposition of Les Misérables [32] under a four-block template; Appendix Figure 8 follows it step by step on this network, on the karate club [60] and on three feature-correlation matrices: the pattern part takes the community blocks, the band and the feature groups, and the low-rank part the hubs and the general correlation factor.

Adaptive Pattern Selection

The experiments above give PatLR its mask; Algorithm 3 selects it jointly with the permutation, and the experiment asks how much reconstruction quality this costs and whether the planted geometry is identified. We plant each of the nine masks of the default vocabulary (n=200n=200, with and without a rank-3 component, SNR 4 and 1; 540 instances) and compare Adaptive PatLR, run over these nine masks plus three gallery distractors, with Oracle PatLR (the planted mask), brute force over the same vocabulary and SVD at its best rank (Figure 5; Appendix § 13.§ 5.1).

Figure 5. Adaptive pattern selection (n=200n=200, 540 instances). (a, b) Mask selected by Adaptive PatLR (columns; the checkerboard is counted with block k=2k=2) for each planted mask (rows) at SNR 4 and SNR 1, in % of instances over both generators; red frames: the selected mask contains the planted one (block+band covers block k=3k=3 up to two rows). (c) DQ of Adaptive against Oracle PatLR per instance. Per-family numbers: Appendix Table 11.

Quality (Figure 5c). Adaptive PatLR reaches the oracle’s denoising quality on essentially every instance (median ratio 1.00, 5th percentile 0.92), where SVD at its best rank averages less than half of the oracle’s value at SNR 1.

Identification (Figure 5a,Figure 5b). The outcome varies by family: arrowhead, block+band and the block templates k≥4k \ge4 are recovered reliably, whereas thin bands and block k=3k=3 often select a broader or alternative mask (a wider band, a block template or block+band) within 0.07 of the oracle’s DQ; good reconstruction therefore does not imply exact recovery of the geometry. The anti-diagonal and triangular distractors are never selected.

Brute force. An exhaustive scan of the vocabulary with the LAP phase gives the same reconstruction (within 0.01) and similar selections at a cost growing with ∣V∣|\mathcal{V}|; the search costs one PatLR call.

Attention Heads

We use attention matrices to test whether pattern labels are stable across prompts and context lengths, whether the reordering adds information beyond the native token order, in which the literature describes head types, and whether the layerwise profile of labels is shared across three models.

Setup. We score every head of GPT-2, Qwen2.5-0.5B and Qwen2.5-7B against a vocabulary of nine geometric masks (bands, blocks, arrowhead, block+band, diagonal), applied to the causal attention matrices without requiring the reordered matrix to stay causal, with the density-normalized score ((6)), on 20 WikiText-2 passages at n∈{128,512}n \in\{128, 512\} tokens; the native token order is a candidate for every mask, and the label of a (head, prompt) pair is the mask with the lowest score (Appendix § 13.§ 7).

Labels and layer organization. Arrowhead, the geometry of the attention sink [59, 61], is the label of 69% / 67% / 80% of the (head, prompt) pairs of GPT-2 / Qwen2.50.5B / Qwen2.5-7B at n=512n=512, block masks take most of the rest, thin bands and the diagonal a few percent. The label is a fit, not the best of a poor set: the selected mask’s score is about an order of magnitude below its random-permutation level. By layer (Figure 6a), the first three to four layers of every model carry block labels and the later layers arrowhead; on Qwen2.5-0.5B the last two layers return to block-k2k2. Most block-labelled pairs are wide local heads in the native token order, labelled by the block mask containing their window (Appendix Figure 13).

Figure 6. Attention heads at n=512n=512, unified scoring. (a) Qwen2.5-7B: share of the top-1 label per layer over 20 prompts. (b) Modal label per relative-depth bin for the three models; markers show the bins where all three agree. (c) Arrowhead share under the native token order and with reordering, with the share of (head, prompt) labels that change (Appendix § 13.7.4).

Are the permutations needed? Scoring the same pairs in their native token order (Figure 6c) changes a few percent of the labels on GPT-2 and Qwen2.5-0.5B; on Qwen2.5-7B the arrowhead share rises from 0.61 to 0.80 and 23% of the labels change. The reason is that on a quarter of the passages the sink is not the first token: there the native-order arrowhead share is below 2%, and the reordering restores the label (Appendix § 13.7.4). The reordering thus buys a label independent of where the sink sits.

Stability. The mean agreement of a head’s label with its modal label over the 20 prompts is 0.96–0.99 for arrowhead heads and 0.64–0.74 for the others. Between n=128n=128 and n=512n=512 the modal label of a head is unchanged for more than nine heads in ten. On a shared 10-bin relative-depth grid the per-layer modal label agrees across the three models in 8/10 bins (Figure 6b): blocks in the first tenth and arrowhead thereafter (Appendix § 13.7.3).

Discussion and Limitations

Limitations. The dense implementation costs O(n3)O(n^3) per LAP step and per exchange round, which makes large-matrix and long-context analyses costly (Appendix § 13.8). The permutation search is heuristic and does not guarantee global optimality (§ 3). Adaptive selection operates within a supplied mask vocabulary: a selected label is the best fit among the candidates, not an identification of the generating geometry (§ 5.4). Our theoretical guarantees concern optimization, while recovery under noise is evaluated empirically. The attention study covers three decoder-only models at 128 and 512 tokens; other architectures and longer contexts remain future work.

Conclusion

We introduced permutation-structural simplicity as an axis of matrix structure complementary to low rank: the pattern distance relates a dozen classical reordering problems to one objective (Table 2), Alternating LAP is one solver for any binary mask, PatLR adds a low-rank residual, Adaptive PatLR selects the pattern from a vocabulary, and on attention heads the same score gives stable labels with one depth profile across three models.

Acknowledgments and Disclosure of Funding

We thank the anonymous reviewers and the area chair for suggestions that led to the specialized baselines, the capacity controls, and the hardness statement. This work received no third-party funding. The authors declare no competing interests.

Pattern Dictionary, Worked Example and Notation

Pattern dictionary

Table 2 lists the pattern families of Figure 1 together with the classical problems they encode; families used in our experiments are marked with a dagger, the others are included to delineate the scope of the formulation and are not analysed here. Table 3 relates the masks to the established problems and to the specialized methods used as baselines.

Figure 1. Gallery of patterns, one representative per structural hypothesis (each cell is the binary mask MM, blue = 1), grouped by the kind of structure they encode: order, grouping, nesting, separability, branching, self-similarity. Daggers mark the families used in our experiments; Table 2 gives the classical problem behind each pattern. Masks are shown up to the permutations the framework optimizes over (an anti-diagonal band equals a band under column reversal). Any binary mask is admissible: MM encodes the structure hypothesized for an application or is selected from a vocabulary.

Mask / settingClassical problemSpecialized methods comparedWhere
Fixed MM, one permutationKoopmans–Beckmann QAPQAP-FAQ (as alternative solver)§ 5.1
Fixed MM, two permutationsBilinear assignment, graph matchingBirkhoff relaxations (discussed)§ 3
Banded, exact supportBandwidth / profile reductionRCM, Gibbs–Poole–Stockmeyer§ 5.1
Banded / Robinson, noisySeriation, latent orderingSpectral and convex seriation§ 5.1
Staircase band (rectangular)Consecutive-ones, interval seriationBarycentre, spectral, convex seriation§ 5.1
Cyclic bandCircular seriationCircular spectral embeddingApp. § 13.6.2
Block-diagonal, {0,1}\{0,1\}Community detection, SBMBethe Hessian, non-backtracking, regularized spectral, Leiden§ 5.2
Block-diagonal, weightedPlanted partition (likelihood)Spectral clustering§ 5.2
Band inside blocksComposite (no dedicated method)Cluster-then-order pipeline§ 5.2
Any MM + low rank (PatLR)Structured plus low-rank approximationSVD at matched nominal budget, RPCA, spectral co-clustering§ 5.3

Table 3. Correspondence between pattern masks and established problems, with the specialized methods used as baselines in this paper.

A 6 × 6 example

Take n=6n = 6, the band mask Mij=1M_{ij} = 1 iff ∣i−j∣≤1|i-j| \le1, and the reference matrix Bij=max⁡(0,5−2∣i−j∣)B_{ij} = \max(0, 5 - 2|i-j|). Scramble it by p=(0,2,4,1,3,5)p = (0, 2, 4, 1, 3, 5) (zero-based), i.e. Aij=Bpi,pjA_{ij} = B_{p_i,p_j}:

B (reference)=(531000353100135310013531001353000135)A (scrambled)=(510300151330015033330510033151003015)B\ \text{(reference)} = \begin{pmatrix} 5 & 3 & 1 & 0 & 0 & 0 \\ 3 & 5 & 3 & 1 & 0 & 0 \\ 1 & 3 & 5 & 3 & 1 & 0 \\ 0 & 1 & 3 & 5 & 3 & 1 \\ 0 & 0 & 1 & 3 & 5 & 3 \\ 0 & 0 & 0 & 1 & 3 & 5 \end{pmatrix} \qquad A\ \text{(scrambled)} = \begin{pmatrix} 5 & 1 & 0 & 3 & 0 & 0 \\ 1 & 5 & 1 & 3 & 3 & 0 \\ 0 & 1 & 5 & 0 & 3 & 3 \\ 3 & 3 & 0 & 5 & 1 & 0 \\ 0 & 3 & 3 & 1 & 5 & 1 \\ 0 & 0 & 3 & 0 & 1 & 5 \end{pmatrix}

BB is concentrated near the diagonal but not exactly supported on the mask: its eight entries at ∣i−j∣=2|i-j| = 2 have magnitude one, so the optimum is dM(A)=dM(B)=8d_M(A) = d_M(B) = 8, while the objective at the identity ordering is ∥(1−M)⊙A∥F2=90\|(1-M) \odot A\|_F^2 = 90. One step. With rows fixed, placing column cc at position qq costs Qq,c=∑i(1−Miq)Aic2Q_{q,c} = \sum_i (1-M_{iq})A_{ic}^2, the off-pattern mass this placement would create (Lemma 1):

M (band, w=1)=(110000111000011100001110000111000011)Q (rows = positions q, columns = c)=(91943263635918182627262510181026262626101810252627261818935362643199)M\ \text{(band, }w=1\text{)} = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix} \qquad Q\ \text{(rows = positions }q\text{, columns = }c\text{)} = \begin{pmatrix} 9 & 19 & 43 & 26 & 36 & 35 \\ 9 & 18 & 18 & 26 & 27 & 26 \\ 25 & 10 & 18 & 10 & 26 & 26 \\ 26 & 26 & 10 & 18 & 10 & 25 \\ 26 & 27 & 26 & 18 & 18 & 9 \\ 35 & 36 & 26 & 43 & 19 & 9 \end{pmatrix}

An optimal assignment on QQ orders the columns (0,1,3,2,4,5)(0, 1, 3, 2, 4, 5) at cost 74, exactly the off-pattern mass after the move; the row step is symmetric. Run. The successive exact one-sided minimizations give 90→74→40→890 \to74 \to40 \to8, and both final orders equal (0,3,1,4,2,5)=p−1(0, 3, 1, 4, 2, 5) = p^{-1}, so the reordered matrix is exactly BB. Each step is the global optimum of its subproblem, so the objective never increases (Proposition 1); this does not imply global convergence in general, since other initializations or tied assignments can end at coordinatewise local minima, which is what the spectral initialization and the restarts address.

Notation and terminology

Symbol / termMeaning
Aπ,σ=PπAPσTA^{\pi,\sigma}=P_{\pi}AP_{\sigma}^{\mathsf{T}}rows reordered by π\pi, columns by σ\sigma; (Aπ,σ)ij=Aπ−1(i),σ−1(j)(A^{\pi,\sigma})_{ij}=A_{\pi^{-1}(i),\sigma^{-1}(j)}, a permutation mapping an original index to its position
ΠM(X)=M⊙X\Pi_M(X)=M\odot Xmasking operator; (I−ΠM)(X)(I-\Pi_M)(X) is the off-pattern part
dM(A;π,σ)d_M(A;\pi,\sigma)off-pattern squared Frobenius mass at fixed permutations (1)
dM(A)d_M(A)its minimum over independent row and column permutations (2)
dMcom(A),dM(A;π)d_M^{\mathrm{com}}(A),d_M(A;\pi)minimum under a common permutation (σ=π\sigma=\pi); the value at a fixed π\pi
νM(A)\nu_M(A)explained pattern variance 1−dM(A)/∥A∥F21-d_M(A)/\lVert A\rVert_F^2
ρM=∣M∣1/n2\rho_M=|M|_1/n^2mask density (∣M∣1|M|_1 the number of ones)
s~M(A)\widetilde{s}_M(A)density-normalized score dM(A)/(∥A∥F2(1−ρM)3/2)d_M(A)/(\lVert A\rVert_F^2(1-\rho_M)^{3/2}), equation (6)
S,X=PπTUVTPσS,X=P_{\pi}^{\mathsf{T}}UV^{\mathsf{T}}P_{\sigma}PatLR pattern part (reordered frame) and low-rank part (original frame), Section 4
2-SUM∑ij∣Aij∣(π(i)−π(j))2\sum_{ij}|A_{ij}|(\pi(i)-\pi(j))^2, the seriation objective whose spectral relaxation is the Fiedler order
ERerror reduction 1−dM(A;π^)/dM(A;id)1-d_M(A;\hat{\pi})/d_M(A;\mathrm{id}) of the found order over the input order
BEband energy, the in-mask energy fraction after reordering
DQdenoising quality 1−∥A^−Atrue∥F/∥Atrue∥F1-\lVert\hat{A}-A_{\mathrm{true}}\rVert_F/\lVert A_{\mathrm{true}}\rVert_F, against the clean matrix
EVexplained variance 1−∥A−A^∥F2/∥A∥F21-\lVert A-\hat{A}\rVert_F^2/\lVert A\rVert_F^2, against the observed matrix
block+band (k,w)(k,w)union of kk equal diagonal blocks and the band ∣i−j∣≤w|i-j|\le w (vocabulary, Table 10, attention)
band-in-blockintersection, a band inside each block: the composite target of § 5.2 and Appendix § 13.6.4
anti-diagonal (w)(w)anti-diagonal band ∣i+j−(n+1)∣≤w|i+j-(n+1)|\le w (w=10w=10 at n=200n=200); Table 2 lists w=0w=0
ALTLAP-linAlternating LAP on the separable score with W=AW=A, the linear criterion (§ 3)

Table 4. Symbols and terms used throughout; standard notions (LAP, QAP, Fiedler vector, ARI, Kendall τ\tau) are used in their usual sense.

Deferred Proofs

Basic identities and scope of the formulation

We use the conventions Aπ,σ:=PπAPσTA^{\pi,\sigma}:=P_{\pi}AP_{\sigma}^{\mathsf{T}}, (Aπ,σ)ij=Aπ−1(i),σ−1(j)(A^{\pi,\sigma})_{ij}=A_{\pi^{-1}(i),\sigma^{-1}(j)}; ΠM(X):=M⊙X\Pi_M(X):=M\odot X is the masking operator and (I−ΠM)(X)=(1−M)⊙X(I-\Pi_M)(X)=(1-M)\odot X extracts the off-pattern part. For rectangular AA, M∈Rm×nM\in\mathbb{R}^{m\times n} the same definitions apply with π∈Sm\pi\in S_m, σ∈Sn\sigma\in S_n and ρM=∣M∣1/(mn)\rho_M=|M|_1/(mn); Lemma 1 and Algorithm 1 are unchanged, the two LAPs having sizes nn and mm. The restriction σ=π\sigma=\pi gives the common-permutation distance dMcom(A)=min⁡πdM(A;π)d_M^{\mathrm{com}}(A)=\min_{\pi}d_M(A;\pi) with dM(A;π):=∥(I−ΠM)(Aπ)∥F2d_M(A;\pi):=\lVert(I-\Pi_M)(A^{\pi})\rVert_F^2; it is natural for symmetric A=ATA=A^{\mathsf{T}}, M=MTM=M^{\mathsf{T}} and is also imposed on the asymmetric attention matrices (§ 5.5). Because ∥Aπ,σ∥F=∥A∥F\lVert A^{\pi,\sigma}\rVert_F=\lVert A\rVert_F, the partition of entries by MM yields the in-pattern reformulation dM(A)=∥A∥F2−max⁡π,σ∥ΠM(Aπ,σ)∥F2d_M(A)=\lVert A\rVert_F^2-\max_{\pi,\sigma}\lVert\Pi_M(A^{\pi,\sigma})\rVert_F^2 (§ 2), which we use freely in the proofs below.

The boundary of the formulation. Masks whose objective does not depend on the permutation (the full mask; under σ=π\sigma=\pi the diagonal and, for symmetric AA, the triangle) are collected in Appendix § 11.§ 3. Some classical notions of structure after reordering are not fixed binary supports and therefore fall outside Definition 1 as stated: Monge and Robinson matrices are ordering constraints on the values of AA (a Robinson matrix is banded only approximately, which is why § 5.1 fits a band of the correlation length to it); a nested hierarchy of blocks coincides, as a binary mask, with its coarsest level, so the hierarchy is visible in a support only through separators (nested dissection); and N ⁣: ⁣MN\!:\!M sparsity [41] is a family of masks whose allowed positions differ between rows and groups, fitted by alternating the permutation with a per-group selection of the support rather than with one mask.

Basic properties of dMd_M

(i) Nonnegativity follows from the Frobenius norm being nonnegative. Equality dM(A)=0d_M(A)=0 iff some (π,σ)(\pi,\sigma) places every off-pattern entry of Aπ,σA^{\pi,\sigma} at zero, i.e. Aπ,σA^{\pi,\sigma} is MM-supported. (ii) Upper bound. By the in-pattern reformulation of (2), dM(A)=∥A∥F2−max⁡π,σ∥ΠM(Aπ,σ)∥F2≤∥A∥F2d_M(A)=\lVert A\rVert_F^2-\max_{\pi,\sigma}\lVert\Pi_M(A^{\pi,\sigma})\rVert_F^2\leq\lVert A\rVert_F^2. For the tighter bound, average over (π,σ)∈Sn×Sn(\pi,\sigma)\in S_n\times S_n: each entry Akl2A_{kl}^2 appears at each position (i,j)(i,j) with equal probability, so Eπ,σ[∥ΠM(Aπ,σ)∥F2]=ρM∥A∥F2\mathbb{E}_{\pi,\sigma}[\lVert\Pi_M(A^{\pi,\sigma})\rVert_F^2]=\rho_M\lVert A\rVert_F^2. Hence max⁡π,σ∥ΠM(Aπ,σ)∥F2≥ρM∥A∥F2\max_{\pi,\sigma}\lVert\Pi_M(A^{\pi,\sigma})\rVert_F^2\geq\rho_M\lVert A\rVert_F^2, giving dM(A)≤(1−ρM)∥A∥F2d_M(A)\leq(1-\rho_M)\lVert A\rVert_F^2. The averaging argument uses independent π\pi and σ\sigma. Under the restriction σ=π\sigma=\pi a common permutation never moves a diagonal entry off the diagonal, so with DA=∑iAii2D_A=\sum_i A_{ii}^2, OA=∑i≠jAij2O_A=\sum_{i\neq j}A_{ij}^2 and mdiag,moffm_{\mathrm{diag}},m_{\mathrm{off}} the numbers of diagonal and off-diagonal positions of MM,

Eπ∥ΠM(Aπ,π)∥F2=mdiagnDA+moffn(n−1)OA,\mathbb{E}_{\pi}\lVert\Pi_M(A^{\pi,\pi})\rVert_F^2=\frac{m_{\mathrm{diag}}}{n}D_A+\frac{m_{\mathrm{off}}}{n(n-1)}O_A,

and the bound (1−ρM)∥A∥F2(1-\rho_M)\lVert A\rVert_F^2 can fail: for A=(0110)A=\begin{pmatrix}0&1\\1&0\end{pmatrix} and M=I2M=I_2, min⁡πdM(A;π,π)=2>(1−ρM)∥A∥F2=1\min_\pi d_M(A;\pi,\pi)=2>(1-\rho_M)\lVert A\rVert_F^2=1. The same remark applies to the expectation ρM∥A∥F2\rho_M\lVert A\rVert_F^2 used to motivate the density normalization in Section 4.1. More generally the common-permutation distance is a restriction of the feasible set: it is never below dM(A)d_M(A) and can exceed it even for symmetric AA and MM (the same example has dM(A)=0d_M(A)=0 with two permutations and 22 under one), so statements proved for independent permutations transfer to the case σ=π\sigma=\pi only where this is said.

(iii) Permutation invariance. dM(PαAPβT)=min⁡π,σ∥(I−ΠM)(PπPαAPβTPσT)∥F2=min⁡π,σ∥(I−ΠM)(PπαAPσβT)∥F2=min⁡π′,σ′dM(A;π′,σ′)=dM(A)d_M(P_\alpha A P_\beta^{\mathsf T})=\min_{\pi,\sigma}\lVert(I-\Pi_M)(P_\pi P_\alpha A P_\beta^{\mathsf T}P_\sigma^{\mathsf T})\rVert_F^2=\min_{\pi,\sigma}\lVert(I-\Pi_M)(P_{\pi\alpha}AP_{\sigma\beta}^{\mathsf T})\rVert_F^2=\min_{\pi',\sigma'}d_M(A;\pi',\sigma')=d_M(A), reparametrising π′=πα\pi'=\pi\alpha, σ′=σβ\sigma'=\sigma\beta. □

Proof of Lemma 1 (Column-separability)

Expand the off-pattern mass with rows fixed at πr\pi_r and columns at σ\sigma:

∑i,j(1−Mij)(PπrAPσT)ij2=∑i,j(1−Mij)Aπr−1(i),σ−1(j)2=∑i,j(1−Mij)Bi,σ−1(j)2.(7)\begin{aligned} \sum_{i,j}(1-M_{ij})(P_{\pi_r}AP_\sigma^{\mathsf T})_{ij}^2 \\ &=\sum_{i,j}(1-M_{ij})A_{\pi_r^{-1}(i),\sigma^{-1}(j)}^2=\sum_{i,j}(1-M_{ij})B_{i,\sigma^{-1}(j)}^2. \tag*{(7)} \end{aligned}

Substituting p=jp=j (target position) and c=σ−1(j)c=\sigma^{-1}(j) (original column placed at position jj):

(7)=∑p=1n∑i=1n(1−Mip)Bi,σ−1(p)2=∑c=1n∑i=1n(1−Mi,σ(c))Bi,c2=∑c=1nQσ(c),c,(8)(7)=\sum_{p=1}^{n}\sum_{i=1}^{n}(1-M_{ip})B_{i,\sigma^{-1}(p)}^2=\sum_{c=1}^{n}\sum_{i=1}^{n}(1-M_{i,\sigma(c)})B_{i,c}^2=\sum_{c=1}^{n}Q_{\sigma(c),c}, \tag*{(8)}

using Qp,c=∑i(1−Mip)Bi,c2Q_{p,c}=\sum_i(1-M_{ip})B_{i,c}^2. The expression ∑cQσ(c),c\sum_cQ_{\sigma(c),c} over bijections σ:[n]→[n]\sigma:[n]\to[n] is exactly a Linear Assignment Problem. The row case follows identically with rows and columns exchanged. □

Proof of Proposition 1 (Monotone convergence)

Define F(πr,σ):=∥(I−ΠM)(PπrAPσT)∥F2F(\pi_r,\sigma):=\lVert(I-\Pi_M)(P_{\pi_r}AP_\sigma^{\mathsf T})\rVert_F^2. At each half-step, one permutation is fixed and the other is set to the global minimizer of the resulting LAP (Lemma 1):

σ(t+1)=arg⁡min⁡σF(πr(t),σ)⇒F(πr(t),σ(t+1))≤F(πr(t),σ(t)).\sigma^{(t+1)}=\mathop{\arg\min}_{\sigma}F(\pi_r^{(t)},\sigma)\quad\Rightarrow\quad F(\pi_r^{(t)},\sigma^{(t+1)})\leq F(\pi_r^{(t)},\sigma^{(t)}).

Similarly, πr(t+1)=arg⁡min⁡πrF(πr,σ(t+1))\pi_r^{(t+1)}=\mathop{\arg\min}_{\pi_r}F(\pi_r,\sigma^{(t+1)}) gives F(πr(t+1),σ(t+1))≤F(πr(t),σ(t+1))F(\pi_r^{(t+1)},\sigma^{(t+1)})\leq F(\pi_r^{(t)},\sigma^{(t+1)}). Each full iteration reduces (or maintains) FF. Since FF takes values in the finite set {F(π,σ):π,σ∈Sn}\{F(\pi,\sigma):\pi,\sigma\in S_n\}, the sequence of values is eventually constant. Stabilization of the values alone does not stop the iterates: when the LAP has several optimal assignments the permutations can keep moving on a plateau of constant FF. If ties are broken by keeping the current permutation whenever it already attains the LAP optimum, every change of a permutation strictly decreases FF, so only finitely many changes occur and the final pair is a coordinate-wise local minimum (neither one-sided LAP can improve it). □

Proof of Theorem 1 (NP-hardness)

Throughout, G=(V,E)G=(V,E) is a simple graph with ∣V∣=n|V|=n and ∣E∣=m|E|=m, and AGA_G its {0,1}\{0,1\} adjacency matrix. Restricting the feasible set to σ=π\sigma=\pi changes the problem, so hardness of the symmetric problem does not by itself imply hardness of the two-permutation problem; the reduction treats both cases. For a pair (π,σ)(\pi,\sigma) the entry AuvA_{uv} is placed at position (π(u),σ(v))(\pi(u),\sigma(v)).

We reduce from Minimum Bisection Garey and Johnson, [23]: given GG with nn even, find ∣S∣=n/2|S|=n/2 minimizing cut⁡(S,Sˉ)\operatorname{cut}(S,\bar S). Let MM be the 2-block mask with blocks of size n/2n/2 and set

A=AG+(m+1)I.A=A_G+(m+1)I.

For (π,σ)(\pi,\sigma) let SS be the set of vertices that π\pi places in the first n/2n/2 row positions and TT the set that σ\sigma places in the first n/2n/2 column positions. An entry is off-pattern iff its row and column positions lie in different blocks, so

dM(A;π,σ)=(m+1)2∣S△T∣+∑u∈S, v∉T(AG)uv+∑u∉S, v∈T(AG)uv.d_M(A;\pi,\sigma)=(m+1)^2|S\mathbin{\triangle}T|+\sum_{u\in S,\,v\notin T}(A_G)_{uv}+\sum_{u\notin S,\,v\in T}(A_G)_{uv}.

The two edge sums together are at most 2m2m. If S≠TS\ne T then, because ∣S∣=∣T∣|S|=|T|, ∣S△T∣≥2|S\mathbin{\triangle}T|\ge2 and dM(A;π,σ)≥2(m+1)2>2md_M(A;\pi,\sigma)\ge2(m+1)^2>2m, whereas any pair with S=TS=T costs exactly 2cut⁡(S,Sˉ)≤2m2\operatorname{cut}(S,\bar{S})\le2m. Hence every minimizer has S=TS=T and dM(A)=2min⁡∣S∣=n/2cut⁡(S,Sˉ)d_M(A)=2\min_{|S|=n/2}\operatorname{cut}(S,\bar{S}). The same identity holds under σ=π\sigma=\pi (where S=TS=T automatically), which is the original symmetric reduction.

The band of width 1 under σ=π\sigma=\pi. Let AA be symmetric and MM the banded mask with w=1w=1. Under σ=π\sigma=\pi the in-band mass is

∑∣i−j∣≤1Aπ−1(i),π−1(j)2=∑uAuu2+2∑i=1n−1Aπ−1(i),π−1(i+1)2,\sum_{|i-j|\le1}A^2_{\pi^{-1}(i),\pi^{-1}(j)} =\sum_u A^2_{uu}+2\sum_{i=1}^{n-1}A^2_{\pi^{-1}(i),\pi^{-1}(i+1)},

so by the in-pattern reformulation (§ 2) minimizing dMd_M is equivalent to maximizing ∑i=1n−1Aπ−1(i),π−1(i+1)2\sum_{i=1}^{n-1}A^2_{\pi^{-1}(i),\pi^{-1}(i+1)} over orderings, i.e. finding a maximum-weight Hamiltonian path in the complete graph with edge weights Auv2A^2_{uv}. For A=AGA=A_G this sum equals n−1n-1 iff GG has a Hamiltonian path, so even {0,1}\{0,1\} weights suffice and computing the value of dMd_M is NP-hard [23]. Deciding whether dM=0d_M=0 (bandwidth 1) is polynomial [50]; the hardness concerns the value of dMd_M when it is positive, and we do not claim it for independent permutations.

Permutation ambiguities: automorphisms of a mask

In words: a planted instance has zero error at the planted permutations; any other zero-error pair must place the whole support of the signal inside the mask; and when the signal fills the mask, such a pair can only be a symmetry of the mask. Formally, let Aut⁡(M):={(α,β)∈Sn2:Mα(i),β(j)=Mij ∀i,j}\operatorname{Aut}(M):=\{(\alpha,\beta)\in S_n^2:M_{\alpha(i),\beta(j)}=M_{ij}\ \forall i,j\} be the joint automorphism group of MM (the pairs of row and column permutations that map the mask onto itself), and Aut⁡sym(M):={σ∈Sn:Mσ(i),σ(j)=Mij}\operatorname{Aut}^{\mathrm{sym}}(M):=\{\sigma\in S_n:M_{\sigma(i),\sigma(j)}=M_{ij}\} its single-permutation version for M=MTM=M^\mathsf{T}.

Proposition 3 (Zero-error permutations). Let S0S_0 be MM-supported and A=Pπ∗TS0Pσ∗A=P_{\pi^*}^{\mathsf{T}}S_0P_{\sigma^*}. Then dM(A)=0d_M(A)=0, attained at (π∗,σ∗)(\pi^*,\sigma^*); every pair with dM(A;π^,σ^)=0d_M(A;\hat{\pi},\hat{\sigma})=0 has relative permutations (α,β)=(π^∘(π∗)−1,σ^∘(σ∗)−1)(\alpha,\beta)=(\hat{\pi}\circ(\pi^*)^{-1},\hat{\sigma}\circ(\sigma^*)^{-1}), the found pair expressed relative to the planted one, for which PαS0PβTP_\alpha S_0P_\beta^\mathsf{T} is MM-supported; and if supp⁡(S0)=supp⁡(M)\operatorname{supp}(S_0)=\operatorname{supp}(M), then (α,β)∈Aut⁡(M)(\alpha,\beta)\in\operatorname{Aut}(M). Under σ=π\sigma=\pi the same holds for instances planted by one permutation, A=Pπ∗TS0Pπ∗A=P_{\pi^*}^{\mathsf{T}}S_0P_{\pi^*}, with Aut⁡sym(M)\operatorname{Aut}^{\mathrm{sym}}(M) in place of Aut⁡(M)\operatorname{Aut}(M) (an instance planted by two different permutations need not have dM(A;π)=0d_M(A;\pi)=0 for any π\pi).

Proof. dM(A;π∗,σ∗)=∥(I−ΠM)(S0)∥F2=0d_M(A;\pi^*,\sigma^*)=\|(I-\Pi_M)(S_0)\|_F^2=0 by the support condition. If dM(A;π^,σ^)=0d_M(A;\hat{\pi},\hat{\sigma})=0 then Pπ^APσ^T=PαS0PβTP_{\hat{\pi}}AP_{\hat{\sigma}}^\mathsf{T}=P_\alpha S_0P_\beta^\mathsf{T} is MM-supported. If moreover supp⁡(S0)=supp⁡(M)\operatorname{supp}(S_0)=\operatorname{supp}(M), then supp⁡(PαS0PβT)={(α(i),β(j)):Mij=1}⊆supp⁡(M)\operatorname{supp}(P_\alpha S_0P_\beta^\mathsf{T})=\{(\alpha(i),\beta(j)):M_{ij}=1\}\subseteq\operatorname{supp}(M), and since permutations preserve cardinality the containment is an equality, i.e. Mα(i),β(j)=MijM_{\alpha(i),\beta(j)}=M_{ij} for all i,ji,j. The symmetric case is the same argument with α=β\alpha=\beta. Note that Aut⁡(M)\operatorname{Aut}(M) is the joint row ×\times column action, in general strictly larger than the product of the row and column stabilizers: for M=InM=I_n it is the diagonal copy of SnS_n, while the only purely row-preserving permutation is the identity.

Proposition 4 (Automorphism groups of symmetric patterns). In the symmetric case (σ=π,M=MT)(\sigma= \pi, M = M^{\mathsf{T}}) the ambiguities of the three main families are the following.

(i) Banded mask (Mij=1[∣i−j∣≤w],w≥1,n>2w+1)(M_{ij} = \mathbb{1}[|i-j| \leq w], w \geq1, n > 2w+1): the only symmetries are the identity and the reversal i↦n+1−ii \mapsto n+1-i, so an order is recoverable up to global reversal; Aut⁡sym(M)={id,rev}\operatorname{Aut}^{\mathrm{sym}}(M) = \{\mathrm{id}, \mathrm{rev}\}.

(ii) kk-block mask (equal blocks of size b=n/kb = n/k): the symmetries are arbitrary permutations of the kk blocks combined with arbitrary permutations within each block, so the partition into blocks is recoverable and the order within a block is not; Aut⁡sym(M)≅(Sb)k⋊Sk\operatorname{Aut}^{\mathrm{sym}}(M) \cong(S_b)^k \rtimes S_k, the wreath product Sb≀SkS_b \wr S_k.

(iii) Arrowhead mask (n≥3)(n \geq3): every permutation fixing the hub is a symmetry and no other is, so only the hub is identifiable; Aut⁡sym(M)≅Sn−1\operatorname{Aut}^{\mathrm{sym}}(M) \cong S_{n-1}.

These ambiguities fix what recovery can mean, and the experiments score accordingly: an order by ∣τ∣|\tau|, i.e. up to reversal (§ 5.1), a partition by ARI (§ 5.2), and an arrowhead fit as the identification of a hub.

Proof. For (i): in the simple graph on {1,…,n}\{1,\ldots,n\} defined by the off-diagonal support of MM (i∼ji \sim j iff 1≤∣i−j∣≤w1 \leq|i-j| \leq w; the diagonal is preserved by every permutation), the vertices of minimum degree ww are exactly 11 and nn (for w≥1w \geq1 and n>2w+1n > 2w+1 every interior vertex has degree ≥w+1\geq w+1), so an automorphism fixes or swaps them; composing with rev\mathrm{rev} we may assume σ(1)=1\sigma(1) = 1. The neighbours 2,…,w+12,\ldots,w+1 of vertex 11 have the distinct degrees w+1,…,2ww+1,\ldots,2w, so each is fixed, and for j=2,…,n−wj = 2,\ldots,n-w the closed neighbourhood of the fixed vertex jj contains exactly one vertex not yet fixed, j+wj+w, which is therefore fixed as well. Hence σ=id\sigma= \mathrm{id}. (At w=0w = 0 the mask is InI_n and every permutation is an automorphism.) For (ii): Mij=1M_{ij} = 1 iff ⌈i/b⌉=⌈j/b⌉\lceil i/b\rceil= \lceil j/b\rceil, so the off-diagonal support is a disjoint union of kk cliques of size bb; an automorphism maps cliques to cliques, hence permutes the blocks and acts by an arbitrary permutation within each. For (iii): any σ\sigma with σ(1)=1\sigma(1) = 1 preserves MM, and for n≥3n \geq3 the hub is the only vertex adjacent to all others, so every automorphism fixes it (at n=2n = 2 the arrowhead is the full mask).

Further Properties of the Framework

PatLR updates and proof of monotone convergence

The infimum in (4) need not be attained: the set of sums S+UVTS + UV^{\mathsf{T}} is not closed, as for low-rank plus sparse models [52]; the algorithm uses only the conditional minimizers in SS and XX, which exist, and a safeguarded proposal in the permutations. Nor is the split unique: for an in-mask position (i,j)(i,j) and H=eiejTH = e_i e_j^{\mathsf{T}}, every pair S=tHS = tH, X=(1−t)HX = (1-t)H reconstructs A=HA = H exactly, so without further constraints the components are a decomposition of the fit, not identified parts, and the experiments score the reconstruction S+UVTS + UV^{\mathsf{T}}. For fixed permutations, both inner updates are exact. Writing

F(π,σ,S,X)=∥Pπ(A−X)PσT−S∥F2F(\pi,\sigma,S,X) = \left\|P_{\pi}(A-X)P_{\sigma}^{\mathsf{T}} - S\right\|_{F}^{2}

with S⊙(1−M)=0S \odot(1-M) = 0 and rank⁡(X)≤k\operatorname{rank}(X) \leq k:

  1. the pattern step is the projection S∗=ΠM(Pπ(A−X)PσT)S^{*} = \Pi_M(P_{\pi}(A-X)P_{\sigma}^{\mathsf{T}});

  2. the low-rank step is the rank-kk truncation X∗=SVD⁡k(A−PπTSPσ)X^{*} = \operatorname{SVD}_k(A-P_{\pi}^{\mathsf{T}}SP_{\sigma}) by Eckart–Young (using

    ∥Pπ(A−X)PσT−S∥F2=∥(A−X)−PπTSPσ∥F2.\left\|P_{\pi}(A-X)P_{\sigma}^{\mathsf{T}} - S\right\|_{F}^{2} = \left\|(A-X)-P_{\pi}^{\mathsf{T}}SP_{\sigma}\right\|_{F}^{2}.

Useful identity. For any (π,σ,X)(\pi,\sigma,X) the optimal SS given the rest is S∗=ΠM(Pπ(A−X)PσT)S^{*} = \Pi_M(P_{\pi}(A-X)P_{\sigma}^{\mathsf{T}}), and substituting back yields equation (5) of Section 4, restated here for the proof:

min⁡S:S⊙(1−M)=0F(π,σ,S,X)=∥(I−ΠM)(Pπ(A−X)PσT)∥F2=dM(A−X;π,σ).\min_{S:S\odot(1-M)=0} F(\pi,\sigma,S,X) = \left\|(I-\Pi_M)(P_{\pi}(A-X)P_{\sigma}^{\mathsf{T}})\right\|_{F}^{2} = d_M(A-X;\pi,\sigma).

Proof of Proposition 2. Index iterations by tt and write the state at the start of iteration tt as (πt,σt,St,Xt)(\pi_t,\sigma_t,S_t,X_t). The body of the loop performs three updates.

(1) Pattern step. St+1=ΠM(Pπt(A−Xt)PσtT)S_{t+1} = \Pi_M(P_{\pi_t}(A-X_t)P_{\sigma_t}^{\mathsf{T}}) is the exact minimizer of FF over MM-supported SS, so F(πt,σt,St+1,Xt)≤F(πt,σt,St,Xt)F(\pi_t,\sigma_t,S_{t+1},X_t) \leq F(\pi_t,\sigma_t,S_t,X_t). (2) Low-rank step. Xt+1=SVD⁡k(A−Pπt⊤St+1Pσt)X_{t+1} = \operatorname{SVD}_k(A - P_{\pi_t}^{\top} S_{t+1}P_{\sigma_t}) is the global minimizer over rank-kk XX (Eckart–Young), so F(πt,σt,St+1,Xt+1)≤F(πt,σt,St+1,Xt)F(\pi_t,\sigma_t,S_{t+1},X_{t+1}) \le F(\pi_t,\sigma_t,S_{t+1},X_t).

(3) Safeguarded permutation update, followed by re-synchronization of SS. A candidate (π~,σ~)(\tilde{\pi},\tilde{\sigma}) is produced by ALTLAP on A−Xt+1A-X_{t+1} and accepted only if dM(A−Xt+1;π~,σ~)<dM(A−Xt+1;πt,σt)d_M(A-X_{t+1};\tilde{\pi},\tilde{\sigma}) < d_M(A-X_{t+1};\pi_t,\sigma_t). By (5) this compares the reduced objectives min⁡SF(π~,σ~,S,Xt+1)\min_S F(\tilde{\pi},\tilde{\sigma},S,X_{t+1}) and min⁡SF(πt,σt,S,Xt+1)\min_S F(\pi_t,\sigma_t,S,X_{t+1}). The algorithm then recomputes St+1′=ΠM(Pπt+1(A−Xt+1)Pσt+1⊤)S'_{t+1}=\Pi_M(P_{\pi_{t+1}}(A-X_{t+1})P_{\sigma_{t+1}}^{\top}) for the accepted pair, which is the minimizer in (5), so

F(πt+1,σt+1,St+1′,Xt+1)=min⁡SF(πt+1,σt+1,S,Xt+1)≤min⁡SF(πt,σt,S,Xt+1)≤F(πt,σt,St+1,Xt+1).F(\pi_{t+1},\sigma_{t+1},S'_{t+1},X_{t+1}) = \min_S F(\pi_{t+1},\sigma_{t+1},S,X_{t+1}) \le\min_S F(\pi_t,\sigma_t,S,X_{t+1}) \le F(\pi_t,\sigma_t,S_{t+1},X_{t+1}).

If the proposal is rejected, (πt+1,σt+1)=(πt,σt)(\pi_{t+1},\sigma_{t+1})=(\pi_t,\sigma_t) and the same chain holds with equality. The recomputation matters: without it the stored St+1S_{t+1} belongs to the old pair and F(πt+1,σt+1,St+1,Xt+1)F(\pi_{t+1},\sigma_{t+1},S_{t+1},X_{t+1}) can exceed the previous value even though the reduced objective decreased.

Combining the three inequalities, F(πt+1,σt+1,St+1′,Xt+1)≤F(πt,σt,St,Xt)F(\pi_{t+1},\sigma_{t+1},S'_{t+1},X_{t+1}) \le F(\pi_t,\sigma_t,S_t,X_t), where the left-hand side is exactly the state the loop carries into the next iteration and returns at termination. The sequence of FF-values is therefore non-increasing and bounded below by 0, hence convergent.

Unlike Proposition 1, this does not give finite termination: the permutations range over the finite set Sn×SnS_n \times S_n, but XX is continuous, and for fixed (π,σ)(\pi,\sigma) the alternating S/XS/X updates are alternating projections that converge in value without necessarily reaching a fixed point in finitely many steps. The algorithm stops when the decrease of FF falls below a tolerance ε\varepsilon or after a capped number of iterations.

Coordinates of XX. The low-rank factor XX is kept in the original (unpermuted) coordinates across iterations: when (π,σ)(\pi,\sigma) changes, XX does not need to be relabeled, whereas a copy stored in the permuted frame would become inconsistent with the new (π,σ)(\pi,\sigma) and break monotonicity.

Identifiability limits of the pattern score

The score s~M(A;π,σ)\tilde{s}_M(A;\pi,\sigma) and its minimised form s~M(A)\tilde{s}_M(A) are those of equation (6). Let A=Pπ∗⊤S0Pσ∗A=P_{\pi^*}^{\top}S_0P_{\sigma^*} with supp⁡(S0)=supp⁡(M∗)\operatorname{supp}(S_0)=\operatorname{supp}(M^*). Then dM∗(A)=0d_{M^*}(A)=0 (the planted pair places every entry of S0S_0 inside M∗M^*), so s~M∗(A)=0\tilde{s}_{M^*}(A)=0. For a candidate M′M', Pπ^APσ^⊤=PαS0Pβ⊤P_{\hat{\pi}}AP_{\hat{\sigma}}^{\top}=P_\alpha S_0P_\beta^{\top} with α=π^(π∗)−1\alpha=\hat{\pi}(\pi^*)^{-1}, β=σ^(σ∗)−1\beta=\hat{\sigma}(\sigma^*)^{-1}, so dM′(A;π^,σ^)=0d_{M'}(A;\hat{\pi},\hat{\sigma})=0 exactly when PαM∗Pβ⊤≤M′P_\alpha M^*P_\beta^{\top}\le M' entrywise. Hence every mask that contains a row/column-permuted copy of M∗M^* also scores exactly 0, and every mask that does not scores strictly more, for any strictly positive density penalty g(ρM)g(\rho_M) in place of (1−ρM)3/2(1-\rho_M)^{3/2}; a sufficient condition for the latter is ∣M′∣1<∣M∗∣1|M'|_1<|M^*|_1. Among the zero-score masks the score does not distinguish at all: 0 divided by any penalty is 0, so the planted mask and its containers tie, and preferring the sparsest of them is a separate convention, not a property of the score. The remark concerns exact support only: a zero residual cannot distinguish a mask from its containers, whatever the density factor.

Role of the exponent. Under noise the containers acquire positive scores and the density factor becomes active. The exponent 3/23/2 is a heuristic over-correction of coverage, not a derived constant: under independent uniform row and column permutations E[dM(A;π,σ)]=(1−ρM)∥A∥F2\mathbb{E}[d_M(A;\pi,\sigma)]=(1-\rho_M)\lVert A\rVert_F^2 (Appendix B.2), so the normalized null level is (1−ρM)−1/2(1-\rho_M)^{-1/2} and denser masks receive a larger null score, whereas the exponent 1 would equalize the null level across densities. Whether this is enough once the permutations are optimized is an empirical question, measured in Appendix E.5.1.

Special masks: permutation-invariant objectives and exact solutions

Table 5 summarizes the cases; the derivations follow.

Mask, settingObjective
full mask M=1M = 1identically 0
diagonal, σ=π\sigma= \piconstant ∑a≠bAab2\sum_{a \ne b} A_{ab}^{2} (permutation-invariant)
upper triangle, σ=π\sigma= \pi, symmetric AAconstant 12∑a≠bAab2\frac{1}{2}\sum_{a \ne b} A_{ab}^{2}
upper triangle, σ=π\sigma= \pi, asymmetric AAweight of the backward arcs (linear ordering)
diagonal or anti-diagonal, independent (π,σ)(\pi,\sigma)one LAP (Lemma 1)
arrowhead, σ=π\sigma= \piexact: choice of the hub, O(n2)O(n^{2})

Table 5. Masks for which the objective is permutation-invariant or exactly solvable.

Objectives that do not depend on the permutation. For M=1M = 1, dM(A;π,σ)=0d_M(A; \pi,\sigma) = 0 for every AA, π\pi, σ\sigma. Under a common permutation (σ=π)(\sigma= \pi) and for any AA, the diagonal mask gives dM(A;π)=∑i≠jAπ−1(i),π−1(j)2=∑a≠bAab2d_M(A; \pi) = \sum_{i \ne j} A_{\pi^{-1}(i),\pi^{-1}(j)}^{2} = \sum_{a \ne b} A_{ab}^{2}, since the pairs (π−1(i),π−1(j))(\pi^{-1}(i),\pi^{-1}(j)) with i≠ji \ne j range over all ordered pairs a≠ba \ne b. Under σ=π\sigma= \pi and for symmetric AA, the upper-triangular mask gives dM(A;π)=∑i>jAπ−1(i),π−1(j)2=12∑a≠bAab2d_M(A; \pi) = \sum_{i>j} A_{\pi^{-1}(i),\pi^{-1}(j)}^{2} = \frac{1}{2}\sum_{a \ne b} A_{ab}^{2}, because Aab2=Aba2A_{ab}^{2} = A_{ba}^{2} and the pairs i>ji > j cover every unordered pair once; for an asymmetric AA the same quantity is the weight of the backward arcs of the ordering, the linear-ordering objective. With independent permutations the diagonal and triangular masks are no longer trivial: the diagonal and the anti-diagonal are single LAPs (Lemma 1), and the triangle is not constant.

Exact solution for the arrowhead mask under σ=π\sigma= \pi. The diagonal is invariant under a common permutation, so the only choice is which index becomes the hub hh:

max⁡π∥ΠM(Aπ,π)∥F2=∑iAii2+max⁡h∑j≠h(Ahj2+Ajh2),\max_{\pi}\left\lVert\Pi_M(A^{\pi,\pi}) \right\rVert_F^2 = \sum_i A_{ii}^{2} + \max_h \sum_{j \ne h}\left(A_{hj}^{2} + A_{jh}^{2}\right),

computable in O(n2)O(n^{2}). The attention pipeline of Appendix § 13.§ 7 uses this value as the arrowhead score and as a check on the solver.

Algorithmic Details

Initialization and the exchange phase

Initialization. The default start for every mask is the Fiedler vector of the graph Laplacian L=D−∣A∣L = D - |A|, D=diag⁡(∣A∣1)D = \operatorname{diag}(|A|1): ordering vertices by their spectral embedding aligns with bandwidth-minimal orderings [6]. For the anti-diagonal band the Fiedler order of the folded path is unfolded from both ends and the two starts are kept as candidates; experiments that start a block fit from a spectral or Bethe-Hessian partition say so where they are reported (Appendix § 13.6.3). Random restarts mitigate the residual local-minimum issue.

Common permutation. For σ=π\sigma= \pi the two-sided iterate of a restart is rounded to one permutation, π^∈arg⁡min⁡π∈{π0,π∗,σ∗}dM(A;π)\hat{\pi} \in\arg\min_{\pi\in\{\pi_0,\pi^*,\sigma^*\}} d_M(A;\pi) with π0\pi_0 the start (rounding alone can lose ground, so the start is kept as a candidate), and the best π^\hat{\pi} over restarts is finished by the exchange descent. With CC the permuted weight matrix (C=B⊙BC = B \odot B for the pattern distance, C=BC = B for the linear score, B=Pπ^APπ^TB = P_{\hat{\pi}} A P_{\hat{\pi}}^{\mathsf{T}}) and D=1−MD = 1 - M, exchanging positions pp and qq changes the objective ∑ijDijCij\sum_{ij} D_{ij}C_{ij} by

Δpq=∑j≠p,q[(Dpj−Dqj)(Cqj−Cpj)+(Djp−Djq)(Cjq−Cjp)]+(Dpq−Dqp)(Cqp−Cpq)+(Dpp−Dqq)(Cqq−Cpp).\Delta_{pq} = \sum_{j \ne p,q} \left[(D_{pj} - D_{qj})(C_{qj} - C_{pj}) + (D_{jp} - D_{jq})(C_{jq} - C_{jp})\right] + (D_{pq} - D_{qp})(C_{qp} - C_{pq}) + (D_{pp} - D_{qq})(C_{qq} - C_{pp}).

valid for asymmetric AA as well; the matrix (Δpq)(\Delta_{pq}) is two products DCTDC^{\mathsf{T}} and DTCD^{\mathsf{T}}C plus entrywise terms, O(n3)O(n^{3}) per evaluation. A round evaluates Δ\Delta, then applies the improving exchanges in order of gain on disjoint positions, at most n/32n/32 per round, each re-checked exactly in O(n)O(n) under the current order before it is applied; rounds continue while an exchange improves. The output is never worse than the start and no exchange of two positions improves it (Proposition 1). With several starts the LAP phase runs from each start and the exchange phase from the best rounded permutation; on the sparse graphs of Appendix § 13.6.3, where the LAP steps stall early, the two phases are interleaved per start (three rounds). The exchange phase costs about 1 s at n=500n=500 and 7 s at n=1000n=1000 on one core (Appendix § 13.8).

Algorithm 3 ADAPTIVE PATLR

Require: $A$, rank $k$, vocabulary $\mathcal{V}=\{M_1,\ldots,M_K\}$, budget $N$, cooling $\gamma$, exploration floor $p_{\min}$, proposal steps $\ell$; write $f(j,\pi,\sigma):=\tilde{s}_{M_j}(A;\pi,\sigma)$
1: $\pi_0\leftarrow\operatorname{FIEDLERINIT}(A)$; for every $j$: $(\pi'_j,\sigma'_j)\leftarrow\operatorname{ALTLAP}(A,M_j,\ell;(\pi_0,\pi_0))$ {screening}
2: $j\leftarrow\arg\min_{j'}f(j',\pi_{j'}',\sigma_{j'}')$; $(\pi,\sigma)\leftarrow(\pi_j,\sigma_j)$; $T\leftarrow T_0>0$
3: $(j^*,\pi^*,\sigma^*)\leftarrow(j,\pi,\sigma)$ {incumbent: best visited state}
4: for $t=1,\ldots,N$ do
5: $(\pi,\sigma)\leftarrow\operatorname{ALTLAP}(A,M_j,1;(\pi,\sigma))$
6: if $f(j,\pi,\sigma)<f(j^*,\pi^*,\sigma^*)$ then $(j^*,\pi^*,\sigma^*)\leftarrow(j,\pi,\sigma)$ {update incumbent}
7: with prob. $p(T)=\max(p_{\min},T/T_0)$:
8: $j'\sim\operatorname{Uniform}[K]$; $(\pi',\sigma')\leftarrow\operatorname{ALTLAP}(A,M_{j'},\ell;(\pi,\sigma))$
9: $\Delta\leftarrow f(j',\pi',\sigma')-f(j,\pi,\sigma)$
10: if $\Delta<0$ or $\operatorname{rand}()<e^{-\Delta/T}$ then $(j,\pi,\sigma)\leftarrow(j',\pi',\sigma')$
11: if $f(j,\pi,\sigma)<f(j^*,\pi^*,\sigma^*)$ then $(j^*,\pi^*,\sigma^*)\leftarrow(j,\pi,\sigma)$ {update incumbent}
12: $T\leftarrow\gamma T$
13: end for
14: return $\operatorname{PATLR}(A,M_{j^*},k)$ started from $(\pi^*,\sigma^*)$ {Alg. 2; a fresh ALTLAP start on $M_{j^*}$ is also tried and the better kept}

Adaptive PatLR: joint pattern–permutation search

Settings not stated in § 4.1: the default vocabulary is blocks k∈{2,3,4,6}k\in\{2,3,4,6\}, bands w∈{1,2,4}w\in\{1,2,4\}, arrowhead and block+band (k=3k=3, w=2w=2), nine masks with fixed parameters (the attention study uses the nine-mask vocabulary of § 5.5); the exploration probability is p(T)=max⁡(pmin⁡,T/T0)p(T)=\max(p_{\min},T/T_0) with pmin⁡=0.15p_{\min}=0.15, T0T_0 is calibrated from the score spread at the Fiedler initialization (floored at a small positive constant), γ=0.95\gamma=0.95, and a proposal is evaluated with ℓ=3\ell=3 LAP steps from the current pair (a permutation pair optimized for block k=6k=6 is already a reasonable start for block k=4k=4 or block+band). The ALTLAP calls inside the search are the LAP phase of Algorithm 1, without the exchange phase: the search compares many masks under a small budget, and finishing every proposal at a local minimum would turn each cheap evaluation into a full fit. The exchange phase, a fresh three-restart fit and PATLR are applied to the selected mask only. The incumbent updates make the output the best visited state; whether the finite search selects the planted mask is the empirical question of § 5.4 and Appendix § 13.§ 5.1.

Out-of-vocabulary structure. The selector never rejects: it returns the best-scoring visited state, so a structure outside the vocabulary (unequal or nested blocks, a hybrid shape) is approximated by the closest available mask; in our planted experiments the nearest single-family mask is selected rather than a noise-level answer. Two practical remedies follow. A best score close to the random-permutation level indicates that no mask in the vocabulary explains the matrix. That level is not a universal constant: for independent random permutations and no optimization, E[s~M]=(1−ρM)/(1−ρM)3/2=(1−ρM)−1/2\mathbb{E}[\tilde{s}_M]=(1-\rho_M)/(1-\rho_M)^{3/2}=(1-\rho_M)^{-1/2}, under σ=π\sigma=\pi it depends on the split of the mass between the diagonal and the off-diagonal (Appendix B), and optimizing over permutations lowers it further, so a threshold on it is a heuristic calibrated per mask rather than a derived rejection rule; A=0A=0 and ρM=1\rho_M=1 are excluded by convention. The vocabulary is extended by adding a mask, at a cost linear in ∣V∣|\mathcal{V}|. Estimating mask parameters from the data instead of enumerating fixed masks (e.g. block boundaries by change-point segmentation of the reordered matrix, alternated with the permutation step), and calibrating each mask’s score against its own random-permutation null rather than a density correction, are left for future work.

Experimental Details and Additional Results

For the experiments summarized in Section 5 this appendix gives the generators, the information available to each method, the baseline settings, the full grids and the paired intervals; it also reports the experiments that appear only here (the compute-budget ablation, the circular and nested ordering geometries, block-size estimation, the long-context control and wall-clock scaling), each with the question it answers. Unless stated otherwise, comparisons are paired on identical instances over 20 seeds with 95% bootstrap intervals of the paired difference.

Ablation: Initialization, Restarts, and Compute Budget

Figure 7 runs the solvers of Table 1 on the same instances with increasing budgets and records the running best error reduction against cumulative wall-clock: Alternating LAP from the Fiedler order plus random restarts (the protocol of Table 1, five restarts there) and from random restarts only, up to 20 restarts, and FAQ with 1 to 10 starts. Three things are visible. The first run accounts for almost all of the gain over the Fiedler order alone; additional restarts add at most 0.04 over 20 restarts, and random starts reach the values of the Fiedler start on all but one panel (Gauss w=5w=5, n=200n=200, where the Fiedler start stays 0.05 ahead), so on these planted instances the descent, not the spectral start, does the work. On the sparse {0,1}\{0,1\} graphs the restart budget adds about 0.01: the LAP steps stall on the many ties induced by sparse binary inputs (the same stalling appears without any noise on the w=1w=1 band, the Hamiltonian-path case of Appendix § 10.5) and the exchange phase supplies the remaining descent (next paragraph). FAQ with one start is weak there and owes its final value to its randomized starts; on the Gaussian inputs Alternating LAP is above FAQ at every budget.

Figure 7. Error reduction against cumulative wall-clock on the instances of Table 1 (20 seeds, 95% bootstrap intervals; single CPU core). Markers: AltLAP after 1, 2, 3, 5, 10, 20 restarts (Fiedler start plus random, or random only), FAQ after 1, 3, 5, 10 starts; the open circle is the Fiedler order without any LAP step.

Without the exchange phase. Running Algorithm 1 with the exchange phase disabled, on the instances and budget of Table 1, separates the two phases. The LAP phase alone reaches ER 0.61/0.50/0.41 (Gauss w=2w=2), 0.78/0.65/0.55 (Gauss w=5w=5), 0.15/0.06/0.01 (sparse w=2w=2) and 0.63/0.48/0.29 (sparse w=5w=5) at n=100/200/500n=100/200/500; the exchange phase raises these to 0.69/0.61/0.52, 0.87/0.75/0.61, 0.45/0.30/0.15 and 0.69/0.53/0.34, the values of Table 1. On the Gaussian inputs it adds 0.06–0.11 and on the sparse graphs it supplies most of the reduction, since the LAP steps stall on the ties induced by binary inputs, the same stalling as on the sparse SBM graphs of § 5.2. At n=500n=500 the phase takes about a third of the run time on the Gaussian instances and about a tenth on the sparse graphs (runtimes in Appendix § 13.§ 2).

Banded Baselines from the Seriation, QAP, and Bandwidth Literatures

Table 6 extends Table 1 with all methods and both of our metrics (ER / BE), and Table 7 scores the same orderings by the bandwidth family’s own criteria. Methods: RCM [16] and Gibbs–Poole–Stockmeyer (GPS) [25] on the {0,1}\{0,1\} support (the graph itself in the sparse regime; the KNN-20 sparsification in the Gaussian regime); F+greedy (Fiedler order plus greedy adjacent swaps on 2-SUM); the plain spectral 2-SUM order of Atkins et al. [ [4] (the Fiedler ordering itself); convex seriation [21] (Frank–Wolfe over the permutahedron with the concave vertex-pulling term, penalty weight and start chosen by the 2-SUM value); QAP-FAQ with three starts; FAQ followed by AltLAP (keeping the better of the two); AltLAP with one restart (equal-budget variant) and with five. Our objective and FAQ’s are the same QAP, but the two heuristics solve different inner problems: FAQ relaxes the single-permutation problem, whereas AltLAP descends on the two-sided objective, rounds to one permutation and finishes with the exchange descent; the rounding can lose ground, which is why the start is kept as a candidate. The two are closely related: at a permutation PπP_{\pi} the FAQ gradient ∇Ptr⁡(MTPWPT)=2MPπW\nabla_{P}\operatorname{tr}(M^{\mathsf{T}}PW P^{\mathsf{T}})=2MP_{\pi}W equals −2Q-2Q of Lemma 1 up to a constant per column, so the first FAQ direction-finding step from a permutation is the LAP step of Algorithm 1; FAQ then takes a fractional step inside the Birkhoff polytope, while AltLAP moves to the vertex and alternates sides. Warm-starting AltLAP from the FAQ order (the FAQ+AltLAP column of Table 6) adds 0.02–0.12 on the Gaussian inputs, where the LAP steps rarely move the FAQ order and the gain is the exchange phase, and at most 0.01 on the sparse graphs.

RegimennRCMGPSF+greedySpectralConvexFAQFAQ+AltLAPAltLAP-r1AltLAP
Gauss w=2w=2300.03/0.390.05/0.410.84/0.900.76/0.850.85/0.910.60/0.750.68/0.800.87/0.920.87/0.92
1000.05/0.340.05/0.340.37/0.560.32/0.520.36/0.560.51/0.660.62/0.730.69/0.780.69/0.78
2000.03/0.300.04/0.310.14/0.380.15/0.390.14/0.380.46/0.610.58/0.700.61/0.720.61/0.72
5000.03/0.270.03/0.270.03/0.270.04/0.280.04/0.280.40/0.550.52/0.640.52/0.640.52/0.64
Gauss w=5w=5300.07/0.540.09/0.550.98/0.990.97/0.980.98/0.990.84/0.920.86/0.930.98/0.990.98/0.99
1000.09/0.410.09/0.410.72/0.820.61/0.750.73/0.820.66/0.780.72/0.820.87/0.910.87/0.91
2000.08/0.350.08/0.360.33/0.530.34/0.540.34/0.540.61/0.730.66/0.760.76/0.830.75/0.82
5000.06/0.300.05/0.290.08/0.320.10/0.330.09/0.320.57/0.680.60/0.700.60/0.700.61/0.71
Sparse w=2w=2300.23/0.330.24/0.330.45/0.510.39/0.470.46/0.520.73/0.760.74/0.770.67/0.710.67/0.71
1000.06/0.100.06/0.100.09/0.130.09/0.130.09/0.130.49/0.510.50/0.520.44/0.460.45/0.47
2000.02/0.050.02/0.040.03/0.050.03/0.050.03/0.050.36/0.370.36/0.370.30/0.320.30/0.31
5000.00/0.010.00/0.010.00/0.010.00/0.010.01/0.010.20/0.200.20/0.200.15/0.160.15/0.16
Sparse w=5w=5300.41/0.590.04/0.340.78/0.850.76/0.830.78/0.850.88/0.920.89/0.930.91/0.940.91/0.94
1000.16/0.240.15/0.230.29/0.360.29/0.360.30/0.370.66/0.690.66/0.690.68/0.710.69/0.72
2000.09/0.140.08/0.130.10/0.140.12/0.160.10/0.150.52/0.540.52/0.550.53/0.550.53/0.56
5000.03/0.050.02/0.040.02/0.040.02/0.040.02/0.040.33/0.350.34/0.350.33/0.350.34/0.35

Table 6. Banded recovery, ER / BE (higher = better), 20 seeds. Bold marks the best ER per row (ties within 0.005).

RegimennidentityRCMGPSF+greedyConvexFAQAltLAPRCMGPSAltLAP
Gauss w=2w=23029262628292929416417422
10097828396959796425145154466
200196162159192192197195168091771217592
500494405399489490496492104377109910110834
Gauss w=5w=53029262628292929416417423
10097828396959797425145154476
200196162159192192196194168091771217598
500494405399489490493494104377109910110756
Sparse w=2w=2302610810102516135142120
10094474554529287229826342363
200192117111139133190192114421258913083
50049236535845544149149193432101738103868
Sparse w=5w=53029292429292929430407428
10096585570719391282331652483
200195131128164159192189131001489413319
50049339239345646049349098342106402103963

Table 7. The same orderings scored by the bandwidth family: bandwidth (lower = better; identity order and six methods) and profile for RCM, GPS and AltLAP, means over 20 seeds on the shared {0,1}\{0,1\} support.

Two metric families, one support. Bandwidth max⁡{∣i−j∣:Sij=1}\max\{|i-j|:S_{ij}=1\} and profile ∑i(i−min⁡{j≤i:Sij=1})\sum_i(i-\min\{j\le i:S_{ij}=1\}) need a discrete support, so every ordering is scored on the same {0,1}\{0,1\} support that RCM and GPS are given. GPS is the better bandwidth reducer, as expected, and neither bandwidth method reduces off-band mass. Conversely our methods barely reduce bandwidth: a few small entries far from the diagonal cost almost no mass but fix max⁡∣i−j∣\max|i-j|. On noisy inputs the classical criterion saturates (at n=500n=500 in the Gaussian regime every ordering, including the identity, has a bandwidth close to the maximum), because the signal falls below the noise at ∣i−j∣≈7|i-j|\approx7 and the support beyond is noise, so the criterion is set by the farthest noise entries whose palet distance measures the mass concentration.

Runtimes at n=500n=500 (one EPYC core): RCM, GPS and the spectral order 0.01–0.02 s; convex seriation 0.45–0.55 s; F+greedy 0.7 s; FAQ (three starts) 2.0–2.8 s; AltLAP with one restart 0.8–1.2 s and with five 1.7–4.1 s (the exchange phase runs once, from the best restart).

PatLR Decomposition Visualizations

Figure 8 follows the decomposition on one synthetic instance of the experiment of Figure 4, where the planted parts are known and can be compared with the recovered ones, and, without added noise, on the two real networks of § 5.3 and on three feature-correlation matrices from the UCI repository [Wine, Breast Cancer Wisconsin (Diagnostic) and Optical Recognition of Handwritten Digits; Aeberhard and Forina, [2], Wolberg et al., [58], Alpaydin and Kaynak, [3], each with the mask of the default vocabulary that fits it best at rank 1. The first column shows each matrix in its native order (node numbering of the graph, feature order of the dataset), the second the random order given to the solver. The row norm of the low-rank part follows the row mass on Les Misérables, Wine and Breast Cancer; on the karate club the rank-1 part concentrates on the two highest-degree nodes, the two faction leaders.

Figure 8. PatLR step by step. Top row: a synthetic instance with known truth (banded w=3w=3 pattern plus a rank-3 component of equal energy, n=100n=100, scrambled, SNR 1): the planted S0S_0 and L0L_0, the noisy input, the input in the found order, the recovered SS and UVTUV^{\mathsf{T}} and their sum with its DQ. Remaining rows: real matrices without added noise, karate club (weighted adjacency, block(18,16)(18, 16) from the two factions, rank 1); Les Misérables (co-occurrence weights scaled to [0,1][0, 1], block(19,19,19,20)(19, 19, 19, 20) template, rank 3); and the signed feature-correlation matrices of Wine (band w=4w=4), Breast Cancer (block(15,15)(15, 15)) and Digits (pixel correlations, block(32,32)(32, 32)), rank 1; left to right: the input in its native order; the input in the random order given to the solver; the input in the order found by PatLR, mask outlined; the pattern part SS; the low-rank part UVTUV^{\mathsf{T}}; their sum with its explained variance; the row norm of UVTUV^{\mathsf{T}} against the row mass ∑j∣Aij∣\sum_j |A_{ij}| (weighted degree for the graphs, total absolute correlation for the features). Graphs on a white-to-blue scale, signed matrices and UVTUV^{\mathsf{T}} on a diverging scale (blue positive); rr is the correlation in the last column.

PatLR: Full Denoising Grid, Ablations and Capacity Control

Setup of Figure 4, remaining details. The pattern part is S0=2M⊙R+0.15(1−M)⊙RS_0 = 2M \mathbin{\odot} R + 0.15(1-M) \mathbin{\odot} R for one symmetric Gaussian matrix RR, with the diagonal set to ∣Rii∣+0.3\lvert R_{ii}\rvert+ 0.3 (the generator of the capacity control below); S0S_0 is symmetric for the six symmetric masks, while for the upper-triangular mask it is asymmetric (upper triangle at scale 2, lower at 0.15), so under the common permutation its objective is the linear-ordering problem of Table 2, not the constant it would be for a symmetric matrix. The low-rank part is L0=UU⊤L_0 = UU^\top with U∈Rn×3U \in\mathbb{R}^{n \times3} Gaussian, scaled to a fraction ff of the clean energy (f=0.5f=0.5 in Figure 4); the noise is scaled per instance to SNR⁡=∥A∥F2/∥E∥F2\operatorname{SNR} = \lVert A\rVert_F^2/\lVert E\rVert_F^2, so the noisy input has DQ 1−1/SNR⁡1 - 1/\operatorname{SNR}. RPCA is principal component pursuit with its low-rank part as the estimate; SVD-dof is the SVD at the rank with the parameter count of PatLR (rule below); PatLR runs from the Fiedler order and from its unfolding (one random restart each) and keeps the lower objective; PatLR-rnd uses a random mask of the same density; the oracle column fixes the permutation to the planted one and alternates SS and XX only.

Table 8 gives the full grid. Three regularities hold across it. An estimate that copies the in-mask entries, i.e. C^=M⊙(C+E)+(1−M)⊙X\widehat{C}=M\mathbin{\odot}(C+E)+(1-M)\mathbin{\odot}X in the coordinates of the mask (pattern alone with X=0X=0, PatLR and the oracle with the rank-3 XX), has error ∥M⊙E∥F2+∥(1−M)⊙(X−C)∥F2\lVert M\mathbin{\odot}E\rVert_F^2+\lVert(1-M)\mathbin{\odot}(X-C)\rVert_F^2 exactly, the two terms having disjoint supports, so its DQ is at most 1−∥M⊙E∥F2/∥C∥F21-\lVert M\mathbin{\odot}E\rVert_F^2/\lVert C\rVert_F^2. For a mask placed independently of the noise the in-mask noise energy is ρM∥E∥F2\rho_M\lVert E\rVert_F^2 in expectation, which gives the value 1−ρM/SNR⁡1-\rho_M/\operatorname{SNR}; a permutation chosen from the data tends to place more noise inside the mask, not less. The off-mask term is the clean energy outside the mask for the pattern-only estimate (X=0X=0) and ∥(1−M)⊙(X−C)∥F2\lVert(1-M)\mathbin{\odot}(X-C)\rVert_F^2 for PatLR, which is smaller when CC has low-rank structure outside the mask and larger when XX fits noise. On the pattern-only families the off-mask clean values are i.i.d. and carry no low-rank structure, so on the five families whose order the solver recovers the rank-3 oracle lands below the pattern-only value by 0.01 at SNR 4, 0.05 at SNR 1 and 0.07–0.11 at SNR 0.5 (on the band and the anti-diagonal the oracle’s planted order puts it above the pattern-only estimate, whose order is the solver’s). The gap between PatLR and the oracle is concentrated on the banded and anti-diagonal families, i.e. in the permutation search on sparse masks, and grows as the SNR falls. The random-mask control PatLR-rnd lies 0.2–0.5 below PatLR on the planted pattern and 0.1–0.4 below it with the rank-3 component at SNR 1; it stays above the SVD level where random positions can absorb signal mass under a free permutation (the band, anti-diagonal, block and block+band families on the planted pattern, the band and anti-diagonal with the rank-3 component) and within 0.05 of it or below elsewhere. With 80% of the clean energy in the low-rank part, SVD-best is the better estimate on the dense masks, and with 20% PatLR is the best estimate on every family: the mask pays for the in-mask noise it copies only while the pattern carries enough of the signal.

PatternρM\rho_MinputSVD-dofSVD-bestRPCApattern onlyPatLRPatLR-rndoracle
planted pattern, SNR 4.0
Banded0.0350.750.120.750.100.760.760.550.88
Block0.2500.750.340.750.210.920.910.540.91
Arrowhead0.0150.750.340.750.190.780.780.360.78
Checkerboard0.5000.750.530.750.340.870.860.600.86
Block+band0.3270.750.410.750.250.910.890.550.89
Anti-diagonal0.1020.750.210.750.120.860.860.550.91
Triangular0.5020.750.660.750.410.870.860.530.86
planted pattern, SNR 1.0
Banded0.0350.000.030.07-0.050.690.640.440.81
Block0.250-0.000.010.020.110.730.680.200.68
Arrowhead0.0150.000.270.280.030.770.730.270.72
Checkerboard0.500-0.00-0.000.010.210.490.440.070.44
Block+band0.327-0.000.010.010.150.660.600.140.60
Anti-diagonal0.1020.000.030.040.010.720.670.370.80
Triangular0.502-0.000.110.120.250.480.440.010.44
planted pattern, SNR 0.5
Banded0.035-1.00-0.10-0.02-0.280.590.490.280.71
Block0.250-1.00-0.42-0.02-0.110.480.37-0.280.37
Arrowhead0.015-1.000.190.25-0.220.750.670.140.65
Checkerboard0.500-1.00-0.72-0.02-0.04-0.01-0.12-0.63-0.12
Block+band0.327-1.00-0.53-0.02-0.080.320.21-0.400.22
Anti-diagonal0.102-1.00-0.20-0.01-0.210.500.360.080.64
Triangular0.502-1.00-0.63-0.01-0.01-0.04-0.13-0.68-0.11
pattern + rank-3 component (equal energy), SNR 4.0
Banded0.0350.750.550.750.540.420.860.760.94
Block0.2500.750.620.750.600.570.920.710.92
Arrowhead0.0150.750.670.760.580.440.890.580.89
Checkerboard0.5000.750.680.750.650.630.860.710.85
Block+band0.3270.750.640.750.620.590.900.700.90
Anti-diagonal0.1020.750.570.750.550.430.880.750.94
Triangular0.5020.750.740.760.670.630.860.670.86
pattern + rank-3 component (equal energy), SNR 1.0
Banded0.0350.000.470.510.350.340.770.660.88
Block0.250-0.000.300.490.430.380.710.370.71
Arrowhead0.0150.000.630.630.370.430.850.500.85
Checkerboard0.5000.000.150.490.460.240.460.190.45
Block+band0.327-0.000.240.490.440.330.630.310.63
Anti-diagonal0.102-0.000.410.490.380.260.690.560.84
Triangular0.5020.000.190.490.470.240.450.160.46
pattern + rank-3 component (equal energy), SNR 0.5
Banded0.035-1.000.370.470.080.220.610.500.81
Block0.250-1.00-0.120.460.15-0.090.36-0.080.42
Arrowhead0.015-1.000.560.560.090.410.800.380.80
Checkerboard0.500-1.00-0.570.460.17-0.39-0.22-0.50-0.08
Block+band0.327-1.00-0.280.460.16-0.190.18-0.220.27
Anti-diagonal0.102-1.000.190.450.11-0.040.350.270.71
Triangular0.502-1.00-0.540.460.18-0.28-0.12-0.52-0.08
pattern + rank-3 component carrying 20% of the clean energy, SNR 1 (10 seeds)
Banded0.0350.000.210.220.110.550.710.530.85
Block0.250-0.000.130.200.240.590.700.270.70
Arrowhead0.0150.000.420.420.160.640.700.290.79
Checkerboard0.500-0.000.060.200.310.400.460.110.45
Block+band0.3270.000.100.200.260.530.620.210.63
Anti-diagonal0.1020.000.180.200.160.550.670.450.83
Triangular0.502-0.000.140.210.330.380.450.060.46
pattern + rank-3 component carrying 80% of the clean energy, SNR 1 (10 seeds)
Banded0.0350.000.730.780.570.140.810.770.91
Block0.250-0.000.470.780.600.160.570.480.72
Arrowhead0.0150.000.810.810.570.210.910.730.91
Checkerboard0.500-0.000.230.780.600.120.350.270.43
Block+band0.327-0.000.380.780.600.150.490.410.64
Anti-diagonal0.102-0.000.630.780.580.070.670.660.86
Triangular0.502-0.000.240.780.600.100.430.260.46

Table 8. Denoising quality on the seven families, all settings of the experiment of Figure 4 (n=200n=200; 20 seeds unless stated; best of SVD-dof, SVD-best, RPCA, pattern only, PatLR and PatLR-rnd per row in bold; “oracle” is PatLR at the planted permutation).

Ablation of the permutation. Table 9 fixes the permutation instead of searching it, on the planted-pattern matrices at σ=0.3\sigma=0.3 (scrambled). With the permutation fixed to the input order the effect differs between families: block, checkerboard, block+band, anti-diagonal and triangular fall below the SVD level, whereas the masks that contain the diagonal keep what a symmetric scrambling leaves in place; the band stays above SVD on the diagonal entries alone, and the arrowhead reaches the searched value because its hub row and column form a rank-2 matrix that the low-rank term absorbs at any order. With the permutation fixed to the planted order PatLR is high on every family. The joint solver attains the planted-order value on five families and stays below it on banded and anti-diagonal, the two sparse masks whose order is hardest to recover.

PatternSVD-dofpattern onlyPatLR, input orderPatLRPatLR, planted order
Banded0.100.730.290.730.86
Block0.410.960.310.960.96
Arrowhead0.280.480.740.740.73
Checkerboard0.680.970.540.970.97
Block+band0.500.960.380.970.96
Anti-diagonal0.210.810.140.830.92
Triangular0.790.970.550.970.97

Table 9. PatLR with the permutation searched, fixed to the input order, or fixed to the planted order (DQ, n=200n=200, σ=0.3\sigma=0.3, scrambled inputs, 20 seeds).

Capacity control at a matched parameter count. Table 10 compares the models at an equal nominal parameter count on the planted-pattern matrices at σ=0.3\sigma=0.3 in their planted order (the scrambled version changes no entry by more than 0.01). PatLR with mask MM and residual rank rr has df=∣M∣+r(2n−r)\mathrm{df}=|M|+r(2n-r) free parameters (the in-mask entries plus a rank-rr factorization). SVD-dof receives the rank r′=round⁡(n−max⁡(n2−df,0))r'=\operatorname{round}\left(n-\sqrt{\max(n^2-\mathrm{df},0)}\right) clipped to [1,n][1,n], which has the same count; SVD-3 is the fixed-rank estimate. The blockmodel baseline is spectral co-clustering [20]: kk-means on the leading singular vectors of rows and of columns, then block means. “BM” chooses k∈{2,3,4,5,6,8}k\in\{2,3,4,5,6,8\} by the best DQ (an oracle choice, generous to the baseline); “BM-dof” uses k=round⁡(df)k=\operatorname{round}(\sqrt{\mathrm{df}}), the same nominal budget as PatLR. PatLR-rnd replaces the planted mask by a random mask of the same density, redrawn per seed, with an otherwise identical pipeline. At σ=0.3\sigma=0.3 the noise carries up to half of the energy of these matrices (column “input”), so the table measures which model class retains a full-rank in-mask structure at a given parameter count rather than noise removal; the i.i.d. in-mask values are a model mismatch for the blockmodel, which is why it sits at the SVD-dof level at matched budget. The hierarchical pattern of Table 2 is omitted: as a binary mask a two-level hierarchy coincides with its coarsest level.

PatternρM\rho_Mr′r'k′k'inputSVD-3SVD-dofRPCABMBM-dofPatLRPatLR-rnd
Banded0.0357510.570.050.100.070.040.270.730.52
Block0.250301060.920.060.410.180.040.420.960.61
Arrowhead0.0155420.130.280.280.050.270.430.740.29
Checkerboard0.500631460.960.060.680.310.040.620.970.73
Block+band0.327401200.930.060.510.220.040.420.970.64
Anti-diagonal0.10214730.790.060.210.130.040.260.830.57
Triangular0.502631460.960.070.790.400.020.810.970.67

Table 10. Capacity control, DQ at n=200n=200, σ=0.3\sigma=0.3, 20 seeds: ρM\rho_M is the mask density, r′r' the matched SVD rank, k′k' the matched number of co-clusters, “input” the DQ of the noisy matrix itself.

Adaptive PatLR: Additional Analysis

Selection, Identification and Cost on Planted Matrices

Setup. Each of the nine masks of the default vocabulary is planted at n=200n=200 with the generator of Figure 4 (i.i.d. Gaussian values of scale 2 on the mask and 0.15 off it), either alone (pattern only) or plus a rank-3 PSD component of equal energy (pattern + rank-3); the matrix is scrambled by a random permutation and symmetric Gaussian noise is added at SNR 4 and SNR 1 (10 and 20 seeds; 540 instances). The selector’s vocabulary has 12 masks: the nine planted families and three gallery masks (parity checkerboard, anti-diagonal band of width 10, upper triangular). The parity checkerboard is a row/column-permuted copy of the two-block mask (reorder even and odd indices), so the density-normalized score cannot and should not separate the two; it is counted with block k=2k=2 throughout. Methods: Oracle PatLR (rank 3, planted mask; 12 iterations, 3 restarts); Adaptive PatLR (Algorithm 3, N=80N=80, ℓ=3\ell=3, rank 3); brute force (every mask fitted by the LAP phase of Alternating LAP, 15 iterations from 3 restarts, i.e. the search’s LAP-only evaluation at a full budget per mask; the mask with the lowest density-normalized score kept, then PatLR with it); SVD at the rank with the highest DQ. DQ is measured against the clean matrix in its planted order. Times are single-core seconds on an Apple M3 (six instances at SNR 1).

Results (Table 11, Figure 5). Across the 540 instances the ratio DQadapt/DQoracle\mathrm{DQ}_{\mathrm{adapt}}/\mathrm{DQ}_{\mathrm{oracle}} has median 1.00, 5th percentile 0.92 and minimum 0.76 (a band w=4w=4 instance at SNR 1, planted alone, for which block+band was selected); it exceeds 1 in a third of the instances. SVD at its best rank averages DQ 0.29 against the oracle’s 0.68 at SNR 1 and 0.75 (the noisy input itself) against 0.87 at SNR 4. Brute force has median ratio 1.00 and minimum 0.74; its DQ is within 0.01 of the search’s in every (family, generator, SNR) cell, and its selection frequencies agree with the search’s within 10% in 29 of the 36 cells, the larger differences being between masks of equal DQ (block k=3k=3 against block+band; on block k=2k=2 with the rank-3 component at SNR 1, block k=6k=6 against band w=4w=4). It takes 3.7 s against 2.9 s for the search and 2.5 s for the oracle; its cost grows with ∣V∣|V|, whereas after the initial vocabulary screening the search uses a fixed budget of NN iterations rather than fully fitting every mask. Fitting every mask with the full solver (exchange phase included) before comparing scores is not better: the wide band then attains the lowest normalized score more often, and on block k=3k=3, arrowhead and block+band with the rank-3 component at SNR 1 the selected mask has a lower DQ (0.53, 0.79, 0.53 against 0.61, 0.85, 0.62), the exact minimizer of the heuristic score not being the best-reconstructing mask (Appendix § 11.§ 2). On six real matrices (the feature correlations of Iris, Wine, Breast Cancer and Digits, the karate club and Les Misérables), where no planted mask exists, the adaptively selected mask matches the best fixed mask of the vocabulary in explained variance within 0.025 in 24 of 29 (matrix, rank) cells, the exceptions being a sparser choice at rank ≤3\le3 on Digits and rank ≤2\le2 on Les Misérables. Identification (Figure 5a,Figure 5b and the last columns of Table 11) splits by the geometry of the vocabulary. Arrowhead, block+band and the block templates k=4k=4 and k=6k=6 are identified in nearly every instance, although block k=4k=4 fits inside block k=2k=2 and block k=6k=6 inside block k=3k=3: under noise the denser container’s smaller residual does not pay back its density penalty. The few misses go to a neighbouring block size and all occur at SNR 1. Block k=2k=2 is identified whenever the pattern is planted alone and at SNR 4 with the rank-3 component; at SNR 1 with the rank-3 component the selector prefers a sparser mask (block k=6k=6 or band w=4w=4) at the oracle’s DQ, the low-rank term absorbing the two dense blocks so that the density penalty of the half-dense mask is no longer paid back. The nested families go to a larger mask in most instances (narrow bands to the wide band; block k=3k=3 to block+band, whose blocks cover those of block k=3k=3 up to two rows), within 0.04 of the oracle’s DQ. The remaining non-exact choices are the thin bands without a low-rank part: their order is recovered only partially at this budget, the planted mask then copies a misaligned band, and the selector prefers wider masks (block k=6k=6, block+band), which tolerate the misalignment; at SNR 4 they reach a higher DQ than the planted mask and at SNR 1 a DQ 0.02–0.07 below it. With the rank-3 component the wide band is identified in most instances.

planted maskSNR 4SNR 1
OracleAdaptiveSVDexact/cont.OracleAdaptiveSVDexact/cont.
pattern only
block k=2k=20.860.860.751000.440.460.01100
block k=3k=30.890.890.7540 / 600.600.600.0145 / 55
block k=4k=40.910.910.751000.680.680.02100
block k=6k=60.920.920.751000.750.740.0395 / 5
band w=1w=10.770.780.750 / 400.690.670.125 / 95
band w=2w=20.770.790.750 / 600.670.630.0910 / 55
band w=4w=40.760.790.7500.630.560.0510
arrowhead0.780.780.751000.730.720.28100
block+band0.890.890.751000.600.600.01100
pattern + rank-3 component
block k=2k=20.860.800.751000.460.470.490
block k=3k=30.900.900.7510 / 900.630.610.490 / 70
block k=4k=40.920.920.751000.710.700.4990
block k=6k=60.940.940.751000.790.790.50100
band w=1w=10.880.880.750 / 1000.810.770.5110 / 90
band w=2w=20.870.880.7510 / 900.790.780.5140 / 55
band w=4w=40.860.850.75600.750.740.5090
arrowhead0.890.890.761000.850.850.63100
block+band0.900.900.751000.630.620.4970

Table 11. Adaptive pattern selection on planted matrices (n=200n=200). DQ of Oracle PatLR (planted mask), Adaptive PatLR and SVD at its best rank, and the share of instances (%) in which Adaptive PatLR selects the planted mask (second number where present: a mask containing the planted one, a wider band for the bands and block k=3k=3 for block k=6k=6, or block+band for block k=3k=3, whose blocks it covers up to two rows). At SNR 4 the noisy input itself has DQ =1−1/SNR=0.75=1-1/\mathrm{SNR}=0.75. 10 seeds at SNR 4, 20 at SNR 1.

Sensitivity to the Residual Rank

Figure 9 shows DQ against the residual rank rr on the setup of Figure 4 (n=200n=200, the planted pattern alone and with a rank-3 component of equal energy, SNR 4 and 1, 20 seeds) for PatLR with the planted mask, SVD at the same rank and Adaptive PatLR. With a rank-3 component in the data, DQ peaks at the true rank for PatLR and declines slowly beyond it, while SVD needs a higher rank to reach a lower plateau. With the pattern alone every unit of rank costs DQ at SNR 1 (the low-rank term fits noise) and little at SNR 4. Adaptive PatLR follows PatLR within 0.05 at every rank; the largest differences are on the band planted alone, where it selects a wider mask (Appendix § 13.§ 5.1) and lies 0.04 above PatLR at SNR 4 and 0.04–0.05 below it at SNR 1. The rank is a budget to be chosen, not a free improvement.

Figure 9. Denoising quality against the residual rank rr on the setup of Figure 4 (20 seeds, 95% intervals shaded): PatLR with the planted mask and SVD at the same rank, for the planted pattern alone (solid) and with a rank-3 component (dashed); markers are Adaptive PatLR. The vertical line marks the planted rank 3.

Ordering and Block-Structure Benchmarks: Full Results

This appendix gives the full grids behind Figure 3 and § 5.1–§ 5.2, and two ordering geometries reported only here, circular seriation and nestedness (Appendix § 13.6.2). Counting the cells of each grid by the sign of the paired difference to the named reference (positive / interval containing zero / negative): latent ordering 18/2/4 against spectral and 9/10/5 against convex seriation (24 cells); consecutive ones 4/0/0; circular seriation 2/2/0; sparse SBM 8/1/3 against the Bethe Hessian (12 cells, the negative ones at λ=1.3\lambda=1.3); weighted partition 4/1/0 against spectral clustering; band-in-block 16/0/0 for the refining pass against the pipeline. In the tables, “seeds +/−” counts the seeds on which the paired difference is positive / negative.

Latent-order recovery

Setup. Bij=exp⁡(−(i−j)2/2ℓ2)B_{ij}=\exp(-(i-j)^2/2\ell^2) is a Robinson matrix with correlation length ℓ\ell; it is scrambled by a uniformly random permutation pp and symmetric Gaussian noise of standard deviation σ\sigma is added. The target is the banded mask of width w=ℓw=\ell. The metric is ∣τ∣|\tau|, the absolute Kendall correlation between the recovered and the planted positions (absolute because reversing an order preserves banded structure). Baselines: spectral seriation (Fiedler order of the Laplacian of ∣A∣|A| [[4]]); convex seriation [[21]], implemented as Frank–Wolfe on the 2-SUM objective over the permutahedron with the concave vertex-pulling term −μ var⁡(y)-\mu\,\operatorname{var}(y), the penalty weight μ∈{0.1,0.3,0.5,1,2}\mu\in\{0.1, 0.3, 0.5, 1, 2\} and the start (spectral or two random) selected by the 2-SUM value itself, never by τ\tau (on noiseless inputs it recovers the planted order exactly); QAP-FAQ with three starts; and a single run of Alternating LAP initialized from the spectral order (AltLAP-r1; five restarts change no conclusion). Grid: ℓ∈{6,12,25}\ell\in\{6,12,25\}, n∈{100,300}n\in\{100,300\}, σ∈{0.05,0.1,0.2,0.3}\sigma\in\{0.05,0.1,0.2,0.3\}.

Results. Table 12 lists the 24 cells behind the counts of § 5.1. The four negative cells are ℓ=w=25\ell=w=25 at n=100n=100, where the band covers 44.5% of the matrix; the two ties are ℓ=6\ell=6, n=300n=300 at σ≥0.2\sigma\ge0.2, where the correlation length is short relative to nn, the global order is weakly identified and all methods are poor (τ\tau between 0.25 and 0.34). Runtimes at n=300n=300 (one EPYC core): spectral 0.002 s, convex ≈\approx 0.25 s, FAQ 0.6–1.1 s, AltLAP-r1 0.1–0.2 s, of which the exchange phase is the larger part.

ℓ\elln, σn,\ \sigmaSpectralConvexFAQAltLAP-r1Δ\Delta vs spectral [CI], seeds +/−+/-Δ\Delta vs convex [CI], seeds +/−+/-
6100, 0.050.9810.9920.2691.000+0.019 [+0.017, +0.021], 20/0+0.008 [+0.007, +0.008], 20/0
6100, 0.10.9430.9750.3570.986+0.043 [+0.036, +0.051], 20/0+0.011 [−0.001, +0.021], 17/3
6100, 0.20.8240.9050.2930.861+0.037 [+0.020, +0.053], 17/3−0.044 [−0.084, −0.003], 9/11
6100, 0.30.6730.7000.2250.722+0.049 [+0.029, +0.072], 18/2+0.022 [−0.007, +0.047], 15/5
6300, 0.050.8110.8610.1590.828+0.017 [+0.011, +0.022], 18/2−0.033 [−0.083, +0.015], 8/12
6300, 0.10.5430.5490.1650.554+0.011 [+0.001, +0.020], 14/6+0.004 [−0.072, +0.078], 8/12
6300, 0.20.3360.3340.1170.337+0.002 [−0.006, +0.009], 9/11+0.003 [−0.088, +0.080], 10/10
6300, 0.30.2500.2840.1090.256+0.006 [−0.006, +0.017], 12/8−0.029 [−0.097, +0.033], 10/10
12100, 0.050.9950.9970.6340.997+0.002 [+0.002, +0.003], 17/1−0.000 [−0.001, +0.001], 9/7
12100, 0.10.9830.9880.5920.991+0.008 [+0.007, +0.009], 20/0+0.003 [+0.002, +0.004], 18/2
12100, 0.20.9540.9660.6620.981+0.027 [+0.023, +0.030], 20/0+0.015 [+0.013, +0.017], 20/0
12100, 0.30.9210.9390.6580.972+0.051 [+0.045, +0.058], 20/0+0.033 [+0.030, +0.036], 20/0
12300, 0.050.9800.9900.2410.999+0.019 [+0.018, +0.020], 20/0+0.010 [+0.009, +0.010], 20/0
12300, 0.10.9430.9660.3260.977+0.034 [+0.026, +0.041], 19/1+0.011 [−0.001, +0.020], 16/4
12300, 0.20.8390.8610.2640.889+0.050 [+0.032, +0.065], 18/2+0.028 [−0.010, +0.052], 17/3
12300, 0.30.7090.7870.1690.750+0.041 [+0.018, +0.062], 17/3−0.037 [−0.133, +0.026], 14/6
25100, 0.050.9990.9990.9900.991−0.008 [−0.008, −0.007], 0/20−0.008 [−0.008, −0.007], 0/20
25100, 0.10.9930.9930.9790.980−0.012 [−0.013, −0.011], 0/20−0.012 [−0.013, −0.011], 0/20
25100, 0.20.9780.9780.9600.962−0.016 [−0.018, −0.013], 0/20−0.016 [−0.018, −0.014], 0/20
25100, 0.30.9600.9610.9420.945−0.015 [−0.018, −0.012], 0/20−0.016 [−0.018, −0.013], 0/20
25300, 0.050.9920.9960.4970.997+0.005 [+0.004, +0.005], 20/0+0.001 [+0.001, +0.002], 20/0
25300, 0.10.9820.9880.5600.993+0.012 [+0.011, +0.013], 20/0+0.006 [+0.005, +0.006], 20/0
25300, 0.20.9590.9710.5160.988+0.029 [+0.027, +0.031], 20/0+0.017 [+0.017, +0.018], 20/0
25300, 0.30.9330.9500.4920.983+0.050 [+0.045, +0.054], 20/0+0.033 [+0.031, +0.034], 20/0

Table 12. Latent-order recovery, all 24 cells: ∣τ∣|\tau| against the planted order (mean over 20 seeds; best of spectral, convex and ours in bold) and paired differences of AltLAP-r1 against spectral and convex seriation. FAQ optimizes the same pattern objective from its default starts.

Mask width. The band width given to the solver is the correlation length of the generator. Table 13 repeats AltLAP-r1 with the width halved and doubled: a factor-two error in either direction changes τ\tau by less than 0.01 in most cells and by up to 0.06 (doubled width at ℓ=12\ell=12, n=100n=100, σ=0.3\sigma=0.3), where the lead over convex seriation is lost; a four-fold overestimate (w=25w=25 at ℓ=6\ell=6, n=100n=100) falls below the spectral order. Choosing the width by the density-normalized score of § 4.1 is not an option on these smooth kernels: the score never selects a width below the correlation length and picks a wider candidate whenever one is available, so ww is a user input here.

Table 13: Latent-order recovery with the band width halved and doubled (∣τ∣|\tau|, mean over 20 seeds; the paper’s width w=ℓw=\ell in bold). At n=100n=100 the doubled width 50 is omitted.

ℓ\elln,σn,\sigmaSpectralConvexw=ℓ/2w=\ell/2w=ℓw=\ellw=2ℓw=2\ell
6100, 0.10.9430.9750.9810.9860.983
6100, 0.30.6730.7000.7100.7220.726
6300, 0.10.5430.5490.5470.5540.553
6300, 0.30.2500.2840.2550.2560.261
12100, 0.10.9830.9880.9890.9910.972
12100, 0.30.9210.9390.9670.9720.913
12300, 0.10.9430.9660.9750.9770.971
12300, 0.30.7090.7870.7480.7500.759
25100, 0.10.9930.9930.9770.980–
25100, 0.30.9600.9610.9390.945–
25300, 0.10.9820.9880.9920.9930.986
25300, 0.30.9330.9500.9780.9830.958

Table 13.

Consecutive ones, circular seriation, and nestedness

Consecutive ones (fixed-width staircase recovery). The consecutive-ones property (§ 5.1) is decided in linear time by PQ-trees [9], but recognition is brittle (one corrupted entry can destroy the property), so the applied literature, from physical mapping to archaeological seriation [31], orders the matrix with heuristics: barycentre reordering, spectral [4] and convex [21] seriation. Our target is the staircase band Mij=1[si≤j<si+w]M_{ij}=1[s_i\le j<s_i+w] with non-decreasing starts sis_i, fitted with independent row and column permutations; for a matrix whose rows all carry ww ones, AA has the C1P iff dM(A)=0d_M(A)=0 for some mask of this family (ordering rows by the start of their interval makes the starts non-decreasing). General C1P with varying interval lengths is a larger class and would require a search over the start and length profiles; what we test is the noisy recovery of the fixed-width model, with the evenly spaced profile sis_i and its sensitivity below. Instances: planted 60 × 60 staircases with w=12w=12 and independent flip noise at rate ff, 20 seeds. Our solver runs from random restarts only and keeps the candidate with the best mask fit, which uses no labels. Metrics: ∣τ∣|\tau| of the recovered row and column orders against the planted ones, and edits, the minimum number of entries that must be changed to make every row contiguous under the returned ordering.

Paired against convex seriation, the column τ\tau of the staircase fit is higher by +0.075 [+0.063, +0.088], +0.136 [+0.118, +0.157], +0.280 [+0.220, +0.358] and +0.377 [+0.300, +0.469] at f=0.02f=0.02, 0.05, 0.10, 0.15, and the edit count lower by 97 [89, 106], 148 [137, 160], 215 [194, 238] and 216 [202, 232], on 20 of 20 seeds at every level. An insertion local search on the 2-SUM criterion needs 114–201 more edits than the staircase fit on 20 of 20 seeds, so the gain is not produced by refinement as such. Row totals are constant by construction and column totals vary only near the boundary, which is why sorting by marginals carries almost no information. Runtimes: 0.03 s spectral, 0.18 s convex, 0.3–0.5 s local search, 0.5–1 s ours.

Table 15 repeats the comparison with the shape of the matrix, the start profile and the interval lengths varied. The fixed staircase keeps the higher τ\tau and the lower edit count for rectangular matrices, for an irregular start profile and for interval lengths jittered by up to ±8\pm8, with the smallest margins under the irregular profile and the largest jitter. Re-estimating the mask from the data after the cold fit, one interval per row (the interval-envelope pattern of Figure 1), lowers the edit count slightly and restores the row order under the irregular profile.

Settingf=0.05f=0.05 noisef=0.05f=0.05 convexf=0.05f=0.05 fixed maskf=0.05f=0.05 re-estimatedf=0.15f=0.15 noisef=0.15f=0.15 convexf=0.15f=0.15 fixed maskf=0.15f=0.15 re-estimated
60 ×\times 60, w=12w=12 (as Table 14)1790.86 / 3171.00 / 1661.00 / 1655400.51 / 7160.92 / 4960.93 / 494
40 ×\times 80, w=16w=161610.80 / 3280.98 / 1550.98 / 1534830.49 / 6690.77 / 4610.77 / 451
80 ×\times 40, w=8w=81610.88 / 2471.00 / 1451.00 / 1454830.61 / 5740.97 / 4300.97 / 430
irregular start profile1790.71 / 3340.85 / 1880.85 / 1845400.51 / 6950.80 / 5100.80 / 507
interval lengths 12±412 \pm41790.86 / 3040.96 / 1890.97 / 1825400.53 / 7040.86 / 5150.85 / 510
interval lengths 12±812 \pm81790.87 / 2910.91 / 2050.93 / 1935400.65 / 6640.78 / 5270.80 / 519

Table 15. Noisy consecutive ones under changes of the generator (20 seeds): column ∣τ∣|\tau| / edits for convex seriation, the fixed staircase mask and the mask re-estimated as one interval per row; “noise” is the number of entries flipped during corruption.

Table 14: Noisy consecutive ones (60 × 60, w=12w=12, 20 seeds): row ∣τ∣|\tau| / column ∣τ∣|\tau| / edits. Controls use the identical protocol and restart budget with a random or a block mask of the same density.

Methodf=0.02f=0.02f=0.05f=0.05f=0.10f=0.10f=0.15f=0.15
Sort by marginals0.05 / 0.04 / 5820.05 / 0.05 / 6380.06 / 0.06 / 7340.07 / 0.06 / 837
Barycentre reordering0.73 / 0.66 / 2950.61 / 0.51 / 4480.53 / 0.42 / 6080.46 / 0.36 / 732
Spectral seriation0.90 / 0.87 / 2030.84 / 0.66 / 4470.67 / 0.44 / 6590.49 / 0.37 / 790
Convex seriation0.92 / 0.92 / 1630.85 / 0.85 / 3120.71 / 0.69 / 5500.50 / 0.53 / 718
Spectral + 2-SUM local search0.92 / 0.88 / 1810.85 / 0.83 / 3320.71 / 0.61 / 5700.49 / 0.53 / 721
Staircase mask, AltLAP (cold)0.99 / 1.00 / 660.99 / 0.99 / 1640.98 / 0.97 / 3350.95 / 0.91 / 502
Spectral, then AltLAP0.99 / 1.00 / 670.98 / 0.97 / 1680.83 / 0.78 / 3680.56 / 0.53 / 550
Control: random mask (cold)0.06 / 0.06 / 6170.07 / 0.07 / 6720.05 / 0.07 / 7650.08 / 0.09 / 859
Control: block mask (cold)0.28 / 0.25 / 3220.31 / 0.29 / 4020.34 / 0.31 / 5370.24 / 0.21 / 666

Table 14.

Circular seriation

A latent order can be cyclic rather than linear: similarities between points on a closed curve are banded modulo nn, and spectral seriation needs a dedicated circular embedding for this case [46]. The question is whether the same solver covers the cyclic geometry by changing only the mask. For n=120n=120 points on a circle with a decaying kernel and Gaussian noise, the target is the cyclic band mask of width 10 and the reference is the spectral circular embedding; the metric is circular Kendall τ\tau up to rotation and reflection (20 seeds). Ours is the better of 128 cold restarts and a coarse-to-fine run, chosen by the objective. In Table 16 both methods recover the order at low noise (the difference is within ±0.01\pm0.01); at noise 0.5 and 0.7 the cyclic band is ahead (+0.035 and +0.103, on 13 and 18 of 20 seeds), and at noise 1.0 neither recovers the order and the interval contains zero. The linear spectral order is far below throughout, so the cyclic mask, not a generic ordering, carries the result; the gain over the circular embedding is concentrated at moderate noise.

NoiseSpectral (linear)Circ. spectralCirc. spectral →\to AltLAPAltLAP, cyclic (cold)Δ\Delta vs circ. spectral [CI]seeds +/−
0.30.3720.9630.9650.958−0.005 [−0.015, +0.006]6/13
0.50.3930.9030.9340.938+0.035 [+0.014, +0.055]13/7
0.70.3320.7820.8790.885+0.103 [+0.065, +0.138]18/2
1.00.2030.4310.4710.469+0.039 [−0.072, +0.142]11/9

Table 16. Circular seriation (n=120n=120, cyclic band w=10w=10): circular Kendall τ\tau, mean over 20 seeds, and the paired difference of ours against the circular spectral embedding.

Nestedness: a boundary case. In a nested (Ferrers) matrix the ones of each row contain those of every row with a smaller degree, the structure of species-by-site and similar ecological matrices [10]. The question here is whether a general reordering objective adds anything where a one-pass specialized method exists: sorting rows and columns by their marginals recovers a noiseless nested matrix exactly and, although under flip noise it need not minimize our objective, it is the reference. For planted 60 ×\times 80 Ferrers matrices with flip rate ff, the two-sided AltLAP uses the nested mask with its profile estimated from the row degrees (no oracle information); Table 17 gives the column ∣τ∣|\tau| and the flips to a nested matrix (20 seeds). The mask fit reproduces the degree order at f≤0.02f \le0.02 and falls below it from f=0.05f=0.05 on, by 0.06 in τ\tau at f=0.15f=0.15 with a similar flip count; warm-starting from the degree order does not help, and a larger restart budget does not change the values. Where degree sorting already recovers the structure, the mask objective adds nothing; this is the boundary case noted in § 5.1.

ffDegree sortSpectralAltLAP, nested maskDegree sort →\to AltLAP
0.00.994 / 00.586 / 12770.994 / 00.994 / 0
0.020.967 / 1340.573 / 13820.965 / 1290.963 / 131
0.050.942 / 3010.544 / 16580.932 / 2990.925 / 301
0.10.906 / 5740.548 / 17120.881 / 5860.862 / 587
0.150.876 / 8190.507 / 19310.817 / 8430.806 / 842

Table 17. Nestedness (60 ×\times 80 planted Ferrers matrices, flip rate ff, 20 seeds): column ∣τ∣|\tau| / flips to a nested matrix under the returned order (lower is better).

Block models against the state of the art

Sparse binary SBM at the detectability scale. Symmetric SBM with k=4k=4 equal blocks, n=500n=500, cin=c+(k−1)λcc_{\mathrm{in}}=c+(k-1)\lambda\sqrt{c} and cout=c−λcc_{\mathrm{out}}=c-\lambda\sqrt{c}, so λ=1\lambda=1 is the asymptotic (Kesten–Stigum) detectability threshold [19], mean degree c∈{8,16,32}c \in\{8,16,32\}, 20 seeds. Panel: Bethe Hessian H(r)=(r2−1)I−rA+DH(r)=(r^2-1)I-rA+D with r=cr=\sqrt{c} [49]; the non-backtracking operator in Ihara–Bass form [34]; regularized spectral clustering [43];

Leiden [53], which estimates kk itself; the block mask fitted by Alternating LAP from eight random starts, the LAP and exchange phases interleaved per start (three rounds) and the best start kept by the criterion (“ours”); and the same run started from the Bethe-Hessian partition. All methods except Leiden receive the true kk; our mask also encodes equal block sizes, which the planted model satisfies and the spectral methods do not use. On sparse {0,1}\{0,1\} graphs the LAP phase alone stalls early (ARI 0.56 at λ=1.6\lambda= 1.6, c=16c = 16, with the exchange phase disabled, 32 starts); with the exchange phase the fit reaches 0.82.

With equal block sizes the number of within-block pairs is fixed, so maximizing the within-block edge count, which is our criterion on a {0,1}\{0,1\} matrix, is the maximum-likelihood objective for the planted partition at any nn and any p>qp > q (for p<qp < q the sign reverses; for k=2k = 2 it is minimum bisection; Abbe, [1]). The crossover of § 5.2 moves with the mean degree (Table 18). Below it the criterion values are 0.33 (ours) against 0.24 (Bethe-Hessian partition) in error reduction at c=16c = 16, λ=1.3\lambda= 1.3, with the ARIs in the opposite order; the gap between the MAP and the Bayes-optimal (belief-propagation) estimator near the threshold is the reason belief propagation and its spectral linearizations were introduced [19, 34, 49]. We do not establish inconsistency of the criterion at this nn, nor that the search reaches its global optimum. Refining the Bethe-Hessian partition with our criterion costs 0.3–0.5 s on top of its 0.04 s.

λ\lambdaccBethe H.Non-backtr.Reg. sp.LeidenSwap onlyOursBH →\to oursΔ\Delta vs BH [CI]seeds +/−+/-
1.380.420.380.410.130.050.150.47−0.272-0.272 [−0.296-0.296, −0.248-0.248]0/20
1.3160.430.390.350.150.080.220.51−0.208-0.208 [−0.249-0.249, −0.167-0.167]1/19
1.3320.470.390.400.130.110.350.57−0.116-0.116 [−0.168-0.168, −0.059-0.059]2/18
1.680.730.720.730.610.130.700.78−0.034-0.034 [−0.083-0.083, +0.009+0.009]11/9
1.6160.740.740.750.710.320.820.82+0.080+0.080 [+0.069+0.069, +0.093+0.093]20/0
1.6320.780.780.780.830.580.860.86+0.079+0.079 [+0.063+0.063, +0.095+0.095]18/2
2.080.920.910.920.940.790.940.95+0.022+0.022 [+0.013+0.013, +0.030+0.030]18/2
2.0160.920.920.920.950.940.950.95+0.028+0.028 [+0.021+0.021, +0.036+0.036]20/0
2.0320.940.940.940.970.960.970.97+0.027+0.027 [+0.019+0.019, +0.034+0.034]19/1
2.580.990.980.990.990.981.001.00+0.009+0.009 [+0.006+0.006, +0.012+0.012]18/2
2.5160.990.990.990.990.991.001.00+0.007+0.007 [+0.004+0.004, +0.010+0.010]17/1
2.5320.990.990.991.001.001.001.00+0.009+0.009 [+0.006+0.006, +0.013+0.013]18/0

Table 18. Sparse SBM, k=4k = 4, n=500n = 500, mean ARI over 20 seeds. “Ours” is Alternating LAP from random starts; “swap only” is a Kernighan–Lin-style exchange search alone from random balanced partitions (same criterion and block sizes); the paired difference is against the Bethe Hessian, with the best panel method per row in bold.

Weighted planted partition. A=μ⋅1[same block]+EA = \mu\cdot1[\text{same block}] + E with μ>0\mu> 0 and EE symmetric with i.i.d. N(0,σ2)\mathcal{N}(0,\sigma^2) upper-triangular entries, σ=1\sigma= 1, n=300n = 300, k=4k = 4 equal blocks, 20 seeds. This is the regime of the block experiments in the paper, where minimizing the signed off-mask mass is the maximum-likelihood criterion for the partition. Spectral clustering on the weighted matrix is the natural baseline; graph methods are defined for graphs and receive the matrix sparsified at its strongest 10% of entries. The squared loss rewards large negative off-mask entries as if they were structure, which is why it fails on this generator, whose blocks differ in mean but not in variance (the ablation column); the linear loss, which on a {0,1}\{0,1\} matrix coincides with the squared one, is the likelihood here. A Kernighan–Lin-style swap search on the same linear criterion tracks the run from μ=0.4\mu= 0.4 on and lies 0.02–0.03 below it at the two weakest signals, so on these dense matrices the criterion, not the particular optimizer, carries the result.

Table 19: Weighted planted partition (n=300n = 300, k=4k = 4, σ=1\sigma= 1), mean ARI over 20 seeds; paired difference of ours (AltLAP-lin, cold start) against spectral clustering. “Squared” is AltLAP on the squared loss of Definition 1 (the ablation row); “KL (lin.)” is a Kernighan–Lin-style swap search on the same linear criterion from random balanced starts, an alternative optimizer of our objective.

μ\muSpectralReg. sp.Bethe H.Non-b.LeidenSquaredKL (lin.)AltLAP-linSpec. → oursΔ\Delta vs spectral [CI]seeds +/−
0.300.4030.0280.0640.0520.0330.0030.3240.3560.556−0.046 [−0.111, +0.024]7/13
0.350.6800.0730.1190.1020.0540.0040.8070.8270.838+0.147 [+0.126, +0.169]20/0
0.400.8500.1540.2180.1790.0920.0060.9270.9320.932+0.081 [+0.058, +0.105]19/1
0.500.9750.4820.5600.4450.3540.0180.9940.9950.995+0.020 [+0.014, +0.027]18/1
0.600.9960.8210.8140.8130.8660.0501.0001.0001.000+0.004 [+0.002, +0.008]7/0

Table 19.

At the weakest signal the cold run is within the interval of spectral clustering and the spectral-started run is the entry that pays: +0.154 [+0.118, +0.188] and +0.159 [+0.135, +0.182] over spectral clustering at μ=0.30\mu= 0.30 and 0.35.

Block sizes. The block mask fixes the block sizes, which above are the planted (equal) ones. Table 20 plants blocks of sizes 1:1:2:2 as well and gives the solver the equal-size mask, the true sizes, or sizes estimated as the cluster sizes of the size-free spectral method in the same panel (regularized spectral clustering on the graphs, spectral clustering on the weighted matrices; no labels), next to the size-free baselines, the Kernighan–Lin-style swap search on the same criterion with the true sizes (KL) and Alternating LAP started from the Bethe-Hessian partition. With equal planted blocks the estimated sizes cost almost nothing. With unequal blocks the equal-size mask is misspecified and falls below the size-free methods, the true sizes give the best result in the panel, and the estimated sizes recover most of the gap, above the partition they were taken from. The swap search from random starts needs the dense signal of the weighted matrices and stays low on the sparse graphs, so the LAP steps, not the exchanges alone, do the work there.

Table 20: Block recovery with the block sizes in the mask equal, true, or estimated from a spectral partition (ARI). Top: sparse SBM, n=500n=500, k=4k=4, c=16c=16, 20 seeds, ours = Alternating LAP. Bottom: weighted planted partition, n=300n=300, k=4k=4, σ=1\sigma=1, 10 seeds, 16 restarts, ours = AltLAP-lin.

Planted sizesλ\lambdaBethe H.Reg. spectralLeidenKL (true)BH → ours (true)equaltrueestimated
equal1.60.740.750.740.320.790.820.820.80
equal2.00.920.920.950.940.950.950.950.94
1:1:2:21.60.590.540.520.660.520.490.840.65
1:1:2:22.00.890.850.930.920.680.590.960.89
Planted sizesμ\muSpectralKL-lin (true)Squared loss (true)equaltrueestimated
equal0.40.840.930.000.930.930.89
equal0.60.991.000.031.001.000.99
1:1:2:20.40.620.940.010.550.940.79
1:1:2:20.60.981.000.070.631.000.98

Table 20.

Real labelled networks. The same panel on standard networks with published communities (Table 21; equal-size masks, or “+sizes”: block sizes re-estimated from the order by change-point segmentation, three rounds, no oracle information). Reference partitions: the two factions of Zachary’s karate club [60]; the two groups of nine women of the Davis Southern Women data [18, 22], with the bipartite women–events graph used as a symmetric adjacency on all 32 nodes and ARI computed on the 18 women; the three classes of the political-books network (compiled by V. Krebs; [40]) and the twelve conferences of the football network [26]. All methods receive kk; PatLR uses rank 1; results are means over 10 seeds (standard deviations ≤0.03\le0.03, zero for the deterministic methods). Les Misérables has no published partition (the block(19, 19, 19, 20) mask of § 5.3 is an equal split, not a ground truth) and is not scored here. Two details behind § 5.2: on Karate the low-rank term of PatLR carries the degree profile, which the plain block fit has to place inside the blocks; on polbooks (49/43/13) the equal-size mask improves the error reduction while the ARI does not move, a balanced partition being a different problem from community detection.

Table 21: Community recovery on labelled networks (ARI). “+sizes”: block sizes re-estimated from the order (change-point segmentation) instead of equal sizes; “BH →” initializes from the Bethe-Hessian partition. PatLR uses rank 1.

MethodKarate (k=2k=2)Davis (k=2k=2)Polbooks (k=3k=3)Football (k=12k=12)
Spectral clustering0.8820.0000.4650.813
Regularized spectral0.8820.0000.6240.869
Bethe Hessian0.8821.0000.6590.897
Non-backtracking0.8821.0000.4050.906
Leiden0.4650.4050.6210.807
AltLAP, equal blocks0.7720.7770.4550.739
AltLAP + sizes0.7721.0000.4730.733
BH → AltLAP0.7720.7770.4790.763
BH → AltLAP + sizes0.7720.7770.4790.793
PatLR, equal blocks1.0000.7770.4920.743
PatLR + sizes1.0000.7770.4760.775
BH → PatLR0.7721.0000.4770.752
BH → PatLR + sizes0.7721.0000.4810.764

Table 21.

Composite target: a band inside blocks

Planted matrices with k∈{3,5}k \in\{3,5\} blocks (equal or unequal sizes), a band of width w∈{1,3}w \in\{1,3\} inside each block, noise σ∈{0.1,0.3}\sigma\in\{0.1,0.3\}, n=150n=150, 20 seeds: 16 configurations. The target mask is the band inside the blocks (block AND band); the union mask would be blind to the within-block order. Metrics: error reduction on the target mask, ARI of the block assignment read off the order, and within-block Kendall τ\tau. Methods: spectral clustering (blocks only), global Fiedler ordering, a two-stage pipeline (cluster, then spectral order within each cluster), QAP-FAQ and AltLAP on the composite mask, AltLAP with a change-point estimate of the block boundaries (for unequal sizes), and AltLAP warm-started from the two-stage pipeline.

Table 22 averages over the configurations and Table 23 gives each one with its paired interval; the summary is in § 5.2. Details: the refining pass re-estimates the block boundaries from the order by change-point segmentation, so the block sizes are not given; it raises the target error reduction by +17% to +257% relative (median +96%), from a median 45% of the planted order’s value for the pipeline to 94% for the refined run (90–99% at w=3w=3, σ=0.1\sigma=0.1), and by +11% to +227% when the pipeline uses convex seriation inside the blocks, with the within-block τ\tau gain at w=3w=3 is +0.02 to +0.09 with the interval above zero in 7 of 8 configurations, and at w=1w=1 it is within ±0.02, a band of width one determining little of the order. From a cold start the composite mask alone gives block ARI 0.78, and 0.88 with the boundary estimate (e.g. 0.45 → 0.89 on k=3k=3, unequal, w=3w=3, $\sigma=0.3); for the within-block order the hard mask truncates the smooth decay, and the pipeline’s seriation is the better starting point, which is why the two are combined. FAQ from its default starts does not recover the blocks (Table 22).

Table 22: Composite band-in-block target, averages over the 16 configurations and 20 seeds; per-configuration values in Table 23.

Methodtarget ERblock ARIwithin-block τ\tau
Spectral clustering0.0571.0000.09
Fiedler ordering0.0500.8390.10
Two-stage (cluster, then order)0.1151.0000.45
QAP-FAQ (composite mask)0.1370.1810.18
AltLAP (composite mask)0.1710.7810.20
AltLAP + boundary estimation0.1730.8770.20
Two-stage, then AltLAP0.1901.0000.47
Two-stage, convex seriation inside0.1241.0000.46
Two-stage (convex), then AltLAP0.1931.0000.48

Table 22.

kkwwσ\sigmaoraclepipel.+Altrel.Δ\Delta [CI]pipel.+AltΔ\Delta [CI]pipel.+Alt
3 eq.10.10.1300.0430.104+142%+0.061 [+0.060, +0.062]0.310.32+0.007 [−0.009, +0.023]0.0450.105
3 eq.10.30.0860.0250.084+239%+0.059 [+0.058, +0.061]0.170.16−0.009 [−0.029, +0.010]0.0260.084
3 eq.30.10.3050.1960.288+47%+0.093 [+0.088, +0.097]0.710.76+0.054 [+0.038, +0.071]0.2150.290
3 eq.30.30.2140.1000.200+100%+0.100 [+0.096, +0.103]0.410.43+0.024 [−0.001, +0.050]0.1000.200
3 uneq.10.10.1160.0360.091+154%+0.055 [+0.053, +0.057]0.290.30+0.003 [−0.010, +0.015]0.0380.093
3 uneq.10.30.0790.0220.077+257%+0.055 [+0.054, +0.057]0.170.15−0.018 [−0.039, +0.004]0.0240.077
3 uneq.30.10.2760.1630.248+53%+0.085 [+0.082, +0.089]0.630.68+0.055 [+0.041, +0.071]0.1780.257
3 uneq.30.30.1990.0830.179+115%+0.096 [+0.093, +0.098]0.400.44+0.030 [+0.013, +0.050]0.0900.185
5 eq.10.10.1930.0900.168+87%+0.078 [+0.076, +0.080]0.440.46+0.019 [+0.009, +0.028]0.0960.166
5 eq.10.30.1100.0430.108+153%+0.065 [+0.063, +0.068]0.240.22−0.021 [−0.037, −0.004]0.0460.108
5 eq.30.10.4150.3530.413+17%+0.060 [+0.055, +0.065]0.870.96+0.089 [+0.080, +0.099]0.3720.414
5 eq.30.30.2630.1730.260+50%+0.087 [+0.084, +0.090]0.560.63+0.065 [+0.048, +0.082]0.1830.262
5 uneq.10.10.1660.0720.138+93%+0.067 [+0.065, +0.068]0.400.41+0.013 [+0.003, +0.023]0.0760.140
5 uneq.10.30.1000.0360.097+168%+0.061 [+0.060, +0.062]0.210.21−0.006 [−0.026, +0.014]0.0400.099
5 uneq.30.10.3690.2720.347+28%+0.076 [+0.072, +0.080]0.800.86+0.062 [+0.050, +0.071]0.3030.361
5 uneq.30.30.2430.1420.230+62%+0.088 [+0.084, +0.091]0.510.55+0.046 [+0.017, +0.074]0.1510.238

Table 23. Composite target per configuration (20 seeds): the two-stage pipeline (spectral clustering, spectral seriation inside each cluster) and the same pipeline followed by one AltLAP pass on the band-in-block mask; “oracle” is the error reduction of the planted order on that mask. Paired differences with 95% bootstrap intervals; block ARI is 1.00 for both in every configuration. The last two columns repeat the ER for the pipeline with convex seriation inside the clusters.

Attention Head Analysis: Full Details

This appendix gives the pipeline behind § 5.5, the per-model results, and the identity-order control. All numbers come from one run of the unified scoring described below.

Score, Vocabulary and a Synthetic Check

The score s~M(A)\widetilde{s}_M(A) of (6) on a causal attention matrix (rows queries, columns keys) is the minimum mass outside the mask after a common reordering of queries and keys, normalized by ∥A∥F2(1−ρM)3/2\lVert A\rVert_F^2(1-\rho_M)^{3/2} (equation (6)). The strict upper triangle is identically zero and contributes nothing to dMd_M for any mask and permutation, so no symmetrization is needed. The masks are the plain geometric masks of § 2, not their intersection with the lower triangle (the arrowhead is the full hub row, hub column and diagonal, which is what the closed form of Appendix § 11.§ 3 assumes); a common permutation does not preserve the causal triangle itself, and the structural labels describe the reordered matrix. The nine masks of § 5.5 were fixed ahead of time to span the regimes of the standard taxonomy of attention [14, 56, 59]: local routing (bands of width 1, 2, 4), segment- or topic-level grouping (blocks, k=2,3,4k=2,3,4), sink-like global routing of every query to a few distinguished keys such as BOS (arrowhead), modular-local heads (three blocks plus the band ∣i−j∣≤2|i-j|\leq2) and pure self-loops (diagonal). The vocabulary is a controlled basis set, not an exhaustive one. At n=512n=512 the block+band mask (blocks of 170 plus a remainder block of 2, plus the band) differs from block-k3k3 (blocks of 170, 170, 172) in 0.3% of the entries, so near-ties between the two labels are expected and the two are read together below.

Synthetic check. Four head types with a constructed ground truth are scored with the full pipeline at n=128n=128 (20 instances each, scrambled by a random permutation; Table 24, Figure 10): a local head (Gaussian kernel of width 1.5 tokens plus noise, so that the band ∣i−j∣≤4|i-j|\leq4 holds 99% of the kernel mass), a topic head (three equal blocks plus noise), a global head (every query attends the first key, plus a diagonal and noise) and a self head (a dominant diagonal plus noise). The global and topic heads are identified in every instance, the topic head either as block-k3 or as the block+band mask that contains its blocks; the local head is identified in most instances, with block masks selected otherwise at a small margin (the noise carries two thirds of the energy of these instances). The self head is a boundary case of the vocabulary: every mask that contains the diagonal fits it, the optimized thin bands pack slightly more noise than the diagonal alone, and the label thin band in every instance, by a small margin. A pure self-loop head is therefore reported by this pipeline as a thin band, and the band labels of real heads should be read as covering it.

Head typeTrue maskTrue mask selectedLabels selectedMargin
Localband w=4w=415/20band w=4w=4 (15), block+band (3), block k=3k=3 (1), block k=4k=4 (1)0.03
Topicblock k=3k=312/20block k=3k=3 (12), block+band (8)0.56
Globalarrowhead20/20arrowhead (20)0.60
Selfdiagonal0/20band w=4w=4 (20)0.02

Table 24. Synthetic attention heads scored with the paper’s pipeline (9-mask vocabulary, density-normalized score, identity candidate, n=128n=128, 20 instances per type): instances in which the true mask is the label, the labels selected, and the median relative margin of the selected mask over the runner-up.

Figure 10. Synthetic attention heads, one instance per type: the scrambled input (top) and the same matrix in the order returned for the selected mask, mask outlined (bottom), with the density-normalized scores of the selected and, where different, of the true mask.

Pipeline

Models and prompts. GPT-2 [117M parameters, 12 layers ×\times 12 heads; Radford et al., [45]], Qwen2.5-0.5B (24×1424 \times14) and Qwen2.5-7B (28×2828 \times28) [Qwen Team, [44]], loaded from the Hugging Face hub (gpt2, Qwen/Qwen2.5-0.5B, Qwen/Qwen2.5-7B). The prompts are the first 20 passages of at least 5n5n characters formed from consecutive non-heading lines of the WikiText-2 validation split [Merity et al., [39]] (its first two to five articles), tokenized by each model’s tokenizer and truncated to n∈{128,512}n \in\{128, 512\} tokens (two passages fall a few tokens short of 512); the passages differ between the two lengths.

Extraction. One forward pass per (model, prompt, length) on a single GPU (one H100; about two hours for the full grid of models, prompts and lengths) returns the L×H×n×nL \times H \times n \times n tensor of post-softmax attention weights (fp16 for the Qwen models, fp32 for GPT-2; non-finite rows, which occur in ≤0.1%\le0.1\% of the rows of Qwen2.5-7B, are zeroed).

Scoring. For every (layer, head, prompt) and every mask of the vocabulary we compute (i) the optimized score, Alternating LAP from a spectral start with 8 iterations and 2 restarts at n=512n=512 (12 and 3 at n=128n=128). On a causal AA the symmetric eigensolver of Appendix § 12.§ 1 reads the lower triangle, so the operator it diagonalizes is D−WD-W with W=A+AT−diag⁡AW=A+A^{\mathsf{T}}-\operatorname{diag} A and D=diag⁡(A1)D=\operatorname{diag}(A\mathbf{1}), the identity for softmax rows; the start is therefore the order by the second-largest eigenvector of the symmetrized attention matrix WW, not the Fiedler vector of its graph Laplacian (whose degree matrix would be diag⁡(W1)\operatorname{diag}(W\mathbf{1}). The objective itself is not symmetrized. (ii) The identity score, under the native token order, and (iii) the mean score under five random permutations (the null level). The score of a mask is the lower of (i) and (ii); for the arrowhead mask the closed-form optimum of Appendix C.3 is taken as well (it is attained to within 1% by the solver for 99.6–99.9% of the pairs). The label of a pair is the mask with the lowest score; its margin is the relative gap to the runner-up. Scoring one 512-token head takes about 12 core-seconds (Appendix § 13.8).

Intervals. All intervals are 95% bootstrap intervals over prompts (the 20 prompts resampled with replacement, the statistic recomputed on all heads), i.e. they treat the prompt, not the (head, prompt) pair, as the unit of replication.

Per-Model Results

Table 25 gives the per-model numbers behind § 5.5 at both lengths; Figure 11 the per-layer label shares and Figure 12 the per-head modal label, its agreement over prompts and its margin. The depth profile is the same in all six (model, length) cells: block labels in the first three to four layers, arrowhead after them, with Qwen2.5-0.5B returning to block-k2 in its last two layers at both lengths. Within a model the label shares move by a few points between n=128n=128 and n=512n=512, and the modal label of a head is the same at both lengths for 91–95% of the heads (0.70–0.77 among the heads whose modal label is not arrowhead at both lengths, so the block-type labels are less stable than the arrowhead label and the layer profile). On the 10-bin relative-depth grid the three models agree in 8/10 bins at both lengths; pairwise agreement is 0.9 for GPT-2 vs. Qwen2.5-7B and for Qwen2.5-0.5B vs. Qwen2.5-7B and 0.8 for GPT-2 vs. Qwen2.5-0.5B. The last column of Table 25 is the accuracy of a multinomial logistic regression that predicts the label of a pair from four scalar descriptors of the head on that prompt (row entropy, mean maximum weight, sparsity, mean distance from the diagonal), trained on 19 prompts and tested on the held-out one; it is well above the majority label and well below one, so these descriptors partially predict the labels under the tested logistic-regression model. About three quarters of the pairs carry a confident label, a margin over the runner-up above 20% (column “confident”). Figure 13 shows representative heads before and after reordering: the block-labelled heads of the first layers are wide local heads whose mass already lies in the diagonal blocks in the native order (the native order is within 1% of the optimum for 74–84% of the block-labelled pairs at n=512n=512, 57–71% at n=128n=128), and on the Qwen2.5-7B passages whose sink is not the first token the reordering moves the sink key to the front.

Modelnnarrowhead [CI]block-k2other blocksbandsallarrowheadotherconfidentnullscalars / maj.
GPT-251269.3 [69.0, 69.7]14.812.93.00.910.990.740.770.070.87 / 0.69
GPT-212872.2 [71.7, 72.6]12.810.84.10.900.980.680.780.080.86 / 0.72
Qwen2.5-0.5B51267.1 [66.5, 67.6]15.915.41.60.860.960.640.710.120.81 / 0.67
Qwen2.5-0.5B12869.1 [68.3, 69.8]16.312.91.70.860.960.620.740.120.81 / 0.69
Qwen2.5-7B51279.9 [79.4, 80.3]11.48.20.50.920.980.670.830.090.89 / 0.80
Qwen2.5-7B12881.3 [80.8, 81.8]10.27.41.00.910.970.630.850.090.89 / 0.81

Table 25. Per-model attention results (unified scoring). Label shares in % of (head, prompt) pairs: arrowhead with its 95% interval over prompts, block-k2, the other block masks and block+band together, bands and diagonal together. Agreement: mean per-head agreement with the head’s modal label over the 20 prompts, for all heads, for the heads whose modal label is arrowhead, and for the others. Confident: share of pairs whose margin over the runner-up exceeds 20%. Null: median ratio of the selected mask’s score to its score under random permutations. Scalars: leave-one-prompt-out accuracy of predicting the label from four scalar descriptors / majority baseline.

Figure 11. Share of the top-1 label per layer for the three models (columns) at n=512n=512 (top) and n=128n=128 (bottom), 20 prompts.

Figure 12. Per-head view at n=512n=512, one row per model: the modal label over the 20 prompts (left), the share of prompts carrying that label (middle) and the median relative margin of the selected mask over the runner-up (right).

Figure 13. Representative heads of each model at n=128n=128 (one passage per model), logarithmic colour scale: a block-labelled head (left pair) and an arrowhead head (right pair), each in the native token order and in the order found for the selected mask, mask outlined, with the density-normalized score. The block-labelled heads are wide local heads, fitted by the native order; the Qwen2.5-7B arrowhead head has its sink at a key other than the first token (identity score 1.02), which the reordering brings to the front.

Identity-Order Control and Long-Context Control

Are the permutations needed? Table 26 scores every (head, prompt) pair at n=512n=512 under three rules: the identity order only, the optimized order only (spectral start, no identity candidate), and the unified rule that keeps the identity as a candidate for every mask. The optimized score of a mask can be worse than its identity score, because the solver is started from the spectral start and not from the identity, and on causal attention the native order already is the band; comparing identity labels with optimized-only labels therefore counts label changes caused by competing masks getting worse. Under the unified rule only a few percent of the labels of GPT-2 and Qwen2.5-0.5B change, against about a fifth under the optimized-only rule. On Qwen2.5-7B the change is concentrated on particular passages: on 15 of the 20 passages at n=512n=512 (14 at n=128n=128) the native-order arrowhead share is 0.82 and 3–5% of the labels change, as on the smaller models; on the remaining passages, all of which begin with the token “The”, the sink is not the first token, the native-order arrowhead share is below 0.02, and 83–85% of the labels change. With reordering the arrowhead share is 0.77–0.83 on every Qwen2.5-7B passage. This is also why the interval over prompts of the Qwen2.5-7B label-change rate in Table 26 is wide. The last column checks the solver against the closed-form arrowhead optimum (Appendix § 11.§ 3).

Modelarrowhead sharelabels changed vs identity
identityoptimizedunifiedunified [CI]optimizedsolver = exact
GPT-20.700.700.693.5% [3, 4]19%99.9%
Qwen2.5-0.5B0.700.680.676.5% [6, 7]24%99.8%
Qwen2.5-7B0.610.800.8023.4% [8, 39]34%99.6%

Table 26. Identity-order control at n=512n=512, 20 prompts. Arrowhead share of the (head, prompt) labels under the identity order, under the optimized order only, and under the unified rule (identity kept as a candidate); share of labels that differ from the identity labels under the unified rule (95% interval over prompts) and under the optimized-only rule; share of pairs on which the solver’s arrowhead score is within 1% of the closed-form optimum.

Position subsampling does not transfer. A tempting shortcut for long contexts is to score a random subset of 128 of the 512 positions. The label obtained this way agrees with the full-length label for only 0.40 / 0.41 / 0.41 of (head, prompt) pairs (GPT-2 / Qwen2.5-0.5B / Qwen2.5-7B; 5 prompts, two draws each, unified scoring at the sub-length budget), and the per-head modal label over these draws agrees with the full-length one for about half of the heads, against 0.91–0.95 agreement of the per-head modal label between the contiguous n=128n=128 and n=512n=512 contexts. Non-contiguous subsampling destroys the band and block geometry; long contexts should be analysed on contiguous windows or with the scaling routes of Appendix § 13.8.

Wall-Clock Scaling of Alternating LAP

Planted banded instances in the Gaussian regime of § 5.1 (w=5w=5), one Fiedler-initialized run of the LAP phase with an iteration cap of 10, 3 seeds at every nn; the exchange phase is timed separately below. All times are single-thread wall-clock seconds (BLAS and the assignment solver pinned to one core) on an Apple M3 with 18 GB of memory; peak resident memory is the maximum over the three runs. Two noise series are reported: the per-entry noise fixed at σn=0.05\sigma_n=0.05 (the regime of Table 1), under which the band holds a 1/n1/n fraction of the energy and the error reduction of the planted order itself falls from 0.80 to 0.20; and the noise scaled as σn∝n−1/2\sigma_n \propto n^{-1/2}, which keeps the planted order’s error reduction at 0.80 for every nn. Table 27 gives the measurements.

nnFiedlerper iter.LAPstotalFAQmemoryAltLAPFAQAltLAPtime
5000.00.040.030.40.70.2 GB0.51 (0.80)0.570.51 (0.80)1.0
10000.10.140.101.54.70.4 GB0.44 (0.67)0.480.52 (0.80)1.6
20001.00.730.498.332.50.6 GB0.34 (0.50)0.380.55 (0.80)7.5
400010.95.43.1652491.3 GB0.24 (0.34)0.250.59 (0.80)46
8000105371847919363.2 GB0.15 (0.20)0.160.63 (0.80)334

Table 27. Wall-clock scaling of the LAP phase of one Alternating LAP run (single thread, Apple M3). Times in seconds; “LAPs” is the part of an iteration spent in the two assignment solves; ER is the error reduction of the solver and, in parentheses, of the planted order. FAQ: one run of QAP-FAQ on the same instances and objective. Means over 3 seeds (FAQ at n≥4000n \ge4000 and the fixed-SNR series at n=8000n=8000: one seed).

Cost. An iteration of the LAP phase is two O(n3)O(n^{3}) cost-matrix products and two assignment solves; the solves take three quarters of it at small nn and half at n=8000n=8000, and the iteration time decreases as the iterates converge (first and last iteration at n=8000n=8000: 78 s and 22 s), so the total grows by 4–8× per doubling of nn. The dense Fiedler start (a full eigendecomposition) becomes a fifth of the total at the largest size. Memory is a handful of dense n×nn \times n doubles. FAQ on the same objective costs 2–4× more and reaches a similar error reduction from one start.

Exchange phase. On the same instances, started from the output of the LAP phase above, the exchange descent of Appendix § 12.§ 1 takes 0.8–1.1 s at n=500n=500 (20–28 rounds), 6.4–7.6 s at n=1000n=1000 (32–39 rounds) and 24–48 s at n=2000n=2000 (25–48 rounds), and raises the error reduction by 0.07–0.08, 0.06–0.07 and 0.04–0.05. A round is dominated by the gain evaluation, two n×nn \times n products: 0.4 s at n=2000n=2000, 2.7 s at n=4000n=4000 and 20 s at n=8000n=8000 on this machine, so at the observed 25–50 rounds the phase would take a few minutes at n=4000n=4000 and of the order of 10–20 minutes at n=8000n=8000, comparable with the LAP phase; it was not run at these two sizes. On the same machine PatLR (rank 3, 12 iterations, 3 restarts) takes 3.0 s at n=200n=200, 22 s at n=500n=500 and 134 s at n=1000n=1000; Adaptive PatLR (N=80N=80, ℓ=3\ell=3, default vocabulary) 2.9 s at n=200n=200 and 31 s at n=500n=500, i.e. 1–1.4× the cost of one PatLR call. The benchmark panels and the attention scoring run as single-threaded processes on a 24-core AMD EPYC; scoring one 512×512512 \times512 attention head against the 9-mask vocabulary (8 iterations, 2 restarts per mask, plus the identity and five random permutations) takes about 12 core-seconds there, so the full grid of § 5.5 (1,264 heads × 20 prompts at n=512n=512, and again at n=128n=128) is about 85 core-hours (22 processes).

Scaling routes. On one M3 core a solve on a planted banded instance thus takes about two seconds at n=500n=500 and, for the LAP phase alone, minutes at n=8000n=8000 (Table 27), and a vocabulary scan of a single 8000-token matrix would take hours per head. The cost matrix is dense (a banded mask only makes it O(n2)O(n^2) to assemble), so the assignment solve is the bottleneck; sparse assignment with restricted candidates, coarsen-then-refine, and GPU Sinkhorn or auction solvers [17, 8] are left for future work.

Quality against nn. The iteration cap is not binding: with the cap raised to 30 the solver stops by its own convergence test after 9–12 iterations at n≤2000n \le2000 and the error reduction changes by less than 0.001. Under fixed per-entry noise the error reduction falls with nn because the attainable reduction falls: the solver reaches a stable two thirds to three quarters of the planted order’s value at every nn. With the matrix SNR held fixed the error reduction does not degrade with size; it rises slowly with nn. Under fixed per-entry noise the Fiedler start alone reduces the error by 0.1 at n=500n=500 and by less than 0.04 at n≥1000n \ge1000 (the Laplacian of ∣A∣|A| is dominated by the dense noise), so the reduction is produced by the LAP iterations.

NeurIPS Paper Checklist

  1. Claims

Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

Answer: [Yes]

Justification: Claims match § 2–5 and the appendices.

Guidelines:

  • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.

  • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.

  • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

  • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

  1. Limitations

Question: Does the paper discuss the limitations of the work performed by the authors?

Answer: [Yes]

Justification: § 6: cost, local optima, vocabulary scope, proxy objective, theory scope.

Guidelines:

  • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.

  • The authors are encouraged to create a separate “Limitations” section in their paper.

  • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

  • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

  • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

  • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

  • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

  • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not to penalize honesty concerning limitations.

  1. Theory assumptions and proofs

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

Answer: [Yes]

Justification: Full proofs in Appendices § 10–§ 11; assumptions stated with each result.

Guidelines:

  • The answer [N/A] means that the paper does not include theoretical results.

  • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

  • All assumptions should be clearly stated or referenced in the statement of any theorems.

  • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

  • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

  • Theorems and Lemmas that the proof relies upon should be properly referenced.

Experimental result reproducibility

Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

Answer: [Yes]

Justification: Setups, hyperparameters and seed counts per experiment (typically 20, exceptions stated) in Section 5 and Appendix E.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

  • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

  • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

  • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

Open access to data and code

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

Answer: [No]

Justification: No code release; Algorithms 1–3 fully specified; all data public.

Guidelines:

  • The answer [N/A] means that paper does not include experiments requiring code.

  • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

  • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

  • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

  • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

  • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

  • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

  • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

6. Experimental setting/details

Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?

Answer: [Yes]

Justification: Section 5 and Appendix E.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

  • The full details can be provided either with the code, in appendix, or as supplemental material.

7. Experiment statistical significance

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

Answer: [Yes]

Justification: 95% bootstrap intervals: over seeds (typically 20) for the benchmarks, over the 20 prompts for attention.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

  • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

  • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

  • The assumptions made should be given (e.g., Normally distributed errors).

  • It should be clear whether the error bar is the standard deviation or the standard error of the mean.

  • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

  • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).

  • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

8. Experiments compute resources

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

Answer: [Yes]

Justification: Attention extraction: one H100, about 2 hours. Benchmark panels and attention scoring: AMD EPYC, single-threaded processes, about 85 core-hours. Scaling study and PatLR timings: Apple M3 (Appendix E.8).

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

  • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

  • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).

Code of ethics

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

Answer: [Yes]

Justification: Conforms.

Guidelines:

  • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.

  • If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.

  • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).

Broader impacts

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

Answer: [N/A]

Justification: Foundational matrix analysis; no direct societal impact.

Guidelines:

  • The answer [N/A] means that there is no societal impact of the work performed.

  • If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.

  • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

  • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.

  • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.

  • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).

Safeguards

Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?

Answer: [N/A]

Justification: No such assets released.

Guidelines:

  • The answer [N/A] means that the paper poses no such risks.

  • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.

  • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.

  • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

Licenses for existing assets

Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

Answer: [Yes]

Justification: All assets public and cited; UCI CC BY 4.0, GPT-2 MIT, Qwen2.5 Apache 2.0, WikiText-2 CC BY-SA 3.0.

Guidelines:

  • The answer [N/A] means that the paper does not use existing assets.

  • The authors should cite the original paper that produced the code package or dataset.

  • The authors should state which version of the asset is used and, if possible, include a URL.

  • The name of the license (e.g., CC-BY 4.0) should be included for each asset.

  • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

  • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.

  • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

  • If this information is not available online, the authors are encouraged to reach out to the asset’s creators.

New assets

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

Answer: [N/A]

Justification: None released.

Guidelines:

  • The answer [N/A] means that the paper does not release new assets.

  • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

  • The paper should discuss whether and how consent was obtained from people whose asset is used.

  • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.

Crowdsourcing and research with human subjects

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

Answer: [N/A]

Justification: None.

Guidelines:

  • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.

  • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.

  • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.

Institutional review board (IRB) approvals or equivalent for research with human subjects

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

Answer: [N/A]

Justification: Not applicable.

Guidelines:

  • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.

  • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

  • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.

  • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.

Declaration of LLM usage

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.

Answer: [N/A]

Justification: LLMs are study subjects only.

Guidelines:

  • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.

  • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

References

  1. [1]Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1–86, 2018. URL http://jmlr.org/papers/v18/16-480.html.
  2. [2]Stefan Aeberhard and M. Forina. Wine. UCI Machine Learning Repository, 1992.
  3. [3]E. Alpaydin and C. Kaynak. Optical recognition of handwritten digits. UCI Machine Learning Repository, 1998.
  4. [4]Jonathan E. Atkins, Erik G. Boman, and Bruce Hendrickson. A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing, 28(1):297–310, 1998. doi: 10.1137/S0097539795285771.DOI
  5. [5]Cevdet Aykanat, Ali Pınar, and Ümit V. Çatalyürek. Permuting sparse rectangular matrices into block-diagonal form. SIAM Journal on Scientific Computing, 25(6):1860–1879, 2004.DOI
  6. [6]Stephen T. Barnard, Alex Pothen, and Horst Simon. A spectral algorithm for envelope reduction of sparse matrices. Numerical Linear Algebra with Applications, 2(4):317–334, 1995. doi: 10.1002/nla.1680020402.DOI
  7. [7]Annabell Berger and Berit Schreck. The isomorphic version of Brualdi’s and Sanderson’s nestedness. Algorithms, 10(3):74, 2017.DOI
  8. [8]Dimitri P. Bertsekas. The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1):105–123, 1988. doi: 10.1007/BF02186476.DOI
  9. [9]Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3):335–379, 1976.DOI
  10. [10]Richard A. Brualdi and James G. Sanderson. Nested species subsets, gaps, and discrepancy. Oecologia, 119(2):256–264, 1999.DOI
  11. [11]Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM, 58(3):1–37, 2011. doi: 10.1145/1970392.1970395.DOI
  12. [12]Eranda Çela. The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers, 1998.
  13. [13]Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019.arxiv.org/abs/1904.10509
  14. [14]Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? An analysis of BERT’s attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 276–286. Association for Computational Linguistics, 2019. doi: 10.18653/v1/W19-4828.
  15. [15]Antė Ćustić, Vladyslav Sokol, Abraham P. Punnen, and Binay Bhattacharya. The bilinear assignment problem: complexity and polynomially solvable special cases. Mathematical Programming, 166:185–205, 2017.
  16. [16]E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th ACM National Conference, pages 157–172, 1969. doi: 10.1145/800195.805928.DOI
  17. [17]Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, volume 26, 2013.
  18. [18]Allison Davis, Burleigh B. Gardner, and Mary R. Gardner. Deep South: A Social Anthropological Study of Caste and Class. University of Chicago Press, Chicago, 1941.
  19. [19]Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84:066106, 2011.DOI
  20. [20]Inderjit S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 269–274, 2001.DOI
  21. [21]Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d’Aspremont. Convex relaxations for permutation problems. In Advances in Neural Information Processing Systems, volume 26, 2013.arxiv.org/abs/1306.4805
  22. [22]Linton C. Freeman. Finding social groups: A meta-analysis of the Southern Women data. In Ronald Breiger, Kathleen Carley, and Philippa Pattison, editors, Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, pages 39–97. National Academies Press, Washington, DC, 2003. doi: 10.17226/10735.
  23. [23]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  24. [24]Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345–363, 1973. doi: 10.1137/0710032.DOI
  25. [25]Norman E. Gibbs, William G. Poole, and Paul K. Stockmeyer. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM Journal on Numerical Analysis, 13(2):236–250, 1976.DOI
  26. [26]Michelle Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002. doi: 10.1073/pnas.122653799.DOI
  27. [27]Boris Goldengorin and Dmitry Krushinsky. Linear assignment problems in combinatorial optimization. In Sergiy Butenko, Panos M. Pardalos, and Volodymyr Shylo, editors, Optimization Methods and Applications: In Honor of Ivan V. Sergienko’s 80th Birthday, volume 130 of Springer Optimization and Its Applications, pages 183–216. Springer, Cham, 2017. doi: 10.1007/978-3-319-68640-0_9.DOI
  28. [28]Bruce Hajek, Yihong Wu, and Jiaming Xu. Submatrix localization via message passing. Journal of Machine Learning Research, 18(186):1–52, 2018.
  29. [29]John A. Hartigan. Direct clustering of a data matrix. Journal of the American Statistical Association, 67(337):123–129, 1972.DOI
  30. [30]Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: first steps. Social Networks, 5(2):109–137, 1983. doi: 10.1016/0378-8733(83)90021-7.DOI
  31. [31]David G. Kendall. Seriation from abundance matrices. In F. R. Hodson, D. G. Kendall, and P. Täutu, editors, Mathematics in the Archaeological and Historical Sciences, pages 215–252. Edinburgh University Press, 1971.
  32. [32]Donald E. Knuth. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM Press / Addison-Wesley, New York, 1993.DOI
  33. [33]Tjalling C. Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica, 25(1):53–76, 1957. doi: 10.2307/1907742.DOI
  34. [34]Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.DOI
  35. [35]Eugene L. Lawler. The quadratic assignment problem. Management Science, 9(4):586–599, 1963.DOI
  36. [36]Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11:985–1042, 2010.
  37. [37]Ross M. McConnell. A certifying algorithm for the consecutive-ones property. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 768–777, 2004.DOI
  38. [38]Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with Gumbel-Sinkhorn networks. In International Conference on Learning Representations, 2018.arxiv.org/abs/1802.08665
  39. [39]Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017.arxiv.org/abs/1609.07843
  40. [40]M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577–8582, 2006. doi: 10.1073/pnas.0601602103.DOI
  41. [41]Jeff Pool and Chong Yu. Channel permutations for N:M sparsity. In Advances in Neural Information Processing Systems, volume 34, 2021.
  42. [42]Alex Pothen and Chin-Ju Fan. Computing the block triangular form of a sparse matrix. ACM Transactions on Mathematical Software, 16(4):303–324, 1990.DOI
  43. [43]Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic blockmodel. In Advances in Neural Information Processing Systems, volume 26, 2013.arxiv.org/abs/1309.4111
  44. [44]Qwen Team. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115, 2024.
  45. [45]Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAI, 2019.
  46. [46]Antoine Recanati, Thomas Kerdreux, and Alexandre d’Aspremont. Reconstructing latent orderings by spectral clustering. arXiv preprint arXiv:1807.07122, 2018.arxiv.org/abs/1807.07122
  47. [47]W. S. Robinson. A method for chronologically ordering archaeological deposits. American Antiquity, 16(4):293–301, 1951. doi: 10.2307/276978.DOI
  48. [48]M. Puck Rombach, Mason A. Porter, James H. Fowler, and Peter J. Mucha. Core-periphery structure in networks. SIAM Journal on Applied Mathematics, 74(1):167–190, 2014.
  49. [49]Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the Bethe Hessian. In Advances in Neural Information Processing Systems, volume 27, 2014.DOI
  50. [50]James B. Saxe. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM Journal on Algebraic and Discrete Methods, 1(4):363–369, 1980.DOI
  51. [51]Vladyslav Sokol, Anté Ćustić, Abraham P. Punnen, and Binay Bhattacharya. Bilinear assignment problem: Large neighborhoods and experimental analysis of algorithms. INFORMS Journal on Computing, 32(3):730–746, 2020. doi: 10.1287/ijoc.2019.0893.DOI
  52. [52]Jared Tanner, Andrew Thompson, and Simon Vary. Matrix rigidity and the ill-posedness of robust PCA and matrix completion. SIAM Journal on Mathematics of Data Science, 1(3):537–554, 2019.arxiv.org/abs/1811.05919
  53. [53]Vincent A. Traag, Ludo Waltman, and Nees Jan van Eck. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9:5233, 2019.DOI
  54. [54]Lieven Vandenberghe and Martin S. Andersen. Chordal graphs and semidefinite optimization. Foundations and Trends in Optimization, 1(4):241–433, 2015.
  55. [55]Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Louis J. Podrazik, Steven G. Kratzer, Eric T. Harley, Donniell E. Fishkind, R. Jacob Vogelstein, and Carey E. Priebe. Fast approximate quadratic programming for graph matching. PLOS ONE, 10(4):e0121002, 2015.DOI
  56. [56]Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5797–5808. Association for Computational Linguistics, 2019. doi: 10.18653/v1/P19-1580.DOI
  57. [57]Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007. doi: 10.1007/s11222-007-9033-z.
  58. [58]William Wolberg, Olvi Mangasarian, Nick Street, and W. Street. Breast cancer Wisconsin (diagnostic). UCI Machine Learning Repository, 1993.
  59. [59]Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2309.17453
  60. [60]Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452–473, 1977. doi: 10.1086/jar.33.4.3629752.DOI
  61. [61]Shuangfei Zhai, Tatiana Likhomanenko, Etai Littwin, Dan Busbridge, Jason Ramapuram, Yizhe Zhang, Jiatao Gu, and Joshua M. Susskind. Stabilizing transformer training by preventing attention entropy collapse. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of PMLR, pages 40770–40803, 2023.arxiv.org/abs/2303.06296
  62. [62]Tianyi Zhou and Dacheng Tao. GoDec: Randomized low-rank & sparse matrix decomposition in noisy case. In Proceedings of the 28th International Conference on Machine Learning (ICML), pages 33–40, 2011.

Paper details

vlnc:W_3bsna72y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents