Estimating Stochastic Block Models in the Presence of Covariates

Estimating Stochastic Block Models in the Presence of Covariates

\address{Cowles Foundation for Research in Economics, Yale University, New Haven, CT 06520.} \email{[email removed]} \address{Department of Economics, Georgetown University, Washington, D.C., 20007.} \email{[email removed]}

Introduction

The Stochastic Block Model (SBM) is a powerful yet convenient framework for network data analysis, by postulating that each node in a network belongs to a community, in the presence of a finite number of communities. The community assignments are unobserved to the researcher. A SBM is highly effective in applications where community membership can be regarded as a discretized version of unobserved heterogeneity. The standard SBM has been applied widely in diverse areas, where an algorithm based on spectral clustering is often used. Statistical properties of these methodologies have been investigated intensively in the recent literature; see, \citeasnoun{lei2015consistency}, \citeasnoun{joseph2016impact} and \citeasnoun{rohe2016co}, just to name a few.

As an alternative approach, one can employ a model with more specific structures for the edge probability functions, while incorporating (possibly continuous-valued) unobserved heterogeneity through node-specific fixed effects. An advantage of such an approach is its ease of incorporating observed covariates into the model. If one is willing to accept a specific form of the edge probability function, e.g. scalar valued fixed effects representing unobserved heterogeneity, and the estimation algorithm is computationally feasible, then such a method is practical and intuitive to use, and by having covariates in the model, it can shed valuable insights on, for example, the magnitude of homophily (or heterophily) effects in terms of observed characteristics in a given network.

The main goal of our paper is to develop a procedure that incorporates both unobserved heterogeneity (through unobserved community assignments) and observed heterogeneity (through covariates) building on the SBM framework. More specifically, our version of SBM lets each edge probability, together with the probability of community assignment, be impacted by observed covariates in a flexible manner. That is, we postulate that the edge probabilities and the community assignment probabilities are nonparametric function of covariates. Unobserved community assignment enters the model in a fully unrestricted way, since it simply indexes (or used as a label for) the edge probability and the community assignment probability. We note that letting the community assignment probability depend on covariates nonparametrically is an important feature of our model. It means that the observed covariates (or observed heterogeneity) and the unobserved heterogeneity can be correlated in an unspecified way, a feature often considered to be highly desirable in econometrics. Of course, this generality comes at the cost of additional technical complications, a part of the many theoretical challenges presented by our model, as is discussed shortly.

We propose a computationally tractable two-step procedure to estimate the conditional edge probabilities as well as the community assignment probabilities. The first step relies on a spectral clustering algorithm applied to a localized adjacency matrix of the network. We build on the $k$-nearest neighbor ($k$-nn) algorithm in our localization procedure, followed by the Singular Value Decomposition (SDV) to compute left/right singular vectors of the localized adjacency matrix, or, more precisely, a localized and normalized version of the Laplacian. Note that we need to employ SVD, as opposed to the eigen-value decomposition often used for the standard spectral clustering, even though we consider undirected network. This is because our localized and normalized network Laplacian depends on the covariate values at each of the two nodes, resulting its asymmetry. We then apply $K$-means clustering to extract communities, as in the standard spectral clustering algorithm, though it is implemented at each covariate value. As in the literature of the standard SBM without covariates, we provide non-asymptotic bounds for misclassificaiton error. Since we allow for correlation of unknown form between the community assignment and the covariates, it naturally induces independent but non-identically distributed (i.n.i.d) covariates when conditioned on community assignments, even though we assume random sampling for community assignments and observed covariates. We thus obtain some non-asymptotic results for the $k$-nn estimator under an i.n.i.d sampling; those can be of independent theoretical interest.

In the second step, once again we employ the $k$-nn regression algorithm, but this time in order to estimate the edge probability matrix and the community assignment probability vector. We apply the $k$-nn estimator to the extracted communities obtained from the first step. We study the statistical properties of these estimators while taking account of the effects of classification error in the first step, by obtaining non-asymptotic bounds for them.

Notation.

\

For a matrix $M$, $\|M\|$ denotes its spectral norm, $\|M\|_F$ its Frobenius norm, $\|M\|_{\max}$ its max norm. $\mathcal{B}(x,r) \subset \mathbb{R}^{d}$ is the closed ball of center $x$ and radius $r$, $\lambda$ is the Lebesgue measure on $\mathbb{R}^d$, $V_d = \int_{\mathcal{B}(0,1)}\text{d}\lambda$ and $I_k$ is the identity matrix of size $k$.

Model and Estimator

Stochastic Block Model with Covariates

\

We consider a network of $N$ nodes such that each node $i$ has a $d$-vector of covariates $x(i)$ and belongs to a community $g(i) \in [G]$ where $G \in \mathbb{N}$. For each node $i$, the researcher observes $x(i)$ but does not observe the community $g(i)$. Let $\mathbb{M}_{N,G} \subset \mathbb{R}^{N \times G}$ the set of membership matrices, i.e., of matrices such that each row has exactly one nonzero coefficient set to $1$. Let $\theta_i \in \mathbb{R}^G$ be a vector such that $\theta_{i g(i)} = 1$ and all other coefficients are $0$. Then $\Theta := (\theta_1, ..., \theta_N)^{\top} \in \mathbb{M}_{N,G}$. The researcher also observes the adjacency matrix $A=\left(A_{ij}\right)_{1\leq i,j\leq N}$. Define ${\bf x} = \{x(i), i \in [N]\}$ and ${\bf g} = \{g(i), i \in [N]\}$. In our stochastic block model with covariates, the distribution of the adjacency matrix conditional on ${\bf x}$ and ${\bf g}$ is given by a matrix-valued function $B: (x,x') \mapsto B(x,x') \in \mathbb{R}^{G\times G}$: conditional on ${\bf x}$ and ${\bf g}$, the entries $A_{ij}$ are i.i.d Bernouilli random variables with $$ \Pr(A_{ij} =1 | {\bf x}, {\bf g}) = \Pr(A_{ij} =1 | x(i),x(j),g(i),g(j)) = B_{g(i)g(j)}(x(i),x(j)). $$ We note that the function $B$ may vary with $N$ and thus allows for sparsity. The distribution of $g(i)$ conditional on $x(i)$ is given by the functions $x \mapsto \pi_g(x) = \Pr(g(i)=g|x(i)=x)$, for $g\in[G]$. We assume that $(x(i),g(i))_{i \in [N]}$ are i.i.d random variables, and let $\mathcal S_X = \operatorname*{supp}(x(i))$. However we state some of our results as nonasymptotic bounds conditional on ${\bf g}$, in which case it is understood that we only assume that $(x(i))_{i \in [N]}$ are independent draws and the marginal distribution of each depend on $g(i)$ only.

Construction of the estimator

\

Our primary parameters of interest are $B(x,x')$ and $\pi(x) = (\pi_1(x),...,\pi_G(x))$ for some $(x,x') \in \mathcal{S}_X \times \mathcal{S}_X$. Our estimators of these quantities rely on a spectral clustering algorithm applied to a truncated adjacency matrix, following the intuition of $k$-nearest neighbor regression. Before describing the algorithm and our estimators, we introduce the following notations.

Let $k \in \mathbb{N}$. We define the $k$-nearest neighbor ($k$-NN) radius of $x$ as $r_k(x) := \inf \{ r>0 \, : \, |\mathcal{B}(x,r) \cap {\bold x} | = k \}$. The $k$-neighborhood of $x$ is $ \eta_N(x) := \{ i \in [N] \, : \, ||x(i) - x|| \leq r_k(x)\}. $ Let $\eta_N(x,x') := \{(x(i),x(j)): x(i) \in \eta_N(x) \text{ and } x(j) \in \eta_N(x') \}$. For ease of notation, we sometimes write $\eta(x)$. For these units, we define the adjacency matrix ${A^{\eta}} \in \mathbb{R}^{k \times k}$: it is a submatrix of the network adjacency matrix $A$ where rows index units in $\eta(x)$ and columns index units in $\eta(x')$. Similarly, $\Theta^{\eta}(x) \in \mathbb{M}_{k,G}$ is the membership matrix for the individuals in $\eta(x)$: it is a submatrix of $\Theta$ where rows index units in $\eta(x)$ and columns index communities. Note that we drop the dependence of ${A^{\eta}}$ in $x$ and $x'$ for ease of notation. Let $O^\eta \in \mathbb{R}^{k \times k}$ and $Q^\eta \in \mathbb{R}^{k \times k}$ be the diagonal matrices such that $O_{ii}^\eta := \sum_{j \in \eta_N(x')} A_{ij}^\eta$ and $Q_{jj}^\eta := \sum_{i \in \eta_N(x)} A_{ij}^\eta$. For $\tau > 0$, we also define $O_\tau^\eta := O^\eta + \tau I_{k}$ and $Q_\tau^\eta := Q^\eta + \tau I_{k'}$. Finally, by analogy with the regularized graph Laplacian in the symmetric case, let $$L_\tau^\eta : = {(O_\tau^\eta)}^{-\frac 1 2} A^\eta {(Q_\tau^\eta)}^{- \frac 1 2}. $$ Our estimation procedure first applies a spectral clustering algorithm to $L_\tau^\eta$ to estimate the communities of units in $\eta(x)$ and $\eta(x')$. This spectral clustering algorithm proceeds as follows.

Spectral Clustering Algorithm:

Once these communities are estimated, we estimate $B_{gh}(x,x')$ and $\pi_g(x)$ by running $k$-NN regressions on the appropriate communities. For $i \in \eta(x)$, let $\hat{g}(i)$ be the estimated community, i.e., such that $\left(\widehat{\Theta}^\eta(x)\right)_{i, \hat{g}(i)} = 1$ and $\left(\widehat{\Theta}^\eta(x)\right)_{i,g} = 0$ for any $g \neq \hat{g}(i)$. Estimated communities of units in $\eta(x')$ are similarly defined. Let $\mathcal{G}_{h N}(x) = \{g(i) = h, i \in \eta_N(x)\}$ and $n_h(x) = |\mathcal{G}_{h N}(x)|$. Our estimator for $n_h(x)$ is $\hat{n}_h(x) := \# \{i \in \eta(x) \, : \, \hat{g}(i) = h \}$. We can finally introduce our estimators of the connection probabilities and community probabilities. The estimator of $\pi_h(x)$ is

The estimator of $B_{gh}(x,x')$ is

Assumptions

\

We will maintain the following assumptions where $S$ is a subset of $\mathcal{S}_X$, the support of $x$.

We consider the case where the covariates are continuous. Define the density of $x(i)$ given $g(i)=g$ as $f(.|g)$, for $g \in [G]$. Define also $\underline{f}(x) := \min_{g \in [G]} \ f(x|g) $.

Similarly, define $ \overline{f}(x) := \max_{g \in [G]} \ f(x|g). $

Some smoothness assumptions will be imposed to study our estimators.

Note that $l_B$ may depend on $N$ and thus captures sparsity.

Clustering

We fix a pair $(x,x') \in S^2$. The main result of this section is a high probability finite sample bound on a misclustering measure applied to $\widehat{\Theta}^\eta(x)$ and $\widehat{\Theta}^\eta(x')$. This result is obtained in 3 steps. We first obtain a finite sample bound on the difference between the graph Laplacian and its population counterpart. We then apply a version of Davis-Kahan theorem to bound the difference between $\hat{U}$, $\hat{V}$, and their population counterparts. Finally, we use theoretical properties of the $K$-means algorithm to bound the misclustering error.

Convergence of the graph Laplacian

\

To introduce the population counterpart of $L_\tau^\eta$, we define the following objects. Let $P({\bf x},{\bf g}) := {\mathbb E}[A|{\bf x},{\bf g}]$. Thus, $P_{ij}({\bf x},{\bf g}) = {\mathbb E}[A_{ij}|x(i),x(j),g(i),g(j)]$. Let also $P_{ij}(x,x',{\bf g}) = {\mathbb E}[A_{ij}|x(i) = x,x(j) = x',g(i),g(j)] $ and $P(x,x',{\bf g}) = \left(P_{ij}(x,x',{\bf g})\right)_{1\leq i,j \leq N}$. As in Section (ref), we also define the localized matrices $P^\eta({\bf x},{\bf g})$ and $P^\eta(x,x',{\bf g})$ as submatrices of the matrices $P({\bf x},{\bf g})$ and $P(x,x',{\bf g})$ where rows index units in $\eta(x)$ and columns index units in $\eta(x')$. Let $\mathcal{O}^\eta({\bf x},{\bf g}) \in \mathbb{R}^{k \times k}$, $\mathcal{O}^\eta(x,x',{\bf g}) \in \mathbb{R}^{k \times k}$, $\mathcal{Q}^\eta({\bf x},{\bf g}) \in \mathbb{R}^{k \times k}$ and $\mathcal{Q}^\eta(x,x',{\bf g}) \in \mathbb{R}^{k \times k}$ be the diagonal matrices such that ${\mathcal O}_{ii}^\eta({\bf x},{\bf g}) := \sum_{j \in \eta_N(x') } {\mathbb E}[A_{ij}^\eta|{\bf x},{\bf g}]$, ${\mathcal O}_{ii}^\eta(x,x',{\bf g}) := \sum_{j \in \eta_N(x') } P_{ij}(x,x',{\bf g})$, ${\mathcal Q}_{jj}^\eta({\bf x},{\bf g}) := \sum_{i \in \eta_N(x)} {\mathbb E}[A_{ij}^\eta|{\bf x},{\bf g}]$ and finally ${\mathcal Q}_{jj}^\eta(x,x',{\bf g}) := \sum_{i \in \eta_N(x)} P_{ij}(x,x',{\bf g})$. Define also $\mathcal{O}_\tau^\eta({\bf x},{\bf g}) := \mathcal{O}^\eta({\bf x},{\bf g})+ \tau I_{k}$, $\mathcal{O}_\tau^\eta(x,x',{\bf g}) := \mathcal{O}^\eta(x,x',{\bf g})+ \tau I_{k}$, $\mathcal{Q}_\tau^\eta({\bf x},{\bf g}) := \mathcal{Q}^\eta({\bf x},{\bf g})+ \tau I_{k}$ and $\mathcal{Q}_\tau^\eta(x,x',{\bf g}) := \mathcal{Q}^\eta(x,x',{\bf g})+ \tau I_{k}$. Finally, let

To obtain a finite sample bound, we will rely on concentration inequalities for symmetric matrices. However, $P^\eta(x,x',{\bf g}) $ and $A^\eta$ are not symmetric in general. Following \citeasnoun{rohe2016co}, we first focus on their Hermitian dilations, where the Hermitian dilation of a matrix $M$, denoted $\widetilde{M}$, is given by $$ \widetilde{M} =

. $$ Define the minimum degree $$d_{\min}(x,x', {\bold x}) := \min \left(\min_{i \in \eta_N(x)} {\mathcal O}_{ii}(x,x',{\bf g}), \min_{j \in \eta_N(x')} {\mathcal Q}_{jj}(x,x',{\bf g}),\min_{i \in \eta_N(x)} {\mathcal O}_{ii}({\bf x},{\bf g}), \min_{j \in \eta_N(x')} {\mathcal Q}_{jj}({\bf x},{\bf g})\right).$$ In most of the computations, we drop the dependence in $(x,x', {\bold x})$. Define

Note that this finite sample bound holds conditionally on $({\bold g},{\bold x})$. It cannot be integrated directly because Conditions ((ref)) and ((ref)) are restrictions on $\bold x$. We show in Lemma (ref) that under certain assumptions, $\sup_{x \in S} r_k(x) \leq R_k$ holds with high probability and we derive in Lemma (ref) a high probability bound for $d_{\min}$. Lemma (ref) obtains a high probability bound on $\|\widetilde{L_\tau^\eta} - \widetilde{{\mathcal L}_\tau^\eta}(x,x',{\bf g}) \|$ which will hold conditional on $\bold g$ only.

Lower bound on $d_{\min}(x,x', {\bold x})$

\

The finite sample bound obtained in Lemma (ref) is valid under restrictions on $d_{\min}(x,x', {\bold x})$, a localized minimum expected degree. In this section, we derive a nonasymptotic probability bound on $d_{\min}(x,x', {\bold x})$ and combine it with Lemmas (ref) and (ref) to obtain a finite sample bound on $ \|\widetilde{L_\tau^\eta} - \widetilde{{\mathcal L}_\tau^\eta}(x,x',{\bf g}) \| $ conditional on ${\bf g}$ only and with explicit dependence in $k$. For $h \in [G]$, let

Define $$ \Delta = \inf_{(x,x') \in S^{2}} \min_{g \in [G]} \max_{h \in [G]} B_{gh}(x,x') $$ Note that as for $B$ and $l_B$, $\Delta$ may vary with $N$ and thus captures sparsity. We assume that $\Delta >0$. A natural lower bound on $d_{\min}(x,x', {\bold x})$ therefore involves $\min_{h \in [G]} \underline{n_h}$. We show in Lemma (ref) that under certain assumptions, $\inf_{x \in S} r_k(x) \geq \underline{R}_k$ holds with high probability, where

The following lemma uses this result and establishes a lower bound on $\min_{h \in [G]} \underline{n_h}$.

Combining Lemma (ref) together with Lemma (ref), we obtain a new bound on $\|\widetilde{L^\eta} - \widetilde{{\mathcal L}^\eta}(x,x',{\bf g}) \|$.

Clustering

\

In this section, for ease of readability, we do not display dependence of many of the defined objects in $x,x',\tau, k$, etc. Using the Laplacian ${L_\tau^\eta}$ we compute its top $G$ left/right singular vectors, to obtain the SVD of ${L_\tau^\eta}$ $$ {L_\tau^\eta} = U \widehat \Lambda V^\top $$ where $U, V \in {\mathbb R^{k \times G}}$. We then apply $K$-means clustering to $U$ and $V$, solving

It is possible to use a faster clustering algorithm by using an approximate solution instead, incorporating the approximation error explicitly in the following analysis as in \citeasnoun{lei2015consistency}.

Note that the $i$-th element of the diagonal matrix ${\mathcal O}_\tau^\eta(x,x',{\bf g})$ only depends on $g(i)$. Define the diagonal matrix $\overline{{\mathcal O}} \in \mathbb{R}^{G \times G}$ collecting these coefficients, i.e., such that $\overline{{\mathcal O}}_{gg} = \sum_{j \in \eta_N(x')} B_{gg(j)}(x,x') + \tau$. Similarly, define the diagonal matrix $\overline{{\mathcal Q}} \in \mathbb{R}^{G \times G}$ such that $\overline{{\mathcal Q}}_{gg} = \sum_{i \in \eta_N(x)} B_{g(i)g}(x,x') + \tau$.

Define $\mathcal{N}(x) = {\mathrm{diag}}\left({\sqrt{n_1(x)}},...,{\sqrt{n_G(x)}}\right)$ and let

be the SVD of $B(x,x')$ after normalization by $\mathcal{N}(x) \overline{{\mathcal O}}^{-1/2}$ and $\mathcal{N}(x') \overline{{\mathcal Q}}^{-1/2}$. Note that

with $({\mathcal O}_\tau^\eta(x,x',{\bf g}))^{-\frac 1 2} \Theta^\eta(x) = \Theta^\eta(x) \overline{{\mathcal O}}^{-1/2}$ and $({\mathcal Q}_\tau^\eta(x,x',{\bf g}))^{-\frac 1 2} \Theta^\eta(x') = \Theta^\eta(x') \overline{{\mathcal Q}}^{-1/2}$. Thus

From this expression, by slight modification of the argument in the proof of Lemma 2.1 in \citeasnoun{lei2015consistency}, considering SVD instead of eigenvalue decomposition, and taking account of the normalization of the Laplacian, we see that the SVD of ${{\mathcal L}^\eta}(x,x',{\bf g})$ is given by $$ {{\mathcal L}^\eta}(x,x',{\bf g}) = {\mathcal U} \Lambda_\tau {\mathcal V^\top} $$ with $\mathcal U = \Theta^\eta(x) \mathcal Z_U$ and $\mathcal V = \Theta^\eta(x') \mathcal Z_V$ where $\mathcal Z_U = \mathcal{N}(x)^{-1} z_U$ and $\mathcal Z_V = \mathcal{N}(x)^{-1} z_V$.

Note

As in \citeasnoun{rohe2016co}, define $$ \tilde {\mathcal U}: = \frac{1}{\sqrt 2}\binom{\mathcal U}{\mathcal V}, $$ $$ \tilde {U}: = \frac{1}{\sqrt 2}\binom{U}{V}, $$ then $\tilde {\mathcal U}$ and $\tilde {U}$ are the eigenvectors corresponding to top $G$ eigenvalues of $\widetilde{\mathcal L^\eta}$ and $\widetilde{L^\eta}$, respectively. We will use $\lambda_1(x,x') \geq \lambda_2(x,x') \geq ... \geq \lambda_G(x,x')$ and $\hat \lambda_1(x,x') \geq \hat \lambda_2(x,x') \geq ... \geq \hat \lambda_G(x,x')$ to denote them although we drop $(x,x')$ in most of our computations. We now have

We now bound misclassification rates. Let $$ \bar U = \widehat{\Theta}^\eta(x)Z_U,\quad \bar V = \widehat{\Theta}^\eta(x')Z_V, $$ then

and likewise $$ \|\bar V - \mathcal VQ_V\|_F^2 \leq 4\|V - \mathcal V Q_V\|_F^2. $$ Define $$ \mathcal Z_U' = \mathcal Z_U Q_U, \quad \mathcal Z_V' = \mathcal Z_V Q_V, $$ Note that for $g \in [G]$, by (ref)

Moreover, let $$ \mathcal S_{gN}(x) := \left \{i \in \mathcal G_{gN}(x): \|\bar U_{i \cdot} - (\mathcal UQ_U)_{i \cdot}\| \geq \frac 1 2 \sqrt{\frac{1}{n_g(x)} + \frac{1}{\max\{n_\ell(x): \ell \neq g\}}}\right \}. $$ Then

Therefore we have

By Lemma (ref) it follows that

The same holds with $ \frac{|\mathcal S_{hN}(x')|}{n_h(x')}$. Moreover, one can show that following the proof of Lemma 5.3 of \citeasnoun{lei2015consistency}, the definition of $S_{gN}(x)$, in view of (ref), guarantees that for each $g \in [G]$, under the condition

the estimated membership matrix $\widehat{\Theta}^\eta(x)$ assigns the correct membership for every $i \in \mathcal G_{gN}(x) \setminus \mathcal S_{gN}(x)$. That is, for $\mathcal{G}_N(x) = \cup_{g\in [G]} (\mathcal G_{gN}(x) \setminus \mathcal S_{gN}(x))$, there exists a permutation matrix $J(x)$ such that $(\widehat{\Theta}\eta (x))_{\mathcal{G}_N(x) \cdot} J(x) = (\Theta^\eta(x))_{\mathcal{G}_N(x) \cdot} $ and the same holds for $x'$.

By (ref) and (ref), the singular values of ${{\mathcal L}^\eta}(x,x',{\bf g}) $ are that of $\mathcal{N}(x) \overline{{\mathcal O}}^{-1/2} B(x,x') \overline{{\mathcal Q}}^{-1/2} \mathcal{N}(x')$. Denote $\sigma_1(M) \geq ... \geq \sigma_r(M)$ the singular values of a matrix $M$ of rank $r$. We use Theorem 3.3.16 of \citeasnoun{horn1990matrix}, see also \citeasnoun{wang1997some}, and write

where we recall that the matrices $\mathcal{N}(x)$, $\overline{{\mathcal O}}$ and $\overline{{\mathcal Q}}$ are diagonal. Their singular values are equal to their diagonal coefficients, and

This implies that

We plug in (ref) and the bounds obtained on the relevant quantities in (ref). This condition becomes

We combine (ref) and (ref) to obtain a finite sample probability bound on $\sum_{g=1}^G |\mathcal S_{gN}(x)|/n_g(x)$ in the following Lemma.

\

Estimation of $B$ and $\pi$

As in the previous section, we fix a pair $(x,x') \in S^2$. Recall that $\mathcal{G}_{h N}(x) = \{g(i) = h, i \in \eta_N(x)\}$ and $n_h(x) = |\mathcal{G}_{h N}(x)|$. We introduce the following new notation,

Note that the estimators of $\pi_h(x)$ and $B_{gh}(x,x')$ can be written

Define the oracle estimators for $\pi_g(x)$ and $B_{gh}(x,x')$ as

In this section, we derive probability bounds on $\widehat{\pi}_h(x)$ and $\widehat{B}_{gh}(x,x')$. Note that according to Lemma (ref), with probability at least $1-\delta$ conditional on ${\bold g}$, the memberships of $i \in \left(\mathcal{G}_{g N}(x) \setminus \mathcal{S}_{gN}(x) \right)$ are all correctly estimated up to a permutation. Thus all the following probability bounds hold up to a permutation. We explore this identification issue this raises in Remark (ref).

Result conditional on $\bold g$

\

We can decompose

where by a slight abuse of notation the summations are over $i \in \eta_N(x)$ and $j \in \eta_N(x')$. We look at $T_1$ and $T_2$ separately.

When (ref) holds,

where the second inequality holds by the argument used in (ref). Similarly, when (ref) holds we obtain $$ T_{22} \leq \frac{1}{n_h(x')} \sum_{l \in [G]} |\mathcal{S}_{lN}(x')|. $$ Note that when (ref) holds,

where we used the same argument as in (ref) in the second inequality. We use similar arguments to bound $T_{21}$ and $T_{22}$ and obtain

We now bound $|B_{gh}^{or}(x,x') -B_{gh}(x,x')|$. The oracle estimator is not a standard $k$-nearest neighbor estimator with, say, $k=n_g(x)n_h(x')$, because $n_g(x)$ and $n_h(x')$ are not chosen by the statistician but random. Moreover, the neighborhood for $x$ is chosen separately from that of $x'$. It is also not a Nadaraya-Watson estimator with uniform kernel as $r_{n_g(x)}^g (x) $ and $r_{n_h(x')}^h (x') $ are random. Write $$A_{ij} = B_{g(i)g(j)}(x(i),x(j)) + \zeta_{ij},$$ then we can decompose

In this decomposition, $T_3$ is a bias term and $T_4$ is a variance term. As in the proof of Lemma (ref), the bias term can be bounded using Assumption (ref),

by $r_{n_g(x)}^g (x) \leq r_k(x)$ and $r_{n_h(x')}^g (x') \leq r_k(x')$. Note that the relevant regressor dimension is $d$. As for the variance term $T_4$, note that we can rewrite $$ T_4 = \frac{1}{n_g(x) n_h(x')} \ \big|\sum_{\substack{i \in \mathcal{G}_{g N}(x)\\j \in \mathcal{G}_{h N}(x')}} \zeta_{ij} \big|, $$ where conditional on $(\bold x,\bold g)$, $\{ \zeta_{ij}, \ i \in \mathcal{G}_{gN}(x),\ j \in \mathcal{G}_{hN}(x') \}$ are independent mean-zero bounded random variables. We apply a Hoeffding inequality for bounded random variables, see Theorem 2.2.6 in \citeasnoun{vershynin2018high}, and obtain for any $a_0 \geq 0$,

where we used that $\zeta_{ij} \in [-1,1]$. Taking $a_0 = \sqrt{2 n_g(x) n_h(x')\ln(2/\tilde{\delta})}$ implies

We combine (ref) with (ref) and (ref) to obtain the following Lemma.

Results unconditional on ${\bf g}$

Result on the community assignment probabilities

\

The following results hold up to a permutation but for ease of readability we let $J(x) = J(x')=I$. Note that when (ref) holds,

The behavior of $\pi^{or}_g(x)$ is given by Theorem 1 of \citeasnoun{jiang2019non}. Write $$ \bold{1}_{g,x}(i) =\pi_g(x) +\xi_i $$ with $\mathbb{E}(\xi_i|x(i)=x)=0$. Assumptions 1-3 of \citeasnoun{jiang2019non} hold by Assumptions (ref), (ref) and taking the sub-gaussian parameter to be $ 1$ since $\xi_i \in [-1,1]$ almost surely, see Exercise 2.4 in \citeasnoun{wainwright2019high}. We note that the imposed assumption of independence between $\xi$ and $x$ is not needed for his Theorem 1\footnote{The application of Hoeffding's inequality in the Proof of Theorem 1 (see p4004) can be done conditional on $\bold x$ as long as $(x(i),\xi_i)$ for $i=1...n$ is i.i.d.}. Assume also that

then under Assumption (ref), Theorem 1 of \citeasnoun{jiang2019non} implies that the following holds with probability at least $1 - \tilde{\delta}$,

Let $\pi_g := \Pr(g(i)=g) = \mathbb{E}(\pi_g(x(i)))$ and $\underline{\pi} := \min_{g \in [G]} \pi_g$. We combine Equations (ref) and (ref) to obtain a probability bound unconditional on ${\bf g}$ in the following Lemma, where (ref) is replaced with

\

Result on the connection probabilities

\

We integrate Lemma (ref) with respect to ${\bf g}$ on $T({\bf g})$ and obtain the following Lemma.

Conclusion

This paper demonstrates that it is possible to incorporate both observed and unobserved heterogeneity in network data analysis in a flexible way, at least when we have discrete values of heterogeneity represented by community assignments. It offers a highly versatile, yet computationally tractable procedure, which is expected to complement the existing methodology for analyzing networks with covariates under more specific structures for the edge probabilities and the community assignment probabilities. Our results build upon recent developments in spectral clustering in SBMs and $k$-nn algorithms, and we contribute to the literature by addressing novel theoretical challenges presented by our multi-step procedure. Though our estimators can be computed in a straightforward manner, an extensive simulation exercise is called for in order to assess the efficacy of the new procedure in a practical setting.

\ \

\setcounter{section}{0}