Technische Samenvatting: Algoritmen met Optimale Tijdcomplexiteit voor het Berekenen van Algemene RWK's op Sparse Grafen

Probleemstelling

Het artikel behandelt de computationele flessenhals die gepaard gaat met het berekenen van Algemene Random Walk Kernels (RWK's) voor sparse grafen. RWK's zijn een gevierde familie van positief definite, symmetrische functies die gelijkenissscores toekennen aan paren grafen door een gewogen som te nemen van wandelingen van verschillende lengtes op de directe productgraaf $G_1 \times G_2$.

Hoewel RWK's populaire kernels omvatten zoals gemarginaliseerde, geometrische en exponentiële kernels, is hun exacte berekening prohibitief duur. Voor grafen met $N$ knopen bedraagt de brute-force evaluatie via de directe productgraaf een complexiteit van $O(N^6)$. Zelfs geoptimaliseerde methoden, zoals het oplossen van Sylvester-vergelijkingen of het gebruik van spectrale decompositie, vereisen doorgaans $O(N^3)$ tijd en falen vaak bij het verwerken van gelabelde grafen of het schalen naar massale datasets. Bovendien kunnen bestaande sub-kubische methoden over het algemeen niet omgaan met willekeurige coëfficiëntenseries $(\mu_i)$ die nodig zijn voor het leren van de kernelparameters. Opvallend genoeg bood eerder werk door Kang et al. (2012) wel een $O(N)$ algoritme, maar dit was beperkt tot het specifieke geval van geometrische RWK's op ongelabelde grafen.

De centrale vraag is: Is het mogelijk om onbevooroordeelde schattingen van algemene RWK's voor sparse, gelabelde grafen te berekenen met een lineaire tijdscomplexiteit van $O(N)$?

Methodologie: Graph Voyagers (GVoys)

De auteurs stellen Graph Voyagers (GVoys) voor, het eerste algoritme dat een onbevooroordeelde benadering van algemene RWK's kan bereiken in $O(N)$ tijd voor zowel gelabelde als ongelabelde sparse grafen. De methode generaliseert Graph Random Features (GRFs), maar introduceert specifieke mechanismen om het instantiëren van de directe productgraaf $G_1 \times G_2$ in het geheugen te vermijden.

Kernmechanisme

1. Afhankelijke Random Walks: In plaats van wandelingen te samplen op de enorme productgraaf, samplen GVoys onafhankelijke random walks op $G_1$ en $G_2$. Om wandelingen op de productgraaf te emuleren, worden deze onafhankelijke wandelingen gekoppeld via gedeelde random variabelen.
2. Filtering via Random Variabelen:
   • Lengte-matching ($g$-variabelen): Om ervoor te zorgen dat alleen wandelingen van dezelfde lengte bijdragen aan de kernel (zoals vereist door de definitie van de productgraafwandeling), vermenigvuldigt het algoritme de bijdragen van wandelingen met gedeelde Rademacher random variabelen $g(l)$ bij elke stap $l$. Omdat $E[g(l_1)g(l_2)] = \mathbb{I}(l_1 = l_2)$, verdwijnen kruistermen waarbij de wandellengtes verschillen in verwachting.
   • Label-matching ($z$-variabelen): Voor gelabelde grafen introduceert het algoritme aanvullende gedeelde random variabelen $z(l, i)$ die overeenkomen met de labels van de knopen. Dit filtert bijdragen uit van wandelingen waarbij de sequentie van knopenlabels niet overeenkomt, wat effectief de beperking afhandelt dat randen in de productgraaf alleen bestaan tussen knopen met identieke labels.
3. Graaf-niveau Embeddings: Het algoritme construeert laagdimensionale feature-vectoren voor elke graaf. Het dot product van deze embeddings voor een willekeurig paar grafen $(G_i, G_j)$ levert een onbevooroordeelde schatting van de ware RWK $K_{RWK}(G_i, G_j)$.
4. Geheugenefficiëntie: De methode instantiëren de adjacency matrix van de productgraaf niet. Het maakt gebruik van sparse representaties en ankerpunten om de dimensionaliteit te reduceren, waardoor de ruimtecomplexiteit lineair blijft ten opzichte van het aantal knopen.

Algoritmische Details

• Input: Grafen $G_i$, modulatiefunctie $f_\mu$ (afgeleid van coëfficiënten $\mu_i$), terminatiekans $p_{halt}$, en het aantal wandelingen $m$.
• Proces:
  1. Initialiseer gedeelde random sequenties $g$ en $z$.
  2. Simuleer voor elke graaf $m$ random walks startend vanaf diverse knopen.
  3. Cumuleer "deposits" bij ankerknopen, gewogen door de modulatiefunctie, de random variabelen en de wandelkans.
  4. Construeer feature-matrices $C_i$ en $D_i$.
• Output: Feature-vectoren $\phi(G_i)$ zodanig dat $K_{RWK}(G_i, G_j) = \mathbb{E}[\phi(G_i)^\top \phi(G_j)]$.

Belangrijkste Bijdragen

1. Lineaire Tijdscomplexiteit: Het artikel presenteert het eerste $O(N)$ algoritme voor de onbevooroordeelde benadering van algemene RWK's (die willekeurige coëfficiëntenseries $(\mu_i)$ dekken) voor zowel gelabelde als ongelabelde sparse grafen. Dit breidt de eerdere $O(N)$ methoden uit die beperkt waren tot specifieke gevallen zoals geometrische RWK's op ongelabelde grafen.
2. Schaalbaarheid naar Massale Datasets: Door het niet instantiëren van de directe productgraaf, schaalt de methode naar grafen met $>2^{14}$ knopen en datasets met duizenden grafen, waar eerdere methoden faalden door geheugenbeperkingen (OOM) of tijdslimieten.
3. Theoretische Garanties:
   • Onbevooroordeeldheid: Theorem 4.1 bewijst dat de estimator onbevooroordeeld is.
   • Concentratie: Theorem 4.2 biedt exponentiële concentratiebounds, die aantonen dat de estimator scherp convergeert naar de ware kernelwaarde.
   • Optimaliteit: Theorem 4.3 demonstreert dat het gebruik van Rademacher-distributies voor de random variabelen $g$ de variantie van de estimator minimaliseert.
4. Impliciet Kernel Leren: Het vermogen om algemene RWK's te benaderen (in plaats van vaste speciale gevallen) maakt het end-to-end leren van de coëfficiëntenserie $(\mu_i)$ mogelijk, wat schaalbaar impliciet graph kernel leren ontsluit.

Experimentele Resultaten

De auteurs evalueerden GVoys op de TUDataset en synthetische Erdős-Rényi grafen:

• Nauwkeurigheid: GVoys convergeert naar exacte RWK-waarden naarmate het aantal random walks toeneemt. In grafenclassificatietaken (bijv. MUTAG, ENZYMES, NCI1) kwam GVoys overeen met of presteerde het beter dan exacte RWK-baselines.
• Snelheid:
  • Voor grafen met $>2^{10}$ knopen presteerde GVoys beter dan spectrale decompositie, conjugate gradient en fixed-point iteratie methoden.
  • Op grafen met $2^{13}$ knopen was GVoys 27$\times$ sneller dan fixed-point iteratie.
  • Op grafen met $2^{14}$ knopen was GVoys 8$\times$ sneller dan conjugate gradient, terwijl andere baselines tekortkwamen in geheugen of tijd.
• Kernel Leren: Het leren van de coëfficiënten $(\mu_i)$ met behulp van GVoys op de MUTAG-dataset leverde een nauwkeurigheid op van $88,3\%$, een verbetering van $8,5\%$ ten opzichte van de standaard geometrische RWK-baseline ($81,4\%$).

Betekenis en Claims

Het artikel claimt de langdurige computationele barrière in graph kernel methoden te hebben opgelost. Door een lineaire tijd- en ruimtecomplexiteit te bereiken, maken GVoys het mogelijk om algemene random walk kernels toe te passen op massale, real-world datasets die voorheen onbereikbaar waren.

De auteurs benadrukken dat hun methode de eerste sub-kubische algoritme is dat een onbevooroordeelde benadering bereikt voor algemene RWK's op zowel gelabelde als ongelabelde grafen. Hoewel er eerder $O(N)$ algoritmen bestonden voor specifieke instanties (zoals geometrische RWK's op ongelabelde grafen), zijn GVoys de eersten die het algemene geval met willekeurige coëfficiënten en gelabelde knopen aanpakken. De introductie van nieuwe graaf-embeddings (random features) die de kernelstructuur behouden, maakt lineaire schaling mogelijk ten opzichte van zowel het aantal knopen in een graaf als het aantal grafen in een dataset. Deze capaciteit wordt benadrukt als een vereiste voor schaalbaar impliciet graph kernel leren, waarbij de kernelparameters zelf uit de data worden geleerd.

Het artikel concludeert dat hoewel de methode onbevooroordeeld is voor ongewogen, ongerichte grafen, de stochastische aard van de estimator mogelijk robuustheid biedt tegen ruis in downstream taken, wat potentieel beter presteert dan exacte kernelberekeningen in classificatiescenario's.