11institutetext: Institute for AI in Medicine and Healthcare, Faculty of
Informatics, Technical University of Munich 22institutetext: Department of
Diagnostic and Interventional Radiology, Faculty of Medicine, Technical
University of Munich 33institutetext: BioMedIA, Department of Computing,
Imperial College London 44institutetext: Institute for Machine Learning in
Biomedical Imaging, Helmholtz-Zentrum Munich
44email<EMAIL_ADDRESS>
# Extended Graph Assessment Metrics for Regression and Weighted Graphs

Tamara T. Mueller 11 Sophie Starck 11 Leonhard F. Feiner 1122 Kyriaki-
Margarita Bintsi 33 Daniel Rueckert 1133 Georgios Kaissis 112244

###### Abstract

When re-structuring patient cohorts into so-called population graphs,
initially independent patients can be incorporated into one interconnected
graph structure. This population graph can then be used for medical downstream
tasks using graph neural networks (GNNs). The construction of a suitable graph
structure is a challenging step in the learning pipeline that can have severe
impact on model performance. To this end, different graph assessment metrics
have been introduced to evaluate graph structures. However, these metrics are
limited to classification tasks and discrete adjacency matrices, only covering
a small subset of real-world applications. In this work, we introduce extended
graph assessment metrics (GAMs) for regression tasks and weighted graphs. We
focus on two GAMs in specific: homophily and cross-class neighbourhood
similarity (CCNS). We extend the notion of GAMs to more than one hop, define
homophily for regression tasks, as well as continuous adjacency matrices, and
propose a light-weight CCNS distance for discrete and continuous adjacency
matrices. We show the correlation of these metrics with model performance on
different medical population graphs and under different learning settings,
using the TADPOLE and UKBB datasets.

##  1 Introduction

The performance of graph neural networks can be highly dependent on the graph
structure they are trained on [16, 15]. To this end, several graph assessment
metrics (GAMs) have been introduced to evaluate graph structures and shown
strong correlations between specific graph structures and the performance of
graph neural networks (GNNs) [14, 16, 15]. Especially in settings, where the
graph structure is not provided by the dataset but needs to be constructed
from the data, GAMs are the only way to assess the quality of the constructed
graph. This is for example the case when utilising so-called population graphs
on medical datasets. Recent works have furthermore shown that learning the
graph structure in an end-to-end manner, can improve performance on population
graphs [9]. Some of these methods that learn the graph structure during model
training operate with fully connected, weighted graphs, where all nodes are
connected with each other and the tightness of the connection is determined by
a learnable edge weight. This leads to a different representation of the
graph, which does not fit the to-date formulations of GAMs. Furthermore,
existing metrics are tailored to classification tasks and cannot be easily
transformed for equally important regression tasks. The contributions of this
work are the following: (1) We extend existing metrics to allow for an
assessment of multi-hop neighbourhoods. (2) We introduce an extension of the
homophily metric for regression tasks and continuous adjacency matrices and
(3) define a cross-class neighbourhood similarity (CCNS) distance metric and
extend CCNS to learning tasks that operate on continuous adjacency matrices.
Finally, (4) we show these metrics’ correlation to model performance on
different medical and synthetic datasets. The metrics introduced in this work
can find versatile applications in the area of graph deep learning in medical
and non-medical settings, since they strongly correlate with model performance
and give insights into the graph structure in various learning settings.

##  2 Background and Related Work

###  2.1 Definition of graphs

A discrete graph $\mathit{G}:=(\mathit{V},\mathit{E})$ is defined by a set of
$n$ nodes $\mathit{V}$ and a set of edges $\mathit{E}$, connecting pairs of
nodes. The edges are unweighted and can be represented by an adjacency matrix
$\mathbf{A}$ of shape $n\times n$, where $\mathbf{A}_{ij}=1$ if and only if
$e_{ij}\in\mathit{E}$ and $0$ otherwise. A continuous/weighted graph
$\mathit{G}_{w}:=(\mathit{V}_{w},\mathit{E}_{w},\mathbf{W})$, assigns a
(continuous) weight to every edge in $\mathit{E}_{w}$, summarised in the
weight matrix $\mathbf{W}$. Continuous graphs are for example required in
cases where the adjacency matrix is learned in an end-to-end manner and
backpropagation through the adjacency matrix needs to be feasible. A
neighbourhood $\mathcal{N}_{v}$ of a node $v$ contains all direct neighbours
of $v$ and can be extended to $k$ hops by $\mathcal{N}^{(k)}_{v}$. For this
work, we assume familiarity with GNNs [3].

###  2.2 Homophily

Homophily is a frequently used metric to assess a graph structure that is
correlated to GNN performance [15]. It quantifies how many neighbouring nodes
share the same label [15] as the node of interest. There exist three different
notions of homophily: edge homophily [10], node homophily [19], and class
homophily [12, 15]. Throughout this work, we use node homophily, sometimes
omitting the term node, only referring to homophily.

######  Definition 1 (Node homophily)

Let $\mathit{G}:=(\mathit{V},\mathit{E})$ be a graph with a set of node labels
$\mathit{Y}:=\\{y_{u};u\in\mathit{V}\\}$ and $\mathcal{N}_{v}$ be the set of
neighbouring nodes to node $v$. Then $\mathit{G}$ has the following node
homophily:

$h(\mathit{G},\mathit{Y}):=\frac{1}{|\mathit{V}|}\sum_{v\in\mathit{V}}\frac{\left|\\{u|u\in\mathcal{N}_{v},Y_{u}=Y_{v}\\}\right|}{|\mathcal{N}_{v}|},$
(1)

where $|\cdot|$ indicates the cardinality of a set.

A graph $G$ with node labels $Y$ is called homophilous/homophilic when
$h(G,Y)$ is large (typically larger than 0.5) and heterophilous/heterophilic
otherwise [10].

###  2.3 Cross-class neighbourhood similarity

Ma et al. [16] introduce a metric to assess the graph structure for graph deep
learning, called cross-class neighbourhood similarity (CCNS). This metric
indicates how similar the neighbourhoods of nodes with the same labels are
over the whole graph – irrespective of the labels of the neighbouring nodes.

######  Definition 2 (Cross-class neighbourhood similarity)

Let $\mathit{G}=(\mathit{V},\mathit{E})$, $\mathcal{N}_{v}$, and $Y$ be
defined as above. Let $C$ be the set of node label classes, and
$\mathcal{V}_{c}$ the set of nodes of class $c$. Then the CCNS of two classes
$c$ and $c^{\prime}$ is defined as follows:

$\operatorname{CCNS}(c,c^{\prime})=\frac{1}{|\mathcal{V}_{c}||\mathcal{V}_{c^{\prime}}|}\sum_{u\in\mathcal{V},v\in\mathcal{V^{\prime}}}{\operatorname{cossim}(d(u),d(v))}.$
(2)

$d(v)$ is the histogram of a node $v$’s neighbours’ labels and
$\operatorname{cossim}(\cdot,\cdot)$ the cosine similarity.

##  3 Extended Graph Metrics

In this section, we introduce our main contributions by defining new extended
GAMs for regression tasks and continuous adjacency matrices. We propose (1) a
unidimensional version of CCNS which we call CCNS distance, which is easier to
evaluate than the whole original CCNS matrix, (2) an extension of existing
metrics to $k$-hops, (3) GAMs for continuous adjacency matrices, and (4)
homophily for regression tasks.

###  3.1 CCNS distance

The CCNS of a dataset with $n$ classes is an $n\times n$ matrix, which can be
large and cumbersome to evaluate. The most desirable CCNS for graph learning
has high intra-class and low inter-class values, indicating similar
neighbourhoods for the same class and different neighbourhoods between
classes. We propose to collapse the CCNS matrix into a single value by
evaluating the $L_{1}$ distance between the CCNS and the identity matrix,
which we term CCNS distance.

######  Definition 3 (CCNS distance)

Let $\mathit{G}=(\mathit{V},\mathit{E})$, $C$, CCNS be defined as above. Then
the CCNS distance of $\mathit{G}$ is defined as follows:

$D_{\operatorname{CCNS}}:=\frac{1}{n}\sum{\lVert\operatorname{CCNS}-\mathbb{I}\rVert_{1}},$
(3)

where $\mathbb{I}$ indicates the identity matrix and $\lVert\cdot\rVert_{1}$
the $L_{1}$ norm.

We note that the CCNS distance is best at low values and that we do not define
CCNS for regression tasks, since it requires the existence of class labels.

###  3.2 $K$-hop metrics

Most GAMs only evaluate direct neighbourhoods. However, GNNs can apply the
message passing scheme to more hops, including more hops in the node feature
embedding. We therefore propose to extend homophily and CCNS on unweighted
graphs to $k$-hop neighbourhoods. An extension of the metrics on weighted
graphs is more challenging, since the edge weights impact the $k$-hop metrics.
The formal definitions for $k$-hop homophily and CCNS for unweighted graphs
can be found in the Appendix. We here exchange the notion of $\mathcal{N}_{v}$
with the specific $k$-hop neighbourhood $\mathcal{N}^{(k)}_{v}$ of interest.

###  3.3 Metrics for continuous adjacency matrices

Several graph learning settings, such as [6, 9], utilise a continuous graph
structure. In order to allow for an evaluation of those graphs, we here define
GAMs on the weight matrix $\mathbf{W}$ instead of the binary adjacency matrix
$\mathbf{A}$.

######  Definition 4 (Homophily for continuous adjacency matrices)

Let $\mathit{G}_{w}=(\mathit{V}_{w},\mathit{E}_{w},\mathbf{W})$, be a weighted
graph defined as above with a continuous adjacency matrix. Then the $1$-hop
node homophily of $\mathit{G}_{w}$ is defined as follows:

$\operatorname{HCont}(G_{w},Y):=\frac{1}{|V|}\sum_{v\in
V}{\left(\frac{\sum_{u\in\mathcal{N}_{v}|y_{u}=y_{v}}{w_{uv}}}{\sum_{u\in\mathcal{N}_{v}}{w_{uv}}}\right)},$
(4)

where $w_{uv}$ is the weight of the edge from $u$ to $v$.

######  Definition 5 (CCNS for continuous adjacency matrices)

Let $\mathit{G}_{w}=(\mathit{V}_{w},\mathit{E}_{w},\mathbf{W})$, $C$,
$cossim(\cdot,\cdot)$ be defined as above. Then, the CCNS for weighted graphs
is defined as follows:

$\operatorname{CCNS}_{cont}(c,c^{\prime}):=\frac{1}{|\mathcal{V}_{c}||\mathcal{V}_{c^{\prime}}|}\sum_{u\in\mathcal{V},v\in\mathcal{V^{\prime}}}{\operatorname{cossim}(d_{c}(u),d_{c}(v))},$
(5)

where $d_{c}(u)$ is the histogram considering the edge weights of the
continuous adjacency matrix of the respective classes instead of the count of
neighbours. The CCNS distance for continuous adjacency matrices can be
evaluated as above.

###  3.4 Homophily for regression

Homophily is only defined for node classification tasks, which strictly limits
its application to a subset of use cases. However, many relevant graph
learning tasks perform a downstream node regression, such as age regression
[21, 2]. We here define homophily for node regression tasks. Since homophily
is a metric ranging from $0$ to $1$, we contain this range for regression
tasks by normalising the labels between $0$ and $1$ prior to metric
evaluation. We subtract the average node label distance from $1$ to ensure the
same range as homophily for classification.

######  Definition 6 (Homophily for regression)

Let $\mathit{G}=(\mathit{V},\mathit{E})$ and $\mathcal{N}^{k}_{v}$ be defined
as above and $Y$ be the vector of node labels, which is normalised between $0$
and $1$. Then the $k$-hop homophily for regression is defined as follows:

$\operatorname{HReg}^{(k)}(G,Y):=1-\left(\frac{1}{|V|}\sum_{v\in
V}\left({\frac{1}{|\mathcal{N}^{(k)}_{v}|}\sum_{n\in\mathcal{N}^{(k)}_{v}}{\left\lVert
y_{v}-y_{n}\right\rVert_{1}}}\right)\right),$ (6)

where $\lVert\cdot\rVert_{1}$ indicates the $L_{1}$ norm.

######  Definition 7 (Homophily for continuous adjacency matrices for
regression)

Let $\mathit{G}_{w}=(\mathit{V}_{w},\mathit{E}_{w},\mathbf{W})$, Y, and
$\mathit{N}_{v}$ be defined as above and the task be a regression task, then
the homophily of $\mathit{G}$ is defined as follows:

$\operatorname{HReg}(G,Y):=1-\left(\frac{1}{|V|}\sum_{v\in
V}\left(\frac{\sum_{n\in\mathcal{N}_{v}}{w_{nv}\left\lVert
y_{v}-y_{n}\right\rVert_{1}}}{\sum_{n\in\mathcal{N}_{v}}{w_{nv}}}\right)\right),$
(7)

where $w_{nv}$ is the weight of the edge from $n$ to $v$ and
$\lVert\cdot\rVert_{1}$ the $L_{1}$ norm.

###  3.5 Metric evaluation

In general, we recommend the evaluation of GAMs separately on the train,
validation, and test set. We believe this to be an important evaluation step
since the metrics can differ significantly between the different sub-graphs,
given that the graph structure in only optimised on the training set.

##  4 Experiments and Results

We evaluate our metrics on several datasets with different graph learning
techniques: We (1) assess benchmark classification datasets using a standard
learning pipeline, and (2) medical population graphs for regression and
classification that learn the adjacency matrix end-to-end. All experiments are
performed in a transductive learning setting using graph convolutional
networks (GCNs) [11]. In order to evaluate all introduced GAMs, we
specifically perform experiments on two task settings: classification and
regression, and under two graph learning settings: one using a discrete
adjacency matrix and one using a continuous one.

###  4.1 Datasets

In order to evaluate the above defined GAMs, we perform node-level prediction
experiments with GNNs on different datasets. We evaluate $\\{1,2,3\\}$-hop
homophily and CCNS distance on the benchmark citation datasets Cora, CiteSeer,
and PubMed [24], Computers and Photos, and Coauthors CS datasets [20]. All of
these datasets are classification tasks. We use $k$-layer GCNs and compare
performance to a multi-layer perceptron (MLP).

Furthermore, we evaluate the introduced metrics on two different medical
population graph datasets, as well as two synthetic datasets. The baseline
results for these datasets can be found in Appendix Table 4. We generate
synthetic datasets for classification and regression to analyse the metrics in
a controllable setting. As a real-world medical classification dataset, we use
TADPOLE [17], a neur-imaging dataset which has been frequently used for graph
learning on population graphs [18, 6, 9]. For a regression population graph,
we perform brain age prediction on $6\,406$ subjects of the UK BioBank [22]
(UKBB). We use $22$ clinical and $68$ imaging features extracted from the
subjects’ magnetic resonance imaging (MRI) brain scans, following the approach
in [5]. In both medical population graphs, each subject is represented by one
node and similar subjects are either connected following the $k$-nearest
neighbours approach, like in [9] or starting without any edges.

###  4.2 GNN Training

Prior to this work, the homophily metric has only existed for an evaluation on
discrete adjacency matrices. In this work, we extend this metric to continuous
adjacency matrices. In order to evaluate the metrics for both, discrete and
continuous adjacency matrices, we use two different graph learning methods:
(a) dDGM and (b) cDGM from [9]. DGM stands for differentiable graph module,
referring to the fact that both methods learn the adjacency matrix in an end-
to-end manner. cDGM hereby uses a continuous adjacency matrix, allowing us to
evaluate the metrics introduced specifically for this setting. dDGM uses a
discrete adjacency matrix by sampling the edges using the Gumbel-Top-K trick
[8]. Both methods are similar in terms of model training and performance,
allowing us to compare the newly introduced metrics to the existing homophily
metric in the dDGM setting.

###  4.3 Results

####  4.3.1 (1) Benchmark classification datasets

The results on the benchmark datasets are summarised in Table 1. We can see
that the $k$-hop metric values can differ greatly between the different hops
for some datasets, while staying more constant for others. This gives an
interesting insight into the graph structure over several hops. We believe an
evaluation of neighbourhoods in graph learning to be more insightful if the
number of hops in the GNN matches the number of hops considered in the graph
metric. Interestingly, performance of $k$-hop GCNs did not align with the
$k$-hop metric values on the specific datasets. We summarise these results in
Appendix Table 3. One possible reason for this might be that, e.g., the
$3$-hop metrics assess the $1$, $2$, and $3$-hop neighbourhood at once, not
just the outer ring of neighbours. Another reason for this discrepancy might
be that homophily and CCNS do not perfectly predict GNN performance.
Furthermore, different graph convolutions have shown to be affected
differently by low-homophily graphs [25]. We believe this to be an interesting
direction to further investigate GAMs for GNNs.

Table 1: $K$-hop graph metrics of benchmark node classification datasets. Cl.: number of classes, Nodes: number of nodes Dataset | Nodes | Cl. | Node homophily $\uparrow$ |  $D_{\operatorname{CCNS}}$ $\downarrow$
---|---|---|---|---
$1$-hop |  $2$-hop |  $3$-hop |  $1$-hop |  $2$-hop |  $3$-hop
Cora | 1,433 | 7 |  0.825 $\pm$ 0.29 |  0.775 $\pm$ 0.26 |  0.663 $\pm$ 0.29 | 0.075 | 0.138 | 0.229
CiteSeer | 3,703 | 6 |  0.706 $\pm$ 0.40 |  0.754 $\pm$ 0.28 |  0.712 $\pm$ 0.29 | 0.124 | 0.166 | 0.196
PubMed | 19,717 | 3 |  0.792 $\pm$ 0.35 |  0.761 $\pm$ 0.26 |  0.687 $\pm$ 0.26 | 0.173 | 0.281 | 0.363
Computers | 13,752 | 10 |  0.785 $\pm$ 0.26 |  0.569 $\pm$ 0.27 |  0.303 $\pm$ 0.20 | 0.080 | 0.275 | 0.697
Photo | 7,650 | 8 |  0.837 $\pm$ 0.25 |  0.660 $\pm$ 0.30 |  0.447 $\pm$ 0.28 | 0.072 | 0.210 | 0.429
Coauthor CS | $18,333$ | $15$ |  0.832 $\pm$ 0.24 |  0.698 $\pm$ 0.25 |  0.520 $\pm$ 0.25 | 0.043 | 0.110 | 0.237

####  4.3.2 (2) Population graph experiments

Table 2 shows the dDGM and cDGM results of the population graph datasets. We
can see that in some settings, such as the classification tasks on the
synthetic dataset using dDGM, the homophily varies greatly between train and
test set. This can be an indication for over-fitting on the training set,
since the graph structure is optimised for the training nodes only and might
not generalise well to the whole graph.

Figure 1: Development of graph metrics on TADPOLE over training using cDGM; left: train set; right: validation set Figure 2: Development of metrics on UKBB dataset using cDGM on validation set Table 2: cDGM and dDGM results on the population graph datasets. We report the test scores averaged over $5$ random seeds and $1$-hop homophily and CCNS distance of one final model each. We do not report CCNS distance on regression datasets, since it is not defined for regression tasks. Method | Dataset | Task | Test score | 1-hop node homophily $\uparrow$ |  $1$-hop $D_{\operatorname{CCNS}}$ $\downarrow$
---|---|---|---|---|---
train | test | train | test
cDGM | Synthetic 1k | c |  0.7900 $\pm$ 0.08 |  1.0000 $\pm$ 0.00 |  1.0000 $\pm$ 0.00 | 0.0000 | 0.0000
|  | r |  0.0112 $\pm$ 0.01 |  0.9993 $\pm$ 0.00 |  0.9991 $\pm$ 0.00 | - | -
| Synthetic 2k | c |  0.8620 $\pm$ 0.03 |  1.0000 $\pm$ 0.00 |  1.0000 $\pm$ 0.00 | 0.0000 | 0.0000
|  | r |  0.0173 $\pm$ 0.00 |  0.8787 $\pm$ 0.06 |  0.8828 $\pm$ 0.05 | - | -
| Tadpole | c |  0.9333 $\pm$ 0.01 |  1.0000 $\pm$ 0.00 |  0.9781 $\pm$ 0.09 | 0.0000 | 0.0314
| UKBB | r |  4.0775 $\pm$ 0.23 |  0.8310 $\pm$ 0.06 |  0.8306 $\pm$ 0.07 | - | -
dDGM | Synthetic 1k | c |  0.8080 $\pm$ 0.04 |  0.6250 $\pm$ 0.42 |  0.1150 $\pm$ 0.32 | 0.4483 | 0.4577
|  | r |  $0.0262$ $\pm$ $0.00$ |  0.7865 $\pm$ 016 |  0.8472 $\pm$ 0.15 | - | -
| Synthetic 2k | c |  0.7170 $\pm$ 0.06 |  0.6884 $\pm$ 0.40 |  0.0950 $\pm$ 0.29 | 0.4115 | 0.4171
|  | r |  0.0119 $\pm$ 0.00 |  0.8347 $\pm$ 0.13 |  0.8295 $\pm$ 0.13 | - | -
| Tadpole | c |  0.9614 $\pm$ 0.01 |  0.9297 $\pm$ 0.18 |  0.8801 $\pm$ 0.31 | 0.1045 | 0.0546
| UKBB | r |  3.9067 $\pm$ 0.04 |  0.8941 $\pm$ 0.13 |  0.9114 $\pm$ 0.12 | - | -

Since we here use graph learning methods which adapt the graph structure
during model training, also the graph metrics change over training. Figure 1
shows the development of the accuracy as well as the mean and standard
deviation of the $1$-hop homophily and CCNS distance, evaluated on the train
(left) and validation set (right). We can see that for both sets, the
homophily increases with the accuracy, while the standard deviation (STD) of
the homophily decreases and the CCNS distance decreases with increasing
performance. However, the GAMs align more accurately with the training
accuracy (left), showing that the method optimised the graph structure on the
training set. The validation accuracy does not improve much in this example,
while the validation GAMs still converge similarily to the ones evaluated on
the train set (left). Figure 2 shows the mean (left) and STD (right) of the
validation regression homophily $\operatorname{HReg}$ on the UKBB dataset with
continuous adjacency matrices (using cDGM) and the corresponding change in
validation mean absolute error (MAE). Again, homophily raises when the
validation MAE decreases and the STD of the homophily decreases in parallel.
On the left, the dotted grey line indicates the MAE of a mean prediction on
the dataset. We can see that the mean regression homophily
$\operatorname{HReg}$ raises once the validation MAE drops below the error of
a mean prediction. We here only visualise a subset of all performed
experiments, but we observe the same trends for all settings. From these
experiments we conclude that the here introduced GAMs show strong correlation
with model performance and can be used to assess generated graph structures
that are used for graph deep learning.

##  5 Conclusion and Future Work

In this work, we extended two frequently used graph assessment metrics (GAMs)
for graph deep learning, that allow to evaluate the graph structure in
regression tasks and continuous adjacency matrices. For datasets that do not
come with a pre-defined graph structure, like population graphs, the
assessment of the graph structure is crucial for quality checks on the
learning pipeline. Node homophily and cross-class neighbourhood similarity
(CCNS) are commonly used GAMs that allow to evaluate how similar the
neighbourhoods in a graph are. However, these metrics are only defined for
discrete adjacency matrices and classification tasks. This only covers a small
portion of graph deep learning tasks. Several graph learning tasks target node
regression [21, 2, 1]. Furthermore, recent graph learning methods have shown
that an end-to-end learning of the adjacency matrix is beneficial over
statically creating the graph structure prior to learning [9]. These methods
do not operate on a static binary adjacency matrix, but use weighted
continuous graphs, which is not considered by most current GAMs. In order to
overcome these limitations, we extend the definition of node homophily to
regression tasks and both node homophily and CCNS to continuous adjacency
matrices. We formulate these metrics and evaluate them on different synthetic
and real world medical datasets and show their strong correlation with model
performance. We believe these metrics to be essential tools for investigating
the performance of GNNs, especially in the setting of population graphs or
similar settings that require explicit graph construction.

Our definition of the CCNS distance $D_{\operatorname{CCNS}}$ uses the
$L_{1}$-norm to determine the distance between the node labels in order to
weight each inter-class-connection equally. However, the $L_{1}$-norm is only
one of many norms that could be used here. Given the strong correlation of our
definition of $D_{\operatorname{CCNS}}$, we show the the usage of the
$L_{1}$-norm is a sensible choice. We also see an extension of the metrics for
weighted graphs to multiple hops as promising next steps towards better graph
assessment for GNNs.

There exist additional GAMs, such as normalised total variation and normalised
smoothness value [13], neighbourhood entropy and centre-neighbour similarity
[23], and aggregations similarity score and diversification distinguishability
[7] that have been shown to correlate with GNN performance. An extension of
these metrics to regression tasks and weighted graphs would be interesting to
investigate in future works. All implementations of the here introduced
metrics are differentiable. This allows for a seamless integration in the
learning pipeline, e.g. as loss components, which could be a highly promising
application to improve GNN performance by optimising for specific graph
properties.

## References

  * [1] Berrone, S., Della Santa, F., Mastropietro, A., Pieraccini, S., Vaccarino, F.: Graph-informed neural networks for regressions on graph-structured data. Mathematics 10(5) (2022). https://doi.org/10.3390/math10050786, https://www.mdpi.com/2227-7390/10/5/786
  * [2] Bintsi, K.M., Baltatzis, V., Potamias, R.A., Hammers, A., Rueckert, D.: Multimodal brain age estimation using interpretable adaptive population-graph learning. arXiv preprint arXiv:2307.04639 (2023)
  * [3] Bronstein, M.M., Bruna, J., LeCun, Y., Szlam, A., Vandergheynst, P.: Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine 34(4), 18–42 (2017)
  * [4] Buitinck, L., Louppe, G., Blondel, M., Pedregosa, F., Mueller, A., Grisel, O., Niculae, V., Prettenhofer, P., Gramfort, A., Grobler, J., Layton, R., VanderPlas, J., Joly, A., Holt, B., Varoquaux, G.: API design for machine learning software: experiences from the scikit-learn project. In: ECML PKDD Workshop: Languages for Data Mining and Machine Learning. pp. 108–122 (2013)
  * [5] Cole, J.H.: Multimodality neuroimaging brain-age in uk biobank: relationship to biomedical, lifestyle, and cognitive factors. Neurobiology of aging 92, 34–42 (2020)
  * [6] Cosmo, L., Kazi, A., Ahmadi, S.A., Navab, N., Bronstein, M.: Latent-graph learning for disease prediction. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 643–653. Springer (2020)
  * [7] Elam, J.S., Glasser, M.F., Harms, M.P., Sotiropoulos, S.N., Andersson, J.L., Burgess, G.C., Curtiss, S.W., Oostenveld, R., Larson-Prior, L.J., Schoffelen, J.M., et al.: The human connectome project: a retrospective. NeuroImage 244, 118543 (2021)
  * [8] Jiang, B., Zhang, Z., Lin, D., Tang, J., Luo, B.: Semi-supervised learning with graph learning-convolutional networks. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 11313–11320 (2019)
  * [9] Kazi, A., Cosmo, L., Ahmadi, S.A., Navab, N., Bronstein, M.M.: Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 45(2), 1606–1617 (2022)
  * [10] Kim, D., Oh, A.: How to find your friendly neighborhood: Graph attention design with self-supervision. arXiv preprint arXiv:2204.04879 (2022)
  * [11] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
  * [12] Lim, D., Li, X., Hohne, F., Lim, S.N.: New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104.01404 (2021)
  * [13] Lu, S., Zhu, Z., Gorriz, J.M., Wang, S.H., Zhang, Y.D.: Nagnn: classification of covid-19 based on neighboring aware representation from deep graph neural network. International Journal of Intelligent Systems 37(2), 1572–1598 (2022)
  * [14] Luan, S., Hua, C., Lu, Q., Zhu, J., Chang, X.W., Precup, D.: When do we need gnn for node classification? arXiv preprint arXiv:2210.16979 (2022)
  * [15] Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.W., Precup, D.: Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.05641 (2021)
  * [16] Ma, Y., Liu, X., Shah, N., Tang, J.: Is homophily a necessity for graph neural networks? arXiv preprint arXiv:2106.06134 (2021)
  * [17] Mueller, S.G., Weiner, M.W., Thal, L.J., Petersen, R.C., Jack, C., Jagust, W., Trojanowski, J.Q., Toga, A.W., Beckett, L.: The alzheimer’s disease neuroimaging initiative. Neuroimaging Clinics 15(4), 869–877 (2005)
  * [18] Parisot, S., Ktena, S.I., Ferrante, E., Lee, M., Moreno, R.G., Glocker, B., Rueckert, D.: Spectral graph convolutions for population-based disease prediction. In: International conference on medical image computing and computer-assisted intervention. pp. 177–185. Springer (2017)
  * [19] Pei, H., Wei, B., Chang, K.C.C., Lei, Y., Yang, B.: Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 (2020)
  * [20] Shchur, O., Mumme, M., Bojchevski, A., Günnemann, S.: Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018)
  * [21] Stankeviciute, K., Azevedo, T., Campbell, A., Bethlehem, R., Lio, P.: Population graph gnns for brain age prediction. In: Proceedings of the ICML. vol. 202 (2020)
  * [22] Sudlow, C., Gallacher, J., Allen, N., Beral, V., Burton, P., Danesh, J., Downey, P., Elliott, P., Green, J., Landray, M., et al.: Uk biobank: an open access resource for identifying the causes of a wide range of complex diseases of middle and old age. PLoS medicine 12(3), e1001779 (2015)
  * [23] Xie, Y., Li, S., Yang, C., Wong, R.C.W., Han, J.: When do gnns work: Understanding and improving neighborhood aggregation. In: IJCAI’20: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,$\\{$IJCAI$\\}$ 2020\. vol. 2020 (2020)
  * [24] Yang, Z., Cohen, W., Salakhudinov, R.: Revisiting semi-supervised learning with graph embeddings. In: International conference on machine learning. pp. 40–48. PMLR (2016)
  * [25] Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., Koutra, D.: Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems 33, 7793–7804 (2020)

##  Appendix 0.A Further Information on Extended Graph Assessment Metrics

###  0.A.1 $K$-hop metrics

We here formally define $k$-hop node homophily and $k$-hop CCNs.

######  Definition 8 ($k$-hop node homophily)

A graph $\mathit{G}:=(\mathit{V},\mathit{E})$ with the set of node labels
$\mathit{Y}:=\\{y_{u};u\in\mathit{V}\\}$ has the following $k$-hop node
homophily:

$h^{(k)}(\mathit{G},\mathit{Y}):=\frac{1}{|\mathit{V}|}\sum_{v\in\mathit{V}}\frac{\left|\\{u|u\in\mathcal{N}^{(k)}_{v},y_{u}=y_{v}\\}\right|}{|\mathcal{N}^{(k)}_{v}|},$
(8)

where $\mathcal{N}^{(k)}_{v}$ is the set of nodes in the $k$-hop neighbourhood
of $v$.

######  Definition 9 ($k$-hop CCNS)

A graph $\mathit{G}:=(\mathit{V},\mathit{E})$ with the set of node labels $C$
has the following $k$-hop CCNS for two classes $c$ and $c^{\prime}$:

$\operatorname{CCNS}(c,c^{\prime})=\frac{1}{|\mathcal{V}_{c}||\mathcal{V}_{c^{\prime}}|}\sum_{u\in\mathcal{V},v\in\mathcal{V^{\prime}}}{\operatorname{cossim}(d^{(k)}(u),d^{(k)}(v))},$
(9)

where $d^{(k)}(v)$ indicates the empirical histogram of the labels of the
$k$-hop neighbours of node $v$ and $\operatorname{cossim}(\cdot,\cdot)$ the
cosine similarity.

Table 3 summarises model performances of $\\{1,2,3\\}$-hop GCNs on the
different benchmark datasets and the corresponing MLP performance on the node
features only. We can see that even though $3$-hop homophily of the datasets
Computers and Photo is very low, the GCNs with $3$ hops perform best on these
datasets. This does not align with our initial intuition about these metrics
and we believe this finding to be interesting to investigate further.

Table 3: Graph metrics of benchmark node classification datasets with corresponding performances of an MLP and 1,2, and 3-hop GCNs, reported in accuracy in %. Nodes: number of nodes, Cl.: number of classes in the dataset. Dataset | Nodes | Cl. | Node homophily | MLP | GCN
---|---|---|---|---|---
1-hop | 2-hop | 3-hop | 1-hop | 2-hop | 3-hop
Cora | $1\,433$ | 7 |  0.825 $\pm$ 0.29 |  0.775 $\pm$ 0.26 |  0.663 $\pm$ 0.29 | 60.41 | 76.33 | 81.70 | 78.90
Citeseer | $3\,703$ | 6 |  0.706 $\pm$ 0.40 |  0.754 $\pm$ 0.28 |  0.712 $\pm$ 0.29 | 61.19 | 71.20 | 72.10 | 67.10
Pubmed | $19\,717$ | 3 |  0.792 $\pm$ 0.35 |  0.761 $\pm$ 0.26 |  0.687 $\pm$ 0.26 | 74.00 | 76.60 | 79.10 | 77.70
Computers | $13\,752$ | 10 |  0.785 $\pm$ 0.26 |  0.569 $\pm$ 0.27 |  0.303 $\pm$ 0.20 | 79.35 | 39.27 | 67.56 | 83.13
Photo | $7\,650$ | 8 |  0.837 $\pm$ 0.25 |  0.660 $\pm$ 0.30 |  0.447 $\pm$ 0.28 | 82.09 | 48.10 | 82.88 | 88.37
Coauthor CS | $18\,333$ | $15$ |  0.832 $\pm$ 0.24 |  0.698 $\pm$ 0.25 |  0.520 $\pm$ 0.25 | 88.93 | 93.13 | 89.31 | 92.09

###  0.A.2 Node-wise metrics

The $k$-hop homophily for regression can also defined for every node
individually and then combined in the full homophily over the entire graph as
defined in the main part of this work.

######  Definition 10 (Homophily for regression)

Let $\mathit{G}=(\mathit{V},\mathit{E})$ and $\mathcal{N}^{k}_{v}$ be defined
as above and $Y$ be the vector of node labels, which is normalised between $0$
and $1$. Then the $k$-hop homophily of a node $v\in\mathit{V}_{c}$ in a node
regression task is defined as the mean label distance between the node $v$ and
all it’s neighbours.

$\operatorname{HReg}^{(k)}_{v}:=1-\left(\frac{1}{|\mathcal{N}^{(k)}_{v}|}\sum_{n\in\mathcal{N}^{(k)}_{v}}{\left\lVert
y_{v}-y_{n}\right\rVert}\right),$ (10)

where $|\cdot|$ is the cardinality of a set and $\lVert x\rVert$ the absolute
value of x.

The $k$-hop homophily for regression of the whole graph $\mathit{G}$ can then
be extracted as follows:

$\displaystyle\operatorname{HReg}^{(k)}_{G}$
$\displaystyle:=1-\left(\frac{1}{|V|}\sum_{v\in
V}{\operatorname{HReg}^{(k)}_{v}}\right)$
$\displaystyle=1-\left(\frac{1}{|V|}\sum_{v\in
V}\left({\frac{1}{|\mathcal{N}^{(k)}_{v}|}\sum_{n\in\mathcal{N}^{(k)}_{v}}{\left\lVert
y_{v}-y_{n}\right\rVert}}\right)\right).$ (11)

##  Appendix 0.B Experiments

In this section we give more details on training parameters and setups of the
experiments performed in this work.

###  0.B.1 Synthetic dataset

The synthetic datasets are generated using sklearn [4]. Each dataset consist
of either $1\,000$ or $2\,000$ nodes, with $50$ node features of which $5$ are
informative. For all experiments on the synthetic dataset we utilise early
stopping and the initial graph structure is generated using the $k$-nearest
neighbours approach with $5$ neighbours and the Euclidean distance.

###  0.B.2 TADPOLE dataset

We use the same TADPOLE dataset as in [9], which consists of $564$ subjects.
The task is the classification of Alzheimer’s disease, mild cognitive
impairment and control normal. For all experiments on the TADPOLE dataset, we
use early stopping and generate the initial graph structure using the
$k$-nearest neighbours approach and the Euclidean distance.

###  0.B.3 UKBB dataset

The dDGM experiments on the UKBB dataset are performed using no initial graph
structure, since this resulted in better model performance. For the cDGM
experiments we use the $k$-nearest neighbours approach with $x$ neighbours. We
utilised no early stopping and the Euclidean distance for the graph
construction for the cDGM experiments.

###  0.B.4 Baseline results

Table 4 summarises the baseline results on the population graph datasets using
a random forest and the implementation from sklearn [4].

Table 4: Baseline results using random forests on the different datasets. For classification tasks, we report accuracy in % and for regression MAE. We report the mean and standard deviation of a $5$-fold cross validation. Dataset | Nr. nodes | Task | Test Score
---|---|---|---
Synthetic | $1000$ | Binary classification |  78.00 $\pm$ 0.07
|  | Regression |  0.0529 $\pm$ 0.01
| $2000$ | Binary classification |  88.10 $\pm$ 0.02
|  | Regression |  0.0081 $\pm$ 0.00
Tadpole | $564$ | Classification |  94.15 $\pm$ 0.01
UKBB | $6406$ | Regression |  4.2644 $\pm$ 0.05