Research map / Graph learning / Knowledge and temporal graphs
Learning Changes in Graphon Attachment Network Models
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.
Introduces Graphon Attachment Network Models (GAN-M) for growing networks with time-evolving graphon attachment probabilities and a WESUM change-point statistic on subgraph counts, with theoretical consistency guarantees and simulations plus an email-Eu-core real-data example.
Problem
Detecting and localizing structural change points in evolving networks whose attachment graphons change over time, where cumulative growth and strong dependence across time break classical CUSUM assumptions.
Approach
Shows that expected subgraph counts in GAN-M are piecewise polynomial in time, and builds WESUM, a CUSUM-type statistic with weights orthogonal to polynomial trends, applied to subgraph counts with seeded intervals and distillation for multiple change-point detection.
Key results
- Theorem 3.1 gives P(K-hat = K, max localization error <= epsilon) >= 1 - C2 T^-1 under an SNR condition on jump magnitude and spacing.
- In simulations over 100 repetitions, detection works across degree-heterogeneous, SBM and RDPG settings; e.g., Scenario 3 with (C1,C2)=(0.12,0.04) gives normalized Hausdorff 0.26e-2 and ARI 1.00 for the triangle subgraph.
- On email-Eu-core, triangles detect change points at nodes 432 and 795, while line segments detect three at 166, 422, and 759.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Decrease α, increasing the jump magnitude | WESUM · Simulation Scenario 1 | change-point estimation accuracy | Helped |
| Increase the signal level | WESUM · Simulation Scenarios 3 and 4 | estimation accuracy | Helped |
| Use larger subgraphs | WESUM · Simulation Scenarios 3 and 4 | estimation accuracy | Hurt |
| Use smaller subgraphs, such as triangles | WESUM · Simulation studies | change-point detection accuracy | Helped |
Surprising findings
- Smaller subgraphs (e.g., triangles, line segments) give better detection bounds and faster convergence, while larger subgraphs converge more slowly.
Limitations
- Theory requires bounded number of nodes entering per time step and a signal-to-noise condition on jump magnitude and spacing.
- Choice of optimal subgraph is left for future exploration.
Experimental setup
Datasets: email-Eu-core network (Paranjape et al., 2017) simulated GAN-M networks
Benchmarks: simulated GAN-M scenarios 1-4 email-Eu-core
Metrics: difference in number of change-points normalized Hausdorff distance Averaged Rand Index
Baselines: classical CUSUM
Builds on: CUSUM graphon models preferential attachment random interval distillation (Fan & Wu 2024) seeded intervals (Kovács et al. 2023)
Closest papers by meaning
- Transfer Learning on Edge Connecting Probability Estimation Under Graphon Model (NeurIPS 2025 · similarity 0.87)
- A Few Moments Please: Scalable Graphon Learning via Moment Matching (NeurIPS 2025 · similarity 0.85)
- Low-Rank Graphon Learning for Networks (NeurIPS 2025 · similarity 0.85)
- Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective (ICML 2024 · similarity 0.85)
- Flowette: Flow Matching with Graphette Priors for Graph Generation (NeurIPS 2026 · similarity 0.85)
- Beyond Message Passing: Neural Graph Pattern Machine (ICML 2025 · similarity 0.85)
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.