CS Paper Radar

Poisson Subspace Clustering: Focusing on the Essentials in Count Data

Collin Leiber, Kai Puolamäki, Heikki Mannila

cs.LG ·submitted 2026-08-24 14:13 UTC · v1
publishedcode/dataunusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Selective Inference for Clustering Under Unknown Covariance

cs.LG stat.MEstat.AP ·2026-10-12 ·Yiqun T. Chen, Lucy L. Gao
similarity 0.55
Abstract

Unsupervised clustering is widely used to discover underlying group structure, after which researchers often seek to validate these groups via post-hoc hypothesis testing on the population means. However, using the same data both to form clusters and to test for a difference in means inflates the Type I error rate. Recent work in selective inference has proposed solutions when the underlying data are drawn from a multivariate Gaussian distribution with a known covariance matrix or an unknown isotropic covariance matrix. We propose a new selective test for the difference in means between two clusters that provably controls the Type I error rate under an arbitrary unknown covariance matrix. Our test statistic does not require estimating the feature covariance matrix; instead, it leverages a Monte Carlo sampling procedure over the set of orthogonal matrices. We show that this new selective test can be computed efficiently, and we derive closed-form solutions when clusters are formed using k-means or hierarchical clustering. In simulations, we demonstrate that our proposed p-value controls the selective Type I error rate and achieves substantial power, and we illustrate its application on gene expression and drug review data sets.

0.22

Efficient and Generalizable Archetypal Analysis for Discrete Data

cs.LG stat.ML ·2026-10-08 ·A. Emilie J. Wedenborg, Jesper Løve Hinrich, Morten Mørup
similarity 0.53
Abstract

Archetypal Analysis (AA) represents observations as convex combinations of extremal data-driven profiles, yielding interpretable low-dimensional descriptions of complex datasets. Classical AA relies on a least-squares objective, which is poorly suited to discrete observations such as binary, count, and categorical data. We introduce an efficient likelihood-based framework for AA supporting Bernoulli, Poisson, and multinomial observation models. Our optimization scheme employs local quadratic approximations of the negative log-likelihood, enabling constrained updates through sequential minimal optimization (SMO) and an active-set method. Scalability is improved by bounding the active set while preserving simplex feasibility. We further introduce a cross-validated predictive likelihood criterion for selecting the number of archetypes, providing a principled alternative to reconstruction-error heuristics and stability-based diagnostics. Synthetic experiments demonstrate computational efficiency and accurate recovery of model complexity. Applications to single-cell RNA sequencing, microbiome composition, and somatic mutation data show that the learned archetypes capture interpretable domain-specific structures while achieving competitive likelihood fits and stable solutions. Overall, the proposed framework enables efficient likelihood-based archetypal analysis of discrete data, complemented by predictive likelihood-based model selection.

0.25

Efficient Estimation of High Information Projections using Nearest Neighbours

cs.LG stat.ML ·2026-08-26 ·David P. Hofmeyr
similarity 0.52
Abstract

An intuitive method for dimensionality reduction is proposed, which is highly effective for finding interesting projections of multivariate data. Following similar intuitive motivation to a number of existing techniques, the proposed method is based on enhancing the nearest neighbour relationships in the data. The proposed projection arises from the spectral decomposition of a matrix designed to encode the local covariance structure in the data, where the local covariance at a point is captured by pairs of its nearest neighbours. We show that under standard regularity conditions this matrix is a consistent estimator of the so-called ``Density Information Matrix'' (DIM); a non-parametric analogue of the Fisher Information Matrix. Spectral decompositions of DIMs have been shown to be connected with the important problems of Independent Components Analysis and, in the supervised context, Sufficient Dimension Reduction. However, existing estimators of the DIM are computationally expensive to compute and only target the DIM of a surrogate density, which is proportional to the square of the true underlying density. In addition, we go on to explore the practical utility of our method in aiding the downstream tasks of cluster analysis and outlier detection.

0.22

ExplainCC: Explaining Correlated Clusters by Node Labels

cs.LG cs.DS ·2026-10-28 ·Nadeesha Shyami Kumari Herath Mudiyanselage, Florian Adriaens, Nikolaj Tatti
top venue similarity 0.52
Abstract · Accepted to CIKM 2026

An increasingly important requirement for clustering algorithms is that decisions and outcomes need to be clearly understandable for human users. We address this requirement for the Correlation Clustering (CC) problem, in case the objects to be clustered are accompanied by labels. In CC one seeks to partition a set of objects into clusters based on pairwise similarity and dissimilarity information. Our proposed model only considers clusters that can be explained by a label tree, which is essentially a decision tree that partitions the objects according to labels. The goal is to find an explainable partition of the data that minimizes the CC objective function. We formalize this problem from a theoretical viewpoint, and prove several hardness of approximation results, also when constraining the size of the tree. Our proposed greedy method finds locally optimal splits, and works recursively in a top-down approach. To efficiently compute the best split, we carefully maintain certain counters. An experimental evaluation demonstrates its effectiveness. The proposed algorithm processes graphs with over million edges in a few minutes, can find the ground truth in synthetic data, and is able to produce interpretable clusters in real world networks.

0.35

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

cs.LG stat.MLmath.PRmath.SP ·2026-10-23 ·Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee, Himasish Talukdar
similarity 0.52
Abstract

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.

0.22

Dirichlet Process Mixtures within Semiparametric Bayesian Networks: A Novel Conditional Density Estimation Approach

cs.LG cs.AIstat.ML ·2026-10-26 ·Victor Alejandre, Pedro Larrañaga, Concha Bielza
code/data similarity 0.51
Abstract

Semiparametric Bayesian networks (SPBNs) are flexible probabilistic graphical models for representing joint distributions of continuous variables through lower-dimensional conditional probability distributions (CPDs). Existing SPBN models use kernel density estimators (KDEs) for non-parametric CPD modeling, but their one-component-per-observation mixture representation can lead to increased inference costs and density estimation errors, which can be limiting. In this work, we define a new CPD modeling approach for non-parametric components based on Bayesian non-parametric Dirichlet Process Mixtures (DPMs) within SPBNs. DPMs provide a data-adaptive clustering of observations, yielding a more compact representation while retaining the flexibility of non-parametric density estimation, unlike KDE. This results in lower inference costs while improving density estimation performance. We implement the proposed DPM-based SPBN (DPM-SPBN) by extending the open-source PyBNesian package and evaluate it on synthetic and real-world data. For a given network structure, DPM-based CPDs significantly outperform state-of-the-art Bayesian network models for continuous variables in density estimation, achieving lower absolute log-likelihood errors on synthetic data. We further investigate the impact of the proposed CPD modeling on structure learning methods relying on CPD-based scores. DPM-based SPBNs achieve lower structure learning and density estimation errors than KDE-based SPBNs. Experiments on real-world data corroborate these findings, identifying DPM-based CPD modeling as the most effective alternative among the evaluated non-parametric approaches for continuous variables.

0.34

Causal DAG Identification for Count Data via Poisson Thinning Structural Equation Models

cs.LG stat.MEstat.ML ·2026-09-05 ·Penggang Gao, Ming Cai, Hisayuki Hara
unusual similarity 0.51
Abstract · 35 pages, 6 figures

Count-valued variables arise in many scientific and applied settings, yet explicit structural models that allow full identification of causal DAGs from observational data remain limited. The Poisson branching structural causal model (PB-SCM) provides a count-valued analogue of linear structural equation models using binomial thinning and independent Poisson exogenous variables, but its causal DAG is generally only partially identifiable. Building on this framework, we propose the Poisson thinning structural equation model (PT-SEM), which replaces binomial thinning in PB-SCM with Poisson thinning and allows node-wise exogenous distributions from diverse count-distribution families. Under node-wise regularity conditions, we establish identifiability of the causal DAG, the thinning coefficients, and the node-wise exogenous distributions. The same identification analysis extends to binomial thinning, yielding full identifiability whenever every nonsink has non-Poisson exogenous noise. We further develop a structure learning algorithm that optimizes, via dynamic programming, a BIC score based on local likelihoods evaluated at plug-in moment estimates, and establish its consistency for DAG selection. Simulations demonstrate favorable performance in DAG recovery and thinning-coefficient estimation, and a real-data application illustrates the practical utility of PT-SEM.

0.30

GO-Based Clustering for Learning Cluster-Level Causal Gene Regulatory Networks

cs.LG ·2026-10-05 ·Azlaan Mustafa Samad, Wei Zhang, Adèle H Ribeiro
similarity 0.51
Abstract

Discovery of causal relationships in high-dimensional Gene Regulatory Networks (GRN) is computationally challenging and often difficult to interpret due to dense connections. Therefore, grouping genes together into functional modules can improve tractability and biological interpretability. However, existing cluster level causal discovery methods assume access to a predefined admissible partitions, requiring the graph over clusters to be acyclic. Constructing such partitions is therefore challenging. In this work, we introduce GO-based Clustering for Causal Discovery (GO4CD), an algorithm that uses Gene Ontology (GO) to construct biologically meaningful gene partitions at multiple levels of granularity, while favoring those more likely to be admissible for causal discovery. GO4CD groups together genes participating in a shared biological process, and propagates gene annotations through the ontology hierarchy to achieve different granularity of partitions. Furthermore, we integrate GO4CD with Causal Learning over Clusters (CLOC) algorithm and evaluate recovery of true Markov equivalence class both with an oracle of conditional independencies and on simulated gene expression data using multivariate conditional independence tests. We evaluate GO4CD on multiple E.coli regulatory subnetworks and find that it is inadmissible in 18.1% of the cases, compared with 65.3-82.3% for the semantic-similarity baselines. Our results indicate that GO4CD is substantially better suited to learning causal GRNs defined over biologically meaningful gene clusters.

0.27