Kalkyl för ändligt viktade grafer

Inom matematik är kalkyl på finita vägda grafer en diskret kalkyl för funktioner vars domän är vertexuppsättningen av en graf med ett ändligt antal hörn och vikter associerade med kanterna . Det handlar om att formulera diskreta operatorer på grafer som är analoga med differentialoperatorer i kalkyl , såsom graf Laplacians (eller diskreta Laplace-operatorer ) som diskreta versioner av Laplacian , och använda dessa operatorer för att formulera differentialekvationer , skillnadsekvationer eller variationsmodeller på grafer som kan tolkas som diskreta versioner av partiella differentialekvationer eller kontinuumvariationsmodeller. Sådana ekvationer och modeller är viktiga verktyg för att matematiskt modellera, analysera och bearbeta diskret information inom många olika forskningsområden, t.ex. bildbehandling , maskininlärning och nätverksanalys .

I applikationer representerar ändligt viktade grafer ett ändligt antal enheter genom grafens hörn, eventuella parvisa samband mellan dessa enheter genom grafkanter och betydelsen av ett samband med en kantviktsfunktion. Differentialekvationer eller differensekvationer på sådana grafer kan användas för att utnyttja grafens struktur för uppgifter som bildsegmentering (där hörnen representerar pixlar och de viktade kanterna kodar pixellikhet baserat på jämförelser av Moore-kvarter eller större fönster), datakluster , data klassificering eller gemenskapsdetektering i ett socialt nätverk (där hörnen representerar användare av nätverket, kanterna representerar länkar mellan användare och viktfunktionen indikerar styrkan i interaktioner mellan användare).

Den största fördelen med ändligt viktade grafer är att genom att inte vara begränsade till mycket regelbundna strukturer som diskreta regelbundna rutnät , gittergrafer eller maskor , kan de användas för att representera abstrakta data med oregelbundna inbördes samband.

Om en ändligt viktad graf är geometriskt inbäddad i ett euklidiskt utrymme, dvs. grafens hörn representerar punkter i detta utrymme, så kan det tolkas som en diskret approximation av en relaterad icke-lokal operator i kontinuuminställningen.

Grundläggande definitioner

En ändligt viktad graf $G$ definieras som en trippel $G=(V,E,w)$ för vilken

• ${\displaystyle V=\{x_{1},\dots ,x_{n}\},n\in \mathbb {N} } ,$ är en finit uppsättning index betecknade som grafens hörn eller noder ,
• $E\subset V\times V$ är en ändlig uppsättning av (riktade) grafkanter som förbinder en delmängd av hörn,
• $w\colon E\rightarrow \mathbb {R}$ är en kantviktsfunktion definierad på grafens kanter.

I en riktad graf har varje kant $(x_{i},x_{j})\in E$ en startnod $x_{i}\ i V$ och en slutnod $x_{j}\in V$ . I en oriktad graf för varje kant $(x_{i},x_{j})$ finns det en kant $(x_{j},x_ {i})$ och viktfunktionen måste vara symmetrisk, dvs. $w(x_{i},x_{j})= w(x_{j},x_{i})$ . På resten av denna sida kommer graferna att antas vara oriktade, om inte annat specifikt anges. Många av idéerna som presenteras på denna sida kan generaliseras till riktade grafer.

Kantviktsfunktionen $w$ associerar till varje kant $(x_{i},x_{j})\in E$ ett verkligt värde $w(x_{i},x_{j})>0$ . Av både matematiska och applikationsspecifika skäl krävs ofta att viktfunktionen på kanterna är strikt positiv och på denna sida kommer den att antas vara så om inte annat specifikt anges. Generaliseringar av många av idéerna som presenteras på den här sidan för att inkludera negativt viktade kanter är möjliga. övervägs en utvidgning av domänen för kantviktsfunktionen till ${\displaystyle V\times V} (med den resulterande funktionen fortfarande kallad$ kantviktsfunktionen ) genom att sätta ${ \displaystyle w(x_{i},x_{j})=0}$ när $(x_{i},x_{j})\inte \in E$ .

I applikationer representerar varje grafvertex $x\in V$ vanligtvis en enda enhet i den givna datan, t.ex. element i en ändlig datamängd, pixlar i en bild eller användare i ett socialt nätverk. En grafkant representerar ett förhållande mellan två entiteter, t.ex. parvisa interaktioner eller likheter baserat på jämförelser av geometriska grannskap (till exempel av pixlar i bilder) eller av en annan egenskap, där kantvikten kodar för styrkan i detta förhållande. De vanligaste viktfunktionerna är normaliserade för att mappa till värden mellan 0 och 1, dvs $w:E\rightarrow (0,1]$ .

I det följande antas att de betraktade graferna är sammankopplade utan självslingor eller flera kanter mellan hörn. Dessa antaganden är för det mesta ofarliga eftersom i många applikationer varje ansluten komponent i en frånkopplad graf kan behandlas som en graf i sin egen rätt, varje utseende av $w(x_{i},x_{ i})$ (som skulle vara icke-noll i närvaro av självslingor) visas i närvaro av en annan faktor som försvinner när $i=j$ (se avsnittet om differentialgrafoperatorer nedan) och kant vikter kan koda liknande information som flera kanter kunde.

Grannskap

En nod $x_{j}\in V$ är en granne till noden $x_{i}\in V$ om det finns en kant $(x_{i},x_{j})\in E$ . När det gäller notation kan detta förhållande förkortas med ${\displaystyle x_{j}\sim x_{i}} ,$ vilket bör läsas som " $x_{j}$ är en granne till $x_{i}$ ". Annars, om $x_{j}$ inte är en granne till $x_{i}$ skriver man $x_{j}\not \sim x_{i}$ . Kvarteret ${\mathcal {N}}(x_{i})$ i en vertex $x_{i}\in V$ är helt enkelt uppsättningen av grannar ${\mathcal {N}}(x_{i}):=\{x_{j}\in V\colon x_{j} \sim x_{i}\}$ . Graden av en vertex $x_{i}\in V$ är den viktade storleken på dess grannskap:

$\deg(x_{i}):=\summa _{j\,:\,x_{j}\sim x_{i}}w(x_{i},x_{j}).$

Observera att i specialfallet där $w\equiv 1$ på $E$ (dvs grafen är oviktad ) har vi $\deg(x_{i}):=|{\mathcal {N}}(x_{i})|$ .

Utrymme av verkliga vertexfunktioner

Låt ${\displaystyle {\mathcal {H}}(V):=\{f:V\rightarrow \mathbb {R} \}} vara$ utrymmet för (verklig ) vertexfunktioner . Eftersom $V$ är en finit mängd kan vilken vertexfunktion $f\in {\mathcal {H}}(V)$ representeras som en $n$ - dimensionell vektor $f\in \mathbb {R} ^{n}$ (där $n:=|V|$ ) och därav utrymmet för vertexfunktionerna ${\mathcal {H}}(V)$ kan identifieras med ett $n$ -dimensionellt Hilbert-rymd: ${\mathcal {H}}( V)\cong \mathbb {R} ^{n}$ . Den inre produkten av ${\mathcal {H}}(V)$ definieras som:

$\langle f,g\rangle _{{\mathcal {H}}(V)}:=\summa _{x_{i}\in V}f(x_{i})g(x_{i} ),\quad \forall f,g\in {\mathcal {H}}(V).$

Dessutom, för alla vertexfunktioner $f\in {\mathcal {H}}(V)$ är $\ell _{p}$ -norm och $\ell _{\infty }$ -norm av $f$ definieras som:

$\|f\|_{p}={\begin{cases}\left(\summa _{x_{i}\in V}|f(x_{i})|^{p}\right) ^{\frac {1}{p}},&{\text{ för }}1\leqslant p<\infty \ ,\\\max _{x_{i}\in V}|f(x_{i} )|,&{\text{ för }}p=\infty \ .\end{cases}}$

ℓ $\ell _{2}$ induceras av den inre produkten.

I applikationer är vertexfunktioner användbara för att märka nodernas hörn. Till exempel, i grafbaserad dataklustring, representerar varje nod en datapunkt och en vertexfunktion används för att identifiera klustermedlemskap i noderna.

Utrymme av riktiga kantfunktioner

Analogt med verkliga vertexfunktioner kan man introducera rymden för verkliga kantfunktioner ${\mathcal {H}}(E):=\{F:E\rightarrow \mathbb {R} \}$ . Eftersom vilken kantfunktion som helst $F$ är definierad på en ändlig uppsättning kanter $E$ , kan den representeras som en $m$ -dimensionell vektor $F\in \mathbb {R} ^{m}$ , där $m:=|E|$ . Följaktligen kan utrymmet för kantfunktionerna ${\mathcal {H}}(E)$ identifieras som ett $m$ -dimensionellt Hilbert-utrymme, dvs ${\mathcal {H}}(E)\cong \mathbb {R} ^{m}$ .

Ett specialfall av en kantfunktion är den normaliserade kantviktsfunktionen $w\colon E\rightarrow (0,1]$ introducerad ovan i avsnittet om grundläggande definitioner . Liknande den funktionen, valfri kantfunktion $F$ kan trivialt utökas till $V\times V$ genom att sätta $F(x_{i},x_{j }):=0$ om $(x_{i},x_{j})\inte \in E$ . Utrymmet för dessa utökade kantfunktioner betecknas fortfarande med ${\mathcal {H}}(E)$ och kan identifieras med $\mathbb {R} ^{m}$ , där nu $m :=|V|^{2}$ .

Den inre produkten av ${\mathcal {H}}(E)$ definieras som:

$\langle F,G\rangle _{{\mathcal {H}}(E)}:=\summa _{(x_{i},x_{j})\in E}F(x_{i} ,x_{j})G(x_{i},x_{j}),\quad \forall F,G\in {\mathcal {H}}(E).$

Dessutom, för valfri kantfunktion $F\in {\mathcal {H}}(V)$ är $\ell _{p}$ -norm och $\ell _{\infty }$ -norm av $F$ definieras som:

$\|F\|_{p}={\begin{cases}\left(\summa _{(x_{i},x_{j})\in E}|F(x_{i},x_ {j})|^{p}\right)^{\frac {1}{p}}&{\text{ för }}1\leqslant p<\infty \ ,\\\max _{(x_{i },x_{j})\in E}|F(x_{i},x_{j})|,&{\text{ för }}p=\infty \ .\end{cases}}$

ℓ $\ell _{2}$ induceras av den inre produkten.

Om man förlänger kantmängden $E$ på ett sätt så att $E=V\x V$ blir det tydligt att ${ \mathcal {H}}(E)\cong \mathbb {R} ^{n\ gånger n}$ eftersom ${\mathcal {H}}(V)\cong \mathbb { R} ^{n}$ . Detta innebär att varje kantfunktion kan identifieras med en linjär matrisoperator.

Differentiella grafoperatorer

En viktig ingrediens i kalkylen på finita vägda grafer är efterlikningen av standard differentialoperatorer från kontinuuminställningen i den diskreta inställningen av finita vägda grafer. Detta gör att man kan översätta väl studerade verktyg från matematiken, såsom partiella differentialekvationer och variationsmetoder, och göra dem användbara i applikationer som bäst kan modelleras med en graf. Det grundläggande konceptet som gör denna översättning möjlig är grafgradienten, en första ordningens skillnadsoperator på grafer. Baserat på detta kan man härleda högre ordningens differensoperatorer, t.ex. grafen Laplacian.

Första ordningens differentialoperatörer

Viktade skillnader

Låt $G=(V,E,w)$ vara en ändligt viktad graf och låt $f\in {\mathcal {H}}( V)$ vara en vertexfunktion. Då är den viktade skillnaden (eller den viktade grafderivatan ) av $f$ längs en riktad kant $(x_{i},x_{j})\in E$

$\partial _{x_{j}}f(x_{i})\ :=\ {\sqrt {w(x_{i},x_{j})}}\left(f(x_{j} )-f(x_{i})\höger).$

För varje viktad skillnad gäller följande egenskaper:

• $\partial _{x_{i}}f(x_{j})=-\partial _{x_{j}}f (x_{i}),$
• $\partial _{x_{i}}f(x_{i})=0,$
• $f(x_{i})=f(x_{j})\Högerpil \partial _{x_{j }}f(x_{i})=0.$

Viktad gradient

Baserat på begreppet viktade skillnader definierar man den viktade gradientoperatorn på grafer $\nabla _{w}:{\mathcal {H}}(V)\rightarrow { \mathcal {H}}(E)$ som

$(\nabla _{w}f)(x_{i},x_{j})\ =\ \partial _{x_{j}}f(x_{i}).$

Detta är en linjär operator .

För att mäta den lokala variationen av en vertexfunktion $f$ i en vertex $x_{i}\in V$ kan man begränsa gradienten $\nabla _{w} f$ av $f$ till alla riktade kanter som börjar med $x_{i}$ och använder $\ell _{p}$ -normen för denna kantfunktion, dvs.

$\|(\nabla _{w}f)(x_{i},\cdot )\|_{\ell _{p}}={\begin{cases}\left(\summa _{x_{ j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^ {p}\right)^{\frac {1}{p}}&{\text{ för }}1\leq p<\infty ,\\\max _{x_{j}\sim x_{i}} {\sqrt {w(x_{i},x_{j})}}|f(x_{j})-f(x_{i})|&{\text{ för }}p=\infty .\end {fall}}$

Viktad divergens

Adjointoperatorn $(V)}$$\nabla _{w}^{*}\colon {\mathcal {H}}(E)\rightarrow {\mathcal {H$ } för den viktade gradientoperatorn är en linjär operator definierad av

$\langle \nabla _{w}f,G\rangle _{{\mathcal {H}}(E)}=\langle f,\nabla _{w}^{*}G\rangle _{{ \mathcal {H}}(V)}\quad {\text{ för alla }}f\in {\mathcal {H}}(V),G\in {\mathcal {H}}(E).$

För oriktade grafer med en symmetrisk viktfunktion $w\in {\mathcal {H}}(E)$ adjointoperatorn $\nabla _{w}^{*}$ av en funktion $F\in {\mathcal {H}}(E)$ vid en vertex $x_{i}\in V$ har följande form:

$\left(\nabla _{w}^{*}F\right)(x_{i})\ =\ \sum _{x_{j}\sim x_{i}}{{\sqrt {w (x_{i},x_{j})}}(F(x_{j},x_{i})-F(x_{i},x_{j}))}.$

Man kan sedan definiera den viktade divergensoperatorn på grafer via adjointoperatorn som $\operatornamn {div} _{w}:=-\nabla _{w}^{*}$ . Divergensen på en graf mäter nettoutflödet av en kantfunktion i varje hörn av grafen.

Andra ordningens differentialoperatorer

Graf Laplace-operatör

Den viktade grafen Laplacian $\Delta _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)$ är en väl studerad operator i grafinställningen. Genom att efterlikna förhållandet $\operatorname {div} (\nabla f)=\Delta f$ för Laplace-operatorn i kontinuuminställningen, kan den viktade grafen Laplacian härledas för vilken vertex som helst $x_{i}\in V$ som:

${\begin{aligned}(\operatörsnamn {div} _{w}(\nabla _{w}f))(x_{i})&={\frac {1}{2}}\sum _ {x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}(\nabla _{w}f(x_{j},x_{i})- \nabla _{w}f(x_{i},x_{j}))\\&={\frac {1}{2}}\summa _{x_{j}\sim x_{i}}{\ sqrt {w(x_{i},x_{j})}}\left({\sqrt {w(x_{i},x_{j})}}(f(x_{j})-f(x_{ i}))-{\sqrt {w(x_{j},x_{i})}}(f(x_{i})-f(x_{j}))\right)\\&={\frac {1}{2}}\summa _{x_{j}\sim x_{i}}w(x_{i},x_{j})(2f(x_{j})-2f(x_{i}) )\\&=\summa _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i}))\ =:\ (\Delta _{w}f)(x_{i}).\end{aligned}}$

Observera att man måste anta att grafen $G$ är oriktad och har en symmetrisk viktfunktion $w(x_{i}, x_{j})=w(x_{j},x_{i})$ för denna representation.

Diagram p-Laplace-operatorer

Den kontinuerliga $p$ -Laplace-operatorn är en andra ordningens differentialoperator som kan översättas väl till finita viktade grafer. Den tillåter översättning av olika partiella differentialekvationer, t.ex. värmeekvationen, till grafinställningen.

Baserat på första ordningens partiella skillnadsoperatorer på grafer kan man formellt härleda en familj av viktade grafer $p$ -Laplace-operatorer ${\displaystyle \Delta _{ w,p}\colon {\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)} för$ 1 $\displaystyle 1\leq p<\infty }$ genom minimering av diskret $p$ -Dirichlet energi funktionell

$E(f)\ :=\ {\frac {1}{p}}\summa _{x_{i}\in V}\|\nabla _{w}f(x_{i},\cdot )\|_{\ell _{p}}^{p}.$

De nödvändiga optimalitetsvillkoren för en minimering av energifunktionella $E$ leder till följande definition av grafen $p$ -Laplacian:

$(\Delta _{w,p}f)(x_{i})\ :=\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j} )^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p-2}(f(x_{j})-f(x_{i} ))$

Observera att grafen Laplace-operatorn är ett specialfall av grafen $p$ -Laplace-operatorn för ${\displaystyle p=2} ,$ dvs.

$(\Delta _{w,2}f)(x_{i})\ =\ (\Delta _{w}f)(x_{i})\ =\ \summa _{x_{j}\ sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i})).$

Ansökningar

Kalkylering på ändligt viktade grafer används i ett brett spektrum av applikationer från olika områden som bildbehandling, maskininlärning och nätverksanalys. En icke uttömmande lista över uppgifter där ändligt viktade grafer har använts är:

• bildnedsättning
• bildsegmentering
• bildmålning
• tomografisk rekonstruktion
• omvända problem
• dataklustring
• punktmolnkompression _
• handskriven sifferigenkänning

Se även

• Fasfältmodeller på grafer

Anteckningar

1. ^ Observera att en något annorlunda definition av oriktad graf också används, som anser att en oriktad kant är en tvåuppsättning (uppsättning med två distinkta element) $\{x_{i },x_{j}\}$ istället för ett par ordnade par $(x_{i},x_{j})$ och $( x_{j},x_{i})$ . Här behövs den senare beskrivningen, eftersom den krävs för att tillåta kantfunktioner i ${\mathcal {H}}(E)$ (se avsnittet om kantfunktionernas rymd ) att ta olika värden på $(x_{i},x_{j})$ och $(x_{j},x_{i})$ .