# Generalized translation on graph

David I.Shuman in "vertex-frequency analysis on graph" claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply this transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph."

In this paper generalized translation operator that allows us to shift a window around the vertex domain so that it is localized around any given vertex, just as we shift a window along the real line to any center point in the classical windowed Fourier transform for signals on the real line.

generalized translation operator:

$$(T_{i}f)(n) := \sqrt{N}(f*\delta_{i})(n) = \sqrt{N}\sum_{\ell=0}^{N-1}\hat{f}(\lambda_{\ell}) \chi^{*}_{\ell}(i)\chi_{\ell}(n) .$$

See the picture

Question

1. How do I understand translation on the graph?
2. How to label irregular graphs with high dimensional data?

Thanks.

• With 1 do you mean to ask "How do I understand the translation algorithm on the graph"? I don't understand what you mean by motion here so I am assuming that you refer to the translation that is analogous to $x(t-5)$ (?). And with 2, "How to label irregular graphs with high dimensional" what? Do you mean "...with high dimensional data"? Do you have a specific type of data in mind? – A_A Sep 19 '18 at 1:48
• @A_A Yes, yes. can you help me? – niloofar jamshidi Sep 19 '18 at 4:12
• Can I please ask if this was resolved? – A_A Sep 21 '18 at 14:44
• @A_A I am very thankful that you are my teacher. – niloofar jamshidi Sep 22 '18 at 6:06

To understand either of these, you first have to understand the basic premise behind Graph Signal Processing (GSP) which is to map a signal to a graph and then work with it on the "Graph space". This is possible due to certain similarities of classic DSP concepts and Algebraic Graph Theory.

So, it is easier to start from the second question because, before we start applying GSP, we first need a graph.

How to label irregular graphs with high dimensional data?

The short answer is that this is still an open problem and currently, there are "signals" that are naturally mapping on graphs and others where the mapping is either arbitrary or in some way constructed.

Signals that naturally map on graphs are usually expressed as weights of the graph's edges through a Weight Matrix that is similar to an Adjacency Matrix.

Typical examples are usually items and some form of similarity between them. For example, suppose that you have a set of $N$ time series $X$ and you evaluate their cross correlation. This will result in a Weight Matrix (let's call it $W$) whose $i^{th}, j^{th}$ element ($W_{i,j}$) is the cross correlation between time series $X_{:,i}$ and $X_{:,j}$. (So, $X$ is an $m \times n$ matrix of $n$ time series signals each being $m$ samples long.)

What does this graph look like? It looks like a Clique. In other words, because we have examined all-to-all cross correlatons, all nodes are considered connected with each other. But, the strength of the connection is expressed by some weight.

So, yes, they are all connected, but some are much more closer than others.

For signals that do not naturally map on graphs, you first have to solve the corresponding graph labeling problem. This is generally done in two ways, either by coming up with a function that maps a signal to some graph or arbitrarily.

In the arbitrary case, you select some graph whose order (the number of nodes) is equal to the number of samples in your signal. That graph's nodes can be arbitrarily connected, it could for example be an entirely random graph where there is equal chance for any two nodes to be connected.

This is what the author of the paper that you link is actually doing. They take an arbitrary graph (a road network) and they map on to it an exponential decay signal. How? Arbitrarily. Does it make sense? No, but it illustrates the point they are trying to make about showing the effect of the operators.

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

The other way that you can do the mapping is with an intuitive or model fitting (in the sense of optimisation) way.

So, an intuitive way to map a signal to a graph is to put the samples of some $x[n]$ time series on the nodes of a graph that are simply connected as a "line" (so, something looking like $x[0] \rightarrow x[1] \rightarrow x[2] \rightarrow x[3] \ldots \rightarrow x[n]$ ).

And a constructed way is to use optimisation in order to construct a graph whose connectivity represents SOME aspect of your original signal $x[n]$.

Which brings us to the first question:

How do I understand translation on the graph?

The short answer is that translation on a graph is equivalent to a re-ordering of the edges that effects a new connectivity pattern on the nodes of the graph. In this way, the nodes appear to have "moved" or translated to a different "position".

So now the question is how do you define "position" and to an extent this question is a bit related to the first one because "position" and how you represent the signal are related.

But, here is a very simple example, just to demonstrate a trivial translation.

Say we have this signal: $x = \left\{ 0,1,2,3,2,1,0,1,2,3,2,1,0 \right\}$ and we map it to the "line" graph $G(V,E)$ we saw earlier that looks like $x[0] \rightarrow x[1] \rightarrow x[2] \rightarrow x[3] \ldots$. In other words, we assign $x[0]$ to $v_0$, $x[1]$ to $v[1]$ and so on and we assume that nodes are connected "sequentially" (and cyclically).

The adjacency matrix (or the weight matrix) of this graph is:

$$A = \begin{vmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{vmatrix}$$

Notice here that I have connected $x[|V|]$ back to $x[0]$ with that last line.

So, how do you "move" nodes around?

In classic DSP, if you wanted to shift things in time, you did something like: $y[n] = x[n+2], n \in \left\{0 .. |x| \right\}$ and the shift is cyclic here. After this, our shifted sequence $y$ looks like: $y = \left\{ 2,3,2,1,0,1,2,3,2,1,0,0,1 \right\}$

Right, so how could we achieve the same, solely utilising the $A$ to effect the same shifting on our graph signal?

Well, that's easy here because instead of having our initial time series $x$ connected as $x[n] \rightarrow x[n+1]$ it is as if we now connect $x[0] \rightarrow x[2], x[1] \rightarrow x[3], x[2] \rightarrow x[4], \ldots$. So basically, the same $A$ as above, only that now the $1$s appear two places to the right of their current position.

Did you notice how we expressed something that happened in the time domain to something that happens in the graph domain?

The key idea here is that we translated the signal by changing the way the nodes are connected. Translation is basically an operator on the connectivity of the graph.

BUT!

Notice here that we said earlier that we assume a "line" graph as the underlying graph for our signal. We made an arbitrary decision. We could have mapped our signal on the road network of some city (as the authors of the paper that you link have done). Then, how do you define translation on that thing?!?".

This is where the Graph Laplacian and Algebraic Graph Theory come into play.

To cut a long story short, the Graph Laplacian is like the Discrete Fourier Transform for signals in the time domain.

It has been the topic of a lot of research in pure mathematics and its eigenvectors and eigenvalues are supposed to return a lot of information about the graph's connectivity structure (for example, whether it contains cycles or not, what sort of lengths of cycles, whether it is completely connected or not, etc).

So, basically, what the authors are working on in the paper that you linked are a translation operator and a "DFT" equivalent operator on the graph laplacian so that you can "translate" nodes around an arbitrary connected graph (not only one looking like a line, it could have any shape) and decompose and recompose the graph connectivity matrix to elementary components no matter how complex the graph is.

You can see now how the representation of the graph and "translation" are connected. The Laplacian of the graph depends on the values of its adjacency (or weight) matrix (i.e. its structure). You map your signal $x[n]$ on the node set of the graph $V$ and you assume (or construct) the edge set $E$. Therefore, any notions of "translation" or "frequency" now depend on the structure of the adjacency matrix.

Therefore, don't try to understand why Fig.7 in the paper that you link looks the way it looks. First of all, the mapping of the signal on the road network is arbitrary and second, the "translation" depends both on the mapping and the connectivity matrix of the road network. Conceptually, this particular example does not have an immediate connection with reality. But at the same time, conceptually it shows you what translation means over a graph signal and a graph that can have arbitrary connectivity.

Perhaps it is easier to think about GSP in terms of linear algebra because at the end of the day, this is what it is all based on.

If we forget about graphs, adjacencies, nodes, edges, mappings, etc for a minute and focus on the Laplacian: The whole point of GSP is to come up with a new representation for $x[n]$ in the form of a matrix. A new "decomposition" if you like, similar to the way the DFT matrix decomposes a signal or similar to the way Wavelets decompose a signal.

In fact, wavelets are part of the family of "constructed" graphs I am talking about earlier. They are basically a matrix. This matrix could also be expressed as a graph. When it is expressed as a graph, it opens the door to "new" ways of working with signals or "new" ways of working with graphs. For more information on this line of thinking please see this paper or this paper and this paper (for methods of discovering graph representations).

Hope this helps.

• I cannot thank you enough for helping me. Thank you for the clarification. – niloofar jamshidi Sep 22 '18 at 6:04
• @niloofarjamshidi In what sense? What is the question? – A_A Sep 23 '18 at 19:23
• Generally, Since the mapping of the signal on the road network is arbitrary, Understanding the intuition behind the translation operator Particular modulation operator on graph is hard! Arranging the subject in mind is hard for me! Can we consider graph domain Generalization finite Hilbert space ?! in this paper focuses on mathematics .Can you introduce such articles like this? – niloofar jamshidi Sep 24 '18 at 21:39
• @niloofarjamshidi I will try to edit the post with a specific example and a more complex network but I am not sure how soon I will be able to do this. – A_A Sep 24 '18 at 23:43