🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

Diese Arbeit stellt fest, dass Message-Passing-Graph-neuronale Netze mit teilweise zufälligen Knotenmerkmalen universelle Approximationsfähigkeiten für permutationsinvariante und permutationsäquivariante Funktionen auf festen gerichteten Graphen besitzen, während sie gleichzeitig theoretische obere Schrankken für deren Approximationsraten basierend auf der Netzwerkkomplexität herleitet.

Ursprüngliche Autoren: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Veröffentlicht 2026-07-30

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das Rätsel der gestaltwandelnden Menge

Stellen Sie sich vor, Sie versuchen, einem Computer beizubringen, die Welt nicht als Raster von Pixeln oder als Liste von Wörtern zu verstehen, sondern als ein Geflecht von Verbindungen. Dies ist das Reich der Graph Neural Networks (GNNs), eines Zweigs der künstlichen Intelligenz, der darauf ausgelegt ist, Daten zu verarbeiten, die wie eine Karte von Freunden, Molekülen oder Verkehrsrouten aussehen. In diesen Karten ist das Wichtigste nicht nur, was ein einzelnes Objekt ist, sondern wie es mit seinen Nachbarn verbunden ist.

Es gibt jedoch eine knifflige Regel, die diese Computer befolgen müssen: Symmetrie. Wenn Sie eine Gruppe von Freunden haben und deren Namen vertauschen, bleibt die Gruppe dieselbe Gruppe. Eine gute Graph-KI sollte nicht darauf achten, wer in Stuhl A oder Stuhl B sitzt; sie sollte nur darauf achten, welches Muster entsteht, wer mit wem spricht. Dies wird als Permutationsinvarianz (für die gesamte Gruppe) oder Permutationsäquivarianz (für die einzelnen Elemente) bezeichnet. Das Problem ist, dass Standard-KI-Modelle darin schlecht sind. Sie werden oft durch die Reihenfolge verwirrt, in der Daten eintreffen, und erkennen nicht, dass zwei unterschiedlich aussehende Listen von Namen tatsächlich denselben sozialen Kreis beschreiben.

Um dies zu beheben, haben Wissenschaftler versucht, der KI „zufälliges Rauschen“ oder „zufällige IDs“ zu geben, um ihr zu helfen, die Knoten voneinander zu unterscheiden – so ähnlich, als würde man jeder Person in einer Menge einen temporären, einzigartigen Aufkleber geben. Aber bis jetzt wussten wir nicht vollständig, ob dieser Trick die KI in die Lage versetzen könnte, jedes mögliche Muster zu lernen, oder ob es Grenzen für die Fähigkeit gab, komplexe Regeln zu erlernen. Diese Arbeit taucht tief in diese Frage ein und fragt: „Wenn wir diesen graph-lesenden Computern zufällige Aufkleber geben, können sie in der Lage sein, jede Graphstruktur perfekt zu verstehen?“

Die Magie der zufälligen Aufkleber

Die Autoren dieser Arbeit, Lukas Gonon, Thilo Meyer-Brandis und Niklas Weber, wollten beweisen, dass eine bestimmte Art von Graph-KI, ein sogenanntes Permutation-Equivariant Neural Network (PENN), unglaublich leistungsfähig wird, wenn man ihm zufällige Knotenmerkmale gibt. Stellen Sie sich ein PENN wie ein Team von Detektiven vor, die versuchen, ein Geheimnis auf einer Landkarte zu lösen. Normalerweise können die Detektive zwei Verdächtige nicht unterscheiden, wenn sie identisch aussehen und die gleichen Freunde haben. Aber wenn man jedem Verdächtigen einen zufälligen, einzigartigen Aufkleber (ein zufälliges Merkmal) gibt, können die Detektive sie endlich unterscheiden und den Fall lösen.

Die Hauptentdeckung des Papers ist eine „universelle“ Garantie. Die Autoren haben mathematisch bewiesen, dass diese PENNs, wenn man sie mit zufälligen Aufklebern füttert, in der Lage sind, jede messbare Funktion auf einem Graphen fester Größe mit beliebig hoher Wahrscheinlichkeit zu approximieren. Auf einfaches Deutsch übersetzt: Wenn Sie möchten, dass die KI eine bestimmte Regel über ein Netzwerk lernt (wie etwa vorherzusagen, ob ein Molekül giftig ist oder welches Finanznetzwerk gefährdet ist), und wenn Sie ihr genügend zufällige Aufkleber geben, gibt es eine PENN-Architektur, die diese Regel fast perfekt lernen kann. Dies gilt selbst dann, wenn die Regel unordentlich oder komplex ist und selbst wenn die Daten viele verschiedene Arten von Merkmalen an den Knoten und Kanten aufweisen.

Wie gut ist „gut genug“?

Das Paper sagt jedoch nicht nur „es funktioniert“; es sagt Ihnen auch, wie groß die KI sein muss, um die Aufgabe zu bewältigen. Die Autoren untersuchten Funktionen, die glatt und wohldefiniert sind (mathematisch gesehen „ $k$ -mal stetig differenzierbar“, wobei $k \ge 2$ ). Sie leiteten eine Formel für die Approximationsraten ab, was im Grunde ein Tempolimit beschreibt, wie schnell die KI lernt, wenn man sie größer macht.

Sie fanden heraus, dass die Tiefe des Netzwerks (die Anzahl der Schichten) nur logarithmisch wachsen muss, wenn man mehr Genauigkeit fordert. Das ist eine großartige Nachricht: Wenn Sie doppelt so viel Genauigkeit wollen, müssen Sie nicht das Gehirn verdoppeln; Sie benötigen nur ein winziges Stück mehr Tiefe. Die Anzahl der Verbindungen (nicht-Null-Gewichte) wächst jedoch polynomisch, wenn Sie mehr Genauigkeit fordern. Speziell skaliert die Komplexität mit einer Potenz von $1/\epsilon$ , wobei $\epsilon$ Ihre gewünschte Fehlermarge ist. Das Paper stellt fest, dass diese Potenz von der „Glätte“ der Regel abhängt, die Sie zu lernen versuchen ( $k$ ), und der Größe des Graphen ( $N$ ). Im Wesentlichen gilt: Für sehr komplexe, zackige Regeln oder sehr große Graphen benötigen Sie viel mehr Verbindungen, aber für glatte Regeln bleibt die KI effizient.

Der „Durchschnitt“-Trick für die Sicherheit

Einer der spielerischsten und praktischsten Erkenntnisse des Papers befasst sich mit einem Nebeneffekt der Verwendung von zufälligen Aufklebern. Da die Aufkleber zufällig sind, kann es sein, dass die KI bei einem Durchlauf ein etwas anderes Ergebnis liefert als bei einem anderen, wenn man sie mit anderen Aufklebern füttert. Dies bricht die Symmetrieregel: Die KI behandelt dieselbe Gruppe von Freunden möglicherweise unterschiedlich, nur weil sich die Aufkleber geändert haben.

Die Autoren schlagen eine kluge Lösung vor: das Mittelbildungsverfahren (Averaging). Wenn man die KI viele Male mit verschiedenen zufälligen Aufklebern laufen lässt und das Ergebnis mittelt, hebt sich die Zufälligkeit auf, und die KI wird wieder perfekt symmetrisch. Sie haben bewiesen, dass diese „gemittelte“ Version immer noch die Superkraft besitzt, jede Regel lernen zu können. Es ist, als würde man eine Menge von Menschen bitten, das Gewicht eines Kürbisses zu schätzen; eine Person mag weit daneben liegen, aber wenn man den Durchschnitt der Schätzungen von hundert Menschen nimmt, erhält man ein sehr genaues Ergebnis. Das Paper zeigt, dass man diese perfekte Symmetrie und die perfekte Lernfähigkeit gleichzeitig erreichen kann, indem man einfach einige Durchläufe mittelt.

Was dies für die Zukunft bedeutet

Die Autoren stellen vorsichtig klar, dass dies ein theoretischer Beweis ist und keine Simulation eines spezifischen Datensatzes. Sie haben mathematisch demonstriert, dass das Potenzial besteht, dass diese Modelle universelle Approximatoren sind. Sie schließen explizit die Idee aus, dass man komplexe, maßgeschneiderte Architekturen benötigt, um dies zu erreichen; die Standard-PENN-Struktur ist, wenn sie mit zufälligen Merkmalen ergänzt wird, ausreichend.

Sie stellen auch klar, dass zufällige Merkmale zwar die „perfekte Symmetrie“ eines einzelnen Durchlaufs brechen, aber nicht die „Symmetrie in der Erwartung“ (das durchschnittliche Verhalten). Dies deutet darauf hin, dass die Verwendung von zufälligen Merkmalen in der Praxis eine robuste Strategie ist. Das Paper kommt zu dem Schluss, dass PENNs mit zufälligen Merkmalen als starker Baseline-Ansatz für das Graph-Learning betrachtet werden sollten. Sie sind nicht nur eine theoretische Kuriosität; sie bieten einen konkreten, mathematisch fundierten Bauplan für die Entwicklung von Graph-KIs, die sowohl leistungsfähig als auch flexibel sind und in der Lage sind, komplexe Muster in Netzwerken zu lernen – von chemischen Molekülen bis hin zu Finanzsystemen.

Technisches Resümee: Universalität und Approximationsraten von Graph Neural Networks mit Zufallsmerkmalen

Problemstellung

Graph Neural Networks (GNNs), insbesondere Message-Passing-Architekturen, haben beachtliche empirische Erfolge erzielt, stehen jedoch vor theoretischen Einschränkungen hinsichtlich ihrer Ausdrucksstärke. Standardmäßige Message-Passing-GNNs sind durch den 1-Weisfeiler–Leman-Test (1-WL) begrenzt, was bedeutet, dass sie bestimmte nicht-isomorphe Graphstrukturen nicht unterscheiden können. Während Strategien existieren, um dies zu überwinden – etwa durch höherwertige Architekturen oder die Anreicherung von Knotenmerkmalen – mangelt es an fundierten theoretischen Ergebnissen, die die universelle Approximationsfähigkeit spezifischer, praktischer GNN-Architekturen bei der Verwendung von Zufallsmerkmalen (Random Features) etablieren. Zudem stützen sich bestehende Universalitätsresultate oft auf restriktive Annahmen, wie die Forderung, dass Zielfunktionen kontinuierlich sein müssen, Domänen kompakt sein müssen oder Merkmale endlichdimensional sein müssen, und versäumen es häufig, Approximationsraten (Komplexitätsschranken) für diese Modelle zu adressieren.

Methodik

Die Autoren untersuchen Permutations-Äquivariante Neuronale Netze (Permutation-Equivariant Neural Networks, PENNs), eine Klasse von GNNs, die viele populäre Message-Passing-Architekturen (z. B. GCN, GIN, GraphSAGE, GAT) generalisiert. Die zentrale methodische Innovation ist die Augmentierung von Standard-Knotenmerkmalen mit zufälligen Knotenmerkmalen.

Architekturdefinition: Das Paper definiert PENNs als Funktionen, die aus Feedforward-Neural-Network-Komponenten ( $\rho, \phi, \alpha, \psi$ ) bestehen, welche Informationen aus Nachbarschaften und globalen Graphattributen aggregieren. Diese Struktur subsumiert das Aggregate-Combine-Readout (ACR)-Framework.
Zufallsmerkmale: Die Autoren führen zufällige Knotenmerkmale $R$ ein, die „endliche eindeutige Knotenmerkmale“ bereitstellen. Dies bedeutet, dass die Zufallsmerkmale mit hoher Wahrscheinlichkeit (oder fast sicher) distinkten Knoten distinkte Identifikatoren zuweisen und somit die Symmetrie aufbrechen, die Standard-GNNs einschränkt. Das Framework unterstützt sowohl unabhängige und identisch verteilte (i.i.d.) Zufallsmerkmale als auch deterministische eindeutige Identifikatoren (oder deren zufällige Permutationen).
Approximations-Framework: Die Studie nutzt klassische universelle Approximations-Theoreme für FNNs (z. B. Leshno et al., 1993), passt diese jedoch an den Graph-Kontext an. Die entscheidende Erkenntnis ist: Wenn Knotenmerkmale eindeutig sind, kann jede permutations-äquivariante Funktion als Komposition von FNNs dargestellt werden, die auf diesen eindeutigen Merkmalen operieren.
Erwartungswert-basierte Äquivarianz: In Anerkennung dessen, dass die pfadweise Permutations-Äquivarianz durch feste Zufallsmerkmale gebrochen wird, analysieren die Autoren die Permutations-Äquivarianz im Erwartungswert. Sie schlagen vor, PENNs über mehrere neu gesampelte Zufallsmerkmale zu mitteln, um die Äquivarianz-Eigenschaften wiederherzustellen und gleichzeitig eine hohe Ausdrucksstärke zu behalten.

Zentrale Beiträge

1. Universelle Approximations-Theoreme

Das Paper stellt fest, dass PENNs, die mit Zufallsmerkmalen augmentiert sind, universelle Approximatoren für messbare permutations-invariante und permutations-äquivariante Funktionen auf gerichteten Graphen mit fester Größe und mehrdimensionalen Knoten-/Kantenmerkmalen sind.

Generalität: Im Gegensatz zu vorangegangenen Arbeiten (z. B. Abboud et al., 2020; Puny et al., 2020) erfordert dieses Resultat weder die Stetigkeit der Zielfunktion noch setzt es Kompaktheit oder die Endlichkeit des Merkmalsraums voraus. Es ist auf messbare Funktionen auf unbeschränkten Domänen anwendbar.
Konkrete Architektur: Die Autoren spezifizieren eine konkrete Architektur (PENNs), für die die Universalität gilt, anstatt lediglich die Existenz einer abstrakten Architektur zu behaupten.
Wahrscheinlichkeit: Die Approximation gilt mit beliebig hoher Wahrscheinlichkeit, sofern die Zufallsmerkmale eindeutige Knotenidentifikatoren induzieren.

2. Approximationsraten und Komplexitätsschranken

Für $k$ -mal stetig differenzierbare Funktionen ( $k \ge 2$ ), die auf kompakten Domänen definiert sind, leitet das Paper explizite obere Schranken für die Komplexität der PENN-Komponenten ab, die erforderlich sind, um einen gewünschten Approximationsfehler $\varepsilon$ zu erreichen.

Tiefe: Die erforderliche Anzahl an Schichten wächst logarithmisch bezüglich $1/\varepsilon$ ( $O(\log(1/\varepsilon))$ ).
Breite/Gewichte: Die Anzahl der Nicht-Null-Gewichte wächst polynomiell bezüglich $1/\varepsilon$ , spezifisch als $O(\varepsilon^{-c/(k-1)})$ , wobei $c$ von den Graph-Dimensionen ( $N, d, d'$ ) abhängt.
Fluch der Dimensionalität: Die Schranken spiegeln eine Form des Fluchs der Dimensionalität hinsichtlich des Graph-Domains wider, wobei die Schwere für Funktionen mit höherer Regularität ( $k$ ) gemildert wird.

3. Permutations-Äquivarianz im Erwartungswert

Das Paper adressiert den Trade-off zwischen Ausdrucksstärke und Symmetrie. Während eine einzelne Realisierung eines PENN mit Zufallsmerkmalen nicht pfadweise permutations-äquivariant ist, beweisen die Autoren, dass der Erwartungswert des PENN-Outputs (bedingt auf den Graph-Input) permutations-äquivarient ist. Des Weiteren zeigen sie, dass das Mitteln über eine endliche Anzahl i.i.d. Zufallsmerkmal-Samples die universelle Approximationsfähigkeit bewahrt und gleichzeitig den Bias in Richtung Äquivarianz verbessert.

Ergebnisse

Theorem 9: Stellt fest, dass für jede messbare permutations-äquivariante Funktion $f$ und jedes $\varepsilon, \delta > 0$ ein PENN mit Zufallsmerkmalen existiert, sodass die Wahrscheinlichkeit, dass der Approximationsfehler $\varepsilon$ übersteigt, höchstens $\delta$ beträgt.
Theorem 11: Liefert eine maßtheoretische Version des Universalitätsresultats, die anwendbar ist, wenn die Graph-Verteilung selbst eindeutige Knotenmerkmale induziert.
Theorem 16: Demonstriert, dass der gemittelte PENN (unter Verwendung von $M$ i.i.d. Kopien von Zufallsmerkmalen) ebenfalls die universelle Approximationsfähigkeit erfüllt, wobei die Fehlerwahrscheinlichkeit durch $\delta$ begrenzt ist.
Theorem 18: Liefert die quantitativen Approximationsraten. Es beweist, dass für hinreichend reguläre Funktionen PENNs mit spezifischen architektonischen Constraints (Tiefe und Breite) die Zielfunktion mit hoher Wahrscheinlichkeit uniform approximieren können. Die Komplexitätsschranken spiegeln jene bekanntermaßen für Standard-Feedforward-Neuronale-Netze wider.

Bedeutung und Ansprüche

Die Autoren behaupten, dass diese Arbeit wesentliche Lücken im theoretischen Verständnis von GNNs schließt:

Überbrückung von Theorie und Praxis: Durch den Beweis der Universalität für eine konkrete, speichereffiziente Architektur (PENNs) statt für abstrakte Modelle, liefern die Ergebnisse eine theoretische Grundlage für die Verwendung von Zufallsmerkmalen in praktischen GNN-Anwendungen.
Generalisierung bestehender Resultate: Die Ergebnisse generalisieren bisherige Universalitäts-Theoreme, indem sie Annahmen über Stetigkeit, Kompaktheit und die Natur der Zielfunktionen lockern (messbar vs. stetig).
Praktische Orientierung: Die abgeleiteten Approximationsraten bieten eine theoretische Orientierungshilfe bei der Auswahl von Hyperparametern (Tiefe und Breite) basierend auf der gewünschten Genauigkeit und der Regularität der Zielfunktion.
Benchmarking: Die Autoren legen nahe, dass PENNs mit Zufallsmerkmalen als starke Baselines für Graph-Learning-Aufgaben betrachtet werden sollten, sei es als kompetitive Alternativen zu State-of-the-Art-Modellen oder als Referenzpunkt zur Validierung der Fähigkeiten anderer Architekturen.

Das Paper schließt mit dem Schluss, dass Zufallsmerkmale zwar einen Verlust der pfadweisen Äquivarianz mit sich bringen können, die resultierenden Modelle jedoch eine überlegene Ausdrucksstärke besitzen und bei Mittelung die wünschenswerten Symmetrieeigenschaften beibehalten, was sie zu einem robusten theoretischen und praktischen Werkzeug für das Graph-Learning macht.