Stability-Based Adversarial Generalization Bounds for Hypergraph Convolutional Networks

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 $T$ SGD updates and $n$ training examples, the resulting bounds scale as $\mathcal{O}(T/n)$ 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 $n$ and $T$. A separate one-layer construction under zero attacks, zero regularization, and a restricted training horizon gives a uniform-stability lower bound of order $r_{deg}\eta T/n$, where $r_{deg}$ measures degree imbalance and $\eta$ 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.