Topology-Calibrated Graph Diffusion

1. Integration point: replace the fixed-depth propagation block in a GCN, graph SSM, or residual message-passing network. Use the combinatorial Laplacian L=D-A, optionally after adding self-loops, and propagate hidden states with a stable diffusion operator rather than repeatedly applying an unconstrained adjacency matrix. For each connected graph, compute n=|V| and Delta=max degree. If the dataset supplies a genus upper bound g, set the target diffusion horizon T=beta*n/(Delta*max(g,1)); for known K_h-minor-free data, use T=beta*n/(Delta*h^2*(log(max(h,2)))^2). beta is a tunable dimensionless constant, initially 1. 2. Pseudocode: inputs X, edge list, g (or h), number of propagation substeps m. Build D and L; set alpha=min(eta/Delta, T/m), with eta in (0,1), for example eta=0.5; set H=X. Repeat j=1,...,m: H=H-alpha*(L@H); then apply the usual residual MLP or graph-convolution update. Feed H to the task head. This realizes total diffusion time approximately T while respecting the high-frequency stability ceiling alpha<=1/Delta. 3. The paper supplies the topology-dependent scale Delta*g/n or Delta*h^2(log h)^2/n; the implementation estimates n and Delta exactly, while g or h comes from metadata or a safe known upper bound. If topology metadata is unavailable, compare against an empirical proxy obtained from a graph-minor or genus estimator, but do not use that proxy in the first experiment. 4. Cheap validation: train a 3-layer GCN and a fixed-depth APPNP-style baseline on Cora, CiteSeer, and a synthetic planar-versus-random graph benchmark. Compare fixed propagation horizons with the calibrated horizon at equal message-passing FLOPs. Measure validation accuracy, oversmoothing via mean pairwise cosine similarity of node embeddings, and stability under graph-size scaling. The hypothesis is that calibrated diffusion retains higher accuracy and lower embedding collapse on large planar or low-genus graphs, while the stability ceiling prevents divergence on high-degree graphs.