Degree-Neutral Unfolded Embeddings for Dynamic Networks with Drifting Popularity

When a network is observed as a sequence of time windows, such as weekly email traffic, daily school contacts, or rolling stock-correlation graphs, analysts want one picture per window that shows which group each node belongs to, and they want that picture to move only when group membership actually changes. Spectral embeddings place each node at coordinates given by the top eigenvectors of a graph matrix. They fail at this in a specific, predictable way. A node's coordinates scale with how many connections it has, so a node that becomes busier in one window, like a student at recess or a stock in an earnings week, appears to move even though its group has not changed. Unfolding is the current best fix. It concatenates all window matrices side by side and takes one singular value decomposition, so every window shares a single coordinate system. Unfolded Laplacian Spectral Embedding (ULSE) introduced normalized-Laplacian unfolding to remove this "spurious temporal drift." Its guarantees, however, hold only when nodes within a group have statistically equal connectivity. The authors list the extension to time-varying degree-corrected models as open.

We propose to close that gap using a specific tool from static spectral clustering: degree-neutral regularization of the random-walk Laplacian. In a static graph, Optimal Laplacian regularization for sparse spectral community detection showed that adding a carefully chosen constant $\tau$ to every node's degree before normalizing makes eigenvector entries depend on community labels alone and not on degrees. The same choice keeps the informative eigenvalues visible down to the point where detection becomes theoretically impossible. Our claim is that choosing this constant separately for each window, and then unfolding, yields embeddings in which movement signals membership change even when node popularity drifts. The claim also covers the regime that time-window analysis forces on us: short windows, where each snapshot is sparse. The same machinery supplies a principled answer to a question that is usually settled by guesswork, namely how short a window can be before community structure becomes undetectable.

Core Claim

We model window $t$ as a time-varying degree-corrected block model:

$$P^{(t)}_{ij} = \theta_i(t)\,\theta_j(t)\,B^{(t)}_{z_i(t)\,z_j(t)}.$$

Here $P^{(t)}_{ij}$ is the probability of an edge between nodes $i$ and $j$ in window $t$, $\theta_i(t)$ is node $i$'s popularity in that window, $z_i(t)$ is its community, and $B^{(t)}$ is the block connectivity matrix. For each window we form the regularized random-walk operator $(D_t+\tau_t I)^{-1}A_t$, where $A_t$ is the adjacency matrix and $D_t$ is the diagonal degree matrix. The constant $\tau_t$ is set by the Bethe-Hessian rule of Dall'Amico et al., estimated from that window alone. The Bethe-Hessian is a matrix from statistical physics whose negative eigenvalues count detectable communities. We stack the per-window operators into one unfolded matrix and take a truncated singular value decomposition. Node $i$ at time $t$ is then read off the time-$t$ block.

We conjecture, and aim to prove, that in the population limit this embedding satisfies ULSE's two stability properties even when $\theta_i(t)$ varies. Cross-sectional stability means that same-community nodes coincide within a window. Longitudinal stability means that a node whose community does not change keeps its coordinates. ULSE-n1 and ULSE-n2 are only guaranteed these properties when $\theta$ is constant. The key difference from existing work is therefore the regularizer: it is chosen per window from each window's own spectrum and aimed at degree neutrality, rather than being a fixed normalization. A byproduct is a window-length rule. Choose the shortest window for which each window's Bethe-Hessian still reports $K$ negative eigenvalues, where $K$ is the number of communities.

Research Program

The theoretical program has three parts. First, we will compute the population unfolded operator under the model above and show that the per-window $\tau_t$ cancels $\theta_i(t)$ in the right singular blocks. We expect this to require the per-window degree-neutral $\tau_t$, not a single shared $\tau$, because windows differ in average degree. Second, we will extend ULSE's dynamic Cheeger-type bound, which relates unfolded singular values to the worst conductance bottleneck across windows, to the regularized operator. Third, we will characterize when an informative singular value separates from the noise bulk as window length shrinks. This characterization turns the window-length rule into a statement with conditions. The last part may prove only a sufficient condition; we will say so if that is all we get.

Each role in the program is played by different prior work. ULSE supplies the unfolding construction and the stability criteria we test against. Dall'Amico et al. supply the regularizer and its Bethe-Hessian estimate. Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel is a constraint on the design: it shows that row-normalizing embeddings removes degree scaling, but that low-leverage nodes then need a thresholding step with no automated cutoff. This is exactly the fragility we expect short windows to expose. Spectral Algorithms for Community Detection in Directed Networks is a second constraint. Its ratio-of-eigenvectors trick cancels popularity, but its consistency requires average degree well above $\log n$ and a core-attachment step for peripheral nodes. Short windows violate both. Within scope are undirected graphs, a fixed node set, and fixed $K$. Nodes absent from a window enter as isolated rows. Handling them gracefully is part of the evaluation, not an assumption.

Baselines

The naive reference point is to aggregate all windows into one graph and run static regularized spectral clustering (RSC) as in Qin and Rohe. This assigns each node a single label, so it cannot register membership change. Its only role is to anchor the accuracy of stable nodes and to show how much signal is lost when time is ignored.

The strongest existing method is ULSE, in both the n1 and n2 variants, as described in Unfolded Laplacian Spectral Embedding. It is the only method in the file built for exactly this question, dynamic embeddings under degree heterogeneity. On synthetic dynamic block models with high degree heterogeneity, its authors report ULSE clustering scores of "ARI/NMI ~0.9–1.0," against "ARI ~0.54" for unfolded adjacency embedding (UASE). ARI and NMI are standard agreement scores between predicted and true labels. That result was obtained with time-constant popularity. On the Primary School, Brain, and S&P 500 data, the file reports only that ULSE "consistently outperformed" alternatives; no reported result found on Lacuna for numeric scores there.

The second strong baseline is UASE followed by per-window row normalization, which transplants the RSC projection into the unfolded setting. A third is per-window ratio-of-eigenvectors applied to UASE's right blocks, in the D-SCORE style.

All methods will use the same unfolded data, the same embedding dimension, the same k-means step, and a matched budget for tuning. For ULSE and the row-normalized variants, "matched" means we grid-search any thresholds and choose them with oracle labels, and we report this choice openly, while our $\tau_t$ is estimated without labels. To beat ULSE, our method must do two things on the drifting-popularity benchmarks: raise mean per-window ARI by a margin larger than seed-to-seed spread, and cut the embedding displacement of non-switching nodes. In windows of moderate density, where ULSE is already near its reported 0.9–1.0 regime, we must match it within noise.

The ablations isolate the key ingredient. We compare per-window Bethe-Hessian $\tau_t$ against $\tau=0$, against $\tau_t$ equal to each window's average degree (the Qin–Rohe heuristic), and against a single shared $\tau$ for all windows. Each comparison is run with and without row normalization. If a shared $\tau$ performs as well as per-window $\tau_t$, then the temporal part of the claim fails.

Why not just…?

Why not just row-normalize existing unfolded embeddings? Under the model above, each right-block row of UASE is roughly $\theta_i(t)$ times a community vector, so row normalization cancels $\theta_i(t)$ in expectation. This is the most serious threat to the proposal, and in dense windows we expect it to roughly tie with our method. We argue it breaks in short windows. There, a low-degree node's row is mostly noise, and normalizing it to unit length inflates that noise to full size. Qin and Rohe needed leverage thresholding for exactly this reason. Our window-length sweep is designed to show where the two methods diverge. If they never diverge, we will report that row-normalized UASE suffices and reduce the contribution to the window-length rule.

Why not just apply the ratio-of-eigenvectors trick per window? Dividing by the leading singular vector cancels popularity only when that vector's entries are bounded away from zero. D-SCORE's guarantee requires average degree much larger than $\log n$, together with a core-attachment step. Nodes that are nearly isolated within a window make the division unstable. We include this method as a baseline and expect it to degrade fastest as windows shrink.

Why not just set $\tau$ to the average degree in every window? This is cheap, and it may be enough away from the detectability threshold. Dall'Amico et al. show, however, that the average-degree choice collapses eigenvector entries into a single unimodal distribution near that threshold, while the Bethe-Hessian choice keeps them bimodal. Short windows push every snapshot toward this threshold. The average-degree ablation above tests this directly.

Why not just aggregate the windows and cluster once? Aggregation cannot represent a node switching communities. ULSE's dynamic Cheeger analysis shows that unfolding tracks the worst bottleneck across windows, while averaging blurs transient bottlenecks. This baseline serves only as the floor for accuracy on stable nodes.

Proposed Experiments

The central benchmark is synthetic data from the time-varying degree-corrected model, with power-law popularity whose exponent varies as in Qin and Rohe's static experiments. We run three regimes. In the first, memberships are fixed and popularities drift through random bursts; we measure false movement as the mean displacement of stable nodes. In the second, a fraction of nodes switch communities at times that coincide with degree bursts, which is the adversarial case. There we measure how well each node's per-window displacement separates switchers from stayers, scored as area under the ROC curve (the probability that a random switcher moves more than a random stayer). In the third, a fixed edge stream is re-cut into progressively shorter windows. There we plot per-window ARI against window length and check whether our Bethe-Hessian window rule lands near the empirical point where accuracy collapses.

As a sanity check, before any dynamic claim, the per-window operator reduced to a single snapshot must reproduce static behavior on Political Blogs. On that network, Qin and Rohe report RSC mis-clustering "about 80 out of the 1,222 nodes," and Wang et al. report 60 errors for D-SCORE with core attachment. We expect to land in that range after symmetrizing the graph.

The real-data evaluation uses the Primary School contact network, dynamic brain connectivity, and S&P 500 return networks from the ULSE study. Because the file gives no numeric results for these, we will rerun ULSE ourselves under identical preprocessing. Where ground-truth labels exist (school classes, known sectors), we report per-window ARI and NMI. We also report the stability of non-switching nodes, and a qualitative check of whether detected moves coincide with known events such as recess periods or market shocks, as opposed to degree spikes alone.

The decisive checks are these. On the drifting-popularity synthetic data, per-window $\tau_t$ must beat ULSE on stable-node displacement. The comparison with a shared $\tau$ and with row-normalized UASE must show that the per-window, degree-neutral choice matters specifically in short windows. And the window rule must predict the collapse point better than a fixed average-degree threshold. If row-normalized UASE matches us at every window length, the unfolding-plus-regularization claim is refuted, and we will say so.