RECHERCHE

Network alignment and similarity reveal
atlas-based topological differences
in structural connectomes

Matteo Frigo1*

, Emilio Cruciani2*

, David Coudert2

, Rachid Deriche1

,

Emanuele Natale2

, and Samuel Deslauriers-Gauthier1

1Université Côte d’Azur, Inria, France
2Université Côte d’Azur, Inria, CNRS, I3S, France
*These authors contributed equally to this work.

un accès ouvert

journal

Mots clés: Brain network topology, Structural connectome, Graph alignment, Graph Jaccard index,
Weisfeiler-Leman, Brain parcellation

ABSTRAIT

The interactions between different brain regions can be modeled as a graph, called
connectome, whose nodes correspond to parcels from a predefined brain atlas. The edges
of the graph encode the strength of the axonal connectivity between regions of the atlas
that can be estimated via diffusion magnetic resonance imaging (IRM) tractography. Herein,
we aim to provide a novel perspective on the problem of choosing a suitable atlas for
structural connectivity studies by assessing how robustly an atlas captures the network
topology across different subjects in a homogeneous cohort. We measure this robustness
by assessing the alignability of the connectomes, namely the possibility to retrieve graph
matchings that provide highly similar graphs. We introduce two novel concepts. D'abord, le
graph Jaccard index (GJI), a graph similarity measure based on the well-established Jaccard
index between sets; the GJI exhibits natural mathematical properties that are not satisfied
by previous approaches. Deuxième, we devise WL-align, a new technique for aligning
connectomes obtained by adapting the Weisfeiler-Leman ( WL) graph-isomorphism test.
We validated the GJI and WL-align on data from the Human Connectome Project database,
inferring a strategy for choosing a suitable parcellation for structural connectivity studies.
Code and data are publicly available.

RÉSUMÉ DE L'AUTEUR

An important part of our current understanding of the structure of the human brain relies on the
concept of brain network, which is obtained by looking at how different brain regions are
connected with each other. In this paper we present a strategy for choosing a suitable
parcellation of the brain for structural connectivity studies by making use of the concepts of
network alignment and similarity. To do so, we design a novel similarity measure between
weighted networks called graph Jaccard index, and a new network alignment technique called
WL-align. By assessing the possibility to retrieve graph matchings that provide highly similar
graphs, we show that morphology- and structure-based atlases define brain networks that are
more topologically robust across a wide range of resolutions.

Citation: Frigo, M., Cruciani, E.,
Coudert, D., Deriche, R., Natale, E., &
Deslauriers-Gauthier, S. (2021).
Network alignment and similarity reveal
atlas-based topological differences in
structural connectomes. Réseau
Neurosciences, 5(3), 711–733. https://est ce que je
.org/10.1162/netn_a_00199

EST CE QUE JE:
https://doi.org/10.1162/netn_a_00199

Informations complémentaires:
https://doi.org/10.1162/netn_a_00199
https://osf.io/depux

Reçu: 18 Décembre 2020
Accepté: 6 May 2021

Intérêts concurrents: Les auteurs ont
a déclaré qu'aucun intérêt concurrent
exister.

Auteur correspondant:
Matteo Frigo
matteo.frigo@inria.fr

Éditeur de manipulation:
Alex Fornito

droits d'auteur: © 2021
Massachusetts Institute of Technology
Publié sous Creative Commons
Attribution 4.0 International
(CC PAR 4.0) Licence

La presse du MIT

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

/

/

t

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

.

t

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Atlas-based topological differences in structural connectomes

INTRODUCTION

Because of the immense complexity of the brain, it is impossible to gain any insight into its global
operation without simplifying assumptions. One such assumption, which has been widely used by
neuroscientists, is that the brain, and in particular the cortical surface, can be divided into distinct
and homogeneous areas. Of course the definition of homogeneous areas greatly depends on one’s
point of view, which has led to a plethora of brain parcellations. Par exemple, the cortical surface
has been subdivided based on its cytoarchitecture (Brodmann, 1909), gyri (Desikan et al., 2006),
functional organization (Schaefer et al., 2017), axonal connectivity (Gallardo, Wells, Deriche, &
Wassermann, 2018), and combinations of these and other features (Glasser et al., 2016). There is
also significant evidence that cortical regions vary in shape, size, number, and location across
subjects and even across individual tasks, making the existence of a single canonical atlas unlikely.
In addition to studying the characteristics of specific brain regions defined by a parcellation, là
has been a growing interest in their relationship and interactions, an emerging field known as con-
nectomics. In this context, the focus is shifted from understanding how information is segregated in
the brain to how it is integrated. Par exemple, through diffusion magnetic resonance imaging (IRM)
tractography, structural connections between brain areas can be recovered. The result is a network
whose nodes correspond to cortical regions and whose edge weights represent the strength of the
structural connectivity between pairs of regions. A similar network can also be built from resting-
state functional MRI yielding a functional, rather than structural, réseau. These brain networks,
which encode the structural and functional connections of the brain, are referred to as connec-
tomes (Hagmann, 2005; Sporns, Tonomi, & Kötter, 2005). Given functional or structural connec-
tomes, their features can be compared across subjects and populations to link network changes to
pathology or to further increase our understanding of its organization. An underlying assumption
is that a correspondence exists between nodes of the network across subjects, a condition that
is usually satisfied by using a group parcellation (Gallardo, Wells, et coll., 2018; Parisot, Arslan,
Passerat-Palmbach, Wells, & Rueckert, 2015). The drawback of this strategy is that it ignores
any subject-specific changes in cortical organization and reduces the specificity of the results.
An alternative approach is to construct a mapping between the nodes of the network prior to
the comparison, therefore allowing the use of subject-specific atlases. To our knowledge, ce
approach has never been investigated in the field of network neuroscience.

The construction of a mapping between network nodes corresponds to what is known in
various fields as network alignment or graph matching (Ayache & Faverjon, 1987; Barak,
Chou, Lei, Schramm, & Sheng, 2019; Conte, Foggia, Sansone, & Vento, 2004; Korula &
Lattanzi, 2014; Singh, Xu, & Berger, 2008). Plus récemment, the graph matching problem gained
attention also in the field of neuroscience, being used in the contexts of the analysis of connec-
tome heterogeneity across subjects (Rasero et al., 2017; Takerkart, Auzias, Thirion, & Ralaivola,
2014) and system-level matching of structural and functional connectomes (Osmanlıog(cid:1)lu et al.,
2019). Graph alignment solutions (called alignments) correspond to a permutation of the labels
of the nodes of a graph that maximizes its similarity to a second graph. There is no standard way
to measure the quality of its solutions (Bayati, Gleich, Saberi, & Wang, 2013). This is also
reflected in the neuroimaging literature, where various measures of similarity between brain
networks are used (Becker et al., 2018; M.. K. Chung, Lee, Solo, Davidson, & Pollak, 2017;
Deslauriers-Gauthier, Zucchelli, Frigo, & Deriche, 2020; Osmanlıog(cid:1)lu et al., 2019; Rasero
et coll., 2017; Takerkart et al., 2014; Villareal-Haro, Ramirez-Manzanares, & Pichardo-Corpus,
2020). In the context of connectomics, a graph alignment is a reordering of the labels of the
nodes of a brain network that maximizes its similarity with a second one while preserving the
topology. Describing the brain network through its connectivity (also known as adjacency)
matrice, permutations of the node labels correspond to identical permutations of the rows and

712

Parcellation:
Subdivision of the brain into distinct
regions with respect to
morphological, cytoarchitectonic,
anatomical, topological, ou
functional criteria.

Tractography:
Method for tracking the trajectory of
the axonal pathways that exploits the
anisotropy of the diffusion MRI signal.

Connectome:
The network that encodes the
connections of the human brain; it
refers to a comprehensive description
of the brain’s structural and/or
functional connections.

Functional connectome:
Network-like description of the
coherence between the activity in
different brain regions; it can be
obtained by studying co-activation
patterns in functional MRI, EEG, ou
MEG.

Structural connectome:
Network that describes the structure
of the white matter connections in
the brain; it can be obtained via
diffusion MRI-based tractography.

Network alignment:
Function that maps nodes of a graph
onto nodes of another graph, alors que
usually trying to preserve adjacency
(end points of edges in a graph
should map onto end points of edges
of the other graph).

Graph similarity:
Measure of how much two networks
are close with respect to some
criteria of topological nature.

Neurosciences en réseau

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

/

t

/

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

.

t

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Atlas-based topological differences in structural connectomes

columns of the connectivity matrix. This problem is distinct from the brain atlas correspondence
and parcel matching problems (Gallardo, Gayraud, et coll., 2018; Mars et al., 2016). The main
difference is that in those problems the permutation acts only on the rows of the connectivity
matrix as they find correspondences between connectivity fingerprints that rely on external
features. Inversement, graph alignment does not rely on any external information and uses only
information contained in the topology of the graphs.

The complexity of finding the optimal alignment between two graphs using a näıve brute
force strategy is exponential in the number of nodes. It is therefore intractable even for the
smallest of brain networks, which typically have 50 cortical regions. Spectral methods are a
popular approach to the alignment problem (Feizi et al., 2019; Hayhoe, Barreras, Hassani, &
Preciado, 2019; Nassar, Veldt, Mohammadi, Grama, & Gleich, 2018), despite being subject to
limitations (Wilson & Zhu, 2008). Modern machine learning paradigms exploit deep learning
techniques for finding an alignment (Heimann, Shen, Safavi, & Koutra, 2018; Li et al., 2018;
Liu, Cheung, Li, & Liao, 2016), however they make use of partially available information about
the alignment itself (Liu et al., 2016), or lack explainability and interpretability.

We first introduce the graph Jaccard index (GJI), a natural objective function for the network
alignment problem. For a given alignment, the GJI rewards correct matches while simultaneously
penalizing mismatches, overcoming limitations of previous approaches (Feizi et al., 2019).

We then propose a new graph alignment heuristic, the Weisfeiler-Leman alignment (WL-align),
based on a weighted variant of the Weisfeiler-Leman algorithm for graph isomorphism (Weisfeiler
& Leman, 1968). WL-align is amenable to concrete interpretability in terms of local network struc-
ture around each node (Chiffre 2) and can be integrated with other heuristics. We compare WL-
align against the fast approximate quadratic programming for graph matching (FAQ) (Vogelstein
et coll., 2015), another efficient brain-alignment heuristic that is solely based on network structure.

THEORY

A brain network is characterized as an edge-weighted graph G = (V, E ), where each of the n
nodes represents a brain region and each weight wij encodes the strength of the connection
between regions i and j. The graph G can always be considered as complete, given that an
bord (je, j ) =2 G can be associated with a null weight wij = 0. The matrix that encodes in position
(je, j ) the weight of the edge wij between nodes i and j is called adjacency matrix of G and is
denoted as Adj(G). In the context of connectomics (Hagmann, 2005; Sporns et al., 2005), le
adjacency matrix is also known as connectivity matrix. In this work we consider only networks
with nonnegative edge weights. For structural connectomes this does not impose any special
preprocessing, since they are usually constructed using streamline count, length, or weights
that are already nonnegative. Cependant, functional connectomes can contain negative entries
because they are typically based on the correlation of resting-state functional MRI signals. UN
practical solution, already used in other studies (Deslauriers-Gauthier et al., 2020), is to thresh-
old the connectomes, therefore replacing negative entries by zeros.

Brain Alignment

To compare two networks, it is of fundamental importance to establish a correspondence between
the nodes of the two graphs. Given two networks G1 = (V1, E1) and G2 = (V2, E2) of n1 and n2 nodes
→ V2 (whose existence is granted
respectivement, it is possible to define an injective map m : V1
whenever |V1| ≤ |V2|) that is called graph matching or network alignment. An edge (toi, v) 2 E1 is
correctly matched by m if (m(toi), m(v)) 2 E2 and both edges have the same weight. Notice that a
graph matching that matches all edges corresponds to an injective graph homomorphism. In the

Neurosciences en réseau

713

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

t

/

/

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

.

t

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Atlas-based topological differences in structural connectomes

context of connectomics we will refer to m also as a brain alignment. A simple representation of
this function is that of a matching matrix Pm of dimension n2 × n1 (with n2

≥ n1) defined as

(cid:1)

Pmð

Þij ¼

1

if m jð Þ ¼ i;
0 otherwise:

(1)

In the special case where n1 = n2, Pm is a permutation matrix. If m is an isomorphism between
G1 and G2, then the transformation between the adjacency matrices of the two graphs is fully
characterized by the matching matrix and is given by

Adj G1
ð

Þ ¼ P>
m

Adj G2
ð

ÞPm:

(2)

Quality of Brain Alignments

Once a brain alignment is identified, its quality can be assessed by evaluating the (dis)similarité
of the two resulting networks. On a lexical note, we remark how the concept of similarity
between networks used throughout this work fits well the standard concept of matrix similarity
in the particular case where the change of basis matrix is a permutation matrix. Dans ce qui suit,
the similarity measures are defined for equal-sized networks, as typically encountered in con-
nectomics. Classical metrics for this task are based on the comparison of the adjacency matrices
of the two graphs by means of Pearson’s correlation coefficient, ℓ
p distance, or Frobenius dis-
tance (Vogelstein et al., 2015). The norm-based distances estimate the dissimilarity between two
graphs G1 and G2 by computing the distance between their adjacency matrices as follows:
Þ ¼ Adj G1
k

Þ − Adj G2

dt G1; G2

(3)

ð

ð

ð

;

Þ
kt

where t indicates the type of norm ( p for ℓp norms and F for Frobenius norm). Note that higher
distance corresponds to lower similarity. Another similarity measure that has been widely
adopted in neuroimaging and brain connectivity is correlation; among the many definitions
of correlation, we consider

C G1; G2

ð

Þ ¼

→
→
hAdj
Þ; Adj
ð
ð
G2
G1
→
→
Þk2 _ kAdj
kAdj
ð
ð
G2
G1

Þi
Þk2

;

(4)

where the numerator is the scalar product between the vectorizations of the adjacency matrices
of the two graphs and the denominator is the product of their norms. This similarity measure is
also known as cosine similarity, since it corresponds to the cosine of the angle between the two
vectors. Other distances based on geometrical (Venkatesh, Jaja, & Personne, 2020) and homolog-
ical (M.. K. Chung et al., 2017) properties of the networks have been proposed. All such measures
capture some aspects of the similarity between two graphs, but none of them satisfies all the
following requirements:

▪ arising as a natural generalization of other similarity measures for less structured data, pour

example, for sets of values without a network structure;

▪ being applicable to the algorithmic graph isomorphism and induced subgraph isomor-
phism problems, as fundamental special cases of the problem of measuring the similarity
between two graphs;

▪ being simple enough so that its value can be easily interpreted;
▪ giving a straightforward notion of metric in the considered space.

We therefore propose a new measure obtained by generalizing the Jaccard similarity index,
a similarity metric widely adopted in data mining, so that algorithmic problems such as in-
duced subgraph isomorphism can be retrieved as special cases. De plus, while our proposed

Neurosciences en réseau

714

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

/

t

/

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

t

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Atlas-based topological differences in structural connectomes

measure assigns a clear meaning to the correspondence between two edges in two given
graphs, it also depends on the global network structure.

Weighted graph Jaccard similarity index. The Jaccard similarity index was originally proposed in
the context of set theory to measure the similarity between two sets A and B. It is computed as
the ratio between the size of their intersection and the size of their union; c'est,

J A; Bð

Þ ¼

A ∩ B
j
j
UN [ B
j
j

:

(5)

An example of what is measured by the Jaccard index on sets is given in the top panel of
Chiffre 1. Notice that J(UN, B) is defined in the [0, 1] range and the extreme values are attained

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

/

t

/

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

.

t

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Chiffre 1. Top panel. The two sets contoured by the circles have a non-empty intersection marked
by the black dots. The Jaccard similarity index between the two sets is the result of the ratio between
the number of elements in the intersection and the number of elements in the union of the two sets.
The resulting Jaccard index is equal to J = 3/33 ≈ 0.09. Bottom panel. This figure shows an example
of how to compute the GJI between two compatible graphs X and Y. For each pair of nodes i, j 2 {UN,
B, C, D}, one computes the minimum and maximum between Xi,j and Yi,j . These two quantities will
be used to define the numerator and the denominator of the GJI defined in Equation 7. As shown in
the min (yellow) and max (vert) graphs, edges that are not in a graph are associated with a null
weight. The GJI is then computed as the ratio between the sum of the minimal weights and the sum
of the maximal weights.

Neurosciences en réseau

715

Atlas-based topological differences in structural connectomes

either when the intersection of the two sets is empty (c'est à dire., UN \ B = ; ) J.(UN, B) = 0) or when the
two sets are equal (c'est à dire., A = B ) J.(UN, B) = 1). Both the sets need to be non-empty.

The Jaccard similarity index has also been generalized to nonnegative real vectors and, dans
this more general setting, is also known as Ruzicka similarity. In detail, given two vectors x, oui 2
Rd such that xi

≥ 0, their weighted Jaccard similarity index can be computed as

≥ 0 and yi

J x; yð

Þ ¼

P.

P.
d

d

i¼1 min xi; yi
ð
i¼1 max xi; yi
ð

:

Þ

Þ

(6)

Note that the Jaccard similarity index between two sets follows as a special case whenever the
vectors x, y are binary and their dimension d is equal to the size of the union of the two sets.

Our adaptation of the concept of Jaccard similarity index to weighted graphs is based on the
identification of the nodes of the two graphs. Given two brain networks G1 and G2 with ad-
jacency matrices Adj(G1) = A and Adj(G2) = B, the weighted graph Jaccard similarity index
(GJI) of G1 and G2 is

P.

J G1; G2
ð

Þ ¼

P.

je; jð

Þ2E

je; jð

Þ2E

(cid:3)

(cid:4)

min Ai; j; Bi; j
(cid:3)
max Ai; j; Bi; j

(cid:4) ;

(7)

where E is the set of all possible pairs of nodes. For the sake of the present work, we remark that we
can think of B as having been previously aligned to A via Equation 2. Alternativement, the weighted
graph Jaccard similarity index is defined as the weighted Jaccard index of the vectorizations of the
graphs’ adjacency matrices. Notice that J(G1, G2) is not well defined when both G1 and G2 are
vide (c'est à dire., E1 = E2 = ;). Whenever Adj(G1) = Adj(G2), the min and the max in Equation 7 coincide
and J(G1, G2) = 1. On the contrary, if G1 and G2 do not have any edge in common (c'est à dire., E1 \ E2 = ;),
the numerator of Equation 7 will be equal to 0 and J(G1, G2) = 0. A remarkable property of the
weighted Jaccard similarity index is that it induces a metric in the space where it is defined. Comme
a matter of fact, the function dJ(X, oui) = 1 − J(X, oui) 2 [0, 1] respects the three properties of metrics:

Identité: dJ(X, oui) = 0 if and only if x = y;

1.
2. Symmetry: dJ(X, oui) = dJ( oui, X);
3. Triangle inequality: dJ(X, oui) ≤ dJ(X, z) + dJ(z, oui).

The first two properties trivially follow from the definition of J, while the third follows as a
particular case of what is presented in Charikar (2002, Lemma 1). An example of how the
GJI acts on two graphs is given in the bottom panel of Figure 1.

We have so far formally established the notion of network alignment (Équation 1), and pre-
sented the graph Jaccard index as a principled way to measure the quality of an alignment
(Équation 7). We are thus ready, in the next section, to describe our variant of the
Weisfeiler-Leman heuristic and to show how to employ it to construct a network alignment.

Weisfeiler-Leman Network Alignment

In this work we propose a brain-alignment technique that allows us to define the graph matching
m between two brain networks G1 and G2 with a three-step procedure:

1. For each node u in both graphs, define a vector Hu called signature.
2. Define a complete bipartite graph where on one side there are the nodes of the first graph
and on the other side there are the nodes of the second graph; the Euclidean distance
between two signatures becomes the weight of each edge of the bipartite graph.

716

Signature:
Feature vector assigned to each node
of a graph.

Bipartite graph:
Network whose nodes can be
divided in two distinct and
nonoverlapping sets, such that there
are no edges connecting nodes in the
same set.

Neurosciences en réseau

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

t

/

/

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

t

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Atlas-based topological differences in structural connectomes

3. The graph matching is given by the solution of the minimum weight bipartite matching
problem, also known as assignment problem, on the bipartite graph previously defined.

The novelty element of this brain-alignment algorithm is given by the definition of the node
signature, which is determined with an algorithm inspired by the Weisfeiler-Leman ( WL)
method for graph isomorphism testing (Weisfeiler & Leman, 1968). For this reason, WL-align
is the name we propose for our brain-alignment algorithm.

Node signature. The signature that we associate to each node of the two graphs describes the
local connectivity pattern of the node. It relies on the concept of volume of a node, which is
defined as the sum of the weights of the edges incident to the node itself, namely

vol vð Þ ¼

wuv;

X

u2V

(8)

where V is the set of nodes in the graph, v is the node of which we compute the volume vol(v),
and wuv is the weight of the edge connecting nodes u and v. The algorithm that defines the
signature of node u considers the subnetwork G0 induced by the nodes that are reachable from
u in at most ℓ hops. At each of these hops, G0 retains only the k nodes with highest contribu-
tion, weighted according to a function of the path that connects them to u. In detail, such a
contribution is computed via the following function

8
>< f v0; …; vh ð Þ :¼ >:

vol v0ð
Þ
w v0; v1
ð
vol v0ð
Þ

Þ

if π ¼ v0ð

Þ;

_ f v1; …; vh

ð

Þ otherwise;

(9)

Breadth-first search (BFS):
Graph traversal that, starting from a
root node, explores all its neighbors
before moving to the neighbor’s
neighbors, et ainsi de suite.

P‘

where w(toi, v) is just a more verbose notation for the edge weight wuv. The subnetwork G0 is a
complete k-ary tree of depth ℓ that can be obtained from a breadth-first search (BFS) starting
i¼0 ki nodes. For this reason the parameters k and ℓ are respec-
from u, and has a total of d =
tively called width and depth. The entries of the signature Hu 2 Rd are then computed starting
from u and following the BFS by recursively estimating the contribution of each edge to the
volume of the considered node via Equation 9. A formal description of the algorithm for com-
puting the signature Hu is given in Algorithm 1, while a graphical intuition is illustrated in
Chiffre 2.

Bipartite graph. Once a signature is computed for each node of the two graphs, we define a
weighted complete bipartite graph Gm = ((V1 [ V2), (V1 × V2)). The nodes on the left, c'est, V1,
represent the nodes of the first graph, while the nodes on the right, c'est, V2, represent the
nodes of the second graph. The edge weights encode the distance between the signatures of
pairs of nodes belonging to different graphs, c'est, each edge (toi, v) with u 2 V1 and v 2 V2 is
→ R defined as the Euclidean distance between
weighted according to a function b : V1 × V2
the signatures of the two end points b(toi, v) = kHu − Hvk2. Chiffre 3 shows a simple example of
the defined bipartite graph.

Assignment problem. The final step towards finding the wanted matching with WL-align is the
resolution of the assignment problem corresponding to the bipartite graph Gm defined in the
previous paragraph. The matching can be found by selecting a minimum-weight graph match-
ing, namely a subset of edges of the bipartite graph such that every node has degree 1 et le
sum of the weights of all edges of the subset is minimal. In formal terms, given the two sets V1
→
and V2 and the weighting function b that define Gm, the problem asks to find a bijection m : V1
V2, c'est, the matching, that minimizes the function (cid:3)
lem is efficiently solved by the Hungarian algorithm (Jacobi, 1890; Kuhn, 1955).

u2V1 b(toi, m(toi)). This assignment prob-

Neurosciences en réseau

717

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

/

t

/

e
d
toi
n
e
n
un
r
t
je
c
e
–
p
d

je

F
/

/

/

/

/

5
3
7
1
1
1
9
6
0
4
8
0
n
e
n
_
un
_
0
0
1
9
9
p
d

t

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

Atlas-based topological differences in structural connectomes

Algorithm 1 WL-align signature

Input: graph G; node u; width k; depth ℓ

Output: signature Hu

← empty list

1: Hu
2: Q ← empty queue

3: Q ← append π = (toi)

4: while Q is not empty do

5: π = (toi, …, vh) ← pop path from Q
6: Hu

← append f(π)

7:

8:

9:

10:

11:

if h < ℓ then π z ← (u, …, vh, z), 8z 2 V ← nodes s.t. f(π z1, …, zn Q ← append the k paths π z1) ≥ … ≥ f(π z1,…, π zk. zn) end if . FIFO data-structure; pop left (get and remove); append right . π is the zero-length, single-node path . append right . h is the length of π . if (vh, z) =2 E then w(vh, z) = 0 ) f(π z) = 0 . ties broken uniformly at random l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 12: end while 13: return Hu METHODS We processed the data of 100 unrelated subjects from the Human Connectome Project (HCP) database and obtained the structural brain networks via dMRI-based tractography. For each of the 100 subjects we considered 23 parcellations (Desikan, Glasser, Gallardo at 11 different resolutions, Schaefer at 10 different resolutions), obtaining a total of 2,300 weighted graphs. For each parcellation, we retrieved a network alignment between each of the 5,050 pairs of subjects using WL-align, which is the novel technique introduced in this work, and the state- of-the-art competitor FAQ for a total of 232,300 alignments. The quality of the obtained align- ments was then assessed using four network similarity measures. Data and Preprocessing To build the structural brain networks, we considered the preprocessed data of the HCP database (U100 subject group; Glasser et al., 2013; Van Essen et al., 2012; WU-Minn Human Connectome Project Consortium, 2017). For each subject, a five-tissue-type image (Smith, Tournier, Calamante, & Connelly, 2012) was obtained using the FreeSurfer pipeline (Fischl, 2012) invoked through MRtrix3 (Tournier et al., 2019). A response function was estimated for the white matter, gray matter, and cerebrospinal fluid using a maximal spherial harmonic order of 8 for all tissues (Jeurissen, Tournier, Dhollander, Connelly, & Sijbers, 2014). The fiber orien- tation distribution functions (fODFs) were then computed using the multishell, multitissue con- strained spherical deconvolution algorithm (Jeurissen et al., 2014). Finally, the fODFs were used as input for probabilistic anatomically constrained tractography performed with the iFOD2 algorithm (Smith et al., 2012) seeding from the gray matter–white matter interface and obtaining a total of five million streamlines per subject. Network Neuroscience 718 Atlas-based topological differences in structural connectomes l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . t / / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Figure 2. The graph on the left is the one that serves as an example for explaining the algorithm for computing the signature Hu of node u with k = 2 and ℓ = 2. The first entry of Hu is Hu[1] = vol(u), which is obtained by considering all the edges touching node u contoured by the purple circle in panel 1. The focus then moves to the two neighbors that create a path with highest f, namely v1 and v2, which are marked by the blue and green circles in panel 2. They are considered in decreasing order (w.r.t. the volume) and the corresponding entries are computed with Equation 9. For instance, the second entry of Hu is equal to Hu[2] = vol(v1) · a1/vol(u). The third entry is computed in an analogous way as Hu[3] = vol(v2) · a2/vol(u). This concludes the definition of the first 1 + k entries of Hu. The following entries are defined by considering first the blue and then the green subnetwork in panel 3. The fourth entry is equal to Hu[4] = vol(u) · (a1/vol(v1)) · (a1/vol(u)) and the fifth is Hu[5] = vol (w1) · (b1/vol(v1) · (a1/vol(u)). Analogously, the sixth and the last entry will be Hu[6] = vol(w4) · (b4/vol(v2)) · (a2/vol(u)) and Hu[7] = vol(w5) · (b5/ vol(v2)) · (a2/vol(u)). Parcellations. The four parcellations considered in this work subdivide the cerebral cortex fol- lowing different characteristics of the brain. The Desikan (Desikan et al., 2006) parcellation is based on the manual segmentation of a template of the brain cortex that takes into account the morphological consistencies of healthy human brains. For each subject, it was obtained directly Figure 3. The red and blue nodes in the two rows represent the two graphs G1 = (V1, E1) and G2 = (V2, E2) being aligned. The displayed complete bipartite graph is the one constructed in the second step of the WL-align algorithm. Each edge has weight equal to the Euclidean distance between the signatures of the nodes that it connects. For instance, the weight associated with the edge connecting − Hvk2, where Hu and Hv are the signatures of nodes u and v nodes u 2 V1 and v 2 V2 is kHu defined in the first step of the WL-align algorithm. Network Neuroscience 719 Atlas-based topological differences in structural connectomes from the HCP database (aparc+aseg.nii.gz) together with the cortical surface in fslr32k space. The Glasser parcellation (Glasser et al., 2016) follows a multimodal approach that considers cortical architecture, function, connectivity, and topography. Its projection onto the fslr32k space was obtained from the BALSA repository (Van Essen et al., 2017). The Gallardo parcella- tion (Gallardo, Wells, et al., 2018) is based on the segmentation of the structural connectivity profiles associated with each point of the cortical surface, and the Schaefer parcellation (Schaefer et al., 2017) is based on the analysis of the coactivation patterns of the brain by means of the analysis of resting-state functional connectivity. The Gallardo and the Schaefer parcella- tions were computed with a granularity of 100, 200, 300, 400, 500, 600, 700, 800, 900, and 1,000 parcels. The Gallardo parcellation was computed also with a granularity of 50 parcels. We extracted the 11 Gallardo atlases from the extrinsic connectivity parcellation of Gallardo et al. (Gallardo, Wells, et al., 2018). The used Schaefer atlas (Schaefer et al., 2017) was downloaded from the repository of the CBIG laboratory (Yeo, 2020) for the seven-network parcellation (Yeo et al., 2011). The use of multiresolution parcellations reflects the multiscale nature of the brain network and allows us to inspect how the atlas resolution affects the similarity and the alignment of brain networks. Connectomes. For each subject and parcellation, in-house software was used for counting the number of streamlines connecting each pair of regions. The obtained quantity was encoded as the weight of the edge connecting the two parcels in the brain network. All the edge weights were then divided by the sum of all the weights in the graph. A total of 23 connectomes of dif- ferent sizes were obtained for each subject. Given the limitations of dMRI-based tractography, self-connections were excluded from the connectomes, that is, the diagonal of the adjacency matrix is set to 0. Because of the high resolution of some parcellations, some regions turned out to be isolated (i.e., not connected to any other region). In order to have a connected graph, which is a requirement of the WL-align algorithm, we artificially connected these isolated (i.e., zero-volume) nodes to the others by adding small-weighted edges connecting each of these nodes to all the other nodes in the graph. This weight was set to 1 (before normalization), which from the point of view of tractography is equivalent to the existence of one single streamline connecting the region to the others. The obtained graphs are undirected and weighted. Intracohort Variability In order to assess the variability between the brain networks of the subjects in the studied co- hort, for each subject we measured the similarity between the connectomes of each pair of subjects with three different similarity metrics: the weighted graph Jaccard index (Equation 7), the Frobenius norm (Equation 3) and the correlation (Equation 4). Network Alignments In order to assess the ability of WL-align to retrieve the wanted alignment map, we prepared the dataset in a way that allows us to test the quality of the alignment against a known ground truth. In practice, for each parcellation p, we randomly permuted the node labels of the con- nectomes of all subjects keeping track of the permutation maps. These permutation maps al- low us to compute the ground truth matching m* between each pair of brain networks computed with the same parcellation. For the same set of brains, we also computed two graph matchings. The first is mWL, which is computed with the proposed WL-align technique. The width and depth parameters of the WL-align algorithm were fixed to k = blog2 nc, where n is the number of nodes in the consid- ered network (i.e., one hemisphere), and ℓ = 2. We limited the width for efficiency reasons (the Network Neuroscience 720 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d t . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes Bi-stochastic matrix: Matrix of positive entries where each column and row sums to 1. ℓ size of the signature is greater than k , as described in the previous section) and the depth since further increasing it does not lead to substantial gain w.r.t. the quality of the alignments (the deeper the nodes in the search, the smaller the contribution of the nodes to the signature, as described in Equation 9). The second is mFAQ, which is computed with the fast approximate quadratic programming for graph matching (FAQ) algorithm (Vogelstein et al., 2015), which is the state-of-the-art tech- nique for network alignment. FAQ works in three main steps: (a) arbitrarily choose a starting bi-stochastic matrix, which acts as a relaxed permutation matrix that aligns the two networks; (b) find a local solution to the relaxed quadratic assignment problem (rQAP), a dual version of the graph matching problem; (c) project back onto the set of permutation matrices. The solu- tion found by FAQ transforms the adjacency matrix of the first graph into one with approxi- mately minimal Frobenius distance from the adjacency matrix of the second graph. Notice that optimality with respect to the Frobenius distance might not correspond to absolute opti- mality. We used the implementation of FAQ available in the graspologic package (J. Chung et al., 2019; https://graspologic.readthedocs.io/), setting the number of random initializations to 30. Both WL-align and FAQ were run separately on each hemisphere of the brain, and the two resulting partial alignments were then combined into a single one. The motivation for this choice is that the correct hemisphere can always be assigned to a cortical region, and this property is independent from any influence potentially caused by the registration of the template atlas onto the subject-specific cortical mesh, while other properties, such as the location of a region, would be. Moreover, by studying single-hemisphere alignments we bypass the issue concerning the high degree of left-right similarity that characterizes the brain, which could drive the solution towards suboptimal alignments that are hardly distinguishable without external criteria such as the localization or geometry of the brain regions. Notice that this choice concerns the design of the experiment, not the setup of the graph matching algo- rithm, which could still be obtained using the full brain network, hence including the inter- hemispheric connections. Quality of Alignments Given two networks G1 = (V1, E1) and G2 = (V2, E2) defined on the same parcellation and given a matching m between them, we consider the following metrics to evaluate the quality of the matching m. ▪ Node matching ratio (NMr): The fraction of nodes that have been correctly matched by m with respect to the ground truth matching m* (known a priori), namely NMr mð Þ ¼ j f u 2 V1 : m uð Þ ¼ m* uð Þ j g V1j j : (10) The NMr metric is defined in the [0, 1] range, and higher values correspond to better alignments. ▪ Graph Jaccard index J: As defined in Equation 7, namely J mð ð Þ ¼ J m G1 ð Þ; G2 Þ; (11) where, with an abuse of notation, we write m(G1) to denote the relabeling of the nodes obtained by applying the matching m on the nodes of G1. Recall that the graph Jaccard index is defined in the [0, 1] range, and higher values correspond to better alignment. Network Neuroscience 721 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes ▪ J ratio ( Jr): The ratio between the graph Jaccard index J(m) obtained by m and the graph Jaccard index J(m*) obtained by the ground truth matching m*, namely Jr mð Þ ¼ Þ J mð Þ J m*ð : (12) When the ground truth matching m* is also an optimal matching, the denominator J(m*) acts as a normalization factor, which takes into account how complex it is to retrieve the matching m* in terms of Jaccard similarity; under such an assumption of ground truth optimality, the Jr metric takes values in the [0, 1] range, where higher values correspond to better alignment. ▪ Frobenius norm (FRO): The Frobenius norm of the difference between the adjacency ma- trices of m(G1) and G2, namely FRO mð Þ ¼ Adj m G1 k ð ð Þ − Adj G2 Þ ð ; Þ kF (13) where, as was also done for J, we write m(G1) to denote the relabeling of the nodes ob- tained by applying the matching m on the nodes of G1. The FRO metric is defined in the [0, 2] range (since the adjacency matrices both have norm 1), and lower values corre- spond to better alignment. For each considered parcellation p and for each network alignment algorithm of interest x (either WL-align or FAQ), we report the average similarity metric, computed among all pairs of brains in the parcellation. For example, considering NMr as similarity metric, we compute NMrx p ¼ 1 Pj j X G1;G2 ð Þ2P NMr mð Þ; (14) where P is the set of all pairs of brains with parcellation p and m is the matching found by algorithm x for the input pair of graphs G1, G2. Analogously, this is done for all similarity metrics. A further qualitative assessment of the accuracy of the alignments obtained with WL-align was performed by projecting the matching ratio of each node onto the cortical surface of a randomly picked subject, obtaining a visual indication of the localization of the regions that have been more or less frequently correctly matched. Projecting this information directly on the cortical surface provides insights into the spatial organization of the errors and of the cor- rect matches. Statistical Analysis In order to understand the differences between the alignments obtained with WL-align and FAQ, statistical analyses were performed with an alpha of 0.05 in all experiments. A separate analysis was performed for each of the four similarity metrics presented in the previous section. First, for each atlas and pair of subjects we computed an alignment with WL-align and FAQ. For each atlas, we compared the distributions of the values of the similarity metric computed on the alignments obtained with the two techniques using the nonparametric paired-samples Wilcoxon signed-rank test (Wilcoxon, 1945). RESULTS Experiments We processed the data of 100 unrelated subjects from the HCP database, obtaining the struc- tural brain networks as detailed in the Methods section. For each of the 100 subjects we Network Neuroscience 722 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . t / / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes considered 23 parcellations (Desikan, Glasser, Gallardo × 11, Schaefer × 10), obtaining 2,300 weighted graphs. For each parcellation, we retrieved a network alignment between each pair of subjects using WL-align and FAQ. The ability of WL-align to retrieve the correct brain- alignment map was quantitatively evaluated by means of four similarity measures. First, a novel measure of similarity between brain networks called graph Jaccard index was introduced in the Theory section as an adaptation of the concept of Jaccard index between sets. While be- having in a way that is similar to the commonly used correlation index defined in Equation 4, the graph Jaccard index has the property of defining a metric in the space of connectomes. This is a remarkable property in the context of modern data science, as many standard ma- chine learning techniques can be applied only in metric spaces. The second considered sim- ilarity measure is the aforementioned correlation index defined in Equation 4, also known as cosine similarity. The third similarity measure is the Frobenius distance defined in Equation 3, which actually is a dissimilarity measure; therefore connectomes showing higher Frobenius distance are less similar and vice versa. The node matching ratio defined in Equation 10 is the last considered similarity measure. Comparison Between Similarity Measures Each employed similarity metric answers a specific question. The node matching ratio corre- sponds to what the expression suggests; namely, it counts how many nodes were correctly matched and normalizes the result by the number of nodes in the graph. The other similarity measures have less intuitive definitions. For this reason, and in order to assess the intracohort similarity of the connectomes, we measured how much the connectomes of the subjects in the considered datasets are similar to each other with respect to each metric and each parcella- tion. We recall that the dataset contains only healthy unrelated subjects that do not exhibit any family structure (WU-Minn Human Connectome Project Consortium, 2017). This allows us to compare how the within-group similarity reacts to the change in resolution and type of the used parcellation. For each parcellation, Figure 4 shows how similar the subjects are with re- spect to the graph Jaccard index, the Frobenius norm, and correlation. In particular, the figure reports for each parcellation the average similarity across all the pairs of subjects, which can be computed from the ground truth matching that is granted by the fact that each network is defined on a known set of nodes. Despite using the ground truth matching, the graphs are not expected to exhibit perfect similarity (i.e., J = 1, FRO = 0, or C = 1), as their edge weights are subject-specific. This specificity is what determines the intracohort variability that is taken into account into the J ratio similarity metric defined in Equation 12. The most noticeable fact is that the graph Jaccard index and the correlation show an inverted trend with respect to the one of the Frobenius norm. A higher number of parcels give both lower Jaccard/correlation index and lower Frobenius distance, which a priori is counterintuitive. This phenomenon is attrib- utable to the fact that the Frobenius norm is incapable of capturing the relative difference be- tween edge weights and instead considers only the absolute difference between them. As a matter of fact, parcellations with a higher number of parcels will create brain networks with lower edge weights, since the same amount of connectivity (i.e., the same number of stream- lines) is distributed among a number of edges that grow quadratically with the number of re- gions. For this reason, the absolute value of the edge weights will be lower, giving also a lower absolute difference. On the contrary, the graph Jaccard index and the correlation, which are able to capture the relative difference between edge weights, show lower similarity values between brain networks obtained with a higher number of parcels compared with brain net- works obtained with a lower number of parcels. This difference suggests that the graph Jaccard index and the correlation mitigate the influence of the number of parcels in the estimation of Network Neuroscience 723 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . t / / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes Figure 4. Each point shows the average similarity between every pair of subjects in the considered cohort measured on connectomes ob- tained with a specific parcellation. The alignment used is the one defined by the ground truth, which in our experiments is known a priori. All panels show the similarity measure as a function of the number of parcels of the considered atlas. A higher graph Jaccard index and correlation corresponds to higher similarity. On the contrary, a higher Frobenius norm corresponds to lower similarity. In order to keep the intuition that higher is better, the y-axis of the Frobenius norm is flipped. l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / t / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 the similarity between the compared brain networks. Another observation can be done on the singular nature of the Desikan and Glasser parcellations. When measured with the GJI and the correlation, both of these parcellations exhibit an intracohort similarity in line with the one of the Gallardo parcellation at the corresponding resolutions. Computing Brain Alignments With WL-Align In this work, the concept of similarity between networks was used as a proxy for the quality of a brain alignment, since a good graph matching is expected to correspond to a higher simi- larity between the aligned graph and the ground truth. A separate analysis was performed for each of the 23 considered parcellations. First, an alignment was computed between each pair of subjects with the proposed technique WL-align and the state-of-the-art algorithm FAQ, then the similarity between the aligned network and the ground truth network was computed with the similarity measures listed in the Methods section. The node matching ratio (NMr) tells the proportion of nodes that were correctly matched by the alignment. This measure does not give any information about the topological differences between the original and the aligned graph, but it gives an important insight on how many nodes are correctly labeled, which may be of fundamental importance in connectomic studies where the regions are associated with a spe- cific function of the brain. The second metric used is the Jaccard similarity index introduced and described in this paper, while the third metric employed is the Jaccard index ratio. The latter measures how the Jaccard index performed with respect to the Jaccard index of the ground truth matching shown in Figure 4, which is known a priori from the design of the ex- periment. It differs from the raw Jaccard index in the sense that it takes into account the com- plexity of the alignment problem, which we showed in the previous section to be more difficult when the number of parcels is higher. A final comparison was made using the Frobenius distance, which is what the FAQ algorithm is designed to minimize. This makes it particularly interesting since we expect FAQ to give Frobenius distance that is less or equal to the one obtained with WL-align. In the context of this work, the simplest nontrivial alignment to be re- Subject-wise analysis. trieved is the one between the brain network of a subject and its randomly permuted version. Network Neuroscience 724 Atlas-based topological differences in structural connectomes In this case, a good alignment algorithm is expected to always retrieve the ground truth align- ment. In Figure 5 we report the average similarity between the ground truth and the obtained alignment. We notice that WL-align consistently achieves the best possible performance with respect to all the considered metrics. In particular, the naive metric of the node matching ratio always gives similarity equal to 1, meaning that WL-align correctly labels all the nodes when- ever a structural brain network is aligned against a randomly permuted version of itself. These considerations are true for every parcellation. On the contrary, FAQ does not solve the self- alignment problem exactly. All the considered metrics highlight a poor performance of FAQ both in absolute terms and compared with WL-align. As a matter of fact, FAQ on average yields at most 40% of correctly matched nodes, while WL-align consistently gives 100% of correctly matched nodes. Also, different parcellations behave differently when FAQ is em- ployed; for instance, the Desikan parcellation gives lower Frobenius similarity with respect to the other parcellations but shows higher Jaccard index and node matching ratio. Full cohort analysis. When all the subjects are aligned with the permuted version of each other, the problem is more complicated. Even though we considered healthy subjects whose acqui- sition followed the same protocol and that have been processed in an identical way, the subject-specific differences and the intrinsic noise of the data yield estimated structural brain networks that are in practice different among each other, despite being substantially coherent. In order to assess the ability of the proposed alignment technique to overcome these differences and yield an alignment as close as possible to the ground truth, we considered all the align- ments between each pair of subjects, including the ones between a subject and a randomly permuted version of itself. The brain alignments obtained with WL-align are compared with the ones computed with FAQ and presented in Figure 6, which reports the average similarity between the obtained alignment and the ground truth alignment among all the possible pairs of subjects. The statistical significance of the differences between results obtained with WL-align and FAQ is assessed using the nonparametric paired-samples Wilcoxon signed-rank test (Wilcoxon, 1945). For the studied cohort, statistically significant differences are observed for each atlas and each employed similarity metric, as shown in section B of the Supporting Figure 5. The displayed results concern the alignment between the structural brain network of one subject and its randomly permuted ver- sion. Each panel shows one type of similarity between the aligned networks. Higher values of NMr, Jaccard index, and Jaccard index ratio correspond to higher similarity, whereas the Frobenius norm is higher when similarity is lower. In order to keep the intuition that higher is better, the y-axis of the Frobenius norm is flipped. In each panel, one point corresponds to the average (among subjects) similarity computed between brain networks obtained on a specific parcellation and aligned with one technique among WL-align and FAQ. We do not report the results for the J ratio since in this experiment its denominator J(m*) = 1, making the plot identical to the one of the graph Jaccard index. All four plots show the similarity as a function of the number of parcels in the considered atlas. Network Neuroscience 725 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / t / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d t . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Figure 6. The displayed results concern the alignment between the structural brain networks of each pair of subjects including the self-comparisons. Each panel shows one type of similarity be- tween the aligned brain networks. Higher values of NMr, Jaccard index, and Jaccard index ratio correspond to higher similarity, whereas the Frobenius norm is higher when similarity is lower. In order to keep the intuition that higher is better, the y-axis of the Frobenius norm is flipped. In each panel, one point corresponds to the averag e (among subjects) similarity computed between brain networks obtained on a specific parcellation and aligned with one technique among WL-align and FAQ. All four plots show the similarity as a function of the number of parcels in the considered atlas. Information. In terms of Frobenius norm, the alignments obtained with WL-align and FAQ are very similar, with WL-align systematically showing slightly higher Frobenius similarity. The per- formance of the Gallardo parcellation is indistinguishable from that of the Schaefer parcella- tion. Also, the Glasser parcellation is in line with the Schaefer and Gallardo parcellations when the alignment is obtained with WL-align, while this is not true for the Desikan parcella- tion. Recalling that FAQ is a technique that is inherently based on the Frobenius norm and that WL-align is not, we can notice that WL-align gives a brain alignment that also satisfies the op- timality criteria of FAQ, additionally to its own. A second thing that we can notice about the Frobenius norm is that it exhibits the same phenomenon as in Figure 4, where the Frobenius similarity increases with the number of parcels. This phenomenon appears for the same reason as before; namely, the Frobenius norm does not capture the relative difference between the edge weights in the compared networks. All the other employed similarity metrics suggest that WL-align has superior performance with respect to FAQ. While FAQ has almost identical per- formances when applied on the Gallardo and the Schaefer parcellations, WL-align shows Network Neuroscience 726 Atlas-based topological differences in structural connectomes relevant and previously unobserved differences between the performances of the two. In par- ticular the Gallardo parcellation allows retrieval of better alignments with respect to the Schaefer parcellation. This may be because we are studying structural connectivity, therefore the use of a function-based parcellation like that of Schaefer may affect the quality of the align- ment when compared with the structural connectivity computed on a structure-based parcella- tion like the one of Gallardo. Looking at the behavior of the Desikan and the Glasser parcellation, we notice two different scenarios. The Glasser parcellation shows Jaccard similar- ity slightly lower than the one of the Gallardo parcellation but still higher than Schaefer’s, sug- gesting that the multimodal nature of the atlas allows us to capture, at least in part, the structural connectivity features that we are looking at. This contrast is evident only when WL-align is em- ployed. The Desikan parcellation behaves differently. While exhibiting lower performance with FAQ, when the WL-align is employed it emerges as a slightly superior parcellation with respect to the NMr, the GJI, and the J ratio. We finally notice that atlases with more than 400 parcels all behave very similarly; namely, they reach a plateau in terms of Jaccard index, Jaccard index ratio, and node matching ratio. This is true both when WL-align and when FAQ are employed. The performance in this range is lower than the one in the 50–400 parcel range. Self-Matching Rate Figure 7 illustrates the self-matching rate for each region of nine example atlases, that is, the fraction of times that regions were correctly matched when aligning different brains represented l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Figure 7. Self-matching rate of the labeling per region for different atlases using WL-align. Atlases with 100 regions or fewer are illustrated in the first row. The second row illustrates atlases with approximately 300 regions, and the third row those with 1,000 regions. Network Neuroscience 727 Atlas-based topological differences in structural connectomes using the same atlas. It is clear that as the number of parcels is increased, the matching rate is reduced. This can be explained by the increased difficulty of the alignment problem, but also by a decrease in the signal-to-noise ratio of the connectomes driven by the reduction in parcel size. It is also interesting to note that the matching rate does not appear to be sym- metric across hemispheres. For example, the right inferior parietal region of the Desikan atlas obtains relatively high matching rate of roughly 0.8, whereas the contralateral region only ob- tains roughly 0.4. This analysis gives important insights into the type of errors that are made by WL-align. In particular, it shows that the incorrect matchings do not have a particular structure that can be related to the geometry and morphology of the brain, be it some regional concen- tration of errors or some consistent symmetry with respect to the hemispheres. DISCUSSION AND CONCLUSIONS Among the fundamental problems of network neuroscience at the scale of whole-brain struc- tural connectivity, finding correspondences between brain regions and quantitatively assessing the similarity between brain networks are particularly important when it comes to considering massive heterogeneous datasets and modern data science techniques. In this work we consid- ered these two problems in relation to the unresolved question concerning the choice of the parcellation for structural connectivity studies. We proposed and analyzed a similarity index between brain networks, inspired by the Jaccard index between sets, that behaves in a similar way to the classical correlation index. Additionally, it enjoys the remarkable property of defining a metric in the space of connec- tomes, which is interesting both from the theoretical point of view and for data science appli- cations. The proposed graph Jaccard index was shown to be less affected by the number of regions in the chosen parcellation than the Frobenius distance, which is one example of (dis) similarity index from the class of norm-based distances. The second object introduced in this paper is WL-align, a novel algorithm that allows us to find the graph alignment between two brain networks. It relies solely on topological features of the brain network, which makes it particularly suitable for being applied also outside the do- main of network neuroscience. When WL-align is used in our experiments in order to retrieve the alignment between a network and a permuted version of itself, it gives the exact solution. This does not happen when the main competitor FAQ is employed. The superior performance of WL-align is also evident when brain networks of different subjects are aligned. In this case, the WL-align algorithm was shown to retrieve brain alignments that are closer to the ground truth with respect to the alignments obtained by FAQ, and we showed that the difference be- tween the WL-align and the FAQ alignments is statistically significant in the studied population. Notice that as it is designed, the WL-align algorithm builds on the construction of a feature vector for each node of the graph, which is then used as an edge weight in an assignment prob- lem on a bipartite graph. This does not include any prior knowledge other than the topological similarity between the two networks to be aligned. The analysis provided in this work was in- tentionally constrained to the pure topological comparison of networks. Nevertheless, it would be possible to extend the feature vector defined in WL-align with any prior of geometrical, spa- tial, anatomical, or connectomic nature or to add any constraints in the assignment problem on the bipartite graph. Future work will be devoted to the design of these constraints and features. The proposed WL-align algorithm can be further adapted to work with types of networks other than the structural networks studied in this work, which are undirected and have nonneg- ative edge weights. The most intuitive way to adapt WL-align is to change the way in which the node signatures are defined, then set up the bipartite graph and find the matching with the Network Neuroscience 728 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d t . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes Hungarian algorithm in the canonical way. A first interesting case is represented by weighted networks having both positive and negative weights. This is the typical case of functional con- nectivity studies, where the connectivity between regions is evaluated as the correlation (i.e., wij 2 [−1, 1]) between the activation in different regions (Van Den Heuvel & Pol, 2010). As we defined it in this work, WL-align would select the most relevant d nodes in an unpredictable way because of the presence of negative-valued entries in Equation 9. A possible adaptation of it would be to select the relevant edges performing the breadth-first search ignoring the sign of the weights, then evaluating the corresponding entries of the WL signature using the signed edge weights in Equation 9. Another possible adaptation would require the decomposition of − An, where Ap is the positive part of the the adjacency matrix of the network as Adj(A) = Ap matrix and An is the negative part of the matrix. Notice that the graphs corresponding of both Ap and An will have nonnegative edge weights. For each node, the WL signatures obtained from Ap and An can be concatenated, then used in the canonical way. Another interesting case is rep- resented by directed networks, which in the context of brain imaging represent the concept of effective connectivity (Friston, 2011). Here, the only further adaptation that would be required is a careful definition of the breadth-first search that gives the selection and the order of nodes that are used for defining the WL signature. For directed positive-weighted network, the algo- rithm works as it is, while for directed networks with signed weights it would require the adap- tations mentioned for the case of functional connectivity. Finally, we discuss the adaptation of WL-align to temporal networks. This type of graph has gained much interest in the context of brain imaging since the concept of dynamic functional connectome (Preti, Bolton, & Van De Ville, 2017) has been introduced and the consequent definition of specific tools for the graph- theoretical analysis of these time-dependent networks (Sizemore & Bassett, 2018). In this case, at least two options can be explored: First, one could concatenate the WL signatures of each node obtained at each time point, then run WL-align in the canonical way. Alternatively, it would be possible to perform the breadth-first search by taking into account the temporal com- ponent, hence traversing the graph in both space and time. An important instance of the graph matching problem that we did not consider in this work corresponds to when the two networks that are being aligned have different numbers of nodes. Being a generalization of a graph isomorphism test, WL-align does not appear to be trivially adaptable to this case. A possible solution would be to employ some dimensionality reduction technique (e.g., clustering via community detection) in the larger graph to reduce the number of nodes to the one of the smaller graph, then use WL-align to retrieve the wanted alignment. Some remarkable conclusions concerning the parcellations to be used in structural brain connectivity studies can be drawn from the ability of WL-align to find the correct alignment between two brain networks. First, the function-based parcellation of Schaefer is a poorer choice than the structure-based parcellation of Gallardo, the multimodal parcellation of Glasser, and the morphological parcellation of Desikan. This was expected from the fact that the whole study is centered on measuring structural connectivity, hence the choice of a function-based parcellation was never expected to be optimal from any point of view. Allowing expression of this concept quantitatively is one of the merits of WL-align. A second remarkable aspect is the performance of the Desikan atlas, which gave better results in terms of alignability than any other parcellation of any granularity. For this reason, whenever a study is designed using a coarse parcellation of the cortex (in the 50–200 parcel range), one should con- sider using the Desikan atlas as a first choice. Not only would it be a highly reliable choice that has been consistently used throughout time in the community, but with this study we showed that it would also allow definition of brain networks with more consistent topological features, in particular those captured by WL-align. As far as brain atlases with a higher number of parcels are Network Neuroscience 729 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / t / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d t . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes concerned, we showed that parcellations with a number of parcels in the range of more than 400 have lower performance in terms of GJI and NMr. However, when the intersubject variability is taken into account in the evaluation of the similarity, as for the case of the Jaccard index ratio, we see that the performance is nearly constant for atlases with more than 300 parcels. The change in performance that we observe with the growing resolution of the atlas could also be due to the number of streamlines employed in the tractography pipeline, which could be adapted to the atlas used, but in practice is the same for every atlas at each resolution. On the other hand, the standardized tractography pipeline (including the identical number of streamlines in each tractogram) is what allowed us to present a comprehensive analysis and comparison of the performance across resolutions. In order to disambiguate this point, it would first be necessary to analyze how the strongest connections in the network (hence those con- sidered by WL-align) are affected by the number of tracked streamlines. An alternative solution could be to employ a tractography filtering technique such as SIFT2 (Smith, Tournier, Calamante, & Connelly, 2015), COMMIT (Daducci, Dal Palù, Lemkaddem, & Thiran, 2014), or LiFE (Pestilli, Yeatman, Rokem, Kay, & Wandell, 2014) in order to mitigate the lim- ited reliability of streamline count as a proxy of axonal connectivity (Jbabdi & Johansen-Berg, 2011). Given that tractography filtering techniques have nonnegligible effects on the topology of structural connectomes (Frigo et al., 2020), an independent analysis is due in order to assess how their use affects the alignability of connectomes. Notice that in our analysis we used the defined similarity metrics to assess which atlas yields connectomes with higher or lower robustness in a certain resolution range. This means that we could not have used the similarity argument to claim that, for instance, the Desikan atlas (68 parcels) should in general be preferred to the Gallardo 1000 atlas. In this sense, we highlight how the considered similarity metrics (GJI, Jr, NMr, and Fro) should not be used for selecting the appropriate resolution at which structural connectivity studies should be de- signed, but they provide a well-grounded tool for assessing which of the available atlases at the wanted resolution is most suitable for the considered type of study. As highlighted throughout the paper, this work analyzes the problems of parcellation selec- tion and brain alignment in the context of structural connectivity. Any conclusion we made should not be straightforwardly generalized to functional connectivity or effective connectivity studies, which would require a separate analysis that was out of the scope of this work. ACKNOWLEDGMENTS The authors would like to thank Dr. Guillermo Gallardo for help in computing the Gallardo parcellation and Professor Joshua T. Vogelstein for the discussion on the use of FAQ. Also, we are grateful to the OPAL infrastructure from Université Côte d’Azur and Inria Sophia Antipolis– Méditerranée “NEF” computation platform for providing resources and support. Data were provided in part by the Human Connectome Project, WU-Minn Consortium (principal inves- tigators: David Van Essen and Kamil Ugurbil; 1U54MH091657) funded by the 16 NIH Institutes and Centers that support the NIH Blueprint for Neuroscience Research; and by the McDonnell Center for Systems Neuroscience at Washington University. DATA AVAILABILITY The data and code used in this work are all available at open repositories, as indicated in the text. We uploaded the code used and the obtained connectomes and alignments on the Open Science Framework. They can be found at this link: https://osf.io/depux/ (Frigo & Cruciani, 2020). Network Neuroscience 730 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . t / / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes SUPPORTING INFORMATION Supporting information for this article is available at https://doi.org/10.1162/netn_a_00199. AUTHOR CONTRIBUTIONS Matteo Frigo: Conceptualization; Data curation; Formal analysis; Investigation; Methodology; Software; Visualization; Writing – original draft; Writing – review & editing. Emilio Cruciani: Conceptualization; Data curation; Formal analysis; Investigation; Methodology; Software; Visualization; Writing – original draft; Writing – review & editing. David Coudert: Methodology; Supervision; Writing – review & editing. Rachid Deriche: Funding acquisition; Methodology; Supervision; Writing – review & editing. Emanuele Natale: Conceptualization; Formal analysis; Investigation; Methodology; Project administration; Software; Writing – orig- inal draft; Writing – review & editing. Samuel Deslauriers-Gauthier: Conceptualization; Data curation; Formal analysis; Investigation; Methodology; Project administration; Software; Visualization; Writing – original draft; Writing – review & editing. FUNDING INFORMATION Rachid Deriche, Matteo Frigo, and Samuel Deslauriers-Gauthier, H2020 European Research Council (https://dx.doi.org/10.13039/100010663), Award ID: 694665. REFERENCES Ayache, N., & Faverjon, B. (1987). Efficient registration of stereo images by matching graph descriptions of edge segments. International Journal of Computer Vision, 1(2), 107–131. https:// doi.org/10.1007/BF00123161 Barak, B., Chou, C.-N., Lei, Z., Schramm, T., & Sheng, Y. (2019). (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in neural information processing systems 32 (pp. 9190–9198). Curran Associates, Inc. Retrieved from https://papers.nips.cc/paper /9118-nearly-efficient-algorithms-for-the-graph-matching-problem -on-correlated-random-graphs.pdf. Bayati, M., Gleich, D. F., Saberi, A., & Wang, Y. (2013). Message-passing algorithms for sparse network alignment. ACM Transactions on Knowledge Discovery from Data, 7(1), 3:1–3:31. https://doi.org/10 .1145/2435209.2435212 Becker, C. O., Pequito, S., Pappas, G. J., Miller, M. B., Grafton, S. T., Bassett, D. S., & Preciado, V. M. (2018). Spectral mapping of brain functional connectivity from diffusion imaging. Scientific Reports, 8, 1411. https://doi.org/10.1038/s41598-017-18769-x, PubMed: 29362436 Brodmann, K. (1909). Vergleichende lokalisationslehre der gros- shirnrinde in ihren prinzipien dargestellt auf grund des zellen- baues. Leipzig: Barth. Charikar, M. S. (2002). Similarity estimation techniques from rounding algorithms. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (pp. 380–388). New York, NY: Association for Computing Machinery. https://doi.org/10 .1145/509907.509965 Chung, J., Pedigo, B. D., Bridgeford, E. W., Varjavand, B. K., Helm, H. S., & Vogelstein, J. T. (2019). GraSPy: Graph statistics in Python. Journal of Machine Learning Research, 20(158), 1–7. Retrieved from https://jmlr.org/papers/v20/19-490.html. Chung, M. K., Lee, H., Solo, V., Davidson, R. J., & Pollak, S. D. (2017). Topological distances between brain networks. In International Workshop on Connectomics in Neuroimaging (Vol. 10511, pp. 161–170). https://doi.org/10.1007/978-3-319-67159-8_19 Conte, D., Foggia, P., Sansone, C., & Vento, M. (2004). Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(03), 265–298. https://doi.org/10.1142/S0218001404003228 Daducci, A., Dal Palù, A., Lemkaddem, A., & Thiran, J.-P. (2014). Commit: Convex optimization modeling for microstructure informed tractography. IEEE Transactions on Medical Imaging, 34(1), 246–257. https://doi.org/10.1109/ TMI.2014.2352414, PubMed: 25167548 Desikan, R. S., Ségonne, F., Fischl, B., Quinn, B. T., Dickerson, B. C., Blacker, D., … Killiany, R. J. (2006). An automated labeling system for subdividing the human cerebral cortex on MRI scans into gyral based regions of interest. NeuroImage, 31(3), 968–980. https://doi .org/10.1016/j.neuroimage.2006.01.021, PubMed: 16530430 Deslauriers-Gauthier, S., Zucchelli, M., Frigo, M., & Deriche, R. (2020). A unified framework for multimodal structure–function mapping based on eigenmodes. Medical Image Analysis, 66. https://doi.org/10.1016/j.media.2020.101799, PubMed: 32889301 Feizi, S., Quon, G., Mendoza, M., Medard, M., Kellis, M., & Jadbabaie, A. (2019). Spectral alignment of graphs. IEEE Transactions on Network Neuroscience 731 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / t / e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes Network Science and Engineering, 7(3), 1182–1197. https://doi.org /10.1109/TNSE.2019.2913233 Fischl, B. (2012). FreeSurfer. NeuroImage, 62(2), 774–781. https://doi.org/10.1016/j.neuroimage.2012.01.021, PubMed: 22248573 Frigo, M., & Cruciani, E. (2020). Brain alignment, OSF, https://osf.io /depux. Frigo, M., Deslauriers-Gauthier, S., Parker, D., Ismail, A. A. O., Kim, J. J., Verma, R., & Deriche, R. (2020). Diffusion MRI trac- tography filtering techniques change the topology of structural connectomes. Journal of Neural Engineering, 17(6), 065002. h t t p s : / / d o i . o r g / 1 0 . 1 08 8 / 1 7 4 1 - 2 5 5 2 / a b c 2 9 b, P ub Me d: 33075758 Friston, K. J. (2011). Functional and effective connectivity: A re- view. Brain Connectivity, 1(1), 13–36. https://doi.org/10.1089 /brain.2011.0008, PubMed: 22432952 Gallardo, G., Gayraud, N., Deriche, R., Clerc, M., Deslauriers- Gauthier, S., & Wassermann, D. (2018). Solving the cross- subject parcel matching problem using optimal transport. In International Conference on Medical Image Computing and Computer-Assisted Intervention (Vol. 11070, pp. 836–843). Granada, Spain. https://doi.org/10.1007/978-3-030-00928-1_94 Gallardo, G., Wells, W., Deriche, R., & Wassermann, D. (2018). Groupwise structural parcellation of the whole cortex: A logistic random effects model based approach. NeuroImage, 170, 307–320. https://doi.org/10.1016/j.neuroimage.2017.01.070, PubMed: 28161314 Glasser, M. F., Coalson, T. S., Robinson, E. C., Hacker, C. D., Harwell, J., Yacoub, E., … Van Essen, D. C. (2016). A multi-modal parcella- tion of human cerebral cortex. Nature, 536, 171–178. https://doi .org/10.1038/nature18933, PubMed: 27437579 Glasser, M. F., Sotiropoulos, S. N., Wilson, J. A., Coalson, T. S., Fischl, B., Andersson, J. L., … Jenkinson, M. (2013). The minimal preprocessing pipelines for the Human Connectome Project. N e u r o I m a g e , 8 0 , 1 0 5 – 1 2 4 . h t t p s : / / d o i . o r g / 1 0 . 1 0 1 6 / j .neuroimage.2013.04.127, PubMed: 23668970 Hagmann, P. (2005). From diffusion MRI to brain connectomics (Unpublished doctoral dissertation, EPFL, Lausanne, Switzerland). Hayhoe, M., Barreras, F., Hassani, H., & Preciado, V. M. (2019). SPECTRE: Seedless network alignment via spectral centralities. arXiv:1811.01056. Heimann, M., Shen, H., Safavi, T., & Koutra, D. (2018). REGAL: Representation learning-based graph alignment. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management - CIKM ’18 (pp. 117–126). Torino, Italy: ACM Press. https://doi.org/10.1145/3269206.3271788 Jacobi, C. G. J. (1890). The reduction to normal form of a non-normal system of differential equations. De aequationum differentialium sys- temate non normali ad formam normalem revocando. III. C. G. J. Jacobi manuscriptis posthumis in medium protulit A. Clebsch. Jbabdi, S., & Johansen-Berg, H. (2011). Tractography: Where do we go from here? Brain Connectivity, 1(3), 169–183. https://doi.org /10.1089/brain.2011.0033, PubMed: 22433046 Jeurissen, B., Tournier, J.-D., Dhollander, T., Connelly, A., & Sijbers, J. (2014). Multi-tissue constrained spherical deconvolu- tion for improved analysis of multi-shell diffusion MRI data. NeuroImage, 103, 411–426. https://doi.org/10.1016/j .neuroimage.2014.07.061, PubMed: 25109526 Korula, N., & Lattanzi, S. (2014). An efficient reconciliation algo- rithm for social networks. Proceedings of the VLDB Endowment, 7(5), 377–388. https://doi.org/10.14778/2732269.2732274 Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), 83–97. https://doi.org/10.1002/nav.3800020109 Li, C., Wang, S., Yu, P. S., Zheng, L., Zhang, X., Li, Z., & Liang, Y. (2018). Distribution distance minimization for unsupervised user identity linkage. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (pp. 447–456). Torino, Italy: Association for Computing Machinery. https://doi.org/10.1145/3269206.3271675 Liu, L., Cheung, W. K., Li, X., & Liao, L. (2016). Aligning users across social networks using network embedding. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (pp. 1774–1780). New York, NY: AAAI Press. Retrieved from https://www.ijcai.org/ Proceedings/16 /Papers/254.pdf. Mars, R., Verhagen, L., Gladwin, T., Neubert, F., Sallet, J., & Rushworth, M. (2016). Comparing brains by matching connec- tivity profiles. Neuroscience and Biobehavioral Reviews, 60, 90–97. https://doi.org/10.1016/j.neubiorev.2015.10.008, PubMed: 26627865 Nassar, H., Veldt, N., Mohammadi, S., Grama, A., & Gleich, D. F. (2018). Low rank spectral network alignment. In Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW ’18 (pp. 619–628). Lyon, France: ACM Press. https://doi .org/10.1145/3178876.3186128 Osmanlıog(cid:1)lu, Y., Tunç, B., Parker, D., Elliott, M. A., Baum, G. L., Ciric, R., … Verma, R. (2019). System-level matching of structural and functional connectomes in the human brain. NeuroImage, 199, 93–104. https://doi.org/10.1016/j.neuroimage.2019.05 .064, PubMed: 31141738 Parisot, S., Arslan, S., Passerat-Palmbach, J., Wells, W., & Rueckert, D. (2015). Tractography-driven groupwise multi-scale parcella- tion of the cortex. Information Processing in Medical Imaging, 24, 600–612. https://doi.org/10.1007/978-3-319-19992-4_47, PubMed: 26221706 Pestilli, F., Yeatman, J. D., Rokem, A., Kay, K. N., & Wandell, B. A. (2014). Evaluation and statistical inference for human connec- tomes. Nature Methods, 11(10), 1058–1063. https://doi.org/10 .1038/nmeth.3098, PubMed: 25194848 Preti, M. G., Bolton, T. A., & Van De Ville, D. (2017). The dynamic functional connectome: State-of-the-art and perspectives. NeuroImage, 160, 41–54. https://doi.org/10.1016/j.neuroimage .2016.12.061, PubMed: 28034766 Rasero, J., Pellicoro, M., Angelini, L., Cortes, J. M., Marinazzo, D., & Stramaglia, S. (2017). Consensus clustering approach to group brain connectivity matrices. Network Neuroscience, 1(3), 242–253. https://doi.org/10.1162/NETN_a_00017, PubMed: 29601048 Schaefer, A., Kong, R., Gordon, E. M., Laumann, T. O., Zuo, X.-N., Holmes, A. J., … Yeo, B. T. (2017). Local-global parcellation of the human cerebral cortex from intrinsic functional connectivity MRI. Cerebral Cortex, 28(9), 3095–3114. https://doi.org/10.1093 /cercor/bhx179, PubMed: 28981612 Singh, R., Xu, J., & Berger, B. (2008). Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Network Neuroscience 732 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Atlas-based topological differences in structural connectomes Sciences, 105(35), 12763–12768. https://doi.org/10.1073/pnas .0806627105, PubMed: 18725631 Sizemore, A. E., & Bassett, D. S. (2018). Dynamic graph metrics: Tutorial, toolbox, and tale. NeuroImage, 180, 417–427. https:// doi.org/10.1016/j.neuroimage.2017.06.081, PubMed: 28698107 Smith, R. E., Tournier, J.-D., Calamante, F., & Connelly, A. (2012). Anatomically-constrained tractography: Improved diffusion MRI streamlines tractography through effective use of anatomical in- formation. NeuroImage, 62(3), 1924–1938. https://doi.org/10 .1016/j.neuroimage.2012.06.005, PubMed: 22705374 Smith, R. E., Tournier, J.-D., Calamante, F., & Connelly, A. (2015). Sift2: Enabling dense quantitative assessment of brain white matter connectivity using streamlines tractography. NeuroImage, 119, 338–351. https://doi.org/10.1016/j.neuroimage.2015.06 .092, PubMed: 26163802 Sporns, O., Tonomi, G., & Kötter, R. (2005). The human connectome: A structural description of the human brain. PLoS Computational Biology, 1, 245–251. https://doi.org/10.1371/journal.pcbi .0010042, PubMed: 16201007 Takerkart, S., Auzias, G., Thirion, B., & Ralaivola, L. (2014). Graph- based inter-subject pattern analysis of fMRI data. PLoS ONE, 9(8), e104586. https://doi.org/10.1371/journal.pone.0104586, PubMed: 25127129 Tournier, J.-D., Smith, R., Raffelt, D., Tabbara, R., Dhollander, T., Pietsch, M., … Connelly, A. (2019). MRtrix3: A fast, flexible and open software framework for medical image processing and visualisation. NeuroImage, 202, 116137. https://doi.org/10 .1016/j.neuroimage.2019.116137, PubMed: 31473352 Van Den Heuvel, M. P., & Pol, H. E. H. (2010). Exploring the brain network: A review on resting-state fMRI functional connectivity. European Neuropsychopharmacology, 20(8), 519–534. https:// doi.org/10.1016/j.euroneuro.2010.03.008, PubMed: 20471808 Van Essen, D. C., Smith, J., Glasser, M. F., Elam, J., Donahue, C. J., Dierker, D. L., … Harwell, J. (2017). The brain analysis library of spatial maps and atlases (BALSA) database. NeuroImage, 144, 270–274. https://doi.org/10.1016/j.neuroimage.2016.04.002, PubMed: 27074495 Van Essen, D. C., Ugurbil, K., Auerbach, E., Barch, D., Behrens, T., Bucholz, R., … WU-Minn HCP Consortium. (2012). The Human Connectome Project: A data acquisition perspective. NeuroImage, 62(4), 2222–2231. https://doi.org/10.1016/j .neuroimage.2012.02.018, PubMed: 22366334 Venkatesh, M., Jaja, J., & Pessoa, L. (2020). Comparing functional connectivity matrices: A geometry-aware approach applied to participant identification. NeuroImage, 207, 116398. https://doi .org/10.1016/j.neuroimage.2019.116398, PubMed: 31783117 Villareal-Haro, J. L., Ramirez-Manzanares, A., & Pichardo-Corpus, J. A. (2020). A community-based topological distance for brain- connectome classification. Journal of Complex Networks, 8(4), cnaa034. https://doi.org/10.1093/comnet/cnaa034 Vogelstein, J. T., Conroy, J. M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, E. T., … Priebe, C. E. (2015). Fast approximate qua- dratic programming for graph matching. PLoS ONE, 10(4). https:// doi.org/10.1371/journal.pone.0121002, PubMed: 25886624 Weisfeiler, B. Y., & Leman, A. A. (1968). The reduction of a graph to canonical form and the algebra which appears therein. (English translation of the original paper published in Russian.) Retrieved from https://www.iti.zcu.cz/wl2018/pdf/wl_paper _translation.pdf. Wilcoxon, F. (1945). Individual comparisons by ranking methods. In Biometrics bulletin (Vol. 1, pp. 80–83). International Biometric Society. https://doi.org/10.2307/3001968 Wilson, R. C., & Zhu, P. (2008). A study of graph spectra for com- paring graphs and trees. Pattern Recognition, 41(9), 2833–2841. https://doi.org/10.1016/j.patcog.2008.03.011 WU-Minn Human Connectome Project Consortium. (2017). 1200 Subjects Data Release Reference Manual. Retrieved from https:// www.humanconnectome.org/storage/app/media/documentation /s1200/HCP_S1200_Release_Reference_Manual.pdf. Yeo, B. T. (2020). Computational Brain Imaging Group (CBIG) re- pository. Retrieved from https://github.com/ ThomasYeoLab / C B I G / t r e e / m a s t e r / s t a b l e _ p r o j ec t s / b r a i n _ p a r c el l a t i o n /Schaefer2018_LocalGlobal/Parcellations/HCP. Yeo, B. T., Krienen, F. M., Sepulcre, J., Sabuncu, M. R., Lashkari, D., Hollinshead, M., … Buckner, R. L. (2011). The organization of the human cerebral cortex estimated by intrinsic functional connec- tivity. Journal of Neurophysiology, 106(3), 1125–1165. https://doi .org/10.1152/jn.00338.2011, PubMed: 21653723 Network Neuroscience 733 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / t e d u n e n a r t i c e - p d l f / / / / / 5 3 7 1 1 1 9 6 0 4 8 0 n e n _ a _ 0 0 1 9 9 p d . t f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3

Télécharger le PDF