Research map / Learning theory and algorithms / Sample complexity
Learning the Behavior of a Dynamical System Via a “20 Questions” Approach
Abhijin Adiga, Chris Kuhlman, Madhav Marathe, Ravi S. S., Daniel Rosenkrantz, Richard Stearns
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase number of random queries per degree class from l=2 to l=10 | Method 2 randomized query sets · 50 sampled sets per network | number of complete query sets out of 50: 0 -> 5 to 50 complete sets | Improved |
| apply compaction algorithm to randomized complete sets | Method 2 · real-world networks | query set size: 80% reduction | Improved |
| apply compaction algorithm to coloring-based sets | Method 1 · real-world networks | query set size | No clear effect |
| use randomized plus compaction instead of G2 coloring | Method 2 vs Method 1 · real-world networks | query set size: 1.5 to 2 times that of Method 1 | Hurt |
| use adaptive greedy instead of batch coloring | Method 3 vs Method 1 · FB | query set size: 225 -> 53 | Improved |
| use adaptive greedy instead of batch coloring | Method 3 vs Method 1 · Enron | query set size: 1385 -> 624 | Improved |
| use adaptive greedy instead of batch coloring | Method 3 vs Method 1 · Clique | query set size: 1001 -> 8 | Improved |
| widen threshold range theta from 0 to 1 | Method 3 · random k-regular graphs | number of queries | Hurt |
| widen threshold range theta | Method 3 · real-world networks | number of queries: less than 1.5Δ | Hurt |
| set uniform fixed threshold near Δ/2 versus near 0 or Δ | Method 3 · random k-regular graphs | number of queries: maximum around Δ/2 | Mixed |
| increase graph degree k | Method 3 · random k-regular graphs | number of queries | Hurt |
| increase graph density with limited threshold range | Method 3 · dense networks | number of queries | Improved |
Closest papers by meaning
- Learning the Topology and Behavior of Discrete Dynamical Systems (AAAI 2024 · similarity 0.88)
- A Graph Dynamics Prior for Relational Inference (AAAI 2024 · similarity 0.85)
- Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks (ICML 2024 · similarity 0.85)
- Benchmarking Structural Inference Methods for Interacting Dynamical Systems with Synthetic Data (NeurIPS 2024 · similarity 0.84)
- Interpretable Relational Inference with LLM-Guided Symbolic Dynamics Modeling (NeurIPS 2026 · similarity 0.84)
- DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs (NeurIPS 2025 · similarity 0.83)
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.
