Graphical Dirichlet Process for Clustering Non-Exchangeable Grouped Data

Abstract

We consider the problem of clustering grouped data with possibly non-exchangeable groups whose dependencies can be characterized by a known directed acyclic graph. To allow the sharing of clusters among the non-exchangeable groups, we propose a Bayesian nonparametric approach, termed graphical Dirichlet process, that jointly models the dependent group-specific random measures by assuming each random measure to be distributed as a Dirichlet process whose concentration parameter and base probability measure depend on those of its parent groups. The resulting joint stochastic process respects the Markov property of the directed acyclic graph that links the groups. We characterize the graphical Dirichlet process using a novel hypergraph representation as well as the stick-breaking representation, the restaurant-type representation, and the representation as a limit of a finite mixture model. We develop an efficient posterior inference algorithm and illustrate our model with simulations and a real grouped single-cell data set.

Keywords: Bayesian nonparametrics; clustering; directed acyclic graph; family-owned restaurant process; non-exchangeable groups.

Figure 1:

DAG for AR2.

Figure 2:

Family tree with three generations. Males are depicted with the color blue and females with red.

Figure 3:

Sharing of features by GDP.

Figure 4:

Schematic illustration of HDP and GDP. HDP is a special case of GDP when the DAG is a fork.

Figure 5:

DAG augmented with a hidden root $G_1^{\left(0\right)}$, indicated by the dashed arrows. The original root nodes are $G_1^{\left(1\right)},\dots ,G_{l_1}^{\left(1\right)}$.

Figure 6:

Illustration of hypernodes (represented by dashed ovals) of the DAG for our motivational problem. (a) Hypernode $H_2$ consists of the generation-1 ancestors (i.e., $G_2$ and $G_3$) of node $G_6$. (b) Hypernode $H_3$ consists of the generation-1 ancestors (i.e., $G_3$ and $G_4$) of node $G_7$. (c) Hypernode $H_4$ consists of the generation-1 ancestors (i.e., $G_5,G_6$, and $G_7$) of node $G_8$. Hypernode $H^{*}$ consists of the generation-2 ancestors (i.e., $G_2,G_3$, and $G_4$) of node $G_8$.

Figure 7:

The DAG of experimental groups.

Figure 8:

Clustering performance of GDP for different sample sizes. The colors indicate the estimated clusters by GDP. Adjusted Rand index is reported at the top of each panel.

Figure 9:

The boxplots of the adjusted Rand indices for GDP, HDP, and k-means for all sample sizes.

Figure 10:

Clustering of the group-specific single-cell data whose dimensions are reduced to 2 by UMAP by (a) GDP and (b) HDP.