Graf Fourier transform

Inom matematik är Fourier- grafens grafiska transform en matematisk transformation som egennedbryter en grafs Laplacian-matris till egenvärden och egenvektorer . Analogt med den klassiska Fouriertransformen representerar egenvärdena frekvenser och egenvektorer bildar vad som kallas en grafisk Fourierbas .

Graph Fourier-transformen är viktig i spektralgrafteori . Det är allmänt tillämpat i den nyligen genomförda studien av grafstrukturerade inlärningsalgoritmer , såsom de allmänt använda konvolutionella nätverken .

Definition

Givet en oriktad viktad graf $G=(V,E)$ , där $V$ är uppsättningen av noder med $|V|=N$ ( $N$ är antalet noder) och $E$ är uppsättningen av kanter, en grafsignal $f: V\rightarrow \mathbb {R}$ är en funktion som definieras på toppen av grafen $G$ . Signalen $f$ mappar varje vertex $\{v_{i}\}_{i=1,\ldots ,N}$ till ett reellt tal $f(i)$ . Vilken grafsignal som helst kan projiceras på egenvektorerna för den laplaciska matrisen $L$ . Låt $\lambda _{l}$ och $\mu _{l}$ vara det $l_{\text{th}}$ egenvärdet och egenvektorn för den laplaciska matrisen $L$ (egenvärdena sorteras i ökande ordning, dvs. $0=\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{N-1}$ ), grafen Fouriertransform (GFT) ${\hat {f}}$ för en grafsignal ${\displaystyle f} på$$G$ :s hörn är expansionen av $f$ i termer av egenfunktionerna för $L$ . Det definieras som:

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

där $\mu _{l}^{*}=\mu _{l}^{\text{T}}$ .

Eftersom $L$ är en reell symmetrisk matris , är dess egenvektorer $\{\mu _{l}\}_{l=0,\cdots ,N -1}$ bildar en ortogonal bas . Därför existerar en invers graf Fourier-transform (IGFT) och den skrivs som:

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

Analogt med den klassiska Fourier-transformen ger graf-Fourier-transform ett sätt att representera en signal i två olika domäner: vertexdomänen och grafspektraldomänen . Observera att definitionen av grafens Fouriertransform och dess invers beror på valet av egenvektorer från Laplacian, som inte nödvändigtvis är unika. Egenvektorerna för den normaliserade Laplacian-matrisen är också en möjlig bas för att definiera framåt- och inversgrafens Fourier-transform.

Egenskaper

Parsevals identitet

Parseval- relationen gäller för grafens Fouriertransform, det vill säga för alla $f,h\in \mathbb {R} ^{N}$

$\langle f,h\rangle =\langle {\hat {f}},{\hat {h}}\rangle .$

Detta ger oss Parsevals identitet :

$\sum _{i=1}^{N}|f(i)|^{2}=\|f\|_{2}^{2}=\langle f,f\rangle =\langle {\hat {f}},{\hat {f}}\rangle =\|{\hat {f}}\|_{2}^{2}=\summa _{l=0}^{N- 1}\left|{\hat {f}}\left(\lambda _{l}\right)\right|^{2}.$

Generaliserad faltningsoperator

Definitionen av faltning mellan två funktioner $f$ och $g$ kan inte tillämpas direkt på grafsignaler, eftersom signalöversättningen inte definieras i grafer. Men genom att ersätta det komplexa exponentiella skiftet i klassisk Fouriertransform med grafen Laplacian egenvektorer, kan faltning av två grafsignaler definieras som:

$(f*g)={\mathcal {I}}{\mathcal {G}}{\mathcal { F}}[{\mathcal {G}}{\mathcal {F}}[f]\cdot {\mathcal {G}}{\mathcal {F}}[g]],$

$(f*g)(i)=\summa _{l=0}^{N-1}{\hat {f}}(\lambda _{l}){\hat {g}}(\ lambda _{l})\mu _{l}(i).$

Egenskaper för faltningsoperatorn

Den generaliserade faltningsoperatorn uppfyller följande egenskaper:

• Generaliserad faltning i vertexdomänen är multiplikation i grafens spektraldomän: ${\widehat {f*g}}={\hat {f}}{\hat {g}}.$
• Kommutativitet : $f*g=g*f$
• Distributivitet : $f*(g+h)=f*g+f*h$
• Associativitet : $(f*g)*h=f*(g*h)$
• Associativitet med skalär multiplikation: $\alpha (f*g)=(\alpha f)*g=f*(\alpha g )$ , för valfri $\alpha \in \mathbb {R}$ .
• Multiplikativ identitet : $f*g_{0}=f$ , där $g_{0}(i)=\ summa _{l=0}^{N-1}\mu _{l}(i)$ är en identitet för den generaliserade faltningsoperatorn.
• Summan av den generaliserade faltningen av två signaler är en konstant gånger produkten av summan av de två signalerna:

$\sum _{i=1}^{N}(f*g)(i)={\sqrt {N}}{\hat {f}}(0){\hat {g}}(0 )={\frac {1}{\sqrt {N}}}\left[\sum _{i=1}^{N}f(i)\right]\left[\sum _{i=1}^ {N}g(i)\höger].$

Generaliserad översättningsoperatör

Som tidigare nämnts kan den klassiska översättningsoperatorn $T_{v}$ inte generaliseras till grafinställningen. Ett sätt att definiera en generaliserad översättningsoperator är genom generaliserad faltning med en deltafunktion centrerad vid vertex $n$ : $\left(T_{n}f\right)(i)={\sqrt {N}}\left(f *\delta _{n}\right)(i){=}{\sqrt {N}}\summa _{l=0}^{N-1}{\hat {f}}\left(\lambda _ {l}\right)u_{l}^{*}(n)u_{l}(i),$

där $\delta _{i}(n)={\begin{cases}1,&{\text{if }}i=n,\\0,&{\text{annars.}}\end{cases }}$

Normaliseringskonstanten ${\sqrt {N}}$ säkerställer att översättningsoperatorn bevarar signalmedelvärdet, dvs.

$\sum _{i=1}^{N}(T_{n}f)(i)=\summa _{i=1}^{N}f(i).$

Översättningsoperatörens egenskaper

Den generaliserade faltningsoperatorn uppfyller följande egenskaper:

För alla ${\displaystyle f,g\in \mathbb {R} ^{N}} ,$ och $j,k\in \ {1,2,\dots ,N\}$ ,

• $T_{j}(f*g)=(T_{j}f)*g=f*(T_ {j}g)$
• $T_{j}T_{k}f=T_{k}T_{j}f$
• $\sum _{i=1}^{N}(T_{j}f )(i)={\sqrt {N}}{\hat {f}}(0)=\summa _{i=1}^{N}f(i)$
• $\left\|T_{j}f\right\|\neq \|f\|$

Ansökningar

Bildkomprimering

Att representera signaler i frekvensdomän är ett vanligt tillvägagångssätt för datakomprimering. Eftersom grafsignaler kan vara glesa i sin grafspektrala domän, kan Fourier-graftransformen också användas för bildkomprimering .

Grafbrusreducering

I likhet med klassisk brusreducering av signaler baserade på Fourier-transform, kan graffilter baserade på Fourier-grafens transformation utformas för grafsignalnedsättning.

Dataklassificering

Eftersom grafens Fourier-transform möjliggör definitionen av faltning på grafer, gör det möjligt att anpassa de konventionella faltningsneurala nätverken (CNN) för att fungera på grafer. Grafstrukturerade semi-övervakade inlärningsalgoritmer, såsom graffaltningsnätverk (GCN), kan sprida etiketterna för en grafsignal genom hela grafen med en liten delmängd av märkta noder, som teoretiskt fungerar som en första ordningens approximation av spektrala graffalsningar utan beräkning grafen Laplacian och dess egenuppdelning.

Verktygslåda

GSPBOX är en verktygslåda för signalbehandling av grafer, inklusive grafens Fouriertransform. Den stöder både Python- och MATLAB -språken.

externa länkar

• DeepGraphLibrary Ett gratis Python-paket byggt för enkel implementering av grafiska neurala nätverk.