Two–Sample Test for Stochastic Block Models via Maximum Entry–Wise Deviation

Network data analysis has become a popular research topic in many fields, including gene classification, social relationship investigation, and financial risk management. In the past decades, the majority of works mainly focused on the large-scale network data with community structure, see, e.g., Newman & Girvan (2004); Newman (2006); Steinhaeuser & Chawla (2010). In the network data analysis, the stochastic block model proposed by Holland et al. (1983) is a popular tool to fit the network data with community structure, see, e.g., Snijders & Nowicki (1997); Nowicki & Snijders (2001); Bickel & Chen (2009); Rohe et al. (2011); Choi et al. (2012); Jin (2015); Zhang & Zhou (2016). The stochastic block model with $K$ communities assumes that $n$ nodes of the network are clustered into $K$ communities, that is, there exists a mapping of community membership (also known as community membership label) $g:[n]\rightarrow[K]^{n}$, where $[n]=\{1,\ldots,n\}$. Formally, $g(i)=k$ means that the node $i$ belongs to the community $k$. For an unweighted and undirected graph $G$, it can be represented by a binary symmetric adjacency matrix $A$, that is, $A_{ij}=1$ if there is a connection (or an edge) between node $i$ and node $j$ and $A_{ij}=0$ otherwise. Given the community membership label $g$, the stochastic block model assumes that the entries $A_{ij}(i>j)$ of the adjacency matrix $A$ are mutually independent Bernoulli random variables with probabilities $P_{ij}=B_{g(i)g(j)}$ for a certain symmetric probability matrix $B\in[0,1]^{K\times K}$, where matrix $P$ is called as edge-probability matrix. Then the stochastic block model is completely and uniquely determined by the pair $(g,B)$ up to label permutations of nodes.

The fundamental issues in the stochastic block model are model selection and community detection. Given an adjacency matrix $A$, the goal of model selection is to estimate the number of clusters or communities, and the goal of community detection is to cluster all nodes into different communities such that the connections between the nodes in the same community are dense and the connections between the nodes in the different communities are sparse. To enhance the flexibility of the model, variations of the stochastic block model were also proposed, such as the degree-corrected stochastic block model proposed by Karrer & Newman (2011) addressed the degree heterogeneity by introducing the additional node activeness parameters, and Airoldi et al. (2008) proposed the mixed membership stochastic block model, where a single node may belong to multiple communities. For the model selection, many methods are used to estimate the number of communities, including the sequential testing methods (Lei, 2016; Hu et al., 2021), and the likelihood-based methods (Saldña et al., 2017; Wang & Bickel, 2017; Hu et al., 2020). Meanwhile, the majority of efficient methods also have been proposed to recover the community structure, such as modularity (Newman, 2006), variational methods (Daudin et al., 2008), profile-likelihood maximization (Bickel & Chen, 2009), spectral clustering (Rohe et al., 2011; Jin, 2015), pseudo-likelihood maximization (Amini et al., 2013), and profile-pseudo likelihood methods (Wang et al., 2021). The corresponding asymptotic properties of estimation of community label have been obtained, see, e.g., Rohe et al. (2011); Zhao et al. (2012); Choi et al. (2012); Lei & Rinaldo (2015); Sarkar & Bickel (2015); Zhang & Zhou (2016); Wang et al. (2021).

In the past decades, the research interest of much literature focuses on the study of one sample of stochastic block models. Usually, in the social network, people surrounding a leader may tend to develop a closer relationship with another leader, see, e.g., Barnett & Onnela (2016). This phenomenon may lead to an issue, that is, whether the community structure (the number of communities $K$, the community probability matrix $B$, and the community membership label $g$) of the network will change over time or the environment.

As the simplest case of the multi-layer stochastic block model, two sample networks may also appear. For a multi-layer stochastic block model, it can be classified into a variety of more specific situations: First, all layer networks come from the identical stochastic block model $(g,B)$; second, each layer of the network comes from a different model but they have the same community structure, that is, $g$ is identical across all layers; third, each layer of the network comes from different models, that is, $g$ and $B$ are different in each layer. In fact, for the third case, it can be considered as a mixed model of multiple stochastic block models. However, how could we distinguish the three situations? Intuitively, we should judge whether two models are the same when we have two samples from the corresponding models. A common inference method to judge whether two models are the same is the hypothesis testing method. Tang et al. (2017) considered whether two independent finite-dimensional random dot product graphs are generated by the identical model. Using the adjacency spectral embedding for each sample, they constructed a statistic based on the kernel function. Ghoshdastidar & von Luxburg (2018) used the largest singular value of a scaled and centralized matrix to construct the statistic and proved that the null distribution convergences in distribution to a Tracy-Widom distribution. Ghoshdastidar et al. (2020) proposed two test statistics using the Frobenius norm and spectral norm to test whether two samples of networks are generated from the identical edge-probability matrix. However, this testing procedure requires choosing an appropriate threshold. Recently, Chen et al. (2021a) simplified the statistics in Ghoshdastidar & von Luxburg (2018) and proposed a test procedure for a two-sample network test. Based on the random matrix theory, Chen et al. (2021b) used the trace of a constructed matrix to obtain the statistic and proved that the asymptotic null distribution is the standard normal distribution.

For the methods mentioned above, one defect is that either the edge-probability matrices of the two populations differ greatly or multiple samples are required. Hence, when we only have two samples, the methods mentioned above may not work well as there is less information. In addition, it is worth noting that when the community structure changes slightly, the edge-probability matrix may change less, especially when the network size is relatively large. The above methods of testing $H_{0}:P_{1}=P_{2}$ may not work well, where $P_{1}$ and $P_{2}$ are the edge-probability matrices of two network models. It implies that we cannot test the difference between the two models when the difference is tiny but the network size is very large. Thus, detecting the difference between two samples of stochastic block models is an interesting research problem. Under the two-sample test of the stochastic block model, Wu et al. (2022) proposed a test method based on the locally smoothed adjacency matrix. To construct the smoothed adjacency matrix, their method separates a community into serval non-overlapping neighboring sub-communities and averages the entries of the adjacency matrix in non-overlapping local neighborhoods within communities. However, the procedure is complex and only applicable to a small number of communities. In this article, we want to construct a statistic that allows $K$ to diverge with $n$.

In this article, based on the maximum entry-wise deviation of the two centered and rescaled adjacency matrices, we propose a two-sample test statistic to detect the change of two stochastic block models under two observed adjacency matrices. We show that the asymptotic null distribution of the test statistic is a Gumbel distribution when $K=o(n/\log^{2}n)$. This testing method allows $K$ to grow linearly with $n$ up to a logarithmic factor. It is well known that the number of communities must be less than the number of nodes in the stochastic block model. Since $K$ cannot grow faster, Rohe et al. (2014) called this scenario ($K\rightarrow\infty$) the highest dimensional stochastic block model. Compared with the method in Wu et al.(2022), we relax the condition that the number of communities $K$ is fixed. Moreover, we also show that the proposed test is asymptotically powerful against serval alternative models, and does not need additional methods to improve the power of the proposed test. Finally, to improve the flexibility of the proposed method, we extend the proposed method to the degree-corrected stochastic block model.

Next, we formally describe this issue. Let $\mathcal{X}=(X_{ij})_{n\times n}$ and $\mathcal{Y}=(Y_{ij})_{n\times n}$ be two binary symmetric adjacency matrices from two stochastic block models parametrized by $(g_{x},B_{x})$ and $(g_{y},B_{y})$, respectively. For any $i$, let $X_{ii}=Y_{ii}=0$, i.e., no loop edge exists. In this article, we assume that the node label of the two networks is identical, instead of the community label of the node. Hence, the two networks $\mathcal{X}$ and $\mathcal{Y}$ can be viewed as repeated observations in the same individuals. Then, given two sample networks $\mathcal{X}$ and $\mathcal{Y}$, the testing problem can be formulated as

Intuitively, there are four mutually exclusive scenarios for the alternative hypothesis: (i) $K_{x}\neq K_{y}$, (ii) $K_{x}=K_{y},g_{x}=g_{y}$, but $B_{x}\neq B_{y}$, (iii) $K_{x}=K_{y},B_{x}=B_{y}$, but $g_{x}\neq g_{y}$, and (iv) $K_{x}=K_{y},g_{x}\neq g_{y},B_{x}\neq B_{y}$.

Our testing procedure for (1) goes as follows. First, we get consistent estimators of $K_{x}$ and $K_{y}$, denoted by $\widehat{K}_{x}$ and $\widehat{K}_{y}$, respectively. If $\widehat{K}_{x}\neq\widehat{K}_{y}$, it means that $(g_{x},B_{x})=(g_{y},B_{y})$ cannot be true, so we can directly reject the null hypothesis. If $\widehat{K}_{x}=\widehat{K}_{y}$, based on $\widehat{K}_{x}=\widehat{K}_{y}=\widehat{K}$, we obtain the strongly consistent estimators $\widehat{g}_{x}$ and $\widehat{g}_{y}$ for the community membership labels $g_{x}$ and $g_{y}$. Second, we estimate the entries of $B_{x}$ and $B_{y}$ by the sample proportions of each community based on $(\mathcal{X},\widehat{g}_{x})$ and $(\mathcal{Y},\widehat{g}_{y})$. Third, we use $\widehat{B}_{y}$ ($\widehat{B}_{x}$) to center and rescale adjacency matrix $\mathcal{X}$ ($\mathcal{Y}$), and sum for new matrix under specific rules, and get a combined information matrix, see (7). Finally, we obtain the test statistic by the maximum of the elements of the combined information matrix. The basic principle of this method is that if the null hypothesis is true, the entries of the combined information matrix asymptotically follow the normal distribution. According to the results of Zhou (2007), the asymptotic distribution of the maximum of elements after normalization is a Gumbel distribution. On the other hand, under the alternative hypothesis, the adjacency is incorrectly centered and scaled, and this deviation is magnified to a very large value by the normalization term. This implies that the test statistic can successfully separate $H_{0}$ and $H_{1}$ in (1).

The remainder of the article is organized as follows. In Section 2, we introduce the new test statistic and state its asymptotic null distribution and asymptotic power. In Section 3, we extend the proposed method to the degree-corrected stochastic block model. Simulation studies and real-world data examples are given in Sections 4 and 5, respectively. All technical proofs are postponed to the Appendix.

Consider a stochastic block model on $n$ nodes with the community label $g$ and probability matrix $B$. Given a number of communities $K$ and a community label $g$, the maximum likelihood estimator of $B$ is given by

where $\mathcal{N}_{u}=\left\{i:g(i)=u\right\}$ for $1\leq u\leq K$, $i\in\{1,\ldots,n\}$ stands for the label of a node, and $n_{u}=\left|\mathcal{N}_{u}\right|$. After here, $\mathcal{N}_{u}^{x}=\left\{i:g_{x}(i)=u\right\}$ and $n_{u}^{x}=\left|\mathcal{N}^{x}_{u}\right|$, where $x$ can be replaced by $y$.

For an adjacency matrix $A$, Hu et al. (2021) used a test statistic, based on the maximum entry-wise deviation, to test the following two hypothesis tests:

(1) $H_{0}:K=K_{0}\quad\mathrm{v.s.}\quad H_{1}:K>K_{0}$, and

(2) $H_{0}:g=g_{0}\quad\mathrm{v.s.}\quad H_{1}:g\neq g_{0}$,

In this article, We aim to develop a new test statistic that allows it can be used to test two samples. For two samples $\mathcal{X}$ and $\mathcal{Y}$ from stochastic block models $(g_{x},B_{x})$ and $(g_{y},B_{y})$, respectively, let $\widehat{K}_{x}$ and $\widehat{K}_{y}$ be obtained by some estimation methods, such as the recursive approach in Zhao et al. (2011), the sequential testing method given in Lei (2016), the likelihood-based method in Saldña et al. (2017), the corrected Bayesian information criterion in Hu et al. (2020), the test based on maximum entry-wise deviation in Hu et al. (2021), and the spectral methods in Le & Levina (2022). In this article, we use the corrected Bayesian information criterion in Hu et al. (2020) to get consistent estimators $\widehat{K}_{x}$ and $\widehat{K}_{y}$. Recall that given the number of communities $K_{x}$ and $K_{y}$, the community labels $g_{x}$ and $g_{y}$ can be consistently estimated, denote by $\widehat{g}_{x}$ and $\widehat{g}_{y}$, by some existing strongly consistent community detection procedures, e.g., the majority voting algorithm in Gao et al. (2017) and the profile-pseudo likelihood method in Wang et al. (2021). In view of this, throughout the paper, we formally assume that

which implies that we require that all estimators are strongly consistent. Hence, we can get the $\widehat{B}_{x}$ and $\widehat{B}_{y}$ by equation (2). Note that the community membership label $\widehat{g}_{x}$ and the probability matrix $\widehat{B}_{x}$ depend on the number of communities $\widehat{K}_{x}$. If $\widehat{g}_{x}$ is a strongly consistent estimator, $\widehat{K}_{x}$ must be the consistent estimator. Then, Condition (3) can be relaxed to $\mathbb{P}\left\{\widehat{g}_{x}=g_{x},\widehat{g}_{y}=g_{y}\right\}\rightarrow 1$. In fact, if $\widehat{K}_{x}\neq\widehat{K}_{y}$, then it is natural that $\widehat{g}_{x}\neq\widehat{g}_{y}$ and $\widehat{B}_{x}\neq\widehat{B}_{y}$. Since $\widehat{g}_{x}$ and $\widehat{g}_{y}$ are consistent estimators, we can reject the null hypothesis with probability tending to 1. Meanwhile, For case (iv), there is indeed a problem of identifiability. Because both $g$ and $B$ are allowed to vary, the existing methods cannot reasonably solve the problem of identifiability. Thus, in this article, we mainly focus on cases (ii) and (iii) for four alternative hypotheses. Then, we assume $K_{x}=K_{y}=K$. Without loss of generality, we write $\widehat{K}=\widehat{K}_{x}=\widehat{K}_{y}$ when $\widehat{K}_{x}=\widehat{K}_{y}$. Next, we formally state the test statistic. As mentioned in the introduction, our test statistic is motivated by the contrast of $\mathcal{X}$ (or $\mathcal{Y}$) and $\widehat{B}_{y}$ (or $\widehat{B}_{x}$), i.e.:

Moreover, based on the maximum entry-wise deviation, the proposed test statistic has the following form:

In this section, we extend the proposed method to the degree-corrected stochastic block model. In reality, a network may contain many high-degree nodes and lower-degree nodes, that is, the degree heterogeneity of nodes. To address this issue, Karrer & Newman (2011) proposed a degree-corrected stochastic block model. Specifically, for an undirected network $\mathcal{X}$, this model assume that the edge $X_{ij}$ satisfies $\mathbb{P}\{X_{ij}=1\}=\theta_{i}\theta_{j}B_{g(i)g(j)}$, where $\theta_{i}$ is the degree parameter for node $i$. To ensure the identifiability of the model, we assume that $\sum_{i}\theta_{i}/n=1$. For two sample networks $\mathcal{X}$ and $\mathcal{Y}$, the testing problem has the following form:

where $\theta_{x}$ and $\theta_{y}$ are the node degree parameters for networks $\mathcal{X}$ and $\mathcal{Y}$, respectively.

Similar to the general stochastic block model, for the two-sample test of the degree-corrected stochastic block model, we consider the following test statistic:

where

where $\widehat{\theta}^{x}_{i}=|g_{x}^{-1}(u)|d_{i}/\sum_{j\in\{j:g_{x}(j)=g_{x}(i)\}}d_{j}$ is the maximum likelihood estimator of $\theta^{x}_{i}$ and $d_{i}=\sum_{j}X_{ij}$. $\widehat{\theta}^{y}_{i}$ is similar to that of $\widehat{\theta}^{x}$. Note that it is difficult to obtain the asymptotic null distribution of $L_{D}(g_{x},g_{y})$ as the complex dependency between the entries $\tau_{iv}$. By the simulation studies, we find that the empirical distribution of $T_{D}=L_{D}^{2}(\widehat{g}_{x},\widehat{g}_{y})-2\log(2\widehat{K}n)+\log\log(2\widehat{K}n)$ is also the Gumbel distribution with $\mu=-2\log(2\sqrt{\pi})$ and $\beta=2$. Then, we have a rejection rule:

where $Q_{1-\alpha}$ is the $\alpha$th quantile of the Gumbel distribution with $\mu=-2\log(2\sqrt{\pi})$ and $\beta=2$. Similar to the general stochastic block model, we can obtain the bootstrap corrected statistic through the identical method.

In this section, we evaluate the performance of the proposed test statistics in various simulation studies. Firstly, the number of communities is estimated by the Bayesian information criterion proposed by Hu et al. (2020), and the community membership label is estimated by strongly consistent estimation methods mentioned above, i.e., the profile-pseudo likelihood method in Wang et al. (2022), initialized by spectral clustering with permutations, is used to obtain the community membership label. In the simulation, we consider the test statistic $T_{n}=L_{n}^{2}(\widehat{g}_{x},\widehat{g}_{y})-2\log(2\widehat{K}n)+\log\log(2\widehat{K}n)$ and the bootstrap corrected test statistic $T_{n}^{boot}$. In comparative experiments, the maximum deviation method (referred to as TST-MD) proposed by Chen et al. (2021a) and the spectral-based method (referred to as TST-S) proposed by Chen et al. (2021b) are used.