# MPXGAT: An Attention based Deep Learning Model for Multiplex Graphs
Embedding

Marco Bongiovanni<EMAIL_ADDRESS>Luca Gallo  Roberto Grasso
Alfredo Pulvirenti<EMAIL_ADDRESS>
###### Abstract

Graph representation learning has rapidly emerged as a pivotal field of study.
Despite its growing popularity, the majority of research has been confined to
embedding single-layer graphs, which fall short in representing complex
systems with multifaceted relationships. To bridge this gap, we introduce
MPXGAT, an innovative attention-based deep learning model tailored to
multiplex graph embedding. Leveraging the robustness of Graph Attention
Networks (GATs), MPXGAT captures the structure of multiplex networks by
harnessing both intra-layer and inter-layer connections. This dual
exploitation facilitates accurate link prediction within and across the
network’s multiple layers. Our comprehensive experimental evaluation,
conducted on various benchmark datasets, confirms that MPXGAT consistently
outperforms state-of-the-art competing algorithms.

###### keywords:

Multiplex Graphs , GAT , Link prediction , Multiplex embedding

[1]organization=Department of Mathematics and Computer Science, University of
Catania,addressline=Via Santa Sofia, 64, city=Catania, postcode=95125,
country=Italy [2]organization=Department of Network and Data Science, Central
European University,addressline=Quellenstraße 51, city=Vienna, postcode=1100,
country=Austria [3]organization=Department of Physics and Astronomy,
University of Catania,addressline=Via Santa Sofia, 64, city=Catania,
postcode=95125, country=Italy [4]organization=Department of Clinical and
Experimental Medicine, University of Catania,addressline=Via Santa Sofia, 64,
city=Catania, postcode=95125, country=Italy

We introduce MPXGAT, an attention-based model for embedding multiplex networks

MPXGAT is effective in predicting links across layers of real-world
multiplexes

MPXGAT shows significant improvement over state-of-the-art competitors

##  1 Introduction and Related Works

In the last decades, graphs have proved to be a fundamental mathematical tool
to model various real-world complex systems. From transportation systems to
power grids, from the network of our social relationships to that of neurons
in our brains, complex networks are all around us. Due to such ubiquity,
network and graph theory have imposed themselves in many research fields, from
engineering to physics, social science, and biology [1, 2, 3, 4].

A topic that has recently received considerable interest in computer science
is that of how to efficiently represent large-scale graphs [5, 6, 7].
Particularly, graph embedding methods, which consist in projecting the
elements of a graph, i.e., vertices, edges, and motifs, to a low-dimensional
vector space by preserving some of the graph properties, have shown to be very
successful in graph representation [8]. These embedding techniques are
suitable for multiple applications, as they can be used in downstream learning
tasks, including node classification [9], link prediction [10], and community
detection [11].

We can broadly categorize graph embedding methods into traditional graph
embedding and graph neural networks (GNNs) based embedding methods [8]. The
first group consists of algorithms that represent graphs relying on techniques
such as random walks [12, 13, 14] and matrix factorization methods. These
shallow approaches have several drawbacks that limit their efficiency and
effectiveness. First, they do not share any parameters between the nodes in
the encoder function, which maps each node to a vector representation, making
them statistically and computationally inefficient. Second, they ignore the
node attributes during the encoding process, leading to a lower quality of the
embeddings. Third, they are transductive, meaning they can only generate
embeddings for the nodes seen during the training phase [15].

Embedding methods based on GNNs go beyond such limitations using more
sophisticated encoders accounting for the graph structure and the node
attributes. The key feature of a GNN is that the embedding of a node in the
graph is obtained by aggregating the embeddings of the node’s neighbors [8].
In the last few years, a large variety of methods have been developed [6, 16,
17, 18], with the most notable examples including Graph Convolutional Networks
(GCNs) [19], GraphSAGE [20] and Graph Attention networks (GATs) [16].

Although graphs are widely recognized for their versatility in modeling
complex systems, traditional graph structures are limited to depicting a
singular relationship type among system entities. This simplistic
representation is insufficient for systems where entities engage in diverse
interactions [3]. For example, social systems often involve individuals
connected through various relationships such as friendship, kinship, or
professional collaboration, and they may communicate through multiple channels
like direct contact, phone, or online platforms [21, 22]. Similarly, in
biological systems, proteins may interact genetically, physically, or through
spatial proximity [23].

To encapsulate the complexity of such systems, advanced mathematical
structures like multidimensional and multiplex graphs are employed [24, 25,
26]. Multidimensional graphs, or edge-labeled multigraphs, feature vertices
connected by edges of different labels, each signifying a distinct interaction
type within the system. Multiplex graphs, on the other hand, consist of
multiple interconnected layers, with each layer dedicated to a specific
relationship type.

The key distinction between multigraphs and multiplex networks lies in the
representation of system units. In multigraphs, a unit is depicted as a single
node linked to others through various connection types. Multiplex networks
[27, 22], however, represent units as a set of nodes distributed across
different layers, connected by inter-layer links. Typically, a unit is
represented in only a subset of layers, indicating connections through certain
relationship types. Furthermore, it is often the case that only a portion of
the inter-layer links connecting the multiple representations of the same unit
is known [26].

Multi-relational network embedding is a challenging problem recently garnering
significant research interest. Various methods to embed networks with multiple
types of nodes and links, such as multidimensional networks and multiplex
networks, have been proposed. Some of these methods are based on shallow
embedding approaches [28, 29, 30, 31], while others use graph convolutional
networks (GCNs) [32, 33, 34] or graph attention networks (GATs) [35]. However,
none of these methods can solve the problem of predicting links between
different layers of a multilayer network. This problem is important when the
network structure is incomplete or heterogeneous. For example, some methods
assume that all nodes are present in every layer, which is not realistic in
many cases. Other methods (such as [36]; [37]; [38]) do not distinguish
between intra-layer and inter-layer links, ignoring the diversity and
complexity of multilayer networks. Very recently, MultiplexSAGE, a
generalization of GraphSAGE aimed at embedding multiplex networks by relaxing
these hypothesis, have been proposed [39], yet there is still a need for new
methods that can address the problem of predicting inter-layer links in a
general, flexible and more reliable way.

The inter-layer link prediction problem finds many crucial applications: i)
linking user identities across different online social networks (OSNs), an
emerging task in social media that has attracted increasing attention in
recent years [40]. User identity linkage finds potential impact in different
domains, from recommendation systems to cybersecurity [41]; ii) identifying
the same genes or proteins across different biological networks, such as gene
expression, protein interaction, metabolic pathways, etc. This can help to
discover the molecular mechanisms of diseases and to find potential drug
targets [42]; iii) matching the same entities across different knowledge
graphs [43], which can help to enrich the semantic information and to improve
query answering and reasoning capabilities. The range of possible applications
of inter-layer link prediction ultimately motivates the development of
embedding algorithms for multiplex networks that are able to distinguish
between intra-layer and inter-layer links, and to reconstruct both
connectivity patterns.

Predicting inter-layer connections in multiplex networks differs from graph
matching or alignment. Graph matching [44] identifies isomorphisms between
graphs, ensuring identical topology. In contrast, inter-layer prediction
uncovers missing links between nodes representing the same unit across layers,
with diverse connectivity. Global graph alignment [45] finds optimal
correspondences between multiple graphs, considering both structure and node
labels. However, inter-layer link prediction focuses on a specific bijection
between two graphs, i.e., layers of a multiplex network. Also, while graph
alignment is general, inter-layer prediction is specific to multiplex
networks.

In this paper, we introduce MPXGAT, an attention based deep learning model for
multiplex graphs embedding. Our methodology, based on GATs, consists in
embedding the nodes of a multiplex network by leveraging the information about
their intra-layer and inter-layer connections, allowing for link prediction
tasks both within the same layer and across different layers. We carry out a
thorough experimental analysis on three benchmark datasets, showing that
MPXGAT out-performs state-of-the-art competing algorithms. We conclude with an
in-depth study of the model main features, proving how their use positively
impacts the performance of the algorithm itself.

##  2 Methods

In this section, we provide details of our model, _MPXGAT_ , which can embed
multiplex networks, namely networks where multiple types of link exist. We
first provide some preliminary notions, next, we introduce the mathematical
formulation of the model, and finally, we describe the algorithmic
implementation.

###  2.1 Preliminary Notions

We start by defining the basic concepts of simple and multiplex graphs A graph
(network) is a mathematical structure consisting of a set of vertices (nodes)
and a set of edges (links), where each edge represents a relation between a
pair of vertices. Simple graphs are able to capture only one kind of
relationship, so they are limited when it comes to characterizing systems
where multiple types of interactions coexist. The need of a higher degree of
expressiveness motivates the use of multiplex graphs. We can define multiplex
graphs as a graphs composed by two different sub-networks, which we refer to
as horizontal and vertical. The horizontal network consists of a collection of
simple graphs, called (horizontal) layers. In this setup, each unit of a
system can be represented as a node in one or more layers, with each layer
referring to a certain type of relationship. We refer to the connections
within a given layer as intra-layer links. The second sub-network, namely the
vertical network, consists of a single-layer graph formed by the set of edges
connecting nodes across different layers. We assume that a node $i$ on a layer
$\alpha$ can be connected to at most one node $j$ on another layer $\beta$,
i.e., the two nodes represent the same unit of the system. Also, we assume
that if node $i$ on layer $\alpha$ is connected to node $j$ on layer $\beta$,
and if node $j$ is connected to node $k$ on layer $\gamma$, then nodes $i$ and
$k$ are also connected. Under these hypothesis, the vertical network consists
in a collection of connected components, which can be either cliques or
isolated nodes. The edges in the vertical network will be referred to as
inter-layer links.

Formally, a multiplex graph is a set ${\mathbb{V}}$ of $N$ nodes that are
connected through $L$ different layers. We assume that $N_{\alpha}$ nodes are
present in each layer $\alpha\in\\{0,1,\dots,L\\}$, such that
$N_{1}+\dots+N_{L}=N$. Each layer $\alpha$ is a graph
${\mathcal{G}}_{\alpha}=\left({\mathbb{V}}_{\alpha},\mathcal{E}_{\alpha}\right)$
where ${\mathbb{V}}_{\alpha}\in{\mathbb{V}}$ is the set of the $N_{\alpha}$
nodes and $\mathcal{E}_{\alpha}$ is the set of edges connecting them. The node
sets for each layer are disjoint, i.e.,
${\mathbb{V}}_{\alpha}\cap{\mathbb{V}}_{\beta}=\emptyset$ for
$\alpha\neq\beta$, and their union makes the set of all nodes ${\mathbb{V}}$.
The set of intra-layer links for the horizontal network can be defined as
$\mathcal{E}_{\mathrm{intra}}=\bigcup_{\alpha=1}^{L}\mathcal{E}_{\alpha}$.
Hence, we define the horizontal network as
${\mathcal{G}}_{H}=\left({\mathbb{V}},\mathcal{E}_{\mathrm{intra}}\right)$.
The vertical network can be instead defined as
${\mathcal{G}}_{V}=\left({\mathbb{V}},\mathcal{E}_{\mathrm{inter}}\right)$,
where
$\mathcal{E}_{\mathrm{inter}}=\left\\{\left(i,j\right)\in{\mathbb{V}}\times{\mathbb{V}}\mid\exists\alpha,\beta\in\\{0,1,\dots,L\\}\,s.t.\,\left(i,j\right)\in\mathcal{E}_{\alpha}\times\mathcal{E}_{\beta}\right\\}$
is the set of inter-layer edges. Figure 1 shows an illustration of a multiplex
graph.

Table 1: Description of the variables involved in this work. Note that
superscripts $\cdot^{H}$ and $\cdot^{V}$ are omitted for the sake of
readability

VARIABLE | DESCRIPTION
---|---
$N\in\mathbb{N}$ | Number of nodes in the multiplex graph
${\mathbb{V}}$ | Set of nodes in the multiplex graph
$L\in\mathbb{N}$ | Total number of horizontal layers of the multiplex graph
$\alpha\in\mathbb{N}$ | Index of the horizontal layer in the multiplex graph
$N_{\alpha}$ | Number of nodes within the horizontal layer of index $\alpha$
${\mathbb{V}}_{\alpha}$ | Set of nodes within the horizontal layer of index $\alpha$
$\mathcal{E}_{\alpha}$ | Set of edges within the horizontal layer $\alpha$
${\mathcal{G}}_{\alpha}$ | Layer of index $\alpha$ in the horizontal network
$\mathcal{E}_{\mathrm{intra}}$ | Set of intra-layer edges for the horizontal network
$\mathcal{E}_{\mathrm{inter}}$ | Set of inter-layer edges for the horizontal network
${\mathcal{G}}_{H}$ | Horizontal network of the multiplex graph
${\mathcal{G}}_{V}$ | Vertical network of the multiplex graph
$F\in\mathbb{N}$ | Initial node feature dimensionality
$F^{\prime}\in\mathbb{N}$ | Final node feature dimensionality
$i\in\mathbb{N}$ | Source node
$j\in\mathbb{N}$ | Destination node
$k\in\mathbb{N}$ | Source node horizontal layer’s index
$q\in\mathbb{N}$ | Destination node horizontal layer’s index
$\mathcal{N}_{i}$ | Set of nodes connected to node $i$
${\bm{h}}_{i}\in\mathbb{R}^{F}$ | Embedding of node $i$
${\bm{v}}\in\mathbb{R}^{F^{\prime}}$ | Attention weight vector
${\bm{W}}\in\mathbb{R}^{F^{\prime}\times F}$ | Weight matrix, used to linearly transform the node embeddings
$e_{i,j}\in\mathbb{R}$ | Attention coefficient between node $i$ and $j$
$\alpha_{i,j}\in\mathbb{R}$ | Normalized attention coefficient between nodes $i$ and $j$
${\bm{h}}_{i}\in\mathbb{R}^{F^{\prime}}$ | Updated embedding of node $i$ after a forward pass
$\sigma$ | Activation function (in our case LeakyReLU)
$f$ | Function used to transform the horizontal embeddings
| to the same dimensional space of the vertical embedding
$g$ | Function used to combine the data obtained from the vertical network
| with the result of the application of the function $f$

Figure 1: A toy example of a multiplex network with 2 horizontal layers. The
solid edges represent the intra-layer connections while the dashed edges are
the inter-layer edges.

###  2.2 The MPXGAT General Framework

The main idea of MPXGAT is to generate two separate embeddings for each node
in two different phases. In the first phase, each node is embedded according
to the horizontal layers, where it has multiple types of relation with other
nodes. In the second phase, nodes are embedded according to the vertical
network, where they are linked to their counterparts on different layers. In
the following, we will use the superscript $\cdot^{H}$ when we refer to the
horizontal network, while the superscript $\cdot^{V}$ will refer to the
vertical one. The notation used, together with the most relevant variables of
our model, are reported in Table 1.

Figure 2: The structure of the MPXGAT model. In this toy example, it is
applied on a multiplex network with 2 horizontal layers where the solid blue
edges represent the intra-layer connections while the dashed red edges are the
inter-layer edges. The data is provided to the _MPXGAT-H_ throughout the dot-
and-dash blue lines. Once processed these are used to feed the _MPXGAT-V_
together with the inter-layer links (the dotted green lines). The output of
the model consists of both horizontal and vertical nodes embedding.

Our algorithm uses two sub-models, one for each embedding phase: MPXGAT-H and
MPXGAT-V (an illustration of the model structure is shown in Figure 2). In the
most general framework, MPXGAT-H applies a series of GAT convolutional layers
independently to each layer of the horizontal network Mathematically, the
embedding is described by the following equations:

$\displaystyle e_{i,j}^{H_{k}}$
$\displaystyle=\text{LeakyReLU}\left(\left[{\bm{W}}^{H_{k}}\cdot{\bm{h}}_{i}^{H_{k}}\cdot({\bm{v}}^{H_{k}})^{T}||{\bm{W}}^{H_{k}}\cdot{\bm{h}}_{j}^{H_{k}}\cdot({\bm{v}}^{H_{k}})^{T}\right]\right)$
(1a) $\displaystyle\alpha_{i,j}^{H_{k}}$
$\displaystyle=\text{softmax($e_{i,j}^{H_{k}}$)}=\frac{\exp(e_{i,j}^{H_{k}})}{\sum_{z\in\mathcal{N}_{i}^{H_{k}}}\exp(e_{i,z}^{H_{k}})}$
(1b) $\displaystyle{\bm{h}}_{i}^{{}^{\prime}H_{k}}$
$\displaystyle=\sigma\left(\sum_{j\in\mathcal{N}_{i}^{H_{k}}}\alpha_{i,j}^{H_{k}}\cdot{\bm{W}}^{H_{k}}\cdot{\bm{h}}_{j}^{H_{k}}\right)$
(1c)

Equations 1 govern the convolutional layer as described in the GAT model [16].
In particular, in Equation 1c, ${\bm{h}}^{\prime H_{k}}_{i}$ represents the
horizontal embedding of the node _i_ that belongs to the layer $k$, while
Equation 1b describes the self attention mechanism in layer $k$.

Leveraging the horizontal embeddings, MPXGAT-V generates the vertical
embeddings by making use of a custom mechanism inspired by the one applied in
the GAT model, which we call GAT-V. The equations to compute the vertical
embedding of node _i_ are the following:

$\displaystyle e_{i,j}^{V^{k,q}}$
$\displaystyle=\text{LeakyReLU}\left(\left[{\bm{W}}^{V}\cdot{\bm{h}}_{i}^{V}\cdot({\bm{v}}^{V})^{T}||{\bm{W}}^{V}\cdot{\bm{h}}_{j}^{V}\cdot({\bm{v}}^{V})^{T}\right]\right)$
(2a) $\displaystyle\alpha_{i,j}^{V^{k,q}}$
$\displaystyle=\text{softmax($e_{i,j}^{V^{k,q}}$)}=\frac{\exp(e_{i,j}^{V^{k,q}})}{\sum_{z\in\mathcal{N}_{i}^{V}}\exp(e_{i,z}^{V})}$
(2b) $\displaystyle{\bm{h}}_{i}^{{}^{\prime}V}$
$\displaystyle=\sigma\left(\sum_{j\in\mathcal{N}_{i}^{V}}g\left(\left[\alpha_{i,j}^{V}\cdot{\bm{W}}^{V}\cdot{\bm{h}}_{j}^{V}\right],f({\bm{h}}_{i}^{H_{k}},{\bm{h}}_{j}^{H_{q}})\right)\right)$
(2c)

Equations 2 contain two novel elements. The first is the function $f$, which
transforms the final horizontal embeddings to the same dimensional space of
the vertical embeddings. Such a function can be a simple linear transformation
of the node horizontal embeddings, or it can be more complex, depending on the
specific task considered. The second feature we introduce is the function $g$,
which combines the data obtained from the current vertical embedding with the
results of the the function $f$.

###  2.3 MPXGAT Implementation for Link Prediction

We now present an implementation of _MPXGAT_ that is suitable for link
prediction. We customize the attention mechanisms of both _MPXGAT-H_ and
_MPXGAT-V_ , which are described in Equations 1a, 1b and 2a, 2b, respectively.
In particular:

  * 1.

in Equations 1a and 2a, instead of a single weight matrix for both $i$ and $j$
nodes, i.e., ${\bm{W}}^{H}$, two different weight matrices,
$\left({\bm{W}}^{H}_{i},{\bm{W}}^{H}_{j}\right)$, are used. By doing that, we
improve the representation capabilities of the model, at the expense of a
greater number of parameters. The same choice is done for the weight vector,
where instead of a single vector ${\bm{v}}^{H},$ we use two,
$\left({\bm{v}}^{H}_{i},{\bm{v}}^{H}_{j}\right)$. Moreover, to improve the
generalization capabilities of the model, the concatenation operator $||$ is
implemented as a sum $+$, and both parts of this operation are augmented with
the introduction of a bias vector;

  * 2.

in Equations 1b and 2b an additional dropout mechanism is applied to the
attention coefficients. In this way, we sub-sample the paths present in the
graph, granting the model a better generalization capability.

A further addition is the use of _multiple attention heads_ , consisting in
calculating different embeddings of the same nodes applying multiple times the
convolutional layer. This generates multiple node representations that
highlight different kinds of patterns about the nodes, as each attention head
can be seen as a distinct information channel representing a certain aspect of
nodes. The implemented sub-models concatenates the embeddings for each
attention head in the hidden convolutional layers of the model, and uses a
mean operation for the final one.

Finally, for both sub-models the activation function $\sigma$ in Equations 1c
and 2c we consider the _LeakyReLU_.

The general _MPXGAT_ framework rely on the $f$ and $g$ functions for the
embedding, which can be specified according to the particular task we want to
solve. Here, the two functions $f$ and $g$ introduced in Equation 2c have the
following characteristics:

  * 1.

$f$ performs a linear transformation of the horizontal embedding of the source
node, ${\bm{h}}_{i}^{H}$, to the same dimensional space of its vertical
embedding, ${\bm{h}}_{i}^{V}$, here described with ${\bm{x}}_{i}^{H}$. This is
done through an additional weight matrix ${\bm{Z}}^{H}$. The result is then
multiplied by a vector of parameters ${\bm{v}}_{i}^{H}$, whose role is to
enhance the patterns from the horizontal embeddings. Finally, the LeakyReLU
function is applied.

  * 2.

The function $g$ performs a weighted sum of the output of the function $f$
(see Equation 3c) and the data computed with the convolutional layer for the
vertical network (see Equation 3d). A scalar parameter $\beta$, automatically
inferred during the learning process, is introduced to tune the information
coming from the horizontal and vertical embeddings, respectively. In
particular when $\beta=0$ the horizontal embedding is not considered, while
for $\beta=0.5$ both the components are considered with the same weight.

Formally, the equations describing the implementation of _MPXGAT_ for link
predictions are:

$\displaystyle{\bm{x}}_{i}^{H}$
$\displaystyle={\bm{h}}_{i}^{H}\cdot{\bm{Z}}^{H}+{\bm{b}}_{h_{i}}$ (3a)
$\displaystyle\alpha_{i}^{H}$ $\displaystyle=\text{LeakyReLU}\left(\
{\bm{x}}_{i}^{H}\cdot{\bm{v}}_{i}^{H}\right)$ (3b)
$\displaystyle{\bm{m}}^{H}_{i}$
$\displaystyle=f({\bm{x}}_{i}^{H})=\alpha_{i}^{H}*{\bm{x}}_{i}^{H}$ (3c)
$\displaystyle{\bm{m}}^{V}_{i,j}$
$\displaystyle=\alpha_{i,j}^{V}\cdot{\bm{x}}_{j}^{V}$ (3d) $\displaystyle
g\left({\bm{m}}^{V},{\bm{m}}^{H}\right)$
$\displaystyle=\left({\bm{m}}^{V}_{i,j}*\left(1-\text{ReLU}\left(\beta\right)\right)\right)+\left(\left({\bm{m}}^{H}_{i}\right)*\text{ReLU}\left(\beta\right)\right)$
(3e)

A few aspects of our model are worth remarking. First, we assume neither to
have the same number of nodes in each horizontal layer nor to have all
possible inter-layer links, making our algorithm a valuable tool for
reconstructing inter-layer connectivity. Second, _MPXGAT_ is quite flexible,
as it supports the use of node features and edge weights. In particular,
different features can be used by the two sub-models, since the horizontal and
the vertical networks are defined and processed as separated entities. As we
will show in the next section, these characteristics guarantee our model good
performances even in datasets where the edge density in the horizontal or
vertical networks is high, which represents a strong limit of algorithms based
on GraphSAGE [39].

##  3 Results

In this section, we present the results obtained by _MPXGAT_ in predicting
both intra-layer and inter-layer links. We first present the datasets studied,
as well as the experimental setup used for the analysis, and the competing
methods considered as benchmarks for our algorithm. Then, we test the
performances of _MPXGAT_ in the link prediction task. We round up the analysis
by assessing the impact of the horizontal and vertical sub-models on the
embedding procedure.

###  3.1 Dataset

To assess the performance of _MPXGAT_ in predicting both intra-layer and
inter-layer connections, we employ the same datasets that have been originally
used to test _MultiplexSAGE_ [39]. These include data relative to three types
of real-world multiplex networks, namely a collaboration, a biological, and an
online social networks. Specifically, we considered the following datasets.

arXiv [46]. The arXiv multiplex network represents collaborations in various
research topics published on the pre-print archive. Each layer of the network
corresponds to a different research category or theme. The network was
obtained by selecting papers published before May 2014 that contain the
keyword _networks_ in their titles or abstracts.

Drosophila [47]. This multiplex network represents the interactions between
proteins and genes in the common fruit fly, i.e., Drosophila melanogaster,
with each layer corresponding to interactions of various types. The dataset
was collected from the Biological General Repository for Interaction Datasets
(BioGRID), with data updated until January 2014.

ff-tt-yt [48]. This multiplex network is derived from Friendfeed (ff), a
social media aggregation platform where users can link their accounts from
various online social networks (OSNs). The network comprises users who have
registered a single Twitter (tw) account and a sole YouTube (yt) account on
Friendfeed. Additionally, the Twitter and YouTube accounts are linked to a
single Friendfeed account.

For each empirical dataset, we consider exclusively the largest connected
component of the multiplex networks and we treat all networks as undirected
and unweighted. Details about the largest connected component for each of
these datasets are provided in Table 2.

We remark that, for all datasets considered in our analysis, nodes are not
provided with any external features. Hence, we associate to each node, $n$, a
one-hot encoding vector defined by the Kronecker function, $\delta_{i,n}$.

Table 2: Dataset Information including the number of nodes, edges, and average degree for the largest connected component of each dataset (arXiv, Drosophila, and ff-tw-yt) Dataset | Nodes | Edges | Avg. Degree
---|---|---|---
arXiv | 19,310 | 20,738 | 1.07
Drosophila | 11,867 | 5,171 | 0.44
ff-tw-yt | 11,827 | 6,028 | 0.51

###  3.2 Experimental setup

To assess the performance of _MPXGAT_ , we consider the experimental setup
delineated in [39]. We partition the data following a multiple step procedure.
First, we randomly select 20% of the network nodes, labeling them as _marked
nodes_. We then define test and training sets. Both sets encompass positive
and negative examples, the former corresponding to actual links within the
network, while the latter consisting in pairs of unconnected nodes. In the
test set, positive examples comprise a subset of 20% of the intra-layer links
and all inter-layer links among the marked nodes. Conversely, positive
examples in the training set include all remaining intra-layer and inter-layer
links in the multiplex network. As negative examples within the test set, we
include 20% of all possible negative intra-layer links among the marked nodes,
as well as all possible inter-layer links between them. The negative examples
in the training set correspond to the remaining pairs of unconnected nodes.

To test the performance of our algorithm, instead of conducting a single
experiment for each dataset, we repeat the embedding procedure multiple times.
For each repetition, we randomly select a subset of marked nodes, defining the
training and test sets accordingly. To obtain the best parameter settings, we
apply a grid search method.

###  3.3 Competing Methods

We conduct a comparative analysis of _MPXGAT_ against three competing
methodologies, specifically _GraphSAGE_ , _GATNE_ and _MultiplexSAGE_.

_GraphSAGE_ [20]. _GraphSAGE_ is an inductive node embedding algorithm that
leverages node features to learn an embedding function capable of generalizing
to unseen nodes. It was originally designed for single-layer network
embeddings, so in our experiments, we apply it without distinguishing between
intra-layer and inter-layer links.

_GATNE_ [35]. _GATNE_ is an embedding algorithm for attributed heterogeneous
networks, encompassing multigraphs with diverse node and edge types. To adapt
_GATNE_ to our specific task, we introduced two categories of edges, denoted
as intra-layer and inter-layer links. This adjustment allows us to create a
multigraph that the algorithm can learn to embed effectively.

_MultiplexSAGE_ [39]. _MultiplexSAGE_ represents an extension of the GraphSAGE
algorithm, specifically tailored for embedding multiplex networks. Its key
feature is the distinction made between inter-layer and intra-layer links that
allows for the prediction of both intra-layer and inter-layer connectivity
patterns.

Other relevant methods such as [31], [33], [28], [49], [29], [30] and [34] can
not be used as competing methods, as they assume that each layer has the same
number of nodes and that all inter-layer connections are known. Therefore, as
we are interested in predicting both intra-layer and inter-layer links, these
methods are not suitable benchmarks for evaluating the performance of
_MPXGAT_.

###  3.4 Embedding Multiplex Networks

Our first analysis concerns the prediction of both intra-layer and inter-layer
links when embedding a multiplex network. For each embedding, we evaluate the
Area Under the Receiveing Operating Characteristic (ROC) Curve (AUC), and take
an average over the different repetitions as a performance metric. We consider
the standard deviation as an indicator of statistical error. Table 3 provides
an overview of the performances obtained with _MPXGAT_ , _GraphSAGE_ , _GATNE_
, and _MultiplexSAGE_. We note that _GATNE_ outperforms _GraphSAGE_ and
_MultiplexSAGE_ in intra-layer link prediction, having a higher average AUC
for all three datasets. However, _MPXGAT_ has comparable performances with
_GATNE_ on the ff-ww-tt and the Drosophila dataset, while the latter performs
better on the arXiv dataset. Yet, with regards to inter-layer link prediction,
_MPXGAT_ clearly performs better than all other algorithms, including
_MultiplexSAGE_ , which is explicitly designed for that task. Overall, if we
consider the general performance of the methods without distinguishing intra-
and inter-layer connections, our algorithm emerges as the best solution, as
reported in Table 4.

Table 3: Performance comparison on intra-layer and inter-layer link prediction
across the three distinct datasets: ff-tw-yt, Drosophila, and arXiv. The
assessment is based on the AUC metric, using the standard deviation as error
metric. The best performing tool is highlighted in boldface

Algorithm | ff-tw-yt | Drosophila | arXiv
---|---|---|---
| _intra_ | _inter_ | _intra_ | _inter_ | _intra_ | _inter_
_GraphSAGE_ | 0.47 (± 0.02) | 0.56 (± 0.02) | 0.54 (± 0.02) | 0.63 (± 0.02) | 0.72 (± 0.02) | 0.70 (± 0.01)
_GATNE_ | 0.83 (± 0.01) | 0.47 (± 0.01) | 0.78 (± 0.01) | 0.55 (± 0.01) | 0.91 (± 0.01) | 0.63 (± 0.01)
_MultiplexSAGE_ | 0.48 (± 0.02) | 0.62 (± 0.02) | 0.51 (± 0.01) | 0.77 (± 0.02) | 0.71 (± 0.02) | 0.83 (± 0.01)
_MPXGAT_ | 0.76 (± 0.06) | 0.83 (± 0.01) | 0.76 (± 0.05) | 0.86 (± 0.02) | 0.80 (± 0.02) | 0.84 (± 0.01)

Table 4: Overall AUC performaces calculated as a weighted sums of the results shown in Table 3, based on the number of edges used to evaluate the models. Algorithm | ff-tw-yt | Drosophila | arXiv
---|---|---|---
_GraphSAGE_ | 0.49 (± 0.02) | 0.57 (± 0.01) | 0.70 (± 0.01)
_GATNE_ | 0.72 (± 0.01) | 0.69 (± 0.02) | 0.72 (± 0.01)
_MultiplexSAGE_ | 0.52 (± 0.02) | 0.61 (± 0.01) | 0.79 (± 0.01)
_MPXGAT_ | 0.78 (± 0.03) | 0.80 (± 0.03) | 0.82 (± 0.04)

As described in Section 2, _MPXGAT_ employs two distinct embeddings, dealing
with the horizontal, i.e., intra-layer, and vertical, i.e., inter-layer,
embeddings, respectively. In contrast, the other models rely on a single
embedding that serves both tasks. As we will further investigate in the next
section, it is this architectural difference that allows _MPXGAT_ to predict
with a certain reliability both intra-layer and inter-layer links.

###  3.5 Measure the impact of Horizontal Embeddings

We now establish the impact of the horizontal embeddings on the performance of
_MPXGAT_. To do so, we conduct two experiments. In the first, we perform the
embedding with _MPXGAT_ , but instead of using MPXGAT-V, which leverages the
horizontal embeddings generated by MPXGAT-H, for embedding the vertical
network, we consider a standard GAT [16], thus ignoring the contribution of
MPXGAT-H. Table 5 reports the average AUC for the inter-layer link prediction
in both configurations. We observe that neglecting the horizontal embeddings
leads to worse performances across all datasets, suggesting that including the
MPXGAT-V submodel increases the algorithm adaptability and predictive power.

To validate the significance of these findings we performed a Welch’s T-test.
The p-values are $6.00\times 10^{-7}$, $9.10\times 10^{-10}$, and $1.10\times
10^{-7}$ for the Drosophila, arXiv, and ff-tw-yt datasets, respectively,
confirming the statistical significance of our finding.

Table 5: Results of the ongoing experiment aimed at assessing the impact of
excluding horizontal embeddings on inter-layer link prediction. The
performance is evaluated in terms of AUC across the three datasets. The second
model, which omits horizontal embeddings, exhibits lower performance in inter-
layer link prediction across all datasets.

Algorithm | ff-tw-yt | Drosophila | arXiv
---|---|---|---
_MPXGAT-V_ _(layer _GAT-V_)_ | 0.83 ± (0.01) | 0.86 ± (0.01) | 0.84 ± (0.01)
_GAT_ _(layer _GAT_)_ | 0.72 ± (0.02) | 0.78 ± (0.02) | 0.78 ± (0.01)

In the second experiment, we keep the original model architecture but instead
of providing MPXGAT-V with the horizontal embeddings generated by MPXGAT-H, we
replace them with random embeddings, i.e., vectors whose components are random
values.

Table 6 shows the results of the comparison with regards to the inter-layer
link prediction. We note that for both the ff-tw-yt and the arXiv dataset,
using the horizontal embeddings increases the performance of the prediction
task, while we observe similar values of the average AUC for the Drosophila
dataset. The statistical significance of this result is confirmed by the
Welch’s T-test, for which we obtain p-values equal to $6.10\cdot 10^{-6}$,
$0.75$, $3.60\cdot 10^{-4}$ for the arXiv, Drosophila, and ff-ww-tt datasets,
respectively.

We conjecture that this outcome is due to the structure of the multiplex
network, both in terms of the size of the different layers, i.e., the number
of nodes laying on them, and of the connectivity patterns, both within the
same layer (e.g., randomness, clustering and community organization, and
across different ones, i.e., overlapping).

Table 6: Results of the experiment investigating the impact of replacing
meaningful horizontal embeddings with random embeddings. The performance is
evaluated in terms of AUC. The model with random embeddings performs worse in
two out of the three datasets compared to the model with actual embeddings,
indicating a significant decrease in predictive accuracy.

Algorithm | ff-tw-yt | Drosophila | arXiv
---|---|---|---
_MPXGAT-V_ _(actual embedding)_ | 0.83 ± (0.01) | 0.86 ± (0.01) | 0.84 ± (0.01)
_MPXGAT-V_ _(random embedding)_ | 0.80 ± (0.02) | 0.86 ± (0.01) | 0.81 ± (0.01)

##  4 Conclusions

In this paper we have introduced _MPXGAT_ , an attention based deep learning
model for the embedding of multiplex graphs. Through a comprehensive
experimental analysis we showed that MPXGAT out-performs state-of-the-art
competing algorithms. Future work will be aimed at better understanding how
the community structure withing each layer influences the performances of the
algorithm in terms of the reliability of predicted inter-layer relations. An
implementation of _MPXGAT_ in Python is available at
https://github.com/MarcoB46/MPXGAT.

## References

  * [1] M. E. Newman, The structure and function of complex networks, SIAM review 45 (2) (2003) 167–256.
  * [2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, Complex networks: Structure and dynamics, Physics reports 424 (4-5) (2006) 175–308.
  * [3] V. Latora, V. Nicosia, G. Russo, Complex networks: principles, methods and applications, Cambridge University Press, 2017.
  * [4] M. Newman, Networks, Oxford university press, 2018.
  * [5] D. Bacciu, F. Errica, A. Micheli, M. Podda, A gentle introduction to deep learning for graphs, Neural Networks 129 (2020) 203–221.
  * [6] F. Chen, Y.-C. Wang, B. Wang, C.-C. J. Kuo, Graph representation learning: a survey, APSIPA Transactions on Signal and Information Processing 9 (2020) e15.
  * [7] M. Grohe, word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data, in: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020, pp. 1–16.
  * [8] S. Khoshraftar, A. An, A survey on graph representation learning methods, arXiv preprint arXiv:2204.01855 (2022).
  * [9] Y. Rong, W. Huang, T. Xu, J. Huang, Dropedge: Towards deep graph convolutional networks on node classification, arXiv preprint arXiv:1907.10903 (2019).
  * [10] L. Lü, T. Zhou, Link prediction in complex networks: A survey, Physica A: statistical mechanics and its applications 390 (6) (2011) 1150–1170.
  * [11] S. Fortunato, Community detection in graphs, Physics reports 486 (3-5) (2010) 75–174.
  * [12] B. Perozzi, R. Al-Rfou, S. Skiena, Deepwalk: Online learning of social representations, in: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 701–710.
  * [13] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, Q. Mei, Line: Large-scale information network embedding, in: Proceedings of the 24th international conference on world wide web, 2015, pp. 1067–1077.
  * [14] A. Grover, J. Leskovec, node2vec: Scalable feature learning for networks, in: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855–864.
  * [15] W. L. Hamilton, R. Ying, J. Leskovec, Representation learning on graphs: Methods and applications, arXiv preprint arXiv:1709.05584 (2017).
  * [16] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio, Graph attention networks, arXiv preprint arXiv:1710.10903 (2017).
  * [17] M. Liu, H. Gao, S. Ji, Towards deeper graph neural networks, in: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 2020, pp. 338–348.
  * [18] H. Gao, S. Ji, Graph u-nets, in: international conference on machine learning, PMLR, 2019, pp. 2083–2092.
  * [19] T. N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, arXiv preprint arXiv:1609.02907 (2016).
  * [20] W. Hamilton, Z. Ying, J. Leskovec, Inductive representation learning on large graphs, Advances in neural information processing systems 30 (2017).
  * [21] M. Szell, R. Lambiotte, S. Thurner, Multirelational organization of large-scale social networks in an online world, Proceedings of the National Academy of Sciences 107 (31) (2010) 13636–13641.
  * [22] F. Battiston, V. Nicosia, V. Latora, Structural measures for multiplex networks, Physical Review E 89 (3) (2014) 032804.
  * [23] M. De Domenico, V. Nicosia, A. Arenas, V. Latora, Structural reducibility of multilayer networks, Nature communications 6 (1) (2015) 6864.
  * [24] S. Boccaletti, G. Bianconi, R. Criado, C. I. Del Genio, J. Gómez-Gardenes, M. Romance, I. Sendina-Nadal, Z. Wang, M. Zanin, The structure and dynamics of multilayer networks, Physics reports 544 (1) (2014) 1–122.
  * [25] M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale, D. Pedreschi, Foundations of multidimensional network analysis, in: 2011 international conference on advances in social networks analysis and mining, IEEE, 2011, pp. 485–489.
  * [26] E. Cozzo, G. F. De Arruda, F. A. Rodrigues, Y. Moreno, Multiplex networks: basic formalism and structural properties, Vol. 10, Springer, 2018.
  * [27] M. De Domenico, A. Solé-Ribalta, E. Cozzo, M. Kivelä, Y. Moreno, M. A. Porter, S. Gómez, A. Arenas, Mathematical formulation of multilayer networks, Physical Review X 3 (4) (2013) 041022.
  * [28] W. Liu, P.-Y. Chen, S. Yeung, T. Suzumura, L. Chen, Principled multilayer network embedding, in: 2017 IEEE International Conference on Data Mining Workshops (ICDMW), IEEE, 2017, pp. 134–141.
  * [29] H. Zhang, L. Qiu, L. Yi, Y. Song, Scalable multiplex network embedding., in: IJCAI, Vol. 18, 2018, pp. 3082–3088.
  * [30] Y. Shi, F. Han, X. He, X. He, C. Yang, J. Luo, J. Han, mvn2vec: Preservation and collaboration in multi-view network embedding, arXiv preprint arXiv:1801.06597 (2018).
  * [31] M. Gong, W. Liu, Y. Xie, Z. Tang, M. Xu, Heuristic 3d interactive walks for multilayer network embedding, IEEE Transactions on Knowledge and Data Engineering 34 (7) (2020) 3309–3321.
  * [32] C. Yang, A. Pal, A. Zhai, N. Pancha, J. Han, C. Rosenberg, J. Leskovec, Multisage: Empowering gcn with contextualized multi-embeddings on web-scale multipartite networks, in: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 2020, pp. 2434–2443.
  * [33] V. N. Ioannidis, A. G. Marques, G. B. Giannakis, Tensor graph convolutional networks for multi-relational and robust learning, IEEE Transactions on Signal Processing 68 (2020) 6535–6546.
  * [34] Z. Huang, X. Li, Y. Ye, M. K. Ng, Mr-gcn: Multi-relational graph convolutional networks based on generalized tensor product., in: IJCAI, Vol. 20, 2020, pp. 1258–1264.
  * [35] Y. Cen, X. Zou, J. Zhang, H. Yang, J. Zhou, J. Tang, Representation learning for attributed multiplex heterogeneous network, in: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp. 1358–1368.
  * [36] A. Behrouz, M. Seltzer, Anomaly detection in multiplex dynamic networks: from blockchain security to brain disease prediction (2022).  arXiv:2211.08378.
  * [37] A. Behrouz, F. Hashemi, Cs-mlgcn: Multiplex graph convolutional networks for community search in multiplex networks, in: Proceedings of the 31st ACM International Conference on Information & Knowledge Management, CIKM ’22, Association for Computing Machinery, New York, NY, USA, 2022, p. 3828–3832.  doi:10.1145/3511808.3557572.
URL https://doi.org/10.1145/3511808.3557572

  * [38] M. Qu, J. Tang, J. Shang, X. Ren, M. Zhang, J. Han, An attention-based collaboration framework for multi-view network representation learning (2017).  arXiv:1709.06636.
  * [39] L. Gallo, V. Latora, A. Pulvirenti, Multiplexsage: A multiplex embedding algorithm for inter-layer link prediction, IEEE Transactions on Neural Networks and Learning Systems (2023).
  * [40] K. Shu, S. Wang, J. Tang, R. Zafarani, H. Liu, User identity linkage across online social networks: A review, Acm Sigkdd Explorations Newsletter 18 (2) (2017) 5–17.
  * [41] R. Tang, S. Jiang, X. Chen, H. Wang, W. Wang, W. Wang, Interlayer link prediction in multiplex social networks: An iterative degree penalty algorithm, Knowledge-Based Systems 194 (2020) 105598.
  * [42] P. B. Jain, T. T. Nguyen, J. Mináč, L. E. Muller, R. C. Budzinski, Composed solutions of synchronized patterns in multiplex networks of kuramoto oscillators, Chaos: An Interdisciplinary Journal of Nonlinear Science 33 (10) (2023).
  * [43] M. Azmy, P. Shi, J. Lin, I. F. Ilyas, Matching entities across different knowledge graphs with graph embeddings, arXiv preprint arXiv:1903.06607 (2019).
  * [44] R. Mathon, A note on the graph isomorphism counting problem, Information Processing Letters 8 (3) (1979) 131–136.
  * [45] C.-Y. Ma, C.-S. Liao, A review of protein–protein interaction network alignment: From pathway comparison to global alignment, Computational and Structural Biotechnology Journal 18 (2020) 2647–2656.
  * [46] M. De Domenico, A. Lancichinetti, A. Arenas, M. Rosvall, Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems, Phys. Rev. X 5 (2015) 011027.  doi:10.1103/PhysRevX.5.011027.
URL https://link.aps.org/doi/10.1103/PhysRevX.5.011027

  * [47] C. Stark, B.-J. Breitkreutz, T. Reguly, L. Boucher, A. Breitkreutz, M. Tyers, Biogrid: a general repository for interaction datasets, Nucleic Acids Research 34 (Database issue) (2006) D535–D539.  doi:10.1093/nar/gkj109.
  * [48] M. Dickison, M. Magnani, L. Rossi, Multilayer Social Networks, Cambridge University Press, 2016.
  * [49] M. Qu, J. Tang, J. Shang, X. Ren, M. Zhang, J. Han, An attention-based collaboration framework for multi-view network representation learning, in: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, Association for Computing Machinery, New York, NY, USA, 2017, p. 1767–1776.  doi:10.1145/3132847.3133021.
URL https://doi.org/10.1145/3132847.3133021


A NOTE ON OPEN QUESTIONS ASKED TO ANALYSIS AND

NUMERICS CONCERNING THE HAUSDORFF MOMENT PROBLEM

Daniel Gerth and Bernd Hofmann

Abstract We address facts and open questions concerning the degree of ill-
posedness of the composite Hausdorff moment problem aimed at the recovery of a
function $x\in L^{2}(0,1)$ from elements of the infinite dimensional sequence
space $\ell^{2}$ that characterize moments applied to the antiderivative of
$x$. This degree, unknown by now, results from the decay rate of the singular
values of the associated compact forward operator $A$, which is the
composition of the compact simple integration operator mapping in $L^{2}(0,1)$
and the non-compact Hausdorff moment operator $B^{(H)}$ mapping from
$L^{2}(0,1)$ to $\ell^{2}$. There is a seeming contradiction between (a)
numerical computations, which show (even for large $n$) an exponential decay
of the singular values for $n$-dimensional matrices obtained by discretizing
the operator $A$, and (b) a strongly limited smoothness of the well-known
kernel $k$ of the Hilbert-Schmidt operator $A^{*}A$. Fact (a) suggests severe
ill-posedness of the infinite dimensional Hausdorff moment problem, whereas
fact (b) lets us expect the opposite, because exponential ill-posedness occurs
in common just for $C^{\infty}$-kernels $k$. We recall arguments for the
possible occurrence of a polynomial decay of the singular values of $A$, even
if the numerics seems to be against it, and discuss some issues in the
numerical approximation of non-compact operators.

Key words: Ill-posed linear operators, decay rates of singular values,
Hausdorff moment problem, composition of compact and non-compact operators,
kernel smoothness of Hilbert-Schmidt operators.

AMS Mathematics Subject Classification: 47A52, 47B06, 44A60, 45C05, 65R30.

##  1 Introduction

In the recent paper [5], we have dealt with properties of the forward operator
$B^{(H)}:L^{2}(0,1)\to\ell^{2}$ of the Hausdorff moment problem defined as

$[B^{(H)}z]_{j}:=\int_{0}^{1}t^{j-1}z(t)dt\qquad(j=1,2,...).$ (1)

This inverse problem, which can be written as an operator equation

$B^{(H)}\,z\,=\,y,$ (2)

aims at the recovery of a function $z\in L^{2}(0,1)$ from data of the square-
summable infinite sequence
$\left\\{\int_{0}^{1}t^{j-1}z(t)dt\right\\}_{j=1}^{\infty}$ of monomial
moments to $z$. It has been outlined ibid that $B^{(H)}$ is a non-compact and
injective bounded linear operator with non-closed range, which implies that
the operator equation (2) is ill-posed of type I in the sense of Nashed [13].
This means that there is an infinite dimensional subspace of $\ell^{2}$ on
which the inverse of $B^{(H)}$ is continuous. Despite considerable efforts in
[5], a full description of this subspace is still missing.

Open Question 1: What is the infinite dimensional subspace of $\ell^{2}$, on
which the inverse of the operator $B^{(H)}$ is continuous?

In contrast to linear ill-posed problems of type II with compact forward
operators in Hilbert spaces, where the decay rate to zero of the singular
values expresses the degree of ill-posedness in a concise way, the
characterization of the strength of ill-posedness is much more complicated
(cf. [6, 7, 12]) in non-compact cases like (2) with $B^{(H)}$ from (1). As
discussed in [5], for the Hausdorff operator $B^{(H)}$ it seems to be
important that $B^{(H)}(B^{(H)})^{*}:\ell^{2}\to\ell^{2}$ coincides with the
infinite dimensional Hilbert matrix
$\mathbb{H}=\left(\frac{1}{i+j-1}\right)_{i=1,j=1}^{\infty}$, where the
$n$-dimensional segments
$\mathbb{H}_{n}=\left(\frac{1}{i+j-1}\right)_{i=1,j=1}^{n}$ are very ill-
conditioned $n\times n$-matrices with condition numbers that grow
exponentially with $n$ as an impact of the well-known asymptotics
$\sigma_{n}(\mathbb{H}_{n})\sim\,\exp(-3.526n)$ as $n\to\infty$ (see, e.g.,
[3, Example 3.3]).

If, however, $B^{(H)}$ acts in combination with a compact operator, then the
composition operator is compact, and its singular value decay rate serves as
an appropriate measure for the corresponding ill-posedness. Such situation
occurs if we try to recover $x\in L^{2}(0,1)$ from moment data applied to the
antiderivative of $x$. In the present note, we combine the compact integration
operator $J:L^{2}(0,1)\to L^{2}(0,1)$ defined as

$[Jx](s):=\int_{0}^{s}x(t)dt\qquad(0\leq s\leq 1)$ (3)

with $B^{(H)}$ from (1) in the operator equation

$Ax\,=\,y\,,$ (4)

where the forward operator is here the composition

$A:=B^{(H)}\circ J:L^{2}(0,1)\to\ell^{2}.$ (5)

Taking into account the well-known properties of $J$ and $B^{(H)}$, the
composition $A$ from (5) turns out to be a compact and injective bounded
linear operator with non-closed range. Consequently, there exists a singular
system $\\{\sigma_{i}(A),u_{i}(A),v_{i}(A)\\}_{i=1}^{\infty}$ with complete
orthonormal systems $\\{u_{i}(A)\\}_{i=1}^{\infty}$ in $L^{2}(0,1)$ and
$\\{v_{i}(A)\\}_{i=1}^{\infty}$ in $\ell^{2}$, respectively, satisfying the
conditions $Au_{i}(A)=\sigma_{i}(A)v_{i}(A)\;(i=1,2,...)$ and the positive and
non-increasing sequence of singular values
$\\{\sigma_{i}(A)\\}_{i=1}^{\infty}$ with $\lim_{i\to\infty}\sigma_{i}(A)=0$.
In this context, we recall the following definition from [7, Definition 8],
which has been slightly updated. We also refer to [9] for the related concept
of ill-posedness intervals and further discussions.

######  Definition 1.

Let $A$ be a compact operator mapping between Hilbert spaces with non-closed
range. If there exists a constant $C>0$ and an exponent $0<\kappa<\infty$ such
that

$C\,i^{-\kappa}\leq\sigma_{i}(A)\quad\forall i\in\mathbb{N}\,,$ (6)

we call the operator equation (4) moderately ill-posed of degree at most
$\kappa$. If for all $\varepsilon>0$ , (6) does not hold with $\kappa$
replaced by $\kappa-\varepsilon$ we call (4) ill-posed of degree $\kappa$. If
(6) does not hold for arbitrarily large $\kappa$, we call (4) severely ill-
posed. Typical behaviour of severely ill-posed equations is exponential ill-
posedness, which means that there exist positive constants $C_{1},C_{2}$ and
an exponent $0<\theta<\infty$ such that the inequality

$\sigma_{i}(A)\leq C_{1}\,\exp(C_{2}\,i^{\theta})\quad\forall i\in\mathbb{N}$
(7)

holds.

Open Question 2: Is the operator equation (4) with the composite operator $A$
from (5) moderately ill-posed or, in contrast, even exponentially ill-posed?

To the best of our knowledge, this question that we ask to analysis and
numerics in this note has not yet been answered satisfactorily, despite
considerable efforts in the articles [4, 5, 8]. In Section 2 we formulate our
current knowledge about analytical results and corresponding suggestions with
respect to Open Question 2. We will formulate in this context an Open Question
3, which meets the possible occurrence of exponential ill-posedness for
integral equations kernel functions of limited smoothness. Numerical
computations of the singular value decay for $n\times n$ matrices
approximating the operator $A$ from (5) will be discussed in Section 3. This
decay is of exponential type, even if $n$ is fairly large. However, we
reiterate an explanation given in [4] that such phenomenon does not rule out
the possibility of moderate ill-posedness for the original equation (4) with
$A$ mapping between the infinite dimensional Hilbert spaces $L^{2}(0,1)$ and
$\ell^{2}$. In Section 4 we formulate some open problems on the relation
between the spectrum of non-compact operators and their discrete
approximations.

##  2 Analysis facts for the infinite dimensional composite
Hausdorff moment problem

In order to get insight into the structure of the compact operator $A$ from
(5) with $B^{(H)}$ from (1) and $J$ from (3), we recall some corresponding
results from [5]. In this context, the system $\\{L_{j}\\}_{j=1}^{\infty}$ of
normalized shifted Legendre polynomials with the explicit expressions

$L_{j}(t)=\frac{\sqrt{2j-1}}{(j-1)!}\left(\frac{d}{dt}\right)^{j-1}t^{j-1}(1-t)^{j-1}\quad(0\leq
t\leq 1),$

which is a complete orthonormal system in $L^{2}(0,1)$, plays a prominent
role. Taking into account [5, Proposition 5 and Remark 2] we can factorize the
Hausdorff (monomial) moment operator $B^{(H)}$ as $B^{(H)}=\mathbb{L}\circ Q$,
where $\mathbb{L}:\ell^{2}\to\ell^{2}$ is an infinite lower triangular matrix
occurring in the Cholesky decomposition $\mathbb{H}=\mathbb{L}\mathbb{L}^{*}$
of the infinite Hilbert matrix $\mathbb{H}$. For an explicit expression of the
entries of $\mathbb{L}$ we refer to [5, Proposition 5]. On the other hand, the
operator $Q:L^{2}(0,1)\to\ell^{2}$ defined as

$[Qx]_{j}:=\langle x,L_{j}\rangle_{L^{2}(0,1)}\quad(j=1,2,...)$ (8)

characterizes an isometry. Consequently, we can factorize the operator
equation (4) into an inner problem

$Q\,(Jx)=w\,,$ (9)

ill-posed of type II with the compact operator $Q\circ J$, and an outer
problem

$\mathbb{L}\,w\,=\,y\,$ (10)

which is ill-posed of type I.

Solving the operator equation (9) is in the papers [10, 14] considered as the
reconstruction of the derivative $x\in L^{2}(0,1)$ of the function $Jx$ based
on Legendre-type moments $\\{\int_{0}^{1}L_{j}(t)[Jx](t)dt\\}_{j=1}^{\infty}$,
or in other words as a specific approach of numerical differentiation. Due to
the isometry $Q$ and the well-known singular value asymptotics
$\sigma_{i}(J)\asymp 1/i\,$111For two decreasing sequences
$\\{s_{i}\\}_{i=1}^{\infty}$ and $\\{t_{i}\\}_{i=1}^{\infty}$ of positive
numbers, the symbol $s_{i}\asymp t_{i}$ denotes that there are constants
$0<\underline{c}\leq\overline{c}<\infty$ such that the inequalities
$\underline{c}\,s_{i}\leq t_{j}\leq\overline{c}\,s_{i}\qquad(i=1,2,...)$ are
valid. of $J$, we have that $\sigma_{i}(Q\circ J)\asymp 1/i$ and that the
operator equation (9) is moderately ill-posed of degree one.

Since $\mathbb{L}$ is the infinite lower triangular matrix of the Cholesky
decomposition of the infinite Hilbert matrix $\mathbb{H}$, we derive from the
properties of $\mathbb{H}$ (cf., e.g, [11]) that the spectrum of the non-
compact operator $\mathbb{L}$ with
$\|\mathbb{L}\|_{\mathcal{L}(\ell^{2},\ell^{2})}=\sqrt{\pi}$ contains the
whole interval $[0,\sqrt{\pi}]$ and is purely continuous, because $\mathbb{H}$
has no embedded eigenvalues.

Although the complete singular system of $J$ is available as

$\textstyle\left\\{\sigma_{i}(J)=\frac{2}{(2i-1)\pi},\;u_{i}(J)=\sqrt{2}\cos{\scriptstyle\left(i-\frac{1}{2}\right)}\pi
t,\;v_{i}(J)=\sqrt{2}\sin{\scriptstyle\left(i-\frac{1}{2}\right)}\pi
t\right\\}_{i=1}^{\infty},$

we cannot conclude from this to the singular system
$\\{\sigma_{i}(A),u_{i}(A),v_{i}(A)\\}_{i=1}^{\infty}$ of the compact operator
$A=\mathbb{L}\,\circ Q\,\circ J\,$ or at least to its singular value
asymptotics, because the orthonormal eigensystem
$\\{u_{i}(A)\\}_{i=1}^{\infty}$ is completely unknown and does not seem to
have anything to do with the eigensystem $\\{u_{i}(J)\\}_{i=1}^{\infty}$. A
visualization of this is given in Figure 1, where we plot a numerical
approximation to $u_{10}(A)$ and $u_{10}(J)$ obtained by calculating the
singular value decomposition of $1000\times 1000$ matrix approximations to $A$
and $J$.

Figure 1: Singular functions $u_{10}(A)$ and $u_{10}(J)$ computed from the
discretized operators. Obviously, the functions look completely different.

We now recall a result from [8], which leaves open whether the operator
equation (4) with the composite operator $A$ from (5) is moderately or
severely (exponentially) ill-posed in the sense of Definition 1.

######  Proposition 1 (Corollary 3.6 and Theorem 5.1 in [8]).

For the composite operator $A:L^{2}(0,1)\to\ell^{2}$ from (5) there exist
positive constants $\underline{C}$ and $\overline{C}$ such that, for
sufficiently large indices $i\in\mathbb{N}$, the inequalities

$\exp(-\underline{C}\,i)\leq\sigma_{i}(A)\leq\frac{\overline{C}}{i^{3/2}}$
(11)

concerning the singular values of $A$ are valid.

Hence, it needs further approaches to bridge the big gap of singular value
rates occurring in Proposition 1 and to decide whether the lower bound or the
upper bound in the inequality chain (11) is more realistic. Since $A$ is a
Hilbert-Schmidt operator, a conceivable alternative approach to the singular
value asymptotics of $A$ is via the smoothness of the symmetric and positive
kernel $k(s,t)$ for $(s,t)\in[0,1]\times[0,1]$ of the integral operator
$A^{*}A$ mapping in $L^{2}(0,1)$. In the appendix of [8] it has been proven
that this kernel representation attains the form of an infinite series as

$[A^{*}Ax](s)=\int\limits_{0}^{1}k(s,t)\,x(t)dt\quad\mbox{with}\quad
k(s,t)=\sum\limits_{j=1}^{\infty}\frac{(1-s^{j})(1-t^{j})}{j^{2}}\,.$ (12)

######  Proposition 2.

The kernel $k(s,t)$ from (12) is continuous on the whole closed unit square,
i.e., $k\in C([0,1]\times[0,1])$. However, there occur poles at some boundary
points of the unit square for partial derivatives of $k$ with respect to the
variable $s$. Even for the first partial derivative we have that
$\frac{\partial k(s,t)}{ds}\notin C([0,1]\times[0,1])$ due to
$\lim\limits_{s\to 1}\frac{\partial k(s,t)}{ds}=-\infty$ for $0\leq t<1$.

###### Proof.

It is evident that the functions $0\leq(1-s^{j})(1-t^{j})/j^{2}\leq 1/j^{2}$
are continuous for all $(s,t)\in[0,1]\times[0,1]$ and for all
$j\in\mathbb{N}$, which implies that the series
$\sum_{j=1}^{\infty}\frac{(1-s^{j})(1-t^{j})}{j^{2}}$ is uniformly absolutely
convergent and that the kernel function $k$ is continuous on the whole closed
unit square. By repeated formal partial differentiation of all terms inside
the sum with respect to the variable $s$ we see that poles with growing order
occur at some boundary points, which contradicts an assumption of infinite
differentiability of the kernel $k$. Just the first partial derivative of the
form $\frac{\partial
k(s,t)}{ds}=\sum_{j=1}^{\infty}\frac{-s^{j-1}(1-t^{j})}{j}$ does not attain a
finite value at the boundary points $(s,t)$ of the unit square characterized
by $s=1$ and $0\leq t<1$, because of $\lim\limits_{s\to 1}\frac{\partial
k(s,t)}{ds}=-\infty$.∎

Open Question 3: Under which conditions can an operator equation (4) with a
Hilbert-Schmidt operator $A$ mapping from $L^{2}(0,1)$ into an arbitrary
Hilbert space $Y$ with non-closed range $\mathcal{R}(A)$ be severely
(exponentially) ill-posed in the sense of Definition 1, provided that the
kernel $k\in L^{2}([0,1]\times[0,1])$ from $A^{*}A:L^{2}(0,1)\to L^{2}(0,1)$
has limited smoothness, which means that $k$ is not infinitely many
continuously differentiable on the whole closed unit square?

Answers to that question, which seems to be an open one at the moment, could
help to evaluate the impact of the limited smoothness of the kernel $k$ in
(12) on the singular value asymptotics of $A$ from (5). If severely ill-posed
equations would require infinite differentiability of the kernel on the whole
square $[0,1]\times[0,1]$, then a polynomial decay rate of $\sigma_{i}(A)$
could be concluded.

##  3 Numerical results for the discretized problem and an attempt to explain

If we would know the singular functions $u_{i}(A)\in L^{2}(0,1)$ and
$v_{i}(A)\in\ell^{2}$, then we could verify the ideal $n\times n$-diagonal
matrices

$\mathbb{D}^{A}_{n}=\left(\langle
Au_{i}(A),v_{j}(A)\rangle_{\ell^{2}}\right)_{i,j=1}^{n}={\rm
diag}(\sigma_{1}(A),...,\sigma_{n}(A))$

with the largest $n$ singular values $\sigma_{i}(A)=\langle
Au_{i}(A),v_{i}(A)\rangle_{\ell^{2}}$ as diagonal entries.

Open Question 4 : What are the singular functions $u_{i}(A)\in L^{2}(0,1)$ and
$v_{i}(A)\in\ell^{2}$ of the composite operator $A=B^{(H)}\circ J$ from (5)?

In place of $\mathbb{D}^{A}_{n}$, we can only calculate in practice for
orthonormal test bases $\\{\hat{u}_{i}\\}_{i=1}^{\infty}$ in $L^{2}(0,1)$ and
$\\{\hat{v}_{i}\\}_{i=1}^{\infty}$ in $\ell^{2}$ the $n\times n$-Gramian
matrices

$\mathbb{G}^{A}_{n}=\left(\langle
A\hat{u}_{i},\hat{v}_{j}\rangle_{\ell^{2}}\right)_{i,j=1}^{n}\qquad\mbox{with}\qquad\sigma_{i}(\mathbb{G}^{A}_{n})\leq\sigma_{i}(A)\quad(i=1,2,...,n)$
(13)

(cf. [2, Theorem 3.1]) and
$\;\lim\limits_{n\to\infty}\sigma_{1}(\mathbb{G}^{A}_{n})=\sigma_{1}(A)\;$
(cf. [2, Theorem 3.5]). As a consequence of (13), for fixed (possibly even
large) $n$, the computed matrix singular values
$\sigma_{i}(\mathbb{G}^{A}_{n})\,(i=1,2,...,n)$ by using any test bases
$\\{\hat{u}_{i}\\}_{i=1}^{\infty}$ and $\\{\hat{v}_{j}\\}_{j=1}^{\infty}$ can
only yield lower bounds in (13) of the decay rates of the singular values
$\sigma_{i}(A)$ of the operator $A$ mapping between infinite dimensional
spaces. Due to the prominent role of the Legendre polynomials, the Gramian
matrices $\mathbb{G}^{A}_{n}=\left(\langle
AL_{i},e^{(j)}\rangle_{\ell^{2})}\right)_{i,j=1}^{n}$ for
$\hat{u}_{i}(t)=L_{i}(t)\;(0\leq t\leq 1)$ and
$\hat{v}_{j}=e^{(j)}\;(e_{k}^{(j)}=\delta_{k,j})$ are of specific interest.
From [8, Lemma 5.4] we have that $\langle
AL_{1},e^{(j)}\rangle_{\ell^{2}}=\frac{1}{j+1}$ and for $2\leq i\leq n$ that
$\langle AL_{i},e^{(j)}\rangle_{\ell^{2}}=\frac{1}{j\sqrt{2j+1}}\langle
L_{i},h_{j}\rangle_{L^{2}(0,1)}$ by using the normalized monomials
$h_{j}(t)=\sqrt{2j+1}\,t^{j}$ with $\|h_{j}\|_{L^{2}(0,1)}=1$. A plot of the
first 20 singular values $\sigma_{i}(\mathbb{G}_{n}^{A})\;(i=1,\dots,20)$ and
$n=100$ is shown in Figure 2. There the exponential decay of the singular
values is easily seen.

Figure 2: Semi-logarithmic plot of the first 20 singular values of
$\mathbb{G}_{n}^{A}$ with $n=100$. As reference we plotted the function
$\exp(-1.2i+2)$. The fit of this function to the computed singular values
emphasizes the exponential decay of the latter.

The fact that the kernel $k$ from (12) is not continuously differentiable
makes severe ill-posedness of the operator equation (4) with the composite
operator $A$ from (5) quite unlikely. In contrast to that, numerical
computations of singular values of $n\times n$-matrices arising from
discretizations of $A$ with $n$ supporting points show clearly an exponential
decay, even for large $n$ (displayed with $n=10^{4}$ in Figure 3), and hence
suggest severe ill-posedness. However, there are no stringent analytical
arguments that allow us to conclude to an exponential decay of the singular
values of the operator $A:L^{2}(0,1)\to\ell^{2}$ from an exponential decay of
singular values of associated discretization matrices. Taking into account the
extreme ill-conditioning of Hilbert matrices, below we recall arguments from
[4] that might explain the exponential decay of matrix singular values even if
the original operator $A$ mapping between infinite dimensional spaces has
polynomially decreasing singular values.

Figure 3: (Plot courtesy of [4]) Semi-logarithmic plot of singular values of
$n\times n$-matrices with $n=10^{4}$ supporting points representing
discretization matrices of the operators $A$, $B^{(H)}$ and $J$. While
numerically the singular values of $J$ decay as suggested by the theory, the
singular values of $B^{(H)}\circ J$ decay exponentially in the numerical
experiments.

In [4] some arguments were made that an exponential decay of matrix singular
values is possible even if the singular values of the original operator $A$
are slowly decreasing, which we recall here. Consider the $n$-dimensional
segments $\mathbb{H}_{n}$ of the Hilbert matrix $\mathbb{H}$ introduced above.
Then the corresponding segments $\mathbb{L}_{n}$ (first $n$ columns and rows
of $\mathbb{L}$) satisfy the condition
$\mathbb{L}_{n}(\mathbb{L}_{n})^{*}=\mathbb{H}_{n}$, which implies that
$\sigma_{i}(\mathbb{L}_{n})=\sqrt{\sigma_{i}(\mathbb{H}_{n})}$. In this
context, we recall that (cf., e.g., [2, Theorem 3.5])

$1\leq\sigma_{1}(\mathbb{H}_{n})\leq\pi=\lim\limits_{n\to\infty}\sigma_{1}(\mathbb{H}_{n})=\sigma_{1}(\mathbb{H}),$

and we rewrite the inequality from [3, formula (4.8)]) as

$\sigma_{i}(\mathbb{L}_{n})\leq
2\,[\varphi(n)]^{i-1}\,(\sigma_{1}(\mathbb{H}_{n}))^{1/2}\quad(i=1,2,...,n-1),$
(14)

with the damping factor $\varphi(n)$,

$0<\varphi(n):=\exp\left(-\frac{\pi^{2}}{2\ln(8n-4)}\right)<1\,,$ (15)

which is growing with $n$ to one with an asymptotics characterized by
$1-\varphi(n)\sim 1/\ln(n)$ as $n\to\infty$. We conjecture that (14) holds
approximately as an equation if $n\gg i$, which means that for fixed and
sufficiently large $n$ the decay of $\sigma_{i}(\mathbb{L}_{n})$ with respect
to growing $i$ is exponentially as
$\sigma_{i}(\mathbb{L}_{n})\sim\exp(-K\,i)\;$ with some $K=K(n)>0$. Table 1
shows that the multiplier $\varphi(N)^{i-1}$ in (14) is rather far from one
even for $i$ of medium size and large $n$.

$\;\;\;\;\;\;n$ |  $i=2$ |  $i=4$ |  $i=10$ |  $i=51$
---|---|---|---|---
|  |  |  |
|  |  |  |
$10^{2}$ |  0.4777 |  0.1091 |  0.0013 |  $9.1932\cdot 10^{-17}$
$10^{3}$ |  0.5774 |  0.1926 |  0.0071 |  $1.1920\cdot 10^{-12}$
$10^{4}$ |  0.6459 |  0.2695 |  0.0196 |  $3.2240\cdot 10^{-10}$
$10^{6}$ |  0.7331 |  0.3940 |  0.0612 |  $1.8129\cdot 10^{-7}$
$10^{9}$ |  0.8054 |  0.5224 |  0.1426 |  $1.9982\cdot 10^{-5}$
Table 1: Values of occurring multiplier $\varphi(n)^{i-1}$ in (14).

It was conjectured in [4] that
$\lim_{n\rightarrow\infty}\sigma_{i}(\mathbb{H}_{n})=\pi$ for any fixed $i$ as
it appears that even numerically the singular values of the truncated Hilbert
matrix (and hence those of the operators $\mathbb{L}_{n}$) increase slowly as
the truncation index grows. For the multiplication operator and its
discretization an analogon to this conjecture was shown in [4], but here we
must leave it as an open question, since we only have the upper bound (14) on
the singular values, but no lower bound.

Open Question 5: Is $\lim_{n\rightarrow\infty}\sigma_{i}(\mathbb{H}_{n})=\pi$
for any fixed $i$, or, if not, what is the behaviour of
$\sigma_{i}(\mathbb{H}_{n})$ as $n$ increases?

To apply these findings for the interpretation of the singular value decay
curves in Figure 3, we denote by $A_{n}$ and $J_{n}$ $n\times
n$-discretization matrices of the operators $A=\mathbb{L}\circ Q\circ J$ and
$J$, respectively. Then we know that
$\sigma_{2i}(A_{n})\leq\sigma_{i}(\mathbb{L}_{n})\,\sigma_{i}(J_{n}),$ but the
associated curves of Figure 3 even suggest that we have for large $n$
approximately

$\sigma_{i}(A_{n})\approx\sigma_{i}(\mathbb{L}_{n})\,\sigma_{i}(J_{n})\approx
C\,\exp(-K(n)\,i)\,\sigma_{i}(J_{n}),$ (16)

where $\sigma_{i}(J_{n})\sim 1/i$ holds. If $n$ is not too large, then for
medium values of $i$ the singular value $\sigma_{i}(A_{n})$ is dominated by
$\sigma_{i}(\mathbb{L}_{n})\sim\exp(-K(n)\,i)$, because the damping multiplier
$\varphi(n)^{i-1}$ in (14) is still far from one. This explains the
exponential decay in the $\sigma_{i}(A_{n})$-curve of Figure 3 independent of
the objective singular value decay rate of the operator $A$ mapping between
infinite dimensional spaces. For making assertions concerning this decay rate,
numerics reach its limit here. Only for small $i$ and very large $n$ we have
that $\varphi(n)^{i-1}$ is close to one, which would reflect a polynomial
decay of $\sigma_{i}(J_{n})$ in $\sigma_{i}(A_{n})$ in a realistic way. One
might argue that this is visible in Figure 3 for $i<5$.

##  4 The relationships between the spectrum of non-compact operators and
their discrete approximations

The argument presented above boils down to the convergence of the matrix
approximations $\mathbb{L}_{n}$ to $B^{H}$, and the relation of the spectra.
As before, we recall the relations
$\mathbb{L}_{n}\mathbb{L}_{n}^{*}=\mathbb{H}_{n}$ and
$\mathbb{L}\mathbb{L}^{*}=\mathbb{H}$ and discuss the Hilbert matrix in the
following. To compare $\mathbb{H}$ and $\mathbb{H}_{n}$ we extend here
$\mathbb{H}_{n}$ to an infinite matrix by filling it up with zero rows and
columns such that both are operators mapping in $\ell^{2}$. In this sense,
$\mathbb{H}_{n}$ has a finite dimensional range and hence represents a compact
operator, whereas $\mathbb{H}$ is not compact. Therefore, $\mathbb{H}_{n}$
cannot converge to $\mathbb{H}$ in norm, i.e.
$\|\mathbb{H}-\mathbb{H}_{n}\|_{\mathcal{L}(\ell^{2},\ell^{2})}\not\to 0$ as
$n\to\infty$, because the norm limits of compact operators are always compact.
Related to this are the spectra, where $\mathbb{H}_{n}$ possesses a discrete
spectrum for all $n\in\mathbb{N}$, but the spectrum of $\mathbb{H}$ is purely
continuous. This raises the following question that seems to be closely
related to Open Question 4.

Open Question 6: How does
$\|\mathbb{H}-\mathbb{H}_{n}\|_{\mathcal{L}(\ell^{2},\ell^{2})}$ behave as
function of $n$?

The truncated matrices $\mathbb{H}_{n}$ have been treated in the literature
fairly extensively, but we could not find publications on the remainder. Hence
we can only speculate here, and it seems plausible that
$\|\mathbb{H}-\mathbb{H}_{n}\|_{\mathcal{L}(\ell^{2},\ell^{2})}=\pi=\|\mathbb{H}\|_{\mathcal{L}(\ell^{2},\ell^{2})}$.
To support this idea, we show in Figure 4 a plot of the norms
$\|\mathbb{H}_{n}-\mathbb{H}_{100}\|_{\mathcal{L}(\ell^{2}(n),\ell^{2}(n))}$
that we computed in the discrete finite dimensional setting with MATLAB. As
$n$ increases the norm increases. For the largest $n=12000$ we find
$\|\mathbb{H}_{n}-\mathbb{H}_{100}\|_{\mathcal{L}(\ell^{2}(n),\ell^{2}(n))}\approx
2.19$, which is still significantly smaller than $\pi$, but in terms of the
slow convergence of the term $\varphi(n)$ from (15), we might need an
unreasonable large $n$ to get close to $\pi$.

Figure 4: Numerical computation of
$\|\mathbb{H}_{n}-\mathbb{H}_{100}\|_{\mathcal{L}(\ell^{2}(n),\ell^{2}(n))}$
for $1000\leq n\leq 12000$.

## Acknowledgment

Daniel Gerth has been supported in part by the German Science Foundation (DFG)
under the grant GE 3171/1-1 (Project No. 416552794) and by the European Social
Fund in conjunction with the German Federal State of Saxony as part of the
REACT Junior Research Group project ELIOT (100602771). Bernd Hofmann has been
supported by the German Science Foundation (DFG) under the grant HO 1454/13-1
(Project No. 453804957).

## References

  * [1]
  * [2] R. C. Allen Jr., W. R. Boland,V. Faber and G. M. Wing, Singular values and condition numbers of Galerkin matrices arising from linear integral equations of the first kind, J. Math. Anal. Appl., 109(2): 564–590, 1985.
  * [3] B. Beckermann, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math., 85(4):553–577, 2000.
  * [4] D. Gerth _A note on numerical singular values of compositions with non-compact operators_ , Electronic Transactions on Numerical Analysis, 57:57–66, 2022, https://doi.org/10.1553/etna_vol57s57.
  * [5] D. Gerth, B. Hofmann, C. Hofmann and S. Kindermann, The Hausdorff moment problem in the light of ill-posedness of type I, Eurasian Journal of Mathematical and Computer Applications, 9(2):57–87, 2021.
  * [6] B. Hofmann B and G. Fleischer, Stability rates for linear ill-posed problems with compact and non-compact operators, Z. Anal. Anwendungen, 18(2):267–286, 1999.
  * [7] B. Hofmann and S. Kindermann, On the degree of ill-posedness for linear problems with non-compact operators, Methods Appl. Anal., 17(4):445–461, 2010.
  * [8] B. Hofmann and P. Mathé, The degree of ill-posedness of composite linear ill-posed problems with focus on the impact of the non-compact Hausdorff moment operator, Electronic Transactions on Numerical Analysis, 57:1–16, 2022, https://doi.org/10.1553/etna_vol57s1.
  * [9] B. Hofmann and U. Tautenhahn, On ill-posedness measures and space change in Sobolev scales, Z. Anal. Anwendungen, 16(4):979–1000, 1997.
  * [10] S. Lu, V. Naumova and S. V. Pereverzev, Legendre polynomials as a recommended basis for numerical differentiation in the presence of stochastic white noise, J. Inverse Ill-Posed Probl., 21(2):193–216, 2013.
  * [11] W. Magnus, On the spectrum of Hilbert’s matrix, Amer. J. Math., 72:699–704, 1950.
  * [12] P. Mathé, M. T. Nair and, B. Hofmann, Regularization of linear ill-posed problems involving multiplication operators, Applicable Analysis, 101(2):714–732, 2022.
  * [13] M. Z. Nashed, A new approach to classification and regularization of ill-posed operator equations, In: Inverse and Ill-posed Problems Sankt Wolfgang, 1986, volume 4 of Notes Rep. Math. Sci. Engrg. (Eds.: H. W. Engl and C. W. Groetsch), Academic Press, Boston, 1987, pp. 53–75.
  * [14] Z. Zhao, A truncated Legendre spectral method for solving numerical differentiation, Int. J. Comput. Math., 87(14):3209-3217, 2010.

Daniel Gerth,

Chemnitz University of Technology,

Faculty of Mathematics, 09107 Chemnitz, Germany,

Email<EMAIL_ADDRESS>
Bernd Hofmann,

Chemnitz University of Technology,

Faculty of Mathematics, 09107 Chemnitz, Germany,

Email<EMAIL_ADDRESS>