Drift-Guided Adversarial Training for Hypergraph Neural Networks

Hypergraph neural networks are graph networks whose "edges" can join any number of nodes at once, such as all co-authors of one paper or all items in one shopping basket. Like ordinary graph networks, they can be broken by small, deliberate changes. An attacker can add or remove a node from a group, or nudge node features, and accuracy collapses. The only established defense is adversarial training: during training the model is repeatedly shown worst-case perturbed inputs. For hypergraphs, finding those worst cases means many rounds of gradient computation through the hypergraph's propagation operator on every training step, and the cost is high enough that the paper introducing this defense names it as its main limitation.

This proposal makes the worst-case search cheap by using where hypergraph attacks actually do damage. Adversarial Attacks and Robust Training for Hypergraph Neural Networks found empirically that attacks hurt most when they touch low-degree nodes and small hyperedges, because those membership changes distort the network's propagation operator the most. We turn that observation into a closed-form score that can be computed from node and hyperedge degrees alone. The score ranks every candidate membership flip by how much it would distort the operator. Each training step then spends one gradient evaluation on only the top-ranked candidates. The claim we will test is that this recovers most of the robustness of full multi-step adversarial training at roughly twice the cost of ordinary training.

Core Claim

A hypergraph network built on the convolution of Hypergraph Convolution and Hypergraph Attention propagates features through a normalized operator $\Theta = D_v^{-1/2} H W B^{-1} H^\top D_v^{-1/2}$. Here $H$ is the 0/1 matrix recording which node belongs to which hyperedge, $W$ holds hyperedge weights $w_e$, $B$ holds hyperedge sizes $b_e$, and $D_v$ holds node degrees $d_v$. Its entries are

$$\Theta_{uv} = \frac{1}{\sqrt{d_u d_v}} \sum_{e \ni u,v} \frac{w_e}{b_e}.$$

Because $D_v$ and $B$ are diagonal, flipping a single membership $(v,e)$ affects only a few things: row and column $v$, and the entries for pairs inside $e$. The size of the change is controlled by $1/b_e$, $w_e/d_v$, and the degrees of the other members of $e$. This means the operator change ("drift") caused by every existing membership, and by every plausible new one, can be computed exactly in time linear in the number of nonzeros of $H$, with no backpropagation. The formula reproduces the small-hyperedge and low-degree weakness that MeLA observed. It also gives us a ranking with which to restrict the expensive part of the inner maximization.

The proposed defense, which we call Drift-Guided Adversarial Training, combines four steps. First, a degree-only drift score selects a candidate set of $k$ membership flips. Second, a single gradient of the training loss is taken with respect to those $k$ incidence entries and the node features. Third, structural changes are flipped greedily within budget, as the greedy topology attack (GTA) of Towards an Efficient and General Framework of Robust Training for Graph Neural Networks does for pairwise edges, and the features take a single randomly initialized gradient-sign step. Fourth, the perturbation is kept and refined across epochs instead of being regenerated from scratch. The new elements are the closed-form candidate restriction over the hypergraph incidence space and the persistence across epochs. GTA works on a pairwise adjacency matrix and perturbs topology only. MeLA-D searches the joint structure-and-feature space with full multi-step projected gradient descent (PGD).

Research Program

The first piece is analytical. We will derive the exact single-flip drift of $\Theta$ for both additions and removals, and bound the first-order change in the loss by drift times the gradient norm with respect to $\Theta$. Under that bound, candidates outside the top-$k$ by drift can only matter if their loss gradient is unusually large. We will check empirically how often this happens. Additions are the hard case, because there are $|V|\,|E|$ possible new memberships. We will restrict additions to node–hyperedge pairs within two propagation hops and score only those. Whether this misses strong attacks is a question for the experiments, not something we assume.

The second piece is the training loop described above. It will be implemented for three backbones. The first is the hypergraph convolution of Hypergraph Convolution and Hypergraph Attention. The second is HNHN from HNHN: Hypergraph Networks with Hyperedge Neurons, which gives hyperedges their own hidden states. Its drift score has to be derived through the $\alpha,\beta$ degree normalization instead of $\Theta$. The third is AllSetTransformer, the nonlinear backbone MeLA used to test transfer. For attention-based backbones the closed form becomes a heuristic and not an exact quantity. We will report how much worse the ranking gets there.

The third piece is the threat that matters most: an adaptive adversary. A defense that only protects the region it samples might simply push attackers elsewhere. We will therefore attack every trained model with full MeLA-PGD and with a modified MeLA-PGD that is forbidden from touching the defender's top-$k$ candidates, forcing it into high-degree regions and large hyperedges. We will also run the MeLA attack against our models trained with a nonlinear target, to check that robustness is not an artifact of gradient masking.

Baselines

The naive reference is the same backbone trained by ordinary empirical risk minimization with no defense. Under MeLA-PGD, MeLA reports accuracy drops of up to 60% under poisoning and up to 76% under evasion on its citation and co-authorship benchmarks, so this sets the floor.

The strongest existing method is MeLA-D from Adversarial Attacks and Robust Training for Hypergraph Neural Networks. It is full min-max adversarial training with a multi-step PGD inner loop over both incidence and features, and a mini-batch variant for large graphs. It is the only hypergraph-specific adversarial training method in the literature and defines the robustness target. The paper reports robustness gains of 22% to 42% over undefended models, reaching 56% in specific scenarios. The file gives these only as ranges, and no per-dataset absolute robust-accuracy numbers were found on Lacuna for MeLA-D, so we will rerun it with the authors' settings. We will use the same perturbation budgets $\epsilon_x, \epsilon_h$, the same epochs, the same hyperparameter search budget, and the same GPU, and log wall-clock time and peak memory. Beating it means one of two things: robust accuracy within 2 points of MeLA-D at no more than one quarter of its training time, or higher robust accuracy at matched time. Matching it at equal cost would be a negative result.

The single-step reference is adversarial training with MeLA-FGSM perturbations, at the same per-step cost as our method but without candidate restriction or persistence. Two ablations isolate the key ingredient. The first keeps everything but replaces drift-ranked candidates with $k$ uniformly random candidates. The second keeps drift ranking but regenerates perturbations from scratch each epoch. If random candidates do as well, the drift score contributes nothing and the claim fails.

The pairwise route projects each hypergraph to a clique expansion, then trains a GCN with GTA from Towards an Efficient and General Framework of Robust Training for Graph Neural Networks, and with GAME from Chasing All-Round Graph Representation Robustness: Model, Training, and Optimization where memory allows. Both are evaluated against MeLA attacks applied to the original hypergraph.

The training-free route has three variants. The first is Jaccard-style pruning of memberships between dissimilar nodes. The second is KCES from KCES: Training-Free Defense for Robust Graph Neural Networks via Kernel Complexity applied to the clique expansion. The third is a degree-only structural fix with no adversarial training: tuning HNHN's $\alpha,\beta$ normalization to down-weight small hyperedges and low-degree nodes.

Why not just…?

Why not just do single-step adversarial training with MeLA-FGSM? This is the most serious competitor, because it has the same per-step cost. MeLA shows that its multi-step attack is far stronger than its single-step attack. Single-step training is known in the broader literature to defend against one-step attacks while staying vulnerable to iterative ones, a point the file links to the graph robustness work of Towards an Efficient and General Framework of Robust Training for Graph Neural Networks and Chasing All-Round Graph Representation Robustness. Our method differs in two ways: it concentrates the single gradient on the flips with the most leverage, and it accumulates perturbations across epochs, which approximates a multi-step search spread over training. The MeLA-FGSM training baseline, evaluated under MeLA-PGD, settles this directly. If it matches us, our contribution reduces to an analysis result.

Why not just clique-expand and reuse fast pairwise defenses like GTA or GAME? HNHN shows that distinct hypergraphs can collapse to the same clique expansion, and that the expansion blows up the edge count: on DBLP, HyperGCN took over 560 seconds and reached 71.3% accuracy, against 44 seconds and 85.1% for HNHN. MeLA notes that pairwise perturbations do not map back to unique hyperedge-membership changes, so a pairwise-trained defense never sees the attack it will face. We still run this baseline against MeLA attacks on the original hypergraph, because a strong result would be informative.

Why not just fix the normalization so small hyperedges and low-degree nodes matter less, with no adversarial training? This is a real threat. Our own drift analysis says vulnerability is concentrated in those regions, so a reweighting might remove most of it for free. The tuned-$\alpha,\beta$ baseline tests this. We expect it to cost clean accuracy, since small hyperedges often carry real signal, and to fail against joint feature-and-structure attacks. MeLA found such joint attacks super-additive, and a fixed reweighting does not respond to features at all. If the reweighting matches us on robust accuracy at equal clean accuracy, we will report that cheaper finding instead.

Why not just prune suspicious memberships before training, using Jaccard filtering or KCES? On pairwise Cora under Metattack, KCES reaches 82.99% against 75.28% for GNN-Jaccard, which shows that training-free sanitization can be strong. KCES, however, relies on pairwise kernels that inherit clique-expansion blindness. Jaccard filtering compares raw features, which a joint attack also perturbs. Both are included as baselines under the same MeLA attacks.

Why not just use MeLA-D's mini-batch variant, which already scales to OGBN-MAG and Yelp? Mini-batching reduces memory but leaves the number of inner gradient steps per update unchanged. The per-epoch wall-clock comparison against mini-batch MeLA-D on Yelp and OGBN-MAG measures exactly this gap.

Proposed Experiments

Accuracy experiments use Cora, Citeseer, and Cora-CA, the settings MeLA reports. Scaling experiments use Walmart, Trivago, Yelp (4.5M hyperedges), and OGBN-MAG (736k nodes), in both poisoning and evasion and across the three backbones. Metrics are clean accuracy; robust accuracy under MeLA-PGD, MeLA-FGSM, and the restricted adaptive MeLA-PGD; per-epoch wall-clock time; total training time; and peak GPU memory. All are reported as mean and spread over five seeds.

Three checks are decisive. First, drift ranking must beat random candidates at equal $k$ by a clear margin in robust accuracy. Without this the mechanism is unsupported. Second, under the restricted adaptive attack that avoids the defender's candidate region, robust accuracy must stay within a few points of the unrestricted case. A large drop would show the defense only covers the region it samples. Third, on Yelp and OGBN-MAG, training time must be well below that of mini-batch MeLA-D at comparable robust accuracy.

We will also trace robust accuracy against $k$, which tells practitioners how much of the incidence space actually needs searching. Finally, we will measure how often MeLA-PGD's chosen flips fall inside the top-$k$ drift set, a direct test of the claim that hypergraph adversarial damage is predictable from degrees.