ARL-TR-8276 • FEB 2018

US Army Research Laboratory

Signal Processing for Time-Series Functions

on a Graph

by Humberto Muñoz-Barona, Jean Vettel, and

Addison Bohannon

Approved for public release; distribution is unlimited.
NOTICES

Disclaimers

The findings in this report are not to be construed as an official Department of the

Army position unless so designated by other authorized documents.

Citation of manufacturer’s or trade names does not constitute an official endorsement or approval of the use thereof.

Destroy this report when it is no longer needed. Do not return it to the originator.
ARL-TR-8276 • FEB 2018

US Army Research Laboratory

Signal Processing for Time-Series Functions

on a Graph

by Humberto Muñoz-Barona

Southern University and A&M College, Baton Rouge, LA

Jean Vettel and Addison Bohannon

Human Research and Engineering Directorate, ARL

Approved for public release; distribution is unlimited.
REPORT DOCUMENTATION PAGE Form Approved

OMB No. 0704‐0188

Public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the

data needed, and completing and reviewing the collection information.  Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing

the burden, to Department of Defense, Washington Headquarters Services, Directorate for Information Operations and Reports (0704‐0188), 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202‐

4302.  Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to any penalty for failing to comply with a collection of information if it does not display a

currently valid OMB control number.

PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS.

1. REPORT DATE (DD‐MM‐YYYY) 2. REPORT TYPE 3. DATES COVERED (From ‐ To)

4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER

5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

6. AUTHOR(S) 5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION REPORT

NUMBER

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S)

11. SPONSOR/MONITOR'S REPORT NUMBER(S)

12. DISTRIBUTION/AVAILABILITY STATEMENT

13. SUPPLEMENTARY NOTES

14. ABSTRACT

15. SUBJECT TERMS

16. SECURITY CLASSIFICATION OF:   17. LIMITATION

       OF  

       ABSTRACT

18. NUMBER

       OF  

        PAGES

19a. NAME OF RESPONSIBLE PERSON

a. REPORT b. ABSTRACT c. THIS PAGE 19b. TELEPHONE NUMBER (Include area code)

Standard Form 298 (Rev. 8/98)

Prescribed by ANSI Std. Z39.18

February 2018 Technical Report

Signal Processing for Time-Series Functions on a Graph

Humberto Muñoz-Barona, Jean Vettel, and Addison Bohannon

ARL-TR-8276

Approved for public release; distribution is unlimited.

June-September 2017

US Army Research Laboratory

ATTN: RDRL-HRF-B

Aberdeen Proving Ground, MD 21005-5066

primary author’s email: <addison.w.bohannon.civ@mail.mil>.

Previous research introduced signal processing on graphs, an approach to generalize signal processing tools such as filtering to

functions supported on graphs. These methods can be applied to scalar functions with a domain that can be described by a fixed

weighted undirected graph. We consider here time-series functions supported on a fixed, weighted, undirected graph and show

that an extension to the approach of Shuman et al. does not generalize to this problem, but rather suffers from a catastrophic loss

of temporal information in the signal during convolution operations. Finally, we propose alternative signal processing

approaches to time-series functions on a fixed graph.

signal processing, network neuroscience, machine learning, network science, graph theory

28

Addison W Bohannon

Unclassified Unclassified Unclassified UU (410) 278-8974

ii
Approved for public release; distribution is unlimited.

Contents

List of Figures iv

Acknowledgments v

1. Introduction 1

2. Mathematical Background 3

2.1 Hilbert Spaces 3

2.2 Fourier Analysis 4

2.3 Spectral Graph Theory 5

3. Graph Signal Processing 8

4. Results 9

4.1 Hilbert Spaces of Time-Series Signals 9

4.2 Graph Differential Operators of Time-Series Signals 10

4.3 Constructing the Graph Fourier Transform 11

4.4 Graph Convolution for Time-Series Signals 13

5. Discussion 13

6. Conclusion 14

7. References 16

Distribution List 19

iii
Approved for public release; distribution is unlimited.

List of Figures

Fig. 1 Time-series function on a fixed graph.............................................2

iv
Approved for public release; distribution is unlimited.

Acknowledgments

This research was supported by mission funding to the US Army Research Laboratory (Jean Vettel and Addison Bohannon) and through a Faculty Fellowship from

the Thurgood Marshall College Fund (Humberto Muñoz-Barona). The views and

conclusions contained in this report are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the US

Government.

v
Approved for public release; distribution is unlimited.

INTENTIONALLY LEFT BLANK.

vi
Approved for public release; distribution is unlimited.

1. Introduction

In many real-world systems, the most interesting behavior emerges from complex

interactions between the constituent elements.1 These systems arise in applications

as varied as neuroimaging, transportation networks, and social media use. In these,

and many other applications, the relationship between elements of the network (or

nodes) can be described by connections (or edges) that capture similarity, coherence, or functionality.2

In order to understand these emergent behaviors, we require

analytical approaches that respect the relational information between elements of

these interacting systems.3

Over the last 6 years, developing novel methods to analyze time-evolving network

dynamics of brain activity has been a strong component of the US Army Research

Laboratory’s (ARL’s) ongoing research in translational neuroscience.4 This emphasis reflects a theoretical movement from traditional neuroimaging approaches that

focused on the computational processing of segregated areas of the brain to a set

of innovative network science approaches to investigate the dynamic communication among brain regions.5,6 Across the 84 billion neurons in the brain,7 networks

are dynamically forming and dissolving to connect the localized neural ensembles

that perform specialized computational processing as global networks that integrate

across regions in support of time-evolving task activity to enable human behavior.8,9 Thus, to understand the complex dynamics of neural processing, methods

must preserve the spatio-temporal properties that embody what brain regions are

communicating and when in intricately timed interaction. The burgeoning field of

network neuroscience leverages a graph theoretic approach from network science,

where the component parts of a system (nodes) are connected based on their pairwise interactions (edges) in a graph.10 We will leverage this formalism here since

it facilitates the study of brain activity by preserving the underlying geometry of

the data. However, since we are interested in time-evolving network dynamics, we

cannot rely on traditional approaches that capture scalar signals supported on the

nodes of a graph; instead, we consider time-series functions supported on the nodes

of a graph.

Graph signal processing has been proposed as a method to analyze functions with an

irregular domain that can be described by a weighted graph.11,12 These approaches

consider scalar functions supported on the vertices of a graph and adapt tools from

1
Approved for public release; distribution is unlimited.

classical signal processing such as filtering to account for the graph domain. This

work essentially divides into 2 basic approaches: graph Laplcian-based filtering

and weighted adjacency matrix-based filtering. In Shuman et al.,11 and elaborated

in Bronstein et al.,13 filtering operators are polynomials of the graph Laplacian of

the graph domain, while in Sandryhaila and Moura,12 filtering operators are polynomials of the weighted adjacency matrix of the graph domain. At the time of this

project, graph Laplacian-based methods have elicited greater use and adoption in

the scientific literature and have recently been successfully applied in various deep

learning frameworks.13

In this report, we assess the possibility of extending the techniques of Shuman et

al.11 to the more general problem of time-series functions on the vertices of a fixed

weighted undirected graph (see Fig. 1). The rest of the report is outlined as follows.

In Section 2, we review the mathematical background necessary for graph signal

processing, namely Hilbert spaces, Fourier analysis, and spectral graph theory. In

Section 3, we present the graph signal processing approach from Shuman et al.11

In Section 4, we present our original work, extending the approach of Shuman et

al.11 to time-series functions on a fixed graph. In Section 5, we discuss the results of

this effort. We find that a direct extension of the approach will not generalize to the

problem of time-series functions on a graph. Rather, the temporal information that

we hope to retain is instead lost because the graph Fourier basis does not form an

orthonormal basis for the space of functions in which we are interested. In Section 6,

we discuss alternative approaches to address this failure by extending the approach

of Sandryhaila and Moura12 or deliberately constructing an orthonormal basis for

the functions.

Fig. 1 Time-series function on a fixed graph

2
Approved for public release; distribution is unlimited.

2. Mathematical Background

Graph signal processing leverages spectral graph theory to extend classical signal

processing operations such as filtering to functions that have irregular domains that

can be described by graphs. These methods depend heavily on theory from Hilbert

spaces, Fourier analysis, and spectral graph theory. We present here the necessary

mathematical background.

2.1 Hilbert Spaces

Hilbert spaces provide the abstract vector space in which functions exist, and it is in

this space that the tools of signal processing act on functions. We define some basic

definitions relating to Hilbert spaces and provide motivating examples.

Definition 2.1. A Hilbert space is a real vector space H with an inner product hf, gi

such that H is complete in the induced norm, kfk =

p

hf, fi.

Example 2.2. L

2

(R) = {f : R → R|kfk < ∞}, with inner product hf, gi =

R ∞

−∞ f(x)g(x)dx is an infinite-dimensional Hilbert space.

Definition 2.3. An orthonormal basis of a Hilbert space H is a sequence {xn}

N

n=1,

N ∈ N, with hxn, xmi = δnm (δnm = 1 if n = m and 0 otherwise), ∀n, m ∈ N such

that x ∈ H has a unique representation x =

PN

n=1hx, xnixn, where xn are distinct

elements.

Example 2.4. The set of functions {e

iwt : w ∈ R} is an orthonormal basis for

L

2

(R) called the standard Fourier basis.

Hilbert spaces make analysis of complicated mathematical objects more intuitive.

In a vector space such as R

n

, the canonical basis (i.e., e1 = [1, 0, . . . , 0]T, . . . , en =

[0, . . . , 0, 1]T where ·

T

is the usual matrix transpose) forms an orthonormal basis.

This construction allows all vectors in the vector space to be represented as linear

combinations of a fixed set of canonical vectors. Similarly, the Euclidean distance

(i.e., kx−yk

2 =

Pn

i=1 xiyi) allows us to measure distance between any 2 vectors in

the vector space. Together, these 2 concepts simplify the analysis of vectors. Hilbert

spaces generalize these concepts to spaces of functions and other abstract objects.

Fourier analysis depends heavily on these concepts to provide an orthonormal basis

for arbitrary functions.

3
Approved for public release; distribution is unlimited.

2.2 Fourier Analysis

Classical signal processing leverages the results of Fourier analysis to deconstruct

functions into simpler trigonometric functions for processing steps such as filtering.

We present the definition of the Fourier transform, inverse Fourier transform, and

convolution along with the convolution theorem.

A Fourier transform represents a time-series as a linear combination of complex

exponential functions in the frequency domain, and the inverse Fourier transform

reassembles the frequency components into a time-series. The Fourier transform

and inverse Fourier transform provide invertible mappings between the time representation of a signal and the frequency representation of a signal.

Definition 2.5. The Fourier transform of a function f ∈ L

1

(R) is defined as

F(f(t)) = ˆf(ω) = Z ∞

−∞

f(t)e

−iωtdt, for ω ∈ R. (1)

Definition 2.6. The inverse Fourier transform is defined by

F

−1

(

ˆf(ω)) = f(t) = 1

2π

Z ∞

−∞

ˆf(ω)e

iωtdω, for t ∈ R. (2)

Implicit in the definition of the Fourier transform is the inner product from L

2

(R)

and the basis function e

iωt. The Fourier transform is the projection of f onto basis

functions indexed by frequency.

The convolution operation provides another basic building block for classical signal

processing.

Definition 2.7. A convolution operation ∗ : L

2

(R)×L

2

(R) → L

2

(R) is defined by

(f ∗ g)(x) = Z ∞

−∞

f(y)g(x − y)dy, for x ∈ R. (3)

An important property of the convolution is captured in the following, a standard

result of Fourier analysis14 :

Theorem 2.8. (Convolution Theorem) Convolution of two functions in the time do4
Approved for public release; distribution is unlimited.

main is equivalent to multiplication in the frequency domain

F[f(t) ∗ g(t)] = F(f)(w) · F(g)(w) = ˆf(w) · gˆ(w). (4)

This is a helpful tool in frequency filtering where we choose filter functions (i.e., g

in the definition of the convolution) to either amplify or attenuate contributions from

the frequency components of a signal (i.e., f in the definition of the convolution).

Often, gˆ(·) is referred to as the transfer function of the filter, and when combined

with the Convolution theorem, filtering can be performed by the following:

fout(t) := (fin ∗ g)(t) = F

−1

(

ˆfin(w) · gˆ(w)). (5)

2.3 Spectral Graph Theory

Graphs provide the topology for arbitrary objects through pair-wise similarity. These

relationships build a discrete geometry for data that does not necessarily conform to

Euclidean geometry. Spectral graph theory concerns the spectral content (eigenvalues and eigenvectors) of these graphs. Here, we define a graph, review some basic

properties, and derive the graph Laplacian and its spectral properties.

Definition 2.9. A weighted undirected graph G is defined as the triple (V, E, W),

where V = {1, . . . , n} is the set of vertices, E = {{i, j} : i, j ∈ V} is the set of

edges, and W is the n×n symmetric adjacency matrix of the edge weights wij ≥ 0

for {i, j} ∈ E.

A graph is principally made up of vertices, which represent the objects of interest.

We capture relationships between objects by connecting them with edges, where

the strength of each edge (the weight) represents the similarity of the connected

objects. The pair-wise similarity (or near-ness) of objects induces a unique geometry on the domain. Other common properties of graphs are the degree matrix and

neighborhood.

Definition 2.10. The degree matrix is defined as D = diag(d1, . . . , dn) where di = P

j:j6=i wij .

Definition 2.11. The neighborhood of a vertex is the set of vertices connected to

vertex i by an edge, Ni = {j ∈ V|i 6= j, {i, j} ∈ E}.

5
Approved for public release; distribution is unlimited.

The neighborhood definition given is general. For our purposes, the neighborhood

of a node includes all other nodes in the graph. We can also weight vertices to

convey the relative importance of vertices. These weights also become important in

developing either the un-normalized or normalized graph Laplacian.

Definition 2.12. The vertex weight matrix is defined by A = diag(a1, . . . , an)

where ai ≥ 0 ∈ R for all i ∈ V.

Next, we build spectral graph theory by considering functions defined on a graph.

We begin with defining a Hilbert space for these functions.

Definition 2.13. Let `

2

(V) = {f : V → R : kfk`

2(V) < ∞} be the Hilbert space

with the following inner product:

hf, gi`

2(V) =

X

i∈V

aifigi (6)

and induced norm kfk`

2(V) =

p

hf, fi`

2(V)

.

Definition 2.14. Let `

2

(E) = {F : E → R : kfk`

2(E) < ∞} be the Hilbert space

with the following inner product:

hF, Gi`

2(E) =

X

{i,j}∈E

wijFijGij (7)

and induced norm kFk`

2(E) =

p

hF, Fi`

2(E)

.

Then, we use concepts from discrete calculus to define a difference operator that

acts on these functions.

Definition 2.15. Let f ∈ `

2

(V). The graph gradient operator ∇ : `

2

(V) → `

2

(E)

is defined as

(∇f)ij = fj − fi. (8)

Together with the Hilbert space on the edges of the graph, the graph gradient allows

us to examine the Dirichlet energy of a function on the graph.

Definition 2.16. The Dirichlet energy of f ∈ `

2

(V) is defined as

S(f) = 1

2

k∇fk

2

`

2(E)

. (9)

6
Approved for public release; distribution is unlimited.

The Dirichlet energy measures the smoothness of functions by summing the gradient (or tendency of the function to change) over the entire domain. This idea is

borrowed from statistical physics in which low-energy states are more likely (and

more stable) than high-energy states. Importantly, if we define the adjoint of the

gradient (∇∗), we can write the Dirichlet energy as a quadratic function of f.

S(f) = 1

2

k∇fk

2

`

2(E)

=

1

2

h∇f, ∇fi

2

`

2(E)

=

1

2

hf, ∇∗∇fi

2

`

2(E)

=

1

2

hf, ∆fi

2

`

2(E)

where ∆ = D − W is known as the un-normalized graph Laplacian. We note that

S(f) = 0 if and only if f is constant across all vertices, and S(f) is small when f

has similar values at neighboring vertices connected by an edge with a large weight

(i.e., when it is smooth).

We may be interested in finding smooth functions f ∈ `

2

(V). We know that the

subspace of constant functions minimizes the Dirichlet energy, but what about nontrivial functions that minimize the Dirichlet energy? One procedure for finding such

functions would be to constrain the subspace of functions to be orthogonal to the

subspace of constant functions and minimize the Dirichlet energy within this subspace. We could further ask for another subspace of functions orthogonal to that

subspace that minimizes the Dirichlet energy, and repeat this process until we have

|V| orthogonal functions. This procedure can be posed concisely in the following

optimization problem:

min

Φ∈Rn×n

tr(ΦT ∆Φ)  ̃ s.t. Φ

TΦ = I (10)

where ∆ =  ̃ A−1(D − W) is the un-normalized graph Laplacian if A = I and the

normalized graph Laplacian if A = D.

13 This optimization problem is solved by an

eigendecomposition of the normalized graph Laplacian, ∆ = ΦΛΦ  ̃ T.

7
Approved for public release; distribution is unlimited.

3. Graph Signal Processing

Now that we have established the mathematical tools, we review the approach of

Shuman et al.11 to extend classical signal processing tools to functions with a graph

domain. We begin with generalizing the Fourier transform and inverse Fourier transform. Then, we use the convolution theorem to define the convolution.

As described in Eq. 1, the Fourier transform is a projection onto an orthonormal basis. This leads us to seek an orthonormal basis for `

2

(V). We note that the normalized graph Laplacian ∆ ̃ is a symmetric matrix, so it has real nonnegative eigenvalues and a complete set of orthonormal eigenvectors that span R

n

. Further, we can

associate these eigenvectors with a notion of frequency (or smoothness) because

smaller eigenvalues are associated with eigenvectors, or modes, of lower Dirichlet

energy. Thus, the eigendecomposition of the graph Laplacian provides us an orthonormal basis for `

2

(V) that can be partially ordered with respect to frequency

(or smoothness). In Shuman et al.,11 associating the Fourier basis with the graph

Laplacian eigenbasis provides the means by which we extend signal processing

techniques to functions which occur on graphs.

Let Φ = [φ0, . . . , φn−1] be the graph Fourier (eigen) basis of the graph Laplacian.

Definition 3.1. The graph Fourier transform of a discrete signal f ∈ `

2

(V) is

defined as

ˆfi = hf, φiiL2(V)

. (11)

Definition 3.2. The graph inverse Fourier transform is defined as

f =

Xn−1

i=0

ˆfiφi

. (12)

Now, we address the convolution. A direct extension is impossible because the definition of the convolution requires a translation operator and such an operation is

meaningless on an unordered set of vertices. Therefore, Shuman et al.11 proposes

to use the convolution theorem as a definition for the convolution. This bypasses

the translation hurdle by using the previously defined Fourier and inverse Fourier

transform.

8
Approved for public release; distribution is unlimited.

Definition 3.3. The graph convolution ∗g : L

2

(V) × L

2

(V) → L

2

(V) is defined as

f ∗g g := Xn−1

i=0

(hf, φiiL2(V)hg, φiiL2(V))φi (13)

or equivalently,

f ∗g g = Gf := Φdiag(ˆg)ΦTf, (14)

where gˆ = (ˆg(λ1), . . . , gˆ(λn)) is the spectral representation of g.

4. Results

Our problem is such: we want to process signals {fi ∈ L

2

(R)}i∈V that occur on the

vertices of a fixed graph G. We imagine distinct functions with a fixed spatial topology captured by the graph. Shuman et al.11 considers scalar functions on the vertices

of the graph, but here we follow their approach and extend it as necessary to define

filtering and convolution operations. We begin with defining the Hilbert space and

difference operators for such functions. Then, we compute an orthonormal basis,

with which we generalize the Fourier and inverse Fourier transform.

4.1 Hilbert Spaces of Time-Series Signals

Functions on a bounded time domain, T = [0, τ ], have a natural Hilbert space.

Definition 4.1. Let L

2

(T ) = {f : T → R : kfk < ∞} be the Hilbert space with

the following inner product:

hf, gi =

Z

T

f(t)g(t)dt. (15)

Here, we consider a set of time-series functions f = {fi ∈ L

2

(T ) : i ∈ V}. We

use the inner product from the Hilbert space for the time domain within the inner

product from the graph domain. This provides the following Hilbert spaces:

Definition 4.2. Let L

2

(V × T ) = {f : V × T → R|kfk < ∞} be the Hilbert space

with the following inner product:

hf, giL2(V×T ) =

X

i∈V



ai

τ

Z

T

fi(t)gi(t)dt. (16)

9
Approved for public release; distribution is unlimited.

Definition 4.3. Let L

2

(E × T ) = {f : E × T → R|kfk < ∞} be the Hilbert space

with the following inner product:

hF, GiL2(E×T ) =

X

{i,j}∈E



wij

τ

Z

T

Fij (t)Gij (t)dt. (17)

4.2 Graph Differential Operators of Time-Series Signals

We follow Bronstein et al.13 to define the graph differential operators on the Hilbert

spaces L

2

(V × T ) and L

2

(E × T ).

Definition 4.4. The graph gradient operator ∇T : L

2

(V × T ) → L

2

(E × T ) of a

signal f ∈ L

2

(V × T ) is defined as

(∇T f)ij (t) := fj (t) − fi(t). (18)

Definition 4.5. The graph divergence operator divT : L

2

(E × T ) → L

2

(V × T ) of

a function F ∈ L

2

(E × T ) is defined as

(divT F)i(t) = 1

ai

X

j:{i,j}∈E

wijFij (t). (19)

We verify that the graph gradient is the adjoint of the graph divergence.

Theorem 4.6. The graph gradient is the adjoint of the graph divergence.

10
Approved for public release; distribution is unlimited.

Proof.

hF, ∇T fiL2(E×T ) =

X

{i,j}∈E

wij

τ

Z τ

0

Fij (t)(∇f)ij (t)dt

=

X

{i,j}∈E

wij

τ

Z τ

0

Fij (t)[fj (t) − fi(t)]dt

=

X

{i,j}∈E

wij

τ

Z τ

0

Fij (t)fj (t)dt −

X

{i,j}∈E

wij

τ

Z τ

0

Fij (t)fi(t)dt

=

X

{i,j}∈E

wji

τ

Z τ

0

(−Fji(t))fj (t)dt −

X

{i,j}∈E

wij

τ

Z τ

0

Fij (t)fi(t)dt

=

X

{i,j}∈E

wij

τ

Z τ

0

(−Fij (t))fi(t)dt

=

X

i∈V

1

τ

Z τ

0

X

j:{i,j}∈E

wij (−Fij (t))fi(t)dt

=

X

i∈V

1

τ

Z τ

0

1

ai

X

j:{i,j}∈E

aiwij (−Fij (t))fi(t)dt

= h−divT F, fiL2(V×T )

We have assumed that F is conservative (i.e., Fij = −Fji), as it is in the case of a

gradient, and used the symmetry of W (i.e., wij = wji).

4.3 Constructing the Graph Fourier Transform

As in spectral graph theory, we can seek the functions that minimize the Dirichlet

energy:

ST (f) = 1

2

k∇fk

2

L2(E×T )

(20)

=

1

2

X

{i,j}∈E

wij

τ

Z

T

(∇f)ij (t)(∇f)ij (t)dt (21)

=

1

2τ

Z

T

X

{i,j}∈E

wij (∇f)ij (t)(∇f)ij (t)dt (22)

=

1

τ

Z

T

1

2

k(∇f)(t)k

2

`

2(E)

dt (23)

=

1

τ

Z

T

S[f(t)]dt (24)

11
Approved for public release; distribution is unlimited.

The Dirichlet energy for the time-series function is the integral of the instantaneous

energy. A similar result is obtained from the orthogonality constraint. Let Φ =

[φ0, . . . , φn−1] where φi ∈ L

2

(V × T ) for all i ∈ V.

hφi, φj iL2(V×T ) =

X

k∈V

ak

τ

Z

T

(φi(t))k(φj (t))kdt (25)

=

1

τ

Z

T

X

k∈V

ak(φi(t))k(φj (t))kdt (26)

=

1

τ

Z

T

hφi(t), φj (t)i`

2(V)dt (27)

We see that if 2 functions are orthogonal in `

2

(V) at each time instance, then they

are orthogonal in L

2

(V × T ).

In both the objective and constraints of the optimization problem, there is independence over time. The minimum is achieved by instantaneously minimizing the

Dirichet energy with respect to the orthogonality constraint. We observe that the

graph Fourier basis is obtained by continuously solving an eigenproblem over time.

min

Φ(t)∈Rn×n

tr(Φ(t)

T ∆Φ(  ̃ t)) s.t. Φ(t)TΦ(t) = I (28)

Furthermore, since G is not time-varying, Φ(t) = Φ is a constant with respect to

time.

We can now define our graph Fourier transform:

Definition 4.7. The graph Fourier transform of a time-series signal f ∈ L

2

(V × T )

is defined as

ˆfi(t) = hf, φiiL2(V×T )

(29)

=

X

j∈V

aj

τ

Z

T

fj (t)(φi)jdt (30)

=

X

j∈V

aj



1

τ

Z

T

fj (t)dt(φi)j (31)

=

X

j∈V

aj

 ̄fj (φi)j (32)

= h

 ̄f, φii`

2(V)

(33)

12
Approved for public release; distribution is unlimited.

where we use φi(t) = φi for all i ∈ V and t ∈ T and  ̄f is the average of f over T .

Definition 4.8. The graph inverse Fourier transform of a time-series signal ˆf is

defined as

f(t) = Xn−1

i=0

1

τ

Z

t∈T

ˆfi(t)φidt. (34)

4.4 Graph Convolution for Time-Series Signals

Finally, we can construct the convolution as done in Shuman et al.11

Definition 4.9. The graph convolution ∗T : L

2

(V × T )×L

2

(V × T ) → L

2

(V × T )

is defined as:

f ∗T g := Xn−1

i=0

(hf, φiiL2(V×T )  hg, φiiL2(V×T ))φi. (35)

5. Discussion

There is a fundamental problem in this construction of the convolution. The convolution theorem depends on the invertibility of the Fourier transform by the inverse

Fourier transform. However, we observe a loss of information through the proposed

graph Fourier transform. Let us consider a function f ∈ L

2

(V × T ). Given its spectral representation ˆf, we should be able to recover f exactly by the inverse graph

Fourier transform.

f(t)

?=

Xn−1

i=0

1

τ

Z

t∈T

ˆfi(t)φidt (36)

?=

Xn−1

i=0

1

τ

Z

t∈T



hf, φiiL2(V×T )



φidt (37)

?=

Xn−1

i=0

1

τ

Z

t∈T



h

 ̄f, φii`

2(V)



φidt (38)

?=

Xn−1

i=0

h

 ̄f, φii`

2(V)φi (39)

6=  ̄f (40)

Instead, we simply recover the average of f over time.

13
Approved for public release; distribution is unlimited.

This result is not only unsatisfying but also wholly insufficient. We set out to treat

the time domain simultaneously with the irregular spatial domain, but in doing so,

we ultimately still lost all but first-order information in the time domain. We can

now recognize that this straight-forward extension of the approach in Shuman et

al.11 did not result in the construction of an orthonormal basis as in the case of

scalar functions on a fixed graph. {φi}i∈V does not span L

2

(V × T ), a necessary

condition for the Fourier transform to be invertible.

6. Conclusion

We have evaluated the possibility of extending the approach proposed in Shuman

et al.11 for signal processing of scalar functions supported on a fixed graph domain

to the case of time-series functions supported on a fixed graph domain. Following

a similar construction of the Fourier and inverse Fourier transform and convolution operations, the result is insufficient. All but first-order information from the

temporal domain is lost within the convolution. A straight-forward extension of the

approach failed to yield an orthonormal basis, but this points to a path forward.

Our future work will investigate 2 alternative approaches. In the first, we will investigate extending the approach proposed in Sandryhaila and Moura12 where timeseries signals (discretely sampled functions) can be considered directed graphs in

which time samples can be represented by nodes that are connected only to adjacent time samples in a directed (causal) manner. In the second, we will consider

methods that yield an orthonormal basis by design. We recognize that these timeseries functions exist in a Hilbert space that is itself the composition of Hilbert

spaces with known orthonormal bases. We want to use Fourier basis functions to

represent the temporal information in our functions while retaining the spatial basis functions that capture the geometry of our domain. Thus, we could use constructive techniques to deliberately assemble an orthonormal basis for this Hilbert

space of time-series functions on graphs by considering functions from either a

direct sum (i.e., L

2

(V × T ) = L

2

(T ) ⊕ . . . ⊕ L

2

(T )) or tensor product (i.e.,

L

2

(V × T ) = `

2

(V) ⊗ L

2

(T )) of Hilbert spaces.

Immediate future applications will focus on the analysis of neuroimaging data using

these graph signal processing approaches. This approach provides an opportunity

to identify novel spatio-temporal features of the data that provide insight about the

underlying brain network dynamics. While these features in and of themselves may

14
Approved for public release; distribution is unlimited.

have interesting interpretation within the field of network neuroscience, they can

also be used in conjunction with machine learning approaches to identify brain dynamics that can predict fluctuations in performance, providing an opportunity to

advance the state-of-the-art from previous ARL research.15–18 More generally, this

approach is not limited to applications on neuroimaging data, and it can also provide important contributions to understanding time-evolving network across a host

of additional Army-relevant domains, including diverse domains such as communication networks, sensor networks, and social networks.

15
Approved for public release; distribution is unlimited.

7. References

1. Simon HA. The architecture of complexity. Proceedings of the American

Philosophical Society. 1962;106(6):467–482.

2. Vettel J, Dagro A, Gordon S, Kerick S, Kraft R, Luo S, Rawal S, Vindiola M,

McDowell K. Brain structure-function couplings (FY11). Aberdeen Proving

Ground (MD): Army Research Laboratory (US); 2012 Feb. Report No.: ARLTR-5893.

3. Fortunato S. Community detection in graphs. Physics Reports.

2010;486(3):75–174.

4. Vettel JM, McKee PJ, Dagro A, Vindiola M, Yu A, McDowell K,

Franaszczuk PJ. Scientific accomplishments for arl brain structure-function

couplings research on large-scale brain networks from FY11–FY13 (DSI Final

Report). Aberdeen Proving Ground (MD): Army Research Laboratory (US);

2014 Mar. Report No.: ARL-TR-6871.

5. Alivisatos AP, Chun M, Church GM, Greenspan RJ, Roukes ML, Yuste R. The

brain activity map project and the challenge of functional connectomics. Neuron. 2012;74(6):970–974.

6. Bullmore E, Sporns O. Complex brain networks: graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience.

2009;10(3):186–198.

7. Azevedo FA, Carvalho LR, Grinberg LT, Farfel JM, Ferretti RE, Leite RE,

Filho WJ, Lent R, Herculano-Houzel S. Equal numbers of neuronal and nonneuronal cells make the human brain an isometrically scaled-up primate brain.

The Journal of Comparative Neurology. 2009;513(5):532–541.

8. Friston KJ. Functional and effective connectivity in neuroimaging: A synthesis. Human Brain Mapping. 1994;2(1-2):56–78.

9. Sporns O, Tononi G, Edelman GM. Theoretical neuroanatomy: Relating

anatomical and functional connectivity in graphs and cortical connection matrices. Cerebral Cortex. 2000;10(2):127–141.

10. Bassett DS, Sporns O. Network neuroscience. Nature Neuroscience.

2017;20(3):353–364.

16
Approved for public release; distribution is unlimited.

11. Shuman DI, Narang SK, Frossard P, Ortega A, Vandergheynst P. The emerging

field of signal processing on graphs: Extending high-dimensional data analysis

to networks and other irregular domains. IEEE Signal Processing Magazine.

2013;30(3):83–98.

12. Sandryhaila A, Moura JM. Discrete signal processing on graphs. IEEE Transactions on Signal Processing. 2013;61(7):1644–1656.

13. Bronstein MM, Bruna J, LeCun Y, Szlam A, Vandergheynst P. Geometric

deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine. 2017;34(4):18–42.

14. Reed M, Simon B. Methods of modern mathematical physics. New York

(NY): Academic Press; 1980.

15. Lawhern VJ, Solon AJ, Waytowich NR, Gordon SM, Hung CP, Lance BJ.

EEGNet: a Compact Convolutional Network for EEG-based Brain-Computer

Interfaces. arXiv preprint arXiv:1611.08024; 2016.

16. Yeh FC, Vettel JM, Singh A, Poczos B, Grafton ST, Erickson KI, Tseng WYI,

Verstynen TD. Quantifying differences and similarities in whole-brain white

matter architecture using local connectome fingerprints. PLOS Computational

Biology. 2016;12(11).

17. Muraskin J, Sherwin J, Lieberman G, Garcia JO, Verstynen T, Vettel JM,

Sajda P. Fusing multiple neuroimaging modalities to assess group differences

in perception-action coupling. Proceedings of the IEEE. 2017;105(1):8–100.

18. Waytowich NR, Faller J, Garcia JO, Vettel JM, Sajda P. Unsupervised adaptive transfer learning for steady-state visual evoked potential brain-computer

interfaces. In: 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC); 2016 ; Budapest, Hungary. IEEE; 2016. p. 4135–4140.

17
Approved for public release; distribution is unlimited.

INTENTIONALLY LEFT BLANK.

18
Approved for public release; distribution is unlimited.

1

(PDF)

DEFENSE TECHNICAL

INFORMATION CTR

DTIC OCA

2

(PDF)

DIR ARL

IMAL HRA

RECORDS MGMT

RDRL DCL

TECH LIB

1

(PDF)

GOVT PRINTG OFC

A MALHOTRA

2

(PDF)

RDRL-HRF-B

A BOHANNON

J VETTEL

19
Approved for public release; distribution is unlimited.

INTENTIONALLY LEFT BLANK.

20