Year: 2021

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 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 of message functions to 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 to 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.

heading: 1 INTRODUCTION
text: Knowledge base (KB) (Auer et al., 2007) is an important tool to organize and explore human knowledge, thereby promoting a 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(e1, · · · , en) (n is arity) that represents the relation r ∈ R between real-world entities ei ∈ E. 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 E into a d-dimensional vector space R ∈ R|R|×d,E ∈ R|E|×d. In last decades, the research community mainly focuses on embedding knowledge graphs (KGs) that only contain binary facts {r(e1, e2)}, e.g., isCaptialOf(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 a 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) because n-ary facts are widespread in KBs, e.g., playCharacterIn(LeonardNimoy,Spock,StarTrek1). 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(e1, . . . , en) : n ∈ {2, . . . , N}} named as hyper-relational KGs (HKGs). Unfortunately, it 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 a 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 a 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 G(E,R, S), respectively. The length of MRHG’s edge (e1, . . . , en) (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(e1, . . . , en) ∈ S. Under the MRHG modeling, these works adapt powerful graph
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 (e.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 representationsR 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, 2018). Its performance may not be good if there are many non-symmetric relations existed (see Appx. B.1). It may be a potential solution to design a universal message function to cover as many relational patterns as possible. But covering a certain pattern does not mean that the model can reach good performance on it (Meilicke et al., 2018; Rossi et al., 2021). Moreover, a pioneer work AutoSF (Zhang et al., 2020) shows that designing data-aware models can consistently achieve high performance on any given KGs. Thus, dynamically searching message functions could be an effective way to 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 to 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 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. Thus, we identify the necessary computation operators that are domian-specific 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, we 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 a suitable GNN that can achieve high performance on the given HKG.
• Inspired by rigid message function designs, we define a 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-art performance by designing data-aware message functions. Besides, we also transfer MSeaHKG to other graph-based tasks and further investigate its capability.

heading: 2 RELATED WORK

heading: 2.1 ONE-SHOT NEURAL ARCHITECTURE SEARCH IN GRAPH NEURAL NETWORK
text: 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

heading: Type Model Scenarios Message Function
text: 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 an 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.e., evaluating the performance of architecture after training it to 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 et 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. 1, 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:
step1 : mi ← agg({mgc(ei, ej)}ej∈N(ei)), step2 : ei ← act(comb(ei,mi)), (1)
where ei ∈ Rd represents the embedding of node ei, mi is the intermediate embeddings of ei gathered from its neighborhood N(ei). The search space of operators in Eq. 1 are summarized into:
• Message Function mgc(·): The message function decides the way to gather information from a neighborhood ej of the center node ei. Zhang et al. (2021) summarizes the typical message in existing GNN searching methods as mgc(ei, ej) = aijWej , where aij denotes the attention scores between nodes ei with ej . Besides, we present more message function designs in Tab. 1.
• Aggregation Function agg(·): It controls the way to aggregate message from nodes’ neighborhood. Usually agg ∈ {sum,mean,max}, where sum(·) = ∑ ej∈N(ei)mgc(ei, ej),
mean(·) = ∑ ej∈N(ei)mgc(ei, ej)/|N(v)|, and max(·) denotes channel-wise maximum.
• Combination Function comb(·): It determines the way to merge messages between neighborhood and node itself. In literature, comb is selected from {concat, add,mlp}, where concat(·) = [ei,mi], add(·) = ei + mi, and mlp(·) = MLP (ei +mi) (MLP is Multi-layer Perceptron).
• Activation Function act(·): [identity, sigmoid, tanh, relu, elu] are some of the most commonly used activation functions (Gao et al., 2020).
Overall, mgc(·) 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 hij between ei and ej as input without learning edge embeddings, and recent AutoGEL (Zhili et al., 2021) simply extends the message function mgc(·) to learn edge embeddings without studying the interactions between entities and relations, thereby failing to handle the LP/RP tasks on HKGs.
Entity Embed Relation Embed
Computing Operator
Role/Position Embed
Positional matrix Transform matrix
...
...
Cat&MLP
Message Function Space

heading: 2.2 GRAPH NEURAL NETWORKS FOR KG/HKG EMBEDDING
text: As introduced in Sec. 1 and Sec. 2.1, message functions in classic GNNs simply aggregate messages from adjacent nodes (see Tab. 1 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) proposes to model relations R in KGs through relation-specific weight matrix Wr ∈ Rd×d for r ∈ R in message functions, which is instantiated as:
ei = act(sum({Wrej}r(ei,ej)∈I(ei))), (2) where I(ei) = {r(ei, ej) ∈ S : r ∈ R, ej ∈ E} is the set of relational edges incident on ei. But such relation modeling may lead to the over-parameterization issue because there are many relations in KGs. Therefore, CompGCN (Vashishth et al., 2020) utilizes the embedding vector r to represent the relation instead of weigh matrix:
ei = act(sum({Wλ(r)φ(ej , r)}r(ei,ej)∈I(ei))), r = Wr (3) where λ(r) records the directional information of edges. The entity-relation composition operator set {sub,mult, corr} is inspired by classical scoring function design in existing KG embedding models, such as element-wise subtraction sub(·) = ej − r (Bordes et al., 2013), inner product mult(·) = ej ∗ r (Yang et al., 2015), circular correlation corr(·) = ej ◦ r (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 roj of entity ej and assumes a hyperrelational fact r(e1, . . . , en) is composed by a base triplet r(es, eo) with a set of role-value pairs {(roj , ej)} such that r(es, eo, {(roj , ej)}). Then StarE takes base relation with the role-value pairs as a hyper-relation and performs the composition operator φr(·) on the hyper-relation with base entity: es = act(sum({Wλ(r)φr(eo, γ(r,hr))}r(es,eo,{(roj ,ej)})∈I(es))), hr = W sum({φo(roj , ej)}j),
where hr is the hidden representation aggregated from the role-value pairs, γ(·) is a concatenate operator to output the representation of hyper-relation. The update of r in StarE is similar to CompGCN. Instead of requiring role information, G-MPNN (Yadati, 2020) proposes to model positional information in GNNs:
ei = act([ei, agg({rs,P (s) ∗ ∏
j∈{1,...,n}
pej ,s ∗ ej}r(e1,...,en)∈I(ei))]), (4)
where s represents r(e1, . . . , en) ∈ S, P (s) : s→ {1, . . . , np} is a positional mapping (np ≤ |E|), and pej ,s is the positional embedding vector of ej on fact s. To intuitively check the difference of message functions, we plot the framework of general MPPNs and GNNs for KGs/HKGs in Fig. 1.

heading: 3 MSEAHKG
text: In this section, we first propose a 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 on the proposed space and solve it by leveraging an efficient search algorithm.

heading: 3.1 GNN SEARCH SPACE DESIGN FOR HKG EMBEDDING
text: 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 is 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. 1 and Fig. 1) does not apply to 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 as presented in Sec. 2.2. From Fig. 1, we can observe that those message functions are mainly different in these two aspects: 1) the operators (e.g., W , φ, γ) 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, γ in StarE, agg(·) in G-MPNN. Moreover, the structure of message functions for HKGs (StarE and G-MPNN) tends to 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 be represented as a certain correlation among r(pemu(e1, . . . , en)) (check more in Appx. B.2), where pemu denotes the permutation. For example, r is symmetry if r(ej , ei) must be true when r(ei, ej) is true. Therefore, the message function in the search space must be able to handle such correlation in the form of r(pemu(e1, . . . , en)). In the next, we first introduce the space of operators, and then discuss how they deal with r(pemu(e1, . . . , en)).
• Positional Transformation MatrixWP (e): The position of entity in a fact can largely determine the plausibility of the fact. For example, isCaptialOf(Beijing,China) is true while isCaptialOf(China,Beijing) is false. G-MPNN utilizes the positional embedding pe,s and re,P (e) to encode the position of entity e and relation r in different facts, which requires the model complexity O(d|S|(|E|+N)). However, the training data set is very sparse in KBs. Such over-parameterization 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→ {1, . . . , N}, then the positional matrix is able to transform e to the permutation position in pemu(·) by WP (e)e, whereWP (e) consumes O(Nd2) (|S| d in practice).
• Concatenate Operator γ(·): It mainly determines the concatenation way between embedding vectors. In this paper, we set Oγ = {concat,mult, wsum} (Galkin et al., 2020), where wsum is the weighted sum. In general, γ(·) can concatenate embeddings after the positional transform matrixWP (e), i.e., encoding pemu(e1, . . . , en).
• Role Embedding ro: Unlike the positional information of entities encoded byWP (e), the role embedding is utilized to model the semantic information of entities (Liu et al., 2021). For example, the roles in 2nd position of facts playCharacerIn(actor:ZacharyQuinto,character :Spock,movie:StarTrek) and actorAwardIn(actor:ZacharyQuinto,award: BC-BSFC,movie:StarTrek) are different though other entities and roles are same. Thus, the model should be able to capture the role of candidate entities after usingWP (e), e.g., BC-BSFC is unlike to be the 2nd entity of playCharacerIn since its role is award instead of character.
• Composition Operator φ(·): Following CompGCN, we utilize composition operator φ(·) to capture message between the node and edge embeddings before aggregation step. Note that φ actually encodes the interaction between r and pemu(e1, . . . , en). While CompGCN and StarE empirically selects the most proper φ(·), we include this operator into the space X . Thus, MSeaHKG is able to automatically search for the most suitable φ(·) in a more efficient way. We combine the settings of CompGCN and StarE to set Oφ = {sub,mult, corr, rotat} (rotat (Sun
Under review as a conference paper at ICLR 2022
Positional matrix
... ... ... ...
...
Cat&MLP
CompGCN G-MPNNStarEMPNN Computing Operator Transform Matrix entity relation role/position
Positional matrix
... ... ... ... ...
Cat&MLP
CompGCN G-MPNNStarEMPNN Computing Operator Transform Matrix entity relation role/position
Positional matrix
... ... ... ...
...
Cat&MLP
CompGCN G-MPNNStarEMPNN Computing Operator Transform Matrix entity relation role/position
et al., 2019), see 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) = h operation allows inputs to skip one layer in the message function; (2) UnlikeWP (e), the transform matrixW processes the hidden representations.
Among above components, we fix the role embedding and positional transform matrixWP (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 , φ, γ, idt} for searching. As shown in Fig. 2 (c), we denote the node oki as i-th operator of O in k-th layer and hki be the hidden representation outputted by oki . Then we have:
{h0i }2n+1i=1 = {WP (e1)e1, . . . ,WP (en)en, ro1 , . . . , ron , r}, (5)
hki = o k i ( {θkijhk−1j } |O| j=1 ) , for k ∈ {1, . . . ,K} and i ∈ {1, . . . , |O|}, (6)
where θkij ∈ {0, 1} controls the connection between oki with o k−1 j . Note that {h0i } n+1 i=1 = {WP (e1)e1, . . . ,WP (en)en, r} if role information is not available in the given HKG. From Fig. 2 (c), we can observe that the structure of message functions is controlled by {θkij}. To avoid manual operation selection, we also search for concrete operations of two operators φ and γ. Given the operator set Oφ and Oγ , let θφki , θ γk i ∈ {0, 1} records the selection i-th operation oi ∈ Oφ,Oγ at k-layer respectively. Then, φ and γ perform the computation in Eq. 6 could be φk(h) = ∑ θφki oi(h) and γ k(h) = ∑ θγki oi(h). Note that ∑ i θ φk i = 1 and ∑ i θ γk i = 1. Let θmg = {θkij} ∪ {θ φk i } ∪ {θ γk i }. The message function parameterized by θmg is defined as:
mg ( r(e1, . . . , en);θ mg ) = MLP&concat({hKi } |O| i=1), (7)
where we simplify role embedding ro for simplicity and hKi is outputted by the last layer of Eq. 6. 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 MSeaHKG 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 Θ = {θmg,θagg, . . . } be parameter set for all operators selection in our MPNN framework. Then, an architecture can be represented as XΘ = {mg(·;θmg), agg(·;θagg), · · · } (check other functions in Appx. C.1). And existing GNNs for KG/HKG embeddings actually can be represented by different instantiations of Θ. Overall, a GNN model XΘ encodes the given HKG G into embedding space ω = {E,R}, i.e., ω = XΘ(G).

heading: 3.2 SEARCH ALGORITHM DESIGN
text: In this subsection, we introduce how to select the GNN XΘ that can achieve high performance on the given G. First, we evaluate performance of XΘ based on the HKG embedding ω = {E,R} since XΘ is utilized to encode G(E,R, S) into ω, i.e., ω = XΘ(G). In the KG/HKG embedding, the scoring function f(s;ω) is to verify the plausibility of fact s = r(e1, . . . , en) by decoding ω (check more about scoring functions in Appx. C.2). Generally, the good embedding ω can make f(s;ω) to distinguish true or false for a given fact s. Thus, we build evaluation of XΘ on f(s;ω). Taking link prediction task (predict the missing entity in a fact, e.g., r(?, e2, . . . , en)) as example, let a scoring function f(s;ω) decode ω and output a score matrix ps ∈ [0, 1]|E|, where pse 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 `(f(s;ω)) = ∑ e∈E y s e log p s e, where y s e = 1 if e is the ground truth
otherwise 0. Subsequently, we denote L(XΘ,ω;G) = ∑ s∈S `(f(s;ω)) to calculate the overall loss of a GNN model XΘ with the HKG embedding ω on G(E,R, S). Formally the GNN search problem for a given HKG G is formulated as:
min Θ,ω L(XΘ,ω;G). (8)
Solving Eq. 8 is a non-trivial task because XΘ (e.g., XΘ = {agg : sum, act : relu, . . . }) is from a large space. For example, only the structure space size {θkij} of message function reaches to O(2K|O|
2+(2N+1)|O|). And XΘ is discrete, indicating the gradient-based optimization cannot be employed since∇XΘL(·) does not exist. To enable an efficient search, we first relax the parameters of GNN model Θ from a discrete space into a continuous and probabilistic space Θ̄. More specifically, θkij ∈ {0, 1} restrictively controls the connectivity between oki with o k−1 j , while θ̄ k ij ∈ [0, 1] is the probability that oki is connected with o k−1 j . Then, let X ∼ pΘ̄(X) represent a GNN model X being sampled from the distribution pΘ̄(X). We reformulate the problem in Eq. 8 into:
min Θ̄,ω EX∼pΘ̄(X)[L(X,ω;G)], (9)
where E[·] is the expectation. To compute the gradient w.r.t. Θ̄, we first utilize the reparameterization trick X = gΘ̄(U) (Maddison et al., 2016), where U is sampled from a uniform distribution p(U). Then the gradient w.r.t. Θ̄ and ω is computed as (check full derivation in Appx. C.4):
∇Θ̄EX∼pΘ̄(X)[L(X,ω;G)] = EU∼p(U)[L ′(gΘ̄(U), ω;D)∇Θ̄gΘ̄(U)], (10)
∇ωEX∼pΘ̄(X)[L(X,ω;G)] = EX∼pΘ̄(X)[∇ωL(X,ω;G)]. (11) Note that ∇Θ̄gΘ̄(U) can be computed if gΘ̄(U) is differentiable. Inspired by SNAS (Xie et al., 2018), we leverage Maddison et al. (2016); Jang et al. (2016) to instantiate gΘ̄(U) (see Appx. C.4).

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETUP
text: The experiments are implemented on top of PyTorch (Paszke et al., 2019) and performed on one single RTX 2080 Ti GPU. Appx. D.1.1 introduces the details of hyper-parameters.
Data Sets. The details of data sets are summarized into Tab. 7 in Appx. D.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 WikiPeople 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(?, e2, · · · , en). The relation classification task needs to predict the missing relation in a fact when all entities are known, i.e., ?(e1, · · · , en). We employ Mean Reciprocal Ranking (MRR) (Voorhees, 1999) and Hits@{1, 3, 10}. All reports are in the “filtered” setting (see more in Appx. D.1.3).
Baselines. 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 is upgrade version of m-TransH (Wen et al., 2016) that extended from TransH (Wang et al., 2014); (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 is 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 NeuInfer (Guan et al., 2020); (4) Multi-linear models: The final score of HypE (Fatemi et al., 2020) and RAM (Liu et al., 2021) is computed by multi-way inner product which is extended from bilinear KG embedding models (Yang et 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.
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 et al., 2018) leverages CANDECOMP/PARAFAC decomposition (Hitchcock, 1927), while n-TuckER (Balazevic et al., 2019) is based on Tucker decomposition (Tucker, 1966). GETD (Liu et al., 2020) proposes to reduce the model complexity by tensor ring decomposition.

heading: 4.2 MAIN EXPERIMENTAL RESULTS
text: The main results on HKGs (i.e., WikiPeople and JF17K) have been summarized into Tab. 2 and Tab. 3. Compared with Geometric and classic NN-based methods (e.g., NaLP), GNNs methods (e.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 is 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
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. 1 and Appx. A, the MRHG could be a more natural way to represent HKGs, thereby MSeaHKG benefits from building a 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 NN-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 is 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.

heading: 4.3 MORE INSIGHTS VIA EMPIRICAL STUDY
text: Due to the space limitation, we include more experimental results in 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: (1) 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; Akimoto et al., 2019) to compare the searching effectiveness and efficiency of one-shot NAS search algorithms in our scenarios. Third, we transfer MSeaHKG to more variety of graph-based tasks in Appx. D.4.

heading: 5 CONCLUSION
text: In this paper, we propose a new message function searching method for HKGs, named MSeaHKG. First, we present a novel search space of 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 an 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.

heading: A DISCUSSION ON THE MODELING OF HKG
text: Given a set of facts with the fixed arity {r(e1, . . . , en)}, tensor models (e.g., CP (Lacroix et al., 2018) and TuckER (Balazevic et al., 2019)) use a (n+1)-dimensional tensorGn+1 ∈ {0, 1}|R|×|E|×···×|E| to represent facts, whereGn+1r,1,...,n = 1 represents the fact r(e1, . . . , en) existed otherwiseG n+1 r,1,...,n = 0. Then, tensor models leverage the tensor decomposition techniques to decompose Gn+1 into embeddingsR and E with a core tensor Zn+1 ∈ Rd×···×d:
Gn+1 = Zn+1 ×1 R×2 E ×3 · · · ×n+1 E. Obviously, a tensor Gn+1 can only model facts with the fixed arity n. Thus, we have to build {G2, . . . ,GN+1} to model the facts with mixed arities S = {r(e1, . . . , en) : n ∈ {2, . . . , N}} and decompose them into N − 1 sets of entity and relation embeddings, such as {En,Rn}Nn=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-relational hypergraphs (MRHGs) G(E,R, S) could be a more natural way to represent HKGs. We illustrate examples of KGs and HKGs in Fig. 3 (a) and (b), respectively. Given a fact with high arity (e.g., playCharacterIn(e1,e3,e5)), MRHG can first store the correspondence between multiple entities by a hyperedge (e1, e3, e5), then label this hyperedge with the relation playCharacterIn. Moreover, Fig. 3 (b) demonstrates that the facts with mixed arities (n ∈ {2, 3} in this example) can be represented by a MRHG. Thus, MRHG allows us to directly encode a 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.
... ...
(a) HolE (Nickel et al., 2016).
... ...
(b) RotatE (Sun et al., 2019).
... ...
(c) n-CP (Lacroix et al., 2018).
... ...
(d) n-DistMult (Yang et al., 2015).
Figure 4: Several instantiation cases of MSeaHKG message function space. ◦ denotes circular correlation corr(·) (Nickel et al., 2016), ∗ denotes inner product mult(·) (Yang et al., 2015), − denotes the substraction sub(·) (Bordes et al., 2013), ? is from RotatE (Sun et al., 2018).
Besides, HKGs generally contain more complete information compared with KGs. For example, it 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-Clique Conversion, has been verified to be irreversible and caused the information loss in the facts with high arities (Wen et al., 2016). Therefore, we believe that HKG could be a potential solution to solve complex Q&A scenarios.

heading: B DISCUSSION ON DATA-LEVEL PROPERTIES OF KGS/HKGS AND MESSAGE FUNCTION DESIGN

heading: B.1 DATA-LEVEL PROPERTIES IN KGS: RELATIONAL PATTERNS
text: In the past decades, the research community has found that the relations of KGs exhibit different patterns. For example, we can infer that neighborOf(location2,location1) must be true as long as neighborOf(location1,location2) is true, like neighborOf(ShenZhen,HongKong). But for other relations (e.g., largerThan), we know largerThan(value2,value1) must be false if largerThan(value1,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.e., pursuing expressiveness. Given the learned embeddings ω = {E,R}, the scoring function f(·) is proposed to evaluate whether the fact is true or false (check Appx. C.2 and Tab. 5 for more details about scoring function). For the sake of understanding, we here present the requirements of several relational patterns on scoring functions:
• Symmetry: r is symmetry if r(ej , ei) must be true when r(ei, ej) is true, i.e., f(r(ei, ej)) = f(r(ej , ei))
• Anti-symmetry: r is anti-symmetric if r(ej , ei) must be false when r(ei, ej) is true, i.e., f(r(ei, ej)) = −f(r(ej , ei)).
• Asymmetry: The plausibility of r(ej , ei) is unknown when r(ei, ej) is true, f(r(ei, ej)) 6= f(r(ej , ei)).
• Inverse: r1 and r2 are inverse relations if r1(ei, ej) is true and r2(ej , ei) is true. Then, f(r1(ei, ej)) = f(r2(ej , ei))
As mentioned in Sec. 1, the message function of G-MPNN may not be able to infer the non-symmetric relations. Suppose that s1 = r(e1, e2) is true and r is one of any non-symmetric relations (e.g., antisymmetry s2 = r(e2, e1) must be false). Let hi be the entity feature and hr be the relation feature. According to the message function of G-MPNN in Eq. 4, we can learn the hidden embeddings ofmi: m1 = m2 = hr ∗ h1 ∗ pe1,s ∗ h2 ∗ pe2,s Then ei are updated withmi. With the scoring function
of G-MPNN (multiple inner product), we can compute f(r(e1, e2)) = hr ∗ pe1,s ∗ e1 ∗ pe2,s ∗ e2. Because e1, e2 are seen in s1, G-MPNN will assign the positional embeddings e1, e2 in s1 when computing the score of s2, thereby leading f(r(e1, e2)) = f(r(e2, e1)). Thus, we argue that the fixed message function is 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.

heading: B.2 DISCUSSION ON THE CAPABILITY OF MESSAGE FUNCTIONS TO COVER RELATIONAL PATTERNS ON HKGS
text: As mentioned in Appx. B.1, pursuing expressiveness is one way to 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 mean achieving good performance even the model can cover those relational patterns. Thus, AutoSF (Zhang et al., 2020) proposes to search bilinear-based scoring functions for KGs and consistently achieve good performance. Inspired by literature, MSeaHKG 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, we roughly summarize a high level representations of relational patterns in the scenario of high arity as:
f(r1(pemu(e1, . . . , en));ω)?f(r2(pemu(e1, . . . , en));ω),
where r1, r2 may be same relation or different, pemu(·) represents the permutation of n entities {ei}ni=1, and ? ∈ {=, >, 6=,¬}. For example, f(r1(pemu(e1, . . . , en));ω) = f(r1(pemu(e1, . . . , en));ω) indicates r1 is a symmetry. In this paper, since our scoring function design is a linear transformation (see Appx. C.2), the design of message function in MPNNs (i.e., ω = XΘ(G)) will be the crucial component to capture relational patterns. To capture the permutation information pemu(·), we first utilizeWP (e) to encode the positional information, which transforms entity embeddings into corresponding positions. Then, the operator γ(·) concatenates the entity embeddings after encoding positional information. Lastly, the operator φ(·) computes the interaction between r with ei. In other words,WP (e) and γ(·) are employed to represent pemu(·), and φ(·) is utilized to represent the correlation between r 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 et al., 2018)) and GNNs
for KGs/HKGs can be instantiated as special cases in the MSeaHKG space. We have demonstrated several examples of classic scoring function designs in Fig. 4. Note that the expressiveness of these models has been fully investigated in literature. Every model can cover one or multiple relational 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 a GNN model that can adapt to the relational patterns of the given HKG.

heading: C SUPPLEMENTARY OF SEARCH ALGORITHM

heading: C.1 THE PARAMETERIZATION OF OTHER GNN COMPONENTS
text: Generally, the relaxation of other GNN components (e.g., aggregation and activation) is consistent with φk(h) = ∑ θφki oi(h) and γ k(h) = ∑ θγki oi(h) as presented in Sec. 3.1. Here we illustrate more details.
• Let Oagg = {sum,mean,max} be the set of candidate aggregation functions and mg(r(e1, . . . , en);θ
mg) be the output from Eq. 7. Then, the aggregation function agg(·;θagg) parameterized by θagg can be defined as:
mi = agg({mg(r(e1, . . . , en);θmg)}r(e1,...,en)∈I(ei);θ agg) = ∑
oj∈Oagg θaggj · oj({mg(r(e1, . . . , en);θ mg)}r(e1,...,en)∈I(ei)).
• Let Oact = {identity, sigmoid, tanh} be the set of candidate activation functions. Then, the activation function act(·;θact) parameterized by θact can be defined as:
ei = act(comb(ei,mi);θ act) = ∑ oj∈Oact θactj · oj(comb(ei,mi))
Then, as presented in Sec. 3.2, we can relax θagg and θact into continuous space θ̄agg and θ̄act by leveraging the Gumbel-Softmax technique.

heading: C.2 SCORING FUNCTION FORMULATION
text: As mentioned in Sec. 3.2, the GNN model X embeds the HKG G(E,R, S) into the low-dimensional vector space ω = {E,R}, i.e., ω = X(G). Besides, it is also important to design a scoring function f(s;ω) to interprets the plausibility of the fact s based on the learned ω (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 (e.g., TransE (Bordes et al., 2013) and RotatE (Sun et al., 2018)), neural network models (e.g., ConvE (Dettmers et al., 2018)), tensor decomposition models (e.g., CP (Lacroix et al., 2018), TuckER (Balazevic et al., 2019)). Inspired by the success of literature, we regard the scoring function design as a component of implementations. In this paper, we focus on those scoring functions for facts with high arity (n > 2) and summarize the popular ones in Tab. 5. Note that StarE (Galkin et al., 2020) employs the Transformer (Vaswani et al., 2017) as its scoring function, thus it is not included in Tab. 5.
In principle, MSeaHKG can implement most of existing scoring functions as its decoder. But we argue that the power of the searched message function could well model the interaction between entities and relations in the encoding step. Within a powerful 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 a fact and feed it into the linear transformation with a softmax operator.

heading: C.3 LOSS FUNCTION W.R.T. RELATION PREDICTION
text: Note that the loss function L(X,ω;G) introduced in Sec. 3.2 is under the scenario of link prediction task. In the relation classification task, the probability score is formed to ps ∈ [0, 1]|R|, i.e., predicting
the ground truth r ∈ R when the relation is missing in ?(e1, . . . , e2). The loss function is defined as:
L(X,ω;G) = ∑ s∈S ∑ r∈R ysr log p s r,
where ysr = 1 if r is the ground truth relation in s.

heading: C.4 FULL DERIVATION INVOLVED IN SEC. 3.2
text: First, we present the full derivation of Eq. 10 and Eq. 11, and their approximation based on MonteCarlo sampling:
∇Θ̄EX∼pΘ̄(X)[L(X,ω;G)] = ∇Θ̄EU∼p(U)[L(gΘ̄(U),ω;G)] = ∇Θ̄ ∫ p(U)L(gΘ̄(U),ω;G)dU
= ∫ p(U)∇Θ̄L(gΘ̄(U),ω;G)dU = EU∼p(U)[∇Θ̄L(gΘ̄(U),ω;G)]
= EU∼p(U)[L′(gΘ̄(U),ω;G)∇Θ̄gΘ̄(U)], ∇ωEX∼pΘ̄(X)[L(X,ω;G)] = ∇ω ∫ pΘ̄(X)L(X,ω;G)dX = ∫ pΘ̄(X)∇ωL(X,ω;G)dX
= EX∼pΘ̄(X)[∇ωL(X,ω;G)].
Second, we build the reparameterization trick X = gΘ̄(U) (mentioned in Sec. 3.2) based on GumbelSoftmax (Jang et al., 2016) or Concrete distribution (Maddison et al., 2016). For simplicity, we simplify Θ̄ to the parameter θ̄ for a specific operator space O:
Xo = gθ̄(U) = exp((log θ̄o − log(− log(Uo)))/τ)∑
o′∈O exp((log θ̄o′ − log(− log(Uo′)))/τ) , (12)
where τ is the temperature of softmax, and Uo ∼ Uniform(0, 1). It has been proven that p(limτ→0Xo = 1) = θ̄o/ ∑ o′∈O θ̄o′ making the stochastic differentiable relaxation unbiased once converged (Xie et al., 2018). And the details of∇Θ̄gΘ̄(U) can refer to Xie et al. (2018).

heading: D MORE EXPERIMENTS

heading: D.1 EXPERIMENTAL SETUP

heading: D.1.1 HYPER-PARAMETER SETTINGS
text: We have summarized the hyper-parameters of this paper in Tab. 6. The hyper-parameter set includes Adam optimizer (Kingma & Ba, 2014), learning rate ∈ {0.1, 0.01, 0.001, 0.0001, 0.00001}, # MPNN layers ∈ {1, 2, 3, 4} (see left part of Fig. 2), # layers in message functions K ∈ {1, 2, 3, 4, 5} (see right part of Fig. 2), batch size ∈ {64, 128, 256, 512}, embedding dimension d ∈ {64, 128, 256, 512}, dropout ratio ∈ {0, 0.05, 0.1, 0.15, . . . , 0.5}, label smoothing ratio τ ∈ {0, 0.1, 0.2, . . . , 0.9}. Note that the label smoothing ratio τ is employed to relax the one-hot label vector y. In practical, we set yi = 1 − τ for the ground truth entity/relation, while yi = τ/|E|−1 for link prediction and yi = τ/|R|−1 for relation prediction. That is because there are usually a large candidate space for relations and entities, while Using one-hot vector is quite restrictive. All hyper-parameters are tuned with the help of optuna.samplers.TPESampler (Bergstra et al., 2013; Falkner et al., 2018)1.

heading: D.1.2 DATA STATISTICS
text: Here we present the statistic summary of the benchmark data sets in this paper. And the links for download them.
1https://optuna.readthedocs.io/en/stable/reference/generated/optuna. samplers.TPESampler.html

heading: Hyperparameters Link Prediction Relation PredictionWikiPeople JF17K W-3 J-3 W-4 J-4 WikiPeople JF17K

heading: D.1.3 EVALUATION MEASUREMENT
text: Let ranki,n denote the rank of ground truth entity at position n of i-th fact s = (r, e1, . . . , eN ), defined as: ranki,n = |{e′ ∈ E \{en} : f(s′;ω) > f(s;ω)}|+ 1, where s′ = (r, e1, . . . , en−1, e′, . . . , eN ). As in (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 a test fact. Correspondingly, ranki,n under filtered setting is formed as:
ranki,n = |{e′ ∈ E \{en} : f(s′;ω) > f(s;ω) ∩ s′ /∈ S}|+ 1.
Then we adopt the classical metrics (Bordes et al., 2013; Wang et al., 2014): • Mean Reciprocal Ranking (MRR): 1/N |S| ∑|S| i=1 ∑N n=1 1/ranki,n;
• Hit@1, Hit@3, and Hit@10, where Hit@k is given by 1/|S| ∑|S| i=1 ∑N n=1 I(ranki,n≤k) and I(·) is
the indicator function.
Note that the higher MRR and Hit@k values mean better embedding quality.

heading: D.2 CASE STUDY
text: 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. 7 for data statistics and Tab. 8 for experimental results), which have removed the duplicate and inverse relations of WN18 and FB15k (Bordes et al., 2013; Dettmers et al., 2018). As presented in Rossi et al. (2021), the irreflexive, anti-symmetric, and symmetric relations account for a major proportion of these two data sets, especially facts with the symmetric relations reach 37% in WN18RR. We found that the message function searched on WN18RR (Fig. 5 (a)) is the exact RotatE model (Sun et al., 2019), which has been proven to cover symmetric relations. As for the message function searched on FB15k237 (Fig. 5 (b)), it first feeds the relation embedding into a transformation matrixW . We infer
Under review as a conference paper at ICLR 2022
... ...
... ...
... ...
that is mainly because FB15k237 has 237 relations, which is more than 11 relations on WN18RR. For the message function searched on facts with high arity, we show an example on JF17K-3 in Fig. 5 (c). It 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. 5.

heading: D.3 ABLATION STUDY
text: Except for main experimental results, here we report the performance of several variants of MSeaHKG (see Tab. 9) to investigate some key designs in this paper, including MSeaHKGWr , MSeaHKGop, MSeaHKGst for the search space, MSeaHKGdarts and MSeaHKGrl for the search algorithm.

heading: D.3.1 SEARCH SPACE
text: We first present the configuration of variants:
• MSeaHKGWr basically enables current GNN searching methods working on HKGs. Inspired by R-GCN (see Eq. 2), we first replace the transform matrixW inmgc(·) (see Eq. 1) toWr. Then, we concatenate the entity embeddings as h = concat(e1, . . . , en,0, . . . ,0). Note that the number of zero embeddings 0 is equal to nmax − n. We utilize the message function mgc(r(e1, . . . , en)) = Wrh to replace Eq. 7. Other steps are same with original version.
• MSeaHKGop only searches operations of operators φ and γ in mg(·;θ) (i.e., θ = {θφki } ∪ {θ γk i }),
while keeping the structure of StarE’s message functions. Other steps are same with original version.
• MSeaHKGst only searches structures of the proposed message function mg(·;θ), and sets φ, γ to corr, wsum respectively (i.e., θ = {θkij}). The fixed operations are selected based on better empirical performance. Other steps are same with original version.
From Tab. 9, we observe that the simple extension version MSeaHKGWr 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 on HKGs. Moreover, MSeaHKGop 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 MSeaHKGop achieves a minor improvement compared with StarE. As for MSeaHKGst, 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, MSeaHKGst is still slightly inferior compared with the original version of MSeaHKG. This shows that the best structure and operations are dependent. Simply fixing operations to search the structure may lead to the sub-optimum.

heading: D.3.2 SEARCH ALGORITHM
text: 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 et al., 2018)), and policy gradient-based method (e.g., ENAS (Pham et al., 2018), ASNG (Akimoto et al., 2019)). Here, we implement two more variants of MSeaHKG, MSeaHKGdarts based on DARTS and MSeaHKGrl 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 Θ to learnable parameters. Then, the computation in DAG (see Eq. 6) will be reformed to:
hki = |O|∑ j=1 αkij · oki ( hk−1j ) , αkij = θkij∑|O| j′=1 θ k ij′ . (13)
Then, we are able to minimize the loss L(Θ,ω;G) through the gradient∇ΘL(·). • MSeaHKGrl follows the policy gradient-based NAS search algorithm to derive:
∇Θ̄EX∼pΘ̄(X)[L(X,ω;G)] = ∇Θ̄ ∫ pΘ̄(X)L(X,ω;G)dX = ∫ L(X,ω;G)∇Θ̄pΘ̄(X)dX
= ∫ L(X,ω;G)∇Θ̄ log pΘ̄(X) · pΘ̄(X)dX (14)
= ∇Θ̄EX∼pΘ̄(X)[L(X,ω;G)∇Θ̄ log pΘ̄(X)], where ∇Θ̄pΘ̄(X) = log pΘ̄(X)pΘ̄(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 MSeaHKGrl and MSeaHKGdarts. From Tab. 9 and Tab. 10, we observe that MSeaHKG and MSeaHKGrl have
better performance than MSeaHKGdarts 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 a discrete architecture after finishing the search. But the weights αki in Eq. 13 cannot cannot converge to a one-hot vector, which lead to performance collapse after removing |O − 1| 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 MSeaHKGrl 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 MSeaHKG with MSeaHKGrl, MSeaHKG achieves slight improvements. That is mainly because MSeaHKG directly calculates the gradient w.r.t. Θ̄ from the loss L(·), while MSeaHKGrl takes the loss L(·) as a 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.

heading: D.4 MSEAHKG CAN BE TRANSFERRED TO OTHER GRAPH-BASED TASKS.
text: Since many configurations of MSeaHKG are inspired by GNNs and GNN searching methods, we transfer MSeaHKG to other GNN-related tasks to further investigate its capability.
First, we conduct an 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, nodes represent the users and items, edges have two main types: 1) 5 level of ratings {1, 2, 3, 4, 5} between users and items, 2) connections among users. The goal of the task is to predict the unknown ratings of items given by users. After treating the 5 ratings as 5 edge types, the recommendation task is converted to the relation prediction task, i.e., predict the rating r given ?(user, item). To compare MSeaHKG with literature more conveniently, we follow Fan et al. (2019) to utilize the Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) as the evaluation metrics, and 60% as training data. We let MSeaHKG compute top-3 scores like a = score(2(user, item)), b = score(4(user, item)), c = score(5(user, item)), then adopt weighted sum to output the final rating like (a · 2 + b · 4 + c · 5)/(a+ b+ c). The experimental report in Tab. 11a shows MSeaHKG has a 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 a whole graph G(E,R, S) by aggregating the node embeddings as:
hG = rd({ei}ei∈E).
Due to the modeling of edge representations, MSeaHKG slightly adjusts the readout function as:
hG = rd({[e1, r, e2]}r(e1,e2)∈S). 2https://www.cse.msu.edu/˜tangjili/datasetcode/truststudy.htm
Table 11: The model performance of extending MSeaHKG to other tasks.
(a) The comparison on the rating prediction task of social recommendation. The results of baselines are copied from Fan et al. (2019).
model CiaoMAE RMSE PMF 0.9520 1.1967 TrustMF 0.7681 1.0543 NeuMF 0.8251 1.0824 GraphRec 0.7540 1.0093 MSeaHKG 0.7511 1.0021
(b) The comparison on the graph classification task. The results of baselines on PROTEINS and IMDB-M are copied from PAS (Wei et al., 2021), and those on MUTAG are copied from GIN (Xu et al., 2018).
type model PROTEINS IMDB-M MUTAG GNNs GCN 0.7484 0.5040 0.8560 GraphSAGE 0.7375 0.4853 0.8510 GIN 0.7620 0.5230 0.8940
NAS for
GNNs GraphNAS 0.7520 0.4827 - SNAG 0.7233 0.5000 - You et al. (2020) 0.7390 0.4780 - PAS 0.7664 0.5220 - MSeaHKG 0.7724 0.5317 0.8922
We implement the choices of readout function as {global mean, global max, 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 MSeaHKG achieves not bad performance on these data sets.

Review summaries:
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.

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

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.