Efficient Estimation for Longitudinal Networks via Adaptive Merging

Haoran Zhang, Junhui Wang

TL;DR

This paper introduces a novel framework for estimating the structure of longitudinal networks—systems where connections between nodes appear as a stream of events in real-time. By adaptively merging sparse temporal snapshots into denser, structurally consistent intervals, the authors leverage tensor decomposition and Poisson processes to significantly reduce estimation error compared to traditional fixed-interval methods.

What Problem Does This Paper Address?

Longitudinal networks are everywhere: users "liking" posts on social media, countries engaging in diplomatic conflicts, or neurons firing in a brain. Unlike static networks, these are "continuous-time" systems.

The primary challenge is extreme sparsity. Because interactions are instantaneous, a "snapshot" of the network at any single millisecond might contain only one or zero edges. To get enough data to see a pattern, researchers usually "bin" the data into fixed time intervals (e.g., one month). However, this is a blunt instrument:

  1. High Bias: If the network structure changes rapidly within that month, the binning blurs the details.
  2. High Variance: If the network is stable for a year, binning it into months leaves each bin unnecessarily sparse, making the estimate noisy.

The authors aim to find the "Goldilocks" zone—merging intervals only when the underlying network structure remains stable, thus balancing the bias-variance tradeoff.

Methods

The authors propose a two-step estimation procedure:

  1. Initial Estimation: They split the total time into many tiny, equal-sized intervals. They model the edge occurrences as a Poisson point process and assume the underlying network propensity follows a low-rank Tucker tensor decomposition. This step produces initial "temporal embedding vectors" that describe how the network evolves over time.
  2. Adaptive Merging: They apply a change-point detection algorithm to these temporal embeddings. This identifies periods where the network structure is relatively constant. Adjacent tiny intervals are then merged into larger, "adaptive" blocks.
  3. Refined Estimation: Finally, they re-estimate the network structure using these merged blocks via a Projected Gradient Descent (PGD) algorithm.

A key technical contribution is the modified PGD algorithm, which uses different step sizes for different components of the tensor (the core tensor vs. the node embeddings), ensuring faster and more stable convergence.

Datasets

  • Synthetic Datasets: The authors generated various longitudinal networks with different node counts ($n=50, 100$) and time durations ($T$) to test the model under "strong," "medium," and "weak" data intensity regimes.
  • Militarized Interstate Dispute (MID) Dataset: A real-world dataset covering major international disputes from 1895 to 2014. It includes 195 countries (nodes) and over 110,000 temporal edges.

Key Insights and Ideas

  • The Power of Incoherence: The authors introduced "incoherence conditions" into their theoretical analysis. This allowed them to prove that their method works even in "weak intensity" regimes—scenarios where data is so sparse that previous state-of-the-art methods failed to provide theoretical guarantees.
  • Structural Change as a Signal: Instead of treating time as a simple axis, the paper treats the change in temporal embeddings as the signal for merging. This means the model "learns" the temporal resolution of the data from the data itself.
  • Linear Convergence: They proved that their PGD algorithm converges at a linear rate, making it computationally efficient for large-scale networks.

Key Results

  • Superior Accuracy: In synthetic tests, the Adaptive Merging (AM) approach consistently outperformed standard methods like Higher-Order SVD (HOSVD) and fixed-interval merging. In some sparse scenarios, the error rate for AM was orders of magnitude lower than spectral competitors.
  • Historical Realism: When applied to the MID (international conflict) dataset, the model's adaptive merging didn't just produce numbers—it produced history. The algorithm automatically identified six distinct periods that align with major global events:
  • Pre-WWI
    • The Interwar Period
    • WWII
    • The Cold War
    • The 1990s (Post-Cold War)
    • The 21st Century
  • Predictive Edge: On the MID dataset, the AM method achieved a testing error of 0.739, significantly better than the 1.160 achieved by traditional spectral methods (HOSVD).

Limitations and Future Work

While the framework is robust, the authors note a few areas for growth:

  • Constant Baseline: The current model assumes a constant baseline intensity ($\lambda_0$) for edges. In reality, the "global" rate of interaction might fluctuate due to external shocks (like a global pandemic or economic crash).
  • Covariates: The model currently relies purely on the network topology. The authors suggest that incorporating node-specific metadata (like a country's GDP or a user's age) could further improve estimation.
  • Complex Processes: The model uses a Poisson process, which assumes events are independent. Future iterations could explore Hawkes processes, where one event (like a tweet) increases the probability of a subsequent event (a retweet).

Summary updated

Abstract

Longitudinal network consists of a sequence of temporal edges among multiple nodes, where the temporal edges are observed in real time. It has become ubiquitous with the rise of online social platform and e-commerce, but largely under-investigated in literature. In this paper, we propose an efficient estimation framework for longitudinal network, leveraging strengths of adaptive network merging, tensor decomposition and point process. It merges neighboring sparse networks so as to enlarge the number of observed edges and reduce estimation variance, whereas the estimation bias introduced by network merging is controlled by exploiting local temporal structures for adaptive network neighborhood. A projected gradient descent algorithm is proposed to facilitate estimation, where the upper bound of the estimation error in each iteration is established. A thorough analysis is conducted to quantify the asymptotic behavior of the proposed method, which shows that it can significantly reduce the estimation error and also provides guideline for network merging under various scenarios. We further demonstrate the advantage of the proposed method through extensive numerical experiments on synthetic datasets and a militarized interstate dispute dataset.
BibTeX
@misc{zhang2022efficient,
  author = {Haoran Zhang and Junhui Wang},
  title = {{Efficient Estimation for Longitudinal Networks via Adaptive Merging}},
  year = {2022},
  eprint = {2211.07866},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.07866},
}

Loading related content...

Figure