Transformada de Fourier d'un graf

En matemàtiques, la transformada de Fourier d'un graf és una transformada matemàtica que compon pròpiament la matriu laplaciana d'un graf en valors propis i vectors propis. De manera anàloga a la transformada de Fourier clàssica, els valors propis representen freqüències i els vectors propis formen el que es coneix com a base de Fourier d'un graf.

La transformada de Fourier d'un graf és important en la teoria de grafs espectrals. S'aplica àmpliament en l'estudi recent d'algoritmes d'aprenentatge estructurat en grafs, com ara les xarxes convolucionals àmpliament utilitzades.

Definició

Donat un graf ponderat no dirigit , on V és el conjunt de nodes amb |V|=N ( N sent el nombre de nodes) i E és el conjunt d'arestes, un senyal graf f:V→R és una funció definida als vèrtexs del graf G. El senyal f mapeja cada vèrtex {vi}i=1…,N a un nombre real f(i). Qualsevol senyal de graf es pot projectar sobre els vectors propis de la matriu laplaciana L. Siguin λl i μl el lè valor propi i vector propi de la matriu laplaciana L (els valors propis s'ordenen en ordre creixent, és a dir, 0=λ0≤λ1≤⋯≤λN−1), la transformada de Fourier graf (GFT) f^ d'un senyal graf f als vèrtexs de G és l'expansió de f pel que fa a les funcions pròpies d'L. Es defineix com:

${\mathcal {GF}}[f](\lambda _{l})={\hat {f}}\left(\lambda _{l}\right)=\langle f,\mu _{l}\rangle =\sum _{i=1}^{N}f(i)\mu _{l}^{*}(i),$

on $\mu _{l}^{*}=\mu _{l}^{\text{T}}$.

Des que $L$ és una matriu simètrica real, els seus vectors propis $\{\mu _{l}\}_{l=0,\cdots ,N-1}$ formen una base ortogonal. Per tant, existeix una transformada de Fourier d'un graf invers (IGFT) i s'escriu com:

${\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\hat {f}}](i)=f(i)=\sum _{l=0}^{N-1}{\hat {f}}(\lambda _{l})\mu _{l}(i)$

De manera anàloga a la transformada de Fourier clàssica, la transformada de Fourier d'un graf proporciona una manera de representar un senyal en dos dominis diferents: el domini del vèrtex i el domini espectral del graf. Tingueu en compte que la definició de la transformada de Fourier d'un graf i la seva inversa depenen de l'elecció dels vectors propis laplacians, que no són necessàriament únics. Els vectors propis de la matriu laplaciana normalitzada també són una base possible per definir la transformada de Fourier d'un graf directa i inversa.

Aplicacions

Compressió d'imatge

La representació de senyals en el domini de la freqüència és un enfocament comú per a la compressió de dades. Com que els senyals de grafs poden ser escassos en el seu domini espectral de grafs, la transformada de Fourier de grafs també es pot utilitzar per a la compressió d'imatges.

Reducció de soroll gràfic

De manera semblant a la reducció de soroll clàssica dels senyals basada en la transformada de Fourier, els filtres de grafs basats en la transformada de Fourier de grafs es poden dissenyar per a la reducció de sorolls de grafs.

Classificació de dades

Com que la transformada de Fourier d'un graf permet la definició de convolució en grafss, fa possible adaptar les xarxes neuronals convolucionals convencionals (CNN) per treballar en grafs. Els algorismes d'aprenentatge semisupervisat estructurat en grafs, com ara la xarxa convolucional de grafs (GCN), són capaços de propagar les etiquetes d'un senyal de graf per tot el graf amb un petit subconjunt de nodes etiquetats, teòricament funcionant com una aproximació de primer ordre de convolucions de grafs espectrals sense calcular. el graf laplacià i la seva pròpia composició.