Year: 2021

Abstract:
In several domains such as natural language processing, it has been empirically reported that simple addition and subtraction in a somehow learned embedding space capture analogical relations. However, there is no guarantee that such relation holds for a new embedding space acquired by some training strategies. To tackle this issue, we propose to explicitly model analogical structure with an Abelian group. We construct an Abelian group network using invertible neural networks and show its universal approximation property. In experiments, our model successfully learns to capture word analogies from word2vec representations and shows better performance than other learning-based strategies. As a byproduct of modeling Abelian group operations, we furthermore obtain its natural extension to permutation invariant models with theoretical size-generalization capability.

heading: 1 INTRODUCTION
text: The vector representations of words called word2vec (Mikolov et al., 2013a;b) trained only on large unlabeled text data are known to capture linear regularities between words. For example, vec(“king”)−vec(“man”)+vec(“woman”) results in the most similar vector to vec(“queen”). Similar results have been observed not only in other word embeddings (Mnih & Kavukcuoglu, 2013; Pennington et al., 2014) but also in various embedding spaces, such as combined embeddings of text and image (Kiros et al., 2014), emoji embeddings (Eisner et al., 2016), latent representation of deep convolutional generative adversarial networks (Radford et al., 2016), and feature space of pretrained image models (Upchurch et al., 2017).
Although the reports are interesting and attractive, such approaches have shortcomings. Since those methods of learning from unlabelled data usually do not explicitly incorporate learning analogical structure, there is no guarantee that the acquired embedding space has linear relations between instance pairs even if training itself works well. Even when an embedding space captures some kinds of analogies, it might not work for other kinds of analogies. Indeed, word2vec representation works well for inflectional analogies (68.22% accuracy) but poorly for encyclopedic analogies (7.11% accuracy) in our preliminary experiments (see Table 3 in Section 4.2). In such a case, it is quite difficult to tune the training algorithm for certain kinds of analogies you want to use.
To alleviate these issues, we propose to directly learn analogical relations on the embedding space from labeled data. One challenge in learning analogy in a supervised manner is how to model analogical functions. A naive way to do this is to train two separate models corresponding to addition and subtraction, respectively; however, it does not reflect the analogical structure and might be inefficient. In this work, we propose an Abelian group network to incorporate an analogical inductive bias into a neural network. The proposed network is designed to satisfy the Abelian group condition by using an invertible neural network. We also show that the Abelian group network is a universal approximator of smooth Abelian group operations. Since the inverse element in the Abelian group network and its gradient are analytically computable, we can train it for analogy tasks by common techniques for deep learning, such as stochastic gradient descent.
As a side effect of the algebraic structure, we can construct a permutation invariant function, i.e., a function for multisets, by repeatedly composing an Abelian group operation for multiple inputs. Multiset models can handle inputs of different sizes, and it is important for the models to automatically generalize between different size inputs, especially from small to large ones. However, existing multiset models (Zaheer et al., 2017; Qi et al., 2017) have no such theoretical guarantee. On
the other hand, our multiset models naturally induce the size-generalization capability because the output for larger inputs can be written as the composition of small elements. Further, we show that a necessary and sufficient condition for the composed function being permutation invariant is that the binary operation forms an Abelian semigroup, and we propose an Abelian semigroup network, by using the characterization of associative symmetric polynomials.

heading: 2 PRELIMINARIES

heading: 2.1 DEFINITIONS
text: In this section, let us introduce some basic notations and important definitions that will play a key role in this work.

heading: 2.1.1 BASIC NOTATIONS
text: By N, we represent the set of the natural numbers including 0. We denote a vector by a bold symbol, e.g., x. Let x ∈ Rd be a d-dimensional vector. We represent the i-th element (1 ≤ i ≤ d) of x by xi. For 1 ≤ k ≤ d, x≤k ∈ Rk is the k-dimensional vector (x1, . . . xk) and x<k ∈ Rk−1 is the (k − 1)-dimensional vector (x1, . . . xk−1). We denote the elementwise product of two vectors x,y ∈ Rd by x ⊗ y, such that (x ⊗ y)i = xiyi and the elementwise division of two vectors x ∈ Rd,y ∈ (R \ {0})d by x y, such that (x y)i = xi/yi. By ‖ · ‖, we represent the L2 (Euclidean) norm.

heading: 2.1.2 MULTISET AND PERMUTATION INVARIANCE
text: Here, we use X and Y to describe some domains, which are typically Euclidean spaces, i.e., X = Rd1 and Y = Rd2 . We denote the set of multisets over X by NX . We use {x1, . . .xn} ∈ NX to describe a multiset composed of x1, . . . ,xn ∈ X (any confusion with sets is not problematic in this paper). The cardinality of a multiset is the number of elements with multiplicity and is expressed by | · |, e.g., |{1, 2, 2, 3}| = 4. For n ∈ N, a symmetric group Sn is the set of all n! bijective functions σ : {1, 2, . . . , n} → {1, 2, . . . , n}. For a permutation σ ∈ Sn andX ∈ X , σ ·X is defined such that (σ ·X)i = Xσ(i) for all i ∈ {1, . . . , n}. A function f : Xn → Y is said to be permutation invariant if for any X ∈ Xn and for any permutation σ ∈ Sn, f(σ ·X) = f(X) holds. This concept can be extended to functions that take vectors of different dimensions. Namely, a function f : ⋃ k∈N X k → Y is called permutation invariant if for any k ∈ N, for anyX ∈ X k and for any permutation σ ∈ Sk, f(σ ·X) = f(X) holds. When f : ⋃ k∈N X k → Y is permutation invariant, it can be also viewed as a function that takes multisets as input. For notation simplicity, we sometimes use the same symbol to express the multiset function: f : NX → Y .

heading: 2.1.3 UNIVERSALITY
text: Universality is an important theoretical property of neural networks’ expressive power. Let X and Y be an input domain and an output domain, respectively. We consider a modelM and a class of target functions F , both of which are sets of functions X → Y . The modelM is a sup-universal approximator of F if for any target function f∗ ∈ F , for any > 0, and for any compact subset K ⊂ X , there exists a function f ∈M such that
sup x∈K ‖f(x)− f∗(x)‖ < . (1)
If not noted otherwise, universality refers to the sup-universal property.

heading: 2.1.4 BASIC ALGEBRA
text: Here, we introduce the basic definition of important algebraic structures in this study. Let G be a set and ◦ : G × G → G be a binary operation. Below, we review four properties to define Abelian semigroups and groups.
Associativity For any x, y, z ∈ G, (x ◦ y) ◦ z = x ◦ (y ◦ z).
Identity Element There exists an element e ∈ G, called the identity element, such that for any x ∈ G, x ◦ e = e ◦ x = x.
Inverse Element For any x ∈ G, there exists an element x−1 ∈ G, called the inverse element of x, such that x ◦ x−1 = x−1 ◦ x = e.
Commutativity For any x, y ∈ G, x ◦ y = y ◦ x.
Table 1 shows which properties are required in each algebraic structure. A semigroup only requires associativity to the binary operation. A group is a semigroup with an identity element and inverse elements. An Abelian (semi)group is a (semi)group with commutativity.

heading: 2.2 INVERTIBLE NEURAL NETWORKS
text: Invertible neural networks are neural networks that approximate invertible functions Rd → Rd. Here, we review some existing studies for multi-dimensional case, i.e., d ≥ 2, and singledimensional case, i.e., d = 1.

heading: 2.2.1 NORMALIZING FLOWS
text: Multi-dimensional invertible neural networks have been studied mainly in the context of normalizing flows (Tabak & Vanden-Eijnden, 2010), which iteratively apply invertible functions to a simple original probability distribution to express complex probability distributions (Kobyzev et al., 2020; Papamakarios et al., 2019). There have been many variants proposed including residual flows (Behrmann et al., 2019), neural ODEs (Chen et al., 2018), and autoregressive flows (Kingma et al., 2017). Here we review affine coupling flows (Dinh et al., 2015), one of the most popular models with parallelizable efficient inverse computation. Each layer of the affine coupling flows maps x = (x1, . . . , xd) ∈ Rd to y = (y1, . . . , yd) ∈ Rd such that{
y≤k = x≤k, y>k = x>k ⊗ exp(α(x≤k)) + β(x≤k), (2)
where exp is applied elementwise and α, β : Rk → Rd−k are trainable functions. The inverse is computed as follows: {
x≤k = y≤k, x>k = (y>k − β(y≤k))⊗ exp(−α(y≤k)). (3)
They are used in many successful applications such as NICE (Dinh et al., 2015), Real NVP (Dinh et al., 2017), and Glow (Kingma & Dhariwal, 2018).
Although the normalizing flows have a limited form of transform, they still admit universalities on certain classes of functions (Teshima et al., 2020). The affine coupling flows are Lp-universal (weaker condition of universality) for C2-diffeomorphisms. Some more complex models, including deep sigmoidal flows (Huang et al., 2018) and sum-of-squares polynomial flows (Jaini et al., 2019), are universal for C2-diffeomorphisms.

heading: 2.2.2 SINGLE-DIMENSIONAL INVERTIBLE NEURAL NETWORKS
text: For single-dimensional functions, invertibility is equivalent to strict monotonicity. Monotonic networks (Sill, 1997) model strictly monotonic functions. The monotonically increasing version with
K groups and Jk units for k-th group is as follows:
f(x) = min 1≤k≤K max 1≤j≤Jk
exp(w̃(k,j)) · x+ b(k,j), (4)
where w̃(k,j), b(k,j) ∈ R are trainable parameters. The monotonic networks are a universal approximator for strictly monotonic differentiable functions. Monotonic rational-quadratic transforms (Durkan et al., 2019) are another universal model for the single-dimensional case.

heading: 3 PROPOSED METHODS
text: Here, we introduce the proposed methods. First, we propose a model for Abelian group operations and show its universality. Next, we explain how to model analogical relations by our model. Finally, we present architectures for multiset input and show the size-generalization ability.

heading: 3.1 ABELIAN GROUP NETWORK
text: Let X be a Euclidean space, i.e., X = Rd (d ∈ N). We present the Abelian group network that models Abelian group operations as follows:
x ◦ y = φ−1(φ(x) + φ(y)), (5)
where φ : X → X is a trainable invertible function, typically modeled by an invertible neural network.
First, we check that this binary operation satisfies the four conditions of the Abelian group described in Section 2.1.4.
Proposition 1 (Semigroup Conservation). Let ρ : X → X be a bijective function. When ∗ : X × X → X is associative, x ◦ y = ρ−1(ρ(x) ∗ ρ(y)) is also associative. Similarly, when ∗ is commutative, ◦ is also commutative.
Proof. Associativity:
(x ◦ y) ◦ z = ρ−1(ρ(ρ−1(ρ(x) ∗ ρ(y))) ∗ ρ(z)) = ρ−1((ρ(x) ∗ ρ(y)) ∗ ρ(z)) = ρ−1(ρ(x) ∗ (ρ(y) ∗ ρ(z))) (∵ Associativity of ∗) = ρ−1(ρ(x) ∗ ρ(ρ−1(ρ(y) ∗ ρ(z)))) = x ◦ (y ◦ z).
(6)
Commutativity:
y ◦ x = ρ−1(ρ(y) ∗ ρ(x)) = ρ−1(ρ(x) ∗ ρ(y)) (∵ Commutativity of ∗) = x ◦ y.
(7)
By this proposition, since + is associative and commutative, the Abelian group network is also associative and commutative. The identity element is
e = φ−1(0), (8)
which satisfies
x ◦ e = x ◦ (φ−1(0)) = φ−1(φ(x) + 0) = x
(9)
for all x ∈ X . The inverse element of x ∈ X is
x−1 = φ−1(−φ(x)), (10)
which satisfies x ◦ x−1 = x ◦ (φ−1(−φ(x)))
= φ−1(φ(x)− φ(x)) = φ−1(0) = e.
(11)
It is worth noting that we can analytically compute the inverse function (Equation 10).
Next, we check the expressive power of the Abelian group network. An Abelian Lie group is an Abelian group over a manifold in which the group operation (x, y) 7→ x ◦ y and the inverse function x 7→ x−1 are both differentiable. The following theorem states that the Abelian group network can approximate any Abelian Lie group operation with arbitrary precision. Theorem 1 (Universality of Abelian group networks). Let X be a Euclidean space. Abelian group networks are a universal approximator of Abelian Lie group operations over X . In other words, for any Abelian Lie group operation ∗ : X × X → X , for any > 0, and for any compact subset K ⊂ X , there exists a binary operation function ◦ : X × X → X represented by an Abelian group network such that
sup x∈K,y∈K
‖(x ∗ y)− (x ◦ y)‖ < . (12)
We provide the proof in Appendix C.1. It is based on the theory of the Abelian Lie group and the universality of invertible neural networks.

heading: 3.2 MODELING ANALOGY BY ABELIAN GROUP NETWORK
text: Now we consider an analogical task of predicting an element d in a relation a : b = c : d. Let a, b, c,d ∈ X be embedded vectors of corresponding elements. We need to define a model f : X × X × X → X that predicts d from a, b, and c. Then, if the set of candidate elements are finite as in word embedding, we can search the nearest vector to f(a, b, c). We explained in Section 1 that several studies heuristically use f(a, b, c) = b− a+ c. Analogical relations have two natural laws: when a = b, then c = d holds; a : b = c : d is equivalent to a : c = b : d. when a = c, then b = d holds. Therefore, we would like to design f to satisfy the two condition that f(a, b, c) = c when a = b, and f(a, b, c) = f(a, c, b). These conditions hold in f(a, b, c) = b − a + c. However, when we try to parametrize f by neural networks, it is not trivial to reflect these inductive biases using existing architectures. By using the Abelian group network, we can model f so that it reflects the conditions as follows:
f(a, b, c) = b ◦ a−1 ◦ c = φ−1(φ(b) + φ(φ−1(−φ(a)))) ◦ c. = φ−1(φ(b)− φ(a)) ◦ c. = φ−1(φ(b)− φ(a) + φ(c)).
(13)
Also, this is strictly more expressive than the simple arithmetic operations because when φ is the identity, φ(a, b, c) = b − a + c. We can train this model by minimizing the loss: l(f(a, b, c),d), where l : X → R can typically be an L2 loss or negative cosine similarity.

heading: 3.3 MULTISET ARCHITECTURE AND SIZE GENERALIZATION
text: Here, we construct a multiset architecture by combining the Abelian group networks and show it naturally generalizes in sizes. It is easy to check that if ◦ : X × X → X is associative and commutative, f : X k → X defined by
f(x1, . . . ,xk) = x1 ◦ x2 ◦ · · · ◦ xk (14) is permutation invariant. When this condition holds, we represent the multiset version of f : NX → X as follows by denoting a composition of ◦ by©: f(X) =©x∈X x,whereX ∈ NX is a multiset of X . By modeling ◦ by the Abelian group network, we can construct a multiset architecture of the Abelian group network:
f(X) = φ−1 (∑ x∈X φ(x) ) , (15)
where the invertible function φ : X → X is typically modeled by an invertible neural network. Now, we consider the size-generalization ability of the multiset architectures. An intuitive explanation is as follows. As an extreme case, even if trained only on multisets of two elements, our models can learn the correct binary operation. Therefore, they generalize to multisets of larger sizes. In general, we can derive the following theorem. Appendix C.2 provides the proof. Theorem 2 (Size Generalization of Abelian Group Networks). Let f∗ : NX → X be a target function expressed by a composition of Abelian semigroup (X , ◦): f∗(X) = ©
x∈X x. Let f : NX → X be a multiset architecture of the Abelian group network: f(X) = φ−1 (∑ x∈X φ(x) ) . When
‖f(X)− f∗(X)‖ < (16) holds for anyX (∈ NX ) whose size is smaller than a (≥ 2), then
‖f(X)− f∗(X)‖ < ( (aK1K2) dloga be − 1 )
aK1K2 − 1 (17)
holds for anyX (∈ NX ) whose size is b (≥ a), under the condition that the Lipschitz constants of φ and φ−1 are K1 and K2, respectively.
A necessary and sufficient condition of f in Equation 14 being permutation invariant is that ◦ is an Abelian semigroup operation. In Appendix A, we provide the proof and propose an Abelian semigroup network by using the characterization of associative symmetric polynomials.

heading: 4 EXPERIMENTS
text: Here, we summarize the main experiment of learning word analogies. In addition to this section, we provide the experiments of size generalization on learning multiset functions in Appendix B.

heading: 4.1 COMMON SETTINGS
text: We implemented the neural networks in the PyTorch framework (Paszke et al., 2019) and optimized them using the Adam algorithm (Kingma & Ba, 2015). The hyperparameters for each model in each problem were tuned with validation datasets using the Bayesian optimization of the Optuna framework (Akiba et al., 2019). The experiments were run on Intel Xeon E5-2695 v4 with NVIDIA Tesla P100 GPU. See Appendix D for the detailed settings, such as the model architecture and the range of hyperparameters.

heading: 4.2 WORD ANALOGIES
text: In Section 1, We discussed the general motivation of training analogical functions over an embedding space. In addition, here, we explain the specific issue in word2vec (Mikolov et al., 2013a;b) and justify the motivation of using the Abelian group network. In word2vec, for predicting a word d in a relation a : b = c : d, the word with the most similar vector to b − a + c (we denote the corresponding vector for each word by using a bold symbol) is selected in terms of the cosine similarity:
cos(v1,v2) = v1 · v2 ‖v1‖‖v2‖ . (18)
Usually, the words a, b, c are excluded from the candidate vocabulary under the assumption that a common word does not appear in one analogy example. Although this assumption is reasonable in many cases, it prevents us from solving certain problems such as a past tense verb analogy “do”:“did” = “split”:“split” or a plural noun analogy “apple”:“apples” = “deer”:“deer”. On the other hand, if we do not exclude the words a, b, c from the candidates, word2vec suffers from severe performance degradation e.g., falling from 73.59% to 20.64% in our preliminary experiment on the Google analogy test set. This is due to the nature of the word2vec algorithm: the result of the simple arithmetic calculation b−a+ c has a high probability of being close to b or c in the cosine similarity, especially in a high dimensional space. We mitigate this issue by learning richer functions than addition and subtraction. In this experiment, we trained the Abelian group network from a labeled dataset and compared it with the original word2vec and other learning-based approaches.
Word Embedding We used a 300-dimensional word2vec model for 3 billion words trained on Google News corpus of about 100 billion words1. We normalized each word embedding by L2
norm, following the implementation of the Gensim framework (Řehůřek & Sojka, 2010).
Word Analogy Models We compared different models for a word analogy function f : R300 × R300×R300 → R300 that takes the vectors of words a, b, c and predicts the vector of a word d. In the proposed method (WV + AGN), we modeled f by Equation 13. For the invertible neural network φ : R300 → R300, we implemented a model based on the affine coupling flows described in Section 2.2.1. In addition to the original word2vec (WV): f(a, b, c) = b−a+c, we prepared two trainable baselines based on a multilayer perceptron (WV + MLP and WV + MLP C, respectively):
f(a, b, c) = MLP(b− a+ c), (19) f(a, b, c) = MLPC(CONCAT(a, b, c)), (20)
where we trained MLP : R300 → R300 or MLPC : R900 → R300.
Setup Except for WV, we trained f by minimizing the loss function: lossf (a, b, c,d) = − cos(f(a, b, c),d) on the training set. We measured the accuracy on the test set by calculating the most similar vector to the model output for each word:
argmax d∈V cos(f(a, b, c),d), (21)
where V is the set of all word embeddings in the word2vec model. For reference, we also tested the setting where we removed the words a, b, c from the candidates:
argmax d∈V\{a,b,c} cos(f(a, b, c),d). (22)
Datasets We trained our models on the bigger analogy test set (Rogers et al., 2016), which consists of 4 categories, each of which has 10 smaller subcategories of 50 unique relations. First, we extracted the pairs included in the word2vec vocabularies. Then for each subcategory, randomly split them into a training set (60%), validation set (20%), and test set (20%). Finally, for each set, we generated all the combinations of the pairs for each subcategory and concatenated them among all subcategories. For some relations that contain multiple acceptable candidates, such as mammal and canine for hypernyms of dog, we used the first candidate for training and accepted any for the test. To check the transferability to another dataset, we also tested our models by the Google analogy test set (Mikolov et al., 2013a). It includes 19,544 question pairs (8,869 semantic and 10,675 syntactic), and all the words were included in the word2vec vocabulary. Tables 9 and 10 in Appendix D.2 summarize the explanation and the number of extracted pairs for all subcategories.
Results In Table 2, we summarized the results on the bigger analogy test set when we selected from the whole vocabulary. In this setting, WV performed extremely poorly. WV + AGN achieved the best accuracy in overall, while the three trainable models all outperformed WV. Table 3 shows the accuracy comparison when we excluded a, b, c from the candidates. While the proposed method outperformed WV again, interestingly, the other learning-based models degraded their performance compared to the original WV.
We summarized the results on the Google analogy test set in Tables 4 and 5 for each test setting. Here, MLP-based models significantly dropped performance while the proposed model did not.
1https://code.google.com/archive/p/word2vec/
Only in the setting where we excluded a, b, c from the candidates in the Google analogy test set, the proposed method did not outperform WV. This is possibly because the word2vec model was highly tuned for the Google analogy test set for this evaluation method. Indeed, it has been pointed out that word embedding algorithms are quite dependent on system design choices and hyperparameter tuning Levy et al. (2015). We show the full results of all subcategories on each dataset in each evaluation setting in Tables 11, 12, 13, and 14 in Appendix D.2.
Finally, we enumerated the answers of each model for some toy example relations in Table 6. The first four relations are the cases where a = b or a = c. Thanks to the inductive bias incorporated in the Abelian group network, WV + AGN answered all the questions correctly as well as WV. WV + AGN also predicted the correct words for the last five relations, where we need to predict the words that appeared as c. On the other hand, the MLP-based models failed in most cases, which indicates that they are not good at the type of examples different from the training dataset.
Overall, while the naive learning approach overfitted to the certain dataset and evaluation criteria, the inductive biases incorporated in the Abelian group network successfully prevented the model from overfitting.

heading: 5 RELATED WORK

heading: 5.1 ALGEBRAIC STRUCTURES IN NEURAL NETWORKS
text: In the literature of deep learning, algebraic structures mainly appear in the context of group invariant/equivariant neural networks. For image input, some studies tried to incorporate reflection and rotation invariance into convolutional neural networks (Cohen & Welling, 2016; Worrall et al., 2017). Neural networks for (multi)sets (Zaheer et al., 2017; Qi et al., 2017) adopted invariance/equivariance to symmetric group actions. Recent studies have investigated symmetries invariant/equivariant to more general group actions, such as a subgroup of the symmetric group (Maron et al., 2019b) and sets of symmetric elements (Maron et al., 2020).
Our work differs from the above studies since we try to model an Abelian group/semigroup operation itself.

heading: 5.2 INDUCTIVE BIAS AND EXPRESSIVE POWER OF NEURAL NETWORKS
text: Inductive biases are assumptions on the nature of the data-generating process or the space of solutions in machine learning (Battaglia et al., 2018). Many studies have constructed special neural networks that reflect the inductive biases of a given problem setting. At the same time, since those networks are often composed of limited forms of neural operations, expressive power including universal approximation properties has been studied.
Convolutional layers of convolutional neural networks (CNN) (LeCun et al., 1989) are designed to reflect spacial structures in images. CNN without fully connected layers has been shown to be universal (Zhou, 2018). Invertible neural networks incorporate the inductive bias of being bijective, which we summarized in Section 2.2. Message passing graph neural networks (Gilmer et al., 2017) such as graph convolutional networks (Kipf & Welling, 2017) and graph attention networks (Vaswani et al., 2017) are designed under the assumption that neighboring nodes have similar properties. They have been shown to have limited expressive power in terms of graph isomorphism (Xu et al., 2019; Morris et al., 2019) More expressive models have also been studied (Sato et al., 2019; Maron et al., 2019a; Keriven & Peyré, 2019; Maehara & Hoang, 2019). For a (multi)set learning problem, DeepSets (Zaheer et al., 2017) are one of the most popular models with universal approximation property.

heading: 5.3 SIZE GENERALIZATION
text: Graph neural networks and neural networks for (multi)sets can handle graphs and sets of different sizes, and their size-generalization ability has been empirically shown in some applications such as physical systems (Battaglia et al., 2016) and combinatorial optimization (Khalil et al., 2017; Abe et al., 2019; Veličković et al., 2020). However, from a theoretical perspective, there exist simple tasks on which graph neural networks do not naturally generalize to larger graphs (Yehudai et al., 2020). Recent work has analyzed the extrapolation of graph neural networks trained by gradient descent (Xu et al., 2021). There have been few studies on size generalization of (multi)sets probably because of difficulty in analyzing DeepSets for inputs of different sizes.

heading: 6 CONCLUSION AND FUTURE WORK
text: In this work, we presented a novel neural network architecture to model an Abelian group with universality. In the experiment of learning word analogies, we confirmed that the inductive bias of our model that reflects analogical structure successfully enhanced the performance. This brings up the possibility of solving other analogical tasks such as image generation by image analogies (Hertzmann et al., 2001), which is left as future work. Moreover, as an application other than analogies, we constructed a permutation invariant architecture (i.e., multiset model) by combining the Abelian group models, which has the theoretical capability of size generalization. We hope that our attempt to model algebraic structure by neural networks gives a new insight into the field of machine learning.

heading: A ABELIAN SEMIGROUP NETWORK
text: A.1 MOTIVATION
Below, we present a necessary and sufficient condition for multiset functions that are represented by the composition of binary operations to be well-defined. Proposition 2 (Permutation Invariant Conditions for Binary Operation). Let f : ⋃ k∈N X k → X be a function represented as f(X) = x1 ◦ · · · ◦ xn, (23) where X = (x1, . . . ,xn) ∈ Xn and ◦ : X × X → X is a binary operation (left-associative). The function f is invariant if and only if ◦ forms an Abelian semigroup, namely, ◦ is commutative and associative.
Proof. It is obvious that when ◦ is commutative and associative, f is permutation invariant. Let us consider the case when f is permutation invariant. f((x1,x2)) = f((x2,x1)) leads to x1 ◦ x2 = x2 ◦ x1 (commutativity). From f((x1,x2,x3)) = f((x2,x3,x1)), we have (x1 ◦ x2) ◦ x3 = (x2 ◦ x3) ◦ x1 and commutativity leads to (x1 ◦ x2) ◦ x3 = x1 ◦ (x2 ◦ x3) (associativity).
On the basis of this proposition, our goal decomposes into learning Abelian semigroup operations over X . In Section A.2, we propose neural network architectures for Abelian semigroups.
A.2 ARCHITECTURE
Although the Abelian group network proposed in Section 3.1 is universal for smooth group operations, it is not sufficient for approximating an Abelian semigroup operation such as the product over R, i.e., x ◦ y = xy. Now we extend the Abelian group network and propose the Abelian semigroup network. Our idea is to extend + of Equation 5 to a polynomial. From Proposition 1, Equation 5 is still a semigroup after we replace + by a polynomial of x and y as long as the polynomial is associative and symmetric as a binary operation. We call the polynomials with this property associative symmetric polynomials, which are characterized by the following theorem. Since the original paper only gives a brief explanation, we give detailed proof in Appendix C.3. Theorem 3 (Characterization of Associative Symmetric Polynomials, Commutative Case of (Yoshida, 1963)). An associative symmetric polynomial of x and y is one of the following three forms:
x ∗ y =  α α+ x+ y β(β−1)
γ + β(x+ y) + γxy (γ 6= 0), (24)
where α, β, γ are coefficients.
By applying this theorem to Proposition 1 for X with elementwise product and division, we obtain the following three kinds of Abelian semigroup operations:
x ◦ y =  ρ−1(α) (25) ρ−1 (ρ(x) + ρ(y) +α) (26)
ρ−1(β ⊗ (β − 1) γ + β ⊗ (ρ(x) + ρ(y)) + γ ⊗ ρ(x)⊗ ρ(y)), (27) where ρ : X → X is an invertible function and α,β,γ ∈ X are parameters (γ is nonzero for all elements in Equation 27). Equation 25 is a constant case, on which we do not put a focus due to its trivialness. Equation 26 forms a group where e = ρ−1(−α), x−1 = ρ−1(−ρ(x) − 2α). It can be expressed by the Abelian group network with φ(x) = ρ(x) + α and φ−1(x) = ρ−1(x − α) in Equation 5. Equation 27 is a semigroup but not a group. Just using this equation is fine, but we propose a simpler form, as the Abelian semigroup network:
x ◦ y = φ−1(φ(x)⊗ φ(y)), (28) where φ : X → X is a trainable invertible function typically modeled by an invertible neural network. This is a special case of Equation 27 when β = 0,γ = 1 and therefore is a semigroup. Conversely, the Abelian semigroup network can express Equation 27 by
φ(x) = γ ⊗ ρ(x) + β, φ−1(x) = ρ−1((x− β) γ). (29)
Moreover, the Abelian semigroup network can approximate the Abelian group network: φ′−1(φ′(x) + φ′(y)). Let X>0 = Rd>0, where X = Rd. One construction is approximating a bijective function π : X → X>0,
π(x) = exp(φ′(x)), π−1(x) = φ′−1(log(x)) (30)
by φ, where exp and log act elementwise. This is possible in any compact subset of X . From the previous discussions so far, the Abelian semigroup network can approximate any binary operation which is homeomorphic to an associative symmetric polynomial. We confirm this fact in the experiments.
By calculating Equation 14, we can write the model for multiset input X = {x1, . . .xn} ∈ X in a simple form:
f(X) = φ−1(φ(x1)⊗ · · · ⊗ φ(xn)), (31)
where the invertible function φ : X → X is typically modeled by an invertible neural network. For the Abelian semigroup network, the error bound for small multiset propagates in the form of the product with the values φ(xi), which prevents us from inducing the bound like Theorem 2. However, it still has the size-generalization ability in most real applications where the values are not too large. We confirm this by an experiment in Section B.

heading: B EXPERIMENTS OF SIZE GENERALIZATION
text: To check the size generalization over semigroup and group operations on multisets, we trained the models on synthetic data. The binary operation forms of the examined functions are x ◦ y = x+ y, x+ y + 1, 3 √ x3 + y3 (group cases) and x ◦ y = xy, x+ y + xy2 (semigroup cases).
Setup For the single-dimensional invertible neural network of the Abelian group network and Abelian semigroup network, we used monotonic networks (Sill, 1997). We tuned the hyperparameters, the number of groups and the number of units for each group. As a baseline, we used DeepSets (Zaheer et al., 2017), one of the most popular models for (multi)set learning. It incorporates two multilayer perceptrons (MLP). We used the same number of hidden layers for the two MLPs and tuned the hyperparameters, the number of layers in each MLP, the middle dimension, and the hidden dimension. Each model was trained to minimize the mean squared error on a training set.
Data Generation As training data, we generated 500 multisets of size {2, 3, 4} (chosen uniformly random). All the elements were single-dimensional and selected uniformly at random from [−5.0, 5.0]. A validation data of 100 multisets were generated from the same distribution. We prepared two kinds of test data. One consisted of 100 multisets drawn from the same distribution as the training and validation data, which we refer to by small. To see the size-generalization ability, the other consisted of 100 multisets of size {10, 11, 12} (chosen uniformly at random) with the same element distribution, which we refer to by large.
Results Table 7 summarizes the results. For the group functions, all models including the Abelian semigroup network performed well. This is consistent with the fact that group operations can be approximated by the Abelian semigroup network, as discussed in Section A. While the Abelian group network was better on the other two cases, DeepSets outperformed the Abelian group network on 3 √ x3 + y3. This is possibly due to the optimization of MLPs in DeepSets being easier than monotonic networks in the Abelian group network and Abelian semigroup network. Invertible neural networks for the single-dimensional case that are easy to optimize are important for future work. For the semigroup operations, as well as DeepSets, the Abelian group network did not work well. This is reasonable because these semigroup operations can not be expressed by the Abelian group network.
On the size generalization, although DeepSets worked fairly well, our models worked better. For example, the Abelian semigroup network was better than DeepSets on large of x+ y despite being worse on small; The Abelian group network had similar results on xy and x+ y + xy2 .

heading: C PROOFS
text: C.1 PROOF OF THEOREM 1
First, we review a theorem of the Abelian Lie group, which is important in our proof. The real numbers R with the addition + forms a Lie group, which we denote by (R,+). Also, the torus T = R/2πZ with the addition + modulo 2πZ forms a Lie group, which we denote by (T,+). It is known that any connected Abelian Lie group is isomorphic to (R,+)k× (T,+)h for some k, h ∈ N (Section 4.4.2 of (Procesi, 2007)).
Now, we give the proof of Theorem 1.
Proof. We use the fact that any connected Abelian Lie group is isomorphic to (R,+)k × (T,+)h for some k, h ∈ N. Since there is no homeomorphic function R (which is not compact) to T (which is compact), Abelian Lie groups over a Euclidean space has the form of only (R,+)k. Therefore, any ∗ can be represented as x ∗ y = π−1(π(x) + π(y)), (32) where π : X → X is a homeomorphic function in terms of Lie groups, i.e., π(·) and π−1(·) are analytic. Take any > 0 and a compact subset K ⊂ X . We denote the image of K ×K through the function (x,y) 7→ π(x) + π(y) by S ′ = {π(x) + π(y) | x,y ∈ K}. Let
S = {s | ∃s′ ∈ S ′ s.t. ‖s− s′‖ ≤ 2 } (33)
and K′ = K ∪ π−1(S). (34)
Then, we have a Lipschitz constant L > 0 of π−1 over S since π−1 is continuous and S is compact. Also, from the universality of invertible neural networks (Teshima et al., 2020) for the compact set K′, there exists an invertible neural network φ : X → X such that for any x ∈ K′
‖π(x)− φ(x)‖ < 2L+ 1
(35)
and for any x′ ∈ π(K′) ‖π−1(x′)− φ−1(x′)‖ <
2L+ 1 . (36)
Then, for any x,y ∈ K, φ(x) + φ(y) ∈ S(⊂ π(K′)) because
‖(π(x) + π(y))− (φ(x) + φ(y))‖ ≤ ‖π(x)− φ(x)‖+ ‖π(y) + φ(y)‖
< 2
2L+ 1
< 2 .
(37)
Therefore, for any x,y ∈ X , we have from the Lipshitz continuity of π−1
‖π−1(π(x) + π(y))− π−1(φ(x) + φ(y))‖ ≤ L‖(π(x) + π(y))− (φ(x) + φ(y))‖
< L · 2 2L+ 1
= 2L
2L+ 1
(38)
and from Equation 36
‖π−1(φ(x) + φ(y))− φ−1(φ(x) + φ(y))‖ < 2L+ 1 . (39)
From Equation 38 and 39, for any x,y ∈ K, we obtain
‖(x ∗ y)− (x ◦ y)‖ = ‖π−1(π(x) + π(y))− φ−1(φ(x) + φ(y))‖ ≤ ‖π−1(π(x) + π(y))− π−1(φ(x) + φ(y))‖ + ‖π−1(φ(x) + φ(y))− φ−1(φ(x) + φ(y))‖
≤ 2L 2L+ 1 + 2L+ 1
= .
(40)
This concludes that Abelian group networks are universal.
C.2 PROOF OF THEOREM 2
Proof. We prove that for anyX ∈ NX of size smaller than b ≥ a,
‖f(X)− f∗(X)‖ < ( (aK1K2) dloga be − 1 )
aK1K2 − 1 (41)
by induction on size b. Note that K1K2 > 1 because they are the Lipschitz constants of inverse functions.
Base Case When b = a, Inequality 41 holds.
Inductive Step We assume Inequality 41 holds for size b′ = 1, . . . , b− 1. We divide X of size b into balanced a subsetsX1, . . . ,Xa so thatX =X1+· · ·Xa and each |Xi| ≤ d bae (Addition over multisets is defined as follows: {x1, . . . ,xn}+ {xn+1, . . . ,xN} = {x1, . . . ,xn,xn+1, . . . ,xN}).
Then,
‖f(X)− f∗(X)‖ = ∥∥∥∥∥φ−1 (∑
x∈X
φ(x) ) − ©
x∈X x ∥∥∥∥∥ = ∥∥∥∥∥φ−1 ( a∑ i=1 ∑ x∈Xi φ(x) ) − a © i=1 ( © x∈Xi x
)∥∥∥∥∥ = ∥∥∥∥∥φ−1 ( a∑ i=1 φ(f(Xi)) ) − f∗ ({f∗(X1), . . . , f∗(Xa)})
∥∥∥∥∥ ≤ ∥∥∥∥∥φ−1 ( a∑ i=1 φ(f(Xi)) ) − φ−1 ( a∑ i=1 φ(f∗(Xi))
)∥∥∥∥∥+∥∥∥∥∥φ−1 ( a∑ i=1 φ(f∗(Xi)) ) − f∗ ({f∗(X1), . . . , f∗(Xa)})
∥∥∥∥∥ ≤ K2
∥∥∥∥∥ a∑ i=1 φ(f(Xi))− φ(f∗(Xi)) ∥∥∥∥∥+ ‖f ({f∗(X1), . . . , f∗(Xa)})− f∗ ({f∗(X1), . . . , f∗(Xa)})‖
< K2 ( a∑ i=1 ‖φ(f(Xi))− φ(f∗(Xi))‖ ) +
≤ K2 ( a∑ i=1 K1 ‖f(Xi)− f∗(Xi)‖ ) +
= K1K2 ( a∑ i=1 ‖f(Xi)− f∗(Xi)‖ ) + .
(42)
From the assumption on size d bae, we obtain
‖f(X)− f∗(X)‖ < aK1K2 · ((aK1K2) dlogad ba ee − 1) aK1K2 − 1 +
< aK1K2 · ((aK1K2) dloga ba e − 1) aK1K2 − 1 +
< ( (aK1K2) dloga be − 1 )
aK1K2 − 1 ,
(43)
which establishes the inductive step.
C.3 PROOF OF THEOREM 3
Proof. First, we prove that associative polynomials are at most first-order for each variable. Assume that we have a n-order (n ≥ 2) associative polynomial
x ∗ y = n∑ i=0 n∑ j=0 αi,jx iyj , (44)
where αi,j ∈ R for 0 ≤ i, j ≤ n. Then, we have
(x ∗ y) ∗ z = n∑ i=0 n∑ j=0 αi,j( n∑ k=0 n∑ l=0 αk,lx kyl)izj (45)
and
x ∗ (y ∗ z) = n∑ i=0 n∑ j=0 αi,jx i( n∑ k=0 n∑ l=0 αk,ly kzl)i. (46)
Since ∗ is associative, these two must form an identity. By comparing a coefficient of xn2 , we obtain n∑ j=0 αn,j( n∑ l=0 αn,ly l)nzj = 0. (47)
If we have 0 ≤ j′ ≤ n such that αn,j′ 6= 0, from the coefficient of zj ′ ,
( n∑ l=0 αn,ly l)n = 0. (48)
Recursively, we get αn,0 = αn,1 = · · · = αn,n = 0, which leads to contradiction. Therefore, we now have αn,0 = αn,1 = · · · = αn,n = 0. (49) In the same way, we can also prove
α0,n = α1,n = · · · = αn,n = 0. (50)
From Equation 49 and 50 for n ≥ 2, now we know that associative polynomials are at most firstorder for each variable. Therefore, symmetric associative polynomials have the form:
x ∗ y = α+ β(x+ y) + γxy. (51)
Then we have
(x ∗ y) ∗ z = α+ β((α+ β(x+ y) + γxy) + z) + γ(α+ β(x+ y) + γxy)z (52)
and x ∗ (y ∗ z) = α+ β((α+ β(x+ y) + γxy) + z) + γ(α+ β(x+ y) + γxy)z. (53)
By solving this identity, we obtain αγ = β(β − 1). (54)
This condition is equivalent to the associativity of ∗. It decomposes into three cases: (γ = 0, β = 0), (γ = 0, β = 1), and γ 6= 0. For each case, we obtain
x ∗ y =  α α+ x+ y β(β−1)
γ + β(x+ y) + γxy (γ 6= 0). (55)

heading: D EXPERIMENTAL DETAILS
text: Here, we explain the detailed setting and further discussion of the experiments that we did not cover in the main part.
D.1 EXPERIMENTS OF SIZE GENERALIZATION
Model Architecture For the implementation of the monotonic networks, we followed the Equation 4, except that we added a coefficient term s ∈ R which automatically learn the sign of the weights:
f(x) = min 1≤k≤K max 1≤j≤Jk
s · exp(w̃(k,j)) · x+ b(k,j). (56)
Hyperparameters All networks were trained by the Adam algorithm of lr = 10−3, beta = (0.9, 0.999) for 1000 epochs with the batch size of 32. Hyperparameters of each model were tuned with the validation dataset using the Optuna framework for each function. For DeepSets, the number of layers for each MLP was selected from [2, 8] and the middle dimension and hidden dimension were selected from [2, 32]. For the Abelian group network and Abelian semigroup network, the number of groups and the number of units in each group were selected from [2, 32].
D.2 WORD ANALOGIES
Model architecture For the invertible neural network for the Abelian group network and Abelian semigroup network, we implemented a model based on the affine coupling flows using the FrEIA framework 2. We stacked Glow coupling layers and random permutation layers of the dimensions in turn. For each Glow coupling layer, we used three layer feedforward neural networks with a hyperparameter of hidden dim as a sub network. For MLP and MLP C, we implemented multilayer perceptrons with the ReLU activation function.
Hyperparameters All networks were trained by the Adam algorithm of lr = 10−3, beta = (0.9, 0.999) for 100 epochs with the batch size of 32. The hyperparameters of each model were tuned with the validation dataset using the Optuna framework. For MLP, the number of layers was selected from [2, 6] and the hidden dimension was selected from [8, 256]. For the Abelian group network, the number of layers was selected from [2, 6] and the hidden dimension was selected from [8, 256]. Weight decay was selected from [0, 10−3] for all models.
Table 8 summarizes the selected hyperparameters for each model.
Detailed Results In Table 9 and 10, we explained all the subcategories of the bigger analogy test set and the Google analogy test set. We summarized the full results for each subcategory in Table 11, 12, 13, and 14.
2https://github.com/VLL-HD/FrEIA

Review summaries:
The authors introduce Abelian group networks (AGN) that explicitly model the operational relation between elements in an Abelian group. The authors prove that the design has the ability to model such relations and present feasible neural network realizations. The authors also prove the ability of AGN to learn representations of multisets. The authors design experiments to test AGN's ability to model word analogy by viewing the "a:b = c:d" relation as $c - a + b$. The results seem to suggest that AGN outperforms MLP baselines always and word vectors in some cases. However, closer examinations reveal concerns about their strength and validity to support the efficacy of AGN.

This paper introduces a new kind of neural network for multisets of vector inputs. Whereas DeepSets uses a function h(x, y) = g(f(x) + f(y)), the proposed model uses h(x, y) = f^{-1}(f(x) + f(y)), where f is an invertible neural network. It applies this network to the problem of learning word analogies.