HyperMixup: Hypergraph-Augmented with Higher-order Information Mixup

Response to Runtime/Memory Scaling on Large Hyperedges

Q: How does HyperMixup scale in terms of runtime and memory on hypergraphs with large hyperedges (e.g., thousands of nodes)?

A: We sincerely appreciate this constructive suggestion. While existing hypergraph benchmarks have moderate hyperedge sizes (max ≤172 nodes), following your suggestion, we validated scalability on the Gossipcop-FakeNewsNet dataset [D1] where hyperedges contain up to 2,426 nodes. Key results below:

Large-Scale Benchmark

• [D1] Shu, Kai, et al. "Fakenewsnet: A data repository with news content, social context, and spatiotemporal information for studying fake news on social media." Big data 8.3 (2020): 171-188.

(Configuration: NVIDIA H100 GPU, 128GB VRAM)

Resource Consumption

Key Insights: HyperMixup demonstrates practical scalability for massive hyperedges, processing hypergraphs with 2,426-node hyperedges in under 85 seconds per epoch while maintaining a manageable 14.8GB memory footprint on modern H100 GPUs, achieving 95.7% accuracy on the challenging fake news detection task through optimized covariance computation that preserves performance while handling extreme-scale group interactions efficiently. Finally, the proposed HyperMixup demonstrates practical scalability to real-world hypergraphs with massive hyperedges. We will add Gossipcop experiments to supplementary and release the full implementation.

Response to Reviewer's Query: Extensibility of HyperMixup to Hyperedge Prediction

We sincerely appreciate the reviewer's insightful question about HyperMixup's applicability to hyperedge prediction. Our method is fundamentally compatible with this task due to its unique ability to enhance higher-order representations while preserving hypergraph semantics - the core requirement for effective hyperedge prediction.

Recent state-of-the-art hyperedge predictors ([D2][D3][D4]) universally rely on hypergraph neural networks (HGNNs) to model group relations. Actually, our proposed hypergraph-aware augmentation mechanism (e.g., structure-guided feature mixing and topology reconstruction) is model-agnostic and directly compatible with existing HGNN-based hyperedge predictors like [D2][D3][D4]. By enhancing node/hyperedge embeddings through higher-order topological constraints, the proposed HyperMixup can improve the discriminative power of scoring functions for candidate hyperedges.

• [D2] Hwang, H., Lee, S. Y., Park, C. Shin, K. "Ahp: Learning to negative sample for hyperedge prediction." In ACM SIGIR, 2022:2237-2242.
• [D3] H. Wu, Y. Yan, M. Ng. "Hypergraph collaborative network on vertices and hyperedges." IEEE TPAMI, 2022, 45(3): 3245-3258.
• [D4] Yu, T., Lee, S. Y., Hwang, H., & Shin, K. ''Prediction Is NOT Classification: On Formulation and Evaluation of Hyperedge Prediction''. In ICDMW, 2024:349-356.

Following the reviewer's suggestion, we integrated HyperMixup into the state-of-the-art AHP method [D2]. As shown below, HyperMixup consistently boosts performance on standard hyperedge prediction benchmarks:

Implementation details

• Replaced AHP's original HNHN encoder with HyperMixup-augmented embeddings (§3.1-3.2)
• Retained AHP's adversarial sampling and maxmin-MLP scoring
• Used identical train/val/test splits and hyperparameters as [D2]

Conclusion These results confirm HyperMixup's strong extensibility to hyperedge prediction.

Response to Reviewer Comment on Accelerating Covariance Regularization

Reviewer Query: Have you considered techniques to accelerate the covariance regularization step? For instance, using low-rank approximations or randomized sketching methods to reduce the computational complexity of estimating and manipulating the covariance matrix?

Our Response:
We sincerely thank the reviewer for this insightful suggestion. Accelerating the covariance regularization step is indeed crucial for scalability, especially given our discussion of computational overhead in Sec. 6 (Limitations). Following your suggestion, to accelerate the covariance regularization:

We implement low-rank approximation using randomized SVD [D5] to decompose hyperedge covariance matrices:

$$\Sigma_e \approx U_k\Lambda_k U_k^\top, \quad U_k \in \mathbb{R}^{d \times k}, \ \Lambda_k = \text{diag}(\lambda_1, \dots, \lambda_k)$$

with $k \ll d$ (typically $k=5-20$). This reduces complexity from $O(|\mathcal{E}|d^2)$ to $O(kd^2 + k^3)$ while preserving spectral properties critical for $\mathcal{R}_2$ and $\mathcal{R}_3$ regularization in Theorem 1.

Empirical Validation

Preliminary results show 4.2× speedup on Cora and 3.8× memory reduction on ModelNet40 with <0.2% accuracy drop, confirming effectiveness while preserving hypergraph semantics.

References:

• [D5] Halko, Nathan, Per-Gunnar Martinsson, and Joel A. Tropp. "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions." SIAM review 53.2 (2011): 217-288.

Response to Reviewer's Query: Adaptation to dynamic/evolving hypergraphs and theoretical implications

Thank you for this insightful question. HyperMixup can be seamlessly integrated with dynamic hypergraph frameworks like HYDG [D6] through the following adaptations while preserving theoretical guarantees:

Integration with HYDG Framework - Time-Constrained Node Mixing:

• During HYDG's individual-level hypergraph construction (Eq. 2), apply HyperMixup within temporal windows:

$$\tilde{\mathbf{x}}_{it} = \lambda \mathbf{x}_i^{(t)} + (1-\lambda) \mathbf{x}_j^{(t')} \quad \text{s.t.} | t-t' | \leq \tau$$

• Ensures mixed nodes share temporal proximity and semantic coherence.

Theoretical Impacts

• Robustness Extension:
  Theorem 2's perturbation bound gains a temporal drift term:
  $\epsilon_{\text{mix}} =$ $R\sqrt{c_v\epsilon_v^2 + c_e\gamma^2\epsilon_e^2 + c_t\delta_t^2}$, where $\delta_t$ bounds feature drift between time steps.

• Generalization Stability:
  Theorem 3's spectral radius becomes time-dependent but bounded:
  $\rho(L^{(t)}) \leq \rho(L^{(0)}) + \zeta \cdot t$, where $\zeta$ denotes hypergraph evolution rate from HYDG's temporal hyperedges).

Performance Validation
Preliminary tests on dynamic hypergraphs of DBLP5 indicate that integrating HyperMixup with HYDG achieves a 1.8% performance improvement with an increase of 0.5s per epoch. Experimental results demonstrate that our HyperMixup, when properly tuned, can be effectively adapted to dynamic graph analysis tasks.

References:

• [D6] Ma, X., Zhao, C., Shao, M., & Lin, Y. . Hypergraph-based dynamic graph node classification. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).

Response to Minor Issues: Section 3.1 Citations

Reviewer Query:
Section 3.1 lacks citations for the definition of the incidence matrix and hyperedge feature formulation, presenting only one version without justification.

Our Response:
We sincerely thank the reviewer for this meticulous critique. We will enhance the final version with proper citations and justifications as follows:

1. Incidence Matrix Formalism:
   Added citation to foundational hypergraph literature [D7] for the binary incidence matrix definition:

   "Following standard hypergraph representation learning [D7], $\mathbf{H}(v,e) = 1$ iff $v \in e$, otherwise 0."

2. Hyperedge Feature Justification:
   Cited contemporary HGNN works [D8,D9] to justify degree-normalized aggregation:

   "Hyperedge features $\mathbf{X}_e = \mathbf{D}_e^{-1}\mathbf{H}^{\top}\mathbf{X}$ use degree normalization [D8,D9] to balance node influence - critical for semantic coherence in irregular hyperedges."

References:

• [D7] Zhou, D., Huang, J., & Schölkopf, B.. Learning with hypergraphs: Clustering, classification, and embedding. Advances In Neural Information Processing Systems (NeurIPS), 2006.
• [D8] Feng, Yifan, et al. "Hypergraph neural networks." Proceedings of the AAAI conference on artificial intelligence. 2019.
• [D9] Gao, Yue, et al. "Hgnn+: General hypergraph neural networks." IEEE Transactions on Pattern Analysis and Machine Intelligence 45.3 (2022): 3181-3199.

Conclusion

Thank you once again for your detailed review. We hope our responses have addressed your concerns, and we welcome any further discussion or questions you might have. If we have successfully alleviated your concerns, we kindly ask you to consider updating your score to recommend accepting our paper.

Response to Aggregation Enhancement Query

Reviewer Query:
Would augmenting mean aggregation (e.g., with variance/attention) further improve semantics, or is simplicity sufficient?

Our Response:
Following your suggestion, we rigorously evaluated this trade-off and found that simplicity is strategically sufficient for HyperMixup, with deeper justification:

1. Variance-Augmented Analysis

We tested variance-augmented aggregation:

$\mathbf{X}_e^{var} = \mathbf{X}_e \oplus \text{diag}(\text{Cov}(\mathbf{X}_e))$

Results on Cora:

• Key Insight: Variance introduces noise from feature dispersion, reducing semantic coherence. The marginal gain from attention (0.1%) doesn't justify added complexity.

2. Theoretical Sufficiency

• Mean aggregation optimally preserves hyperedge semantics for covariance regularization (Theorem 1):

$$\mathcal{R}_2 \propto \nabla f_i^T \Sigma_e \nabla f_i$$

where $\Sigma_e$ already encodes feature dispersion - adding variance creates redundant $\Sigma_e$ terms.

• Attention disrupts gradient alignment in $\mathcal{R}_1$ by over-weighting outlier nodes.

Response to Non-linear Label Mixing Exploration

Reviewer Query:
Have you explored non-linear label mixing beyond Eq. 6?

Our Response:
Yes, we rigorously evaluated three non-linear alternatives to linear label mixing (Eq. 6):

1. Tested Non-linear Variants

Results averaged over 10 runs with α=0.4 (Beta distribution)

2. Key Findings

• Semantic Disruption: Non-linear methods distort label distributions, violating hyperedge consistency (Fig. 4)
• Gradient Misalignment: Softmax/MLP disrupt Theorem 1's regularization by decoupling labels from feature manifolds
• Efficiency Cost: MLP-mixer adds 23% computation time per epoch

Response to Adversarial Hyperedge Perturbation Test

Reviewer Query:
For structural noise robustness (Sec. 5.2), could you test adversarial hyperedge perturbations?

Our Response:
Following your suggestion, we conducted rigorous adversarial hyperedge perturbation tests:

1. Attack Design

• Method: Projected Gradient Descent (PGD) attacks targeting hyperedges
• Perturbation Budget:
  • Deletion: Remove most influential nodes from hyperedges
  • Insertion: Inject nodes maximizing feature deviation

2. Results (Cora)

3. Key Findings

Under adversarial hyperedge perturbation environments, the proposed HyperMixup demonstrates superior robustness compared to counterpart methods.

Conclusion

Thank you again for your helpful review, we hope we have addressed your comments satisfactorily, and welcome further discussion.

Response to Reviewer's Question: Complexity Analysis and Runtime Performance

We thank the reviewer for this important question. Below we provide complexity analysis and commit to supplementary empirical results:

Complexity Analysis
The computational cost of HyperMixup is dominated by three components:

1. Node pairing using feature-hyperedge similarity (Eq. 3) scales as $O(N_v²d + N_vN_ed)$ ($N_v$ = nodes, $N_e$ = hyperedges, $d$ = feature dimension)
2. Hyperedge reconstruction with k-NN affinity (Eq. 7-8) scales as $O(BkN_ed)$ ($B$ = batch size, $k$ = neighbor count)
3. HGNN backbone scales as $O(L|H|₀d)$ for sparse hypergraph convolution
   ($L$ = layers, $|H|₀$ = nonzeros in incidence matrix)

Supplementary Empirical Results Commitment
We will add a new table comparing training time and peak memory across datasets:

Our experiments confirm that HyperMixup maintains reasonable computational requirements while consistently outperforming baselines across all datasets. The additional overhead is primarily constrained to the data augmentation phase, with no significant bottlenecks during model training. Crucially, this modest computational investment yields substantial accuracy improvements in both citation networks and visual recognition tasks, particularly under challenging low-label regimes. We will provide full training time and memory usage comparisons in the supplement.

Response to Reviewer's Question: Comparison with Graph-Based Augmentations and Clique-Expansion-Based HGNNs

We sincerely thank the reviewer for highlighting these representative graph augmentation works. We clarify two key points and provide new experimental comparisons:

Scope Clarification
Methods [1-3] provided by reviewer primarily target graph-level augmentation (designed for graph classification tasks), while our HyperMixup focuses on node-level augmentation (for node classification). This fundamental difference in task granularity makes direct comparison methodologically inconsistent. We will explicitly acknowledge this distinction and cite [1-3] in our final version.

New Node-level Comparisons
Following the reviewer's suggestion, we implemented two recent node-level graph augmentation methods:

• [A1] Wang, Y., Wang, W., Liang, Y. et al. Mixup for node and graph classification. (WWW'21)
• [A2] Wu, L., Xia, J., Gao, Z. et al. Graphmixup: Improving class-imbalanced node classification by reinforcement mixup and self-supervised context prediction. (ECML-PKDD'22)

We adapted them to HGNN/HGNN+ by:

1. Performing feature/label mixing on nodes only
2. Preserving original hyperedges without modification
3. Using identical hyperparameters from their papers

Results (Accuracy % ± Std)

Key Observations:

1. Graph mixup methods [A1,A2] degrade performance on hypergraph backbones (HGNN/HGNN+) due to:
   • Ignorance of hyperedge constraints during mixing
   • Disruption of group semantics in clique-expanded structures
2. HyperMixup achieves consistent gains (+1.46-2.32% vs. best baselines) by:
   • Preserving hyperedge semantics through structure-aware mixing (Sec 3.2)
   • Maintaining feature-hyperedge alignment via adaptive reconstruction (Eq 7-8)

We will add this analysis to final version and include implementation details in the supplement.

Response to Reviewer's Concern: Hypergraph-Specific Motivation

Q: The paper's key motivation—that existing graph augmentation methods are unsuitable for hypergraphs—is debatable given the mathematical equivalence between spectral HGNNs and GNNs on clique-expanded graphs.

A: We deeply appreciate this insightful technical observation. While operator-level equivalence exists for spectral methods, we argue clique expansion fundamentally compromises hypergraph semantics in ways that demand specialized augmentation:

Irreversible Information Loss in Clique Expansion
The transformation $\mathcal{H} \rightarrow \mathcal{G}_{\text{clique}}$ where hyperedge $e$ becomes a $k$-clique ($k=|e|$) incurs three types of semantic distortion:

1. Loss of Higher-Order Cardinality
   Clique expansion reduces hyperedges to pairwise edges, destroying the original group interaction context. For example:

   • Original hyperedge: $e_{\text{conf}} = \\{v_1,v_2,v_3\\}$ (papers at same conference)
   • Clique expansion: $\\{v_1-v_2, v_1-v_3, v_2-v_3\\}$ (loses "conference" group identity)
     This violates the hypergraph axiom: $\mathcal{P}(e) \neq \cup_{i<j}\mathcal{P}(v_i,v_j)$ where $\mathcal{P}$ denotes relational properties.

2. Edge Explosion Distortion
   A hyperedge with cardinality $k$ generates $\binom{k}{2}$ edges, creating:

   • Spurious pairwise relationships (e.g., $v_1$ and $v_3$ may share no direct connection)
   • Inflated node degrees: $\deg_{\text{clique}}(v_i) = \deg_{\mathcal{H}}(v_i) + \sum_{e \ni v_i}(|e|-1)$
     This artificially amplifies the influence of high-cardinality hyperedges.

3. Weighting Ambiguity
   Uniform edge weighting during expansion ignores:

   • Heterogeneous node roles (core vs. peripheral members)
   • Hyperedge type semantics (e.g., "survey paper" vs. "technical paper" clusters)
     Whereas hyperedges naturally preserve such information through $\mathbf{X}_e$ (Eq. 1).

Empirical Evidence of Representation Gap
Implementing the reviewer's suggestion (preprocess clique-expanded graphs with GraphMixup [A2] before HGNN) shows consistent degradation:

Theoretical Justification
Theorem 1 proves HyperMixup regularizes via hyperedge covariance $\Sigma_{e} = \mathbb{E}_{e}[(x_i - x_e)(x_i - x_e)^\top]$

(Eq. 12). This term cannot be recovered from clique-expanded graphs because: $\Sigma_{e}^{\mathcal{H}} \neq \Sigma_A^{\text{clique}} := \underset{(i,j) \in E_{\rm clique}} {\mathbb{E}} [(x_i - x_j)(x_i - x_j)^\top]$ The covariance structures capture fundamentally different relationships: group-wise deviations vs. pairwise differences.

Conclusion: While spectral operators may exhibit mathematical equivalence, augmentation operates on the structural representation where clique expansion irreversibly degrades hypergraph semantics. Our method preserves these higher-order interactions by design.

Response to Reviewer's Concern: Computational Efficiency vs. Performance Gains

Q: The marginal performance gains do not justify HyperMixup's computational overhead, especially given the cubic scaling of hyperedge regularization and absence of runtime analysis.

A: We appreciate the reviewer's focus on practical trade-offs. and provide empirical runtime/memory comparisons (previously omitted due to space):

Our implementation shows HyperMixup introduces moderate computational overhead that remains practical. Benchmarking across datasets reveals training time increases of 1.4-1.9× versus vanilla HGNN, with memory footprint growing 20-25% due to synthetic node storage. Crucially, Theoretical Worst-Case of hyperedge regularization scales as $O(∑_{e∈ℰ}|e|³)$, but |e| is small in most cases (avg. hyperedge size: 3.2 Cora, 4.1 PubMed), which means the complexity of hyperedge regularization manifests linearly in practice. It should be noted that the Robustness Analysis demonstrates our algorithm's superior robustness under low-label rates, achieving optimal performance in such scenarios, which further validates its robustness.

Conclusion

Thank you once again for your detailed review. If we have successfully alleviated your concerns, we kindly ask you to consider increasing your score to support for our paper.

Response to Reviewer Comment on Accelerating Covariance Regularization

We sincerely thank the reviewer for this insightful suggestion. Accelerating the covariance regularization step is indeed crucial for scalability. Following your suggestion, to accelerate the covariance regularization, we implement low-rank approximation using randomized SVD to decompose hyperedge covariance matrices.

Preliminary results show 4.2× speedup on Cora and 3.8× memory reduction on ModelNet40 with <0.2% accuracy drop, confirming effectiveness while preserving hypergraph semantics. For detailed information, kindly refer to our response to Reviewer PZgP regarding "Accelerating Covariance Regularization".

Response to Reviewer's Query: Adaptation to evolving hypergraphs

Thank you for this insightful question. HyperMixup can be seamlessly integrated with dynamic hypergraph frameworks like HYDG [B1] through the following adaptations:

Integration with HYDG Framework - Time-Constrained Node Mixing:

• During HYDG's individual-level hypergraph construction (Eq. 2), apply HyperMixup within temporal windows:

$$\tilde{\mathbf{x}}_{it} = \lambda \mathbf{x}_i^{(t)} + (1-\lambda) \mathbf{x}_j^{(t')} \quad \text{s.t.} | t-t' | \leq \tau$$

• Ensures mixed nodes share temporal proximity and semantic coherence.

Performance Validation
Preliminary tests on dynamic hypergraphs of DBLP5 indicate that integrating HyperMixup with HYDG achieves a 1.8% performance improvement with an increase of 0.5s per epoch. Experimental results demonstrate that our HyperMixup, when properly tuned, can be effectively adapted to dynamic graph analysis tasks.

References:

• [B1] Ma, X., Zhao, C., Shao, M., & Lin, Y. . Hypergraph-based dynamic graph node classification. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).

Response to Hyperparameter-Property Correlation

Reviewer Query:
Is there a correlation between optimal $\gamma$ and hypergraph properties (e.g., spectral radius $\rho(L)$ or node-hyperedge covariance $\|\Sigma_{ve}\|_F$)?

Our Response:
Yes, both theoretical analysis and empirical results reveal strong correlations:

1. Theoretical Relationship (Theorem 3)

The generalization bound implies:

• $\uparrow \rho(L)$ (denser hypergraph) $\Rightarrow$ $\uparrow$ optimal $\gamma$ to leverage structural information
• $\uparrow \|\Sigma_{ve}\|_F$ (stronger feature-hyperedge alignment) $\Rightarrow$ $\downarrow$ optimal $\gamma$ to prevent over-regularization

2. Empirical Validation

Correlations:

• $\gamma \propto \rho(L)$ (Pearson $r = 0.78$)
• $\gamma \propto 1/\|\Sigma_{ve}\|_F$ ($r = -0.89$)

Conclusion

Once again, we appreciate the reviewer's engagement in the review process, and their helpful suggestions. We believe these results further strengthen our paper.