# ROGPL: Robust Open-Set Graph Learning via Region-Based Prototype Learning

Qin Zhang1, Xiaowei Li1, Jiexin Lu1, Liping Qiu1, Shirui Pan2, Xiaojun
Chen1111Corresponding author, Junyang Chen1

###### Abstract

Open-set graph learning is a practical task that aims to classify the known
class nodes and to identify unknown class samples as unknowns. Conventional
node classification methods usually perform unsatisfactorily in open-set
scenarios due to the complex data they encounter, such as out-of-distribution
(OOD) data and in-distribution (IND) noise. OOD data are samples that do not
belong to any known classes. They are outliers if they occur in training (OOD
noise), and open-set samples if they occur in testing. IND noise are training
samples which are assigned incorrect labels. The existence of IND noise and
OOD noise is prevalent, which usually cause the ambiguity problem, including
the intra-class variety problem and the inter-class confusion problem. Thus,
to explore robust open-set learning methods is necessary and difficult, and it
becomes even more difficult for non-IID graph data. To this end, we propose a
unified framework named ROGPL to achieve robust open-set learning on complex
noisy graph data, by introducing prototype learning. In specific, ROGPL
consists of two modules, i.e., denoising via label propagation and open-set
prototype learning via regions. The first module corrects noisy labels through
similarity-based label propagation and removes low-confidence samples, to
solve the intra-class variety problem caused by noise. The second module
learns open-set prototypes for each known class via non-overlapped regions and
remains both interior and border prototypes to remedy the inter-class
confusion problem. The two modules are iteratively updated under the
constraints of classification loss and prototype diversity loss. To the best
of our knowledge, the proposed ROGPL is the first robust open-set node
classification method for graph data with complex noise. Experimental
evaluations of ROGPL on several benchmark graph datasets demonstrate that it
has good performance.

Figure 1: Overview of the proposed ROGPL. In the latent representation space,
two modules are designed: denoising via label propagation and open-set
prototype learning via regions. In specific, we first correct noisy labels
through similarity-based label propagation and removes low-confidence samples,
to solve the intra-class variety problem caused by noise. Then we learn open-
set prototypes for each known class via non-overlapped regions and remains
both interior and border prototypes to remedy the inter-class confusion
problem. These two modules are iteratively updated under the constraints of
classification loss and prototype diversity loss.

## Introduction

Graph neural networks (GNNs) (Gilmer et al. 2017; Guo et al. 2022; Hamilton,
Ying, and Leskovec 2017; Tan et al. 2023) have become a prominent technique to
analyze graph structured data in many real-world systems, such as traffic
state prediction (Zheng et al. 2020), disease classification (Chereda et al.
2019), and user profile completion in social networks (Wong et al. 2021). The
recent success of supervised GNNs is built upon two crucial cornerstones: that
the training and test data are drawn from an identical distribution, and that
large-scale reliable  high-quality labeled  data are available for training.
However, in real-world applications, large-scale labeled data drawn from the
same distribution as test data are usually unavailable.

Real-world applications normally are in open-set scenarios (Zhang et al.
2023a; Nimah et al. 2021; Zhang et al. 2022), the existence of new-emerged
out-of-distribution (OOD) samples, i.e.samples that do not belong to any known
classes, is prevalent. They are outliers if they occur in training (OOD
noise), and open-set samples if they occur in testing. Moreover, the manually
generating clean labeled data set would involve domain experts evaluating the
quality of collected data and thus is very expensive and time-consuming
(Zhang, Luo, and Gu 2023). Alternatively, we can collect data and labels based
on web search (Yu et al. 2018), crowdsourcing (Fang, Yin, and Tao 2014; Li et
al. 2017a) and user tags (Li et al. 2017b; Xiao et al. 2015). These data and
labels are cheap but inevitably noisy (Zhang, Luo, and Gu 2023; Li et al.
2022).

The presence of OOD noise and IND noise ( in-distribution samples with
incorrect labels) can be detrimental to GNNs (Zhang et al. 2021), as they
would cause the ambiguity problem, including the intra-class variety problem
in which samples with same class labels may contain objects of different
semantic categories, and the inter-class confusion problem in which samples of
different intent classes may contain objects of similar semantic
categories(Wang et al. 2023). The open-set unknown class samples occur during
testing further complicates this problem.

Thus, it is necessary to build robust open-set learning models (Wu et al.
2021) that can learn from noisy data, achieving classification of known class
samples and identification of unknown open-set class samples during testing.
Previous works mainly concentrated on robust learning or open-set learning
separately, the problem of robust open-set learning with complex noise has not
been sufficiently explored so far (Huang, Wang, and Fang 2022; Zhang et al.
2023b), and it becomes even more difficult for non-IID graph data.

In this paper, as shown in Fig. 1, for solving the problem of open-set graph
learning with complex IND and OOD noise, we propose a new framework ROGPL to
do robust open-set node classification. It consists of two main steps:
denoising via label propagation and open-set prototype learning via regions.
Specifically, in the latent representation space, ROGPL first corrects noisy
labels through similarity-based pseudo-label propagation and remove low-
confidence samples, to solve the intra-class variety problem caused by noise.
Then the second module learns open-set prototypes for each known class via
non-overlapped regions and remains both interior and border prototypes to
remedy the inter-class confusion problem. The two modules are iteratively
updated under the constraints of both classification loss and prototype
diversity loss. Experimental evaluations of ROGPL on several benchmark graph
datasets demonstrates that it has good performance.

## Preliminaries

This study focuses on the node classification problem for a graph. A graph is
denoted as $G=(V,E,X)$, where $V=\\{v_{i}|{i=1,\ldots,N}\\}$ is a set of $N$
nodes in the graph, and $E=\\{e_{i,j}|i,j=1,\ldots,N.$ $i\neq j\\}$ is a set
of edges connecting pairs of nodes $v_{i}$ and $v_{j}$.
$X\in\mathbb{R}^{N\times s}$ denotes the feature matrix of nodes, where $s$ is
the dimension of node features. The feature vector of each node $v_{i}$ is
indicated by $x_{i}\in X$. The topological structure of $G$ is represented by
an adjacency matrix $A\in\mathbb{R}^{N\times N}$, where $A_{i,j}=1$ if the
nodes $v_{i}$ and $v_{j}$ are connected, i.e., $\exists e_{i,j}\in E$, and
otherwise $A_{i,j}=0$. The label matrix of $G$ is $Y\in\mathbb{R}^{N\times
C}$, where $C$ is the already-known node classes. If a label $c$ is assigned
to a node $v_{i}\in V$, then $y_{i,c}=1$, and otherwise, $y_{i,c}=0$.

For a typical closed-set node classification problem, a GNN encoder
$f_{\theta_{g}}$ takes the node features $X$ and adjacency matrix $A$ as
input, aggregates the neighborhood information and outputs representations.
Then, a classifier $f_{\theta_{c}}$ is used to classify the nodes into $C$
already-known classes. The GNN encoder and the classifier are optimized to
minimize the expected risk (Yu et al. 2017) in Eq. (1), assuming that the
testing data $\mathcal{D}_{te}$ and the training data $\mathcal{D}_{tr}$ have
the same feature space and label space, i.e.,

$f^{*}=arg\min_{f\in\mathcal{H}}\mathbb{E}_{(x,y)\sim\mathcal{D}_{te}}\mathbb{I}(y\neq
f(\theta_{g},\theta_{c};x,A))$ (1)

where $\mathcal{H}$ is the hypothesis space, $\mathbb{I}(\cdot)$ is the
indicator function which outputs 1 if the expression holds and 0 otherwise.
This function can be generally optimized using cross-entropy to distinguish
between known classes.

In the open-set node classification problem, given a graph $G=(V,A,X)$,
$\mathcal{D}_{tr}=(X,Y)$ denotes the training nodes. The test nodes are
denoted by $\overline{\mathcal{D}}_{te}=(X_{te},Y_{te})$, where $X_{te}=S\cup
U$, $Y_{te}=\\{1,\ldots,C,C+1,\ldots\\}$. The set $S$ is the nodes that belong
to seen classes that already appeared in $\mathcal{D}_{tr}$ and $U$ is the set
of nodes that do not belong to any seen class (i.e., unknown class nodes). The
goal of open-set node classification is to learn a $(C+1)$-$class$ classifier
$f_{\overline{\theta}_{c}}$ such that
$f(\theta_{g},\overline{\theta}_{c};X_{te},\overline{A}):\\{X_{te},\overline{A}\\}\rightarrow\overline{\mathcal{Y}}$,
$\overline{\mathcal{Y}}=\\{1,\ldots,C,unknown\\}$, by minimizing the expected
risk (Yu et al. 2017):

$\overline{f}^{*}=arg\min_{f\in\mathcal{H}}\mathbb{E}_{(x,y)\sim\mathcal{\overline{D}}_{te}}\mathbb{I}(y\neq
f(\theta_{g},\overline{\theta}_{c};x,\overline{A}))$ (2)

where $\overline{A}$ is the adjacency matrix for $X_{te}$. The predicted class
$unknown\in\overline{\mathcal{Y}}$ consists of a group of novel categories,
which may contain multiple classes. An intuitive way of transforming a close-
set classifier into an open-set classifier is thresholding (Hendrycks and
Gimpel 2017).

In the problem of Open-set node classification with IND noise and OOD noise,
given a graph $G=(V,A,X)$,
$\mathcal{D}_{tr}=(X,Y=S)=\\{x_{i},y_{i}\\}_{i=1}^{N}$ is the training set and
$\mathcal{D}_{te}=(X_{te},Y_{te}=S\cup U)$ is the test set. In
$\mathcal{D}_{tr}$, we assume that the instance-label pair $(x_{i},y_{i})$ ,
$1\leq i\leq N$, consists of three types. Let $y_{i}^{*}$ denote the ground-
truth label of $x_{i}$. A clean sample is a node whose assigned label matches
the ground-truth label, i.e., $y_{i}=y_{i}^{*}$. An IND noise sample is a node
whose assigned label does not match the ground-truth label, but the node
matches one of the classes in $S$, i.e.$y_{i}\neq y_{i}^{*},y_{i}^{*}\in S$.
An OOD noise sample is a node whose assigned label does not match the ground-
truth label and any known class label neither, i.e.$y_{i}\neq
y_{i}^{*},y_{i}^{*}\notin S$. Moreover, under the strict setting of open-set
classification, it is assumed that the ground-truth label of OOD noise
$y_{i}^{*}\notin U$, i.e., there is no overlap between the classes of OOD
noise and the unknown classes in the test set. Due to the memorization effect
(Arpit et al. 2017), noisy data can severely impair the performance of network
training. Therefore, it is desirable to develop noise-robust methods for open-
set node classification, which can handle complex and diverse noises. The
ultimate goal is to learn a noise-robust open-set node classifier that can
minimize the expected risk in Eq. (2).

## Methodology

For solving the problem of open-set graph learning with complex IND and OOD
noise, we propose a new framework ROGPL, which consists of two main steps:
denoising via label propagation and open-set prototype learning via regions.
As shown in Fig. 1, in the latent representation space, we first corrects
noisy labels through soft pseudo-label propagation and removes low-confidence
samples, to solve the intra-class variety problem caused by noise. Then we
learn open-set prototypes for each known class via non-overlapped regions and
remains both interior and border prototypes to remedy the inter-class
confusion problem. The two modules are iteratively updated under the
constraints of both classification loss and prototype diversity loss.

### Denoising via Label Propagation

Inspired by label propagation algorithms for semi-supervised
learning(Grandvalet and Bengio 2004; Iscen et al. 2018; Chandra and Kokkinos
2016), which seek to transfer labels from supervised examples to neighboring
unsupervised examples according to their similarity in feature space, we
leverage neighbour consistency to modify the supervision of each sample and to
correct noise. First, we build a $k$-nearest neighbor graph $G_{N}$ upon $Z$,
where $Z\in\mathbb{R}^{N\times K}$ is the latent representation given by an
encoder network $f_{\theta}$ by taking the nodes feature $X$,
i.e.$z_{i}=f_{\theta}(x_{i})$. $K$ indicates the dimension of the
representation vectors and is determined by the network $f_{\theta}$.

In graph $G_{N}$, the affinity matrix $W\in\mathbb{R}^{N\times N}$ is encoded
by the similarities between vertices, which is obtained by:

$W_{ij}=\left\\{\begin{aligned}
&[z_{i}^{\top}z_{j}]_{+}^{\beta},&\text{if}~{}i\neq j\land x_{j}\in
N_{k}(x_{i}),\\\ &0,&\text{otherwise.}\end{aligned}\right.$ (3)

where $N_{k}(x_{i})$ is a similarity-based neighborhood set, i.e.the set of
$k$ nearest neighbors of $x_{i}$ in $X$, and $\beta$ is a parameter for
diffusion on region manifolds(Chandra and Kokkinos 2016; Iscen et al.
2017)which we simply set as $\beta$ in our experiments.

Suppose we have clean nodes along with some noisy nodes, label propagation
spreads the label information of each node to the other nodes based on the
connectivity in the graph $G_{N}$. To weaken the influence of noisy labels, we
set $\tilde{y}_{i}=y_{i}$ to the one-hot label vector of $x_{i}$ if $x_{i}$ is
selected as a clean sample by Eq.(5), otherwise we use category prediction
which is a $C$-dimensional vector representing the belongingness of $x_{i}$ to
the $C$ known classes, i.e.$\tilde{y}_{i}=\hat{p}_{i}$, as shown in Eq. (8).
The propagation process is repeated until a global equilibrium state is
achieved, and each example is assigned to the class from which it has received
the most information.

Formally, for graph $G_{N}=(W,X)$, $D$ is the degree matrix ( a diagonal
matrix with entries $D_{ii}=\sum_{j}W_{ij}$), label propagation (Iscen et al.
2019) can be computed by minimizing

$J(\bar{Y})=\sum_{i=1}^{N}\|\bar{y}_{i}-\tilde{y}_{i}\|+\alpha\sum_{i,j=1}^{N}W_{ij}\|\frac{1}{\sqrt{D_{ii}}}\bar{y}_{i}-\frac{1}{\sqrt{D_{jj}}}\bar{y}_{j}\|^{2}$
(4)

where $\alpha$ is a regularization parameter to balance the fitting constraint
(the first term) and the smoothing term (the second term). The fitting
constraint encourages the classification of each node to their assigned label,
and the smoothing term encourages the outputs of nearby points in the graph to
be similar (Iscen et al. 2019). The obtained
$\bar{Y}=[\bar{y}_{1},\ldots,\bar{y}_{N}]\in\mathbb{R}^{N\times C}$ is the
refined soft pseudo-labels for $X$ after label propagation, further we
transform $\bar{Y}$ into hard pseudo-labels by taking the largest prediction
score to guide the training.

Finally, we use a sufficiently high threshold $\eta\in[0,1]$ to select a
reliable subset of nodes as the clean dataset:

$g_{i}=\left\\{\begin{aligned}
&1,&\text{if}~{}\bar{Y}_{iy_{i}}^{(t)}>\frac{1}{C},\\\
&\mathbb{I}[\max_{c}\bar{Y}_{ic}^{(t)}>\eta],&\text{otherwise.}~{}~{}~{}~{}~{}\\\
\end{aligned}\right.$ (5)

where $\mathbb{I}(\cdot)$ is the indicator function which outputs 1 if the
expression holds and 0 otherwise. $t$ denotes the number of iteration rounds.
$g_{i}$ is a binary indicator representing the conservation of node $v_{i}\in
V$ when $g_{i}=1$ and the removal of node $v_{i}$ when $g_{i}=0$. Thus, the
clean node set $V_{cln}=\\{v_{i}\|\forall v_{i}\in V\wedge
g_{i}=1\\}=V\backslash\\{v_{i}\|\forall v_{i}\in V\wedge g_{v}=0\\}$.

### Open-Set Prototype Learning via Regions

Overview.  With the filtered training data (clean node set $V_{cln}$),
different from the conventional classification paradigm which directly feeds
node features into a GNN to predict the class label, we aim at learning
multiple representative prototypes for each category, and predicting class
label by calculate the similarity between the node and prototypes. Upon the
latent representation $Z$, in the latent representation space, we learn the
prototypes. The prototype pool can be represented as
$P=\\{P_{1},P_{2},...,P_{C}\\}$ where $C$ is the number of known classes.
$P_{c}=\\{p_{c,1},p_{c,2},\cdots,p_{c,K_{c}}\\}\in\mathbb{R}^{K_{c}\times D}$
denotes the prototypes of category $c$ and $K_{c}$ indicates the number of
prototypes of category $c$. Given a node $x_{i}$, after obtaining the high-
level feature representation $z_{i}$, we compare it with all prototypes via
calculating cosine similarity:

$s_{c,k}^{(i)}=\frac{z_{i}\cdot p_{c,k}}{\|z_{i}\|\|p_{c,k}\|}$ (6)

After obtain similarity with all prototypes,we regard the class-wise largest
similarity score to obtain the scores of $x_{i}$ belonging to class $c$, i.e.,

$s_{c}^{(i)}=\max_{k}(s_{c,1}^{(i)},\ldots,s_{c,k}^{(i)},\ldots,s_{c,K_{c}}^{(i)})$
(7)

And the vector of score of belonging between $x_{i}$ and each class is

$\hat{p}_{i}=[s_{1}^{(i)},s_{2}^{(i)},\ldots,s_{C}^{(i)}]$ (8)

The final classification prediction of $x_{i}$ is

$\hat{y}_{i}=\arg\max_{c}{\hat{p}_{i,c}}=\arg\max_{c}{s_{c}^{(i)}}$ (9)

Open-Set Prototype Learning.  The open-set node classification is different
with the closed set classification problem, in which the class boundaries of
known classes require to be tight and clear. Traditional prototype (Yang et
al. 2018) learning normally use typical interior prototypes (such as the mean
vectors of node representation in the same class) to represent the class.
However, we argue that border prototypes are also crucial for classification,
especially for open-set scenarios, since they provide more detailed
information for preserving discrimination between classes and the information
of class boundaries. We believe the combination of interior prototypes and
border prototypes can well relieve the intra-class variety problem caused by
the noise and inter-class confusion problem, and obtain tight and clear
boundaries for known class, reserve more space for unknown classes.

Since the original training data containing IND and OOD noises, to avoid the
ambiguity problem caused by noise data, we optimize the prototype learning
based on the clean nodes $V_{cln}$ and the refined label annotations
$\bar{Y}$. We first divide the latent space into regions by clustering the
clean nodes where any clustering algorithm could be used, and we use $K$-means
for its simplicity. With the obtained clusters, under the guidance of label
matrix $\bar{Y}$, we use homogeneous clusters to update the interior
prototypes and use non-homogeneous clusters to obtain border prototypes.

To obtain the most representative interior prototype for each class, we make
interior prototypes as trainable weights of a feed forward network $f_{\phi}$
and initialized with He initialization(Liu et al. 2022). For brevity, we
denote the interior prototypes by matrix

$P_{I}=[P^{I}_{1},\ldots,P^{I}_{C}]\in\mathbb{R}^{C\times D}$ (10)

$P^{I}_{c}$ is the interior prototype for class $c$. We update the interior
prototype network $f_{\phi}$ and representation learning network $f_{\theta}$
iteratively. Since a rapidly changing of prototypes may disorganize the
representativeness of the learned prototypes and make the training process
unstable, we utilize a small learning rate to dynamically and smoothly update
the prototypes through back-propagation:

$P^{I}_{c,(t)}=P^{I}_{c,(t-1)}-\varphi\frac{\partial\mathcal{L}}{\partial
P^{I}_{c}}$ (11)

where $P^{I}_{c,(t)}$ and $P^{I}_{c,(t-1)}$ are the interior prototype of
class $c$ at epoch $t$ and epoch $t-1$ respectively. $\mathcal{L}$ is the
total loss shown as Eq. (15). $\varphi$ is the learning rate which is set as
small numbers. Note that here we only use the samples in the homogeneous
clusters to update the corresponding interior prototypes, i.e.we select the
regions containing nodes belonging to a single class, and use these nodes to
update the interior representative prototype for the corresponding class.

Towards border prototypes, the idea is to analyze those regions which contain
nodes belonging to different classes. We obtain border prototypes by computing
the mean vector of nodes with the same class label in non-homogeneous
clusters. For example, suppose a cluster $R_{k}$ insists of samples of two
classes,
i.e.$M_{k}=\bar{V}_{1}^{k}\cup\bar{V}_{2}^{k}\cup\ldots\cup\bar{V}_{C}^{k}$,
where $\bar{V}_{c}^{k}$ consists of a couple of nodes from class $c$, and
there exists $m,n\in\\{1,\ldots,C\\}$ such that
$\bar{V}_{m}^{k}\neq\emptyset~{}\wedge~{}\bar{V}_{n}^{k}\neq\emptyset$, then
we can obtain border prototypes of class $m$ and $n$ by:

$P_{m}^{k}=\frac{1}{\|\bar{V}_{m}^{k}\|}\sum_{v_{i}\in\bar{V}_{m}^{k}}z_{i},~{}~{}P_{n}^{k}=\frac{1}{\|\bar{V}_{n}^{k}\|}\sum_{v_{i}\in\bar{V}_{n}^{k}}z_{i}$
(12)

It is the same for clusters that contain nodes from several different classes.

We utilize cross-entropy loss to train the encoder network $f_{\theta}$ and
prototype network $f_{\phi}$ on clean nodes $V_{cln}$, under the supervision
of refined class label $\bar{Y}$:

$\mathcal{L}_{cls}=-\frac{1}{N}\sum_{i=1}^{N}\bar{y}_{i}\log\frac{exp(s_{\bar{y}_{i}}^{(i)}/T)}{\sum_{c=1}^{C}\exp{(s_{c}^{(i)}/T)}}$
(13)

where $T$ is a temperature hyperparameter that we introduced to make the
results more differentiated (Agarwala et al. 2020).

With the adoption of both interior and border prototypes, the diversity of
prototypes within a class can be well mined. To further relieve the inter-
class confusion problem, we hope the prototypes of different categories also
away from each other. Thus, we enhance the diversity of the prototypes of
known classes by adopting the orthogonal constraint to keep the orthogonality
of interior prototypes by using the diversity loss:

$\mathcal{L}_{div}=\|P_{I}P_{I}^{\top}-I\|_{F}^{2}$ (14)

where $\|\cdot\|_{F}$ is the Frobenius-norm and $I$ is the identity matrix of
any desired dimension. The overall loss function of ROGPL is:

$\mathcal{L}=\mathcal{L}_{cls}+\lambda\mathcal{L}_{div}$ (15)

where $\lambda$ is the loss hyper-parameter.

So far, we obtain interior prototype and border prototypes for each known
class, and we predict the class label of clean nodes through Eq. (7) and (9).
To make a hard prediction, we adopt a probability threshold $\tau$, such that
a testing point $x_{i}$ is deemed as an unknown class sample if
$\max_{c}\hat{p}_{i,c}<\tau$.

## Experiments

We design our experiments to evaluate ROGPL, focusing on the following
aspects: open-set classification comparison, robustness analysis, and ablation
study. Codes will be available online.

### Experimental Setup

Dataset and Metrics.  To evaluate the performance of the proposed framework
for robust open-set node classification, We conducted experiments on three
main benchmark graph datasets (Wu, Pan, and Zhu 2020; Zhu et al. 2022), namely
Cora222https://graphsandnetworks.com/the-cora-dataset/,
Citeseer333https://networkrepository.com/citeseer.php (Yang, Cohen, and
Salakhudinov 2016), and Coauthor-
CS444https://docs.dgl.ai/en/0.8.x/generated/dgl.data.Coauthor-
CSDataset.html (Zhou et al. 2023), which are widely used citation network
datasets. The statistics of the datasets are presented in the Appendix. In
terms of the metrics, following the study of Wu et al. (Wu et al. 2021), we
adopt macro-F1 and AUROC to measure the performance.

Implementation Details.  In the experiments, we adopt GCN (Kipf and Welling
2016) as backbone neural network for the encoder $f_{\theta}$, configured with
two hidden layers with a dimension of 128. The prototype network $f_{\phi}$
configured with a linear layer with a dimension of $C+1$. ROGPL is implemented
with PyTorch and the networks are optimized using adaptive moment estimation
with a learning rate of $10^{-3}$. The balance parameters $\lambda$ is set to
$10^{-2}$. The threshold $\eta$ were selected by a grid search in the range
from $0$ to $1$ with a step of $10^{-1}$. The number of nearest neighbors $k$
were selected by a grid search in the range from $30$ to $35$ with a step of
$1$.

For each experiment, the baselines and the proposed method were applied on the
same training, validation, and testing datasets. All the experiments were
conducted on a workstation equipped with an Intel(R) Xeon(R) Gold 6226R CPU
and an Nvidia A100 GPU.

Test Settings.  To evaluate the performance of open-set node classification,
for each dataset, the data of several classes were held out as the unknown
classes for testing and the remaining classes were considered as the known
classes. 70% of the known class nodes were sampled for training, 10% for
validation, and 20% for testing.

To assess the performance of the proposed ROGPL framework on graph data with
different noises, we tested it with mixed IND and OOD noise. In the training
set, we randomly selected 5%/25%/50% of the known class samples to be IND
noise, and randomly replaced their ground-truth labels with wrong known class
labels. Then, we used the nodes from neither the known classes of the training
set nor the unknown classes of the test set as OOD noise, and randomly
assigned known class labels to them. The samples with right known class labels
(clean data), the known class samples with incorrect labels (IND noise) and
the far-away unknown class samples with wrong known class labels (OOD noise)
constitute the final training set. The test set includes the known class
samples and the unknown class samples, where the unknown classes are different
from the classes of OOD noise. The setting of inductive learning was adopted
for all the experiments, where no information about the unknown class in the
test set (such as the feature $x_{i}$ or other side information of unknown
classes) is utilized during training or evaluation.

Methods | GCN_soft | GCN_sig | GCN_soft$\\_\tau$ | GCN_sig$\\_\tau$ | NWR_$\tau$ | Openmax | OpenWGL | $\mathcal{G}^{2}Pxy$ |  NGC |  PNP | ROGPL
---|---|---|---|---|---|---|---|---|---|---|---
Cora | 5% | F1 | 63.73 | 64.12 | 70.53 | 57.80 | 69.41 | 60.40 | 73.03 | 72.00 | 59.69 | 70.26 | 78.36
AUROC | fail | fail | 82.82 | 81.40 | 75.05 | 67.26 | 79.36 | 78.30 | 78.20 | 82.04 | 91.00
25% | F1 | 64.31 | 63.78 | 70.69 | 66.91 | 68.98 | 59.82 | 70.58 | 69.92 | 52.13 | 64.78 | 77.59
AUROC | fail | fail | 77.92 | 79.94 | 81.69 | 87.61 | 77.90 | 77.36 | 80.22 | 84.87 | 91.59
50% | F1 | 60.96 | 59.73 | 62.53 | 62.93 | 61.93 | 53.50 | 63.59 | 57.52 | 62.70 | 66.29 | 76.90
AUROC | fail | fail | 79.46 | 78.52 | 78.73 | 80.88 | 85.40 | 63.68 | 83.64 | 83.54 | 90.47
Citeseer | 5% | F1 | 39.03 | 37.74 | 59.13 | 59.93 | 52.28 | 33.23 | 59.87 | 52.40 | 59.44 | 59.99 | 62.24
AUROC | fail | fail | 85.67 | 85.56 | 76.13 | 55.01 | 86.08 | 67.75 | 84.05 | 85.70 | 87.84
25% | F1 | 38.30 | 38.02 | 23.04 | 57.79 | 48.51 | 36.70 | 57.42 | 53.53 | 55.42 | 59.83 | 63.89
AUROC | fail | fail | 84.50 | 82.26 | 72.59 | 75.68 | 82.34 | 53.97 | 80.46 | 84.03 | 88.84
50% | F1 | 30.39 | 31.71 | 35.41 | 35.54 | 35.65 | 24.83 | 40.46 | 41.92 | 56.39 | 51.81 | 57.08
AUROC | fail | fail | 64.20 | 50.74 | 61.22 | 67.89 | 79.54 | 38.03 | 77.43 | 80.40 | 85.64
Coauthor-CS | 5% | F1 | 75.44 | 76.50 | 76.63 | 71.70 | 75.43 | 62.68 | 74.09 | 83.45 | 77.61 | 83.56 | 81.68
AUROC | fail | fail | 83.14 | 86.61 | 89.57 | 81.65 | 87.39 | 82.95 | 85.57 | 85.55 | 93.25
25% | F1 | 74.58 | 75.19 | 81.92 | 73.38 | 65.64 | 66.38 | 72.98 | 67.21 | 69.18 | 79.37 | 83.32
AUROC | fail | fail | 87.77 | 88.35 | 88.69 | 80.62 | 86.35 | 86.03 | 85.11 | 85.47 | 94.06
50% | F1 | 72.93 | 60.77 | 68.87 | 52.63 | 78.66 | 59.97 | 54.70 | 72.96 | 63.06 | 68.40 | 79.29
AUROC | fail | fail | 75.02 | 83.97 | 87.58 | 81.48 | 85.13 | 72.87 | 84.27 | 84.85 | 93.31
Table 1: Comparison of open-set node classification in test F1-score and AUROC
(%) on three datasets, where IND noise (5%/ 25%/ 50%) and near OOD noise is
injected into training set.

Baselines.  We compare ROGPL with 10 baselines, which are from three
categories.

  * •

1) Closed-set classification methods: GCN_soft and GCN_sig. They are GCNs
(Kipf and Welling 2016) with a softmax layer or a multiple 1-vs-rest of
sigmoids layer as output layer.

  * •

2) Open-set classification methods: GCN_soft_$\tau$, GCN_sig_$\tau$,
NWR_$\tau$ (Tang, Yang, and Li 2022), Openmax (Bendale and Boult 2016),
OpenWGL (Wu, Pan, and Zhu 2020) and $\mathcal{G}^{2}Pxy$ (Zhang et al. 2023b).
Specifically, GCN_soft_$\tau$, GCN_sig_$\tau$ and NWR_$\tau$ are GCN_soft,
GCN_sig and the original NWR (Tang, Yang, and Li 2022) methods by added a
threshold chosen from $\\{0.1,0.2,\ldots,0.9\\}$ to perform open-set
recognition. Openmax (Bendale and Boult 2016) is an open-set recognition model
based on “activation vectors” (i.e. penultimate layer of the network). OpenWGL
(Wu, Pan, and Zhu 2020) and $\mathcal{G}^{2}Pxy$ (Zhang et al. 2023b) are two
open-set node classification methods for graph data, which has no robust
learning ability.

  * •

3) Robust open-set classification methods: NGC (Wu et al. 2021) and PNP (Sun
et al. 2022). NGC (Wu et al. 2021) is an open-world noisy data learning method
for image classification which employs geometric structure and model
predictive confidence to collect clean sample. PNP_$\tau$ (Sun et al. 2022) is
a robust classifier learning method for image data with IND and OOD noise,
where data augmentation is used to help the identification of noisy samples.
To perform open-set recognition, we adopt a threshold chosen from
$\\{0.1,0.2,\ldots,0.9\\}$ to PNP.

Note that the graph data are first embedded by a GCN before being feed into
the models that cannot handle graph data. A detailed introduction can be found
in the Appendix.

### Open-Set Node Classification with Complex Noisy Graph Data

Considering that real-world scenarios are complex and noisy data vary across
different tasks, we assessed the proposed model for open-set classification
with IND noise and two types of OOD data: near OOD data and far OOD data.
Here, OOD data include OOD noise in the training set and out-of-distribution
samples of unknown classes that occur during testing.

#### Open-Set Classification with IND Noise and Near OOD Data.

In this experiment, for each dataset, following the setting of OpenWGL (Wu,
Pan, and Zhu 2020), the data of the last class were held out as the unknown
class for testing, and the data of the second last class which were re-
assigned with random known class labels were set as the OOD noise data and
injected into the training set. The remaining classes were considered as known
classes, while the known class samples in training set were re-assigned with
wrong known class labels with a rate of 5%, 25% and 50% (i.e.IND noise rate),
respectively.

Table 1 lists the macro-F1 and AUROC scores for open-set node classification
with near OOD noise and different proportions of IND noise. It is observed
that ROGPL generally obtain the best performance on the benchmarks. This shows
that ROGPL can better distinguish between a known class and an unknown class,
even though there is a large amount of complex and diverse noises during
training. Specifically, ROGPL achieves an average of 6.23% improvement over
the second-best method (PNP) in terms of F1 score and an average of 6.62%
improvement in terms of AUROC on the three datasets.

Furthermore, we examined the detailed classification accuracy in terms of
known classes and unknown classes. We found that to gain the ability of
unknown class detection, compared to the closed-set classifier, there is a
slight decrease in the performance of known class classification, i.e., from
86.33% (GCN_soft) to 75.48% (ROGPL) on average, while the unknown class
detection accuracy is increased from 0% to a remarkable 83.78% on average.
Moreover, compared to other open-set node classification methods, such as
$\mathcal{G}^{2}Pxy$, ROGPL achieves an average improvement of 11.9%, 13.29%
and 9.94% in accuracy of known classification, unknown detection and overall
classification, respectively. The average improvement in F1 score is 9.94%.
Details are provided in the Appendix.

Methods | 5% far OOD noise | 25% far OOD noise
---|---|---
Cora | Citeseer | Coauthor-CS | Cora | Citeseer | Coauthor-CS
F1 | AUROC | F1 | AUROC | F1 | AUROC | F1 | AUROC | F1 | AUROC | F1 | AUROC
GCN_soft | 64.67 | fail | 39.04 | fail | 60.36 | fail | 63.12 | fail | 39.04 | fail | 77.08 | fail
GCN_sig | 64.11 | fail | 41.33 | fail | 69.32 | fail | 63.44 | fail | 40.78 | fail | 65.94 | fail
GCN_soft$\\_\tau$ | 71.81 | 74.61 | 58.57 | 82.35 | 65.81 | 78.37 | 70.38 | 75.13 | 56.09 | 81.61 | 60.48 | 72.37
GCN_sig$\\_\tau$ | 62.65 | 77.54 | 54.60 | 84.58 | 54.23 | 86.73 | 69.23 | 76.38 | 57.41 | 81.81 | 57.75 | 84.31
NWR_$\tau$ | 71.94 | 76.58 | 48.35 | 75.06 | 79.46 | 87.65 | 68.79 | 80.67 | 48.08 | 71.67 | 54.77 | 83.76
Openmax | 28.37 | 79.06 | 26.64 | 81.17 | 66.90 | 82.10 | 31.41 | 84.40 | 15.55 | 79.03 | 67.23 | 85.07
OpenWGL | 71.83 | 76.76 | 58.51 | 84.78 | 76.38 | 87.24 | 67.87 | 74.50 | 57.28 | 82.75 | 75.71 | 85.10
$\mathcal{G}^{2}Pxy$ | 69.24 | 80.67 | 43.26 | 62.53 | 66.98 | 69.57 | 66.54 | 75.26 | 41.67 | 60.95 | 70.45 | 68.34
NGC | 57.58 | 78.57 | 52.30 | 78.07 | 66.96 | 84.47 | 59.86 | 76.88 | 55.41 | 81.22 | 64.84 | 83.96
PNP | 72.21 | 79.51 | 60.22 | 83.93 | 77.50 | 87.42 | 72.19 | 77.47 | 57.58 | 81.94 | 81.34 | 84.23
ROGPL | 77.62 | 87.89 | 60.90 | 84.50 | 83.11 | 92.34 | 76.31 | 86.48 | 58.08 | 85.49 | 82.06 | 89.78
Table 2: Comparison of open-set node classification in test F1-score and AUROC
(%) on three datasets, where IND noise (5%) and far OOD noise (5% / 25%) from
the Pubmed dataset is injected into the training set.

#### Open-Set Node Classification with IND Noise and Far OOD Data.

To investigate the effect of rough OOD noise, we used OOD samples that are
from different dataset as the source of OOD noise. Specifically, we randomly
selected samples of the first two classes from Pubmed (Hu et al. 2020) and
mixed them with data from Cora, Citeseer and Coauthor-CS to create the
training set with far OOD noise, where the OOD noise rate is set to 5% or 25%.
Each node from Pubmed was randomly assigned to a known class label, and edges
between the node and its $k$-nearest neighbors were added, where $k$ is a
random integer in the range from 1 to 5. We also added some samples from the
remaining categories in the Pubmed dataset to the test set in corresponding
proportion, to evaluate the performance of ROGPL on the samples from far open-
set. The other settings are the same as the experiment of near OOD data, and
the IND noise rate is set as 5%.

The results of open-set node classification with far OOD noise are presented
in Table 2. The results show that ROGPL generally outperforms the baselines,
achieving an average improved of 2.84% in F1 and an average improvement of
5.33% in AUROC, compared to the global second-best method PNP. The detailed
classification accuracy in terms of known classes and unknown classes with far
OOD noise are given in the Appendix.

### Robustness Analysis under Different Noise Rate

In this section, we evaluate the robustness of ROGPL for different levels of
IND and OOD noise for the open-set node classification task. We first examine
how ROGPL reacts to different IND noise rate. We kept the OOD noise rate
constant and used the same setting as the experiment of Table 1, while we
varied the IND noise rate from 0%, 5%, 25%, 50% to 75%. Fig. 2(a) and Fig.
2(b) show the results on the Cora and Citeseer datasets, respectively. We
observe that ROGPL maintains a relatively stable performance when the noise
rate is within a certain range, for example no more than 50%. However, once
the IND noise exceeds a certain threshold, ROGPL’s performance drops sharply.

Additionally, we investigate the performance of ROGPL in terms of different
OOD noise rate, by keeping the IND noise rate constant as 5%, while varying
the far OOD noise rate from 0%, 5%, 25%, 50% to 75% . The results on Cora and
Citeseer are shown in Fig.2(c) and Fig. 2(d)respectively. It can be observed
that ROGPL maintains a surprisingly stable performance even with large amounts
of far OOD noise in the training data, which demonstrates the strong
robustness of ROGPL against OOD noise.

(a) Cora

(b) Citeseer

(c) Cora

(d) Citeseer

Figure 2: The performance of ROGPL with respect to different IND noise rate and OOD noise rate on Cora and Citeseer datasets.  Methods | Cora | Citeseer | Coauthor-CS
---|---|---|---
F1 | AUROC | F1 | AUROC | F1 | AUROC
ROG${}_{PL}\neg G_{N}$ | 74.87 | 89.90 | 61.79 | 86.94 | 81.08 | 91.10
ROG${}_{PL}\neg$denoise | 77.24 | 86.56 | 61.24 | 86.99 | 81.03 | 87.86
ROG${}_{PL}\neg\mathcal{L}_{div}$ | 73.67 | 89.85 | 60.35 | 86.73 | 79.88 | 90.32
ROG${}_{PL}\neg$region | 76.54 | 84.11 | 61.63 | 87.49 | 80.89 | 86.45
ROGPL | 78.36 | 91.00 | 62.24 | 87.84 | 81.68 | 93.25
Table 3: Ablation study of robust open-set node classification in test F1
score and AUROC (%) on three datasets, where IND noise (5%) and near OOD noise
is injected into the training set.

### Ablation Study

We compare variants of ROGPL in an ablation study to evaluate the effect of
its main modules and settings:

  * •

ROG${}_{PL}\neg G_{N}$: a variant of ROGPL without building $k$-nearest
neighbor graph $G_{N}$, and original graph $G$ is used in the label
propagation stage.

  * •

ROG${}_{PL}\neg$denoise: a variant of ROGPL without the label propagation
based denoising module.

  * •

ROG${}_{PL}\neg$region: a variant of ROGPL without clustering, i.e.the
interior prototype of each class is updated by the clean nodes from all
classes, and there is no border prototypes.

  * •

ROG${}_{PL}\neg\mathcal{L}_{div}$: a variant of ROGPL with loss
$\mathcal{L}_{div}$ removed. We only utilize classification loss
$\mathcal{L}_{cls}$ to train the encoder network $f_{\theta}$ and prototype
network $f_{\phi}$.

The performance of the proposed method and its four variants are presented in
Table 3. The results demonstrate that both label propagation based denoising
module and region-based prototype learning module are important and building
$k$nn graph $G_{N}$ is necessary. The large gap of performance between  ROGPL
and  ROG${}_{PL}\neg$region  verifies the contribution of open-set prototypes
on open-set node classification.

## Conclusion

This paper introduced a novel prototype learning based robust open-set node
classification method to learn an open-set classifier from graphs with mixed
IND and OOD noisy nodes. By correcting noisy labels through similarity-based
label propagation and removing low-confidence samples, the proposed method
relieve the intra-class variety caused by noise. Further, by learning open-set
prototypes via non-overlapped regions and remaining both interior and border
prototypes, the method can remedy the inter-class confusion problem, and save
more space for open-set classes. To the best of our knowledge, the proposed
ROGPL is the first robust open-set node classification method for graph data
with complex noise. Experimental evaluations on several benchmark graph
datasets demonstrates its good performance.

## Acknowledgments

This research was supported by National Natural Science Foundation of China
(62206179, 92270122), Guangdong Provincial Natural Science Foundation
(2022A1515010129, 2023A1515012584), University stability support program of
Shenzhen (20220811121315001), Shenzhen Research Foundation for Basic Research,
China (JCYJ20210324093000002).

## References

  * Agarwala et al. (2020) Agarwala, A.; Pennington, J.; Dauphin, Y.; and Schoenholz, S. 2020.  Temperature check: theory and practice for training models with softmax-cross-entropy losses.  arXiv:2010.07344.
  * Arpit et al. (2017) Arpit, D.; Jastrzebski, S.; Ballas, N.; Krueger, D.; Bengio, E.; Kanwal, M. S.; Maharaj, T.; Fischer, A.; Courville, A.; Bengio, Y.; et al. 2017.  A closer look at memorization in deep networks.  In _International conference on machine learning_ , 233–242. PMLR.
  * Bendale and Boult (2016) Bendale, A.; and Boult, T. E. 2016.  Towards open set deep networks.  In _IEEE conference on computer vision and pattern recognition_ , 1563–1572.
  * Chandra and Kokkinos (2016) Chandra, S.; and Kokkinos, I. 2016.  Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs.  In _Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part VII 14_ , 402–418. Springer.
  * Chereda et al. (2019) Chereda, H.; Bleckmann, A.; Kramer, F.; Leha, A.; and Beissbarth, T. 2019.  Utilizing Molecular Network Information via Graph Convolutional Neural Networks to Predict Metastatic Event in Breast Cancer.  In _GMDS_ , 181–186.
  * Fang, Yin, and Tao (2014) Fang, M.; Yin, J.; and Tao, D. 2014.  Active learning for crowdsourcing using knowledge transfer.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 1809–1815.
  * Gilmer et al. (2017) Gilmer, J.; Schoenholz, S. S.; Riley, P. F.; Vinyals, O.; and Dahl, G. E. 2017.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , 1263–1272. PMLR.
  * Grandvalet and Bengio (2004) Grandvalet, Y.; and Bengio, Y. 2004.  Semi-supervised learning by entropy minimization.  _Advances in neural information processing systems_ , 17.
  * Guo et al. (2022) Guo, K.; Zhou, K.; Hu, X.; Li, Y.; Chang, Y.; and Wang, X. 2022.  Orthogonal graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 3996–4004.
  * Hamilton, Ying, and Leskovec (2017) Hamilton, W.; Ying, Z.; and Leskovec, J. 2017.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30.
  * Hendrycks and Gimpel (2017) Hendrycks, D.; and Gimpel, K. 2017.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  _International Conference on Learning Representations_.
  * Hu et al. (2020) Hu, W.; Fey, M.; Zitnik, M.; Dong, Y.; Ren, H.; Liu, B.; Catasta, M.; and Leskovec, J. 2020.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ , 33: 22118–22133.
  * Huang, Wang, and Fang (2022) Huang, T.; Wang, D.; and Fang, Y. 2022.  End-to-end open-set semi-supervised node classification with out-of-distribution detection.  In _IJCAI_ , 2087–2093.
  * Iscen et al. (2018) Iscen, A.; Tolias, G.; Avrithis, Y.; and Chum, O. 2018.  Mining on manifolds: Metric learning without labels.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 7642–7651.
  * Iscen et al. (2019) Iscen, A.; Tolias, G.; Avrithis, Y.; and Chum, O. 2019.  Label propagation for deep semi-supervised learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 5070–5079.
  * Iscen et al. (2017) Iscen, A.; Tolias, G.; Avrithis, Y.; Furon, T.; and Chum, O. 2017.  Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2077–2086.
  * Kipf and Welling (2016) Kipf, T. N.; and Welling, M. 2016.  Semi-supervised classification with graph convolutional networks.  arXiv:1609.02907.
  * Li et al. (2022) Li, S.; Xia, X.; Ge, S.; and Liu, T. 2022.  Selective-supervised contrastive learning with noisy labels.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 316–325.
  * Li et al. (2017a) Li, W.; Wang, L.; Li, W.; Agustsson, E.; and Van Gool, L. 2017a.  Webvision database: Visual learning and understanding from web data.  arXiv:1708.02862.
  * Li et al. (2017b) Li, Y.; Yang, J.; Song, Y.; Cao, L.; Luo, J.; and Li, L.-J. 2017b.  Learning from noisy labels with distillation.  In _Proceedings of the IEEE international conference on computer vision_ , 1910–1918.
  * Liu et al. (2022) Liu, Y.; Jin, M.; Pan, S.; Zhou, C.; Zheng, Y.; Xia, F.; and Philip, S. Y. 2022\.  Graph self-supervised learning: A survey.  _IEEE Transactions on Knowledge and Data Engineering_ , 35(6): 5879–5900.
  * Nimah et al. (2021) Nimah, I.; Fang, M.; Menkovski, V.; and Pechenizkiy, M. 2021.  ProtoInfoMax: Prototypical Networks with Mutual Information Maximization for Out-of-Domain Detection.  In Moens, M.-F.; Huang, X.; Specia, L.; and Yih, S. W.-t., eds., _Findings of the Association for Computational Linguistics: EMNLP 2021_ , 1606–1617. Punta Cana, Dominican Republic: Association for Computational Linguistics.
  * Sun et al. (2022) Sun, Z.; Shen, F.; Huang, D.; Wang, Q.; Shu, X.; Yao, Y.; and Tang, J. 2022.  Pnp: Robust learning from noisy labels by probabilistic noise prediction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 5311–5320.
  * Tan et al. (2023) Tan, R.; Tan, Q.; Zhang, Q.; Zhang, P.; Xie, Y.; and Li, Z. 2023.  Ethereum fraud behavior detection based on graph neural networks.  _Computing_ , 1–28.
  * Tang, Yang, and Li (2022) Tang, M.; Yang, C.; and Li, P. 2022.  Graph auto-encoder via neighborhood wasserstein reconstruction.  arXiv:2202.09025.
  * Wang et al. (2023) Wang, B.; Yang, K.; Zhao, Y.; Long, T.; and Li, X. 2023.  Prototype-based intent perception.  _IEEE Transactions on Multimedia_.
  * Wong et al. (2021) Wong, R. Y. M.; Cheung, C. M.; Xiao, B.; and Thatcher, J. B. 2021.  Standing up or standing by: Understanding bystanders’ proactive reporting responses to social media harassment.  _Information Systems Research_ , 32(2): 561–581.
  * Wu, Pan, and Zhu (2020) Wu, M.; Pan, S.; and Zhu, X. 2020.  Openwgl: Open-world graph learning.  In _IEEE international conference on data mining_ , 681–690.
  * Wu et al. (2021) Wu, Z.-F.; Wei, T.; Jiang, J.; Mao, C.; Tang, M.; and Li, Y.-F. 2021.  NGC: A unified framework for learning with open-world noisy data.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 62–71.
  * Xiao et al. (2015) Xiao, T.; Xia, T.; Yang, Y.; Huang, C.; and Wang, X. 2015.  Learning from massive noisy labeled data for image classification.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2691–2699.
  * Yang et al. (2018) Yang, H.-M.; Zhang, X.-Y.; Yin, F.; and Liu, C.-L. 2018.  Robust classification with convolutional prototype learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 3474–3482.
  * Yang, Cohen, and Salakhudinov (2016) Yang, Z.; Cohen, W.; and Salakhudinov, R. 2016.  Revisiting semi-supervised learning with graph embeddings.  In _International conference on machine learning_ , 40–48. PMLR.
  * Yu et al. (2018) Yu, X.; Liu, T.; Gong, M.; and Tao, D. 2018.  Learning with biased complementary labels.  In _Proceedings of the European conference on computer vision (ECCV)_ , 68–83.
  * Yu et al. (2017) Yu, Y.; Qu, W.-Y.; Li, N.; and Guo, Z. 2017.  Open-category classification by adversarial sample generation.  In _International Joint Conference on Artificial Intelligence_ , 3357–3363.
  * Zhang et al. (2021) Zhang, C.; Bengio, S.; Hardt, M.; Recht, B.; and Vinyals, O. 2021.  Understanding deep learning (still) requires rethinking generalization.  _Communications of the ACM_ , 64(3): 107–115.
  * Zhang, Luo, and Gu (2023) Zhang, C.; Luo, L.; and Gu, B. 2023.  Denoising Multi-Similarity Formulation: A Self-Paced Curriculum-Driven Approach for Robust Metric Learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 11183–11191.
  * Zhang et al. (2023a) Zhang, Q.; Chen, S.; Xu, D.; Cao, Q.; Chen, X.; Cohn, T.; and Fang, M. 2023a.  A Survey for Efficient Open Domain Question Answering.  In Rogers, A.; Boyd-Graber, J.; and Okazaki, N., eds., _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 14447–14465. Toronto, Canada: Association for Computational Linguistics.
  * Zhang et al. (2022) Zhang, Q.; Li, Q.; Chen, X.; Zhang, P.; Pan, S.; Fournier-Viger, P.; and Huang, J. Z. 2022.  A Dynamic Variational Framework for Open-World Node Classification in Structured Sequences.  In _2022 IEEE International Conference on Data Mining (ICDM)_ , 703–712. IEEE.
  * Zhang et al. (2023b) Zhang, Q.; Shi, Z.; Zhang, X.; Chen, X.; Fournier-Viger, P.; and Pan, S. 2023b.  G2Pxy: generative open-set node classification on graphs with proxy unknowns.  In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence_ , 4576–4583.
  * Zheng et al. (2020) Zheng, C.; Fan, X.; Wang, C.; and Qi, J. 2020.  Gman: A graph multi-attention network for traffic prediction.  In _AAAI Conference on Artificial Intelligence_ , 1234–1241.
  * Zhou et al. (2023) Zhou, B.; Jiang, Y.; Wang, Y.; Liang, J.; Gao, J.; Pan, S.; and Zhang, X. 2023.  Robust graph representation learning for local corruption recovery.  In _Proceedings of the ACM Web Conference 2023_ , 438–448.
  * Zhu et al. (2022) Zhu, Q.; Zhang, C.; Park, C.; Yang, C.; and Han, J. 2022.  Shift-Robust Node Classification via Graph Adversarial Clustering.  arXiv:2203.15802.


# Depth-dependent resolution quantification in 3D fluorescence microscopy

Neil Wright  Department of Bioengineering, Imperial College London, London, UK
Christopher J Rowlands  Department of Bioengineering, Imperial College London,
London, UK<EMAIL_ADDRESS>
A method is presented to quantify resolution as a function of depth in
features of morphologically complex 3D samples. Applying the method to the
brain of Drosophila, resolution is measured at increasing depth throughout the
central brain region. The results quantify improvements in image quality when
using two-photon microscopy compared to confocal. It is also demonstrated how
resolution improvements through tuning a single parameter, laser power, can be
measured objectively. Since the metric is interpretable as the average
resolution within a feature, it is suitable for comparing results across
optical systems, and can be used to inform the design of biological
experiments requiring resolution of structures at a specific scale.

## Introduction

Quantifying image quality is important for both experiment design and the
development of optical instruments. In biology, it may be necessary to resolve
structures at a certain level of detail; users may not appreciate that
features which can be readily observed in one part of the sample may be
unresolvable elsewhere. Similarly, having an objective metric of quality in
microscopy allows comparison and improvement of instruments under various
adverse imaging conditions, as opposed to the favourable conditions that occur
near a tissue surface. Since the final quality is a function of both the
sample and optical system as a whole, this should be reflected in any metric.

In 3D samples, image quality is also highly dependent on tissue depth, with
quality degrading due to light attenuation and distortion caused by
scattering. Previous approaches to quantify this effect have sometimes relied
on signal intensity [1, 2] as a metric. However, intensity lacks an obvious
practical interpretation, and may not always correlate with image quality.
Another approach is to use a score based on arbitrary units [3], though this
also has the same issue of interpretability. In theory, using resolution as a
metric directly can solve these issues.

Resolution refers to the minimum distance at which two separate objects are
distinguishable. Mathematically, this can be defined based on either spatial
frequency contrast or distance. The Modulation Transfer Function (MTF) can be
used to characterise the former, while the Rayleigh Criterion is an example of
the latter. This states that two Airy discs are resolvable if the centre of
one disc lies within or outside the first minimum of the diffraction pattern
of the other [4].

While specially manufactured test samples can be used to assess the
performance of an optical system using either method, natural images are
unlikely to contain patterns of known contrast or distance that can be used
directly to measure resolution. Estimation methods must therefore be used
instead. This can be done by either estimating the MTF [5] or using an
approach based on Fourier Ring Correlation (FRC) [6]. The latter technique
originates in electron microscopy and involves finding the highest spatial
frequency in an image distinguishable from noise [7].

However, a problem arises when applying a single measurement to more complex
samples where resolution may be non-uniform across the image. This is often
the case in 3D biological specimens where variations in factors such as tissue
depth, type, or fluorophore concentration may create large differences in
quality within the same optical plane.

Previously, it has been shown that FRC can be used to analyse local resolution
by splitting the image into tiles [8], an approach recently used to analyse
fine features in super resolution images [9]. Here, by applying this approach
to 3D fluorescence microscopy, we show how it can be used to isolate a
particular feature within a 3D sample and quantify resolution within that
feature as a function of depth.

The method is demonstrated by analysing the central region of the dissected
brain of Drosophila Melanogaster, a model organism widely used in
neurobiology. Due to its 3D morphology, optical sections of the fly brain can
contain regions of heterogeneous resolution, with particular differences
between the central brain and optic lobes caused by differing levels of light
scattering. By calculating the average FRC value within the central brain, we
show how to characterise resolution within any arbitrarily shaped region of an
image, and by extension quantify the degradation of resolution in a feature in
3D.

Results comparing confocal and two-photon imaging are presented. These align
with previous findings on the highly scattering nature of the fly brain
compared to mammalian brain, even when two-photon microscopy is used [10].
Additionally, we show how to quantify improvements in resolution when a single
parameter, laser power, is increased.

The method presented is generally applicable for analysing resolution in
features of 3D samples where image quality is non-uniform. In addition, as a
metric of resolution, it has a practical interpretation which can be used to
inform experimental considerations and compare results across different
optical instruments.

## Methods

### Sample preparation

Green Fluorescent Protein (GFP) was expressed pan-neuronally in Drosophila by
crossing nSyb-GAL4 (Bloomington Drosophila Stock Center (BDSC) #68222) with
10XUAS-IVS-mCD8::GFP (BDSC #32187). Adult male and female flies were
anaesthetised by low temperature and brains dissected in phosphate-buffered
saline (PBS) using fine forceps (Dumont #55 and #5SF) [11]. Dissected brains
were transferred to a PBS-filled glass-bottom 35 mm confocal dish (VWR) coated
with poly-D-lysine (approximately $100\text{\,}\mathrm{\SIUnitSymbolMicro
g}$/mL; Sigma), and oriented dorsal side down.

### Confocal and two-photon microscopy

Confocal and two-photon (2p) images were both taken using the same commercial
Leica SP5 inverted microscope at the Facility for Imaging by Light Microscopy
(FILM) at Imperial College London. Each sample was used to capture a stack for
all modalities. Because initial results found photobleaching to be minimal
except for higher power 2p stacks, the order was not randomised and 2p stacks
were always captured last.

A 20x 0.7 NA dry objective (Leica) was used for imaging and a photomultiplier
tube (PMT) was used to detect fluorescence. Bit depth was set to 16 bits and
pixel size set to 94.6 nm (8192$\times$8192 format) with a line scan rate of
400 Hz.

Frames were captured with a step size of
$10\text{\,}\mathrm{\SIUnitSymbolMicro m}$. Confocal imaging used an Argon
laser at 488 nm and pinhole size of 1 Airy Unit. Two-photon imaging used a Mai
Tai DeepSee laser (Newport Spectra-Physics) tuned to 920 nm and the pinhole
fully opened.

Power was measured using a Thorlabs S170C power sensor for the Argon laser,
and S425C for the DeepSee laser.

### Image analysis

#### Mean resolution algorithm

The algorithm to compute the Mean FRC (mFRC) in a region-of-interest (ROI) of
arbitrary shape is illustrated in Figure 1. First, ROIs were drawn around the
central brain region for each image in the Z-stack and used to generate masks.
The image was then split into small (64x64 pixels) tiles. For each tile in the
mask, FRC was calculated. The mFRC value for each depth was taken to be the
mean of all tiles in the mask for that depth. Finally, mFRC was plotted as a
function of depth.

In general, calculating FRC requires two independent images. Here, ‘single
image’ FRC was used, whereby each full image is first split into sub-images as
described in [12]. FRC was calculated according to the standard formula of
computing the Pearson correlation coefficient of rings of increasing radius in
the Fourier transforms of the two images according to Equation 1:

$\text{FRC}(r)=\frac{\sum\limits_{i\in R}F_{1}(r_{i})\cdot
F_{2}(r_{i})*}{\sqrt{\sum\limits_{i\in
R}|F_{1}(r_{i})|^{2}\cdot\sum\limits_{i\in R}|F_{2}(r_{i})|^{2}}}$ (1)

where $F_{1}$ is the Fourier transform of the first image and $F_{2}*$ is the
complex conjugate of the Fourier transform of the second image; the numerator
is a real number [13]. The inverse of the frequency below which the
correlation drops below a fixed 1/7 cut-off is the FRC value [14]. All code
was written in Java.

#### FRC Colourmaps

High-detail FRC colourmaps [9] were generated to highlight precise variations
in resolution across images (Figure 2). The approach to generate colourmaps
was similar to the method described above, except that, instead of dividing
the image into tiles, a 64x64 pixel block centred on each pixel was scanned
across the ROI. The FRC value for each block was converted to a colour value
and used to draw a single pixel at the corresponding coordinates in the
colourmap. Artifacts were smoothed by applying a Gaussian blur (Radius = 10)
using Fiji [15]. It was found that the rolling FRC method produced comparable
results to the tiling method in terms of mean value within the ROI, but at the
cost of greatly increased computation. Therefore, the tiling method was used
when comparing results from different imaging modalities. As a simple example,
assuming a tile size of 64 $\times$ 64 pixels, a 1024 $\times$ 1024 pixel
square ROI requires 16 $\times$ 16 = 256 FRC calculations for the tiling
method, but 1,048,576 FRC calculations for the rolling block method.

Figure 1: (A) Schematic of the method to calculate Mean FRC (mFRC). First, a
region-of-interest (ROI) is drawn over the feature to be analysed in each
image in the Z-stack. The image is then divided into small tiles, and the
Fourier Ring Correlation (FRC) value for each tile within the ROI is
calculated by selecting the highest spatial frequency whose correlation
coefficient is greater than the cut-off value. Finally, the mean value for
each ROI is computed and plotted as a function of depth. Since FRC represents
the minimum resolvable distance, lower values correspond to better image
quality. (B) Drosophila brain with the dorsal side facing down. The black line
represents an optical plane. Variable tissue depths (blue arrows) result in
differing levels of light scattering, contributing to resolution heterogeneity
within the image. Drosophila brain based on graphic from virtualflybrain.org
[16]. Figure 2: (A) Example images of an nSyb¿GFP brain at various depths for
each imaging modality. Confocal power levels were
$9\text{\,}\mathrm{\SIUnitSymbolMicro W}$ (low),
$100\text{\,}\mathrm{\SIUnitSymbolMicro W}$ (mid), and
$224\text{\,}\mathrm{\SIUnitSymbolMicro W}$ (high). Two-photon power was 22mW.
Each image has been individually optimised for brightness and contrast to
highlight image quality. Scale bar = $100\text{\,}\mathrm{\SIUnitSymbolMicro
m}$. (B) High-detail rolling FRC colourmaps of the central brain ROI,
generated from the same two-photon stack shown in A. The scale represents
minimum resolvable distance (FRC) from 0 to 7+
$\text{\,}\mathrm{\SIUnitSymbolMicro m}$. Figure 3: Resolution as a function
of depth in the central region of the Drosophila brain for 4 different
specimens. Values are plotted for depths where $\geq$95% of tiles contained
correlating spatial frequencies for at least half the specimens. Three
different confocal power levels ($9\text{\,}\mathrm{\SIUnitSymbolMicro W}$,
$100\text{\,}\mathrm{\SIUnitSymbolMicro W}$, and
$224\text{\,}\mathrm{\SIUnitSymbolMicro W}$) were compared with two-photon
imaging (22 mW) using the mFRC metric.

## Results and Discussion

### Theoretical considerations for imaging parameters

To determine the pixel size required to capture all information within the
image, Abbe’s diffraction formula was used to estimate the minimum theoretical
distance resolvable by the system [4]:

$d=\lambda/(2\text{NA})$ (2)

Here, d=349 nm for confocal and 657 nm for 2p imaging. Shannon-Nyquist
sampling requires using half these values [17]. Therefore, a pixel size of 189
nm (equivalent to full image size of 4096x4096 pixels) was chosen, close to
the value required.

Since calculating FRC requires two independent images, initial attempts
captured two separate stacks for each modality. However, it was found that
occasionally the z-galvo position shifted slightly between stacks,
compromising results. To ensure alignment of the two images, ‘single image’
FRC was used instead [12], whereby a single image is split into sub-images. To
achieve equivalent sampling, stacks were captured with a pixel size of 94.6
nm, equivalent to a pixel size of 189 nm for each sub-image.

### Resolution heterogeneity within the same image

Initial attempts found that using a single FRC calculation for each full image
in the stack led to inconsistent and non-monotonic results. FRC colourmaps [9]
revealed that this was due to non-uniformity of resolution within images,
particularly the contrast between the central brain and optic lobes, which
begin at deeper optical planes (Figure 1B) and thus appear as higher
resolution areas due to decreased light scattering. Apart from the optic
lobes, the effect of differential light scattering on resolution is also
apparent at the edges of the central brain, where tissue is thinnest and image
quality better, and in the middle of the brain, where tissue is thickest and
image quality worst (Figure 2). While the central brain region was analysed
here as a whole, depending on requirements it would also be possible to take a
more fine-grained approach and analyse only specific structures of interest.
Alternatively, the entire brain could be characterised solely as a function of
depth using a depthmap-based method. Aside from the effect of scattering, the
colourmaps indicated that the outlines of major brain structures, such as the
antennal lobes, mushroom body, and central complex, also appeared as high-
resolution features, likely due to the presence of sharp ‘edges’ resulting
from differing GFP concentrations (Figure 2).

To isolate a particular feature of interest for analysis, simply cropping the
image has the disadvantage that only rectangular areas can be analysed, rather
than the arbitrary shapes which are common in natural images. An alternative
approach of masking out other features risks creating artificially sharp edges
in the image, which may distort measurements of resolution. To overcome these
issues, the mFRC method was developed based on splitting the image into small
tiles. This allows characterisation of resolution in image features of any
arbitrary shape, providing results which remain relatively consistent across
samples. As noted in the Methods, a ‘rolling block’ approach can be applied
similarly if more fine-grained information is required, though this comes at
the cost of increased computation.

It is noted that one limitation of this method is that while use of small
tiles provides highly localised information, tile size also constrains the
lowest spatial frequency which can be correlated. This results in a trade-off
between minimising the area to which resolution information is localised and
maximising the range of resolutions which can be detected. A tile size of
64$\times$64 pixels was found to provide a reasonable compromise in this
regard.

### Confocal and two-photon resolution in Drosophila brain

Two-photon (2p) imaging is widely used in neurobiology, including in
Drosophila [18]. Use of higher-order excitation suppresses out of focus
fluorescence, while longer wavelengths of light are less prone to scattering
[19]. Here, the benefits of 2p (22 mW) were apparent for depths approximately
$35\text{\,}\mathrm{\SIUnitSymbolMicro m}$ and greater, with the difference
increasing with depth (Figure 3). For depths less than this, sufficiently-
powered confocal appeared to provide slightly sharper images, in line with the
theoretical resolution benefits of shorter wavelengths [4]. Despite the
benefits of 2p, however, imaging depth was still limited in comparison to
mammalian brain, where imaging up to 1.6 mm has been reported [20]. This
aligns with a recent study on the optical properties of the fly brain, which
attributed its highly scattering nature to extensive light scattering at the
air-tissue interface in tracheae [10]. At a practical level, though deeper
brain structures such as the mushroom body calyx and proto-cerebral bridge
could be imaged using 2-photon imaging (Figure 2), higher resolution imaging
of these regions may require 3-photon microscopy [10]. A further consideration
is that 2p causes considerably more photobleaching than confocal, which may be
a factor in certain experiments, such as those involving long-term imaging.
Additionally, while the results here were based on dissected brains,
resolution may vary in fixed samples or in vivo.

Confocal laser power was used as an example to demonstrate how improvements in
image quality through tuning a single parameter can be quantified using the
method described (Figure 3). In the results, each increase in power led to a
measurable improvement in resolution, with the improvement becoming more
pronounced with increasing depth. This can be explained by the general
principle that, as the number of photons increases, signal increases linearly
while noise increases by the square root of the number of photons, leading to
a higher signal-to-noise ratio (SNR) [21]. Quantifying resolution in this way
thus allows system tuning until requirements for a given experiment are met.

## Conclusion

The method described showed how any region of arbitrary shape within an image
can be characterised in terms of mean resolution using a metric based on
Fourier Ring Correlation. This enabled quantification of resolution as a
function of depth in 3D features in a way that remains relatively consistent
across samples. Using the method applied to the brain of Drosophila,
resolution at each depth level of the central brain was measured and the
benefits of 2-photon imaging over confocal quantified objectively. Measurement
of image quality improvements through tuning a single parameter, laser power,
was also demonstrated. It is suggested that this method may be generally
useful for other samples in 3D microscopy where resolution is heterogeneous
and quantifying image quality at different depths is important.

## Acknowledgements

NW is grateful for support from the Medical Research Council (MRC). CJR is
grateful to the following bodies for support: Engineering and Physical
Sciences Research Council (EP/S016538/1, EP/X017842/1, EP/W024969/1);
Biotechnology and Biological Sciences Research Council (BB/T011947/1);
Wellcome Trust (212490/Z/18/Z); Cancer Research UK (29694, EDDPMA-
May22\100059); Royal Society (RGS\R2\212305); Chan Zuckerberg Initiative
(2020-225443, 2020-225707); Imperial College Excellence Fund for Frontier
Research. The Facility for Imaging by Light Microscopy (FILM) at Imperial
College London is part-supported by funding from the Wellcome Trust (grant
104931/Z/14/Z) and BBSRC (grant BB/L015129/1). Stocks obtained from the
Bloomington Drosophila Stock Center (NIH P40OD018537) were used in this study.

## Disclosures

The authors declare no conflicts of interest.

## Data Availability Statement

Data underlying the results presented in this paper are not publicly available
at this time but may be obtained from the authors upon reasonable request.

## References

  * [1] Mihaela Balu et al.  “Effect of excitation wavelength on penetration depth in nonlinear optical microscopy of turbid media”  In _J Biomed Opt_ 14.1, 2009, pp. 010508  DOI: 10.1117/1.3081544
  * [2] Chen-Yuan Dong et al.  “Applications of two-photon fluorescence microscopy in deep-tissue imaging”  In _Optical Sensing, Imaging, and Manipulation for Biological and Biomedical Applications_ , 2000  DOI: 10.1117/12.390532
  * [3] Friedrich Preusser et al.  “FRC-QE: A robust and comparable 3D microscopy image quality metric for cleared organoids”  In _Bioinformatics_ , 2021  DOI: 10.1093/bioinformatics/btab160
  * [4] Lord Rayleigh  “Investigations in optics, with special reference to the spectroscope”  In _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ 8.49, 1879, pp. 261–274  DOI: 10.1080/14786447908639684
  * [5] Christopher J Rowlands, Oliver T Bruns, Moungi G Bawendi and Peter T C So  “Objective, comparative assessment of the penetration depth of temporal-focusing microscopy for imaging various organs”  In _J Biomed Opt_ 20.6, 2015, pp. 61107  DOI: 10.1117/1.jbo.20.6.061107
  * [6] Niccolò Banterle, Khanh Huy Bui, Edward A Lemke and Martin Beck  “Fourier ring correlation as a resolution criterion for super-resolution microscopy”  In _J Struct Biol_ 183.3, 2013, pp. 363–367  DOI: 10.1016/j.jsb.2013.05.004
  * [7] W O Saxton and W Baumeister  “The correlation averaging of a regularly arranged bacterial cell envelope protein”  In _J Microsc_ 127.Pt 2, 1982, pp. 127–38  DOI: 10.1111/j.1365-2818.1982.tb00405.x
  * [8] Siân Culley et al.  “Quantitative mapping and minimization of super-resolution optical imaging artifacts”  In _Nat Methods_ 15.4, 2018, pp. 263–266  DOI: 10.1038/nmeth.4605
  * [9] Weisong Zhao et al.  “Quantitatively mapping local quality of super-resolution microscopy by rolling Fourier ring correlation”  In _bioRxiv_ , 2022  DOI: 10.1101/2022.12.01.518675
  * [10] Kuo-Jen Hsu, Yen-Yin Lin, Ann-Shyn Chiang and Shi-Wei Chu  “Optical properties of adult Drosophila brains in one-, two-, and three-photon microscopy”  In _Biomed Opt Express_ 10.4, 2019, pp. 1627–1637  DOI: 10.1364/boe.10.001627
  * [11] Joy S Wu and Liqun Luo  “A protocol for dissecting Drosophila melanogaster brains for live imaging or immunostaining”  In _Nat Protoc_ 1.4, 2006, pp. 2110–5  DOI: 10.1038/nprot.2006.336
  * [12] Sami Koho et al.  “Fourier ring correlation simplifies image restoration in fluorescence microscopy”  In _Nat Commun_ 10.1, 2019, pp. 3103  DOI: 10.1038/s41467-019-11024-z
  * [13] Marin Van Heel  “Similarity measures between images”  In _Ultramicroscopy_ 21.1, 1987, pp. 95–100  DOI: 10.1016/0304-3991(87)90010-6
  * [14] Robert P J Nieuwenhuizen et al.  “Measuring image resolution in optical nanoscopy”  In _Nat Methods_ 10.6, 2013, pp. 557–62  DOI: 10.1038/nmeth.2448
  * [15] Johannes Schindelin et al.  “Fiji: an open-source platform for biological-image analysis”  In _Nat Methods_ 9.7, 2012, pp. 676–82  DOI: 10.1038/nmeth.2019
  * [16] Robert Court et al.  “Virtual Fly Brain-An interactive atlas of the Drosophila nervous system”  In _Front Physiol_ 14, 2023, pp. 1076533  DOI: 10.3389/fphys.2023.1076533
  * [17] C.E. Shannon  “Communication in the Presence of Noise”  In _Proc. IRE_ 37.1, 1949, pp. 10–21  DOI: 10.1109/jrproc.1949.232969
  * [18] Karel Svoboda and Ryohei Yasuda  “Principles of two-photon excitation microscopy and its applications to neuroscience”  In _Neuron_ 50.6, 2006, pp. 823–39  DOI: 10.1016/j.neuron.2006.05.019
  * [19] Fritjof Helmchen and Winfried Denk  “Deep tissue two-photon microscopy”  In _Nat Methods_ 2.12, 2005, pp. 932–40  DOI: 10.1038/nmeth818
  * [20] Demirhan Kobat, Nicholas G. Horton and Chris Xu  “In vivo two-photon microscopy to 1.6-mm depth in mouse cortex”  In _J. Biomed. Opt._ 16.10, 2011, pp. 1  DOI: 10.1117/1.3646209
  * [21] Colin J.. Sheppard, Xiaosong Gan, Min Gu and Maitreyee Roy  “Signal-to-Noise Ratio in Confocal Microscopes”  In _Handbook Of Biological Confocal Microscopy_ , 2006, pp. 442–452  DOI: 10.1007/978-0-387-45524-2˙22