Permutation Diagnostics for Cross-View Similarity

Why Permute Patient Labels?

Two omics views can each have strong internal structure and still agree across patients no more than would be expected from a chance matching. A cross-view similarity statistic, such as kernel alignment or a network-agreement score, summarizes the observed matching. A permutation diagnostic asks whether that statistic is unusually large relative to matchings that keep each view intact but disconnect their patient identities.

The key operation is to permute the patient labels in one view only. For a patient-indexed matrix, this means applying the same permutation to its rows and columns. The matrix’s within-view pattern is preserved; only the correspondence between its patients and those in the other view changes. This creates a reference distribution for the chosen statistic under a null of no patient-specific cross-view correspondence.

Definition: Let \(K^{(1)}\) and \(K^{(2)}\) be \(n \times n\) patient-indexed similarity matrices from two omics views. For a permutation matrix \(P\), the relabelled second-view matrix is \(P K^{(2)} P^\top\). If \(T\) measures cross-view agreement, the permutation reference consists of \(T(K^{(1)}, P K^{(2)} P^\top)\) over allowed permutations \(P\). For networks, replace the kernel matrices with patient-by-patient network similarity matrices.

The permutation null is about the matching of patients across views, not whether either view contains structure. Permuting the entries of a matrix independently would destroy that structure and answer a different question. Likewise, permuting rows without the corresponding columns would not simply relabel patients: it would alter the matrix’s meaning.

Statistic, Assumptions, and Test

Choose the statistic before examining its permutation results. For centered kernel matrices \(K_c^{(1)}\) and \(K_c^{(2)}\), a common choice is centered kernel alignment, the normalized Frobenius inner product. Here \(H=I-\mathbf{1}\mathbf{1}^\top/n\) is the centering matrix, \(K_c=HKH\), and \(\|A\|_F\) is the square root of the sum of squared entries of \(A\).

T_{\mathrm{align}} = \frac{\operatorname{tr}\!\left(K_c^{(1)}K_c^{(2)}\right)} {\|K_c^{(1)}\|_F\|K_c^{(2)}\|_F}

This statistic is dimensionless and larger values indicate greater alignment. A network statistic might instead be the correlation between the two vectors of corresponding off-diagonal edge weights, or a prespecified weighted agreement score. Because network edges share nodes, the edges are not independent observations; the permutation procedure must act on patient labels, not treat edges as independent replicates.

A one-sided test is appropriate when the scientific question, stated in advance, is whether agreement is greater than expected under random patient matching. Its hypotheses are \(H_0\): the patient correspondence between views is exchangeable under the null, and \(H_a\): the observed correspondence produces unusually large agreement. This is not a test that either view has no structure, nor does rejection establish a causal or biological mechanism.

Assumptions: Under \(H_0\), the patient labels in one view are exchangeable relative to the other view, so the allowed relabellings are equally plausible. Patients must be correctly matched in the observed data; each permutation must preserve the within-view matrix structure; and the statistic and analysis choices must be specified without selecting them to make the observed agreement look extreme. If exchangeability holds only within strata, permutations must be restricted to those strata. If observations are clustered or repeated within a patient, the permutation unit must preserve that dependence.

For all \(n!\) permutations, the exact upper-tail p-value is the fraction whose statistic is at least as large as the observed statistic. Ties are included, making the test conservative when the permutation distribution has ties. For \(B\) random permutations sampled from the non-identity permutations, let \(b\) be the number with statistic at least as large as observed. The usual Monte Carlo estimate is \((b+1)/(B+1)\); the added one accounts for the observed arrangement and prevents a zero estimate.

p_{\mathrm{exact}} = \frac{\#\{P:T_P \geq T_{\mathrm{obs}}\}}{n!} \qquad \widehat{p}_{\mathrm{MC}} = \frac{b+1}{B+1}

Worked Calculations

Worked Example: Exact Network Agreement With Three Patients

Hypothetical data. Three patients, A, B, and C, have edge weights in two omics networks. In the order AB, AC, BC, the first network has \(x=(3,1,0)\), and the second has \(y=(2,1,0)\). Use the Pearson correlation of the three edge weights as the agreement statistic, and test whether it is unusually high. Assume that, under the null, all six patient-label assignments in the second view are exchangeable.

The observed edge vectors are paired in their stated order. Their means are \(\bar{x}=4/3\) and \(\bar{y}=1\). The centered cross-product is \(3\), while the centered sums of squares are \(14/3\) and \(2\). Thus

T_{\mathrm{obs}} = \frac{(3-4/3)(2-1)+(1-4/3)(1-1)+(0-4/3)(0-1)} {\sqrt{(14/3)(2)}} = \frac{3}{\sqrt{28/3}} \approx 0.982

Relabelling the three patients in the second network induces six possible orders of its edge weights. The dot products with \(x\), in those six orders, are \(7,6,5,3,2,1\). For example, the first is \(3(2)+1(1)+0(0)=7\), and the second is \(3(2)+1(0)+0(1)=6\). The centered cross-product equals each raw dot product minus \((4)(3)/3=4\), so the six centered cross-products are \(3,2,1,-1,-2,-3\). The denominator remains \(\sqrt{28/3}\) for every permutation.

Only one of the six statistics is at least the observed value \(0.982\), giving \(p_{\mathrm{exact}}=1/6\approx0.167\). This small example does not provide evidence at the 0.05 level that the observed edge-weight correlation exceeds the permutation reference. The result is coarse because only six assignments are possible.

Worked Example: Permutation Alignment for Linear Kernels

Hypothetical data. For three matched patients, suppose centered one-dimensional measurements in two views are \(x=(1,0,-1)\) and \(y=(1,0,-1)\). Their linear kernels are \(K^{(1)}=xx^\top\) and \(K^{(2)}=yy^\top\), both positive semidefinite. Use normalized kernel alignment and enumerate all six patient permutations of the second view.

For rank-one kernels, the alignment after a permutation of \(y\) is \(\{x^\top(P y)\}^2/(\|x\|^2\|y\|^2)\). Both squared vector norms equal \(2\). The six possible relabelled vectors are \((1,0,-1)\), \((1,-1,0)\), \((0,1,-1)\), \((0,-1,1)\), \((-1,1,0)\), and \((-1,0,1)\). Their dot products with \(x\) are \(2,1,1,-1,-1,-2\), respectively. Therefore the six alignments are \(1,0.25,0.25,0.25,0.25,1\).

The observed alignment is \(1\). Two of six assignments attain this value, so \(p_{\mathrm{exact}}=2/6\approx0.333\). The second assignment ties the observed statistic even though it is a different patient matching. Counting that tie is required for the upper-tail p-value. A perfect observed alignment is not, by itself, proof of an exceptional alignment relative to the permutation reference.

Worked Example: Monte Carlo Calibration

Hypothetical data. A study has enough patients that exhaustive enumeration is impractical. Its observed, prespecified network-agreement statistic is \(T_{\mathrm{obs}}=0.42\). The analyst draws \(B=999\) random patient-label permutations in the second view; 18 produce a statistic at least \(0.42\). Assume the permutations respect any required exchangeability strata.

The Monte Carlo p-value is

\widehat{p}_{\mathrm{MC}} = \frac{18+1}{999+1} = \frac{19}{1000} = 0.019

At significance level \(\alpha=0.05\), this is evidence against the exchangeable-matching null in favor of greater agreement. It is not the probability that the null hypothesis is true. The estimate also has simulation error: a rough Monte Carlo standard error is \(\sqrt{0.019(1-0.019)/1000}\approx0.00432\). More permutations would improve numerical precision, but would not fix a poor permutation design or an invalid exchangeability assumption.

Why the Reference Distribution Is Valid

The exact calibration follows from the exchangeability assumption. Conditional on the two observed within-view structures, if every patient matching is equally plausible under \(H_0\), the observed matching has no privileged position among the \(n!\) assignments. Its statistic therefore has the same permutation distribution as a randomly selected assignment. The proportion of assignments with statistic at least as large as the observed one is an exact upper-tail p-value, with ties handled conservatively.

For a Monte Carlo test, the same logic applies to the sampled assignments. The observed arrangement is included through the added one in the numerator and denominator. This gives a valid finite-simulation test under uniform sampling from the allowed permutations; it also ensures \(\widehat{p}_{\mathrm{MC}}\) cannot be zero. The standard error describes simulation variability in the estimated tail probability, not uncertainty about the biological effect.

Centering does not invalidate simultaneous label permutation. Since \(H=I-\mathbf{1}\mathbf{1}^\top/n\) is unchanged by a relabelling in the sense that \(HP=PH\), centering a permuted matrix gives \(H(PKP^\top)H=P(HKH)P^\top\). Thus the centered structure is relabelled consistently. Any data-dependent operation that uses cross-view correspondence, however, must be repeated for each permutation if the goal is to calibrate the complete analysis procedure.

Diagnostics, Alternatives, and Limitations

Before interpreting a result, check that the permutation distribution represents the intended null. Inspect its range, center, and shape; confirm that the observed statistic is computed by exactly the same rule as each permuted statistic; and verify that each matrix remains symmetric and retains its original within-view entries under relabelling. For Monte Carlo tests, increase \(B\) when the estimated p-value is near the decision threshold or when its simulation error is too large for the intended conclusion. A handful of permutations cannot reliably resolve a small tail probability.

The main alternative is a parametric reference distribution, which can be faster but depends on a model for the statistic’s distribution and its dependence structure. Permutation calibration avoids specifying that distribution, but is valid only under the chosen exchangeability scheme. Another option is a prespecified null model that simulates new networks or kernels; that can address a different scientific null, but requires credible assumptions about how within-view structures arise. These approaches are not interchangeable: label permutation specifically tests whether patient correspondence is stronger than exchangeable matching, conditional on the observed views.

Approach	What it preserves or assumes	Key limitation
Patient-label permutation	Preserves each observed view’s internal matrix structure; requires exchangeable matching under the null.	Can be invalid if labels are not exchangeable or restrictions are ignored.
Parametric reference	Uses a specified probability model for the statistic or data.	Misspecification can distort tail probabilities.
Simulated structural null	Preserves features specified by a model for network or kernel generation.	Conclusions depend on whether that structural model is credible.

A significant result establishes unusually high agreement relative to the chosen permutation null, not that the views measure the same biology or that one view improves prediction. Shared batch effects, disease severity, age, or other covariates may produce cross-view agreement. If these factors make unrestricted patient labels nonexchangeable, use a scientifically justified restricted permutation scheme or state that the diagnostic is not calibrated for the desired conditional question. Similarly, arbitrary selection among many statistics, preprocessing choices, or tuning settings can make the reported p-value too small unless the selection process is accounted for.

Wrong: “The network edges are numerous, so I can treat them as independent and use an ordinary correlation test.” Correction: Edges share patients and are dependent; permute whole patient labels to preserve the network structure.
Wrong: “I shuffled individual matrix entries to create a more random null.” Correction: That destroys within-view structure. Apply the same patient permutation to rows and columns.
Wrong: “The p-value is the probability that the two views are unrelated.” Correction: It is the probability, under the specified exchangeable-matching null, of a statistic at least as large as observed.

Key takeaway: A permutation diagnostic is only as meaningful as its null and exchangeability assumptions. Preserve each view’s structure, permute patient correspondence as a unit, use a prespecified agreement statistic, and interpret the result relative to that precise null.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

Why must a patient permutation reorder both rows and columns of a similarity matrix?
If 9 of 499 random permutations are at least as extreme as the observed statistic, what is the Monte Carlo p-value using the plus-one formula?
What null is tested by permuting patient labels in one omics view?
Why can a high alignment still have a non-small permutation p-value?
What should be done if patient labels are exchangeable only within treatment strata?

Solutions. (1) Rows and columns jointly identify the patients on the two axes; reordering both preserves the same within-view relationships under new labels. (2) \((9+1)/(499+1)=10/500=0.020\). (3) The null is that patient correspondence across views is exchangeable, conditional on the preserved within-view structures and any permutation restrictions. (4) Other allowed matchings may produce similarly high alignment, so the observed value may not be unusual under the null. (5) Permute labels only within the treatment strata, provided that restricted scheme matches the scientific null and preserves the relevant dependence structure.