Random Wavelet Features for Graph Kernel Machines

Probleemstelling

Graph kernels bieden een fundamentele manier om gelijkenis tussen knopen in een graf te definiëren, wat essentieel is voor taken zoals knoopclassificatie, linkpredictie en signaalreconstructie. Deze kernels worden vaak gedefinieerd als een functie van de graf-Laplaciaan ($L$). Het directe berekenen van de volledige kernel-matrix (grootte $N \times N$) is echter computationeel onhaalbaar voor grote netwerken, met een kost van $O(N^3)$ door de noodzaak van een volledige eigenontbinding (eigendecompositie).

Bestaande methoden voor het benaderen van kernels, zoals "Random Fourier Features" voor Euclidische ruimtes, zijn niet direct toepasbaar op grafen zonder de structurele informatie te verliezen. Bestaande grafische random features (zoals g-GRFs) die gebaseerd zijn op ruimtelijke random walks, presteren vaak slecht bij kernels die spectraal gelokaliseerd zijn (d.w.z. kernels die voornamelijk lage frequenties of gladde modi benadrukken), omdat deze methoden moeite hebben met het vastleggen van langeafstandsafhankelijkheden.

Methodologie

De auteurs introduceren een nieuwe methode voor het genereren van randomized spectral node embeddings (gerandomiseerde spectrale knoop-embeddings). De kern van de aanpak ligt in het combineren van Graph Signal Processing (GSP) en random feature methods.

Het doel is een random feature map $\phi: V \to \mathbb{R}^K$ te construeren zodat het inproduct $\langle \phi_i, \phi_j \rangle$ een lage-rang benadering $\tilde{\Gamma}$ van de gewenste graf-kernel $\Gamma = h(L)$ benadert, zonder de volledige eigenontbinding van $L$ te hoeven uitvoeren.

De methode bestaat uit twee hoofdstappen (zie Algorithm 1):

1. Range Finding (Bepalen van de deelruimte):

   • Het doel is om een orthonormale basis $Q$ te vinden die de deelruimte benadert die wordt opgespannen door de $K$ gladste eigenvectoren van $L$ (de laagste eigenwaarden).
   • In plaats van de ideale laagdoorlaatfilter $\chi_K$ (die exact de eerste $K$ eigenvectoren selecteert) te gebruiken, wat onmogelijk is zonder de eigenwaarden te kennen, wordt een Chebyshev-polynoombenadering $p_\chi$ gebruikt.
   • Er worden $K+r$ willekeurige Gaussische signalen $G$ gegenereerd en gefilterd met dit polynoom: $B = p_\chi(L)G$.
   • Door Gram-Schmidt orthogonalisatie op $B$ toe te passen, wordt $Q$ verkregen.
   • Om de nauwkeurigheid te verhogen, wordt oversampling gebruikt (parameter $r$), wat de kans vergroot dat de berekende deelruimte goed overeenkomt met de werkelijke top-$K$ eigenvectoren.

2. Kernel Benadering (Embedding Constructie):

   • De uiteindelijke embedding-matrix $\Phi$ wordt berekend door de gefilterde signalen $Q$ te vermenigvuldigen met de wortel van de kernel-functie $h^{1/2}(L)$.
   • Ook hier wordt een polynoombenadering $p_h$ gebruikt voor de filter $h^{1/2}$.
   • De embedding voor knoop $i$ is de $i$-de kolom van $\Phi = (p_h(L)Q)^\top$.
   • Het inproduct van twee knoop-embeddings benadert de kernel-waarde: $\langle \phi_i, \phi_j \rangle \approx \Gamma_{ij}$.

Complexiteit:
De methode vermijdt de $O(N^3)$ kost. De dominantie ligt in het uitvoeren van matrix-vector producten met de Laplacian (via polynoombenadering). De totale tijdscomplexiteit is $O(MEK + NK^2)$ en de geheugencomplexiteit is $O(NK)$, waarbij $M$ de graad van het polynoom is en $E$ het aantal randen. Dit maakt de methode schaalbaar voor grote, schaarse grafen.

Belangrijkste Bijdragen

1. Randomized Spectral Embeddings: Een nieuwe constructie voor graf-embeddings die specifiek is ontworpen om lage-rang benaderingen van Laplacian-gebaseerde kernels te leveren.
2. Superieure Prestaties voor Spectraal Gelokaliseerde Kernels: De auteurs tonen aan dat hun methode aanzienlijk nauwkeuriger is dan bestaande ruimtelijke random feature methoden (zoals g-GRFs) voor kernels die sterk gelokaliseerd zijn in het frequentiedomein (bijv. diffusie-kernels met een smalle bandbreedte).
3. Theoretische Foutanalyse: Er wordt een strikte theoretische bovengrens afgeleid voor de benaderingsfout ($E = \|\Gamma - \tilde{\Gamma}\|$). Deze fout wordt opgesplitst in een fout door de range finding ($E_R$) en een fout door de polynoombenadering ($E_P$). De analyse toont aan dat de fout convergeert naar de optimale lage-rang benadering naarmate $M$ en $r$ toenemen.
4. Verbinding met Randomized SVD: De methode wordt in verband gebracht met Randomized Singular Value Decomposition (RSVD), waarbij wordt aangetoond dat het gebruik van graf-spectrale filters een verbetering biedt ten opzichte van de standaard RSVD voor deze specifieke toepassing.

Resultaten

De auteurs hebben hun methode getest op synthetische grafen (Swiss-Roll en Community-grafen) en vergeleken met g-GRFs en de optimale lage-rang benadering (via volledige eigenontbinding):

• Nauwkeurigheid bij smalle bandbreedte: Op een Swiss-Rool graf met 5.000 knopen presteerde de methode uitstekend voor diffusie-kernels met een hoge spectrale lokalisatie (kleine $\sigma$). De relatieve fout was aanzienlijk lager dan die van g-GRFs.
• Invloed van de rang ($K$):
  • Voor de Swiss-Roll graf (waar eigenwaarden gelijkmatig verspreid zijn), bereikte de methode een foutniveau dat zeer dicht bij de optimale rang-$K$ benadering lag tot $K \approx 1000$.
  • Voor de Community graf (waar eigenwaarden in clusters zitten), nam de nauwkeurigheid af bij hogere $K$ ($>80$) omdat de schatting van de $K$-de eigenwaarde onnauwkeurig werd in dicht op elkaar gepakte gebieden. Dit onderstreept dat de prestatie afhankelijk is van de eigenwaarde-verdeling.
• Computationele Efficiëntie: De tijdscomplexiteit groeide lineair met het aantal knopen $N$ (voor vaste $K$), in tegenstelling tot de kubische groei ($O(N^3)$) van exacte methoden. Voor grote $N$ was de methode dus aanzienlijk sneller dan het berekenen van de exacte kernel of de exacte SVD.

Significantie

Dit werk biedt een schaalbare en principieel onderbouwde oplossing voor het leren van graf-representaties met kernel-methoden. Het opent de deur voor het toepassen van geavanceerde kernel-machines op zeer grote netwerken, waarbij de structuur van de graf behouden blijft. De methode is vooral waardevol voor toepassingen waarbij globale geometrische eigenschappen (die corresponderen met lage frequenties in het spectrum) cruciaal zijn, een domein waar bestaande ruimtelijke benaderingsmethoden vaak tekortschieten. De combinatie van GSP-tools met random feature technieken vormt een nieuwe richting in het veld van graf-machine learning.