# On Detecting Low-pass Graph Signals
under Partial Observations ††thanks: This work is supported in part by HKRGC
Project #24203520.

Hoang-Son Nguyen  Dept. of Computer Science & Engineering
The Chinese University of Hong Kong
<EMAIL_ADDRESS>Hoi-To Wai  Dept. of Systems Engineering &
Engineering Management
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
###### Abstract

The application of graph signal processing (GSP) on partially observed graph
signals with missing nodes has gained attention recently. This is because
processing data from large graphs are difficult, if not impossible due to the
lack of availability of full observations. Many prior works have been
developed using the assumption that the generated graph signals are smooth or
low pass filtered. This paper treats a blind graph filter detection problem
under this context. We propose a detector that certifies whether the partially
observed graph signals are low pass filtered, without requiring the graph
topology knowledge. As an example application, our detector leads to a pre-
screening method to filter out non low pass signals and thus robustify the
prior GSP algorithms. We also bound the sample complexity of our detector in
terms of the class of filters, number of observed nodes, etc. Numerical
experiments verify the efficacy of our method.

###### Index Terms:

graph signal processing, low pass graph filter, partial observations.

##  I Introduction

An important goal of graph signal processing (GSP) [1] is to extract insights
from complex network data. Using graph shift operator (GSO), graph filters &
signals as the underlying constructs, GSP has led to many theoretically
justified graph learning methods [2, 3], e.g., prior works showed how to
estimate the structure of weather [4] and brain networks [5]. Meanwhile, the
overwhelming size of complex networks has necessitated practical methods to
consider the _partial observation_ setting where a fraction of nodes are never
observed.

The partial observation setting may break a number of properties such as
structure of eigenvectors, smoothness of graph signals, etc., that are
necessary for graph learning. To this end, the early work [6] proposed to
exploit the ‘low-rank+sparse’ structure in the precision matrix of partially
observed graph signal. Subsequent work such as [7] proposed a graph learning
criterion using smoothness of graph signals, [8] considered time-series data,
[9] considered a linear influence model, and [10, 11] focused on
identifiability of network dynamical systems. Additionally, the authors have
studied graph feature learning from partial observations, such as community
[12], central nodes [13]. In the above works, a common assumption made is that
the graph signals are _smooth_ , or more generally, generated from a network
process that can be modeled as exciting a _low-pass graph filter_ [14].

While the _low-pass graph filter_ assumption can be motivated by modeling
network processes from social-physical aspects (e.g., [14], [15]), the latter
often requires prior knowledge on the given dataset. In the absence of prior
knowledge or when the dataset is corrupted, applying GSP methods may lead to
unexpected results. Under this context, it is natural to ask: _Do we know if a
dataset of partially observed graph signals is generated from a low-pass
filter, without knowing the underlying graph beforehand?_ Addressing the
question gives a certificate _prior to_ applying the mentioned methods on
partially observed signals and guarantees reliable outcomes.

Our plan is to build on the authors’ prior work [16], which tackled a similar
detection problem but was focused on fully observed graph signals.
Particularly, as the detection problem is ill-posed in general since
smoothness/low-pass-ness are defined with respect to the graph itself, [16]
focuses on a simplified case where the graph is known to be modular [17], a
common feature for graphs found in networked systems. It then derives a
detector based on the clusterizability of principal components, i.e., spectral
pattern, for observed graph signals.

For partially observed graph signals, the challenge lies on how to account for
the effect of missing nodes on the _observed_ spectral pattern. To this end,
our contributions are:

  * •

We show that the $K$-means score detector in [16] can correctly detect the
spectral pattern of _partially observed_ low-pass graph signals. Though the
latter also exhibit spectral pattern that distinguishes itself from any non-
low-pass signals, we prove that the sampling complexity critically depends on
the number of observed nodes.

  * •

We demonstrate that the proposed detector can be used as a pre-screening
procedure to robustify community detection from partially observed graph
signals.

The rest of this paper is structured as follows. Section II describes the
partial observation setting and formulates the blind detection problem.
Section III develops the proposed method and reports its sample complexity.
Finally, Section IV presents results from preliminary numerical experiments.

Notations. We use $||\cdot||_{2}$ to denote spectral norm for matrices and
Euclidean norm for vectors, and $||\cdot||_{\rm F}$ to denote Frobenius matrix
norm. For a symmetric matrix $\mathbf{X}$, $\lambda_{i}(\mathbf{X})$ denotes
the $i^{th}$ smallest eigenvalue of a matrix.

##  II Problem Statement

Consider an undirected, connected $N$-node graph $G=(V,E)$ where
$V=\\{1,...,N\\}$ and $E\subseteq V\times V$. The graph can be represented as
an adjacency matrix $\mathbf{A}\in\\{0,1\\}^{N\times N}$, a Laplacian matrix
$\mathbf{L}=\mathbf{D}-\mathbf{A}$ where
$\mathbf{D}=\operatorname{diag}(\mathbf{A}\mathbf{1})$, or a normalized
Laplacian matrix
$\mathbf{L}_{\text{norm}}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$.
The aforementioned matrix representations of $G$ qualify as graph shift
operators (GSO), which are any symmetric matrix
$\mathbf{S}\in\mathbb{R}^{N\times N}$ such that $\mathbf{S}_{ij}\neq 0$ only
if $(i,j)\in E$. A GSO admits an eigendecomposition
$\mathbf{S}=\mathbf{V}\mathbf{\Lambda}\mathbf{V}^{\top}$, where the columns of
$\mathbf{V}=[\mathbf{v}_{1},\cdots,\mathbf{v}_{N}]$ are the orthonormal
eigenvectors associated with eigenvalues sorted in ascending order, and
$\mathbf{\Lambda}$ is a diagonal matrix of eigenvalues, also known as the
graph frequencies. We focus on the case of $\mathbf{S}=\mathbf{L}_{\rm norm}$.

The graph filter is defined as a polynomial of the GSO:

$\displaystyle\textstyle\mathcal{H}(\mathbf{S})=\sum_{t=0}^{T}h_{t}\mathbf{S}^{t}=\mathbf{V}h(\mathbf{\Lambda})\mathbf{V}^{\top},$
(1)

where $\\{h_{t}\\}_{t=0}^{T-1}$ are the filter coefficients. The latter also
defines the frequency response function:
$h(\lambda)=\sum_{t=0}^{T}h_{t}\lambda^{t}$ and
$h(\mathbf{\Lambda})=\operatorname{diag}(h(\lambda_{1}),...,h(\lambda_{n}))$.
For simplicity, we assume the magnitudes of frequency responses to be
distinct, i.e. $|h(\lambda_{i})|\neq|h(\lambda_{j})|$ for all $i\neq j$. By
sorting the magnitude of frequency responses in descending order as
$|h_{1}|>...>|h_{N}|$, the graph filter operator can be written as
$\mathcal{H}(\mathbf{S})=\mathbf{U}\mathbf{h}\mathbf{U}^{\top}$, where
$\mathbf{h}=\operatorname{diag}(h_{1},...,h_{N})$ and $\mathbf{U}$ is
accordingly the column re-ordered version of $\mathbf{V}$.

A graph signal on $G$ is represented as a $N$-dimensional vector that is the
output of a graph filter (1):

$\displaystyle\textstyle\mathbf{y}=\mathcal{H}(\mathbf{S})\mathbf{x}+\mathbf{w}.$
(2)

The $i$th element of $\mathbf{y}$ denotes the signal on node $i\in V$,
subjected to the excitation graph signal $\mathbf{x}\in\mathbb{R}^{N}$, and
$\mathbf{w}\in\mathbb{R}^{n}$ is a zero-mean white noise with
$\mathbb{E}[\mathbf{w}\mathbf{w}^{\top}]=\sigma^{2}\mathbf{I}$ for
$\sigma^{2}\geq 0$. The observed signal $\mathbf{y}$ is assumed to be
stationary, i.e., $\mathbb{E}[\mathbf{x}]=\mathbf{0}$ and
$\mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]=\mathbf{I}$ [18], [19] for
simplicity; however, our analysis can be extended to the non-stationary case
of $\mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]\neq\mathbf{I}$.

The graph signal $\mathbf{y}$ in (2) can also be modeled as the output of a
network process. Prior works in GSP have suggested to categorize network
process according to their frequency response. Among others, an important
class of graph filters is the low-pass graph filters [20, 14], which is
defined by:

######  Definition 1.

A graph filter $\mathcal{H}(\cdot)$ is said to be $K$-low-pass if

$\displaystyle\eta_{K}:=\frac{\max_{i=K+1,...,N}|h(\lambda_{i})|}{\min_{i=1,...,K}|h(\lambda_{i})|}<1,$
(3)

where $K$ is cut-off frequency, and $\eta_{K}$ is the sharpness of
$\mathcal{H}$.

From the definition, a low-pass graph filter retains (resp. attenuates) the
energy of the excitation graph signal at low (resp. high) frequencies. A graph
signal is said to be low-pass if it is the output of a low-pass graph filter.

We further consider the scenario when the graph signals in (2) can only be
partially observed. Without loss of generality, we assume that the first $n$
nodes are observed and denote

$\mathbf{y}_{o}=[\mathbf{I}_{n\times
n},\mathbf{0}_{n\times(N-n)}]\,\mathbf{y}=:\mathbf{E}_{o}\mathbf{y}.$ (4)

As mentioned in the Introduction, the application of GSP on partial
observations has gained popularity as the model arises naturally for large
graphs where it is difficult to obtain observations on every nodes. Under this
context, GSP applications such as graph learning [7], community detection [12]
have exploited the _smoothness_ property and motivate the latter by modeling
the graph signal observations as _low pass signals_.

We depart from the above works and inquire if the _smoothness_ property is
valid for a given dataset. This leads to the blind low-pass graph filter
detection problem:

######  Problem 1.

Given the parameter $K$ and a set of partially observed graph signals [cf.
(2), (4)], determine if the underlying graph filter is $K$-low-pass or not
[cf. Definition 1]. We denote the null hypothesis ${\mathcal{}T}_{0}$ (resp.
alternative hypothesis ${\mathcal{}T}_{1}$) as ‘${\mathcal{}H}({\bf S})$ is
(resp. not) $K$-low-pass’.

Notice that Problem 1 serves as a data-driven certificate to the successful
applications of the prior GSP works.

There are two challenges in solving Problem 1: (i) the graph topology or the
GSO ${\bf S}$ is unknown, (ii) the graph signals are partially observed where
${\bf E}_{o}$ is unknown. Either challenge has made it impossible to verify
Definition 1 directly. Our prior work [16] proposed to narrow down the
detection problem w.r.t. arbitrary graphs to the class of $K$-modular graphs
[17] with $K$ densely connected components. The number of densely connected
components naturally determines the parameter $K$ for the low-pass filter. It
then exploits the spectral pattern of graphs to formulate a $K$-means score
detector111We remark that when $K=1$, i.e., the graph contains only one dense
component, applying the Perron Frobenius theorem [21] suffices to detect the
$1$-low-pass graph signals. Here, we shall focus on the case of $K\geq 2$..
The detector is proven to produce accurate result under mild assumptions on
the noise statistics and graph filter properties.

This paper aims to extend the aforementioned detector in [16] to the partial
observation context. Interestingly, we show that the $K$-means score detector
is still robust in this scenario, whose performance loss depends naturally
with the ratio $n/N$.

##  III Low-pass Detection with Partial Observations

This section develops a detector for Problem 1 under the partial observation
setting. Our development begins by investigating the _covariance matrix_ of
partially observed signals:

$\begin{split}\mathbf{C}_{o}=\mathbb{E}[\mathbf{y}_{o,m}\mathbf{y}_{o,m}^{\top}]&=\mathbf{V}_{o}h(\mathbf{\Lambda})^{2}\mathbf{V}_{o}^{\top}+\sigma^{2}\mathbf{I}\\\
&=\mathbf{U}_{o}{\bf
h}^{2}\mathbf{U}_{o}^{\top}+\sigma^{2}\mathbf{I},\end{split}$ (5)

where we have used $\mathbf{y}_{o,m}$ to denote the $m$th realization of the
partially observed signal in (4). We have defined the _row-sampled_
eigenmatrices
$\mathbf{V}_{o}=\mathbf{E}_{o}\mathbf{V},\mathbf{U}_{o}=\mathbf{E}_{o}\mathbf{U}\in\mathbb{R}^{n\times
N}$. The noiseless covariance is
$\overline{\mathbf{C}}_{o}=\mathbf{C}_{o}-\sigma^{2}\mathbf{I}=\mathbf{U}_{o}{\bf
h}^{2}\mathbf{U}_{o}^{\top}$.

Following the insight from [12], we note that when the graph filter has a
_sharp_ cut-off (e.g., $\eta_{K}\ll 1$ under ${\mathcal{}T}_{0}$), the
following approximation holds

$\overline{\mathbf{C}}_{o}\approx\mathbf{U}_{o,K}{\bf
h}_{K}^{2}\mathbf{U}_{o,K}^{\top},$ (6)

where $\mathbf{U}_{o,K}$ takes the $K$ left-most column vectors from
$\mathbf{U}_{o}$. Under ${\mathcal{}T}_{0}$, the matrix $\mathbf{U}_{o,K}$
corresponds to the row-sampled and column permuted version of
$\mathbf{V}_{K}=[\mathbf{v}_{1},...,\mathbf{v}_{K}]$. To this end, the _row
vectors_ of $\mathbf{V}_{K}$ are clusterizable when $G$ is $K$-modular.
Meanwhile, under ${\mathcal{}T}_{1}$ when the graph filter is _not_ $K$-low-
pass, ${\bf U}_{o,K}$ corresponds to the row sampled versions of the bulk
eigenvectors $\\{\mathbf{v}_{K+1},...,\mathbf{v}_{N}\\}$ which are not
clusterizable [22]. Together, they motivate the following $K$-means score: for
any $\mathbf{N}\in\mathbb{R}^{N\times K}$, we denote

$\begin{split}\mathbb{K}^{*}(\mathbf{N})&\textstyle:=\min_{\mathcal{C}}\,\mathbb{K}(\mathbf{N},\mathcal{C}),\\\
\mathbb{K}(\mathbf{N},\mathcal{C})&\textstyle:=\sum_{k=1}^{K}\sum_{i\in\mathcal{C}_{k}}||\mathbf{n}^{\rm
row}_{i}-\frac{1}{|\mathcal{C}_{k}|}\sum_{j\in\mathcal{C}_{k}}\mathbf{n}^{\rm
row}_{j}||^{2}_{2},\end{split}$ (7)

where ${\mathcal{}C}=\\{{\mathcal{}C}_{1},\ldots,{\mathcal{}C}_{K}\\}$ is a
set of non-overlapping partition for $\\{1,...,N\\}$ and $\mathbf{n}^{\rm
row}_{i}$ denotes the $i$th row vector of $\mathbf{N}$.

Define the sampled covariance matrix
$\widehat{\mathbf{C}}_{o}:=(1/M)\sum_{m=1}^{M}\mathbf{y}_{o,m}\mathbf{y}_{o,m}^{\top}$
and its top-$K$ eigenvectors are stacked up as $\widehat{\mathbf{Q}}_{K}$.
Following the insights from [12, 16] and observe that
$\widehat{\mathbf{Q}}_{K}\approx\mathbf{U}_{o,K}$ when $n$ is sufficiently
close to $N$, we propose to tackle Problem 1 by detecting
${\mathcal{}T}_{0}$/${\mathcal{}T}_{1}$ based on $\mathbb{K}^{*}(\widehat{\bf
Q}_{K})$. From the above discussions, $\mathbb{K}^{*}(\widehat{\bf Q}_{K})$
will be small (resp. large) when the graph filter is (resp. not) $K$-low-pass.
This motivates the proposed detector in Algorithm 1.

Algorithm 1 Low-pass Detection with Partial Observations

1: Input: Partially observed graph signals $\\{\mathbf{y}_{o,m}\\}_{m=1}^{M}$,
no. of clusters $K\geq 2$, detection threshold $\delta>0$.

2: Calculate
$\widehat{\mathbf{C}}_{o}:=(1/M)\sum_{m=1}^{M}\mathbf{y}_{o,m}\mathbf{y}_{o,m}^{\top}$.

3: Compute the top-$K$ eigenvectors
$\widehat{\mathbf{Q}}_{K}\in\mathbb{R}^{n\times K}$ of
$\widehat{\mathbf{C}}_{o}$.

4: Output: $\widehat{\mathcal{T}}={\mathcal{}T}_{0}$ if
$\mathbb{K}^{*}(\widehat{\mathbf{Q}}_{K})<\delta$; or
$\widehat{\mathcal{T}}={\mathcal{}T}_{1}$ otherwise.

###  III-A Performance Analysis and Theoretical Insights

We next present the analysis on the finite-sample performance of Algorithm 1.
In addition to verifying the correctness of the detector, our analysis shall
demonstrate the favorable conditions where the detector is effective. Note
that there are multiple sources of error that need to be controlled carefully.
For instance, the approximation in (6) is not exact, the columns of
$\mathbf{U}_{o,K}$ are not orthogonal, etc.

To set up the analysis, we require the following condition on spectral gap of
the covariance matrix:

######  H 1.

With probability at least $1-\delta_{\rm gap}$, there exists $\rho_{\rm gap}$
such that
$\lambda_{n-K-1}(\overline{\mathbf{C}}_{o})-\lambda_{n-K}(\overline{\mathbf{C}}_{o})-||\widehat{\mathbf{C}}_{o}-\overline{\mathbf{C}}_{o}||_{2}\geq\rho_{\rm
gap}>0$.

The above can be satisfied when $\widehat{\mathbf{C}}_{o}$ is sufficiently
close to $\overline{\mathbf{C}}_{o}$, e.g., when sufficient number of samples
are observed and the noise level $\sigma^{2}$ is small, and the noiseless
covariance $\overline{\mathbf{C}}_{o}$ is approximately rank $K$. We also let:

######  H 2.

The graph filter ${\mathcal{}H}(\mathbf{S})$ is at least $\eta$-sharp and
$\gamma$-flat:

$\frac{\max_{i=K+1,...,N}|h_{i}|}{\min_{i=1,...,K}|h_{i}|}\leq\eta<1,~{}~{}\frac{\max_{1\leq
i\leq K}h_{i}^{2}}{\min_{1\leq j\leq K}h_{j}^{2}}\leq\gamma.$ (8)

The above specifies the class of graph filters that we detect. Notice if the
graph filter is $K$-low-pass, then the above $\eta$ takes the same role as
$\eta_{K}$ in (3).

As mentioned in the previous section, the proposed detector relies on the
clusterizability of the top-$K$ eigenvectors for the normalized Laplacian in
$K$-modular graphs. To obtain theoretical insights, we assume that the full
graph $G$ is generated from the stochastic block model (SBM) with:

######  H 3.

We have $G\sim\text{SBM}(N,K,r,p)$ with $p\geq r>0$, $p/K+r\geq(32\log
N+1)/N$.

By $G\sim\text{SBM}(N,K,r,p)$, we denote a random graph with $N$ nodes equally
partitioned into $K$ blocks, described by a membership matrix
$\mathbf{Z}\in\\{0,1\\}^{N\times K}$ such that $\mathbf{Z}_{ij}=1$ if and only
if node $i$ is in block $j$, and a connectivity matrix
$\mathbf{B}\in[0,1]^{K\times K}$, whose entries $\mathbf{B}_{ij}$ being the
probability of edges between nodes in block $i$ and block $j$. The parameters
$r,p$ describes the connectivity such that
$\mathbf{B}=p\mathbf{I}+r\mathbf{1}\mathbf{1}^{\top}$. We also assume the
following on the _bulk eigenvectors_ of $\mathbf{L}_{\rm norm}$:

######  H 4.

With probability at least $1-\delta_{\rm\text{SBM}}$, there exists
$c_{\text{\text{SBM}}}>0$ independent of $N,r,p$ with
$\min_{l=K+1,...,N}\mathbb{K}^{*}(\mathbf{v}_{l})\geq c_{\text{\text{SBM}}}$.

Note that H4 is observed for $G\sim\text{SBM}(N,K,r,p)$ empirically [16], yet
it remains an open conjecture to be verified theoretically. With H3, H4, it is
easy to deduce that $\mathbb{K}^{*}(\mathbf{V}_{K})={\mathcal{}O}(\log N/N)$
[23], while the $K$-means score for the bulk eigenvectors is bounded away by
$c_{\text{\text{SBM}}}>0$.

Let ${\mathcal{}T}_{\rm gnd}\in\\{{\mathcal{}T}_{0},{\mathcal{}T}_{1}\\}$ be
the ground truth hypothesis. Our main analytical result is summarized below:

######  Theorem 1.

Under H1, H2, H3, H4. Suppose that the following threshold-dependent term
satisfies

$\displaystyle\tilde{\delta}_{\rm min}:=\min\Bigg{\\{}$
$\displaystyle\delta-\sqrt{\frac{N}{n}}\sqrt{\frac{1225K^{3}\log N}{p(N-K)}},$
$\displaystyle\sqrt{\frac{N}{n}}\sqrt{c_{\rm\text{SBM}}-\frac{2450K^{3}\log
N}{p(N-K)}}-\delta\Bigg{\\}}>0,$

and that

$\tilde{\sigma}:=\frac{\rho_{\rm gap}(\tilde{\delta}_{\rm
min}-\sqrt{K}(||\mathbf{I}-\mathbf{R}_{K}||_{\rm
2}+6\gamma\eta))}{2\sqrt{K}}-\sigma^{2}>0,$

where $\mathbf{R}_{K}\in\mathbb{R}^{K\times K}$ is an upper triangular matrix
in the QR factorization of
$\mathbf{U}_{o,K}=\sqrt{N/n}\mathbf{Q}_{K}\mathbf{R}_{K}$. If the number of
samples $M$ satisfies

$\displaystyle\sqrt{\frac{M}{\log
M}}\geq\frac{\sqrt{2}c_{1}\operatorname{tr}(\overline{\mathbf{C}}_{o})}{\tilde{\sigma}}$
(9)

where $c_{1}$ is a constant independent of $N,M$, then we have

$\displaystyle\mathbb{P}(\widehat{\mathcal{T}}=\mathcal{T}_{\rm gnd})\geq
1-4/N-5/M-\delta_{\rm gap}-\delta_{\rm\text{SBM}}.$ (10)

The above result considers randomnesses in the graph signals generation (2)
and the SBM graph properties in H3, H4.

The theorem asserts that when $\tilde{\delta}_{\rm min}>0$,
$\tilde{\sigma}>0$, then with a sufficiently large number of samples,
Algorithm 1 will return a correct detection with high probability as
$N,M\to\infty$. To satisfy $\tilde{\delta}_{\rm min}>0$, as
$c_{\rm\text{SBM}}=\Theta(1)$, the requirement can be fulfilled with
$\delta=\Theta(\sqrt{N/n})$. Furthermore, to satisfy $\tilde{\sigma}>0$, we
require two criterion: (i) the noise level $\sigma^{2}$ is sufficiently small,
(ii) the filter constant $\gamma\eta$, and the factor
$\|\mathbf{I}-\mathbf{R}_{K}\|_{2}$ are smaller than
${\mathcal{}O}(\tilde{\delta}_{\rm min})$. Note that
$\|\mathbf{I}-\mathbf{R}_{K}\|_{2}$ decreases to $0$ as $n\to N$; see Fig. 1
for illustration. Finally, we note that the sample complexity, i.e., minimal
$M$ needed to satisfy (9), is proportional to $\tilde{\sigma}^{-1}$. From the
above discussions, $\tilde{\sigma}^{-1}$ is reduced when the graph filters to
be detected are _sharp and flat_ , i.e., $\eta\ll 1,\gamma\approx 1$, and the
number of observed nodes is large enough $n\to N$.

$20$$40$$60$$80$$100$$120$$140$$160$$180$$10^{-2}$$10^{-1}$$10^{0}$No. of
observed nodes $\displaystyle n$ (over
$N=150$)$\displaystyle{||\mathbf{I}-\mathbf{R}_{K}||_{\rm 2}}$K=2K=3K=4

Figure 1: Monte-Carlo simulation of $||\mathbf{I}-\mathbf{R}_{K}||_{\rm 2}$ as
$n\to N$, where the corresponding
$\mathbf{U}_{o,K}=\mathbf{Q}_{K}\mathbf{R}_{K}$ is from $\mathbf{L}_{\rm
norm}$ of a graph generated by $\text{\text{SBM}}(180,K,\log N/N,4\log N/N)$,
with $K\in\\{2,3,4\\}.$

Lastly, we remark that the proof for Theorem 1 is adapted from our prior works
[16, 12] which applied [23, 24]. It can be found in the online
appendix222https://www1.se.cuhk.edu.hk/~htwai/pdf/sam24-appendix.pdf.

##  IV Numerical Experiments

This section presents numerical experiments to validate our findings. We first
evaluate the direct detection performance in tackling Problem 1, then we
consider an application on robustifying the blind community detection method.

###  IV-A Detecting Low-pass Signals from Partial Observations

We use synthetic data to evaluate the performance of our proposed detector in
various settings. In the following experiment, the graph $G$ with $N=150$
nodes and $K=3$ blocks is generated according to H3 such that
$G\sim\text{\text{SBM}}(150,3,\log N/N,4\log N/N)$. The full graph signals in
(2) are generated with
$\mathbf{x}\in\mathbb{R}^{N}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$ and
$\mathbf{w}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I})$ where
$\sigma^{2}=10^{-2}$, then we select $n$ nodes uniformly at random to form the
partial observations (4). We benchmark Algorithm 1 in distinguishing signals
generated by a low-pass filter $e^{-\tau\mathbf{L}_{\rm norm}}$ (null
hypothesis $\mathcal{T}_{0}$) from signals by a non-low-pass filter
$e^{\tau\mathbf{L}_{\rm norm}}$ (alternative hypothesis $\mathcal{T}_{1}$),
where the sharpness of the filter $\eta$ decreases as $\tau>0$ increases. The
performance is measured by the area under ROC (AUROC) such that ${\sf
AUROC}=1$ when the detection is perfect. Figure 2 reports the results from
1000 Monte-Carlo trials.

We observe that the performance improves as $n,M$ increases, as well as the
sharpness parameter $\eta$ controlled by $\tau$. Moreover, Algorithm 1
delivers reliable performance (with ${\sf AUROC}\approx 1$) when $n\geq
100,M\geq 100$. This indicates that the spectral pattern of low-pass graph
signals are significant enough despite that $1/3$ of the nodes are not
observed and only $M\approx n$ samples are observed. The above observations
coincide with our finite-sample analysis in Theorem 1.

102030405060708090100110120130140150$0.4$$0.6$$0.8$$1$No. of observed nodes
$\displaystyle
n$AUROC$\tau$=2.0$\tau$=1.0$\tau$=0.5$\tau$=0.1102030405060708090100110120130140150160170180190200$0.4$$0.6$$0.8$$1$No.
of samples $\displaystyle M$

Figure 2: Comparing low-pass detection performance against (left) no. of
observed nodes $n$ ($M=100$), (right) no. of observed samples $M$ ($n=100$).
The $\tau$ setting adjusts the sharpness of graph filters
$e^{-\tau\mathbf{L}_{\rm norm}}$ or $e^{\tau\mathbf{L}_{\rm norm}}$.

102030405060708090100110120130140150$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$No.
of observed nodes $\displaystyle n$Error
Rate0.10.20.30.40.50.60.70.80.91.0$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$Corrupted
portion of a signal $p_{s}$Corrupted +[12]Pre-screen +[12]Non-corrupted +[12]

Figure 3: Comparing blind community detection performance vs. (left) no. of
observed nodes $n$ ($p_{s}=1$), (right) corrupted portion of signals $p_{s}$
($n=50$).

###  IV-B Application: Robustifying Blind Community Detection

We illustrate an application of Algorithm 1 as a pre-screening procedure
before applying prior work that demands low-pass graph signals. We consider
the blind community detection method [12] which directly infer communities in
a graph from low-pass graph signals that are partially observed. To satisfy
the low-pass graph signal requirement, we apply Algorithm 1 on _small batches_
of $M_{\sf batch}$ graph signal observations and retain (resp. drop) the small
batches that are identified as low-pass (resp. non-low-pass). The pre-screened
dataset is then provided to [12] to infer the communities.

We consider $G\sim\text{SBM}(150,3,\log N/N,7\log N/N$), with $N=150$ nodes
and $K=3$ clusters. The _normal_ graph signals are generated using (2), (4)
with $\sigma^{2}=10^{-2}$ and the filter
${\mathcal{}H}(\mathbf{S})=(\mathbf{I}-0.5\mathbf{L}_{\rm norm})^{3}$, where
$10\%$ of samples are _corrupted_ in a burst of length $m_{\sf burst}=10$,
such that $p_{s}$-fraction of nodal observations are replaced with
${\mathcal{}N}(0,1)$. For the pre-screening procedure, we apply Algorithm 1 on
small batches of size $M_{\sf batch}=50$ from $M=10^{3}$ samples, with
$\delta=0.5$. Figure 3 reports the results of 1000 Monte-Carlo trials.

Observe the dataset corruption severely affects the performance of blind
community detection [12]. Meanwhile, our pre-screening procedure robustifies
the method in [12]. We note the effectiveness of pre-screening improves with
$n$ as it approaches the performance of non-corrupted dataset, coinciding with
Theorem 1 that low-pass detection becomes more accurate as $n$ increases. Pre-
screening also delivers consistent improvement across different levels of
signal corruption.

Conclusions. This paper studies the low-pass graph signal detection problem
with partial observations. We showed that a simple $K$-means score detector
can distinguish spectral pattern of the low-pass/non-low-pass signals and
analyzed its sample complexity. Our work can robustify GSP on partially
observed signals. Future work includes deriving an explicit bound w.r.t. no.
of observed nodes $n$ and explore other applications.

## References

  * [1] A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [2] G. Mateos, S. Segarra, A. G. Marques, and A. Ribeiro, “Connecting the dots: Identifying network structure via graph signal processing,” _IEEE Signal Processing Magazine_ , vol. 36, no. 3, pp. 16–43, 2019.
  * [3] X. Dong, D. Thanou, M. Rabbat, and P. Frossard, “Learning graphs from data: A signal representation perspective,” _IEEE Signal Processing Magazine_ , vol. 36, no. 3, pp. 44–63, 2019.
  * [4] D. Thanou, X. Dong, D. Kressner, and P. Frossard, “Learning heat diffusion graphs,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 3, no. 3, pp. 484–499, 2017.
  * [5] W. Huang, T. A. Bolton, J. D. Medaglia, D. S. Bassett, A. Ribeiro, and D. Van De Ville, “A graph signal processing perspective on functional brain imaging,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 868–885, 2018.
  * [6] V. Chandrasekaran, P. A. Parrilo, and A. S. Willsky, “Latent variable graphical model selection via convex optimization,” _The Annals of Statistics_ , pp. 1935–1967, 2012.
  * [7] A. Buciulea, S. Rey, and A. G. Marques, “Learning graphs from smooth and graph-stationary signals with hidden variables,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 8, pp. 273–287, 2022.
  * [8] A. Jalali and S. Sanghavi, “Learning the dependence graph of time series with latent factors,” _arXiv preprint arXiv:1106.1887_ , 2011.
  * [9] V. Matta, A. Santos, and A. H. Sayed, “Graph learning under partial observability,” _Proceedings of the IEEE_ , vol. 108, no. 11, pp. 2049–2066, 2020.
  * [10] J. M. Hendrickx, M. Gevers, and A. S. Bazanella, “Identifiability of dynamical networks with partial node measurements,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 6, pp. 2240–2253, 2018.
  * [11] A. Santos, D. Rente, R. Seabra, and J. M. Moura, “Learning the causal structure of networked dynamical systems under latent nodes and structured noise,” _arXiv preprint arXiv:2312.05974_ , 2023.
  * [12] H.-T. Wai, Y. C. Eldar, A. E. Ozdaglar, and A. Scaglione, “Community inference from partially observed graph signals: Algorithms and analysis,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 2136–2151, 2022.
  * [13] Y. He and H.-T. Wai, “Central nodes detection from partially observed graph signals,” in _2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2023, pp. 1–5.
  * [14] R. Ramakrishna, H.-T. Wai, and A. Scaglione, “A user guide to low-pass graph signal processing and its applications: Tools and applications,” _IEEE Signal Processing Magazine_ , vol. 37, no. 6, pp. 74–85, 2020.
  * [15] M. H. DeGroot, “Reaching a consensus,” _Journal of the American Statistical association_ , vol. 69, no. 345, pp. 118–121, 1974.
  * [16] C. Zhang, Y. He, and H.-T. Wai, “Detecting low pass graph signals via spectral pattern: Sampling complexity and applications,” _arXiv preprint arXiv::2306.01553_ , 2023.
  * [17] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” _Proceedings of the National Academy of Sciences_ , vol. 99, no. 12, p. 7821–7826, Jun. 2002.
  * [18] N. Perraudin and P. Vandergheynst, “Stationary signal processing on graphs,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 13, pp. 3462–3477, 2017.
  * [19] A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Stationary graph processes and spectral estimation,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 22, pp. 5911–5926, 2017.
  * [20] A. Sandryhaila and J. M. Moura, “Discrete signal processing on graphs,” _IEEE transactions on signal processing_ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [21] Y. He and H.-T. Wai, “Identifying first-order lowpass graph signals using perron frobenius theorem,” in _2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021, pp. 5285–5289.
  * [22] U. von Luxburg, “A tutorial on spectral clustering,” _Statistics and Computing_ , vol. 17, no. 4, p. 395–416, Aug. 2007.
  * [23] K. Rohe, S. Chatterjee, and B. Yu, “Spectral clustering and the high-dimensional stochastic blockmodel,” _The Annals of Statistics_ , vol. 39, no. 4, Aug. 2011.
  * [24] F. Bunea and L. Xiao, “On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fPCA,” _Bernoulli_ , vol. 21, no. 2, pp. 1200 – 1230, 2015.

## Appendix: Proof of Theorem 1

Additional Notations. In the following analysis, we define the QR
decomposition of $\mathbf{U}_{o,K}$ as
$\mathbf{U}_{o,K}=c_{0}\mathbf{Q}_{K}\mathbf{R}_{K}$, in which
$c_{0}=\sqrt{n/N}$ is a normalization parameter,
$\mathbf{Q}_{K}\in\mathbb{R}^{n\times K}$ is an orthogonal matrix spanning the
range of $\mathbf{U}_{o,K}$ and $\mathbf{R}_{K}$ is upper-triangular. We also
set the diagonal of $\mathbf{R}_{K}$ to be non-negative. Moreover, under H3,
$\mathbf{A}$ satisfies
$\mathbb{E}[\mathbf{A}]=\mathbf{Z}\mathbf{B}\mathbf{Z}^{\top}=:\mathcal{A}$;
the population normalized Laplacian matrix of the SBM is then
$\mathcal{L}_{\rm
norm}=\mathbf{I}-\mathcal{D}^{-1/2}\mathcal{A}\mathcal{D}^{-1/2}$, where
$\mathcal{D}=\operatorname{diag}(\sum_{j=1}^{N}\mathcal{A}_{1j},...,\sum_{j=1}^{N}\mathcal{A}_{Nj})$.
Lastly, the set $\mathcal{R}_{K}^{m\times n}$ consists of $m\times n$ matrices
having at most $K$ unique rows.

Our proof is adapted from [16, 12]. First, consider the ground truth as
$\mathcal{T}_{\rm gnd}=\mathcal{T}_{0}$, which implies
$\mathbf{U}_{K}=\mathbf{V}_{K}\mathbf{\Pi}$ for some permutation matrix
$\mathbf{\Pi}$. Define the indicator matrix $\mathbf{X}^{*}$ be associated
with the partition
$\mathcal{C}^{*}\in\arg\min_{\mathcal{C}}\mathbb{K}(\mathbf{Q}_{K},\mathcal{C})$:

$\displaystyle\mathbf{X}^{*}_{ik}:=\begin{cases}1/\sqrt{|\mathcal{C}^{*}_{i}|}&\text{if
}i\in\mathcal{C}^{*}_{i}\text{,}\\\ 0&\text{otherwise.}\end{cases}$

We observe that

$\displaystyle\sqrt{\mathbb{K}^{*}(\widehat{\mathbf{Q}}_{K})}\leq||(\mathbf{I}-\mathbf{X}^{*}(\mathbf{X}^{*})^{\top})\widehat{\mathbf{Q}}_{K}||_{\rm
F}$
$\displaystyle=||(\mathbf{I}-\mathbf{X}^{*}(\mathbf{X}^{*})^{\top})\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}^{\top}||_{\rm
F}$
$\displaystyle\leq||(\mathbf{I}-\mathbf{X}^{*}(\mathbf{X}^{*})^{\top})\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}||_{\rm
F}+||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F}$
$\displaystyle=\sqrt{\mathbb{K}^{*}(\mathbf{Q}_{K})}+||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F}.$

Similarly, we further have

$\displaystyle\sqrt{\mathbb{K}^{*}(\mathbf{Q}_{K})}\leq{c_{0}^{-1}}\sqrt{\mathbb{K}^{*}(\mathbf{U}_{o,K})}+||\mathbf{Q}_{K}-{c_{0}^{-1}}\mathbf{U}_{o,K}||_{\rm
F}$
$\displaystyle\leq{c_{0}^{-1}}\sqrt{\mathbb{K}^{*}(\mathbf{U}_{o,K})}+||\mathbf{Q}_{K}||_{\rm
F}||\mathbf{I}-\mathbf{R}_{K}||_{\rm 2}$
$\displaystyle={c_{0}^{-1}}\sqrt{\mathbb{K}^{*}(\mathbf{U}_{o,K})}+\sqrt{K}||\mathbf{I}-\mathbf{R}_{K}||_{\rm
2}.$

Define the orthogonal matrix
$\overline{\mathcal{O}}_{K}=\mathcal{O}_{K}\mathbf{\Pi}$, where
$\mathcal{O}_{K}$ is from Lemma 4. Since
$\mathcal{V}_{K}\overline{\mathcal{O}}_{K}\in\mathcal{R}_{K}^{N\times K}$
[23], we have
$\mathbf{E}_{o}\mathcal{V}_{K}\overline{\mathcal{O}}_{K}\in\mathcal{R}_{K}^{n\times
K}$. Consequently, by H3 and Lemma 4, with probability at least $1-2/N$,

$\displaystyle\sqrt{\mathbb{K}^{*}(\mathbf{U}_{o,K})}=\min_{\overline{\mathbf{U}}\in\mathcal{R}_{K}^{n\times
K}}||\mathbf{U}_{o,K}-\overline{\mathbf{U}}||_{\rm F}$
$\displaystyle\leq||\mathbf{U}_{o,K}-\mathbf{E}_{o}\mathcal{V}_{K}\overline{\mathcal{O}}_{K}||_{\rm
F}\leq||\mathbf{E}_{o}||_{2}||\mathbf{U}_{K}-\mathcal{V}_{K}\overline{\mathcal{O}}_{K}||_{\rm
F}$
$\displaystyle=||\mathbf{U}_{K}-\mathcal{V}_{K}\overline{\mathcal{O}}_{K}||_{\rm
F}\leq\frac{35\sqrt{K^{3}\log N}}{\sqrt{p(N-K)}}.$

Combining the upper-bound of $\sqrt{\mathbb{K}^{*}(\mathbf{Q}_{K})}$ with
Lemma 2 as well as H1, H2, we conclude that when the null hypothesis holds,
with probability at least $1-2/N-5/M-\delta_{\rm gap}$,

$\displaystyle\mathbb{K}^{*}(\widehat{\mathbf{Q}}_{K})\leq\Bigg{[}\sqrt{\frac{N}{n}}\frac{35\sqrt{K^{3}\log
N}}{\sqrt{p(N-K)}}+\sqrt{K}||\mathbf{I}-\mathbf{R}_{K}||_{\rm 2}$
$\displaystyle+2\sqrt{K}\Bigg{(}3\gamma\eta+\frac{c_{1}\operatorname{tr}(\overline{\mathbf{C}}_{o})\sqrt{2\log
M/M}+\sigma^{2}}{\rho_{\rm gap}}\Bigg{)}\Bigg{]}^{2}.$ (11)

The next case is to consider the ground truth as
$\mathcal{T}_{gnd}=\mathcal{T}_{1}$. Define $\widehat{\mathbf{X}}$ associated
with
$\widehat{\mathcal{C}}\in\arg\min_{\mathcal{C}}\mathbb{K}(\widehat{\mathbf{Q}}_{K},\mathcal{C})$.
Similar to the previous case, we have

$\displaystyle\sqrt{\mathbb{K}^{*}(\mathbf{Q}_{K})}\leq||(\mathbf{I}-\widehat{\mathbf{X}}\widehat{\mathbf{X}}^{\top})\mathbf{Q}_{K}||_{\rm
F}$
$\displaystyle=||(\mathbf{I}-\widehat{\mathbf{X}}\widehat{\mathbf{X}}^{\top})\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}||_{\rm
F}$
$\displaystyle\leq||(\mathbf{I}-\widehat{\mathbf{X}}\widehat{\mathbf{X}}^{\top})\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}^{\top}||_{\rm
F}+||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F}$
$\displaystyle=\sqrt{\mathbb{K}^{*}(\widehat{\mathbf{Q}}_{K})}+||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F},$

which implies
$\sqrt{\mathbb{K}^{*}(\widehat{\mathbf{Q}}_{K})}\geq\sqrt{\mathbb{K}^{*}(\mathbf{Q}_{K})}-||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F}$. By the same technique, we obtain
$\sqrt{\mathbb{K}^{*}(\mathbf{Q}_{K})}\geq
c_{0}^{-1}\sqrt{\mathbb{K}^{*}(\mathbf{U}_{o,K})}-\sqrt{K}||\mathbf{I}-\mathbf{R}_{K}||_{\rm
2}$.

Our remaining task is to lower bound $\sqrt{\mathbb{K}^{*}(\mathbf{U}_{o,K})}$
using H4. Let $\mathbf{U}_{r,s}=[\mathbf{u}_{r},...,\mathbf{u}_{s}]$ consist
of column vectors from $\mathbf{U}$, with $r\leq s$. Also, let $\pi$ be a
permutation function on $\\{1,...,N\\}$, satisfying
$|h_{i}|=|h(\lambda_{\pi(i)})|$. We can see that the set
$\mathcal{P}:=\\{i:1\leq i\leq K,K+1\leq\pi(i)\leq N\\}$ is non-empty under
$\mathcal{T}_{gnd}=\mathcal{T}_{1}$. Then, for any $r\leq s$ such that
$[r,s]\in\mathcal{P}$, by Lemma 1,

$\displaystyle\mathbb{K}^{*}(\mathbf{U}_{o,K})$
$\displaystyle\geq\mathbb{K}^{*}(\mathbf{U}_{K})-|\mathbb{K}^{*}(\mathbf{U}_{o,K})-\mathbb{K}^{*}(\mathbf{U}_{K})|$
$\displaystyle\geq\mathbb{K}^{*}(\mathbf{U}_{K})-\frac{2450K^{3}\log
N}{p(N-K)}$
$\displaystyle\geq\mathbb{K}^{*}(\mathbf{U}_{r,s})-\frac{2450K^{3}\log
N}{p(N-K)}.$

By H4, we have $\mathbb{K}^{*}(\mathbf{U}_{r,s})\geq c_{\text{\text{SBM}}}$.
Together with H1, H2, with probability at least $1-4/N-5/M-\delta_{\rm
gap}-\delta_{\rm\text{SBM}}$, the following lower bound holds

$\displaystyle\mathbb{K}^{*}(\widehat{\mathbf{Q}}_{K})\geq\Bigg{[}\sqrt{\frac{N}{n}}\sqrt{c_{\rm\text{SBM}}-\frac{2450K^{3}\log
N}{p(N-K)}}-\sqrt{K}||\mathbf{I}-\mathbf{R}_{K}||_{\rm 2}$
$\displaystyle-2\sqrt{K}\Bigg{(}3\gamma\eta+\frac{c_{1}\operatorname{tr}(\overline{\mathbf{C}}_{o})\sqrt{2\log
M/M}+\sigma^{2}}{\rho_{\rm gap}}\Bigg{)}\Bigg{]}^{2}.$ (12)

Finally, we can conclude the proof by noting that
$\widehat{\mathcal{T}}=\mathcal{T}_{\rm gnd}$ holds when $\delta$ upper bounds
the right-hand side of (11) and also lower bounds the right-hand side of (12).

### Technical Lemmas

######  Lemma 1.

Under H3. Let $\mathbf{U}_{K}$ denote the columns of the first $K$
eigenvectors of $\mathbf{L}_{\rm norm}$, and
$\mathbf{U}_{o,K}=\mathbf{E}_{o}\mathbf{U}_{K}$. With probability at least
$1-4/N$,

$\displaystyle|\mathbb{K}^{*}(\mathbf{U}_{o,K})-\mathbb{K}^{*}(\mathbf{U}_{K})|\leq\frac{2450K^{3}\log
N}{p(N-K)}.$

###### Proof.

By the triangular inequality,

$|\mathbb{K}^{*}(\mathbf{U}_{o,K})-\mathbb{K}^{*}(\mathbf{U}_{K})|\leq\mathbb{K}^{*}(\mathbf{U}_{o,K})+\mathbb{K}^{*}(\mathbf{U}_{K}).$

Applying Lemma 3 yields
$\mathbb{K}^{*}(\mathbf{U}_{K})\leq\frac{35^{2}K^{3}\log N}{pN(N-K)}$ with
probability at least $1-2/N$.

We now derive an upper-bound for $\mathbb{K}^{*}(\mathbf{U}_{o,K})$. As
$\mathcal{V}_{K}\mathcal{O}_{K}\in\mathcal{R}_{K}^{N\times K}$, we have
$\mathbf{E}_{o}\mathcal{V}_{K}\mathcal{O}_{K}\in\mathcal{R}_{K}^{n\times K}$.
Then, with probability at least $1-2/N$,

$\displaystyle\mathbb{K}^{*}(\mathbf{U}_{o,K})\leq||\mathbf{U}_{o,K}-\mathbf{E}_{o}\mathcal{V}_{K}\mathcal{O}_{K}||_{\rm
F}^{2}\leq||\mathbf{E}_{o}||_{\rm
2}^{2}||\mathbf{U}_{K}-\mathcal{V}_{K}\mathcal{O}_{K}||_{\rm F}^{2}$
$\displaystyle=||\mathbf{U}_{K}-\mathcal{V}_{K}\mathcal{O}_{K}||_{\rm
F}^{2}=\frac{35^{2}K^{3}\log N}{p(N-K)}.$

This concludes the proof. ∎

######  Lemma 2.

Under H1, H2, the following inequality holds with probability at least $1-5/M$

$\displaystyle||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F}\leq$ $\displaystyle
2\sqrt{K}\Bigg{(}3\gamma\eta+\frac{c_{1}\operatorname{tr}(\overline{\mathbf{C}}_{o})\sqrt{2\log
M/M}+\sigma^{2}}{\rho_{\rm gap}}\Bigg{)}.$

where $c_{1}$ is a constant independent of $N,M$ [24].

###### Proof.

By [12, Proposition 1], we have a deterministic upper-bound:

$\displaystyle||\mathbf{Q}_{K}\mathbf{Q}_{K}^{\top}-\widehat{\mathbf{Q}}_{K}\widehat{\mathbf{Q}}_{K}||_{\rm
F}\leq$
$\displaystyle\sqrt{2K}\left(\sqrt{2}\gamma(2||\mathbf{U}_{K}||_{2}+||\mathbf{U}_{N-K}||_{2})\eta_{K}+\frac{||\widehat{\mathbf{C}}_{o}-\overline{\mathbf{C}}_{o}||_{\rm
2}}{\rho_{\rm gap}}\right)$

where we further have $||\mathbf{U}_{K}||_{2}\leq 1$ and
$||\mathbf{U}_{N-K}||_{2}\leq 1$ due to their orthogonality. In addition,
applying [24, Theorem 2.1] on $\\{\mathbf{y}_{o,m}\\}_{m=1}^{M}$ yields the
following inequality: with probability at least $1-5/M$,

$\displaystyle||\widehat{\mathbf{C}}_{o}-\overline{\mathbf{C}}_{o}||_{\rm
2}\leq 2c_{1}\operatorname{tr}(\overline{\mathbf{C}}_{o})\sqrt{\frac{\log
M}{M}}+\sigma^{2}.$

This concludes the proof. ∎

The last two auxiliary lemmas are borrowed from [16], which have been inspired
by [23, 24]:

######  Lemma 3 ([16, Proposition 2]).

Under H3. For $\mathbf{V}_{K}$ consisting of $K$ bottom eigenvectors of
$\mathbf{L}_{\rm norm}$, with probability at least $1-2/N$,

$\mathbb{K}^{*}(\mathbf{V}_{K})\leq\frac{35^{2}K^{3}\log N}{p(N-K)}.$

######  Lemma 4 ([16, Lemma 2]).

Under H3. Let $\mathbf{V}_{K},\mathcal{V}_{K}$ denote the columns of the first
$K$ eigenvectors of $\mathbf{L}_{\rm norm},\mathcal{L}_{\rm norm}$. With
probability at least $1-2/N$, there exists an orthogonal matrix
$\mathcal{O}_{K}\in\mathbb{R}^{K\times K}$ such that

$||\mathbf{V}_{K}-\mathcal{V}_{K}\mathcal{O}_{K}||_{\rm
F}\leq\frac{35\sqrt{K^{3}\log N}}{\sqrt{p(N-K)}}.$