11institutetext: The Ohio State University at Mansfield, 1760 University Drive
Mansfield, OH 44906, USA<EMAIL_ADDRESS>
# Partial duality for ribbon graphs

Sergei Chmutov

###### Abstract

This is an expository paper extending the tutorial talk at the MATRIX Workshop
on Uniqueness and Discernment in Graph Polynomials in October 2023. The
explanation is mainly based on CVT22  with maximal possible simplifications.

##  1 Introduction

The concept of partial duality appeared in Ch  in an attempt to unify the
various Thistlethwaite type theorems of CP ; DFKLS ; CV  from the knot theory.
The classical Thistlethwaite theorem relates the Jones polynomial of a link to
the Tutte polynomial of a checkerboard graph, the Tait graph, of its plane
diagram. There were several generalizations of this theorem to virtual links
where graphs on a higher genus surface, i.e. ribbon graphs, naturally
appeared. It turned out that all these ribbon graphs are related via partial
duality operations.

Since then partial duality was thoughtfully studied and described in many
papers CVT21 ; EZ ; GMT ; GMT21 ; GMT21e ; Mo3 ; YaJi21 ; YaJi22 ; YaJi22 ;
YaZh22 ; YaJi22s ; YaJi22dm ; Yus22 . For an excellent exposition see EMM . In
CMNR19c ; CMNR19p , it was found that the partial dual operation generalized
to delta matroids is a well known operation of twist of A. Bouchet Bu87 ; Bu89
. So we should treat the partial duality from Ch  simply as a geometric
description of Bouchet’s twist operation for the delta matroids of ribbon
graphs. Also we would like to mention CVT22 , where the partial duality
operation was generalized to hypermaps. Its (delta) matroidal analogue is
still unknown.

The idea of partial duality is to split the classical Euler-Poincaré duality

$G\ =\
\raisebox{-20.0pt}[10.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr.eps}}
\put(3.0,20.0){\color[rgb]{192,96,0}{$\scriptstyle e_{1}$}}
\put(25.0,20.0){\color[rgb]{192,96,0}{$\scriptstyle e_{2}$}}
\put(20.0,-4.0){\color[rgb]{192,96,0}{$\scriptstyle e_{3}$}}
\end{picture}}\quad\raisebox{-5.0pt}[20.0pt][30.0pt]{\begin{picture}(30.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=30.0pt]{totor.eps}}
\end{picture}}\quad\raisebox{-30.0pt}[0.0pt][0.0pt]{\begin{picture}(60.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=60.0pt]{tr-g2.eps}}
\end{picture}}\quad\raisebox{-5.0pt}[0.0pt][0.0pt]{\begin{picture}(30.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=30.0pt]{totor.eps}}
\end{picture}}\quad\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(60.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=60.0pt]{g2.eps}}
\put(5.0,20.0){\color[rgb]{255,0,255}{$\scriptstyle e_{1}$}}
\put(47.0,20.0){\color[rgb]{255,0,255}{$\scriptstyle e_{2}$}}
\put(20.0,12.0){\color[rgb]{255,0,255}{$\scriptstyle e_{3}$}}
\end{picture}}\quad=\ G^{*}$

for graphs cellulary embedded to surfaces into steps making a duality relative
to a single edge at a time. Before giving the formal definitions in the next
section we explain how it works on this particular example. The difficulty is
that the partial duality may change the genus of the surface into which the
graph is embedded.

First, to find the partial duality relative to the edge $e_{1}$ it is
convenient to consider the graph $G$ embedded not into a plane but into an
annulus, a surface with boundary.

$G$$\scriptstyle e_{1}$$\scriptstyle e_{2}$$\scriptstyle e_{3}$

The partial duality relative to the edge $e_{1}$ changes the annulus by adding
a band across the edge $e_{1}$ to the two boundary circles of the annulus.
Then the edge $e_{1}$ is shrunk to a new vertex and the dual edge $e_{1}$ goes
along the band. Here is the result $G^{\\{e_{1}\\}}$, the partial dual of $G$
relative to the edge $e_{1}$.

$G^{\\{e_{1}\\}}$$\scriptstyle e_{1}$$\scriptstyle e_{2}$$\scriptstyle e_{3}$

Notice that this is a duality. This means that if we would like to make a
partial dual relative to a loop $e_{1}$ of the graph $G^{\\{e_{1}\\}}$ then we
have to return to the original graph $G$. Hence, the partial duality relative
to a loop removes the band along this loop and split the corresponding vertex
into two vertices connected by the dual edge. The partial duality of
$G^{\\{e_{1}\\}}$ relative to the edge $e_{2}$ works in a similar way to
produce the graph $G^{\\{e_{1},e_{2}\\}}$.

$G^{\\{e_{1},e_{2}\\}}$$\scriptstyle e_{1}$$\scriptstyle e_{2}$$\scriptstyle
e_{3}$

Now the edge $e_{3}$ is a loop. According to the above procedure for partial
duality relative to a loop we have to cut the band along this loop and split
the only vertex of $G^{\\{e_{1},e_{2}\\}}$. The result is the graph
$G^{\\{e_{1},e_{2},e_{3}\\}}$

$\raisebox{-20.0pt}[35.0pt][25.0pt]{\begin{picture}(100.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=100.0pt]{tr-e1e2e3.eps}}
\put(32.0,45.0){$G^{\\{e_{1},e_{2},e_{3}\\}}$}
\put(15.0,30.0){\color[rgb]{255,0,255}{$\scriptstyle e_{1}$}}
\put(78.0,30.0){\color[rgb]{255,0,255}{$\scriptstyle e_{2}$}}
\put(51.0,10.0){\color[rgb]{255,0,255}{$\scriptstyle e_{3}$}}
\end{picture}}\qquad=\qquad\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(60.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=60.0pt]{g2.eps}}
\put(5.0,20.0){\color[rgb]{255,0,255}{$\scriptstyle e_{1}$}}
\put(47.0,20.0){\color[rgb]{255,0,255}{$\scriptstyle e_{2}$}}
\put(20.0,12.0){\color[rgb]{255,0,255}{$\scriptstyle e_{3}$}}
\end{picture}}\quad=\ G^{*}$

on a sphere which is equivalent to the classical Euler-Poincaré dual $G^{*}$.

##  2 Formal definitions

###### Definition 2.1

A ribbon graph $G$ is a surface (possibly non-orientable) with boundary,
represented as the union of two sets of closed topological discs called
vertex-discs $V(G)$ and edge-ribbons $E(G)$, satisfying the following
conditions:

  * $\bullet$

these discs intersect by disjoint line segments;

  * $\bullet$

each such line segment lies on the boundary of precisely one vertex-disc and
precisely one edge-ribbon;

  * $\bullet$

every edge-ribbon contains exactly two such line segments.

We consider ribbon graphs up to a homeomorphism of the corresponding surfaces
preserving the decomposition on vertices and edges.

###### Definition 2.2

For a ribbon graph $G$ and a subset of the edge-ribbons $A\subseteq E(G)$, the
partial dual, $G^{A}$ of $G$ relative to $A$ is a ribbon graph constructed as
follows.

  * •

The vertex-discs of $G^{A}$ are bounded by connected components of the
boundary of the spanning subgraph of $G$ containing all the vertices of $G$
and only the edges from $A$.

  * •

The edge-ribbons of $E(G)\setminus A$ are attached to these new vertices
exactly at the same places as in $G$. The edge-ribbons from $A$ become parts
of the new vertex-discs. For $e\in A$ we take a copy of $e$, $e^{\prime}$, and
attach it to the new vertex-discs in the following way. The rectangle
representing $e$ intersects with vertex-discs of $G$ by a pair of opposite
sides. But it intersects the boundary of the spanning subgraph, that is the
new vertex-discs, along the arcs of the other pair of its opposite sides. We
attach $e^{\prime}$ to these arcs by this second pair. The copies of the first
pair of sides in $e^{\prime}$ become the arcs of the boundary of $G^{A}$.

Partial duality relative to a set of edges can be done step by step one edge
at a time.

The partial duality relative to one edge can be illustrated as follows.

$G=\
\raisebox{-8.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{dus1.eps}}
\put(23.0,-3.0){\mbox{$e$}}
\end{picture}}\quad\raisebox{-4.0pt}[0.0pt][0.0pt]{\begin{picture}(20.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=20.0pt]{totorl.eps}}
\end{picture}}\quad\raisebox{-24.0pt}[25.0pt][30.0pt]{\begin{picture}(75.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=75.0pt]{dus3.eps}}
\put(-8.0,13.0){\mbox{$e^{\prime}$}} \end{picture}}\ =\
\raisebox{-25.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{dus4.eps}}
\put(31.0,50.0){\mbox{$e^{\prime}$}} \end{picture}}\ =\ G^{\\{e\\}}$

Here the boxes with dashed arcs mean that there might be other edges attached
to these vertices. The partial duality relative to an orientable loop goes in
the opposite direction, from right to left.

For a non-orientable loop we have.

$G=\
\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{dus-
no1.eps}} \put(31.0,40.0){\mbox{$e$}}
\end{picture}}\quad\raisebox{-2.0pt}[25.0pt][30.0pt]{\begin{picture}(20.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=20.0pt]{totorl.eps}}
\end{picture}}\quad\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{dus-
no2.eps}} \put(31.0,40.0){\mbox{$e^{\prime}$}} \end{picture}}\ =\ G^{\\{e\\}}$

###### Lemma 1

Properties of partial duality Ch . Let $G$ be a ribbon graph.

  * (a)

Suppose $E(G)\ni e\not\in A\subseteq E(G)$. Then
$G^{A\cup\\{e\\}}=\bigl{(}G^{A}\bigr{)}^{\\{e\\}}$.

  * (b)

$\bigl{(}G^{A}\bigr{)}^{A}=G$.

  * (c)

$\bigl{(}G^{A}\bigr{)}^{B}=G^{\Delta(A,B)}$, where $\Delta(A,B):=(A\cup
B)\setminus(A\cap B)$ is the symmetric difference of sets.

  * (d)

Partial duality preserves orientability of ribbon graphs.

  * (e)

Let $\widetilde{G}$ be a surface without boundary obtained from $G$ by gluing
discs to all boundary component of $G$. Then
$\widetilde{G^{A}}=\widetilde{G^{E(G)\setminus A}}$.

  * (f)

The partial duality preserves the number of connected components of ribbon
graphs.

There are several ways to encode ribbon graphs. In subsequent sections we
express partial duality relative to a single edge in these encodings following
CVT22  where it was given in a more general situation of hypermaps.

##  3 Partial duality for gems

###### Definition 3.1

According to S. Lins Lins82 a gem (graph-encoded map) is a trivalent graph
whose edges are colored into three colors 0, 1, and 2 in such a way that that
at every vertex the three meeting edges all have different colors.

Gems encode ribbon graphs in the following way. The trivalent graph is the
graph of boundary segments of all the discs. The line segments between the
vertex-discs and edge-ribbons are colored 2. The other segments of the
boundary of vertex-discs (in between vertices and faces) colored 1. And the
other two sides of edge-ribbons (in between edges and faces) are colored 0.
Backwards, from a gem we can construct a ribbon graph in the following way. To
each cycle of the gem colored by two colors 1 and 2, 12-cycle, we glue a disc
which will be a vertex-disc of the resulting ribbon graph. To each 02-disc we
glue an edge-ribbon. In general it will be a hypermap. But if all 02-cycles of
a gem have length 4, then we will get a ribbon graph. This construction can be
generalize to higher dimensions with more colors, see CVT22 .

Here is an example.

$G\
=\quad\raisebox{-15.0pt}[20.0pt][20.0pt]{\begin{picture}(40.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=40.0pt]{tr.eps}}
\end{picture}}\quad=\quad\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
rg.eps}}
\end{picture}}\quad=\quad\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
gem.eps}} \put(40.0,35.0){\scriptsize gem} \end{picture}}$

###### Proposition 3.2

Partial duality relative to an edge for gems CVT22 ; EZ . Let $e$ be an edge
of a ribbon graph $G$ and $C$ be the corresponding 02-cycle of its gem. Then
the partial duality relative to $e$ is given by swapping colors 1 and 2 along
the cycle $C$.

Here is an example

$G\
=\quad\raisebox{-20.0pt}[25.0pt][20.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
gem.eps}} \put(24.0,-5.0){\color[rgb]{192,96,0}{$\scriptstyle e_{3}$}}
\end{picture}}\quad\raisebox{2.0pt}[0.0pt][0.0pt]{\begin{picture}(20.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=20.0pt]{totor.eps}}
\end{picture}}\quad\raisebox{-20.0pt}[0.0pt][0.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
gem-e3.eps}} \put(24.0,-5.0){\color[rgb]{255,0,255}{$\scriptstyle e_{3}$}}
\end{picture}}\quad=\quad\raisebox{-35.0pt}[0.0pt][0.0pt]{\begin{picture}(55.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=55.0pt]{tr-
rg-e3.eps}} \end{picture}}\quad=\quad G^{\\{e_{3}\\}}$

##  4 Partial duality for rotation systems

A rotation system is a way to encode a ribbon graph by two permutations of
$2|E|$ elements.

###### Definition 4.1

GT ; MT A rotation system on an abstract graph is cyclic order of half-edges
around every vertex (given by a permutation $\sigma_{V}$) and an involution of
two half-edges forming a single edge (given by a product of transpositions
$\sigma_{E}$).

Here is an example.

$\raisebox{8.0pt}{$G=$}\raisebox{-10.0pt}[0.0pt][10.0pt]{\begin{picture}(40.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=40.0pt]{tr.eps}}
\put(12.0,26.0){$\scriptstyle 1$}\put(1.0,9.0){$\scriptstyle 2$}
\put(6.0,-4.0){$\scriptstyle 3$}\put(28.0,-4.0){$\scriptstyle 4$}
\put(25.0,26.0){$\scriptstyle 6$} \put(35.0,9.0){$\scriptstyle 5$}
\end{picture}}\qquad\qquad\begin{array}[b]{l}\sigma_{V}(G)=(16)(23)(45)\\\
\sigma_{E}(G)=(12)(34)(56)\end{array}$

We use rotation systems for orientable ribbon graphs. In that case, two
permutations $(\sigma_{V},\sigma_{E})$ completely determine the ribbon graph.

###### Proposition 4.2

Partial duality relative to an edge for rotation systems CVT22 . Suppose that
an edge $e$ has two half edges $a$ and $b$. So, in the permutation
$\sigma_{E}$ it corresponds to a transposition $(ab)$. Then

$\sigma_{V}(G^{\\{e\\}})=(ab)\cdot\sigma_{V}(G),\quad\sigma_{E}(G^{\\{e\\}})=\sigma_{E}(G)\
.$

These formulas were rediscovered in (GMT21e, , Equation 14) and announced in
GMT21 (see also (GMT, , Section 5.2)).

For example, if $e_{3}=(34)$ in our triangle example, then

$\sigma_{V}(G^{\\{e_{3}\\}})=(34)\cdot(16)(23)(45)=(16)(2453)$

.

$\raisebox{8.0pt}{$G=$}\raisebox{-10.0pt}[0.0pt][0.0pt]{\begin{picture}(40.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=40.0pt]{tr.eps}}
\put(12.0,26.0){$\scriptstyle 1$}\put(1.0,9.0){$\scriptstyle 2$}
\put(6.0,-4.0){$\scriptstyle 3$}\put(28.0,-4.0){$\scriptstyle 4$}
\put(25.0,26.0){$\scriptstyle 6$} \put(35.0,9.0){$\scriptstyle 5$}
\end{picture}}\qquad\raisebox{2.0pt}[40.0pt][20.0pt]{\begin{picture}(20.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=20.0pt]{totor.eps}}
\end{picture}}\qquad\raisebox{-35.0pt}[0.0pt][0.0pt]{\begin{picture}(55.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=55.0pt]{tr-
rg-e3.eps}} \put(12.0,62.0){$\scriptstyle 1$} \put(1.0,16.0){$\scriptstyle 2$}
\put(34.0,35.0){$\scriptstyle 3$}\put(34.0,6.0){$\scriptstyle 4$}
\put(40.0,62.0){$\scriptstyle 6$} \put(50.0,16.0){$\scriptstyle 5$}
\end{picture}}\quad=\quad G^{\\{e_{3}\\}}$

##  5 Partial duality for bi-rotation systems

A bi-rotation system is a way to encode a ribbon graph by three permutations
$\tau_{0}$, $\tau_{1}$, and $\tau_{2}$ of $4|E|$. It works for non-orientable
ribbon graphs as well.

###### Definition 5.1

GT ; MT A bi-rotation system is a set of three fixed point free involutions,
$\tau_{0}$, $\tau_{1}$, and $\tau_{2}$, acting on a set of vertices of the
corresponding gem according to the figure.

Here we think about vertices of the gem as local flags consisting of a triple
$(v,e,f)$ of a vertex $v$, an edge $e$ incident to $v$, and a face $f$
adjacent to both $v$ and $e$. We will depict such a flag as a small black
right triangle with one acute angle at the vertex $v$, the right angle at the
edge $e$ and the another acute angle at the vertex of the gem. So every edge-
ribbon of the original ribbon graph has fours such flags adjacent to it.

At each vertex of the gem the three edges of the gem are colored by three
different colors, $0$, $1$, and $2$. The permutation $\tau_{i}$ swaps the
flags in the pairs of vertices connected by an an edge colored by $i$.

In Tutte1984aa W. Tutte introduced a less symmetrical description of a ribbon
graph (combinatorial map) in terms of three permutations $\theta$, $\phi$, and
$P$ which can be expressed in terms of $\tau_{0}$, $\tau_{1}$, and $\tau_{2}$
as follows:

$\theta=\tau_{2},\quad\phi=\tau_{0},\quad P=\tau_{1}\tau_{2}.$

Here is an example of the bi-rotation system.

$G=\raisebox{-20.0pt}[0.0pt][28.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
gem-bir.eps}} \put(12.0,35.0){$\scriptstyle 1$} \put(1.0,16.0){$\scriptstyle
2$}\put(15.0,12.0){$\scriptstyle 3$} \put(21.0,34.0){$\scriptstyle 4$}
\put(8.0,5.0){$\scriptstyle 5$} \put(10.0,-5.0){$\scriptstyle
6$}\put(35.0,-5.0){$\scriptstyle 7$} \put(32.0,10.0){$\scriptstyle 8$}
\put(39.0,8.0){$\scriptstyle 9$} \put(45.0,15.0){$\scriptstyle
a$}\put(33.0,37.0){$\scriptstyle b$} \put(25.0,25.0){$\scriptstyle c$}
\put(23.0,3.5){$\scriptstyle e$}
\end{picture}}\qquad\qquad\qquad\begin{array}[]{l}\tau_{0}(G)=(12)(34)(58)(67)(9c)(ab)\\\
\tau_{1}(G)=(1b)(4c)(26)(35)(7a)(89)\\\
\tau_{2}(G)=(1c)(23)(56)(78)(9a)(bc)\end{array}$

In this case we use the hexadecimal number system. So, $a=10$, $b=11$, and
$c=12$. In particular, for the edge-ribbon $e$ we have four local flags
5,6,7,and 8. So its contribution to the permutations $\tau_{0}$ and $\tau_{2}$
will be $\tau_{0}^{e}=(58)(67)$ and $\tau_{2}^{e}=(56)(78)$.

###### Proposition 5.2

Partial duality relative to an edge for bi-rotation systems CVT22 . Let
$\tau_{0}^{e}$ be the product of two transpositions in $\tau_{1}$ for $e$, and
$\tau_{2}^{e}$ be the product of two transpositions in $\tau_{2}$ for $e$.

Then
$\tau_{0}(G^{\\{e\\}})=\tau_{0}(G)\tau_{0}^{e}\tau_{2}^{e},\quad\tau_{1}(G^{\\{e\\}})=\tau_{1}(G),\quad\tau_{2}(G^{\\{e\\}})=\tau_{2}(G)\tau_{0}^{e}\tau_{2}^{e}$.

In our example we have

$\begin{array}[]{ll}\tau_{0}(G^{\\{e\\}})&=\tau_{0}(G)\tau_{0}^{e}\tau_{2}^{e}=(12)(34)(58)(67)(9c)(ab)(58)(67)(56)(78)\\\
&=(12)(34)(56)(78)(9c)(ab)\\\\[5.0pt]
\tau_{1}(G^{\\{e\\}})&=(1b)(4c)(26)(35)(7a)(89)\\\\[5.0pt]
\tau_{2}(G^{\\{e\\}})&=\tau_{2}(G)\tau_{0}^{e}\tau_{2}^{e}=(1c)(23)(56)(78)(9a)(bc)(58)(67)(56)(78)\\\
&=(1c)(23)(58)(67)(9a)(bc)\end{array}$

These permutations correspond to the following gem:

$G^{\\{e\\}}=\raisebox{-20.0pt}[20.0pt][20.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
gem-e3-bir.eps}} \put(12.0,35.0){$\scriptstyle 1$}
\put(1.0,16.0){$\scriptstyle 2$}\put(15.0,12.0){$\scriptstyle 3$}
\put(21.0,34.0){$\scriptstyle 4$} \put(8.0,5.0){$\scriptstyle 5$}
\put(10.0,-5.0){$\scriptstyle 6$}\put(35.0,-5.0){$\scriptstyle 7$}
\put(32.0,10.0){$\scriptstyle 8$} \put(39.0,8.0){$\scriptstyle 9$}
\put(45.0,15.0){$\scriptstyle a$}\put(33.0,37.0){$\scriptstyle b$}
\put(25.0,25.0){$\scriptstyle c$} \put(23.0,3.5){$\scriptstyle e$}
\end{picture}}$

##  6 Genus change

In this section we give a formula for the change of genus under partial
duality. We will deal with the Euler genus $\gamma$ which is equal to twice
the genus for orientable ribbon graphs and to the number of Möbius bands $\mu$
in the presentation of the surface of the ribbon graph as (possibly several)
spheres with $\mu$ cross-caps in the unorientable case.

Let $G$ be a ribbon graph and $A$ be a subset of its edges. Consider a
subgraph of $G$, $G[A]$ induced by $A$. This means that the edge-ribbons of
$G[A]$ are exactly $A$ and the vertex-discs are exactly the vertex-discs of
$G$ incident with edges of $A$. In a similar way we can considered the
subgraph $G^{*}[A]$ of the total Euler-Poincaré dual $G^{*}$ induced by $A$.
Its vertices are the vertex-discs of $G^{*}$, which are the faces of the
original ribbon graph $G$. Note that the graphs $G[A]$ and $G^{*}[A]$
considered as ribbon graphs themselves are not dual to each other. The
vertices of $G^{*}[A]$ are the faces of $G$, not $G[A]$. For any ribbon graph
$G$, we use the notation $v(G)$ and $f(G)$ for the number of vertex-discs of
$G$ and the number of face-discs of $G$ respectively. The last one is the same
as the number of boundary components of $G$.

###### Proposition 6.1

$\gamma(G^{A})-\gamma(G)=v(G[A])+v(G^{*}[A])-f(G[A])-f(G^{*}[A]).$

This proposition is a further simplification of (CVT22, , Corollary 3.4). It
covers various cases of (GMT, , Table 1.1) and (CVT21, , Fig.1).

In our example

$G\
=\quad\raisebox{-20.0pt}[0.0pt][20.0pt]{\begin{picture}(50.0,15.0)(0.0,0.0)\put(0.0,0.0){\includegraphics[width=50.0pt]{tr-
rg.eps}} \put(20.0,-5.0){\scriptsize$e_{3}$} \end{picture}}\quad$

with $A=\\{e_{3}\\}$, $G[A]$ is the ribbon graph with two vertices and an edge
$e_{3}$ between them. So $v(G[A])=2$, but $f(G[A])=1$ because $G[A]$ has only
one boundary component. For $G^{*}[A]$, there are two vertices of $G^{*}$
bacause there two faces of $G$. And the edge $e_{3}$ connects these two
vertices of $G^{*}[A]$. So we have $v(G^{*}[A])=2$ and $f(G^{*}[A])=1$. A
reader can see that the graphs $G[A]$ and $G^{*}[A]$ are equivalent, but not
dual to each other as ribbon graphs! Therefore the change of genus from
Proposition 6.1 is

$\gamma(G^{\\{e_{3}\\}})-\gamma(G)=2+2-1-1=2.$

This is an orientable case, the genus is half of the Euler genus $\gamma$.
Consequently the graph $G^{\\{e_{3}\\}}$ is on torus as we saw before.

##  7 Partial-dual Genus Polynomial

In GMT J. L. Gross, T. Mansour, T. W. Tucker introduced the Partial-dual Genus
Polynomial of ribbon graphs. In the orientable case it is as follows.

${\ }^{\partial}\Gamma_{G}(z):=\sum_{A\subseteq E(G)}z^{g(G^{A})}\ .$

In the non-orientable case you need to use the Euler genus instead of genus.
This polynomial was studied in various papers CVT21 ; GMT ; GMT21 ; GMT21e ;
YaJi21 ; YaJi22 ; YaJi22 ; YaZh22 ; YaJi22s ; YaJi22dm ; Yus22 . In particular
in YaJi22dm ; Yus22 it was generalized to delta-matroids. Among the most
recent results I would like to mention Ch23 , where it was discovered that the
Partial-dual Genus Polynomial of ribbon graphs appearing from chord diagrams
is a weight system from the theory of Vassiliev knot invariants. Recently
(December 2023), Iain Moffatt informed me that he proved that Partial-dual
Genus Polynomial weight system comes from the Lie algebra $\mathfrak{gl}_{N}$
weight system. Also Q.Deng, F.Dong, X.Jin, Q.Yan DDJY  generalize this result
to the farmed chord diagrams.

###### Acknowledgements.

I am very grateful to the MATRIX Institute for providing excellent research
atmosphere for the Workshop on Uniqueness and Discernment in Graph Polynomials
in October 2023 and to the MATRIX-Simons Travel Grant for covering a big part
of my travel expenses.

## References

  * (1) A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program. 38 (1987) 147–159.
  * (2) A. Bouchet, A. Bouchet, Maps and delta-matroids, Discrete Math. 78 (1989) 59–71.
  * (3) S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, Journal of Combinatorial Theory, Ser. B 99(3) (2009) 617–638.
  * (4) S. Chmutov, Partial-dual genus polynomial as a weight system, Communications in Mathematics, 31(3) (2023) 113–124. doi.org/10.46298/cm.11709, 12 pages.
  * (5) S. Chmutov, I. Pak, The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial, Moscow Mathematical Journal, 7(3) (2007) 409–418.
  * (6) S. Chmutov, F.Vignes-Tourneret, On a conjecture of Gross, Mansour and Tucker. European Journal of Combinatorics, 97(3) (2021) doi:j.ejc.2021.103368, 1–7.
  * (7) S. Chmutov, F.Vignes-Tourneret, Partial Duality of Hypermaps. Arnold Mathematical Journal, (2022) doi:s40598-021-00194-8, 1–24.
  * (8) S. Chmutov, J. Voltz, Thistlethwaite’s theorem for virtual links, Journal of Knot Theory and its Ramifications, 17(10) (2008) 1189–1198.
  * (9) C. Chun, I. Moffatt, S. Noble, R. Rueckriemen, Matroids, Delta-matroids and Embedded Graphs, Journal of Combinatorial Theory, Series A, 167 (2019) 7–59. (journal / arXiv)
  * (10) C. Chun, I. Moffatt, S. Noble, R. Rueckriemen, On the interplay between embedded graphs and delta-matroids, Proceedings of the London Mathematical Society, 118 (2019) 675–700.
  * (11) O. Dasbach, D. Futer, E. Kalfagianni, X.-S. Lin, N. Stoltzfus, The Jones polynomial and dessins d’enfant, Journal of Combinatorial Theory, Ser.B, 98 (2008) 384–399.
  * (12) Q. Deng, F. Dong, X. Jin, Q. Yan, Partial-dual polynomial as a framed weight system. Preprint arXiv:2402.03799 [math.CO].
  * (13) M. Ellingham, X. Zha, Partial duality and closed 2-cell embeddings, Journal of Combinatorics 8(2) (2017) 227–254.
  * (14) J. A. Ellis-Monaghan, I. Moffatt, Graphs on Surfaces: Dualities, Polynomials, and Knots, Springer, 2013.
  * (15) J. L. Gross and T. W. Tucker, Topological graph theory, Wiley, NY, 1987.
  * (16) J. L. Gross, T. Mansour, T. W. Tucker, Partial duality for ribbon graphs, I: Distributions, European Journal of Combinatorics 86 (2020) 103084, 1–20.
  * (17) J. L. Gross, T. Mansour, T. W. Tucker, Partial duality for ribbon graphs, II: Partial-twuality polynomials and monodromy computations, European Journal of Combinatorics 95 (2021) 103329, 1–28.
  * (18) J. L. Gross, T. Mansour, T. W. Tucker, Enumerating Graph Embeddings and Partial-Duals by Genus and Euler Genus, Enumerative Combinatorics and Applications 1(1) (2021) #S2S1, 1–17.
  * (19) S. Lins, Graph-encoded maps, Journal of Combinatorial Theory, Ser. B, 32(2) (1982) 171–181.
  * (20) I. Moffatt, Separability and the genus of a partial dual, European Journal of Combinatorics 34 (2013) 355–378.
  * (21) B. Mohar, C. Thomassen, Graphs on Surfaces, The Johns Hopkins University Press, 2001.
  * (22) W. Tutte, Graph Theory, In: Rota, G.C. (ed.) Encyclopedia of Mathematics and its Applications, 21. Addison-Wesley Publishing Company, Boston (1984).
  * (23) Q. Yan, X. Jin, Counterexamples to a conjecture by Gross, Mansour, and Tucker on partial-dual genus polynomials of ribbon graphs, European Journal of Combinatorics 93 (2021) 103285, 1–12.
  * (24) Q. Yan, X. Jin, Counterexamples to the interpolating conjecture on partial-dual genus polynomials of ribbon graphs, European Journal of Combinatorics 102 (2022) 103493, 1–7.
  * (25) Q. Yan, X. Jin, Partial-dual polynomials and signed intersection graphs, Forum of Mathematics, Sigma 102(e69)(2022) 1–16.
  * (26) Q. Yan, X. Jin, Twist monomials of binary delta-matroids. Preprint `arXiv:2205.03487v1 [math.CO]`.
  * (27) Y. Yang, X. Zha, Partial-dual Euler-genus distributions for bouquets with small Euler genus, Ars Mathematica Contemporanea. 22(3) (2022) #P3.09, 13pp.
  * (28) D. Yuschak, Delta-matroids with twist monomials. To appear in European Journal of Combinatorics. Preprint `arXiv:2208.13258v1 [math.CO]`.


# Interpretable Signed Link Prediction with Signed Infomax Hyperbolic Graph

Yadan Luo, Zi Huang, Hongxu Chen, Yang Yang, Hongzhi Yin and Mahsa
Baktashmotlagh  Y. Luo, Z. Huang, M. Baktashmotlagh and H. Yin are with School
of Information Technology and Electrical Engineering, The University of
Queensland, Australia. E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Chen is with the School of
Computer Science in University of Technology Sydney, Australia. E-mail:
<EMAIL_ADDRESS>Y. Yang is with the Center for Future Media and the
School of Computer Science and Engineering, University of Electronic Science
and Technology of China, China. E-mail<EMAIL_ADDRESS>received
November 25, 2020. Manuscript revised June 13, 2021.

###### Abstract

Signed link prediction in social networks aims to reveal the underlying
relationships (i.e. links) among users (i.e. nodes) given their existing
positive and negative interactions observed. Most of the prior efforts are
devoted to learning node embeddings with graph neural networks (GNNs), which
preserve the signed network topology by message-passing along edges to
facilitate the downstream link prediction task. Nevertheless, the existing
graph-based approaches could hardly provide human-intelligible explanations
for the following three questions: (1) which neighbors to aggregate, (2) which
path to propagate along, and (3) which social theory to follow in the learning
process. To answer the aforementioned questions, in this paper, we investigate
how to reconcile the balance and status social rules with information theory
and develop a unified framework, termed as Signed Infomax Hyperbolic Graph
(SIHG). By maximizing the mutual information between edge polarities and node
embeddings, one can identify the most representative neighboring nodes that
support the inference of edge sign. Different from existing GNNs that could
only group features of friends in the subspace, the proposed SIHG incorporates
the signed attention module, which is also capable of pushing hostile users
far away from each other to preserve the geometry of antagonism. The polarity
of the learned edge attention maps, in turn, provides interpretations of the
social theories used in each aggregation. In order to model high-order user
relations and complex hierarchies, the node embeddings are projected and
measured in a hyperbolic space with a lower distortion. Extensive experiments
on four signed network benchmarks demonstrate that the proposed SIHG framework
significantly outperforms the state-of-the-arts in signed link prediction.

###### Index Terms:

link prediction; signed social network; mutual information maximization;
hyperbolic graph network.

##  1 Introduction

Understanding social interactions on the Web is critical for a broad set of
tasks, such as community detection [1, 2, 3], personalized recommendation [4,
5], fake account detection [6] and event prediction [7]. By giving thumbs up,
following and subscribing, users expose their positive preferences, support
and approval for others who share the same opinions. Users also link to
signify disapproval, disagreement, or distrust of others with negative
response such as blocking. In such a signed social network, users or entities
of interest are generally represented as nodes, and the mutual interactions
are modeled as edges (or links) with signs.

While important, the interplay of positive and negative relations poses a
great challenge to the vast majority of conventional online social network
research that only considers observed connections as positive links, which
refers to unsigned networks. Dedicated network embedding methods for unsigned
networks [8, 9, 10, 11, 12, 13, 14] developed in the past, have exploited the
fact that the node embeddings are highly correlated with the link structure of
the network. These algorithms, therefore, predominantly focus on node
representations and force the connected nodes to have similar latent features
to preserve both local connectivity and the high-order proximity among nodes
in a graph. By using the low-dimensional node vectors, traditional machine
learning methods can be applied to predict the connectivity between an
arbitrary pair of nodes. However, for the real-life networks which consist of
both positive and negative links (i.e. signed networks), the existing unsigned
link prediction techniques are not directly applicable by virtue of lacking a
specific mechanism to deal with the negative connections.

Figure 1: An illustration of the interpretability of the proposed model for
signed social networks. The learned signed attention maps are optimized by
maximizing the mutual information between the node representations and the
given edge polarity, which provide cues for discovering the underlying social
theories.

With a rapid development of graph neural networks (GNNs), recent works of SGCN
[15] and SNEA [16] have been focusing on re-designing deep graph models to
work with signed and undirected graph structures, where node features are
recursively aggregated with adjacent nodes along signed edges. The core idea
is based on one of the well-known social theories, the structural balance
theory [17]. It roughly implies that attitudes of a user can change based on
the assumption that a user’s friends of friends can be deduced as friends,
while enemies of friends can be considered as enemies. Nevertheless, as the
balance rule is only tenable under certain circumstances, the status theory
[18, 19, 20] is developed, which states that the signed links can be inferred
by comparing the users’ social status.

As modern social networks are complex and evolve quickly, user preferences or
opinions remain uncertain and unstable. Before reaching the convergence, the
underlying signed links cannot be explicitly predicted by either social
theory. For instance, as shown in Figure 1, given the positive link from user
$k$ to user $j$ and the negative link from user $j$ to user $i$, user $k$ will
be predicted as an enemy of user $i$ based on the balance theory, while as a
friend if it is based on the status theory. Thereby, in our work, we aim to
better comprehend the complex interplay between these two social theories and
jointly accommodate them in one unified framework to provide reasonable
explanations of the user interactions at the current stage.

Even though one of recent work [21] that attempts to combine two social
theories by manually defining 38 different types of local network motifs for
guiding aggregation, it is still non-trivial to propose such a unified
framework due to the following three challenges:

  * •

The existing graph-based models generally lack interpretability in a sense
that they do not easily allow for human-intelligible explanations of the
following questions: for each target node-pair, (1) which neighboring nodes
are decision-critical? (2) how to design the aggregation path for multi-hop
neighbors? and (3) which social theory can be referred to? While the first two
questions can be answered by inferring edge attention scores [16, 21], the
last one has not yet been investigated.

  * •

On the one hand, manually defining local motifs for aggregation is tedious and
time-consuming, especially in the presence of massive number of adjacent
neighbors. On the other hand, automatically embedding complex hierarchical
neighborhood structures in GCNs or GAT can incur a large distortion [22, 23].
As depicted in Figure 2, the positive and negative connections in signed
social networks at a large scale typically exhibit power-law distributions,
which implies the underlying node hierarchy is complex. Such a dilemma forces
common graph-based models to trade off between human-labors and prediction
accuracy.

  * •

Existing graph models do not define an inverse operation of grouping features,
which means that features of negative pairs could hardly be pushed away from
each other in the embedding space.

Figure 2: Positive and negative distributions in signed social networks. The
power-law distributions exhibited implies the underlying node hierarchy is
complex, which can not be well captured by Euclidean embeddings.

Core idea: To address the first challenge of endowing the models with
interpretability, we demonstrate our core idea in Figure 1. Inspired by recent
advances in information theory, our strategy is to learn the optimal signed
edge attention scores by maximizing the mutual information between the
adjacency matrix of the observed social networks and the concatenated
representations of the node pairs. By doing so, (1) the target nodes can
automatically identify the most representative positive or negative neighbors
multi-hops away that could support the prediction of the given edge polarity;
(2) the explanations for each aggregation can be discovered by comparing the
signs of the learned attention scores. For example, as shown in the Case 1 of
Figure 1, each node feature is comprised of a positive part (e.g., $P_{i}(1)$)
and a negative part (e.g., $N_{i}(1)$), where they represent the information
of the positive and negative neighborhood and $1$ indicates the first
aggregation layer. When aggregating the user $j$’s negative features
$N_{j}(1)$ at the first graph layer to the user $i$’s negative features
$N_{i}(2)$ at the second layer, one can identify the balance theory is applied
if the attention score $w_{ij}^{-(2)}$ is positive (e.g.,
$w_{ij}^{-(2)}=+0.6$); otherwise, the status rule is leveraged in this
aggregation (e.g., $w_{ij}^{-(2)}=-0.6$).

Specifically, in this paper, we propose a novel Signed Infomax Hyperbolic
Graph (SIHG) network to reconcile balance and status theories in the task of
signed link prediction. In order to fully inherit the rich hierarchical
information in signed graphs, we generalize graph neural network to operate on
a non-Euclidean space, where features from positive neighbors and negative
neighbors are separately aggregated in different hyperbolic manifolds. To
jointly realize the inclusion of features for friends and exclusion for foes
in the embedding space, a signed attention mechanism is further incorporated,
where positively linked nodes are mapped to close-by points whereas negatively
linked nodes are transformed far from each other in hyperbolic manifolds. In
line with the mutual information estimation, the learned attention scores
provide interpretable explanations of social theories. As the proposed SIHG is
agnostic to the choice of hyperbolic models, two hyperbolic models are
testified in our framework. Extensive experiments conducted on four signed
social network benchmarks evidence the superiority of the derived SIHG over
the state-of-the-art approaches. In summary, our contribution is four-fold.

  * •

We introduce a new Signed Infomax Hyperbolic Graph (SIHG) framework for signed
link prediction, which unifies two social theories and provides human-
intelligible interpretations by maximizing mutual information (addressing
challenge 1).

  * •

The projected hyperbolic space fully exploits the topology of users’ positive
and negative neighborhoods and learns the respective geometrical
representations. Two hyperbolic models of Hyperboloid and Poincaré Ball are
testified in our framework (addressing challenge 2).

  * •

By incorporating the mutual information estimation, the derived signed
attention module not only automatically learns the aggregation paths, but also
pushes the hostile user nodes far away from each other (addressing challenge
3).

  * •

We have demonstrated the effectiveness and interpretability of the proposed
SIHG through extensive quantitative experiments and qualitative visualizations
on four large-scale signed social network datasets. Source
code111https://github.com/Luoyadan/SIHG is provided for reference.

The rest of the paper is organized as follows. Section 2 introduces the
mathematical definition of the signed link prediction task and theoretical
foundations of signed social networks, followed by the details of the proposed
SIHG model. The experimental comparisons with state-of-the-art, ablation study
and visualizations are highlighted in Section 4. Section 5 presents a brief
review of recent advances in signed link prediction and mutual information
estimation. We conclude in Section 6.

Figure 3: An illustration of the (a) structural balance and (b) status
theories, and the suggested aggregation paths. The gray line with a ‘+’ symbol
refers to a positive connection, while the one with a ‘-’ symbol refers to a
negative connection. Green edges and red edges in the left figure indicates
the inferred positive and negative relations, respectively. The gray boxes
contain the triangles that do not satisfy the theory and yellow boxes include
Figure 4: An overview of the proposed Signed Infomax Hyperbolic Graph (SIHG)
architecture with $L$ graph layers. TABLE I: Summary of frequently used
notation.

Symbol | Description
---|---
Input Graph: |
$\mathcal{G}$ | Signed social network
$\mathcal{V}$ | Vertices
$\mathcal{E}^{+}$ | Positive edge sets
$\mathcal{E}^{-}$ | Negative edge sets
${\bm{A}}$ | Adjacency matrix
${\bm{v}}_{i}$ |  The $i$-th vertex
$x_{i}$ |
Hyperbolic: |
$c$ | The curvature of hyperbolic space
${\bm{o}}$ |  The origin in $\mathbb{H}^{d,K^{\prime}}$
$\mathcal{T}_{{\bm{o}}}\mathbb{H}^{d,K}$ |  The tangent space centered at point ${\bm{o}}$
$\mathcal{T}_{{\bm{x}}}\mathbb{H}^{d,K}$ |  The tangent space centered at point ${\bm{x}}$
$\mathbb{R}^{d}$ |  Euclidean space with dimension $d$
Operations: |
$P_{o\rightarrow x}^{K}(\cdot)$ |  Parallel transport from $\mathcal{T}_{{\bm{o}}}\mathbb{H}^{d,K}$ to $\mathcal{T}_{x}\mathbb{H}^{d,K}$
$\otimes^{H}$ | Multiplication in hyperbolic space
$\oplus^{H}$ | Addition in hyperbolic space
$\texttt{exp}_{{\bm{o}}}$ and $\texttt{exp}_{{\bm{x}}}$ | exponential map
$\texttt{exp}_{{\bm{o}}}$ and $\texttt{log}_{{\bm{x}}}$ | logarithmic map
$\texttt{Dist}({\bm{x}},{\bm{y}})$ |  Intrinsic distance between ${\bm{x}}$ and ${\bm{y}}$ in $\mathbb{H}^{d,K}$
$\|{\bm{v}}\|_{L}$ |  The norm of ${\bm{v}}$ in $\mathcal{T}_{x}\mathbb{H}^{d,K}$
Network: |
$\mathcal{G}_{P}$ | Positive branch of SIHG
$\mathcal{G}_{N}$ | Negative branch of SIHG
$\mathcal{G}_{P}^{(l),H}$ |  The $l$-th layer of positive branch
$\mathcal{G}_{N}^{(l),H}$ |  The $l$-th layer of negative branch
$\mathcal{V}^{P(l),H}$ |  The vertices at the $l$-th layer in the positive branch
$\mathcal{V}^{N(l),H}$ |  The vertices at the $l$-th layer in the negative branch
$\mathcal{N}^{+}(i)$ |  The positive neighbor sets of the $i$-th vertice
$\mathcal{N}^{-}(i)$ |  The negative neighbor sets of the $i$-th vertice
$h_{i}^{P(l),H}$ |  The $i$-th vertex’s feature at the $l$-th layer in the positive branch
$h_{i}^{N(l),H}$ |  The $i$-th vertex’s feature at the $l$-th layer in the negative branch
$z_{i}^{H}$ |  The final representation of the $i$-th vertex
$p_{ij}$ |  The edge prediction between the $i$-th vertex and the $j$-th vertex

##  2 Preliminaries

###  2.1 Problem Definition

A signed social network can either be modeled as a directed or undirected
graph $\mathcal{G}=(\mathcal{V},\mathcal{E}^{+},\mathcal{E}^{-})$ with a sign
on each edge $e_{ij}\in\mathcal{E}^{+}\cup\mathcal{E}^{-}$, where the vertices
$\mathcal{V}=\\{{\bm{v}}_{i}\\}_{i=1}^{N}$ represent a set of $N$ users. The
initial feature for each node is denoted as ${\bm{v}}_{i}\in\mathcal{V}$ with
${\bm{x}}_{i}\in\mathbb{R}^{d}$, where $d$ is the dimension of node
embeddings. ${\bm{A}}\in\mathbb{R}^{N\times N}$ is the adjacency matrix of the
signed network, where ${\bm{A}}_{ij}=1$, if there is a positive link from
${\bm{v}}_{i}$ to ${\bm{v}}_{j}$, and ${\bm{A}}_{ij}=0$ for a negative link.
For all ${\bm{A}}_{ij}$ which are equal to 0.5, there is no directed edge from
${\bm{v}}_{i}$ to ${\bm{v}}_{j}$. Positive edges
$\mathcal{E}^{+}=\\{e_{ij}|{\bm{A}}_{ij}=1\\}_{i,j=1}^{N}$, and negative edges
$\mathcal{E}^{-}=\\{e_{ij}|{\bm{A}}_{ij}=0\\}_{i,j=1}^{N}$ are partially
observed at the training stage. The signed link prediction problem which we
address here is to predict if a pair of nodes in $\mathcal{V}$ will remain
disconnected or will be connected by a positive or negative link.

###  2.2 Balance and Status Theories

We start by introducing the two fundamental social-psychological theories,
which are illustrated in Figure 3.

Structural Balance Theory [20]: is based on the common principles that “the
friend of my friend is my friend” and “the foe of my friend is my foe”. For
instance, in Figure 3(a), if node ${\bm{v}}_{k_{1}}$ forms a triad with the
edge $e_{ij_{1}}$, the triangle on
$({\bm{v}}_{i},{\bm{v}}_{j_{1}},{\bm{v}}_{k_{1}})$ should have an odd number
of positive signs regardless of edge direction. Those triads that obey
structural balance theory refer to balanced triangles, such as
$({\bm{v}}_{i},{\bm{v}}_{j_{1}},{\bm{v}}_{k_{1}})$ and
$({\bm{v}}_{i},{\bm{v}}_{j_{2}},{\bm{v}}_{k_{2}})$ shown in the yellow dotted
box. Otherwise, they are called as unbalanced triangles as highlighted in the
grey dotted box.

Status Theory: Alternatively, another theory is developed based on the notion
of status [18, 19], as shown in Figure 3(b). The status may indicate the
relative prestige, ranking, or reputation. The status theory posits that, in a
positive edge $e_{ij}$, user $i$ regards user $j$ as having a higher status,
while in a negative edge $e_{ij}$, user $i$ regards user $j$ as having a lower
status. By assuming that all nodes follow the status ordering, the edge sign
should flip if its direction is flipped.

Comparison. Based on different social theories, the latent representation of
each node $i$ in a signed graph will be updated along various aggregation
paths, which are demonstrated in Figure 3. For instance, according to balance
theory, the first-order positive neighbors (e.g., ${\bm{v}}_{j_{2}}$) of node
${\bm{v}}_{i}$ and the second-order negative neighbors (e.g.,
${\bm{v}}_{k_{2}}$) will be grouped in ${\bm{P}}_{i}(1)$ and
${\bm{N}}_{i}(2)$, respectively. To this end, the edge polarity between
${\bm{v}}_{i}$ and ${\bm{v}}_{k_{2}}$ can be inferred by measuring the
similarity of the respective node embeddings.

Discussion. By comparing each of four typical types of signed triangles, the
following two observations can be drawn:

  1. 1.

The edge sign cannot be simply inferred by either of the theories, due to the
conflicts in some cases. For example, the triangle $(i,j_{2},k_{2})$ that
satisfies status theory are not balanced.

  2. 2.

For the same signed social network, the learned node embeddings can still vary
significantly according to different theories. For example, with negative
links $e_{ij_{2}}$ and $e_{j_{2}k_{2}}$, the representation of node
${\bm{v}}_{k_{2}}$ should be far from the feature of node ${\bm{v}}_{i}$ in
status theory, which is opposite to the situation in balance theory.

Motivated by the observations mentioned above, we aim to derive a unified
framework that dynamically chooses a proper path to aggregate node embeddings
and predict edge polarities. The core principle behind the framework is to
infer the missing signs of edges that provides interpretable explanations for
the given edge labels, which can be achieved by maximizing the mutual
information in the signed social networks.

##  3 Methodology

In this section, we go through the details of the proposed Signed Infomax
Hyperbolic Graph (SIHG) framework as illustrated in Figure 4. In order to
embed the positive and negative neighbors’ information hierarchically and
structurally, we firstly split the node representations into two part and
construct two $L$-layer hyperbolic graph sub-networks, i.e.,
$\mathcal{G}_{P}=\\{\mathcal{G}_{P}^{(l),H}=(\mathcal{V}^{P(l),H},\mathcal{E}^{+},\mathcal{E}^{-})\\}_{l=1}^{L}$
and
$\mathcal{G}_{N}=\\{\mathcal{G}_{N}^{(l),H}=(\mathcal{V}^{N(l),H},\mathcal{E}^{+},\mathcal{E}^{-})\\}_{l=1}^{L}$
for passing messages of positive and negative neighbors $L$-hops away,
respectively. The superscript H denotes hyperbolic embedding and the
superscripts P and N indicate the positive and negative semantics,
respectively. Each positive node
${\bm{v}}_{i}^{P(l),H}\in\mathcal{V}^{P(l),H}$ and each negative node
${\bm{v}}_{i}^{N(l),H}\in\mathcal{V}^{N(l),H}$ at the $l$-th layer are
associated with hidden features of ${\bm{h}}_{i}^{P(l),H}\in\mathbb{H}^{d,K}$
and ${\bm{h}}_{i}^{N(l),H}\in\mathbb{H}^{d,K}$, where $\mathbb{H}^{d,K}$ is
the hyperbolic manifold in $d$ dimensions with constant negative curvature
$c=-1/K(K>0)$. As the input node feature $x_{i}^{0,E}\in\mathbb{R}^{d}$ is in
a Euclidean space (denoted with the superscript E), we first transform it to
the hyperbolic space via the $\texttt{exp}_{{\bm{o}}}$ map (Section 3.1), and
then leverage the signed attention strategy to aggregate the features from
neighborhoods (Section 3.2). The aggregation is guided by maximizing the
mutual information between the concatenated node features and edge signs, as
discussed in Section 3.3. To this end, two fundamental social theories can be
seamlessly reconciled and interpreted by the learned attention maps.

###  3.1 Hyperbolic Transformation

Before formalizing the hyperbolic transformations for input Euclidean node
features, we start by outlining a relationship between the Euclidean space and
Hyperbolic space. A hyperbolic space is a homogeneous space that has a
constant negative curvature, which is distinguished from Euclidean spaces with
zero curvature ($c=0$). While the tangent spaces of the points on hyperbolic
manifold are isometric to $\mathbb{R}^{d}$, the Euclidean transformation can
be performed in $\mathcal{T}_{{\bm{o}}}\mathbb{H}^{d,K}$, where
${\bm{o}}:=\\{\sqrt{K},0,\ldots,0\\}\in\mathbb{H}^{d,K}$ is the origin in
$\mathbb{H}^{d,K}$. Motivated by this, we regard $(0,{\bm{x}}^{0,E})$ as a
point in the tangent space $\mathcal{T}_{{\bm{o}}}\mathbb{H}^{d,K}$ and
project it to hyperbolic space by $\texttt{exp}_{{\bm{o}}}$ map, where
${\bm{o}}$ serves as a reference point to :

$\displaystyle{\bm{x}}^{0,H}=\texttt{exp}_{{\bm{o}}}(0,{\bm{x}}^{0,E}),$ (1)

with ${\bm{x}}^{0,H}$ the corresponding point in $\mathbb{H}^{d,K}$. For
linear transformation of a point in a Hyperbolic space, we define the
following operations:

$\displaystyle\begin{split}&{\bm{x}}^{H}={\bm{W}}\otimes^{H}{\bm{x}}^{0,H}\oplus^{H}{\bm{b}},\\\
&{\bm{W}}\otimes^{H}{\bm{x}}:=\texttt{exp}_{{\bm{o}}}({\bm{W}}\texttt{log}_{{\bm{o}}}({\bm{x}})),\\\
&{\bm{x}}\oplus^{H}{\bm{b}}:=\texttt{exp}_{{\bm{x}}}(P_{o\rightarrow
x}^{K}({\bm{b}})),\end{split}$ (2)

where ${\bm{W}}\in\mathbb{R}^{d\times d}$ is a learnable weight matrix, and
${\bm{b}}\in\mathbb{R}^{d}$ is a bias. The $P_{o\rightarrow x}^{K}(\cdot)$ is
the parallel transport from $\mathcal{T}_{{\bm{o}}}\mathbb{H}^{d,K}$ to
$\mathcal{T}_{x}\mathbb{H}^{d,K}$. There are several important models of
hyperbolic space such as the Klein model, Hyperboloid model, and Poincaré ball
model, in which the differentiable operations log and exp can be implemented
differently. Any two of the aforementioned models can be related by a
transformation that preserves all the geometrical properties of the space,
including isometry. Without lose of generality, here, we introduce the
following two hyperbolic models in our framework:

####  3.1.1 Hyperboloid Model

The hyperboloid model, also called as Lorentz model, is defined as
$\mathbb{H}^{d,K}:=\\{{\bm{x}}\in\mathbb{R}^{d+1}:\langle{\bm{x}},{\bm{x}}\rangle_{L}=-K,x_{0}>0\\}$,
where
$\langle\cdot,\cdot\rangle_{L}:\mathbb{R}^{d+1}\times\mathbb{R}^{d+1}\rightarrow\mathbb{R}$
indicating the Minkowski inner product, specifically
$\langle{\bm{x}},{\bm{y}}\rangle_{L}:=-x_{0}y_{0}+x_{1}y_{1}+\ldots+x_{d}y_{d}$.
The tangent space centered at point x is
$\mathcal{T}_{x}\mathbb{H}^{d,K}:=\\{{\bm{v}}\in\mathbb{R}^{d+1}:\langle{\bm{v}},{\bm{x}}\rangle_{L}=0\\}$.
The mapping between tangent space and hyperbolic space is through exponential
and logarithmic maps, respectively. The exponential map
$\texttt{exp}_{{\bm{x}}}:\mathcal{T}_{{\bm{x}}}\mathbb{H}^{d,K}\rightarrow\mathbb{H}^{d,K}$,
and the logarithmic map
$\texttt{log}_{{\bm{x}}}:\mathbb{H}^{d,K}\rightarrow\mathcal{T}_{{\bm{x}}}\mathbb{H}^{d,K}$
of the hyperboloid model are given by:

$\begin{split}&\texttt{exp}_{{\bm{x}}}({\bm{v}})=\text{cosh}(\frac{\|{\bm{v}}\|_{L}}{\sqrt{K}}){\bm{x}}+\sqrt{K}\text{sinh}(\frac{\|{\bm{v}}\|_{L}}{\sqrt{K}})\frac{{\bm{v}}}{\|{\bm{v}}\|_{L}},\\\
&\texttt{log}_{{\bm{x}}}({\bm{y}})=\texttt{Dist}({\bm{x}},{\bm{y}})\frac{{\bm{y}}+\frac{1}{K}\langle{\bm{x}},{\bm{y}}\rangle_{L}{\bm{x}}}{\|{\bm{y}}+\frac{1}{K}\langle{\bm{x}},{\bm{y}}\rangle_{L}{\bm{x}}\|_{L}},\\\
&\texttt{Dist}({\bm{x}},{\bm{y}})=\sqrt{K}\text{arcosh}(-\langle{\bm{x}},{\bm{y}}\rangle_{L}/K),\end{split}$
(3)

where ${\bm{v}}\in\mathcal{T}_{x}\mathbb{H}^{d,K}$ and
${\bm{x}},{\bm{y}}\in\mathbb{H}^{d,K}$. $\texttt{Dist}({\bm{x}},{\bm{y}})$
indicate the intrinsic distance between two points ${\bm{x}}$ and ${\bm{y}}$
in $\mathbb{H}^{d,K}$. We denote
$\|{\bm{v}}\|_{L}=\sqrt{\langle{\bm{v}},{\bm{v}}\rangle_{L}}$ as the norm of
${\bm{v}}\in\mathcal{T}_{x}\mathbb{H}^{d,K}$.

####  3.1.2 Poincaré Ball Model

The Poincaré Ball model with constant negative curvature
($c=-\frac{1}{K},K>0$) is an open unit ball, i.e.,
$\mathbb{H}^{d,K}:=\\{{\bm{x}}\in\mathbb{R}^{d}:\|{\bm{x}}\|<1\\}$. For any
point ${\bm{x}}\in\mathbb{H}^{d,K}$, the exponential map
$\texttt{exp}_{{\bm{x}}}:\mathcal{T}_{{\bm{x}}}\mathbb{H}^{d,K}\rightarrow\mathbb{H}^{d,K}$
and the logarithmic map
$\texttt{log}_{{\bm{x}}}:\mathbb{H}^{d,K}\rightarrow\mathcal{T}_{{\bm{x}}}\mathbb{H}^{d,K}$
are defined, respectively, as:

(4)

where $\oplus$ is the Mobius addition for any
${\bm{x}},{\bm{y}}\in\mathbb{H}^{d,K}$. Mobius addition is defined as,

$\displaystyle{\bm{x}}\oplus{\bm{y}}=\frac{(1+\frac{2}{K}\langle{\bm{x}},{\bm{y}}\rangle+\frac{1}{K}\|{\bm{y}}\|^{2}){\bm{x}}+(1-\frac{1}{K}\|{\bm{x}}\|^{2}){\bm{y}}}{1+\frac{2}{K}\langle{\bm{x}},{\bm{y}}\rangle+\frac{1}{K^{2}}\|{\bm{x}}\|^{2}\|{\bm{y}}\|^{2}},$
(5)

with $\langle\cdot,\cdot\rangle$ being the inner product.

###  3.2 Signed Neighbor Aggregation

In this section, we discuss how to aggregate node’s information from its
positive and negative neighborhood after obtaining the transformed features on
the hyperbolic space. We first define the set of positive and negative
neighbors of a user $i$ to be $\mathcal{N}^{+}(i)$ and $\mathcal{N}^{-}(i)$,
respectively. For the first aggregation layer, we have

$\begin{split}&{\bm{h}}_{i}^{P(1),H}=\texttt{exp}_{{\bm{x}}_{i}^{H}}\Big{(}\sigma\big{(}{\bm{W}}^{(1)}_{p}[\sum_{j\in\mathcal{N}^{+}(i)}{\bm{w}}^{+(1)}_{ij}\texttt{log}_{{\bm{o}}}({\bm{x}}_{j}^{H}),{\bm{x}}_{i}^{H}]\big{)}\Big{)},\\\
&{\bm{h}}_{i}^{N(1),H}=\texttt{exp}_{{\bm{x}}_{i}^{H}}\Big{(}\sigma\big{(}{\bm{W}}^{(1)}_{n}[\sum_{j\in\mathcal{N}^{-}(i)}{\bm{w}}^{-(1)}_{ij}\texttt{log}_{{\bm{o}}}({\bm{x}}_{j}^{H}),{\bm{x}}_{i}^{H}]\big{)}\Big{)},\\\
&{\bm{w}}_{ij}^{+(1)}=\mathcal{F}_{j\in\mathcal{N}^{+}(i)}\Big{(}\sigma({\bm{a}}^{(1)T}_{p}[{\bm{W}}^{(1)}_{pw}\texttt{log}_{{\bm{o}}}{\bm{x}}^{H}_{i},{\bm{W}}^{(1)}_{pw}\texttt{log}_{{\bm{o}}}{\bm{x}}^{H}_{j}])\Big{)},\\\
&{\bm{w}}_{ij}^{-(1)}=\mathcal{F}_{j\in\mathcal{N}^{-}(i)}\Big{(}\sigma({\bm{a}}^{(1)T}_{n}[{\bm{W}}^{(1)}_{nw}\texttt{log}_{{\bm{o}}}{\bm{x}}^{H}_{i},{\bm{W}}^{(1)}_{nw}\texttt{log}_{{\bm{o}}}{\bm{x}}^{H}_{j}])\Big{)},\end{split}$

(6)

where the function
$\mathcal{F}_{j\in\mathcal{N}(i)}({\bm{x}})=(2e^{{\bm{x}}_{i}}/\sum_{j}e^{{\bm{x}}_{j}})-1$
regularizes the attention weights $w_{ij}^{+(1)},w_{ij}^{-(1)}$ in a range of
$(-1,1)$. ${\bm{W}}^{(1)}_{p},{\bm{W}}^{(1)}_{n}\in\mathbb{R}^{d\times 2d}$,
${\bm{a}}^{(1)}_{p},{\bm{a}}^{(1)}_{n}\in\mathbb{R}^{2d\times d}$, and
${\bm{W}}^{(1)}_{pw},{\bm{W}}^{(1)}_{nw}\in\mathbb{R}^{d\times d}$ are the
weight matrices. $\sigma(\cdot)$ is the LeakyReLU activation, with
$[\cdot,\cdot]$ being the concatenation operation. The hidden representation
${\bm{h}}_{i}^{P(1),H}\in\mathbb{H}^{d,K}$ and
${\bm{h}}_{i}^{N(1),H}\in\mathbb{H}^{d,K}$ collect the positive and negative
supports from the adjacent positive and negative neighbors, respectively,
which allow to embed node features close to positive neighbors and distant to
negative neighbors. However, for multi-hop neighborhood, the relationships
become complex to determine. According to Figure 3, the aggregation rule for
$l>1$ is defined as,

$\begin{split}&\hat{{\bm{h}}}_{i}^{P(l),H}=[\sum_{j\in\mathcal{N}^{+}(i)}{\bm{w}}^{+(l)}_{ij}\texttt{log}_{{\bm{o}}}({\bm{h}}_{j}^{P(l-1),H}),\sum_{k\in\mathcal{N}^{-}(i)}{\bm{w}}^{-(l)}_{ik}\texttt{log}_{{\bm{o}}}({\bm{h}}_{k}^{N(l-1),H})],\\\
&\hat{{\bm{h}}}_{i}^{N(l),H}=[\sum_{j\in\mathcal{N}^{-}(i)}{\bm{w}}^{-(l)}_{ij}\texttt{log}_{{\bm{o}}}({\bm{h}}_{j}^{N(l-1),H}),\sum_{k\in\mathcal{N}^{+}(i)}{\bm{w}}^{+(l)}_{ik}\texttt{log}_{{\bm{o}}}({\bm{h}}_{k}^{P(l-1),H})],\\\
&{\bm{h}}_{i}^{P(l),H}=\texttt{exp}_{{\bm{h}}_{i}^{P(l-1),H}}\Big{(}\sigma\big{(}{\bm{W}}^{(l)}_{p}[\hat{h}_{i}^{P(l),H},{\bm{h}}_{i}^{P(l-1),H}]\big{)}\Big{)},\\\
&{\bm{h}}_{i}^{N(l),H}=\texttt{exp}_{{\bm{h}}_{i}^{N(l-1),H}}\Big{(}\sigma\big{(}{\bm{W}}^{(l)}_{n}[\hat{h}_{i}^{N(l),H},{\bm{h}}_{i}^{N(l-1),H}]\big{)}\Big{)}.\end{split}$

(7)

The node latent feature will be updated iteratively with the weighted
aggregation of neighbors’ features. The weight factors for positive and
negative neighbors’ features are calculated as,

$\begin{split}&w_{ij}^{+(l)}=\mathcal{F}_{j\in\mathcal{N}^{+}(i)}\Big{(}\sigma({\bm{a}}^{(l)T}_{p}[{\bm{W}}^{(l)}_{pw}\texttt{log}_{{\bm{o}}}{\bm{h}}_{i}^{P(l-1),H},{\bm{W}}_{pw}^{(l)}\texttt{log}_{{\bm{o}}}{\bm{h}}_{j}^{P(l-1),H}])\Big{)},\\\
&w_{ij}^{-(l)}=\mathcal{F}_{j\in\mathcal{N}^{-}(i)}\Big{(}\sigma({\bm{a}}^{(l)T}_{n}[{\bm{W}}^{(l)}_{nw}\texttt{log}_{{\bm{o}}}{\bm{h}}_{i}^{N(l-1),H},{\bm{W}}_{nw}^{(l)}\texttt{log}_{{\bm{o}}}{\bm{h}}_{j}^{N(l-1),H}])\Big{)},\\\
&w_{ik}^{+(l)}=\mathcal{F}_{k\in\mathcal{N}^{+}(i)}\Big{(}\sigma({\bm{a}}^{(l)T}_{p}[{\bm{W}}^{(l)}_{nw}\texttt{log}_{{\bm{o}}}{\bm{h}}_{i}^{N(l-1),H},{\bm{W}}_{pw}^{(l)}\texttt{log}_{{\bm{o}}}{\bm{h}}_{k}^{P(l-1),H}])\Big{)},\\\
&w_{ik}^{-(l)}=\mathcal{F}_{k\in\mathcal{N}^{-}(i)}\Big{(}\sigma({\bm{a}}^{(l)T}_{n}[{\bm{W}}^{(l)}_{pw}\texttt{log}_{{\bm{o}}}{\bm{h}}_{i}^{P(l-1),H},{\bm{W}}_{nw}^{(l)}\texttt{log}_{{\bm{o}}}{\bm{h}}_{k}^{N(l-1),H}])\Big{)},\end{split}$

(8)

with
$\mathcal{F}_{j\in\mathcal{N}(i)}({\bm{x}})=(2e^{{\bm{x}}_{i}}/\sum_{j}e^{{\bm{x}}_{j}})-1$.
Similarly, ${\bm{W}}^{(l)}_{p},{\bm{W}}^{(l)}_{n}\in\mathbb{R}^{d\times 2d}$,
${\bm{a}}^{(l)}_{p},{\bm{a}}^{(l)}_{n}\in\mathbb{R}^{2d\times d}$ and
${\bm{W}}^{(l)}_{pw},{\bm{W}}^{(l)}_{nw}\in\mathbb{R}^{d\times d}$ are
learnable weight matrices. The final representation
${\bm{z}}_{i}^{H}\in\mathbb{H}^{d,K}$ for each node $i$ at the $L$-th layer
can be obtained by,

${\bm{z}}_{i}^{H}=[{\bm{h}}_{i}^{P(L),H},{\bm{h}}_{i}^{N(L),H}].$ (9)

###  3.3 Mutual Information Maximization

For guiding the path of aggregation between balance theory and status theory,
a Shannon entropy-based measure, i.e., Mutual information (MI) is leveraged to
measure the correlations between the adjacency matrix ${\bm{A}}$ and the
concatenated representations of node-pairs ${\bm{Z}}$, with
${\bm{z}}_{ij}=[{\bm{z}}_{i}^{H},{\bm{z}}_{j}^{H}]\in\mathbb{H}^{2d,K}$. By
maximizing the mutual information, it is anticipated that the models can
identify a subset of node neighbors that are most influential for the edge
prediction during the message passing and determine either push the neighbors’
features closer or further in the node embedding space. To measure the mutual
dependence between the two variables ${\bm{Z}}$ and ${\bm{A}}$, we first
introduce some notations for calculation. Let (${\bm{Z}}$, ${\bm{A}}$) be a
pair with values over the space $\mathcal{Z}\times\mathcal{A}$. The joint
distribution is denoted by $\mathbb{P}_{{\bm{Z}}{\bm{A}}}$ and the marginal
distributions are $\mathbb{P}_{{\bm{Z}}}$ and $\mathbb{P}_{{\bm{A}}}$,
respectively. Based on the principle of [24, 25], the mutual information
$I({\bm{Z}},{\bm{A}})$ is equivalent to the Kullback-Leibler (KL) divergence
between the joint and product of the marginals,
$\mathbb{P}_{{\bm{Z}}{\bm{A}}}$ and
$\mathbb{P}_{{\bm{Z}}}\otimes\mathbb{P}_{{\bm{A}}}$:

$\begin{split}I({\bm{Z}},{\bm{A}})&=D_{KL}(\mathbb{P}_{{\bm{Z}}{\bm{A}}}\;\|\;\mathbb{P}_{{\bm{Z}}}\otimes\mathbb{P}_{{\bm{A}}}),\\\
&=\mathbb{E}_{\mathbb{P}_{{\bm{Z}}{\bm{A}}}}[\log\frac{d\mathbb{P}_{{\bm{Z}}{\bm{A}}}}{d\mathbb{P}_{{\bm{Z}}\otimes{\bm{A}}}}].\\\
\end{split}$ (10)

Here we consider $\mathbb{P}_{{\bm{Z}}{\bm{A}}}$ amd
$\mathbb{P}_{{\bm{Z}}\otimes{\bm{A}}}$ as being distributions on a compact
domain $\Omega\in\mathbb{R}^{2d}$. Equation (10) can be interpreted as, the
larger the divergence between the joint and the product of the marginals, the
stronger the dependence between ${\bm{Z}}$ and ${\bm{A}}$. Maximizing mutual
information forces the node embeddings to aggregate features from their
positive and negative neighbors within $L$ hops. However, both the joint
distribution and marginal distributions are intractable for optimization,
which motivates various approaches to estimate the tractable lower bound of
mutual information. One of the most commonly used is the Donsker-Varadhan
representation [26] of the KL-divergence, with which the lower-bound to the
mutual information $\hat{I}_{\theta}({\bm{Z}},{\bm{A}})$ can be derived as,

$\begin{split}\hat{I}_{\theta}({\bm{Z}},{\bm{A}}):=\underset{T:\Omega\rightarrow\mathbb{R}}{\text{sup}}\mathbb{E}_{\mathbb{P}_{{\bm{Z}}{\bm{A}}}}[T_{{\bm{\theta}}}]-\log(\mathbb{E}_{\mathbb{P}_{{\bm{Z}}}\otimes\mathbb{P}_{{\bm{A}}}}[e^{T_{\theta}}]),\end{split}$
(11)

where $T_{{\bm{\theta}}}:{\bm{Z}}\times{\bm{A}}\rightarrow\mathbb{R}$ is a
discriminator function parameterized by ${\bm{\theta}}$, which takes the
${\bm{Z}}$ and ${\bm{A}}$ as inputs and turns a value vector. More details of
$T_{{\bm{\theta}}}$ can be found in Section 4.3. The expectations in Equation
(11) are finite and can be estimated using i.i.d samples from the joint
distribution and shuffled samples from the respective marginal distributions,
respectively. The objective function in Equation (12) can be maximized by
gradient ascent, as:

$\mathcal{L}_{mim}=-\hat{I}_{\theta}({\bm{Z}},{\bm{A}}).$ (12)

###  3.4 Edge Classifier and Training Objectives

For the task of signed link prediction, we use the Fermi-Dirac decoder to
generate the predictions, which are supervised by a binary cross entropy loss:

$\begin{split}&p_{ij}=[e^{(\texttt{Dist}({\bm{z}}_{i}^{H},{\bm{z}}_{j}^{H})^{2}-r)/t}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+1\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}]^{-1},\\\
&\mathcal{L}_{cls}=\sum_{i,j\in\mathcal{V}}{\bm{A}}_{ij}\text{log}(p_{ij})+(1-{\bm{A}}_{ij})\text{log}(1-p_{ij}),\end{split}$
(13)

with $r$ and $t$ being the hyperparameters. To further constrain the node
embeddings, we design a positive ranking loss and a negative ranking loss,
respectively. For each positive or negative pair of users $(i,j)$, we randomly
sample a neutral user $k$ which has no link to the anchor $i$. The following
objectives enable the positively linked users closer (and negatively linked
users farther) in the embedded space than the no-link pairs $(i,k)$:

$\begin{split}\mathcal{L}_{pos}=\sum_{(i,j)\in\mathcal{E}^{+},k}max(0,\texttt{Dist}({\bm{z}}_{i}^{H},{\bm{z}}_{j}^{H})-\texttt{Dist}({\bm{z}}_{i}^{H},{\bm{z}}_{k}^{H})),\\\
\mathcal{L}_{neg}=\sum_{(i,j)\in\mathcal{E}^{-},k}max(0,\texttt{Dist}({\bm{z}}_{i}^{H},{\bm{z}}_{k}^{H})-\texttt{Dist}({\bm{z}}_{i}^{H},{\bm{z}}_{j}^{H})).\end{split}$
(14)

Lastly, the model is jointly trained by edge classification loss, mutual
information loss, and two embedding losses:

$\mathcal{L}=\mathcal{L}_{cls}+\alpha\mathcal{L}_{pos}+\beta\mathcal{L}_{neg}+\gamma\mathcal{L}_{mim},$
(15)

where $\alpha$, $\beta$, and $\gamma$ denote the loss coefficients,
respectively.

##  4 Experimental Settings

###  4.1 Datasets and Evaluation Metrics

In this section, we conduct extensive experiments on four real-world signed
social network datasets, i.e., Bitcoin-Alpha222http://www.btcalpha.com/,
Bitcoin-OTC333http://www.bitcoin-otc.com/, Slashdot444http://slashdot.org/,
Epinions555http://www.epinions.com/. The general statistics of the four
network datasets are summarized in Table II .

  * •

Bitcoin-Alpha and Bitcoin-OTC [27, 28] are two who-trusts-whom networks of
Bitcoin trading. Members of Bitcoin Alpha and OTC rate other members as trust
or distrust to prevent transactions from risky users.

  * •

Slashdot [19] is collected from a technology-related news website known for
its specific user community. The website features user-submitted and editor-
evaluated technology oriented news. It allows users to tag each other as
friends (positive links) or foes (negative links).

  * •

Epinions [19] is a trust network for the consumer review site. All the trust
relationships interact and form the Web of Trust, which is then combined with
review ratings to determine which reviews are shown to the user.

In order to predict the link relationship of the unconnected node pairs, we
randomly select $20\%$ of the links in the social networks to form a test set,
with the remaining links as the training set. We utilize the standard metrics
i.e., area under curve (AUC), F1 score, macro-averaged F1 score, and micro-
averaged F1 score to evaluate the prediction performance.

###  4.2 Baselines Methods

We compare our approach with the following signed network embedding and link
prediction methods:

  * •

TSVD [29]: performs linear dimensionality reduction by means of truncated
singular value decomposition (SVD).

  * •

SSE [30]: reformulates the Rayleigh quotient as an objective for embedding
learning.

  * •

SiNE [31]: optimizes an objective function guided by social theory in signed
networks to generate the node embeddings in a deep learning framework.

  * •

SIDE [32]: provides a linearly scalable method to obtain the low-dimensional
vectors with random walks.

  * •

SIGNet [33]: builds upon word2vec embedding approaches and adds a sampling
strategy to maintain balance in high-order neighborhoods.

  * •

SGCN [15]: generalizes GNNs to a signed network for the first time. It designs
a new aggregation strategy for undirected signed network.

  * •

SiGAT [21]: incorporates graph motifs into GAT to capture the balance theory
and status theory jointly.

  * •

SNEA [16]: proposes a graph attention layer to estimate the importance
coefficients for the node pairs.

###  4.3 Implementation Details

Our source code is based on PyTorch [34], which is available in an anonymous
repository666https://github.com/Luoyadan/SIHG for reference. All experiments
are conducted on two servers with two GeForce GTX 2080 Ti GPUs. Similar to
previous works in this area [15], random seed is set to 42. For fair
comparisons, the feature dimensions of node embedding $d$ are fixed to 64. The
total number of training epochs $M$ is 800 for Bitcoin-Alpha and Bitcoin-OTC
datasets, 900 for Slashdot and Epinions datasets. The Adam optimizer is
applied with a weight decay of $1\times 10^{-5}$. The learning rate $\mu$ is
initiated to be $1\times 10^{-2}$ for Bitcoin-Alpha and Bitcoin-OTC datasets,
and $5\times 10^{-3}$ for Slashdot and Epinions datasets. The learning rate is
adapted by a cosine annealing schedule. The node embedding is initialized with
TruncatedSVD [29], with maximum 30 iterations. The optimal loss coefficients
$\alpha$, $\gamma$ are searched with optuna [35] framework, and $\beta$ is
empirically set to 0.83 for all tasks. The hyperparameter $r$ and $t$ for edge
classifier are fixed to 2 and 1, respectively. Without loss of generality, we
set the curvature $K=1$ (i.e. $c=-1$), which can be further tuned for
$\mathcal{G}_{p}$ and $\mathcal{G}_{n}$. The $T_{{\bm{\theta}}}$ network
firstly maps each node-pair representation / edge sign from $128$-D / $1$-D to
$128$-D with two fully connected layers. It then projects the addition of the
two 128-D vectors to 1-D scores with a LeakyReLU and a fully connected layer.

TABLE II: The general statistics of the four datasets used in our experiments.

Datasets | # Nodes | # Links | % Positive Links | % Negative Links
---|---|---|---|---
Bitcoin-Alpha | 3,783 | 14,145 | 89.99 | 10.01
Bitcoin-OTC | 5,881 | 21,522 | 85.45 | 14.55
Slashdot | 82,140 | 549,202 | 77.40 | 22.60
Epinions | 131,827 | 841,372 | 85.30 | 14.70

##  5 Experimental Results and Analysis

Following the settings in Section 4, we conduct experiments to evaluate the
performance of the proposed SIHG regarding both the signed link prediction
effectiveness and interpretation quality. In particular, we aim to answer the
following research questions (RQs) via experiments:
RQ1: How effectively can SIHG perform signed link prediction compared with
state-of-the-art baselines?
RQ2: What is the contribution of each key component of the proposed model
structure?
RQ3: How the hyperparameters affect the performance of SIHG in terms of
prediction effectiveness?
RQ4: How is the quality of the learned node representations?
RQ5: How to interpret the underlying social theories with the learned signed
attention maps?

###  5.1 Signed Link Prediction Effectiveness (RQ1)

In Table III, we report the signed link prediction results across the four
benchmark datasets in terms of AUC and F1 scores. The baseline results refer
to [16, 15]. The graph depth $L$ is fixed to 3 and the Hyperboloid model is
incorperated in SIHG. In order to fully investigate the graph-based baselines
that are highly related to our work, we re-implement SGCN, SiGAT, and SNEA,
and additionally report the macro-F1 and micro-F1 scores in Table IV. It is
observed that the proposed SIHG framework is superior to all the compared
methods in most cases. Among the four commonly-used evaluation metrics, the
AUC scores of SIHG are boosted by the largest margin ($13.03\%$ on Slashdot)
over the best performing baseline, especially on the large-scale datasets,
while the macro-F1 scores are slightly weaker. We infer this result is due to
using macro-average, which computes the score independently for each class
(i.e. $-1,1$) and treats all classes equally. Therefore, using macro-F1 cannot
fairly testify the prediction quality on extremely biased datasets such as
signed social networks.

TABLE III: AUC and F1 scores of predicting signed edges among four datasets.

Method | Bitcoin-Alpha | Bitcoin-OTC | Slashdot | Epinions
---|---|---|---|---
AUC | F1 | AUC | F1 | AUC | F1 | AUC | F1
TSVD [29] | 0.740 | 0.863 | 0.761 | 0.870 | 0.740 | 0.804 | 0.766 | 0.843
SSE [30] | 0.764 | 0.898 | 0.803 | 0.923 | 0.769 | 0.820 | 0.822 | 0.901
SiNE [31] | 0.781 | 0.895 | 0.782 | 0.876 | 0.785 | 0.850 | 0.831 | 0.902
SIDE [32] | 0.642 | 0.753 | 0.632 | 0.728 | 0.554 | 0.624 | 0.617 | 0.725
SGCN [15] | 0.801 | 0.915 | 0.804 | 0.908 | 0.786 | 0.859 | 0.849 | 0.920
SiGAT [21] | 0.775 | 0.894 | 0.796 | 0.903 | 0.789 | 0.857 | 0.853 | 0.917
SNEA [16] | 0.816 | 0.927 | 0.818 | 0.924 | 0.799 | 0.868 | 0.861 | 0.933
SIHG | 0.898 | 0.961 | 0.915 | 0.953 | 0.895 | 0.919 | 0.926 | 0.957

TABLE IV: The signed link prediction results of the proposed method and
compared baselines. ∗ indicates the results of re-implrementation.

Dataset | Method | AUC | F1 | macro-F1 | micro-F1
---|---|---|---|---|---
Bitcoin-Alpha |  SGCN∗ [15] | 0.8147 | 0.8996 | 0.6836 | 0.8310
SiGAT∗ [21] | 0.8393 | 0.9519 | 0.6721 | 0.9109
SNEA∗ [16] | 0.8293 | 0.9297 | 0.7430 | 0.8786
SIHG | 0.8981 | 0.9614 | 0.7115 | 0.9279
Bitcoin-OTC |  SGCN∗ [15] | 0.8087 | 0.9152 | 0.7617 | 0.8605
SiGAT∗ [21] | 0.8797 | 0.9423 | 0.7578 | 0.8983
SNEA∗ [16] | 0.8131 | 0.9174 | 0.7705 | 0.8646
SIHG | 0.9154 | 0.9528 | 0.7949 | 0.9165
Slashdot |  SGCN∗ [15] | 0.7827 | 0.8688 | 0.7512 | 0.8068
SNEA∗ [16] | 0.7918 | 0.8627 | 0.7634 | 0.8051
SIGNet [33] | - | - | - | 0.8320
SIHG | 0.8950 | 0.9189 | 0.7934 | 0.8696
Epinions |  SGCN∗ [15] | 0.8343 | 0.8001 | 0.6277 | 0.7075
SNEA∗ [16] | 0.8542 | 0.9304 | 0.8167 | 0.8873
SIGNet [33] | - | - | - | 0.9200
SIHG | 0.9262 | 0.9571 | 0.8261 | 0.9247

TABLE V: The study of node embedding size. ∗ indicates the results of re-
implrementation.

Dataset | Method | AUC | F1 | macro-F1 | micro-F1
---|---|---|---|---|---
Bitcoin-Alpha |  SGCN∗-32 | 0.8111 | 0.7778 | 0.5440 | 0.6638
|  SGCN∗-64 | 0.8147 | 0.8996 | 0.6836 | 0.8310
|  SGCN∗-128 | 0.8310 | 0.8972 | 0.6621 | 0.8257
| SIHG-32 | 0.8867 | 0.9587 | 0.6714 | 0.9226
| SIHG-64 | 0.8981 | 0.9614 | 0.7115 | 0.9279
| SIHG-128 | 0.9015 | 0.9599 | 0.6986 | 0.9251
Bitcoin-OTC |  SGCN∗-32 | 0.7942 | 0.7831 | 0.5984 | 0.6833
|  SGCN∗-64 | 0.8087 | 0.9152 | 0.7617 | 0.8605
|  SGCN∗-128 | 0.8751 | 0.9278 | 0.7792 | 0.8792
| SIHG-32 | 0.9041 | 0.9496 | 0.7744 | 0.9104
| SIHG-64 | 0.9154 | 0.9528 | 0.7949 | 0.9165
| SIHG-128 | 0.9200 | 0.9513 | 0.7959 | 0.9142

###  5.2 Ablation Study (RQ2)

To investigate the validity of the derived MI objective (MIM), the signed
attention mechanism (Signed Attention) and the incorporated Hyperboloid models
(Hyperbolic), we compare the seven variants of SIHG model on both Bitcoin-
Alpha and Bitcoin-OTC datasets, and summarize the comparison results in Table
VI. The graph depth $L$ is fixed to 3 and loss coefficients $\alpha$ and
$\gamma$ are empirically fixed. The first row corresponds to the simplest
baseline, which resembles SGCN yet it has separate transformations for
positive and negative neighbors’ features. By comparing the rest of variants
with one or two components removed, we observed degradation in the respective
performances of signed link prediction. It is noteworthy that removing the MI
objective will lead to a significant drop in prediction accuracy, which
verifies the importance of discovering correlations between the edge polarity
and the latent node embedding pairs.

TABLE VI: Ablation study of the proposed SIHG on Bitcoin-Alpha and Bitcoin-OTC
datasets.

|  |  | Bitcoin-Alpha | Bitcoin-OTC
---|---|---|---|---
MIM | Signed Attention | Hyperbolic | AUC | F1 | AUC | F1
- | - | - | 0.8149 | 0.9020 | 0.8268 | 0.9297
$\surd$ | - | - | 0.8867 | 0.9602 | 0.9071 | 0.9493
- | $\surd$ | - | 0.8532 | 0.9571 | 0.8925 | 0.9456
- | - | $\surd$ | 0.8756 | 0.9580 | 0.9004 | 0.9517
- | $\surd$ | $\surd$ | 0.8767 | 0.9588 | 0.9034 | 0.9510
$\surd$ | $\surd$ | - | 0.8880 | 0.9597 | 0.9115 | 0.9507
$\surd$ | - | $\surd$ | 0.8817 | 0.9575 | 0.9133 | 0.9527
$\surd$ | $\surd$ | $\surd$ | 0.8981 | 0.9614 | 0.9154 | 0.9528

TABLE VII: The link prediction performances of the proposed SIHG w.r.t.
various hyerbolic models on 3 datasets.

Dataset | Method | AUC | F1 | macro-F1 | micro-F1
---|---|---|---|---|---
Bitcoin-Alpha | Euclidean | 0.8880 | 0.9597 | 0.6934 | 0.9247
Poincaré | 0.8860 | 0.9600 | 0.6894 | 0.9251
Hyperboloid | 0.8981 | 0.9614 | 0.7115 | 0.9279
Bitcoin-OTC | Euclidean | 0.9115 | 0.9507 | 0.7822 | 0.9125
Poincaré | 0.9071 | 0.9510 | 0.7826 | 0.9130
Hyperboloid | 0.9154 | 0.9528 | 0.7949 | 0.9165

###  5.3 Parameter Sensitivity (RQ3)

We evaluate the sensitivity of the proposed SIHG method w.r.t the choices of
hyperbolic models, loss coefficients $\alpha$ and $\gamma$, and the depth $L$
of graph networks on the Bitcoin-Alpha and Bitcoin-OTC datasets.

Effect of Hyperbolic Model. First, we assessed the impact of the base model of
the SIHG, i.e., Euclidean, Poincaré, and Hyperboloid models w.r.t four
evaluation metrics. Notably, for Euclidean model, we do not apply the log and
exp maps. The results, reported in Table VII, demonstrate that the proposed
SIHG framework with the hyperboloid model achieve a relatively higher
performance compared to the Euclidean alternative, improving AUC scores from
$88.8\%$ to $89.8\%$. The performance improvement also illustrates the
numerical stability of the Hyperboloid over the Poincaré.

Effect of Loss Coefficients. To study the effect of the loss coefficients, we
conducted the experiments on the proposed SIHG with the varying values of
$\alpha$ and $\gamma$. The remaining coefficient $\beta$ is empirically set to
0.83. The search of the optimal loss coefficients is implemented with the
optuna [35] toolbox. The Figure 6 is plotted based on the results from 100
trails, with $\alpha$ and $\gamma$ ranging from 0 to 3. In addition, the 2D
contour maps of parameter sensitivity evaluated on two datasets are provided
in Figure 7. It can be observed that the AUC and F1 scores are going uphill
when $\gamma$ increases, which validates the importance of the derived mutual
information maximization strategy. Another finding is that, the AUC and F1
scores become quite stable when reaching sufficiently large loss coefficients.
This indicates that our SIHG framework is robust with respect to loss
coefficients.

TABLE VIII: Prediction performance of the signed edges with respect to various
graph depth on the two datasets.

Dataset | Method | AUC | F1 | macro-F1 | micro-F1
---|---|---|---|---|---
Bitcoin-Alpha | SIHG-1 | 0.8897 | 0.9597 | 0.6712 | 0.9244
SIHG-2 | 0.8862 | 0.9612 | 0.7079 | 0.9276
SIHG-3 | 0.8981 | 0.9614 | 0.7115 | 0.9279
SIHG-4 | 0.8664 | 0.9602 | 0.8978 | 0.9255
Bitcoin-OTC | SIHG-1 | 0.9113 | 0.9505 | 0.7779 | 0.9121
SIHG-2 | 0.9120 | 0.9505 | 0.7834 | 0.9123
SIHG-3 | 0.9154 | 0.9528 | 0.7949 | 0.9165
SIHG-4 | 0.9025 | 0.9515 | 0.7891 | 0.9142

Effect of Graph Depth. To investigate the impact of the number of stacked
graph layers, we examined the proposed SIHG framework with varying depth of
graph layers, i.e., $L\in\\{1,2,3,4\\}$. As shown in Table VIII, the
performance of the proposed SIHG with deeper graph networks generally
increases until $L$ reaches 3. Due to the sparsity of signed networks and the
intrinsic over-smoothing risk of GNNs, the SIHG-4 achieves a relatively lower
performance compared to SIHG-3.

Effect of Embedding Dimensionality. Another fundamental hyperparameter is the
size of the resulting embeddings. We studied the performance of SIHG and the
compared baseline SGCN [15] with respect to the dimensionality
$d\in\\{32,64,128\\}$ on the Bitcoin-Alpha and Bitcoin-OTC datasets. The
results, shown in Table V demonstrates the high-dimensional vectors are
capable of preserving more information of original network and user
interactions, yielding a higher performance for both methods. It is also
observed that the proposed method (i.e., SIHG∗-32) can learn compact node
representations which performance surpasses the one of the longer vector
learned by SGCN (i.e., SGCN∗-128) for signed link prediction.

(a)

(b)

(c)

(d)

Figure 5: The visualization of the learned embeddings by graph-based baselines
and the proposed SIHG with Hyperbolid model on the Bitcoin-Alpha dataset.

(a)

(b)

Figure 6: The impact of loss coefficients $\alpha$ and $\gamma$ on signed link
prediction. The best trial is marked with a red point.

(a)

(b)

Figure 7: The contour plot of parameter study of loss coefficients $\alpha$
and $\gamma$.

(a)

(b)

Figure 8: The visualization of the signed attention map extracted from the
proposed SIHG. Best viewed in color.

###  5.4 Embedding Visualization (RQ4)

To evaluate the importance of high-order topology and hierarchy preservation,
we conduct experiments on the test set of the Bitcoin-Alpha dataset, and
visualize the node-pair embeddings with PCA in Figure 5. The features of the
compared baselines, i.e., SGCN, SiGAT, SNEA are extracted before passing them
to the classifier. The embeddings are scattered as circles in the projected 3D
subspace, with different colors indicating the edge polarities i.e., red
represents friendship and blue represents antagonism. In contrast to existing
graph models, the proposed SIHG are more powerful to preserve tree structure,
where nodes close to the center are generally higher in the hierarchy of the
tree.

###  5.5 Interpretability for Social Theories (RQ5)

In order to study the interpretability of two fundamental social theories, we
run experiments on the Bitcoin-Alpha dataset. We extract the signed attention
maps of $w^{-(l)}_{ik}$ and $w^{-(l)}_{ij}$ in the positive and negative
aggregation branches at the second graph layer ($l=2$), respectively. For
simplicity, we only visualize the connections starting from the node $6$ and
$10$. The attention maps are plotted in Figure 8 with D3.js. Recalling the
aggregation paths in Figure 3, we can clearly discriminate the social rules by
comparing the sign of attention score for each edge. For instance, the
negative edge attention score (e.g., $6\rightarrow 3713$) in $w_{ij}^{-(2)}$
stands for structural balance theory, and the positive one (e.g.,
$6\rightarrow 42$) for status theory. The signed attention learned is crucial
to provide interpretation of the sociological mechanisms behind the given
signed networks.

##  6 Related Work

###  6.1 Signed Network Embedding

Network embedding approaches [8, 9, 10, 11, 12, 13, 14] aim to represent each
node as a low-dimensional vector, by considering the node’s neighborhood and
feature information. Similar nodes are expected to be projected close to each
other in the subspace, which facilitate the downstream tasks such as node
classification and link prediction. Early methods such as DeepWalk [36] and
Node2vec [37] have been proposed to capture node proximity with the random
walk strategy. A newly emerging stream of work attempts to compute embeddings
of large graph-structured data not in Euclidean but in hyperbolic space, which
refers to the space with constant negative curvature. Nickel et al. [38]
explored the Poincare ball model for embedding learning, which is based on
Riemannian optimization. However, prior work only consider learning embeddings
for unsigned networks that only consist of positive links, thus failing to
handle signed networks that further consider negative links with more valuable
information [20]. The root of modeling signed networks lies in two important
sociological theories [19], i.e., balance theory and status theory. Motivated
by social balance theory, Chiang et al. [39] extended weighted kernel k-means
clustering to the signed network setting, by considering a signed variant of
Laplacian matrix, which can be used as the basis for graph kernels. Similarly,
Zheng et al. [30] applied random walk normalized to analyze signed graphs,
which can be embedded in a lower-dimensional space that reveals the global
similarity between nodes. Hsieh et al. [40] reformulated the sign inference
problem as a low-rank matrix completion problem and proved that the missing
links can be recovered under certain conditions.

Different from the above-mentioned works that learn node representations by
spectral analysis or matrix factorization, another line of work jointly
aggregates and propagates information in neural networks. SNE [41] optimizes a
Skip-Gram like objective function by the maximum likelihood estimation and
incorporates two signed vectors to represent the positive or negative edges
with a log-bilinear model. Guided by the extended balance theory, SiNE [31]
introduces a new objective function for signed network embedding, adding
virtue nodes to enhance the training process. To improve algorithmic
efficiency, SIDE [32] is built upon a truncated random walk, which aims to
represents proximity in signed directed networks as a compact low-dimensional
vector. To maintain structural balance in higher-order neighborhoods, SIGNet
[33] leverages a new targeted node sampling strategy for random walks in
directed signed networks. Of late, SGCN [15] is proposed, which generalizes
GCN [42] to signed networks and applies a mean pooling strategy to aggregate
messages from neighboring nodes according to balance theory. With the advent
in the self-attention mechanism, SiGAT [21] utilizes the graph attention
networks (GAT) to embed different motifs in directed signed networks.
Subsequently, SDGNN [43] extends SiGAT with two additional loss, i.e., margin
loss for edge direction and binary cross entropy loss for triangle relation
preserving. Similarly, SNEA [16] proposes a graph attention layer and provides
a more universal way to aggregate information through both positive and
negative links based on balance theory. To cope with the over-smoothing
problem, SGDNet [44] derives a signed random walk diffusion method, which
aggregates node features on signed edges and effectively exploits information
from multi-hop neighbors. Nonetheless, the existing approaches biasedly rely
on the balance and/or status theory for edge sign prediction, which may be
easily violated in practice. In our proposed SIHG framework, the principle of
mutual information maximization guides the model to infer edge polarities from
the informative positive and negative node neighbors, where the aggregation
paths are learned by the signed attention module and two social theories are
thus naturally unified.

###  6.2 Mutual Information Estimation

With the strong growth of data [45, 46, 47, 48], Mutual Information (MI)
estimation, quantifying the amount of shared information between a pair of
random variables, has been playing a pivotal role in representation learning
[24] and wide applications [49]. MI maximization can be used to extract
representations that are highly relevant to the target task, or controlling
the amount of information between the learned representations and the original
data [50, 51, 52]. While effective, few of the prior mutual information
estimators can generalize to deep neural networks due to the high
dimensionality and sample size. In order to overcome the intractability of MI
in the presence of high-dimensional and continuous data, Mutual Information
Neural Estimation (MINE) [25] makes the estimation of MI on deep neural
networks feasible via training a statistics network to distinguish samples
coming from the joint distribution and the product of marginals of two random
variables. Different from MINE that employs a lower-bound to the MI based on
the Donsker-Varadhan representation [26] of the KL-divergence, the Jensen-
Shannon MI estimator (JSD) [53] follows the formulation of f-GAN KL-
divergence. Our proposed SIHG shares the same spirit with the mutual
information estimators, which aims to mine the informative representations
oriented by the task. But instead of using for unsupervised learning, we, for
the first time, adapt the mutual information to guide the aggregation in the
deep graph model and validate its effectiveness on a practical signed link
prediction task.

##  7 Conclusion

In this work, we propose a deep SIHG framework for the signed link prediction
in the presence of large-scale signed social networks. Different from the
existing approaches which rely on balance or status theory, we automatically
select the aggregation path and reconcile the two theories by maximizing the
mutual information between the learned node embeddings and the edge
polarities. Experiments evidence the effectiveness of our proposed approach
over the state-of-the-art methods, especially improving the AUC scores by up
to 13.0$\%$.

## Acknowledgments

This work is partially supported by ARC FT130101530, NSFC No. 61628206 and
Google PhD Fellowship. Thanks to Kevin Swersky for valuable discussions on
this topic and to the reviewers for their helpful suggestions.

## References

  * [1] R. Márquez and R. Weber, “Overlapping community detection in static and dynamic social networks,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2019, pp. 822–823.
  * [2] M. Sachan, A. Dubey, S. Srivastava, E. P. Xing, and E. H. Hovy, “Spatial compactness meets topical consistency: Jointly modeling links and content for community detection,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2014, pp. 503–512.
  * [3] S. P. Bhatt, S. Padhee, A. P. Sheth, K. Chen, V. L. Shalin, D. Doran, and B. S. Minnery, “Knowledge graph enhanced community detection and characterization,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2019, pp. 51–59.
  * [4] Z. Jiang, H. Liu, B. Fu, Z. Wu, and T. Zhang, “Recommendation in heterogeneous information networks based on generalized random walk model and bayesian personalized ranking,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2018, pp. 288–296.
  * [5] P. P. Analytis, D. Barkoczi, P. Lorenz-Spreen, and S. Herzog, “The structure of social influence in recommender networks,” in _Proc. International Conference on World Wide Web, WWW_ , 2020, pp. 2655–2661.
  * [6] A. Breuer, R. Eilat, and U. Weinsberg, “Friend or faux: Graph-based early detection of fake accounts on social networks,” in _WWW ’20: The Web Conference 2020_ , 2020, pp. 1287–1297.
  * [7] B. C. Molokwu, “Event prediction in complex social graphs using one-dimensional convolutional neural network,” in _Proc. International Joint Conference on Artificial Intelligence, IJCAI_ , 2019, pp. 6450–6451.
  * [8] H. Gao, J. Pei, and H. Huang, “Progan: Network embedding via proximity generative adversarial network,” in _Proc. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD_, 2019, pp. 1308–1316.
  * [9] L. Gong, L. Lin, W. Song, and H. Wang, “JNET: learning user representations via joint network embedding and topic embedding,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2020, pp. 205–213.
  * [10] W. Lin, F. He, F. Zhang, X. Cheng, and H. Cai, “Initialization for network embedding: A graph partition approach,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2020, pp. 367–374.
  * [11] X. Huang, Q. Song, J. Li, and X. Hu, “Exploring expert cognition for attributed network embedding,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2018, pp. 270–278.
  * [12] Y. Ma, Z. Ren, Z. Jiang, J. Tang, and D. Yin, “Multi-dimensional network embedding with hierarchical structure,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2018, pp. 387–395.
  * [13] J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and J. Tang, “Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2018, pp. 459–467.
  * [14] H. Wang, F. Zhang, M. Hou, X. Xie, M. Guo, and Q. Liu, “SHINE: signed heterogeneous information network embedding for sentiment link prediction,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2018, pp. 592–600.
  * [15] T. Derr, Y. Ma, and J. Tang, “Signed graph convolutional networks,” in _Proc. IEEE International Conference on Data Mining, ICDM_ , 2018, pp. 929–934.
  * [16] Y. Li, Y. Tian, J. Zhang, and Y. Chang, “Learning signed network embedding via graph attention,” in _Proc. Conference on Artificial Intelligence, AAAI_ , 2020, pp. 4772–4779.
  * [17] D. Cartwright and F. Harary, “Structural balance: a generalization of heider’s theory.” _Psychological review_ , vol. 63, no. 5, p. 277, 1956.
  * [18] R. V. Guha, R. Kumar, P. Raghavan, and A. Tomkins, “Propagation of trust and distrust,” in _Proc. International Conference on World Wide Web, WWW_ , 2004, pp. 403–412.
  * [19] J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg, “Signed networks in social media,” in _Proc. International Conference on Human Factors in Computing Systems, CHI_ , 2010, pp. 1361–1370.
  * [20] ——, “Predicting positive and negative links in online social networks,” in _Proc. International Conference on World Wide Web, WWW_ , 2010, pp. 641–650.
  * [21] J. Huang, H. Shen, L. Hou, and X. Cheng, “Signed graph attention networks,” in _Proc. International Conference on Artificial Neural Networks, ICANN_ , 2019, pp. 566–577.
  * [22] I. Chami, Z. Ying, C. Ré, and J. Leskovec, “Hyperbolic graph convolutional neural networks,” in _Proc. Advances in Neural Information Processing Systems, NeurIPS_ , 2019, pp. 4869–4880.
  * [23] Q. Liu, M. Nickel, and D. Kiela, “Hyperbolic graph neural networks,” in _Proc. Advances in Neural Information Processing Systems, NeurIPS_ , 2019, pp. 8228–8239.
  * [24] R. Linsker, “Self-organization in a perceptual network,” _IEEE Computer_ , vol. 21, no. 3, pp. 105–117, 1988.
  * [25] M. I. Belghazi, A. Baratin, S. Rajeswar, S. Ozair, Y. Bengio, R. D. Hjelm, and A. C. Courville, “Mutual information neural estimation,” in _Proc. International Conference on Machine Learning, ICML_ , 2018, pp. 530–539.
  * [26] M. D. Donsker and S. R. S. Varadhan, “Asymptotic evaluation of certain markov process expectations for large time. iv,” _Communications on Pure and Applied Mathematics_ , vol. 36, no. 2, pp. 183–212, 1983.
  * [27] S. Kumar, F. Spezzano, V. S. Subrahmanian, and C. Faloutsos, “Edge weight prediction in weighted signed networks,” in _Proc. IEEE International Conference on Data Mining, ICDM_ , 2016, pp. 221–230.
  * [28] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. S. Subrahmanian, “REV2: fraudulent user prediction in rating platforms,” in _Proc. ACM International Conference on Web Search and Data Mining, WSDM_ , 2018, pp. 333–341.
  * [29] C. Eckart and G. Young, “The approximation of one matrix by another of lower rank,” _Psychometrika_ , vol. 1, no. 3, pp. 211–218, 1936.
  * [30] Q. Zheng and D. B. Skillicorn, “Spectral embedding of signed networks,” in _Proc. SIAM International Conference on Data Mining, SDM_ , 2015, pp. 55–63.
  * [31] M. R. Islam, B. A. Prakash, and N. Ramakrishnan, “Signet: Scalable embeddings for signed networks,” in _Proc. Advances in Knowledge Discovery and Data Mining - Pacific-Asia Conference, PAKDD_ , 2018, pp. 157–169.
  * [32] J. Kim, H. Park, J. Lee, and U. Kang, “SIDE: representation learning in signed directed networks,” in _Proc. International Conference on World Wide Web, WWW_ , 2018, pp. 509–518.
  * [33] M. R. Islam, B. A. Prakash, and N. Ramakrishnan, “Signet: Scalable embeddings for signed networks,” in _Proc. Advances in Knowledge Discovery and Data Mining - Pacific-Asia Conference, PAKDD_ , 2018, pp. 157–169.
  * [34] A. Paszke, S. Gross, F. Massa _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” in _Proc. Advances in Neural Information Processing Systems, NeurIPS_ , 2019, pp. 8024–8035.
  * [35] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama, “Optuna: A next-generation hyperparameter optimization framework,” in _Proc. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD_, 2019, pp. 2623–2631.
  * [36] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proc. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD_, 2014, pp. 701–710.
  * [37] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proc. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD_, 2016, pp. 855–864.
  * [38] M. Nickel and D. Kiela, “Poincaré embeddings for learning hierarchical representations,” in _Proc. Advances in Neural Information Processing Systems, NeurIPS_ , 2017, pp. 6338–6347.
  * [39] K. Chiang, J. J. Whang, and I. S. Dhillon, “Scalable clustering of signed networks using balance normalized cut,” in _Proc. ACM International Conference on Information and Knowledge Management, CIKM_ , 2012, pp. 615–624.
  * [40] C. Hsieh, K. Chiang, and I. S. Dhillon, “Low rank modeling of signed networks,” in _Proc. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD_, 2012, pp. 507–515.
  * [41] S. Yuan, X. Wu, and Y. Xiang, “SNE: signed network embedding,” in _Proc. Advances in Knowledge Discovery and Data Mining - Pacific-Asia Conference, PAKDD_ , 2017, pp. 183–195.
  * [42] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _Proc. International Conference on Learning Representations, ICLR_ , 2017.
  * [43] J. Huang, H. Shen, L. Hou, and X. Cheng, “SDGNN: learning node representation for signed directed networks,” _CoRR_ , vol. abs/2101.02390, 2021.
  * [44] J. Jung, J. Yoo, and U. Kang, “Signed graph diffusion network,” _CoRR_ , vol. abs/2012.14191, 2020.
  * [45] Y. Zhang, F. Liu, Z. Fang, B. Yuan, G. Zhang, and J. Lu, “Clarinet: A one-step approach towards budget-friendly unsupervised domain adaptation,” in _Proc. International Joint Conference on Artificial Intelligence (IJCAI)_ , 2020, pp. 2526–2532.
  * [46] Z. Fang, J. Lu, F. Liu, J. Xuan, and G. Zhang, “Open set domain adaptation: Theoretical bound and algorithm,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–14, 2020.
  * [47] L. Zhong, Z. Fang, F. Liu, J. Lu, B. Yuan, and G. Zhang, “How does the combined risk affect the performance of unsupervised domain adaptation approaches?” _AAAI_ , 2021.
  * [48] Y. Luo, Z. Wang, Z. Huang, Y. Yang, and C. Zhao, “Coarse-to-fine annotation enrichment for semantic segmentation learning,” in _Proc. ACM International Conference on Information and Knowledge Management (CIKM)_ , A. Cuzzocrea, J. Allan, N. W. Paton, D. Srivastava, R. Agrawal, A. Z. Broder, M. J. Zaki, K. S. Candan, A. Labrinidis, A. Schuster, and H. Wang, Eds. ACM, 2018, pp. 237–246.
  * [49] Y. Liu, Y. Yeh, T. Fu, S. Wang, W. Chiu, and Y. F. Wang, “Detach and adapt: Learning cross-domain disentangled deep representation,” in _Proc. IEEE Conference on Computer Vision and Pattern Recognition, CVPR_ , 2018, pp. 8867–8876.
  * [50] A. A. Alemi, I. Fischer, J. V. Dillon, and K. Murphy, “Deep variational information bottleneck,” in _Proc. International Conference on Learning Representations, ICLR_ , 2017.
  * [51] N. Tishby, F. C. N. Pereira, and W. Bialek, “The information bottleneck method,” _CoRR_ , vol. physics/0004057, 2000.
  * [52] A. A. Alemi, I. Fischer, and J. V. Dillon, “Uncertainty in the variational information bottleneck,” _CoRR_ , vol. abs/1807.00906, 2018.
  * [53] R. D. Hjelm, A. Fedorov, S. Lavoie-Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengio, “Learning deep representations by mutual information estimation and maximization,” in _Proc. International Conference on Learning Representations, ICLR_ , 2019.

|  Yadan Luo received the B.S. degree in computer science from the University
of Electronic Engineering and Technology of China in 2017. She is currently
working toward the Ph.D. degree at the University of Queensland. Her research
interests include multimedia retrieval, machine learning and computer vision.
---|---
|  Zi Huang is an ARC Future Fellow in School of ITEE, The University of
Queensland. She received her BSc degree from Department of Computer Science,
Tsinghua University, China, and her PhD in Computer Science from School of
ITEE, The University of Queensland. Dr. Huang’s research interests mainly
include multimedia indexing and search, social data analysis and knowledge
discovery.
---|---
|  Hongxu Chen Dr. Hongxu Chen is now working as a Postdoctoral Research
Fellow in Network Science Lab at University of Technology Sydney (UTS). Hongxu
Chen received his PhD degree in 2020 from The University of Queensland (UQ),
Australia. His research interests include data mining, network science,
network/graph embedding, recommender systems as well as social networks
modelling and analytics.
---|---
|  Yang Yang received the bachelor’s degree from Jilin University in 2006, the
master’s degree from Peking University in 2009, and the Ph.D. degree from The
University of Queensland, Australia, in 2012, under the supervision of Prof.
H. T. Shen and Prof. X. Zhou. He was a Research Fellow under the supervision
of Prof. T.-S. Chua with the National University of Singapore from 2012 to
2014. He is currently with the University of Electronic Science and Technology
of China.
---|---
|  Hongzhi Yin received the PhD degree in computer science from Peking
University, in 2014. He is a senior lecturer with the University of
Queensland. He received the Australia Research Council Discovery Early-Career
Researcher Award, in 2015. His research interests include recommendation
system, user profiling, topic models, deep learning, social media mining, and
location-based services.
---|---
|  Mahsa Baktashmotlagh received the bachelor’s degree in software engineering
from the Sharif University of Technology and the M.Sc. degree in IT
engineering from Polytechnic University in 2007. She also received the PhD
degree in computer science from the University of Queensland in 2014. She is
now a lecturer in the University of Queensland.
---|---