Pith. sign in

REVIEW 4 major objections 6 minor 77 references

Generalization Performance of Hypergraph Neural Networks

T0 review · 4 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper derives the first margin-based PAC-Bayes generalization bounds for four classes of hypergraph neural networks, showing that test error is governed by hypergraph statistics (maximum node degree, hyperedge size, incidence-set…

desk verdict First PAC-Bayes analysis for hypergraph NNs, but the T-MPHN theorem is unproven and two other theorems don't match their appendix; the UniGCN part looks salvageable. read the letter →

arxiv 2501.12554 v2 pith:47T7FI4Q submitted 2025-01-22 cs.LG

Yifan Wang , Gonzalo R. Arce , Guangmo Tong This is my paper · ORCID
classification cs.LG MSC 68T0768Q3205C65
keywords GraphClassificationHypergraphNeuralNetworksLearningTheoryPAC-Bayesboundsmarginlossperturbationanalysisgeneralization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper seeks the first theoretical handle on when hypergraph neural networks generalize: it derives margin-based PAC-Bayes bounds for four representative architectures — UniGCN (convolutional), AllDeepSets (set-based), M-IGN (invariant/equivariant), and T-MPHN (tensor-based) — in the hypergraph classification setting. The bounds say that test error is controlled by simple hypergraph statistics (maximum node degree $D$, maximum hyperedge size $M$, maximum number of incident hyperedges $R$), the number of layers, the hidden width, and the spectral norms of the learned weights. The point of such a result is that it names the structural quantities that make higher-order learning succeed or fail, which pairwise-graph bounds cannot do, and it gives practitioners a quantity to track during training. The paper further reports that the theoretical bounds and empirical losses move together across synthetic and real datasets, with the alignment improving after training.

What carries the argument

The load-bearing object is the perturbation analysis: for each model, the proof bounds how much the output can change when each weight matrix is perturbed by a small Gaussian noise $u$, decomposing the change into (a) the maximum node-representation norm $\Phi_l$ in each layer and (b) the maximum output variation $\Psi_l$ induced by perturbed weights. These two quantities satisfy a recursion $\Psi_l \le C\,\Psi_{l-1}\|W^{(l)}+U^{(l)}\| + C\,\Phi_{l-1}\|U^{(l)}\|$ with $C = DRM$ for UniGCN (analogous constants for the other models), and the recursion is solved by observing that $\{\Phi_l\}$ forms a geometric sequence. This perturbation bound is then fed into the standard PAC-Bayes margin lemma (Lemma 5), with a normalization trick that rescales all layers to a common spectral norm $\beta$ and a covering argument that keeps the KL divergence tractable. For T-MPHN, row-wise normalization caps $\Psi_l$ by 2, which is what removes the hypergraph statistics from its bound.

What would settle it

Compute the perturbation bound of Lemma 4 for a trained T-MPHN whose last layer satisfies $\|W^{(L+1)}\| = \gamma$ (which lies inside the interval $[\gamma/2, \gamma\sqrt{m}/2]$ for any $m \ge 4$): the bound is at least $2\gamma$, eight times the $\gamma/4$ threshold of Lemma 5, so the perturbation condition $\Pr[\max_A \|f_{w+u}(A) - f_w(A)\|_\infty < \gamma/4] \ge 1/2$ cannot hold for any noise distribution, and this single check determines whether Theorem 4's derivation, as written, goes through.

Watch

Extended reading notes

Core claim

The central claim is that the generalization error of a hypergraph neural network trained with a margin objective is, with high probability, bounded above by its empirical margin loss plus a complexity term of order $\sqrt{(L^2 B^2 h \ln(Lh)(RMD)^L W_1 W_2 + \log(mL/\sigma))/(\gamma^2 m)}$ for UniGCN, with structurally identical terms for the other three architectures. The factor $(RMD)^L$ is the heart of the result: each propagation step multiplies the perturbation sensitivity by the product of the maximum incidence-set size, the maximum hyperedge size, and the maximum node degree, so deep models on dense, large-hyperedge hypergraphs are provably harder to generalize. For the tensor-based model T-MPHN, row-wise normalization collapses the dependence: the perturbation bound becomes the constant $2\|W^{(L+1)}\| + 3\|U^{(L+1)}\|$, removing $D$, $M$, and $R$ entirely. The paper also reports empirical consistency: Pearson correlations between theoretical bounds and empirical loss are mostly positive and often close to 1, and training (with weight decay) improves the alignment.

Load-bearing premise

The load-bearing premise is that for every weight scale the theorems handle, one can choose Gaussian perturbation noise small enough that outputs shift by less than a quarter of the margin $\gamma$ with probability at least $1/2$, while keeping the KL term finite; for T-MPHN, the paper's own perturbation bound $2\|W^{(L+1)}\| + 3\|U^{(L+1)}\|$ already exceeds $\gamma/4$ whenever $\|W^{(L+1)}\| \ge \gamma/2$, so that premise is not satisfied in the middle interval Theorem 4 must cover.

Editorial extensions

If this is right

  • Generalization degrades exponentially in depth: each layer multiplies the bound by the factor $DRM$ (maximum node degree times maximum hyperedge size times maximum incident-hyperedge count), so dense, large-hyperedge hypergraphs require exponentially more data to reach a fixed test error.
  • The bounds provide a training-time diagnostic: tracking weight spectral norms and hypergraph statistics should track test error, and the paper's experiments report Pearson correlations that are mostly positive and often near 1, improving after training.
  • Setting $M = R = 1$ reduces the UniGCN bound to the known graph-neural-network PAC-Bayes bound, so the hypergraph result recovers the GNN analysis as a special case.
  • For the tensor model T-MPHN, row-wise normalization removes $D$, $M$, and $R$ from the bound entirely, predicting that this architecture's generalization depends only on its last layer's spectral norm and the number of training samples.
  • The same machinery extends to node classification: treating each node's output as a subnetwork and applying a union bound over nodes and classes yields a per-node generalization bound of the same shape.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • My reading: the reported correlations are between empirical loss and bounds computed from the same fitted weights, so both curves share their inputs (weight norms, depth, hypergraph statistics); the correlation therefore shows the bound tracks the same factors as the loss, not that the bound is tight. An independent test would clamp weight norms across datasets with varying $D$, $M$, $R$ and check
  • A testable prediction the paper leaves implicit: holding architecture and training budget fixed, the sample size needed to reach a given test error should grow multiplicatively with $(RMD)^L$; the twelve synthetic datasets with varying $M$ and $R$ could be used to check this directly.
  • The T-MPHN step in Theorem 4 deserves scrutiny: Lemma 4's bound $2\|W^{(L+1)}\| + 3\|U^{(L+1)}\|$ cannot be driven below $\gamma/4$ when $\|W^{(L+1)}\| \ge \gamma/2$, the middle of the interval the theorem must cover, so that proof path needs an additional argument or an extra assumption if it is to hold as stated.
  • The normalization trick that makes the KL term tractable requires homogeneous activations, which is why attention-based models with softmax are excluded; a scale-normalized or temperature-tempered attention mechanism would be a natural test case for extending the same recursion.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes margin-based PAC-Bayes generalization bounds for four representative hypergraph neural network families: UniGCN, AllDeepSets, M-IGN, and T-MPHN, with an additional analysis of HGNN/HGNN+. The main theorems claim bounds of the form L_D ≤ L_{S,γ} + O(...), with the complexity term depending on hypergraph statistics (maximum degree D, hyperedge size M, incidence size R), depth L, hidden dimension h, and spectral norms of the learned weights. The appendix contains perturbation lemmas, a covering argument over normalized weights, and the proof details. The empirical section compares computed bounds with empirical losses on synthetic and real datasets and reports Pearson correlations.

Significance. If the four theorems were established, the paper would be a useful first theoretical step for hypergraph classification, and the proposed decomposition of the perturbation analysis into a bound on the maximum node representation and a bound on layerwise output variation is a reasonable strategy. The authors also provide source code and data, and they report the poor T-MPHN correlation cases rather than hiding them, which is a transparency strength. However, the proofs as written contain internal inconsistencies of exponential magnitude in three of the four main bounds, and the T-MPHN perturbation condition cannot be met in part of the interval the proof must cover. The central claim of the paper is therefore not supported by the supplied derivations.

major comments (4)
  1. [Theorem 4 / Appendix C.8 / Lemma 4 / Lemma 5] Lemma 5 (Appendix B) requires Pr_u[sup_A ||f_{w+u}(A) − f_w(A)||_∞ < γ/4] ≥ 1/2. Lemma 4 gives ||T-MPHN_{w+u}(A) − T-MPHN_w(A)||_2 ≤ 2||W^{(L+1)}|| + 3||U^{(L+1)}||. In the proof of Theorem 4 (C.8), the weights are normalized so that ||W^{(i)}|| = β, and the interval (26) is [γ/2, γ√m/2]. For any β in this interval, the deterministic term 2β is at least γ, which already exceeds γ/4, so the bound used by the proof cannot satisfy the Lemma 5 condition. The proposed Gaussian construction σ = (γL − 8L4β)/(12L√(2h ln 4h)) is negative for β ≥ γL/(8(L+1)), in particular at the lower endpoint β = γ/2. Thus no positive-variance perturbation satisfying the stated bound exists in the interval that the proof must cover, and Remark 6's assertion that the perturbation condition is 'always satisfied' is contradicted by the proof's own equations. Theorem 4 is therefore not derived.
  2. [Theorem 2 / Lemma 2 / Remark 2 / Appendix C.4 and D.2] The main-text Theorem 2 claims a bound with dependence (RM)^L, while Lemma 2 and Remark 2 use C_A = (M+1)(R+1), and the KL computation in C.4 leads to a bound containing C_A^{2L}. The bound calculation in D.2 uses C^{2L} with C = max(M,R). These expressions differ by exponential factors in M and R, so the statement of Theorem 2 is not the quantity proven in the appendix. The same mismatch propagates to Table 1, which reports O(M^L R^L) for AllDeepSets.
  3. [Theorem 3 / Appendix C.6 / Appendix D.2] Theorem 3 states C_I2 = (MD)^L B^2 h ln(Lh) (E(1,L))^2 inside the square root, so the bound depends on (MD)^L. However, the KL computation in C.6 contains a factor (MD)^L inside a constant that is then squared through the KL term, yielding (MD)^{2L}, and the empirical bound formula in D.2 also uses (MD)^{2L}. This is an exponential gap in the claimed dependence on M and D. Consequently, the M-IGN bound as stated is not the bound established by the appendix.
  4. [Remark 6 / Theorem 4] The remark states that for T-MPHN 'the perturbation bound here is always satisfied without any assumption on the spectral norm of perturbations and weights.' This is not consistent with the proof of Theorem 4, which relies on the covering interval [γ/2, γ√m/2] and chooses σ as a function of β. The claim in the remark removes exactly the assumption that is load-bearing for Lemma 5 but provides no alternative construction of prior and posterior distributions. The reader's stress-test concern therefore lands: the T-MPHN proof is incomplete as written.
minor comments (6)
  1. [Section 3.1, Definition 1] In the definition of the ⊗ operation, the expression 'B[I, :, :]' uses an undefined uppercase 'I'; this should be the row index of A, presumably lowercase 'i'.
  2. [Appendix D.2 / Remark 2] The parameter count for AllDeepSets is inconsistent: Remark 2 and C.4 use L2 = 4L+1, while D.2 defines L2 = 2L+1. The normalization scheme depends on this count, so the discrepancy should be resolved.
  3. [Theorem 4 statement] The displayed bound in Theorem 4 is syntactically ambiguous: the denominator is not clearly grouped, and the term '||W^{(L+1)}||^2 m' appears to be inside the square-root denominator in the main text but is different from the denominator m(γ − ||W^{(L+1)}||)^2 used in Eq. (25). Please correct the typesetting and align the statement with the proof.
  4. [Section 4.6] The paragraph claiming that setting M = 1 and R = 1 recovers the GNN bound of [38] drops the factor D^L that is still present in Theorem 1 under that substitution. As written, the claimed reduction is not accurate.
  5. [Section 5.2 / Figures 2 and 3] The Pearson correlations are reported for curves that are also displayed after Savitzky-Golay smoothing. Please state explicitly whether the coefficients are computed on the raw values or on the smoothed curves, since smoothing can inflate correlation estimates.
  6. [Throughout] There are several typographical and naming inconsistencies, including 'Futher Discussions' in the conclusion heading, 'AllDeepSet' versus 'AllDeepSets', and 'M-GIN' versus 'M-IGN' in Tables 6 and elsewhere. Please proofread and standardize the notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the PAC-Bayes bounds are derived from explicit perturbation lemmas and standard external framework, not from data-fitting or self-citation; residual concerns are proof-correctness issues rather than circularity.

full rationale

Score 0. The paper's claimed derivation chain runs from explicit model definitions and spectral-norm perturbation analyses (Lemmas 1-4) to a standard PAC-Bayes application (Lemma 5). No parameter is fitted to the quantity being bounded: the quantities D, M, R, B, h, and the spectral norms W1, W2 are computed from the architecture, the input hypergraph statistics, and the trained weights, not tuned to make the empirical loss or generalization error match. The use of Neyshabur et al.'s Lemma 5 is an external, standard framework result, and the paper's reduction of its UniGCN bound to the known GNN result of Liao et al. for M=R=1 is an explicit specialization, not a load-bearing self-citation. The T-MPHN architecture is defined in the paper itself (Section 4.5), and the citation to the prior T-MPHN paper is provenance rather than an unverified premise used to force a conclusion. The empirical correlation study is at most partly structural because the plotted bound contains the empirical-loss term, but that observation is not used in the derivation of Theorems 1-4 and does not fit any parameter. There are serious proof-validity concerns, notably that Lemma 4's bound 2||W^(L+1)|| + 3||U^(L+1)|| and the sigma formula in Appendix C.8 appear to make Theorem 4's perturbation condition unsatisfiable for beta in the middle interval [gamma/2, gamma sqrt(m)/2]; there are also internal mismatches between theorem statements and appendix formulas for AllDeepSets and M-IGN. These are correctness gaps, not circular reductions, so they do not raise the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The bounds rely on standard PAC-Bayes machinery and assumptions about feature norms and ReLU properties; no free parameters were fitted to data. The main issue is not circularity but internal inconsistency between theorem statements and appendix computations.

assumptions (5)
  • standard math PAC-Bayes margin bound (Lemma 5 adapted from Neyshabur et al. [48])
    Core framework; requires prior independent of training data and a perturbation condition.
  • domain assumption Feature norms are bounded: ||X[i,:]||_2 ≤ B and ||Z[k,:]||_2 ≤ B (Section 3.1)
    Used throughout the perturbation bounds; not verified on the empirical datasets.
  • standard math ReLU is 1-Lipschitz and positive homogeneous
    Lipschitz property used for perturbation recursions; homogeneity used for weight normalization in Theorems 1 to 4.
  • standard math Spectral norm concentration for Gaussian perturbation matrices (Tropp bound, Eq. 8 in Appendix C.2)
    Used to turn Gaussian weight perturbations into high-probability spectral norm bounds.
  • domain assumption Multiclass margin loss with margin γ
    Standard definition (Eq. 2); bounds hold for any γ > 0.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generalization Performance of Hypergraph Neural Networks." pith.science (2026). https://pith.science/paper/47T7FI4Q

@misc{pith2026250112554,
  author       = {Pith},
  title        = {Pith review of: Generalization Performance of Hypergraph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/47T7FI4Q}},
  note         = {Machine review of arXiv:2501.12554}
}
read the original abstract

Hypergraph neural networks have been promising tools for handling learning tasks involving higher-order data, with notable applications in web graphs, such as modeling multi-way hyperlink structures and complex user interactions. Yet, their generalization abilities in theory are less clear to us. In this paper, we seek to develop margin-based generalization bounds for four representative classes of hypergraph neural networks, including convolutional-based methods (UniGCN), set-based aggregation (AllDeepSets), invariant and equivariant transformations (M-IGN), and tensor-based approaches (T-MPHN). Through the PAC-Bayes framework, our results reveal the manner in which hypergraph structure and spectral norms of the learned weights can affect the generalization bounds, where the key technical challenge lies in developing new perturbation analysis for hypergraph neural networks, which offers a rigorous understanding of how variations in the model's weights and hypergraph structure impact its generalization behavior. Our empirical study examines the relationship between the practical performance and theoretical bounds of the models over synthetic and real-world datasets. One of our primary observations is the strong correlation between the theoretical bounds and empirical loss, with statistically significant consistency in most cases.

Figures

Figures reproduced from arXiv: 2501.12554 by the authors.

Figure 1
Figure 1. Consistency between empirical loss (Emp) and theo [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Consistency between empirical loss (Emp) and the [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Each subgroup, labeled by [𝐿, 𝑟1, 𝑟2], presents the consistency results on ER datasets for UniGCN (top row) and AllDeepSets (bottom row) with trained (left with 𝑟1) and random parameters (right with 𝑟2). an observation is promising in the sense that it is arguably over￾ambitious to expect that the empirical loss matches perfectly with the theoretical bounds. However, we also observed corners where such a correlation… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Consistency between empirical loss (Emp) and theoretical bounds (Theory). Each subgroup labeled by [graph type, [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]
Figure 5
Figure 5. Figure 5: Results on DBLP. Each subgroup labeled by [model, [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]
Figure 6
Figure 6. Figure 6: Results on Collab. Each subgroup labeled by [model, [PITH_FULL_IMAGE:figures/full_fig_p036_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 65 canonical work pages

  1. [1]

    Emmanuel Abbe. 2018. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research 18, 177 (2018), 1–86

    2018

  2. [2]

    Alessia Antelmi, Gennaro Cordasco, Mirko Polato, Vittorio Scarano, Carmine Spagnuolo, and Dingqi Yang. 2023. A survey on hypergraph representation learning. Comput. Surveys 56, 1 (2023), 1–38

    work page 2023

  3. [3]

    Devanshu Arya, Deepak K Gupta, Stevan Rudinac, and Marcel Worring. 2020. Hypersage: Generalizing inductive representation learning on hypergraphs.arXiv preprint arXiv:2010.04558 (2020)

    arXiv 2020

  4. [4]

    Waiss Azizian and marc lelarge. 2021. Expressive Power of Invariant and Equi- variant Graph Neural Networks. In ICLR. https://openreview.net/forum?id= lxHgXYN4bwl

    work page 2021

  5. [5]

    Song Bai, Feihu Zhang, and Philip HS Torr. 2021. Hypergraph convolution and hypergraph attention. Pattern Recognition 110 (2021), 107637

    2021

  6. [6]

    Peter L Bartlett and Shahar Mendelson. 2001. Rademacher and Gaussian com- plexities: Risk bounds and structural results. In International Conference on Com- putational Learning Theory. Springer, 224–240

    work page 2001

  7. [7]

    Mohammad Mahdi Bejani and Mehdi Ghatee. 2021. A systematic review on overfitting control in shallow and deep neural networks. Artificial Intelligence Review 54, 8 (2021), 6391–6438

    work page 2021

  8. [8]

    Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. 2021. Weisfeiler and lehman go topological: Message passing simplicial networks. In ICML. PMLR, 1026–1037

    work page 2021

Show all 77 references
  1. [9]

    Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Ra- jagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. 2000. Graph structure in the web. Computer networks 33, 1-6 (2000), 309–320

    2000

  2. [10]

    Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. 2022. You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks. In ICLR. https://openreview.net/forum?id=hpBTIv2uy_E

    2022

  3. [11]

    I Chien, Chung-Yi Lin, and I-Hsiang Wang. 2018. Community detection in hypergraphs: Optimal statistical limit and efficient algorithms. In International Conference on Artificial Intelligence and Statistics . PMLR, 871–879

    2018

  4. [12]

    Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. 2021. Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems 34 (2021), 1713–1726

    2021

  5. [13]

    Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross. 2000. An optimal algorithm for Monte Carlo estimation. SIAM Journal on computing 29, 5 (2000), 1484–1496

    2000

  6. [14]

    Alcebiades Dal Col, Fabiano Petronetto, José R de Oliveira Neto, and Juliano B Lima. 2024. Windowed hypergraph Fourier transform and vertex-frequency representation. Signal Processing 223 (2024), 109538

    2024

  7. [15]

    Manh Tuan Do, Se-eun Yoon, Bryan Hooi, and Kijung Shin. 2020. Structural patterns and generative models of real-world hypergraphs. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining . 176–186

    2020

  8. [16]

    Yihe Dong, Will Sawin, and Yoshua Bengio. 2020. Hnhn: Hypergraph networks with hyperedge neurons. arXiv preprint arXiv:2006.12278 (2020)

    2020 arXiv

  9. [17]

    Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. 2019. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems 32 (2019)

    2019

  10. [18]

    Iulia Duta, Giulia Cassarà, Fabrizio Silvestri, and Pietro Liò. 2024. Sheaf hyper- graph networks. Advances in Neural Information Processing Systems 36 (2024)

    2024

  11. [19]

    David Easley, Jon Kleinberg, et al. 2010. Networks, crowds, and markets: Reasoning about a highly connected world . Vol. 1. Cambridge university press Cambridge

    2010

  12. [20]

    Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. 2021. Learning theory can (sometimes) explain generalisation in graph neural networks. NeurIPS 34 (2021), 27043–27056

    2021

  13. [21]

    Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. 2022. How Powerful are K-hop Message Passing Graph Neural Networks. In NeurIPS, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran Associates, Inc., 4776–4790. https://pr...

    2022

  14. [22]

    Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. 2019. Hy- pergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33. 3558–3565

    2019

  15. [23]

    Yoav Freund and Robert E Schapire. 1998. Large margin classification using the perceptron algorithm. In Proceedings of the eleventh annual conference on Computational learning theory. 209–217

    1998

  16. [24]

    Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. 2022. HGNN+: General hy- pergraph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 3 (2022), 3181–3199

    2022

  17. [25]

    Yue Gao, Zizhao Zhang, Haojie Lin, Xibin Zhao, Shaoyi Du, and Changqing Zou

  18. [26]

    Floris Geerts. 2020. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007.12035 (2020)

    2020 arXiv

  19. [27]

    2008.Exploring network structure, dynamics, and function using NetworkX

    Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008.Exploring network structure, dynamics, and function using NetworkX . Technical Report. Los Alamos National Lab.(LANL), Los Alamos, NM (United States)

    2008

  20. [28]

    Jing Huang and Jie Yang. 2021. UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks. In IJCAI-21, Zhi-Hua Zhou (Ed.). International Joint Conferences on Artificial Intelligence Organization, 2563–2569. https: //doi.org/10.24963/ijcai.2021/353 Main Track

    2021 doi

  21. [29]

    Sheng Huang, Mohamed Elhoseiny, Ahmed Elgammal, and Dan Yang. 2015. Learning hypergraph-regularized attribute predictors. In Proceedings of the IEEE conference on computer vision and pattern recognition . 409–417

    2015

  22. [30]

    Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. 2023. Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs. In ICLR. https://openreview.net/forum?id=kDSmxOspsXQ

    2023

  23. [31]

    Stefanie Jegelka. 2022. Theory of graph neural networks: Representation and learning. In The International Congress of Mathematicians

    2022

  24. [32]

    Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R Zhang. 2023. Gen- eralization in graph neural networks: Improved pac-bayesian bounds on graph diffusion. In International Conference on Artificial Intelligence and Statistics. PMLR, 6314–6341

    2023

  25. [33]

    Fotis Kitsios, Eleftheria Mitsopoulou, Eleni Moustaka, and Maria Kamariotou

  26. [34]

    Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Dandapani Sivakumar, Andrew Tompkins, and Eli Upfal. 2000. The Web as a graph. In Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 1–10

    2000

  27. [35]

    John Langford and John Shawe-Taylor. 2002. PAC-Bayes & margins. Advances in neural information processing systems 15 (2002)

    2002

  28. [36]

    Dongjin Lee and Kijung Shin. 2023. I’m me, we’re us, and i’m us: Tri-directional contrastive learning on hypergraphs. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 8456–8464

    2023

  29. [37]

    Geon Lee, Minyoung Choe, and Kijung Shin. 2021. How do hyperedges overlap in real-world hypergraphs?-patterns, measures, and generators. In Proceedings of the web conference 2021 . 3396–3407

    2021

  30. [38]

    Renjie Liao, Raquel Urtasun, and Richard Zemel. 2021. A {PAC}-Bayesian Ap- proach to Generalization Bounds for Graph Neural Networks. In ICLR. https: //openreview.net/forum?id=TR-Nj6nFx42

    2021

  31. [39]

    Biao Liu, Ning Xu, Jiaqi Lv, and Xin Geng. 2023. Revisiting pseudo-label for single- positive multi-label learning. In International Conference on Machine Learning . PMLR, 22249–22265

    2023

  32. [40]

    Tenenbaum, and Leslie Pack Kaelbling

    Zhezheng Luo, Jiayuan Mao, Joshua B. Tenenbaum, and Leslie Pack Kaelbling

  33. [41]

    Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. 2019. Invariant and Equivariant Graph Networks. In ICLR. https://openreview.net/forum?id= Syx72jC9tm

    2019

  34. [42]

    David McAllester. 2003. Simplified PAC-Bayesian margin bounds. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings. Springer, 203–215

    2003

  35. [43]

    In The First Learning on Graphs Conference

    On the Expressiveness and Generalization of Hypergraph Neural Networks. In The First Learning on Graphs Conference . https://openreview.net/forum?id= 4FlyRlNSUh

  36. [44]

    David A McAllester. 1999. PAC-Bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory . 164–170

    1999

  37. [45]

    Christopher Morris, Gaurav Rattan, and Petra Mutzel. 2020. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. NeurIPS 33 (2020), 21824–21840

    2020

  38. [46]

    David A McAllester. 1998. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory . 230–234

    1998

  39. [47]

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, Vol. 33. 4602–4609

    2019

  40. [48]

    Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. 2018. A PAC- Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Net- works. In ICLR

    2018

  41. [50]

    Shirui Pan, Xingquan Zhu, Chengqi Zhang, and S Yu Philip. 2013. Graph stream classification using labeled and unlabeled graphs. In 2013 IEEE 29th International Conference on Data Engineering (ICDE) . IEEE, 398–409

    2013

  42. [51]

    Karelia Pena-Pena, Daniel L Lau, and Gonzalo R Arce. 2023. T-HGSP: Hypergraph signal processing using t-product tensor decompositions. IEEE Transactions on Signal and Information Processing over Networks 9 (2023), 329–345. Generalization Performance of Hypergraph Neural Networ...

    2023

  43. [52]

    Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. 2020. k-hop graph neural networks. Neural Networks 130 (2020), 195–205

    2020

  44. [53]

    Abraham Savitzky and Marcel JE Golay. 1964. Smoothing and differentiation of data by simplified least squares procedures. Analytical chemistry 36, 8 (1964), 1627–1639

    1964

  45. [54]

    Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. 2018. The vapnik– chervonenkis dimension of graph and recursive neural networks.Neural Networks 108 (2018), 248–259

    2018

  46. [55]

    Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. 2022. Ordered subgraph aggregation networks. Advances in Neural Information Processing Systems 35 (2022), 21030–21045

    2022

  47. [56]

    Tan Sun and Junhong Lin. 2024. PAC-Bayesian Adversarially Robust Gener- alization Bounds for Graph Neural Network. arXiv preprint arXiv:2402.04038 (2024)

    2024 arXiv

  48. [57]

    Joel A Tropp. 2012. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics 12 (2012), 389–434

    2012

  49. [58]

    Franco Scarselli, Sweah Liang Yong, Marco Gori, Markus Hagenbuchner, Ah Chung Tsoi, and Marco Maggini. 2005. Graph neural networks for rank- ing web pages. In The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI’05). IEEE, 666–672

    2005

  50. [59]

    Fuli Wang, Karelia Pena-Pena, Wei Qian, and Gonzalo R Arce. 2024. T- HyperGNNs: Hypergraph neural networks via tensor representations. IEEE Transactions on Neural Networks and Learning Systems (2024)

    2024

  51. [60]

    Maolin Wang, Yaoming Zhen, Yu Pan, Yao Zhao, Chenyi Zhuang, Zenglin Xu, Ruocheng Guo, and Xiangyu Zhao. 2024. Tensorized hypergraph neural networks. In Proceedings of the 2024 SIAM International Conference on Data Mining (SDM) . SIAM, 127–135

    2024

  52. [61]

    Vladimir Vapnik. 1968. On the uniform convergence of relative frequencies of events to their probabilities. In Doklady Akademii Nauk USSR . 781–787

    1968

  53. [62]

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Pow- erful are Graph Neural Networks?. In ICLR. https://openreview.net/forum?id= ryGs6iA5Km

    2019

  54. [63]

    Du, Ken ichi Kawarabayashi, and Stefanie Jegelka

    Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. 2020. What Can Neural Networks Reason About?. In ICLR. https://openreview.net/forum?id=rJxbJeHFPS

    2020

  55. [64]

    Hanrui Wu and Michael K Ng. 2022. Hypergraph convolution on nodes- hyperedges network for semi-supervised node classification. ACM Transactions on Knowledge Discovery from Data (TKDD) 16, 4 (2022), 1–19

    2022

  56. [65]

    Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. 2019. Hypergcn: A new method for training graph convolutional networks on hypergraphs. NeurIPS 32 (2019)

    2019

  57. [66]

    Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. InProceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 1365–1374

    2015

  58. [67]

    Ning Xu, Congyu Qiao, Jiaqi Lv, Xin Geng, and Min-Ling Zhang. 2022. One positive label is sufficient: Single-positive multi-label learning with label enhance- ment. Advances in Neural Information Processing Systems 35 (2022), 21765–21776

    2022

  59. [68]

    Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. 2017. Deep sets. Advances in neural information processing systems 30 (2017)

    2017

  60. [69]

    Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. 2024. Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness. In The Twelfth International Conference on Learning Representations . https: //openreview.net/forum?id=HSKaGOi7Ar

    2024

  61. [70]

    Ze-Bang Yu and Min-Ling Zhang. 2021. Multi-label classification with label- specific feature generation: A wrapped approach. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 9 (2021), 5199–5210

    2021

  62. [71]

    Ruochi Zhang, Yuesong Zou, and Jian Ma. 2020. Hyper-SAGNN: a self-attention based graph neural network for hypergraphs. In ICLR. https://openreview.net/ forum?id=ryeHuJBtPH

    2020

  63. [72]

    Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. 2006. Learning with hypergraphs: Clustering, classification, and embedding. NeurIPS 19 (2006). Conference’17, July 2017, Washington, DC, USA Yifan Wang, Gonzalo R. Arce, and Guangmo Tong Appendix A Notations and Definitions...

    2006

  64. [73]

    Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. 2018. Beyond link prediction: Predicting hyperlinks in adjacency space. In AAAI, Vol. 32

    2018

  65. [76]

    Altogether, we separate the proof into three parts for three ranges of𝛽

    However, when dealing with𝛽 values that fall within the third case, it is necessary to determine the specific values of 𝑃 and𝑄 that satisfy the perturbation condition for each𝛽. Altogether, we separate the proof into three parts for three ranges of𝛽. First case. We start from ...

    2017

  66. [77]

    Since we have the upper bound, the above statement will always be satisfied

    Therefore,LD,0(𝑓w) is always bounded by 1. Since we have the upper bound, the above statement will always be satisfied. As a result, we should only consider𝛽 in the above range, see Equation 26. We have an assumption that|𝛽− ˜𝛽|≤ 1 𝐿4𝛽. Thus, we use a cover of size(√𝑚− 1)𝐿4 wi...

    2017

  67. [78]

    of one graph type (i.e., ER or SBM) and one model (i.e., T-MPHN, and HGNN+) with trained ((a), (b), (e), and (f)) and random parameters ((c), (d), (g), and (h)), where each figure plots the results of twelve datasets; the figures, from left to right, show the results with 2, 4...

    2017

  68. [2020]

    IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 5 (2020), 2548–2566

    Hypergraph learning: Methods and practices. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 5 (2020), 2548–2566

    2020

  69. [2022]

    Interna- tional Journal of Information Management Data Insights 2, 1 (2022), 100056

    User-Generated Content behavior and digital tourism services: A SEM- neural network model for information trust in social networking sites. Interna- tional Journal of Information Management Data Insights 2, 1 (2022), 100056

    2022

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.