Vertex-Frequency Analysis on Graphs

Introduction

In applications such as social networks, electricity networks, transportation networks, and sensor networks, data naturally reside on the vertices of weighted graphs. Moreover, weighted graphs are a flexible tool that can be used to describe similarities between data points in statistical learning problems, functional connectivities between different regions of the brain, and the geometric structures of countless other topologically-complex data domains.

In order to reveal relevant structural properties of such data on graphs and/or sparsely represent different classes of signals on graphs, we can construct dictionaries of atoms, and represent graph signals as linear combinations of the dictionary atoms. The design of such dictionaries is one of the fundamental problems of signal processing, and the literature is filled with a wide range of dictionaries, including, e.g., Fourier, time-frequency, curvelet, shearlet, and bandlet dictionaries (see, e.g., for an excellent historical overview of dictionary design methods and signal transforms).

Of course, the dictionary needs to be tailored to a given class of signals under consideration. Specifically, as exemplified in [2, Example 1], in order to identify and exploit structure in signals on weighted graphs, we need to account for the intrinsic geometric structure of the underlying data domain when designing dictionaries and signal transforms. When we construct dictionaries of features on weighted graphs, it is also desirable to (i) explicitly control how these features change from vertex to vertex, and (ii) ensure that we treat vertices in a homogeneous way (i.e., the resulting dictionaries are invariant to permutations in the vertex labeling). Unfortunately, weighted graphs are irregular structures that lack a shift-invariant notion of translation, a key component in many signal processing techniques for data on regular Euclidean spaces. Thus, many of the existing dictionary design techniques cannot be directly applied to signals on graphs in a meaningful manner, and an important challenge is to design new localized transform methods that account for the structure of the data domain.

Accordingly, a number of new multiscale wavelet transforms for signals on graphs have been introduced recently (see and references therein for a review of wavelet transforms for signals on graphs). Although the field of signal processing on graphs is still young, the hope is that such transforms can be used to efficiently extract information from high-dimensional data on graphs (either statistically or visually), as well as to regularize ill-posed inverse problems.

Windowed Fourier transforms, also called short-time Fourier transforms, are another important class of time-frequency analysis tools in classical signal processing. They are particularly useful in extracting information from signals with oscillations that are localized in time or space. Such signals appear frequently in applications such as audio and speech processing, vibration analysis, and radar detection. Our aim here is to generalize windowed Fourier analysis to the graph setting.

Underlying the classical windowed Fourier transform are the translation and modulation operators. While these fundamental operations seem simple in the classical setting, they become significantly more challenging when we deal with signals on graphs. For example, when we want to translate the blue Mexican hat wavelet on the real line in Figure 1(a) to the right by 5, the result is the dashed red signal. However, it is not immediately clear what it means to translate the blue signal in Figure 1(c) on the weighted graph in Figure 1(b) “to vertex 1000.” Modulating a signal on the real line by a complex exponential corresponds to translation in the Fourier domain. However, the analogous spectrum in the graph setting is discrete and bounded, and therefore it is difficult to define a modulation in the vertex domain that corresponds to translation in the graph spectral domain.

In this paper, an extended version of the short workshop proceeding , we define generalized convolution, translation, and modulation operators for signals on graphs, analyze properties of these operators, and then use them to adapt the classical windowed Fourier transform to the graph setting. The result is a method to construct windowed Fourier frames, dictionaries of atoms adapted to the underlying graph structure that enable vertex-frequency analysis, a generalization of time-frequency analysis to the graph setting. After a brief review of the classical windowed Fourier transform in the next section and some spectral graph theory background in Section 3, we introduce and study generalized convolution and translation operators in Section 4 and generalized modulation operators in Section 5. We then define and explore the properties of windowed graph Fourier frames in Section 6, where we also present illustrative examples of a graph spectrogram analysis tool and signal-adapted graph clustering. We conclude in Section 7 with some comments on open issues.

The Classical Windowed Fourier Transform

An example of a windowed Fourier atom is shown in Figure 2.

A second, perhaps more intuitive, way to interpret $Sf(u,\xi)$ is as the Fourier transform of $f(T_{u}g)^{*}$, evaluated at frequency $\xi$. That is, we multiply the signal $f$ by (the complex conjugate of) a translated window $T_{u}g$ in order to localize the signal to a specific area of interest in time, and then perform Fourier analysis on this localized, windowed signal. This interpretation is illustrated in Figure 3.

As mentioned in Section 1, our plan for the rest of the paper is to generalize the translation and modulation operators to the graph setting, and then mimic the classical windowed Fourier transform construction of (3) and (4).

Spectral Graph Theory Notation and Background

where we adopt the convention that the inner product be conjugate-linear in the second argument. The inverse graph Fourier transform is then given by

Note that the definitions of the graph Fourier transform and its inverse in (5) and (6) depend on the choice of graph Laplacian eigenvectors, which is not necessarily unique. Throughout this paper, we do not specify how to choose these eigenvectors, but assume they are fixed. The ideal choice of the eigenvectors in order to optimize the theoretical analysis conducted here and elsewhere remains an interesting open question; however, in most applications with extremely large graphs, the explicit computation of a full eigendecomposition is not practical anyhow, and methods that only utilize the graph Laplacian through sparse matrix-vector multiplication are preferred. We discuss these computational issues further in Section 6.7.1.

Some intuition about the graph spectrum can also be carried over from the classical setting to the graph setting. In the classical setting, the Laplacian eigenfunctions (complex exponentials) associated with lower eigenvalues (frequencies) are relatively smooth, whereas those associated with higher eigenvalues oscillate more rapidly. The graph Laplacian eigenvalues and associated eigenvectors satisfy

Therefore, since each term in the summation of the right-hand side is non-negative, the eigenvectors associated with smaller eigenvalues are smoother; i.e., the component differences between neighboring vertices are small (see, e.g., [2, Figure 2]). As the eigenvalue or “frequency” increases, larger differences in neighboring components of the graph Laplacian eigenvectors may be present (see for further discussions of notions of frequency for the graph Laplacian eigenvalues). This well-known property has been extensively utilized in a wide range of problems, including spectral clustering , machine learning [11, Section III], and ill-posed inverse problems in image processing .

2 Localization of Graph Laplacian Eigenvectors and Coherence

There have recently been a number of interesting research results concerning the localization properties of graph Laplacian eigenvectors. For different classes of random graphs, show that with high probability for graphs of sufficiently large size, the eigenvectors of the graph Laplacian (or in some cases, the graph adjacency operator), are delocalized; i.e., the restriction of the eigenvector to a large set must have substantial energy, or in even stronger statements, the element of the matrix $\boldsymbol{\chi}:=\left[\chi_{0},\chi_{1},\ldots,\chi_{N-1}\right]$ with the largest absolute value is small. We refer to this latter value as the mutual coherence (or simply coherence) between the basis of Kronecker deltas on the graph and the basis of graph Laplacian eigenvectors:

These non-localization results are consistent with the intuition one might gain from considering the eigenvectors of the Laplacian for the unweighted path and ring graphs shown in Figure 5. The eigenvalues of the graph Laplacian of the unweighted path graph with $N$ vertices are given by

and one possible choice of associated orthonormal eigenvectors is

These graph Laplacian eigenvectors, which are shown in Figure 5(b), are the basis vectors in the Discrete Cosine Transform (DCT-II) transform used in JPEG image compression. Like the continuous complex exponentials, they are non-localized, globally oscillating functions. The unordered eigenvalues of the graph Laplacian of the unweighted ring graph with $N$ vertices are given by (see, e.g., [18, Chapter 3], [19, Proposition 1])

and one possible choice of associated orthonormal eigenvectors is

These eigenvectors correspond to the columns of the Discrete Fourier Transform (DFT) matrix. With this choice of eigenvectors, the coherence of the unweighted ring graph with $N$ vertices is $\frac{1}{\sqrt{N}}$, the smallest possible coherence of any graph. In this case, the basis of DFT columns and the basis of Kronecker deltas on vertices of the graph are said to be mutually unbiased bases.

However, empirical studies such as show that certain graph Laplacian eigenvectors may in fact be highly localized, especially when the graph features one or more vertices whose degrees are significantly higher or lower than the average degree, or when the graph features a high degree of clustering (many triangles in the graph). Moreover, Saito and Woei identify a class of starlike trees with highly-localized eigenvectors, some of which are even close to a delta on the vertices of the graph. The following example shows two less structured graphs that also have high coherence.

For the sensor network, $\sigma_{1}=0.074$ and $\sigma_{2}=0.075$. For the Swiss roll graph, $\sigma_{1}=0.100$ and $\sigma_{2}=0.215$. The coherences are based on the orthonormal Laplacian eigenvectors computed by MATLAB’s svd function.

The existence of localized eigenvectors can limit the degree to which our intuition from classical time-frequency analysis extends to localized vertex-frequency analysis of signals on graphs. We discuss this point in more detail in Sections 4.2, 6.6, and 6.7.

Finally, we define some quantities that are closely related to the coherence $\mu$ and will also be useful in our analysis. We denote the largest absolute value of the elements of a given graph Laplacian eigenvector by

and the largest absolute value of a given row of $\boldsymbol{\chi}$ by

Generalized Convolution and Translation Operators

The main objective of this section is to define a generalized translation operator that allows us to shift a window around the vertex domain so that it is localized around any given vertex, just as we shift a window along the real line to any center point in the classical windowed Fourier transform for signals on the real line. We use a generalized notion of translation that is – aside from a constant factor that depends on the number of vertices in the graph – the same notion used as one component of the spectral graph wavelet transform (SGWT) in [22, Section 4]. However, in order to leverage intuition from classical time-frequency analysis, we motivate its definition differently here by first defining a generalized convolution operator for signals on graphs. We then discuss and analyze a number of properties of the generalized translation as a standalone operator, including the localization of translated kernels.

Since the simple translation $g(t-\tau)$ cannot be directly extended to the graph setting, we cannot directly generalize (14). However, the classical convolution product also satisfies

Using notation from the theory of matrix functions , we can also write the generalized convolution as

The generalized convolution product defined in (16) satisfies the following properties:

Generalized convolution in the vertex domain is multiplication in the graph spectral domain:

An invariance property with respect to the graph Laplacian (a difference operator):

The sum of the generalized convolution product of two signals is a constant times the product of the sums of the two signals:

2 Generalized Translation on Graphs

3 Properties of the Generalized Translation Operator

Some expected properties of the generalized translation operator follow immediately from the generalized convolution properties of Proposition 1.

$T_{i}(f\ast g)=(T_{i}f)\ast g=f\ast(T_{i}g)$.

$\sum_{n=1}^{N}(T_{i}f)(n)=\sqrt{N}\hat{f}(0)=\sum_{n=1}^{N}f(n)$.

However, the niceties end there, and we should also point out some properties that are true for the classical translation operator, but not for the generalized translation operator for signals on graphs. First, unlike the classical case, the set of translation operators $\{T_{i}\}_{i\in\{1,2,\ldots,N\}}$ do not form a mathematical group; i.e., $T_{i}T_{j}\neq T_{i+j}$. In the very special case of shift-invariant graphs [24, p. 158], which are graphs for which the DFT basis vectors (9) are graph Laplacian eigenvectors (the unweighted ring graph shown in Figure 5(c) is one such graph), we have

However, (26) is not true in general for arbitrary graphs. Moreover, while the idea of successive translations $T_{i}T_{j}$ carries a clear meaning in the classical case, it is not a particularly meaningful concept in the graph setting due to our definition of generalized translation as a kernelized operator.

Second, unlike the classical translation operator, the generalized translation operator is not an isometric operator; i.e., $\lVert T_{i}f\rVert_{2}\neq\lVert f\rVert_{2}$ for all indices $i$ and signals $f$. Rather, we have

Substituting $\chi_{0}(i)=\frac{1}{\sqrt{N}}$ into (4.3) yields the first inequality in (27). ∎

4 Localization of Translated Kernels in the Vertex Domain

We now examine to what extent translated kernels are localized in the vertex domain. First, we note that a polynomial kernel with degree $K$ that is translated to a given center vertex is strictly localized in a ball of radius $K$ around the center vertex, where the distance $d_{{\mathcal{G}}}(\cdot,\cdot)$ used to define the ball is the geodesic or shortest path distance (i.e., the distance between two vertices is the minimum number of edges in any path connecting them). Note that this choice of distance measure ignores the weights of the edges and only depends on the unweighted adjacency matrix of the graph.

Let $\widehat{p_{K}}$ be a polynomial kernel with degree $K$; i.e.,

for some coefficients $\{a_{k}\}_{k=0,1,\ldots,K}$. If $d_{{\mathcal{G}}}(i,n)>K$, then $(T_{i}p_{K})(n)=0$.

By [22, Lemma 5.2], $d_{{\mathcal{G}}}(i,n)>K$ implies $({\mathcal{L}}^{K})_{i,n}=0$. Combining this with the fact that

and with the definitions (25) and (30) of the generalized translation and the polynomial kernel, we have

More generally, as seen in Figure 7, if we translate a smooth kernel to a given center vertex $i$, the magnitude of the translated kernel at another vertex $n$ decays as the distance between $i$ and $n$ increases. In Theorem 1, we provide one estimate of this localization by combining the strict localization of polynomial kernels with the following upper bound on the minimax polynomial approximation error.

If a function $f(x)$ is $(K+1)$-times continuously differentiable on an interval $[a,b]$, then

where the infimum in (31) is taken over all polynomials $q_{K}$ of degree $K$.

where the infimum is taken over all polynomial kernels of degree $K_{in}$, as defined in (30). More generally, for $p,q\geq 1$ such that $\frac{1}{p}+\frac{1}{q}=1$,

From Lemma 2, $(T_{i}p_{K_{in}})(n)=0$ for all polynomial kernels $\widehat{p_{K_{in}}}$ of degree $K_{in}$. Thus, we have

where (4.4) follows from Hölder’s inequality, and (35) follows from

Substituting (31) into (35) yields the following corollary to Theorem 1.

If $\hat{g}(\cdot)$ is $d_{in}$-times continuously differentiable on $[0,\lambda_{\max}]$, then

When the kernel $\hat{g}(\cdot)$ has a significant DC component, as is the case for the most logical candidate window functions, such as the heat kernel, then we can combine Theorem 1 and Corollary 2 with the lower bound on the norm of a translated kernel from Lemma 1 to show that the energy of the translated kernel is localized around the center vertex $i$.

Moreover, if $\hat{g}(\cdot)$ is $d_{in}$-times continuously differentiable on $[0,\lambda_{\max}]$, then

If $\hat{g}(\lambda)=e^{-\tau\lambda}$, then $\hat{g}(0)=1$, $\sup_{\lambda\in[0,\lambda_{\max}]}\left|\hat{g}^{(d_{in})}(\lambda)\right|=\tau^{d_{in}}$, and (38) becomes

where the second inequality follows from Stirling’s approximation: $m!\geq\sqrt{2\pi m}\left(\frac{m}{e}\right)^{m}e^{\frac{1}{12m+1}}$ (see, e.g. [26, p. 257]). Interestingly, a term of the form $\left(\frac{C\tau e}{d_{in}}\right)^{d_{in}}$ also appears in the upper bound of [27, Theorem 1], which is specifically tailored to the heat kernel and derived via a rather different approach.

Agaskar and Lu define the graph spread of a signal $f$ around a given vertex $i$ as

We can now use (39) to bound the spread of a translated heat kernel around the center vertex $i$ in terms of the diffusion parameter $\tau$ as follows:

where $\left|{\cal R}(i,r)\right|$ is the number of vertices whose distance from vertex $i$ is exactly $r$. Note that

where the final equality in (2) follows from the Taylor series expansion of the exponential function around zero. While the above bounds can be quite loose (in particular for weighted graphs as we have not incorporated the graph weights into the bounds), the analysis nonetheless shows that we can control the spread of translated heat kernels around their center vertices through the diffusion parameter $\tau$. For any $\epsilon>0$, in order to ensure $\Delta_{i}^{2}(T_{i}g)\leq\epsilon$, it suffices to take

where $\Omega(\cdot)$ is the Lambert W function. Note that the right-hand side of (43) is increasing in $\epsilon$.

In the limit, as $\tau\rightarrow 0$, $T_{i}g\rightarrow\delta_{i}$, and the spread $\Delta_{i}^{2}(T_{i}g)\rightarrow 0$. On the other hand, as $\tau\rightarrow\infty$, $T_{i}g(n)\rightarrow\frac{1}{\sqrt{N}}$ for all $n$, $\lVert T_{i}g\rVert_{2}\rightarrow 1$, and $\Delta_{i}^{2}(T_{i}g)\rightarrow\frac{1}{N}\sum_{n=1}^{N}d_{in}^{2}$.

Generalized Modulation of Signals on Graphs

Note first that, for connected graphs, $M_{0}$ is the identity operator, as $\chi_{0}(n)=\frac{1}{\sqrt{N}}$ for all $n$. In the classical case, the modulation operator represents a translation in the Fourier domain:

We quantify this localization in the next theorem, which is an improved version of [3, Theorem 1].

Given a weighted graph ${\mathcal{G}}$ with $N$ vertices, if for some $\gamma>0$, a kernel $\hat{f}$ satisfies

where the last three inequalities follow from (11), Hölder’s inequality, and (60), respectively. Combining (49) and (5.1) yields (61). ∎

Given a weighted graph ${\mathcal{G}}$ with $N$ vertices, if for some $\gamma>0$, a kernel $\hat{f}$ satisfies (60), then

We lower bound the numerator by squaring (49). We upper bound the denominator as follows:

which follows from squaring (5.1) and from applying the triangle inequality at (48), following the same steps until (49), and squaring the result. ∎

It would also be interesting to find conditions on $\hat{f}$ such that

or such that the spread of $\widehat{M_{k}f}$ around $\lambda_{k}$, defined as either [2, p. 93]

Windowed Graph Fourier Frames

Equipped with these generalized notions of translation and modulation of signals on graphs, we can now define windowed graph Fourier atoms and a windowed graph Fourier transform analogously to (3) and (4) in the classical case.

As with the classical windowed Fourier transform described in Section 2, we can interpret the computation of the windowed graph Fourier transform coefficients in a second manner. Namely, we can first multiply the signal $f$ by (the complex conjugate of) a translated window:

and then compute the windowed graph Fourier transform coefficients as $\sqrt{N}$ times the graph Fourier transform of the windowed signal:

Note that the $.*$ in (54) represents component-wise multiplication.

In Figure 12, we illustrate this alternative interpretation of the windowed graph Fourier transform by first multiplying the signal $f$ of Figure 11(a) by the window $T_{27}g$ (componentwise), and then taking the graph Fourier transform of the resulting windowed signal.

2 Frame Bounds

We now provide a simple sufficient condition for the collection of windowed graph Fourier atoms to form a frame (see, e.g., )

where (6.2) is due to Parseval’s identity, and (56) follows from the symmetry of ${\mathcal{L}}$ and the definition (25) of $T_{i}$. Moreover, under the hypothesis that $\hat{g}(0)\neq 0$, we have

The upper bound on $B$ follows directly from (29). ∎

If $\mu=\frac{1}{\sqrt{N}}$, then $\left\{g_{i,k}\right\}_{i=1,2,\ldots,N;~k=0,1,\ldots,N-1}$ is a tight frame with $A=B=N\lVert g\rVert_{2}^{2}$.

In Table 1, we compare the lower and upper frame bounds derived in Theorem 3 to the empirical optimal frame bounds, $A$ and $B$, for different graphs.

3 Reconstruction Formula

where the last equality follows from (4.3). ∎

In the classical case, $\lVert T_{n}g\rVert_{2}^{2}=\lVert g\rVert_{2}^{2}=1$, so this term does not appear in the reconstruction formula (see, e.g., [7, Theorem 4.3]).

4 Spectrogram Examples

As in classical time-frequency analysis, we can now examine $|Sf(i,k)|^{2}$, the squared magnitudes of the windowed graph Fourier transform coefficients of a given signal $f$. In the classical case (see, e.g., [7, Theorems 4.1 and 4.3]), the windowed Fourier atoms form a tight frame, and therefore this spectrogram of squared magnitudes can be viewed as an energy density function of the signal across the time-frequency plane. In the graph setting, the windowed graph Fourier atoms do not always form a tight frame, and we cannot therefore, in general, interpret the graph spectrogram as an energy density function. Nonetheless, it can still be a useful tool to elucidate underlying structure in graph signals. In this section, we present some examples to illustrate this concept and provide further intuition behind the proposed windowed graph Fourier transform.

In Figure 14(b), in order to make the structure of the signal more evident, we arranged the vertices of the sensor graph on the horizontal axis according to clusters, so that vertices in the same cluster are close to each other. Of course, this would not be possible if we did not have an idea of the structure a priori. A more general way to view the spectrogram of a graph signal without such a priori knowledge is as a sequence of images, with one image per graph Laplacian eigenvalue and the sequence arranged monotonically according to the corresponding eigenvalue. Then, as we scroll through the sequence (i.e., play a frequency-lapse video), the areas of the graph where the signal contains low frequency components “light up” first, then the areas where the signal contains middle frequency components, and so forth. In Figure 15, we show a subset of the images that would comprise such a sequence for the signal from Example 5.

5 Application Example: Signal-Adapted Graph Clustering

We generate a signal $f$ on the 500 vertex random sensor network of Example 1 as follows. First, we generate four random signals $\left\{f_{i}\right\}_{i=1,2,3,4}$, with each random component uniformly distributed between 0 and 1. Second, we generate four graph spectral filters $\left\{\widehat{h_{i}}(\cdot)\right\}_{i=1,2,3,4}$ that cover different bands of the graph Laplacian spectrum, as shown in Figure 16(a). Third, we generate four clusters, $\left\{C_{i}\right\}_{i=1,2,3,4}$, on the graph, taking the first three to be balls of radius 4 around different center vertices, and the fourth to be the remaining vertices. These clusters are shown in Figure 16(b). Fourth, we generate a signal on the graph as

i.e., we filter each random signal by the corresponding filter (to shift its frequency content to a given band), and then restrict that signal to the given cluster by setting the components outside of that cluster to 0. The resulting signal $f$ is shown in Figure 16(c). Fifth, we compute the windowed graph Fourier transform coefficients of $f$ using a window $\hat{g}(\lambda)=e^{-0.3\lambda}$. Sixth, we use a classical trick of applying a nonlinear transformation to the coefficients (see, e.g., [33, Section 3]), and define the vectors $\left\{y_{i}\right\}_{i=1,2,\ldots,N}$ as

with $\alpha=0.75$. Finally, we perform $k$-means clustering on the points $\left\{y_{i}\right\}_{i=1,2,\ldots,N}$, searching for 6 clusters to give the algorithm some extra flexibility. The resulting signal-adapted graph clustering is shown in Figure 16(d).

6 Tiling

Thus far, we have generalized the classical notions of translation and modulation in order to mimic the construction of the classical windowed Fourier transform. We have seen from the examples in the previous subsections that the spectrogram may be an informative tool for signals on both regular and irregular graphs. In this section and the following section, we examine the extent to which our intuitions from classical time-frequency analysis carry over to the graph setting, and where they deviate due to the irregularity of the data domain, and, in turn, the possibility of localized Laplacian eigenfunctions.

First, we compare tilings of the time-frequency plane (or, in the graph setting, the vertex-frequency plane). Recall that Heisenberg boxes represent the time-frequency resolution of a given dictionary atom (including, e.g., windowed Fourier atoms or wavelets) in the time-frequency plane (see, e.g., [7, Chapter 4]). As shown in the tiling diagrams of Figure 17(a) and 17(b), respectively, the Heisenberg boxes of classical windowed Fourier atoms have the same size throughout the time-frequency plane, while the Heisenberg boxes of classical wavelets have different sizes at different wavelet scales. While one can trade-off time and frequency resolutions (e.g., change the length and width of the Heisenberg boxes of classical windowed Fourier atoms by changing the shape of the analysis window), the Heisenberg uncertainty principle places a lower limit on the area of each Heisenberg box.

In Figure 17(c) and 17(d), we use the windowed graph Fourier transform to show the sums of spectrograms of five windowed graph Fourier atoms on a path graph and five spectral graph wavelets on a path graph, respectively. The plots are not too different from what intuition from classical time-frequency analysis might suggest. Namely, the sizes of the Heisenberg boxes for different windowed graph Fourier atoms are roughly the same, while the sizes of the Heisenberg boxes of spectral graph wavelets are similar at a fixed scale, but vary across scales.

In Figure 18, we plot three different windowed graph Fourier atoms – all with the same center vertex – on the Swiss roll graph. Note that all three atoms are jointly localized in the vertex domain around the center vertex 62, and in the graph spectral domain around the frequencies to which they have been respectively modulated. However, unlike the path graph example in Figure 17, the sizes of the Heisenberg boxes of the three atoms are quite different. In particular, the atom $g_{62,983}$ is extremely close to a delta function in both the vertex domain and the graph spectral domain, which of course is not possible in the classical setting due to the Heisenberg uncertainty principle. The reason this happens is that the coherence of this Swiss roll graph is $\mu=0.94$, and the eigenvector $\chi_{983}$ is highly localized, with a value of -0.94 at vertex 62. The takeaway is that highly localized eigenvectors can limit the extent to which intuition from the classical setting carriers over to the graph setting.

7 Limitations

In this section, we briefly discuss a few limitations of the proposed windowed graph Fourier transform.

While the exact computation of the windowed graph Fourier transform coefficients via (52) and (53) is feasible for smaller graphs (e.g., less than 10,000 vertices), the computational cost may be prohibitive for much larger graphs. Therefore, it would be of interest to develop an approximate computational method that scales more efficiently with the size of the graph. Recall that

The quantity $T_{i}g$ in the last term of (59) can be approximately computed in an efficient manner via the Chebyshev polynomial method of [22, Section 6], and therefore $f\left(T_{i}g\right)^{*}$ can be approximately computed in an efficient manner. Thus, if there was a fast approximate graph Fourier transform, we could apply that to the fast approximation of $f\left(T_{i}g\right)^{*}$ in order to approximately compute the windowed graph Fourier transform coefficients $\left\{Sf(i,k)\right\}_{k=0,1,\ldots,N-1}$. Unfortunately, we are not yet aware of a good fast approximate graph Fourier transform method.

7.2 Lack of a Tight Frame

As discussed in Sections 6.2 and 6.4, the collection of windowed graph Fourier atoms need not form a tight frame, meaning that the spectrogram can not always be interpreted as an energy density function. Furthermore, the lack of a tight frame may lead to (i) less numerical stability when reconstructing a signal from (potentially noisy) windowed graph Fourier transform coefficients , or (ii) slower computations, for example when computing proximity operators in convex regularization problems .

7.3 No Guarantees on the Joint Localization of the Atoms in the Vertex and Graph Spectral Domains

Thus far, we have seen that (i) if we translate a smooth kernel $\hat{g}$ to vertex $i$, the resulting signal $T_{i}g$ will be localized around vertex $i$ in the vertex domain (Section 4.4); (ii) if we modulate a kernel $\hat{g}$ that is localized around 0 in the graph spectral domain, the resulting kernel $\widehat{M_{k}g}$ will be localized around $\lambda_{k}$ in the graph spectral domain (Section 5); and (iii) a windowed graph Fourier atom, $g_{ik}$, is often jointly localized around vertex $i$ in the vertex domain and frequency $\lambda_{k}$ in the graph spectral domain (e.g., Figure 18). In classical time-frequency analysis, the windowed Fourier atoms $g_{u,\xi}$ are all jointly localized around time $u$ and frequency $\xi$. So we now ask whether the windowed graph Fourier atoms are always jointly localized around vertex $i$ and frequency $\lambda_{k}$? The answer is no, and the reason once again follows from the possibility of localized graph Laplacian eigenvectors. For a smooth window $\hat{g}$, the translated window $T_{i}g$ is indeed localized around vertex $i$; however, $g_{ik}=\sqrt{N}\chi_{k}.*(T_{i}g)$ may not be localized around vertex $i$ when $\chi_{k}(n)$ is close to zero for all vertices $n$ in a neighborhood around $i$. One such example is shown in Figure 19. Similarly, in order for $\hat{g}_{ik}$ to be localized around frequency $\lambda_{k}$ in the graph spectral domain, it suffices for $\widehat{T_{i}g}$ to be localized around 0 in the graph spectral domain. However,

and, therefore, it is possible that the multiplication by a graph Laplacian eigenvector changes the localization of the translated window in the graph spectral domain. In classical time-frequency analysis, these phenomena never occur, because the complex exponentials are always delocalized.

Despite the lack of guarantees on joint localization, the windowed graph Fourier transform is still a useful analysis tool. First, if the coherence $\mu$ is low (close to $\frac{1}{\sqrt{N}}$), the graph Laplacian eigenvectors are delocalized, the atoms are jointly localized in the vertex and graph spectral domains, and much of the intuition from classical time-frequency analysis carriers over to the graph setting. Even when the coherence is close to 1, however, it often happens that the majority of the atoms are in fact jointly localized in time and frequency. This is because only those atoms whose computations include highly localized eigenvectors are affected. We have observed empirically that there tends to be only a few graph Laplacian eigenvectors, most commonly those associated with the higher frequencies (eigenvalues close to $\lambda_{\max}$). Moreover, if $\chi_{k}$ is highly localized around a vertex $j$, then $Sf(i,k)$ will be close to 0 for any vertex $i$ not close to $j$, so it is not particularly problematic that $g_{ik}$ may not be localized around $i$ in the vertex domain.

Conclusion and Future Work

We defined generalized notions of translation and modulation through multiplication with a graph Laplacian eigenvector in the graph spectral and vertex domains, respectively. We leveraged these generalized operators to design a windowed graph Fourier transform, which enables vertex-frequency analysis for signals on graphs. We showed that when the chosen window is smooth in the graph spectral domain, translated windows are localized in the vertex domain. Moreover, when the chosen window is localized around zero in the graph spectral domain, the modulation operator is close to a translation in the graph spectral domain. If we apply this windowed graph Fourier transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph. The example in Figure 14 shows that the windowed graph Fourier transform may be a valuable tool for extracting information from signals on graphs, as structural properties of the data that are hidden in the vertex domain may become obvious in the transform domain.

One line of future work is to continue to improve the localization results for the translated kernels presented in Section 4.4, preferably by incorporating the graph weights. This issue is closely related to the study of both the localization of eigenvectors and recent work in the theory of matrix functions . In particular, it is related to the off-diagonal decay of entries of a matrix function $g({\mathcal{L}})$, as studied in . To our knowledge, existing results in this area also do not incorporate the entries of the matrix ${\mathcal{L}}$ (other than through the eigenvalues), but rather depend primarily on the sparsity pattern of ${\mathcal{L}}$. For more precise numerical localization results, numerical linear algebra researchers have also turned to quadrature methods to approximate the quantity $\delta_{i}^{*}g({\mathcal{L}})\delta_{j}$ (see, e.g., and references therein).

Motivated by the spirit of vertex-frequency analysis introduced in this paper, we are also investigating a new, more computationally efficient dictionary design method to generate tight frames of atoms that are jointly localized in the vertex and graph spectral domains.

Appendix

where the square root in $\sqrt{d}$ is applied component-wise.

We can keep the definition (16) of the generalized convolution, with the normalized graph Laplacian eigenvalues and eigenvectors replacing those of the combinatorial graph Laplacian. Statements 1-7 in Proposition 1 are still valid; however, (24) becomes

Accordingly, we can redefine the generalized translation operator as

so that Property 3 of Corollary 1 becomes

Because they only depend on the graph structure and not the specific graph weights, the localization results of Theorem 1, Corollary 2, and Corollary 3 also hold, with the constant $\sqrt{N}$ replaced by $\lVert\sqrt{d}\rVert_{2}$ and an extra factor of $\sqrt{d_{i}}$ in the denominator of (37) and (38).

1.2 Generalized Modulation in the Normalized Laplacian Graph Fourier Basis

When we use the normalized Laplacian eigenvectors as a graph Fourier basis instead of the combinatorial Laplacian eigenvectors, we can define a generalized modulation as

Given a weighted graph ${\mathcal{G}}$ with $N$ vertices, if for some $\gamma>0$, a kernel $\hat{f}$ satisfies

1.3 Example: Resolution Tradeoff in the Normalized Laplacian Graph Fourier Basis

Next, our localization result on the generalized modulation, Theorem 5, tells us that

The normalized graph Laplacian eigenvalues of a graph ${\mathcal{G}}$ satisfy

where for every subset ${\mathcal{V}}_{1}\subset{\mathcal{V}}$, $\delta$, the isoperimetric dimension of ${\mathcal{G}}$, and $c_{\delta}$, the isoperimetric constant, satisfy

and $C_{\delta}$ is a constant that only depends on $\delta$.

Combining (63) and (64), for a fixed $\tau$,

Comparing (65) and (66) to (62), we see that as the diffusion parameter $\tau$ increases, our guarantee on the localization of $\widehat{M_{k}g}$ around frequency $\lambda_{k}$ in the graph spectral domain improves, whereas the guarantee on the localization of $T_{i}g$ around vertex $i$ in the vertex domain becomes weaker, and vice versa.

2 Alternative Definition of Generalized Modulation

A second option is to define $f$ on the spectrum $\sigma(\check{L})$. For example, in Figure 21, we let $\hat{\hat{f}}(\check{\lambda}_{j})=e^{\check{\tau}\check{\lambda}_{j}}$, and then modulate again via (67). One advantage of defining the kernel in this manner is that we can more easily characterize the spread of the modulated kernel in the graph spectral domain of ${\mathcal{G}}$, using, e.g., our translation localization results from Section 4.4. For example, with $\hat{\hat{f}}(\cdot)$ a heat kernel and $\check{G}$ a weighted path graph (which has a maximum Laplacian eigenvalue upper bounded by 4) as in Figure 21, the bound (2) becomes

which is close to form of the desired bound on the spread of modulated kernels we mentioned in (51), especially for a graph ${\mathcal{G}}$ whose spectrum is close to uniformly distributed on $[0,\lambda_{\max}]$.

References

References