PaperlayerView exact revision on arXiv

Source-linked AI summary

Do Higher-Order Models Win for Higher-Order Reasons? Rethinking Performance Gains in Hypergraph Learning

Fanchen Bu, Fan Li, Geon Lee, Sunwoo Kim, Xiaoyang Wang, Renaud Lambiotte, Kijung Shin

arXiv:2610.07981v1cs.LGcs.SI

TL;DR

Higher-order models often outperform lower-order baselines, but conventional comparisons do not establish that higher-order information explains those advantages. The paper perturbs higher-order information while preserving pairwise information and finds that many advantages persist, while simple lower-order additions narrow some remaining gaps.

  • Problem

    Conventional performance comparisons do not establish whether higher-order information explains higher-order models’ advantages over lower-order baselines.

    Source: §1 · pp. 1–2

  • Method

    The paper perturbs higher-order information while preserving the weighted pairwise representation, then compares higher- and lower-order model performance across the two views.

    Source: §4 · p. 5, §7 · p. 13

  • Results

    Across 25 benchmarks spanning three tasks, many higher-order advantages largely remain after perturbation, while simple lower-order additions are overall helpful and reduce some remaining gaps.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The findings call for separating performance advantages from their attribution and assessing whether benchmarks test the higher-order capability they are intended to measure.

    Source: §7 · p. 13

    Attribution statements depend on preserving the multiplicity-weighted clique expansion; other perturbations preserving the same information remain a natural extension.

    Source: §8 · p. 13

Abstract

from arXiv · show

Higher-order models (e.g., hypergraph neural networks) often outperform lower-order baselines on hypergraph learning benchmarks, and their advantages are commonly attributed to their ability to exploit higher-order information. However, better performance alone does not establish this explanation. We therefore ask: Do higher-order models win for higher-order reasons? To investigate this question, we introduce a controlled performance-attribution framework that perturbs higher-order information while preserving the lower-order, i.e., pairwise, information. Across 25 commonly used hypergraph learning benchmarks spanning three tasks, we frequently observe an intriguing pattern: higher-order models originally outperform lower-order baselines, yet retain most of their advantage after perturbation. This suggests that much of the observed advantage remains achievable without the higher-order information. We then investigate potential lower-order explanations for these remaining gaps. We find that simple additions to a lower-order baseline, e.g., richer pairwise weighting, more steps of pairwise feature propagation, and normalization, reduce the remaining performance gaps, supporting lower-order explanations for part of the observed advantage. Our analysis calls for the hypergraph learning community to rethink performance attribution by distinguishing performance gains from their explanations, adopt stronger lower-order baselines, and use suitable benchmarks that better test the value of higher-order information.

1 Introduction

Higher-order models are designed to exploit group relations, but better benchmark performance alone does not show that higher-order information explains their advantage. The paper tests this attribution with an intervention that preserves pairwise information, finding that advantages often persist and can be partly narrowed by strengthening lower-order baselines.

1 Introduction

  • The intervention compares original and perturbed data views, preserving lower-order information while changing higher-order information.If the advantage depends substantially on higher-order information, the authors expect it to shrink under perturbation.Source: §1 · p. 2
  • Synthetic controls show a vanishing advantage when higher-order information is essential and equal performance when it is redundant.These cases establish expected responses for the intervention.Source: §1 · p. 2
  • On many commonly used real-world benchmarks, higher-order models retain most of their performance advantage after candidate higher-order information is perturbed.The paper notes that much of this advantage can therefore be achieved without that information.Source: §1 · p. 3
  • Richer pairwise weighting, more pairwise propagation steps, and normalization substantially reduce several retained gaps; these additions are overall helpful without further tuning.The findings support lower-order explanations for part of the observed advantage.Source: §1 · p. 3
  • Across 25 benchmarks spanning three tasks, many higher-order model advantages largely remain after higher-order information is perturbed.This challenges the interpretation that higher-order information explains the observed wins.Source: §1 · p. 3
  • The findings motivate distinguishing performance gains from their explanations and testing whether benchmarks measure the capability they are intended to assess.The authors also call for investigating what sustains remaining gaps.Source: §1 · p. 3

2 Related Work

Prior hypergraph-learning comparisons establish predictive differences, but do not by themselves identify which information accounts for them. This paper focuses on whether higher-order information explains higher-order models’ advantages, rather than on structural recovery or dynamical reducibility.

2 Related Work

  • Comparisons of HNNs with pairwise-graph and feature-only baselines establish predictive differences but do not identify the information responsible.The paper frames its contribution as an attribution question about the source of HNN performance.Source: §2 · pp. 3–4
  • Prior studies vary interaction order to examine higher-order information’s predictive value, while this work asks whether HNN advantages depend on that information.The cited approaches progressively add projections or reduce higher-order interactions.Source: §2 · pp. 3–4
  • Work on structural recovery and dynamical reducibility differs from this paper’s focus on the predictive role of higher-order information in HNN performance.The related work addresses information loss, reconstruction ambiguity, and when mechanisms or dynamics reduce to pairwise ones.Source: §2 · p. 4

3 The Performance-Attribution Question

The section defines higher- and lower-order information and models, then asks how much of a higher-order model’s benchmark advantage is attributable to information beyond the weighted clique expansion.

3.1 Preliminaries

  • A hypergraph is represented by nodes, unique hyperedges with multiplicity weights, and optional node features; its weighted clique expansion may lose information because distinct hypergraphs can share it.A benchmark is a dataset paired with a prediction task, so the same dataset under different tasks defines different benchmarks.Source: §3.1 · p. 4

3.2 Higher- and lower-order information and models

  • Lower-order information is the weighted clique expansion, while higher-order information distinguishes hypergraphs sharing that expansion.A model is higher-order if its parameterized functions can distinguish such hypergraphs; it is lower-order if they are determined by the expansion.Source: §3.2 · p. 4
  • The lower-order definition is conditional on pair co-occurrence weights, and a higher-order model family’s capacity does not establish that a fitted instance uses that information.Architecture alone does not determine information access; a graph neural network with hypergraph-derived encodings can use higher-order information.Source: §3.2 · pp. 4–5

3.3 The performance-attribution question

  • The performance-attribution question asks how much of a higher-order model’s advantage over a lower-order model is attributable to higher-order information.A model may distinguish hypergraphs with the same expansion while its benchmark advantage arises from other differences between the models.Source: §3.3 · p. 5

4 A Controlled Performance-Attribution Framework

The framework changes higher-order information while preserving lower-order information, then compares model performance across original and perturbed views. It uses the resulting gap changes to assess attribution and partial perturbations as additional diagnostics.

4 A Controlled Performance-Attribution Framework

  • The intervention creates original and fully perturbed views, replacing non-pairwise hyperedges by weighted pairwise expansions while preserving lower-order information and leaving the task unchanged.For hypergraph classification, the transformation is applied to each hypergraph in the dataset.Source: §4 · p. 5
  • If higher-order information is a major source of advantage, the authors expect the higher-order model’s advantage to shrink on the fully perturbed view.The perturbation replaces higher-order groupings with weighted pairwise connections.Source: §4 · p. 5
  • The framework compares original and perturbed performance gaps, with the lower-order model’s performance unchanged because it receives the same information in both views.A positive ∆attr = ∆(0) − ∆(1) indicates intervention sensitivity, while a positive ∆(1) means an advantage remains achievable without the perturbed information.Source: §4 · p. 5
  • Partial perturbations expand a proportion of hyperedges larger than two at each level, averaging test performance over multiple sampled views.Intermediate levels do not define unique views, so multiple subsets are sampled at each level.Source: §4 · p. 5

5 Empirical Analysis on Real-World Benchmarks

The empirical analysis tests performance attribution on synthetic controls and 25 real-world dataset–task benchmarks, then examines whether stronger lower-order processing can explain gaps that survive perturbation. Most material real-world advantages largely persist, while simple lower-order additions narrow some remaining gaps with effects that vary across tasks and benchmarks.

5.1 Experimental setup

  • The evaluation covers 25 real-world dataset–task benchmarks across node classification, hyperedge prediction, and hypergraph classification, selecting models by original-view mean validation performance.The study evaluates 17 higher-order models alongside feature-only and pairwise lower-order models, using accuracy for node and hypergraph classification and AP for hyperedge prediction in the main text.Source: §5.1 · p. 6

5.2 Synthetic calibration: Two controlled cases

  • In the synthetic essential-information case, perturbation removes the higher-order model’s 50-point advantage; in the redundant case, both selected models maintain perfect performance.The controls are constructed so motif templates have identical weighted clique expansions in the essential case, while pairwise information distinguishes templates in the redundant case.Source: §5.2 · pp. 6–7

5.3 Real-world results: Advantages largely survive perturbation

  • 14 of 18 benchmarks with material original gaps retain at least 80% of the gap after perturbation, with a median retention of 96.7%.On Trivago, the gap falls from 44.4 to 42.8 accuracy points; on Pokec, the advantage remains essentially unchanged at 23.5 AP points.Source: §5.3 · p. 7, Figure 2 · p. 8
  • Largely retained gaps occur on 8 of 10 node-classification benchmarks, all four hyperedge-prediction benchmarks, and 2 of 4 hypergraph-classification benchmarks.The additions’ benefits are not uniform: across all six hypergraph-classification benchmarks, O+D+L reduces accuracy on five, with a mean change of −0.95 points.Source: §5.3 · p. 9, §5.4 · p. 11

5.4 Investigating lower-order explanations for retained gaps

  • Three case studies show retained gaps can shrink through richer pairwise operators, longer-range input diffusion with LayerNorm, and matching cold-node handling and activation choices.The case studies examine node classification on Walmart and Trivago and hyperedge prediction on Pokec.Source: §5.4 · pp. 9–11, Figure 3 · p. 10
  • O+D+L reduces mean remaining-gap ratios to 0.44 for node classification, 0.78 for hyperedge prediction with the identity cold-node policy, and 0.66 for hypergraph classification.Across 13 node-classification benchmarks, O and O+D+L improve accuracy by averages of 2.96 and 3.69 points, respectively; structural self weights and associated normalization account for much of the improvement.Source: §5.4 · p. 11

6 Broader Implications for the Hypergraph-Learning Community

The paper argues that model-performance comparisons alone do not identify which information source accounts for an advantage. It recommends controlled attribution protocols, stronger lower-order comparisons, and benchmarks designed to test information requirements.

Evaluation protocols

  • Complement original-view comparisons with controlled interventions that declare and verify preserved lower-order information and report both removed and remaining gap portions.A leaderboard can establish which model performs better, but not the source of that advantage.Source: §6 · p. 12

Evaluation baselines

  • Include competitive feature-only and richer pairwise baselines, with validation-based tuning opportunities comparable to those given to higher-order models.The paper notes that weak lower-order comparators cannot establish that lower-order information is insufficient.Source: §6 · p. 12

Evaluation benchmarks

  • Assess higher-order necessity at the dataset–task level and document hyperedge and target construction so readers can evaluate plausible feature-only or pairwise explanations.Benchmarks designed around specific information requirements can make the distinction more testable; synthetic controls can include both necessary and sufficient lower-order cases.Source: §6 · p. 12

7 Conclusion

The paper separates higher-order models’ performance advantages from claims about why they occur. Its results motivate attribution-aware evaluation, stronger lower-order comparators, and benchmarks designed to test specific information requirements.

7 Conclusion

  • Across real-world benchmarks, most of higher-order models’ original advantage often survives perturbing higher-order information, while simple lower-order additions improve baseline performance.The authors recommend controlled interventions, stronger lower-order comparators, and benchmarks designed to distinguish the capabilities they test.Source: §7 · p. 13

8 Limitations and Future Directions

The limitations identify boundaries in what the intervention establishes and propose extensions to the intervention, model analysis, and benchmark design. Supplementary sections detail prior-work interpretations, perturbation construction, benchmarks, splits, and evaluated model families.

8 Limitations and Future Directions

  • Attribution depends on preserving the multiplicity-weighted clique expansion; matching performance does not establish how the original higher-order model used information, and real-world information requirements are generally unknown.The authors suggest comparing alternative interventions, changing architectural components under control, and developing semi-synthetic benchmarks with known higher-order requirements.Source: §8 · p. 13

A Details of Quotes from Prior Work (Supplementing Section 1)

  • Prior work has interpreted improved comparisons as evidence that hypergraph structure or non-pairwise interactions benefit performance, including Feng et al. (2019), Bai et al. (2021), Li et al. (2026), and Xu et al. (2023).Source: A Details of Quotes from Prior Work… · p. 18

B Details of Partial Perturbations (Supplementing Section 4)

  • The partial perturbation samples weighted hyperedge instances for clique expansion, leaving pairwise instances unselected and preserving the weighted pairwise co-occurrences.Permutations define nested selections as perturbation increases; at the full endpoint, the non-singleton structure is weighted pairs.Source: B Details of Partial Perturbations… · p. 18

C.1 Benchmarks: Datasets and tasks

  • The benchmark inventory contains 25 task benchmarks—13 for node classification, six for hyperedge prediction, and six for hypergraph classification—drawn from 19 distinct datasets.Source: §C.1 · p. 19

C.1.1 Datasets for node classification and hyperedge prediction

  • The 13 node-classification datasets also supply six hyperedge-prediction benchmarks; those six are Cora, Pubmed, Cora-CA, DBLP-CA, Actor, and Pokec.Source: §C.1.1 · p. 19

C.1.2 Datasets for hypergraph classification

  • Hypergraph classification uses six datasets, each comprising a collection of hypergraphs with each whole hypergraph serving as one prediction instance.Source: §C.1.2 · p. 20

C.1.3 Other details

  • Preprocessing and splits vary by task, while the intervention preserves features, labels, targets, graph order, and split membership; for hyperedge prediction, only the support graph changes.Node classification uses 50/25/25 splits, hyperedge prediction 60/20/20, and hypergraph classification 80/10/10.Source: §C.1.3 · pp. 20–21

C.2 Models

  • The evaluated models include spectral, spatial, and tensor-based hypergraph neural networks, alongside lower-order baselines including MLP, CEGCN, and CEGAT.Source: §C.2 · p. 21

C.3 Implementations and hyperparameter tuning

This appendix describes benchmark model selection and configurations, then constructs synthetic cases where higher-order information is either essential or redundant.

C.3 Implementations and hyperparameter tuning

  • The benchmark comparisons use official DHG-Bench implementations and released YAML configurations, with a selected model pair for each primary comparison.Table 1 covers 25 comparisons across node classification, hyperedge prediction, and hypergraph classification; the Yelp pair has a resource exception.Source: §C.3 · p. 21, Table 1 · p. 22
  • Configuration tables list benchmarks as rows and varying YAML fields as columns, with shared settings listed below each table.The symbols L, E, H, M, T, p, η, and λ denote specified layer, hidden-size, epoch, dropout, learning-rate, and weight-decay fields.Source: §C.3 · pp. 21–22

D.1 Construction

  • Each synthetic hypergraph contains 21 disjoint six-node motifs, and its label is determined by the majority motif template.Node features identify within-motif roles but encode neither the template nor the hypergraph label.Source: §D.1 · pp. 36–37
  • The two motif templates have identical weighted clique expansions, so their pairwise structure alone does not distinguish them.Every unordered role pair occurs with the same multiplicity in both templates, and identical pairwise edges add no template or label signal.Source: §D.1 · p. 37
  • For the redundant-information case, template-specific pairwise tags distinguish the templates and reveal the majority label using lower-order information alone.T0 receives tag {1, 4} and T1 receives tag {2, 3}, each with weight four.Source: §D.1 · p. 37

D.2 Evaluation

The evaluation selects fixed model representatives for each family and tests them across synthetic datasets, seeds, and perturbation levels.

D.2 Evaluation

  • The evaluation includes 15 higher-order and three lower-order models that support hypergraph classification.Source: §D.2 · p. 37
  • For each case, the best model in each family is selected by original-view validation accuracy, with Macro-F1 breaking ties, and its identity and hyperparameters are fixed.Source: §D.2 · p. 37
  • Final test performance averages nine runs per model and view across three generated datasets and three training seeds, at r values 0, 0.25, 0.50, 0.75, and 1.Each dataset has balanced 300/100/100 train, validation, and test hypergraphs.Source: §D.2 · p. 37

E.1 Detailed benchmark-wise results

Across benchmarks with material original advantages, most of the gap remains after full perturbation; the section reports gap and retention results for all 25 comparisons.

E.1 Detailed benchmark-wise results

  • The 80% boundary is descriptive rather than a significance threshold, and retention can exceed 100%, be negative, or be N/A for nonpositive original gaps.Source: §E.1 · p. 37, Table 23 · p. 39
  • Table 22 reports original, intermediate, and fully perturbed gaps for all 25 benchmarks, with gaps defined as higher-order performance minus the fixed lower-order comparator.The metric is accuracy for node and hypergraph classification and AP for hyperedge prediction.Source: §E.1 · p. 37, Table 22 · p. 38
  • 14 of 18 comparisons with an original gap of at least one point retain at least 80%, and median retention is 96.7%.Retention is the fully perturbed gap divided by the original gap; 12 comparisons retain at least 90% and 10 at least 95%.Source: §E.1 · p. 37, Table 23 · p. 39

E.2 Secondary-metric results

The appendix checks secondary-metric gap retention, audits whether lower-order baselines are invariant across views, and extends endpoint and perturbation-level results across models. The results show heterogeneous responses, including stable or improved performance after perturbation.

E.3 Empirical check of lower-order baseline invariance

  • Across 75 comparisons, lower-order inputs were identical; the same trained model met output tolerances in 150/150 comparisons, while retraining changed mean primary scores by at most 0.783 points.The largest same-model primary-score change was 0.00727 points.Source: §E.3 · pp. 39–40, Table 25 · p. 41, Table 26 · p. 41

E.2 Secondary-metric results

  • Figure 6 compares original and fully perturbed gaps under AUROC for hyperedge prediction and Macro-F1 for hypergraph classification, flagging gaps retaining at least 80%.Retention is reported only for original gaps of at least one point; the diagonal marks unchanged gaps.Source: §E.2 · p. 39, Figure 6 · p. 40, Table 24 · p. 40

E.4 Node classification

  • Of 36 complete top-three node-classification trajectories, 28 changed by less than one accuracy point and eight decreased by at least one point.The trajectories retain the top three higher-order models by original-view validation performance.Source: §E.4 · p. 42, Figure 9 · p. 44, Figure 10 · p. 45

E.5 Hyperedge prediction

  • Among 100 available hyperedge-prediction cells, 29 decreased by at least one AP point, 35 improved by at least one point, and 36 changed by less than one point.Across 17 complete top-three trajectories, seven decreased by at least one AP point, eight changed by less than one point, and two improved; Cora-CA and Pokec show within-benchmark disagreement.Source: §E.5 · p. 46, Figure 11 · p. 46, Figure 12 · p. 47

E.6 Hypergraph classification

  • Among 89 available hypergraph-classification cells, 28 decreased by at least one accuracy point, 19 improved by at least one point, and 42 changed by less than one point.Across 18 complete top-three trajectories, eight decreased by at least one point, nine changed by less than one point, and one improved; Steam-Player’s three selected models decreased, while RHG-3’s remained stable.Source: §E.6 · p. 50, Figure 15 · p. 50, Figure 16 · p. 51

F.1 Detailed benchmark-wise analysis

The detailed analyses test whether pairwise weighting, propagation, normalization, feature processing, and architecture account for performance gaps that remain after higher-order information is perturbed. Several lower-order controls recover or reduce those gaps, while endpoint HNNs retain architectural differences beyond ordinary graph convolution.

Walmart: current operator and diffusion controls

  • On Walmart, CEGCN accuracy rises from 67.98 to 68.15 to 74.56 as its operator adds pair counts and structural self weights; selected input diffusion reaches 76.32.The controls keep the CEGCN architecture, inputs, and training settings fixed across the operator ladder.Source: §F.1 · p. 54

Trivago: fixed-architecture diffusion sweeps

  • On Trivago, binary-input diffusion reaches 77.64 ± 0.25 accuracy at k = 64, versus 47.75 ± 0.52 with no extra steps; LayerNorm adds 13.55 and 12.60 points at k = 64 and 256.The selected weighted and binary sweeps differ by 0.68 points while changing both operator and depth.Source: §F.1 · p. 54, Table 28 · p. 55

Pokec: matched policy and activation controls

  • On Pokec, matching HGNN’s zero-message cold-node policy raises CEGCN AP from 59.71 to 78.22; replacing ReLU with ELU adds another 1.92 points.The query nodes, offsets, labels, encoder, and scorer settings are held fixed.Source: §F.1 · pp. 54–55, Table 29 · p. 55

Other hyperedge-prediction cases

  • On Actor, TFHNN’s unchanged 10.15-point advantage uses node features without incidence-based message passing; pairwise controls match fully perturbed UniGCNII on Cora-CA and HGNN on Pokec.These cases show retained hyperedge-prediction gaps can be matched by feature-only or pairwise mechanisms.Source: §F.1 · p. 55

Additional node-classification analyses

  • Node-classification controls associate Cora-CA gains with pairwise weighting and design choices, while propagation ablations on DBLP-CA, Cora, and ModelNet40 reduce accuracy.The authors caution that similar propagation losses and remaining gaps do not establish that propagation alone explains those gaps.Source: §F.1 · p. 55

Pairwise controls for hypergraph classification

  • On RHG-10, Pair-Multiplicity exceeds CEGAT by 2.25 points, more than HNHN’s 1.72-point remaining advantage; on RHG-3, Pair-SAGE-Mean recovers about 78% of HNHN’s remaining advantage.Both controls use weighted clique-expansion information and were outside the original model-selection pool.Source: §F.1 · p. 55

Pubmed and Ratings: feature processing versus propagation

  • On Pubmed and Ratings, LEGCN’s self-only control retains most of its advantage over MLP, while restoring incidence propagation adds only 0.09 and 0.21 points, respectively.The self-only gains are 1.29 points on Pubmed and 1.22 on Ratings.Source: §F.1 · p. 56

What the 17 HNNs compute at the fully perturbed endpoint

  • Fully perturbed endpoints retain weighted pairwise connections and singleton incidences, but HNNs also differ in normalization, nonlinear messages, representations, restart paths, and readout.Consequently, preserving pair counts and singleton multiplicities does not make the architectures or their performance interchangeable.Source: §F.1 · p. 56, Table 30 · p. 56

F.2 O/D/L additions shared across datasets and primary-metric results

The study evaluates shared lower-order additions across benchmarks and reports primary-metric scores and paired changes. It separates pair-multiplicity and self-weight operator changes, residual diffusion, and classifier normalization.

F.2 O/D/L additions shared across datasets and primary-metric results

  • The O/D/L recipes are evaluated across 13 node-classification, six hypergraph-classification, and six hyperedge-prediction datasets without further hyperparameter tuning.Hyperedge prediction uses both identity and zero-message cold-node policies.Source: §F.2 · pp. 58–59
  • O1 replaces binary adjacency with pair multiplicities, while O2 adds structural self weights, including singleton contributions, after O1.Because the changes are sequential, O2 also changes neighbor-message normalization.Source: §F.2 · p. 58
  • The matched O comparison trains binary CEGCN, +O1, and +O1+O2 separately on all 25 benchmarks, holding architecture, activations, heads, splits, and training settings matched.Diffusion and normalization are disabled in this decomposition.Source: §F.2 · p. 58
  • D combines original features with features propagated for different numbers of steps before any trainable transformation; L inserts LayerNorm after activation and before dropout.L uses ϵ = 10^-5 with learned affine scale and bias; O and D add no trainable parameters.Source: §F.2 · pp. 58–59
  • Tables 31–42 report primary-metric scores and changes by task and cold-node policy, while Tables 44–53 report secondary-metric results.The task-specific primary metrics are accuracy for node and hypergraph classification and AP for hyperedge prediction.Source: §F.2 · p. 59, Table 31 · p. 60, Table 32 · p. 60
Loading 2610.07981v1…