Abelian Neural Networks
Authors: Kenshin Abe
Takanori Maehara
Issei Sato
Venue: ICLR 2022 Submitted (2022)
Keywords: algebra
Abelian group
word analogy
invertible neural networks
permutation invariant
size generalization

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.

Under review as a conference paper at ICLR 2022
ABELIAN NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In several domains such as natural language processing, it has been empirically reported that simple addition and subtraction in somehow learned emhedding space capture analogical relations. However, there is no guarantee that such rela- tion holds for 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 neu- ral networks and show its universal approximation property. In experiments, our model successfully learns to capture word analogies from word2vec representa- tions and shows better performance than other learning-basel strategies. As a byproduct of modeling Abelian group operations, we furthermore obtaín its natu- ral extension to permutation invariant models with theoretical size-gnncralization capability.
INTRODUCTION
The vector representations of words called word2vec (Mikolov al., 201 20;3;;) trained only on large unlabeled text data are known to capture linear regularities between words. For example, vec("king") vec("eemn veec"" veom"wommn") results in the most similar vector to veo("queen"). Sim- ilar 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 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 embedding space captures some kinds of analogies, might not work for other kinds of analogies. Indeed, word2vec representation works well for inflectional analogies 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 tune the training algorithm for certain kinds of analogies you want 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 supervised manner how to model analogical functions. A naive way to do this is to train two separate models corresponding to addition and subtraction, respectively; however, does not reflect the analogical structure and might be inefficient. In this work, we propose an Abelian group network to incorporate 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 side effect of the algebraic structure, can construct 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 auto- matically 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

---

Under review as a conference paper at ICLR 2022
the other hand, our multiset models naturally induce the ge-nenelilzzziin capability because the output for larger inputs can be written as the composition of small elements. Further, we show that 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.
2
PRELIMINARIES
2.1
DEFINITIONS
In this section, let us introduce some basic notations and important definitions that will play a key role in this work.
2.1.1 BASIC NOTATIONS
By N, we represent the set of the natural numbers including O. We denote vector by a bold symbol, e.g., æ. Let x Rd be d-dimensional vector. We represent the i-th element (1 I S d) of by For 1 k d, ISk E IR is the k-dimensional vector (#1.... .zA) and Z< E R== is the (k- -1)-dimmesio vector (.I,...TK-1
We denote the elementwise product of two vectors y E Ra by x & y. such that (ær @ y); Iilki and the elementwise division of two vectors a E R y E (RR) \ {0))d by æ Ø y, such that (æ 2 y): = 21/U6. By || Il. we represent the La (Euclidean) norm.
2.1.2 MULTISET AND PERMUTATION INVARIANCE
Here, we use X' and y to describe some domains, which are typically Euclidean spaces, i.c. X Rdi and = d2d We denote the of multisets over X' by N* We use {.1,... E N to describe multiset composed of æ1...., In E X (any confusion with sets is not problematic in this paper). The cardinality of a multiset the number of elements with multiplicity and is expressed by e.,. 2, 4.
For n E N, a symmetric group Sn is the set of all n! bijective functions a: (1,2..... .RJ.
n) -
m). For permutation E Sn and X E X, x is defined such that (a-X): Xo()) for all i E (1..... nn.. A function f: N - Y is said to be permutation invariant if for any X E X and for any permutation that take vectors of different dimensions. Namely, function f: UKEN x + Y is called permuta- Sk, ((. X) f(X) holds. When f: UKeN X - y is permutation invariant, it can be also viewed as a function that takes multisets input. For notation simplicity, sometimes use the same symbol to express the multiset function: f: N + y
Sn, fo XX) = f(X) holds. This concept can be extended functions
tion invariant if for any N, for any X x and for any permutation
2.1.3 UNIVERSALITY
Universality is an important theoretical property neural networks' expressive power. Let and Y' be an input domain and an output domain, respectively. We consider a model M and a class of target functions F. both of which are sets functions X' + y. The model M sup-universal approximator of F if for any target function f* F, for any O, and for any compact subset C X. there exists a function f M such that
sup [f(x) ff==)=f(()))) <c. æEk
If not noted otherwise, universality refers to the sup-universal property.
2.1.4 BASIC ALGEBRA
Here, we introduce the basic definition of important algebraic structures in this study. Let be set and o: G x G G be a binary operation. Below, review four properties define Abelian semigroups and groups.
Associativity For any x, y. (xo oz o
2

---

Under review as a conference paper at ICLR 2022
Identity Element
G, called the identity element, such that for any There exists element x E G,roc= e z = Z.
Inverse Element For any æ E G, there exists an element x= E G, called the inverse element of x, such that r
oz =..
Commutativity For any x. G, z
Table shows which properties are required in each algebraic structure. A semigroup only requires associativity the binary operation. group is a semigroup with an identity element and inverse elements. An Abelian (semi)group is (semi)group with commutativity.
Table 1: Properties required for each algebraic structure.
Associativity Identity
Inverse
Commutativity
Semigroup Group
Abelian Semigroup
Abelian Group
2.2 INVERTIBLE NEURAL NETWORKS
Invertible neural networks are neural networks that approximate invertible functions R2 + Rd. Here, we review some existing studies for multi-dimensional case, i.e., 2, and single- dimensional case, i.e., d
2.2.1 NORMALIZING FLOWS
multi-dimensional invertible neural networks have been studied mainly in the context of normaliz- ing flows (Tabak & Vanden-Fijnden, 2010), which iteratively apply invertible functions to a sim- ple 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 al., 2017). Here we review affine coupling flows (Dinh et al., 2015), one of the most popular mod- els with parallelizable efficient inverse computation. Each layer of the affine coupling flows maps x = (Z1...., E Rd to y = (y/1.... ya) E IRd such that
Y& ggk:
(2)
リ> wン & exp(a(x<u)) + ((æss),
where exp is applied elementwise and a, R Rd-k are trainable functions. The inverse is computed as follows:
aghh ysk,
x>*k (シ>k ((y @ exp(-a(y<x)).
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 universalitics on certain classes of functions (Teshima al., 2020). The affine coupling flows are Ll-universal (weaker condition of universality) for C² O"-diffcommophiimms Some more complex models, including deep sigmoidal flows (Huang et al., 2018) and sum-of-squaal of-squrres polynomial flows (Jaini al., 2019), are universal for C dd-iffeomorphisms..
2.2.2
INVERTIBLE NEURAL NETWORKS
For mingle-dimensional functions, invertibility is equivalent to strict monotonicity. Monotonic net- works (Sill, 1997) model strictly monotonic functions. The monotonically increasing version with
3

---

Under review as a conference paper at ICLR 2022
K groups and J3 units for k-th group is as follows:
f(x) = min max exp( x ((ho)) ISKS 1855
(4)
where w((e), ((k5) R are trainable parameters. The monotonic networks are universal ap- proximator for strictly monotonic differentiable functions. Monotonic quaddrtcc transforms (Durkan et al., 2019) are another universal model for the single-dimensional case.
PROPOSED METHODS
Here, we introduce the proposed methods. First, we propose model for Abelian group operations and show its universality. Next, explain how to model analogical relations by our model. Finally, we present architectures for multiset input and show the size-generalization ability.
3.1 ABELIAN GROUP NETWORK
Let X' be Euclidean space, i.e., Rd E N). We present the Abelian group network that models Abelian group operations follows:
zo yoy= - o(y)),
(5)
where o: X - A' is trainable invertible function, typically modeled by invertible neural net- work.
First, check that this binary operation satisfies the four conditions of the Abelian group described in Section 2.1.4.
Proposition 1 (Semigroup Conservation). Let p: X + X be a bijective function. When X X X is associative, ooy p (p(x) p(y)) is also associative. Similarly, when * is commutative, is also commutative.
Proof. Associativity:
(xx) p(2)) =p-a((((a)) p(u)) p())
(6)
= =p-) * (p(y) (: Associativity of x)
(p(x))()) p(p (p(y) ((z)))) = a (y o z).
Commutativity:
yo x (p(x) * p(z))
(p(x)) ply)) (: Commutativity of +)
x oy..
By this proposition, since + is associative and commutative, the Abelian group network is also associative and commutative. The identity element
e (0)
(8)
which satisfies
2oe x (0 (0))
(9)
= (6(x) + 0)
for all E X. The inverse element of E X' is
Φ 1 (- ((x)))
(10)

---

Under review as a conference paper at ICLR 2022
which satisfies
x o a - x (0 (-o(x))) 0 ()(x) -(())
(11)
- (0)= =c
It is worth noting that we can analytically compute the inverse function (Equation 10).
Next, check the expressive power of the Abelian group network. An Abelian Lie group is an Abelian group over manifold in which the group operation (z, y) + x o and the inverse function + are both differentiable. The following theorem states that the Abelian group network can approximate any Abelian Lie group operation with arbitrary precision.
Theorem (Universality of Abelian group networks), Let X be a Euclidean space. Abelian group networks are universal approximator of Abelian Lie group operations over X. In other words, for any Abelian Lie group operation *: X X - X, for any >> O, and for any compact subset K. C X, there exists a binary operation function o: X X + X represented by Abelian group network such that
[1 y (x y) <e YEK.YEK
sup
(12)
We provide the proof in Appendix C.I. It is based on the theory of the Abelian Lie group and the universality of invertible neural networks.
3.2 MODELING ANALOGY BY ABELIAN GROUP NETWORK
Now we consider an analogical task of predicting an element in relation : a, b, c, d E X be embedded vectors of corresponding elements. We need define a model f: X x X' x X - X' that predicts d from a, b, and c. Then, if the set of candidate elements are finite as word embedding, we can search nearest vector to [(a b, c). We explained in Section that several studies heuristically use S(a, b, c) = b
: = c d. Let
Analogical relations have two natural laws: when a = b, then = holds; a b c: d equivalent to b d. when the two condition that f(a, b, c) = c when a b, and f(a, b) = f(a, c, 6). These conditions hold in f(a, b. c) b + However, when try parametrize f by neural networks, it is not trivial to reflect these inductive biases using existing architectures. By using the Abelian group network, model f that it reflects the conditions follows:
then 6 d holds. Therefore, we would like to design f to satisfy
(aabb, c) b a!
( + 660-
(13)
o (d(() ((a)) oc.
= - ((a) + H(c)).
Also, this is strictly more expressive than the simple arithmetic operations because when & is the identity, o(a, b, c) b c. We can train this model by minimizing the loss: 1(f(a, b, c), d), where I: X' can typically be an I loss or negative cosine similarity.
3.3 MULTISET ARCHITECTURE AND SIZE GENERALIZATION
Here, we construct multiset architecture by combining the Abelian group networks and show it naturally generalizes in sizes. It is casy to check that if o: X X' + X' is associative and commutative, f: X X' defined by
(14) is permutation invariant. When this condition holds, represent the multiset version of f: Nx X' as follows by denoting a composition of o by O: f(x) = OzE x, where X E NN is multiset of X. By modeling by the Abelian group network, we can construct multiset architecture of the Abelian group network:
f( xx) = σ1 x2
f(X) = 01
Σ d(m)) xE
Σd(z)
(15)
5

---

Under review as a conference paper at ICLR 2022
where the invertible function Φ: X X' is typically modeled by invertible neural network.
Now, we consider the size- tizz-enneralization ability of the multiset architectures. An intuitive explana- tion is follows. As extreme casc, even if trained only multisets of two elements, our models can learn the correct binary operation. Therefore, they generalize to multisets of larger sizes. In general,
derive the following theorem. Appendix C.2 provides the proof.
Theorem 2 (Size Generalization of Abelian Group Networks), Let fr; N tion expressed by composition of Abelian semigroup (X) (X) O Let f: No + X
+ X be target func-
be a multiset architecture of the Abelian group network: f(X)= = -- (Enex 6(x)).
When
llf(x) - (x)) <E
(16)
holds for any X (E N*) whose size is smaller than a (2 2), then
[If(X) - f(xiil {(aK,Kg, flog. -1 aK1K2 -
(17)
holds for any X (E N whose size b (2 a), under the condition that the Lipschitz constants of and 6- are K1 and K2, respectively.
necessary and sufficient condition of f in Equation being permutation invariant that an Abelian semigroup operation. In Appendix A, we provide the proof and propose Abelian semigroup network by using the characterization associative symmetric polynomials.
EXPERIMENTS
Here, we summarize the main experiment of learning word analogies. In addition this section, we provide the experiments of size generalization on learning multiset functions in Appendix B.
4.1 COMMON SETTINGS
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 Intel Xeon E5-2699 v4 with NVIDIA
the Optuna
framework (Akiba et al., 2019). The experiments Tesla P100 GPU. See Appendix D for the detailed settings, such as the model architecture and the range of hyperparameters.
4.2 WORD ANALOGIES
In Section 1, We discussed the general motivation of training analogical functions over an embed- ding space. In addition, here, we explain the specific issue word2vee (Mikolov et al., 201 3a;b) and justify the motivation of using the Abelian group network. In word2vec, for predicting word a relation the corresponding vector for each word by using bold symbol) is selected in terms of the cosine similarity:
: d, the word with the most similar vector to b + e (we denote
cos(v); v2) 1 22
(18)
Usually, the words a, b, e are excluded from the candidate vocabulary under the assumption that common word does appear in one analogy example. Although this assumption reason- able in many cases, it prevents us from solving certain problems such as past tense verb analogy "do""""id"" "split":
"deer":'derr". On the other hand, if we do not exclude the words a, b, 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 b- a + c has a high probability being close to b or e in the cosine similar- ity, 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- approaches.
or plural noun analogy "apple":"applee

---

Under review as a conference paper at ICLR 2022
Word Embedding We used 300-dimensional word2vec model for 3 billion words trained Google News corpus of about 100 billion words'. We normalized each word embedding by L norm, following the implementation of the Gensim framework (Rehūřek & Sojka, 2010).
Word Analogy Models We compared different models for word analogy function f R2000 x R2000 x R8:00 + R2:00 that takes the vectors of words a, b, c and predicts the vector of a word d. In the modeled by Equation 13. For the invertible neural network
proposed method (WV + AGN), 6: 32000 + R-300 we implemented a model based on the affine coupling flows described in Section 2.2.1. In addition the original word2vec (WV): f(a, b, c) b- + c, we prepared two trainable baselines based on a multilayer perceptron (WV + MLP and WV + MLP.C, respectively):
f(a, b, = MLP a + c),
(19)
f(a. c) MLP MMPPCMCOOOO (CONCATT b,)).
(20)
where we trained MLP: 300 + 1:300 or MLPc 12900 - 30000
Setup Except for WV, we trained ʃ by minimizing the loss function: lossy b, e, 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:
arg max cos(f(a, b, c),d), dEV
(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:
arg max cos(f b, c). de (a.
(22)
Datasets We trained our models on the bigger analogy test set (Rogers et al., 2016), which con- sists of categories, each of which has 10 smaller subcategories of 50 unique relations. First, 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 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 syn- tactic), and all the words were included in the word2vee vocabulary. Tables 9 and 10 Appendix D.2 summarize the explanation and the number of extracted pairs for all subcategories.
Table 2: Accuracy on bigger analogy test set when we selected from the whole words.
num
WV
WV + MLP
WV + MLP.C
WV AGN
Overall
3314
177 (5.34%)
565 (17.05%)
674 (20.34%)
690 (20.82 %)
Inflectional
900
100 (11.11%)
317 (35.22%
340 (37.78%)
435 (48.33
Derivational
882
4 (0.45%)
15 (1.70%)
40 (4.54 %)
20 (2.27%)
Lexicographic
632
52 (8.23%)
154 (24.37%)
202 (31.96% %)
172 (2..2%%)
Encyclopedic
900
21 (2.33%)
79 (8.78%)
92 (10.22%)
63 (7.00%)
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, 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.
7

---

Under review as a conference paper at ICLR 2022
Table 3: Accuracy on bigger analogy test set when we excluded a, b, c from the candidates.
num
WV
WV + MLP
WV MLP
WV + AGN
Overall
3314
864 (26.07%)
569 (17.17%)
686 (20.70%)
1065 (32.14%)
Inflectional
900
614 (68.
324 (36.00%)
369 (41.00%)
656 (72.89
Derivational
882
103 (11.68%) %)
17 (1.93%)
43 (4.88%)
98 (11.11%)
Lexicographic
632
83 (13.13%)
151 (23.89%)
188 (29.75%)
205 (32.44 %)
Encyclopedic
900
64 (7.11%)
77 (8.56%)
86 (9.56%)
106 (11.78 %)
Table 4: Accuracy of transfer test to Google analogy test set when we selected from the whole words.
num
WV
WV + MLP
WV + MLP_C
WV + AGN
Overall
19544
4033 (20.64%)
1346 (6.89%)
2222 (11.37%)
5676 (29.04 %)
Semantic 8869
1995 (22. 49%)
161 (1.82%)
256 (2.89%)
2260 (25.48 %)
Syntactic 10675
2038 (19.09%)
1185 (11.10%)
1966 (18.42%)
3416 (32.00
Only in the setting where we excluded a, 6, c from the candidates in the Google analogy test set, the proposed method did not outperform WV. This is possibly because the word2vee 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 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 WV. WV AGN also predicted the correct words for the last five relations, where we need to predict the words that appeared as 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.
RELATED WORK
5.1 ALGEBRAIC STRUCTURES IN NEURAL NETWORKS
In the literature of deep learning, algebraic structures mainly appear in the context of group invari- ant/equivariant neural networks. For image input, some studies tried to incorporate reflection and ro- tation 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 invarianneeoqquivaraacce 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.
5.2 INDUCTIVE BIAS AND EXPRESSIVE POWER OF NEURAL NETWORKS
Inductive biases are assumptions on the nature of the data-generating process or the space of so- lutions in machine learning (Battaglia et al., 2018). Many studies have constructed special neural networks that reflect the inductive biases of 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.
8

---

Under review as a conference paper at ICLR 2022
Table 5: Accuracy of transfer to Google analogy test set when we excluded a, b, from the
candidates.
num
WV
WV + MLP
WV + MLP.C
WV + AGN
Overall
19544
14382 (73.59%)
1427 (7.30%)
2414 (12.35%)
11857 (60.67%)
Semantic
8869
6482 (73.09 %)
163 (1.84%)
256 (2.89%)
4918 (55.45%)
Syntactic
10675
7900 (74.00 %)
1264 (11.84%)
2158 (20.22%)
6939 (65.00%)
Table 6: Answers of each model for relations that include identical words.
WV WV + MLP
WV MLP.C
WV + AGN
do:do make:?
make
realize
ensuring dustcover
make
apple:apple pen:?
retractable.leash did failed
pen
pen
do:did do:
seemed
did
apple:apples apple:?
apples parsley-sprig
fruit
apples
do:did = split:?
split failed
split
split
do:did set:?
set decided
established set
do:did = put:?
put
allowed
Serge Audate
put
applecapples deer:?
deer raptor
fawn Proximex C###
deer
applecapples = dice:?
dice ethnic heritages
dice
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 bijec- tive, 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 prop- erties. They have been shown 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 al., 2019a; Keriven Peyré, 2019; Machara & Hoang, 2019). For (multi)set learning problem, DeepSets (Zaheer et al., 2017) are one of the most popular models with universal approxi- mation property.
5.3
SIZE GENERALIZATION
Graph neural networks and neural networks for (multi)sets can handle graphs and sets of different sizes, and their citeeeeneralization 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; Veličković et al., 2020). However, from a theoretical perspective, there exist simple tasks which graph neural networks do not naturally generalize larger graphs (Yehudai 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 (multi)sets probably because of difficulty in analyzing DeepSets for inputs of different sizes.
CONCLUSION AND FUTURE WORK
In this work, we presented a novel neural network architecture to model an Abelian group with universality. 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, 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.
application other than

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving np-hard problems on graphs with extended alphago zero. arXiv: Learning, 2019.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 2019.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray Kavukcuoglu. Interaction networks for learning about objects, relations and physies. In Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016.
Peter Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. ArXiv, abs/ 1e//11006002660 2018.
Jens Behrmann, Will Grathwohl, Ricky TQ Chen, David Duvenaud, and Jörn-Henrik Jacobsen. Invertible residual networks. In International Conference on Machine Learning, pp. 573-582, 2019.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary dif- ferential equations. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 6572-6583, 2018.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In Maria Florina Balcan and Kilian Q Weinberger (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2990-2999, New York, New York, USA, Jun 2016. PMLR.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: mation. Workshop of International Conference Learning Representations, 2015.
Non-linear independent components esti-
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. Inter-
national Conference on Learning Representations, 2017.
Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Neural spline flows, In Conference on Neural Information Processing Systems, 2019.
Ben Eisner, Tim Rocktäschel, Isabelle Augenstein, Matko Bosnjak, and Sebastian Riedel. emoji2vec: Learning emoji representations from their description. ArXiv, ht///669.08355 2016.
J. Gilmer, S. Schoenholz, P. Riley, Oriol Vinyals, and G. Dahl. Neural message passing for quantum chemistry. Proceedings of the 34th International Conference on Machine Learning, 2017.
Aaron Hertzmann, Charles E. Jacobs, Nuria Oliver, Brian Curless, and D. Salesin. Image analogies. Proceedings of the 28th annual conference on Computer graphics and interactive techniques, 2001.
C. Huang, David Krueger, Alexandre Lacoste, and Aaron C. Courville, Neural autoregressive flows. In International Conference on Machine Learning, 2018
Priyank Jaini, Kira A. Selby, and Yaoliang Yu. Sum-of-squares polynomial flow. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3009-3018, PMLR, 09-15 Jun 2019.
N. Keriven and G. Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems 32, 2019.
10

---

Under review as a conference paper at ICLR 2022
Elias Boutros Khalil, Hanjun Dai, Yuyu Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In Conference on Neural Information Processing Systems, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Diederik P. Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1xl convolutions. Conference in Neural Information Processing Systems, 2018.
Diederik P. Kingma, Tim Salimans, and M. Welling. Improved variational inference with inverse autoregressive flow. In Advances in Neural Information Processing Systems, 2017.
Thomas Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Ryan Kiros, Ruslan Salakhutdinov, and Richard Zemel. Unifying visual-semantic embeddings with multimodal neural language models. ArXiv, Abs/1411.25533 2014.
I. Kobyzev, S. Prince, and M. Brubaker. Normalizing flows: introduction and review of current methods. IEFE transactions pattern analysis and machine intelligence, 2020.
Y. LeCun, B. Boser, Denker, D. Henderson, Howard, W. Hubbard, and L.. Jackel. Backpropa- gation applied to handwritten zip code recognition. Neural Computation, 1:541-551, 1989.
Omer Levy, Yoav Goldberg, and Ido Dagan. Improving distributional similarity with lessons learned from word embeddings. Transactions of the Association for Computational Linguistics, 2015.
T. Maehara and NT Hoang. A simple proof of the universality of invariant/cquivariant graph neural networks. ArXiv, 2019.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Y. Lipman. On the universality of invariant net- works. In Proceedings of the 36th International Conference Machine Learning, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4363-4371. PMLR, 09-15 Jun 2019b.
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6734-6744. PMLR, 13-18 Jul 2020.
Tomas Mikolov, Kai Chen, G. S. Corrado, and J. Dean. Efficient estimation of word representations in vector space. In Workshop of International Conference on Learning Representattonss, 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. Conference on Neural Information Processing Systems, 2013b.
Andriy Mnih and Koray Kavukeuoglu. Learning word embeddings efficiently with noise-contrastive estimation. In NIPS, 2013.
C. Morris, Martin Ritzert, M. Fey, William L. Hamilton, J. E. Lenssen, Gaurav Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Conference on Artificial Intelligence, 2019.
George Papamakarios, Eric T. Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Bal- aji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. ArXiv, abs/1911.02762,, 2019.
11

---

Under review as a conference paper at ICLR 2022
Adam Paszke, S. Gross, Francisco Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, Alban Desmaison, Andreas Köpf, E. Yang. Zach Vito Martin Rai- son, Alykhan Tejani, Sasank Chilamkurthy, B. Steiner, Lu Fang, Junjie Bai, and Soumith Chin- tala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, 2019.
Jeffrey Pennington, R. Socher, and Christopher Manning. Glove: Global vectors for word repre- sentation. In Conference on Empirical Methods in Natural Language Processing, 2014.
Claudio Procesi. Lie groups. an approach through invariants and representations. Bull. Amer. Math. Soc, 2007.
C. R. Qi, H. Su, Kaichun Mo, and L. Guibas. Pointnet: Deep learning point sets for 3d classi- fication and segmentation. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 77-85, 2017.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. CoRR, abs/1 1ts//511..00 106434, 2016.
Radim Rehüřek and Petr Sojka. Software Framework for Topic Modelling with Large Corpora. In Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, pp. 45-50, Valletta, Malta, May 2010. ELRA.
Anna Rogers, Aleksandr Drozd, and S. Matsuoka. Analogy- basee detection of morphological and semantic relations with word embeddings: what works and what doesn't. In SRW@ IILTNALAA, 2016.
R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combina- torial problems. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, 2019.
J. Sill. Monotonic networks. In Conference on Neural Information Processing Systems, 1997.
E. Tabak and E. Vanden-Eijnden. Density estimation by dual ascent of the log-likelihood. Commu- nications in Mathematical Sciences, 8:217-233, 2010.
Takeshi Teshima, I. Ishikawa, Koichi Tojo, Kenta Oono, M. Ikeda, and M. Sugiyama. Coupling- based invertible neural networks are universal diffeomorphism approximators. Conference on Neural Information Processing Systems, 2020.
Paul Upchurch, Jacob V. Gardner, Geoff Pleiss, Kavita Bala, Robert Pless, Noah Snavely, and Kil- ian Q Weinberger. Deep feature interpolation for image content changes. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 6090-6099, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, L. Kaiser, and Illia Polosukhin. Attention is all you need. In Conference on Neural Informa- tion Processing Systems, 2017.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execu- tion of graph algorithms. In International Conference on Learning Representations, 2020.
Daniel E. Worrall, Stephan Garbin, Daniyar Turmukhambetov, and Gabriel J. Brostow. Harmonic networks: Deep translation and rotation equivariance. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition ( (CVPR), July 2017.
Keyulu Xu, Weihua Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference Learning Representations, 2021.
12

---

Under review as a conference paper at ICLR 2022
Gilad Yehudai, Ethan Fetaya, E. Meirom, Gal Chechik, and Haggai Maron. On size generalization in graph neural networks. ArXiv, abs/2010.08853, 2020.
Reikichi Yoshida. On some semi-groups. Bulletin of the American Mathematical Society, 69(3): 369-371, 1963.
M. Zaheer, S. Kottur, Siamak Ravanbakhsh, Póczos, Salakhutdinov, and Alex Smola. Deep sets. Conference on Neural Information Processing Systems, 2017.
Ding-Xic Xuan Zhou. Universality of deep convolutional neural networks. ArXiv, abs/ (oss/8805.1069, 2018.
13

---

Under review as a conference paper at ICLR 2022
A
ABELIAN SEMIGROUP NETWORK
A.1 MOTIVATION
Below, we present 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 UKER X X be a function represented as
f(x) m1 Fn:
(23)
where X (.1...., T.) E X and o: X X X is binary operation (left-associative). The function f is invariant if and only if o 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((x), 222) = f((22, leads to 3 o 22 = 32 21 (commutativity). From / [(x1, B2 2x)) = f( [[(22, 22 31 )), we have (æt 222 2z
(x2 o Vz) x1 and commutativity leads to (æ1 x2) 2y = 21 o (22 o xx) (associativity).
On the basis of this proposition, 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 opera- tions, it is not sufficient for approximating an Abelian semigroup operation such as the product over R. i.c., x yy = zy. Now we extend the Abelian group network and propose the Abelian semigroup network. Our idea is to extend + of Equation 5 to polynomial. From Proposition 1, Equation is still a semigroup after we replace + by polynomial of and y as long as the polynomial is asso- ciative 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 brief explanation, we give detailed proof in Appendix C.3.
Theorem (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:
a a + x +
x
+ 9(8-1) 1) + 3(x + 9) + (7 + 0),
(24)
where oz, B, 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:
(a)
(25)
x o
(p(x)) + p(y) + a.)
(26)
(B@ (B - 1 BY++B (p(x) + p(y)) + 2 p(x) @ p(y)),
(27)
where p - X' an invertible function and a, B, E are parameters (r is nonzero for all elements in Equation 27). Equation 25 is constant case, on which we do not put focus due to its trivialness. Equation 26 forms a group where e = =p- (- =1 p p (-p(x))
2a.. It can
be expressed by the Abelian group network with ((x) p(x) a and ø (z) p (x a) in Equation Equation 27 is a semigroup but not group. Just using this equation is fine, but we propose simpler form, the Abelian semigroup network:
x o y = o- (Ø(x) @ Φ(v)),
(28)
where X - X' trainable invertible function typically modeled by an invertible neural network. This is special case of Equation 27 when 3 = 0. = and therefore is semigroup. Conversely, the Abelian semigroup network can express Equation 27 by
(xx) 7 p(x=) + B, & (xx - B) 8)001 77
(29)
14

---

Under review as a conference paper at ICLR 2022
Moreover, the Abelian semigroup network can approximate the Abelian group network: o' (d'(2) d'()). Let Xso = RS0- where X' Rd. One construction is approximating a bijective function : X Zzo.
<()) = exp(o x (ar) - (log(()))))))
(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 oper- ation which 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 { In E in simple form:
f(x) = - & ... & o(æx)),
(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 o(z;). which prevents us from inducing the bound like Theorem 2. However, still has the genereallaliznnnnn ability most real applications where the values are not too large. We confirm this by an experiment in Section B.
B EXPERIMENTS OF SIZE GENERALIZATION
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 y
y + y + Vz 3 + y (group cases) and z y zy,
2 (semigroup cases).
Setup For the iigle-dimensions invertible neural network of the Abelian group network and Abelian semigroup network, used monotonic networks (Sill, 1997). We tuned the hyperparame- ters, the number of groups and the number of units for each group. As baseline, we used DeepSets (Zaheer al., 2017), 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 layers in each MLP, the middle dimension, and the hidden dimension. Each model was trained to minimize the mean squared error on training set.
Data Generation As training data, we generated 500 multisets of size 3, 4] (chosen uni- formly 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 pre- pared 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-generalin aizegenerallzzttion 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 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 ap- proximated by the Abelian semigroup network, discussed in Section A. While the Abelian group network was better on the other two cases, DeepSets outperformed the Abelian group network on V23 + 33. This is possibly due to the optimization of MLPs in DeepSets being easier than mono- tonic networks in the Abelian group network and Abelian semigroup network. Invertible neural networks for the single-dimensional case that are casy 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 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 + despite being worse small; The Abelian group network had similar results on xy and + y 2
15

---

Under review as a conference paper at ICLR 2022
Table 7: Mean squared error comparison between the models for each function. The upper three operations are groups and the lower two equations are semigroups. Square root of the values are presented. Smaller better.
DeepSets
AGN
ASN
2. + y
small
0.00226
3.63e-7
0.0832
large
0.908
0.0366
0.309
x + y/ +
small
0.00772
4.17e-7
0.136
large 0.0335
0.0132
0.956
V 3 y
small
0.0844
0.284
0.427
large
0.229
0.636
1.26
small
13.0
36.7
0.00000295
large
28500
28390
31.5
y
small
0.965
7.08
0.000660
large
194
193
1.22
C PROOFS
C.I PROOF OF THEOREM 1
First, we review a theorem of the Abelian Lie group. which is important in our proof. The real numbers E with the addition + forms Lie group, which we denote by (R. Also, the torus T= RR/2zZ with the addition + modulo 2x forms a Lie group, which we denote by (T, +). It is known that any connected Abelian Lie group is isomorphic to (R, +) x (T, + for some k. h e N (Section 4.4.2 of (Procesi, 2007)).
Now, we give the proof of Theorem
Proof. We use the fact that any connected Abelian Lie group is isomorphic to (I, +) x (T, +) for some k, h E N. Since there is homeomorphic function & (which is not compact) to T (which compact), Abelian Lie groups over a Euclidean space has the form of only (R, +) Therefore, any be represented
(32) where π : X' + A' is a homeomorphic function in terms of Lie groups, i.e., x(-) and (-) are analytic. Take any >> 0 and a compact subset C X. We denote the image of IC K. through the function (x, y) + π (x) + (z) by S' = {ι))) + mty) æ y E KJ.. Let
x = ( + (B)))
S = {8 Es' E S' s.l. ||s s' < 2c}
(33)
and
K KK=
(34)
Then, we have Lipschitz constant L> of over S since - 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 æ E KC
[ ((x))1 +1
(35)
and for any x' E x(K')
(x') - x- (xx)) +1
(36)
Then, for any x, y E K, 6(x) (ly) E S(C ((C')) because
[T(T(>) + + (6(x) + ((v))11 < ||x(x) +|)() +vv))
2c
(37)
2L +1
2c.
16

---

Under review as a conference paper at ICLR 2022
Therefore, for any æ, y N, have from the Lipshitz continuity of .
n (a) (1)) ((((x)) + +()))) S (T)()) + (1)) (0(x) ((y))1
2c
< L
2L +1
(38)
2L
2T. +1
and from Equation 36
π | (+(x)+ +(y)) o ( 2L +1
(39)
From Equation 38 and 39, for any x; E Kc, we obtain
- (6(x) x 4) (x y)ll = | - (g))))
< (x n (
+ || (Ø(x) + +()) o- (0(x))
(40)
2Lc
2L +1 + 2L+1
6.
This concludes that Abelian group networks are universal.
C.2 PROOF OF THEOREM 2
Proof. We prove that for any X E 2 of size smaller than b b24 a,
1I((X) ((x))1(x)) e ((aK, Moga b1 [2)
1)
(41)
0KiK2 -1
by induction on size Note that K2 > because they are the Lipschitz constants of inverse functions.
Base Case When a, Inequality 41 holds.
Inductive Step We assume Inequality 41 holds for size 6/ = 1...., b 1. We divide X of size b into balanced a subsets X,...., X, so that x,+ Xx, and each X,l < [& (Addition over multisets is defined follows: {a1,..., Fn,) (# x2 (x) ... Fy. Butly By
17

---

Under review as a conference paper at ICLR 2022
Then,
0
Σ
((xx)
O
xE
((x))
Ö
x
x
(((()))
r (X)(),, ((xa)))
Σ Earrox))
((((i))
((f
- -f -1(1)()),...,
(42)
K₂
Σ
-((F(x))) +
11 (US
(Xx)))) - -r (L))
< K2
Σ -(0 +c
S K2
Σ
Ki (x))
- (((iil +
= K2
Σ [[(x))) - +e.
From the assumption on size [. we obtain
IIf(X) - f(x) < aK1K2 <((aK, loga [ -1) +
aKiK2
KKgK22 e((akiKg) 10g 87 - 1) +
(43)
aKiK2 K2
6 ((aKiK2) (2) [oga b7 - 1)
Kg -1
which establishes the inductive step.
11
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
0i yy
(44)
<=0 5m0
where aij E R for 0 ú.j S n. Then, we have
(x * 1)
a y y
k
(45)
0= 0=000 0
k=0 1=0
and
I (1*z)
ak. k 2
(46)
==0
k=0
18

---

Under review as a conference paper at ICLR 2022
Since is associative, these two must form an identity. By comparing coefficient of x" obtain
an =0.
(47)
==
1=0
If we have 0 i S such that an # 0, from the coefficient of a
anay' O.
(48)
1=0
Recursively, get an now have
0n ann
0, which leads to contradiction.
Therefore,
On = On,1
On,
(49)
In the same way, we can also prove
0n, a1n On,n
(50)
From Equation 49 and 50 for 2 now know that associative polynomials are at most first- order for each variable. Therefore, symmetric associative polynomials have the form:
x z + 3(x + 7-y-
(51)
Then we have
(x=y)=z=a+) B((a + 3(x + 3) + 7zy) + 2) + 7(a + 3(x + 3) + +zzy)
(52)
and
x (y) B((a B(x + u) + 7any) +) 7( 3(x 3) vay)=
(53)
By solving this identity, we obtain
o7 = ( 1).
(54)
This condition is equivalent to the associativity of s. It decomposes into three cases: (7 0, 0), (7 = 0, B = 1). and 7 * O. For each case, we obtain
x *
a a x x+ 3(8-1) + 3(x + v) + (v
(55)
D EXPERIMENTAL DETAILS
Here, we explain the detailed setting and further discussion of the experiments that we did not cover in the main part.
D. EXPERIMENTS OF SIZE GENERALIZATION
Model Architecture For the implementation of the monotonic networks, followed the Equa-
tion 4, except that we added a coefficient term E which automatically learn the sign of the weights:
f(x)
min max s (k)()) ((k.)
(56)
ISRSK 15954
Hyperparameters All networks were trained by the Adam algorithm of Ir 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]
19

---

Under review as a conference paper at ICLR 2022
D.2 WORD ANALOGIES
Model architecture For the invertible neural network for the Abelian group network and Abelian semigroup network, implemented model based the affine coupling flows using the FrEIA framework 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 hyperparameter of hidden dim as 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 Ir 10-3, beta (0.9, 0.999) for 100 epochs with the batch size of 32. The hyperparameters 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 selected from [2, 6] and the hidden dimension selected from [8, 256]. decay was selected from [0, 10 $ for all models.
each model were
Table 8 summarizes the selected hyperparameters for each model.
Table 8: Selected hyperparameters in word analogy task.
layer num
hidden dim
W2V W2V + MIP
4
223
W2V MLP_C
516
W2V + AGN
5
151
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.
20

---

Under review as a conference paper at ICLR 2022
Table 9: Detailed explanation of bigger analogy test pair refers the whole relation size, used refers to the number included in the word2vec model, and identical refers to the number of used relations that include identical words. category
subcategory
example
pair
used
identical
Inflectional
101 noun plural reg
album:albums
50
50
Inflectional
I02 noun plural irreg
ability:abilities
50
48
2
Inflectional
103 adj comparative
angrytangrier
50
Inflectional
104 superlatie
able:ablest
50
49
0
Inflectional
105 verb.inf 3pSg
accept:accepts
50
Inflectional
106 verb_inf- Ving
achieve:achieving
50
49
O
Inflectional
107 verb_inf Ved
accept:aceppeed
50
50
Inflectional
108 verb Ving 3pSg
adding:adds
50
50
Inflectional
109 verb Ving Ved 110 verb verb_3pSg- Ved
adding:added
50
50
Inflectional
adds:added
50
50
Derivational
D01 noun+less
arm:armless
50
48
Derivational
D02 un+adj reg
able:unable
50
Derivational
D03 adj+ly.rep reg
accordingaccorrding...
50
49
Derivational
D04 over+adj reg
ambitiouusoverrmbbit..
50
Derivational
D05 adj+ness reg
amazing:amazzingnes
50
45
Derivational
D06 re+verb reg
acquire:reacquire
50
Derivational
D07 verb+able_reg
accept:acceptable
50
49
Derivational
DO8 verb+er_irrep
achieve:achiever
50
49
Derivational
D09 verb+tion irreg
accuse:accusation
50
48
Derivational
D1O verb+ment irreg
accomplish:accommpli.
50
47
Encyclopedic
E01 country capital
abuja:nigeria
50
37
Encyclopedic
E02 country language
andorra:catalan
50
36
Encyclopedic
E03 UK_city county
aberdden::berrdeenshi..
50
Encyclopedic
E04 name nationality
aristotle:greek
50
23
Encyclopedic
E05 name occupation
andersen writepppe.......ppe......
50
Encyclopedic
E06 animal young
ape:baby/infant
50
50
Encyclopedic
E07 animal sound
alpaca:bray
50
Encyclopedic
E08 animal shelter
ant:anthillinseetar.
50
50
Encyclopedic
E09 things color
antbblac//boow//red
50
Encyclopedic
E10 male female
actor:actress
50
48
Lexicographic
L01 hypernyms animals
allosaurus:dinosaur.....
50
50
Lexicographic
L02 hypernyms misc
armchair
50
50
Lexicographic
L03 hyponyms misc
back backpack:daypackkk
50
50
Lexicographic
L04 meronyms substance
atmosphere:gas/oxyye..
50
50
Lexicographic
LO5 meronyms member
acropat
50
50
Lexicographic
L06 meronyms part
academiiarcollege/uii.
50
47
Lexicographic
L07 synonyms intensity
afraid:terrifieddhor....
50
50
Lexicographic
L08 synonyms exact
airplane:aeroplaneepp.
50
Lexicographic
L09 antonyms gradable
ablerumable/incapabl.
50
50
0
Lexicographic
L10 antonyms
binary
affer:beforeeeatier...
50
21

---

Under review as a conference paper at ICLR 2022
Table 10: Detailed explanation of Google analogy test set. num refers to the whole relation size and used refers the number included in the word2vec model.
category
subcategory
example
num
used
Semantic
capial-common-countiis
Athens:Greece
506
506
Semantic
capital-world
Abuja:Nigeria
4524
4524
Semantic
currency
Algeria:dinar
866
866
Semantic
city-in-state
Chicago:Illinois
2467
2467
Semantic
family
boy:girl
506
506
Syntactic
graml araml--djective-tt-advrrh
amazing.amazingly
992
Syntactic
gram2-opposite
acceptablerumaccpttablle
812
812
Syntactic
gram3-comparative
bad:worse
1332
1332
Syntactic
gram4-superlative
bad:worst
1122
1122
Syntactic
code:coding
1056
1056
Syntactic
nationality-adjeee
Albania.Albamian
1599
1599
Syntactic
gram7 -umn--pst-tense
dancing.danced
1560
1560
Syntactic
gram8-plural
banana:bananas
1332
1332
Syntactic
gram9-plural-verbs
decrease:decreases
870
870
22

---

Under review as a conference paper at ICLR 2022
Table 11: Model comparison for each subcategory of bigger analogy test
num
WV
WV + MLP
WV + MLP.C
WV + AGN
101
90
2(2.22%)
5(5.56%)
10(11.11%)
7(7.78%)
102
0(0.00%)
0(0.00%)
8(8.89%)
0(0.00%)
103
90
13(14.44%)
22((4.44%)
20(22.22%)
41(45.56%)
104
10(11.11%)
18(20.00%)
25(27.78%)
39(43.33%
105
90
26(28.89%)
58(64.44%)
52(57.78%)
60(66.67%
106
90
14(15.56%)
13(14.44%)
19(21.11%)
(7.63338%
107
90
3(3.33%)
54(60.00%)
42(46.67%)
42(46.67%)
108
90
11(12.22%)
40(44.44%)
51(66.67%
54(60.00%
109
8(8.89%
49(54.44%)
53(58899%
62 89%
I10
90
13(14.44%
58(64.44%)
60(66.67%)
73(81.11%
D01
90
0(0.00%
0(0.00%)
0
((.00%%
D02
90
0(0.00%)
1(111%)
(0.00%%
000.00%)
D03
1(1.11%
2(2.22%)
910.00%
5(5.66%)
DO4
90
0(0.00%)
0(0.00%)
(
0(0.00%)
D05
0(0.00%)
2(2.78%)
13(18.06%)
5(6.94%)
D06
90
0(0.00%)
2(2.22%)
8(8889%)
0(0.00%)
D07
90
0(0.00%)
0(0.00%)
0(0.00%)
0(0.00%)
DO8
0(0.00%)
4(4.44%)
1(1111%)
0(0.00%)
D09
90
3(3.33%
0(0.00%)
8(8.89%)
7(7.78%)
D10
0(0.00%)
4(4.44%)
1(1111%)
3(3.33%)
C01
56
((0000%
((0.00%)
1(1.79%)
2(3.57%)
E02
4(7.14%)
14(25.00%)
21(37.50%
4(7.14%)
E03
20
6(30.00%
0(0.00%)
0(0.00%)
3(15.00%)
E04
2(10.00%)
3(15000%)
0(0.00%)
4(20.00%)
E05
30
5(16.67%)
6(20.00%)
8(26.67%)
5(16.67%)
E06
90
4(4.44%)
36(40.00%)
54(60.00%
42(46.67%)
E07
90
3(3.33%)
18(20.00%)
13(14.44%)
7(7.78%)
EOS
90
12(13.33%)
39(43.33%
37(41.11%)
56(62.22%)
E09
10(11.11%)
38(42.22%
61(67.78%)
35(38.89%)
E10
90
6(6.67%)
0(0.00%)
7(7.78%)
14(15.66%)
L01
90
0(0.00%
52(57.78%)
55(61.11%%
38(42.22%
L02
90
1(1.11%
15(16.67%)
25(27.78%)
8(8.89%)
L03
90
0(0.00%
0(0.00%)
0(0.00%)
((0.00%)
LO4
90
0(0.00%)
4(4.44%)
10(11.11%)
4(4.44%)
LO5
90
0(0.00%)
1(1111%)
2(2.22%)
0(0.00%)
L06
90
9(10.00%
0(0.00%)
0(0.00%)
6(6.67%)
L07
90
11(12.22%)
5(5.56%)
0(0.00%)
7(7.78%)
L08
0(0.00%)
0(0.00%)
0(0.00%)
((0.00%)
L09
90
0(0.00%)
2(2.22%
0(0.00%)
0(0.00%)
L10
0(0.00%)
((0.00%)
0(0.00%)
0(0.00%)
23

---

Under review as a conference paper at ICLR 2022
Table 12: Model comparison for each subcategory of bigger analogy test
num
WV
WV+ + MLP
WV + MLP.C
WV + AGN
101
90
53(8.899%
5(5.6%%
11(12.22%)
55(61.11%% 1))
I02
90
42(46.67%
0(0.00%)
9(10.00%)
30(33.33%
I03
90
86995.66%
22(24.44%)
20(22.22%)
73(81.11%)
I04
90
68(75.56%
18(20.00%)
26(28.89%
64(71.11%)
105
90
(17.778%%
58(64.44%)
55(61.11%)
61
106
90
(9(76.67%
13(14.44%)
26(28.89%)
71(78.89%
107
90
52(57.78%)
55(61.11%)
42(46.67%)
68(75.56%
108
90
56(62.22%
42(46.67%
51(66.67%
69(76.67%
I09
90
58(6444%)
50(55.66%)
63(7..00%)
85(9444%
I10
90
69(76.67%)
61(677788)
66(73.33%)
80188.89%
D01
90
0(0.00%)
(00.0%%
0(0.00%
0(0.00%
D02
90
(3333%%
(3.33%%
000.00%)
2(2.22%)
D03
90
89%
2(222%%
910.00%%
15(16.67%)
DO4
90
11(12.22%
0(0.00%)
00.00%%
3(3.33%
DO5
72
(29.1117%
2(2.78%)
13(18.06%)
17(23.61%)
D06
90
13(14.44%)
((2.2%%)
10(11.11%)
19(21.11%
DO7
90
1(1.11%)
0(0.00%)
0(0.00%)
4(4.44%)
DO8
90
1(1.11%)
4(4.44%)
1(1.11%)
2(2.22%
D09
90
21(23.33%)
0(0.00%)
910.00%%
24(26.67%
D10
90
6(6.67%)
4(4.44%)
1(1111%)
12(13.33%
E01
56
18(32.14%)
00000%%
1(1.79%)
5(8.93%)
E02
56
0(0.00%)
14(25.00%)
19(39.93%
4(7.14%
E03
20
0(0.00%
0(0.0%%
(
0(0.00%
E04
20
0(0.00%)
3(15.00%)
0
4(20.00%
E05
30
0(0.00%)
6(20.00%)
6(20.00%)
2(6.67%)
E06
90
5(5.56%)
33(6.667%
51(6.667%
47(52.22%
E07
90
3(3.33%)
17(18.89%
12(13.33%)
19(21.11%
E08
90
2(2.22%)
40(44.44%
35(38.89%
53
E09
90
12(13.33%)
38(42.22%)
67(.33))%
33(36.67%)
E10
90
43(47.78%
0(0.00%)
7(7.78%)
38(42.22%
L01
90
7(7.78%)
48(53.33%
50(55.56%
51
L02
90
3(3.33%)
15(16.67%
(5.27.78%
17(18.89%
L03
90
3(3.33%
0(0.00%)
0
((2.2%%
LO4
90
1(1.11%)
3(3333%)
9(1.00%)
5(5.56%)
LO5
90
1(1.11%)
1(1111%)
2(2.22%)
1(1.11%
L06
90
0(0.00%
0(0.00%)
0(0.00%)
1(1.11%)
L07
90
12(13.33%
4(4.44%)
0(0.00%)
2(2.22%
L08
90
27(30.00%
0(0.00%)
0(0.00%)
17(18.89%)
L09
90
2(2.22%)
5(5.56%)
0(0.00%)
5(5.56%
L10
90 8(8.89%
1(1111%)
0(0.00%)
5(5.56%)
24

---

Under review as a conference paper at ICLR 2022
Table 13: Model comparison for each subcategory of Google analogy test set.
num
WV
WV + MLP
WV MLP
WV + AGN
copital-common....
506
225
((0.00%)
0(0.00%)
227(44.86%%
capital-wordd
4524
1168(25.829))
0(0.00%)
0(0.00%)
1223(27.08%)
currency
866
185(21.36%)
0(0.00%)
0(0.00%)
119(13.74%)
city-in-state
2467
252(10.21%)
0(0.00%)
0(0.00%)
350(14.19%
family
506
165(32.61%)
161(31.82%)
256(50.59%)
341(67.399)
graml-adjective...
992
15(1.51%)
86(8.67%)
156(15.73%
84(8.47%)
gram2-opposite
812
14(1.22%)
200(24.63%)
286(35.22%)
235 22.99%
gram3-comparati...
1332
(29.77%70%
242(18.17%)
433(32.51%)
713(53.53%
gram4-superlati...
1122
124(11.05%)
244(21.75%)
311(27.72%)
406(36.19% 19%
grams-present-p...
1056
73(6.91%)
71(6.72%%
219(20.74%)
160(15.15%)
gram6-nationali...
1599
1180 80%
0(0.00%)
0(0.00%)
196(62.299)
gramt-past-tens...
1560
134(8.59%)
127(8.14%)
252(16.15%)
353 (2%.6%%))
gram8-plural
1332
63(4.73%)
82(6.16%)
92(6.91%%
176(13.21%
gram9-plural-ve...
870
(06(18)))%)
(15.292)9%
217(24.94%)
593(33.68%
Table 14: Model comparison for each subcategory of Google analogy test set.
num
WV
WV + MLP
WV + MIP.C WV AGN
capital-common....
506
421 20%%
0(0.00%)
0(0.00%)
378(74.70%)
capital-world
4524
3580(79. 13%) 13%)
0(0.00%)
0(0.00%)
2689(59.44%)
currency
866
304
0(0.00%)
0(0.00%)
180(20.79%)
city-in-state
2467
1749(70.90%
0(0.00%)
0(0.00%)
1223(49.57%
family
506
428(84.58%)
163(32.21%)
256(50.59%
448(88.54%
grami-adjective...
992
283 (23628553 .3%%)
93(9.38%)
162(16.33%)
283(28.53%)
gram2-opposite
812
347(42.73%)
(24
299(36.82%
419(51.60%
gram3-comparati...
1332
1210(90.84%)
248(18.62%
(37(32.81%)
1044(78.38%)
gram4-superlati..
1122
980(87.34%)
246(21.93%)
319 43%
777 256...55%
gramS-present-p...
1056
825(78.12%)
78(7.39%)
298(28. 22%
729
gram6-nationali..
1599
1438(89.93%)
0(0.00%)
0(0.00%)
1158
gram7-past-tens....
1560
1029(65.96%)
157(10.06%)
283(18.14%)
1061 01%)
gram8-plural
1332
1197
103(7.73%)
122(9.16%)
826(62.01%)
grame-plural-ve...
870
591 (67.939)%
138(15.86%)
238(27.36%)
242(73.1H 79..7%
25


Reviews:
[{"review_id": "zg-1QpN4Ujn", "reviewer": "Reviewer_aHe9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the paper is generally reasonably clear, I feel that it takes a long time to get to the main idea, which is on page 5-6 of 9. The preliminaries (some of which are not actually used until the Appendix, I believe), related work, and elementary proofs on page 5, take up quite a lot of space.\n\nSo it's surprising to me that in the methods section, \\phi, a critical component of the model, is left undefined. Its definition does not come until the bottom of page 7, in the experiments section, and even then, the definition is not an equation, but just the name of the network (Glow) and a citation.\n\nCould you explain why commutativity is needed to model word analogies? Even if \\circ is noncommutative, wouldn't you still have the property that a = b -> f(a,b,c) = c and a = c -> f(a,b,c) = b?\n\nYou write: “We mitigate this issue [of eliminating a, b, and c from the candidate set] by learning richer functions than addition and subtraction.\" But this seems to be not borne out by the experiments, where WV+AGN benefit greatly from eliminating a, b, and c from the candidate set, while WV+MLP and WV+MLP_C do not.\n\nOn the Google analogy test set, the proposed model does not outperform WV. You write: “This is probably because the word2vec model was highly tuned for the Google analogy test set for this evaluation method.\" While this is possible, do you have a citation or evidence for this claim?\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper describes a simple and interesting method for modeling unordered data that has some nice theoretical properties, like generalization from smaller to larger sets. However, it is applied to only one problem, the word analogy problem, where the sets are always of size 3 and the importance of commutativity could be made more clear. Experimental results are mixed, with the proposed model performing the best on BATS but not on the Google analogies dataset.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_zMkNt4xXlh", "reviewer": "Reviewer_uoK8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The approach is motivated well, the proposed abelian network is very interesting and could have applications for other tasks. \n2. The paper is written well and is very easy to follow\n\nWeaknesses:\n\nThe experimental setup seems quite weak:\n1. The authors only consider only word embedding setup (word2vec) which is several years old and many other better-performing embeddings (on word analogy task) have since been proposed such as fasttext or glove.\n2. Even with word2vec, the proposed approach only outperforms baselines in a specific case (where we exclude query words from the candidate set). \n3. Why is this problem interesting in itself? A side effect of learning unsupervised word embeddings was they perform well on word analogies, however, it is not clear why training of this specific task is important. Does that improve the embeddings for any downstream tasks where they can be used?\n\n---- \n\nUpdated the score from 5 to 6 after rebuttal\n", "summary_of_the_paper": "This paper presents a method of learning word analogies by training a network to explicitly model analogical relationships using an architecture based on invertible projections, which they show induces an abelian group on the input space. With a supervised setup using a training set of word analogies, the paper shows improvements over baselines that do not model this structure.", "summary_of_the_review": "While the presented premise and the theory of abelian neural networks is quite interesting and may have interesting applications, the experimental section seems weak and needs additional results/motivation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OKDej8p80ia", "reviewer": "Reviewer_ezJt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Pros\n- Novel interesting idea of explicitly incorporating Abelian relation prior into neural networks.\n- Theoretical proofs for the claimed properties regarding the AGN's ability to model Abelian relations and multisets.\n\n### Cons\n- Insufficient empirical evidence that AGN will help certain kinds of learning tasks in a realistic setting. The current evaluation is restricted to the word analogy task and does not show a definitive gain under practical settings. The strengths of the MLP baselines are questionable. Important details missing. See questions below and localized points below (Table 2-6).\n\nI think the authors could improve the strength of the work by any of the following.\n1) Looking for better tasks that can showcase the benefit of modeling Abelian relation explicitly. The arithmetic relation between word pairs is thought to be an emergent property of the popular word vector learning objectives. In other words, it may already be well-modeled by word vectors and thus AGN does not give a further advantage. At least a discussion about possible applications to a wide range of tasks would show the proposal has a greater impact.\n2) Showing that AGN indeed gives a notable boost to word analogy in a practical setting. For example, not when WV is weakened when a, b, c are present (Table 2,4,6). Those words can easily be excluded in practice. I think Table 3 gives positive results but there are numbers in that table that seem off to me, which leads to the next point.\n3) Making sure the experimental settings are described well and all the interesting/unusual observations from the results are addressed. For example, why would accuracy drop when excluding a, b, c, in Table 3? Why are MLPs so bad in Table 6? Those unusual observations may be related to problematic settings/processes, or unrealized behaviors/findings. In either case, it will be worth examining.\n4) Comparing to competitive baselines. WV is an attested and competitive baseline. However, MLPs used in the paper seem to be particularly poor. Especially, why would they be poorer than WV (Table 3, 4, 5, 6) when they are built on top of WV? I think this suggests there is something wrong with the design and/or training. Thus, we don't really know if AGN has an advantage over MLP.\n5) Showing AGN is advantageous in other aspects, e.g. interpretability, rather than focusing only on accuracy.\n\n### Questions to the Authors\n1) What is exactly the neural network architecture used in the experiments?\n2) What are the authors' thoughts or plans in applying/experimenting AGN for other tasks / in other settings?\n3) Localized points below for Table 2-6.\n\n### Localized Points\n1) Eq (5). Are w^{(k, j)}, b^{(k, j)} for 1 <= k <= K, 1 <= j <= J_k all trainable parameters?\n2) End of P7. Worth explaining what is \"the Glow architecture\" used here.\n3) Table 2. The competitive results for MLP_C suggest a simple linear underlying relation between embedding vectors. All the extra theory and design may be overkill.\n4) Table 3. Compared to Table 2, for example, the last two numbers of MLP_C, I don't understand why there can be a drop? I think removing words a, b, c would only help? Are they cases where the correct answer is one of the words a, b, c, such as \"split: split\"? If that is the case, we should probably remove impossible queries or at least make a remark on the existence and frequency of such cases. \n5) Table 4 and 5. The numbers make it seems like the benefit of AGN is to reduce confusion from a, b, c. However, we can easily exclude them in downstream applications.\n6) After Table 5. \"This is probably because the word2vec model was highly tuned for the Google analogy test set for this evaluation method.\" Do we have a better dataset, or even a better task, to showcase the benefit of the proposed approach?\n7) Table 6, \"we enumerated the answers of each model for some toy example relations\". How are the examples chosen? Random? Or by some criteria? \n8) Table 6, the first half. This may be a nice verification for the theoretical property, but it is hardly helpful in practice: one can write some simple logic to give the right answer for \"a:a = b:?\" queries.\n9) Table 6, the second half. WV does just as perfect as AGN, so it does not particularly show an advantage. MLP and MLP_C failed completely. The comparison does not seem to support AGN is better, but rather there is something really bad happening with MLP and MLP_C and makes one doubt the legitimacy of them as competitive baselines. \n10) After Table 6. \"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.\" I feel it impresses more as if we should put a better effort into designing and tuning baseline MLPs. Why are they giving nonsensical predictions while still making reasonable numbers in previous tables?", "summary_of_the_paper": "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.", "summary_of_the_review": "Novel and interesting idea of adding explicit Abelian constraints into neural networks with proofs that AGN is able to model Abelian relations. However, the scope is limited to word analogy and experimental results do not provide good support that AGN is advantageous than word vectors and MLPs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider an interesting approach for modeling analogical relations through Abelian group networks. While the conceptual contributions in the work, the explicit introduction of Abelian relations in particular, were generally appreciated, the reviewers found the numerical results provided in the paper lacking. In addition, several issues regarding the scope of the problems to which the proposed approach applies have been raised. Thus, given this, and the exchanges between the reviewers and the authors, in its present form, the paper cannot be recommended for acceptance. The authors are encouraged to incorporate the valuable feedback provided by the knowledgeable reviewers.
Decision: Reject