Research map / Bandits and online learning / Online convex optimization and games
Incremental Topological Ordering and Cycle Detection with Predictions
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.
Proposes learning-augmented data structures (Learned DFS Ordering and Ideal Learned Ordering) for incremental topological ordering and cycle detection, using per-vertex ancestor/descendant edge count predictions, with theoretical bounds and experiments on SNAP temporal graphs.
Problem
Maintaining a topological ordering and detecting cycles under incremental edge insertions in a directed graph is expensive in the worst case, while simple greedy heuristics are fast in practice but can be slow in the worst case.
Approach
Coarse-grained predictions of each vertex's number of ancestor and descendant edges in the final graph warm-start level-based (BFGT/BK-style) incremental ordering, giving consistent, robust and smooth running-time guarantees in terms of prediction error eta.
Key results
- LDFS with 5% training data processes up to 36x fewer vertices and edges than baselines on real temporal data, with a 3.1x runtime speedup on the reported setting.
- With 50% training data, cost improvements reach up to a factor of 116 over baselines.
- Theoretically, Ideal Learned Ordering runs in expected total time O~(min{n*eta, m*eta^{1/3}, n^2}), and LDFS in O(m*eta + n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| warm-start DFS levels with predictions from 5% training data instead of zero predictions | LDFS · Email-Eu-core test (last 50%) | cost (nodes and edges processed): 5.0e+5 -> 8.4e+3 | Helped |
| warm-start DFS levels with predictions from 5% training data instead of zero predictions | LDFS · CollegeMsg test (last 50%) | cost (nodes and edges processed): 1.2e+5 -> 9.6e+3 | Helped |
| warm-start DFS levels with predictions from 5% training data instead of zero predictions | LDFS · Math Overflow test (last 50%) | cost (nodes and edges processed): 2.8e+5 -> 4.4e+4 | Helped |
| warm-start DFS levels with predictions from 50% rather than 5% training data | LDFS · Email-Eu-core test (last 50%) | cost (nodes and edges processed): 8.4e+3 -> 2.6e+3 | Helped |
| warm-start DFS levels with predictions from 50% rather than 5% training data | LDFS · CollegeMsg test (last 50%) | cost (nodes and edges processed): 9.6e+3 -> 5.4e+3 | Helped |
| warm-start DFS levels with predictions from 50% rather than 5% training data | LDFS · Math Overflow test (last 50%) | cost (nodes and edges processed): 4.4e+4 -> 2.8e+4 | Helped |
| warm-start DFS levels with predictions from 5% training data instead of zero predictions | LDFS · Email-Eu-core test (last 50%) | runtime (s): 0.274 -> 0.071 | Helped |
| warm-start DFS levels with predictions from 5% training data instead of zero predictions | LDFS · CollegeMsg test (last 50%) | runtime (s): 0.101 -> 0.021 | Helped |
| warm-start DFS levels with predictions from 5% training data instead of zero predictions | LDFS · Math Overflow test (last 50%) | runtime (s): 0.241 -> 0.094 | Helped |
| add noise to the predictions | LDFS · email-Eu-core robustness experiment | cost (nodes and edges processed) | Hurt |
| add noise to the predictions | LDFS · synthetic DAGs, high edge density and high perturbation | cost (nodes and edges processed) | Hurt |
Surprising findings
- On very dense synthetic DAGs with large added prediction noise, LDFS can become slower than the DFS II baseline.
Limitations
- Theoretical guarantees for the ideal algorithm depend on the sparse/dense and error-parameter analysis and rely on known BK/BFGT subroutines.
- Experiments are limited to three sparse temporal networks and synthetic DAGs with n=1000.
- No nontrivial lower bounds are known for either problem, so the optimality of the bounds is not established.
Experimental setup
Datasets: email-Eu-core CollegeMsg Math Overflow
Benchmarks: email-Eu-core CollegeMsg Math Overflow
Metrics: total cost (nodes and edges processed) running time (s)
Baselines: DFS I DFS II BFGT BK
Builds on: BFGT algorithm BK algorithm (Bender et al. sparse incremental topological ordering) DFS-based incremental topological ordering (DFS II)
Closest papers by meaning
- TMetaNet: Topological Meta-Learning Framework for Dynamic Link Prediction (ICML 2025 · similarity 0.86)
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (AAAI 2025 · similarity 0.86)
- TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration (ICML 2025 · similarity 0.86)
- Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity (ICLR 2025 · similarity 0.86)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.85)
- Analytical Construction on Geometric Architectures: Transitioning from Static to Temporal Link Prediction (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.