# EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Cost

Jaeseung Heo
Graduate School of Artificial Intelligence
POSTECH
South Korea
<EMAIL_ADDRESS>
&Seungbeom Lee∗
Graduate School of Artificial Intelligence
POSTECH
South Korea
<EMAIL_ADDRESS>
Sungsoo Ahn
Graduate School of Artificial Intelligence
POSTECH
South Korea
<EMAIL_ADDRESS>
&Dongwoo Kim
Graduate School of Artificial Intelligence
POSTECH
South Korea
<EMAIL_ADDRESS>
Equal contribution.

###### Abstract

Graph-based models have become increasingly important in various domains, but
the limited size and diversity of existing graph datasets often limit their
performance. To address this issue, we propose EPIC (Edit Path Interpolation
via learnable Cost), a novel interpolation-based method for augmenting graph
datasets. Our approach leverages graph edit distance to generate new graphs
that are similar to the original ones but exhibit some variation in their
structures. To achieve this, we learn the graph edit distance through a
comparison of labeled graphs and utilize this knowledge to create graph edit
paths between pairs of original graphs. With randomly sampled graphs from a
graph edit path, we enrich the training set to enhance the generalization
capability of classification models. We demonstrate the effectiveness of our
approach on several benchmark datasets and show that it outperforms existing
augmentation methods in graph classification tasks.

##  1 Introduction

Graph data has become increasingly important in various domains, such as
social networks, bioinformatics, and recommendation systems [1, 2, 3].
However, the limited size and diversity of existing graph datasets often limit
the performance of graph-based models. One way to overcome this limitation is
to augment the existing dataset by generating new graphs with similar
properties. [4, 5, 6, 7, 8, 9, 10, 11, 12] The augmentation can improve the
generalization ability of graph-based models and make them more robust to
different real-world scenarios [13, 14].

The mixup method has proven successful as a data augmentation technique,
particularly for Euclidean data such as images [7, 13, 15]. It involves
generating new samples by performing linear interpolation between the features
and labels of two randomly selected samples from the original dataset. This
method has demonstrated its effectiveness in enhancing the generalization and
robustness of deep learning models for image classification tasks [16].

However, applying the mixup method directly to graph data poses challenges.
Unlike the Euclidean domain, graph structures lack a direct spatial
arrangement of their elements, making it difficult to define meaningful linear
interpolations for graphs. This highlights the necessity of exploring
alternative augmentation methods specifically designed for graph data.

In this paper, we propose a novel approach to graph dataset augmentation based
on the concept of graph edit distance [17]. The graph edit distance is a
widely-used metric that quantifies the similarity between two graphs by
counting the minimum number of edit operations required to transform one graph
into another, such as node and edge insertions, deletions, or substitutions.
By computing the graph edit distance between two graphs, we construct a graph
edit path representing the transformation process from one graph to the other
through edit operations. The intermediate graph states along this path can be
seen as an interpolation between two graphs and are utilized to augment the
training set.

A simple count-based approach for edit distance computation, however, may not
adequately capture the importance of individual operations. For instance,
operations that modify functional groups in molecular graphs may hold greater
significance than others [18, 19]. Hence, we introduce a problem-specific cost
model to account for the context-dependent cost. We formulate an edit distance
learning framework that leverages the insight that the distances between
graphs within the same class should be relatively shorter than those between
different classes. This enables us to learn a cost model that better reflects
the underlying graph data characteristics.

By combining the graph edit distance metric with our learned cost model, we
present a novel graph dataset augmentation method named Edit Path
Interpolation via learnable Cost (EPIC). Experimental evaluations on various
graph classification tasks demonstrate the effectiveness and improved
performance of our approach compared to existing methods. Additional
experiments under the presence of noisy labels show the robustness of our
approach against the others.

##  2 Related Work

###  2.1 Graph edit distance

The graph edit distance is a metric that quantifies the dissimilarity between
two graphs [17]. It measures the minimum number of edit operations required to
transform one graph into another. These edit operations include node and edge
insertion, deletion, and substitution. The computational complexity of
obtaining graph edit distance is known to NP-complete [20]. A number of works
addressing the problem of the high computational cost have been proposed.
Cross et al. [21] cast the optimization process into a Bayesian framework with
a genetic search algorithm. Myers et al. [22] adopt the Levenshtein distance
to model the probability distribution for structural errors in the graph-
matching. In [23], a binary linear programming formulation of the graph edit
distance for unweighted, undirected graphs is proposed. Fischer et al. [24]
propose an approximated graph edit distance based on Hausdorff matching.
Recent approaches adopt the deep learning method to efficiently prune the
search tree in computation [25].

Recently, deep neural network-based graph edit distance learning methods have
been proposed. In contrast to the traditional approximation methods, where the
cost of edit operation is fixed, these methods learn the cost of individual
edit operations. One standard approach to learning costs using neural networks
involves obtaining embeddings from node and edge attributes, which are then
used to compute the edit distance in a supervised manner [26, 27]. However,
these approaches require ground truth or expected correspondences between two
graphs, which are inapplicable in various situations. Riba et al. [28] learn
the cost using node features extracted by graph neural networks and optimizes
the cost by approximating graph edit distance to Hausdorff distance. The
Hausdorff distance is an effective method for approximating the graph edit
distance in quadratic time, but it is not suitable for edit path construction
since it allows one-to-many substitution between nodes.

###  2.2 Graph augmentation for graph neural networks

With the success of recent Graph Neural Networks (GNNs) for graph-level
classification tasks, augmentation methods for graph-structured data aim to
improve the generalization ability of GNNs by creating diverse training
samples. Most commonly used augmentation methods are based on random
modifications on original data [5, 4, 6]. For example, Dropnode [5] and
DropEdge [4] uniformly drop nodes and edges, respectively. A subgraph sampling
[6, 29] and motif swap [30] perturb the subgraph of the original graph via
subgraph matching. These methods assign the same labels before and after the
perturbation.

To overcome the simplicity of basic approaches, mixup-based methods are
proposed for graph augmentation [8, 10, 9, 12]. The mixup methods are an
augmentation technique that generates new training data by taking convex
combinations of pairs of inputs and their corresponding labels. Mixup methods
can be naturally used for regular data, such as images. However, applying
mixup for graph-structure data is challenging due to the irregular structure.
Manifold mixup [8] interpolates embeddings from the last layer for two graphs
and uses it as a graph representation of the augmented graph. Submix [10]
proposes a node split and merge algorithm to perturb original graphs and then
mix random subgraphs of multiple graphs. ifMixup [9] adds dummy nodes to match
the size of two graphs. Then it interpolates between node feature matrices and
adjacency matrices to generate mixed graphs. S-mixup [12] computes an
alignment matrix between two graphs with graph matching network [31] first and
then mixes up node features. G-mixup [11] mixes graphons [32] of different
classes and augments training set by generating the graphs from the mixed
graphon.

##  3 EPIC: Edit Path Interpolation via learnable Cost

In this section, we first describe a graph data augmentation method with a
graph edit path. We then propose a method to learn a graph edit distance by
learning the cost of individual edit operations.

Figure 1: Illustration of graph edit path and their corresponding labels for
augmentation.

###  3.1 Augmentation with graph edit path

#### Construction of graph edit path

We consider a graph ${G}=(\mathcal{V},\mathcal{E})$ associated with node and
edge attributes. The graph edit distance is a metric that quantifies the
dissimilarity between two graphs. It measures the minimum number of edit
operations required to transform one graph into another or computes the total
cost of edit operations if the cost of individual operations varies. These
edit operations involve node and edge insertion, deletion, and attribute
substitution.

Once the graph edit distance is computed, a graph edit path can be obtained by
applying a series of edit operations from a source graph to reach a target
graph. It represents the step-by-step transformation from one graph to another
while minimizing the edit distance.

The graph edit distance is generally invariant to the order of edit
operations. However, there are certain dependencies between node and edge
operations. The node deletion operation can only be performed after all the
connected edges are deleted. The edge insertion operation can only be
performed when the two target nodes are presented.

We only consider the node operations in order to simplify the graph edit path
construction. Specifically, when a new node is inserted into a graph, we
perform edge insertion operations for all edges whose adjacent nodes are given
after insertion. When a node is deleted, we perform edge deletion operations
for all edges connected to the deleted node. When a node is substituted, we
perform edge insertion, deletion, and substitution operations accordingly. The
detailed algorithm is provided in Algorithm 1. By doing so, we can construct
the graph edit path whose length is equal to the number of node edit
operations in the computation of the graph edit distance. Figure 1 illustrates
an example of a graph edit path between two graphs and possible augmentation.

Algorithm 1 Applying node operation

1:A node operation $(u\rightarrow v)$, source graph
${G}_{S}=(\mathcal{V}_{S},\mathcal{E}_{S})$, target graph
${G}_{T}=(\mathcal{V}_{T},\mathcal{E}_{T})$, and the current graph
${G}_{C}=(\mathcal{V}_{C},\mathcal{E}_{C})$.

2:if $u=\varnothing$ then

3: Insert the node $v$ to $\mathcal{V}_{C}$.

4:else if $v=\varnothing$ then

5: Delete the node $u$ from $\mathcal{V}_{C}$.

6:else

7: Substitute the node feature of node $u$ with the node feature of node $v$.

8:end if

9:for each edge $(u,u^{\prime})$ in $\mathcal{E}_{C}$ do

10: if node $u^{\prime}\in\mathcal{V}_{T}$ and edge $(u,u^{\prime})$ not in
$\mathcal{E}_{T}$ then

11: Remove the edge $(u,u^{\prime})$ from $\mathcal{E}_{C}$.

12: else if node $u^{\prime}\in{\mathcal{V}_{T}}$ and edge $(v,u^{\prime})$ in
$\mathcal{E}_{T}$ then

13: Substitute edge attributes of $(u,u^{\prime})$ in $\mathcal{E}_{C}$ with
those of $(v,u^{\prime})$ in $\mathcal{E}_{T}$ if needed.

14: end if

15:end for

16:for each edge $(v,v^{\prime})\in\mathcal{E}_{C}$ adjacent to node $v$ in
$\mathcal{V}_{T}$ do

17: if node $v^{\prime}\in{\mathcal{V}_{C}}$ then

18: Insert the edge $(v,v^{\prime})$ to $\mathcal{E}_{C}$.

19: end if

20:end for

#### Graph augmentation and label assignment

We use the graph edit path to construct an augmented graph. We randomly sample
two graphs in the training set. The graph edit distance between the two graphs
is computed, then the graph edit path is constructed with node operations in
random order. The samples obtained from a graph edit path are used as
augmented graphs. Examples of augmented graphs are provided in Figure 1.

To assign a label to the augmented graph, we use the cost of edit operations
from the augmented graph to the source and the target graphs. Let
$(o_{1},...,o_{n})$ be a sequence of edit operations applied to transforming
source graph ${G}_{S}$ to target graph ${G}_{T}$, and $c(o)$ be the real-
valued cost function of operation $o$, which is precisely defined in Section
3.2. With the corresponding one-hot classification label of the source graph
$\boldsymbol{y}_{S}$ and the target graph $\boldsymbol{y}_{T}$, the label of
the augmented graph $\bar{\boldsymbol{y}}$ obtained by applying the first $m$
operations $(o_{1},...,o_{m})$ is computed as

$\displaystyle\bar{\boldsymbol{y}}=\frac{\sum_{i=m+1}^{n}c\left(o_{i}\right)}{\sum_{i=1}^{n}c\left(o_{i}\right)}\boldsymbol{y}_{S}+\frac{\sum_{i=1}^{m}c\left(o_{i}\right)}{\sum_{i=1}^{n}c\left(o_{i}\right)}\boldsymbol{y}_{T},$
(1)

where $c(\cdot)$ measures the cost of an operation. The assigned label is
inversely proportional to the operation cost to reach the source or target
from the augmented graph.

###  3.2 Learning costs of edit operations

The standard unit cost model [17, 24, 33] of the graph edit distance is
incapable of measuring the importance of each operation as all operations are
assigned the same cost, regardless of their significance or impact. However,
the importance of edit operations would differ based on the context of the
dataset. For example, changes in a functional group of molecular graphs can
lead to larger semantic perturbation than the other parts in a property
prediction task [18, 19]. Therefore, the edit operation leading to a large
semantic modification should cost more than the others. To measure the
importance of each operator in the computation of graph edit distance, we
propose a learning algorithm for the operation cost based on a neural network
model.

#### Triplet loss for learning distance

A good cost function should be problem dependent. We use the triplet loss with
known labels [34] to learn the graph edit distance and the operation costs
therein. We assume that the pair of graphs within the same class has a
relatively shorter distance than those of different classes. Let
$\operatorname{GED}({G},{G}^{\prime})$ be the distance between graphs ${G}$
and ${G}^{\prime}$. We propose a triplet loss-based objective function to
encode our intuition:

$\displaystyle\mathcal{L}({G},{G}^{+},{G}^{-})=\max\left(\operatorname{GED}({G},{G}^{+})-\operatorname{GED}({G},{G}^{-})+\gamma,0\right),$
(2)

where ${G}^{+}$ is a positive example whose label is the same as ${G}$,
${G}^{-}$ is a negative example whose labels are different from ${G}$, and
$\gamma$ is a margin hyperparameter.

#### Graph edit distance as constrained optimization

The computational complexity of graph edit distance computation is NP-complete
[20]. Learning graph edit distance often requires relaxation to make the
algorithm tractable [24, 33]. To simplify the learning process, we assume that
the cost of node operation _subsumes_ the cost of dependent edit operations,
similar to the construction of the edit path. With the simplified assumption,
we only need to consider the following three cases when computing the edit
distance between source graph ${G}_{S}=(\mathcal{V}_{S},\mathcal{E}_{S})$ and
target graph ${G}_{T}=(\mathcal{V}_{T},\mathcal{E}_{T})$ with operation cost
function
$c:\mathcal{V}_{S}\cup\varnothing\times\mathcal{V}_{T}\cup\varnothing\rightarrow\mathbb{R}$,
where $\varnothing$ represents an empty node:

  * •

Node $u$ in $\mathcal{V}_{S}$ is substituted by node $v$ in $\mathcal{V}_{T}$
with substitution cost $c(u,v)$.

  * •

Node $u$ in $\mathcal{V}_{S}$ is deleted with deletion cost
$c(u,\varnothing)$.

  * •

Node $v$ in $\mathcal{V}_{T}$ is inserted with insertion cost
$c(\varnothing,v)$.

We construct a cost matrix that encapsulates all required costs to compute the
edit distance between two graphs. The cost matrix is constructed as

$\displaystyle
C=\left[\begin{array}[]{cccccc}c\left(u_{1},v_{1}\right)&\cdots&c\left(u_{1},v_{m}\right)&c\left(u_{1},\varnothing\right)&\cdots&\infty\\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\\
c\left(u_{n},v_{1}\right)&\cdots&c\left(u_{n},v_{m}\right)&\infty&\cdots&c\left(u_{n},\varnothing\right)\vspace{0.05in}\\\
c\left(\varnothing,v_{1}\right)&\cdots&\infty&\infty&\cdots&\infty\\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\\
\infty&\cdots&c\left(\varnothing,v_{m}\right)&\infty&\cdots&\infty\end{array}\right],$
(9)

where $n$ and $m$ are the number of nodes in ${G}_{S}$ and ${G}_{T}$,
respectively.

With the cost matrix, the problem of computing the graph edit distance can be
reduced to solving the assignment problem. Since the node in the source graph
can only be substituted or deleted, only one operation can be performed in
each of the first $n$ rows. Similarly, since the node in the target graph can
only be substituted or inserted, only one operation in each of the first $m$
columns can be performed in edit distance computation. A binary assignment
matrix $X$, whose size is the same as the cost matrix, is introduced to
indicate which operation is performed in edit distance computation. With the
assignment matrix, the computation of graph edit distance can be formulated as
a constrained optimization problem

$\displaystyle\operatorname{GED}({G}_{S},{G}_{T})=\min_{X}\sum_{i=1}^{n+m}\sum_{j=1}^{n+m}C_{ij}X_{ij}$
$\displaystyle\text{ s.t. }\sum_{j=1}^{n+m}X_{ij}=1,\;1\leq i\leq
n,\quad\sum_{i=1}^{n+m}X_{ij}=1,\;1\leq j\leq m,\quad\;X_{ij}\in\\{0,1\\}.$
(10)

#### Design cost function with neural networks

We introduce the graph neural network framework to parameterize the cost
function $c$. Specifically, we use the embedding distances between two nodes
as the substitution cost. Let $h_{u}$ and $h_{v}$ be the output embedding of
node $u\in{G}_{S}$ and $v\in{G}_{T}$ from a graph neural network. We use the
distance between two embeddings as a substitution cost, i.e.,
$c_{\theta}(u,v)=||h_{u}-h_{v}||_{2}$, where $\theta$ is the parameter of the
graph neural network. The embeddings of the graph neural network encode the
neighborhood structure of the target node. If the embeddings of two nodes are
similar, then the two nodes are likely to play a similar role in the graph.
Hence, the substitution cost measures the structural similarity between two
nodes. For the insertion and deletion operations, we additionally introduce a
multi-layer perceptron, i.e.,
$c_{\theta,\phi}(u,\epsilon)=\operatorname{MLP}_{\phi}(h_{u})$ and
$c_{\theta,\phi}(\epsilon,v)=\operatorname{MLP}_{\phi}(h_{v})$, where $\phi$
denotes the parameters of $\operatorname{MLP}$. The $\operatorname{MLP}$
computes the cost of insertion and deletion using the embedding of a node. We
use the same network for both insertion and deletion. The graph neural
networks encode the local structure of nodes into node embeddings.
Consequently, by considering the costs of node operations, we effectively
encapsulate the information regarding the neighborhood edges as well.

#### Model optimization with a differentiable assignment matrix

To learn the graph edit distance, we need to minimize the loss in Equation 2
w.r.t $\theta$ and $\phi$. However, this optimization involves a non-
differentiable optimization problem w.r.t the assignment matrix $X$ in Section
3.2. The Hungarian algorithm [35] can be used to find the optimal assignment
$X$ for each iteration of the stochastic gradient descent step. However, the
Hungarian algorithm is non-differentiable and has a computational complexity
of $O(n^{3})$, making it difficult to employ during gradient-based
optimization. We instead employ the Sinkhorn-Knopp algorithm [36] to address
this issue to obtain a differentiable assignment matrix. The Sinkhorn-Knopp
algorithm transforms a non-negative matrix into a doubly stochastic matrix to
approximate the Hungarian algorithm. Specifically, Sinkhorn-Knopp iteratively
updates a soft assignment matrix $\tilde{X}$ via two intermediate variables
$\boldsymbol{u}$ and $\boldsymbol{v}$. Once $\boldsymbol{u}$ and
$\boldsymbol{v}$ are initialized as a vector of ones, i.e.,
$\boldsymbol{u}^{(0)}=[1,\cdots,1]^{\top}$, at $k$-th iteration of Sinkhorn-
Knopp approximates the assignment matrix via

$\displaystyle\boldsymbol{u}^{(k)}=\frac{X^{(k-1)}\mathbf{1}}{K\boldsymbol{v}^{(k-1)}},\quad\boldsymbol{v}^{(k)}=\frac{X^{{(k-1)}\top}\mathbf{1}}{K^{\top}\boldsymbol{u}^{(k-1)}},\quad\tilde{X}^{(k)}=\operatorname{diag}(\boldsymbol{u}^{(k)})K\operatorname{diag}(\boldsymbol{v}^{(k)}),$
(11)

where each entry of matrix $K$ is parameterized by the cost matrix and a
regularizer parameter $\delta$ as $K_{ij}=\exp({-C_{ij}/\delta})$, and
$\mathbf{1}$ is a vector of ones. $\delta$ is a regularization term
controlling the sharpness of the assignment matrix.

Note that the back-propagation algorithm needs to optimize the entire
iterative process of the Sinkhorn-Knopp approximation. In experiments, we set
the number of maximum iterations to 10 to reduce the computational cost. After
learning the cost function, to augment a pair of randomly selected graphs, we
first compute the cost matrix and then create a graph edit path using the
optimal assignment from the Hungarian algorithm. Figure 2 shows the overall
illustration of our proposed approach.

Figure 2: Overall illustration of graph edit distance learning. The assignment
matrix can be obtained by either Hungarian or Sinkhorn-Knopp. For learning, we
use Sinkhorn-Knopp, and for augmentation, we use Hungarian.

##  4 Experiments

In this section, we first show the effect of EPIC in graph classification
tasks over 11 datasets. We further evaluate the robustness of GNNs with our
method against corrupted labels. We provide additional analysis of our model
selection process.

###  4.1 Effect of augmentation for graph classification

#### Datasets

We used eight classification datasets: NCI1, BZR, COX2, Mutagenicity, IMDB-
BINARY, IMDB-MULTI, PROTEINS, ENZYMES from TUDataset [2] and three
classification dataset: BBBP, BACE, HIV from MoleculeNet [37]. The datasets
cover a wide range of tasks, including social networks, bioinformatics, and
molecules. The detailed statistics of each dataset are shown in Appendix A.

#### Baselines

For baseline augmentation models, we employ two classical graph augmentation
methods: DropEdge [4] and DropNode [5], and three Mixup-based augmentations:
SubMix [10], Manifold-Mixup (M-Mixup) [8], and G-Mixup [11]. We also report
the performance of a vanilla model without augmentation.

Table 1: Classification accuracy of TUDataset [2]. We report the average and
standard deviation (in brackets) over five seeds. We mark the best and the
second-best performances in bold and underline, respectively. The rank column
shows the average rank of a model performance across all datasets.

| Method | NCI1 | BZR | COX2 |  Mutagen. | IMDB-B | IMDB-M | PROTEINS | ENZYMES | Rank
---|---|---|---|---|---|---|---|---|---|---
GIN | Vanilla | 81.68(0.8) | 87.07(2.7) | 83.40(2.7) | 81.57(0.7) | 72.90(0.6) | 48.40(1.2) | 67.80(2.2) | 46.33(2.3) | 3.5
Dropedge [4] | 74.61(0.7) | 85.85(0.4) | 80.43(2.7) | 79.13(1.1) | 71.20(1.6) | 47.20(2.0) | 68.97(1.6) | 39.00(3.1) | 5.4
Dropnode [5] | 73.05(1.8) | 85.61(3.0) | 78.51(1.6) | 77.91(1.0) | 72.90(3.4) | 46.60(2.0) | 67.53(3.3) | 38.00(3.6) | 6.1
SubMix [10] | 81.31(0.6) | 85.61(3.6) | 83.62(2.3) | 66.58(1.5) | 71.70(1.0) | 48.60(1.0) | 70.76(2.2) | 44.33(4.8) | 4.0
M-Mix [8] | 81.00(0.4) | 85.37(3.6) | 84.47(1.0) | 81.68(0.9) | 73.20(0.6) | 47.93(1.8) | 68.70(1.1) | 46.67(1.7) | 3.5
G-Mix [11] | 80.92(1.9) |  88.05(1.6) | 82.98(0.8) | 81.66(0.6) | 72.20(1.0) | 48.13(1.2) | 68.16(2.8) | 43.67(6.9) | 4.1
EPIC |  82.31(1.5) | 87.32(2.0) |  84.89(2.7) |  81.86(1.0) |  73.40(0.8) |  48.93(0.6) |  70.85(0.9) |  47.83(3.5) | 1.1
GCN | Vanilla | 81.07(0.7) | 85.85(2.8) | 84.26(2.2) | 81.70(1.1) | 70.60(1.3) |  48.27(1.5) | 64.13(1.6) | 44.67(5.7) | 3.5
Dropedge [4] | 74.24(1.0) | 82.93(4.3) | 83.40(1.2) | 80.37(0.6) | 70.50(1.8) | 45.67(1.5) | 64.75(3.4) | 39.33(1.8) | 5.4
Dropnode [5] | 73.78(1.8) | 80.73(2.4) | 79.15(1.8) | 78.32(1.6) | 69.40(3.0) | 39.80(3.7) |  68.43(1.8) | 36.17(3.6) | 6.0
SubMix [10] | 81.99(0.6) | 86.34(2.0) | 83.62(4.1) | 79.77(0.9) | 68.50(0.1) | 46.47(2.5) | 66.82(2.1) | 43.67(4.9) | 4.5
M-Mix [8] | 81.41(0.5) | 84.15(2.3) | 83.83(2.1) | 81.96(0.6) | 69.40(1.1) | 46.40(2.7) | 66.28(1.5) | 44.00(5.3) | 4.1
G-Mix [11] | 82.04(1.8) | 87.32(2.4) | 84.89(1.4) | 80.32(0.7) | 69.90(1.8) | 45.87(3.0) | 68.07(1.2) | 46.17(4.3) | 3.0
EPIC |  82.31(0.1) |  87.80(1.2) |  85.74(0.6) |  82.19(0.5) |  70.80(1.7) | 47.07(1.4) | 67.44(1.2) |  47.17(5.6) | 1.4

Table 2: Classification AUC-ROC of MoleculeNet [37].

| Method | BBBP | BACE | HIV | Rank
---|---|---|---|---|---
GIN | Vanilla | 65.90(1.9) | 77.01(2.7) | 75.10(2.7) | 4.0
Dropedge [4] | 65.32(1.8) | 74.50(0.9) | 75.57(0.6) | 4.7
Dropnode [5] | 64.32(5.0) | 76.37(3.0) | 75.36(1.3) | 5.3
SubMix [10] | 65.58(5.0) | 75.26(6.8) | 76.36(1.3) | 3.7
M-Mix [8] | 64.48(1.6) | 75.30(2.6) | 75.55(2.0) | 4.7
G-Mix [11] | 64.33(3.2) |  78.54(1.9) | 75.29(0.6) | 4.3
EPIC |  68.33(1.9) | 77.17(3.2) |  76.85(1.4) | 1.3
GCN | Vanilla | 66.08(3.4) | 76.35(4.2) | 75.45(0.7) | 4.7
Dropedge [4] | 65.71(2.5) | 72.79(7.9) | 75.90(1.6) | 5.0
Dropnode [5] | 68.33(3.0) | 71.37(5.0) | 74.41(0.9) | 5.3
SubMix [10] | 67.68(1.2) | 75.19(5.6) | 75.61(2.1) | 4.0
M-Mix [8] | 67.38(2.0) |  79.67(0.9) | 75.23(1.2) | 3.7
G-Mix [11] | 65.10(2.3) | 77.54(5.3) | 75.99(0.9) | 4.0
EPIC |  68.68(2.3) | 77.67(1.7) |  76.81(1.3) | 1.3

#### Implementation details

We first learn the cost of edit operations for each dataset. We use Adam
optimizer [38] with a learning rate decay of 0.1 every 25 epochs. We train the
cost function for 100 epochs on TUDataset. While we use Sinkhorn-Knopp
approximation with $k=10$ in Equation 11 for training, the Hungarian algorithm
is used for inference to obtain an optimal assignment given costs. We perform
graph classification tasks with GIN [39] and GCN [40] as a backbone model for
augmentation. When we train each backbone model, we use the same
hyperparameter and architecture for all baselines and our method for a fair
comparison. We follow the Open Graph Benchmark setting [1] for MoleculeNet
dataset. When training classification models, we compute the edit path between
randomly paired graphs in each batch and use randomly chosen graphs from the
edit path as augmentation. We use the validation set to choose the portion of
augmented data points. The additional details of hyperparameters and model
configurations can be found in Appendix B.

#### Classificaiton results

Table 1 shows the overall results of the TUDataset for graph classification
tasks. Our augmentation method outperforms the other baselines on seven and
six datasets with GIN and GCN backbones, respectively, and achieves the
second-best performance on one dataset with GIN and GCN backbones. Table 2
shows the classification AUC-ROC with MoleculeNet datasets. The results show
that EPIC consistently improves classification accuracy over the vanilla
model, whereas the other augmentations occasionally degrade the classification
performance.

###  4.2 Robustness analysis

We conduct a study that shows the robustness of the augmentation method with
the presence of noisy labels. A similar study is also conducted in Hendrycks
et al. [13], Pang et al. [14]. We randomly corrupt labels in the training set
of IMDB-BINARY, IMDB-MULTI, and Mutagenicity datasets and test the model
performance with the uncorrupted test set. We run the experiments with three
different proportions of noise: $\\{0.2,0.4,0.6\\}$ based on GIN. Except for
the noise, we use the same setting used in Section 4.1. Table 3 shows the
classification accuracy with different proportions of noisy labels. EPIC
outperforms the other baseline models, except for one case, showing the
robustness of our augmentation under the noisy environment.

Table 3: Robustness analysis on IMDB-BINARY, IMDB-MULTI, and Mutagenicity
datasets. We randomly corrupt the label of the training set and measure the
test performance with random noise.

| IMDB-BINARY | IMDB-MULTI | Mutagenicity
---|---|---|---
Method | 20% | 40% | 60% | 20% | 40% | 60% | 20% | 40% | 60%
Vanilla | 72.50(1.2) | 66.10(1.6) | 44.30(6.6) | 48.00(1.2) | 46.07(1.1) | 42.33(3.7) | 75.30(0.7) | 68.52(1.4) | 46.38(3.1)
Dropedge [4] | 70.30(4.1) | 66.20(5.1) | 48.30(4.0) | 44.80(2.4) | 42.60(3.1) | 37.93(2.2) | 75.47(0.9) | 67.71(1.5) | 45.13(4.1)
Dropnode [5] | 70.90(1.0) | 68.80(3.4) | 52.40(2.3) | 45.60(1.9) | 43.00(2.5) | 39.53(1.9) | 72.98(1.5) | 66.26(1.5) | 45.89(3.1)
SubMix [10] | 72.20(1.0) | 67.70(2.0) | 43.10(9.4) | 48.67(1.2) | 45.53(1.3) | 40.60(5.2) | 73.00(1.5) | 66.86(2.6) |  59.03(2.5)
ManifoldMix [8] | 71.90(1.1) | 69.90(3.8) | 49.70(6.5) | 48.07(1.3) | 46.67(1.1) | 43.40(3.3) | 75.49(0.9) | 67.43(3.6) | 45.91(2.7)
G-Mix [11] | 71.60(1.9) | 70.00(4.3) | 44.60(10.0) | 47.33(0.8) | 44.80(2.1) | 40.67(1.7) | 76.06(1.5) | 69.25(0.8) | 45.27(4.1)
EPIC |  72.60(1.1) |  71.00(1.8) |  53.70(3.4) |  49.07(1.2) |  47.60(1.1) |  43.73(1.9) |  76.96(1.5) |  69.62(1.1) | 49.25(3.6)

###  4.3 Ablation studies

In this subsection, we show the result of ablation studies on each component
in EPIC. Further ablation studies are shown in Appendix C.

#### Cost function variations

We test the effectiveness of the learnable cost function against other
variations of the cost function. We use two variations of the cost function:
unit cost, which measures the number of edit operations, and feature-distance
cost, which measures the distance between two input node features, adopted
from Ling et al. [12].

The result in 4(a) shows that the learnable cost outperforms the other cost
functions across all datasets. The results empirically verify our claim that
the good cost function should be problem dependent and can be learned from the
dataset.

We also classify the graphs in the test dataset based on their distance to the
closest graph in each class. If the cost is learned properly, the distance
from a test graph to the graph in the same class should be close to each
other. 4(b) shows the result of distance-based classification. In most cases,
EPIC outperforms the other fixed-cost methods. For some datasets, such as
IMDB-BINARY, the distance-based classification performs similarly to the
classification model with augmentation.

Table 4: Comparisons between three different cost functions. Three different
cost functions: unit, feature-distance, and EPIC, are tested on TUDataset. GIN
is used as a backbone.

(a) Classification accuracy with augmentation

Method | NCI1 $\uparrow$ | BZR$\uparrow$ | COX2$\uparrow$ | Mutagen.$\uparrow$ | PROTEINS$\uparrow$ | ENZYMES$\uparrow$ | IMDB-B$\uparrow$ | IMDB-M $\uparrow$
---|---|---|---|---|---|---|---|---
Unit cost | 82.28(0.9) | 86.59(1.9) | 84.47(1.0) | 81.47(0.8) | 72.80(0.3) | 48.53(1.2) | 70.49(1.2) | 46.50(1.5)
Feature-distance | 81.65(1.4) | 85.37(1.5) | 83.83(1.2) | 81.73(0.4) | 73.10(0.7) |  48.93(0.5) | 69.96(1.2) | 46.17(2.7)
EPIC |  82.31(1.4) |  87.32(2.0) |  84.89(2.6) |  81.86(0.9) |  73.40(0.7) |  48.93(0.5) |  70.85(0.9) |  47.83(3.5)

(b) Distance-based classification accuracy

Method | NCI1 $\uparrow$ | BZR$\uparrow$ | COX2$\uparrow$ | Mutagen.$\uparrow$ | PROTEINS$\uparrow$ | ENZYMES$\uparrow$ | IMDB-B$\uparrow$ | IMDB-M $\uparrow$
---|---|---|---|---|---|---|---|---
Unit cost | 60.49(0.4) | 72.20(3.7) | 52.34(3.8) | 56.69(2.0) | 56.86(1.5) |  25.83(3.0) | 55.50(2.8) | 36.33(2.2)
Feature-distance | 60.70(0.8) | 72.93(4.0) | 52.55(3.2) | 55.51(1.8) |  57.31(1.7) |  25.83(2.9) | 56.00(2.8) | 36.20(1.6)
EPIC |  72.69(0.3) |  77.80(2.9) |  60.43(3.5) |  75.33(1.0) | 56.95(0.8) | 23.67(4.7) |  67.70(1.8) |  39.33(2.8)

(a) BBBP

(b) HIV

Figure 3: Training and validation loss curves on BBBP and HIV datasets with
Hungarian and Sinkhorn-Knopp algorithms in the training process.

#### Hungarian vs Sinkhorn-Knopp

We investigate the impact of a differentiable assignment matrix with the
Sinkhorn-Knopp algorithm against a fixed assignment matrix from the Hungarian
algorithm in the process of training. In Figure 3, we present the training and
validation curve on the BBBP and HIV datasets. In general, the Sinkhorn-Knopp
algorithm shows a more stable learning process than the Hungarian algorithm.
The training loss with Hungarian has not been stabilized after 40 epochs in
BBBP and 20 epochs in HIV datasets. Moreover, the validation loss of Sinkhorn-
Knopp is consistently lower than Hungarian after certain iterations. We
conjecture that the non-smooth loss surface of Hungarian makes the gradient
descent work hard, and eventually, the model fails to reach a good local
minimum, whereas the smooth loss surface of Sinkhorn-Knopp results in a better
performance despite being an approximation of Hungarian.

(a) Substitutions between positive pair

(b) Edit path between positive pair

(c) Substitutions between negative pair

(d) Edit path between negative pair

Figure 4: Examples of learned edit distance from a lollipop dataset. The
dashed lines in (a) and (c) represent the nodes with substitution operations.
The head nodes are substituted to their counterpart in the positive pair case,
whereas no substitution is performed between the heads of the negative pair.
(b) and (d) show the sampled edit path from the source to target graphs. The
lollipop head remains the same during the transition with a positive pair.

###  4.4 Qualitative analysis

To examine how the results of the learned distance are reflected in the
augmented graph, we conduct an experiment with a lollipop dataset whose
structural properties are easily visualized. The $(m,n)$-_lollipop_ graph
consists of a head, a complete graph with $m$ nodes, and a tail, a chain
structured $n$ nodes. The lollipop dataset consists of graphs with varying $m$
and $n$. The label of a graph is the size of the head, i.e., $m$. Figure 4
displays examples of the trained graph edit distances and the corresponding
edit path for positive and negative pairs. With a positive pair, the learned
graph edit distance substitutes the head nodes from the source graph for those
of the target graph. Eventually, it maintains the complete subgraph of the
head along the edit path. Whereas with a negative pair, the head nodes of the
source graph are deleted first, and those of the target graph are inserted
later. We also observe that the insertion and deletion costs of head nodes are
more expensive than those of tail nodes, making the distance between the
negative pair long. Additionally, we present the assigned cost for
substitution to each node in Appendix D, which consistently shows the
effectiveness of the cost function for EPIC.

##  5 Conclusion

In this paper, we have presented a novel approach for graph dataset
augmentation based on the graph edit distance. Our method overcomes the
limitations of linear interpolation techniques in the non-Euclidean domain and
provides a tailored augmentation solution for graph data. Through extensive
experiments on benchmark datasets, we have demonstrated the effectiveness of
our approach in improving the performance and robustness of graph-based
models. In this work, we only consider the node operation cost for
computational simplicity, but incorporating edge operation cost into the
framework would be a solid and important future direction.

## References

  * Hu et al. [2020] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ , 33:22118–22133, 2020.
  * Morris et al. [2020] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  In _ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020)_ , 2020.  URL www.graphlearning.io.
  * Leskovec et al. [2007] Jure Leskovec, Lada A Adamic, and Bernardo A Huberman.  The dynamics of viral marketing.  _ACM Transactions on the Web (TWEB)_ , 1(1):5–es, 2007.
  * Rong et al. [2019] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  _arXiv preprint arXiv:1907.10903_ , 2019.
  * Feng et al. [2020] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang.  Graph random neural networks for semi-supervised learning on graphs.  _Advances in neural information processing systems_ , 33:22092–22103, 2020.
  * You et al. [2020] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  _Advances in neural information processing systems_ , 33:5812–5823, 2020.
  * Zhang et al. [2017] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  _arXiv preprint arXiv:1710.09412_ , 2017.
  * Verma et al. [2019] Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio.  Manifold mixup: Better representations by interpolating hidden states.  In _International conference on machine learning_ , pages 6438–6447. PMLR, 2019.
  * Guo and Mao [2021] Hongyu Guo and Yongyi Mao.  ifmixup: Towards intrusion-free graph mixup for graph classification.  _arXiv e-prints_ , pages arXiv–2110, 2021.
  * Yoo et al. [2022] Jaemin Yoo, Sooyeon Shim, and U Kang.  Model-agnostic augmentation for accurate graph classification.  In _Proceedings of the ACM Web Conference 2022_ , pages 1281–1291, 2022.
  * Han et al. [2022] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu.  G-mixup: Graph data augmentation for graph classification.  In _International Conference on Machine Learning_ , pages 8230–8248. PMLR, 2022.
  * [12] Hongyi Ling, Zhimeng Jiang, Meng Liu, Shuiwang Ji, and Na Zou.  Graph mixup with soft alignments.
  * Hendrycks et al. [2019] Dan Hendrycks, Norman Mu, Ekin D Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  Augmix: A simple data processing method to improve robustness and uncertainty.  _arXiv preprint arXiv:1912.02781_ , 2019.
  * Pang et al. [2019] Tianyu Pang, Kun Xu, and Jun Zhu.  Mixup inference: Better exploiting mixup to defend adversarial attacks.  _arXiv preprint arXiv:1909.11515_ , 2019.
  * Shen et al. [2022] Zhiqiang Shen, Zechun Liu, Zhuang Liu, Marios Savvides, Trevor Darrell, and Eric Xing.  Un-mix: Rethinking image mixtures for unsupervised visual representation learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 2216–2224, 2022.
  * Thulasidasan et al. [2019] Sunil Thulasidasan, Gopinath Chennupati, Jeff A Bilmes, Tanmoy Bhattacharya, and Sarah Michalak.  On mixup training: Improved calibration and predictive uncertainty for deep neural networks.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Ullmann [1976] Julian R Ullmann.  An algorithm for subgraph isomorphism.  _Journal of the ACM (JACM)_ , 23(1):31–42, 1976\.
  * Durant et al. [2002] Joseph L Durant, Burton A Leland, Douglas R Henry, and James G Nourse.  Reoptimization of mdl keys for use in drug discovery.  _Journal of chemical information and computer sciences_ , 42(6):1273–1280, 2002.
  * Zhang et al. [2020] Shichang Zhang, Ziniu Hu, Arjun Subramonian, and Yizhou Sun.  Motif-driven contrastive learning of graph representations.  _arXiv preprint arXiv:2012.12533_ , 2020.
  * Abu-Aisheh et al. [2015] Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau.  An exact graph edit distance algorithm for solving pattern recognition problems.  In _4th International Conference on Pattern Recognition Applications and Methods 2015_ , 2015.
  * Cross et al. [1997] Andrew DJ Cross, Richard C Wilson, and Edwin R Hancock.  Inexact graph matching using genetic search.  _Pattern Recognition_ , 30(6):953–970, 1997.
  * Myers et al. [2000] Richard Myers, RC Wison, and Edwin R Hancock.  Bayesian graph edit distance.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 22(6):628–635, 2000.
  * Justice and Hero [2006] Derek Justice and Alfred Hero.  A binary linear programming formulation of the graph edit distance.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 28(8):1200–1214, 2006.
  * Fischer et al. [2015] Andreas Fischer, Ching Y Suen, Volkmar Frinken, Kaspar Riesen, and Horst Bunke.  Approximation of graph edit distance based on hausdorff matching.  _Pattern Recognition_ , 48(2):331–343, 2015.
  * Wang et al. [2021] Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang.  Combinatorial learning of graph edit distance via dynamic embedding.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5241–5250, 2021.
  * Cortés et al. [2019] Xavier Cortés, Donatello Conte, and Hubert Cardot.  Learning edit cost estimation models for graph edit distance.  _Pattern Recognition Letters_ , 125:256–263, 2019.
  * Caetano et al. [2009] Tibério S Caetano, Julian J McAuley, Li Cheng, Quoc V Le, and Alex J Smola.  Learning graph matching.  _IEEE transactions on pattern analysis and machine intelligence_ , 31(6):1048–1058, 2009.
  * Riba et al. [2021] Pau Riba, Andreas Fischer, Josep Lladós, and Alicia Fornés.  Learning graph edit distance by graph neural networks.  _Pattern Recognition_ , 120:108132, 2021.
  * Wang et al. [2020] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi.  Graphcrop: Subgraph cropping for graph classification.  _arXiv preprint arXiv:2009.10564_ , 2020.
  * Zhou et al. [2020] Jiajun Zhou, Jie Shen, and Qi Xuan.  Data augmentation for graph classification.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 2341–2344, 2020.
  * Li et al. [2019] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli.  Graph matching networks for learning the similarity of graph structured objects.  In _International conference on machine learning_ , pages 3835–3845. PMLR, 2019.
  * Airoldi et al. [2013] Edo M Airoldi, Thiago B Costa, and Stanley H Chan.  Stochastic blockmodel approximation of a graphon: Theory and consistent estimation.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Riesen and Bunke [2009] Kaspar Riesen and Horst Bunke.  Approximate graph edit distance computation by means of bipartite graph matching.  _Image and Vision computing_ , 27(7):950–959, 2009.
  * Schroff et al. [2015] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A unified embedding for face recognition and clustering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 815–823, 2015.
  * Kuhn [1955] Harold W Kuhn.  The hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2):83–97, 1955.
  * Sinkhorn and Knopp [1967] Richard Sinkhorn and Paul Knopp.  Concerning nonnegative matrices and doubly stochastic matrices.  _Pacific Journal of Mathematics_ , 21(2):343–348, 1967.
  * Wu et al. [2018] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande.  Moleculenet: a benchmark for molecular machine learning.  _Chemical science_ , 9(2):513–530, 2018.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Weininger [1988] David Weininger.  Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules.  _Journal of chemical information and computer sciences_ , 1988.
  * Martins et al. [2012] Ines Filipa Martins, Ana L Teixeira, Luis Pinheiro, and Andre O Falcao.  A bayesian approach to in silico blood-brain barrier penetration modeling.  _Journal of chemical information and modeling_ , 52(6):1686–1697, 2012.
  * Subramanian et al. [2016] Govindan Subramanian, Bharath Ramsundar, Vijay Pande, and Rajiah Aldrin Denny.  Computational modeling of $\beta$-secretase 1 (bace-1) inhibitors using ligand based approaches.  _Journal of chemical information and modeling_ , 56(10):1936–1949, 2016.
  * [44] DTP DTP.  Aids antiviral screen (2004).  _URL http://dtp. nci. nih. gov/docs/aids/aids-data. html_.
  * Wale et al. [2008] Nikil Wale, Ian A Watson, and George Karypis.  Comparison of descriptor spaces for chemical compound retrieval and classification.  _Knowledge and Information Systems_ , 14:347–375, 2008\.
  * Mahé and Vert [2009] Pierre Mahé and Jean-Philippe Vert.  Graph kernels based on tree patterns for molecules.  _Machine learning_ , 75(1):3–35, 2009.
  * Debnath et al. [1991] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch.  Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity.  _Journal of medicinal chemistry_ , 34(2):786–797, 1991.
  * Rozemberczki et al. [2020] Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar.  An api oriented open-source python framework for unsupervised learning on graphs.  _arXiv preprint arXiv:2003.04819_ , 10(3340531.3412757), 2020.
  * Dobson and Doig [2003] Paul D Dobson and Andrew J Doig.  Distinguishing enzyme structures from non-enzymes without alignments.  _Journal of molecular biology_ , 330(4):771–783, 2003.
  * Schomburg et al. [2004] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg.  Brenda, the enzyme database: updates and major new developments.  _Nucleic acids research_ , 32(suppl_1):D431–D433, 2004.
  * Flamary et al. [2021] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al.  Pot: Python optimal transport.  _The Journal of Machine Learning Research_ , 22(1):3571–3578, 2021.

##  Appendix A Dataset Details

#### Dataset statistics

We present the statistics for each dataset from TUDataset [2] and MoleculeNet
[37] in Table 5. It includes the number of data, classes, average nodes, and
edges, the source of data, and the presence of node and edge labels. For BBBP,
BACE, and HIV datasets, we use OGB package [1] to convert SMILES strings [41],
the sequence of atoms and symbols, to molecular graphs.

Table 5: Statistics for each dataset from TUDataset [2] and MoleculeNet [37].

Dataset | Size | Classes | Source | Avg.nodes | Avg.edges | Node labels | Edge labels
---|---|---|---|---|---|---|---
BBBP [42] | 2039 | 2 | Small molecule | 24.06 | 51.91 | ✓ | ✓
BACE [43] | 25 | 2 | Small molecule | 34.09 | 73.72 | ✓ | ✓
HIV [44] | 41127 | 2 | Small molecule | 25.51 | 54.94 | ✓ | ✓
NCI1 [45] | 4110 | 2 | Small molecule | 29.87 | 32.30 | ✓ | ✗
BZR [46] | 405 | 2 | Small molecule | 35.75 | 38.36 | ✓ | ✗
COX2 [46] | 467 | 2 | Small molecule | 41.22 | 43.45 | ✓ | ✗
Mutagenicity [47] | 4337 | 2 | Small molecule | 30.32 | 30.77 | ✓ | ✗
IMDB-BINARY [48] | 1000 | 2 | Ego network | 19.77 | 96.53 | ✗ | ✗
IMDB-MULTI [48] | 1500 | 3 | Ego network | 13.00 | 65.94 | ✗ | ✗
PROTEINS [49] | 1113 | 2 | Macro molecule | 39.06 | 72.82 | ✓ | ✗
ENZYMES [50] | 600 | 6 | Macro molecule | 32.63 | 62.14 | ✓ | ✗

#### Dataset description

We use 10 graph-level classification datasets: BBBP, BACE, HIV from
Moleculenet [37] and NCI1, BZR, COX2, Mutagenicity, IMDB-BINARY, IMDB-MULTI,
PROTEINS, ENZYMES from TUDatset [2]. The details of each dataset are shown in
Table 6. Through the various dataset from a wide range of domains, we can test
the effect of our EPIC for graph classification.

Table 6: Detailed description for each dataset from TUDataset [2] and
MoleculeNet [37]

Dataset | Description
---|---
BBBP | Binary classification to predict blood-brain barrier penetration of given molecule
BACE | Binary classification to predict binding results for a set of inhibitors of human $\beta$-secretase $1$ of a given molecule
HIV | Binary classification to predict experimentally measured abilities to inhibit HIV replication
NCI1 | Binary classification to predict bio-assays result to suppress the growth of human non-small cell lung cancer.
BZR | Binary classification to predict ligands for the benzodiazepine receptor
COX2 | Binary classification to predict cyclooxygenase-2 Inhibitors
Mutagenicity | Binary classification to predict mutagenic bio-active compounds
IMDB-BINARY (MULTI) | Binary (Multi) classification to predict the genre of ego network derived from actor collaboration
PROTEINS | Multiclass classification to predict whether a protein is an enzyme
ENZYMES | Multiclass classification to assign enzymes to one of the 6 classes, which reflect the catalyzed chemical reaction

##  Appendix B Experiment Settings

#### Dataset split

To evaluate the performance of TUDataset, we split the dataset into the train,
validation, and test sets using the ratio of 7:1:2. To address the issue of
imbalanced labels within the dataset, we make each split has the same
proportion of labels. We use the split provided by the Open Graph Benchmark
[1] to evaluate the performance of the MoleculeNet dataset. The same split is
used for all experiments.

#### Training cost function

To train the cost function using the triplet loss, we randomly sample a
positive sample and a negative sample from the dataset. On each epoch,
different samples are randomly chosen for training, while fixed samples are
used during the evaluation step. Python Optimal Transport [51] is employed to
implement the Sinkhorn-Knopp algorithm. The model with the best validation
loss is used for augmentation and additional experiments. The hyperparameters
include the learning rate, the number of layers in the backbone GNN, and the
parameter $\delta$ in Equation 11. Table 7 provides an overview of the
hyperparameter search space.

Table 7: Hyperparameter search space for training the cost function.

Hyperparameter | Values
---|---
Learning rate | 0.01, 0.001
# layers | 2, 5
$\delta$ | 0.3, 0.1, 0.01

#### Training vanilla model

Following the experimental setup of [4, 11, 12], we initially tune the
hyperparameters related to the backbone model structure and the model
training. These hyperparameters are then fixed to evaluate the performance of
the augmentation methods. The hyperparameter search space for the vanilla
model is provided in Table 8.

Table 8: Hyperparameter search space for training the vanilla model.

Hyperparameter | Values
---|---
Learning rate | 0.01, 0.001, 0.0001
# layers | 2, 5
Batch size | 32, 64
Hidden dim | 16, 32, 64, 128

For the TUDataset, we train the model for 100 epochs and evaluate the mean
accuracy and standard deviation over five runs. In the case of the MoleculeNet
dataset, we train the model for 100 epochs for the BBBP and BACE datasets and
for 50 epochs for the HIV dataset. The mean AUC-ROC and standard deviation are
evaluated over three runs.

#### Training EPIC

During the augmentation process, a random pair of graphs is chosen as a source
and target graph. One graph from the edit path between the source and target
graphs is selected as the augmented data.

When evaluating the performance of EPIC, we tune two hyperparameters and
select the hyperparameter combination that yields the best performance on the
validation set. The augmentation ratio determines the proportion of augmented
data versus the original training data. The maximum augmentation distance
determines the relative maximum distance from the source to the augmented
graph. A smaller maximum augmentation distance indicates that graphs closer to
the source graph are sampled for augmentation. The hyperparameter search space
for the EPIC is provided in Table 9.

Table 9: Hyperparameter search space for training the EPIC.

Hyperparameter | Values
---|---
Aug ratio | 0.3, 0.5, 0.7
Max aug distance | 0.1, 0.3, 0.5

##  Appendix C Ablation Study

In this section, we describe the ablation studies conducted to configure the
model structure. Specifically, we investigate the influence of different
methods for determining the operation order in the edit path and the number of
iterations in the Sinkhorn-Knopp algorithm.

#### Ablation operation ordering

When calculating the edit distance, the specific operation order does not
affect the final result. To construct the edit path, we need to determine the
operation order. In our analysis, we investigate the difference between two
choices of operation orders. To maintain the local connectivity of the target
graph within the edit path, we employ a breadth-first search (BFS) on the
target graph, and node insertion/deletion/substitution is performed following
the BFS order. The results in Table 10 compare randomly ordered augmentation
with BFS-ordered augmentation on eight datasets. We find no significantly
better ordering choices between these two methods. To minimize additional
computational overhead, we utilize random ordering for the main result.

Table 10: Comparison of randomly ordered augmentation and BFS-ordered
augmentation.

|  Method | NCI1 | BZR | COX2 |  Mutagen. | IMDB-B | IMDB-M | PROTEINS | ENZYMES
---|---|---|---|---|---|---|---|---|---
GIN | BFS | 81.85(0.5) |  87.32(1.6) | 84.47(1.8) |  82.09(0.5) | 72.80(0.8) | 48.47(1.0) | 69.69(2.1) |  49.00(1.8)
Random |  82.31(1.5) |  87.32(2.0) |  84.89(2.7) | 81.86(1.0) |  73.40(0.8) |  48.93(0.6) |  70.85(0.9) | 47.83(3.5)

#### Ablation on iterations of the Sinkhorn-Knopp algorithm

We adopt the Sinkhorn-Knopp algorithm to approximate the Hungarian algorithm
to make the assignment matrix differentiable for optimization during training
as described in Section 3.2. To analyze the effect of the number of iterations
of the Sinkhorn-Knopp algorithm, we evaluate the classification performance
under varying values of $k$ in Equation 11. Table 11 presents the results of
an ablation study.

Table 11: Classification performance under varying values of $k$.

|  | $k$
---|---|---
|  Dataset | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
GIN | BZR | 87.32(2.8) | 87.07(3.3) | 88.29(2.2) | 86.34(3.2) | 86.34(2.3) |  89.76(2.8) | 86.83(3.7) | 88.29(2.8) | 88.29(1.1) | 87.32(1.5)
COX2 | 82.98(0.0) | 84.04(1.7) | 84.04(1.7) | 84.26(2.8) | 84.04(2.9) | 83.62(1.2) |  85.11(1.5) | 82.77(2.2) | 83.40(2.2) | 84.89(2.7)
IMDB-B | 72.50(0.9) | 72.40(1.2) | 72.60(0.4) | 72.90(1.1) | 72.80(1.0) | 72.20(0.8) | 72.70(0.6) | 72.50(0.4) | 73.10(0.2) |  73.40(0.8)
IMDB-M | 48.47(0.8) | 48.33(1.5) | 48.40(1.2) | 48.67(1.0) | 47.67(0.8) | 47.80(1.5) | 48.87(0.4) | 48.33(0.8) |  49.00(0.5) | 48.93(0.6)
ENZYMES | 46.17(3.1) | 46.33(3.4) | 47.33(3.1) | 47.50(4.8) | 44.67(3.9) |  48.17(3.1) | 44.33(5.0) | 43.17(3.5) | 46.00(3.3) | 47.83(3.5)
| Rank | 6.4 | 6.2 | 4.4 | 4.4 | 7.0 | 5.6 | 5.2 | 7.2 | 4.0 | 2.4

We further experiment to observe how well the assignment matrix, $X_{S}$,
derived from the Sinkhorn-Knopp algorithm approximates the assignment matrix,
$X_{H}$, from the Hungarian algorithm, as the parameter $k$ varies. Firstly,
we calculate both assignment matrices from our learned cost function on the
test dataset and compute the Frobenius norm of the difference between the two
matrices, $||X_{A}||_{F}=||X_{S}-X_{H}||_{F}$, and then, measure an average of
each Frobenius norm across the entire dataset.

Figure 5 shows the average of Frobenius norm with varying $k$. We observe that
the error decreases as $k$ increases, suggesting that the Sinkhorn-Knopp
algorithm’s assignment matrix becomes more similar to the assignment matrix
from the Hungarian algorithm. However, as $k$ increases, the computational
cost required for training also increases, indicating a trade-off
relationship.

Figure 5: Frobenius norm of the difference between Hungarian algorithm’s
assignment matrix and Sinkhorn-Knopp algorithm’s assignment matrix with
varying $k$ in Equation 11.

##  Appendix D Further Analysis on _Lollipop_ Dataset

To further show the effectiveness of the cost function for EPIC, we analyze
the cost for substitution to each node on the _lollipop_ dataset.
$(m,n)$-_lollipop_ graph consists of a head, a complete graph with $m$ nodes,
and a tail, a chain structured $n$ nodes, with varying $m$ and $n$. We use the
number of heads as the label of a graph, i.e., $m$. Figure 6 shows the head-
to-head, head-to-tail, and tail-to-tail substitution costs. For instance, the
head-to-head substitution cost measures the average substitution costs between
the head nodes from the source graph with those of the target graph.

With the _negative pair_ , the average node substitution cost for the head
nodes is $0.97$, whereas the average for the tail nodes is $0.04$. These
results align with our intuition that editing the head, closely related to the
label, incurs a high cost. Thus, any modification to this part leads to
substantial changes in the label. With the _positive pair_ , the head-to-head
and tail-to-tail substitution costs are $0.07$ and $0.2$, respectively. Those
values are much smaller than $0.8$ of head-tail costs. The lower cost for the
head-head substitution in a positive pair resulted from the fact that it
involves the exchange of nodes associated with the same label. Similarly, the
low cost for the tail-to-tail substitution aligns well with our intuition
since the nodes are unrelated to the label. In contrast, the head-to-tail
substitution is assigned a high cost because it substitutes a label-associated
part with a non-associated part. This preserves the head part of every graph
on the edit path between _positive_ -pair, ensuring that the augmented graph
keeps the same label over the path.

(a) Average substitution costs between negative pair

(b) Average substitution costs between positive pair

Figure 6: Analysis of substitution cost on _lollipop_ graph. Normalized
average substitution costs between source nodes and target nodes for
_negative_ pair are shown in 6(a) and _positive_ pair in 6(b). The costs are
averaged across the entire dataset.

##  Appendix E Examples of Edit Path

Figure 7 and Figure 8 illustrate examples of the edit path generated by EPIC
on the IMDB-BINARY dataset and PROTEINS dataset, respectively. In each figure,
the upper left graph with blue nodes represents the source graph, and the
lower right graph with red nodes represents the target graph.

Figure 7: The example of the edit path generated by EPIC on the IMDB-BINARY
dataset. Figure 8: The example of the edit path generated by EPIC on the
PROTEINS dataset.


11institutetext: Keio University, Yokohama, Kanagawa, Japan
{ryo-hachiuma, tomy1201<EMAIL_ADDRESS>22institutetext: Keio University School
of Medicine, Shinjuku-ku, Tokyo, Japan
{jmrbx767<EMAIL_ADDRESS>
# Deep Selection: A Fully Supervised Camera Selection Network for Surgery
Recordings

Ryo Hachiuma 11 0000-0001-8274-3710 Tomohiro Shimizu 11 Hideo Saito 11
0000-0002-2421-9862 Hiroki Kajita 22 Yoshifumi Takatsume 22

###### Abstract

Recording surgery in operating rooms is an essential task for education and
evaluation of medical treatment. However, recording the desired targets, such
as the surgery field, surgical tools, or doctor’s hands, is difficult because
the targets are heavily occluded during surgery. We use a recording system in
which multiple cameras are embedded in the surgical lamp, and we assume that
at least one camera is recording the target without occlusion at any given
time. As the embedded cameras obtain multiple video sequences, we address the
task of selecting the camera with the best view of the surgery. Unlike the
conventional method, which selects the camera based on the area size of the
surgery field, we propose a deep neural network that predicts the camera
selection probability from multiple video sequences by learning the
supervision of the expert annotation. We created a dataset in which six
different types of plastic surgery are recorded, and we provided the
annotation of camera switching. Our experiments show that our approach
successfully switched between cameras and outperformed three baseline methods.

###### Keywords:

Surgery recording Camera selection Deep neural network.

##  1 Introduction

Recording plastic surgeries in operating rooms with cameras has been
indispensable for a variety of purposes, such as education, sharing surgery
technologies and techniques, performing case studies of diseases, and
evaluating medical treatment [11, 13]. The targets that best depict the
surgery, such as the surgical field, doctor’s hands, or surgical tools, should
be recorded for these purposes. The recording target differs for each surgery
type and the purpose of recording.

However, it is difficult to continuously record these targets without any
occlusion. If the camera is attached to the operating room environment, the
targets may be occluded by the doctors, nurses, or surgical machines. If the
camera is attached to the doctor’s head to record video from the first-person
view, the camera’s field of view does not always capture the target, and the
video is often affected by motion blur because of the doctor’s head movements.
Therefore, a first-person viewpoint camera is not suitable for recording
surgery. Moreover, the doctors are disturbed by the camera which is attached
to their head during the surgery which requires careful and sensitive
movement.

Shimizu et al. [14] proposed a novel surgical lamp system with multiple
embedded cameras to record surgeries. A generic surgical lamp has multiple
light bulbs that illuminate the surgical field from multiple directions to
reduce the shadows caused by the operating doctors. Hence, Shimizu et al.
expected that at least one of the multiple light bulbs would almost always
illuminate the surgical field. In the same way, we can expect that at least
one of the multiple cameras embedded in the surgical lamp system will always
record the target without occlusion.

As the cameras obtain multiple videos of a single surgery, Shimizu et al. also
proposed a method to automatically select the image with the best view of the
surgical field at each moment to generate one video. By assuming that the
quality of the view is defined by the visibility (area size) of the surgical
field, they used an image segmentation [8] trained for each surgery using
manually annotated images. Then, they applied Dijkstra’s algorithm to generate
a smooth video sequence in which the selected camera does not change
frequently over a period of time.

Although their method only focuses on the visibility of the surgical field,
the visibility of the field is not always treated as the cue of the best view
for recording surgeries. The recording target differs for each surgery type
and the purpose of the recording. In some cases, the pose or the motion of the
doctor’s hands and surgical tools may be the most important, so the best view
should not always be determined by the larger surgical field. A method based
on image segmentation of predefined target objects is therefore not suitable
to select the best view from the multiple videos of the surgical scene.

In this paper, we aim to establish a method to select the best view based on
annotated labels by humans, rather than simply using the area size of the
surgery field. We address the task in a fully supervised manner, in which the
camera selection label is directly given to the prediction model during
training, and the predictor learns to map the video sequences to the
corresponding selected camera labels. No prior work has been proposed that
addresses the task of selecting the best camera view of surgery recordings in
a fully supervised manner.

The naive approach to solve this task is to formulate it as a multi-class
classification problem, in which the model outputs the selected camera index.
However, if the number of cameras in the recording system changes from the
training time to the test time, the model cannot be applied at the test time
as the number of categories (camera index) will differ. We, therefore, predict
the probability of selecting each camera against each frame in the video
sequences instead of predicting the selected camera index. When humans create
a single video that depicts the surgery the best from multiple video
sequences, they consider not only the temporal information of each video
sequence but also the intra-camera context. We, therefore, present a deep
neural network that aggregates information from multiple video sequences not
only sequentially but also spatially (intra-camera direction) to predict the
probability of selecting each camera from each frame.

As there is no dataset available to the public containing surgery recordings
via multiple cameras, we record our dataset using the system proposed by
Shimizu et al. [14]. The actual plastic surgeries are recorded at our
university’s school of medicine. We record six different types of surgery with
five cameras attached to the surgical lamp. We validate our proposed model
with this dataset, and we quantitatively evaluate our approach with three
baseline methods to verify the effectiveness of our approach. The experiments
show that our approach can create a video with the best views from multiple
video sequences.

In summary, our contributions are as follows: (1) To the best of our
knowledge, this is the first study to address the task of selecting the
cameras with the best views from multiple video sequences for the purpose of
recording surgery. (2) We propose an end-to-end deep learning network for the
selection of cameras with the best views, which aggregates the visual context
features sequentially and spatially. (3) We create a dataset of a variety of
plastic surgeries recorded with multiple cameras, we provide camera-switching
labels via a human expert, and we conduct extensive experimentation from
qualitative and quantitative perspectives to show the effectiveness of our
method. Please also refer to our accompanying video.

##  2 Related Work

Multiple cameras are used in many situations, such as office environments,
sports stadiums, and downtown areas. Although large areas can be recorded
without occlusion using multiple cameras, only the necessary information must
be selected from the huge number of video sequences recorded by multiple
cameras. Self-controlled camera technology, such as automatic viewpoint
switching, multiple video summarization, is therefore regarded as an important
issue [1].

Liu et al. [10] presented a rule-based camera switching method inspired by the
heuristic knowledge of a professional video editor. Their method successfully
switches between the viewpoints of three cameras shooting the speaker and the
audience. Doubek et al. [4] recorded moving objects with multiple cameras
embedded in an office environment. Cameras were selected based on their score,
and a resistance coefficient was introduced so that the cameras were switched
only when the score changed significantly. In these methods, camera switching
is conducted based on the heuristic knowledge of the professional.

Recently, Chen et al. [2] presented a camera selection method in which the
rich deep features are extracted from the neural network and online regression
to broadcast soccer games. As they stated in the discussion, their method is
sensitive to experimental parameters, such as the range of camera duration and
the weight of the regularization term. Moreover, their method requires pre-
processing and post-processing of the image and camera selection indices. On
the other hand, our end-to-end deep neural network directly learns to map the
multiple video sequences to the camera selection indices.

The work most relevant to ours is that presented by Shimizu et al. [14]. They
presented a surgery recording system with multiple cameras embedded in the
surgery lamp, with the assumption that at least one of the cameras will always
record the surgery field. They also proposed a camera selection method that
can select one frame among multiple frames obtained by the cameras. They
calculated the area size of the surgery field of each frame, and they applied
Dijkstra’s algorithm to obtain smooth camera selection indices based on the
segmentation score. The aim of the current study differs from theirs. As it is
not always best to record the entire surgery field, it is difficult to
determine the camera selection criterion beforehand. We, therefore, provide
the ground truth of camera selection directly to the predictor, and the
predictor learns to map the multiple video sequences to the camera selection
process in a fully supervised manner.

##  3 Approach

Figure 1: The network architecture of the proposed method

###  3.1 Problem Formulation

Our task is to estimate a sequence of camera labels ${\bf y}=\langle
y_{1},y_{2},\ldots,y_{T}\rangle$, where $y_{t}\in[1,N]$, and $T$ denotes the
number of frames in the sequence, from image sequences
${\bm{I}}=\langle{\bm{I}}_{1},{\bm{I}}_{2},\dots,{\bm{I}}_{T}\rangle$, where
${\bm{I}}_{t}=\langle I^{1}_{t},I^{2}_{t},\ldots,I^{N}_{t}\rangle$, from $N$
cameras. The naive approach to solve this task is to treat it as an $N$-class
classification problem similar to the image classification task: that is to
say, to classify a set of images ${\bm{I}}_{t}$ into $N$ classes for each
point in time. On the other hand, our network predicts the camera selection
probability ${\bm{p}}_{t}^{n}$ for each camera and solve the task as a binary
classification problem. The predicted camera labels $y_{t}$ can be obtained by
calculating the maximum selection probabilities ${\bm{p}}_{t}^{n}$.

###  3.2 Network Architecture

Our network architecture is represented in Figure 1. The network is composed
of four components; visual feature extraction, spatial feature aggregation,
sequential feature aggregation, and selection probability module. First, we
extract the visual feature $\phi_{t}^{n}\in{\mathbb{R}}^{128}$ from each image
$I_{t}^{n}$. We employ ResNet-18 [6] as the visual feature extractor.

Next, we aggregate the features from multiple cameras at each time step to
consider intra-camera (spatial) context,
$\psi_{t}^{G}={\mathbb{A}}(\phi_{t}^{1},\ldots\phi_{t}^{N})$, where
${\mathbb{A}}$ is a spatial feature aggregation module that combines the
independent camera local feature $\phi_{t}^{n}$ into an aggregate feature
$\psi_{t}^{G}$. The aggregated feature should be invariant to the input
permutation as the number of cameras or the index of cameras can be changed at
the test time. To handle unordered feature aggregation, we use the idea of
neural network on 3D point cloud processing. As the order of points should not
be mattered for the extraction of the point cloud’s global feature, the point
cloud’s global feature should be invariant to the order of points. Inspired by
PointNet [12], we employ max pooling as ${\mathbb{A}}$ to extract the global
feature $\psi_{t}^{G}$. The global feature is concatenated to each local
feature $\phi_{t}^{n}$ to obtain the context feature $\psi_{t}^{n}$.

Then, we aggregate the context features over time,
${\hat{\psi}}_{1}^{n},\ldots{\hat{\psi}}_{t}^{n}={\mathbb{B}}(\psi_{1}^{n},\ldots\psi_{t}^{n})$,
where ${\mathbb{B}}$ is a sequential feature aggregation module that computes
the sequential feature ${\hat{\psi}}_{t}^{n}$. In our experiments, we employ a
BiLSTM recurrent neural network [5] with one hidden layer for ${\mathbb{B}}$
which aggregate not only the past sequence but also future sequence against
the target feature.

The output feature ${\hat{\psi}}_{1}^{n},\ldots,{\hat{\psi}}_{t}^{n}$ is then
fed to a multilayer perceptron (MLP) with two hidden layers and leaky
rectified linear units (LeakyReLU) activation function [15] to predict the
selection probability $p_{1}^{n},\ldots,p_{T}^{n}$. The sigmoid activation
function is applied to the output layer. Final predicted camera labels can be
obtained by calculating the maximum selection probabilities at each time step:
$y_{t}=\mathop{\rm arg~{}max}\limits_{1\leq n\leq N}p_{t}^{n}$ where
$p_{t}^{n}$ denotes a camera’s selection probability at the time step $t$ of
$n$-th camera.

###  3.3 Loss function

Because we formulate the task as binary classification problem, the optimal
weight of the network can be obtained using the binary cross entropy between
the prediction $p_{t}^{n}$ and the ground-truth ${\hat{p}}_{t}^{n}$. However,
a class imbalance exists between two categories: selected and not selected.
For example, the ratio of selected labels and not-selected labels is $1:3$ in
the case of four cameras. This class imbalance during training overwhelms the
cross entropy loss. Easily classified negatives (not selected) comprise the
majority of the loss and dominate the gradient. We therefore employ the focal
loss [9], inspired by the two-stage object detection method. The focal loss
$L$ we employ is as follows:

$L({\bm{\xi}})=-\frac{1}{NT}\sum_{n=1}^{N}\sum_{t=1}^{T}(1-q_{t,n})^{\gamma}\log
q_{t,n},$ (1)

where $q_{t,n}$ is $p_{t}^{n}$ when the $n$-th camera at the time step $t$ is
selected as the best camera view (${\hat{p}}_{t}^{n}=1$), and $q_{t,n}$ is
$1-p_{t}^{n}$ when the $n$-th camera at the time step $t$ is not selected as
the best camera view (${\hat{p}}_{t}^{n}=0$). ${\bm{\xi}}$ is the parameters
of the proposed model. $\gamma$ is focusing parameter $\gamma\geq 0$.

##  4 Experiments

###  4.1 Dataset

As there is no dataset available that contains surgery recordings with
multiple cameras, we use the system proposed by Shimizu et al. [14] to create
our dataset. The surgeries are recorded at Keio University School of Medicine.
Video recording of the patients is approved by the Keio University School of
Medicine Ethics Committee, and written informed consent is obtained from all
patients or parents. We record six different types of surgery with five
cameras attached to the surgical lamp. Each surgery is $30$ minutes long, and
the video is recorded at $30$ frames per second (FPS). We subsampled every
five frames for each sequence. The ground-truth annotations are created by a
single expert.

###  4.2 Network training

We employ Adam optimizer [7] with a learning rate of $1.0\times 10^{-4}$. When
training the model, we randomly sample a data fragment of $T=40$ frames. The
model converged after $50$ epochs, which takes about six hours on a GeForce
Quadro GV100. We apply dropout with the $0.5$ probability during training to
reduce the overfitting at the first layer of MLP. We set $\gamma=2.0$ of focal
loss [9]. The weights of ResNet-18 is initialized with the pretrained ImageNet
[3]. We train the model with batch size $2$.

###  4.3 Comparison with the other method and baselines

No prior work has been proposed that addresses the task of switching between
cameras using deep learning for the creation of surgical videos. We therefore
set three baseline methods to validate our approach. We compare the following
baselines:

  * •

Ours w/o spa., seq.: Our camera selection method without spatial feature
aggregation and sequential feature aggregation. This method estimates the
camera probability using ResNet-18 and MLP.

  * •

Ours w/o spa.: Our camera selection network without the spatial feature
aggregation module. In this model, the context of other cameras are not
considered to predict each camera’s selection probability.

  * •

Ours w/o seq.: Our camera selection network without the sequential feature
aggregation module. In this model, the sequential context is not considered to
predict each camera’s selection probability.

Moreover, we also compare the results with Shimizu et al. [14] as the
reference. The focus of this paper is to predict the camera label which is
adapted for each expert. We do not aim to generate the model generalized for
different experts, but the model that represents each expert’s subjective
selection. In contrast, Shimizu et al. [14] aims to select the camera based on
the generic criterion obtained by segmenting the surgical field. This means
that we aim the different goals from Shimizu et al. [14]. However, comparing
the accuracy of the method [14] evaluates how much the expert see the surgical
field during the annotation. We follow the experimental setup for training the
segmentation model and switching parameter as same as the original paper [14].

##  5 Results

Table 1: Quantitative results for camera selection for sequence-out and
surgery-out settings. The dice score (F value) is employed as the evaluation
metric so a higher value is better. S1 to S6 denote the indices of surgeries.
The accuracy of Shimizu et al. [14] is shown as the reference.

| Sequence-Out
---|---
Method | S1 | S2 | S3 | S4 | S5 | S6 | Average
Shimizu et al. [14] | 0.58 | 0.59 | 0.57 | 0.45 | 0.34 | 0.56 | 0.52
Ours w/o spa., seq. | 0.45 | 0.39 | 0.98 | 0.28 | 0.36 | 0.36 | 0.47
Ours w/o spa. | 0.50 | 0.42 | 0.95 | 0.42 | 0.39 | 0.39 | 0.52
Ours w/o seq. | 0.45 | 0.43 | 0.98 | 0.33 | 0.32 | 0.38 | 0.48
Ours | 0.54 | 0.44 | 0.98 | 0.36 | 0.46 | 0.44 | 0.54
|  |  |  |  |  |  |

| Surgery-Out
---|---
Method | S1 | S2 | S3 | S4 | S5 | S6 | Average
Shimizu et al. [14] | 0.46 | 0.44 | 0.20 | 0.30 | 0.33 | 0.52 | 0.38
Ours w/o spa., seq. | 0.41 | 0.45 | 0.82 | 0.50 | 0.37 | 0.35 | 0.48
Ours w/o spa. | 0.46 | 0.45 | 0.89 | 0.69 | 0.38 | 0.38 | 0.54
Ours w/o seq. | 0.40 | 0.48 | 0.88 | 0.56 | 0.40 | 0.38 | 0.52
Ours | 0.44 | 0.47 | 0.90 | 0.70 | 0.42 | 0.43 | 0.56
|  |  |  |  |  |  |

###  5.1 Sequence-Out Evaluation

In this setting, we sequentially split six surgery videos into training and
test data at the ratio of $80\mbox{--}20$. In this setup, we adopted the
sequence-out cross-validation protocol to evaluate our method. That is to say,
the surgery type is known at the test-time but the sequence is unknown at the
test-time. Even though the surgery type is known at the test-time, this
setting is challenging as single surgery contains multiple sub-tasks so the
scene drastically changes between the training and test sequence. The
quantitative results are summarized in Table 1. As shown in Table 1, the
prediction accuracy improves with the use of each module in the proposed
network. It can be seen that Shimizu et al. [14] outperformed the other
methods for four sequences. However, the rich segmentation annotations are
needed at each surgery for Shimizu et al. [14].

The qualitative results of camera switching are shown in Figure 2 (left). As
Figure 2 shows, our model successfully selects the frame with the best view
from among five cameras, and the predicted camera indices are similar to the
camera indices of the ground truth. For example, in the first frame (leftmost
column), the surgical field is the most visible at the frame from Camera $4$.

Figure 2: Qualitative results for (left) Sequence-Out setting and (right)
Surgery-Out setting. The predicted camera frame is highlighted in green, and
the ground-truth camera frame is highlighted in red. The column direction
indicates the time step, and the row direction indicates the camera indices
(Cam.0, …, Cam.4)

###  5.2 Surgery-Out Evaluation

To further test the robustness of the proposed method, we perform the
experiments in the surgery-out setting, in which we train our model on four
surgery videos and test it on the two videos. In this setup, we adopted the
surgery-out cross-validation protocol to evaluate our method. This is a more
challenging setting since the surgery type is completely unknown to the model
at the test-time, and a variety of surgery types exist in the dataset. The
quantitative results are summarized in Table 1. As shown in Table 1, our
method outperforms other baseline methods. As the unseen surgical field
appeared at the test time for Shimizu et al. [14], the performance
significantly drops for surgery-out settings.

The qualitative results of camera switching is visualized in Figure 2 (right).
Even though the type of the surgery is not included in the training dataset,
our model successfully selects the best-viewed frame as like the ground-
truth’s. For the last frame, even though the predicted camera index is not
matched to the ground-truth index, the surgery field, surgical tools, and the
hand are captured within the frame.

##  6 Conclusion

We tackled, for the first time, the task of selecting the camera with the best
view from multiple video sequences of a surgery. Our model learns to map each
video sequence for selection probability while aggregating the features along
the intra-camera and temporal directions in a fully supervised manner. Our
experiments revealed that our method successfully selects the same camera
indices as the ground truth. As the video is divided into the sub-sequences
($40$ frames) to input to the network, the model cannot consider the whole
sequence of the long surgery video for the prediction. Therefore, we will
investigate the autoregressive model which relies on the prediction of the
previous output.

## Acknowledgement

This research was funded by JST-Mirai Program Grant Number JPMJMI19B2, ROIS
NII Open Collaborative Research 2020-20S0404, SCOPE of the Ministry of
Internal Affairs and Communications and Saitama Prefecture Leading-edge
Industry Design Project, Japan. We would like to thank the reviewers for their
valuable comments.

## References

  * [1] Chen, J., Carr, P.: Autonomous camera systems: A survey. In: Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence (2014)
  * [2] Chen, J., Meng, L., Little, J.J.: Camera selection for broadcasting soccer games. In: Winter Conference on Applications of Computer Vision (WACV). pp. 427–435. IEEE (2018)
  * [3] Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: ImageNet: A Large-Scale Hierarchical Image Database. In: Conference on Computer Vision and Pattern Recognition (CVPR). IEEE (2009)
  * [4] Doubek, P., Geys, I., Svoboda, T., Van Gool, L.: Cinematographic rules applied to a camera network. In: The fifth Workshop on Omnidirectional Vision, Camera Networks and Non-Classical Cameras. pp. 17–29. Prague, Czech Republic: Czech Technical University (2004)
  * [5] Graves, A., Fernández, S., Schmidhuber, J.: Bidirectional lstm networks for improved phoneme classification and recognition. In: Proceedings of the 15th International Conference on Artificial Neural Networks: Formal Models and Their Applications - Volume Part II. p. 799–804. Springer-Verlag (2005)
  * [6] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Conference on Computer Vision and Pattern Recognition (CVPR). pp. 770–778. IEEE (Jun 2016)
  * [7] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In: International Conference on Learning Representations (ICLR) (2015)
  * [8] Li, C., Kitani, K.M.: Pixel-level hand detection in ego-centric videos. In: Conference on Computer Vision and Pattern Recognition (CVPR). pp. 3570–3577. IEEE (Jul 2013)
  * [9] Lin, T., Goyal, P., Girshick, R., He, K., Dollár, P.: Focal loss for dense object detection. In: International Conference on Computer Vision (ICCV). pp. 2999–3007. IEEE (Oct 2017)
  * [10] Liu, Q., Rui, Y., Gupta, A., Cadiz, J.J.: Automating camera management for lecture room environments. In: Proceedings of the SIGCHI conference on Human factors in computing systems. pp. 442–449. ACM (2001)
  * [11] Matsumoto, S., Sekine, K., Yamazaki, M., Funabiki, T., Orita, T., Shimizu, M., Kitano, M.: Digital video recording in trauma surgery using commercially available equipment. Scandinavian journal of trauma, resuscitation and emergency medicine 21, 27–27 (Apr 2013)
  * [12] Qi, C.R., Su, H., Mo, K., Guibas, L.J.: Pointnet: Deep learning on point sets for 3d classification and segmentation. In: Conference on Computer Vision and Pattern Recognition (CVPR). pp. 652–660. IEEE (Jul 2017)
  * [13] Sadri, A., Hunt, D., Rhobaye, S., Juma, A.: Video recording of surgery to improve training in plastic surgery. Journal of Plastic, Reconstructive & Aesthetic Surgery 66(4), 122 – 123 (2013)
  * [14] Shimizu, T., Oishi, K., Hachiuma, R., Kajita, H., Takatsume, Y., Saito, H.: Surgery recording without occlusions by multi-view surgical videos. In: International Conference on Computer Vision Theory and Applications (Feb 2020)
  * [15] Xu, B., Wang, N., Chen, T., Li, M.: Empirical evaluation of rectified activations in convolutional network. CoRR abs/1505.00853 (2015), http://arxiv.org/abs/1505.00853