{'fraction_non_alphanumeric': 0.04956938544873544, 'fraction_numerical': 0.01675694633880207, 'mean_word_length': 4.605504587155964, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
AutoSF+: Towards Automatic Scoring Function Design for Knowledge Graph Embedding

Scoring functions, which measure the plausibility of triples, have become the crux of knowledge graph embedding (KGE). Plenty of scoring functions, targeting at capturing different kinds of relations in KGs, have been designed by experts in recent years. However, as relations can exhibit intricate patterns that are hard to infer before training, none of them can consistently perform the best on existing benchmark tasks. AutoSF has shown the significance of using automated machine learning (AutoML) to design KG- dependent scoring functions. In this paper, we propose AutoSF+ as an extension of AutoSF. First, we improve the search algorithm with the evolutionary search, which can better explore the search space. Second, we evaluate AutoSF+ on the recently developed benchmark OGB. Besides, we apply AutoSF+ to the new task, i.e., entity classification, to show that it can improve the task beyond KG completion.


INTRODUCTION
Knowledge Graph (KG) [36,45,51] is a special kind of graph data in which the nodes represent entities and edges are the relations between entities. KG plays vital roles in areas of data mining and machine learning, boosting various downstream applications such as question answering [34,42] and recommendation [30]. Extensive studies have been done on knowledge graph embedding (KGE), which learns a mapping from the symbolic entities and relations to low-dimensional embedding vectors that best preserve the semantical and topological properties in the original KGs [25,51].
One should attach attention to encoding the interactions of entities and relations to obtain high-quality representations of KG. A general method is to define a scoring function (SF) to capture such interactions. The SF measures the plausibility of factual triples with the form of (head entity, relation, tail entity) (or (ℎ, , ) in short), by processing the corresponding embedding vectors , , .
A representative SF is TransE [8], which interprets the relation as a translation from the head entity ℎ to tail entity . Variants of TransE project the entities to a relation-specific hyperplane to deal with relations involving 1-N/N-1/N-N mappings [17,46,54]. These models are categorized as translational distance models (TDMs). For another category, the bilinear models (BLMs) [26,29,33,37,38,49,56,59], their SF can be regarded as using a bilinear product ⊤ ( ) to model the interaction of entities and relations, where ( ) is a square matrix related to relation embedding . Inspired by the predictive performance of deep networks [6], the neural network models (NNMs) have also been explored as scoring functions [12,13,21,44,50].
Concise model architectures make TDMs easy to be comprehended. However, they are shown to be less expressive and less effective [51,53]. NNMs are more powerful but more expensive for training and prone to overfitting due to a large amount of parameters. In comparison, BLMs can express any KG under simple conditions by modeling relation of common properties (e.g., symmetric and anti-symmetric), and have achieved state-of-the-art performance [29]. Even though BLMs tend to be better than TDMs and NNMs for KG learning, there is currently no absolute winner among BLMs. We empirically observe that none of the existing scoring functions consistently perform the best in different datasets, and those better adapted for a certain KG dataset present better performance. Therefore, designing a model with fixed architecture that can adapt to different datasets is not the optimal solution.
Intuitively, one may raise the question: can we design a specific scoring function for a given KG? Usually, the scoring function is custom-designed by human experts in a trial-and-error way, which often requires much time and effort. To make the process of finding optimal SF more affordable and programmable, we need to bridge the gap between model design and the often scarce domain knowledge in KGE. Fortunately, the recently popular technique, automated machine learning (AutoML) comes into our sight.
AutoML has exhibited its great power in many machine learning tasks and applications [24,57]. Inspired by AutoML and especially neural architecture search (NAS) techniques [15,32,62] , we aim to design KG-dependent scoring functions. In this paper, we present an automated design method of scoring function, named AutoSF+. The proposed method can adapt to different KGs and different tasks, reducing human efforts in model design. However, it is not easy to achieve this goal, which requires domain knowledge in both areas of KGE and NAS. The preliminary work AutoSF [60] has designed a special greedy algorithm, enhanced with a filter and predictor to address the domain-specific properties of KGE, to design dataspecific scoring functions. AutoSF is able to search better scoring functions on different datasets, however, the greedy algorithm usually leads to sub-optimal solutions [1,48]. Hence, we improve AutoSF into AutoSF+ with the following three improvements: • First, since the greedy algorithm cannot fully explore the search space and will lead to sub-optimal solutions, we improve it with the evolutionary algorithm, which is also enhanced by the filter and predictor. • Second, we evaluate AutoSF+ on the recently developed benchmarks, i.e., ogbl-biokg and ogbl-wikikg2, which serve as a standard framework for graph learning and have larger scales than current benchmarks.
real part of complex vector ∈ C conjugate of complex vector ∈ C • Finally, we extend the application from KG completion to entity classification. By searching the message function in the GNN framework, we show that AutoSF+ can also improve the entity classification task.
Notations In this paper, vectors are denoted by lowercase boldface, and matrix by uppercase boldface. The commonly used notations are listed in Table 1.

RELATED WORKS 2.1 Knowledge Graph Embedding
A knowledge graph can be seen as a third-order tensor G ∈ R | E |×| R |×| E | . In this section, we consider embedding its entities and relations to a -dimensional space. Let the resultant entity embedding matrix be ∈ R × | E | (with one column for each entity ) and the relation embedding matrix be ∈ R × | R | (with one column for each relation ). The scoring function (ℎ, , ) ∈ R measures plausibility of the triple (ℎ, , ) based on the embeddings of ℎ, , .

Algorithm 1 Training framework of knowledge graph embedding
Require: training triples S , scoring function and loss function . 1 update learnable parameters through backward propagation; 9: until convergence 10: return embeddings and . KGE methods have been extensively studied in recent years. To obtain well-trained embeddings, most KGE models follow the learning procedure as in Algorithm 1. First, we initialize the embeddings of entities and relations in step 1 by Uniform or Xavier method [20]. For each positive triple in the training set, negative triples in step 5 are often sampled from fixed distribution [54] or dynamic schemes [46,61]. Then, the hinge loss [8] and logistic loss [56] can be used as loss function to maximize the score on positive triples and minimize the score on negative triples in step 6.
After that, the embeddings are updated based on stochastic gradient descent [27] in step 8.
The scoring function , which is of central importance in the KGE task, can be examined from the two following aspects.
• Expressiveness. This considers the ability of the scoring function to fit a given KG.
Among all the possible forms of KGs, there are special properties of relations. Common properties include symmetry, antisymmetry, general asymmetry, and inverse. The fully expressive scoring functions can handle all the relation patterns. • Number of parameters. Real-world KGs can be very sparse [45,51].
A scoring function with a large number of trainable parameters may over-fit the training triples.
As mentioned in Section 1, current models mainly fall into three types: TDMs, BLMs and NNMs. It is well-known that many TDMs (such as TransE [8] and TransH [54]) cannot model the symmetric relations well [25,51]. Neural network models, though fully expressive, have large numbers of parameters. This not only prevents the model from generalizing well on unobserved triples in a sparse KG, but also increases the training and inference costs [12,29,50]. In comparison, BLMs (except DistMult) can model all relation patterns and are fully expressive. Besides, these models usually have moderate complexities (with the number of parameters linear in |E |, |R| and ). Therefore, we consider BLM as a better choice, and it will be our focus in this paper.

Neural Architecture Search
The automated machine learning (AutoML) [24,57] has demonstrated its advantages in the design of better machine learning models. There are three important components in AutoML [5,24,57]: (i) Search space: This identifies important properties of the learning models to search. (ii) Search algorithm: A search algorithm is developed to search for good solutions in the designed space. (iii) Evaluation: Since the objective is to improve performance, evaluation is needed to offer feedbacks to the search algorithm.
The recent popularity of neural architecture search (NAS) has enabled the design of deep networks, such as CNN and RNN [15,24,62]. The search algorithms can be classified into two types, i.e. the model-based approach and the sample-based approach. Modelbased approach builds a surrogate model for all candidates in the search space and uses the surrogate model to pick up candidates with promising performance, such as Bayesian algorithm [18], reinforcement learning algorithm [40,62], and gradient-descent algorithm [32,58]. The model-based approaches require evaluating a large number of architectures for training the surrogate model or require differentiable objective w.r.t. architectures. Sample-based approaches heuristically sample in the search space to explore better structures, such as greedy algorithm [31] and evolutionary algorithm [41]. The sample-based approaches are more flexible in selecting architectures and exploring the search space with strategies specific to a certain problem.
As for evaluation methods, parameter-sharing [32,40,58] allows faster architecture evaluation by combining architectures in the whole search space with the same set of parameters [5,32,40]. Despite the appealing speed, the obtained results can be sensitive to initialization, which hinders reproducibility [5]. On the other hand, stand-alone methods [3,31,41,62] train and evaluate the different models separately. They are slower but more reliable. To improve the efficiency of stand-alone methods, a predictor can be trained to select promising architectures [31].

THE PROPOSED SEARCH PROBLEM
Real-world KGs are often large, sparse, incomplete as well as have distinct patterns, and it is unclear how a proper scoring function can be designed for a particular KG. In this section, we first provide a deep insight on current models, and then define "automated scoring function design" as a search problem based on the unified view of bilinear models.

Unifying Existing BLMs
Recall that a BLM may operate in the representation space that can be real, complex or hyper-complex. To present the different BLMs in the same form, we first unify them to the same representation space. The idea is to partition each of the embeddings , , to 4 equal-sized chunks, i.e., The BLM is then written in terms of {⟨ , , ⟩} , , ∈ {1,...,4} . In this way, current BLMs can be simplified and unified as follows.

A Unified Representation of BLMs
Using the above unified form, design of BLM can be simplified to designing ( ) in (1). Hence, we define the unified representation of BLMs in definition 3.1.
the desired scoring function is of the form This covers all the previous BLMs when = 4. A graphical illustration is shown in Figure 2. Let ( , ) outputs a matrix with × blocks, with its ( , )-th block: We define 0 ≡ 0, and sign(0) = 0. The form in (3) can be written more compactly as

Searching for BLMs
As introduced in Section 2.2, AutoML is powerful in designing datadependent machine learning models [15,24,62]. Using the family of unified BLMs in Definition 3.1 as the search space A for structure matrix , the search for a data-specific BLM can be formulated as the following AutoML problem.
Definition 3.2 (AutoSF+). Let ( ; ) be a KG embedding model (where includes the entity embedding matrix and relation embedding matrix , and is the structure matrix) and ( , S) be the performance of on triples S (the higher the better). The AutoSF+ problem is formulated as: * ∈ Arg max ∈A ( * ; ), S val (6) where . . , ± } ∀ , = 1, . . . , } contains all the possible choices of , S tra is the training set, and S val is the validation set.  Figure 2: A graphical illustration of the form of (ℎ, , ).
Similar to the other AutoML problems [16,18,55,62], AutoSF+ can be formulated as a bi-level optimization problem [10]. We first train the model to obtain * (converged model parameters) on the training set S tra by (7), and then search for a better (and consequently a better relation matrix ( , )) based on its performance on the validation set S val in (6). Note that the objectives in (6) and (7) are non-convex, and the search space is large (with (2 +1) 2 candidates. Thus, solving (7) can be expensive and challenging.

THE SEARCH ALGORITHM
In this section, we design efficient algorithms to search for the structure matrix in (2). As in Section 2.2, model-based approaches require a proper surrogate model for the complex search space, or need a differentiable objective w.r.t. architectures on the nondifferentiable ranking metrics. Both of them are impractical. Instead, we focus on the sample-based approaches. In Section 4.1, we introduce the properties specific to AutoSF+, which will then be addressed by the filter and predictor in Section 4.2. Finally, we present an evolutionary algorithm [55] (Section 4.3) that can be easily customized to work with the filter and predictor.

Properties Specific to Structure Matrices
In this part, we introduce two properties that are specific to the search space A, and careful exploitation of these properties would be the key to success. ( , ) are in the first column, will be zero for all head embeddings with 1 = 0. We define degenerate structures that empirically perform bad and should be avoided.

Filter and Predictor
To search efficiently, one needs to (i) ensure that each new is neither degenerate nor equivalent to an already-explored structure; and (ii) the scoring function (ℎ, , ) obtained from the new is likely to have high performance. These can be achieved by designing an efficient filter (Section 4.2.1) and performance predictor (Section 4.2.2).

Filtering Degenerate and Equivalent Structures.
The filtering procedure is shown in Algorithm 2. First, step 2 removes degenerate structure matrices. Next, step 3 generates a set of ( !) 2 2 structures that are equivalent to . is filtered out if any of its equivalent structures appear in the set H containing structure matrices that have already been explored. As is small, this filtering cost is very low compared with the cost of model training in (7).

Fast Evaluation with Predictor.
After collecting structures in H , we construct a predictor P to estimate the goodness of each . Note that search efficiency depends heavily on how to evaluate the candidate models. A highly efficient approach is parameter-sharing, as is popularly used in one-shot NAS [32,40].
Recall from Section 2.1 that it is desirable for the scoring function to be fully expressive. This motivates us to examine how many possible 's can lead to a symmetric or skew-symmetric ( , ). To achieve this goal, we design symmetric-related features (SRF) with ( + 1) dimensions as the input for the predictor. Then, the predictor, a two-layer MLP, uses the SRF as input to predict the true performance. In this way, we can capture the symmetric related properties of different 's and then use the predictor to learn the correlation between SRF and empirical performance.

Evolutionary Algorithm
While the greedy search in AutoSF [60] can be efficient, however, some structures in the search space can never be explored and it will lead to sub-optimal solutions due to the limitation of the greedy algorithm [1,48]. To address this problem, we consider the use of the evolutionary algorithm [2,11].
Algorithm 3 shows the algorithm named AutoSF+. Same as AutoSF+, we start with structures with non-zero elements. It initializes with a set I of non-degenerate and non-equivalent structures in step 1. Then, the main difference with the greedy algorithm in AutoSF [60] is in step 6 to step 11, where the new structures are generated by mutation and crossover. The mutation changes the value of each entry of a given structure to another value in {0, ±1, . . . , ± } with a small probability . As for crossover, given two structures ( ) , ( ) , each entry of the new structure has equal probabilities to be selected from the corresponding entries in either ( ) or ( ) . After mutation and crossover, we check if the newly generated new has to be filtered out. When structures are collected, we use the predictor P in Section 4.2.2 to select topstructures. These are then trained and evaluated for performance. Finally, structures in I with performance worse than the newly evaluated ones are replaced (step 14), i.e. the survive procedure. After repeating for several rounds until the budget is exhausted, the set I, which stores top-evaluated structures and returned.

EXPERIMENTS ON KG COMPLETION
We performed experiments to evaluate the proposed method on the knowledge graph completion (KGC) task. All algorithms are implemented in the pytorch [39] framework on a single RTX 2080Ti GPU (except some on RTX 8000 GPU with OGB dataset).

Algorithm 3 Evolutionary search algorithm (AutoSF+).
Require: , , : number of selected scoring functions by different components; : the nonzero elements of structures in initial set. filter Q, and predictor P. 1: initialization: initialize I as a set of non-degenerate and nonequivalent structures with non-zero elements. 2: train and evaluate all 's in I; 3: add 's to T and record the performance in Y; 4: repeat 5: update predictor P with records in ( T, Y). until | H | = ; 12: select top-structures in H based on the the predictor P; 13: train embeddings and evaluate the performance of each ; 14: survive: update I with if is better than the worst structure in I; 15: add 's in T and record the performance in Y; 16: until budget is exhausted; 17: return I. the full multi-class log-loss [29], which is more robust and has better performance than negative sampling [29,60]. As suggested by [29,49], we use Adagrad [14] as the optimizer. Experiments are performed on five popular benchmark datasets: WN18, FB15k, WN18RR, FB15k237, YAGO3-10 and two newly developed datasets in the open graph benchmark (OGB) including ogbl-biokg and ogbl-wikikg2. Note that the OGB contains realistic and large-scale datasets, among which the ogbl-biokg dataset is relevant to both biomedical and fundamental ML research, while the ogbl-wikikg2 dataset captures the different types of relations between entities in the world. Statistics of these datasets are descriped in Table 2. Performance Measures: The learned scoring functions (ℎ, , ) are evaluated in the context of link prediction. The following two metrics are computed by the ranks that are obtained after filtering all the other observed triples as in [8,54]: (i) Mean reciprocal ranking (MRR): the average of the reciprocal of obtained ranks; and (ii) H@ : ratio of ranks no larger than . The larger the MRR or H@ , the better is the scoring function.

Performance
Comparisons on ogbl-biokg and ogbl-wikikg2 are shown in Table 4 and Table 5, respectively. AutoSF+ achieves state-of-the-art performances on the two OGB datasets: (i) for ogbl-biokg dataset, AutoSF+ out-performs other BLMs or TDMs, improving Test MRR nearly to 1.5% with only half of embedding dimension; (ii) on larger-scale dataset ogbl-wikikg2, AutoSF+ improves Test MRR close to 2.5% with the dimension of 200. These results further demonstrate the importance of searching scoring functions for learning embeddings. The searched scoring functions are shown in Figure 3. As can be seen, they are different from each other and are novel compared with the human-designed BLMs.

Search Algorithm Comparison
In this experiment, we compared AutoSF+ with AutoSF [60] and the following search algorithms on the WN18RR and FB15k237 datasets.
(i) Random, which samples each element of independently and uniformly from {0, ±1, . . . , ± }; (ii) Bayes, which selects each element of from {0, ±1, . . . , ± } by performing hyperparameter optimization using the Tree Parzen estimator [7] and Gaussian mixture model (GMM); (iii) Reinforce, which generates the 2 elements in by using a LSTM [22] recurrently as in NAS-Net [62]; (iv) Greedy, AutoSF without filter and predictor; (v) Evolutionary, AutoSF+ (Alg.3) without filter and predictor. Figure 4 shows the mean validation MRR of the top = 8 structures w.r.t. clock time. First, the Bayes and Reinforce algorithms do not show many advantages over the random search since their surrogate model cannot well address the properties in our search space. Second, Greedy and Evolutionary, even without filter and predictor, outperform the other search algorithms, showing the importance of gradually adjusting scoring functions during searching. AutoSF and AutoSF+ clearly outperform the others with the filter and predictor to deal with the domain-specific properties. Comparing with AutoSF, AutoSF+ is better since the evolutionary algorithm can explore the search space more flexibly.

EXTENSION TO ENTITY CLASSIFICATION
Entity classification aims at predicting the labels of the unlabeled entities. Since the labeled entities are few, a common approach is to use graph neural networks [19,28] to aggregate the neighborhood information. Given the knowledge graph, representative works, including the R-GCN [44] and CompGCN [50], aggregate representations of all the entities layer-by-layer as: Here, ( ℓ , ℓ ) is a composition function that can significantly impact the performance [50] and S tra contains all the training triples. R-GCN uses the composition operator in RESCAL [38], and defines ( ℓ , ℓ ) = ℓ ( ) ℓ , where ( ) is the relation specific weighting matrix in the ℓ-th layer. CompGCN, following TransE [8], DistMult [56] and HolE [37], defines three operators: subtraction where · is the element-wise product, and circular-correlation ( ℓ , ℓ ) = ℓ ( ℓ ★ ℓ ), where ★ = =1 + −1 mod . As mentioned in [50], the choice of composition function is important in learning embeddings. In this task, we use the following bilinear mapping for : ( ℓ , ℓ ) = ( , ℓ ) ℓ , to see whether the form of can benefit representations learning on the entire graph. The structure of is also searched under Definition 3.2, with 5-fold classification accuracy as performance measure.

Setup
Three datasets are used (Table 6): AIFB, which is an affiliation graph; MUTAG, which is a bioinformatics graph; and BGS, which is a geological graph. More details can be found in [43]. In these datasets, only a few entities have labels, and all the entities do not have attributes. Thus for the GCN-based methods, we use the entity's trainable embedding as input. The following four models are compared: (i) GCN [28] without leveraging the relations of edges, i.e. ( ℓ , ℓ ) = ℓ ℓ ; (ii) R-GCN [44] with ( ℓ , ℓ ) = ℓ ( ) ℓ , with ℓ ( ) ∈ R × ; (iii) CompGCN [50] with ( (ℓ) , ℓ ) = ℓ (-/*/★) ℓ , in which the operator is chosen based on 5-fold cross-validation accuracy; and (iv) AutoSF+ which uses the searched structure to form the message function ( ℓ , ℓ ) = ( , ℓ ) ℓ in GCN. The setting of the search algorithms' hyper-parameters is the same as in Section 5.1. As for the learning hyper-parameters, we search the embedding dimension from {12, 20, 32, 48}, learning rate from [10 −5 , 10 −1 ] with Adam as the optimizer [27]. For the GCN, the hidden layer size is the same as the embedding dimension, the dropout rate 1 for GCN's input layer is from [0, 0.5], the dropout rate 2 for the intermediate layers is from [0, 0.5]. We search for 50 hyper-parameter settings for each dataset. Since there is no validation data, we use 5-fold cross-validation to measure the accuracy of training data and use the cross-validation accuracy to select the hyper-parameters in AutoSF+.
6.1.1 Results. We run and evaluate each model 5 times and report the accuracy and standard deviation in Table 7. With different composition operators, R-GCN and CompGCN perform differently in the three datasets. R-GCN is slightly better than CompGCN in AIFB but is worse in the other two sparser datasets. By searching the composition operators, AutoSF+ wins over the baseline methods with more proper messaging functions for a certain dataset.

CONCLUSION
In this paper, we propose AutoSF+, an algorithm to automatically design scoring functions for knowledge graph embedding. As an extension of AutoSF, we use an evolutionary algorithm to search in such a space for more flexible exploration. Results on the five common datasets, the two newly developed OGB datasets, and the entity classification task show that the searched scoring functions outperform existing hand-designed ones. And the proposed evolutionary algorithm is more efficient than greedy search in AutoSF.