Year: 2021

Abstract:
The topological patterns exhibited by many real-world networks motivate development of topology-based methods for assessing the similarity of networks. However, extracting topological structure is difficult, especially for large and dense networks whose node degrees range over multiple orders of magnitude. In this paper, we propose a novel and computationally practical topological clustering method that clusters complex networks with intricate topology using principled theory from persistent homology and optimal transport. Such networks are aggregated into clusters through a centroid-based clustering strategy based on both their topological and geometric structure, preserving correspondence between nodes in different networks. The notions of topological proximity and centroid are characterized using a novel and efficient approach to computation of the Wasserstein distance and barycenter for persistence barcodes associated with connected components and cycles. The proposed method is demonstrated to be effective using both simulated networks and measured functional brain networks.

heading: 1 INTRODUCTION
text: Network models are extremely useful representations for complex data. Significant attention has been given to cluster analysis within a single network, such as detecting community structure (Newman, 2006; Rohe et al., 2011; Yin et al., 2017). Less attention has been given to clustering of collections of network representations. Clustering approaches typically group similar networks based on comparisons of edge weights (Xu & Wunsch, 2005), not topology. Assessing similarity of networks based on topological structure offers the potential for new insight, given the inherent topological patterns exhibited by most real-world networks. However, extracting meaningful network topology is a very difficult task, especially for large and dense networks whose node degrees range over multiple orders of magnitude (Barrat et al., 2004; Bullmore & Sporns, 2009; Honey et al., 2007).
Persistent homology (Barannikov, 1994; Edelsbrunner et al., 2000; Wasserman, 2018) has recently emerged as a powerful tool for understanding, characterizing and quantifying complex networks (Carrière et al., 2020; Chung et al., 2019). Persistent homology represents a network using topological features such as connected components and cycles. Many networks naturally divide into modules or connected components (Bullmore & Sporns, 2009; Honey et al., 2007). Similarly, cycles are ubiquitous and are often used to describe information propagation, robustness and feedback mechanisms (Keizer et al., 1995; Kwon & Cho, 2007; Ozbudak et al., 2005; Venkatesh et al., 2004; Weiner et al., 2002). Effective use of such topological descriptors requires a notion of proximity that quantifies the similarity between persistence barcodes, a convenient representation for connected components and cycles (Ghrist, 2008). Wasserstein distance, which measures the minimal effort to modify one persistence barcode to another (Rabin et al., 2011), is an excellent choice due to its appealing geometric properties (Staerman et al., 2021) and its effectiveness shown in many machine learning applications (Kolouri et al., 2017; Mi et al., 2018; Solomon et al., 2015). Importantly, Wasserstein distance can be used to interpolate networks while preserving topological structure (Songdechakraiwut et al., 2021), and the mean under the Wasserstein distance, known as Wasserstein barycenter (Agueh & Carlier, 2011), can be viewed as the topological centroid of a set of networks.
The high cost of computing persistence barcodes, Wasserstein distance and the Wasserstein barycenter limit their applications to small scale problems, see, e.g., (Clough et al., 2020; Hu et al., 2019; Kolouri et al., 2017; Mi et al., 2018). Although approximation algorithms have been developed (Cuturi, 2013;
Cuturi & Doucet, 2014; Lacombe et al., 2018; Li et al., 2020; Solomon et al., 2015; Vidal et al., 2019; Xie et al., 2020; Ye et al., 2017), it is unclear whether these approximations are effective for clustering complex networks as they inevitably limit sensitivity to subtle topological features. Indeed, more and more studies, see, e.g., (Robins & Turner, 2016; Xia & Wei, 2014) have demonstrated that such subtle topological patterns are important for the characterization of complex networks, suggesting these approximation algorithms are undesirable.
Recently, it was shown that the Wasserstein distance and barycenter for network graphs have closedform solutions that can be computed exactly and efficiently (Songdechakraiwut et al., 2021) because the persistence barcodes are inherently one dimensional. Motivated by this result, we present a novel and computationally practical topological clustering method that clusters complex networks of the same size with intricate topological characteristics. Topological information alone is effective at clustering networks when there is no correspondence between nodes in different networks. However, when networks have meaningful node correspondence, we perform the cluster analysis using combined topological and geometric information to preserve the node correspondence. Statistical validation based on ground truth information is used to demonstrate the effectiveness of our method when discriminating subtle topological features in simulated networks. The method is further illustrated by clustering measured functional brain networks associated with different levels of arousal during administration of general anesthesia. Our proposed method outperforms other clustering approaches in both the simulated and measured data.
The paper is organized as follows. Background on our one-dimensional representation of persistence barcodes is given in section 2, while section 3 presents our topological clustering method. In sections 4 and 5, we compare the performance of our method to several baseline algorithms using simulated and measured networks, and conclude the paper with a brief discussion of the potential impact of this work.

heading: 2 ONE DIMENSIONAL PERSISTENCE BARCODES

heading: 2.1 GRAPH FILTRATION
text: Consider a network represented as a weighted graph G = (V,w) comprising a set of nodes V with symmetric adjacency matrix w = (wij), with edge weight wij representing the relationship between node i and node j. The number of nodes is denoted as |V |. The binary graph G = (V,w ) of G is defined as a graph consisting of the node set V and binary edge weights w ,ij = 1 if wij > and wij = 0 otherwise. We view the binary network G as a 1-skeleton (Munkres, 2018), a simplicial complex comprising only nodes (0-dimensional topological features) and edges (1-dimensional topological features). There are no topological features of higher dimensions in the 1-skeleton, in contrast to well-known Rips complexes (Ghrist, 2008). In the 1-skeleton, there are two types of topological features: connected components and cycles. The number of connected components and the number of cycles in the binary network are referred to as the 0-th Betti number β0(G ) and the 1-st Betti number β1(G ), respectively. A graph filtration of G is defined as a collection of nested binary networks (Lee et al., 2012):
G 0 ⊇ G 1 ⊇ · · · ⊇ G k , where 0 ≤ 1 ≤ · · · ≤ k are filtration values. As increases, more and more edges are removed from the network G since we threshold the edge weights at higher connectivity. For instance, G−∞ has each pair of nodes connected by an edge and thus is a complete graph consisting of a single connected component, while G∞ has no edges and represents the node set. Figure 1 illustrates the graph filtration of a four-node network and the corresponding Betti numbers. Note that other filtrations for analyzing graphs have been proposed, including use of descriptor functions such as heat kernels (Carrière et al., 2020) and task-specific learning (Hofer et al., 2020).

heading: 2.2 BIRTH-DEATH DECOMPOSITION
text: Persistent homology keeps track of birth and death of connected components and cycles over filtration values to determine their persistence, that is, the lifetime from their birth to death over . The persistence is represented as a persistence barcode PB(G) comprising intervals [bi, di] representing the life-time of a connected component or a cycle that appears at the filtration value bi and vanishes at di.
In the edge-weight threshold graph filtration defined in Section 2.1, connected components are born and cycles die as the filtration value increases (Chung et al., 2019). Specifically, β0 is monotonically increasing from β0(G−∞) = 1 to β0(G∞) = |V |. There are β0(G∞) − β0(G−∞) = |V | − 1 connected components that are born over the filtration. Connected components will never die once they are born, implying that every connected component has death value at∞. Thus, we can represent their persistence as a collection of finite birth values B(G) = {bi}|V |−1i=1 . On the other hand, G−∞ is a complete graph containing all possible cycles; thus, all cycles have birth values at −∞. Again, we can represent the persistence of the cycles as a collection of finite death values D(G) = {di}. How many cycles are there? Since the deletion of an edge wij must result in either the birth of a connected component or the death of a cycle, every edge weight must be in either B(G) or D(G). Thus, the edge weight set W = {wij |i > j} decomposes into the collection of birth values B(G) and the collection of death values D(G). Since G−∞ is a complete graph with |V |(|V |−1) 2 edge weights and |V | − 1 of these weights are associated with the birth of connected components, the number of cycles inG−∞ is thus equal to |V |(|V |−1) 2 −(|V |−1) = 1+ |V |(|V |−3) 2 . In the example of Figure 1, we have B(G) = {e3, e5, e6} and D(G) = {e1, e2, e4}. Other graph filtrations (Carrière et al., 2020; Hofer et al., 2020) do not necessarily share this monotonicity property and consequently one-dimensional barcode representations are not applicable.
Finding the birth values in B(G) is equivalent to finding edge weights comprising the maximum spanning tree of G and can be done using well-known methods such as Prim’s and Kruskal’s algorithms (Lee et al., 2012). Once B(G) is known, D(G) is simply given as the remaining edge weights. Finding B(G) and D(G) requires only O(n log n) operations, where n is the number of edges in the network, and thus is extremely computationally efficient.

heading: 3 CLUSTERING METHOD

heading: 3.1 TOPOLOGICAL DISTANCE SIMPLIFICATION
text: Use of edge-weight threshold filtration and limiting consideration to connected components and cycles as topological features results in significant simplification of the 2-Wasserstein distance (Rabin et al., 2011) between barcode descriptors (Cohen-Steiner et al., 2010) of networks as follows. Let G and H be two given networks that have the same number of nodes. The topological distance dtop(G,H) is defined as the optimal matching cost:(
min τ ∑ p∈PB(G) ||p− τ(p)||2 ) 1 2 = ( min τ ∑ p=[bp,dp]∈PB(G) [ bp − bτ(p) ]2 + [ dp − dτ(p) ]2) 12 , (1)
where the optimization is over all possible bijections τ from barcode PB(G) to barcode PB(H). Intuitively, we can think of each interval [bi, di] as a point (bi, di) in 2-dimensional plane and that the topological distance measures the minimal amount of work to move points in PB(G) to PB(H). Note this alternative representation of points in the plane is equivalent to the persistence barcode and
called the persistence diagram (Edelsbrunner & Harer, 2008). Moving a connected component point (bi,∞) to a cycle point (−∞, dj) or vice versa takes an infinitely large amount of work. Thus, we only need to optimize over bijections that match the same type of topological features. Subsequently, we can equivalently rewrite dtop in terms of B(G), D(G), B(H) and D(H) as
dtop(G,H) = ( min τ0 ∑ b∈B(G) [ b− τ0(b) ]2 +min τ1 ∑ d∈D(G) [ d− τ1(d) ]2) 12 , (2)
where τ0 is a bijection from B(G) to B(H) and τ1 is a bijection from D(G) to D(H). The first term matches connected components to connected components and the second term matches cycles to cycles. Matching each type of topological feature separately is commonly done in medical imaging and machine learning studies (Clough et al., 2020; Hu et al., 2019). The topological distance dtop has a closed-form solution that allows for efficient computation as follows (Songdechakraiwut et al., 2021).
dtop(G,H) = ( ∑ b∈B(G) [ b− τ∗0 (b) ]2 + ∑ d∈D(G) [ d− τ∗1 (d) ]2) 12 , (3)
where τ∗0 maps the l-th smallest birth value in B(G) to the l-th smallest birth value in B(H) and τ ∗ 1 maps the l-th smallest death value in D(G) to the l-th smallest death value in D(H) for all l.
A proof is in the supplementary material. As a result, the optimal matching cost can be computed quickly and efficiently by sorting birth and death values, and matching them in order. The computational cost of evaluating dtop is O(n log n), where n is the number of edges in networks.

heading: 3.2 TOPOLOGICAL CLUSTERING
text: Let G = (V,w) and H = (V,u) be two networks. We define the network dissimilarity d2net between G and H as a weighted sum of the squared geometric distance and the squared topological distance:
d2net ( G,H ) = (1− λ) ∑ i ∑ j>i ( wij − uij )2 + λd2top ( G,H ) , (4)
where λ ∈ [0, 1] controls the relative weight between the geometric and topological terms. The geometric distance measures the node-by-node dissimilarity in the networks that is not captured by topology alone and is helpful when node identity is meaningful, such as in neuroscience applications. Given observed networks with identical node sets, the goal is to partition the networks into k clusters C = {Ch}kh=1 with corresponding cluster centroids or representativesM = {Mh}kh=1 such that the sum of the network dissimilarities d2net from the networks to their representatives is minimized, i.e.,
min C,M L(C,M) = min C,M k∑ h=1 ∑ G∈Ch d2net(Mh, G). (5)
The topological clustering formulation given in (5) suggests a natural iterative relocation algorithm using coordinate descent (Banerjee et al., 2005). In particular, the algorithm alternates between two steps: an assignment step and a re-estimation step. In the assignment step, L is minimized with respect to C while holdingM fixed. Minimization of L is achieved simply by assigning each observed network to the cluster whose representative Mh is the nearest in terms of the criterion d2net. In the re-estimation step, the algorithm minimizes L with respect toM while holding C fixed. In this case, L is minimized by re-estimating the representatives for each individual cluster:
min M k∑ h=1 ∑ G∈Ch d2net(Mh, G) = k∑ h=1 min Mh ∑ G∈Ch d2net(Mh, G). (6)
We will consider solving the objective function given in (6) for λ = 0, λ = 1 and λ ∈ (0, 1). λ = 0 describes conventional edge clustering (MacQueen, 1967) since the topological term is excluded.
λ = 1 describes clustering based on pure topology and ignores correspondence of edge weights. This case is potentially useful for clustering networks whose node sets are not identical or of different size. Each representative Mh of cluster Ch minimizes the sum of the squared topological distances, i.e.,
min Mh ∑ G∈Ch d2top(Mh, G) = min B(Mh),D(Mh) ∑ G∈Ch ( ∑ b∈B(Mh) [ b− τ∗0 (b) ]2 + ∑ d∈D(Mh) [ d− τ∗1 (d) ]2) .
(7) Thus, we only need to optimize over the topology of the network, i.e., B(Mh) and D(Mh), instead of the original network Mh itself. The topology solving (7) is the topological centroid of networks in cluster Ch. Interestingly, the topological centroid has closed-form solution and can be calculated analytically as follows.
Lemma 1. Let G1, ..., Gn be n networks each with m nodes. Let B(Gi) : bi,1 ≤ · · · ≤ bi,m−1 and D(Gi) : di,1 ≤ · · · ≤ di,1+m(m−3)/2 be the topology of Gi. It follows that the l-th smallest birth value of the topological centroid of the n networks is given by the mean of all the l-th smallest birth values of such networks, i.e., ∑n i=1 bi,l/n. Similarly, the l-th smallest death value of the topological
centroid is given by ∑n i=1 di,l/n.
Since Eq. (7) is quadratic, Lemma 1 can be proved by setting its derivative equal to zero. The complete proof is given in the supplementary material. The results in (Songdechakraiwut & Chung, 2020) may be used to find the centroid of different size networks.
For the most general case considering both correspondence of edge weights and topology, i.e., when λ ∈ (0, 1), we can optimize the objective function given in (6) by gradient descent. Let H = (V,u) be a cluster representative being estimated given Ch. The gradient of the squared topological distance ∇Hd2top(G,H) with respect to edge weights u = (uij) is given as a gradient matrix whose ij-th entry is
∂d2top(G,H)
∂uij =
{ 2 [ uij − τ∗0 (uij) ] if uij ∈ B(H);
2 [ uij − τ∗1 (uij) ] if uij ∈ D(H).
(8)
This follows because the edge weight set decomposes into the collection of births and the collection of deaths. Intuitively, by slightly adjusting the edge weight uij , we have the slight adjustment of either a birth value in B(H) or a death value in D(H), which slightly changes the topology of the network H . The gradient computation consists of computing persistence barcodes and finding the optimal matching using the closed-form solution given in (3), requiring O(n log n) operations, where n is the number of edges in networks.
Evaluating the gradient for (6) requires computing the gradients of all the observed networks. This can be computationally demanding when the size of a dataset is large. However, an equivalent minimization problem that allows faster computation is possible using the following result:
Lemma 2. k∑ h=1 min Hh ∑ G∈Ch d2net(G,Hh) = k∑ h=1 min Hh ( (1− λ) ∑ i ∑ j>i ( wh,ij − uh,ij )2 + λd2top ( M̂top,h, Hh )) ,
(9)
where wh = (wh,ij) are edge weights in the sample mean network Mh = (V,wh) of cluster Ch, and M̂top,h is the topological centroid of networks in cluster Ch.
Thus, instead of computing the gradient for every network in the set, it is sufficient to compute the gradient at the cluster sample means Mh and topological centroids M̂top,h. Hence, one only needs to perform topological interpolation between the sample mean network Mh and the topological centroid M̂top,h of each cluster. That is, the optimal representative is the one whose geometric location is close to Mh and topology is similar to M̂top,h. At each current iteration, we take a step in the direction of negative gradient with respect to an updated H from the previous iteration. Note that the proposed method constrains the search of cluster centroids to a space of meaningful networks through topological interpolation. In contrast, the sample mean, such as would be used in a naive application of k-means, does not necessarily represent a meaningful network.
Furthermore, we have the following theorem:
Theorem 1. The topological clustering algorithm monotonically decreases L in (5) and terminates in a finite number of steps at a locally optimal partition.
The proofs for Lemma 2 and Theorem 1 are provided in the supplementary material.

heading: 4 VALIDATION USING SIMULATED NETWORKS
text: Simulated networks of different topological structure are used to evaluate the clustering performance of the proposed approach relative to that of seven other methods. We use the term topology to denote the proposed approach with λ > 0. Clustering using the special case of λ = 0 is termed the edge-weight method. Recall that the graph filtration used decomposes the edge weights into two groups of birth and death values corresponding to connected components and cycles (section 2.2). In order to assess the impact of separating edge weights into birth and death sets, we evaluate an ad hoc method called sort that applies k-means to feature vectors obtained by simply sorting edge weights.
In addition, we evaluate several clustering algorithms that utilize network representations. Two persistent homology clustering methods based on the well-known Rips filtration (Ghrist, 2008) are evaluated. The Rips filtration results in standard two-dimensional barcodes representing connected components and cycles. Consequently, two separate Wasserstein distances are needed to match connected components to connected components and cycles to cycles. The Wasserstein method performs clustering using k-medoids based on the sum of the two Wasserstein distances for connected components and cycles. The computational complexity of the Wasserstein method is managed by utilizing an approximation algorithm (Lacombe et al., 2018) to compute Wasserstein distance. A Wasserstein barycenter clustering algorithm called Bregman Alternating Direction Method of Multipliers (B-ADMM) (Ye et al., 2017) is used to cluster two-dimensional barcodes for cycles. In order to make B-ADMM computationally tractable, each barcode is limited to no more than the 50 most persistent cycles.
The Net Stats clustering approach uses k-means to cluster three-dimensional feature vectors composed of the following network summary statistics: (1) average weighted degree over all nodes (Rubinov & Sporns, 2010), (2) average clustering coefficient over all nodes (Rubinov & Sporns, 2010) and (3) modularity (Newman, 2006; Reichardt & Bornholdt, 2006).
Lastly, we evaluate two clustering approaches based on graph kernels with kernel k-means (Dhillon et al., 2004). One is the edge histogram kernel (Sugiyama & Borgwardt, 2015) method. The other is the propagation kernel method of (Neumann et al., 2016) with each node assigned the continuous attribute of the sum of edge weights incident to the node.
Initial clusters for all methods are selected at random.
Modular network structure Random modular networks Xi are simulated with |V | nodes and m modules such that the nodes are evenly distributed among modules. Figure 2 displays modular networks with |V | = 60 nodes and m = 5 modules such that |V |/m = 12 nodes are in each module. Edges connecting two nodes within the same module are assigned a random weight following a normal distribution N (µ, σ2) with probability r or otherwise Gaussian noise N (0, σ2) with probability 1− r. On the other hand, edges connecting nodes in different modules have probability 1− r of beingN (µ, σ2) and probability r of being N (0, σ2). The modular structure becomes more pronounced as the within-module connection probability r increases. Any negative edge weights are set to zero. This procedure yields random networks Xi that exhibit topological connectedness. We use µ = 1 and σ = 0.5 universally throughout the study.
Simulation Three groups of modular networks L1 = {Xi}20i=1, L2 = {Xi}40i=21 and L3 = {Xi}60i=41 corresponding to m = 2, 3 and 5 modules, respectively, are simulated. This results in 60 networks in the dataset, each of which has a group label L1, L2 or L3. We consider r = 0.9, 0.8, 0.7 and 0.6 to vary the strength of the modular structure, as illustrated in Figure 2.
The dataset is partitioned into three clusters C1, C2 and C3 using the candidate algorithms. Clustering performance is then evaluated by first assigning each cluster to the group label that is most frequent in
that cluster and then calculating the accuracy statistic s as the fraction of correctly labeled networks, i.e., s = 160 ∑3 i=1 maxj{|Ci ∩ Lj |}, where |Ci ∩ Lj | denotes the number of common networks in both Ci and Lj . Note this evaluation of clustering performance is called purity, which not only is transparent and interpretable but also works well in this simulation study where the number and size of clusters are small and balanced, respectively (Manning et al., 2008). Since the distribution of the accuracy s is unknown, a permutation test is used to determine the empirical distribution under the null hypothesis that sample networks and their group labels are independent (Ojala & Garriga, 2010). The empirical distribution is calculated by repeatedly shuffling the group labels and then re-computing the corresponding accuracy for one million random permutations. By comparing the observed accuracy to this empirical distribution, we can determine the statistical significance of the clustering performance. The p-value is calculated as the fraction of permutations that give accuracy higher than the observed accuracy s. The average p-value and average accuracy across 100 different initial assignments is reported.
Results Figure 3 indicates that all methods considered perform relatively well with pronounced modularity (r = 0.9). As the modularity strength diminishes with decreasing r, clustering performance also decreases. The proposed topological clustering algorithm (λ = 1) performs relatively well for the more nuanced modularity associated with r = 0.7 and 0.6. Since the dataset is purposefully generated to exhibit dependency between the sample networks and their group labels, the p-value indicates the degree of statistical significance to which structure is differentiated (Ojala & Garriga, 2010). Small p-values indicate the algorithm is able to differentiate network structure. The proposed method has very low p-values indicating that its improved accuracy over the baseline methods is significant. The Wasserstein and
B-ADMM methods require very high computation costs for the Rips filtration (Otter et al., 2017), and the approximations of Wasserstein distance (Lacombe et al., 2018) and barycenter (Ye et al., 2017). The ad hoc sort method performs nearly identically to the topology approach, showing that the separation into births of connected components and deaths of cycles has no apparent impact for these simulated networks with densely connected structure. However, we hypothesize the separation will impact performance when networks are sparse. The complete experimental results including an additional set of module sizes m = 2, 5 and 10 are provided in the supplementary material.
Figure 4 displays topological clustering performance as a function of λ for the strongest (r = 0.9) and weakest (r = 0.6) degree of modularity. The performance is not very sensitive to the value of λ. When the within-module connection probability is small (r = 0.6), increasing the weight of the topological distance by increasing λ results in the best performance. We hypothesize that in this case the relatively strong random nature of the edge weights introduces noise into the geometric term that
hinders performance as λ decreases. Conversely, the topological distance appears less sensitive to this particular edge weight noise, resulting in the best performance when λ = 1.

heading: 5 APPLICATION TO FUNCTIONAL BRAIN NETWORKS
text: Dataset We evaluate our method using an extended brain network dataset from the anesthesia study reported by Banks et al. (2020) (see the supplementary material). The measured brain networks are based on alpha band (8-12 Hz) weighted phase lag index (Vinck et al., 2011) applied to 10-second segments of resting state intracranial electroencephalography recordings from eleven neurosurgical patients administered increasing doses of the general anesthetic propofol just prior to surgery. The network size varies from 89 to 199 nodes while the number of networks (10-second segments) per subject varies from 71 to 119. Each segment is labeled as one of the three arousal states: pre-drug wake (WA), sedated/responsive (S), or unresponsive (U); these labels are used as ground truth in the cluster analysis. Figure 5 illustrates sample mean networks and Betti plots describing topology for a representative subject.
Performance evaluation We apply the adjusted Rand index (ARI) (Hubert & Arabie, 1985) to compare clustering performance against ground truth. Lower scores indicate less similarity while higher scores show higher similarity between estimated and ground-truth clusters. Perfect agreement is scored as 1.0. For each subject, we calculate these performance metrics by running the algorithm for 20 different initial conditions, resulting in 20 scores which are then averaged. We also average across subjects (11× 20 scores) to obtain a final overall score, which describes the overall output clusters across trials and subjects. We calculated average confusion matrices for each method by assigning each cluster to the state that is most frequent in that cluster.
Cluster analysis All baselines used in the simulation study are evaluated on the brain network dataset. In addition, we consider clustering using k-medoids and three previously proposed network distance measures for brain network analyses: Gromov-Hausdorff (GH) (Lee et al., 2012); Kolmogorov-Smirnov (KS) (Chung et al., 2019); and the spectral norm (Banks et al., 2020). Initial clusters are selected at random for all methods. Figure 6 reports the ARI of the topological approach for multiple predefined λ’s including λ = 0 and λ = 1. The relative performance of topological clustering is reported in Figures 7
and 8 assuming λ = 0.5, which results in equal weighting of topological and geometric distances.
Results Figure 6 indicates that the performance on the brain network data set varies significantly across subjects, but in general varies stably with λ. The best performance occurs with λ between 0.4 and 0.7, suggesting that a combination of geometric and topological distances gives the best result and that performance is not sensitive to the exact value chosen for λ. Note that different regions of the brain are functionally differentiated, so it is plausible that topological changes due to changing arousal level vary with location, giving geometric distance a role in the clustering of brain networks. Prior expectations of this sort can be used to determine whether to cluster based only on topology (λ = 1) or a combination of geometry and topology.
Figure 7 compares the ARI performance metric for individual subjects and the combination of all the subjects. All methods demonstrate significant variability in individual subject performance. This is expected due to the variations in effective signal to noise ratio, the number of nodes, and the number of networks in each underlying state. Consequently the combined performance across subjects has high variability. The topological method with λ = 0.5 performs relatively well across all subjects. Figure 8 illustrates that proposed approach is particularly effective at separating wake (WA) and unresponsive (U) states. Transitioning from the wake state to the unresponsive state results in dramatic changes in brain connectivity (Banks et al., 2020). The majority of errors from the proposed topological clustering approach are associated with the natural overlap between wake and sedated states (S). The sedated brain, in which subjects have been administered propofol but are still conscious, is expected to be more like the wake brain than the unresponsive brain. Thus, errors are expected to be more likely in differentiating sedated and wake states than sedated and unresponsive states. This suggests that the types of errors observed in the proposed method are consistent with prior biological expectations.
Impact The demonstrated effectiveness and computational elegance of our approach to clustering networks based on topological similarity will have a high impact on the analysis of large and complex network representations. In the study of brain networks, algorithms that can demonstrate correlates of behavioral states are of considerable interest. The derived biomarkers of changes in arousal state presented here demonstrate potential for addressing the important clinical problem of passively assessing arousal state in clinical settings, e.g., monitoring depth of anesthesia and in establishing diagnosis and prognosis for patients with traumatic brain injury and other disorders of consciousness. More broadly, the algorithm presented here will contribute to elucidating the neural basis of consciousness, one of the most important open problems in biomedical science.

Review summaries:
Given a weighted graph, authors construct a filtration on top of it that is associated with a persistence diagram. This persistence diagram summarizes the topology of the weighted graph. Authors propose then to cluster different graphs using either the distance between the persistence diagrams (that they call the topological distance) or an interpolation between the L2 distance between the weights and the topological distance.  The relevance of this algorithm is then showcased on synthetic examples and real-world datasets. 

In this article, the authors propose a way to characterize graphs using topology and persistent homology. Indeed, graphs represented with adjacency matrices can be filtered using the corresponding edge weights, and the resulting persistence diagrams can then be used for encoding the topological structures of the graph. Moreover, since the topology of graphs can be easily controlled (the only features they have are connected components and loops), their persistence diagrams are simple enough so that matching and distances between them can be computed efficiently. However, since topology alone can miss important information, the authors suggest to combine this topological distance with a more standard distance, namely the Frobenius norm between the adjacency matrices themselves. Then, they show how to use these distances in an expectation-maximization-like algorithm, using some theoretical computation guarantees of the Fréchet mean associated to their distances. Finally, they provide experiments in which their procedure compares favorably to competitors on a few synthetic and real-world graph classification tasks.

This paper presents a novel algorithm for clustering networks based on their topological properties. To this end, an algorithm based on persistent homology (a method from computational topology that permits the calculation of multi-scale features of unstructured and structured data sets) is introduced. The key feature of the algorithm is that it manages to substantially reduce the cost of 'matching' topological features between two different data sets, thus making their comparison and similarity assessment computationally feasible. The paper provides an algorithm that can employ *both* geometrical and topological features of a network (with an appropriate regularisation term); experiments demonstrate the general utility of the algorithm.