# Scaling Frustration Index and Corresponding Balanced State Discovery for
Real Signed Graphs

Muhieddine Shebaro and Jelena Tešić

###### Abstract

Structural balance modeling for signed graph networks presents how to model
the sources of conflicts. The state-of-the-art has focused on computing the
frustration index of a signed graph as a critical step toward solving problems
in social and sensor networks and for scientific modeling. However, the
proposed approaches do not scale to modern large, sparse signed networks.
Also, they do not address that there is more than one way in some networks to
reach a consensus with the minimum number of edge-sign switches needed. We
propose an efficient balanced state discovery algorithm and a network
frustration computation that will discover the nearest balanced state for the
_any_ size of the graph network and compute the frustration of the network.
The speedup of the proposed method is around 300 times faster than the state-
of-the-art for signed graphs with hundreds of thousands of edges. The
technique successfully scales to find the balanced states and frustration of
the networks with millions of nodes and edges in real time where state-of-the-
art fails.

frustration index, balanced states, signed graphs, scaling, in-memory

##  1 Introduction

Unstructured data requires a rich graph representation; the signed networks
model complex relationships through the interdependence between entities
complementary to instance features. When opposing edges are included in a
network, we can study social dynamics and stability concerning friendship and
enmity in more depth [5, 32], or expand to new application domains, such as
brain behavior [41]. However, signed graph benchmarks are currently too small
and too similar in topology to actual data, hindering progress in signed graph
analysis [33, 30]. Signed graph extensions have been demonstrated for narrow-
band tasks in finance [7], polypharmacy [35], bioinformatics [34], and sensor
data analysis [12, 36]. To date, signed graph benchmark evaluations of the
algorithms are small in size, do not have the same topology as signed graphs
derived from accurate data, and the algorithms make assumptions that are not
applicable in real signed networks [14, 45].

Figure 1: (a) Unsigned graph $G$ with 4 vertices and 5 edges; (b) Eight
possible edge sign combinations for $G$ that are balanced.

The work focuses on scaling the computing of the frustration index and finding
the associated balanced state for large signed networks. Balance theory
represents a theory of changes in attitudes [1]: people’s attitudes evolve in
networks so that friends of a friend will likely become friends, and so will
enemies of an enemy [1]. Heider established the foundation for social balance
theory [25], and Harary established the mathematical foundation for signed
graphs and introduced the k-way balance[11, 23]. Balance theory concepts have
been used to predict edge sentiment, to recommend content and products, or to
identify unusual trends [16, 20, 29, 3]. A network is considered balanced only
if every fundamental cycle contains an even number of opposing edges. One
measure of the network is its distance from its balanced state. A signed
network’s _frustration index_ is the smallest number of edge-sign switches
needed to reach a balanced state. The frustration index is one measure of
network property in many scientific disciplines, that is, in chemistry [44],
biology [28], brain studies [39], physical chemistry [48] and control [19].
The calculation of the frustration index can also be reduced to the maximum
cut of the graph in a particular case of all opposing edges, which proved to
be NP-hard [27]. State-of-the-art methods address the computation of the
frustration index for signed graphs with up to 100,000 vertices [9], and the
approach does not scale to modern large-scale sparse networks. The signed
networks can have multiple nearest balanced states, e.g., multiple paths to a
balanced state with the corresponding minimal or near-minimal number of edge
switches to reach more than one closest balanced state [38]. The contributions
are:
(1) Scaling discovery of the _frustration index_ for any real-world signed
network of any size or density based on efficiently finding a fundamental
cycle basis.
(2) Extending the frustration cloud from a set in [38] to a _(key, value)_
tuple collection $\mathcal{F}_{\Sigma}$ =
$\mathcal{B}$:($\mathcal{C},\mathcal{S}$)/ The nearest balanced states with
their associated frequency and edge switches will be stored in the memory-
bound frustrated cloud as a tuple.
(3) Benchmark comparison of seven spanning tree sampling methods including a
breakthrough study of frustration index computation and timing for networks
with tens of millions of nodes.
This paper introduces an algorithm to discover the nearest balanced state for
a signed graph of _any_ size under real-time processing constraints. The
outcome is the edges that need to change signs for the network to achieve a
balanced state. The number of edges in the output set captures the frustration
of the network. The connection between the fundamental cycle basis and the
frustration index is that each unbalanced cycle will be balanced by switching
the sign of the edges. The counter is increased by one for each switch. The
more unbalanced cycles a signed network has, the greater the frustration index
of this network. _graphB++_ initially obtains a spanning tree and performs
these sign switches on _non-tree_ edges.

Figure 2: (a) Signed graph $\Sigma$; (b) Near-balanced states of $\Sigma$,
$\Sigma^{\prime}_{i}:i\in[1,5]$ where blue lines illustrate the spanning tree
and yellow signs note the edge sign change in Algorithm 1. If a fundamental
cycle contains an odd number of negative edges, sign switching occurs on _non-
tree_ edges (non-blue edges) to balance the signed network.

The paper is organized as follows: in Section 2, we summarize related work in
the field; in Section 3, we present preliminary findings; in Section 5, we
introduce a novel algorithm for computing the frustration index and its
scalable version; in Section 6, we analyze different sampling approaches of
the spanning tree and propose two new methods; in Section 8, we conduct
experiments to evaluate the efficiency of the proposed algorithm on ten
different signed graph benchmarks and apply and measure the findings on signed
graphs derived from the 26 Amazon ratings and reviews datasets [24], and in
Section 8 we summarize our findings.

##  2 Related Work and Motivation

In this section, we _motivate_ and discuss the applications and _significance_
of computing the frustration index in various fields. There is currently no
open-source code for calculating the frustration index except for the Binary
Linear Programming (BLP) model baseline [7], so we use BLP as a baseline for
comparison.
Frustration Applications: In chemistry, the stability of fullerenes is related
to the frustration index [44]. The frustration index has been used to measure
how an incoherent system responds to perturbations in large-scale signed
biological networks [28]. The frustration of the network has been determining
the strength of agent commitment to make a decision and win the disorder in
adversarial multi-agent networks [19]. The frustration in neuroplasticity
assesses the development of brain networks, as studies have shown that a
person’s cognitive performance and the frustration of the brain network have a
negative correlation [39]. In physical chemistry, the protein-protein
interaction can be predicted using the frustration index of the protein-signed
network [48]. Saberi et al. investigated the pattern for the formation of
frustrating connections in different brain regions during multiple life
stages[40].
Computing the Frustration Index: Researchers have focused on calculating the
exact frustration index, not finding the balanced state of the network.
Calculating the frustration index is an NP-hard problem equivalent to
calculating the ground state of the spin glass model on unstructured graphs
[43]. The frustration index for small fullerene graphs can be calculated in
polynomial time[17], and the finding has been extended to estimate the genetic
algorithm of the frustration index in [44]. Bansal et al. introduced the
correlation clustering problem, which is a problem in computing the minimum
number of frustrated edges for several subsets [10]. Aref et al. provided an
exact algorithm to calculate the partial balance and frustration index with
O($(2^{b})|E|^{2}$) complexity where $b$ is a fixed parameter, and $|E|$ is
the number of edges [7]. Researchers have focused on approximating the
frustration computation. Aref et. al introduced the approximate algorithm of
complexity O($\sqrt{log(|V|)}$), $|V|$ is the number of vertices that
theoretically converged to the exact frustration index when tested on networks
up to 2,000 edges [8]. Recent improvements in the algorithm include binary
programming models and the use of multiple powerful mathematical solvers by
Guribo [22], and the algorithm can handle up to $|E|=100,000$ edges and
compute the frustration index of the network in 10 hours [9]. For millions of
vertices in Amazon’s bi-partite ratings and reviews network, these approaches
are still too complex. This is because integer and binary programming models
are known to be slow, computationally expensive, and have a huge search space
for large problems. They might output an approximate solution to the problem,
but that doesn’t necessarily mean they are better than a heuristic approach
that is much faster and scalable. For example, we can see the use of a
parallel genetic algorithm for solving large integer programming models [18]
because the authors postulate that as these models grow, the efficiency
decreases greatly, making it impossible to have any output.

##  3 Preliminary Data

_Graph_ $G=(V,E)$ is a set of vertices $V$ connected by the set of edges $E$.
The number of vertices in the graph $G$ is $|V|$, and the number of edges is
$|E|$. _Path_ is a sequence of distinct edges that connect a sequence of
distinct vertices. _Cycle_ is a path that begins and ends at the same vertex.
_Connected graph_ is a graph in which a path joins two vertices. _Subgraph_ is
a graph whose all edges and vertices are contained in a larger graph, for
example, path and cycle. _Signed graph_ $\Sigma$ is a tuple of a graph
$G=(V,E)$ and an edge signing function $\sigma:E\rightarrow\\{+1,-1\\}$. The
edge can be positive $+$ or negative $-$, $e\in[e^{+},e^{-}]$, $E^{+}$, and
$E^{-}$ are sets of positive and negative edges of $G$. _Sign_ of a subgraph
is _product_ of the edges signs. _Balanced signed graph_ is a signed graph
where every cycle is positive. _Harary bipartition_ separates the vertices of
the balanced graph into two sets such that the vertices of both sets
internally agree with each other but disagree with the vertices of the other
set [11]. _Near-balanced_ graph $\Sigma^{\prime}$ is a balanced graph that
requires a minimum number of edge sign switches to produce a balanced graph
from the signed graph $\Sigma$. _Frustration cloud_ $\mathcal{F}_{\Sigma}$ is
a set of all signed near-balanced graphs of $\Sigma$:
$\mathcal{F}_{\Sigma}=\left\\{\Sigma^{\prime}_{i}|i\in[1,N]\land
Fr(\Sigma^{\prime}_{i})=0\right\\}$. The unsigned graph $G$ with four vertices
and five edges is illustrated in Figure 1(a), and all possible combinations of
edge signs that result in balanced signed graphs are illustrated in Figure
1(b). The frustration cloud $\mathcal{F}_{\Sigma}$ for a signed graph $\Sigma$
is formed using the tree balance algorithm outlined in Alg. 1 and explained in
detail in [38]. Only five of these balanced graphs are nearest balanced states
for a specifically signed graph $\Sigma$ illustrated in Fig. 2(a), as
illustrated by the frustration cloud
$\mathcal{F}_{\Sigma}=\left\\{\Sigma^{\prime}_{i}|i\in[1,5]\right\\}$ in Fig.
2(b).

Data: Signed graph $\Sigma$

Data: Spanning tree $T$ of $\Sigma$

Result: Balanced graph $\Sigma^{\prime}_{T}$

1 forall  _edges $e$, $e\in\Sigma\setminus T$_ do

2 if  _fundamental cycle $T\cup e$ is negative_ then

3 switch edge sign in $\Sigma^{\prime}_{T}$: $e^{-}\rightarrow
e^{+};e^{+}\rightarrow e^{-}$ ;

4

5

6 end forall

Algorithm 1 Tree-Based Signed Graph Balancing

Balance only affects the signs of the edges as it negates some of them to
reach a consensus state (line 3 in Alg.1). The minimum number of edge sign
switches is the frustration cloud. To discover all the states of a signed
graph, Alg. 1 should be run with _all_ spanning trees $T$ of $\Sigma$. The
cloud $\mathcal{F}_{\Sigma}$ encompasses all the individual closest balanced
states that result from this algorithm. The exact number for any graph $G$ can
be calculated in polynomial time as the determinant of a matrix derived from
the chart, using Kirchhoff’s matrix-tree theorem [46]. For a small social
network such as the Highland Tribes [37] with $16$ vertices and $29$ positive
and $29$ opposing edges, the number of spanning trees is $402,506,278,163$
[38]. The _graphB_ algorithm was introduced in [38] as a scaled adjustment of
the Alg. 1 for loop in line 1: instead of all trees, the algorithm loops over
$k$ spanning trees discovered using the method $M$ (Alg. 2 line 1). Next, the
_graphB+_ algorithm scaled the computation of fundamental cycles for the
spanning tree $T$ in Alg. 1. If $T$ is a spanning tree of $\Sigma$ and $e$ is
an edge of $\Sigma$ that does not belong to $T$, then _fundamental Cycle_
$\emph{C}_{e}$, defined by $e$, is the cycle consisting of $e$ together with
the straightforward Path in $T$ connecting the endpoints of $e$. If $|V|,v\in
V$ denotes the number of edges and $|E|,e\in E$ the number of vertices in
$\Sigma$, there are precise $|E|-(|V|-1)$ fundamental cycles, one for each
edge that does not belong to $T$. Each $\emph{C}_{e}$ is linearly independent
of the remaining cycles because it includes an edge $e$ not present in any
other fundamental process. The _graphB+_ algorithm was introduced in [2] as an
efficient way to balance the signed graph given the spanning tree $T$. The
main benefits of _graphB+_ are that labels can be computed with linear time
complexity, only require a linear amount of memory, and that the running time
for balancing a cycle is linear in the length of the cycle times the vertex
degrees but _independent_ of the size of the graph. The algorithm speeds up
the balancing to more than 14 million fundamental cycles identified,
traversed, and balanced. This paper proposes the _graphB++_ algorithm to scale
the frustration cloud computation (with an extension to its definition) and
approximate the frustration index for large real signed graphs.

##  4 Definition of the Objective

We extend _graphB+_ to approximate the frustration index $Fr_{\Sigma}$ for a
given signed network using a particular tree-sampling technique (we will see
later which technique is ideal for _graphB++_ for minimizing this value in
Section 8.3):

$Fr_{\Sigma}=min_{i}(\mathcal{S}(i));$
The $S$ is a container that stores the number of edge sign switches for a
given $i$th nearest balanced state. For every state in each iteration, the
number of edge sign switches is counted by comparing the originally signed
network with the produced balanced state. It is assigned to $\mathcal{S}(i))$.
We aim to find a balanced state with a minimum number of switches and return
it to the frustration index using the extended version _graphB++_. We also
construct the memory-bound frustration cloud $\mathcal{F}_{\Sigma}$ and extend
its definition to the following:

$\mathcal{F}_{\Sigma}=(\mathcal{B}(i),\mathcal{C}(i),\mathcal{S}(i)),i\leq\mathcal{F}_{max}\;$
The $\mathcal{B}(i)$ is a container for storing the $i$th balanced state,
$\mathcal{C}(i)$ is a container for saving the number of $i$th balanced state
produced, and $\mathcal{S}(i)$ is a container that keeps the number of edge
sign switches for a given $i$th nearest balanced state. $\mathcal{F}_{max}$
represents the number of balanced states where a memory limit is reached
during the frustration cloud creation.

##  5 Scalable Computation

We propose _graphB++_ , an efficient algorithm that computes balanced states
and frustration index. The _graphB++_ algorithm builds on the _graphB_ and
_graphB+_ baseline. First, the algorithm integrates different tree-sampling
approaches, as outlined in Alg. 2) for frustration index computation. Next,
the _graphB++_ algorithm scales the calculation of the frustration index and
associated optimal balanced state by iteratively keeping in memory only the
subset of nearest balanced states with the smallest number of edge negations,
as outlined in Alg. 3. The result of _graphB++_ is that the frustration index
and the closest balanced associated state can be computed in minutes for the
_any_ large signed graph.

Data: Signed graph $\Sigma$ and spanning trees sampling method $M$

Result: frustration index Fr($\Sigma$)=$min_{i}$($\mathcal{S}$) and
frustration cloud $\mathcal{F}_{\Sigma}$ =
$\mathcal{B}$:($\mathcal{C},\mathcal{S}$).

1 Generate set $\mathcal{T}_{M^{k}}$ of $k$ spanning trees of $\Sigma$ using
$M$;

2 Empty $\mathcal{F}_{\Sigma}$ ;

3 foreach  _spanning trees $T$, $T\in\mathcal{T}_{k}$_ do

4 Find nearest balanced state $\Sigma^{\prime}_{T}$ using Alg. 1;

5 s = edge signs difference count from $\Sigma$ to $\Sigma^{\prime}_{T}$;

6 Transform $\Sigma^{\prime}_{T}$ balanced state to string B ;

7 if  _$B\notin\mathcal{B}$ _ then

8 add key B to $\mathcal{B}$;

9 S($B$) = s;

10 C($B$) = 1 ;

11

12 else

13 C(B)++ ;

14

15 end foreach

Algorithm 2 Graph Balancing and Frustration Index

We extend the definition of frustration cloud $\mathcal{F}_{\Sigma}$ (Sect. 3)
from a set to a _(key,value)_ tuple collection $\mathcal{F}_{\Sigma}$ =
$\mathcal{B}$:($\mathcal{C},\mathcal{S}$). The key is the unique balanced
state $\mathcal{B}(i)$, and the value is the count of balanced states
occurring in iteration $\mathcal{C}(i)$, and the edge count switches to the
balanced state $\mathcal{S}(i)$. In each balancing iteration, we examine the
resulting balance state (Alg. 2). $\Sigma^{\prime}_{T}$ in relation to
$\mathcal{B}$. To make the process more efficient, we represent the balanced
state $\Sigma^{\prime}_{T}$ as a string B. The balanced state
$\Sigma^{\prime}_{T}$ represents the 3 edges vectors (src,tgt,sign). If an
edge $i$ is defined by two vertices $(u,v)$ and a sign $s$, the algorithm
balances the graph and stores the edges as src(i)=u, tgt(i)=v, sign(i)=s.

For _graphB++_ implementation, we propose an efficient transform (O(|E|)) of
the balanced state output $\Sigma^{\prime}$ to the string hash key B for
comparison with other balanced states (Alg. 2 line 5). First, the triple edge
vector (src(i),tgt(i),sign(i)) is inserted into a set of tuple data structures
to organize the edges and prepare for string conversion automatically. Then,
it is transformed to a string format "src(i)->tgt(i): sign(i)," and then all
edge strings are concatenated in order, separated by the delimiter "|" and
stored as the B key in $\mathcal{B}$. If B is in $\mathcal{B}$, we increase
the corresponding $C(B)$ value count, where $B$ is the existing balanced state
$\Sigma^{\prime}_{T}$. If $\Sigma^{\prime}_{T}$ is not in $\mathcal{B}$, we
add ($\Sigma^{\prime}_{T}$,$(1,$number of switched edge signs) pair to the
collection. If the state was previously unseen, we add the new balanced state
inefficient matrix format to the hashmap as a string key as illustrated in
Alg. 2. Then, we add 1 to the end of the count stack $\mathcal{C}$ and add the
number of edge switches in the graph for this balanced state to the
frustration cloud frequency stack $\mathcal{S}$. These two values (count stack
and frequency stack) are stored as a pair, and the value of the hashmap of the
balanced state string as a key is that pair. If the balanced state exists in
$\mathcal{B}$, we increase the count at the same string key in $\mathcal{C}$
only (the first element of the pair is modified), as illustrated in the
Algorithm 2. Now, Alg. 2 line 5 takes $O(E)$ for comparison. The minimum
number of edge switches in all balanced states defines the frustration index,
and we compute the frustration index as Fr($\Sigma$)=min($\mathcal{S}$). As
the number of iterations increases, more elements will be added to
$\mathcal{B}$, and the space complexity is linear. This can become an issue
for graphs with millions of nodes and vertices as the frustration cloud is too
big for the main memory.

Data: $\Sigma$ signed graph; $M$ tree sampling method

Result: frustration index $Fr_{\Sigma}=min_{i}(\mathcal{S}(i))$ and
frustration cloud
$\mathcal{F}_{\Sigma}=$($\mathcal{B}(i),\mathcal{C}(i),\mathcal{S}(i)$),
$i\leq\mathcal{F}_{max}$;

1 Generate set $\mathcal{T}_{k}$ of $k$ spanning trees of $\Sigma$ ;

2 Determine $\mathcal{F}_{max}$, $|\mathcal{F}_{\Sigma}|<CAP$ ;

3 Empty matrix $\mathcal{B}$, empty count vector $\mathcal{C}$, and empty edge
switch count vector $\mathcal{S}$, $i=0$, frInd=0. ;

4 foreach  _$T$ spanning tree, $T\in\mathcal{T}_{k}$_ do

5 Find nearest balanced state $\Sigma^{\prime}_{T}$ using Alg. 1 ;

6 frInd = # $\Sigma^{\prime}_{T}$ switch edge signs (Alg. 1, line 3) ;

7 if  _$frInd <max_{i}(\mathcal{S}(i))$ _ then

8 if  _$\Sigma_{T}\notin\mathcal{B}$ _ then

9 if  _$i <\mathcal{F}_{max}$_ then

10 $i$++ ;

11 else

12 $i$ takes the index of current $max_{i}(\mathcal{S}(i))$ ;

13 $\mathcal{S}(i)$ = frInd ;

14 $\mathcal{B}(i)$ = $\Sigma_{T}$ ;

15 $\mathcal{C}(i)=1$ ;

16

17 else

18 $\mathcal{C}_{i}$ ++ ;

19

20 end foreach

Algorithm 3 Scalable Graph Balancing and Frustration Index

Thus, for large graphs, we adapt Alg. 2 as outlined in Alg. 3 to scale the
computation. First, we compute the number of balanced states that we can keep
in the memory as $\mathcal{F}_{max}$ (Alg. 3, line 2). Next, we keep only the
$\mathcal{F}_{max}$ closest balanced states in $\mathcal{B}$, their count
through all $k$ iterations in $\mathcal{C}$, and the number of switched edges
for each of them in $\mathcal{S}(i)$. Note that there can be different
balanced states of $\Sigma$ with the same number of switched edges. Finally,
we compute the frustration index as a minimum of $\mathcal{S})$. The proposed
approach scales well with the size of the signed graph, as we limit the number
of the nearest balanced states that we keep in the memory based on their
frustration index and capacity of the frustration cloud hashmap in-memory
storage, as illustrated in Algorithm 3. The comparison of balanced states now
has up to $k$ iterations times $\mathcal{F}_{max}$ closest balanced states. We
determine $\mathcal{F}_{max}$ so that the size of the frustration cloud in
memory is smaller than $CAP$. In experiments, we define $CAP$ as 75% of the
total RAM size under the assumption that some vital system processes are
running in the background. The algorithmic complexity remains
$O(|E|log(|V|)d_{a})$ where $d_{a}$ is the average degree of a vertex, $|V|$
is the number of vertices, and $|E|$ is the number of edges [2].

##  6 Sampling Spanning Trees

In this section, we propose to utilize the randomization and hybridization of
the standard tree sampling approaches to maximize the chances of discovering
the optimal nearest balanced state in Alg. 2. The following techniques have
been dominantly used in maze generation. Depth first search (DFS) algorithm
[13] with time complexity O($|V|+|E|$) begins the traverse at the root node
and proceeds through the nodes as far as possible until it reaches the node
with all the nearby nodes visited. Breadth first search (BFS) algorithm [13]
with time complexity O($|V|+|E|$) is a graph traversal approach in which the
algorithm first passes through all nodes on the same level before moving on to
the next level.

We propose to use the randomized algorithms as follows: in each iteration, we
shuffle and randomize a node’s neighborhood using a uniformly distributed
random seed number before applying a static algorithm. The idea is that a node
establishes a link to the first node not visited based on the randomized order
of the adjacency list in the network. Randomized Depth First Search (RDFS)
algorithm transforms DFS into a non-deterministic algorithm by eliminating the
static ordering of the adjacency lists. The time complexity of the DFS is
known to be O($|V|+|E|$), where $|V|$ is the number of vertices and $|E|$ is
the number of edges in the signed network. The algorithm also runs in linear
time O($n$), where $n$ is the number of nodes adjacent to a specific node in
the network, so the total time complexity is O($|V|+|E|$). Aldous-Broder
algorithm with complexity O($|V|$) produces a random uniform spanning tree by
performing a random walk on a finite graph with any initial vertex and stops
after all vertices have been visited [26]. For the popular Kruskal’s algorithm
[47] that has a time complexity O($|E|log|V|$) or O($|E|log|E|$), we intend to
generate random spanning trees by assigning random weights to every edge in
each iteration before running the algorithm. It is used to find the minimum
spanning tree of a connected and weighted graph. Randomizing the weights of
Prim’s algorithm [21] [47] with complexity O($|V|^{2}$) can also generate
random spanning trees. We propose a new algorithm, the RDFS-BFS sampler, to
minimize the frustration index and maximize the number of unique stable states
to increase algorithmic chances of finding the optimal state among all the
nearest balanced states.

Figure 3: Breadth First Search (red lines) and Depth First Search (blue lines)
spanning tree construction approaches result in a different number of the
unique nearest balanced states retrieved for iteration. In this example, BFS
produces 3 unique balanced states in 8 iterations, while DFS produces 2 unique
balanced trees. Figure 4: Randomized Breadth First Search (red lines) and
Randomized Depth First Search (blue lines) spanning tree construction
approaches result in a different number of the unique nearest balanced states
retrieved for iteration. In this example, RBFS produces the same balanced
states as BFS in Figure 1 while RDFS captures all five unique and balanced
states.

Data: Signed graph $\Sigma$ and a root Node $n$

Result: Spanning tree $T$ of $\Sigma$

1 Get uniformly distributed random number 0 or 1, $z$ ;

2 if  _$z$ is $0$_ then

3 Run BFS algorithm [13]

4 else if  _$z$ is $1$_ then

5 Run RDFS algorithm

Algorithm 4 Hybridized RDFS-BFS Sampling Table 1: SNAP Signed graph Largest connected component (LCC) attributes. $|V|$ is the number of vertices and $|E|$ is the number of edges in the largest connected component LCC; The label _% positive_ is the number of positive edges divided by $e$; Vertex degree statistics are calculated in terms of the average, mean and maximum node degree; graph density $d=2*|E|/(|V|*|V-1|)$ and $bal_{3}$ is the percentage of triangles in the graph that are balanced.  SNAP | vertices | edges | vertex degrees | attributes
---|---|---|---|---
[33] | $|V|$ | $|E|$ | cycles | % positive | average | median | max | density | $bal_{3}$
$\Sigma$ Fig. 2(a) | 4 | 5 | 2 | 60 | 2.5 | 2.5 | 3 | 0.833 | 0.0
test10 [2] | 10 | 13 | 4 | 53.85 | 2.6 | 2.5 | 4 | 0.288 | 0.5
highland [37] | 16 | 58 | 43 | 50 | 7.25 | 7.5 | 10 | 0.483 | 0.868
sampson18 [42] | 18 | 112 | 95 | 54.4 | 12.44 | 12.50 | 16 | 0.732 | 0.6
rainFall [14] | 306 | 93,636 | 93,331 | 68.78 | 305.00 | 305 | 305 | 1.0 | 0.717
S&P1500 [14] | 1,193 | 711,028 | 709,836 | 75.13 | 1,192 | 1,192 | 1,192 | 0.833 | 0.718
wikiElec [33] | 7,539 | 112,058 | 104,520 | 73.33 | 28.16 | 15 | 1,079 | 0.004 | 0.798
wikiRfa [33] | 7,634 | 175,787 | 168,154 | 77.91 | 43.99 | 13 | 1,233 | 0.005 | 0.717
epinions [33] | 119,130 | 704,267 | 585138 | 83.23 | 11.82 | 2 | 3,558 | $<0.001$ | 0.890
slashdot [33] | 82,140 | 500,481 | 418342 | 77.03 | 12.19 | 2 | 2,548 | $<0.001$ | 0.856

##  7 Complexity Analysis

_graphB++_ that is based on the original implementation of _graphB+_ (BFS) has
a complexity of O($|E|*log(|V|*d)$) time, where |E| is the number of edges,
|V| is the number of vertices, and d is the average spanning-tree degree of
the vertices on each cycle. The code for scaling the processing and saving of
balanced states in the memory-bound frustration cloud and approximating the
frustration index, which builds upon graphB+, adds O(|E|). O($|E|*log(|V|*d)$)
is still the dominant term. On the other hand, for _graphB++_ that is adapted
for other tree-sampling techniques, the reimplemented vertex relabeling step
takes O($|V|+|E|$) instead because DFS is used to perform the pre-order
traversal on a random spanning tree generated by a custom sampler of
particular complexity. The second implementation assigns beginning and end
ranges on each edge to any spanning tree efficiently. Algorithmic complexity
is O($|V||E|*\alpha$), and $\alpha$ is the average depth from a particular
vertex of an edge to the deepest relabeled vertex where the assignment of the
end range of the edge takes place. Both implementations have been connected to
the efficient fundamental cycle balancing method [2] with complexity
O($|E|*log(|V|*d)$). Likewise, the same code was employed for index
computation, which takes O($|E|$). Hence, the total time complexity for the
adapted version of _graphB++_ is O($|V||E|*\alpha$) unless the complexity of
the selected custom sampler is high enough to exceed this complexity. Section
6 outlines the time complexity for each tree-sampling technique.

##  8 Experiments

$\bullet$ Section 8.2 shows which tree-sampling technique for _graphB++_ is
ideal for minimizing the approximation of the frustration index.
$\bullet$ Section 8.3 demonstrates the effect of increasing the number of
iterations on the convergence of the frustration index to the minimum in
_graphB++_ for a given signed network.
$\bullet$ Section 8.4 shows how the proposed _graphB++_ algorithm compares to
Binary Linear Programming model (BLP) [6] for computing the amount of
frustration on real-world signed networks in terms of performance and time.
$\bullet$ Section 8.5 answers how to overcome the memory restrictions of
extracting and saving balanced states with their associated frequencies and
frustration in the frustration cloud for _graphB++_.

Table 2: Konect Largest Connected Component (LCC) graph attributes [30]. $|E|$ is the number of vertices, and $|V|$ is the number of edges in the LCC of the graph. The _% positive_ label marks the percentage of positive edges in the LCC. | Largest Connected Component Graph
---|---
Konect | vertices | edges | cycles | %
[30] | $|V|$ | $|E|$ | $|E|-|V|+1$ | positive
_Sampson_ | 18 | 126 | 145 | 51.32
_ProLeague_ | 16 | 120 | 105 | 49.79
_DutchCollege_ | 32 | 422 | 391 | 31.51
_Congress_ | 219 | 521 | 303 | 80.44
_BitcoinAlpha_ | 3,775 | 14,120 | 10,346 | 93.64
_BitcoinOTC_ | 5,875 | 21,489 | 15,615 | 89.98
_Chess_ | 7,115 | 55,779 | 48,665 | 32.53
_TwitterReferendum_ | 10,864 | 251,396 | 240,533 | 94.91
_SlashdotZoo_ | 79,116 | 467,731 | 388,616 | 76.092
_Epinions_ | 119,130 | 704,267 | 585,138 | 85.29
_WikiElec_ | 7,066 | 100,667 | 93,602 | 78.77
_WikiConflict_ | 113,123 | 2,025,910 | 1,912,788 | 43.31
_WikiPolitics_ | 137,740 | 715,334 | 577,595 | 87.88

###  8.1 Setup, Implementation, and Data

Signed Graph Benchmarks used in the experiments are SNAP [33], Konect [30],
and Amazon ratings [24]. Both SNAP and Konect signed graph characteristics are
described in Table 1 and 2 respectively. Concerning Amazon, ratings and
reviews data [24] provides rating information between 0 (low) and 5 (high) of
the Amazon users on different products. We have transformed the graphs to 18
signed bipartite graphs, where ratings 5 and 4 imply a positive edge, rating 3
and 2 give no edge, and ratings 0 and 1 give a negative edge. The graph
characteristics are described in Table 8 and result in tens of millions of
vertices and edges in a signed graph.
Setup The operating system used for all experimental evaluations is Linux
Ubuntu 20.04.3 running on the 11th Gen Intel(R) Core(TM) i9-11900K @ 3.50GHz
with 16 physical cores. It has one socket, two threads per core, and eight
cores per socket. The architecture is X86_x64. GPU is Nvidia GeForce having
8GB memory. Its driver version is 495.29.05, and the CUDA version is 11.5. The
cache configuration is L1d : 384 KiB, L1i : 256 KiB, L2 : 4 MiB, L3 : 16 MiB.
The CPU op is 32-bit and 64-bit.
Implementation The baseline implementation is based on the published Binary
Linear Programming (BLP) code [6]. The binary linear model runs on a Jupyter
notebook in Python [6] and is based on a Guribo mathematical solver and covers
several parameters [22]. The dependencies of the binary terms in the objective
function of the AND and XOR models are considered using AND constraints and
two standard XOR constraints per edge, respectively. Two replacements in the
ABS model’s objective function linearized two absolute value terms [9]. The
code [6] was run with the following modifications: (1) the method parameter is
-1, automatic; (2) the lazy parameter is 1 with enabled speedup; (3)
_multiprocessing.cpu_count()_ is added as the thread parameter, and (4) the
time limit for the model run is set to up to 40 hours. The code provided [6]
generates random graphs based on the specified number of nodes, edges, and
probability of negative edges. Our improvements to the code allow for the code
to (1) accept the same input format as _graphB++_ ; and to (2) detect and
eliminate duplicates, inconsistencies, self-loops, and invalid signs in the
input graph. The graphB++ implementation extends the open-source
implementation [2] to include and test proposed tree sampling strategies while
keeping the original speed-up optimization for finding fundamental cycles
intact. The implementation of tree sampling strategies and the adaptation of
graphB++ to work with them are highly optimized in C++. This is achieved by
employing the least number of loops possible, incorporating OpenMP directives
for parallelization, and freeing dynamically allocated objects when unused.
The _graphB++_ also implements frustration cloud computation based on the
memory size in Alg. 3. This is done by retrieving the total RAM size from the
Linux system during runtime and the current resident set size in which the
current execution is consuming. Then, these two values are compared in each
iteration to determine the limit of the number of balanced states to save. The
code is released on the anonymous gitHub [4], and the data is publicly
available [33, 30, 24].

Table 3: The time complexities of SEVEN tree-sampling techniques incorporated in _graphB++_ Sampler | BFS | DFS | RDFS | Hybrid | Kruskal | Prim | AB
---|---|---|---|---|---|---|---
Complexity | O($|V|+|E|$) | O($|V|+|E|$) | O($|V|+|E|$) | O($|V|+|E|$) | O($|E|log|V|$) or O($|E|log|E|$) | O($|V|^{2}$) | O($|V|$)

The graph constructed from the Highland Tribes data, _highland_ , has a high
number of balanced triangles (86.8% from Tab. 1), is small in size (3
communities, 16 vertices), and exhibits high clusterability. The _sampson_
signed graph captures 18 monks and their pairwise attitudes with 63 positive
and 49 negative edges [42]. The _rainfall_ signed graph is a fully connected
dense graph of pairwise interrelationships of Australian rainfall between 306
locations. A matrix contains positive and negative correlations between
stations [14]. The _S &P1500_ graph models the correlations of stocks over 2
years [14]. The wikiElec, the signed graph of the Wikipedia administrator
votes, has a low density (0.04), and 79.8% of the triangles in the network are
balanced [33]. The wikiRfa, the Wikipedia manager election [33] has 7,634
nodes and 105,160 edges with an average degree of 43.99 [33]. The slashdot
signed graph has 1 connected component, $82,140$ vertices, $385,515$ positive,
and $114,966$ negative edges [33]. Half of the nodes have two or fewer edges,
and the graph density is 0.1 %. The epinions signed graph we are analyzing has
$131,828$ vertices, $592,236$ positive and $118,974$ negative edges, and low
density (under 0.1%) [33]. Both _slashdot_ and _epinions_ qualify as a large
and sparse graph with a power-law degree distribution [15]. The median degree
in sparse networks is usually much lower than the average degree, and all four
[33] graphs are considered sparse.

_Sampson_ is a directed network that contains ratings between monks related to
a crisis in an abbey (or monastery) in New England (USA), which led to the
departure of several of the monks [30]. _ProLeague_ are results of football
games in Belgium from the Pro League in 2016/2017 in the form of a directed
signed graph. Nodes are teams; each directed edge from A to B denotes that
team A played at home against team B. The edge weights are the goal
difference, and thus favorable if the home team wins, negative if the away
team wins, and zero for a draw [30]. _DutchCollege_ is a directed network that
contains friendship ratings between 32 university freshmen who mostly did not
know each other before starting university. Each student was asked to rate the
other at seven different time points. A node represents a student, and an edge
between two students shows that the left rated the right. The edge weights
show how good their friendship is in the eye of the left node. The weight
ranges from -1 for the risk of conflict to +3 for best friend [30]. _Congress_
is a signed network where nodes are politicians speaking in the United States
Congress, and a directed edge denotes that a speaker mentions another speaker
[30]. In the _Chess_ network, each node is a chess player, and a directed edge
represents a game with the white player having an outgoing edge and the black
player having an ingoing edge. The weight of the edge means the outcome [30].
_BitcoinAlpha_ is a user-user trust/distrust network from the Bitcoin Alpha
platform on which Bitcoins are traded [30]._BitcoinOTC_ is a user-user
trust/distrust network, from the Bitcoin OTC platform, on which Bitcoins are
traded [30]. _TwitterReferendum_ captures data from Twitter concerning the
2016 Italian Referendum. Different stances between users signify a negative
tie, while the same stances indicate a positive link [31]. _WikiElec_ is the
network of users from the English Wikipedia that voted for and against each
other in admin elections [30]. _Slashdot_ is the reply network of the
technology website Slashdot. Nodes are users, and edges are replies [30]. The
edges of _WikiConflict_ represent positive and negative conflicts between
users of the English Wikipedia [30]. _WikiPolitics_ is an undirected signed
network that contains interactions between the users of the English Wikipedia
that have edited pages about politics. Each interaction, such as text editing
and votes, is given a positive or negative value [30]. _Epinions_ is the trust
and distrust network of epinions, an online product rating site. It
incorporates individual users connected by directed trust and distrust links
[30]. The characteristics of the signed graphs are listed in Table 2. Note the
overlap with SNAP data and a subtle difference in how graphs were derived.

###  8.2 Selecting the Spanning Tree Method

In this experiment, we compare the timing and frustration computation of
_graphB++_ implementation of Alg. 2 of SEVEN different tree sampling methods
described in Section 6 and look for the most effective and efficient sampling
method for the frustration index computation. The seven methods are: Prim,
Kruskal, Breadth First Search (BFS), Depth First Search (DFS), Randomized DFS
(RDFS), Hybrid RDFS-BFS and Aldous-Broder sampling. Note that _graphB++_ runs
are non-deterministic, and we run the methods multiple times. The frustration
computed and completion time is always the same for smaller graphs and within
0.1% for larger graphs. We compare the findings to the BLP baseline
implementation for SNAP datasets. Table 1 summarizes the resulting frustration
index per method. The results are summarized in Table 4 in terms of the actual
frustration index value and Figure 7 (top) in terms of the computed
frustration index as a percentage of the total number of edges in the graph.
BFS-spanning trees produce balanced states of minimum edge switches, and DFS-
spanning trees make trees with maximum edge switches, as evident from the
frustration computed in Figure 7 (top). RDFS/Kruskal/Aldous-Broder frustration
scores are slightly better due to the randomization step. BFS discovers the
optimal trees for the frustration computation, but they are repetitive.
The timing is reported on the log 10 scale in seconds in Figure 7 (bottom) as
BLP takes 40 hours for larger datasets (far right navy bar in Fig. 7
(bottom)). RDFS-BFS hybrid approach is competitive with BFS in terms of
frustration index (green and blue bars in Figure 7 (top)) with the small
timing overhead for large graphs (Fig. 7 (bottom)): BFS produces 117,587
frustrations while BFS-RDFS produces 115,932 frustrations in 1000 iterations
for the slashdot dataset. The Prim approach is too slow for large datasets,
and the baseline BLP takes too long or it does not complete. We also tabulated
the timing per iteration for each tree-sampling technique in Table 6. Since
the time complexity of Prim is O($V^{2}$), the number of iterations is set to
1, and it was very inefficient and slow for large graphs such as WikiConflict.
Moreover, Aldous-Broder did not terminate for DutchCollege because, in
uncommon scenarios, this sampler would get stuck looping when performing a
random walk. After all, the current vertex’s neighbors are already visited.

Table 4: SNAP frustration for 1000 iterations of graphB++ with SEVEN different tree samplers introduced in Section 6, and the baseline. AB stands for Aldous-Broder. BFS and Hybrid consistently perform the best.  | rainFall | S&P 1500 | wikiElec | wikiRfa | epinions | slashdot
---|---|---|---|---|---|---
BFS | 10,217 | 134,515 | 24,827 | 43,971 | 100,450 | 117,587
RDFS | 20,047 | 326,957 | 51,197 | 78,215 | 276,584 | 205,236
DFS | 22,879 | 351,135 | 50,617 | 78,151 | 275,211 | 205,089
Hybrid | 10,217 | 134,863 | 23,970 | 42,573 | 118,588 | 115,932
Kruskal | 18,576 | 318,733 | 38,255 | 71,990 | 200,264 | 188,495
AB | 19,403 | 323,657 | 47,252 | 74,438 | 246941 | 198785
Prim | 21,312 | 355,819 | 51,732 | 79,482 | N/A | N/A
BLP | 10,150 | 176,965 | 29,257 | 26,778 | N/A | 77,283
Table 5: Frustration index approximated for Konect datasets [30] using graphB++ for _SIX_ sampling techniques (BFS, RDFS, DFS, Hybrid, Kruskal, Aldous-Broder) in 1000 iterations in Algorithm 3.  Konect [30] | Frustration Index for Spanning Tree Method
---|---
Sampling | BFS | RDFS | DFS | Hybrid | Kruskal | AB
_Sampson_ | 35 | 37 | 39 | 37 | 38 | 37
_ProLeague_ | 13 | 13 | 20 | 13 | 13 | 13
_DutchCollege_ | 2 | 2 | 2 | 2 | 2 | N/A
_Congress_ | 21 | 18 | 53 | 19 | 18 | 19
_BitcoinAlpha_ | 1,105 | 3,487 | 4,371 | 1,022 | 1,716 | 1,585
_BitcoinOTC_ | 1,827 | 6,364 | 6,422 | 1,999 | 2,506 | 3,367
_Chess_ | 20,991 | 23,800 | 23,842 | 20,685 | 23,212 | 23,753
_TwitterRef._ | 16,183 | 104,122 | 93,014 | 27,938 | 40,723 | 37,670
_Slashdot Zoo_ | 109,930 | 190,720 | 191,936 | 111,270 | 172,902 | 188,072
_Epinions_ | 100,646 | 276,883 | 280,758 | 117,829 | 198,989 | 244,482
_WikiElec_ | 22,289 | 45,094 | 45,024 | 23,284 | 36,024 | 39,916
_Wiki Conflict_ | 252,400 | 933,814 | 907,660 | 217,385 | 631,438 | 780,447
_Wiki Politics_ | 86,833 | 268,518 | 266,613 | 80,389 | 172,859 | 224,145
Table 6: Average Frustration Index computation time per iteration using spanning tree sampling methods for 1000 iterations for Konect data in Table 2. BFS sampling method is the fastest. The algorithm is highly parallelizable.  Konect [30] | Computation Time for Spanning Tree Method
---|---
Sampling | BFS | RDFS | DFS | Hybrid | Kruskal | AB
_Sampson_ | 0.0003s | 0.00084s | 0.00053s | 0.00106s | 0.00055s | 0.00057s
_ProLeague_ | 0.00027s | 0.0008s | 0.0035s | 0.00088s | 0.0005s | 0.0005s
_DutchCollege_ | 0.0008s | 0.00216s | 0.00179s | 0.00288s | 0.00158s | N/A
_Congress_ | 0.00102s | 0.00505s | 0.00301s | 0.00629s | 0.00317s | 0.00340s
_BitcoinAlpha_ | 0.024s | 0.126s | 0.103s | 0.143s | 0.098s | 0.102s
_BitcoinOTC_ | 0.041s | 0.265s | 0.229s | 0.268s | 0.214s | 0.231s
_Chess_ | 0.085s | 0.388s | 0.283s | 0.375s | 0.250s | 0.282s
_TwitterRef._ | 0.457s | 2.826s | 2.277s | 2.566s | 2.111s | 2.155s
_SlashdotZoo_ | 0.838s | 19.131s | 13.803s | 15.102s | 9.849s | 11.880s
_Epinions_ | 1.368s | 20.794s | 12.795s | 16.715s | 11.902s | 13.373s
_WikiElec_ | 0.16859s | 0.63977s | 0.487s | 0.559s | 0.462s | 0.502s
_WikiConflict_ | 6.503s | 94.102s | 65.282s | 77.045s | 40.720s | 41.293s
_WikiPolitics_ | 1.582s | 21.585s | 17.374s | 19.613s | 15.925s | 17.010s

###  8.3 Iteration Timing

Here, we evaluate the efficiency of the proposed algorithm by comparing
_graphB++_ frustration and timing if the number of iterations increases.
Figure 5 shows the change in performance for the two best tree sampling
methods when the number of iterations grows. As discussed in Section 6, more
iterations will not impact BFS sampling in smaller graphs. The frustration
shows a slight improvement for the larger graphs for both methods when the
number of iterations increases in Figure 5. Note that the _graphB++_ running
time linearly increases with the number of iterations. The frustration
improvements are insignificant on the sampled signed graph to justify the
increased iteration count.

Figure 5: _graphB++_ frustration for six benchmark datasets, two spanning
three sampling approaches (BFS and RDFS-BFS), and three different iteration
counts.

###  8.4 graphB++ vs. SOTA

In this experiment, we compare the baseline BLP [9] with graphB++
implementation with breadth-first search (BFS) spanning tree sampling in 1000
iterations in terms of the frustration index and the time it takes to compute
the frustration index for 10 benchmark graphs in Table 2. The space complexity
of BLP is $O(|V|^{2})$, where $|V|$ is the number of vertices on the graph.
The researchers also stated that real signed graphs with up to $100,000$ edges
could be solved in 10 hours [9]. Since the frustration cloud computation can
fit in the memory, we ran the _graphB++_ implementation of Algorithm 2 with
the breadth-first search (BFS) spanning tree. All external processes are
closed to prevent interference with time measurements. The measurement for
both methods includes the time it takes to input the file, process it, and
output the results.

Figure 6: _graphB++_ time complexity for BFS sampling method for three different iteration counts, 1000, 2000, and 5000. Table 7: SNAP Signed graph baseline performance as a function of the number of fundamental cycles $|E|-|V|+1$ for the baseline Binary Linear Programming (BLP) [9] and proposed _graphB++_ algorithm with BFS tree sampling for frustration index computation. The BLP baseline was never completed for epinions and never converged beyond Guribo heuristic for S&P1500, wikiElec and wikiRfa datasets (*).  SNAP | Cycles | BLP | graphB++
---|---|---|---
[33] | $|E|-|V|+1$ | index | time | index | time
test10 [2] | 4 | 2 | 0.06s | 2 | 0.08s
highland [37] | 43 | 7 | 0.035s | 7 | 0.13s
sampson18 [42] | 95 | 43 | 0.06s | 39 | 0.27s
rainFall [14] | 93,331 | 10,150 | 7.5hrs | 10,271 | 83.4s
S&P1500 [14] | 709,836 | 176,965* | 14.15*hrs | 134,515 | 1478s
wikiElec [33] | 104,520 | 29,257* | 40hrs | 24,827 | 184s
wikiRfa [33] | 168,154 | 26,778* | 40 hrs | 43,971 | 281s
epinions [33] | 585,138 | N/A | N/A | 100,450 | 1360s
slashdot [33] | 418,342 | 77,283* | 40 hrs | 117,587 | 937s

The results are outlined in the last four columns of Table 2. BLP and graphB++
computation for small graphs was fast and close. Both methods retrieve correct
frustration indices for the three datasets. For the sampson18 dataset, the BLP
heuristic gets stuck in the local minima and results in 43 instead of 39 for
the frustration index. During the optimization process, the BLP model’s bound
value increases from 9 to 40.55088 while the incumbent value is at 43. After,
the best bound also increases to reach an integer solution of 43, resulting in
a gap 0%, whereas _graphB++_ approximates the frustration index to be 39. The
baseline code fails for two graphs with over 700,000 edges, as described in
Table 2. The BLP code fails for the sparse epinions (over 700,000 vertices)
and produces no results, where _graphB++_ finds 1000 nearest balanced states
of the graph, the most optimal one with frustration 100,450 in under 23
minutes. BLP code on the fully connected S&P1500 signed graph produces a
heuristic frustration estimate of 176,965 after 14.15 hours of processing and
fails during the model-solving phase. On the other hand, _graphB++_ finds 1000
near-balanced states of the network and associated frustration 134,515 in 24.6
minutes (Table 2). The most extensive signed graph in which we were able to
run the linear binary solver was the fully connected rainFall network [14] due
to $|E|<100,000$ [9] algorithm limitation. The linear binary solver finished
with a frustration index of 10,150 and a time of 26,054.25s (7.5 hours) while
the _graphB++_ ’s computed frustration index as 10,217 in 83.58s (0.02 hours),
more than 300 times faster.

Figure 7: Frustration index computed (with timing comparison) using Binary
Linear Programming (BLP) [9] and graphB++ 1000 iterations for different tree
sampling methods over different real large signed graphs except for Prim (1
iteration). BLP never finished computing the frustration index for epinions
and sp1500 within the 40 hours allocated.

The linear binary solver fails to complete the computations for wikiElec
within 40 hours: a proximity value of the frustration index was estimated
between 21,299 and 29,257, where _graphB++_ calculated the frustration 24,827
and provided an associated balanced state in 185s (3min+). Note that the BLP
code produces a heuristics frustration estimate in 40 hours for wikiRfa and
slashdot (it fails for epinion) and a gap with _no associated balanced state_
as a guide on balancing the graph. For wikiRfa and slashdot, the heuristic
upper bound computed in 40 hours is much lower than the discovered balanced
states. On the other hand, Table 2 outlines that _graphB++_ finds 1000 unique
near-balanced states for wikiRfa and slashdot in 5min and 15min, respectively,
and offers frustration as a measure of the nearest balanced state it
discovered in the process.

In summary, the _graphB++_ outputs the corresponding balanced state in the
same time frame, while the BLP code does not. The _graphB++_ computes the
nearest balanced states in minutes for large graphs compared to hours for BLP
if the computation does not fail. For eight out of ten graphs tested,
_graphB++_ frustration is exact (4), close to actual (rainFall), or better
than the heuristic (wikiElec, S&P1500, and epinions). Next, we investigate how
the tree sampling methods influence the discovered state frustration. We have
shown that the proposed _graphB++_ balanced state discovery is equal to or
superior to the state of the art for small networks and efficient for more
extensive networks, and scales for large networks both in terms of processing
time and producing outcomes where BLP either fails or makes heuristics without
the associated balanced state.

###  8.5 Scaling Balanced State Discovery

Table 8: Amazon ratings and reviews graph characteristics [24]: The number of vertices, edges, and cycles reflect the number in the largest connected component of each dataset.  Amazon | |V| | |E| | BLP | graphB++ scale
---|---|---|---|---
Ratings |  |  | index | time | index | time
Books | 9,973,735 | 22,268,630 | N/A | N/A | 3,146,316 | 19hrs
Electronics | 4,523,296 | 7,734,582 | N/A | N/A | 1,025,401 | 7.8 hrs
Jewelry | 3,796,967 | 5,484,633 | N/A | N/A | 613,129 | 6hrs
TV | 2,236,744 | 4,573,784 | N/A | N/A | 636,568 | 5.2hrs
Vinyl | 1,959,693 | 3,684,143 | N/A | N/A | 412,859 | 4.4hrs
Outdoors | 2,147,848 | 3,075,419 | N/A | N/A | 264,497 | 4hrs
Android App | 1,373,018 | 2,631,009 | N/A | N/A | 386,947 | 3.6hrs
Games | 1,489,764 | 2,142,593 | N/A | N/A | 173,063 | 2.2hrs
Automotive | 950,831 | 1,239,450 | N/A | N/A | 85,859 | 50min
Garden | 735,815 | 939,679 | N/A | N/A | 70,690 | 32.2min
Baby | 559,040 | 892,231 | N/A | N/A | 106,092 | 30.1min
Digital Music | 525,522 | 702,584 | N/A | N/A | 34,019 | 23min
Instant Video | 433,702 | 572,834 | N/A | N/A | 32,001 | 20.7min
Musical Inst. | 355,507 | 457,140 | N/A | N/A | 24,959 | 14.7min
Amazon | |V| | |E| | BLP | graphB++
Reviews |  |  | index | time | index | time
Digital Music | 9,109 | 64,706 | 10,311 | 38.5 hrs | 19,926 | 101s
Instant Video | 6,815 | 37,126 | 6,001 | 40hrs | 10,833 | 101s
Musical Instr | 2,329 | 10,261 | 1,162 | 136.4s | 2,311 | 17.3s
Figure 8: _graphB++_ time complexity is linear with graph size |V|+|E| for a
fixed number of iterations (1000) for the benchmark (Tab. 2) and Amazon (Tab
8) signed graphs.

In this experiment, we implement Alg. 3 and set the $CAP$ to 75% of the total
RAM size. We apply it to Amazon data in Table 8. The BLP model only worked and
converged for the smallest 3 Amazon signed networks, the Core5 reviews in Tab.
8. All Amazon rating signed graphs have several vertices |V| higher than
300,000, and BLP outputs a memory error before initializing the model. The
algorithm attempts to construct an adjacency matrix that does not fit into
memory for any graph with more than 100,000 vertices. For smaller signed
graphs BLP algorithm converges within 40 hours and finds the optimal
frustration index. _graphB++_ recovers the balanced state and associated
frustration index for small graphs and in minutes for under 2 million edges;
see the last column of Table 8. The serialized process takes about an extra
hour for each 1 million edges, and the processing, for a fixed $CAP$, is
linear in time with the number of edges and vertices, see Figure 8. The most
extensive graph we have processed is Amazon books with close to 10 million
vertices and over 22 million edges, and it took 19 hours to find the nearest
balanced state with frustration 3,146,316. The _graphB++_ processing times of
the 17 Amazon graphs (Tab. 8) exhibit the same linear trend with the size of
the graph. In conclusion, we have demonstrated that graphB++ can scale and
find the nearest balanced state for _any_ size signed graph.

##  9 Summary and Future Work

There is more than one way to achieve balance in the network. The frustration
index characterizes the optimal nearest balanced state where the minimum edge
switches are required to achieve balance in the network. It has been shown
that the tree-spanning approach to graph balancing produces the nearest
balanced states, e.g., there can be no other balanced state nearest balanced
state derived from [38]. In this paper, we extend this finding and propose a
novel algorithm for discovering the nearest balanced states for any graph size
in a fraction of the time. Our approach converges to the global optimum for
the small graphs that the state-of-the-art binary linear programming (BLP)
model computes. BLP does not work for graphs larger than 100,000 vertices
while _graphB++_ seamlessly scales with the graph size to discover one or more
nearest balanced states for the network. The state might not be optimal for a
minimal number of edge switches, but it is close to optimal, and the algorithm
produces a list of edges to switch to achieve the balanced state. We have
shown that the iterations of the underlying algorithm can be parallelized [2],
and we plan to do this in the future. In this work, we report the result on
one computer for 1000, 2000, or 5000 iterations. The timing of one iteration
will help us scale the process even further as we will spawn the jobs in
parallel for large signed graphs.

## References

  * [1] Robert P. Abelson and Milton J. Rosenberg.  Symbolic psycho-logic: A model of attitudinal cognition.  Behavioral Science, 3(1):1–13, 1958.
  * [2] Ghadeer Alabandi, Jelena Tešić, Lucas Rusnak, and Martin Burtscher.  Discovering and balancing fundamental cycles in large signed graphs.  In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’21, New York, NY, USA, 2021. Association for Computing Machinery.
  * [3] Victor Amelkin and Ambuj K Singh.  Fighting opinion control in social networks via link recommendation.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 677–685, 2019.
  * [4] Anonimoys.  Codebase for scaling frustration index and corresponding balanced state discovery for real signed graphs paper.  https://anonymous.4open.science/r/graphBplusplus-547A/README.md, 2023.
  * [5] T. Antal, P. L. Krapivsky, and S. Redner.  Social balance on networks: The dynamics of friendship and enmity.  Physica D: Nonlinear Phenomena, 224(1):130–136, 2006.
  * [6] Samin Aref.  frustration-index-xor.  https://github.com/saref/frustration-index-XOR, 2021.
  * [7] Samin Aref, Andrew J. Mason, and Mark C. Wilson.  An exact method for computing the frustration index in signed networks using binary programming.  CoRR, abs/1611.09030, 2016.
  * [8] Samin Aref, Andrew J. Mason, and Mark C. Wilson.  A modeling and computational study of the frustration index in signed networks.  Networks, 75(1):95–110, 2020.
  * [9] Samin Aref and Zachary P Neal.  Identifying hidden coalitions in the US House of Representatives by optimally partitioning signed networks based on generalized balance.  Scientific reports, 11(1):1–9, 2021.
  * [10] Nikhil Bansal, Avrim Blum, and Shuchi Chawla.  Correlation clustering.  Machine Learning, 56(1-3):89 – 113, 2004.
  * [11] Dorwin Cartwright and Frank Harary.  Structural balance: a generalization of Heider’s theory.  Psychological Rev., 63:277–293, 1956.
  * [12] Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun.  Spagnn: Spatially-aware graph neural networks for relational behavior forecasting from sensor data.  In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 9491–9497. IEEE, 2020.
  * [13] Thomas H. Cormen.  Introduction to algorithms. MIT Press, 2009.
  * [14] Mihai Cucuringu, Apoorv Vikram Singh, Déborah Sulem, and Hemant Tyagi.  Regularized spectral methods for clustering signed networks.  Journal of Machine Learning Research, 22(264):1–79, 2021.
  * [15] Lorenzo Dall’Amico and Romain Couillet and Nicolas Tremblay.  A unified framework for spectral clustering in sparse graphs.  In Journal of Machine Learning Research, pages 1–56, 2021.
  * [16] Tyler Derr, Zhiwei Wang, Jamell Dacon, and Jiliang Tang.  Link and interaction polarity predictions in signed networks.  Social Network Analysis and Mining, 10(1):1–14, 2020.
  * [17] Tomislav Došlić and Damir Vukičević.  Computing the bipartite edge frustration of fullerene graphs.  Discrete Applied Mathematics, 155(10):1294–1301, 2007.
  * [18] Mohammad K Fallah, Mina Mirhosseini, Mahmood Fazlali, and Masoud Daneshtalab.  Scalable parallel genetic algorithm for solving large integer linear programming models derived from behavioral synthesis.  In 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pages 390–394, 2020.
  * [19] Angela Fontan and Claudio Altafini.  Achieving a decision in antagonistic multi-agent networks: frustration determines commitment strength.  2018 IEEE Conference on Decision and Control (CDC), Decision and Control (CDC), 2018 IEEE Conference on, pages 109 – 114, 2018.
  * [20] Kiran Garimella, Tim Smith, Rebecca Weiss, and Robert West.  Political polarization in online news consumption.  In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 152–162, 2021.
  * [21] Saul I. Gass and Michael C. Fu, editors.  Prim’s Algorithm, pages 1160–1160.  Springer US, Boston, MA, 2013.
  * [22] GUROBI.  Gurobi optimization.  https://www.gurobi.com/.
  * [23] Frank Harary and Dorwin Cartwright.  On the coloring of signed graphs.  Elemente der Mathematik, 23:85–89, 1968.
  * [24] Ruining He and Julian McAuley.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering.  In Proceedings of the 25th International Conference on World Wide Web, WWW ’16, pages 507–517. ACM, 2016.
  * [25] Fritz Heider.  Attitudes and cognitive organization.  J. Psychology, 21:107–112, 1946.
  * [26] Yiping Hu, Russell Lyons, and Pengfei Tang.  A reverse aldous-broder algorithm.  ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 57(2):890 – 900, 2021.
  * [27] Falk Hüffner, Nadja Betzler, and Rolf Niedermeier.  Separator-based data reduction for signed graph balancing.  Journal of combinatorial optimization, 20(4):335–360, 2010.
  * [28] Giovanni Iacono and Claudio Altafini.  Average frustration and phase transition in large-scale biological networks: a statistical physics approach.  IFAC Proceedings Volumes, 43(14):320–325, 2010.  8th IFAC Symposium on Nonlinear Control Systems.
  * [29] Ruben Interian, Ruslan G Marzo, Isela Mendoza, and Celso C Ribeiro.  Network polarization, filter bubbles, and echo chambers: An annotated review of measures, models, and case studies.  arXiv preprint arXiv:2207.13799, 2022.
  * [30] Jérôme Kunegis.  KONECT – The Koblenz Network Collection.  In Proceedings of the 22nd International Conference on World Wide Web, WWW ’13, pages 1343–1350. ACM, 2013.
  * [31] Mirko Lai et al.  Stance Evolution and Twitter Interactions in an Italian Political Debate.  InNatural Language Processing and Information Systems, pages 15–27. Springer, 2018.
  * [32] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg.  Predicting positive and negative links in online social networks.  In Proceedings of the 19th International Conference on World Wide Web, WWW ’10, pages 641–650. ACM, 2010.
  * [33] Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * [34] Rui Li, Xin Yuan, Mohsen Radfar, Peter Marendy, Wei Ni, Terence J. O’Brien, and Pablo M. Casillas-Espinosa.  Graph signal processing, graph neural network and graph learning on biological data: A systematic review.  IEEE Reviews in Biomedical Engineering, pages 1–1, 2021.
  * [35] Taoran Liu, Jiancong Cui, Hui Zhuang, and Hong Wang.  Modeling polypharmacy effects with heterogeneous signed graph convolutional networks.  Applied Intelligence, 51:8316–8333, 2021.
  * [36] Tianya Liu, Andong Sheng, Guoqing Qi, and Yinya Li.  Admissible bipartite consensus in networks of singular agents over signed graphs.  IEEE Transactions on Circuits and Systems II: Express Briefs, 68(8):2880–2884, 2021.
  * [37] Kenneth Read.  Cultures of the Central Highlands, New Guinea.  Southwestern Journal of Anthropology, 10(1):1–43, 1954.
  * [38] Lucas Rusnak and Jelena Tešić.  Characterizing attitudinal network graphs through frustration cloud.  Data Mining and Knowledge Discovery, 6, November 2021.
  * [39] Majid Saberi, Reza Khosrowabadi, Ali Khatibi, Bratislav Misic, and Gholamreza Jafari.  Requirement to change of functional brain network across the lifespan.  PLoS ONE, 16(11):1 – 19, 2021.
  * [40] Majid Saberi, Reza Khosrowabadi, Ali Khatibi, Bratislav Misic, and Gholamreza Jafari.  Pattern of frustration formation in the functional brain network.  NETWORK NEUROSCIENCE, 6(4):1334 – 1356, 2022.
  * [41] Majid Saberi, Reza Khosrowabadi, Ali Khatibi, Bratislav Mišić, and Gholamreza Jafari.  Topological impact of negative links on the stability of resting-state brain network.  Scientific Reports, 11(1):2176, 2021.
  * [42] S. Sampson.  A novice in a period of change: An experimental and case study of relationships.  Ph.D. thesis, Cornell University, 1968.
  * [43] Michael T Schaub, Neave O’Clery, Yazan N Billeh, Jean-Charles Delvenne, Renaud Lambiotte, and Mauricio Barahona.  Graph partitions and cluster synchronization in networks of oscillators.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 26(9):094821, 2016.
  * [44] Z Seif and MB Ahmadi.  Computing frustration index using genetic algorithm.  Communications in Mathematical and Computer Chemistry, 71:437–443, 2014.
  * [45] Maria Tomasso, Lucas Rusnak, and Jelena Tešić.  Advances in scaling community discovery methods for signed graph networks.  Journal of Complex Networks, 10(3), 06 2022.  cnac013.
  * [46] William T. Tutte.  Graph theory, volume 21 of Encyclopedia of Mathematics and its Applications.  Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1984\.
  * [47] Yuxin Wu, Deyuan Meng, and Zheng-Guang Wu.  geeksforgeeks.  https://www.geeksforgeeks.org/.  Accessed: 2023-06-01.
  * [48] Xiaozhou Zhou, Haoyu Song, and Jingyuan Li.  Residue frustration-based prediction of protein-protein interactions using machine learning.  Journal of physical chemistry, 126(8):1719–727, 2022.


# Sliced-Wasserstein normalizing flows:
beyond maximum likelihood training

Florentin Coeurdoux1 Nicolas Dobigeon1,2 Pierre Chainais3
1- University of Toulouse This work was supported by the Artificial Natural
Intelligence Toulouse Institute (ANITI, ANR-19-PI3A-0004), the AI Sherlock
Chair (ANR-20-CHIA-0031-01), the ULNE national future investment programme
(ANR-16-IDEX-0004) and the Hauts-de-France Region. IRIT/INP-ENSEEIHT  F-31071
Toulouse  France
2- Institut Universitaire de France (IUF)  France
3- Univ. Lille  CNRS  Centrale Lille  UMR 9189 CRIStAL  F-59000 Lille  France

###### Abstract

Despite their advantages, normalizing flows generally suffer from several
shortcomings including their tendency to generate unrealistic data (e.g.,
images) and their failing to detect out-of-distribution data. One reason for
these deficiencies lies in the training strategy which traditionally exploits
a maximum likelihood principle only. This paper proposes a new training
paradigm based on a hybrid objective function combining the maximum likelihood
principle (MLE) and a sliced-Wasserstein distance. Results obtained on
synthetic toy examples and real image data sets show better generative
abilities in terms of both likelihood and visual aspects of the generated
samples. Reciprocally, the proposed approach leads to a lower likelihood of
out-of-distribution data, demonstrating a greater data fidelity of the
resulting flows.

##  1 Introduction

Approximating probability distributions thanks to normalizing flows (NFs) has
proven to be a powerful approach to accurately represent the underlying
processes at the origin of collected data. NFs are designed to provide a
tractable approximation of the data-generating density $p_{X}$ by transforming
a base normal distribution through a series of bijective transformations [1].
The usual approach to train such architectures relies on the principle of
maximum likelihood estimation (MLE), i.e., maximizing the joint density of the
observed data with respect to (w.r.t.) the parameters of the network. The
constraint of relying on a parametric family of distributions may however
raise crucial issues. Indeed, the optimality of MLE holds only when there is
no model misspecification, i.e., the true data distribution $p_{X}$ belongs to
the family that can be represented by the optimized model. In practice, it is
difficult to ensure a priori that the chosen family of functions is able to
accurately model the targeted distribution. Hence the choice of the learning
objective becomes largely an essential but most often empirical question.
Moreover, training NF explicitly uses a Gaussian likelihood, i.e, a function
of the two first moments. Hence, optimizing a Gaussian likelihood function
leaves any higher order moments completely free. A more refined way of fully
characterizing the targeted distribution would be to match all the other
higher order moments as well. Clearly, using a statistical distance between
distributions during the training process would shift the optimization task
from a nonlinear regression problem w.r.t. the likelihood parameters to a more
relevant problem of looking for the best matching between the generated
distribution and the targeted one. Grover _et al._ [2] proposed a hybrid
objective that bridges implicit and prescribed learning by combining MLE and
adversarial training using a GAN. The hybrid objective has a balancing effect
between perceptually good-looking samples and an accurate density estimation
of the inputs. The authors also demonstrate that this hybrid objective has a
regularizing effect, which permits the model to outperform MLE as well as
adversarial learning. However the choice of using an adversarial architecture
is accompanied by the well-documented drawbacks of GANs. An adversarial
architecture requires the training of an additional discriminator which is
notoriously unstable, can lead to mode collapse [3] and can produce
overconfident predictions from out-of-distribution (OoD) inputs [4].

To overcome the issues mentioned above, this paper introduces a novel hybrid
loss function to be used to train NF. As suggested above, in addition to the
conventional MLE-based term, the proposed hybrid training loss also
incorporates a term to measure the discrepancy between the generated and the
targeted distribution. This term derives from the Sliced-Wasserstein distance
(SW) [5] between the true data distribution and the generated samples.
Experimental results show that augmenting the MLE objective with this term
consistently achieves higher likelihood as well as better quality of the
generated samples. It also demonstrates better OoD detection capabilities
compared to classical training of flow-based models. Section 2 introduces the
proposed method referred to as sliced-Wasserstein NF (SW-NF) and its hybrid
learning objective. Section 3 illustrates its performances on numerical
experiments. Conclusions and prospects are reported in Section 4.

##  2 Sliced-Wasserstein flows

###  2.1 Normalizing flows

NFs are a flexible class of deep generative networks that learn a change of
variable between two probability distributions $p_{X}$ and $p_{Z}$ through an
invertible transformation $f_{\theta}:X\mapsto Z=f_{\theta}(X)$ parametrized
by $\theta$ [1]. In general, $p_{X}$ is only known through samples
$x=\left\\{x_{n}\right\\}_{n=1}^{N}$ and, for tractability purpose, $p_{Z}$ is
chosen as a centered normal distribution with unit variance. The parameters
$\theta$ defining the operator $f_{\theta}$ are then adjusted according the
MLE principle and exploiting the change of variable

$p_{X}(x)=p_{Z}\left(f_{\theta}(x)\right)\left|\operatorname{det}J_{f_{\theta}^{-1}}\right|\quad\textrm{with}\quad
J_{f_{\theta}^{-1}}=\frac{\partial f_{\theta}^{-1}}{\partial x}$ (1)

In other words, the network is trained by minimizing the negative log-
likelihood (NLL) or equivalently the loss function denoted by
$\mathcal{L}_{\text{MLE}}(x;\theta)=-\log(p_{X}(x))$. Without loss of
generality, this work focuses on NFs based on affine coupling layers. Examples
of such flows include RealNVP [6], Glow [7] among others.

###  2.2 Sliced-Wassertein distance

In recent years, Wasserstein distance, which is intimately related to the
theory of optimal transport (OT), has received a considerable attention from
the machine learning (ML) community because of its theoretical properties when
comparing distribution. However, it suffers from strong computational and
statistical limitations, which have severely hindered its effective use in
problems in high dimensions. Several workarounds have been proposed to
alleviate these issues and to enable the use of OT in ML applications. In
particular, the Sliced-Wasserstein (SW) distance is an alternative OT metric
[5]. It has been increasingly popular since it benefits from a significantly
reduced computational cost over the Wasserstein distance, especially on large-
scale problems. In a nutshell, the SW distance compares high-dimensional
distributions by comparing their projected 1d-distributions for which the
computation of the Wasserstein distance is closed-form. According to a Monte
Carlo principle the SW distance between two distributions $p_{X}$ and $p_{Z}$
empirically represented by two sets of samples $x$ and $z$, respectively, can
be approximated by _i)_ drawing a large set of vectors $u_{1},\ldots,u_{J}$
uniformly distributed over the unit sphere then ii) averaging the true
1d-Wasserstein distances between the slices of the two distributions along
directions $u_{i}$. It will be denoted as $\mathcal{L}_{\text{SW}}(x,z)$ in
what follows. Its formulation through its projections onto the unit sphere is
well adapted when samples are vectors. Introduced by Nguyen et _al._ [8], the
so-called convolution SW (CSW) generalizes SW to images using a series of
convolutions in the spirit of a multiresolution approach. We denote
$\mathcal{L}_{\text{CSW}}(x,z)$ the corresponding distance measure.

###  2.3 Hybrid objective function

The proposed SW-NF method builds on a NF neural architecture $f_{\theta}$ to
target a normal latent distribution $p_{Z}$ so that the likelihood of the
observed data $p_{X}$ is well-defined and tractable for exact evaluation and
MLE training. Departing from conventional strategies deployed to train NFs,
this work proposes to derive a hybrid objective function that binds the
likelihood of a prescribed model to high order moment matching. To this aim
the conventional MLE-based objective is augmented with an additional term
measuring the discrepancy between the respective distributions of the original
data $x\sim P_{X}$ and the generated data $\tilde{x}=f^{-1}_{\theta}(z)$. Note
that the likelihood loss is prescribed on the latent space while the SW-based
distance between the generated and target distributions can be prescribed over
the data space. Thus the proposed hybrid objective is a combination of
reconstruction and feature losses defined as

$\mathcal{L}(x,z;\theta)=\mathcal{L}_{\star\text{W}}(x,f^{-1}_{\theta}(z))+\alpha\mathcal{L}_{\text{MLE}}(x;\theta)$
(2)

where $\alpha$ is a hyperparameter balancing the two terms and
$\mathcal{L}_{\star\text{W}}$ refers to either $\mathcal{L}_{\text{SW}}$ for
vector data sets or to $\mathcal{L}_{\text{CSW}}$ for image inputs,
respectively. It is worth noting that the new objective function can be
interpreted as a regularized counterpart of the change of variable on the data
space. Moreover it has the great advantage of not depending on an auxiliary
network as in [2]. Note that the SW-based discrepancy measure between the
generative model and the data distributions can also be prescribed over the
latent space by replacing the SW-based term in (2) by
$L_{\star\text{W}}(z,f_{\theta}(x))$.

##  3 Numerical experiments

This section assesses the versatility and the accuracy of proposed SW-NF
method through numerical experiments. First, experiments conducted on the
Circle data set from scikit-learn are presented to provide some insights about
key ingredients of the proposed approach. Then the performance of SW-NF is
illustrated through more realistic experimental settings exploiting the
CIFAR-10 and SVHN image data sets. It is compared to the alternative training
strategies which consist in relying on the sole MLE or SW terms in (2) and to
the Flow-GAN method which hybridizes MLE and GAN losses [2]. For all results
reported below, the stochastic gradient descent is implemented in Pytorch,
with the Adam optimizer, a learning rate of $10^{-4}$ and a batch size of
$4096$ or $8192$ samples. When dealing with the toy example, the NF
implementing the unknown mapping $f$ is chosen as a RealNVP [6] and the
conventional SW distance is chosen for hybridization. When dealing with the
image-driven experiments, the network architecture is Glow [7] and the CSW is
considered as a statistical distance. The proposed learning strategy is
compared with conventional method from two task-driven perspectives, namely
goodness-of-fit and OoD detection.

Objective | NLL | SW | $\left\|\kappa_{3}\right\|^{2}_{2}$ | $\left\|\kappa_{4}\right\|^{2}_{2}$
---|---|---|---|---
MLE | 0.52 | 0.0033 | 0.2233 | 5.6124
SW | 1.78 | $\mathbf{0.0007}$ | $\mathbf{0.0026}$ | $\mathbf{0.1822}$
SW-Flow | $\mathbf{0.41}$ | 0.0008 | 0.0501 | 0.2259
Flow-GAN [2] | 0.51 | 1.23 | 0.4756 | 7.7725
Table 1: Circle data set: assessment of goodness-of-fit (for all metrics, the lower the better). Objective | Inception | NLL (bits/dim) | CSW | $\left\|\kappa_{3}\right\|^{2}_{2}$ | $\left\|\kappa_{4}\right\|^{2}_{2}$
---|---|---|---|---|---
MLE | 2.42 | 3.54 | 1514.26 | 64.94 | 2462.37
SW | 1.28 | 9.81 | 1190.11 | 13.13 | 598.54
SW-Flow | 3.04 | 3.19 | 1014.26 | 6.24 | 656.37
Flow-GAN | 3.21 | 4.21 | 1621.78 | 72.3 | 3079.12
Table 2: CIFAR-10 data set: assessment of goodness-of-fit (for inception
score, the higher the better; for all other metrics, the lower the better).

Goodness-of-fit: We first study the goodness-of-fit of the targeted latent
space through the learned inverse transform. This evaluation is conducted by
evaluating not only the NLL but also the (C)SW distance and the $3$rd- and
$4$th-order cumulants $\kappa_{3}$ and $\kappa_{4}$ which are expected to be
equal to zero for the prescribed normal distribution $p_{Z}$. Table 1 and
Table 2 report the results reached by the proposed SW-NF approach for the
circle-shaped and the CIFAR-10 data sets, respectively. Table 2 also gives the
inception score for visual inspection of the images. Interestingly, the
proposed SW-NF method provides significantly better NLL scores than the sole
MLE-based learning strategy. For the two data sets, it also leads to
competitive results in terms of (C)SW and normality features, reaching scores
close to SW-based learning. In addition, when considering the CIFAR-10 images,
it leads to higher inception score, thus suggesting higher visual quality of
the generated samples.

Method | Moons | Blobs
---|---|---
MLE | 0.37 | 0.54
SW | 0.61 | 0.70
SW-NF | 0.53 | 0.73
Table 3: Circle data set: performance of OoD in term of AUROC (the closer to 1
the better).

Out-of-distribution detection: The second set of experiments assesses the
ability of detecting OoD data. Table 3 reports the area under the receiving
operator caracteristics (AUROC) for moon-shaped and blob-shaped data sets
given a model trained on circles. In the absence of SW term in the training
loss, the model constantly shows lower ability to discriminate OoD data from
the training distribution data. In the context of CIFAR-10 data sets, the
experimental setup of [9] has been considered. Glow-based NFs have been
trained on CIFAR-10 and we monitor the prescribed likelihood for both CIFAR-10
and SVHN images. Fig. 1 (a) shows the results obtained by a sole MLE-based
training: this model predicts a higher likelihood of OoD data. Fig. 1 (b)
depicts similar plots when considering the proposed hybrid loss: it leads to
lower likelihood to OoD data coming from the SVHN data set.

(a) MLE training

(b) Hybrid training

Figure 1: Likelihood histogram for 1000 CIFAR-10 images (orange) and 1000 SVHN
images (blue) prescribed by a CSW-NF trained on CIFAR-10 images.

##  4 Conclusion

This paper introduces a new paradigm to train normalizing flow. It consists in
augmenting the loss term derived from the conventional maximum likelihood
principle with a discrepancy measure between the generated and targeted
distributions. The resulting hybrid loss function thus combines a Gaussian
likelihood with a (convolutional) sliced-Wasserstein distance between
distributions. Numerical experiments show the better performance of the
proposed hybrid training procedure in terms of perceptual as well as
statistical quantitative metrics. On top of that, one observes a better
robustness of the out-of-distribution behavior. This works consists of a step
towards the design of more powerful NF implemented as true generative models,
beyond their simple use as nonlinear regressors structurally imposed by a
conventional MLE training.

## References

  * [1] G Papamakarios, E Nalisnick, D J. Rezende, S. Mohamed, and B. Lakshminarayanan.  Normalizing flows for probabilistic modeling and inference.  Journal of Machine Learning Research, 22(57):1–64, 2021.
  * [2] A. Grover, M. Dhar, and S. Ermon.  Flow-gan: Combining maximum likelihood and adversarial learning in generative models.  In Proc. AAAI Conference on Artificial Intelligence, 2018.
  * [3] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen.  Improved techniques for training gans.  In Proc. Advances in Neural Information Processing Systems, volume 29, 2016.
  * [4] D. Hendrycks and K. Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  In Proc. International Conference on Learning Representations, 2017\.
  * [5] J. Rabin, G. Peyré, J. Delon, and M. Bernot.  Wasserstein barycenter and its application to texture mixing.  In Proc. Scale Space and Variational Methods in Computer Vision, pages 435–446. Springer Berlin Heidelberg, 2012.
  * [6] L. Dinh, J. Sohl-Dickstein, and S. Bengio.  Density estimation using Real NVP, 2017.
  * [7] D. P Kingma and P. Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In Proc. Advances in Neural Information Processing Systems, 2018\.
  * [8] K. Nguyen and N. Ho.  Revisiting sliced wasserstein on images: From vectorization to convolution, 2022.
  * [9] E. Nalisnick, A. Matsukawa, Y. W. Teh, D. Gorur, and B. Lakshminarayanan.  Do deep generative models know what they don’t know?  In Proc. International Conference on Learning Representations, 2019\.