acceptodds
Under review as a conference paper at ICLR 2027

Stability-Based Adversarial Generalization Bounds for Hypergraph Convolutional Networks

Abstract

Hypergraph convolutional networks (HGCNs) propagate information through hyperedges whose learnable weights also determine degree normalization. Analyzing adversarial generalization therefore requires tracking both perturbations of the propagation operator and the coupled updates of layer matrices and hyperedge weights. Under the stated boundedness, Lipschitz activation, and uniform joint-gradient smoothness assumptions, we derive stability-based adversarial generalization bounds for HGCNs trained by two-stream stochastic gradient descent (SGD). We first derive an operator perturbation bound accounting for incidence and weight changes and their effects on normalization. On the explicit family of one large hyperedge and hub-sharing pair edges, over a common weight domain, the ratio between the optimal global hyperedge-weight Lipschitz constants of native propagation and loopless clique expansion grows as the square root of the maximum hyperedge cardinality. Propagating operator sensitivity through the coupled SGD dynamics yields structural and feature adversarial generalization bounds that expose the effects of degree imbalance, network depth, and accumulated optimization expansion. For SGD updates and training examples, the resulting bounds scale as for a fixed architecture when the stated regularity and step-size conditions hold and the loss, gradient, and accumulated-expansion terms are bounded independently of and . A separate one-layer construction under zero attacks, zero regularization, and a restricted training horizon gives a uniform-stability lower bound of order , where measures degree imbalance and is the common step size. Sample-size experiments show both lower gaps at larger training sizes and feature-attack reversals on Cora and PubMed. Controlled forward passes attain the predicted geometric depth dependence.

Primary area:
learning theory
Keywords:
Hypergraph convolutional networks, two-stream stochastic gradient descent, hyperedge-weight Lipschitz constant

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_VMRSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies adversarial generalization of hypergraph convolutional networks trained jointly over layer parameters and hyperedge weights. It combines propagation-operator perturbation bounds with a two-stream SGD stability analysis. It also establishes a sensitivity separation between native propagation and loopless clique expansion, plus a local instability lower bound.

Critical strengths

The operator sensitivity analysis is the main novel contribution. The matching upper and lower bounds on a constructed hypergraph family quantify how native propagation and loopless clique expansion respond differently to hyperedge-weight perturbations.

Critical weaknesses
  1. Strong assumptions, while their applicability to practical adversarial training is unclear. A4 directly assumes joint gradient smoothness of the maximized adversarial objective, though maximizer switching can destroy smoothness. The O(T/n) rate also needs uniformly bounded accumulated expansion, which is not established for the experimental training settings. These conditions may limit the novelty or contributions over existing analyses.

  2. The necessity and interpretation of the degree dependence remain unclear. For fixed incidence and weights bounded below by w_\min , the weight-perturbation coefficient can be bounded by 2/w_\min, without the explicit degree ratios in the paper’s C2. Meanwhile, the lower-bound construction varies weight scales and regularity constants, making a topological effect hard to isolate. The results therefore give limited evidence that the proposed degree dependence captures an unavoidable mechanism or offers actionable training guidance.

Questions for authors
  1. Under what concrete conditions does A4 hold for the ReLU networks and finite-step PGD updates used in the experiments? How are changes in the selected attack controlled?

  2. Do the experimental learning-rate schedules satisfy the bounded-accumulation condition needed for the O(T/n) interpretation? If not, what does the unsimplified bound predict for those settings?

  3. Can the fixed-incidence weight-sensitivity coefficient C2 be replaced by 2/w_\min? If so, which degree dependencies in the main generalization bounds remain necessary?

  4. What does the lower-bound construction establish beyond sensitivity to small absolute weight scales? Does it show unavoidable topology dependence when weight scales and regularity constants are controlled?

Reviewer_bE5WOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper analyzes adversarial generalization of hypergraph convolutional networks in which both layer matrices and hyperedge weights are learned. Because hyperedge weights enter the propagation operator and its degree normalization, the two parameter blocks interact during training. The contributions are: an operator-perturbation bound; an explicit hypergraph family exhibiting a square-root separation between native and loopless-clique weight sensitivity; stability bounds for two-block SGD under structural and feature attacks; and a local uniform-stability lower bound involving a degree-related quantity. The experiments examine directional sensitivity, sample-size dependence, degree imbalance, and controlled forward-depth effects.

Critical strengths
  1. Changes to hyperedge weights affect both the incidence product and normalization, so treating the propagation matrix as fixed would miss an important source of parameter coupling. Separating the two update streams and accounting for both parameter blocks is well motivated.
Critical weaknesses
  1. The empirical measurements do not directly validate the generalization theorems
Questions for authors
  1. How are positive weights, bounded degrees, and layer norms maintained by the stated SGD updates? Under what conditions does A4 hold for the actual activation and attack procedure, and how is finite-step PGD error handled?
  2. Can Eq. (17) be replaced by the normalization-aware bound 2/wmin⁡2/w_{\min}2/wmin​? After this substitution, which dependence on degree imbalance remains in the final guarantees, beyond absolute weight scale and the assumed smoothness constants?
Reviewer_hkFgOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper derives stability-based adversarial generalization bounds for hypergraph convolutional networks (HGCNs) trained with “two-stream” SGD, where layer weights and hyperedge weights are learned together. It gives an operator perturbation bound, an operator separation result showing native hypergraph propagation is about √m more sensitive to hyperedge weights than clique expansion on a constructed family, structural and feature adversarial generalization bounds of order O(T/n). Experiments on Cora, PubMed, CiteSeer, and synthetic hypergraphs examine sample-size, degree, and depth trends.

Critical strengths
  1. Learning hyperedge weights jointly with layer weights, where the weights also enter degree normalization, is a relevant and non-trivial setting.
  2. The paper is careful about stating assumptions and the scope of each result.
Critical weaknesses
  1. The framework closely follows Hardt et al. and Cao et al. (2025) for adversarial GCN training. The main change is replacing the adjacency operator with the hypergraph operator and adding a hyperedge-weight update stream.
  2. Theorem 1 is disconnected from the rest of the paper. It uses a contrived family, its relevance to real hypergraphs is unclear, and it does not feed into the generalization bounds.
  3. The theory and experiments use different threat models. The theory uses ℓ∞/ℓ1 incidence budgets and single-row feature attacks; the experiments use Frobenius budgets and all-row PGD.
  4. The paper is hard to follow. It introduces many constants with little intuition, the proofs are all in the appendix, and the main text reads as a sequence of statements rather than an explanation.
Questions for authors

See Weaknesses

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.