# To further understand graph signals

Feng Ji, Wee Peng Tay The authors are with the School of Electrical and
Electronic Engineering, Nanyang Technological University, 639798, Singapore
(e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph signal processing (GSP) is a framework to analyze and process graph-
structured data. Many research works focus on developing tools such as Graph
Fourier transforms (GFT), filters, and neural network models to handle graph
signals. Such approaches have successfully taken care of “signal processing”
in many circumstances. In this paper, we want to put emphasis on “graph
signals” themselves. Although there are characterizations of graph signals
using the notion of bandwidth derived from GFT, we want to argue here that
graph signals may contain hidden geometric information of the network,
independent of (graph) Fourier theories. We shall provide a framework to
understand such information, and demonstrate how new knowledge on “graph
signals” can help with “signal processing”.

###### Index Terms:

Graph signal processing, signal types, smooth graph signals

##  I Introduction

Since its emergence, the theory and applications of graph signal processing
(GSP) have rapidly developed [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]. Many
different aspects of GSP have been explored. GSP is based on the choice of a
graph shift operator (GSO), and the cornerstone of GSP is _graph Fourier
transform_ defined using the GSO [1, 2]. This allows us to introduce
_frequency domain_ , analogous to the classical Fourier theory. A well-studied
topic in GSP is the _theory of filtering_ [2, 11]. Graph filters are
fundamental tools to analyze and process graph signals. Many important topics
stem from the theory of filtering, including _sampling theory_ [14, 15, 16,
17, 18] and _graph neural networks_ [7, 8]. The article [11] contains a
comprehensive overview that also discusses many other related topics such as
signal reconstruction, graph learning, and applications of GSP.

Suppose a graph $G$ is of size $n$. According to the definition, a graph
signal $f$ is a vector in $\mathbb{R}^{n}$, with each component corresponding
to a node of the graph. There is no reasonable interpretation of $f$ without
the graph $G$. The above-mentioned works take care of the “signal processing”
aspect of GSP, by leveraging the fundamental assumption that the signal value
should be close to each other at any pair of nodes connected by an edge. From
here, we see that the property of the signal $f$ with respective to (w.r.t.)
the graph $G$ plays a central role. Motivated by such a consideration, in this
paper, we focus solely on the “graph signal” aspect of GSP. To be more
precise, we want to describe how we may quantify the notion of “smoothness” of
graph signals. Based on such a notion, we can give a characterization of graph
signals. To do so, we want to dig out hidden geometric information contained
in graph signals and compare such information with the geometry of the given
graph.

Classically, many research works rely on the notion of bandlimitedness [18,
19, 20, 21, 22] to characterize graph signals, with tasks ranging from
sampling, and signal reconstruction to topology learning. A signal with small
bandwidths is considered to be smooth. However, it is arguable whether such
consideration is most appropriate or not. For example, in the first place,
bandlimitedness does not only depend on the graph but also relies heavily on
the choice of the GSO, for which we have quite a few candidates. Moreover, for
most of the common choices of GSO, smooth signals are those whose values are
close to each other at any pair of nodes connected by an edge, as we described
earlier. However, signal values between nodes further away are not directly
compared. The approach taken in our paper shall address such shortcomings.

To set a few humble goals, we want to:

  * •

Develop new methods to identify hidden geometric information of graph signals.

  * •

Use these methods to explicitly define the smoothness of graph signals.

  * •

Classify graph signals based on the new notion of smoothness.

  * •

Investigate new insights into GSP by combining a new understanding of graph
signals with classical GSP tools.

Each of these goals is fully explored in a section of the paper, and the rest
of the paper is organized as follows. We motivate our goals and approach in
Section II. We realize that asides from being either smooth or noisy, a graph
signal can have other characterizations that agree with neither. For example,
as we demonstrate with an example, a signal can look noisy but contains
important geometric information. We coin the term “perpendicular signal” for
such a signal. To understand perpendicular signals, we propose to take an
indirect route and study a quantitative notion of smoothness. In Section III,
we describe the framework to compare a graph and signals by using an explicit
geometric construction. The framework us allows to formally define the
smoothness of graph signals in Section IV. We present simulation results in
Section V. The focus is to combine our investigation of signals themselves
with well-established GSP tools, to shed light on new insights into GSP
theory. We finally conclude in Section VI. All proofs are contained in the
Appendix.

##  II Graph signal types

Let $G=(V,E)$ be a finite unweighted simple graph of size $n=|V|$, where $V$
is the vertex set and $E$ is the set of edges of $G$. A _graph signal_ $f$ is
a function $f:V\to\mathbb{R}$. An equivalent interpretation is to view $f$ as
an $n$-dimensional vector, where the component corresponding to $v\in V$ is
denoted by $f(v)$. There have been numerous studies of graph signals with the
theory of graph signal processing (GSP). One of the central themes is the
study of _bandlimited graph signals_. Intuitively, the notion is a discrete
analog of its counterpart in classical Fourier theory. Such a signal is
considered to be smooth in the sense that the signal values at neighboring
nodes are close to each other. On the opposite side, we have _noises_ , whose
signal values fluctuate widely even across neighboring nodes. There are
statistical models for noises . In general, they are regarded as obstacles in
graph signal processing. In the next example, we want to discuss the
possibility of scooping up useful information from “noises”. The key
observation is that a seemingly noisy graph signal may contain geometric
information that supplements the graph structure.

######  Example 1.

Consider a helix curve (a spiral in $\mathbb{R}^{3}$ as in Fig. 1) $C$ given
by the parametric form

$\displaystyle C(t)=(x(t),y(t),z(t))=(\cos t,\sin t,t),t\in[0,5\pi].$

Assume that $n$ is chosen such that $5\nmid n-1$. We take $n$ uniformly spaced
points $V=\\{v_{1},\ldots,v_{n}\\}\subset C$ with $v_{1}=C(0)$ and
$v_{n}=C(5\pi)$. The set $V$ together with their connections on $C$ gives rise
to the path graph $P$ with $n$ nodes. On the other hand, we may equivalently
encode all information in a different graph $G$ and a signal $f$ as follows.

We apply the projection $p$ of $V$ to the $(x,y)$-plane. Based on their
proximity on the unit circle, we have a cycle graph $G$ on $n$-nodes
$u_{i}=p(v_{i}),1\leq i\leq n$. The condition $5\nmid n-1$ ensures $u_{i}\neq
u_{j}$ for $i\neq j$. We construct a graph signal $f$ on $G$ such that
$f(u_{i})$ is the height of $v_{i}$, i.e., $f(u_{i})=5(i-1)\pi/(n-1)$. As $C$
spirals multiple rounds, there are nodes close to each other on $G$ whose $f$
values differ much. Hence, $f$ resembles a noise. However, if we disregard the
geometric information contained in $f$, we may have a wrong interpretation of
both $G$ and $f$. In such cases, applying GSP tools to $f$ viewed as a signal
on $G$ becomes inappropriate. However, $G$ and $f$ combined do contain full
information about the original setup. Moreover, we observe that $f$ is placed
in the direction _perpendicular_ to $G$.

Fig. 1: The helix curve.

To give more intuitions, we discuss two different ways to interpret graph
signals. Classically, one chooses a graph shift operator (GSO) $A$ and
constructs a filter bank from it, such as the convolution filters, and band-
pass filters. Given a graph $G=(V,E)$ and a signal $f$, one applies filters
from a filter bank to $f$, for analysis purposes. This is the _function point
of view_ of graph signals, namely we study properties of $f$ using the
geometry of $G$ encoded in $A$.

On the other hand, we may also consider the _geometric point of view_ of graph
signals. Namely, we view $f$ as mapping the nodes $V$ into $\mathbb{R}$. This
should provide additional geometric information of $V$ other than that
contained in $E$. In particular, if such additional information is not
coherent w.r.t. that of $E$ (e.g., Example 1), applying filters constructed
from $G$ to analyze $f$ becomes inappropriate.

The function point of view focuses on understanding graph signals. We should
expect that the function point of view gives a more accurate understanding
provided that the structure of $G$ is more accurate. On the other hand, the
geometric point of view provides us with a means to enhance our knowledge of
the graph structure. In summary, we want to explore geometric information
contained in graph signals as a central theme.

By Example 1, we see describing non-smooth graph signals as noise can cause
information loss. The seemingly noisy signal in the example is in the
perpendicular direction to the planar embedding of the graph. This prompts us
to introduce the notion of perpendicular graph signals.

######  Definition 1.

Let $S$ be a subset of graph signals. Then the space of _perpendicular graph
signals w.r.t. $S$_ is the orthogonal complement $S^{\perp}$ of $S$.

Though we have a seemingly naive notion here, the real point is that the set
$S$ contains those signals coherent with the graph structure, such that it
makes sense to analyze them with current GSP techniques. Such a signal is
considered as “smooth”, which will be made explicit in Section IV. On the
other hand, a signal $f$ in $S^{\perp}$ contains geometric information
“perpendicular” to that offered by $G$ (c.f. Example 1). Hence, we may
consider using $f$ to enhance our understanding of $G$, instead of processing
it with filters built from $G$. According to Definition 1, smooth signals and
perpendicular signals are the two sides of the same coin. Our strategy is to
focus on the former explicitly in Section IV.

We end this section by providing further intuitions and heuristics. We
describe some major challenges to “compare the geometry of graph and signal”,
which motivate subsequent sections.

To proceed, we introduce a notion here. Suppose $f=(f_{i})_{1\leq i\leq
n},g=(g_{i})_{1\leq i\leq n}\in\mathbb{R}^{n}$. For convenience, the notation
is only used till the end of this subsection. We say that $f$ _interlaces_ $g$
if there is a constant $c$ such that $h=f+c$ satisfies $g_{i}\leq h_{i}\leq
g_{i+1}$ for $1\leq i\leq n-1$, $h_{n}\geq g_{n}$ and
$h_{1}g_{1}+h_{n}g_{n}\geq 0$. Notice that the last condition loosely controls
the absolute values of $g_{1}$ and $h_{n}$.

######  Lemma 1.

For $n\geq 3$, suppose $f,g\in\mathbb{R}^{n}$ are nonzero vectors and $g$ is
orthogonal to constant vectors. If a re-arrangement of indices makes $f$
interlace $g$, then $f$ and $g$ are not orthogonal to each other.

Let us try to interpret “$f$ interlaces $g$” geometrically. According to the
definition, the increments in the signal values $f_{i+1}-f_{i}$ are controlled
by those of $g$. In particular, if the increments are small for $g$, so are
those for $f$. On the other hand, if $f$ does not interlace $g$, then we can
observe large increments for $f$ can occur when we have a small increment in
$g$. In the GSP setting, one argues heuristically that a smooth signal is the
one that has a small increment across many direct edges. Therefore, if we have
a set $S$ exhausts smooth signals, then any $f$ perpendicular to $S$ does not
interlace any of the signals in $S$. Based on our discussions, such $f$ tends
to violate having small increments along a direct edge for many different
edges.

However, to make our discussion rigorous, we need to specify what we mean by a
signal being smooth, aside from the hand-waving description as above. The main
challenge is that signals and graphs are different mathematical objects.
Therefore, they are not directly comparable. Our key task is to set-up a
common platform so that we can discuss the geometric contents of both graphs
and signals and make comparisons.

##  III Graph-signal coupling

As we have pointed out in the previous section, a graph signal can contain
geometric information not captured by the graph. In this section, we shall
discuss a framework, called _graph-signal coupling_ , to extract geometric
information from graphs and signals combined.

###  III-A An axiomatic approach

We want to first propose an axiomatic approach to avoid restricting to a
single construction, while we still give an explicit construction in the next
subsection. The axiomatic approach proceeds by stating a few desired
properties any construction needs to satisfy. We start by motivating such
properties.

Recall that we want to find a “common platform” to compare graphs and signals.
More specifically, let $\mathcal{S}$ be a set of objects having geometric
interpretation. For example, $\mathcal{S}$ can be the set of graphs or the set
of finite (pseudo) metric spaces (recall in a pseudo metric space, $d(x,y)=0$
does not imply $x=y$). Suppose $F=\\{f_{1},\ldots,f_{m}\\}$ contains a finite
set of signals on $G$. We want to produce an object $G_{F}\in\mathcal{S}$.

First of all, we _need a notion of equivalence_ between objects in
$\mathcal{S}$, and the reason is as follows. Suppose $G_{1}$ and $G_{2}$ are
isomorphic graphs by a permutation $\sigma$ of the nodes. For $F_{1}$ on
$G_{1}$, permuting (with $\sigma$) the indices of each signal in $F_{1}$
results a set of signals $F_{2}=\sigma(F_{1})$. The objects ${G_{1}}_{F_{1}}$
may not be the same as ${G_{2}}_{F_{2}}$, but they should be equivalent.

The coupling should be extendable to pairs $G_{F_{1}}\in\mathcal{S}$ and
$F_{2}$, where both $F_{1}$ and $F_{2}$ are finite sets of signals on $G$.
More precisely, we want to have an object $(G_{F_{1}})_{F_{2}}\in\mathcal{S}$.
This is because regarded as observations, the signals $F_{1}$ and $F_{2}$ may
not be obtained simultaneously. Moreover, we also want that
$G_{F}\in\mathcal{S}$ allows us to recover both the graph and signals to a
certain extent.

Keeping these requirements in mind, we now formalize the idea of graph-signal
coupling.

######  Definition 2.

Let $\mathcal{G}$ be the set of graphs. A _graph-signal coupling_ consists of
the following data: a set of objects $\mathcal{S}$ and an equivalence relation
“$\sim$” on $\mathcal{S}$. For each graph $G$ and a finite set of signals $F$,
there is a $G_{F}\in\mathcal{S}$ (if $F=\\{f\\}$, we write $G_{f}$ for $G_{F}$
for convenience) such that the following holds:

  1. 1)

Composability: For each finite set of signals $F^{\prime}$, there is
$(G_{F})_{F^{\prime}}\in\mathcal{S}$.

  2. 2)

Commutativity and associativity: $(G_{F})_{F^{\prime}}\sim G_{F\cup
F^{\prime}}$.

  3. 3)

Recoverability of $G$: There is _base map_ $b:\mathcal{S}\to\mathcal{G}$ such
that $b(G_{F})=G$.

  4. 4)

Recoverability of signal: $G_{f}=G_{f^{\prime}}$ implies
$|f(v_{i})-f(v_{j})|=|f^{\prime}(v_{i})-f^{\prime}(v_{j})|,1\leq i,j\leq n$.
Moreover, if $f=af^{\prime}+c$ for scalar $a\neq 0$ and constant signal $c$,
then $G_{f}\sim G_{f^{\prime}}$.

Before presenting an explicit construction in Section III-B, we analyze the
obvious choice of $\mathcal{S}$ being the collection of graphs. This means for
a graph $G$ and a finite set of signals $F$, we need to produce a new graph
$G_{F}$. In the collection of graphs, the most reasonable notion of
equivalence is graph isomorphism. Two isomorphic graphs are essentially the
same up to a re-ordering of vertices. In addition, for any $G$ and a constant
signal $c$, it is reasonable to require $G_{c}$ isomorphic to $G$. Consider
any signal $f$. Condition 2 forces $(G_{f})_{f}$ isomorphic to $G_{f}$. The
latter in turn is isomorphic to $(G_{f})_{c}$ for any constant signal. This
means that on the graph $G_{f}$, we are not able to differentiate $f$ from any
constant signal, i.e, the recoverability of signals is violated.

If we examine the above argument, we notice that the cause of the problem is
that equivalence on our current choice of $\mathcal{S}$ is too restrictive. As
a remedy, we shall consider that $\mathcal{S}$ contains a parametrized family
of graphs in Section III-B.

###  III-B An explicit construction

In this subsection, we give an explicit construction that verifies the
properties listed in Definition 2. The construction is inspired by the basic
construction in linear algebra: taking the sum of perpendicular vectors.

In the construction, an object in $\mathcal{S}$ is a parametrized family of
graphs. More precisely, it is a map $\gamma:M\to\mathcal{G}$, where $M$ is a
parameter space such as a topological space or a manifold, and $\mathcal{G}$
is the collection of finite graphs. For convenience, we use $\gamma$ to denote
such an object.

Given $\gamma_{i}:M_{i}\to\mathcal{G},i=1,2$, a _morphism_ from $\gamma_{1}$
to $\gamma_{2}$ is a map $\phi:M_{1}\to M_{2}$ such that
$\gamma_{1}=\gamma_{2}\circ\phi$ (illustrated in Fig. 2). If $M_{i}$ are
topological spaces, we usually require $\phi$ to be continuous; and if $M_{i}$
are differentiable manifolds, we want $\phi$ to be differentiable. To
understand this notion, consider $g\in Im(\gamma_{1})$, i.e.,
$g=\gamma_{1}(x)$ for $x\in M_{1}$. Then $y=\phi(x)$ satisfies
$\gamma_{2}(y)=g$. Intuitively, this indicates that $\phi$ is analogous to a
“surjection” from $\gamma_{2}$ to $\gamma_{1}$, though we notice a reverse of
domain and codomain. Now we proceed to define the equivalence relation.

Fig. 2: Schematic diagram of a morphism.

######  Definition 3.

Given $\gamma_{1},\gamma_{2}$, we write $\gamma_{1}\leq\gamma_{2}$ if there is
a morphism $\phi$ from $\gamma_{1}$ to $\gamma_{2}$. We say $\gamma_{1}$ and
$\gamma_{2}$ are equivalent to each other, denoted by
$\gamma_{1}\sim\gamma_{2}$ if $\gamma_{1}\leq\gamma_{2}$ and
$\gamma_{2}\leq\gamma_{1}$.

The equivalence is based on the analogy that two finite sets are equivalent to
each other if either surjects onto the other.

We can now define $G_{F}$ for given graph $G$ and a finite set of signals
$F=\\{f_{1},\ldots,f_{k}\\}$. Let $M_{F}=\mathbb{R}_{\geq 0}^{k+1}$. We write
$x=(x_{0},x_{1},\ldots,x_{k})$ for a typical element in $M_{F}$.

Then $G_{F}\in\mathcal{S}$ is a map $G_{F}:M_{F}\to\mathcal{G}$ defined
by111The construction is inspired by the idea of [23] Definition 2.5.

  1. 1)

For two nodes $u,v$, compute

$\displaystyle\Delta(u,v)=\Big{(}\sum_{1\leq i\leq
k}x_{i}(f_{i}(u)-f_{i}(v))^{2}+d_{G}(u,v)^{2}\Big{)}^{1/2},$

where $d_{G}$ is the distance on $G$.

  2. 2)

In $G_{F}(x)$, a pair of nodes $u,v$ is connected by an edge if
$\Delta(u,v)\leq x_{0}$.

Intuitively, $x_{i},1\leq i\leq k$ scales the difference measured by the
signal $f_{i}$. The parameter $x_{0}$ is a threshold to determine the
connections in $G_{F}(x)$. Of course, we need to check the following.

Fig. 3: In this example, $G$ is the path graph on $3$ nodes, and the signal
$f$ is $(0,2,1)^{T}$. As shown below, $G_{f}$ is the parameter family of
graphs. There are two parameters $(x_{0},x_{1})$. The parameter $x_{1}$ scales
signal differences and $x_{0}$ serves as a threshold to determine edge
connections.

######  Theorem 1.

Associating $G,F$ with $G_{F}:M_{F}\to\mathcal{G}$ is a graph-signal coupling.

###  III-C The abstract picture

In this section, we give a more abstract description of the picture, to
explain the theoretical underpinning of our approach.

Let $\mathcal{G}_{n}$ be the collection of unweighted, undirected finite
graphs on $n$ vertices. We start with an object $G$ in this collection. On the
other hand, we want to study signals on such a graph $G$. The collection of
such signals can be identified with $\mathbb{R}^{n}$, denoted by
$\mathcal{F}_{n}$. As we propose in this paper, we want to investigate
geometric information contained in a signal $f\in\mathbb{R}^{n}$. While a
direct comparison of $f$ and $G$ is obscure as they belong to different
collections of objects, we want a common, new collection of objects that
enlarges both $\mathcal{G}_{n}$ and $\mathcal{F}_{n}$.

######  Proposition 1.

Introduce

  * •

$\mathcal{M}_{n}$: the collection of metric spaces of size $n$;

  * •

$\mathcal{MG}_{n}$: the collection of map $\phi:M\to\mathcal{G}_{n}$, i.e., as
a parametrized family of graphs, by a topological space $M$ such that
$Im(\phi)$ is finite; and

  * •

$\mathcal{SG}_{n}$: the collection of a finite sequence of undirected,
unweighted graphs of size $n$.

Then we have the diagram of maps as shown in Fig. 4

Fig. 4: The schematic illustration of Proposition 1.

such that
$\tau_{4}\circ\tau_{3}\circ\tau_{2}\circ\tau_{1}=Id_{\mathcal{G}_{n}}$,
$\tau_{2}\circ\tau_{1}(G)=G_{c}$ for any constant signal $c$. Moreover, if
$\tau_{5}(f)=\tau_{5}(g)$, then $f=g+c$ or $f=-g+c$ for some constant signal
$c$.

As a consequence, we have placed both graphs and signals in the common
collections $\mathcal{MG}_{n}$ and $\mathcal{SG}_{n}$, where we can compare
them directly.

##  IV Smooth graph signal

We have introduced perpendicular signals earlier, which contain additional
geometric information. It is supposed to come together with the notion of
smooth signals, which we formally define in this section. The main idea is
that we make use of the constructions of Section III to place both graph and a
signal in a common collection of objects and make comparisons based on an
appropriate measure defined on the collection. The first goal is to introduce
such a measure.

Let $*$ be the trivial graph on a single node. We also view it as a degenerate
graph on $n$ nodes by identifying all of them with the single node, i.e., the
distance between any pair of nodes is $0$. On the other hand, on the graph
$G$, let $c$ be the unit constant signal.

Recall that according to Section III, we have defined $*_{f}$ and $G_{c}$ as
objects in some collection $\mathcal{S}$. By Proposition 1, $\mathcal{S}$ can
be either the collection of a parameterized family of graphs or the collection
of a finite sequence of graphs.

######  Definition 4.

Assume that there is
$d_{\mathcal{S}}:\mathcal{S}\times\mathcal{S}\to\mathbb{R}_{\geq 0}$. Then for
$\epsilon\geq 0$, a graph signal $f$ on $G$ is called $\epsilon$-smooth
(w.r.t, $d_{\mathcal{S}}$) if $d_{\mathcal{S}}(*_{f},G_{c})\leq\epsilon$.

As we pointed out earlier, we want $d_{\mathcal{S}}$ to play the role of a
metric to measure how different two elements of $\mathcal{S}$ are. However,
the $d_{\mathcal{S}}$ we are going to define does not satisfy all the
properties of a metric such as being symmetric.

We now describe an explicit construction of $d_{\mathcal{S}}$ based on our
choice of $\mathcal{S}$ and construction of $G_{F}$. We only consider elements
of $\mathcal{S}$ taking the form of $G_{F}$ (cf. Section III). Recall that for
two unweighted graphs $G_{1}$ and $G_{2}$ on the same amount of $n$ vertices,
their _Hamming distance_ $d_{H}(G_{1},G_{2})$ counts the number of edges
contained exclusively in either $G_{1}$ or $G_{2}$. More generally, if
$\Gamma$ is a set of unweighted graphs on $n$ vertices, then

$\displaystyle d_{H}(G_{1},\Gamma)=\min_{G_{2}\in\Gamma}d_{H}(G_{1},G_{2}).$

For $G$ of size $n$ and a finite set of graph signals $F$, we have constructed
$G_{F}:M_{F}\to\mathcal{G}$ such that $M_{F}$ is a subset of a Euclidean
space. The image $Im(G_{F})$ is finite. An extreme case in $Im(G_{F})$ is the
the complete graph $K_{n}$, and write $Im(G_{F})^{\circ}$ for
$Im(G_{F})\backslash\\{K_{n}\\}$. Let the inverse image of $Im(G_{F})^{\circ}$
has _Lebesgue measure_ $|G_{F}^{-1}(Im(G_{F})^{\circ})|$.

Suppose $G_{1}$ and $G_{2}$ are graphs on the same set of ordered vertices $V$
and finite sets of graph signals $F_{1}$ and $F_{2}$. For convenience, denote
$\gamma_{1}={G_{1}}_{F_{1}}$ and $\gamma_{2}={G_{2}}_{F_{2}}$. If
$Im(\gamma_{1})^{\circ}$ is non-empty define

$\displaystyle d_{\mathcal{S}}(\gamma_{1},\gamma_{2})=\sum_{G\in
Im(\gamma_{1})^{\circ}}\frac{|\gamma_{1}^{-1}(G)|}{|\gamma_{1}^{-1}(Im(\gamma_{1})^{\circ})|}d_{H}(G,Im(\gamma_{2})),$
(1)

where $|\cdot|$ denotes the Lebesgue measure of the set. If
$Im(\gamma_{1})^{\circ}=\emptyset$, then
$d_{\mathcal{S}}(\gamma_{1},\gamma_{2})=0$. An illustration is shown in Fig.
5.

Fig. 5: In this example, $G$ is a graph on $4$ nodes. In the top row, we show
the image of $G_{c}$ consisting of a sequence of $3$ distinct graphs. On the
other hand, we consider an eigenbasis $\\{f_{1},f_{2},f_{3},f_{4}\\}$ of the
Laplacian of $G$. In the figure, we show the image of $*_{f_{i}},1\leq i\leq
4$ in subsequent rows. Using the formula for $d_{\mathcal{S}}(\cdot,\cdot)$,
we find that $d_{\mathcal{S}}(*_{f_{i}},G_{c}),1\leq i\leq 4$ are $0,2/3,1,3$
respectively.

We now study some basic properties of $\epsilon$-smooth signals.

######  Lemma 2.

  1. 1)

If $f$ is $\epsilon$-smooth, then so are $rf$ and $f+c$ for any
$r\in\mathbb{R}\backslash\\{0\\}$ and $c$ a constant signal.

  2. 2)

If $G$ is connected, then the set of $0$-smooth signals contains only constant
signals if and only if $G$ is not a path.

  3. 3)

The map $\mathbb{R}^{n}\to\mathbb{R},f\mapsto d_{\mathcal{S}}(*_{f},G_{c})$ is
continuous on the subset of non-constant signals.

We now discuss other means to estimate the parameter $\epsilon$ without
directly using the definition.

######  Example 2.

In this example, we re-visit Fig. 5. In particular, we want to compute
$d_{\mathcal{S}}(\gamma_{1},\gamma_{2})$ for
$\gamma_{1}=*_{\sqrt{6}f_{2}}=*_{f_{2}}$ and $\gamma_{2}=G_{c}$, without
directly using the definition. The idea here is that instead of considering
each graph of $Im(*_{f_{2}})$, we consider edges in these graphs. More
specifically, we order pairs of distinct vertices $\\{u,v\\}$ increasingly
according to $\Delta(\\{u,v\\})=|f_{2}(u)-f_{2}(v)|$. We obtain the sequence:
$Q=(Q_{1},\ldots,Q_{6}):\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\},\\{v_{3},v_{4}\\},\\{v_{1},v_{4}\\},\\{v_{2},v_{4}\\}$
with the corresponding $\Delta$ values $0,1,1,2,3,3$. We partition $Q$ into
$3$ parts: $I_{0}=(Q_{1}),I_{1}=(Q_{2},Q_{3},Q_{4})$ and
$I_{2}=(Q_{5},Q_{6})$.

Notice that in Fig. 5, we see that $Im(G_{c})$ contains $3$ graphs, and we
call them $G^{(0)}$, $G^{(1)}$ and $G^{(2)}$ respectively.

Now we process each $Q_{l},l=1,\ldots,6$ to obtain a number $\epsilon_{l}$. We
show how this is done for typical examples $Q_{1}$ and $Q_{4}$. For
$Q_{1}=\\{v_{1},v_{2}\\}$, we notice that the pair first appears as an edge in
$G^{(1)}$. We then identify the first pair of $I_{1}$ is
$Q_{2}=\\{v_{1},v_{3}\\}$. Then we compute
$\epsilon_{1}=|\Delta(Q_{1})-\Delta(Q_{2})|/\Delta(Q_{6})=1/3$. Similarly for
$Q_{4}=\\{v_{3},v_{4}\\}$, we notice that it first appears as an edge in
$G^{(1)}$ as well, and determine $Q_{2}$ being the first pair of $I_{1}$. We
then find $\epsilon_{4}=|\Delta(Q_{4})-\Delta(Q_{2})|/\Delta(Q_{6})=1/3$. The
same computation determines that
$\epsilon_{2}=\epsilon_{3}=\epsilon_{5}=\epsilon_{6}=0$. Summing all of them
we obtain $\sum_{1\leq l\leq 6}\epsilon_{6}=2/3$, which is exactly the
smoothness of $f_{2}$.

We shall next rigorously describe and then demystify the procedure.

Before formalizing the procedure in Example 2, we make the following technical
assumption on $f$: for two different pairs (as sets) of nodes
$\\{u_{1},v_{1}\\}$ and $\\{u_{2},v_{2}\\}$, we have
$|f(u_{1})-f(v_{1})|\neq|f(u_{2})-f(v_{2})|$.

For the graph $G$, let $D_{G}$ be its diameter. For each $0\leq k\leq D_{G}$,
we define $G^{(k)}$ be to the graph on $V$ and $u,v$ is connected by an edge
if and only if $d_{G}(u,v)\leq k$. This sequence of graphs $G^{(k)},0\leq
k\leq D_{G}$ is nothing but the image of $G_{c}$.

Suppose we order the distinct pairs of vertices $\\{u,v\\}$ of $V$
increasingly according to $|f(u)-f(v)|$. In this way, we obtain an ordered
sequence of pairs of vertices $Q=(Q_{l})_{1\leq l\leq n(n-1)/2}$, with
$Q_{l}=\\{u_{l},v_{l}\\}$. A _$D_{G}+1$ -partition_ $\mathcal{P}$ of
$I=\\{1,\ldots,n(n-1)/2\\}$ is a decomposition of $I=\cup_{0\leq k\leq
D_{G}}I_{k}$ into $D_{G}+1$ disjoint subsequences of consecutive numbers
$I_{k}$ in $I$. We assume that the numbers in $I_{k}$ are smaller than those
in $I_{k+1}$, and we allow $I_{k}$ to be empty. We compute
$\epsilon_{\mathcal{P}}$ as follows.

Algorithm 1

Input: $G,f,Q,\mathcal{P}$ Output: $\epsilon_{\mathcal{P}}$ of $f$

  * •

For each $1\leq l\leq n(n-1)/2$, let $k$ be the index such that
$(u_{l},v_{l})$ is an edge of $G^{(k)}$ for the first time, in the sequence
$G^{(0)},\ldots,G^{(D_{G})}$.

  * •

Let $l^{\prime}$ be first element of $I_{k}$ and
$Q_{l^{\prime}}=\\{u_{l^{\prime}},v_{l^{\prime}}\\}$.

  * •

Set

$\displaystyle\epsilon_{l}=\frac{\big{|}|f(u_{l^{\prime}})-f(v_{l^{\prime}})|-|f(u_{l})-f(v_{l})|\big{|}}{|f(u_{(n(n-1)/2)})-f(v_{n(n-1)/2})|}.$

  * •

Summing over $1\leq l\leq n(n-1)/2$,

$\displaystyle\epsilon_{\mathcal{P}}=\sum_{1\leq l\leq n(n-1)/2}\epsilon_{l}.$

The observation made in Example 2 is demystified by the following result.

######  Proposition 2.

Let $\epsilon$ be the smallest number such that $f$ is $\epsilon$-smooth. Then
$\epsilon=\min_{\mathcal{P}}\epsilon_{\mathcal{P}}$, where the minimum is
taken over all partitions $\mathcal{P}$ of $I=\\{1,\ldots,n(n-1)/2\\}$ into
$D_{G}+1$ subsequences.

Based on the proof of Proposition 2, we can describe the role played by the
partition $\mathcal{P}=\\{I_{0},\ldots,I_{D_{G}}\\}$. To compute
$\epsilon_{\mathcal{P}}$, we form the sequence of graphs $G_{(l)}$ by
including $Q_{1},\ldots,Q_{l}$ as edges. In the expression
$d_{H}(\cdot,\cdot)$, we put $G_{(l)}$ with $G^{(k)}$ as the arguments for
$l\in I_{k}$. By the proposition, any choice of $\mathcal{P}$ allows us to
obtain an upper bound of $\epsilon$. Moreover, to find the optimal partition,
we only need to find the starting and ending indices of each $I_{k},0\leq
k\leq D_{G}$. This leads to Algorithm 2 that is based on the binary search of
such indices.

Algorithm 2

Input: $G,f$ Output: $\mathcal{P}$ of $f$

  * •

Construct $G^{(k)}$ for $0\leq j\leq D_{G}$.

  * •

Form the sequence of pairs of nodes $Q=(Q_{l})_{1\leq l\leq n(n-1)/2}$ with
$Q_{l}=\\{u_{l},v_{l}\\}$ such that
$|f(u_{l})-f(v_{l})|<|f(u_{l+1})-f(v_{l+1})|$.

  * •

For any $Q_{l}$, recall $G_{(l)}$ is the graph with edges
$Q_{1},\ldots,Q_{l}$.

  * •

For each $0\leq k\leq D_{G}$, apply binary search to $Q$ to find the starting
and ending indices of $I_{k}$, with the following rule: Then $l\in I_{k}$ if
$k$ is the largest element in $\operatorname*{arg\,min}_{0\leq j\leq
D_{G}}d_{H}(G_{(l)},G^{(j)})$. Any index $l$ such that $Q_{l}$ is considered
in each iteration is used as a reference index in subsequent iterations.

To end this section, we slightly generalize Definition 4. What is missing from
the current notion of $\epsilon$-smoothness is that it is not preserved under
vector addition. Hence, in general, they do not form a vector space. This is
unfavorable in signal processing. On the other hand, Lemma 2 3 shows that if
$\epsilon>0$, in general $\epsilon$-smooth vectors span $\mathbb{R}^{n}$. To
come up with useful vector spaces, we propose the following.

######  Definition 5.

Suppose $F=\\{f_{1},\ldots,f_{n}\\}$ is an orthonormal basis of
$\mathbb{R}^{n}$. Then let $F_{\epsilon}=\\{f\in F\mid
f:\epsilon\text{-smooth}\\}$. An arbitrary signal is $\epsilon$-smooth w.r.t.
$F$ if $f$ is in the span of $F_{\epsilon}$.

If $L$ is a matrix admitting an eigenbasis, then $f$ is $\epsilon$-smooth
w.r.t. $L$ if it is $\epsilon$-smooth w.r.t. an eigenbasis of $L$.

More generally, $f$ is $\epsilon$-smooth if it is in the span of a set of
pairwise orthogonal $\epsilon$-smooth vectors.

##  V Simulations

In this section, we provide simulation results. The main focus is to
demonstrate that well-established GSP tools can be modified with our new
framework to give new insights and experimental observations.

###  V-A Band-pass filters: old wine in new bottles

In this subsection, we study band-pass filters. We first recall briefly what
they are in GSP. Let $L$ be a fixed GSO such as the Laplacian of $G$. It
admits an orthonormal eigenbasis $\mathcal{E}=\\{e_{1},\ldots,e_{n}\\}$ with
the corresponding eigenvalues
$0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$. For a subset $Y$ of
$[n]=\\{1,\ldots,n\\}$, the _band-pass filter $B_{Y}$_ on any graph signal $f$
is defined as

$\displaystyle B_{Y}(f)=\sum_{i\in Y}\langle e_{i},f\rangle e_{i},$

where $\langle\cdot,\cdot\rangle$ is the standard inner-product. The band-pass
filter retains only the components, indexed by $Y$, of the eigen-decomposition
of $f$. A slightly more general version is that we take a pair of numbers
$\bm{\alpha}=(\alpha_{0},\alpha_{1})$, and construct
$B_{Y,\bm{\alpha}}=\alpha_{0}B_{Y}+\alpha_{1}I_{n}$, with $I_{n}$ the identity
map. For example, $B_{Y}=B_{Y,\bm{\alpha}}$ for $\bm{\alpha}=(1,0)$. The
coefficients $\bm{\alpha}$ provide additional flexibility if we do not want to
completely disregard contributions from $e_{i}$ for $i\notin Y$.

In many tasks, the index set is chosen as $X_{m}=\\{1,\ldots,m\\}$ for some
$m<n$. The resulting filter is called a low-pass filter. It leverages the
intuition that structured signals are smooth in the sense that it contains
mainly “low frequency” components. Here, “low” refers to small eigenvalues. In
our paper, we provide a different interpretation of smoothness as formally
defined in Section IV. This allows us to choose an index set according to the
smoothness therein. We describe how this simple procedure is done as follows.

Algorithm 3

Input: $\mathcal{E},G,m$ Output: $Y_{m}$ of size $m$

  * •

For each $e_{i}\in\mathcal{E}$, find $\epsilon_{i}=d_{H}(*_{e_{i}},G_{c})$ for
any constant signal $c$.

  * •

Determine a permutation $\sigma$ of $1,\ldots,n$ according to increasing order
of $\epsilon_{i}$, i.e., $\epsilon_{\sigma(i)}\leq\epsilon_{\sigma(i+1)}$.

  * •

$Y_{m}=\\{\sigma(1),\ldots,\sigma(m)\\}$.

The index set $Y_{m}$ constructed in Algorithm 3 shall be used as a substitute
of $X_{m}=\\{1,\ldots,m\\}$ in classical GSP. In general, the resulting filter
$B_{Y}$ is not a low-pass filter in the classical sense. We shall demonstrate
with simulations.

We consider the MNIST dataset.222http://yann.lecun.com/exdb/mnist/ We use a
$2$D-lattice $G=(V,E)$ to model the graph for each image, and $L$ is the
Laplacian of $G$. As described above, it has an orthonormal eigenbasis
$\mathcal{E}=\\{e_{1},\ldots,e_{n}\\}$. We first compute $\epsilon_{i}$ as in
Algorithm 3, to investigate the relation between the notions of smoothness
introduced in the paper and implicitly suggested by classical GSP. In Fig. 6,
we show the plot of $\epsilon_{i}$ (normalized by the size of $G$) against
$i$. The indices on the horizontal axis are ordered according to the sizes of
the eigenvalues of $L$. Therefore, from the plot, we see that an index $i$
with small GSP frequency does not necessarily have small $\epsilon_{i}$. As a
consequence, $Y_{m}$ can be very different from the set
$X_{m}=\\{1,\ldots,m\\}$, which is used to construct a low-pass filter in
classical GSP. A low-pass filter in terms of size of $\epsilon_{i}$ is a
classic band-pass filter, but not necessarily a classical low-pass filter.

Fig. 6: The plot of $\epsilon_{i}$ against $i$, where the indices on the
horizontal axis are ordered according to the graph frequencies.

We investigate the difference between the band-pass filters with
$X_{m}=\\{1,\ldots,m\\}$ and $Y_{m}=\\{\sigma(1),\ldots,\sigma(m)\\}$ on
processing noisy images, with $m\approx 0.2n$. To do so, we add independent
Gaussian noise to each pixel of the samples in the MNIST dataset. We apply
appropriate band-pass filters, as denoising functions, to the noisy images to
recover the original images. To be flexible, the filters are
$B_{X_{m},\bm{\alpha}}$ and $B_{Y_{m},\bm{\alpha}^{\prime}}$ as described at
the beginning of this subsection. Both coefficient sets $\bm{\alpha}$ and
$\bm{\alpha}^{\prime}$, as hyperparameters, are tuned based on a small number
of samples. In Fig. 7, we show the results. We see that with
$B_{Y_{m},\bm{\alpha}^{\prime}}$, the recovered images look more like the
original ones (especially the complement of the digit figures) as compared
with those recovered with $B_{X_{m},\bm{\alpha}}$, which is the classical low-
pass filter.

Fig. 7: We show sample images recovered from noisy ones using
$B_{X_{m},\bm{\alpha}}$ and $B_{Y_{m},\bm{\alpha}^{\prime}}$. Each row
corresponds to a digit from $0$ to $9$. Every four columns consist of an
example. In each example, the last image of the group is the original image
and the third image is the noisy image. The first image is the one obtained by
applying $B_{Y_{m},\bm{\alpha}^{\prime}}$, while the second image is obtained
by applying $B_{X_{m},\bm{\alpha}}$.

###  V-B Principle components of graph signals

In this subsection, we investigate the construction of Section III by studying
the principle components of graph signals. The dataset we use here is from a
weather station network in the United States with $n=197$
nodes.333http://www.ncdc.noaa.gov/data-access/ The signals are daily
temperatures recorded over the year 2013.

We pre-process each $f$ in our dataset as follows. Let $c$ be any constant
signal, we place $f$ by $f-\langle f,c\rangle c$, i.e., the constant component
from $f$ is removed as it does not give any useful geometric information of
the graph. The pre-processing step results in a perpendicular signal to the
$0$-smooth signals according to Definition 1.

The geographic locations of the stations are available, and based on such
information, a $k$-NN graph $G=(V,E)$ is constructed. The size of the graph is
$|V|=194$, and the average degree of $G$ is $\approx 5$ and $|E|=495$. Among
all the signals, we randomly choose $3$ samples from each month to form a
sample set of signals $F$ containing $36$ signals, approximately $10\%$ of all
the available signals.

By the construction of Section III, we obtain a parametrized family of graphs
$G_{F}:M_{F}\to\mathcal{G}$, where $M_{F}=\mathbb{R}_{\geq 0}^{37}$ and
$\mathcal{G}$ is the collection of graphs on $194$ vertices. The entire image
$Im(G_{F})$ of $G_{F}$ is too large for us to investigate. For our purpose, we
consider a subset $C=\\{G_{0},\ldots,G_{20}\\}$ of $Im(G_{F})$ consisting of
$21$ graphs. Each $G_{i},0\leq i\leq 20$ is of the form
$G_{F}(y_{i},x_{i},\ldots,x_{i})$ such that:

  * •

$x_{0}=0$ (hence $G_{0}=G$).

  * •

$x_{20}>\\!\\!>1$ and $x_{1}<\ldots<x_{19}$ are chosen to equally divide the
interval $(x_{0},x_{20})$.

  * •

The control parameter $y_{i}$ is chosen such that the size of $G_{i}$ is
approximately the same as that of $G$.

We first study how each $G_{i},1\leq i\leq 20$ is different from $G_{0}=G$. We
compute the Hamming distance $d_{H}(G_{0},G_{i})$ that counts the number of
edges contained exclusively in either $G_{0}$ or $G_{i}$. The plot of
$d_{H}(G,G_{i})$ against $i$ is shown in Fig. 8. We see that the curve is in
general increasing in $i$. It is steep initially and becomes flatter when $i$
is large, say exceeds $10$. For the extreme case $G_{20}$, it is constructed
almost solely from sample signals $F$. However, the Hamming distance
$d_{H}(G,G_{20})$ suggests that around $2/3$ of the edges of $G$ are also
contained in $G_{20}$, though $G$ and $G_{20}$ are constructed from completely
different means.

Fig. 8: The plot of Hamming distance against the index $i$.

For our next task, we want to perform a Fourier analysis of the temperature
signals. It is however unfavorable to use $G_{i},0\leq i\leq 20$ directly as
some of them are not connected. We construct $H_{i}$ whose edges are the
unions of edges in $G$ and $G_{i}$. The plot for $d_{H}(G,H_{i})$ is also
shown in Fig. 8. For example, we add $\approx 25\%,32\%$ more edges to $G$ to
form $H_{10}$ and $H_{20}$ respectively. For each $H_{i},0\leq i\leq 20$, let
$L_{i}$ be its Laplacian and $B_{i}=\\{e_{i,j},1\leq j\leq 194\\}$ be an
eigenbasis of $L_{i}$. For each signal $f$, we compute its Fourier
coefficients $\hat{f}_{i,j}=\langle f,e_{i,j}\rangle$. The principal
components of $f$ w.r.t. $B_{i}$ are those indices $j$ such that
$|\hat{f}_{i,j}|$ is large. Let $\tau_{i}$ be the permutation of indices
$\\{1,\ldots,194\\}$ such that
$|\hat{f}_{i,\tau_{i}(j)}|\geq|\hat{f}_{i,\tau_{i}(j+1)}|$, i.e., $\tau_{i}$
re-orders the indices according to $|\hat{f}_{i,j}|$ decreasingly. For each
$k\leq 194$, we set $\hat{f}^{k}_{i}=\sqrt{\sum_{1\leq j\leq
k}\hat{f}_{i,\tau_{i}(j)}^{2}}/|f|$. If we interpret $|f|$ as the energy of
$f$, then $\hat{f}_{i}^{k}$ computes the percentage of the energy of $f$
contained in $k$ principal components. Therefore, for the same (small) $k$,
the $H_{i}$ with larger $\hat{f}_{i}^{k}$ value is preferred. In Fig. 9, we
show the plots of average $\hat{f}^{k}_{i}$ against $k$. On the left, we show
the general trend by including all $1\leq i\leq 20$ and $1\leq k\leq 194$. We
see that on the large scale, we have the same general trend for every
$H_{i},0\leq i\leq 20$. On average, for each $i$, $\hat{f}^{k}_{i}$ quickly
reaches a very high percentage as $k$ increases, and the curve becomes almost
flat. On the other hand, by amplifying the details for $i=0,10,20$ and
$k=1,\ldots,5$, we see that $H_{10}$ gives the largest mean $\hat{f}^{j}_{i}$,
while $H_{0}$ gives the smallest. The graph $H_{10}$ uses both information
from the graph $G=H_{0}$ and the sample signals $F$.

Fig. 9: The plots of mean of $\hat{f}_{j}^{k}$ against $k$. On the left, we
show that general trend by including all $1\leq i\leq 20$ and $1\leq k\leq
194$. On the right, we enlarge the details for $i=0,10,20$ and $k=1,\ldots,5$.

While Fig. 9 gives a rough comparison, we now compare $H_{0}=G$ and $H_{10}$
in more detail. For a signal $f$ and $1\leq k\leq 5$, we find out
$(\hat{f}^{k}_{10}-\hat{f}^{k}_{0})/\hat{f}^{k}_{0}$ as the relative change
against $\hat{f}^{k}_{0}$. We consider the change significant if either
$(\hat{f}^{k}_{10}-\hat{f}^{k}_{0})/\hat{f}^{k}_{0}\geq 10\%$ or
$(\hat{f}^{k}_{10}-\hat{f}^{k}_{0})/\hat{f}^{k}_{0}\leq-10\%$, with the former
favors $H_{10}$ and the latter favors $H_{0}$. We go through every $f$ in the
dataset, and the distribution of instances for significant relative changes
are shown in Fig. 10. We see there are much more instances that favor $H_{10}$
than those that favor $H_{0}$. The difference in such instances is more than
$15\%$ of the total number of signals for $k=1$, where we use a single
component to approximate a signal. It is approximately $10\%$ for $k=2$, where
we use two components to approximate a signal.

Fig. 10: The histograms of distributions of instances for significant
relatives changes against $\hat{f}^{k}_{0}$. For the first plot, we show the
results for $k=1,2,3,4,5$ all considered together. While for the remaining two
plots, we show the individual results for $k=1$ and $k=2$.

##  VI Conclusions

In this paper, we study graph signal processing by focusing on graph signals
themselves. Motivated by the necessity to understand graph signals
geometrically, we introduce a new notion of smoothness. It is based on
comparing a signal with a graph with both considered elements of an enlarged
set of objects. The new notion allows us to partially classify graph signals,
and obtain new insights in conjunction with classical GSP tools. For future
works, we shall explore the potential of the framework in more application
scenarios.

##  Appendix A Proofs of theoretical results

###### Proof:

By re-arranging indices if necessary, we assume that $f_{i}\leq f_{i+1}$ and
$g_{i}\leq g_{i+1}$ for $1\leq i\leq n-1$. Moreover, as $g$ is orthogonal to
the constant vector, $f$ is not orthogonal to $g$ if and only if $f+c$ is not
orthogonal to $g$. Without loss of generality, by adding a constant $c$ to $f$
if necessary, we assume that $g_{i}\leq f_{i}\leq g_{i+1},1\leq i\leq n-1$ and
$f_{n}\geq g_{n}$.

As $g$ is nonzero and $g$ is orthogonal to the constant vectors, we have
$g_{1}<0$ and $g_{n}>0$. Suppose $f_{i}$ and $g_{i}$ have the same parity,
i.e., $f_{i}g_{i}\geq 0$, for each $1\leq i\leq n$. As $f$ is nonzero, either
$f_{1}<0$ or $f_{n}>0$. Then $\langle f,g\rangle=\sum_{1\leq i\leq
n}f_{i}g_{i}\geq\max\\{f_{n}g_{n},f_{1}g_{1}\\}>0$.

If for some $1\leq i\leq n$, $f_{i}g_{i}<0$, we have $g_{i}<0<f_{i}$ by the
interlacing property. For $j>i$, we have $f_{j}\geq g_{j}\geq f_{i}>0$; while
for $l<i$, we have $g_{l}\leq f_{l}\leq g_{i}<0$. In particular,
$f_{j}g_{j}>0$ for each $j\neq i$. Therefore, if $1<i<n$, we find $\langle
f,g\rangle\geq f_{1}g_{1}+f_{i}g_{i}+f_{n}g_{n}$. As either
$f_{1}g_{1}+f_{i}g_{i}\geq 0$ or $f_{i}g_{i}+f_{n}g_{n}\geq 0$, we have
$\langle f,g\rangle>0$. If $i=1$ or $i=n$, then $\langle f,g\rangle\geq
f_{1}g_{1}+f_{2}g_{2}+f_{n}g_{n}\geq f_{2}g_{2}>0$. This concludes the proof.
∎

###### Proof:

We first verify the recoverability of graphs. If $G_{F}$ is as constructed,
then $G$ is nothing but $G_{F}(1,0\ldots,0)$. For recoverability of signal, we
notice that

$\displaystyle|f(v_{i})-f(v_{j})|=\inf_{x_{0}\in\mathbb{R}^{\geq
0}}\\{G_{f}(x_{0},1)\text{ contains }(v_{i},v_{j})\text{ as an edge}\\}.$

Therefore, if $G_{f}=G_{f^{\prime}}$, then
$|f(v_{i})-f(v_{j})|=|f^{\prime}(v_{i})-f^{\prime}(v_{j})|$. In the reverse
direction, if $f=af^{\prime}+c$, then notice that
$|f(v_{i})-f(v_{j})|=|a||f^{\prime}(v_{i})-f^{\prime}(v_{j})|$. The
equivalence between $M_{f}$ and $M_{f^{\prime}}$ is given by $\phi:M_{f}\to
M_{f^{\prime}},(x_{0},x_{1})\mapsto(x_{0},x_{1}/|a|)$, and
$\psi:M_{f^{\prime}}\to M_{f},(x_{0},x_{1})\mapsto(x_{0},|a|x_{1})$.

For composability, consider two finite sets of signals $F_{1}$ of size $k_{1}$
and $F_{2}=\\{f_{1},\ldots,f_{k_{2}}\\}$ of size $k_{2}$. Let $F=F_{1}\cup
F_{2}$ of size $k$. Define $M_{1,2}$ (as an abbreviation of
$(M_{F_{1}})_{F_{2}}$) to be $\mathbb{R}_{\geq 0}^{k_{1}+k_{2}+1}$. An element
of $M_{1,2}$ is denoted by
$x=(x_{0},y_{1},\ldots,y_{k_{1}},z_{1},\ldots,z_{k_{2}})$ and abbreviated by
$(x_{0},y,z)$ with $y=(y_{1},\ldots,y_{k_{1}})$ and
$z=(z_{1},\ldots,z_{k_{2}})$. We define $G_{1,2}:M_{1,2}\to\mathcal{G}$. Given
$x=(x_{0},y,z)$, $G_{1,2}(x)$ is the following graph. For a pair of nodes
$v_{i},v_{j}$, similar to above, let

$\displaystyle D_{y}(v_{i},v_{j})=\Big{(}\inf_{x_{0}\in\mathbb{R}^{\geq
0}}\\{G_{F_{1}}(x_{0},y)\text{ contains }(v_{i},v_{j})\text{ as an
edge}\\}\Big{)}.$

From this, we compute

$\displaystyle D_{y,z}(v_{i},v_{j})^{2}=D_{y}(v_{i},v_{j})^{2}+\sum_{1\leq
l\leq k_{2}}z_{l}(f_{l}(v_{i})-f_{l}(v_{j}))^{2}.$

The nodes $v_{i},v_{j}$ are connected by an edge in $G_{1,2}(x)$ if
$D_{y,z}(v_{i},v_{j})\leq x_{0}$.

To show that $G_{1,2}\sim G_{F}$, recall an element of $M_{1,2}$ takes the
form $(x_{0},y_{1},\ldots,y_{k_{1}},z_{1},\ldots,z_{k_{2}})$ and an element of
$M_{F}$ takes the form $(x_{0},x_{1},\ldots,x_{k})$. We examine each signal in
$F_{1}\cup F_{2}$. For $f\in F_{1}\cup F_{2}$, assume it corresponds to
$y_{i}$ if $f\in F_{1}$, $z_{j}$ if $f\in F_{2}$, and $x_{l}$. Then define
$\phi:M_{1,2}\to M_{F}$ such that the $x_{l}$-component of
$\phi\big{(}(x_{0},y_{1},\ldots,y_{k_{1}},z_{1},\ldots,z_{k_{2}})\big{)}$ is
$y_{i}+z_{j}$. It is straightforward to check that any smooth map such that
$\phi\circ\psi=Id_{M_{F}}$ defines an equivalence between $G_{1,2}$ and
$G_{F}$. ∎

###### Proof:

We define the maps $\tau_{1}$ \- $\tau_{5}$ in Fig. 4.

  * •

For $\tau_{1}$, consider $G=(V,E)\in\mathcal{MG}_{n}$, define $\tau_{1}(G)$ to
be the metric space on $V$ with distance metric $d_{G}$ on $G$.

  * •

For $\tau_{2}$, given $(V,d)$ a finite metric space on $n$ points with metric
$d$, define $M_{V}=\mathbb{R}^{\geq 0}$. For $x_{0}\in M_{V}$,
$\tau_{2}(V)(x_{0})$ is the graph on $V$ such that distinct pair
$v_{i},v_{j}\in V$ are connected by an edge if $d(v_{i},v_{j})\leq x_{0}$.

  * •

For $\tau_{3}$, given $\phi:M\to\mathcal{G}_{n}$, the associated sequence is
$Im(\phi)$ ordered by the number of edges.

  * •

For $\tau_{4}$, let $S=\\{G_{1},\ldots,G_{k}\\}$ be a finite sequence of
graphs on $n$ vertices. If $k=1$, then $\tau_{4}(S)=G_{1}$; and if $k\geq 2$,
then $\tau_{4}(S)=G_{2}$.

  * •

For $\tau_{5}$, let $f=(f_{i})_{1\leq i\leq n}$ (the notation is only valid in
this proof) be an element of $\mathcal{F}_{n}$. Define $M_{f}=\mathbb{R}_{\geq
0}$. For $x_{0}\in M_{f}$, $\tau_{5}(f)(x_{0})$ is the graph on
$\\{v_{1},\ldots,v_{n}\\}$, and $v_{i},v_{j}$ is connected by an edge if
$|f_{i}-f_{j}|\leq x_{0}$.

The claims
$\tau_{4}\circ\tau_{3}\circ\tau_{2}\circ\tau_{1}=Id_{\mathcal{G}_{n}}$
$\tau_{2}\circ\tau_{1}(G)=G_{c}$ are straightforward to check for the
constructions, which are omitted here. Let us verify the statement on
$\tau_{5}$.

As we have seen earlier, $\tau_{5}(f)=\tau_{5}(g)$ implies that
$|f_{i}-f_{j}|=|g_{i}-g_{j}|$ for any $1\leq i\neq j\leq n$. Let us briefly
recall the reason is that

$\displaystyle|f_{i}-f_{j}|=\inf_{x_{0}\in M_{f}}\\{\tau(f)(x_{0})\text{
contains }(v_{i},v_{j})\text{ as an edge}\\}.$

Subtracting $f$ and $g$ by the constant signals $f_{0}$ and $g_{0}$
respectively, we assume that $f_{0}=g_{0}=0$. If $f$ and $g$ are constant
signals, then we are done. Otherwise, without loss of generality, we assume
that $f_{2}\neq 0$ and $g_{2}\neq 0$. If $f_{1}=0$ and $f_{2}\neq 0$ are both
fixed, then knowing $|f_{i}-f_{1}|$ and $|f_{i}-f_{2}|$ uniquely determines
$f_{i}$. Therefore, as $|f_{i}-f_{j}|=|g_{i}-g_{j}|$ for any $1\leq i\neq
j\leq n$, we see that $f=g$ if $f_{2}=g_{2}$ and $f=-g$ if $f_{2}=-g_{2}$. ∎

###### Proof:

  1. 1)

We notice that $*_{f+c}=*_{f}$ and $*_{rf}=r(*_{f})$ (as maps). Therefore, if
$f$ is $\epsilon$-smooth, then so do $rf$ and $f+c$.

  2. 2)

Following directly from the definition, a signal of $f$ is $0$-smooth if and
only if $Im(*_{f})\subset Im(G_{c})$. Suppose for $0$-smooth signal $f$, there
is an edge $(v_{i},v_{j})$ such that $f(v_{i})=f(v_{j})$. If $f$ is not a
constant signal, then we can always find another edge $(v_{k},v_{l})$ such
that $f(v_{k})\neq f(v_{l})$ (as $G$ is connected). Choose
$0<x<|f(v_{k})-f(v_{l})|$, then $*_{f}(x)$ contains $(v_{i},v_{j})$ and does
not contain the edge $(v_{k},v_{l})$. Hence, $*_{f}(x)\notin Im(G_{c})$, and
this contradicts that $f$ is $0$-smooth.

Suppose $G$ is a path graph on $n\geq 2$ vertices. We order the vertices as
$v_{1},\ldots,v_{n}$ from one end to the other. Then the non-constant signal
$f=(1,\ldots,n)^{T}$ is also $0$-smooth.

Conversely, suppose $G$ is not a path graph and $f$ is a non-constant
$0$-smooth signal. According to the first paragraph, for each edge
$(v_{i},v_{j})$ of $G$, $f(v_{i})\neq f(v_{j})$. We consider two cases, $G$ is
a tree and $G$ contains a cycle.

Case $1$: If $G$ is a tree, then it must contain a node of degree at least
$3$, say $v_{1}$. Without loss of generality, assume that $3$ of its neighbors
are $v_{2}$, $v_{3}$, and $v_{4}$. If $|f(v_{i})-f(v_{1})|,i=2,3,4$ are not
the same, then re-ordering if necessary we may assume
$|f(v_{2})-f(v_{1})|<x<|f(v_{3})-f(v_{1})|$ for some $x$. Then $*_{f}(x)$
contains $(v_{1},v_{2})$ as an edge and excludes $(v_{1},v_{3})$. Hence,
$*_{f}(x)\notin Im(G_{c})$ and this is a contradiction. If
$|f(v_{i})-f(v_{1})|,i=2,3,4$ are all equal to $y$, then for at least two
nodes, say $v_{2},v_{3}$, we have $f(v_{2})=f(v_{3})$. Choose $0<x<y$, we have
$*_{f}(x)$ contains $(v_{2},v_{3})$ as an edge but excludes both
$(v_{1},v_{2})$ and $(v_{2},v_{3})$. Hence, $*_{f}(x)\notin Im(G_{c})$ and
this leads to a contradiction.

Case $2$: If $G$ contains a cycle of size $m\geq 3$. We order the vertices
along the cycle as $v_{1},\ldots,v_{m}$. If there are pairs $(v_{i},v_{i+1})$
and $(v_{j},v_{j+1})$ with $i\neq j$ (by convention, $v_{m+1}=v_{1}$), such
that $|f(v_{i})-f(v_{i+1}))|<x<|f(v_{j})-f(v_{j+1})|$, then $*_{f}(x)$
contains $(v_{i},v_{i+1})$ as an edge and excludes $(v_{j},v_{j+1})$. This is
impossible if we want $*_{f}(x)\notin Im(G_{c})$. Therefore,
$|f(v_{i})-f(v_{i+1})|$ equals to some $y\neq 0$ for every $1\leq i\leq m$.
This can only happen that for some $i\neq j$, $f(v_{i})=f(v_{j})$. Consider
$0<x<y$, $*_{f}(x)$ contains $(v_{i},v_{j})$ as an edge but excludes
$(v_{1},v_{2})$. Hence $*_{f}(x)\notin Im(G_{c})$ and the contradiction
concludes the last subcase.

  3. 3)

Notice that in the expression (1) of $d_{\mathcal{S}}$ with $\gamma_{1}=*_{f}$
and $\gamma_{2}=G_{c}$, the $d_{H}$ factor in each term is uniformly bounded
by $2n^{2}$ independent of $f$. Moreover, fix a non-constant signal $f$, for
any signal $f^{\prime}$ such that
${\left\lVert{f-f^{\prime}}\right\rVert}\leq\epsilon$ for $\epsilon$ small
enough, we can always ensure that

    1. (a)

$f^{\prime}$ is non-constant.

    2. (b)

The part $1/|\gamma_{1}^{\prime-1}(Im(\gamma_{1}^{\prime})^{\circ})|$ has an
upper bound $\alpha$ that depends only on $f$ for any $\epsilon$ small enough.

    3. (c)

For any $G\in Im(\gamma_{1})^{\circ}\cup Im(\gamma_{1}^{\prime})^{\circ}$,
$\big{|}|\gamma_{1}^{-1}(G)|-|\gamma_{1}^{\prime-1}(G)|\big{|}$ is bounded by
$\beta(\epsilon)$ that converges to $0$ if $\epsilon\to 0$.

We also notice that the number of graphs in $Im(\gamma_{1})^{\circ}\cup
Im(\gamma_{1}^{\prime})^{\circ}$ is also bounded by $n^{2}$, which is
independent of both $f$ and $\epsilon$. Now we estimate

$\displaystyle|d_{\mathcal{S}}(\gamma_{1},\gamma_{2})-d_{\mathcal{S}}(\gamma_{1}^{\prime},\gamma_{2})|\leq
n^{2}\cdot\beta(\epsilon)\cdot 2\alpha\cdot
2n^{2}=4n^{4}\alpha\beta(\epsilon)\to 0,$

as $\epsilon\to 0$.

∎

###### Proof:

Let $\gamma_{1}=*_{f}$, $\gamma_{2}=G_{c}$ and ordered sequence of pairs of
vertices $Q=(Q_{l})_{1\leq l\leq n(n-1)/2}$ as earlier. As we assume that
$|f(u_{1})-f(v_{1})|\neq|f(u_{2})-f(u_{2})|$, the image $Im(\gamma_{1})$ of
$\gamma_{1}$ is a sequence of graphs $G_{(l)},1\leq l\leq n(n-1)/2$ such that
the edge set of $G_{(l)}$ is $\\{Q_{l},1\leq l\leq l\\}$, i.e., $G_{(l+1)}$ is
obtained from $G_{(l)}$ by adding $Q_{l+1}$. To compute $\epsilon$, we need to
find $d_{H}(G_{(i)},G^{(j)})$ for suitable $1\leq i\leq n(n-1)/2$ and $0\leq
j\leq k$. In doing so, we may take the sum over all the edges of $G_{(i)}$ and
$G^{(j)}$, i.e., $d_{H}(G_{(i)},G^{(j)})=\sum_{1\leq l\leq
n(n-1)/2}\theta_{i,j}(Q_{l})$, where $\theta_{i,j}(Q_{l})=1$ if $Q_{l}$ is an
edge of either $G_{(i)}$ or $G^{(j)}$ exclusively and $0$ otherwise.
Therefore, $\epsilon$ is expressed in the form
$\sum_{G_{(i)},G^{(j)}}\sum_{Q_{l}}\theta_{i,j}(Q_{l})$. We want to change the
summation order $\sum_{Q_{l}}\sum_{G_{(i)},G^{(j)}}\theta_{i,j}(Q_{l})$. This
prompts us to go through $Q_{l}$ one-by-one and study its membership in
$G_{(i)}$ and $G^{(j)}$. With this perspective, we describe an equivalent
formula for $\epsilon_{\mathcal{P}}$.

For the partition $\mathcal{P}$ of $I$, we claim that

$\displaystyle\epsilon_{\mathcal{P}}=\sum_{0\leq j\leq D_{G}}\sum_{i\in
I_{j}}\frac{\gamma_{1}^{-1}(G_{(i)})}{\gamma_{1}^{-1}(Im(\gamma_{1})^{\circ})}d_{H}(G_{(i)},G^{(j)}).$
(2)

We prove the claim by showing that for each pair of nodes
$Q_{l}=\\{u_{l},v_{l}\\},1\leq l\leq n(n-1)/2$, it contributes to the same
summand on both sides of (2). For the left-hand-side, the contribution of
$Q_{l}$ is $\epsilon_{l}$. On the right-hand-side, $Q_{l}$ contributes to
either $1$ or $0$ in each of $d_{H}(G_{(i)},G^{(j)})$. We notice that
$G_{(i)}$ is a subgraph of $G_{(i+1)}$ and similarly $G^{(j)}$ is a subgraph
of $G^{(j+1)}$. The pair $Q_{l}$ is an edge of $G_{(i)}$ for $i\geq l$. Let
$k$ be the smallest index such that $Q_{l}$ is an edge of $G^{(k)}$. Then
$Q_{l}$ is an edge of $G^{(j)}$ for $j\geq k$. Therefore, $Q_{l}$ contributes
$1$ to $d_{H}(G_{(i)},G^{(j)})$ with $i\in I_{j}$ if and only if:

  1. (a)

$i<l$ and $j\geq k$, or

  2. (b)

$i\geq l$ and $j<k$.

Let $l^{\prime}$ be smallest index such that $Q_{l^{\prime}}\in G^{(k)}$ and
$l\in I_{k^{\prime}}$. Correspondingly, we consider two cases on $k$ and
$k^{\prime}$ (illustrated in Fig. 11):

  1. (a’)

If $k\leq k^{\prime}$, then b cannot happen. For if $i\geq l$, then $i\notin
I_{j}$ as $j<k\leq k^{\prime}$. Therefore $i<l$ and $j\geq k$. The condition
$i\in I_{j}$ together with $j\geq k$ imply that $i\geq l^{\prime}$. In
summary, we have $l^{\prime}\leq i<l$ and $k\leq j\leq k^{\prime}$ such that
$i\in I_{j}$. Therefore, the contribution of $Q_{l}$ to the right-hand-side of
(2) is $\frac{\sum_{l^{\prime}\leq
i<l}\gamma_{1}^{-1}(G_{(i)})}{\gamma_{1}^{-1}(Im(\gamma_{1})^{\circ})}$, which
is exactly $\epsilon_{l}$ as
$\gamma_{1}^{-1}(G_{(i)})=|f(u_{i+1})-f(v_{i+1})|-|f(u_{i})-f(v_{i})|$.

  2. (b’)

If $k>k^{\prime}$, then a cannot happen. We can show that the contribution of
$Q_{l}$ to the right-hand-side of (2) is $\epsilon_{l}$ by the exact same
argument.

This completes the proof of (2).

Fig. 11: An illustration of the proof of (2).

If we examine the definition of $\epsilon$, for each $0\leq j\leq D_{G}$,
define $I_{j}^{\prime}$ as follows: an index $1\leq l\leq n(n-1)/2$ belongs to
$I_{j}^{\prime}$ if
$d_{H}(G_{(l)},G^{(j^{\prime})})>d_{H}(G_{(l)},G^{(j)})=d_{H}(G_{(l)},Im(\gamma_{2}))$
for any $j^{\prime}>j$. We claim that
$\mathcal{P}^{\prime}=\\{I_{j}^{\prime},0\leq j\leq D_{G}\\}$ is a partition
of $Q$.

For any $1\leq l\leq n(n-1)/2$, suppose $l$ is associated with $j$ and $l+1$
is associated with $j^{\prime}$ as described in the previous paragraph. To
prove the claim, it suffices to show that $j\leq j^{\prime}$. Suppose on the
contrary that $j^{\prime}<j$. From the definition, we have
$d_{H}(G_{(l)},G^{(j)})\leq d_{H}(G_{(l)},G^{(j^{\prime})})$ and
$d_{H}(G_{(l+1)},G^{(j^{\prime})})<d_{H}(G_{(l+1)},G^{(j)})$. Notice that
$G_{(l+1)}$ is obtained from $G_{l}$ by including a single edge $Q_{l+1}$. We
consider the following cases:

  1. (i)

$Q_{l+1}\in G^{(j^{\prime})}$: In this case, $Q_{l+1}$ is also in $G^{(j)}$.
Hence, $d_{H}(G_{(l)},G^{(j)})-1=d_{H}(G_{(l+1)},G^{(j)})$ and
$d_{H}(G_{(l)},G^{(j^{\prime})})-1=d_{H}(G_{(l+1)},G^{(j^{\prime})})$. This
gives a contradiction, as

$\displaystyle d_{H}(G_{(l+1)},G^{(j)})=d_{H}(G_{(l)},G^{(j)})-1\leq
d_{H}(G_{(l)},G^{(j^{\prime})})-1=d_{H}(G_{(l+1)},G^{(j^{\prime})}).$

  2. (ii)

$Q_{l+1}\notin G^{(j)}$: We also have $Q_{l+1}\notin G^{(j^{\prime})}$. Hence,
$d_{H}(G_{(l)},G^{(j)})+1=d_{H}(G_{(l+1)},G^{(j)})$ and
$d_{H}(G_{(l)},G^{(j^{\prime})})+1=d_{H}(G_{(l+1)},G^{(j^{\prime})})$. We have
the same contradiction as in i.

  3. (iii)

$Q_{l+1}\in G^{(j)}$ and $Q_{l+1}\notin G^{(j^{\prime})}$: In this case, we
have $d_{H}(G_{(l)},G^{(j)})-1=d_{H}(G_{(l+1)},G^{(j)})$ and
$d_{H}(G_{(l)},G^{(j^{\prime})})+1=d_{H}(G_{(l+1)},G^{(j^{\prime})})$. The
equations imply that $d_{H}(G_{(l+1)},G^{(j)})<d_{H}(G_{(l+1)},G^{(j)})$,
which is again a contradiction.

The three cases conclude our proof of the claim by contradiction.

In defining the partition $\mathcal{P}^{\prime}$, for the pair $l$ and
$I_{j}^{\prime}$, we have
$d_{H}(G_{(l)},G^{(j)})=d_{H}(G_{(l)},Im(\gamma_{2}))$. Therefore for
$\mathcal{P^{\prime}}$, we have $\epsilon=\epsilon_{\mathcal{P^{\prime}}}$, in
view of (2). For any other partition $\mathcal{P}=\cup_{0\leq k\leq
D_{G}}I_{k}$, if $i\in I_{j^{\prime}}$, then
$d_{H}(G_{(l)},G^{(j^{\prime})})\geq
d_{H}(G_{(l)},Im(\gamma_{2}))=d_{H}(G_{(l)},G^{(j)})$. Therefore,
$\epsilon_{\mathcal{P}}\geq\epsilon_{\mathcal{P^{\prime}}}$. ∎

## References

  * [1] D. I. Shuman, B. Ricaud, and P. Vandergheynst, “A windowed graph fourier transform,” in _Proc. IEEE Workshop on Statistical Signal Process._ , 2012\.
  * [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 Process. Mag._ , vol. 30, no. 3, pp. 83–98, 2013.
  * [3] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,” _IEEE Trans. Signal Process._ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [4] ——, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” _IEEE Signal Process. Mag._ , vol. 31, no. 5, pp. 80–90, 2014.
  * [5] A. Gadde, A. Anis, and A. Ortega, “Active semi-supervised learning using sampling theory for graph signals,” in _Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining_ , 2014.
  * [6] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning Laplacian matrix in smooth graph signal representations,” _IEEE Trans. Signal Process._ , vol. 64, no. 23, pp. 6160–6173, 2016.
  * [7] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _NeurIPS_ , 2016.
  * [8] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [9] H. E. Egilmez, E. Pavez, and A. Ortega, “Graph learning from data under Laplacian and structural constraints,” _IEEE J. Sel. Top. Signal Process._ , vol. 11, no. 6, pp. 825–841, 2017.
  * [10] 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 Trans. Signal Process._ , vol. 66, no. 3, pp. 817–829, 2018.
  * [11] A. Ortega, P. Frossard, J. Kovačević, J. M. F. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proc. IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [12] B. Girault, A. Ortega, and S. S. Narayanan, “Irregularity-aware graph fourier transforms,” _IEEE Trans. Signal Process._ , vol. 66, no. 21, pp. 5746–5761, 2018.
  * [13] F. Ji and W. P. Tay, “A Hilbert space theory of generalized graph signal processing,” _IEEE Trans. Signal Process._ , vol. 67, no. 24, pp. 6188 – 6203, 2019.
  * [14] A. Agaskar and Y. M. Lu, “A spectral graph uncertainty principle,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 7, pp. 4338–4356, 2013.
  * [15] S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, “Discrete signal processing on graphs: Sampling theory,” _IEEE Trans. Signal Process._ , vol. 63, no. 24, pp. 6510–6523, 2015.
  * [16] M. Tsitsvero, S. Barbarossa, and P. Di Lorenzo, “Signals on graphs: Uncertainty principle and sampling,” _IEEE Trans. Signal Process._ , vol. 64, no. 18, pp. 4845–4860, 2016.
  * [17] A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Sampling of graph signals with successive local aggregations,” _IEEE Trans. Signal Process._ , vol. 64, no. 7, pp. 1832–1843, 2016.
  * [18] A. Anis, A. Gadde, and A. Ortega, “Efficient sampling set selection for bandlimited graph signals using graph spectral proxies,” _IEEE Trans. Signal Process._ , vol. 64, no. 14, pp. 3775–3789, 2016.
  * [19] D. E. O. Tzamarias, P. Akyazi, and P. Frossard, “A novel method for sampling bandlimited graph signals,” in _Proc. 26th European Signal Process. Conf._ , 2018.
  * [20] R. Varma and J. Kovac̆ević, “Random sampling for bandlimited signals on product graphs,” in _Proc. 13th Int. Conf. Sampling Theory and Applications_ , 2019.
  * [21] B. Le Bars, P. Humbert, L. Oudre, and A. Kalogeratos, “Learning laplacian matrix from bandlimited graph signals,” in _Proc. IEEE Int. Conf. Acoustics, Speech and Signal Process._ , 2019.
  * [22] F. Ji, H. Feng, H. Sheng, and W. P. Tay, “Sampling theory of bandlimited continuous-time graph signals,” _arXiv preprint arXiv:2010.09952_ , 2020\.
  * [23] G. Carlsson, “Topology and data,” _Bull. Amer. Math. Soc._ , no. 46, pp. 255–308, 2009.