Research map / Learning theory and algorithms / Matrix and tensor methods
Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that iterative proportional fitting (Sinkhorn) recovers maximum likelihood estimates of a biproportional Poisson network model for inferring dynamic networks from marginals, derives error bounds, and introduces ConvIPF to guarantee convergence with minimal edge additions.
Problem
Inferring a dynamic network's time-step adjacency matrices from time-varying row/column marginals and a time-aggregated adjacency matrix, where IPF is used empirically but lacks statistical grounding and often fails to converge on sparse data.
Approach
Identify a Poisson generative network model (biproportional Poisson) whose log-likelihood equals the negative IPF dual objective, so IPF solutions are its MLEs; add structure-dependent error bounds via the Fiedler eigenvalue and a ConvIPF algorithm that adds few edges to guarantee convergence.
Key results
- On synthetic data from the correctly specified model, IPF estimates have average cosine similarity 0.911 to the true hourly network.
- On Citibike data with month-aggregated network, IPF improves cosine similarity over the doubly constrained gravity model by 78%.
- On SafeGraph at 2AM March 2, 2020, ConvIPF adds only 2 edges versus about 10 million edges for the epsilon-replacement baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the time-aggregated network as IPF's initial matrix instead of a distance matrix | IPF for CitiBike hourly network inference · CitiBike hourly networks (month-aggregated network) | cosine similarity: 78% improvement | Helped |
| Add the time-aggregated network (ablation) | IPF for CitiBike hourly network inference · CitiBike hourly networks (month-aggregated network) | cosine similarity: 214% | Helped |
| Add the column marginals q⁽ᵗ⁾ (ablation) | IPF for CitiBike hourly network inference · CitiBike hourly networks (month-aggregated network) | cosine similarity: around 31% | Helped |
| Add the row marginals p⁽ᵗ⁾ (ablation) | IPF for CitiBike hourly network inference · CitiBike hourly networks (month-aggregated network) | cosine similarity: around 31% | Helped |
| Use a finer temporal granularity for the time-aggregated network | IPF for CitiBike hourly network inference · CitiBike hourly networks | cosine similarity | Helped |
| Replace the Poisson data-generating distribution with an exponential distribution | IPF network inference · Synthetic exponential-distribution data | cosine similarity: 0.911 -> 0.855 | Hurt |
| Replace the Poisson data-generating distribution with a negative binomial distribution (γ = 0.5) | IPF network inference · Synthetic negative-binomial data | cosine similarity: 0.911 -> 0.843 | Hurt |
| Minimize the number of added edges rather than replacing all zeros with ε | ConvIPF · SafeGraph, 2AM on March 2, 2020 | new edges: 10012193 -> 2 | Helped |
| Minimize the change in λ₁ rather than replacing all zeros with ε | ConvIPF · SafeGraph, 2AM on March 2, 2020 | change in λ₁: 30.04 -> 5.60 \cdot 10^{-9} | Helped |
Surprising findings
- IPF's estimation error of the underlying parameters grows quickly with sparsity even though the marginals are matched exactly in all cases.
- Replacing all zeros with a small epsilon adds over 10 million edges on SafeGraph, drastically altering network structure.
Limitations
- Model is Poisson and biproportional, assuming no time-varying row-column interactions; misspecification only partly tested.
- Error bounds depend on sparsity and the Fiedler eigenvalue, degrading as the network becomes disconnected or sparse.
- Stationarity assumption for joint inference only approximately holds on real data.
Experimental setup
Datasets: SafeGraph mobility data (Richmond metro) Citibike NYC bikeshare data synthetic data from biproportional Poisson model
Benchmarks: SafeGraph Richmond mobility Citibike hourly ground-truth networks
Metrics: cosine similarity l2 error of parameters number of added edges change in lambda_1 IPF iterations
Baselines: gravity model doubly constrained gravity model ablation without time-aggregated network epsilon replacement of zeros
Builds on: iterative proportional fitting Sinkhorn's algorithm Poisson regression collective graphical models
Closest papers by meaning
- Variational Inference for sparse network reconstruction from count data (ICML 2019 · similarity 0.87)
- A Generic Family of Graphical Models: Diversity, Efficiency, and Heterogeneity (ICML 2025 · similarity 0.86)
- Dynamic Network Model from Partial Observations (NeurIPS 2018 · similarity 0.86)
- Multiresolution Analysis and Statistical Thresholding on Dynamic Networks (NeurIPS 2025 · similarity 0.84)
- Graph Structure Inference with BAM: Neural Dependency Processing via Bilinear Attention (NeurIPS 2024 · similarity 0.84)
- Generating Hypotheses of Dynamic Causal Graphs in Neuroscience: Leveraging Generative Factor Models of Observed Time Series (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.