Link Prediction with Relational Hypergraphs

Authors: Xingyue Huang, Miguel Romero Orth, Pablo Barcelo, Michael M. Bronstein, Ismail Ilkan Ceylan
Primary area: learning on graphs and other geometries & topologies
Keywords: link prediction, relational hypergraphs, expressivity study

Abstract:
Link prediction with knowledge graphs has been thoroughly studied in graph machine learning, leading to a rich landscape of graph neural network architectures with successful applications. 
Nonetheless, it remains challenging to transfer the success of these architectures to link prediction with *relational hypergraphs*, where the task is over *$k$-ary relations*, substantially harder than link prediction on knowledge graphs with binary relations only.
In this paper, we propose a framework for link prediction with relational hypergraphs, empowering applications of graph neural networks on *fully relational* structures. Theoretically, we conduct a thorough analysis of the expressive power of the resulting model architectures via corresponding relational Weisfeiler-Leman algorithms and also via logical expressiveness.  Empirically, we validate the power of the proposed model architectures on various relational hypergraph benchmarks. The resulting model architectures substantially outperform every baseline for inductive link prediction, and also lead to state-of-the-art results for transductive link prediction.

Decision: reject
Reviewer scores: 6, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730010731085

thread_type:
official_review

<thread_object>
creator: reviewer_dikx

<content>
summary:
This work proposes HCNet, which extends state-of-the-art NBFNet and C-MPNN of conventional graph for link prediction to relational hypergraphs for hyper-relation predictions. It first follows the schema of conventional graph neural network works, defines the invariance under relational hypergraph and proves the expressivity of their proposal using proposed WL test for relational hypergraph. Then, it follows the schema of knowledge graph works, proves that the logical reasoning ability of HCNet is same as grade model logic on hypergraph. Besides, this work achieves better empirical results on relational hypergraph benchmarks.

strengths:
- This works have concrete theoretical justifications on both graph representation and knowledege graph domains including WL test (for relational hypergraph) and power of logical reasoning.
- The empirical result looks pretty good in compare to related works on relational hypergraph baselines.

weaknesses:
- Although this work made enough refinement to adpat NBFNet and C-MPNN design onto relational hypergraph, there isn't significiant novelty introduced in the refinement: they are simply directly replace the concepts from conventional graph to relational hypergraph.
- For logical reasoning, I believe it should focus more on explainability to people, but the concept of graded modal logic for hypergraph (the definition and examples) in this paper is too abstract for people to understand their power. I think more evidence of HGML should be provided (in appendix), e.g., is it able to represent all logics or answer all logical queries on relational hypergraph? If not, what's the limitation?
- Since this is a neural network work and link prediction work (where negative sampling is necessary), they will be a lot randomness in experiments, thus it is essential to provide confidence interval at least to your works (I understand that some baselines do not have confidence interval).

questions:
- I am not familiar with the background of link prediction on relational hypergraph, thus I have questions to the necessity of this problem: It seems that the hyper relation prediction can be decomposed into prediction over a relational path or subgraph, and all three benchark you used seems to built from conventional knowledege graph, thus I am wondering is there a real-world dataset or task where only relational hypergraph methods can handle, and can not be decomposed into conventional relational graph methods?
- Since your method is transductive on relations, can we simply treat each relation as an independent node, and use the hyper relation position as edge attribute between a node and the relation node (e.g., $r(u_k)$ becomes $u_k \overset{k}{\leftrightarrow} r$), thus we can convert this task into a classifition task over multiple edges on conventional graph? Is there any baselines corresponding to this idea?
- Is the order essential in hyper relations? I think it is possible to permute some node positions while not hurts the hyper relation? If so, isn't your definition too strict?
- I think predicting the relation also falls into link prediction catalog, but your link prediciton only focuses on nodes, is it defined only for this work?
- In refinement, I think you want to define $\xi$ is more expressive than $\xi'$ (can distinguish more cases), thus isn't $\xi' \prec \xi$ better than $\xi \prec \xi'$ in representing which one is more expressive?
- How is your method runtime in real-world training and inference? NBFNet is already expensive since the graph convolution has to be redo if the query change, and in your case, hyperedge may introduce exponential increase on the amount of neighbors.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730713086867

thread_type:
official_review

<thread_object>
creator: reviewer_mmja

<content>
summary:
The paper introduces HC-MPNNs, a novel GNN architecture for link prediction on relational hypergraphs, achieving state-of-the-art results in both inductive and transductive tasks. While highly expressive, the model faces scalability challenges due to its computational complexity.

strengths:
- **Innovative Approach**: The paper introduces Hypergraph Conditional Message Passing Neural Networks (HC-MPNNs), which generalize existing GNN architectures and target the complex task of k-ary link prediction on relational hypergraphs, moving beyond traditional binary link prediction tasks.
- **Theoretical Rigor**: The authors provide a detailed analysis of HC-MPNNs' expressive power through Weisfeiler-Leman tests and logical expressiveness, which significantly adds to the theoretical foundation of GNNs on hypergraphs.
- **State-of-the-Art Performance**: Empirical results demonstrate that HC-MPNNs outperform existing models for both inductive and transductive link prediction tasks across multiple datasets, showcasing substantial improvements.

weaknesses:
- **Computational Complexity**: The paper acknowledges that the proposed HC-MPNNs may be computationally intensive, particularly for large hypergraphs. An in-depth analysis of the computational costs compared to baseline models is needed to assess scalability better.
- **Limited Scope**: The model is focused solely on link prediction. Exploring its applicability to other tasks, such as node classification or hypergraph-based query answering, would provide more versatility and impact.
- **Assumptions on Data Structure**: The approach assumes that hypergraph structures are available and complete, which may not always be feasible in real-world scenarios. The limitations of applying this method to noisy or partially observed hypergraphs are not discussed.

questions:
- **Expressiveness Limitations**: Could the authors provide more details on situations or graph structures where the expressive power of HC-MPNNs might fall short, even with the enhanced encoding?
- **Impact of Hypergraph Structure**: How does the structure or density of a hypergraph affect the model’s performance, especially in cases of sparse or highly connected hypergraphs?
- **Generalization to Noisy Data**: How robust is HC-MPNN to noisy or incomplete hypergraph data, and are there mechanisms in place to handle such cases?
- **Positional Encoding Variants**: The ablation studies show sinusoidal positional encoding as the best choice. Could the authors elaborate on why this is effective in hypergraph contexts compared to other embeddings?
- **Use of Meta-Paths**: Given that meta-paths are important structures in relational (non-hypergraph) graphs [1, 2, 3], could there be advantages to incorporating them in hypergraph contexts?
- **Scalability of the Model**: Is the model feasible to apply in very large-scale hypergraphs (e.g., millions of nodes)? 

[1] Seongjun, Y. et al., Graph Transformer Networks: Learning meta-path graphs to improve GNNs, 2022

[2] Ferrini, F. et al., Meta-Path Learning for Multi-relational Graph Neural Networks, LOG 2023

[3]Fu, Xinyu, et al. "Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding." Proceedings of the web conference 2020. 2020.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721415903

thread_type:
official_review

<thread_object>
creator: reviewer_tzjo

<content>
summary:
The authors first give an understanding of the expressive power and limitations of HR-MPNNs and propose the HC-MPNN structure based on HR-MPNN. Compared with current HR-MPNN models, the HC-MPNN structured model HCNet carries out a novel query-specific node initialization method. With the Weisfeiler-Leman test, the author proves that this model can better model isomorphic nodes since it maintains a better expressiveness than the HR-MPNN structured models in the relational hypergraphs.

strengths:
S1. Clear and well-organized presentation of the whole paper.

S2. Solid proof of the theoretical expressiveness of the proposed method.

S3. Available code.

S4. Transductive experiments have been added.

weaknesses:
Unfortunately for the authors, I am the reviewer who held a negative opinion on this paper for NeurIPS 2024. Here, I summarize my previous negative feedback:

**Major Concerns:**

C1. The theoretical proof in this paper is unrelated to the inductive setting. Previously, I hoped the authors would compare more transductive settings. This time, **Table 2 has addressed this concern quite well**. Thus, I decided to raise my score.

C2. I previously argued that hyper-relational graphs and relational hypergraphs can be converted with small tricks, which is why many prior studies conducted experiments on datasets like WD50K, WIKIPEOPLE, JF17K, and FBAuto. Therefore, I also suggested that the authors consider experimenting on other hyper-relational graphs. However, the authors hold a different view, and the explanation provided in lines 145-153 is not sufficient to alleviate my concern. Thus, I will retain my suggestion for this submission and discuss it further with other reviewers.

**Minor Concerns:**

C3. Many of the methods presented in Table 1 were published in or before 2020, which may imply that the inductive setting is not currently a major research focus. The authors may need to emphasize the significance of the inductive setting more in the paper.

questions:
I would like the authors to continue discussing the disagreement over C2, explaining why they insist that relational hypergraphs and hyper-relational graphs have irreconcilable differences. In my view, even if their structures are not identical, small modifications could allow format conversion. The benefits of doing so include:

	1.	Making the proposed method more generalized and applicable to a broader range of scenarios.
	2.	Aligning with many previous studies in the field.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731169072902

thread_type:
official_review

<thread_object>
creator: reviewer_t9zr

<content>
summary:
This paper proposes a new method for link prediction in relational hypergraphs, where the task focuses on k-ary relations. It first investigates the expressive power of existing GNNs for relational hypergraphs, and then introduces the hypergraph conditional message passing neural network (HC-MPNN) by utilizing and extending the techniques from conditional message passing neural networks (C-MPNNs) (Huang et al., 2023). The HC-MPNN is further extended to an inductive setting, and show good experimental results.

strengths:
1. The paper is written in a good structure. Although the definition of the relational hypergraph is a little bit complex; the descriptions in the paper is not difficult to understand. The organization of the paper is good. From the theoretic analysis to model improvement, the techniques are quite clear.

2. Extending the C-MPNN and HR-MPNN to HC-MPNN is technically sound. And the extension to inductive link prediction is interesting.

3. Both theoretic analysis and experiments are comprehensive. It has with both inductive and transductive settings, and the analysis of the initialization and positional encoding is also useful.

weaknesses:
1. First, I have a concern about the practicality of the method. From my understanding, the relational hyperedge is just like a sentence, and it has fixed directions and positions for entities. So, why do not people just use Transformers for NLP by regarding the relational hyperedge as a sentence? And the query based approach is just like a BERT-based model? I do not see much benefit from modeling it as a hypergraph. I am actually curious to see the results of BERT on the same datasets if possible. 

2. Second, although the paper is technically sound and the analysis is complete/rigorious; but every step in the model is not surprising and a little bit trivial. Without the analysis part, the HC-MPNN is like just a migration of C-MPNN to hypergraphs. The inductive link prediction part is more interesting. 

3. I do not fully understand the training. Since the message passing is query dependent, there must be a lot of queries in the training data. How do you select such queries for training? And for each query, the node representation is different, does not it increase the computational complexity a lot?

questions:
1. Does a relational hyperedge have a fixed number of entities? For example, can we have r(e1, e2) and r(e1, e2, e3) at the same time? 
2. How to train the model with queries?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731956568045

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global response

comment:
We thank the reviewers for their comments. We respond to each concern in detail in our individual responses, and we provide a summary of our rebuttal based on the feedback from the reviewers:
- **Additional Baseline.**  We add an additional baseline model BERT as an instance of transductive embedding methods (**Reviewer t9zR**).
- **Additional Dataset.** We experimented with an additional transductive dataset  (JF17K) and compared our model with the baseline model including models operating on hyper-relational knowledge graphs. (**Reviewer tZJo**).
- **Extended discussions on Design Choices.** We highlight the delicate design choices behind HC-MPNNs which are crucial in applying conditional message passing on relational hypergraphs. (**Reviewer t9zR, Reviewer dikX**)
- **Implications of Expressiveness Results.** In addition to quantifying the precise expressive power of HC-MPNNs, we also elaborate on the induced expressiveness limitations (**Reviewer mmja, Reviewer dikX**).
- **Scalability.**  We discuss the scalability of HCNets and provide a strategy to apply HCNets on much larger graphs. (**Reviewer mmja, Reviewer dikX**)

We hope that our answers address your concerns, and we are looking forward to a fruitful discussion period.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732453781777

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank the reviewers for taking their time to review our paper. We have now integrated all the feedback and additional findings from the rebuttal to the paper (highlighted in blue). We would deeply appreciate any additional feedback and looking forward to discuss further.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This submission violated the anonymity policy. In the provided link (https://anonymous.4open.science/r/HCNet/README.md), when clicking the blue-colored text, Link Prediction with Relational Hypergraphs, the arXiv version of the paper is shown, which reveals all authors' information: https://arxiv.org/abs/2402.04062

This submission should have been desk-rejected. It was difficult to expect a redirection to the arXiv paper, so this clear violation was not found during the desk-rejecting period.

In addition to some of the reviewers' remaining concerns, I also found some critical issues based on my own reading:

1. **Misunderstandings of the relationship between relational hypergraphs and n-ary relational graphs.**\
The authors argue that "link prediction with relational hypergraphs is a more general problem setup" than that with n-ary relational graphs. However, I'm afraid I have to disagree with it. While a relational hyperedge can be transformed into an n-ary relational fact without loss of information, the reverse transformation is not always lossless. Given a hyperedge $r(u_1,u_2,u_3, u_4)$, it can be transformed into a 4-ary relational fact $\\{r_1:u_1, r_2:u_2, r_3:u_3, r_4:u_4\\}$ without loss of information. However, when we transform $\\{r_1:u_1, r_2:u_2\\}$ and $\\{r_1:u_3, r_2:u_4, r_3:u_5\\}$ into hyperedges, they are transformed into $r’_1(u_1, u_2)$ and $r’_2(u_3,u_4,u_5)$. In this conversion, the information loss occurs: the facts that $u_1$ and $u_3$ are both involved in $r_1$ and that $u_2$ and $u_4$ are both involved in $r_2$ are lost. Therefore, n-ary relational graphs are a more general form than relational hypergraphs.

2. **Mismatch of the concept of the relational hypergraph and benchmark datasets**\
The authors claim to "opt out datasets of hyper-relational knowledge graphs" and to "focus only on the datasets designed for relational hypergraphs". However, the datasets the authors used are extracted from knowledge bases such as Wikidata or Freebase, none of which are originally relational hypergraphs but in the form of n-ary relational graphs or hyper-relational knowledge graphs. While these datasets may have been adopted for evaluating methods targeting relational hypergraphs, their original structures do not perfectly align with the definition of relational hypergraphs. This mismatch renders these datasets unsuitable for evaluating methods designed specifically for relational hypergraphs. The authors should instead conduct experiments on datasets extracted from relational hypergraphs.

3. **Misunderstanding of the literature**\
The authors stated, "We also highlight the evaluation differences as experiments on hyper-relational knowledge graphs only corrupt entities in the main triplets, whereas, in link prediction with relational hypergraphs setting, all entities mentioned at all positions are corrupted". However, this claim is inaccurate. For example, GRAN [1], a model for hyper-relational knowledge graphs, includes an evaluation setting where all entities mentioned at all positions can be corrupted.

4. **Missing literature**\
The manuscript does not include recent baseline methods, such as HJE [2] (Published on February 13, 2024). HJE demonstrates superior performance compared to the proposed method. For instance, regarding MRR on the WikiPeople dataset, HCNet achieves 0.421, whereas HJE achieves 0.450.

5. **Incorrectly reporting baseline's performance**\
This manuscript incorrectly reports ReAlE's performance [3]. For example, on the FB-AUTO dataset, the original ReAlE paper reports an MRR of 0.873, whereas this manuscript reports it as 0.861.

6. **Misunderstanding on JF17K**\
In the rebuttal, the authors included experiments on the JF17K dataset to compare with baseline methods designed for hyper-relational knowledge graphs. However, the JF17K dataset is an n-ary relational graph dataset, not a hyper-relational knowledge graph dataset in its original form. Thus, the authors should instead conduct experiments on datasets such as WD50K to facilitate a valid comparison with baseline methods targeting hyper-relational knowledge graphs.

[1] Wang et al., 2021. Link Prediction on N-ary Relational Facts: A Graph-based Approach. ACL Findings.\
[2] Li et al., 2024. HJE: Joint Convolutional Representation Learning for Knowledge Hypergraph Completion. TKDE.\
[3] Fatemi et al., 2023. Knowledge Hypergraph Embedding Meets Relational Algebra. JMLR.