# Flasque Meadows

João Dias  and  Bruno Dinis  Departamento de Matemática, Universidade de Évora
<EMAIL_ADDRESS>Departamento de Matemática, Universidade de Évora
<EMAIL_ADDRESS>
###### Abstract.

In analogy with flasque sheaves, we introduce the notion of flasque meadow as
a common meadow where the transition maps are all surjective. We study some
properties of flasque meadows and illustrate them with many examples and
counterexamples.

###### Key words and phrases:

Flasque meadows, rings, directed lattices

###### 2010 Mathematics Subject Classification:

16U90, 06B15, 13B10

##  1\. Introduction

The notion of common meadow has gained some attention lately due to recently
discovered connections with ring theory and with nonstandard analysis [10, 13,
14, 12, 15] (see also [8, 9] for other recent developments). Originally
introduced by Bergstra and Tucker in [1], _meadows_ are algebraic structures
with two operations, addition and multiplication, where both operations have
inverses which are total. This implies in particular that one is allowed to
divide by zero. The original idea was to view meadows as abstract data types
given by equational axiomatizations [3, 5, 6, 2]. The point is that one is
then able to obtain simple term rewriting systems which are easier to automate
in formal reasoning [2, 7]. However, and as mentioned above, meadows are also
algebraic structures whose study has interest on its own. For our purposes,
two different kinds of meadows are particularly relevant: _common meadows_ ,
introduced by Bergstra and Ponse in [4] and _pre-meadows with $\mathbf{a}$_,
introduced by the authors in [13]. In these classes of meadows the inverse of
zero is an element, denoted $\mathbf{a}$, which is absorbent for both
operations. The interesting feature of these two classes is that they can be
decomposed as disjoint unions of rings [13], which allows to adapt many of the
results of ring theory onto them. Pre-meadows with $\mathbf{a}$ differ from
common meadows as the former do not require the existence of an inverse
function. This turns out to be crucial in trying to enumerate finite common
meadows [14]. The two structures are nevertheless related since $P$, a pre-
meadow with $\mathbf{a}$ such that $0\cdot P$ is finite and the partial order
in $0\cdot P$ is a total order, is actually a common meadow.

In this paper we introduce a new class of meadows, called _flasque meadows_ ,
inspired by a recently discovered connection between meadows and sheaves [15].
The term _flasque_ originates from Sheaf Theory, where a sheaf is said to be
flasque if the restriction maps are surjective [19, p. 67]. Flasque sheaves
have the nice property of preserving some exact sequences. We study some basic
properties of flasque meadows and illustrate them with many examples and
counterexamples.

##  2\. Preliminaries

In this section we recall some definitions and results on common meadows.

######  Definition 2.1.

A _pre-meadow_ is a structure $(P,+,-,\cdot)$ satisfying the following
equations

  1. $(P_{1})$

$(x+y)+z=x+(y+z)$

  2. $(P_{2})$

$x+y=y+x$

  3. $(P_{3})$

$x+0=x$

  4. $(P_{4})$

$x+(-x)=0\cdot x$

  5. $(P_{5})$

$(x\cdot y)\cdot z=x\cdot(y\cdot z)$

  6. $(P_{6})$

$x\cdot y=y\cdot x$

  7. $(P_{7})$

$1\cdot x=x$

  8. $(P_{8})$

$x\cdot(y+z)=x\cdot y+x\cdot z$

  9. $(P_{9})$

$-(-x)=x$

  10. $(P_{10})$

$0\cdot(x+y)=0\cdot x\cdot y$

Let $P$ be a pre-meadow and let $P_{z}:=\\{x\in M\mid 0\cdot x=z\\}$. We say
that $P$ is a _pre-meadow with $\mathbf{a}$_ if there exists a unique $z\in
0\cdot P$ such that $|P_{z}|=1$ (denoted by $\mathbf{a}$) and
$x+\mathbf{a}=\mathbf{a}$, for all $x\in P$. A _common meadow_ is a pre-meadow
with $\mathbf{a}$ equipped with an inverse function $(\cdot)^{-1}$ satisfying

  1. $(M_{1})$

$x\cdot x^{-1}=1+0\cdot x^{-1}$

  2. $(M_{2})$

$(x\cdot y)^{-1}=x^{-1}\cdot y^{-1}$

  3. $(M_{3})$

$(1+0\cdot x)^{-1}=1+0\cdot x$

  4. $(M_{4})$

$0^{-1}=\mathbf{a}$

######  Example 2.2.

  1. (1)

The set $P=\\{0,1,x,\mathbf{a}\\}$ with the operations

$+$ | $0$ | $1$ | $x$ | $\mathbf{a}$
---|---|---|---|---
$0$ | $0$ | $1$ | $x$ | $\mathbf{a}$
$1$ | $1$ | $0$ | $x$ | $\mathbf{a}$
$x$ | $x$ | $x$ | $x$ | $\mathbf{a}$
$\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$
$\cdot$ | $0$ | $1$ | $x$ | $\mathbf{a}$
---|---|---|---|---
$0$ | $0$ | $0$ | $x$ | $\mathbf{a}$
$1$ | $0$ | $1$ | $x$ | $\mathbf{a}$
$x$ | $x$ | $x$ | $x$ | $\mathbf{a}$
$\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$

is a pre-meadow but not a pre-meadow with $\mathbf{a}$ since, the fact that
$|P_{x}|=1=|P_{\mathbf{a}}|$ would entail $x=\mathbf{a}$.

  2. (2)

The set $M=\\{0,1,x,y,\mathbf{a}\\}$ with the operations

$+$ | $0$ | $1$ | $x$ | $y$ | $\mathbf{a}$
---|---|---|---|---|---
$0$ | $0$ | $1$ | $x$ | $y$ | $\mathbf{a}$
$1$ | $1$ | $0$ | $y$ | $x$ | $\mathbf{a}$
$x$ | $x$ | $y$ | $x$ | $y$ | $\mathbf{a}$
$y$ | $y$ | $x$ | $y$ | $x$ | $\mathbf{a}$
$\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$
$\cdot$ | $0$ | $1$ | $x$ | $y$ | $\mathbf{a}$
---|---|---|---|---|---
$0$ | $0$ | $0$ | $x$ | $x$ | $\mathbf{a}$
$1$ | $0$ | $1$ | $x$ | $y$ | $\mathbf{a}$
$x$ | $x$ | $x$ | $x$ | $x$ | $\mathbf{a}$
$y$ | $x$ | $y$ | $x$ | $y$ | $\mathbf{a}$
$\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$ | $\mathbf{a}$

is a pre-meadow with $\mathbf{a}$. Indeed, $M_{0}=\\{0,1\\}$,
$M_{x}=\\{x,y\\}$ and $M_{\mathbf{a}}=\\{\mathbf{a}\\}$. Moreover, $M$ becomes
a common meadow by making $1^{-1}=1$, $y^{-1}=y$, and
$0^{-1}=x^{-1}=\mathbf{a}^{-1}=\mathbf{a}$.

A _directed lattice of rings_ is a lattice where the vertices are labelled by
unital commutative rings and the edges are labelled by ring homomorphisms.

In [13] a connection between meadows and directed lattices was unveiled (see
Theorem 2.4 below) which allows to represent meadows in a diagram form. We
illustrate this with the following example.

######  Example 2.3.

Consider the lattice $L$ over the set $\\{1,2,3,4\\}$ (on the left)

${0}$${{(\mathbb{Z})_{0}}}$${1}$${2}$${{(\mathbb{Z}_{2})_{1}}}$${{(\mathbb{Q})_{2}}}$${3}$${{(\mathbb{R})_{3}}}$${4}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\pi}$$\scriptstyle{\iota_{1}}$$\scriptstyle{\iota_{2}}$

A directed lattice of rings $\Gamma=\bigsqcup\Gamma_{i}$ over $L$ is a
labeling of the vertices by unital commutative rings $R_{i}$ and of the arrows
by unital ring homomorphisms.

Here (on the right), $\pi$ is the projection homomorphism to the quotient
$\mathbb{Z}/(2)\simeq\mathbb{Z}_{2}$, and $\iota_{1},\iota_{2}$ are the
inclusion homomorphisms (note that $\iota_{2}\circ\iota_{1}$ is the inclusion
map of $\mathbb{Z}$ into $\mathbb{R}$). The unlabelled arrows correspond to
the unique map that exists to the trivial ring, that we denote by
$\\{\mathbf{a}\\}$, which we usually omit since it is unique. Throughout the
paper we will also drop the lattice indices.

We now recall the main result from [13], linking rings and common meadows. The
set of invertible elements of the ring $R$ is denoted $R^{\times}$.

######  Theorem 2.4 ([13, Theorem 3.3]).

Let $L$ be a lattice and $\Gamma$ a directed lattice of rings over $L$ such
that, for all $i$ in a set of indices $I$ and all $x\in\Gamma_{i}$ the set:

$J_{x}:=\\{j\in I\mid f_{j,i}(x)\in\Gamma_{j}^{\times}\\}$

has a greatest element. Then, there exists a common meadow $M=\bigsqcup_{i\in
L}\Gamma_{i}$ with the operations

  * •

$x+_{M}y=f_{i\wedge j,i}(x)+_{i\wedge j}f_{i\wedge j,j}(y)$, where $+_{i\wedge
j}$ is the sum in $\Gamma_{i\wedge j}$;

  * •

$x\cdot_{M}y=f_{i\wedge j,i}(x)\cdot_{i\wedge j}f_{i\wedge j,j}(y)$, where
$\cdot_{i\wedge j}$ is the product in $\Gamma_{i\wedge j}$.

such that the lattice $0\cdot M$ is equivalent to $L$.

The following corollary is useful to show immediately that certain directed
lattices are common meadows, since it entails that if all the vertices of the
associated lattice of a pre-meadow with $\mathbf{a}$ are fields, then it must
be a common meadow.

######  Corollary 2.5 ([12]).

Every $P$, pre-meadow with $\mathbf{a}$ such that $P_{0\cdot z}$ is a field,
for all $0\cdot z\in 0\cdot P$, is a common meadow.

######  Example 2.6.

Recall that for $p$ prime, there exists a unique field $\mathbb{F}_{p^{n}}$
with exactly $p^{n}$ elements. Also, the field $\mathbb{F}_{p^{n}}$ is an
algebraic extension of $\mathbb{F}_{p^{m}}$ whenever $m|n$. Consider the
following directed lattice

${{\mathbb{F}_{p}}}$${{\mathbb{F}_{p^{2}}}}$${{\mathbb{F}_{p^{3}}}}$${{\mathbb{F}_{p^{5}}}}$${\cdots}$${{\mathbb{F}_{p^{6}}}}$${{\mathbb{F}_{p^{10}}}}$${{\mathbb{F}_{p^{15}}}}$${\cdots}$${\cdots}$${\cdots}$${\cdots}$${\cdots}$${{\\{\mathbf{a}\\}}}$

We have that $M=\bigsqcup_{n\in\mathbb{N}}\mathbb{F}_{p^{n}}$ is a common
meadow, by Corollary 2.5.

##  3\. Flasque Meadows

As shown in [12, Proposition 3.4], there exists a class of common meadows $M$
which is completely determined by $M_{0}$. We will see (in Proposition 3.7)
that in the class of pre-meadows with $\mathbf{a}$ a similar phenomenon
occurs. We recall that, given a pre-meadow $P$, the transition maps of $P$ are
ring homomorphisms $f_{0\cdot w,0\cdot z}:P_{0\cdot w}\to P_{0\cdot z}$. If
the maps are surjective, then $P_{0\cdot w}/\ker(f_{0\cdot w,0\cdot z})$ is
isomorphic to $P_{0\cdot z}$. The case where the maps are surjective is of
great interest since, in that case, $P_{0}$ defines the entire meadow.

######  Definition 3.1.

Let $P$ be a pre-meadow with $\mathbf{a}$. We say that $P$ is _flasque_ if for
all $0\cdot z,0\cdot w\in 0\cdot P$ the transition maps $f_{0\cdot w,0\cdot
z}:P_{0\cdot w}\to P_{0\cdot z}$ are surjective.

The first examples of flasque pre-meadows are the pre-meadows with
$\mathbf{a}$ constructed from a ring, i.e. of the form

(1) $M(R):=\bigsqcup_{I\trianglelefteq R}R/I,$

for some unital commutative ring $R$ (see [12] for more on this class of
meadows).

######  Example 3.2.

The directed lattice

${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\mathrm{Id}_{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$

where the maps $\pi_{1}$ and $\pi_{2}$ are the projection maps on the first
and second coordinates, respectively, defines a flasque common meadow.

######  Example 3.3.

Consider the ring $\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}$.
The directed lattice of rings associated with $M(R)$ is

${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(0\times
0\times\mathbb{Z}_{5})}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(0\times\mathbb{Z}_{3}\times
0)}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(\mathbb{Z}_{2}\times
0\times
0)}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(0\times\mathbb{Z}_{3}\times\mathbb{Z}_{5})}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(\mathbb{Z}_{2}\times
0\times\mathbb{Z}_{5})}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times
0)}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}/(\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5})}}$

which is equivalent to

${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}\times\mathbb{Z}_{5}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{3}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{5}}}$${{\mathbb{Z}_{3}\times\mathbb{Z}_{5}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{3}}}$${{\mathbb{Z}_{5}}}$${{\\{\mathbf{a}\\}}}$

Where the transition maps are the natural quotient homomorphisms.

######  Counterexample 3.4.

  1. (1)

Not all flasque pre-meadow with $\mathbf{a}$ are common meadows. Indeed, the
pre-meadow with $\mathbf{a}$ associated with the following directed lattice is
not a common meadow

${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{\mathrm{Id}_{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{1}}$

.

  2. (2)

Not all common meadows are flasque. Indeed the directed lattice

${\mathbb{Z}}$${{\mathbb{R}\times\mathbb{R}}}$${\mathbb{R}}$${\mathbb{R}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{1\mapsto(1,1)}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$

is associated with a common meadow. However this meadow is not flasque since
the map $1\mapsto(1,1)$ fails to be surjective.

######  Proposition 3.5.

Let $R$ be a commutative ring. Then $M(R)$ is a flasque pre-meadow with
$\mathbf{a}$.

###### Proof.

Since the transition maps are projections from $R/I$ to $R/J$ with $I\subseteq
J$ then they are surjective, and so $M(R)$ is flasque. ∎

We now give an alternative condition for a pre-meadow with $\mathbf{a}$ to be
flasque.

######  Proposition 3.6.

Let $P$ be a pre-meadow with $\mathbf{a}$ then the following are equivalent:

  1. (1)

for all $0\cdot z,0\cdot w\in 0\cdot P$ the transition map $f_{0\cdot w,0\cdot
z}:P_{0\cdot w}\to P_{0\cdot z}$ is surjective.

  2. (2)

for all $0\cdot z\in 0\cdot P$ the transition map $f_{0,0\cdot z}:P_{0}\to
P_{0\cdot z}$ is surjective.

###### Proof.

The implication $(1)\Rightarrow(2)$ is obvious.

Assume that for all $0\cdot z\in 0\cdot P$ the transition map $f_{0,0\cdot
z}:P_{0}\to P_{0\cdot z}$ is surjective. Let $0\cdot z,0\cdot w\in 0\cdot P$.
We have that $f_{0\cdot z}=f_{0\cdot w,0\cdot z}\circ f_{0\cdot w}$ is
surjective, so $f_{0\cdot w,0\cdot z}$ is also surjective. ∎

If $P$ is a flasque pre-meadow with $\mathbf{a}$, then $P$ is determined by
$P_{0}$ and the lattice structure of $0\cdot P$. The following proposition
reflects this fact.

######  Proposition 3.7.

Let $P$ be a flasque pre-meadow with $\mathbf{a}$. Then $P=P_{0}+0\cdot P$.

###### Proof.

By Proposition 3.6, for all $x\in P$ there exists some $y\in P_{0}$ such that
$x=y+0\cdot x$. Then $P\subseteq P_{0}+0\cdot P$, and so $P=P_{0}+0\cdot P$ as
we wanted. ∎

As a consequence of Proposition 3.7, every $P$, a flasque pre-meadow with
$\mathbf{a}$, decomposes into the sum of a ring $P_{0}$ with a lattice $0\cdot
P$. Moreover, if $P$ is a flasque pre-meadow with $\mathbf{a}$ and $P_{0}$ is
a field, then $P$ must be a common meadow, by Proposition 3.6.

######  Theorem 3.8.

Let $M$ be a common meadow. Then $M^{\prime}=M_{0}\times(0\cdot
M\setminus\\{\mathbf{a}\\})\sqcup\\{\mathbf{a}\\}$, with the operations

$\begin{cases}(x,0\cdot z)+(y,0\cdot w)=(x+y,0\cdot z\cdot w)\\\ (x,0\cdot
z)\cdot(y,0\cdot w)=(x\cdot y,0\cdot z\cdot w),\end{cases}$

where $(x,0\cdot z),(y,0\cdot w)\in M^{\prime}$, is a common meadow. In
particular, if $M$ is flasque and such that $M_{0}$ is a field, then $M$ is
isomorphic to $M^{\prime}$.

###### Proof.

Since $(M_{0},+,\cdot)$ is a ring and $0\cdot M$ is a semigroup, both
operations are associative on $M^{\prime}$. Let $(x_{i},0\cdot z_{i})\in
M^{\prime}$, with $i=1,2,3$. Then

$\displaystyle(x_{1},z_{1})\cdot((x_{2},z_{2})+(x_{3},z_{3}))$
$\displaystyle=(x_{1}\cdot(x_{2}+x_{3}),z_{1}\cdot z_{2}\cdot z_{3})=$
$\displaystyle(x_{1}\cdot x_{2}+x_{1}\cdot x_{3},z_{1}\cdot z_{2}\cdot
z_{1}\cdot z_{3})$
$\displaystyle=(x_{1},z_{1})\cdot(x_{2},z_{2})+(x_{1},z_{1})\cdot(x_{3},z_{3})$

and so distributivity holds on $M^{\prime}$. The elements $(0,0)$ and $(1,0)$
are the identity of the sum and the product, respectively. For $(x,z)\in
M^{\prime}$ we have

$(x,z)^{-1}=\begin{cases}(x^{-1},z),\text{ if }x\in M_{0}^{\times}\\\
\mathbf{a},\text{ otherwise}\end{cases}$

The remaining common meadow axioms are easy to very.

If $M$ is a flasque common meadow such that $M_{0}$ is a field, then for all
$0\cdot z\in 0\cdot M$ $M_{0\cdot z}\simeq M_{0}$. Since all surjective
homomorphisms between fields are isomorphisms, the transition maps are all
isomorphisms. Let $\Phi:M^{\prime}\to M$ be the function defined by
$\Phi(x,0\cdot z)=f_{0,0\cdot z}(x)=x+0\cdot z$, where $f_{0,0\cdot z}$ are
the transition maps of $M$. Since all transition maps are isomorphisms, $\Phi$
must be bijective. Let us see that it is in fact an homomorphism of common
meadows. Let $(x,0\cdot z),(y,0\cdot w)\in M^{\prime}$. Then

$\displaystyle\Phi(x,0\cdot z)+\Phi(y,0\cdot w)$ $\displaystyle=x+0\cdot
z+y+0\cdot w=$ $\displaystyle x+y+0\cdot z\cdot w$
$\displaystyle=\Phi(x+y,0\cdot z\cdot w).$

Similarly, one shows that $\Phi(x,0\cdot z)\cdot\Phi(y,0\cdot w)=\Phi(x\cdot
y,0\cdot z\cdot w)$. Also $\Phi(1,0)=1$. Hence $\Phi$ is an isomorphism of
common meadows, and so $M^{\prime}$ is isomorphic to $M$. ∎

######  Example 3.9.

Consider the common meadow $M$ (which is not flasque) associated with the
directed lattice on the left. Then $M^{\prime}$ can be represented by the
directed lattice on the right, where the non-trivial arrows correspond to the
identity function.

  1.   2. ${\mathbb{Z}}$${{\mathbb{Z}\times\mathbb{Z}}}$${\mathbb{Z}}$${\mathbb{Z}}$${\mathbb{R}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{1\mapsto(1,1)}$$\scriptstyle{\mathrm{Id}_{\mathbb{Z}}}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\iota\circ\pi_{2}}$

  3. ${\mathbb{Z}}$${\mathbb{Z}}$${\mathbb{Z}}$${\mathbb{Z}}$${\mathbb{Z}}$${{\\{\mathbf{a}\\}}}$

The proof of Theorem 3.8 also shows that, given a common meadow $M$, there
exists an homomorphism $\Phi:M_{0}\times(0\cdot
M\setminus\\{\mathbf{a}\\})\sqcup\\{\mathbf{a}\\}\to M$ which is surjective if
and only if $M$ is flasque. By [13, Corollary 4.22], it follows that
$M^{\prime}/\ker^{R}(\Phi)$ is isomorphic to $M$.

######  Proposition 3.10.

Let $R$ be a unital commutative ring and $S$ an idempotent commutative monoid
with a zero $\mathbf{a}$. Then
$M=R\times(S\setminus\\{\mathbf{a}\\})\sqcup\\{\mathbf{a}\\}$ with the
operations:

$\begin{cases}(x,a)+(y,b)=(x+y,a\cdot b)\\\ (x,a)\cdot(y,b)=(x\cdot y,a\cdot
b)\\\
(x,a)+\mathbf{a}=\mathbf{a}+(x,a)=(x,a)\cdot\mathbf{a}=\mathbf{a}\cdot(x,a)=\mathbf{a}\end{cases}$

defines a common meadow.

The proof of Proposition 3.10 is similar to the proof of Theorem 3.8 and so it
will be omitted.

Recall that an idempotent commutative monoid $S$ with zero (i.e. with an
absorbent element) is equivalent to a lattice, where $x\leq y$ if $x\cdot y=y$
for $x,y\in S$. The directed lattice associated with the meadow
$M=R\times(S\setminus\\{\mathbf{a}\\})\sqcup\\{\mathbf{a}\\}$ is the lattice
$S$ where each node is replaced by the ring $R$ and all transition maps are
the identity.

######  Example 3.11.

Consider the monoid $S=\\{0,x,y,\mathbf{a}\\}$, where $0$ is the identity, and
$x\cdot y=\mathbf{a}$. The common meadow
$M=(\mathbb{Z}_{2}\times\mathbb{Z}_{2})\times(S\setminus\\{\mathbf{a}\\})\sqcup\\{\mathbf{a}\\}$
is associated with the following directed lattice

${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${\\{\mathbf{a}\\}}$$\scriptstyle{\mathrm{Id}}$$\scriptstyle{\mathrm{Id}}$

Given an ideal $I$ of $M$, the quotient meadow $M/I$ (see [13, Section 4] for
more on quotients of meadows) is a flasque pre-meadow with $\mathbf{a}$ which
is not necessarily a common meadow. Indeed, taking for instance the ideal
$I=\\{((0,0),0),((0,1),x),((0,1),y),\mathbf{a}\\}$, the quotient $M/I$ is not
a common meadow, while the quotient $M/J$ by the ideal
$J=\\{((0,0),0),((0,1),x),((1,0),y),\mathbf{a}\\}$ is in fact a common meadow.

Another consequence of the proof of Theorem 3.8 is that if $S$ is not
idempotent then $M=R\times(S\setminus\\{\mathbf{a}\\})\sqcup\\{\mathbf{a}\\}$
is a structure similar to a common meadow. However this structure is not
distributive. In fact we have

$(x,a)\cdot(y,b)+(x,a)\cdot(z,c)=(x,a)\cdot((y,b)+(z,c))+(0,a),$

and so distributivity holds up to a factor $(0,a)$. The fact that
distributivity holds up to a correcting term resembles what happens with the
so called _neutrices_ and in Nonstandard Analysis (see [21, 18]). Neutrices
are convex additive subgroups of the hyperreal numbers, for example the set of
all infinitesimals. Neutrices have also been studied from a purely algebraic
point of view, giving rise to the notions of _assembly_ , _association_ and
_solid_ , which are algebraic structures111These structures are related with
usual algebraic structures, but are flexible in the sense that by having
individualized neutral elements become stable under some (but not all)
translations and shifts. For this reason, some authors have dubbed them
“flexible” (see e.g. [20]). More recently, assemblies have been shown to be
unions of groups and can therefore be seen as semigroups [11]. This connection
was also the inspiration to establish common meadows as unions of rings. that
possess individualized neutral elements. These can also be seen as
“generalized zeros” and appear in the distributivity formula as correction
terms, since distributivity does not hold in general (see [16, 17]). The paper
[10] is a first attempt at connecting the two ideas, but a proper connection
is still to be done.

By Theorem 2.4, a pre-meadow $P$ is a common meadow if and only if for all
$x\in P$ the set $J_{x}=\\{0\cdot z\in 0\cdot P\mid x+0\cdot z\in P_{0\cdot
z}^{\times}\\}$ has a greatest element. That is, the study of the elements of
the set $J_{x}$ allows to check if a pre-meadow with $\mathbf{a}$ is a common
meadow. In general, this task is somewhat difficult. The next theorem gives a
characterization, for flasque common meadows, which is easier to verify in
practice. Indeed, it shows that, in that case, one only needs to verify the
condition for the elements in $P_{0}$, which should be intuitively obvious
since for flasque meadows $P_{0}$ determines the whole meadow.

######  Theorem 3.12.

Let $P$ be a flasque pre-meadow with $\mathbf{a}$. Then $J_{x}$ has a greatest
element, for all $x\in P$, if and only if it has a greatest element for all
$x\in P_{0}$.

###### Proof.

The direct implication is obvious. Let $x\in P$. If $0\cdot x\in J_{x}$, then
$J_{x}$ has a unique maximal element. So, let us assume that $0\cdot x\notin
J_{x}$. Since $P$ is flasque, there exists some $y\in P_{0}$ such that
$x=y+0\cdot x$. Note that if $J_{x}\subseteq J_{y}$, then
$0\cdot\overline{y}\cdot x\in J_{x}$, where $\overline{y}$ is the greatest
element of $J_{y}$. By the definition of $J_{x}$, for every element $0\cdot
z\in J_{x}$ we have $0\cdot z\leq 0\cdot x$. Since $J_{x}\subseteq J_{y}$ we
also have $0\cdot z\leq 0\cdot\overline{y}$. Hence $0\cdot z\leq
0\cdot\overline{y}\cdot x$, which implies that $0\cdot\overline{y}\cdot x$ is
the greatest element of $J_{x}$. ∎

######  Counterexample 3.13.

In case a pre-meadow with $\mathbf{a}$ is not flasque one is indeed required
to verify the condition of $J_{x}$ having a greatest element, for all $x$. To
see this, consider the pre-meadow with $\mathbf{a}$ defined by the directed
lattice

${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}\times\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\mathbb{Z}_{2}}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{a\mapsto(a,a)}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{1}}$

The elements $x\in P_{0}\simeq\mathbb{Z}_{2}$ all verify that $J_{x}$ has a
greatest element. However, $J_{(1,0)}$ has two distinct maximal elements. So,
the condition fails for an element of
$P_{(0,0)}\simeq\mathbb{Z}_{2}\times\mathbb{Z}_{2}$.

As an application of Theorem 3.12 we will see that there exist non-Artinian
rings $R$ such that $M(R)$ is a common meadow. This provides a positive answer
to a question raised in [12].

######  Example 3.14.

Consider the ring $R=\prod_{n\in\mathbb{N}}\mathbb{Z}_{2}$, consisting of
countably many copies of $\mathbb{Z}_{2}$. Clearly $R$ is not Artinian. Let us
see that $M(R)$ is a common meadow. Since $M(R)$ is flasque (by Proposition
3.5), then by Theorem 3.12 all we need to check that for all $x\in R=M(R)_{0}$
the set $J_{x}$ has a greatest element. To see that, consider
$(a_{n})_{n\in\mathbb{N}}\in R$, and define the element
$(b_{n})_{n\in\mathbb{N}}\in R$ by

$b_{n}=\begin{cases}b_{n}=0,&a_{n}\neq 0\\\ b_{n}=1,&a_{n}=0.\end{cases}$

Then $(a_{n})_{n\in\mathbb{N}}+I$ is invertible in $R/I$ if and only if
$(b_{n})_{n\in\mathbb{N}}\in I$, and so the ideal generated by
$(b_{n})_{n\in\mathbb{N}}$ is the smallest ideal $I$ such that
$(a_{n})_{n\in\mathbb{N}}+I$ is invertible in $R/I$. Then,
$I=((b_{n})_{n\in\mathbb{N}})$ is the greatest element in
$J_{(a_{n})_{n\in\mathbb{N}}}$ and so it is a common meadow by Theorem 2.4.

As shown by Counterexample 3.4, not all pre-meadows with $\mathbf{a}$ are
flasque. However, given a pre-meadow with $\mathbf{a}$ we can consider the
submeadow $P_{0}+0\cdot P$, which is a flasque pre-meadow with $\mathbf{a}$.
In fact, it is the largest flasque pre-meadow with $\mathbf{a}$. We then have

${{P_{0}\times 0\cdot P}}$${{P_{0}+0\cdot P}}$${P}$

where the first map is surjective and the second one is injective. So, given a
pre-meadow with $\mathbf{a}$ we can use the simpler pre-meadows $P_{0}\times
0\cdot P$ and $P_{0}+0\cdot P$ in order to study $P$.

######  Proposition 3.15.

Let $P$ be a pre-meadow with $\mathbf{a}$. Then $\overline{P}=P_{0}+0\cdot P$
is a flasque pre-meadow with $\mathbf{a}$. Additionally, $\overline{P}$ is the
largest flasque submeadow of $P$ with $\overline{P}_{0}=P_{0}$. In particular,
if $P$ is a common meadow then $\overline{P}$ is also a common meadow.

###### Proof.

By construction, one easily checks that $\overline{P}$ is in fact the largest
flasque pre-meadow with $\mathbf{a}$.

Suppose now that $P$ is a common meadow. Since $\overline{P}$ is flasque, by
Theorem 3.12 we have that $\overline{P}$ is a common meadow if and only if for
all $x\in P_{0}$ the set $J_{x}$ has a greatest element. Since $J_{x}\subseteq
0\cdot P=0\cdot\overline{P}$ and $P$ is a common meadow, $J_{x}$ has a
greatest element and so $\overline{P}$ is also a common meadow. ∎

######  Example 3.16.

Let $M$ be the common meadow associated with the following directed lattice of
rings

${\mathbb{Z}}$${{\mathbb{R}\times\mathbb{R}}}$${\mathbb{C}}$${\mathbb{R}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{1\mapsto(1,1)}$$\scriptstyle{\iota\circ\pi_{1}}$$\scriptstyle{\pi_{2}}$

Where $\iota$ is the inclusion map from $\mathbb{R}$ to $\mathbb{C}$. The
meadow $M$ is not flasque since the map $1\mapsto(1,1)$ is not surjective. The
construction of the largest flasque pre-meadow is done by taking the image of
the transition maps. Indeed, the directed lattice

${\mathbb{Z}}$${{\mathbb{Z}\times\mathbb{Z}}}$${\mathbb{Z}}$${\mathbb{Z}}$${{\\{\mathbf{a}\\}}}$$\scriptstyle{1\mapsto(1,1)}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$

is a flasque pre-meadow with $\mathbf{a}$. In this case, it is even a common
meadow.

## References

  * [1] J. Bergstra, Elementary algebraic specifications of the rational function field, in Logical Approaches to Computational Barriers, A. Beckmann, U. Berger, B. Löwe, and J. Tucker, eds., Berlin, Heidelberg, 2006, Springer Berlin Heidelberg, pp. 40–54.
  * [2] , Arithmetical datatypes, fracterms, and the fraction definition problem, Transmathematica, (2020).
  * [3] J. Bergstra, Y. Hirshfeld, and J. Tucker, Fields, Meadows and Abstract Data Types, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 166–178.
  * [4] J. Bergstra and A. Ponse, Division by Zero in Common Meadows, Springer International Publishing, Cham, 2015, pp. 46–61.
  * [5] , Arithmetical datatypes with true fractions, Acta Inform., 57 (2020), pp. 385–402.
  * [6] J. Bergstra and J. Tucker, The rational numbers as an abstract data type, J. ACM, 54 (2007), p. 7–es.
  * [7] , On the axioms of common meadows: Fracterm calculus, flattening and incompleteness, The Computer Journal, 66 (2023), pp. 1565–1572.
  * [8] J. A. Bergstra and J. V. Tucker, Fracterm calculus for signed common meadows, Transmathematica, (2024).
  * [9] J. A. Bergstra and J. V. Tucker, Rings with common division, common meadows and their conditional equational theories, 2024.
  * [10] E. Bottazzi and B. Dinis, Flexible involutive meadows, 2023.  (submitted) arXiv: 2309.01284.
  * [11] U. Dardano, B. Dinis, and G. Terzo, Assemblies as semigroups, Examples and Counterexamples, 5 (2024).
  * [12] J. Dias and B. Dinis, Artinian meadows, 2024.  arXiv: 2407.07793.
  * [13] , Strolling through common meadows, Communications in Algebra, (2024), pp. 1–28.
  * [14] J. Dias and B. Dinis, Towards an enumeration of finite common meadows, International Journal of Algebra and Computation, (2024).
  * [15] J. Dias, B. Dinis, and P. Marques, Meadows as sheaves (in preparation), 2024.
  * [16] B. Dinis and I. van den Berg, Algebraic properties of external numbers, J. Log. Anal., 3:9 (2011), pp. 1–30.
  * [17] B. Dinis and I. van den Berg, Characterization of distributivity in a solid, Indagationes Mathematicae, 29, Issue 2 (2018), pp. 580–600.
  * [18] B. Dinis and I. van den Berg, Neutrices and external numbers: a flexible number system, Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2019.  With a foreword by Claude Lobry.
  * [19] R. Hartshorne, Algebraic geometry, vol. No. 52 of Graduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1977.
  * [20] J. Justino and I. van den Berg, Cramer’s rule applied to flexible systems of linear equations, Electron. J. Linear Algebra, 24 (2012/13), pp. 126–152.
  * [21] F. Koudjeti and I. van den Berg, Neutrices, external numbers, and external calculus, in Nonstandard analysis in practice, F. and M. Diener, eds., Universitext, Springer, Berlin, 1995, pp. 145–170.

### Acknowledgments

Both authors acknowledge the support of FCT - Fundação para a Ciência e
Tecnologia under the project: 10.54499/UIDB/04674/2020, and the research
center CIMA – Centro de Investigação em Matemática e Aplicações.

The second author also acknowledges the support of CMAFcIO – Centro de
Matemática, Aplicações Fundamentais e Investigação Operacional under the
project UIDP/04561/2020.


# Variational Graph Normalized AutoEncoders

Seong Jin Ahn<EMAIL_ADDRESS>KAISTDaejeonRepublic of Korea43017-6221 and
MyoungHo Kim  KAISTDaejeonRepublic of Korea<EMAIL_ADDRESS>
(2021)

###### Abstract.

Link prediction is one of the key problems for graph-structured data. With the
advancement of graph neural networks, graph autoencoders (GAEs) and
variational graph autoencoders (VGAEs) have been proposed to learn graph
embeddings in an unsupervised way. It has been shown that these methods are
effective for link prediction tasks. However, they do not work well in link
predictions when a node whose degree is zero (i.g., isolated node) is
involved. We have found that GAEs/VGAEs make embeddings of isolated nodes
close to zero regardless of their content features. In this paper, we propose
a novel Variational Graph Normalized AutoEncoder (VGNAE) that utilize
$L_{2}$-normalization to derive better embeddings for isolated nodes. We show
that our VGNAEs outperform the existing state-of-the-art models for link
prediction tasks. The code is available at
https://github.com/SeongJinAhn/VGNAE.

Link Prediction, Graph Embedding, Graph Convolutional Networks, Normalization

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
30th ACM International Conference on Information and Knowledge Management;
November 1–5, 2021; Virtual Event, QLD, Australia††booktitle: Proceedings of
the 30th ACM International Conference on Information and Knowledge Management
(CIKM ’21), November 1–5, 2021, Virtual Event, QLD, Australia††price:
15.00††doi: 10.1145/3459637.3482215††isbn: 978-1-4503-8446-9/21/11††ccs:
Computing methodologies Neural networks††ccs: Computing methodologies
Unsupervised learning††ccs: Computing methodologies Learning latent
representations

##  1\. Introduction

Link prediction in the graph is to determine whether there is an unknown
relationship between nodes in the incomplete original graph. For example, it
can be used to predict a link indicating if a specific substance in a
biological network has a positive effect on the treatment of a specific
disease, or if a specific literature or patent belongs to a certain author.

With the advancement of deep learning techniques, graph embedding models have
been widely used in solving various problems in graphs. Graph embedding models
generate low-dimensional vectors for nodes in the graph, called node
embeddings, and learn these vector representations according to their purpose.
Among graph embedding technologies, Graph Convolutional Networks (GCNs) are
known to outperform other graph embedding models (Kipf and Welling, 2016a;
Defferrard et al., 2016; Bruna et al., 2013). GCNs utilize information of
neighborhood to embed nodes by fusing features of the node itself and its
neighbors. In link prediction tasks, a Graph Autoencoder (GAE) (Kipf and
Welling, 2016b) is used to learn node embeddings generated by the GCN-encoder
via the reconstruction loss. Since then, numerous GAE/VGAE variants have been
proposed to achieve improved performance of link prediction (Pan et al., 2018;
Salha et al., 2020; Mavromatis and Karypis, 2020; Di et al., 2020).

Figure 1. (a) A graph with isolated nodes ($v_{7}$ and $v_{8}$), (b) content
features of nodes and (c) embedding space of latent vectors corresponding to
node $v_{i}$ (i=1,2,…,8)

In many applications, there occur nodes in a graph that have no connection
with other nodes. In this paper, we call such nodes, i.e., nodes with no
connection isolated nodes. For example, consider the following scenario. There
is a high school that maintains a social network G among members (e.g.,
students, professors, and staffs) where nodes are members and an edge between
two members represents a ”friendship” relation. Suppose the school has a
number of freshmen. Here ”Find out friends of students” can be considered a
link prediction task where new nodes (freshmen) are involved. Such new nodes
do not have any connection initially, and hence are isolated nodes in G when
link prediction tasks are performed. Since there are no connectivity
information of this case, feature contents of isolated nodes (e.g. the circles
or hobby of students) play a major role in link prediction.

We have found that existing GAEs do not properly handle feature contents of
isolated nodes. GAEs learn to make a low similarity of embeddings between a
pair of unconnected nodes. Consider a graph consisting of eight nodes in
Figure 1 (a). Figure 1 (c) shows vectors in an embedding space of the graph in
Figure 1 (a) where $z_{i}$ (i=$1,2,...,8$) is a latent vector corresponding to
node $v_{i}$ (i=$1,2,...,8$). Relative positions of $z_{i}$ are determined
based on the content information and the connectivity information in Figure 1
(a). Now consider two isolated nodes $v_{7}$ and $v_{8}$. Since $v_{7}$ and
$v_{8}$ are not connected with other nodes, similarities between their
embeddings and all other nodes should be low. We have found that GAEs tend to
make the Euclidean norm of embedding vectors of isolated nodes small in order
to reduce similarities between embeddings of isolated nodes and all the other
nodes. As a result, the embeddings of isolated nodes go close to zero
regardless of their content features.

In this paper, we propose a novel graph embedding technique, called
Variational Graph Normalized AutoEncoder (VGNAE) for link prediction where the
aforementioned problem of isolated nodes is properly handled. We propose a
Graph Normalized Convolutional Network (GNCN) that effectively use
$L_{2}$-normalization to prevent embeddings of isolated nodes from going near
zero. Our VGNAE is a VGAE model where a GNCN is used to derive the mean and a
GCN is used to derive the variance. We show through extensive experiments that
our proposed VGNAE effectively handles the problem of isolated nodes, and
outperforms other existing state-of-the-art link prediction models.

##  2\. Preliminaries

A graph $G$ can be represented as $G=(V,E,X)$ where $V$ is a set of vertices,
$E\subset V\times V$ is a set of edges, and $X$ is a feature matrix of $V$.
_N(v)_ denotes a set of neighbors of $v\in V$, $n=|V|$ denotes the number of
vertices, and $A\in R^{n\times n}$ is an adjacency matrix of $G$. Let
_$\vec{z_{v}}$_ be a vector that is an embedding of a node $v$, and
_$||\vec{x}||$_ denotes an euclidean norm ($L_{2}$-norm) of vector $\vec{x}$.

###  2.1. Graph Convolutional Networks

Graph Convolutional Networks (GCNs) generalize the convolution operations to
the graph domain. The SpectralCNN (Bruna et al., 2013) first proposes
convolutional networks to the graph domains using the graph fourier transform.
The ChebyConv (Defferrard et al., 2016) parameterizes the graph convolution
with chebyshev polynomials for efficient and localized filters. The GCN (Kipf
and Welling, 2016a) simplifies ChebyConv by using a normalization trick. Some
unsupervised learning methods using GCNs have been proposed. Kipf et al. (Kipf
and Welling, 2016b) propose two graph auto-encoders (GAEs and VGAEs) that
reconstruct the adjacency matrix by node embeddings generated by GCNs. LGAE
(Salha et al., 2020) is a simple and interpretable linear models leveraging
one-hop linear encoding. ARGA and ARVGA (Pan et al., 2018) are two variants of
adversarial approaches to learn robust embeddings. GraphInfoClust (Mavromatis
and Karypis, 2020) captures richer information and nodal interaction by
maximizing the mutual information between nodes of a same cluster. sGraphite-
VAE (Di et al., 2020) extends the GNNs by exploring the aggregation using
mutual information.

###  2.2. $L_{2}$-normalization

Certain properties about the norm of the embedding of the object
($||\vec{z_{o}}||$) have been addressed in several studies. In neural
translation models, an infrequent word is prone to have a embedding with a low
$L_{2}$-norm ($||\vec{w}||$) (Kobayashi et al., 2020; Arefyev et al., 2018;
Schakel and Wilson, 2015; Nguyen and Chiang, 2017; Nguyen and Salazar, 2019).
In image recognition models, an embedding representing poor quality image has
a low $L_{2}$-norm and vice versa (Liu et al., 2017; Wang et al., 2018). Also
in image search, methods in (Wu et al., 2017; Eghbali and Tahvildari, 2019)
normalizes the embedding to minimize the quantization error in high-resolution
image search. They and their subsequent studies use $L_{2}$-normalization
(Ranjan et al., 2017; Wang et al., 2017; Zheng et al., 2018) to minimize
errors caused by the imbalance between norms. In addition, some works (Merrill
et al., 2020; Nguyen and Salazar, 2019) show that the magnitude of the
parameter continues (norm) to increase during gradient descent. Zhang et al.
(Zhang et al., 2020) turns out that the imbalance between norms causes an
unstable direction update and uses $L_{2}$-normalization to resolve the
problem.

As far as we know, PairNorm (Zhao and Akoglu, 2019) and MSGNorm (Li et al.,
2020) are the only approach that use $L_{2}$-normalization in GCNs. However,
they are proposed to solve the over-smoothing problem, not for the problem
caused by isolated nodes.

##  3\. Our Approach

###  3.1. Norm-zero tendency of isolated nodes

For node $v\in\\{v_{1},v_{2},...,v_{n}\\}$ in a graph, there are certain
relationships between the norm of nodes $||\vec{z_{v}}||$ from GAEs and
degrees $d_{v}$. Figure 2 (a) shows node embeddings from a GAE for the Cora
and CiteSeer datasets in a 2-dimensional embedding space. Figure 2 (b) shows
the norms of node embeddings $||\vec{z_{v}}||$ from the GAE with respect to
degrees of nodes for the Cora and CiteSeer datasets. As shown in Figure 2 (a),
embeddings of isolated nodes are around $\vec{0}$. The norm of those vectors
will be close to zero. In Figure 2 (b), we can find out the norms of an
embedding vectors of isolated nodes tend to be close to zero. This also
happens with the mean vector of VGAEs. We call this phenomenon ”norm-zero
tendency of isolated nodes”, which is an extreme case of the imbalance between
norms. This tendency makes embeddings of isolated nodes indistinguishable
regardless of values of their content features.

Figure 2. (a) A 2-dimensional embedding space of a GAE in the Cora and the
CiteSeer dataset (b) a degree of nodes $d(v)$ and their norms of node
embeddings $||\vec{z_{v}}||$ from a GAE in the Cora and the CiteSeer dataset.

###  3.2. Graph Normalized Convolutional Network

We propose a novel graph neural network called a Graph Normalized
Convolutional Network (GNCN) that uses $L_{2}$-normalization before
propagation. Consider a feature matrix
$X=[\vec{x_{1}},\vec{x_{2}},...,\vec{x_{n}}]^{T}$ where $\vec{x_{i}}\in R^{m}$
is a content feature vector of node $v_{i}$ and $n$ is the number of nodes. A
GNCN first generates the feature transformed vectors ($\vec{h}\in R^{f}$) with
a learnable matrix W $\in R^{m\times f}$.

(1) $\vec{h_{i}}=\vec{x_{i}}W$

Let $s\in R$ be a scaling constant that represents a norm of the hidden
feature being propagated. Our proposed GNCN generates the normalized feature
transformed vectors ($\vec{n}\in R^{f}$) and propagates the normalized vector
to generates node embeddings ($\vec{z}\in R^{f}$).

(2) $\vec{n_{i}}=s{\vec{h_{i}}\over||\vec{h_{i}}||}$ (3)
$\vec{z_{i}}={1\over{d_{i}}+1}\vec{n_{i}}+\sum_{j\in
N(i)}{1\over\sqrt{d_{i}+1}\sqrt{d_{j}+1}}\vec{n_{j}}\quad{\rm where}\quad
i\in\\{1,2,...,n\\}$

Now, for a feature matrix $X\in R^{n\times m}$ and an adjacency matrix $A$,
$GNCN(X,A,s)$ is defined as follows:

(4) ${\rm GNCN(X,A,s)}=s\tilde{D}^{-{1\over 2}}\tilde{A}\tilde{D}^{-{1\over
2}}g(XW)$

Here
$g([\vec{h_{1}},\vec{h_{2}},...,\vec{h_{n}}]^{T})=[{\vec{h_{1}}\over||\vec{h_{1}}||},{\vec{h_{2}}\over||\vec{h_{2}}||},...,{\vec{h_{n}}\over||\vec{h_{n}}||}]^{T}$
, $Z=[\vec{z_{1}},\vec{z_{2}}$ $,...,\vec{z_{n}}]^{T}\in\mathbb{R}^{n\times
f}$ is a node embedding matrix, $W\in\mathbb{R}^{m\times f}$ is a trainable
matrix, $\tilde{A}=A+I_{N}$, $\tilde{D}$ is a degree matrix of $\tilde{A}$,
and $s$ is a scaling constant. We will show that our proposed GNCN properly
handles the norm-zero tendency of isolated nodes through experiments in Sec
4.4.1.

###  3.3. Variational Graph Normalized AutoEncoder

In this paper, we propose two variants of graph autoencoder called Graph
Normalized AutoEncoder (GNAE) and Variational Graph Normalized AutoEncoder
(VGNAE). For each node $v\in\\{1,2,...,n\\}$, GNAE encodes the local structure
information and node feature information of its neighborhood to derive latent
variables $\vec{z_{v}}\in R^{f}$. To generate
$Z=[\vec{z_{1}},\vec{z_{2}},...,\vec{z_{n}}]^{T}\in R^{n\times f}$, GNAE uses
a GNCN encoder that avoids the norm-zero tendency of isolated nodes. GNAE uses
a inner-product decoder to create the reconstructed adjacent matrix $\hat{A}$
from $Z$ as follows:

(5) $\hat{A}=\sigma(Z^{T}Z),\quad{\rm with}\quad Z=GNCN(X,A,s)$

where $\sigma$ is a sigmoid function.

We also propose a Variational Graph Normalized AutoEncoder (VGNAE). Since mean
vectors in VGAEs also have norm-zero tendency of isolated nodes, we derive
mean vectors of VGNAE with a GNCN encoder. Our VNGAE takes a simple inference
model by using the mean field approximation to define the variational family
as follows:

(6) $q(Z|X,A)=\prod_{i=1}^{n}q(z_{i}|X,A)\quad{\rm with}\quad
q(z_{i}|X,A)=N(z_{i}|\mu_{i},diag({\sigma_{i}}^{2}))$

where $\mu=[\mu_{1},\mu_{2},...,\mu_{n}]^{T}=GNCN(X,A,c)$ is the matrix of
mean vectors $\mu_{i}$ ; similarly
$log\sigma=[log\sigma_{1},...,log\sigma_{i}]^{T}=GCN(X,A)$.

Our generative model reconstructs graph structure $A$ by using a simple inner
product decoder.

(7)
$p(A|Z)=\prod_{i=1}^{n}\prod_{j=1}^{n}p(A_{ij}|\vec{z_{i}},\vec{z_{j}})\quad{\rm
with}\quad p(A_{ij}=1|Z)=\sigma(\vec{z_{i}}^{T}\vec{z_{j}})$

For GNAE, we minimize the reconstruction error of $\hat{A}$. For VGNAE,
optimization is made by maximizing a tractable variational lower bound (ELBO)
as follows:

(8) $L_{ELBO}=E_{q(Z|X,A)}[logp(A|Z)]-KL(q(Z|X,A)||p(Z))$

where $KL(q||p)=\Sigma_{j}Q_{j}log({Q_{j}\over P_{j}})$ is the Kullback-
Leibler divergence between $q$ and $p$. We use a Gaussian prior $p(Z)$ $=$
$\prod_{i=1}^{n}$ $N(z_{i}|0,I)$.

##  4\. Experiments

We conduct various experiments to show performance improvements of our
proposed VGNAEs in link prediction when isolated nodes are involved. First, we
show the performance improvement of our GNCN by comparing the AUC scores of
isolated nodes in various types of graph structured networks. Then, we
evaluate our GAE/VGNAE employing the GNCN.

###  4.1. Datasets

We use various types of attributed graphs. First, we use three citation
network datasets (Cora, Citeseer, and Pubmed). Second, we use a coauthor
network Coauthor CS (Shchur et al., 2018). Third, we use a co-purchase graph
Amazon Photo (Shchur et al., 2018). Statistics about datasets are described in
Table 1.

Table 1. The statistics of the benchmark graph datasets Dataset | Type | #Nodes | #Edges | #Features
---|---|---|---|---
Cora | Citation | 2,708 | 5,429 | 1,433
CiteSeer | Citation | 3,327 | 4,732 | 3,703
PubMed | Citation | 19,717 | 44,338 | 500
CS | Coauthor | 18,333 | 81,894 | 6,805
Photo | Co-purchase | 7,487 | 119,043 | 745

###  4.2. Setup

We implement all our models using Pytorch 1.4.0 (Paszke et al., 2019). We use
the Adam optimizer (Kingma and Ba, 2014) with a learning rate of 0.005. We
train all models for a maximum of 300 epochs and early stopping with a window
size of 50. In all the experiments, 64 dimensions are used for node
embeddings. A scaling constant ($s$) in GNCN is set as 1.8. For GCN (Kipf and
Welling, 2016a), we use a two-layer GCN with the dimension of hidden
embeddings is set to 128. For GraphHeat (Xu et al., 2020) and APPNP (Klicpera
et al., 2018), the optimal hyper-parameters (e.g. scaling parameter $s$ and
teleport rate $t$) are chosen through validation set. For GraphHeat (Xu et
al., 2020), 0.4 is used for the coeffient $s$. For APPNP (Klicpera et al.,
2018), 0.15 is used for the teleport rate and 10 is used for the number of
propagations. The link prediction models are evaluated by the area under the
ROC curve (AUC) and average precision (AP) scores.

###  4.3. Results

####  4.3.1. GNCN : Power of normalization for isolated nodes

In this section, we present that performance of GAEs with existing GCN
encoders degrades when isolated nodes are involved. We also present that GAEs
using our proposed GNCN encoders effectively encode isolated nodes. We compare
the performance of GAEs using various GCN-based encoders for isolated nodes
and connected nodes on Cora, CiteSeer, CS and, Photo datasets. The compared
GCN-based encoders are GCN (Kipf and Welling, 2016a), GAT (Veličković et al.,
2017), SGCN (Wu et al., 2019), SuperGAT (Kim and Oh, 2020), APPNP (Klicpera et
al., 2018), GraphHeat (Xu et al., 2020), PairNorm (Zhao and Akoglu, 2019), and
MSGNorm (Li et al., 2020).

For every dataset, we use a training set 60%, a validation set 10%, and a test
set 30% among all edges. We add the same number of randomly sampled negative
edges to the valid set and test set. We measured the AUC score for isolated
nodes and connected nodes in test sets. The results are shown in Figures 3.
Figure 3 shows that the AUC scores of GAEs with other GCN encoders of isolated
nodes is significantly lower than that of connected nodes (10 $\sim$ 20%) for
all types of graphs. Experimental results on graphs of various types show that
the degrade of performance in isolated nodes occurs in general graphs. In
addition, it can be seen that the accuracy at the isolated nodes for each GCN
varies depending on the type of dataset. We confirmed that existing GCNs are
not suitable encoders of GAEs when isolated nodes are involved. The methods
using proposed GNCN ensured the highest performance of the isolated nodes for
all graphs without compromising the performance of the connected nodes.

Figure 3. AUC scores of isolated nodes and connected nodes

####  4.3.2. Performance Comparision of GNAE/VGNAE with state-of-the-art
methods

We conduct experiments on citation networks (Cora, CiteSeer, and PubMed) to
compare the performance of GNAE/VGNAE with state-of-the-art link prediction
models, i.e., LGAE (Salha et al., 2020), ARGA (Pan et al., 2018), ARGVA (Pan
et al., 2018), Graph InfoClust (GIC) (Mavromatis and Karypis, 2020), and
sGraphite-VAE (Di et al., 2020). For all datasets, 20%, 40%, and 80% of edges
are used for training sets. For the remaining edges, the ratio of 1 to 3 are
used for valiatdation sets and test sets. We add the same number of randomly
sampled negative edges for each valid and test set. For each dataset divided
in this way, the AUC and AP scores are measured. The results of link
prediction in the dataset are shown in Table 2.

Table 2. Experiment results for citation datasets on link prediction task Data | Metric | Train | GAE | LGAE | ARGA | GIC | sGraph | GNAE | VGNAE
---|---|---|---|---|---|---|---|---|---
Cora | AUC | 20% | 0.782 | 0.866 | 0.795 | 0.880 | 0.845 | 0.887 | 0.890
40% | 0.856 | 0.908 | 0.844 | 0.914 | 0.840 | 0.926 | 0.929
80% | 0.922 | 0.938 | 0.919 | 0.933 | 0.885 | 0.956 | 0.954
AP | 20% | 0.793 | 0.878 | 0.806 | 0.881 | 0.829 | 0.901 | 0.901
40% | 0.861 | 0.915 | 0.856 | 0.911 | 0.828 | 0.936 | 0.933
80% | 0.930 | 0.945 | 0.927 | 0.929 | 0.867 | 0.957 | 0.958
CiteSeer | AUC | 20% | 0.786 | 0.906 | 0.750 | 0.930 | 0.928 | 0.946 | 0.941
40% | 0.836 | 0.925 | 0.832 | 0.936 | 0.936 | 0.956 | 0.961
80% | 0.894 | 0.955 | 0.904 | 0.962 | 0.963 | 0.965 | 0.970
AP | 20% | 0.797 | 0.913 | 0.777 | 0.934 | 0.897 | 0.953 | 0.948
40% | 0.850 | 0.929 | 0.844 | 0.938 | 0.910 | 0.958 | 0.966
80% | 0.903 | 0.959 | 0.915 | 0.966 | 0.943 | 0.970 | 0.971
PubMed | AUC | 20% | 0.937 | 0.946 | 0.936 | 0.950 | 0.837 | 0.950 | 0.951
40% | 0.959 | 0.962 | 0.955 | 0.958 | 0.876 | 0.963 | 0.964
80% | 0.967 | 0.974 | 0.973 | 0.960 | 0.896 | 0.975 | 0.976
AP | 20% | 0.940 | 0.947 | 0.941 | 0.947 | 0.859 | 0.950 | 0.949
40% | 0.961 | 0.961 | 0.959 | 0.956 | 0.879 | 0.961 | 0.963
80% | 0.967 | 0.975 | 0.976 | 0.965 | 0.902 | 0.975 | 0.976

As can be seen in Table 2, our GNAE/VGNAE show superior results compared to
other methods in all divisions. Also we can observe that the fewer observed
edges (the smaller the ratio of the training rate), the better the performance
of our proposed method compared to other SOTA models. This is because as the
ratio of unobserved edges increase, the number of isolated nodes also
increases.

##  5\. Conclusions

We have presented that in GAE and VGAE embeddings of isolated nodes tends to
go to zero regardless of their content features on various graph-structured
networks. This tendency can significantly degrade accuracy of link prediction
when many isolated nodes are involved. We have argued that the
$L_{2}$-normalization is an effective technique to generate proper embeddings
of isolated nodes in the link prediction task. We have shown through extensive
experiments that our proposed VGNAE performs better than other existing
methods.

## Acknowledgements

This work was supported by the Bio-Synergy Research Project of the MSIT (No.
2013M3A9C4078137), the National Research Foundation of Korea(NRF) grant (No.
2020R1A2C1004032), and the ITRC support program (IITP-2020-2020-0-01795)
supervised by the IITP.

## References

  * (1)
  * Arefyev et al. (2018) Nikolay Arefyev, Pavel Ermolaev, and Alexander Panchenko. 2018\.  How much does a word weigh? Weighting word embeddings for word sense induction.  _arXiv preprint arXiv:1805.09209_ (2018).
  * Bruna et al. (2013) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013.  Spectral networks and locally connected networks on graphs.  _arXiv preprint arXiv:1312.6203_ (2013).
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ 29 (2016), 3844–3852.
  * Di et al. (2020) Xinhan Di, Pengqian Yu, Rui Bu, and Mingchao Sun. 2020\.  Mutual Information Maximization in Graph Neural Networks. In _2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 1–7.
  * Eghbali and Tahvildari (2019) Sepehr Eghbali and Ladan Tahvildari. 2019.  Deep spherical quantization for image search. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 11690–11699.
  * Kim and Oh (2020) Dongkwan Kim and Alice Oh. 2020.  How to find your friendly neighborhood: Graph attention design with self-supervision. In _International Conference on Learning Representations_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kipf and Welling (2016a) Thomas N Kipf and Max Welling. 2016a.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Kipf and Welling (2016b) Thomas N Kipf and Max Welling. 2016b.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ (2016).
  * Klicpera et al. (2018) Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2018.  Predict then propagate: Graph neural networks meet personalized pagerank.  _arXiv preprint arXiv:1810.05997_ (2018).
  * Kobayashi et al. (2020) Goro Kobayashi, Tatsuki Kuribayashi, Sho Yokoi, and Kentaro Inui. 2020.  Attention is not only a weight: Analyzing transformers with vector norms.  _arXiv preprint arXiv:2004.10102_ (2020).
  * Li et al. (2020) Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. 2020\.  Deepergcn: All you need to train deeper gcns.  _arXiv preprint arXiv:2006.07739_ (2020).
  * Liu et al. (2017) Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. 2017\.  Sphereface: Deep hypersphere embedding for face recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 212–220.
  * Mavromatis and Karypis (2020) Costas Mavromatis and George Karypis. 2020.  Graph InfoClust: Leveraging cluster-level node information for unsupervised graph representation learning.  _arXiv preprint arXiv:2009.06946_ (2020).
  * Merrill et al. (2020) William Merrill, Vivek Ramanujan, Yoav Goldberg, Roy Schwartz, and Noah Smith. 2020.  Parameter Norm Growth During Training of Transformers.  _arXiv preprint arXiv:2010.09697_ (2020).
  * Nguyen and Chiang (2017) Toan Q Nguyen and David Chiang. 2017.  Improving lexical choice in neural machine translation.  _arXiv preprint arXiv:1710.01329_ (2017).
  * Nguyen and Salazar (2019) Toan Q Nguyen and Julian Salazar. 2019.  Transformers without tears: Improving the normalization of self-attention.  _arXiv preprint arXiv:1910.05895_ (2019).
  * Pan et al. (2018) Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. 2018\.  Adversarially regularized graph autoencoder for graph embedding.  _arXiv preprint arXiv:1802.04407_ (2018).
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ 32 (2019), 8026–8037.
  * Ranjan et al. (2017) Rajeev Ranjan, Carlos D Castillo, and Rama Chellappa. 2017\.  L2-constrained softmax loss for discriminative face verification.  _arXiv preprint arXiv:1703.09507_ (2017).
  * Salha et al. (2020) Guillaume Salha, Romain Hennequin, and Michalis Vazirgiannis. 2020\.  Simple and effective graph autoencoders with one-hop linear models.  _arXiv preprint arXiv:2001.07614_ (2020).
  * Schakel and Wilson (2015) Adriaan MJ Schakel and Benjamin J Wilson. 2015.  Measuring word significance using distributed representations of words.  _arXiv preprint arXiv:1508.02297_ (2015).
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018\.  Pitfalls of graph neural network evaluation.  _arXiv preprint arXiv:1811.05868_ (2018).
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Wang et al. (2017) Feng Wang, Xiang Xiang, Jian Cheng, and Alan Loddon Yuille. 2017\.  Normface: L2 hypersphere embedding for face verification. In _Proceedings of the 25th ACM international conference on Multimedia_. 1041–1049.
  * Wang et al. (2018) Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong, Jingchao Zhou, Zhifeng Li, and Wei Liu. 2018\.  Cosface: Large margin cosine loss for deep face recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 5265–5274.
  * Wu et al. (2019) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019\.  Simplifying graph convolutional networks. In _International conference on machine learning_. PMLR, 6861–6871.
  * Wu et al. (2017) Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N Holtmann-Rice, David Simcha, and Felix Yu. 2017.  Multiscale quantization for fast similarity search.  _Advances in Neural Information Processing Systems_ 30 (2017), 5745–5755.
  * Xu et al. (2020) Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. 2020.  Graph convolutional networks using heat kernel for semi-supervised learning.  _arXiv preprint arXiv:2007.16002_ (2020).
  * Zhang et al. (2020) Dingyi Zhang, Yingming Li, and Zhongfei Zhang. 2020\.  Deep Metric Learning with Spherical Embedding.  _Advances in Neural Information Processing Systems_ 33 (2020).
  * Zhao and Akoglu (2019) Lingxiao Zhao and Leman Akoglu. 2019.  Pairnorm: Tackling oversmoothing in gnns.  _arXiv preprint arXiv:1909.12223_ (2019).
  * Zheng et al. (2018) Yutong Zheng, Dipan K Pal, and Marios Savvides. 2018\.  Ring loss: Convex feature normalization for face recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 5089–5097.