Hephaestus: Mixture Generative Modeling with Energy Guidance for Large-scale QoS Degradation
Authors: Nguyen Hoang Khoi Do
Bach Ngo
Youval Kashuv
Canh V. Pham
Hanghang Tong
My T. Thai
Venue: NeurIPS 2025 poster ()
Keywords: Combinatorial Optimization
Reinforcement learning
Generative AI
Primary area: optimization
TL;DR: We propose Hephaestus, a generative self-reinforcing framework for solving the QoSD problem on large networks with nonlinear edge-weight functions, outperforming prior combinatorial and ML-based methods

Abstract: We study the Quality of Service Degradation (QoSD) problem, in which an adversary perturbs edge weights to degrade network performance. This setting arises in both network infrastructures and distributed ML systems, where communication quality, not just connectivity, determines functionality. While classical methods rely on combinatorial optimization, and recent ML approaches address only restricted linear variants with small-size networks, no prior model directly tackles the QoSD problem under nonlinear edge-weight functions. This work proposes Hephaestus, a self-reinforcing generative framework that synthesizes feasible solutions in latent space, to fill this gap. Our method includes three phases: (1) Forge: a Predictive Path-Stressing (PPS) algorithm that uses graph learning and approximation to produce feasible solutions with performance guarantee, (2) Morph: a new theoretically grounded training paradigm for Mixture of Conditional VAEs guided by an energy-based model to capture solution feature distributions, and (3) Refine: a reinforcement learning agent that explores this space to generate progressively near-optimal solutions using our designed differentiable reward function. Experiments on both synthetic and real-world networks show that our approach consistently outperforms classical and ML baselines, particularly in scenarios with nonlinear cost functions where traditional methods fail to generalize.

Hephaestus: Mixture Generative Modeling with Energy Guidance for Large-scale QoS Degradation
Nguyen Do lit Bach Ngo2:t, Youval Kashuv', Canh Pham Hanghang Tong", My Thail
University of Florida, FL, USA "The Frazer School, FL. USA
$ORLab, Phenikaa University, Viet Nam University of Illinois at Urbana-Champann IL, USA Equal contribution
*Correspondence to: mythai cise.ufl.edu
Abstract
We study the Quality of Service Degradation (QoSD) problem, in which an adver- sary perturbs edge weights degrade network performance. This setting arises both network infrastructures and distributed ML systems, where communication quality, not just connectivity, determines functionality, While classical methods rely on combinatorial optimization, and recent ML approaches address only re- stricted linear variants with small-size networks, no prior model directly tackles the QoSD problem under nonlinear edge-weight functions. This work proposes Hephaestus, a reiffreinn generative framework that synthesizes feasible solutions in latent space, to fill this gap. Our method includes three phases: (1) Forge: a Predictive Path-Stressing (PPS) algorithm that uses graph learning and ap- proximation to produce feasible solutions with performance guarantee, (2) Morph: a new theoretically grounded training paradigm for Mixture of Conditional VAEs guided by an energy-based model capture solution feature distributions, and (3) Refine: a reinforcement learning agent that explores this space to generate progres- sively near-optimal solutions using designed differentiable reward function. Experiments on both synthetic and real-world networks show that our approach consistently outperforms classical and ML baselines, particularly scenarios with nonlinear cost functions where traditional methods fail to generalize.
Introduction
We consider the problem of degrading path-based system performance through minimal, stealthy perturbations over a set weighted connections. Formally, let a directed graph G = (V, with [V] n nodes and |E| m edges, represent system of interacting components, where each i-th edge is associated with non-decreasing weight function fi No + R+ A perturbation x = (x1, .2...., ,..,...,m Im) ) E EI used to increase edge weights where the new i-th edge weight becomes fi (x,) Vi [m]. We also refer to x as the budget allocated increase the weight of edge e to (x.)). Given a set of critical source-target pairs XC = {($1, (()1,tz),... f....... fx)], maximum perturbation budgets (box constraints) b (01, be...., bm)) N and threshold T E R++, the goal to find the lowest-cost perturbation x such that every shortest path between (s,, f.) E K. exceeds T.
We formulate this problem, also called Quality of Service Degradation (QoSD) [ as the following constrained optimization:
min |x||1 KENW
subject to:
SP (s,, 2 (8,t))K
0 5 x; < b,, x; E E Vi e [m]
where SPa(s,t;X) = Emer, fe(x.) denotes the length of the shortest path م.,z from to t, under perturbation x. QoSD is NP-complete problem
[ Note that the total path cost in SPa(s, is
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

determined by the edge functions fi(z;), rather than directly by 24. Although I2 E z U ({}}. D the problem is not an Integer Program (IP) in general, since the cost functions f((x;) may be nonlinear (e.g., quadratic convex or log-concave). Intuitively, the QoSD problem seeks perturbation x that "stress" global system paths beyond their functional thresholds, not merely their connectivity, while remaining subtle at the local level.
This problem arises in many real-world systems, from networked infrastructures to machine learning, where performance depends not just on connectivity but on effective communication. In blockchain, for example, transactions must reach all miners promptly to maintain consensus; targeted delays can disrupt synchronization and increase the risk of forks [2 3 4 [3]. The same story applies to traffic control systems [ 6 7 8 9. where attackers can manipulate signal timing to induce congestion and delay key routes. In Graph Neural Networks (GNN) (10] In, stealthy perturbing edge weights or node features can distort message passing and harm predictive performance. all these settings, (i) the system functionality is compromised, regardless of its connectivity, making all state of the art (SOTA) methods focusing on structural failures ineffective; and (ii) attacks are stealthily distributed across the network, making local defenses ineffective. These characteristics make QoSD natural and general framework for modeling such vulnerabilities.
Despite its compact formulation, this problem presents several challenges: First, the objective is non-submodular and becomes more complex under nonlinear edge functions such as quadratic or log- concave costs, making greedy or relaxation- based methods ineffective. Second, feasibility checking expensive: every update to x requires recomputing global shortest paths for all pairs in KCaa bottleneck for large graphs or many constraints. Third, the solution space is exponentially large as the number of perturbation vectors grows exponentially with the number of edges, making the search for quality solutions intractable. These challenges limit the applicability of classical optimization and learning methods, thus calling for scalable alternatives capable of handling a large number of path-based constraints with complex edge dynamics.
To address these challenges, we propose Hephaeatus, three-phase Forge-Morph-Refiee generative framework for solving QoSD at scale under both linear and nonlinear edge functions. The framework begins with Forge, generating diverse feasible solutions using our shortest-path attention- based Predictive Path aath-Stressing (PPS) algorithm, which efficiently approximates global path constraints and addresses both scalability and feasibility checking. We next employ Morph, a mixture-of mixxure-off-eenraaiiee experts model guided by an Energy- thergy-Baseed Model (EBM), which allows deterministic expert expansion to approximate arbitrarily complex multimodal distributions over combinatorial solution spaces. Finally at Refine, a reinforcement learner refines the generated candidates in the latent space using differentiable reward function, enabling smooth and efficient optimization. As a result, for any unseen graph that shares structural characteristics with those observed during training, the RL agent can quickly select appropriate latent variables and decode them into high-quality colutions-effecttvvnn addressing the challenge of intractability over large combinatorial spaces.
Overall, our key contributions are summarized as follows:
We propose Hephaestus, the first end-to-end, generative self-reinforcing framework for QoSD that unifies feasibility search, solution modeling, and optimization into a scalable pipeline capable of handling non-linear costs and large path constraints.
Theoretically, we provide (i) an approximation guarantee for PPS. a corner stone of Forge, that bounds the cost of the generated solutions relative to the optimum, (ii) convergence analysis for Emergy--aased Model guided mixture training that avoids intractable normalizing constants for Morph, and (iii) proof that policy refinement in the latent space be directly performed via gradient ascent, enabling near-optimal solution tuning in Refine with RI.
Extensive experiments on both synthetic and real-world networks demonstrate that Hephaestus consistently outperforms classical and ML baselines. Ablation studies further validate the complementary role of each phase in improving overall performance, especially under nonlinear cost regimes where traditional methods fail to generalize.
2 Related Work
Network Interdiction. The QoSD problem was first introduced by Nguyen and Thai [0. It models a novel form of soft network interdiction, where attackers degrade end-to-end performance by increasing edge weights without explicitly disrupting topological connectivity. This contrasts sharply

---

with classical hard interdiction [12 13 14 2]. which assume complete removal of nodes or edges to disrupt flow or connectivity under budget constraints. These classical settings are less realistic in stealthy or infrastruuture-ccontttaann
environments. Until recently, Stackelherg routing games under logit-based attacker response models [15] adopt a bounded-rational view of adversaries and optimize defender strategies probabilistically over sensitive nodes. While conceptually related to soft disruption, these models differ significantly from QoSD: they focus on node-based protection, rely on attacker stochasticity, and do not generalize to continuous edge-based disruptions.
proposed three approximation algo- rithms-Adaptic Adaptive Trading (AT), Iterative Greedy (IG), and Sampling Algorithm the QoSD problem. These methods support both linear and nonlinear fc but guarantee performance only in the linear case and treat tource-targtt pairs independently, leading to less efficient budget spending. In contrast, Hephaestus leverages PPS algorithm with guarantees for both settings. This foundation enables the training of self-reinforcing generative model that captures structural correlations across source-target pairs, resulting in more globally effective degradation strategies.
Possible Solving Methods. Nguyen and Thai
solving
On the other hand, QoSD can be reformulated as an ILP in the special case when weight function f-) linear, making recent ML techniques for integer and mixed-integer linear programs (ILPs/MILPs)
16
17
18 19
applicable to this setting. One direction integrates ML into solver heuristics 20
21 such as branching [23] separation 24
25
and cut selection [26] 27 Another focuses on
learning to generate heuristic solutions [28
29
30
31
32 33] Notably, the Predict-and-Searce (PS)
framework [4 35] leverages solvers such as Gurobi [36] or SCIP B77 to generate label solutions
during training. At inference time, it predicts initial solutions, which are then refined using the same solvers, following the peddec-then-optimnzg paradigm 38 39 40 In contrast, DiffIL.O 41 relaxes ILPs into differentiable surrogate objectives and optimizing them end-to-end via gradient descent, enabling unsupervised training without solver-generated labels, but only works effectively with small to medium ILP. Hephaestus fundamentally differs from these approaches by directly handling both linear and non-linear weight functions-includee quadratie-convex and log-concave-wihhnne relying on solvers, allowing it to scale to large graphs with many constraints.
Hephaestus
Forg
SPAGAN
Predictive Path Stressing
Top solutions with highest reward
POrTUR
Histure of C-VEE Exparts
Morph
-~ (z
Refine
Ener gy Based Model
Reinforcenee Reisforcemntt esming
Gating Network
EN
DE
SPAGAN Reward Model
SPAGAN Reward Model
EN
DE
Figure 1: Given graph dataset, we train SPAGAN predict shortest path costs and guide PPS to generate feasible solutions across varying thresholds, forming Pretrained Solution Dataset. Then, an EBM approximates the underlying solution distribution, while a Mix-CVAE learns closely match this distribution. Once the MiX-CVAE converges, an RL agent modifies latent samples, which are decoded into lower-cost solutions. The top-k high-reward samples are added back the Solution Dataset to retrain both the EBM and Mix- Mix-CVAE in future episodes, enabling continual improvement.
We present our Hephaestus framework, illustrated in Figure I which consists of three phases: Feasible Solution Generation, (2) Morph: Energy- Guided Generative Modeling, and Latent Policy Optimization. In Forge, we use SPAGAN 42] to estimate shortest-pan -ath costs and guide our Predictive Path Stressing (PPS) algorithm, which generates feasible solutions (or perturbations) to QoSD and forms a pre-trained solution set Doo The Morph phase trains an Energy-Ban Based Model (EBM) 43 on sool for guiding a Mixture-of-Condifee
(1) Forge:
(3) Refine:
VAEs (Mix- CVAE) to approximate the underlying solution feature distribution. To improve coverage, new

---

experts are dynamically added in regions of EBM where Mix-CVAF shows high modeling error. In the final phase Refine, reinforcement learning agent operates the latent space of Mix-CVAE to refine latent variables and synthesize better solutions. These new samples are iteratively added back into D allowing both EBM and MiX-CVAE to improve over time.
CVAE 45 46
47
3.1 Forge: Feasible Solution Generation
Training a strong generative model in Morph requires a high-qualing dataset of feasible solutions x, as the model can only lear to produce effective solutions if the training data itself covers wide range of valid perturbations with low budgets. However, generating such data is challenging: for each pair (s, f), the QoSD objective is often non-submodular and the number of feasible paths having cost shorter than T can be extremely large, making it computationally expensive to enumerate or verify them all. To tackle this challenge, we design hybrid Ml-approximationn algorithm that leverages trained shortest-path attention model to guide the approximation search. We begin with dataset of graphs Drraph = {G, (V,, =,)] representing diverse sampled network topologies. For each G,, we define a collection of target node pairs K; = {(s;, t from which shortest path estimations will be drawn. To this end, we train a Shortest Path Graph Attention Network (SPAGAN) 42 denoted by Te: (G, s, t, x) + de,e. where 8o takes as input a graph G = (V, E) and a source-targer pair (s, t), and outputs real-valued estimate du,, E R of the shortest-path distance between and under baseline weight function fe- The model 8o trained using a supervised regression loss (i.e Huber Loss 48, 44] over mini-batches of path distances from subgraphs, where ground truth distances are obtained via exact computation (i.e Dijkstra algorithm [50]). By training over a diverse set of subgraphs extracted from the graph, the model learns transferable embeddings that capture structural priors and efficiently generalize to large graphs, enabling solution verification in unseen instances.
Once So is trained, we use it to guide the search for diverse solutions x. Specifically, we pro- pose PPS algorithm to iteratively search adversarial perturbations that elevate the predicted path length (x) of each pair (s, beyond a given threshold T. Unlike traditional approx- imation methods [ that require costly repeated computation of exact paths, PPS leverages the efficiency of So to estimate marginal gains in violation potential and guides the pertur- bation accordingly. Let P denote the current set of shortest paths under perturbation x, i.e., P = (pr.. (s, t) E IC, Bo(G, s, x;x) < TT where Bo(G, s, x) R Legsa, fe( returns the predicted shortest path length under x, if 3e is well trained. To quantify the progress of x, we define the potential function C(P,x) x) Epnter min (T, (G, s,t, x)). Each iteration of PPS selects an edge e E & and an increment Ate E that maximizes the predicted gain-to-cost ratio:
C(P,x+ 1.) C(P,x)
Ac arg max EEE, AE(1,b,
(2)
A
where 1, is the standard basis vector corresponding to edge e, and b, is the upper budget bound for that edge. After determining (c", A*), perturbation is updated via x < x A -ee, and the path set P iss recomputed via Ge. This process repeated until almost all node pairs (s,t) KC are predicted to have path lengths exceeding the target threshold, i.c., C(P.x) 2 |P|T E, where E is an input parameter. For each graph G2 ~ Daroph, the PPS algorithm is executed independently across a set of QoS thresholds T (Ti .T...... TM and pairs K- (KI,..., KM), }. producing a corresponding set of feasible perturbations (x [ E K, K.TEE E T). The resulting pretrained solution dataset is thus formalized as 0o = [[G 1, IGG E Deraph K. E K, T' E T which forms the basis of the Morph phase (Section p.2p. For notational simplicity, we refer each element of Deol training instance (G, K, T, x), representing a specific degradation scenario and having a guarantee:
Theorem 1. (PPS Ratio) Let h [ ///uiin 1. where Wmin min E We. Assume that the set E is chosen from E such that Pr(E* C E = a, where E" is the set of edges of the optimal solution and E (0, 1) is a constant. Given a parameter ē >> then running PPS on E yields a solution such (Proof in Appx B.
that C(P,x) > |P[T - and EE [[[[[]]]] S (1 + +h hl((n) + In In In(11)))(PTT
Theorem ensures that every solution generated by PPS achieves a provably bounded cost relative to the optimum. Such quality assurance is critical: the generative model introduced in Morph will be trained purely on Foo, thus its quality directly determines the generative capacity and generalization performance. Without such theoretical grounding, the learned latent distribution could diverge or collapse around suboptimal patterns.

---

3.2 Morph: Energy-Guided Generative Modeling
Given the pre-trained solution set Dool from the Forge phase, Morph aims to model the underlying pattern of high-quality solutions through the conditional distribution p(x c), where the condition [G, K) encodes the graph, the set of critical node pairs. and the threshold context. Since the true distribution is unknown, we approximate it using conditional generative model Q(x e) that can generate feasible solutions for an arbitrary [G,K, T" instance. To achieve this, we implement $2 as Mixture of Conditional VAEs (Mix-CVAEs), denoted Ω = [Ma.... ..... ,22x], ). where each expert Ω2 consists of an encoder Pv and a decoder Ma. For given training pair (x, c), the encoder produces a latent posterior (z x, c), and the decoder reconstructs the input via P& (x z, c), forming the mapping S2 (x, c) = (P (x, c)) = MM o Pa.. We train each CVAE expert by maximizing the evidence lower bound (ELBO) [6 on samples (G, K., T, x) ~ Dool:
CELBO_ = Egg log z, c) gL (z) x, c) (l c)] C..
where the first term encourages accurate reconstruction of x, and the second regularizes the latent representation z E Rdd to align with a context-aware prior. After training, new solutions can be generated by sampling z ~ (z(z | c) and decoding via X = MM (z,
Since optimizing the ELBO is merely an indirect way to minimize the reverse KI. divergence, this objective often encourages the learned distribution Pa | <) to focus on the dominant modes that appear most frequently in the dataset (x,). However, if p(x) is truly multimodal [51] a single expert S2 can exhibit mode-seeking behavior -.ee, it may ignore rare but critical regions of p(x c). More severely, we do not even know which regions of p are not being
Mode-Seeking Problem.
captured by the CVAE Qi since the true form of is unknown.
Energy-Based Guidance for Generative Modeling. To address the above limitation, introduce an Energy-Based Model (EBM) [44) defined as (x) = 1 exp (-E(x)/T), where E(x) is a learnable energy function, 0 is temperature parameter controlling the sharpness of the distribution and the normalizing constant function Z = fx exp (- F((x)/T) dx ensures q(x) is a valid probability distribution. Unlike CVAR, EBM makes no strong parametric assumptions about the form of the true distribution p(x): instead, it defines a flexible energy landscape shaped directly by the energy values. We thus employ an EBM (xx) as a surrogate for the true but unknown- distribution p(x), and aim to learn y by minimizing mingeQ KL (p(x) || q(x)). where Q denotes the feasible family of EBMs parameterized by Exx). Simultaneously, we train the generative model [2x) (e.g.. Mix-CVAEs) to match ((x) by minimizing the KL divergence minnee KL (g(x) || [(x)), where & represents the feasible set of generative distributions realizable by our model class. Ideally, when the two KL divergences become zero, then p(z)= = (zx) = M(x),, or indirectly [2(x)= = =p(z).
However, single C-VAE may only capture dominant mode of the distribution g(x) as mentioned earlier. To ensure comprehensive coverage, we monitor the density gap between the EBM and the current generative model via the log-ratio function x(x) log (x)) ((xx)) Whenever x(x) > 8 for some threshold 6 > O, we interpret this region as underrepresented by the current C- model Q and dynamically add a new C-VAE expert f2 (x) specialized to this region, forming a new Mixture of C-VAE Ω This expert is integrated into the mixture through a gating mechanism, ensuring that the overall generative model incrementally improves its coverage of high-density regions in g(x), and thereby indirectly approximates the true data distribution p(x) (See Figure
ptx)
p(x)
p(x)
q(x)
(x))
(x)
(x)
(x)
(X())
Step
Step 2
Step
Figure 2: At each iteration, the generative model Q(x) adds expert in regions where the log-ratio (x) = log (n(x)/[(x)) exceeds 6, thereby covering more of q(x). Meanwhile, ((x) adapts to align with p(z). As the steps progress, q(x) increasingly approximates p(z), and M(z), augmented by new experts, converges to q(x), ultimately yielding p(x) Rs q(x)= z Q(x).
Theorem 2. (Expert Augmentation Efficiency): Suppose there exists constant e >> such that Pp(x) (x(x) 0} 2 e; the region {a: x(x) > 6), new expert QN (2)) is added with gating
5

---

weight a(x) = 1(((x) > 87a0 (0 do a < 1) and trained to satisfy 2 (z) 2 cq(x) (((x)oo for
some e E (0. 1): then the updated mixture (x) a(xx) +1) (1 azx) [x) satisfies
KT[G])(')) I (T]]]12) (6, s), where 7 c) ao(6 + log c) 6o > 0 and 6o > 0 is a lower bound on |x(m)>6 (())dr. (Proff Appendix B.2)
From Theorem we observe that each time new expert is added, (L(g)((2)) is reduced by at least ((,,) relative to the previous (L]] Since the initial KL divergence with only one expert is finite, repeatedly augmenting the mixture with new experts allows us. in the limit of infinitely many
experts without sacrificing the computational cost [53 [4], to drive the (T]( to zero on Dool
However, directly computing (TT.p(())]l (x)) and (T(g(x) [[(()))((((()))) is highly challenging in practice, as it requires evaluating the normalization constant of the EBM. Estimating typically involves
Markov Chain Monte Carlo (MCMC) (55), which becomes extremely expansive during the EBM training. Fortunately, as we will show next, there is no need to compute Z.
Theorem 3. (Normalization Free Function) The objective function min, maxa (KT.(pllg) (I)()))gg) is normalizing free and is independent of Z. (Proof in Appendix B.3)
Per Theorem completely avoid the need compute Z by reformulating the problem minimax objective, where the normalizing constant cancels out in the difference of KI. divergences:
min max (MLxx(LL(llg)) (L()))))
QEQ DEE
Any terms involving log Z appear in both (T((plg) and (l]()2])), and hence exactly cancel each other out. This cancellation frees us from having to perform expensive MCMC estimates of Z, yet still allows the EBM to guide the generative model Ω effectively.
Minimax Optimization. From Equation 4 the EBM is optimized by minimizing the difference between the expected energy under the data distribution and the expected energy under the Mix-
E (x)] (minimax derivation Appendix B.3). To stabilize training and ensure that energy values remain bounded, we incorporate a commonly-
CVAE model distribution ming Ex(())
[ [x)]
used regularization term [43 based on the squared energies 7 (Exts)]Eexx))) + Engo) [Eg [x)()) ( where 7 > 0 is a regularization coefficient. For a Mix-CVAE approximating an EBM, we modify the standard ELBO incorporate EBM guidance during expert training. Specifically, based on Equation we define guided objective Cn Cquide CELBO + > -Epg(t))) (ps (x z, c))) where
C. the added term term penalizes low-quality samples in high-energy (i.e., low-density) regions under the energy- based model 4s (x) x exp(-Ex(x)
3.3 Refine: Latent Policy Optimization
Once the Mix-CVAE Ω has successfully captured the true solution distribution, similar inputs (consisting of x, G, Kc, and T') that lead to similar-quality solutions are mapped nearby points in the continuous latent space. This property makes the search and optimization process more efficient. In Refine, we train an RL agent with a policy π to blend and explore that latent space, aiming to generate solutions that are better than those in the original pretrained dataset Dand These newly discovered solutions are then added back into sol reinforcing their feature patterns and making easier to retrain the generative model in future iterations. The optimization of policy π over the latent
def (S. T. R). This includes (i) finite sets of states S, (ii) finite set of actions A, (iii) transition distribution I' (s' s,a) where s, s' E S, a E AA and (iv) a reward function R: : S x A + R. We specify each component as follows:
space is formulated as a Markov Decision Process (MDP) (56), M
State (s E E): A state is defined by latent representations = (zi, c) for =; = Pe (x;, c) and X; E Daol, where 2; E ddd is the latent vector produced by the encoder Ps from the input data x,.
Action (a E A): An action a; = (14, o,) is vector of two components: 14 E Rdd (predicted mean) and 0; E Rdd (predicted scale). The modification vector 5, = a; Cnoise + H4. where Enoise (0, I), and the latent vector updated as 2. = 2; + 6z.
Transition Dynamics (T): When an action a; = (Hi σ,)) is taken, a new state 8;41 = (21+1:)) where 21+1 2,, is then formed.
Reward Function (R): Given 2i+1, the decoder Ma decodes into solution š;41 = {x1,-. ......... Tmh To make optimization smoother, apply soft transformation to each element: ã, = log(1 + e²))

---

where 2, E & to produce a smooth vector X,+1. Moreover, instead of using a binary feasibility label (feasible or not) for each pair (s, E S. we define a smooth total feasibility score over all pairs:
F(G,K,
Σ 1+ expepp= (3o(G, s, ro)nd((++))) -T))
(5)
(e,))EK
Here, for each pair (s, { controls how sharply the score changes near the threshold T. If the predicted path cost slightly exceeds T. the sigmoid quickly pushes the score closer to 1. This formulation ensures that (G, S, &;+1) provides continuous and differentiable reward signal, which is more suitable for optimizing the RL policy. Finally, our reward function is defined as:
R(x++1) F (G, K. &1+1) x log(1 + || ll2).
(6)
This reward formulation balances two objectives: the first term encourages the generation of solution vectors by pushing the predicted path cost above T,, while the second term, weighted by x, penalizes excessive budget usage, thus promoting stealth and cost-effectiveness. We intentionally keep the cost penalty relatively small so that the RL agent focuses primarily on finding a valid solution (i.e, only increasing weights) before optimizing cost. In what follows, we show several properties of our dense reward function which make the RL training process much easier.
Lemma (Differentiable Reward Function) Let Bo XX + E. be differentiable on an open set X' C IRm. The reward function R(x) is differentiable on X. (Proof in Appendix B.4)
Theorem 4. (Reward Estimation Consistency) Assume that Qi has converged properly, for any perturbed latent vector 2, == 2; + E V R(Mg (2.,,) c)) with small ē > O we have R (x;) > R (x,). where x = -Ma(s,,)) c). (Proof in Appendix B.5)
Specifically, by Theorem 4 small perturbations in the latent code 2; following the gradient of the reward, yield strictly higher returns. Since the reward R(xx is differentiable (Lemma []. we can perform gradient ascent [57] directly in latent space as in Equation (6] Concretely, starting from 2;, we iterate & f- 23 ē V R(Ma(z, c)) until convergence to 2 leading to next state 8(+1 = (Z++1= 2/. e). The resulting latent offise 8, & 2; together with o; defines a feasible action a; = (6,, o,). This warm-start procedure mitigates inefficient random exploration in the early stages and accelerates convergence by guiding policy π towards locally optimal regions. Once the model reaches sufficient reward levels, we allow it to autonomously explore and exploit the latent space using standard reinforcement learning frameworks, leveraging efficient exploration strategies See Appendices A and C for the full algorithm and its analysis.
from the RI. literature 58 59 60].
Inference Process. Given a new instance problem, policy iteratively modifies random latent vector 2 in latent space to maximize the reward defined in Equation [ However, it is not guaranteed that the decoded solution & from Ma(z) is valid. To address this, we introduce feasibility refinement algorithm called PPS-I, a variant of the PPS algorithm. Unlike PPS, which relies on the learned estimator x-) for the approximation of the shortest path, PPS-I replaces it with the exact calculation of the shortest path using Dijkstra's 's algorithm to ensure 100% fcasibility. This yields 1 in the ratio stated in Theorem I Moreover, with a strong Mix-CVAE Ω the initial solution & produced by ι is often close to valid, significantly minimizing the refinement overhead of PPS-I. Implementation details and analysis of PPS-I are provided in Appendix A4.
4 Experiments
Settings. We evaluate the effectiveness and scalability of Hephaestus on synthetic and real-world networks under varying QoSD thresholds. For synthetic graphs, we generate Rrdös-Rényi topologies with n = 1024 nodes, varying edge density I, fixed threshold T = 20, and [K] = 10 critical pairs. Real-world datasets include Email [61]. Gnutella (62). RoadCA (63), and Skitter (64), covering diverse scales and domains. For each, we sample 50 critical pairs, compute their maximum bascline shortest-path length, and set T' to 140%-260% of this value to normalize degradation difficulty across topologies. Dataset statistics are in Appendix C.1. For training the entire Hephaestus framework in both synthetic and real networks, we generate a large corpus of graphs with varying architectures (e.g.. Barabási- -abber, Rényi, and "atts-Strogatz) as well as diverse edge densities and thresholds, while keeping the number of nodes consistent with those in the testing graphs.
Baselines. We compare Hephaestus with range of baselines, including classical approximation methods and learning-base IP solvers. Approximation baselines include Adaptive Trading (AT),
7

---

Iterative Greedy (IG), and Sampling Algorithm (SA) from M. which offer varying trade-off's between cost-effectiveness, concavity handling, and scalability. For learning- bearning-based IP methods, we evaluate three SOTA methods for ILP: DIFFILO O [41], Predict-and-Sent
34 and L-MIL POPT [25] which combine neural predictors with IIP solvers like Gurobi. Baseline solutions are refined using Gurohi with 3000s timeout-tripled tripled from the original setup. For large networks (e.g.. RoadCA, Skitter), we extend this to 6000s and enable 'MIPFocus=1' [41 665 [66] with heuristics to prioritize feasibility. This setup is crucial, as exact solving often leads to long runtime memory errors in large networks. In constrast, our method employs PPS-I to ensure 100% feasible refinement without relying on exact solvers, while still achieving significantly faster performance due to its approximate nature. Note that we excluded a diffusion-basee generative solver (e.g.. the Gurobi Gurobi-guided diffusion model [67]) due to its scalability issues in large-scale constrained combinatorial optimization problems, particularly over graphs with millions of nodes. In particular, this approach requires costly iterative sampling using series of VAE models, with 100 denoising steps for Denoising Diffusion Implicit Model (DDIM) (68) and 1000 steps for Denoising Diffusion Probabilistic Model (DDPM) [69]. making them computationally impractical to evaluate in large-scale setups such RoadCA or Skitter.
Edge Weight Function Settings. We evaluate methods under three types of fe(x) representing different degradation dynamics: (i) Linear: fxx = N(x),, modeling uniform delay per unit cost; (ii) Quadratic Convex: fe(x)= = N(z"), capturing congestion effects with rapidly increasing cost; and (iii) Log Concave: [a = N(In æ:), modeling diminishing returns as error-rate degradation. ML-based IP solvers operate only under linear functions,
compare all methods in this setting, including the exact solver. For convex and concave settings, only the approximation methods and Hephaestus are applicable. Notably, Gurobi fails on the Log Concave case due to the non-convex feasible region induced by logarithmic constraints, and is excluded from that evaluation.
24
2
Pachg Sovar
20
Dangva Caedy
Sampl Apaicon
0'6
15
Dansity
Denccty
(a) Linear
(b) Quadratic Convex
(c) Log Concave
Figure 3: Our solution quality on the testing synthetic graph with varying density is evaluated under Linear, Quadratic Convex, and Log- Coneave functions. ML-based ILPs compared with the best best-performing approximation baseline AT for Linear weights but excluded for the other two due to incompatibility; exact solver also does not support Log-Concave.
Email
Gnutella
RoadCA
Skitter
Method
140%%
180%
220%
2600%
140%
180%
220%
260%
140%
180%
220%
260%
140%
180%
220%
260%
Adaptive Trading
2653
5460
9675
3528
6613
23504
32935
1739299
Groedy
5458
8258
9713
3537
6626
13782
17830
24076
33127
369415
915682
1983011
3125008
Sampling Alg.
14665
4200
7775
70823
90166
1789237
2871248 6294921
5308
3490
10987
11043
17161
350397
1724336 3012839
Predict Search
9701
3645
11364
11196
18084
24967
33954
358937
1849725 3197237
L-MILPOPT
S462
3615
12069
19302
25310
34866
360994
931678
1901972 3220155
Solver
5268
9318
3383
6402
Ours
2647
5329
9601
3497
6511
8376
10495
14415
20186 27699 255789
658727 1258765 2199372
Table 1: Performance of Hephaestus and baselines on four real datasets at different thresholds T
under Linear edge weight function setting. The best is highlighted in bold excluding exact solution.
For RoadCA and Skitter dataset, ML-based methods can only use Gurobi with heuristic mode.
Solution Quality Evaluation. On the synthetic dataset, Hephaestus achieves the lowest total cost in This
all graph densities, outperforming AT and closely matching the exact solver because Hephaestus uses various solutions from the PPS algorithm to train Qg which learns where the budget should be spent effectively. As a result, Hephaestus often spends budgets on common edges that affect multiple source-target pairs. In contrast, even the best approximation algorithm in baselines, AT, cannot provide better solution than Hephaestus as it handles each pair independently, which can lead to spending edges that do not help other pairs.
8

---

Learning- based methods also exhibit the same behavior, resulting in solutions that are worse than ours. DiffILO spreads budget too widely to fix constraint violations because it relaxes binary decisions into soft probabillistic variables, while Bight-MMl.Popp splits the graph, which breaks global structure and leads to redundant spending. Predict-and-Search depends on Gurobi-generan are poor, it cannot refine them due to a narrow search space. For the Quadratic Convex (QC) and Log Concave scenarios, all IP-based ML methods become inapplicable, and even the exact solver (Gurobi) is only able to handle the QC case. Our method continues to outperform the approximation algorithms in both settings, Appendix C.8 shows that Hephaestus with PPS-I consistently achieves higher solution quality and faster runtime compared to ML-based baselines refined with Gurobi.
labels: if these
Across the four real-workd networks under thresholds T {140%, 180%, 220%, 260% J. the advan- tage of Hephaestus becomes more evident, especially on larger graphs. As shown in Table LI ours consistently achieves the lowest total budget the highest threshold = 260%. On large-scale networks where exact solvers are no longer applicable. Hephaestus achieves the most significant im- provements. Specifically, it reduces total cost by 28.1 % on Skitter and 16.8% on RoadCA compared to the second-best method, DIFFILO. On medium-scale graphs like Gnutella, Hephaestus outperforms DIFFILO by 4.5% at the highest threshold, and is only marginally behind it (by 7 units) at the lowest threshold. On the smaller Email network, ours achieves 1.0% improvement over DIFFILO at the highest threshold and is only 1% worse at the lowest. Due to space limitations, we refer readers to Appendix C.7 for more detailed comparisons of Hephaestus with other baselines on Quadratic Convex and Log Concave cost functions on real datasets.
Surgy Boria
Eneny
herpy die
Seep devisiie
Trieps unde TEU
Tripps T014
Serpp 2011
3-Expprr
6-Expert
7-Expert
9-Export
Figure 4: Comparison between the distribution from the EBM and the distribution from the Mix- CVAE with varying numbers of experts on a synthetic dataset with maximum density. Increasing the number of experts improves mode coverage and alignment with the target EBM distribution.
(4) 3-Expert
(b) 5/Expert
(e) 74Exert
(4) 9-Expert
Figure 5: An example of conditional latent space visualization via UMAP (70 for the trained Mix- CVAE on the same synthetic graph and pairs but different thresholds. Points represent latent vectors colored by threshold T.. Clear clustering shows the latent space captures meaningful patterns.
Impact of Expert A Addition in Mix- NiX-CVAE guided by EBM. We seek to determine whether Mix- CVAE, when guided by the EBM and augmented with additional experts via our method, can fully capture the distribution induced by the EBM. Figure 4 empirically demonstrates the effectiveness of our expert expansion strategy. As the number of experts in Ω increases from 3 to 9, the distribution of generated samples (orange curves) increasingly aligns with the encegy-based target distribution (blue curves). Notably, the generated distribution progressively captures more modes and exhibits better approximation of both the shape and spread of the underlying the target EBM. This improvement verifies that expert addition enables Mix-CVAE multimodal structure of the solution space p(z | c). Figure 5 further corroborates this benefit via latent space visualization. Using UMAP projections of latent variables sampled across different thresholds in the same synthetic network, we observe clear cluster formation corresponding to structural and contextual variations. These clusters become more evident as more experts are added, implying that the augmented latent space encodes richer semantic distinctions. This structured separation is
overcome mode collapse and better reflect the true

---

critical for downstream reinforcement learning in Phase 3, where the agent explores the latent space synthesize stronger attacks. Readers are referred to Appendix C for more ablation experiments.
Conclusion
In this paper. introduced Hephaestus, generative mixture model for assessing network QoS under adversarial budget constraints. By combining predictive path stressing with self self-improving generative learning, it captures structural vulnerabilities and generalizes across network scales. Exper- iments on synthetic and real-world graphs show that our framework outperforms both approximation and learning- -ased baselines in cost, feasibility, and scalability. These results highlight the potential of generative modeling with structured latent search for scalable network topology optimization.
Discussion
Limitations. While the proposed learning-based framework performs well on QoSD problems, it still has some key limitations. In theory, the overall architecture can be extended to other combinatorial optimization tasks on graphs, as long as suitable solvers or estimators are available to support gradient-free training and iterative refinement. However, its success relies on the quality of the initial solutions, which are used train the generative model. Specifically, the framework depends on having reasonably good approximation algorithm to produce the initial dataset in Forge. In addition, the model's ability to generalize to unseen network instances is influenced by two important factors. First, it depends on how well the GNN-based estimator (such as SPAGAN) can generalize when predicting shortest-path costs on new graphs. Second, it relies on the quality the graph representation that is used as input to the conditional generative model. If the estimator or the encoder fails to capture meaningful structural features, the overall performance both in terms of feasibility and cost may degrade. Future research could improve generalization by incorporating graph-invariant invariant features, training on more diverse graph distributions, or using more expressive graph-based foundation models.
Broader Impact. This work proposes a Barning-basede framework for solving Quality of Service Degradation (QoSD) problems in large-scale networks, with the potential to influence both algorithmic research and practical applications infrastructure security, communication planning. and critical network vulnerability assessment. By combining generative modeling, energy-based guidance, and reinforcement learning, the framework offers a scalable alternative to traditional combinatorial solvers, enabling approximate yet effective solutions for computationally intractable tasks. This approach can assist network designers and operators in stress test systems, proactively identifying fragile components, and evaluating resilience under adversarial or high-load scenarios. It also provides reusable architecture for structured optimization over graphs, which could benefit domains such as transportation, power grids, and supply chain logistics.
7 Acknowledgments
This work was partially supported by National Science Foundation grant IIS-2416606. Any opinions, findings, and conclusions or recommendations expressed in this paper, however, are those of the authors and do not necessarily reflect the views of the funding agency.
10

---

References
[1] Lan N Nguyen and My Thai. Network resilience assessment via qos degradation metrics: an algorithmic approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(1):1-32, 2019.
[2] Alan Kuhnle, Victoria G. Crawford, and My T. Thai. Network resilience and the length- engthh-bouded multicut problem: Reaching the dynamic billion-scale with guarantees. Proc. ACM Meas. Anal. Comput. Syst., 2(1), April 2018.
[3] Maria Apostolaki, Aviv Zohar, and Laurent Vanbever. Hijacking bitcoin: Routing attacks on cryptocurrencies. In 2017 IEEE Symposium on Security and Privacy (SP), pages 375-392, 2017.
[4] Carlos Pinzón and Camilo Rocha. Double-spend attack models with time advantange for bitcoin. Electronic Notes in Theoretical Computer Science, 229:79-103, 2016.
[5] Richard Dennis, Gareth Owenson, and Benjamin Aziz. A temporal blockchain: a formal analysis. In 2016 International Conference on Collaboration Technologies and Systems (CTS), pages 430-437. IEEE, 2016.
[6] Qi Alfred Chen, Yucheng Yin, Yiheng Feng, Z Morley Mao, and Henry X Liu. Exposing congestion attack on emerging connected vehicle based traffic signal control. In NDSS, 2018.
[7] Stephen Checkoway, Damon McCoy, Brian Kantor, Danny Anderson, Hovav Shacham, Stefan Savage, Karl Koscher, Alexei Czeskis, Franziska Roesner, and Tadayoshi Kohno. Comprehen- sive experimental analyses of automotive attack surfaces. In Proceedings of the 20th USENIX Conference on Security, SEC' 11, page 6, USA, 2011. USENIX Association.
[8] Karl Koscher, Alexei Czeskis, Franziska Roesner, Shwetak Patel, Tadayoshi Kohno, Stephen Checkoway, Damon McCoy, Brian Kantor, Danny Anderson, Hovav Shacham, and Stefan Savage. Experimental security analysis of a modern automobile. In 2010 IEEE Symposium on Security and Privacy, pages 447-462, 2010.
[9] Sahar Mazloom, Mohammad Rezacirad, Aaron Hunter, and Damon McCoy. security analysis of an /in-vehicle) infotainment and app platform. In 10th USENIX workshop on offensive technologies (WOOT 16), 2016.
[10] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
[11] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 11.000000000.... 2017.
[12] Eitan Israeli and R. Kevin Wood. Shortest-path network interdiction. Networks, 40(2);97-111 2002.
[13] J. Cole Smith, Mike Prince, and Joseph Geunes. Modern network interdiction problems and algorithms. In Handbook of Combinatorial Optimization, pages 1949-1987. Springer, 2013.
[14] J. Cole Smith and Yuyuan Song. A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3):797-81) 2020.
[15] Tien Mai, Avinandan Bose, Arunesh Sinha, Thanh H. Nguyen, and Ayushman K. Singh. Tackling stackelberg network interdiction against a boundedly rational adversary. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (ICAAI) 2024.
[16) Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
[17] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Thirty-seventh Conference on Neural Information Processing Systems, 2023.

---

[18] Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. A survey for solving mixed integer programming via machine learning, Neurocomputing. 519:205-217, 2023.
[19] Xijun Li, Fangzhou Zhu, Hui- Zhen, Weilin Luo, Meng Lu,, Yimin Huang. Zhenan Fan, Zirui Zhou, Yufei Kuang. Zhihai Wang, Zijie Geng, Yang Li, Haoyang Liu, Zhiwu An, Muming Yang, Jianshu Li, Jie Wang. Junchi Yan, Defeng Sun, Tao Zhong, Yong Zhang, Jia Zeng, Mingxuan Yuan, Jianye Hao, Jun Yao, and Kun Mao. Machine learning insides optverse ai solver:
Design principles and applications, 2024.
[20] He He, Hal Daumé, and Jason Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[21] Radu Baltean- Baltean-Lugojant Lugojan, Pierre Bonami, Ruth Misener, and Andrea Tramontani. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. preprint: http:///ww.. optimization aptimizaatinn-nninee online. org/DB HTML/2018/1 1/6943, html, 2019.
[22] Yufei Kuang, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, and Yongdong Zhang. Accelerate presolve in large-scale linear programming via reinforcement learning. IEEE transactions on pattern analysis and machine intelligence, PP, 04 2025.
[23] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact com- binatorial optimization with graph convolutional neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[24] Sirui Li, Wenbin Ouyang, Max B. Paulus, and Cathy Wu. Learning to configure separators in branch-and-cut. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[25] Huigen Ye, Hua Xu, and Hongyan Wang. Light-MILPopt Solving large-scale mixed integer linear programs with lightweight optimizer and scall-scale training dataset. In The Twelfth International Conference on Learning Representations, 2024.
[26] Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In International Conference on Learning Representations, 2023.
[27] Hongyu Cheng and Amitabh Basu. Learning cut generating functions for integer programming, In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 61455 61480. Curran Associates, Inc., 2024.
[28] Vinod Nair Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang. Ravichan- dra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks, 2021.
[29] Tachyun Yoon. Confidence threshold neural diving, 2022.
[30] Elias B. Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219-10227, 2022.
[31] Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. Gnn&gbdt-guicke fast optimizing framework for large-scale integer programming. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 39864-39878, 2023.
[32] Hao Zeng, Jiaqi Wang, Avirup Das, Junying He, Kunpeng Han, Haoyuan Hu, and Mingfei Sun. Effective generation of feasible solutions for integer programming via guided diffusion. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages -118-4118, 2024.
12

---

[33] Hoang M. Ngo, Nguyen H K. Do, Minh N. Vu, Tre' R. Jeter, Tamer Kahveci, and My T. Thai. Charme: A chain-based reinforcement learning approach for the minor embedding problem. 2025.
[34] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. arXiv preprini 2302.x:330005666 2023.
[35] Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Contrastive predict-and and-serrh- for mixed integer linear programs. In Forty-first International Conference on Machine Learning, 2024.
[36] Gurobi Optimization, LLC. Gurobi optimizer, 2021.
[37] Tobias Achterberg. Scip: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1-41, 2009.
[38] Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1):9-26, 2022.
[39] Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, volume 34, pages 1504-1511, 2020.
[40] Arman Zharmagambetov, Brandon Amos, Aaron Ferber, Taoan Huang, Bistra Dilkina, and Yuandong Tian. Landscape surrogate: Learning decision losses for mathematical optimization under partial information. Advances in Neural Information Processing Systems, 36, 2024.
[41] Zijie Geng, Jie Wang, Xijun Li, Fangzhou Zhu, Jianye HAO, Bin Li, and Feng Wu. Differen- tiable integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025.
[42] Yiding Yang. Xinehao Wang, Mingli Song, Junsong Yuan, and Dacheng Tao. Spagan: Shortest path graph attention network. In Proceedings of the Twenty-Fighth International Joint Confer- ence on Artificial Intelligence, 1JCAI-19, pages 4099-4105, International Joint Conferences on Artificial Intelligence Organization, 7 2019.
[43] Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. Advances in neural information processing systems, 32, 2019.
[44] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, Fujie Huang, et al. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
[45] Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. Advances in neural information processing systems, 28, 2015.
[46] Huyen Nguyen, Hieu Dam, Nguyen Hoang Khoi Do. Cong Tran, and Cuong Pham. Rem: scalable reinforced multi-expert framework for multiplex influence maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 39(25):27099-27107,, Apr. 2025.
[47] Nguyen Hoang Khoi Do, Truc Nguyen, Malik Hassanaly, raed alharbi, Jung Taek Seo, and My T. Thai. Swift hydra: Self-reinforcing generative framework for anomaly detection with multiple mamba models. In The Thirteenth International Conference on Learning Representations, 2025,
[48] Puning Zhao, Lifeng Lai, Li Shen, Qingming Li, Jiafei Wu, and Zhe Liu. A huber loss minimization approach to mean estimation under user-level differential privacy. In A. Globerson, I.. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 130018-130055 Curran Associates, Inc., 2024.
[49] Gregory Meyer. An alternative probabilistic interpretation of the huber loss. Conference on Computer Vision and Pattern Recognition, pages 5257-5265, 06 2021.
13

---

[50] Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269- 1959.
[51] Huy Nguyen, Xing Han, Carl Harris, Suchi Saria, and Nhat Ho. On expert estimation in hierar- chical mixture of experts: Beyond softmax gating functions. arXiv preprint arXiv:2410.02935, 2024.
[52] Hien Dang, Tho Tran, Tan Nguyen, and Nhat Ho. Neural collapse for cross-entropy class- imbalanced learning with unconstrained relu feature model. arXiv preprint arXiv:2401.02058. 2024.
[53] Huy Nguyen, Pedram Akbarian, Fanqi Yan, and Nhat Ho. Statistical perspective of top-k sparse softmax gating mixture of experts. In The Twelfth International Conference on Learning Representations, 2024.
[54] Zixiang Chen, Yihe Deng, Yue Wu, Quanquan Gu, and Yuanzhi Li. Towards understanding the mixture-of-cxperts layer in deep learning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 2006222300.... Curran Associates, Inc., 2022.
[55] Walter R Gilks, Sylvia Richardson, and David Spiegelhalter. Markov chain Monte Carlo in practice. CRC press, 1995.
[56] Chelsea C. White and Douglas J. White. Markov decision processes. European Journal of Operational Research, 39(1):1-16, 1989.
[57] Sebastian Ruder. An overview of gradient descent optimization algorithms. ArXiv, 1609.04747, 2016.
[58] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: A new approach for hard-exploration problems. arxiv. 2019, 1901.
[59] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference machine learning, pages 2778-
2787. PMLR, 2017.
[60] David Silver, Thomas Hubert, Julian Schritwieserr, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Græepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint 1rXiv:1712.01815 2017.
[61] Hao Yin, Austin Benson, Jure Leskovee, and David F Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 555-564, 2017.
[62] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):-ess 2007.
[63] Jure Leskovec, Kevin Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123, 2009.
[64] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. Proceedings of the eleventh ACM SIGKDD international conference Knowledge discovery in data mining, pages 177-187, 2005.
[65] Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via a modern optimization lens. The Annals of Statistics, 44(2):813-852, 2016.
[66] Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356,
2017. 2017.
14

---

[67] Hao Zeng, Jiaqi Wang, Avirup Das. Junying He, Kunpeng Han, Haoyuan Hu, and Mingfei Sun. Effective generation of feasible solutions for integer programming via guided diffusion. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD '24, page 4107-4118, 18, New York, NY, USA, 2024. Association for Computing Machinery.
[68]
Jiaming Song. Chenlin Meng. and Stefano Ermon. Denoising diffusion implicit models. In International Conference Learning Representations, 2021.
[69] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 200 Red Hook, NY, USA, 2020. Curran Associates Inc.
[70] Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 2018.
[71] Nguyen Do, Cao Dung Truong, Nguyen Hang Duy, Minh Hoai, and Cuong Pham. Self- controlling photonie-on-chip networks with deep reinforcement learning, 07 2021.
[72] Nguyen Do, Tanmoy Chowdhury, Chen Ling, Liang Zhao, and My Thai. Mim-reasoner: Learning with theoretical guarantees for multiplex influence maximization, 2024.
[73] Nguyen Do Hoang Khoi, Cuong Pham Van, Hoang Vu Tran, and Cao Dung Truong. Multi- objective exploration for proximal policy optimization. In 2020 Applying New Technology in Green Buildings (ATiGB), pages 105-109, 2021.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction (Lines 1-18, 67-78) ac- curately reflect the contributions of the paper: (i) proposing a new generative framework Hephaestus for QoSD with both linear and nonlinear edge weights, (ii) introducing predic- tive path-stressing algorithm with provable guarantees, (iii) theoritically modeling solution distributions with an energy-guided mixture of CVAEs, and (iv) refining solutions via latent-space RL.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Limitations of our framework are discussed in the Limitation Section (Ap- pendix/Supplementary file).
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
16

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper provides theoretical guarantees in Theorem 1 (Line 159), Theorem 2 (Line 209), Theorem (Line 223), Lemma (Line 272), and Theorem 4 (Line 274), with explicit assumptions involving constants such ō, e, and bounds energy/log-ratio terms. Complete proofs are deferred to Appendix B. Due to space limitations, additional corollaries, theorems, and lemmas that support and extend the main results are also included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper provides sufficient detail to reproduce the main experimental results. Section 4 outlines datasets, baselines, evaluation protocols, and QoSD settings. Appendix C includes ablations, dataset statistics, and details on thresholds, graph generation, and tuning parameters for all baselines.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
17

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: An anonymized code is in the supplemental material with scripts for training SPAGAN, Mix-CVAE, EBM, and the RL refinement phase, along with instructions and preprocessed data for both synthetic and real datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwwpppplcpgguceeeeeeeeeeeooeeeee wwwpc//ggiiss/eeeeeeeeee /CoeeeSm ssiinni ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 4 and Appendix detail dataset, thresholds, sampling strategy, SPA- GAN training, CVAE settings, and reinforcement learning parameters.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
18

---

Answer: [No]
Justification: While results are consistently benchmarked across multiple thresholds and densities, the paper reports the average performance over 20 independent trials per instance, as stated in Appendix C. However, it does not include error bars, standard deviations, or confidence intervals.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section provides timeout settings for baselines (e.g.. 3000s-6000s for Gurobi), and Appendix C includes compute specifications and other individual experiment run for training and inference phases.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps://eurrpps http:///owrrrp..ccpppcacccccccaa
Answer: [Yes]
Justification: The research complies with the NeurIPS Code of Ethics. All experiments are conducted on publicly available or synthetic datasets. No human subjects or personally identifiable data were involved.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
19

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper explicitly discusses social impacts of the model studied, and the advancement of our solutions. The broader impact statement is in Appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The models developed are not of high misuse risk (e.g., they are not language image generators), and datasets used are standard graph datasets or synthetic ones without sensitive content.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
20

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets (e.g.. Email, Gnutella, RoadCA) and tools (e.g.. Gurobi, SCIP) are properly cited with references [35], [41]. [60-63], and their usage complies with open academic licensing terms.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the satiaastsspppesswiii. paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
They are provided with documentation and instructions in the supplemental material.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The research does not involve any crowdsourcing or human subject experi-
ments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
21

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve human subjects; therefore, IRB approval is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: No large language models (LLMs) are used in our core methodologies, lemmas and theorems.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bettts://neurige http///rips.cc//oofeeeeeeeeeeeee ecc/con/reec for what should or should be described.
22

---

Supplementary for Hephaestus: Mixture Generative Modeling with Energy Guidance for Large-scale QoS Degradation
This supplementary material serves the appendix to the main paper to provide full algo- rithmic pseudocode for all components of the framework, detailed derivations and proofs of key theoretical results, comprehensive ablation studies and hyperparameter settings, as well as expanded discussions on implementation to reproduce results, scalability, and generalization. It organized as follows:
8
DETAILS OF HEPHAESTUS
24
8.1
Hephaestus Main Framework
8.2
Forge
24
8.3
SPAGAN Training
25
8.4
Predictive Path Stressing (PPS)
26
8.5
Morph
26
8.6
Refine
28
87
Inference Process
8.8
Predictive Path Stressing Inference (PPS-I)
29
THEOREMS AND PROOFS
30
9.1
Predictive Path Stressing Algorithm Ratio
30
9.2
Expert Augmentation Elliciency
933
Normalization Free Function
36
9.4
Differentiable Reward Function
38
9.5
Reward Estimation Consistency
39
10
DE
EXPERIMENTS AND ABI ATION STUDIES
10.1
Dataset Details
10.2
Hyperparameter Settings
10.3
SPAGAN Generalization
10.4
Robustness to SPAGAN Errors and Exact-Paae Path Safeguard
48
10.5
Resilience Weak Initial Data
10.6
Comparison with Alternative Latent Optimization Strategies
10.7
Energy Distribution Convergence during Minimax Training
10.8
Latent Space Visualization
54
10.9
Impact of Expert Addition in Mix-CVAE
55
10.10 10
Performance under
Edge Weight Functions
10.11
Soundness the Reward Function
58
10.12
Relative optimal gap convergence
59
10.15
Hephaestus with different feasibility refinement
60
23

---

8 DETAILS OF HEPHAESTUS
8.1 Hephaestus Main Framework
Algorithm I: Hephaestus Main Framework
Input:
Initial graph dataset Deraph set of critical pairs K, set of thresholds T, hyperparameters for all components.
Output: Trained Hephaestus model (SPAGAN So. EBM q. Mix-CVAE Ω RI. agent T), and ability to generate near-optimal solutions x" for new QoSD instances.
1/ Initialize storage for solutions
// -- Phase 1:
Forge -
2 (Bo. D soo
initial f- F T)
3 Dsol + Dool U 2 sol
initial
1/ Phase 2: Morph
q, 12) Morph(
// Phase 3: Refine (Iterative Self-Reinffrrement))
for each episode 1..... Emaasepisvdes episodes do Top-koSolutions Refine 52, π,, Deal 35) (
D D U Top-K-Solutions // Augment solution dataset
8
e mod Exerrinnfeee == 0 then
Periodically retrain Morph with augmented data (g. 92) + Morph(D*dl)
10 π < Finalize RL Agent Training from collected experiences
Return 30, 9, 92,
The pseudocode for the main framework of Hephaestus encapsulates full pipeline for solving the QoS Degradation (QoSD) problem through a self-reinforcing generative approach. The algorithm begins by initializing an empty solution set (line 1) and entering the Forge phase (line 2), where trains a Shortest Path Graph Attention Network (SPAGAN) to approximate shortest-path costs, and then runs the Predictive Path Stressing (PPS) algorithm to generate diverse, feasible perturbation solutions across multiple graphs, thresholds, and critical source-target pairs. These solutions are collected into a pretrained dataset soo (line 3), which is then assigned the foundation training set for the next phase, Morph (line 4).
In Morph (line 4), an Energy-Basee Model (EBM) is trained estimate the underlying solution density, and a Mixture of Conditional VAEs (Mix-CVAE) is optimized to match this density, with new experts dynamically added cover poorly modeled regions. Finally, the Refine phase (starting from line 6) trains an RL agent to explore and optimize in the latent space of the Mix-CVAE improving solution quality while maintaining feasibility. Furthermore, after each episode, the best performing (highest reward) solutions are added back to D= and for all Fretrain, (itraiinffrey episodes, the generative model (q, 52) is periodically re-trained on this augmented dataset (lines 10-11), allowing continual improvement and adaptation. The framework outputs all trained components: SPAGAN, EBM, Mix-CVAE, and RL policy synthesize near-optimal QoSD solutions on new graphs (line 12).
8.2
Forge
The Forge phase is responsible for constructing initial dataset of feasible QoSD perturbation solutions using graph-learned approximation method. It begins by training an SPAGAN, denoted Go. the provided set of input graphs praph (Line 2). This model learss to efficiently approximate the shortest-paid -ath costs under varying edge perturbations. An empty set seal is initialized to store solutions (Line 3). Then, for every graph G, in the dataset (Line 4), and for every configuration of critical source-target pairs K. E K and thresholds T E T (Lines 5-6), the PPS is executed to produce (+) perturbation vector x (Line 7). This vector is expected to increase all relevant shortest path costs past the threshold T, using SPAGAN as efficient surrogate for shortest path cost estimation. Each resulting solution instance then added to the solution set sol (Line 8), preserving its associated graph, set of critical pairs, and threshold. Once all iterations complete, the function returns both
new

---

the trained SPAGAN model and the newly constructed dataset of feasible perturbations (Line 10), which will serve as the training base for the Morph phase.
Algorithm 2: Forge
Procedure Forget Deraph K, T)
80 Trai_SPAAAATE graph) // Train SPAGAN for path cost estimation D f 0
for each graph G; Deruph do for each critical pair configuration K. E K do for each threshold T E do
7
K,T P,, soll new
[fe]: b) U K, (7) xTT))
8
f
new
Return (Bo. Daol
8.3 SPAGAN Training
This procedure describes the supervised training for SPAGAN, used to approximate shortest-pant distances between node pairs in graph. The function begins by initializing the SPAGAN model To (Line 2), which is parameterized to learn over graph-structured input. For a fixed number of training epochs, the model is iteratively updated (starting from line 3). During each epoch, the algorithm samples mini-batches of data data-eat each consisting a graph G. source-targe target pair (s. t), and the corresponding ground-truth shortest-path distance true dist, typically computed via Dijkstra's 'ss algorithm (Line 5). For each instance, the model predicts the baseline shortest-path cost de.e using the sub-graph (Line 6). The prediction eπror is measured using the Huber loss function, which provides robustness to outliers and smooth gradients (Line 7). The model parameters are then updated using backpropagation (Line 8), allowing the network to gradually learn transferable representation of graph structure and path dynamics. Once training converges, the fully trained SPAGAN model So is returned (Line 9) to be used in Forge for shortest path estimation.
Algorithm 3: SPAGAN Training with Subgraph Sampling
Procedure Train_SPaGrin SPAGAN(D8aap
Initialize SPAGAN model So
Duubraap t ExtractSubgraphs(2] (umpp) // Generate training subgraphs from full graphs
for each training epoch do for each batch (G t, true ( from D ruhgroph do
da,t +- (G 8, 1, // Predict baseline shortest path on subgraph loss <- HuberLosss/ (os trtuerruiii siue__dst)::
Update ßo parameters using backpropagation:
Return Trained So
8.4 Predictive Path Stressing (PPS)
Solving the QoS Degradation (QoSD) problem computationally challenging due to the exponential number of feasible paths and the non-submodular nature of the objective function under nonlinear edge costs. To mitigate these challenges, PPS avoids enumerating all feasible paths and instead incrementally constructs feasible perturbation vector NI)), using shortest-pan -ath predictions from pretrained SPAGAN model Te. Unlike exact methods, PPS relies entirely on SPAGAN to both determine shortest paths and estimate their costs under perturbation. The algorithm starts from an initial perturbation Xinitial (Line 2), and constructs set K-violate of source-target pairs whose predicted path costs, given by To Go(G, 8, 1; x). fall below threshold (Line For each violating pair, obtains the corresponding shortest path Pa.t using the SPAGAN shortest-path predictor (Lines 6-8), A soft
25

---

which serves as proxy to measure gap feasibility (Lines 13-14). While ((P.)) remains less than the relaxed threshold [P] PPI-T-- - É, the algorithm performs updates by selecting the edge e and increment A that lead the greatest increase in potential per budget unit (Lines 10-24). This is computed by evaluating each candidate update x' and recomputing the potential function C(P, x') using SPAGAN predictions (Lines 17-20), without requiring explicit path enumeration or cost function evaluations. Once the optimal update is applied (Line 24). the algorithm checks whether the potential function C(P. has exceeded the soft feasibility threshold [P| T E. If so, the set of violating pairs is refreshed by recomputing their shortest paths and corresponding predicted costs using SPAGAN (Line 25). The process repeats until all pairs satisfy the constraint (o,G, 8, 1; x) z T, which point the final perturbation vector x is returned (Line 27).
potential function is defined as: C(P,x) = EPLEP min So
Algorithm 4: Predictive Path Stressing (PPS)
Procedure PPS(G = (V,
; {fe] b, Ximitial 3o)
Input: Graph G (V, EE), target pairs K., threshold T, edge cost functions {fe J. budget box b, initial vector Xinitial, trained SPAGAN 8a
Output: Feasible adversarial budget vector such that estimated path cost Eeep.. fe(xe) 2 T for all (s,t)= E K
x Xinitial ;
Kvviolate + {(s, E Enep,, Se(x,) < T, Ps,t = SPAGMIPath((f...ss.t.....
while Kvialute # do
P P+ 0: foreach (s, E Kevisiate do
Ps,t + SPACANPath(BB. s,
P PU (patt:
1/ Evaluate soft potential function c(P,x) +0
10
while C(P,x) < P do
11
(c", "A,"" ) f- (None, -oo);
12
Ep + UPEEP? p:
13
foreach Ps, E P do
14
x(, + C(P, x) + min (o
15
foreach e E E do
16
for A = 1 to b. - xe do
x' + x
1,;
C(P,x') +0;;
19
foreach Pa.t E do
L C(P,x') x(),x') + 3o
8 + -
21
A
22
if 8 > 8max then (e", A+ Smax) (,)
// Apply optimal update x + A l.
// Update violating pairs using SPAGAN
25
K (s.,t) E EeEm, fe(xe) T, Ps.t = (,
26
Return x
8.5
Morph
The Morph phase is designed to model the distribution of high-quality QoSD solutions using a generative framework guided by energy-based learning. Intuitively, the goal is to make the Energy- Based Model (EBM) go approximate the true, but unknown, solution distribution as closely as possible. To do this, the EBM is trained to assign low energy (i.c., high likelihood) to real solutions
26

---

Xeeal ~ D effectively pulling its density toward regions with meaningful feasible solutions. At the same time, is encouraged to assign high energy (i.e., low likelihood) to generated (fake) samples Xtake 52, which come from the current generative model Q. This adversarial learning setup drives the EBM away from areas the generator covers poorly, creating pressure that helps both models evolve: the EBM becomes more selective, and the generator learns to cover harder regions.
Algorithm 5: Morph
Procedure Morph(Dtal)
Initialize EBM qe and Mix-CVAE 1
[S. [2N] (initially N 0 for first expert)
for each minimax training iteration 1: = 1, Kmax_morph do // Update EBM qo
Sample (Xreal, c) from D
Sample Mtake (z)c) (from any expert S2;):
Xtake f- -MM c.) (from eurrent W's decoder Mo):
Drat Lig f- ()
[Ea [reat]] - EB [xtak)] + (IB[EaxXra ((rak)))))
Update parameters 0 of EBM to minimize Laj
// Update MiX-CVAE Sample (Xreal, c) from D
LQ < 0;
for each expert S2 .M))) E S do
10
Zeeccded +- p(()) (Xreal; :): FIBBO x- Ex- (a)xia (a) Porg (Nreal 2, [2,c]] - KL(Āuco Dt;
11
Xreal, c) 1) |c]
13
Sample Aprior ~ Para (z c)
Xgenerated f M (Zprior: c)
14
guidd t- Lg. FI.O + X- Eg (Xgenerated // Penalize high energy generations
15
La t La + Lis.
Lguidee // Potentially use gating weights here
17
Update Mix-CVAE parameters v. for all experts to minimize Lq // Expert Addition Strategy
18
if l: (mod Kyhuck eesport)
then
19
Sample Xcheck from Dool or generate from current Ω
20
x (Xehheck) -- (ogg(e(Xxchck)) ((Xeee)))((X (Ccheck)) // Density ratio if (XXcheeck > Sexpert_aid add and current number of experts < Nmax then
21
22
Add a new CVAB expert 22 1 to it;
Initialize/Train 9N (e.g., focused on data from regions where x dexpert_add re-train mixture);
- N
25
Return (Trained qo. Trained ?)
Formally, the algorithm starts by initializing both the EBM qo and mixture of Conditional VAEs = Pg. ... 3. starting with one single expert (Line 2). Each minimax training iteration proceeds in two stages. First, the EBM is updated by contrasting energy scores between real samples and generated ones. Fake samples are produced by sampling a latent vector Zfak ~ Pa (z c) from the prior of any expert and decoding it via decoder M2 of J (Lines 4-6). The EBM loss pushes energy lower on real samples and higher on generated ones, with variance-basee based regularization to stabilize training (Line 7), and the parameters 0 are updated accordingly (Line 8).
Next, the generative model inputs to latent space, and the decoder reconstructs the solution. The training objective combines the standard ELBO which promotes good reconstruction and posterior-prior alignment- energy penalty term (Line 15). This penalty uses the EBM to discourage high-energy generations, ie.. samples that lie in unrealistic or undersampled regions. The total loss La aggregates across all experts and is minimized to improve the generative model's coverage of low-energy regions (Line 16). To adaptively expand model capacity, the algorithm includes periodic expert addition
updated (Lines 10-17). For each expert 2, the encoder maps real
an
27

---

strategy (Lines 21 21-28). Every expeek_expeat
expent steps, it evaluates whether the current mixture ! underfits any region of the solution space using a density ratio test: x(x) log (x)x / c)). this score exceeds threshold δexpert add, indicating insufficient generative density, a new CVAE expert is added and trained specifically on that difficult region. This enables the generator to incrementally
cover diverse and potentially multimodal distributions. The process continues until the maximum
number experts is reached or training ends. Finally, Morph returns both the trained EBM and the mixture-based generative model.
8.6 Refine
Algorithm 6: Refine
Procedure Refine(g, S2, n, Dih :30
Input: Energy model q, generative model Ω RL policy n, solution dataset Dool, SPAGAN estimator 8o
Output: Top-K refined feasible solutions with low cost Initialize Snow + / // Storage for solutions generated in this episode for each RL training step
...... Smax do
Sample instance (G, K. Xx) from D C c [G, IG, // Context input Zeartent t PPs(X, c) // Encode current solution into latent space for each step 1 1==,,-... 1,..., Imar do
(ue; 04. <- T (state(Xcurrem: (Zaureett c)) // Sample action
6 ~ N (0,
10
+ Pt Pc+ or E /// Perturb latent
11
Zuext + Zeurrent + 6
12
8 + Molene c) // Decode solution
13
x 4 log(1 + xx) // Soft transform for reward
// Evaluate feasibility score via SPAGAN approximation
14
fscore E(Sp,))) T4exp(- ((Bo(((( ((..)))))))
// Compute reward (Eq. 6)
R₂ + fscore-
log(1 + )
16
Store transition ((Zcumenn; c), (1e ot), RG, (Zmext: c)) in replay buffer;
Update policy using replay buffer (e.g., PPO, DDPG, gradient-ascent, etc.)
18
Zeuurent &- Znext
if R2 2 Retrreh
Ima then Xrefined +- PPSS- T, // Ensure 100% feasibility
20
21
Snew + Snow U {(G, Xccine)))
Break
// Select best solutions based on true cost Sort Snew ascending order of [|xefined]]]
23
24 Select top K entries as Spopk:
25
Return Styp
This algorithm implements single episode of the Refine phase, which performs latent-space opti- mization via reinforcement learning to improve solution quality for the QoSD problem. The goal to generate low-cost, feasible perturbation vectors by guiding latent policy network using differentiable reward structure. The algorithm begins by initializing an empty buffer Spew to store high-quality solutions generated during the episode (Line 2). At each RL training step (Line 3), an instance KG, T.T.) is sampled from the solution dataset Dol and the corresponding context vector = TJ is constructed (Line 5). The current solution x is encoded into latent space via the encoder P of any CVAE expert Ω4 E Ω to yield Zeurratt (Line 6). An RL trajectory is then simulated over I Imax steps (Line 7). At each step I, the RL agent samples an action a, (H,, o,) from the policy network given the current state (Line 8), and applies stochastic perturbation to the latent vector using Gaussian noise ~ (O, 7) (Lines 9-10). The next latent state Z is computed and decoded into candidate perturbation vector & using the decoder Mg (Lines 1 11-12). A soft
28

---

transformation X log(1 + )* is then applied to allow stable reward evaluation (Line 13). To assess the quality of the decoded solution, feasibility score is computed based on SPAGAN's predictions of shortest path costs for each critical pair (Line 14), followed by differentiable reward Rg that penalizes excessive cost via logarithmic budget term (Line 16). The resulting transition stored in replay buffer, and the RL policy is updated using any standard algorithm such as PPO, DDPG, or curiosity-driven exploration (Lines 17). The latent vector then updated for the next step (Line 18). If the reward exceeds a predefined threshold Rirresh or the trajectory reaches the time limit (Line 19), the decoded solution passed through PPS-I (Line 20) to continue refine and ensure exact feasibility, The resulting solution is stored in Snow (Line 21), and the trajectory is terminated (Line 22). After all episodes are completed, the algorithm ranks the refined solutions by their true cost | || (Line 23), selects the top-K. best ones (Line 24). and returns them the output of the refinement episode (Line 25). These solutions are later fed back into the seff-reinforcement loop, improving both the generative model and the energy function in subsequent iterations.
8.7 Inference Process
Algorithm Inference Process
Procedure Inference( Gnew, Knews T Tnews Dt IT, 3e)
Input: New instance (Gnow, Knew T new). trained Q, π, 30
Output: Near-optimal feasible solution X Cnew + [Gnew; Knew, Tnw]]:
Sample initial latent vector Zini (e.g., from Itss prior Po Cnew) ) encode a heuristic
solution);
z" < Zinit
// RL agent refines latent vector for the new instance
for k I,... K Kinferemce_ssn stepp do Action = (H, 0) t (state(zz (nntee )) // RL policy acts on current latent
state
Epoise ~ ~N 1) ) // Exploration or deterministic if a is small 8 O o. Emoise + p
z= 2" Ō
10
Nyaw
f Malz", ('l""""Cevv Cnew) (Decoder from !2): PPS-I(Gnew new Knew, Tnows Xeas) // Final refinement for feasibility
tinal
12 Return Xiinal
In Algorithm the inference process of the Hephaestus framework aims generate near-optimal, feasible solutions on a new unseen QoSD instance (Gnew; Knew, Tnew) using the trained models Ω ग, and So. The goal is leverage the learned latent-space generator and RL policy to efficiently synthesize a high-quality perturbation vector without needing to re-run the full training pipeline. The process begins by constructing the context vector Caew [Gnow Knew T [oow] (Line 2). An initial latent vector Zinit is then obtained either by sampling from the prior of the trained Mix- CVAE Po (z| Crow) (Line 3). This serves as the starting point for iterative improvement. The current latent solution is set to 2" = (Line 4). To refine this latent vector, the trained RL policy æ is applied iteratively (Lines 5-9). At each step the policy takes the current latent state and produces an action which defines a mean and uncertainty over latent perturbations (Line 6). A Gaussian perturbation sampled and applied to the latent vector z gradually steering the solution toward more feasible and lower-cost regions (Lines 9-10). This process continues either for fixed number of inference steps Kinference steps or until the reward (implicitly computed within the policy) stabilizes. After refinement, the latent code z" is decoded into of the generative model Ω (Line 10). To ensure full fcasibility, this vector is passed through the PPS-I post-pree prot-procsssing module (Line 11), which guarantees that the final solution x satisfies the QoSD constraints. The final output is then returned (Line 12).
(u, o).
perturbation vector X using the decoder Ma
8.8 Predictive Path Stressing Inference (PPS-I)
This procedure describes PPS-I, variant of the Predictive Path Stressing (PPS) algorithm that retains the same iterative update mechanism over shortest-path constraints. However, PPS-I differs from PPS in two key aspects. First, instead of relying on SPAGAN predictions, it uses Dijkstra's algorithm
29

---

to compute exact shortest paths Ps,t and evaluates their true costs using the nonlinear edge functions fe fz.z)) as shown in Lines 7, and 27. This guarantees correctness under arbitrary cost functions but incurs higher computational overhead. Second, PPS-I accepts non-zero initial perturbation vector Xinitial as input (Line 3), allowing to continually refine approximate solutions produced by learning-based modules rather than starting from scratch. The rest of the rngic-computinnn potential (Lines 13-15), evaluating marginal gain for candidate updates (Lines 16-23), and selecting optimal edge increments (Line remanemi structurally similar to PPS. The set of violating pairs refreshed using recomputed exact shortest paths (Line 27), and the process continues until full feasibility is achieved.
soft
Algorithm 8: Predictive Path Stressing Inference (PPS-I)
Procedure PPS-I(G = (V. E,, K,T,, T, {fe]. b, Ximitiat)
Input:
Graph G (V, E), critical pairs K,, threshold T, edge cost functions {fe}: budget
bounds b, initial solution Xnitial
Output: Feasible budget vector such that Eeep., fa(xe) T for all (s, E K.
x Ximitial ; Kviilate + (s, K. Eeep.. fe(xe) < T, Pa, = (..iisistrraPPttt.ssstssss
while Kenolure + do
P + 0 // Shortest paths for current violations
foreach (s, E Kiviolote do
Ps.t Dij --
P - PU (p
1/ Evaluate potential function
c(P.x) + 0;
10
while C(P, < -
11
(e", ((,0max) +- (None, None, -
Ep + S
12
13
foreach Pa. do
Cp + Eneppn fa(x.):
15
C(P,x) + C(P,x) + min(T,
16
foreach e E E do
17
for A- = 1 to b Te do
x
le:
C(P,x') +0;
20
foreach Pa. E do d + Le'en, (e))
C(P,x') C(P,x') x') + min(T,c))
8 C(Px') (((x))
A
if 8 6max then (e", A+, Smax) + (e,
25
// Apply optimal update x < x + A 1,+
26
// Update violating pairs
27
Kyvolate (s, E Eeep., fe(xe) < <T, Ps.: DijksstraPath(C.s....))
28
Return x
9 THEOREMS AND PROOFS
9.1 Predictive Path Stressing Algorithm Ratio
Theorem (PPS Ratio) Let h [T/Wminl where Wmin min F we. Assume that the set is chosen from E such that Pr[E* _ E] a, where Ex is the set of edges of the optimal solution and
30

---

a E (0, 1) is constant. Given parameter E > 0, then running the Predictive Path Stressing algorithm
on yields solution x such that C(P,x) x) 2 |P È and B|[|x||]] - (L+A T (m(1/)) OPT
Proof. Recall that C(P.x) = Epep min T. fe (1e)) and thus C(P,.) is monotone. Denote x is the partial solution after iteration of the algorithm, e; is the edge added to the solution in iteration i with ze, j; and J() be a vector we add to the solution x" in the i-th iteration.
Since the Predictive Path Stressing algorithm selects, in each iteration i, the edge e that maximizes the marginal gain per unit cost, given by C(Ps'' +ule.j.)) C((Px))) If Ed C E, this value is at least as large
J.
as the average marginal gain per unit cost in the optimal solution given by [PIT-C(Pxx)) given the solution xi-1, we have
Therefore.
OPT
c(P,x*) - C(P,xx->)
C(P,x' x-= uuuueee ((e. - C(P,x*=1)
J1
J1 PIT C(P, 1
2
(8)
OPT
C(P,x) -((,x(-1)
8: OPT
(P - 1
(9)
Therefore,
B [[(((px)) - C((P,t
(10)
Ji
2 E Pr(E" _3 OPT (PP[T - c(Pxx (Ppxxx PP(E" [ 0|x
(11)
2 OPT (P - c( P. x 1) |
aji
(12)
By taking expectation over - we obtain
aji [[e(P,)) C(P,) 2 E
OPTT
(1PTT
(13)
Re-arranging the above inequality gives:
< E P - (C(P,x--)
aji
(IP C(P, x11)
(14)
OPT
E (IP -(P,x x11)
aji
(IP -
-))
(15)
OPT
E
aji OPT
(IPIT- ((P.--(
(16)
Let / is the number iteration. By applying the inequality (66) iteratively over these iterations, we obtain the following:
E -(I,T-C(Pxx))
<E
PIT
aji OPT
]
aj: OPT }
< E
P
exp
(using 1 - S 7²
Σi= Ji
<
PIT
exp
OPT
al|x'||1
)
<
P|T exp
OPT
31

---

By the terminal condition of the algorithm, C(P,x*) 2 PIT ē and C(P.x < PPT - E so we have
- PIT exp (-
al|x/~1|
(17)
OPT
a aa/x*
P
exp
22
(18)
OPT
a a|1x-1111
exp
(19)
OPT
PP|T
S a||x ||1
P
(20)
OPT
OPT
P
||x- S
In
(21)
Besides, from the inequality
we also have (in expectation)
ajt C OPT
- c (P.
(22)
ajt (IPTT - C (P,x sc(P,))
-((,)x*+ -(
(23)
OPT
aj: (IPIT (P, - OPT ( ((Pxx*11)
(24)
aji S OPT (Since |P C (P,,'(())>()))
-C ((,xx=)))
(25)
OPT
je
(26)
The set of feasible paths can be upper bounded in terms of the maximum path length and the number of nodes. In particular, the number of edges of feasible path is upper-bounded by h T
(since
each edge has weight least Wmin), the number of feasible paths of the is upper-hounded by n". We therefore have:
OPT
In OPT
P|T
|||[[[|1] B 111] + B s
(27)
a OPT
P
In
(28)
a OPT
1 + In
(29)
E
OPT
(1 +
hl(nn) + In + In )
(30)
which completes the proof. See Remarks and for how our ratio generalizes to both linear and non-linear cases, and how the performance behaves when model Jo accurately estimates the exact value.
Remark 1. (Approximation ratio when f& is integer-valued). In Theorem 1, if fs is integer-valued for E [m] and we set E E (0, 1), then running the Predictive Path Stressing algorithm on E yields feasible solution x, i.e, C(P,x) = P(T such that E[[|x|]]] < (1+hln(n)+hn1] OPT
Remark 2. If PPS selectes all edges in the optimal solution, i.e, Pr(E C C = 1, then running the Predictive Path Stressing algorithm E yields solution such that C(P,x) P ? and ||||||||| & (1 + h In()) + In In(1/2))OPT
9.2 Expert Augmentation Efficiency
Theorem 2 (Expert Augmentation Efficiency): Suppose there exists constant 0 such that PP(2) (x(x) > 8) 2 e; on the region fa X(x) > 8), a new expert Ωx+1( is added with gating weight (xx) = [x(x)= > 5ann (0 < ap < 1) and trained to satisfy QN+1(1) 2 cg(x)) for
some (0, 1); then the updated mixture Ω (x) a(x) (x+1(x) (1 a(x)) ((z) satisfies
32

---

KL(g))()) & (L(g]1 7(,, c), where y(d, c) a0(6 + loge) co > 0 and > 0 is a lower bound on [x()>> (())d() dz.
Proof. In the regions where x(x) log and x(x) 6, we add a new expert (x) and extend the gating network so that its output becomes:
g(ar fā(z)
N+1 (x), 0. N+ with
Σ w/(x) =1 1.
(31)
1=0
Without loss of generality and for analysis purposes, we form a new mixture by taking a convex combination of the old mixture and the new expert:
(x) = (x) (x)) + - ([x) P(x).
(32)
We choose the gating function a(x) to focus on regions where x(#) > 6. particular, we set:
a(x) 1fx(x) _))())
(33)
and for simplicity we take a(z) = ag for those æ with x(æ) > where 0 < ag < Next, we consider the KL divergence between ((x) and the original mixture l(xz).
KL(g]](2 = =f ((x) log
g(x) dr, (xx)
(34)
and the KL divergence between g(x) and the updated mixture P2(x))
KL(g))()) = ((x) log ((x) dx
[x(x)
/ ((x) log n(r) (x) + (())) da
(x))
/ ((x) (z)) (og)))))))))
+ (1-a(xx) [(x)) de
< ((x) log ((x) - a(x) log((++(() (1 - axx)) log (2x) dx
((x)) log ((x) de / (()) (x)) do f a()0)(( (x))))
log log ((x)) dr.
(35)
We can achieve the above because the logarithm is concave (and thus - log is convex), Jensen's 's inequality implies that:
log 2'(x)) = log ((()) QN+1 (x) + (1 a()) a(x)) 2(x))
(36)
2 a(x)) log (x) + a<x)) log Q(r)
= - (x) < -a(x) log 2N+ (x) - - -a())))))))))))))) log 2(x).
/ ((x)) log St (x) de - / ((x)) a(x) log U2+ (x) dx - (())(( -a())) log 2(x) dr.
(37)
Recall that the KL divergence between q and Q is defined as:
33

---

KL(g]] = / ((x)) log g(x)) dr (1xx)
(38)
= ((x) log g (0x) dx -
(()
((x) dr.
Similarly, for the updated mixture (z), we have the following.
KL(g)10) = / ((x) log g(x) dæ
(1(x))
(39)
/ ((x) log ((x) dx
f log St (x) dz.
((x))
If we subtract the original divergence from the new one, the terms involving ff g(x) log ((x) dx cancel, leaving:
/ ((x)) log log do / q(x)) log (x())) dz
KL(g))() KL(g][()
/ ((x)) ((x))o de / ((x)) log 12(x)) dr
(40)
= f (()) dx + / u((x) u(x))oog log M(x) de.
q(x) (gg / g(x)(( alz) do
KL(g))0) [L <
+ (x) ((g
(()) log (x)) - g(z)(1 - a<x)) log (xx) dæ
+ (z))
(()) [og (x) log (xx) dr.
(41)
This completes the derivation. We have shown that the difference in the KL divergence between and the updated mixture S' and that between y and the original mixture bounded above by:
(L(g))2)) - (L())l)) - - = a(x) 1o - log 2(x)) dz.
(42)
Notice that the region where x(xx) < 5, the indicator in (xx)) is zero, only integrate over the region where x(æ) 8. Setting axx) = ag on that region, we obtain:
((x) log 2N+1(2) Mxx)
KL(g]12) (())))))))))))))))))) < -ap
dz.
(43)
x(x)>8
Now, for any with x(x) > 8, we have log
((s) ((())
> 6 so that g(m)
((x) cxp(6). Suppose further that the
new expert is designed such that, on this region, (x) 2 eq(x), where E (0, 1) is constant. Then it holds that:
(x+1(x) 2(x)
g(x) 1(r)
2
c exp(o).
(44)
34

---

Taking logarithms gives:
(N+1(4)
2 8 + log c. log 2(x)
(45)
Thus, if we let:
7 q(x) dr,
(46)
x(x)>
and assume (through technical equivalence between ((r) and p(z)) that 17 2 co 0, then obtain:
[ ((is)>6 (xx) log 2N+1(T) dr 2 (6 + log c) co-
2(x))
Therefore, the reduction KL divergence satisfies:
KL(gl192)) kL(g s -ao (6 + log c) E0-
Defining:
7(6,e) (ō + log c) 60:
We conclude that:
(L(g))12)) S (L(9) ((6,c), c),
which shows that the addition of the new expert decreases the KL. divergence by at least (6,, c) > 0. Thus, this completes our proof.
Corollary 3 (Effectiveness of Expert Addition and Gating Retraining). Suppose that at each iteration, new expert is added in regions where the discrepancy x(x) > 8, and the gating network is retrained using a softmax function that produces a convex combination of expert outputs. The updated mixture then takes the form (((++((x)) = E (x)0 where the new gating weights wf(x) are derived from softmax layer.
We have that the loss function for the gating network, defined as the KL divergence
Lg (Sg) - / g((x) g(00)oog log
( E w/ (x; Sy) (4(x) dx
is T.g- -mooth and "ty-Strongly convex in neighborhood of the optimal parameter S Then, if we update the gating parameters via gradient descent with learning rate small enough ensure convergence, the KL divergence between the target distribution ((x) and the current mixture ( (z) decreases by at least a fixed amount y > O at each iteration. That is,
KL. (112(()))) S KL (0112(()) ->
As result, the sequence mixtures (2)) converges to g(x), in the sense that
lim KL (1)l120) = 0, so (x) + q(x) almost everywhere. 100
Finally, if (ax) good approximation of the true target distribution p(z)-for example, because comes from properly trained energy-based model-then the mixture also converges to p(r). In the limit, we obtain the desired equilibrium where
2(x) g(x) p(z),
showing that the mixture model has successfully learned the target distribution through iterative refinement.
Proof: After the new expert is added, the gating network is retrained using softmax layer that produces new weights
35

---

exp(f((x))
wx(x) E exp(f((x))
i= O....,,N N+1
that the updated mixture becomes
N+1
('(x) - Σ (.))).
We define the gating network's loss as the KL divergence
((z)
Lg(Sa) = /0(x) Σ/= w/ Sg) (2)
dx.
Because softmax produces convex combination, the mapping Ei=o w; Sy) 24(x)) is convex
in the gating weights. Under the assumptions that Lgg is Tyy-smooth and -t-Strongly convex near the optimum Sy, update the parameters by gradient descent:
(t+1) = -.0 1l V Lg((
By standard results, the error in the gating network decreases as
||= - -g s (1 17 (2p4g - my T3L1)) 11 - -gl1?
ensuring convergence provided the learning rate Ty is chosen sufficiently small. As the gating network converges, the new mixture (z) = N w/ sg) (x(x) becomes an even better approximation of q(x), reinforcing the reduction in KL divergence
established earlier. If this process of detecting regions where xxr) > adding new expert, and retraining the gating network is repeated iteratively,
we obtain sequence of mixtures (2())))) for which
KL(gl10(+)) (L(g))) (6,
Thus, by repeated application, we ensure
lim (L(g)
8000
Assuming that g(x)) is good proxy for p(x) (due proper training of the EBM), it follows that
(x) + ((x) and ultimately (x)()x) + p(z),
establishing the desired Nash equilibrium p(æ) q(x)) 1((x).
9.3 Normalization Free Function
Theorem 3 (Normalization Free Function): The objective function min, maxa (KT((())()))))) (L(l))))); is normalizing free which is independent with Z.
36

---

Proof. By definition, the KL divergence between p(r) and g(z) is (L = ff /((x) log p(z) dr.
q(0)
Since ((x) exp( Fie)
we can rewrite it as:
2
p(z) log p(x) dx
KL(plla)
g(x))
/ p(z) (log - log q(x)) de
/ p(z) ((g) (logpppp))ceeooo dx / p(x) log g(z) dx
E(x)
/ p(x) log))o))())) p(x) do
exp
p(xx log
dr
Z
/ p(x) log do / p(x)) E(x)
log 7 dr
log()))(( do + / ((x) dr + log Z f p(x) dx
log))ogp(x) do p(z)E(z) de + log 2,
Similarly, the KI. divergence between ((x) and g(x) is:
KL(2]]g) / ((x) log [2xx) dr g(z)
((x) log 01x) dx / (xx) log logg(z) dr
f ((x) log l(x) dx / (xx) [ [[xx] log z { dx
/ ((x) log M(x) do + / Mx))((r) do + log 2 / Mxx dæ
1
((x) log f(x) dr 1 / [(z) dz + log Z
The difference between the two KI. divergences is then:
/ p(x) log(()) dr + / B(x) dx + log Z
KL(pllg) KL
/ | (gg + 1 (zx)) F(x)) do + log 7
/ p(z) logp(z) dx log de I p(=))(x)) - 1 - [(=))((a)) dz.
= p(x) log de / (x)) log (x)) da
Entmpy Different
( [Fo [F(Fo())))
Notice that the log Z terms cancel, so the difference is independent of Z.
Corollary 4 (Reduction to Energy Expectation Difference) Under the setting of Theorem 3, the minimax objective
min max { KL (I(lg))) - KI((2)1)) }
37

---

is equivalent (up to additive and multiplicative constants independent of 0) to
min 8
R Ra-p
[a((t] - E Sems(/Eo(1)) [o(x)]
Proof. By Theorem we have:
KL(pllg) (L(S2]l)) - p(x) logp(z) do - / p(x) log ((x) do - (/ do (47)
/ (xx) log ((x) dx)
(48)
= / p(x) log p(x) dr / (2xx) log ((x) dx + [2((z) p(x)] log g ((x) da
(49)
= / plx)) log logp(z)
(2(x)) log ((xx) de
(50)
+ /I((s) -M(x)] [--E(()) -log Z dr
(51)
+ } 1 |I((0) -s((x)] Eo(x) do (since (Ib(e) [Io(a) 2(x:)] dr 0
(52)
= C + 1 (Eempl [o (Eo) - Evwn [o(x)))
(53)
Since adding the constant C and scaling by 1/7 do not affect the location of the minimizer in 0, follows that
arg min (T(())l)) (T(()))))) arg min B
[F(((<))) R. (o)()))))
8
which establishes the claimed reduction.
9.4 Differentiable Reward Function
Lemma Let Se : X' + R be differentiable on an open set X' C R". The reward function R(x) is differentiable on X.
Proof. Let (G 8, I; x) be a neural estimator of shortest-path cost from source node to target node parameterized by 0. Define the reward function as:
R(x)=
Σ L (,, (a.t)K
- log (1+ (T(])
Penalty
Smooth feasibility Term
where L(²) Ite-cr is sigmoid function with slope parameter <> 0, T(x) log (1 (1+0 e*). applied coordinate-wise, and T' > 0 is the feasibility threshold, and к 0 is regularization hyperparameter. We aim to show that R(x) is continuously differentiable on any open domain X' c m First, the estimator So is deep graph neural network constructed composition of L differentiable layers:
3o Ft. 10..o/1-11 St-1 f
where each Ss may involve affine maps, ELU activations, attention mechanisms, and message-passing steps, all of which are differentiable. Hence, by the chain rule, (o,G,8,45) is differentiable on X. For each (s, t) e K,, define:
38

---

(x)((x) L (Bo(G, -T).
Since To is differentiable and {2) is smooth ( ( ) on I with L'(2) = -(2)) (1 L(2)), it follows from the chain rule that (x) is differentiable:
V (x = L' (3,(G, -T) V
Summing over all (s, t) in K, we obtain:
1 (x) = E Lx,((x)
(x.1)EX
which is finite sum of differentiable functions and therefore differentiable on X. Let Y R - R be the rector-valued softplus function such as:
T(x) [log (1 ea ...)....,oo log (1
e²m))
where each component Y; (z,) is differentiable, with:
e
T/ (1:)
+ c = L (x:))
Hence T C (R"),, and so the m [ E T, (z;) also differentiable as finite sum of differentiable functions. Now we consider the scalar penalty A(x) = log (1 + (x) Because T, (an) for all Tú, have (x)]] > and log(1 + u) is smooth on (0, oc). Hence, by the chain rule:
VA(x) 1 [x)]
V
Σ Y, (z:)
which is well-defined and continuous on R Putting both together that F F(x) = - fx,(x) and A(x) log (1 + |x) is both differentiable. Therefore, the reward function R(x)
Fxx) x (xx) differentiable on any open set X' C R=" i.e., R E (X).
This concludes the proof.
9.5 Reward Estimation Consistency
Theorem 4 (Reward Estimation Consistency) Assume that Ω has converged properly, for any perturbed latent vector 2 ;= 24 + V V,,, c)) with small é > 0, we have R (x,) > R (x.). where &; Mo c).
Proof. prove this theorem, we first prove that for a well-converged Qa. Ma is Lipschitz- continuous.
Consider the decoder My : Rd R.. composed N layers. For j to N each layer computes:
h ( Rel.
where hn =2 E Rdd W, E Rd xd and by E IRd; The output layer computes:
X Ma(zi) q (1) Wyhn=I+ bN,
with WN PxdN-1 and by E T.P. To prove that Ma Lipschitz continuous, consider two inputs 2;, 2 E Rdd We aim to show:
[[Mo(2)) Mc(21)l K||z; &ell
where K is finite constant.
39

---

Starting from the output layer:
- (Mo(s))MM(E)))) [lan(1 - q (2:)
W +b W
(2:)
[WW(( (et) - -
S Wwlllala (2.) - 1
where [[ 2|2 denotes the spectral norm of WN. For each hidden layer j = down to
|1 [11g/t) (s)) (8.) (1a)(1)2)) 9, (h) (11=))
[|
(2.) + +b²)
Re, b;)il
I (2)) -w,
(since ReLU is I-Lipschitz)
< [[5 1-
By recursively applying these incqualities, we obtain:
| - 11
1
II
[ WWWN--- A -1112 (1(6=)) - -165011
[W +11/22 1| -zil--
E:|1-
At the output layer:
[M4())) Mo( [WWlla|n (8:)
-N--11-
Substituting the recursive bound:
N || - -ell-
- - S Hwsill
Define K = -1 [[2ll2 To ensure K is finite, we enforce bounds (Layer Normalization) on the spectral norms: |[Willa 5j, where sj are finite constants. Then:
K
II j=1
Sj.
If we choose s, = < for all j. then K < S < 1, which is finite. Therefore, M& is Lipschitz continuous with Lipschitz constant K, satisfying:
[[Ma(2)) Ma(2))l K| 2:|l-
Thus, we finished proving that M& is Lipschitz-continuovi continuous. Given Pe is well converged, with Ma being Lipschitz continuous and differentiable, a small learning rate é induces small change in latent vector 2; which results in a small change the data point x; reconstructed by C-VAE, We can use the first-order Taylor expansion for small Az;
& 2;
*;
MM (2: R Mo (z:) Jm, (zi) Az;
where JMH (2:) is the Jacobian matrix of Ms at From the update rule:
Az = 24 = E. V., R(x.)
40

---

Thus, the change in X; is:
&; x; JMs (zi) = JMm (zi) R(x.)
Since x, Ma (zi), by the chain rule, have:
V R(x,) JMg (2) (2)) R(x,)
Therefore:
x; -xx, ~ JMs (21) JMg (21) Vx, R(x,)
Let 3 = JM, (2)) JMs (zi), which a positive semi-definite matrix. Thus:
& x, ~ é V R(x;)
Using a first-order Taylor expansion of around x;
AR = R(x,) - R(xx) = Vx, Rx,) T
(x: -x,x x:)
Substituting &; X,, we obtain:
Z T (x,
Since is positive semi-definite and 0:
AR 2 0
More specifically, AR = 0 if and only v R (x;) = 0. Otherwise, R > 0. Therefore, under the given conditions and for sufficiently small ē
R(x)) R (x;)
This completes the proof.
Remark 3 (Trade-off between Lipschitz control and expressiveness), Imposing strict Lipschitz constraints the decoder Ma. for instance by enforcing [|W,l22 S s; for all layers that I S K, guarantees global smoothness but inevitably limits the network's 's representational capacity. Such strong spectral normalization can suppress high-frequency components essential for accurate reconstruction, leading to degradation in performance. Hence, while a bounded Ms ensures stability, often sacrifices fine grainer generative fidelity.
Remark (Local Lipschitz behavior on latent support). In practice, it is not necessary to enforce global Lipschitz constraint across all decoder layers. The decoder Ms only needs be locally Lipschitz over the high-density region of the latent prior p(z) = N 1). Formally, there exists constant Talnat > O such that for any 21, 22 within f2 {= p(2) c).
[M(22)) < Z 22ll
This localized smoothness naturally emerges from the VAE objective, which regularizes qo (2|ar toward p(z) and thereby aligns nearby z 's with semantically close reconstructions.
41

---

9.6 Safe Ball In Latent Space
Assumption (Edge-cost Lipschitz). Each edge function fe is Le Lipischhit on [0, be] and
Ly == max Le- cEE
(A1)
Assumption (Estimator Uniform Error). The SPAGAN surrogate satisfies
s, (Pa [s)] S Esaa
(s,
(A2)
Proposition 2 (Safe Ball In Latent Space). Let x, -M) c) be feasible and denote the true
safety margin by Á min(s.t)e (SP (s,tssstx xx) T] 0. Assume well trained SPAGAN's error (S
uniformly bounded by (0 S Espa A). With h [T/wmin]> L max Tez m |E|, and
decoder-Lipschie constant L.M every latent vector satisfying
Â spa
|| 21l12
S
h h V LM
decoded MM(2, for which 3o 8, (;, T 2espa for all (s, () KC; Thus, exploration within this latent ball guarantees provable safety and restores near full feasibility.
Proof. We begin by recalling Decoder Ms Idd "R" (with [E) is globally LM -ipsccitiitz
[ Mo(22, e)ll S LmIl21 22/12,
42 22 Rdd.
(54)
With Wmin == min. We. let h = [T/ //miin] every shortest path ý under threshold T satisfies [i] < h. For any two perturbations x, x' and any (s,t) KC, we have:
[SPo(s,t;)) - SPo(s,t;x') = Ee((x,
PEP
CEA
Le|xe - X-1
(55)
< h L ||x -x'll1
< h L, Vm ||x x'112.
Switch to the estimator using assumption A2 and by applying the triangle inequality, which states la + b
cl < |al + +6
|c|. we have:
42

---

]o(s, - (s) = - + (Po(s,t;)) ts,,,t;
+ (P,(s) txx,
< (0(8,1;x) - SPo(8,1;))
+
SP (8,44, - -0 4; x.)
truc-cost gap
S Cyo
Scspa
+ -
Exp
= 25spo
+ [SPa(s, - SPa(s,t;x.)
225pp
h vm Mo(z,c) Mb
+ h m m M ||: - 2+112
= -130(s, t; Ja t; x.)] 2 -22spa + h v Lm 2x112)
(56)
The initial solution x, is feasible with a true safety margin Á that SPa 2 T+A Moreoever, from Assumption 2, we have
33 (,, SPc -Pc (s, S Espa
(57)
Expa 39 (G, s, x,,) - SPa (s, t; xxxx) S Expa
From this compound inequality, are interested in the left-hand side to find lower bound for 3o s;
Eppa & 3o (G, 8, 1,,;,, SPa (8,
3o s, 2 SPc (s, xx,)
Capa
(58)
3o (G, s, t,),
2 T + A Capa
Since the proposition states the condition || - 2 llz
S
A A-exp and we know that
hT. /mI
h, L-f, /m, Lm are all positive, this implies h |||
2. 21 I
Espa. hence:
(e, s, xx) 2 Jo (,,,t;;.)) - [3o 8, t;x) - 30 (G, s, t;
(Note: since A B - AA Bl)
(T + A Espa [oo 8, x; 30 (G, x:xx)] (Note: Substituting the lower bound for 30 G, s, x; ))
2 (T++ + (spa) (25.gu + h Ly /m LM ||| - zz l12)
(Note: Substituting the upper bound for [30 - -o (xx)))
(59)
T A
Capa 26 - h L /m LM ||I - 2+112
T + A 3Cppa hL.ymLL 1/2 -2212
> T + A
3Copo A - Cspp))
(Note: Since
hLL hhL,/mLM| || 2a 111 2 -(A Csppa
T A 35 3Espa A + Espa
T - 2Espa
This completes the proof.
43

---

10 DETAILS EXPERIMENTS AND ABLATION STUDIES
This section provides comprehensive details of our experimental setup, evaluation metrics, and abla- tion studies. We aim to assess both the effectiveness and generalizability of the proposed Hephaestus framework across a range of real-world network topologies and baselines. The experiments are designed to evaluate performance from multiple perspectives; solution feasibility, budget efficiency, scalability, and training dynamics. In addition, ablation studies are conducted to isolate the contri- butions of key architectural components including the SPAGAN --asedd path estimator, mixture of generative experts, and reinforcement- based refinement- and to examine how each contributes to the overall performance. We also detail the hyperparameter choices, compute infrastructure, and exact solver setups used for benchmarking.
10.1 Dataset Details
2 provides detailed statistics of the real-world network datasets used in our experiments, each chosen to represent different structural and functional properties. The Email network is a directed communication graph among 1,005 individuals with 25,571 edges and a diameter of 7, capturing organizational email interactions characterized by strong community structures. The Gnutella dataset represents decentralized peer-to-peer file-sharing system from August 2002. It contains 6,301 nodes and 20,777 directed connections, with small diameter of 9 and low clustering, reflecting its unstructured topology. The RoadCA network is a large-scale undirected graph of California's 's road infrastructure with approximately 1.96 million nodes and 2.77 million edges, and unusually large diameter of 849 typical of sparse, planar transportation networks. Finally, the Skitter dataset models the Internet at the autonomous system (AS) level using traceroute data, comprising 1.7 million nodes and 11 11.1 million directed edges with a diameter of 25. This dataset captures the hierarchical structure of inter-AS connectivity. Collectively, these datasets span wide spectrum of scales, densities, and network types, forming a comprehensive benchmark for evaluating the scalability and generalizability of Hephaestus and its baselines.
Table 2: Statistics of real network datasets used in experiments.
Data
Type
Nodes
Edges
Diameter
Email
Directed
1,005
25,571
11
Gnutella
Directed
6,301
20,777
9
RoadCA
Undirected
1.96 M
2.77 M
849
Skitter
Directed
1.7 M
11.1 M
25
10.2 Hyperparameter Settings
In Table we provide a detailed summary of the hyperparameters used across the three core phases of the Hephaestus framework: Forge, Morph, and Refine. These settings were chosen through extensive trial runs and empirical tuning identify the perf-perf configurations. The selected values aim to ensure training stability, strong generalization across diverse graph instances, and consistent performance throughout the pipeline.
In Forge, we train the SPAGAN model to estimate shortest-path costs efficiently. After trying several network configurations, we found that using 5 layers of Graph Attention Networks (GAT), each with 512 hidden units and 8 attention heads, gave reliable results on a wide range of graph structures. The ELU activation function was chosen because it helps avoid the dead neuron problem that can happen with ReLU, especially during early stages of training. For the learning rate, we tested multiple values and observed that 5 x 10-4 consistently led to stable convergence within 3000 epochs. Larger learning rates often made training unstable, while smaller ones slowed down progress too much. When choosing a loss function, we initially experimented with mean squared error (MSE), but observed that it was highly sensitive to a few long-path outliers, which harms the overall learning process. address this, we adopted the Huber loss, which combines the benefits MSE and MAE (Mean Absolute Error): it behaves quadratically for small emors to ensure smooth optimization and transitions to a only linear penalty for large errors. This property allowed us to reduce the influence of extreme outliers while still penalizing them, resulting more stable convergence and improved
44

---

Table Hyperparameter Settings.
Component/Phase
Parameter
Value
Phase I: Forge
SPAGAN (8e)
Network Architecture
5 Shortest Path GAT layers, 512 units, 8 heads
Activation Function
ELU
Learning Rate (a)
5 x 10
Optimizer
Adam
Adam 12
(0.9, 0.999)
Batch Size
256
Training Epochs
3000
Loss Function
Huber Loss
Max per-edge budget (6,)
T
Phase 2: Morph
EBM (g(x))
Network Architecture
6 MLP layers, 512 units
Activation Function
Swish
Learning Rate (OEEM)
2 10-1
Optimizer
Adam
Regularization (5)
1.0
Batch Size (EBM Update)
256
Training Iterations (Minimax)
50000
Mix-CVAE (!2)
Latent Dimension of each CVAE (d)
128
Encoder Architecture
GAT Encoder + MLP
Decoder Architecture
MLP Decoder
Activation Function
LeakyReLU
Learning Rate (ag)
10-4
Optimizer
Adam
Batch Size (CVAE Update)
256
Initial Experts (Nini)
1
Max Experts (Nmaw)
9
Expert Add Threshold (5)
0.425
KL Weight ($KL)
0.1
Prior
N(0, 7)
Phase 3: Refine
RL Agent (I))
Policy/Value Net Arch. Activation Function
MLP layers, 256 units
LeakyReLU
Learning Rate (a.n..
1 x 10
Optimizer
Adam
Discount Factor (YRL)
0.99
Reward Smoothness (()
5.0
Reward Cost Weight (xx)
0.05
Gradient Ascent Step (êaл)
2 10
RL Training Episodes
50000
Top-K Solutions
10
45

---

predictive accuracy across diverse graph instances. The maximum per-edge budget b. = T defines the allowable range of perturbations and ensures that a feasible solution always exists for any input graph. Specifically, by assigning The = T to every edge least T. thus trivially satisfying the QoSID constraint. This choice guarantees feasibility without loss of generality, while still leaving many rooms for the model to explore more efficient and sparse perturbations to reduce total perturbation cost. Finally, we used a batch size of 256, which provided reliable gradients while fitting comfortably within GPU memory during training.
E, the cost of any path becomes at
In Morph, the EBM is a 6-layer MLP with 512 units and Swish activation, which improves smoothness
of the learned energy surface. The EBM is trained with learning rate of 2 x 10- using a minimax schedule for 50,000 iterations, along with regularization term 4 = 1.0 to prevent gradient explosion. For the Mix-CVAE, a latent dimension of 128 was sufficient to model the diverse structure of perturbations, while the encoder incorporates graph context via GAT layers. The KI. weight fK1 = 0.15 balances reconstruction and latent regularization. We initialize with a single expert and allow expansion up to 9 experts, adding new CVAEs when the density ratio X > 0.425, indicating insufficient coverage by existing experts.
as a 4-layer MLP with 256 units per layer and LeakyReLU activations which helps mitigate vanishing gradients. It commonly occur during late-stage training when the model begins to converge and reward differences become minimal. conservative learning rate of 1 x 10 was selected to ensure policy stability, while a discount factor of 0.99 promotes long-tern planning over greedy improvements. The reward shaping parameters Ç = 5.0 and 0.05 control the smoothness of feasibility and cost feedback, respectively. We perturb the latent vector with a small gradient ascent step &GA = x 10-3 to explore -nrrrdiimpooiing directions, and retain the top-10 10 feasible solutions per episode to enrich the training buffer. We follow the model
In Refine, we implement policy
architecture of PPO based on works 77 72 73
Hardware Specification. All experiments were conducted on a workstation equipped with an Intel Core 19-14900K CPU, 192 GB RAM, and 2x NVIDIA RTX 4090 GPUs (total 48 GB VRAM). While the GPUs played a critical role in training the SPAGAN, MiX-CVAE, and RL components efficiently, the large RAM and CPU core count were especially important for evaluating exact solvers like Gurobi and approximation algorithms. In particular, we relied on Gurobi to refine and benchmark outputs from baseline methods such as DIFFILO, refinement steps often required solving Icage-scale ILPs with huge number of constraints and integer variables, where runtime and memory bottlenecks were significant. Thus, the high-performance CPU and 192 GB RAM were essential for verifying solution quality and feasibility in our exact evaluation pipeline.
aedfict-nd-Seaaeee and I.-MILPOPPT, etc. These
Gurobi Heuristic Setup (Important). To assess the quality of learned solutions and evaluate optimality under exact conditions, we use Gurobi as a ground-truth solver. However, solving the full QoSD problem exactly is highly challenging at scale due to the exponential number of potential constraints. Recall h
denotes the maximum number of edges in any feasible path, where T is the budget threshold and Wiin is the minimum edge weight. Since each path consist of at most h edges, and the graph contains n nodes, the total number of feasible paths is upper-bounded by nh. This results in an exponentially large constraint space in the corresponding MILP formulation. This issue is especially severe when the threshold T' is high, since a larger number of short paths remain feasible. In our experiments, instances with more than 10,000 nodes at maximum density when all feasible paths are explicitly enumerated under medium T.
observed that Gurobi consistently fails solve problem
To address this scalability bottleneck, we adopt a heuristic strategy based on sampling for Gurobi refinement, which we refer as Gurobi-Heuristie Instead of enumerating all paths, we iteratively sample the current shortest paths between critical tarret pairs- vairs-using Dijkstra- and enforce path constraints only on these sampled paths. Gurobi then solves the reduced problem and updates the edge weights accordingly. This process is repeated: new shortest paths are sampled under the updated perturbation x, and the solver is rerun. The iteration stops once no newly sampled path violates the threshold constraint T, thereby ensuring feasibility without needing to enumerate the full exponential set of feasible paths shorter than T. This strategy is crucial for making feasible to refine the solutions produced by any ML-based DIFFILO and Predict-and-Seaat Search-on on large-scale graphs. Without it, exact refinement via Gurobi would be computationally infeasible due to the overwhelming number of constraints. To further
Hephaestus or baselines such as
46

---

improve performance under such settings, Gurobi is configured with heuristic-oriented parameters including "Heuristics=0.5" "MIPFocus=1" and full threading support.
10.3
SPAGAN Generalization
250
200
120
100
80
medidedd
150
100
20
Fune Value
Fratt Value
True Value
(a) Graph 1000
(b) Graph 2000
(c) Graph 3000
(d) Graph 1000
(c) Graph 2000
(f) Graph 3000
Figure 6: Predictive Accuracy Across Different Graph Sizes.
120
Prodiceed Value Thue Value
Prodicted Valae Trus Value
100
1000
600
800
500
400
600
300
200
200
100
Prod ctod Value Tue Value
20
40
50
50
100
120
100
200
500
400
300
500
700
300
200
400
500
800
1000 1200
(a) Frddös-Rényi Model
(b) Barabási-Albert Model
(c) Watts-Strogatz Model
(d) Rénōs-Réényi Model
(c) Barabási-Albert Model
(f) Watts-Strogatt Model
Figure 7: Predictive Accuracy Across Different Graph Topologies.
In our framework, SPAGAN model (5o) plays vital role in Forge, where it serves as fast and accurate estimator shortest-path costs. These estimates directly support the Predictive Path Stressing (PPS) algorithm in generating initial feasible perturbation vectors without requiring full shortest-pale path solver calls. Therefore, we want to evaluate the generalization capability SPAGAN, by designing two sets of experiments using synthetic graphs. The first examines how well the model scales across different graph sizes, while the second investigates its performance across distinct graph structures.
To test scalability, we trained SPAGAN on Erdös-Rényi (ER) graphs with 1,000 nodes at maxi- mum density, and then evaluated its predictions on ER graphs with larger sizes 220es-2,000 and 3,000 nodes-also also at maximum density. EnguresSJand, show the results. The scatter plots in Figure (a-c) compare SPAGAN's predictions with ground-truth shortest-path distances obtained via Dijkstra's
47

---

algorithm, In all cases, the predicted values closely follow the diagonal (Predicted = True), indicating high prediction accuracy. The corresponding error histograms in Figure 7 (a-c) further support this, with prediction errors concentrated around zero and minimal high-magnitude deviations, suggesting both low bias and low variance.
In the second evaluation, to evaluate SPAGAN's ability to generalize across different graph topologies, we fixed the training on ER graphs with 1,000 nodes and tested the model on two structurally distinct types: Barabási-Albert (scale-free) and Watts-Strogatz (small-worid), each with the same node count. As shown in Figures 6 and SPAGAN's predictions remain highly accurate. The scatter plots in Figure 7 (a-c) continue to show strong alignment between predicted and true path costs, and the histograms in Figure 7 (a-c) maintain the same eπror concentration pattern seen in the size generalization study. Taken two evaluations together, these results demonstrate that SPAGAN capable of generalizing effectively across both varying graph sizes and structural types. Its predictive accuracy and stability under diverse conditions make it reliable and efficient surrogate for shortest-pate estimation within the broader Hephaestus framework.
10.4
Robustness to SPAGAN Errors and Exact-Patl Safeguard
10.4.1 Exact-Path Feasibility Check and Safeguard (PPS-I)
Let G = EV be a weighted directed graph, where each edge E has a perturbed weight fa(e determined by the allocated budget ze from the perturbation vector TR!g) Given set of source-target pairs {(s), 4)) and threshold T > O, we define the overall feasibiiiy rate of perturbation x as
Feas(x) m Σ ISSPo 2 T)
where the shortest-path length under perturbation is given by SPa(s,t; minpe)((s.) Eeep fe (z.). PPS-I takes any candidate x (from PPS or RL) and performs: (i) compute (3,, (2) for all pairs via Dijkstra; (ii) while da(s;, (2) < for any i, identify a shortest path p² and increment (eeeeep by the minimum amount to push d (s;, (2) to T. This yields final & with Feas($) ()) =
Proposition (Guarantee of PPS-I). Let IC be the set of QoSD pairs with threshold T > 0, and let the per-pair slack under perturbation be
slack (s, t) = max T SPa(s,t;x)},
with total slack S(x) = E(.t)ex slacky (s, t). Assume every edge-weight function fe()) is non- decreasing and locally Lipschitz, with a positive lower bound on its incremental gain:
fe(ra + 1) - fe(xe)
Gmin 0.
Then, for any initial perturbation x, PPS-I returns an updated & such that SP (s, 2 T for all (s, t) E IC, thereby ensuring 100% feasibility. Moreover, the total additional cost is bounded by
|x|||
|||||
< 1_ S(x).
Cmin
Proof. At each iteration, PPS-I selects violating pair f) with SP 1; x) T. extracts its exact shortest path p² under current x, and increases budgets on edges E p* by the smallest nonnegative increments Are such that
Elferr + A - fe())) 2 T -T-PPcss,tt))
eEp*
Since each fe is non-decreasing, all shortest-pant path lengths are non non-decreasing under the update. Hence the total slack S(x) = ")x max(O, T SP e; x}} strictly decreases whenever there is violation. Because IC is finite and slack is bounded below by 0, PPS-I must terminate in finitely many steps at some with S(x) 0, i..., (P, 2 T for all (s, t) E K.
We now relate the total increase in edge weights to the increase in budgets. From the discrete lower bound assumption
fe(x. + 1) (ze) Cmin+
48

---

each unit increase of Ie increases the corresponding edge cost by at least Cuin- For multiple steps, we can sum this inequality Az, times:
Az.
fe( - fe(2))
[fe +j+1) -f(( +
Cmin
(Gt xe).
This simply means that fe grows at least linearly with slope Cmin- In other words, the function lies above a line of slope Cmin passing through (Ies fx()) Summing this inequality over all edges yields
E ( - fe(xx)) (e CEE
E - xe) = Cmin || x||1.
Cmin
cEE
The left-hand side represents the total increase in edge weights caused by all PPS-I updates. By construction, this cumulative increase cannot exceed the initial total slack S(x). since S(x) quantifies exactly the total amount of shortest-path length that must be compensated reach feasibility. Hence
Cmin
&
x||1 S ((x)
| - ||x||1
S(x)
Dually, the incremental upper bound (by Lipschitz) implies
fae) - fe(xe) I Cmax (&e - Iee
- S Cmax ||Ax|||. eEE
To eliminate the initial violations, the cumulative increase of shortest- path lengths must be least the total deficit one needs to fill, which is lower-bounder by the initial total slack:
E[fa E
fe(see) 2 S(x).
Therefore,
S(x)
((x)
S Cmax ||Ax||1
|| ||x||1 2
Cmax
gives us the desired sandwich bound feasibility at termination.
S(x) Cmax
|
||x||2 S
S(x) Canin
together with guaranteed
10.4.2 Robustness to SPAGAN Prediction Noise
The purpose of this experiment is to evaluate the robustness of HEPHAESTUS under imperfect shortest-path predictions produced SPAGAN. In real-world deployment, SPAGAN may encounter topologies or edge-weight distributions not seen during training, leading to degraded path estimates that could cascade through subsequent stages of the pipeline. Hence, it is crucial to quantify how such prediction noise affects overall feasibility, cost efficiency, and the effectiveness of our safeguard module PPS-I.
To model degraded SPAGAN predictions, we inject independent zero-mean noise with rate n E (30%, 10%, 5%) into SPAGAN-estimates shortest-path scores during PPS and RL decision-making Let d(s, denote the SPAGAN-predicted distance, we perturb it as d,, (s, t) d(s,, t) + Es,ts where Es,t is sampled to achieve the target noise level (calibrated on the validation split). We then evaluate: (i) PPS (greedy optimization on noisy estimates); (ii) RL refinement latent space (also using noisy estimates for reward shaping); and (iii) PPS-I, which applies exact post-check correction via Dijkstra guarantee feasibility. We report feasibility rate (%) over m 50 source tauree-target pairs and the total perturbation budget cost.
From Table 4 (with m=50 source-target pairs), observe four key findings:
1. PPS degrades under noisy predictions: Feasibility drops by up to 22% (e.g., RoadCA with 30% noise), and cost increases by about 20% as perturbation budgets are misallocated to irrelevant edges.
49

---

Table Sensitivity SPAGAN noise and exact-path safeguard (PPS-I). We report feasibility (%) and total cost after each stage; PPS-I also shows wall-clock fix time (s) for the exact Dijkstra-basee correction.
Dataset
Noise
PPS Feas.
PPS Cost
RL Feas.
RL Cost
PPS-I Feas.
PPS-I Cost
PPS-I Time
Email
30%
90.0
3284
94.0
2911
100.0
3005
20.2
10%
94.0
3185
100.0
2802
5%
3157
2640
100.0
2712
0%
100.0
3091
100.0
2691
100.0
2691
0.0
RoadCA
30%
78.0
13730
86.0
10985
100.0
11061
214.8
10%
88.0
12556
92.0
10148
100.0
10795
137.2
5%
92.0
12123
94.0
9892
100.0
9907
48.6
0%
100.0
11283
100.0
9184
100.0
9277
0.0
RL refinement recovers performance: RL improves feasibility and reduces cost over PPS by leveraging gradient signals in latent space. For instance, the RoadCA dataset with 30% noise, RL improves feasibility from 78% to 86% and reduces cost from 13,730 to 10,985.
PPS-I ensures 100% feasibility in all cases: Regardless of SPAGAN noise level, PPS-I con- sistently restores feasibility via exact Dijkstra-based correction. This confirms the pipeline's correctness guarantee.
Cost penalty of PPS-I modest: Even in the worst case (RoadCA, 30% noise), the PPS-I cost increases by only 199 relative to the ideal (0% noise) case i.e., 11,061 vs. 9,277, while fcasibility remains perfect.
10.5 Resilience to Weak Initial Data
This experiment aims assess the system's ability recover from weak or suboptimal initial data and to validate whether the latent-space refinement mechanism truly corrects, rather than amplifies, early- stage imperfections. In other words, we examine the self-reinforcing capability of the Morph-Refine loop under noisy or incomplete initialization. Our framework is explicitly designed to mitigate the influence of suboptimal or noisy solutions generated the early phase. Unlike heuristic post- processing, our refinement operates entirely in the latent space, where reinforcement-leamiie agent optimizes a differentiable reward that reflects both feasibility and cost efficiency. Consequently, even if the initial perturbation samples from the PPS stage are imperfect, the refinement progressively corrects them rather than propagating the errors.
(RL)
To validate this behavior, we conduct cycle-level robustness experiment. After each refinement cycle, the top-k highest-reward latent samples are added back the pre-trained solution set D forming self-reinforcing feedback loop between the Morph (Mix-CVAE) and Refine (RL) phases. This feedback mechanism provides two benefits:
(i) Mix-CVAE retraining incorporates improved latent samples, enriching the coverage of feasible solution modes.
(ii) The RL policy learns on an increasingly structured latent manifold, enabling discover even better perturbations in subsequent cycles.
On Email with 260. the improvement saturates after roughly five refinement cycles, yielding a total cost reduction of 18.5%. On the larger-scale RoadCA dataset, cost reductions continue to increase even after eight cycles, peaking at over ~ 26% under high thresholds. These results confirm that HEPHAESTUS remains robust to weak noisy initial data, and that the latent-space feedback loop effectively improves data quality over successive cycles.
Table reports the relative cost reduction (%) across refinement cycles under varying feasibility thresholds T. Both Email and RoadCA datasets exhibit clear monotonie improvements, showing that later cycles consistently achieve higher-quality perturbations.
50

---

Table 5: Cycle-level improvement in cost reduction (%) across thresholds T. The values represent budget savings relative to the initial solution (Cycle 0).
Dataset
Cycle
T-140%
T=180%
T=220%
T-260%
Email
0
0.00
0.00
0.00
0.00
1
4.01
5.25
6.82
7.95
2
8.67
10.15
12.44
14.21
3
10.86
12.50
15.03
17.88
4
11.07
12.97
15.58
18.04
11.23
13.11
15.98
18.52
RoadCA
0
0.00
0.00
0.00
0.00
7.01
8.55
10.11
11.58
2
10.91
12.98
15.03
17.34
3
12.83
15.21
17.85
20.19
4
15.67
17.89
20.45
22.87
5
17.42
19.53
22.10
24.53
6
18.27
20.33
22.98
25.66
7
18.51
20.76
23.42
26.09
8
18.61
20.89
23.54
26.21
Gmail Dataset
Goutella Detanet
30
75
29
rowndd tan
(baded mas.
Thraded
RoadCA Dataset
Sutter Datacet
Tendiah
Minded tons
Thenked 20m
Soffoeeneen Cydle
Figure 8: Evolution of Total Budget during the Refine phase (RL agent training)
51

---

10.5.1 RL Convergence Behavior under Different Problem Scales
To analyze how the RL policy behaves across different problem scales, we provide detailed train- ing statistics on two real-world datasets: Email (1005 nodes, 25,571 edges) and RoadCA (1.96M nodes, 2.77M edges). Both experiments conducted using clean SPAGAN predictions to isolate convergence dynamics.
Table 6: Training-phase convergence statistics on datasets of different scales, We report feasibility, expected total budget, and reward over three distinct training stages,
Email
RoadCA
Training
Feas. (%) Expected Total Budget
Fens. Expected Total Budget
Stage 1: Feasihility Search Behavior
Episodes 0-5K
1921.65
15147.21
551.5
Episodes O- 10K
40.0 100
2641.58 64453.49
5-6 37 - 2348.62
Stuge 2: Cost Optimization Behavior
Episodes 5K 15K
98.0
15117.21 + 2697.81
561.95
871.72
Episodes 10K 35K
98.0 d
64453.49 9265.72
2348.60 62 3075.00
Stage 3: Convergence
Episodes 15K 50K
98.0 2
2697.84 + 17
874.2 +
Episodes 35K- 50K
98.0
9265.72 = 49
3975.08 =: 37
As shown in Table training proceeds in three stages based on episode count. In Stage (Episodes 0-5K / 00100)), the policy rapidly improves feasibility (maximizing term 1 of reward function) from 80% to 100% (Email) and from 40% to 100% (RoadCA), demonstrating its ability to learn constraint satisfaction from scratch. In Stage 2, the focus shifts to cost optimization (term 2 of reward function): total budget drops significantly from 15147.21 2697 84 on Email, and from 64453.49 to 9265.72 on RoadCA, while feasibility remains approximately 98%. Finally, in Stage 3, the reward and cost metries converge with low variance, e.g., on RoadCA, reward stabilizes at 3975.03 37 and budget at 9265.72 72 = 49, confirming stable convergence even in large-scale settings.
10.6
Comparison with Alternative Latent Optimization Strategies
central motivation for the HEPIAASSTS framework is that reinforcement learning (RL) can effectively optimize latent representations beyond what static population- based methods can achieve. To verify this, we conduct controlled comparisons against two alternative latent optimization strategies: Bayesian Optimization (BO) and Evolutionary Strategies (ES). This experiment aims to evaluate whether the RI-baasd refinement phase indeed provides superior sample efficiency, scalability to higher latent dimensions, and robustness noisy SPAGAN predictions.
Each method is evaluated on the Gnutella dataset under varying latent dimensionalities reporting the final perturbation cost (lower is better) and feasibility rate (%). All evaluations are conducted using clean SPAGAN predictions (i.e., without additional noise) for a fair comparison.
Table Comparison between RL-based refinement and alternative latent-space optimization strate- gies. Lower cost indicates better efficiency.
Method
Latent Dim.
Final Cost &
Feas. Rate 1
PPS (no refinement)
4118
100%
RL (Ours)
16
3435
100%
64
3419
100%
Bayesian Opt. (BO)
16
3590
98%
28
4055
52%
Evolutionary Strat. (ES)
16
3612
94%
64
3598
98%
52

---

Table 8: Comparison of RL and ES under different levels of SPAGAN noise. All experiments are conducted on the Gautella dataset with latent dimensions d E {16, 64). Lower cost indicates better performance, and higher feasibility denotes stronger robustness.
Method
Latent Dim. d SPAGAN Noise (%)
Final Cost
Feas. Rate
PPS
0
4118
100%
5
4221
96%
10
4318
92%
30
4392
86%
RL (Ours)
16
0
3435
100%
5
3596
98%
10
3714
92%
30
3832
86%
64
0
3419
100%
5
3550
98%
10
3668
96%
30
3775
92%
Evo. Strat. (ES)
16
0
3612
94%
5
3798
91%
10
3945
87%
30
4201
81%
64
0
3598
98%
5
3756
95%
10
3912
91%
30
4187
85%
We observe that BO performs well only in low-dimensional latent spaces (d S 30) but suffers from severe sample inefficiency and surrogate modeling errors as dimensionality increases. ES scales better converges slowly, often resulting in suboptimal costs. In contrast, our RL-based refinement achieves both the lowest final cost and full constraint satisfaction (100% feasibility) across all latent dimensions. This confirms that the seiic-ggradeet-barr refinement is more robust and sample- efficient than model-based (BO) population-base based (ES) strategies, especially in high-dimensional latent manifolds.
Robustness under Noisy SPAGAN Predictions. To further evaluate the resilience of these methods, we extend the comparison noisy settings by injecting controlled levels of perturbation into SPA- GAN's path predictions (5%. 10%, and 30%). This additional test closes the loop with the robustness discussion in Section 10.4.2 and examines how optimization strategies behave when their latent objectives are corrupted by upstream model uncertainty.
From these results, we observe that Evolutionary Strategies are more sensitive SPAGAN prediction noise, likely due to their strong reliance on the quality of the pre-trained solution set Deol generated during the Forge phase. In contrast, our RL-based refinement maintains both higher feasibility and lower cost under noise, demonstrating stronger robustness across latent dimensions and noise levels.
10.7 Energy Distribution Convergence during Minimax Training
The objective of this experiment is to evaluate how well the generative model Mix-CVAE (12) can progressively align its generated samples with the energy distribution implicitly defined by the Ahergy-Basee Model (EBM) during adversarial co-training. Specifically, we aim to assess whether, as training proceeds, !2 learns to generate samples that lie in low-energy regions -those that the EBM assigns to real data. Since the true data distribution is unknown and cannot visualized directly, we rely the EBM's energy outputs as surrogate for this alignment. The hypothesis is that if Ω successfully learns the real data distribution, the energy distributions fake (generated) and real samples will gradually converge.
53

---

(a) Step
(h) Step 32
(c) Step 64
(d) Step 128
(c) Step 256
Figure 9: Energy histograms comparing real versus fake data across minimax training. The x-axis assigned by the Energy-Base Based Model (EBM), while the y-axis indicates
denotes the energy the frequency samples observed at each energy level. Real data samples (blue), drawn from the ground-truth dataset Deml typically have low energy values and cluster near zero the left of the x-axis, reflecting the EBM's preference for them. Fake data samples (orange), generated by the Mix-CVAE 22, initially have higher energies but gradually shift leftward training progresses. This convergence the two distributions indicates that Ω is learning to generate samples that align more closely with the EBM's learned energy landscape.
Figure 9 illustrates this convergence process by plotting energy histograms over five key training steps. Real data from the dataset Deol are shown blue (low energy region on left-side x-axis), while fake data sampled from Qt are shown in orange the right side. At early stages such Step 8 and Step 32, there is sigmificant contrast: the EBM assigns low energy to real samples, which are densely concentrated near the left of the histogram, while fake samples occupy much higher energy regions, reflecting their low realism. As training progresses (Steps 64 and 128), the two distributions begin overlap, indicating that Q is learning produce more realistic outputs that better match the EBM's learned energy profile. By Step 256, the energy distributions of real and fake samples nearly coincide, suggesting that Si has successfully learned generate samples that the EBM considers indistinguishable from real data. This result highlights key insight: although the EBM is explicitly trained minimize energy for real data and maximize it for generated data, the Mix-CVAE generator gradually catches up. Initially, it produces unrealistic, high-energy samples, but through adversarial feedback. learns synthesize low-energy (high-quality) solutions. Thus, we demonstrates that the generator effectively "chases" the moving energy boundary set by the EBM and ultimately converges regions of high data likelihood.
10.8 Latent Space Visualization
40
35
20
15
(a) Linear
(b) Quadratic Convex
(c) Log Concave
Figure 10: Conditional Latent Space Visualization via UMAP for the trained Mix-CVAE conducted on the same synthetic graph but under varying threshold values T across different edge weight functions: Linear, Quadratic (Convex), and Log- Concave. Each point represents a latent vector corresponding to solution, colored by the associated threshold T. The structure of the latent space reveals how the model differentiates solution representations under changing constraints and cost dynamics, with clustering patterns indicating sensitivity to the underlying threshold conditions.
In this experiment, the goal is to assess whether the latent space learned by the conditional generative model (Mix-CVAB) meaningfully captures different constraints T the same graph. Specifically, we visualize the latent vectors z using UMAP projections to examine whether different threshold values result in separable or clustered embeddings-aa indicator of successful conditional representation learning. Figure T0 shows the latent space organization when Mix-CVAE, is trained and evaluated on the same synthetic graph but under three different edge weight functions: Linear, Quadratic (Convex), and Log-Concave. Across all three subfigures, we observe clear gradient-based separation and distinct
54

---

Email
RoadCA
Skitte
Figure 11: Conditional Latent Space Visualization for the trained Mix-CVAE under the Linear weight function setting. Each point represents a latent vector z corresponding to a generated solution, colored by either the input graph type the threshold T' The presence of distinct clusters separable regions in the latent space suggests that the model captures meaningful variations related to graph structure and problem-specife constraints, indicating successful conditional encoding.
clusters aligned with increasing values of T. This pattern suggests that the generative model is sensitive to threshold constraints and learns to organize the latent space accordingly. Interestingly, the separation structure varies with the cost function type: Linear produces smooth band-like transitions, while Log-Concave shows more localized clustering, potentially reflecting its sharper cost escalation characteristics.
Figure T complements this analysis by testing Mix-CVAE on real-world graphs (Email, Gnutella, RoadCA, Skitter) under the same linear edge cost setting. Again, latent vectors are visualized and colored by threshold. Across different graph topologies, we still consistently observe separable clusters and gradual transitions in z-space with respect to T, indicating that the generative model generalizes across input graphs and captures structural information relevant feasibility under constraints. In particular, datasets with greater structural diversity (e.g.. Skitter and RoadCA) exhibit more complex spatial patterns, highlighting the model's ability to encode both graph topology and constraint semantics.
10.9 Impact of Expert Addition in Mix-CVAE
The goal of this experiment is to evaluate the effect of adding more experts in the Mix-CVAE architecture modeling capability and final solution quality. Figures 12 14 and toggethhr provide a comprehensive view of how the number of experts (3, 5, 7, 9) influences the generative model's ability approximate the true solution distribution and optimize budget outcomes.
Cnery diniiuion
combutor
Shars darridoo
Mo-ONE diriuuee
Drenis under TMU
Ewety'
Swets
Thrtpp 201
(n) 3-Exppert
[b) S-Expert
7-Expert
(4] 9-Expert
Figure 12: Comparison between the distribution from the EBM and the distribution from the Mix- CVAE with varying numbers of experts on synthetic network with maximum density. Increasing the number of experts improves mode coverage and alignment with the target EBM distribution.
Impact of Expert Addition on Generative Modeling. Figures 12 and 13 compare the energy distributions of real solutions (as evaluated under the EBM) and fake samples generated by the Mix-CVAE across both synthetic and real network settings. When only 3 experts are used, the generated samples show poor alignment with the real data distribution, evidenced by noticeable discrepancies between the orange increases, this alignment improves signficantly-indicatnn that the model is better able to capture the underlying modes and structure of the target distribution. This validates the core motivation behind expert addition: increasing the number of experts enhances the model's capacity to represent multimodal solution spaces. Furthermore, Figure [4] provvdes additional insight by visualizing the latent space of the trained Mix-CVAE via UMAP on synthetic graphs. Each point represents latent vector colored by its corresponding threshold T. With more experts, the latent space becomes more
and blue (EBM) bars. As the number of experts
55

---

MICCNE
MI-CHNL
Grargy duri
Grargy Burdbuuto
Eneigy
Eargy
Emei sale IRM
Eangy or I8M (d) 9-Expert
(a) 3-Expert
(b) 6-Expert
7-Export
Lingg on CUM [o] 3-Expert
(eway
Chicg andiTIO (c) 7-Export
Cy (d) 9-Export
(b) S-Export
Enwrg
Enargy cantbratioo
Kamgy
(b) 5-Expert
7-Export
(4) 9-Expert
Banggr
Bargy
Eweey EBH
Enitgy enter ES (b) 6-Expert
Entty CBM (d) 9-Export
(4) 3-Export
7-Export
Figure 13: Impact of adding experts on real-world networks. From top to bottom: results on Email, Gnutella, RoadCA, and Skitter networks.
organized, exhibiting distinct clusters that correspond different threshold levels. This structured separation suggests that the model is learning to conditionally represent diverse solution modes, improving both interpretability and the quality generated samples.
(a) 3-Expert
(b) S-Expert
7-Expert
9-Expert
Figure 14: An example of conditional latent space visualization for the trained Mix-CVAE on the same synthetic graph and pairs but different thresholds. Points represent latent vectors z, colored by threshold T'. Clear clustering shows the latent space captures meaningful patterns.
Impact of Expert Addition on Total Cost. To evaluate whether the improved modeling capacity from adding more experts in MiX-CVAE leads to better optimization outcomes, we analyze its effect on the total budget required to solve QoSD instances. Figure [5 directly illustrates this downstream impact by plotting the average total budget (in log scale) achieved across range of graph densities (from sparse to dense) under three distinct edge weight functions: Linear, Quadratic Convex, and Log Concave. We observe a consistent trend: increasing the number of experts from 3 to leads to a progressive reduction in the final budget required to satisfy the QoSD constraint across all edge weight settings. The gap between configurations becomes more pronounced as
56

---

Fermh Eiaan)
21
214
Busqe
0.2
0.4
0.6
0.5
02
0.5
3.5
02
0.4
0.6
Demiyy
Dersiy
Dendty
(a)
Linear
(b) Quadratic Convex
(c) Log Concave
Figure 15: Impact of adding of experts (3, 5, 7, and 9) the resulting total budget across varying
graph densities, testing on the synthetic graph under (a) Linear, (b) Quadratic Convex, and (c) Log Concave edge weight functions.
graph density increases, where solution spaces become more complex and multimodal. Notably, the 9-expert model consistently outperforms the others, achieving the lowest e under nonlinear edge weight functions like Log Concave and Quadratic Convex. This confirms that enhanced expressiveness in the generative model enables better exploration and exploitation of feasible regions in the solution space.
These results demonstrate a clear benefit of the expert addition strategy: as the number of experts increases, Mix-CVAL becomes more capable of capturing diverse solution modes, which directly improves solution quality. The budget savings are especially significant under higher density graphs, where the optimization problem is inherently harder and requires stronger modeling capacity to discover high-quality solutions.
10.10 Performance under Non-Linear Edge Weight Functions
The main paper presents only performance comparisons on real-world networks under the linear weight function, where the QoSID problem can be reformulated as an IIP and solved exactly. This section will show performance of Hephaestus in real networks under non-linear edge weight settings where such reformulations are no longer tractable for existing ML-based or optimization baselines. Specifically, T evaluates the Quadratic Convex setting, where each edge weight follows the form f=(2.) 2)=²). This convex formulation rapidly increases edge cost budget increases, meaning that even small increases in budget can suffice to surpass the threshold T. Fortunately, the latest versions of Gurobi support solving quadratic objectives, hence, exact solver is still included in this setting for benchmarking. In contrast, Table examines the Log- Concave case, where the edge weight is defined as (xt. N(In z²). This class of function is much slower grow, achieving total cost above often requires significantly more budget per edge. Importantly, Gurobi and other solvers do support log-concave objectives natively in mixed-integer formulations, making exact optimization infeasible. Therefore, only approximation methods methoos--Adapive Trading (AT), Iterative Greedy (IG), Sampling Algorithm (SA) and our method Hephaestus are reported in Table 10
Email
Gnutella
RoadCA
Skitter
Method
140%
180%
220%
260%
140%
180%
260%
180%
220% 260%
180%
220%
260%
Trading
1933
4261
6647
7771
1558
3267
5842
7518
7747
12880
1876
20821
290772
11463
1637765
2743321
Iterative Greerly
1978
4301
6697
7825
1942
3635
7561
9774
7888
1893
19369
12049
347454
889621
19672555
3173690
Sampling Alg.
3687
8835
12532
16384
2803
4609
12670
15126
16271
28856
55014
60716 521783
1580349
2478424
5741999
Exact Solver
7646
$409
7051
Repbseatus
4256
6602
7711
1529
5631
7327
4955
9253 14107 20493 171157
493507
9794447 1716387
Table 9; Performance of HEPHAESTUS and baselines on four real datasets at different thresholds T.
The best is highlighted in bold excluding exact solution. (Convex)
Performance under Quadratic Convex fo: In Table 9 (Quadratic Convex), Hephaestus consistently achieves the lowest total cost among all approximation methods. On smaller graphs like Email and Gnutella, its performance is often close to the exact solver when available, while on larger graphs like RoadCA and Skitter, where the exact solver fails to run aun-Heehaestus still maintains strongest performance compared with remaining available baselines, highlighting scalability and robustness to nonlinear cost functions.
57

---

Email
Gnutella
RaadCA
Skiller
Method
140%
180%
220%
260%
140%
180%
220%
260%
140%
180%
220%
200%
140%
180%
220%
260%
Adaptive Trading
3309
7595
12812
14759
6589
10897
15268
21147 20218
29266
46248
69457
11 1130533
4191546
6931595
9/97272
Therative Greedy
3473
7706
13095
16042
66.19
11571
16092
21491
21M1
30189
48197
71405
1339904
5174196
8751811
10111558
Sampling Alg.
4404
9589
15218
18336
7980
13957
19612 23286
38427
68551 95579
128118 5621568 7573689
10220892
15464201
Rephaestue 3188
7320
10942
12318
6403 10754 13949 19110 17299 27242 42311
64796
424188 1115779
2608813
7064231
Table 10: Performance (Total Attack Budget) of HEPHAESTUS and approximation baselines on four
real datasets under Log Concave edge weights. Lower is better. Best apppoximatton//HPHAEESTT result is bolded. Exact Solver fails to run.
Performance under Log Concave fe: Table 10 (Log Concave) further highlights Hephaestus' scalability and generality. Despite there no longer ground-truth solver, Hephaestus consistently outperforms AT, IG, and SA across all thresholds and network sizes. The gap in total budget becomes particularly significant for larger graphs and higher thresholds, as approximation methods struggle to effectively navigate the slow growth dynamics of the log- log-concave function. By contrast, Hephaestus's generative-refinen framework allows it to adapt to the more complex shape of the cost landscape.
These findings validate that Hephaestus remains highly effective in settings where other solvers or learning-based methods are inapplicable. Moreover, the results underscore the flexibility of Hephaestus across diverse graph structures, ranging from small, sparse email networks to mas- sive Internet-scale topologies like Skitter. Moreover, unlike many existing learning-basee basedd meth- ods-such as DIFFILO or Predict-and Sand-SSarch-weee functions, Hephaestus is built to work across a wide range of cost models. This is possible because it separates the learning of solution structures (e.g.. which paths to attack) from the specific form of fa (e.g.. linear, quadratic, log-concave). In fact, owing to its generative modeling approach in latent space, Hephaestus does not rely on any particular formula for how edge costs increase, hence, can handle different types of cost functions without needing to change its architecture. This flexibility makes Hephaestus more practical for real-world use, where both the structure of the network and how costs behave can vary significantly from one case to another.
are designed specifically for linear cost
10.11 Soundness of the Reward Function
Recall that the reward function used in the Refine phase of Hephaestus is defined as follows:
R (x++)== = / (G,
x log (1 + |3++
(60)
(i) Smooth fcasibility temm
(ii) Soft penalty term
Ours
Budget
214
Ours
Durs
Total
Total
MB09
5000
so0ted Modell aucist axcre
10000
Spisode
Episade
(a) Graph 1000
(b) Graph 3000
(c) Graph 5000
Figure 16: Evolution of Total Budget during the Refine phase (RL agent training)
This reward formulation encourages policy т to generate solutions that are both feasible (increasing the sigmoid- based term for all critical pairs (s, f)) and efficient (penalizing a large total budget using the second term). The key idea is to guide the policy to find a balance between maximizing feasibility and minimizing the total cost.
In Figure 17 we show how the total budget evolves over training episodes across three different edge weight settings: Linear, Quadratic Convex, and Log- Concave. A noteworthy observation across all plots is that the budget initially increases sharply during the early training phase, especially visible in episodes 0-3000. This behavior can be explained as: at this stage, the RI. agent has not yet learned effective policies and instead prioritizes feasibility, attempting to push more critical paths above the required threshold T, often by over-allocating budget. This is aligned with the feasibility
58

---

Budget
Total Budget
Total
Ours
Ours
Adaptive Trading
Acaptive Trading
Ours
Adaptive Trading
scres
2000
<comg
Jesto
20000
Episode
Eissdee
Epsode
(a) Linear
(b) Quadratic Convex
(c) Log Concave
Figure 17: Evolution of Total Budget during the Refine phase (RL agent training)
2002
100
13.0
Smoothh Foasbiility
Foasibllity
Faaxibilitt
Reward
Smarth Bt
Smooth biy
Smaohh Feasbily
10075 7000
W0126
100
10032
20003
10033
20003
1000
10030
70000
20015
1000 50000
Spisode
(a) Linear
(b) Quadratic Convex
(c) Log Concave
Figure 18: Evolution of Feasible Solution quality (blue, left axis) and Agent Reward (red, right axis)
over training episodes.
curve in Figure 18 (a-c), where the smooth feasibility skyrockets during the same initial phase, confirming that the agent is successfully raising path costs. As training continues and the feasibility nears saturation (close to a value of 10, meaning that the total cost of the shortest paths for all 10 target pairs exceeds the threshold 7), we begin to observe a transition: the agent shifts focus toward reducing the overall budget while preserving feasibility. This can be seen Figure 17 a). where from episode 3000 onwards, the total budget starts steadily decline. Correspondingly, Figure 18 shows that feasibility remains stable, indicating that the agent is successfully optimizing the second term of the reward without sacrificing the first. However, particularly interesting phenomenon occurs around episode 7000. As the agent becomes increasingly focused on minimizing the cost penalty, temporarily neglects feasibility. This is reflected in Figure 18(a) sharp dip in smooth feasibility around that episode, suggesting some paths have dropped below the threshold. Simultancously. Figure 17a) shows sudden plunge in total budget. confirming that the policy has aggressively reduced edge weights to cut cost. Eventually, the agent corrects this behavior. Realizing that dropping feasibility lowers the total reward, the policy re-adjusts recover feasibility, while continuing to reduce less impactful edges. This adaptive dynamic exactly what the reward function is designed elicit: the policy explores aggressively, corrects when needed, and eventually converges to a high-feasibiliny low-cost solution.
it selectively increases the budget critical edges to
This self-regulating behavior is consistent across Quadratic Convex (Figure 10b/1 lb) and Log- Concave (Figure 10c/1 Ic)) settings, although the trajectory is slightly more gradual in the latter due to the slower cost escalation of log-concave functions. The reward curves (in red, Figure 11) grow monotonically across all cases, confirming that the policy is indeed optimizing the reward function effectively. Overall, these experiments confirm the soundness of the reward design. It provides a useful training signal that balances feasibility and efficiency, and encourages intelligent exploration-expplee coooraatoo-exlloiaattion exploitation dynamics during learning.
10.12 Relative optimal gap convergence
The goal of this experiment is to evaluate how effectively and efficiently each method approaches the optimal solution terms of total budget, using relative optimal gap as the key metric. This gap quantifies the percentage deviation from the best-known solution, where lower values indicate better performance and zero denotes exact optimality. As observed in the Figure [9 existing learning-baat based baselines, such as L-MILPOPT. mrdicttanddSeamte exact solver like Gurobi to reduce their optimality gap. While this refinement phase eventually helps those methods converge, it often takes several thousand seconds and incurs substantial computational cost. In contrast, Hephaestus with Gurobi refinement (red curve) starts with high-quality initial solutions, thanks to the expressiveness of Mix-CVAE, and rapidly converges to zero gap much
and DiffILO weeuuireeureeeeeeeeeeeeeeuueeeee post- posst-roccessing using an
59

---

L-MILPOPT
25
Predict & Search AT
20
Diffilo
Ours(PPS-I)
15
Ours(Gurobi)
10
0
1000 2000
3000
4000
5000
6000
Figure 19: Convergence comparison of the relative optimal gap across Hephaestus and baseline methods under the Linear cost setting. The relative optimal gap measures the percentage deviation from the best-known (optimal) solution, with lower values indicating better performance. Existing ML-based methods POPT, PeedictanddSeargee DifiILO) gradually reduce their gaps over time through external solver refinement (e.g., Gurobi), but typically require thousands of seconds. In contrast, Hephaestus with Gurobi (red curve) rapidly converges zero gap due to its initial solutions and efficient generative modeling. Hephaestus with PPS-I (green curve), although not exact, achieves low gaps in significantly less time, offering fast and practical alternative.
faster. This demonstrates the synergy between generative modeling and reinforcement learning in guiding the solution space effectively. Meanwhile, Hephaestus with PPS-I (green curve) does reach exact optimality, as PPS-I is an approximation algorithm that does not enforce all path constraints exhaustively. However, it consistently achieves low optimality gaps in fraction of the time compared to exact methods, offering an effective trade-off between solution quality and efficiency. An interesting observation in the curve is the initial rise in total cost during the first few seconds, after which the value quickly plateaus. This behavior comes from the fact that the initial solution generated by the RL policy т- not fully satisfy all feasibility constraints. PPS-I then incrementally increases edge budgets based on marginal benefit-lo-cost analysis, just enough to achieve feasibility, and terminates once all critical pairs satisfied. Thus, this experiment underscores that Hephaestus capable of adapting to different computational needs. delivers fast approximate results with PPS-I, provably optimal solutions with Gurobi deinement-whie consistently outperforming existing baselines in both convergence quality and speed.
10.13 Hephaestus with different feasibility refinement
In this section, we want to show performance of Hephaestus under three refinement modes: initial prediction only (no refinement), refinement via PPS-Inference (PPS-I), and full Gurobi-based refine- ment. These configurations are compared against classical approximation baselines (AT, IG, SA), several (earning-basee approaches (L-MILPOPT, Predict-and-Search DIFFILO), and the exact solver, across synthetic Erdös-Rényi graphs with increasing edge density (p = 0.2, 0.5, 1.0). As illustrated Table IT across all densities, Hephaestus 's initial predictions already yield strong performance, achieving netr-optimal total cost and high feasibility often outperforming other ML-based methods even before refinement. When PPS-I is applied, Hephaestus consistently reaches 100% feasibility with only minor increases in total cost. For instance, at 1.0, the PPS-I solution attains 2236 total budget, just 1.45% above the exact optimum (2204), while completing only seconds-or 200x faster than the full exact solver. This efficiency comes from the fact that the latent generative model already places solutions very close to the feasible region. PPS-I only needs to make slight local adjust- ments (i.e., increasing budgets on few critical edges) to push all violated shortest-path -att constraints
60

---

Table 11: Performance comparison of Hephaestus (Hephaestus) under different refinement strategies (Initial Prediction, PPS-I, and Gurobi) across varying graph densities and benchmarked against baselines. The table reports total budget (lower is better), feasibility rate (higher is better), and running time (in seconds). Results demonstrate that Hephaestus consistently achieves optimal or near-optimal solutions with significantly lower computation time using PPS-I, while Gurobi refinement reaches exact feasibility at higher computational cost.
Graph Density (p)
Method
Total Budget + Feasibility Rate t Running Time (s) 4
AT
163
100.00
44.10
IG
189
100.00
43.23
SA
240
100.00
508.49
L-MILPOPT (Initial Pred.)
462
95.11
15.22
L-MILPOPT (Gurobi)
119
100.00
240.96
P&S (Initial Pred.)
411
95.52
34.57
P&S (Gurobi)
119
100.00
716.31
DIFFILO (Initial Pred.)
386
92.78
28.31
DIFFILO (Gurobi)
119
100.00
412.64
Hephaestus (Initial Pred.)
119
100.00
12.98
Hephaestus (PPS-1)
119
100.00
13.72
Hephaestus (Gurobi)
119
100.00
198.22
Exact Solver
119
100.00
921.18
AT IG
856
100.00
147.35
992
100.00
144.46
SA
1260
100.00
2409.83
L-MILPOPT (Initial Prod.)
2735
84.17
37.56
L-MILPOPT (Gurobi)
639
100.00
1503.01
P&S (Initial Pred.)
2158
82.91
86. 43
0.5
P&S (Gurobi)
630
100.00
117.91
DIFFILO (Initial Pred.)
2027
88.36
70.78
DIFFILO (Gurobi)
630
100.00
2579.00
Hephaestus (Initial Pred.)
631
99.12
21.95
Hephaestus (PPS-1)
637
100.00
24.00
Hephaestus (Gurobi)
630
100.00
1238.88
Exact Solver
630
100.00
5757.38
AT
2288
100.00
298.00
IG
2471
100.00
350.33
SA
3238
100.00
8113.90
L-MILPOPT (Initial Pred.)
8573
78.12
175.08
L-MILPOPT (Gurobi)
2237
100.00
4070.23
P&S (Initial Pred.)
8549
78.36
172.85
P&S (Gurobi)
2204
100.00
4836.18
DIFFILO (Initial Pred.)
7095
83.01
141.55
DIFFILO (Gurobi)
2204
100.00
3919.23
Hephaestus (Initial Pred.)
2215
98.18
28.77
Hephaestus (PPS-I)
2236
100.00
37.12
Hephaestus (Gurobi)
2204
100.00
2218. 16
Exact Solver
2204
100.00
8127.64
61

---

above threshold T. Thus. PPS-I acts as a lightweight yet effective refinmmnt method, ideal for scenarios where runtime is critical but small optimality gaps are acceptable. When exact optimality is required, combining Hephaestus with Gurobi refinement yields the best possible solution (zero optimality gap) in all cases. Importantly, due the strong initialization from Mix-CVAE and RI., Gurobi converges significantly faster than from scratch- demonstrating the value of learning- baaning-based warm starts even for traditional solvers. Compared to L-MILPOPT, Predict-and-Searce
and DIF- FILO, which depend heavily on post-hoc Gurobi refinement and suffer from lower feasibility in their initial outputs, Hephaestus stands out by producing feasible or near-feasible solutions immediately, This results in better cost-feasibility tradeoff's and reduced reliance expensive solver calls.
62


Reviews:
[{"review_id": "5c2Tx6iXKd", "reviewer": "Reviewer_Tyqx", "summary": "This paper proposes Hephaestus, a novel generative modelling framework for solving the Quality of Service Degradation (QoSD) problem, which is formulated as perturbing network edge weights minimally yet sufficiently to degrade service quality. The paper proposes a three-stage sequential solution for the problem:\n\n1. Forge, employing a Predictive Path-Stressing (PPS) algorithm to generate feasible initial solutions with theoretical guarantees.\n2. Morph, a generative modelling approach using Mixture of Conditional VAEs (Mix-CVAEs) guided by an Energy-Based Model (EBM) to model multimodal solution distributions using the output from step 1. as input.\n3. Refine, a reinforcement learning method for fine-tuning latent-space solutions to achieve near-optimality using a differentiable reward function.\n\nThe paper provides rigorous experimental evaluations across synthetic and real-world networks, demonstrating Hephaestus's effectiveness over classical optimization and ML-based baselines, especially under nonlinear conditions. The effectiveness of the algorithm and theoretical guarantees are provided for the algorithm stages. Notably, it can handle both linear and non-linear edge cost functions and a large number of path constraints (that prevents the problem being stated as ILP), which past methods could not.", "questions": "1. The authors should discuss the analysis of failure modes. It would improve the paper to discuss how errors in the learned models (SPAGAN or the generative model) affect the outcome. A suggestion is to include a brief sensitivity analysis or worst-case check: e.g., verify a few final solutions with an exact shortest-path computation to confirm no constraints are violated. Reporting the predictor’s accuracy on shortest path estimates for test graphs would also reassure that the learned model is reliable. If certain graph topologies or weight patterns cause predictor mistakes, acknowledging that and perhaps integrating a safeguard (such as occasional exact path re-checks for critical pairs) could be beneficial.\n2. The authors should consider simplifying the explanations for critical, complex components (particularly Morph phase and latent RL refinement) to improve the presentation.\n3. Dynamic/Adaptive Scenario as Future Work: While not necessary for this paper’s scope, mentioning possible extensions to handle dynamic attacks or repeated games could strengthen the impact. For example, one could imagine an online version of Hephaestus that updates its strategy as network conditions or defences change.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Tackles a highly relevant real-world challenge: QoS degradation via stealthy perturbations in networked systems (e.g., blockchain, traffic control, distributed ML). Although the problem is relevant, it is not broadly relevant but more relevant for the networking community.\n- The paper is well executed and it offers strong technical depth, including theoretical guarantees (i) approximation bounds for PPS i.e. they prove an approximation ratio for the PPS in Forge, ensuring the generated initial solutions are within a bounded factor of optimal – Forge part; (ii) convergence analysis and proofs of Mix-CVAEs with EBM guidance – Morph part; (iii) design of the RL reward and the gradient-based latent refinement (Theorem 4) demonstrate deep technical insight into stabilizing and accelerating training – Refine part.\n- Comprehensive Evaluation and Analysis. The experimental section is extensive. The authors evaluate different graph types and sizes (beyond million nodes size networks) in the main part and in more details in the appendix. They also investigate why Hephaestus performs well: for instance, the discussion notes that the learned model tends to concentrate budget on edges that benefit multiple source–target pairs, whereas baselines waste budget on pair-specific edges.\n- Strong Empirical Performance: Hephaestus shows clear performance gains over a wide array of baselines. On synthetic graphs, it achieved the lowest costs across all tested densities, essentially matching the optimal in linear cases. In more complex cost settings (quadratic, log-concave) where learning-based ILP solvers cannot be applied, it still outperformed the best classical approximations.\n- The paper is generally well-written and flows well, considering the somewhat complex orchestration of the whole proposal.\n\nWeaknesses:\n- High Complexity, Implementation Overhead & feasibility to be deployed in practice: The Hephaestus framework is quite complex orchestration, involving multiple models and training stages (a GNN predictor, a heuristic search, an EBM, several VAE “experts”, and an RL agent). Implementing and tuning this entire pipeline might be challenging. The approach trades off runtime per instance for a heavy upfront training cost on a distribution of graphs. In scenarios where such extensive training is not feasible or when one needs a quick solution for a single new network, this could be a drawback. The practical impact in real deployment scenarios remains partly speculative without a deeper discussion of implementation challenges (e.g., noise, model drift in real environments) – which are not discussed as limitations. Due to the orchestration nature of the approach (3 stages) having a bad outcome of the first (Forge) i.e. having a bad data will likely have influence on the other phases.\n- Clarity. Though generally well written, given the complexity and number of innovations (PPS, Mix-CVAE, EBM, latent RL), the paper’s readability occasionally suffers from density.\n- Focus on Static Scenario: The QoSD problem is treated as a one-shot perturbation planning problem on a static weighted graph. In practice, network conditions and attack strategies might evolve over time. The paper does not address dynamic or adaptive adversarial scenarios (which is beyond its scope, but still a limitation of the current model).\n\nSuitability:\n- The paper is relevant to machine learning and representation community but to a limited extend, there are more suitable venues for this work such as SIGCOMM, ICNP, INFOCOM.\n\nMinor typos:\n- In the supplemental material, the section is named: DETAILS EXPERIMENTS AND ABLATION STUDIES. \nShould it be named: \nDETAILS OF THE EXPERIMENTS AND ABLATION STUDIES or \nDETAILS, EXPERIMENTS AND ABLATION STUDIES", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. How do SPAGAN errors impact final outcomes? Have you conducted sensitivity analysis or exact-path verification to ensure constraint satisfaction? perhaps integrating a safeguard ?**\n\nWe thank reviewer for a pointing that. Despite that SPAGAN demonstrates generalization on graphs with similar topology (Appendix 3.3), we still explicitly address the failure scenario where SPAGAN's predictions degrade under out-of-distribution (OOD) graphs—by incorporating a **robustness safeguard**: PPS-I, described in Section 3.3. PPS-I can refine any intermediate solution (including those from PPS or RL) using exact shortest-path computations via Dijkstra, thereby guaranteeing 100% feasibility of the final perturbation.\n\nIn response to the suggestion for a worst-case check using exact computation to **verify that no path constraints are violated**, we note that our framework already includes such a mechanism. Specifically, we define a feasibility check function that applies Dijkstra to compute the true shortest-path distances after perturbation. We then report the feasibility rate (%), measured as the percentage of source–target pairs whose shortest-path lengths exceed a given threshold $T$ (i.e., successfully disconnected). To further quantify robustness, we also conducted a **sensitivity analysis** by injecting controlled levels of random noise (30%, 10%, 5%) into SPAGAN’s predicted shortest-path values. This simulates various degrees of degraded model performance. We then evaluated the impact of this noise on feasibility (out of 50 pairs) and cost across all stages of our pipeline—PPS, RL, and PPS-I—on two benchmark datasets.\n\n| Dataset  | Noise Rate (\\%) | PPS  Feas.  (\\%) | PPS  Cost | RL  Feas.  (\\%) | RL  Cost | PPS-I  Feas.  (\\%) | PPS-I  Cost | PPS-I  Fix Time (s) |\n|----------|:---------------:|:----------------:|:---------:|:---------------:|:--------:|:------------------:|:-----------:|:---------------:|\n| Email    |        30       |       90.0       |    3284   |       94.0      |   2911   |        100.0       |     3005    |       20.2      |\n|          |        10       |       94.0       |    3185   |       96.0      |   2759   |        100.0       |     2802    |       15.7      |\n|          |        5        |       96.0       |    3157   |       98.0      |   2640   |        100.0       |     2712    |       6.1       |\n|          |        0        |       100.0      |    3091   |      100.0      |   2691   |        100.0       |     2691    |       0.0       |\n| RoadCA   |        30       |       78.0       |   13730   |       86.0      |   10985  |        100.0       |    11061    |      214.8      |\n|          |        10       |       88.0       |   12556   |       92.0      |   10148  |        100.0       |    10795    |      137.2      |\n|          |        5        |       92.0       |   12123   |       94.0      |   9892   |        100.0       |     9907    |       48.6      |\n|          |        0        |       100.0      |   11283   |      100.0      |   9184   |        100.0       |     9277    |       0.0       |\n\nFrom the table, we observe:\n\n- PPS degrades under noise: Higher SPAGAN noise reduces feasibility (up to –22%) and increases cost due to misallocated budget (e.g., RoadCA, 30% noise).\n\n- RL improves robustness: RL boosts both feasibility and cost-efficiency over PPS by optimizing in latent space (e.g., RoadCA: 78% → 86%, cost drops from 13,730 → 10,985).\n\n- PPS-I ensures 100% feasibility: It always restores feasibility via exact Dijkstra correction, regardless of noise level.\n\n- PPS-I cost overhead is modest: Worst-case cost increase is ~19% (RoadCA: 11,061 vs. 9,277) while preserving perfect feasibility.\n\nThese show that Hephaestus is still robust to significant errors in SPAGAN’s predictions. We will include this analysis to the main paper\n\n**W1. Having a bad data in the first phase will likely have influence on the other phases**\n\nThis is insightful point. Our framework is explicitly designed to mitigate the influence of poor-quality initial data through a latent-space refinement loop. In particular, our RL operates entirely in the latent space, where it learns to generate high-quality perturbation vectors that improve feasibility and cost-efficiency, as directly reflected by the differentiable reward function. Crucially, the best-performing solutions—i.e., those with the highest rewards—are not discarded after refinement. Instead, they are added back into the pretrained solution dataset (as shown in Figure 1) to enrich the diversity and quality of training data. This feedback mechanism has two key effects:\n\n1) Mix-CVAE retraining in the next cycle benefits from improved latent samples, allowing it to better capture useful solution modes.\n\n2) The RL policy, in turn, receives a more informative and structured latent space, enabling it to produce even better solutions in future cycles.\n\nWe empirically validate this self-reinforcing effect through the following table, which shows the cost reduction (%) achieved across successive refinement cycles. Specifically, we measure the relative improvement in cost (budget savings) after each cycle where the top‑$k$ highest-reward samples are added back to the solution set. Results on three benchmark datasets under four different feasibility thresholds $T$ clearly demonstrate monotonic improvement with more cycles:\n\n| Dataset  | Cycle | T=140\\% $\\uparrow$ |T=180\\% $\\uparrow$ | T=220\\% $\\uparrow$ | T=260\\% $\\uparrow$ |\n|----------|:-----:|:---------------------------:|:---------------------------:|:---------------------------:|:---------------------------:|\n| Email    |   0   |             0.00            |             0.00            |             0.00            |             0.00            |\n|          |   1   |             4.01            |             5.25            |             6.82            |             7.95            |\n|          |   2   |             8.67            |            10.15            |            12.44            |            14.21            |\n|          |   3   |            10.86            |            12.50            |            15.03            |            17.88            |\n|          |   4   |            11.07            |            12.97            |            15.58            |            18.04            |\n|          |   5   |            11.23            |            13.11            |            15.98            |            18.52            |\n| RoadCA   |   0   |             0.00            |             0.00            |             0.00            |             0.00            |\n|          |   1   |             7.01            |             8.55            |            10.11            |            11.58            |\n|          |   2   |            10.91            |            12.98            |            15.03            |            17.34            |\n|          |   3   |            12.83            |            15.21            |            17.85            |            20.19            |\n|          |   4   |            15.67            |            17.89            |            20.45            |            22.87            |\n|          |   5   |            17.42            |            19.53            |            22.10            |            24.53            |\n|          |   6   |            18.27            |            20.33            |            22.98            |            25.66            |\n|          |   7   |            18.51            |            20.76            |            23.42            |            26.09            |\n|          |   8   |            18.61            |            20.89            |            23.54            |            26.21            |\n\n- On Email with $T=260%$, improvement saturates after 5 cycles, yielding up to ~18.5% cost reduction.\n\n- On the large-scale RoadCA dataset with $T=260%$, cost reductions continue to rise even after 8 cycles, peaking at over ~26% under high thresholds.\n\nThese results show that our pipeline is resilient to weak initial data.\n\n**W2, also Q2. Though generally well written, the paper’s readability occasionally suffers from density.**\n\nThank you for the valuable suggestion. We agree that the Morph phase and latent-space RL refinement are technically dense components, and we appreciate the need for improved clarity. We will revise these sections to enhance readability by summarizing key math intuitively, e.g., describing how Mix-CVAE captures multimodal solution structures from PPS, and how the RL policy operates in latent space to improve feasibility and cost via a differentiable reward function. We will also highlight modularity in the pipeline.\n\n**Q3, also W3: Dynamic/Adaptive Scenario as Future Work for Hephaestus**\n\nThank you for the suggestion. Although Hephaestus currently focuses on the static QoSD setting, its modular design naturally supports extensions to dynamic scenarios. For example, SPAGAN can be retrained incrementally as the network topology evolves, Mix-CVAE and RL can adapt via continual or meta-learning, and our add-back mechanism already forms a feedback loop for iterative refinement. As future work, we plan to explore online variants of Hephaestus that adapt strategies in response to changing network conditions or defenses, potentially framing the problem as a repeated game or adaptive attack.\n\n**Suitability. The reviewer questions whether the paper is better suited for networking venues (e.g., SIGCOMM, INFOCOM) rather than ML conferences.**\n\nWhile our work intersects with networking, its core contributions also lie in generative mixture modeling, latent-space RL, and structured optimization—central topics in the ML community. Furthermore, our framework is generalizable and can be applied to other challenging CO problems, as long as a reasonably good approximation method exists for the Forge phase. We believe this brings meaningful value to the ML community beyond the original QoSD problem."}, {"review_id": "fh7PpVS0E3", "reviewer": "Reviewer_GFJA", "summary": "Hephaestus is a generative framework for Quality of Service Degradation that aims to identify minimal, stealthy perturbations to network edge weights to degrade system performance. It combines predictive path approximation, energy-guided mixture generative modeling, and latent-space reinforcement learning to efficiently generate high-quality solutions under nonlinear cost functions and large-scale constraints.", "questions": "1.Since PPS relies on estimated shortest path lengths from SPAGAN rather than exact values, it’s unclear how errors in this approximation affect the feasibility or optimality of generated solutions. Has the robustness of the pipeline been evaluated under noisy or miscalibrated SPAGAN outputs?\n2.The paper claims generalization to unseen graphs with similar structure, but it is not clear how well the RL-based refinement policy performs when topology or distribution shifts occur. Would retraining be needed for significantly different domains?", "limitations": "1.The quality and diversity of the pretrained solution dataset (Dsol) is critical for the Morph phase, yet the paper does not examine the failure modes when Dsol is sparse or biased. If the initial PPS-based solutions are suboptimal, the entire pipeline may converge to poor regions of the solution space.\n2.The current setup assumes static graph topologies and fixed critical pairs. In practical scenarios (e.g., networks with dynamic routing), it's unclear whether Hephaestus can adapt online or if it requires full retraining from scratch.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "strengths:\n1.Unlike prior methods that treat feasibility search, modeling, and optimization as separate tasks, Hephaestus introduces a unified, generative pipeline that handles them jointly. This end-to-end design addresses the inefficiency and fragmentation of previous methods, especially under large-scale nonlinear constraints where classical ILP or heuristic-based solvers fail to generalize.\n2.Earlier approximation algorithms like Adaptive Trading or Iterative Greedy handle each source-target pair independently, leading to budget inefficiencies. Hephaestus’s PPS algorithm uses shortest-path estimation and a global potential function to coordinate updates across all pairs, providing better resource allocation with theoretical approximation guarantees.\n\nweakness:\n1.The Forge phase depends on a well-trained SPAGAN model to estimate shortest paths, but the paper lacks a thorough sensitivity analysis on how inaccuracies in SPAGAN affect overall performance. If SPAGAN generalizes poorly to unseen graph structures, the entire pipeline could suffer significantly.\n2.Although the RL phase improves solution quality, training policies in latent space still requires iterative rollouts and reward evaluation, which can be computationally intensive. The paper does not provide detailed analysis of RL convergence behavior or resource cost under different problem scales.", "was_revised": false, "final_justification": "", "rebuttal": "**Q1, also W1. It’s unclear how errors in SPAGAN approximation affect the feasibility or optimality of generated solutions. Has the robustness of the pipeline been evaluated under noisy SPAGAN outputs?**\n\nThank you for raising this important question. While SPAGAN shows strong generalization on graphs with similar topology (as illustrated in Appendix 3.3), we also address the out-of-distribution (OOD) setting through a robust safeguard—PPS-I, introduced in Section 3.3 (Inference Process) of the main paper. PPS-I is designed to refine any intermediate solution—including those from the RL refinement phase or PPS—using exact shortest-path computation via Dijkstra’s algorithm, thereby guaranteeing 100% feasibility of the final perturbation vector regardless of SPAGAN’s prediction accuracy.\n\nTo evaluate the pipeline’s robustness under degraded SPAGAN predictions, we conducted a controlled noise injection study. Specifically, we perturb SPAGAN’s predicted shortest-path values with varying levels of random noise (30%, 10%, 5%) and assess the downstream effects on PPS, RL, and PPS-I across two real-world datasets.\n\n| Dataset  | Noise Rate (\\%) | PPS  Feas.  (\\%) | PPS  Cost | RL  Feas.  (\\%) | RL  Cost | PPS-I  Feas.  (\\%) | PPS-I  Cost | PPS-I  Fix Time (s) |\n|----------|:---------------:|:----------------:|:---------:|:---------------:|:--------:|:------------------:|:-----------:|:---------------:|\n| Email    |        30       |       90.0       |    3284   |       94.0      |   2911   |        100.0       |     3005    |       20.2      |\n|          |        10       |       94.0       |    3185   |       96.0      |   2759   |        100.0       |     2802    |       15.7      |\n|          |        5        |       96.0       |    3157   |       98.0      |   2640   |        100.0       |     2712    |       6.1       |\n|          |        0        |       100.0      |    3091   |      100.0      |   2691   |        100.0       |     2691    |       0.0       |\n| RoadCA   |        30       |       78.0       |   13730   |       86.0      |   10985  |        100.0       |    11061    |      214.8      |\n|          |        10       |       88.0       |   12556   |       92.0      |   10148  |        100.0       |    10795    |      137.2      |\n|          |        5        |       92.0       |   12123   |       94.0      |   9892   |        100.0       |     9907    |       48.6      |\n|          |        0        |       100.0      |   11283   |      100.0      |   9184   |        100.0       |     9277    |       0.0       |\n\nFrom the table, with number of pairs is 50, we observe four following keys:\n1. PPS degrades under noisy predictions: feasibility drops by up to 22% (e.g., RoadCA with 30% noise), and cost increases (~20%) as perturbation budgets are allocated to irrelevant edges.\n\n2. RL refinement recovers performance: RL improves feasibility and reduces cost over PPS by leveraging gradient signals in the latent space. For instance, in the RoadCA dataset at 30% noise, RL improves feasibility from 78% to 86%, and reduces cost from 13730 to 10985.\n\n3. PPS-I ensures 100% feasibility in all cases: Regardless of SPAGAN noise level, PPS-I consistently restores feasibility via exact Dijkstra-based correction. This confirms the pipeline’s correctness guarantee.\n\n4. Cost penalty of PPS-I is modest: Even in the worst-case (RoadCA, 30% noise), the PPS-I cost only increases by ~19% relative to the ideal (0% noise) case—i.e., 11061 vs. 9277—while feasibility remains perfect.\n\nWe will include this analysis to the main manuscript\n\n\n**Q2, also Limitation 2. It is not clear how well the RL-based refinement policy performs when topology or distribution shifts occur. Would retraining be needed for significantly different domains?**\n\nSince our RL policy operates in the latent space, its generalization ability depends on three main factors:\n\n1) Robustness of SPAGAN’s predictions: As SPAGAN provides shortest-path approximations that guide the construction of initial solutions, any degradation here may propagate downstream. However, we have shown in Question 1 that even under significant prediction noise, the RL policy still improves feasibility and cost-effectiveness, demonstrating strong tolerance to upstream approximation error.\n\n2) Generalization of Mix-CVAE: Since the latent space is shaped by a Mix-CVAE trained over solution trajectories, its ability to encode meaningful structures for unseen graphs is critical. Fortunately, generalization of VAE-style models across structurally similar data distributions is well-established in the literature [1,2], especially when trained on diverse samples.\n\n3) Generalization of the policy network: The learned RL policy receives a latent vector as input and refines it toward better solution quality. Its ability to generalize to out-of-distribution (OOD) domains depends on whether the latent embeddings of unseen graphs lie within the training support. Prior works  [3,4] in reinforcement learning (e.g., in offline RL and model-based control) show that policies can generalize across tasks when the representation space is sufficiently expressive—which applies here due to the modularity of our pipeline.\n\nHowever, we also believe that if the target domain exhibits significantly different structural characteristics, retraining or fine-tuning the RL policy may indeed be beneficial to fully capture domain-specific latent dynamics. To our best knowledge, few-shot learning for domain adaptation of generative models is a rapidly advancing field [5,6,7], and such techniques can theoretically be incorporated into our framework to enhance transferability with minimal overhead.\n\n[1] Abstract representations emerge naturally in neural networks trained to perform multiple tasks. Nature Communication 2023\n\n[2] Beta-VAE: Learning Basic Visual Concepts with a Constrained Variational Framework. ICLR 2017\n\n[3] Planning to Explore. ICML 2020\n\n[4] Reinforcement Learning with Prototypical Representations. ICML 2021\n\n[5] One-Shot Generative Domain Adaptation. ICCV 2023\n\n[6] Make Your One-step Diffusion Model Better Than Its Teacher. ECCV 2024\n\n[7] The Superposition Using the Itô Density Estimator. ICLR 2025\n\n**W2. Analysis of RL convergence behavior under different problem scales.**\n\nTo address this, we provide detailed training statistics on real datasets with different scale: Email (1005 nodes 25571 edges) and RoadCA (1.96M nodes, 2.77M edges), both with clean SPAGAN's prediction. \n\n| Training Phase              |              |                 Email               |                             |          |                 RoadCA                  |                               |\n|-----------------------------|:----------------------:|:------------------------------:|:---------------------------:|:----------------------:|:------------------------------:|:-----------------------------:|\n|                             |       Feas. (\\%)       |          Expected Total Budget          |            Reward           |       Feas. (\\%)       |          Expected Total Budget          |             Reward            |\n| Stage1: Feasibility Search Behavior |     Episodes 0 – 5K    |                                |                             |    Episodes 0 – 10K    |                                |                               |\n|                             | $80.0 \\rightarrow 100$ |  $1921.65 \\rightarrow 15147.21$  | $201.44 \\rightarrow 551.95$ | $40.0 \\rightarrow 100$ |  $2641.58 \\rightarrow 64453.49$ |  $545.37 \\rightarrow 2348.62$ |\n| Stage 2: Cost Optimization Behavior  |    Episodes 5K – 15K   |                                |                             |   Episodes 10K – 35K   |                                |                               |\n|                             |      $98.0 \\pm 2$      | $15147.21 \\rightarrow 2697.84$ | $551.95 \\rightarrow 874.72$ |      $98.0 \\pm 2$      | $64453.49 \\rightarrow9265.72$ | $2348.62 \\rightarrow 3975.03$ |\n| Stage 3: Convergence        |   Episodes 15K – 50K   |                                |                             |   Episodes 35K – 50K   |                                |                               |\n|                             |      $98.0 \\pm 2$      |        $2697.84 \\pm 17$       |       $874.72 \\pm 14$       |      $98.0 \\pm 2$      |       $9265.72 \\pm 49$       |        $3975.03 \\pm 37$       |\n\nAs shown in the table, training proceeds in three stages based on episode count. In Stage 1 (Episodes 0–5K / 0–10K), the policy rapidly improves feasibility (maximizing term 1 of reward function) from 80% to 100% (Email) and from 40% to 100% (RoadCA), demonstrating its ability to learn constraint satisfaction from scratch. In Stage 2, the focus shifts to cost optimization (term 2 of reward function): total budget drops significantly from 15147.21 to 2697.84 on Email, and from 64453.49 to 9265.72 on RoadCA, while feasibility remains approximately 98%. Finally, in Stage 3, the reward and cost metrics converge with low variance, e.g., on RoadCA, reward stabilizes at 3975.03 ± 37 and budget at 9265.72 ± 49, confirming stable convergence even in large-scale settings. \n\n**Limitation 1. If the initial PPS-based solutions are suboptimal, the entire pipeline may converge to poor regions of the solution space**\n\nOur framework is specifically designed to reduce the impact of low-quality initial data by employing a latent-space refinement loop. Importantly, instead of discarding the highest-reward solutions generated by the RL phase, we incorporate them back into the pretrained solution set (as illustrated in Figure 1). This feedback loop serves two main purposes: (1) it enhances the training distribution for the Mix-CVAE in the next iteration, enabling the model to better capture informative solution patterns; and (2) it provides the RL policy with a richer and more structured latent space, allowing it to generate higher-quality solutions in subsequent cycles."}, {"review_id": "M2I4vVv1XV", "reviewer": "Reviewer_AUQg", "summary": "This paper investigates the Quality-of-Service Degradation (QoSD) problem, where an adversary perturbs edge weights in a network to degrade end-to-end performance while adhering to budget constraints. It introduces Hephaestus, a novel three-phase generative framework comprising: (1) Forge, which uses a Predictive Path-Stressing (PPS) algorithm guided by a shortest-path attention model (SPAGAN) to generate feasible perturbations; (2) Morph, an energy-based, expert-augmented generative model (Mix-CVAE) designed to capture multimodal solution distributions; and (3) Refine, a reinforcement learning agent that explores the latent space to produce optimized solutions using a smooth, differentiable reward.", "questions": "1. How robust is the PPS algorithm when SPAGAN is trained on distributions that differ from the test graph topology?\n\n2. Has the RL refinement phase been compared with alternative latent optimization strategies like Bayesian optimization or ES?\n\n3. How is the number of CVAE experts in Morph determined? Is there a risk of redundancy or overfitting?", "limitations": "YES", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper offers a well-integrated approach to the QoSD problem by combining graph learning, generative modeling, and reinforcement learning, and demonstrates strong empirical performance on large-scale real-world networks.\n2. The paper provides solid theoretical guarantees (e.g., for PPS, latent RL convergence, and normalization-free energy modeling).\n3. Its ability to handle nonlinear edge cost functions (e.g., quadratic and log-concave) distinguishes it from prior work.\n4. The modular structure of Hephaestus (Forge-Morph-Refine) is clearly presented with detailed ablations.\n\n**Weaknesses:**\n\n1. The framework relies on SPAGAN's accuracy—robustness to prediction errors in large, noisy graphs is not extensively discussed.\n2. The expert expansion mechanism in Mix-CVAE adds computational overhead; resource usage and efficiency trade-offs are not evaluated.\n3. The reinforcement learning component (Refine) is theoretically elegant, but lacks empirical discussion on convergence behavior and sample efficiency.\n4. The paper does not compare with recent powerful generative optimization methods (e.g., diffusion-based solvers or large-scale neural MIP solvers).", "was_revised": true, "final_justification": "The additional clarifications and experiments are appreciated. They address most of my earlier concerns and strengthen the case for the proposed pipeline's robustness. I look forward to seeing these additions and updates incorporated in the final version.", "rebuttal": "**Q1 and W1. How robust is the PPS algorithm when SPAGAN is trained on distributions that differ from the test graph topology?**\n\nWe thank the reviewer for this insightful question. While SPAGAN exhibits strong generalization on graphs with similar topology (as illustrated in Appendix 3.3), we also take care of the out-of-distribution (OOD) case. In particular, we include a robust safeguard—PPS-I, as described in Section 3.3 (Inference Process) of the main paper. PPS-I is capable of taking any intermediate solution (including those produced by the RL refinement phase) and further refining it using exact shortest-path computation (via Dijkstra’s algorithm), thereby guaranteeing 100% feasibility of the final perturbation vector, regardless of SPAGAN’s prediction quality.\n\nTo empirically evaluate robustness under distributional shift, we conducted additional experiments in which we injected controlled levels of random noise into SPAGAN’s predictions—simulating degraded generalization. With number of pairs is 50, we report both feasibility (percentage of source–target pairs successfully disconnected, i.e., shortest path > T) and total cost across varying noise levels (30%, 10%, 5%, and 0% of real value) on three real-world datasets used in the main paper (excluding Skitter due to time constraints during the rebuttal). We also assess the ability of both RL and PPS-I to recover from noisy predictions. Results are summarized below:\n| Dataset  | Noise Rate (\\%) | PPS  Feas.  (\\%) | PPS  Cost | RL  Feas.  (\\%) | RL  Cost | PPS-I  Feas.  (\\%) | PPS-I  Cost | PPS-I Fix Time (s) |\n|----------|:---------------:|:----------------:|:---------:|:---------------:|:--------:|:------------------:|:-----------:|:---------------:|\n| Email    |        30       |       90.0       |    3284   |       94.0      |   2911   |        100.0       |     3005    |       20.2      |\n|          |        10       |       94.0       |    3185   |       96.0      |   2759   |        100.0       |     2802    |       15.7      |\n|          |        5        |       96.0       |    3157   |       98.0      |   2640   |        100.0       |     2712    |       6.1       |\n|          |        0        |       100.0      |    3091   |      100.0      |   2691   |        100.0       |     2691    |       0.0       |\n| Gnutella |        30       |       86.0       |    4392   |       92.0      |   3775   |        100.0       |     3909    |       40.6      |\n|          |        10       |       92.0       |    4318   |       96.0      |   3694   |        100.0       |     3741    |       21.3      |\n|          |        5        |       96.0       |    4221   |       98.0      |   3550   |        100.0       |     3568    |       14.9      |\n|          |        0        |       100.0      |    4118   |      100.0      |   3419   |        100.0       |     3499    |       0.0       |\n| RoadCA   |        30       |       78.0       |   13730   |       86.0      |   10985  |        100.0       |    11061    |      214.8      |\n|          |        10       |       88.0       |   12556   |       92.0      |   10148  |        100.0       |    10795    |      137.2      |\n|          |        5        |       92.0       |   12123   |       94.0      |   9892   |        100.0       |     9907    |       48.6      |\n|          |        0        |       100.0      |   11283   |      100.0      |   9184   |        100.0       |     9277    |       0.0       |\n\nFrom the table above, we observe the following:\n\n- PPS performance degrades as SPAGAN’s prediction noise increases, leading to reduced feasibility and inflated cost due to budget being allocated to non-critical edges.\n\n- RL refinement helps recover both feasibility and cost, but does not fully guarantee constraint satisfaction.\n\n- PPS-I consistently restores 100% feasibility, correcting violations through exact computation regardless of prior noise levels.\n\n- Even in the worst-case scenario (RoadCA with 30% noise), PPS-I incurs only a modest cost increase of approximately 19% compared to the ideal, noise-free case (11,061 vs. 9,277), while still maintaining full feasibility.\n\nThese findings highlight the robustness of our three-phase pipeline: even when the learned SPAGAN model fails to generalize, PPS-I ensures feasibility recovery, while RL contributes to cost efficiency along the way. We will include these findings and discussion in the final version of the paper.\n\n **Q2. Has the RL refinement phase been compared with alternative latent optimization strategies like Bayesian Optimization or ES?**\n\nBased on the reviewer’s suggestion, we conducted a comprehensive comparison between our RL-based refinement phase and alternative latent space optimization strategies, including Bayesian Optimization (BO) and Evolutionary Strategies (ES). As summarized in Table 4 below, we evaluate each method on the Gnutella dataset under varying latent dimensionalities, reporting the final cost (lower is better) and feasibility rate. We note that BO does not scale well to high-dimensional latent spaces (e.g., $d>30$) due to its sample inefficiency and surrogate modeling limitations. Therefore, we restrict BO to low-dimensional latent settings ($d=16$ and $d=28$), while allowing higher dimensions for RL and ES. Furthermore, all evaluations are conducted under clean SPAGAN predictions (i.e., without additional noise), to ensure consistent comparison of refinement strategies.\n\n| Method             | Latent $d$ | Final Cost $\\downarrow$ | Feas. Rate $\\uparrow$ |\n|--------------------|------------|:--------------------------------:|:------------------------------:|\n| PPS      | -          |               4118               |              100\\%             |\n| RL (Ours)          | 16         |               3435               |              100\\%             |\n|                    | 64         |               3419               |              100\\%             |\n| Bayesian Opt. (BO) | 16         |               3590               |              98\\%              |\n|                    | 28         |               4055               |              52\\%              |\n| Evo. Strat. (ES)   | 16         |               3612               |              94\\%              |\n|                    | 64         |               3598               |              98\\%              |\n\nFrom these results, we can see that our RL-based refinement consistently achieves the best final cost and full constraint satisfaction (100% feasibility) across both latent dimensions. We will also incorporate this discussion in the final version. \n\n**Q3 and W2. How is the number of CVAE experts in Morph determined? Is there a risk of redundancy or overfitting?**\n\nThank you for raising this important question. The number of CVAE experts is dynamically determined during training based on a density discrepancy criterion, which quantifies how well the current set of experts captures the latent distribution (we let max expert = 9 in our paper). Specifically, we compute a score $\\chi(\\mathbf{x}) = \\log q(\\mathbf{x}) - \\log \\Omega(\\mathbf{x})$ that identifies regions where the mixture model fails to match the energy-guided latent distribution. New experts are only added when this discrepancy exceeds a threshold, ensuring that expansion is data-driven and targeted toward unexplained modes.\n\nRegarding the potential risks of redundancy or overfitting, we would like to highlight several theoretical justifications and empirical safeguards that guide our expert expansion strategy as demonstrated in prior works, including:\n\n[1] Towards Understanding Mixture of Experts in Deep Learning, NeurIPS 2020\n\n[2] A Statistical Perspective of Sparse Top-k Softmax Gating in MoE, ICLR 2023\n\n[3] SwiftHydra: Self-Reinforcing Generative Framework for Anomaly Detection with Multiple Mamba Models, ICLR 2025\n\nthere are two key theoretical insights:\n\n(i) MoE models are more expressive than single-expert models [1,3], especially in modeling multi-modal or structured solution spaces like those in the QoSD setting. While increased model capacity could raise overfitting concerns, in practice, top-$k$ sparse gating acts as an implicit regularizer, activating only the most relevant subset of experts per input. This input-dependent sparsity limits the effective model capacity seen by any given sample, thereby reducing the chance of overfitting despite the large total number of experts [2].\n\n(ii) Even when the number of experts $N \\to \\infty$ (overspecified setting), our use of top-$k$ sparse softmax gating ensures that: Only $k \\ll N$ experts are active per input, keeping inference cost bounded and efficient; The convergence rates of parameter and density estimation remain unchanged compared to dense gating, as proven in [2,3]. This decouples model capacity from inference cost and training stability, eliminating the typical trade-off between expressiveness and generalization. Thus, adding more experts improves coverage of target distribution without harming generalization or causing significant computational overhead.\n\n**W4. The paper does not compare with recent powerful generative optimization methods (e.g., diffusion-based solvers or large-scale neural MIP solvers)**\n\nWe would like to clarify that our baseline set already includes two recent and powerful optimization methods with different scale (1) DiffiLO (ICLR 2025 Spotlight), a differentiable ILP solver that performs well on small to medium-sized graphs and (2) Light-MILPopt (ICLR 2024), a neural MILP solver designed for large-scale graphs.\n\nWe believe this combination already represents state-of-the-art in combinatorial optimization across graph sizes, and our method consistently outperforms both on multiple datasets, especially in handling nonlinear cost structures and enforcing feasibility via latent-space control"}, {"review_id": "05tppEGgYQ", "reviewer": "Reviewer_4YUB", "summary": "This paper proposes a self-reinforcing generative framework called Hephaestus to address the QoSD problem under both linear and nonlinear edge-weight functions.  Specifically, the proposed method uses graph learning to produce feasible solutions with a performance guarantee, then trains a Mixture of Conditional VAEs guided by an energy-based model to capture solution feature distributions, and finally uses a reinforcement learning agent in the latent space to fine-tune the solutions. Experiments show the superior performance of the proposed method, especially in nonlinear settings.", "questions": "I suggest the authors provide a more reasonable explanation of why using the Mixture of Conditional VAEs guided by an energy-based model can alleviate mode collapse.", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The proposed Hephaestus framework is a novel framework to address QoSD, filling the gap that previous methods can't tackle nonlinear edge-weight functions.\n2. Experiments show the superior performance of Hephaestus in nonlinear settings and various datasets.\n3. Each step in this framework has a theoretical guarantee.\n\nWeaknesses:\nIt seems that using a Mixture of Conditional VAEs guided by an energy-based model is not reasonable. For VAEs, it minimizes KL(p|q) for q distribution, which is known as mode coverage, and is always applied to alleviate mode collapse[1]. Conversely, for energy-based models, the minimax training will cause the VAEs to optimize KL(q|p) w.r.t. q, which can lead to mode collapse[2]. Therefore, the motivation for designing a Mixture of Conditional VAEs guided by an energy-based model is not reasonable. At least, it seems this design can't alleviate mode collapse with the paper's explanation.\n\n[1] Divergence Triangle for Joint Training of Generator Model, Energy-based Model, and Inferential Model. CVPR 2019\n\n[2] Exploring bidirectional bounds for minimax training of Energy-based models. IJCV 2025", "was_revised": true, "final_justification": "I maintain my positive score.", "rebuttal": "We thank the reviewer for pointing out potential tension between VAEs and EBMs in generative modeling. First, we clarify that our approach does **not** train VAEs adversarially via a minimax objective. Instead, the **minimax formulation is used solely to derive a principled training objective for the EBM**, allowing us to train it independently **without requiring explicit sampling from the model distribution or estimating the partition function $Z_\\theta$**, which is typically expensive (e.g., via MCMC or Langevin dynamics). Specifically, as shown in **Equation (4)**, our approach starts from the following minimax objective:\n$$\n\\min _{q \\in \\mathcal{Q}} \\max _{\\Omega \\in \\mathfrak{E}}\\{\\mathrm{KL}(p \\| q)-\\mathrm{KL}(\\Omega \\| q)\\}\n$$\nThis formulation seeks a latent density \\$q\\$ that is simultaneously close to the true data distribution \\$p\\$ and exposes gaps in the current generator \\$\\Omega\\$. From this equation we can derive the objective function for EBM (shown in Appendix 2.3: Proof of Theorem 3) that the inner maximization over \\$\\Omega\\$ yields a variational bound which leads to the following energy‐based training objective for the EBM (we also defined in main paper):\n$$\n\\min _\\theta \\mathbb{E} _{p(\\mathbf{x})}\\left[E _\\theta(\\mathbf{x})\\right]-\\mathbb{E} _{\\Omega(\\mathbf{x})}\\left[E _\\theta(\\mathbf{x})\\right]\n$$\nThis objective encourages the EBM to assign low energy to real (feasible) samples (from $p(\\mathbf{x})$) and higher energy to generated samples (from $\\Omega(\\mathbf{x})$), effectively learning a density discrepancy signal. On the other hand, each VAE expert \\$\\Omega \\_i\\$ is then trained independently using an energy‐guided ELBO (we also defined in main paper):\n$$\n\\mathcal{L} _{\\Omega _i}^{\\text {guide }}=\\mathcal{L} _{\\Omega _i}^{\\mathrm{ELBO}}+\\lambda \\cdot \\mathbb{E} _{\\tilde{p} _\\phi(\\mathbf{z} \\mid c)}\\left[E _\\theta\\left(\\tilde{p} _\\phi(\\mathbf{x} \\mid \\mathbf{z}, c)\\right)\\right]\n$$\nIn the above, samples generated by the VAE that are assigned **high energy** by the EBM are penalized. This encourages each expert to specialize in generating samples within **low-energy regions**, i.e., those aligned with the real distribution. Whenever an expert can no longer effectively minimize its energy penalty (i.e., it fails to cover a high-$\\chi(x)$ region where $\\chi(\\mathbf{x}) = \\log q(\\mathbf{x}) - \\log \\Omega(\\mathbf{x}) > \\delta$), a **new VAE expert is added** to capture that region. This process is repeated until the overall mixture model covers the high-quality regions of the data distribution, driving the **total EBM energy loss toward zero**. As a consequence, **adding more experts in the Mix-CVAEs progressively reduces density discrepancy**, ensuring better coverage of the data manifold and effectively avoiding **mode collapse**, without requiring the VAE to be inherently mode-covering or mode-seeking.\n\nSecond, although this does not affect how the VAE is trained—nor does it require the VAE to be explicitly mode-covering or mode-seeking—for completeness, we note that the VAE training objective is derived from the reversed KL divergence \\$\\mathrm{KL}\\left(q \\_\\phi(\\mathbf{z} \\mid \\mathbf{x}) | p \\_\\theta(\\mathbf{z} \\mid \\mathbf{x})\\right)\\$, not \\$KL(p|q)\\$.  We recall briefly the derivation from original VAE paper [1] here:\n\n$$\n\\begin{aligned}\nD _{K L}\\left(q _\\phi \\| p _\\theta\\right) & =\\mathbb{E} _{q _\\phi}\\left[\\log \\frac{q _\\phi(\\mathbf{z} \\mid \\mathbf{x})}{p _\\theta(\\mathbf{z} \\mid \\mathbf{x})}\\right] \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]-\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{z} \\mid \\mathbf{x})\\right] \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]-\\mathbb{E} _{q _\\phi}\\left[\\log \\frac{p _\\theta(\\mathbf{z}, \\mathbf{x})}{p _\\theta(\\mathbf{x})}\\right] \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]-\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{z}, \\mathbf{x})\\right]+\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{x})\\right] \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]-\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{z}, \\mathbf{x})\\right]+\\int q _\\phi(\\mathbf{z} \\mid \\mathbf{x}) \\log p _\\theta(\\mathbf{x}) \\,\\mathrm{d}\\mathbf{z} \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]-\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{z}, \\mathbf{x})\\right]+\\log p _\\theta(\\mathbf{x}) \\int q _\\phi(\\mathbf{z} \\mid \\mathbf{x}) \\,\\mathrm{d}\\mathbf{z} \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]-\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{z}, \\mathbf{x})\\right]+\\log p _\\theta(\\mathbf{x}) \\\\\\\\\\\\\n& =\\mathbb{E} _{q _\\phi}\\left[\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})-\\log p _\\theta(\\mathbf{z}, \\mathbf{x})\\right]+\\log p _\\theta(\\mathbf{x}) \\\\\\\\\\\\\n\\Rightarrow \\log p _\\theta(\\mathbf{x}) & =\\mathbb{E} _{q _\\phi}\\left[\\log p _\\theta(\\mathbf{z}, \\mathbf{x})-\\log q _\\phi(\\mathbf{z} \\mid \\mathbf{x})\\right]+\\mathrm{KL}\\left(q _\\phi \\| p _\\theta\\right)\n\\end{aligned}\n$$\nAs \\$\\log p \\_\\theta(\\mathbf{x})\\$ is constant, maximizing \\$\\mathrm{ELBO}=\\mathbb{E} \\_{q \\_\\phi(\\mathbf{z} \\mid \\mathbf{x})}\\left\\[\\log p \\_\\theta(\\mathbf{x} \\mid \\mathbf{z})\\right]-\\mathrm{KL}\\left(q \\_\\phi(\\mathbf{z} \\mid \\mathbf{x}) | p \\_\\theta(\\mathbf{z})\\right)\\$ indirectly minimizes the reverse KL(q|p). Recent work [2] instead studies the “forward” KL divergence for Variational inference by leveraging MCMC.\n\n[1] Original VAE paper: Auto-Encoding Variational Bayes. Conference: ICLR 2014\n\n[2] Transport Score Climbing: Variational Inference Using Forward KL and Adaptive Neural Transport. Journal: Transactions on Machine Learning Research 2023"}]

Author rebuttal:

Meta-review: This paper investigates the Quality-of-Service Degradation (QoSD) problem, where an adversary perturbs edge weights in a network to degrade end-to-end performance while adhering to budget constraints. It introduces Hephaestus, a novel three-phase generative framework for solving the QoSD problem. The reviewers highlighted the strong technical depth, solid theoretical rigor, and comprehensive and strong empirical results. Nonetheless, the reviewers also pointed out the high complexity, implementation overhead & feasibility to be deployed in practice, the primary focus on static scenario, the sensitivity relying on SPAGAN for the overall performance, the lack of empirical discussion on convergence behavior and sample efficiency, and potential issues using a mixture of Conditional VAEs guided by an energy-based model.
Decision: Accept (poster)