Directed Acyclic Graph Convolutional Networks

Technische Samenvatting: Convolutionele Netwerken voor Gerichte Acyclische Grafen (DCN)

Probleemstelling
Gerichte Acyclische Grafen (DAG's) zijn fundamenteel voor toepassingen die causale inferentie, planning en het ontwerpen van neurale architecturen omvatten. Het leren van signalen die op DAG's worden ondersteund, vormt echter unieke uitdagingen voor Graph Neural Networks (GNN's). Standaard GNN's vertrouwen op iteratief berichtenverkeer en spectrale analyse gebaseerd op grafverschuivingsoperatoren (GSO's). Bij DAG's is de bijkomende matrix strikt onder-driehoekig en nilpotent, wat resulteert in een ingestorte spectrum (alle eigenwaarden zijn nul). Dit maakt standaard instrumenten uit de spectrale graaftheorie nutteloos en verhindert de directe toepassing van conventionele convolutionele GNN's. Bovendien kunnen generieke aggregatiemechanismen in standaard GNN's de sterke inductieve bias van de partiële ordening die inherent is aan DAG's, niet expliciet in aanmerking nemen. Bestaande DAG-specifieke modellen, zoals D-VAE en DAGNN, vertrouwen vaak op computatief intensieve sequentiële bewerkingen (bijvoorbeeld recurrente eenheden) die niet goed schalen naar grote grafen.

Methodologie
De auteurs stellen de DAG Convolutional Network (DCN) voor, een nieuw architectuurconcept dat is gebaseerd op principes van Graph Signal Processing (GSP) en specifiek is toegesneden op DAG's. De kernmethodologie vertrouwt op causale graaffilters die zijn afgeleid uit het kader van de gewogen transitieve sluiting.

1. Causale Grafverschuivingsoperatoren (GSO's): In plaats van de bijkomende matrix $A$ te gebruiken, maakt de DCN gebruik van een set causale GSO's $\{S_k\}_{k \in V}$. Deze operatoren worden gedefinieerd via de gewogen transitieve sluitingsmatrix $W = (I - A)^{-1}$, die overeenkomt met het bereikbaarheidsgraph van de DAG. Een causale GSO $S_k$ aggregeert signaalbijdragen van de gemeenschappelijke voorouders van een knoop $v_i$ en een referentieknoop $v_k$.
2. Spectrale Interpretatie: De kolommen van $W$ dienen als een Fourier-basis voor DAG-signalen. De causale GSO's zijn idempotent en delen $W$ als hun eigenvectormatrix, wat een goed gedefinieerde spectrale domeinrepresentatie mogelijk maakt waarbij filteren overeenkomt met puntsgewijze schaling van Fourier-coëfficiënten.
3. DCN Architectuur: De DCN implementeert convoluties per laag met behulp van een bank van deze causale GSO's. Voor een invoersignaal $X$ wordt de output van laag $\ell$ berekend als:
   $$X^{(\ell)} = \sigma \left( \sum_{k \in V} S_k X^{(\ell-1)} \Theta^{(\ell)}_k \right)$$
   waarbij $\Theta^{(\ell)}_k$ leerbare filtercoëfficiënten zijn en $\sigma$ een niet-lineariteit is. Deze structuur vangt langafstandige afhankelijkheden van voorouders efficiënt op via verspreide matrixvermenigvuldigingen.
4. Parallelle DCN (PDCN): Om schaalbaarheidsproblemen aan te pakken waarbij het aantal parameters in DCN lineair groeit met het aantal knopen $N$, introduceren de auteurs PDCN. Deze variant verwerkt verschoven signalen $\{S_k X\}$ in parallelle takken via een gedeeld Multi-Layer Perceptron (MLP), en de outputs worden opgeteld. Dit ontwerp ontkoppelt het aantal leerbare parameters van de grootte van de graaf, waardoor het schaalbaar is voor grote $N$.

Belangrijkste Bijdragen

• Nieuwe Architectuur: De ontwikkeling van DCN, die convolutionele bewerkingen op DAG's formaliseert met behulp van causale graaffilters, en een spectrale interpretatie biedt die eerder niet beschikbaar was voor DAG-signalen.
• Schaalbare Variant: De introductie van PDCN, die voorspellende prestaties behoudt terwijl het aantal parameters constant blijft, ongeacht de grootte van de DAG.
• Theoretische Eigenschappen:
  • Permutatie-equivariantie: De auteurs bewijzen dat zowel DCN als PDCN permutatie-equivariant zijn, wat robuustheid garandeert tegen herlabeling van knopen.
  • Uitdrukkingskracht: Het is vastgesteld dat PDCN voldoet aan de voorwaarden van de Weisfeiler-Lehman (WL)-test en in staat is om niet-isomorfe DAG's van elkaar te onderscheiden.
  • Uniciteit: Proposition 2 toont aan dat de set causale GSO's de onderliggende DAG-structuur uniek identificeert.
• Efficiëntie: De architectuur maakt gebruik van verspreide matrixoperaties en vooraf berekenbare verschuivingsoperatoren, wat aanzienlijke computationele voordelen biedt ten opzichte van sequentiële DAG-modellen.

Experimentele Resultaten
Het artikel evalueert (P)DCN op synthetische en real-world datasets tegen state-of-the-art baselines (waaronder GCN, GIN, D-VAE, DAGNN en DAG+NodeFormer).

• Synthetische Taken:
  • Diffusieleer: DCN bereikt een lagere Genormaliseerde Gemiddelde Kwikkelfout (NMSE) dan baselines bij het voorspellen van gediffundeerde signalen, wat superieure robuustheid tegen ruis en variërende randdichtheden aantoont.
  • Bronidentificatie: DCN-varianten (specifiek met gebruik van getransponeerde GSO's) bereiken hoge nauwkeurigheid bij het traceren van signaalbronnen, presteren beter dan DAG-agnostische modellen en tonen betere schaalbaarheid dan sequentiële modellen zoals DAGNN.
  • Schaalbaarheid: Naarmate de grafgrootte toeneemt (tot $N=1000$), behouden DCN en PDCN hun prestaties en redelijke trainingstijden, terwijl modellen zoals DAGNN en D-VAE falen om te voltooien (DNF) vanwege geheugen- en tijdsbeperkingen.
• Real-world Toepassingen:
  • Imputatie van Genexpressie: Op een dataset van Arabidopsis Thaliana imputeren DCN en PDCN succesvol ontbrekende genexpressieniveaus, met een NMSE die vergelijkbaar is met D-VAE en DAGNN, maar met een aantal parameters dat enkele ordes van grootte lager is en snellere trainingstijden.
  • Hydrologische Voorspelling: Op data van de rivier de Theems presteert DCN beter dan alle baselines bij het voorspellen van chemische concentraties op niet-gewaarnomen locaties, door effectief gebruik te maken van de stroomstructuur van stroomopwaarts naar stroomafwaarts.

Betekenis en Beweringen
Het artikel positioneert (P)DCN als een haalbaar kader voor deep learning op DAG-gestructureerde data, ontworpen vanuit eerste principes van grafsignaalverwerking. De auteurs beweren dat door de partiële ordening van DAG's direct op te nemen in de convolutionele operatoren, de modellen een sterke inductieve bias bereiken die de nauwkeurigheid, robuustheid en computationele efficiëntie verbetert ten opzichte van bestaande methoden. Het werk overbrugt de kloof tussen causale inferentiemodellen en deep learning, en biedt een principiële alternatief voor sequentiële aggregatiemethoden. De auteurs erkennen beperkingen, met name dat de afhankelijkheid van een groot aantal GSO's in de volledige DCN nog steeds uitdagingen kan vormen voor zeer grote grafen, wat toekomstig werk suggereert in adaptieve selectie van GSO's.