Graph Shift Operators (GSOs)

Graph Shift Operator (GSO)

A graph shift operator is any matrix $S \in \mathbb{R}^{n\times n}$ satisfying

$$S_{ij} \neq 0 \;\Rightarrow\; i=j \;\text{or}\; (i,j)\in\mathcal{E}.$$

Then a graph shift is of the form $Sx$ for a graph signal $x \in \mathbb{R^n}$.

Information aggregation in graphs can be represented by local diffusion processes. We can, however, represent these as global processes using the GSOs. Notice that the output of a shift operator for a node is a linear combination of the signals in its immediate neighbourhood and the signal it carries. The GSO encodes all of these local signal propagations.

Some important GSOs are as follows:

Adjacency Matrix

Undirected

$$A_{ij} = A_{ji} = W(i,j)$$

Directed

$$A_{ij} = W(j,i)$$

Degree Matrix

Undirected

$$D = \mathrm{diag}(A\mathbf{1})$$

Directed

$$D^{\text{out}} = \mathrm{diag}(A\mathbf{1})$$ $$D^{\text{in}} = \mathrm{diag}(A^\top \mathbf{1})$$

A degree matrix is a diagonal matrix encoding how strongly a node is connected to the graph. In the undirected case each diagonal element is the sum of the edge weights of the corresponding vertex. The directed case is analogous with in and out degree matrices.

Laplacian Matrix

Undirected

$$L_{ij} = \begin{cases} - A_{ij}, & i \neq j \\ d(i), & i = j \end{cases}$$ $$L = D - A$$

Directed

Multiple definitions exist. Two common ones are:

$$\begin{aligned} & \\[6pt] L &= D^{\text{out}} - A \\[6pt] L_{\text{sym}} &= \tfrac{1}{2}\left(L + L^\top\right) \end{aligned}$$

The Laplacian is central to many graph based applications and generalizes differentiation to arbitrary graphs. It is a measure of closeness between a node and the average of it's neighbours.

Random Walk Matrix

Undirected

$$P_{ij} = \frac{A_{ij}}{d(i)}$$ $$P = D^{-1}A$$

Directed

$$P_{ij} = \frac{A_{ij}}{d^{\text{out}}(i)}$$ $$P = (D^{\text{out}})^{-1}A$$

The random walk matrix defines a Markov Chain for transitioning between vertices. Notice the sum of each row is 1, and if considered as probabilities, each value corresponds to the probability of transition which is proportional to the edge weights of a vertex. The directed version uses the out degree.

Random Walk Laplacian

Undirected

$$L^{\mathrm{rw}} = I - P$$ $$= I - D^{-1}A$$

Directed

$$L^{\mathrm{rw}} = I - (D^{\text{out}})^{-1}A$$

The random walk Laplacian is a measure of deviation between the graph signal (or the equilibrium) with it's expected value after one application of the random walk matrix, intuitively a discrete turn of information diffusion.

Notice:

$$L^{\mathrm{rw}} x = x - Px$$

Normalized Adjacency

Undirected

$$\bar{A} = D^{-\frac12} A D^{-\frac12}$$ $$\bar{A}_{ij} = \frac{A_{ij}}{\sqrt{d(i)\,d(j)}}.$$

Directed

$$\bar{A} = P$$

The normalized adjacency matrix normalizes the adjacencies by the degrees, eliminating bias due to the total degree to measure a normalized version of connectivity.

For undirected graphs, this matrix is symmetric.

For directed graphs, this is the same thing as the random walk matrix. Normalizing by one direction results in the edge weighted values that sum to one, exactly the random walk matrix.

Normalized Laplacian

Undirected

$$\bar{L} = I - \bar{A}$$ $$= I - D^{-\frac12} A D^{-\frac12}$$

Directed

$$\bar{L} = I - P$$ $$= I - (D^{\text{out}})^{-1}A$$

It is a measure of closeness between a node and the degree normalized average of it's neighbours. For undirected graphs it is symmetric and positive semidefinite.

For directed graphs, the normalized Laplacian is the random walk Laplacian.