[1,2]B. A. Schreiber [1,3]E. J. Soilleux

[1]Department of Pathology, University of Cambridge, Tennis Court Road,
Cambridge, CB2 1QP, Cambridgeshire, United Kingdom 2]Department of Applied
Mathematics and Theoretical Physics, University of Cambridge, Wilberforce
Road, Cambridge, CB3 0WA, Cambridgeshire, United Kingdom 3]Lyzeum ltd,
Cambridge, CB1 2LA, Cambridgeshire, United Kingdom 4]Edinburgh Pathology,
Institute of Genetics & Cancer, University of Edinburgh, Crewe Road,
Edinburgh, EH4 2XR, UK 5]Artificial Intelligence and Machine Learning, GSK
plc, Great West Road, Brentford, TW8 9GS, Middlesex, UK

# Rapid Artefact Removal and H&E-Stained Tissue Segmentation

<EMAIL_ADDRESS>J. Denholm  F. Jaeckle  M. J. Arends  K. M. Branson  C.-B.
Schönlieb<EMAIL_ADDRESS>*  [  [  [  [

###### Abstract

We present an innovative method for rapidly segmenting hematoxylin and eosin
(H&E)-stained tissue in whole-slide images (WSIs) that eliminates a wide range
of undesirable artefacts such as pen marks and scanning artefacts. Our method
involves taking a single-channel representation of a low-magnification RGB
overview of the WSI in which the pixel values are bimodally distributed such
that H&E-stained tissue is easily distinguished from both background and a
wide variety of artefacts. We demonstrate our method on 30 WSIs prepared from
a wide range of institutions and WSI digital scanners, each containing
substantial artefacts, and compare it to segmentations provided by Otsu
thresholding and Histolab tissue segmentation and pen filtering tools. We
found that our method segmented the tissue and fully removed all artefacts in
29 out of 30 WSIs, whereas Otsu thresholding failed to remove any artefacts,
and the Histolab pen filtering tools only partially removed the pen marks. The
beauty of our approach lies in its simplicity: manipulating RGB colour space
and using Otsu thresholding allows for the segmentation of H&E-stained tissue
and the rapid removal of artefacts without the need for machine learning or
parameter tuning.

###### keywords:

Artefact Removal, Tissue Segmentation, Whole-Slide Imaging, Haematoxylin and
Eosin, Machine Learning

##  1 Introduction

(a)

(b)

(c)

(d)

Figure 1: (a) A WSI of a H&E-stained biopsy containing only minor, non-
interfering artefacts. (b) The tissue segmentation provided by applying Otsu
thresholding to the luminance of the WSI. The clear distinction between the
intensities of the tissue and the rest of the WSI caused the Otsu threshold to
lie between the maximum intensity of the tissue and the minimum intensity of
background, allowing for a successful tissue segmentation. (c) A WSI of an
H&E-stained biopsy containing orange pen marks splitting the tissue of
different levels and used to identify three features of interest. (d) The
tissue segmentation provided by applying Otsu thresholding to the luminance of
the WSI. The pen marks interfered with the Otsu threshold calculation,
resulting in a tissue segmentation that contains tissue and pen marks.

Otsu thresholding [1] is often applied to the luminance of whole-slide images
(WSI) of haematoxylin and eosin (H&E)-stained tissue for the purposes of
segmentation [2, 3, 4, 5, 6, 7, 8, 9, 10, 11] (see Figure 1), including in
popular histopathological analysis tools Histolab [12] and PyHist [13].
However, Otsu thresholding only successfully segments the tissue from the
background when the tissue and background pixels are well-separated in a
greyscale representation of the WSI. While this is often the case in artefact-
free WSIs, WSIs often contain artefacts such as pen marks and dark scanning
artefacts, which cause this assumption to fail, thus resulting in artefacts
wrongly identified as tissue, tissue rejected as background, or both (see
Figure 1). While there are a large and diverse range of artefacts that can
occur on a WSI, in the context of this paper artefacts will refer only to pen
marks (see Figures 3a, b, c, d, and g), bounding boxes added by the scanners
(see Figures 3e, f and g) scanning artefacts such as dark blobs or text (see
Figures 3e and f).

The exclusion of pen marks in particular is a crucial first step for any
machine learning-based automated WSI analysis pipeline; pathologists often use
pen marks to highlight areas of interest which, if observed by a machine
learning algorithm, could result in deleterious bias, spurious classifications
or even data leakage, thus reducing the confidence in the performance metrics
and the generalizability of the algorithm [14].

In this paper, we propose a new tissue segmenting algorithm for H&E-stained
tissue which can segment tissue in the presence of artefacts. We tested our
method on WSIs of H&E-stained duodenal biopsies prepared at multiple different
institutions, scanned using multiple different scanners, and containing a
large range of artefacts of different types, shapes and colours.

##  2 Method

Our method improves on Otsu thresholding by selecting a representation of the
WSI data that better separates H&E-stained tissue from background and
artefacts than luminance. Given a three channel image $I=[I_{R},I_{B},I_{G}]$,
the channels are normalized so that the channels of each pixel are represented
by floats ranging from 0 to 1. Then, the following representation of the data
is calculated:

$T=\textrm{ReLU}(I_{R}-I_{G})\odot\textrm{ReLU}(I_{B}-I_{G})$ (1)

where $\textrm{ReLU}(x)=\max(x,0)$ is the rectifier linear unit and $\odot$ is
the Hadamard product, both of which act element-wise. Otsu thresholding is
then used to separate tissue and non-tissue pixels [1]. Note that this
calculation requires no parameter training or tuning. A Python implementation
of this previously unreported algorithm can be found here
https://gitlab.developers.cam.ac.uk/bas43/h_and_e_otsu_thresholding in
accordance with the Guidelines for Authors Submitting Code and & Software
presented in Nature Research https://www.nature.com/nature-
portfolio/editorial-policies/reporting-standard#reporting-requirements. All
relevant guidelines were followed in the development and testing of this
algorithm.

Figure 2: Left: Two 24-bit colour cubes, one with the white corner at the
origin and one with the black corner at the origin. Middle: The pixels which
result in values greater than 0 in the representation specified in Equation 1
and Algorithm 1. Right: The pixels that have values greater than 0 in this
representation

RGB Image: $[I_{R},I_{G},I_{B}]$

Normalize: $I_{R},I_{G},I_{B}\leftarrow I_{R}/255,I_{G}/255,I_{B}/255$

R - G Representation: $I_{R-G}\leftarrow\textrm{ReLU}[I_{R}-I_{G}]$

B - G Representation: $I_{B-G}\leftarrow\textrm{ReLU}[I_{B}-I_{G}]$

Tissue Representation: $T\leftarrow I_{R-G}\odot I_{B-G}$

Otsu threshold: $\gamma\leftarrow\mathrm{Otsu}[T]$

if  _$T[p] >\gamma$_ then

Pixel $p$ is segmented as tissue

else

Pixel $p$ is rejected

end if

Algorithm 1 Our method for segmenting H&E stained tissue

The assumption made by Otsu thresholding is that tissue and non-tissue pixels
can be separated by their grey-scale values, which is not the case when
artefacts are present. However, our method, which is described in Equation 1
and Algorithm 1, is based on the assumption that the tissue pixels can be
identified by being both more blue than green and more red than green as
compared to non-tissue pixels. The advantage of our method is that all shades
of grey have approximately the same value in the red channel as the green
channel, so their difference is 0, while pixels of H&E-stained tissue have
higher values in the blue and red channels than the green. Setting all
negative values in both representations to zero ensures that artefacts with
high green channels compared to blue or red channels do not adversely
influence the threshold calculation, and are thus considered as background.
Thus, this representation results in a bimodal distribution that separates
pixels that are the most “purple-pink” from others, so pen marks (which are
often black, blue, green or red) are also excluded, independent of the pixel’s
light intensity. Pixels on an RGB colour cube that have a non-zero value in
this representation are shown in figure 2 and comparisons between Otsu
thresholding and our method on an RGB colour cube can be seen in the
supplementary material.

We compared the performance of our method against Otsu thresholding and
Histolab’s pen filtering tools by applying these methods to a dataset of WSIs
and assessing the resulting tissue segmentations qualitatively.

###  2.1 Data

To compare the performances of the Otsu thresholding, Histolab and our method,
we applied both methods to a selection of 60 WSIs of H&E stained duodenal
biopsies. Of the 60 WSIs selected:

  * •

15 contained pen marks

  * •

15 contained scanning artefacts

  * •

30 contained no significant artefacts

The WSIs were hand-picked so that they contained a wide range of artefacts of
different types, shapes and colours. The WSIs were scanned with a wide range
of digital scanners (Ventana, Aperio, Hamamatsu and Philips), and the 30 WSIs
with no significant artefacts were selected at random and matched for scanner
type of the 30 WSIs with pen marks or artefact.

###  2.2 Ethical Statement

All fully anonymized slide scans (and patient data) were obtained with full
ethical approval from the Oxfordshire Research Ethics Committee A (IRAS:
162057; PI: Prof. E. Soilleux), and the method was performed in accordance
with their guidelines and regulations. Informed consent was obtained from all
subjects and/or their legal guardian(s).

##  3 Results

Figure 3: Seven WSIs of H&E-stained biopsies containing artefacts of a wide
range of types and colours. The aim was to segment the tissue without
including background and artefacts. First Column: The original WSI. Second
Column: The tissue segmentation provided by applying Otsu thresholding to the
luminance of the WSIs placed on a white background. Otsu thresholding failed
to reject a single artefact and failed to segment the tissue in (e). Third
Column: The tissue segmentation from Histolab tissue thresholding and pen
filters. While there was partial pen mark removal in (a), (b), (c) and (d),
the pen marks were not fully removed in any image, no tissue was segmented in
(e), no pen marks were removed in (g). Forth Column: The tissue segmentation
from our method placed on a white background. Our method successfully
segmented all tissue and rejected all background and artefacts except the pen
marks in (g). Our method failed to reject the pen marks in (g) because the pen
is the same colour as the eosin.

Otsu thresholding, Histolab and our method were used to segment the tissue
from the 60 WSIs described above. Examples of the WSIs selected and the tissue
segmentation of these methods can be viewed in Figure 3. Examples of the
tissue segmentation masks provided by Otsu thresholding and our method, and
the Sørensen–Dice coefficient’s between the segmentations and a manually
segmented tissue mask are displayed in the supplementary material. The tissue
segmentations were assessed by a single observer, and considered “successful”
if all the following were true:

  * •

All tissue was segmented

  * •

All background was rejected from the segmentation

  * •

All bounding boxes were rejected from the segmentation

  * •

All artefacts were rejected from the segmentation

Otsu thresholding rejected pen and scanning artefacts from the tissue
segmentation in 0/30 WSIs containing artefacts. In 2/30 WSIs containing
artefacts, the influence the artefacts had on the threshold was so great that
the tissue was not segmented as tissue (see Figure 3e).

The Histolab pen filtering tool only partially removed pen marks in Figures
3a-d, and removed no pen marks in Figure 3g. Other artefacts such as scanning
artefacts were not effected by the Histolab tools.

Our method segmented the tissue in all 60/60 WSIs and rejected all artefacts
in 29/30 WSIs containing pen and scanning artefacts. The only WSI where pen
marks were included in the tissue segmentation can be seen in Figure 3g. Here
our method failed to reject the pen marks because tissue and non-tissue pixels
could not be separated through their “pinkness”, when the pen marks were also
pink.

##  4 Discussion

While Otsu thresholding segmented the tissue in all artefact-free WSIs and
most WSIs with artefacts, it identified all artefacts as tissue as well. In 2
out of 30 WSIs with artefacts, the presence of artefacts caused the threshold
to ignore tissue and include background in the tissue segmentation as seen in
Figure 3e.

The Histolab pen filtering tools were applied to the tissue segmentations in
order to remove the remaining pen marks. The filtering tools performed best on
blue pen marks, as seen in Figures 3a and d. However, the tools did not remove
the edges of pen marks of all colours, and dailed to detect the majority of
all green and orange pen marks, as seen in Figures 3b and c respectively. The
pink pen marks presented in Figure 3g remained untouched. Additionally, the
Histolab tools were not designed to remove scanning artefacts and bounding
boxes so these features remained.

Our method, on the other hand, segmented the tissue in all WSIs and rejected
artefacts in all WSIs containing artefacts but one. The only exception can be
seen in Figure 3g, which contained pink pen marks that caused all methods to
fail.

The thresholding algorithm presented here is a rapid, reliable and easily
implementable tissue segmentation and artefact removal tool for WSIs of
H&E-stained tissue. In machine learning tasks especially, this tool can be
used as a preprocessing step that ensures artefacts do not cause the machine
learning algorithm to train on irrelevant patches or patches that contain data
leaking pen marks.

It should be noted that this method is built to segment H&E-stained tissue
only, and will not perform as intended on tissue which has been stained with
stains that do not appear pink/purple. However, this method should be
relatively simple to generalize to other stains by using representations of
the WSI data that uniquely differentiate the stained tissue from background
and artefacts, and will be studied in future research.

## Funding

This work was supported by the Pathological Society [PKAG/924] and
GlaxoSmithKline [LEAG/781]

## Author Contributions

B. A. Schreiber devised the thresholding algorithm and wrote the manuscript.
J. Denholm and F. Jaeckle independently tested and compared Otsu thresholding,
Histolab, and the thresholding algorithm presented here. Histological
expertise was provided by M. J. Arends and E. J. Soilleux. The project was
initialized by E. J. Soilleux and supervised by K. M. Branson, C.-B. Schönlieb
and E. J. Soilleux. All authors were given the opportunity to review and
comment on the manuscript.

## Data Availability

The datasets of WSIs analysed during this current study have not publicly
available due to the large size of the WSIs and legal considerations. However,
low-level representations of the WSIs used in the study have been made
available at
https://gitlab.developers.cam.ac.uk/bas43/h_and_e_otsu_thresholding.

## References

  * Otsu [1979] N. Otsu,  A Threshold Selection Method from Gray-Level Histograms,  IEEE Transactions on Systems, Man, and Cybernetics 9 (1979) 62–66. doi:10.1109/TSMC.1979.4310076.
  * Wang et al. [2020] X. Wang, H. Chen, C. Gan, H. Lin, Q. Dou, E. Tsougenis, Q. Huang, M. Cai, P.-A. Heng,  Weakly Supervised Deep Learning for Whole Slide Lung Cancer Image Analysis,  IEEE Transactions on Cybernetics 50 (2020) 3950–3962. doi:10.1109/TCYB.2019.2935141.
  * Denholm et al. [2022] J. Denholm, B. A. Schreiber, S. C. Evans, O. M. Crook, A. Sharma, J. L. Watson, H. Bancroft, G. Langman, J. D. Gilbey, C. B. Schönlieb, M. J. Arends, E. J. Soilleux,  Multiple-instance-learning-based detection of coeliac disease in histological whole-slide images,  Journal of Pathology Informatics 13 (2022) 100151. doi:10.1016/j.jpi.2022.100151.
  * Campanella et al. [2019] G. Campanella, M. G. Hanna, L. Geneslaw, A. Miraflor, V. Werneck Krauss Silva, K. J. Busam, E. Brogi, V. E. Reuter, D. S. Klimstra, T. J. Fuchs,  Clinical-grade computational pathology using weakly supervised deep learning on whole slide images,  Nature Medicine 25 (2019) 1301–1309. doi:10.1038/s41591-019-0508-1.
  * Khened et al. [2021] M. Khened, A. Kori, H. Rajkumar, G. Krishnamurthi, B. Srinivasan,  A generalized deep learning framework for whole-slide image segmentation and analysis,  Scientific Reports 11 (2021) 11579. URL: https://www.nature.com/articles/s41598-021-90444-8. doi:10.1038/s41598-021-90444-8, number: 1 Publisher: Nature Publishing Group.
  * Anghel et al. [2019] A. Anghel, M. Stanisavljevic, S. Andani, N. Papandreou, J. H. Rüschoff, P. Wild, M. Gabrani, H. Pozidis,  A High-Performance System for Robust Stain Normalization of Whole-Slide Images in Histopathology,  Frontiers in Medicine 6 (2019) 193. doi:10.3389/fmed.2019.00193.
  * Haghighat et al. [2022] M. Haghighat, L. Browning, K. Sirinukunwattana, S. Malacrino, N. Khalid Alham, R. Colling, Y. Cui, E. Rakha, F. C. Hamdy, C. Verrill, J. Rittscher,  Automated quality assessment of large digitised histology cohorts by artificial intelligence,  Scientific Reports 12 (2022) 5002. URL: https://www.nature.com/articles/s41598-022-08351-5. doi:10.1038/s41598-022-08351-5, number: 1 Publisher: Nature Publishing Group.
  * Smith et al. [2021] B. Smith, M. Hermsen, E. Lesser, D. Ravichandar, W. Kremers,  Developing image analysis pipelines of whole-slide images: Pre- and post-processing,  Journal of Clinical and Translational Science 5 (2021) e38. doi:10.1017/cts.2020.531, publisher: Cambridge University Press.
  * Veta et al. [2019] M. Veta, Y. J. Heng, N. Stathonikos, B. E. Bejnordi, F. Beca, T. Wollmann, K. Rohr, M. A. Shah, D. Wang, M. Rousson, M. Hedlund, D. Tellez, F. Ciompi, E. Zerhouni, D. Lanyi, M. Viana, V. Kovalev, V. Liauchuk, H. A. Phoulady, T. Qaiser, S. Graham, N. Rajpoot, E. Sjöblom, J. Molin, K. Paeng, S. Hwang, S. Park, Z. Jia, E. I.-C. Chang, Y. Xu, A. H. Beck, P. J. van Diest, J. P. W. Pluim,  Predicting breast tumor proliferation from whole-slide images: The TUPAC16 challenge,  Medical Image Analysis 54 (2019) 111–121. doi:10.1016/j.media.2019.02.012.
  * Schmauch et al. [2019] B. Schmauch, A. Romagnoni, E. Pronier, C. Saillard, P. Maillé, J. Calderaro, M. Sefta, S. Toldo, M. Zaslavskiy, T. Clozel, M. Moarii, P. Courtiol, G. Wainrib,  Transcriptomic learning for digital pathology,  bioRxiv (2019) 760173\. doi:10.1101/760173.
  * Zhang et al. [2022] H. Zhang, Y. Meng, Y. Zhao, Y. Qiao, X. Yang, S. E. Coupland, Y. Zheng,  DTFD-MIL: Double-tier feature distillation multiple instance learning for histopathology whole slide image classification,  in: 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022, pp. 18780–18790. doi:10.1109/CVPR52688.2022.01824, ISSN: 2575-7075.
  * Marcolini et al. [2022] A. Marcolini, N. Bussola, E. Arbitrio, M. Amgad, G. Jurman, C. Furlanello,  histolab: A python library for reproducible digital pathology preprocessing with automated testing,  SoftwareX 20 (2022) 101237. URL: https://www.sciencedirect.com/science/article/pii/S2352711022001558. doi:10.1016/j.softx.2022.101237.
  * Muñoz-Aguirre et al. [2020] M. Muñoz-Aguirre, V. F. Ntasis, S. Rojas, R. Guigó,  PyHIST: A histological image segmentation tool,  PLOS Computational Biology 16 (2020) e1008349. URL: https://doi.org/10.1371/journal.pcbi.1008349. doi:10.1371/journal.pcbi.1008349.
  * Kaufman et al. [2023] S. Kaufman, S. Rosset, C. Perlich, O. Stitelman,  Leakage in data mining: Formulation, detection, and avoidance,  ACM Transactions on Knowledge Discovery from Data 6 (2023) 15:1–15:21. URL: https://dl.acm.org/doi/10.1145/2382577.2382579. doi:10.1145/2382577.2382579.


# Recording and Interpreting Developer Behaviour in Programming Tasks

1st Martin Schröer  University of BremenDepartment of Computer
ScienceBremenGermany<EMAIL_ADDRESS>and  2nd Rainer Koschke
University of BremenDepartment of Computer ScienceBremenGermany koschke@uni-
bremen.de

(2024)

###### Abstract.

To evaluate how developers perform differently in solving programming tasks,
i.e., which actions and behaviours are more beneficial to them than others and
if there are any specific strategies and behaviours that may indicate good
versus poor understanding of the task and program given to them, we used the
MIMESIS plug-in [22] to record developers’ interactions with the IDE. In a
series of three studies we investigated the specific behaviour of developers
solving a specific programming task. We focused on which source code files
they visited, how they related pieces of code and knowledge to others and when
and how successfully they performed code edits. To cope with the variety of
behaviours due to interpersonal differences such as different level of
knowledge, development style or problem solving stratiegies, we used an
abstraction of the observed behaviour, which enables for a better comparison
between different individual attributes such as skill, speed and used
stratiegies and also facilitates later automatic evaluation of behaviours,
i.e. by using a software to react to.

program comprehension, software maintenance, human factors, developer
interactions, visualisation

††journalyear: 2024††copyright: acmlicensed††conference: 2024 First IDE
Workshop; April 20, 2024; Lisbon, Portugal††booktitle: 2024 First IDE Workshop
(IDE ’24), April 20, 2024, Lisbon, Portugal††doi:
10.1145/3643796.3648450††isbn: 979-8-4007-0580-9/24/04††conference: 46th
International Conference on Software Engineering; April 2024; Lisbon,
Portugal††ccs: Software and its engineering Software maintenance tools††ccs:
Software and its engineering Maintaining software††ccs: Software and its
engineering Software evolution

##  1\. Introduction

There have been several approaches to describe how developers perform program
comprehension, i.e., how they tackle the issue to understand an existing
program which they have to perform a task with, e.g., fixing a bug or
introducing a new functionality. Early works started with models describing
how knowledge about a program is supposedly acquired and organised within the
developers’ mind [23, 2, 16, 25, 26, 27]. Later research attempts were devoted
to describe the particular strategy developers may apply in programming tasks
in general [24] and more specific [7, 5]. Recent works focus more specifically
on individual aspects of program comprehension, such as the particular
knowledge developers need [8, 12, 21] and the pecularities of different
working tasks [7, 20] as well as the influence of experience on the different
comprehension strategies [9]. With the introduction of the Information
Foraging Theory [19] to the understanding of how a search for knowledge for
program comprehension is conducted in particular [10], new approaches to
observe and understand the specific working steps involved have emerged [11].
Recent works building on these approaches revealed that the models and
assumptions seem to be incomplete, as working patterns could not be observed
[18] as predicted by corresponding literature. These findings motivated us to
conduct our studies. In this article, we will discuss findings from
interaction data recorded from developers performing programming tasks and
furthermore we will also outline the usage of specific action patterns of
recorded developer behaviour to evaluate the developers performance in
comprehension and task solving.

##  2\. Related Work

Röhm et al. [20] observed the development activities of professional
developers to investigate how developers comprehend software. They found that
most of the developers they observed employed a recurring comprehension
strategy based on the context of a task, whereby the particular strategy
chosen by an individual developer differed among them, e.g., some developers
started with reading the code, while others preferred starting with inspecting
the documentation or requirements. In contrast to our study, they observed
their participants using a think-aloud method [4] and conducted interviews.

Grigoreanu et al. [5] investigated the strategies and specific sensemaking
steps which participants showed in their study while performing a debugging
task. They gathered data from think-aloud protocols [4] recorded from their
participants and used a visualisation representing the participants’
sensemaking steps. Their findings were that in debugging there are multiple
sensemaking loops on different levels of the comprehension process, each
utilizing specific sensemaking sequences. This was later challenged by the
findings of Piorkowski et al. [18], who neither could observe presence of
those sensemaking sequences or their assumed distribution in the comprehension
process, nor found support for the assumption of a hierachical sensemaking
loop. In their work, they revealed non-linear action patterns such as
”Oscillate”, i.e., developers moving forth and back between two adjacent
comprehension states and ”Restart”, i.e., developers advancing to the highest
state of comprehension, then returning to the lowest state and starting over.
In contrast to our work, they focused on actions of end-users debugging
Microsoft Excel spreadsheets based on think-aloud protocols and visualised
assumed sensemaking steps, while we recorded and visualised interactions of
developers with the IDE while performing programming tasks on a program’s
source code.

Lawrance et al. [11] investigated how professional developers are fixing bugs,
with focus on the aspect how information needed to solve the task is sought
for, inspired by ideas from the Information Foraging Theory (IFT) [19],
suggesting that humans searching for information are using similar methods as
a predator foraging for prey, e.g., following ”information scents”. They found
that their participants uttered far more scent-related questions than such
relating to a hypothesis about the program they tried to understand. Their
work contrasts to ours in that they used a video recording of their
participants who were instructed to ”think aloud” [4] about what they are
doing and they limited their research specifically to debugging activities.
Also, the effectiveness of cue- or ”information scent”-based strategies to
program comprehension was investigated by Piorkowski et al. [17], who found in
a corresponding study, that while developers often followed scents, their
prediction about the profit and cost of such pursuits was usually rather bad:
50 percent of the developers’ navigations were leading to less valuable
information (if any) than they had expected, while the cost of such
information pursuit exceeded their anticipation by nearly 40 percent on
average. In a different study, Piorkowski et al. [18] used video recordings to
transcribe the development steps expressed by the recorded developers in the
form of ”think aloud protocols” [4]. They then used the debugging strategy
code set by Grigoreanu et al. [5] to code the utterances of the developers
they observed according to the taxonomy of questions that Sillito et al. [24]
defined, revealing that not only the sequence, but also the distribution of
comprehension strategies displayed did not, or did only partially match the
corresponding predictions, such as progressing from an initial focus point to
finally understanding groups of groups [24], nor was displaying the
corresponding goal patterns [5]. The developers displayed ”repeating” or
”oscillating” goal patterns, rather than following a linear or hierarchical
sequence that was predicted by literature. In contrast to their study, we use
more fine-grained interaction recordings and a graphical visualisation of
developer interactions, where their work used a numerical representation of
comprehension steps assumed from their participants’ recorded utterances.

##  3\. Study

We used the Mimesis tool [22] to record developers’ interactions with the IDE.
Mimesis captures various interactions, among others it captures interactions
such as navigations, e.g., opening and switching between files, code events
such as selection, code changes or searching for keywords and debugger usgage,
such as setting breakpoints, starting the debugger and hitting a set
breakpoint. Mimesis allows to run an Eclipse session from within a web
browser, not requiring any additional download on the client side. It also
offers the functionality to display instructions and a survey to participants
before they start working with the IDE. In our studies, we used the source
code of JabRef111https://www.jabref.orgJabRef, a well known scientific
literature reference manager, thus providing an authentic code base to have
participants work with.

###  3.1. Study Design

For the conduction of the studies we chose scenarios in which developers had
to perform a rather small, yet not trivial edit, thus allowing us to collect
interaction data which was then investigated for the presence of observations
reported by related works [24, 5, 20, 18, 13, 14]. Specifically, we wanted to
examine the recordings for the presence of rather linear or hierarchical
working patterns indicating the comprehension steps as suggested by the model
of Sillito et al. [24], the application of comprehension strategies as
described by Grigoreanu et al. [5], and the specific action patterns that were
observed by Piorkowski et al. [18].

Three independent studies were conducted: A) Participants were asked to add a
missing ”Save” button next to the ”New Library” and ”Open Library” buttons
that can be found below the upper menubar’s ”File” option. B) We introduced a
bug, which led to clicking on the ”Copy Version” button in the ”About” dialog
of JabRef not working as expected. The task was to fix this bug. C) This study
was based on the task given in B), but additionally, participants were
presented with a history of their previous navigations through the code and
suggested bookmarks for possibly interesting code locations. Participants of
any of the studies descibed above were presented with a survey asking for
demographic information such as age and occupation and their personal
knowledge about programming before starting to work on the task itself.

Previous studies have suggested that developers tend to neglect certain task-
relevant information given to them [6, 20, 3, 1, 15]. To investigate what kind
of information provided is actually used by the developers we used a
particular file structure that was providing useful information together with
the program’s source code such as the task’s instruction and additional
information in text files separate from the source code itself. The recordings
would allow us to see whether and when these files were accessed. We
distributed this information to seperate files to observe the information
utilisation behaviour of the developers, i.e., if and when they access the
information provided and what are the preceeding and subsequent actions that
they perform.

Furthermore, subjects were informed at the beginning of the trial that they
were allowed to arbitrarily decide when they have completed the task. That is,
if they assumed they had performed all necessary code changes, they were free
to independently finish their participation. Beyond this, there was also no
time limit given, neither were participants instructed to use a particular
approach to solve the task. They were suggested to perform in whatever way
they felt the most comfortable to do so.

This was done to allow the observation of the most natural, yet individual
development task solving behaviour possible and led to the participants
showing a high variety in how they performed the task, which we will discuss
in detail in the next section.

##  4\. Results

Out of over 300 participation attempts, N=51 recordings were selected for
further investigation, due to the participation being successfully finished
($n_{s}$ = 32), or unsuccsessful ($n_{u}$ = 19), but of appropriate length and
showing a reasonable attempt to solve the given task, i.e., browsing the
source code and searching for an entry point as opposed to giving up after
reading the instructions.

Overall, participants showed a broad variety in how they tried to solve the
task. The time spent on solving the task ranged from under 10 minutes to up to
almost 2 hours. Beyond that, participants also showed different approaches to
gain insight into the source code. Only a part of them used the debugging
functionality ($n_{d}=14$), whereas others used strategies such as ”poor man’s
debugger”, i.e., adding custom text output to certain places within the
program, while others seemed to use none of those strategies at all and just
read the source code.

###  4.1. Understanding Developer Behaviour

When we used Mimesis visualisation of the recordings, we came to notice that
in spite of the broad variety between participants, there overall seem to be
distinct ”phases” in participtions that could be described as follows: 1)
”Investigation”–in this phase rather much navigation behaviour happens, i.e.,
file browsing and scrolling activity. Only few code interactions happen, if
any. 2) ”Edit”–developers in this phase spend longer times navigating in
certain code ”blocks” and performing code edits, also sometimes use program
launches or debugging, before advancing to another code block. 3) ”Validation
Phase”–again more broadly navigation behaviour occurs in this phase.
Developers appear to have completed all essential code edits, they seem to be
again scanning the code (similar to the investigation phase), probably to
check whether they have considered every code line important to the task. This
phase usually ends with some program launches to check the program’s runtime
behaviour. From this overall observation, at first there seem to be some
accordance to the assumptions of linear or hierarchical comprehension models
and strategies [24, 5]: Developers initially seem to locate an appropriate
starting point, then read the surrounding code to expand their knowledge,
perform code edits and validate their edits at last. But when furthermore
examined in detail, it seems that developers probably rather use a kind of
recursive approach. They may identify a suitable focus point to start from and
then, by investigating the relations of this focus point with the program
expand their knowledge, so far in according to corresponding assumptions. But
in contrast to the assumptions, developers do not seem to necessarily just
advance further in the model, but rather tend to restart, i.e., using the
partial knowledge gained by selecting and expanding a focus point to find a
better point to start over.

Recordings overall revealed distinct action patterns, that were similar to the
action sequences that Piorkowski et al. [18] observed. We were able to observe
developers scrolling forth and back through the code, sometimes repeatedly,
while occasionally switching between the source code file and the provided
documentation. This may indicate an action pattern similar to what Piorkowski
et al. [18] found to be an ”Oscillate” pattern, as scrolling forth and back
may be considered to be comprehending control or data flow (detailed
understanding strategy), while advancing through the code may be considered to
be a code inspection (coarse overall understanding strategy). The behaviour of
developers reading the source code file, performing some edits, then switching
back to the instruction file before returning to the code file to advance
reading and editing may be compared to the ”Restart” pattern.

Regarding the use of provided additional information, all participants made
use of the provided files to some extent. Interestingly, this also seems to
correlate with the working phase they were currently in, as all subjects
accessed and read the files containing the instructions, notes and temperature
conversion information at the beginning of the task and most of them revisited
the instruction file before completing working on the task, most likely to
check for completeness. But also a majority revisited the instruction and note
files after spending time in the ”Inspection” phase and just before entering
the ”Edit” phase, this behaviour may also indicate the switch between
comprehension stages, i.e., after gathering enough information about the
program to be confident enough to begin editing it, they were checking again
what specifically they were expected to do.

Figure 1. Examples for participations

The graph shows the assumed comprehension and task solving performance. The
surrounding area is the amount of distinct files visited. An ideal performance
would have the graph match or even exceed the upper bound of this area, while
overall being concise, i.e., showing only few action-pattern repetitions.
Horizontal lines depict edits, symbols on the graph represent matched action
patterns, e.g., using the debugger.
In the upper visualisation, the subject at first used an alternative solution
to the task, before realizing and revising for the actual solution.
The lower visualisation displays a participation with lower overall
comprehension, using ”poor man’s debugging” and a lot of additional unneeded
changes due to uncertainty.

###  4.2. Comprehension and Task solving metric

In an approach to evaluate developers’ behaviour while also coping with the
broad variety of different problem solving strategies and specific behaviours
displayed by our participants, we developed a behaviour coding system. Based
on the developer behaviours and action patterns that could be observed in the
recordings from our aforementioned studies, we defined distinct presumed
comprehension and task solving states which are transitioned by certain
developer behaviours and action patterns. As the navigation behaviour seems to
correlate with comprehension and progress in task solving, e.g., developers
comparing new to recently vistited source files seem to display a better
comprehension (”between-patch strategies” [18]) than developers constantly
opening new files without comparing them to each other, or constantly
resorting to the task’s intructions, we introduced a metric to express this
kind of navigation behaviour: Cyclissity.

$Cyclissity=1-P_{c}/N$, where $P_{c}$ is the position of the current file in
the file history and $N$ is the number of files visited in total.

If a developer compares two recently visited files, the resulting cyclissity
would be high, whereas visiting a file, while other files have been visited in
between would lead to a lower cyclissity value. Visiting new files per
definition results in a cyclissity of zero. Together with corresponding action
patterns, this enables for a better understanding and evaluation of developer
behaviour.

When a developer is working on a programming task, the behaviour and specific
action patterns displayed togehter with the cyclissity computed for the
corresponding file navigations lead to transitions between the aforementioned
comprehension and task solving states which are rated for increased, decreased
or not changed assumed comprehension and task solving performance.

This also allows for generalization and enables for an otherwise difficult
comparison between developers, due to different working speeds, invidiual
problem solving strategies and expertise.

When applied to the recordings of our studies, this coding scheme shows
promising results in terms of describing participants’ task solving
performance (cf. Figure 1).

It has to be pointed out, that while a low rating can be regarded indicating
poor performance, reaching a high rating is not suffcient as a suitable
indicator for good performance alone: While a participant repeatedly using
action-patterns that are assumed to be beneficial for comprehension and task-
solving will be awarded with a high overall rating, this may also indicate the
participant performing the right steps, but still struggling to recognise the
correct code change. For this reason, it is important to also keep track of
action-pattern frequency and repetitions, especially.

While in the successful recordings from our study, there were a number of high
scoring participants, which solved the given task using only few steps and
within short time, there also were a number of participants which, probably
due to less expertise or knowledge, showed longer time and much more steps
needed, yet still also solved the task as well. The latter would have most
likely benefitted from some kind of (tool) assistance when–by observable
repetition of certain action-patterns–showed the indication of them struggling
with the task.

##  5\. Conclusion

In analysing IDE interactions recorded from N=51 participations of developers
performing programming tasks, we showed that in contrast to the developers
showing a wide variety in speed, knowledge and individual problem solving
strategies there seem to be general behaviours and specific action patterns
that can also be utilised to presume a developers’ current quality of
comprehension and task-solving.

The specific working patterns observed in our recordings also show some
interesting deviations from what those works suggested, especially in the
assumption of a rather linear comprehension progress. They rather fit to the
observations of Röhm et al. [20], Piorkowski et al. [18], Minelli et al. [13],
in that developers seem to recursively switch forth and back between different
stages of comprehension, making the general assumption of a linear or
hierachic progression seem to be too strict. Instead, developers seem to use
some kind of refining approach, resembling to what Sadowski et al. [21]
observed for general search behaviour in programming tasks: developers seem to
start comprehending programs with a generic assumption or question at an
almost arbitrary location within the program’s source code, gathering more
information while progressing further through the lines of source code,
allowing them to refine their assumptions about the program, this leading to
them restarting their inspection of potentially important lines, similar to
what could be observed by the ”oscillating” (scrolling back and forth)
navigation behaviour in our study.

##  6\. Outlook

We are currently conducting another study to validate our findings, in which
participants are asked to rate their task solving performance action-pattern
triggered times.

## Acknowledgements

We like to thank all study subjects for their participation. This work was
supported by the Deutsche Forschungsgemeinschaft (DFG, grant KO 2324/3-3).

## References

  * Bazrafshan and Koschke [2014] Saman Bazrafshan and Rainer Koschke.  Effect of clone information on the performance of developers fixing cloned bugs.  In _SCAM_ , pages 1–10. IEEEPress, 2014.
  * Brooks [1983] Ruven Brooks.  Towards a theory of the comprehension of computer programs.  _International journal of man-machine studies_ , 18(6):543–554, 1983.
  * Edmundson et al. [2013] Anne Edmundson, Brian Holtkamp, Emanuel Rivera, Matthew Finifter, Adrian Mettler, and David Wagner.  An empirical study on the effectiveness of security code review.  In _International Symposium on Engineering Secure Software and Systems_ , pages 197–212. Springer, 2013.
  * Ericsson and Simon [1993] Karl Anders Ericsson and Herbert Alexander Simon.  _Protocol analysis_.  MIT press Cambridge, MA, 1993.
  * Grigoreanu et al. [2012] Valentina Grigoreanu, Margaret Burnett, Susan Wiedenbeck, Jill Cao, Kyle Rector, and Irwin Kwan.  End-user debugging strategies: A sensemaking perspective.  _ACM Trans. Comput.-Hum. Interact._ , 19(1):5:1–5:28, May 2012.  ISSN 1073-0516.  doi: 10.1145/2147783.2147788.  URL http://doi.acm.org/10.1145/2147783.2147788.
  * Guzzi et al. [2011] Anja Guzzi, Lile Hattori, Michele Lanza, Martin Pinzger, and Arie van Deursen.  Collective code bookmarks for program comprehension.  In _Proceedings of the 2011 IEEE 19th International Conference on Program Comprehension_ , ICPC ’11, pages 101–110, Washington, DC, USA, 2011\. IEEE Computer Society.  ISBN 978-0-7695-4398-7.  doi: 10.1109/ICPC.2011.19.  URL http://dx.doi.org/10.1109/ICPC.2011.19.
  * Ko et al. [2006] Andrew J Ko, Brad A Myers, Michael J Coblenz, and Htet Htet Aung.  An exploratory study of how developers seek, relate, and collect relevant information during software maintenance tasks.  _IEEE Transactions on software engineering_ , 32(12), 2006\.
  * Ko et al. [2007] Andrew J Ko, Robert DeLine, and Gina Venolia.  Information needs in collocated software development teams.  In _Software Engineering, 2007. ICSE 2007. 29th International Conference on_ , pages 344–353. IEEE, 2007.
  * Ko and Uttl [2003] Andrew Jensen Ko and Bob Uttl.  Individual differences in program comprehension strategies in unfamiliar programming systems.  In _Program Comprehension, 2003. 11th IEEE International Workshop on_ , pages 175–184. IEEE, 2003.
  * Lawrance et al. [2008] Joseph Lawrance, Rachel Bellamy, Margaret Burnett, and Kyle Rector.  Using information scent to model the dynamic foraging behavior of programmers in maintenance tasks.  In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , pages 1323–1332. ACM, 2008.
  * Lawrance et al. [2013] Joseph Lawrance, Christopher Bogart, Margaret Burnett, Rachel Bellamy, Kyle Rector, and Scott D Fleming.  How programmers debug, revisited: An information foraging theory perspective.  _IEEE Transactions on Software Engineering_ , 39(2):197–215, 2013.
  * Maalej et al. [2014] Walid Maalej, Rebecca Tiarks, Tobias Roehm, and Rainer Koschke.  On the comprehension of program comprehension.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , 23(4):31, 2014.
  * Minelli et al. [2014] Roberto Minelli, Andrea Mocci, Michele Lanza, and Lorenzo Baracchi.  Visualizing developer interactions.  In _2014 Second IEEE Working Conference on Software Visualization_ , pages 147–156. IEEE, 2014.
  * Minelli et al. [2015] Roberto Minelli, Andrea Mocci, and Michele Lanza.  I know what you did last summer-an investigation of how developers spend their time.  In _2015 IEEE 23rd International Conference on Program Comprehension_ , pages 25–35. IEEE, 2015.
  * Oliveira et al. [2014] Daniela Oliveira, Marissa Rosenthal, Nicole Morin, Kuo-Chuan Yeh, Justin Cappos, and Yanyan Zhuang.  It’s the psychology stupid: how heuristics explain software vulnerabilities and how priming can illuminate developer’s blind spots.  In _Proceedings of the 30th Annual Computer Security Applications Conference_ , pages 296–305. ACM, 2014.
  * Pennington [1987] Nancy Pennington.  Comprehension strategies in programming.  In _Empirical studies of programmers: second workshop_ , pages 100–113. Ablex Publishing Corp., 1987.
  * Piorkowski et al. [2016] David Piorkowski, Austin Z Henley, Tahmid Nabi, Scott D Fleming, Christopher Scaffidi, and Margaret Burnett.  Foraging and navigations, fundamentally: developers’ predictions of value and cost.  In _Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering_ , pages 97–108. ACM, 2016.
  * Piorkowski et al. [2013] David J Piorkowski, Scott D Fleming, Irwin Kwan, Margaret M Burnett, Christopher Scaffidi, Rachel KE Bellamy, and Joshua Jordahl.  The whats and hows of programmers’ foraging diets.  In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , pages 3063–3072. ACM, 2013.
  * Pirolli and Card [1999] Peter Pirolli and Stuart Card.  Information foraging.  _Psychological review_ , 106(4):643, 1999.
  * Röhm et al. [2012] Tobias Röhm, Rebecca Tiarks, Walid Maalej, and Rainer Koschke.  How do professional developers comprehend software.  In _International Conference on Software Engineering._ , pages 81–90. ACM, 2012.
  * Sadowski et al. [2015] Caitlin Sadowski, Kathryn T Stolee, and Sebastian Elbaum.  How developers search for code: a case study.  In _Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering_ , pages 191–201. ACM, 2015.
  * Schröer and Koschke [2021] Martin Schröer and Rainer Koschke.  Recording, visualising and understanding developer programming behaviour.  In _2021 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)_ , pages 561–566. IEEE, 2021.
  * Shneiderman and Mayer [1979] Ben Shneiderman and Richard Mayer.  Syntactic/semantic interactions in programmer behavior: A model and experimental results.  _International Journal of Parallel Programming_ , 8(3):219–238, 1979.
  * Sillito et al. [2008] Jonathan Sillito, Gail Murphy, and Kris De Volder.  Asking and answering questions during a programming change task.  _IEEE Transactions on Software Engineering_ , 34(4):434–451, 2008.
  * Soloway et al. [1988] Elliot Soloway, Beth Adelson, and Kate Ehrlich.  Knowledge and processes in the comprehension of computer programs.  _The nature of expertise_ , pages 129–152, 1988.
  * von Mayrhauser and Vans [1995a] Anneliese von Mayrhauser and A Marie Vans.  Industrial experience with an integrated code comprehension model.  _Software Engineering Journal_ , 10(5):171–182, 1995a.
  * von Mayrhauser and Vans [1995b] Anneliese von Mayrhauser and A Marie Vans.  Program comprehension during software maintenance and evolution.  _Computer_ , 28(8):44–55, 1995b.


# Space-Time Graph Neural Networks with Stochastic Graph Perturbations

###### Abstract

Space-time graph neural networks (ST-GNNs) are recently developed
architectures that learn efficient graph representations of time-varying data.
ST-GNNs are particularly useful in multi-agent systems, due to their stability
properties and their ability to respect communication delays between the
agents. In this paper we revisit the stability properties of ST-GNNs and prove
that they are stable to stochastic graph perturbations. Our analysis suggests
that ST-GNNs are suitable for transfer learning on time-varying graphs and
enables the design of generalized convolutional architectures that jointly
process time-varying graphs and time-varying signals. Numerical experiments on
decentralized control systems validate our theoretical results and showcase
the benefits of traditional and generalized ST-GNN architectures.

Index Terms—  ST-GNNs, GNNs, stability anaysis, graph perturbations, transfer
learning

##  1 Introduction

Stability analysis of graph neural networks (GNNs) was studied extensively in
literature [1, 2, 3, 4, 5] and affirms that small changes in input graphs
translate into small, bounded changes in the outputs. It also provides a
characterization of the design parameters, e.g., the depth and width of GNNs,
that preserve stability. The acquired gain, when stability holds, is the
ability to transfer learned GNNs between different graphs of the same size
without re-training the models. Stability is a notion that is different from
GNN transferability, which considers transfer learning to graphs of larger
sizes [6, 7, 8]. Together, they allow executing GNNs on underlying graphs that
are different from those used in training and determine which architectures
are more robust to graph changes.

GNNs are aligned with applications in distributed controllers [9, 10, 11] and
wireless systems [12, 13, 14]. Both tasks are challenging, since the
underlying graph varies rapidly over time and the signals endure delays while
being propagated between agents. To deal with signal delays, we leveraged
diffusion equations to introduce space-time graph neural networks (ST-GNNs) in
[15]. Specifically, we formulated a diffusion equation over a space-time
domain that respects propagation time between nodes. This allowed the proposed
space-time convolutions to aggregate each node’s present data along with
outdated information from its neighbors. During training ST-GNNs learn to
weigh the outdated information and offset their negative impact on the model’s
predictions. Our analysis also proved that the new architecture is stable to
graph and time perturbations. However, the challenge of facing dynamic graphs
during training is still to be addressed.

The first work to approach this challenge is [16] that studied dynamic graphs
modelled as stochastic processes and showed that GNNs are stable to stochastic
graph perturbations. However, their analysis focuses on signals that are fixed
over time, which is impractical in certain applications. In this paper, we
bridge this gap and study both signals and graphs that vary over time. We
extend our previous work in ST-GNNs to accommodate time-varying graphs and
prove their stability to stochastic graph perturbations. Our contributions can
be summarized as follows:

  1. (C1)

We prove the stability of STGFs and ST-GNNs to stochastic graph perturbations.
Our result implies that ST-GNNs can handle transfer learning to time-varying
graphs.

  2. (C2)

Motivated by our stability analysis, we introduce generalized STGFs and
generalized ST-GNNs that are tailored to jointly process time-varying graphs
and time-varying signals and study their spectral properties.

  3. (C3)

We conduct experimental examination of ST-GNNs and generalized ST-GNNs
distributed controller settings.

Due to the limited space, all the proofs are relegated to an extended version
of the paper.

##  2 Space-Time Graph Neural Networks

Consider an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with a
set of $N$ nodes $\mathcal{V}$ and a set of edges
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$. We define discrete-time
signals ${\bf x}_{i}(t)$ at each node $i$, which can be concatenated to a
space-time graph signal ${\bf X}\in\mathbb{R}^{N\times T}$. Then $\bf S\bf X$
and $\bf X\bf C$ define the 1-hop diffusion of the space-time signal in space
and time respectively. Note that ${\bf S}\in\mathbb{R}^{N\times N}$ is the
graph shift operator (GSO), which usually represents the graph adjacency or
Laplacian, and ${\bf C}\in\\{0,1\\}^{N\times N}$ is a circulant matrix that
models the time shift operator (TSO). Then we can define the $k$-hop space-
time diffusion as ${\bf S}^{k}{\bf X}{\bf C}^{k}$, which allows us to define
the space-time graph filter (STGF) as the following convolutional operator

${{\bf Y}}=\sum_{k=0}^{K}h_{k}{\bf S}^{k}{\bf X}{\bf C}^{k},$ (1)

where the coefficients $\\{h_{k}\\}_{k=0}^{K}$ and the number of filter taps
$K$ are design parameters. The operation in (1) respects the time delays that
occur in sharing information between the neighbors. Indeed, the GSO and TSO
are jointly applied to ensure that the signals are shifted in space and time
before being aggregated over the graphs.

We design ST-GNNs as a cascade layers that deploy the STGF in (1) followed by
a nonlinear activation function $\sigma$. To distinguish the layers’
intermediate outputs we use subscript $l$ and superscript $f$ to denote the
$l$-th layer and the $f$-th feature of the signal respectively. The output of
the $l$-th layer is expressed as

${\bf X}_{l}^{f}=\sigma\Big{(}\sum_{g=1}^{F}\sum_{k=0}^{K}h_{kl}^{fg}{\bf
S}^{k}{\bf X}_{l-1}^{g}{\bf C}^{k}\Big{)}.$ (2)

We assume that the number of the features $F$ is fixed across all layers. We
further refer to the ST-GNN’s output, i.e., the output of the last layer $L$,
as ${\bf\Phi}({\bf X};{\bf S},\mathcal{H})$ with
$\mathcal{H}=\\{h_{kl}^{fg}\\}_{k,l}^{f,g}$ being the set of all learnable
parameters. Note that, we represent the underlying graph with a fixed GSO $\bf
S$, which is not always the case in practise. In the following section,
overcome this limitation we show how (1) can be modified to accommodate time-
varying graphs.

##  3 Generalized Space-Time GNNs

In various applications the graph is changing over time. In multi-agent
systems, for instance, the graph dynamics are time varying due to link
dropping and re-wiring. As a result, we observe a sequence of GSOs $\\{{\bf
S}_{k},\dots,{\bf S}_{0}\\}$. The diffusion of graph signals over this
sequence is modeled as

${\bf S}_{k}\dots\bf S_{0}{\bf X}=:{\bf S}_{k:0}{\bf X}.$

Since STGFs perform a weighted sum of diffused signals as shown in (1), a
generalized form of the STGF’s output can be derived as

$\tilde{\bf Y}=\sum_{k=0}^{K}h_{k}{\bf S}_{k}\dots\bf S_{0}{\bf
XC}^{k}=\sum_{k=0}^{K}h_{k}{\bf S}_{k:0}{\bf XC}^{k},$ (3)

with ${\bf S}_{0}$ being the identity matrix ${\bf I}$. Equation (1) is
obviously a special case with ${\bf S}_{K}=\dots={\bf S}_{1}={\bf S}$. Like
ST-GNNs in (2), we define the output of the $l$-th layer of the generalized
ST-GNN as

$\tilde{\bf
X}_{l}^{f}=\sigma\Big{(}\sum_{g=1}^{F}\sum_{k=0}^{K}h_{kl}^{fg}{\bf
S}_{k:0}\tilde{\bf X}_{l-1}^{g}{\bf C}^{k}\Big{)}.$ (4)

The following lemma shows the frequency response of (3).

######  Lemma 1 (Generalized STGF frequency response).

For a space-time graph filter with coefficients $\\{h_{k}\\}_{k=0}^{K}$
running over a sequence of $K$ GSOs as in (3), the generalized frequency
response is

$\begin{split}h({\bm{\lambda}},\omega)=\sum_{k=0}^{K}h_{k}e^{jk\omega}\prod_{\kappa=0}^{k}\lambda_{\kappa},\end{split}$
(5)

where ${\bm{\lambda}}=[\lambda_{1},\dots,\lambda_{K}]^{\top}$,
$\lambda_{0}=1$, and $\lambda_{k}$ is the analytic variable corresponding to
the eigenvalue of ${\bf S}_{k}$.

The proof of Lemma 1 is delegated to the journal version, due to space
limitations. We observe that the frequency response is a multi-variate
function in the graph-frequency variables $\lambda_{k},\forall k$, and the
time-frequency variable $\omega$.

In practice, we usually need to transfer generalized ST-GNN to different time-
varying graphs that are not observed during training. Therefor a natural
question that arises is “under which conditions is transfer learning doable?”
We tackle give a definitive answer to this question by analyzing the deviation
in the outputs between ST-GNNs and generalized ST-GNNs. Bounded deviations,
imply that learned models can be transferred between different sequences of
graphs.

##  4 Stability To Stochastic Graph Perturbations

To analyze the deviation between ST-GNNs and genaralized ST-GNNs, we first
define a model for time-varying graphs. In particular, we study a sequence of
random graphs $\\{{\cal G}_{k}\\}_{k=1}^{K}$ sampled from a nominal graph
$\cal G$ according to the following criteria.

######  Definition 1 (Random Edge Sampling).

Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, we define a random
graph RES($\mathcal{G},p$) with a realization
$\mathcal{G}_{k}=(\mathcal{V},\mathcal{E}_{k})$ such that an edge
$(i,j)\in\mathcal{E}$ exists in $\mathcal{E}_{k}$ with probability $p$, i.e.,

$\mathbb{P}[(i,j)\in\mathcal{E}_{k}]=p,\ \forall(i,j)\in\mathcal{E}.$ (6)

Definition 1 implies that ${\cal G}_{k}$ is constructed by sampling edges from
the nominal graph with probability $p$. From Definition 1, it follows that the
relation between the nominal GSO $\bf S$ and the random GSO ${\bf S}_{k}$ can
be written as

${\bf S}_{k}={\bf S}+{\bf E}_{k},$ (7)

where ${\bf E}_{k}$ models the deviation between the two GSOs. In (7), The
size of the deviation ${\bf E}_{k}$ is controlled by the edge-drop probability
$1-p$. Higher probabilities account for dropping more edges, which in turn
results in higher perturbation size $\|{\bf E}_{k}\|_{2}$. Probability $p$ can
be viewed as a measure of similarity between the nominal graph ${\cal G}$ and
a random realization ${\cal G}_{k}$.

With relation (7) in place, we next aim to compute the difference in STGF’s
outputs when running over either $\bf S$ or the sequence ${\bf S}_{K:0}$ with
each GSO having been constructed according to Definition 1. To achieve this,
we introduce Lemma (2), which defines a smoothness measure of the multi-
variate filter in (5).

######  Lemma 2.

Consider the generalized frequency response $h({\bm{\lambda}},\omega)$ in
Lemma 1, and let ${\bm{\lambda}}_{1}=[\lambda_{11},\dots,\lambda_{1K}]^{T}$
and ${\bm{\lambda}}_{2}=[\lambda_{21},\dots,\lambda_{2K}]^{T}$ be two
multivariate graph-frequency vectors. The variability in the frequency
response is then quantified as

$h({\bm{\lambda}}_{1},\omega)-h({\bm{\lambda}}_{2},\omega)={\bf\nabla}_{\bm{\lambda}}^{T}h({\bm{\lambda}}_{1,2},\omega)\cdot({\bm{\lambda}}_{1}-{\bm{\lambda}}_{2}),$
(8)

where
${\bf\nabla}_{\bm{\lambda}}h({\bm{\lambda}}_{1,2},\omega)=\left[\frac{\partial
h({\bm{\lambda}}^{(1)},\omega)}{\partial\lambda_{1}},\dots,\frac{\partial
h({\bm{\lambda}}^{(K)},\omega)}{\partial\lambda_{K}}\right]^{T}$ is the
Lipschitz gradient, and
${\bm{\lambda}}^{(k)}=[\lambda_{11},\dots,\lambda_{1k},\allowbreak\lambda_{2(k+1)},\dots,\lambda_{2K}]^{T}$
contains the first $k$ entries of ${\bm{\lambda}}_{1}$ along with the last
$K-k$ entries of ${\bm{\lambda}}_{2}$.

The proof of Lemma 2 follows the proof of Lemma 1 in [16]. The Lipschitz
gradient in (8) can be seen as a general measure of filter-response
variability, which is usually quantified by the derivatives in univariate
filters. Using the Lipschitz gradient, we define a class of smooth filters,
namely generalized integral Lipschitz filter, in the following definition.

######  Assumption 1.

[Generalized Integral Lipschitz filter] An STGF with the generalized frequency
response in Lemma 1 is generalized integral Lipschitz if there exists a
constant $C_{L}>0$ such that for any graph-frequency vectors
${\bm{\lambda}}_{1}$ and ${\bm{\lambda}}_{2}$ it holds that for all $\omega$

$\begin{split}\|{\bf\nabla}_{\bm{\lambda}}h({\bm{\lambda}}_{1,2},\omega)\|_{2}\leq
C_{L},\end{split}$ (9)
$\quad\|{\bm{\lambda}}_{1}\odot{\bf\nabla}_{\bm{\lambda}}h({\bm{\lambda}}_{1,2},\omega)\|_{2}\leq
C_{L},$ (10)

where ${\bf\nabla}_{\bm{\lambda}}h({\bm{\lambda}}_{1,2},\omega)$ is the
Lipschitz gradient defined in Lemma 2, and $\odot$ is the Hadamard product.

The condition in (9) indicates that the frequency response
$h({\bm{\lambda}},\omega)$ does not change faster than linear since we have

$\begin{split}|h({\bm{\lambda}}_{1},\omega)-h({\bm{\lambda}}_{2},\omega)|&=|{\bf\nabla}_{\bm{\lambda}}^{T}h({\bm{\lambda}}_{1,2},\omega)\cdot({\bm{\lambda}}_{1}-{\bm{\lambda}}_{2})|\\\
&\leq\|{\bf\nabla}_{\bm{\lambda}}^{T}h({\bm{\lambda}}_{1,2},\omega)\|_{2}\cdot\|{\bm{\lambda}}_{1}-{\bm{\lambda}}_{2}\|_{2}\\\
&\leq C_{L}\|{\bm{\lambda}}_{1}-{\bm{\lambda}}_{2}\|_{2}.\end{split}$

The first inequality follows from triangle inequality while the first and
third lines are direct application of Equations (8) and (9) respectively. On
the other hand, the condition in (10) states that the variability in the
frequency response should be low at higher eigenvalues. In other words,
filters that meet (10), albeit stable, have a near-flat response at higher
frequencies and therefore have poor discriminibilty between high graph
frequencies. Under the two conditions, Theorem 1 characterizes the stability
properties of STGFs.

######  Theorem 1 (STGF Stability).

Consider an STGF with coefficients $\\{h_{k}\\}_{k=0}^{K}$ running over a
sequence of $K$ identical GSOs ${\bf S}$ with output $\bf Y$ as in (1).
Consider a sequence of $K$ realizations of $RES(\mathcal{G},p)$ with GSOs
$\\{{\bf S}_{k}\\}_{k=1}^{K}$ under which the filter output $\tilde{\bf Y}$ is
captured in (3). Let ${\bf S}_{k}={\bf S}+{\bf E}_{k}$, for $k=1,\dots,K$, and
${\bf S}_{0}={\bf I}$. If Assumption 1 holds, the expected difference between
the filter outputs satisfies

$\mathbb{E}[\|\tilde{\bf Y}-{\bf Y}\|_{F}^{2}]\leq C(1-p)\|{\bf
X}\|_{F}^{2}+\mathcal{O}\left((1-p)^{2}\right),$ (11)

where $C=\alpha NC_{L}^{2}$, and the scalar $\alpha$ is either the maximum
node degree if $\bf S$ is the adjacency or $2$ if it is the Laplacian.

Theorem 1 affirms that the bound depends on some graph and filter parameters
as well as the probability of edge drop $1-p$. It comes with no surprise that
$N$ and $1-p$ contribute to the stability constant since holding either of
them fixed and increasing the other leads to dropping more edges while
constructing the random graph realization ${\cal G}_{k}$. Thus the distance
between the GSOs $\bf S$ and ${\bf S}_{k}$ increases and affects the stability
of the model. We also observe that filters with lower $C_{L}$ are more robust
to perturbations. The constant $C_{L}$ describes the variability in the filter
response (cf. (9)) and smaller values of $C_{L}$ indicates that the filter
response changes slowly. This implies that the filter smoothness is key to
provoke stability.

To analyze the stability of ST-GNNs, we consider a class of nonlinearities
$\sigma$ that is Lipschitz continuous as stated in Assumption 2.

######  Assumption 2.

The nonlinearities $\sigma$ are Lipschitz-continuous functions with a
Lipschitz constant $C_{\sigma}>0$ such that, for any two vectors ${\bf x}_{1}$
and ${\bf x}_{2}$, we have

$\|\sigma({\bf x}_{1})-\sigma({\bf x}_{2})\|_{2}\leq C_{\sigma}\|{\bf
x}_{1}-{\bf x}_{2}\|_{2}.$ (12)

This assumption is satisfied by the activation functions usually used in GNNs,
e.g., ReLU and hyperbolic tangent (tanh) functions. When Assumptions 1 and 2
hold, the stability of ST-GNNs is determined by Theorem 2.

######  Theorem 2 (ST-GNN Stability).

Consider an L-layer ST-GNN ${\bf\Phi}({\bf X};{\bf S},\mathcal{H})$ with $F$
features per layer and $F$ input and output features. Let the STGF with
coefficients $\\{h_{kl}^{fg}\\}_{kl}^{fg}$ at each layer satisfy Assumption 1
and have a unit norm, i.e., $\left|h({\bm{\lambda}},\omega)\right|\leq 1$.
Also, consider the same ST-GNN runs over a sequence of $K$ realizations of
$RES(\mathcal{G},p)$ with output $\tilde{\bf\Phi}({\bf X};{\bf
S},\mathcal{H})$. If the nonlinear activation functions satisfy Assumption 2,
the expected difference between the outputs is bounded by

$\begin{split}\mathbb{E}\left[\|\tilde{\bf\Phi}({\bf X};{\bf
S},\mathcal{H})-{\bf\Phi}({\bf X};{\bf S},\mathcal{H})\|_{F}^{2}\right]&\\\
\leq C(1-p)\|{\bf X}\|_{F}^{2}+&\mathcal{O}\left((1-p)^{2}\right),\end{split}$
(13)

where $C=\alpha NL^{2}C_{L}^{2}C_{\sigma}^{2L}F^{2L}$ with $\alpha$ being the
same constant in Theorem 1.

Besides all the factors that control the stability of STGFs, Theorem 2
includes some design factors, e.g., the number of features $F$, the number of
layers $L$, and the Lipschitz constant of the nonlinearities $C_{\sigma}$. It
is worth noting, however, that the bound grows exponentially with the number
of layers, which suggests that deep networks are less robust to perturbations.
This result is in line with other works that recommend the use of GNNs with
only a few layers [17]. The authors in [18] even show that a single-layer GNN
with multi-tap filters has a performance that is comparable, or even superior,
to that of multi-layer single-tap GNNs. For our considered tasks, we have also
observed that a small number of layers is sufficient to ensure stability
without sacrificing performance/expressivity. Detailed study of the expressive
power of GNNs can be found in [19].

##  5 Numerical Simulations

We consider the flocking problem in [20], where the objective is to coordinate
a swarm of agents to move together at the same velocity and avoid collisions.
The problem has a closed-form optimal solution (see [21]). However, this
solution requires access to data from all the agents and therefore does not
allow decentralized settings. On the other hand, solutions that rely on
gathering information from local neighborhood are harder to find. ST-GNNs can
close this gap by learning a decentralized policy using imitation learning.

To construct a dataset, each agent is associated with a time sequence of
positions $\mathbf{p}_{i}\in\mathbb{R}^{2\times T}$ and velocities
$\mathbf{v}_{i}\in\mathbf{R}^{2\times T}$ as node features. The agent is also
associated with optimal accelerations $\mathbf{u}_{i}\in\mathbb{R}^{2\times
T}$ as node predictions, which are pre-computed with a centralized algorithm.
The node features are computed at each time step $t$ via the system dynamics
as soon as the model predicts the acceleration $\hat{\bf u}_{i}(t-1)$, as
described in [20]. The agents form a communication network that varies over
time. The underlying graph ${\cal G}(t)$ contains an edge between nodes $i$
and $j$ if and only if they are within the communication range of each other,
i.e., $\|{\bf p}_{i}(t)-{\bf p}_{j}(t)\|_{2}\leq R$. Since the graph depends
on the present positions of the agents, we cannot forecast the graph sequence
before training/execution. For our experiments, the dataset contains $400$
examples for training, $80$ for validation, and another $80$ for testing.

We train an ST-GNN that consists of one layer with $K=3$, $F=64$ and $\tanh$
activation function. We then implement a local layer at each node to predict
the agent accelerations $\hat{\bf u}_{i}(t)$. We use ADAM [22] with learning
rate $5\times 10^{-4}$ and forgetting factors $\beta_{1}=0.9$ and
$\beta_{2}=0.999$ in order to optimize the MSE between the optimal ${\bf
u}_{i}(t)$ and the predicted $\hat{\bf u}_{i}(t)$. We train our model over
$30$ epochs and used validation input-output pairs to choose the one that
minimizes the velocity variation among the agents,

$\text{cost }=\sum_{i=1}^{N}\left\|{\bf v}_{i}-\frac{1}{N}\sum_{j=1}^{N}{\bf
v}_{j}\right\|_{F}^{2},$

averaged over the validation dataset.

Fig. 1: Relative cost induced by stochastic perturbations with different
sampling probabilities $p$ for $N=20$ (top), $N=50$ (middle), and $N=80$
(bottom).

In our first experiment, we train an ST-GNN on a fixed graph and test it over
a sequence of random graphs sampled according to definition 1. Contrary to
[20], we train our model on the average of the graph sequence. But since we
cannot forecast the graphs before training as we mentioned before, we use the
agent’s positions computed with the optimal accelerations to compute the graph
sequence and, in turn, their average. During execution, we sample a graph
sequence from the average graph with a sampling probability
$p\in\\{1,0.95,0.9,0.85,0.8,0.75,0.7\\}$. Note that the sampled graph
sequences no longer represent the agent’s proximity since we decide on the
fixed graph before training and we sample randomly from it at execution. Fig.
1 shows that the relative cost increases linearly with the edge-drop
probability $1-p$, matching the result of Theorem 2. We also train an STGF
with $K=4$ and $F=32$ and verify the linear bound of Theorem 1. We, however,
observe that ST-GNNs show less relative cost compared to STGFs even though we
used a lower number of features with the latter. We attribute this observation
to the $\tanh$ activation function being a nonexpansive mapping (i.e., we have
$C_{\sigma}\leq 1$).

We train a generalized ST-GNN, where the graphs are formed according to the
communication networks between the agents. The graphs are constructed based on
a communication range of $R=2m$ as described at the beginning of this section
and as in [20]. Thus the graphs are time varying during both training and
execution. Fig. 2 illustrates snapshots of the output of a generalized ST-GNN
for two test examples with unseen time-varying graphs of sizes $N=20$ and
$N=50$ nodes. The snapshots were taken at the beginning and end of a time
interval of $2$s. We observe that all the agents managed to move with the same
velocity and in the same direction by the end of the time interval. This
indicates that the trained ST-GNN is successfully transferred to unseen
graphs, which validate our theoretical results.

(a) $t=0$s

(b) $t=1.99$s

Fig. 2: Snapshots of two test examples: (top) $N=20$ and (bottom) $N=50$. The
dots represent the agents, the gray lines illustrate the underlying graphs,
and the dark arrows show the agents’ velocity.

##  6 Conclusions

The paper studied the stability of ST-GNNs to stochastic graph perturbations
and showed that we can transfer learned models over time-varying graphs. Our
analysis also enabled us to design generalized ST-GNNs that can be trained
over time-varying graphs. We concluded that the stability bound is controlled
by some graph, filter, and design parameters. The bound increases linearly
with the graph size as well as the size of graph perturbations, represented by
the edge-drop probability. It also depends on the Lipschitz constant of STGFs
and the nonlinearities. Among all those parameters, only the Lipschitz
constant of the filters cannot be decided before training since the filter is
learnable. The stability can though be enhanced by forcing the filter to have
a low Lipschitz constant during training, which is left as a future work.

## References

  * [1] S. Verma and Z.-L. Zhang,  “Stability and generalization of graph convolutional neural networks,”  in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 1539–1548.
  * [2] N. Keriven, A. Bietti, and S. Vaiter,  “Convergence and stability of graph convolutional networks on large random graphs,”  Advances in Neural Information Processing Systems, vol. 33, pp. 21512–21523, 2020.
  * [3] F. Gama, J. Bruna, and A. Ribeiro,  “Stability properties of graph neural networks,”  IEEE Transactions on Signal Processing, vol. 68, pp. 5680–5695, 2020.
  * [4] H.-S. Nguyen, Y. He, and H.-T. Wai,  “On the stability of low pass graph filter with a large number of edge rewires,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022, pp. 5568–5572.
  * [5] H. Kenlay, D. Thano, and X. Dong,  “On the stability of graph convolutional neural networks under edge rewiring,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 8513–8517.
  * [6] R. Levie, W. Huang, L. Bucci, M. M. Bronstein, and G. Kutyniok,  “Transferability of spectral graph convolutional neural networks.,”  J. Mach. Learn. Res., vol. 22, pp. 272–1, 2021.
  * [7] L. Ruiz, L. Chamon, and A. Ribeiro,  “Graphon neural networks and the transferability of graph neural networks,”  Advances in Neural Information Processing Systems, vol. 33, pp. 1702–1712, 2020.
  * [8] S. Maskey, R. Levie, and G. Kutyniok,  “Transferability of graph neural networks: an extended graphon approach,”  arXiv preprint arXiv:2109.10096, 2021.
  * [9] K. Osanlou, A. Bursuc, C. Guettier, T. Cazenave, and E. Jacopin,  “Optimal solving of constrained path-planning problems with graph convolutional networks and optimized tree search,”  in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2019, pp. 3519–3525.
  * [10] Q. Li, W. Lin, Z. Liu, and A. Prorok,  “Message-aware graph attention networks for large-scale multi-robot path planning,”  IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 5533–5540, 2021.
  * [11] Y. Zhou, J. Xiao, Y. Zhou, and G. Loianno,  “Multi-robot collaborative perception with graph neural networks,”  IEEE Robotics and Automation Letters, vol. 7, no. 2, pp. 2289–2296, 2022.
  * [12] S. He, S. Xiong, Y. Ou, J. Zhang, J. Wang, Y. Huang, and Y. Zhang,  “An overview on the application of graph neural networks in wireless networks,”  IEEE Open Journal of the Communications Society, 2021.
  * [13] Z. Zhao, G. Verma, C. Rao, A. Swami, and S. Segarra,  “Distributed scheduling using graph neural networks,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021, pp. 4720–4724.
  * [14] W. Yan, D. Jin, Z. Lin, and F. Yin,  “Graph neural network for large-scale network localization,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021, pp. 5250–5254.
  * [15] S. Hadou, C. I. Kanatsoulis, and A. Ribeiro,  “Space-time graph neural networks,”  in International Conference on Learning Representations, 2022.
  * [16] Z. Gao, E. Isufi, and A. Ribeiro,  “Stability of graph convolutional neural networks to stochastic perturbations,”  Signal Processing, vol. 188, pp. 108216, 2021.
  * [17] T. Chen, K. Zhou, K. Duan, W. Zheng, P. Wang, X. Hu, and Z. Wang,  “Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022\.
  * [18] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger,  “Simplifying graph convolutional networks,”  in Proceedings of the 36th International Conference on Machine Learning. 2019, pp. 6861–6871, PMLR.
  * [19] C. I. Kanatsoulis and A. Ribeiro,  “Graph neural networks are more powerful than we think,”  arXiv preprint arXiv:2205.09801, 2022.
  * [20] E. Tolstaya, F. Gama, J. Paulos, G. Pappas, V. Kumar, and A. Ribeiro,  “Learning decentralized controllers for robot swarms with graph neural networks,”  in Proceedings of the Conference on Robot Learning, Oct 2020, vol. 100, pp. 671–682.
  * [21] H. G. Tanner, A. Jadbabaie, and G. J. Pappas,  “Stable flocking of mobile agents part II: dynamic topology,”  in Proceedings of the IEEE Conference on Decision and Control, 2003, vol. 2, pp. 2016–2021.
  * [22] D. P. Kingma and J. Ba,  “Adam: A method for stochastic optimization,”  in International Conference on Learning Representations ICLR, 2015\.