# A User Guide to Low-Pass Graph Signal Processing and its Applications

Raksha Ramakrishna, Hoi-To Wai, Anna Scaglione RR, AS are with the School of
Electrical, Computer, and Energy Engineering, Arizona State University, AZ,
USA. Emails<EMAIL_ADDRESS>HTW is with the Department of
Systems Engineering and Engineering Management, The Chinese University of Hong
Kong, Hong Kong SAR of China. Email<EMAIL_ADDRESS>
###### Abstract

The notion of graph filters can be used to define generative models for graph
data. In fact, the data obtained from many examples of network dynamics may be
viewed as the output of a graph filter. With this interpretation, classical
signal processing tools such as frequency analysis have been successfully
applied with analogous interpretation to graph data, generating new insights
for data science. What follows is a user guide on a specific class of graph
data, where the generating graph filters are low-pass, i.e., the filter
attenuates contents in the higher graph frequencies while retaining contents
in the lower frequencies. Our choice is motivated by the prevalence of low-
pass models in application domains such as social networks, financial markets,
and power systems. We illustrate how to leverage properties of low-pass graph
filters to learn the graph topology or identify its community structure;
efficiently represent graph data through sampling, recover missing
measurements, and de-noise graph data; the low-pass property is also used as
the baseline to detect anomalies.

##  I Introduction

A growing trend in signal processing and machine learning is to develop
theories and models for analyzing data defined on irregular domains such as
graphs. Graphs often express relational ties, such as social, economics
networks, or gene networks, for which several mathematical and statistical
models relying on graphs have been proposed to explain trends in the data [1].
Another case is that of physical infrastructures (utility networks such as
power, gas, water delivery systems and transportation networks) where physical
laws, in addition to the connectivity, define the structure in signals.

For a period of time, the graphical interpretation was primarily used in
statistics with the aim of making _inference_ about graphical models.
Meanwhile, the need for _processing_ graph data has led to the emerging field
of graph signal processing (GSP), which takes a deterministic and system
theoretic approach to justify the properties of graph data and to inspire the
associated signal processing algorithms. A cornerstone of GSP is the formal
definition of graph filter, which extends the notions of linear time invariant
(LTI) filtering of time series signals to data defined on a graph, a.k.a.
graph signals.

In a similar vein as LTI filters in discrete-time signal processing, a graph
filter can be classified as either low-pass, band-pass, or high-pass,
depending on its graph frequency response. Among them, this article focuses on
the _low-pass_ graph filters and the _low-pass_ graph signals generated from
them. These graph filters capture a smoothing operation applied to the input
graph signals, which is a common property of processes observed in many
physical/social systems (see Section III). As a motivating example, in Fig. 1,
we illustrate a few real datasets with such models from social networks, power
systems and financial market, and show the eigenvalue spectra of their sample
covariance matrices. A salient feature observed is that these sample
covariance matrices are low-rank, thus displaying an important symptom of low-
pass filtered graph signals (to be discussed in Section IV).

Figure 1: Illustrating the eigenvalue spectra of sample data covariance matrix
of voltage, Senate rollcall, and financial stock data. These data admit
physical/social models that can be regarded as low-pass filtered graph
signals. A salient feature of their low-pass nature is observed as the low-
rank property of the sample covariance matrices.

Previous articles such as [2, 3] have provided a comprehensive introduction to
modeling and processing graph or network data using GSP, favoring general
abstractions over focusing on particular structures and concrete applications.
This _user guide_ takes a different approach, concentrating on _low-pass graph
filters_ and the corresponding _low-pass graph signal_ outputs. Low-pass graph
signals have specific properties that affect their structure and dictate how
to approach, for example, sampling, denoising and inference problems. They are
worth focusing on, because they are very common in practice. We start the
article by surveying _low-pass_ GSP properties and insights, setting the stage
for the description of the concrete situations where such a model applies. A
set of particular examples is then provided, highlighting the fact that low-
pass graph signals often appear in different application domains. In fact,
resorting to existing underlying network dynamical models that justify
different data sets, we show that low-pass graph processes are nearly
ubiquitous in contexts where GSP is applicable.

##  II Basics of Graph Signal Processing

Many tools introduced in this user guide involve several fundamental concepts
of GSP, including a formal definition of low-pass graph filters/signals. These
ideas will be briefly reviewed in this section. For more details, the readers
are referred to the excellent prior overview articles such as [3, 2]. We
denote vectors with boldfaced lowercase letters, $\bm{x}$ and uppercase
letters for matrices, $\mathbf{A}$. The operation $\texttt{Diag}(\bm{x})$
creates a diagonal matrix with elements from vector $\bm{x}$.

We focus on a weighted undirected graph
${\mathcal{}G}=({\mathcal{}N},{\mathcal{}E})$ with $n$ nodes such that
${\mathcal{}N}=\\{1,\ldots,n\\}$ and
${\mathcal{}E}\subseteq{\mathcal{}N}\times{\mathcal{}N}$ is the edge set. A
graph signal is a function $x:{\mathcal{}N}\rightarrow\mathbb{R}$ which can be
represented by a $n$-dimensional vector ${\bm{x}}=(x(i))_{i\in{\mathcal{}N}}$.
A Graph Shift Operator (GSO) is a matrix $\bm{S}\in\mathbb{R}^{n\times n}$
satisfying $[\bm{S}]_{ij}\neq 0$ if and only if $i=j$ or
$(i,j)\in{\mathcal{E}}$. When multiplied by a graph signal ${\bm{x}}$, each
entry of the shifted graph signal is a linear combination of the one-hop
neighbors’ values, therefore ‘shifting’ the graph signal with respect to the
graph topology. In this article, we take the Laplacian matrix as the GSO. The
Laplacian matrix is defined as ${\bm{L}}:={\bm{D}}-{\bm{A}}$, where ${\bm{A}}$
is the weighted symmetric adjacency matrix of ${\mathcal{}G}$, and
${\bm{D}}=\texttt{Diag}({\bm{A}}{\bf 1})$ is a diagonal matrix of the weighted
degrees. It is also common to take the GSO as the normalized Laplacian matrix,
or the adjacency matrix [4].

Having defined the GSO, we discuss how to measure the smoothness of graph
signals and analyze their content in the graph frequency domain. Recall that
if a signal is smooth in time, the norm of its time derivative is small. For a
graph signal ${\bm{x}}$, its _graph derivative_ is defined as

$[{\nabla}{\bm{x}}]_{ij}=\sqrt{A_{ij}}(x_{i}-x_{j}).$

The squared Frobenius norm of graph derivative, a.k.a. the _graph quadratic
form_ [2], provides an idea of the smoothness of the graph signal ${\bm{x}}$:

${\rm S}_{2}({\bm{x}}):=\frac{1}{2}\|{\nabla}{\bm{x}}\|_{\rm
F}^{2}={\bm{x}}^{\top}{\bm{L}}{\bm{x}}=\sum_{i,j}A_{ij}(x_{i}-x_{j})^{2}.$ (1)

Observe that if $x_{i}\approx x_{j}$ for any neighboring nodes $i,j$, then
${\rm S}_{2}({\bm{x}})\approx 0$. As such, we say that a graph signal is
_smooth_ if ${\rm S}_{2}({\bm{x}})/\|\bm{x}\|_{2}$ is small.

Figure 2: The GFT basis, ${\bf u}_{1},{\bf u}_{2},{\bf u}_{10},{\bf u}_{15}$,
associated to the graph Laplacian of an undirected, unweighted graph with $15$
nodes. As the eigenvalue increases, the eigenvectors tend to be more
oscillatory.

Let us take a closer look at the graph quadratic form ${\rm S}_{2}({\bm{x}})$.
We set the eigendecomposition of the Laplacian matrix as
${\bm{L}}={\bm{U}}\bm{\Lambda}{\bm{U}}^{\top}$ and assume that it has
eigenvalues of multiplicity one ordered as
$\bm{\Lambda}=\texttt{Diag}(\lambda_{1},\ldots,\lambda_{n})$ with
$0=\lambda_{1}<\lambda_{2}<\cdots<\lambda_{n}$, and ${\bm{U}}=({\bf
u}_{1}~{}{\bf u}_{2}~{}\cdots~{}{\bf u}_{n})$ with ${\bf
u}_{i}\in\mathbb{R}^{n}$ being the eigenvector for $\lambda_{i}$. Observe that
for any ${\bm{x}}\in\mathbb{R}^{n}$, it holds $\frac{{\rm
S}_{2}({\bm{x}})}{\|\bm{x}\|_{2}}\geq\frac{{\rm S}_{2}({\bf u}_{1})}{\|{\bf
u}_{1}\|_{2}}=\lambda_{1}$, and for any $\bm{x}$ orthogonal to ${\bf u}_{1}$,
it holds $\frac{{\rm S}_{2}({\bm{x}})}{\|\bm{x}\|_{2}}\geq\frac{{\rm
S}_{2}({\bf u}_{2})}{\|{\bf u}_{2}\|_{2}}=\lambda_{2}$ and so on for the other
eigenvectors. The observation indicates that the larger the eigenvalue, the
more oscillatory the eigenvector is over the vertex set. In particular, the
smallest eigenvalue $\lambda_{1}=0$ is associated with the flat, all-ones
eigenvector ${\bf u}_{1}=(1/\sqrt{n}){\bf 1}$, as seen in Fig. 2. The above
motivates the definition of graph frequencies as the eigenvalues
$\lambda_{1},\ldots,\lambda_{n}$ and of the Graph Fourier Transform (GFT)
basis as the set of eigenvectors $\bm{U}$ [4]. Therefore, the $i^{\text{t}h}$
frequency component of ${\bm{x}}$ is defined as the inner product between
${\bf u}_{i}$ and ${\bm{x}}$:

$\widetilde{x}_{i}={\bf u}_{i}^{\top}{\bm{x}},~{}i=1,\ldots,n,$ (2)

and $\widetilde{\bm{x}}={\bm{U}}^{\top}{\bm{x}}$ is called the GFT of
${\bm{x}}$. The magnitude of the GFT vector $|\widetilde{\bm{x}}|$ is the
‘spectrum’ of the graph signal ${\bm{x}}$, where $|\widetilde{x}_{i}|^{2}$
represents the signal power at the $\lambda_{i}$th frequency.

An important concept to modelling data with GSP is the graph filtering
operation. To this end, a linear _graph filter_ is described as the linear
operator:

${\mathcal{}H}({\bm{L}})=\sum_{p=0}^{P-1}h_{p}{\bm{L}}^{p}={\bm{U}}\Big{(}\sum_{p=0}^{P-1}h_{p}\bm{\Lambda}^{p}\Big{)}{\bm{U}}^{\top},$
(3)

where $P$ is the _filter order_ (can be infinite) and
$\\{h_{p}\\}_{p=0}^{P-1}$ are the _filter’s coefficients_ ; as a convention,
we use ${\bm{L}}^{0}=\bm{I}$ and $\lambda_{0}^{0}=0^{0}=1$. From (3), one can
see that the graph filter has similar interpretation as an LTI filter in
discrete-time signal processing where the former replaces the time shifts by
powers of the GSO. Meanwhile, the second expression in (3) defines the
_frequency response_ as the diagonal matrix
$h(\bm{\Lambda}):=\sum_{p=0}^{P-1}h_{p}\bm{\Lambda}^{p}$. A graph signal
${\bm{y}}$ is said to be filtered by ${\mathcal{}H}({\bm{L}})$ with the input
excitation ${\bm{x}}$ when

${\bm{y}}={\mathcal{}H}({\bm{L}}){\bm{x}}.$ (4)

To better appreciate the effects of the graph filter, note that the $i$th
frequency component of ${\bm{y}}$ is:

$\widetilde{y}_{i}=h(\lambda_{i})\cdot\widetilde{x}_{i},~{}i=1,\ldots,n,$ (5)

where $h({\lambda}):=\sum_{p=0}^{P-1}h_{p}\lambda^{p}$ is the transfer
function of the graph filter, or equivalently, we have
$\widetilde{\bm{y}}=h(\bm{\lambda})\odot\widetilde{\bm{x}}$. It is similar to
the convolution theorem in discrete-time signal processing.

#### Low-pass Graph Filter and Signal

Inspired by (5), we define the ideal low-pass graph filter with a cut-off
frequency $\lambda_{k}$ through setting the transfer function as
$h(\lambda)=1,\lambda\leq\lambda_{k}$ and $0$ otherwise [5]. Alternatively,
one can say that a graph filter is low-pass if its frequency response is
concentrated on the low graph frequencies. In this article, we adopt the
following definition from [6]:

######  Definition 1.

For any $1\leq k\leq n-1$, define the ratio
$\eta_{k}:=\frac{\max\\{|h(\lambda_{k+1})|,\ldots,|h(\lambda_{n})|\\}}{\min\\{|h(\lambda_{1})|,\ldots,|h(\lambda_{k})|\\}}.$
(6) The graph filter ${\mathcal{}H}({\bm{L}})$ is $k$-low-pass if and only if
the low-pass ratio $\eta_{k}$ satisfies $\eta_{k}\in[0,1)$.

The integer parameter $k$ characterizes the _bandwidth_ , or the cut-off
frequency of the low-pass filter is at $\lambda_{k}$. The ratio $\eta_{k}$
quantifies the ‘strength’ of the low-pass graph filter. Upon passing a graph
signal through ${\mathcal{}H}({\bm{L}})$, the high frequency components (above
$\lambda_{k}$) are attenuated by a factor of less than or equal to $\eta_{k}$.
Using this definition, the ideal $k$-low-pass graph filter has the ratio
$\eta_{k}=0$, whose filter order has to be at least $P\geq n-k+1$ and transfer
function $h(\lambda)$ has $\\{\lambda_{k+1},\ldots,\lambda_{n}\\}$ as its
roots.

Finally, a _$k$ -low-pass graph signal_ refers to a graph signal that is the
output of a $k$-low-pass filter, subject to a ‘well-behaved’ excitation (i.e.
does not possess strong high frequency components), which includes, but is not
limited to, the white noise.

#### The Impact of Graph Topologies

From Definition 1, one can observe that the low-pass ratio $\eta_{k}$ of a
graph filter depends on the filter’s coefficients $\\{h_{p}\\}_{p=0}^{P-1}$
and the graph Laplacian matrix’s spectrum $\lambda_{1},\ldots,\lambda_{n}$.
The condition $\lambda_{k}\ll\lambda_{k+1}$ facilitates the design of a
$k$-low-pass graph filter with a favorable ratio $\eta_{k}\ll 1$ and a low
filter order $P$. As an example, the order-1 graph filter
${\mathcal{}H}({\bm{L}})={\bm{I}}-\lambda_{n}^{-1}{\bm{L}}$ is $k$-low-pass
with the ratio
$\eta_{k}=\frac{\lambda_{n}-\lambda_{k+1}}{\lambda_{n}-\lambda_{k}}=1-\frac{\lambda_{k}-\lambda_{k+1}}{\lambda_{n}-\lambda_{k}}$,
where $\eta_{k}$ is small if $\lambda_{k}\ll\lambda_{k+1}$.

An example of graph topologies favoring the condition
$\lambda_{k}\ll\lambda_{k+1}$ is the stochastic block model (SBM) [7] for
describing random graphs with $k$ blocks/communities with nodes in
${\mathcal{}N}$ partitioned as ${\mathcal{}N}_{1},\ldots,{\mathcal{}N}_{k}$.
Consider a simplified SBM with $k$ equal-sized blocks specified by a
membership matrix ${\bm{Z}}\in\\{0,1\\}^{n\times k}$ such that $Z_{i\ell}=1$
if and only if $i\in{\mathcal{}N}_{\ell}$; and a latent model
${\bm{B}}\in[0,1]^{k\times k}$ where $B_{j,\ell}$ is the probability of edges
between nodes in block $j$ and $\ell$. We consider the homogeneous planted
partition model (PPM) such that ${\bm{B}}=b{\bf 1}{\bf 1}^{\top}+a{\bm{I}}$
with $b,a>0$. With the above specification, the adjacency matrix ${\bm{A}}$ is
a symmetric binary matrix with independent entries satisfying
$\mathbb{E}[{\bm{A}}]={\bm{Z}}\bm{B}{\bm{Z}}^{\top}$. When the graph size
grows to infinity ($n\rightarrow\infty$), the Laplacian matrix of an SBM-PPM
graph converges almost surely to its expected value [7, Theorem 2.1]:

${\bm{L}}\overset{a.s.}{\longrightarrow}\mathbb{E}[{\bm{L}}]=\frac{n(a+kb)}{k}\,{\bm{I}}-{\bm{Z}}\big{(}b{\bf
1}{\bf 1}^{\top}+a{\bm{I}}\big{)}{\bm{Z}}^{\top}.$ (7)

From the above, it can be shown that
$\lambda_{k+1}-\lambda_{k}=\frac{na}{k}\gg 1$ for $\mathbb{E}[{\bm{L}}]$,
i.e., a favorable graph model for $k$-low-pass graph filters. Lastly, the
bottom-$k$ eigenvectors of the expected Laplacian associated with
$\lambda_{1},\ldots,\lambda_{k}$ can be collected into the matrix
$\sqrt{\frac{k}{n}}{\bm{Z}}{\bm{P}}$, where ${\bm{P}}$ diagonalizes the matrix
${\bm{B}}$. In other words, the eigenvectors corresponding to the bottom-$k$
eigenvalues of ${\bm{L}}$ will reveal the block structure.

In contrast, the Erdös-Rényi graphs have Laplacian matrices that do not
generally satisfy $\lambda_{k}\ll\lambda_{k+1}$. In fact, asymptotically
($n\rightarrow\infty$) the empirical distribution of the eigenvalues of
Laplacian matrices tends to the free convolution of the standard Gaussian
distribution and the Wigner’s semi-circular law [8]. Such spectrum does not
favor the design of a $k$-low-pass graph filter with $\eta_{k}\ll 1$,
reflecting the fact that block structure or communities do not emerge in Erdös
Rényi graphs.

#### Low-pass Graph-Temporal Filter

When the excitation to a graph filter is of time-varying nature, and the
topology is fixed, we consider a graph-temporal filter [9] with the impulse
response:

$\displaystyle\textstyle{\mathcal{}H}(\bm{L},t):=\sum_{p=0}^{P-1}h_{p,t}{\bm{L}}^{p},$
(8)

such that the graph filter’s output is given by the time-domain convolution
${\bm{y}}_{t}=\sum_{s=0}^{t}{\mathcal{}H}({\bm{L}},t-s){\bm{x}}_{s}$. The
filter is causal and $\bm{x}_{s}=\bm{0}$ for $s<0$. We can apply $z$-transform
and the GFT to the graph signal process $\\{{\bm{x}}_{t}\\}_{t\geq 0}$ to
obtain the $z$-GFT signal, $\widetilde{\bm{X}}(z)$, given by:

$\displaystyle\textstyle\bm{X}(z)=\sum_{t=0}^{\infty}{\bm{x}}_{t}z^{-t},~{}~{}~{}\widetilde{\bm{X}}(z)={\bm{U}}^{\top}{\bm{X}}(z),$
(9)

which represents $\\{{\bm{x}}_{t}\\}_{t\geq 0}$ in the joint $z$-graph
frequency domain. With that, we obtain the input-output relation
$\widetilde{\bm{Y}}(z)=\widetilde{\bm{h}}(z)\odot\widetilde{\bm{X}}(z)$ and
graph-temporal joint transfer function
$\mathbb{H}(\lambda,z):=\sum_{t=0}^{\infty}\sum_{p=0}^{P-1}h_{p,t}\lambda^{p}z^{-t}$.
A class of graph-temporal filters for modeling graph signal processes is the
GF-ARMA $(q,r)$ filter, whose input-output relation in time domain and $z$-GFT
domain are described below, respectively:

$\begin{split}&{\bm{y}}_{t}-{\mathcal{}A}_{1}({\bm{L}}){\bm{y}}_{t-1}\cdots-{\mathcal{}A}_{q}({\bm{L}}){\bm{y}}_{t-q}\\\
&\hskip
14.22636pt={\mathcal{}B}_{0}({\bm{L}}){\bm{x}}_{t}+\cdots+{\mathcal{}B}_{r}({\bm{L}}){\bm{x}}_{t-r},\\\
&\widetilde{\bm{a}}(z)\odot\widetilde{\bm{Y}}(z)=\widetilde{\bm{b}}(z)\odot\widetilde{\bm{X}}(z),\end{split}$

where $\widetilde{\bm{a}}(z)=1-\sum_{s=1}^{q}\widetilde{\bm{a}}_{s}z^{-s}$ and
$\widetilde{\bm{b}}(z)=\sum_{s=0}^{r}\widetilde{\bm{b}}_{s}z^{-s}$ are the
$z$-transform of the graph frequency responses of the graph filter taps
$\\{{\mathcal{}A}_{s}({\bm{L}})\\}_{s=1}^{q}$,
$\\{{\mathcal{}B}_{s}({\bm{L}})\\}_{s=0}^{r}$ for the GF-ARMA $(q,r)$ filter.
Note that the joint frequency response is given by
$\mathbb{H}(\lambda_{i},z)={[\widetilde{\bm{b}}(z)]_{i}}\big{/}{[\widetilde{\bm{a}}(z)]_{i}}$,
whose poles and zeros may vary depending on the graph frequencies
$\lambda_{1},\ldots,\lambda_{n}$. A relevant case is when
${\mathcal{}H}(\bm{L},t)$ is a _low-pass graph-temporal filter_. Similar to
Definition 1, we say that ${\mathcal{}H}(\bm{L},t)$ is low-pass with a cutoff
frequency $(\lambda_{k},\omega_{0})$ and ratio $\eta_{k}$ if:

$\eta_{k}=\frac{\max_{\lambda\in\\{\lambda_{k+1},\ldots,\lambda_{n}\\},\omega\in(\omega_{0},2\pi)}|\mathbb{H}(\lambda,e^{j\omega})|}{\min_{\lambda\in\\{\lambda_{1},\ldots,\lambda_{k}\\},\omega\in[0,\omega_{0}]}|\mathbb{H}(\lambda,e^{j\omega})|}<1.$
(10)

Graph signals filtered by a low-pass graph-temporal filter are also commonly
found in applications, as we will illustrate next.

##  III Models of Low-pass Graph Signals

Before studying the GSP tools for low-pass graph signals, a natural question
is where can one find such graph signals? It turns out that many physical and
social processes are naturally characterized by low-pass graph filters. In
this section, we present various examples and show that their generation
processes can be represented as outputs from low-pass graph filters.

#### Diffusion Model

The first case pertains to observations from a diffusion process, whose
variants are broadly applicable in network science. As an example, we consider
the heat diffusion model in [10]. In this example, the relevant graph is a
proximity graph where each node $i\in{\mathcal{}N}$ is a location (e.g.,
cities), and if locations $i,j$ are close to each other, then
$(i,j)\in{\mathcal{}E}$. The graph is endowed with a symmetric weighted
adjacency matrix encoding the distance between locations. The graph signal
${\bm{y}}_{t}\in\mathbb{R}^{n}$ encodes the temperature of $n$ locations at
time $t$, and let ${\bm{x}}_{0}\in\mathbb{R}^{n}$ be the initial heat
distribution. The temperature of a location is diffused to its neighbors. Let
$\sigma>0$ be a constant, we have

${\bm{y}}_{t}=e^{-t\sigma{\bm{L}}}{\bm{x}}_{0}=\big{(}{\bm{I}}-t\sigma{\bm{L}}+\frac{(t\sigma)^{2}}{2}{\bm{L}}^{2}-\cdots\big{)}{\bm{x}}_{0}$
(11)

where (11) is a discretization of the heat diffusion equation [10]. As
${\bm{L}}{\bf 1}={\bf 0}$, the matrix exponential
$e^{-t\sigma{\bm{L}}}={\bm{I}}-t\sigma{\bm{L}}+\frac{(t\sigma)^{2}}{2}{\bm{L}}^{2}-\cdots$
is row stochastic. The temperature at time $t$ is thus a weighted average of
neighboring locations’ temperatures at $t=0$, i.e., this is a diffusion
dynamical process.

To understand (11) under the context of low-pass filtering, we observe that
${\bm{y}}_{t}$ is a filtered graph signal with the excitation ${\bm{x}}_{0}$
and the graph filter ${\mathcal{}H}({\bm{L}})=e^{-t\sigma{\bm{L}}}$. We verify
that ${\mathcal{}H}({\bm{L}})$ is $k$-low-pass with Definition 1 for any
$k<n$. Note that the low-pass ratio $\eta_{k}$ is:

$\frac{e^{-t\sigma\lambda_{k+1}}}{e^{-t\sigma\lambda_{k}}}=e^{-t\sigma(\lambda_{k+1}-\lambda_{k})}.$

As $\lambda_{k+1}>\lambda_{k}$ and $t\sigma>0$, we see that
${\mathcal{}H}({\bm{L}})$ is a $k$-low-pass graph filter for any
$k=1,\ldots,n-1$.

We have assumed that ${\bm{x}}_{0}$ is an impulse excitation affecting the
system only at the initial time. In practice, the excitation signal may not be
an impulse and the output graph signal ${\bm{y}}_{t}$ is expressed as the
convolution ${\bm{y}}_{t}=\sum_{s=0}^{t}e^{-(t-s)\sigma{\bm{L}}}{\bm{x}}_{s}$.
This corresponds to a low-pass graph-temporal filter with the joint transfer
function $\mathbb{H}(\lambda,z)=(1-e^{-\lambda\sigma}z^{-1})^{-1}$. Besides,
the diffusion process is common in network science as similar models arise in
contagion process and product adoption to name a few.

#### Opinion Dynamics

This example pertains to opinion data mined from social networks with the
influence of external excitation [6, 11]. The relevant graph ${\mathcal{}G}$
is the social network graph where each node $i\in{\mathcal{}N}$ is an
individual, and ${\mathcal{}E}$ is the set of friendships. Similar to the
previous case study, this graph is endowed with a symmetric weighted adjacency
matrix ${\bm{A}}$, where the weights measure the trust among pairs of
individuals. Let $\alpha\in(0,\lambda_{n}^{-1})$, $\beta\in(0,1)$ be
parameters of trust on others and susceptibility to external influence of an
individual respectively. The evolution of opinions follows that of a
combination of DeGroot’s and Friedkin-Johnsen’s model [12], which is a GF-
AR(1) model:

${\bm{y}}_{t+1}=(1-\beta)\big{(}{\bm{I}}-\alpha{\bm{L}}\big{)}{\bm{y}}_{t}+\beta{\bm{x}}_{t},$
(12)

where ${\bm{y}}_{t}\in\mathbb{R}^{n}$ is a graph signal of the individuals’
opinions at time $t$, and ${\bm{x}}_{t}\in\mathbb{R}^{n}$ is a graph signal of
the external opinions perceived by the social network. Note that this also
corresponds to a low-pass graph-temporal filter with the joint transfer
function
$\mathbb{H}(\lambda,z)=\beta[1-(1-\beta)(1-\alpha\lambda)z^{-1}]^{-1}$.

To discuss the steady state of (12), let us assume that
${\bm{x}}_{t}\equiv\bm{x}$. Considering (12), we observe that ${\bm{y}}_{t+1}$
is a convex combination of ${\bm{x}}$ and weighted average of the neighbors’
opinions at time $t$ that is formed by taking a weighted average of
neighboring signals in ${\bm{y}}_{t}$ using a diffusion operator
${\bm{I}}-\alpha{\bm{L}}$. As $\beta>0$, the recursion is stable, leading to
the steady state (or equilibrium) opinions:

${\bm{y}}=\lim_{t\rightarrow\infty}{\bm{y}}_{t}=\left({\bm{I}}+\widetilde{\alpha}{\bm{L}}\right)^{-1}{\bm{x}}={\mathcal{}H}({\bm{L}}){\bm{x}},$
(13)

where we have defined $\widetilde{\alpha}=\beta(1-\alpha)/\alpha>0$ and
${\bm{y}}$ is a filtered graph signal excited by ${\bm{x}}$.

The graph filter above is given by
${\mathcal{}H}({\bm{L}})=(\bm{I}+\widetilde{\alpha}{\bm{L}})^{-1}$. To verify
that it is a $k$-low-pass graph filter with Definition 1, we note that for any
$k<n$, the low-pass ratio $\eta_{k}$ is

$\frac{1+\widetilde{\alpha}\lambda_{k}}{1+\widetilde{\alpha}\lambda_{k+1}}=1-\widetilde{\alpha}\frac{\lambda_{k+1}-\lambda_{k}}{1+\widetilde{\alpha}\lambda_{k}}.$

Again, we observe that as $\lambda_{k+1}>\lambda_{k}$, the above graph filter
is $k$-low-pass for any $k=1,\ldots,n-1$. However, we remark that this low-
pass ratio may be undesirable with $\eta_{k}\approx 1$ when
$\widetilde{\alpha}\ll 1$. Interestingly, a similar generative model as (12)
is found in equilibrium problems such as quadratic games [13].

Two remarks are in order. First, social networks are typically directed, and
this suggests using a non-symmetric shift operator as opposed to the symmetric
Laplacian matrix, which we used for simplicity of exposition. Second, many
alternative models for social networks interactions are non-linear and linear
GSP is insufficient in those contexts.

#### Finance Data

Financial systems such as stock market and hedge funds produce return reports
periodically about their business performances. A collection of these reports
can be studied as graph signals, where the relevant graph ${\mathcal{}G}$
consists of nodes ${\mathcal{}N}$ that are financial institutions, and edges
${\mathcal{}E}$ that are business ties between them. It has been studied [14]
that business performances are correlated according to the business ties.
Moreover, the returns are affected by a number of common factors [15].
Inspired by [14], [15, Ch. 12.2], let $\beta\in(0,1)$ be the strength of
external influences, a reasonable model for the transient dynamics of the
graph signal ${\bm{y}}_{t}$ of business performance measures is also a GF-
AR(1):

${\bm{y}}_{t+1}=(1-\beta){\mathcal{}H}({\bm{L}}){\bm{y}}_{t}+\beta{\bm{B}}{\bm{x}},$
(14)

where ${\mathcal{}H}({\bm{L}})$ is an unknown but low-pass graph filter,
${\bm{B}}\in\mathbb{R}^{n\times r}$ represents the factor model affecting
financial institutions, and ${\bm{x}}\in\mathbb{R}^{r}$ is the excitation
strength. The equilibrium of (14) is:

${\bm{y}}=\lim_{t\rightarrow\infty}{\bm{y}}_{t}=\Big{(}\frac{1}{\beta}{\bm{I}}-\frac{\overline{\beta}}{\beta}{\mathcal{}H}({\bm{L}})\Big{)}^{-1}{\bm{B}}{\bm{x}}\equiv\widetilde{\mathcal{}H}({\bm{L}}){\bm{B}}{\bm{x}},$

where $\overline{\beta}=1-\beta$. We see that ${\bm{B}}{\bm{x}}$ is the
excitation signal and the equilibrium ${\bm{y}}$ is the filter output. Suppose
that ${\mathcal{}H}({\bm{L}})$ is a $k$-low-pass graph filter with the
frequency response satisfying $h(\lambda)\geq 0$, then for
$\widetilde{\mathcal{}H}({\bm{L}})$, we can evaluate the low-pass ratio
$\eta_{k}$ as

$\begin{split}1-\frac{\overline{\beta}\big{\\{}\min_{\ell=1,\ldots,k}h(\lambda_{\ell})-\max_{\ell=k+1,\ldots,n}h(\lambda_{\ell})\big{\\}}}{1-\overline{\beta}\max_{\ell=k+1,\ldots,n}h(\lambda_{\ell})}.\end{split}$

As
$\min_{\ell=1,\ldots,k}h(\lambda_{\ell})-\max_{\ell=k+1,\ldots,n}h(\lambda_{\ell})>0$
since ${\mathcal{}H}({\bm{L}})$ is a $k$-low-pass graph filter itself, we
observe that $\widetilde{\mathcal{}H}({\bm{L}})$ is again $k$-low-pass
according to Definition 1.

For ${\bm{y}}$ to be a $k$-low-pass graph signal, one has to also assume that
${\bm{B}}{\bm{x}}$ is not high-pass (i.e., not orthogonal to a low-pass one).
This is a mild assumption as the latent factor affecting financial
institutions are either independent of the network, or are aligned with the
communities. Above all, we remark that (14) is an idealized model where
determining the exact model is an open problem in economics, see [15, 14].

#### Power Systems

In the case of power systems, the relevant graph
${\mathcal{}G}=({\mathcal{}N},{\mathcal{}E})$ is the electrical transmission
lines network. The node (a.k.a. bus) set includes generator buses,
${\mathcal{}N}_{g}=\\{1,\ldots,|{\mathcal{}N}_{g}|\\}$, and non-generator/load
buses, ${\mathcal{}N}_{\ell}={\mathcal{}N}\setminus{\mathcal{}N}_{g}$. The
edge set $\mathcal{E}$ refers to the transmission lines connecting the buses.
The branch admittance matrix, $\bm{Y}$, models the effect of transmission
lines and is a complex symmetric matrix associated with ${\mathcal{}G}$, where
$\left[\bm{Y}\right]_{ij}$ is the complex admittance of the branch between
nodes $i$ and $j$ provided that $(i,j)\in\mathcal{E}$ . The graph signals we
consider are the complex voltage phasors, denoted as
${\bm{v}}_{t}\in\mathbb{C}^{n}$ when measured at time $t$. They can be
obtained using phasor measurement units (PMU) [16] installed on each bus
$i\in{\mathcal{}N}$. The graph shift operator in this case is a diagonally
perturbed branch admittance matrix:

$\displaystyle{\bm{S}}_{\sf
grid}:=\bm{Y}+\texttt{diag}\left({\small[\bm{y}_{g}^{\top},\bm{y}_{\ell}^{\top}(0)]}\right),$
(15)

where $\bm{y}_{g}\in\mathbb{C}^{|{\mathcal{}N}_{g}|}$ is the generator
admittance and ${\bm{y}}_{\ell}(0)\in\mathbb{C}^{|{\mathcal{}N}_{\ell}|}$ is
the load admittance at $t=0$.

Note that ${\bm{S}}_{\sf grid}$ is a GSO on the grid graph as $[{\bm{S}}_{\sf
grid}]_{ij}=0$ if $(i,j)\notin{\mathcal{}E}$. The _complex symmetric_ matrix
${\bm{S}}_{\sf grid}$ can be decomposed as ${\bm{S}}_{\sf grid}={\bf
U}\bm{\Lambda}{\bf U}^{\top}$, where ${\bf U}$ is a complex orthogonal matrix
satisfying ${\bf U}^{\top}{\bf U}={\bm{I}}$, and $\bm{\Lambda}$ is a diagonal
matrix with diagonal elements $\\{\lambda_{1},\ldots,\lambda_{n}\\}$ sorted as
$0<|\lambda_{1}|\leq\cdots\leq|\lambda_{n}|$; see [17] for modeling details.
Let ${\bm{i}}_{t}^{g}\in\mathbb{C}^{n}$ be the outgoing current at each node
at time $t$, given by
$\bm{i}^{g}_{t}:=[\bm{y}^{\top}_{g}\odot{\exp\left(\bm{x}^{\top}_{t}\right)},\bm{0}]^{\top},$
where elements in
$\exp\left(\bm{x}_{t}\right)\in\mathbb{C}^{\lvert\mathcal{N}_{g}\rvert}$ are
the internal voltage phasors at the generator buses. Applying Kirchoff’s
current law in quasi-steady state, the voltage phasors
$\bm{v}_{t}\in\mathbb{C}^{n}$ are:

$\displaystyle\bm{v}_{t}={\bm{S}}_{\sf
grid}^{-1}\,\bm{i}^{g}_{t}+\bm{w}_{t}=\mathcal{H}({\bm{S}}_{\sf
grid})\,\bm{i}^{g}_{t}+\bm{w}_{t},$ (16)

where ${\bm{w}}_{t}\in\mathbb{C}^{n}$ captures the slow time-varying nature of
the load and other modeling approximations. In other words, ${\bm{v}}_{t}$ is
a graph signal obtained by the graph filter ${\mathcal{}H}({\bm{S}}_{\sf
grid})={\bm{S}}_{\sf grid}^{-1}$ and the excitation signal
${\bm{i}}_{t}^{g}\in\mathbb{C}^{n}$. Particularly, we observe that
${\mathcal{}H}({\bm{S}}_{\sf grid})={\bm{S}}_{\sf grid}^{-1}$ is a low-pass
graph filter. Consider any $k\leq n$, the low-pass ratio $\eta_{k}$ is

${|\lambda_{k}|}/{|\lambda_{k+1}|}.$

As the power grids tend to be organized as communities to serve different
areas with high population densities, the system admittance matrix $\bm{Y}$ is
block diagonal and sparse. In particular, with $k$ communities in the grid
graph, these facts indicate that the graph filter is $k$-low-pass satisfying
$\eta_{k}\ll 1$.

The excitation graph signal $\bm{i}^{g}_{t}$ itself has a low-rank structure,
as $[\bm{i}^{g}_{t}]_{i}=0$ at $i\notin{\mathcal{}N}_{g}$. The temporal
dynamics of $\bm{x}_{t}$ can be described as an AR(2) graph filter [9] using a
reduced generator-only shift operator
$\bm{S}_{\text{red}}\in\mathbb{C}^{\lvert\mathcal{N}_{g}\rvert}$ with the
graph-temporal transfer function, $\mathbb{H}(\lambda_{\text{red}},z)$,

$\begin{split}&\bm{x}_{t}=\sum_{s=0}^{t}\mathcal{H}\left(\bm{S}_{\text{red}},t-s\right)\bm{p}_{s},\\\
&\mathbb{H}(\lambda_{\text{red}},z)=\sigma_{p}^{2}\Big{(}1-\sum_{p=0}^{1}a_{p,1}\lambda_{\text{red}}^{p}z^{-1}-\sum_{p=0}^{1}a_{p,2}\lambda_{\text{red}}^{p}z^{-2}\Big{)}^{-1}.\end{split}$

where $\bm{p}_{s}$ is the stochastic power input to the system. The graph-
temporal filter is low-pass in the time domain. The overall system in (16) has
approximately the properties of a low-pass graph temporal filter according to
the definition in (10).

##  IV User Guide to Low-pass Graph Signal Processing

If we observe a set of low-pass graph signals such as those from Section III,
what can we learn from these signals? Can we find efficient representations
for them? Can we exploit this structure to denoise the signal or detect
anomalies? To answer these questions, we begin by studying two salient
features of low-pass graph signals, namely _low-rank covariance matrix_ , and
_smoothness_ as measured by the graph quadratic form. Then, we illustrate how
these features can enable low-pass GSP to sample graph signals (and therefore
compress them), to infer the graph topology, and to detect anomalous
activities. Furthermore, when the graph topology admits a clustered structure,
we highlight how these clusters emerge in the low-pass graph signals and
provide insights on the optimal sampling patterns.

We now consider a set of $m$ low-pass graph signals that can be modeled as
outcomes of independent and identically distributed random experiments, given
as:

${\bm{y}}_{\ell}={\mathcal{}H}({\bm{L}})\,{\bm{x}}_{\ell}+{\bm{w}}_{\ell},\quad\ell=1,\ldots,m,$
(17)

such that ${\mathcal{}H}({\bm{L}})$ is a $k$-low-pass graph filter defined on
the Laplacian matrix, ${\bm{x}}_{\ell}$ is the excitation signal, and
${\bm{w}}_{\ell}$ is an additive noise. For simplicity, we do not consider the
more general low-pass graph-temporal processes and assume that
${\bm{x}}_{\ell}$, ${\bm{w}}_{\ell}$ are zero-mean white noise with
$\mathbb{E}[{\bm{x}}_{\ell}{\bm{x}}_{\ell}^{\top}]={\bm{I}}$,
$\mathbb{E}[{\bm{w}}_{\ell}{\bm{w}}_{\ell}^{\top}]=\sigma^{2}{\bm{I}}$. We
remark that the following observations still hold for the general setting when
$\mathbb{E}[{\bm{x}}_{\ell}{\bm{x}}_{\ell}^{\top}]$ is not white, or even
diagonal. The latter relaxation is important for the applications listed in
Section III. For instance, in opinion dynamics, the excitation signals may
represent external opinions that do not affect the social network uniformly,
e.g., they are news articles written in a foreign language.

###  IV-A Low-rank Covariance Matrix

From (17), it is straightforward to show that
$\\{{\bm{y}}_{\ell}\\}_{\ell=1}^{m}$ is zero-mean with the covariance matrix

${\bm{C}}_{y}={\bm{U}}h(\bm{\Lambda})^{2}{\bm{U}}^{\top}+\sigma^{2}{\bm{I}}.$
(18)

Recall that ${\mathcal{}H}({\bm{L}})$ is a $k$-low-pass graph filter, if
$\eta_{k}\ll 1$ as defined in (6), the energy of $h(\bm{\Lambda})$ will be
concentrated in the top-$k$ diagonal elements. Therefore, when the noise
variance is small ($\sigma^{2}\approx 0$), the low-pass graph signals lie
approximately in $\mbox{span}({\bm{U}}_{k})$, a $k$-dimensional subspace of
$\mathbb{R}^{n}$.

#### a-i). Sampling Graph Signals

As the $k$-low-pass graph signals lie approximately in
$\mbox{span}({\bm{U}}_{k})$, it is possible to map the graph signals almost
losslessly onto $k$-dimensional vectors. While the $k$-dimensional
representation can be obtained by projecting on the space spanned by
${\bm{U}}_{k}$, it is not necessary to do so. An alternative to generate this
$k$-dimensional representation is by decimating the graph signals.

[0cm 4.75cm](a) |  |  [0cm 4.75cm](b) |  |  [0cm 4.75cm](c) |
---|---|---|---|---|---
Figure 3: (a) Magnitude of Graph Fourier Transform (GFT) of voltage graph
signal plotted with respect to normalized graph frequencies. (b) Sampling
pattern overlaid on the support of GSO $\bm{S}_{\sf grid}$ for placing
synchro-phasors sensors on the synthetic 2000 bus ACTIVSg power grid system by
employing a greedy method to find $k=100$ rows of $\mathbf{U}_{k}$ so that the
smallest singular value of $\bm{\Phi}\bm{U}_{k}$ is maximized (The first
entries correspond to generator buses). This case emulates the grid for the
state of Texas (called ERCOT systems), where there are 8 areas, matching the
number of communities evident from the GSO. (c) Reconstructed voltage graph
signal using optimally placed sensors at a subset of buses (1000-1500).

To describe the setup, we let
${\mathcal{}N}_{s}=\\{s_{1},\ldots,s_{n_{s}}\\}\subset{\mathcal{}N}$ be a
sampling set with cardinality $n_{s}=|{\mathcal{}N}_{s}|$. A sampled version
of ${\bm{y}}_{\ell}$ is constructed as (omitting the subscript $\ell$ for
brevity):

$\text{{\sf(i)} select a subset ${\mathcal{}N}_{s}\subset{\mathcal{}N}$;
{\sf(ii)} set}~{}~{}{\bm{y}}_{\sf samp}=\bm{\Phi}{\bm{y}},$ (19)

such that

$[\bm{\Phi}]_{q,j}=\begin{cases}1,&\text{if}~{}j=s_{q},\\\
0,&\text{otherwise},\end{cases}$

and $\bm{\Phi}\in\mathbb{R}^{n_{s}\times n}$ is a fat sampling matrix that
compresses the graph signal to an $n_{s}$-dimensional vector. To recover
${\bm{y}}$, we interpolate ${\bm{y}}_{\sf samp}$ using a matching linear
transformation [18], giving $\widehat{\bm{y}}=\bm{\Psi}{\bm{y}}_{\sf samp}$
with $\bm{\Psi}\in\mathbb{R}^{n\times n_{s}}$ to be designed later. Clearly,
when $n_{s}<n$, it is not possible to exactly recover an _arbitrary graph
signal_. To ensure exact recovery, we see that it requires certain additional
conditions on the sampling set and the graph signal.

Exactly recovering ${\bm{y}}$ from its sampled version ${\bm{y}}_{\sf samp}$
would require the sampled graph signal to be in the range space of sampling
matrix $\bm{\Phi}$. We let
$\overline{\bm{y}}={\bm{U}}_{k}{\bm{U}}_{k}^{\top}{\bm{y}}$ be the projection
of ${\bm{y}}$ onto the (low-frequency) subspace spanned by ${\bm{U}}_{k}$ and
$\overline{\bm{w}}={\bm{y}}-\overline{\bm{y}}$ be the projection error. The
projected graph signal $\overline{\bm{y}}$ is a $k$-bandlimited (in fact,
$k$-low-pass) graph signal. From [18, Theorem 1], a sufficient condition for
exact recovery is that if

${\rm rank}\big{(}\bm{\Phi}{\bm{U}}_{k}\big{)}=k,$ (20)

then there exists an interpolation matrix $\bm{\Psi}\in\mathbb{R}^{n\times
n_{s}}$ such that $\bm{\Psi}\bm{\Phi}\overline{\bm{y}}=\overline{\bm{y}}$. In
fact, it is possible to recover any $k$-bandlimited graph signal from its
sampled version. We have

$\widehat{\bm{y}}=\bm{\Psi}{\bm{y}}_{\sf
samp}=\overline{\bm{y}}+\bm{\Psi}\bm{\Phi}\overline{\bm{w}}={\bm{y}}+(\bm{\Psi}\bm{\Phi}-{\bm{I}})\overline{\bm{w}}.$
(21)

As $k$-low-pass graph signals lie approximately in ${\rm span}({\bm{U}}_{k})$,
we have $\overline{\bm{w}}\approx 0$ provided that $\eta_{k}\ll 1$. Under
condition (20), the sampling-and-interpolation procedure results in a small
interpolation error.

Clearly, a necessary condition to satisfy (20) is $n_{s}\geq k$, i.e., we
require at least the same number of samples as the bandwidth of the low-pass
graph filter which produces the graph signal ${\bm{y}}$. Beyond the necessary
condition, obtaining a sufficient condition for (20) can be difficult as it is
not obvious to derive conditions on the sampling set. The design of the
sampling set has been the focus of work in [18, 19, 20] which propose to find
${\mathcal{}N}_{s}$ via a greedy method, or via the graph spectral proxies.
The above statements are valid for any graph signal that has a sparse
frequency support. In the case of low-pass graph signals, we can obtain
insights on what type of sampling patterns are compatible with (20). Consider
the special case of SBM-PPM graphs with $k$ blocks discussed in Section II.
Note that as $n\rightarrow\infty$, we have
${\bm{U}}_{k}=\sqrt{k/n}\,{\bm{Z}}{\bm{P}}$ for this model, where ${\bm{Z}}$
is the block-membership matrix. Subsequently, condition (20) can be easily
verified if ${\mathcal{}N}_{s}$ contains _at least one node_ from _each of the
$k$ blocks_.

In Fig. 3, we consider a power system application. We first plot the magnitude
of GFT of voltage graph signal with respect to normalized graph frequencies in
log scale. From the linear decay, it is evident that the magnitude of GFT
coefficients at lower frequencies is higher confirming the signal is low-pass
in nature. Then, the sampling pattern (or optimal placement of sensors) for
graph signal reconstruction is shown in the figure. The block structure in the
GSO for the electric grid guides the sampling strategy. In this example, the
smallest singular value of $\bm{\Phi}\bm{U}_{k}$ is maximized using a greedy
algorithm [20].

#### a-ii). Blind Community Detection

Another consequence of (18) relates to learning the _block or community
structure_ when the graph topology is unknown. When the graph topology is
known, spectral clustering (SC) is often the method of choice. The SC method
computes the bottom-$k$ eigenvectors of Laplacian as ${\bm{U}}_{k}$ and
partitions the $n$ nodes via $k$-means:

$F^{\star}=\min_{{\mathcal{}N}_{1},\ldots,{\mathcal{}N}_{k}}~{}F({\mathcal{}N}_{1},\ldots,{\mathcal{}N}_{k};{\bm{U}}_{k}),$
(22)

where

$F({\mathcal{}N}_{1},\ldots,{\mathcal{}N}_{k};{\bm{U}}_{k}):=\Big{(}\sum_{q=1}^{k}\sum_{i\in{\mathcal{}N}_{q}}\Big{\|}{\bf
u}_{i}^{\rm row}-\frac{1}{|{\mathcal{}N}_{q}|}\sum_{j\in{\mathcal{}N}_{q}}{\bf
u}_{j}^{\rm row}\Big{\|}_{2}^{2}\Big{)}^{1/2},$

such that ${\bf u}_{i}^{\rm row}\in\mathbb{R}^{k}$ is the $i$th row vector of
${\bm{U}}_{k}$. In fact, this is an effective method for SBM-PPM graphs where
solving (22) reveals the true block membership [7].

[0cm 5cm](a) |  |  [0cm 5cm](b) |
---|---|---|---
Figure 4: Communities detected from opinion dynamics and stock data. (a) US
Senate voting records: (Top) inferred membership via BlindCD, (Bottom) actual
party membership of Senators taken from
[https://en.wikipedia.org/wiki/115th_United_States_Congress]. Note that the
purple color in the bottom indicates that the state has a Democrat Senator and
a Republican Senator. (b) Daily returns of S&P100 stocks. Colors on the nodes
represent different detected communities. Communities are manually labeled
according to business types.

Although only the graph signals $\\{{\bm{y}}_{\ell}\\}_{\ell=1}^{m}$ are
observed, we know from (18) that the covariance matrix ${\bm{C}}_{y}$ will be
dominated by a rank-$k$ component spanned by ${\bm{U}}_{k}$ under the low-pass
assumption. In fact, this is precisely what we need for community detection as
hinted in (22). To this end, [6] proposed the blind community detection
(BlindCD) procedure:

$\begin{array}[]{l}\text{{\sf(i)} find the top-$k$ eigenvectors
$\widehat{\bm{U}}_{k}\in\mathbb{R}^{n\times k}$}\\\\[2.84544pt]
~{}~{}~{}~{}\text{of sample covariance
$\widehat{\bm{C}}_{y}=\frac{1}{m}\sum_{\ell=1}^{m}{\bm{y}}_{\ell}{\bm{y}}_{\ell}^{\top}$;}\\\\[2.84544pt]
\text{{\sf(ii)} apply $k$-means on the rows of
$\widehat{\bm{U}}_{k}$.}\end{array}$

If we denote the detected communities as
$\widehat{\mathcal{}N}_{1},\ldots,\widehat{\mathcal{}N}_{k}$, then

$F(\widehat{\mathcal{}N}_{1},\ldots,\widehat{\mathcal{}N}_{k};{\bm{U}}_{k})-F^{\star}={\mathcal{}O}(\eta_{k}+\sigma+{m}^{-1/2}).$
(23)

In other words, the BlindCD approaches the performance of SC if the graph
filter is $k$-low-pass with $\eta_{k}\ll 1$, the observation noise $\sigma$ is
small, and the number of samples $m$ is large. Notice that (23) is a general
result which holds even if $\mathbb{E}[{\bm{x}}_{\ell}{\bm{x}}_{\ell}^{\top}]$
is non-diagonal or low-rank. Moreover, BlindCD is shown to outperform a two-
step approach that learns the graph first and then apply SC; see [6].

In Fig. 4, we illustrate results of community detection for opinion dynamics
and financial data by using data from US Senate from the 115th US Congress
(2017-2019) and daily return data of stocks in the S&P100 index from Feb. 2013
to Dec. 2016 [source: https://www.kaggle.com/camnugent/sandp500] respectively.
The observed steady-state graph signals ${\bm{y}}_{\ell}$ for the opinion
dynamics case are the aggregated vote records of each state, and we observe
$m=502$ voting rounds. In Fig. 4 (a), we apply BlindCD to partition the states
into $K=2$ groups, where a close alignment between our results with the actual
party memberships of this US Congress is observed. The financial dataset used
contains $m=975$ days of data for $n=92$ stocks. In Fig. 4 (b) we apply
BlindCD to partition the stocks into $K=10$ groups. Each of the community
detected includes companies of the same business type (for instance, ‘BAC’
(Bank of America) is with ‘JPM’ (JP Morgan)) showing the effectiveness of the
method.

###  IV-B Smooth Graph Signals

In Section II we introduced the graph quadratic form to quantify the
_smoothness_ of a graph signal. Particularly, if ${\rm
S}_{2}({\bm{y}})={\bm{y}}^{\top}{\bm{L}}{\bm{y}}\ll\|{\bm{y}}\|_{2}$, the
graph signal ${\bm{y}}$ is said to be smooth. For $k$-low-pass graph signals,
we observe that

$\mathbb{E}\big{[}{\rm
S}_{2}({\bm{y}}_{\ell})\big{]}\approx\sum_{i=1}^{k}\lambda_{i}\,|h(\lambda_{i})|^{2}+\sigma^{2}{\rm
Tr}({\bm{L}}),$ (24)

where we have used that ${\mathcal{}H}({\bm{L}})$ is $k$-low-pass with
$\eta_{k}\ll 1$ to derive the approximations. In the cases when
$\lambda_{i}\approx 0$, $i=1,\ldots,k$ such as large SBM-PPM graphs with
parameters $(a,b)$ satisfying $b\ll 1$, $a\approx 1$, we expect the $k$-low-
pass graph signal to be smooth, i.e., $\mathbb{E}[{\rm
S}_{2}({\bm{y}}_{\ell})]\approx 0$.

#### b-i). Graph Topology Learning

The smoothness property can be used to learn the graph topology by fitting a
Laplacian matrix which best _smoothens_ the graph signals. This is exemplified
by the estimator:

$\begin{array}[]{rl}\displaystyle\min_{{\bm{z}}_{\ell},\ell=1,\ldots,m,\widehat{\bm{L}}}&\displaystyle\frac{1}{m}\sum_{\ell=1}^{m}\Big{\\{}\frac{1}{\sigma^{2}}\|{\bm{z}}_{\ell}-{\bm{y}}_{\ell}\|_{2}^{2}+{\bm{z}}_{\ell}^{\top}\widehat{\bm{L}}{\bm{z}}_{\ell}\Big{\\}}\\\
\text{s.t.}&{\rm
Tr}(\widehat{\bm{L}})=n,~{}\widehat{L}_{ji}=\widehat{L}_{ij}\leq 0,~{}i\neq
j,~{}\widehat{\bm{L}}{\bf 1}={\bm{0}},\end{array}$ (25)

where we have used the graph quadratic form,
${\bm{z}}_{\ell}^{\top}\widehat{\bm{L}}{\bm{z}}_{\ell}$, to regulate the
smoothness of ${\bm{z}}_{\ell}\approx{\bm{y}}_{\ell}$ with respect to the
fitted $\widehat{\bm{L}}$. Dong et al. [21] motivated (25) as a maximum-a-
posterior (MAP) estimator for the Laplacian matrix, where
${\bm{y}}_{\ell}\sim{\mathcal{}N}({\bm{0}},{\bm{L}}^{\dagger}+\sigma^{2}{\bm{I}})$
and ${\bm{L}}^{\dagger}$ is the pseudo-inverse of the Laplacian matrix. This
amounts to interpreting the data as outcomes of a Gaussian Markov Random Field
(GMRF) with precision matrix chosen as the Laplacian, effectively connecting
statistical graphical models to GSP models. Note that methods following
similar insights as (25) can be found in [22, 23].

For graph signals that are output from low-pass graph temporal filters, a
similar smoothness property to (24) can also be exploited to interpolate
missing data. Let $\bm{Y}\in\mathbb{R}^{n\times m}$ be a matrix whose columns
are $\bm{y}_{t},t=1,2,\dots m$, where ${\bm{y}}_{t}$ is the graph signal at
time $t$; and ${\bm{Y}}^{\sf samp}$ be the sampled version of ${\bm{Y}}$ where
some values are missing at different node/time indices. The key for
interpolating the data is to regularize via graph quadratic form and
$\ell_{2}$ norm of the time derivative in addition to minimizing the
$\ell_{2}$ misfit between available samples $\bm{Y}^{\sf samp}$ and
reconstructed samples at known locations, $\mathcal{M}(\bm{Y})$, i.e.,

$\begin{split}\min_{\bm{Y}\in\mathbb{R}^{n\times
m}}&\left\|\mathcal{M}(\bm{Y})-\bm{Y}^{\sf samp}\right\|_{F}^{2}\\\
&+\gamma\,\Big{\\{}\sum_{\ell=1}^{m}{\bm{y}}_{\ell}^{\top}{\bm{L}}{\bm{y}}_{\ell}+\sum_{\ell=2}^{m}\|{\bm{y}}_{\ell}-{\bm{y}}_{\ell-1}\|_{2}^{2}\Big{\\}}.\end{split}$

See [24] and the references therein for a detailed discussion.

###  IV-C Anomalies Detection with Low-pass GSP

Consider a model consistent with (17). The fact that the low-pass graph
process is dominated by low graph frequency components can be considered the
null-hypothesis characterized by the low-pass properties, such as low-rank
covariance matrix and smoothness. On the other hand, many anomalies can be
modeled as an additive _sparse noise_ signal ${\bm{w}}_{i}$, or a _high
frequency_ graph signal. Such noise signals arise in several scenarios such as
a change in the graph connectivity or parameters, a contingency in
infrastructures, the result of malicious activities in social networks, or the
sudden fall in the market value of a financial entity. High frequency noise
signals are also produced by a perturbation that is inconsistent with the
generative model. For instance, in infrastructure networks this could be
symptomatic of malfunctioning sensors or even a false data injection attack
(FDIA)[25].

Such anomalies cause a surge in the high frequency spectral components of a
low-pass graph signal, a fact that can be leveraged in a manner similar to the
classical array processing problem of detecting a source embedded in noise.

[0cm 4.75cm](a) |  |  [0cm 4.75cm](b) |
---|---|---|---
Figure 5: (a) Magnitude of graph Fourier transform of the output after ideal
high-pass filtering, $\lvert\bm{U}^{T}{\mathcal{}H}_{\sf
HPF}({\bm{L}})\bm{y}_{\ell}\rvert$, $k=1200$, under the hypotheses of anomaly
$\mathcal{A}_{1}$ and no anomaly $\mathcal{A}_{0}$. Particular example of FDIA
on voltage graph signal $\bm{y}_{\ell}$ from ACTIVSg2000 case is shown. We see
a surge in high frequency components when there is an attack. (b) Spatial
difference filtering of the graph signal under a diffusion model with abnormal
activities on 11 nodes; the top figure shows the ground truth locations of
anomalies, middle and bottom figures show the graph signal $\bm{y}_{\ell}$ and
filtered graph signal, ${\mathcal{}H}_{\sf SD}({\bm{L}})\bm{y}_{\ell}$,
respectively.

Formally, the observed signal under null and alternative hypothesis is
described as

${\bm{y}}_{\ell}=\begin{cases}{\mathcal{}H}({\bm{L}}){\bm{x}}_{\ell},&~{}~{}\text{under}~{}{\mathcal{}A}_{0},\\\
{\mathcal{}H}({\bm{L}}){\bm{x}}_{\ell}+{\bm{w}}_{\ell}&~{}~{}\text{under}~{}{\mathcal{}A}_{1},\end{cases}$

where ${\bm{w}}_{\ell}$ is a high frequency graph signal. Our task amounts to
testing the hypothesis ${\mathcal{}A}_{0}$, ${\mathcal{}A}_{1}$, and/or to
estimate the locations of non-zeros in ${\bm{w}}_{i}$ when the latter is a
sparse signal and under ${\mathcal{}A}_{1}$.

Intuitively, we can apply a high-pass graph filter to distinguish between
${\mathcal{}A}_{0}$ and ${\mathcal{}A}_{1}$. Let ${\mathcal{}H}_{\sf
HPF}({\bm{L}})$ be an ideal high-pass graph filter with the frequency response
$h_{\sf HPF}({\lambda})=1$, $\lambda\geq\lambda_{k+1}$ and $0$ otherwise.
Consider the test statistics as $\Gamma_{\ell}=\|{\mathcal{}H}_{\sf
HPF}({\bm{L}}){\bm{y}}_{\ell}\|$. Under ${\mathcal{}A}_{0}$ and the $k$-low-
pass assumption, we have $\Gamma_{\ell}\leq\|{\mathcal{}H}_{\sf
HPF}({\bm{L}}){\mathcal{}H}({\bm{L}})\|_{2}\|{\bm{x}}_{\ell}\|=\|h_{\sf
HPF}(\bm{\lambda})\odot
h(\bm{\lambda})\|_{\infty}\|{\bm{x}}_{\ell}\|={\mathcal{}O}(\eta_{k})$, and
thus the test statistics $\Gamma_{\ell}$ will be small. On the other hand,
under ${\mathcal{}A}_{1}$, we obtain ${\mathcal{}H}_{\sf
HPF}({\bm{L}}){\bm{y}}_{\ell}\approx{\bm{w}}_{\ell}$ since the anomalies
consist of high graph frequency components. Thus the test statistics
$\Gamma_{\ell}$ will be large. Imposing a threshold of
$\delta=\Theta(\eta_{k})$, we can consider the detector

$\Gamma_{\ell}=\|{\mathcal{}H}_{\sf
HPF}({\bm{L}}){\bm{y}}_{\ell}\|\underset{{\mathcal{}A}_{1}}{\overset{{\mathcal{}A}_{0}}{\lessgtr}}\delta.$

Furthermore, if ${\mathcal{}A}_{1}$ holds, these anomaly events can be located
from the support of ${\mathcal{}H}_{\sf HPF}({\bm{L}}){\bm{y}}_{\ell}$.

As a demonstration, Fig. 5 (a) shows the magnitude of GFT of the voltage graph
signal after filtering using an ideal high-pass graph filter,
$\bm{U}^{\top}{\mathcal{}H}_{\sf HPF}({\bm{L}}){\bm{y}}_{\ell}$. The voltage
graph signal under the hypothesis of no anomaly is the output of a low-pass
graph filter. When there is a FDIA, we observe an increase in energy of the
high frequency components.

To obtain a simple implementation of high-pass graph filters, we may consider
${\mathcal{}H}_{\sf SD}({\bm{L}})={\bm{L}}={\bm{D}}-{\bm{A}}$ whose frequency
response is given by $h({\lambda})={\lambda}$. When applied on a graph signal
${\bm{y}}_{\ell}$, we will observe the difference between
${\bm{D}}{\bm{y}}_{\ell}$ and ${\bm{A}}{\bm{y}}_{\ell}$, where the latter is a
one-hop averaged version of ${\bm{y}}_{\ell}$. We call this operation the
spatial difference which is similar to the method proposed in [26] for anomaly
detection on social networks. See the illustration in Fig. 5 (b).

##  V Concluding Remarks

In this user guide, we highlighted the key elements of low-pass GSP in several
applications like graph parameter inference and graph signal sampling while
emphasizing the intuition from time series analysis. We also discussed several
physical models where low-pass GSP can be effectively used. However, the tools
available for low-pass GSP are ever-expanding, and aid the discovery of new
physical models where low-pass GSP can be applied. Additionally, there are
several open research directions as discussed below.

#### Directed Graphs

Throughout this article, we have assumed that the observed data is supported
on a graph topology which is undirected, and the shift operator (Laplacian
matrix) is symmetric. This is clearly not a truthful model for a lot of real
systems such as social and economics networks. The challenge of extending the
existing GSP tools to directed graphs lies in defining the appropriate GFT
basis. For instance, the properties of a circular shift matrix is what a
directed shift operator should emulate.

Much of the prior research has focused on finding the appropriate GFT basis on
directed graphs. The definition of frequency is again variational, but based
on the norm of the difference between and vector and the shift operator
$\bm{S}$ of the corresponding graph does not have to be symmetric. More
formally, the idea of smoothness is defined as
$\|\bm{x}-\lambda_{n}^{-1}\bm{S}\bm{x}\|_{2}^{2}$ where $\lambda_{n}$ is the
maximum eigenvalue of $\bm{S}$. This is the definition used in [4] for GFT on
directed graphs, where the GSO is set as the adjacency matrix $\bm{A}$ and the
GFT is defined as $\widetilde{\bm{y}}={\bf U}^{-1}{\bm{y}}$ such that ${\bf
U}$ is obtained from the Jordan decomposition of the adjacency matrix
${\bm{A}}={\bf U}\bm{\Lambda}{\bf U}^{-1}$. Although ${\bf U}$ is a basis, it
is not orthogonal, so the Parseval’s identity does not hold since
$\|\widetilde{\bm{y}}\|_{2}\neq\|{\bm{y}}\|_{2}$. That is not surprising since
the norm of $\widetilde{\bm{y}}$ does not have the same physical
interpretation of power spectral density that applies to signals whose support
is time. A potential fix is studied in [27] which searches for the GFT basis
that minimizes the directed total variation, also see [28]. Unfortunately the
GFT basis does not admit a closed form solution.

The tools discussed in this article, such as sampling theory [18] and anomaly
detection may still work for low-pass graph signals on directed graphs with
minor adjustments. The challenge lies in the graph inference/learning methods
since second-order statistics such as correlations are difficult to justify in
directed graphs, where also the notion of _community_ is ambiguous. A useful
definition of community must first be studied before tools of GSP can be
applied for community inference in directed graphs.

#### Low-pass Graph Signals in the Edge Space

An alternative form of graph signals are those that are defined on the edges.
They can be defined as the function $f:{\mathcal{}E}\rightarrow\mathbb{R}$ and
the equivalent vector ${\bm{f}}\in\mathbb{R}^{|{\mathcal{}E}|}$, which are
useful for describing _flows_ on graphs such as traffic in transportation
network. As suggested in [29], the shift operator can be taken as the edge
Laplacian ${\bf L}_{e}={\bf B}^{\top}{\bf B}$, where ${\bf
B}\in\mathbb{R}^{n\times|{\mathcal{}E}|}$ is the node-to-edge incidence
matrix. The null space of the edge Laplacian ${\bf L}_{e}$ corresponds to the
cyclic flow vector, which is also the eigenvector for the lowest graph
frequency $\lambda_{1}=0$. It is anticipated that a low-pass edge-graph
signal, whose energy is focused in the low graph frequencies, will consist of
mostly cyclic flows within communities. An interesting direction is to develop
a sampling theory for low-pass edge-graph signals, as well as the inference of
edge Laplacian matrix.

#### Identifying Low-pass Graph Signals

So far we have relied on domain knowledge about the data models, e.g., the
examples in Section III, to help justify various graph data as low-pass graph
signals.

For graph signals taken from an unknown system, one has to be cautious before
applying this low-pass GSP user guide. Even though _non-low-pass_ graph
processes are rarely found in a natural setting, there is a crucial need to
design tools for identifying low-pass graph signals. With known GSO, it can be
done by inspecting the GFT spectrum; with unknown GSO, the problem is related
to the joint estimation of graph process and topology; readers are referred to
[30] for recent works in this direction.

#### Acknowledgement

The authors thank the anonymous reviewers and the guest editors for their
useful feedback. This material is based upon work supported in part by, the U.
S. Army Research Laboratory and the U. S. Army Research Office under
contract/grant number W911NF2010153 and the NSF CCF-BSF: CIF: 1714672 grant.
Hoi-To Wai’s work is supported by the CUHK Direct Grant #4055135.

## References

  * [1] E. D. Kolaczyk and G. Csárdi, _Statistical analysis of network data with R_. Springer, 2014, vol. 65.
  * [2] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE Signal Processing Magazine_ , vol. 30, no. 3, pp. 83–98, 2013.
  * [3] 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.
  * [4] A. Sandryhaila and J. M. Moura, “Discrete Signal Processing on Graphs,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [5] N. Tremblay, P. Gonçalves, and P. Borgnat, “Design of Graph Filters and Filterbanks,” in _Cooperative and Graph Signal Processing_. Elsevier, 2018, pp. 299–324.
  * [6] H.-T. Wai, S. Segarra, A. E. Ozdaglar, A. Scaglione, and A. Jadbabaie, “Blind Community Detection From Low-Rank Excitations of a Graph Filter,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 436–451, 2020.
  * [7] K. Rohe, S. Chatterjee, B. Yu _et al._ , “Spectral clustering and the high-dimensional stochastic blockmodel,” _The Annals of Statistics_ , vol. 39, no. 4, pp. 1878–1915, 2011.
  * [8] X. Ding, T. Jiang _et al._ , “Spectral distributions of adjacency and Laplacian matrices of random graphs,” _The Annals of Applied Probability_ , vol. 20, no. 6, pp. 2086–2117, 2010.
  * [9] E. Isufi, A. Loukas, A. Simonetto, and G. Leus, “Separable autoregressive moving average graph-temporal filters,” in _2016 24th European Signal Processing Conference (EUSIPCO)_. IEEE, 2016, pp. 200–204.
  * [10] 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.
  * [11] C. Ravazzi, R. Tempo, and F. Dabbene, “Learning Influence Structure in Sparse Social Networks,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 4, pp. 1976–1986, 2017.
  * [12] N. E. Friedkin, “A Formal Theory of Reflected Appraisals in the Evolution of Power,” _Administrative Science Quarterly_ , vol. 56, no. 4, pp. 501–529, 2011.
  * [13] O. Candogan, K. Bimpikis, and A. Ozdaglar, “Optimal Pricing in Networks with Externalities,” _Operations Research_ , vol. 60, no. 4, pp. 883–905, 2012\.
  * [14] M. Billio, M. Getmansky, A. W. Lo, and L. Pelizzon, “Econometric measures of connectedness and systemic risk in the finance and insurance sectors,” _Journal of financial economics_ , vol. 104, no. 3, pp. 535–559, 2012.
  * [15] R. N. Mantegna and H. E. Stanley, _Introduction to econophysics: correlations and complexity in finance_. Cambridge university press, 1999.
  * [16] J. D. Glover, M. Sarma, and T. Overbye, “Power System Analysis and Design,” _Cengage Learning_ , vol. 4, 2008.
  * [17] R. Ramakrishna and A. Scaglione, “On Modeling Voltage Phasor Measurements as Graph Signals,” in _2019 IEEE Data Science Workshop, DSW 2019_. Institute of Electrical and Electronics Engineers Inc., 2019, pp. 275–279.
  * [18] S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, “Discrete Signal Processing on Graphs: Sampling Theory,” _IEEE Transactions on Signal Processing_ , vol. 63, no. 24, pp. 6510–6523, 2015.
  * [19] A. Anis, A. Gadde, and A. Ortega, “Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 14, pp. 3775–3789, 2016.
  * [20] M. Tsitsvero, S. Barbarossa, and P. Di Lorenzo, “Signals on graphs: Uncertainty Principle and Sampling,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 18, pp. 4845–4860, 2016.
  * [21] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning Laplacian Matrix in Smooth Graph Signal Representations,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 23, pp. 6160–6173, 2016.
  * [22] V. Kalofolias, “How to Learn a Graph from Smooth Signals,” in _Artificial Intelligence and Statistics_ , 2016, pp. 920–929.
  * [23] B. Pasdeloup, V. Gripon, G. Mercier, D. Pastor, and M. G. Rabbat, “Characterization and Inference of Graph Diffusion Processes From Observations of Stationary Signals,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 4, no. 3, pp. 481–496, 2017.
  * [24] F. Grassi, A. Loukas, N. Perraudin, and B. Ricaud, “A Time-Vertex Signal Processing Framework: Scalable Processing and Meaningful Representations for Time-Series on Graphs,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 3, pp. 817–829, 2017.
  * [25] R. Ramakrishna and A. Scaglione, “Detection of False Data Injection Attack using Graph Signal Processing for the Power Grid,” in _2019 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_. Institute of Electrical and Electronics Engineers Inc., 2019, pp. 1–5.
  * [26] H.-T. Wai, A. E. Ozdaglar, and A. Scaglione, “Identifying Susceptible Agents in Time Varying Opinion Dynamics Through Compressive Measurements,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 4114–4118.
  * [27] S. Sardellitti, S. Barbarossa, and P. Di Lorenzo, “On the Graph Fourier Transform for Directed Graphs,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 11, no. 6, pp. 796–811, 2017.
  * [28] R. Shafipour, A. Khodabakhsh, G. Mateos, and E. Nikolova, “A Directed Graph Fourier Transform With Spread Frequency Components,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 4, pp. 946–960, 2018.
  * [29] M. T. Schaub and S. Segarra, “Flow smoothing and denoising: graph signal processing in the edge-space,” in _2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_. IEEE, 2018, pp. 735–739.
  * [30] V. N. Ioannidis, Y. Shen, and G. B. Giannakis, “Semi-Blind Inference of Topologies and Dynamical Processes Over Dynamic Graphs,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 9, pp. 2263–2274, 2019.