11institutetext: The University of Iowa, Iowa City, IA 52242, USA
11email<EMAIL_ADDRESS>
# A deep learning network with differentiable dynamic programming for retina
OCT surface segmentation

Hui Xie  Weiyu Xu  Xiaodong Wu

###### Abstract

Multiple-surface segmentation in Optical Coherence Tomography (OCT) images is
a challenge problem, further complicated by the frequent presence of weak
image boundaries. Recently, many deep learning (DL) based methods have been
developed for this task and yield remarkable performance. Unfortunately, due
to the scarcity of training data in medical imaging, it is challenging for DL
networks to learn the global structure of the target surfaces, including
surface smoothness. To bridge this gap, this study proposes to seamlessly
unify a U-Net for feature learning with a constrained differentiable dynamic
programming module to achieve an end-to-end learning for retina OCT surface
segmentation to explicitly enforce surface smoothness. It effectively utilizes
the feedback from the downstream model optimization module to guide feature
learning, yielding a better enforcement of global structures of the target
surfaces. Experiments on Duke AMD (age-related macular degeneration) and JHU
MS (multiple sclerosis) OCT datasets for retinal layer segmentation
demonstrated very promising segmentation accuracy.

###### Keywords:

retina OCT surface segmentation deep learning differentiable dynamic
programming.

##  1 Introduction

Highly accurate surface segmentation for retina optical coherence tomography
(OCT) is a clinical necessity in many diagnostic and treatment tasks of
ophthalmic diseases. In retina OCT imaging, the frequent presence of weak
image boundaries complicated by image artifacts often leads to undesirable
boundary spikes with many automated segmentation methods. However, experienced
ophthalmologists can well delineate retinal surfaces from OCT scans in those
difficult scenarios while taking advantage of their global shape information
and mutual interaction. This indicates that surface insufficiency can be
remedied by making use of surface shape and context priors in the segmentation
methods [29]. We thus propose to seamlessly integrate differentiable dynamic
programming (DDP) [19] into a deep learning framework with an end-to-end
training for retina OCT surface segmentation to enforce surface smoothness.

Many retina OCT segmentation methods have been proposed in past years. Garvin
et al. first introduced the graph-based optimal surface segmentation method
[14] for surface delineation in retinal OCT [6], which was further developed
by incorporating various a priori knowledge reflecting anatomic and imaging
information [29, 25]. Other known OCT surface segmentation approaches include
level set [2, 7, 17], probabilistic global shape model [21], random forest
classifier [12, 30], and dynamic programming [3, 32, 10, 20]. Each of these
traditional methods has its own strength. They all share a common drawback
that is their dependence on handcrafted features.

Armed with superior data representation learning capacity, deep learning (DL)
methods are emerging as powerful alternatives to traditional segmentation
algorithms for many medical image segmentation tasks [15, 28]. Fully
convolutional networks (FCNs) [24, 18], Convolutional neural networks (CNNs)
[27], and U-Net [23, 13, 8, 16, 31] have been utilized for retinal layer
segmentation in OCT images. Due to the scarcity of training data in medical
imaging, it is yet nontrivial for DL networks to implicitly learn global
structures of the target surfaces. Thus, the retinal layer topology cannot be
guaranteed with those methods, neither the continuity and smoothness of the
retinal surfaces can be ensured. To address those limitations, the graph-based
method and dynamic programming were used as post-processing for the deep
learning models to enforce surface monotonicity and smoothness [4, 11]. In
this scheme, feature learning is, in fact, disconnected from the downstream
optimization; the learned features thus may not be truly appropriated for the
model. He et al. further extended the deep regression idea[27] with fully
differentiable soft-argmax operations to generate surface positions followed
by ReLU operations to guarantee the surface order in their fully convolutional
regression network (FCRN) [8]. The hybrid 2D-3D CNN [16] using B-scan
alignment was proposed to obtain continuous 3D retinal layer surfaces from
OCT. The IPM optimization method [31] effectively integrates the DL feature
learning with the IPM optimization to enforce mutual interaction between
surfaces, but the IPM optimization runs on each A-scan. All these methods[8,
16, 31] achieved highly accurate segmentation of retinal surfaces from OCT.
However, their performance is prone to be affected by image outliers with bad
quality or artifacts with the limited size of training data [8], as they lack
the capability of explicitly learning surface smoothness structure.

This study proposes to unify the powerful feature learning capability of DL
with a constrained DDP module in a single deep neural network for end-to-end
training to achieve globally optimal segmentation while explicitly enforcing
surface smoothness. In the proposed segmentation framework, a U-Net with
additional image gradient channels [31] is leveraged as the backbone for
learning parameterized surface costs. The retinal surface inference by
minimizing the total surface cost while satisfying surface smoothness
constraints is realized by a DDP module for a globally optimal solution. The
differentiability of the DDP module enables efficient backward propagation of
gradients for an end-to-end learning. To the best of our knowledge, this is
the first work to apply differentiable dynamic programming for surface
segmentation in medical images. Experiments on retina spectral-domain OCT
datasets demonstrated improved surface segmentation accuracy.

##  2 Method

###  2.1 Problem Formulation

Let $\mathcal{I}(X,Z$ of size $X$$\times$$Z$ be a given 2D B-scan of an OCT
image. For each $x=0,1,\ldots,X-1$, the pixel subset
$\\{\mathcal{I}(x,z)|0\leq z<Z\\}$ forms a column parallel to the
$\mathbf{z}$-axis, denoted by $Col(x)$, which corresponds to an A-scan of the
OCT image. Our goal is to seek $N>0$ retinal surfaces, each of which $S_{i}$
($i=0,1,\ldots,N-1$) intersects every column $Col(x)$ at exactly one location
$z^{(i)}_{x}$, that is, $\mathcal{I}(x,z^{(i)}_{x})\in S_{i}$. To find an
optimal surface $S_{i}$, each pixel $\mathcal{I}(x,z)$ is associated with an
on-surface cost $c_{i}(x,z)$, which is related to the likelihood of
$\mathcal{I}(x,z)$ on $S_{i}$. Each retinal surface express a certain degree
of smoothness, which specifies the maximum allowed change in the
$\mathbf{z}$-dimension of a feasible surface along each unit distance change
in the $\mathbf{x}$-dimension. More specifically, with given smoothness
parameters $\Delta^{(i)}_{x}>0$ for $S_{i}$, if
$\mathcal{I}(x,z^{\prime}),\mathcal{I}(x-1,z^{\prime\prime})\in S_{i}$, then
$|z^{\prime}-z^{\prime\prime}|\leq\Delta^{(i)}_{x}$. The optimization
objective of our surface segmentation problem is to maximize the total on-
surface cost of all pixels on the $N$ sought surfaces
$\mathcal{S}^{*}=\\{S_{0}^{*},S_{1}^{*},\ldots,S_{N-1}^{*}\\}$, with

$\displaystyle\mathcal{S}^{*}$
$\displaystyle=\operatorname*{argmax}_{\mathcal{S}=\\{S_{0},S_{1},...,S_{N-1}\\}}\mathbb{E}(\mathcal{S})=\sum_{i=0}^{N-1}\sum_{\mathcal{I}(x,z)\in
S_{i}}c_{i}(x,z)$ (1)
$\displaystyle\text{s.t.}\quad|z_{x}^{(i)}-z_{x+1}^{(i)}|\leq\Delta_{x}^{(i)},\quad\text{for
$i=0,1,...,N-1$; $x=0,1,...,X-2$.}$

###  2.2 Network Architecture

Figure 1: The U-Net based network architecture with additional seven gradient
channels as input. The number of channels for each layer is indicated with
$c$. The DDP module solves the optimization problem for segmentation and
outputs optimal smooth retinal surfaces $\mathcal{S}$ for the $L_{1}$ loss.

The proposed surface segmentation network is based on a U-Net architecture
[22], as illustrated in Fig. 1, which consists of seven convolution layers.
This U-Net acts as a feature-extracting module for the surface segmentation
head. We started with 24 feature maps in the first convolution layer. In each
downsampling layer, a conv2d module followed by a 2x2 max-pooling doubles the
feature maps, and then a cascade of three same conv2d modules with a residual
connection is used. The upsampling layers use a symmetric structure as the
downsampling layers, but with bilinear upsample modules.

As in the IPM segmentation method [31], we use image gradient information as
additional input channels to enrich image input information while reducing the
learning burden of the network, as image gradients are prominent features to
discriminate image boundaries. Our proposed network used seven gradient
channels including gradient scales along the orientations of $0^{\circ}$
($\mathbf{x}$-dimension), $45^{\circ}$, $90^{\circ}$, and $135^{\circ}$,
normalized gradient directions in the $0^{\circ}$-$90^{\circ}$ and
$45^{\circ}$-$135^{\circ}$ coordinate systems, and the gradient magnitude in
the $0^{\circ}$-$90^{\circ}$ coordinate system, all of which are directly
computed from raw images. All these gradient channels with the raw image are
then concatenated into eight channels as the input to the U-Net framework.

Followed the U-Net is a simple segmentation head, which consists of a 1x1
conv2d followed by a conv2d module. The segmentation head outputs a $N\times
X\times Z$ logits. Note that $N$ is the number of target surfaces and the size
of the input B-scan is $X$x$Z$. A softmax over the $\mathbf{z}$-dimension of
the $N\times X\times Z$ logits gets the predicted probabilities
$p^{(i)}_{x,z}\in[0,1]$, where $i\in[0,N)$, $z\in[0,Z)$, and $x\in[0,X)$. Each
$p^{(i)}_{x,z}$ indicates the probability of the pixel $\mathcal{I}(x,z)$ on
Surface $S_{i}$. The initial estimate $\mu_{x}^{(i)}$ of the surface location
of $S_{i}$ on Column $Col(x)$ can then be computed [8, 31], with
$\mu_{x}^{(i)}=\sum_{z=0}^{z=Z-1}z\cdot p^{(i)}_{x,z}$. The on-surface cost
$c_{i}(x,z)$ for each pixel $\mathcal{I}(x,z)$ on $Col(x)$ is parameterized,
as $c_{i}(x,z)=-(z-\mu_{x}^{(i)})^{2}$.

###  2.3 DDP Module with Smoothness Constraints

The DDP module solves the optimization problem in Eqn. (1). The smoothness
constraints $\Delta^{(i)}_{x}$ between two adjacent columns $Col(x)$ and
$Col(x-1)$ for the target surface $S_{i}$ can be learned from the training
data. In our experiments, $\Delta^{(i)}_{x}$ is simply set to be $\alpha>0$
plus the maximum surface position difference of $S_{i}$ between $Col(x)$ and
$Col(x+1)$ in the whole training set. Let $\tau^{(i)}_{x,z}$ denote the
maximum total on-surface cost for $S_{i}$ starting from $Col(0)$ while ending
at the pixel $\mathcal{I}(x,z)$. Based on the dynamic programming technique,
we have

$\tau^{(i)}_{x,z}=\begin{cases}c_{i}(0,z)&\text{if x=0}\\\
c_{i}(x,z)+\max_{z-\Delta^{(i)}_{x}\leq z^{\prime}\leq
z+\Delta^{(i)}_{x}}\\{\tau^{(i)}_{x-1,z^{\prime}}\\}&\text{else
$x\in[1,X)$},\\\ \end{cases}$ (2)

where $z\in[0,Z)$, and $\Delta^{(i)}_{x}>0$. The maximum of
$\\{\tau^{(i)}_{X-1,0},\tau^{(i)}_{X-1,1},\ldots,\tau^{(i)}_{X-1,Z-1}\\}$
gives the total on-surface cost of the optimal surface $S^{*}_{i}$.

As the $\max$ operator above in Eq. (2) is not differentiable, we use a
differentiable operator of LogSumExp [19], as follows, to approximate the
$\max$ operator:

$\phi^{(i)}_{x-1,z}(\tau)=\frac{1}{t}\log\sum_{z^{\prime}=z-\Delta^{(i)}_{x}}^{z+\Delta^{(i)}_{x}}\exp(t\cdot\tau^{(i)}_{x-1,z^{\prime}}),\quad
t>0.$ (3)

This $\phi^{(i)}_{x-1,z}(\tau)$ has an elegant property that it is bounded in
a narrow band of the real value $m=\max_{z-\Delta^{(i)}_{x}\leq z^{\prime}\leq
z+\Delta^{(i)}_{x}}\\{\tau^{(i)}_{x-1,z^{\prime}}\\}$, as follows:

$m\leq\phi^{(i)}_{x-1,z}(\tau)\leq m+\frac{\log(2\Delta^{(i)}_{x}+1)}{t}$ (4)

In practice, we can choose a proper $t$ such that $\frac{\log(2\Delta
x+1)}{t}\leq\epsilon$, to make the approximation error of
$\phi^{(i)}_{x-1,z}(\tau)$ is less than arbitrary small $\epsilon>0$. Using
the approximation of $\phi^{(i)}_{x-1,z}(\tau)$, the DP recursive formula Eqn.
(2) can be written, as follows.

$\tau^{(i)}_{x,z}=\begin{cases}c_{i}(0,z)&\text{if x=0}\\\
c_{i}(x,z)+\frac{1}{t}\log\sum_{z^{\prime}=z-\Delta^{(i)}_{x}}^{z+\Delta^{(i)}_{x}}\exp(t\cdot\tau^{(i)}_{x-1,z^{\prime}})&\text{else
$x\in[1,X)$},\\\ \end{cases}$ (5)

which is differentiable everywhere. The difference between our method and
Mensch et al.’s DDP [19] is that we consider a constrained DDP model.

In the backtracking stage of DP to obtain optimal $S_{i}^{*}$, we need to know
the surface location $z^{(i)}_{x}$ of $S_{i}^{*}$ on each column $Col(x)$.
Based on Danskin’s Theorem [1], the gradient of $\phi^{(i)}_{x-1,z}(\tau)$
attains $\operatorname*{arg\,max}_{z-\Delta^{(i)}_{x}\leq z^{\prime}\leq
z+\Delta^{(i)}_{x}}\\{\tau^{(i)}_{x-1,z^{\prime}}\\}$, as follows:

$\displaystyle\operatorname*{arg\,max}_{z-\Delta^{(i)}_{x}\leq z^{\prime}\leq
z+\Delta^{(i)}_{x}}\\{\tau^{(i)}_{x-1,z^{\prime}}\\}$
$\displaystyle=\frac{\partial\phi^{(i)}_{x-1,z}(\tau)}{\partial\tau}$ (6)
$\displaystyle=\frac{\exp(t\cdot\tau^{(i)}_{x-1,z^{\prime}})}{\sum_{z^{\prime\prime}=z-\Delta^{(i)}_{x}}^{z+\Delta^{(i)}_{x}}\exp(t\cdot\tau^{(i)}_{x-1,z^{\prime\prime}})},$
$\displaystyle\text{for
$z^{\prime}\in[z-\Delta^{(i)}_{x},z+\Delta^{(i)}_{x}]$}.$

Here Eqn. (6) indicates that the softmax function is a smooth approximation of
the argmax function. Thus, during backtracking, the optimal surface location
$z^{(i)}_{x-1}$ of $S_{i}^{*}$ on $Col(x-1)$ can be computed, as follows.

$\displaystyle
z^{(i)}_{x-1}=\frac{\sum_{z^{\prime}=z-\Delta^{(i)}_{x}}^{z+\Delta^{(i)}_{x}}(z^{\prime}\cdot\exp(t\cdot\tau^{(i)}_{x-1,z^{\prime}}))}{\sum_{z^{\prime}=z-\Delta^{(i)}_{x}}^{z+\Delta^{(i)}_{x}}\exp(t\cdot\tau^{(i)}_{x-1,z^{\prime}})}.$
(7)

In the inference stage, we thus obtain the set of optimal surfaces
$\mathcal{S}^{*}=\\{S_{0}^{*},S_{1}^{*},\ldots,S_{N-1}^{*}\\}$. While during
the training stage, $\mathcal{S}^{*}$ is used to define the loss of the
network for backward propagation.

###  2.4 Loss Functions

We use multiple-surface cross entropy loss $L_{mCE}$ and the L1 loss $L_{1}$
to train our proposed network. Let $g^{(i)}_{x,z}\in\\{0,1\\}$ denote the
ground truth probability of pixel $\mathcal{I}(x,z)$ on $S_{i}$. Then,
$L_{mCE}$ can be computed, with

$L_{mCE}=\frac{-\sum_{i=0}^{N-1}\sum_{z=0}^{Z-1}\sum_{x=0}^{X-1}\\{g^{(i)}_{x,z}\ln(p^{(i)}_{x,z})+(1-g^{(i)}_{x,z})\ln(1-p^{(i)}_{x,z})\\}}{NZX}.$
(8)

Let $s^{(i)}_{x}$ be the ground truth surface location of $S_{i}$ on Column
$Col(x)$. The L1 loss can be computed, as follows

$L_{1}=\frac{1}{NX}\sum_{i=0}^{N-1}\sum_{x=0}^{X-1}\|z^{(i)}_{x}-s^{(i)}_{x}\|.$
(9)

The total loss $L$ for this surface segmentation network is $L=L_{mCE}+L_{1}$.
To improve the training efficiency, we first pre-train the proposed
segmentation network without the DDP module, and then add it for further fine
tuning of the network. In the pre-training, $z^{(i)}_{x}=\mu^{(i)}_{x}$ in
Eqn. 9 is used.

##  3 Experiments

The proposed method was validated on two public data sets – Duke AMD (age-
related macular degeneration) dataset [5] and JHU MS (multiple sclerosis)
dataset [9]. PyTorch version 1.81 on Ubuntu Linux 20.04 was used for the
implementation of the proposed method. Ablation experiments were also
conducted to evaluatet the contribution of the DDP module in the proposed
network. Experiments used 100 epochs for pretraining without the DDP module
and then added the DDP module for further training.

###  3.1 Duke AMD OCT Data

The Duke AMD data set [5] consists of 384 SD-OCT volumes (115 normal and 269
AMD subjects). Each original OCT volume is of size $100\times 512\times 1000$.
The manual tracings are only available around the fovea. So each volume was
cropped to form $51$ B-scans of size $512\times 361$ around the fovea as our
input data. The $\mathbf{z}$-axial resolution of A-scans is 3.24 $\mu
m$/pixel. The manual tracings on each scan include three surfaces: ILM, Inter
RPEDC, and OBM from top to the bottom. In our experiments, we randomly divided
all 384 samples into training (187 AMD + 79 normal), validation (41 AMD + 18
normal), and test (41 AMD + 18 normal) sets. In this experiment, we used 128
channels in the segmentation head, a batch size of 8, and an Adam optimizer
with an initial learning rate of 0.1 without weight decay. In the fine tune
stage, training with the DDP module needed 2.9 seconds per batch.

Table 1: MASD ± standard deviation evaluated on Duke AMD test set and the
ablation study.

|  | Normal Group | AMD Group
---|---|---|---
Methods | TotalMean | GroupMean | ILM | InterRPEDC | OBM | GroupMean | ILM | InterRPEDC | OBM
Method comparison: MASD (mean absolute surface distance) ± standard deviation
($\mu m$)†
G-OSC [29] | – | – | 3.85±0.16 | 4.56±0.35 | – | – | 4.43±0.71 | 9.33±1.74 | –
CNN-S [26] | – | – | 2.88±0.22 | 4.14±0.32 | – | – | 3.43±0.35 | 5.92±0.84 | –
CNN-S-2 [27] | – | 4.07±0.55 | 3.36±0.23 | 3.84±0.58 | 4.97±1.01 | 5.20±1.58 | 3.71±0.77 | 6.07±1.84 | 5.58±1.80
FCRN [16]‡ | 2.78±3.31 | – | 1.24±0.51 | 2.06±1.51 | 2.28±0.36 | – | 1.73±2.50 | 3.09±2.09 | 4.94±5.35
Hybrid2D3D [16] | 2.71±2.25 | – | 1.26±0.47 | 2.10±1.36 | 2.40±0.39 | – | 1.76±2.39 | 3.04±1.79 | 4.43±2.68
Ours | 1.88±1.96 | 1.41±0.89 | 0.55±0.41 | 1.57±0.90 | 2.10±0.45 | 2.08±2.25 | 1.38±3.17 | 1.80±1.10 | 3.06±1.61
Ablation Experiment: MASD ± standard deviation ($\mu m$)
OursWithoutDDP | 1.90 ± 2.10 | 1.43±0.93 | 0.56±0.24 | 1.64±1.06 | 2.10±0.46 | 2.10±2.42 | 1.47±3.65 | 1.83±1.04 | 3.00±1.45
Ablation $p\textrm{-values}$ analysis for the MASD errors
Ours vs. OursWithoutDDP | 1.43e-08 | 1.06e-13 | 3.23e-02 | 3.82e-24 | 9.78e-01 | 6.81e-04 | 9.23e-26 | 1.00e-03 | 2.24e-23
† Bold fonts indicate the best in its column. “-” indicates no reported
results in the corresponding literature.
‡ The results were obtained from the re-implementation of FCRN in Ref. [16].

Table 2: The HD errors evaluated on Duke AMD test set. Bold fonts indicate the best in its column. | Average 95% HD | Average HD
---|---|---
Methods | ILM | InterRPEDC | OBM | ILM | InterRPEDC | OBM
FCRN$(\mu m)$ [16]† | 4.88 | 9.73 | 11.32 | 7.44 | 16.19 | 14.73
Hydrid2D3D$(\mu m)$ [16]† | 4.78 | 8.99 | 9.91 | 7.41 | 14.78 | 13.43
OursWithoutDDP$(\mu m)$ | 4.80 | 6.59 | 6.87 | 6.00 | 11.13 | 9.18
Ours$(\mu m)$ | 4.74 | 6.53 | 6.99 | 5.91 | 10.98 | 9.25
† Courtesy to Hong Liu [16] for the HD results.

The mean absolute surface distance (MASD) errors for the proposed and the
compared methods as well as the ablation study are shown in Table 1. Our DDP
method demonstrated improved segmentation accuracy for all MASD measurements
over the compared methods. The ablation experiment and $p\textrm{-values}$
analysis showed that the DDP module significantly improved the segmentation
accuracy for all three surfaces in the AMD subjects; while for the normal
subjects, the DDP module significantly improved segmentation performance on
both ILM and Inter RPEDC and achieved comparable results on OBM. For the
Hausdorff distance (HD), our method outperformed both FCRN [8] and Hybrid2D3D
[16] (Table 2), achieving much smaller HD errors especially for two
challenging surfaces of Inter RPEDC and OBM. The DDP module significantly
reduced HD errors for both ILM and Inter RPEDC. Sample segmentations of three
AMD cases are illustrated in Fig. 2.

Figure 2: Segmentation samples of three AMD cases in the Duke AMD test set.
The red arrows indicate segmentation errors. Our proposed DDP method
alleviated the errors in weak boundary regions. The orange arrows show that
our DDP results are also not perfect, which show over smoothness effect on the
segmented surfaces.

###  3.2 JHU MS OCT Data

The public JHU MS dataset [9] includes 35 human retina scans acquired on a
Heidelberg Spectralis SD-OCT system, of which 14 are healthy controls (HC) and
21 have a diagnosis of multiple sclerosis (MS). Each volume has 9 surfaces,
and 49 B-scans each with size of 128$\times$1024 after cropping out the center
part by a Matlab script [9]. The $\mathbf{z}$-axial resolution of A-scans is
3.87 $\mu$m/pixel.

Table 3: MASD ± standard deviation evaluated on JHU MS test set and and the
ablation study.

Methods | Overall | ILM | RNFL-GCL | IPL-INL | INL-OPL | OPL-ONL | ELM | IS-OS | OS-RPE | BM
---|---|---|---|---|---|---|---|---|---|---
Method comparison: MASD (mean absolute surface distance)† ± standard deviation
($\mu m$) errors
FCRN [8] | 2.83±1.48 | 2.41±0.81 | 2.96±1.70 | 2.87±1.69 | 3.19±1.49 | 2.72±1.70 | 2.65±1.14 | 2.01±0.88 | 3.55±1.73 | 3.10±2.21
IPM [31] | 2.78±0.85 | 2.32±0.27 | 3.07±0.68 | 2.86±0.33 | 3.24±0.60 | 2.73±0.57 | 2.63±0.51 | 1.97±0.57 | 3.35±0.83 | 2.88±1.63
Ours | 2.75±0.94 | 2.35±0.38 | 2.89±0.69 | 2.83±0.41 | 3.03±0.48 | 2.74±0.62 | 2.57±0.68 | 2.02±0.80 | 3.31±0.77 | 2.99±1.99
Ablation Experiment: MASD ± standard deviation ($\mu m$) errors
OursWithoutDDP | 2.77±0.96 | 2.33±0.30 | 2.91±0.61 | 2.79±0.39 | 3.12±0.58 | 2.69±0.61 | 2.62±0.79 | 2.05±0.98 | 3.45±0.92 | 2.94±1.87
Ablation $p\textrm{-values}$ analysis for the MASD errors
Ours vs. OursWithoutDDP | 2.30e-56 | 4.94e-05 | 5.20e-03 | 1.59e-27 | 1.47e-111 | 2.33e-30 | 1.95e-74 | 1.13e-41 | 7.21e-264 | 1.65e-34
† Bold fonts indicate the best in its column in method comparison.

Table 4: The ablation study on the HD errors evaluated on JHU MS test set.

Methods | ILM | RNFL-GCL | IPL-INL | INL-OPL | OPL-ONL | ELM | IS-OS | OS-RPE | BM
---|---|---|---|---|---|---|---|---|---
Average 95% HD
OursWithoutDDP$(\mu m)$ | 5.42 | 8.38 | 7.24 | 7.63 | 7.45 | 5.99 | 4.66 | 7.55 | 5.92
Ours$(\mu m)$ | 5.44 | 8.11 | 7.31 | 7.5 | 7.59 | 5.85 | 4.47 | 7.50 | 5.90
DDP’s improvement | -0.37% | 3.33% | -0.96% | 1.73% | -1.84% | 2.39% | 4.25% | 0.67% | 0.34%
Average HD
OursWithoutDDP$(\mu m)$ | 8.32 | 13.96 | 11.62 | 12.03 | 11.99 | 8.83 | 7.85 | 10.52 | 8.38
Ours$(\mu m)$ | 8.18 | 13.12 | 11.33 | 10.97 | 11.22 | 8.25 | 6.75 | 10.36 | 8.2
DDP’s improvement | 1.71% | 6.40% | 2.56% | 9.66% | 6.86% | 7.03% | 16.30% | 1.54% | 2.20%

In this experiment, the proposed segmentation model was trained on the last
six HC and last nine MS subjects according to the order of their IDs and
tested on the other 20 subjects, which is the same experimental configuration
as in He et al.’s FCRN [8]. The Gaussian, salt & pepper noise, and random
flipping on the $\mathbf{x}$-direction were used for data augmentation. The
experiment used a segmentation head of 64 channels, batch size 4, an Adam
optimizer with an initial learning rate of 0.01 without weight decay, and a
reducing learning rate on plateau scheduler with patience 20 and factor 0.5.
In the fine tune training stage, DDP needed 13 seconds per batch.

The MASD errors for the FCRN [8], IPM [31] , and proposed methods are shown in
Table 3, which also shows the ablation study results. The proposed method
achieved an overall MASD error of $2.75\pm 0.94$$\mu$m averaged over all nine
surfaces, outperforming both compared methods. For individual surfaces, our
method achieved higher segmentation accuracy on 8 surfaces compared to FCRN
and on 6 surfaces compared to IPM. The DDP module significantly improved the
segmentation accuracy with respect to the MASD metric for all nine surfaces.
As to the HD metric, the DDP module achieved lower HD errors for all segmented
surfaces and lower 95% HD errors on six out of nine surfaces (Table 4).

##  4 Discussion and Conclusion

In this paper, a novel DL framework for OCT surface segmentation is proposed,
which unifies a constrained DDP optimization with a deep learning network for
end-to-end both learning. It effectively integrates the feedback from the
downstream model optimization for segmentation into the forefront feature
learning by the DL network, explicitly enforcing smoothness for all segmented
surfaces. The proposed method was validated in two public OCT datasets and
outperformed the compared state-of-the-art methods. Further improvement
includes using DL to learn surface smoothness constraints in the DDP module.
This proposed method has the potential to be adapted for other structured
surface segmentation problems in medical imaging.

## References

  * [1] Bertsekas, D.P.: Control of uncertain systems with a set-membership description of the uncertainty. Ph.D. thesis, Massachusetts Institute of Technology (1971)
  * [2] Carass, A., Lang, A., Hauser, M., Calabresi, P.A., Ying, H.S., Prince, J.L.: Multiple-object geometric deformable model for segmentation of macular OCT. Biomedical optics express 5(4), 1062–1074 (2014)
  * [3] Chiu, S.J., Li, X.T., Nicholas, P., Toth, C.A., Izatt, J.A., Farsiu, S.: Automatic segmentation of seven retinal layers in SDOCT images congruent with expert manual segmentation. Optics express 18(18), 19413–19428 (2010)
  * [4] Fang, L., Cunefare, D., Wang, C., Guymer, R.H., Li, S., Farsiu, S.: Automatic segmentation of nine retinal layer boundaries in OCT images of non-exudative AMD patients using deep learning and graph search. Biomedical optics express 8(5), 2732–2744 (2017)
  * [5] Farsiu, S., Chiu, S.J., O’Connell, R.V., Folgar, F.A., Yuan, E., Izatt, J.A., Toth, C.A., Group, A.R.E.D.S..A.S.D.O.C.T.S., et al.: Quantitative classification of eyes with and without intermediate age-related macular degeneration using optical coherence tomography. Ophthalmology 121(1), 162–172 (2014)
  * [6] Garvin, M.K., Abràmoff, M.D., Kardon, R., Russell, S.R., Wu, X., Sonka, M.: Intraretinal layer segmentation of macular optical coherence tomography images using optimal 3-D graph search. IEEE transactions on medical imaging 27(10), 1495–1505 (2008)
  * [7] Gawlik, K., Hausser, F., Paul, F., Brandt, A.U., Kadas, E.M.: Active contour method for ILM segmentation in ONH volume scans in retinal OCT. Biomedical optics express 9(12), 6497–6518 (2018)
  * [8] He, Y., Carass, A., Liu, Y., Jedynak, B.M., Solomon, S.D., Saidha, S., Calabresi, P.A., Prince, J.L.: Structured layer surface segmentation for retina OCT using fully convolutional regression networks. Medical image analysis 68, 101856 (2021)
  * [9] He, Y., Carass, A., Solomon, S.D., Saidha, S., Calabresi, P.A., Prince, J.L.: Retinal layer parcellation of optical coherence tomography images: Data resource for multiple sclerosis and healthy controls. Data in brief 22, 601–604 (2019)
  * [10] Keller, B., Cunefare, D., Grewal, D.S., Mahmoud, T.H., Izatt, J.A., Farsiu, S.: Length-adaptive graph search for automatic segmentation of pathological features in optical coherence tomography images. Journal of biomedical optics 21(7), 076015 (2016)
  * [11] Kugelman, J., Alonso-Caneiro, D., Read, S.A., Vincent, S.J., Collins, M.J.: Automatic segmentation of OCT retinal boundaries using recurrent neural networks and graph search. Biomedical optics express 9(11), 5759–5777 (2018)
  * [12] Lang, A., Carass, A., Hauser, M., Sotirchos, E.S., Calabresi, P.A., Ying, H.S., Prince, J.L.: Retinal layer segmentation of macular OCT images using boundary classification. Biomedical optics express 4(7), 1133–1152 (2013)
  * [13] Lee, C.S., Tyring, A.J., Deruyter, N.P., Wu, Y., Rokem, A., Lee, A.Y.: Deep-learning based, automated segmentation of macular edema in optical coherence tomography. Biomedical optics express 8(7), 3440–3448 (2017)
  * [14] Li, K., Wu, X., Chen, D.Z., Sonka, M.: Optimal surface segmentation in volumetric images-a graph-theoretic approach. IEEE transactions on pattern analysis and machine intelligence 28(1), 119–134 (2005)
  * [15] Litjens, G., Kooi, T., Bejnordi, B.E., Setio, A.A.A., Ciompi, F., Ghafoorian, M., Van Der Laak, J.A., Van Ginneken, B., Sánchez, C.I.: A survey on deep learning in medical image analysis. Medical image analysis 42, 60–88 (2017)
  * [16] Liu, H., Wei, D., Lu, D., Li, Y., Ma, K., Wang, L., Zheng, Y.: Simultaneous alignment and surface regression using hybrid 2D-3D networks for 3D coherent layer segmentation of retina OCT images. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 108–118. Springer (2021)
  * [17] Liu, Y., Carass, A., He, Y., Antony, B.J., Filippatou, A., Saidha, S., Solomon, S.D., Calabresi, P.A., Prince, J.L.: Layer boundary evolution method for macular OCT layer segmentation. Biomedical optics express 10(3), 1064–1080 (2019)
  * [18] Masood, S., Fang, R., Li, P., Li, H., Sheng, B., Mathavan, A., Wang, X., Yang, P., Wu, Q., Qin, J., Jia, W.: Automatic choroid layer segmentation from optical coherence tomography images using deep learning. Scientific reports 9(1), 1–18 (2019)
  * [19] Mensch, A., Blondel, M.: Differentiable dynamic programming for structured prediction and attention. In: International Conference on Machine Learning. pp. 3462–3471. PMLR (2018)
  * [20] Rathke, F., Desana, M., Schnörr, C.: Locally adaptive probabilistic models for global segmentation of pathological oct scans. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 177–184. Springer (2017)
  * [21] Rathke, F., Schmidt, S., Schnörr, C.: Probabilistic intra-retinal layer segmentation in 3-D OCT images using global shape regularization. Medical image analysis 18(5), 781–794 (2014)
  * [22] Ronneberger, O., Fischer, P., Brox, T.: U-Net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [23] Roy, A.G., Conjeti, S., Karri, S.P.K., Sheet, D., Katouzian, A., Wachinger, C., Navab, N.: ReLayNet: retinal layer and fluid segmentation of macular optical coherence tomography using fully convolutional networks. Biomedical optics express 8(8), 3627–3642 (2017)
  * [24] Schlegl, T., Waldstein, S.M., Bogunovic, H., Endstraßer, F., Sadeghipour, A., Philip, A.M., Podkowinski, D., Gerendas, B.S., Langs, G., Schmidt-Erfurth, U.: Fully automated detection and quantification of macular fluid in OCT using deep learning. Ophthalmology 125(4), 549–558 (2018)
  * [25] Shah, A., Abámoff, M.D., Wu, X.: Optimal surface segmentation with convex priors in irregularly sampled space. Medical image analysis 54, 63–75 (2019)
  * [26] Shah, A., Abramoff, M.D., Wu, X.: Simultaneous multiple surface segmentation using deep learning. In: Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support, pp. 3–11. Springer (2017)
  * [27] Shah, A., Zhou, L., Abrámoff, M.D., Wu, X.: Multiple surface segmentation using convolution neural nets: application to retinal layer segmentation in OCT images. Biomedical optics express 9(9), 4509–4526 (2018)
  * [28] Shen, D., Wu, G., Suk, H.I.: Deep learning in medical image analysis. Annual review of biomedical engineering 19, 221–248 (2017)
  * [29] Song, Q., Bai, J., Garvin, M.K., Sonka, M., Buatti, J.M., Wu, X.: Optimal multiple surface segmentation with shape and context priors. IEEE transactions on medical imaging 32(2), 376–386 (2012)
  * [30] Xiang, D., Chen, G., Shi, F., Zhu, W., Liu, Q., Yuan, S., Chen, X.: Automatic retinal layer segmentation of OCT images with central serous retinopathy. IEEE journal of biomedical and health informatics 23(1), 283–295 (2018)
  * [31] Xie, H., Pan, Z., Zhou, L., Zaman, F.A., Chen, D.Z., Jonas, J.B., Xu, W., Wang, Y.X., Wu, X.: Globally optimal OCT surface segmentation using a constrained IPM optimization. Optics Express 30(2), 2453–2471 (2022)
  * [32] Yang, Q., Reisman, C.A., Wang, Z., Fukuma, Y., Hangai, M., Yoshimura, N., Tomidokoro, A., Araie, M., Raza, A.S., Hood, D.C., Chan, K.: Automated layer segmentation of macular OCT images using dual-scale gradient information. Optics express 18(20), 21293–21307 (2010)


# The Banking Transactions Dataset and its Comparative Analysis with Scale-
free Networks*

Akrati Saxena1, Yulong Pei1, Jan Veldsink2,Werner van Ipenburg2, George
Fletcher1, Mykola Pechenizkiy1  1Eindhoven University of Technology,
Eindhoven, The Netherlands
<EMAIL_ADDRESS>2Coöperatieve Rabobank
U.A., Utrecht, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

We construct a network of 1.6 million nodes from banking transactions of users
of Rabobank. We assign two weights on each edge, which are the aggregate
transferred amount and the total number of transactions between the users from
the year 2010 to 2020. We present a detailed analysis of the unweighted and
both weighted networks by examining their degree, strength, and weight
distributions, as well as the topological assortativity and weighted
assortativity, clustering, and weighted clustering, together with correlations
between these quantities. We further study the meso-scale properties of the
networks and compare them to a randomized reference system. We also analyze
the characteristics of nodes and edges using centrality measures to understand
their roles in the money transaction system. This will be the first publicly
shared dataset of intra-bank transactions, and this work highlights the unique
characteristics of banking transaction networks with other scale-free
networks.

##  I Introduction

The analysis of large-scale complex networks, including social networks,
technological networks, biological networks, has offered in-depth insights to
uncover and explore their evolution and understand several dynamic phenomena
taking place on these networks [1]. Some interesting examples, where complex
networks have been used to provide solutions for various real-world problems,
include understanding human communication pattern [2], designing fair policies
for overcoming pandemic [3], disrupting communities in terrorist networks [4],
medicine development and treatment of complex diseases [5], and so on. The
analysis of bank transaction network will be beneficial for several research
directions.

  * •

It will help in understanding the flow of money at the microscopic level as
well as how this contributes towards the macroscopic money transaction system.

  * •

It will improve the downstream tasks in the financial domain with guidance
from the topological perspective. Some representative tasks including fraud
detection and user classification in transaction networks.

  * •

It will shed light on financial simulator design. Existing simulators focus on
individual customer behavior, while our analysis can provide complementary
information about collective behaviors of group users.

The existing studies on financial network analysis focus on trade network or
inter-bank transaction networks that show different patterns from intra-bank
transaction data. Most of the studies on the financial domain, either make use
of a financial simulator to generate synthetic transactions, e.g., PaySim [6],
or concentrate on specific downstream tasks such as anomaly detection [7]. In
this paper, we aim to bridge the gap by presenting a detailed analysis of
unweighted and weighted networks constructed from a data set of the money
transactions of more than 1.6 million users of Rabobank.

This paper analyzes unweighted and weighted, large-scale, one-to-one bank
transaction networks. We follow the ‘cookbook approach’ for performing a
systematic analysis of basic and more advanced network characteristics, which
has also been followed in previous network analysis work [2]. We explain the
characteristics of the dataset and networks in Section II. We study some of
the basic network characteristics in Section III. We explore meso-scale
structural properties of the network, including k-cliques and the coupling of
link weight with the network topology in Section IV. We briefly highlight
centrality-based roles of nodes and edges in Section V. We present a
comparative analysis of the unique characteristics of the transaction network
with other scale-free networks in Section VI and, finally, discuss our
findings and future directions in Section VII.

Our main contributions are mentioned below.

  1. 1.

The anonymized banking transaction data of users. As per the best of our
knowledge, this will be the first publicly available dataset of users’ banking
transactions. The dataset is available at
https://github.com/akratiiet/RaboBank_Dataset.

  2. 2.

We perform a detailed analysis of unweighted and weighted banking transaction
networks and highlight the similarities and differences of these networks with
other types of networks. As per the best of our knowledge, this is the first
work to analyze intra-bank transaction network. We hope the shared data and
this work will help further help in understanding the evolution of money flow
in society.

##  II Dataset and Networks

The dataset is collected from the Coöperatieve Rabobank
U.A.111https://www.rabobank.nl/, a Dutch multinational banking and financial
services company. This dataset consists of bank accounts and transactions
between them. For any pairs of accounts with one or more transactions, we also
collected more information, including the numbers of transactions between two
accounts and the total amount of money transferred from one account to another
over a period of 11 years from 2010 to 2020. Thus, it can be organized into a
transaction network, either unweighted or weighted. The data was shared for
1,624,030 bank accounts and 4127043 transactions based on (from_account,
to_account) pair.

We create the network from this data, having 1,624,030 nodes which are
accounts, and 3,823,167 edges which represent that the respective users
performed one or more transactions. Next, we identify the weakly connected
components in the network, and it contains 723 connected components, where the
largest weakly connected component contains 1,622,173 nodes and 3,821,514
edges. The information of connected components is: 1 component has 1,622,172
nodes, 3 components have 27, 15, and 13 nodes, and the rest of the components
have less than ten nodes. The weakly largest connected component will be
referred to as $G(V,E)$ where $V$ is the set of node and $E$ is the set of
edges. In our analysis, we mainly consider the weakly largest connected
component (WLCC) if not mentioned otherwise.

Considering the transaction information, we create two weighted networks (i)
edge-weight is the total amount of money transferred between two accounts, and
(ii) edge-weight is the total number of transactions between two accounts. The
first network will be referred to as $G^{T}$, and the second will be referred
to as $G^{N}$. If there are more than one rows for a (from_account,
to_account) pair in the banking data, then the weights are added to compute
the edge-weight in $G^{T}$ and $G^{N}$ networks.

Newman categorized the real-world scale-free networks into four main
categories: (i) Biological, (ii) Information, (iii) Technological, and (iv)
Social [8]. The banking transaction network falls under the category of
Information Network.

##  III Basic Network Characteristics

We show a small subgraph of the network in Fig. 1 that is sampled using
snowball sampling [9]. The sample has been extracted from the network by
picking a source node at random (shown with black color) and including all
nodes in the sample that are within a topological distance of $l=3$ from the
source node. The node size and color are scaled based on the total degree (in-
degree + out-degree) of the node. It appears from this figure that the network
consists of a few hubs that are well connected with each other and small
clusters of nodes as previously observed in other scale-free networks [2, 10].

Figure 1: A sample subgraph extracted from the black node (chosen uniformly at
random) till distance $l=3$.

To further understand network structure, we show in Fig. 2 the average number
of nodes $N_{s}(l)$ as a function of distance $l$, where $N_{s}(l)$ represents
the number of nodes within a distance $l$ from a given source node. The plots
are shown for several choices of the source node using solid colored lines,
and the average value of $N_{s}(l)$ for uniformly sampled $0.1\%$ source nodes
is shown by the black dashed line. The $N_{s}(l)$ is computed for a small
sample due to the high computational complexity. To a good approximation, we
analyze that the curve follows the Boltzman equation
$B+(A-B)/(1+(x/x_{0})^{p})$, where $A$, $B$, $x_{0}$, and $p$ are the
parameters [11].

Figure 2: Average Number of nodes $(N_{s}(l))$ at distance $l$ as a function
of distance $(l)$ for uniformly sampled $0.1\%$ source nodes (dashed black
lines) and the number of nodes at distance $l$ for some random nodes (solid
thin lines).

We further analyze the macro-scale properties of the network. In Fig. 3, we
show the cumulative in- and out-degree distribution of the weakly largest
connected component (WLCC). The cumulative degree distribution $P_{>}(k)$ is
defined as $P_{>}(k)=\int_{k}^{\infty}p(x)dx$, where $p(x)$ is the degree
probability density function. The cumulative degree distribution $P_{>}(k)$
for the WLCC is approximated well by the power-law equation of the form
$P(k)=c*(k)^{(-\gamma)}$, having the exponent $\gamma\approx 1.43$ and $1.13$
for the cumulative in-degree and out-degree distribution, respectively.
Similar to the communication network [2], this network also has a rapidly
decaying degree distribution where hubs are few, and therefore this network
follows the properties of traditional scale-free networks such as anomalous
diffusion.

Figure 3: Cumulative In-degree and out-degree distribution.

For a better understanding of the network, we plot the out-degree versus in-
degree in Fig. 4; the plot shows that the out-degree is not correlated with
in-degree and has the Spearman correlation coefficient $-0.15$. It indicates
that there is no correlation between in-degree and out-degree. That is
reasonable because most accounts that belong to regular customers have more
transfer-out operations, e.g., purchasing products, than transfer-in
operations, e.g., receiving salaries.

Figure 4: Out-degree versus In-degree for WLCC.

By taking into consideration the transaction information, i.e., times of
transactions and amount of money, we construct two weighted networks, $G^{T}$,
and $G^{N}$. The cumulative edge-weight distributions are shown in Fig. 5. We
also analyze the correlation of edge-weights in both the networks that denote
the dependency of the total transferred amount with the number of
transactions. In specific, we show the correlation for randomly sampled 10000
edges in Fig. 6, and observe that the Spearman correlation coefficient of both
types of edge-weights is 0.71. The results show that the users have a high
correlation between the total amount transferred and the number of
transactions for transferring that amount over time.

Figure 5: Cumulative edge-weight distribution for $G^{T}$ and $G^{N}$. Figure
6: Correlation of edge-weights for randomly sampled 10000 edges in two
networks $G^{T}$ and $G^{N}$. The two weights are clearly correlated having
Spearman’s coefficient 0.71.

The weights on edges contain richer information of transactions, so we compute
the strength where the in-strength $s^{in}(i)$ and out-strength $s^{out}(i)$
of a node $i$ is the sum of weights of incoming edges and out-going edges,
respectively. For example, the in-strength of a node $i$ is computed as,
$s^{in}(i)=\sum_{(j,i)\in E}w_{ji}$, where $w_{ji}$ is the weight of an edge
from node $j$ to node $i$. We investigate the cumulative in- and out-strength
distributions of both weighted networks, and the plots are shown in Fig. 7. As
expected, both distributions follow the power law. The distributions of in-
strength and out-strength are similar because in the process of data
collection, we filter out special accounts such as gas stations that have much
higher in-degrees than out-degrees. In Fig. 8, we show the out-strength versus
in-strength for $G^{T}$ and $G^{N}$ networks having the Spearman correlation
$-0.08$ and $-0.09$, respectively. We observe no correlation between out-
strength and in-strength as expected, as most outgoing transactions are made
to buy basic necessities for daily life, including grocery shopping or gas
station payments, and these transactions have already been removed from the
considered data. However, further detailed analysis will help in highlight the
fraction of expenses for different types; this is out of scope for this work
due to the unavailability of this data.

Figure 7: Cumulative In-strength and Out-strength distribution. Figure 8: Out-
strength versus In-strength for $G^{T}$ network in red color and for $G^{N}$
network in blue color.

We further analyze the average In-strength vs. In-degree and average out-
strength vs. out-degree for understanding the correlation of average edge-
weights from lower to higher degree nodes. The results are shown in Fig. 9. We
observe that the average in/out-strength increases with in/out-degree till a
certain range ($\sim 100$), and after that, no clear correlation is observed
in $G^{T}$ network. The reason is that a user may have incoming or outgoing
transactions with many users, but the transactions with those users might be
performed for a small amount. For example, a user providing a paying-guest
facility may have many incoming transactions, but each user will transfer a
small amount as it is rare that a person stays at one place quite often. Due
to different types of accounts having a higher degree, no clear correlation is
observed for the higher degree nodes. However, the average in/out-strength
increases with in/out-degree in $G^{N}$ network and has a higher correlation.

(i) $G^{T}$

(ii) $G^{N}$

Figure 9: Average In-strength vs. In-degree and average out-strength vs. out-
degree.

###  III-A Neighborhood Analysis

For further understanding, we analyze the characteristics of the local
neighborhood of nodes. We first compute the assortativity of degree and
strength of the network that measures the similarity of connections in the
network with respect to the node degree or strength, respectively [12, 13].
The assortativity values are mentioned in Table I, and neither degree or
strength assortativity nor dis-assortativity is observed. These results are
not in correlation with the assortativity observed in other scale-free
networks, such as phone call based communication network [2] or the Internet
network [14].

We plot the average neighbor In-degree versus In-degree $\left\langle
k^{in}_{nn}|k^{in}\right\rangle$ and average neighbor out-degree versus out-
degree $\left\langle k^{out}_{nn}|k^{out}\right\rangle$ in Fig. 10, and
observe that the most of the users have a high average neighbor degree
irrespective of in/out-degree of a user. The average neighbor In-strength
versus In-strength $\left\langle s^{in}_{nn}|s^{in}\right\rangle$ and average
neighbor out-strength versus out-strength $\left\langle
s^{out}_{nn}|s^{out}\right\rangle$ for $G^{T}$ and $G^{N}$ networks are shown
in Fig. 11 and no correlation is observed due to the basic network
characteristics (as explained for Fig. 9).

Assortativity | Value
---|---
In-degree Assortativity | -0.018
Out-degree Assortativity | -0.011
In-strength Assortativity $G^{T}$ | -0.004
Out-strength Assortativity $G^{T}$ | -0.005
In-strength Assortativity $G^{N}$ | -0.005
Out-strength Assortativity $G^{N}$ | -0.003
TABLE I: In and Out- Degree and Strength Assortativity values for different
networks. Figure 10: Average neighbor In-degree versus In-degree and average
neighbor out-degree versus out-degree.

(i) $G^{T}$

(ii) $G^{N}$

Figure 11: Average Neighbor In-strength versus In-strength and average
neighbor out-strength versus out-strength.

We compute the clustering coefficient of nodes that is the ratio of the number
of closed triads in the neighborhood of a node with the total possible
triangles. For unweighted networks, the clustering coefficient of a node $i$
is computed as [15],

$CC_{i}=\frac{1}{k^{tot}_{i}(k^{tot}_{i}-1)-2k^{r}_{i}}T_{u}$ (1)

where $k^{tot}$ is the sum of in-degree and out-degree of node $i$,
$k^{r}_{i}$ is the reciprocal degree of node $i$, and $T_{u}$ is the number of
directed triangles through node $i$. For weighted networks, the clustering
coefficient is computed as [16],

$CC_{i}=\frac{1}{k^{tot}_{i}(k^{tot}_{i}-1)-2k^{r}_{i}}\sum_{t\in
T^{dir}_{ijk}}(w_{t})^{1/3}$ (2)

where $T^{dir}_{ijk}$ is the set of all directed triangle including node $i$,
and $w_{t}$ for a triangle is computed as
$\widehat{w_{ij}}\widehat{w_{jk}}\widehat{w_{ki}}$ if the triangle has edges
$(i,j)$, $(j,k)$, and $(k,i)$ edges, where $\widehat{w_{ij}}$ is the
normalized edge-weight by that is computed by dividing the edge-weight
$w_{ij}$ by the maximum weight in the network.

The average clustering coefficient versus degree is plotted in Fig. 12. The
clustering coefficient decreases with the total degree of nodes. It shows that
when a user makes more transactions with different accounts, it is less
probable that the neighboring accounts will make a transaction with each
other. The clustering coefficient follows the same pattern as observed in
other large-scale scale-free unweighted and weighted networks [2, 17].

In Table II, we summarize the characteristics of the considered networks that
include the minimum, maximum, mean, standard deviation, skewness222The
skewness measures the asymmetry of the given probability distribution about
its mean., and Kurtosis333Kurtosis computes how heavily the tail of the
distribution differs from the tail of a normal distribution. values of various
basic network properties.

Figure 12: Average clustering coefficient versus total degree. |  | Min | Max | Mean | Std | Skewness | Kurtosis
---|---|---|---|---|---|---|---
G | In-degree | 0 | $2.04\times 10^{4}$ | 2.36 | 32.66 | $2.17\times 10^{2}$ | $1.05\times 10^{5}$
Out-degree | 0 | $1.27\times 10^{4}$ | 2.36 | 20.26 | $3.35\times 10^{2}$ | $1.84\times 10^{5}$
Clustering Coefficient | 0 | 1 | 0.02 | 0.12 | 7.29 | 53.95
$G^{T}$ | In-strength | 0 | $1.57\times 10^{10}$ | $1.54\times 10^{5}$ | $1.34\times 10^{7}$ | $1.01\times 10^{3}$ | $1.18\times 10^{6}$
Out-strength | 0 | $4.04\times 10^{9}$ | $1.54\times 10^{5}$ | $6.53\times 10^{6}$ | $4.71\times 10^{2}$ | $2.61\times 10^{5}$
Edge-weight | 1 | $3.35\times 10^{9}$ | $6.56\times 10^{4}$ | $2.75\times 10^{6}$ | $8.99\times 10^{2}$ | $9.43\times 10^{5}$
Weighted Clustering Coefficient | 0 | $2.72\times 10^{-3}$ | $2.31\times 10^{-7}$ | $7.30\times 10^{-6}$ | $1.62\times 10^{2}$ | $4.22\times 10^{4}$
$G^{N}$ | In-strength | 0 | $5.04\times 10^{6}$ | $68.16$ | $4.08\times 10^{3}$ | $1.17\times 10^{3}$ | $1.44\times 10^{6}$
Out-strength | 0 | $3.11\times 10^{6}$ | $68.16$ | $2.94\times 10^{3}$ | $8.19\times 10^{2}$ | $8.01\times 10^{5}$
Edge-weight | 1 | $2.58\times 10^{4}$ | $28.93$ | $1.19\times 10^{2}$ | $34.02$ | $3.24\times 10^{3}$
Weighted Clustering Coefficient | 0 | $5.47\times 10^{-2}$ | $1.41\times 10^{-5}$ | $1.83\times 10^{-4}$ | $71.15$ | $1.24\times 10^{4}$
TABLE II: Summary of descriptive network statistics.

##  IV Meso-scale Network Characteristics

In this section, we analyze the meso-scale characteristics of the network. The
macro-scale characteristics focus on the properties of the network, and micro-
scale characteristics analyze the properties of the nodes; however, meso-scale
characteristics mainly focus on the structure of the network. For example, how
the nodes are connected, the evolution was random or regulated by any evolving
phenomenon, and so on.

First to analyze the local structure of the network, we compare the presence
of cliques of different orders as these are considered the basic building
blocks and moderate different functionalities of the network [18, 19]. We
compare the cliques of order $k=1,2,...,8$ with random networks in which the
probability to have a connection is the same for all pairs of node. The random
networks are created using Erdős-Rényi (ER) network generative model [20]. The
link formation probability in the ER graph is computed as, $p=2m/(n(n-1))$,
and the expected number $E[X]$ of cliques with $k$ nodes is computed as
$E[X]=\begin{pmatrix}n\\\ k\end{pmatrix}\left(k!/a\right)p^{l}$, where
$l=k(k-1)/2$ and $a=k!$ is the number of automorphic graphs, those are
isomorphic to node-edge order preserved permutation of the graph [21]. The
cliques are counted by considering the undirected version of the network, and
the results are shown in Table III. Note that $k=1$ corresponds to the number
of nodes $n=1622173$ and $k=2$ to the number of edges $m=3318903$, which are
the same in the Rabobank and random network. The presence of high-order
cliques (cliques beyond order three) in the Rabobank network makes it starkly
different from a random network that has a very low probability of high-order
cliques being present.

Order | Empirical Count | ER Expectation
---|---|---
1 | 1622173 | 1622173
2 | 3318903 | 3318903
3 | 417461 | 11.42
4 | 34638 | $7.43\times 10^{-11}$
5 | 3815 | $9.76\times 10^{-28}$
6 | 417 | $2.70\times 10^{-50}$
7 | 26 | $1.61\times 10^{-78}$
8 | 0 | $1.12\times 10^{-112}$
TABLE III: Number of cliques of order $k=1,2,...,8$ in the undirected Rabobank
network (empirical count) and their expectation values in a corresponding ER
network (ER expectation).

We also compare the reciprocity [22] of the network with random networks. The
reciprocity of a directed network is defined as the ratio of the number of
edges pointing in both directions to the total number of edges in the network;
it is computed as, $r=\frac{|(i,j)\in G|(j,i)\in G|}{|E|}$. The expected value
of reciprocity in an Erdős-Rényi directed network is computed as
$E[r]=\frac{m}{n(n-1)}$, where $n$ is the number of nodes and $m$ is the
number of edges. The network $G$ has reciprocity $0.26$ that is much higher
than the expected value of the reciprocity in a random network that is
$1.05\times 10^{-6}$.

To further understand how the users are connected in a group and how these
groups are further connected with each other, we analyze the community
structure of the network. For the Rabobank data, the information of ground
truth communities is not known. However, the unavailability of the ground
truth data is a well-known issue in analyzing network data, and the
researchers have proposed several methods to identify communities using the
structural properties of the network. We use the Leiden community detection
method [23] that is an extension of the Louvain community detection method to
identify well-connected communities in directed weighted/unweighted networks.
The Leiden algorithm starts from a singleton partition and executes in three
phases (i) move nodes from one community to another to identify a partition,
(ii) refinement of the partition, and (iii) create an aggregated network based
on the refined partition using the non-refined partition. The algorithm is
applied iteratively until there is no further improvement. The implementation
for the community detection and their evaluation is used provided by [24].

The distribution of the number of communities versus community size is shown
in Fig. 13. We observe that there are several small-size communities and a few
big-size communities as observed in several scale-free networks [25]. The
communities for network $G$ are linearly binned with bucket size 100. In Table
IV, we discuss the properties of the observed communities. The first row tells
the number of communities; next, we discuss the min, max, mean and std. of
community size. The communities are further evaluated using (i) Modular
Density [26] that explains the expected density of community, (ii) Hub
Dominance [27] that defines the ratio of the degree of the highest connected
node with respect to the theoretically maximal degree within the community,
(iii) Conductance [28] that computes the fraction of total edges that point
outside the community, and (iv) Normalized-cut [28] that is the normalized
value of the fraction of existing edges (out of all possible edges) leaving
the community. The results show that the bank transaction networks contain
community structure as observed in other networks, such as social networks,
co-authorship networks, financial networks, and so on [25]. However, the
limitation of this analysis is that it is entirely based on the Leiden
community detection method due to the unavailability of the ground-truth data.

Figure 13: No. of Communities versus community size. Metric/Network | G | $G^{T}$ | $G^{N}$
---|---|---|---
#Communities | 219 | 1434 | 685
Size-Min | 3 | 2 | 2
Size-Max | 129545 | 173698 | 200910
Size-Mean | 7407.18 | 1131.22 | 2368.14
Size-Std. | 17927.49 | 7456.09 | 12261.84
Modularity Density | 418.99 | 1557.24 | 998.55
Hub Dominance | 0.86 | 1.22 | 1.26
Conductance | 0.10 | 0.22 | 0.17
Normalized-cut | 0.10 | 0.22 | 0.17
TABLE IV: Characteristics of communities identified using Leiden Community
Detection method.

Apart from community structure, we analyze the core-periphery structure of the
network that is another well-known meso-scale network structure [29, 30]. In a
banking transaction network, the core-periphery network will provide insights
into the flow of money from peripheral to more central nodes. The core-
Periphery structure is analyzed using k-shell decomposition algorithm [31]. In
the k-shell method, first, we remove all nodes of degree (in-degree + out-
degree) 1 until there is no node of degree one and assign them shell-index
($k_{S}$) 1. Then iteratively, we remove nodes of degree 2, 3, 4, … until all
nodes have a shell-index value. While removing nodes of degree $k$ if any node
having degree less than $k$ appears, it is also removed in the same iteration
and is assigned shell index $k_{s}=k$. In Fig. 14, we show the distribution of
the nodes as we move from the outer peripheral layer to the inner core layer.
The inner layers have a very small number of nodes. In network $G$, the
highest shell-index is 46 shared by 2,871 nodes that is a very small fraction
of all nodes. The results are similar to as observed in other networks where
only a few nodes acquire the central position in a network [30].

Figure 14: Distribution of nodes from periphery to core.

The structural analysis of the network using k-clique, reciprocity, community,
and core-periphery structure, shows that the network is not random and follows
the structural properties observed in other real-world large-scale scale-free
networks [2, 32, 33].

##  V Characteristics of Nodes and Edges

We briefly analyze the characteristics of nodes and edges using centrality
measures [34] to observe their behavior in correlation with the scale-free
network structure. We first analyze the betweenness centrality of edges to
study the role of a transaction in the money flow. The betweenness centrality
of an edge is computed based on the number of shortest paths passing through
that edge [35]. The algorithm is computationally costly, we therefore u.a.r.
sample a subgraph of 10,000 nodes having 59832 edges and show the cumulative
distribution of the link betweenness centrality in Fig. 15. The results show
that it is very less probable to have a high betweenness centrality,
confirming that most of the transactions happen within groups and a few
transactions happen with the rest of the network.

Figure 15: The cumulative edge betweenness centrality for the sampled graph
having 10k nodes.

To analyze the importance of nodes, we compute PageRank of network $G$, and
its cumulative distribution is shown in Fig. 16. The network has a few nodes
having very high PageRank and many nodes having lower PageRank value, as also
observed in other scale-free networks [36, 10]. The experimental analysis of
link betweenness centrality and PageRank concludes that a few transactions and
a few nodes have much higher importance than others in the bank transaction
network. The one limitation of this analysis is that the comparative study of
nodes’ and edges’ characteristics with their attributes couldn’t be performed
due to the limited information available in anonymized dataset.

Figure 16: The cumulative PageRank distribution on network $G$.

##  VI Transaction network vs. Scale-Free Networks

The banking transaction network follows the characteristics of scale-free
networks; still, it has some clear similarities and differences with other
scale-free real-world networks. The degree distribution, strength
distribution, edge-weight follows power law as observed in other social,
information, biological or technological networks [10]; however, there is no
correlation between in-degree vs. out-degree, and in-strength vs. out-strength
as observed in other Information networks, such as WWW [37]. In social and
Information (transportation) networks, the strength of nodes increases with
degree [2, 38]; however, the banking transaction network has different pattern
due to the nature of the network evolution (please refer to Section III).
These basic characteristics show that neighborhood connectivity is different
from other kinds of networks. The network is neither assortative nor
disassortative, as we observe in most of the other scale-free networks
including trade and finance networks [12, 17]; therefore, no correlation with
the neighborhood nodes’ degree is observed.

The evolution of the network is not random and regulated by an underlying
evolving mechanism. The network has community, and hierarchical structure [25,
30] as observed in other scale-free networks as shown in Section IV. One
another main difference that we observed is the correlation of weak ties with
edge-weights. In social networks, the weak ties, or also referred to as
bridges, are the connections between communities and therefore have a lower
edge-weight as the social interaction between people belonging to two
different communities is not very strong [2]. However, in the banking
transaction network, no such correlation is observed. The transactions that
happened between users belonging to different communities might have lower or
higher strength based on the transferred amount and the total number of
transactions. The evolving model for banking transaction networks is still an
open question, and the above statistical observations mentioning the
similarities and differences will help pin down the underlying evolving
mechanism.

##  VII Conclusion

In this work, we constructed an unweighted network from bank transaction
records of Rabobank and two weighted networks where edge-weights are assigned
using the aggregated amount of transactions and the total number of
transactions from 2010 to 2020. The network is useful in understanding the
flow of money in society as it is derived from one-to-one money transactions.
To our knowledge, it is the first intra-bank transaction network studied so
far and will be the first bank transaction dataset that will be publicly
available. One of our aims was to explore the relationship between the network
topology and the money flow based on the associated weights. The analysis of
k-cliques and reciprocity shows that the network evolution is not random. To
further analyze, we study the network’s community structure that shows that
the users are organized in the smaller groups making more transactions between
them and fewer transactions outside the group.

We believe that this bank transaction network and our analysis of the
network’s characteristics can help solve some practical tasks in the financial
domain. For instance, in anomaly detection, the deviation of anomalous users’
transaction behavior from structural characteristics of normal users might
help in the early detection of suspicious and anomalous users. One can further
analyze the mutual bank transaction network having connections if both end-
users make transactions to each other as it will work as a good proxy to
understand the underlying trust-based social network and its impact on the
money flow.

## References

  * [1] Alain Barrat, Marc Barthelemy, and Alessandro Vespignani.  Dynamical processes on complex networks.  Cambridge university press, 2008.
  * [2] Jukka-Pekka Onnela, Jari Saramäki, Jörkki Hyvönen, Gábor Szabó, M Argollo De Menezes, Kimmo Kaski, Albert-László Barabási, and János Kertész.  Analysis of a large-scale weighted network of one-to-one human communication.  New journal of physics, 9(6):179, 2007.
  * [3] James Atwood, Hansa Srinivasan, Yoni Halpern, and David Sculley.  Fair treatment allocations in social networks.  arXiv preprint arXiv:1911.05489, 2019.
  * [4] Ryan Miller, Ralucca Gera, Akrati Saxena, and Tanmoy Chakraborty.  Discovering and leveraging communities in dark multi-layered networks for network disruption.  In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 1152–1159. IEEE, 2018.
  * [5] Edwin K Silverman, Harald HHW Schmidt, Eleni Anastasiadou, Lucia Altucci, Marco Angelini, Lina Badimon, Jean-Luc Balligand, Giuditta Benincasa, Giovambattista Capasso, Federica Conte, et al.  Molecular networks in network medicine: Development and applications.  Wiley Interdisciplinary Reviews: Systems Biology and Medicine, 12(6):e1489, 2020.
  * [6] Edgar Lopez-Rojas, Ahmad Elmir, and Stefan Axelsson.  Paysim: A financial mobile money simulator for fraud detection.  In 28th European Modeling and Simulation Symposium, EMSS, Larnaca, pages 249–255. Dime University of Genoa, 2016.
  * [7] Yulong Pei, Fang Lyu, Werner van Ipenburg, and Mykola Pechenizkiy.  Subgraph anomaly detection in financial transaction networks.  In ACM International Conference on AI in Finance, 2020.
  * [8] Mark EJ Newman.  The structure and function of complex networks.  SIAM review, 45(2):167–256, 2003.
  * [9] Sang Hoon Lee, Pan-Jun Kim, and Hawoong Jeong.  Statistical properties of sampled networks.  Physical review E, 73(1):016102, 2006.
  * [10] Mark Ed Newman, Albert-László Ed Barabási, and Duncan J Watts.  The structure and dynamics of networks. Princeton university press, 2006.
  * [11] Carlo Cercignani.  The boltzmann equation.  In The Boltzmann equation and its applications, pages 40–103. Springer, 1988.
  * [12] Mark EJ Newman.  Assortative mixing in networks.  Physical review letters, 89(20):208701, 2002.
  * [13] Mark EJ Newman.  Mixing patterns in networks.  Physical review E, 67(2):026126, 2003.
  * [14] Romualdo Pastor-Satorras, Alexei Vázquez, and Alessandro Vespignani.  Dynamical and correlation properties of the internet.  Physical review letters, 87(25):258701, 2001.
  * [15] Giorgio Fagiolo.  Clustering in complex directed networks.  Physical Review E, 76(2):026107, 2007.
  * [16] Jari Saramäki, Mikko Kivelä, Jukka-Pekka Onnela, Kimmo Kaski, and Janos Kertesz.  Generalizations of the clustering coefficient to weighted complex networks.  Physical Review E, 75(2):027105, 2007.
  * [17] Stefano Schiavo, Javier Reyes, and Giorgio Fagiolo.  International trade and financial integration: a weighted network analysis.  Quantitative Finance, 10(4):389–399, 2010.
  * [18] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon.  Network motifs: simple building blocks of complex networks.  Science, 298(5594):824–827, 2002.
  * [19] Nadav Kashtan, S Itzkovitz, R Milo, and U Alon.  Topological generalizations of network motifs.  Physical Review E, 70(3):031909, 2004.
  * [20] Paul Erdos, Alfréd Rényi, et al.  On the evolution of random graphs.  Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
  * [21] Béla Bollobás and Bollobás Béla.  Random graphs.  Number 73. Cambridge university press, 2001.
  * [22] Franco Ruzzenenti, Diego Garlaschelli, and Riccardo Basosi.  Complex networks and symmetry ii: Reciprocity and evolution of world trade.  Symmetry, 2(3):1710–1744, 2010.
  * [23] Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck.  From louvain to leiden: guaranteeing well-connected communities.  Scientific reports, 9(1):1–12, 2019.
  * [24] Giulio Rossetti, Letizia Milli, and Rémy Cazabet.  Cdlib: a python library to extract, compare and evaluate communities from complex networks.  Applied Network Science, 4(1):1–26, 2019.
  * [25] Alex Arenas, Leon Danon, Albert Diaz-Guilera, Pablo M Gleiser, and Roger Guimera.  Community analysis in social networks.  The European Physical Journal B, 38(2):373–380, 2004.
  * [26] Shihua Zhang, Xue-Mei Ning, Chris Ding, and Xiang-Sun Zhang.  Determining modular organization of protein interaction networks by maximizing modularity density.  In BMC systems biology, volume 4, pages 1–12. BioMed Central, 2010\.
  * [27] Andrea Lancichinetti, Mikko Kivelä, Jari Saramäki, and Santo Fortunato.  Characterizing the community structure of complex networks.  PloS one, 5(8):e11976, 2010.
  * [28] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  IEEE Transactions on pattern analysis and machine intelligence, 22(8):888–905, 2000.
  * [29] Stephen P Borgatti and Martin G Everett.  Models of core/periphery structures.  Social networks, 21(4):375–395, 2000.
  * [30] Akrati Saxena and SRS Iyengar.  Evolving models for meso-scale structures.  In 2016 8th International Conference on Communication Systems and Networks (COMSNETS), pages 1–8. IEEE, 2016.
  * [31] Stephen B Seidman.  Network structure and minimum degree.  Social networks, 5(3):269–287, 1983.
  * [32] Yihjia Tsai, Cheng-Chin Lin, and Ching-Chang Lin.  Characteristics of weighted email communications.  In 2005 5th International Conference on Information Communications & Signal Processing, pages 399–403. IEEE, 2005.
  * [33] Akrati Saxena.  A survey of evolving models for weighted complex networks based on their dynamics and evolution.  arXiv preprint arXiv:2012.08166, 2020.
  * [34] Akrati Saxena and Sudarshan Iyengar.  Centrality measures in complex networks: A survey.  arXiv preprint arXiv:2011.07190, 2020.
  * [35] Ulrik Brandes.  On variants of shortest-path betweenness centrality and their generic computation.  Social Networks, 30(2):136–145, 2008.
  * [36] M Zubair Shafiq, Muhammad U Ilyas, Alex X Liu, and Hayder Radha.  Identifying leaders and followers in online social networks.  IEEE Journal on Selected Areas in Communications, 31(9):618–628, 2013.
  * [37] Yihong Hu and Daoli Zhu.  Empirical analysis of the worldwide maritime transportation network.  Physica A: Statistical Mechanics and its Applications, 388(10):2061–2071, 2009.
  * [38] Alain Barrat, Marc Barthélemy, and Alessandro Vespignani.  Modeling the evolution of weighted networks.  Physical review E, 70(6):066149, 2004.