Poisson Subspace Clustering: Focusing on the Essentials in Count Data

Poisson Subspace Clustering: Focusing on the Essentials in Count Data Collin Leiber1,2*, Kai Puolamäki2 and Heikki Mannila1 1*

arXiv:2608.23287v1 [cs.LG] 24 Aug 2026

2

Aalto University, Espoo, Finland. University of Helsinki, Helsinki, Finland.

*Corresponding author(s). E-mail(s): collin.leiber@aalto.fi; Contributing authors: kai.puolamaki@helsinki.fi; heikki.mannila@aalto.fi; Abstract Count data represented as a matrix of non-negative integer values, such as contingency tables, are prevalent across diverse domains. When clustering such data sets, specific methods are required, as generic algorithms often fail to consider their unique distributional properties, leading to unreliable outputs. An effective strategy is to use well-established statistical models such as the Poisson and negative binomial distributions. We present 3CPO, a clustering algorithm based on statistically solid modeling of count data. In addition to the cluster labels, it identifies a subset of relevant columns, enhancing the interpretability of the results. We propose a simple iterative algorithm that maximizes the posterior probability to find good clustering solutions and discuss its properties. Extensive experiments demonstrate its ability to define high-quality clusters within associated subspaces for various data domains, ranging from gene expressions and texts to economics. Our findings suggest that 3CPO is a robust solution for clustering count data in a statistically sound and interpretable manner. Our code is available at https://github.com/collinleiber/3CPO. Keywords: Common Subspace Clustering, Count Data, Expectation Maximization, Column Selection, Poisson Distribution

1 Introduction Count data are a natural and commonly used type of data, e.g., in the form of contingency tables. The idea is that each entry in the data matrix represents the number 1

of occurrences of some event. This type of data is used in a wide variety of research fields, such as biology (Snow et al. 2007), ecology (Farnsworth et al. 2005), mobility studies (Ceder 1984), environmental studies (Hargesheimer and Lewis 1998), publication studies (Waltman et al. 2012), or economics (Rouwendal and Boter 2009). Due to its definition, count data have some unique properties: (1) all values are non-negative natural numbers, (2) all rows share a common domain, and (3) all columns share a common domain. Property (3) contrasts typical tabular data sets, where each column usually describes a different trait. Consider a data set regarding personal information consisting of columns for year of birth, place of birth, height, and gender. These columns are hard to compare as they do not even share a common data type. In contrast, an exemplary count data set could comprise various options, where each entry in the data matrix counts how often a person has chosen a particular option. This information could be used to determine whether someone prefers option A or option B. If one would like to explore certain groups within count data, clustering is a viable choice. Clustering algorithms try to group the rows of a data matrix, using some notion of similarity, so that all rows within a group share a natural relationship, while those in different groups are dissimilar (Dubes and Jain 1976). As an unsupervised machinelearning task, no prior knowledge of the data is required. In general, clustering has already been extensively studied (Xu and Wunsch II 2005), especially in the context of tabular data. However, it has been shown that due to the unique characteristics of count data, transformations often perform worse than sophisticated models, such as Poisson and negative binomial distributions (O’Hara and Kotze 2010). This limits the applicability of traditional clustering algorithms that often require pre-processed data to return satisfactory results. Therefore, we argue that specialized approaches are a valuable tool in the data mining toolbox. As count data is often high-dimensional, e.g., gene expression data or bag-of-words representations of texts, it is beneficial to cluster relevant rows and automatically select columns relevant for the clustering task. In this way, a subsequent analysis of the identified structures can be simplified, reducing the manual work a domain expert has to invest. For tabular data sets, such subspace clustering algorithms have already been studied extensively (Sim et al. 2013). The selection of relevant columns can be carried out in two different ways: specifically for each cluster or globally for all clusters. In the first variant, individual columns are selected for each cluster so that their characteristics are best described. This is a well-studied field of research (Kriegel et al. 2012) and is used, e.g, in block-diagonal co-clustering (Battaglia et al. 2025). A disadvantage is that the comparability of individual clusters is more difficult as the clusters are located in different subspaces (Goebl et al. 2014). For this reason, so-called common subspace clustering has gained momentum in recent years (Ding and Li 2007; Goebl et al. 2014; Mautz et al. 2017; Bauer et al. 2023). Here, a single subspace is defined that contains all clusters. In this paper, we propose 3CPO, Clustering and Column selection of Count Data using a Poisson-based Optimization. 3CPO uses concepts based on the Poisson distribution to cluster the rows of a data matrix and to simultaneously select the columns that are most relevant for this clustering result. Extensive experiments verify the good performance of 3CPO with respect to the created clusters. Furthermore, we show that

2

our method can significantly reduce the number of relevant columns. This property simplifies a subsequent interpretation of the clustering results, which is beneficial in real-world unsupervised scenarios. Our main contributions are as follows: 1. We propose a sophisticated and statistically sound model to describe the entries within a count data matrix using the Poisson distribution. 2. We introduce 3CPO, a common subspace clustering algorithm that iteratively maximizes the posterior probability with respect to our proposed model. 3. Extensive experiments using data sets from diverse domains verify that 3CPO outperforms its competitors in many scenarios and simplifies interpreting the results by automatically selecting the most informative columns.

2 Related Work We see two research areas that are relevant for our proposal: clustering of count data and column selection for clustering.

2.1 Clustering of Count Data Baselines. An easy way to take into account certain characteristics of count data is to pre-process the data. For example, to handle different magnitudes of row sums, one can consider the relative frequencies of the columns, i.e., divide each value by the row sum. Another option is to compute the revealed comparative advantage (RCA) (Balassa 1965), which is often used in economics. An issue with pre-processing count data is discussed by O’Hara and Kotze (2010), where transformations are shown to be often unsuitable for count data. Therefore, it would be beneficial if the clustering algorithm operated on the raw data. Here, an option is Spherical k -Means (Dhillon and Modha 2001) (SKM), a variant of k -Means (Lloyd 1982) that optimizes toward the cosine instead of the Euclidean distance. It follows that the length of a vector does not influence the result, making SKM more suitable for sparse data such as text representations. Our proposal follows a similar idea by implicitly incorporating pre-processing within the model and therefore simplifying the clustering process. Poisson-based Clustering. Examples of Poisson-based clustering approaches are PoissonC and PoissonL (Cai et al. 2004), which model the expected values of the Poisson distribution as products of row- and column-specific factors, where each cluster receives its own column values (details in Appendix A.1). This formulation is optimized using an Expectation Maximization (EM) (Dempster et al. 1977) approach, where cluster assignments are updated by considering probabilities (PoissonL) or a Chi-squared test (PoissonC). Note that columns not following the clustering model can heavily influence the final result. To receive more appropriate distances, TransChisq (Kim et al. 2007) adds a feature transformation to this formulation by considering all pairs of features. In (Rau et al. 2011), a method based on a Poisson-Mixture-Model is proposed that considers replicates in gene expression data. Using a Poisson-based dissimilarity function, the proposal in (Witten 2011) applies complete linkage to perform hierarchical clustering.

3

Dirichlet-based Clustering. Another family of approaches is based on Dirichlet distributions, often used for topic modeling. Latent Dirichlet Allocation (Blei et al. 2003) adapts a three-level hierarchical Bayesian model that is optimized using an EM-based approach. EDCM (Elkan 2006), an approximation of the Dirichlet compound multinomial distribution, improves on traditional multinomial distributions by considering burstiness, i.e., the phenomenon that if an entry occurs once, it is likely that it occurs again. Often, multiple distributional families are combined to better capture the unique characteristics of the data. Examples are the Multinomial Generalized Dirichlet Distribution (Bouguila 2008), a composition of the generalized Dirichlet and multinomial distributions, and Multinomial Beta-Liouville Mixture (Bouguila 2011), a combination of the multinomial and the Beta-Liouville distributions. Exponential approximation to the Multinomial Beta-Liouville (Zamzami and Bouguila 2020) is another case that can simultaneously fit a model and select the optimal number of clusters by applying an extended EM procedure. In contrast to these methods, our approach only considers a simple Poisson distribution to yield a hard clustering solution.

2.2 Column Selection for Clustering While some research has already been done that combines clustering of count data with column selection, to the best of our knowledge, this has been focused on coclustering, i.e., simultaneously clustering the rows and columns of a data matrix. This can, for example, be achieved by using information-theoretic approaches such as CROINFO (Govaert and Nadif 2018) which optimizes a loss function based on mutual information. Algorithms like CoclustMod (Ailem et al. 2015) and CoclustSpecMod (Labiod and Nadif 2011) interpret co-clustering as a graph modularity problem. Other methods, e.g., (Govaert and Nadif 2010; Ailem et al. 2017b,a), use the Poisson distribution in the form of Poisson Latent Block Models (Nadif and Govaert 2005). This idea has been generalized by ELBM and SELBM (Hoseinipour et al. 2025) to consider (sparse) block models from various distributions of the exponential family. TauCC (Battaglia et al. 2024) simplifies the complexity of choosing hyperparameters in co-clustering by automatically identifying an appropriate number of clusters. In our work, the goal is not to analyze multiple column sets containing different clustering characterizations but to filter out columns not helpful for the clustering task and, thus, identify a single set of columns that is relevant for all clusters. This allows not only the analysis of the intra-cluster but also the inter-cluster relationship (Goebl et al. 2014). Common subspace algorithms pursue a similar goal, by defining a single relevant subspace, often by combining a feature transformation with column selection, e.g., by applying Singular Value or QR Decomposition (Ding et al. 2002), Linear Discriminant Analysis (Ding and Li 2007), Givens rotations (Goebl et al. 2014), specialized eigenvalue decompositions (Mautz et al. 2017) or modality-based projection pursuit (Bauer et al. 2023). The actual clustering is then performed in the resulting subspaces, often using variants of k -Means or the EM algorithm, and influences the feature transformation in an iterative manner. Yet, if one wants to receive a lower-dimensional and interpretable representation of count data, these approaches are less practical, as the applied rotations lead to mixtures of features that cannot be easily interpreted. Furthermore, we have no guarantee that the resulting features are integers, so statistical 4

z

∈ C1 ∈ C0 ∈ C− }| { z }| { z }| {

  2 6 Cluster R1  6   32 28 Cluster R2   8  27   21 Cluster R3   18  12

3 9 9 8 7 2 18 14 12 8

C λR i λj|k (Eq. (2)) 2.0 3.0 4.0 1.0 2.0 6.0 9.0 12.0 3.0 6.0 6.0 9.0 12.0 3.0 6.0 32.0 8.0 32.0 8.0 8.0 28.0 7.0 28.0 7.0 7.0 8.0 2.0 8.0 2.0 2.0 27.0 18.0 36.0 9.0 9.0 21.0 14.0 28.0 7.0 7.0 18.0 12.0 24.0 6.0 6.0 12.0 8.0 16.0 4.0 4.0

4 12 12 32 28 8 36 28 24 16

10.0 30.0 30.0 32.0 28.0 8.0 31.5 24.5 21.0 14.0

1 3 3 8 7 2 9 7 6 4

6 7 1 5 7 5 3 10 5 8

25 25 20 20 25 23 20 24 22 25

λR i = {0.02, 0.06, 0.06, 0.16, 0.14, 0.04, 0.18, 0.14, 0.12, 0.08} λC j|− = {16, 9, 20, 5, 5.7, 22.9} C j|0

, 90, 200, 50, 57, 229} → λλ == {{160 100, 150, 200, 50, 100, 500} C j|1

λC j|2 = {200, 50, 200, 50, 50, 200} λC j|3 = {150, 100, 200, 50, 50, 175}

C λR i λj|0 (Eq. (3)) 3.2 1.8 4.0 1.0 1.1 4.6 9.6 5.4 12.0 3.0 3.4 13.7 9.6 5.4 12.0 3.0 3.4 13.7 25.6 14.4 32.0 8.0 9.1 36.6 22.4 12.6 28.0 7.0 8.0 32.1 6.4 3.6 8.0 2.0 2.3 9.2 28.8 16.2 36.0 9.0 10.3 41.2 22.4 12.6 28.0 7.0 8.0 32.1 19.2 10.8 24.0 6.0 6.8 27.5 12.8 7.2 16.0 4.0 4.6 18.3

16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0 16.0

λC j|− (Eq. (4)) 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 9.0 20.0 5.0 5.7 n×m

22.9 22.9 22.9 22.9 22.9 22.9 22.9 22.9 22.9 22.9

Fig. 1: Motivation. The upper matrix shows a data set X ∈ N , where n = 10, m = 6, containing three clusters. Only the first two columns are relevant for clustering (highlighted in yellow, red and dark blue) and therefore belong to C1 . Columns three and four (light blue) equally contribute to all clusters and belong to C0 . Columns five and six (gray) contain (uniformly distributed) noise and belong to C− . The lower C C matrices show the expected values when using λC j|− , λj|0 and λj|k , where the green color highlights the closest expected value compared to X among those three matrices. foundations based on count data like the Poisson distribution cannot be applied. A similar problem is described by Klein et al. (2023) for clustering mixed-type data in a common subspace setting. Their proposal identifies relevant features by comparing the cost function with respect to a so-called clustered space to a noise space that contains a single cluster. Zamzami and Bouguila (2023) identify the number of clusters and the most important features for count data by combining the generalized Dirichlet multinomial with the minimum message length criterion.

3 Definitions, Theory, and Algorithms In this work, the main goal is to partition the n rows of a matrix Y ∈ Nn×m consisting 0 of non-negative integer counts, into K ∈ N>0 clusters Rk ⊆ [n] = {1, . . . , n}, where k ∈ [K ], such that ∪K k=1 Rk = [n] and Rk ∩ Rl = ∅ if k ̸= l. More formally, we define the probability of Yij by using the Poisson distribution as Y

p(Yij , µij ) = Pois(Yij | µij ) ∝ µij ij e−µij . 5

(1)

In our experiments, we use Xij = Yij + 10−3 for numerical stability in place of Yij , which can be interpreted as a weak Gamma prior.1 Following the proposal in, e.g., (Cai et al. 2004), we model the expected number of occurrences µij as a product of row- and column-specific factors. This leads to two main assumptions for the data matrix X: (i) entries within row i are scaled by the rowspecific value λR i and (ii) entries in cluster k follow the proportions as defined by the column and cluster-specific values λC j|k that play a role similar to “cluster centroids” and are ideally different from those of other clusters. These conditions are quite strict and are often not satisfied in practice. Let us consider a hypothetical matrix, where each row contains the word counts of a letter. In most cases, greeting phrases are only contained once, regardless of the length of the letter. This contradicts Assumption (i). In contrast, accompanying words such as ‘the’ usually occur more frequently in longer documents and fulfill Assumption (i). However, their number is probably less dependent on the content (i.e., cluster), which contradicts Assumption (ii). To address these problems, we divide the m columns of the data matrix into three non-overlapping subsets C− , C0 , and C1 , with C− ∪ C0 ∪ C1 = [m]; see Fig. 1. The subset C1 contains those columns that are important for clustering and for which the overall scale of the row matters. For columns j ∈ C1 the Poisson parameter reads C µij = λR i λj|k ,

if

j ∈ C1 and i ∈ Rk ,

(2)

C where λR i ∈ R>0 are the row-specific and λj|k ∈ R>0 for k ∈ [K ] the column-specific parameters. The subset C0 contains those columns where the overall scale does have an effect, but the clusters behave in a similar way (violating Assumption (ii)). For columns j ∈ C0 we have C µij = λR if j ∈ C0 . (3) i λj|0 ,

Finally, the subset C− contains those columns where neither the scale of the row nor the cluster is informative (violating Assumptions (i) and (ii)). The values in columns j ∈ C− are modeled by a column-specific parameter:

µij = λC j|− ,

if

j ∈ C− .

(4)

Since we assume that all entries within a matrix X have been drawn independently, the log-loss of X is given by

L(X) = −

Xn i=1

Xm j=1

log p(Xij , µij ) +

X

b(X·j |K ),

(5)

j∈C1

where b(X·j |K ) ∈ R≥0 is a penalty term related to the column selection, defined in Sect. 3.3. This loss function is scale invariant if b(X·j |K ) = 0, i.e., for all α ∈ R>0 we have L(X) = L(αX). For the details, see Appendix A.3. 1

The full expression with the prior would be: p(Yij , µij ) = Pois(Yij | µij ) × Gamma(µij | α, β) ∝

Y +α−1 −µ µijij e ij

X

∝ µijij e−µij with α = 1 + 10−3 and the second Gamma parameter being β = 0.

6

Our main computational problem is as follows. Problem 1 Given a n × m matrix of counts X, the number of clusters K, and the definitions C given in Eq. (2)-(4), find the parameters {λR i , λj|· }, the clustering R1 , . . . , RK and the column partitions C− , C0 , C1 that minimize the log-loss given by Eq. (5).

We solve Problem 1 using an Expectation Maximization (EM)-type algorithm, where we iterate finding (i) the optimal expected values µij (Sect. 3.1), (ii) the clustering R1 , . . . , RK (Sect. 3.2), and (iii) the column partition C− , C0 , C1 (Sect. 3.3), that at each step maximize the likelihood. This is repeated until convergence. We describe the initialization of C− , C0 , C1 and R1 , . . . , RK in Sect. 3.5. A pseudocode version of our method is given in Algorithm 1. Detailed derivations can be found in Appendix A.

3.1 Finding the Expected Values µij Following the definitions in Eq. (2)–(4), we can find the expected values µij by deterC C C mining the parameters λR i , λj|− , λj|0 and λj|k . The update rules are obtained by solving R the equations ∂L(X)/∂λi = 0 and ∂L(X)/∂λC j|l = 0 for l ∈ {−, 0} ∪ [K ]. Notice that R C C for any constant κ ∈ R>0 , we can multiply all λR i ← κλi and divide all λj|l ← λj|l /κ for l ∈ {0} ∪ [K ] without P affecting the parameters µij . For this reason, we will set, n without loss of generality, i=1 λR i = 1. Given a clustering R1 , . . . , RK and a column partition C1 , C0 , C− , the solutions for the row-specific parameters are

λR i =

P P  (P Xij )( i∈R Xij ) kP j∈C0  Pn j∈C P 0 ∪C1 P (

i=1 j∈C0 Xij )( P Xij  Pn j∈C P1 , i=1 j∈C Xij

i∈Rk

j∈C1 ∪C0 Xij )

,

if

i ∈ Rk and C0 ̸= ∅

if

i ∈ Rk and C0 = ∅

(6)

1

(for details, see Appendix A.2). For the column parameters, we obtain:

λC j|− =

Xn

λC j|0 =

Xn

λC j|k =

i=1

Xij /n,

(7)

Xij , i=1 P P  (P Xij )( n Xij ) k Pi=1 j∈C0  i∈RP , (



P

Xij i∈Rk P j∈CP 0 n i∈Rk Xij )( i=1 j∈C1 Xij ) P P , X ij i∈R j∈C k

(8) if

C0 ̸= ∅

if

C0 = ∅.

(9)

1

We will compute and store the column parameters for all columns to update the column partitions later in Sect. 3.3.

3.2 Finding the Clustering R1 , . . . , RK Similarly, the update rule for the clustering R1 , . . . , RK that maximizes the likelihood when all other parameters are kept fixed is given by computing the score

Sik =

X j∈C1

Xij log µ̂kij − µ̂kij ,

7

(10)

where µ̂kij =

(

P

i∈R̂k Xij )(

P

i∈R̂k

P

P

j∈C1 ∪C0 Xij )

j∈C1 ∪C0 Xij

and R̂k are the cluster assignments from the

last iteration. Finally, we assign each row i ∈ [n] to the cluster k ∈ [K ] with the  highest score Sik , i.e., Rk = i ∈ [n] | k = arg maxk′ ∈[K] Sik′ .

3.3 Finding the Column Partitions C− , C0 , C1 To find the column partitions, we again maximize the likelihood, keeping all other parameters fixed. To this end, we compute the contributions to the log-likelihood Lj (g ) for each column j ∈ [m] and partition g ∈ {−, 0, 1}. We obtain:

Xn

 Xij log λC − λC , j|− j|− i=1    Xn  C R C Lj (0) = Xij log λR λ − λ λ i j|0 i j|0 , i=1     XK X C R C Lj (1) = Xij log λR λ − λ λ i j|k i j|k − b(X·j |K ).

Lj (−) =



k=1

i∈Rk

(11) (12) (13)

Here, we added a penalty term motivated by the Minimum Description Length (MDL) (Rissanen 1978) (see Eq. (5)) defined by

 Xn b(x|K ) = max 0, (K − 1) log

i=1

 xi .

(14)

The intuition is that the additional information to describe parameters λC j|k requires K − 1 cluster-specific column sums (knowingPthe total column sum gives the K -th n sum), each of which can be described by log i=1 Xij bits or less. Other options for the penalty term, such as the Bayesian Information Criterion (BIC) (Schwarz 1978), i.e., b(x|K ) = K 2 log n, are also applicable. To solve Problem 1 we simply assign column j to group Cg such that g = arg maxg′ ∈{−,0,1} Lj (g ′ ).

3.4 Distance Between the Rows In many practical applications, it may be helpful to have a distance measure between the rows. In particular, we use such a distance measure to obtain a better initialization of the clusters (see Sect. 3.5). A natural way to define a distance between items a, b ∈ [n] is to consider a 2 × m submatrix containing only these two rows. The distance can then be computed as the difference in losses of Eq. (5) (assuming C1 = [m], C− = C0 = ∅) between both rows being in the same cluster (R1 = {a, b}) and in individual clusters (R1 = {a}, R2 = {b}). Doing the computations using Eqs. (6)–(9) results in the distance

d(a, b) =

Xm

X i∈{a,b}

j=1

Xij log (Xij Nab / (ri cj )),

(15)

Pm where we used ri = j=1 Xij , cj = Xaj + Xbj , and Nab = ra + rb (details are provided in Appendix A.4). The distance is, to a constant factor, the classical likelihood–ratio test statistic for independence in 2 × m contingency tables. It is always non-negative

8

Algorithm 1: The 3CPO algorithm (without outlier detection) Input: data set X, number of clusters K Output: cluster assignments Rk , column values λC j|k , column partitions C1 , C0 , C− 1 // Initialization (Sect. 3.5) Pn Pn C and λC 2 λj|− ← i=1 Xij i=1 Xij /n j|0 ← Pn C C (X log λ − λ ) 3 Lj (−) ← ij i=1 j|− j|− m 4 C1 ← assign the ⌊ 2 ⌋ columns with the hightest h(j) values (Eq. (16)) to C1 5 C− ← [m] \ C1 and C0 ← ∅ 6 R1 , . . . , RK ← initial cluster assignments by k-Means++ with d(a, b) (Eq. (15)) in C1 7 while C1 , C0 or any Rk changed in last iteration do C 8 λR i , λj|k ← update lambdas (Sect. 3.1) 9 // Update column partitions (Sect. 3.3) 10 for j ∈ [m] do P R C R C 11 Lj (0) ← n i=1 (Xij log(λi λj|0 ) − λi λj|0 ) PK P C R C 12 Lj (1) ← k=1 i∈Rk (Xij log(λR i λj|k ) − λi λj|k ) − b(X·j |K) 13 14 15 16 17 18 19

C− ← {j | j ∈ [m] ∧ Lj (−) ≥ max(Lj (0), Lj (1))} C0 ← {j | j ∈ [m] ∧ j ∈ / C− ∧ Lj (0) ≥ Lj (1)} C1 ← [m] \ (C− ∪ C0 ) // Update cluster assignments (Sect. 3.2) R1 , . . . , R K ← ∅ for i ∈ [n] do P k ← argmax j∈C1 Xij log(µ̂kij ) − µ̂kij (Eq. (10)) k′ ∈[K]

20 21

Rk ← Rk ∪ {i} return Rk , λC j|k , C1 , C0 , C−

and zero only if Xij = ri cj /Nab for all i ∈ {a, b} and j ∈ [m]; in particular, the distance is zero if there exists κ ∈ R>0 such that Xaj = κ Xbj for all j ∈ [m].

3.5 Finding the Initial Values Good initial values result in faster convergence to a better (local) optimum. Initial C− , C0 , C1 . As an initial guess, we set C0 = ∅. Next, we use the following heuristic, motivated by Eq. (15), to measure the potential clustering information h(j ) within each column Xn  h(j ) = Xij log (Xij N/ (ri cj )) /cj , (16) i=1

Pn

Pm

where cj = i=1 Xij and N = j=1 cj 2 . C1 is then defined as the ⌊ m 2 ⌋ columns with the highest h(j ) values. We divide by cj to avoid placing disproportionate weight on columns containing high values. Lastly, we set C− = [m] \ C1 . Alternatively, one can randomly assign the columns in [m] to C− and C1 , so that C− ∩ C1 = ∅. Initial R1 , . . . , RK . Using the k -Means++ (Arthur and Vassilvitskii 2007) seeding mechanism within C1 with d(a, b) as defined by Eq. (15) in place of the Euclidean 2

This formulation is equivalent to the Kullback-Leibler divergence with p = Xij /cj and q = ri /N .

9

distance gives us the K rows Z ∈ R>0 K×|C1 | . Afterward, we receive the initial cluster assignments R1 , . . . , RK by assigning each row in X Pto its best matching P row within Z according to Eq. (10) with Rˆk = {Zk } ⇒ µ̂kij = ( j∈C1 Xij )(Zkj / j∈C1 Zkj ).

3.6 Identifying Outliers In many real-world applications, data sets contain rows that deviate from the clustering model assumptions, potentially degrading clustering quality. To address this, we propose an outlier detection mechanism integrated within the 3CPO framework that intends to demonstrate the expandability of our method. Other outlier detection approaches are also conceivable and can be easily integrated. The core idea is to model outliers using a data set-wide (“background”) column parameter rather than cluster-specific values. Using such a noise distribution is a wellstudied strategy in clustering, e.g., in (Banfield and Raftery 1993). Specifically, rows assigned to the outlier set O ⊆ [n] have their Poisson parameters defined by: C µij = λR i λj|0 ,

if

i ∈ O ∧ j ∈ C0 ∪ C1 ,

(17)

S where k∈K Rk ∪ O = [n] and ∀k∈K Rk ∩ O = ∅. At each iteration (or as a final step, after convergence), rows are assigned to clusters or to the outlier set based on likelihood comparison. For each row i, we compute the score for cluster assignment: Sik =

X j∈C1

X Xij log µ̂kij − µ̂kij −

j∈C1

where µ̂kij is defined in Sect. 3.2 and µ̂0ij =

(

Xij log µ̂0ij − µ̂0ij ,

(18)

Pn P Xij ) i=1 Xij )( Pn P j∈C1 ∪C0 . The score Sik i=1 j∈C ∪C Xij 1

0

quantifies the log-likelihood difference between assigning row i to cluster k versus the background model. We then assign i ∈ Rk if maxk Sik ≥ 0, otherwise i ∈ O. This criterion ensures that rows fitting any cluster better than the background model remain within a cluster. See Appendix A.5 for detailed derivations and update rules.

3.7 Convergence and Complexity Convergence. We see that the steps described in Sects. 3.1, 3.2, and 3.3 always lead to a local optimum. Since there is a finite number of possible clustering solutions and each step is guaranteed not to increase the loss function, 3CPO has to converge. To empirically verify this claim, Fig. 2 shows the loss after each iteration for three data sets. It is evident that the loss is steadily decreasing. The dashes on the bottom also show that it is beneficial to integrate the selection of columns into the optimization instead of performing a simpler pre-/post-processing, as changes can happen at any time due to updates in Rk which often lead to noticeable decreases in the loss. Complexity. As for other clustering algorithms, except for simple methods such as k -Means, for which theoretical results exist (Arthur and Vassilvitskii 2007, 2006), it is challenging to prove approximability or runtime guarantees. However, we can derive the asymptotic computational complexity of our method. Calculating the colC umn parameters λC j|− and λj|0 as well as the bias b(X·j |K ) has to be done only 10

64

2000

41

48

1500

27

32

1000

13

16

500

0

0

Changes of column partitions

0

5

10

Iteration

15

(a) Data set: SportA.

C1 C0 C

Changes of column partitions

0

5

10

15

Iteration

20

25

(b) Data set: Optdigits.

C1 C0 C

|C1|

|C1| Loss

|C1| Loss

Loss C1 C0 C

55

0 Changes of column partitions

0

5

10

Iteration

15

(c) Data set: BBCSports.

Fig. 2: Loss of 3CPO (blue line) and number of columns in C1 (green line) after each iteration. The dashes below indicate changes of C1 (red), C0 (blue) and C− (gray). once, and the complexity is O(nm). Updating the row parameters λR i has a complexity of O(n |C0 ∪ C1 |), and updating the cluster-specific column parameters λC j|k has a complexity of O(nm). The complexity of updating the cluster assignments Rk is O(n |C1 | K ), and for the column partitions C− , C0 and C1 it is O(nm). Assuming I iterations until the process converges gives the worst-case complexity of O(InmK ), indicating that the runtime grows linearly with I , n, m, and K .

4 Experiments We show the applicability of our method by evaluating its performance in various scenarios. In addition, we validate essential design decisions through ablation studies.

4.1 Evaluation Setup We compare 3CPO with various comparison algorithms using multiple evaluation metrics and data sets from different domains. Comparisons. For comparison, we choose multiple clustering algorithms that return hard cluster labels, including the Poisson-based clustering algorithms PoissonL and PoissonC (using our proposed initialization strategy for Rk - see Sect. 3.5) as well as SKM. Furthermore, we consider k -Means (KM) in combination with various transformation functions to account for different normalizations. These are row-wise D z-normalization (STD, XST = (Xij − mean(Xi· ))/std(Xi· )), row-wise min-max ij MM normalization (MM, Xij = (Xij − min(Xi· ))/(max(Xi· ) − min(Xi· ))), relative frequency (RF, XRF /ri ), and revealed comparative advantage (RCA, XRCA = ij = XijP ij Pn Pm m Xij N/(ri cj )). Here, ri = j=1 Xij , cj = i=1 Xij , and N = j=1 cj . In addition, we consider the co-clustering algorithms CROINFO, CoclustMod (CCMod), CoclustSpecMod (CCSMod), ELBM, SELBM, and TauCC. The number of row and column clusters is set according to the ground truth and ELBM and SELBM use a Poisson model. Other parameters follow the defaults in the implementations. All algorithms except TauCC receive the number of ground truth clusters as input parameter. As the comparison algorithms are unable to detect outliers, we use 3CPO without outlier detection if not explicitly mentioned otherwise to ensure a fair comparison. Outlier detection is examined separately in the end of Sect. 4.2. 11

Information regarding the used implementations is given in Appendix C. Data sets. We consider one synthetic and 11 real-world count data sets from various domains: synthetic (Synth), Wholesales (Kelly et al.), Sport Articles (SportA) (Kelly et al.), Optdigits (Kelly et al.), BBCSports (Greene and Cunningham 2006), BBCNews (Greene and Cunningham 2006), WebKB 3 , Reuters21578 (Reuters) (Kelly et al.), 20Newsgroups (20NewsG) (Kelly et al.), Mouse Cell Atlas (MouseAtlas) (Tran et al. 2020), Gene Expression (GeneExp) (Kelly et al.), and Human Dendritic Cells (HDendritic) (Tran et al. 2020). Detailed descriptions of these data sets, including potential pre-processing steps, are provided in Appendix B, and the specific characteristics, i.e., the number of clusters K , rows n, columns m, data ranges, sparsity information, and imbalance ratios, are summarized in Table B1. Metrics. To evaluate our results, we consider the Unsupervised Clustering Accuracy (ACC) (Yang et al. 2010), Normalized Mutual Information (NMI) (Kvalseth 1987) and Adjusted Rand Index (ARI) (Hubert and Arabie 1985). These metrics compare the predicted clustering labels with ground truth labels, where 1 indicates a perfect match and values close to 0 a random assignment. All results are reported in %.

4.2 Evaluation of the Clustering Performance Comparison to traditional Clustering Algorithms. The upper part of Table 1 shows the ARI results of 3CPO and the traditional clustering algorithms, i.e., those not performing a column selection (NMI and ACC results can be found in Appendix D.1). Each entry corresponds to the average and standard deviation (±) of ten executions. Note that each execution itself consists of ten runs, where only the result with the best internal score (e.g., Eq. (5) for 3CPO and inertia for k -Means) is considered. We see that 3CPO is the top performer in eight out of twelve experiments. Considering Synth and BBCSport, it outperforms all competitors by more than 38% and by more than 6% in the case of WebKB. Furthermore, if 3CPO does not perform best, the gap to the best performer is often marginal with differences below 1% in the case of SportA and Optdigits. An exception is Wholesales, where RCA+KM is by far the best algorithm, indicating why RCA is a common technique in economics. However, RCA+KM performs much worse than its competitors in all other scenarios. The only other case in which the gap to the best-performing algorithm exceeds 1% is HDendritic. Here, the difference between 3CPO (79.6 ± 5.8) and the best competitor, PoissonL (83.4 ± 5.2), lies within one standard deviation, indicating that 3CPO often attains results comparable to the top performer. Overall, the strongest competitor is PoissonL, which can be interpreted as a special version of 3CPO with C− = C0 = ∅. Nevertheless, 3CPO yields superior results on most high-dimensional text and biology data sets, underscoring the benefit of explicit column selection. Considering the average across all tested data sets, 3CPO is a good choice in unsupervised scenarios. Comparison to Co-Clustering Algorithms. The lower part of Table 1 shows the ARI results of 3CPO and the co-clustering clustering algorithms (NMI and ACC results can be found in Appendix D.1). The setting is the same as for the traditional approaches. The only exception is TauCC, where each execution corresponds to a single run as the implementation does not include an internal scoring function. 3

https://www.cs.cmu.edu/∼webkb/ (accessed 07.01.2026)

12

Table 1: ARI results (in %) of traditional clustering (top) and co-clustering algorithms (bottom). Entries correspond to the mean of ten executions ± the standard deviation. The best result for each data set and group of algorithms (traditional/co-clustering) is marked in bold, the runner-up is underlined, and the third place is dashed-underlined. Data set

3CPO

PoissonL

PoissonC

SKM

KM

STD+KM

MM+KM

RF+KM

RCA+KM

Synth Wholesales SportA Optdigits BBCSports BBCNews WebKB Reuters 20NewsG MouseAtlas GeneExp HDendritic

95.5 ± 0.0 30.1 ± 0.0 32.3 ± 0.5 66.7 ± 2.2 90.1 ± 2.9 89.9 ± 0.9 31.5 ± 3.2 67.8 ± 1.6 23.0 ± 1.3 56.3 ± 6.2 99.1 ± 0.1 79.6 ± 5.8

33.3 ± 0.1 31.3 ± 0.0 32.5 ± 0.2 67.0 ± 1.8 51.6 ± 8.1 89.2 ± 0.8 25.4 ± 0.9 65.2 ± 5.0 22.2 ± 1.9 55.4 ± 5.0 98.7 ± 0.1 83.4 ± 5.2

29.9 ± 0.0 32.8 ± 0.0 21.9 ± 1.5 45.0 ± 3.1 27.7 ± 4.0 63.4 ± 6.7 20.2 ± 3.8 44.1 ± 4.0 14.6 ± 1.5 18.5 ± 9.5 86.7 ± 11.0 74.8 ± 6.1

42.7 ± 0.0 26.5 ± 0.0 29.5 ± 0.0 67.5 ± 0.1 10.4 ± 1.7 31.5 ± 4.0 11.4 ± 0.2 21.9 ± 0.2 2.0 ± 0.2 39.3 ± 2.6 98.5 ± 0.0 79.9 ± 0.2

0.2 ± 0.0 −3.1 ± 0.0 21.3 ± 0.0 67.1 ± 0.2 0.3 ± 0.2 6.0 ± 0.3 3.6 ± 0.0 15.2 ± 0.6 0.4 ± 0.0 1.6 ± 0.1 98.2 ± 0.1 37.5 ± 13.3

42.1 ± 0.0 28.2 ± 0.0 31.9 ± 0.0 67.6 ± 0.1 9.5 ± 0.9 24.6 ± 1.6 12.0 ± 0.2 32.5 ± 0.1 2.1 ± 0.1 38.4 ± 1.4 99.1 ± 0.1 80.2 ± 0.4

42.9 ± 0.1 27.9 ± 0.2 25.9 ± 0.1 67.3 ± 0.3 6.9 ± 3.6 16.4 ± 1.5 10.9 ± 0.4 31.9 ± 0.0 1.5 ± 0.1 36.3 ± 2.0 98.3 ± 0.0 75.5 ± 0.2

42.5 ± 0.0 21.3 ± 0.0 7.5 ± 0.0 66.5 ± 0.2 9.8 ± 1.7 25.6 ± 1.8 11.0 ± 2.7 3.7 ± 4.2 1.1 ± 0.2 28.6 ± 2.6 98.5 ± 0.1 37.5 ± 13.3

0.0 ± 0.0 47.0 ± 0.3 0.1 ± 0.0 0.0 ± 0.0 3.7 ± 2.6 15.4 ± 12.0 −0.0 ± 0.1 0.3 ± 0.3 0.0 ± 0.0 0.1 ± 0.0 3.7 ± 9.8 −0.1 ± 0.1

Data set

3CPO

CROINFO

CCMod

CCSMod

ELBM

SELBM

TauCC

Synth Wholesales SportA Optdigits BBCSports BBCNews WebKB Reuters 20NewsG MouseAtlas GeneExp HDendritic

95.5 ± 0.0 30.1 ± 0.0 32.3 ± 0.5 66.7 ± 2.2 90.1 ± 2.9 89.9 ± 0.9 31.5 ± 3.2 67.8 ± 1.6 23.0 ± 1.3 56.3 ± 6.2 99.1 ± 0.1 79.6 ± 5.8

32.8 ± 0.3 33.6 ± 0.5 25.4 ± 0.8 49.7 ± 2.1 48.3 ± 5.2 62.1 ± 2.3 20.1 ± 1.4 59.9 ± 1.2 16.2 ± 0.7 49.7 ± 1.8 59.0 ± 3.1 81.9 ± 1.3

25.2 ± 0.1 32.0 ± 0.0 30.3 ± 0.0 21.4 ± 1.5 41.0 ± 4.3 71.9 ± 1.8 20.4 ± 0.7 64.6 ± 4.1 6.9 ± 0.6 38.4 ± 1.8 72.4 ± 2.9 72.2 ± 5.0

17.8 ± 20.8 3.2 ± 9.1 31.4 ± 0.1 33.2 ± 2.9 38.1 ± 0.1 62.3 ± 0.3 25.8 ± 0.1 46.1 ± 0.0 6.2 ± 2.3 27.4 ± 0.1 93.2 ± 0.0 0.0 ± 0.0

9.2 ± 8.6 2.0 ± 5.0 7.1 ± 0.0 45.3 ± 3.0 0.3 ± 0.1 4.5 ± 0.2 3.7 ± 0.1 34.6 ± 0.3 0.5 ± 0.1 1.4 ± 0.3 4.3 ± 1.4 45.1 ± 4.3

3.5 ± 1.6 1.9 ± 0.6 6.5 ± 0.1 23.1 ± 4.3 0.3 ± 0.0 2.9 ± 0.6 0.0 ± 0.0 10.1 ± 1.0 0.0 ± 0.0 0.5 ± 0.1 0.0 ± 0.0 4.0 ± 7.8

25.1 ± 0.6 27.6 ± 0.0 15.8 ± 15.1 10.6 ± 7.5 26.2 ± 6.3 41.8 ± 10.5 11.3 ± 2.0 43.2 ± 0.5 2.1 ± 1.5 34.4 ± 4.6 53.1 ± 9.4 42.3 ± 23.0

Table 2: ARI results (in %) regarding text data sets pre-processed by TF-IDF and BM25. Entries correspond to the mean of ten executions ± the standard deviation. The best performance is highlighted in bold. Data set

3CPO

TF-IDF+KM

BM25+KM

TF-IDF+SKM

BM25+SKM

BBCSports BBCNews WebKB Reuters 20NewsG

90.1 ± 2.9 89.9 ± 0.9 31.5 ± 3.2 67.8 ± 1.6 23.0 ± 1.3

71.0 ± 11.4 84.2 ± 2.8 18.8 ± 1.0 19.3 ± 0.2 5.6 ± 0.6

43.7 ± 17.0 87.7 ± 6.8 14.6 ± 1.3 34.8 ± 5.0 5.5 ± 0.5

76.5 ± 7.1 86.4 ± 0.8 22.4 ± 1.1 34.0 ± 0.2 8.2 ± 0.4

81.1 ± 6.8 90.7 ± 0.3 29.0 ± 1.9 55.8 ± 1.2 21.1 ± 1.2

The results show that 3CPO ranks among the top three across all data sets. The strongest competitor is CROINFO, which outperforms 3CPO on Wholesales and HDendritic while maintaining a low standard deviation in almost all experiments. Considering that TauCC has to determine the number of clusters and only does a single run per execution, its performance is noteworthy as it is often in a similar region as CROINFO, CCMod, and CCSMod. In contrast, ELBM and SELBM appear to struggle with raw features, suggesting they may require additional pre-processing. A detailed look at text data sets: Comparison to TF-IDF. To better assess the performance with respect to the text data sets, we compare 3CPO to k -Means and SKM in combination with term frequency–inverse document frequency (TF-IDF) and BM25 (Robertson and Zaragoza 2009) with its free parameters set to kbm25 = 1.5 and bbm25 = 0.75. The remaining experimental setting corresponds to Table 1. The ARI results are shown in Table 2 (NMI and ACC results can be found in Appendix D.1). 13

Table 3: Clustering results (in %) and the number of outliers |O| when using the outlier detection feature. An asterisk ∗ indicates that only non-outliers are used for the evaluation. Entries correspond to the mean of ten executions ± the standard deviation. Improvements compared to results without outlier detection are marked in bold. Data set

ACC∗

NMI∗

ARI∗

|O|

Data set

ACC∗

NMI∗

ARI∗

|O|

Synth Wholesales SportA Optdigits BBCSports BBCNews

91.9 ± 0.0 86.2 ± 0.2 85.3 ± 0.1 82.1 ± 2.0 98.4 ± 1.1 97.9 ± 0.4

81.7 ± 0.0 47.4 ± 0.5 37.2 ± 0.2 79.2 ± 1.0 95.5 ± 2.0 93.3 ± 0.8

85.4 ± 0.0 52.2 ± 0.7 49.4 ± 0.2 72.6 ± 2.4 95.9 ± 2.7 94.9 ± 0.9

336 ± 0 144 ± 1 341 ± 4 443 ± 3 56 ± 4 137 ± 11

WebKB Reuters 20NewsG MouseAtlas GeneExp HDendritic

56.8 ± 3.7 85.3 ± 7.3 39.8 ± 2.6 72.4 ± 7.7 100.0 ± 0.0 87.7 ± 7.3

39.3 ± 1.1 75.3 ± 7.0 42.7 ± 1.1 75.8 ± 3.5 100.0 ± 0.0 81.5 ± 3.7

33.1 ± 3.0 73.9 ± 8.2 25.4 ± 1.3 64.5 ± 8.2 100.0 ± 0.0 82.6 ± 5.5

431 ± 38 427 ± 275 978 ± 49 1326 ± 84 14 ± 2 22 ± 2

Table 4: Total (m) and cluster-relevant columns (|C1 |) as identified by 3CPO. Entries for |C1 | correspond to the mean of ten executions ± the standard deviation. m |C1 |

Synth

Wholesales

SportA

Optdigits

BBCSports

BBCNews

WebKB

Reuters

20NewsG

MouseAtlas

GeneExp

HDendritic

6 2±0

6 5±0

55 41 ± 1

64 56 ± 1

2000 799 ± 8

2000 1379 ± 6

2000 1315 ± 18

2000 1322 ± 8

2000 1454 ± 15

15006 14566 ± 59

20531 6445 ± 3

26593 16673 ± 406

We see that 3CPO performs best in four out of five scenarios. It outperforms the runner-up, BM25+SKM, by a substantial margin on BBCSports and Reuters. In general, the experiments indicate the applicability of 3CPO for text data. Furthermore, as it uses raw word counts and discovers a subset of relevant columns, its results are more interpretable than those of more sophisticated word embeddings like Word2Vec (Mikolov et al. 2013) or BERT (Devlin et al. 2019). This can benefit a subsequent analysis of the results, allowing domain experts to identify key terms driving cluster definitions. Our main experiments further demonstrate that 3CPO can be applied to data from various domains and is not restricted to texts. Performance with Outlier Detection. We further evaluate 3CPO when incorporating the optional “background” component for outlier detection. Table 3 shows the results where metrics (denoted by ∗) are calculated only on non-outlier samples. Using the outlier detection method, 3CPO is able to improve the clustering scores for all data sets except Synth, indicating that it successfully identifies rows that are hard to assign to any specific cluster. This behavior is practically valuable since declaring uncertain samples as outliers can prevent wrong cluster assignments leading to false conclusions. The proportion of identified outliers varies considerably across data sets, exceeding 10% for Synth, Wholesales, SportA, and MouseAtlas. While this reduces the clustering task’s complexity, it also reflects genuine data characteristics where many samples lack clear cluster membership. We want to highlight the result regarding GeneExp, where 3CPO achieves a perfect clustering result while only identifying ∼ 14 outliers. Appendix D.4 provides visual examples of outliers identified within Optdigits.

4.3 Analysis of the Column Partitions In addition to the clustering performance, we analyze the number of columns selected as relevant for the clustering task, i.e., the number of columns in C1 . These results are shown in Table 4. For many high-dimensional data sets such as BBCSports, BBCNews, WebKB, Reuters, 20NewsG, and GeneExp, 3CPO noticeable reduces the number of 14

# Zero entries per column in X

600

# Zero entries per column in C0

500

500

200

400

150

300

200

100

200

100

50

400 300

0 300

0

0

100 200 300 400 500 600 700

# Zero entries per column in C1 80

200

60

150

0

100 200 300 400 500 600 700

350 300 250 200 150 100 50 0

40

100

20

50 0

100 0

# Zero entries per column in C

250

0

100 200 300 400 500 600 700

0

# Zero entries per column in X

600

250

200

300

400

500

600

700

(a) BBCSports data set.

0

500

1000

1500

2000

# Zero entries per column in C1

# Zero entries per column in C0 200 175 150 125 100 75 50 25 0 20

0

500

1000

1500

2000

# Zero entries per column in C

15 10 5 0

500

1000

1500

2000

0

1700 1800 1900 2000 2100 2200

(b) BBCNews data set.

Fig. 3: Histograms showing the amount of zeros per column in each column partition.

C Table 5: The ten most important words (based on the largest difference λC j|l − λj|0 for j ∈ C1 and based on the largest λC j|l for j ∈ C0 ∪ C− ) within the BBCSports and BBCNews data sets per column partition and cluster as identified by 3CPO. C C Most important words w.r.t. λC j|l − λj|0 or λj|l (stemmed)

Data set

Partition + Cluster

BBCSports BBCSports BBCSports BBCSports BBCSports BBCSports BBCSports

C1 C1 C1 C1 C1 C0 C−

1 (⇒ l = 1) 2 (⇒ l = 2) 3 (⇒ l = 3) 4 (⇒ l = 4) 5 (⇒ l = 5) (⇒ l = 0) (⇒ l = −)

‘half’, ‘six’, ‘their’, ‘franc’, ‘nation’, ‘the’, ‘rugbi’, ‘ireland’, ‘wale’, ‘england’ ‘year’, ‘indoor’, ‘world’, ‘race’, ‘athlet’, ‘her’, ‘olymp’, ‘she’, ‘in’, ‘the’ ‘four’, ‘day’, ‘by’, ‘run’, ‘his’, ‘test’, ‘wicket’, ‘over’, ‘off’, ‘ball’ ‘the’, ‘australian’, ‘she’, ‘her’, ‘final’, ‘in’, ‘seed’, ‘roddick’, ‘set’, ‘open’ ‘unit’, ‘leagu’, ‘have’, ‘chelsea’, ‘club’, ‘that’, ‘he’, ‘is’, ‘we’, ‘it’ ‘as’, ‘at’, ‘with’, ‘but’, ‘was’, ‘on’, ‘for’, ‘of’, ‘and’, ‘to’ ‘former’, ‘move’, ‘face’, ‘month’, ‘week’, ‘old’, ‘intern’, ‘injuri’, ‘last’, ‘said’

Ground Truth Fit Rugby Athletics Cricket Tennis Football – –

BBCNews BBCNews BBCNews BBCNews BBCNews BBCNews BBCNews

C1 C1 C1 C1 C1 C0 C−

1 (⇒ l = 1) 2 (⇒ l = 2) 3 (⇒ l = 3) 4 (⇒ l = 4) 5 (⇒ l = 5) (⇒ l = 0) (⇒ l = −)

‘tori’, ‘blair’, ‘would’, ‘govern’, ‘said’, ‘parti’, ‘elect’, ‘labour’, ‘he’, ‘mr’ ‘music’, ‘was’, ‘for’, ‘award’, ‘best’, ‘of’, ‘in’, ‘and’, ‘film’, ‘the’ ‘player’, ‘after’, ‘england’, ‘game’, ‘play’, ‘win’, ‘we’, ‘his’, ‘he’, ‘but’ ‘said’, ‘firm’, ‘bank’, ‘market’, ‘compani’, ‘us’, ‘of’, ‘it’, ‘in’, ‘the’ ‘can’, ‘user’, ‘phone’, ‘game’, ‘are’, ‘peopl’, ‘that’, ‘technolog’, ‘mobil’, ‘use’ ‘about’, ‘new’, ‘up’, ‘their’, ‘an’, ‘this’, ‘will’, ‘as’, ‘is’, ‘to’ ’12’, ‘earlier’, ‘20’, ‘januari’, ‘charg’, ‘2003’, ‘third’, ‘dure’, ‘follow’, ‘week’

Politics Entertainment Sport Business Tech – –

selected columns. Our main takeaway is that our approach fulfills its goal by outperforming PoissonL in most cases, while considering less columns for clustering, e.g., only ∼ 32% in the case of GeneExp. Noteworthy is also the result for BBCSports, where 3CPO outperforms all competitors while only using ∼ 40% of the columns. As count matrices often contain many zero entries (see Table B1), we further investigate whether 3CPO simply filters out columns that contain mostly zeros. To disprove this hypothesis, we analyze the amount of zero entries per column in the whole data X as well as in C1 , C0 and C− . The histograms in Fig. 3 illustrate that the general distribution of the zero entries per column is similar across all column partitions. This applies to data sets where only ∼ 40% of the columns are put into C1 (see BBCSports) and to data sets where more than 65% of the columns are assigned to C1 (see BBCNews). This confirms that 3CPO’s performance is driven by structural patterns in the count data rather than a trivial filtering of zero-heavy columns. Lastly, we provide a qualitative analysis of the column partitioning using the text data sets BBCSports and BBCNews. We identify the most discriminative words in C1 15

0.8 0.5

0.8 0.5

0.6 0.0

0.6 0.0

ARI

1.0 1.0

ARI

1.0 1.0

0.5 0.2

0.5 0.2

1.0 0.4

0.0 0.0

0.0 0

1.0 0.4

0.210

0.4 20

0.6 30

# Noise Columns

400.8

501.0

0.0 0.0

0.0 0

0.220

0.4 40

0.6 60

800.8

Maximum Noise Value

1001.0

3CPO PoissonL PoissonC SKM KM STD+KM MM+KM RF+KM RCA+KM CROINFO CoclustMod CoclustSpecMod ELBM SELBM TauCC

(a) Increasing the amount of noise (b) Increasing the maximum value columns. within the noise column.

Fig. 4: Robustness experiments investigating the impact of columns containing uniformly distributed noise on the clustering performance (measured by ARI). The upper plots show traditional clustering algorithms and the lower plots show co-clustering algorithms. In (a) we increase the amount noise columns with values within [0, 15] and in (b) we have a single noise column with values within [0, u] (u is given on the x-axis). C for each cluster by calculating the difference λC j|k − λj|0 . Additionally, we report the C most frequent words in C0 and C− , characterized by λC j|0 and λj|− , respectively. The results are shown in Tab. 5. 3CPO is able to capture essential cluster characteristics (e.g., ‘party’ and ‘govern’ for ‘Politics’ or ‘athlete’ and ‘olymp’ for ‘Athletics’) and also recognizes irrelevant words (e.g., stop words) by moving them into C0 and C− .

4.4 Robustness to Noise Columns We investigate the robustness of 3CPO with respect to noise columns by conducting two experiments. The basis for these experiments is the Synth data set, where we only consider the first four columns (C1 and C0 ). In the first experiment (Fig. 4a), we add an increasing number of columns containing uniformly distributed values within [0, 15]. The results show that 3CPO is the only algorithm that is not affected by these noise columns, as the ARI is constantly 1.0, indicating that it successfully assigns all those columns into C− . In the second experiment (Fig. 4b), we add a single column containing uniformly distributed values within [0, u], where u ∈ [1, 100]. Here, all traditional clustering algorithms except KM and RCA+KM perform well if u ≤ 7. With respect to the co-clustering algorithms only CROINFO returns good results if u ≤ 18. However, with increasing u, 3CPO is the only method that still returns high-quality results until around u = 32.

4.5 Ablation Studies We conduct a series of experiments in which certain components of our method are ignored. Here, we fix C− = ∅, C0 = ∅, ignore the penalty for column selection by setting b(x|K ) = 0, or use BIC as the penalty for column selection as described in Sect. 3.3. The results are summarized in Table 6. As our proposed version of 3CPO 16

Table 6: ARI results (in %) and the final number of columns included in C1 of various ablation studies. Entries correspond to the mean of ten executions ± the standard deviation. Colors indicate whether the average performance of 3CPO lies above (green), within (yellow) or below (red) the standard deviation band, where above is better for ARI and below is better for |C1 |. Data set

Metric

3CPO

C− = ∅

C0 = ∅

b(X·j ) = 0

b(X·j ) = BIC(X·j )

Synth

ARI |C1 |

95.5 ± 0.0 2.0 ± 0.0

33.3 ± 0.1 5.8 ± 0.6

95.5 ± 0.0 4.0 ± 0.0

95.5 ± 0.0 4.0 ± 0.0

95.5 ± 0.0 2.0 ± 0.0

Wholesales

ARI |C1 |

30.1 ± 0.0 5.0 ± 0.0

31.3 ± 0.0 6.0 ± 0.0

30.1 ± 0.0 5.0 ± 0.0

30.1 ± 0.0 5.0 ± 0.0

30.1 ± 0.0 5.0 ± 0.0

SportA

ARI |C1 |

32.3 ± 0.5 41.1 ± 1.4

32.3 ± 0.1 42.5 ± 1.1

32.6 ± 0.2 52.0 ± 0.0

32.6 ± 0.2 52.0 ± 0.0

32.5 ± 0.3 41.3 ± 0.9

Optdigits

ARI |C1 |

66.7 ± 2.2 55.8 ± 0.6

66.9 ± 1.8 56.0 ± 0.0

66.8 ± 2.2 56.0 ± 0.0

66.8 ± 2.2 62.0 ± 0.0

66.8 ± 2.2 56.0 ± 0.0

BBCSports

ARI |C1 |

90.1 ± 2.9 799.2 ± 7.6

78.0 ± 8.2 860.6 ± 28.1

75.2 ± 8.5 1218.8 ± 14.5

63.3 ± 7.6 1953.7 ± 5.9

87.0 ± 6.3 720.8 ± 14.7

BBCNews

ARI |C1 |

89.9 ± 0.9 1379.0 ± 6.2

90.1 ± 0.7 1437.4 ± 4.5

89.6 ± 0.7 1758.4 ± 2.3

89.5 ± 0.4 1984.8 ± 2.3

90.1 ± 0.7 1367.4 ± 6.1

WebKB

ARI |C1 |

31.5 ± 3.2 1314.9 ± 18.4

24.9 ± 1.1 1407.9 ± 42.5

33.8 ± 3.5 1854.2 ± 6.8

32.6 ± 2.7 1936.2 ± 4.6

30.9 ± 2.5 1282.7 ± 19.2

Reuters

ARI |C1 |

67.8 ± 1.6 1321.9 ± 7.9

65.7 ± 5.1 1390.7 ± 29.1

67.2 ± 3.3 1914.6 ± 2.1

65.4 ± 4.2 1976.0 ± 1.7

68.3 ± 1.3 1213.3 ± 11.7

20NewsG

ARI |C1 |

23.0 ± 1.3 1453.7 ± 15.3

23.2 ± 1.7 1456.7 ± 13.1

22.4 ± 1.0 1990.5 ± 0.8

22.5 ± 0.9 1999.0 ± 0.0

22.8 ± 2.0 1564.4 ± 10.4

MouseAtlas

ARI |C1 |

56.3 ± 6.2 14566.0 ± 58.8

55.4 ± 5.0 14753.0 ± 14.8

56.3 ± 6.2 14650.3 ± 26.2

56.3 ± 6.2 14736.9 ± 21.3

56.2 ± 6.2 14550.3 ± 60.4

GeneExp

ARI |C1 |

99.1 ± 0.1 6445.1 ± 3.1

98.7 ± 0.1 7652.8 ± 3.0

99.1 ± 0.1 7718.8 ± 3.0

98.8 ± 0.1 14135.0 ± 0.0

99.0 ± 0.2 8065.6 ± 5.3

HDendritic

ARI |C1 |

79.6 ± 5.8 16672.9 ± 406.2

83.4 ± 5.2 23694.0 ± 388.1

79.6 ± 5.8 17599.1 ± 393.0

79.6 ± 5.7 20094.5 ± 274.9

79.6 ± 5.7 16574.9 ± 343.4

never performs significantly worse than a competitor, it is considered the most reliable across all experiments. In addition, it usually identifies a solution with fewer selected columns. We see that ignoring b(x|K ) and setting C0 = ∅ leads to similar results, including a significant increase in the number of selected columns without positively influencing the clustering results. This confirms our hypothesis that a penalty term is needed to identify columns that behave similarly for all clusters. In many cases, removing such columns positively influences the clustering, as less noise is included in the final result. This is particularly evident with BBCSports and 20NewsG. Without the integration of C− , 3CPO also has trouble properly clustering WebKB. When using b(x|K ) = BIC (X·j |K ) instead of the MDL-based formulation, the results are very similar, indicating stability w.r.t. the choice of b(x|K ). We want to emphasize that in situations where the proposed variant of 3CPO does not perform best (e.g., in the case of SportA), the difference is usually small and within the standard deviation.

4.6 Estimating the Number of Clusters In many unsupervised scenarios, the number of clusters K is unknown to the user. Therefore, it is a significant advantage if an algorithm gives guidance on how to define this value. Similarly to our penalty term b(x|K ), we define an MDL-based penalty term to describe different parameterizations for K : v (K ) = L0 (K ) + n log K , where L0 (·) is the universal prior for integers (Rissanen 1983). This term encodes the number of clusters by L0 (K ) and the cluster assignments by n log K . Note that the clusterspecific column values are already encoded by b(x|K ). The penalty v (K ) is added to Eq. (5) to prevent the model from overfitting when increasing K .

17

|C1| 3 2 1

5

10

15

K

20

25

30

(a) Synth (Kgt = 3).

0

K=6

5

10

15

K

20

25

30

(b) GeneExp (Kgt = 5).

K=5

5

2000 1750 1500 1250 1000 750 500 250 0

|C1|

4

K=3

20000 17500 15000 12500 10000 7500 5000 2500 0

|C1| Loss (incl. penalty for K)

5

Loss (incl. penalty for K)

Loss (incl. penalty for K)

6

10

15

K

20

25

30

(c) BBCSports (Kgt = 5).

Fig. 5: Loss of 3CPO (incl. the penalty term v (K ) – blue line) and number of columns in C1 (green line) for varying K . Each entry corresponds to the best loss after 20 runs. The red line marks the K for which the minimum loss occurs.

Fig. 5 shows the extended loss, i.e., LK (X) = L(X) + v (K ), and the number of columns in C1 of 3CPO for Synth, GeneExp, and BBCSports using K ∈ {2, 3, . . . , 30}. To receive more reliable results, each entry corresponds to the best result after 20 runs. We notice that the number of columns in C1 decreases with increasing K as b(x|K ) depends on K . Yet, 3CPO identifies the ground truth K for Synth and BBCSports and is only off by one for GeneExp. When analyzing the identified clusters regarding GeneExp, we see that 3CPO splits the largest ground truth cluster with 300 samples into two clusters of size 65 and 235, leading to an ARI of 87.9. This behavior potentially offers additional insights for domain experts. In the case of Synth, we can see a conspicuous bump in the loss at K = 9 due to the fifth column containing uniformly distributed noise. Here, 3CPO subdivides each ground truth cluster into three additional clusters, e.g., by dividing the noise into ranges [0, 5], [6, 10], and [11, 15]. Appendix E provides results (estimated K , ARI, Purity) for all data sets, discusses k -Means-based k -estimation techniques and states results regarding the number of clusters as identified by TauCC. In general, our experiments show that 3CPO can obtain high quality results without knowing the ground truth number of clusters when dealing with high-dimensional text data sets but struggles with certain tabular data.

5 Limitations Despite its robust clustering performance and options for interpretability, 3CPO possesses certain limitations that provide avenues for future research. First, the model assumes a Poisson-based structure. While effective for many count data scenarios, this may be sub-optimal for data sets exhibiting significant overdispersion or zero-inflation beyond the Poisson mean-variance identity. Extending the methodologies to other distributions such as the negative binomial would enhance its versatility. Second, the current definition of the penalty term for column selection, b(x|K ), and the encoding of outliers are subject to heuristic choices. As the number of clusters K currently influences feature selection, the model may converge to undesired local optima in specific high-dimensional settings. Finally, another issue is that 3CPO requires the number of clusters to be known apriori. While we propose a heuristic to estimate the number of clusters for 3CPO, a more cohesive integration – akin to the iterative splitting 18

approach of X -Means (Pelleg and Moore 2000) – could further improve the quality and stability of the process, increasing the applicability in real-world scenarios where the number of clusters is often unknown.

6 Discussion and Conclusions We introduced 3CPO, a principled approach for clustering count data with integrated column selection that combines theoretical rigor with practical efficiency. The method outputs a hard clustering of rows and simultaneously finds a subset of columns that are relevant for clustering. We found that 3CPO outperforms the compared methods in many scenarios. Notably, our approach often beats tailored bag-of-words text representations for text data, indicating its general applicability. Beyond competitive performance on standard benchmarks, 3CPO shows a superior performance in noisy settings. The integration of a Poisson-based noise model enables 3CPO to outperform clustering methods using normalized versions of the count matrix, e.g., by applying RCA. Our outlier detection feature further improves clustering quality by highlighting samples that do not fit the underlying clustering assumptions. This opens up interesting possibilities for future work, for example, by refining the outlier detection mechanism and integrating an automatic estimation of the number of clusters.

Acknowledgements. We thank the Research Council of Finland (decisions 364226, 368654) and the Technology Industries of Finland Centennial Foundation for funding. We thank the Finnish Computing Competence Infrastructure (FCCI) for computational and data storage resources.

Declarations The authors have no competing interests to declare.

References Ailem, M., Role, F., Nadif, M.: Co-clustering document-term matrices by direct maximization of graph modularity. In: CIKM, pp. 1807–1810 (2015). ACM Ailem, M., Role, F., Nadif, M.: Model-based co-clustering for the effective handling of sparse data. Pattern Recognit. 72, 108–122 (2017) Ailem, M., Role, F., Nadif, M.: Sparse poisson latent block model for document clustering. IEEE Trans. Knowl. Data Eng. 29(7), 1563–1576 (2017) Arthur, D., Vassilvitskii, S.: How slow is the k -means method? In: ACM SCG, pp. 144–153 (2006) Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: SIAM SODA, pp. 1027–1035 (2007)

19

Balassa, B.: Trade Liberalisation and “Revealed” Comparative Advantage. The Manchester School 33(2), 99–123 (1965) Bauer, L.G.M., Leiber, C., Böhm, C., Plant, C.: Extension of the dip-test repertoire - efficient and differentiable p-value calculation for clustering. In: SIAM SDM, pp. 109–117 (2023) Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent Dirichlet Allocation. J. Mach. Learn. Res. 3, 993–1022 (2003) Bouguila, N.: Clustering of count data using generalized dirichlet multinomial distributions. IEEE Trans. Knowl. Data Eng. 20(4), 462–474 (2008) Bouguila, N.: Count data modeling and classification using finite mixtures of distributions. IEEE Trans. Neural Networks 22(2), 186–198 (2011) Battaglia, E., Peiretti, F., Pensa, R.G.: Fast parameterless prototype-based coclustering. Mach. Learn. 113(4), 2153–2181 (2024) Battaglia, E., Peiretti, F., Pensa, R.G.: Co-clustering: A survey of the main methods, recent trends, and open problems. ACM Comput. Surv. 57(2), 48–14833 (2025) Banfield, J.D., Raftery, A.E.: Model-based gaussian and non-gaussian clustering. Biometrics, 803–821 (1993) Ceder, A.: Bus frequency determination using passenger count data. Transp. Res. A 18(5-6), 439–453 (1984) Cai, L., Huang, H., Blackshaw, S., Liu, J.S., Cepko, C., Wong, W.H.: Clustering analysis of sage data using a poisson approach. Genome Biol. 5, 1–9 (2004) Devlin, J., Chang, M., Lee, K., Toutanova, K.: BERT: pre-training of deep bidirectional transformers for language understanding. In: Association for Computational Linguistics NAACL-HLT (1), pp. 4171–4186 (2019) Ding, C.H.Q., He, X., Zha, H., Simon, H.D.: Adaptive dimension reduction for clustering high dimensional data. In: Proc. IEEE ICDM 2002, pp. 147–154 (2002) Dubes, R.C., Jain, A.K.: Clustering techniques: The user’s dilemma. Pattern Recognit. 8(4), 247–260 (1976) Ding, C.H.Q., Li, T.: Adaptive dimension reduction using discriminant analysis and K -means clustering. In: ICML. ACM International Conference Proceeding Series, vol. 227, pp. 521–528 (2007) Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the em algorithm. J. R. Stat. Soc. Ser. B 39(1), 1–22 (1977)

20

Dhillon, I.S., Modha, D.S.: Concept decompositions for large sparse text data using clustering. Mach. Learn. 42, 143–175 (2001) Elkan, C.: Clustering documents with an exponential-family approximation of the dirichlet compound multinomial distribution. In: ICML, vol. 148, pp. 289–296 (2006) Farnsworth, G.L., Nichols, J.D., Sauer, J.R., Fancy, S.G., Pollock, K.H., Shriner, S.A., Simons, T.R., Ralph, C., Rich, T.: Statistical approaches to the analysis of point count data: a little extra information can go a long way. In: Proc. 3rd Int. Partners Flight Conf., vol. 2, pp. 736–743 (2005) Greene, D., Cunningham, P.: Practical solutions to the problem of diagonal dominance in kernel document clustering. In: ICML, vol. 148, pp. 377–384 (2006). ACM Gopalan, P., Hofman, J.M., Blei, D.M.: Scalable recommendation with hierarchical poisson factorization. In: AUAI Press UAI, pp. 326–335 (2015) Goebl, S., He, X., Plant, C., Böhm, C.: Finding the optimal subspace for clustering. In: Proc. IEEE ICDM 2014, pp. 130–139 (2014) Govaert, G., Nadif, M.: Latent block model for contingency table. Communications in Statistics—Theory and Methods 39(3), 416–425 (2010) Govaert, G., Nadif, M.: Mutual information, phi-squared and model-based coclustering for contingency tables. Adv. Data Anal. Classif. 12(3), 455–488 (2018) Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2, 193–218 (1985) Hoseinipour, S., Aminghafari, M., Mohammadpour, A., Nadif, M.: A sparse exponential family latent block model for co-clustering. Adv. Data Anal. Classif. 19(4), 951–987 (2025) Hargesheimer, E.E., Lewis, C.M.: Particle counting: How, why, where, & what equipment. Alberta WW Oper. Assoc. (1998) Kriegel, H.-P., Kröger, P., Zimek, A.: Subspace clustering. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 2(4), 351–364 (2012) Klein, M., Leiber, C., Böhm, C.: k-submix: Common subspace clustering on mixedtype data. In: ECML/PKDD (1). Springer Lecture Notes in Computer Science, vol. 14169, pp. 662–677 (2023) Kelly, M., Longjohn, R., Nottingham, K.: The UCI Machine Learning Repository Kvalseth, T.O.: Entropy and correlation: Some comments. IEEE Trans. Syst. Man Cybern. 17(3), 517–519 (1987)

21

Kim, K., Zhang, S., Jiang, K., Cai, L., Lee, I.-B., Feldman, L.J., Huang, H.: Measuring similarities between gene expression profiles through new data transformations. BMC Bioinform. 8, 1–14 (2007) Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129– 136 (1982) Labiod, L., Nadif, M.: Co-clustering for binary data with maximum modularity. In: ICONIP, pp. 700–708 (2011). Springer Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. arXiv:1301.3781 (2013) Manning, C.D., Raghavan, P., Schütze, H.: Introduction to Information Retrieval, (2008). Cambridge University Press Müllner, D.: Modern hierarchical, agglomerative clustering algorithms. arXiv preprint arXiv:1109.2378 (2011) Mautz, D., Ye, W., Plant, C., Böhm, C.: Towards an optimal subspace for k-means. In: Proc. ACM SIGKDD 2017, pp. 365–373 (2017) Nadif, M., Govaert, G.: A comparison between block CEM and two-way CEM algorithms to cluster a contingency table. In: PKDD. Springer Lecture Notes in Computer Science, vol. 3721, pp. 609–616 (2005) O’Hara, R., Kotze, J.: Do not log-transform count data. Nat. Precedings (2010) Pelleg, D., Moore, A.W.: X-means: Extending k-means with efficient estimation of the number of clusters. In: ICML, pp. 727–734 (2000) Rouwendal, J., Boter, J.: Assessing the value of museums with a combined discrete choice/count data model. Applied Economics 41(11), 1417–1436 (2009) Rau, A., Celeux, G., Martin-Magniette, M.-L., Maugis-Rabusseau, C.: Clustering highthroughput sequencing data with poisson mixture models. Research Report RR7786, INRIA (2011) Rissanen, J.: Modeling by shortest data description. Automatica 14(5), 465–471 (1978) Rissanen, J.: A universal prior for integers and estimation by minimum description length. Ann. Stat. 11(2), 416–431 (1983) Role, F., Morbieu, S., Nadif, M.: Coclust: a python package for co-clustering. Journal of Statistical Software 88, 1–29 (2019) Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of

22

cluster analysis. Comput. Appl. Math. 20, 53–65 (1987) Robertson, S.E., Zaragoza, H.: The probabilistic relevance framework: BM25 and beyond. Found. Trends Inf. Retr. 3(4), 333–389 (2009) Satopaa, V., Albrecht, J.R., Irwin, D., Raghavan, B.: Finding a ”kneedle” in a haystack: Detecting knee points in system behavior. In: ICDCS Workshops, pp. 166–171 (2011). IEEE Schwarz, G.: Estimating the dimension of a model. The annals of statistics, 461–464 (1978) Snow, L., Davies, R., Christiansen, K., Carrique-Mas, J., Wales, A., O’connor, J., Cook, A., Evans, S.: Survey of the prevalence of salmonella species on commercial laying farms in the united kingdom. Vet. Rec. 161(14), 471–476 (2007) Sim, K., Gopalkrishnan, V., Zimek, A., Cong, G.: A survey on enhanced subspace clustering. Data Min. Knowl. Discov. 26, 332–397 (2013) Tran, H.T.N., Ang, K.S., Chevrier, M., Zhang, X., Lee, N.Y.S., Goh, M., Chen, J.: A benchmark of batch-effect correction methods for single-cell rna sequencing data. Genome biology 21(1), 12 (2020) Thorndike, R.L.: Who belongs in the family? Psychometrika 18(4), 267–276 (1953) Waltman, L., Calero-Medina, C., Kosten, J., Noyons, E.C., Tijssen, R.J., Eck, N.J., Leeuwen, T.N., Raan, A.F., Visser, M.S., Wouters, P.: The leiden ranking 2011/2012: Data collection, indicators, and interpretation. J. Am. Soc. Inf. Sci. Technol. 63(12), 2419–2432 (2012) Witten, D.M.: Classification and clustering of sequencing data using a poisson model. Ann. Appl. Stat. 5(4), 2493–2518 (2011) Xu, R., Wunsch II, D.C.: Survey of clustering algorithms. IEEE Trans. Neural Networks 16(3), 645–678 (2005) Yang, Y., Xu, D., Nie, F., Yan, S., Zhuang, Y.: Image clustering using local discriminant models and global integration. IEEE Trans. Image Process. 19(10), 2761–2773 (2010) Zamzami, N., Bouguila, N.: High-dimensional count data clustering based on an exponential approximation to the multinomial beta-liouville distribution. Information Sciences 524, 116–135 (2020) Zamzami, N., Bouguila, N.: A novel minorization-maximization framework for simultaneous feature selection and clustering of high-dimensional count data. Pattern Anal. Appl. 26(1), 91–106 (2023)

23

Appendix A

A Poisson-based Clustering Model

The Poisson distribution is a natural foundation when working with count data. The probability mass function regarding a discrete random variable Xij is defined as X

p(Xij | µij ) =

µij ij −µij e , (Xij )!

(A1)

where µij are the expected number of occurrences. Since we assume that all entries have been drawn independently, the likelihood of a given n × m data matrix X is given by

p(X | µ) =

n Y m Y

p(Xij | µij ).

(A2)

i=1 j=1

If we do not restrict the parameters µij , the solution is trivially to set the parameters equal to the observations or µij = Xij . However, this will lead to overfitting because the number of parameters equals the number of observations. Therefore, we need some simplifying modeling assumptions. We follow the definition given, e.g., in (Cai et al. 2004; Kim et al. 2007), where the mean is a product of row- and column-specific factors C µij = λR i λj ,

(A3)

C where λR i ∈ R>0 and λj ∈ R>0 . This concept is closely related to Poisson Factorization (Gopalan et al. 2015). We can compute optimal values for the parameters λR i and λC j so that the likelihood of Eq. (A2) is maximized by applying Maximum Likelihood Estimation (MLE). Since argmaxµ∈R>0 p(X | µ) = argmaxµ∈R>0 log(p(X | µ)) our objective can be formulated as to maximizing the following function

  n Y m C Xij Y
(λR λ ) R C i j e−(λi λj )  log p(X | µ) = log  ( X )! ij i=1 j=1 =

n X m X

(A4)

C R C Xij log(λR i ) + Xij log(λj ) − (λi λj ) − log((Xij )!).

i=1 j=1

Setting the first derivative regarding λR i to zero yields !

0=

m
X ∂ Xij log p ( X | µ ) = − λC j R ∂λR λ i i j=1

m X 1 P ⇔ λR = Xij . m i C j=1 λj j=1

24

(A5)

Analogously, when considering the derivative regarding λC j , we obtain

λC j = Pn

n X

1

R i=1 λi i=1

Xij .

(A6)

R Note that for any constant κ ∈ R>0 , we can divide λR λC i ← λi /κ and multiply j ← P m C C κλj without affecting the parameters µij . Therefore, w.l.o.g. we can set j=1 λj = 1. This yields

λR i =

m X

Xij = ri

and

j=1

n X cj cj 1 C P Xij = Pn = λj = n N r r i=1 i i=1 i=1 i

(A7)

and finally

ri cj µij = Pn i′ =1

ri′

ri cj = Pm j ′ =1

cj ′

=

ri cj . N

(A8)

Standardization using the Poisson Model. The described Poisson model can be used to apply a Poisson-based standardization (or z-normalization) to a data matrix X. We show how this relates to Chi-squared and the Revealed Comparative Advantage (RCA) (Balassa 1965). The standard score of an entry Xij is calculated as STD(Xij ) =

Xij − µij . σij

(A9)

Considering that in the case of the Poisson distribution µ = σ 2 , the Poisson-based standard score can be formulated as P-STD(Xij ) =

Xij − µij . √ µij

(A10)

Note that this formulation is equal to the square root of Pearson’s Chi-squared test, p i.e., P-STD(Xij ) = X 2 (Xij ). Furthermore, we can consider a generalized version of P-STD with a weighting factor α for the denominator (which is set to 0.5 in Eq. (A10)). P-STD(Xij , α) =

Xij − µij (µij )α

(A11)

If α = 1, this formulation is equal to the RCA up to a constant of −1, i.e., P-STD(Xij , 1) =

Xij − µij Xij N = − 1 = RCA(Xij ) − 1. (µij )1 ri cj

25

(A12)

As P-STD with α = 0.5 builds on a solid statistical model that takes into account increasing variances for larger expected values, we argue that it is more robust with regard to noisy data than RCA.

A.1

PoissonL/PoissonC: Poisson-based Clustering

The described Poisson model was used to propose the PoissonL and PoissonC algorithms (Cai et al. 2004) for clustering gene expression data. However, as shown in our experiments, they are not only applicable to gene expression data but also more generally to count data. The objective is to divide the data into K ∈ N>0 sets of rows Rk that show a similar relationship between the columns and, therefore, can be modeled using the described Poisson model by representing each set of rows Rk using a specific λC j|k ∈ R>0 . This can be formulated as minimizing the loss function

L(X) = −

K X X m X

C log(p(Xij | λR i λj|k ))

k=1 i∈Rk j=1

=−

K X X m X

(A13) C R C Xij log(λR i ) + Xij log(λj|k ) − λi λj|k − log((Xij )!).

k=1 i∈Rk j=1

As we are only optimizing with respect to λC j|k and Rk , this can be simplified to

L(X) = −

m K X X X

R C Xij log(λC j|k ) − λi λj|k + const.

(A14)

k=1 i∈Rk j=1

Using this definition, we perform an iterative approach to update the cluster assignments Rk and cluster-specific λC j|k values. We start with initial cluster assignments, e.g., by random initialization or by utilizing more sophisticated initialization strategies like the one proposed in Sect. 3.5, which builds on k -Means++ (Arthur and Vassilvitskii 2007). Afterward, we repeat two steps until convergence. First, we compute the cluster-specific column values 1

λC j|k = P

X

i∈Rk ri i∈Rk

Xij ,

(A15)

Pm C R where the column parameters are scaled such that ∀k∈[K] j=1 λj|k = 1 and λi is defined as in Eq. (A7). Second, we update the cluster assignments by choosing the cluster that gives the highest log-probability, considering the new column values Rk = {i ∈ [n] | k = argmaxk′ ∈[K]

m X j=1

26

R C Xij log(λC j|k′ ) − λi λj|k′ }.

(A16)

Algorithm 2: The PoissonL/PoissonC algorithms Input: data set X, number of clusters K Output: the cluster assignments Rk , the cluster-specific column values λC j|k 1 // Initialization Pm R 2 λi ← j=1 Xij 3 R1 , . . . , RK ← initialize cluster assignments (e.g., by k -Means++) 4 while any Rk changed in last iteration do 5 // Update lambdas 6 for k ∈ [K ] do 7 for j ∈ [m] do P P 1 8 λC i∈Rk Xij j|k ← ri i∈Rk

// Update cluster assignments R1 , . . . , RK ← ∅ for i ∈ [n] do if Algorithm is PoissonL Pmthen R C k ← argmaxk′ ∈[K] j=1 Xij log(λC j|k′ ) − λi λj|k′ else if Algorithm is PoissonC then C 2 Pm (Xij −λR i λj|k′ ) k ← argmink′ ∈[K] j=1 R C λ λ

9 10 11 12 13 14 15

i

17

j|k′

Rk ← Rk ∪ {i}

16

return Rk , λC j|k

PoissonC (Cai et al. 2004) uses an alternative strategy to update the cluster assignments by choosing the cluster that gives the minimum Chi-squared value. The complete process is given in Algorithm 2.

A.2

3CPO: Poisson-based Subspace Clustering

The PoissonL and PoissonC algorithms have two main assumptions regarding the data matrix X: 1. All entries within row i are scaled by the row-specific value λR i . 2. The values in cluster k all follow the proportions as defined in the column-specific values λC j|k and are different to other clusters. If one of these properties is violated, the quality of the clustering result can suffer greatly. Therefore, our proposed algorithm 3CPO automatically discovers noisy columns and defines a subspace that only contains columns that fulfill the mentioned assumptions. This also has the advantage that the resulting clustering solution is easier to interpret, as only a subset of the columns has to be analyzed. 3CPO identifies

27

relevant columns by optimizing the following loss function

L(X) = −

Xn

Xm

i=1

j=1

log p(Xij , µij ) +

X

b(X·j |K )

j∈C1

columns violating assumption (1)

=−

K X X

zX

k=1 i∈Rk

j∈C−

columns violating assumption (2)

}| { zX }| {

R C log p(Xij | λC ) + log p ( X | λ λ ) ij i j|0 j|− j∈C0

(A17)

! X

+

C log p(Xij | λR i λj|k )

X

+

b(X·j |K ),

j∈C1

j∈C1

{z

|

}

|

relevant columns for clustering

{z

}

column selection penalty term

where C− , C0 and C1 are non-overlapping partitions of the m columns so that C− ∪ C0 ∪C1 = [m] and b(X·j |K ) is a penalty term explained in Sect. 3.3. Note that columns that do not follow assumption (1) are contained in C− and do not use the row-specific values λR i to calculate the expected value. Given an input matrix Y, we set Xij = Yij + α − 1, as defined in the main paper. Considering constant terms that are not relevant for the optimization yields

L(X) = −

K X X

X

k=1 i∈Rk

j∈C−

C Xij log(λC j|− ) − λj|− +

X

R C Xij log(λC j|0 ) − λi λj|0

j∈C0

! +

X

+

Xij log(λR i )

(A18)

j∈C0 ∪C1

j∈C1

X

X

R C Xij log(λC j|k ) − λi λj|k +

b(X·j |K ) + const..

j∈C1

The lambda parameters can be optimized again by performing MLE. This gives us

X 1 P Xij , C C j∈C1 λj|k + j∈C0 λj|0 j∈C ∪C

λR i = P

0

if

i ∈ Rk ,

(A19)

1

n

λC j|− =

1X Xij , n i=1

λC j|0 = Pn

1

λC j|k = P

1

(A20)

n X

R i=1 λi i=1

Xij ,

X

R i∈Rk λi i∈Rk

(A21)

Xij .

(A22)

C C Since λR i depends on λj|0 and λj|k , we cannot follow the strategy proposed before and simply set the sum of the cluster-specific column values equal to one. Since λj|0 1 C R C is shared across all clusters, the factor κ used for scaling λR i ← κλi and λj|l ← κ λj|l

28

C has to be equal for all l ∈ {0} ∪ [K ] so that λR i λj|l = µij is fulfilled. However, w.l.o.g., Pn R we can scale i=1 λi = 1. It follows that

λC j|0 =

n X

⇒

Xij

i=1

X

λC j|0 =

n X X

Xij .

(A23)

i=1 j∈C0

j∈C0

Furthermore, we consider the following formulations (based on Eq. (A19) and (A22)) regarding cluster k P P X i∈Rk j∈C1 Xij P λC = (A24) j|k R i∈Rk λi j∈C 1

and

P

P

X

ij i∈Rk j∈C0 ∪C1 P λR i =P C + C λ λ j∈C1 j|k j∈C0 j|0 i∈Rk

X

⇒

X

P λC j|k =

j∈C1

P

Xij 1 P j∈C0 ∪C − λC j|0 . R λ i∈Rk i j∈C0

i∈Rk

(A25)

X

Inserting Eq. (A24) leads to

P

P

Xij P j∈CR1 = i∈Rk λi

i∈Rk

⇒

X

P

P

P

1 P j∈C0 ∪C R λ i∈Rk i P

i∈Rk

−

X

λC j|0

j∈C0

j∈C0 ∪C1 Xij −

i∈Rk

λR i =

Xij

P

i∈Rk

P

C j∈C0 λj|0

P

i∈Rk

P

j∈C1 Xij

(A26)

P

i∈Rk j∈C0 Xij λR . ⇒ i = Pn P i=1 j∈C0 Xij i∈Rk

X

This formulation can be used to compute λC j|k as

λC j|k =

P Pn P ( i∈Rk Xij )( i=1 j∈C0 Xij ) P P . i∈Rk j∈C0 Xij

29

(A27)

Lastly, for i ∈ Rk this yields

P

λR i =P

( j∈C1

P

j∈C ∪C1 Xij Pn P0 Pn P X )( Xij ) ij i∈Rk P Pi=1 j∈C0 + i=1 j∈C0 Xij i∈R j∈C Xij

0 P k P P ( j∈C0 ∪C1 Xij )( i∈Rk j∈C0 Xij ) P P P P = Pn P ( i=1 j∈C0 Xij )( i∈Rk j∈C1 Xij + i∈Rk j∈C0 Xij ) P P P ( j∈C ∪C Xij )( i∈Rk j∈C0 Xij ) P P = Pn P 0 1 . ( i=1 j∈C0 Xij )( i∈Rk j∈C1 ∪C0 Xij )

(A28)

When using these definitions, we have to make sure that C0 ̸= ∅, because the C denominator in the formulation of λR i and λj|k would be zero if C0 = ∅. In this case, P P P Xij kP j∈C1 Pi∈R we can set i∈Rk λR for all k ∈ [K ] as the λC n i = j|k parameters are i=1 j∈C1 Xij Pn R independent. This fulfills the assumption i=1 λi = 1 and leads to

Pn P Xij X i=1 C Pj∈C1 λj|k = P Xij , i∈Rk j∈C1 Xij i∈Rk

if

C0 = ∅

(A29)

C0 = ∅.

(A30)

and

λR i = Pn

i=1

1 P

X

j∈C1 Xij j∈C1

Xij ,

These results can be summarized as Xn λC Xij /n, j|− = i=1 Xn λC Xij , j|0 = i=1 P P  (P Xij )( n Xij ) k Pi=1 j∈C0  i∈RP , if C0 ̸= ∅ Xij i∈Rk P j∈CP C 0 P n λj|k = ( Xij )( i=1 j∈C Xij )  i∈RP 1 k P , if C0 = ∅ i∈Rk j∈C1 Xij P P P  ( Xij )( i∈R Xij ) kP j∈C0  Pn j∈C P 0 ∪C1 P , if ( X )( ij i=1 j∈C0 i∈Rk j∈C1 ∪C0 Xij ) P λR i = X ij  Pn j∈C P1 if Xij , i=1

A.3

j∈C1

if

(A31) (A32) (A33)

i ∈ Rk and C0 ̸= ∅

(A34)

i ∈ Rk and C0 = ∅.

Scale Invariance

We observe that the scaling of the matrix X does not matter if ∀j∈C1 b(X·j |K ) = 0. Theorem 1 If we fix b(X·j |K) = 0 the clustering R1 , . . . , RK and the column partition is unchanged if we multiply X → αX by a constant α ∈ R>0 .

30

Proof Assume the iterations described in Sects. 3.1, 3.2, and 3.3 have converged. If we transform X ← αX and continue the iterations, λR i defined by Eq. (6) remains unchanged. The C C C C parameters λC ← αλ (Eq. (7)), λ ← αλC j|− j|− j|0 j|0 (Eq. (8)), and λj|k ← αλj|k (Eq. (9)) P m are each multiplied by α. Then Sik of Eq. (10) becomes Sik ← αSik + j=1 αXij log α. The clustering remains unchanged because the transformation does not change the orderk ing Pmof Si for a given i (the multiplication by α does not change the ordering and the term respect to k). Similarly, the terms for the column partition j=1 αXij log α is constant with P P αXij log α (Eq. (11)), Lj (0) ← αLj (0)+ n change as Lj (−) ← αLj (−)+ n i=1 αXij log α i=1 P n (Eq. (12)), and Lj (1) ← αLj (1) + i=1 αXij log α (Eq. (13)). Again, the column partition remains unchanged, since multiplication by α does not change ordering and because the term Pn αX ij log α is the same for all Lj (−), Lj (0), and Lj (1). Therefore, if we are at the local i=1 optimum and multiply X by a constant, the iterative algorithm does not change clustering and the column partitions. □

PnIf the bias term is non-zero, as in Eq. (14), we have the scaling Lj (1) ← αLj (1) + i=1 αXij log α − (K − 1) log α, breaking the invariance, slightly favouring solutions with less columns in C1 for larger α > 1.

A.4

Poisson-based Distance Function

In many situations, it is desirable to have a general-purpose distance function for count data that can, for example, be used for initialization purposes (compare Sect. 3.5) or when conducting agglomerative clustering (Müllner 2011). To define such a distance function, we ignore the partitions of the columns, i.e., C1 = [m] and C− = C0 = ∅. We start with the log-loss of Eq. (A14).

LK (X) = −

m K X X X

C R C Xij log(λR i λj|k ) − λi λj|k + const.

(A35)

k=1 i∈Rk j=1

=−

m K X X X

Xij log(

k=1 i∈Rk j=1

ri ckj ri ckj )− + const., Nk Nk

(A36)

Pm P P where ri = j=1 Xij , ckj = i∈Rk Xij and Nk = i∈Rk ri . If each row defines its own cluster, this results in Ln (X) = −

n X m X

Xij log(Xij ) − Xij + const..

(A37)

i=1 j=1

The distance function is then based on the difference between those two losses. ∆L(X) =LK (X) − Ln (X) =

K X X m X k=1 i∈Rk j=1

−Xij log(

(A38)

ri ckj ri ckj )+ + Xij log(Xij ) − Xij Nk Nk

31

(A39)

K X X m X

ri ckj Xij Nk )+ − Xij r c Nk i kj j=1 i∈R k=1 k   K m m X X ri X X Xij Nk  = ckj  − ri + Xij log( ) Nk j=1 ri ckj j=1

=

Xij log(

(A40)

(A41)

k=1 i∈Rk

=

K X X

ri − ri +

m X

Xij log(

j=1

k=1 i∈Rk

Xij Nk ) ri ckj

(A42)

Finally, the distance between rows a and b is the difference of the log-losses, considering that the rows originate from two clusters (containing only themselves) or a shared cluster. m X X

d(a, b) =∆Lab (X) =

Xij log(

i∈{a,b} j=1

Xij Nab ), ri c(ab)j

(A43)

where, c(ab)j = Xaj + Xbj and Nab = ra + rb .

A.5

Outlier Detection

When considering outliers during the optimization (as explained in Sect. 3.6), the clustering objective from Eq. (A18) becomes n X X

L(X) = −

C Xij log(λC j|− ) − λj|− +

i=1 j∈C−

+

K X X

n X X

R C Xij log(λC j|0 ) − λi λj|0

i=1 j∈C0

X

R C Xij log(λC j|k ) − λi λj|k +

n X

X

Xij log(λR i )

(A44)

i=1 j∈C0 ∪C1

k=1 i∈Rk j∈C1

! +

XX

R C Xij log(λC j|0 ) − λi λj|0

i∈O j∈C1

+

X

b(X·j |K ) + const.,

j∈C1

where O contains the indices of the outlier rows. Performing MLE gives us the same C update rules for λC j|− , λj|k as shown in Eq. (A19)-(A22). Only the updating mechanisms R C for λi and λj|0 have to be adapted

 P

1P C C j∈C0 ∪C1 Xij j∈C1 λj|k + j∈C0 λj|0 R λi = P 1 P C j∈C0 ∪C1 Xij j∈C ∪C λj|0

P

0

( λC j|0 =

Pn

, if j ∈ C0

P 1

P

, if j ∈ C1 .

R i∈O λi

, if i ∈ O.

(A45)

1

Pn 1

R i=1 λi

, if i ∈ Rk

i=1 Xij i∈O Xij

32

(A46)

Since we do not want to optimize λj|0 for j ∈ C1 for outliers (else, would just Pwe n C add another cluster with λC = b λ for j ∈ C ), we force λ = 1 j|0 i=1 Xij for all j|0 j|K+1 j ∈ C0 ∪ C1 . It follows that P P  (P Xij )( i∈R Xij ) kP j∈C0  Pn j∈C P 0 ∪C1 P , if i ∈ Rk ( i=1 j∈C Xij )( i∈R Xij ) R j∈C ∪C 0 1 0 λi = (A47) Pk 1  Pn P , if i ∈ O. j∈C0 ∪C1 Xij Xij i=1

j∈C0 ∪C1

Extending the summary from Eq. (A31) gives us

λC j|− =

Xn

λC j|0 =

Xn

i=1

Xij /n

(A48)

Xij i=1 P P  (P Xij )( n Xij ) k Pi=1 j∈C0  i∈RP , X

(A49)

if C0 ̸= ∅ ij i∈Rk P j∈CP 0 n X )( X ) ij ij  i∈RP k Pi=1 j∈C1 , if C0 = ∅ i∈Rk j∈C1 Xij P P P  ( Xij ) j∈C0 ∪C1 Xij )( P P P i∈RkP j∈C0  , if  ( n X )( ij  i=1 j∈C0 i∈Rk j∈C1 ∪C0 Xij )  P X ij Pn j∈C P1 λR , if i = i=1 j∈C1 Xij  P   X ij  Pn j∈C P 0 ∪C1 , if i=1 j∈C ∪C Xij

λC j|k =

(

(A50)

P

0

Appendix B

i ∈ Rk and C0 ̸= ∅ i ∈ Rk and C0 = ∅

(A51)

i ∈ O.

1

Data sets

In our study, we consider one synthetic and 11 real-world data set from various domains such as economics, biology, images, and texts. Wholesales 4 (Kelly et al.) counts the monetary units that were spent annually on six product groups in a horeca (hotel/restaurant/cafe) or a retail store. The image data set Optdigits 4 (Kelly et al.) summarizes 32 × 32 bitmaps showing handwritten digits (0–9) by counting the number of activated pixels within blocks of size 4 × 4. Furthermore, we consider the text data sets BBCSports 5 (Greene and Cunningham 2006), BBCNews 5 (Greene and Cunningham 2006), WebKB 6 , Reuters21578 4 (Reuters) (Kelly et al.) and 20Newsgroups 4 (20NewsG) (Kelly et al.). BBCSports consists of sports news articles regarding athletics, cricket, football, rugby, and tennis and BBCNews consists of news stories regarding business, entertainment, politics, sport, and tech. WebKB is a collection of university websites within six different categories. In the case of Reuters, we use articles from the categories ‘grain’, ‘money-fx’, ‘earn’, ‘acq’, and ‘crude’, and 20NewsG contains messages from 20 newsgroups. All text data sets are pre-processed by applying stemming7 and using bag-of-words8 . Afterward, we consider the most frequent 2000 terms. Another text data set used is Sport Articles 4 4

https://archive.ics.uci.edu/ (accessed 07.01.2026) http://mlg.ucd.ie/datasets/bbc.html (accessed 07.01.2026) 6 https://www.cs.cmu.edu/∼webkb/ (accessed 07.01.2026) 7 https://www.nltk.org/api/nltk.stem.SnowballStemmer.html (accessed 07.01.2026) 8 https://scikit-learn.org/stable/modules/generated/sklearn.feature extraction.text.CountVectorizer. html (accessed 07.01.2026) 5

33

Table B1: Data set characteristics: the number of rows n, columns m and clusters K as well as the data range, the sparsity (ratio of zeros) and the imbalance (ratio between the smallest and largest ground truth cluster, i.e., mink∈[K] |Ck |/maxk∈[K] |Ck |). Furthermore, the table includes information about the data domain. A dagger † indicates that the original number of features has been modified. Data set Synth Wholesales SportA Optdigits BBCSports BBCNews WebKB Reuters 20NewsG MouseAtlas GeneExp HDendritic

n

m

K

Range

Sparsity

Imbalance

Domain

1000 440 1000 5620 737 2225 4518 8367 18846 6954 801 576

6 6 55 64 2000† 2000† 2000† 2000† 2000† 15006 20531 26593

3 2 2 10 5 5 6 5 20 11 5 4

[0, 125] [3, 112151] [0, 897] [0, 16] [0, 145] [0, 245] [0, 3992] [0, 245] [0, 11151] [0, 274689] [0, 21] [0, 598415]

1% 0% 31% 49% 92% 92% 95% 97% 97% 91% 16% 82%

1.00 0.48 0.57 0.97 0.38 0.76 0.08 0.15 0.63 0.06 0.26 0.50

Tabular (synthetic) Tabular (economics) Tabular (text characteristics) Image (digits) Text (sport articles) Text (news articles) Text (university websites) Text (news articles) Text (news articles) Tabular (biology) Tabular (biology) Tabular (biology)

(SportA) (Kelly et al.), which does not count occurrences of words but the frequencies of 55 different word groups like ‘personal pronouns.’ The Gene Expression 4 (GeneExp) data set (Kelly et al.) contains five clusters, each describing a different kind of tumor. The Human Dendritic Cells 9 (HDendritic) data set (Tran et al. 2020) consists of human blood dendritic cell single-cell RNA sequencing data regarding four cell types and the Mouse Cell Atlas 9 (MouseAtlas) data (Tran et al. 2020) contains 11 cell types from different organ systems. As gene expression data often contains estimated counts, we round all values to the closest integer. Lastly, we consider a synthetic data set (Synth) with three clusters. The distribution of the first four columns follows the logic shown in Fig. 1, where the cluster membership determines the ratio between column entries. For rows in the first cluster, the ratio between the first four columns is (2, 3, 4, 1), meaning v1 = 2v4 , v2 = 3v4 , and v3 = 4v4 . The second and third clusters follow ratios of (4, 1, 4, 1) and (3, 2, 4, 1), respectively. The base value v4 ranges within [1, 30], resulting in vi ∈ [1, 120] for i ∈ [4]. The fifth column contains uniformly distributed values within [0, 15], and the last column is stable across all clusters with a constant value of 20. To simulate realworld variance, we add random noise within [1, 5] to 20% of the entries. The data set is designed such that only the first two columns are relevant for clustering and, thus, should be assigned to C1 . Since the third and fourth columns follow the same distribution for all rows but depend on the row scaling, they should be assigned to C0 . Finally, the fifth and sixth columns are independent of both row scaling and cluster distributions and should therefore be moved to C− . A good clustering result for Synth suggests that the algorithm is able to ignore noise features and thus concentrate on cluster-relevant structures. The characteristics of all benchmark data sets are given in Table B1. 9

https://github.com/JinmiaoChenLab/Batch-effect-removal-benchmarking/ (accessed 07.01.2026)

34

Appendix C

Implementations

For the conducted experiments, we use our own implementations for 3CPO, PoissonL, PoissonC and Spherical k -Means (SKM). These can be found in our repository10 . The k -Means-based approaches use the k -Means implementation from scikit-learn 11 . For CROINFO, CoclustMod and CoclustSpecMod we use the implementations provided by the coclust 12 package (Role et al. 2019). The implementations of EBML13 , SEBML13 and TauCC14 are taken from the repositories as referenced in the respective publications.

Appendix D

Additional Results

In the following sections, we provide complementary experimental results that did not fit into the main paper.

D.1

ACC and NMI Results

In addition to the ARI results presented in Table 1, Table 2 and Table 6, we also evaluate the clustering results using ACC and NMI. These extended evaluations are provided in Table D2 (traditional algorithms), Table D3 (co-clustering), and Table D4 (tf-idf/bm25-based text data analysis). Furthermore, Table D5 contains the additional results for the ablation study discussed in Sect. 4.5. Generally, the different metrics show similar trends and rarely diverge. Striking differences arise mainly with ACC when dealing with highly unbalanced cluster sizes, such as in the WebKB data set. Here, the smaller clusters have significantly less influence on the final score. Consequently, the ACC is often disproportionately higher than the corresponding NMI and ARI results, which more accurately reflect the difficulty of capturing smaller groups.

D.2

Initialization Strategies for Rk

We conduct a series of experiments to evaluate the influence of our proposed initialization strategy for the cluster assignments Rk (Sect. 3.5) – named Poisson-k -Means++. We compare against random cluster assignments (random labels), picking random rows followed by the assignment method described in Sect 3.5 (random centers), the seeding mechanism of k -Means++ using the Euclidean distance, and a full execution of k -Means. For the k -Means++ version, the labels are received by determining for each row Xi· the closest selected row based on the Euclidean distance. For k -Means++ and k -Means (full), we also test a version in which we first divide each row by the row-sum (named as RF+). The results are shown in Table D6. We can see that all versions perform similarly for Synth, Wholesales, and GeneExp. Furthermore, it is evident that there is no clear winner in all other scenarios. 10

https://github.com/collinleiber/3CPO (accessed 27.01.2026) https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html (accessed 07.01.2026) https://github.com/franrole/cclust package (accessed 07.01.2026) 13 https://github.com/Saeidhoseinipour/ELBMcoclust (accessed 07.01.2026) 14 https://github.com/rupensa/tauCC (accessed 07.01.2026) 11 12

35

Table D2: Clustering results (in %) of traditional clustering algorithms. Entries correspond to the mean of ten executions ± the standard deviation. The best result for each data set and evaluation metric is marked in bold, the runner-up is underlined, and the third place is dashed-underlined. Data set

Metric

3CPO

PoissonL

PoissonC

SKM

KM

STD+KM

MM+KM

RF+KM

RCA+KM

Synth

ACC NMI ARI

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0

58.0 ± 0.0 42.4 ± 0.1 33.3 ± 0.1

57.2 ± 0.0 39.9 ± 0.0 29.9 ± 0.0

61.3 ± 0.1 49.0 ± 0.1 42.7 ± 0.0

36.6 ± 0.2 0.3 ± 0.0 0.2 ± 0.0

61.0 ± 0.0 49.1 ± 0.0 42.1 ± 0.0

61.1 ± 0.0 49.5 ± 0.1 42.9 ± 0.1

61.0 ± 0.0 48.3 ± 0.0 42.5 ± 0.0

35.8 ± 0.0 0.2 ± 0.0 0.0 ± 0.0

Wholesales

ACC NMI ARI

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0

78.2 ± 0.0 23.1 ± 0.0 31.3 ± 0.0

78.9 ± 0.0 24.0 ± 0.0 32.8 ± 0.0

75.9 ± 0.0 19.5 ± 0.0 26.5 ± 0.0

59.3 ± 0.0 0.9 ± 0.0 −3.1 ± 0.0

76.8 ± 0.0 20.0 ± 0.0 28.2 ± 0.0

76.6 ± 0.1 20.3 ± 0.2 27.9 ± 0.2

73.2 ± 0.0 17.2 ± 0.0 21.3 ± 0.0

84.4 ± 0.1 36.1 ± 0.2 47.0 ± 0.3

SportA

ACC NMI ARI

78.5 ± 0.2 24.1 ± 0.5 32.3 ± 0.5

78.6 ± 0.1 24.2 ± 0.2 32.5 ± 0.2

73.4 ± 0.8 18.2 ± 0.2 21.9 ± 1.5

77.2 ± 0.0 23.0 ± 0.0 29.5 ± 0.0

73.3 ± 0.0 14.1 ± 0.0 21.3 ± 0.0

78.3 ± 0.0 24.4 ± 0.0 31.9 ± 0.0

75.6 ± 0.0 17.8 ± 0.1 25.9 ± 0.1

64.3 ± 0.0 13.3 ± 0.0 7.5 ± 0.0

63.6 ± 0.0 0.3 ± 0.0 0.1 ± 0.0

Optdigits

ACC NMI ARI

80.0 ± 2.0 75.1 ± 0.9 66.7 ± 2.2

80.1 ± 2.1 75.2 ± 1.0 67.0 ± 1.8

63.7 ± 3.5 63.4 ± 2.1 45.0 ± 3.1

80.0 ± 0.1 74.8 ± 0.1 67.5 ± 0.1

79.3 ± 0.2 75.6 ± 0.3 67.1 ± 0.2

80.1 ± 0.1 74.8 ± 0.1 67.6 ± 0.1

79.4 ± 0.4 75.5 ± 0.4 67.3 ± 0.3

79.1 ± 0.2 75.1 ± 0.3 66.5 ± 0.2

10.6 ± 0.1 1.4 ± 0.2 0.0 ± 0.0

BBCSports

ACC NMI ARI

96.1 ± 1.2 89.4 ± 2.0 90.1 ± 2.9

70.7 ± 6.6 58.6 ± 6.0 51.6 ± 8.1

54.1 ± 4.3 32.5 ± 4.5 27.7 ± 4.0

37.1 ± 1.7 17.7 ± 2.4 10.4 ± 1.7

28.7 ± 0.3 2.7 ± 0.2 0.3 ± 0.2

36.3 ± 1.5 16.3 ± 1.7 9.5 ± 0.9

35.9 ± 2.5 15.2 ± 3.0 6.9 ± 3.6

37.4 ± 1.5 16.4 ± 2.3 9.8 ± 1.7

40.6 ± 2.7 11.8 ± 5.9 3.7 ± 2.6

BBCNews

ACC NMI ARI

95.7 ± 0.4 87.2 ± 0.8 89.9 ± 0.9

95.4 ± 0.4 86.2 ± 0.8 89.2 ± 0.8

81.1 ± 5.0 66.5 ± 4.3 63.4 ± 6.7

63.2 ± 3.0 38.3 ± 1.8 31.5 ± 4.0

33.2 ± 0.7 8.0 ± 0.3 6.0 ± 0.3

56.8 ± 2.0 34.1 ± 1.0 24.6 ± 1.6

50.9 ± 1.7 25.6 ± 0.6 16.4 ± 1.5

55.5 ± 2.2 32.2 ± 1.8 25.6 ± 1.8

37.8 ± 9.5 28.3 ± 15.2 15.4 ± 12.0

WebKB

ACC NMI ARI

57.4 ± 2.7 37.2 ± 1.2 31.5 ± 3.2

51.8 ± 2.0 34.1 ± 1.4 25.4 ± 0.9

44.5 ± 4.0 26.6 ± 2.3 20.2 ± 3.8

38.7 ± 0.3 18.2 ± 0.2 11.4 ± 0.2

39.2 ± 0.1 2.8 ± 0.0 3.6 ± 0.0

39.2 ± 0.4 18.0 ± 0.2 12.0 ± 0.2

38.8 ± 0.5 16.7 ± 0.4 10.9 ± 0.4

40.0 ± 3.1 15.6 ± 3.3 11.0 ± 2.7

36.3 ± 0.3 1.5 ± 0.4 −0.0 ± 0.1

Reuters

ACC NMI ARI

80.9 ± 2.9 70.8 ± 2.9 67.8 ± 1.6

80.1 ± 3.4 68.1 ± 2.5 65.2 ± 5.0

65.7 ± 4.2 53.2 ± 3.2 44.1 ± 4.0

50.5 ± 0.2 35.9 ± 0.3 21.9 ± 0.2

44.5 ± 6.0 19.6 ± 1.6 15.2 ± 0.6

57.9 ± 0.0 37.2 ± 0.0 32.5 ± 0.1

57.2 ± 0.0 37.2 ± 0.0 31.9 ± 0.0

41.1 ± 1.2 29.7 ± 0.2 3.7 ± 4.2

47.3 ± 0.3 1.4 ± 0.6 0.3 ± 0.3

20NewsG

ACC NMI ARI

38.4 ± 2.5 39.9 ± 1.0 23.0 ± 1.3

37.2 ± 2.4 39.4 ± 0.9 22.2 ± 1.9

29.6 ± 1.9 32.2 ± 1.3 14.6 ± 1.5

12.2 ± 0.3 5.8 ± 0.4 2.0 ± 0.2

7.5 ± 0.1 2.7 ± 0.0 0.4 ± 0.0

11.8 ± 0.3 5.8 ± 0.2 2.1 ± 0.1

11.1 ± 0.2 5.0 ± 0.2 1.5 ± 0.1

9.8 ± 0.2 3.7 ± 0.4 1.1 ± 0.2

5.7 ± 0.4 0.9 ± 0.5 0.0 ± 0.0

MouseAtlas

ACC NMI ARI

67.5 ± 6.0 67.6 ± 2.3 56.3 ± 6.2

67.1 ± 3.9 65.7 ± 3.0 55.4 ± 5.0

46.6 ± 7.3 42.9 ± 7.1 18.5 ± 9.5

56.4 ± 2.9 57.2 ± 1.6 39.3 ± 2.6

32.6 ± 0.4 21.8 ± 0.6 1.6 ± 0.1

54.6 ± 1.7 56.7 ± 0.9 38.4 ± 1.4

52.4 ± 1.7 51.3 ± 1.3 36.3 ± 2.0

50.9 ± 2.1 49.4 ± 1.9 28.6 ± 2.6

20.7 ± 0.0 0.8 ± 0.1 0.1 ± 0.0

GeneExp

ACC NMI ARI

99.6 ± 0.1 98.4 ± 0.2 99.1 ± 0.1

99.4 ± 0.1 97.8 ± 0.2 98.7 ± 0.1

93.0 ± 6.8 90.3 ± 6.5 86.7 ± 11.0

99.4 ± 0.0 97.6 ± 0.0 98.5 ± 0.0

99.3 ± 0.1 97.3 ± 0.2 98.2 ± 0.1

99.6 ± 0.0 98.5 ± 0.1 99.1 ± 0.1

99.3 ± 0.0 97.1 ± 0.0 98.3 ± 0.0

99.3 ± 0.1 97.4 ± 0.2 98.5 ± 0.1

39.3 ± 4.2 6.0 ± 13.5 3.7 ± 9.8

HDendritic

ACC NMI ARI

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.8

91.2 ± 6.1 80.9 ± 4.0 83.4 ± 5.2

84.8 ± 8.0 73.7 ± 3.1 74.8 ± 6.1

91.9 ± 0.1 77.2 ± 0.2 79.9 ± 0.2

57.0 ± 11.1 48.1 ± 10.6 37.5 ± 13.3

92.1 ± 0.2 77.4 ± 0.2 80.2 ± 0.4

89.7 ± 0.1 73.9 ± 0.1 75.5 ± 0.2

57.0 ± 11.1 48.1 ± 10.6 37.5 ± 13.3

33.6 ± 0.6 1.0 ± 0.3 −0.1 ± 0.1

Poisson-k -Means++, random labels, and random centers all provide good solutions across the benchmark. However, if one considers the better results for BBCSports and HDendritic, the version of 3CPO using Poisson-k -Means++ is a reasonable choice.

D.3

Evaluation of the Runtime

We compare the runtime of the Poisson-based approaches 3CPO, PoissonL, and PoissonC and the co-clustering algorithms. Here, each entry corresponds to the sum of ten runs, except for TauCC, where the entries correspond to a single run. In the first experiment (Fig. D1a), we use the Synth data set as described above and increase the number of rows n ∈ [1 000, 50 000]. The runtime of 3CPO, PoissonL and PoissonC is very similar and shows a linear increase with n. 3CPO is slightly slower as it updates the column partitions in each iteration and needs to re-calculate λR i , while it is only computed once for PoissonL and PoissonC. CoclustMod and CROINFO also show a

36

Table D3: Clustering results (in %) of co-clustering algorithms. Entries correspond to the mean of ten executions ± the standard deviation. The best result for each data set and evaluation metric is marked in bold, the runner-up is underlined, and the third place is dashed-underlined. Data set

Metric

3CPO

CROINFO

CCMod

CCSMod

ELBM

SELBM

TauCC

Synth

ACC NMI ARI

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0

57.9 ± 0.1 42.0 ± 0.2 32.8 ± 0.3

60.0 ± 0.2 34.0 ± 0.4 25.2 ± 0.1

45.8 ± 14.5 20.0 ± 23.6 17.8 ± 20.8

45.4 ± 7.7 14.7 ± 14.1 9.2 ± 8.6

42.5 ± 0.2 7.3 ± 0.1 3.5 ± 1.6

59.8 ± 0.0 33.7 ± 0.5 25.1 ± 0.6

Wholesales

ACC NMI ARI

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0

79.2 ± 0.2 25.1 ± 0.5 33.6 ± 0.5

78.4 ± 0.0 25.1 ± 0.0 32.0 ± 0.0

68.8 ± 3.1 2.3 ± 6.7 3.2 ± 9.1

64.7 ± 4.3 1.6 ± 3.9 2.0 ± 5.0

65.5 ± 0.1 0.3 ± 0.1 1.9 ± 0.6

75.7 ± 0.0 21.8 ± 0.0 27.6 ± 0.0

SportA

ACC NMI ARI

78.5 ± 0.2 24.1 ± 0.5 32.3 ± 0.5

75.2 ± 0.4 19.4 ± 0.7 25.4 ± 0.8

77.7 ± 0.0 21.2 ± 0.0 30.3 ± 0.0

78.1 ± 0.0 23.1 ± 0.0 31.4 ± 0.1

66.9 ± 0.0 4.3 ± 0.0 7.1 ± 0.0

66.6 ± 0.1 4.0 ± 0.1 6.5 ± 0.1

70.1 ± 6.6 10.9 ± 10.5 15.8 ± 15.1

Optdigits

ACC NMI ARI

80.0 ± 2.0 75.1 ± 0.9 66.7 ± 2.2

65.7 ± 1.7 60.7 ± 2.2 49.7 ± 2.1

33.6 ± 1.9 34.4 ± 1.5 21.4 ± 1.5

45.8 ± 3.8 50.9 ± 2.5 33.2 ± 2.9

61.5 ± 5.0 57.0 ± 2.0 45.3 ± 3.0

40.3 ± 2.8 39.4 ± 3.7 23.1 ± 4.3

20.3 ± 7.2 19.6 ± 13.1 10.6 ± 7.5

BBCSports

ACC NMI ARI

96.1 ± 1.2 89.4 ± 2.0 90.1 ± 2.9

62.3 ± 3.7 58.3 ± 3.9 48.3 ± 5.2

64.2 ± 2.3 47.6 ± 5.7 41.0 ± 4.3

60.8 ± 1.1 51.7 ± 1.0 38.1 ± 0.1

28.4 ± 0.2 1.7 ± 0.1 0.3 ± 0.1

31.6 ± 0.0 0.6 ± 0.0 0.3 ± 0.0

51.6 ± 5.7 28.0 ± 7.5 26.2 ± 6.3

BBCNews

ACC NMI ARI

95.7 ± 0.4 87.2 ± 0.8 89.9 ± 0.9

79.9 ± 1.4 63.2 ± 1.7 62.1 ± 2.3

87.3 ± 0.9 67.8 ± 1.7 71.9 ± 1.8

76.6 ± 0.3 66.1 ± 0.3 62.3 ± 0.3

31.0 ± 0.6 5.7 ± 0.2 4.5 ± 0.2

27.6 ± 0.4 5.2 ± 0.2 2.9 ± 0.6

60.5 ± 9.6 45.6 ± 9.2 41.8 ± 10.5

WebKB

ACC NMI ARI

57.4 ± 2.7 37.2 ± 1.2 31.5 ± 3.2

46.6 ± 1.7 26.1 ± 1.0 20.1 ± 1.4

53.7 ± 0.7 25.8 ± 0.7 20.4 ± 0.7

56.8 ± 0.1 32.0 ± 0.0 25.8 ± 0.1

35.6 ± 0.1 2.4 ± 0.0 3.7 ± 0.1

36.3 ± 0.0 0.0 ± 0.0 0.0 ± 0.0

48.3 ± 2.7 13.1 ± 2.3 11.3 ± 2.0

Reuters

ACC NMI ARI

80.9 ± 2.9 70.8 ± 2.9 67.8 ± 1.6

70.8 ± 0.7 55.6 ± 1.5 59.9 ± 1.2

77.9 ± 2.8 59.1 ± 3.1 64.6 ± 4.1

67.4 ± 0.0 56.1 ± 0.0 46.1 ± 0.0

59.2 ± 0.1 19.8 ± 0.1 34.6 ± 0.3

48.0 ± 1.1 6.9 ± 0.6 10.1 ± 1.0

68.8 ± 0.4 35.2 ± 0.9 43.2 ± 0.5

20NewsG

ACC NMI ARI

38.4 ± 2.5 39.9 ± 1.0 23.0 ± 1.3

28.4 ± 1.0 30.4 ± 0.7 16.2 ± 0.7

15.5 ± 0.5 17.3 ± 0.5 6.9 ± 0.6

19.1 ± 0.9 24.8 ± 2.5 6.2 ± 2.3

7.9 ± 0.3 2.8 ± 0.1 0.5 ± 0.1

5.4 ± 0.1 0.3 ± 0.1 0.0 ± 0.0

8.7 ± 1.9 6.9 ± 4.4 2.1 ± 1.5

MouseAtlas

ACC NMI ARI

67.5 ± 6.0 67.6 ± 2.3 56.3 ± 6.2

61.1 ± 2.1 62.6 ± 1.3 49.7 ± 1.8

58.2 ± 2.6 57.2 ± 2.5 38.4 ± 1.8

54.8 ± 0.0 52.2 ± 0.0 27.4 ± 0.1

31.3 ± 0.9 22.3 ± 1.0 1.4 ± 0.3

25.8 ± 1.1 8.5 ± 1.9 0.5 ± 0.1

50.4 ± 6.1 51.3 ± 4.6 34.4 ± 4.6

GeneExp

ACC NMI ARI

99.6 ± 0.1 98.4 ± 0.2 99.1 ± 0.1

77.3 ± 2.0 73.9 ± 3.1 59.0 ± 3.1

84.4 ± 2.3 80.2 ± 1.6 72.4 ± 2.9

97.6 ± 0.0 93.8 ± 0.0 93.2 ± 0.0

32.3 ± 1.7 9.1 ± 1.9 4.3 ± 1.4

37.5 ± 0.0 0.0 ± 0.0 0.0 ± 0.0

67.2 ± 7.5 61.3 ± 8.5 53.1 ± 9.4

HDendritic

ACC NMI ARI

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.8

92.3 ± 0.5 77.9 ± 1.5 81.9 ± 1.3

80.7 ± 4.5 72.6 ± 3.2 72.2 ± 5.0

33.7 ± 0.0 1.0 ± 0.0 0.0 ± 0.0

72.8 ± 3.8 45.9 ± 2.6 45.1 ± 4.3

36.2 ± 4.8 6.5 ± 10.9 4.0 ± 7.8

64.3 ± 16.2 46.2 ± 20.3 42.3 ± 23.0

similar behavior while the runtime of CoclustSpecMod, ELBM, SELBM and TauCC increases exponentially. If we increase the number of columns in C0 for Synth as done in the second experiment (Fig. D1b), we can see that 3CPO is slightly slower than PoissonL and PoissonC in the beginning. However, it is faster for large m as 3CPO assigns the additional columns to C0 and, thus, needs to consider fewer columns when updating the cluster assignments Rk . The co-clustering approaches CoclustMod, CROINFO, ELBM, and TauCC show an exponential increase of the runtime with increasing m. CoclustSpecMod often terminated immediately after initialization and appears to have problems with the structure of the data. In summary, the experiments confirm the linear complexity of 3CPO with respect to n and m as described in Sect. 3.7.

37

Table D4: Clustering results (in %) regarding text data sets pre-processed by TFIDF and BM25. Entries correspond to the mean of ten executions ± the standard deviation. The best performance is highlighted in bold. Data set

Metric

3CPO

TF-IDF+KM

BM25+KM

TF-IDF+SKM

BM25+SKM

BBCSports

ACC NMI ARI

96.1 ± 1.2 89.4 ± 2.0 90.1 ± 2.9

86.9 ± 6.3 74.7 ± 6.3 71.0 ± 11.4

64.1 ± 8.0 58.9 ± 10.5 43.7 ± 17.0

89.2 ± 5.0 77.8 ± 4.7 76.5 ± 7.1

92.4 ± 2.9 82.0 ± 4.6 81.1 ± 6.8

BBCNews

ACC NMI ARI

95.7 ± 0.4 87.2 ± 0.8 89.9 ± 0.9

93.2 ± 1.2 81.6 ± 1.8 84.2 ± 2.8

94.0 ± 5.3 85.9 ± 3.9 87.7 ± 6.8

94.1 ± 0.4 83.3 ± 0.8 86.4 ± 0.8

96.0 ± 0.2 87.9 ± 0.4 90.7 ± 0.3

WebKB

ACC NMI ARI

57.4 ± 2.7 37.2 ± 1.2 31.5 ± 3.2

45.3 ± 0.7 26.7 ± 0.9 18.8 ± 1.0

44.8 ± 2.7 26.0 ± 1.1 14.6 ± 1.3

49.2 ± 1.2 30.4 ± 1.3 22.4 ± 1.1

51.9 ± 2.6 36.0 ± 2.1 29.0 ± 1.9

Reuters

ACC NMI ARI

80.9 ± 2.9 70.8 ± 2.9 67.8 ± 1.6

50.0 ± 0.2 33.6 ± 0.2 19.3 ± 0.2

60.4 ± 5.9 42.9 ± 4.5 34.8 ± 5.0

56.1 ± 0.1 49.0 ± 0.3 34.0 ± 0.2

73.1 ± 0.6 64.0 ± 2.3 55.8 ± 1.2

20NewsG

ACC NMI ARI

38.4 ± 2.5 39.9 ± 1.0 23.0 ± 1.3

21.3 ± 1.2 20.1 ± 1.2 5.6 ± 0.6

21.9 ± 1.6 26.9 ± 1.4 5.5 ± 0.5

24.3 ± 0.9 23.0 ± 1.3 8.2 ± 0.4

39.6 ± 1.5 38.0 ± 1.2 21.1 ± 1.2

100

102

Runtime (s)

Runtime (s)

103 101 100 10 1

3CPO PoissonL PoissonC CROINFO CoclustMod CoclustSpecMod ELBM SELBM TauCC

10 1 10 2

10 2 10 3

0

10

20

30

# Rows (x1000)

40

10 3

0

25 50 75 100 125 150 175 200

# Columns

(a) Runtime with an increasing n (b) Runtime with an increasing m (m = 6, logarithmic scale). (n = 1000, logarithmic scale).

Fig. D1: Runtime experiments investigating the impact of the number of rows n and columns m. Both experiments build on the Synth data set, where the number of clusters K = 3. The experiments are run on an Apple M3 Pro with 16GB memory.

D.4

Detected Outliers for Optdigits

Inspecting the outliers identified by 3CPO within the Optdigits data set, it is noticeable that more than half of those belong to cluster eight according to the ground truth. Considering that our outlier detection uses a distribution shared across all clusters and considering the row-scaling due to λR i , the outlier definition is prone to rows that use similar values for all pixels. As the digit eight requires the most “active” pixels, it is the most likely to fall into the outlier category if it deviates too much from an average writing style. To validate this, we visually examine a random set of inliers and outliers and find that the majority of outliers exhibit genuinely unusual characteristics despite the class imbalance in the outlier set. A common trait is, for example, a gap within the structure

38

Table D5: Clustering results (in %) and the final number of columns included in C1 of various ablation studies. Entries correspond to the mean of ten executions ± the standard deviation. Colors indicate whether the average performance of 3CPO lies above (green), within (yellow) or below (red) the standard deviation band, where above is better for ACC, NMI and ARI and below is better for |C1 |. Data set

Metric

3CPO

C− = ∅

C0 = ∅

b(X·j ) = 0

b(X·j ) = BIC(X·j )

Synth

ACC NMI ARI |C1 |

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

58.0 ± 0.0 42.4 ± 0.1 33.3 ± 0.1 5.8 ± 0.6

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 4.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 4.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

Wholesales

ACC NMI ARI |C1 |

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

78.2 ± 0.0 23.1 ± 0.0 31.3 ± 0.0 6.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

SportA

ACC NMI ARI |C1 |

78.5 ± 0.2 24.1 ± 0.5 32.3 ± 0.5 41.1 ± 1.4

78.5 ± 0.0 24.0 ± 0.2 32.3 ± 0.1 42.5 ± 1.1

78.6 ± 0.1 24.2 ± 0.2 32.6 ± 0.2 52.0 ± 0.0

78.6 ± 0.1 24.2 ± 0.2 32.6 ± 0.2 52.0 ± 0.0

78.6 ± 0.1 24.4 ± 0.3 32.5 ± 0.3 41.3 ± 0.9

Optdigits

ACC NMI ARI |C1 |

80.0 ± 2.0 75.1 ± 0.9 66.7 ± 2.2 55.8 ± 0.6

80.1 ± 2.1 75.1 ± 1.0 66.9 ± 1.8 56.0 ± 0.0

80.1 ± 2.0 75.2 ± 1.0 66.8 ± 2.2 56.0 ± 0.0

80.1 ± 2.0 75.2 ± 1.0 66.8 ± 2.2 62.0 ± 0.0

80.1 ± 2.0 75.2 ± 1.0 66.8 ± 2.2 56.0 ± 0.0

BBCSports

ACC NMI ARI |C1 |

96.1 ± 1.2 89.4 ± 2.0 90.1 ± 2.9 799.2 ± 7.6

87.3 ± 6.4 79.4 ± 5.7 78.0 ± 8.2 860.6 ± 28.1

89.1 ± 4.0 78.0 ± 5.3 75.2 ± 8.5 1218.8 ± 14.5

80.3 ± 8.3 68.8 ± 5.2 63.3 ± 7.6 1953.7 ± 5.9

93.7 ± 5.5 87.1 ± 4.2 87.0 ± 6.3 720.8 ± 14.7

BBCNews

ACC NMI ARI |C1 |

95.7 ± 0.4 87.2 ± 0.8 89.9 ± 0.9 1379.0 ± 6.2

95.8 ± 0.3 87.2 ± 0.8 90.1 ± 0.7 1437.4 ± 4.5

95.6 ± 0.3 86.6 ± 0.7 89.6 ± 0.7 1758.4 ± 2.3

95.5 ± 0.2 86.7 ± 0.4 89.5 ± 0.4 1984.8 ± 2.3

95.8 ± 0.3 87.3 ± 0.6 90.1 ± 0.7 1367.4 ± 6.1

WebKB

ACC NMI ARI |C1 |

57.4 ± 2.7 37.2 ± 1.2 31.5 ± 3.2 1314.9 ± 18.4

50.7 ± 2.3 34.5 ± 0.6 24.9 ± 1.1 1407.9 ± 42.5

58.2 ± 3.0 36.7 ± 1.2 33.8 ± 3.5 1854.2 ± 6.8

57.4 ± 2.6 37.0 ± 1.5 32.6 ± 2.7 1936.2 ± 4.6

56.6 ± 1.9 37.1 ± 0.8 30.9 ± 2.5 1282.7 ± 19.2

Reuters

ACC NMI ARI |C1 |

80.9 ± 2.9 70.8 ± 2.9 67.8 ± 1.6 1321.9 ± 7.9

80.2 ± 3.7 68.9 ± 2.7 65.7 ± 5.1 1390.7 ± 29.1

80.1 ± 3.2 70.5 ± 3.0 67.2 ± 3.3 1914.6 ± 2.1

78.1 ± 4.2 68.7 ± 3.7 65.4 ± 4.2 1976.0 ± 1.7

80.8 ± 2.7 71.7 ± 2.3 68.3 ± 1.3 1213.3 ± 11.7

20NewsG

ACC NMI ARI |C1 |

38.4 ± 2.5 39.9 ± 1.0 23.0 ± 1.3 1453.7 ± 15.3

37.9 ± 1.3 39.4 ± 1.2 23.2 ± 1.7 1456.7 ± 13.1

38.1 ± 1.9 39.8 ± 0.8 22.4 ± 1.0 1990.5 ± 0.8

37.9 ± 1.8 39.8 ± 0.8 22.5 ± 0.9 1999.0 ± 0.0

37.3 ± 2.0 39.5 ± 1.2 22.8 ± 2.0 1564.4 ± 10.4

MouseAtlas

ACC NMI ARI |C1 |

67.5 ± 6.0 67.6 ± 2.3 56.3 ± 6.2 14566.0 ± 58.8

67.1 ± 3.9 65.7 ± 3.0 55.4 ± 5.0 14753.0 ± 14.8

67.5 ± 6.0 67.6 ± 2.3 56.3 ± 6.2 14650.3 ± 26.2

67.5 ± 6.0 67.6 ± 2.3 56.3 ± 6.2 14736.9 ± 21.3

67.5 ± 6.1 67.5 ± 2.3 56.2 ± 6.2 14550.3 ± 60.4

GeneExp

ACC NMI ARI |C1 |

99.6 ± 0.1 98.4 ± 0.2 99.1 ± 0.1 6445.1 ± 3.1

99.4 ± 0.1 97.7 ± 0.2 98.7 ± 0.1 7652.8 ± 3.0

99.6 ± 0.1 98.3 ± 0.2 99.1 ± 0.1 7718.8 ± 3.0

99.5 ± 0.1 97.9 ± 0.2 98.8 ± 0.1 14135.0 ± 0.0

99.5 ± 0.1 98.2 ± 0.3 99.0 ± 0.2 8065.6 ± 5.3

HDendritic

ACC NMI ARI |C1 |

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.8 16672.9 ± 406.2

91.2 ± 6.1 80.9 ± 4.0 83.4 ± 5.2 23694.0 ± 388.1

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.8 17599.1 ± 393.0

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.7 20094.5 ± 274.9

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.7 16574.9 ± 343.4

of the eight. Fig. D2 shows a random selection of inliers and outliers which showcase usual and unusual characteristics.

Appendix E

Estimating the Number of Clusters for k-Means-based Approaches

In the following, we evaluate whether the K -estimation strategy used by 3CPO outperforms established strategies for k -Means. We utilize three criteria to estimate K for k -Means: (1) elbows in the inertia curve (Thorndike 1953) detected by the Needle algorithm (Satopaa et al. 2011), (2) the Silhouette score (Rousseeuw 1987), and (3) the BIC score as defined for X -Means (Pelleg and Moore 2000). For visualization,

39

Table D6: Clustering results (in %) and the final number of columns included in C1 for different initialization strategies for Rk . Poisson-k -Means++ corresponds to the strategy of 3CPO, proposed in Sect. 3.5. Representation corresponds to Tab. 1. Data set

Metric

Poisson-k -Means++

random labels

random centers

k -Means++

k -Means (full)

RF+k -Means++

RF+k -Means (full)

Synth

ACC NMI ARI |C1 |

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

98.5 ± 0.0 92.5 ± 0.0 95.5 ± 0.0 2.0 ± 0.0

60.0 ± 0.0 44.6 ± 0.0 37.1 ± 0.0 3.0 ± 0.0

Wholesales

ACC NMI ARI |C1 |

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.7 ± 0.3 29.2 ± 3.9 30.5 ± 0.5 5.3 ± 0.4

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

77.5 ± 0.0 31.9 ± 0.0 30.1 ± 0.0 5.0 ± 0.0

SportA

ACC NMI ARI |C1 |

78.5 ± 0.2 24.1 ± 0.5 32.3 ± 0.5 41.1 ± 1.4

78.5 ± 0.1 24.0 ± 0.1 32.3 ± 0.1 40.6 ± 0.5

78.5 ± 0.2 24.0 ± 0.5 32.3 ± 0.5 41.1 ± 1.4

78.5 ± 0.2 24.0 ± 0.4 32.3 ± 0.3 41.1 ± 0.7

78.2 ± 0.0 23.8 ± 0.0 31.7 ± 0.0 39.0 ± 0.0

78.6 ± 0.2 24.2 ± 0.5 32.5 ± 0.4 41.9 ± 1.1

76.5 ± 0.0 20.5 ± 0.0 27.9 ± 0.0 46.0 ± 0.0

Optdigits

ACC NMI ARI |C1 |

80.0 ± 2.0 75.1 ± 0.9 66.7 ± 2.2 55.8 ± 0.6

80.1 ± 2.0 75.1 ± 1.0 66.8 ± 2.3 54.0 ± 0.0

80.9 ± 0.3 75.5 ± 0.2 67.6 ± 0.4 55.4 ± 0.9

78.6 ± 3.1 74.4 ± 1.5 65.3 ± 3.2 55.0 ± 1.0

76.0 ± 3.1 73.2 ± 1.5 62.0 ± 3.6 54.2 ± 0.6

79.3 ± 2.8 74.8 ± 1.3 65.9 ± 3.0 55.0 ± 1.0

77.1 ± 0.1 74.0 ± 0.1 64.6 ± 0.1 55.6 ± 0.8

BBCSports

ACC NMI ARI |C1 |

96.1 ± 1.2 89.4 ± 2.0 90.1 ± 2.9 799.2 ± 7.6

89.9 ± 9.1 83.5 ± 7.7 82.8 ± 10.6 796.8 ± 7.9

91.2 ± 5.0 84.2 ± 3.2 84.4 ± 3.5 798.0 ± 19.1

91.5 ± 6.7 85.8 ± 5.0 84.7 ± 7.2 792.8 ± 21.1

88.1 ± 8.0 84.2 ± 3.8 82.7 ± 5.8 782.3 ± 22.7

92.0 ± 5.3 83.9 ± 5.7 83.7 ± 6.5 785.3 ± 17.1

93.2 ± 5.6 87.0 ± 5.0 86.9 ± 5.8 791.8 ± 13.2

BBCNews

ACC NMI ARI |C1 |

95.7 ± 0.4 87.2 ± 0.8 89.9 ± 0.9 1379.0 ± 6.2

96.0 ± 0.5 87.7 ± 1.1 90.5 ± 1.2 1378.4 ± 5.5

95.7 ± 0.6 87.1 ± 1.5 89.9 ± 1.5 1380.4 ± 5.5

95.5 ± 0.8 86.7 ± 1.7 89.4 ± 1.9 1376.2 ± 6.3

95.5 ± 0.7 86.8 ± 1.6 89.4 ± 1.8 1376.8 ± 6.7

95.4 ± 0.5 86.6 ± 1.0 89.3 ± 1.2 1376.3 ± 4.2

95.6 ± 0.5 86.9 ± 1.0 89.5 ± 1.0 1378.2 ± 4.7

WebKB

ACC NMI ARI |C1 |

57.4 ± 2.7 37.2 ± 1.2 31.5 ± 3.2 1314.9 ± 18.4

58.8 ± 2.3 37.9 ± 0.4 32.6 ± 2.7 1326.4 ± 17.5

57.1 ± 1.9 37.3 ± 0.8 31.4 ± 2.3 1317.2 ± 8.2

56.0 ± 3.8 36.4 ± 1.5 30.0 ± 4.0 1312.9 ± 31.8

56.3 ± 3.4 36.7 ± 1.1 30.8 ± 3.3 1313.1 ± 26.1

55.4 ± 2.7 36.1 ± 1.5 30.2 ± 2.5 1309.0 ± 9.9

55.0 ± 3.7 36.6 ± 1.3 30.9 ± 2.8 1307.6 ± 25.5

Reuters

ACC NMI ARI |C1 |

80.9 ± 2.9 70.8 ± 2.9 67.8 ± 1.6 1321.9 ± 7.9

81.3 ± 2.6 70.5 ± 1.7 67.6 ± 0.7 1321.0 ± 9.7

79.6 ± 3.8 69.7 ± 2.1 65.8 ± 2.9 1318.9 ± 11.7

81.1 ± 6.5 71.5 ± 3.1 65.9 ± 4.3 1316.3 ± 15.2

84.9 ± 4.6 72.1 ± 1.9 66.6 ± 2.8 1306.5 ± 17.1

78.9 ± 2.4 69.0 ± 2.5 65.0 ± 3.7 1311.5 ± 28.7

77.6 ± 4.9 67.7 ± 2.5 62.9 ± 5.1 1301.8 ± 32.8

20NewsG

ACC NMI ARI |C1 |

38.4 ± 2.5 39.9 ± 1.0 23.0 ± 1.3 1453.7 ± 15.3

37.0 ± 1.4 39.1 ± 0.8 22.3 ± 1.3 1405.2 ± 8.9

38.4 ± 2.4 39.9 ± 0.7 23.0 ± 0.8 1439.8 ± 11.8

25.9 ± 1.3 32.9 ± 1.6 16.2 ± 1.2 1144.3 ± 25.3

25.8 ± 1.5 32.8 ± 2.0 16.1 ± 1.5 1135.0 ± 21.9

37.9 ± 2.0 39.7 ± 0.7 23.2 ± 1.4 1444.9 ± 14.8

39.5 ± 1.5 40.6 ± 0.7 23.7 ± 1.0 1458.0 ± 11.4

MouseAtlas

ACC NMI ARI |C1 |

67.5 ± 6.0 67.6 ± 2.3 56.3 ± 6.2 14566.0 ± 58.8

65.9 ± 2.5 67.6 ± 2.1 55.4 ± 3.5 14662.8 ± 7.2

67.7 ± 2.6 68.1 ± 1.4 56.5 ± 3.4 14576.3 ± 71.2

64.2 ± 3.2 66.5 ± 3.3 52.6 ± 5.3 14524.3 ± 35.0

63.2 ± 2.0 68.0 ± 0.5 54.3 ± 0.9 14508.8 ± 17.1

68.1 ± 12.5 64.2 ± 10.9 51.2 ± 21.8 14616.6 ± 64.7

74.5 ± 3.0 70.6 ± 1.6 63.2 ± 2.9 14605.5 ± 59.3

GeneExp

ACC NMI ARI |C1 |

99.6 ± 0.1 98.4 ± 0.2 99.1 ± 0.1 6445.1 ± 3.1

99.6 ± 0.1 98.3 ± 0.2 99.1 ± 0.2 6446.0 ± 2.8

92.8 ± 7.2 93.6 ± 4.7 91.0 ± 8.3 6272.2 ± 239.6

99.6 ± 0.0 98.4 ± 0.1 99.1 ± 0.1 6444.4 ± 2.7

99.6 ± 0.0 98.5 ± 0.0 99.2 ± 0.0 6443.0 ± 0.0

99.6 ± 0.1 98.3 ± 0.2 99.0 ± 0.1 6447.3 ± 3.2

99.6 ± 0.0 98.5 ± 0.0 99.2 ± 0.0 6443.0 ± 0.0

HDendritic

ACC NMI ARI |C1 |

87.5 ± 7.2 77.8 ± 3.8 79.6 ± 5.8 16672.9 ± 406.2

81.2 ± 5.9 74.6 ± 3.4 74.8 ± 4.9 16635.5 ± 406.8

84.3 ± 7.6 76.4 ± 4.5 76.9 ± 6.7 16601.9 ± 483.0

49.1 ± 14.5 27.8 ± 25.1 19.7 ± 18.9 5940.5 ± 4774.3

46.0 ± 14.1 22.1 ± 24.4 15.3 ± 18.1 5667.2 ± 3879.9

72.1 ± 6.8 64.1 ± 9.6 58.2 ± 15.0 15235.7 ± 1694.7

66.3 ± 5.1 55.4 ± 7.1 45.0 ± 11.4 13682.6 ± 1782.3

inertia and BIC are min–max normalized for each algorithm; the Silhouette score is bound within [−1, 1]. The remaining setting is equal to the one described in Sect. 4.6. We vary the number of clusters K ∈ {2, 3, . . . , 30} and, for each K , run each clustering method 20 times. In the end, we only evaluate the run with the best inertia. The results for Synth, GeneExp and BBCSports are illustrated in Fig. E3. We observe that all standard K -estimation techniques struggle to identify the ground-truth number of clusters for the Synth data set. Specifically, the elbow method suggests K ≈ 7, while the Silhouette score recommends K = 2 and the BIC score suggests K = 30. For the GeneExp data set, the K -estimation is more consistent; the elbow method and Silhouette score both indicate K ≈ 6 for most algorithms (excluding RCA+KM), while the BIC score recommends K = 12 or K = 13. For BBCSports, both the elbow method and Silhouette score provide poor recommendations, whereas BIC yields K within [3, 8] for all algorithms except standard k -Means (KM). Overall, we do not have a clear winner that is performing well in

40

(a) Inliers.

(b) Outliers.

Fig. D2: Visual examples of eight inliers and eight outliers identified by 3CPO in the Optdigits data set.

all scenarios. Our proposed method 3CPO, on the other hand, was able to provide a reasonable number of clusters in all three cases. In addition to the visual examples presented in Fig. E3, we report results for all data sets in Tab. E7, stating the estimated number of clusters K together with the corresponding ARI and Purity (Manning et al. 2008) values. We include Purity to assess how pure clusters are when K is overestimated. Since Purity increases mechanically with larger K , it should be interpreted alongside the K -estimation error. Across data sets, the Silhouette score tends to underestimate K as 56 of 62 outcomes are K = 2. This leads to good results for Wholesales and SportA. In contrast, the BIC score often overestimates K , returning the upper bound K ∈ {29, 30} in 44 cases (note that the maximum K is 30 in our experiments). This often leads to high Purity values but significantly lower ARI results. It should be noted that to some degree these weaknesses may be related to the data transformations that have been conducted (STD, MM, RF, RCA). For Optdigits, elbow and Silhouette lead to very good results, providing estimates of K = 9 or K = 10 for all k -Means-based algorithms except RCA+KM. In this case, the results for 3CPO and TauCC are far worse. In general, 3CPO struggles to match the ground truth K on most tabular data sets. However, it performs notably better than the competitors on high-dimensional text data, achieving higher ARI and Purity values in most experiments. Concretely, it estimates the correct K for Synth and BBCSports, is only off by one for BBCNews and GeneExp, and is close for 20NewsG and WebKB. Based on the results for Synth and 20NewsG, 3CPO appears capable of accurately estimating both low and high cluster counts. 41

5

10

15

K

20

25

0.5

BIC score

Loss

Silhouette score

0.6

0.4 0.3 0.2

30

5

10

15

20

K

25

5

30

10

15

K

20

25

30

(a) Loss (inertia), Silhouette score, and BIC score for the Synth data set (Kgt = 3).

0.6

BIC score

Loss

Silhouette score

0.8

0.4 0.2 0.0

5

10

15

K

20

25

30

5

10

15

20

K

25

5

30

10

15

K

20

25

30

(b) Loss (inertia), Silhouette score, and BIC score for the GeneExp data set (Kgt = 5).

0.2

BIC score

Loss

Silhouette score

0.3

0.1 0.0 0.1

5

10

15

K

20

25

30

5

10

15

K

20

25

5

30

10

15

K

20

25

30

(c) Loss (inertia), Silhouette score, and BIC score for the BBCSports data set (Kgt = 5). SKM

KM

STD+KM

MM+KM

RF+KM

RCA+KM

Fig. E3: Loss (inertia), Silhouette score, and BIC score of the k -Means-based comparison algorithms for an increasing number of clusters K . The colored dots indicate the suggested number of clusters for each algorithm and evaluation method.

Regarding the co-clustering algorithm TauCC, which determines K intrinsically, we find that it correctly identifies K = 3.0 (averaged across runs) for Synth. However, it tends to underestimate the number of clusters for GeneExp and BBCSports, returning an average of K = 3.0 for both. This trend of underestimation is consistent across other data sets, with averages of K = 2.1, K = 9.5, and K = 3.6 for Optdigits, 20NewsG, and MouseAtlas, respectively.

42

Table E7: The estimated number of clusters K and the corresponding ARI and Purity values obtained by different K -estimation strategies. TauCC intrinsically estimates K , 3CPO uses the method described in Sect. 4.6, and the k -Means-based approaches use the elbow method, Silhouette score (SIL) and BIC score. The result that best matches the ground truth is highlighted in bold. Data set

Metric

3CPO

TauCC (mean)

Elbow

SKM SIL

BIC

Elbow

KM SIL

BIC

STD+KM Elbow SIL BIC

MM+KM Elbow SIL BIC

RF+KM Elbow SIL BIC

RCA+KM Elbow SIL BIC

Synth (Kgt = 3)

K ARI Purity

3 95.5 98.5

3.0 25.1 59.8

8 53.1 86.0

2 −0.1 34.1

30 25.2 95.1

7 16.7 64.8

2 0.4 36.7

29 10.2 88.3

7 60.4 89.0

2 0.0 34.2

29 31.7 94.6

7 63.3 88.1

2 −0.1 34.1

30 22.0 94.3

8 50.6 85.3

2 0.0 34.1

30 23.1 95.3

8 21.7 57.4

2 0.0 34.3

29 17.7 83.1

Wholesales (Kgt = 2)

K ARI Purity

30 3.9 88.6

3.0 27.6 75.7

8 12.7 82.3

2 26.5 75.9

29 5.1 86.6

8 23.2 86.4

2 −3.1 67.7

30 7.3 90.7

8 13.4 80.7

2 28.2 76.8

30 5.6 84.5

9 13.3 81.8

2 27.8 76.6

30 7.9 87.3

8 8.8 80.9

2 21.3 73.2

30 2.8 83.6

7 15.3 85.5

4 18.8 84.3

30 3.9 87.0

SportA (Kgt = 2)

K ARI Purity

19 3.2 79.3

1.7 15.8 70.1

8 8.0 80.1

2 29.5 77.2

23 2.7 78.7

6 14.5 74.3

3 19.6 72.1

30 6.3 80.9

9 7.0 78.3

2 31.9 78.3

22 3.1 78.8

9 8.0 80.1

2 25.9 75.6

29 2.6 79.2

9 6.2 78.2

2 7.5 64.3

26 2.5 78.9

8 4.8 0.66

2 0.1 63.6

29 6.0 75.9

Optdigits (Kgt = 10)

K ARI Purity

30 48.0 91.4

2.1 10.6 20.3

9 60.1 73.4

9 60.1 73.4

30 43.6 91.7

10 67.1 80.3

10 67.1 80.3

30 43.9 94.0

9 60.3 73.4

9 60.3 73.4

30 43.1 92.2

10 67.0 80.3

10 67.0 80.3

30 50.8 94.3

9 59.6 73.2

9 59.6 73.2

30 44.8 92.0

8 0.0 10.7

2 0.0 10.2

30 11.8 30.9

BBCSports (Kgt = 5)

K ARI Purity

5 92.0 97.2

3.0 26.2 51.6

10 17.3 64.2

2 5.8 36.0

8 22.4 66.8

9 0.3 37.7

2 0.0 36.0

14 0.7 41.2

10 14.1 60.0

2 4.2 36.0

6 11.3 47.2

12 8.9 50.2

2 1.6 36.0

6 7.1 47.1

11 11.1 54.5

2 5.6 36.0

7 15.3 57.8

8 0.8 39.5

2 0.3 36.5

3 1.2 38.7

BBCNews (Kgt = 5)

K ARI Purity

6 82.3 96.0

3.4 41.8 60.5

14 20.4 69.8

2 4.6 26.8

18 17.9 71.0

6 6.3 35.2

2 3.9 28.2

29 11.5 55.6

12 19.7 66.9

2 3.3 26.3

14 19.6 66.9

15 14.8 59.3

2 2.1 26.0

15 14.8 59.3

11 20.4 63.0

2 2.3 27.0

12 19.6 61.5

15 0.4 30.5

2 −0.1 23.6

17 1.4 30.7

WebKB (Kgt = 6)

K ARI Purity

9 29.1 71.0

2.9 11.3 48.3

9 13.7 59.5

2 0.1 36.3

30 8.6 65.8

7 3.9 39.5

2 0.0 36.3

30 5.8 44.8

9 13.3 59.2

2 0.7 36.3

27 8.1 63.9

9 10.3 54.7

2 −0.4 36.3

26 7.3 60.0

12 10.6 55.3

2 −0.8 36.3

30 10.4 64.9

4 0.1 36.9

2 0.2 36.9

28 −1.7 39.3

Reuters (Kgt = 5)

K ARI Purity

18 25.6 96.7

2.0 43.2 68.8

8 18.9 68.9

2 27.2 64.8

30 11.0 85.1

8 16.3 60.2

2 9.2 48.9

30 12.0 70.0

8 17.8 68.0

2 26.4 64.5

30 11.3 85.8

11 14.7 72.3

2 27.0 64.5

29 10.5 80.8

9 11.2 65.0

3 15.2 63.8

29 5.9 76.9

6 0.2 47.6

2 0.2 47.4

28 0.3 48.4

20NewsG (Kgt = 20)

K ARI Purity

22 22.9 41.7

9.5 2.1 8.7

11 1.5 11.4

2 0.4 7.5

30 2.0 13.8

6 0.0 5.9

2 0.0 5.3

30 0.5 8.3

11 1.8 11.2

2 0.6 8.3

30 2.0 13.6

12 1.2 10.8

2 0.3 7.7

26 1.7 12.7

11 0.8 9.7

2 0.4 7.4

30 1.5 11.3

5 0.0 5.3

2 0.0 5.3

30 0.0 5.6

MouseAtlas (Kgt = 11)

K ARI Purity

26 55.0 65.3

3.6 34.4 50.4

9 39.0 68.0

2 3.2 25.2

30 28.6 82.5

9 1.5 34.4

2 0.7 21.9

30 1.2 38.0

11 37.1 68.0

2 17.5 43.8

29 31.2 81.8

10 34.9 63.3

2 3.8 27.7

30 26.9 77.6

10 24.5 56.8

2 2.5 25.1

30 28.0 73.8

10 0.0 20.7

2 0.0 20.4

30 0.4 22.0

GeneExp (Kgt = 5)

K ARI Purity

6 87.9 99.6

3.0 53.1 67.2

6 87.6 99.3

6 87.6 99.3

13 45.9 99.5

7 71.4 99.3

6 87.6 99.3

12 48.7 99.5

6 87.8 99.4

6 87.8 99.4

12 48.7 99.6

7 73.2 99.4

6 87.1 99.4

12 44.6 99.4

7 71.2 99.1

6 87.6 99.3

12 48.4 99.6

12 0.2 38.5

2 0.1 37.7

22 0.7 39.7

HDendritic (Kgt = 4)

K ARI Purity

29 74.9 95.8

2.7 42.3 64.3

6 54.9 92.7

4 80.1 92.0

29 28.8 95.8

11 82.1 93.2

2 −0.1 33.5

30 38.5 95.5

7 55.7 93.6

3 68.9 77.4

29 25.3 95.1

7 49.8 89.4

5 61.4 88.5

23 24.3 94.3

11 82.1 93.2

2 −0.1 33.5

30 38.5 95.5

3 −0.1 33.5

2 −0.1 33.5

2 −0.1 33.5

43

Related documents

• A Quasi-Likelihood Approach to Zero-Inflated Spatial Count Data#320064
• Spectral clustering in the Gaussian mixture block model#609727
• Correlation Clustering with Random Partial Information#620715
• Correlation Clustering with Random Partial Information#619036
• Penalized Likelihood Methods for Modeling Count Data#141607