Network Alignment

Using graph topology to infer alignments between brain networks.

This work was done in collaboration with Emanuele Natale and has been published in (Frigo et al., 2021).

Brain atlases are central objects in network neuroscience, where the interactions between different brain regions are modeled as a graph called connectome. In structural connectomes, nodes are parcels from a predefined cortical atlas and edges encode the strength of the axonal connectivity between regions measured via diffusion Magnetic Resonance Imaging (MRI) tractography. We aimed at providing a novel perspective on the evaluation of brain atlases by modeling it as a network alignment problem, with the goal of tackling the following question: given an atlas, how robustly does it capture the network topology across different subjects? The answer to this question is thoroughly analysed in (Frigo et al., 2021) and in this page we present the methodological aspects of this analysis.

The assumption behind our experiments is that subjects from homogeneous cohorts produce connectomes with very similar topology. We measured this similarity by means of how well the two brain networks of two subjects can be aligned.

The evaluation of the alignability of two networks is done by estimating an alignment map \(m\) between two graphs and computing the similarity between target and the alignment graph. For this reason we introduced two novel concepts arising as natural generalizations of previous ones: a similarity measure between weighted graphs called graph Jaccard index (GJI) that generalises the Jaccard index between sets and an alignment algorithm called WL-align that builds on top of the same heuristic of the Weisfeiler-Lehman graph isomorphism test.

Graph Jaccard Index

The graph Jaccard index (GJI) is a novel graph similarity measure between graphs based on the well-established Jaccard index between sets. Originally, the Jaccard index between sets has been defined as the ratio between the size of the overlap of the two sets over the size of their union.

\[J(A, B) = \frac{\left|A\cap B\right|}{\left|A\cup B\right|}\]

Notice that:

  • \(0\le J \le 1\).
  • \(J\sim 0\) : low similarity.
  • \(J\sim 1\) : high similarity.

In the forthcoming example, the two sets \(A\) and \(B\) have low similarity, since they share few elements compared to their cardinality.

Jaccard similarity index between two sets.

To define a similar concept of similarity between weighted graphs, we devised the Graph Jaccard Index (GJI). Instead of looking at elements of sets, we based the GJI on the edge weights of the two graphs. We then substituted the concepts of intersection and union with the concepts of minimum and maximum between edge weights. Given two weighted graphs defined on the same set of edges \(X = (V, E_x, W_x)\) and \(Y = (V, E_y, W_y)\), the GJI between them is defined as

\[J(G_1, G_2) = \frac{\sum_{e\in E} \min\left(W_x(e), W_y(e)\right)}{\sum_{e\in E} \max\left(W_x(e), W_y(e)\right)}\]

and the following figure shows an example of what this equation represents.

Jaccard similarity index between two graphs. The first term in the numerator and the denominator correspond to the minimum and maximum edge weight between nodes A and B in the two graphs. These two graphs have low GJI, therefore they are very dissimilar.

The GJI has some properties that make it an interesting tool for the evaluation of similarity between graphs.

  • It generalises the concept of similarity for less structured data (i.e., sets).
  • It applies to the graph isomorphism problem.
  • The interpretation is straightforward and simple.
  • The GJI induces a metric (1-J) in the space of weighted graphs.

WL-align

We devised WL-align, a new technique for aligning connectomes obtained by adapting the Weisfeiler-Lehman (WL) graph-isomorphism test.

An alignment between two graphs \(X = (V_x, E_x)\) and \(Y = (V_y, E_y)\) is a function \(m: V_x \to V_y\) that maps the nodes of a graph onto the nodes of another. A good alignment returns a graph that is isomorphic to the target.

The algorithmic approach to finding graph alignments is essentially composed of two steps:

  1. Embed each node in the two graphs in a suitable space associating a signature \(H_u\in\mathbb{R}^n\) to each node \(u\).
  2. Find correspondences between nodes in the embedding.

We designed a signature following the same principle of the Weisfeiler-Lehman graph-isomorphism test, namely considering that two isomorphic graphs have nodes that have the same “connectivity pattern” around them. We translated this concept into the definition of the WL-signature, which gives a description of the connectivity around a node by concatenating some features that rely uniquely on the edge weights in a bounded neighbourhood of depth \(d\) and width \(\ell\) of the node of which the signature is being computed. A precise definition of the obtained \(H_u\) can be found in (Frigo et al., 2021), but a visual intuition is hereafter displayed.

Construction of the WL signature of node u with depth d=2 and width l=2.

Once a signature has been computed for each node, a bipartite graph can be set up. Each part of the graph contains the nodes of one of the two graphs to align, and each edge node in one graph is connected to all the nodes of the other graph with an edge having weight equal to the euclidean distance between the signatures of the two nodes it connects. The alignment can then be obtained by computing the minimum weight bipartite matching with the Hungarian algorithm.

Bold edges correspond to the minimum weight bipartite matching between the blue and red graphs.

The devised technique goes under the name of WL-align.

References

  1. Frigo, Matteo, Cruciani, Emilio, Coudert, David, Deriche, Rachid, Natale, Emanuele, and Deslauriers-Gauthier, Samuel "Network alignment and similarity reveal atlas-based topological differences in structural connectomes". Network Neuroscience. 2021.