Vertex misalignment and changepoint localization in network time series

1. Problem Statement

The paper addresses the challenge of changepoint localization in time series of networks (dynamic networks). A critical, often overlooked assumption in existing literature is that the vertex sets across different time steps are perfectly aligned (i.e., vertex $i$ at time $t$ corresponds to the same entity as vertex $i$ at time $t+1$).

In practice, vertex correspondence is often unknown, corrupted, or non-existent (e.g., in neural organoid growth where cells divide and die, or in social networks where identities shift). The authors investigate how vertex misalignment (shuffling) impacts the ability to detect distributional changes in the underlying network dynamics. They specifically ask: Does losing vertex correspondence render changepoint detection impossible, or can certain signals be recovered using marginal statistics?

2. Methodology and Framework

Theoretical Framework: Latent Position Processes (LPP)

The authors model the network time series using Random Dot Product Graphs (RDPGs) governed by a Latent Position Process (LPP).

• Latent Positions: Each vertex $i$ has a latent position vector $X_{i,t} \in \mathbb{R}^d$ at time $t$.
• Dynamics: The connection probability between nodes is determined by the inner product of their latent positions. The evolution of these positions over time constitutes the LPP.
• Changepoint: A changepoint $t^*$ is defined as a point where the distribution of the LPP changes (either in marginal or joint distributions).

Key Metrics and Tools

To detect changepoints, the authors utilize Euclidean Mirrors, a technique that embeds the sequence of networks into a low-dimensional Euclidean space where changes in dynamics appear as structural shifts (e.g., slope changes).

• $d_{MV}$ Distance (Maximum Directional Variation): A distance metric between latent position distributions at times $t$ and $s$ that accounts for the joint distribution and dependence across time. It requires known vertex alignment.
• $ind\text{-}d_{MV}$ Distance: A distance metric calculated assuming vertices are independent (marginal distributions only). This represents the information available when alignment is lost.
• Wasserstein Distance ($W_p$): Used to compare marginal distributions of latent positions without requiring alignment.
• Graph Matching: An attempt to recover alignment by finding a permutation matrix $P$ that minimizes the Frobenius norm between adjacency matrices ($\|A - PBP^\top\|_F$).

Proposed Models: London vs. Atlanta

To isolate the effects of misalignment, the authors define two distinct LPP models:

1. London Model: The latent positions evolve as a random walk starting from a fixed point. The marginal distribution of latent positions changes over time (specifically, the mean shifts).
   • Hypothesis: Changepoints are detectable via marginal statistics even without alignment.
2. Atlanta Model: The latent positions evolve as a random walk starting from a uniform distribution over the state space. The marginal distribution remains stationary (constant) over time; only the joint distribution (temporal dependence/correlation) changes at $t^*$.
   • Hypothesis: Changepoints are undetectable without alignment because marginal statistics contain no signal.

3. Key Contributions and Theoretical Results

A. Impact of Vertex Shuffling on Dependence

The authors prove that vertex shuffling weakens the dependence between latent positions across time.

• Theorem 1 & Corollary 1: They quantify the error introduced by shuffling. The estimated distance between time points becomes a convex combination of the true joint distance ($d_{MV}$) and the independent distance ($ind\text{-}d_{MV}$). As the proportion of shuffled vertices ($\alpha$) increases, the signal regarding temporal correlation degrades.

B. The London Model (Marginal Sufficiency)

• Result: In the London model, the marginal distribution of latent positions is sufficient to identify the changepoint.
• Theorem 4 & 5: The authors show that statistics based on marginal information (e.g., Average Degree, Wasserstein distance $W_1$) are exactly Euclidean realizable and can localize $t^*$ even with 100% vertex shuffling.
• Implication: For processes where the signal lies in the marginal distribution, vertex alignment is not essential for changepoint detection.

C. The Atlanta Model (Joint Distribution Necessity)

• Result: In the Atlanta model, the marginal distribution is constant; the changepoint is encoded entirely in the temporal correlation (joint distribution).
• Theorem 6: When vertices are shuffled, the $d_{MV}$ mirror collapses into a degenerate, uninformative structure. The $W_1$ and average degree mirrors are flat (zero signal).
• Implication: If the signal is in the joint distribution, vertex alignment is critical. Once lost, the information is irrecoverable.

D. Graph Matching and Optimal Transport

• Theorems 2 & 3: The authors analyze whether Graph Matching or Optimal Transport can recover the lost signal in the Atlanta model.
• Finding: They prove that while these methods can align matrices, they cannot reconstruct the specific joint distributional changes required for changepoint localization in the Atlanta setting. The "information loss" from shuffling in the Atlanta model is fundamental and cannot be corrected by standard alignment techniques.

4. Simulation and Empirical Results

The authors validate their theory through extensive simulations and a real-world-inspired dataset (swarm data).

• London Model Simulations:

  • Methods using $d_{MV}$, $W_1$, and Average Degree all successfully localized the changepoint.
  • Performance remained robust even with 100% vertex shuffling.
  • Interestingly, using marginal statistics (Average Degree) sometimes outperformed $d_{MV}$ due to lower variance.

• Atlanta Model Simulations:

  • True Alignment: $d_{MV}$ successfully localized the changepoint.
  • Shuffled Alignment: All methods (including $d_{MV}$, $W_1$, and Average Degree) failed, with Mean Squared Error (MSE) rising significantly above the "chance level."
  • Graph Matching: Applying graph matching (all-to-one or consecutive) to the shuffled data did not recover the changepoint. The MSE remained high, confirming that alignment recovery is insufficient to restore the lost joint signal.

• Swarm Data (Real-world Application):

  • Applied to a simulated swarm of agents.
  • True Alignment: Detected structural changes at 800s and 810s.
  • Shuffled: The mirror became noisy and uninformative.
  • Graph Matching: Partially recovered the dynamics but failed to detect the second changepoint (810s), suggesting that real-world data often lies between the "London" and "Atlanta" extremes, containing both marginal and joint signals.

5. Significance and Practical Implications

1. Diagnosis of Signal Type: The paper provides a framework for practitioners to determine if their network time series signal lies in the marginal or joint distribution.
   • If the signal is marginal (like London), vertex alignment is non-essential, and robust methods like Wasserstein distances or Average Degree can be used.
   • If the signal is joint (like Atlanta), accurate vertex correspondence is mandatory.
2. Limitations of Graph Matching: The study challenges the assumption that graph matching can universally solve the misalignment problem. In cases where the changepoint relies on subtle joint dependencies, matching may fail to recover the necessary information.
3. Methodological Guidance:
   • Practitioners should test multiple dissimilarity measures (e.g., $d_{MV}$ vs. $W_1$).
   • If $d_{MV}$ and $ind\text{-}d_{MV}$ yield similar results, the signal is likely marginal.
   • If they diverge significantly, the signal is likely joint, and alignment is critical.
4. Theoretical Advancement: The work bridges random matrix theory, optimal transport, and network inference, providing rigorous bounds on how vertex shuffling degrades statistical inference in dynamic networks.

Conclusion

The paper demonstrates that the robustness of changepoint localization in network time series is fundamentally dependent on the interplay between marginal and joint information. While some network dynamics can be tracked without vertex alignment, others are irretrievably lost if correspondence is broken, and this loss cannot be mitigated by standard graph matching techniques. This necessitates a careful selection of inference methods based on the underlying data-generating process.