Message Function Search for Hyper-relational Knowledge Graph
Authors: Shimin Di
Lei Chen
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Neural Network
Hyper-relational Knowledge Graph
Knowledge Base Embedding

Abstract: Recently, the hyper-relational knowledge graph (HKG) has attracted much attention due to its widespread existence and potential applications. The pioneer works have adapted powerful graph neural networks (GNNs) to embed HKGs by proposing domain-specific message functions. These message functions for HKG embedding are utilized to learn relational representations and capture the correlation between entities and relations of HKGs. However, these works often manually design and fix structures and operators of message functions, which makes them difficult to handle complex and diverse relational patterns in various HKGs (i.e., data patterns). To overcome these shortcomings, we plan to develop a method to dynamically search suitable message functions that can adapt to patterns of the given HKG. Unfortunately, it is not trivial to design an expressive search space and an efficient search algorithm to make the search effective and efficient. In this paper, we first unify a search space of message functions that enables both structures and operators to be searchable. Especially, the classic KG/HKG models and message functions of existing GNNs can be instantiated as special cases in the proposed search space. Then, we design an efficient search algorithm to search the message function and other GNN components for any given HKGs. Through empirical study, we show that the searched message functions are data-dependent, and can achieve leading performance in link/relation prediction tasks on benchmark data sets.

Under review as a conference paper at ICLR 2022
MESSAGE FUNCTION SEARCH RELATIONAL KNOWLEDGE GRAPH
FOR
HYPER-
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, the hyper-relational knowledge graph (HKG) has attracted much attention due to its widespread existence and potential applications. The pioneer works have adapted powerful graph neural networks (GNNs) embed HKGs by proposing domain-specific message functions. These message functions for HKG embedding are utilized learn relational representations and capture the correlation between entities and relations of HKGs. However, these works often manually design and fix structures and operators of message functions, which makes them difficult handle complex and diverse relational patterns in various HKGs (i.e., data patterns). To overcome these shortcomings, we plan to develop method to dynamically search suitable message functions that can adapt to patterns of the given HKG. Unfortunately, it is not trivial to design an expressive search space to enable the powerful message functions being searched, especially the space cannot be too large for the sake of search efficiency. In this paper, we first unify a search space message functions search both structures and operators. The message functions of existing GNNs and some classic KG/HKG models can be instantiated as special cases of the proposed search space. Then, we leverage a search algorithm search the message function and other GNN components for any given HKGs. We empirically show that the searched message functions are data-dependent, and can achieve leading performance in link/relation prediction tasks on benchmark HKGs.
INTRODUCTION
Knowledge base (KB) (Auer et al., 2007) an important tool to organize and explore human knowledge, thereby promoting series of applications. e.g., question answering (Lukovnikov et al., 2017) and recommendation system (Cao et al., 2019). Generally, the KB stores the n-ary fact r(e,,... c,, (n is arity) that represents the relation
R between real-world entities e; F. To manipulate large scale KBs, KB embedding (Nickel et al., 2015; Wang et al., 2017) proposes to encode the set of relations R and entities into a d'-dimensional vector space E R [ E E R El xd In last decades, the research community mainly focuses embedding knowledge graphs (KGs) that only contain binary facts (r(E1, e2)] e.g., isCaptialCs (Beijing, China) Among kinds of KG embedding models (Rossi et al., 2021), tensor models (Lacroix et al., 2018; Balazevic et al., 2019) propose to represent a KG into 3-order tensor and decompose tensors into R and E, which achieve outstanding empirical performance and theoretical guarantees. Recent studies start to learn embeddings from n-ary facts (n 2 2) because π-ary facts are widespread in KBs, e.g., Spock, StarTrekl). For example, more than 30% of entities in Freebase (Bollacker et al., 2008) involve facts with higher arity (Wen et al., 2016). Therefore, it is necessary to investigate the more general case of KGs, facts with mixed arities S (r(ei....,e..
pl ellyCharrccterie
reeonardiimon
en)
(2...., ... }}} named as hyper-relational KGs (HKGs).
Unfortunately, is hard to extend powerful tensor models from the case of fixed arity (e.g.. KG) to the case of mixed arities (i.e., HKG). That is because tensor can only model a set of facts under the same arity. Instead, some pioneer works (Yadati, 2020; Galkin et al., 2020) demonstrate that the multi-relational hypergraph (MRHG) could be more natural way to model HKGs (see Appx. A for more details). Let entities E and relations R be nodes and edge types in the MRHG GEE, R. S), respectively. The length of MRHG's edge (ei....., ,x) (hyperedge) could be variant, which can represent facts with various arities n. And hyperedges can be labeled by multiple edge types r R like r(ei,...,ea. S. Under the MRHG modeling, these works adapt powerful graph

---

Under review as a conference paper at ICLR 2022
neural networks (GNNs) (Kipf & Welling, 2016; Hamilton et al., 2017) to embed HKGs (Yadati, 2020; Galkin et al., 2020). Generally, GNNs learn node embeddings by passing messages (c.g. the node features) from adjacent nodes to the center node. But in scenarios of HKGs, it is important to know the type of edge (relation) that connects several entities. Therefore, existing GNNs for HKG embedding design several domain-specific message functions to learn relational representations R by capturing the interaction between entities E' and relations R.
Existing works manually design and fix the structures and operators of message functions. However, such rigid message function designs are not conducive to pursuing high empirical performance, as relations usually have distinct patterns in various KGs/HKGs. For example, the message function of G-MPNN (Yadati, 2020) adopts the inner product way like DistMult (Yang et al., 2015) to compute the correlation between entities and relations, which has been proven to only cover symmetric relations (Kazemi & Poole, 201 8). Its performance may not be good if there are many non-symmetric relations existed (see Appx. B. It may a potential solution to design a universal message function to cover many relational patterns as possible. But covering certain pattern does not mean that the model can reach good performance on (Meilicke et al., 2018; Rossi et al., 2021). Moreover, a pioneer work AutoSF (Zhang et al., 2020) shows that designing data-awart models can consistently achieve high performance on any given KGs. Thus, dynamically searching message functions could be an effective way capture the data patterns of the given HKG and pursue high performance.
Unfortunately, the searching method AutoSF is strictly restricted to bilinear KG models (Yang et al., 2015; Kazemi & Poole, 2018), which is not applicable to message function design and the HKG scenario. Besides, although neural architecture search (NAS) (Elsken et al., 2019) has been introduced search GNN architectures, current GNN search spaces (Zhang et al., 2021) are not well regularized to tasks on HKGs. Specifically, the existing search spaces of message function follow the classic way to simply aggregate node neighbors to learn node embeddings. while ignoring edge embeddings to represent relations. Thus, they cannot capture the correlation between entities and relations of HKGs.
In summary, rigid message function designs for HKGs are not conducive to consistently pursuing high performance on different data sets, while existing searching methods are not applicable for HKGs. To bridge this research gap, we propose the Message function SEArch for any given HKGs, named as MSeaHKG. However, it is non-trivial to design expressive search space to enable the powerful message functions being searched, especially the space cannot be too large for the sake of search efficiency. Thus, we identify the necessary computation operators that are domian-speciinn designs for HKGs and propose to search the interaction between these operators for capturing the relational patterns. Moreover, except for the message function search, we also incorporate other GNN components (e.g., aggregation function) in the MSeaHKG search space for more performance improvements. Then, formulate the discrete HKG models with probabilistic modelings to enable an efficient NAS algorithm working on our scenario. The main contributions are listed as:
Previous GNN searching methods generally ignore the edge representations, which fails to handle semantic meaningful relations on HKGs. Besides, their message functions cannot capture complex interactions between entities with relations. In this paper, we propose a searching method to dynamically design suitable GNN that can achieve high performance on the given HKG.
Inspired by rigid message function designs, we define novel search space of message functions for HKGs, which enables the message function to be flexibly searched on the given HKG. Especially. the message function designs of existing GNNs for HKGs and some classic KG/HKG models can be instantiated as special cases of the proposed space.
We conduct experiments on benchmark HKGs for the link prediction and relation prediction tasks. Experimental results demonstrate that MSeaHKG can consistently achieve state-of-the-a performance by designing data-aware message functions. Besides, we also transfer MSeaHKG to other graph-based tasks and further investigate its capability.
2 RELATED WORK
2.1 ONE-SHOT NEURAL ARCHITECTURE SEARCH IN GRAPH NEURAL NETWORK
To avoid manual efforts on neural architecture designs, NAS (Hutter et al., 2018; Yao & Wang, 2018) aims to automatically search suitable neural architectures for the given data and task. Generally, search
2

---

Under review as a conference paper at ICLR 2022
Table 1: Overview of Existing Works. NC, GC, LP, RP denote node classification, graph classification, link prediction, relation prediction, respectively. DP(.) is dropout; (-) is batch normalization; o(-) outputs the hidden representation after summarizing mixed operations (Zhao et al., 2021); h denotes the output from i-th operator of O in K-th layer of message function (see Sec. 3.1).
Scenarios
Type
Model
Message Function
Task
Type/Length of edge
You et al. (2020)
NC/GC/LP
DP(BN(We; + +b) ar,concat aij We;
NAS for GNNs
GraphNAS
=1/= =2
AGNN
NC
SANE
Wolfe))c,ENIe (.ysMP(hss)e) W,e;
///= =
NAS-GCN
GC
R-GCN
2 21/= =2
GNNs for KGs/HKGS
CompGCN
Wxmnjej r)
LP/RP
StarE
Wx(ri Co, 7(, hr))
2 1/ 2
G-MPNN
Tr(e) * Pe, * ei
Ours
MSeaHKG
LP/RP
1/ 2
MT..&coocctt (h li=1)
space, search algorithm, and evaluation measurement are three important components in NAS (Elsken et al., 2019). Search space defines what network architectures in principle should be searched. The search algorithm performs efficient search over the search space and finds architectures that achieve good performance. Evaluation measurement decides how to evaluate the searched architectures during the search. Classical NAS methods are computationally consuming because candidate architectures are evaluated by the stand-alone way, i.c., evaluating the performance of architecture after training it convergence. More recently, one-shot NAS (Pham et al., 2018) proposes the weight sharing mechanism to share network weights across different candidate architectures and evaluate them on the shared weights, which can extremely reduce the search cost.
Some pioneer works have explored NAS for GNNs, such as You et al. (2020), GraphNAS (Gao et al., 2020), AGNN (Zhou al., 2019), NAS-GCN (Jiang & Balaprakash, 2020). And the one-shot NAS also has been introduced to search GNN architectures recently, e.g., SANE (Zhao et al., 2021). As shown in the left part of Fig. most GNN searching methods follow the message passing neural networks (MPNNs) (Gilmer et al., 2017) to unify two steps of the GNN framework in one layer:
stepl m, < agg( (m, (()(,)) step2: e, f- act(comb(e, m.)).
(1)
where e, E Rd represents the embedding of node ei. m, is the intermediate embeddings of e gathered from its neighborhood N (e.). The search space of operators in Eq. 1 are summarized into:
Message Function mge(-): The message function decides the way to gather information from neighborhood e, of the center node et. Zhang et al. (2021) summarizes the typical message in existing GNN searching methods as mgo(e,, e,) = 0g₃ Wej, where asj denotes the attention scores between nodes e, with eg- Besides, present more message function designs in Tab. 1.
Aggregation Function agg(-): controls the way to aggregate message from nodes' neigh- borhood. Usually agg E {sum, mean, maz), where sum(-) = Ee,EN(e.) mge e,), mean(.) EejeN(e)) mge(e; (,))) and max(-) denotes channel-wise maximum.
Combination Function comb(.): It determines the way merge messages between neighborhood and node itself. In literature, comb is selected from {comcat, add, mlp). where concat(.) = [e,, m.). add(-) e, + m, and mlp(-) = .M LP + m.) (M LP is Multi-layer Perceptron).
Activation Function a-)(-): [identity, sigmoid, tanh, relu, elu] are some of the most commonly used activation functions (Gao et al., 2020).
Overall, (-) in Eq. 1 only learns node embeddings, which cannot encode the semantic meaningful edge types (i.e., relations in HKGs). Note that NAS-GCN (Jiang & Balaprakash, 2020) takes the edge feature h,y between e, and ej as input without learning edge embeddings, and recent AutoGEL (Zhili et al., 2021) simply extends the message function mg.(.) (.) to learn edge embeddings without studying the interactions between entities and relations, thereby failing to handle the L./RPP tasks on HKGs.
3

---

Under review as a conference paper at ICLR 2022
ently
relation roleposition
Computing Openator
e
P
P
((,)
Ø
((c)
agg
0g9
comb(
concat
((()
I(e,)
act(
act (sum(())
act sum
act
C
MPNN
CompGON
StarE
G-MPNN
Figure 1: The framework of several GNN frameworks. The green box refers to the message function. Note that CompGCN and StarE select sum(-) as agg(.) and omit comb(.), while G-MPNN concat(-) as combl.).
2.2 GRAPH NEURAL NETWORKS FOR KG/HKG EMBEDDING
As introduced in Sec. and Sec. 2.1, message functions classic GNNs simply aggregate messages from adjacent nodes (see Tab. I and Eq. 1). But in scenarios of KGs and HKGs, it is important to know the type of edge (relation) that connects several entities. To capture relations, R-GCN (Schlichtkrull et al., 2018 8) proposes to model relations R in KGs through relation-speciie weight matrix W, ddxd for R in message functions, which is instantiated as:
e; = (sum) eW r(ee)))),,
where =(e)== = (r(e), ej) S : R, F} is the set of relational edges incident But such relation modeling may lead the over-parameeerization issue because there are many relations in KGs. Therefore, CompGCN (Vashishth et al., 2020) utilizes the embedding vector r to represent the relation instead weigh matrix:
C; = ast(m (W (e(())))))))) r=
(3)
where X(r) records the directional information of edges. The entity-relation relation composition operator set {sub, mult, corr} is inspired by classical scoring function design existing KG embedding models, such element-wise subtraction sub(-) ej (Bordes al., 2013), inner product mail(-)) = ej r (Yang et al., 2015), circular correlation corr(.) = ej o o (Nickel et al., 2016).
Subsequently, StarE and G-MPNN extend the applications of GNNs from KGs to HKGs. StarE (Galkin et al., 2020) requires the role information To, of entity éj and assumes hyper- relational fact r(ei....,, .,) is composed by base triplet r(es, 6o) with (Troy eE}} such that r(c., co. {TTo e.))). Then StarE takes base relation with the role-value pairs as hyper-relation and performs the composition operator (--(-) on the hyper-relation with base entity:
of role-value pairs
e, = accmmsu (A 7(, h, ((r,,,))lree.ee breee)eee.... ())))) h, W sum((oo(rr e;)bs);
where h, is the hidden representation aggregated from the role-vaie balev pairs, 7-)) concatenate operator to output the representation of hyper-relation. The update of in StarE is similar to CompGCN. Instead requiring role information, G-MPNN (Yadati, 2020) proposes to model positional information in GNNs:
= act((e;, (gllee Pr)
II Peçi (err jE(I....))
(4)
where represents r(e en) E S, P(s)
{1...., ......pp } is positional mapping (n, |E), and Psy., is the positional embedding vector of e, on fact s. To intuitively check the difference of message functions, plot the framework of general MPPNs and GNNs for KGs/HKGs in Fig.
4

---

Under review as a conference paper at ICLR 2022
3 MSEAHKG
In this section, we first propose search space, especially the space of message functions, which enables the powerful GNNs to be searched for any given HKGs. Then, we formulate our search problem the proposed space and solve it by leveraging an efficient search algorithm.
3.1 GNN SEARCH SPACE DESIGN FOR HKG EMBEDDING
As discussed in Sec. 1, designing the proper message function is more conducive to capturing relational patterns of given HKGs and pursuing high empirical performance. Therefore, the first task to design an expressive search space so that message functions covering various relational patterns can be searched. However, the space of existing GNN searching methods (see Eq. and Fig. I) does not apply HKGs and cannot cover the message functions of GNNs for KGs/HKGs (see Sec. 2.2). Thus, we focus on the search space design of message functions in this paper.
Recently, various message functions have been proposed for KGs/HKGs presented in Sec. 2.2. From Fig. I, we can observe that those message functions are mainly different these two aspects: 1) the operators (e.g., W, Φ 7) for computing hidden representations, 2) the structure of message functions that decides how computational operators are connected. For the operator selection, existing works manually tune them on different data sets, such as Φ in CompGCN, &o, Ør, y in StarE, agg(-) in G-MPNN, Moreover, the structure of message functions for HKGs (StarE and G-MPNN) tends be deeper and more complex than those for KGs (e.g.. CompGCN), This is because the message function needs to process more information (e.g.. more entities/roles) when facing the facts with higher arity. These observations motivate us to build space of operators and structures for message function search. Furthermore, we investigate more about the relationship between operators and relational patterns. Generally, the relational pattern can represented as certain correlation among r(pemu((e) (1, en)) (check more in Appx. B.2), where penru denotes the permutation. For example, r is symmetry if r(e,, e;) must be true when r(E;, Eÿ) is true. Therefore, the message function the search space must be able to handle such correlation in the form of f ((pemu(e1,.-. ... Cn)). In the next, we first introduce the space of operators, and then discuss how they deal with ((pemu(e.......
Positional Transformation Matrix W P(ee: The position of entity in a fact can largely determine the plausibility of the fact. For example, i isCapt al (Be iin, Ch na) is true while i sCappialCs (China, Bei jing) is false. G-MPNN utilizes the positional embedding Pe.. and Pe) to encode the position of entity e and relation different facts, which requires the model complexity Odd[S((E)) + N)). However, the training data set is very sparse in KBs. Such over-parameeterization may make the training insufficient. Instead, we adopt the way to transform one entity e to N possible positions. Let the positional mapping be P(e) e [I....,N) N). then the positional matrix is able to transform e to the permutation position in pemau(-) by er
where WP(e) consumes O(Nd)) ([S) >> d in practice).
Concatenate Operator 7()): It mainly determines the concatenation way between embedding vectors. In this paper, we set O., {concal, mult, wsum) } (Galkin al., 2020), where wsum is the weighted sum. In general, 7(-) can concatenate embeddings after the positional transform matrix W W(e). i.e., encoding perru .., en).
Role Embedding ro: Unlike the positional information of entities encoded by WP(e). the role em- bedding utilized to model the semantic information of entities (Liu et al., 2021). For example, the roles in 2nd position of facts playCharacer In (actor: ZacharyQuinto character Spock, movie: StarTrek) and actorAwardIn (actor: ZacharyQuinto, award: BC-BSFC, movie e: StarTrek) are different though other entities and roles are same. Thus, the model should be able to capture the role of candidate entities after using WP(e). e.g. BC-BSFC unlike be the 2nd entity of pllyCharaceeria since its role is award instead of character.
Composition Operator o(-): Following CompGCN, we utilize composition operator d(-) to capture message between the node and edge embeddings before aggregation step. Note that & actually encodes the interaction between r and pemu(ee,... e.)) While CompGCN and StarE empirically selects the most proper d(.),
include this operator into the space X. Thus, MSeaHKG is able to automatically search for the most suitable o(-) in a more efficient way. We combine the settings of CompGCN and StarE to set O₂ (sub, mult, corr,
corr, rotat) (rotal (Sun
5

---

Under review as a conference paper at ICLR 2022
Inputs
e eF
ex
Fay
MPNN Layer 1
mg(::0) 0)
M
layer cnt
I(e:)
idtt
agg(
MPNN Layer 2
W
layer ont
comb(
MPNN Layer 3
act (.)
h
h
layer cnt
MLP&concat
Ouputs
(a) Framework.
(b) One-layer MPNN
(c) Message Function Space.
Figure 2: The framework MSeaHKG. Fig. (b) represents concrete framework MPNN layer in Fig. (a), and Fig. (c) is detailed formulation of mg(:: 0) in Fig. (b). The operator layer ent enables the connectivity of different layers (Jiang & Balaprakash, 2020).
et al., 2019), others in Sec 2.2). Besides, é not only occurs between primary relations with entities, but also captures the correlation between roles with entities.
Others: (1) The idt (h) operation allows inputs skip one layer in the message function; (2)
Unlike WP(e). the transform matrix W processes the hidden representations.
Among above components, we fix the role embedding and positional transform matrix W P(e) in the message function (see Fig. 2 (c)) at the initial layer, which are specific designs to HKG problems. And we include others into the space of message function O (W, 6, idf) for searching. As shown in Fig. 2 (c), we denote the node of as i-th operator of O in k-th layer and h be the hidden representation outputted by of. Then we have:
(M 2 ( P(e.)))....... W en, rop...., r. h = of where 8 E 1) controls the connection between of with of !t- Note that (h [h
(5)
for k [l....,KK and i E (1,...,, |01,
(6)
(W (l, W ((,,.)).., Cn, r} if role information is not available the given HKG. From Fig. 2 (c). we can observe that the structure of message functions is controlled by {0))}.
To avoid manual operation selection, we also search for concrete operations two operators á and
y. Given the operator set O₂ and O,,, let 000h 07 E {0. 1} records the selection i-th operation
o Oz, O, at k-layer respectively. Then, and 7 perform the computation in Eq. 6 could be
(+(h) Σ thh (h) and (*h) ( Note that 05
and Σ, 87th 1. Let @mg (0 U ( ( The message function parameterized by @m is defined as:
mg(r(ei.....,.. 0 .M LP&comclll ((h K )!2)),
where we simplify role embedding r. for simplicity and h is outputted by the last layer of Eq. Intuitively, existing GNNs for KGs/HKGs are contained in the MSeaHKG space (compare Fig. 1 and Fig. 2). Moreover, we include more discussions about the instantiations of other KG/HKGs models in the MScaHKG space and the capability of handling relational patterns in Appx. B.2.
In addition to message function search, we also search for other operators (e.g., agg, comb, act) like existing GNN search methods as shown in Fig. 2 (a) and (b). Let + {0 0099 .... be parameter set for all operators selection in our MPNN framework. Then, an architecture can be represented as Xe (m)9), a= 8a09), ) (check other functions in Appx. C.I). And existing GNNs for KG/HKG embeddings actually can be represented by different instantiations of @ Overall, a GNN model Xe encodes the given HKG into embedding space (E, R), i.e., Xe(g).

---

Under review as a conference paper at ICLR 2022
3.2 SEARCH ALGORITHM DESIGN
In this subsection, we introduce how to select the GNN Xe that can achieve high performance on the given G. First, we evaluate performance of Xe based on the HKG embedding w { R] since Xe is utilized to encode (E R, S) into w, i.e., w = (9)). In the KG/HKG embedding, the scoring function f(; w) is to verify the plausibility of fact s = r(ee..... ................................ enp) by decoding w (check more about scoring functions in Appx. C.2). Generally, the good embedding w can make f(s; w) to distinguish true or false for a given fact 8. Thus, we build evaluation of Xe on (s:ww) Taking link prediction task (predict the missing entity in fact, e.g., r(?, e....... Cx)) as example, let scoring function (s; w) decode w and output a score matrix p" E [0, 1] where p. is the probability score of E E may be the ground truth of the missing entity. Then, we follow Dettmers et al. (2018) to construct the cross entropy loss ([(() = Legg y log where De if is the ground truth otherwise O. Subsequently, we denote L(Xe, wi 9) = Eoes ((f(s; w)) to calculate the overall loss of GNN model Xe with the HKG embedding w on G(E, R, S). Formally the GNN search problem for given HKG G is formulated as:
min ((Xo.w:) 0,u
Solving Eq. 8 is a non-trivial task because Xe (c.g., Xe = {agg- sum, act : relu, }}) is from large space. For example, only the structure space size {0 } of message function reaches to ((2 +(2+++++ 0l). And Xe is discrete, indicating the gradient- based optimization cannot be employed since Vx. does not exist. To enable an efficient search, we first relax the parameters of GNN model e from discrete space into a continuous and probabilistic space + More specifically, 0y {0. 1} restrictively controls the connectivity between of with of k- while 8% E [0, 1] is the probability that of is connected with of - Then, let X ~ pe (X) represent GNN model X being sampled from the distribution ( We reformulate the problem in Eq. 8 into:
min (x) w[)), m
(9)
where ET-] is the expectation. To compute the gradient w.r.t. Q we first utilize the reparameterization
trick X = 96 (U) (Maddison et al., 2016), where U is sampled from uniform distribution p(U).
Then the gradient w.r.t. θ and is computed as (check full derivation in Appx. C.4):
( [C(X w; 9) = EU (F) V (U)), V Ex [ [(X, g) = (xx VxX,
(10)
(11)
Note that Vase (U') can be computed if 96 (U) is differentiable. Inspired by SÑAS (Xie et al., 2018), we leverage Maddison al. (2016); Jang et al. (2016) to instantiate ge (U) (see Appx. C.4).
EXPERIMENTS
4.1
EXPERIMENTAL SETUP
The experiments are implemented on top of PyTorch (Paszke et al., 2019) and performed on one single RTX 2080 Ti GPU. Appx. D. introduces the details of hyper- parameerrssssss.
Data Sets. The details of data sets are summarized into Tab. 7 in Appx. 1.1.2. For experiments on HKGs (facts with mixed arities), we employ 2 benchmark data sets: (1) Wiki-People (Guan et al., 2019) is extracted from wiki-data, which mainly concerns the entities that belong to the human type. (2) JF17K (Zhang et al., 2018) is extracted from Freebase (Bollacker et al., 2008). For experiments on facts with fixed arities, we utilize several data sets with fixed arities and n > 2: WikiPeople-3, JF17k-3, WikiPeople-4, and JF17k-4. Note that GETD (Liu et al., 2020) filters out the 3-ary and 4-ary facts from WikiPcople and JF17K to construct WikiPeople-n and JF17k-n respectively.
Tasks and Evaluation Metrics. In this paper, we mainly compare HKG embedding models on the link and relation prediction task in the transductive setting. The link prediction task is to predict the missing entity in the given fact at n possible positions, e.g., predicting the first missing entity r(? ... , ).). The relation classification task needs predict the missing relation in fact when all entities are known, i.c.. ?(e), ... ). We employ Mean Reciprocal Ranking (MRR) (Voorhees, 1999) and Hits @ (1,3, 10). All reports are in the "filtered" setting (see more in Appx. 1.1.3).
7

---

Under review as a conference paper at ICLR 2022
Table 2: The model comparison of the link prediction task on HKGs. The results of NNs and multi-linear baselines are copied from Liu et al. (2020), those of Geo and S2S are copied from Di al. (2021). And GNN baselines are re-implemented due to the task variance.
WikiPeople
JF17K
type
model
MRR
Hit@1
Hit@3
Hit@ 10
MRR
Hit@1
Hit@3
Hit 10
Geo
RAE
0.172
0.102
0.182
0.320
0.310
0.219
0.334
0.504
NaLP
0.338
0.272
0.364
0.466
0.366
0.290
0.391
0.516
NNs
HINGE
0.333
0.259
0.361
0.477
0.473
0.397
0.490
0.618
Neulnfer
0.350
0.282
0.381
0.467
0.517
0.436
0.553
0.675
Multi-
HypE
0.292
0.162
0.375
0.502
0.507
0.421
0.550
0.669
linear
RAM
0.380
0.279
0,445
0.539
0.539
0.463
0.573
0.690
StarE
0.378
0.265
0.452
0.542
0.542
0.454
0,580
0.685
GNNs
G-MPNN
0.367
0.258
0,439
0.526
0.530
0.459
0.572
0.688
S28
0.372
0.277
0,439
0.533
0.528
0.457
0.570
0.690
Search
MSeaHKG
0.395
0.291
0.470
0.554
0.577
0.481
0.599
0.711
Table 3: The model comparison of the relation prediction task on HKGs. The results of NNs are copied from Guan et al. (2020), others are based on our implementations.
WikiPeople
JF17K
type
model
MRR
Hit@1
Hit@3
Hit@ 10
MRR
Hit@1
Hit@3
Hit
Nal.P
0.735
0.595
0.852
0.938
0.825
0.762
0.873
0.927
NNs
NeuInfer
0.765
0.686
0.877
0.900
0.861
0.832
0.885
0.910
StarE
0.800
0.753
0.936
0.951
0.901
0.884
0.929
0.963
GNNs
G-MPNN
0.777
0.694
0.905
0.912
0.864
0.842
0.883
0.917
S2S
0.813
0.744
0.928
0.960
0.912
0.877
0.932
0.951
Search
MSeaHKG
0.831
0.787
0.955
0.972
0.933
0.894
0.950
0.972
Except for GNNs in Sec. 2.2, we present key functions of most adopted baselines in Tab. 5. For tasks on HKGs, we mainly compare the proposed method with advanced HKG embedding models: (1) Geometric model: RAE (Zhang et al., 2018). which upgrade version of m-TransH (Wen et al., 2016) that extended from TransH (Wang et al., 201 3014); (2) GNN-based models: G-MPNN (Yadati, 2020) and StarE (Galkin et al., 2020) (note that we re-implement and tune them because G-MPNN under inductive settings and StarE only tests the performance of main triplets in hyper-relational facts); (3) Other NN-based models: NaLP (Guan et al., 2019), HINGE (Rosso et al., 2020), and Neulnfer (Guan et al., 2020); (4) Multi-lines models: The final score of HypE (Fatemi al., 2020) and RAM (Liu et al., 2021) is computed by multi-way inner product which is extended from bilinear KG embedding models (Yang al., 2015). (5) Search method: S2S (Di et al., 2021) proposes a search space for tensor decomposition models and searches for sparse core tensors. It shares embeddings to jointly learn from facts with mixed arities to alleviate the issue of tensor modeling.
Baselines.
Except for the above methods on HKGs, we also include the tensor decomposition models (n-CP, n-TuckER, GETD) that work well on the scenario of facts with fixed arity. n-CP (Lacroix al., 2018) leverages CANDECOMP/PARATAC decomposition (Hitchcock, 1927), while n-TuckER (Balazevic al., 2019) based on Tucker decomposition (Tucker, 1966). GETD (Liu al., 2020) proposes to reduce the model complexity by tensor ring decomposition.
4.2 MAIN EXPERIMENTAL RESULTS
The main results HKGs (i.c., WikiPeople and JF17K) have been summarized into Tab. 2 and Tab. Compared with Geometric and classic NN-based methods (c.g.. NaLP), GNNs methods (c.g., StarE) achieve outstanding performance, which demonstrates the power of GNNs on the graph tasks. And StarE generally is better than G-MPNN in GNNs methods because the inner product way in G-MPNN cannot handle several relational patterns as mentioned in Sec. 1. Besides, although the multi-linear method RAM utilizes the simple inner product as its scoring function, it carefully models the role semantic information and interaction patterns, thus achieving good performance. Another searching method S2S alleviates the extension issue of tensor decomposition models from the fixed to the mixed scenario. It still slightly inferior compared with other state-of the-art methods. Overall, all existing methods cannot consistently achieve the leading performance on different tasks and data sets. In this
8

---

Under review as a conference paper at ICLR 2022
Table 4: The model comparison of the link prediction task on facts with fixed arity. The results of tensor models are copied from Liu et al. (2020), others are copied from Di et al. (2021).
WikiPe
JF17K-3
WikiPeople-4
JF17K-4
type
model
MRR
H@10 10
MRR
H@ 10
MRR
H@1 10
MRR
H@ 10
Geo
RAE
0.239
0.379
0.505
0.644
0.150
0.273
0.707
0.835
NaLP
0.301
0.508
0.515
0.679
0.342
0.540
0.719
0.805
NNs
HINGE
0.338
0.508
0.587
0.738
0.352
0.557
0.745
0.842
NeuInfer
0.355
0.521
0.622
0.770
0.361
0.566
0.765
0,871
n-CP
0.330
0.496
0.700
0.827
0.265
0,445
0.787
0.890
Tensor
n-TuckER
0.365
0.548
0.727
0.852
0.362
0.570
0.804
0.902
GETD
0.373
0.558
0.732
0.856
0.386
0.596
0,810
0.913
$2S
0.386
0.559
0.740
0.860
0.391
0.600
0.822
0.924
Search
MSeaHKG
0.405
0.583
0.757
0.892
0.412
0.628
0.834
0.940
paper, MSeaHKG pursues the high model performance by dynamically designing the most suitable message function for the given HKG and task. The searched message functions can capture data-level properties (see case study in Appx. D.2), thereby showing the leading performance. Especially, the search space of another search method S2S is based on the tensor modeling. As discussed in Sec. and Appx. A, the MRHG could be a more natural way to represent HKGs, thereby MSeaHKG benefits from building message function search space in GNNs under the MRHG modeling.
We show experiments on facts with fixed arity in Tab. 4. As discussed in Sec. 1, we can indeed observe that classic tensor decomposition models (n-CP, n-TuckER, GETD) perform better than Geometric and based methods on the scenario of fixed arity. Then, S2S proposes to dynamically sparsify the core tensor of tensor decomposition models for the given data and further improve the performance of tensor models. Moreover, we note that MSeaHKG still performs better than S2S even in the scenario of fixed arity. That because S2S simply assumes 3 relationships between entities and relations in the search space: positive, irrelevant, and negative. But the message function space in Sec. 3.1 could characterize more complex interactions between entities and relations, thereby achieving improvements.
4.3 MORE INSIGHTS VIA EMPIRICAL STUDY
Due the space limitation, we include more experimental results Appx. D to provide more insights and verify several claims in this paper. First, we demonstrate case studies in Appx. D.2 that the searched message functions are data-dependent and can adapt to the given data set. Second, we conduct ablation studies to analyze the components of the proposed method in Appx. D.3. Specifically, we show several variants of the proposed search space to demonstrate: (I) with a simple extension of message function, the GNN searching method cannot work well on HKGs (e.g., AutoGEL discussed in Sec. 2.2), (2) automatic operation selection can improve the performance built on the manual operation tuning, (3) the structure design of message functions is important to improve performance on HkGs. Then, we implement two more popular NAS algorithms (Liu et al., 2018 8; Akimoto et al., 2019) to compare the searching effectiveness and efficiency of one-shot NAS search algorithms in our scenarios. Third, we transfer MS to more variety of graph-based tasks Appx. D.4.
5 CONCLUSION
In this paper, we propose new message function searching method for HKGs, named MSeaHKG. First, we present a novel search space message functions in MPNNs, which enables both structure search and operation selection in message functions. With our expressive message function design, some classic KGs/HKGs models and existing message functions for HKGs could be instantiated as special cases of the proposed space. Then, we develop efficient one-shot NAS algorithm to search the message function and other GNN components for the given HKG. The empirical study demonstrates that the searched message functions are data-dependent and can adapt to the data patterns of the given HKGs. Overall, MSeaHKG has shown its effectiveness and efficiency on benchmark data sets.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In ICML. 2019.
Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. Dbpedia: nucleus for web of open data. In The Semantic Web, pp. 722-735. Springer, 2007.
I. Balazevic, C. Allen, and T. Hospedales. Tucker: Tensor factorization for knowledge graph completion. EMNLP, pp. 5188-5197, 2019.
J. Bergstra, D. Yamins, and D. D. Cox. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. 2013.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: a collabo- ratively created graph database for structuring human knowledge. In SIGMOD, pp. 1247-1250, 2008.
A. Bordes, N. Usunier, A. Marcia-Duran J. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pp. 2787-2795, 2013.
Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua. Unifying knowledge graph learning and recommendation: Towards a better understanding of user preferences. In WWW, pp. 151-161, 2019.
Xiangxiang Chu, Tianbao Zhou, Bo Zhang, and Jixiang Li. Fair darts: Eliminating unfair advantages in differentiable architecture search. ECCV, pp. 465-480. Springer, 2020.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2D knowledge graph embeddings. AAAI, 2018.
Shimin Di, Quanming Yao, and Lei Chen. Searching to sparsify tensor decomposition for n-ary relational data. In WebConf, pp. 4043 2021.
Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: survey. J. Mach. Learn. Res., 20(55):1-21, 2019.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter optimiza- tion at scale. In ICML, pp. 1437-1446. PMLR, 2018.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In WWW, pp. 417-426, 2019.
Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. Knowledge hypergraphs: Prediction beyond binary relations. 2020.
Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. Message passing for hyper-relational knowledge graphs. In EMNLP, 2020.
Yang Gao, Hong Yang. Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In IJCAI, volume 20, pp. 1403-1409, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pp. 1263-1272. PMLR, 2017.
Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Cheng. Link prediction n-ary relational data. In wWW, pp. 583-593, 2019.
Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and Xueqi Cheng. Neuinfer: Knowledge inference on n-ary facts. ACI., pp. 6141-6151 2020.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, pp. 1025-1035, 2017.
10

---

Under review as a conference paper at ICLR 2022
Frank L Hitchcock. The expression of tensor a polyadic sum of products. Journal of Mathematics and Physics, 6(1-4):164-18, 1927.
F. Hutter, L. Kotthoff, and J. Vanschoren. Automated Machine Learning: Methods, Systems, Challenges. Springer, 2018.
Eric Jang. Shixiang Gu, and Ben Poole. Categorical reparameteriization with gumbel-softmax, arXiv preprint 1...:16611.01144 2016.
Shengli Jiang and Prasanna Balaprakash. Graph neural network architecture search for molecular property prediction. IEEE Big Data, pp. 1346-1353, IEEE, 2020.
S. Kazemi and D. Poole. Simple embedding for link prediction in knowledge graphs. In NeurIPS, pp. 4284 4295, 2018.
D.P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016.
T. Lacroix, N. Usunier, and G. Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, pp. 2863-2872, 2018.
H. Liu, K. Simonyan, and Y. Yang. DARTS: Differentiable architecture search. In ICLR, 2018.
Yu Liu, Quanming Yao, and Yong Li. Generalizing tensor decomposition for n-ary relational knowledge bases. In WebConf, pp. 1104-1114,
2020.. 2020.
Yu Liu, Quanming Yao, and Yong Li. Role-aware modeling for n-ary relational knowledge bases. In WebConf, pp. 2660-2671, 2021.
Denis Lukovnikov, Asja Fischer, Jens Lehmann, and Sören Auer. Neural network-based question answering over knowledge graphs on word and character level. In WWW, pp. 1211 1211-1220, 2017.
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: continuous relaxation of discrete random variables. arXiv preprint arXiv: 1e0116111100122.. 2016.
Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt, Fine-grained evaluation of rule-and ambedding-baase systems for knowledge graph completion. ISWC, pp- 3-20, 2018
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings the IEEE, 104(1):11-33) 2015.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic embeddings of knowledge graphs. In AAAI, 2016.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, al. Pytorch: An imperative style, high-performance deep learning library. In NeurIPS. pp. 8024-8035, 2019.
H. Pham, M. Guan, B. Zoph. Q. Le, and J. Dean. Efficient neural architecture search via parameter sharing. In ICML, pp. 4092-4101, 2018.
Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. Knowl- edge graph embedding for link prediction: A comparative analysis. TKDD, 15(2):1-49, 2021. 2021.
Paolo Rosso, Dingqi Yang, and Philippe graph embedding for link prediction. In WebConf, pp. 1885-1896, 2020.
Beyond triplets: hyper-relational knowledge
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, pp. 593-607. Springer, 2018.
11

---

Under review as a conference paper at ICLR 2022
DI Shimin, YAO Quanming, Yongqi ZHANG, and CHEN Lei. Efficient relation- aware scoring function search for knowledge graph embedding. In ICDE, pp. 1104-1115. IEEE, 2021.
Z. Sun, Z. Deng, J. Nie, and J. Tang. RotatE: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation complex space, In ICLR, 2018
K. Toutanova and D. Chen. Observed versus latent features for knowledge base and text inference. In Workshop on CVSMC, pp. 57-66, 2015.
T. Trouillon, Christopher R., É. Gaussier, J. Welbi, S. Riedel, and G. Bouchard. Knowledge graph completion via complex tensor factorization. JMLR, 18(1):4735-477) 2017.
Ledyard R Tucker. Some mathematical notes three-mode factor analysis. Psychometrika, 31(3): 279-311, 1966.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition-baser multi- relational graph convolutional networks. In ICLR, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurIPS, pp. 5998-5008, 2017.
Ellen Voorhees. The trec-8 question answering track report. In TREC, volume 99, pp. 77-82, 1999.
Q. Wang, Mao, Wang, and L. Guo. Knowledge graph embedding: A survey of approaches and applications. TKDE, 29(12):2724-277) 2743, 2017.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In AAAI, 2014.
Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. Pooling architecture search for graph classification. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2091-2100, 2021.
Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and Richong Zhang. On the representation and embedding of knowledge bases beyond binary relations. IJCAI, 2016.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. ML, 8(3-4):229-252) 1992.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. arXiv preprint arXiv: 11t..9882209926, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2018.
Naganand Yadati. Neural message passing for multi-relational ordered and recursive hypergraphs. Advances in Neural Information Processing Systems, 33, 2020.
B. Yang, W. Yih, X. He. Gao, and L. Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
Quanming Yao and Mengshuo Wang. Taking human out of learning applications: A survey automated machine learning. Technical report,
2018.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi. Thomas Brox, and Frank Hutter. Un- derstanding and robustifying differentiable architecture search. arXiv preprint arXiv: 999.09656. 2019.
12

---

Under review as a conference paper at ICLR 2022
11 play
0s Spook
Spock
charTn
R SteghensManleyy
r2 charln In
0.
to StephenMankey
Q0 StorTych
:play
SterTvok
LeonardNimoy
Hy
Q.
6 LeonardNimoyy
Q
0s StarTrek
es StarTrek
RobertWise
iisertWise
(a) KG with Multi-relational Graph Modeling.
(b) HKG with Multi-relational Hypergraph Modeling.
Figure 3: The illustration KGs and HKGs. The binary facts are simplified in (b) make the 3-ary facts look more prominent.
Richong Zhang, Junpeng Li, Jiajie Mei, and Yongyi Mao. Scalable instance reconstruction in knowledge bases via relatedness affiliated embedding. In wwW, pp. 1185-1194, 2018.
Yongqi Zhang, Quanming Yao, Wenyuan Dai, and Lei Chen. AutoSF: Searching scoring functions for knowledge graph embedding. In ICDE, pp. 433 333-444, 2020.
Ziwei Zhang, Xin Wang, and Wenwu Zhu. Automated machine learning graphs: A survey. arXiv preprint N.iv:2103.00744 2021.
Huan Zhao, Quanming Yao, and Weiwei Tu. Search to aggregate neighborhood for graph neural network. arXiv preprint arXiv:2104.0660 2021.
Wang Zhili, Di Shimin, and Chen Lei. Autogel: An automated graph neural network with explicit link information. In NeurIPS, 2021.
Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXiv: 909.03184, 2019.
A DISCUSSION ON THE MODELING OF HKG
Given set of facts with the fixed arity fr(ei....., en)). }, tensor models (e.g., CP (Lacroix et al., 2018)
and TuckER (Balazevic et al., 2019)) use (n + --dimnnsiinaal tensor G {0, 1) [ xx to represent facts, where G Ir.l....n
x-
represents the fact r(ei,..., ea) existed otherwise Gr.1.....
G
0. Then, tensor models leverage the tensor decomposition techniques to decompose G into embeddings R and E with core tensor Z" E Rdx...dd
= z X1 RX X3 xx+1 E.
Obviously, tensor GD+1 can only model facts with the fixed arity n. Thus, we have build (G" G to model the facts with mixed arities S = fr(ei,..., ex)) ): n E {2, N} and decompose them into N - 1 sets of entity and relation embeddings. such as (E", R N J==2- But KBs are known to have the data sparse issue, thus learning multiple set of embeddings could lead to severe problems.
As mentioned in Sec. 1, multi- hypergraphs (MRHGs) G(E, R, could be more natural way to represent HKGs. We illustrate examples of KGs and HKGs in Fig. (a) and (b), respectively. Given a fact with high arity (e.g., playCha racterIn (e1, cs, es) MRHG can first store the correspondence between multiple entities by hyperedge (e1, é3, 65), then label this hyperedge with the relation plas playCharacterTi arities (n E {2.3} in this example) can be represented by a MRHG. Thus, MRHG allows us to directly encode given HKG into entity and relation embeddings, where every embedding vector is jointly learned from low and high arities. However, tensor modeling leads the model to learn multiple sets of embeddings.
Moreover, Fig. 3 (b) demonstrates that the facts with mixed
13

---

Under review as a conference paper at ICLR 2022
(a) HolE (Nickel et al., 2016).
(b) RotatE (Sun et al., 2019).
(c) n-CP (Lacroix et al., 2018).
(d) n-DistMult (Yang el al., 2015).
Figure 4: Several instantiation cases of MSeaHKG message function space. denotes circular correlation (orr(-) (Nickel et al., 2016), * denotes inner product mult(-) (Yang et al., 2015). denotes the substraction sub(-) (Bordes al., 2013). * from RotatE (Sun al., 2018).
Besides, HKGs generally contain more complete information compared with KGs. For example, is hard to answer "who plays Spock in StarTrek-3?" with the KG example (Fig. 3 (a)). That is because KGs suffer from the information loss of correspondence among multiple entities. Generally, the constructing procedure of KG, named Star-to- to-Ciqu Conversion, has been verified to be irreversible and caused the information loss in the facts with high arities (Wen al., 2016). Therefore, we believe that HKG could be potential solution to solve complex Q&A scenarios.
B DISCUSSION ON DATA-LEVEL PROPERTIES OF KGs/HKGs AND MESSAGE FUNCTION DESIGN
B. DATA-LEVEL PROPERTIES IN KGs: RELATIONAL PATTERNS
In the past decades, the research community has found that the relations of KGs exhibit differ- ent patterns. For example, we can infer that nei nh (locati on2, location must true as long as neighborCf (locat locationn, location2) neighborOf (Shenžhen, HongKong). But for other relations (e.g., largerThan), know largerThan (value2, valuel) must be false if 1 Maargerhhar (valuel, value2) is true. Many relational patterns in KGs have been found and discussed (Kazemi & Poole, 2018; Rossi et al., 2021), such as symmetry, anti-symmetry, asymmetry, inversion, composition, hierarchy. intersection. However, various KGs usually contain different relational patterns with different proportions of facts. To handle diverse relational patterns on different KGs (i.e., data-level properties), kinds of scoring functions have been proposed to cover as many relational patterns as possible, i.c., pursuing expressiveness. Given the learned embeddings w {E, R). the scoring function f(-) is proposed to evaluate whether the fact is true or false (check Appx. C.2 and Tab. for more details about scoring function). For the sake of understanding, we here present the requirements of several relational patterns on scoring functions:
true, like
Symmetry: r is symmetry if r(ej 64) must be true when r(ei,e)) is true, i.e., s(r(ei, [(r(e;,e:) e:))
Anti-symmetry: is anti-symmetric if ez) must be false when r(ei, ez) is true, i.e., f(r(e,,))) =-((r(e,,
Asymmetry: The plausibility of e() is unknown when e(es,e)) true, f(r(es, + f(r(e,,
Inverse: ri and r2 are inverse relations if ri(e,, ez) is true and r2(e,, ei) true. Then, f(ri(e,, e,)) f(r2(e,,e.))
As mentioned in Sec. 1, the message function of G-MPNN may not be able to infer the non-symmetric relations. Suppose that 81 = r(e1, e2) is true and r one of any non-symmetric relations (e.g., anti- symmetry $2 r(e2,e) e1) must be false). Let h, be the entity feature and h, be the relation feature.
According to the message function G-MPNN in Eq. 4, we can learn the hidden embeddings m,:
m. m2 h h Per. h2 Pez.s Then e; updated with m,, With the scoring function
14

---

Under review as a conference paper at ICLR 2022
Table 5: Scoring Functions for Facts with High-order Arities.
Type
Model
Scoring Function Design (((:w
Notes
m- mn-TransH
Disl ay(e; - v. e, + r| I (e; - U e, + rll + Eig FC((en,)))
V, is relation dependent.
Geo
FC(() is fully connected
RAE
layer.
e, (d) is for eq in j-th po-
n-CP
r * 1 e
(1)
en
sition.
Z E Rdxx-xdd X is ten- sor product in i-th mode, TR(-) is tensor ring de- composition W; a order tensor.
n- n-TuckER
Z X1 r X2 E1 X3 ... Xn+1 On
Tensor
GETD
TR(WI..... (WW,,,.,WW)).... X1 X2 X3 Xn-1 Cn.
Seen(s) returns the seen entities ej in Conv(.) is the convolu- tional filter.
GNNs
G-MPNN
P(a) *TeeESeen(s) Peçia Ej
HypE
r * Conv(e1) Conv(ez) *...* Conv(en)
Multi-
is embedding for i-th role r, é, E mxd is embedding matrix of e 3 is the searched sparse core tensor, denotes (Jr:i.......
linear
RAM
E Ti (1; *...* (n,.)))
Search S2S
Ejreiinn 2 X1 pdr X2 ett x.. x e
of G-MPNN (multiple inner product). we can compute f(r(e), e2)) h Pel.. * * Peu,s e2. Because 61, 62 are seen $1, G-MPNN will assign the positional embeddings 61, 62 in 81 when computing the score of $2, thereby leading f(r(e1, e2)) frr(e,, (12,,e))) Thus, we argue that the fixed message function not flexible enough to capture the relational patterns of the given HKGs, especially its performance may not be good if some uncovered relational patterns exist in the given data set.
B.2 DISCUSSION ON THE CAPABILITY OF MESSAGE FUNCTIONS TO COVER RELATIONAL PATTERNS ON HKGs
As mentioned in Appx. B.1, pursuing expressiveness is one way cover relational patterns on KGs. Such potential solution is also discussed in Sec. 1. However, Meilicke et al. (2018); Rossi et al. (2021) report that being expressive does not mcan achieving good performance even the model can cover those relational patterns. Thus, AutoSF (Zhang et al., 2020) proposes to search bilinear-bases scoring functions for KGs and consistently achieve good performance. Inspired by literature, MS proposes to search proper message functions for the pursuit of high model performance on any given HKGs.
Generally, the relational patterns on HKGs have not been explored before. Inspired by literature on KGs, roughly summarize high level representations of relational patterns in the scenario of high arity as:
f(r (pemuuu(ee........ fra.rri...
where F1,72 may be same relation or different, pemnu(-) represents the permutation of n For example, f(r1 (pemu(e1, w))
entities (c and E {=,,,,,}} indicates rn is a symmetry. In this paper, since our scoring func- tion design is linear transformation (see Appx. C.2), the design of message function in MPNNs (i.e., w = (g) will be the crucial component to capture relational patterns. To capture the permutation information pemnu(-). we first utilize WP(e) encode the positional information, which transforms entity embeddings into corresponding positions. Then, the operator 7(-) concatenates the entity embeddings after encoding positional information. Lastly, the operator s(.) computes the interaction between r with e,, In other words, W(e) and 7(-) employed to represent pemuu(-), and o(-) is utilized to represent the correlation between and pemu(-). Within such design, most classic scoring function designs (including Geometric models (Bordes et al., 2013; Nickel et al., 2016: Sun et al., 2019), Bilinear models (Yang et al., 2015) and Tensor models (Lacroix al., 2018)) and GNNs
(remmu((ee....
15

---

Under review as a conference paper at ICLR 2022
for KGs/HKGs can be instantiated as special cases in the MSeaHKG space. We have demonstrated several examples classic scoring function designs in Fig. 4. Note that the expressiveness of these models has been fully investigated in literature. Every model can patterns, which can make our message function space expressive enough to handle most HKGs. In other words, the search space of MSeaHKG has the potential to return GNN model that adapt to the relational patterns of the given HKG.
or multiple relational
C SUPPLEMENTARY OF SEARCH ALGORITHM
C.I THE PARAMETERIZATION OF OTHER GNN COMPONENTS
Generally, the relaxation of other GNN components (e.g., aggregation and activation) is consistent presented in Sec. 3.1. Here we illustrate
with o* (h) Σ (h() and 7 (h) Σ (h)) (h)
more details.
Let Oesg {sum, mean, maz) be the set of candidate aggregation functions and mg(r(e)..... en ): f))) be the output from Eq. 7. Then, the aggregation function agg(;; 0599) parameterized by 09g9 can be defined as:
m, = =ggg((g((((e)..... en): 0 (m9)) " Ir(es..... 8o99) 0705 oz 0y((mg(r(e))... en): mmg) ) Mele))ee)))))))
Σ
0y oyE0n
Let Oact fidentily, sigmoid, tanh) be the of candidate activation functions. Then, the activation function act(-; gaet) parameterized by gast can be defined as:
act(comb((e; m:); aad)
Σ
gact oj (ycomb(e;
OfEO
Then, as presented in Sec. 3.2, we can relax Oags and gast into continuous space Bagg and fact by leveraging the Gumbel-Softmax technique.
C.2 SCORING FUNCTION FORMULATION
As mentioned in Sec. 3.2, the GNN model X embeds the HKG G R) into the low-dimensional vector space w { R.. ie., w X (G). Besides, it is also important to design a scoring function [(s;w) to interprets the plausibility of the fact based on the learned w (Rossi et al., 2021; Zhang et al., 2020; Shimin et al., 2021). Many promising scoring functions have been proposed in the past decades, including geometric models (c.g., TransE (Bordes et al., 2013) and RotatE (Sun et al., 2018)), neural network models (c.g.. ConvE (Dettmers al., 2018)), tensor decomposition models (e.g., CP (Lacroix et al., 2018), TuckER (Balazevic et al., 2019)). Inspired by the success of literature, regard the scoring function design as component of implementations. In this paper, we focus those scoring functions for facts with high arity (n > 2) and summarize the popular ones in Tab. 5. Note that StarE (Galkin al., 2020) employs the Transformer (Vaswani al., 2017) its scoring function, thus it is not included in Tab. 5.
In principle, MSeaHKG
implement most of existing scoring functions its decoder. But argue that the power of the searched message function could well model the interaction between entities and relations in the encoding step. Within a powerfull encoder, it may be unnecessary to introduce a complex scoring function like CompGCN (Vashishth et al., 2020) and StarE (Galkin et al., 2020) to decode embeddings. In this paper, we simply concatenate the embeddings of known entities and relations in fact and feed it into the linear transformation with a softmax operator.
C.3 LOSS FUNCTION W.R.T. RELATION PREDICTION
Note that the loss function C(X, w 9) introduced in Sec. 3.2 is under the scenario of link prediction task. In the relation classification task, the probability score is formed p² [0, [R i.e., predicting
16

---

Under review as a conference paper at ICLR 2022
the ground truth R. when the relation is missing in (ee...... ((e,,...,,2)) .2). The loss function is defined as:
((X,w;9)==
ΣΣ SES YER
y log pr:
where y if r is the ground truth relation in 8.
C.4 FULL DERIVATION INVOLVED SEC. 3.2
First, we present the full derivation of Eq. 10 and Eq. 11, and their approximation based on Monte- Carlo sampling:
(x ( V (UU)
/ -,o Eunp( Vowpeioo Exopuui(((oo(()),,)))00eee
V Xx V. ( (xxx) px(X)Vul(Xxx::)jx
Second, we build the reparameterization trick X 96 (U)) (mentioned in Sec. 3.2) based Gumbel- Softmax (Jang et al., 2016) or Concrete distribution (Maddison et al., 2016). For simplicity, we simplify è to the parameter 0 for specific operator space O:
exp((log 0, log( - log(U))))/
X, = (U) = E Eo'eo exp((log)))) 0, logg log (U,) )))/T)
(12)
where is the temperature of softmax, and U, ~ Uniform(0.1 1). It has been proven that plimm-~o X, = 1) 0./ Eoreo O,r making the stochastic differentiable relaxation unbiased once converged (Xie et al., 2018), And the details of V Vega(U) can refer to Xie et al. (2018).
D MORE EXPERIMENTS
D.1 EXPERIMENTAL SETUP
D.1.1 HYPER-PARAMETEE SETTINGS
We have summarized the hyper- spper-parameters of this paper in Tab. 6. The hyper-parameter set includes Adam optimizer (Kingma& Ba, 2014), learning rate E (0.1,0.01, 0.001, 0.0001, 0.00001), MPNN layers E {1, 2, 3, 4) (see left part of Fig. 2), # layers in message functions K E 2,,2,3, 4,5) (see right part of Fig. 2), batch size E {64, 128, 256, 512), embedding dimension d E {64, 128, 256, 512]. dropout ratio {0, 0.05, 0.1, 0.15. ... 0.5). label smoothing ratio E {0, 0.1, 0. ... 0.9)). Note that the label smoothing ratio т is employed to relax the one-hot label vector y. In practical, we for the ground truth entity/relation, while y: -//21-1 for link prediction and y: 7/IR|-1 for relation prediction. That is because there are usually a large candidate space for tuned
set y,
relations and entities, while Using one-hot vector is quite restrictive. All hyper-parameters with the help of untuna. samplers TPES ampler (Bergstra et al., 2013; Falkner et al., 2018)!.
1.1.2 DATA STATISTICS
Here we present the statistic summary of the benchmark data sets in this paper. And the links for download them.
hhttps://og readthedocs. baaatteesss.teaaatteeeeeeeeeeeee samplers. www.amppseepeeeee.mmeemp. html
17

---

Under review as a conference paper at ICLR 2022
Table 6: List of typer--arameters in main experiments. W and J are abbreviations of WikiPeople and JF17K, respectively.
Link Prediction
Relation Prediction
Hyperparameters
WikiPeople
JF17K
W-3
J-3
W-4
J-4
WikiPeople JFT7K
Learning rate
0.0001
0.001
0.0001
0.001
0.0001
0.0001
0.0001
0.001
# MPNN layers
1
I
2
2
# Layers in mg(.)
3
2
3
4
4
Batch size
256
128
128
128
256
128
256
128
Embedding dim
256
256
128
128
256
128
128
128
Dropout ratio
0.15
0.2
0.1
0.1
0.05
0.15
0.2
0.15
Label smoothing ratio т
0.3
0.8
0.7
0.5
0.8
0.7
0.1
0.1
Table 7: The statistical summary data sets.
type
data set
# all facts
# facts (n > 2) max arity N
# ent
# rel
train
valid
test
JF17K
100,947
46,320
28.645
322
76,379
24,568
Mixed
WikiPeople
382,229
44,315
47,765
707
305,725
38,223
38,281
WNI8RR
93,003
0
40,943
11
86,835
3,034
3,134
FB15k237
310,116
14,541
237
272,115
17,535
20,466
JF17K-3
34,544
34,544
11,541
104
27,635
3,454
3,455
Fixed
JF17K-4
9,509
9,509
6,536
23
7,607
951
951
WikiPeople-3
25,820
25,820
12,270
66
20,656
2,582
2,582
WikiPeople-4
15,188
15,188
9,528
50
12,150
1,519
1,519
D.1.3 EVALUATION MEASUREMENT
Let ranks, denote the rank ground truth entity at position n of i-th fact = (N,))....,EN) defined
rank = K('' E E Men) f(s':w) f(s:w))++1,
where s' 61. 1n-1. ....,,,.....ee As (Bordes et al., 2013: Wang et al., 2014), we report performance under the "filtered" setting, i.e., evaluating the rank of test fact after removing all corrupted facts that exist in the train, valid, and test data set. That is because true facts in data set should be not considered as faults when evaluating test fact. Correspondingly, rank,, under filtered setting is formed as:
rank; It''' E (en) f(s(:w) ((s $ SSH + 1.
Then we adopt the classical metrics (Bordes et al., 2013; Wang et al., 2014):
Mean Reciprocal Ranking (MRR): 1/N > ΣN 1/rakk..i
Hit@l I, Hit@3, 3, and Hit@ 10, where Hit@k is given by 1/1s| 1 E (rank,, Sk) and II() is the indicator function.
Note that the higher MRR and @it@k values mean better embedding quality.
D.2 CASE STUDY
The relational patterns on KGs (see Appx. B) have been fully investigated (Kazemi & Poole, 2018; Rossi et al., 2021) in existing works. Thus, we first show the case studies on two benchmark KGs WN18RR (Dettmers et al., 2018) and FB15k237 (Toutanova & Chen, 2015) (see Tab. for data statistics and Tab. 8 for experimental results), which have removed the duplicate and inverse relations of WN18 and FB 15k (Bordes et al., 2013; Dettmers et al., 2018). As presented Rossi et al. (2021), the irreflexive, anti-symmetrie, and symmetric relations account for major proportion of these two data sets, especially facts with the symmetric relations reach 37% in WN18RR. We found that the message function searched WNiSRR (Fig. 5 (a)) is the exact RotatE model (Sun al., 2019), which has been proven to cover symmetric relations. As for the message function searched on FB 153377 (Fig. 5 (b)), it first feeds the relation embedding into transformation matrix W. We infer
18

---

Under review as a conference paper at ICLR 2022
91
02
11
02
Wsum
w0sum
idt
concat(
Cat&MLP
(a) WN18RR.
(b) FB15K237.
(c) FB15K237.
Figure 5: Several message functions searched by MSeaHKG on different data sets.
Table 8: The model comparison of the link prediction task on KGs. The results of R-GCN and CompGCN are copied from Vashishth al. (2020), and others copied from Rossi et al. (2021).
FB15k237
WN18RR
type
model
MRR
Hit@1 I
Hit@ 10
MRR
Hit@1 I
Hit@ 10
TransE
0.310
0.217
0.497
0,206
0.028
0.495
Geometric
RotatE
0.336
0.238
0.531
0,475
0.426
0.574
Bilinear
DistMult
0.313
0.224
0.490
0.433
0.397
0.502
Tensor
TuckER
0.352
0.259
0.536
0.459
0.430
0.514
R-GCN
0.248
0.151
0.417
GNNs
CompGCN
0.355
0.264
0.535
0.479
0.443
0.546
Search
MSeaHKG
0.360
0.267
0.545
0.485
0.446
0.554
that is mainly because FB FB15k237 has 237 relations, which more than 11 relations on WN18RR. For the message function searched on facts with high arity, show example on JF17K-3 3 in Fig. 5 (c). demonstrates that the message function tends to be deeper and complex in the high arity case. Note that the full version of message functions searched on WikiPeople (N 9) and JF17K (N 6) is too large to put it on paper. Overall, we can observe that the message functions are data-dependent from Fig.
D.3 ABLATION STUDY
Except for main experimental results, here report the performance of several variants of MSeaHKG (see Tab. 9) to investigate some key designs in this paper, including MSeaHKG",, W MSeaHKG MSeaHKG*t for the search space, MSeaHKGdard darts and MSeaHKG" for the search algorithm.
D.3.1 SEARCH SPACE
We first present the configuration of variants:
MSeaHKG basically enables current GNN searching methods working on HKGs. Inspired by R-GCN (see Eq. 2), we first replace the transform matrix W in mgg(-) (see Eq. to W,. Then, we concatenate the entity embeddings as h (onent(e).......... en O, ..... 0). Note that the number of zero embeddings 0 is equal to Amax n. We utilize the message function ( en)) W,h to replace Eq. 7. Other steps are same with original version.
MSeaHKG only searches operations of operators and in mg(: 0) (i.e., 0 (0 } (0)t }), while keeping the structure of StarE's message functions. Other steps are same with original version.
MSeaHKG only searches structures of the proposed message function mg(:; 0), and sets Ø, to corr, wsum respectively (i.c., 0 {Ø) }). The fixed operations are selected based on better empirical performance. Other steps are same with original version.
19

---

Under review as a conference paper at ICLR 2022
Table 9: The comparison of variants of MScaHKG in the link prediction task on HKGs.
WikiPeople
JF17K
Type
Model
MRR
Hit@)
Hit@3
Hit@ 10
MRR
Hit@]
Hit@ 10
StarE
0.378
0.265
0.452
0.542
0.542
0.454
0.580
0.685
GNNs
G-MPNN
0.367
0.258
0.439
0.526
0.530
0.459
0.572
0.688
S2S
0.372
0.277
0.439
0.533
0.528
0.457
0.570
0.690
Search
MSeaHKG
0.395
0.291
0.470
0.554
0.577
0.481
0.599
0.711
MSeaHKG
0.354
0.233
0.431
0.520
0.512
0.445
0.553
0.671
Variants of space
MSeaHKG
0.385
0.274
0.460
0.548
0.554
0.468
0.591
0,699
MSeaHKGat
0.391
0.278
0.465
0.552
0.563
0.475
0.602
0.706
Variants of algorithm
MSeaHKGGarta
0.373
0.275
0.445
0.535
0.554
0.460
0.588
0.697
MSeaHKG"
0.380
0.281
0.457
0.542
0.563
0.472
0.593
0.701
From Tab. 9, we observe that the simple extension version MSeaHKG even cannot achieve as good performance as existing GNNs (e-g.. StarE and G-MPNN). This verifies the claim that the simple message function in the existing GNN searching method (e.g.. AutoGEL (Zhili et al., 2021) discussed in Sec. 2.2) may not be able to handle the complex correlations between relations and entities HKGs. Moreover, MSeaHKG keeps the same message function structure with StarE but searches suitable operations. Differ from manually tuning operations in StarE, the automatic way is more powerful so that MSeaHKG achieves minor improvement compared with StarE. As for MSeaHKG it can search for more flexible structures of message functions for the given HKG and achieve the best performance among several variants. It can illustrate that the message function design is important to HKG embedding. However, MSeaHKG is still slightly inferior compared with the original version of MScaHKG. This shows that the best structure and operations are dependent. Simply fixing operations to search the structure may lead to the sub-optimum.
D.3.2 SEARCH ALGORITHM
In this paper, we mainly focus on one-shot NAS search algorithms due to their searching efficiency (see more discussion in Sec. 2.1). Existing one-shot NAS algorithms can be roughly categorized into: stochastic differentiable method (e.g.. SNAS (Xie et al., 2018)), deterministic differentiable method (e.g., DARTS (Liu al., 2018)), and policy gradient-based method (e.g., ENAS (Pham et al., 20, ASNG (Akimoto et al., 2019)). Here, we implement two more variants of MSeaHKG, MSeaHK G Gdrrts based on DARTS and MSeaHKG" based on ASNG, to investigate the performance of other two kinds of NAS search algorithms in our application scenario.
MSeaHKGdarts follows DARTS to directly relax O to learnable parameters. Then, the computa- tion in DAG (see Eq. 6) will be reformed to:
h
Σ
of (h 1 o Σ5- 0h
(13)
'y'
Then, are able minimize the loss L(O, () through the gradient VoL(.).
Ml follows the policy gradient-based NAS search algorithm derive:
V (XXX, = V / (XX wtt.
C(X, 9) o
logno (X) (X
(14)
= V Fxxxeex) LX V
where Vore (X) = log (esp@(()ec (X) (X) is the policy gradient trick (Williams, 1992). In practical, we utilize ASNG (Akimoto et al., 2019) to instantiate Eq. 14, which implements the fisher information matrix for fast convergence and adaptive learning rate for robustness.
We here analyze the model comparison between original MSeaHKG with its variants M and MSeaHKGderts From Tab. 9 and Tab. 10, observe that MSeaHKG and MSeaHKGr have
20

---

Under review as a conference paper at ICLR 2022
Table 10: on HKGs.
The training time comparison (in hours) of GNN-based models in the link prediction task
HKGs
Arity=3
Arity=4
Type
Model
WikiPeople
JF17K
W-3
J-3
W-4
G-MPNN
15.4
4.3
1.2
1 0.1
0.5
+
0.1
0.6 + 0.1
GNNs
StarB
137.5
16.7
2.6
+
4.7
0.8
2.3
+ 0.4
1.9 0.2
Search
MSeaHKG
3.79
7.7
1.8
0.4
0.9
0.1
1.1 0.2
Variants
MSeaHKG
2..
2. 21
0.3
1.5
0.2
1.3 0.1
algorithm
MSeaHKG"
35.1 3.0
10.3 + 1.7
2.3 0.3
1.5 0.2
1.4 0.2
1.1 0.1
better performance than MSeaHKGdart in both effectiveness and efficiency comparisons. First, DARTS aims to train a supernet by mixing all candidate operations during the searching phase, then it will derive discrete architecture after finishing the search. But the weights o in Eq. 13 cannot cannot converge to a one-hot vector, which lead to performance collapse after removing IO operations in O (Zela et al., 2019; Chu et al., 2020). Second, it will consume more computational resources when maintaining all operations during the search. Instead, MSeaHKG and MSeaHKG" are to train discrete architectures in searching (the bounded discreteness of MSeaHKG is discussed in Appx. C.4), which avoids performance collapse and large computational overhead. As for the comparison between MSeaHIGG with MSeaHKG" MSeaHKG achieves slight improvements, That is mainly because MSeaHKG directly calculates the gradient w.r.t. C from the loss L()), while MSeaHKGT takes the loss ((-) reward to feed it to a RL controller.
From Tab. 10, we also can observe the efficiency comparison between GNN-based models (G-MPNN, StarE, and MSeaHKG). Like other NAS methods, MSeaHKG requires two training phases, searching architecture and training the searched architecture from the scratch. Thus, it needs more running time compared with G-MPNN. Moreover, both G-MPNN and MSeaHKG utilizes the simple decoders (i.e., scoring function discussed in Appx. C.2), while StarE adopts the complex transformer as its decoder. Thus, StarE is less efficient.
D.4 MSFAHKG CAN BE TRANSFERRED TO OTHER GRAPH-BASED TASKS.
Since many configurations of MSeaHKG are inspired by GNNs and GNN searching methods, transfer MSeaHKG to other GNN-related tasks to further investigate its capability.
First, we conduct extensive experiment on social recommendation (Fan et al., 2019), where the recommendation data sets are formed as multi-relational graphs. In the data set Ciao 2 nodess represent the users and items, edges have two main types: 1) 5 level of ratings 21, 3, 4, 5) between users and items, 2) connections among users. The goal of the task to predict the unknown ratings of items given by users. After treating the 5 ratings 5 edge types, the recommendation task is converted to the relation prediction task, i.e., predict the rating r given ?(user, item). To compare MScaHKG with literature more conveniently, we follow Fan al. (2019) to utilize the Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) as the evaluation metrics, and 60% training data. We let MSeaHKG compute top-3 scores like score(2( (uuuer,, item)) ). = score(4( (user, item))), e score(5 (5( user, item)). then adopt weighted sum to output the final rating like (a + b. + e 5)/(a + b + c). The experimental report in Tab. 1l shows MS has good generalized ability to the social recommendation task, which is consistent with the performance on KGs (i.e., multi-relational graphs).
Second, we extend MSeaHKG to graph-level tasks. We incorporate one more essential component at the final layer of MPNNs, i.e., readout funcion rd(-). General MPNNs employ rd(-) to output the representation of whole graph G(E, R, S) by aggregating the node embeddings as:
hg = rd(fe))aeE).
Due to the modeling of edge representations, MSeaHKG slightly adjusts the readout function as:
hG = re((eessr.e)lrreeeeess)
"https://www cse. www.see....edu/.ee http:///caannaaaaaaattatteeeeees htm
21

---

Under review as a conference paper at ICLR 2022
Table 11: The model performance of extending MSeaHKG to other tasks.
(b) The comparison the graph classification task. The results of baselines PROTEINS and IMDB-M copied from PAS (Wei al., 2021), and those on MUTAG are copied from GIN (Xu al., 2018).
(a) The comparison on rating pre- diction task of social recommendation. The results of baselines are copied from Fan al. (2019).
type
model
PROTEINS
IMDB-M MUTAG
Ciao
GCN
0.7484
0.5040
0.8560
model
MAE
RMSE
GNNs
GraphSAGE
0.7375
0.4853
0.8510
PMF
0.9520
1.1967
GIN
0.7620
0.5230
0.8940
TrustMF
0.7681
1.0543
GraphNAS
0.7520
0.4827
NeuMF
0.8251
1.0824
NAS
SNAG
0.7233
0.5000
GraphRec
0.7540
1.0093
for
You et al. (2020)
0.7390
0,4780
MScaHKG
0.7511
1.0021
GNNs
PAS
0.7664
0.5220
MSeaHKG
0.7724
0,5317
0.8922
We implement the choices of readout function as [global mean, global mar, global.sum). We report the accuracy in Tab. 11b. Among 3 data sets, the graphs in MUTAG are multi-relational, thus most of GNN searching methods do not include it in empirical study. We can observe that MScaHKG achieves not bad performance on these data sets.
22


Reviews:
[{"review_id": "tCh2dpuKWrD", "reviewer": "Reviewer_WuXj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "I think the work is novel in including the message function in the search space for NAS. This introduced a novel way to learn the representation using flexibility of the knowledge from the message functions. The search algorithm is a variation of the NAS tailored for this framework. \n\nThe experiments shows better results for the proposed method in comparison with other baselines. The other methods shows variable effectiveness over different datasets, but the proposed model beats all of them in all the presented results. \n\nThe ablation study also looks good and shows effect of different message passing functions and algorithms for the framework. \n\nWe have result on different arity (3 and 4) for the same dataset. It would be interesting to see the relation between arity and effectiveness of the method tabulated.\n\nAuthors have shown result in link prediction task and relation prediction tasks. It would be interesting to see the performance in more variety of tasks.\n\nIt may be outside of the scope of this paper, but one question can be how should the framework perform in non HKG problems? May be we can get good result for other one shot problems in graph.\n\n\n\n\n\n", "summary_of_the_paper": "\nIn this paper, authors propose a new message function searching method for Hyper Relational Knowledge Graphs. They also proposed a search space of message functions. Finally the authors proposed a one shot NAS algorithm for searching in the message function space and also over other GNN components for a given Hyper Relational Knowledge Graph.\n\n\n", "summary_of_the_review": "Overall I think the paper is technically strong and authors have shown effectiveness of their method. Although the scope may be somehow limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K8fePE8fic-", "reviewer": "Reviewer_y4dP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Overall I feel the paper is nicely written and easy to follow. I am slightly confused by the main point of the paper. Is the main contribution of the paper proposing a new HKG method that achieves state-of-the-art in link prediction and relation prediction over HKGs, or the main contribution is a NAS platform with different configurations of GNNs in the search space? It seems that the authors claim the contribution to be the second but in the experiment, they just show that here’s a new method that achieves SOTA compared with prior methods. I am mostly curious about the performance of other prior baselines after doing the same hyperparameter search using the proposed framework. Besides, aren’t all the methods and details in Sec 3.2 already well established in the literature, including but not limited to how to frame the optimization as a search problem, gumbel softmax, etc.\n\n- “But in scenarios of HKGs, it is important to know which relation (edge type) makes entities (nodes) adjacent.” What do you mean by this sentence?\n- It should be “LP/RP” instead of “LR/RP” in the last row of Table 1.\n- “firs” -> “first”, ‘cases studies” -> “case studies”\n- The paper mentioned that they relax the discrete search space into a continuous and probabilistic space. How did you relax discrete parameters like different aggregation and activation functions? \n- What’s the difference between the position matrix and role embedding? I assume both are used to distinguish entities at different positions in the hyper edge.\n- Many of the configurations in Sec. 3 seem to be also applicable in general graph neural networks, e.g, concatenation, composition, residual connection and so on. It would be helpful to clarify which ones are specific to HKG, which ones are not. Otherwise it’s confusing and it’s unclear how novel the proposed design choices are.\n", "summary_of_the_paper": "The paper proposes a new neural architecture search framework over graph neural networks in hyper relational knowledge graphs (HKG). The main motivation is that the current GraphNAS system does not have an emphasis on edge representations and how message passing functions handle position-sensitive information on HKG. The paper proposes a new search space of these configurations and proposes a new HKG method that achieves state-of-the-art on several benchmarks.", "summary_of_the_review": "I feel the paper is not currently clear in the contribution and there are some disjoint between the method section and the experiment section. Also I am not entirely convinced of the necessity of a new NAS framework specifically designed for GNNs on HKGs. It seems like a problem of limited scope, and many new configurations also apply to GNNs in other tasks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-B9laf7TQVg", "reviewer": "Reviewer_gMZD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Pros:  \n* Automatically searching message-passing functions for HKGs is an important yet underexplored problem.  \n* The proposed search space seems to incorporate most state-of-the-art MPNNs for HKGs.  \n* The experimental results are comprehensive, with ablation studies, examples, and various analyses provided in the appendix.  \n\nConcerns and questions:  \n* The writing of the paper could be improved, especially the methodology part where there are many symbols involved, which is hard to follow.   \n* Some experimental results are not consistent with results presented in previous papers (e.g., StarE and G-MPNN). The authors need to explain where the difference comes from.  \n* The code is not available yet, so there is currently no way to assess the proposed method experimentally. I believe the authors would make the code publicly available at publication time?  \n", "summary_of_the_paper": "In this paper, the authors propose to conduct neural architecture search (NAS) for hyper-relational knowledge graphs (HKGs). Compared with normal graphs, HKGs can better model the complex relationships between different entities. Specifically, a novel search space is proposed inspired by recent message-passing GNNs on HKGs such as G-MPNN, CompGCN, StarE, etc., and a differentiable search algorithm is utilized. Experiments demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "Overall, I think this paper makes non-trivial contributions in the search space design for HKGs with extensive experiments, and thus may be interesting to both KGs and NAS community.\n\n===after rebuttal===\nI have read the rebuttal and my score remains positive.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies  neural architecture search for hyper-relational knowledge graphs (HKGs).  A  search space is put-forth, and  it is  searched with a differentiable search algorithm. The paper is technically strong. However,  there are some concerns about the narrow scope of the problem/solution, given that other more general formulations have also been studied.
Decision: Reject