HyperNear: Unnoticeable Node Injection Attacks on Hypergraph Neural Networks

We sincerely appreciate your detailed review and for recognizing the novelty and contributions of our work, including the introduction of HyperNear, its theoretical grounding, and its strong empirical results. Below, we address your comments point by point.

Weakness1: Figure 4 illustrates the difference in the distribution of homophily ratio before and after the attack. We will refine Figure 4 by enhancing its clarity, improving the legend contrast, and adding explanatory annotations to highlight how classification results support our stealthiness claims. Thank you for your valuable suggestions.

Weakness2: We clarify that Figure 1(a) is designed to illustrate how the impact of injected malicious nodes propagates through the hypergraph topology, rather than demonstrating homophily-guided injection. Meanwhile, we acknowledge that Figure 1(b) could better highlight homophily's role in stealthiness. To improve clarity, we will enhance the figure and captions to better convey these distinctions.

Weakness3: Thank you for the suggestion. The five datasets we use are widely adopted benchmarks in hypergraph learning, making them appropriate for evaluating HyperNear. However, we agree that exploring additional datasets could further reveal the impact of hypergraph structure on attack robustness. We consider this an important direction for future work.

Other 1: We will increase the font size in Table 1 to improve readability.

Question 1: Our paper already provides a theoretical analysis of how hypergraph topology influences homophily and how local perturbations can cascade through the structure. Specifically, Theorem 3.1 formalizes how perturbations affect node relationships, with the first term capturing linear propagation effects, while higher-order terms reflect nonlinear amplification, which can become significant under large perturbations or varying hyperedge weights.

Additionally, Figure 11 illustrates how perturbations propagate in HNNs, visually demonstrating this cascading effect. The primary term dominates for small perturbations, ensuring controlled degradation, while higher-order dependencies introduce more complex, nontrivial effects under larger structural changes.

Question 2: In hypergraphs, homophily quantifies the similarity of connected nodes in feature space, making it a natural and intuitive measure of structural changes. Since hypergraph neural networks heavily rely on homophily for information propagation, perturbing homophily can significantly degrade model performance, which aligns with our attack objectives.

As discussed in our paper, exploring alternative structural change metrics in hypergraphs is an important future research direction. While homophily provides a strong foundation, other potential measures could offer complementary insights into structural vulnerabilities.

Once again, we sincerely appreciate your thoughtful feedback and your recognition of the novelty and significance of this work. Your comments have helped us refine our presentation and identify valuable directions for future research.

We sincerely appreciate your comprehensive and positive evaluation of our work, particularly your recognition of our theoretical contributions, experimental rigor, and positioning within the broader adversarial attack literature on hypergraphs. Your feedback reinforces the significance of our study and motivates future research in this area. Next I address your concerns point by point.

Weakness 1: In our paper, we have already evaluated the homophily shift for the ''Random'' baseline to illustrate stealthiness. Additionally, Figure 8 provides a comprehensive analysis of how other attack methods (NDA, FGA) affect homophily across different datasets (DBLP-CA, Cora, Pubmed, Citeseer). This effectively demonstrates the stealthiness variations among different attack strategies. Your suggestion is valuable, and we will consider adding a table with homophily change metrics for other methods in the revised manuscript.

Weakness 2: To improve the clarity of performance comparisons, we have added a summary row to the table that presents the average performance drop for each attack method relative to the ''Clean'' baseline. This allows for a more intuitive comparison of the overall impact of HyperNear against other methods.

Suggestion 1: Thank you for the suggestion to improve cross-referencing between the main text and the supplementary material. We will scrutinize our manuscript againto ensure that the reader is clearly directed to the relevant supplemental chapters that provide more detail.

Suggestion 2: Yes. We will ensure consistent font styles across all figures for a more polished presentation.

Suggestion 3: We will increase the font size in the experimental figures to improve readability.

Thank you again for recognizing this work and for your constructive comments.

Claims&W2&W3: Thank you for your valuable feedback and for recognizing the effectiveness of our attack methodology.

Our claim of stealthiness is based on the observation that homophily-aware attacks introduce perturbations aligned with existing structural patterns, making them less detectable than naive attacks. While Figure 4 & 5 provide empirical evidence, we acknowledge the need for stronger theoretical justification. Regarding adversarial defenses, existing graph-based methods may not directly apply to hypergraphs due to structural differences. Evaluating robustness against hypergraph-specific defenses is an important direction for future work.

To the best of our knowledge, no prior work has established attack methods for hypergraphs. Our study serves as an exploratory step, proposing the first black-box attack framework for hypergraph neural networks, which is a fundamental prerequisite for systematic defense research. Given the absence of standardized adversarial defenses in hypergraph learning, we deliberately prioritize vulnerability analysis over premature defense development, aligning with security research paradigms in graph learning [4], where attack understanding precedes defense formulation. We believe this work lays a crucial foundation for future robustness studies in hypergraph learning.

Theoretical: Thank you for recognizing our mathematical formulation of the attack optimization process, which balances effectiveness and stealthiness. While we do not provide formal convergence guarantees, this is due to the complexity of hypergraph structures, where high-order dependencies and discrete perturbations make theoretical analysis non-trivial. Nevertheless, our empirical results consistently demonstrate stable and effective attack performance across multiple datasets. Future work could explore theoretical analyses, such as proving convergence under specific constraints or employing continuous relaxations of the attack space.

W1: While we agree that black-box attacks are a key contribution, our work is not merely about transferring existing attacks to a black-box setting. Instead, we position this as an exploratory study into the fundamental vulnerabilities of hypergraph neural networks under adversarial attacks, an area that has received little attention.

Notably, every reviewer recognized our work as a promising and significant direction, highlighting the importance of understanding adversarial threats in hypergraphs. Our study emphasizes the challenges posed by the higher-order dependence of hypergraphs and the need for homophily-aware perturbations. We further elaborate on these challenges in Q1, where we discuss the difficulty of designing attacks that remain stealthy while coordinating complex hypergraph structures.

W2: Thank you for the suggestion. We will enhance Figure 1(b) by improving color contrast, making the distinction between homophilous and heterophilous hyperedges more visually intuitive. For concerns regarding formal proofs, please refer to our response to Claims&W2&W3.

Q1: Compared to black-box attacks on GNNs, perturbations in standard graphs only affect pairwise connections, while in hypergraphs, a single hyperedge impacts multiple nodes. This requires coordinated modifications to remain stealthy, making attack design significantly harder. Compared to white-box attacks on HNNs, our black-box setting lacks access to model parameters or gradients, requiring surrogate models and heuristic strategies.

Moreover, hypergraph attacks require greater stealth, as their intricate interdependencies render naive perturbations more easily detectable. Additionally, while hypergraphs have attracted growing interest for their strong representational capabilities, the study of homophily in hypergraphs has only recently begun to receive attention [5]. The structural complexity of hypergraphs makes the homophily problem particularly challenging and still largely underexplored.

Q2: We follow the strict black-box setting in [6], where attacker can access node features but has no knowledge of model parameters or gradients. Therefore, using original feature for feature generation is consistent with this definition. In addition, the use of raw features belongs to the reasonable a priori knowledge of the attacker (e.g., publicly available user features are observable by the attacker in social networks) and does not conflict with the black-box setting.

Thank you again for recognizing this work and for your constructive comments.

[4] Zügner et al., Adversarial Attacks on Neural Networks for Graph Data. In KDD, 2018.

[5] Li et al., When Hypergraph Meets Heterophily: New Benchmark Datasets and Baseline. In AAAI, 2025.

[6] Xu et al., Blindfolded Attackers Still Threatening: Strict Black-Box Adversarial Attacks on Graphs. In AAAI, 2022.

We sincerely appreciate your detailed feedback and address your concerns below.

Claims1: Our claim of unnoticeability is relative, meaning that our attack is designed to be less detectable compared to naive perturbations. The degree of unnoticeability also varies across datasets due to differences in hypergraph structures [1]. For instance, Cora has a noisier and less structured hypergraph compared to Cora-CA, as their hyperedge constructions differ. Thus it produces less impact in Fig.4(b) (Cora-CA) than in Fig.4(a) (Cora).

Claims2: Yes. Please refer to our response to Reviewer FH69’s Q2.

Claims3: In addition to four surrogate models in transferability (HyperGCN, HGNN, ED-HNN, UniGCNII), Table 2 includes UniSAGE, UniGIN, UniGCN, and UniGAT, covering diverse hypergraph neural networks for comprehensive evaluation.

Methods1&Exp: Our study focuses on homophily because both structural and feature perturbations directly affect it, making it a better indicator of unnoticeability than degree or feature distributions, which are outside our scope. As noted in line 201, we measure homophily FHH, defining the x-axis in Figure 4. Revealing homophily’s sensitivity is a key contribution, as it captures both structural and feature-based perturbation effects.

Methods2: Random: Node features are randomly sampled from a Gaussian distribution fitted to existing node features. NDA: We select nodes with the smallest degrees and perturb their features by adding Gaussian noise proportional to feature variance. Full details are available in our public code.

Theoretical1&Theoretical2: Section 3.1 analyzes hypergraph topology's vulnerability, not its comparison to standard graphs. Hyperedges amplify perturbations differently from graphs, where message passing is pairwise. While both graphs and hypergraphs allow perturbation propagation through the structure, their structural mechanisms differ fundamentally. Corollary 3.2 shows hyperedge weight and feature changes impact all incident nodes simultaneously.

Supplementary: Thank you for noting this issue. The incomplete code was due to an outdated version of the repository used at the time of submission. We have now updated it with the correct, runnable code.

Other: We will redraw Figure 2 to improve clarity, ensuring legends do not obscure numbers.

Q1: The practicality of such attacks lies in the non-i.i.d. nature of hypergraph data, where structural dependencies significantly impact representation learning. Unlike graphs, hypergraphs propagate information across multiple entities, influencing representation learning (e.g., HGNN+ [2]).

Q2: Lines 916-927 (Appendix B) define our adversarial objective. Algorithm 1 (Line 17) terminates when further perturbations no longer improve attack effectiveness or when accuracy drops below a threshold, preventing over-perturbation and also to conserve resources.

Q3: We believe that, in some cases, random injections may unintentionally act as data enhancement, leading to performance improvements rather than degradation. This aligns with findings in contrastive learning for hypergraphs (e.g., HyperGCL [3]), where certain hyperedge augmentation can enhance model generalizability and robustness. This further justifies the need for dedicated adversarial attack studies on hypergraphs.

Q4: Theorem 3.1's perturbation $ΔR_v$​ refers to structural modifications via node injection, altering neighborhood relationships and feature propagation.

Q5: ''t-hop features" are neighborhood features aggregated through t-hop hyperedges. Line 110 defines $f(\cdot)$ as the aggregation function, with $f_t$ representing t-hop features. We will clarify that $n$ is the maximum hop count. As noted in Line 161, both $f(\cdot)$ and $\phi$ are differentiable hypergraph convolution aggregation functions. Theorem 3.1 holds if aggregation follows Eq. (6).

Q6: Line 198 already provides the definition: the average degree of hyperedge $e$ is given by $d_e=\frac{1}{|e|}\sum_{i \in e}d_i$, ensuring balanced normalization in homophily calculations.

Q7: Naive adversarial attacks lack strategic design and inject random or heuristic perturbations without considering hypergraph structure. Our optimized hypergraph-specific attacks balance effectiveness and stealth.

We sincerely appreciate your thorough review and constructive feedback, which have greatly contributed to improving the clarity of our work. If you have any further questions or concerns, we would be glad to provide additional clarification or discussion. Thank you once again for your time and valuable input.

[1] Wang et al., From Graphs to Hypergraphs: Hypergraph Projection and its Remediation. In ICLR, 2024.

[2] Gao et al., HGNN+: General Hypergraph Neural Networks. In TPAMI, 2023.

[3] Wei et al., Augmentations in Hypergraph Contrastive Learning: Fabricated and Generative. In NeurIPS, 2022.