Graph Fourier Transform

← Back to Knowledge Share

In a classical setting, if you have a signal sampled on a perfectly regular grid—like an audio wave over uniform time intervals or an image on a 2D pixel grid—the classical Fourier Transform decomposes that signal into a combination of sine and cosine waves of varying frequencies.

But what happens when your data doesn't live on a neat, regular grid? What if your "sensors" or data points are scattered irregularly, like weather stations across a continent, or nodes in a complex computer network? The classical Fourier Transform fails here because there is no uniform "translation" or "shift" operator.

This is where the Graph Fourier Transform comes in. It generalizes the traditional Fourier Transform so it can be applied to data residing on arbitrary, irregular structures (graphs).

When the literature states that "graph Fourier transforms decompose signals on graphs," here is exactly what that means, broken down into its core components:

1. The "Graph" and the "Signal"

  • The Graph (\(G\)): This is the underlying structure. It consists of nodes (data points) and edges (the connections or relationships between those points).
  • The Signal (\(x\)): This is the actual data living *on top* of the graph. Mathematically, it is a vector \(x \in \mathbb{R}^N\), where each node \(i\) has a specific scalar value \(x_i\) (e.g., the temperature reading at a specific weather station).

2. Redefining "Frequency" using the Laplacian

In classical physics, frequency dictates how rapidly a signal changes over time or space. High frequency means rapid oscillation; low frequency means smooth, gradual changes.

On a graph, we measure "frequency" by looking at how rapidly a signal changes *across connected edges*.

  • Low Graph Frequency: Connected nodes have very similar signal values (the signal is "smooth" across the graph structure).
  • High Graph Frequency: Connected nodes have drastically different or opposite values (the signal "oscillates" rapidly across edges).

To calculate this, we use the Graph Laplacian (\(L\)). It is defined as:

\[L = D - A\]

Where \(A\) is the Adjacency matrix (showing which nodes are connected) and \(D\) is the Degree matrix (a diagonal matrix showing how many connections each node has). The Laplacian acts exactly like the second-derivative operator in calculus—it measures the local roughness or curvature of the signal on the graph.

3. The Decomposition (The Core Concept)

To decompose the signal, we perform an eigenvalue decomposition on the Graph Laplacian:

\[L = U \Lambda U^T\]

This yields two critical pieces of information:

  1. The Eigenvectors (\(U\)): These form our new "sine and cosine waves." They are an orthogonal set of basis vectors. Each eigenvector represents a fundamental "graph wave."
  2. The Eigenvalues (\(\Lambda\)): These represent the specific "frequencies" of those graph waves. A low eigenvalue means the corresponding eigenvector is very smooth across the graph. A high eigenvalue means it is highly oscillatory.

The Graph Fourier Transform is simply the projection of your original signal \(x\) onto these eigenvectors.

If \(\hat{x}\) is the transformed signal in the frequency domain, the GFT is calculated as:

\[\hat{x} = U^T x\]

Why \(L = D - A\)?

The definition \(L = D - A\) is not arbitrary; it is the exact mathematical formulation required to measure the local roughness or variation of a signal across a graph.

Think about what happens when you multiply the Laplacian matrix \(L\) by a signal vector \(x\).

Because matrix multiplication is distributive, \(Lx = (D - A)x = Dx - Ax\). Let's look at what each part does to a specific node \(i\):

  • The Degree part (\(Dx\)): The degree matrix is diagonal. Multiplying \(D\) by \(x\) simply takes the signal value at node \(i\) (\(x_i\)) and multiplies it by the number of neighbors it has (\(d_i\)). So, \((Dx)_i = d_i x_i\).
  • The Adjacency part (\(Ax\)): The adjacency matrix \(A\) has a 1 wherever there is a connection. Multiplying \(A\) by \(x\) effectively sums up the signal values of all immediate neighbors of node \(i\). So, \((Ax)_i = \sum_{j \in \text{neighbors}(i)} x_j\).

Putting them together for a single node \(i\):

\[(Lx)_i = d_i x_i - \sum_{j \in \text{neighbors}(i)} x_j\]

If you factor out the degree \(d_i\), you get:

\[(Lx)_i = d_i \left( x_i - \frac{1}{d_i} \sum_{j \in \text{neighbors}(i)} x_j \right)\]

The Intuition: The operation \(L = D - A\) compares the value of a node to the *average value of its neighbors*. If a node's value is exactly the average of its neighbors, \((Lx)_i = 0\) (the signal is perfectly smooth locally). If it differs greatly from its neighbors, \((Lx)_i\) is large. Therefore, \(L\) is a "roughness operator."

Example

Let's walk through a concrete, step-by-step mathematical example using the simplest possible irregular structure: a 3-node line graph.

Imagine three connected rooms in a hallway, and we are measuring the temperature in each room.

The Graph Structure:

Room 1 --- Room 2 --- Room 3

Step 1: Form the Graph Laplacian (\(L\))

First, we need to map the geometry of our hallway into the Graph Laplacian matrix (\(L = D - A\)).

  • Adjacency Matrix (\(A\)): Represents the connections. Room 1 connects to 2. Room 2 connects to 1 and 3. Room 3 connects to 2.

\[A = \begin{bmatrix} 0 & 1 & 0 \ 1 & 0 & 1 \ 0 & 1 & 0 \end{bmatrix}\]

  • Degree Matrix (\(D\)): A diagonal matrix showing how many connections each room has. Room 1 has one connection, Room 2 has two, Room 3 has one.

\[D = \begin{bmatrix} 1 & 0 & 0 \ 0 & 2 & 0 \ 0 & 0 & 1 \end{bmatrix}\]

  • The Laplacian (\(L\)): Subtracting the two gives us our "second-derivative" operator for this specific graph.

\[L = \begin{bmatrix} 1 & -1 & 0 \ -1 & 2 & -1 \ 0 & -1 & 1 \end{bmatrix}\]

Step 2: Find the Graph Frequencies (Eigen-decomposition)

To find our "sine and cosine waves" for this specific hallway, we perform an eigen-decomposition on \(L\) (\(L = U \Lambda U^T\)).

Calculating this yields three eigenvalues (\(\lambda\)) and three corresponding eigenvectors (\(u\)):

  1. Low Frequency (\(\lambda_0 = 0\)):

\[u_0 = \begin{bmatrix} 0.57 \ 0.57 \ 0.57 \end{bmatrix}\]

*Interpretation:* The "DC component" or global average. Notice how the values are identical across all three rooms. It represents a perfectly smooth signal with no variation.

  1. Medium Frequency (\(\lambda_1 = 1\)):

\[u_1 = \begin{bmatrix} 0.71 \ 0 \ -0.71 \end{bmatrix}\]

*Interpretation:* A gradual gradient. Room 1 is positive, Room 2 is neutral, Room 3 is negative. It represents a signal sloping from one end of the graph to the other.

  1. High Frequency (\(\lambda_2 = 3\)):

\[u_2 = \begin{bmatrix} 0.41 \ -0.82 \ 0.41 \end{bmatrix}\]

*Interpretation:* High oscillation. The signal spikes up in Room 1, drops sharply in Room 2, and spikes back up in Room 3.

Step 3: Introduce a Signal (\(x\))

Now, let's put some actual temperature data onto our graph.

  • Room 1: 5°C (Near a heater)
  • Room 2: 4°C (Middle of the hall)
  • Room 3: 2°C (Near a drafty window)

Our signal vector is:

\[x = \begin{bmatrix} 5 \ 4 \ 2 \end{bmatrix}\]

Step 4: Perform the Graph Fourier Transform

We want to decompose our temperature readings into the three graph frequencies we discovered in Step 2. We do this by calculating the dot product of our signal \(x\) against each eigenvector \(u\) (\(\hat{x} = U^T x\)).

  • Low Frequency Coefficient (\(\hat{x}_0\)):

\[0.57(5) + 0.57(4) + 0.57(2) \approx \mathbf{6.27}\]

  • Medium Frequency Coefficient (\(\hat{x}_1\)):

\[0.71(5) + 0(4) - 0.71(2) \approx \mathbf{2.13}\]

  • High Frequency Coefficient (\(\hat{x}_2\)):

\[0.41(5) - 0.82(4) + 0.41(2) \approx \mathbf{-0.41}\]

Step 5: The Interpretation

You have successfully performed a Graph Fourier Transform. The original spatial signal \(x = [5, 4, 2]\) has been transformed into the graph frequency domain as \(\hat{x} = [6.27, 2.13, -0.41]\).

What does this tell us about the data?

  1. The massive low-frequency coefficient (6.27) tells us the hallway has a strong underlying baseline temperature.
  2. The moderate medium-frequency coefficient (2.13) captures the steady gradient (the heat flowing from the 5°C room toward the 2°C room).
  3. The near-zero high-frequency coefficient (0.41) tells us there are almost no sharp, jagged anomalies in the hallway. The temperature changes smoothly across the connected edges.