graph signal processing problem

Data

subject:: Data Science Methods for Large Scale Graphs parent:: Graph Signals and Graph Signal Processing theme:: math notes

Graph Signal Processing Problem

In a graph signal processing problem (or graph regression or signal regression), the graph $G$ is the data support, and is thus fixed. The data are graph signals $x\in {\mathbb{R}}^n$ and we want to predict signals $y\in {\mathbb{R}}^n$. Assuming $x,y\sim p(x,y)$, we regress signals $y$ on predictor signals $x$.

Here, the hypothesis class are the graph convolutions \cal{F}$$=\left\{ z=\sum_{k=0}^{K-1} h_{k}S^kx, h_{k} \in \mathbb{R} \right\}

Our minimization problem is then ${\min }_{h_k}\frac{1}{M}{\sum }_j\ell \left(y^{(j)},{\sum }_{k=0}^{K-1}{h}_k{S}^k{x}^k\right)$

Example

The fixed graph is the US weather station network. Suppose we have our $y$, the recorded temperatures from February 3 from the last $n$ years, and our $x$, the recorded temperatures from November 3 from the last $n$ years.

• Temperatures on the graph are recorded as time series and
• we want to predict the february temperatures from the november temperatures.

Application: temperature forecasting. Predict february 2026 temperatures $(y^{\prime })$ from the november 2025 temperatures $(x^{\prime })$ as $y^{\prime }\approx {\sum }_{k=0}^{K-1}{h}_k^{\ast }{S}^k{x}^{\prime }$

Using $L^2$ loss, our minimization problem becomes: ${\min }_{h_k}\frac{1}{M}{\sum }_j{\left|\left|y^{(j)}-{\sum }_{k=0}^{K-1}{h}_k{S}^k{x}^k\right|\right|}_2^2$

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source