Source-linked AI summary
Cone Extended Rayleigh Quotients for Directed Graph Learning: Minimax Spectral Certificates, Sensitivity, and Adaptive Control
Yavdat Sh. Il'yasov, Nur F. Valeev
TL;DR
Directed graph learning requires methods that preserve the information in nonsymmetric propagation operators and their distinct right and left modes. The paper develops a two-sided cone framework for certification, differentiable surrogates, sensitivity, and adaptive control, and reports a 21.5% Cora spectral-level reduction under a 0.5% budget with unchanged observed test accuracy. Its scope is limited for strongly nonnormal operators and boundary cone levels that may be non-spectral.
Problem
Directed propagation is generally nonsymmetric, and the quadratic Rayleigh quotient does not retain the operator's distinct right–left structure.
Method
The paper applies a two-sided cone Rayleigh framework to trainable directed operators, combining a posteriori bounds, differentiable soft surrogates, right–left sensitivity, and graph-supported interventions.
Results
21.5% reduction in the distinguished spectral level was achieved on directed Cora under a cumulative edge-weight budget of 0.5%, with unchanged observed test accuracy for the considered trained model and split.
Takeaways & Limitations
The right and left modes jointly certify the directed cone level and provide an adaptive control map for modifying influential graph interactions.
Takeaways & Limitations
For strongly nonnormal operators, controlling λC alone does not control transient amplification, singular values, resolvent growth, or pseudospectral behavior.
Abstract
from arXiv · showhide
Directed graph learning naturally leads to trainable nonsymmetric propagation operators with distinct right and left spectral structures. Building on the two-sided cone Rayleigh framework for generalized pencils \[ B_θ-λG, \] we develop a learning-oriented methodology for spectral certification, sensitivity analysis, and control without requiring symmetry, nonnegativity, or cone preservation. In the positive-orthant setting, computable lower and upper cone bounds provide an a posteriori enclosure of a distinguished cone level, while smooth soft-min/max surrogates preserve rigorous one-sided bounds with explicit approximation errors and remain differentiable with respect to the trainable parameters. For a simple interior level, the right and left modes satisfy \[ Dλ_C(B)[H]=v_C^T H u_C, \] yielding first-order optimal graph-supported interventions under prescribed perturbation budgets and motivating adaptive spectral control. Numerical experiments demonstrate the applicability of the approach beyond cone-preserving operators and in directed learning settings. Signed nonsymmetric perturbations reveal a transition from interior eigenpairs to boundary complementary quasi-pairs, including non-spectral cone levels, while controlled experiments show that symmetrization can remove predictive information carried solely by edge direction. On the directed Cora citation network, adaptive recomputation of the right--left sensitivity reduces the distinguished spectral level by approximately $21.5\%$ under a cumulative edge-weight reduction budget of $0.5\%$, with no observed change in test accuracy for the trained model and data split considered.
1 Introduction and related work
The paper addresses directed graph learning with nonsymmetric operators by retaining distinct right and left modes rather than replacing directionality with symmetric surrogates. It develops cone-based certification, sensitivity, and adaptive control, with experiments spanning boundary behavior and directed classification.
- Directed propagation operators are generally nonsymmetric, so their distinct right and left modes are not captured by the quadratic Rayleigh quotient.
- The two-sided cone Rayleigh framework works directly with the original nonsymmetric operator and accommodates interior eigenpairs and boundary quasi-pairs.
- Computable two-sided bounds and differentiable soft surrogates provide a posteriori certification while remaining compatible with trainable parameters.
- Right–left sensitivity yields graph-supported interventions and adaptive recomputation of edge rankings for spectral control.
- Controlled experiments show that symmetrization may remove predictive information carried specifically by edge orientation.
- On directed Cora, adaptive sensitivity recomputation reduced the distinguished spectral level by approximately 21.5% under a cumulative edge-weight budget of 0.5%, with unchanged observed test accuracy.
2 Directed learning and the spectral control problem
The learning setup uses a trainable directed propagation operator and a generalized matrix pencil, preserving graph directionality while allowing spectral control of a distinguished cone level. The resulting formulation is designed for nonsymmetric operators and remains meaningful for singular reference metrics.
- The graph is weighted and directed, with directionality A ≠ A^T retained throughout.
- Node features are propagated by a trainable operator Bθ whose architecture is secondary to its spectral role.
- The model associates Bθ with a generalized pencil and distinct right and left generalized eigenproblems.
- The formulation avoids explicit inversion of G, remains meaningful when G is singular, and does not require Bθ to be positive, symmetric, or cone preserving.
- The distinguished cone level is a generalized eigenvalue in the interior regime but may be quasi-spectral at the cone boundary.
3 Two-sided cone spectral framework
The cone framework defines two-sided variational levels for generalized nonsymmetric pencils over admissible cones. Its minimax principle provides attained extremizers, while boundary complementarity explains cone levels that need not be ordinary eigenvalues.
- The framework applies to arbitrary real matrices and generalized non-selfadjoint pencils without assuming cone preservation.
- A cone extended Rayleigh quotient is homogeneous in each variable, enabling separate minimax formulations for upper and lower cone levels.
- The cone minimax principle ensures equality of the relevant variational quantities and attainment by right and left quasi-eigenvectors.
- Interior extremizers satisfy the corresponding right–left generalized eigenvalue conditions.
- At the boundary, complementary quasi-pairs can share a cone level that lies outside the generalized spectrum.
- The formulation recovers classical positive theory while also applying to sign-changing and non-cone-preserving operators.
4 Differentiable spectral certification and sensitivity
The paper turns the cone framework into learning-compatible certificates and sensitivity rules. Positive-orthant trial modes give computable enclosures, smooth surrogates retain certification with bounded error, and right–left modes identify perturbations that most influence the cone level.
- Approximate positive right and left modes produce a computable a posteriori enclosure of the distinguished cone level.
- For sparse operators, evaluating the enclosure requires matrix–vector products Bθu and Bθ^T v.
- Soft-min/max smoothing preserves the certified one-sided bounds while adding at most 2ε log N to the exact enclosure.
- The smooth enclosure yields a differentiable sufficient condition for λC(Bθ, G) ≤ Λ.
- For a simple interior generalized eigenvalue, right–left perturbation theory identifies the first-order influence of an arbitrary perturbation H.
- The resulting sensitivity map supports locally optimal graph-supported interventions and adaptive updating after successive modifications.
5 Certified learning and adaptive spectral control
The section integrates cone-level certification with differentiable learning objectives and right–left sensitivity-based graph control. It also clarifies that the certificate targets a distinguished cone-relevant spectral mode rather than all nonnormal dynamics.
- Certified learning: Certified lower and upper bounds provide an a posteriori enclosure of the distinguished cone level during learning.
- Sensitivity and intervention: For a simple interior generalized eigenvalue, the sensitivity map is given by the normalized right–left modes.
- Sensitivity and intervention: Right–left modes determine locally optimal graph-supported directions for decreasing the distinguished level under Frobenius and L1 budgets.
- Adaptive control: Recomputing sensitivities after each modification yields adaptive control that updates the local linearization along the intervention path.
- Scope of the certificate: Controlling λ_C does not generally control transient amplification, pseudospectral growth, operator norms, or prediction robustness for strongly nonnormal operators.
6 Algorithms and computational cost
The algorithms alternate mode and model updates using sparse or structured forward and transpose propagations. Certification uses exact enclosure criteria, while residual norms alone are insufficient for a two-sided guarantee.
- Algorithms: Training alternates between updating auxiliary modes with fixed parameters and updating model parameters with fixed modes.
- Algorithms: Automatic differentiation supplies gradients, and mode variables are warm-started from the preceding outer iteration.
- Adaptive control: Adaptive control restricts interventions to admissible interactions, recomputes modes and certificates, and stops at the certified cap or exhausted cumulative budget.
- Computational cost: For graph-sparse operators, spectral operations use sparse or structured propagations plus O(N) componentwise and soft-min/max work.
- Computational cost: The spectral cost per outer iteration scales as O(m_mode(|E| + N)) apart from model-specific trainable edge-weight evaluation.
- Stopping and certification: Certification uses the exact gap, because residual norms may be monitored for interior eigenpairs but do not alone provide a two-sided enclosure.
7 Numerical experiments
The experiments validate cone certification, sensitivity, and adaptive control across signed nonsymmetric operators, directed learning benchmarks, direction-only comparisons, and the Cora citation network. Results include boundary quasi-pairs, certified spectral caps, preserved accuracy, direction-dependent predictive gains, and substantial adaptive spectral reduction.
- Signed perturbations and boundary quasi-pairs: Signed nonsymmetric perturbations transition from interior eigenpairs to boundary complementary quasi-pairs that can be non-spectral.Across 25 cases, seven have interior right–left pairs, while 18 boundary cases are typically separated from the ordinary spectrum by 10^-3–10^-2.
- Validation of right–left sensitivity: Finite-difference tests and graph-supported perturbations show that the right–left product accurately captures directional sensitivity and influential graph interactions.For B + 0.05H_graph, the observed shift is 0.04697 versus a first-order prediction of 0.04721.
- Certified directed learning: Across 50 directed-SBM realizations, certified learning enforces the spectral cap with only small operator modifications and no systematic accuracy change.No eigensolver is used during training or certification, and post-hoc eigensolvers confirm the certified bound in all 50 runs.
- What is lost by graph symmetrization?: Symmetrization can remove predictive information carried by edge orientation when the expected symmetrized graph has no class-dependent signal.At δ = 0.04, ΔAcc = 0.0940 with 95% CI [0.0662, 0.1218] and p = 1.36 × 10^-8; the mean fitted slope is 2.220.
- Adaptive spectral control on Cora: On Cora, adaptive sensitivity recomputation lowers the distinguished spectral level by approximately 21.5% under a 0.5% cumulative edge-weight budget while preserving observed test accuracy.The reduction is approximately 37% larger than with fixed ranking.
8 Discussion and conclusion
The paper applies a two-sided cone Rayleigh framework directly to trainable nonsymmetric directed operators, combining certification, differentiable bounds, sensitivity analysis, and adaptive control. Experiments cover interior and boundary regimes and show substantial spectral reduction on Cora without observed accuracy change.
- The nonsymmetric pencil is treated directly, preserving distinct right and left modes instead of replacing the operator with a symmetric or Hermitian surrogate.
- Computable lower and upper bounds provide an a posteriori enclosure of the distinguished cone level.
- Smooth soft-min/max surrogates remain differentiable and retain explicit one-sided approximation bounds for gradient-based learning with certification.
- The same right–left modes characterize and certify the cone level, generate a sensitivity map, and support first-order graph interventions under Frobenius and L1 budgets.
- Signed nonsymmetric perturbations transition from interior eigenpairs to boundary complementary quasi-pairs, including common cone levels outside the ordinary spectrum.
- On Cora, adaptive sensitivity recomputation reduces the distinguished spectral level by approximately 21.5% under a cumulative edge-weight budget of 0.5%, with unchanged observed test accuracy for the considered model and split.
- For strongly nonnormal operators, controlling λ_C alone does not control transient amplification, singular values, resolvent growth, or pseudospectral behavior.
Data availability
The paper identifies public data and reproducibility resources for its experiments.
- Cora data are publicly available, while synthetic-data procedures and reproducibility code, scripts, and canonical outputs are described or provided through a Zenodo package.