SPHINX: Structural Prediction using Hypergraph Inference Network
Authors: Iulia Duta
Pietro Lio
Venue: ICML 2025 poster (2025)
Keywords: hypergraph prediction
hypergraph representation learning
Primary area: deep_learning->graph_neural_networks
TL;DR: Learning to predict hypergraph structure in an unsupervised way,  only from the downstream task signal.

Abstract: The importance of higher-order relations is widely recognized in numerous real-world systems. However, annotating them is a tedious and sometimes even impossible task. Consequently, current approaches for data modelling either ignore the higher-order interactions altogether or simplify them into pairwise connections. 
To facilitate higher-order processing, even when a hypergraph structure is not available, we introduce SPHINX, a model that learns to infer a latent hypergraph structure in an unsupervised way, solely from the final task-dependent signal. To ensure broad applicability, we design the model to be end-to-end differentiable, capable of generating a discrete hypergraph structure compatible with any modern hypergraph networks, and easily optimizable without requiring additional regularization losses.
Through extensive ablation studies and experiments conducted on four challenging datasets, we demonstrate that our model is capable of inferring suitable latent hypergraphs in both transductive and inductive tasks.  Moreover, the inferred latent hypergraphs are interpretable and contribute to enhancing the final performance, outperforming existing methods for hypergraph prediction.

SPHINX: Structural Prediction using Hypergraph Inference Network
Iulia Duta
Pietro Liò
Abstract
learning community (Leskovec et al., 2005; Hu et al., 2020), the availability of hypergraph datasets much more lim- ited. Recent work (Wang & Kleinberg, 2024) highlights two potential causes for the lack of higher-order data. On one hand, current technology used for collecting information is mostly designed optimised to detect pairwise interactions. Furthermore, even in the exceptional case when the data is gathered in a higher-order format, the published version is often released in a reduced, pairwise form.
The importance of higher-order relations widely recognized in numerous real-world systems. How- ever, annotating them is a tedious and sometimes even impossible task. Consequently, current ap- proaches for data modelling either ignore the higher-order interactions altogether or simplify them into pairwise connections. To facilitate higher-order processing, even when a hypergraph structure is not available, we introduce SPHINX, model that learns infer latent hypergraph structure in unsupervised way, solely from the final task-dependent signal. To ensure broad ap- plicability, we design the model to be end-to-end differentiable, capable of generating a discrete hypergraph structure compatible with any mod- em hypergraph networks, and easily optimizable without requiring additional regularization losses. Through extensive ablation studies and experi- ments conducted on four challenging datasets, we demonstrate that our model is capable of inferring suitable latent hypergraphs in both transductive and inductive tasks. Moreover, the inferred latent hypergraphs are interpretable and contribute to enhancing the final performance, outperforming existing methods for hypergraph prediction.
Therefore, to preserve the higher-order information, it is erucial to develop methods for learning the hypergraph structure in an unsupervised way, only from point-wise observations. To create a general, widely-applicable model, we identify a set of key desiderata. 1) The model should applicable to a broad type of tasks. This is a challenge for most existing hypergraph predictors, which optimize single hypergraph, limiting their usefulness transduc- tive setups. 2) The model should be compatible with any hypergraph processing architecture. This requires our inference model to be fully differentiable while produc- ing a sparse and discrete hypergraph structure. Existing methods often fall short, as they are either only partially dif- ferentiable (relying on techniques such as top-k selection or thresholding to enforce sparsity) or restricted to generating only weighted hypergraphs. 3) A powerful model should be easy to optimise. This is limitation exhibited by most of the modern architectures for which predicting a suitable hypergraph requires various types of regularization losses.
1. Introduction
Motivated by these, we introduce Structural Prediction us- ing Hypergraph Inference Network (SPHINX), model for unsupervised latent hypergraph inference, that can be used in conjunction with any recent models designed for hyper- graph processing. SPHINX models the hyperedge discovery as a clustering problem, adapting a soft clustering algorithm to sequentially identify subsets of highly correlated nodes, corresponding to each hyperedge. To produce a discrete hypergraph structure, we take advantage of the recent devel- opment in differentiable k-subset sampling (Ahmed et al., 2023; Minervini al., 2023), obtaining more effective training procedure, that eliminates the necessity for heavy regularisation. While classical selection methods such as Gumbel-Softmax (Jang et al., 2017) fail to control the spar- sity of the hypergraph, our constrained k-subset sampling produces a more accurate latent structure.
Graphs are universally recognized as the standard repre- sentation for relational data. However, their capabilities restricted to modelling pairwise connections. Emerg- ing research shows that real-world applications including neuroscience (Guo et al., 2021), chemistry (Jost & Mulas, 2018), biology (Viñas et al., 2022), often exhibit group in- teractions, involving more than two elements. This leads to the development of a new field dedicated to representing higher-order relations, in the form of hypergraphs. How- ever, while graph datasets are widespread in the machine
'Department of Computer Science, University of Cambridge. Correspondence to: lulia Duta sid366@cam.ac...
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

SPHINXX Structural Prediction using Hypergraph Inference Network
Experiments on both inductive and transductive datasets show that our inferred hypergraph surpasses existing graph and hypergraph-based models on the final downstream task. Moreover, our synthetic experiments reveal that the inferred structure correlates well with the ground-truth connectivity that guides the dynamical process, outperforming other hy- pergraph predictors. The resulting model is general, easy to optimise, which makes it an excellent candidate for mod- elling higher-order relations, even in the absence of an notated connectivity.
et al., 2022) incorporates causal relations into the framework. For temporal data, these models infer single structure for the entire timeseries. dNRI (Graber & Schwing, 2020) im- proves on that respect, by modifying the graph structure at each timestep.
Hypergraph Networks. Several data structures for higher- order modelling were proposed, including simplicial com- plexes (Torres & Bianconi, 2020), cell complexes (Lun- dell & Weingram, 1969), and more generally, hyper- graphs (Banerjee, 2021). To model hypergraphs, several deep learning methods have recently emerged. Hypergraph Neural Networks (Feng et al., 2019) applies GNNs on top of a weighted clique expansion. This could be seen as a two-stage message passing scheme, sending messages from nodes to hyperedges and viceversa. UniGNN (Huang & Yang, 2021) and AllDeepSets (Chien et al., 2022) introduce more general framework in which the two stages can be implemented as any permutationninvarian function such as DeepSets (Zaheer et al., 2017) or Transformers ( (Vaswani et al., 2017). Further proposed extensions include the in- tegration of attention mechanisms (Bai et al., 2021; Zhang et al., 2022: Georgiev et al., 2022), or attaching additional geometric structure to the hypergraph, through the incorpo- ration of cellular sheaves (Duta et al., 2023). While these methods can be seen as learning to modify the structure, they require an initial hypergraph structure.
Our main contributions are summarised as follows:
1. We propose novel method for explicit hypergraph inference, that uses sequential predictor to identify subsets of highly-related nodes and a k-subset sam- pling to produce an explicit hypergraph structure, that can be plugged into any hypergraph neural network.
2. The model performs unsupervised hypergraph dis- covery, by using supervision only from the weak node- level signal. We empirically show that the predicted hypergraph correlates well with the true higher-order structure, even if the model was not optimised for it.
3. The latent hypergraph enforces an inductive bias for capturing higher-order correlations, even in the ab- sence of the real structure, which proved be benefi- cial for downstream tasks such as trajectory predic- tion (inductive) or node classification (transductive). Having an explicit structure allows us to visualise the discovered hypergraph, adding a new layer of inter- pretability to the model.
Structural inference on hypergraphs. Providing the hy- pergraph structure to the model requires measuring higher- order correlations, which often implies a highly difficult and expensive annotation process. This leads to the necessity of inferring the latent hypergraph structure directly from data. However, when moving from the graph realm to the hyper- graph domain, the set of potential edge candidates abruptly increases from quadratic to exponential. This makes the problem of inferring the latent hypergraph structure signif- icantly more challenging. Classical attempts of achieving this include methods based on Bayesian inference (Young et al., 2021) or statistical approaches that filter against a null model for hypergraphs (Musciotto et al., 2021).
2. Related work
Structural inference on graphs. Modelling relational data using Graph Neural Networks (GNNs) (Kipf & Welling, 2017; Veličković et al., 2018) proves to be beneficial in several real-world domains (Bica & van der Schaar, 2022: Sanchez-Gonzalez et al., 2020; Lam et al., 2023). Most of the current graph methods assume that the graph connectiv- ity is known. However, providing the relational structure is highly challenging task, that, when possible to compute, requires either expensive tools, or advanced domain knowl- edge. These limitations led to the development of a new machine learning field dedicated to learning to infer struc- ture from data in an unsupervised way. Neural Relational Inference (Fetaya et al., 2018) one of the pioneering works inferring an adjacency matrix from point-wise observations. The model consists of an encoder that learns to predict distribution over the potential relationships and a GNN de- coder that receives a sampled graph structure and learns to predict the future trajectory. fNRI ( (Webb et al., 2019) extends this work by inferring a factorised latent space, ca- pable of encoding multiple relational types, while (Löwe
While relational inference for graphs is an established field in deep learning, it remains largely underexplored in the hypergraph domain. The common approach is to either extract hyperedges using k-NN (Huang al., 2009), clus- tering (Jiang et al., 2019; Gao al., 2013) or iteratively optimising regularisation constraints (Liu et al., 2016). How- ever, the resulting hypergraph is static, independent of the targeted downstream task. More recent several methods (Yu et al., 2012: Wang et al., 2024; Cai et al., 2022; Zhang et al., 2018: Gao et al., 2020) improve on the kNN approach by learning a task-guided mask modify the initial structure. While producing dynamic hypergraphs, optimising the mask restrict the method to only work in the transductive setup, in
2

---

SPHIINX: Structural Prediction using Hypergraph Inference Network
SPHINX pipeline
Hypergraph predictor
K-sampling
Hypergraph processing
diomma I-gubset sarping
CIL
gradlent
diocets kroubset
gradlont
Figure 1: SPHINX architecture, designed to capture higher-order interactions without having access to the ground-truth hypergraph structure. The model consists of three stages: A) The hypergraph predictor infers a probabilistic latent hypergraph structure, by using sequential clustering algorithm produce global, history-aware hyperedges. At each timestep, the node features are enriched with the information about the already predicted hyperedges and the resulting cluster represent the hyperedge membership. B) A k-subset sampling algorithm is applied to transform each probability distribution into discrete incidence relations, while maintaining the end-to-end differentiability of the framework. The k-nodes constraint ensures a more stable optimisation process, beneficial for the final performance. C) The predicted hypergraph structure can be used in any standard hypergraph neural network order to produce higher-order representations.
which a single hypergraph produced for the entire dataset. Very few methods in the literature are general enough allow learning hypergraph structure in both inductive and transductive tasks.' GroupNet (Xu et al., 2022) and DynGroupNet (Xu et al., 2024) use the correlation matrix to extract submatrices of high connectivity, EvolveHyper- graph (Li et al., 2022) predicts a soft connectivity for each node, relying on Gumbel-Softmax and regularisation tricks to produce a sparse, discrete structure, while TDHNN (Zhou al., 2023) uses differentiable clustering to produce soft incidence, followed by top-k selection to impose sparsity. For more in-depth analysis of the existing dynamic hyper- graph predictors, please see Section B of the Appendix.
model learns to infer a latent hypergraph that can further used in conjunction with any classical hypergraph neural network architecture.
Our input consists of a set of nodes V = {u,li E {1... NJ} each one characterised by feature vector 2; E R The goal is to predict, for each node, the target y/ E R In the entire paper, we are following the assumption that the node-level target yi the result of a higher-order dynamics, guided by an unknown higher-order structure H.
The processing stages of method summarized in Figure 1. First, we predict the latent hypergraph based on the input features X. The inferred hypergraph structure is then fed into a hypergraph network to obtain the final prediction. To fulfil our goal of obtaining a generally ap- plicable method, easy to optimize and compatible with any hypergraph architecture, our method needs to satisfy two important characteristics. Firstly, the pipeline needs to be end-to-end differentiable, such that the latent hypergraph inference can be trained in weakly supervised fashion, solely from the downstream signal. Secondly, it needs to produce a sparse and discrete structure, such that can be used inside any existing hypergraph processing model.
3. Structure Prediction using SPHINX
The Structure Prediction using Hypergraph Inference Net- work (SPHINX) model is designed to produce higher-order representations without access to ground-truth hypergraph structure. From the set of point-level observations, the
the term inductive when different hypergraph predicted for each example and transductive setup when a single hypergraph is predicted for the entire dataset.
From
3

---

SPHINXX: Structural Prediction using Hypergraph Inference Network
To achieve these, we designed the model using two core components: learnable soft clustering that sequentially predicts probability distributions for each one of the M potential hyperedges. and differentiable k- k-sampling that, based on this probability distribution, samples discrete sub- sets of nodes forming the hypergraph structure. Both components are differentiable such that the model can be easily trained using standard backpropagation techniques. Moreover, the predicted hypergraph structure is discrete object, following the classical structural representation used in any hypergraph processing models H = (V, F), where V is the of nodes and E' is a the of hyperedges.
the symmetries exhibited by the set of hyperedges, inddpen- dently inferring M hyperedges leads to strong ambiguity issues. Concretely, since the slots are initialized randomly, there is no mechanism in place to distribute the hyperedges between slots: multiple slots could be attached to the same obvious hyperedge, leaving others completely uncovered.
To alleviate this, we propose a sequential slot attention. Instead of predicting all hyperedges simultaneously, we will predict them sequentially, one at time, ensuring that at each timestep the hyperedge prediction mechanism is aware of the hyperedges predicted so far. To achieve that, the features of each node z; are enriched with an additional binary vector b, E {0, 1] (M-1) indicating the relationship between that node and the previously predicted hypergraphs. Specifically, when predicting hyperedge j. for each previous hyperedge (t < j). bu = 1 if the node was previously selected to be part of the hyperedge / and ba = 0 otherwise. This way, the slot-attention algorithm has the capacity to produce more diverse hyperedges, as we show in Section 4.1.
3.1. Hypergraph predictor
The goal of this module is to transform set of node features X E N into a set of incidence probabilities P E x where N represents the number of nodes and M repre- sents the expected number of hyperedges. Each column j E {1...M) .M} corresponds to a hyperedge and represents the probability of each node being part of the hyperedge j. In order to accurately predict these probabilities, the model needs to have a global understanding of the nodes interac- tions and identify the subsets that are more likely to exhibit a higher-order relationship.
3.2. Discrete constrained sampling
The hypergraph predictor module, as described above, pro- duces a probabilistic incidence matrix P E R R xMM, where each element Pt.j denotes the probability of a node i be- ing part of the hyperedge j. However, the standard hyper- graph neural network architectures are designed work with sparse and discrete rather than probabilistic structures.
Taking inspiration from the computer vision literature for unsupervised object detection (Greff al., 2020), we model the hypergraph discovery task as soft clustering problem, where each cluster corresponds to a hyperedge. We adapt the iterative slot-attention algorithm (Locatello et al., 2020) to produce M clusters, each one corresponding to predicted hyperedge. The probability of a node é being part of a cluster j. computed as the node-cluster similarity, represents the incidence probabilities Pij corresponding to node i and hyperedge j. Therefore, we will use the terms slots and hyperedges interchangeably.
Previous work (Li et al., 2022) employs Gumbel- Softmax (Jang et al., 2017) to differentiably sample from a categorical distribution. However, these techniques sample each element in the hyperedge independently. without any control on the cardinality of the hyperedge. This leads to unstable optimisation, that requires additional training strate- gies such specific sparsity regularisation. Top-k is another popular approach to achieve sparsity (Zhou et al., 2023; Xu et al., 2022). However, to preserve gradients, the gener- ated structure cannot be discretized. Although a weighted hypergraph can be beneficial for certain architectures, it is not universally compatible with all decoders and makes the interpretation of the latent space more challenging.
Slot Attention for probabilistic incidence prediction. We start by creating M slots, one for each hyperedge. Each slot 8y e /R/ is randomly initialized from a normal distribution. At each iteration, the slots representation updated as the weighted average of all the nodes, with the weights com- puted as a learnable product similarity as indicated by Equation 1, where fi, f2 and fa represent MLPs and a is a non- cineariar After Q iterations, the pairwise similarity between the updated slot representation and the set of node features represents the predicted probability distribution p.. for hyperedge j.
To address this issue, are leveraging the recent advance- ment in constrained k-subset sampling (Ahmed et al., 2023; Niepert et al., 2021; Minervini et al., 2023). These meth- ods were successfully used to tackle discrete problems such as combinatorial optimisation, learning explanations and, more recently, rewiring graph topology (Qian et al., 2023). (1) Different from classical differentiable samplers (Jang et al., 2017), the k-subset sampler would produce subset of size exactly k. equipped with gradient estimator useful for backpropagation.
1t Σ (olfi))))
Pij p(u Ee,) = = f(())
(2)
Sequential Slot Attention for solving ambiguities. The above algorithm suffers from a strong limitation. Due to
In our work, we took advantage of these recent advance-
4

---

SPHINXX Structural Prediction using Hypergraph Inference Network
ments and apply it to produce discrete incidence matrix from the probabilities inferred by the slot attention algo- rithm. Concretely, given the probability distribution P.ji for each hyperedge j, the discrete sampler would select a subset of nodes, representing the group of nodes forming the hyperedge. As demonstrated in Section 4.1, by ensuring that each hyperedge contains exactly & elements, this ap- proach improves over the previous techniques, manifesting an easier optimisation. While the cardinality i needs to be set apriori, as hyperparameter. this value can vary between different hyperedges.
extent the model learns to infer the correct structure.
To alleviate these shortcomings, current works adopt one of the following approaches: either using symthetic data, where we can directly have access to the higher-order relationships used to generate the outcome, or by using real-world data and only evaluate the capability of the model to improve the final prediction, without directly computing the accuracy of the discovered latent structure.
In our work we adopt both approaches. First, we perform an in-depth ablation study on a synthetic dataset containing par- ticle simulations. Then, we move to the real-world datasets where we evaluate on both inductive and transductive setups. Our goal two-fold. We show that our model capable of learning an appropriate latent hypergraph structure in an unsupervised way. Additionally, we prove that the latent higher-order structure, learnt jointly with the rest of the model, helps the performance of the downstream task on both the inductive and transductive problems.
3.3. Hypergraph processing
Producing discrete hypergraph structure and being able to propagate the gradient through the entire pipeline, en- able us to process the resulting latent hypergraph with any existing architecture designed for higher-order represen- tations. In recent years, several architectures were devel- oped for hypergraph-sttucture imput (Feng et al., 2019; Wang al., 2022; Huang & Yang, 2021; Chien et al., 2022). Most of them follow the general two-stage message- passing framework. In the first stage, the information is sent from nodes to the hyperedges using a permutation- invariant operator 2j- = fv-e (1== E ej)). In the sec- ond stage the messages are sent back from hyperedge to nodes T3 = fE-v /E-vv(=>)) E e2t)).
4.1. Particle Simulations
Our simulated system consists of N particles moving in 2D space. For each example, K random triangles were uniformly sampled to represent K 3-order interactions. All the particles that are part of triangle rotate around the triangle's 's center of mass with a random angular velocity Og characteristic to each particle i. If one particle is part of multiple triangles, the rotation will happen around its average center of mass. Examples of such trajectories are depicted in Figure 3 and Figure 6. For each trajectory we observe the position of the particles in the first 22 steps, and the task is to infer the trajectory for the following 25 steps. Each example exhibits two higher-order interactions. The dataset contains 1000 trajectories for training, 1000 for validation and 1000 for test.
In our experiments we use similar setup to the one proposed in (Chien al., 2022), in which the two func- tions fV-E and JE-V are implemented as DeepSets (Za- (S)
heer et al., 2017) models fv-
MLP(E.es es (MLP(s))). Note that, although we experi- mented primarily with the architecture presented above, the framework is general enough to be used with any other hypergraph network. Our experiments demonstrated that even simpler hypergraph models enable the discovery of accurate higher-order structures.
For all experiments, the hypergraph predictor treats parti- cles as nodes. For each particle, the node features consist of the (r, y) coordinates corresponding to the first T timesteps. These features will be used to predict the incidence matrix H. During training, the hypergraph processor receives the predicted hypergraph structure together with the particle's position at timestep and the goal is to predict the position of the particles at timestep ( ++1 1. To generate longer trajec- tories, during testing, the model receives at each moment in time the position predicted at the previous timestep.
4. Experimental Analysis
While the importance of higher-order processing is widely accepted in the machine learning community (Zhou al., 2006) and beyond (Zhang et al., 2020), the amount of bench- marks developed to properly validate the hypergraph meth- ods is still insufficient. This issue becomes even more pro- nounced when it comes to latent hypergraph inference. Al- though there is evidence that many existing real-world tasks exhibit underlining bigher-order interactions that can be beneficial to capture, evaluating the capability of neural network to predict the latent structure remains challenging- First, the input features should contain enough information to predict the hypergraph structure. Secondly, even if we do not need the hypergraph structure as a supervision signal, having access to it is necessary to properly evaluate to what
Hypergraph discovery. These datasets allow us to exper- iment with learning the higher-order relations in a setup where we have access to the ground-truth connectivity. Our model produces discrete hypergraph structures that we can inspect and evaluate, offering an additional level of inter- pretability to the framework. Visualisations of our learned hypergraph structure (see Figure 3) reveal that they are
5

---

SPHINXX: Structural Prediction using Hypergraph Inference Network
a)
13)
b)
C)
5.00000
0.0012
0.025
100
0.00003
0.0013
0.000
Overlap
5,00005
0.013
0.010
0.7
0.00002
0.003
20
0.6
SPHINK-AIDesseett
0.00000
0.000
SPHINX+HSNW
SPHINX+HCHA HCHA
0.5
250
500
730
2000
epoch
Figure 2: Ablation studying the importance of hypergraph inference on the Particle Simulation. (a) The sequential prediction and constrained k-subset sampling clearly helps the downstream performance. (b) SPHINX also predicts more accurate hypergraphs in terms of overlap. (c) Moreover, hypergraph discovery improves during training on the synthetic datasets, even if the model is not supervised for this task. Regardless of the hypergraph architectures, the models achieve a high overlap between the (unsupervised) predicted hypergraph and the gt. connectivitys.
highly correlated to the ground-truth interactions used to generate the dataset.
Section 3.1, SPHINX alleviates this issue by inferring the slots sequentially, and providing at each step historical in- formation about the structure predicted so far. Figure 2.a and 2.b demonstrate the benefits of our design choices. Se- quential prediction (SPHINX) has a clear advantage, outper- forming the classical simultaneous predictor (SPHINX w/o sequential).
We quantitatively evaluate to what extent SPHINX learns the true higher-order relationships, by computing the over- lap between our model's prediction and the ground-truth hyperedges. We refer to the Appendix for a full description of the metric used in this experiment. In Figure 2.c we ob- serve that, even if we do not explicitly optimise for this task, the accuracy of the hypergraph structure predictor increases during training, reaching up to 90% overlap.
Influence of k-sampling, Previous work on inferring hyper- graphs (Li et al., 2022) takes inspiration from the graph do- main (Fetaya et al., 2018) where the differentiable sampling is achieved using the Gumbel-Softmax trick. We argue that, inferring the subset of nodes that are part of a hyperedge generates more challenges compares to the graph scenarios. At the beginning of training, sampling each perredee incidence independently, without constraints, can lead to hyperedges containing either too few too many nodes, which highly damages the optimisation. We can observe this phenomenon visually in Figure 6, column SPHINX w gumbel. In this work, we leverage the recent advance in dif- ferentiable k-subset sampling, which imposes the k-nodes constraint, while still allowing us to estimate the gradient during backpropagation. The experiments in Figure 2.a and Figure 2.b (see gumbel model vs SPHINX model) show that the k-subset sampling improves the results, leading to an easier optimisation and better final performance. This is in line with the results from (Li et al., 2022) where smoothness and sparsity regularisation are crucial for improving the re- sults on a real-world dataset. In contrast, our model obtains competitive performance without any optimisation trick.
General and versatile, our model is designed to predict hypergraph structure that is useful for any hypergraph neural network. However, since the supervision signal comes from the high-level tasks, the architecture used for hypergraph processing can impose certain inductive biases, influencing the hypergraph structure learned by the predictor. In the experiment depicted in Figure 2.c, we investigate to what extent our model learns an accurate higher-ordet order structure, regardless of the hypergraph processing architecture. We train a set of models using the same hypergraph predictor for inferring the hypergraph structure, but various hypergraph networks for processing it. For this, we experiment with AllDeepSets (Chien al., 2022), HGNN (Feng al., 2019) and HCHA (Bai et al., 2021). The results show that our model is capable of learning the suitable structure irrespec- tive of the specifics in the processing model.
Importance of sequential prediction. While the classical slot-attention algorithm infers all the clusters in parallel, we argue that this is not an appropriate design choice for hy- pergraph prediction. Often, the set of hyperedges is mostly symmetric, which makes the problem of attaching the slots to different hyperedges highly ambiguous. In fact, we vi- sually observed that, when predicting all the hyperedges simultaneously, the model tends to associate multiple slots to the same hyperedge, leaving others completely uncovered (see SPHINX w/o sequential model in Figure 6). This be- haviour leads to both a decrease in downstream performance and less accurate hypergraph predictor. As described in
Comparison with inductive hypergraph predictors. The Particle Simulation dataset heavily relies on higher-order processing. In order to predict the particle movement, the model needs to identify the higher-order structures that guide the rotation. To understand to what extent our model is able to produce and process a useful hypergraph structure, we compare against two baselines: a model using a random structure (denoted as random in Figure 2) and node-level model, that ignores the hypergraph structure (denoted as w/o
6

---

SPHINXX: Structural Prediction using Hypergraph Inference Network
Table I: Ablation study on the NBA dataset. Both us- ing sequential, history-award aware predictors and using k-subset sampling prove to be beneficial for the final performance. Moreover, SPHINX shows a clear advantage compared to the existing inductive hypergraph predictors on the single- trajectory prediction task (ADE/FDE metrics).
Table 3: Performance in the inductive setup. in terms of
mino and minFDEg0 metrics for the NBA dataset.
METHOD
1SRC
2SFC
35EC
4SEC
NRI
0.51/0.74
0.96/1.65
1.42/2.50
1.86/3.26
HYPERG. GRAPH
DNRI
0.59/0.70
0.93/1.52
1.38/2.21
1.78/2.81
EVOLVEGRAPH
0.35/0.48
0.66/0.97
1.15/1.86
1.64/2.64
STGAT
0,45/0.66
0.87/1.41
1.28/2.08
1.69/2.66
2SEC
3SEC
4SBC
TRAJECTRON++
0.44/0.67
0.79/1.18
1.51/2.49
2.09/3.52
SPHINX W/O SEQUENTIAL 0.62/0.94
1.18/2.08
1.73/3.14
2.25/4.08
EVOLVEH (H)
0.49/0.74
0.95/1.68 68
1.44/2.27
1.91/3.08
SPHINX W GUMBEL
1.29/1.81
2.10/3.34
2.81/4.00
3.45/5.66
EVOLVEH (H+G)
0.33/0.49
0.63/0.95
0.93/1.36
1.21/1.74
TDHNN
0.68/1.03
1.27/2.22
1.84/3.31
2.30/4.29
TDHNN
0.68/1.03
1.27/2.22
1.84/3.31
2.30/4.29
GROURNET
0.63/1.03
1.38/2.61
2.15/4.11
2.83/5.15
GROUPNET
0,34/0.48
0.62/0.95
0.87/1.31
1.13/1.69
SPHINX
0.59/0.92
1.12/2.06
1.65/3.13
2.14/4.09
SPHINX
0.30/0.43
0.59/0.94
0.88/1.38
1.16/1.74
respective of the hypergraph architecture used as decoder. 3 Predicting the hyperedges sequentially ameliorate the ambiguity issue, improving the hypergraph inference. ④ k- subset sampling is crucial for a good performance, proving to be superior to the standard Gumbel-Softmax approach and allowing us to eliminate the regularisation tricks. (5) Fi-
structure). Both models perform much worse than our learn- able hypergraph model, indicating that the dataset highly depends on higher-order interactions and that our model is capable of discovering an appropriate latent structure.
We also compared against existing hypergraph predictors in the literature. Most of the existing methods are constrained to only work in the transductive setup (by only predicting a single hypergraph for all examples). The only models that are applicable in the inductive setup are GroupNet (Xu et al., 2022), TDHNN (Zhou et al., 2023) and EvolveHyper- graph (Li al., 2022)². The results in Figure 2.a show that our predictor outperforms all the existing ones. We believe that the drop in performance for the existing models is due to the poor gradients used in updating the predictor. Both GroupNet and TDHNN models use a form of top-k selection which only partially propagates the gradients. Moreover, qualitative evaluation shows that TDHNN suffers from the same limitation our "w/o sequential baseline": all the hyperedges ended up selecting the same set of nodes.
nally, discovering the latent hypergraph structure is clearly beneficial for the downstream prediction, improving upon existing inductive hypergraph predictors.
4.2. Inductive setup
To evaluate our model on an inductive real-world dataset, where we need predict a distinct hypergraph for each example, we the NBA SportVU dataset, containing information about the movement of the players during bas- ketball matches. Each example contains 11 trajectories, 5 players from each team and one trajectory for the ball. The hypergraph predictor receives as node features the first 5 timesteps of each trajectory and the goal is to predict the next 10 steps. While our model is not especially designed as a tracking system, the dynamics followed by the basket- ball game contain higher-order relations that are difficult to identify, thus representing a good testbed for our method.
Our model not only outperforms the existing ones in terms of downstream performance, but also discovers more ac- curate hyperedges. Computing the overlap between the prediction and the oracle hyperedges, SPHINX achieves an overlap of 90% compared to 67% for TDHNN (Figure 2.b)².
Ablation study. We assess our core design choices on the real-world dataset as well. In Table 1 we are reporting the average displacement error (ADE) and final displace- ment error (FDE) metrics. Similar to the particle simulation datasets, observe that predicting the hyperedges sequen- tially outperforms the simultaneous approach (SPIINX w/o sequential model) used by standard differentiable clustering al algorithms. Moreover, the k-subset sampling proved to be clearly superior to the Gumbel-Softmax used in the previous methods (SPHINX w gumbel model).
Implementation details. Unless otherwise stated, experi- ments use two slots and the AllDeepSSes model as decoder. For estimating the gradients in the k-subset sampling algo- rithm we experiment with SIMPLE (Ahmed et al., 2023), AIMLE (Minervini et al., 2023) and IMLE (Niepert et al., 2021) algorithms. The first two perform on par, while IMLE suffers from gradient issues. We use Adam optimizer for 1000 epochs, trained single GPU.
Key findings. The results presented in this section demon- strate that: i Our model predicts accurate hypergraph connectivity, that correlates well with the ground-truth struc- ture, even without being optimized for this task and 2 ir-
Comparison recent methods. In Table 3 we compare against other structure-basee methods in the literature in- cluding graph-based methods: NRI (Fetaya et al., 201 2018), DNRI (Graber & Schwing, 2020), EvolveGraph (Li et al., 2020), STGAT (Huang et al., 2019), Trajectron++ (Salz- mann et al., 2020) and hypergraph- based methods: higher- order-only EvolveHypergraph (H), the full EvolveHyper-
FEvol TEvolveHHperrge Hypergaap does not have public code.
Forr GroupNet we not compute the overlap since the num- her of edges is constrained to equal to the number nodes.
7

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
Table 2: Performance on the transductive datasets using various features. SPHINX obtains better results compared to both the static methods, where the structure doesn't modify during training, and dynamic methods, where the hypergraph is optimised. Mean/std computed over 20 runs.
Ground truth
Prediction
NTU MVCNN
MODELNET40 MVCNN
MODEL
GVCNN
GV+MV
GVCNN
GV+MV
GCN
78.80 0..90=0..2
7..72
80,43:11009
9..80-0.46
91.50:11.80
94,85
GAT
79.60-0.03
78.50+1..17
80.16+1.08
91.65-0.25
90.07+0.41
95.75+0.14
STATie
HGNN
82.50=1.62
79.10=0.90
83,6420.37
91.80=1.73
91 00:0000666
96.96+1.43
HGNN+
82.80=1.11
76.40:1.17
84.1810.82
0..50=0.08
90.6011.68
96.92:1.81
HNHN
83.10=1.89
79. 79.60
80,6010.95
12.10-1.776
91.10:11.84
9..8
HYPERGCN
79.90=1.78
78. 033
79.9010.91
92.20=0.80
90.20:10.28
96.10.0.65
DHGNN
82.30=0..8
85.13440.22 1.56
12.13-1.55
85.5340.83
96.99:1.49
DYNAMIC
DESPHGSL
76.28=1.45
1.57
78.67+00.77
89.32-0.71
88.62+0.93
90.33++0 66
HSL
81.82=1.30
75. 13.688.1 1.46
82.26:1 1.20
93.17-0.25
91.4410.42
96.92:10.41
Figure 3:
Predicted trajectories and the latent hypergraph on two exam- ples of the Particle Simulation.
TDHNN
92.70-1.61
10076-+1.05
92,70+ 1.26
96.96-0.34
91 91-92-0.50
98.69+0.38
SPHINX
94,80=0,90
92.95=00885
94.67:0.71
97.29-0.29
92.79:10.41
98.92:20.21
graph (H+G) (Li et al., 2022). GroupNet (Xu et al., 2022) and TDHNN (Zhou et al., 2023). Our method improves the
to the task) GCN, GAT (Veličković et al., 2018), HGNN, HGNN+ (Gao et al., 2023), HNHN (Dong et al., 2020), HyperGCN (Yadati et al., 2019) and dynamic hyperaph methods (where the structure is learned) DHGNN (Jiang et al., 2019), DeepHGSL (Zizhao et al., 2022). HSL (Cai et al., 2022), TDHNN, Table 2 shows that SPHINX learns a better latent structure, improving the final performance.
short and medium-term prediction, while obtaining com- petitive results on the long-term prediction. Moreover, it is the only hypergraph-bast based method that does not require any auxiliary loss function or additional pairwise predictions.
The metrics used in the recent literature (minADEgo and minFDF2g) take into account only the best trajectory from a pool of 20 sampled trajectories. Recently (Greer et al., 2020) show that these metries suffer from a series of lim- ittttion, favouring methods that produce diverse, but less accurate trajectories. Thus, in Table I, we also compared against the existing hypergraph-bassee methods using the single-traeectory prediction metrics (ADE/FDE) (the code for Evooleeyypergaphl is not publicly available). The results clearly show that for single-trajectory prediction our method obtains better results on both short and long-ten tang-termppe prediction.
Note that, upon retraining the TDHNN model, we improved their official results. For fairness we report the improved performance (TDHNN*). However, qualitative evaluation showed that in all cases each hyperedge learned by TDHNN ends up containing all the nodes in the dataset. While the model still obtains a good downstream performance, it seems that this is the results of learning good attention coefficients rather than learning a useful sparse structure.
Implementation details. For all transductive experiments we adopt the split from (Zhou et al., 2023) and train the model with three types of visual features: GVCNN (Feng et al., 2018), MVCNN (Su et al., 2015) or combining both of them. We are treating the number of slots and the cardinality of slots as hyperparameters. Unless otherwise stated, we use AllDeepSet model as hypergraph processor.
Implementation details. In all experiments we use the split from (Xu et al., 2022). For the observed trajectory the features are enhanced with the velocity. For the unobserved trajectory, the velocity is computed based on the predicted position. The models are trained for 300 epochs, using Adam with Ir. 0.001, decreased by a factor of 10 when reaching a plateau. We treat the sampling algorithm as a hyperparameter, experimenting with AIMLE and SIMPLE.
5. Conclusion
We are introducing SPHINX, a model for unsupervised hypergraph inference that enables higher-order processing in tasks where hypergraph structure is not provided. The model adopts global processing in the form of sequential soft clustering for predicting hyperedge probability, paired with a k-subset sampling algorithm for discretizing the struc- ture such that it can be used with any hypergraph neural network decoder and eliminating the need for heavy optimi- sation tricks. Overall, the resulting method a general and broadly applicable solution for relational processing, facili- tating seamless integration into various real-world systems perceived to necessitate higher-order analysis.
4.3. Transductive setup
Most of the hypergraph inference methods are constrained to only predict a single hypergraph, which makes them unsuit- able for the inductive setup. To allow direct comparison with all methods, perform experiments on two transductive datasets for object classification. ModelNet40 (Wu et al., 2014) contains 12311 objects of 40 types, while NTU (Chen et al., 2003) contains 2012 objects with 67 types.
Comparison to recent methods. We compare against both static methods (where the structure does not adapt
8

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
The authors would like thank Char- lotte Magister, Daniel McFadyen, Alex Norcliffe and Paul Scherer for fruitful discussions and constructive suggestions during the development of the paper.
Acknowledgment
Graph Representation Learning and Beyond Work- shop ICMI. 2020, June 2020. Code available:
https//giitubbcomm///iteddcchhhh
Duta, I., Cassarà, G., Silvestri, F., and Lio, P. Sheaf hyper- graph networks. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Feng, Y., Zhang, Z., Zhao, X., Ji, R., and Gao, Y. Gvenn: Group-view convolutional neural networks for 3d shape recognition. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10. 20.1009/VPR.22018000000
2018. doi:
References
Feng, Y., You, H., Zhang, Z.,, Ji, R., and Gao, Y. Hypergraph neural networks. Proc. Conf. AAAI Artif. Intell., 33(01): 3558-3565, July 2019.
Ahmed, K., Zeng, Z., Niepert, M., and Van den Broeck, G. Simple: A gradient estimator for k-subset sampling. In Proceedings of the International Conference on Learning Representations (ICLR), may 2023.
Fetaya, T., Wang. E., Welling, K.-C., Zemel, M., Kipf, T., Fetaya, E., Wang, K.-C. J., Welling, M., and Zemel, R. Neural relational inference for interacting systems. In International Conference on Machine Learning. 2018.
Bai, S., Zhang, F. and Torr, P. H. Hypergraph con- volution and hypergraph attention. Pattern Recogni- tion, 110:107631 2021. ISSN 0031-3203. doi: https:
(iniiorg/10.111160 www.tpaa.pppooopo..o..ooo
Gao, Y., Wang, M., Zha, Z., Shen, J., Li, X., and Wu, X. Visual-textual joint relevance learning for tag based social image search. IEEE Transactions on Image Processing, 22:363-376, 2013. URL ht https: /api. semanticscholes org/ Ctrppsrrpusssacc 7432373.
Banerjee, A.
On the spectrum of hypergraphs. Linear Algebra and its Applications, 614:82-110, 2021. ISSN 0024-3795. doi: https://doi.org// 10..011)...aa..222...... 012. Special Issue ILAS 2019.
Gao, Y., Zhang, Z., Lin, H., Zhao, X., Du S., and Zou, C. Hypergraph learning: Methods and practices. IEEE Transactions on Pattern Analysis and Machine Intelli- gence, 14:2548-25666 2020.
Bica, I. and van der Schaar, M. Transfer learning hetero- geneous feature spaces for treatment effects estimation. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances Neural Informa- tion Processing Systems, volume 35, pp. 37184-37198, Curran Associates, Inc., 2022.
Gao, Y., Feng, Y., Ji, S., and Ji, R. Hgnn+: General hyper- graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):31813199 2023. doi: 10. 21109/TPAM..2022.311
Cai. D., Song, M., Sun. C., Zhang, B., linda Qiao, and Li, H. Hypergraph structure learn- ing for hypergraph neural networks. In Inter- national Joint Conference on Artificial Intelligence, 2022. URL https: /app.aapp..a//// http:://ap.....aaaaaeeee.m semanticscholleee....o.occccoc sttp/oorpusID::5003111
Georgiev, G., Brockschmidt, M., and Allamanis, M. HEAT: Hyperedge attention networks. Transactions Machine Learning Research, 2022. ISSN 2835-8856.
Graber, C. and Schwing, A. G. Dynamic neural relational inference. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition ( (CVPR), June 2020.
Chen, D.-Y., Tian, X.PP., Shen, Y.-T., and Ouhyoung, M. On visual similarity based 3d model retrieval. Comput. Graph. Forum, 22:223-232, 09 2003. doi: 10.1111/ 066766659.00669.
Greer, R., Deo, N., and Trivedi, M. M. Trajectory prediction in autonomous driving with a lane heading auxiliary loss. IEEE Robotics and Automation Letters, 6:4907-4914 4, 2020.
Chien, E., Pan, C., Peng, J., and Milenkovic, O. You are allset: multiset function framework for hypergraph neu- ral networks. In International Conference Learning Representations, 2022.
Greff, K., van Steenkiste, S., and Schmidhuber, J. On the binding problem in artificial neural networks. ArXiv, abs/2012.05208, 2020.
Dong, Y., Sawin, W., and Bengio, Y. Hnhn: Hy- pergraph networks with hyperedge neurons.

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
Guo, T., Zhang, Y., Xue, Y., and Qiao, L.. Brain function network: Higher order more discrimination. Frontiers in Neuroscience, 15, 08 2021. doi: 20.331 696639.
Systems, 284:111254, 2024. ISSN 0950-7051. doi: URL http:://www.sceeeeeddieee com/ calence/articee//////00007222222
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Sys- Curran Associates,
Leskovec, Kleinberg, J. M., and Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. In Knowledge Discovery and Data Mining, 2005.
tems, volume 33, pp. 22118-2213, Inc., 2020.
Li, J., Yang. F., Tomizuka, M., and Choi, C. Evolvegraph: Multi agett trajectory prediction with dynamic relational reasoning. arXiv: Computer Vision and Pattern Recogni- tion, 2020.
Huang, J. and Yang, J. Unignn: a unified framework for graph and hypergraph neural networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 2021.
Li, J., Hua, C., Park, J., Ma, H., Dax, V., and Kochen- derfer, M. J. Evolvehypergraph: Group-aware dynamic relational reasoning for trajectory prediction, 2022.
Huang, Y., Liu, Q.. and Metaxas, D. |video object segmen- tation by hypergraph cut, pp. 7738-1745, 2009, doi: 10.1 10.100/CVPR.220095500077777
Liu, Q. Sun, Y., Wang, C., Liu, T., and Tao, D. Elastic net hypergraph learning for image clustering and semi- supervised classification. IEEE Transactions on Image Processing, 26:452-463, 2016. URL https: /api. semanticscholes org/ CorpusID ( 6468560.
Huang, Y., Bi, H., Li, Z., Mao, T., and Wang, Z. Stgat: Mod- cling spatial-temporal interactions for human trajectory prediction. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 6271-6280, 2019.
Locatello, F,, Weissenborn, D., Unterthiner, T., Mahendran, A., Heigold, G., Uszkoreit, J., Dosovitskiy, A., and Kipf, T. Object-centric learning with slot attention. arXiv preprint arXiv:2006. 15055, 2020.
Jang, E., Gu, S., and Poole, B. Categorical reparameteriza- tion with gumbel-softmax. In Sth International Confer- ence on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceed- ings. OpenReview.net 2017.
Löwe, S., Madras, D., Zemel, R., and Welling, M. Amor- tized causal discovery: Learning to infer causal graphs from time-series data. Causal Learning and Reasoning (CLeaR), 2022.
Jiang. J., Wei, Y., Feng, Y., Cao. J., and Gao, Y. Dynamic hypergraph neural networks. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 19AA'19, pp. 2635-2641 AAAI Press, 2019. ISBN 9780999241141.
Lundell, A. T. and Weingram, S. CW Complexes, pp. 41-76. Springer New York, New York, NY, 1969. ISBN 978-1- 4684-6254-8, doi: 10.10077978-114444--65555
Jost, J. and Mulas, R. Hypergraph laplace operators for chemical reaction networks, 2018.
Minervini, P., Franceschi, L., and Niepert, M. Adaptive perturbation- gradient estimation for discrete latent variable models. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8):920099208 Jun. 2023. doi: 10. 1..16699aaii....m 33718.26103.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Leurning Representations (ICLR), 2017.
Lam, R., Sanchez- Gonialzz,, A., Willson, M., Wirnsberger, P., Fortunato, M., Alet, F., Ravuri, S., Ewalds, T., Eaton- Rosen, Z.. Hu, W., Merose, A., Hoyer, S., Holland. G., Vinyals, O., Stott, J., Pritzel, A., Mohamed, S., and Battaglia, P. Learning skillful medium-range global weather forecasting. Science, 382(6677)1441--172 2023. doi: 10. 2.112//sienceeadi2255
Musciotto, F., Battiston, F., and Mantegna, R. Detecting informative higher-order interactions in statistically vali- dated hypergraphs. Communications Physics, 4, 09 2021. doi: 10. 0133//420005021-00777
Niepert, M., Minervini, P., and Franceschi, L. Implicit MLE: Backpropagating through discrete exponential family dis- tributions. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021.
Lei, F. Huang, J., Jiang, J., Huang, D., Li, Z., and Wang, C.-D. Unveiling the potential of long-range dependence with mask-guided struc- ture learning for hypergraph. Knowledge-Baud Based
10

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
Qian, C., Manolache, A., Ahmed, K., Zeng, Z., den Broeck, G. V., Niepert, M., and Morris, C. Probabilisti- cally rewired wressage-passing neural networks. ArXiv, abs/2310.02156,, 2023.
Wang, Y. and Kleinberg, J. From graphs to hypergraphs: Hy- pergraph projection and its reconstruction. In The Twelfth International Conference on Learning Representations. 2024.
Salzmann, T., Ivanovic, B., Chakravarty, P., and Pavone, M. Trajectron++: Dynamically-feitn feasibbe trajectory forecast- ing with heterogeneous data. In Computer Vision ECCV 2020: 16th European Conference, Glasgow, UK, Au- gust 23-28, 2020, Proceedings, Part XVIII, pp. 683-700, Berlin, Heidelberg, 2020. Springer- Veringer-Verlag... ISBN 978-3- 030-58522-8. doi:
Webb, E., Day, B., Andrés-Teres H., and Lio', P. Factorised neural relational inference for mulii-interaction systems. ArXiv, abs/1905 ftss/195.00721, 2019.
Wu, Z., Song. S., Khosla, A., Yu, F., Zhang, L., Tang, X., and Xiao, J. 3d shapenets: A deep representation for volumetric shapes. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1912-1920, 2014. URL https: / /ppi. semanticscholar. org
Sanchez-Gonzalez, A., Godwin, J., Pfaff, T., Ying, R., Leskovec. J., and Battaglia, P. Learning to simulate com- plex physics with graph networks. In III, H. D. and Singh, A. (eds.). Proceedings of the 37th International Confer- ence on Machine Learning, volume 119, pp. 8459-8468, 2020.
Xu, C., Li, M., Ni, Z., Zhang, Y., and Chen, S. Group- net: Multiscale hypergraph neural networks for trajectory prediction with relational reasoning. In The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Su, H., Maji, S., Kalogerakis, E., and Leamed-Miller, E. Multi-view convolutional neural networks for 3d shape recognition. 05 2015. doi: 10. 10.1100C1...11
Xu, C.,, Wei, Y., Tang, B., Yin, S., Zhang, Y., Chen, S., and Wang. Y. Dynamic-group gropr--aoouurrreee networks for multi-agent trajectory prediction with relational reason- ing. Neural Networks, 170:564-577, 2024. ISSN 0893-6080. doi: http://dcb.aor//o...ooooeeeeeeed
Torres, J. J. and Bianconi, G. Simplicial complexes: higher- order spectral dimension and dynamics. Journal of Physics: Complexity, 1, 2020.
005. UBL.tttprr//ww..cceeeeddeeee.... com/
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones,
L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. At- tention is all you need. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Yadati, N., Nimishakavi, M., Yadav, P., Nitin, V., Louis, A., and Talukdar, P. Hypergen: A new method for training graph convolutional networks on hypergraphs. In Wal- lach, H., Larochelle, H., Beygelzimer, A., d'Alché-Bus Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Young. J.-G., Petri, G., and Peixoto. T. Hypergraph recon- struction from network data. Communications Physics, 4, 06 2021. doi: 10.1038/44205--00-0000777
Yu, J., Tao, D., and Wang, M. Adaptive hypergraph learning and its application in image classification. IEEE Transac- tions on Image Processing, 21( 2012. doi: 10. (099TTP.011..2990000
Viñas, R., Joshi, C. K., Georgiev, D., Dumitrascu, B., Gama- zon, E. R., and Liò, P. Hypergraph factorisation for multi-tissue gene expression imputation, bioRxiv, 2022. doi: 10. 10.1101/2022073315500211
Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. Deep sets. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fer- gus, R., Vishwanathan, S.,. and Garnett, R. (eds.), Ad- vances in Neural Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017.
Wang, P., Yang, S., Liu, Y., Wang, Z., and Li, P. Equivariant hypergraph diffusion neural operators. arXiv preprint arXiv:2207.06688. 2022.
Wang. S., Zhang, Y., Lin, X., Hu, Y., Huang, Q., and Yin, B. Dynamic hypergraph structure learning for multivari- ate time series forecasting. JEEE Transactions on Big Data, PP:1-13, 08 2024. doi: 10.1109/BDATTA20244 3362188.
Zhang, J., Chen, Y., Xiao, X., Lu, R., and Xia, S. Learnable hypergraph laplacian for hypergraph learning. In ICASSP, 2022.

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
Zhang, S., Ding, Z., and Cui, S. Introducing hypergraph signal processing: Theoretical foundation and practical applications. IEEE Internet of Things Journal, 7(1):639- 660, 2020. doi: 10.1 (Q.1099000..201122990222
Zhang, Z., Lin, H., and Gao, Y. Dynamic hypergraph struc- ture learning. IJCAI'18, pp. 3162-3169. AAAI Press,
2018. ISBN 9780999241127.
Zhou, D., Huang, J., and Schölkopf, B. Learning with hy- pergraphs: Clustering, classification, and embedding. In Schölkopf, B., Platt, and Hoffman, T. (eds.), Advances in Neural Information Processing Systems, volume 19.
MIT Press, 2006.
Zhou, P. Wu, Z., Zeng, X., Wen, G., Ma, and Zhu, X. Totally dynamic hypergraph neural networks. In Elkind. E. (ed.), Proceedings of the Thirty-Second In- ternational Joint Conference on Artificial Intelligence, IJCAI-23, pp. 2476-2483. International Joint Confer- ences on Artificial Intelligence Organization, 8 2023. doi: 10.249963/ficai220233777 URL https: /doi.iooooooooo org/ 10. 0144996/1jcai.22220 275. Main Track.
Zizhao, Z., Feng. Y., Ying, S., and Gao, Y. Deep hypergraph structure learning, 08 2022.
12

---

SPHINXX: Structural Prediction using Hypergraph Inference Network
Appendix
This appendix contains details related to our proposed Structural Prediction using Hypergraph Inference Network (SPHINX) model, including broader impact and potential limitations, qualitative visualisations from our model and the baselines we compared against in this paper, details about the proposed dataset, information about the implementation of the model and additional experiments referred in the main paper. We will soon release the full code associated with the paper.
Section A highlights a series of potential limitations that can be address to improve the current work, together with a discussion about the social impact of our approach.
Section B presents an overview of the existing methods for hypergraph prediction, with a focus on a few qualities that we believe a general methods should fulfill.
Section C present the computational complexity of our model.
Section D contains visualisation of the discovered hypergraph structure and the predicted trajectory for our proposed model and different variations of it.
Section E provides more details about the proposed synthetic dataset, further information about the method and its training process.
Section F presents additional ablation studies showing the influence of varying the number of hyperedges in our model, but also more detailed analysis of the synthetic experiments presented in the paper.
A. Broader Impact & Limitations
In this paper, we are proposing a framework for processing higher-order interactions in scenarios where a ground-truth hypergraph connectivity is either too expensive or not accessible at all. We are showing that our model capable of recovering the latent higher-order structure without supervision at the hypergraph level, thus improving the final, higher-level performance. While mainly tested trajectory prediction tasks, our model is general and versatile and can be applied to any scenarios where we suspect capturing and modeling higher-order relations can be beneficial. Consequently, we believe that our model doesn't have any direct negative societal impact. Moreover, the method has the advantage of allowing us to inspect the learned latent hypergraph structure (as we can see in Section D of this Supplementary Material). This offer an advantage in terms of interpretability, allowing us to better understand and address potential mistakes in the model's s prediction.
By construction, our model predicts a set of M slots, each one corresponding to hyperedge. This process is sequential, with one slot predicted at each time-step. While stopping criterion can be imposed to allow dynamic number of hyperedges, in order to be able to take advantage of the historical features b E {0, 1) N) we need to have access to pre-defined maximum number of hyperedges M. In the current version of our work, this number is picked as a hyperparameter. However, in Section D. we experimentally show that the chosen value doesn't 't have a significant impact on the results. As long as the number of hyperedges is larger than the expected one, the performance doesn't decrease.
Furthermore, as we show in our experimental analysis, the k-subset sampling has a clear, positive impact the performance of our model. However, this comes with a limitation: the sampled hyperedge is constrained to have exactly k nodes. During training, this constrain helps the optimisation in terms of stability, allowing us to easily train our model without the need for regularisation or optimisation tricks. However, we are restricted to predict only k-regular hyperedges (i.e. hyperedges containing exactly k nodes). While in all our experiments we use the same constant l: for all hyperedges, the framework allows us to use a sequence of cardinalities, ones for each hyperedge. However, additional domain knowledge is needed to pre-determined this sequence. Since having extra slots proved to harmless for our model, one solution is to provide a diverse list of k such that it covers a broader range of possibilities. While interesting to explore, these experiments are left as future work.
On the inductive setup, in order to better align with the current literature, we mainly validate our model on the trajectory prediction task. However, in the current form, our model predicts single hypergraph structure for the entire trajectory. This is well suited for the synthetic benchmark, where the dynamics for each example is determined by a single hypergraph structure, that does not change in time. On the other hand, in worldworld setups, such as the NBA dataset, the higher-order interactions between the players might change along the game. Thus, having a distinct, dynamic hypergraph structure, that
13

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
evolves in time, could be beneficial. However, solving trajectory prediction is not the main goal for our model. Instead, our purpose is to have general model, that allows to infer and process higher-order interaction. We helieve that adapting SPHINX to more specific scenarios, such as creating a dynamic, evolving structure is an interesting area for future work.
B. Overview of the existing dynamic hypergraph predictors
Table 4: Overview of the existing methods for hypergraph prediction.
METHOD
INDUCTIVE
TRANSDUCTIVE
DIFFERENTIABLE
DISCRETE
REGULARISATION FFEIEN--REE
DEEHHGSL (ZIZHAG ET AL., 2022)
REQUIRES INITEAL IGGAPI
MHSL (LE) AL., 2024)
XX
REQUIRES INITIAL HORAPH
HERALD (ZHANG RT Al.,, 2022)
REQUIRES INITIAL BIGRAPIS
ADA-HYPER (Yu AL.,, 2012)
DVHL (ZHANG ET AL.., 2018)
DRGNN (JING Al.,, 2019)
(DIHSL (WANG ET AL., CALET AL., 2022)
TDHNN (ZHOU Af.,, 2023)
(DYNIGROLPÑET (XU ET AL... 2022: 2024)
EvOLVEltYPEKGRAPH (LI AL., 2022)
SPHINX (ÖURS)
For better understanding of the field, we are offering an overview of the existing methods for dynamic hypergraph prediction, focusing on the three desiderata that we highlight in the introduction: 1) The model should be applicable on broad types of tasks. For a general hypergraph prediction method, it should be adaptable for both the inductive and the transductive setup. 2) The model should be compatible with any hypergraph processing architecture. This requires the model to be differentiable and to produce a discrete output such that it can be easily plugged into any hypergraph decoder. 3) powerful model should be easy to optimise. Most of the models requires additional regularisation terms or residual branches in order to optimise the hypergraph predictor well. Ideally, the model should allow to incorporate the hypergraph predictor component without negatively impacting the optimisation process.
For completeness, we are including also methods such as DeepHGSI, MHSI. and HERALD, but these methods does not directly generate hypergraph structure, but rather rewire an existing one. As we can see in Table 4, half of the models are unapplicable in the inductive setup mainly due to the fact that they are treating the structure as a parameter. The models marked with the symbol are only partially differentiable. Models such as top-k or threasholding, when using to infer a discrete structure, loses the gradient. Moreover, the table also suggests that most of the methods are having issue in optimising a sparse, discrete structure without incorporating various regularisation constraints.
The results presented in our main paper confirm the fact that SPHINX is general and easy to adapt method, as it obtains good performance across various setups, without any additional regularisation.
C. Computational complexity.
We analyse the computational complexity of the hypergraph-inferree inference component for the SPHINX architecture (hypergraph predictor + sampling) when using the SIMPLE k-subset sampling algorithm. The overall complexity would be obtained by adding the complexity specific to the hypergraph neural network used to process the higher-order structure. If / is the number of nodes, K is the cardinality of the predicted hyperedges and M is the number of inferred hyperedges, the vectorized complexity for the sampling module is OllogN x logK)) and the complexity of slot-attention with Q iterations and one slot (Q x N). Then, the overall complexity for predicting M hyperedges is O(M x Q x N + M x logN x logK)).
D. Visualisations
One of the advantages brought by our method is providing a discrete latent hypergraph structure, that can be easily visualise, offering higher level of interpretability compared to attention-based methods. Figure 6 shows the trajectories and latent structure learned by our model on some examples from the Particle Simulation and NBA datasets. We are visualising the ground-truth trajectories, the trajectories and structure predicted by our full model, and the trajectories and learned structure corresponding to the model used in our ablation study: SPHINX w/o sequential and SPHINX w Gumbel.
When the slots are predicted in parallel, without access to the already predicted hyperedges (the model called SPHINX w/o
14

---

SPHIINX: Structural Prediction using Hypergraph Inference Network
Figure 4: Examples of 25-steps trajectories from the Particle Simulation datasets. The highlighted triangles represent the 3-order interactions used to generate the trajectories.
sequential), the slots tends to collapse in single hyperedge represented by all the slots. On the other hand, removing the constraints on the cardinality of the hyperedges, by applying Gumbel-Softmax (the model called SPMNNX w Gumbel). the optimisation process leads to "greedy" slots, that covers all the nodes in the hypergraph.
In contrast, our SPHINX model learns sparse and intuitive hypergraph structures, alleviating the slot collapsing behaviour, On the synthetic dataset, the predicted hypergraph highly coincide with the real connectivity. By inspecting the higher-order structures learned by our model the NBA dataset, observe that most of the inferred hyperedges contains the node associated with the ball (denoted white node in Figure 6). we believe that this is natural choice, since the position of the ball should have a critical influence on the decision taken by all basketball players.
Insights on the inferred hypergraph. Evaluating the accuracy of predicted latent hypergraphs in real-world data is critical but challenging problem, that remains an open problem. Our datasets lack annotations for higher-ordes structures, and even if they would have existed, there's no guarantee they would be optimal for the task.
However, to understand the type hypergraph predicted by our model the real-world datasets, we analyze the NBA dataset, an inductive dataset that is easier visualize and interpret. For model with hyperedges and nodes per hyperedge:
the average node degree for the predicted hypergraphs are [1.97, 1.98, 1.99, 1.99, 1.98, 1.95, 1.96, 1.96, 1.96, 1.95, 4.29]. The first 10 nodes correspond to players- model focuses uniformly on all of them; while the last node represents the ball- the model learns to include the ball in most hyperedges. Thus the predicted structures are star-like hypergraphs, aligning with our intuition that player movement highly influenced by the ball's position.
the average percentage of duplicated hyperedges across examples is 2.74%.
This shows high diversity in our predictions, confirming that the model captures not just the most likely connections but also a scene-specific structure.
E. Experimental details
E.1. Datasets details
We create a synthetic benchmark, Particle Simulation, to validate the capabilities of our model in terms of downstream performance, while also enabling the evaluation of the predicted higher-order interactions. Previous works used various synthetic setups to achieve this goal. However, to our knowledge, none of them are publicly available.
Particle Simulation dataset contains a set of particles moving according to a higher-order law. Each example in our dataset consists of N particles moving 2D space. Among them, K random triangles where uniformly sampled to represent K 3-order interactions. All the particles that are part of triangles are rotating around the triangle's center of mass with an angular velocity A; randomly sampled for each particle i. If one particle is part of multiple triangles, the rotation will happen around their average center of mass. The task is, given the first / = 22 time steps of the trajectory (only the position of the particles and the angle velocity associated with the particles, no triangles provided), to be able to predict the rest of the trajectory (25 steps). Note that, for each example in the dataset, we have different triangles connecting the particles. Given the hypergraph structure, the task satisfy the Markovian property, but in order to predict the hypergraph structure you need access to at least consecutive timesteps.
15

---

SPHINN: Structural Prediction using Hypergraph Inference Network
The dataset contains higher-order interaction per trajectory. The dataset split constitutes of 1000 trajectories for training, 1000 forvalidation and 1000 for test.
Some examples of the dataset are depicted in Figure 4.
E.2. Implementation details
Model details. To encode the observed part of the trajectory into the hypergraph predictor, experimenting with two variants. Either we are using an MLP that receives the concatenation of the node's coordinates from all timesteps, or a 1D temporal Convolutional Neural Network acting on the temporal dimension.
For the synthetic dataset, both the hypergraph predictor and the hypergraph processor are receiving as input the (x.y) coordinates of each node, while for the NBA dataset the spatial coordinates are enriched with information about the velocity (the real velocity for the observed trajectory and the estimated one during evaluation).
For the AltDeepSets model, used Hypergraph Processor, we adapt the standard architecture, by incorporating information about the angular velocity: at each layer, in the form of sin(O.), cos( concatenated to each node at the end of each layer.
1 step
5 steps
25 steps
0.00010
0.00125
0.03
0.00008
0.00100
MSE
0.00006
MSE
0.00075
MSE
0.02
0.00004
0.00050
0.01
0.00002
0.00025
0.00000
0.00000
0.00
1
4
Num slots
Num slots
Num slots
Figure 5: Experiments on Particle Simulation dataset investigating the importance of choosing the correct number of predicted hyperedges. Having less hyperedges than the real number (two) negatively impact the performance. However, when increasing the number hyperedges above the true value, the performance does not deteriorate, indicating that the model robust at discovering the hypergraph structure, as long as enough slots are provided.
Unless otherwise specified, the results reported in the main paper are obtained using syper-parameter tuning. We are performing bayesian hyperparameter tuning, setting the base learning rate at 0.001, multiplied with a factor of d e (0.1, 1.0, 10.0} when Icarning the parameters corresponding to the hypergraph predictor, a batch size of 128, self-loop added into the structure. The hidden state picked from the set values (32, 64, 128, 256}, the number of AllDeepSets layers from 21, the number of layers for the used MLPs from 32 4), the number hyperedges from {1, 3, 5, 7} (except for the synthetic setup where the number of hyperedges is set and 2 respectively), the dimension of hyperedges from {3, 4, 5, 6} (except for the synthetic setup where the number of hyperedges is set to 3), nonlincarities used for the similarity score are either sigmoid, sparsemax or softmax, the algorithm for k-subset sampling is either AIMLE or SIMPLE, with their associated noise distribution sum of gamma or gumbel. For the NBA dataset, we are training for 300 epochs, while for the Particle Simulation we are training for 1000 epochs.
The code for loading the NBA dataset based on the official code for (Xu et al., 2022y1. The code for the various k-subset sampling algorithms is based on the code associated with AIMLE (Minervini al., 2023), IMLE" (Niepert al., 2021) and SIMPLE (Ahmed et al., 2023) methods.
Metric details. To validate to what extent our model is able to predict the correct hypergraph structure, we are computing the overlap between the predicted hypergraph and the ground-truth connectivity used to generate the trajectory. For a model
www.:///iiinnngggn...oaaaeeeeeee under under MIT License
hhttps//gitthhb.co http:///ittuu.coo///nniioooooooe under MIT License thtpps:/githuh.com. LWA.LCCCA-StarA/SSMPPP custom License, open for research
under MIT License
16

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
predicting K hyperedges, let's consider the set of predicted hyperedges as P PP--P2-PK)) J and the target hyperedges as G = [gi, 92-9K): ). For each element
are computing the percentage of the nodes that are in both the prediction p; and the ground-truth hyperedge 9i. Since we are computing the element-wise overlap between two unordered sets, we fix the order of the ground-trui truth list G. and compute the metric against all the possible permutations of P. The overlap corresponding to the best permutation represents our reported metric. This metric is a scalar between 0 and 1, with O representing completely non-overlapping sets, and 1 denoting perfect matching.
F. Additional experiments
E.1. Description of the models used in Particle Simulation
In the following, we will describe all the baselines used in the Particle Simulations ablation study.
Random structure Instead of predicting the hypergraph structure, this model uses randomly sampled hypergraph con- nectivity. The goal is to understand how much of our performance comes from having a strong decoder, compared to the advantage of predicting a real, suitable hypergraph structure.
No structure entirely ignores the higher-order interaction, by setting the incidence matrix to zero. The purpose of this baseline is to understand to what extent our datasets require higher-order interactions.
SPHINX w/o sequential uses the same processing our full proposed model. However, instead of sequential slot-attention it uses the classical slot-attention clustering, which predicts all the slots simultaneously. Comparison with this baseline sheds light on the importance of predicting the hyperedges sequentially.
SPHINX w Gumbel is a modification of our full SPHINX model, by replacing the k-subset sampling with the Gumbel- Softmax, frequently used both graph and hypergraph inference models. While allowing us to propagate gradients through the sampling step, the Gumbel-Softma has no constraints on the number of nodes contained in each hyperedge, sampling independently for each mode-hyperede incidence relationship.
TDHNN and GroupNet We adapt the models proposed in (Zhou et al., 2023) and (Xu et al., 2022) respectively to predict the group of particles that are interacting in the Particle Simulation dataset. To ensure a fair comparison we are using the same decoder in all experiments and only modify the encoder.
F.2. Varying. number of hyperedges
Although the number of parameters does not scale with the number of inferred hyperedges, by construction we are restricted to predict maximum M hyperedges, where M is set as hyperparameter. This is mainly due to the use of binary feature vector 5 encoding the history predicted so far, which has a fixed dimension {0, 1] (MM-1)
To establish what extent the value we choose as the number of hyperedges impacts the performance, we conduct an ablation study by varying the number of slots predicted by our method. The results in Figure show that picking number of slots larger than the real one doesn't 't harm the performance. Visual analysis of the learned hypergraph reveals that, when offering more slots than needed, the model tends to produce redundancy, associating the extra slots to hyperedges that were already discovered. To better understand this behaviour, we measured the average number of distinct hyperedges predicted when providing more slots than required. The results are show in Table 5.
Table 5: Ablation study providing more slots than the real number. Unique Hyperedges denotes the number of unique predicted hyperedges while MSE denotes the final performance.
Slots
Unique Hyperedges
MSE
slot
1.00
0.00007
2 slots
1.96
0.00002
3 slots
2.15
0.000017
4 slots
2.14
0.000007
We believe that this is very interesting result, it shows that when equipped with more slots than necessary the model learss some form of redundancy (by predicting the same hyperedge multiple times) instead of hallucinating fake relations.
17

---

SPHINNX: Structural Prediction using Hypergraph Inference Network
Ground truth
SPHINX
SPHINX w/o sequential
SPHINX Gumbel
NBA
NBA
Two- Two- Trianggnsl
Two- Triangles
Figure 6: Visualisation of the trajectories predicted by our full model (SPHINX) and the variations used in the ablation study (SPHINX w/o sequential and SPHINX Gumbel) the Particle Simulation and NBA dataset. In the ground-truth column the highlighted polygons represent the true connectivity, while for the models they represent the discovered hyperedges. Both using Gumbel-Soffmax and dropping the sequential prediction clearly impact the predicted hypergraphs. Gumbel-Softmax struggles to produce sparse structure, while the lack of sequentiality leads to both predicted hyperedges containing the same set of nodes. On the other hand, our model manage to discover diverse structures, close to the ground-truth ones in the synthetic scenario.
18


Reviews:
[{"review_id": "JxttTeqiI1", "reviewer": "Reviewer_WzEA", "summary": "The paper introduces SPHINX, a novel model designed to infer latent hypergraph structures in an unsupervised manner solely from task-dependent signals. Recognizing the limitations of traditional graph models in capturing higher-order interactions, SPHINX employs a sequential soft clustering approach combined with constrained k-subset sampling to generate discrete hypergraph structures. These structures are compatible with existing hypergraph neural networks and can be optimized end-to-end without additional regularization losses. Through extensive experiments on four challenging datasets, including both synthetic and real-world data, the authors demonstrate that SPHINX effectively infers meaningful hypergraphs that enhance performance in both transductive and inductive tasks, outperforming existing hypergraph prediction methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and constructive feedback. We appreciate the time you've taken to review our work, and we would like to address your concerns and questions.\n\n**Fixed hyperedge size**\n\nWe want to mention that, while the cardinality k is indeed non-learnable, SPHINX does allow hyperedges of different sizes. The coefficient k in the k-sampling algorithm does not affect the number of learnable parameters so it can differ from one hyperedge to another. For simplicity and to reduce hyperparameter search space, we use a fixed k across all hyperedges. However, if a more diverse hypergraph structure is needed, an array of k-values can be provided as input\n\nWe agree that a dynamic k could enhance flexibility and is a promising direction for improvement. One possible adaptation is selecting k for each hyperedge based on probability distribution statistics. For instance, defining k as the number of nodes above a probability threshold or the rank at which a certain gap appears in the distribution. While this approach remains non-differentiable w.r.t k, it eliminates the need for pre-defined hyperedge cardinality by allowing dynamic values.\n\nWhile these adaptations are straightforward, they were not included in the current study. Exploring fully learnable hyperedge cardinality is an interesting future direction..\n\n**Predefined Hyperedge Count / Sensitivity w.r.t. M**\n\nHaving a fixed maximum number of hyperedges is indeed a limitation that we are sharing with most of the hypergraph predictor methods in the literature. \n\nThe experiments presented in the Appendix (Fig 5)  are designed to understand to what extent this affects the performance of the model on the synthetic setup (where we know what is the real number of hyperedges needed). The results show that, as expected, having a too small M causes a drop in performance while having an M that is larger than the golden standard does not affect the performance.  \n\nTo better understand this behaviour, we measured, for each hypergraph, the average number of distinct hyperedges predicted when providing more slots than required.  The results are as follow: \n\n| Slots | Unique Hedges | MSE |\n|------------|------------------|-----------|\n| **1 slot**  | 1.00 | 0.00007 |\n| **2 slots** | 1.96 | 0.00002 |\n| **3 slots** | 2.15 | 0.000017|\n| **4 slots** | 2.14 | 0.000007|\n\nWe believe that this is a very interesting result, as it shows that when equipped with more slots than necessary the model learns some form of redundancy (by predicting the same hyperedge multiple times) instead of hallucinating fake relations.\n\n**Computational efficiency and memory usage on large-scale data**\n\nFor a model with N nodes, M hyperedges, and cardinality of hyperedges K, the complexity of our model is O(M × N + M × logN × logK). This becomes problematic when the number of nodes and the number of hyperedges is simultaneously very large. \nThe most computationally intensive component is the slot-attention algorithm. To improve scalability for large-scale datasets, one potential optimization is to precompute an initial node clustering and restrict slot-attention computations to selecting hyperedges within each cluster (local structure) rather than across the entire graph. This would reduce complexity to O(M×N′+M×log⁡N′×log⁡K), where N’ is the maximum cardinality of a cluster.\n\nFollowing reviewer suggestions, we also measured the time and memory consumption per iteration on NBA dataset (batch size: 128, 11 nodes per example) and the ModelNet dataset (hypergraph with 12 311 nodes). All experiments were conducted on 1 GPU,  Quadro RTX 8000 with 49GB. While we ensured architectural comparability between models, we note that our model has not yet been optimized for large-scale datasets. Further engineering improvements can further enhance scalability.\n\n| Metric | ModelNet40  | | |NBA | | |\n|---------------------------|----------------------|-|-------|-------------------|-------------------|-----------------|\n|| SPHINX |TDHNN||SPHINX|TDHNN|GroupNET|\n| **Training Time (sec)** |0.32 |0.77||0.018|0.21|0.071|\n| **Inference Time (sec)** |0.26|0.76||0.030 |0.22|0.030|\n| **Memory Usage (MB)**  |9156.17|20559.32||187.61|508.00|3261.53|\n\nWhile our model's memory requirements increase with dataset size, it remains significantly more efficient than previous models in the literature.\n\n**Additional  related work on dynamic hypergraphs and k-subset sampling algorithms**\n\nWe thank the reviewer for the suggestions. We will do our best to incorporate a review of the k-subset sampling advancement together with  more dynamic hypergraph learning methods. We are welcoming any particular suggestions of relevant work that we are missing.\n\nWe appreciate the suggestions and agree that enabling hypergraph inference unlocks numerous real-world applications. While our experiments focused on a subset of topics, we are eager to explore broader real-world applications in future work.", "claims_and_evidence": "The paper makes several key claims:\n\n1.SPHINX can accurately infer latent hypergraph structures in an unsupervised manner solely from task-dependent signals.\n2.The inferred hypergraphs are interpretable and enhance performance in both transductive and inductive tasks.\n3.SPHINX outperforms existing hypergraph prediction methods across multiple datasets.\n\nThese claims are supported by comprehensive experimental evidence, including ablation studies that highlight the importance of sequential prediction and k-subset sampling. The model is evaluated on both synthetic and real-world datasets, demonstrating superior performance metrics compared to baseline and state-of-the-art methods. Additionally, the paper provides qualitative visualizations of the inferred hypergraphs, aligning closely with ground-truth structures in synthetic settings, further reinforcing the validity of the claims.", "methods_and_evaluation_criteria": "The proposed method, SPHINX, integrates a sequential soft clustering mechanism with constrained k-subset sampling to infer hypergraph structures. Specifically, it utilizes a slot-attention mechanism adapted for sequential prediction to address ambiguity issues inherent in parallel hyperedge prediction. The k-subset sampling ensures that each hyperedge contains exactly k nodes, facilitating stable optimization without the need for additional regularization.\n\nFor evaluation, the authors employ both synthetic and real-world datasets. The synthetic Particle Simulation dataset allows for direct assessment of hypergraph inference accuracy by comparing predicted hyperedges with ground truth. Real-world datasets, including the NBA SportVU, ModelNet40, and NTU datasets, are used to evaluate the downstream performance of SPHINX in inductive and transductive tasks. Metrics such as Average Displacement Error (ADE), Final Displacement Error (FDE), and overlap with ground-truth hyperedges are utilized to measure performance.", "theoretical_claims": "The paper does not present significant theoretical claims or proofs. The focus is primarily on the empirical performance of the SPHINX model in inferring hypergraph structures and enhancing downstream task performance. Therefore, there are no theoretical proofs to verify.", "experimental_designs_or_analyses": "The experimental design is robust and well-structured. The authors conduct extensive ablation studies to isolate the contributions of sequential prediction and k-subset sampling, demonstrating their necessity for optimal performance. The use of both synthetic and real-world datasets allows for comprehensive evaluation of the model's capabilities in controlled and practical scenarios. Additionally, the comparison with a range of baseline and state-of-the-art methods across different tasks and datasets ensures that the performance improvements are consistent and significant. The inclusion of qualitative visualizations further aids in understanding the effectiveness of the inferred hypergraphs.", "relation_to_broader_scientific_literature": "The paper situates its contributions within the broader context of graph and hypergraph neural networks, as well as structural inference in machine learning. It builds upon existing works in neural relational inference and hypergraph neural networks, addressing their limitations by enabling unsupervised hypergraph inference that is both inductive and transductive. SPHINX distinguishes itself by introducing sequential slot-attention and constrained k-subset sampling, which are not extensively explored in current literature. By comparing with a wide range of related methods, the paper highlights its novel approach to hypergraph structure prediction and its superior performance, contributing significantly to the field of higher-order relational modeling.", "essential_references_not_discussed": "The paper appears to comprehensively review the relevant literature in the domains of hypergraph neural networks and structural inference. However, it does not mention recent advancements in dynamic hypergraph learning or specific k-subset sampling techniques that might be pertinent. Including references to the latest works in these areas could provide a more thorough context and strengthen the positioning of SPHINX within the current research landscape.", "other_strengths_and_weaknesses": "Strengths:\n1.Innovation: SPHINX introduces a novel combination of sequential slot-attention and constrained k-subset sampling, addressing key limitations in current hypergraph inference methods.\n2.Comprehensive Evaluation: The extensive experiments on both synthetic and real-world datasets, along with thorough ablation studies, provide strong evidence of the model’s effectiveness.\n3.Interpretability: By generating discrete hypergraph structures, SPHINX offers enhanced interpretability, allowing for better understanding and visualization of high-order interactions.\n4.Applicability: The model’s compatibility with various hypergraph neural network architectures and its performance in both inductive and transductive settings make it versatile for different applications.\n\n\nWeaknesses:\n1.Fixed Hyperedge Size: The requirement of fixed k-node hyperedges may limit the model’s flexibility in scenarios where the size of high-order interactions varies.\n2.Predefined Hyperedge Count: The necessity to set a maximum number of hyperedges (M) beforehand could be restrictive in dynamic environments where the number of interactions is not known a priori.\n3.Limited Theoretical Insight: The paper focuses heavily on empirical results, with limited discussion on the theoretical underpinnings of why the proposed method works effectively.", "other_comments_or_suggestions": "The paper is well-written and presents a clear narrative of the problem, proposed solution, and experimental validation. Including more diverse real-world applications beyond trajectory prediction, such as social network analysis or biological interaction networks, could further demonstrate the versatility of SPHINX. Additionally, exploring dynamic hyperedge sizes or adaptive hyperedge counts in future work would address some of the current limitations and enhance the model’s applicability.", "questions_for_authors": "1.  Have you considered extending SPHINX to handle hyperedges of varying sizes, and if so, what challenges do you anticipate?\n2.  How does SPHINX perform with larger-scale datasets in terms of computational efficiency and memory usage?\n3. Can you provide more insights on how sensitive the model's performance is to the chosen maximum number of hyperedges (M)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KdgfXFshfL", "reviewer": "Reviewer_rEAs", "summary": "This paper introduces the SPHINX model, which aims to infer a latent hypergraph structure suitable for the final task in an unsupervised manner from input features, to support higher-order relationship processing in the absence of a readily available hypergraph structure. The process is divided into three steps: First, the hypergraph predictor infers a latent hypergraph based on the input features. Next, a k-subset sampling algorithm is used to transform the obtained probability distribution into specific incidence relationships. Finally, the predicted hypergraph is applied to a standard hypergraph neural network to generate higher-order representations. Experimental results show that SPHINX not only excels in inferring latent hypergraphs but also effectively enhances the performance of downstream tasks in both inductive and transductive settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your detailed review and valuable feedback on our paper. We would like to address your concerns and questions.\n\n**Hypergraph evaluation for real-world datasets**\n\nQuantitatively evaluating the accuracy of predicted latent hypergraphs in real-world dataset is a very important but also very challenging problem, that remains open in the community. Our datasets lack annotations for higher-order structures, and even if they would have existed, there’s no guarantee they would be optimal for the task. This aligns with challenges in the explainability community, where models are typically tested on synthetic data. Additionally, research in the rewiring community suggests that even when a ground-truth (hyper)graph is available, it is often suboptimal for solving the task. All of these motivated us to construct the synthetic dataset, where we can control a strong connection between the hypergraph structure and the label. \n\nHowever, to better interpret the type of hypergraph predicted by our model in the real-world datasets, we analyze the NBA dataset, an inductive dataset that is easier to visualize and interpret. For a model with six hyperedges and four nodes per hyperedge:\n- the avg node degree for our predicted hypergraphs are [1.97, 1.98, 1.99, 1.99, 1.98, 1.95, 1.96, 1.96, 1.96, 1.95, 4.29].\nThe first 10 nodes correspond to players - model focuses uniformly on all of them; while the last node represents the ball - the model learns to include the ball in most hyperedges. Thus, the predicted structures are star-like hypergraphs, aligning with our intuition that player movement is highly influenced by the ball’s position. \n- the average percentage of duplicated hyperedges across examples is 2.74%. This shows a high diversity in our predictions, confirming that the model captures not just the most likely connections but also learns a dynamic, scene-specific structure.\n\nRegarding the diversity of the datasets, we especially picked them to span both the inductive and transductive setup, with a wide variety of sizes: NBA (11 nodes) ModelNet40 (12311 nodes), NTU (2012 nodes).\n\n***Model is easy to optimize* without analysis**\n\nAs mentioned in the introduction, by *easy to optimise* we mean that our model does not require additional regularisation losses that are necessary in most of the previous works in order to stabilise the training (e.g. sparsity regularisation, reconstruction regularisation). We are sorry for not being clear enough in that respect and we are happy to further clarify this claim if the reviewer thinks it necessary.\n\n**Missing review of classical methods and dynamic graph structures**\n\nWe aimed to provide a broad overview, covering 2018-2024 papers from both machine learning and closed-form solution methods. We're happy to expand it and would appreciate any specific suggestions from the reviewer.\n\nIn the section *Structural Inference on Graphs*, we discuss advancements in the graph prediction literature. However, we apologize if any relevant works were overlooked and we will do our best to do a more comprehensive review in the final version.\n\n**Analysis of the model’s interpretability**\n\nThe interpretable character of our model is indeed given by the discrete structure of our hypergraph which enables: a) explicit inspection of the latent structure used by the final model, and b) discovery of meaningful correlations in the input data. For a concrete example, please refer to the NBA analysis above, which illustrates how our model captures interpretable patterns in real-world data.\n\n**Scalability for large-scale data**\n\nFor a model with N nodes and M hyperedges, each containing K nodes, the computational complexity is O(MxN+MxlogNxlogK) . This can become a challenge when both the number of nodes and hyperedges grow significantly. The primary computational bottleneck lies in the slot-attention algorithm. To enhance scalability for large datasets, a potential optimization is to precompute an initial clustering of nodes and limit slot-attention computations to selecting hyperedges within each cluster rather than across the entire dataset. This adjustment would reduce the complexity to O(MxN'+MxlogN'xlogK), where N' represents the maximum cluster size.\n\nFollowing your suggestions, we measured time and memory per iteration on NBA (batch size 128, 11 nodes) and ModelNet (12,311 nodes) using a Quadro RTX 8000 (49GB). While ensuring architectural comparability, our code is not optimized for large-scale datasets. Further engineering improvements can further enhance scalability.\n\n|Metric|ModelNet40| | |NBA| | |\n|-|-|-|-|-|-|-|\n||SPHINX |TDHNN||SPHINX|TDHNN|GroupNET|\n|**Training Time (sec)**|0.32 |0.77||0.018|0.21|0.071|\n|**Inference Time (sec)**|0.26|0.76||0.030 |0.22|0.030|\n|**Memory Usage (MB)**|9156.17|20559.32||187.61|508.00|3261.53|\n\nWhile our model's memory requirements increase with dataset size, it remains significantly more efficient than previous models in the literature.", "claims_and_evidence": "Some of the arguments in the paper are not sufficiently substantiated. Although the authors claim that SPHINX can infer latent hypergraphs that are highly consistent with the true higher-order structures, the validation on real-world datasets is not adequate. There is no direct evidence to prove the match between the inferred hypergraphs and the actual higher-order relationships; the authors only provide indirect proof through the improved performance of downstream tasks. Additionally, the paper claims that the “model is easy to optimize,” but it does not provide a detailed analysis of the convergence speed and stability of the optimization process, nor does it offer comparative experiments to support this claim. As a result, the persuasiveness of this claim is weak.", "methods_and_evaluation_criteria": "The proposed method is rational to some extent, yet its evaluation criteria are limited. In addition to focusing on the improved performance of downstream tasks, the assessment of the hypergraph predictor should also consider multiple aspects of the hypergraph structure itself, such as its rationality, sparsity, and interpretability. However, the paper mainly focuses on the performance of downstream tasks and lacks rich indicators to evaluate the quality of the hypergraph structure itself. This single evaluation method may not fully reflect the effectiveness and superiority of the method.", "theoretical_claims": "The paper lacks sufficient theoretical analysis regarding the model's generalization ability and its applicability across different data distributions, which undermines the robustness of the model's theoretical foundation.", "experimental_designs_or_analyses": "The experimental design has some deficiencies, especially in the selection of datasets. Although both synthetic and real-world datasets are included, the diversity of the real-world datasets is insufficient, which limits the validation of the model's effectiveness on different types of data and tasks. This affects the comprehensive evaluation of the model's actual performance. Increasing the diversity of datasets is crucial for verifying the model's robustness and generalization ability.", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to the existing literature to some extent, but the elaboration is not deep enough. Hypergraph inference, as an emerging field, intersects with areas such as graph neural networks and structural prediction. However, when discussing related work, the authors mainly focus on recent studies and lack sufficient review of classical theories and methods. This makes the background introduction of the paper not comprehensive enough, making it difficult to fully demonstrate its innovativeness and significance.", "essential_references_not_discussed": "Some relevant works are not cited or discussed in the paper. For example, in the field of graph neural networks in recent years, there have been some works on the learning and prediction of dynamic graph structures. These methods share some similarities with hypergraph inference in terms of ideas, but they are not mentioned in the paper.", "other_strengths_and_weaknesses": "Strengths:The paper proposes a novel unsupervised hypergraph inference model that is compatible with existing hypergraph neural network architectures and can enhance the performance of downstream tasks. Additionally, the design of the model is innovative, especially the use of the k-subset sampling algorithm to generate discrete hypergraph structures, which provides a new approach for hypergraph inference.\nWeaknesses:In addition to the previously mentioned issues of insufficient evidence, limited evaluation criteria, and lack of theoretical analysis, the scalability of the model is also a concern. When dealing with large-scale datasets, the computational complexity of the hypergraph predictor may be high, which could affect the efficiency and practicality of the model.", "other_comments_or_suggestions": "None", "questions_for_authors": "1.How can the consistency between the inferred hypergraph structure and the true higher-order relationships of the hypergraph structure be verified on real-world datasets? Are there any more direct validation methods other than the improved performance of downstream tasks?\n2.In Section 3.1, the authors generate discrete hypergraph structures using a hypergraph predictor and a k-subset sampling algorithm. However, regarding the interpretability of the generated hypergraph structures, can the authors provide a more detailed analysis?\n3.In Section 4, the authors demonstrate the performance of SPHINX on several benchmark datasets. However, regarding the computational cost when dealing with large-scale graph data, do the authors have any plans to optimize the algorithm to enhance its scalability?\n4.In the experimental section, the authors primarily conducted experiments on synthetic datasets and a few common benchmark datasets. However, the diversity and complexity of these datasets are limited, which prevents a comprehensive validation of the method's effectiveness on different types of graph data and tasks.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F4OiUTgKzE", "reviewer": "Reviewer_BF7S", "summary": "The authors focus on unsupervised hypergraph inference. Three key desiderata are identified: applicability to a broad type of tasks, compatibility with any hypergraph process architecture, and ease of optimization. They propose SPHINX that adapts the slot attention for sequential hyperedge prediction, and is differentiable by leveraging contrained k-subset sampling. SPHINX is compatible with popular hypergraph neural networks. Experiments are conducted on synthetic and real-world datasets. Extensive results and analysis verify the superiority of SPHINX, and how its key components take effect.\n\n**Update after rebuttal**\n\nI have read the response from the authors. Since my original recommendation was to accept, I will maintain my recommendation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s comments and feedback. We thank the reviewer for pointing out Liao et al, which shares similarities with our work in sequential structure prediction and offers inspiration for future improvements. We will include a discussion in the paper.\n\n**Different hyperedge sizes**\n\nSPHINX allows hyperedges of different sizes. The argument k in the sampling algorithm does not affect the number of learnable parameters so it can vary among hyperedges. For simplicity and to reduce hyperparameter search space, we fix k across all hyperedges. However, if a more diverse hypergraph is needed, an array of k-values can be given as input.\n \n**Choosing M and k**\n\nAs mentioned in the paper, all experiments treats M and k as hyperparameters.\n\nDynamic hyperedge sizes: We agree that a dynamic k could enhance flexibility and is a promising direction for improvement. An alternative to hand-picking k is to select it according to the probability distribution: defining k as the number of nodes above a probability threshold or the rank with a significant gap in the distribution. Though still non-differentiable, this removes the need for predefined hyperedge sizes.\n\nSensitivity to the number of hyperedges M: Having a fixed maximum number of hyperedges is a limitation that we share with most hypergraph predictors in the literature. The experiments in Fig 5 examine how this impacts performance in the synthetic setup. As expected, a too small M causes a drop in performance while an M that is larger than the oracle(2) does not affect the performance. To understand this behaviour, we measured the average number of unique hyperedges. Results show that, when equipped with more slots than necessary, the model learns a form of redundancy (predicting the same hyperedge multiple times) instead of hallucinating fake relations.\n|Slots|Unique Hedges|MSE|\n|-|-|-|\n|**1** |1.00|0.00007|\n|**2**|1.96|0.00002|\n|**3**|2.15|0.000017|\n|**4**|2.14|0.000007|\n\nThat said, we agree that developing a fully dynamic model with adaptive k and M is an important future direction.\n\n**Insights on the inferred hypergraph**\n\t\nEvaluating the accuracy of predicted latent hypergraphs in real-world data is a critical but challenging problem, that remains an open problem. Our datasets lack annotations for higher-order structures, and even if they would have existed, there’s no guarantee they would be optimal for the task.\n\nHowever, to understand the type of hypergraph predicted by our model in the real-world datasets, we analyze the NBA dataset, an inductive dataset that is easier to visualize and interpret. For a model with 6 hyperedges and 4 nodes per hyperedge:\n- the avg node degree for the predicted hypergraphs are [1.97, 1.98, 1.99, 1.99, 1.98, 1.95, 1.96, 1.96, 1.96, 1.95, 4.29]. The first 10 nodes correspond to players- model focuses uniformly on all of them; while the last node represents the ball- the model learns to include the ball in most hyperedges. Thus the predicted structures are star-like hypergraphs, aligning with our intuition that player movement is highly influenced by the ball’s position. \n- the avg percentage of duplicated hyperedges across examples is 2.74%. This shows a high diversity in our predictions, confirming that the model captures not just the most likely connections but also a scene-specific structure.\n\n**Description of  k-subset sampling**\n\nTo maintain readability, we initially omitted certain technical details, such as the formulation of k-sampling. However, we agree that including this information will make the paper more self-contained and reproducible. We will add a section in the appendix.\n\n**Running time**\n\nFollowing your suggestions, we measured time per iteration on NBA(batch size 128, 11 nodes) and ModelNet(12311 nodes) using a Quadro RTX 8000 GPU. While ensuring architectural comparability, our code is not optimized for large-scale data. More engineering improvements can further enhance scalability.\n||ModelNet| | |NBA| | |\n|-|-|-|-|-|-|-|\n||SPHINX |TDHNN||SPHINX|TDHNN|GroupNET|\n|**Training Time (sec)**|0.32 |0.77||0.018|0.21|0.071|\n|**Infer Time (sec)**|0.26|0.76||0.030 |0.22|0.030|\n\n**Order of sequential prediction for hyperedges**\n\nWe thank the reviewer for pointing this out. Since we do not have supervision at the hypergraph level, we believe order ambiguity is less pronounced than in graph-generation tasks (e.g., GRAN). But, sequential prediction still introduces equivalence classes in the latent space, where any predicted orders yield the same hypergraph, potentially causing model confusion.\n\nTo address this, we initialize slot attention deterministically, using the same random sequence for all examples, allowing the model to learn a canonical order if one exists. However, we agree that this is a naive way of imposing an order and we think that there is room for improvement in that regard. We thank the reviewer for identifying the GRAN paper which might offer inspiration for avoiding order-ambiguity.", "claims_and_evidence": "The claim in contributions is supported by experimental results, including accurate hypergraph discovery and how it benefits downstream tasks.", "methods_and_evaluation_criteria": "1. SPHINX is designed under the guidance of three desiderata pointed out by the authors. SPHINX is well-motivated and reasonably designed.\n\n2. Clustering-based hyperedge discovery and k-subset sampling to allow backpropagation are reasonable for end-to-end hypergraph inference.\n\n3. Designing particle simulation to verify the effectiveness of SPHINX on hypergraph prediction is reasonable because the ground truth are known.\n\n4. The transductive and inductive settings for hypergraph inference are widely accepted.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The experimental design is rather comprehensive.\n1. Experiments are conducted on both synthetic datasets and real-world datasets. Personally, I think it is creative to design the particle simulation to verify the accuracy of hypergraph discovery.\n2. SPHINX is compared with representative baselines and state-of-the-art methods\n3. Hypergraph inference is studied under both the inductive and transductive settings.\n4. Various ablation studies are conducted to validate the key features of SPHINX, e.g., sequential prediction, k-sampling, etc.", "relation_to_broader_scientific_literature": "This paper is related to structural inference, higher-order network learning, hypergraph neural networks, etc.", "essential_references_not_discussed": "A previous that uses sequential prediction for graph generation is not reviewed.\n\nEfficient Graph Generation with Graph Recurrent Attention Networks. In NeurIPS, 2019.", "other_strengths_and_weaknesses": "Strengths:\nS1. SPHINX is technically solid and empirically significant under variant experimental settings.\n\nS2. It is innovative to apply the slot attention in computer vision to hypergraph clustering.\n\nWeaknesses:\n\nW1. SPHINX may not be general enough to infer arbitrarily structured hypergraphs. Please see Q1 for details.", "other_comments_or_suggestions": "Personally, I think more technical descriptions of k-subset sampling, a key technique in SPHINX, should be added, either in the main text or the appendices.", "questions_for_authors": "Q1. I have several questions on hypergraph inference from the algorithmic perspective.\n\nQ2. How to determine the number of total hyperedges M, and the size of each hyperedge k, i.e., the number of nodes it contains. Are they specified before hypergraph inference? How to decide the best M and k? Specifically, M and the largest k reflect the intrinsic order of higher-order interaction. Thus, I believe it is crucial for understanding the complexity of the interaction.\n\nQ3. Does your algorithm allow hyperedges of different sizes?  Besides, I note that the authors analyze the computational complexity in Appendix C. Is it possible to report the running time?\n\nQ4. How do you determine the order of sequential prediction for hyperedges? Will that affect the performance? \n\nQ5. Can you analyze the inferred hypergraphs on real-world datasets? It will help the readers understand the meaning the hyperedges and better justify the contributions of ``adding a new layer of interpretability to the model''. The authors may consider reporting some statistics of the hypergraphs (e.g., number of hyperedges and the largest size of hyperedges) and conducting some case studies.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gLImvLN5AC", "reviewer": "Reviewer_HCWJ", "summary": "SPHINX proposes an unsupervised framework for latent hypergraph inference that models higher-order interactions directly from point-wise data. The method employs a sequential slot attention mechanism to predict hyperedge probabilities and uses differentiable k-subset sampling to convert these probabilities into a discrete hypergraph structure. This latent structure is then integrated into any hypergraph neural network, enabling improved performance on both inductive and transductive tasks, as demonstrated through extensive experiments and ablation studies.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s positive feedback on our work. Below, we address the key points raised and we will incorporate all suggestions into the final version of the paper.\n\n**Selecting the number of hyperedges M**\n\nHaving a fixed maximum number of hyperedges is a limitation that we are sharing with most of the hypergraph predictor methods in the literature  and we agree with the reviewer that having a fully dynamic model, allowing dynamic number of hyperedges, is an important direction.\n\nThe experiments presented in the Appendix (Fig 5)  are designed to understand to what extent this affects the performance of the model on the synthetic setup (where we know what is the real number of hyperedges needed). The results show that, as expected, having a too small M causes a drop in performance while having an M that is larger than the golden standard does not affect the performance.  \nTo better understad this behaviour, we measured the average number of distinct hyperedges predicted when providing more slots than required. The results are as follow: \n\n| Slots      | Unique Hyperedges | MSE       |\n|------------|------------------|-----------|\n| **1 slot**  | 1.00             | 0.00007   |\n| **2 slots** | 1.96             | 0.00002   |\n| **3 slots** | 2.15             | 0.000017  |\n| **4 slots** | 2.14             | 0.000007  |\n\nWe believe that this is a very interesting result, as it shows that when equipped with more slots than necessary the model learns some form of redundancy (by predicting the same hyperedge multiple times) instead of hallucinating fake relations.", "claims_and_evidence": "The paper’s claims are supported by clear and convincing empirical evidence. Extensive experiments show improvements in hypergraph accuracy and downstream task performance, effectively validate the approach.", "methods_and_evaluation_criteria": "The proposed methods—sequential slot attention for hyperedge inference and differentiable k-subset sampling for discretization—are well-motivated and appropriate for the challenge of inferring latent hypergraph structures. I especially love the fact that SPHINX can be used with any hypergraph neural network decoder and eliminating the need for heavy optimisation tricks.", "theoretical_claims": "NA", "experimental_designs_or_analyses": "The experimental design is robust and comprehensive.", "relation_to_broader_scientific_literature": "The pipeline could be inspiring for other graph structure learning methods.", "essential_references_not_discussed": "The paper cites most of the key works in hypergraph learning and unsupervised relational inference.", "other_strengths_and_weaknesses": "I think the hyperparameter M is a really strong prior and needs to be carefully tuned. It would be better if there is some way to select M (or heuristically set an appropriate M).", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel model, i.e., SPHINX, designed to infer latent hypergraph structures in an unsupervised manner solely from task-dependent signals. All four reviewers are positive about this paper with the overall ratings of two accept and two weak accept. The reviewers are generally satisfied with the rebuttal. The AC agrees with the reviewers and recommends acceptance. Please take the reviewers' detailed comments and the rebuttal into consideration when preparing the final version.
Decision: Accept (poster)