Phase-Synchrony Clustering for Streaming Graphs

When a graph changes one edge at a time, as in citation networks, social interactions, or similarity graphs over arriving data, systems that keep a clustering of it up to date face an uncomfortable choice. They can freeze the cluster each existing node belongs to and place only the newcomers, which is cheap but lets early mistakes persist forever. Or they can periodically re-optimize everyone, which corrects drift but costs nearly as much as starting over. This note proposes a third option borrowed from models of "temporal binding," the idea from neuroscience-inspired networks that features belonging to the same object are tagged by firing in the same rhythm. Each graph node carries a phase, an angle on a circle or a unit vector on a sphere. Edges pull the phases of connected nodes together. Each time an edge arrives or disappears, only the nodes near it are briefly relaxed. Clusters are simply groups of nodes whose phases agree, so the number of clusters is never fixed in advance.

The specific bet is about where the maintenance work goes, not about oscillators being exotic. Each node can cheaply measure how much it disagrees with its neighbors: how far its phase sits from the weighted average phase around it. That disagreement is near zero inside stable communities and spikes exactly where communities are splitting, merging, or drifting. If update work is spent only where disagreement is high, the method should match the accuracy of full reassignment at close to the cost of frozen assignment. It should also handle edge-by-edge streams, which current dynamic coarsening explicitly does not.

Core Claim

Three ingredients together should beat both frozen incremental updates and snapshot re-optimization on streaming clustering, at equal compute. The first is a per-node running neighborhood sum of phases, updated in constant time per edge event. The second is a local relaxation of coupled-oscillator dynamics on the graph, in the style of Kuramoto models (a classic system of rotating units that pull toward their neighbors' angles). The third is a scheduler that relaxes only nodes whose local coherence has dropped. "Beat" means a better accuracy-per-work curve on drifting graphs and faster recovery after communities merge or split. We expect this without a preset cluster count and without per-event cost that grows with the square of the largest degree.

What would be new is the maintenance mechanism. No paper in the file uses phase dynamics to maintain a clustering of an evolving graph. The closest work uses synchrony either to build static graphs or to cluster static inputs. Synch-Graph turns co-firing spiking neurons into a graph rebuilt from scratch every 150 ms window and classifies it with a graph network, with no incremental maintenance. Artificial Kuramoto Oscillatory Neurons (AKOrN) shows that oscillators on a hypersphere synchronize into object groups through test-time relaxation, but only over fixed couplings inside convolutional or attention backbones. Kuramoto Orientation Diffusion Models runs Kuramoto dynamics on fixed lattices for generation. We take the relaxation idea from AKOrN and move it onto a graph whose couplings themselves change.

Research Program

The motivation comes from the dynamic-maintenance literature. Adapting to Evolving Graphs introduces two dynamic coarsening methods. DIGC freezes old node assignments and suffers "error lock-in." ACNR reassigns nodes to fix drift but is expensive, works only on discrete snapshots, and is stated by its authors not to support continuous-time event streams. Fully Dynamic Coreset Spectral Clustering keeps edge updates at $O(\log n)$ but pays $O(k d_{\max}^2 \log n)$ at query time, where $k$ is the cluster count and $d_{\max}$ the maximum degree, so it degrades on graphs with hubs. Deep Temporal Graph Clustering (BenchTGC) processes interactions chronologically to avoid future edges leaking into past states, but requires a fixed $k$ and names automatic cluster-count discovery as open.

The method works as follows. Each node $i$ holds a unit vector $x_i \in S^{N-1}$, with $N$ around 4–8 so that many clusters fit without crowding a single circle. It also stores a running sum

$$S_i = \sum_j w_{ij} x_j - \beta \sum_{j \in R_i} x_j,$$

where $w_{ij}$ is the current edge weight. $R_i$ is a small, bounded set of sampled non-neighbors that provide weak repulsion so unrelated groups spread apart. $\beta$ is that repulsion strength.

Inserting or deleting edge $(i,j)$ changes only $S_i$ and $S_j$, in $O(N)$ time. A node's coherence is

$$\rho_i = \frac{x_i \cdot S_i}{\lVert S_i \rVert}.$$

This is the alignment between a node and its neighborhood average, and it costs nothing extra to read off. A relaxation step moves $x_i$ toward $S_i$ (projected back to the sphere), as in AKOrN's update without a learned natural frequency. Each moved node then pushes its change into its neighbors' sums.

A priority queue keyed on $1-\rho_i$ decides which nodes get relaxed, under a fixed budget of node updates per event. Nodes that never fall below the coherence threshold are never touched. That property is what should make this cheaper than ACNR. When a hub moves, its change must be pushed to all its neighbors, so hub moves are expensive. We expect hubs to move rarely because their many neighbors anchor them. Measuring whether this holds on power-law graphs is part of the program, not an assumption.

Repulsion is kept sparse and bounded. Neuronal Synchrony in Complex-Valued Deep Networks reports that dominant negative couplings produce chaotic phase switching, so this is a known constraint on the design.

Cluster labels are read out online by grouping phase vectors with an angular threshold, with no preset $k$. A new group forms whenever a coherent set of nodes settles at a direction far from every existing group. This mirrors KomplexNet, which formed a third phase cluster zero-shot when scenes went from two digits to three.

Node deletion simply subtracts the node's contributions from its neighbors' sums and flags those neighbors for relaxation. This sidesteps the unit-norm "absence" problem AKOrN notes, because absent nodes hold no state at all.

The base method is training-free. A learned variant, in which a small encoder sets edge weights from node features, is a follow-up only if the base method holds up.

The analysis component asks one question: does low coherence actually predict which nodes a full re-optimization would reassign? We measure the precision and recall of the $\rho_i$ threshold against the set of nodes whose labels change under from-scratch spectral clustering after each batch of events. If coherence is a poor predictor, the scheduler loses its justification, and we want to find that out directly.

Baselines

The naive reference point is frozen assignment in the style of DIGC from Adapting to Evolving Graphs. New nodes are placed and old ones are never moved. It shows how much error lock-in costs on each stream, and any method that cannot beat it on drifting graphs has no case.

The accuracy ceiling is static spectral clustering recomputed from scratch on the current graph at each evaluation point. It is run with the true $k$, which gives it an advantage. It is not a fair latency competitor, but it defines the clustering every incremental method is trying to track.

The strongest existing maintenance method for clustering quality under edge churn is the just-in-time coreset structure of Fully Dynamic Coreset Spectral Clustering. On dynamic k-NN EMNIST, its authors report it to be about 10x faster per query than static recomputation by the end of graph growth, with adjusted Rand index (ARI, agreement with ground-truth clusters corrected for chance) "nearly identical" to the full algorithm. No exact ARI value is reported in the file. We run it with its published $\epsilon$ and with $k$ set to the true cluster count. This gives it oracle knowledge we deny our method.

ACNR from Adapting to Evolving Graphs is the reassignment competitor. We feed it micro-snapshots at several event-batch sizes so it can approximate streaming. Its reported numbers are 10–20x speedup over recomputation and 98–99% of full-recomputation downstream accuracy.

BenchTGC from Deep Temporal Graph Clustering is the learned temporal-clustering competitor on its own Data4TGC datasets. Its reported gain is a 42.15% relative ARI improvement on arXivCS over static adaptations. That is a relative figure, and no absolute ARI is given in the file. For comparability we reuse that benchmark's chronological splits.

All methods get the same event stream, the same hardware, and an equal hyperparameter-tuning budget of twenty configurations on a held-out early prefix of each stream. They are compared on matched total work, counted as node-state updates plus distance computations, as well as on wall-clock time.

Two ablations isolate the key ingredients. The first keeps the scheduler but replaces phase vectors with discrete label propagation, which tests whether continuous phases matter. The second keeps the phase dynamics but spends the same per-event budget on uniformly random nodes or on the event's endpoints and neighbors, which tests whether coherence-based targeting matters.

Beating the field means two things. On the accuracy–work curve, our method must match ACNR's ARI at no more than DIGC's work plus a small multiple. It must also strictly dominate both ablations on drifting streams.

Why not just…?

Why not just recompute periodically from scratch? Recomputing from scratch is the accuracy ceiling, but the file shows it is 10–20x slower than incremental coarsening (Adapting to Evolving Graphs) and 10x slower per query than coresets on EMNIST (Fully Dynamic Coreset Spectral Clustering). Static methods also ran out of memory on arXivLarge (Deep Temporal Graph Clustering). Between recomputations its answers go stale, and our recovery-time metric measures that staleness directly.

Why not just run warm-started label propagation on touched nodes? This is the real threat. Label propagation already needs no $k$, is local, and is cheap. Our first ablation is exactly this, using our own scheduler. Our hypothesis is that discrete labels give no graded disagreement signal: they either flip or they don't. That should make them prone to two failures, ties that flip back and forth at community boundaries and a slower response to gradual drift. If the ablation matches us, the honest conclusion is that the contribution is the coherence-driven scheduler rather than the oscillators. We would report it that way.

Why not just warm-start an incremental spectral embedding and re-run k-means? A few power-iteration steps from the previous eigenvectors also reuse past work. However, each step touches every node, it needs $k$, and splits or merges change the number of eigenvectors needed. We include it as an extra baseline at matched work. The planted merge/split streams are where we expect it to lag: after a split it must notice that $k$ has changed, whereas phase groups can separate on their own.

Why not just shrink ACNR's snapshots to tiny batches? We do this as part of the ACNR baseline. ACNR re-optimizes everything inside each snapshot, so its per-event cost should rise as batches shrink. Coherence-driven relaxation instead skips nodes that are already consistent with their neighbors. If ACNR's curve meets ours at small batch sizes, the advantage is only an engineering one, and we would say so.

Proposed Experiments

The first testbed is the dynamic stochastic block model streams and dynamic k-NN MNIST/EMNIST graphs used in Fully Dynamic Coreset Spectral Clustering. We extend them with planted events in which two communities merge, one splits, and a new community appears mid-stream. This tests recovery time, measured as the number of events until ARI returns within 0.02 of the recompute ceiling, and tests whether new clusters are found without a preset $k$.

The second is AS-733 and the Kindle and DBLP streams from the dynamic-coarsening work, for organic drift. The third is Data4TGC, namely arXivCS, DBLP, Patent, and arXivLarge, replayed edge by edge in timestamp order. arXivLarge is the scale test at 1.3 million nodes and 13 million interactions, and memory must stay well under the 10 GB envelope BenchTGC reports. The fourth is power-law graphs with tunable maximum degree, where we plot per-event and per-query latency against $d_{\max}$ to test directly whether we avoid the quadratic-degree growth of the coreset method.

Metrics are ARI and normalized mutual information against ground truth over time, and ARI against the recompute ceiling. We also report work and wall-clock time per event, label churn (the fraction of unchanged nodes whose label flips anyway), and the precision and recall of coherence as a predictor of true reassignments.

The decisive checks are three. First, on planted-drift streams, the full method must beat frozen assignment in recovery time and match ACNR in accuracy at markedly less work. Second, coherence-targeted relaxation must beat random-budget relaxation at equal budget, or the central mechanism is refuted. Third, the phase representation must beat label propagation under the same scheduler on boundary churn and gradual drift; otherwise the oscillator component should be dropped. We would also report negative results, for example chaos when repulsion is too strong, or hubs moving often enough to erase the latency advantage.