#  Cordiality of Digraphs††thanks: AMS Classification number: 05C20, 05C38,
05C78  ††thanks: Key words and phrases: tournament, wheel graph, fan graph,
$(2,3)$-cordial)

LeRoy B. Beasley, Manuel A. Santana, Jonathan Mousley
and David E. Brown

Department of Mathematics and Statistics
Utah State University
Logan, Utah 84322-3900, U.S.A

###### Abstract

A $(0,1)$-labelling of a set is said to be friendly if approximately one half
the elements of the set are labelled 0 and one half labelled 1. Let $g$ be a
labelling of the edge set of a graph that is induced by a labelling $f$ of the
vertex set. If both $g$ and $f$ are friendly then $g$ is said to be a cordial
labelling of the graph. We extend this concept to directed graphs and
investigate the cordiality of sets of directed graphs. We investigate a
specific type of cordiality on digraphs, a restriction of quasigroup-
cordiality called $(2,3)$-cordiality. A directed graph is $(2,3)$-cordial if
there is a friendly labelling $f$ of the vertex set which induces a
$(1,-1,0)$-labelling of the arc set $g$ such that about one third of the arcs
are labelled 1, about one third labelled -1 and about one third labelled 0. In
particular we determine which tournaments are $(2,3)$-cordial, which
orientations of the $n$-wheel are $(2,3)$-cordial, and which orientations of
the $n-$fan are $(2,3)$-cordial.

##  1 Introduction

The study of cordial graphs began in 1987 with an article by I. Cahit [2]:
”Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs”. In 1991,
Hovey [3] generalized this concept to ${\mathcal{A}}$-cordial graphs where
${\mathcal{A}}$ is an abelian group. A further generalization, one that
included cordiality of directed graphs, appeared in 2012 with an article by
Pechenik and Wise [4], where the ${\mathcal{A}}$ was allowed to be any quasi
group, not necessarily Abelian. We modify this concept to
$(A,{\mathcal{A}})$-cordial digraphs where $A$ is a subset of the quasigroup
${\mathcal{A}}$.

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. A
$(0,1)$-labelling of the vertex set is a mapping $f:V\to\\{0,1\\}$ and is said
to be friendly if approximately one half of the vertices are labelled 0 and
the others labelled 1. An induced labelling of the edge set is a mapping
$g:E\to\\{0,1\\}$ where for an edge $uv,g(uv)=\hat{g}(f(u),f(v)$ for some
$\hat{g}:\\{0,1\\}\times\\{0,1\\}\to\\{0,1\\}$ and is said to be cordial if
$f$ is friendly and about one half the edges of $G$ are labelled 0 and the
others labelled 1. A graph, $G$, is called cordial if there exists a cordial
induced labelling of the edge set of $G$. In this article, as in [1], we
define a cordial labelling of directed graphs that is not merely a cordial
labelling of the underlying undirected graph.

A specific type of $(A,{\mathcal{A}})$-cordial digraph is a $(2,3)$-cordial
digraph defined by Beasley in [1]. Let $D=(V,A)$ be a directed graph with
vertex set $V$ and arc set $A$. Let $f:V\to\\{0,1\\}$ be a friendly vertex
labelling and let $g$ be the induced labelling of the arc set,
$g:A\to\\{0,1,-1\\}$ where for an arc
$\overrightarrow{uv},g(\overrightarrow{uv})=f(v)-f(u)$. The labellings $f$ and
$g$ are $(2,3)$-cordial if $f$ is friendly and about one third the arcs of $D$
are labelled 1, one third are labelled -1 and one third labelled 0. A digraph,
$D$, is called $(2,3)$-cordial if there exists $(2,3)$-cordial labellings $f$
of the vertex set and $g$ of the arc set of $D$.

Note that here and what follows, the term “about” when talking about fractions
of a quantity we shall mean as close is possible in integral arithmetic, so
about half of 9 is either 4 or 5, but not 3 or 6.

##  2 Preliminaries

###### Definition 2.1

A quasigroup is a set ${\mathcal{Q}}$ with binary operation $\circ$ such that
given any $a,b\in{\mathcal{Q}}$ there are $x,y\in{\mathcal{Q}}$ such that
$a\circ x=b$ and $y\circ a=b$.

Fact: All two element quasigroups are Abelian.

Proof.  Suppose that ${\mathcal{Q}}=\\{a,b\\}$ is a quasi group with binary
operation $\circ$. Then, there are $x,y\in{\mathcal{Q}}$ such that $a\circ
x=a$ and $y\circ a=a$. If $x=y=b$ then ${\mathcal{Q}}$ is Abelian. Otherwise,
we must have $a\circ a=a$. Similarly either ${\mathcal{Q}}$ is abelian or
$b\circ b=b$.

Now, suppose that $a\circ a=a$ and $b\circ b=b$. Then there are
$c,d\in{\mathcal{Q}}$ such that $a\circ d=b$ and $c\dot{a}=b$. Since $a\circ
a=a$., we must have that both $c=b$ and $d=b$. That is ${\mathcal{Q}}$ is
Abelian.

We now formalize the terms mentioned in the introduction. We let
${\mathbb{Z}}_{k}$ denote the set of integers $\\{0,1,\dots,k\\}$ with
arithmetic is modulo $k$ as needed. Further let ${\mathbb{Z}}_{k}^{-}$ denote
the set ${\mathbb{Z}}_{k}$ with binary operation “-”, subtraction modulo $k$.
Clearly ${\mathbb{Z}}_{k}^{-}$ is a nonabelian quasigroup.

###### Definition 2.2

A ${\mathbb{Z}}_{k}$-labelling (or simply a $k$-labelling) of a finite set,
${\cal X}$, is a mapping $f:{\cal X}\to{\mathbb{Z}}_{k}$ and is said to be
friendly if the labelling is evenly distributed over ${\mathbb{Z}}_{k}$, that
is, given any $i,j\in{\mathbb{Z}}_{k}$, $-1\leq|f^{-1}(i)|-|f^{-1}(j)|\leq 1$
where $|{\cal X}|$ denotes the cardinality of the set ${\cal X}$.

###### Definition 2.3

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$, and
let $f$ be a friendly $(0,1)$-labelling of the vertex set $V$. Given this
friendly vertex labelling $f$, an induced $(0,1)$-labelling of the edge set is
a mapping $g:E\to\\{0,1\\}$ where for an edge $uv,\,g(uv)=\hat{g}(f(u),f(v))$
for some $\hat{g}:\\{0,1\\}\times\\{0,1\\}\to\\{0,1\\}$ and is said to be
cordial if $g$ is also friendly, that is about one half the edges of $G$ are
labelled 0 and the others are labelled 1, or
$-1\leq|g^{-1}(0)|-|g^{-1}(1)|\leq 1$. A graph, $G$, is called cordial if
there exists a induced cordial labelling of the edge set of $G$.

The induced labelling $g$ in a cordial graph is usually
$g(u,v)=\hat{g}(f(u),f(v))=|f(v)-f(u)|$ [2],
$g(u,v)=\hat{g}(f(u),f(v))=f(v)+f(u)$ (in ${\mathbb{Z}}_{2}$) [3], or
$g(u,v)=\hat{g}(f(u),f(v))=f(v)f(u)$ (product cordiality) [5].

In [3], Hovey introduced ${\cal A}$-friendly labellings where ${\mathcal{A}}$
is an Abelian group. A labelling $f:V(G)\to{\cal A}$ is said to be ${\cal
A}$-friendly  if given any $a,b\in{\cal A}$,
$-1\leq|f^{-1}(b)|-|f^{-1}(a)|\leq 1$. If $g$ is an induced edge labelling and
$f$ and $g$ are both ${\cal A}$-friendly Then $g$ is said to be an ${\cal
A}$-cordial labelling and $G$ is said to be ${\cal A}$-cordial. When ${\cal
A}={\mathbb{Z}}_{k}$ we say that $G$ is $k$-cordial. We shall use this concept
with digraphs.

Given an undirected graph or a digraph, $G$, let $\hat{G}$ denote the subgraph
(or subdigraph) of $G$ induced by its nonisolated vertices. So $\hat{G}$ never
has an isolated vertex. The need for this will become apparent in Example 3.1.

In this article, we will be concerned mainly with digraphs. We let
${\mathcal{D}}_{n}$ denote the set of all simple directed graphs on the vertex
set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$. Note that the arc set of members of
${\mathcal{D}}_{n}$ may contain digons, a pair of arcs between two vertices
each directed opposite from the other. We shall let ${\mathcal{T}}_{n}$ denote
the set of all subdigraphs of a tournament digraph. So the members of
${\mathcal{T}}_{n}$ contain no digons. Let $D\in{\mathcal{D}}_{n}$, $D=(V,A)$
where $A$ is the arc set of $D$. Then $D$ has no loops, and no multiple arcs.
An arc in $D$ directed from vertex $u$ to vertex $v$ will be denoted
$\overrightarrow{uv},\overleftarrow{vu}$ or by the ordered pair $(u,v)$. We
also let ${\mathcal{G}}_{n}$ denote the set of all simple undirected graphs on
the vertex set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$. So all members of
${\mathcal{T}}_{n}$ are orientations of graphs in ${\mathcal{G}}_{n}$.

In [4], Pechenik and Wise introduced quasigoup cordiality. When the quasigroup
is nonabelian, this type of cordiality is quite suitable for studying
labellings of directed graphs. In fact, if ${\mathcal{Q}}$ is a quasigroup
with any binary operation $\circ$ with the property that for any
$a,b\in{\mathcal{Q}}$ $a\circ b=b\circ a$ if and only if $a=b$, we have the
best situation for directed graphs.

Now the set ${\mathbb{Z}}_{k}$ with binary operation $\circ$ where for
$a,b\in{\mathbb{Z}}_{k}$, $a\circ b=b-a\mod k$ is such a quasigroup.

In our incvestigations we make one further restriction: we will label our
vertices with only a subset of ${\mathcal{Q}}$, not necessarily the whole set
${\mathcal{Q}}$:

###### Definition 2.4

Let ${\mathcal{Q}}$ be a quasigroup with binary operation $\circ$ and let
${\mathbb{Q}}$ be a subset of ${\mathcal{Q}}$. Let $D=(V,A)$ be a directed
graph with vertex set $V$ and arc set $A$. Let $f:V\to{\mathbb{Q}}$ be a
friendly ${\mathbb{Q}}$-labelling of $V$ and let $g:A\to{\mathcal{Q}}$ be an
induced arc labelling where for $\overrightarrow{uv}\in A$,
$g(\overrightarrow{uv})=\hat{g}(f(u),f(v))$ for some
$\hat{g}:{\mathbb{Q}}\times{\mathbb{Q}}\to{\mathcal{Q}}$. The mapping $g$ is
said to be $({\mathbb{Q}},{\mathcal{Q}})$-cordial if $g$ is also friendly,
that is, given any $a,b\in{\mathcal{Q}}$, $-1\leq|g^{-1}(a)|-|g^{-1}(b)|\leq
1$. A directed graph, $D$, is called $({\mathbb{Q}},{\mathcal{Q}})$-cordial if
there exists a induced $({\mathbb{Q}},{\mathcal{Q}})$-cordial labelling of the
arc set of $D$.

We now shall restrict our attention to the smallest case of
$({\mathbb{Q}},{\mathcal{Q}})$-cordiality that is appropriate for directed
graphs, $({\mathbb{Z}}_{2},{\mathbb{Z}}_{3}^{-})$-cordiality, that defined by
Beasley in [1], $(2,3)$-cordiality.

##  3 $(2,3)$-orientable Digraphs.

Let $D=(V,A)$ be a directed graph with vertex set $V$ and arc set $A$. Let
$f:V\to\\{0,1\\}$ be a friendly labelling of the vertices of $D$. As for
undirected graphs, an induced labelling of the arc set is a mapping
$g:A\to{\cal X}$ for some set ${\cal X}$ where for an arc
$(u,v)=\overrightarrow{uv},g(u,v)=\hat{g}(f(u),f(v))$ for some
$\hat{g}:\\{0,1\\}\times\\{0,1\\}\to{\cal X}$. As we are dealing with directed
graphs, it would be desirable for the induced labelling to distinguish between
the label of the arc $(u,v)$ and the label of the arc $(v,u)$, otherwise, the
labelling would be an induced labelling of the underlying undirected graph. If
we let ${\cal X}=\\{-1,0,1\\}$ and $\hat{g}(f(u),f(v))=f(v)-f(u)$ using real
arithmetic, or arithmetic in ${\mathbb{Z}}_{3}$, we have an asymmetric
labelling. In this case, if about one third of the arcs are labelled 0, about
one third of the arcs are labelled 1 and about one third of the arcs are
labelled -1 we say that the labelling is $(2,3)$-cordial. Formally:

###### Definition 3.1

Let $D\in{\mathcal{T}}_{n}$, $D=(V,A)$, be a digraph without isolated
vertices. Let $f:V\to\\{0,1\\}$ be a friendly labelling of the vertex set $V$
of $D$. Let $g:A\to\\{1,0,-1\\}$ be an induced labelling of the arcs of $D$
such that for any $i,j\in\\{1,0,-1\\}$, $-1\leq|g^{-1}(i)|-|g^{-1}(j)|\leq 1$.
Such a labelling is called a $(2,3)$-cordial labelling.

A digraph $D\in{\mathcal{T}}_{n}$ whose subgraph $\hat{G}$ can possess a
$(2,3)$-cordial labelling will be called a $(2,3)$-cordial digraph.

An undirected graph $G$ is said to be $(2,3)$-orientable if there exists an
orientation of $G$ that is $(2,3)$-cordial.

In [1] the concept of $(2,3)$-cordial digraphs was introduced and paths and
cycles were investigated. In [6] one can find further investigation of
orientations of paths and trees as well as finding the maximum number of arcs
possible in a $(2,3)$-cordial digraph. In this article we continue this
investigation, showing which tournaments, which orientations of the wheel
graphs, and which orientations of the fan graphs are $(2,3)$-cordial.

###### Definition 3.2

Let $D=(V,A)$ be a digraph with vertex labelling $f:V\to\\{0,1\\}$ and with
induced arc labelling $g:A\to\\{0,1,-1\\}$. Define
$\Lambda_{f,g}:{\mathcal{D}}_{n}\to{\mathbb{N}}^{3}$ by
$\Lambda_{f,g}(D)=(\alpha,\beta,\gamma)$ where
$\alpha=|g^{-1}(1)|,\beta=|g^{-1}(-1)|,$ and $\gamma=|g^{-1}(0)|$.

Let $D\in{\mathcal{T}}_{n}$ and let $D^{R}$ be the digraph such that every arc
of $D$ is reversed, so that $\overrightarrow{uv}$ is an arc in $D^{R}$ if and
only if $\overrightarrow{vu}$ is an arc in $D$. Let $f$ be a $(0,1)$-labelling
of the vertices of $D$ and let $g(\overrightarrow{uv})=f(v)-f(u)$ so that $g$
is a $(1,-1,0)$-labelling of the arcs of $D$. Let $\overline{f}$ be the
complementary $(0,1)$-labelling of the vertices of $D$, so that
$\overline{f}(v)=0$ if and only if $f(v)=1$. Let $\overline{g}$ be the
corresponding induced arc labelling of $D$,
$\overline{g}(\overrightarrow{uv})=\overline{f}(v)-\overline{f}(u)$.

###### Lemma 3.1

Let $D\in{\mathcal{T}}_{n}$ with vertex labelling $f$ and induced arc
labelling $g$. Let $\Lambda_{f,g}(D)=(\alpha,\beta,\gamma)$. Then

  1. 1.

$\Lambda_{f,g}(D^{R})=(\beta,\alpha,\gamma)$.

  2. 2.

$\Lambda_{\overline{f},\overline{g}}(D)=(\beta,\alpha,\gamma)$, and

  3. 3.

$\Lambda_{\overline{f},\overline{g}}(D^{R})=\Lambda_{f,g}(D).$

Proof. If an arc is labelled 1, -1, 0 respectively then reversing the
labelling of the incident vertices gives a labelling of -1, 1, 0 respectively,
If an arc $\overrightarrow{uv}$ is labelled 1, -1, 0 respectively, then
$\overrightarrow{vu}$ would be labelled -1, 1, 0 respectively.

###### Example 3.1

Now, consider a graph, Xn in ${\mathcal{G}}_{n}$ consisting of three parallel
edges and n-6 isolated vertices. Is Xn $(2,3)$-orientable? If $n=6$, the
answer is no, since any friendly labelling of the six vertices would have
either no arcs labelled 0 or two arcs labelled 0. In either case, the
orientation would never be $(2,3)$-cordial. That is X6 is not
$(2,3)$-orientable, however with additional vertices like X7 the graph is
$(2,3)$-orientable.

Thus, for our investigation here, we will us the convention that a graph, $G$,
is $(2,3)$-orientable/$(2,3)$-cordial if and only if the subgraph of $G$
induced by its nonisolated vertices, $\hat{G}$, is
$(2,3)$-orientable/$(2,3)$-cordial.

###  3.1 $(2,3)$-Orientations of a Complete Graph – Tournaments

It is an easy exercise to show that every 3-tournament is $(2,3)$-cordial and
that two of the four non isomorphic 4-tournaments are $(2,3)$-cordial. See
Figures 2 and 3. Note that the 4-tournaments that are not $(2,3)$-cordial may
require more that a cursory glance to verify that they are not
$(2,3)$-cordial.

###### Lemma 3.2

Every 5-tournament is $(2,3)$-cordial.

Proof. Let $T\in{\cal D}_{5}$ be a tournament. Then there are two vertices,
without loss of generality, $v_{1}$ and $v_{2}$, whose total out degree is
four. (And hence the total in-degree of $v_{1}$ and $v_{2}$ is also four. Let
$f$ be the vertex labelling and let $f(v_{1})=f(v_{2})=1$ and
$f(v_{3})=f(v_{4})=f(v_{5})=0$. Let $g$ be the arc labelling
$g(\overrightarrow{v_{i}v_{j}})=f(v_{j})-f(v_{i})$. Then, the arc between
$v_{1}$ and $v_{2}$ is labelled 0, as are the three arcs between $v_{3},v_{4}$
and $v_{5}$. Thus there are four arcs labelled 0. The three arcs from $v_{1}$
or $v_{2}$ to vertices $v_{3},v_{4}$ or $v_{5}$ are labelled 1 and the three
arcs from $v_{3},v_{4}$ or $v_{5}$ to vertices $v_{1}$ or $v_{2}$ are labelled
-1. In Figure 1 is an example of the labelling described above. Thus
$\Lambda_{f,g}({T})=(3,3,4)$. That is $T$ is $(2,3)$-cordial.

$0$$0$$1$$1$$0$$0$$0$$0$$-1$$1$$-1$$1$$-1$$1$$0$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$
Figure 1:  A $(2,3)$-Cordial labellings of a 5-tournament

###### Lemma 3.3

If $n\geq 6$ and $T\in{\mathcal{D}}_{n}$ is a tournament on $n$ vertices then
$T$ is not $(2,3)$-cordial.

Proof. We divide the proof into two cases:

Case 1. $n$ is even. Let $n=2k$. We shall show that there must be more arcs
labelled 0 than is allowed in any $(2,3)$-cordial digraph with
$\frac{n(n-1)}{2}$ arcs. For any vertex labelled 0, there are $k-1$ other
vertices also labelled 0 so that there are $k-1$ arcs labelled 0 that either
begin or terminate at that vertex. Also there are $k$ such vertices so there
are $k(k-1)/2$ arcs between pairs of vertices each labelled 0. (Note, since
each arc is adjacent to two vertices we have divided the total number by 2 to
get the number of distinct arcs labelled 0.) There are also $k(k-1)/2$ arcs
between pairs of vertices each labelled 1. Thus we must have $k(k-1)$ arcs
labelled 0.

Now, there must be at most one third the number of arcs labelled 0, so we must
have $3k(k-1)\leq\frac{n(n-1)}{2}+2=\frac{4k^{2}-2k+4}{2}$. That is, we must
have $k^{2}-2k-2\leq 0$. But that only happens if $k\leq 2$. So if $k\geq 3$
or $n\geq 6$, $T$ is not $(2,3)$-cordial.

Case 2. $n$ is odd. Let $n=2k+1$. Without loss of generality, we may assume
that there are $k$ vertices labelled 0 and $k+1$ vertices labelled 1. Thus
there are $\frac{1}{2}k(k-1)$ arcs labelled 0 that connect two vertices
labelled 0 and $\frac{1}{2}(k+1)k$ arcs labelled 0 that connect two vertices
labelled 1. Thus there are at least $k^{2}$ arcs labelled 0. To be
$(2,3)$-cordial we must have that $3k^{2}\leq\frac{n(n-1)}{2}+2$, or
$k^{2}-k-2\leq 0$. That happens only if $k\leq 2$. But, since $n$ is odd,
$n\geq 7$ so $k\geq 3$. Thus, $T$ is not $(2,3)$-cordial.

$0$$0$$1$and$0$$0$$1$$1$$0$$-1$$0$$1$$-1$ Figure 2:  $(2,3)$-Cordial
labellings of 3- tournaments  $T_{4,3}:(2,2,2,0)$Not
(2,3)-cordial$T_{4,4}:(3,1,1,1)$Not
(2,3)-cordial$0$$1$$1$$0$$1$$-1$$-1$$0$$0$$1$$T_{4,1}:(2,2,1,1)$$0$$1$$0$$1$$1$$0$$0$$1$$-1$$-1$$T_{4,2}:(3,2,1,0)$
Figure 3:  $(2,3)$-Cordial labellings of two 4-tournaments and two non (2,3)
cordial 4-tournaments with their out-degree sequences.

###### Lemma 3.4

The tournaments $T_{4,3}$ and $T_{4,4}$ of Figure 3 are not $(2,3)$-cordial.

Proof. Since $T_{4,4}$ is the reversal of $T_{4,3}$, by Lemma 3.1 we only need
show that $T_{4,3}$ is not $(2,3)$-cordial. Further, by Lemma 3.1 we may
assume that the upper left vertex of $T_{4,3}$ in Figure 3 is labelled 0.
Since any permutation of the other three vertices results in an isomorphic
graph we may assume that the upper right vertex is labelled 0 and the bottom
two are labelled 1. This results in one arc labelled 1, three arcs labelled -1
and two arcs labelled 0. Thus $T_{4,3}$ is not $(2,3)$-cordial.

###### Theorem 3.1

Let $T$ be an $n$-tournament. Then $T$ is $(2,3)$-cordial if and only if
$n\leq 5$ and $T$ is not isomorphic to $T_{4,3}$ or $T_{4,4}$.

Proof. Lemmas 3.4, 3.2 and 3.3 together with Figures 2 and 3 establish the
theorem.

We end this section with a couple of observations we labell as corollaries:

###### Corollary 3.1

The property of being (or not being) $(2,3)$-cordial is not closed under
vertex deletion.

Proof. Every tournament on $k$ vertices is a vertex deletion of a tournament
on $k+1$ vertices. Thus, $T_{4,3}$, which is not $(2,3)$-cordial, is a vertex
deletion of a tournament on 5 vertices, which is $(2,3)$-cordial, and this
tournament is a vertex deletion of a tournament on 6 vertices, which is not
$(2,3)$-cordial.

###### Corollary 3.2

The property of being (or not being) $(2,3)$-cordial is not closed under arc
contraction.

Proof. As in the above corollary, every tournament on $k$ vertices is an arc
contraction of a tournament on $k+1$ vertices. Thus, $T_{4,3}$, which is not
$(2,3)$-cordial, is an arc contraction of a tournament on 5 vertices, which is
$(2,3)$-cordial, and this tournament is an arc contraction of a tournament on
6 vertices, which is not $(2,3)$-cordial.

###  3.2 $(2,3)$-Orientations of Wheel Graphs

A wheel graph on $n$ vertices consists of an $(n-1)$-star together with edges
joining the non central vertices in a cycle. A 6-wheel is shown in Figure 4.
Since we are not concerned with digraphs that contain digons, we shall assume
that $n\geq 4$ in this section.

An orientation of the wheel graph with the central vertex being a source/sink
is called an out/in-wheel. If the outer cycle of the wheel is oriented in a
directed cycle the wheel is called a cycle-wheel. If the $n$-wheel is oriented
such that it is both an out-wheel and a cycle-wheel it is called an $n$-cycle-
out-wheel. See Figure 5.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$ Figure 4:  A 6-wheel graph.
$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$ Figure 5:  A 6-cycle-out-wheel
graph.

###### Definition 3.3

Let $W_{n}=(V,A)$ be an $n$-wheel digraph with central vertex $v_{n}$ and with
vertex labelling $f:V\to\\{0,1\\}$ Let $g$ be the induced arc labelling
$g:A\to\\{0,1,-1\\}$ where $g(\overrightarrow{uv})=f(v)-f(u)$. Let $S$ be the
set of arcs incident with the central vertex and let $T$ be the set of arcs
not incident with the central vertex. Define $\Lambda^{S}_{f,g}$ to be the
real triple $\Lambda^{S}_{f,g}(D)=(\alpha_{S},\beta_{S},\gamma_{S})$ where
$\alpha_{S}=|g^{-1}(1)\cap S|,\beta_{S}=|g^{-1}(-1)\cap S|,$ and
$\gamma_{S}=|g^{-1}(0)\cap S|$ and $\Lambda^{T}_{f,g}$ to be the real triple
$\Lambda^{T}_{f,g}(D)=(\alpha_{T},\beta_{T},\gamma_{T})$ where
$\alpha_{T}=|g^{-1}(1)\cap T|,\beta_{T}=|g^{-1}(-1)\cap T|,$ and
$\gamma_{T}=|g^{-1}(0)\cap T|$. Since $S\cup T=A$, the set of all arcs of $D$,
$\alpha_{S}+\alpha_{T}=\alpha,\beta_{S}+\beta_{T}=\beta$, and
$\gamma_{S}+\gamma_{T}=\gamma$, where
$\Lambda_{f,g}(D)=(\alpha,\beta,\gamma)$.

###### Theorem 3.2

Let $W_{n}$ be the $n$-wheel graph with central vertex $v_{n}$, and let
$\overrightarrow{W}$ be a cyclic-out orientation of $W_{n}$. Then
$\overrightarrow{W}$ is not $(2,3)$-cordial.

Proof. We proceed with two cases, the case that $n$ is even then the case that
$n$ is odd. Let $W=(V,A)$ and let $f:V\to\\{0,1\\}$ be a vertex labelling and
$g:A\to\\{0,1,-1\\}$ be the induced arc labelling,
$g(\overrightarrow{uv}=f(v)-f(u)$. Suppose that $f$ and $g$ is a
$(2,3)$-cordial labelling.

Case 1: $n=2k$. Without loss of generality, we may assume that $f(v_{n})=0$.
Thus, $\alpha_{S}=k,\beta_{S}=0$ and $\gamma_{S}=k-1$. Further, since the
orientation is cyclic, $\alpha_{T}=\beta_{T}$. Since
$\alpha-1\leq\beta\leq=\alpha+1$ we have
$\alpha_{T}+k-1=\alpha_{T}+\alpha_{S}-1=\alpha-1\leq\beta=\beta_{T}+\beta_{S}=\beta_{T}=\alpha_{T}$.
Thus $k-1\leq 0$ or $k\leq 1,$ a contradiction since $n\geq 4$.

Case 2: $n=2k+1$. Without loss of generality we may assume that $f(v_{n})=0$.
Since either $k$ or $k+1$ of the non central vertices must be labelled 0, we
have two possibilities: $\alpha_{S}=k$ or $\alpha_{S}=k+1$.

Subcase 1. $\alpha_{S}=k$ Here we have $\gamma_{S}=k$ and $\beta_{S}=0$.
Further, $\alpha_{T}=\beta_{T}$ since $\overrightarrow{W}$ is cyclic. Since
the labelling is $(2,3)$-cordial, $\alpha-1\leq\beta\leq\alpha+1$. Thus
$k+\alpha_{T}-1=\alpha_{S}=\alpha_{T}-1=\alpha-1\leq\beta=\beta_{S}+\beta_{T}=\alpha_{T}$.
That is $k-1\leq 0$ or $k\leq 1$, a contradiction since $n\geq 4$.

Subcase 2. $\alpha_{S}=k+1$ Here we have $\gamma_{S}=k-1$ and $\beta_{S}=0$.
Further, $\alpha_{T}=\beta_{T}$ since $\overrightarrow{W}$ is cyclic. Since
the labelling is $(2,3)$-cordial, $\alpha-1\leq\beta\leq\alpha+1$. Thus
$k+\alpha_{T}=k+1+\alpha_{T}-1=\alpha_{S}+\alpha_{T}-1=\alpha-1\leq\beta=\beta_{S}+\beta_{T}=\alpha_{T}$.
That is $k\leq 0$, a contradiction since $n\geq 4$.

In all cases we have arrived at a contradiction thus we must have that
$\overrightarrow{W}$ is not $(2,3)$-cordial.

###### Lemma 3.5

Let $C$ be an undirected cycle with a $(0,1)$-vertex labelling. Then, there is
an even number of edges in $C$ whose incident vertices are labelled
differently.

Proof. We may assume that the vertex $v_{1}$ is labelled 0. Going around the
cycle, the labelling goes from 0 to 1 then back again to zero. This two step
change must happen a fixed number of times then return to vertex $v_{1}$. Thus
there are an equal number of changes in labelling from 0 to 1 and from 1 to 0.
That is, the total number of changes is an even number.

###### Theorem 3.3

Let $W_{n}$ be the undirected wheel graph on $n$ vertices. Then, $W_{n}$ is
not $(2,3)$-orientable if and only if $n=2k$ for some integer $k$, 4 does not
divide $n$, and $2n-2=3z$ for some integer $z$.

Proof. Let $\overrightarrow{W_{n}}$ be an orientation of the wheel graph on
$n$ vertices with central vertex $v_{n}$. Let $A_{H}$ be the set of arcs
incident with $v_{n}$, and let $A_{R}$ be the arcs not incident with $v_{n}$.
Then $A=A_{H}\cup A_{R}$. Let $f$ be a friendly vertex labelling and $g$ the
induced arc labelling of $\overrightarrow{W_{n}}$. Define ,
$\lambda_{f,H}(x)=|g^{-1}(x)\cap A_{H}|$, and $\lambda_{f,R}(x)=|g^{-1}(x)\cap
A_{R}|$, Define $\lambda_{f}(x)=\lambda_{f,H}(x)+\lambda_{f,R}(x)$, that is
$\lambda_{f}(x)=|g^{-1}(x)|$.

We begin by showing that for $n=2k$ for some integer $k$, $k=2\ell+1$ for some
integer $\ell$, and $2n-2=3z$ for some integer $z$ that $W_{n}$ is not
$(2,3)$-orientable. In this case, We may assume that $f(v_{n})=0$ and
$\lambda_{f,H}(1)+\lambda_{f,H}(-1)=k$, an odd integer. By Lemma 3.5 the
number of arcs that are not incident with $v_{n}$ and labelled either 1 or -1
is even. Thus
$\lambda_{f}(1)+\lambda_{f}(-1)=(\lambda_{f,H}(1)+\lambda_{f,H}(-1))+(\lambda_{f,R}(1)+\lambda_{f,R}(-1))$
is the sum of an even integer and an odd integer, so that
$\lambda_{f}(1)+\lambda_{f}(-1)$ is an odd integer. But since the total number
of arcs is $2n-2=3z$, if $\overrightarrow{W_{n}}$ is $(2,3)$-cordial, we must
have $\lambda_{f}(1)+\lambda_{f}(-1)=2z$, an even integer, a contradiction.
Thus, in this case $W_{n}$ is not $(2,3)$-orientable.

We now show that for all other cases $W_{n}$ is $(2,3)$-orientable. We divide
the proof into three cases, those being whether the total number of edges in
$W_{n}$ is a multiple of three, one more than a multiple of three, or two more
than a multiple of three.

Case 1. $2n-2=3z$ for some integer $z$.

Subcase 1.1. $n=2k$ and $k=2\ell$. In this case, let $f$ be the labelling such
that the labelling of the cycle has $2(z-\frac{k}{2})$ edges incident with
vertices labelled differently. Orient all arcs not incident with $v_{n}$
clockwise around the cycle. Orient half the arcs incident with $v_{n}$ that
are labelled 1 away from $v_{n}$, and half toward $v_{n}$. In this case,
$\lambda_{f,H}(0)=k-1$, and
$\lambda_{f,H}(1)=\lambda_{f,H}(-1)=\frac{k}{2}=\ell$. Further,
$\lambda_{f,R}(1)=\lambda_{f,R}(-1)=z-\frac{k}{2}$. Thus,
$\lambda_{f}(1)=\lambda_{f}(-1)=\lambda_{f,H}(1)+\lambda_{f,R}(1)=\ell+z-\frac{k}{2}=z$.
Thus, we must also have $\lambda_{f}(0)=z$, and that $W_{n}$ is
$(2,3)$-orientable.

Subcase 1.2. $n=2k+1$. In this case proceed as in Subcase 1 labelling the
vertices not incident with $v_{n}$ with an even number of 1’s (either $k$ or
$k+1$). Let $\ell$ be half of this even number. Then, we produce a
$(2,3)$-cordial orientation of $W_{n}$ the same as in Subcase 1.1.

Case 2. $2n-2=3z+1$ for some integer $z$.

Subcase 2.1. $n=2k$, $k=2\ell$. In this case, let $f$ be the labelling such
that the labelling of the cycle has $2(z-\frac{k}{2})$ edges incident with
vertices labelled differently. Orient all arcs not incident with $v_{n}$
clockwise around the cycle. Orient half the arcs incident with $v_{n}$ that
are labelled 1 away from $v_{n}$, and half toward $v_{n}$. In this case,
$\lambda_{f,H}(0)=k-1,\lambda_{f,H}(1)=\lambda_{f,H}(-1)=\frac{k}{2}=\ell$.
Further, $\lambda_{f,R}(1)=\lambda_{f,R}(-1)=z-\frac{k}{2}$. Thus,
$\lambda_{f}(1)=\lambda_{f}(-1)=\lambda_{f,H}(1)+\lambda_{f,R}(1)=\ell+z-\frac{k}{2}=z$.
Thus, we must also have $\lambda_{f}(0)=z+1$, and that $W_{n}$ is
$(2,3)$-orientable.

Subcase 2.2. $n=2k$, $k=2\ell+1$ In this case, let $f$ be the labelling such
that the labelling of the cycle has $2(z-\frac{k-1}{2})$ edges incident with
vertices labelled differently. Orient $\ell$ of the arcs incident with $v_{n}$
that are labelled 1 away from $v_{n}$, and $\ell+1$ of those arcs toward
$v_{n}$. In this case, $\lambda_{f,H}(0)=k-1,\lambda_{f,H}(1)=\ell$ and
$\lambda_{f,H}(-1)=\ell+1$. Further,
$\lambda_{f,R}(1)=\lambda_{f,R}(-1)=z-\frac{k}{2}=z=\ell$. Thus,
$\lambda_{f}(1)=\lambda_{f,H}(1)+\lambda_{f,R}(1)=\ell+z-\ell=z$, and
$\lambda_{f}(-1)=\lambda_{f,H}(-1)+\lambda_{f,R}(-1)=\ell+1+z-\ell=z+1$. Thus,
we must also have $\lambda_{f}(0)=2n-2-(z)-(z+1)=z$, and thus $W_{n}$ is
$(2,3)$-orientable.

Subcase 2.3. $n=2k+1$. In this case proceed as in Subcase 2.1 labelling the
vertices not incident with $v_{n}$ with an even number of 1’s (either $k$ or
$k+1$ depending upon whether $k$ is even or odd). Let $\ell$ be half of this
even number. Then, we produce a $(2,3)$-cordial orientation of $W_{n}$ the
same as in Subcase 2.1.

Case 3. $2n-2=3z+2$ for some integer $z$.

Subcase 3.1. $n=2k$, $k=2\ell$. In this case, let $f$ be the labelling such
that the labelling of the cycle has $2(z-\frac{k}{2})$ edges incident with
vertices labelled differently. Orient all arcs not incident with $v_{n}$
clockwise around the cycle. Orient half the arcs incident with $v_{n}$ that
are labelled 1 away from $v_{n}$, and half toward $v_{n}$. In this case,
$\lambda_{f,H}(0)=k-1,\lambda_{f,H}(1)=\lambda_{f,H}(-1)=\frac{k}{2}=\ell$.
Further, $\lambda_{f,R}(1)=\lambda_{f,R}(-1)=z-\frac{k}{2}$. Thus,
$\lambda_{f}(1)=\lambda_{f}(-1)=\lambda_{f,H}(1)+\lambda_{f,R}(1)=\ell+z-\frac{k}{2}=z$.
Thus, we must also have $\lambda_{f}(0)=z+1$, and that $W_{n}$ is
$(2,3)$-orientable.

Subcase 3.2. $n=2k$, $k=2\ell+1$ In this case, let $f$ be the labelling such
that the labelling of the cycle has $2(z-\frac{k-1}{2})$ edges incident with
vertices labelled differently. Orient $\ell$ of the arcs incident with $v_{n}$
that are labelled 1 away from $v_{n}$, and $\ell+1$ toward $v_{n}$. In this
case, $\lambda_{f,H}(0)=k-1,\lambda_{f,H}(1)=\ell$ and
$\lambda_{f,H}(-1)=\ell+1$. Further,
$\lambda_{f,R}(1)=\lambda_{f,R}(-1)=z-\frac{k}{2}=z=\ell$. Thus,
$\lambda_{f}(1)=\lambda_{f,H}(1)+\lambda_{f,R}(1)=\ell+z-\ell=z$, and
$\lambda_{f}(-1)=\lambda_{f,H}(-1)+\lambda_{f,R}(-1)=\ell+1+z-\ell=z+1$. Thus,
we must also have $\lambda_{f}(0)=z$, and that $W_{n}$ is $(2,3)$-orientable.

Subcase 3.3. $n=2k+1$. In this case proceed as in subcase 3.1 labelling the
vertices not incident with $v_{n}$ with an even number of 1’s (either $k$ or
$k+1$ depending upon whether $k$ is even or odd. Let $\ell$ be half of this
even number. Then, we produce a $(2,3)$-cordial orientation of $W_{n}$ the
same as in Subcase 3.1.

We have now established the theorem.

###  3.3 $(2,3)$-Orientations of Fan Graphs.

A fan graph is isomorphic to a wheel graph with one edge of the cycle deleted.
Thus, by deleting one properly chosen arc from the cycle of a $(2,3)$-oriented
$n$-wheel graph we obtain an orientation of the $n$-fan graph that is
$(2,3)$-cordial. Note that if there are at least as many arcs labelled $x$
($x=1,-1$ or $0$) as any other labelling, the properly chosen arc would be in
the set of arcs labelled $x$.) Thus there is only one case to consider, the
case where $2n-2=3z,n=2k$ and $k=2\ell+1$ for some $z,k$, and $\ell$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{2\alpha-1}$$v_{2\alpha}$$v_{2\alpha+1}$$v_{s-1}$$v_{s}$$v_{s+1}$$v_{n-1}$$v_{n}$$\dots$$\cdots$$\vdots$$s=k+\alpha$001101111000
Figure 6:  $F_{n}$ with oriented cycle arcs.

###### Theorem 3.4

Let $n\geq 5$ and let $F_{n}$ be the $n$-fan graph with central vertex
$v_{1}$, that is the edges not on the cycle are all incident to $v_{1}$. Let
$\overrightarrow{F}$ be a cyclic-out orientation of $F_{n}$. Then
$\overrightarrow{F}$ is not $(2,3)$-cordial.

Proof. As for wheel graphs, the number of arcs labelled 1 on the cycle is
equal to the number of arcs labelled -1 and there are at least two arcs
labelled 1 on the interior of the cycle. thus, the number of arcs labled 1 in
$\overrightarrow{F}$ is at least two more that the arcs labelled -1 in
$\overrightarrow{F}$. That is $\overrightarrow{F}$ is not $(2,3)$-cordial.

###### Theorem 3.5

Let $F_{n}$ be the fan graph on $n$ vertices, $2n-3=3z+2$, $n=2k$ and
$k=2\ell+1$ for some integers $k,\ell,$ and $z$. Then there is an orientation
of $F_{n}$ that is $(2,3)$-cordial.

Proof. Let $\alpha=z-\ell+1$, and define $f:V\to\\{0,1\\}$ by $f(v_{2i-1})=0,$
$i=1,\dots,\alpha$, $f(v_{2i})=1,i=1,\dots,\alpha$,
$f(v_{2\alpha+i})=1,i=1,\dots,k-\alpha$, and
$f(v_{k+\alpha+i})=0,i=1,\dots,k-\alpha$, Note that
$(k-\alpha)+(k+\alpha)=2k=n$, so all vertices are labelled. Orient the cycle
clockwise, so that the oriented cycle is $\overrightarrow{v_{1}v_{2}}$,
$\overrightarrow{v_{2}v_{3}}$, …, $\overrightarrow{v_{n-1}v_{n}}$,
$\overrightarrow{v_{n}v_{1}}$. See Figure 6 where the vertex labellings are
outside the cycle.

Now, orient $\ell$ of the inner arcs from $v_{1}$ to arcs labelled 1 (except
for $v_{2}$ which is not an inner arc) away from $v_{1}$ and the remaining
$\ell$ such arcs inward so that we get $\overrightarrow{F_{n}}=(V,A)$. Let
$g:A\to\\{0,1,-1\\}$ be the induced labelling,
$g(\overrightarrow{uv})=f(v)-f(u)$. Then there are $\alpha$ arcs labelled $1$
on the cycle, $\alpha$ arcs labelled $-1$ on the cycle, $\ell$ of the inner
arcs are labelled $-1$ and $\ell$ of the inner arcs are labelled $1$. Thus, in
all of $\overrightarrow{F_{n}}$ there are $\alpha+\ell=z+1$ arcs labelled -1,
$\alpha+\ell=z+1$ arcs labelled 1 and (hence) $z$ arcs labelled $0$. That is,
this orientation of $F_{n}$ is $(2,3)$-cordial.

###  3.4 Extremes of $(2,3)$ Cordiality

As seen in section 3, complete graphs are not $(2,3)$-orientable if $n\geq 6$.
So the question arises: How large can a $(2,3)$-orientable graph be (how many
edges)? Or: How large can a $(2,3)$-cordial digraph be? That question was
fully answered by M. A. Santana in [6] For completeness we shall include the
proofs of his results.

###### Theorem 3.6

[6, Theorem 3.1] Every simple directed graph is $(2,3)$ cordial if and only if
there exists a friendly vertex labelling such that about $\frac{1}{3}$ of the
edges are connected by vertices of the same label.

Proof. Let $G$ be a graph such that there exists a friendly labelling on $G$
such that about $\frac{1}{3}$ of the edges are connected by vertices of the
same labell. This would mean about $\frac{2}{3}$ of the edges are connected by
vertices of different labells, and therefore arcs may be assigned such that
$G$ is cordial. Now let $H$ be a graph such that there does not exist a
friendly labelling on $H$ such that such that about $\frac{1}{3}$ of the edges
are connected by vertices of the same labell then there will be no way $H$ can
be cordial since only then could about one third of the edges be labelled 0..

Santana’s application of Theorem 3.6 is

###### Theorem 3.7

[6, Theorem 4.2] Given a directed graph $G=(V,E)$ with vertex set $V$ and
$n=|V|$ with $n\geq 6$, and edge set $E$, the maximum size of $E$ such that
$G$ is cordial for any given $n$ is

$|E|_{max}=\displaystyle{n\choose
2}-Z+\Bigg{\lceil}\frac{1}{2}\Big{(}\displaystyle{n\choose
2}-Z\Big{)}\Bigg{\rceil}\\\ Z\\\ =\displaystyle{\lceil\frac{n}{2}\rceil\choose
2}+\displaystyle{\lfloor\frac{n}{2}\rfloor\choose 2}.$ (1)

000111 Figure 7: A complete graph. Dashed Lines represent edges labelled zero
regardless of arc orientation

Proof. From section 3 we have that for any tournament with $n\leq 5$ there
exists a cordial labelling, save for the case when $n=4$ thus we begin with a
complete graph with $n\geq 6$. Recall that the number of vertices on a
complete graph is $n\choose 2$. Due to our cordial labelling the number of
edges with an induced labelling of 0 will be our $Z$. This is because it will
be the number of edges connected by two vertices of the same label, as shown
in Figure 7. If $n$ is even that will mean that $Z=2{\frac{n}{2}\choose 2}$,
i.e., it will be the number of edges on two $\frac{n}{2}$ complete graphs
represented by the labellings of ones and zeros. The floor and ceiling
function in $(1)$ simply account for the odd case.
For every tournament with $n\geq 6$ vertices, $Z>\frac{1}{3}{n\choose 2}$.
Therefore some of the arcs labelled zero will need to be removed to get a
cordial graph. How many arcs need to be removed is going to be equal to how
much greater $Z$ is than the number of half the number of arcs not labelled
zero. By the definition of a directed cordial graph we know that $Z$ can be
larger than $\alpha$ or $\beta$ and we can still have a cordial graph, hence
the ceiling function.

As mentioned in the introduction, the smallest non $(2,3)$-cordial digraph is
an orientation of Xn, three parallel arcs. A question may be asked: What is
the minimum number of arcs in a non $(2,3)$-cordial digraph that has no
isolated vertices?

##  4 Conclusions

In this article we have shown that the only tournaments that are
$(2,3)$-cordial are when $n\leq 5$ and then not for two 4-tournaments. That
except for one case when $n$ is even, the $n$-wheel graph has an orientation
that is $(2,3)$-cordial and that at least one orientation of any wheel graph
is not $(2,3)$-cordial. Further, we show that every fan graph has a
$(2,3)$-cordial orientation, and as for wheel graphs there is always an
orientation of the $n$-fan that is not $(2,3)$-cordial.

## References

  * [1] L. B. Beasley, Cordial Digraphs, In Press.
  * [2] I. Cahit, Cordial graphs: A weaker version of graceful and harmonious graphs, Ars Comb. 23(1987) 201-208.
  * [3] M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183-194.
  * [4] O. Pechenik and J. Wise, Generalized graph cordiality, Discuss. Math. Graph Theory 32(2012) 557-567.
  * [5] E Salehi, PC-labelling of a graph and its PC-set, Bull. Ins.t Comb. Appl. 58(2010) 112-121.
  * [6] M. A. Santana, J. M. Mousley, D. E. Brown, and L. B. Beasley, (2,3)-Cordial Trees and Paths, Preprint.

Authors email addresses: LeRoy B. Beasley<EMAIL_ADDRESS>Manuel Santana<EMAIL_ADDRESS>Jonathan Mousley,
<EMAIL_ADDRESS>David E. Brown<EMAIL_ADDRESS>


# Your Graph Recommender is Provably a Single-view Graph Contrastive Learning

Wenjie Yang<EMAIL_ADDRESS>Fudan UniversityShanghaiChina ,
Shengzhong Zhang<EMAIL_ADDRESS>Fudan UniversityShanghaiChina ,
Jiaxing Guo<EMAIL_ADDRESS>Fudan UniversityShanghaiChina and
Zengfeng Huang<EMAIL_ADDRESS>Fudan UniversityShanghaiChina

(2018)

###### Abstract.

Graph recommender (GR) is a type of graph neural network (GNNs) encoder that
is customized for extracting information from the user-item interaction graph.
Due to its strong performance on the recommendation task, GR has gained
significant attention recently. Graph contrastive learning (GCL) is also a
popular research direction that aims to learn, often unsupervised, GNNs with
certain contrastive objectives. As a general graph representation learning
method, GCLs have been widely adopted with the supervised recommendation loss
for joint training of GRs. Despite the intersection of GR and GCL research,
theoretical understanding of the relationship between the two fields is
surprisingly sparse. This vacancy inevitably leads to inefficient scientific
research.

In this paper, we aim to bridge the gap between the field of GR and GCL from
the perspective of encoders and loss functions. With mild assumptions, we
theoretically show an astonishing fact that _graph recommender is equivalent
to a commonly-used single-view graph contrastive model_. Specifically, we find
that (1) the classic encoder in GR is essentially a linear graph convolutional
network with one-hot inputs, and (2) the loss function in GR is well bounded
by a single-view GCL loss with certain hyperparameters. The first observation
enables us to explain crucial designs of GR models, e.g., the removal of self-
loop and nonlinearity. And the second finding can easily prompt many cross-
field research directions. We empirically show a remarkable result that the
recommendation loss and the GCL loss can be used interchangeably. The fact
that we can train GR models solely with the GCL loss is particularly
insightful, since before this work, GCLs were typically viewed as unsupervised
methods that need fine-tuning. We also discuss some potential future works
inspired by our theory.

Graph Neural Network, Graph Recommendation, Graph Contrastive Learning

††copyright: acmlicensed††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Computing methodologies Machine learning

##  1\. Introduction

Graph data are ubiquitous in real-world applications, with recommendation
systems(He et al., 2020; Wang et al., 2019; Wu et al., 2021; Yu et al., 2022)
serving as one of the most representative examples. In recommendation systems,
users and items can be considered as nodes in a graph, and their interactions
form the edges between these nodes. By modeling the use-item interactions in
this way, the task of recommending user interests transforms into a prediction
problem on graph. Several early works are proposed to tackle this
collaborative filtering task, such as SVD++ (Koren, 2008) and Neural Attentive
Item Similarity (NAIS) (He et al., 2018). In recent years, a type of powerful
graph encoder called graph neural network has been applied to graph
recommendation (He et al., 2020; Wu et al., 2021). GNNs enable each node to
gather information from its neighboring nodes through the message-passing
operation, and then utilize the aggregated representations to learn downstream
tasks. However, node features are often unavailable in the context of
collaborative filtering. To address this issue and cater to personalized
recommendations, LightGCN (He et al., 2020) is proposed, and soon becomes the
most commonly used baseline model. Instead of transformation matrices,
LightGCN first initializes a learnable embedding for each node. It then
propagates these embeddings on the graph and computes the loss. Despite its
effectiveness, we are surprised to find that the details of LightGCN lack
sufficient theoretical explanations. For instance, _what are the differences
between LightGCN and other GNN encoders, e.g.,(Kipf and Welling, 2016)? Why do
the modifications made in LightGCN lead to its effectiveness in graph
recommendation tasks?_ In this paper, we show that these research questions
can be rigorously analysed by a simple bridge between encoders.

Recent GR models also include graph contrastive learning to boost their
performance (Wu et al., 2021; Yu et al., 2022, 2023). The primary idea of GCLs
is to learn (often unsupervised) graph encoders by minimizing the distance
between positive pairs and maximizing the distance between negative pairs, and
it has been a popular research direction even outside the GR field (Zhang et
al., 2020; Zhu et al., 2021a, 2020). Despite this overlap between GCL and GR,
research conducted on these two fields is rather parallel. For example, the
scalability issue is studied on GCL by some works (Zheng et al., 2022; Zhang
et al., 2023), and is also studied on GR by some other works (Zhang et al.,
2024; Chen et al., 2024). In this paper, we theoretically show some
astonishing results that bridge the gap between GCL and GR. With these
findings, we can easily identify redundancies in these two fields and avoid
inefficient research efforts. Specifically, we show:

_Graph recommender is provably a single-view graph contrastive learning
model._

This finding answers lots of research questions and brings novel insights. We
can immediately know that the recommendation loss and the single-view GCL loss
can be used interchangeably, which yields a new GCL method and a new way to
train GR models. The fact that we can train GR models solely with the GCL loss
is particularly interesting since GCLs were typically viewed as unsupervised
methods in previous works. We anticipate that our results will lead to
numerous novel research works. Research on GCL, such as scalability and
negative sample mining, can be transferred to GR, and vice versa. Our
contributions can be summarized as follows:

  * •

We carefully review the GR and GCL fields and present the application of GCL
in GR. We include the training pipeline of both directions in our paper,
making it self-contained and suitable as reading material for beginners.

  * •

We demonstrate the equivalence between GR and GCL from the perspectives of
both encoders and loss functions. This discovery not only provides theoretical
explanations for the effectiveness of existing models but also deepens our
understanding of both directions. Most importantly, based on our theory,
research in GCL and GR can be mutually inspired by each other, and new
directions can be prompted.

  * •

We conduct extensive experiments to demonstrate the interchangeability of GCL
and GR losses. The fact that training graph recommender models solely use GCL
loss is remarkable because previous research often consider GCL as an
unsupervised loss function that must be used in conjunction with downstream
tasks. In the field of recommendation, GCL has been regarded as unsuitable
even for pre-training. However, our theory easily explains why using GCL loss
alone is sufficient for training graph recommender models.

Outline. In Section 2, we discuss the related works. To ensure the self-
contained nature of this paper, we provide separate introductions to the
algorithmic processes of GR and GCL for authors unfamiliar with these fields
in Section 3. Section 4 presents the main conclusions of the article,
highlighting the establishment of connections between encoders and the proof
of equivalence between losses. In Section 5, we demonstrate experimental
results to further validate our theoretical findings and provide examples of
new research directions.

##  2\. Related Work

Graph Contrastive Learning. Graph contrastive learning is a powerful tool for
graph representation learning. There are a two lines of research on GCLs,
namely single-view GCLs and multi-view GCLs. Similar to contrastive learning
in the computer vision field, multi-view GCLs (e.g., (Zhu et al., 2020, 2021b;
Zhang et al., 2021; Zheng et al., 2022; Chen et al., 2023)) perform data
augmentations to generate corrupted views of the target graph and consider
synthetic nodes originating from the same node as positive pairs, while
treating the remaining nodes as negative samples. GRACE (Zhu et al., 2020) is
a representative multi-views GCL, it performs edge dropping and feature
masking data augmentation, then choose negative pair from both inter-view and
intra-view. GCA (Zhu et al., 2021b) is an improved version of GRACE, which
performs adaptive augmentation instead of the handcrafted ones. There are also
works like CCA-SSG (Zhang et al., 2021), which takes the perspective of
canonical correlation analysis. Scalability issue has also been studied, GGD
(Zheng et al., 2022) use group discrimination instead of individual level.
There are also more sophisticated model, like PolyGCL (Chen et al., 2023) that
learns spectral polynomial filters.

With the graph information, one can also do single-view GCLs (e.g., (Hamilton
et al., 2017; Zhang et al., 2020; Zhu et al., 2021a; Wang et al., 2022)),
which consider adjacent nodes as positive pairs and unconnected nodes as
negative samples. SCE (Zhang et al., 2020), motivated by the classical
sparsest cut problem, only uses negative samples from unconnected nodes. It is
the first GCL work that does not rely on data augmentation. COLES (Zhu et al.,
2021a) further improves SCE by treating connected nodes as positive samples.
Single-view GCLs are typically more efficient and less expensive to train
compared to multi-views GCLs.

The original GCLs follow the pre-train then fine-tune paradigm, they first
learn representations with the unsupervised contrastive learning, than fit a
linear classifier for the downstream task. Many research works have been
conducted on GCLs, including hard negative mining (Xia et al., 2022) and
scalability (Zhang et al., 2023). With the connection established between GCL
and GR, these studies can be easily applied to graph recommender systems.

Graph Recommender. Collaborative filtering (CF) is one of the most classical
methods for recommender systems. The primary idea of CF is to filter out items
that a user might like with user-item interactions. In recent years, GNNs have
been incorporated into CF-based recommender system. These graph recommender is
able to learn complex structural pattern, and they are more expressive than
traditional CF. For example, an early work NGCF (Wang et al., 2019) performs
message-passing on the user-item bipartite graph and trains embeddings with
recommendation loss. Afterward, LightGCN (He et al., 2020) removes the non-
linear activation functions and feature transformations in GR, simplifying the
model while achieving promising performance. Despite LightGCN becoming the
mainstream graph recommender, we are astonished to find that previous works
have obtained minimal theoretical understanding regarding these
simplifications.

Graph contrastive learning is also used in graph recommender. To the best of
our knowledge, they all use multi-views GCLs. SGL (Wu et al., 2021) is the
first work to incorporate the InfoNCE (Gutmann and Hyvärinen, 2010) loss into
GR. Following SGL, SimGCL (Yu et al., 2023) is proposed to discard graph
augmentation, achieving a more efficient model without sacrificing
performance. Unlike traditional GCLs, the contrastive learning loss in these
papers is learnt jointly with the downstream recommendation loss. There is
also a work called CPTPP (Yang et al., 2024) that studies the new prompt-
tuning framework. However, to the best of our knowledge, our paper is the
first work that demonstrate the feasibility of training a viable GR model
solely using GCL. ContraRec (Wang et al., 2023) is a recent work that also try
to build connection between the recommendation loss and the contrastive
learning loss. Unlike our work, ContraRec focus on the sequential
recommendation, which results in a compromising contrastive loss that is not
used in application. Furthermore, the experiments in ContraRec are conducted
used an extended version of the recommendation loss, while our paper shows
that training GR with off-the-shelf single-view GCLs is possible. We believe
that the latter brings more insight, since GCLs were viewed as unsupervised
losses in the past.

##  3\. Preliminaries

We consider the undirected graph $G=(\mathbf{A},\mathbf{X})$, where
$\mathbf{A}\in\\{0,1\\}^{n\times n}$ is the adjacency matrix, and
$\mathbf{X}\in\mathbb{R}^{n\times f}$ is the feature matrix. For GR, the
bipartite adjacency matrix can also be formulated as

(1) $\mathbf{A}=\begin{pmatrix}\mathbf{0}&\mathbf{R}\\\
\mathbf{R}^{T}&\mathbf{0}\end{pmatrix},$

where $\mathbf{R}$ is the user-item interaction matrix. The feature matrix
$\mathbf{X}$ is not available in GR. The set of vertices and edges is
represented as $V$ and $E$. We also denote $n=|V|$ and $m=|E|$. The degree of
the $i$-th node is $d_{i}$, and the diagonal degree matrix is $\mathbf{D}$.
The symmetrically normalized matrix is
$\tilde{\mathbf{A}}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, and the
symmetrically normalized matrix with self-loop is
$\hat{\mathbf{A}}=(\mathbf{D}+\mathbf{I})^{-1/2}(\mathbf{A}+\mathbf{I})(\mathbf{D}+\mathbf{I})^{-1/2}$.
The neighbor set of a node $x$ is denoted as $\mathcal{N}_{x}$. In both GR and
GCL, the negative samples are randomly selected from all unconnected nodes, we
denote the negative sample set as $\mathcal{N}_{x}^{-}$ and
$K=|\mathcal{N}_{x}^{-}|$. The Laplacian matrix of $\mathbf{A}$ is
$\mathbf{L}=\mathbf{D}-\mathbf{A}$. We also have $\mathbf{L}^{-}$ as the
randomly generated Laplacian matrices capturing the negative sampling.

###  3.1. GCN

Graph convolutional network (GCN) (Kipf and Welling, 2016) is the most common
GNN encoder. Given the node representations $\mathbf{H}^{(l)}$ of the $l$-th
layer, the next layer representations are computed as follow:

(2)
$\mathbf{H}^{(l+1)}=\sigma(\hat{\mathbf{A}}\mathbf{H}^{(l)}\mathbf{W}^{(l)}),$

where $\mathbf{W}^{(l)}$ is a learnable parameter matrix and $\sigma(\cdot)$
is the activation function (e.g., ReLU). GCNs consist of multiple convolution
layers, with the initial representations $\mathbf{H}^{(0)}=\mathbf{X}$.

###  3.2. LightGCN

LightGCN (He et al., 2020) is a widely used GR model. Unlike GCN, LightGCN
trains user and item embeddings instead of transformation matrix. Let the
$0$-th embedding matrix be $\mathbf{E}^{(0)}\in\mathbb{R}^{(n_{u}+n_{i})\times
d}$, where $n_{u}$ and $n_{i}$ are the numbers of users and items,
respectively. For GR, we also denote $n=n_{u}+n_{i}$. The propagation rule of
LightGCN is formulated as follow:

(3) $\mathbf{E}^{(l+1)}=\tilde{\mathbf{A}}\mathbf{E}^{(l)}.$

The final embedding matrix is a weighted average of each layer, i.e.,

(4)
$\mathbf{E}=\sum_{l=0}^{L-1}\alpha_{l}\tilde{\mathbf{A}}^{l}\mathbf{E}^{(0)},$

where $L$ is the number of layers. For simplicity, we set
$\alpha_{l}=\frac{1}{L+1}$ throughout this paper.

In LightGCN, the score between a pair of user and item is the inner product of
their final embedding:

(5) $\hat{y}_{ui}=e_{u}^{T}e_{i},$

where $e_{u}$ and $e_{i}$ are embeddings of $u$ and $i$ from $\mathbf{E}$. The
model can be trained using the bayesian personalized ranking (BPR) loss
(Rendle et al., 2012):

(6)
$\mathcal{L}_{\mathrm{BPR}}=-\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\ln\sigma_{\mathrm{s}}(\hat{y}_{ui}-\hat{y}_{uj})+\lambda||\mathbf{E}^{(0)}||^{2},$

where $\sigma_{\mathrm{s}}(\cdot)$ is the sigmoid function and $\lambda$
controls the $L_{2}$ regulation.

In order to make our paper self-contained, we provide the pipeline of LightGCN
for readers who are unfamiliar with GR. Please refer to Algorithm 1 for
details.

Algorithm 1 The pipeline of LightGCN

1:The training adjacency matrix $\mathbf{A}$, the number of hidden dimensions
$d$, the regulation coefficient $\lambda$.

2:Initialize the embedding lookup table
$\mathbf{E}^{(0)}\in\mathbb{R}^{n\times d}$.

3:while not converge do $\triangleright$ Training

4: Propagate embeddings $\mathbf{E}^{(0)}$ with (3).

5: Get final embeddings $\mathbf{E}$ with (4).

6: Compute the loss $\mathcal{L}_{\mathrm{BPR}}$ with (6).

7: Back propagation and update the embeddings $\mathbf{E}^{(0)}$.

8:end while

9:for $(u,i)$ in the test set do $\triangleright$ Testing

10: Compute the score $\hat{y}_{ui}=e^{T}_{u}e_{i}$.

11:end for

12:Sort the test set by $\hat{y}$ and compute the metrics.

###  3.3. (Single-view) GCLs

GCL is a class of unsupervised graph representation learning method. It aims
to learn the embeddings of the graph by distinguishing between similar and
dissimilar nodes. In this paper, we mainly focus on single-view GCLs, in which
a GCN model, denoted as $\mathrm{GCN}(\mathbf{A},\mathbf{X})$, is trained on
the original graph $G$ without data augmentation. We take COLES (Zhu et al.,
2021a) as an example of single-view GCL. Its objective is as follow:

(7)
$\begin{split}\mathcal{L}_{\mathrm{COLES}}&=\mathrm{Tr}(\mathbf{E}^{T}\mathbf{L}\mathbf{E})-\beta\mathrm{Tr}(\mathbf{E}^{T}\mathbf{L}^{-}\mathbf{E})\\\
&=\mathcal{L}_{\mathrm{COLES}}^{+}-\beta\mathcal{L}_{\mathrm{COLES}}^{-},\end{split}$

where $\beta$ is a hyperparameter. For convenience, we divide the loss
function into two parts.

Most of GCL researches use node classification as the downstream task (e.g.,
(Zhang et al., 2020; Zhu et al., 2021a)). They first learn representations
with unsupervised objectives, then train a separate classifier with the
downstream task loss. We also provide a pipeline of ordinary GCLs in Algorithm
2.

Algorithm 2 The pipeline of ordinary GCLs

1:The adjacency matrix $\mathbf{A}$, the feature matrix $\mathbf{X}$, the
number of layers $L$, the negative coefficient $\beta$, labels of certain
downstream task $y$.

2:Pre-compute the Laplacian matrix $\mathbf{L}$ and sample the negative
Laplacian matrix $\mathbf{L}^{-}$.

3:Initialize the learnable parameters $\mathbf{W}^{(l)},\forall l\in[L]$.

4:while not converge do $\triangleright$ Pre-training

5: Get the final embedding $\mathbf{E}$ with (2).

6: Compute the unsupervised loss $\mathcal{L}_{\mathrm{COLES}}$ with (7).

7: Back propagation and update the parameters $\mathbf{W}^{(l)}$.

8:end while

9:Get and freeze the embedding $\mathbf{E}$.

10:Get train/test split. $\triangleright$ Downstream Task

11:Fit a linear (or MLP) classifier on the training set with lables $y$ and
embeddings $\mathbf{E}$.

12:Predict labels for the test set with the linear classifier.

In GR, there are also models that utilize GCLs (e.g., (Wu et al., 2021; Yu et
al., 2023)). However, these models are jointly learned with the BPR and
contrastive loss, instead of the pre-training then fine-tuning paradigm.
Specifically, they simply add certain contrastive loss into Line 5 of
Algorithm 1.

##  4\. Theoretical Analysis

In this section, we theoretically bridge the gap between GCL and GR. We start
with a mild assumption.

###### Assumption 4.1.

Throughout this paper, we assume the embedding of each node is normalized,
i.e., $||e_{x}||=1,\forall x\in V$.

The assumption of normalized embedding is widely used in deep learning theory
(e.g., (Huang et al., 2022)). In GCL, it is also easy to normalized the
embeddings for downstream tasks. However, naive adoption of normalization may
hinder the performance of recommender system. Fortunately, a recent work
(Chung et al., 2023) proposes a debiasing regulation to address this issue. In
this paper, we conduct GR experiments with normalized embeddings and this
regulation to ensure the consistency between theory and practice.

###  4.1. The equivalence between encoders

We first investigate the duality between GCN and LightGCN encoder. The results
help us gain a better understanding of why LightGCN works well in GR. A well-
known fact is that personalized embeddings can be viewed as a linear layer
with one-hot inputs. Therefore, we have the following proposition.

###### Proposition 4.2.

Let users and items have one-hot features, LightGCN is a GCN without non-
linearity and self-loop.

###### Proof.

For GR, the feature matrix $\mathbf{X}$ is not available. If we let
$\mathbf{H}^{(0)}=\mathbf{X}=\mathbf{I}$, and the learnable parameter matrix
$\mathbf{W}^{(0)}=\mathbf{E}^{(0)}$. The last layer embeddings of LightGCN are
simply:

(8) $\mathbf{E}^{(L)}=\tilde{\mathbf{A}}^{L}XW^{(0)}.$

This is equivalent to the embeddings of GCN without non-linearity and self-
loop. ∎

It is not difficult to understand why LightGCN works without self-loop. In GR,
the average of embeddings in each layer is adopted instead of only the last
layer. Thus, each node is still able to acquire its own information, only with
different weights. The original paper of LightGCN (He et al., 2020) shows this
under a compromising form where the symmetric normalization is discarded.
Alternatively, we can use the relative influence in (Chen et al., 2022;
Lampert and Scholtes, 2023) to show this.

###### Lemma 4.3 (The relative influence in GNN (Lampert and Scholtes, 2023)).

If the GNN passes messages along all $k$-length walks from $u$ to $v$ with
equal probability, then the relative influence of input feature $e^{(0)}_{u}$
on node output $e^{(k)}_{v}$ is on the average

(9) $\mathbb{E}\left(\frac{\partial e^{(k)}_{v}/\partial
e^{(0)}_{u}}{\sum_{u^{\prime}\in V}\partial e^{(k)}_{v}/\partial
e^{(0)}_{u^{\prime}}}\right)=\frac{\mathbf{A}_{uv}^{k}}{\sum_{u^{\prime}\in
V}\mathbf{A}_{u^{\prime}v}^{k}},$

where $\mathbf{A}_{uv}^{k}$ computes the number of walks of length $k$ from
node $u$ to $v$.

With lemma 4.3, we can compare the relative influence of each nodes and its
own output between the self-loop added GNN and the average embedding GNN.
Specifically, for GNNs with self-loop, the relative influence is
$\frac{\tilde{\mathbf{A}}_{uu}^{L}}{\sum_{u^{\prime}\in
V}\tilde{\mathbf{A}}_{u^{\prime}u}^{L}}$. For GNNs with average embeddings as
the output, like LightGCN, we have
$\sum_{l=0}^{L-1}\frac{\mathbf{A}_{uu}^{l}}{\sum_{u^{\prime}\in
V}\mathbf{A}_{u^{\prime}u}^{l}}$. Consider a 2-layer GNN, the former becomes
$\frac{1+d_{u}}{1+3d_{u}+d_{u}^{(2)}}$, and the later becomes
$1+\frac{d_{u}}{d_{u}+d_{u}^{(2)}}$, where $d_{u}^{(2)}$ is the number of
2-hop neighbors of node $u$. We observe that the self-loop added GNN receive
less information from its own input than the average embedding GNN. We also
compare these two variants empirically and present the results in Section 5.3.

However, comprehending the removal of non-linearity poses greater challenges
as it plays a crucial role in deep learning. With Proposition 4.2, we know
that this is due to the fact that one-hot features do not contain rich
information, and non-linearity in GNN is only useful when the node attributes
are far more informative than the graph structure (Wei et al., 2022).
Formally, (Wei et al., 2022) considers the contextual stochastic block model
(CSBM) (Deshpande et al., 2018). In CSBM, labels are first sampled from
Rademacher distribution. Based on the node labels, node features are sampled
from $\mathbb{P}_{1}$ and $\mathbb{P}_{-1}$. We further set
$\mathbb{P}_{1}=\mathcal{N}(\mu,1/d)$ and
$\mathbb{P}_{-1}=\mathcal{N}(\nu,1/d)$ for some $\mu,\nu\in\mathbb{R}^{d}$.
For the node pair $(u,v)$ subject to $y_{u}=y_{v}$, the probability that an
edge exists is $p$. If $y_{u}\neq y_{v}$, the probability is $q$. This model
can be translated into the GR task by viewing each label as whether the item
is positive or negative for a particular user $u$, and the edges between items
as ”item-user-item” meta-paths. Denote the non-linear propagation model as
$\mathcal{P}$, and the optimal linear counterpart as $\mathcal{P}^{l}$, we can
compute the signal-to-noise ratio (SNR) $\rho_{r}$ and $\rho_{l}$.

###### Theorem 4.4 (The SNR of nonlinear and linear propagation model (Wei et
al., 2022)).

Assume the structure information $\mathcal{S}(p,q)=(p-q)^{2}/(p+q)$ is
moderate, i.e., $\mathcal{S}(p,q)=\omega_{n}(\frac{(\ln n)^{2}}{n})$ and
$\frac{S(p,q)}{|p-q|}\not\to_{n}1$. And
$\sqrt{d}||\mu-\nu||=\omega_{n}(\sqrt{\ln n/S(p,q)n})$, we have:

  * •

I. Limited Attributed Information: When
$\sqrt{d}\|\mu-\nu\|=\mathcal{O}_{n}(1)$,

(10) $\displaystyle\rho_{r}=\Theta_{n}(\rho_{l}),$

Further, if $\sqrt{d}\|\mu-\nu\|_{2}=o_{n}(|\log(p/q)|)$,
$\rho_{r}/\rho_{l}\to_{n}1$;

  * •

II. Sufficient Attributed Information: When
$\sqrt{d}\|\mu-\nu\|_{2}=\omega_{n}(1)$ and $\sqrt{d}\|\mu-\nu\|_{2}=o_{n}(\ln
n)$, we have

(11) $\displaystyle\rho_{r}$
$\displaystyle=\omega_{n}(\min\\{\exp(d\|\mu-\nu\|_{2}^{2}/3),nS(p,q)d^{-1}\|\mu-\nu\|_{2}^{-2}\\}\cdot\rho_{l})$
$\displaystyle=\omega_{n}(\rho_{l}).$

Theorem 4.4 shows that when attributed information is limited, the SNR of
regular GNNs with nonlinear propagation has the same order as its optimal
linear counterpart. LightGCN in GR tasks clearly falls into this category.
Since orders are not correlated to whether the item is positive or negative,
the expectation of node inputs are the same: $\mu=\nu=\frac{1}{n}\mathbf{1}$,
and $\sqrt{d}||u-v||=0=O_{n}(1)$.

###  4.2. The equivalence between loss functions

(a) Yelp2018

(b) Amazon-Kindle

(c) Alibaba-iFashion

Figure 1. The ratio of negative coefficient $\beta_{u}/\beta_{l}$ on three
real-world datasets.

We then investigate the equivalence between the loss functions, establishing a
bridge between GR and GCL, which can simultaneously facilitate the advance of
both fields. We first present the following lemma, the proof is deferred to
Appendix A.

###### Lemma 4.5.

The trace of the quadratic form of the Laplacian matrix is equal to the
smoothness on the graph, i.e.,

(12)
$\mathrm{Tr}(\mathbf{E}^{T}\mathbf{L}\mathbf{E})=\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}||e_{u}-e_{i}||^{2}.$

Lemma 4.5 makes $\mathcal{L}_{\mathrm{COLES}}$ easier to deal with, and can be
found in standard textbooks, e.g., (Hamilton, 2020). We then present our
result in the following main theorem, the proof is deferred to Appendix A.

###### Theorem 4.6.

With the normalized embeddings, we have the following equivalence:

(13)
$\begin{split}\frac{K}{2}\mathcal{L}_{\mathrm{COLES}}^{+}-\frac{d_{\mathrm{min}}}{2}\mathcal{L}_{\mathrm{COLES}}^{-}+d_{\mathrm{min}}Kn_{u}-mK\leq\mathcal{L}_{\mathrm{BPR}}\\\
\leq\frac{K}{2}\mathcal{L}_{\mathrm{COLES}}^{+}-\frac{d_{\mathrm{max}}}{4}\ln(\frac{2e^{2}}{e^{2}+1})\mathcal{L}_{\mathrm{COLES}}^{-}+\mathrm{constant},\end{split}$

where
$\mathrm{constant}=d_{\mathrm{max}}Kn_{u}\ln(\frac{2e^{3}+2e}{e^{2}+1})-mK$.

In GR researches, the number of negative samples is often set as one, i.e.,
$K=1$. Therefore, the hyperparameter that control the effect of the negative
terms $\beta$ is $\beta_{l}=d_{\mathrm{min}}$ for the lower bound and
$\beta_{u}=\frac{d_{\mathrm{max}}}{2}\ln(\frac{2e^{2}}{e^{2}+1})$ for the
upper bound. If $\beta_{u}/\beta_{l}$ is close enough to $1$, we can conclude
that the equivalence of GR and GCL loss is good. We empirically show this on
three real-world datasets, Yelp2018, Amazon-Kindle and Alibaba-iFashion. We
use 1,000 batches to get the kernel density estimation of
$\beta_{u}/\beta_{l}$, and plot the distribution in Figure 1. We observe that
$\beta_{u}/\beta_{l}$ is roughly concentrated around $1$, which indicates the
corresponding negative coefficient of the upper bound and the lower bound are
similar.

It can be concluded from Theorem 4.6 that, the performance of GNNs on the
recommendation task, namely $\mathcal{L}_{\mathrm{BPR}}$, can be well bounded
by certain weighted versions of the contrastive loss
$\mathcal{L}_{\mathrm{COLES}}$. In other words, training the model using GR
loss and GCL loss is essentially equivalent. With this information, we can
facilitate knowledge exchange between the two fields. The research on single-
view GCL can be applied to GR. Similarly, the findings in GR research can also
assist in enhancing GCL. We give some research examples in the next section.

##  5\. Experiments

Table 1. Summary of the datasets used in node classification. Dataset | #Nodes | #Edges | #Features | #Classes
---|---|---|---|---
Cora | 2,708 | 5,429 | 1,433 | 7
CiteSeer | 3,327 | 4,732 | 3,703 | 6
PubMed | 19,717 | 44,338 | 500 | 3
Computers | 13,752 | 491,722 | 767 | 10
Photo | 7,650 | 238,163 | 745 | 8
Co-CS | 18,333 | 163,788 | 6,805 | 15
Co-Physics | 34,493 | 495,924 | 8,415 | 5

In this section, we validate through experiments that the loss functions of
GCL and GR can be used interchangeably. These experiment can be divided into
two categories, namely _GR-inspired GCL research_ and _GCL-inspired GR
research_. We believe that our findings can prompt a broader range of more
sophisticated researches, which we leave for future work.

###  5.1. GR-inspired GCL research

Table 2. Evaluation of BPR loss on unsupervised single-view GCL. We use classification accuracy as the metric. All experiments are repeated 10 times. We bold the best-performing method and underline the second-best method for each dataset. We cannot get the results of SP-GCL on CiteSeer since it does not support graphs with isolated nodes. Methods | Cora | CiteSeer | PubMed | Computers | Photo | Co-CS | Co-Physics
---|---|---|---|---|---|---|---
GraphSAGE | 77.8 $\pm$ 1.3 | 68.2 $\pm$ 1.5 | 75.5 $\pm$ 0.9 | 68.3 $\pm$ 0.7 | 73.2 $\pm$ 0.7 | 90.7 $\pm$ 0.4 | 94.3 $\pm$ 0.1
SCE | 80.9 $\pm$ 0.8 | 70.0 $\pm$ 0.7 | 76.3 $\pm$ 0.7 | 84.4 $\pm$ 0.8 | 89.5 $\pm$ 0.6 | 91.6 $\pm$ 0.2 |  95.5 $\pm$ 0.1
COLES |  81.8 $\pm$ 0.4 |  70.7 $\pm$ 1.0 | 75.6 $\pm$ 1.2 | 85.9 $\pm$ 0.4 |  92.1 $\pm$ 0.4 | 92.0 $\pm$ 0.2 |  95.6 $\pm$ 0.1
SP-GCL | 81.5 $\pm$ 0.5 | - |  78.9 $\pm$ 1.0 |  87.7 $\pm$ 0.5 |  91.9 $\pm$ 0.5 |  92.4 $\pm$ 0.3 | 94.8 $\pm$ 0.1
BPR |  81.6 $\pm$ 0.6 |  70.6 $\pm$ 0.8 |  78.7 $\pm$ 0.8 |  86.1 $\pm$ 0.5 | 91.7 $\pm$ 0.4 |  92.2 $\pm$ 0.3 | 95.2 $\pm$ 0.1
Table 3. Evaluation of joint training between COLES and various multi-views GCLs. We use classification accuracy as the metric. All experiments are reported 10 times. Methods | Cora | CiteSeer | PubMed | Computers | Photo | Co-CS | Co-Physics
---|---|---|---|---|---|---|---
GRACE | 83.5 $\pm$ 0.3 | 70.1 $\pm$ 0.9 | 80.2 $\pm$ 0.7 | 85.4 $\pm$ 0.4 | 90.2 $\pm$ 0.4 | 92.1 $\pm$ 0.3 | 95.5 $\pm$ 0.1
GCA | 83.3 $\pm$ 0.5 | 68.7 $\pm$ 0.6 | 81.2 $\pm$ 0.6 | 88.9 $\pm$ 0.5 | 92.3 $\pm$ 0.3 | 92.2 $\pm$ 0.1 | 95.5 $\pm$ 0.1
CCA-SSG | 82.1 $\pm$ 0.4 | 70.5 $\pm$ 0.9 | 81.8 $\pm$ 0.7 | 88.4 $\pm$ 0.6 | 92.5 $\pm$ 0.2 | 92.5 $\pm$ 0.4 | 95.4 $\pm$ 0.2
GGD | 81.7 $\pm$ 0.5 | 69.6 $\pm$ 0.7 | 80.4 $\pm$ 0.4 | 85.5 $\pm$ 0.8 | 92.1 $\pm$ 0.4 | 92.4 $\pm$ 0.4 | 95.2 $\pm$ 0.1
PolyGCL | 80.1 $\pm$ 0.4 | 70.2 $\pm$ 0.5 | 79.2 $\pm$ 0.7 | 82.8 $\pm$ 0.6 | 89.2 $\pm$ 0.5 | 91.3 $\pm$ 0.2 | 95.5 $\pm$ 0.2
COLES + GRACE | 83.6 $\pm$ 0.5 | 70.8 $\pm$ 0.6 | 80.7 $\pm$ 0.8 | 85.5 $\pm$ 0.4 | 90.6 $\pm$ 0.4 | 92.2 $\pm$ 0.2 | 95.5 $\pm$ 0.1
COLES + GCA | 83.7 $\pm$ 0.4 | 70.6 $\pm$ 0.7 | 81.5 $\pm$ 0.5 | 89.1 $\pm$ 0.3 | 92.4 $\pm$ 0.4 | 92.5 $\pm$ 0.2 | 95.6 $\pm$ 0.2
COLES + CCA-SSG | 82.6 $\pm$ 0.5 | 72.0 $\pm$ 0.4 | 81.9 $\pm$ 0.5 | 88.4 $\pm$ 0.5 | 92.7 $\pm$ 0.3 | 92.9 $\pm$ 0.5 | 95.5 $\pm$ 0.1
COLES + GGD | 82.3 $\pm$ 0.7 | 70.9 $\pm$ 0.8 | 80.4 $\pm$ 0.6 | 86.2 $\pm$ 0.3 | 92.5 $\pm$ 0.2 | 92.5 $\pm$ 0.3 | 95.6 $\pm$ 0.1
COLES + PolyGCL | 81.8 $\pm$ 0.6 | 71.0 $\pm$ 0.7 | 80.2 $\pm$ 0.7 | 86.2 $\pm$ 0.5 | 92.5 $\pm$ 0.4 | 92.7 $\pm$ 0.4 | 95.6 $\pm$ 0.1

We start with the GR-inspired GCL research. A natural question is: _Can we use
the BPR loss to train GNNs in an unsupervised manner?_ To investigate this
question, we conduct unsupervised graph representation learning on seven
datasets and evaluate the effectiveness of the models using node
classification, the results are reported in Table 2. We use Cora, CiteSeer and
PubMed (Yang et al., 2016), Amazon-Computers and Amazon-Photo, Coauthor-CS and
Coauthor-Physics (Shchur et al., 2018). The data statitics are in Table 1. For
baselines, we include common single-view GCLs:

  * •

Unsupervised GraphSAGE (Hamilton et al., 2017): An early work that samples
positive pairs by random walk.

  * •

SCE (Zhang et al., 2020): A sparsest cut inspired, negative samples only GCL
method.

  * •

COLES (Zhu et al., 2021a): A contrastive Laplacian eigenmaps method with both
positive and negative pairs.

  * •

SP-GCL (Wang et al., 2022): A single-view GCL method that works on both
homophilic and heterophilic graphs.

For all datasets, we first train a GNN with 512 hidden dimensions, then fit a
linear classifier and report its accuracy. We use the bpr loss
$\mathcal{L}_{\mathrm{BPR}}$ to replace the COLES loss
$\mathcal{L}_{\mathrm{COLES}}$, and dub the model ”BPR”. In GCL, this can be
done by treating connected nodes as the positive pair, and sampling one
negative sample for each anchor node. With the contrastive pairs, we simply
train the GNN with Equation (6) instead of Equation (7). From Table 2, we
observe that BPR works well as a single-view GCL, despite not achieving state-
of-the-art performance. This result further supports the validity of our
findings.

Previous works have reported that the performance of GR can be improved if it
is jointly trained with multi-view GCLs. Since we have obtained the
equivalence between the bpr loss and single-view GCLs, it is intriguing to
ask: _Will joint training with multi-view GCLs benefits single-view GCL?_ We
conduct experiments on the previously mentioned seven datasets. We modify the
loss function of COLES $\mathcal{L}_{\mathrm{COLES}}$ to the following
function:

(14)
$\mathcal{L}_{\mathrm{COLES+MVGCL}}=\mathcal{L}_{\mathrm{COLES}}+\gamma\mathcal{L}_{\mathrm{MVGCL}},$

where $\mathcal{L}_{\mathrm{MVGCL}}$ is the loss function of a certain multi-
view GCL and $\gamma$ is a hyperparameter. We choose five representative
methods to be jointly trained with COLES:

  * •

GRACE (Zhu et al., 2020): An early multi-view GCL method that uses an extended
version of the InfoNCE loss. The edge removing graph augmentation technique is
proposed in this method.

  * •

GCA (Zhu et al., 2021b): An improved version of GRACE that uses adaptive
augmentation instead of the static one.

  * •

CCA-SSG (Zhang et al., 2021): It optimizes a feature-level objective inspired
by the canonical correlation analysis. Methods like CCA-SSG are not viewed as
contrastive models in some paper, but they are generally equivalent according
to (Garrido et al., 2023).

  * •

GGD (Zheng et al., 2022): A scalable GCL method with group discrimination.

  * •

PolyGCL (Chen et al., 2023): A recent GCL method with polynomial filters.

We observe that, joint training of COLES and multi-view GCLs indeed improves
the performance on most of datasets. It could be attribute to the regulation
effects brought by graph augmentation. On many datasets, this combination also
exceeds the original multi-view GCLs. This is also intuitive since the single-
view GCL includes explicit structure information that helps models to identify
more positive samples.

###  5.2. GCL-inspired GR research

Table 4. Summary of the datasets used in graph recommender. Dataset | #Users | #Items | #Edges
---|---|---|---
Yelp2018 | 31,668 | 38,048 | 1,561,406
Amazon-Kindle | 138,333 | 98,572 | 1,909,965
Alibaba-iFashion | 300,000 | 81,614 | 1,607,813
Table 5. Evaluation of GR models that trained solely with the single-view GCL loss. We use Recall@20 and NDCG@20 as the metrics. Methods | Yelp2018 | Amazon-Kindle | Alibaba-iFashion
---|---|---|---
Recall@20 | NDCG@20 | Recall@20 | NDCG@20 | Recall@20 | NDCG@20
LightGCN | 0.0639 | 0.0525 | 0.2057 | 0.1315 | 0.0955 | 0.0461
LightGCNCOLES | 0.0623 | 0.0507 | 0.1996 | 0.1302 | 0.0973 | 0.0458
SGL | 0.0675 | 0.0555 | 0.2069 | 0.1328 | 0.1032 | 0.0498
SGLCOLES | 0.0651 | 0.0548 | 0.2035 | 0.1322 | 0.1024 | 0.0489
SimGCL | 0.0721 | 0.0601 | 0.2104 | 0.1374 | 0.1151 | 0.0567
SimGCLCOLES | 0.0703 | 0.0592 | 0.2075 | 0.1355 | 0.1097 | 0.0546
XSimGCL | 0.0723 | 0.0604 | 0.2147 | 0.1415 | 0.1196 | 0.0586
XSimGCLCOLES | 0.0710 | 0.0594 | 0.2080 | 0.1378 | 0.1105 | 0.0566

We then provide several examples of GCL-inspired GR research. Similar to the
previous section, we begin by validating the following question: _Can we train
a graph recommender solely using single-view GCL loss?_ To do so, we want to
replace the bpr loss $\mathcal{L}_{\mathrm{bpr}}$ with a single-view GCL loss
$\mathcal{L}_{\mathrm{COLES}}$ in Algorithm 1. In addition, we also need to
normalize the final embedding $\mathbf{E}$ to match with our assumption.
However, the naive normalization is known to be harmful to recommender system
(Chung et al., 2023), i.e., force embeddings to reside on the surface of a
unit hypersphere will cause dramatic performance degrade. Fortunately, there
is also a regularization term to address this problem in (Chung et al., 2023).
Given the user set $\mathcal{U}$ and the item set $\mathcal{I}$, they first
calculate a sum of pairwise Gaussian potentials for each set homogeneously:

(15)
$\mathcal{L}_{\mathrm{hom}}=\sum_{x\in\mathcal{U}}\sum_{y\in\mathcal{U}}e^{-t||e_{x}-e_{y}||^{2}}+\sum_{x\in\mathcal{I}}\sum_{y\in\mathcal{I}}e^{-t||e_{x}-e_{y}||^{2}},$

where $t$ is a hyperparameter. Then, they also use the heterogeneous loss
between positive and negative samples:

(16)
$\mathcal{L}_{\mathrm{het}}=\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}e^{-t||e_{i}-e_{j}||^{2}}.$

The previous study (Chung et al., 2023) have demonstrated that the combination
of Equation (15) and (16) effectively mitigates the bias introduced by
normalization. With this regulation term, we finally arrive our training
objective:

(17)
$\mathcal{L}_{\mathrm{GR}_{\mathrm{COLES}}}=\mathcal{L}_{\mathrm{COLES}}+\mathcal{L}_{\mathrm{hom}}+\mathcal{L}_{\mathrm{het}}.$

Previous works regarded contrastive learning loss like
$\mathcal{L}_{\mathrm{COLES}}$ as unsupervised, making it difficult to
understand why Equation (17) can directly train a good GR model without fine-
tuning. However, this becomes very natural with Theorem 4.6, because we know
that $\mathcal{L}_{\mathrm{COLES}}$ and $\mathcal{L}_{\mathrm{BPR}}$ are
equivalent. We replace $\mathcal{L}_{BPR}$ with
$\mathcal{L}_{\mathrm{GR}_{\mathrm{COLES}}}$, and conducted experiments on
multiple GR models:

  * •

LightGCN (He et al., 2020): An early work of graph recommender and the most
commonly-used backbone model. It initializes a learnable embedding lookup
table and propagates it using the message-passing operation. Then the
embeddings are optimized with the BPR loss.

  * •

SGL (Wu et al., 2021): The GCL loss is adopted for jointly training with the
BPR loss. We change the BPR loss to the single-view GCL loss and keep the
original contrastive module, the model is dubbed SGLCOLES.

  * •

SimGCL (Yu et al., 2022): It performs embedding augmentation instead of graph
augmentation for efficiency. We change the BPR loss to the single-view GCL
loss and keep the original contrastive module, the model is dubbed
SimGCLCOLES.

  * •

XSimGCL (Yu et al., 2023): It performs contrastive learning across different
layer embeddings for further simplification. We change the BPR loss to the
single-view GCL loss and keep the original contrastive module, the model is
dubbed XSimGCLCOLES.

We use three real-world datasets: Yelp2018 (He et al., 2020), Amazon-kindle
(Wu et al., 2021) and Alibaba-iFashion (Wu et al., 2021). We report Recall@20
and NDCG@20 in Table 5, these two metrics are commonly used in previous works
(He et al., 2020; Wu et al., 2021; Yu et al., 2023). It is clear that the
single-view GCL loss works well in GR. This finding is novel because previous
research believed that GCL could only be trained in conjunction with the BPR
loss, and even contrastive pre-training was considered challenging (Yang et
al., 2024). However, our study demonstrates for the first time that GCL can be
used as a standalone downstream task in graph recommender systems. This
finding also enables many research studies on GCL to directly apply to GR,
such as scalability (Zhang et al., 2023) and negative sample mining (Xia et
al., 2022). We leave these aspects for future work.

###  5.3. Additional Experiments

Self-loop and average. As mentioned in Section 4.1, the LightGCN encoder uses
the average embeddings of all layers instead of just the final embedding.
Despite the fact that it does not add self-loop into the adjacency matrix,
nodes in LightGCN actually receives more information from the inputs than the
vanilla GCN. Here, we empirically investigate these two options of
architecture. We add self-loop into the adjacency matrix and take only the
final embeddings as the output, this model is dubbed as LightGCNSelfloop. We
compare the original average embedding LightGCN with the modified version. The
results are presented in Table 6. We observe that two encoders produce similar
performance. This is predictable since they capture same information just with
different weights. Additionally, LightGCNSelfloop performs better on the
Yelp2018 dataset, while the original LightGCN performs better on Amazon-Kindle
and Alibaba-iFashion. We believe the reason for this is that Yelp2018 is with
a significantly larger density (0.13%, while Amazon-Kindle has 0.014% and
Alibaba-iFashion 0.007%). The rich neighborhood information is better captured
with the LightGCNSelfloop according to our analysis in Section 4.1, since each
node has less relative influence on itself in this encoder.

Table 6. Evaluation of LightGCNSelfloop and the original LightGCN. We use Recall@20 and NDCG@20 as the metric. The better results are bolded. Dataset | Metric | LightGCNSelfloop | LightGCN
---|---|---|---
Yelp2018 | Recall@20 | 0.0642 | 0.0639
NDCG@20 | 0.0528 | 0.0525
Amazon-Kindle | Recall@20 | 0.2023 | 0.2057
NDCG@20 | 0.1317 | 0.1315
Alibaba-iFashion | Recall@20 | 0.0940 | 0.0955
NDCG@20 | 0.0450 | 0.0461

Sensitivity analysis. We conduct sensitivity analysis on the negative
coefficient $\beta$ used in GR experiments. We present the result on Yelp2018
in Figure 2. We observe that $\beta$ does not significantly affect the
performance of GR in reasonable range.

Figure 2. Recall@20 and NDCG@20 on the Yelp2018 dataset with varying $\beta$.

Ablation study. In Section 5.2, we use the regulation terms in (Chung et al.,
2023) to mitigate the bias introduced by normalization. We study how these
terms affect GR models by conducting ablation study. The results are presented
in Table 7. We observe that the regulation terms indeed mitigate the bias,
since the performance drops dramatically after the regulation terms are
removed. This result further verifies the effectiveness of (Chung et al.,
2023). We also observe that GR model trained with only these regulation terms
fails to get a meaningful result. Thus it is safe to conclude that
$\mathcal{L}_{\mathrm{COLES}}$ is the main recommendation loss and
$\mathcal{L}_{hom}+\mathcal{L}_{het}$ is only for debiasing.

Table 7. The ablation study on the Yelp2018 dataset. LightGCNCOLES is the LightGCN model trained with Equation 17. $-$Regulation is trained with only the single-view GCL loss $\mathcal{L}_{\mathrm{COLES}}$. $-$COLES is trained with only the regulation terms $\mathcal{L}_{\mathrm{hom}}+\mathcal{L}_{\mathrm{het}}$. | Recall@20 | NDCG@20
---|---|---
LightGCNCOLES | 0.0623 | 0.0507
$-$Regulation | 0.0301 | 0.0249
$-$COLES | 0.0041 | 0.0033

###  5.4. Experimental details

Experiments are conducted on a server with 80 GB NVIDIA A100 GPU. For the node
classification task, we use the code repository of
SCE111https://github.com/szzhang17/Sparsest-Cut-Network-Embedding,
COLES222https://github.com/allenhaozhu/COLES and SP-GCL
333https://github.com/haonan3/SPGCL. For the unsupervised GraphSAGE, we use
the example code from torch-geometric 444https://github.com/pyg-
team/pytorch_geometric/blob/master/examples/graph_sage_unsup.py. We also use
the repository of GRACE555https://github.com/CRIPAC-DIG/GRACE,
GCA666https://github.com/CRIPAC-DIG/GCA, CCA-
SSG777https://github.com/hengruizhang98/CCA-SSG,
GGD888https://github.com/zyzisastudyreallyhardguy/Graph-Group-Discrimination
and PolyGCL999https://github.com/ChenJY-Count/PolyGCL. For the graph
recommender task, we use SELFREC101010https://github.com/Coder-Yu/SELFRec, a
comprehensive framework for self-supervised and graph recommendation.

We adhered closely to the setting employed in prior studies. Specifically, we
use 2-layers GCN for all node classification tasks. We use 3-layers models for
GR since they preform best in most of datasets. We set the number of hidden
dimension to 512 for GCLs and 64 for GRs. We use the Adam (Kingma and Ba,
2014) optimizer without weight decay, the learning rates for GCLs are tuned
from {5e-4, 1e-3, 5e-3, 1e-2} and for GRs are fixed as 1e-2. For GCLs, we use
linear model in scikit-learn111111https://scikit-
learn.org/stable/modules/linear_model.html to predict the downstream tasks.
For GR, it is conventional to use mini-batch gradient descent, so we adpot
this setting and use 2048 as the batch size. We adopt the default choice from
previous papers and set $t=2$ and $\beta=0.9$.

##  6\. Conclusion

In this paper, we establish a connection between the fields of GCL and GR.
With mild assumptions, we theoretically demonstrate the equivalence between
GCL and GR in terms of both encoders and loss functions. This finding not only
helps explain the phenomenon observed in previous experiments but also
inspires new research directions. Through extensive experiments, we show the
interchangeability of GCL and GR losses. The effectiveness of off-the-shelf
GCL loss in training GR models is particularly astonishing, as prior work
typically considered GCL loss to be unsupervised and required joint training
with BPR loss in recommendation tasks. We also provide examples of new
research directions that arise from our discoveries.

## References

  * (1)
  * Chen et al. (2024) Hao Chen, Yuanchen Bei, Qijie Shen, Yue Xu, Sheng Zhou, Wenbing Huang, Feiran Huang, Senzhang Wang, and Xiao Huang. 2024.  Macro graph neural networks for online billion-scale recommender systems. In _Proceedings of the ACM on Web Conference 2024_. 3598–3608.
  * Chen et al. (2023) Jingyu Chen, Runlin Lei, and Zhewei Wei. 2023.  PolyGCL: GRAPH CONTRASTIVE LEARNING via Learnable Spectral Polynomial Filters. In _The Twelfth International Conference on Learning Representations_.
  * Chen et al. (2022) Rongqin Chen, Shenghui Zhang, Ye Li, et al. 2022\.  Redundancy-free message passing for graph neural networks.  _Advances in Neural Information Processing Systems_ 35 (2022), 4316–4327.
  * Chung et al. (2023) Hyunsoo Chung, AI Omnious, and Jungtaek Kim. 2023.  Leveraging Uniformity of Normalized Embeddings for Sequential Recommendation.  _4th Workshop on Self-Supervised Learning: Theory and Practice at Advances in Neural Information Processing Systems_ (2023).
  * Deshpande et al. (2018) Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. 2018.  Contextual stochastic block models.  _Advances in Neural Information Processing Systems_ 31 (2018).
  * Garrido et al. (2023) Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman, and Yann Lecun. 2023.  On the duality between contrastive and non-contrastive self-supervised learning. In _ICLR 2023-Eleventh International Conference on Learning Representations_.
  * Gutmann and Hyvärinen (2010) Michael Gutmann and Aapo Hyvärinen. 2010.  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 297–304.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * Hamilton (2020) William L Hamilton. 2020.  _Graph representation learning_.  Morgan & Claypool Publishers.
  * He et al. (2020) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020.  Lightgcn: Simplifying and powering graph convolution network for recommendation. In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval_. 639–648.
  * He et al. (2018) Xiangnan He, Zhankui He, Jingkuan Song, Zhenguang Liu, Yu-Gang Jiang, and Tat-Seng Chua. 2018.  NAIS: Neural attentive item similarity model for recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ 30, 12 (2018), 2354–2366.
  * Huang et al. (2022) Weiran Huang, Mingyang Yi, Xuyang Zhao, and Zihao Jiang. 2022.  Towards the Generalization of Contrastive Self-Supervised Learning. In _The Eleventh 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 (2016) Thomas N Kipf and Max Welling. 2016.  Semi-Supervised Classification with Graph Convolutional Networks. In _International Conference on Learning Representations_.
  * Koren (2008) Yehuda Koren. 2008.  Factorization meets the neighborhood: a multifaceted collaborative filtering model. In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_. 426–434.
  * Lampert and Scholtes (2023) Moritz Lampert and Ingo Scholtes. 2023.  The Self-Loop Paradox: Investigating the Impact of Self-Loops on Graph Neural Networks. In _The Second Learning on Graphs Conference_.
  * Rendle et al. (2012) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2012.  BPR: Bayesian personalized ranking from implicit feedback.  _arXiv preprint arXiv:1205.2618_ (2012).
  * 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).
  * Wang et al. (2023) Chenyang Wang, Weizhi Ma, Chong Chen, Min Zhang, Yiqun Liu, and Shaoping Ma. 2023.  Sequential recommendation with multiple contrast signals.  _ACM Transactions on Information Systems_ 41, 1 (2023), 1–27.
  * Wang et al. (2022) Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang. 2022.  Can Single-Pass Contrastive Learning Work for Both Homophilic and Heterophilic Graph?  (2022).
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019.  Neural graph collaborative filtering. In _Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval_. 165–174.
  * Wei et al. (2022) Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R Benson, and Pan Li. 2022.  Understanding non-linearity in graph neural networks from the bayesian-inference perspective.  _Advances in Neural Information Processing Systems_ 35 (2022), 34024–34038.
  * Wu et al. (2021) Jiancan Wu, Xiang Wang, Fuli Feng, Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. 2021.  Self-supervised graph learning for recommendation. In _Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval_. 726–735.
  * Xia et al. (2022) Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z Li. 2022.  ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning. In _International Conference on Machine Learning_. PMLR, 24332–24346.
  * Yang et al. (2024) Haoran Yang, Xiangyu Zhao, Yicong Li, Hongxu Chen, and Guandong Xu. 2024.  An Empirical Study Towards Prompt-Tuning for Graph Contrastive Pre-Training in Recommendations.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016.  Revisiting semi-supervised learning with graph embeddings. In _International conference on machine learning_. PMLR, 40–48.
  * Yu et al. (2023) Junliang Yu, Xin Xia, Tong Chen, Lizhen Cui, Nguyen Quoc Viet Hung, and Hongzhi Yin. 2023.  XSimGCL: Towards extremely simple graph contrastive learning for recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ (2023).
  * Yu et al. (2022) Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoc Viet Hung Nguyen. 2022.  Are graph augmentations necessary? simple graph contrastive learning for recommendation. In _Proceedings of the 45th international ACM SIGIR conference on research and development in information retrieval_. 1294–1303.
  * Zhang et al. (2021) Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. 2021.  From canonical correlation analysis to self-supervised graph neural networks.  _Advances in Neural Information Processing Systems_ 34 (2021), 76–89.
  * Zhang et al. (2024) Jiahao Zhang, Rui Xue, Wenqi Fan, Xin Xu, Qing Li, Jian Pei, and Xiaorui Liu. 2024.  Linear-Time Graph Neural Networks for Scalable Recommendations. In _Proceedings of the ACM on Web Conference 2024_. 3533–3544.
  * Zhang et al. (2020) Shengzhong Zhang, Zengfeng Huang, Haicang Zhou, and Ziang Zhou. 2020.  Sce: Scalable network embedding from sparsest cut. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 257–265.
  * Zhang et al. (2023) Shengzhong Zhang, Wenjie Yang, Xinyuan Cao, Hongwei Zhang, and Zengfeng Huang. 2023.  StructComp: Substituting propagation with Structural Compression in Training Graph Contrastive Learning. In _The Twelfth International Conference on Learning Representations_.
  * Zheng et al. (2022) Yizhen Zheng, Shirui Pan, Vincent Lee, Yu Zheng, and Philip S Yu. 2022.  Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination.  _Advances in Neural Information Processing Systems_ 35 (2022), 10809–10820.
  * Zhu et al. (2021a) Hao Zhu, Ke Sun, and Peter Koniusz. 2021a.  Contrastive laplacian eigenmaps.  _Advances in neural information processing systems_ 34 (2021), 5682–5695.
  * Zhu et al. (2020) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2020.  Deep graph contrastive representation learning.  _arXiv preprint arXiv:2006.04131_ (2020).
  * Zhu et al. (2021b) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021b.  Graph contrastive learning with adaptive augmentation. In _Proceedings of the Web Conference 2021_. 2069–2080.

##  Appendix A Proofs

###### Lemma A.1.

The trace of the quadratic form of the Laplacian matrix is equal to the
smoothness on the graph, i.e.,

(18)
$\mathrm{Tr}(\mathbf{E}^{T}\mathbf{L}\mathbf{E})=\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}||e_{u}-e_{i}||^{2}.$

###### Proof.

(19)
$\begin{split}\mathrm{Tr}(\mathbf{E}^{T}\mathbf{L}\mathbf{E})&=\sum_{k=1}^{d}\sum_{i=1}^{n}\sum_{j=1}^{n}e_{i,k}e_{j,k}\mathbf{L}_{i,j}\\\
&=\sum_{k=1}^{d}(\sum_{i=1}^{n}e_{i,k}^{2}\mathbf{L}_{i,i}+\sum_{i\neq
j}e_{i,k}e_{j,k}\mathbf{L}_{i,j})\\\
&=\frac{1}{2}\sum_{k=1}^{d}(\sum_{i=1}^{n}e_{i,k}^{2}\mathbf{L}_{i,i}+2\sum_{i\neq
j}e_{i,k}e_{j,k}\mathbf{L}_{i,j}+\sum_{j=1}^{n}e_{j,k}^{2}\mathbf{L}_{j,j})\\\
&=\frac{1}{2}\sum_{k=1}^{d}\sum_{i\neq
j}(e_{i,k}^{2}\mathbf{A}_{i,j}-2e_{i,k}e_{j,k}\mathbf{A}_{i,j}+e_{j,k}^{2}\mathbf{A}_{i,j})\\\
&=\frac{1}{2}\sum_{k=1}^{d}\sum_{i\neq
j}\mathbf{A}_{i,j}(e_{i,k}-e_{j,k})^{2}\\\
&=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\mathbf{A}_{i,j}||e_{i}-e_{j}||^{2}\\\
&=\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}||e_{u}-e_{i}||^{2}.\end{split}$

∎

###### Theorem A.2.

With the normalized embeddings, we have the following equivalence:

(20)
$\begin{split}\frac{K}{2}\mathcal{L}_{\mathrm{COLES}}^{+}-\frac{d_{\mathrm{min}}}{2}\mathcal{L}_{\mathrm{COLES}}^{-}+d_{\mathrm{min}}Kn_{u}-mK\leq\mathcal{L}_{\mathrm{BPR}}\\\
\leq\frac{K}{2}\mathcal{L}_{\mathrm{COLES}}^{+}-\frac{d_{\mathrm{max}}}{4}\ln(\frac{2e^{2}}{e^{2}+1})\mathcal{L}_{\mathrm{COLES}}^{-}+\mathrm{constant},\end{split}$

where
$\mathrm{constant}=d_{\mathrm{max}}Kn_{u}\ln(\frac{2e^{3}+2e}{e^{2}+1})-mK$.

###### Proof.

(21)
$\begin{split}\mathcal{L}_{\mathrm{BPR}}&=-\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\ln\left(\frac{1}{1+\exp(\hat{y}_{uj}-\hat{y}_{ui})}\right)\\\
&=-\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\ln\left(\frac{\exp(\hat{y}_{ui})}{\exp(\hat{y}_{ui})+\exp(\hat{y}_{uj})}\right)\\\
&=-K\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\hat{y}_{ui}+\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\ln(e^{\hat{y}_{ui}}+e^{\hat{y}_{uj}})\\\
&=\mathcal{L}_{\mathrm{BPR}}^{+}+\mathcal{L}_{\mathrm{BPR}}^{-},\end{split}$

where we denote
$\mathcal{L}_{\mathrm{BPR}}^{+}=-K\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\hat{y}_{ui}$
as the positive part of the BPR loss, and
$\mathcal{L}_{\mathrm{BPR}}^{-}=\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\ln(e^{\hat{y}_{ui}}+e^{\hat{y}_{uj}})$
as the negative part of the BPR loss. Then, we have:

(22)
$\begin{split}\mathcal{L}_{\mathrm{BPR}}^{+}&=-K\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}\hat{y}_{ui}\\\
&=\frac{K}{2}\sum_{u=1}^{n_{u}}\sum_{i\in\mathcal{N}_{u}}(||e_{u}-e_{i}||^{2}-2)\\\
&=\frac{K}{2}\mathcal{L}_{\mathrm{COLES}}^{+}-mK.\end{split}$

For the negative part, we have:

(23)
$\begin{split}\mathcal{L}_{\mathrm{BPR}}^{-}&\geq\sum_{u=1}^{n_{u}}d_{u}\sum_{j\in\mathcal{N}_{u}^{-}}\hat{y}_{uj}\\\
&\geq
d_{\mathrm{min}}\sum_{u=1}^{n_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\hat{y}_{uj}\\\
&=-\frac{d_{\mathrm{min}}}{2}\sum_{u=1}^{n_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}(||e_{u}-e_{j}||^{2}-2)\\\
&=-\frac{d_{\mathrm{min}}}{2}\mathcal{L}_{\mathrm{COLES}}^{-}+d_{\mathrm{min}}Kn_{u},\end{split}$

and,

(24) $\begin{split}\mathcal{L}_{\mathrm{BPR}}^{-}&\leq
d_{\mathrm{max}}\sum_{u=1}^{n_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\ln(e+e^{\hat{y}_{uj}})\\\
&\leq
d_{\mathrm{max}}\sum_{u=1}^{n_{u}}\sum_{j\in\mathcal{N}_{u}^{-}}\left(\frac{1}{2}\ln(\frac{2e^{2}}{e^{2}+1})(\hat{y}_{uj}+1)+\ln(e+\frac{1}{e})\right)\\\
&=\frac{d_{\mathrm{max}}}{2}\ln(\frac{2e^{2}}{e^{2}+1})(2Kn_{u}-\frac{\mathcal{L}_{\mathrm{COLES}}^{-}}{2})+d_{\mathrm{max}}Kn_{u}\ln(e+\frac{1}{e}).\end{split}$

By plugging equations (22), (23), and (24) back into equation (21), we obtain
the desired inequality. ∎