NVE: A Separability and Coverage-Aware Internal Validation Metric for Biclustering

# NVE: A Separability and Coverage-Aware Internal Validation Metric for Biclustering
Source: [https://arxiv.org/html/2608.29045](https://arxiv.org/html/2608.29045)
I Navin KumarJames C\. BezdekPunit Rathore††thanks:P\. Tiwari is with the Robert Bosch Center for Cyber\-Physical Systems \(RBCCPS\), Indian Institute of Science, Bengaluru, India \(e\-mail: paritosht@iisc\.ac\.in\)\. I\. Navin Kumar was with RBCCPS, Indian Institute of Science, Bengaluru, India, at the time of this work\. He is now with Cisco India††thanks:J\. C\. Bezdek is a Visiting Senior Research Fellow, University of Melbourne, Australia\.††thanks:P\. Rathore is an Assistant Professor with the Robert Bosch Centre for Cyber\-Physical Systems \(RBCCPS\) and the Centre for Infrastructure, Sustainable Transportation and Urban Planning \(CiSTUP\), Indian Institute of Science, Bengaluru, India\.

###### Abstract

Biclustering, or co\-clustering, aims to discover coherent submatrices by grouping rows and columns of a data matrix simultaneously\. This local two\-dimensional structure makes validation more difficult than in ordinary clustering, where internal indices usually rely on compactness and separation in a single shared feature space\. Existing popular internal biclustering measures such as Mean Squared Residue \(MSR\), and Virtual Error \(VE\) mainly evaluate within\-bicluster coherence\. Although useful, these measures do not directly assess whether the extracted biclusters are mutually distinct or whether they explain a meaningful portion of the data matrix\. This paper investigates Normalised Virtual Error \(NVE\), an internal validation metric that extends VE using a super\-bicluster normalization strategy\. By comparing the VE of each bicluster with the VE obtained after merging it with other biclusters, NVE introduces a relative notion of separability and redundancy\. We also study a coverage\-adjusted variant, NVEcov, which penalizes solutions that obtain low error by selecting only very small submatrices\. Through controlled synthetic benchmarks and yeast gene\-expression datasets, we examine whether NVE and NVEcovprovide information beyond standard coherence\-based metrics\. The results show that NVE is sensitive to redundant and poorly separated biclusters, while NVEcovchanges solution rankings when low\-error biclusters cover only a negligible part of the matrix\. These findings suggest that NVE\-based measures are useful complementary criteria for internal co\-clustering validation, especially when coherence, separability, and coverage must be considered jointly\.

###### Index Terms:

Biclustering, co\-clustering, internal validation, cluster validity, virtual error, normalized virtual error, mean squared residue, bicluster quality, gene expression analysis\.

## IIntroduction

Biclustering, also referred to as co\-clustering or two\-mode clustering, is used when meaningful structure is expected to appear in both dimensions of a rectangular data matrix\. Instead of assigning objects to clusters over the full feature space, biclustering searches for submatrices whose rows exhibit coherent behaviour over selected subsets of columns\. This formulation is natural in gene\-expression analysis, document\-word analysis, recommender systems, and other relational data settings, where a group of objects may be similar only under a limited set of conditions or attributes\. Foundational work such as Cheng and Church’s residue\-based biclustering model\[[1](https://arxiv.org/html/2608.29045#bib.bib1)\]and Dhillon’s bipartite spectral co\-clustering formulation\[[2](https://arxiv.org/html/2608.29045#bib.bib2)\]established biclustering/co\-clustering as a distinct problem rather than a direct extension of ordinary clustering\. Subsequent surveys have emphasized the diversity of bicluster types, search strategies, and validation criteria that arise from this local two\-dimensional structure\[[3](https://arxiv.org/html/2608.29045#bib.bib3),[4](https://arxiv.org/html/2608.29045#bib.bib4),[5](https://arxiv.org/html/2608.29045#bib.bib5)\]\.

The evaluation problem is correspondingly different from standard cluster validation\. In conventional clustering, many internal validity indices are built around compactness and separation in a single shared feature space\. A cluster is good if its points are close to one another and well separated from points in other clusters\. For a bicluster, this geometry is no longer sufficient\. A biclusterBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\)occupies only the submatrix induced by row setIkI\_\{k\}and column setJkJ\_\{k\}; two biclusters may overlap, use different column subsets, or express different coherence models\. As a result, a global distance between row clusters or a global variance decomposition does not directly measure whether the extracted submatrices are meaningful\. A useful internal validation measure for biclustering must therefore ask a more specific question:are the reported submatrices internally coherent, mutually non\-redundant, and large enough to explain a non\-trivial portion of the data matrix?

Most widely used internal biclustering measures address only the first part of this question\. The mean squared residue \(MSR\) introduced by Cheng and Church evaluates the fit of an additive row\-column model within a bicluster\[[1](https://arxiv.org/html/2608.29045#bib.bib1)\]\. This measure is useful, but its interpretation depends on the assumed coherence model\. Particularly, residue\-based scores may penalize scaling patterns that are structurally meaningful in applications such as gene\-expression analysis\. Virtual Error \(VE\) was introduced to address this limitation by comparing standardized row profiles with a virtual pattern representing the average behaviour of the bicluster\[[6](https://arxiv.org/html/2608.29045#bib.bib6)\]\. Comparative studies of bicluster quality measures show that such measures can respond quite differently to constant, shifting, scaling, and combined patterns\[[7](https://arxiv.org/html/2608.29045#bib.bib7)\]\. Thus, internal coherence is not a single universal property; it is tied to the pattern model that the measure is designed to capture\.

Even when a coherence measure is appropriate, evaluating each bicluster in isolation leaves two important gaps\. First, a collection of biclusters may contain redundant structures\. If two biclusters have nearly the same behavioural pattern, merging them may not substantially degrade coherence; a solution composed of such repeated patterns should not be judged as strongly as a solution containing distinct local structures\. Second, coherence\-only criteria can favour very small submatrices\. Small biclusters can appear extremely clean, sometimes for purely numerical or statistical reasons, while covering only a negligible fraction of the matrix\. External validation and benchmark\-based comparisons can address some of these issues when a reference solution is available\[[8](https://arxiv.org/html/2608.29045#bib.bib8),[9](https://arxiv.org/html/2608.29045#bib.bib9)\], and statistical significance methods provide another complementary view under a chosen null model\[[10](https://arxiv.org/html/2608.29045#bib.bib10),[11](https://arxiv.org/html/2608.29045#bib.bib11)\]\. However, many practical settings require an internal criterion that can be computed directly from the data matrix and the extracted biclusters, without ground truth labels or application\-specific annotations\.

This paper studies whether our proposed internal validation metric,Normalised Virtual Error\(NVE\), and its coverage\-aware variant provide such additional internal validation information\. The starting point is the observation that VE captures a behaviourally meaningful form of within\-bicluster consistency, but does not by itself compare a bicluster against the rest of the solution\. We therefore combine the VE coherence model with a super\-bicluster normalization idea related to the normalized squared residue framework of Lee et al\.\[[12](https://arxiv.org/html/2608.29045#bib.bib12)\]\. For a biclusterBkB\_\{k\}, NVE compares its VE with the VE obtained after merging it with alternative biclusters\. IfBkB\_\{k\}is genuinely distinct, these merged super\-biclusters should be less coherent; if it is redundant, the normalization exposes that lack of separation\. We further consider a coverage\-adjusted form, denoted NVEcov, which penalizes solutions that achieve low error by explaining only a very small portion of the matrix\.

The central question of the paper is therefore not whether NVE should replace all existing biclustering validation measures\. Rather, we ask whether NVE contributes information that is not already captured by standard coherence\-based measures such as MSR and VE\. This distinction is important\. A useful validation measure need not be universally best; it should make visible a property of the solution that would otherwise be hidden\. In the present case, the properties of interest are behavioural consistency, relative separability, and coverage\. These properties are related but not equivalent, and treating them as interchangeable can lead to different conclusions about which biclustering solution is preferable\.

The main contributions of this paper are as follows:

- •We formulate NVE as an internal, algorithm\-agnostic validation criterion that extends VE from an isolated bicluster coherence score to a solution\-level measure incorporating relative separability through super\-biclusters\.
- •We introduce a coverage\-adjusted variant, NVEcov, to reduce the tendency of coherence\-only measures to favour small, highly homogeneous biclusters with limited representativeness\.
- •We design controlled synthetic scenarios that isolate specific evaluation failure modes, including scaling behaviour, redundant or overlapping biclusters, small\-clean versus large\-noisy structures, thin\-column degeneracy, and coverage cherry\-picking\.
- •We compare MSR, VE, NVE, and NVEcovon both synthetic benchmarks and yeast gene\-expression datasets, examining whether the proposed measures alter solution ranking and model selection in practice\.

Overall, the paper positions NVE as a complementary internal validation measure for co\-clustering\. Its purpose is to make separability and representativeness visible alongside behavioural coherence, while retaining the pattern sensitivity that motivated VE\. The remainder of the paper introduces the necessary background, reviews related biclustering validation work, defines NVE and NVEcov, and evaluates their behaviour in controlled and real\-data experiments\.

## IIBackground

### II\-ABiclustering Overview

Biclustering, also referred to as co\-clustering in parts of the literature, aims to identify localized structure in a data matrix by selecting subsets of rows and columns simultaneously\. LetD~m×n\\widetilde\{D\}\_\{m\\times n\}denote the data matrix, where each elementd~i​j\\widetilde\{d\}\_\{ij\}represents the interaction between objectxi∈X=\{x1,x2,…,xm\}x\_\{i\}\\in X=\\\{x\_\{1\},x\_\{2\},\\ldots,x\_\{m\}\\\}and featureyj∈Y=\{y1,y2,…,yn\}y\_\{j\}\\in Y=\\\{y\_\{1\},y\_\{2\},\\ldots,y\_\{n\}\\\}\. The goal is to obtain a set ofKKbiclusters𝒪=\{\(Ok,Fk\)\}k=1K\\mathcal\{O\}=\\\{\(O\_\{k\},F\_\{k\}\)\\\}\_\{k=1\}^\{K\}, whereOk⊆XO\_\{k\}\\subseteq XandFk⊆YF\_\{k\}\\subseteq Ydefine subsets of rows and columns such that the corresponding submatrixBk=D~​\(Ok,Fk\)B\_\{k\}=\\widetilde\{D\}\(O\_\{k\},F\_\{k\}\)exhibits high internal coherence and interpretable structure\.

Each biclusterBkB\_\{k\}thus captures a subset of objects that show a coherent behavioural pattern across a subset of features\. This local two\-dimensional representation distinguishes biclustering from conventional clustering, which groups objects over the full feature space or partitions along a single axis\. Formally, the process can be viewed as finding a mapping

Φ:D~m×n↦\{B1,B2,…,BK\},\\Phi:\\widetilde\{D\}\_\{m\\times n\}\\mapsto\\\{B\_\{1\},B\_\{2\},\\ldots,B\_\{K\}\\\},such that intra\-bicluster similarity is maximized while while different biclusters remain meaningfully distinguishable\. Owing to this bidirectional structure, validation metrics for biclustering must account for dependencies between the row and column spaces, rather than evaluating each independently\.

Several methodological families of biclustering and co\-clustering algorithms have been developed, each reflecting different assumptions about the structure of the data matrix\. Cheng and Church\[[1](https://arxiv.org/html/2608.29045#bib.bib1)\]introduced a residue\-based formulation that searches for submatrices with low mean squared residue, while Dhillon\[[2](https://arxiv.org/html/2608.29045#bib.bib2)\]cast co\-clustering as bipartite spectral graph partitioning\. Large Average Submatrices \(LAS\)\[[13](https://arxiv.org/html/2608.29045#bib.bib13)\]instead adopts a statistical perspective, seeking submatrices whose average signal is unusually large relative to the background\. These approaches represent complementary residue\-based, graph\-theoretic, and statistical views of the same broad goal: recovering coherent local submatrices from high\-dimensional data\. The validation measures studied in this paper are algorithm\-agnostic and require only the data matrix and the final collection of biclusters\.

### II\-BBicluster Properties

Validation in biclustering is more involved than in ordinary clustering because a bicluster is defined jointly by a row subset and a column subset\. Thus, the quality of a bicluster cannot be judged only by compactness in a single feature space\. LetA∈ℝn×mA\\in\\mathbb\{R\}^\{n\\times m\}be the data matrix, and letBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\)denote a bicluster with row setIk⊆\{1,…,n\}I\_\{k\}\\subseteq\\\{1,\\dots,n\\\}and column setJk⊆\{1,…,m\}J\_\{k\}\\subseteq\\\{1,\\dots,m\\\}\. A useful validation measure should assess whether the induced submatrix is internally coherent, whether its pattern agrees with the intended bicluster model, and whether the collection of recovered biclusters is informative at the solution level\.

Several properties are therefore relevant when evaluating a biclustering solution\. First, a bicluster should exhibit strong internal coherence, commonly measured by residue\- or error\-based criteria such as MSR and VE\[[1](https://arxiv.org/html/2608.29045#bib.bib1),[6](https://arxiv.org/html/2608.29045#bib.bib6)\]\. Second, this coherence should correspond to an appropriate pattern model\. Depending on the application, meaningful biclusters may be constant, additive, multiplicative, order\-preserving, or combinations of these patterns\[[3](https://arxiv.org/html/2608.29045#bib.bib3),[7](https://arxiv.org/html/2608.29045#bib.bib7)\]\. Third, biclusters should have non\-trivial size and coverage: very small submatrices can appear highly coherent while explaining little of the data matrix\. Fourth, at the solution level, the recovered biclusters should not be excessively redundant\. Although overlap is natural in biclustering, repeated discovery of nearly identical row–column structures reduces interpretability and adds little new information\. Finally, statistical significance and robustness to noise or missing values are also desirable, but they typically require additional null\-model, perturbation, or application\-specific assumptions\[[11](https://arxiv.org/html/2608.29045#bib.bib11),[5](https://arxiv.org/html/2608.29045#bib.bib5)\]\.

This paper does not attempt to optimize all of these properties simultaneously\. Instead, they define the evaluation landscape in which Normalised Virtual Error is positioned\. The proposed metric family focuses on three internal dimensions that can be computed directly from the data matrix and the extracted biclusters: behavioural coherence through VE, relative distinctness through super\-bicluster comparison, and representativeness through union coverage\. In this sense, NVE and NVEcovare not intended to replace external validation, statistical significance analysis, or robustness studies\. Their role is narrower: to test whether separability and coverage expose information that standard coherence\-only summaries do not capture\.

### II\-CExisting Internal Validation Measures

#### II\-C1Mean Squared Residue \(MSR\)

MSR was introduced by Cheng and Church\[[1](https://arxiv.org/html/2608.29045#bib.bib1)\]and remains one of the most widely used internal measures of bicluster coherence\. For a biclusterBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\)extracted from a data matrixAA, MSR is defined as

MSR⁡\(Bk\)=1\|Ik\|​\|Jk\|​∑i∈Ik∑j∈Jk\(ai​j−ai​Jk−aIk​j\+aIk​Jk\)2,\\mathrm\{MSR\}\(B\_\{k\}\)=\\frac\{1\}\{\|I\_\{k\}\|\|J\_\{k\}\|\}\\sum\_\{i\\in I\_\{k\}\}\\sum\_\{j\\in J\_\{k\}\}\\left\(a\_\{ij\}\-a\_\{iJ\_\{k\}\}\-a\_\{I\_\{k\}j\}\+a\_\{I\_\{k\}J\_\{k\}\}\\right\)^\{2\},\(1\)whereai​ja\_\{ij\}denotes the entry of the data matrixAAin rowiiand columnjj, and

ai​Jk\\displaystyle a\_\{iJ\_\{k\}\}=1\|Jk\|∑j∈Jkai​j,aIk​j=1\|Ik\|∑i∈Ikai​j,\\displaystyle=\\frac\{1\}\{\|J\_\{k\}\|\}\\sum\_\{j\\in J\_\{k\}\}a\_\{ij\},\\qquad a\_\{I\_\{k\}j\}=\\frac\{1\}\{\|I\_\{k\}\|\}\\sum\_\{i\\in I\_\{k\}\}a\_\{ij\},\(2\)aIk​Jk\\displaystyle a\_\{I\_\{k\}J\_\{k\}\}=1\|Ik\|​\|Jk\|​∑i∈Ik∑j∈Jkai​j\.\\displaystyle=\\frac\{1\}\{\|I\_\{k\}\|\|J\_\{k\}\|\}\\sum\_\{i\\in I\_\{k\}\}\\sum\_\{j\\in J\_\{k\}\}a\_\{ij\}\.
Smaller MSR values indicate stronger fit to an additive row–column model\. For a biclustering solutionℬ=\{B1,…,BK\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{K\}\\\}, the average MSR, also called ASR, is

ASR⁡\(ℬ\)=1K​∑k=1KMSR⁡\(Bk\)\.\\mathrm\{ASR\}\(\\mathcal\{B\}\)=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\mathrm\{MSR\}\(B\_\{k\}\)\.\(3\)
Although MSR is useful and widely adopted, it evaluates only within\-bicluster additive coherence\. It can therefore penalize meaningful shifting or scaling patterns and does not account for bicluster size, redundancy, or coverage\[[6](https://arxiv.org/html/2608.29045#bib.bib6),[5](https://arxiv.org/html/2608.29045#bib.bib5)\]\. These limitations motivate the use of complementary measures such as VE, NVE, and NVEcov\.

#### II\-C2Virtual Error \(VE\)

VE was introduced by Divinaet al\.and was proposed to address some of the known limitations of MSR as a bicluster quality measure\[[6](https://arxiv.org/html/2608.29045#bib.bib6)\]\. In particular, VE is designed to evaluate the consistency of the overall behaviour of the rows in a bicluster with respect to a representativevirtual pattern, making it more suitable for pattern\-based biclusters\.

For a biclusterBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\), the virtual pattern is defined over the selected columns and is given by

rj=1\|Ik\|​∑i∈Ikbi​j,j∈Jk,r\_\{j\}=\\frac\{1\}\{\|I\_\{k\}\|\}\\sum\_\{i\\in I\_\{k\}\}b\_\{ij\},\\qquad j\\in J\_\{k\},\(4\)wherebi​jb\_\{ij\}denotes the entry of the bicluster submatrix at rowiiand columnjj\. Thus, the virtual pattern summarizes the common trend of the bicluster across its columns\.

To focus on behaviour rather than absolute magnitude, both the row profiles of the bicluster and the virtual pattern are standardized before comparison\[[14](https://arxiv.org/html/2608.29045#bib.bib14)\]\. Letb^i​j\\hat\{b\}\_\{ij\}denote the standardized value of entrybi​jb\_\{ij\}and letr^j\\hat\{r\}\_\{j\}denote the standardized value of the corresponding component of the virtual pattern\. The VE of biclusterBkB\_\{k\}is then defined as

VE⁡\(Bk\)=1\|Ik\|​\|Jk\|​∑i∈Ik∑j∈Jk\|b^i​j−r^j\|\.\\mathrm\{VE\}\(B\_\{k\}\)=\\frac\{1\}\{\|I\_\{k\}\|\|J\_\{k\}\|\}\\sum\_\{i\\in I\_\{k\}\}\\sum\_\{j\\in J\_\{k\}\}\\left\|\\hat\{b\}\_\{ij\}\-\\hat\{r\}\_\{j\}\\right\|\.\(5\)
Similar to Equation[3](https://arxiv.org/html/2608.29045#S2.E3), we can report the average VE across all discovered biclusters for a biclustering solution:

AvgVE⁡\(ℬ\)=1K​∑k=1KVE⁡\(Bk\)\.\\mathrm\{AvgVE\}\(\\mathcal\{B\}\)=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\mathrm\{VE\}\(B\_\{k\}\)\.\(6\)
Lower VE values indicate that the rows in the bicluster follow a common standardized pattern more closely\. For this reason, VE is better suited than MSR for assessing biclusters that exhibit coherent behavioural trends, including shifting and scaling patterns\[[6](https://arxiv.org/html/2608.29045#bib.bib6)\]\. However, VE remains an internal within\-bicluster coherence measure\. It evaluates how well the entries of a bicluster agree with their virtual pattern, but it does not directly account for between\-bicluster distinctness, overlap, or redundancy within the full biclustering solution\.

#### II\-C3Normalised Squared Residue \(NSR\)

NSR, proposed by Leeet al\.\[[12](https://arxiv.org/html/2608.29045#bib.bib12)\], extends MSR by incorporating a relative notion of distinctness between biclusters\. Instead of evaluating each bicluster only in isolation, NSR compares its internal coherence with the coherence of a largersuper biclusterformed by merging it with another bicluster\.

Let a biclustering solution beℬ=\{B1,…,BK\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{K\}\\\}, where each bicluster is written asBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\)\. For two biclustersBkB\_\{k\}andBℓB\_\{\\ell\}, their super bicluster is defined as

Bk​ℓ=\(Ik∪Iℓ,Jk∪Jℓ\)\.B\_\{k\\ell\}=\(I\_\{k\}\\cup I\_\{\\ell\},\\;J\_\{k\}\\cup J\_\{\\ell\}\)\.\(7\)The quantityMSR⁡\(Bk​ℓ\)\\mathrm\{MSR\}\(B\_\{k\\ell\}\), as computed in Eq\. \([1](https://arxiv.org/html/2608.29045#S2.E1)\), then measures the residue of the merged structure\. If two biclusters are genuinely distinct, their merger is expected to be less coherent, leading to a larger MSR\.

A solution\-level form of NSR can therefore be written as

NSR⁡\(ℬ\)=∑k=1KMSR⁡\(Bk\)∑k=1Kminℓ≠k⁡MSR⁡\(Bk​ℓ\)\.\\mathrm\{NSR\}\(\\mathcal\{B\}\)=\\frac\{\\sum\_\{k=1\}^\{K\}\\mathrm\{MSR\}\(B\_\{k\}\)\}\{\\sum\_\{k=1\}^\{K\}\\min\_\{\\ell\\neq k\}\\mathrm\{MSR\}\(B\_\{k\\ell\}\)\}\.\(8\)Lower values indicate better quality, since they reflect low within\-bicluster residue together with a stronger degradation of coherence when biclusters are merged with their closest counterparts\. Thus, unlike MSR, NSR attempts to assess not only internal homogeneity but also the relative distinctness of biclusters\. However, because it is still built on MSR, it inherits MSR’s limitations in handling broader pattern\-based structures, particularly shifting and scaling relationships\[[6](https://arxiv.org/html/2608.29045#bib.bib6)\]\.

### II\-DRelated Work

The preceding sections define the biclustering setting and the internal measures used in this study\. We therefore use the related work mainly to delimit the evaluation question addressed here\. The residue\-based model of Cheng and Church and the bipartite spectral formulation of Dhillon remain two canonical starting points for biclustering and co\-clustering, while the survey of Madeira and Oliveira organized the field in terms of bicluster types, algorithmic strategies, and evaluation criteria\[[1](https://arxiv.org/html/2608.29045#bib.bib1),[2](https://arxiv.org/html/2608.29045#bib.bib2),[3](https://arxiv.org/html/2608.29045#bib.bib3)\]\. More recent surveys make the same distinction explicit: biclustering evaluation includes internal quality, external recovery, statistical significance, visualization, and application\-dependent validation, and these should not be treated as interchangeable objectives\[[4](https://arxiv.org/html/2608.29045#bib.bib4),[5](https://arxiv.org/html/2608.29045#bib.bib5)\]\.

Prior work on internal validity measures shows why the choice of coherence model matters\. Aguilar\-Ruiz formalized shifting and scaling patterns as meaningful structures in gene\-expression data\[[15](https://arxiv.org/html/2608.29045#bib.bib15)\], and Divina et al\. proposed Virtual Error \(VE\) to evaluate standardized behavioural consistency rather than only additive residue\[[6](https://arxiv.org/html/2608.29045#bib.bib6)\]\. Pontes et al\. compared a broad family of bicluster quality measures and showed that different indices respond differently to constant, shifting, scaling, and combined patterns\[[7](https://arxiv.org/html/2608.29045#bib.bib7)\]\. These results are central to the motivation of the present paper: MSR/ASR and VE/AvgVE are informative reference axes, but they do not by themselves measure whether the biclusters in a full solution are mutually distinct or whether the solution covers a meaningful part of the matrix\.

External validation and benchmark\-based comparisons address a different problem\. Prelic et al\. proposed an influential experimental framework combining synthetic recovery and biological validation\[[8](https://arxiv.org/html/2608.29045#bib.bib8)\], while Eren et al\. emphasized that comparisons based on a single planted model can be misleading because algorithms optimize different bicluster models\[[16](https://arxiv.org/html/2608.29045#bib.bib16)\]\. Horta and Campello studied desirable properties of external similarity measures for comparing biclustering solutions\[[17](https://arxiv.org/html/2608.29045#bib.bib17)\], and Padilha and Campello extended this direction in a large comparative evaluation using synthetic and biological evidence\[[9](https://arxiv.org/html/2608.29045#bib.bib9)\]\. Benchmark generators such as G\-Bic further support controlled assessment under varied coherence, overlap, and noise conditions\[[18](https://arxiv.org/html/2608.29045#bib.bib18)\]\. These studies are relevant to experimental design, but their validation setting is not the same as ours: external measures require a planted or reference solution, whereas NVE is intended for internal comparison when only the data matrix and the extracted biclusters are available\.

Statistical significance provides another complementary view\. Early graph\-theoretic approaches searched for biclusters unlikely to arise under a random model, and BSig later evaluated the statistical significance of biclustering solutions under different coherence assumptions\[[10](https://arxiv.org/html/2608.29045#bib.bib10),[11](https://arxiv.org/html/2608.29045#bib.bib11)\]\. Pattern mining\-based biclustering also makes the relation between coherence assumptions, search constraints, and quality criteria explicit\[[19](https://arxiv.org/html/2608.29045#bib.bib19)\]\. Such methods are important because small coherent biclusters can occur by chance in high\-dimensional data\. However, significance testing depends on a specified null model and does not directly provide the simple solution\-level comparison targeted here, namely a deterministic score combining behavioural coherence, relative separability, and coverage\.

The closest prior internal criterion is the normalized squared residue \(NSR\) framework of Lee et al\.\[[12](https://arxiv.org/html/2608.29045#bib.bib12)\]\. NSR uses a super\-bicluster comparison idea: if two biclusters represent distinct structures, merging them should degrade coherence\. NVE keeps this solution\-level normalization principle but replaces the additive\-residue model with the VE behavioural model\. The coverage\-adjusted variant then adds an explicit representativeness term so that a solution formed from very small, clean biclusters is not automatically preferred over a broader, moderately noisy solution\. Thus, the contribution of NVE is not to replace external validation, significance analysis, or all existing internal indices\. Its narrower role is to test whether VE\-based coherence, super\-bicluster separability, and union coverage expose information that standard coherence summaries do not capture\.

## IIINormalised Virtual Error

The internal validation measures reviewed above capture different aspects of bicluster quality, but none of them provides a complete assessment on its own\. In particular, standard coherence measures such as MSR and VE focus on the internal consistency of each bicluster, but they do not directly reward the recovery of larger and more informative submatrices\. As a result, relying on coherence alone can bias evaluation toward small biclusters, even when larger biclusters reveal broader and more useful structure in the data\. In biclustering, this is an important limitation, since a good solution should ideally balance internal coherence with non\-trivial size\.

A second limitation is that most internal measures evaluate biclusters in isolation\. Among the measures discussed earlier, only NSR incorporates a relative notion of distinctness by comparing a bicluster with merged alternatives\. This is useful because a high\-quality biclustering solution should contain biclusters that are not only internally coherent, but also meaningfully distinguishable from one another\. If merging two biclusters substantially degrades their coherence, this suggests that they represent separate structures rather than redundant variations of the same pattern\.

To address these limitations, we propose the*Normalised Virtual Error*\(NVE\), which extends VE in two ways\. First, it incorporates a normalization strategy inspired by NSR, so that the coherence of each bicluster is assessed relative to the coherence of merged alternatives\. Second, it can be coupled with an explicit size or coverage factor to account for the area of the matrix captured by the bicluster\. In this way, NVE is intended as an algorithm\-agnostic internal evaluation measure for biclustering and co\-clustering solutions\.

### III\-ANVE Definition

Letℬ=\{B1,…,BK\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{K\}\\\}be a biclustering solution on a data matrixA∈ℝn×mA\\in\\mathbb\{R\}^\{n\\times m\}, where each bicluster is written asBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\)with row index setIkI\_\{k\}and column index setJkJ\_\{k\}\. For two biclustersBkB\_\{k\}andBjB\_\{j\}, define the corresponding super bicluster asBk​j=\(Ik∪Ij,Jk∪Jj\)B\_\{kj\}=\(I\_\{k\}\\cup I\_\{j\},\\;J\_\{k\}\\cup J\_\{j\}\)\.

Using the Virtual ErrorVE⁡\(Bk\)\\mathrm\{VE\}\(B\_\{k\}\)of each, as in Eq\. \([5](https://arxiv.org/html/2608.29045#S2.E5)\), we first define the normalized contribution ofBkB\_\{k\}as

NVEk=VE⁡\(Bk\)minj≠k⁡VE⁡\(Bk​j\)\.\\mathrm\{NVE\}\_\{k\}=\\frac\{\\mathrm\{VE\}\(B\_\{k\}\)\}\{\\min\_\{j\\neq k\}\\mathrm\{VE\}\(B\_\{kj\}\)\}\.\(9\)The denominator comparesBkB\_\{k\}against the most coherent super bicluster obtained by merging it with another bicluster\. WhenBkB\_\{k\}is genuinely distinct, merging it with any other bicluster is expected to increase the virtual error, leading to a small normalized ratio\.

The overall NVE of the biclustering solution is then defined as

NVE⁡\(ℬ\)=∑k=1KVE⁡\(Bk\)∑k=1Kminj≠k⁡VE⁡\(Bk​j\)\.\\mathrm\{NVE\}\(\\mathcal\{B\}\)=\\frac\{\\sum\_\{k=1\}^\{K\}\\mathrm\{VE\}\(B\_\{k\}\)\}\{\\sum\_\{k=1\}^\{K\}\\min\_\{j\\neq k\}\\mathrm\{VE\}\(B\_\{kj\}\)\}\.\(10\)Lower values ofNVE⁡\(ℬ\)\\mathrm\{NVE\}\(\\mathcal\{B\}\)indicate better solutions, as they correspond to biclusters that are internally pattern\-consistent while remaining relatively distinct from their merged alternatives\.

In this form, NVE remains a general internal validation measure: it does not depend on how the biclusters were generated, and it can therefore be applied to the outputs of different biclustering or co\-clustering algorithms in a uniform way\.

### III\-BCoverage\-adjusted Normalised Virtual Error\.

The vanilla Normalised Virtual Error \(NVE\) evaluates a biclustering solution by combining within\-bicluster behavioural coherence, captured through VE, with a normalization term based on super\-biclusters\. In this way, NVE reflects both internal pattern consistency and a relative notion of distinctness\. However, vanilla NVE does not explicitly reward the size or representativeness of the extracted biclusters\. Consequently, a solution made up of a few very small but internally coherent biclusters may still obtain a favorable score even when it explains only a negligible fraction of the data matrix\. This is an important limitation in biclustering, where the size, overlap, and overall coverage of the recovered biclusters are widely recognized as relevant structural aspects of a solution\[[5](https://arxiv.org/html/2608.29045#bib.bib5),[20](https://arxiv.org/html/2608.29045#bib.bib20),[21](https://arxiv.org/html/2608.29045#bib.bib21)\]\.

To address this limitation, we introduce a coverage\-adjusted variant of NVE, denoted byNVEcov\\mathrm\{NVE\}\_\{\\mathrm\{cov\}\}, defined as

NVEcov​\(ℬ\)=NVE⁡\(ℬ\)\(CR⁡\(ℬ\)\+ϵ\)1/2,\\mathrm\{NVE\}\_\{\\mathrm\{cov\}\}\(\\mathcal\{B\}\)=\\frac\{\\mathrm\{NVE\}\(\\mathcal\{B\}\)\}\{\\left\(\\mathrm\{CR\}\(\\mathcal\{B\}\)\+\\epsilon\\right\)^\{1/2\}\},\(11\)whereℬ=\{B1,…,BK\}\\mathcal\{B\}=\\\{B\_\{1\},\\ldots,B\_\{K\}\\\}is the set of extracted biclusters,NVE⁡\(ℬ\)\\mathrm\{NVE\}\(\\mathcal\{B\}\)is the vanilla NVE score,CR⁡\(ℬ\)∈\[0,1\]\\mathrm\{CR\}\(\\mathcal\{B\}\)\\in\[0,1\]is the coverage ratio of the solution, andϵ\>0\\epsilon\>0is a small numerical constant introduced for stability\. The coverage ratio is defined as

Ω⁡\(Bk\)=Ik×Jk,CR⁡\(ℬ\)=\|⋃k=1KΩ⁡\(Bk\)\|n​m\.\\Omega\(B\_\{k\}\)=I\_\{k\}\\times J\_\{k\},\\qquad\\mathrm\{CR\}\(\\mathcal\{B\}\)=\\frac\{\\left\|\\bigcup\_\{k=1\}^\{K\}\\Omega\(B\_\{k\}\)\\right\|\}\{nm\}\.\(12\)Here,Ω⁡\(Bk\)\\Omega\(B\_\{k\}\)denotes the set of matrix positions covered by biclusterBk=\(Ik,Jk\)B\_\{k\}=\(I\_\{k\},J\_\{k\}\)\. Thus,⋃k=1KΩ⁡\(Bk\)\\bigcup\_\{k=1\}^\{K\}\\Omega\(B\_\{k\}\)is the set of distinct entries covered by at least one bicluster in the solution, andn​mnmis the total number of entries in the data matrixA∈ℝn×mA\\in\\mathbb\{R\}^\{n\\times m\}\.

The proposed adjustment preserves the original interpretation of NVE as a minimization criterion, while introducing a global representativeness term at the solution level\. When the union coverage is small, the denominator in Eq\. \([11](https://arxiv.org/html/2608.29045#S3.E11)\) decreases and the score is penalized accordingly\. Conversely, among solutions with comparable NVE values, those covering a larger fraction of the matrix receive a lower NVEcovscore\. The exponent1/21/2provides a moderate adjustment, so that coverage complements rather than overwhelms the coherence and distinctness information already captured by vanilla NVE\.

An important advantage of definingCR⁡\(ℬ\)\\mathrm\{CR\}\(\\mathcal\{B\}\)through the union of covered matrix entries, rather than through the mean bicluster area ratio, is that the coverage ratio measures the effective portion of the matrix explained by the full solution\. As a result, heavily overlapping biclusters do not receive artificial credit for repeatedly covering the same entries\. This is especially desirable because overlap and coverage are recognized as distinct structural dimensions of biclustering solutions, and excessive overlap can reduce the interpretability of the recovered patterns\[[20](https://arxiv.org/html/2608.29045#bib.bib20),[21](https://arxiv.org/html/2608.29045#bib.bib21)\]\. In this sense, NVEcovcomplements vanilla NVE by adding a global representativeness criterion: while NVE evaluates coherence and relative distinctness, NVEcovadditionally evaluates whether the extracted biclusters account for a meaningful portion of the data matrix\.

## IVExperiments and Results

This section examines whether Normalised Virtual Error \(NVE\) and its coverage\-aware variant, NVEcov, provide useful evaluation information that is not already captured by existing biclustering metrics\. In particular, we want to see whether NVE adds information about how well biclusters are separated from one another beyond what coherence\-based measures such as ASR and VE can show\. We also want to test whether NVEcovadds a meaningful notion of coverage, so that solutions made up of very small but clean biclusters are not always preferred over solutions that explain a larger part of the data\. To study these questions, we first use controlled synthetic datasets where the planted structure is known, and then we use real yeast benchmark datasets to see how metric choice affects the ranking and selection of biclustering solutions in practice\.

### IV\-ASynthetic Benchmark Datasets

![Refer to caption](https://arxiv.org/html/2608.29045v1/synthetic_biclusters_s1_s7.png)Figure 1:Heatmaps of two synthetic data matrices from Table[I](https://arxiv.org/html/2608.29045#S4.T1); rows are permuted so the four planted biclustersB1B\_\{1\}–B4B\_\{4\}stack at the top \(matrix values unchanged\)\. Black rectangles mark each bicluster’s row\-band and column support\. In S1 the blocks have distinct column supports and distinct patterns \(NVE≪1\\ll 1\); in S7 they share the same columns and the same pattern, differing only in per\-row shifts, so any pairwise merge reproduces the pattern and NVE→1\\to 1even though ASR and VE rate each block individually as good\.To isolate the information captured by MSR, VE, NVE, and NVEcov, we constructed ten controlled synthetic datasets, each represented by a300×40300\\times 40matrix with planted biclusters over a Gaussian background\. The dimensions were chosen to be biologically plausible while keeping column overlap non\-trivial and computation manageable\. Unless overlap is part of the intended stress test, planted biclusters are non\-overlapping in the row–column subspace\. Table[I](https://arxiv.org/html/2608.29045#S4.T1)summarises the scenarios and the metric tension each one is designed to expose\.

The scenarios are grouped around four diagnostic questions\. S1–S3 examine coherence\-model dependence: S1 is an additive baseline where MSR, VE, NVE, and NVEcovshould largely agree; S2 introduces pure scaling, where MSR is expected to penalise a pattern that VE can still regard as coherent; and S3 combines shifting and scaling with mixed\-sign patterns, making both residue and virtual\-error coherence more difficult while preserving separability\. S5 and S7 focus on redundancy and separation\. In S5, overlapping biclusters generated from the same underlying pattern should remain favourable under within\-bicluster scores but become less attractive under NVE, while S7 is an extreme clone case in which individually coherent biclusters carry little separable information; Fig\.[1](https://arxiv.org/html/2608.29045#S4.F1)illustrates this contrast\. S4, S9a, and S9b test the coverage–coherence trade\-off: small clean biclusters can obtain low error, but NVEcovshould favour broader solutions when they explain a more meaningful portion of the matrix\. Finally, S6 and S8 are diagnostic stress tests\. S6 exposes the thin\-column degeneracy of VE\-based quantities, motivating minimum\-size checks, whereas S8 provides a progressive noise ladder for assessing whether metric values respond monotonically to controlled degradation\.

This design makes the synthetic benchmark more than a collection of artificial examples\. Each scenario creates a known structural condition under which two or more metrics are expected to agree or disagree\. The resulting comparisons therefore test whether NVE and NVEcovadd separability and coverage information beyond standard within\-bicluster coherence\.

Table I:Summary of synthetic benchmark scenarios\.KKdenotes the number of planted biclusters\. The “Stress test” column names the metric property or inter\-metric tension each scenario is designed to probe\.IDNameKKSignal typeStress testS1Additive4Pure additive, low noiseBaseline agreement; NVE≪1\\ll 1S2Scaling4All\-positive scalingMSR high, VE≈0\\approx 0; MSR–VE disagreementS3Mixed shift\-scale4Shift \+ scale, mixed\-signBoth MSR and VE degrade; NVE separability persistsS4Size vs\. quality4Additive \(2 clean, 2 noisy\)Coverage–coherence trade\-off; NVEcovsensitivityS5Overlap4Additive, equal signalRedundancy detection; MSR/VE blind, NVE sensitiveS6Thin columns4Additive \+ constant stripesVE degeneracy; minimum\-size filter necessityS7Identical clones4Same pattern, shared columnsZero separability; NVE→1\\to 1despite low MSR/VES8Noise ladder5Additive,σ\\sigmaincreasingMetric calibration vs\. controlled quality gradientS9aCoverage tiling8Additive, moderate noiseNVEcovrewards broad coverageS9bCoverage cherry\-pick3Additive, near\-perfectNVEcovpenalises negligible coverage

### IV\-BReal Datasets

We also evaluate the proposed measures on twoSaccharomyces cerevisiaegene\-expression benchmarks that have been used repeatedly in the biclustering literature: thealpha\_factorexperiment derived from theSpellman et al\.cell\-cycle dataset, and theheat\_shock\_1experiment derived from theGasch et al\.environmental stress\-response dataset\. Thealpha\_factordata capture transcriptional activity across cell\-cycle conditions and are known to contain localized groups of genes with coordinated temporal behaviour, whereasheat\_shock\_1reflects the yeast transcriptional response under heat stress and exhibits condition\-specific local co\-expression patterns\. These datasets are complementary: the former emphasizes structured periodic regulation, while the latter reflects stress\-induced local responses\. Their continued use in prior biclustering studies makes them suitable test beds for examining whether internal validity measures such as VE, NVE, and NVEcovdistinguish coherent and informative biclustering solutions across different biological regimes\.

### IV\-CEvaluation of Biclustering Algorithms

We evaluated three biclustering algorithms in our experiments: Cheng and Church \(CCA\)\[[1](https://arxiv.org/html/2608.29045#bib.bib1)\], Large Average Submatrices \(LAS\)\[[13](https://arxiv.org/html/2608.29045#bib.bib13)\], and Spectral Biclustering\[[22](https://arxiv.org/html/2608.29045#bib.bib22)\]\. CCA is a residue\-based method that searches for submatrices with low mean squared residue, and it serves as a standard coherence\-oriented baseline\. LAS searches for submatrices with large average values by using repeated randomized searches followed by refinement, and it provides a useful contrast because it often favours strong local patterns\. Spectral Biclustering is a matrix decomposition based method that groups rows and columns jointly, giving a third type of biclustering solution that is different from the other two approaches\. These three algorithms were chosen because they represent different styles of biclustering and therefore make it easier to see when changes in evaluation are due to the metric rather than to one particular algorithm family\. CCA and LAS were implemented as per\[[9](https://arxiv.org/html/2608.29045#bib.bib9)\]and their publicly available library, while Spectral Biclustering used the standard Python implementation corresponding to\[[22](https://arxiv.org/html/2608.29045#bib.bib22)\]\. The outputs of all three algorithms were converted to a common bicluster representation before computing the evaluation measures\. In all experiments, the algorithms were run through the same experimental framework, and apart from the requested number of biclusters, their default settings were kept unchanged\.

### IV\-DExperimental protocol

The experiments were carried out in two stages\. First, we used controlled synthetic datasets in which the planted bicluster structure is known\. For these datasets, each algorithm was asked to return the planted number of biclusters for that scenario, so the comparison focuses on how the evaluation metrics behave when the target number of biclusters is fixed\. Second, we used the yeast benchmark datasets, where the true bicluster structure is not known in advance\. In this setting, each algorithm was run over a small sweep of requested bicluster numbers, withK∈\{3,5,8,10,15\}K\\in\\\{3,5,8,10,15\\\}chosen as a coarse sweep from small to relatively large biclustering solutions\. For every resulting solution, we computed ASR, AvgVE, NVE, NVEcov, and coverage\. The score\-based metrics were interpreted in a lower\-is\-better sense, while coverage was reported separately to show how much of the data matrix was explained by the biclustering solution\. Using the same algorithms and the same evaluation metrics in both the synthetic and the real\-data experiments allows the results to be compared directly across the two settings\.

### IV\-EControlled synthetic validation

We first used controlled synthetic datasets to check what information the different metrics are actually capturing\. These datasets are useful because each one was designed to create a specific evaluation situation, such as clean additive structure, scaling structure, overlap, redundancy, or low coverage\. This lets us test the behavior of the metrics in settings where the intended bicluster structure is known in advance\. Table[II](https://arxiv.org/html/2608.29045#S4.T2)summarizes the algorithm that most often obtains the best score under each metric across the synthetic scenarios\. It shows that the preferred algorithm changes with the evaluation criterion\. ASR, AvgVE, NVE, and NVEcovemphasize different aspects of the output: additive residue, virtual\-error coherence, relative separation, and coverage\-adjusted separation\.

#### IV\-E1Coherence\-oriented cases\.

The first group of synthetic datasets, namely S1–S3, was used to examine cases where the planted biclusters are well separated but differ in their internal signal model\. In S1, the biclusters follow a simple additive pattern, so coherence\-based metrics and the NVE family both behave as expected\. In S2 and S3, the patterns become more difficult because scaling and mixed shift\-scale effects are introduced\. These cases are useful because they show that ASR and AvgVE do not always respond in the same way to the same structure\. At the same time, the planted biclusters are still distinct from one another, so NVE remains mainly a measure of separability rather than just another measure of internal coherence\.

#### IV\-E2Separation and redundancy\.

The separation\-specific role of NVE is most transparent in Figure[2](https://arxiv.org/html/2608.29045#S4.F2)\([2\(a\)](https://arxiv.org/html/2608.29045#S4.F2.sf1)\)\. Across S1, S5, and S7, the numerator in Eq\. \([10](https://arxiv.org/html/2608.29045#S3.E10)\),∑kVE⁡\(Bk\)\\sum\_\{k\}\\mathrm\{VE\}\(B\_\{k\}\), remains of the same order but the denominator∑kminj≠k⁡VE⁡\(Bk​j\)\\sum\_\{k\}\\min\_\{j\\neq k\}\\mathrm\{VE\}\(B\_\{kj\}\)changes sharply\. In S1, merging two planted biclusters produces a much less coherent super\-bicluster, so the denominator is large and NVE is low\. In S5, this contrast weakens because overlapping biclusters remain partially compatible after merging\. In S7, it nearly disappears: clone biclusters can be merged with little additional incoherence, so NVE moves toward one even though the individual biclusters still appear clean under coherence\-only scores\. This is precisely the kind of redundancy penalty that ASR and AvgVE do not provide\.

\(a\)NVE decomposition: numerator vs\. denominator\(b\)Coverage penalty in NVEcovon synthetic data\. Here,CR\\mathrm\{CR\}denotes the coverage ratio defined in Eq\. \([12](https://arxiv.org/html/2608.29045#S3.E12)\)\.
Figure 2:NVE decomposition and coverage penalisation on illustrative synthetic cases\.
#### IV\-E3Coverage\-related cases\.

The coverage effect is equally explicit in Figure[2\(b\)](https://arxiv.org/html/2608.29045#S4.F2.sf2)\. S9b attains the best NVE because the cherry\-picked biclusters are nearly perfect internally, but its union coverage is only about1%1\\%, so NVEcovincreases sharply after the coverage penalty is applied\. By contrast, S9a and S4 retain slightly worse NVE values yet improve relative to S9b once the solution covers a non\-trivial fraction of the matrix\. Referencing this plot directly makes the intended distinction clearer: NVEcovis not simply a noisier version of NVE, but a criterion that changes the ordering when apparent quality is obtained by explaining too little of the matrix\.

Overall, the controlled synthetic experiments serve as a sanity check before moving to algorithm\-level comparisons\. They show that the proposed metrics were designed to respond to specific structural properties of biclustering solutions: NVE responds to separation and redundancy, while NVEcovadds a direct preference against extremely small, low\-coverage solutions\. This gives a clear basis for the larger synthetic and real\-data experiments that follow\.

### IV\-FSynthetic benchmark results at matchedKK

After checking the basic behavior of the metrics on planted synthetic structures, we next compared the three algorithms on the full set of synthetic datasets using the planted number of biclusters for each case\. This setting is useful because it removes model selection from the comparison\. The main question here is not which algorithm can guess the correct number of biclusters, but rather how the different evaluation metrics judge the solutions when the targetKKis fixed\.

The matched\-KKsynthetic summaries are more informative when the metric\-specific plots are cited separately; see Figs\.[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(a\)](https://arxiv.org/html/2608.29045#S4.F3.sf1)\)–[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(d\)](https://arxiv.org/html/2608.29045#S4.F3.sf4)\)\. Figure[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(a\)](https://arxiv.org/html/2608.29045#S4.F3.sf1)\) gives a mixed picture, with CCA or Spectral often preferred depending on the scenario\. In contrast, Figs\.[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(b\)](https://arxiv.org/html/2608.29045#S4.F3.sf2)\) and[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(c\)](https://arxiv.org/html/2608.29045#S4.F3.sf3)\) favour LAS on most datasets, which is consistent with LAS returning small, locally clean biclusters\. The reversal in Fig\.[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(d\)](https://arxiv.org/html/2608.29045#S4.F3.sf4)\) is therefore substantive rather than cosmetic: once coverage is penalised, Spectral becomes the most frequent winner\.

Table II:Most frequent winning algorithm under each metric on the synthetic datasets\.MetricMost frequent winnerASRCCA \(5/10 datasets\)AvgVELAS \(8/10 datasets\)NVELAS \(8/10 datasets\)NVEcovSpectral \(8/10 datasets\)This shift is especially clear on S2 scaling and S9b coverage cherry\-pick\. On S2, LAS gives the best AvgVE \(0\.3130\.313\) and NVE \(0\.4280\.428\), but it covers only8\.3%8\.3\\%of the matrix, whereas Spectral covers69\.3%69\.3\\%and becomes best under NVEcov\(1\.1411\.141\)\. On S9b, LAS again dominates ASR, AvgVE, and NVE, yet its solution covers only0\.27%0\.27\\%of the matrix; once coverage is taken into account, Fig\.[3](https://arxiv.org/html/2608.29045#S4.F3)\([3\(d\)](https://arxiv.org/html/2608.29045#S4.F3.sf4)\) shows that the preferred solution switches to Spectral\. These examples strengthen the main conclusion of the synthetic benchmark: NVE and especially NVEcovdo not merely rescale coherence, but can reverse the ranking by penalising narrow, cherry\-picked structure\.

\(a\)ASR\(b\)AvgVE\(c\)NVE\(d\)NVEcov
Figure 3:Matched\-KKsynthetic benchmark scores under ASR, AvgVE, NVE, and NVEcov\. All four metrics are min\-optimal\.Taken together, these matched\-KKsynthetic experiments show that metric choice is not a minor detail\. If the evaluation is based only on coherence\-oriented measures, one family of solutions may look clearly preferable\. If separability and coverage are also taken into account, the ranking can change\. This is the main result of the synthetic benchmark comparison: NVE and especially NVEcovdo not simply repeat the information already given by ASR and AvgVE, but can lead to meaningfully different judgments about biclustering quality\.

### IV\-GYeast benchmark results underKK\-sweep

The real\-data yeast experiments were used to study a more practical setting in which the true number of biclusters is not known in advance\. Instead of fixingKKto a planted value, each algorithm was run over a small range of requested bicluster numbers, and the resulting solutions were evaluated by ASR, AvgVE, NVE, and NVEcov\. This setup is useful because it shows whether the choice of metric affects not only the ranking of algorithms, but also the choice of model complexity\. Table[III](https://arxiv.org/html/2608.29045#S4.T3)lists representative yeast cases in which different metrics select different values ofKKfor the same dataset and algorithm\. Each entry is the value ofKKthat minimizes the corresponding metric over the tested sweep\.

The main result is that the selected solution often changes when the metric changes\. Across the yeast experiments, the bestKKchosen by NVEcovdiffered from the bestKKchosen by ASR in many dataset\-algorithm combinations\. Similar differences were also seen when NVEcovwas compared with AvgVE and NVE\. This means that the metric is not only scoring the same solutions in a slightly different way; it is often pointing to a different part of theKK\-sweep altogether\. In that sense, the yeast experiments provide stronger evidence than the synthetic matched\-KKexperiments, because they show that metric choice can affect the final model that would actually be selected in practice\.

Table III:Chosen values ofKKin the yeastKK\-sweep experiments\.Dataset / AlgorithmASRAvgVENVENVEcov01\_alpha\_factor / CCA1555802\_cdc\_15 / CCA15331502\_cdc\_15 / Spectral555303\_cdc\_28 / CCA10851504\_elutriation / CCA10510814\_nitrogen\_depletion / CCA3338In terms of algorithm ranking, NVEcovmost often favoured Spectral on the yeast data, while LAS was selected much less often\. This is consistent with what was already seen in the synthetic experiments\. LAS can obtain very strong values under coherence\-oriented criteria, but these solutions often cover only a very small part of the matrix\. By contrast, Spectral more often produces solutions with broader coverage, so once the coverage penalty is taken into account, its ranking improves\. CCA remains competitive on some datasets, but in general the yeast results suggest that NVEcovprefers solutions that strike a better balance between structure quality and extent of coverage\.

\(a\)01\_alpha\_factor\(b\)02\_cdc\_15\(c\)03\_cdc\_28\(d\)04\_elutriation\(e\)08\_25mm\_DTT\(f\)12\_heat\_shock\_1\(g\)13\_heat\_shock\_2\(h\)14\_N2\_depletion
Figure 4:Yeast benchmarkKK\-sweeps scored by NVEcov\.The real\-data argument also becomes sharper when the dataset\-specific NVEcovsweeps are cited directly\. In02\_cdc\_15\(Fig\.[4](https://arxiv.org/html/2608.29045#S4.F4)\([4\(b\)](https://arxiv.org/html/2608.29045#S4.F4.sf2)\)\), the NVEcovminimum occurs for Spectral atK=3K=3, whereas ASR prefers CCA atK=15K=15and AvgVE prefers LAS atK=15K=15\. Thus, the metric choice changes both the preferred algorithm and the selected model complexity\. In04\_elutriation\(Fig\.[4](https://arxiv.org/html/2608.29045#S4.F4)\([4\(d\)](https://arxiv.org/html/2608.29045#S4.F4.sf4)\)\), LAS performs best under AvgVE and NVE atK=8K=8, but NVEcovinstead selects Spectral atK=3K=3, consistent with the fact that the LAS solution covers only about5\.2%5\.2\\%of the matrix while the selected Spectral solution covers about43\.3%43\.3\\%\. The main cautionary counterexample should also be pointed out explicitly\. In13\_heat\_shock\_2\(Fig\.[4](https://arxiv.org/html/2608.29045#S4.F4)\([4\(g\)](https://arxiv.org/html/2608.29045#S4.F4.sf7)\)\), LAS returns an effectively degenerate solution with coverage around0\.21%0\.21\\%, yet all four metrics collapse to zero\. This is not evidence against the usefulness of NVE or NVEcov, but it does show that a coverage penalty alone cannot rescue pathologically small outputs once the underlying VE term has already collapsed\.

### IV\-HFailure modes and caveats

Although the main experiments suggest that NVE and NVEcovprovide useful additional information, the results also show that these metrics should not be treated as automatically reliable in every situation\. Some edge cases produce solutions that look very favourable numerically even though they are not especially useful from a biclustering point of view\. For this reason, it is important to discuss the situations in which the proposed metrics can become misleading\. Fig\.[5](https://arxiv.org/html/2608.29045#S4.F5)shows the local NVE contribution of each recovered bicluster, with Figs\.[5](https://arxiv.org/html/2608.29045#S4.F5)\([5\(a\)](https://arxiv.org/html/2608.29045#S4.F5.sf1)\)–[5](https://arxiv.org/html/2608.29045#S4.F5)\([5\(j\)](https://arxiv.org/html/2608.29045#S4.F5.sf10)\) reporting the individual scenarios and Fig\.[5](https://arxiv.org/html/2608.29045#S4.F5)\([5\(k\)](https://arxiv.org/html/2608.29045#S4.F5.sf11)\) showing the reference colourmap used for these heatmaps\. In each heatmap, rows denote algorithms and columns denote biclustersB1,…,BK∗B\_\{1\},\\ldots,B\_\{K^\{\*\}\}obtained at the scenario’s ground\-truth value ofK∗K^\{\*\}\. Each cell reportsNVE⁡\(Bk\)=VE⁡\(Bk\)/minℓ≠k⁡VE⁡\(Bk​ℓ\)\\operatorname\{NVE\}\(B\_\{k\}\)=\\operatorname\{VE\}\(B\_\{k\}\)/\\min\_\{\\ell\\neq k\}\\operatorname\{VE\}\(B\_\{k\\ell\}\), whereBk​ℓB\_\{k\\ell\}is the union super\-bicluster formed fromBkB\_\{k\}andBℓB\_\{\\ell\}\. Thus, lighter and smaller cells indicate biclusters that are internally coherent and remain well separated from their nearest merged alternative, whereas darker and larger cells identify noisy, redundant, or weakly separated local components\. The figure should therefore be read as a diagnostic map of where an algorithm succeeds or fails within a scenario, rather than only as an aggregate ranking\.

One clear example comes from the synthetic thin\-column case\. The per\-bicluster diagnostic in Fig\.[5](https://arxiv.org/html/2608.29045#S4.F5)\([5\(f\)](https://arxiv.org/html/2608.29045#S4.F5.sf6)\) shows that once a bicluster collapses to only two columns, the VE\-based terms can become artificially small, which then propagates into AvgVE and the NVE family\. The issue here is not genuine bicluster quality, but score degeneracy induced by an undersized submatrix\. This is why the thin\-column scenario should be cited directly when discussing the need for a minimum\-size filter\. A closely related problem appears in the yeast benchmark\. Fig\.[4](https://arxiv.org/html/2608.29045#S4.F4)\([4\(g\)](https://arxiv.org/html/2608.29045#S4.F4.sf7)\) shows that13\_heat\_shock\_2contains a LAS solution whose score remains spuriously favourable despite negligible coverage\.Taken together, Figs\.[5](https://arxiv.org/html/2608.29045#S4.F5)\([5\(f\)](https://arxiv.org/html/2608.29045#S4.F5.sf6)\) and[4](https://arxiv.org/html/2608.29045#S4.F4)\([4\(g\)](https://arxiv.org/html/2608.29045#S4.F4.sf7)\) support a more precise caveat: NVE\-based measures are most informative when biclusters are large enough for VE to be numerically stable, and they should be reported together with basic size and coverage statistics whenever very small outputs are possible\.

\(a\)S1 additive \(K=K\*=4\)\(b\)S2 scaling \(K=K\*=4\)\(c\)S3 mixed shift scale \(K=K\*=4\)\(d\)S4 size vs quality \(K=K\*=4\)\(e\)S5 overlap \(K=K\*=4\)\(f\)S6 thin columns \(K=K\*=4\)\(g\)S7 identical clones \(K=K\*=4\)\(h\)S8 noise ladder \(K=K\*=5\)\(i\)S9a coverage tiling \(K=K\*=8\)\(j\)S9b cov\. cherrypick \(K=K\*=3\)![Refer to caption](https://arxiv.org/html/2608.29045v1/per_bicluster_nve_colorbar.png)\(k\)Reference

Figure 5:Per\-bicluster NVE diagnostics on synthetic benchmark scenarios\.These edge cases suggest that an additional validity check may be needed before NVE\-based scores are interpreted\. One simple option would be to impose a minimum bicluster size, especially a minimum number of columns, before computing VE, NVE, or NVEcov\. Another option would be to report NVE\-family scores together with coverage and average bicluster dimensions, so that a very low score from a tiny solution is not mistaken for strong overall performance\. We do not treat this as a failure of the main idea behind NVE, but rather as a reminder that evaluation metrics still depend on the kinds of solutions produced by the underlying algorithm\.

Overall, these caveats do not remove the main findings of the paper\. Instead, they help define the conditions under which the proposed metrics are most informative\. NVE is most useful when the biclusters are large enough for VE to be stable and when the main question is whether the discovered biclusters are genuinely distinct\. NVEcovis most useful when low\-coverage cherry\-picking is a realistic concern\. However, in the presence of very small or degenerate biclusters, additional filtering or reporting rules are likely to be necessary\.

### IV\-IRelation to NSR

The closest prior internal measure to NVE is the normalized squared residue \(NSR\) of Lee et al\.\[[12](https://arxiv.org/html/2608.29045#bib.bib12)\]\. NSR and NVE use the same general normalization idea: the coherence of each bicluster is compared with the coherence of a super\-bicluster formed by merging it with another bicluster\. Their difference is the elementary coherence functional\. NSR is defined from the mean squared residue \(Eq\. \([8](https://arxiv.org/html/2608.29045#S2.E8)\)\), whereas NVE replacesMSR⁡\(⋅\)\\operatorname\{MSR\}\(\\cdot\)byVE⁡\(⋅\)\\operatorname\{VE\}\(\\cdot\)\. Thus, NSR is best viewed as the MSR\-based member of the same super\-bicluster\-normalization family, rather than as an independent pattern\-consistency measure\.

This distinction is important mathematically\. For an additive biclusterai​j=μ\+αi\+βj\+ϵi​ja\_\{ij\}=\\mu\+\\alpha\_\{i\}\+\\beta\_\{j\}\+\\epsilon\_\{ij\}, MSR measures the residual noise variance and is well matched to the assumed model\. However, for a noiseless multiplicative biclusterai​j=si​pja\_\{ij\}=s\_\{i\}p\_\{j\}, the Cheng–Church residue is

ai​j−ai​J−aI​j\+aI​J=\(si−s¯\)​\(pj−p¯\),a\_\{ij\}\-a\_\{iJ\}\-a\_\{Ij\}\+a\_\{IJ\}=\(s\_\{i\}\-\\bar\{s\}\)\(p\_\{j\}\-\\bar\{p\}\),and hence

MSR⁡\(B\)=\(1\|I\|​∑i∈I\(si−s¯\)2\)​\(1\|J\|​∑j∈J\(pj−p¯\)2\),\\operatorname\{MSR\}\(B\)=\\left\(\\frac\{1\}\{\|I\|\}\\sum\_\{i\\in I\}\(s\_\{i\}\-\\bar\{s\}\)^\{2\}\\right\)\\left\(\\frac\{1\}\{\|J\|\}\\sum\_\{j\\in J\}\(p\_\{j\}\-\\bar\{p\}\)^\{2\}\\right\),which is generally nonzero even when the bicluster follows a perfect scaling pattern\. NSR cannot remove this model bias, because both its numerator and denominator are still computed from MSR\. NVE was introduced precisely to retain the super\-bicluster separability idea while using the VE coherence model, which is more appropriate for standardized behavioural patterns\.

To verify that this distinction is not merely formal, we computed NSR only on a small diagnostic subset of the planted synthetic biclusters, without rerunning the full algorithmic benchmark\. The results in Table[IV](https://arxiv.org/html/2608.29045#S4.T4)show the expected behavior\. NSR and NVE both identify the identical\-clone case as poorly separated, confirming that NSR is a meaningful predecessor for additive redundancy\. However, NSR is much more strongly affected by the scaling scenario because it inherits MSR’s additive\-model bias\. It also prefers the low\-coverage cherry\-picked solution over the broader tiling solution, whereas NVEcovreverses this ranking by design\.

Table IV:Targeted NSR diagnostic on planted synthetic biclusters\.ScenarioASRAvgVENSRNVENVEcovCoverageS1 additive0\.08610\.15480\.03720\.25870\.72920\.1258S2 scaling1\.48970\.15610\.24430\.22310\.62910\.1258S7 identical clones0\.09580\.23391\.03661\.09733\.21260\.1167S9a coverage tiling0\.20410\.34970\.13490\.47091\.63120\.0833S9b coverage cherry\-pick0\.05170\.23310\.01920\.27162\.71630\.0100

For this reason, we do not treat NSR as a full baseline throughout all experiments\. The main empirical question is whether VE\-based normalization and coverage adjustment add information beyond standard coherence summaries\. NSR is therefore used here as a conceptual and diagnostic reference: it validates the super\-bicluster normalization principle in the additive setting, while also illustrating why the proposed VE\-based and coverage\-adjusted variants are needed\.

## VConclusion

This paper examined whether Normalised Virtual Error \(NVE\) and its coverage\-aware variant NVEcovprovide evaluation information beyond that already captured by existing internal biclustering measures\. The central motivation was that commonly used measures such as ASR, MSR, and AvgVE mainly assess within\-bicluster coherence, but do not explicitly evaluate whether the extracted biclusters are genuinely distinct from one another or whether they explain a meaningful portion of the data matrix\. To address this gap, we studied NVE as a VE\-based criterion that incorporates relative distinctness through comparison with merged super\-biclusters, and NVEcovas a further extension that penalises low coverage at the solution level\.

Taken together, the experiments support three main conclusions\. First, NVE captures information about separation and redundancy that is not fully reflected by coherence\-based measures\. This was most clearly seen in the controlled synthetic datasets, where overlapping or near\-duplicate biclusters could still look favourable under coherence\-based scoring but were penalised more clearly by NVE\. Second, NVEcovadds a further evaluation component by discouraging solutions that achieve low coherence error while covering only a very small fraction of the matrix\. In both the synthetic benchmarks and the yeast benchmarkKK\-sweeps, this adjustment could change the preferred algorithm and, in the real\-data setting, the selected model complexity\. Third, these effects show that NVE\-based criteria do not merely rescale existing coherence measures: they make separability and representativeness explicit, and can therefore lead to different judgements about biclustering quality\.

At the same time, the results also make clear that NVE\-based evaluation should not be interpreted uncritically\. When biclusters become extremely small or degenerate, especially in thin\-column settings, VE\-based quantities can become artificially favourable\. The yeast experiments showed a related failure mode in which a negligible\-coverage solution could still receive extremely strong scores\. For this reason, we do not claim that NVE or NVEcoveliminates the need for basic sanity checks on bicluster size and coverage\. Rather, the proposed measures are most useful when applied to solutions for which the underlying VE computation is numerically meaningful, and when they are reported together with simple structural diagnostics such as average bicluster dimensions and coverage\.

Overall, the main conclusion is that NVE and especially NVEcovcontribute useful additional internal validation information for biclustering and co\-clustering\. NVE adds a notion of relative separability and redundancy that is absent from standard coherence\-only measures, while NVEcovadds a notion of representativeness by discouraging narrow, low\-coverage solutions\. Together, these properties make the proposed measures useful not only for scoring biclustering solutions, but also for practical model selection\. Future work should study more robust VE\-based formulations for very small biclusters, investigate alternative coverage and overlap regularisations, and evaluate the proposed criteria across a broader range of biclustering algorithms and application domains\.

## References

- \[1\]Y\. Cheng and G\. M\. Church, “Biclustering of expression data,” in*Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology \(ISMB\)*\. AAAI Press, 2000, pp\. 93–103\.
- \[2\]I\. S\. Dhillon, “Co\-clustering documents and words using bipartite spectral graph partitioning,” in*Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining \(KDD\)*\. ACM, 2001, pp\. 269–274\.
- \[3\]S\. C\. Madeira and A\. L\. Oliveira, “Biclustering algorithms for biological data analysis: A survey,”*IEEE/ACM Transactions on Computational Biology and Bioinformatics*, vol\. 1, no\. 1, pp\. 24–45, 2004\.
- \[4\]M\. D\. M\. Noronha, R\. Henriques, S\. C\. Madeira, and L\. E\. Zarate, “Impact of metrics on biclustering solution and quality: A review,”*Pattern Recognition*, vol\. 127, p\. 108612, 2022\.
- \[5\]E\. N\. Castanho*et al\.*, “Biclustering data analysis: a comprehensive survey,”*Briefings in Bioinformatics*, vol\. 25, no\. 4, p\. bbae342, 2024\.
- \[6\]F\. Divina, B\. Pontes, R\. Giráldez, and J\. S\. Aguilar\-Ruiz, “An effective measure for assessing the quality of biclusters,”*Computers in biology and medicine*, vol\. 42, no\. 2, pp\. 245–256, 2012\.
- \[7\]B\. Pontes, R\. Giráldez, and J\. S\. Aguilar\-Ruiz, “Quality measures for gene expression biclusters,”*PLOS ONE*, vol\. 10, no\. 3, p\. e0115497, 2015\.
- \[8\]A\. Prelic, S\. Bleuler, P\. Zimmermann, A\. Wille, P\. Buhlmann, W\. Gruissem, L\. Hennig, L\. Thiele, and E\. Zitzler, “A systematic comparison and evaluation of biclustering methods for gene expression data,”*Bioinformatics*, vol\. 22, no\. 9, pp\. 1122–1129, 2006\.
- \[9\]V\. A\. Padilha and R\. J\. G\. B\. Campello, “A systematic comparative evaluation of biclustering techniques,”*BMC Bioinformatics*, vol\. 18, p\. 55, 2017\.
- \[10\]A\. Tanay, R\. Sharan, and R\. Shamir, “Discovering statistically significant biclusters in gene expression data,”*Bioinformatics*, vol\. 18, no\. suppl\_1, pp\. S136–S144, 2002\.
- \[11\]R\. Henriques and S\. C\. Madeira, “Bsig: evaluating the statistical significance of biclustering solutions,”*Data Mining and Knowledge Discovery*, vol\. 31, no\. 2, pp\. 447–486, 2017\.
- \[12\]Y\.\-R\. Lee, J\.\-H\. Lee, and C\.\-H\. Jun, “Validation measures of bicluster solutions,”*Industrial Engineering and Management Systems 8*, 2009\.
- \[13\]A\. A\. Shabalin, V\. J\. Weigman, C\. M\. Perou, and A\. B\. Nobel, “Finding large average submatrices in high dimensional data,”*The Annals of Applied Statistics*, vol\. 3, no\. 3, pp\. 985–1012, 2009\.
- \[14\]C\. Colantuoni, G\. Henry, S\. Zeger, and J\. Pevsner, “Snomad \(standardization and normalization of microarray data\): Web\-accessible gene expression data analysis,”*Bioinformatics*, vol\. 18, no\. 11, pp\. 1540–1541, 2002\.
- \[15\]J\. S\. Aguilar\-Ruiz, “Shifting and scaling patterns from gene expression data,”*Bioinformatics*, vol\. 21, no\. 20, pp\. 3840–3845, 2005\.
- \[16\]K\. Eren, M\. Deveci, O\. Kucuktunc, and U\. V\. Catalyurek, “A comparative analysis of biclustering algorithms for gene expression data,”*Briefings in Bioinformatics*, vol\. 14, no\. 3, pp\. 279–292, 2013\.
- \[17\]D\. Horta and R\. J\. G\. B\. Campello, “Similarity measures for comparing biclusterings,”*IEEE/ACM Transactions on Computational Biology and Bioinformatics*, vol\. 11, no\. 5, pp\. 942–954, 2014\.
- \[18\]E\. N\. Castanho, J\. P\. Lobo, R\. Henriques, and S\. C\. Madeira, “G\-bic: Generating synthetic benchmarks for biclustering,”*BMC Bioinformatics*, vol\. 24, p\. 457, 2023\.
- \[19\]R\. Henriques, C\. Antunes, and S\. C\. Madeira, “A structured view on pattern mining\-based biclustering,”*Pattern Recognition*, vol\. 48, no\. 12, pp\. 3941–3958, 2015\.
- \[20\]P\. Waltman*et al\.*, “Multi\-species integrative biclustering,”*BMC Bioinformatics*, vol\. 11, p\. 215, 2010\.
- \[21\]S\. Sutheeworapong*et al\.*, “A novel biclustering approach with iterative optimization to identify coexpressed gene sets in microarray data,”*Cancer Informatics*, vol\. 11, pp\. 123–135, 2012\.
- \[22\]Y\. Kluger, R\. Basri, J\. T\. Chang, and M\. Gerstein, “Spectral biclustering of microarray data: Coclustering genes and conditions,”*Genome Research*, vol\. 13, no\. 4, pp\. 703–716, 2003\.