Keywords

1 Introduction

Connectomics, the study of connectivity in the brain, has become an indispensable tool in the analysis of brain network organization. With the advent of imaging techniques such as diffusion MRI or functional MRI, structural or functional connectivity of the brain regions can be modeled efficiently with connectomes, which are annotated graphs with nodes representing brain regions and edges denoting the relationship between region pairs. Graph theoretical analysis of connectomes has provided novel insights into the network organization of the healthy brain, widening our understanding of the relationship between brain and behavior. Additionally, it also introduced imaging biomarkers for neurological diseases and disorders in the brain along with useful information about their recovery patterns [8, 25].

Connectomic analysis studies that utilize graph-theoretical tools generally focus on summary metrics that quantify network properties such as centrality, local efficiency, small-worldness, or participation coefficient [22]. While making statistical analysis with these measures is useful for characterizing neurological patterns at the population level, such an approach is limited in two main aspects which become more crucial in the assessment of brain disorders. First, these standalone measures describing network structure do not reveal information on how much an individual connectome differ from the healthy controls, which is essential for quantifying the subject-specific brain condition. Second, such standard measures evaluate generic properties of networks and do not leverage disorder-specific information that can enhance diagnostic evaluation. On the other hand, standard measures such as Euclidean distance [18] or Pearson’s correlation [5] are commonly used to quantify similarity of a connectome (of possibly a patient) relative to a population (of controls) mainly by considering the edges independently. However, such standard measures are limited in not leveraging the connectivity information embedded into the network topology as well as not being specific to the disease.

Graph matching is a powerful technique for quantifying similarity between graphs by considering overall network topology in an optimization problem setup, which is well-studied and widely used in pattern recognition and computer vision over several decades [4]. Despite its strong potential, graph matching is seldom applied to connectomics [17], with matching-based measures recently starting to emerge to assess connectomic similarity [14] in healthy subjects [15] as well as in patients [13, 16]. Although graph matching methods presented in such studies provide subject-specific connectomic similarity scores, they are still generic measures that do not incorporate disease-specific information. Although learning over graphs was proposed using Graph Neural Networks in determining proper distance metrics for connectomes [12], such methods are prone to overfitting and lack interpretability, especially for diseases that are generally examined using datasets of limited sample size. Consequently, connectomic biomarkers that i) quantifying differences among connectomes, ii) that utilize network topology information while iii) allowing to be tuned for specific diseases with limited sample size are desirable.

In this work, we propose a graph matching based method to quantify connectomic similarity, which can be trained for diseases to provide a subject-specific score that offers better separation between patients and controls. We use graph edit distance (GED) to attain graph matching, where we train edit cost parameters using Markov Chain Monte Carlo (MCMC) to make our method disease-specific. We consider the average GED between an individual’s brain graph and the healthy control population as the measure assessing the state of the disease for that individual. We demonstrate the utility of our method over a moderate-to-severe traumatic brain injury (TBI) dataset to provide a connectomic measure for TBI. The contribution of our study is threefold. First, our score is subject-specific and it incorporates network topology information in the presence of pathology. Second, training of GED parameters provides us insights about which functional systems are affected more by the disease at the population level. Third, the proposed score can be used as a potential connectomic biomarker of the disease as it correlates well with clinical scores.

2 Methods

2.1 Graph Edit Distance

Human brain constitutes a network structure that can be represented as connectomes, which are simply graphs encoding structural or functional connectivity information of brain regions. The presence of neurological disorders commonly results in changes in the network topology of the brain, such as increased or decreased connectivity relative to a healthy subject. Consequently, measuring the connectomic dissimilarity of patients relative to healthy controls is of great importance in evaluating the effect of pathology.

Graph edit distance is a powerful graph matching technique that quantifies dissimilarity between two graphs \(G_p, G_q\) by calculating the minimum edit cost to transform \(G_p\) into \(G_q\) [7]. Edit cost in GED is accounted for by node insertion, deletion, and substitution operations, which is characterized by the amount of distortion that each operation introduces. These edit operations, also referred to as edit paths, reveal a correspondence between nodes of the two graphs. Since connectomes are special graphs where nodes correspond to brain regions that are based on the same anatomical atlas for all subjects, nodes in one graph are likely to get matched to their counterparts in another graph due to anatomical similarity across people. Structural differences due to subject-specific variations and alterations induced by pathology of neurological disorders, on the other hand, would lead to node mismatches, resulting in a larger graph edit distance.

Calculating edit cost requires defining proper cost functions for edit operations. Since neurological disorders can cause certain cognitive deficits that involve functional systems of the brain in varying degrees, the manifestation of structural alterations may be localized or widely distributed, and can be expected to differ by functional subnetworks rather than having a uniform effect over all nodes of the graph [8]. To capture such subnetwork dependent patterns at the population level, we define node substitution cost as the Manhattan distance between the node attributes weighted by a system-level dysfunction coefficient.

$$\begin{aligned} C(\mathbf{v}_i^p \rightarrow \mathbf{v}_j^q; {\varvec{\alpha }}) = \alpha _{s_i} \times \alpha _{s_j} \times d_{Manhattan}(\mathbf{v}_i^p, \mathbf{v}_j^q) = \alpha _{s_i} \times \alpha _{s_j} \times ||\mathbf{v}_i^p - \mathbf{v}_j^q||_1 \end{aligned}$$
(1)

where \(\mathbf{v}_i^p\) and \(\mathbf{v}_j^q\) represent ith and jth nodes in \(G_p\) and \(G_q\), respectively. Each node \(\mathbf{v}\) is annotated with an \(N_{node}\)-dimensional feature vector that represents its connectivity to the rest of the graph, where \(N_{node}\) is the number of nodes in the parcellation. The dysfunction coefficient \(\alpha _{s_i} > 0\) characterizes the population-level effect of an edit operation for the system that node i belongs to. The GED parameter \({\varvec{\alpha }} = \{\alpha _0, ..., \alpha _{N_{sys}}\}\) is an \(N_{sys}\)-dimensional vector representing the dysfunction coefficient for \(N_{sys}\) functional systems pre-defined by the atlas.

We define node insertion and deletion costs similarly, as the weighted Manhattan distance between the feature vector of the node and a zero vector.

$$\begin{aligned} C(\mathbf{\varnothing } \rightarrow \mathbf{v}_j^q; {\varvec{\alpha }}) = \alpha _{s_j}^2 \times d_{Manhattan}(\mathbf{0}, \mathbf{v}_j^q) = \alpha _{s_j}^2 \times ||\mathbf{v}_j^q||_1 \end{aligned}$$
(2)
$$\begin{aligned} C(\mathbf{v}_i^p \rightarrow \mathbf{\varnothing }; {\varvec{\alpha }}) = \alpha _{s_i}^2 \times d_{Manhattan}(\mathbf{v}_i^p, \mathbf{0}) = \alpha _{s_i}^2 \times ||\mathbf{v}_i^p||_1 \end{aligned}$$
(3)

Given the edit cost parameter \({\varvec{\alpha }}\), GED aims to find optimum edit path \(\mathcal {P}(G_p, G_q; {\varvec{\alpha }})\) that transforms graph \(G_p\) into \(G_q\) with minimum edit cost.

$$\begin{aligned} d_{GED}(G_p, G_q; {\varvec{\alpha }}) = \min _{(e_1, ... e_K)\in \mathcal {P}(G_p, G_q; {\varvec{\alpha }})}\sum _{k=1}^K C(e_k; {\varvec{\alpha }}) \end{aligned}$$
(4)

where \(e_k\) indicates an edit operation.

Utilizing the one-to-one mapping between nodes that ensues GED calculation, we calculate matching accuracy as the rate of correct matches of nodes between the two graphs [17].

$$\begin{aligned} A_{GED}|_{\mathcal {P}(G_p, G_q; {\varvec{\alpha }})} = \frac{\sum _{k=1}^{N_{node}} \delta (e_k = \mathbf{v}_k^p \rightarrow \mathbf{v}_k^q)}{N_{node}} \end{aligned}$$
(5)

where \(\delta (\cdot )=1\) if the edit path matches a node to its counterpart and 0 otherwise.

We calculate the GED for each subject relative to the healthy population and consider the average of these distances as the disease biomarker for each subject. Since the exact computation of GED is intractable, we use the Kuhn-Munkres algorithm to calculate an approximate solution to the problem [20].

2.2 Edit Cost Parameter Estimation

In order to tailor the similarity measure specifically for one brain disorder, we train our algorithm to learn the system-level dysfunction coefficient \({\varvec{\alpha }}\) by using the Metropolis-Hastings algorithm, a Markov chain Monte Carlo (MCMC) method. Our objective in training is based on our hypothesis that matching accuracy between a patient and a healthy control should be low due to distortions induced by disease while matching accuracy between healthy controls should be high due to a lack of pathology. This objective can be achieved by minimizing the following energy function:

$$\begin{aligned} E_d[\tilde{\varvec{\alpha }}, \mathbf{G}] = \frac{1}{N_p}\sum _{i = 1}^{N_p}\max \{0, -(\overline{A_{GED}}|_{\mathcal {P}(\mathbf{G_c}; \tilde{\varvec{\alpha }})} - A_{GED}|_{\mathcal {P}(G_{p_i}, \mathbf{G_c}; \tilde{\varvec{\alpha }})}) + \gamma \} \end{aligned}$$
(6)

where \(\mathbf{G}\) denotes the dataset of graphs, \(\overline{A_{GED}}|_{\mathcal {P}(\mathbf{G_c}; \tilde{\varvec{\alpha }})}\) is the mean of average matching accuracy of healthy controls while \(A_{GED}|_{\mathcal {P}(G_{p_i}, \mathbf{G_c}; \tilde{\varvec{\alpha }})}\) is the average matching accuracy of patient \(p_i\) relative to healthy controls. Maximizing \(E_d[\tilde{\varvec{\alpha }}, \mathbf{G}]\) encourages matching accuracy among controls to become higher than matching accuracy between patients and controls at least by a margin \(\gamma \). The estimated dysfunction coefficient \(\tilde{{\varvec{\alpha }}}\) is therefore tuned to capture disease-related distortion in the brain.

We further impose the following prior term to ensure that all dysfunction coefficients would be positive:

$$\begin{aligned} E_p[\tilde{\varvec{\alpha }}] = {\left\{ \begin{array}{ll} 0 &{} \text {if }\tilde{\alpha _i} > 0,\ \forall i \in \{0, .., N_{sys}\}\\ +\infty &{} \text {otherwise} \end{array}\right. } \end{aligned}$$
(7)

Thus, final objective function is defined as follows:

$$\begin{aligned} E[\tilde{\varvec{\alpha }}, \mathbf{G}] = E_d[\tilde{\varvec{\alpha }}, \mathbf{G}] + E_p[\tilde{\varvec{\alpha }}] \end{aligned}$$
(8)

We apply simulated annealing for the optimization with the temperature T controlling the annealing schedule. Current parameter \(\tilde{\varvec{\alpha }}^t\) will be updated by a new parameter \(\tilde{\varvec{\alpha }}^{t+1}\) with the acceptance rate:

$$\begin{aligned} a = \min \{1, \exp \{- \frac{E[\tilde{\varvec{\alpha }}^{t+1}, \mathbf{G}] - E[\tilde{\varvec{\alpha }}^t, \mathbf{G}]}{T}\}\} \end{aligned}$$
(9)

2.3 Interpretation of Dysfunction Coefficients

To interpret the estimated dysfunction coefficients, we highlight that the nodal structural alterations captured by the Manhattan distance between a subject and a healthy control would have two components: difference due to disease-induced pathology and non-disease-related difference due to subject-specific variations. Tuning GED for dysfunction coefficients could give us information about the vulnerability of systems to the disease. Intuitively, a larger dysfunction coefficient will discourage a node in a patient from matching to its counterpart in a healthy control. Likewise, a small dysfunction coefficient will encourage correct matching of nodes even with a large difference between two nodal features. Since our objective function maximizes matching accuracy within controls while minimizing matching accuracy between patients and controls, functional systems that are affected by the disease will have a larger dysfunction coefficient to encourage mismatches for patients. On the other hand, a region where non-disease-related difference is dominant will have a small dysfunction coefficient to improve matching accuracy for controls. Therefore, learning of dysfunction coefficients in MCMC is equivalent to estimating the distribution of pathology in connectomes at the systems level.

3 Experiments

3.1 Dataset and Preprocessing

We validate our method over a traumatic brain injury dataset consisting of 34 moderate-to-severe patients (12 female) and 35 healthy controls (9 female) that pass quality assurance, with the age of patients ranging from 18 to 65 years (mean = 33.9 years, std = 14.9 years), and the age of healthy controls ranging from 19 to 56 years (mean = 34.9 years, std = 10.3 years), respectively. Imaging scans are taken at 3 months post-injury. The Glasgow Outcome Scale-Extended (GOSE) is used to assess global functional outcome of the TBI patients at the time of imaging (range = [2, 8], mean = 5.1, std = 1.5).

Diffusion weighted imaging scans are acquired on a Siemens 3T TrioTim whole-body scanner with an 8-channel array head coil (single-shot, spin-echo sequence, TR/TE = 6500/84 ms, b = 1000 s/\(\text {mm}^2\), 30 directions, flip angle = \(90^{\circ }\), resolution = \(2.2 \times 2.2 \times 2.2\) mm). High-resolution T1-weighted anatomic images are also obtained using a 3D MPRAGE imaging sequence with TR = 1620 ms, TI = 950 ms, TE = 3 ms, flip angle = \(15^{\circ } \), 160 contiguous slices of 1.0 mm thickness, FOV = \(192 \times 256\,\text {mm}^2\), 1NEX, resolution = \(1 \times 1 \times 1\,\text {mm}\). 100 regions of interests from Schaefer atlas [21] and additional 16 subcortical regions are extracted to represent the nodes of the structural network (116 nodes in total). A mask is defined using voxels with an FA of at least 0.15 for each subject. We perform deterministic tractography to generate and select 10 million streamlines, which is seeded randomly within the mask. Angle curvature threshold of \(60 ^{\circ }\), and a minimum and maximum length threshold of 5 mm and 400 mm are applied, resulting in a \(116 \times 116\) adjacency matrix of weighted connectivity values, where each element represents the number of streamlines between regions. Eight functional systems are identified including 7 subnetworks as described in [24] and another for representing subcortical regions.

3.2 Experimental Setup

We conduct fivefold cross-validation to evaluate our method. Each testing set consists of 14 subjects and each training set consists of 55 subjects. In the training, 8 dysfunction coefficients are initialized with equal weights \({\tilde{\varvec{\alpha }}^0} = [1, ..., 1]\). We use Multivariate Gaussian distribution \({\varvec{\alpha }}^{t+1} \sim \mathcal {N}(\tilde{\varvec{\alpha }}^t | {\varvec{\varSigma }})\) with \(\sigma ^2 = 0.001\) as the transition probability for iteration \(t+1\) to generate new parameters. We set the margin as \(\gamma = 0.5\). The temperature for simulated annealing is initially set as \(T_0 = 0.01\) and scheduled to decrease as number of iteration \(t \ge 0\) increases, following the equation \(T = \frac{T_0}{\ln (t+1)}\). We set the maximum iterations of MCMC to be 100 for each fold.

In evaluating test subjects in each fold, we compare our proposed measure of GED with training of parameters (denoted GED-tr) with two commonly used connectomic similarity measures: Euclidean distance and Pearson’s distance (defined as \(1 - r_{Pearson}\)). We evaluate the effect of training dysfunction coefficients in GED-tr by contrasting it with the standard GED without parameter tuning (denoted GED-st). We normalized all four measure s by calculating z-score to make them comparable. All measures were validated at both population and subject-specific level. For the population analysis, we use Welch’s t-test to examine the group difference of the dissimilarity score between patients and healthy controls for each fold and use Hedges’ g method to estimate effect size. As each testing set is independent, p-values and effect sizes in the 5-fold study can be combined using Fisher’s method [6] and inverse variance-weighted average method [10]. For the subject-specific analysis, we use linear regression to examine the relationship between each measure and the GOSE score.

Fig. 1.
figure 1

Dissimilarity scores of subjects in each group (healthy controls and patients) with respect to healthy control population (values are normalized using z-score for comparison). Our proposed method GED-tr achieves the best separation by reducing variation of scores in controls and increasing the separation between patients and controls. Note that, effect sizes for significant group differences between patients and controls are shown above boxes, with significance level after Bonferroni correction being \(p\le 0.0125\).

Full size image

3.3 Results and Discussions

Population Analysis

Dissimilarity at Connectome Level. Dissimilarity of subjects relative to healthy controls is shown in Fig. 1 along with effect sizes of group differences between patients and controls. We observed that although all four dissimilarity measures show significant group differences between patients and controls (with \(p < 0.0125\), after Bonferroni multiple comparison correction), our proposed method GED-tr with parameter tuning demonstrates the largest group difference with an effect size of 1.19, achieving the best separation between patients and healthy controls on the TBI dataset. It is followed by Euclidean, GED-st, and Pearson distance with effect sizes of 0.97, 0.95, and 0.92, respectively. Comparing group differences between patients and controls for GED with and without training of parameters, we observe that GED-tr shows improvements in reducing the score range and variation in controls while preserving the score range for patients, highlighting the importance of training parameters for the disease. It is interesting to note that effect size of GED-st is similar to those of Euclidean and Pearson’s distance, which might indicate that, although standard GED considers network topology that is ignored by the other two measures, it does not improve sensitivity of the measure to the disease without parameter tuning. In summary, GED-tr achieving the best separation might be attributed to it combining the information embedded in network topology with tuning of the parameters for the disease.

Fig. 2.
figure 2

Dysfunction coefficients at functional systems level, with larger dysfunction coefficients indicating a dominant pathology effect at the associated functional systems. We observe large coefficient values for limbic and subcortical networks, which highlights their vulnerability to injury. Note that, dysfunction coefficients are normalized by the total sum of coefficients to show the relative vulnerability of the systems.

Full size image

System-Level Dysfunction Coefficients. We present the system-level dysfunction coefficients estimated by our algorithm for each functional system in Fig. 2. The limbic system and the subnetwork consisting of subcortical regions are shown to have the largest values among eight functional systems. These results indicate that network topology of the nodes comprising these systems is affected by TBI the most. This finding is supported by the significant decline in fractional anisotropy and the volume reduction in these two subnetworks in the presence of TBI [3, 23, 26]. Limbic system and subcortical regions, which are generally associated with memory and regulating emotions [11, 19], also overlaps with the cognitive deficits such as memory loss and emotional disorders that are commonly observed after the brain injury [1]. Our results suggest that default mode, frontoparietal, salience ventral attention, and dorsal attention network show TBI specific patterns that can help discriminate TBI patients from healthy controls. Structural alteration of these regions might be correlated with impairment of sustained attention and executive function in TBI [2, 9]. We note that, since these results indicate the level of dysfunction at 3 months post-injury, we could expect to see more immediate or long-term outcomes of the disease by evaluating a longitudinal TBI dataset that spans acute phase of the disease up to a year post-injury.

Fig. 3.
figure 3

Linear regression with GOSE in the patient population. The proposed measure GED-tr (\(p =0.013, R^2 = 0.181\)) has significant linear relationship with GOSE. Euclidean distance (\(p = 0.224, R^2 = 0.047\)) and Pearson distance (\(p=0.079, R^2 = 0.096\)) are not significant in terms of linear regression with GOSE. Note that, significance level after Bonferroni correction is \(p\le 0.016\).

Full size image

Subject-Specific Analysis. Lastly, we report the linear regression analysis results between each measure and the GOSE score for the patient population in Fig. 3. We observe that the proposed measure GED-tr shows a significant negative correlation with GOSE and demonstrates the highest relationship with \(R^2=0.181\), while neither Euclidean nor Pearson distance shows significant correlation. The results demonstrate that our measure quantifying dissimilarity of patients relative to controls correlates well with the clinical score, which shows its potential as a subject-specific biomarker for the disease. It is interesting to note that, although we observed in Fig. 1 that our method achieves the smallest variation among the patient group, it shows a higher correlation with the clinical score relative to Euclidean and Pearson distance as shown in Fig. 3. This might suggest that our proposed score discards non-disease-related variations while preserving information about the pathology.

4 Conclusion

In this study, we present a novel subject-specific measure that utilizes a learning-based graph edit distance to quantify dissimilarity of patients relative to healthy controls. Our measure provides better separation between patients and controls for the specific disease as it learns the pattern of the pathology at functional systems level. With the optimal parameters obtained via MCMC, we demonstrate on a TBI dataset that our method shows superiority over alternative connectomic dissimilarity measures in terms of increased group differences between patients and healthy controls. Our method enables a multi-resolution analysis of brain dysfunction, with the GED capturing subject-specific structural alterations due to the disease at the level of the whole brain, and the parameter tuning capturing the vulnerability of functional systems to pathology. Moreover, our measure is clinically meaningful, since it correlates well with a commonly used clinical measure of functional outcome in TBI, highlighting its potential to be used as a connectomic biomarker for neurological diseases.

We note that factors external to the disease such as age, gender, and volume of brain, as well as inaccuracies arising from data acquisition and tractographic biases, could have affected clinical outcomes of our study. Although effects of these factors are partially alleviated by minimizing graph distance between healthy controls, we will expand our analysis to regress out these effects in our future work. In this work, we only demonstrate the utility of our method with a case study on structural connectomes of TBI patients, the proposed method can easily be customized as a biomarker for other diseases and disorders, and be extended to capture the patterns of change over both functional and structural connectomes. The proposed measure can further be applied in domains other than disease quantification, such as clustering brain states, participant identification using connectomic fingerprinting, as well as longitudinal analysis of connectomes.