A Greedy Bit-flip Training Algorithm for Binarized Knowledge Graph Embeddings (2020)

Abstract: This paper presents a simple and effective discrete optimization method for training binarized knowledge graph embedding model B-CP. Unlike the prior work using a SGD-based method and quantization of real-valued vectors, the proposed method directly optimizes binary embedding vectors by a series of bit flipping operations. On the standard knowledge graph completion tasks, the B-CP model trained with the proposed method achieved comparable performance with that trained with SGD as well as state-of-the-art real-valued models with similar embedding dimensions.

## introduction knowledge graph embedding (kge) has a wide range of applications in ai and nlp, such as knowledge acquisition, question answering, and recommender systems. most of the existing kge models represent entities and relations as real or complexvalued vectors thus consuming a large amount of memory @xcite @xcite @xcite @xcite @xcite @xcite @xcite @xcite . to deal with knowledge graphs with more than a million entities, more lightweight models are desirable for faster processing and to reduce memory consumption, as ai applications on mobile devices are becoming more common. @xcite proposed a binarized kge model b-cp, wherein all vector components are binarized, allowing them to be stored compactly with bitwise representation. despite the reduced memory consumption by more than a magnitude, b-cp performed as well as the existing real-valued kge models on benchmark tasks. b-cp is based on the cp decomposition of a knowledge graph @xcite . it is fully expressive @xcite , meaning that any knowledge graph can be represented as a b-cp model. during the training of b-cp, however, realvalued embeddings are maintained and are quantized at each training step @xcite . the loss function is computed with respect to the quantized vectors, but stochastic gradient descent is performed on the real vectors with the help of hinton's "straight-through" estimator (hste) @xcite . thus, training does not benefit significantly from the compact bitwise representations, although score computation is faster by a bitwise technique. dkge @xcite is another binary kge model proposed recently, but it also maintains real-valued vectors during training, as it solves a relaxed optimization problem with continuous variables. in this paper, we propose greedy bit flipping, a new training approach for b-cp in which binary vectors are directly optimized, i.e., without the intervention of real-valued vectors. a bit in binary vectors is sequentially flipped in a greedy manner so that the objective loss is improved. the advantages of greedy bit flipping are: (1) it does not need to maintain real-valued vectors even during training; (2) it is simple and is easy to implement; and ## binarized cp decomposition for knowledge graphs a knowledge graph is a set of triples (e i , e j , r k ), where e i , e j are subject and object entities (represented as nodes in the graph), respectively, and r k is the label of the relation between them (corresponding to labeled arcs in the graph). when a triple is in a knowledge graph it is called a fact. a knowledge graph can be equivalently represented by a third-order boolean tensor @xmath0, 1} n e ×n e ×n r , where n e is the number of entities in the graph, and n r is the number of relation labels; if a triple (e i , e j , r k ) is a fact, x i @xmath1, and 0 otherwise. cp decomposition @xcite is a general technique for decomposing a tensor into a sum of rank-1 tensors. for a third-order tensor x representing a knowledge graph, its approximate cp decomposition is given by x ≈ ∑ d @xmath2, and a d , b @xmath3. in this case, matrices the b-cp decomposition of a knowledge graph @xcite differs from the standard cp, in that x is decomposed in terms of binary vectors a d , b @xmath4, +1} n e , c @xmath5, +1} n r . as with cp, b-cp decomposition can be cast as a problem of binary classification, and solved by logistic regression. first, each x i jk is assumed to be a random variable sampled independently from a probability distribution parameterized by a, b, c: to train factor matrices to match observed/ unobserved facts encoded as x , we minimize the algorithm 2: update(m, n, d, pos, neg) input: @xmath6, +1} n×d : factor matrix to update input: pos: set of positive triples (facts) input: neg: set of negative triples (non-facts) output: m: updated factor matrix 1 c ←random permutation of indices 1, . . . , d 2 foreach @xmath7, . . . , n} do // run in parallel 3 foreach @xmath8, but in random order 4 if ∆(m i j ) < 0 then m i j ← -m i j negative log likelihood of the posterior probability: the proposed training method randomly samples an element (or a bit) of the factor matrices a, b, c of b-cp, and negates its sign if this "bit flipping" reduces the objective loss. this process is repeated until the loss does not improve further or a specified number of iterations is reached. the pseudocode of the algorithm is depicted in algorithms 1 and 2. in algorithm 1, when a factor matrix is updated, the other two factor matrices are fixed. as the number n r of relations is considerably smaller than the number n e of entities in general, the change in the relation matrix c influences the total loss much more significantly than entity matrices a and b. for this reason, we update c prior to a and b in each iteration to promote faster convergence. actual update is carried out in algorithm 2. as remarked on line 2, a row of a factor matrix, which represents a single entity or a relation, can be processed in parallel, because the score of an individ-ual triple depends only on a single subject, object, and relation it contains; for instance, even when all subject embeddings are updated simultaneously, only one of them can change the score of any given triple. this means that, when multiple rows of a factor matrix are updated, the change in the total loss in eq. ( 1 ) is invariant to the order of the updates, as long as the other two factor matrices are fixed. since algorithm 2 updates only one matrix, we see that its rows can be processed in parallel. by contrast, the loss is dependent on the order of updated columns (i.e., bits) within a row, i.e., components in an embedding vector. we thus change the order of updated columns every time algorithm 2 is called, by shuffling the set [d] of dimensions in line 1. in algorithm 2, each bit in a factor matrix is examined to see if it is worth being flipped. for instance, consider a component (bit 1 ), and let a denote the factor matrix a after a i j is flipped to -a i j . the change in the loss is then ## conclusion in this paper, we have introduced greedy bit flipping, a simple yet effective discrete optimization method for training the binarized kge model b-cp. on the standard benchmark datasets of kgc, b-cp models trained by bit flipping were on per with hste-trained b-cp in terms of accuracy. experimental results show that the kgc performance was stable over different initial values. making ensemble of multiple b-cp models is made tractable by the small memory consumption of b-cp, which brought further performance improvement. bit flipping is unique in that it does not require the loss function to be differentiable, making it potentially applicable to a wide range of loss functions. we plan to investigate this direction in our future work. application of bit flipping to other binarized kge models is another interesting direction. a binary version of distmult looks interesting as a starting point, as it is closely related to dkge @xcite , a recently proposed binarized model.