Autoregressive networks with dependent edges

1. Problem Statement

Dynamic network modeling is crucial for understanding evolving systems (e.g., social interactions, biological networks). A significant challenge in this field is modeling dependent edges. In real-world networks, the formation or dissolution of an edge between two nodes often depends not only on the history of that specific edge but also on the states of other edges (e.g., transitivity, reciprocity, degree heterogeneity).

Existing approaches face limitations:

• Standard AR models: Often assume edge-wise independence between snapshots, failing to capture complex dependencies like transitivity.
• TERGMs (Temporal Exponential Random Graph Models): While flexible, they often suffer from degeneracy issues, computational intractability for large networks, and a lack of rigorous high-dimensional asymptotic theory, especially when the number of nodes ($p$) grows with the sample size ($n$).
• Latent variable models: Induce dependence implicitly, making it difficult to configure specific structural features like transitivity explicitly.

The paper addresses the need for a framework that explicitly models dependent edges in discrete-time dynamic networks, accommodates high-dimensional settings ($p \to \infty$), and provides rigorous statistical inference without relying on strict stationarity assumptions.

2. Methodology

2.1 Model Framework: Dependent-Edge AR(m)

The authors propose a class of Dependent-Edge Autoregressive (dep. edge AR) models.

• Definition: The network process $\{X_t\}$ is an $m$-th order Markov chain. Conditioned on the past $m$ snapshots ($X_{t-1}, \dots, X_{t-m}$), the edges $X_{t,ij}$ are mutually independent.
• Transition Probabilities: The probability of an edge forming ($X_{t,ij}=1$ given $X_{t-1,ij}=0$) or dissolving ($X_{t,ij}=0$ given $X_{t-1,ij}=1$) is modeled explicitly as a function of:
  1. The history of the specific edge.
  2. The history of other edges in the network (capturing dependencies like transitivity).
• Formulation:
  $$\alpha_{t-1, ij} = P(X_{t,ij}=1 | \text{past}) = f_{ij}(\cdot; \theta)$$
  $$\beta_{t-1, ij} = P(X_{t,ij}=0 | \text{past}) = g_{ij}(\cdot; \theta)$$
  where $\theta$ is a parameter vector containing both global parameters (affecting all edges, e.g., transitivity strength) and local parameters (node-specific, e.g., heterogeneity in forming/dissolving edges).

2.2 Specific Models Proposed

The framework is instantiated with three models capturing key network features:

1. Degree Heterogeneity Model: Captures "rich-get-richer" effects where high-degree nodes are more likely to form new edges.
2. Persistence Model: Models the tendency for edge states (connected or disconnected) to remain unchanged over multiple time steps (AR(3)).
3. Transitivity Model: Explicitly models the "friend of a friend" effect, where the probability of an edge forming depends on the number of common neighbors ($U_{t-1, ij}$) and disjoint neighbors ($V_{t-1, ij}$).

2.3 Estimation Procedure

Due to the high dimensionality (number of local parameters scales with $p$), standard Maximum Likelihood Estimation (MLE) suffers from slow convergence rates. The authors propose a two-stage estimation strategy:

1. Initial Estimation (Partial Likelihood):

   • Parameters are split into Global ($\theta_G$) and Local ($\theta_{G^c}$).
   • Global parameters are estimated by maximizing the full log-likelihood.
   • Local parameters are estimated by maximizing partial log-likelihoods that isolate specific components, mitigating the impact of the high-dimensional nuisance parameters.
   • Result: Consistent estimators, but with slow convergence rates ($O_p(n^{-1/4}p^{1/4})$).

2. Improved Estimation (Projected Score):

   • To achieve faster convergence, the authors employ a projection strategy (inspired by Chang et al., 2021, 2023).
   • The score function for a target parameter is projected onto a direction that minimizes the influence of the nuisance parameters (the rest of the vector).
   • This involves solving a linear programming problem to find the projection vector $\hat{\phi}_l$.
   • The final estimator $\hat{\theta}$ is obtained by solving the projected score equation.
   • Result: The improved estimator achieves a faster convergence rate of $O_p(n^{-1/2}p^{-1})$ for global parameters and $O_p((np)^{-1/2})$ for local parameters.

2.4 Asymptotic Theory

• Martingale Structure: The authors construct a martingale difference sequence based on the conditional independence assumption, allowing for asymptotic analysis without assuming stationarity of the network process.
• Limiting Distribution: The improved estimator is shown to be asymptotically normal (or a mixture of normals) under general conditions. If the process satisfies mixing conditions, the limiting distribution is strictly normal.
• High-Dimensional Consistency: The theory holds even when $p$ diverges with $n$ (specifically $p \ll n^\delta$), a regime where standard ergodicity arguments fail.

3. Key Contributions

1. Novel Modeling Framework: Introduction of the dep. edge AR class, which explicitly allows for dependence between edges across time and within snapshots (conditional on history), bridging the gap between simple AR models and complex TERGMs.
2. High-Dimensional Inference: Development of a rigorous asymptotic theory for dynamic networks where the number of nodes grows with the sample size, overcoming the lack of stationarity in such settings.
3. Efficient Estimation Algorithm: Proposing a projected score method that significantly improves the convergence rate of MLEs in high-dimensional network settings, making inference feasible for large networks.
4. Software Implementation: The authors provide an open-source R package (arnetworks) implementing the estimation and inference procedures.

4. Results

4.1 Simulation Studies

• Accuracy: Simulations on the transitivity model demonstrate that the improved estimator significantly outperforms the initial estimator in terms of Mean Absolute Error (MAE). For example, the error for global parameters dropped from ~1.2 to ~0.05 in specific settings.
• Coverage: The 95% confidence intervals constructed using the derived asymptotic distribution achieve coverage probabilities close to the nominal level (approx. 95%).
• Scalability: The method remains effective even for large networks ($p=500$) and varying sample sizes.

4.2 Real Data Analysis: Email Interactions

• Dataset: Email exchanges in a Polish manufacturing company (106 nodes, 39 weekly snapshots).
• Findings:
  • Transitivity: Strong evidence of transitivity; edges are more likely to form between nodes with common neighbors.
  • Heterogeneity: Significant node-level heterogeneity. Managers (higher in the hierarchy) showed a higher propensity to form new edges compared to non-managers.
  • Model Fit: The proposed Transitivity AR model achieved the lowest BIC (Bayesian Information Criterion) compared to competing models (Global AR, Edgewise AR, Edgewise Mean), indicating a superior balance of fit and complexity.
  • Forecasting: In link prediction tasks (ROC curves), the Transitivity AR model performed competitively, dominating simpler models and showing that capturing edge dependence improves forecasting accuracy.

5. Significance

This paper represents a significant advancement in the statistical analysis of dynamic networks:

• Theoretical Rigor: It provides the first formal high-dimensional asymptotic analysis for a flexible class of discrete-time dynamic network models that do not require stationarity.
• Practical Utility: By explicitly modeling dependencies like transitivity and degree heterogeneity, the framework offers a more realistic representation of social and biological systems than independent-edge models.
• Computational Feasibility: The proposed projection-based estimation makes it possible to perform rigorous statistical inference on large-scale dynamic networks, a task previously hindered by computational complexity and slow convergence of standard estimators.
• Bridge to Existing Literature: It clarifies the relationship between AR models and TERGMs, showing that conditionally independent TERGMs are a special case of the proposed framework, while offering a more tractable estimation path.

In summary, the paper offers a robust, theoretically grounded, and computationally efficient framework for modeling and inferring complex dynamic networks with dependent edges.