# Rethinking Machine Learning Model Evaluation in Pathology

Syed Ashar Javed*, Dinkar Juyal*, Shreya Chakraborty*, Zahil Shanis*, Harsha
Pokkalla, Aaditya Prakash PathAI Inc., Boston<EMAIL_ADDRESS>
###### Abstract

Machine Learning has been applied to pathology images in research and clinical
practice with promising outcomes. However, standard ML models often lack the
rigorous evaluation required for clinical decisions. Machine learning
techniques for natural images are ill-equipped to deal with pathology images
that are significantly large and noisy, require expensive labeling, are hard
to interpret, and are susceptible to spurious correlations. We propose a set
of practical guidelines for ML evaluation in pathology that address the above
concerns. The paper includes measures for setting up the evaluation framework,
effectively dealing with variability in labels, and a recommended suite of
tests to address issues related to domain shift, robustness, and confounding
variables. We hope that the proposed framework will bridge the gap between ML
researchers and domain experts, leading to wider adoption of ML techniques in
pathology and improving patient outcomes.

##  1 Introduction

Pathology is often treated as a ground-truth for many serious diseases and a
pathologist’s diagnosis is critical for a wide variety of tasks, including
drug development and clinical diagnostics. The typical workflows of a
pathologist are complicated, subjective and limited by what humans can
evaluate. The use of machine learning in pathology has begun to transform the
field with applications like clinical decision support tools (Campanella et
al., 2019), improving prognostic utility over manual reads (Taylor-Weiner et
al., 2021), automating slide scoring in clinical trials (Glass et al., 2021),
novel biomarker discovery (Echle et al., 2021), and understanding tumor
pathology (Jiang et al., 2020; Diao et al., 2021)††*equal contributions.

These models require thorough validation and verification since they directly
impact patient lives and their evaluation requires a careful look at the
setting in which they will be deployed. Pathology images also differ from
natural images in various ways - they are massive in resolution (billions of
pixels) with each magnification-level containing markedly different
information (Komura & Ishikawa, 2018), have different equivariances from
natural images (Veeling et al., 2018) and contain stain variations which can
confound models (Yagi, 2011; Madabhushi & Lee, 2016; Tellez et al., 2019). In
addition to that, exhaustive labeling of these images is prohibitive as they
require expert annotations and are time-consuming. Finally, building ML models
for these problems requires understanding of biological causal structures to
deal with spurious features (Castro et al., 2020). These differences
necessitate model evaluation guidelines specific to pathology problems to
prevent life threatening model failures.

In machine learning, dataset creation, evaluation setup, choice of metrics,
and the data splits used for training, validation and testing have been areas
of study in themselves, and the research community depends on agreed standards
for evaluating novel methods and their utility in the real world. Previous
work in medical imaging has highlighted problems in transferring these
evaluation methodologies, making models brittle for deployment in real-world
setting (Park & Han, 2018; England & Cheng, 2019; Varoquaux & Cheplygina,
2021; Reinke et al., 2021). In this work, we propose a guideline on ML model
evaluation for pathology which go beyond standard ML metrics. We define how to
setup the evaluation framework, create the test-set, acquire labels for
evaluation and finally suggest a set of evaluation metrics which are aimed
towards real-world deployment.

##  2 Guidelines for Model Evaluation

We divide model evaluation into three stages: evaluation setup, label
collection, and evaluation metrics as shown in Figure 1. We provide pathology-
specific recommendations for each of them in the following sections.

Figure 1: Guidelines for Model Evaluation

###  2.1 Evaluation Setup

####  2.1.1 Alignment of evaluation experiments with model’s intended use

The applications of ML in pathology vary by their intended use, such as drug
discovery, diagnostics, prognostics, decision-support, or triage. Therefore,
their evaluation setup and metrics must account for the targeted use-case. For
example, a clinical decision support tool is used by pathologists to look at
predictions generated by the model to refine their diagnosis. The evaluation
setup must measure the change in pathologist performance when assisted by the
model instead of comparing model predictions against that of the pathologist.

Another example is the use of ML in building a triage tool for screening
patients. In oncology, ML can be used to filter out obviously benign cases so
that the pathologists prioritize malignant cases, thus improving patient care.
In such scenarios, instead of using common metrics like accuracy or AUROC, one
should use Precision@K%Recall due to the low tolerance for a false negative.

####  2.1.2 Enriched and confounder-aware test set creation

Pathology samples come with biological and other metadata like patient-related
(age, gender, ethnicity), image-related (scanner type, image format,
magnification), specimen & stain related (tissue collection type, thickness of
specimen, staining protocol), and clinical (disease stage, prescribed therapy,
omics data). Low prevalence of certain metadata values coupled with small,
imbalanced datasets in pathology often lead to overoptimistic results if the
test set composition does not account for smaller substrata. This hidden
stratification problem (Oakden-Rayner et al., 2020) can result in the model
not working well for patients belonging to a hidden substrata, which in turn
deteriorates trust in such tools. Another stratum which needs more
representation is samples close to the decision boundary where significant
ambiguity in labels exist. This occurs since labels in pathology represent a
biological process which is continuous. For example, along with benign and
malignant there exist borderline cases which might be under-represented if
real-world data distribution is replicated in test dataset.

A related problem is the presence of confounders in the test set which are
spuriously predictive of the label. For example, in pancreatic cancer, (Kather
et al., 2020) show that KRAS mutation can be predicted from a pathology image.
However, KRAS mutation is almost exclusively present in only one sub-type of
pancreatic cancer (pancreatic ductal adenocarcinoma), thus becoming a strong
biological confounder (Waters & Der, 2018). Therefore, even a well performing
mutation prediction model might be relying on pancreatic sub-type features
instead of the KRAS mutation features. The fact that these confounders can
also be partial, non-biological and specific to the dataset, further
complicates matters (Badgeley et al., 2019; Larrazabal et al., 2020; Zech et
al., 2018).

To ensure that the test-set is reliable and the model is predicting the
variable of interest and not a confounder, we offer the following suggestions:

  * •

Curate test sets such that they have enough representation of any sub-strata
of data that we care about or that could be a confounder (Seyyed-Kalantari et
al., 2020). This can be done through enrichment (oversampling) of rare
substrata as mentioned in this FDA guide (Food et al., ). However
practitioners should be aware of selection bias due to test-set enrichment (Yu
& Eng, 2020).

  * •

Incorporate stratified evaluation metrics as opposed to a single test-set wide
global metric. For example, ensuring consistent performance across patient
demographics or disease severity.

  * •

Conduct a correlation check on all metadata values present in the dataset to
see if any of them correlate highly with label values for the task of
interest. For example, if all images positive for prostate cancer come from
the same hospital, the model can learn to predict the hospital instead of the
cancer, making it a potential confounder.

####  2.1.3 External hold-out test set

Curated datasets are useful for research, but often suffer from the problem of
a homogeneous test-set. The approach of collecting data from a single source
and splitting it into train-val-test sets results in inflated performance
since the models might not generalize to distributional shifts (like images
from a new hospital) (Tellez et al., 2019; Campanella et al., 2019). Many
popular pathology datasets (Borkowski et al., 2019; Hosseini et al., 2019;
Karimi et al., 2019) and studies (Shao et al., 2021; Sudharshan et al., 2019)
do not have externally held-out test sets from a new site which prevent an
evaluation of the generalizability. We suggest using multiple held-out patient
cohorts from different medical sites and demographics while constructing the
test set (Koh et al., 2021). We also suggest checking for test data leakage in
the form of patient samples being present across multiple splits. Finally, we
urge the community to make such a testing setup the norm for model evaluation
in pathology.

Figure illustrates the discordance among pathologists while grading NASH, an
aggressive form of non-alcoholic fatty liver disease increasingly being seen
as an epidemic in the US. In this case, NASH severity is found by performing a
liver biopsy, viewing the extracted tissue through a microscope and observing
signs of disease progression such as presence of fat, different kinds of
inflammation etc.

What is most telling in this figure is the extremely low agreement among
doctors while predicting disease progression even after using the most
reliable way to do so, which is viewing the tissue extracted from the biopsy.
The numbers on the left column denote the Kappa score for different
morphological indicators of NASH (N denotes the number of patients), when the
first study was done in 2005. The right column shows the agreement scores for
the same from a 2020 study; there has been little or no change in these
agreement scores among human experts even after 15 years.

###  2.2 Evaluation Labels

(a)

(b)

Figure 2:

It is possible to get fast and cheap labels using crowdsourced tools for
natural images, and the correctness of these labels is easily verifiable. In
contrast, it is a lot harder to collect ground-truth labels for pathology.
Pathology images have billions of pixels, millions of cells, and thousands of
regions of interest, making label collection extremely resource-intensive.
Annotators (typically certified pathologists) are in short supply and per unit
cost of annotations is order of magnitude higher than natural images.
Annotators also have their own biases (Aeffner et al., 2017).

A more insidious problem is of the high ‘inter-annotator variability’
(Carrasco-Zevallos et al., 2021) as shown in Figure 2(a), and ‘intra-annotator
variability’ (Kleiner et al., 2005; Davison et al., 2020): annotators disagree
not only with each other but also with their past selves. These variabilities
exist at different stages of label generation - they can originate from
inherent ambiguity in the labeling system, different interpretations of the
same labeling scheme by different experts, and the differences in the
expertise of these annotators (Ozkan et al., 2016). The threshold for
acceptable variability is subjective, and depends on factors such as the
particular organ and disease.

We propose the following guidelines while collecting labels:

  * •

Collect multiple annotations per image and measure the inter-annotator
agreement. If possible, collect multiple annotations on the same image from
the same annotator at adequately-spaced timepoints (called ‘washout period’)
to measure intra-annotator variability. If these variabilities are high, the
ML task might not be viable.

  * •

Aggregate the labels to a single consensus if the intra and inter-annotator
variabilities are low. Instead of comparing model performance with a single
pathologist (Liu et al., 2017) or consensus, measure the agreement of the
model with the consensus and judge it against inter-annotator consensus. This
is more realistic and appreciates the difficulty of the task as judged by
human’s inability to do it consistently (Raciti et al., 2020). Kappa (Linear,
Quadratic) and Intraclass Correlation Coefficient(ICC) are popularly used to
measure single and multi-rater agreement Bulten et al. (2022); Koo & Li
(2016).

###  2.3 Evaluation Metrics

####  2.3.1 Reproducibility, Repeatability, & Robustness tests

Pathology images are heterogeneous with regard to staining, tissue thickness,
and are prone to variations during tissue processing, cutting, staining, and
digitization (Figure 2(b)). These variations cause minor visually perceptible
changes to the image, but can drastically change the model prediction. Lack of
robustness to these perturbations poses a major challenge to the wider
adoption and use of ML in pathology, especially in a clinical setting
(Schömig-Markiefka et al., 2021). Accuracy based assessment of models,
although necessary, is not sufficient for capturing model generalization.
Following tests must be incorporated into the model evaluation framework to
assess model’s robustness to these variations:

  * •

Reproducibility Tests: Models must be tested under known sources of variations
and evaluated for consistency and accuracy in performance. This includes
testing by explicitly changing external variations such as staining &
scanning, variations associated with hardware (non-determinism in GPU) and
software packages. Models in pathology are usually trained on smaller patches
of the image due to their large size (Shao et al., 2021; Taylor-Weiner et al.,
2021). Stochasticity introduced due to sampling the patches can lead to
inconsistent predictions and robustness to this variability must also be
reported.

  * •

Repeatability Tests: Repeatability expresses the precision under the same
operating conditions over a short interval of time (FDA, 1995). This test
captures unknown & unaccountable variations that are not covered by
reproducibility tests. Consistency in model predictions must be measured and
reported by rescanning & rerunning inference on the same image multiple times,
keeping all known sources of variations constant.

  * •

Robustness to Perturbations: Creating test sets that capture all possible
real-world variations of images is not practical. An alternative can be to
evaluate robustness on synthetically generated perturbations inspired by real
world variations to image samples, by measuring consistency of predictions
across these perturbations (Hendrycks & Dietterich, 2019; Schömig-Markiefka et
al., 2021). Models that are robust to synthetic variations have been shown to
be robust to natural variations (Faryna et al., 2021).

####  2.3.2 Negative Control Tests

Cross domain differences in pathology images collected from different sources
may confound the discovery of explanatory variables and lead to poor
generalization. This phenomenon, called ‘batch effects’ (Goh et al., 2017),
can lead to the model learning spurious features. Existing literature on batch
effects show that models can predict patient age, sex, race, time of slide
preparation, site, and scanner (Schmitt et al., 2021; Howard et al., 2020).

Although creating confounder-aware test sets can mitigate some of these
issues, partial and hidden confounders may go unnoticed and affect model
performance. Another approach to tackle this issue is to perform negative
control tests which involve running experiments under conditions in which the
model is not expected to produce correct predictions (Lipsitch et al., 2010).
We suggest the following strategies for designing negative control experiments
for ML in pathology:

  * •

Train with regions of the image which have no discriminative information. For
example, a model trained to predict cancer using only background (non-tissue
area) should perform poorly.

  * •

Train without regions which are essential for predicting the label. For
example, models for predicting cancer should perform poorly when trained and
deployed on patches sampled from non-cancer regions.

Failure of a negative control test signals the presence of confounders and
biases that create spurious correlations. These tests are not designed to
detect all types of confounders, but they help detect the prominent ones and
take appropriate actions.

##  3 Conclusion

Machine learning for pathology requires different evaluation standards due to
differences in image characteristics and clinical use-case. Existing datasets
and evaluation metrics prevalent within the ML community need to be rethought
to fit pathology applications. We have observed that there exist two distinct
communities, one of ML researchers focused on the development of novel methods
and the other of computational pathology researchers focused on exploring and
utilizing the power of ML in healthcare, and model evaluation differs between
them materially. We argue that domain-specific knowledge from pathology
concerning label reliability, test set enrichment, and biological confounders
should permeate into ML research. Conversely, advancements in ML such as
synthetic data generation, robustness and sensitivity analysis, and out-of-
domain testing deserve wider adoption in computational pathology. In this
paper, we propose a set of guidelines for evaluating ML models in pathology
which will help researchers create better datasets, metrics, and evaluation
setup. We believe this will improve patient outcomes through ML applications
in pathology and inform real-world motivated research.

#### Acknowledgments

Authors would like to thank Jonathan Rubin (Philips, Amazon) and Maz Abulnaga
(MIT) for their inputs.

## References

  * Aeffner et al. (2017) Famke Aeffner, Kristin Wilson, Nathan T. Martin, Joshua C. Black, Cris L. Luengo Hendriks, Brad Bolon, Daniel G. Rudmann, Roberto Gianani, Sally R. Koegler, Joseph Krueger, and G. Dave Young.  The Gold Standard Paradox in Digital Image Analysis: Manual Versus Automated Scoring as Ground Truth.  _Archives of Pathology & Laboratory Medicine_, 141(9):1267–1275, 05 2017.  ISSN 0003-9985.  doi: 10.5858/arpa.2016-0386-RA.  URL https://doi.org/10.5858/arpa.2016-0386-RA.
  * Badgeley et al. (2019) Marcus A Badgeley, John R Zech, Luke Oakden-Rayner, Benjamin S Glicksberg, Manway Liu, William Gale, Michael V McConnell, Bethany Percha, Thomas M Snyder, and Joel T Dudley.  Deep learning predicts hip fracture using confounding patient and healthcare variables.  _NPJ digital medicine_ , 2(1):1–10, 2019.
  * Borkowski et al. (2019) Andrew A Borkowski, Marilyn M Bui, L Brannon Thomas, Catherine P Wilson, Lauren A DeLand, and Stephen M Mastorides.  Lung and colon cancer histopathological image dataset (lc25000).  _arXiv preprint arXiv:1912.12142_ , 2019.
  * Bulten et al. (2022) Wouter Bulten, Kimmo Kartasalo, Po-Hsuan Cameron Chen, Peter Ström, Hans Pinckaers, Kunal Nagpal, Yuannan Cai, David F Steiner, Hester van Boven, Robert Vink, et al.  Artificial intelligence for diagnosis and gleason grading of prostate cancer: the panda challenge.  _Nature medicine_ , pp. 1–10, 2022.
  * Campanella et al. (2019) Gabriele Campanella, Matthew G Hanna, Luke Geneslaw, Allen Miraflor, Vitor Werneck Krauss Silva, Klaus J Busam, Edi Brogi, Victor E Reuter, David S Klimstra, and Thomas J Fuchs.  Clinical-grade computational pathology using weakly supervised deep learning on whole slide images.  _Nature medicine_ , 25(8):1301–1309, 2019.
  * Carrasco-Zevallos et al. (2021) Oscar Carrasco-Zevallos, Amaro Taylor-Weiner, Harsha Pokkalla, Maryam Pouryahya, Charles Biddle-Snead, Ling Han, Ryan Huss, Dinkar Juyal, Zahil Shanis, Aryan Pedawi, et al.  Ai-based histologic measurement of nash (aim-nash): A drug development tool for assessing clinical trial end points.  In _JOURNAL OF HEPATOLOGY_ , volume 75, pp. S254–S254. ELSEVIER RADARWEG 29, 1043 NX AMSTERDAM, NETHERLANDS, 2021.
  * Castro et al. (2020) Daniel C Castro, Ian Walker, and Ben Glocker.  Causality matters in medical imaging.  _Nature Communications_ , 11(1):1–10, 2020.
  * Davison et al. (2020) Beth A. Davison, Stephen A. Harrison, Gad Cotter, Naim Alkhouri, Arun Sanyal, Christopher Edwards, Jerry R. Colca, Julie Iwashita, Gary G. Koch, and Howard C. Dittrich.  Suboptimal reliability of liver biopsy evaluation has implications for randomized clinical trials.  _Journal of Hepatology_ , 73(6):1322–1332, 2020\.  ISSN 0168-8278.  doi: https://doi.org/10.1016/j.jhep.2020.06.025.  URL https://www.sciencedirect.com/science/article/pii/S0168827820303998.
  * Diao et al. (2021) James A Diao, Jason K Wang, Wan Fung Chui, Victoria Mountain, Sai Chowdary Gullapally, Ramprakash Srinivasan, Richard N Mitchell, Benjamin Glass, Sara Hoffman, Sudha K Rao, et al.  Human-interpretable image features derived from densely mapped cancer pathology slides predict diverse molecular phenotypes.  _Nature communications_ , 12(1):1–15, 2021.
  * Echle et al. (2021) Amelie Echle, Niklas Timon Rindtorff, Titus Josef Brinker, Tom Luedde, Alexander Thomas Pearson, and Jakob Nikolas Kather.  Deep learning in cancer pathology: a new generation of clinical biomarkers.  _British journal of cancer_ , 124(4):686–696, 2021.
  * England & Cheng (2019) Joseph R England and Phillip M Cheng.  Artificial intelligence for medical image analysis: a guide for authors and reviewers.  _American journal of roentgenology_ , 212(3):513–519, 2019.
  * Faryna et al. (2021) Khrystyna Faryna, Jeroen van der Laak, and Geert Litjens.  Tailoring automated data augmentation to h&e-stained histopathology.  In _Medical Imaging with Deep Learning_ , 2021.
  * FDA (1995) FDA.  Guideline for Industry: Text on Validation of Analytical Procedures .  https://www.fda.gov/media/71724/download, 1995.
  * (14) Food, Drug Administration, et al.  Guidance for industry and food and drug administration staff: Computer-assisted detection devices applied to radiology images and radiology device data-premarket notification [510 (k)] submissions.
  * Glass et al. (2021) Benjamin Glass, Michel Erminio Vandenberghe, Surya Teja Chavali, Syed Ashar Javed, Marlon Rebelatto, Shamira Sridharan, Hunter Elliott, Sudha Rao, Michael Montalto, Murray Resnick, et al.  Machine learning models to quantify her2 for real-time tissue image analysis in prospective clinical trials., 2021.
  * Goh et al. (2017) Wilson Wen Bin Goh, Wei Wang, and Limsoon Wong.  Why batch effects matter in omics data, and how to avoid them.  _Trends in biotechnology_ , 35(6):498–507, 2017\.
  * Hendrycks & Dietterich (2019) Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  _arXiv preprint arXiv:1903.12261_ , 2019.
  * Hosseini et al. (2019) Mahdi S Hosseini, Lyndon Chan, Gabriel Tse, Michael Tang, Jun Deng, Sajad Norouzi, Corwyn Rowsell, Konstantinos N Plataniotis, and Savvas Damaskinos.  Atlas of digital pathology: A generalized hierarchical histological tissue type-annotated database for deep learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11747–11756, 2019.
  * Howard et al. (2020) Frederick M Howard, James Dolezal, Sara Kochanny, Jefree Schulte, Heather Chen, Lara Heij, Dezheng Huo, Rita Nanda, Olufunmilayo I Olopade, Jakob N Kather, et al.  The impact of digital histopathology batch effect on deep learning model accuracy and bias.  _bioRxiv_ , 2020.
  * Jiang et al. (2020) Yahui Jiang, Meng Yang, Shuhao Wang, Xiangchun Li, and Yan Sun.  Emerging role of deep learning-based artificial intelligence in tumor pathology.  _Cancer communications_ , 40(4):154–166, 2020\.
  * Karimi et al. (2019) Davood Karimi, Guy Nir, Ladan Fazli, Peter C Black, Larry Goldenberg, and Septimiu E Salcudean.  Deep learning-based gleason grading of prostate cancer from histopathology images—role of multiscale decision aggregation and data augmentation.  _IEEE journal of biomedical and health informatics_ , 24(5):1413–1426, 2019.
  * Kather et al. (2020) Jakob Nikolas Kather, Lara R Heij, Heike I Grabsch, Chiara Loeffler, Amelie Echle, Hannah Sophie Muti, Jeremias Krause, Jan M Niehues, Kai AJ Sommer, Peter Bankhead, et al.  Pan-cancer image-based detection of clinically actionable genetic alterations.  _Nature Cancer_ , 1(8):789–799, 2020.
  * Kleiner et al. (2005) David E. Kleiner, Elizabeth M. Brunt, Mark Van Natta, Cynthia Behling, Melissa J. Contos, Oscar W. Cummings, Linda D. Ferrell, Yao-Chang Liu, Michael S. Torbenson, Aynur Unalp-Arida, Matthew Yeh, Arthur J. McCullough, Arun J. Sanyal, and Nonalcoholic Steatohepatitis Clinical Research Network.  Design and validation of a histological scoring system for nonalcoholic fatty liver disease.  _Hepatology_ , 41(6):1313–1321, 2005.  doi: https://doi.org/10.1002/hep.20701.  URL https://aasldpubs.onlinelibrary.wiley.com/doi/abs/10.1002/hep.20701.
  * Koh et al. (2021) Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  In _International Conference on Machine Learning_ , pp. 5637–5664. PMLR, 2021.
  * Komura & Ishikawa (2018) Daisuke Komura and Shumpei Ishikawa.  Machine learning methods for histopathological image analysis.  _Computational and structural biotechnology journal_ , 16:34–42, 2018.
  * Koo & Li (2016) Terry K Koo and Mae Y Li.  A guideline of selecting and reporting intraclass correlation coefficients for reliability research.  _Journal of chiropractic medicine_ , 15(2):155–163, 2016.
  * Larrazabal et al. (2020) Agostina J Larrazabal, Nicolás Nieto, Victoria Peterson, Diego H Milone, and Enzo Ferrante.  Gender imbalance in medical imaging datasets produces biased classifiers for computer-aided diagnosis.  _Proceedings of the National Academy of Sciences_ , 117(23):12592–12594, 2020.
  * Lipsitch et al. (2010) Marc Lipsitch, Eric Tchetgen Tchetgen, and Ted Cohen.  Negative controls: a tool for detecting confounding and bias in observational studies.  _Epidemiology (Cambridge, Mass.)_ , 21(3):383, 2010.
  * Liu et al. (2017) Yun Liu, Krishna Gadepalli, Mohammad Norouzi, George E. Dahl, Timo Kohlberger, Aleksey Boyko, Subhashini Venugopalan, Aleksei Timofeev, Philip Q. Nelson, Greg S. Corrado, Jason D. Hipp, Lily Peng, and Martin C. Stumpe.  Detecting cancer metastases on gigapixel pathology images, 2017.
  * Madabhushi & Lee (2016) Anant Madabhushi and George Lee.  Image analysis and machine learning in digital pathology: Challenges and opportunities.  _Medical image analysis_ , 33:170–175, 2016.
  * Oakden-Rayner et al. (2020) Luke Oakden-Rayner, Jared Dunnmon, Gustavo Carneiro, and Christopher Ré.  Hidden stratification causes clinically meaningful failures in machine learning for medical imaging.  In _Proceedings of the ACM conference on health, inference, and learning_ , pp. 151–159, 2020.
  * Ozkan et al. (2016) Tayyar A Ozkan, Ahmet T Eruyar, Oguz O Cebeci, Omur Memik, Levent Ozcan, and Ibrahim Kuskonmaz.  Interobserver variability in gleason histological grading of prostate cancer.  _Scandinavian journal of urology_ , 50(6):420–424, 2016.
  * Park & Han (2018) Seong Ho Park and Kyunghwa Han.  Methodologic guide for evaluating clinical performance and effect of artificial intelligence technology for medical diagnosis and prediction.  _Radiology_ , 286(3):800–809, 2018.
  * Raciti et al. (2020) Patricia Raciti, Jillian Sue, Rodrigo Ceballos, Ran Godrich, Jeremy D Kunz, Supriya Kapur, Victor Reuter, Leo Grady, Christopher Kanan, David S Klimstra, et al.  Novel artificial intelligence system increases the detection of prostate cancer in whole slide images of core needle biopsies.  _Modern Pathology_ , 33(10):2058–2066, 2020.
  * Reinke et al. (2021) Annika Reinke, Matthias Eisenmann, Minu D Tizabi, Carole H Sudre, Tim Rädsch, Michela Antonelli, Tal Arbel, Spyridon Bakas, M Jorge Cardoso, Veronika Cheplygina, et al.  Common limitations of image processing metrics: A picture story.  _arXiv preprint arXiv:2104.05642_ , 2021.
  * Schmitt et al. (2021) Max Schmitt, Roman Christoph Maron, Achim Hekler, Albrecht Stenzinger, Axel Hauschild, Michael Weichenthal, Markus Tiemann, Dieter Krahl, Heinz Kutzner, Jochen Sven Utikal, et al.  Hidden variables in deep learning digital pathology and their potential to cause batch effects: prediction model study.  _Journal of medical Internet research_ , 23(2):e23436, 2021.
  * Schömig-Markiefka et al. (2021) Birgid Schömig-Markiefka, Alexey Pryalukhin, Wolfgang Hulla, Andrey Bychkov, Junya Fukuoka, Anant Madabhushi, Viktor Achter, Lech Nieroda, Reinhard Büttner, Alexander Quaas, et al.  Quality control stress test for deep learning-based diagnostic model in digital pathology.  _Modern Pathology_ , 34(12):2098–2108, 2021.
  * Seyyed-Kalantari et al. (2020) Laleh Seyyed-Kalantari, Guanxiong Liu, Matthew McDermott, Irene Y Chen, and Marzyeh Ghassemi.  Chexclusion: Fairness gaps in deep chest x-ray classifiers.  In _BIOCOMPUTING 2021: Proceedings of the Pacific Symposium_ , pp. 232–243. World Scientific, 2020.
  * Shao et al. (2021) Zhuchen Shao, Hao Bian, Yang Chen, Yifeng Wang, Jian Zhang, Xiangyang Ji, et al.  Transmil: Transformer based correlated multiple instance learning for whole slide image classification.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Sudharshan et al. (2019) PJ Sudharshan, Caroline Petitjean, Fabio Spanhol, Luiz Eduardo Oliveira, Laurent Heutte, and Paul Honeine.  Multiple instance learning for histopathological breast cancer image classification.  _Expert Systems with Applications_ , 117:103–111, 2019\.
  * Taylor-Weiner et al. (2021) Amaro Taylor-Weiner, Harsha Pokkalla, Ling Han, Catherine Jia, Ryan Huss, Chuhan Chung, Hunter Elliott, Benjamin Glass, Kishalve Pethia, Oscar Carrasco-Zevallos, et al.  A machine learning approach enables quantitative measurement of liver histology and disease monitoring in nash.  _Hepatology_ , 74(1):133–147, 2021.
  * Tellez et al. (2019) David Tellez, Geert Litjens, Péter Bándi, Wouter Bulten, John-Melle Bokhorst, Francesco Ciompi, and Jeroen Van Der Laak.  Quantifying the effects of data augmentation and stain color normalization in convolutional neural networks for computational pathology.  _Medical image analysis_ , 58:101544, 2019.
  * Varoquaux & Cheplygina (2021) Gaël Varoquaux and Veronika Cheplygina.  How i failed machine learning in medical imaging–shortcomings and recommendations.  _arXiv preprint arXiv:2103.10292_ , 2021.
  * Veeling et al. (2018) Bastiaan S Veeling, Jasper Linmans, Jim Winkens, Taco Cohen, and Max Welling.  Rotation equivariant cnns for digital pathology.  In _International Conference on Medical image computing and computer-assisted intervention_ , pp. 210–218. Springer, 2018.
  * Waters & Der (2018) Andrew M Waters and Channing J Der.  Kras: the critical driver and therapeutic target for pancreatic cancer.  _Cold Spring Harbor perspectives in medicine_ , 8(9):a031435, 2018.
  * Yagi (2011) Yukako Yagi.  Color standardization and optimization in whole slide imaging.  In _Diagnostic pathology_ , volume 6, pp. 1–12. Springer, 2011\.
  * Yu & Eng (2020) Alice C Yu and John Eng.  One algorithm may not fit all: how selection bias affects machine learning performance.  _Radiographics_ , 40(7):1932–1937, 2020.
  * Zech et al. (2018) John R Zech, Marcus A Badgeley, Manway Liu, Anthony B Costa, Joseph J Titano, and Eric Karl Oermann.  Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: a cross-sectional study.  _PLoS medicine_ , 15(11):e1002683, 2018.


0.9 10cm 5 PREPRINT

11institutetext: AGH University of Science and Technology, Kraków, Poland
11email<EMAIL_ADDRESS>
# Strengthening structural baselines for graph classification using Local
Topological Profile

Jakub Adamczyk  0000-0003-4336-4288 Wojciech Czech  0000-0002-1903-8098

###### Abstract

We present the analysis of the topological graph descriptor Local Degree
Profile (LDP), which forms a widely used structural baseline for graph
classification. Our study focuses on model evaluation in the context of the
recently developed fair evaluation framework, which defines rigorous routines
for model selection and evaluation for graph classification, ensuring
reproducibility and comparability of the results. Based on the obtained
insights, we propose a new baseline algorithm called Local Topological Profile
(LTP), which extends LDP by using additional centrality measures and local
vertex descriptors. The new approach provides the results outperforming or
very close to the latest GNNs for all datasets used. Specifically, state-of-
the-art results were obtained for 4 out of 9 benchmark datasets. We also
consider computational aspects of LDP-based feature extraction and model
construction to propose practical improvements affecting execution speed and
scalability. This allows for handling modern, large datasets and extends the
portfolio of benchmarks used in graph representation learning. As the outcome
of our work, we obtained LTP as a simple to understand, fast and scalable,
still robust baseline, capable of outcompeting modern graph classification
models such as Graph Isomorphism Network (GIN). We provide open-source
implementation at GitHub.

###### Keywords:

Graph representation learning Graph classification Fair evaluation Graph
descriptors Baseline models.

##  1 Introduction

Graph classification is an essential variant of supervised learning problems,
gaining popularity in many scientific fields due to the growing volume of
structured datasets, which encode pairwise relations between modeled objects
of different types. The applications of graph classification algorithms range
from cheminformatics [11], where high-level properties of molecules such as
toxicity or mutagenicity are predicted, to sociometry [29], biology [32] and
technology [16], tackling different classes of complex networks, whose non-
trivial dynamics can be explained by learning structural patterns.

Graph classification poses the inherent problem of measuring the dissimilarity
between objects which do not lie in metric space but have combinatorial
nature. This challenge is typically addressed by extracting isomorphism-
invariant representations in the form of feature vectors [33] (also called
graph embeddings, descriptors, fingerprints) or by constructing explicit
pairwise similarity measures known as graph kernels [13]. More recently, the
graph embedding problem was successfully reformulated within the framework of
deep convolutional neural networks. Adopting the concept of convolution to
vertex neighborhoods by introducing hierarchical iterative operators on
multidimensional states of vertices allowed for building task-specific, low-
dimensional representations for vertices, edges, and, after global pooling,
the whole graph [27].

Baselines are the crucial elements of the fair comparison frameworks used in
machine learning. As deep learning methods become increasingly powerful, the
baseline algorithms used for their evaluation should also provide competitive
results, forming good reference points for analyzing algorithms’ performance.
The recent development of Graph Neural Networks (GNNs), which automatically
extract task-relevant features via deep learning, increased the number of
attempts to solve various graph classification tasks [31, 34]. Nevertheless,
fair evaluation practices were frequently neglected in reported studies, and
only recently the need for more rigorous model evaluation was highlighted [4].
This increased the demand for more powerful yet simple and fast baseline
methods.

Motivated by recent findings regarding the discriminative power of Local
Degree Profile (LDP) [2], which, together with SVM as the classification
model, were proven to be competitive with the newest GNN models, we study the
robustness and scalability of the new Local Topological Descriptor (LTP) built
using histograms of specific descriptors representing vertex and edge
structural features. We also use Random Forest classifier instead of SVM to
reduce the sensitivity of baseline to hyperparameter tuning [19]. All
experiments are performed in the regime of fair evaluation framework [4] to
ensure replicability and to correct inaccuracies present in some earlier works
(such as reporting accuracy on validation set). We also propose performance
improvements in the implementation of LDP and LTP, resulting in better
scalability and enabling the computation on large and dense social network
benchmarks.

The key contributions of this work are the thorough analysis of the graph
classification baseline composed of LDP and SVM, reporting limitations of this
approach, the proposal of a new topological baseline utilizing Random Forest
and experimental evaluation showing its robustness compared to the state-of-
the-art. In addition, we present a modular software framework for LDP/LTP-
based graph classification together with the associated open-source Python
code shared on GitHub.

##  2 Related works

In the early works related to graph comparison, the concept of graph edit
distance (GED) was introduced [1]. It was based on calculating the optimal
sequence of elementary operations (adding/removing vertex/edge) required to
transform one graph into another. Computational complexity prevented GED
algorithms from being widely used for larger graphs ($>1000$ vertices).
Nevertheless, multiple successful attempts at classifying attributed graphs
were reported based on benchmark dataset [21]. The IAM graph database [21]
formed the first consistent framework for comparing the efficiency of graph
classification algorithms based on GED or graph embedding methods.

Graph embedding forms the comprehensive field of methods and applications
aimed at the generation of multidimensional graph invariants/descriptors,
which can be recognized as graph feature extraction or feature engineering
[33]. Graph descriptors can be assigned to the vertex, the edge, or the graph
itself. Representing a graph as a vector enables using a multitude of
unsupervised and supervised machine learning algorithms suitable for tabular
data. The most popular graph invariants come from the field of complex
networks and spectral graph theory. They are represented by several graph
centrality measures, clustering coefficient, efficiency and permutation
invariants constructed from the eigenpairs of Laplace matrix [26]. Generic-
purpose vertex and edge descriptors can be aggregated to form a high-
dimensional graph representation such as B-matrix [3] or, after including
vertex attributes, even more expressive relation order histograms [15]. Graph
descriptors can be also extracted by mining frequent patterns/subgraphs,
resulting in the topological fingerprint suitable for structural pattern
recognition but also querying graph databases [14]. This approach was further
extended by introducing domain-specific representations such as molecular
fingerprints [22], which are widely used in the prediction of biochemical
properties. As graph embedding algorithm can be adjusted to the domain, graph
type (e.g. attributed vs. non-attributed), or even available computing
resources, the topological descriptors still represent promising are for graph
feature engineering and, as presented in [2], can compete with state-of-the-
art graph representation learning techniques.

The concept of graph substructure mining was generalized in the form of graph
kernels [13], which assess the structural similarity between two graphs by
pairwise comparison of their subcomponents. Most typically, the concept of
R-convolution [10] is applied as a generic purpose convolution framework for
discrete structures. One of the most interesting representatives of this group
are Weisfeiler-Lehman kernels designed for subtrees, edges, shortest paths,
and whole graphs [23]. They utilize the concept of Weisfeiler-Lehman test of
isomorphism, which was also used in the construction of Graph Isomorphism
Networks (GIN). Another family of graph kernels uses the concept of optimal
assignment [6] to reduce the number of pairwise sub-kernel computations
required to obtain a similarity value. In this work, we focus on explicit
graph embedding and graph representation learning, skipping graph kernels as a
less feasible solution for scalable graph classification.

In case of graph embedding and graph kernels, the domain-specific knowledge
can be incorporated by designing specific substructure descriptors with the
help of experts. Such an approach can be treated as an example of feature
engineering. The different method, providing automatic, task-specific graph
feature extraction, is represented by Graph Representation Learning models
exemplified by Graph Neural Networks (GNNs). They form a modern and
extensively studied framework for graph classification, with dozens of
available models and specific taxonomy [18]. Graph Isomorphism Networks (GIN)
[28] were designed to be as powerful as Weisfeiler-Lehman isomorphism test in
discriminating graphs. They were reported to achieve state-of-the-art results
on graph classification benchmarks; therefore, they will be used as the main
reference point for evaluating our method. GraphSAGE [9] is a general
inductive framework for different convolutional GNNs, providing a new
neighborhood sampling method, which ensures fixed-size aggregation sets to
limit computational overhead related to processing hubs, present, e.g., in
social networks. The aggregation function for node states can be treated as a
hyperparameter and tuned on the validation set. The newer DiffPool model [30]
generates hierarchical graph representations using a differentiable graph
pooling layer. It assigns nodes to clusters to achieve coarse-graining of
input for the next layer, which reduces computation time. Edge-Conditioned
Convolution (ECC) model [24] introduces convolutions over local graph
neighborhoods using edge labels and custom coarsening procedure subsampling
vertices on pooling layers to reduce graph size. The high classification
accuracy was achieved by ECC on molecular datasets. Also, Deep Graph
Convolutional Neural Network (DGCNN) model [31] proposes custom localized
graph convolution similar to spectral filters and related to Weisfeiler-Lehman
subtree kernel. Additionally, the new SortPooling layer is introduced,
enabling standard neural network training on graphs. All models mentioned in
this paragraph will be used in the evaluation of the new LTP baseline.

##  3 Methods

Graph classification tasks can be organized into well-defined pipeline. First,
the graph is typically represented as a sparse adjacency matrix. Optionally,
vertex and edge feature matrices can be used, if they are available. The
matrices provide the input to the feature extraction algorithm, which outputs
a feature vector representing a graph embedding in a metric space. Next, a
tabular classification algorithm is used. For explicit feature extraction
methods, such as LDP or graph kernels, the graph invariants are calculated by
an algorithm distinct from the classifier. This allows using arbitrary
algorithms for both parts. For graph representation learning methods, such as
GNNs, those representations are typically learned end-to-end using a
differentiable framework and gradient-based optimization, with multilayer
perceptron (MLP) as a classifier. This potentially increases flexibility and
makes embeddings more task-related, but requires vastly more data and
computational resources.

Local Degree Profile (LDP) [2] proposes a feature extraction based on vertex
degree statistics, which are calculated for each node in the graph and then
aggregated into the embedding vector. Following conventions from [2], we
denote the graph as $G(V,E)$, where $V$ is the set of vertices (or nodes) $v$
and $E$ is the set of edges $e$. Degrees of neighboring nodes form a multiset
$DN(v)=\\{\text{degree}(v)|(u,v)\in E\\}$. For each node, we then calculate
the following statistics: $\text{degree}(v)$, $\min(DN)$, $\max(DN)$,
$\text{mean}(DN)$, $\text{std}(DN)$. This way, for each node, we obtain the
summary statistics of itself and its 1-hop neighborhood. They are then
aggregated for the whole graph by calculating a histogram or empirical
distribution function (EDF) over each feature. They are concatenated for all
features, forming a final graph embedding. The number of bins used for
aggregation and the choice between histogram and EDF are hyperparameters.
There are also additional hyperparameters reflecting the method of
preprocessing the features before the aggregation. Normalization can be
applied: separately per graph, dividing the degrees by the highest value (this
results in representing the feature value relative to the rest of the graph),
or for the whole dataset, dividing by the highest degree in the dataset. Also,
based on the observation that node degrees follow a power law for social
networks, one can use log scale for aggregating features.

Any additional node- or edge-based structural descriptors can be included in
the LDP in the form of histograms. The authors experiment with multiple ones:
neighbors degree sum, lengths of shortest paths, closeness centrality, Fiedler
vector and Ricci curvature. They remark that only shortest paths gave visible
advantage, but could only be calculated in reasonable time on bioinformatics
datasets, which have small molecular graphs. However, the gains using the
shortest paths are consistent, about 2%, indicating that incorporating edge-
based information can be beneficial. It should be noted that additional
descriptors rapidly increase the dimensionality of the resulting embedding,
which may result in degraded performance due to the curse of dimensionality,
so only a limited number of well-chosen descriptors should be used.

Over the years, a vast number of node and edge descriptors were proposed.
Among them, there are three commonly used groups, describing very different
structural properties of the graph: centrality measures, link prediction
indexes, and sparsification scores. Centrality indicates the importance or the
influence of the node in the graph. Different measures focus on, e.g., how
much information flows though a given node, or how many walks go through that
node. They can also be defined for edges, indicating importance of connections
in the graph. Link prediction indexes describe edges and are used to suggest
the new edges to be added to the graph. They analyze the neighborhoods of the
nodes, assigning high scores to the potential edges between nodes that share a
large portion of their neighbors, or which have neighborhoods leading to
shorter paths between them. Graph sparsification algorithms aim to eliminate
edges, which are the least important for keeping the overall structure of the
graph, especially in relation to hub nodes and communities. They aim to
locally incorporate more global information about graph topology, assigning
higher scores to more important edges.

During preliminary experiments, we surveyed descriptors representing each of
those groups and available in the Networkit [25] library. While almost all
gave promising results, we selected one from each group: edge betweenness
centrality, Jaccard Index and Local Degree Score. The selection was based on
intuitions that those particular descriptors will bring more edge-focused or
more global information than only node degree statistics, enhancing the
discriminative power of the baseline.

Edge betweenness centrality (EBC) [7] is a centrality measure based on
shortest paths, which measures how much influence the edge has over the flow
of information in the network. It is defined as the fraction of the shortest
paths in the graph going through the edge $e=(u,v)$:

$EBC(e)=\sum_{s,t;(s,t)\neq(u,v)}\frac{\sigma_{st}(e)}{\sigma_{st}},$ (1)

where $\sigma_{st}$ is the total number of shortest paths between nodes $s$
and $t$, and $\sigma_{st}(e)$ is the number of those paths that go through
$e$. This can be computed using Floyd-Warshall algorithm, which will give
infinity values for disconnected graphs; we simply omit them in our
implementation. We selected this descriptor, since it is based on shortest
paths, which gave the good results in [2], and also takes into consideration
the cyclic structure of the graph, e.g., it distinguishes molecules with
linear scaffolds vs those with more ring-like topology.

Jaccard Index (JI) [12] is a normalized overlap between node neighborhoods
$N(u)$ and $N(v)$:

$JI(u,v)=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|}$ (2)

We calculate it for the existing edges $e=(u,v)$ in the graph, obtaining a
descriptor of a 3-hop subgraph. This feature should better discriminate
between graph with visible community substructures and those without such node
clusters.

Local Degree Score (LDS) [17] was proposed to detect edges between hubs, i.e.
nodes with locally high degree, and keep only those edges after graph
sparsification. For each node $v$, the rank of its neighbor $u$,
$\text{rank}(v,u)$ is the number of neighbors of $v$ with degree lower than
$u$. Note that this is asymmetrical, i.e.
$\text{rank}(u,v)\neq\text{rank}(v,u)$. For each edge, the Local Degree Score
is defined as:

$LDS(e)=\max\left(1-\frac{\ln\text{rank}(v,u)}{\ln\text{degree}(v)},1-\frac{\ln\text{rank}(u,v)}{\ln\text{degree}(u)}\right),$
(3)

which is simply taking the higher value from perspective of $u$ or $v$, since
either of them can be the hub node, giving a high LDS value. We selected this
feature, since it can indicate the dispersion of nodes in the graph. If there
are few edges with high LDS, it indicates that there are a few well separated
clusters in the graph, centered around hub nodes, e.g., communities or well-
connected functional groups in chemistry.

We propose to use the LDP descriptors together with the additional features
described above, creating the Local Topological Profile. This method
incorporates additional graph topology information in a local fashion,
enhancing LDP with more discriminative power. Of course, this increases the
computational cost, which we discuss below.

LDP authors remark that shortest path lengths are not used for social network
datasets due to unreasonably long computing time. Their implementation,
however, uses NetworkX [8] for computing graph descriptors, which is a Python
library, performing sequential computations. Instead, we propose to use
Networkit [25], a parallelized C++ library. This way, we are able to utilize
modern CPUs with multiple cores and compute descriptors in parallel. We do not
perform a timing comparison, as we also could not finish computation with
NetworkX in any reasonable time. The experiments on subsets of datasets
indicate that Networkit is at least a one or two degrees of magnitude faster
even on much smaller, molecular graphs. For this reason, our whole
implementation of descriptors computation is based on Networkit.

Classification algorithm applied to feature vectors has a direct influence on
both accuracy and scalability. LDP used Support Vector Machine (SVM) with a
Gaussian kernel, which is a powerful classifier traditionally used with graph
kernels, since they work well with small datasets. However, they are not
scalable, since kernel calculation alone takes $O(n^{2})$ for $n$ graphs in
the dataset. Moreover, they are sensitive to hyperparameter choice [19], hence
requiring extensive tuning to obtain good results. In addition, they are
typically trained with the Sequential Minimal Optimization (SMO) algorithm,
which is inherently sequential, not utilizing modern CPUs with multiple cores.
Linear SVMs, while faster to compute, typically give worse results, which the
authors of LDP also observe.

We propose to change SVM to a Random Forest (RF) classifier. It is bagging
ensemble of decision trees, which means that each tree can be trained
independently in parallel, increasing scalability. Decision tree induction is
also very fast, relying on a greedy top-down algorithm. They typically give
good results with default hyperparameters, requiring only a sufficiently high
number of trees [20]. In preliminary study, we did not observe any significant
effect of hyperparameter tuning, even with large hyperparameter grids, hence
we skipped this step.

More importantly, in contrast to LDP [2], we use a fair evaluation protocol
with test sets. We use the fair comparison procedure from [4], adapted in the
following way. The datasets and their statistics are summarized in Table 1. We
use the same test splits, and apply 10-fold CV for testing. However, since our
baseline is fast to compute, we can afford to perform inner 5-fold CV for
validation and hyperparameter tuning, instead of holdout. Following [4], we
report mean and standard deviation of accuracy on test sets.

Table 1: Statistics of datasets used, following [4]. Dataset | # Graphs | Avg. # Nodes | Avg. # Edges | # Classes
---|---|---|---|---
DD | 1178 | 284.32 | 715.66 | 2
NCI1 | 4110 | 29.87 | 32.30 | 2
PROTEINS | 1113 | 39.06 | 72.82 | 2
ENZYMES | 600 | 32.63 | 64.14 | 6
IMDB-B | 1000 | 19.77 | 96.53 | 2
IMDB-M | 1500 | 13.00 | 65.94 | 3
REDDIT-B | 2000 | 429.63 | 497.75 | 2
REDDIT-5K | 4999 | 508.82 | 594.87 | 5
COLLAB | 5000 | 74.49 | 2457.78 | 3

We tune the following hyperparameters for LDP (the same as the authors of
[2]):

  * •

number of bins: [30, 50, 70, 100]

  * •

aggregation: [histogram, EDF]

  * •

normalization: [none, graph, dataset]

  * •

log scale: [false, true]

We tune the following hyperparameters for SVM (the same as authors of [2]):

  * •

C (regularization): [$10^{-3}$, $10^{-2}$, …, $10^{2}$, $10^{3}$]

  * •

$\gamma$ (Gaussian kernel bandwidth): [$10^{-2}$, $10^{-1}$, …, $10^{1}$,
$10^{2}$]

For RF, we do not perform tuning, instead setting the following parameters
(based on Scikit-learn defaults) for dataset with $n$ samples and $d$
features: 500 trees, minimizing Gini impurity, using $\sqrt{d}$ features,
sampling $n$ samples with replacement.

We use PyTorch Geometric [5] for data loading and computing node degree
features, Networkit [25] for computing EBC, JI and LDS descriptors, and
Scikit-learn to implement SVM and RF. We perform all experiments using 12th
Gen Intel Core i7-12700KF 3.61 GHz processor with 32 GB of RAM. Feature
extraction processes graphs sequentially, while feature calculation is done in
parallel, using all available cores. We use all available cores for RF
(`n_jobs=-1`) and for grid search. We performed experiments to answer the
following questions:

  1. 1.

Can we improve training speed and prediction accuracy, using RF instead of
kernel SVM? If so, by how much?

  2. 2.

Is tuning all LDP hyperparameters necessary? Can we eliminate some
hyperparameters, or set reasonable defaults, in order to decrease tuning time?

  3. 3.

Do additional descriptors increase prediction accuracy? Can we use all 3
additional descriptors to get the best average improvement?

  4. 4.

What is the difference in training speed between the original LDP (using SVM
and with hyperparameter tuning) and our proposed LTP (using RF and without
tuning)?

  5. 5.

How does LTP compare against baselines from [4] and GNNs?

##  4 Results and discussion

The first experiment concerned comparison of LDP prediction accuracy when
using RF (without tuning) instead of SVM (with tuning). We include both linear
and kernel SVM results. We used a reasonable default values based on LDP paper
[2]: 50 bins, histogram aggregation, normalization per graph, and linear
scale. As shown in Table 2, RF always gave better results than both linear and
kernel SVM. Interestingly, in some cases linear SVM outperformed kernel SVM,
contradicting findings in [2]. The average improvement of RF over SVMs across
all datasets is 3.4%, but can be as high as 7.3% on ENZYMES or 5.9% on DD.
Additionally, the timings presented in Figure 1 indicate that RF is about an
order of magnitude faster than SVM, being the result of both a more
parallelizable algorithm and no need for hyperparameter tuning. Based on this
finding, we only use RF in further experiments.

Table 2: Classification accuracy on testing sets using LDP features and three
analyzed models. The best result for each dataset is marked in bold.

Dataset Linear SVM Kernel SVM RF DD 68.2 $\pm$ 4.3 68.9 $\pm$ 4.0 74.9 $\pm$
3.4 NCI1 65.8 $\pm$ 2.7 71.5 $\pm$ 2.8 73.8 $\pm$ 2.0 PROTEINS 66.6 $\pm$ 3.2
66.0 $\pm$ 3.3 71.1 $\pm$ 3.1 ENZYMES 25.7 $\pm$ 6.0 29.5 $\pm$ 5.2 36.8 $\pm$
5.8 IMDB-B 60.2 $\pm$ 4.3 64.3 $\pm$ 3.6 65.9 $\pm$ 2.2 IMDB-M 39.6 $\pm$ 3.4
35.3 $\pm$ 2.6 43.9 $\pm$ 2.4 REDDIT-B 78.0 $\pm$ 2.7 88.1 $\pm$ 2.1 89.6
$\pm$ 1.5 REDDIT-5K 46.4 $\pm$ 2.0 52.3 $\pm$ 1.5 52.8 $\pm$ 1.4 COLLAB 68.0
$\pm$ 2.3 71.0 $\pm$ 2.1 73.5 $\pm$ 2.2

Figure 1: Training time using LDP features: SVM vs RF clasifier.

To verify the necessity of tuning LDP hyperparameters, we set the default
values and vary a single hyperparameter at a time. We used 50 bins, histogram
aggregation, normalization per graph, and linear scale. Due to space
constraints, we do not include the whole results tables, but they are
available on GitHub. For each hyperparameter, we calculate the number of times
each value gave the best result. Additionally, for each value, we also
calculate the absolute average difference between its result and the best
result for a given hyperparameter on each dataset. The lower the absolute
difference, the better, since it means that a given hyperparameter value, on
average, gives the best results among all its possible values. results are
presented in Table 3.

For the number of bins, we can clearly select 50 bins as the optimal value.
While 30 bins gave the best results the same number of times, on average they
performed worse compared to the optimal hyperparameter value. Similarly, for
normalization it is evident that we do not need to perform any kind of
normalization, since using no normalization obtained the best results on
majority of datasets and on average. This is somewhat contrary to the results
obtained in LDP paper [2], but it is apparently an advantage of RF, since it
considers each feature separately, while calculating tree splits. For
aggregation method, the results are very close, both for number of wins and
average difference compared to the best result. In this case, the choice does
not matter that much, and we choose the simpler histogram method. The linear
scale obtained much better results on average than the log scale, so the
choice is obvious. Overall, this means that we can confidently recommend
default values for all LDP hyperparameters, and tuning them is not
particularly helpful. This dramatically decreases the computational cost,
while having little effect on accuracy on average, which is a desirable
tradeoff in a baseline method.

Table 3: Number of wins and absolute average difference between the result for
a given hyperparameter value and the best result for any hyperparameter value.
Higher number of wins is better, lower absolute average difference is better.
For each hyperparameter, the value with the lowest absolute average difference
has been marked in bold.

Hyperparameter Value # Wins Abs. avg. difference compared to best Number of
bins 30 4 0.69% 50 4 0.22% 70 1 0.70% 100 0 0.63% Normalization None 5 0.23%
Graph 2 2.03% Dataset 2 0.39% Aggregation Histogram 5 0.71% EDF 4 0.69% Scale
Linear 4 0.35% Log 5 0.64%

To assess whether additional descriptors increase accuracy of this method, we
performed another set of experiments. We start with basic LDP, and add one
additional descriptor at a time: lengths of shortest paths (SP), edge
betweenness centrality (EBC), Jaccard Index (JI) and Local Degree Score (LDS).
Finally, we check our proposed Local Topological Profile (LTP) method,
combining LDP with EBC, JI and LDS descriptors. In all experiments, we keep
the same hyperparameters: 50 bins, histogram aggregation, no normalization,
and linear scale. As shown in Table 4, in every case the additional
descriptors achieved the best result, while LTP was the best on 6 out of 9
datasets. On PROTEINS and IMDB-M it was the second best, being worse than the
best by just $0.1\%$ on the latter. It was also the third best on NCI1.
Therefore, we can conclude that adding selected descriptors definitely
increases the discriminatory power of this method. LTP is a robust method,
performing the best on average, and using it eliminates the need to tune
descriptor selection.

For performance analysis, we compare the original method from [2], i.e., LDP +
SVM + hyperparameter tuning, with the proposed method, i.e. LTP + RF, without
any tuning. For the former, we tune feature extraction hyperparameter and SVM
hyperparameters separately, since grid search on combined parameters grids
would result in approximately 20 times larger number of models to be trained
for a single test fold, which is infeasible. We measure the time for the whole
experimental procedure, i.e. feature extraction and classifier training and
tuning for all 10 test folds. This way, we take all characteristics of both
approaches into consideration: LDP taking more time due to tuning, and LTP due
to extracting more features. As shown in Figure 2, our proposed LTP approach
is vastly superior to LDP in terms of speed, being 1–3 orders of magnitude
faster on all datasets. It should be noted that our LDP implementation is
nevertheless much faster than the original one, since we use PyTorch Geometric
to compute LDP features in parallel with optimized C++ subroutines. The
original Python-based, sequential implementation in NetworkX would be
additionally 1–2 orders of magnitude slower, based on preliminary experiments.
Our method was also very fast on datasets with large number of large graphs
(REDDIT datasets and COLLAB), which indicates good scalability. This is
especially important considering that graph datasets are getting larger and
baselines also have to scale well.

Lastly, we compare accuracy of LTP to GNNs from [4], based on the same fair
evaluation framework (compatible settings for model selection and model
evaluation). For social networks, we compare against stronger models, using
node degree. The outcome is summarized in Table 5. For easier comparison, in
Table 6 we also present the average rank of the model across all datasets,
i.e. on average which place, from 1st to 8th, it took. Our LTP approach
achieves state-of-the-art results on IMDB-B, IMDB-M, REDDIT-B and COLLAB,
achieving as much as 3.8% higher accuracy on COLLAB than the previous best
method, GIN. Note that our method makes use of graph topology exclusively,
ignoring node and edge features. This explains why on bioinformatics datasets
we did not get as good results. In fact, on DD, PROTEINS and ENZYMES the best
result is achieved by exclusively feature-based baseline from [4], which does
not use graph topology at all. On average, LTP obtained the best rank among
all models, beating even a theoretically very powerful GIN architecture.
Additionally, all GNNs require GPUs and many hours of computation, while our
method gives results in mere seconds.

Table 4: Classification accuracy of LDP with additional descriptors and LTP.
The best result for each dataset is marked in bold.

Dataset LDP LDP \+ SP LDP \+ EBC LDP \+ JI LDP \+ LDS LTP DD 76.0 $\pm$ 3.0
76.3 $\pm$ 2.8 77.0 $\pm$ 3.6 76.0 $\pm$ 3.4 75.8 $\pm$ 2.6 77.1 $\pm$ 3.7
NCI1 77.2 $\pm$ 1.5 76.1 $\pm$ 1.6 76.8 $\pm$ 1.7 76.6 $\pm$ 1.4 77.4 $\pm$
1.6 77.0 $\pm$ 1.9 PROTEINS 70.6 $\pm$ 1.7 71.9 $\pm$ 2.2 73.0 $\pm$ 3.2 72.6
$\pm$ 3.2 71.4 $\pm$ 3.0 72.7 $\pm$ 4.2 ENZYMES 37.4 $\pm$ 4.0 37.2 $\pm$ 5.4
40.2 $\pm$ 6.5 40.0 $\pm$ 6.6 38.7 $\pm$ 5.6 42.5 $\pm$ 4.1 IMDB-B 71.3 $\pm$
3.3 72.2 $\pm$ 4.0 72.9 $\pm$ 4.6 73.0 $\pm$ 4.3 74.2 $\pm$ 4.2 74.5 $\pm$ 4.3
IMDB-M 49.0 $\pm$ 4.4 49.2 $\pm$ 4.1 49.2 $\pm$ 5.0 49.3 $\pm$ 4.5 50.1 $\pm$
4.8 50.0 $\pm$ 4.6 REDDIT-B 89.6 $\pm$ 1.2 90.5 $\pm$ 2.1 90.1 $\pm$ 1.7 89.6
$\pm$ 1.3 91.1 $\pm$ 1.1 91.1 $\pm$ 1.0 REDDIT-5K 51.9 $\pm$ 1.6 51.9 $\pm$
1.9 51.7 $\pm$ 1.8 52.7 $\pm$ 2.0 53.1 $\pm$ 1.9 53.3 $\pm$ 1.5 COLLAB 75.7
$\pm$ 2.0 76.5 $\pm$ 2.2 76.8 $\pm$ 1.9 76.8 $\pm$ 1.8 78.7 $\pm$ 2.4 79.4
$\pm$ 2.5

Figure 2: Experiment time using LDP and LTP approaches. Table 5: Comparison of accuracy with fair comparison results from [4]. Higher is better. Best result for each dataset has been marked in bold. Dataset | Baseline [4] | DGCNN | DiffPool | ECC | GIN | GraphSAGE | LDP | LTP
---|---|---|---|---|---|---|---|---
DD |  | 78.4
---
$\pm$4.5
| 76.6
---
$\pm$4.3
| 75.0
---
$\pm$3.5
| 72.6
---
$\pm$4.1
| 75.3
---
$\pm$2.9
| 72.9
---
$\pm$2.0
| 76.0
---
$\pm$3.0
| 77.1
---
$\pm$3.7
NCI1 |  | 69.8
---
$\pm$2.2
| 76.4
---
$\pm$1.7
| 76.9
---
$\pm$1.9
| 76.2
---
$\pm$1.4
| 80.0
---
$\pm$1.4
| 76.0
---
$\pm$1.8
| 77.2
---
$\pm$1.5
| 77.0
---
$\pm$ 1.9
PROTEINS |  | 75.8
---
$\pm$3.7
| 72.9
---
$\pm$3.5
| 73.7
---
$\pm$3.5
| 72.3
---
$\pm$3.4
| 73.3
---
$\pm$4.0
| 73.0
---
$\pm$4.5
| 70.6
---
$\pm$1.7
| 72.7
---
$\pm$4.2
ENZYMES |  | 65.2
---
$\pm$6.4
| 38.9
---
$\pm$5.7
| 59.5
---
$\pm$5.6
| 29.5
---
$\pm$8.2
| 59.6
---
$\pm$4.5
| 58.2
---
$\pm$6.0
| 37.4
---
$\pm$4.0
| 42.5
---
$\pm$4.1
IMDB-B |  | 70.8
---
$\pm$5.0
| 69.2
---
$\pm$3.0
| 68.4
---
$\pm$3.3
| 67.7
---
$\pm$2.8
| 71.2
---
$\pm$3.9
| 68.8
---
$\pm$4.5
| 71.3
---
$\pm$3.3
| 74.5
---
$\pm$4.3
IMDB-M |  | 49.1
---
$\pm$3.5
| 45.6
---
$\pm$3.4
| 45.6
---
$\pm$3.4
| 43.5
---
$\pm$3.1
| 48.5
---
$\pm$3.3
| 47.6
---
$\pm$3.5
| 49.0
---
$\pm$4.4
| 50.0
---
$\pm$4.6
REDDIT-B |  | 82.2
---
$\pm$3.0
| 87.8
---
$\pm$2.5
| 89.1
---
$\pm$1.6
OOR |  | 89.9
---
$\pm$1.9
| 84.3
---
$\pm$1.9
| 89.6
---
$\pm$1.2
| 91.1
---
$\pm$1.0
REDDIT-5K |  | 52.2
---
$\pm$1.5
| 49.2
---
$\pm$1.2
| 53.8
---
$\pm$1.4
OOR |  | 56.1
---
$\pm$1.7
| 50.0
---
$\pm$1.3
| 51.9
---
$\pm$1.6
| 53.3
---
$\pm$1.5
COLLAB |  | 70.2
---
$\pm$1.5
| 71.2
---
$\pm$1.9
| 68.9
---
$\pm$2.0
OOR |  | 75.6
---
$\pm$2.3
| 73.9
---
$\pm$1.7
| 75.7
---
$\pm$2.0
| 79.4
---
$\pm$2.5
Table 6: Comparison of average model ranks. The best result is marked in bold. | Baseline [4] | DGCNN | DiffPool | ECC | GIN | GraphSAGE | LDP | LTP
---|---|---|---|---|---|---|---|---
| Average
---
rank
3.8 | 5.2 | 4.6 | 7.6 | 2.7 | 5.4 | 4 | 2.6

##  5 Conclusions

We presented the new structural baseline for graph classification called Local
Topological Profile (LTP). The research questions addressing its efficiency
and scalability in comparison to related LDP method and competitive GNN
methods were studied in the experimental section, where we conclude that using
the Random Forest classifier instead of SVM improved the accuracy and the
speed of computation by a large margin and this observation applies to all
datasets used. We note that tuning of feature extraction hyperparameters is
not necessary therefore, we can use default values for all datasets,
decreasing tuning time significantly. More importantly, we observe that
introducing additional topological descriptors increases predictive accuracy
in LTP method significantly. Using all three proposed descriptors (Edge
Betweenness Centrality, Jaccard Index, Local Degree Score) gives very good
prediction results across nine benchmark datasets, at the same time LTP is 2–3
orders of magnitude faster than the original LDP approach. Finally, we achieve
state-of-the-art results on 4 out of 9 benchmark datasets, and in other cases
get very strong accuracy, comparable to or even outcompeting modern GNNs,
while using exclusively the graph topology. We share the software package with
the research community, hoping that it can be useful in comparing results
achieved by state-of-the-art graph classification models.

In our future work, we plan to extend the number of vertex/edge descriptors
and enrich the expressive power of LTP towards more global features such as
eccentricity. We also plan to merge LTP feature extraction and baselines from
[4], to strengthen performance on more feature-focused bioinformatics
datasets.

###  5.0.1 Acknowledgements

The research presented in this paper was financed from the funds assigned by
Polish Ministry of Science and Higher Education to AGH University of Science
and Technology. We would like to thank Alexandra Elbakyan for her work and
support for accessibility of science.

## References

  * [1] Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern recognition letters 18(8), 689–694 (1997)
  * [2] Cai, C., Wang, Y.: A simple yet effective baseline for non-attributed graph classification. arXiv preprint arXiv:1811.03508 (2018)
  * [3] Czech, W.: Invariants of distance k-graphs for graph embedding. Pattern Recognition Letters 33(15), 1968–1979 (2012)
  * [4] Errica, F., Podda, M., Bacciu, D., Micheli, A.: A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:1912.09893 (2019)
  * [5] Fey, M., Lenssen, J.E.: Fast graph representation learning with PyTorch Geometric. In: ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)
  * [6] Fröhlich, H., Wegner, J.K., Sieker, F., Zell, A.: Optimal assignment kernels for attributed molecular graphs. In: Proceedings of the 22nd international conference on Machine learning. pp. 225–232 (2005)
  * [7] Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proceedings of the national academy of sciences 99(12), 7821–7826 (2002)
  * [8] Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using networkx. Tech. rep., Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008)
  * [9] Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)
  * [10] Haussler, D., et al.: Convolution kernels on discrete structures. Tech. rep., Citeseer (1999)
  * [11] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., Leskovec, J.: Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33, 22118–22133 (2020)
  * [12] Jaccard, P.: The distribution of the flora in the alpine zone. 1. New phytologist 11(2), 37–50 (1912)
  * [13] Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Applied Network Science 5(1), 1–42 (2020)
  * [14] Kuramochi, M., Karypis, G.: An efficient algorithm for discovering frequent subgraphs. IEEE transactions on Knowledge and Data Engineering 16(9), 1038–1051 (2004)
  * [15] Łazarz, R., Idzik, M.: Relation order histograms as a network embedding tool. In: Computational Science–ICCS 2021: 21st International Conference, Krakow, Poland, June 16–18, 2021, Proceedings, Part II 21. pp. 224–237. Springer (2021)
  * [16] Li, Y., Gu, C., Dullien, T., Vinyals, O., Kohli, P.: Graph matching networks for learning the similarity of graph structured objects. In: International conference on machine learning. pp. 3835–3845. PMLR (2019)
  * [17] Lindner, G., Staudt, C.L., Hamann, M., Meyerhenke, H., Wagner, D.: Structure-preserving sparsification of social networks. In: Proceedings of the 2015 IEEE/ACM International conference on advances in social networks analysis and mining 2015. pp. 448–454 (2015)
  * [18] Liu, R., Cantürk, S., Wenkel, F., Sandfelder, D., Kreuzer, D., Little, A., McGuire, S., O’Bray, L., Perlmutter, M., Rieck, B., et al.: Taxonomy of benchmarks in graph representation learning. arXiv preprint arXiv:2206.07729 (2022)
  * [19] Probst, P., Boulesteix, A.L., Bischl, B.: Tunability: Importance of hyperparameters of machine learning algorithms. The Journal of Machine Learning Research 20(1), 1934–1965 (2019)
  * [20] Probst, P., Wright, M.N., Boulesteix, A.L.: Hyperparameters and tuning strategies for random forest. Wiley Interdisciplinary Reviews: data mining and knowledge discovery 9(3), e1301 (2019)
  * [21] Riesen, K., Bunke, H., et al.: Iam graph database repository for graph based pattern recognition and machine learning. In: SSPR/SPR. vol. 5342, pp. 287–297 (2008)
  * [22] Rogers, D., Hahn, M.: Extended-connectivity fingerprints. Journal of chemical information and modeling 50(5), 742–754 (2010)
  * [23] Shervashidze, N., Schweitzer, P., Van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12(9) (2011)
  * [24] Simonovsky, M., Komodakis, N.: Dynamic edge-conditioned filters in convolutional neural networks on graphs. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 3693–3702 (2017)
  * [25] Staudt, C.L., Sazonovs, A., Meyerhenke, H.: Networkit: A tool suite for large-scale complex network analysis. Network Science 4(4), 508–530 (2016)
  * [26] Wilson, R.C., Hancock, E.R., Luo, B.: Pattern vectors from algebraic graph theory. IEEE transactions on pattern analysis and machine intelligence 27(7), 1112–1124 (2005)
  * [27] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems 32(1), 4–24 (2020)
  * [28] Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018)
  * [29] Yanardag, P., Vishwanathan, S.: Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. pp. 1365–1374 (2015)
  * [30] Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems 31 (2018)
  * [31] Zhang, M., Cui, Z., Neumann, M., Chen, Y.: An end-to-end deep learning architecture for graph classification. In: Proceedings of the AAAI conference on artificial intelligence. vol. 32 (2018)
  * [32] Zhang, X.M., Liang, L., Liu, L., Tang, M.J.: Graph neural networks and their current applications in bioinformatics. Frontiers in genetics 12, 690049 (2021)
  * [33] Zhang, Y.J., Yang, K.C., Radicchi, F.: Systematic comparison of graph embedding methods in practical tasks. Physical Review E 104(4), 044315 (2021)
  * [34] Zhou, Y., Zheng, H., Huang, X., Hao, S., Li, D., Zhao, J.: Graph neural networks: Taxonomy, advances, and trends. ACM Transactions on Intelligent Systems and Technology (TIST) 13(1), 1–54 (2022)