Phase-Aligned Graph Coarsening for Training Synchronization GNNs at Scale

Many imaging and sensing pipelines contain a hidden sub-problem called phase synchronization. It works like this. You have many local pieces, such as overlapping patches of a ptychographic scan or nodes of a sensor network. Each piece is correct only up to an unknown rotation of its phase. You also have noisy measurements of the phase difference between pairs of pieces, and you want one consistent phase for every piece. Graph neural networks (GNNs), models that update each node by aggregating messages from its neighbors, have recently become the most robust tool for this task when many pairwise measurements are corrupted. Their best-known version has only been run on graphs of about a thousand nodes. Real stitching graphs from large scans have millions of nodes, and ordinary tricks for speeding up GNN training break exactly the structure these models depend on.

This note proposes one such speedup, graph coarsening (training on a smaller graph of merged "super-nodes"), redesigned for phase data. The idea is simple. Before merging a cluster of nodes, rotate each member into a common local phase frame, then merge. Written as complex matrices, this rotate-then-merge step turns out to be a Hermitian version of the message-passing-preserving coarsening of Joly and Keriven. That lets their error guarantees carry over, even though their framework was built for undirected graphs and phase-difference graphs look directed. We would train the synchronization GNN on the coarse graph, lift the result back, and fine-tune briefly. The claim to test is that this gives order-of-magnitude reductions in training memory and time with accuracy close to full-graph training. Phase-blind coarsening and neighbor sampling should both fail at this.

Core Claim

Phase synchronization data on a graph with edges $(i,j)$ can be written as a Hermitian matrix $H$ with entries $H_{ij} = w_{ij} e^{i\Delta_{ij}}$. Here $w_{ij}$ is an edge reliability weight and $\Delta_{ij}$ is the measured phase difference. The property that looks "directed," $\Delta_{ij} = -\Delta_{ji}$, is just Hermitian symmetry, $H_{ji} = \overline{H_{ij}}$.

Graph Coarsening with Message-Passing Guarantees builds the coarse propagation matrix $S_c = Q S Q^+$. In that formula $Q$ assigns nodes to super-nodes and $Q^+$ (its pseudo-inverse) lifts signals back. The paper proves this construction preserves multi-step message passing where spectrum-preserving coarsening does not. It lists directed graphs as open future work.

We replace the real assignment matrix with a phase-aligned one: $$ (Q_\phi)_{k v} = \frac{1}{\sqrt{|C_k|}}\, e^{-i\phi_v}\ \text{if } v \in C_k,\qquad H_c = Q_\phi\, H\, Q_\phi^{+}. $$ In this formula $C_k$ is the $k$-th cluster and $\phi_v$ is node $v$'s phase estimated by synchronizing only within its own cluster.

If each cluster is internally consistent, rotating its members into a common frame makes their phases add constructively. The super-node then carries a clean phase. The coarse edge phases are aggregates of fine edge phases taken along consistent paths. The coarse graph's cycle inconsistency (the sum of phase offsets around a triangle, which is zero for clean data) is a weighted combination of fine-cycle inconsistencies. That makes it a usable self-supervised training signal.

A phase-blind $Q$ with real, nonnegative entries averages vectors pointing in unrelated directions, so they cancel. We expect this cancellation, not reduced graph size, to be the dominant failure of naive coarsening on phase data. Separating those two causes is the experiment that matters most.

The theoretical part of the project extends the restricted-spectral-approximation bound from real symmetric to complex Hermitian propagation matrices. That bound controls how far coarse message passing drifts from fine message passing. The extension should be mostly routine, because the proof relies on an orthonormal eigenbasis, which Hermitian matrices also have. The non-routine part is adding a term that controls error through the within-cluster synchronization error in $\phi$.

Why This Pairing, and What It Builds On

The downstream model is GNNSync, from Robust Angular Synchronization via Directed Graph Neural Networks. It is a directed GNN with unrolled projected power-method steps, a triangle cycle-inconsistency loss, and a periodic "upset" loss. It outperformed seven baselines under heavy outlier noise, on graphs up to about 1,100 nodes. This paper motivates the proposal and supplies the model. We do not change its architecture. We change only the graph it is trained on.

The coarsening paper supplies the operator and the proof strategy. It also constrains the design. Its bounds hold only for linear propagation, and GNNSync is nonlinear. We therefore make no guarantee claims about the full model and treat the nonlinear case empirically.

Multiscale Phase Retrieval motivates the hierarchy. It solves phase retrieval in small local blocks and then synchronizes blocks through a multilevel schedule optimized with plain gradient descent. Our phase-aligned super-nodes are the learned, graph-level counterpart of those blocks. Unlike that work, we need no special interferometric hardware; the graph comes from the data.

Section 2 of the research file shows that nobody has done this pairing. PhaseCode (Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes) uses message passing on a designed sparse bipartite graph, but its graph is fixed and nothing is learned. DeepPhaseCut speeds up PhaseCut with convolutional networks on small image patches and uses no graph structure.

The application regime is ptychographic stitching. A ptychographic scan illuminates many overlapping spots and records a diffraction pattern at each. Reconstructing each spot locally leaves every patch with its own unknown global phase, which is the ambiguity described in Phase Retrieval using Alternating Minimization. The relative phase of two overlapping patches can be read from the argument of their inner product over the shared region. That produces a synchronization graph whose size grows with scan length. Irregular scan paths and position errors, which Predicting ptychography probe positions using single-shot phase retrieval neural network shows are a real fragility, corrupt edges. That is exactly the outlier regime where GNNSync is claimed to help.

Research Program

The work has three parts.

The first part is the operator and its theory. We will implement $Q_\phi$ with clusters chosen by a cheap local rule. The rule grows clusters greedily and rejects any addition that raises the cluster's mean triangle inconsistency above a threshold. This avoids the SVD and spectral-clustering cost that the coarsening paper flags as its offline bottleneck. Within-cluster phases $\phi_v$ come from a few power-method iterations restricted to the cluster. We will prove the Hermitian extension of the propagation-error bound for the linear part of the model, which is the unrolled power-method steps.

The second part is the training procedure. We coarsen, possibly over several levels, and train GNNSync on $H_c$ with its original losses. We then initialize node phases on the fine graph as $\phi_v$ plus the lifted super-node phase, and fine-tune on sampled fine subgraphs for a small, fixed number of steps.

The third part is scaling the graphs. We build synthetic random-geometric and Erdős–Rényi synchronization graphs from $10^3$ to $10^6$ nodes with controlled outlier fractions. We also build ptychographic stitching graphs from simulated scans on MNIST and Stanford Dogs images. These are the image sets used by Deep Iterative Phase Retrieval for Ptychography. We add irregular scan paths and injected probe-position errors.

Baselines

The naive reference point uses no learning at all. It is spectral synchronization followed by the generalized power method on the full graph, the classical approach GNNSync was compared against. It is linear in the number of edges per iteration and scales easily. Every method must beat it on phase error at matched outlier rates, or learning is not justified at that scale.

The strongest competitor is GNNSync itself, trained on the full graph with its published losses, wherever that fits in memory. At larger sizes it is trained with neighbor-sampled mini-batches in the style of FastGCN. It is the strongest competitor because it defines the accuracy we are trying to keep. For exact synchronization error, no reported result was found on Lacuna for GNNSync on PACM or U.S. Cities. The file states only that it beat seven baselines across more than 340,000 runs. We will therefore rerun it ourselves on those datasets with the same hyperparameter search budget, the same GPU, and the same number of gradient steps as our method, counting fine-tuning steps.

For coarsening fidelity, the reference is Joly and Keriven's Cora result. Linear SGC reached 81.6% accuracy on the full graph, 78.5% with their operator at 70% reduction, and 74.6% with naive coarsening, and training was about 30% faster at 50% reduction. Our method beats this baseline if it recovers at least that fraction of the full-graph gap in phase error at comparable reduction ratios. It must also cut peak training memory roughly in proportion to the reduction.

Three ablations isolate the key ingredient. The first uses the same clusters with a real, phase-blind $Q$. The second uses phase-aligned clusters with the symmetric sandwich $Q_\phi H Q_\phi^{\top}$ instead of the pseudo-inverse form. The third uses random clusters instead of cycle-consistency-guided clusters. All share the same training budget.

Why not just…?

Why not just run the spectral or power method on the full graph, since it already scales? This is a real threat, and at low outlier rates we expect it to tie. Its known weakness is heavy, structured corruption, which is the regime where GNNSync reported gains. The experiments sweep the outlier fraction. The proposal matters only above the crossover where full-graph GNNSync beats the power method. If that crossover disappears at large scale, the result is negative and we will report it as such.

Why not just train GNNSync on small graphs and run inference on the large one? Inference is cheap, so this could make coarsening unnecessary. It will fail if the corruption patterns or degree distributions of the large graph differ from the small training graphs, as with long ptychographic scans whose position drift accumulates. We include it as a baseline, with training on 1,000-node subgraphs drawn from the same generator. If it matches our method, the honest conclusion is that training scale was never the bottleneck.

Why not just use neighbor sampling or cluster mini-batches, the standard GNN speedup? Sampling drops edges, which destroys the triangles the cycle-inconsistency loss is computed on. With per-layer sampling most triangles vanish. We will measure directly the fraction of triangles that survive each sampler and relate it to final error.

Why not just use multiple GPUs or an out-of-core system? Marius++ and DiskGNN show that single-machine out-of-core training can beat clusters. DiskGNN reports a 7.5x average speedup over Ginex on ogbn-papers100M. These systems move data faster but still compute on every edge, and they fix the graph layout offline. They are complementary to our method rather than competing with it. We report wall-clock time next to a plain in-memory full-graph run so readers can tell how much of the gain comes from reducing computation rather than from I/O.

Decisive Checks

The central experiment plots phase error, defined as mean angular error after removing the global phase, against reduction ratio. It compares phase-aligned and phase-blind coarsening at a fixed outlier rate on graphs of $10^4$ nodes, where full-graph GNNSync still fits. The claim is supported only if phase-aligned coarsening stays within a small margin of full-graph GNNSync at 70–90% reduction while phase-blind coarsening degrades sharply. A second check tests the theory: the measured drift of the unrolled linear steps should follow the Hermitian bound as within-cluster synchronization error grows.

A third check scales to $10^6$ nodes and to ptychographic stitching graphs. There we report peak memory, time to reach a target error, and downstream stitched-image PSNR against the power method and the train-small-infer-large baseline. If phase-aligned coarsening wins only where the power method already succeeds, we will conclude that this is not the right lever.