2 Noisy stochastic block model
2.1 The model
The noisy stochastic block model (NSBM) is a random graph model suited for the problem of graph inference. In this model, we assume that the observed matrix is a perturbation of an unobserved binary graph, which is the true graph to be inferred. The binary graph is chosen to be a stochastic block model (SBM) for its capacity to model graph heterogeneity.
The definition is stated for an undirected graph without self-loops, but extensions are straightforward. We also consider only the Gaussian NSBM but this model can be extended to any parametric model.
Let \(p\geq 2\) be the number of nodes and \(\mathcal{A}=\{(i,j): 1\leq i <j\leq p\}\) the set of all possible pairs of nodes. Denote \(Q\) the number of latent node blocks. In the NSBM, we denote \(X=(X_{i,j})_{1\leq i,j\leq p}\in\mathbb R^{p^2}\) the symmetric, real-valued observation matrix. The observations \(X_{i,j}, (i,j)\in\mathcal{A}\), are generated by the following random layers:
First, a vector \(Z=(Z_1,\dots,Z_p)\) of block memberships of the nodes is generated, such that \(Z_i\), \(1\leq i\leq p\), are independent with common distribution given by the probabilities \(\pi_q=\mathbb P(Z_1=q), q\in\{1,\dots,Q\},\) for some parameter \(\pi=(\pi_q)_{q\in\{1,\dots,Q\}}\in (0,1)^Q\) such that \(\sum_{q=1}^Q \pi_q=1\).
Conditionally on \(Z\), the variables \(A_{i,j}\), \((i,j)\in\mathcal A\), are independent Bernoulli variables with parameter \(w_{Z_i,Z_j}\), for some symmetric matrix \(w=(w_{kl})_{k,l\in\{1,\dots,Q\}}\in (0,1)^{Q^2}\). We denote \(A=(A_{i,j})_{1\leq i,j\leq p}\) the symmetric adjacency matrix, which is a standard binary SBM.
Conditionally on \((Z,A)\), the observations \(X_{i,j}\), \((i,j)\in\mathcal A\) are independent and \(X_{i,j}\) is sampled from the distribution \[X_{i,j} \sim (1-A_{i,j}) \mathcal N(0,\sigma_0^2) + A_{i,j} \mathcal N(\mu_{Z_i,Z_j},\sigma_{Z_i,Z_j}^2)\] for some parameters \(\mu=(\mu_{kl})_{k,l\in\{1,\dots,Q\}}\in \mathbb R^{Q^2}\) such that \(\mu_{kl}=\mu_{lk}\), \(\sigma=(\sigma_{kl})_{k,l\in\{1,\dots,Q\}}\in (\mathbb R_+^*)^{Q^2}\) such that \(\sigma_{kl}=\sigma_{lk}\) and \(\sigma_0\in \mathbb R\). We suppose that \(\sigma_0\) is known (often equal to \(\sigma_0=1\)).
The relation between \(A\) and the observation \(X\) is that missing edges (\(A_{i,j}=0\)) are replaced with pure random noise modeled by the density \(\mathcal N(0,\sigma_0^2)\), also called the null density, whereas in place of present edges (\(A_{i,j}=1\)) there is a signal or effect. The intensity of the signal depends on the block membership of the interacting nodes in the underlying SBM, modeled by the density \(N(\mu_{kl},\sigma_{kl}^2)\), also called alternative density.
The Gaussian NSBM is particularly suitable for modeling situations where the observations \(X_{i,j}\) correspond to test statistics which are known to be approximately Gaussian. We often assume that the variance of the null distribution is known, equal to \(\sigma_0=1\).
For the alternative distribution, we often consider two cases. First, the case where all \(\sigma_{kl}\) are equal to a single known parameter \(\sigma_1\). It is for instance the case when \(X_{i,j}\) correspond to test statistics which are known to be approximately Gaussian with variance asymptotically equal to 1. As this is not always the case, we secondly consider the case where the \(\sigma_{kl}\) are unknown, potentially different from each other, and have to be estimated.
We denote \(\nu_0=(0, \sigma_0)\) the null parameter (that we suppose known) and \(\nu=(\nu_{kl})_{1\leq k, l\leq Q}=(\mu_{kl}, \sigma_{kl})_{1\leq k, l\leq Q}\) the parameters of the effects (with the two mentioned above cases depending on whether the alternative variance is supposed to be known or not). The global model parameter is \(\theta=(\pi,w,\nu_0, \nu)\), where \(\pi\) and \(w\) come from the SBM.
2.2 Data generation of the NSBM
The global parameter \(\theta\) is a
list and its elements are pi, w,
nu0 and nu.
2.2.1 SBM parameters
Denote Q the number of latent blocks in the SBM. Say
The parameters pi and w are the parameters
of the latent binary SBM.
The parameter pi is a Q-vector indicating
the mean proportions of nodes per block. The vector pi has
to be normalized:
The parameter w represents the symmetric matrix \(w=(w_{kl})_{k,l\in\{1,\dots,Q\}}\) such
that \(w_{kl}\in(0,1)\) is a Bernoulli
parameter indicating the probability that there is an edge between a
node in group \(k\) and a node in group
\(l\). The machine representation of
w is a vector of length \(\frac{Q(Q+1)}{2}\) containing the
coefficients of the upper triangle of the matrix from left to right and
from top to bottom. For our graph with two latent blocks, let us
consider
This means that the two blocks are communities as nodes have a large probability to be connected to nodes in the same block ( \(w_{11}=0.8\) and \(w_{22}=0.9\)), and a low probability to connect to nodes in the other group (\(w_{12}=w_{21}=0.1\)).
2.2.2 Gaussian parameters
In the Gaussian model, the null parameter nu0 is a
vector of length 2, giving the mean and the standard deviation of the
Gaussian null distrubtion (\(\nu_0=(0,\sigma_{0})\)). Mostly, we choose
the standard normal distribution:
The parameter nu is a matrix of dimensions \((\frac{Q(Q+1)}{2},2)\) : the first column
indicates the Gaussian means \(\mu_{kl}\) and the second column the
standard deviations \(\sigma_{kl}\) of
the alternative distributions for each block pairs \((k,l)\) (corresponding to the coefficients
of the upper triangle of respectively the matrices \(\mu\) and $ from left to right and from top
to bottom).
For our model with two latent blocks, we choose
theta$nu <- array(0, dim = c(Q*(Q+1)/2, 2))
theta$nu[,1] <- c(4,4,4)
theta$nu[,2]<-c(1,1,1)
theta$nu## [,1] [,2]
## [1,] 4 1
## [2,] 4 1
## [3,] 4 12.2.3 Generate data
To generate a data set with, say, \(p=10\) nodes from the corresponding NSBM we
use the function rnsbm():
The function rnsbm() provides the data generated matrix,
which is symmetric.
## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,] 0.00 0.74 0.47 0.28 3.68 0.76 5.90 3.00 -0.13 4.04
## [2,] 0.74 0.00 4.78 1.22 0.16 4.39 -1.21 -0.10 4.69 0.90
## [3,] 0.47 4.78 0.00 -0.50 2.00 3.71 -0.83 0.78 3.48 -0.48
## [4,] 0.28 1.22 -0.50 0.00 5.92 -0.62 3.68 4.28 -0.28 3.74
## [5,] 3.68 0.16 2.00 5.92 0.00 3.40 3.48 4.79 0.71 2.85
## [6,] 0.76 4.39 3.71 -0.62 3.40 0.00 -1.28 -1.66 0.52 5.64
## [7,] 5.90 -1.21 -0.83 3.68 3.48 -1.28 0.00 4.66 0.77 4.97
## [8,] 3.00 -0.10 0.78 4.28 4.79 -1.66 4.66 0.00 3.39 4.47
## [9,] -0.13 4.69 3.48 -0.28 0.71 0.52 0.77 3.39 0.00 2.21
## [10,] 4.04 0.90 -0.48 3.74 2.85 5.64 4.97 4.47 2.21 0.00The function rnsbm() also provides the latent binary
graph, named latentAdj, which is also symmetric:
## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,] 0 0 0 0 1 0 1 1 0 1
## [2,] 0 0 1 0 0 1 0 0 1 0
## [3,] 0 1 0 0 0 1 0 0 1 0
## [4,] 0 0 0 0 1 0 1 1 0 1
## [5,] 1 0 0 1 0 1 1 1 0 1
## [6,] 0 1 1 0 1 0 0 0 0 1
## [7,] 1 0 0 1 1 0 0 1 0 1
## [8,] 1 0 0 1 1 0 1 0 1 1
## [9,] 0 1 1 0 0 0 0 1 0 0
## [10,] 1 0 0 1 1 1 1 1 0 0as well as the latent blocks, named latentZ:
## [1] 1 2 2 1 1 2 1 1 2 1A more convenient visualization of the graph and the clustering is
given by the function plot.igraph() from the package
igraph:
##
## Attaching package: 'igraph'## The following objects are masked from 'package:stats':
##
## decompose, spectrum## The following object is masked from 'package:base':
##
## unionG=igraph::graph_from_adjacency_matrix(obs$latentAdj)
igraph::plot.igraph(G, vertex.size=5, vertex.dist=4, vertex.label=NA, vertex.color=obs$latentZ, edge.arrow.mode=0) 
and a more convenient visualization of the data is given by the
function plotGraphs():
## NULL
