Skip to content

Transferable Hypergraph Attack via Injecting Nodes into Pivotal Hyperedges

Conference: AAAI 2026
arXiv: 2511.10698
Code: None
Area: AI Security
Keywords: Hypergraph Neural Networks, Adversarial Attack, Node Injection, Hyperedge Pivotality, Transferable Attack

TL;DR

This paper proposes TH-Attack, a transferable node injection attack framework for hypergraph neural networks (HGNNs). By identifying pivotal hyperedges along information aggregation paths and injecting semantic-reversed malicious nodes, TH-Attack achieves effective black-box attacks across various HGNN architectures, reducing classification accuracy from 80%+ to below 30%.

Background & Motivation

Hypergraphs construct complex higher-order relationships among nodes by allowing hyperedges to connect two or more nodes. This capacity offers superior performance in domains such as recommendation systems, biological networks, and 3D computer vision. Hypergraph Neural Networks (HGNNs) capture higher-order features through a two-stage "node \(\to\) hyperedge \(\to\) node" information aggregation mechanism.

As HGNNs are deployed in safety-critical areas like medical diagnosis and financial risk management, checking their adversarial robustness has become urgent. However, existing hypergraph attack methods suffer from significant limitations:

Limitations of Prior Work: - Hypergraph Modification Attacks (e.g., HyperAttack, MGHGA): Rely on gradient information of the target model, operating under white-box/gray-box assumptions. - Hypergraph Injection Attacks (e.g., IE-Attack, H3NI): IE-Attack selects "elite hyperedges" to inject homophilous nodes generated by KDE, while H3NI uses genetic algorithms for hyperedge selection. However, both rely heavily on the message-passing mechanisms of specific HGNNs.

Key Insight: Prior methods overlook a universal vulnerability of HGNNs: hyperedges exhibit significant differences in their "pivotality" along information aggregation paths.

As shown in Figure 1, node \(v_1\) acquires higher-order features solely through hyperedge \(e_1\), whereas node \(v_3\) has two aggregation paths (\(e_2, e_3\)). Attacking \(e_1\) directly disrupts the information propagation of \(v_1\), causing the HGNN to fail in predictions. Conversely, attacking \(e_3\) has a limited impact on \(v_3\), as \(v_3\) still has \(e_2\) as a backup path.

Thus, \(e_1\) possesses higher pivotality than \(e_2\) and \(e_3\). This universal vulnerability exists across all HGNNs based on the "node-hyperedge-node" aggregation mechanism. Attacking pivotal hyperedges can therefore achieve cross-architecture transferability.

Method

Overall Architecture

TH-Attack consists of three core components:

  1. Hyperedge Recognizer: Identifies critical hyperedges through pivotality assessment.
  2. Feature Inverter: Generates semantic-reversed malicious node features based on critical hyperedge features.
  3. Injection Attack: Injects malicious nodes into key hyperedges to destroy information propagation.

Key Designs

1. Hyperedge Pivotality Assessment and Recognizer

Starting from the aggregation process of HGNN:

Node-to-hyperedge aggregation: \(\mathbf{z}_j^{(l)} = \frac{1}{|e_j|} \sum_{v_i \in e_j} \frac{1}{\sqrt{d_{v_i}}} \mathbf{x}_i^{(l)} \Theta^{(l)}\)

Hyperedge-to-node aggregation: \(\mathbf{x}_i^{(l+1)} = \frac{1}{\sqrt{d_{v_i}}} \sum_{e_j \ni v_i} w_{e_j} \mathbf{z}_j^{(l)}\)

For node \(v_i\), its isolation degree is defined as its hyper-degree (the number of hyperedges it belongs to):

\[d_h(v_i) = |\{e_j \in \mathcal{E} \mid v_i \in e_j\}|\]

If \(d_h(v_i) \leq \tau\) (the pivotality level threshold), then the hyperedges containing \(v_i\) are defined as key (pivotal) hyperedges.

Theoretical Support:

Theorem 1 (Perturbation Amplification of High-Pivotality Hyperedges): When a node \(v_i\) aggregates information through a high-pivotality hyperedge, the lower bound of its feature perturbation is:

\[\|\Delta \mathbf{x}_i^{(l+1)}\|_2 \geq \frac{1}{\sqrt{d_{v_i}}} \min_{e_j \ni v_i} w_{e_j} \cdot \|\Delta \mathbf{z}_j^{(l)}\|_2\]

Theorem 2 (Perturbation Attenuation of Low-Pivotality Hyperedges): When a node \(v_k\) aggregates through low-pivotality hyperedges, the perturbation is dispersed over multiple paths:

\[\|\Delta \mathbf{x}_k^{(l+1)}\|_2 \leq \frac{1}{\sqrt{d_{v_k}}} \sum_{e_j \ni v_k} w_{e_j} \|\Delta \mathbf{z}_j^{(l)}\|_2\]

Design Motivation: High-pivotality hyperedges serve as the unique or rare pathways for information propagation. Targeting these hyperedges triggers a perturbation amplification effect. Conversely, low-pivotality hyperedges benefit from redundant paths that disperse perturbation energy. This constitutes a structural vulnerability that is independent of specific HGNN architectures, thereby rendering the attack transferable.

The final set of selected pivotal hyperedges is:

\[\mathcal{E}_{all\_piv} = \{e_j \in \mathcal{E} \mid \exists v_i \in e_j \text{ s.t. } d_h(v_i) \leq \tau\}\]

2. Pivotal Hyperedge-based Feature Inverter

Goal: Generate malicious node features that maximize semantic divergence from the targeted hyperedge's features, effectively injecting "poison" during aggregation.

Initial Confused Feature Generation:

\[\mathbf{x}_{ini}^{(j)} = \mathbf{x}_{pro}^{(j)} \oplus \mathcal{N}(0, \mu^2)\]

Where \(\mathbf{x}_{pro}^{(j)} = \prod_{v_i \in e_j} \mathbf{x}_i\) denotes the element-wise product of node features inside the hyperedge. This preserves statistical correlations while introducing Gaussian noise to enhance diversity.

MLP Enhancement: Utilizes a multi-layer MLP with LeakyReLU to intensify the confusion effect, and ultimately outputs the malicious features via Softmax.

Loss Function — Maximizes semantic divergence while bounding the divergence scale:

\[\mathcal{L}_{cos\_dis} = \cos(\mathbf{x}_{mal}^{(j)}, \mathbf{z}_{e_j}) + \lambda \cdot \mathcal{L}_{reg}\]

Where \(\mathcal{L}_{reg} = \max(\cos(\mathbf{x}_{mal}^{(j)}, \mathbf{z}_{e_j}) - t, 0)\), and \(t\) is the similarity threshold.

Design Motivation: - Minimizing cosine similarity forces the malicious node features to align in the opposite direction of the hyperedge features, inducing maximum disruption during aggregation. - The regularization term prevents excessively large deviations to maintain attack stealthiness. - The hyperedge feature \(\mathbf{z}_{e_j} = H^\top \cdot \mathcal{X}\) depends solely on the hypergraph structure and does not require model parameters, accomplishing a black-box attack.

3. Injection Attack and Cross-Model Transferability

Inject the generated malicious nodes into key hyperedges: \(e_j = \{v_1, v_2\} \to \{v_1, v_2, v_{mal}^{(j)}\}\)

In the updated incidence matrix \(\hat{H}\), the node dimension increases by \(m\) while the hyperedge dimension remains unchanged. The attacked hypergraph \(\hat{\mathcal{G}} = (\hat{\mathcal{V}}, \hat{\mathcal{E}})\) can be directly fed into any HGNN without requiring any knowledge of the target model parameters or architectural details.

Sources of Transferability: - The identification of key hyperedges relies solely on the hypergraph structure, independent of any specific HGNN. - Feature inversion depends only on hyperedge feature aggregation (\(H^\top \mathcal{X}\)), independent of model parameters. - All HGNNs operating on hierarchical "node-hyperedge-node" message passing share this structural vulnerability.

Loss & Training

  • The feature inverter is optimized via backpropagation on \(\mathcal{L}_{cos\_dis}\).
  • The attack budget \(\Phi\) is determined by the perturbation rate \(\eta\) and node count \(N\), typically restricted to under 5% of the total node size.
  • Optimal hyperparameter configuration: \(\lambda=0.1, t=0.9\) (low regularization + high similarity threshold = maximum attack strength).

Key Experimental Results

Main Results

Accuracy Comparison across 6 Datasets \(\times\) 5 HGNNs \(\times\) 6 Attack Methods (%)

Dataset/Model Clean Random DICE FGA IGA IE-Attack TH-Attack
Cora/HGNN 76.41 74.71 74.45 74.41 73.84 73.20 36.08
Cora/HyperGCN 75.95 73.14 73.93 72.62 71.09 68.37 31.55
Cora/UniGCNII 80.08 75.82 77.23 76.65 76.01 76.57 39.42
Cora-CA/UniGCNII 84.68 79.53 80.15 80.57 79.07 83.95 32.72
Pubmed/HGNN 84.28 80.99 81.29 81.99 81.60 84.53 40.96
DBLP/HyperGCN 89.54 83.84 81.72 85.85 81.83 82.64 46.23
ModelNet40/UniGCNII 97.86 93.45 93.51 93.36 93.48 96.65 53.50

TH-Attack significantly outperforms all baselines, decreasing accuracy by 30-50 percentage points in most settings, compared to the 2-10 percentage points drop of baseline methods.

Ablation Study

Variant Cora Cora-CA Citeseer Pubmed
w/o Hyperedge Recognizer (HR) 41.19 / 34.87 / 43.48 38.30 / 24.51 / 40.00 28.69 / 21.43 / 34.05 45.16 / 36.47 / 47.14
w/o Feature Inverter (FI) 61.80 / 38.65 / 73.85 58.40 / 26.57 / 77.72 54.26 / 43.93 / 66.94 44.25 / 38.97 / 47.95
w/o Cosine Distance Loss (CDL) 61.05 / 59.42 / 59.80 59.31 / 54.66 / 60.34 54.45 / 52.64 / 66.06 55.85 / 52.76 / 46.40
Full TH-Attack 36.08 / 31.55 / 39.42 32.03 / 17.02 / 32.72 24.17 / 20.59 / 27.00 40.96 / 35.14 / 44.13

(The three values in each cell correspond to HGNN / HyperGCN / UniGCNII, respectively)

  • Lack of CDL has the most significant impact: Removing the Cosine Distance Loss causes a severe decline in performance, indicating that maximizing semantic divergence is the primary driver of the attack.
  • Significant individual contributions from HR and FI: Validates the complementary roles of key hyperedge selection and malicious feature generation.

Key Findings

  1. Extreme Attack Impact: On Cora, the accuracy of HGNN drops from 76.41% to 36.08% (a drop of 40+ percentage points); on Cora-CA, HyperGCN drops from 76.32% to 17.72%.
  2. High Efficiency under Low Budgets: With a perturbation rate of \(\eta=1\%\), injecting only 23 nodes on Cora drops the HGNN accuracy by 17.17%, while baselines drop by at most 5%.
  3. Robust Cross-Architecture Transferability: The same attack data is effective against 5 different HGNN architectures, whereas baselines (especially IE-Attack) only function on specific models.
  4. Impact of Pivotality Level \(\tau\): The attack severity is strongest when \(\tau=1,2\), and degrades as \(\tau \geq 3\), consolidating the validity of the pivotality hypothesis.
  5. Greater Dominance on Complex Datasets: On complex datasets like ModelNet40, baseline attacks are virtually ineffective (accuracy decreases by only 2-4%), whereas TH-Attack successfully downgrades system performance significantly.

Highlights & Insights

  • Deep insights in problem formulation: Shifts the adversarial focus from "which nodes/edges to attack" to "attacking structural bottlenecks within the information propagation path." This indicates a deep understanding of HGNN architectural vulnerability.
  • Unified theoretical and practical view: Theorems 1 & 2 mathematically formulate the concept of pivotality from the aggregation equation, with experimental setups empirically validating the theoretical predictions.
  • Simplicity and efficiency: No gradient information, surrogate models, or target architecture details are required. It operates as a purely structure-and-feature-based black-box attack on hypergraphs.
  • Astonishing attack performance: Under a mere 5% injection budget, it degrades the accuracy of state-of-the-art HGNNs down to near-random levels.

Limitations & Future Work

  1. Limited to node classification: The performance is not evaluated on other hypergraph tasks like link prediction or community detection.
  2. Absence of defensive analysis: Potential defense strategies are not discussed, such as anomalous injected node detection or suppressing the weight of pivotal hyperedges during aggregation.
  3. Stealthiness of the Feature Inverter: Despite regularization constraints, the paper lacks a quantitative assessment of the anomaly degree of injected nodes in the feature space, leaving open the question of whether they are easily flagged by anomaly detectors.
  4. Dynamic hypergraphs are not considered: The authors highlight attacks on dynamic HGNNs as future directions.
  5. Poisoning configuration in experiments: Since IE-Attack was originally designed as an evasion attack, converting it to a poisoning setup might skew the comparison fairness.
  • The concept of pivotality can be generalized to "bridge edges" or "articulation points" in standard graph neural networks (GNNs).
  • The core concept behind the Feature Inverter can be applied to generate high-quality adversarial examples.
  • This work exposes the common vulnerabilities in the structural bottlenecks of message-passing systems, offering critical insights to the study of HGNN robustness.
  • Inspires potential defenses: designing redundant aggregation paths, and adaptive preservation of pivotal hyperedges.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ — The concept of pivotality is novel with solid theoretical backup; the formulation of attacking structural bottlenecks offers a highly original perspective.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ — Exhaustive evaluation over 6 datasets, 5 models, and 6 baselines under various perturbation rates, with comprehensive ablation and parameter studies.
  • Writing Quality: ⭐⭐⭐⭐ — Highly structured, with intuitive schematic illustrations for motivation, though some mathematical derivations could have been formulated more compactly.
  • Value: ⭐⭐⭐⭐⭐ — Offers significant contributions to HGNN security research by exposing a universal structural vulnerability.