# SPP-CNN: An Efficient Framework for Network Robustness Prediction

Chengpei Wu, Yang Lou, Lin Wang, Junli Li, Xiang Li, and Guanrong Chen
Chengpei Wu and Junli Li are with the College of Computer Science, Sichuan
Normal University, Chengdu 610066, China, and also with the Key Laboratory of
System Control and Information Processing, Ministry of Education, Shanghai
200240, China (e-mail<EMAIL_ADDRESS>lijunli@sicnu.edu.cn).Yang Lou
is with the Department of Computer Science, National Yang Ming Chiao Tung
University, Hsinchu 300, Taiwan (e-mail: felix.lou@ieee.org).Lin Wang is with
the Department of Automation, Shanghai Jiao Tong University, Shanghai 200240,
China, and also with the Key Laboratory of System Control and Information
Processing, Ministry of Education, Shanghai 200240, China (e-mail:
wanglin@sjtu.edu.cn).Xiang Li is with the Institute of Complex Networks and
Intelligent Systems, Shanghai Research Institute for Intelligent Autonomous
Systems, Tongji University, Shanghai 201210, and also with the Department of
Control Science and Engineering, Tongji University, Shanghai 200240, China
(e-mail: lix2021@tongji.edu.cn).Guanrong Chen is with the Department of
Electrical Engineering, City University of Hong Kong, Hong Kong, China
(e-mail: eegchen@cityu.edu.hk).This manuscript has been submitted for
potential publication.(Chengpei Wu and Yang Lou contributed equally to this
work.)(Corresponding author: Yang Lou)

###### Abstract

This paper addresses the robustness of a network to sustain its connectivity
and controllability against malicious attacks. This kind of network robustness
is typically measured by the time-consuming attack simulation, which returns a
sequence of values that record the remaining connectivity and controllability
after a sequence of node- or edge-removal attacks. For improvement, this paper
develops an efficient framework for network robustness prediction, the spatial
pyramid pooling convolutional neural network (SPP-CNN). The new framework
installs a spatial pyramid pooling layer between the convolutional and fully-
connected layers, overcoming the common mismatch issue in the CNN-based
prediction approaches and extending its generalizability. Extensive
experiments are carried out by comparing SPP-CNN with three state-of-the-art
robustness predictors, namely a CNN-based and two graph neural networks-based
frameworks. Synthetic and real-world networks, both directed and undirected,
are investigated. Experimental results demonstrate that the proposed SPP-CNN
achieves better prediction performances and better generalizability to unknown
datasets, with significantly lower time-consumption, than its counterparts.

###### Index Terms:

Complex network, robustness, convolutional neural network, spatial pyramid
pooling, prediction.

##  I Introduction

The study of complex networks enhances our understanding of various real-world
systems, ranging from natural to engineering, to biological, and to social
networks[1, 2, 3]. Scientific investigations intend to reveal the essence and
characteristics of networks, while engineering studies focus on their
functions and applications, regarding such as connectivity[4, 5, 6],
controllability[7, 8, 9, 10, 11, 12, 13, 14], data transmission and
communication abilities[15, 16], and so on. Today, random failures and
malicious attacks take place in many engineering and technological
applications, which significantly degrade or even destroy the network normal
functions. Therefore, it has become important and necessary to strengthen such
network functions against attacks and failures[17, 18, 19, 4, 20, 21, 5, 22,
23, 6]. This leads to the concern of network robustness, which has different
meanings in different scenarios, and here it refers to the ability of a
network to sustain its normal functions when a fraction of the network nodes
and/or edges failure due to attacks. In this paper, network robustness is
studied with respect to both connectivity and controllability against
destructive attacks and failures in the forms of node-removals.

The enhancement of network robustness depends on some reliable and efficient
measures of the defined robustness[5, 6]. In general, network robustness can
be measured in both a priori and a posteriori manners. A priori measures are
referred to specific network features that can be evaluated and calculated
without performing attack simulations. Widely-used a priori robustness
measures include topological measures, for example betweenness centrality[24]
and clustering coefficient[25], and spectral measures include such as natural
connectivity[26], algebraic connectivity[27], effective resistance[28], and so
on. Network spectra can be calculated using the network adjacency matrix and
Laplacian matrix[29]. Although a priori measures are easy-to-access with lower
computational cost and complexity[6, 22], they have limited scopes of
applications[30].

In contrast, a posteriori robustness measures have intuitively clear meanings
with a wider range of applicability, namely, a posteriori measures are
applicable to any type of networks under any kind of attacks, and they return
distinguishable measure values with respect to different attack strategies.
Therefore, the practical a posteriori measures remain as the main approach in
robustness studies for many real-world applications. A posteriori measures are
quantified by recording a sequence of values that represent the remaining
functionality (here, connectivity and controllability) of the network after a
series of node- or edge-removal attacks. Evaluation of a posteriori measures
is generally time-consuming, however, not only due to the iterative node- or
edge-removal processes, but also because of the recalculation of the concerned
network functions, such as the size of largest connected component[4], the
number of needed driver nodes[7, 8], and the number of communicable node
pairs[15, 16].

In practice, it is not always necessary to calculate the exact values of the
network robustness as done in attack simulation. For example, during an
optimization process, network robustness is reevaluated after each structural
disturbance, e.g., edge rewiring[31, 32, 33]. It is very time-consuming to
perform an attack simulation each time, especially for large-scale networks.
Therefore, robustness prediction approaches are more desirable in such cases,
which significantly reduce the cost and time complexity[34].

Network robustness prediction can be achieved by using either analytical or
computational methods. In so doing, the time complexity is either constant[35]
or increasing but significantly slower than that of the attack simulation[36].
Analytical approximations have a much narrower scope of applications to, e.g.,
the controllability robustness under random edge-attacks[37, 38, 35]. In
contrast, machine learning algorithms, such as neural networks and random
forest schemes, have no such limitation[39]. By combining several machine
learning algorithms together, a surrogate ensemble can be formed for
robustness prediction through an optimization process[34].

Regarding neural networks-based frameworks, deep neural networks are more
powerful than canonical machine learning algorithms for efficiently processing
network data. Successful application examples include critical node
identification using deep reinforcement learning[40] and graph attention
networks[41]. The convolutional neural network (CNN)[42]-based prediction
processes network data as gray-scale images[36], thereby fast approximating
the robustness performances against different attacks. Prior knowledge is
useful to further improve the prediction performances[43]. This
straightforward approach requires downsampling and upsampling for the input
data that are smaller and larger than the fixed input size of CNN, however,
thus information distortion may be severe if the input network size is very
large or very small. Graph neural networks (GNN)[44, 45] are able to compress
and unify higher-dimensional network raw data to lower-dimensional
representations. Therefore, GNN-based approaches are more tolerable to the
input data-size changes, and so have better prediction performances[46].
Taking the connectivity robustness prediction as an example, the CNN-based
approach needs an average run time that is $3.48\%$ of the attack simulation,
while the GNN-based approach requires up to $82.8\%$ of the attack
simulation[46].

In this paper, to overcome the aforemention mismatch issue between the various
input sizes and the fixed input size in the CNN-based processing, and also to
achieve a balance between the flexibility of processing different input sizes
and the approximation speed in computation, a spatial pyramid pooling
(SPP)[47] layer is installed into the network robustness predictor, which is
demonstrated to be superior to the other CNN-based and GNN-based frameworks.

Specifically, the work and contributions of this paper are summarized as
follows:

  * 1)

SPP-CNN is proposed, which has a wider tolerance to different input-data sizes
than the CNN- and GNN-based approaches[46], while maintaining fast
approximation speed like the CNN-based approaches[36].

  * 2)

SPP-CNN shows stronger generalizability than the other approaches on
predicting the network robustness for datasets with unseen topologies and
sizes.

  * 3)

SPP-CNN demonstrates better performances than the other approaches on
predicting the robustness of real-world networks, with consistent advantages
for both synthetic and real-world networks.

The rest of the paper is organized as follows. Section II reviews several
measures of the network robustness against destructive node-removal attacks,
and both CNN-based and GNN-based prediction frameworks. Section III introduces
the proposed SPP-CNN. Section IV presents extensive empirical experiment
results with comparison and analysis. Section V concludes the investigation.

##  II Preliminaries

In this paper, network robustness is considered from two specific aspects,
namely the a priori connectivity robustness and controllability robustness,
while other a posteriori robustness measures such as communication robustness
can be investigated in a similar manner. Only node-removal attacks is
discussed, while edge-attacks can also be studied in the same way. Three
state-of-the-art network robustness predictors are reviewed, namely the CNN-
based robustness predictor (CNN-RP)[36], PATCHY-SAN[48], and the learning
feature representation-based predictor (LFR-CNN)[46]. Both PATCHY-SAN and LFR-
CNN consist of a GNN module for graph representation learning, followed by a
CNN for robustness performance prediction (regression).

###  II-A Robustness Measures

####  II-A1 Connectivity Robustness

In this paper, connectivity robustness refers to the ability of a network to
maintain its connectivity against destructive node-removal attacks, which is
widely measured by counting the size of the largest connected component (LCC)
in the network after an attack. If an undirected network is connected or a
directed network is weakly connected, then the LCC is the network itself;
otherwise, a connected component that includes the largest number of nodes is
an LCC. Connectivity robustness is evaluated by the following index:

$R_{1}=\sum_{i=0}^{N-1}{r_{1}(i)}=\sum_{i=0}^{N-1}{\frac{N_{L}(i)}{N-i}}\,,$
(1)

where $N$ is the number of nodes in the given network before being attacked;
$i$ is the total number of nodes that have been removed from the network;
$N_{L}(i)$ is the number of nodes in the remaining LCC; therefore, $r_{1}(i)$
is the density of nodes remaining in the $i$th LCC. The denominator $N-i$
ensures $R_{1}\in(0,1]$, but if the denominator is replaced by $N$ then
$R_{1}\in(0,0.5]$ as used in [4].

The series of values $r_{1}(i)$ can be plotted to show a connectivity curve,
for which the scalar $R_{1}$ reflects the overall connectivity robustness
against node-removal attacks: a higher $R_{1}$ value indicates a better
connectivity robustness.

####  II-A2 Controllability Robustness

Controllability robustness reflects the ability of a networked system to
maintain or regain its controllability with the lowest control cost, e.g., the
minimum number of driver nodes (DN) that are needed to add to the network
after the attack. For a general linear time-invariant (LTI) networked system
$\dot{{\bf x}}=A{\bf x}+B{\bf u}$, where ${\bf{x}}\in\mathbb{R}^{N}$
represents the state vector; ${\bf{u}}\in\mathbb{R}^{b}$ represents the
control input; $A\in\mathbb{R}^{N\times N}$ and $B\in\mathbb{R}^{N\times b}$
are constant matrices. This LTI system is state controllable if and only if
there exist a control input $\bf{u}$ that can drive the state $\bf{x}$ to move
from any initial state to any target state in the state space in finite time.
The state controllability can be determined by checking whether the
controllability matrix $[B\ AB\ A^{2}B\ \cdots A^{N-1}B]$ has a full row-
rank[49]. The concept of structural controllability is a slight generalization
of the state controllability, to deal with two parameterized matrices $A$ and
$B$, in which the parameters characterize the structure of the underlying
system in the sense that if there are specific parameter values that can
ensure the system to be state controllable then the system is said to be
structurally controllable.

For a network with many LTI systems, any node system with control input is a
ND. The minimum number of NDs needed to retain the (state or structural)
controllability of the network can be determined by using either the minimum
inputs theorem (MIT)[7] for directed networks or the exact controllability
theorem (ECT)[8] for both directed and undirected networks, which are defined
as follows:

$N_{D}=\begin{cases}\text{max}\\{1,N-|E|\\},&\text{using
MIT\cite[cite]{[\@@bibref{}{Liu2011N}{}{}]}},\\\
\text{max}\\{1,N-\text{rank}(A)\\},&\text{using
ECT\cite[cite]{[\@@bibref{}{Yuan2013NC}{}{}]}},\\\ \end{cases}$ (2)

where $|E|$ represents the number of edges in the maximum matching $E$, which
is a basic concept in graph theory[7]. Under a sequence of node-removal
attacks, the controllability robustness is measured by

$R_{2}=\sum_{i=0}^{N-1}{r_{2}(i)}=\sum_{i=0}^{N-1}{\frac{N_{D}(i)}{N-i}}\,,$
(3)

where $N_{D}(i)$ is the number of DNs and $r_{2}(i)$ is the density of DNs,
which are needed to retain the network controllability after a total of $i$
nodes have been removed by the attack. Similarly, the series of values
$r_{2}(i)$ can be plotted to show a controllability curve, where $R_{2}$
measures the overall controllability robustness: a lower $R_{2}$ values
indicates a better connectivity robustness.

###  II-B Network Robustness Predictors

There are three commonly-used network robustness predictors, namely CNN-
RP[36], PATCHY-SAN[48], and FR-CNN[46]. Basic principles as well as the pros
and cons of these approaches are reviewed and discussed in this subsection.

The general structures of CNN-RP, PATCHY-SAN, and LFR-CNN are visualized in
Fig. 1. The input is the adjacency matrix, which could also be a Laplacian
matrix or other representations, and the output is the predicted robustness
performance.

Figure 1: General frameworks of CNN-RP, PATCHY-SAN, and LFR-CNN. CNN-RP
processes network data as gray-scaled images, while for PATCHY-SAN and LFR-
CNN, the LFR module performs the selection, assembly, and normalization (SAN)
operations, which compress higher-dimensional (HD) network data to be lower-
dimensional (LD) representations.

####  II-B1 CNN-RP

The structure of CNN-RP[36, 50], using a VGG-structured CNN[51], is shown in
Fig. 2. Adjacency matrices are treated as gray-scale images and processed by
CNN directly. Classification and regression tasks are completed using such an
image-processing mechanism[43].

Figure 2: CNN structure in CNN-RP. The input is an adjacency matrix; the
output is an $N$-vector. Seven feature map (FM) groups are generated with
$N_{i}=\lceil N/2^{(i+1)}\rceil$, for $i=1,2,\ldots,7$. Concatenation layer
reshapes the data to be a vector, from FM 7 to FC1. FC1=$512N_{7}^{2}$ and
FC2=$4096$[36].

The output of CNN-RP is an $N$-vector, which represents a connectivity or
controllability curve, denoted by $\hat{v}$. The mean-squared error between
the predicted curve $\hat{v}$ and the true curve $v$ is used as the loss
function:

$\mathcal{L}=\frac{1}{N}\sum_{i=1}^{N}||\hat{v}(i)-v(i)||\,,$ (4)

where $\hat{v}(i)$ and $v(i)$ represent the predicted and the true
connectivity or controllability values, respectively; $i$ is the total number
of nodes that have been removed from the network; $||\cdot||$ is the Euclidean
norm. The true values $v(i)$ are obtained by performing attack simulation. The
training process aims at adjusting the internal parameters, aiming at
minimizing $\mathcal{L}$.

####  II-B2 PATCHY-SAN and LFR-CNN

As shown in Fig. 1, PATCHY-SAN and LFR-CNN share the same LFR module, which
converts higher-dimensional network data to lower-dimensional representations.
This conversion is achieved by using a series of three operations: selection,
assembly, and normalization (SAN).

First, the $N$ network nodes are sorted according to their importance, which
can be quantified by certain node centrality measure such as node degree or
node betweenness. A total of $W$ most important nodes are first selected. For
each selected node, a receptive field of size $g$ is created based on its
neighboring information. If $N<W$, then all-zero receptive fields are added
for padding. Next, a breadth-first search is conducted to construct the
neighborhood field for each selected node. Finally, a normalization step
converts and normalizes the neighboring field for each selected node to an
embedded vector with a uniform length $gh$, where $h$ is the number of
attributes used for the neighboring nodes. The first element in the resultant
normalized vector represents the root node, followed by the neighboring nodes
sorted according to their centrality measures.

To this end, an $N$-node network represented by an $N^{2}$ adjacency matrix
has been represented by a $W\times(gh)$ matrix, where there are $W$ receptive
fields and each receptive field is presented by a $1\times gh$ vector. Since
$g\ll N$ and $h\ll N$, this procedure generates lower-dimensional learned
feature representations from higher-dimensional raw network data. Then, the
lower-dimensional representations are processed by CNN to predict the
robustness performances of the given networks.

For PATCHY-SAN, a shallow 1D-CNN structure is employed, while for LFR-CNN a
VGG-structured[51] 2D-CNN with 3 feature maps (FMs) is used. The numbers of
internal parameters to be adjusted during training are $5.1\times 10^{5}$ and
$6.0\times 10^{6}$ for PATCHY-SAN and LFR-CNN, respectively.

The same mean-squared error between the predicted curve $\hat{v}$ and the true
curve $v$ as shown in Eq. (4) is used as the loss function for both PATCHY-SAN
and LFR-CNN.

###  II-C Error Measures

Let ${\bf{v_{t}}}=\\{v_{t}(i)\\}_{i=0}^{N-1}$ and
${\bf{v_{p}}}=\\{v_{p}(i)\\}_{i=0}^{N-1}$ be the true and the predicted
robustness curves obtained by attack simulation, respectively. The prediction
error $\xi$ is calculated by

$\xi=\frac{1}{N}\sum_{i=0}^{N-1}{\xi(i)}\,,$ (5)

where $\xi(i)=|v_{t}(i)-v_{p}(i)|$, $i=0,1,...,N-1$. Given two prediction
errors obtained by two different robustness predictors, denoted by ${\xi}_{1}$
and ${\xi}_{2}$, if ${\xi}_{1}<{\xi}_{2}$ then the first predictor performs
better than the second.

##  III Spatial Pyramid Pooling

A CNN consists of convolutional layers and fully-connected layers, as shown in
Fig. 2. The convolutional layers, which work in a sliding-window manner, are
flexible with different input sizes, while the nature of the fully-connected
layers requires a predefined fixed size of input. Therefore, CNNs require a
fixed size for the input data, e.g., $224\times 224$. For image processing
tasks such as classification and object detection[51, 52, 53], cropping[54]
and warping[55], the images may be fit to the required fixed input size. When
complex network data are used as the input to CNNs, upsampling or subsampling
is suitable[36], since cropping and warping may discard or distort some
specific marginal regions of an image, while upsampling and subsampling cause
uniformly random information loss or distortion. However, resizing of network
data not only will change the true network size, but also will change the true
topology, by removing existing nodes or adding dummy nodes. But the resized
network data can be misleading, for example, when hub nodes are deleted.

On the other hand, the GNN-based approaches can effectively reduce the
information loss by extracting neighboring information from the important
nodes, as discussed in Subsection II-B2. The representation learning process
converts the input higher-dimensional data of any size to a regulated fixed-
sized lower-dimensional representation, and then passes it to a CNN. This
process significantly widen the application range of the robustness predictor
to different network sizes[46]. However, the GNN-based approaches are
significantly slower than the CNN-based approaches, where the representation
learning process is the most time-consuming part.

Embedding a spatial pyramid pooling (SPP)[47] layer into CNN, in between the
convolutional layers and fully-connected layers, brings some benefits: it
brings a buffer layer from the flexible convolutional layers to the fixed
fully-connected layers. SPP is developed from the canonical spatial pyramid
matching algorithm in computer vision[56, 57], which statistically counts the
feature distributions of images from multiple scales, such that better
recognition performances can be achieved. The spatial pyramid matching
algorithm sets a number of spatial bins, and then local features within each
individual spatial bin are captured statistically. The representation of the
whole image consists of local features from different spatial bins.

As an extension of the spatial pyramid matching algorithm, SPP uses max
pooling instead of statistical counting to local feature learning and
resizing. Given input images of different sizes, the convolution layers are
able to process all the information and then generate feature maps of
different sizes. The SPP layer then transforms these feature maps to fixed-
length representations.

Figure 3: The convolutional neural network structure with a spatial pyramid
pooling layer. The detailed structure of convolutional layers are shown in
Fig. 4.

As shown in Fig. 3, an $N\times N$ input image results in $L$
$N^{\prime}\times N^{\prime}$ feature maps, where $L$ is the number of filters
in the last convolutional layer. In the SPP layer, feature maps are divided
into 3 different levels of spatial bins, of sizes $1\times 1$, $2\times 2$,
and $4\times 4$, which are processed by max pooling with corresponding sizes.
Then, a representation vector of size $pL$ is generated as the output of the
SPP layer. Here, both $L$ and $p$ are pre-defined hyperparameters. As a
result, for the input image of any size, a fixed length $pL$-vector is
generated as the input to the fully-connected layers. In this paper, three
pyramid pooling levels are used, with sizes of $1\times 1$, $2\times 2$ and
$4\times 4$, respectively. It has been empirically verified that the
performance of the SPP layer is insensitive to different settings of the
pyramid bins[47].

Figure 4: CNN structure of SPP-CNN. The spatial pyramid pooling layer is
installed between the convolutional layers and fully-connected layers. Hard-
sigmoid is installed in the last fully-connected layer, while in other layers
ReLU is installed.

By installing such an SPP layer in CNN, an SPP-CNN is constructed for network
robustness prediction. Fig. 4 shows the structure of SPP-CNN, which consists
of 6 convolutional layers, 1 SPP layer, and 3 fully connected layers. This
structure is able to predict the robustness performances of networks with
hundreds to thousands of nodes. Specifically, $p=21$ represents the total
number of bins, and $L=256$ denotes the number of filters in the last
convolutional layer. The resultant representation has a fixed-length of
$21\times 256=5376$, which is also the fixed input size of the first fully-
connected layer (FC1), namely $L_{1}=pL=5376$.

TABLE I: Parameter setting of the convolutional layers in SPP-CNN. Group | Layer |  | Kernel
---
size
Stride |  | Output
---
channel
Group 1 | Conv7-64 | $7\times 7$ | 1 | 64
Max2 | $2\times 2$ | 2 | 64
Group 2 | Conv5-64 | $5\times 5$ | 1 | 64
Max2 | $2\times 2$ | 2 | 64
Group 3 | Conv3-128 | $3\times 3$ | 1 | 128
Max2 | $2\times 2$ | 2 | 128
Group 4 | Conv3-128 | $3\times 3$ | 1 | 128
Max2 | $2\times 2$ | 2 | 128
Group 5 | Conv3-256 | $3\times 3$ | 1 | 256
Max2 | $2\times 2$ | 2 | 256
Group 6 | Conv3-256 | $3\times 3$ | 1 | 256
Max2 | $2\times 2$ | 2 | 256

The parameter setting of the convolutional layers is shown in Table I. Source
codes of this work are available for the
public111https://fylou.github.io/sourcecode.html.

##  IV Experimental Studies

In this section, the proposed SPP-CNN is experimentally tested and compared
with CNN-RP[36], PATCHY-SAN[48], and LFR-CNN[46]. Network connectivity
robustness under maximum-degree node attacks and controllability robustness
under random node attacks are predicted. Other network robustness under
different attack strategies can be studied in the same manner. Both directed
and undirected, and synthetic and real-world networks are simulated. All
experiments are performed on a PC with GeForce RTX 3080 GPU, which has memory
(RAM) 10 GB with running the Ubuntu 20.04.3 LTS Operating System.

This section is organized as follows. Subsection IV-A introduces the
experimental settings. General comparison of robustness prediction
performances are presented in Subsection IV-B, which demonstrates that SPP-CNN
performs as well as other state-of-the-art GNN-based robustness predictors
when the test data drawn from the same distribution are used for training. The
run-time comparison presented in Subsection IV-C demonstrates that SPP-CNN is
significantly faster than the GNN-based predictors. Then, the generlizability
of the predictors is verified in Subsections IV-D and IV-E, where the test
datasets with unseen synthetic and real-world networks are tested. Finally,
the pros and cons of different predictors are discussed in Subsection IV-F.

###  IV-A Experimental Settings

Nine representative synthetic network models are used for simulation,
including Barabási–Albert (BA) scale-free[58, 59], extreme homogeneous
(EH)[60], Erdös-Rényi (ER) random-graph[61], q-snapback (QS)[62], random
hexagon (RH)[63], random triangle (RT)[63], generic scale-free (SF)[64],
Newman–Watts small-world (SW-NW)[65], and Watts–Strogatz small-world (SW-
WS)[25] network models.

Specifically, the generation of BA networks is based on preferential
attachment[58]; SF networks are generated using predefined weights, namely the
probability of connecting two nodes $i$ and $j$ is proportional to their
weights $w_{i}$ and $w_{j}$, where $w_{i}=(i+\theta)^{-\sigma}$ for any node
$i$, parameters $\sigma\in[0,1)$ and $\theta\ll N$; EH networks are generated
by performing random edge rectifications onto ER networks, such that the
degree distribution of EH is extremely homogeneous[60]; RT and RH consist of
random triangles and hexagons, respectively[63]. These models, BA, EH, ER, RH,
RT, SF, generate undirected instances by default, while directed instances are
generated by assigning random directions onto the edges.

QS consists of a directed backbone chain and multiple snapback edges[62]; SW
starts from an $N$-node directed loop having $K$ ($K=2$ here) connected
nearest-neighbors; shortcuts are randomly added without removing any existing
edges in SW-NW[65], while rewiring operations are performed in SW-WS[25].
Thus, QS, SW-NW, and SW-WS generate directed network instances by default,
while undirected instances are generated by removing the edge directions.

The average degree of each network instance is assigned reasonably at random.
For directed networks, the average degree range is set as $\langle
k\rangle\in[2.5,5]$ for the two SW models, $\langle k\rangle\in[2,4]$ for RH,
$\langle k\rangle\in[1.5,3]$ for RT, and for the other models, $\langle
k\rangle\in[3,6]$. For undirected networks, the average degree range is set to
double, namely, the range is set as $\langle k\rangle\in[5,10]$ for the two SW
models, $\langle k\rangle\in[4,8]$ for RH, $\langle k\rangle\in[3,6]$ for RT,
while for the other models, $\langle k\rangle\in[6,12]$.

Define three sets of synthetic network models, $S_{1}=${BA, EH, ER, QS, RH,
RT, SF, SW-NW, SW-WS}, $S_{2}=${ER, QS, SF, SW-NW}, and $S_{3}=${BA, EH, RH,
RT, SW-WS}. Three network size ranges are set as $N_{a}\in[700,1300]$,
$N_{b}\in[300,700]$, $N_{c}\in[1300,1700]$. For each synthetic model, 1000
network instances are randomly generated as the training data, and 100
instances as the test data. Since the structural connectivity and
controllability are independent of the edge weights, only unweighted networks
are simulated here.

For the LFR module in both PATCHY-SAN and LFR-CNN, the number of features is
set as $h=2$, where node degree and clustering coefficient are employed; the
size of receptive field is set as $g=10$, both are the same as that in[48,
46].

###  IV-B Comparison of Prediction Performances

Both training and test data are drawn from the same sample space, namely each
network instance is randomly generated from any of the 9 synthetic models in
$S_{1}$, with a network size randomly picked as $N_{a}\in[700,1300]$.

TABLE II: Comparison of average prediction errors among SPP-CNN, CNN-RP, PATCHY-SAN, and LFR-CNN. Signs in parentheses denote the Kruskal-Wallis H-test [66] results. A ‘$+$’ sign denotes that SPP-CNN is superior to the other methods with smaller errors; a ‘$\approx$’ sign denotes no significant difference; while a ‘$-$’ sign denotes that SPP-CNN is inferior to the other methods with greater errors. | BA | EH | ER | QS | RH | RT | SF |  | SW-
---
NW
| SW-
---
WS
Directed |  Connectivity Robustness Eq. (1) | SPP-CNN | 0.038 | 0.057 | 0.032 | 0.067 | 0.056 | 0.105 | 0.017 | 0.030 | 0.031
CNN-RP | 0.146($+$) | 0.138($+$) | 0.129($+$) | 0.162($+$) | 0.121($+$) | 0.118($\approx$) | 0.068($+$) | 0.094($+$) | 0.099($+$)
PATCHY-SAN | 0.040($+$) | 0.032($-$) | 0.024($-$) | 0.027($-$) | 0.028($-$) | 0.031($-$) | 0.029($+$) | 0.027($\approx$) | 0.024($-$)
LFR-CNN | 0.041($+$) | 0.078($+$) | 0.039($\approx$) | 0.076($\approx$) | 0.023($-$) | 0.031($-$) | 0.018($\approx$) | 0.029($\approx$) | 0.027($\approx$)
Controllability Robustness Eq. (3) | SPP-CNN | 0.031 | 0.025 | 0.025 | 0.042 | 0.021 | 0.030 | 0.025 | 0.028 | 0.025
CNN-RP | 0.092($+$) | 0.040($+$) | 0.062($+$) | 0.104($+$) | 0.051($+$) | 0.060($+$) | 0.134($+$) | 0.054($+$) | 0.059($+$)
PATCHY-SAN | 0.032($\approx$) | 0.028($\approx$) | 0.026($\approx$) | 0.030($-$) | 0.019($\approx$) | 0.024($\approx$) | 0.049($+$) | 0.024($\approx$) | 0.022($\approx$)
LFR-CNN | 0.024($\approx$) | 0.013($-$) | 0.018($-$) | 0.015($-$) | 0.015($-$) | 0.019($-$) | 0.039($+$) | 0.015($-$) | 0.015($-$)
Undirected |  Connectivity Robustness Eq .(1) | SPP-CNN | 0.023 | 0.070 | 0.025 | 0.026 | 0.028 | 0.047 | 0.016 | 0.029 | 0.028
CNN-RP | 0.055($+$) | 0.188($+$) | 0.121($+$) | 0.135($+$) | 0.121($+$) | 0.100($+$) | 0.020($\approx$) | 0.149($+$) | 0.140($+$)
PATCHY-SAN | 0.030($+$) | 0.032($-$) | 0.022($-$) | 0.024($\approx$) | 0.022($-$) | 0.026($-$) | 0.025($+$) | 0.025($\approx$) | 0.020($-$)
LFR-CNN | 0.026($\approx$) | 0.066($\approx$) | 0.025($\approx$) | 0.027($\approx$) | 0.019($-$) | 0.022($-$) | 0.016($\approx$) | 0.023($\approx$) | 0.020($-$)
Controllability Robustness Eq. (3) | SPP-CNN | 0.027 | 0.013 | 0.016 | 0.014 | 0.018 | 0.018 | 0.026 | 0.016 | 0.017
CNN-RP | 0.060($+$) | 0.037($+$) | 0.031($+$) | 0.035($+$) | 0.039($+$) | 0.039($+$) | 0.085($+$) | 0.045($+$) | 0.046($+$)
PATCHY-SAN | 0.028($\approx$) | 0.015($\approx$) | 0.020($\approx$) | 0.017($+$) | 0.021($+$) | 0.020($\approx$) | 0.040($+$) | 0.016($\approx$) | 0.016($\approx$)
LFR-CNN | 0.037($+$) | 0.016($+$) | 0.017($\approx$) | 0.017($+$) | 0.018($\approx$) | 0.020($\approx$) | 0.060($+$) | 0.018($+$) | 0.019($\approx$)

Table II shows the average prediction errors obtained by SPP-CNN, CNN-RP,
PATCHY-SAN, and LFR-CNN. Boxplots of the prediction errors are presented in
Figs. S1–S4 of the Supplementary Information
(SI)222https://fylou.github.io/pdf/sppsi.pdf due to space limitation here.
Network robustness in terms of connectivity and controllability is predicted,
and the prediction errors are calculated using Eq. (5). The errors are
averaged from 100 independent runs for each synthetic model. A total of
$2\times 2\times 9=36$ comparisons are performed between SPP-CNN and each of
CNN-RP, PATCHY-SAN, and LFR-CNN, namely, directed and undirected networks, two
robustness measures, and 9 synthetic network models. The Kruskal-Wallis
H-test[66] results are shown with the corresponding prediction error values,
where a ‘$+$’ sign denotes that SPP-CNN performs significantly better than the
other methods with smaller errors; a ‘$\approx$’ sign denotes no significant
difference between SPP-CNN and the other methods; while a ‘$-$’ sign denotes
that SPP-CNN performs significantly worse than the other methods with greater
errors.

SPP-CNN performs significantly better than CNN-RP in 34 cases, and for the
rest 2 cases, there is no significant difference between them. As for PATCHY-
SAN and LFR-CNN, the same numbers of superiors and inferiors are obtained,
showing that SPP-CNN significantly outperforms PATCHY-SAN (or LFR-CNN) in 8
cases; SPP-CNN performs significantly worse than PATCHY-SAN (or LFR-CNN) in 12
cases; and they perform statistically equally in the rest 16 cases.

In a nutshell, it is clear that SPP-CNN performs equivalently to or marginally
worse than PATCHY-SAN and LFR-CNN, but significantly better than CNN-RP.

###  IV-C Run Time Comparison

The powerful GNN-based representation learning part of PATCHY-SAN and LFR-CNN
significantly enhances the precision of robustness prediction, which however
is the most time-consuming part. In contrast, SPP-CNN does not involve any
GNN-based operation for feature learning.

(a) $N_{a}\in[700,1300]$

(b) $N_{b}\in[300,700]$

Figure 5: Run time comparison of SPP-CNN, CNN-RP, PATCHY-SAN, LFR-CNN, and
attack simulation (SIM): (a) for network size $N_{a}\in[700,1300]$; and (b)
for network size $N_{b}\in[300,700]$

Figure 5 shows the run time comparison of SPP-CNN, CNN-RP, PATCHY-SAN, LFR-
CNN, and attack simulation (SIM). Fig. 5 (a) presents the run time when the
network size is $N_{a}\in[700,1300]$, of which the average network size is
1000; for Fig. 5 (b), the network size is set as $N_{b}\in[700,1300]$, of
which the average network size is 500.

For each subplot in Fig. 5, it is clear that CNN-RP is the fastest, followed
by SPP-CNN. Clearly, PATCHY-SAN and LFR-CNN are significantly slower than CNN-
RP and SPP-CNN, but much faster than attack simulations. For PATCHY-SAN and
LFR-CNN, the representation learning takes most of the run time.

Comparing Figs. 5 (a) and (b), when the average network size is doubled from
subplot (b) to subplot (a), the time consumption of SPP-CNN, CNN-RP, PATCHY-
SAN, LFR-CNN, and SIM is increased by 1.61, 1,34, 4.78, 4.81, and 8.21 times,
respectively. It is clear that the time consumption of CNN-RP and SPP-CNN
increase significantly slower than the GNN-based predictors do.

The run time difference between CNN-RP and SPP-CNN is negligible, while SPP-
CNN significantly outperforms CNN-RP, as can be seen from Table II, which also
shows that the performance different between SPP-CNN and the GNN-based
predictors is marginal, while the time complexity of SPP-CNN is significantly
lower than PATCHY-SAN and LFR-CNN, as shown in Fig. 5.

###  IV-D Comparison of Generalizability

The generalizability of robustness predictors is tested from two aspects: 1)
using the network models in $S_{1}$, two sets of test instances with unseen
network sizes (UNS) are tested, namely, the network size of training data is
drawn from $N_{a}\in[700,1300]$, while the test data are from
$N_{b}\in[300,700]$ and $N_{c}\in[1300,1700]$. 2) Given network size drawn
from $N_{a}\in[700,1300]$, training instances are generated from the network
models in $S_{2}$, while the test instances are from $S_{3}$. Since $S_{2}$
and $S_{3}$ are two mutually exclusive subsets of $S_{1}$, $S_{3}$ is called
the test data of unseen network topology (UNT). Note that although $S_{2}$ and
$S_{3}$ are mutually exclusive, there are some similarities between the models
in the two sets, e.g., SW-NW $\in S_{2}$ and SW-WS $\in S_{3}$.

TABLE III: Comparison of significant difference between SPP-CNN and each of CNN-RP, PATCHY-SAN, and LFR-CNN.  Significant Difference | ($+$) | ($-$) | ($\approx$)
---|---|---|---
UNS | SPP-CNN vs CNN-RP | 266 | 12 | 10
SPP-CNN vs PATCHY-SAN | 169 | 78 | 41
SPP-CNN vs LFR-CNN | 124 | 108 | 56
UNT | SPP-CNN vs CNN-RP | 11 | 2 | 7
SPP-CNN vs PATCHY-SAN | 15 | 3 | 2
SPP-CNN vs LFR-CNN | 14 | 3 | 3

Table III summarizes the comparison of the significant differences between
SPP-CNN and each of CNN-RP, PATCHY-SAN, and LFR-CNN. The prediction errors for
UNS and UNT are presented in Figs. S5–S8 and S13 of SI, respectively. The
barcharts of the numbers of significant performance differences for UNS and
UNT are shown in Figs. S9–S12 and S14 of SI, respectively. For UNS, there are
$2\times 2\times 9\times 8=288$ neck-to-neck comparisons between SPP-CNN and
each of CNN-RP, PATCHY-SAN, and LFR-CNN, namely, directed and undirected,
connectivity and controllability robustness, 9 synthetic models in $S_{1}$,
and 8 UNS sections in $N_{b}$ and $N_{c}$. For UNT, there are $2\times 2\times
5=20$ comparisons, namely, directed and undirected, connectivity and
controllability robustness, and 5 synthetic models in $S_{3}$.

Only when testing on UNS, SPP-CNN outperforms LFR-CNN marginally, but for all
the rest comparisons, SPP-CNN gains more superiors than inferiors. This
indicates the excellent generalizability of SPP-CNN.

###  IV-E Predicting Robustness for Real-world Networks

The prediction performance is studied by two experiments. The first experiment
investigates the performances of SPP-CNN, PATCHY-SAN, and LFR-CNN on
predicting the robustness of the tested real-world networks. The second
experiment uses mixed sets of both synthetic and real-world networks as both
training and test data. Define $S_{r}=${Reddit-
Multi-12K333https://networkrepository.com/REDDIT-MULTI-12K.php Networks},
where there are 1000 real-world networks selected randomly, of which the
network size ranges as $N_{r}\in[300,700]$.

(a) Real-world networks

(b) Real-world networks and $S_{2}$

(c) $S_{2}$ only

Figure 6: Prediction error comparison in the form of boxplot: (a) both
training and test data are real-world networks; (b) for SPP-CNN, the training
and test data include both real-world networks $S_{r}$ and synthetic models
$S_{2}$; (c) the benchmark performance of SPP-CNN when only $S_{2}$ is used as
both training and test data.

####  IV-E1 Real-world Networks Only

Figure 6 (a) shows the prediction errors obtained by SPP-CNN, PATCHY-SAN, and
LFR-CNN, where the training data set is $S_{r}$ while the test set constitutes
of other randomly picked 100 networks from Reddit-Multi-12K. The boxplot in
Fig. 6 (a) shows that SPP-CNN outperforms both PATCHY-SAN and LFR-CNN, with
statistic significance, using the Kruskal-Wallis test[66].

####  IV-E2 Real-world and Synthetic Networks

To clear up the doubt that the excellent performance of SPP-CNN on predicting
real-world networks is random or due to overfitting, $S_{r}$ and $S_{2}$ are
mixed together in experiments. Thus, the trained SPP-CNN is neither
specialized for synthetic models nor for real-world networks.

As shown in Fig. 6 (b), the prediction error boxplot obtained by SPP-CNN on
real-world networks is similar to that in Fig. 6 (a). This clears up the doubt
of overfitting. Also, the prediction errors obtained by SPP-CNN for synthetic
networks are similar to that in Fig. 6 (c), where a SPP-CNN is specifically
trained for the 4 synthetic models.

In a nutshell, when real-world and synthetic networks are mixed and used as
both training and test data, SPP-CNN can perform robustness prediction as
excellent as the cases where only real-world or only synthetic networks are
used. This also implies the excellent generalizability of SPP-CNN.

###  IV-F Discussions

####  IV-F1 Overall Performance

TABLE IV: A summary of the performances of SPP-CNN when different datasets (including $S_{1}$, $S_{2}$, $S_{3}$, and $S_{r}$) and network sizes (including $N_{a}$, $N_{b}$, and $N_{c}$) are used. A ‘$\approx$’ sign represents that the numbers of superiors and inferiors obtained by SPP-CNN are similar to that obtained by the compared method; while a ‘$\succ$’ sign means that SPP-CNN obtains clearly more superiors than inferiors in the corresponding comparison.  | Training data
---
$S_{1}$ ($N_{a}$) |  $S_{1}$ ($N_{a}$) |  $S_{2}$ ($N_{a}$) | $S_{r}$ |  $S_{r}$+$S_{2}$
| Test data
---
$S_{1}$ ($N_{a}$) |  $S_{1}$ ($N_{b}$ and $N_{c}$) |  $S_{3}$ ($N_{a}$) | $S_{r}$ |  $S_{r}$+$S_{2}$
| Performance
---
of SPP-CNN
|  $\approx$ PATCHY-SAN
---
$\approx$ LFR-CNN
$\succ$CNN-RP
|  $\succ$ PATCHY-SAN
---
$\approx$ LFR-CNN
$\succ$ CNN-RP
|  $\succ$ PATCHY-SAN
---
$\succ$ LFR-CNN
$\succ$ CNN-RP
|  $\succ$ PATCHY-SAN
---
$\succ$ LFR-CNN
$\succ$ CNN-RP
| as good as when $S_{r}$
---
and $S_{2}$ are trained
and tested separately
Figure 7: Overall performances of SPP-CNN, CNN-RP, PATCHY-SAN, and LFR-CNN.

Table IV shows the overall performances of SPP-CNN compared to CNN-RP, PATCHY-
SAN, and LFR-CNN. The results are summarized from the results presented in
Subsections IV-B, IV-D, and IV-E. When the test data and training data are
drawn from the same sample space, SPP-CNN performs as good as the GNN-based
predictors. However, if the test data are drawn from different sample spaces,
SPP-CNN consistently outperforms the other predictors. Here, different sample
spaces mean that either UNS or UNT is set. Also, SPP-CNN outperforms the GNN-
based predictors on predicting the robustness of real-world networks.

Considering both generalizability and run time, Fig. 7 shows the performance
comparison in two-dimensional coordinate plots. Clearly, SPP-CNN and CNN-RP
are faster, while SPP-CNN meanwhile possesses the best generalizability.

####  IV-F2 Information Loss

Given an $N\times N$ adjacency matrix as input, CNN-RP requires a fixed input
size $W\times W$, and thus downsampling or upsampling is necessary. If $N>W$,
then $N-W$ columns and rows are needed to be randomly deleted from the
adjacency matrix in order to fit the input size. If $N<W$, then $W-N$ empty
columns and rows are needed to be randomly added for padding. These deletion
or addition operations may significantly distort the original network
topology, and thus degenerate the subsequent robustness prediction
performance.

For PATCHY-SAN and LFR-CNN, as discussed in Subsection II-B2, if $N>W$, then
only the neighboring fields of the $W$ most important nodes are selected to
construct the receptive fields. While if $N<W$ then $W-N$ dummy nodes are
generated. For CNN-RP, there is always a proportion of
$\delta=\frac{|N-W|}{N}$ information distortion, while for PATCHY-SAN and LFR-
CNN, this information distortion is significantly lower than $\sigma$, since
the neighboring fields of the $W$ most important nodes are always included,
but other unimportant nodes may also be compressed into the neighboring
fields.

Finally, for SPP-CNN, there is always no information loss or distortion from
the input, since networks of any sizes are able to be input without the need
of resizing. Moreover, local features are better captured by the SPP layer.

##  V Conclusions

Measuring network robustness by attack simulations is time-consuming, while
deep neural networks provide a more cost-effective technique for robustness
prediction, which can replace the iterative attack simulations, at least
partially. The CNN-based framework CNN-RP can predict network robustness fast,
but is inefficient when the size of the concerned network is different from
the fixed input size of the CNN. On the other hand, PATCHY-SAN and LFR-CNN,
which incorporate both GNN and CNN, are able to predict network robustness of
different sizes and various topologies with low prediction errors. However,
these GNN-based robustness predictors perform significantly slower than CNN-
RP, due to the powerful but time-consuming feature learning module installed.

In this paper, to overcome the mismatch issue between the various network
sizes and the somewhat fixed input size of the CNN, a spatial pyramid pooling
layer is installed between the convolutional and fully-connected layers of the
CNN, yielding the new SPP-CNN framework.

Extensive experiments are carried out by comparing SPP-CNN with CNN-RP,
PATCHY-SAN, and LFR-CNN. Three sets of synthetic (directed and undirected)
networks with three different network size ranges, together with one set of
real-world networks, are simulated. Detailed comparisons are performed, where
both training and test data are drawn from the same sample space.
Generalization abilities of the predictors are also examined, where the test
data are drawn from different sample spaces, other than the training data
space. The prediction performances on real-world networks are tested from two
aspects: 1) real-world networks are trained and tested separately, and 2)
real-world networks are mixed with synthetic networks. All the experimental
results demonstrate the excellent performances of SPP-CNN: 1) SPP-CNN achieves
significantly better prediction performances than CNN-RP with similar
performances as PATCHY-SAN and LFR-CNN, when tboth training and test data are
drawn from the same sample space. 2) When the sample spaces of training and
test data are different, SPP-CNN shows stronger generalizability than the
other three predictors. 3) SPP-CNN performs prediction significantly faster
than PATCHY-SAN and LFR-CNN.

Overall, the proposed SPP-CNN framework lifts the network robustness
prediction to a higher level, so that the prediction tasks can be accomplished
faster and more precise. This investigation reveals that the great potential
of deep neural networks can be further explored for broader applications in
the future.

## References

  * [1] A.-L. Barabási, _Network Science_. Cambridge University Press, 2016.
  * [2] M. E. Newman, _Networks: An Introduction_. Oxford University Press, 2010.
  * [3] G. Chen, X. Wang, and X. Li, _Fundamentals of Complex Networks: Models, Structures and Dynamics_ , 2nd ed. John Wiley & Sons, 2014.
  * [4] C. M. Schneider, A. A. Moreira, J. S. Andrade, S. Havlin, and H. J. Herrmann, “Mitigation of malicious attacks on networks,” _Proceedings of the National Academy of Sciences_ , vol. 108, no. 10, pp. 3838–3841, 2011.
  * [5] W. Ellens and R. E. Kooij, “Graph measures and network robustness,” _arXiv preprint arXiv:1311.5064_ , 2013.
  * [6] S. Freitas, D. Yang, S. Kumar, H. Tong, and D. H. Chau, “Graph vulnerability and robustness: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , 2022, doi:10.1109/TKDE.2022.3163672 (online published).
  * [7] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex networks,” _Nature_ , vol. 473, no. 7346, pp. 167–173, 2011.
  * [8] Z. Z. Yuan, C. Zhao, Z. R. Di, W.-X. Wang, and Y.-C. Lai, “Exact controllability of complex networks,” _Nature Communications_ , vol. 4, p. 2447, 2013.
  * [9] M. Pósfai, Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Effect of correlations on network controllability,” _Scientific Reports_ , vol. 3, p. 1067, 2013.
  * [10] G. Menichetti, L. Dall’Asta, and G. Bianconi, “Network controllability is determined by the density of low in-degree and out-degree nodes,” _Physical Review Letters_ , vol. 113, no. 7, p. 078701, 2014.
  * [11] L. Wang, X. Wang, G. Chen, and W. K. S. Tang, “Controllability of networked MIMO systems,” _Automatica_ , vol. 69, pp. 405–409, 2016.
  * [12] L. Wang, X. Wang, and G. Chen, “Controllability of networked higher-dimensional systems with one-dimensional communication channels,” _Royal Society Philosophical Transactions A_ , vol. 375, no. 2088, p. 20160215, 2017.
  * [13] L. Xiang, F. Chen, W. Ren, and G. Chen, “Advances in network controllability,” _IEEE Circuits and Systems Magazine_ , vol. 19, no. 2, pp. 8–32, 2019.
  * [14] J.-N. Wu, X. Li, and G. Chen, “Controllability of deep-coupling dynamical networks,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 67, no. 12, pp. 5211–5222, 2020.
  * [15] Y. Lu, Y. Zhao, F. Sun, and R. Liang, “Measuring and improving communication robustness of networks,” _IEEE Communications Letters_ , vol. 23, no. 12, pp. 2168–2171, 2019.
  * [16] B. Mburano, W. Si, and W. X. Zheng, “A comparative study on the variants of r metric for network robustness,” in _International Symposium on Networks, Computers and Communications (ISNCC)_. IEEE, 2021, pp. 1–6.
  * [17] P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, “Attack vulnerability of complex networks,” _Physical Review E_ , vol. 65, no. 5, p. 056109, 2002\.
  * [18] B. Shargel, H. Sayama, I. R. Epstein, and Y. Bar-Yam, “Optimization of robustness and connectivity in complex networks,” _Physical Review Letters_ , vol. 90, no. 6, p. 068701, 2003.
  * [19] R. Cohen and S. Havlin, _Complex Networks: Structure, Robustness and Function_. Cambridge university press, 2010\.
  * [20] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Control centrality and hierarchical structure in complex networks,” _PLoS One_ , vol. 7, no. 9, p. e44459, 2012.
  * [21] A. Bashan, Y. Berezin, S. Buldyrev, and S. Havlin, “The extreme vulnerability of interdependent spatially embedded networks,” _Nature Physics_ , vol. 9, pp. 667–672, 2013.
  * [22] H. Chan and L. Akoglu, “Optimizing network robustness by edge rewiring: A general framework,” _Data Mining and Knowledge Discovery_ , vol. 30, no. 5, pp. 1395–1425, 2016.
  * [23] J. Liu, M. Zhou, S. Wang, and P. Liu, “A comparative study of network robustness measures,” _Frontiers of Computer Science_ , vol. 11, no. 4, pp. 568–584, 2017.
  * [24] L. C. Freeman, “A set of measures of centrality based on betweenness,” _Sociometry_ , pp. 35–41, 1977.
  * [25] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [26] J. Wu, B. Mauricio, Y.-J. Tan, and H.-Z. Deng, “Natural connectivity of complex networks,” _Chinese Physics Letters_ , vol. 27, no. 7, p. 078902, 2010.
  * [27] M. Fiedler, “Algebraic onnectivity of graphs,” _Czechoslovak Mathematical Journal_ , vol. 23, no. 2, pp. 298–305, 1973.
  * [28] D. J. Klein and M. Randić, “Resistance distance,” _Journal of Mathematical Chemistry_ , vol. 12, no. 1, pp. 81–95, 1993.
  * [29] A. Gavili and X.-P. Zhang, “On the shift operator, graph frequency, and optimal filtering in graph signal processing,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 23, pp. 6303–6318, 2017.
  * [30] K. Yamashita, Y. Yasuda, R. Nakamura, and H. Ohsaki, “On the predictability of network robustness from spectral measures,” in _2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC)_ , vol. 2. IEEE, 2019, pp. 24–29.
  * [31] A. Zeng and W. Liu, “Enhancing network robustness against malicious attacks,” _Physical Review E_ , vol. 85, no. 6, p. 066130, 2012.
  * [32] C. M. Schneider, N. Yazdani, N. A. Araújo, S. Havlin, and H. J. Herrmann, “Towards designing robust coupled networks,” _Scientific Reports_ , vol. 3, no. 1, pp. 1–7, 2013.
  * [33] Y. Lou, S. Xie, and G. Chen, “Searching better rewiring strategies and objective functions for stronger controllability robustness,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 68, no. 6, pp. 2112–2116, 2021.
  * [34] S. Wang, J. Liu, and Y. Jin, “A computationally efficient evolutionary algorithm for multiobjective network robustness optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 25, no. 3, pp. 419–432, 2021\.
  * [35] Y. Lou, L. Wang, S. Xie, and G. Chen, “Approximating the controllability robustness of directed random-graph networks against random edge-removal attacks,” _International Journal of Control Automation and Systems_ , 2022\.
  * [36] Y. Lou, Y. He, L. Wang, and G. Chen, “Predicting network controllability robustness: A convolutional neural network approach,” _IEEE Transactions on Cybernetics_ , vol. 52, no. 5, pp. 4052–4063, 2022.
  * [37] P. Sun, R. E. Kooij, Z. He, and P. Van Mieghem, “Quantifying the robustness of network controllability,” in _International Conference on System Reliability and Safety (ICSRS)_. IEEE, 2019, pp. 66–76.
  * [38] P. Sun, R. E. Kooij, and P. Van Mieghem, “Reachability-based robustness of controllability in sparse communication networks,” _IEEE Transactions on Network and Service Management_ , vol. 18, no. 3, pp. 2764–2775, 2021.
  * [39] A. Dhiman, P. Sun, and R. Kooij, “Using machine learning to quantify the robustness of network controllability,” in _International Conference on Machine Learning for Networking_. Springer, 2021, pp. 19–39.
  * [40] C. Fan, L. Zeng, Y. Sun, and Y.-Y. Liu, “Finding key players in complex networks through deep reinforcement learning,” _Nature Machine Intelligence_ , vol. 2, pp. 317–324, 2020.
  * [41] M. Grassia, M. De Domenico, and G. Mangioni, “Machine learning dismantling and early-warning signals of disintegration in complex systems,” _Nature Communications_ , vol. 12, no. 5190, 2021.
  * [42] J. Schmidhuber, “Deep learning in neural networks: An overview,” _Neural Networks_ , vol. 61, pp. 85–117, 2015.
  * [43] Y. Lou, Y. He, L. Wang, K. F. Tsang, and G. Chen, “Knowledge-based prediction of network controllability robustness,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2021, doi:10.1109/TNNLS.2021.3071367 (online published).
  * [44] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [45] W. L. Hamilton, “Graph representation learning,” _Synthesis Lectures on Artifical Intelligence and Machine Learning_ , vol. 14, no. 3, pp. 1–159, 2020\.
  * [46] Y. Lou, R. Wu, J. Li, L. Wang, X. Li, and G. Chen, “A learning convolutional neural network approach for network robustness prediction,” _arXiv preprint arXiv:2203.10552_ , 2022.
  * [47] K. He, X. Zhang, S. Ren, and J. Sun, “Spatial pyramid pooling in deep convolutional networks for visual recognition,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 37, no. 9, pp. 1904–1916, 2015\.
  * [48] M. Niepert, M. Ahmed, and K. Kutzkov, “Learning convolutional neural networks for graphs,” in _International Conference on Machine Learning (ICML)_ , 2016, pp. 2014–2023.
  * [49] C.-T. Chen, _Linear System Theory and Design_ , 3rd ed. Oxford University Press, 1998.
  * [50] Y. Lou, R. Wu, J. Li, L. Wang, and G. Chen, “A convolutional neural network approach to predicting network connectedness robustness,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 4, pp. 3209–3219, 2021.
  * [51] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv Preprint: 1409.1556_ , 2014.
  * [52] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 1–9.
  * [53] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 770–778.
  * [54] M. D. Zeiler and R. Fergus, “Visualizing and understanding convolutional networks,” in _European Conference on Computer Vision_. Springer, 2014, pp. 818–833.
  * [55] R. Girshick, J. Donahue, T. Darrell, and J. Malik, “Rich feature hierarchies for accurate object detection and semantic segmentation,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2014, pp. 580–587.
  * [56] K. Grauman and T. Darrell, “The pyramid match kernel: Discriminative classification with sets of image features,” in _IEEE International Conference on Computer Vision (ICCV)_ , vol. 2. IEEE, 2005, pp. 1458–1465.
  * [57] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , vol. 2. IEEE, 2006, pp. 2169–2178.
  * [58] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” _Science_ , vol. 286, no. 5439, pp. 509–512, 1999.
  * [59] A.-L. Barabási, “Scale-free networks: A decade and beyond,” _Science_ , vol. 325, no. 5939, pp. 412–413, 2009.
  * [60] Y. Lou, L. Wang, K.-F. Tsang, and G. Chen, “Towards optimal robustness of network controllability: An empirical necessary condition,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 67, no. 9, pp. 3163–3174, 2020.
  * [61] P. Erdös and A. Rényi, “On the strength of connectedness of a random graph,” _Acta Mathematica Hungarica_ , vol. 12, no. 1-2, pp. 261–267, 1964\.
  * [62] Y. Lou, L. Wang, and G. Chen, “Toward stronger robustness of network controllability: A snapback network model,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 65, no. 9, pp. 2983–2991, 2018\.
  * [63] Y. Lou, D. Yang, L. Wang, C. Tang, and G. Chen, “Controllability robustness of henneberg-growth complex networks,” _IEEE Access_ , vol. 10, pp. 5103–5114, 2022.
  * [64] K.-I. Goh, B. Kahng, and D. Kim, “Universal behavior of load distribution in scale-free networks,” _Physical Review Letters_ , vol. 87, no. 27, p. 278701, 2001.
  * [65] M. E. Newman and D. J. Watts, “Renormalization group analysis of the small-world network model,” _Physics Letters A_ , vol. 263, no. 4-6, pp. 341–346, 1999.
  * [66] W. H. Kruskal and W. A. Wallis, “Use of ranks in one-criterion variance analysis,” _Journal of the American statistical Association_ , vol. 47, no. 260, pp. 583–621, 1952.

See pages 1- of sppsi.pdf


# Unsupervised collaborative learning using privileged information

Yohan Foucade
Université Sorbonne Paris Nord, CNRS, Institut Galilée
Laboratoire d’Informatique de Paris Nord UMR 7030, F-93430, Villetaneuse,
France
<EMAIL_ADDRESS>Younès Bennani
Université Sorbonne Paris Nord, CNRS, Institut Galilée
Laboratoire d’Informatique de Paris Nord UMR 7030, F-93430, Villetaneuse,
France
<EMAIL_ADDRESS>
###### Abstract

In the collaborative clustering framework, the hope is that by combining
several clustering solutions, each one with its own bias and imperfections,
one will get a better overall solution. The goal is that each local
computation, quite possibly applied to distinct data sets, benefits from the
work done by the other collaborators. This article is dedicated to
collaborative clustering based on the Learning Using Privileged Information
paradigm. Local algorithms weight incoming information at the level of each
observation, depending on the confidence level of the classification of that
observation. A comparison between our algorithm and state of the art
implementations shows improvement of the collaboration process using the
proposed approach.

_K_ eywords Unsupervised learning $\cdot$ Learning from learners $\cdot$
Collaborative Clustering $\cdot$ Distributed learning $\cdot$ Federated
learning.

##  1 Introduction

Cluster analysis is a widely used technique in data analytics. Its goal is the
organization of a collection of patterns into homogenous (small intra-group
variability) and distinct (large inter-group variability) clusters. There is a
large variety of methods for clustering and most require all the data to be
available on the same place and at the same time [1]. However, technical,
legal, confidentiality or computational performance reasons might prevent us
from gathering the data or exchanging sensitive information.

Our work is based on an advanced learning paradigm proposed by Vapnik et al.
called Learning Using Privileged Information (LUPI) [2, 3]. In addition to
examples, learners can be provided with hidden information that exists in the
form of explanations, results, or comparisons, etc. The important question
which Vapnik asks in the supervised case is: can the generalization
performance be improved using the privileged information? Vapnik also showed
this is true in the case of SVM.

The idea of LUPI is the following: suppose we want to establish a decision
rule to determine a label based on certain characteristics $X$, but during the
learning phase, in addition to $X$, we also receive additional information,
referred to as "Privileged Information" $X^{*}$ which will not be available
during the test phase. In such a case, how can we use $X^{*}$ to improve
learning? In this article, we propose a new approach based on the LUPI
paradigm for collaborative clustering based on knowledge sharing among a set
of learners.

In collaborative clustering [4, 5], we assume that we have a dataset
distributed among different nodes of a network (also called sites, or
experts). The goal of each expert is to obtain a clustering of its local data
using findings of its remote counterparts without exchanging the data
themselves. This is often done in two phases. First, a clustering algorithm is
applied locally and independently on each database. This is called the local
phase. Then, during the collaboration phase, data sites exchange their
findings in order to try to improve their results.

The kind of information algorithms share will differ depending on what kind of
data distribution one is dealing with. When objects in different data sites
lie in the same feature space, then experts can share information that can be
represented in the feature space itself. This task in known as vertical
collaborative clustering. In horizontal collaborative clustering, on the other
hand, data sites agree on the identity of the objects but these latter are
described in different feature spaces, then they can no longer share that kind
of information. But they can still compare the clusters they created, using
e.g. their partition matrices. A partition matrix is a $N\\!\times\\!C$ matrix
where $N$ is the number of objects in the dataset and $C$ is the number of
clusters looked for. The $k$-th row of this matrix represents the membership
of each object to the $k$-th cluster.

This paper is dedicated to horizontal collaborative clustering, and our main
contributions are:

  * •

An implementation of an intuitive idea for collaboration: the more doubts we
have about our findings, the more weight we will give to remote findings.

  * •

Collaboration with every experts at the same time. Thus there is no more need
to choose which site to collaborate with at each step.

  * •

Collaboration at the level of each observation. This allows algorithms to
fine-tune the way they collaborate with others.

  * •

Detection of examples that are difficult to cluster.

  * •

Improvement of efficiency by executing in parallel the base-learning processes
on subsets of the training data set.

  * •

Advantage of learning from small subsets of data that fit in main memory.

  * •

Improves predictive performance by combining different learning systems each
having different inductive bias.

It is organized as follows: Section 2 discusses related work. Then our main
contribution –Collaborative Learning Using Privileged Information– is
introduced in Section 3. Next, we present the results obtained with different
datasets. Finally, we discuss the results in Section 5.

##  2 Related Work

Research in collaborative clustering has been introduced by Pedrycz in 2002
[4]. The author proposed a collaborative version of the Fuzzy C-Means
algorithm [8]. For this purpose, the objective function of the fuzzy c-means
algorithm is extended with a second term which forces a clustering based on a
subset to be "aware" of other partitions.

The SAMARAH method introduced by Wemmert in [10] can deal with heterogeneous
hard clustering algorithms. This method attempts to increase similarity
between clusterings through conflicts evaluation and resolution. In order to
compare partitions with possibly different number of clusters, a confusion
matrix is computed between each pair of algorithms. Then, a consensus is found
by applying a voting algorithm to these results.

In 2015, Sublime et al. proposed an approach lifting some limits of previous
works. Indeed, they introduce a framework for collaboration with heterogeneous
algorithms. This method has the advantage not to require any global exchange
confidence parameter, thus the impact of a distant algorithm on the local
results might be different for each observation.
However, using hard clustering results for the construction of the confusion
matrices leads to some loss of information. And every algorithm has the same
weight in this process. As it makes no difference between a data site with
well separated clusters and one with overlapping clusters, it allows low-
performing algorithms to impede the results of the better ones.

After having proposed collaborative versions of Self Organizing Maps (SOM) and
Generative Topographic Mapping (GTM), Ghassany et al. combined Fuzzy C-Means
and GTM algorithms to obtain a collaborative clustering algorithm.

In [13], Sublime et al. describe a collaboration framework for model-based
clustering algorithms. They define a global likelihood function and try to
optimize a proxy for this function. This process requires a weight parameter
between local and external information to be fixed.

More recently, an automated method for optimizing exchange confidence has been
proposed in 2018 by Sublime et al., and the collaboration involved 4 different
views. The authors achieved successful results in detecting noisy views, but
the method tends to favor collaboration between very similar views.

For a more comprehensive survey of the collaborative clustering literature,
the reader may refer to [5].

##  3 Theoretical framework and learning algorithm

In this section, we describe the general framework in which our method applies
and we describe our algorithm.

###  3.1 Setting

The goal of collaborative learning is to learn from local data and from a set
of learners with data stored across a large number of sites.

More formally, let the global data set $X$ distributed among $P$ sites:
$X^{[1]},\dots,X^{[p]},\dots,X^{[P]}$, where
$X^{[p]}=\\{x_{i}^{[p]}\\}_{i=1}^{N}$ is a set of $N$ objects and each object
$x_{i}^{[p]}\in\mathbb{R}^{d}$ is characterized by $d$ features (i.e. is a
vector in an $d$-dimensional feature space).

Our study is centered on the horizontal collaborative clustering problem.
Thus, each data site has access to different $d^{[p]}$ features describing the
same individuals. On each data site, there is an algorithm
$\mathcal{A}^{[p]},\,p=1,\dots,P$ trying to come up with a clustering of its
data $X^{[p]}$. The process has two steps: a local step, and a collaborative
step.

###  3.2 Underlying framework

####  3.2.1 Local step

During the local step, each algorithm $\mathcal{A}^{[p]}$ works on its local
data set $X^{[p]}$ and fits its parameters as it would do in a non-
collaborative framework. One requirement is that all algorithms have to be
probabilistic ones. In particular, one of the output is a responsibility
matrix $R^{[p]}$. This matrix contains the contributions of each component to
each observation, $R_{i,k}^{[p]}=\mathbb{P}(Z_{i}=k|X_{i},\theta)$, where $K$
is the number of clusters, $Z_{i}\in\\{1,\dots,K\\}$ are the components of the
model and the elements of $\theta$ are the distributions parameters.

Once every model has been trained, we want them to exchange information in
order to improve their performances. This is done in the collaborative step.

####  3.2.2 Collaborative step

In the collaborative steps, the different algorithms $\mathcal{A}^{[p]}$ will
exchange information in order to try to improve their respective
classification. In this context, the idea of LUPI is the following: suppose we
want to establish a clustering based on certain characteristics $X^{[p]}$, but
during the learning phase, in addition to $X^{[p]}$, we also receive
additional information, $X^{{[p]}^{*}}$. This additional information is
presented in the form of partition matrices $R^{[p]}$. The local learner
therefore has access to $X^{[p]}$ and $X^{{[p]}^{*}}$, instead of only
$X^{[p]}$, to do its clustering. In our case, for each algorithm
$\mathcal{A}^{[p]}$, $X^{{[p]}^{*}}\equiv R^{-[p]}$, where:

$R^{-[p]}=\\{R^{[q]}\,:\,q\in\\{1,\dots,P\\}\setminus\\{p\\}\\}$ (1)

The set $R^{-[p]}$ contains all partition matrices of site $p$’s counterparts.
In this case, how can we use $X^{[p]}$ and $X^{{[p]}^{*}}$ to improve each
local learners $\mathcal{A}^{[p]}$?

For the sake of simplicity, we consider two learners (sites): $P=2$. On the
local step, they yield two partition matrices: $R^{[1]}(t)$ and $R^{[2]}(t)$.
In particular, for sample $x_{i}$, we have $R^{[1]}_{i,.}$ and
$R^{[2]}_{i,.}$. Thus, the update rule for learner 1 for sample $x_{i}$ is:

$R^{[1]}_{i,.}(t+1)\longleftarrow
f\left(R^{[1]}_{i,.}(t),R^{[2]}_{i,.}(t)\right)$ (2)

We want this update rule to depend on the level of certainty data site 1 has
about its opinion. The higher this level, the lower the difference between
$R^{[1]}_{i,.}(t+1)$ and $R^{[1]}_{i,.}(t)$. Conversely, the lower it is, the
more weight will be put on $R^{[2]}_{i,.}(t)$. Moreover, the higher (resp. the
lower) site $2$’s certainty, the more (resp. less) it will influence
$R^{[1]}_{i,.}(t+1)$.

It turns out that the probabilistic framework is endowed with a measure that
can be interpreted as the amount of uncertainty in a distribution, namely the
entropy. It is defined as follows:

$H(X)=-\sum_{i=1}^{d}p(x_{i})\log_{2}p(x_{i})$ (3)

Where $X$ is a random variable with possible values $\\{x_{1},\dots,x_{d}\\}$.
It follows that the uncertainty for a distribution $R_{i}$ is:

$H(R_{i,.})=-\sum_{k=1}^{K}R_{i,k}\log_{2}R_{i,k}$ (4)

And its normalized version, using the fact that it is positive and maximized
when $X$ is uniformly distributed:

$\mathcal{H}(R_{i,.})=\frac{H(R_{i,.})}{log_{2}(K)}$ (5)

Then $0\leq\mathcal{H}(R_{i,.})\leq 1$, and

  * •

$\mathcal{H}(R_{i,.})\approx 0\Rightarrow
R_{i,.}\approx\mathbbm{1}_{Z_{i}=k}\textrm{ for some }k\in{1,\dots,K}$, i.e.
we have high confidence about membership of observation $i$.

  * •

$\mathcal{H}(R_{i,.})\approx 1\Rightarrow R_{i,.}\approx\frac{1}{K}\ \forall
k\in{1,\dots,K}$, i.e. we have high uncertainty about membership of
observation $i$.

Equation 6 gives the update rule for $R^{[ii]}$ when $P$ algorithms are
involved in the collaboration.

$R^{[p]}(t+1)\\!\longleftarrow\alpha^{[p]}\cdot\\!R^{[p]}(t)+\sum\limits_{R^{[q]}(t)\in
R^{-[p]}}\beta^{[p]}_{[q]}\cdot R^{[q]}(t)$ (6)

where

$\left\\{\begin{array}[]{lll}\alpha^{[p]}\\!=\\!\left(\frac{1}{P-1}\\!\sum\limits_{{R^{[q]}(t)\in
R^{-[p]}}}\\!\mathcal{H}\\!\left(\\!R^{[q]}(\\!t\\!)\\!\right)\right)\\!\cdot\\!\left(\\!1\\!-\\!\mathcal{H}\\!\left(\\!R^{[p]}(\\!t\\!)\\!\right)\right)\\\
\\\
\beta^{[p]}_{[q]}=\mathcal{H}\left(R^{[p]}(t)\right)\\!\cdot\\!\left(1-\mathcal{H}\left(R^{[q]}(t)\right)\right)\end{array}\right.$
(7)

In these equations, $\alpha^{[p]}$ is a vector of size $N$. Each element $i$
of $\alpha^{[p]}$ is a weight associated with the local classification of the
$i$-th observation. This weight depends negatively on the amount of
uncertainty carried by the local classification, and positively on the average
remote classification uncertainty.

Similarly, $\beta^{[p]}_{[q]}$ are vectors of size $N$. Each element $i$ of
$\beta^{[p]}_{[q]}$ is a weight associated with the classification of the
$i$-th observation by algorithm $\mathcal{A}^{[q]}$. This weight depends
positively on the amount of uncertainty carried by the local classification,
and negatively on the uncertainty of the remote classification.

Note that the data sites only share there partition matrices. Therefore, no
matter what the underlying algorithms are, provided that they look for the
same number of components, the collaboration algorithm is still relevant.
However, the data sites need to agree on the identity of the clusters. Our
implementation uses the Hungarian algorithm to reorder the clusters on each
data site. Next, we show how the values of $\alpha$ and $\beta$ can be used to
visualize information flow in the collaboration process, and describe the
CoLUPI algorithm.

####  3.2.3 Collaborative learning algorithm

Based on the theoretical formalism developed and presented in the previous
section, we can design a learning algorithm to establish exchanges between the
different sites through a collaborative process. This algorithm therefore uses
the equation 6 for updating the parameters of the sites in collaborative
interaction.

Algorithm 1 CoLUPI algorithm

Local step:

for all algorithms $\mathcal{A}^{[p]}$ do

train $\mathcal{A}^{[p]}$ on the data $X^{[p]}$

get local parameters $\theta^{[p]}$ and partition matrix $R^{[p]}$

end for

Collaborative step:

repeat

for all algorithms $\mathcal{A}^{[p]}$ do

$R^{[p]}(t+1)\leftarrow f\left(R^{[p]}(t),R^{-[p]}(t)\right)$

train model starting from new partition $R^{[p]}(t+1)$ using data $X^{[p]}$

get $\theta^{[p]}(t\\!+\\!1)$ and $R^{[p]}(t\\!+\\!1)$

if quality$\left(R^{[p]}(t\\!+\\!1)\right)$ is better than
quality$\left(R^{[p]}(t)\right)$ then

Accept collaboration

else

$\theta^{[p]}(t\\!+\\!1)\leftarrow\theta^{[p]}(t)$

$R^{[p]}(t\\!+\\!1)\leftarrow R^{[p]}(t)$

end if

end for

until no algorithm improves for its criterion

###  3.3 Visualization of the collaboration process

#####

In this section, we are interested in visualizing the information flow during
collaboration. As it has been mentioned above, each collaborator assigns one
weight to each source data site (including itself), for each observation. The
mean of these weights for each remote site gives us the average weight
assigned to that site and can be regarded as a confidence coefficient, except
that it is not uniform across observations. If there are $P$ sites, then this
gives us a $P\\!\times\\!P$ matrix as defined in 8 which can be regarded as a
confidence matrix. We show this collaboration heatmap for the Wdbc dataset in
Section 4.

$C_{(P\times
P)}=\begin{pmatrix}\overline{\alpha^{[1]}}&\overline{\beta^{[1]}_{[2]}}&\cdots&\overline{\beta^{[1]}_{[P]}}\\\
\\\
\overline{\beta^{[2]}_{[1]}}&\overline{\alpha^{[2]}}&\cdots&\overline{\beta^{[2]}_{[P]}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\overline{\beta^{[P]}_{[1]}}&\overline{\beta^{[P]}_{[2]}}&\cdots&\overline{\alpha^{[P]}}\end{pmatrix}$
(8)

Where

$\overline{\alpha^{[p]}}=\frac{1}{N}\sum_{i=1}^{N}\alpha_{i}^{[p]}\text{,}$
(9)

and

$\overline{\beta^{[p]}_{[q]}}=\frac{1}{N}\sum_{i=1}^{N}{\beta_{i}}^{[p]}_{[q]}.$
(10)

##  4 Experimental validation

In this section, we present the results obtained after running our algorithm
on several datasets. First, we describe the datasets that has been used in the
experiments, then we present two kinds of results: performance assessment and
visualization of the collaboration process. Finally, we discuss the execution
time of our algorithm with different input values.

###  4.1 Data sets

  * •

The Breast Cancer Wisconsin (Diagnostic) (WDBC) dataset consists in 569
digitized images of a breast mass. There are 30 real-valued input variables
describing the cell nuclei present in each image. Each observation is labelled
as benign or malignant.

  * •

The Spambase data set consists in 57 attributes describing a collection of
4601 spam and non-spam emails.

  * •

The Battalia3 data set is an artificial data set describing 2000 generated
exoplanets with 27 numerical attributes.

  * •

The MV2 dataset features 2000 data points, each described by 6 features. They
have been randomly generated from a mixture of one noise and four Gaussian
components.

  * •

The Isolated letters (Isolet) data set has 617 input variables describing 7797
voice recordings of individuals who spoke the name of each letter of the
alphabet.

  * •

The Madelon data set is an artificial data set containing 4400 data points
grouped in 32 clusters placed on the vertices of a five dimensional hypercube.
Then 15 redundant features and 480 useless features (random probes) were
added, for a total of 500 attributes.

###  4.2 Experimental protocol

In our experiments, we split the databases in order to obtain a horizontal
collaborative clustering setting – i.e. each data site has access to different
input variables for the same set of observations.

###  4.3 Results and analysis

####  4.3.1 Co-LUPI using GTM models

The Co-LUPI algorithm has been applied to each of the 6 data sets mentioned in
4.1 using Generative topographic mappings. The criterion for acceptance of
collaboration was the improvement of the Davies-Bouldin index. This is an
internal index, thus it does not require prior knowledge on the data
structure. A second version of the algorithm, RCo-LUPI, has been implemented.
It features a new, random, initialization of the responsibility matrix at each
step, along with the collaboration matrix. This technique is often used in
unsupervised learning, it is meant to reduce dependence on the initial
parameters. Table 1 shows that in most cases, RCo-LUPI performed slightly
better than Co-LUPI.
In order to visualize the dynamic of this process, one can look at the
successive confidence matrices of the collaboration step. Figure 2 represents
such data. The Co-LUPI algorithm has been applied to the WDBC data set, split
among 18 data sites. Obviously, not all algorithms benefited from the
collaboration at each step. In particular, the algorithm running on data site
number one did not improve its results until the fifth iteration in the
collaboration step. Furthermore, on iteration number 7, only the second
algorithm did improve. While this can be interpreted as a sign of an imminent
end of the

Table 1: Experimental results, Davies-Bouldin index - Co-EM: [13], Co-MV: [15], Co-GTM: [12], Co-SOM: [16], Co-LUPI, RCo-LUPI Name |  Co-EM |  Co-MV |  Co-GTM |  Co-SOM |  Co-LUPI |  RCo-LUPI
---|---|---|---|---|---|---
| Wdbc
---
0.85 | 0.97 | 0.9 | 0.84 | 0.78 | 0.69
| Spam Base
---
0.94 | 1.27 | 0.92 | 0.87 | 0.42 | 0.59
| Battalia3
---
2.43 | 2.83 | 2.68 | 2.51 | 1.47 | 1.37
| MV2
---
1.34 | 1.34 | 1.61 | 1.44 | 0.86 | 0.85
| Isolet
---
– | – | – | – | 1.33 | 1.31
| Madelon
---
– | – | – | – | 0.87 | 0.82

process, 3 other algorithms benefited from these new findings on the next
iteration. The process did not end before 4 more iterations.

###  4.4 Comparison with other collaborative approaches

The Co-LUPI and RCo-LUPI algorithms were empirically compared to four recent
implementations of collaborative clustering algorithms. The optimization
process behind the Co-EM algorithm is based on variational EM. It optimizes a
collaborative term which is equivalent to the entropy [13]. The same principle
is used in Co-EM with the difference that it is based on prototypes, while the
Co-EM is based on partitions [15]. In the Co-SOM and Co-GTM methods, the SOM
and GTM loss functions where modified in order to penalize the difference
between local and remote parameters [16, 12].

In order to assess the performance of our approaches, we use the Friedman test
and Nemenyi test recommended in [17]. First, algorithms are ranked according
to their performance on each dataset. There are as many rankings as their are
datasets. Then, the Friedman test is conducted to test the null-hypothesis
under which all approaches are equivalent, and in this case their average
ranks should be equal. If the null hypothesis is rejected, then the Nemenyi
test will be performed. If the average ranks of two approaches differ by at
least the critical difference(CD), then it can be concluded that their
performances are significantly different. In the Friedman test, we set the
significance level $\alpha=0.05$. The figure 1 shows a critical diagram
representing a projection of average ranks of the algorithms on enumerated
axis. The methods are ordered from left (the best) to right (the worst) and a
thick line connects the groups of algorithms that are not significantly
different (for the significance level $\alpha=5\%$). As shown in figure 1, Co-
LUPI and RCo-LUPI seem to achieve some improvement over the other proposed
techniques. But the results are not sufficient to conclude to a statistically
significant improvement. This result can be explained by the small number of
datasets and by the fact that the Nemenyi test only considers algorithms
performances through their ranks and is blind to the actual value of the
performance index.

Figure 1: Friedman and Nemenyi test for comparing multiple approaches over
multiple data sets: Approaches are ordered from left (the best) to right (the
worst) Figure 2: Information flow during collaboration for the Wdbc data set.
Each row represents a data site and each column the total weight assigned to
that source.

##  5 Conclusion and future work

We introduced Co-LUPI and RCo-LUPI, algorithms based on usage of privileged
information and probability for collaborative clustering. This allows local
algorithms to fine-tune collaboration depending on their (un)certainty –and
their remote counterparts’ (un)certainty– about the classification of each
data point, as measured by the entropy. This update rule is straightforward
and the collaboration is done with every remote site at the same time. This
avoids the classical problem of choosing which site to collaborate with at
each step.
We tested our approach on several data sets in the horizontal collaboration
setting, but it is also applicable in the hybrid setting. The results showed
improvement over state of the art. The framework also provides a way to
visualize information flow during the process. It exhibited interesting
behaviors, as algorithms with lower initial performance tended to make heavier
use of incoming information than the other ones. Moreover, even the algorithms
with the best results after the local step were able to improve in the
process. Indeed, the flexibility brought by Co-LUPI in the weighting of
incoming information allows algorithms to benefit from globally less efficient
counterparts, because the latter can be locally more efficient.
These results are very promising and the algorithm can be improved in several
ways. One big improvement would be to relax the assumption that every
algorithm look for the same number of clusters. This might be challenging as
the algorithms also have to agree on the identity of the different clusters.
This problem is related to the generalized assignment problem. We will also
investigate how is the CoLUPI algorithm performing when used with some of the
most representative algorithms to solve the problem, e.g. monarch butterfly
optimization (MBO) algorithm [18].

## References

  * [1] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data Clustering: A Review,” _ACM Comput. Surv._ , vol. 31, no. 3, pp. 264–323, Sep. 1999.
  * [2] V. Vapnik and A. Vashist, “A new learning paradigm: Learning using privileged information,” _Neural Networks_ , vol. 22, no. 5-6, pp. 544–557, 2009.
  * [3] V. Vapnik and R. Izmailov, “Learning using privileged information: similarity control and knowledge transfer,” _J. Mach. Learn. Res._ , vol. 16, pp. 2023–2049, 2015.
  * [4] W. Pedrycz, “Collaborative Fuzzy Clustering,” _Pattern Recognition Letters_ , vol. 23, no. 14, pp. 1675–1686, 2002.
  * [5] A. Cornuéjols, C. Wemmert, P. Gançarski, and Y. Bennani, “Collaborative clustering: Why, when, what and how,” _Inf. Fusion_ , vol. 39, pp. 81–95, 2018.
  * [6] W. Pedrycz and P. Rai, “Collaborative clustering with the use of Fuzzy C-Means and its quantification,” _Fuzzy Sets and Systems_ , vol. 159, no. 18, pp. 2399–2427, Sep. 2008.
  * [7] X. Lin, C. Clifton, and M. Zhu, “Privacy-preserving clustering with distributed EM mixture modeling,” _Knowledge and Information Systems_ , vol. 8, no. 1, pp. 68–81, Jul. 2005.
  * [8] J. C. Bezdek, _Pattern Recognition with Fuzzy Objective Function Algorithms_ , Springer, Ed. Kluwer Academic Publishers, 1981.
  * [9] S. Bickel and T. Scheffer, “Multi-view clustering,” _Proceedings - Fourth IEEE International Conference on Data Mining, ICDM 2004_ , pp. 19– 26, 12 2004.
  * [10] C. Wemmert, P. Gançarski, and J. J. Korczak, “A collaborative approach to combine multiple learning methods,” _International Journal on Artificial Intelligence Tools_ , vol. 09, no. 01, pp. 59–78, 2000.
  * [11] G. Forestier, P. Gançarski, and C. Wemmert, “Collaborative clustering with background knowledge,” _Data & Knowledge Engineering_, vol. 69, no. 2, pp. 211–228, 2010.
  * [12] M. Ghassany, N. Grozavu, and Y. Bennani, “Collaborative generative topographic mapping,” in _Neural Information Processing - 19th International Conference, ICONIP 2012, Doha, Qatar, November 12-15, 2012, Proceedings, Part II_ , ser. Lecture Notes in Computer Science, T. Huang, Z. Zeng, C. Li, and C. Leung, Eds., vol. 7664\. Springer, pp. 591–598, 2012.
  * [13] J. Sublime, B. Matei, G. Cabanes, N. Grozavu, Y. Bennani, and A. Cornuéjols, “Entropy based probabilistic collaborative clustering,” _Pattern Recognit._ , vol. 72, pp. 144–157, 2017.
  * [14] F. Dietrich and C. List, “Probabilistic opinion pooling generalized. Part one: General agendas,” _Social Choice and Welfare, Springer Verlag_ , vol. 48 (4), pp. 747–786, 2017.
  * [15] M. Ghassany, N. Grozavu, and Y. Bennani, “Collaborative multi-view clustering,” in _The 2013 International Joint Conference on Neural Networks, IJCNN 2013, Dallas, TX, USA, August 4-9, 2013_. IEEE, pp. 1–8, 2013.
  * [16] N. Grozavu and Y. Bennani, “Topological collaborative clustering,” _Aust. J. Intell. Inf. Process. Syst._ , vol. 12, no. 3, 2010.
  * [17] J. Demsar,“Statistical Comparisons of Classifiers over Multiple Data Sets,” _J. Mach. Learn. Res._ , vol. 7, pp. 1–30, 2006.
  * [18] Wang, Gai-Ge, Suash Deb, and Zhihua Cui. "Monarch butterfly optimization." Neural computing and applications 31, no. 7, pp.1995–2014, 2019.
  * [19] Y. Foucade, “CoLUPI: learning from data and learners” [Source code and more material] https://github.com/yfoucade/colupi.