Link Prediction with Relational Hypergraphs
Authors: Xingyue Huang
Miguel Romero Orth
Pablo Barcelo
Michael M. Bronstein
Ismail Ilkan Ceylan
Venue: Accepted by TMLR ()

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 inductive 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 competitive results for transductive link prediction.

Published in Transactions on Machine Learning Research (05/2025)
Link Prediction with Relational Hypergraphs
Xingyue Huang
cinggnc.tuunggees.rrccm
Deportment of Computer Science, University of Oxford, UK
Miguel Romero
mgromero@uc.cd
Department of Computer Science, Universidad Cotólica de Chile, Chile
Pablo Barccló
pbarcelo Cucc. cl
Institute for Mothematics and Comp. Engineering, Universidad Católica de Chile IMED, Chile
Michael M. Bronstein
michael, brccbuel.bommteeiBBesroo.cc ow..seeeiiissss...c......
Department of Computer Science, University of Onford, UK
ismail Îlkan Ceylan
ismail. crrnalllcyylnnecsoor.comm
Department of Computer Science, University of Ozford, UK
Reviewed on OpenReview: https: // //tp:///ppeeee optp///pppee.....omm/// net/ formm? id= SBfee44aHHi1
Abstract
Link prediction with knowledge graphs has been thoroughly studied in graph machine learn- ing, leading to a rich landscape graph neural network architectures with successful appli- cations. Nonetheless, it remains challenging to transfer the success of these architectures to inductive link prediction with relational hypergraphs, where the task is over k-ary relations, substantially harder than link prediction knowledge graphs with binary relations only. In this paper, propose framework for link prediction with relational hypergraphs, empow- ering applications of graph neural networks on fully relational structurcs. Theoretically, we conduct a thorough analysis of the expressive power of the resulting model archilectures via corresponding relational Weisfeiler- Leman algorithms and logical expressiveness. Empiri- cally, we validate the power of the proposed architectures on various relational hypergraph benchmarks. The resulting model architectures substantially outperform every baseline for inductive link prediction and also lead to competitive results for transductive link prediction.
Introduction
Knowledge graphs consist of facts (or, edges) represent-
Hawking
Oxford
ing different relations between pairs of nodes. Knowl-
edge graphs are inherently incomplete (Ji et. al.
2020
Wang et al. 2017) which motivated a large liter--
Nobel
ture on link prediction with knowledge graphs (Wang
StudyDegree
Awarded
et al. 2014 Schlichtkrull et al., 2018 Sun et al. 2019
Teru al., 2020 Vashishth
al. 2020: et al.
2021a; Zhu al. 2021). This task amounts pre-
dicting missing facts in the knowledge graph and has led to rich landscape of graph neural network archi- tectures (Schlichtkrull et al. 2018. Teru et al.) 2020 Vashishth el al.) 2020 Zhu el al. 2021). Our under- standing of these architectures is supported by theoret- ical studics quantifying their expressive power (Barccló
BA
Physics
Figure 1: A relational hypergraph over the relations StudyDegree and Awarded. The facts StudyDegree (Hawking, Oxford, Physics, BA) and Swarded(Physice Nobel, Oxford) are ordered hy- peredges, where the order of entities in each fact denoted by dashed arrows.
et al. Zhang al. 2021 Huang al. 2023
al.
2022
Qiu
2024

---

Published in Transactions on Machine Learning Research (05/2025)
In this work, we are interested in link prediction on fully relational data, where every relation is between k nodes, for any relation-specific choice of k. Relational data can encode rich relationships between entities; e.g., consider a relationship between four entities: "Hawking went to Oxford to study Physics and received a BA degrec". This can be represented with a fact SordyDDeereeHHawkingg Oxford, Physics, BA). Clearly, relational data can be represented via relational hypergraphs, where each ordered, relational lepperedge the hypergraph corresponds to a relational fact (see Figure [
Motivation. Given the prevalence of relational data, link prediction with relational hypergraphs has been widely studied in the context of shallow embedding models (Wen et al.) 2016 Abboud et al 2020; Fatemi ct al.] 2020; 2023), where the idca is to generalize knowledge graph embodding methods to rela- tional hypergraphs. The key limitation of these approaches is that they are all transductive: they cannot be directly used to make predictions between nodes that are not seen during training. The same limi- tation has motivated the development of graph neural network architectures for inductive link prediction on knowlodge graphs enabling for predictions between nodes that are not seen during training Teru
et al. 2020
which eventually led to very strong architectures such as NBFNets (Zhu et al. 2021 In the same spirit, graph neural networks have been extended for inductive link prodiction on relational hypergraphs (Yadati 2020: Zhou et al. 2023). but these approaches do not enjoy the same level of success. This can be attributed to multiple, related fac- tors. In essence, link prediction with relational hypergraphs is a k-ary task (for varying depending on the relation), which is much more challenging than binary prediction task and re- quircs dedicated approaches. On the other hand, existing proposals are simple extensions of relational graph neural networks (such as RGCNs [Shlichtkrull et al., 2018)), ), which cannot adequately cap- ture k-ary tasks. In fact, these architectures are unary encoders that are used for k-ary predictions, which known to a fun- damental limitation (Zhang et al.] 2021 Huang el al.] 2023). To make these points concrete, let us consider the example shown in Figure 2 In this example, regardless of the choice of the unary encoder, it is not possible to distinguish between the query facts ruu, w, t) and r(u, u, t), because the nodes w and v are isomorphic in the hypergraph. However, an appropriate ternary encoder can easily differentiate these facts using the information that the distance between the nodes u and w differs from the distance between the nodes u and v. These limitations along with a lack of an established theory motivates our study.
W
v
Figure Unary encoders cannot dis- tinguish the query facts r(u, v,t) and r(u, w. t), drawn in green.
Approach. We first investigate the expressive power of existing graph neural networks proposed for rela- tional hypergraphs - such as G-MPNNs (Yadati 2020) and RD-MPNNs (Zhou et al.) 2023) to rigor- ously identify their limitations. This is achieved by studying the framework of hypergraph relational message passing neurul nelworks (HR-MPNNs) which subsumes these architectures. To address the limitations of HR-MPNNs, we introduce hypergraph conditional message passing neural networks (HC-MPNNs) as a frame- work for inductive link prediction inspired by the conditional message passing paradigm studied for knowledge graphs (Zhu et al.] 2021 Huang et al. 2023). We conduct a systematic expressiveness study showing that HC-MPNNs compute richer properties of nodes dependent k other nodes when compared to HR-MPNNs.
Specifically, our study for expressive power answers the following questions:
1. Which modes can be distinguished by on archilecture? To answer this question, we generalize existing results given for graph neural networks knowledge graphs (Barceló et al. 2022 Huang et al. 2023) using Weisfeler-Leman algorithms designated for relational hypergraphs.
What properties of nodes can be uniformly expressed by an architecture? To answer this question, we investigate logical expressiveness which situates the class of node properties that can be expressed by architecture within an appropriate logical fragment.
2

---

Published in Transactions on Machine Learning Research (05/2025)
Contributions. Our main contributions can be summarized as follows:
We rigorously identify the expressive power and limitations of HR-MPNNs that encompass most of the existing architectures for link prediction with relational hypergraphs (Section g.
We introduce the novel framework of HC-MPNNs, which includes more expressive architectures, such as HCNets, and addresses the core limitations of HR-MPNNs (Section 5
We present a detailed empirical analysis to validate our theoretical findings (Section G Experiments for inductive and transductive link prediction with relational hypergraphs show that a simple HC-MPNNs architecture surpasses all existing basclines leading to competitive results. Our ablation studics on differ- ent model components justify the importance of our model design choices. We supplement the real-world experiments with a synthetic experiment inspired by the example from Figure 2to to validate the expressive power of HC-MPNNs (Section 6.5
2 Related work
Knowledge graphs. Link prediction with knowledge graphs has been studied extensively in the literature. Early literature dominated by knowledge graph embedding models including TransE (Bordes et al. 2013) RotatE (Sun et al. 2019), ComplEx (Trouillon et al.) 2016), TuckER (Balazevic et al.) 2019), and BoxE (Abboud et al. 2020), which are all restricted to the transductive regime. In the space of graph neural networks, RGCN (Schlichtkrull et al. 2018) and CompGCN (Vashishth et al., 2020g emerged as architectures extending standard message passing neural networks (Gilmer et al. 2017 7 to knowledge graphs using a relational message passing scheme. GralL (Teru et al.) 2020) is the first architecture explicitly designed
to operate in the inductive regime, but it suffers from high computational complexity. [hhu et al. (2021) proposed NBFNets as an archilecture that subsumes previous methods such as NeuralLP (Yang el. al., 2017)
and DRUM (Sadeghian et al. 2019). NBFNets perform strongly and have better computational complexity thanks to their high parallelizability (Zhu et al. 2021). Recently, AeNt (Zhu et al.
2023 is proposed to scale
NBFNets further with the usage of a neural priority function. NBFNets are shown to fall under the framework of conditional message passing neural networks (C-MPNNs) (Huang et al.) 2023) as they compute node representations "conditioned" pairwise on other node representations, making these architectures suitable for link prediction tasks and explaining their superior performance. The success of conditional message passing on knowledge graphs serves as a motivation for our work on relational hypergraphs.
Relational hypergraphs. Link prediction with relational hypergraphs has been widely studied in the context of shallow embedding models (Wen et al., 2016 Abboud et al. |020 Fatemi et al. 2020 2023). To score facts of the form r(u,,... , ux), some methods extend the scoring function (i.e., decoder) of existing knowledge graph embedding mothods to consider multiple entities. For example, m-TransH (Wen et al., 2016) is an extension of TransH (Wang et al. 2014] designed to handle multiple entities jointly. Similarly, GETD (Liu et al., 2020) builds on the bilinear embedding method TuckER (Balazevic et al.] 2019) to handle higher-arity relations. Fatemi et al. (2020) proposed HSimplE and HypE that disentangle the position and relation embedding. BoxE (Abboud et al. 2020 is an embedding model that encodes cach relation using box embeddings, and naturally applies to k-ary relations while achieving strong results on transductive benchmarks. Fatemi et al. (2023) explores the connection between relational algebra and relational hyper- graph embeddings and proposes ReAlE. Recently, Li et al. (0024a) proposed HJE that jointly considers 3D convolution and relation-awan aware 2D convolution, whereas Li et al. (2024b) utilizes 3D circular convolutional neural network and the alternate mask stack strategy to enhance feature extraction. In the space of graph neural networks, Feng et al. (2018) and Yadati et al. (2019) leverage message-passing methods on undi- rected hypergraphs. Subsequently, StarE (Galkin et al. 2020 was introduced as message- passing neural network specifically designed for hyper-relationll knowledge graphs, providing different approach to rep- resent high-arity facts, while Ali et al. (2021) further studied different inductive settings for hyper-relational knowledge graph completion. Georgiev el al. (2022) also incorporates a transformer into message passing for relationll knowledge graphs. The first approach that tailored to relational hypergraphs is G-MPNN (Yadati) 2020), which operates by relational message passing. RD-MPNNs (Zhou et al., 2023) builds on this approach and additionally incorporates the positional information of entities in their respective relations during message passing, which is critical for relational facts since the order of nodes in each edge clearly
message-passing
3

---

Published in Transactions on Machine Learning Research (05/2025)
matters. G-MPNN and RD-MPNNs represent the closest related works to the present study and we show that these architectures are instances of HR-MPNNs and hence are subject to the same limitations.
3 Link prediction with relational hypergraphs
Relational hypergraphs. A relational hypergruph G EV, consists a set V of nodes, a set E of hyperedges (or simply edges or facts) of the form e r(u1....,, ux) E E where r E R is relation type, "1:-.., Me E V are nodes, and k ar(r) is the arity of the relation r. We consider labeled hypergraphs, where the labels are given by a coloring function
nodes c: V + D. If the range of this coloring satisfics D = Rd, say is d-dimensional feature map and use the notation æ. We write p(e) as the relation E R of the hyperedge e E, and e(i) to refer to the node in the i-th arity position of the hyperedge e. We define E(c)= = ((e,)) i) e(i) = v, e E E, 1 S i I ar(p(e))) as the set of set captures all occurrences of node e in different hyperedges and arity positions. We also define the positional neighborhood of a hyperedge e with respect to a position i as MM(e)) = ((e(j).5) i + i, S ك ar(p(e)))- This set represents all nodes that co-occur with the node at position in a hyperedge e, along with their positions. A knowledge graph is relational hypergraph where for all r E R, ar(r) = =2
pairs of a node c. Intuitively, this
Link prediction on hyperedges.
Given relational hypergraph G = (V, E, R, and query q(u1,..,,441 u1,1, ?, Ut+1..., ux), where g E Rt is the query relation and "?" is the querying position, link pre- diction is the problem of scoring all the hyperedges obtained by substituting nodes v E V in place of "?" We denote a k-tuple (u1...., Ug) by a and the tuple (W1...., "t-1; M.41....,, (x) by ū. For convenience, we commonly write a query as a tuple q = (q, t).
Isomorphisms. An isomorphism from relational hypergraph G (V, E, R, to relational hypergraph G' = (V', E", R, c') is bijection V + V such that c(t) (f())) for all v E V, and r(u1,..., (2) E if and only if (ff())), f(())) E E', for all r E R and u1, uk E V.
Invariants. For & 2 1, we define a k-ary relational hyperyraph invariant as a function & associating with each relational hypergraph G = (V, E, R. c) a function E(G) with domain y such that for all relational hyporgraphs G,G', all isomorphisms f from G to G¹, and for all k-tuples of nodes a E Vb, we have [(G)(u) = (()))
Refinements. Given two relational hypergraph invariants & and e,, we say function ((G) Vk + D refines a function ('(G)= V + D, denoted as {(G) 3 (')G), if for all u, u, E Vk, (())(u) = (()) implies (u) = (u')...... In addition, we call such functions equivalent, denoted as {(G) = (') if ((G) 3 (())) and (G) 3 E(G). A k-ary relational hypergraph invariant & refines a k-ary relational hypergraph invariant E' if E(G) refines (C(G) for all relational hypergraphs G. Similarly for equivalence.
4 Hypergraph relational MPNNs
We first introduce HR-MPNNs, which capture existing architectures tailored for relational hypergraphs, such as G-MPNN YYdati 2020) and RD-MPNN (Zhou et al. 2023) (Appendix B.1
Let G = (V, E, x) be a relational hypergraph, where æ is a feature map that yields the initial features T. = x (v) for all nodes V E V. For é 2 0, an HR-MPNN iteratively computes a sequence of feature maps h (1) V + Rd) where the representations (f) (1) are given by:
(0) Fy.
((+1) = UP ( !h! (MsG (1(19) .)) (w, E Ni(e))) I (e,1) E E(o))))
where UP, AGG, and MSG are differentiable, updale, aggregation, and relation-specific message functions, respectively. These functions are layer-specific, but we omit the superscript (E) for brevity. An HR-MPNN has fixed number of layers 2 0 and the final representations of nodes are given by the function h(4) - dd()) We can then use a k-ary decoder DEC, : (d())) + R. to produce a score for the likelihood of q(u) for g R V*.
4

---

Published in Transactions on Machine Learning Research (05/2025)
HR-MPNNs contain architectures designed for single-relational, undirected hypergraphs, such HGNN
Feng et al. 2018) and HyperGCN (Yadatì et al.) 2019) (see Appendix B.2.. Furthermore, HR-MPNNs
capture relational message passing neural networks (Huang et al. 2023), as a special case (see Appendix B.3
MPNNs are well-understood both in terms of their ability to distinguish graph nodes (Morris et al.
2019
Xu et al. 2019 and in terms of their capacity capture logical node properties (Barceló et al. 2020
This
line of work has been extended to relational architectures (Barceló al.) 2022 Huang al.) 2023 In the
next subsections, we provide similar characterizations for HR-MPNNs.
4.1 A Weisfeiler-Leman test for HR-MPNNs
We formally characterize the ability of HR-MPNNS to distinguish nodes in relational hypergraphs via a variant of the 1-dimensional Weisfeilen-Teemn test, namely the hypergraph relational 1-W1, test, denoted by hrwl.- The test hrwl is natural generalization of rwli (Barceló et al., 2022) to relational hypergraphs. Given a relational hypergraph G = (V. E, R),, for & 2 0, hrwl updates the node colorings as:
hrwll = cu).
hrwl (() = (hrwl (V): ((hrr) (w,j) E ((
The function 7 is an injective mapping that maps the above pair to a unique color that has not been used in previous iterations: hrwl(" defines valid node invariant on relational hypergraphs for all f f
As it turns out, hrwl, has the same expressive power as HR-MPNNs in terms of distinguishing nodes over relational hypergraphs:
Theorem 4.1. Let G = (V,E, be relational hypergroph, then the following statements hold:
For all initial feature maps x with c = æ, all HR-MPNNs with layers, and for all 2 L, it holds that hrwl (8) < (0)
2. For all I, 2 0, there is an initial feature map with = and on HR-MPNN with T. layers, such that for all 0 < 8 S L, we have hrwl (0)
Intuitively, item (1) states that hrwl, upper bounds the power of any HR-MPNN: if the test cannot distinguish two nodes, then HR-MPNNs cannot either. On the other hand, item (2) states that HR-MPNNs can be expressive as hrwl:: for any T., there is HR-MPNN that simulates L iterations of the test. In proof, we explicitly construct this HR-MPNN using a simple architecture: the proof requires very delicate construction to ensure the HR-MPNN synthetizes the information around a node (given by its neighborhood E(v)), in the same way hrwl, does (see Appendix
4.2 Logical expressiveness of HR-MPNNS
The previous WT. characterization of HR-MPNNs is non-uniform in the sense that it holds for given relational hypergraph G. We now turn our attention to a uniform analysis of the power of HR-MPNNs and study the problem of which (node) properties can be expressed as HR-MPNNs, which is well-suited for the inductive setup. Following Barceló et al. (022)), we investigate logical classifiers, i.e., those that can be defined in the formalism of first-order logic (FO). Bricfly, a first-order formula d(x) with one free variable x defines a logical classifier that assigns value true to node in relational hypergraph G whenever G - ((u). A logical classifier o(x) is captured by HR-MPNN A if for every relational hypergraph G the nodes u that are classified as true by & and A are the same.
Graded modal logic on hypergraphs. Barceló el al. (2020) showed that a logical classifier is captured by an MPNN over single-relae relational undirected graphs and only it can be expressed in graded modal logic (de Rijko. 2000 Lutz et al., (201). This result is extended to knowledge graphs by Huang et al. (202)) We consider variant of graded modal logic for hypergraphs. Fix of relation types R and a set of node colors C. The hypergraph graded modal logic (HGML) the fragment of FO containing the following unary
5

---

Published in Transactions on Machine Learning Research (05/2025)
Ziq Pa
Pi
DEC
T2
71
T2
T1
2
Hypergraph G
INIT of g(b, a,
Message Passing
Figure 3: Given relational hypergraph with V = {a, b, e), E (r, c), (dd, e, R= (ri, and a query q(b, a), HCNet conditions on the nodes a and b and then applics message passing compute the score for q(b, e, a). Here, 2g is the learnable relation vector for query relation, and pt the positional encoding of the i-th arity position.
formulas. Firstly, a(x) for E C is formula. Secondly, if ((r) and (x(xx) are HGML. formulas, then mp(x)) and ((x) A (x) also are. Thirdly, for R, s is ar(r) and N 2 1:
J2Ng (r(m)-..))) 1 Vit Mar(r)) A V(()
is a HGML formula,, where y = (y),.... Di 1i.1............ Mar(r)) and (ū) is Boolean combination of HGML formulas having free variables from ÿ. Intuitively, the formula expresses that ø participates in at least odges e at position i, where the remaining nodes satisfy condition v
Example 4.2. Consider the set of relations from Figure | and the property: "o is a person who obtained a degree y of a subject a at a university m that has been awarded less than two prices of some subject w.. This can be expressed as the following formula:
(xx) Person(x) A By, 2, ml SSuddy y, 2) -32²p, p, (Awarded(w, p, p.)))
It is casy to verify that (xx) is indeed a HGML formula.
For any property expressed in HGML, such as Φ(x), does there exist an HR-MPNN that captures this property all relational hypergraphs with shared relational vocabulary R and node colors C? Indeed, we show that HR-MPNNs are powerful as HGML:
Theorem 4.3. Each hypergraph graded modal logic classifier is captured by HR-MPNN.
For the proof, we first show a simple normal form for HGML formulas, and then carefully translate formulas of this form into HR-MPNNs. See Appendix D for further discussion regarding HGML.
5 Hypergraph conditional MPNNs
In this section, propose hypergraph conditional message passing networks (HC-MPNNs), generalization of C-MPNNs (Huang et al. 2023) to relational hypergraphs.
Let G E, x) a relational hypergraph, where æ is a feature map. Given a query = (g. û, t), for HC-MPNN computes sequence of feature maps h hig as follows:
(6)
(0) ())T(V.q).
h (6+1) Up (/g (h olga
(MsG (((h))))))) (1(h))))
(0) (w.j) E Ni(e)), (e, E F(O))))
:/g
where INFT, UP. AGG, and MsG are differentiable initialization, update, aggregation, and relation-specifie message functions, respectively. An HC-MPNN has fixed number of layers L 2 O, and the final conditional
node representations are given by h (L)
b/g. We denote by h V - dd(()) the function h (v) = h 2/0

---

Published in Transactions on Machine Learning Research (05/2025)
To ensure that HC-MPNNs compute k-ary representations (see Appendix H impose a generalized version of larget node dislinguishabiliyy proposed by Huang al. (023)). An initialization function satisfies
generalized target node distinguishability if for all q = (g. ú,t);
INIT(u, q) INIT(U, q). Y u i and INIT(U; q) + INIT(Uj, q). Vu,, uj E ût us # uy
Differently from message passing on simple hypergraphs, we need to consider the relation type of each edge (multi-relational) and the relative position of each node (directed) in the edges on relational hypergraphs. Hence, the message function MSGp(e) needs to be relation-specific while also keeping track of the positions of nodes in their respective neighborhoods Mi(e). We can then obtain the scores of query q applying unary decoder DEC on (L) "/q
5.1 Hypergraph conditional networks
We define basic HC-MPNN, which call hypergraph conditional networks (HCNets). For query q (g. û, 1), an HCNet computes the following representations for all & 2 0:
h r/q
Σ
Lem * (p. zg);
=
ift
h (f+1)
(w(0)
h M
(t)
Σ
Ojffi (a
o (1- aa(0))))))) + +b())
vla
(c.))E
where sp(e).g is learnable message function, a is an activation function, ( is learnable weight matrix, (()) as learnable bias term per layer, 2g is the learnable query vector for q E R, and 1e is the indicator function that returns if condition C true, and 0 otherwise. As usual, * is scalar multiplication, and o is element-wise multiplication of vectors. We write a to refer to learnable scalar and p, to refer to the positional encoding position i, which is sinusoidal positional encoding (Vaswani et al. 2017
(6) In particular, we set (p(e).g to be a query-dependent diagonal linear map Diag( W, where W, is a learnable matrix for each relation r. Alternatively, we can adopt inerg-independent map by replacing W,z, with learnable vector w, for each relation r.
Intuitively, the model initialization ensures that all source nodes (i.e., nodes that appear in ū) are initialized to their respective positions in the query edge, and all other nodes are initialized as the zero vector 0 satisfying generalized target node distinguishability, shown in Figure 3
5.2 A Weisfeiler-Leman test for HC-MPNNs
To analyze the expressive power of HC-MPNNs for distinguishing nodes, we can still use the hrwl test provided we restrict ourselves to initial colorings that respect the given query q. Formally, given query
q= (q, u, t) on relational hypergraph G = (V, E, c), say that the coloring satisfies generalized target node distinguishability with respect to if:
c(u) * c(v) Vu E u.
u.ug ū and clu:) # c(u;) Vu,, uy E ū. u4 F uj.
Note that initial colorings satisfying this property are equivalent to the initializations of HC-MPNNs. As a direct consequence Theorem 4.1 we obtain:
Theorem 5.1. Let G = (V, F, R) be a relational hypergraph and = (q, ú) be a query such that c satisfies generalized larget node distinguishabiiity with respect to q. Then the following statements hold:
For all HC-MPNNs with L layers and inilialization INIT with INIT c, 0 0.55 L, we have hrwl hhg
(8)
2. For all I. 2 0, there is on HC-MPNN with L layers s.l. < T., hrwl =n holds.
HHC-MPNNs can also take into account node features with slight modification. detail discussions in Appendix
7

---

Published in Transactions on Machine Learning Research (05/2025)
Theorem 5.1 tells us that HC-MPNNs are stronger than HR-MPNNs due to the initialization: HC-MPNNs can initialize nodes differently based on the query 4, whereas HR-MPNNs always assign the same initial- ization for all queries. In fact, the ternary edges from Figure cannot be distinguished by HR-MPNNs but they can be distinguished by HC-MPNNs.
5.3 Logical expressiveness of HC-MPNNs
We remark that Theorem 4.3 can be translated to HC-MPNNs by slightly modifying the logic. We consider symbolic queries (g. b, 1), where now each b E b is a constant symbol. Our vocabulary contains relation types r E R and node colors C, as before, and additionally the constants b E We define hypergraph graded modal logic with constants (HGMLe) as HGML but, as atomic cases, we additionally have formulas of the form *fxx) (x = b) for some constant. b (see Appendix F for details). This allows to idendify variables with individual constants.
Exomple 5.2. Now that we have a richer vocabulary with constants, we can now represent more formulas "conditioned" on the constants appearing the query. For instance, given a symbolic query with b (Physics, BA), we can express a more complex formula (ax) that represents "x is person with BA degree of Physics at some University m, where less than two prizes p in total have been awarded in Physics." follows:
(x) = Person((2) A Ag, m DegreyDe 2, A (z Physics) A (y = BA)
A - (=22p, (Awarded p, p) A (w Physics)))
Note that this formula (xx) cannot. be expressed as an HGML, formula but it can be as an HGML, formula, due to the additional introduction of constants.
We prove the following result showing that HC-MPNNs can capture richer k-ary node properties Theorem 5.3. Each HGML, classifier can be captured by HC-MPNN over valid relational hypergraphs.
6 Experimental evaluation
We evaluate HCNet on a broad range of experiments:
Inductive experiments (Section 6.1 : We evaluate HCNet for inductive link prediction with relational
hypergraphs and report very substantial improvements reflecting on our theoretical findings.
Transductive experiments (Section 6.2 We evaluate HCNet for transductive link prediction with
relational hypergraphs and report competitive results.
Knowledge graph experiments (Section 6.3 HCNet can handle knowledge graphs as a special case and our evaluation shows that il can match the performance of models such as NBFNets.
Ablation on initialization and positional encoding (Section 6.4h: We conduct ablation studies on the choice of initialization and positional encoding in HCNets.
Expressiveness evaluation (Section 6.5 We conduct synthetic experiment on HyperCycle dataset,
building on the counter-esample in Figure to showcase the expressivity differences between HR-MPNNs
and HC-MPNNs.
Experimental setups. In all experiments, we consider a 2-layer MLP as the decoder and adopt layer normalization and dropout in all layers before applying ReLU activation and skip-connection. During the training, remove edges that currently being treated as positive tuples to prevent overfitting for each batch. We choose the best checkpoint based on its evaluation of the validation set. In terms of evaluation, we adopt filtered ranking protocol. For each test edge q(ui...., u&) where h = ar(g), and for each position E {1,...,k) k), we replace the (-th entities by all other possible entities such that the query after replacement is not in the graph. We consider the query-independent message function for all datasets except WikiPeople. We report Mean Reciprocal Rank (MRR), Hits@l, and Hits@3 for inductive experiments and MRR, Hits@1, and Hits@10 10 for transductive experiments as evaluation metrics and provide averagod results of five runs different seeds. We reported standard deviations and execution time & memory used along with all
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 1: Results of inductive link prediction experiments on WP-IND, JF-IND, and MFB-IND.
WP-IND
JF-IND
MFB-IND
MRR
Hits@1
Hits@3
MRR
Hits@1
Hits@3
MRR
Hits@1
Hits@3
HGNN
0.072
0.045
0.112
0.102
0.086
0.128
0.121
0.076
0.114
HyperGCN
0.075
0.049
0.111
0.099
0.088
0.133
0.118
0.074
0.117
G-MPNN-suu
0.177
0.108
0.191
0.219
0.155
0.236
0.124
0.071
0.123
G-MPNN-meat
0.153
0.096
0.145
0.112
0.039
0.116
0.241
0.162
0.257
G-MPNN-
0.200
0.125
0.214
0.216
0.147
0.240
0.268
0.191
0.283
RD-MPNN 0.304
0.238
0.328
0.402
0.308
0.453
0.122
0.082
0.125
HCNet 0.414
0.352
0.451
0.435
0.357
0.495
0.368
0.223
0.417
other experiment details in Appendix N Furthermore, we provide a ceetailed discussion of computational complexity between HR-MPNNs and HC-MPNNs in Appendix D and a discussion of the impact of relational hypergraphs' density on the performance in Appendix M We ran all experiments on a single NVIDIA V100 GPU. The code for experiments is provided in
6.1 Inductive experiments
Datasets. Yadati 2020p constructed three inductive datasets, WP-IND, JF-IND, and MFB-IND from
existing transductive datasets on relational hypergraphs: Wikileople (Guan et al. 2019). JF17K Wen
et al. 2016), and M-FB15K (Fatemi et al. 2020), with their statistics in Table
Baselines. We compare with the baseline models HGNN (Feng et al. 2018), HyperGCN (aadati et al. 2019), and three variants of G-MPNN (Yadati 2020) with different aggregation functions. Since HGNN and HyperGCN are designed for simple hypergraphs, Yadati (2020) tested them on transformed relational hypergraphs where the relations are ignored. In addition, Yadati (2020) initialized nodes with given node features, whereas we ignore the node feature and initialize each node with the respective initialization defined in HCNets. We modify RD-MPNNs (Zhou et al. (023) by replacing learned entity embeddings to be all one vector 1d to enable inductive link prediction. We adopt the batching trick (Zhu et al. 2021 on MFB-IND. Hyper-parameters are reported in Table 10
Results. We report the inductive experiments results in Table D and observe that HCNet outperforms all the existing baseline methods by large margin, doubling the metric on WP-IND and JF-IND and substantially inercasing on MFB-IND. Notably, we emphasize that HCNet does not utilize the provided node features whereas other baseline models do, further highlighting the effectiveness of HCNet in generalizing to entirely new graphs in the absence of node features. This is because HCNet is more expressive by computing query- dependent k-ary invariants instead of query-agnostic unary invariants in HR-MP such as RD-MPNNs and G-MPNNs with different aggregation functions. Overall, these results perfectly align with the main theoretical findings presented in this paper.
6.2 Transductive experiments
Datasets & Baselines. We evaluate HCNets on the link prediction task with relational hypergraphs, namely the publicly available FB-AUTO, MFB15K, Fatcmi et al. 2020 WikiPeople (Guan et al. 2021
and JF (Wen et al. 2016). These datasets include lacts of diflerent arilies up to 9. We have taken the result of embedding methods m-DisttMult, m-CP, m-TransH from Wen et al. (2016). RAE from Zhang et al.
(2018). , NaLP from Guan et al. (2019), tNaLP+ from Guan al. (2021), HINGE from Rosso et al. (2020).
NeuInfer from Guan et al. (202)). HypE from Fatemi et al. (2020) BoxE from
Abboud al. (2020). RAM
from Liu et al. (2021b). HyPerMI.N from Chen et al. (022)) D, HyConvE. from Wang et. al. (2023). ReATE
from
Fatemi et al. (2023). HJE from (Li et al. 2024a). Hy HyPlanE from
Li et al. 2024b and GNN
Note that we include JF17K for comparing with literature, even though JF17K suffers from redundant entries and severe test. leakages (Galkin et al. 2020
9

---

Published in Transactions on Machine Learning Research (05/2025)
Table 2: Transductive link prediction experiments on FB-ACTO, WikiPeople, JF17K, and MFB15K
FB-AUTO
WikiPeople Hits8k
JF17K
MFB15K
MRR
Hits@k
Hits8110
MRR
Hits810
MRR
Hits@01
Hits4R10
MRR
Hits@R1
Hits8810
un MalisttMllt
0.784
0.745
0.845
0.463
0.372
0,634
0.705
0.633
0.844
m-CP
0.752
0.704
0.837
0.392
0.303
0.560
0.680
0.005
0.828
m- Tr-nransH
0.728
0.727
0.728
0.444
0.370
0.581
0.623
0.531
0.809
RAE
0.703
0.614
0.854
0.253
0.118
0.463
0.396
0.312
0.561
NaLP
0.672
0.611
0.774
0.338
0.272
0.466
0.366
0.290
0.516
tNaLP4
0.729
0.645
0.826
0.339
0.269
0.473
0.449
0.370
0.598
HINGE
0,678
0.333
0.259
0.477
0.473
NeuInfer
0.737
0.700
0.805
0.350
0.282
0.467
0.451
0.373
0.604
HypE
0,804
0.774
0.856
0.263
0.127
0.486
0.494
0.408
0.656
0.777
0.725
0.881
RAM
0.830
0.803
0.876
0.363
0.271
0.500
0.539
0.463
0.690
BoxE
0.844
0.814
0.898
0.560
0.472
0.722
0.761
0.702
0.877
HyperMLN
0.831
0.803
0.877
0.536
0.482
0.717
Hy ConvE
0.841
0.820
0.901
0.362
0.275
0.501
0.590
0.178
0.729
ReALE
0.873
0.852
0.359
0.801
0.755
0.901
RD-MPNNN
0.810
0.714
0.888
0.512
0.445
0.685
HJE
0.872
0.848
0.903
0.450
0.375
0.582
0.590
0.507
0.729
HyCubE
0.881
0.860
0.918
0.448
0.368
0.592
0.584
0.508
0.730
HyPlanF
0.866
0.843
0.909
0.402
0.323
0.549
0.569
0.496
0.708
HCNet
0.871
0.842
0.922
0.421
0.344
0.565
0.540
0.440
0.730
0.759
0.693
0.884
method RD-MPNN from Zhou et al.
). The statistics of the datasets are reported in Table 9 and the hyper-paramene choices in Table 11 The full tables are in Tables 15 and 16 which additionally report H&3,
2023).
Results. We summarize the results for the transductive link prediction tasks and report them in Table 2 HCNet is competitive even comparing with existing embedding methods specifically designed for transductive link prediction tasks. This demonstrates the effectiveness of HCNets also transductive datasets.
6.3 Knowledge graphs experiments
In addition, to evaluate the model's performance on knowledge graphs-a specific instance of relational hypergraphs- we conduct inductive experiments on knowledge graphs, where every edge has an arity of 2, and compare the outcomes with those of current state-of-the-art models.
Setup. We evaluate HCNet on 4 standard inductive splits of WNISRR (Bordes et al. 2013) and FB15k-28 (Dettmers et al. 2018), which was proposed in Teru et al. (222)). We provide the details of the datasets in Table 17 Contrary to the standard experiment sctting (Zhu et al. 2021 2023 on knowledge graph G (V, E, Rt .) where for each relation r(u, v) E E, an inverse-relation r" is introduced symbol and r r-' u) is added in the knowledge graph, in our setup we do not augment inverse edges for HCNet. This makes the task more challenging. We compare HCNet with models designed only for inductivo binary link prediction task with knowledge graphs, namely GralL (Teru et al. 2020), NeuralLP (Yang et al.
fresh relation
2017), DRUM (Sadeghian et al., 2019),, NBFNet (Zhu et al. 2021). RED- GNN (Zhang & Yao 2022 and Net Zhu et al. 2023), and we take the results provided in
Zhu et al. (002)) for comparison.
Results. We report the results in Table 3
We observe that HCNets are highly competitive even compared with state-of-the-art models specifically designed for link prediction with knowledge graphs. HCNets reach the top 3 for 7 out of 8 datasets, and obtain a very close result for the final dataset. Note here that the top 2 models are NBFNet (Zhu et al.) 2021) and A *Net (Zhu et al. 2023) which share a similar idea of HCNet and are all based on conditional message passing. The difference in results lies in the different. message functions, which are further supported in Table of Huang et al. (0023).
However, we highlight that HCNet does not augment with inverse relation edges, as described in the set-up of the experiment. HCNet can recognize the directionality of relational edges and pay respect to both incoming and outgoing edges during message passing. No current link prediction model based on message passing can explicitly take care of this without edge augmentation. In fact, Theorem G.4 implies that all current models based on conditional message passing, including NBFNets, need inverse relation augmentation to match the expressive power of HCNet. Theoretically speaking, this allows us to claim that HCNet is strictly more powerful than all other models in the bascline that are based on conditional message passing, assuming all considered models are expressive enough to match their corresponding relational WL. test.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Table 3: Binary inductive experiment on knowledge graph for Hits result. and second/third best in underline.
The best result is bold,
FB15k-23
WN18RR
Method
v1
v3
v4
v1
v3
v4
GraIL
0.429
0.424
0.424
0.389
0.760
0.776
0.409
0.687
PeuralLP
0.468
0.586
0.571
0.593
0.772
0.749
0.476
0.706
DRUM
0.474
0.595
0.571
0.593
0.777
0.747
0.477
0.702
NBFNet
0.574
0.685
0.637
0.627
0.826
0.798
0.568
0.694
RED-GNN
0.483
0.629
0.603
0.621
0.799
0.780
0.524
0.721
A*Net 0.589
0.672
0.629
0.645
0.810
0.803
0.544
0.743
HCNet
0.566
0.646
0.614
0.610
0.822
0.790
0.536
0.724
Table 4: Ablation on Initialization
Table 5: Ablation on Positional Encoding
INIT
WP-IND
JF-IND
WP-IND
JF-IND
PE
Zg
P
MRR
Hits@3
MRR
Hits@3
MRR
Hits@3
MRR
Hits@3
0.388
0.421
0.390
0.451
Constant
0.393
0.426
0.356
0.428
V
0.387
0.421
0.392
0.447
One-hot
0.395
0.428
0.368
0.432
< 0.394
0.430
0.393
0.456
Learnable
0.396
0.425
0.416
0.480
V V 0.414
0.451
0.435
0.495
Sinusoidal
0.414
0.451
0.435
0.495
6.4 Ablation studies the impact of initialization and positional encoding
To assess the contribution of each model component, we conduct ablation studies mainly on different choices of positional encodings and initialization functions on WP-IND and JF-IND datasets with the same empirical setup described in Section 6.1 Complete results are reported in Appendix N
Initialization. We conduct experiments to validate the impact of different initialization by evaluating all combinations of whether including positional encoding or learnable query vectors žn- From Table we observe that both positional encoding p, and the relation &q are essential in the initialization, as removing either of them worsens the overall performance of HCNet. A closer look reveals that the removal of the ionalional encoding is more detrimental compared to removing relational embedding since the model could deduce the relation types based on implicit information such the arity of the query relation.
Positional encoding. We also examine the importance of the choice of positional encodings, which serves as an indicator of which position the given entities lie in hyperedge. We provide experiments on multiple choices of positional encodings and report the results in Table 5 Empirically, we notice that the sinusoidal positional encoding produces the best results due to its ability to measure sequential dependency between neighboring entities, compared with one-hot positional encoding which assumes orthogonality among each position. We also notice that learnable embeddings do not produce better results since it is generally hard to learn suitable embedding that respects the order of the nodes in relation based on random initialization. Finally, constant embedding evidently performs the worst as it pays respect to position information and treats all hyperedges with the same set of nodes in the same way regardless of the order of the nodes in these odges.
6.5 Expressiveness evaluation
We carry out a synthetic experiment with a custom-built, dataset HyperCycle to showcase that HC-MPNNs are more expressive than HR-MPNNs in the task of link prediction with relational hypergraphs.
Dataset. We construct HyperCycle, a synthetic dataset that consists of multiple relational hypergraphs with relation R (ro, r2). Fach relational hypergraph G is parameterized by syper-parammttes: the number
11

---

Published in Transactions on Machine Learning Research (05/2025)
of nodes which is always multiple of 4, and the arity of each edge k. We construct directed hyper-edge of arity & with alternating relations between r1 and 12 for all lt consecutive nodes in this cycle. We present one example of such relational hypergraph in Figure [ where n = 8 and k = 3. We generate the dataset by choosing n = {8. 12, 16, 20} and h = {3. 4, 5, 6, 7/. We then randomly pick 70% of the generated graphs as the training set and the remaining 30% as the lesting set. (See details in Appendix J
Objective. The objective of this task is for each node identify the node that is located at the "opposite point" in the cycle of the given node as true. Formally speaking, for relational hypergraph G(n,k), want to predict 2-ary (hyper-)edge of relation ro between any node 2; and its "opposite point" 2(++n/2 mod n) for all 1 S i S n, i.c., classify ro(#;, r0(22,"((+n//2 mod n.) as true. The negative sample is generated by considering the ro relation (hyper-Jedges that connect the "2-hop" neighboring node, i.e., classify ro (2 ((++)) mod n) as false. Note that since n + 4, we will never have (i + n/2) mod n = (i + 2) mod n.
Design & Result. We claim that HC-MPNN can cor- rectly predict all the testing triplets, whereas HR-MPNN fails to learn this pattern and will only achieve 50% ac- curacy, which is no better than random guessing. This is exactly due to the lack of expressiveness of HR-MPNNs by relying on a k-ary decoder for link prediction. The- oretically, all nodes of the relational hypergraphs in HyperCycle, due to their rotational symmetry introduced by alternating relation types 72 can be partitioned into two sets. Since the nodes within each set are isomor- phic to each other, it is impossible for any HR-MPNNs to distinguish between these nodes by only computing its unary invariant. Thus HR-MPNNs cannot possibly solve this task, as whenever they classify the target "op- posite point" node to be true, they also have to classify the "2-hop" node to be true, and vice versa. Empiri- cally, we observe that HR-MPNN always fails to Iearn anything meaningful, reaching an accuracy of 50%.
ro
To
Figure 4: Example relational hypergraph from dataset HyperCycle with 8 and k = 3: ri is blue, ra is red, and the objective is to classify the black edge as true and the gray edge as false.
However, HR-MPNN can bridge this gap by introducing the relevant notion of "distance". As HR-MPNN carries out message-passing after identifying the source node, the relative distance between the source node and the target "opposite point" node will be different than the one with the "2-hop" node. Thus, by keeping track of the distance from the source node, HCNet will compute different embedding for the positive triplet and the negative triplet, effectively solving this task. Empirically, observe that HCNet easily reaches 100% accuracy, consistent with our theory.
7 Summary, discussions, and limitations
We investigated two frameworks of relational message-passing neural networks on the task of link prediction with relational hypergraphs, namely HR-MPNNs and HC-MPNNs. Furthermore, we studied the expressive power of these two frameworks in terms of relational WL and logical expressiveness. We then proposed a simple yet powerful model instance of HC-MPNNs called HCNet and presented its superior performance inductive link prediction tasks, which is further supported by additional transductive link prediction and heltc experiments. One limitation lies in the palen high computational complexity of our approach when applied to large relational hypergraphs. Our approach is also limited to link prediction and a potential future avenue to investigate complex query answering on fully relational data. Our study extends the success of link prediction with knowledge graphs to relational hypergraphs where higher-arity relations can be effectively modeled with GNNs, advancing their applications to fully relational structures.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Broader impact
This work mainly focused on link prodiction with relational hypergraphs, which has wide range of ap- plications and thus many potential societal impacts. One potential negative impact is the enhancement of malicious network activities like phishing or pharming through the use of powerful link prediction models. We encourage further studies mitigate these issues.
References
Ralph Abboud, ismail Īlkn Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori. Boxe: box embedding model for knowledge base completion. In NeurIPS, 2020.
Mehdi Ali, Max Berrendorf, Mikhail Galkin, Veronika Thost, Tengfei Ma, Volker Tresp, and Jens Lehmann. Improving inductive link prediction using hyper-relational facts, 2021.
Ivana Balazevic, Carl Allen, and Timothy Hospodales. Tucker: Tensor factorization for knowledge graph completion. In EMNLP-IJCNLP, 2019.
Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel Romero. Weisfeiler and leman go relational. In LoG, 2022.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, 2013.
Zirui Chen, Xin Wang, Chenxu Wang, and Jianxin Li. Explainable link prediction in knowledge hypergraphs. In CIKM, 2022.
Maarten de Rijke. A note on Graded Modal Logic. In Stud Logica, 2000.
Tim Dettmers, Minervini Pasquale, Stenctorp Pontus, and Sebastian Riedel. Convolutional 2D knowledge graph embeddings. In AAAI, 2018.
Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. Knowledge hypergraphs: Prediction beyond binary relations. In IJCAI, 2020.
Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. Knowledge hypergraph embedding
meets relational algebra. JMLR, 2023.
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hyporgraph noural networks. AAAI, 2018
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR- RLGM Workshop, 2019.
Luis Antonio Galárraga, Christina Teffioudi, Katja Hose, and Fabian Suchanck. AMIE: Association rule mining under incomplete evidence in ontological knowledge bases. In WWW, 2013.
Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. Message passing for hyper-relational knowledge graphs. In EMNLP, 2020.
Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. In JCLR, 2024.
Dobrik Georgiev Georgiev, Mare Brockschmids, and Miltiadis Allamanis. HEAT: Hyperedge attention net-
works. Thansactions Machine Learning Research, 2022. ISSN 2835-8856.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In JCML, 2017.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Martin Grohe. The logic of graph neural networks. In LICS, 2021.
Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Chong. Link prodiction on n-ary relational data. WWW, 2019.
Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and Xueqi Cheng. NeuInfer: Knowledge inference on N-ary facts. In ACI, 2020.
Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and Xueqi Cheng. Link prediction on n-ary relational data based on relatedness evaluation. IEEE Transactions on Knowledge and Data Engineering, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Xingyue Huang, Miguel Romero Orth, ismail Īlan Ceylan, and Pablo Barceló. A theory of link prediction via relational weisfeller-leman knowledge graphs. In NewrIPS, 2023.
Shaoxiong Ji, Shirui Pan, E. Cambria, Pekka Marttinen, and Philip S. Yu. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Sys- lems, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Zhao Li, Chenxu Wang, Xin Wang, Zirui Chen, and Jianxin Li. Hje: Joint convolutional representation
learning for knowledge hypergraph completion. IEEE Transactions on Knowledge and Data Engineering, 2024a.
Zhao Li, Xin Wang, Jianxin Li, Wenbin Guo, and Jun Zhao. Hycube: Efficient knowledge hypergraph 3d
circular convolutional embedding. CoRR, 2024b.
Shuwen Liu, Bernardo Grau, Ian Horrocks, and Egor Kostylev. Indigo: Gun-based inductive knowledge graph completion using pair-wise encoding. In NeurIPS, 2021a.
Yu Liu, Quanming Yao, and Yong Li. Generalizing tensor decomposition for n-ary relational knowledge bases, In WWW, 2020.
Yu Liu, Quanming Yao, and Yong Li. Role-aware modeling for n-ary relational knowledge bases. In WWW, 2021b.
Carsten Lutz, Ulrike Sattler, and Frank Wolter. Modal logic and the two-variable fragment. In CSL, 2001.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Haiquan Qiu, Yongqi Zhang, Yong Li, and quanming yao. Understanding expressivity of GNN in rule learning. In ICLR, 2024.
Paolo Rosso, Dingqi Yang, and Philippe Cudré-Mauroxx. Beyond triplets: Hyper-relational knowledge graph embedding for link prediction. In WWW, 2020.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end dif- ferentiable rule mining on knowledge graphs. In NIPS, 2019.
Michael Sojr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In ESWC, 2018.
Zhiqing Sun, Zhi-Hong Deng, Jinn-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In TCLR, 2019.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Komal K. Teru, Etienne G. Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
Théo Trouiloon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaune Bouchard. Complex emn beddings for simple link prediction. In ICML, 2016.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar, Composition based multi-relationa graph convolutional networks. In ICLR, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, 2017.
Chenxu Wang, Xin Wang, Zhao Li, Zirui Chen, and Jianxin Li. Hyconve: A novel embedding model for knowledge hypergraph link prediction with convolutional neural networks. WWW, 2023.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering. 2017.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowlodge graph embodding by translating on hyperplanes. In AAAI, 2014.
Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and Richong Zhang. On the representation and embed- ding of knowledge bases beyond binary relations. In IJCAI, 2016.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Naganand Yadati. Neural message passing for multi-relational ordered and recursive hypergraphs. In NewrIPS, 2020.
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. In NewrIPS, 2019.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NewrIPS, 2017.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In NewrIPS, 2021.
Richong Zhang, Junpeng Li, Jiajie Mei, and Yongyi Mao. Scalable instance reconstruction in knowledge bases via relatedness affiliated embedding. W WWW, 2018.
Yongqi Zhang and Quanming Yao. Knowledge graph reasoning with relational digraph. In WebConf, 2022.
Xue Zhou, Bei Hui, llana Zeira, Hao Wu, and Ling Tian. Dynamic relation learning for link prediction in knowledge hypergraphs. In Appl Intell, 2023.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman- ford networks: A general graph neural network framework for link prediction. In NeurIPS, 2021.
Zhaocheng Zhu, Xinyu Yuan, Mikhail Galkin, Sophie Xhonneux, Ming Zhang, Maxime Gazcau, and Jian Tang. A net: A scalable path-based reasoning approach for knowledge graphs. In NewrIPS, 2023.
15

---

Published in Transactions on Machine Learning Research (05/2025)
A R-MPNNs and C-MPNNs
In this section, we follow Huang al. 20023 and define relational message passing newral nelworks (R- MPNNs) and conditional message passing neural networks (C-MPNNs). For ease of presentation, omit the discussion regarding history functions and readout functions from Huang et al. 2023
Let G = (V, x) be a knowledge graph, where æ is a feature map. A relational message passing neural network (R-MPNN) computes a sequence of feature maps h()) : V + Rd()), for 2 0. For simplicity, write (e) instead of (v). For each node E V, the representations ( are iteratively computed as:
R-MPNNs.
h Ve
h ((+1)) = UP (0) AGc MMs. w N.((),.ee RH)),
where UP, AGG, and MsG, are differentiable update, aggregation, and relation-specific message functions, respectively, -N(()= = {u| r((u,)) v) E E} is the neighborhood of a node E V relative to a relation r E R. An R-MPNN has a fixed number of layers L L20 0, and then, the final node representations are given by the map (L)) V - RRd(L) The final representations can be used for node-level predictions. For link-level tasks, we use a binary decoder DEC, (Rd(L) x (d(L) + E, which produces score for the likelihood of the fact g(u, for R.
C-MPNNs. Tet = = (V, F., x) be knowledge graph, where æ is feature map. A conditional message passing neural network (C-MPNN) iteratively computes pairwise representations, relative to a fixed query E R and a fixed node u E V, as follows:
h ollu.
= INIT(U, v.
h (8-1) UP (2)
olu..q (cc wlugg 2,)l w E NN()),, e RB)).
o|u.q
where INIT, UP, Acc, and MsG, are differentiable initialization, update, aggregation, and relation-specific message functions, respectively.
We denote by h. V x V + d())) the function hy (1, v) = h ofoug and denote Zy to be a learnable vector representing the query q E R. A C-MPNN has a fixed number of layers L 2 0, and the final pair reprosentations are given by h (L) To decode the likelihood of the fact q(u, for some q R, simply use unary decoder DEC RR] R, parameterized by 2-layer MLP. In addition, require INrr(u, 4) to satisfy target node distinguishabiityy; for all R and v + u E V, it holds that INIT(U, u. # INIT(u, v, v.
Nevertheless, we provide a full literature review on link prediction with a hyper-rclational knowledge graph and n-ary relational graph for the sake of completeness.
B HR-MPNNs subsume existing models
In this section, we provide further details on how the proposed framework HR-MPNNs subsumes existing models as claimed.
B.1 HR-MPNNs subsume G-MPNNs and RD-MPNNs
To see why HR-MPNNs subsume RD-MPNNs (Zhou et al. 2023 and G-MPNNs (Yadati 2020 which are prominent examples of message passing model on relational hypergraphs in the literature, it suffices to instantiate some components of HR-MPNNs with particular functions.
An RD-MPNN can be seen as an instance an HR-MPNN that uses summation as AGG, and a relation- specific message function MsG, which, for each relation r, applies summation followed by a linear map with non-linearity. The update function Up is one-layer Multi-layer Perceptron (MLP)).
16

---

Published in Transactions on Machine Learning Research (05/2025)
Similarly, G-MPNN instance be seen HR-MPNN that uses either summation, mean, max AGG, and message function MsG, which, for each relation r, applies a Hadamard product of the relational embedding.
B.2 HR-MPNNs subsuming HGNNs and HyperGCNs
To see why HR-MPNNs generalize HGNNs (Feng et al., 2018 and HyperGCNs (Yddti et al., 2019 on simple, undirected hypergraph, first note that (i) these models are single-relational - no relation types so they are a special case this sense and (ii) the hyperedges these undirected hypergraphs are unordered.
To recover HGNN, we can set the message function MSG, to be mean, ignoring the relation types т, and ignore the relative position in the formula (as there is ordering in simple, undirected hypergraph). Then, we can choose the AGG function to be symmetrically normalized mean, similar to the aggregation in GCN KKip & Welling 2017).
To recover HyperGCN, we set AGG to be the symmetrically normalized mean, and MsG, function to be Wiy arg max,, hh - hyl, with some weight WAy (again ignoring the relation and position i), provided that the message function has access to the feature of considered node h4.
B.3 HR-MPNNs subsume R-MPNNs
We formally show that the R-MPNNs framework is subsumed by the HR-MPNNs framework when applied to the knowledge graph.
be a knowledge graph, then given any R-MPNN instance A with L layer parameterized by Acc!l Up! and MsGAr for 0 E S L, E R, there erists a HR-MPNN instance B with L layer, porumeterized by AGo Up!(), and MSGBr, such that for all E V, we have h (2) for all 0 L.
Theorem B.1. Let G
A,G(T) BBB (v)
Proof. Given an R-MPNN instance A with L layer, we can have that for s < L, we have
h ( x<0) h (C+) A.G (v) U (8)
(A))))) Acc (h ( w WE (N), RR)),
Note that we can now rewrite the updating formula in the following form:
(o) Up (n (o)) Acc (MMSG (L(h (0) ((()) e Ni(e))) ((e, e E(v), = 2B))
We then parameterize a HR-MPNN instance B with L layer of the following form:
(v) = æ(v)
(e-1) BB (v) = Up (1 (U),(())GG (n [MSG (L(h) Ni(())) (e, e E(w)))
where we have for all 0 < f < L. Up! Up!. Acc (z, Acc(((5) for some vector and some (multi-)set S, and
MSG (1 9 (w). (w.)) Mi(e))) = MsG
Mi(e), = 1})
We argue that MsGBp(e) can be achieved by applying a filtering function on each element of the to check if the second argument of the tuple is or not.
17

---

Published in Transactions on Machine Learning Research (05/2025)
Now ready to prove the theorem by induction. First notice that the base case & = 0 trivially holds. For the inductive case, assume that for all E V, we have h h h.((1) hgg.(()) Then, notice that for & $
(2)
A (8+1) A.G (v) Up! h ( (v), Acc ( (MMSCAnto((A
( (w.j) (ee E()) -1a))))))) 2H)
UP (5)
(2)
UP (B (v), AcoE (0 (8) (b), (MSGB (w)) (e.)) B(O)B)
= -hg.G (1+1)
Remark B.2. Note that analogously can show that HC-MPNNs subsumes C-MPNNs by noticing gener- alized target node distinguishability in HC-MPNNs degrades to target node distinguishability in the context of knowledge graph. See further detailed discussion in Appendix
C Proof of Theorem 4.1
Theorem
4.1 Let G = (V, F, RG e) be a relational hyperrgaph, then the following statements hold:
1. For all initial feature maps with = æ, all HR-MPNNs with L layers, and for all 0 < L, it holds that hrwl, = (f)
2. For all L 2 0, there is on initial feature map with and an HR-MPNN with L layers, such that for all 0 s l L,, we have hrwl (t)
Proof. First, for simplicity of notation, we define m!! MsGp(e) (1hh ..) (w,j) Mi(ee)) for edge e, position 1 i ar(p(c)), and f 0.
To prove item (1), we first take an initial feature map with e and a HR-MPNN with L. layers. We apply induction on l. The base case where
follows directly as hrwl = = x = (0) For the inductive case, assume hrwl((+1) (u) hrw](())) (v) for some node pair u, V and for some f 2 1. By injectivity of
T, follows that hrwl (u) = hrwl(( (w) and
(([(hrw)) ( (w,5) E N((e)) (e, E(w)
((((hrw)))w)) (w), (w,j) e Nc (e(,')) e E(v)
By inductive hypothesis, we have h ()) and
((((h() (j) (w.j) e Ni(e)) (e,t) E())= [((( (1)) (w.j) (N((e)) (e, E(r)
Thus we have
[ (Msc p(e) (((h)))) (w.j) E Ni((e)) (e, E F(O)) F(W)) =
(S p(et) ((hh))) 5) (w,5) (w,j) Ne((e)) (6(,t) e E())
and then:
m (6) (e, E E(u) f (e'',')) E E(v)).
18

---

Published in Transactions on Machine Learning Research (05/2025)
We thus conclude that
[e+1) = Up' (n!) Ace ( Am (e, e B(W)))
Upl() (n! AGG A. (6,z) e B(O)))
(((+1))
Now we proceed to show item (2). We use a model of HR-MPNN in the following form and show that any iteration of hrwl1 can simulated by a specific layer of such instance of HR-MPNN:
! Die
((+11) f(t) ([n,0]
(OOzs (1 cl) + P.)) ))) (e.))E((v)
Σ
(2) Sole)
Here, (z) sign (0) b) where ( is parameter matrix, b is the bias term, in this case the all-ones vector b = (l,..., 1)²² and non-linearity use the sign function sign. For relation type R, the function (f) has the form 9f (z) = Y, sign(W;!") = - b), where w and yX are parameter matrices and b is the all-ones bias vector. Rocall that denotes element-wiss wise multiplication and pj the positional encoding al position j, which in this case is a parameter vector.
We shall use the following lemma shown in Morris et al. 2019 Lemma 9). The matrix J denotes the all-ones matrix (with appropriate dimensions).
Lemma C.1 ((Morris et al. 2019)). Let B E Next be a matric whose columns are pairwise distinct. Then there is a matria X E gixs such that the matrix sign( XB - J) (]1, non-singular.
For matrix B, we denote by B, its i-th column. Let n [V] and without loss of generality assume V = (1, (1...., n). Let be the maximum arity over all edges of G. We will write feature maps h : V + Rd for G = (V, E, R, e) also as matrices H e Rdxx, where the column H. corresponds to the d-dimensional feature vector for node v.
Let Fts be the following um x n matrix:
Fts
That is, (Fts), = - xj 2 i, and (Fts);, otherwise. We shall use the columns of Fts node features in our simulation. The following lemma is simple variation of Lemma A.5 from Huang et al. (2023, which in turn is a variation of Lemma C.1 above.
Lemma C.2. Let B E Next be matrix such that t S n, and all the columns are pairwise distinct and different from the all-zeros column. Then there is a matrix E Ruaxs such that the matria sign ( e {-1, 1) numxt is precisely the
of Fts given by its first columns.
Proof. Let z (1. + 1, (k + 1)?.... (k + 1)a-1) E Nixa, where is the largest entry in B, and b = =B Nixt. By construction, the entries of b are positive and pairwise distinct. Without loss of generality,
19

---

Published in Transactions on Machine Learning Research (05/2025)
b 0. As the b, are ordered, we can choose numbers .1..... 2t E R such that by zj < 1 if i 2 j. and by xj > 1 if i < j, for all i,j E {1......) 4). Let 0 = (#1,.... 3t, 2/ (Z1...., 31, ......, 22
assume that b (2 .......,,))))) be) for b1 b2 >
bg....,
2/b,)* E Raxi, Note that (2/b,) b, > 1, for all i E 1l. Let x' = I...... Inn' ) E R be the vector obtained from æ by replacing each entry æ, with m conseculive copies of x..- Then sign(æ'b-J) precisely the sub-matrix of Fts given by its first columns. We can choose X x'2 E Ramxs.
We conclude item (2) by showing the following lemma::
Lemma C.3. There erist a family of feature maps {h! V + Rum 0 < s L}, family of matrices
(W 10 ع & < L} and ((W!") (6) Y 10 e L,r E R}, and positional encodings {p, 1 S j s m] such
that:
h = hr for all 0 SESL.
h mm is column of Fts for all 0 < L and VEV.
c(j) + pi) for all e L and v E V, where f( and gk² are defined as above, i.e. (z) sign (f) b) and ge (z) y, sign( w!! b) (vector b is the all-ones vector).
((++1)== = r (n!
[
( ( Ojzi Spee)
(9
Proof- We proceed by induction on l. Suppose that the node coloring hrw! e with colors 1,...,P, for S n. Then we choose h (0) such that h Fts.(e)) i.e. h is the c(v)-th column of Fts. Thus, ( satisfies the required conditions.
For the inductive case, assume that (9 = hrwl( for 0 S < L and that h is a column of Fts for all V E V. We shall define parameter matrices W(() and ((W!") Y, | r R} and positional encodings (p, 1 J < m) such that the conditions of the lemma are satisfied.
For 1 J s m, the positional encoding pj is independent of l. Let p, 46 + 8e, RT where b is the m-dimensional all-ones vector and ej is the m-dimensional one-hot encoding of j. In other words, all entries of Pj are 4 except for the j-th entry which is 12. We define P5 = (D..... p.) E Rum to be the concatenation of n copies of p..
Let E and define EPos ((e,t) | CE E.ple) = =r, ar(r)) For (e, E E/es, define
2
1 = jjti e(j) + PP)
(
col
e,
(E)
(w,j) M((e).
We claim that for (e, (e', E Epos, we have
0 = L s if and only if col col.r.'
-0(() (1)
-0(0) -00
Suppose first that col., = col... By inductive hypothesis, we have
(hh .1 (l, (w,J) E NN((e) = ((h9)) .11 (w,J) (e)))))
It follows that (0) (6)
o.. Suppose now that colo, i # colo.. p. We consider two cases. Assume first i i i'
(6) -1))
Then o and o differ the i-th coordinate, that is, (o (o?)) * ( Indeed, note that the entries of
vectors of the form (1) +Pj are always prime numbers in (3, 5, 11, 13) (the entries of h are always in (-1,1} (2) by inductive hypothesis). The i-th coordinate of all the vector factors in the product (6) = = e0) + +,)
has value 3, and hence (o!?): 31 On the other hand, there exists vector factor in the product (8) 0 = Ojze ( + P;)) (the factor h (!) (() + +,), whose i-th coordinate is 11. Hence (o! and (o ) have
20

---

Published in Transactions on Machine Learning Research (05/2025)
~ (1)
~
v there different prime factorizations and then they are distinct. Now assume i = Since col * colo e'
must be a position j' such that hrwl(((e())) # hrwl By inductive hypothesis, (2) Me(r) # h (0)
Again by inductive hypothesis, we know that h h00 (e()*) and h Re'(") are columns of Fts, say w.l.o.g. the k-th and k-th columns, respectivcly, for 1 k < k' & n. By construction of Fts, all the m entrics of (1) from coordinates {km + 1...., km + m) are 1, while these are -1 for h (2) differ on the (km + j-) coordinate. Consider the product o.1 Oszi(h + Pp)). The (km + j*)-thh coordinate of the factor Mols") + Py- is 13, while it is in {3,5) for the remaining factors. For the product 02 Ojzr (h (he')) + PP); the (km + j-ttth coordinate of the factor h h00 Re()") + P/- is 11, while it is in {3, for the remaining factors. Hence (o(3) km+ss and (o kmm+s have different prime factorizations and then they are distinct.
Be(g") Be(rt) We claim that o and (8)
02.
Let E R. It follows from the previous claim that if we interpret (0)) and col (f) then these two colorings are equivalent (i.e, the produce the same partition). Let s, be the number of colors involved in these colorings, and let os, E Rum be an enumeration of the distinct vectors appcaring in {or (6) (e, E Epra). Let S, be the (nm x s,)-matrix whose columns are 01,..., Os, Fix an enuneration vi...., of R and define s ErER Sy. Now we are ready to define our sought matrices w!! and y, for r R. We define w!! to be the (s, X mm)-matrix obtained from applying Lemma C.1 to the matrix S, Let y,(0) E Re.xsr be the inverse matrix of sign sign(W S, JJ. Suppose r = rx for < k S [R] Then, the matrix Y is the (s x s,)-matrix defined as the vertical concatenation of the following [R] matrices: Nr....., Ph.....,NZ_.. (,(0) .r NT where Nr is the all-zeros (sp, x 8,) mma-riii By construction, r, sign(W! 5,- is the vertical concatenation of Nr...., .r Iy, N N Nr R) where I, is the 8, x sr identity matrix. In particular, if we consider gr (z) = (0 sign z b) as in the statement of the lemma, then for each (e, E Epos, the vector me gr (o!)) has the form m
colorings for Epos,
(E)
(0) (0,, O 8 0 Orgpsr..., 0 E [0, where O,, is the all-zeros vector of dimension s, and -0()
(8) C2 E [0,1]* is a one-hot encoding of edge color of or equivalently, of edge color col It follows that the vector
1! = Σ
Σ Σ
9 (O))
(c)))
TER (c.))
has the form f!( = (an....., ar yT E N", where a, is the s,-dimonsoonal vector whose entry (a,),, for 1 1 j S s,, is the number of clements (e, in E with color j, that is, such that o!! oy. In particular, a, is an encoding of the multiset [col (e, E F(e) Eroe } and hence f(( is an encoding of the multiset (8)
(.0l,,i p(e)) I (c, E(u) Note that this multiset is precisely the multiset (c,l i) I (c, E E(v) from the definition of the update rule of the hypergraph relational 1-WL test. Hence, the feature map given by the concatenation [h! { for all e E V, equivalent to hrw((++1)
If (col
It remains to define the function ((0, given by the parameter matrix W(O, so that the feature map ((+1) satisfies the conditions of the lemma. Since the columns of Fts are independent, there exists matrix M Raxmm such that Fts is the n X n identity matrix. Since each (((", with v E V, is a column of Fts, then M) E {0, 13" corresponds to a onc-hot encoding of the column or color h Let M' be the (n + 8) x (nm + +s matrix with all entries 0 except for the upper-left (n x nmm)-submatrix which is M, and the lower-right (s s)suumaarrix which the (s s) identity matrix. By construction, we have (' (2) || f! = [Mh (0)) # E No++s Let Zi...., Zq. with q S n, be the distinct vectors of the form MM (00 and let B be the ((n + s) x q)-matrix whose columns are preciscly 2I,.... Eq. We can apply Lemma C.2 to B to obtain a matrix X E Ramx((+s) such that sign(X (XB J) is the matrix given by the first q columns of Fts. We define our sought matrix ((() to be (!) XM.
21

---

Published in Transactions on Machine Learning Research (05/2025)
D HGML and proof of Theorem 4.3
D.1 HGML formulas
Fix a set of relation lypes R and a set node colors C. The heperryrahh graded modal logic (HGML) is the fragment of FO containing the following unary formulas. Firstly, a(x) for a E C is formula. Secondly, if (((:) and (a:) are HGML formulas, then =p((x) and ppx) A o (x) also arc. Thirdly, for E R. 1 isiss ar(r) and N 2 1:
MN (r(m ........... Vi-,, 2, 1.t1. Var(r)) ) V(())
is a HGML formula, where ÿ = (y1..... ..... Di-1, 01+1....... Var(r)) and (ÿ) is a boolean combination of HGML formulas having free variables from ÿ. Intuitivcly, the formula expresses that participates least N edges e at position i, such that the remaining nodes in satisfies V.
Let G E, be relational hypergraph where the range of the node coloring is C. Next, we define the semantics of HGML. We define when node v of G satisfies a HGML formula spxx), denoted by G = p(v), recursively as follows:
if ((²) = alx) for E C,, then G p(v) iff a is the color of o in G, i.e. c(v) =
if ((x) = -pp (xx), then G ((v) iff G / (v().
(((( = (x)) A (x),, then GF (()) G ('()) and G G ("))..
if ((x) 32N (r(y) 11-1, Mi+ls.... ................................
(())) then G - ((v) iff there exists at least N tuples (W),... 11 11+1 ................................ War(r)) of nodes of G such that r(w),..., ....,,... W;- Wi+1...., War(r)) holds in G' and the boolean combination L (wi..... W1-1, Wi.......,...................... War(r)) evaluates to true.
Mar(r)) ,
As example, consider the set of relations from Figure I that is, relations (Person(z), (trrsoy Degreee,,,, V/ m), Awarded(w, p, m)). Consider the property: "x is a person who obtained a degree y of subject at a university m that has been awarded less than two prices of some subject w.. This can be expressed as the following HGML formula:
Φ(x)
Ey. 2, m StuddDeerce(z, m) A ( (Awarded(w, p, p.m)) Person(x) A
w
Observe that HGML formulas have restricted form and hence they are not able to represent all logical queries, which hints at the fundamental limitations of our studied models. For instance, formulas in HGML can only express local properties of nodes. That is, properties of the form "a node is comnected (via hyper- odges) to other nodes satisfying other (local) propertics.. This is illustrated in the example above as the variables y, 2, m are forced to appear together with æ in the hyper-edge StudyDegree(r, y/ F, m)). Another limitation of HGML that once we quantify over the neighboring variables for (in the example y, 2, m), we can only check (local) HGML properties separately for the neighboring variables and combine them via Boolean combinations. In the example above, check the property "m has been awarded less than two prices p of some subject w" for university via the HGML formula ((m) -322p, (Awarded(us; p. m)). In particular, we cannot check properties that involve simultaneously two or more neighboring variables, as these properties would not be HGML properties (they would not even be unary). As an example, consider the property "x is a person who obtained a degree y of subject & at a university m that has been awarded less than two prices p subject z." Now we do not impose that m has less than two prices any subject, but less than two prices in the particular subject z (the same related with person z). This can be expressed
d(x) =
Person(x))
By, 2, m StudyDogree y, m) A -322 (Awarded(z.p,.))
Note that this is not an HGML formula as 3(m,2) -322p (Awarded(2, p, m)) checks condition that involves two neighboring variables (m and 2). This violates exactly the requirement discussed above.
22

---

Published in Transactions on Machine Learning Research (05/2025)
D.2 Proof of Theorem 4.3
Before showing Theorem we need to prove auxiliary result. We define a restriction of HGML, denoted by HGML,, as follows. HGML, is defined as HGML, except for the inductive case
SfMy (r(v). ................................ 1i-1, Vi+1...... Var(r)) A ((O))
where now impose V (ÿ) to be conjunction of HGML formulas with different free variables, that is,
(v)) (i-1(11-1) A (i+1(1++1) A A Par(r) (War(r))
We have that HGML is actually equivalent to HGML, Proposition D.1. Every HGML formula can be translated into an equivalent HGMI, formula.
Proof. We apply induction to the formulas in HGML. The only interesting case is when the formula has the form
M2N ÿ (r(v........ 91-1, x, 9++1. Bar(r)) ) A v(D)
for r E R, 1 arir)))()) N 2 and a boolean combination (ū) of HGML formulas. We can write (1) in disjunctive normal form and since negation and conjunction are part of HGML, we can assume that ( has the form:
()) = V v((11) A A ( 1) A (141)1)4)) A A.. A parr))
15k5g
For s k S d and subset T fl, 1, a,...,,((r))) we denote by of the formula
o (v1,.... 11 Vi+1, Bar(r)) = A aET
pl(( A A (.(a).
agT
Note that of expresses that for the k-th disjunct of V, the conjuncts v (ya) that are false are precisely those for which a E T. In particular the k-th disjunct of Yi corresponds to di
For S C .d) and a vector T = (Tx S fl...., 1, , ar(r)) Th + 0, k $ S), we denote by V STT the formula:
(VI ..... 1, 1i+1,,......... War(r)) =
o4
kES
kgS
V. expresses that exactly the k-th disjuncts for h E S are true, and each of the remaining false disjuncts for k & S are being falsified by making false precisely the conjuncts (a(y)), with a Th. Since HGML contains negation and conjunction, free variables, that is:
write S. conjunction of HGML formulas with different
V S. (y). 1 11 11 ................................ Mar(r)) a1 A Aa- (3641)1411 A (ar(r)
Define
F:= S O. (Th C (L....,,i i- ar(r)) Th + 0. S)}.
Then by construction, we have that +b is true iff exactly one of the formulas in F is true. It follows that
3 (r(ei..... 21 B141. Bar(r)) A M(i)
is equivalent to the HGML, formula
V
32Na ÿ (rler.... V1-1, x. v, 16+1, ... Var(r) (T.(
(N Vs.TE ESy No.T=N
23

---

Published in Transactions on Machine Learning Research (05/2025)
where
- (-ar)))))- ã1 (11) A 1 0 A (ar(() (Var(r))
where ca (Ha) the translation to HGML, of the formula a. (yo), which we already have by induction.
Now we are ready prove Theorem
Theorem 4.3 Each hypergraph graded modal logic classifier is captured by a HR-MPNN.
Proof. We follow similar strategy than the logic characterizations from Barceló et al. 2020): : Huang et al. (2023). Let (zx) be a formula HGML, where the vocabulary contains relation types and node colors C. By Proposition D.1 we can assume that (rr) belongs to HGML,, Let Pi....; PP be an enumeration of the subformulas of +p such that if fo subformula of Pj; then S j. In particular, P = y. We shall define an HR-MPNN B with L layers computing L-dimensional features in each layer. The idea is that at layer L E [ L}, the l-th component of the feature (f) is computed correctly and corresponds to 1 if is satisfied in node v, and 0 otherwise. We add an additional final layer that simply outputs the last component of the feature vector.
We use models of HR-MPNNs of the following form:
h(++1) p(() ((1)((1)))) [n!o|
Σ
(c) Ople) ( (Ofzs (D, - -h (1) )))
(e.))E((v)
where ( is a parameter matrix, b is the bias term and or is a non -omeiineriity For relation type r R, the function gf has the form of (x) a, oW:!" 2), where w!! is a parameter matrix and a, is a parameter vector. Recall that @ denotes element-wise multiplication and Py is the positional encoding at position j, which in this case is a parameter vector. The parameter matrix ((()) will be (L -ma-mxx of the form (+) (W/' I], where w is (L x L) parameter matrix and I is the (L x L) identity matrix. The paramcter matrices w and w! are actually layer independent and hence we omit the superscripts. Therefore, our models are the following form:
Here,
(e+1)) = a Woh + +Σ Σ
a, 1.-o(W, Ojfe (P, {)( + +b)
rER (c.))E p(c)=r
For the non-linearity we use the truncated ReLU function axx) = min(max((0,x). Let m be the maximum arity of the relations in R. For < S m, the positional encoding P, is defined as follows. The dimension of pj must be (the same as for feature vectors). We define a set of positions I, S (1...., : L} as follows: Ij iff there exists a subformuul. of &p of the form
N y (r(I..... 11-1, F. With. Mar(r)) A ai (31)
A.. A (1 A (441(1141)000. A ... A Car(r) (Vart)))
such that j E fl.....i 1.. ar(r)} Then we define Pj such that (py), = if A: E and (p,)x othrrwise.
and aj is the k-th subformula in the cnumeration P1.... PL.
Now we define the parameter matrices Wo E 4 and W, E gLxL, for r E R, together with the bias vector b. For < L, the Ê-row of Wo and W,, and the l-th entry of a, and b are defined as follows (omitted entries are 0):
1. If (e() = a(x)) for a color a E C, then (Wo) = 1.
2. If (1(x)) (1) then (Wo)e -1, and b 1.
24

---

Published in Transactions on Machine Learning Research (05/2025)
3. If (p(x)) (x) A (x( then (Wo)ez 1, (Wo)e and be -1
4. If
pe(x) = 32 (r(y2, 11-1: Rt Mi+1, ................................ Mar(r)) A skks (11)
A
pp:: ((fi A (Pk; (96-1) ) A (Raee (Var(r))
then (W,)es, = 1 for E {I..... I... ar(r)) and (ar)e 1 and by = - + 1.
Let G (V, F, c) be relational hypergraph with node colors from C. In order to apply Bi to G, we choose initial I-dimensional features h such that (h. )e = 1 if 9 = =(x) and a is the color of v, and (h!"), ) 0 otherwise. In other words, the L-dimensional initial feature h is a one-hot encoding of the color of To conclude the theorem show by induction the following statement:
(t) For all S e L, all 1 pspsc l, all v e V,, we have (he )p 1 if and only if G G (ppp))).
We start by showing the following:
(+) For all 1 S E L, all E V, and all S S L such that 9p(x) = a(x) for some a E C, we have (h!"), if and only if G - po(u).
We apply induction on For the base case assume l = Take and S p S L such that (p(xx) a(x) for some C. By construction, we have that:
(h.)), = o ((. = )
By definition of (0), we obtain that (h.) (n )p
and only if G F pp(w)) For the inductive case, suppose > 1 and take e V and 1 1S p L such that (x(x)) a(x) for some We have that:
(h!"), o @(11 (1n
(
By inductive hypothesis we know that (h (f (h = 1 if and only if G F pp(v). It follows that (n = =1 if and only if G F (v).
We now prove statement (t). We start with the base case f= 1. Take E V. It must be the case that p 1 and hence (x)x) = a(x) for some E C. The result follows from (+).
For the inductive case, take l 1. Take v E V and S < E. We consider several cases:
Suppose pp(x) = a(x) for some color a e C. Then the result follows from (+).
Suppose that (p(x)= = -pp((x) (x). We have that:
(h) = of (h ( + +1) = -(h((--) x + 1.
(1 ( O. Since 5 6--1. 1, we have by inductive hypothesis that We obtain that (h ( ) iff (h
(n( = iff G = (v). It follows that (h )2 = 1 iff G -= (p()).
Suppose that (p(x) = (x) (x)))) Then:
(h1 )p σ (1h (1) + (h(f-1)); 1).
We obtain that (n
(2) pp = isf (h - = and (n ((-1) ) = 1. Since j. k S E 6-1,, 1, we have by inductive
hypothesis that (1e(-11) ((((11)) iff G + (v) and (he ) 1 iff G (v). It follows that (Ne(e) ) 1
(6-1)
iff G == (v))).
25

---

Published in Transactions on Machine Learning Research (05/2025)
Suppose that
pp(x) =32N (f(y)...,, 16-1, 9641...... ,ar((r) ) A spke (11)
A A PkL-i (V6-1) A Pket (Ui+1) A ... A PRinno) (War()))
Then:
(h (00)=ok =
E (1 (1-0(2
-
Oczolpi (1((0)))=)) - N +1).
(e))) p(c)=r
We say that a pair (e, 9) E B(v), with p(e) =r, is good if and G F (k, (e(i)) for all j E {l....,
1, + I,..., ar(r)}- We claim that Ejzi Otzg(p: - (t- 1) [k, = 0 (e, is good and Ejts Otzy
e(t)
h (e-1))
Be()) Day > 1 otherwise. Suppose (e,g) is good. Then q i. Take j # i. We have that Dezi (8-1))
h ((t)) )k, 0 since the factor (p: -h
e(t)) )k; when - j. Indeed, by construction, (P))k; 1. Also, since ky 6-1, we have by inductive hypothesis that (h (1((-11)) Jay = 1 iff F (e,( Since (e, is good, it follows that (h (1((-1)) )x; = 1. Hence (P) h (8-1)
(t-1))
c(5) )e, 0. Suppose now that (e, is not good. Assume first that q = Then there exists j # such that H (x, (e(j)). We have that Or h ((()) Jay 1. If t j. then we have (pt)a, 1. Since K3 S l 1, by inductive hypothesis ((-1))
a(t) )k; = 1 when t = j. If t & {i,j), e(t) )ay > 1. Suppose now that q + i. Then choose j q and obtain that Orzg(D: h c(t) )ky 1. Indeed, we have (pr)s, 3 for all
have that (h c(f) ((-1)) ),, = iff G - sxy, (e())) It follows that (p: - h (1-1))
then (pe)a, = 3 and then (p: - h (1)(1))))) Jay > 1. Hence Op4s - h (t-1)
(1(-1))
t * q. Hence all the factors of Opty(P: h (() (((-))) ),, are > 1 and then the product is > 1.
As consequence of the previous claim, we have that:
(h = o (I((e, E F(()) p(e) = r, (e, is good) N 11).
By definition G + (v) iff (((e,)) e E(u) p(e) = r, (e, is good?| 2 N. Hence + (p(()) iff
(h!")) ), 1.
E Proof of Theorem 5.1
Theorem 5.1. Let G = (V,E, be relational hypergraph and = (q. t, be query such that satisfies target node distinguishability with respect to q. Then the following statements hold:
For all HC-MPNNs with L layers and initialization INIT with INIT = c, 0,0 OOSEEs L, we have howl(") = (8)
2. For all L 2 0, there is HC-MPNN with L layers s.t. 0 S E L, hrwl = h4 =h4 holds.
Proof. Note that given G and g, each HC-MPNN A with L layers can be translated into HR-MPNN B with L layers that produce the same node features in cach layer: for B we choose as initial features, the features obtained from the initialization function of A, and use the same architecture of AA (functions UP, AGG, MsG). On the other hand, each HR-MPNN with layers whose initial features define a coloring that satisfies gencralized target node distinguishability with respect q can be translated into a HC-MPNN A with L layers that compute the same node features in each layer: we can define the initialization function of A that obtain the initial features of B and then the same architecture of B.
26

---

Published in Transactions on Machine Learning Research (05/2025)
Item (1) is obtained by translating the given HC-MPNN into its correspondent HR-MPNN and then invoking Theorem 4.1 Similarly, item (2) is obtained by applying Theorem 4.1 to obtain an equivalent HR-MPNN and then translate it to a HC-MPNN.
F Proof of Theorem 5.3
t), where each e b is constant symbol. We consider vocabularies containing relation types r E R, node colors C, and the constants b E b. In this case, we work with relational hypergraphs G = (V, R, c, (1S)scs), where the range of the coloring e is C and up is the interpretation of constant b. We only focus on valid relational hypergraphs, that is, G = (V, E, C, (Ub)be) such that for all b E b, b + 1/ implies vs * un-
We consider symbolic queries q (q, t),,
We define hypergraph graded modal logic with constants (HGML)) as HGML but, as atomic cases, we addi- tionally have formulas of the form (pxx) = (x b) for some constant b. As expected, we have that HC-MPNNs can capture HGMT,, classifiers.
Theorem 5.3. Each HGML, classifier can be captured by a HC-MPNNs over valid relational hyperggaphs.
Now we have extra base cases of the form p(x) (x = b) but the same arguments apply. Note that now we need to
Proof. The theorem follows by applying the same construction as in the proof of Theorem 4.3
define the initial features (0) via the initialization function of the HC-MPNN. Since we are focusing on valid relational hypergraphs, this can be casily done while satisfying generalized target node distinguishability.. J
G Link prediction with knowledge graphs
An interesting observation is that when we restrict relational hypergraphs to have hyperedges of arity exactly 2, we recover the class of knowledge graphs. C-MPNNs (Huang et al.) 2023) are tailored for knowledge graphs and their expressive power has been recently studied extensively, with a focus on their capability for distinguishing pairs of nodes (for a formal definition see Appendix A In this section, we compare HC-MPNNs and C-MPNNs, and hence we are interested in the expressive power HC-MPNNs in terms of distinguishing pairs of nodes. Note however that, in principle, HC-MPNNs do not compute binary invariants. Indeed, for q R and pair of nodes u, we can obtaín two final features depending on whether we pose the query quu ?) or q(?, v). As a con,ention, we shall define the final feature of the pair u, v as the result of the query quu,?) When a HC-MPNN computes binary invariants under this convention, we say the HC-MPNN is restricted to tail predictions.
We proceed to show that HC-MPNNs restricted to tail predictions have the same expressive power in terms of distinguishing pairs of nodes as the rawl, test proposed in Huang et al. (2023). This test is an extension of rawl2, which in turn, matches the expressive power of C-MPNNs. It follows then that HC-MPNNs are strictly more powerful than C-MPNNs over knowledge graphs. We show this by first defining variant of the relational WT. test which upper bound the expressive power of HC-MPNNs restricting to tail predictions.
Given a knowledge graph G = (V, E, R, c, m), where n: V X V + D is a pairwise coloring satisfying targel node distinguishability, i.c. Yu * v, n,, u) # nu,,v), we define a relational hypergraph conditioned local 2- WL test, denoted as hewlg. howly iteratively updates binary coloring nj as follow for all 2 0:
ho (0) v(,
(f+1) (u, v) (howll (u,v), v), al (1(hwwl))) how!
(2) (u, (() (e, E B(v)B)
Note that indeed, hewll computes a binary invariants for all f 2 0. First, we show that HC-MPNN restricted on only tails prediction is indeed characterized by hewl2. The proof idea is very similar to Theorem 5.1 in Huang al. 2023
Theorem G.1. Let G (V,E, R, R, be a knowledge graph where x a feature map and r a pairwise node coloring satisfying target node distinguishability. Given query with q = (g. u, 2), then we have:
27

---

Published in Transactions on Machine Learning Research (05/2025)
1. For all HC-MPNNs restricted tails prediction with L layers and initializations INIT with INIT n, and S f S L, we have hcwl, 3 ha (9)
2. For all L N 0 there an HC-MPNN restricted on tails prediction with layers such that for all 0 s l - L, we have howl? = hg
Proof. We first rewrite the HC-MPNN restricted on tails predictions in the following form. Given a query q = (g, ū, I), we know that since is a knowledge graph, only consists of a single node, which we denote as u. In addition, since we only consider the case of tail prediction, then we always have t= 2. With this restriction, we restate the HC-MPNN restricted on tails prediction on the knowledge graph as follows:
h INIT(U,q),
(0)
(0) h (E+1) UP Up(M// (1) AGo(h 2/g (( (0 (w, E (i(e))) (e, E B(O)B)
Now, we follow similar idea in the proof of C-MPNN for binary invariants Huang et al. 2023 Let -V(V G G= (V, E, R, n) be knowledge graph where is pairwise coloring. Construct the auxiliary knowledge
graph G = (V x V, E', R. eg) where E" = {r((u. (u, w), (u, v)) r(w, u) E E,r E R} and on is the node coloring 67((u, v)) = n(u, v). Similar to Theorem 5.1 If A is a HC-MPNN and B is an HR-MPNN, we write h (0) (u, h (4)
(q.()). (v) and ((u, u)) = (e) ((u,v)) v)) for the features computed by A and B over G and G2, respectively. We sometimes write (c) and (v)) to emphasize that the positional neighborhood within hyperedge and set of hyperedges including node v is taken over the knowledge graph G, respectively. Finally, we say that an initial feature map y for G² satisfies generalized target node distinguishability if y(uu, u)) * y(u,, v)) for all u # v. Note here that the generalized target node distinguishabilit, naturally reduced to target node distinguishabiiity proposed in Huang et al. (2023) since u is a singleton. Thus, we have the following equivalence between HR-MPNN and HC-MPNN restricted on tail prediction the knowledge graph.
Proposition G.2. G E, R, 2,1) be knowledge graph where a is feature map, and n is a pairwise coloring. Let q E R, then:
1. For every HC-MPNN A with L layers, there is on initial feature map y for G2 an HR-MPNN B with L layers such that for all 0 S E L and u, U. VUEVV. VV, we have h(0) (u,, = 1 u)).
2. For every inilãal Seature map y for G salisfying generalized larget node distinguishabitily and every HR-MPNN B with L layers, there is a HC-MPNN A with L layers such that for all 0 l L and
u, U E V, we have h (f) ((u.ve)
(1) h ((u,v)
Proof. We proceed to show item (1) first Consider the HR-MPNN B with the same relational-specific message MsG,, aggregation AGG, and update functions UP as A for all the L layers. The initial feature map y is defined as y((u,v)) v)) TN (g, 2)), where INrT the initialization function of A. Then, by induction number of layer é, we have that for the base case & == 0, h (0) (2) A (1, v) INrr(e, (a. (u). 2)) = y(uu, v)) = n (0) ((u, u)). For the inductive case, assume h ( (u,v) = h ((u, v)), then
h A (++1) (1+)) v) = UP (1 (u, v), Acc (1 (8) (1,
(MsG (1(h (1 (u, ())) (w,j) E (9(1)) I (e, E.)))))
(u, AGG (cG (1,
[MsG ((h (8)
E N. (T((())) ( ((e,)) E (o))))
(t+1) ((,,
hg
28

---

Published in Transactions on Machine Learning Research (05/2025)
To show item (2), we consider A with the same relational-specffcc message MsG,, aggregation AGG, and update functions UP as B for all the L. layers. We also take initialization function INIT such that INIT(U, (g. (u),2) v(( Then, we can follow the same argument for the equivalence as item (1). I
We then show the equivalence terms of the relational WL algorithms:
Proposition G.3. Let G = (V, n) be a knowledge graph where of is a pairwise coloring. For all 2 0 and u, U V, we have that howl? (u, v) computed over G coincides with hrwl," ((u, computed over G = (V x V. E,,,R,R, C2).
Proof. For = O, we have howl? "G, mu,,)) 0) co((u, v)) frwl!" (u, v)). For the inductive case, we have that
hewl (G, v) = 7 (howl/0 (G, u, v), &f (((howl) (G, u, w),j) (w, e (NT(e) (e, e EQ())) -T(hrll (G², v)), (G² ([(hrrl (2)
()) (w,5) e I (e, E (v))t)
hhwll hrw](t+)) (G,,
Now we are ready to show the proof for Theorem G.1 For G = EV,ER 7), we consider G² = (V x E,E', R. cy). We start with item (1). Let A be a HC-MPNN with layers and initialization INIT satisfying INIT v and let Proposition G.2 item (1). For the initialization we have y on since y((u, u)) INIT(U, v, (g. (u), 2)). Thus,
S L. Let y be an initial feature map for G and be an HR-MPNN with layers
can proceed and apply Theorem 4.1 item (1) to Gº, y, and B and show that hrwl 3 h (
B,G,, which in
turns shows that howl!" = h A.G.
We then proceed to show item (2). Let L 2 0 be an integer representing a total number of layers. We apply Theorem 4.1 item (2) to G2 and obtain an initial feature map with y = Gn and an HR-MPNN B with L layer such that hrwl( f1 for all < l S L. We stress again that y and nj both satisfied generalizod target node distinguishability.. Now, let A the HC-MPNN from Proposition G.2 item (2). We finally have that hcwl! h A.G required. Note that the item (2) again holds for HCNet.
We are ready to prove the claim that HC-MPNN is more powerful than C-MPNN by showing the striet containment of their corresponding relational WL test, that is, howl, and rawly. In particular, we show that the defined howly is equivalent to rawlz defined in Huang et al. (2023) via Theorem G.4 Then, by Proposition A.17 in Huang et al. (2023), we have that rawl, x rawlz.
The intuition of Theorem G.4 is that for cach updating step, howly aggregates over all the neighboring edges, which contain both incoming edges and outgoing edges. In addition, howl2 can differentiate between them via the position of the entities in the edge. This is equivalent to aggregating incomnnng relation and outgoing inversod-relation rawl
Theorem G.4. For all knowledge graph G = R,,,),,) let ( = rawl, (1) (G), then howl, (G) = rawl; (6) (G) for all l 220. O.
Proof. First we restate the definition of hcwlz(G) and rawl (G) for convenience. Given that the query is always tail query, i.e., k 2, and given knowledge graph
(V, F., R, c), we have that the updating
29

---

Published in Transactions on Machine Learning Research (05/2025)
formula for hcwlp(G) is
howl!++ (u, v)) T (hewl2
(oool/((G,, (G, (u, o)), [(((hhwl2) 1 (G, (u, w)) (w,j) Ni(e)), p()) I (e,i) E(o)B)
r(hcwl? (0) (G, (u, v)), R (howl] (G, (u, w)) p(e)) (w, (e, E(v)B)
Note here that the second equation comes from the fact that the maximum arity is always 2. Then, recall the definition of rawlg. Given a knowledge graph G = (V,,, where 77 is a pairwise coloring only, we have
fawl+"(( rawlly 1) (G. (u, b)) ( ( (u, r)), & (rawl) (G, (u, w)) w E (N R)E)
where (v) is the relational neighborhood with respect to relation r E R. i.e., w E (,)x) if and only if r(e, w) E E. Equivalently, we can rewrite rawlz in the following form:
r (G, (u, v)) = (rawl (G, (u, v)), & (rawll (G,, (u, w)), ple)) (w.5) E (e,e -(0),i=1)
since we only want to obtain the node w as the tails entities in an edge, and thus the second argument of the (only) element in Mi(e) will always be 2.
For test T, we sometimes write T(G,u), u), T(G, u, v) in case of binary tests, to emphasize that the test is applied over G, and T(G) for the pairwise/ k-ary coloring given by the test. Let G = (V, E, R, c, n) be knowledge graph. The, note that G+ Et, R+) is the augmented knowledge graph where R+ is the disjoint union of R and {r r E RJ, and
E = (r, r((,,) E, u #0}
=+=
We can then define
E(u) ((e,t) (f)) e E}
Et (u) {(c,d) c(()) = v E Et}
(v) = {(e,d)
ee(i) = v, E
Finally, recall the definition of rawly (G, u, v) = rGt, u, v). We can write this in the equivalent form:
rawl; (++1) (G, (u, - (rawl) (8)
(G, (u. v)), 4 (rawl) (6) (G, (v, w)), (w, E E = r (rawl) (1) (G, (u, v)), (rawl) (1) (G, (u, w)) p(e)) (w,j) (e.)). E E(o),
U ll (rawl, (1) (G, (u, w)), p(e)) (w,j) E (ee(), E (V),
Now we are ready to show the proof. First we show that hawl, (G) = rawl;" (0) (G). We prove by induction the number of layers by showing that for some u, e E V and for some E,
(
hcwll (e+1) 1) (G. (u, v)) howl, ( (G, (u', o')) = rawl; (8) (G, (u, v)) = rawl (0) (G, (u',
By assumption, we know the base case holds. Assume that howl, ( (G) = rawl) (2) (G) for some 2 0, for a pair of nodo-pair (u, v), (w', (') E V2, Given that
hcwlf--1) (G, (u, v)) howle(t) (G, (v', v'))
By definition, we have that
T(howl?" (G, (u, v)), &l ( (G. (u, ww). | (w.)) e.C)) (hhowl1)) ( (G. (u', v')), if (howw! (0) (accml(((G, (ul, ((.)) E(v)
30

---

Published in Transactions on Machine Learning Research (05/2025)
Conditioning on i E {1, we can further decompose the set.
r(howl?) ( (G, (u, v)). Af (howl? ! (G, ()). (w.j) (c,)) E(),, (u. (w,J) (e))) i
U [(hwwl (G, ((
T [hholl (G. (u', of)) (howll) (G, (u', w)))),))e | ( (e) =11- 1B.
( U { (howll (G, (u', w)). (w,j) E (e))) E(u'), 2
Assune T is injective, the three arguments in t must match i.e, ( (u, b)) = howl 1 (G. (u', v')), and
If (howl) ( (G, (u, ((). (w.J) (i(e). (e. E E(U)), 1
K (howll (1)) (G,
(w..)) (e,())) F(v'), i =1]
We also have
R (howl," (G. (u, w)). (w,j) (e.e), E E(u), = 2 = (howll 2/ (G, (u', w.), p(e') (w.,) (v.. (e)
E F(v'), ;-)));22] 2
By inductive hypothesis, we have that rawl (G, (u, = raml (1) (u', e')). Thus, we have that (w.j) E Ni(e), E(()) E(c),
[(rawt: (9) (G. (w,,)),,..... [rawl)) (G, (u'..))))
(w.j) (w.)) (.(e)) E(c)), 11
E(u'),
and also
[(rawl: (8) (G, (u, (l.,w))...Pee) ( (s) i(v), [(rawt (9) (G, (u', (. I (w,j) (é,))) E(v),, 2}
First, for the first equation, we notice that
[(rawt: (8) (G. (u, (4,,,))))) (w. Ni(e). E(t), & 11
(rawl)) (4) (G. (u', (w.
(w.j) E (e)
if and only if
p(e)) (w,j) E Ni(e), e E(u), 13 = El (rawl) (2 (u, ()),
{l (rawl) (8) (G, (w', (w,j) Nii(e)) E E(v'), 1
since the filtered set of pair (w,j) are the same, and the (rawl) (2) (G, w)),
(G, and (rawl) (6) (G, (d),))))((ee) matches if and only if (rawl, (2) (0(( (u, w)), 2, p(e)) and (rawlt((1) (f) (G, (M),))) 2, p(e')) matches. This is because we simply augment. an additional position indicator 2 in the tuple as we fixed i i= 1, which does not break the equivalence of the statements.
Then, for the second equation, we note that
(raww) (6) (G, ().. I (1e,5) E Ni(e). E i-)), = (rawtt (8) (u), I (w,j) E (e
if and only if
(rrait (6) (G, (u, (MM Il [rawtt (1)
31

---

Published in Transactions on Machine Learning Research (05/2025)
since this time the filtered set of pair (w,j) also matches, but for the inverse relation. For any edge E(v) where (w, 1) Ne(w), the edge will be in form p(e)(w, v) as we is placed in the first position. Thus, there will be a corresponding reversed edge (v, w) E E" by definition. Then, by the same argument as in the second equation above, adding such an additional position indicator 1 on every tuple will not break the equivalence of the statement.
An important observation is that since the inverse relations are freshly created, we will never mix up these inverse edges in both tests. For rawly can distinguish these edges by checking the freshly created relation symbols r-1 E Rt R, whereas in howlz, the neighboring nodes from these edges are identified with the position indicator in the tuple.
Thus, we have that
[ (rawlz ( (G, (u, (w,J) E (())) = { (rawly (0) (v.,
and also
(rawl: (0) (G, (w, p(E)) (w,j) E (I). (rawl) (6)
(G, (1), p(e')) (w,j) E
Since 7 is injective, this is equivalent to
<rrawl (9) (G, (u, ()))(((((ll) (8) (G, (u, ()), (u, E (e
(rawl) (6)
(G, (u, w)) ((e)) (w,j) (M
r(rawl 11) (G, (u', d')). (0) (G, ||t/ (M(e))
(rawl) ()), (E
and thus, we have
7 (rawlt (2) (G. (u, u)), (rawl) (G) (u, w(). ((C)) (M(C).())))
Trrawt; (6) (G, (ul, )))), ('))) (4) (G, (n', w)), w)) p(e')) (we,5 (.)
and finally
rawl. (f-1) (f-)) (G, (u, v)) rawl) (1+)) (G, (u',
Note that since all arguments apply for both directions, the converse holds.
Remark G.5. We remark that the idea of HC-MPNNs restricted to tail predictions can be extended to arbitrary relational hypergraphs in order to compute k-ary invariants for any k. See Appendix H for a discussion.
H Computing k-ary invariants
In this section, we present a canonical way to construct a valid k-ary invariants. We start by introducing a construction of valid k-ary invariants termed as atomic types, following the convention by Grohe (2021).
H.1 Atomic types
Given a relational hypergraph G = EV,E, R) with / labels and tuple u (u1 .., uk) E Vb where 1,
we define the alomic lype of in G a vector:
(tp) E (0, (+)++(++++)) +
32

---

Published in Transactions on Machine Learning Research (05/2025)
where 1 is the number of colors and m is the arity of the relation with maximum arity. We use the first 1k bits to represent the color of the k nodes in u, another (2) bits to indicate whether node uy is identical to uj. We then represent the order of these nodes using m² bits and finally represent the relation with additional [R| bits.
Atomic types are k-ary relational hypergraph invariants as they satisfy the property that atpp( (G")( if and only if the mapping Ui H u1, ... up u/z is an isomorphism from the induced subgraph Glfui,. .ug] to "'. u/
H.2 Relational hypergraph conditioned local k-WL test
Now we are ready to show the k-ary invariants. Similarly to hewl2, we can restrict HC-MPNN to only carry out tail prediction with relational hypergraphs to make sure it directly computes k-ary invariants. Here, we introduce Relational hypergraph conditioned local k- WL test, dubbed howlg, which naturally generalized howly to relational hypergraph. Given it E Vk- and relational hypergraph G = (V, E, R. c, where Ç: V + D is a k-ary coloring that satisfied generalized target node distinguishability, i.e.,
((ū, u) # v(ū Vu E u, u & ú, Ç(ū, u.) # ((ū, uz) Vus, uj E u.u, u, # Uj.
howly updates k-ary coloring Ç for l 1 0:
howl (0) = ((ū, v))
howl k
(a, [ew]((+1)( (ū. v) = T (howl (ū. v). Hf (I(howl)) ((, (w.)) E
Again, we notice that howl, (2) computes valid k-ary invariants. We can also show that HC-MPNN restricted tails prediction, ie.,, for each query = (g, ū. where = k, is characterized by hewle.
Theorem H.1. Let G = (V, R, x) be relational hypergraphs where x is a feature map and Ç is a k-ary mode coloring satisfying generalized target nodes distinguishability. Given a query with q = [g. ú, k), then we have that:
For all HC-MPNNs restricted on tails prediction with L layers and initializations INIT with INIT = n, and 0 < l < L, , we have howl! = (0)
2. For all L > 0 there is an HC-MPNN restricted on tails prediction with L layers such that for all
0 0 l 2 L, we have howl! = =h
Note that we sometimes write a k-ary tuple (w1,".. , u&) E vk by (u, ux) where (u,,".. ; with a slight abuse of notation. We build an auxiliary relational hypergraph G* = (V*, E", R, R,,() where E' = [r((ū, vi).... (ū, vm)) r(vi.-.. um) e a HC-MPNN and B is an HR-MPNN, we E.r E R}, and < is a node coloring ce((ū,))) = v), If
Proof. The proof is very similar to that in Theorem
(k-1)
write h (1) A v) = h( and h v)) := (()((ū v)) for the features computed by and B over G and Gk, respectivcly. Again, we write N,C and E(u) to emphasize that the positional neighborhood, well as the hyperedges containing node v, is taken over the relational hypergraph G, respectively. Finally, we say that an initial feature map y for Gk satisfies generalized target node distinguishability if
v( u)) # y(ūū))) v)) Vu E u, v & ú, v((ū, u:)) # y(ūū, uz)) Vui, uy E ū, u4 # Uj-
As a result, we have the following equivalence between HR-MPNN and HC-MPNN restricted on tail predic- tion with the relational hypergraph.
Proposition H.2. Let G = (V, E, R, x, () be a knowledge graph where is a feature map, and Ç a k-ary nodes coloring. Let q R, then:
33

---

Published in Transactions on Machine Learning Research (05/2025)
1. For every HC-MPNN A with L layers, there is an initial feature map y for G an HR-MPNN B with layers such that for all & and u, U E V, we have h (e)) (,,,(ū,,)) v) = h h ((ū,
2. For every inilial feature map y for Gh salisfying generalized larget mode disslingussabiiiity and every HR-MPNN B with I. layers, there is a HC-MPNN A with L layers such that for all O S l S L. and (8)
(vu,, v) Vk, we have h h. (., BB,G* ((ū,))))
Proof. We first show item (1). Consider the HR-MPNN B with the same relational-specific message MSG,, aggregation AGG, and update functions UP as A for all the L layers. The initial feature map y is defined as ((ūū v)) [NIT(U, q), where INIT the initialization function of A. Then, by induction on mumber of layer L, we have that for the base case f 0, A (ū, v) INIT(U, q) y(( v)) = hg ((ū, o)).
For the inductive case, assume h (ū, v) (8) ((ū,)) v)), then
A (2+1) (ū, UP 11 ūū v), AGG (1 (ü, v), (MSG [1hh)) (2) (ü, w) (w,j) E (o)))) (e, (W))))
Up (hlg 10 ((ū, u)), AGG (1g (0) v)),
(Ms) (1(h)) ((ū, (l,, E (e) (e, E E (0)B)
hg (1+1) (ū, u)).
To show item (2), we consider A with the same seleticnal-ppecific message MsG,, aggregation AcG, and update functions UP as B for all the L layers. We also take initialization function INIT such that INIT(v, q) y((ū,v) v)). Then, we can follow the same argument for the equivalence as item (1).
Similarly, we can show the equivalence in terms of the relational WL algorithms with howlg:
Proposition H.3. Let G all l 2 0 and (ū, v) E V&, we have that hewl ( (ū, v) computed over G coincides with hrwl ((ū, v)) computed over G = (V*, E,,,R,,,,, R,cc).
be relational hypergraph where Ç is k-ary node coloring. For
Proof. For = we have hewl, ( (G,ū, ((ū, v) c<((ū, v)) hrwl (G,,( For the inductive case, we have that
( howl ((+1) () (G,ū,) T (hawl (G, ū, v), &f (1(hewl (G, (G,ū,w)))) I (w.j) (193,, (e. e (v)B)
=T (T(wllff ( (G*, (ū,
[[((rrl)) (f ("."( e (e),, (e, e (o(((())
hrwi hrwl vū,
Now we are ready to show the proof for Theorem H.1 For relational hypergraph G = (V, R, 9), we
consider G² (V*, E', R2) defined carlier. We start with item (1). Let A be HC-MPNN with L
layers and initialization INIT satisfying INIT = and let 0 < 8 < L. Let be an initial feature map for Gk and B be an HR-MPNN with L layers in Proposition H.2 item (1). For the initialization we have cç
since y(ūū, v)) = INIT(U, q)- Thus, we can proceed and apply Theorem 4.1 item (1) to Gh y, and B and show that hrw(( < h (2)
B, which in turns shows that howl (2) h (8)
A.G-
34

---

Published in Transactions on Machine Learning Research (05/2025)
Table 6: Model asymptotic runtime complexities.
Model
Complexity of a forward pass
Amortized complexity of a query
HR-MPNNs
(L (v
Fld OLL( F +
[R]lV] +
d²
d))
HC-MPNNs
Eld+
O ( m Fld
+ d)))
We then proceed to show item (2). Let L 2 0 be an integer representing total number of layers. We apply Theorem 4.1 item (2) to G and obtain an initial feature map with = <ç and an HR-MPNN B with L layer such that hrwl, = 18.." for all 0 < l < L. We stress again that y and Ç both satisfy generalized target node distinguishability.. Now, let A be the HC-MPNN from Proposition H.2. item (2).
Thus, hewl (t) (8)
A.G as required. Again, we note that the item (2) holds for HCNet.
7
Complexity analysis
In this section, we discuss the asymptotic time complexity of HR-MPNN and HC-MPNN. For HC-MPNN, we consider the model instance of HCNet with gf being a query-independent diagonal linear map. For HR-MPNN, we consider the model instance with the same updating function UP and relation-specific message function MsG, as the considered HCNet model instance, referred to as HRRNet:
T 1d
h (c+1) a ((())
(
(ojria (2) + (1 (0 O + +b(0). (o,))E
Σ
R, c), we denote EV, R to be the size of vertices, edges, and relation lypes. d is the hidden dimension and m is the maximum arity of the edges. Additionally, we denote L to be the total number of layers, and & to be the arity the query relation q E R in the query q == (q, t).
Notation. Given relational hypergraph G (V. (V,
Analysis. Given a query q = (4, ú),,, the runtime complexity of single forward pass of HCNet is O[L(m|E [V())) since for each message, need O(d) for the relation-specific transformation, and we have m| E|E) total amount of message in cach layer. During the updating function, we additionally need a linear transformation for each aggregated message as well as a self-transformation,, which costs O(d) for each node. Adding them up, we have [(m]Rld+ + (VI2) cost. for each layer, and thus ((L(m) Fldd + (Vid)) in total.
Note that this the same as the complexity of HRNet since the only differences lie in initialization methods, which is ((Vld) cost for HCNet. In terms of computing single query, the amortized complexity of HCNet E is OLL( M + d))) since in each forward pass, [V] number of querics are computed at the same time. contrast, HRNet computes |V|** query as once has representations for all nodes in the relational hypergraph, it can compute all possible hyperedges by permuting the nodes and feeding them into the k-ary decoder. We summarize the complexity analysis in Table G
Discussion with space complexity of positional encoding. Note that models designed for inductive inference over knowledge graphs, such NBFNet (Zhu et al., 2021), typically augments the original knowl- edge graph edges with their inverses by introducing inverse relations (i.e., for each r(a, b), an edge of the form (b, a) is added). This is to ensure that messages flow in both directions between two nodes.
To simply extend this idca relational hyperodges, we need the full set of directional interactions a hyperedge of arity k, which requires enumerating all kl permutations of the node ordering, resulting in -!-1 additional hyperedges per original one. If each permutation is treated a distinct. "augmented" relation,
35

---

Published in Transactions on Machine Learning Research (05/2025)
the model must store separate relation embedding for each of these permutations. Assuming uniform arity k and embedding dimension d, this leads to space complexity of |R]kdd.
Note that such an approach is only practical when k = 2, as in traditional knowledge graphs, where it doubles the number embeddings. For relational hypergraphs with larger k, however, this introduces an exponential increase storage and quickly becomes infeasible.
In contrast, our method avoids this explosion by employing positional encodings to distinguish among node permutations within hyperedge. This allows us to retain single relation embedding per relation, with an additional k-length positional embedding shared across all relations, resulting in total space complexity of Rld+ kd. This scales linearly with k; enabling efficient modeling of high-arity hyperedges without sacrificing expressive power.
J Details in synthetic experiments
Dataset construction. We construct HyperCycle, a synthetic dataset that consists of multiple relational hypergraphs with relation R = (ro. r2]- Each relational hypergraph G is parameterized by hyperpa- rameters: the number of nodes n which is always a multiple of 4, and the arity of each edge Given such (n, k) pair, we generate the relational hypergraph G(n, k) = (V (n, k), E(n, k), R(n, k)) where
V(n, k:) = {=1: ... .n)
F(n,k) {r( mod 2)+1 (2((+)) mod 0 < 1
R(n,k) {ro.
We generate the dataset by choosing (8, 12, 16, 20) and k = (3, 4,5, 6, 7]. We then randomly pick 70% of the generated graphs the training set and the remaining 30% as the testing set.
Model architectures. We considered two model architectures, namely an HC-MPNN instance HCNet:
h (0) r/q
Elemm
* (p; + 2q)
ift
h (E+1) (W())
Σ
(Ofzi
(a (0) e(iiia (1 a (p))))))) 3 mn!o) +b(0).
(e,))
and a corresponding HR-MPNNs instance called HRNet that shares the same update, aggregate, and relation- specific message functions as HCNet, defined as follow:
h 1d
h ((+1) = σ (w())
(0sHi (al9) (0) 6G) + (1-a 0 + bl0)) (c,))
Σ
Note that a stands for the ReLU activation function in both models. We additionally use binary MLP decoder for HRNet, which takes the concatcnation of the final representation for cach entity in the query, logether with the learnable query vector 2n to oblain the final probability.
Experimental details. For both models, we use 7 layers, each with 32 hidden dimensions. We configure the learning rate to be lc-3 for both models and train them for 100 epochs.
K Scalability and custom Triton kernel
Scalability is generally concern for inductive link prediction since link prediction bet ween a given pair of nodes relies heavily on the structural properties of these nodes (due to the lack node features) which nccessitates strong encoders that go beyond the power of 1-WL. This is more dramatic for relational hyper- graphs since the prediction now relies on the structural properties of nodes and any model will suffer from scalability issues if & becomes large. With that being said, our approach remains feasible for the benchmark
36

---

Published in Transactions on Machine Learning Research (05/2025)
Table 7: Average degree relational hypergraphs in the experiments.
WP-IND
JF-IND MFB-IND FB-AUTO WikiPeople
Average degree
1.03
1.36
104.5
2.16
6.06
datasets, but we think it is important for future work to scale up these models for larger datasets, much like it has been done for classical GNNs (Hamilton et al. 2017 Zhu et al. 2023).
To resolve this empirically, we have included custom implementation via Triton kernel in our codebase to account for the message passing process on relational hypergraphs, which on average halved the training times and dramatically reduced the space usage of the algorithm (5 times reduction on average). The idea is not materialize all the messages explicitly as in Py'orrch geometric (Fey & Lenssen 2019), but directly write the neighboring features into the corresponding memory addresses. Compared with materializing all hyperedge messages which takes (A))E)) where k is the maximum arily, computing with Triton kernel only is O(VI) in memory. This will enable fast and scalable message passing on relational hypergraphs, both on HR-MPNNs and HC-MPNNs.
L On adding node features
On the surface, it seems that HC-MPNNs does not directly take node features into account. This is because in the task of link prediction on relational hypergraphs, no node features are explicitly provided to begin with, and thus we did not assume the presence of node features in this particular task setting. However, it is relatively straightforward to account for node features by simply concatenating the node feature a, on top of the current representation h, to obtain h [he]] Indeed, the only requirement for HC-MPNNs in the initialization is to satisfy generalized target node distinguishability, and thus concatenating node features will preserve this property. As result, all theoretical results can be directly applied to HC-MPNNs with node features. It is worth noting that this concatenating technique has already been applied in /Zhan et al. (202I) on knowledge graphs with node features and has proven to be successful. Additionally, this technique is also mentioned in Galkin et al. (2024) for link prediction with knowledge graphs using conditional message passing.
M Impact on the density of the relational hypergraphs
To further analyze the impact on the structure and density, we present the average degree of (training) datasots in Table 7 Observe that even though MFB-IND is a very dense hypergraph, HCNets can still manage to double the metrics compared to existing models. Furthermore, we highlight the performance of HCNets in sparse hypergraph settings, which are more representative of many real-world scenarios. Remark- ably, HCNets maintain competitive performance even under these challenging conditions, underscoring their adaptability and effectiveness across wide range of graph density regimes. These findings highlight the versatility of HCNets in handling diverse hypergraph structures.
N Further experiment details
We report the details of the experiment carried out in the body of the paper in this section. In particular, report the dataset statistics of the inductive link prediction task in Table g and of the transductive link prediction task in Table g We also report the hyperparameter used for HCNet in the inductive link
prediction task at Table 10 and transductive link prediction task at Table I1 respectively.
We present the dataset statistics and hyperparameter choices in Table 17 and Table 18 respectively. We also show the complete tables for the ablation study mentioned in Table 13 and Table the detailed definitions
of initialization and positional encoding considered in Table 19 and Table 20 respectively.
37

---

Published in Transactions on Machine Learning Research (05/2025)
Table 8: Dataset statistics of inductive link prediction task with relational hypergraph.
Dataset
# seen vertices
# train hyper- edges
# unseen vertices
# relations
# features
# max arity
WP-IND
4,463
4,139
100
32
37
4
JF-IND
4,685
6,167
100
31
46
4
MFB-IND 3,283
336,733
500
12
25
3
Finally, we report the execution time and GPU usages for epochs of HCNets on all datasets considered in the paper with corresponding hyperparameters in Table 21 See further discussion of scalability in Appendix K For the RD-MPNNs training, consider learming rate of 0.1, dimension of 200, and 10 negative samples for training on all inductive datasets. In the experiments, all relational hypergraphs do not contain node features. We present a detailed discussion and strategy in Appendix L for HC-MPNNs to be applied on relational hypergraphs with node foatures.
We adopt the partial completeness assumption (Galárraga al., 2013) on relational hypergraphs, where we randomly corrupt the t-th position of k-ary fact q(u,,-.. ux) each time for 1 1 k. HCNets minimize the negative log-likelihood of the positive fact presented in the training graph, and the negative facts due to corruption. We represent query q ū, () as the fact g(u1,'.. .uk given corrupting (-th position, and represent its conditional probability as p(vlg) = o(f(h(())) where e V is the considered entity in the I-th position, L is the total number of layer, a the sigmoid function, and I is a 2-layer MLP. We then adopt celf-adversarial negative sampling (Sun et al. 2019 by sampling negative triples from the following distribution:
C(v q) - logg(( q)
Σ wia log(1 - p(c) | q))
where a is the adversarial temperature as part of the hyperparameter, n is the number of negative samples for the positive sample and of is the i-th corrupted vertex of the negative sample. Finally, w; is the weight for the i-th negative sample, given by
log((1 p(v 9))
Wi.a Softmax
a
Table 9: Dataset statistics of transductive link prediction task with relational hypergraph on FB-AUTO, WikiPeople, JF17K, and MFB15K with respective arity.
Dataset
FB-AUTO
WikiPeople
JF17K
MFB15K
[V]
3,410
47,765
29,177
10,314
[R]
8
707
327
71
#train
6,778
305,725
61,104
415,375
#valid
2,255
38,223
15,275
39,348
#test
2,180
38,281
24,915
38,797
# arity=
3,786
337,914
56,322
82,247
# arity=3
0
25,820
34,550
400,027
arity= 4
215
15,188
9,509
26
arity 5
7,212
3,307
2,267
11,220
38

---

Published in Transactions on Machine Learning Research (05/2025)
Table 10: Hyperparameters for inductive experiments of HCNet.
Hyperparameter
WP-IND
JF-IND
MFB-IND
DL)
5
4
GNN Layer
Hidden Dimension
128
256
32
Depth
2
2
Decoder Layer
Hidden Dimension
128
256
32
Optimizer
Adam 5e-3
Adam 1e-2
Adam
Optimization
Learning Rate
5e-3
Batch size
32
1
#Negative Sample
10
10
10
Epoch
20
20
10
Learning
#Batch Per Epoch
10000
Adversarial Temperature
0.5
0.5
0.5
Dropout
0.2
0.2
0
Accumulation Iteralion
1
32
Table 11: Hyperparamcters for transductive experiments of HCNet.
Hyperparamcter
FB-AUTO
WikiPcople
JF17K
MFB15K
Depth(L)
6
GNN Layer
Hidden Dimension
128
64
64
64
Depth
2
2
2
2
Decoder Layer
Hidden Dimension
128
64
64
64
Optimizer
Adam
Adam 1e-3
Adam 5e-3
Adam
Optimization
Learning Rate
1e-3
1e-3
Batch size
32
16
32
#Negative Sample
32
50
32
Epoch
20
6
Learning
# Batch Per Epoch
5000
Adversarial Temperature
0.5
0.5
0.5
0.5
Dropout
0.2
0.2
0.2
0.2
Accumulation Iteration
32
1
Table 12: Results of inductive link prediction experiments. We report averaged MRR, Hits@1, and Hits@3 (higher is better) test sets together with its standard deviation.
WP-IND
JF-IND
MFB-IND
MRR
Hits@1
Hits@3
MRR
Hits@1
Hits@3
MRR
Hits@1
Hits@3
HGNN
0.072
0.045
0.112
0.102
0.086
0.128
0.121
0.076
0.114
HyperGCN
0.075
0.049
0.111
0.099
0.088
0.133
0.118
0.074
0.117
G-MPNN-sum
0.177
0.108
0.191
0.219
0.155
0.236
0.124
0.071
0.123
G-MPNN-mean
0.153
0.096
0.145
0.112
0.039
0.116
0.241
0.162
0.257
G-MPNN-mat
0.200
0.125
0.214
0.216
0.147
0.240
0.268
0.191
0.283
RD-MPNN
0.304
0.238
0.328
0.402
0.308
0.453
0.122
0.082
0.125
HCNet
0.414
0.352
0.451
0.435
0.357
0.495
0.368
0.223 +
0.417
+
+
+
+
+
0.005
0.004
0.005
0.017
0.023
0.014
0.015
0.014
0.022
39

---

Published in Transactions on Machine Learning Research (05/2025)
Table 13: Results of ablation study experiments on initialization. (higher is better) test sets.
We report MRR, Hits@1, and Hits@3
INFT
WP-IND
JF-IND
Zg
p
MRR
Hits@1
Hits@3
MRR
Hits@1
Hits@3
0.388
0.324
0.421
0.390
0.295
0.451
V
0.387
0.321
0.421
0.392
0.302
0.447
V
0.394
0.329
0.430
0.393
0.300
0.456
V
0.414
0.352
0.451
0.435
0.357
0.495
Table 14: Results of ablation study experiments positional encoding. Hits@3 (higher is better) test sets.
We report MRR, Hits@l, and
WP-IND
JF-IND
PE
MRR
Hits@1
Hits@3
MRR
Hits@1
Hits@3
Constant
0.393
0.328
0.426
0.356
0.247
0.428
One-hot
0.395
0.334
0.428
0.368
0.275
0.432
Learnable
0.396
0.335
0.425
0.416
0.335
0.480
Sinusoidal
0.414
0.352
0.451
0.435
0.357
0.495
Table 15: Transductive link prediction experiments FB-AUTO and WikiPeople
FB-AUTO
WikiPeople
MRR
Hits@l
Hits@3
Hits@10
MRR
Hits@1
Hits@3
Hits@10
M-DistMult
0.784
0.745
0.815
0.845
m-CP
0.752
0.704
0.785
0.837
TransH
0.728
0.727
0.728
0.728
RAE
0.703
0.614
0.764
0.854
0.253
0.118
0.343
0.463
NaLP
0.672
0.611
0.712
0.774
0.338
0.272
0.362
0.466
INaLP+
0.729
0.645
0.748
0.826
0.339
0.269
0.369
0.473
HINGE
0.678
0.630
0.706
0.765
0.333
0.259
0.361
0.477
NeuInfer
0.737
0.700
0.755
0.805
0.350
0.282
0.381
0.467
HypE
0,804
0.774
0.823
0.856
0.263
0.127
0.355
0.486
RAM
0.830
0.803
0.851
0.876
0.363
0.271
0.455
0.500
BoxE
0.844
0.814
0.863
0.898
HyperMLN
0.831
0.803
0.851
0.877
HyConvE
0.847
0.820
0.872
0.901
0.362
0.275
0.388
0.501
ReAIE
0.873
0.852
0.886
0.909
RD-MPNN
0.810
0.714
0.870
0.888
HJE
0.872
0.848
0.886
0.903
0.450
0.375
0.487
0.582
HyCubE
0.881
0.860
0.894
0.918
0.448
0.368
0.490
0.592
HyPlanE
0.866
0.843
0.880
0.909
0.402
0.323
0.443
0.549
0.871
0.842
0.892
0.922
0.421
0.344
0.457
0.565
HCNet
0.005
+ 0.007
+ 0.003
+ 0.004
0.004
+ 0.005
+ 0.005
+ 0.007
40

---

Published in Transactions on Machine Learning Research (05/2025)
Table 16: Transductive link prediction experiments JF17K and MFB15K
JF17K
MFB15K
MRR
Hits@1
Hits@3
Hits@10
MRR
Hits@1
Hits@3
Hits@10
m-DistMult
0.463
0.372
0.510
0.634
0.705
0.633
0.740
0.844
m-CP
0.392
0.303
0.441
0.560
0.680
0.605
0.715
0.828
TransH
0.444
0.370
0.475
0.581
0.623
0.531
0.669
0.809
RAE
0.396
0.312
0.433
0.561
NaLP
0.366
0.290
0.334
0.516
+
0.449
0.370
0.484
0.598
HINGE
0.473
0.397
0.490
0.618
NeuInfer
0.451
0.373
0.484
0.604
HypE
0.494
0.408
0.538
0.656
0.777
0.725
0.800
0.881
RAM
0.539
0.463
0.573
0.690
BoxE
0.560
0.472
0.604
0.722
0.761
0.702
0.791
0.877
HyperMLN
0,556
0.482
0.597
0.717
HyConvE
0.590
0.478
0.610
0.729
ReAIE
0.559
0.482
0.594
0.705
0.801
0.755
0.823
0.901
RD-MPNN
0.512
0.445
0.573
0.685
HJE
0.590
0.507
0.613
0.729
HyCubE
0.584
0.508
0.616
0.730
HyPlanE
0.569
0.496
0.600
0.708
0.540
0.440
0.595
0.730
0.759
0.693
0.796
0.884
HCNet
0.002
- 0.001
+ 0.007
+ 0.006
- 0.003
+ 0.002
0.005
+ 0.007
Table 17: Dataset statistics for the inductive relation prediction experiments. #Query* is the number of queries used in the validation set. In the training set, all triplets are used as queries.
Train & Validation
Test # #Triplet
Datasct
# Relation
# Nodes
#Triplet
#Query*
#Nodes
#Query
U1
9
2,746
5,410
630
922
1,618
188
10
6,954
15,262
1,838
2,757
4,011
441
WNISRR
03
11
12,078
25,901
3,097
5,084
6,327
605
04
9
3,861
7,940
934
7,084
12,334
1,429
U1
180
1,594
4,245
489
1,093
1,993
205
200
2,608
9,739
1,166
1,660
4,145
478
7317k-237
03
215
3,668
17,986
2,194
2,501
7,406
865
014
219
4,707
27,203
3,352
3,051
11,714
1,424
41

---

Published in Transactions on Machine Learning Research (05/2025)
Table 18: Hyperparameters for binary inductive experiments with HCNet.
Hyperparameter
WN18RR
FB15k-237
D)
6
GNN Layer
Hidden Dimension
32
32
Depth
2
2
Decoder Layer
Hidden Dimension
64
64
Optimizer
Adam
Adam
Optimization
Learning Rate
5e-3
50-3
Batch size
32
32
#Negative Samples
32
32
Epoch
30
Learning
#Batch Per Epoch
Adversarial Temperature
0.5
0.5
Dropout
0.2
0.2
Accumulation Iteration
1
Table 19: Definition of INIT in the ablation study of initialization. Here, = (4, ü, and d is the hidden dimension before passing to the first layer.
INIT
h (0) v/q
Z
p:
rss I lu=u 1d
igtt n=w, * pi
Egte Lomu; # 2q
E 1 v= * *(p + Zgg
Table 20: Definition of p; in the ablation study of positional encoding. Here, I is the one-hot vector of d dimension where only the index i has entry 1 and the rest 0. Note that d is the hidden dimension before passing to the first layer. p a d-dimensional learnable vectors. Pa. is the j-th index of position encoding P;, and d is the dimension of the vector p..
PE
Constant
P: 1d
One-hot
p: Id
Learnable
Sinusoidal
Pt.2j sin (100003574) Ps(2211) cos (1000893/4)
Table 21: Comparison of the execution time of 1 epoch for inductive and transductive link prediction task with relational hypergraph using a single A10 GPU. Note that we use batch size = 1 during the testing for all models, and 10k steps for MFB-IND during the training of HCNets.
WP-IND
JF-IND
MFB-IND
FR-AUTO
WikiPeople Train
Train
Test
Train
Test
Train
Test
Train
Test
Test
RD-MPNN
2sec
3.5min
2sec
3min
14min
38min
3sec
35min
HCNet
3.5min
18sec
8min
10sec
80min
3.5min
4.5min
4min
3hr
2hr
42


Reviews:
[{"review_id": "OIBUaZ7YWB", "reviewer": "Reviewer_d8jd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is an interesting and fundamental topic in graph learning. Regarding the contributions, the authors analyze HR-MPNNs, the predominant link prediction architectures for relational hypergraphs. They introduce HC-MPNNs, incorporating more expressive architectures such as HCNets, to address the limitations of HR-MPNNs. Empirical analysis supports theoretical insights. HC-MPNN outperforms baselines in both inductive and transductive link prediction tasks. Ablation studies validate model design choices. A synthetic experiment validates HC-MPNN’s expressive capabilities.\n\nAlthough the manuscript is well presented, there are some concerns or weakness that the authors should conduct some deep dive to improve the work for another round of review:\n    - For a self-contained work, all notations should be introduced before their usage. For instance, in Section 4, the notation \\rho(e) was introduced but not defined clearly, and it was also used Section 4.1, where it was employed to formulate hrwl_1. \n    - In the related work, the authors should ensure that they are up-to-date with the latest advancements in hypergraphs and GNNs for link prediction. The work discussed in Section 2 may not adequately cover the most recent developments.\n    - In Theorem 5.1, it is asserted that HC-MPNN possesses greater strength due to its initialization. However, it is unclear why this initialization matters and cannot be overwritten through a sufficient inference/training that coverages to attain an optimal state, thereby rendering HC-MPNN weaker.\n    - In Section 6, for the Hits@k metric, the authors should provide a rationale for employing distinct values for k in inductive and transduction experiments.\n    - As mentioned in Section 6.3, certain baseline methods, such as A*Net and NDBNet, share a similar concept to HCNet and achieved satisfactory performance. Therefore, it is worth to emphasizing the uniqueness/novelty of the proposed method, particularly if it is not significantly different from these existing methods.\n    - In Section 6.2, some baseline methods, such as ReAIE, attained competitive results in multiple datasets and metrics, notably when comparing HCNet and ReAIE. The authors should provide insights to justify the observation of HCNet’s continued superiority.\n    - In Table 3, the authors present the outcomes of a binary inductive experiment conducted on a knowledge graph. While the apparent advantage of the proposed method appears slightly diminished compared to two baseline methods, DBFNet and A*Net, it remains competitive. It is commendable that the authors acknowledge that these methods are based on conditional message passing and share a similar concept to HCNet. However, it remains unclear what the disparity in message function outcomes is responsible for the gap and why the proposed method cannot utilize that function.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This research paper compared HR-MPNNs and HC-MPNNs for link prediction using relational hypergraphs. It evaluated their expressiveness in terms of relational WL and logical expressiveness. The authors proposed a simple yet effective HC-MPNN model, HCNet, and showed its superior performance on inductive link prediction tasks. Transductive link prediction and synthetic experiments supported this finding. However, computational complexity and limitations to link prediction are acknowledged. Future research could explore complex query answering on fully relational data. This study extends link prediction success to relational hypergraphs, effectively modeling higher arity relations using GNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "n/a", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "08tdiOEgbf", "reviewer": "Reviewer_i8ST", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have some concerns/questions about the baselines and datasets.\n- The latest baselines used are from 2023. Are there some newer baselines, like those published in 2024, that can be used to compare with?\n- It would be better to conduct experiments on larger datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- The authors present a novel framework that leverages graph neural networks for relational hypergraphs, extending link prediction beyond traditional knowledge graphs to more complex k-ary relationships. \n- The paper is well-written and clearly motivated.\n- The authors give detailed theoretical proofs, and the experimental results show that the proposed method achieves state-of-the-art results in both inductive and transductive link prediction on relational hypergraph benchmarks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Include newer baselines and larger datasets\n- Correct the **typo**: For the last section, \"Broder impact\". It should be *broader impact*", "broader_impact_concerns": "Sufficiently addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9GghZl1S2B", "reviewer": "Reviewer_8Rrz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper concerns an important problem and is very well written\n2. The model architectures are grounded by elaborate theoretical analysis.\n\n\nWeakness:\n1. **Missing related work:** The writing of the paper gives an impression that that authors are the first one to tackle this problem which is not clearly the case. For instance: this paper from ISWC 2021 https://link.springer.com/chapter/10.1007/978-3-030-88361-4_5 developed methods to use hyper relational facts. The paper needs to be sufficiently discussed and used a baseline. \n\n2. **Missing hyper relational datasets:** It is not clear if the datasets used in the experiments actually contain hyper relational facts. Such datasets can be found in above mentioned paper and the follow-up paper in IJCAI (https://www.ijcai.org/proceedings/2022/0731.pdf).\n\n3. **Limited Contribution:** In my humble opinion the adaptions toe existing techniques do not lead to sufficient contribution. For instance, it is not clear if including the position embedding directly in HCN would not lead to similar improvements. It is also not clear how training is actually performed. If the initialisations have to be made per query does one training batch consists of one query.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates the problem of inductive link prediction with relational hypergraphs in which each relation is defined over k nodes. The paper extends the message passing operations of a GNN over hyperedges.  By introducing query specific initializations the authors further develop hyper graph conditional networks. Theoretical analysis of the expressive power of the develop model architectures is provided. Experiments are conducted to showcase the effectiveness of developed approach.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please consider other works on link prediction in hyperrelational knowledge graphs such as https://link.springer.com/chapter/10.1007/978-3-030-88361-4_5  from the knowledge graph community and discuss teh strengths and weaknesses of your work as compared to such related works. \n\n2. provide experimental results with more datasets such as  WD50K (33), WD50K (66), and WD50k (100)  which contain hyper relational facts.\n\n3. Provide elaborate details on how training of the hyper graph conditional networks is conducted.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As acknowledged by two out of three reviewers, the authors clarified all the main issues raised by them. One reviewer expressed in a very  concise review a not so positive opinion on the paper, raising issues about originality of the proposed work. However, this reviewer did not reply to the rebuttal of the authors, that I personally believe addressed the raised issues in a convincing way.
Decision: Accept (poster)