MAPS_GSTH_part_II

June 18, 2024

Information

ID: 11814
To Cite: DCA Citation Guide

Download Transcript

00:00Today is the second lecture,
00:03second presentation in our series and
00:06I'm very excited to introduce Rahul Sai.
00:12Rahul is an expert in advanced
00:15statistical method including graph theory,
00:18network analysis,
00:19neural network signal processing
00:22and many other impressive terms.
00:25He received the PhD in machine
00:29learning in Georgia Institute of
00:31Technology and now he is a post
00:34doctoral researcher in Wosai Institute.
00:39And I'm not going to take
00:41any more time from you.
00:43Please, it's all yours.
00:46Thank you, Helen. Hello everyone.
00:49I'm Rahul Singh, welcome to the
00:53second lecture of this workshop.
00:56And today I'm going to talk
00:59about graph signal processing.
01:01It's like extending the classical
01:04signal processing techniques
01:05over manifolds or graphs.
01:11A little bit about me,
01:12I started my academic journey back
01:17in India where I studied the signal
01:21processing from Indian Institute
01:23of Space Science and Technology.
01:26And then I went to Iowa State University,
01:29where I got my master's
01:31degree in image processing.
01:33And then I went on for my
01:35doctoral studies at Georgia Tech,
01:37where I got my PhD in machine learning.
01:40And here my most along the line,
01:43my research was in signal processing,
01:46extending the signal processing
01:48techniques to graphs and especially
01:50using the structure in the data and how
01:53we can process the data that that has
01:57some intrinsic structure behind it.
01:59And here I am a post doctor fellow
02:02at Woosa Institute and I'm doing,
02:05I'm applying this machine learning
02:07and signal processing methods
02:09in computational neuroscience.
02:11And my mentors are Smita Krishnaswami
02:15from computer science and Joy
02:18Hirsch from neuroscience.
02:23Moving on to our main toolbox that we
02:28are in the process to learn geometric
02:33scattering trajective homology.
02:36So as Tenanje last week has
02:41given an introduction about it,
02:44there are four steps here.
02:46So any data that is residing on a
02:49manifold or if you have just the data,
02:51the first step to create the manifold
02:54or the graph that this graph creation.
02:57And then we apply this graph signal
03:01processing tools to represent
03:03the data lying on this graph.
03:06And then we do some non,
03:08some dimensionality reduction techniques
03:10to visualize these trajectories
03:13of the data that evolve over time.
03:16And we analyze these trajectories
03:19using topological data analysis that
03:22Tananjay talked about last week.
03:24So step four we covered last week.
03:27Today we are going to cover step two,
03:29that is how to process the data
03:32lying on a graph.
03:34And once after today's lecture
03:37in the third series,
03:40Dhananjay and Brian are going to
03:43combine these two techniques to give
03:46you a overall picture of this geometric
03:50scattering trajectory homology.
03:53So let's move on to the second Step,
03:542, graph signal processing.
03:56So what is this graph signal
03:58processing about?
04:02Mostly we in general we have seen
04:05there are many tools and concepts
04:08that have been developed in classical
04:10signal processing domain where we deal
04:13with data that is in form of a time
04:17series for example, speech, music,
04:20e.g, FM, RI, whatever
04:24or we also
04:25deal with images.
04:27So these are the signals or the data.
04:32For example, this here is a speech
04:34signal and this is speech signal is
04:36for some let's say for 10 seconds.
04:38And we can see that once we
04:42sample this data digitally,
04:44then this is nothing but some
04:47values at each time point.
04:50And if you look at these values and look
04:53at the structure behind these values,
04:55it is just a very linear looking structure.
04:59So T1 time T1 is related to T2T2
05:04is related to TT three because when
05:07you speak it's related with time.
05:10And in images,
05:11the data or the signal that constitute
05:14this image is nothing but this
05:17RGB values at lying on this grid.
05:21So each pixel of this image is a data
05:24value lying on this particular blue node.
05:27And once we kind of arrange these
05:30intensity values of each pixels,
05:33it takes a form of an image.
05:36So in classical signal processing,
05:38we deal with this kind of regular data.
05:40Regular in the sense the structure
05:42behind the data is very regular.
05:45Regular means if you see this
05:48graph here or little structure
05:50that is behind this data is just
05:54one-dimensional path graph and the
05:58image of image values are lying
06:00on this two-dimensional grid.
06:04And in classical signal processing
06:06there are other concepts like our
06:08tools like modulation and translation,
06:13frequency analysis and all.
06:15For example. Why do we need this?
06:17What is this modulation?
06:19If you connect your thoughts to your radio
06:24or even the cable TV or even cell phones,
06:27they are working on different
06:30frequencies and the data is around like
06:33it's it's in the air it it has it is
06:37being sent in form of electromagnetic
06:40waves through multiple antennas.
06:42But all the data,
06:43like if you look at if you're sitting
06:45in your room there you have Wi-Fi data,
06:47your phone data, or even FM,
06:52A FM radio, whatever.
06:53But now you need to kind of
06:56select what you want to receive.
06:58And in order to select that,
07:00there is a concept called modulation.
07:02So you kind of modulate
07:05your voice band frequencies.
07:06For example, somebody's talking,
07:08the frequencies are just
07:10within like 3.2 kilohertz,
07:12but you kind of
07:16shift this frequency to higher frequency
07:18so that it becomes easy to transmit the
07:22data because the antenna size is always
07:28proportional to the wavelength.
07:30So modulating to high frequencies
07:33makes the antenna sizes smaller.
07:35Another concept very familiar is filtering.
07:38Let's say you have some data in the air
07:41and you want to denoise the data because
07:43the data when you send from an antenna,
07:46it gets very noisy from very
07:50from many other signals around.
07:52And with the process the
07:54concept is filtering.
07:55You want to remove the noise or
07:58or kind of smoothen the data,
08:00then you need this filtering operation.
08:03So these are basic operations that
08:06we do in classical signal processing.
08:09But what if the data that we
08:12are dealing with is very lying
08:14on a very irregular setting?
08:17Like for example,
08:18here consider a graph or a
08:22where the each node,
08:24so each blue circle here we can we
08:27call it as a node and each red link
08:30here is we call it as an edge or a link.
08:35And these edges are representing the
08:38relationship or the proximity or the
08:41connectedness of these two nodes or
08:44entities or these two spatial points.
08:47These can these nodes can
08:49be different brain regions.
08:51It can be a person in a social
08:55network and all we will see another
08:57some many examples of this later.
09:01Yeah. So for example here in a brain region,
09:06let's say you are recording F nears or fMRI,
09:11then what it does at the end is
09:14different brain regions have a
09:17time series associated with it.
09:20And today we are not going to take this
09:25time domain information into into account.
09:28What we are going to do is at one
09:31time point we have data collected
09:34from each of the region of the brain
09:37and we want to analyse that data,
09:40develop some tools existing in
09:42classical signal processing to
09:44this irregular structure.
09:45Because brain is like,
09:47it's not like a 2D grade.
09:48It's like in A33 dimensional
09:51space where there are different
09:53structural regions that talk,
09:55talk with each other or send
09:58information from one region to another.
10:01How do we capture that information
10:04in the data and kind of get
10:08better representation?
10:09Some other examples include
10:13some other examples of this graph.
10:15Signals are like some temperature
10:17or pressures recorded at
10:20different geographical locations.
10:22Or it can be a social network
10:24created by Facebook, Twitter,
10:25or it can be a transportation network.
10:28For example, here this is a map of,
10:30I believe Minnesota and and at
10:35each node it can be like a traffic
10:38junction where the signal can be the
10:43kind of how many cars are passing
10:46through that traffic and all.
10:48And it can be traffic at traffic at each
10:51computer node in a computer network.
10:54So whenever you can,
10:55we you see this connectivity
10:58information around you.
10:59There are features associated with
11:01each entity or each node here.
11:04And we want to process such data.
11:08So what are the difficulties
11:10that rise when we talk about this data
11:13lying on a very complex structure?
11:16So if it is A1 dimensional time series,
11:19you can easily shift the signal,
11:20translate the signal.
11:21But then when we talk about in
11:24graph signal processing settings
11:25where the data is very irregular,
11:28then how do we translate or how
11:30we move from one node to another?
11:33Because there are so many nodes
11:35around you that are connected
11:36to you and there is no kind,
11:38there is no concept of moving from one
11:41point to another in a systematic way.
11:45So how, how do we like what,
11:49what kind of tools that can help
11:51to analyze this data properly?
11:53In order to motivate that,
11:56let's look at any time series data
11:591st and then we will relate this to
12:02graph signal processing settings.
12:04So for example,
12:05let's say you have this time series
12:08with you which is a combination of
12:10some some sinusoids or it can be
12:13some combination of many sinusoids.
12:15So here this X is a combination of
12:18these three sinusoids with amplitude
12:21B1B2 and B3 and different frequencies
12:25Omega 1, Omega two and omega-3.
12:28So these frequencies.
12:29So if the frequency is higher,
12:31that means your signal is changing
12:34very rapidly rapidly.
12:35So this omega-3 is higher than
12:37Omega two and Omega one.
12:39So signal is changing very rapidly
12:42and this Omega one is a small so the
12:46signal is very smooth changing very slowly.
12:50So in order to represent this data
12:55either you can save this whole time
12:57series and process this process and do
13:00your processing on this time series
13:03directly or what you can do is you
13:05can convert this data in a different
13:08domain called frequency domain where
13:11this Fourier transform comes handy.
13:14So Fourier transform is nothing but
13:16decomposing any time series in terms
13:21of different frequency sinusoids.
13:24So here if you just take the
13:27Fourier transform of the signal XT,
13:29you will see that there are
13:31only three frequency components
13:33present with different amplitude
13:35or different weights Omega 1,
13:37Omega two and omega-3.
13:40So to represent this signal XT
13:43the same amount of the the same
13:46information can be represented
13:48in this different domain called
13:51Fourier domain or frequency domain.
13:54And here in frequency domain,
13:57as you can see,
13:58you just need three need to save
14:01only Omega 1, Omega two,
14:03omega-3 and corresponding amplitudes.
14:06But in order to save this XT in a machine,
14:08you have to save a lot of values
14:10and it doesn't provide that very
14:12nice frequency intuition as well.
14:15And converting this data to
14:17another domain has some advantages.
14:20It,
14:20it is used in filtering operations
14:23and it and the information and also
14:26all the communication systems are
14:29built around this frequency concept.
14:32So we want to extend the same kind
14:35of frequency interpretation of this
14:37time series data to graph signals.
14:44So how do we do that? So first, let's
14:50talk about some notations here
14:51that I'm going to be using.
14:56And before that, if you have any
14:58questions, feel free to stop me.
15:01And Helen also, if you will see
15:03something in chat, please let me know.
15:06Yes, I'm, I'm watching the questions. Yes.
15:11So notation. So we have a graph here.
15:13We have like 5 node graph
15:1812345. It can be five
15:20different brain regions.
15:22It can be five different geographical
15:25locations in a sensor network.
15:28It can be in a tissue if you if
15:31you can image the cells and all,
15:34it can be each cell and this red,
15:37red lines here are edges or links.
15:41So four is connected to five,
15:43which can be for example in a brain network,
15:45let's say your frontal region connected
15:50to the this temporal parietal
15:53junction or any other you can imagine,
15:56whichever is like in proximity or
15:58there is any other relationship,
16:00we find an edge.
16:02So in order to create a graph,
16:04you can always kind of take
16:06the proximity into account and
16:08create and create these edges.
16:10And then each edge also has
16:13a feature associated with it.
16:15For example, at time point T1,
16:19each of the brain regions will
16:21have some value associated with it
16:24recorded by EGF nears or or F MRI.
16:26It doesn't matter.
16:28And we are just looking at 1:00
16:31time slice of this whole brain
16:34region recording and we are calling
16:36it as a graph signal.
16:38And in order to store this graph
16:40signal information in the machine,
16:42we need to store the graph,
16:45the connectivity and we need to store
16:49this signal values associated with each node.
16:53So when we talk when we talk about
16:56storing this graph in the machine,
16:58we can just store this weight matrix.
17:01What is this weight matrix?
17:03Weight matrix is a is a matrix that is
17:08telling you the relationship between
17:10different nodes or different regions.
17:13So for example here if you see node
17:15two is connected to node three,
17:18node one and node 5.
17:21So if you look at the 2nd row
17:23of this weight matrix 2.
17:25If you look at the 2nd row and
17:28the first column, it is one.
17:30That means this is representing
17:32connection between node two and node one.
17:35Then this diagonal entry is
17:370 because there is.
17:39This is like a self loop two to two.
17:41There is nothing there.
17:43Then the 2nd row and 3rd column
17:45has entry one.
17:47That means node two is connected to node 3,
17:51then fourth entry as well
17:53as fifth entry are one.
17:54That means two is also connected
17:56to four as well as five.
17:58So this connectivity information
18:00you can store in this weight matrix
18:04and then the features associated
18:07with each node we can store
18:11using this vector or signal F.
18:15And then based on this weight matrix,
18:16there are some other matrices defined like
18:19some degree matrix and Laplacian matrix.
18:22What is this degree matrix?
18:24So degree matrix is the
18:26strength of edges in each node.
18:29So for example in node three,
18:31it is connected to three neighbors.
18:35So if if you look at the
18:37third entry here it is 3.
18:40If you look at node 5 then it
18:43is connected to two of the
18:45nodes node two and node four.
18:48So the 5th entry here is 2.
18:51So it is saying you how many.
18:53It is telling you how many edges
18:55are connect, are in are incident
18:57incidenting on a particular node.
18:59It's a diagonal matrix.
19:01And then there is another matrix
19:04called Laplacian matrix which is
19:08nothing but the difference between the
19:11degree matrix and the weight matrix.
19:16So this Laplacian is a very important
19:19matrix for us because as we'll
19:22further see that this Laplacian of
19:25this graph is going to tell us a lot
19:29about the variations in the signals of
19:31variations in the data across the space.
19:35So we are representing graph as G and
19:37this V is nothing but a set of vertices.
19:41So we have like 5 vertices or nodes here
19:4512345 here West is the weight matrix.
19:48So let's go further and look at
19:51the graph Laplacian again closely.
19:56So we have this particular graph here.
19:58This is our graph Laplacian.
20:00As you can see,
20:02it is symmetric because there is no
20:05directionality information or anything.
20:07It is a symmetric matrix and if you look
20:10at the off diagonal entries which are
20:16sorry the diagonal entries which are
20:18nothing but the D the degree values.
20:21And if you look at the off diagonal
20:23entries that are some non positive
20:27or negative values there because it
20:30is coming from this D minus West.
20:33And also if you see the rows are
20:37summing to zero 2 -, 1 -, 1 is 0.
20:41Similarly any other row and it's also
20:45positive positive semi definite matrix.
20:48So if you are not familiar with semi
20:51definite so it is a matrix whose
20:54eigen values are always non negative.
20:58We will talk about this more
21:00and later slides
21:04then what this Laplacian gives us.
21:08Let's oh, before that,
21:11let's talk a little bit about what
21:14is eigen values and eigenvectors
21:15of a matrix R So let's say you have
21:19a matrix like just an N cross.
21:21And for example, here,
21:22this is just a matrix of four entries
21:27and the eigenvectors are those vectors.
21:32If you operate this matrix on,
21:35the direction is not going to change either.
21:38It's going to be scaled,
21:40but the direction is not going to change.
21:42For example, here if you see so AU,
21:46if U is an eigenvector of a matrix A,
21:50then it is just scaled by a factor Lambda,
21:54which is a scalar value called eigenvalue.
21:59So in this first figure here,
22:00if you see the vector 10,
22:04if you just multiply matrix
22:07A and this vector 10,
22:09you can see that you can write it as
22:13scaled version of this vector itself.
22:16This is the eigen value here 2.
22:19So it is it is just scaled from
22:211:00 to 2:00 here and similarly
22:23another eigen value which is -1 here.
22:27So if you look at this vector one and -3,
22:32then if you just multiply A to this vector,
22:37it is going to be stretching
22:39in the other direction,
22:40but the direction is not going to change.
22:45Then given a matrix squared matrix,
22:48of course there are we are we are
22:52introducing these two quantities,
22:54eigen values and eigen vectors.
22:57So eigen values are scalars.
22:59So if A is a N cross N matrix then
23:03you will have N number of eigenvalues
23:06and N number of eigenvectors as well.
23:10So let's do Then what is the use of this
23:14eigenvalues and eigenvectors in our context?
23:18In our context, when we want to
23:21analyze the data lying on a graph,
23:24these eigenvalues and eigenvectors provide
23:27us the intuition of frequency in graph
23:30domain as we will see in next slides.
23:33So given a graph we use a term called
23:39spectrum or sometimes frequency.
23:41So eigenvalues of the Laplacian matrix,
23:44we call it as graph spectrum and eigen.
23:49And these eigenvectors that
23:52we just arrange in columns.
23:55So we have these four nodes here.
24:03Actually there is a little mistake here.
24:07This particular graph,
24:07this Laplacian is not corresponding
24:09to this particular graph.
24:11But I'll, I'll, I'll clarify it later.
24:14So using these eigenvalues and eigenvectors,
24:19how do we define this Fourier transform?
24:22So if you look at the
24:24classical Fourier transform,
24:25we have a time series XT.
24:27If you if we want to define
24:29the Fourier transform of this,
24:30we just use this complex exponentials
24:34or sinusoids because you can
24:37always decompose this complex
24:39exponential into sines and cosines.
24:41And this is the frequency here Omega.
24:44So usually when you see in FM
24:47it's like megahertz or in you
24:49in your in your voice signal,
24:52it is in kilohertz and all and you
24:57are decomposing the signal XT in
24:59terms of this frequency coefficients.
25:02Similarly, in our graph settings,
25:05what we can do is we can decompose
25:08our signal,
25:09a graph signal which is lying on the
25:12vertices or the nodes of the graph
25:14using these eigenvectors of the Laplacian.
25:18So you just compute the eigenvectors
25:20of the Laplacian and then use them to
25:25compute this graph Fourier transform.
25:30So any given graph you have a feature
25:34associated with each vertex vertex.
25:36You apply graph Fourier transform on
25:40this and you get to represent the same
25:45information that is contained in the
25:48data lying on a graph in this graph
25:51frequency domain where this lambdas
25:54are nothing but the eigenvalues of
25:57the graph Laplacian that you can
25:59think it of as just frequencies.
26:01The the like the omegas in classical domain
26:09like cosines, whatever Omegas
26:10that is related that is the
26:12analogous to the graph frequencies
26:14that we are talking about here.
26:16And for each frequency there will
26:19be an associated number called graph
26:23Fourier transform coefficient.
26:25So it is saying that in this
26:28signal or in this data you have
26:31some content of frequency 1,
26:33Omega some or Lambda some content
26:36of frequency 2-3 and so on.
26:41And I'm going to skip
26:43this frequency ordering,
26:45but let let's look at a closer
26:48look into this graph in this
26:51eigenvectors of this Laplacian.
26:53So this is a six node graph.
26:54So I have plotted this six
26:57eigenvectors on top of this.
26:58So if you look at the very first eigenvector,
27:01use zero, which is corresponding
27:04to the lowest eigenvalue.
27:06So sometimes we call this eigenvectors as
27:09harmonics or like you can relate it to
27:13sinusoids in classical signal processing.
27:15So if you look at U0, there's no change.
27:18It's like a constant signal across the graph.
27:21So if you move from node one to three to six,
27:25there's no change.
27:26It's like a constant signal.
27:27There's no change at all if you look at U1.
27:32So if you move from node one to two,
27:35you can see it's like positive to negative.
27:37So you can see a little something
27:39like sine wave occurring here if
27:41you move from one node to another.
27:44So if you move from node 2 to one 2-3,
27:47you can see that it's going
27:49from negative values,
27:51it's going to positive values.
27:52So it's like change,
27:54it is the changing change
27:57across the space is increasing.
27:59And if you look at the eigen vector
28:03corresponding to the largest eigen value,
28:07the change is even like larger.
28:09So if you look at this node,
28:12two to five positive, negative,
28:14then five to four positive, negative.
28:16So the changes are very rapid here.
28:19So the if you look at from U0 to U5,
28:23the change in the signal or change
28:25in this data lying on this,
28:27each node is increasing.
28:30That means these are the harmonics.
28:33We can treat this as a harmonic
28:36like sine waves.
28:37So here there's no change,
28:39a little bit change,
28:40very smoothly varying signal towards
28:43very rapidly changing signal.
28:45And we want to represent our data in terms
28:48of these eigenvectors or graph harmonics.
28:54Do we have any questions at this point? I
29:03just want to follow up and make
29:06sure they understand correctly.
29:08So essentially I can various
29:15just weights on certain ordinate functions.
29:20For instance, if we had the
29:22simple 3 dimensional space,
29:24right, linear, linear, linear,
29:26then we have coordinates in each
29:29space and we have a vector and we
29:32can define this vector much easier.
29:34And here it is pretty much the
29:37same but more complex basis.
29:39So you have this
29:44different types of changes and you
29:49effectively decompose your signal
29:51which can have any kind of shape
29:56and form in the weighted sum of
30:00this more simple type of signals.
30:05Yes, exactly. And it is also providing
30:08the intuition of variations,
30:09how quickly it is changing,
30:11how slowly it is changing accordingly.
30:14Yeah. So you started with this sinusoid,
30:17which was more complicated than
30:21just a simple axis, Jakarta's axis.
30:25And this is more complex than sinusoid
30:28because you have more complex, Yes.
30:30So in sinusoids we had just one dimension
30:33time it was changing across that.
30:35But here we have like very
30:37irregular dimension here.
30:38So it's like non Euclidean
30:40space and still the changes are
30:43according to the connectivity.
30:44So if we move from one node,
30:46the nearby nodes,
30:47how smoothly or how rapidly
30:50my information is varying,
30:51that is kind of provides a sense
30:55of frequency or variability
30:57in this irregular graph.
31:03OK, so let's move on.
31:06So another important thing to notice
31:10here is that we have numbered this,
31:14we have numbered this graph like the we
31:19have assigned #1 to this particular node.
31:21We have assigned #4 to this particular node.
31:24What what if we kind of scramble these
31:28numbers like we can like change node
31:32three to node one and accordingly
31:37the the structure is not changing,
31:40but the representation might change.
31:42So for example, let's look at this.
31:45What the effect of this vertex
31:47indexing or node indexing,
31:49how it changes the graph harmonics
31:52or signal representations.
31:53So we start with again a very simple,
31:57very small graph.
32:00We have this graph here,
32:02we have this weight matrix here.
32:04So here sometimes
32:08it is beneficial to assign a
32:12scalar value to each of the edges
32:15as well or each of the links.
32:18So when we assign a scalar value here,
32:21that means how well connected
32:24node two and node three are.
32:27So if you compare in this particular
32:29figure here node two and node 3,
32:31the connectivity strength is .2 as
32:34compared to node three and four where
32:37the connectivity strength can be .7.
32:39So this can be for example
32:42in your computer networks,
32:44sometimes it can reflect the bandwidth
32:46how much of data one link can carry.
32:50So you can assign weights accordingly.
32:56And in a social network,
32:57sometimes you can say, OK,
33:00this is my best friend versus
33:02friend versus just acquaintances.
33:03So they're the, even though you,
33:05you are friend with you are
33:07friends on social network,
33:09but it's still there are some kind
33:12of weights are associated with your
33:15relationship with your relationship with
33:18other people in the social network as well.
33:21So this weight matrix here
33:23instead of the 011 entries,
33:26there are weights associated here.
33:28So for example the 1st
33:30row and the second column,
33:31the entries .3 that means
33:34node one and node 2.
33:36The connection strength is .3.
33:39And accordingly you can fill in
33:41this matrix and then you can compute
33:44this Laplacian matrix using this
33:47degree minus W which turns out to be
33:49this and then you can compute these
33:52eigen values and eigen vectors.
33:54So let us look at a very nice property
33:57of this Laplacian matrix here.
33:59As you will see the first eigen value
34:03is always going to be 0 always and
34:08the other eigen values are going to
34:11be like non negative eigen values.
34:16That is why it is called positive
34:18semi definite matrix and why this
34:21first eigenvalue is 0 because
34:23this rows are summing to zero.
34:26And also if you look at the first
34:29eigenvector which is the first
34:31column in this big matrix U,
34:33it is just point 5.5.
34:35It's like not changing.
34:36So that's what I was showing here.
34:38There's no change that is U0.
34:41So this is an eigenvector corresponding
34:44to this eigenvalue zero in the
34:47second column here is the eigenvector
34:49corresponding to the eigenvalue
34:52here and the third eigenvector
34:56corresponding this eigenvalue 4th
34:581 corresponding to this eigenvalue.
35:00So the information in the data
35:03in the graph we have represented
35:05the information in terms of these
35:09eigenvalues and eigenvectors.
35:11Once we have these eigenvalues and
35:15eigenvectors and always remember that
35:17this eigenvalues are nothing but the
35:20frequencies and this U's are nothing.
35:23They are analogous to the sinusoids
35:26of different frequencies.
35:27And once we have that we can do some
35:31frequency analysis on this graphs.
35:34So if you look at this vertex
35:39ordering here again.
35:41So this is just first case.
35:42Here I have just plotted all
35:44the four eigen vectors here.
35:46The first one is of course constant.
35:49But if what if?
35:54What if We want to represent this signal.
35:57So we have at node 1A value of five,
36:02at node 2A value of two node 3A value of 6,
36:06at node four we have a value of nine.
36:09And we want to represent this
36:11signal as a combination of these
36:14harmonics or the eigen vectors.
36:16So this signal F1 which is a vector here
36:21can be represented as a linear combination
36:24of these eigen vectors of this laplacian.
36:28And these coefficients are nothing but
36:31the graph Fourier transform coefficients.
36:34So I need 11 worth of weight of
36:39first eigen vector negative point
36:421.83 weighted second eigenvector and
36:44accordingly this is the weight of the
36:47third eigenvector and I can represent
36:50the signal and so I have decomposed
36:53the signal in these four frequency in
36:56terms of these four frequency harmonics.
36:58So it is saying that I have as
37:04compared to the low frequencies.
37:05I have high frequency information
37:08as well here.
37:10And if I change the vertex ordering here,
37:15so here this one became four and
37:19what if I just represent 11 here?
37:22So if you write down the Laplacian,
37:25it is going to change.
37:26So it is going to be a permuted.
37:28So in the second, in the second-half,
37:30when we change the order ordering here,
37:33this Laplacian is going to be a permuted
37:37version of this Laplacian on the left.
37:39But the representation here changed.
37:43And if I compute,
37:45but if I compute these eigenvalues,
37:47as you can see,
37:49just write down the Laplacian,
37:50compute the eigenvalues,
37:52it's going to be similar in exactly
37:55the same in both the cases.
37:56It doesn't matter how you order
37:59these vertices.
38:00And if you look at these eigenvectors,
38:03first one is constant.
38:04If you look at the 2nd eigenvector,
38:06it's just a permutation.
38:08So node one became node 4.
38:12So if you look at the 4th,
38:16the 1st value here,
38:18it went to the 4th value here.
38:20So it just permuted accordingly.
38:22So in this case,
38:24we don't have to worry about
38:26the ordering of these vertices.
38:30So again, if I plot these,
38:33all the eigenvectors,
38:34you can see first one is constant
38:37node ordering orderings are
38:39different in these two cases.
38:41But you see the association here the the
38:46eigenvectors are also permuting accordingly.
38:49So what does that tell us?
38:51So it tells us that no matter
38:54what how you order the vertices,
38:58your representation in the frequency
39:01domain is not going to change at all.
39:04So if you look at the signal here,
39:07so 5269.
39:07So why is five in the first entry here?
39:11Because node one or this particular
39:15region in the brain has a value of five.
39:18That's why 5 here.
39:19And these are the corresponding
39:21eigen vectors.
39:22These are the Fourier coefficients
39:24as you can see see in both cases
39:27F1 and F2 which are exactly the
39:29same information but with different
39:31vertex ordering or node ordering.
39:33But there's no change in the
39:36Fourier domain as.
39:37So it doesn't matter which ordering you use.
39:41Again, I think this is a repetition
39:43of the same concept here.
39:44Again, this another case,
39:47there's no change in the in the signal
39:51representation frequency domain.
39:52So the message here is that
39:55when we order the vertices 1234,
39:59it doesn't matter.
40:00We can just take the, take the,
40:03we can just write down the Laplacian
40:06and compute the eigenvalues and
40:09eigenvectors that will correspond
40:11to the graph frequencies and graph
40:14harmonics or graph sinus or as you can
40:18call it and and there's no change in
40:20the frequency domain representation.
40:25Now once we have this sort of frequency
40:32interpretation of our data lying on a graph,
40:38we want to define some other concepts
40:41like convolution, modulation,
40:42translation that are very basic operations
40:45in classical segment processing.
40:48But how do we do, how do we define
40:51these kind of concepts in graph domain?
40:54So all the all the all these concepts
40:57are defined in the graph domain with
41:00the help of graph Fourier transform.
41:03All of it is based on the
41:05graph Fourier transform.
41:05So the basic building block is going
41:07to be the Fourier transform here.
41:09So again we have a graph here and
41:12we have Laplacian and its eigen
41:14values and eigen vectors shown here.
41:17And let's say I had two different
41:21signals or two different data points
41:24lying on this this same graph.
41:28How do I convolve these two graph signals?
41:32So the way it is done is what we do
41:37is first compute the graph Fourier
41:40transform of the 1st signal F here,
41:42then compute the graph Fourier
41:45transform of the 2nd signal G here,
41:48do point wise multiplication and
41:51then take the inverse transform that
41:54is define that is going to be your
41:58convolve signal H so F convolve.
42:02So F convolve with G gives us this
42:06H signal here and this convolution
42:10operation in classical signal processing,
42:12this convolution operation is also
42:14called like filtering operation where
42:16this can be your original signal and
42:18this can be your filter or a kernel.
42:20How are we you going to come
42:23compute this convolved product?
42:24That is how you do it in graph domain.
42:28And another side information here is
42:31that this basic operation of graph
42:35convolution which is started from the
42:38intuition of this with graph Fourier
42:40transform was the base is the basic
42:43building block of graph neural networks.
42:45If you've heard of that graph
42:47neural networks and there are
42:50many other architectures proposed,
42:53simplified architectures proposed based on
42:55the same concept here the graph convolution.
43:02So why are we defining these concepts?
43:04So because these concepts are going to help
43:07us to represent the signal that we have
43:12at each time point.
43:14That's why we are discussing
43:15this these concepts and this
43:18is another graph translation.
43:20How are we going to define
43:22the graph translation?
43:23I believe we can skip it.
43:25It's not that important here in our context.
43:28But the message here is that if you
43:31want to define these classical signal
43:34processing concepts in graph domain,
43:38graph Fourier transform is the way
43:40that helps us to theoretically
43:42define these concepts.
43:44Otherwise because of this irregular
43:47structure is irregular structure of
43:49this this graph that prohibits us to
43:52kind of extend the concepts directly.
43:55But then graph Fourier transform
43:57comes into picture and eases our
44:00theoretical understanding of
44:01this data lying on this complex
44:04network irregular structures.
44:11So this is a table which is
44:13comparing the the signal processing
44:16concept side by side here.
44:18So this is Fourier transform.
44:21In Fourier transform sinusoids
44:23or complex exponentials are our
44:26basis and we kind of represent our
44:29signal as a linear combination
44:32of these sinusoids and same.
44:35Similarly the graph in graph signal
44:40processing we represent our signal F as A
44:46as a linear combination of the
44:48eigenvectors of the graph Laplacian
44:50and convolution sum we defined
44:54through graph Fourier transform.
44:56Then similar. Similarly you can
44:58define translation and modulation
45:01using this graph Fourier transform.
45:05SO question, I think this table
45:09really helps me to understand
45:11what question I have because you
45:13kind of put everything together.
45:19What I assume, and I need you to
45:22correct me if I'm right or wrong,
45:25is that graph signal processing
45:29gives us better approximation of
45:32complex signals because it has richer
45:38like basic function,
45:40richer set of basic function.
45:42Or is there any other advantage if
45:44you compare this classical signal
45:46processing with graph signal processing,
45:48What is the key advantage here?
45:51Yeah. So first of all,
45:53these concepts here,
45:54you cannot define in the
45:57graph domain directly.
45:59So whatever we see in the first,
46:01in the second column here,
46:02the classical signal,
46:04these concepts are not applicable
46:05directly in graph domain.
46:07You can't define it because of the
46:09irregular structure of the graph.
46:11So you're talking about pretty much
46:14behaviour of signal in one node versus
46:17behaviour or signal multiple nodes.
46:19That's the biggest difference.
46:21Oh, yes, exactly. OK, OK, thank
46:23you. Yeah, yeah.
46:25And in classical signal crossing,
46:27the graph is always the same.
46:29It's like T1T2T3T4,
46:31it's arranged by time. It's not.
46:34Images are arranged by a
46:36very nicely spatial location.
46:37You look at the images like from X to Y,
46:40it's very nicely arranged.
46:42But here if you change the graph,
46:45everything changes.
46:46If you change the graphic structure,
46:48everything changes.
46:49So it's like behaviour,
46:52the time behaviour at one node
46:54versus time behaviour if you want
46:56to combine the all the different
46:58regions together and if you want to
47:00consider the information coming from
47:02my neighbours in the brain regions.
47:04So I have to take this into
47:06account using this graph
47:08signal processing techniques.
47:10So basically dimensionality component,
47:13right? So not necessarily complexity,
47:15but it's more about how much
47:18information you can describe.
47:20Yeah, this is space can be another dimension
47:23if you can look at it. Yeah, thank you.
47:33OK,
47:35so this is a very interesting example
47:39of graph Fourier transform how it
47:43can be helpful and it can give us the
47:47information lying in the data directly
47:50like with a just very little effort,
47:54you can find the find some of the
47:58structure in the data easily.
48:00So this is a sensor net sensor network.
48:02So this is a map of United States,
48:05Florida, we are somewhere here.
48:08So this is just each node is
48:14representing geographical location
48:17and the connectivity of the nodes
48:19is based on the the geography
48:22like the the nodes are connected,
48:26the two geographical locations
48:28are connected by these links if
48:30they are close to each other like
48:33for example this California is
48:34not connected to the East Coast.
48:36So only this California regions
48:39based on the distance between
48:41the geographical locations,
48:44you can connect these nodes.
48:46And once you have this nodes and
48:50connectivity information and you
48:52have this temperature readings
48:54at at one time point you have
48:58temperature readings of all the these
49:02sensors distributed across the US.
49:06As you can see S is little
49:08hotter than the north.
49:09But this is just one time slice.
49:13And let's say some sensors
49:16are malfunctioning,
49:17they are not giving you the correct reading.
49:19So by the nature of the data here,
49:22it is smooth data.
49:23What what does this smooth means here?
49:26If you move from 1 geographical location
49:29to a nearby geographical location,
49:32the temperature change
49:33is not going to be much.
49:35So temperature in New York is more or
49:37less going to be temperature in New Haven,
49:39but it is going to it can be very
49:42different from the temperature
49:44in Texas or Florida or Arizona.
49:46But let's say some sensors
49:49are men malfunctioning.
49:51So if it is malfunctioning,
49:54it is going to destroy this
49:55smoothness structure in the data.
49:57So if you just,
49:59if let's say the sensor network is perfect,
50:03if you take the Fourier graph,
50:05Fourier transform of the data here
50:08you will see all the you will see low
50:12frequency components are dominant here.
50:15There are no high frequency components.
50:17Why?
50:17The same reason the temperature is
50:19not going to change rapidly if you
50:21move from 11 geographical location to other.
50:24But if the sensor is malfunctioning,
50:26then what you will see is there
50:29will be like a spike in high
50:32frequency where you will you can
50:35tell that the temperature changed
50:37by a significant amount if I move
50:40from New Haven to Hartford,
50:42which is usually not the case.
50:44So if you just take the Fourier
50:47transform of one time point and if
50:49you get a high frequency spikes,
50:51you can tell there are some sensors
50:53in this sensor network that are not
50:56performing well that are malfunctioning.
50:58But can we pinpoint which which
51:03sensor is not is is malfunctioning?
51:15Do we have any answers?
51:17You can think of it a little bit
51:26not based on this, based on this
51:30graph, just looking at this graph,
51:32yeah. So if one sensor is malfunctioning,
51:35can we tell like not based on the in general.
51:39I have a one slice of temperature
51:41readings all over the US and I
51:44take the graph Fourier transform.
51:45I see a high frequency spike here.
51:50Then that tells me that there is an issue.
51:53There is an issue in in the network,
51:55but this doesn't tell me
51:57where exactly the issue is.
52:00So this graph Fourier transform
52:02is a global transform.
52:04Global in the sense it captures the frequency
52:08information globally lying on the graph.
52:10It cannot pinpoint where exactly the
52:14those graph frequencies are changing,
52:17where exactly in the space that is going on.
52:19It just tells you there is a change.
52:21I don't know where there is a change.
52:23There is this high frequency or low
52:25frequency information in the graph,
52:26but I don't know where in the space.
52:29So that is kind of a limitation
52:31of this Fourier transform,
52:32but it's still
52:33is it, is it, is it something you can,
52:35for instance, answer by iteratively
52:38dropping one of the notes and
52:41see if your spike disappears.
52:44That can be one strategy if that
52:47is the if that is the goal. But
52:49but but overall, generally we just
52:51know the system doesn't work. Well,
52:53yeah, that is that can be one strategy.
52:55But then we have some advanced tools that
52:58can tell us that can help us tell pinpoint
53:02exact sensor which is malfunctioning.
53:05So for that we need this,
53:08we need to combine the this idea of
53:11the space as well as this idea of
53:14frequency and we want to localize
53:16it in space as well as frequency.
53:19Then there the wavelets come into fake
53:22picture or the graph is scattering
53:24comes into the picture. So yeah.
53:29So to motivate that here again,
53:33if we look at so in the previous slides,
53:36it is slide, it was about this
53:38temperature recordings on the graph.
53:40But if you just look at a very
53:43classical one-dimensional chirp signal,
53:45so let's say it's like starting,
53:47starting at time zero,
53:50it is a slowly varying signal,
53:52low frequency.
53:53Then as the time passes it's it is
53:56varying rapidly and that is chirp up.
53:59So frequency is going up.
54:01And if you look at the just take the
54:04Fourier transform of this signal,
54:06you will see that
54:10OK, just and just reverse the signal now.
54:14So in the time T, time T is equal to 0.
54:18The signal is changing rapidly
54:19and then as the time progresses,
54:22the frequency goes down.
54:24These two are very different signals.
54:29But if you take the Fourier transform,
54:31it's going to look exactly the same.
54:33It cannot.
54:34So that that's the message here.
54:36The Fourier transform cannot point out
54:39where exactly the changes are happening.
54:41It can tell you what changes are happening,
54:43but it cannot tell you where exactly
54:46the thing these changes are happening.
54:48So in order to solve this problem
54:50or in order to discriminate or
54:53localize discriminate such issues
54:55or in order to localize the this
54:59time and frequency together, we
55:05we study the concept called wavelet.
55:10So what are these wavelets?
55:12Wavelets are just nothing but a small wave.
55:15And in, in in literature you can find
55:19there are many different wavelet
55:22shapes that people have studied.
55:25Some of the very popular ones are this
55:29R wavelets and this debash wavelets.
55:32Also this Mexican hat,
55:34So these are the small waves that you
55:37just want to use in order to show in
55:40order to represent your data or represent
55:44your signal that is localized in time
55:47as well as in frequency together.
55:49And we will see how to do that exactly.
55:55So what this wavelet does
55:58is it takes shifts of this.
56:00So this is a very small kind
56:03of a wave and you want to
56:05analyse this time domain signal.
56:07So what you can do is just align
56:10this wavelet at this time window
56:14and compute the correlation between
56:16the signal and this wavelet and
56:19see how correlated they are.
56:21Then shift the same wavelet to
56:23another time window and compute some
56:25correlation coefficients or inner product,
56:28whatever you call it.
56:31And then and then save those numbers,
56:35save those numbers and then you kind
56:38of stretch the wavelet like scale the
56:40wavelet so the changes are not as rapid.
56:43So if you look at this wavelet at the bottom,
56:46it is a,
56:47it is like a stretched version
56:49of this first wavelet here.
56:51So this is called scaling.
56:53So you can scale your wavelet to
56:56like either stretch it or compress it.
57:00And based on that you can you
57:03can capture the high or low
57:06frequency variations in the signal.
57:08So that's how this wavelet wavelets work with
57:12different shifts and scales in time domain.
57:15And this is a very nice example here.
57:17If you look at this,
57:19the chirped up signal where in the beginning
57:23slowly varying signal and then as the
57:26time progresses the frequency is increasing.
57:29Then if you look at this
57:31wavelet coefficients here,
57:34so this vertical axis here is the
57:38frequency and the horizontal axis here
57:40is time and these are the coefficients.
57:42So if you can see this frequency
57:44is increasing slowly in time.
57:46So this transform is not only giving
57:49us information about what frequency
57:52components are present in your
57:54data and but it is also telling
57:56us that at what time windows these
57:59frequency components are present.
58:01And these coefficients are just
58:03computed by just aligning these
58:05we have list to the time window,
58:06computing these inner product or
58:09correlations and just plotting
58:11it here together.
58:12And if you plot this same
58:15coefficients with chirp down signal,
58:17it's going to look exactly the
58:20opposite and you can identify
58:22the OR discriminate between the
58:24two different kind of signals.
58:28Any questions here?
58:31Then we move to the last part.
58:46OK,
58:52so now we have a little bit idea
58:54about what these wavelets are.
58:55So why we came to this wavelet?
58:58Because this Fourier transform
59:01doesn't tell us where exactly in
59:03time and that that can be very
59:05important information sometime you
59:08don't want to miss out on that,
59:09where exactly it is present.
59:10So wavelets give you more kind of
59:14more powerful representation of the
59:16signal in time domain as well as now
59:20how do we kind of extend these this
59:23wavelet concept to graph domain?
59:26Can we do it?
59:32So I'm not going to talk much
59:35about this mathematics here,
59:37not to scare you, but it is just a
59:42little bit that this is just a shifting.
59:45So there is a mother wavelet, sigh.
59:48And this mother wavelet can be
59:51hare debash or Mexican head.
59:54This is a mother wavelet.
59:56And then you kind of shift those wavelets,
59:59stretch those wavelets and compress
01:00:01those wavelets and and then kind
01:00:04of save those wavelets at different
01:00:06scales and different translations
01:00:08of different shifts.
01:00:11So these shifts, yes,
01:00:13we have a question.
01:00:14So again, just to clarify,
01:00:16basically we're doing the same stuff.
01:00:18We are coming up with a
01:00:22set of base functions.
01:00:24So then we can decompose our complex
01:00:27signal into all these base functions.
01:00:30And the whole creativity here is
01:00:34that we are trying to not just
01:00:38stay in one-dimensional signal,
01:00:41but we want to have higher
01:00:44sensitivity to spatial structure,
01:00:46we want to have higher sensitivity
01:00:48to temporal structure.
01:00:49And that's why we're coming up
01:00:52with more complex combination
01:00:53set of base functions, right.
01:00:56So that's the story here.
01:00:58OK,
01:00:59that's a, that's a very good point. Yeah. And
01:01:05yeah, so this similar basically we
01:01:07are trying to get the represent the
01:01:10signal using this different set
01:01:12of basis functions or harmonics
01:01:14or whatever if you can call it.
01:01:16And this side is our mother wavelet
01:01:20and this S acts as a scaling operation.
01:01:24So if you put S as like two or four,
01:01:28so usually people use dyadic wavelets
01:01:31like usually this is scaling factor
01:01:33is in powers of two because you
01:01:35cannot like it's in continuous form.
01:01:37So you cannot like store infinite
01:01:41number of wavelets.
01:01:42You can store or analyze only a finite
01:01:45number of wavelets in in your computer.
01:01:48So you kind of discretize your scales
01:01:51and you discretize your translating
01:01:53to different time windows and
01:01:55you fix those numbers.
01:01:56And once you have fixed those bases,
01:01:59you can compute the coefficients
01:02:01corresponding to the corresponding
01:02:03to different wavelets at
01:02:04different scales and shifts.
01:02:08Then similarly, is there any limit on
01:02:12the the how much data you need to
01:02:16have for what is the relationship?
01:02:18Just intuitively, again,
01:02:20when we are thinking about more
01:02:22simple analysis, we also have to
01:02:24think in terms of power, right?
01:02:26So this is how sensitive we are to
01:02:29changes versus how large our sample is.
01:02:32This seems to be a very
01:02:35different in terms of intuition,
01:02:38but are there any basic rules
01:02:41like how many functions can you
01:02:43incorporate versus how much data you
01:02:45need to have like anything at all?
01:02:47Very, very,
01:02:49very good, very good question here.
01:02:51So it's up to the user,
01:02:55researcher, whatever you call it,
01:02:59to kind of find this by intuition
01:03:02or kind of learn it by applying this
01:03:06wavelets to multiple data sets.
01:03:08So once you have some kind
01:03:10of sense of the data set,
01:03:12what kind of data it is,
01:03:14you can always use.
01:03:16You can start with like two
01:03:19or three different scales and
01:03:21like at different time shifts,
01:03:24like a very few time shifts in a time
01:03:27window depending on how long is the
01:03:29recording versus how much variation.
01:03:32So it is up to the user
01:03:34to kind of determine it.
01:03:36But if you have like if your
01:03:38complexity is increased,
01:03:39because if you take more and more wavelets,
01:03:41your resolution is going to increase and
01:03:43that puts a computational burden on you.
01:03:46So you have to like kind of
01:03:48compromise between the computational
01:03:49burden versus the data set that
01:03:51you are that you have in hand.
01:03:54So there is no hard and fast rule.
01:03:56How many scales or how many
01:03:57shifts you have to use here.
01:03:59It comes from just from the application.
01:04:02Yeah,
01:04:05OK.
01:04:08So this is the wavelet.
01:04:10So in classical domain again this way
01:04:12you can define this wavelet coefficients
01:04:17and then using this intuition
01:04:20of this because this complex.
01:04:22So whenever you see exponential of
01:04:24J Omega that is going to be our
01:04:29eigenvector Laplacian eigenvector.
01:04:30So or even if you see sine sine
01:04:33wave or sine Omega Omega X or cosine
01:04:36Omega X that is literally analogous
01:04:40to our Laplacian eigenvectors.
01:04:43And if you have so here,
01:04:45if you have this A a means the shift.
01:04:48So that is nothing.
01:04:53Oh, this Phi dash, sorry, this side side
01:04:57hat is nothing but this filter here.
01:05:00So I don't want to get into the details here,
01:05:03but the point here is that we
01:05:06want to decompose our signal in
01:05:08in terms of different scales and
01:05:11different shifts in the space.
01:05:14So what exactly is happening here?
01:05:16So we define some kernels for this wavelet.
01:05:21So we don't have to worry about that.
01:05:23If you put it in the toolbox,
01:05:25it just you just need to decide the scales,
01:05:29how many scales you want in the graph
01:05:33and at each node it is computed.
01:05:36So here this is just a ring graph.
01:05:38Here if you look at wavelet at at
01:05:41a scale T is equal to 19 or 20.
01:05:44So if you so high scale means low frequency
01:05:49and low scale means high frequency.
01:05:56So if you look at here the
01:05:59changes are going to be rapid
01:06:02in case of wavelet as low scales and high
01:06:07scales the changes are going to be slow.
01:06:10But let's not get into mathematics,
01:06:14but just intuition wise.
01:06:16High scale is low frequency,
01:06:18low scale is high frequency information. And
01:06:25now
01:06:29in a word,
01:06:33in this workshop, we are
01:06:34remember that we, we were, we are
01:06:38developing the concepts required for this
01:06:42geometric scattering trajectory homology.
01:06:44So it involves these four steps,
01:06:48graph creation.
01:06:49And once you have a graph,
01:06:51you, you want to represent
01:06:54this graph signal somehow.
01:06:56And this is scattering.
01:06:58This particular figure is
01:07:00for a **** graph scattering.
01:07:03And in the next,
01:07:05in the next lecture,
01:07:07Dhananjay and Brian are going to
01:07:10talk about how to use these graph
01:07:14wavelets in order to define exactly
01:07:17this graph scattering transform.
01:07:20So we have, once we have this graph
01:07:24scattering transform defined,
01:07:25it goes to the dimensionality reduction.
01:07:28And then we do some kind of a
01:07:31topological data analysis to find
01:07:34the find the shapes that that
01:07:37come come across from this data.
01:07:39And in the first in last week,
01:07:41in the first lecture,
01:07:42Dhananjay has talked about this,
01:07:44how to deal with these shapes.
01:07:46Today in this step two,
01:07:48we have learned the concepts
01:07:51of frequency in graphs,
01:07:54frequency in in this irregular
01:07:57structure and we have we have
01:08:01gone through Fourier transform
01:08:05and its extension to graphs.
01:08:07And we also introduced concepts
01:08:10of wavelet a little bit.
01:08:12And this representations now are
01:08:15going to be based on this graph
01:08:18wavelets so that we get a richer
01:08:21representation of this data once
01:08:24we have the representation of
01:08:26the data at each time point.
01:08:29So we after we have this
01:08:31representation at each time point,
01:08:33we do this dimensionality reduction
01:08:35and we get a nice trajectory and
01:08:38then we kind of analyze the shape
01:08:41of that trajectory using this TDA.
01:08:48So, OK,
01:08:51so I'm going to just remind again what
01:08:53we have covered and then in my lecture
01:08:55here and if we have any more questions,
01:08:57we can go go through that.
01:08:59So we today we introduced graph signal
01:09:03processing where we and also we kind of,
01:09:07we made an analogy from classical signal
01:09:10processing and how to extend the,
01:09:13the important tools in graph domain.
01:09:16And we found that this Laplacian
01:09:19eigenvalues and eigenvectors are
01:09:20the basic building blocks of all
01:09:23the concepts in graph domain.
01:09:24Most of the conference,
01:09:26most of the concepts in graph domain.
01:09:28And we also introduced what is
01:09:30the use of the wavelet.
01:09:32And next is how do we use this graph
01:09:35wavelets to define graph scattering?
01:09:37And that that's not that's going to be
01:09:42presented by the Ranjay in next week lecture.
01:09:46And then we're going to combine these Step 2,
01:09:52all these steps together in the next
01:09:56lecture to give a picture of geometric
01:09:58scattering, scattering homology.
01:10:03Thank you. That ends my lecture
01:10:05today. Thanks for listening.
01:10:07Thank you, thank you, Rahul.
01:10:09So I want to give an opportunity
01:10:11to our our other participants.
01:10:14If you guys have any questions,
01:10:16I can see that you're sticking around
01:10:19through all this advanced stuff.
01:10:23Any any comments,
01:10:25any questions before I will jump in.
01:10:34So for me, for me it's
01:10:36the same kind of question.
01:10:39My understanding from today,
01:10:40I was I was really curious
01:10:43about this approach and I was
01:10:45wondering what is the backbone.
01:10:48And again, the way I understand
01:10:51that is that we are after some
01:10:56functional and practical decomposition
01:11:00of very complex phenomena into
01:11:04something that we can manage,
01:11:07something we understand.
01:11:10And we just going from say
01:11:13Taylor to Fourier to graph based
01:11:18decomposition and then aiding
01:11:21this temporal component.
01:11:23So we just generating more
01:11:27complex base functions.
01:11:32This is new to me, but in my
01:11:34intuition comes from this,
01:11:36you know, single dimensional story.
01:11:40What is the danger with overheating?
01:11:44Does it exist? Overheating like can be
01:11:49overheat because that would be concerned
01:11:52with more simple decompositions, right?
01:11:57You do understand correctly that all
01:12:00data is treated as signal or are there
01:12:04any components to denoise the process,
01:12:07right, to separate noisy components?
01:12:10Like for instance,
01:12:11you just assume that something of
01:12:13higher frequencies and noise, I don't know.
01:12:16So again, this is me just trying
01:12:18to digest this new material.
01:12:20Like what is the signal?
01:12:21What is noise?
01:12:23Are there any criteria?
01:12:25And what is the danger
01:12:27of overheating generally?
01:12:29Yeah. So talking about frequency first,
01:12:31a high frequencies are not always the noise
01:12:34exactly. Yeah, right. But in
01:12:36most of the cases, most of the cases
01:12:40usually you don't need high frequency
01:12:42because in general the date the in the
01:12:46natural data is smooth in nature seizure.
01:12:51Yeah, Yeah. So the best one is not,
01:12:52not, not all the time,
01:12:55Yeah, not all the time,
01:12:56but they're important sometimes.
01:12:58And over fitting is like sometimes you
01:13:01can kind of take so many scales here
01:13:05and so many kind of so many levels
01:13:09of decomposition and that kind of
01:13:13that that can like create issues.
01:13:16If you kind of take more and more
01:13:18scales and make it more complicated
01:13:21representation in this particular part here.
01:13:23Then again that that has
01:13:25another kind of a set.
01:13:26It can the set back can happen again.
01:13:29But but The thing is,
01:13:30if you're not able to kind of find out
01:13:33the nice patterns and all in the data,
01:13:35if you take two computationally
01:13:38complex methodology here,
01:13:40then you can always reduce it.
01:13:44Still let me yeah, let me try
01:13:46ask this question different way.
01:13:48So if I do something basic as principle
01:13:52component analysis on imaging data,
01:13:54I will always expect that first
01:13:59largest components, maybe three or
01:14:02four are going to be noise, right?
01:14:05So this is my approach to denoising
01:14:08my data and I'm just curious if
01:14:15there is any built in intuitional
01:14:18logic except for high frequencies
01:14:21typically noise to denoising,
01:14:23we are dealing with incredibly noisy
01:14:26data when we do for instance fMRI.
01:14:29So we know that noise is there.
01:14:31So how do you so sometimes noise in
01:14:35this scattering transforms.
01:14:36There are some learnable parameters
01:14:38also they have people have introduced,
01:14:41I think Dhananjay was one of the
01:14:43contributors in the, in those,
01:14:45in those in that work where you
01:14:47can kind of learn from the data,
01:14:49how much of high frequency
01:14:50component I'm going to use,
01:14:51how much of low frequency
01:14:52component I'm going to use.
01:14:54So it's not a hard for hard and
01:14:56fast deterministic set of values or
01:14:58deterministic set of frequency windows.
01:15:00But you can make it learnable
01:15:02as well based on the data.
01:15:05So it can be data-driven
01:15:06learnable representation as well.
01:15:10Maybe I can add a little bit to that.
01:15:12So the denoising is built into all the
01:15:16steps really in the pipeline, right.
01:15:18So the, the way first step has to do
01:15:20with how we construct the graph and how
01:15:23we define like a signal on the graph.
01:15:25So you denoise at that level,
01:15:27there is denoising built into that
01:15:29level in the sense for example in this
01:15:32in this picture when we build a graph,
01:15:34we are our our nodes ourselves
01:15:36and our edges are cells that
01:15:38are adjacent to each other.
01:15:40And so when we define the time
01:15:41lapse signal on the graph,
01:15:42we are averaging the signal over each
01:15:45cell like the segmentation of the cell.
01:15:47When we build a graph from brain,
01:15:50then we consider a parcellation of
01:15:53the brain based off of some Atlas.
01:15:55And so to define a time lapse
01:15:57signal on that graph,
01:15:58we are averaging within each parcel.
01:16:00So there's some averaging happening
01:16:02in the walk cells belonging to each
01:16:05parcel and that has some small amount of
01:16:08denoising built into that averaging process.
01:16:11And then in the graph signal processing here,
01:16:14the wavelets that we are using
01:16:16to kind of capture the signal at
01:16:18different scales on the graph,
01:16:20the shape of the wavelet and,
01:16:22and how that wavelet is being applied to
01:16:25the data that does some amount of denoising.
01:16:28And so that,
01:16:29that's, that's what I was wondering actually.
01:16:30I was wondering if you have some
01:16:33wavelets that typically more more
01:16:35commonly represent noise that
01:16:37because of their shape or not.
01:16:38Like I have my toolbox and I know
01:16:41that in this corner I have noisier
01:16:45base functions like is it or,
01:16:47or it doesn't work like that.
01:16:49So when you pick a wavelet scale that's very,
01:16:51very small, then the frequency of
01:16:54the wavelet is much higher and,
01:16:57and that will correspond to very noisy.
01:17:01That's going to capture noise in,
01:17:03in the, in the data set on the graph.
01:17:06Again, depends on what what scale becomes
01:17:10noise versus what scale is still like,
01:17:13you know, an epileptic seizure,
01:17:15which is, you know,
01:17:16going to be rapidly wading across the brain.
01:17:19So, so there's denoising kind of
01:17:21in the spatial domain that's built
01:17:23into step one and Step 2 through
01:17:26averaging in step one and through
01:17:28the scales of the wavelets in Step 2.
01:17:31But that doesn't address
01:17:33denoising in the temporal domain.
01:17:35And so the denoising in the temporal
01:17:37domain is built into step three has to
01:17:40do with how that trajectory itself gets
01:17:42computed from all of these numerical
01:17:44features that are derived in Step 2.
01:17:46So the temporal denoising happens there.
01:17:49And then there's another denoising
01:17:50step in Step 4 where when we
01:17:52compute the topological signatures,
01:17:54we ignore topology,
01:17:55topology close to the diagonal.
01:17:57And so we are those are kind of
01:17:59the smaller topological features
01:18:01that are not as persistent.
01:18:03So there's again denoising
01:18:04happening at that level,
01:18:06but yeah,
01:18:07there's multiple levels of denoising.
01:18:09I'd say in step one and Step 2,
01:18:11the denoising operates on the spatial
01:18:13axis and step three and step four it
01:18:15operates on the temporal axis of the data.
01:18:19Thank you.
01:18:21Very exciting. Looking
01:18:22forward to the next talk.
01:18:24Yeah, thanks. Wanted to thank also
01:18:26the audience for sticking around.
01:18:28I know it was quite technical today,
01:18:29but it has really built in some
01:18:32vocabulary and some tools that
01:18:33would be very helpful in kind
01:18:35of bringing this all together.
01:18:37In our next workshop,
01:18:39we'll bring it all together,
01:18:40but we'll also show you lots and
01:18:42lots of examples of applying this
01:18:44technique to real data and build
01:18:46even more intuition around what
01:18:48kind of dynamics GSTH is capturing.
01:18:52And then we'll give you access
01:18:54to the tool and have you work on
01:18:55some data sets yourself in the
01:18:57final workshop in the series.
01:18:58So thanks for coming.
01:18:59Thanks for sticking around.
01:19:01Thank you so much.
01:19:03Yes, thank you. See you next week.