Parameter-Free Hypergraph Neural Network for Few-Shot Node Classification

We greatly appreciate your high recognition of our work, and are eager to share our thoughts with you.

Response to Question 1:

Question 1: Can the authors provide error bounds for closed-form approximation in Theorem 1?

Yes, we believe more discussion on the error bounds can make our theoretical claim stronger. We present a summary of our analysis as follows, which will be included in the final version of our paper as well.

In TCS, our approximation is given as follows:

$$\frac{1}{\lambda_1^2}M_1+\frac{1}{\lambda_2^2}M_2+\frac{1}{\lambda_3^2}M_3 \approx \frac{1}{\epsilon}\left(\frac{1}{\lambda_1}M_1+\frac{1}{\lambda_2}M_2+\frac{1}{\lambda_3}M_3\right),$$

where

• $\lambda_1 = \epsilon$
• $\lambda_2 = (1 - 2\epsilon)k + \epsilon$
• $\lambda_3 = k(1 - 2\epsilon + \epsilon c) + \epsilon$

and the matrices form an orthogonal decomposition:

• $M_1 = I_{kc} - \frac{1}{k}(I_c \otimes J_k)$
• $M_2 = \frac{1}{k}(I_c \otimes J_k) - \frac{1}{kc}J_{kc}$
• $M_3 = \frac{1}{kc} J_{kc}$

Here, $J$ denotes an all-one matrix and $\otimes$ is the Kronecker product.

To evaluate the approximation quality, we compute the relative Frobenius norm error:

$$\frac{\left\|\frac{1}{\lambda_1^2}M_1+\frac{1}{\lambda_2^2}M_2+\frac{1}{\lambda_3^2}M_3 - \frac{1}{\epsilon}\left(\frac{1}{\lambda_1}M_1+\frac{1}{\lambda_2}M_2+\frac{1}{\lambda_3}M_3\right)\right\|_F}{\left\|\frac{1}{\lambda_1^2}M_1+\frac{1}{\lambda_2^2}M_2+\frac{1}{\lambda_3^2}M_3\right\|_F}$$

For a representative case with $k = 5$, $c = 10$, the relative errors are as follows:

These results indicate that the approximation becomes increasingly accurate as $\epsilon$ decreases. This supports the validity of our approach, particularly in the regime where $\epsilon$ is sufficiently small.

Response to Question 2:

Question 2: Can the authors clarify the unit used in Table 4?

Thank you for your suggestion. As shown in Table 4, the values represent the running times relative to ZEN, and thus no explicit unit is indicated. The actual running times are reported in the table below, with all values measured in seconds (s). ZEN runs in less than a second across all datasets, achieving as fast as 0.003s on the Senate dataset.

Thank you for your recognition of our work and providing the valuable suggestions and constructive comments. Your thoughtful feedback is deeply appreciated and will greatly assist us in refining and strengthening the manuscript.

Response to Question 1:

Question 1: Why do the authors focus on few-shot classifications? Is it possible to use ZEN for non-few-shot settings?

ZEN is a parameter-free model, which gives it a particular advantage in settings where labeled data is scarce and training is challenging. While ZEN was orginally designed for few-shot setting, our results in the tables below show it performs strongly with more training samples as well. ZEN achieves top average ranks in both 10-shot and 20-shot settings, suggesting it scales well beyond few-shot scenarios.

10-shot classification (10 training nodes per class)

20-shot classification (20 training nodes per class)

Response to Question 2:

Question 2: Could you add the actual running time in ZEN?

Thank you for the suggestion. The actual running times are reported in the table below, with all values measured in seconds (s). ZEN runs in less than a second across all datasets, achieving as fast as 0.003s on the Senate dataset.

Thank you for your valuable comments. Your feedback is greatly appreciated and helps us improve the clarity and quality of our work. We will do our best to address them in the planned revision.

Response to Weakness 1:

Weakness 1: As acknowledged by the authors, ZEN is specifically designed for node classification. Extensions to other hypergraph tasks (e.g., hyperedge prediction, clustering) are left as future work. This means the scope of applicability of this work is limited. The authors may consider analyzing the effectiveness of the work in other tasks.

We fully agree on the importance of assessing our method on other tasks. Some tasks, such as hyperedge prediction, can be reformulated as node classification, allowing ZEN to be applied without modification—for example, by treating hyperedges as nodes using $X_e=D_e^{-1}H^\top X, H_e=H^\top$. For tasks not easily reducible to this setting, ZEN may require further adaptation. We plan to explore such extensions in future work.

Response to Weakness 2:

Weakness 2: The paper discusses the success of linear GNNs such as SGC and APPNP, but does not directly compare ZEN to their hypergraph counterparts or generalizations. A direct comparison with a naïve linearized hypergraph model (beyond HGNN) would provide a stronger baseline.

Thank you for your detailed feedback. We have additionally included three representative linear GNNs (SGC [1], APPNP [2], and SSGC [3]) and three linearized hypergraph models based on UniGCNII [4], AllDeepSets [5], and ED-HNN [6]. For GNNs, we applied clique expansion to convert the hypergraph into a pairwise graph. As shown in the table below, ZEN demonstrates consistently strong performance, outperforming all linear GNN and linearized hypergraph baselines on the majority of datasets.

Response to Weakness 3:

Weakness 3: ZEN is limited to 2-hop propagation. While this is justified by computational cost and redundancy, it may restrict representational power on deeper hypergraph structures. A discussion on possible approximations or sampling strategies for deeper propagation would be a valuable addition.

Thank you for your suggestion. We agree that some datasets may require models with higher-hop propagations for better expressivity. Without approximation, the exact computation of RSI requires high computational cost.

One possible approximation is to estimate the probability that a random walker returns to the starting node after $l$ steps, where $l$ is the number of hops that we aim to model. A simple pseudocode for this strategy is as follows:

• Start at node $i$.
• At each step:
  1. Uniformly sample a hyperedge incident to the current node.
  2. Uniformly sample a node connected to that hyperedge.
• Repeat this process for $l$ steps.
• Record whether the walk ends at the original node $i$. The return probability may serve as an approximation of node-wise self-information at a given hop.

Another possible approximation is to use Hutchinson's Estimator, which provides an unbiased stochastic estimate of the diagonal entries. The equation is given by:

$$\operatorname{diag}(A) \approx \frac{1}{m} \sum_{k=1}^m z^{(k)} \odot \left( A z^{(k)} \right)$$

where:

• $m$ is the number of random probe vectors,
• each $z^{(k)} \in \mathbb{R}^n$ is a random vector with entries independently sampled from the Rademacher distribution (i.e., each entry is $+1$ or $-1$ with equal probability),
• $\odot$ denotes the element-wise (Hadamard) product.

The expectation satisfies

$$\operatorname{diag}(A) = \mathbb{E} \left[ z \odot (A z) \right].$$

Hutchinson's Estimator does not require explicit storage of the entire matrix $A$; instead, it relies solely on matrix-vector multiplications with randomized vectors $z$. This characteristic renders Hutchinson's Estimator particularly suitable and computationally efficient for hypergraph structures.

We consider these approaches to be promising directions for extending ZEN to scenarios where deeper propagation may provide additional benefits.

Response to Weakness 4:

Weakness 4: Lack of baselines. The authors focus on the task of few-shot node classification. However, they only conduct experiments with hypergraph neural networks (HNN) models. There are multiple few-shot node classification works that can act as baselines.

We appreciate the suggestion to strengthen our evaluation by including additional baselines. To the best of our knowledge, there has been no hypergraph model explicitly addressing few-shot node classification as a direct keyword. In response, we have included two semi-supervised hypergraph models—LEGCN [7] and HyperND [8]—as additional baselines. LEGCN utilizes a line expansion approach to adapt hypergraphs to conventional GNN architectures, while HyperND introduces a diffusion-based mechanism for improved label propagation in hypergraphs. As shown in the table below, ZEN consistently demonstrates strong performance, outperforming all additional baselines across the majority of datasets.

References

[1] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In PMLR, 2019. URL https://proceedings.mlr.press/v97/wu19e.html.

[2] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank, 2022. URL https://arxiv.org/abs/1810.05997.

[3] Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International conference on learning representations, 2021.

[4] Jing Huang and Jie Yang. Unignn: a unified framework for graph and hypergraph neural networks, 2021. URL https://arxiv.org/abs/2105.00956.

[5] Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. You are allset: A multiset function framework for hypergraph neural networks, 2022. URL https://arxiv.org/abs/2106.13264.

[6] Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, and Pan Li. Equivariant hypergraph diffusion neural operators, 2023. URL https://arxiv.org/abs/2207.06680.

[7] Yang, Chaoqi and Wang, Ruijie and Yao, Shuochao and Abdelzaher, Tarek. Semi-supervised hypergraph node classification on hypergraph line expansion. CIKM, 2022. URL https://arxiv.org/abs/2005.04843.

[8] Konstantin Prokopchik, Austin R Benson, and Francesco Tudisco. Nonlinear feature diffusion on hypergraphs. PMLR, 2022. URL https://arxiv.org/pdf/2103.14867.

Thanks for your thoughtful feedback. We appreciate your constructive review, which has helped us improve the clarity and quality of the paper.

Response to Weakness 1:

Weakness 1: While the paper addresses the problem of few-shot node classification, it does not follow the conventional n-way k-shot learning paradigm in the evaluation setup. This deviation from standard practices should be discussed or justified.

To address the concerns, we would like to respectfully provide clarification on our task formulation. We define our few-shot node classification task as a transductive, semi-supervised node classification under severe label constraints. In standard n-way k-shot learning, the entire set of classes is typically partitioned into disjoint training and test sets. From each set, n classes are sampled, and k labeled examples per class are selected to construct support sets for episodic training. The model is trained on a variety of such tasks in order to evaluate its capacity for adaptation and generalization to novel, unseen tasks. In contrast, our setting can be regarded as a more challenging variant, where the class set remains fixed and identical to the test classes, and n corresponds to the total number of classes.

To avoid potential confusion with n-way k-shot learning from the meta-learning literature, we are open to revising our terminology in the revised version of our paper to reflect this distinction more clearly; e.g., hard few-shot node classification or semi-supervised node classification with hard label scarcity.

On the other hand, it would be interesting to see how our approach fits into the standard n-way k-shot setting. To the best of our knowledge, this setup has not been explicitly explored for general hypergraphs. Accordingly, we designed a new evaluation protocol by drawing inspiration from the experimental setup of Meta-GNN [1] and adopting hyperparameter configurations aligned with those used in ED-HNN [2]. The results are reported in the table below.

The strong performance of ZEN in this setting highlights its potential as an effective approach for standard few-shot tasks on hypergraphs. Interestingly, ZEN yields promising results even when applied solely to test episodes, suggesting a potentially valuable and underexplored direction. We appreciate the opportunity to highlight this aspect and will consider it an important avenue for future research.

Response to Weakness 2:

Weakness 2: The ablation study shows that removing certain components of ZEN may lead to improved performance, which requires further discussion.

It is true that removing RAP or TCS leads to performance improvements on some datasets (Congress and Senate for RAP, 20News and MN40 for TCS). To analyze this behavior, we examine the ratio of hyperedges to nodes (i.e., density), which we believe an important factor to understand the characteristic of a dataset. The results are reported in the table below.

We observe that RAP improves performance on datasets with low density, while it slightly degrades performance on Congress and Senate, which have densities greater than 1. This aligns with the intuition: as the number of neighbors increases, each node's contribution diminishes due to degree normalization, reducing the relative influence of self-information. In such cases, removing self-information via RAP may have limited or even adverse effects.

As for TCS, it assumes good node embeddings. In the ablation study, the impact of removing TCS is more significant on 20News than on MN40. This may due to the extremely low density of 20News, where ZEN, which relies solely on propagation to refine embeddings, may have struggled to produce sufficiently informative representations.

On the other hand, the result on MN40 may have been influenced by its large number of classes — 40, the highest among all datasets. The relative Frobenius norm error of TCS is given by:

$$\frac{\left\|\frac{1}{\lambda_1^2}M_1+\frac{1}{\lambda_2^2}M_2+\frac{1}{\lambda_3^2}M_3 - \frac{1}{\epsilon}\left(\frac{1}{\lambda_1}M_1+\frac{1}{\lambda_2}M_2+\frac{1}{\lambda_3}M_3\right)\right\|_F}{\left\|\frac{1}{\lambda_1^2}M_1+\frac{1}{\lambda_2^2}M_2+\frac{1}{\lambda_3^2}M_3\right\|_F}$$

As shown in the table below, this approximation error slightly increases with the number of classes:

Although the error remains small overall, the increase suggests that the approximation may become less accurate as the number of classes grows, which could partially explain the results observed on MN40.

References

[1] Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Ji Geng. Meta-gnn: On few-shot node classification in graph meta-learning. CIKM, 2019. URL https://doi.org/10.1145/3357384.3358106.

[2] Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, and Pan Li. Equivariant hypergraph diffusion neural operators, 2023. URL https://arxiv.org/abs/2207.06680.