Curvature-Preserving Graph Augmentation
Implementation & benchmark of arXiv:2608.01929 — Markov and lattice bases for Forman-Ricci curvature of graphs
Source paper: Markov and lattice bases for Forman-Ricci curvature of graphs arXiv:2608.01929 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Generate alternative graph views by applying small integer Markov moves to the joint degree matrix, while rejecting moves that violate nonnegativity or realizability as a simple graph. Train a GNN to produce consistent predictions across the original and rewired views, preserving degree frequencies and curvature-frequency statistics while forcing robustness to higher-order topology.
Formulas
Mathematical statement
For a graph with maximum degree \(\Delta\), let \(J_{ab}\) denote the joint degree matrix entry for edges whose endpoint degrees are \(a\) and \(b\), using the paper's symmetric convention. The paper states that two JDMs \(J,K\) have equal degree frequencies when, for every \(a\), \(J_{aa}+\sum_{b=1}^{\Delta}J_{ab}=K_{aa}+\sum_{b=1}^{\Delta}K_{ab}\), and equal curvature frequencies when, for every curvature class \(\kappa\), \(\sum_{a\leq b,\ a+b=\kappa}J_{ab}=\sum_{a\leq b,\ a+b=\kappa}K_{ab}\). These constraints can be written \(A\operatorname{vec}(J)=A\operatorname{vec}(K)\), so a Markov move \(m\in\ker_{\mathbb Z}(A)\) maps \(J\) to \(J+m\) without changing the statistics. The concrete degree-three move shown in the paper is \(m=\begin{pmatrix}0&0&1&-1\\0&-1&1&1\\1&1&-1&0\\-1&1&0&0\end{pmatrix}\), which replaces edge-degree types \(\{1,4\},\{2,2\},\{3,3\}\) with \(\{1,3\},\{2,3\},\{2,4\}\). A move is legal only when \(J+m\geq0\) entrywise and the resulting degree-class matrix is realizable by a simple graph.
Implementation notes
Integrate this at the graph-data-loader level for message-passing GNNs, before each training epoch or before each sampled minibatch. The input is a simple graph \(G=(V,E)\), its degree labels \(d_v=\deg(v)\), and a target number \(T\) of rewiring attempts. First compute the JDM \(J\) by counting edges by endpoint degree classes. Construct a library of degree-three moves \(m\) satisfying \(A\operatorname{vec}(m)=0\); begin with the explicit 4-by-4 move in the formula and generate permutations of its degree labels when valid. For each attempt, sample a move, check \(J+m\geq0\), select concrete graph edges having the required endpoint-degree types, and replace the old edge-type multiset with the new one. Reject proposals that create self-loops, duplicate edges, or disconnect the graph if connectivity is required. Pseudocode: G_aug=copy(G); repeat T times: J=JDM(G_aug); m=sample_move(); if min(J+m)>=0: proposal=instantiate_edges(G_aug,m); if simple_and_realizable(proposal): G_aug=proposal. Train with supervised loss on \(G\) plus \(\lambda\|f_\theta(G)-f_\theta(G_aug)\|^2\), where \(f_\theta\) is the graph-level or node-level prediction. The paper supplies the exact invariant equations and move condition; empirical code estimates realizability and chooses \(\lambda\), move rate, and the number of attempts. Start on Cora or ogbn-arxiv with a 2-layer GCN or GraphSAGE baseline, using 1-5 rewiring moves per graph. Measure clean validation accuracy, accuracy under random edge perturbations, and prediction consistency. Success means equal or better clean accuracy and a measurable reduction in performance loss under topology perturbation, while verifying that degree and curvature-frequency histograms are exactly unchanged.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.