Research map / Graph learning / Graph algorithms and clustering

AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Neural combinatorial optimization on graphs · 0 citations (OpenAlex)

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 AT-SKM-Net, which accelerates the T-SKM-Net hard-constraint projection layer via a heterogeneous GNN active-set predictor guiding hybrid sampling and a Cholesky-update equality projection, reporting up to 7.29x SKM-layer speedup with zero constraint violations.

Problem

Projection-based hard-constraint enforcement for graph-structured linear-constrained optimization is expensive under dynamic topology changes, since equality projection requires SVD recomputation and inequality SKM iterations sample uniformly over many mostly-inactive constraints.

Approach

Combine a topology-aware heterogeneous GNN that predicts active-constraint scores (used for hybrid sampling in SKM iterations) and a warm-start, with an incremental Cholesky update (rank-1 update plus downdate) plus null-space rotation to replace SVD recomputation when topology changes by low-rank perturbations.

Key results

• AT-SKM-AC achieves 7.29x SKM-layer speedup over T-SKM-Net on the IEEE 300-bus system and 2.95x on the 118-bus system, with zero constraint violations on unseen topologies.
• Active-set prediction (AT-SKM-A) reduces mean inequality iterations by 80%, 55%, and 85% on the 57-, 118-, and 300-bus systems.
• On the gas transport problem, AT-SKM reduces SKM time from 3.15 ms to 0.90 ms (3.50x) while keeping zero violations.

Surprising findings

• Cholesky update alone does not change inequality iteration counts yet gives 3.22x SKM speedup on the 300-bus system, and the combined speedup is super-linear relative to the product of individual gains.
• Sequential Cholesky updates are highly unstable in fp32 on original formulation (e.g., 86-98% failure rates on N-1/N-2 for 57-bus), which adaptive rescaling removes.

Limitations

• Theoretical O(N^2) complexity relies on low-rank perturbations; large-scale timings show memory-bound deviation (empirical exponent 2.28 for N up to 5000).
• Assumptions for the efficiency theorem (local active-set stability, predictor coverage) are idealized and not verified in general.
• Experiments run on a single Apple M4 chip with limited problem sizes.

Experimental setup

Datasets: random geometric graphs IEEE 57-bus IEEE 118-bus IEEE 300-bus GasLib-135

Benchmarks: N-1 SC DC-OPF (IEEE 57/118/300-bus) minimum-cost gas transport (GasLib-135) random geometric graph equality projection

Metrics: total time (ms) inequality iteration count SKM speedup optimality gap (%) max equality violation max inequality violation

Baselines: PyPower NN HGNN DC3 T-SKM-Net

Builds on: T-SKM-Net Sampling Kaczmarz-Motzkin DC3 PyPower Greedy Kaczmarz

Closest papers by meaning

• ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.88)
• Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.85)
• On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.85)
• How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.85)
• Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.85)
• Enforcing convex constraints in Graph Neural Networks (NeurIPS 2025 · similarity 0.85)