Technische Samenvatting: Full-Spectrum Graph Neural Network: Uitdrukkingskrachtig en Schaalbaar

Probleemstelling

Standaard spectrale Graph Neural Networks (GNN's) parametriseren grafpropagatie als Laplacian-filtering. Hoewel is vastgesteld dat spectrale GNN's nodesignals universeel kunnen benaderen, is hun uitdrukkingskracht in het onderscheiden van niet-isomorfe grafen strikt begrensd door de 1-dimensionale Weisfeiler–Lehman-test (1-WL-test). Deze beperking weerspiegelt hun onvermogen om hogere-orde signalen universeel te benaderen. Bovendien vertrouwen klassieke spectrale GNN's op diagonale spectrale filters (functies van enkele eigenwaarden), wat hun vermogen beperkt om complexe interacties te modelleren, met name in heterofiele grafen waar aangrenzende knopen vaak verschillende labels hebben. Bestaande benaderingen om de 1-WL-test te overtreffen, behelzen doorgaans het tillen van berichtuitwisseling naar hogere-orde domeinen (bijv. knopparen) in het ruimtelijke domein, maar een overeenkomstig schaalbaar spectraal kader ontbrak.

Methodologie

De auteurs stellen FSPECGNN (Full-Spectrum Graph Neural Network) voor, een generalisatie van de tweede orde van klassieke spectrale GNN's. De methodologie is gebaseerd op twee kerntheoretische doorbraken:

1. Signal Domein Lifting: In plaats van nodesignals $x \in \mathbb{R}^V$ te filteren, werkt FSPECGNN op knopparsignalen $\varepsilon \in \mathbb{R}^{V \times V}$. Dit tilt het signaal op van het knopdomein naar het knoppardomein.
2. Bivariate Spectrale Filtering: Klassieke spectrale filtering past een univariate functie $g(\lambda)$ toe op eigenwaarden. FSPECGNN breidt dit uit tot een bivariaat filter $g(\lambda_i, \lambda_j)$ over paren van eigenwaarden.
   • De full-spectrum convolutie is gedefinieerd als:
     $$G_\lambda *_{\mathcal{G}} \varepsilon = \sum_{i,j} g(\lambda_i, \lambda_j) u_i u_i^\top \varepsilon u_j u_j^\top$$
     waarbij $L = U\Lambda U^\top$ de eigendecompositie is van de graf-Laplacian.
   • Deze formulering generaliseert klassieke spectrale GNN's, waarvan wordt aangetoond dat ze een diagonale speciale geval zijn van FSPECGNN (teruggekregen door het filter te beperken tot de diagonaal $g(\lambda_i, \lambda_i)$).

Schaalbare Implementatie:
Directe berekening in het knoppardomein ($n^2 \times n^2$) is onuitvoerbaar voor grote grafen. Om dit aan te pakken, stellen de auteurs een schaalbare implementatie voor met behulp van low-rank tensor decompositie:

• Het bivariate polynoomfilter wordt benaderd door een som van scheidbare univariate polynomen: $P(L \otimes I, I \otimes L) \approx \sum_{r=1}^S f_r(L) \otimes h_r(L)$.
• Met gebruik van de eigenschap $(A \otimes B)\text{vec}(\varepsilon) = \text{vec}(B\varepsilon A^\top)$ wordt de convolutie berekend als $h(L) \varepsilon f(L)^\top$, waardoor het expliciet construeren van de $n^2$-dimensionale operator wordt vermeden.
• Het initiële knopparsignaal $\varepsilon$ wordt geconstrueerd via een leerbare combinatie van de identiteit en een GAT-laag ($I + \alpha \text{GAT}$), wat feature-afhankelijke niet-diagonale menging induceert.

Belangrijkste Bijdragen

1. Theoretische Uitdrukkingskracht:

   • Universele Benadering: De auteurs bewijzen dat lineaire FSPECGNN één-dimensionale knopparsignalen universeel kan benaderen (Stelling 3.4), waardoor de universaliteit van spectrale GNN's wordt uitgebreid van knopen naar knopparen.
   • 1-WL Superioriteit: Het artikel stelt vast dat FSPECGNN de 1-WL bovengrens kan overtreffen. Specifiek kan FSPECGNN onder voorwaarden van een eenvoudig spectrum en niet-nul spectrale coëfficiënten uitdrukkingskracht bereiken die equivalent is aan Local 2-GNN (een ruimtelijk model van de tweede orde), en deze potentieel overtreffen met specifieke bivariate polynomen (Stelling 3.8).

2. Heterofiele Grafen Leren:

   • De auteurs analyseren de optimale convolutie voor klassescheiding in heterofiele grafen. Ze bewijzen dat de optimale operator niet-diagonale componenten vereist in de spectrale basis (Stelling 4.1) om inter-klassen connecties te onderdrukken.
   • Een fundamentele beperking wordt bewezen: klassieke spectrale convoluties (diagonale filters) kunnen deze optimale operator niet realiseren, tenzij ze degenereren tot een scalair veelvoud van de identiteit (Stelling 4.2). FSPECGNN kan deze optimale operator realiseren door niet-diagonale spectrale interacties toe te staan.

3. Schaalbaarheid:

   • De voorgestelde low-rank benadering reduceert de computationele complexiteit tot $O(Kmd)$, vergelijkbaar met bestaande polynoom spectrale GNN's, terwijl het de $O(n^3)$ kosten van eigendecompositie en het $O(n^4)$ geheugengebruik van expliciete knoppaar-operaties vermijdt.

Experimentele Resultaten

Het artikel evalueert FSPECGNN op drie taken:

1. Heterofiele Noodclassificatie:

   • Getest op acht datasets (bijv. Texas, Wisconsin, Squirrel, Roman Empire).
   • FSPECGNN-varianten (met Chebyshev-, ChebNetII- en Bernstein-bases) presteerden consequent beter dan state-of-the-art spectrale baselines (ChebNet, GPRGNN, BernNet, etc.).
   • Ablatiestudies bevestigden dat het verwijderen van niet-diagonale interacties of de "in-filter" de prestaties aanzienlijk verslechterde, wat de noodzaak valideert van het modelleren van cross-eigenruimte koppeling.

2. Substructuur Telling (Validatie van Uitdrukkingskracht):

   • Geëvalueerd op homomorfisme- en (chordale) cykel-telling benchmarks.
   • FSPECGNN behaalde prestaties die vergelijkbaar waren met Local 2-GNN en Local 2-FGNN, wat de theoretische voorspelling bevestigt dat het de uitdrukkingskracht van ruimtelijke modellen van de tweede orde evenaart.
   • Het presteerde aanzienlijk beter dan Spectral Invariant GNN's en standaard MPNN's op deze taken.

3. Efficiëntie:

   • FSPECGNN toonde een aanzienlijk lagere runtime (ongeveer 5$\times$ sneller) en lager piek GPU-geheugen in vergelijking met ruimtelijke baselines van de tweede orde (Local 2-GNN, Local 2-FGNN, Subgraph GNN).

Betekenis en Claims

Het artikel stelt dat FSPECGNN een principieel spectraal tegenhanger biedt voor ruimtelijke GNN's van hogere orde. De primaire betekenis ligt in het overbruggen van de kloof tussen spectrale methoden en uitdrukkingskracht van hogere orde:

• Het demonstreert dat heterofylie een inherent tweede-orde fenomeen is dat niet-diagonale spectrale componenten vereist, die klassieke spectrale GNN's structureel missen.
• Het biedt een schaalbare architectuur die de theoretische voordelen van modellering van de tweede orde behoudt (het overtreffen van 1-WL, universele benadering op paren) zonder de prohibitieve computationele kosten van expliciete ruimtelijke methoden van hogere orde.
• Het werk identificeert een fundamentele beperking van diagonale spectrale filters en stelt een generaliseerbaar kader voor (uitbreidbaar naar $k$-de orde) om deze te overwinnen.