Li Hongyi Dyp Læring

[Li Hongyi 2020 ML / DL] P18-19 Graph Neural Network | NN4G, DCNN, MoNet, GraphSAGE, GAT, GIN, ChedNet, GCN

P18 19 Graph Neural Network Nn4g



Jeg har hatt to års erfaring med ML. Denne kursserien brukes hovedsakelig for å kontrollere mangler, og vil registrere noen detaljer som jeg ikke vet.

Noen har allerede tatt notater (veldig vanskelig, anbefales på det sterkeste): https://github.com/Sakura-gh/ML-notes



Tilsvarende merknader i dette avsnittet: Ingen



Disposisjon

  • Introduksjon
  • Veikart
  • Oppgaver, datasett og målestokk
  • Rombasert GNN
  • Graf signalbehandling og spektralbasert GNN
  • Grafgenerering
  • GNN for NLP

Hvordan legge inn node i et funksjonsrom ved hjelp av konvolusjon?

Det er to ideer:



  • Løsning 1: Generaliser begrepet konvolusjon (korelasjon) til graf >> Rombasert konvolusjon
  • Løsning 2: Tilbake til definisjonen av konvolusjon i signalbehandling >> Spektralbasert konvolusjon

Veikart

Oppgaver, datasett og målestokk

Oppgaver:

  • Semi-overvåket nodeklassifisering
  • Regresjon
  • Grafklassifisering
  • Læring av grafrepresentasjon
  • Link prediksjon



    Vanlig datasett:
  • CORA: siteringsnettverk. 2.7k noder og 5.4k lenker
  • TU-MUTAG: 188 molekyler med 18 noder i gjennomsnitt

Rombasert GNN



Bildet over viser den generelle ideen om romlig-basert GNN, ved hjelp av nabo-noder for å oppdatere konvolusjon:

  • Samlet først
  • Avlesning igjen.

NN4G (nevrale nettverk for graf)

I NN4G:

  • Først innebygging av inngangslaget
  • Deretter legger du til naboene til noden, multipliserer den med en vekt og legger til sin egen funksjon (w ˉ 1 ⋅ x 3 bar {w} _1 cdot x_3)
  • Les deretter ut (som vist i figuren nedenfor), legg sammen funksjonene til hvert lag, ta deretter gjennomsnittet, og multipliser deretter med forskjellige vekter, og legg til dem.

DCNN (Diffusion-Convolution Neural Network)

For DCNN behandler vi hver node i det første laget som følger:

  • Som følgerh 3 0 h_3 ^ 0, For å gjennomsnittliggjøre hver egenverdi, er objektet alt og gjeldende node Point at distance 1。

For det andre laget er avstanden 2.

h 3 0 = w 3 0 M E A N (d (3, ⋅) = 1) h_3 ^ 0 = w_3 ^ 0 BETYDNING (d (3, cdot) = 1)
h 3 1 = w 3 1 M E A N (d (3, ⋅) = 2) h_3 ^ 1 = w_3 ^ 1 BETYDNING (d (3, cdot) = 2)

Etter det, for hvert lag, blir node-egenverdivektorpunktene stablet i en matrise etter rader.

Dens Roadout er vist i figuren.

MoNET (Mixture Model Networks)

  • Definer et mål på nodenes 'avstander'
  • Bruk vektet sum (gjennomsnitt) i stedet for bare å oppsummere (gjennomsnitt) nabofunksjoner.

Forskjellig fra den forrige modellen: Denne modellen anser viktigheten av hver nabo for å være forskjellig og vurderer vekten mellom naboene.

Her bruker vi 'grad' for å definere kantvekten mellom naboeneu (x, y) u (x, y).

GraphSAGE （Liten og aggreGat）

  • Kan jobbe med både transduktiv og induktiv setting
  • GraphSAGE lærer hvordan du legger inn nodefunksjoner fra naboer


I tillegg til å snakke om å legge til naboer til gjennomsnittet, og bruke funksjonen som max-pooling, og også legge inn forskjellige ordrer i LSTM for å eliminere effekten av orden.

GAT (Graph Attention Networks)

  • Input: node-funksjonerh = {h ⃗ 1, h ⃗ 2,…, h ⃗ N}, h ⃗ i ∈ RF mathbf {h} = left { vec {h} _ {1}, vec {h} _ { 2}, ldots, vec {h} _ {N} right }, vec {h} _ {i} in mathbb {R} ^ {F}
  • Beregn energi:eij = a (W h ⃗ i, W h ⃗ j) e_ {ij} = a left ( mathbf {W} vec {h} _ {i}, mathbf {W} vec {h} _ { j} høyre)
  • Oppmerksomhetspoeng (over naboene)

α ij = exp ⁡ (LeakyReLU (a → T [W h ⃗ i ∥ W h ⃗ j])) ∑ k ∈ N i exp ⁡ (LeakyReLU (a → T [W h ⃗ i ∥ W h ⃗ k])) alpha_ {ij} = frac { exp left ( text {LeakyReLU} left ( overrightarrow { mathbf {a}} ^ {T} left [ mathbf {W} vec {h} _ { i} | mathbf {W} vec {h} _ {j} right] right) right)} { sum_ {k in mathcal {N} _ {i}} exp left ( text {LeakyReLU} left ( overrightarrow { mathbf {a}} ^ {T} left [ mathbf {W} vec {h} _ {i} | mathbf {W} vec {h} _ {k} right] right) right)}

For å beregne en node, må du først beregne oppmerksomheten til forskjellige naboer, beregne energien til de to nodene, og dette brukes som vekt for vekting. Som vist under.

Denne GAT brukes oftere

GIN (Graph Isomorphism Network)

  • Et GNN kan være maksimalt like kraftig som WL-isomorf test
  • Teoretiske bevis ble levert

Denne undersøkelsen gir noen teoretiske bevis, og konklusjonen er:

  • Når du oppdaterer, er det best å bruke følgende formelh v (k) h_v ^ {(k)}Oppdater (legg til naboer, og legg deretter til egne multipler)
  • Sum i stedet for gjennomsnitt eller maks

hv (k) = MLP ⁡ (k) ((1 + ϵ (k)) ⋅ hv (k - 1) + ∑ u ∈ N (v) hu (k - 1)) h_ {v} ^ {(k) } = operatorname {MLP} ^ {(k)} left ( left (1+ epsilon ^ {(k)} right) cdot h_ {v} ^ {(k-1)} + sum_ { u in mathcal {N} (v)} h_ {u} ^ {(k-1)} right)

Hvorfor bruke sum i stedet for gjennomsnitt eller maks? Følgende figur viser noen moteksempler på gjennomsnitt og maks.

Graf signalbehandling og spektralbasert GNN

Vi håper at grafen kan formes. Den generelle ideen er å endre grafen og filteret slik at de to kan multipliseres direkte. This involves some changes in the signal and system courses.

Signal og system

N-dim Vector Space

Signalet kan sees på som et sett med N-dimensjonale vektorer. Denne vektoren i lineært rom er sammensatt av flere basisvektorer synthesis av:

A ⃗ = ∑ k = 1 N a k v ^ k vec {A} = sum_ {k = 1} ^ N a_k hat {v} _k

Hvis du vil analysis Hva er en bestemt basisvektor, må du gjøre det indre produktet:

a j = A ^ ⋅ v ^ j a_j = hat {A} cdot hat {v} _j

I tillegg, anta at basisvektorene våre er ortogonale (ortogonale):

v ^ i ⋅ v ^ j = δ i j hat {v} _i cdot hat {v} _j = delta_ {ij}

Fourier Series Representasjon

I tidsdomenet brukes ofte basisvektorene til synd og cos.

For et periodisk signal kan det utvides til Fourier-serien:
x (t) = ∑ k = - ∞ ∞ hvilken som helst ω 0 t = ∑ k = - ∞ ∞ ak ϕ k (t) x (t) = sum_ {k = - infty} ^ { infty} a_ {k } e ^ {jk omega_ {0} t} = sum_ {k = - infty} ^ { infty} a_ {k} phi_ {k} (t)

a k ϕ k (t) a_ {k} non_ {k} (t): j-th harmoniske komponenter

Vi har forskjellige måter å beregne påa k a_kstørrelsen til.

Signalrepresentasjon i to domener

Time Domain Basis

A ⃗ = ∑ i a i v ⃗ i vec {A} = sum_ {i} a_i vec {v} _i

x (t) = ∫ - ∞ ∞ x (τ) δ (t - τ) d τ x (t) = int _ {- Infty} ^ { Infty} x () delta (t ) d

I tillegg kan den samme gruppen av signaler også være representert ved forskjellige grunnlag, som kan skrives i følgende form:

x (t) = 1 2 π ∫ - ∞ ∞ X (j ω) ej ω td ω x (t) = frac {1} {2 pi} int ^ { infty} _ {- infty} X (j omega) e ^ {j omega t} d omega

. . . = ∑ k (... B k) u ⃗ k ... = sum_k (... b_k) vec {u} _k

Basis for frekvensdomene

A ⃗ = ∑ k b k u ⃗ k vec {A} = sum_ {k} b_k vec {u} _k

x (t) = 1 2 π ∫ - ∞ ∞ X (j ω) ej ω td ω x (t) = frac {1} {2 pi} int ^ { infty} _ {- infty} X (j omega) e ^ {j omega t} d omega

x (t) = ∫ - ∞ ∞ x (τ) δ (t - τ) d τ x (t) = int _ {- Infty} ^ { Infty} x () delta (t ) d

. . . = ∑ i (... A i) v ⃗ i ... = sum_ {i} (... a_i) vec {v} _i

Fourier transform

Fourier-transform refererer til prosessen med å analysere grunnlaget.

Spektralgrafteori


Som ovenfor, i grafteori, skal tre matriser deklareres, inkludert kritisk matrise og gradmatrise. Hver node har sin egen signal。

Vektoren eller konstanten til hver node kan forstås som signalet til denne noden.

basert på Tulaplace's expansion theorem, kan Positive semi-definite matrix L Del. Eksempler er som følger.

Vertex domenesignal


Beregn først L basert på D og A, og del deretter L iΛ LambdamotU U.

In U, the number of rows represents the node the number of columns represents the 'frequency' in the signal.

Tegn den ut som vist nedenfor.

Hvorfor forstår du 'frekvens' på denne måten? La oss starte diskusjonen.

Diskret tid Fourier basis


I signalet, jo større frekvens, desto større endres signalet mellom to tilstøtende punkter.

Tolker toppunktfrekvens


Det kan sees at den endelige Lf-verdien faktisk er dens egen energimultipel minus energisummen til naboene.

Denne energien må firkantes for å være fornuftig, som vist i figuren nedenfor.

Det kan sees at endringen av signalenergi faktisk representerer om nodene er glatte.

Når du går tilbake til det originale bildet, kan du se:

  • Den såkalte energiforskjellen erλ i lambda_i；
  • λ = 0 lambda = 0Når det er en likestrømskomponent DC component。
Et spesielt eksempel: en linjediagram med 20 noder


Det kan sees at i dette spesifikke eksemplet, jo større frekvens, desto større energiforskjell.

Graf Fourier Transform av signal


Som vist i figuren ovenfor, i likhet med signalbehandlingen til høyre, vil vi utføreU T x U ^ T xDen indre produktoperasjonen av utføres faktisk på hver frekvens analysis. Derfor er den kartlagt til det spektrale domenet.

Invers graf Fourier Transform av signal

Det samme gjelder signalbehandling tilbake til tidsdomene.

Som vist Treat the node as a value on the horizontal axis in the time domain, and add up the parts of each frequency. Beregnes somx = U ⋅ x ^ x = U cdot hat {x}.

Filtrering og problem

Det vi bygde filter, er også basert på frekvens for strekkartlegging. Som vist under.

I faktiske beregninger passerer viy ^ = g θ (Λ) x ^ hatt {y} = g_ theta ( Lambda) hatt {x}Få den filtrerte verdien for hver frekvens.

Som vist nedenfor, vil vi endeligy ^ hat {y}Multipliser medU U, Gjør den inverse Fourier-transformasjonen og gå tilbake til verdien som tilsvarer hver node.

Den siste parameteren vi ønsker å trene er verdien av dette filteret. som følger.

Men problemet er:

  • lignendeg θ (L) = l o g (I + L) g_ theta (L) = log (I + L)Hvis denne funksjonen brukes som en filterfunksjon, Then the parameter size of the filter will change as the input changes (100,000 nodes, then 100,000 filter parameters) ；
  • I tillegg, som vist i figuren nedenfor, vil du lære det du ikke vil lære (hvis koeffisienten til g erL N L ^ N, Så involverer hver filtrering den generelle situasjonen, nei Localize Opp).

ChebNet

Løs de to ovennevnte problemene, filter kan fikses og lokaliser.

Denne kostnadstiden er imidlertid for høy.

It uses a very magical method, as shown in the figure below, to solve the problem of calculating time cost.


som vist ovenfor, først erklærer vi en Chebyshev polynomial Polynomfunksjon. Basert på dette endrer vi g-funksjonen.

Vi vikler en funksjon inn i en polynomfunksjon. Betydningen er som følger.

Innpakning av en funksjon tilsvarer organisering av polynomer. For matematikkproblemet på videregående skole blir beregningen av polynomer mye lettere.

Basert på naturen til selve T-funksjonen, kan den avledes som følger.

Som ovenfor er beregningen sterkt forenklet.

Oppsummert, uavhengig av det matematiske beviset, er det vi må lære oss filteret.

GCN

GCN er den mest brukte og relativt enkle og intuitive.

Den matematiske avledningen bak GCN er som ovenfor, der:

  • Det behandler K i ChebNet som 1
  • Og gjorde mange tilnærminger for å forenkle
  • Og for å forfølge færre parametere, erklærer det forholdet mellom selvinnstilte parametereθ = θ 0 ′ = - θ 1 ′ theta = theta_0 '= - theta_1'
  • Og laget en renormalization trick。


GCN oppsummerer det:

  • Legg til nabo-nodene, og legg deretter til forskyvningen
  • Deretter oppnås neste lag av nevrale nettverk gjennom en aktiveringsfunksjon.

Oppgaver, datasett og målestokk - Resultater


Det kan sees at GCN ikke er veldig bra. Men noen varianter er veldig sterke.




Antall lag har økt, og GCN har blitt dårligere.

Søknad til GCN

Det er bevist at jo flere lag med GCN er stablet, desto mer sannsynlig er det å være et problem:

@inproceedings{ Oono2020Graph, title={Graph Neural Networks Exponentially Lose Expressive Power for Node Classification}, author={Kenta Oono and Taiji Suzuki}, booktitle={International Conference on Learning Representations}, year={2020}, url={https://openreview.net/forum?id=S1ldO2EFPr} }

Hvordan løse dette problemet? Noen foreslo drop edge Metoder:

  • DropEdge: Towards Deep Graph Convolutional Networks on Node Classification

Grafgenerering




kort nevnt tre metoder for generering av graf.

Sammendrag