Bayesian community detection for networks with covariates

There are several works in the literature similar to our model that also use a Bayesian nonparametric approach for tasks related to node clustering.

A pioneering work in the area is that of Kemp et al. (2006). Motivated by the complex system of relations underlying semantic knowledge, Kemp et al. (2006) propose the infinite relational model (IRM) for discovering and clustering underlying structure in relational data sets. In this framework, the observed data are assumed from $n$ types (people, demographic features, answers to a personality test, etc.) and $m$ relationships (person $i$ likes person $j$, feature $x$ causes answer $y$, etc). The motivating example given in Kemp et al. (2006) is that of clustering people, represented by set $T^{1}$, based on social predicates, represented by set $T^{2}$. The observed data is the tensor $T^{1}\times T^{1}\times T^{2}\mapsto\{0,1\}$ whose $(i,j,p)$ entry determines whether persons $i$ and $j$ have social predicate type $p$. The idea is to simultaneously cluster $T^{1}$ and $T^{2}$ so that the tensor is roughly constant within the resulting clusters. In modern language, the model proposed by Kemp et al. (2006) is the so-called tensor SBM (Kim et al., 2017; Wang and Zeng, 2019; Lei et al., 2020) but with a CRP prior on the labels of each dimension to allow for infinite clusters a priori. IRM was later explicitly adopted in Mørup and Schmidt (2012) for community detection in network data, as opposed to relational data. IRM is quite flexible and can, for example, be used to incorporate an attribute or feature taking finite values, by taking $T^{2}$ above to be the levels of that attribute. However, this attribute should be interpreted as an edge feature, and moreover, IRM needs to have observations on the connectivity of persons $(i,j)$ for all possible levels of this attribute. Adding each feature then requires increasing the dimension of the tensor by one, and demanding lots of observations which are not available in practice in network problems.

More recently, nonparametric Bayesian network models that accommodate nodal covariates have been considered, but mostly with the mixed membership SBM (MMSBM) framework of Airoldi et al. (2008). For example, Kim et al. (2012) introduced the nonparametric metadata dependent relational (NMDR) model, that essentially couples the MMSBM likelihood with node-covariate-dependent prior on cluster labels. More specifically, they assume latent community vectors $\eta_{k}$ that interact with node features $\phi_{i}$ to produce a score $v_{ki}$ that determines how likely node $i$ belongs to community $k$, a priori. They assume that $v_{ki}$ are normal with mean $\langle\eta_{k},\phi_{i}\rangle$ and then translate these real-valued affinities to probabilities $\pi_{ki}$ via a logistic-stick breaking process (Ren et al., 2011). The $\pi_{i}=(\pi_{ki})$ then determine the edge probabilities via $\mathbb{E}[A_{ij}\,|\,\pi_{i},\pi_{j}]=\pi_{i}^{T}W\pi_{j}$ where $W$ is the connectivity matrix.

Along the same lines, Zhao et al. (2017) extends the edge partition model (EPM) of Zhou (2015) to incorporate binary node features. The EPM has similarities to MMSBM with novel uses of a Bernoulli-Poisson likelihood coupled with a nonparametric partition model. More specifically, the latent Poisson component $X=(X_{ij})$ still follows a MMSBM decomposition with $\mathbb{E}[X_{ij}\,|\,\phi_{i},\phi_{j}]=\phi_{i}^{T}\Lambda\phi_{j}$ where $\phi_{i}$ are the soft community assignments and $\Lambda$ the connectivity matrix. Similar to Kim et al. (2012), the nodal covariate information is incorporated in constructing a prior on $\phi_{i}=(\phi_{ik})$. The prior assumes $\phi_{i}$ to be drawn from a Gamma distribution with mean $\mathbb{E}[\phi_{ik}]=c_{i}b_{k}\prod_{\ell=1}^{L}h_{\ell k}^{f_{i\ell}}$ where $f_{i\ell}$ is the $\ell$th binary feature of node $i$. Note that by introducing $\eta_{k}:=(\log h_{\ell k})$ and $f_{i}=(f_{i\ell})$, one can write $\mathbb{E}[\phi_{ik}]=c_{i}b_{k}\exp(\langle\eta_{k},f_{i}\rangle)$, showing that essentially the same inner product interaction of feature and latent community vectors as in Kim et al. (2012) is used by Zhao et al. (2017).

As in Kim et al. (2012) and Zhao et al. (2017), our model also incorporates node features into the partition prior; however, we are modeling hard community assignments rather than soft assignment vectors, making the problem somewhat more challenging. More importantly, our approach allows for a more general dependence of the partition on the features via a kernel $q(x_{i}\,|\,\xi)$, compared to the simple inner product approach used in both Kim et al. (2012) and Zhao et al. (2017). Our approach is not limited to binary features and by incorporating more complexity into $q(x_{i}\,|\,\xi)$, we can potentially model more complex feature/community interactions in the prior.

The last closely related work that we discuss is that of Newman and Clauset (2016). They consider node features (metadata) that take values in a finite discrete set (say $\mathbb{X}$). Similar to our work, the node metadata is used to influence the prior on the community assignements. In our notation, they assume $p(z_{i}\,|\,x_{i})=\gamma_{z_{i},x_{i}}$ where $\gamma~{}=~{}(\gamma_{k,x})\in~{}[0,1]^{K\times|\mathbb{X}|}$ is a parameter matrix to be estimated form the data. Compared to the inner product model of Kim et al. (2012) and Zhao et al. (2017), this approach gives a more flexible model for the interaction of the communities and features. The drawback is that it is limited to discrete features and if $|\mathbb{X}|$ is large, there is potential for over-fitting without further regularization of the $\gamma$ matrix. Newman and Clauset (2016) use an EM algorithm to estimate the parameters, and they assume the number of communities to be known.

We now derive a Gibbs sampler to sample from the complete posterior distribution of $(\bm{z},\bm{\xi},\bm{\eta})$ given $A$ and $\bm{x}$. The main challenge is deriving the updates for $\bm{z}$.

We sample from $\bm{z}$, $\bm{\xi}$, and $\bm{\eta}$ through their full conditional distributions, which are given bellow, until reaching convergence, and then obtain a sample of adequate size of the posterior distribution for inference.

We first consider simulated networks with continuous covariates, and in particular, the Gaussian setting (9). We generate networks from an SBM having connectivity matrix $\eta=(\eta_{k\ell})\in[0,1]^{K\times K}$ with

The parameter $r\in[0,1]$ controls the magnitude of disparity between the within and between connectivites and is a measure of network information for the community structure. In our simulations, we set $p=0.1$ and vary $r$. We consider $n=150$ nodes with $K=2$ communities of 100 and 50 nodes, respectively.

For each node, we generate $d=2$ features, with one signal feature related to the community structure and one noise feature whose distribution is the same for all nodes. Letting $x_{i}\in\mathbb{R}^{2}$ be the feature vector for node $i$ and $e_{1}=(1,0)$, we take

where $\sigma_{1}=+1$, $\sigma_{2}=-1$ and $z_{i}\in\{1,2\}$ is the community label of node $i$. Here $\mu\in[0,\infty)$ is proportional to the signal-to-noise ratio of the covariate information.

Figure 2 shows the mean NMI with a 50% quantile band from BCDC and competing methods, averaged over 500 replications, under different settings of $r$ and $\mu$. For BCDC, we have used parameters $\alpha=10$, $\beta=1$ and $\tau=s=1$, and ran the sampler for 1000 iterations. Note that in our comparison, all of the competing methods were given an additional advantage by assuming the knowledge of the true number of communities. However, our method (red) consistently outperforms these other methods. An interesting notable case is that of high network information ($r=0.3$) and pure noise covariate information ($\mu=0$). In this case, BCDC performs as well as BSBM which only operates on network information, while CASC performs much worse being misled by pure noise covariates.

We next consider a simulation study for networks with categorical covariates. For each node $i$, we again generate $d=2$ features with one signal feature related to the community structure and one noise feature whose distribution is the same for all nodes. We consider two designs:

1. (0)

   We consider networks with $n=150$ nodes and $K=3$ equally-sized communities. The signal features are taken to be the true community labels and the noise features are uniformly distributed on $\{1,2,3\}$.

2. (0)

   We consider networks with $n=150$ nodes and $K=2$ communities of 100 and 50 nodes. We create two 4-category features. Let $x_{i}=(x_{i1},x_{i2})\in\{1,2,3,4\}^{2}$ be the feature vector for node $i$. We use the following generative model

   	$\displaystyle\theta_{1},\theta_{2}$	$\displaystyle\sim\operatorname{\mathsf{Dir}}(\bm{1}_{4})\enskip,$
   	$\displaystyle x_{i1}\,|\,z_{i}$	$\displaystyle\sim\theta_{z_{i}},\quad x_{i2}\,|\,z_{i}\sim\bm{1}_{4}/4\enskip,$

   where, for example, $x_{i1}\sim\theta_{z_{i}}$ means that $x_{i1}$ is a categorical variable with probability vector $\theta_{z_{i}}$.

In both cases, we use an SBM with connectivity (22), setting $p=0.1$ and varying $r$ from 0.1 to 0.8. For the parameters of our model, we again set $\alpha=10$, and ran the chain for 1,500 iterations. As above, the results are given over 500 replicates.

Figure 3 shows NMI as a function of $r$ (the network information measure) under the two covariate designs. Once again, all methods except BCDC were given the true number of communities. The NMI values obtained under the proposed model are generally higher than those of the other models with a slightly larger variance, which is likely due to the additional uncertainty in estimating the number of the communities.

Here, we perform a simulation for larger networks with more communities and a mix of continuous and categorical variables. We let the number of nodes $n$ vary from 300 to 1000 and set $K=n/50$ communities. The features are chosen so that neither perfectly separates the clusters, but both are informative. In particular, we take

i.e. $x_{1i}\sim N(1,1)$ for $z_{i}\in\{2,4,\ldots\}$ and $x_{1i}\sim N(-1,1)$ for $z_{i}\in\{1,3,\ldots\}$. We also take $x_{2i}=1$ for $z_{i}\in\{1,2,\ldots K/2\}$ and $x_{2i}=2$ for $z_{i}\in\{K/2+1,\ldots,K\}$. As before, we use an SBM with connectivity (22), setting $p=0.3$ and $r=0.35$.

The results are shown in Figure 4. We find that BCDC is competitive with the other methods when $n\leq 600$, but is superior for larger networks with $n>600$. We also show in Figure 4 the run time for each method. We see that BCDC scales linearly with $n$ and is faster than CASC for all of the networks.

We next consider a setting from Yan and Sarkar (2021), who proposed a covariate-regularized procedure for community detection in sparse graphs. This allows us to explore whether our model works for sparse networks, as well as networks with high-dimensional features. We consider the exact simulation setting as in Yan and Sarkar (2021), in which the networks are generated from a 3-block SBM on 800 nodes with block-size ratios $3:4:5$. The true connectivity matrix is

leading to a very sparse network, with expected average degree $\approx 5.8$. The covariates are generated from 100-dimensional Gaussian distributions $N(\mu_{z_{i}},I_{100})$, with centers that are only non-zero on the first two dimensions:

In this setting, it is difficult to distinguish clusters 1 and 2 using the network information alone, and clusters 2 and 3 based on nodal covariates alone.

This experiment was repeated 100 times for independently generated samples. In each replicate, we ran the chain for 1,000 iterations. The results are shown in Figure 5. Note that our method consistently achieves a better NMI than all of the other methods. Although we did not carry out a direct comparison with the method from Yan and Sarkar (2021) since their work focuses on regularizing high-dimensional features, our NMI results are stable and seem to be higher than those reported in Yan and Sarkar (2021). Importantly, we also see in Figure 5 that BCDC is only slightly slower than all of the methods that use only the network or only the covariates, but is considerably faster than CASC and CASCORE, which also use both the network and the nodal information. This illustrates the disadvantage of CASC for larger sparse networks and highlights the efficiency of our MCMC algorithm. That CASC slows down for larger networks can be attributed to the addition of the dense $\tau XX^{T}$ to the sparse Laplacian $L$, resulting in an overall dense similarity matrix $L_{x}$.

Finally, we consider a network model with homophily, which is the tendency for nodes to be connected when they share a nodal feature. For this, we sample a categorical covariate $x_{i}$ with two levels, and let

where $P_{z_{i}z_{j}}$ is an SBM with connectivity (22), setting $p=0.3$ and $r=0.7$. This creates $2K$ communities, and separates the effect of community structure from the effect of node-level covariates. We take $K=3$ and vary $\beta$ in $[-0.2,0.2]$. Note that when $\beta>0$, we say the nodes exhibit positive homophily. We run this for $n=600$ and $n=1200$.

The results are show in Figure 6. We find that BCDC has superior performance to the other methods even when they are provided the true number ($2K$) of communities. The performance increases as the homophily effect increases in magnitude, which we should expect because the homophily effect is an informative covariate that is not included with BSBM.

In addition to computing the NMI with the (alleged) ground truth labels, it is also helpful to compare the performance using the Bayesian information criterion (BIC) based on an SBM likelihood conditional on the labels. This is especially important because, unlike in the simulations, the “true” clusters are exogenously specified. The (conditional) BIC is defined as the log-marginal likelihood muliplied by $-2$. That is,

where $K$ is the number of communities in $\bm{z}$, $c(K)=\frac{1}{2}K(K+1)+(K-1)$ is the degrees of freedom in the parameters $(\bm{\eta},\bm{\pi})$, $\bm{\pi}$ is the label prior, and $(\bm{\hat{\eta}},\bm{\hat{\pi}})$ is the maximum likelihood estimator of those parameters, i.e., the maximizer of $(\bm{\eta},\bm{\pi})~{}\mapsto~{}p(A~{}\mid~{}\bm{\eta},\bm{\pi},\bm{z})$. We assume a uniform prior over $\bm{\eta}$ and $\bm{\pi}$. Note that (24) is the well-known approximation to the BIC (Schwarz, 1978; Konishi and Kitagawa, 2008) and it shows the usefulness of $\text{BIC}(\bm{z})$ as a measure of performance for real networks: Due to the presence of the complexity term $\approx c(K)\log(n^{2})$, we get a good balance of the model fit and the number of communities. Label vectors $\bm{z}$ with smaller $\text{BIC}(\bm{z})$ are thus more desirable from a block modeling standpoint, regardless of their relation to the ground truth.