SPHINX: Structural Prediction using Hypergraph Inference Network

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.

Selecting the number of hyperedges M

Having 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.

The 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.
To better understad this behaviour, we measured the average number of distinct hyperedges predicted when providing more slots than required. The results are as follow:

We 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.

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.

Different hyperedge sizes

SPHINX 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.

Choosing M and k

As mentioned in the paper, all experiments treats M and k as hyperparameters.

Dynamic 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.

Sensitivity 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.

That said, we agree that developing a fully dynamic model with adaptive k and M is an important future direction.

Insights on the inferred hypergraph

Evaluating 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.

However, 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:

• 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.
• 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.

Description of k-subset sampling

To 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.

Running time

Following 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.

Order of sequential prediction for hyperedges

We 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.

To 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.

We sincerely appreciate your detailed review and valuable feedback on our paper. We would like to address your concerns and questions.

Hypergraph evaluation for real-world datasets

Quantitatively 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.

However, 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:

• 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]. 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.
• 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.

Regarding 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).

Model is easy to optimize without analysis

As 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.

Missing review of classical methods and dynamic graph structures

We 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.

In 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.

Analysis of the model’s interpretability

The 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.

Scalability for large-scale data

For 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.

Following 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.

While our model's memory requirements increase with dataset size, it remains significantly more efficient than previous models in the literature.

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.

Fixed hyperedge size

We 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

We 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.

While these adaptations are straightforward, they were not included in the current study. Exploring fully learnable hyperedge cardinality is an interesting future direction..

Predefined Hyperedge Count / Sensitivity w.r.t. M

Having a fixed maximum number of hyperedges is indeed a limitation that we are sharing with most of the hypergraph predictor methods in the literature.

The 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.

To 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:

We 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.

Computational efficiency and memory usage on large-scale data

For 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. The 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.

Following 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.

While our model's memory requirements increase with dataset size, it remains significantly more efficient than previous models in the literature.

Additional related work on dynamic hypergraphs and k-subset sampling algorithms

We 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.

We 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.