Wenn Graph Neural Networks auf die Riemannsche Vermutung treffen: Eine systematische negative Studie

Abstract

Graph Neural Networks (GNNs) haben bemerkenswerte Erfolge bei Graph-Vorhersageaufgaben in der Chemie, in sozialen Netzwerken und in der kombinatorischen Optimierung erzielt. Aber was passiert, wenn man ein GNN auf eines der tiefsten offenen Probleme der Mathematik ansetzt? Wir haben sieben systematische Experimentierreihen durchgeführt, um zu testen, ob GNNs spektrale Eigenschaften algebraischer Graphen vorhersagen können, deren Eigenwerte über eine Kette bekannter Theoreme mit der Riemannschen Zeta-Funktion und letztlich mit der Riemannschen Hypothese verbunden sind.

Die Antwort ist ein definitives Nein. Über Subgraph- und Full-Graph-Architekturen, Cayley-Graphen, Farey-Graphen und Pizer-Graphen sowie über die Vorhersage der Spektrallücke (spectral gap) und Hecke-Eigenwerte hinweg scheiterte jede GNN-Konfiguration entweder komplett oder lieferte nur marginale Verbesserungen gegenüber einer trivialen logarithmischen Baseline. Das beste Ergebnis über alle Experimente hinweg war ein $\Delta R^2$ von +0,042 gegenüber einer linearen Regression. Wir führen dieses Scheitern auf eine einzige theoretische Ursache zurück: die Vertex-Transitivität. Diese strukturelle Eigenschaft, die Cayley-Graphen eigen ist, lässt jeden Knoten für ein Message-Passing-GNN identisch erscheinen, wodurch die lokale strukturelle Diversität zerstört wird, auf die diese Netzwerke angewiesen sind. Wir formalisieren dies über die Weisfeiler-Leman-Hierarchie und beweisen, dass Standard-Message-Passing-GNNs auf vertex-transitiven Graphen auf Funktionen des Durchmessers und des Grades beschränkt sind.

Nach unserem Kenntnisstand gibt es keine veröffentlichten Arbeiten, die GNNs auf zahlentheoretische Graphstrukturen angewendet haben. Diese Experimente stellen die erste systematische Untersuchung an dieser Schnittstelle dar und setzen klare, harte Grenzen.

---

Einführung: Warum GNNs und Zahlentheorie?

Die Motivation hinter dieser Studie beginnt mit einer verlockenden Kette mathematischer Verbindungen. Betrachten wir einen 4-regulären Graphen, der aus der Gruppe $\text{SL}(2, \mathbb{F}_p)$ aufgebaut ist – der Gruppe der $2\times2$-Matrizen mit Determinante 1 über dem endlichen Körper mit $p$ Elementen. Die Eigenwerte der Adjazenzmatrix dieses Graphen kodieren Expansions-Eigenschaften. Durch die Lubotzky-Phillips-Sarnak-Konstruktion [LPS, 1988] und Pizers Theorem [Pizer, 1990] fallen diese Eigenwerte mit den Hecke-Eigenwerten modularer Formen zusammen. Diese Eigenwerte wiederum steuern das analytische Verhalten von L-Funktionen. Und L-Funktionen verbinden sich über gut untersuchte Mechanismen mit den Nullstellen der Riemannschen Zeta-Funktion $\zeta(s)$.

Die Kette sieht wie folgt aus:

Graph-Eigenwerte $\rightarrow$ Hecke-Eigenwerte $\rightarrow$ L-Funktionen $\rightarrow \zeta(s)$

Wenn ein Machine-Learning-Modell die spektralen Eigenschaften dieser Graphen allein aus ihrer Struktur vorhersagen könnte, würde dies einen computergestützten Pfad in ein Gebiet eröffnen, das Mathematiker seit über einem Jahrhundert mit rein symbolischen Methoden erforschen. Graph Neural Networks scheinen das natürliche Werkzeug für diese Aufgabe zu sein. Sie sind exzellent darin, Beziehungen zwischen lokaler Graphstruktur und globalen Eigenschaften zu erlernen. Vorhersage molekularer Eigenschaften, Analyse sozialer Netzwerke, kombinatorische Optimierung: GNNs dominieren diese Bereiche, indem sie Informationen aus lokalen Nachbarschaften aggregieren.

Wir haben uns entschieden zu testen, ob dieses Versprechen auch auf algebraische Graphen mit Bezug zur Zahlentheorie übertragbar ist. Die Antwort, wie sich herausstellt, verrät mehr über die Grenzen von GNNs als über die Riemannsche Hypothese.

---

Mathematischer Hintergrund

Dieser Abschnitt führt die wichtigsten mathematischen Objekte auf einem Niveau ein, das für ML-Forscher zugänglich ist. Es werden keine Vorkenntnisse in Zahlentheorie vorausgesetzt.

Cayley-Graphen von $\text{SL}(2, \mathbb{F}_p)$

Ein Cayley-Graph wird aus einer Gruppe und einer Erzeugend konstruiert. Man platziert jedes Gruppenelement an einem Knoten und verbindet zwei Knoten mit einer Kante, wann immer einer vom anderen durch Multiplikation mit einem Erzeuger erreicht werden kann. Der resultierende Graph erbt strukturelle Eigenschaften der Gruppe.

Wir untersuchen Cayley-Graphen von $\text{SL}(2, \mathbb{F}_p)$, welche $p(p^2 - 1)$ Elemente besitzen. Unter Verwendung von Standard-Erzeugern (den sogenannten fundamentalen Wurzeln und deren Inversen) sind die resultierenden Graphen 4-regulär. Für $p = 2$ hat der Graph nur 6 Knoten. Für hat er über eine Million.

Diese Graphen besitzen eine entscheidende Eigenschaft namens Vertex-Transitivität: jeder Knoten sieht exakt so aus wie jeder andere Knoten. Man kann jeden Knoten durch eine Symmetrie des Graphen (speziell durch Links-Multiplikation in der Gruppe) auf jeden anderen abbilden. Das bedeutet, dass die lokale Nachbarschaft um jeden Knoten strukturell identisch ist. Jeder Knoten hat den Grad 4, denselben Clustering-Koeffizienten und dieselbe lokale Topologie.

Spektrallücke und Ramanujan-Graphen

Die Spektrallücke (spectral gap) eines Graphen ist die Differenz zwischen seinen zwei größten Eigenwerten. Intuitiv misst sie, wie gut vernetzt und "expandierend" der Graph ist. Eine große Spektrallücke bedeutet, dass Random Walks schnell mischen und Informationen effizient verbreitet werden.

Ein Ramanujan-Graph ist ein Graph, dessen nicht-triviale Eigenwerte durch $2\sqrt{d-1}$ beschränkt sind, wobei $d$ der Grad ist. Für unsere 4-regulären Graphen liegt diese Grenze bei etwa 3,464. Alle Cayley-Graphen in unserem Datensatz erfüllen diese Bedingung. Die Ramanujan-Eigenschaft ist signifikant, da sie die Graphentheorie mit tiefen Ergebnissen der Zahlentheorie verbindet: Die Beschränkung der Graph-Eigenwerte spiegelt Delignes Beschränkung für Hecke-Eigenwerte modularer Formen wider [Deligne, 1974], und beide sind Manifestationen derselben zugrunde liegenden algebraischen Struktur.

Hecke-Eigenwerte und L-Funktionen

Hecke-Eigenwerte sind Zahlen, die modularen Formen zugeordnet sind – speziellen Funktionen mit tiefen Symmetrieeigenschaften. Für Cusp-Formen des Gewichts 2 und der Stufe $p$, bezeichnet als $S_2(\Gamma_0(p))$, besitzt jede Form eine Sequenz von Hecke-Eigenwerten $a_2, a_3, a_5, \dots$, die arithmetische Informationen über die Primzahl kodieren. Die Dimension des Raums der Cusp-Formen (und damit die Anzahl der verschiedenen Eigenwertsequenzen) hängt auf eine nicht-triviale Weise von ab, die mit der Faktorisierung von und anderen arithmetischen Eigenschaften zusammenhängt.

L-Funktionen sind Dirichlet-Reihen, die aus Hecke-Eigenwerten aufgebaut werden. Ihre analytischen Eigenschaften, insbesondere die Lage ihrer Nullstellen, stehen in direktem Zusammenhang mit der Riemannschen Zeta-Funktion. Die Verallgemeinerte Riemannsche Hypothese besagt, dass alle nicht-trivialen Nullstellen jeder L-Funktion auf der kritischen Geraden $\text{Re}(s) = 1/2$ liegen.

Die Pizer-Graph-Konstruktion

Der Pizer-Graph für eine Primzahl $p$ ist eine besonders präzise Brücke zwischen Graphentheorie und Zahlentheorie. Seine Adjazenzmatrix ist exakt der Hecke-Operator $T_2$, der auf dem Raum der Cusp-Formen $S_2(\Gamma_0(p))$ wirkt. Die Kantengewichte werden durch die Arithmetik der Kongruenzuntergruppe bestimmt. Wenn irgendeine Graphkonstruktion eine Verbindung zwischen Graphstruktur und Hecke-Eigenwerten für einen Lernalgorithmus sichtbar machen sollte, dann ist es diese.

Der Farey-Graph

Der Farey-Graph ist eine andere Art von mathematischem Objekt. Endliche Trunkierungen $F_n$ enthalten Brüche mit Nennern bis $n$, die verbunden sind, wenn $|ad - bc| = 1$. Im Gegensatz zu Cayley-Graphen sind Farey-Graphen nicht vertex-transitiv: die Knotengrade reichen von 2 bis $n$. Diese strukturelle Diversität macht sie zu einer wichtigen Kontrollgruppe: Wenn GNNs auch bei Farey-Graphen scheitern, liegt das Problem nicht nur an der Vertex-Transitivität.

Der Weisfeiler-Leman-Test und die Expressivität von GNNs

Der Weisfeiler-Leman (WL)-Test ist ein Algorithmus, der Graphknoten Farben zuweist, indem er diese Farben iterativ basierend auf der lokalen Nachbarschaftsstruktur jedes Knotens verfeinert. Er ist das Standardwerkzeug zur Analyse der Leistungsfähigkeit von GNNs. Ein zentrales theoretisches Ergebnis: Message-Passing-GNNs sind bei der Unterscheidung nicht-isomorpher Graphen höchstens so leistungsfähig wie der 1-WL-Test [Xu et al., 2019].

Auf vertex-transitiven Graphen weist 1-WL in jeder Iteration jedem Knoten dieselbe Farbe zu. Die initiale Färbung ist uniform (alle Knoten haben Grad 4), und der Verfeinerungsschritt bewahrt diese Uniformität, da jeder Knoten dasselbe Multiset an Nachbarfarben sieht. Das bedeutet, dass ein Message-Passing-GNN an jedem Knoten dasselbe Embedding erzeugt.

---

Methodik

Die sieben Experimentierreihen

Wir haben die Untersuchung in sieben progressive Experimentierreihen unterteilt, von denen jede eine andere Hypothese darüber testet, ob GNNs zahlentheoretische Eigenschaften aus der Graphstruktur lernen können.

Track 1: Subgraph-basierte GNN-Architekturen. Extraktion lokaler Subgraphen aus Cayley-Graphen und Training von fünf verschiedenen Architekturen (GAT, SIGN, Stratified, Multi-Task, hierarchisches ChebConv), um die Spektrallücke des gesamten Graphen vorherzusagen. Hypothese: Die lokale Struktur kodiert globale spektrale Informationen.

Track 2: Full-Graph spektrale Konvolution. Verarbeitung vollständiger Cayley-Graphen unter Verwendung von Chebyshev-Polynom-Features, die auf dem normierten Laplacian berechnet wurden, ergänzt durch Random Positional Encoding. Hypothese: Globale spektrale Features in Kombination mit Positionsinformationen können Variationen der Spektrallücke erfassen.

Track 3: Spektrallücke von Farey-Graphen. Anwendung derselben Full-Graph-Architektur auf Farey-Graphen, die nicht vertex-transitiv sind und eine reiche lokale strukturelle Diversität aufweisen. Hypothese: Strukturelle Diversität ermöglicht das Lernen durch GNNs.

Track 4: Hecke-Eigenwerte mit einem Erzeuger. Vorhersage von Hecke-Eigenwerten von Cusp-Formen des Gewichts 2 aus Cayley-Graphen mit einem einzigen Erzeuger. Dies testet direkt die Pizer/LPS-Brücke. Hypothese: Die Graphstruktur kodiert arithmetische Informationen.

Track 5: Hecke-Eigenwerte mit mehreren Erzeugern. Ergänzung durch mehrere Erzeugermengen pro Primzahl, um die Datensatzgröße zu erhöhen. Hypothese: Mehr Daten ermöglichen eine Generalisierung über verschiedene Primzahlen hinweg.

Track 6: Spektrallücke mit mehreren Erzeugern. Ein Kontrollexperiment, bei dem die Spektrallücke des jeweiligen Graphen (die je nach Erzeugermenge variiert) das Ziel ist. Hypothese: Das GNN kann zumindest Erzeugermengen voneinander unterscheiden.

Track 7: Pizer-Graphen. Vorhersage von Hecke-Eigenwerten über verschiedene Stufen hinweg ($T_3$-Eigenwerte aus $T_2$-konstruierten Graphen). Dies ist die mathematisch sauberste Konstruktion. Hypothese: Die exakte Korrespondenz zwischen Graphstruktur und Hecke-Operatoren ermöglicht das Lernen.

Datensätze

Cayley-Graphen von $\text{SL}(2, \mathbb{F}_p)$. Generiert für 26 Primzahlen ($p = 2, 3, 5, \dots, 101$) unter Verwendung von Standard-Erzeugern aus den fundamentalen Wurzeln der Lie-Algebra $\mathfrak{s}\mathfrak{l}$. Alle Graphen sind 4-regulär und vertex-transitiv. Die Größen reichen von 6 Knoten () bis zu 1.010.100 Knoten (). Eigenwerte wurden mittels spärlicher Lanczos-Iteration für 22 Primzahlen berechnet, wobei 18 vollständige spektrale Daten aufweisen (). Für die Multi-Generator-Experimente werden etwa 10 Erzeugermengen pro Primzahl verwendet (fundamentale Wurzeln, Root-Weyl und 8 zufällige Erzeugermengen), was etwa 130 Graphen über 13 Primzahlen ergibt.

Farey-Graphen. Endliche Trunkierungen $F_n$, konstruiert via Stern-Brocot Breitensuche für $n = 10, 20, \dots, 230$ (23 Graphen). Diese sind nicht vertex-transitiv: die Knotengrade reichen von 2 bis $n$, wobei der durchschnittliche Grad gegen 4,0 konvergiert. Die Größen reichen von 33 bis 16.155 Knoten.

Hecke-Eigenwerte. Berechnet mit SageMath für 13 Primzahlen ($p = 11, 17, \dots, 61$). Primzahlen mit trivialen Cusp-Form-Räumen wurden ausgeschlossen. Der Datensatz enthält 13 Datenpunkte, mit 1 bis 5 Eigenformen pro Primzahl, abhängig von der Dimension von $S_2(\Gamma_0(p))$.

Pizer-Graphen. 81 gewichtete Graphen für Primzahlen von 47 bis 499, mit Dimensionen des Cusp-Form-Raums zwischen 4 und 41. Die Adjazenzmatrix jedes Pizer-Graphen kodiert den Hecke-Operator $T_2$. Das Vorhersageziel besteht aus 9 zusammenfassenden Statistiken (Mittelwert, Standardabweichung, Min, Max, Median, Q25, Q75, Radius, pos_frac) der $T_3$-Hecke-Eigenwertverteilung.

Architekturen

Wir haben sechs verschiedene GNN-Architekturen über die Tracks hinweg getestet:

• GAT (Graph Attention Network): 3-lagiges, auf Attention basierendes Message Passing mit einer Hidden-Dimension von 128 und globalem Mean-Pooling [Veličković et al., 2018]. Attention-Mechanismen erlauben es dem Modell, Beiträge von Nachbarn unterschiedlich zu gewichten, was prinzipiell helfen könnte, wenn Nachbarn unterschiedliche Informationen trügen. Auf vertex-transitiven Graphen tun sie das nicht.

• SIGN (Scalable Inception GNN): Vorberechnete 2-Hop-Aggregation mit MLP-Mapping ($9 \rightarrow 128 \rightarrow 1$ Dimensionen), wodurch iteratives Message Passing vollständig vermieden wird [Rossi et al., 2020]. Diese Architektur ist auf Skalierbarkeit bei großen Graphen ausgelegt. Sie funktioniert gut bei sozialen Netzwerken, erbt aber dieselbe Einschränkung der Vertex-Transitivität.

• Stratified GAT: GAT mit BinBalancedBatchSampler, um eine gleichmäßige Repräsentation der Spektrallücken-Bereiche in jedem Trainings-Batch zu gewährleisten. Die Motivation ist, dass Spektrallücken über Primzahlen hinweg nicht gleichmäßig verteilt sind, sodass naives Sampling bestimmte Bereiche überrepräsentiert.

• Multi-Task GIN: Graph Isomorphism Network Encoder mit 5 Task-Heads und Uncertainty Weighting [Kendall et al., 2018]. Die fünf Aufgaben sind Spektrallücke, algebraische Konnektivität, Schätzung des Durchmessers, Girth und Clustering-Koeffizient. Multi-Task-Learning könnte helfen, wenn Hilfsaufgaben eine Struktur mit dem primären Ziel teilen.

• ChebConv hierarchisch: 3-lagige Chebyshev-Konvolution mit Multi-Scale Readout [Defferrard et al., 2016]. Chebyshev-Filter operieren im spektralen Bereich und berechnen polynomielle Approximationen von Graphfiltern. Mit $K = 3$ aggregiert jede Schicht Informationen aus 3-Hop-Nachbarschaften.

Random Positional Encoding

Auf vertex-transitiven Graphen erzeugen Mean-Pool- und Max-Pool-Operationen über identischen Knotenmerkmalen für jeden Graphen identische Vektoren, unabhängig von der Primzahl. Random Positional Encoding (RPE) löst dies, indem jedem Knoten ein zufälliger 8-dimensionaler Vektor zugewiesen wird, der einmal zu Beginn jedes Trainingslaufs gezogen wird. Die Vektoren bleiben für die Dauer dieses Laufs fixiert. Dies bricht die Symmetrie auf Feature-Ebene und ermöglicht es Pooling-Operationen, nicht-degenerierte Repräsentationen zu erzeugen. Die Vektoren enthalten keine strukturellen oder arithmetischen Informationen; sie dienen lediglich als eindeutige Identifikatoren, die es dem GNN ermöglichen, Knoten zu differenzieren. Das GNN muss dann lernen, aggregierte Muster dieser Identifikatoren mit Zielwerten zu assoziieren.

Evaluationsprotokoll

Für Experimente zum spektralen Gap von Cayley-Graphen verwenden wir eine Leave-One-Out-Kreuzvalidierung (LOO-CV) über alle Graphen mit berechneten Eigenwerten. Jedes der 18 Folds trainiert auf 17 Graphen und testet an einem, um eine echte Generalisierung über verschiedene Primzahlen hinweg (cross-prime) zu simulieren. Für Farey-Graph-Experimente verwenden wir einen Standard-Split ($n \le 120$ Training, $n > 120$ Test). Für Hecke-Eigenwert-Experimente erfolgt der Split bei $p \le 37$ Training, $p \ge 41$ Test. Für Pizer-Graphen testen wir sowohl LOO-CV (81 Folds, cross-prime) als auch zufällige 80/20-Splits (within-distribution). Alle Experimente nutzen als primäre Metrik, ergänzt durch MAE und den relativen Fehler als sekundäre Metriken.

Jedes Experiment beinhaltet eine lineare Regressions-Baseline, die nur skalare Graph-Features (Knotenanzahl, Kantenanzahl, Dimension) ohne jegliche strukturelle Informationen verwendet. Die Baseline für Cayley-Graphen ist $\text{spectral gap} \approx \alpha \cdot \log(N) + \beta$, was den dominanten logarithmischen Abfalltrend erfasst. Wenn die Baseline das GNN schlägt, liefert die Graphstruktur keinen Mehrwert gegenüber einem einfachen Maß für die Größe.

---

Ergebnisse

Zusammenfassungstabelle

Track	Graphfamilie	Ziel	Datenpunkte	GNN $R^2$	Baseline $R^2$	Urteil
1	Cayley SL(2, $\mathbb{F}_p$), Subgraph	Spectral gap	599 train	< 0 (alle 5 Arch)

Fünf von sieben Tracks scheitern komplett. Der sechste liefert eine marginale Verbesserung. Der siebte produziert das frappierendste negative Ergebnis: eine exakte Null-Generalisierung über Primzahlen hinweg, trotz einer mathematisch exakten Verbindung zwischen Graphstruktur und Zielwert.

Track 1: Subgraph-GNNs kollabieren beim Cross-Prime-Test

Alle fünf Architekturen erreichen eine nahezu identische Trainingsleistung ($R^2 \approx 0.69$), was zeigt, dass GNNs aus der lokalen Struktur innerhalb einer Trainingsverteilung lernen können. Doch jedes Modell kollabiert katastrophal bei Cross-Prime-Testdaten:

Modell	Architektur	Train $R^2$	Test $R^2$
GAT Baseline	3-layer GAT, h=128	0.69	-122
SIGN	Precomputed 2-hop agg.	0.69	-80
Stratified	Balanced batch + GAT	0.69	-111
Multi-Task	GIN + 5 heads	0.69	negativ
ChebConv Hier.	3-layer ChebConv, K=3	0.69	-44

Ein Test-$R^2$ von -122 bedeutet, dass die Vorhersagen des Modells weitaus schlechter sind als die einfache Vorhersage des Mittelwerts. Das GNN memorisiert die spektralen Gaps der Trainings-Primzahlen und kann nicht generalisieren, da jeder Subgraph, unabhängig von der zugrunde liegenden Primzahl, strukturell identisch aussieht. Die Vertex-Transitivität macht die lokale Struktur aussagelos in Bezug auf die globalen spektralen Eigenschaften.

Track 2: Das beste Ergebnis und warum es nicht ausreicht

Das Full-Graph ChebConv mit Random Positional Encoding erreicht $R^2 = 0.824$ in der LOO-CV, eine Verbesserung von $\Delta R^2 = +0.042$ gegenüber der logarithmischen Baseline ($R^2 = 0.782$). Dies ist der einzige Track, in dem ein GNN seine Baseline sinnvoll übertrifft. Die detaillierten LOO-CV-Ergebnisse:

p	Knoten	Vorhersage	Tatsächlich	Rel. Fehler
2	6	1.173	2.000	41.4%
3	24	1.053	1.268	16.9%
5	120	0.630	0.764	17.5%
7	336	0.553	0.586	5.6%
11	1,320	0.279	0.382	26.9%
13	2,184	0.367	0.325	12.8%
17	4,896	0.210	0.291	27.9%
19	6,840	0.201	0.245	18.0%
23	12,144	0.180	0.207	13.1%
29	24,360	0.184	0.182	0.9%
31	29,760	0.185	0.227	18.7%
37	50,616	0.171	0.171	0.3%
41	68,880	0.167	0.181	7.5%
43	79,464	0.169	0.166	1.7%

Bei großen Graphen ($p \ge 29$) sinkt der relative Fehler unter 6%, mit bemerkenswerter Genauigkeit bei $p = 37$ (0,3%). Kleine Graphen ($p \le 11$) zeigen höhere Fehler, da den Chebyshev-Features bei Graphen mit weniger als einigen tausend Knoten die ausreichende strukturelle Variation fehlt.

Doch die Verbesserung von $+0.042 \Delta R^2$ ist marginal. Die lineare Baseline, $\text{spectral gap} \approx -0.135 \cdot \log(N) + 1.618$, erfasst bereits den dominanten logarithmischen Abfall. Das GNN fügt nur eine winzige Menge nicht-logarithmischer Informationen hinzu. Der Erfolg hängt vom Zusammenspiel dreier Faktoren ab: Chebyshev-Features, die globale spektrale Informationen in knotenspezifische Repräsentationen kodieren; RPE, das die Vertex-Transitivität bricht, sodass Pooling-Operationen nicht-degenerierte Graph-Vektoren erzeugen; und das Regime großer Graphen, das genügend Diversität in den Chebyshev-Features bietet, um verschiedene Primzahlen zu unterscheiden. Fällt einer dieser Faktoren weg, kollabiert die Leistung auf das Baseline-Niveau.

Die marginale Verbesserung deutet darauf hin, dass der spektrale Gap dieser Cayley-Graphen gut durch eine logarithmische Funktion von $|V|$ approximiert werden kann, wobei nur eine geringe Reststruktur verbleibt, die das GNN erfasst. Dies steht im Einklang mit der theoretischen Erwartung aus der Darstellungstheorie: Der spektrale Gap von $\text{Cay}(\text{SL}(2, \mathbb{F}_p), S)$ wird durch die Darstellungstheorie von $\text{SL}(2, \mathbb{F}_p)$ bestimmt, die für große einem universellen Verhalten zustrebt, das durch arithmetische Fluktuationen moduliert wird, die zu subtil sind, als dass ein GNN sie extrahieren könnte.

Track 3: Farey-Graphen offenbaren einen anderen Fehlermodus

Farey-Graphen sind nicht vertex-transitiv. Die Knotengrade reichen von 2 bis $n$. Lokale strukturelle Diversität ist reichlich vorhanden. Dennoch erreicht das GNN $R^2 = -7.57$, während eine log-log lineare Regression $R^2 = 0.9999$ erreicht.

Der Grund: Der spektrale Gap von Farey-Graphen folgt einem nahezu perfekten Potenzgesetz, $\text{gap} \approx 2.65/n$. Dies ist so simpel, dass eine lineare Regression es trivial löst. Das GNN kann diese $1/n$-Skalierung nicht allein aus lokalen Features lernen und extrapoliert schlecht, da die Testgraphen wesentlich größer sind als die Trainingsgraphen.

Dieses Ergebnis ist wichtig, da es zeigt, dass Nicht-Vertex-Transitivität zwar notwendig, aber nicht ausreichend für den Erfolg von GNNs ist. Der Zielwert muss zudem von lokalen strukturellen Merkmalen abhängen und nicht nur von der Skalierung des Graphen.

Track 4: Hecke-Eigenwerte trotzen GNNs und Baselines

Mit nur 13 Datenpunkten (Primzahlen, bei denen der Cusp-Form-Raum nicht-trivial ist) erreicht das GNN $R^2 = -0.21$ bei der Vorhersage des mittleren Hecke-Eigenwerts. Die lineare Baseline schafft $R^2 = 0.41$, was schwach, aber immerhin positiv ist. Das negative GNN-Ergebnis zeigt, dass die Graphstruktur keinerlei nützliche Informationen über Hecke-Eigenwerte liefert.

Dies ist theoretisch zu erwarten: Hecke-Eigenwerte hängen von der tiefen Arithmetik der Primzahl ab (Galois-Konjugationsklassen, Dimension des Cusp-Form-Raums, Klassenzahlen), nicht von der kombinatorischen Struktur eines beliebigen Cayley-Graphen.

Track 5: Mehr Generatoren, gleiches Scheitern

Die Generierung von etwa 10 Generator-Sets pro Primzahl ergibt $\sim 130$ Graphen für 13 Primzahlen. Doch das Multi-Generator-GNN erreicht $R^2 = -0.32$, schlechter als im Experiment mit einem einzelnen Generator. Die Baseline, welche die Tatsache ausnutzt, dass Hecke-Eigenwerte nur von der Primzahl (nicht vom Generator-Set) abhängen, erreicht $R^2 = 0.977$.

Die Multi-Generator-Augmentierung schadet aktiv, da verschiedene Generator-Sets Graphen mit unterschiedlichen lokalen Zyklusmustern und Girth erzeugen, der Hecke-Zielwert jedoch für alle Graphen derselben Primzahl identisch ist. Das GNN overfittet auf generatorspezifische Merkmale, die für den Zielwert irrelevant sind.

Track 6: Sogar das Kontrollexperiment scheitert

Dieser Track stellt eine einfachere Frage: Kann das GNN den spektralen Gap des eigenen Graphen vorhersagen, welcher ja je nach Generator-Set variiert? Die Antwort lautet nein. $R^2 = -2.12$, verglichen mit einer Baseline von 0.43.

Das Scheitern ist besonders frappierend, da strukturierte Generatoren (Fundamentalwurzeln, Root-Weyl) Graphen mit spektralen Gaps von 0,1 bis 0,25 erzeugen (schlechte Expander), während Zufallsgeneratoren Gaps von 2,3 bis 2,6 erzeugen (gute Expander). Das GNN kann nicht einmal diese zwei Regime unterscheiden. Die Unterscheidung wird durch globale algebraische Eigenschaften bestimmt, die für lokales Message-Passing unsichtbar sind.

Track 7: Die Pizer-Graphen versetzen den entscheidenden Schlag

Die Konstruktion der Pizer-Graphen ist der mathematisch sauberste Test. Die Adjazenzmatrix ist der Hecke-Operator $T_2$. Der Zielwert ($T_3$-Eigenwerte) ist eine eng verwandte arithmetische Größe. Wenn irgendein Graph eine lernbare Verbindung zwischen Struktur und Hecke-Eigenwerten aufzeigen sollte, dann dieser.

LOO-CV-Ergebnisse über alle 9 Eigenwert-Statistiken:

Statistik	GNN $R^2$	Baseline $R^2$
mean	0.000	0.174
std	0.000	-0.003
min	0.000	0.074
max	0.000	0.072
median	0.000	0.309
Q25	0.000	-0.161
Q75	0.000	0.096
radius	0.000	0.072
pos_frac	0.000	-0.121
Gesamt	0.000	0.057

Das GNN $R^2$ ist über jede Statistik, jede Graphgrößen-Klasse und jeden einzelnen Fold hinweg *ex Bei einem zufälligen 80/20-Split anstelle von LOO-CV erreicht R² bei einigen Statistiken bis zu +0,52. Dies bestätigt, dass das GNN in der Lage ist, Within-Distribution-Muster zu lernen. Doch sobald eine zurückgehaltene Primzahl eine neuartige arithmetische Struktur einführt, kollabieren die Vorhersagen des Modells zu einer Konstante. Die Arithmetik jeder Primzahl (Faktorisierung von p±1, Klassenzahl, Dimension des Cusp-Form-Raums) erzeugt strukturelle Merkmale, die nicht glatt über Primzahlen hinweg interpolieren.

---

Analyse: Warum alles gescheitert ist

Der Information Bottleneck

Das konsistente Scheitern über alle sieben Tracks hinweg resultiert aus einer theoretischen Einschränkung, die wir wie folgt formalisieren:

Auf einem knotentransitiven Graphen erzeugt ein K-Layer Message-Passing GNN an jedem Knoten identische Embeddings. Ohne Positional Encoding reduziert sich die Repräsentation auf Graphenebene zu einer Funktion, die nur von Graphen-Statistiken abhängt (Knotenanzahl, Kantenanzahl, Dichte, geschätzter Durchmesser). Mit Random Positional Encoding unterscheiden sich die Knoten-Embeddings zwar, jedoch nur durch die injizierten Zufallsvektoren, die keine strukturellen Informationen tragen. Das GNN kann RPE als Schlüssel zur Differenzierung von Knoten nutzen, aber es kann daraus keine spektralen Eigenschaften extrahieren.

Dies hat eine unmittelbare Konsequenz: Bei einer Familie knotentransitiver Graphen, bei denen der Spectral Gap eine nicht-triviale Funktion der Primzahl ist (und nicht allein durch die Anzahl der Knoten bestimmt wird), kann ein Message-Passing GNN ohne RPE den Spectral Gap nicht besser vorhersagen als ein Modell, das nur die Knotenanzahl verwendet.

Knotentransitivität als Hauptursache

Cayley-Graphen von SL(2, Fₚ) sind konstruktionsbedingt knotentransitiv. Jeder Knoten hat den Grad 4, den gleichen Clustering-Koeffizienten und die gleiche lokale Topologie. Ein BFS-Subgraph sieht immer gleich aus, unabhängig davon, von welcher Primzahl er stammt. Die einzige unterscheidbare Information ist die Größe des Subgraphen, was nicht ausreicht, um den Spectral Gap zu rekonstruieren.

Das Experiment mit dem Farey-Graphen (Track 3) bestätigt, dass Knotentransitivität nicht das einzige Problem ist. Selbst bei struktureller Diversität scheitern GNNs, wenn das Ziel eine einfache Funktion der Graphskalierung ist. Aber bei Cayley-Graphen ist die Knotentransitivität der dominierende Fehlerfaktor.

Datenknappheit und die Generalization Gap

Die grundlegende Einschränkung des Datensatzes liegt nicht in der Anzahl der Graphen, sondern in der Natur des Problems. Jede Primzahl erzeugt einen strukturell einzigartigen Graphen, und es gibt kein glattes Interpolationsmuster zwischen den Primzahlen. Die Arithmetik von p = 43 (43 - 1 = 42 = 2 × 3 × 7) unterscheidet sich grundlegend von p = 47 (47 - 1 = 46 = 2 × 23) in einer Weise, die den Cusp-Form-Raum, die Hecke-Eigenwerte und die Struktur des Pizer-Graphen beeinflusst. Kein kontinuierlicher Lernalgorithmus kann diese Lücke schließen.

Selbst mit 130 Graphen (Tracks 5 und 6) oder 81 Pizer-Graphen (Track 7) verbessert sich die Performance nicht. Der Bottleneck ist nicht statistischer, sondern architektonischer Natur: Die Graph-Repräsentation kodiert nicht die arithmetischen Informationen, die für die Vorhersage benötigt werden.

Was Random Positional Encoding tatsächlich bewirkt

RPE bricht die Knotentransitivität auf Feature-Ebene auf, weshalb es für das Ergebnis in Track 2 essenziell ist. Aber RPE-Vektoren sind zufällig und tragen keine strukturellen oder arithmetischen Informationen. Die marginale Verbesserung des GNN gegenüber der linearen Baseline resultiert daraus, dass das Modell lernt, Muster in den RPE-modulierten Chebyshev-Features mit Spectral-Gap-Werten zu assoziieren. Da Chebyshev-Features globale spektrale Informationen kodieren (berechnet aus dem vollständigen Laplacian), lernt das GNN effektiv eine leicht nichtlineare Version der Beziehung zwischen Spectral Gap und log(N). Das ΔR² von +0,042 spiegelt die geringe Reststruktur jenseits dieses logarithmischen Trends wider.

---

Implikationen für KI und Mathematik

GNNs sind das falsche Werkzeug für die spektrale Vorhersage auf algebraischen Graphen

Die grundlegende Diskrepanz zwischen lokalem Message Passing und globalen spektralen Eigenschaften, verstärkt durch die Knotentransitivität, macht GNNs zu einer schlechten Wahl für diese Problemklasse. Symbolische Methoden aus der Darstellungstheorie und Charaktertheorie sind hier angemessener. Ein GNN kann keinen arithmetischen Inhalt aus einem Graphen extrahieren, in dem jeder Knoten gleich aussieht, ungeachtet der Anzahl der Layer oder Attention-Heads.

Diese Erkenntnis geht über SL(2, Fₚ) hinaus. Das gleiche Argument gilt für Cayley-Graphen symmetrischer Gruppen, Diedergruppen und jeder anderen Gruppe. Distanz-reguläre Graphen und stark reguläre Graphen unterliegen der gleichen Einschränkung. Jede knotentransitive Familie wird denselben Fehlermodus aufweisen.

Datenaugmentation kann ein Expressivitätsproblem nicht lösen

Die Multi-Generator-Augmentation (Tracks 5 und 6) erhöht die Datensatzgröße um den Faktor 10, verschlechtert jedoch aktiv die Performance. Das Ziel hängt von der Arithmetik der Primzahl ab, nicht von der lokalen Struktur des Graphen. Mehr Graphen mit demselben arithmetischen Ziel, aber unterschiedlichen kombinatorischen Strukturen, fügen lediglich Rauschen hinzu. Das GNN overfittet auf generator-set-spezifische Features, die für die Hecke-Eigenwerte irrelevant sind.

Dies liefert eine allgemeinere Lektion für ML-Praktiker: Wenn der Bottleneck die Expressivität und nicht die Datenmenge ist, hilft das Sammeln weiterer Daten nicht. Die Informationen, die das Modell benötigt, sind in der Input-Repräsentation schlichtweg nicht vorhanden.

Spektrale Methoden umgehen das Problem, lösen es aber nicht

Die Chebyshev-Vorberechnung (Track 2) greift auf globale spektrale Informationen zu und umgeht so den Message-Passing-Bottleneck. Die resultierende Verbesserung ist jedoch marginal. Das GNN kann den arithmetischen Gehalt des Spectral Gaps immer noch nicht extrahieren. Es erfasst lediglich triviale Nichtlinearitäten im log(N)-Trend.

Es ist anzumerken, dass eine Architektur, die die vollständige Eigenwertzerlegung der Adjazenzmatrix berechnet, das Problem der Spectral-Gap-Vorhersage trivial lösen würde: Man müsste einfach λ₂ ablesen. Eine solche Architektur ist jedoch in keinem sinnvollen Sinne ein GNN. Es handelt sich um eine Routine der numerischen linearen Algebra. Die Frage, die unsere Studie adressiert, ist, ob die inductive biases von GNNs (lokale Aggregation, Weight Sharing, Permutationsinvarianz) für dieses Problem nützlich sind. Das sind sie nicht.

Wann können GNNs für die spektrale Vorhersage funktionieren?

Unsere negativen Ergebnisse bedeuten nicht, dass GNNs universell schlecht in der spektralen Vorhersage sind. Sie sind erfolgreich, wenn:

1. Die Graphfamilie eine reiche lokale strukturelle Diversität aufweist. Nicht-knotentransitive Graphen mit heterogenen Gradverteilungen und Community-Strukturen liefern das induktive Signal, das GNNs benötigen.
2. Die spektrale Eigenschaft mit lokalen Features korreliert. Die HOMO-LUMO-Lücke in Molekülgraphen korreliert beispielsweise mit der Bindungsstruktur und funktionellen Gruppen.
3. Der Graph klein genug ist, damit Message Passing ihn abdecken kann. Typischerweise |V| < 10.000 bei ausreichend vielen Layern. Unsere größten Cayley-Graphen haben über eine Million Knoten.
4. Knoten semantische Features jenseits der Topologie tragen. In Molekülgraphen haben Atome chemische Eigenschaften. In unseren Cayley-Graphen ist jeder Knoten ein Matrixelement mit identischen strukturellen Merkmalen (Grad 4, gleicher Clustering-Koeffizient, gleiche lokale Topologie).

Die Vorhersage molekularer Eigenschaften erfüllt alle vier Bedingungen. Algebraische Graphen mit Bezug zur Zahlentheorie erfüllen keine einzige.

Komplexitätstheoretische Überlegungen

Barlag et al. (2024) zeigen, dass GNNs mit konstanter Tiefe genau die Funktionen berechnen, die durch arithmetische Schaltkreise konstanter Tiefe über den reellen Zahlen (FAC⁰_R) ausdrückbar sind. Die Riemannsche Zeta-Funktion erfordert jedoch beliebig tiefe arithmetische Berechnungen. Diese komplexitätstheoretische Perspektive bekräftigt unsere empirischen Ergebnisse: Das Rechenmodell hinter Standard-GNNs ist fundamental zu schwach für die beteiligten arithmetischen Strukturen.

Die übergeordnete Lektion für KI-gestützte mathematische Forschung

Die Begeisterung über KI in der Mathematik, von DeepMinds Arbeit an kombinatorischen Invarianten-Vermutungen [Davies et al., 2021] bis hin zu Large Language Models, die Wettbewerbstheoreme beweisen, ist gerechtfertigt. Unsere Ergebnisse zeigen jedoch eine Falle auf: Nicht jede mathematische Struktur ist für lernbasierte Ansätze zugänglich. Die spektralen Eigenschaften von Cayley-Graphen werden von tiefer Arithmetik (Darstellungstheorie, Modulformen, L-Funktionen) gesteuert, die für lokales Message Passing unsichtbar ist.

Fortschritte an dieser Schnittstelle werden entweder fundamental neue Architekturen erfordern, die algebraische Strukturen direkt aufnehmen können (symbolische Algebra-Layer, gruppen-äquivariante Architekturen, die die vollständige Gruppenstruktur anstelle von bloßer Permutationsinvarianz respektieren), oder Hybridansätze, die neuronale Netze mit symbolischem mathematischem Schließen kombinieren (Theorem-Prover, Computer-Algebra-Systeme, Bibliotheken der Darstellungstheorie).

Im weiteren Sinne ist unsere Arbeit eine Warnung vor der Anwendung von GNNs auf Graphfamilien mit geringer struktureller Diversität. Knotentransitivität ist in der algebraischen Kombinatorik weit verbreitet. Unsere Analyse bietet einen prinzipiellen Rahmen zur Beurteilung, wann GNNs funktionieren können und wann nicht: Prüfen Sie, ob die Zieleigenschaft in einer nicht-trivialen Weise von lokalen strukturellen Merkmalen abhängt und ob die Graphfamilie genügend lokale Diversität bietet, damit Message Passing informativ ist.

---

Fazit

Wir haben sieben systematische Experiment-Tracks durchgeführt, um zu testen, ob Graph Neural Networks spektrale Eigenschaften algebraischer Graphen mit Bezug zur Riemannschen Hypothese vorhersagen können. Der Umfang ist umfassend: fünf Subgraph-Architekturen, Full-Graph Spectral Convolution, drei verschiedene Graphfamilien (Cayley, Farey, Pizer) und zwei Zieltypen (Spectral Gap, Hecke-Eigenwerte). Jede Konfiguration scheiterte. Fünf Tracks produzierten ein negatives R². Einer ergab ein marginales ΔR² von +0,042 gegenüber einer logarithmischen Baseline. Das Experiment mit dem Pizer-Graphen – der mathematisch sauberste Test, bei dem die Adjazenzmatrix buchstäblich der Hecke-Operator T₂ ist – produzierte exakt null Generalisierung über Primzahlen hinweg.

Die Hauptursache ist die Knotentransitivität, die wir durch eine Proposition formalisiert haben, welche die Expressivität von Message-Passing GNNs auf knotentransitiven Graphen charakterisiert: Ohne Positional Encoding erzeugen solche GNNs an jedem Knoten identische Embeddings, was ihre Repräsentationen auf Graphenebene auf Funktionen von Durchmesser und Grad beschränkt. Mit Positional Encoding ist eine Verbesserung möglich, aber marginal, da Zufallsvektoren keine strukturellen oder arithmetischen Informationen tragen.

Der theoretische Beitrag geht über unsere spezifischen Experimente hinaus. Die Analyse gilt für jede knotentransitive Graphfamilie: Cayley-Graphen jeder Gruppe, distanz-reguläre Graphen, stark reguläre Graphen. In all diesen Szenarien stoßen Message-Passing GNNs an die gleiche fundamentale Expressivitätsbarriere.

Die Botschaft an die KI- und Zahlentheorie-Community ist klar. Graph Neural Networks können in ihrer jetzigen Form keine arithmetischen Eigenschaften aus algebraischen Graphstrukturen vorhersagen. Die spektralen Eigenschaften von Cayley-Graphen werden von einer Arithmetik gesteuert, die für lokales Message Passing unsichtbar ist. Ein GNN, das einen Cayley-Graphen von SL(2, Fₚ) betrachtet, sieht ein perfekt reguläres, merkmalsloses Gitter. Es kann p = 43 nicht von p = 47 unterscheiden, da die lokale Struktur identisch ist.

Negative Ergebnisse haben einen Wert. Sie definieren die Grenzen eines Forschungsraums und bewahren andere davor, gescheiterte Pfade zu wiederholen. Nach unserem Wissen ist dies die erste systematische Studie an der Schnittstelle von GNNs und zahlentheoretischen Graphstrukturen. Die experimentelle Infrastruktur, bestehend aus über 20 Python-Skripten und mehr als 3000 Zeilen Code für Graphgenerierung, Eigenwertberechnung, Hecke-Eigenwert-Extraktion und GNN-Training über sieben Architekturen, ist an sich ein Beitrag: Sie schafft die rechnerische Grundlage für zukünftige Arbeiten in diesem Bereich.

Zukünftige Richtungen, die produktiver sein könnten, umfassen Transformer-basierte Modelle, die direkt auf Sequenzen von Hecke-Eigenwerten operieren (und Graphen vollständig umgehen), gruppen-äquivariante Architekturen, die die vollständige algebraische Struktur respektieren, sowie hybride neuro-symbolische Systeme, die gelernte Repräsentationen mit Computer-Algebra kombinieren. Die grundlegende Frage, ob maschinelles Lernen zum Verständnis der Riemannschen Hypothese beitragen kann, bleibt offen. Aber unsere Ergebnisse zeigen, dass die Antwort nicht durch Standard-GNNs kommen wird, die algebraische Graphen verarbeiten.

---

Referenzen