NOTE-1335: Redko et al. — CO-Optimal Transport

Contribution

It defines an optimal transport problem between two matrices X ∈ ℝ^{n×d} and X′ ∈ ℝ^{n′×d′} that need not share rows, columns or sizes. It fits a sample coupling π^s and a feature coupling π^v together, under a cost that compares the entry X_{i,k} with X′_{j,l}. It proves that the value is a distance between datasets up to row and column permutations, that it lower- bounds Gromov–Wasserstein (GW) on symmetric matrices with equality in the squared-Euclidean case, and that its block coordinate descent then reduces to the known Frank–Wolfe solver for GW. Experiments on heterogeneous domain adaptation and co-clustering report the best accuracy among the baselines.

Key insight

GW compares two sets only through their within-set similarity matrices, so it can forget what the features were. COOT keeps the raw features and pays for that with a second unknown: it must also decide which feature corresponds to which. The invariances shrink accordingly. COOT is “not invariant neither to feature rotations nor to the change of signs” (pp. 5–6), so it cannot confuse a configuration with its mirror image as GW on distances can. But it is invariant to any simultaneous relabelling of rows and columns that leaves a matrix unchanged. Those joint symmetries are exactly what it cannot resolve.

Assumptions

• The problem (eq. 1, p. 2): min over π^s ∈ Π(w, w′), π^v ∈ Π(v, v′) of Σ_{i,j,k,l} L(X_{i,k}, X′{j,l}) π^s{i,j} π^v_{k,l}, with L a divergence between scalars, w, w′, v, v′ histograms on the rows and columns. “when no additional information is available about the data, all the weights’ vectors can be set as uniform” (p. 2).
• Entry-wise comparability. The cost compares X_{i,k} with X′_{j,l} directly, so entries of the two matrices must be on a common scale. That is a real assumption for response matrices from two populations.
• Proposition 1 (p. 4): L = |·|^p, p ≥ 1, n = n′, d = d′, uniform weights, for the identity of indiscernibles; the triangle inequality needs only that L satisfy one.
• Propositions 2–3 (p. 5): L = |·|², and for the equality, C and C′ are squared Euclidean distance matrices; COOT is then run with the same weights on rows and columns, COOT(C, C′, w, w′, w, w′).

Key results

• Bilinear program (pp. 3–4). COOT is “an indefinite Bilinear Program (BP) problem”, for which “there exists an optimal solution lying on extremal points” of the two polytopes. With equal sizes and uniform weights, Birkhoff’s theorem gives an optimal pair of permutations. “Even though solving COOT exactly may be NP-hard” (p. 4), via the bilinear assignment problem.
• Proposition 1 (p. 4; proof pp. 11–13). Under its hypotheses “COOT(X, X′) = 0 iff there exists a permutation of the samples σ1 ∈ Sn and of the features σ2 ∈ Sd, s.t, ∀i, k Xi,k = X′σ1(i),σ2(k)”. It is symmetric, and the triangle inequality is proved for general sizes and weights by gluing couplings.
• Proposition 2 (p. 5; Lemma 1, p. 14). For squared Euclidean C, C′, GW is a concave quadratic program with Hessian −4 XXᵀ ⊗_K X′X′ᵀ.
• Proposition 3 (p. 5; proof p. 15). For any symmetric C, C′, COOT(C, C′, w, w′, w, w′) ≤ GW(C, C′, w, w′). “The converse is also true under the hypothesis of Proposition 2. In this case, if (π∗s , π∗v ) is an optimal solution of (1), then both π∗s , π∗v are solutions of (3). Conversely, if π∗s is an optimal solution of (3), then (π∗s , π∗s ) is an optimal solution for (1).” The proof applies Konno’s theorem relating a concave QP to its bilinear form (Theorem 1, p. 13). I checked equality on five random pairs of 5-point squared-distance matrices (exact, by enumerating permutation pairs) and found strict inequality in three of five pairs of random symmetric non-Euclidean matrices.
• Algorithms (p. 4; pp. 15–16). Block coordinate descent alternates two exact OT problems and “is guaranteed to decrease the loss after each update and so to converge within a finite number of iterations”. In the squared-Euclidean case, setting π^s = π^v gives a DC algorithm that equals the Frank–Wolfe GW solver of LIT-1813, whose line search is always 1 (Algorithms 3–5).
• InvOT and election isomorphism (pp. 17–18). Proposition 4: under cosine similarities and a whitened X′, InvOT, COOT and GW share optimal couplings. §C.5 shows COOT solves the election-isomorphism distance of Faliszewski et al. up to scaling.
• Experiments (pp. 6–9; Tables 1–9). Semi-supervised HDA, Decaf to GoogleNet, n_t = 3: mean accuracy 89.47 against SGW’s 84.65 (Table 1). Unsupervised: 33.28 against CCA’s 13.66, KCCA’s 18.72 and EGW’s 11.42 (Table 2). At n_t = 5 COOT’s lead over SGW narrows to 91.03 against 89.21 and 94.53 against 94.26 (Tables 5, 6), and SGW wins several domain pairs. Co-clustering: lowest error on D1, D2 and D4, behind CCOT-GW on D3; the baselines’ numbers are copied from another paper (Table 3).

Claims

id	claim	strength	support
C1	With equal sizes, uniform weights and L = |·|^p, COOT is zero iff the matrices agree up to a row permutation and a column permutation	strong	Prop. 1, proof pp. 12–13; checked numerically
C2	COOT satisfies the triangle inequality when L does, for any sizes and weights	strong	Prop. 1, gluing proof pp. 11–12
C3	When n ≠ n′ or d ≠ d′, COOT is strictly positive	wrong	asserted p. 4 and p. 13; false: a matrix with two equal rows against one copy of that row costs 0
C4	COOT ≤ GW on symmetric matrices, with equal value and corresponding optimal plans for squared Euclidean distance matrices	strong	Prop. 3 via Konno’s theorem; checked by enumeration
C5	BCD decreases the objective monotonically and stops in finitely many steps	strong, but only to a block-wise optimum	p. 4, citing Horst and Tuy; in my check 12% of 200 random starts reached the global value
C6	COOT gives better HDA accuracy than CCA, KCCA, EGW and SGW	moderate	Tables 1, 2, 5–7; 20 samples per class, 10 random draws; the margin over SGW shrinks as labels grow
C7	COOT’s feature coupling recovers a meaningful spatial transformation between MNIST and USPS pixels	weak	Fig. 1, qualitative; 67% of sample mappings within class

Method

Algorithm 1 (p. 4): start from the product couplings; then repeatedly solve an OT problem for π^v with cost L(X, X′) ⊗ π^s, and one for π^s with cost L(X, X′) ⊗ π^v. Each step is an exact OT problem (network simplex) or, in the entropic version (eq. 2, p. 3), a Sinkhorn problem. For L = |·|² the cost tensor product costs O((n + n′)dd′ + n′²n) by the factorization of LIT-1797 (p. 4; §B.2, p. 13). The comments in Algorithm 1 are swapped: the step that computes π^v is labelled “OT problem on the samples” and the step that computes π^s “OT problem on the features” (p. 4).

Concepts

• Samples and features. Rows and columns of a data matrix (p. 2). Each carries its own histogram.
• Sample coupling π^s, feature coupling π^v. Couplings of rows with rows and of columns with columns. No coupling ever pairs a row with a column.
• Bilinear assignment problem (BAP). The same problem with π^s, π^v restricted to permutation matrices (p. 4).

Connections

• Gromov–Wasserstein. COOT contains GW as a lower bound and, for squared Euclidean inputs, as a special case (Prop. 3). The FGW solver of LIT-1813 is recovered as the symmetric BCD (pp. 15–16). The tensor factorization is LIT-1797’s Proposition 1.
• InvOT (Alvarez-Melis, Jegelka and Jaakkola 2019, LIT-1805): equal couplings under cosine similarity and whitening (Prop. 4, p. 17).
• Co-clustering by OT (Laclau et al. 2017): the CCOT and CCOT-GW baselines (Table 3).
• Election isomorphism (Faliszewski et al. 2019): a special case (§C.5).

Bearing on the record

• CASE-185, the correspondence arm: whether COOT’s joint plans are identifiable. No. The paper proves no uniqueness result for (π^s, π^v), and its Proposition 1 implies the limit. With R and R′ two utterance × probe matrices of equal shape and uniform weights, every pair (σ1, σ2) with R′{σ1(i),σ2(k)} = R{i,k} is a zero-cost, optimal pair. Take any optimal pair and compose it with a joint symmetry of R′ (permutations P of utterances and Q of probes with R′ = P R′ Qᵀ). The result costs exactly the same, because the objective depends on the plans only through the entries they pair. Such a symmetry need not exist for P or Q alone. In my check, the matrix with rows e₁, e₂, e₃ and (½, ½, ½) compared with itself has six optimal pairs, each permuting rows and columns together. Swapping two utterances alone costs 1/3. A 4 × 4 matrix with two communities of two utterances, each answering its own two probes, has 32 zero-cost pairs of 576. That is 4 within-block row swaps times 4 within-block column swaps times 2 for exchanging the communities’ utterances and probes together. That last factor is the exchange’s “utterances and probes can be swapped together at equal cost”, precisely: a community’s items and its probes move as a block. With noise of sd 0.05 the tie breaks, but the second-best pair costs only 5 × 10⁻⁴ more. So real data give near-ties, not uniqueness. The “Why this is here” wording, “utterances and probes can be swapped together”, should not be read as a row being matched with a column. COOT never does that. The swap is a joint relabelling within each side. Two more limits bear on the arm. The global optimum is NP-hard in general (p. 4), and BCD finds block-wise optima: only 12% of my random starts reached the global value. And the entry-wise cost presupposes that the two communities’ response scales are comparable, which is CASE-055’s measurement-invariance question.
• What COOT does identify that GW does not. Against GW on distances (THEORY-1133), COOT removes rotation and sign ambiguity (“contrary to GW, COOT is not invariant neither to feature rotations nor to the change of signs”, pp. 5–6). Its residual ambiguity is the joint permutation-symmetry group of the raw matrix. That group is usually smaller than the isometry group of the derived distance matrix (THEORY-1155).
• CLAIM-257 (change of cover). COOT does fit a probe correspondence rather than assume it, as the “Why this is here” says. But π^v is a coupling with fixed marginals v, v′. Every probe on each side must send and receive its full mass, so a question one side cannot decide cannot be left unmatched. A change of cover would be absorbed into the coupling, not reported separately as the claim asks. The paper’s note that “this procedure can be easily adapted … to include unbalanced OT problems” (p. 5) points to the needed variant, which it does not develop.
• CLAIM-098. The CASE’s outcome “anchored fused GW or co-optimal transport beating orthogonal maps” fits COOT’s structure. COOT’s maps are couplings, neither linear nor invertible in general (n ≠ n′).
• TERM-092. The “Why this is here” calls COOT TERM-092’s frontier “in fittable form”. Nothing in the paper bears on that reading, which is the exchange’s.
• Instruction for ML practice. The HDA and co-clustering results imply method recommendations; that part belongs to the Anthology of the SOTA, and the LIT carries anthology-candidate.

Limitations

• No uniqueness or stability result for the optimal couplings. The paper’s identifiability statement is only the zero case of Prop. 1.
• Proposition 1’s remark on unequal sizes is false. “If n ≠ n′, d ≠ d′ the COOT cost is always strictly positive as there exists a strictly positive element outside the diagonal” (p. 13; also p. 4). Duplicated rows give zero. X = (1 2; 1 2) with uniform w and X′ = (1 2) has the admissible plan π^s = (½, ½)ᵀ, π^v = I/2 with cost 0, which I computed. COOT is therefore a distance only up to such replications, not between datasets in general.
• Exact computation is NP-hard in general, and the BCD gives no global guarantee. The supplement’s §E reports variance over random initializations in the co-clustering task (p. 18).
• Small experiments. HDA uses 20 samples per class and 10 random draws. The co-clustering baselines are quoted from another paper, so the conditions may differ.
• Proposition 3’s equality needs squared Euclidean matrices. For other symmetric matrices it is a strict bound in general. In three of five of my random trials the exact COOT value was below the best GW value found over the coupling polytope by 40 restarts.

Open questions

• Under what conditions on R, R′ (for example, no nontrivial joint permutation symmetry and a gap condition) is the COOT plan unique and stable under noise? A perturbation bound would answer it.
• Does an unbalanced COOT leave unmatched exactly the probes that only one side can decide? That would make it a measurement of CLAIM-257’s change of cover.