Source-linked AI summary
AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs
Xiaochen Zhang, Haoyu Zhu, Yao Zhang, Qingchun Hou
TL;DR
Graph-structured optimization must satisfy strict linear constraints at scale and adapt to changing topologies, while existing projection-based methods face computational costs. AT-SKM-Net combines active-set-guided sampling with incremental Cholesky updates. The paper reports fewer iterations and faster SKM layers while maintaining zero constraint violations.
Problem
Large graph problems require strict feasibility under topology changes, while projection-based methods face costly constraint processing and matrix refactorization.
Source: §1 · pp. 1–2Method
AT-SKM-Net combines topology-aware active-set prediction and hybrid sampling with Cholesky updates for low-rank changes in equality constraints.
Source: §1 · p. 2, §4 · p. 4, §4.3 · p. 6Results
AT-SKM-Net reports zero constraint violations; AT-SKM-A reduces average iteration counts by 80%, 55%, and 85% on the 57-, 118-, and 300-bus systems, respectively.
Source: §1 · p. 2, §5.2 · p. 9Takeaways & Limitations
The framework addresses the trade-off between strict feasibility and real-time scalability in graph-structured optimization with dynamic environments.
Source: §6 · p. 9The theoretical analysis assumes local active-set stability and a predicted candidate set that covers the true active set while remaining much smaller than all constraints.
Source: §4.2 · p. 5
Abstract
from arXiv · showhide
Graph-structured optimization with linear constraints is fundamental to critical infrastructure but faces scalability limits due to massive strict hard constraints and high dimensionality. While recent projection-based methods such as Trainable Sampling Kaczmarz-Motzkin Net (T-SKM-Net) guarantee feasibility, they face high computational costs in dynamic environments by processing the entire constraint set and requiring expensive matrix factorizations. To bridge this gap, we propose the Accelerated Trainable-SKM (AT-SKM) Net framework. To concentrate computation on the active constraints and eliminate redundant calculations, we introduce a hybrid sampling strategy guided by a topology-aware heterogeneous GNN model. To efficiently handle topological shifts in graph-based constraints, we employ a Cholesky Update mechanism that theoretically reduces the equality projection complexity from O(N^3) to O(N^2) under low-rank perturbations. Experiments on random geometric graphs, N-1 Security-Constrained DC-OPF, and minimum-cost gas transport problem demonstrate that AT-SKM reduces iteration counts by up to 85% and achieves 2.95x-7.29x SKM layer speedups, while maintaining zero constraint violations.
1 Introduction
Graph-constrained infrastructure optimization must satisfy strict constraints despite large networks and changing topology, but scalable, fast solutions remain difficult. AT-SKM-Net targets these challenges by combining trainable hard-feasibility correction with structure-aware acceleration.
1 Introduction
- Large graph optimization must meet strict physical or operational constraints as topology changes, while traditional methods struggle to produce feasible solutions within milliseconds.The motivating examples include power-system dispatch and transportation-network flow control.Source: §1 · pp. 1–2
- Neural solvers lack inherent feasibility guarantees, while hard-constraint methods can require costly embedded optimization that limits scalability to graphs with thousands of nodes.Penalty-based soft constraints lack theoretical safety guarantees in the described safety-critical setting.Source: §1 · pp. 1–2
- T-SKM-Net guarantees linear hard-constraint satisfaction, but SVD-based equality projection and uniform sampling of mostly inactive constraints can waste computation.Topology changes require expensive recomputation, and only a few constraints are typically active.Source: §1 · p. 2
- AT-SKM-Net combines graph-aware hard-feasibility correction with accelerations for large constraints and topology changes.Its design uses the low-rank topology perturbations and sparse active constraints of graph-based problems.Source: §1 · p. 2
2 Related Work
Related work addresses hard-constraint neural solvers, SKM acceleration, and active-set prediction. The paper positions AT-SKM-Net against methods whose feasibility scope, computational cost, or handling of changing constraints differs from its target.
2 Related Work
- The related literature spans neural hard-constraint satisfaction, SKM acceleration, and active-set prediction.The paper organizes its review around these three streams.Source: §2 · p. 2
2.1 Neural Methods for Hard Constraint Satisfaction
- Hard-constraint neural methods include embedded optimization, feasible-set parameterization, and correction or projection; their stated limits include scalability, restrictive assumptions, or incomplete guarantees.T-SKM-Net [15] enforces equality and inequality constraints through null-space projection and SKM, but SVD and uniform sampling limit efficiency.Source: §2.1 · pp. 2–3
2.2 Acceleration Methods for SKM
- Greedy Kaczmarz [24] scans all rows per iteration, block SKM [25] requires tuning, and PASKM retains uniform sampling.These approaches address convergence or parallelism without resolving the sampling inefficiency described for SKM.Source: §2.2 · p. 3
2.3 Application of Active-Set Prediction
- Active-set prediction has been applied to Lasso and constrained optimization, but cited approaches may incur reduced-system overhead or assume an unchanged constraint system.Other cited work predicts active sets for warm-starting conventional solvers [30].Source: §2.3 · p. 3
3 Preliminaries
The preliminaries formulate graph-based optimization as minimizing an objective subject to linear equalities and inequalities. The SKM setup first enforces equalities, then updates within their null space to reduce inequality violations.
3 Preliminaries
- The problem uses a graph-dependent objective and state vector subject to linear equality and inequality constraints.The matrices depend on graph G, while b and d define the inequality and equality right-hand sides.Source: §3 · p. 3
- SKM first projects an initial guess onto the equality-constraint hyperplane, then represents equality-feasible iterates using a basis for null(C).The representation is x = xeq + Nω.Source: §3 · p. 3
- SKM samples inequality constraints and updates null-space coefficients to progressively reduce violations while maintaining Cxk = d.The hinge operator measures positive violations, and the step size α lies in (0, 2).Source: §3 · p. 3
4 Accelerated Trainable-SKM Framework
AT-SKM-Net processes an updated graph with an HGNN, projects its warm-start candidate onto the equality manifold, and applies null-space SKM to address remaining inequality violations. Its design combines active-set-guided sampling and incremental Cholesky updates with topology-aware prediction.
4.1 Accelerated Sampling for SKM Iteration: Active-Set Prediction
- The sampling strategy targets sparse active constraints, shifting convergence dependence from the full constraint count and global Hoffman constant toward the predicted-set size and local conditioning.The predicted set is assumed to cover the true active set while remaining much smaller than the full set.Source: §4.1 · p. 4, §4.2 · pp. 5–6
4.1.1 Hybrid Sampling Strategy via Predicted Active-sets
- The hybrid strategy combines prediction-guided sampling of likely active constraints with uniform exploration to retain global convergence robustness.The learned component uses predicted active scores; the uniform component guards against missed active constraints.Source: §4.1.1 · pp. 4–5
4.2 Theoretical Analysis
- Under the stated active-set stability and covering assumptions, the analysis gives global linear convergence in expectation when ρ < 1 and quantifies local acceleration.The local analysis attributes gains to sampling-space compression and conditioning by the true active set.Source: §4.2 · pp. 5–6
4.3 Accelerated Computing for Equality Projection: Cholesky Update
- Low-rank topology changes are handled by rank-1 Cholesky updates and downdates, reducing equality-projection complexity from O(N^3) to O(N^2).The framework also reuses the previous null-space basis and corrects the affected low-dimensional subspace.Source: §4.3 · p. 6
4.4 Topology-Aware Heterogeneous Graph Neural Network for Active-Set Prediction
- The topology-aware HGNN supplies warm-start candidates and active-set scores to guide the accelerated solver.Its architecture is designed to estimate heterogeneous constraint activity across varying topologies.Source: §4.4 · p. 7, §4.4.3 · p. 7
4.4.1 Heterogeneous Graph Representation
- The heterogeneous bipartite representation treats graph nodes and edges as distinct entities, preserving edge-coupling representations instead of absorbing them into nodal states.This addresses the smoothing of edge-specific information associated with homogeneous message passing.Source: §4.4.1 · p. 7
4.4.2 Static-Dynamic Feature Separation
- Structure-aware normalization conditions affine parameters on dynamic hidden features and static physical features to limit dilution of topology information.The inputs are concatenated before graph convolution generates the normalization parameters.Source: §4.4.2 · p. 7
4.4.3 Output Heads
- The HGNN output heads predict a primal-variable warm start and active scores for node and edge constraints, which are normalized into the sampling distribution.The regression head predicts x̂0; the classification head produces constraint activity scores.Source: §4.4.3 · p. 7
5 Experiments
Experiments evaluate AT-SKM on random geometric graphs and N-1 security-constrained DC-OPF, with additional gas-transport validation in the appendix. Results report faster projection and fewer iterations while retaining constraint satisfaction.
5 Experiments
- The evaluation covers RGGs and N-1 SC DC-OPF, with additional minimum-cost gas-transport validation in Appendix C.Experiments were conducted on an Apple M4 chip.Source: §5 · p. 8
5.1 Equality Projection on Random Geometric Graphs
- At approximately 2,000 RGG nodes, SVD takes seconds, while Cholesky updates run in about 10^-2 seconds.The measured SVD runtime follows O(N^3) scaling, while the update runtime aligns with O(N^2).Source: §5.1 · p. 8, Figure 2 · p. 8
5.2 N-1 Security-Constrained DC Optimal Power Flow
- The OPF tests use IEEE 57-, 118-, and 300-bus systems, training on only a subset of feasible N-1 contingencies to assess generalization to unseen topologies.Testing measures cost optimization and constraint satisfaction on seen and unseen topologies.Source: §5.2 · p. 8
- AT-SKM speeds up T-SKM-Net across all tested system sizes while satisfying equality and inequality constraints without compromising solution quality.Table 1 compares methods across seen and unseen scenarios; its SKM-related metrics use unseen scenarios.Source: §5.2 · p. 8, Table 1 · p. 9
- NN and HGNN show constraint violations, NN generalizes poorly to unseen topologies, and DC3 leaves inequality violations despite satisfying equalities.The authors characterize the unconstrained baselines as unsafe for real-world operations.Source: §5.2 · p. 9
- AT-SKM-A reduces average inequality iterations by 80%, 55%, and 85% on the 57-, 118-, and 300-bus systems, respectively.The authors attribute the reduction to hybrid sampling focused on the sparse active-constraint subset.Source: §5.2 · p. 9
- On the 300-bus system, AT-SKM-C reduces SKM runtime from 8.99 ms to 2.79 ms (3.22×), while AT-SKM-A yields a 1.14× speedup despite reducing iterations by 85%.The authors report that the bottleneck shifts from iterative search to linear-algebra operations at large scale.Source: §5.2 · p. 9
- On the 300-bus system, combined AT-SKM-AC achieves 7.29× speedup, exceeding the product of the individual speedups, 1.14× and 3.22×.On the 57-bus system, the combined 4.00× speedup approximately matches 2.35× multiplied by 1.77×.Source: §5.2 · p. 9
6 Conclusion
The conclusion presents AT-SKM as addressing the trade-off between strict feasibility and real-time scalability in dynamic graph optimization. Its inference flow combines a predictor, equality projection, and null-space inequality iterations.
6 Conclusion
- AT-SKM combines neural active-set prediction with incremental Cholesky updates to address computational bottlenecks in T-SKM-Net for dynamic environments.The conclusion frames this as addressing the trade-off between strict feasibility and real-time scalability.Source: §6 · p. 9
A.1 AT-SKM-Net Algorithm Flow
- The algorithm takes constraint data and a predictor, then initializes a candidate solution and sampling probabilities from the predictor's scores.The procedure requires batch size, mixing ratio, and a maximum iteration count, and returns a feasible solution.Source: §A.1 · p. 13
- After equality projection, the algorithm iterates over sampled constraints in the null space and returns the equality-projected solution plus the final null-space update.Each batch combines active-set-weighted samples and uniform samples.Source: §A.1 · p. 13
A.2 Accelerated Sampling by Active-Set Prediction
Active-set prediction guides SKM sampling, while a hybrid uniform component preserves global convergence in expectation. For low-rank topology changes, Cholesky updates maintain projection and null-space computations with quadratic complexity.
A.2 Accelerated Sampling by Active-Set Prediction
- With mixing ratio ρ < 1, the algorithm maintains global linear convergence in expectation toward the feasible set.The uniform component of each batch has at least one sample, supporting the convergence argument.Source: §A.2 · p. 13
- The hybrid sampler combines predicted-set samples with a uniform subset, retaining a global convergence argument while focusing computation on likely active constraints.The proof's local-regime analysis assumes active-set stability and compares contraction rates for uniform sampling over all constraints versus the predicted set.Source: §A.2 · pp. 13–15
- Under α = 1 and finite Hoffman constant H(Ã), the null-space iteration converges linearly in expectation.The analyzed iterate uses the feasible set defined by Ãω ≤ b̃.Source: §A.2 · pp. 13–14
B.1 Implementation Details of the Cholesky Update
- Low-rank perturbations let the Cholesky update reuse factors while maintaining the projection operator and null-space basis.The implementation applies rank-1 update and downdate operations to obtain the updated factor without explicitly reconstructing the perturbed Gram matrix.Source: §B.1 · p. 15
B.2 Complexity Analysis
- Factor maintenance costs O(n_eq^2), projection costs O(n_eq · n), and null-space updating costs O(n · r) plus O(n_eq · n).Here n_eq is the number of equality constraints and r is the null-space dimension.Source: §B.2 · p. 16
- Because n_eq and r are bounded by n, the framework has O(n^2) overall complexity, a theoretical speedup of order n over SVD-based methods.The comparison baseline requires a complete SVD factorization with O(n^3) complexity.Source: §B.2 · p. 16
B.3 Detailed Analysis for Results on RGGs
On random geometric graphs, Cholesky Update outperforms SVD, with the advantage widening at larger scales. Adaptive rescaling improves sequential-update stability across tested precisions and contingency levels.
B.3 Detailed Analysis for Results on RGGs
- 7.36× to 23.35× speedups favor Cholesky Update over SVD for 100–1000-node graphs, with empirical exponents O(n1.46) and O(n1.99), respectively.These empirical growth rates are below theoretical bounds, which the authors attribute to linear-algebra library optimizations for smaller matrices.Source: §B.3 · p. 16, Table 2 · p. 17
- Over 168 times acceleration at 5000 nodes accompanies Cholesky Update's near-quadratic exponent of 2.28, versus SVD's supercubic fitted exponent of 3.49.The reported memory-bound operations can push observed scaling above the ideal quadratic rate.Source: §B.3 · pp. 16–17
B.4 Numerical Stability under Higher-Rank Contingencies
- Adaptive rescaling balances Cholesky update and downdate vector magnitudes while preserving the exact low-rank perturbation.On IEEE 300-bus, the largest intermediate magnitude falls from roughly 1010 to roughly 105.Source: §B.4 · p. 17
- Adaptive rescaling removes all observed fp64 failures across tested systems and contingency levels; under fp32, failures remain only on the 300-bus system.The evaluation covers N-1 and N-2 contingencies and a subset of N-3 contingencies on IEEE 57-, 118-, and 300-bus systems.Source: §B.4 · p. 17, Table 3 · p. 18
C Minimum-Cost Gas Transport Problem
The gas-transport evaluation tests minimum-cost flow under varying demand and topology scenarios, while the DC-OPF formulation models preventive generation dispatch across outage cases. On gas transport, AT-SKM-Net preserves zero violations while reducing SKM computation time relative to T-SKM-Net.
C Minimum-Cost Gas Transport Problem
- The GasLib-135 evaluation varies demand and network topology and tests generalization across seen and unseen operating scenarios.The task minimizes flow-allocation cost subject to nodal balance and edge-capacity constraints.Source: C Minimum-Cost Gas Transport Problem · p. 18
- HGNN-only prediction has small mean optimality gaps but substantial worst-case equality and inequality violations, especially on unseen gas-transport scenarios.The authors conclude direct neural prediction alone is insufficient for safety-critical constrained optimization.Source: C Minimum-Cost Gas Transport Problem · p. 18, Table 4 · p. 18
- 3.50× acceleration reduces total SKM computation time from 3.15 ms to 0.90 ms on gas transport, while both methods retain zero equality and inequality violations on seen and unseen scenarios.AT-SKM-Net also reduces equality projection time from 2.19 ms to 0.53 ms and inequality iteration time from 0.96 ms to 0.37 ms.Source: Table 5 · p. 18, C Minimum-Cost Gas Transport Problem · p. 19
D.1 Mathematical Formulation of N-1 Security-Constrained DC-OPF
- N-1 DC-OPF minimizes operating costs with preventive generation shared across scenarios and system states adapted to each topology.The cases include normal operation and single-line outages; active lines and neighboring buses vary by scenario.Source: §D.1 · p. 19
D.2 N-1 Security-Constrainted DC-OPF Dataset Generation
The appendix details the screened N-1 DC-OPF dataset and training setup, then tests hybrid sampling sensitivity and breaks down AT-SKM-Net runtimes. The runtime comparison reports acceleration in both equality projection and inequality iteration.
D.2 N-1 Security-Constrainted DC-OPF Dataset Generation
- The N-1 dataset uses IEEE 57-, 118-, and 300-bus systems and retains only outages with connected post-contingency topology and a feasible converged OPF solution.Table 6 summarizes system sizes and the counts of valid contingencies after screening.Source: §D.2 · p. 19, Table 6 · p. 20
D.3 Experimental Hyperparameters and Loss Function Configuration
- Training uses a two-layer HGNN with 128 hidden dimensions, Adam at 5e−4, and batch sizes of 64 for training and 1 for testing.The test batch size is intended to simulate real-time inference on individual samples.Source: §D.3 · p. 20
- Training combines pre- and post-projection MSE with focal active-set classification, a linear loss warmup, 1% slack labels, and sampling of about 10% of constraints per iteration.The focal loss uses γ = 2.0 and α = 0.5; active labels are used only to train the predictor.Source: §D.3 · p. 20
D.4 Hyperparameter Sensitivity of Hybrid Sampling Strategy
- With a perfect active-set predictor, hybrid sampling stays stable across sampling ratios on IEEE 118 and sharply improves IEEE 300 convergence with minimal random sampling.On IEEE 300, the reported worst-case performance requires about one-tenth the sampling effort of uniform full-set scanning.Source: Figure 3 · p. 21, §D.4 · p. 21
D.5 Detailed Time Breakdown for AT-SKM-Net on SC DC-OPF Problems
- AT-SKM-Net achieves total SKM speedups of 4.04×, 2.81×, and 9.53×, while equality projection speedup rises from 3.11× to 10.92× across 57–300 buses.Inequality iteration time is reduced by 6.83×, 2.11×, and 6.46× on the 57-, 118-, and 300-bus systems, respectively.Source: Table 7 · p. 21, §D.5 · p. 22
D.6 Robustness under High-Load Operating Conditions
Under heavier loads, AT-SKM-Net retains acceleration across the tested systems. The appendix also evaluates active-set prediction quality and shows that missing true active constraints is more damaging than adding inactive ones.
D.6 Robustness under High-Load Operating Conditions
- Under [1.0, 1.2] load perturbations, AT-SKM-Net achieves total SKM speedups of 3.61×, 2.74×, and 7.81× on the 57-, 118-, and 300-bus systems.Equality projection speedup rises from 2.33× on the 57-bus system to 9.93× on the 300-bus system; mean inequality iterations fall to 2.75, 9.21, and 5.34, respectively.Source: Table 8 · p. 22, §D.6 · p. 22
D.7 Active-Set Prediction Quality
- HGNN active-set recall exceeds 98% across systems, precision ranges from 96.5% to 99.9%, and seen/unseen scenario performance has a negligible gap.The authors identify recall as the key metric because missing a binding constraint can stall convergence.Source: Table 9 · p. 22, §D.7 · p. 23
D.8 Robustness to Active-Set Perturbations
- Dropping true active constraints generally harms convergence more than adding inactive ones, while AT-SKM-Net remains robust to mild prediction errors.On IEEE 118, dropping 0.5 of the true active set raises mean iterations from 15.68 to 29.61; adding inactive constraints at ratio 3.0 raises it to 19.12. A dropped constraint is left to the uniform sampling branch, whereas added constraints dilute guided sampling.Source: §D.8 · pp. 23–24
D.9 Transfer Learning and Pseudo-Label Active-Set Training
The appendix tests transfer to larger systems with active-set heads trained from pseudo labels rather than solver-derived labels. This approach retains total SKM speedups of 3.33× and 7.26× in the two transfer settings.
D.9 Transfer Learning and Pseudo-Label Active-Set Training
- The transfer procedure freezes the shared HGNN backbone and warm-start branch, then retrains only active-set heads using 5% of target N-1 scenarios and model-generated pseudo labels.The labels come from constraints active in the model’s corrected SKM outputs.Source: §D.9 · pp. 24–25
- With pseudo-label training, total SKM speedup is 3.33× for 57→118 transfer and 7.26× for 118→300 transfer, with comparable optimality gaps to T-SKM-Net.Mean inequality iterations decrease from 57.31 to 29.28 for 57→118 and from 30.83 to 6.30 for 118→300.Source: Table 12 · p. 25, §D.9 · p. 25
- The results support solver-generated labels as a training choice rather than a fundamental requirement, with pseudo-label transfer retaining acceleration and strict feasibility.The framework’s warm-start and active-set components can be trained or adapted with weaker supervision.Source: §D.9 · pp. 24–25