Fast topological clustering with Wasserstein distance
Authors: Tananun Songdechakraiwut
Bryan M Krause
Matthew I Banks
Kirill V Nourski
Barry D Van Veen
Venue: ICLR 2022 Poster (2022)
Keywords: Topological data analysis
cluster analysis
persistent homology
Wasserstein distance
Wasserstein barycenter
brain networks
intracranial electrophysiology
consciousness

Abstract: The topological patterns exhibited by many real-world networks motivate the 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.

Published as a conference paper at ICLR 2022
FAST TOPOLOGICAL CLUSTERING WITH WASSERSTEIN DISTANCE
Tananun Songdechakraivutt
Bryan M. Krause & Matthew L. Banks
Department of Electrical and Computer Engineering University of Sesconsin-Madison USA
Department of Anesthesiology
Department of Neuroscience University of Wisconsin-Madison, USA
songdecha k @errawwisse www.wwwws....oe.
Kirill V. Nourski
Barry D. Van Veen
Department of Neurosurgery Iowa Neuroscience Institute University of lowa, USA
Department of Electrical and Computer Engineering University of Aecconsin-Madisonn USA
ABSTRACT
The topological patterns exhibited by many real-world networks motivate the de- velopment of topology-basse 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 aggre- gated into clusters through centroid-based clustering strategy based on both their topological and geometric structure, preserving correspondence between nodes in different networks. The notions topological proximity and centroid are char- acterized using novel and efficient approach computation of the Wasserstein distance and barycenter for persistence barcodes associated with connected compo- nents and cycles. The proposed method demonstrated be effective using both simulated networks and measured functional brain networks.
INTRODUCTION
Network models 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 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 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) has recently emerged as powerful tool for understanding, characterizing and quantifying complex networks (Songdechakraiwut et al., 2021). Persistent homology represents network using topological features such connected components and cycles. Many networks naturally divide into modules or connected components (Bullmore & Sporns, 2009; Honey et al., 2007). Similarly, cycles ubiquitous and are often used to describe information propagation, robustness and feedback mechanisms (Kwon & Cho, 2007; Lind al., 2005). Effective of such topological descriptors requires 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
"Code for topological clustering available httph: btttsp::/giiee http//ggtttttttttee wttphu/.cco/ooooolloooao larn.

---

Published as a conference paper at ICLR 2022
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, 201 1), can be viewed as the topological centroid of 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 al., 2020; Hu al., 2019; Kolouri et al., 2017; Mi et al., 2018). Although approximation algorithms have been developed (Cuturi, 2013;
Cuturi & Doucet, 2014 4; 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 closed- form solutions that can be computed exactly and efficiently (Songdechakraiwutt 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 correspondence between nodes in different networks. However, when networks have meaningful node correspondence, we perform cluster analysis using combined topological and geometric information to preserve 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.
ONE-DIMENSIONAL PERSISTENCE BARCODES
2.1
GRAPHI FILTRATION
Consider a network represented as a weighted graph G = (V,w) comprising set of nodes with symmetric adjacency matrix = (wiy). with edge weight wiy 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 graph consisting of the node set V and binary edge weights We,ij 1 if way > and We,t = 0 otherwise. We view the binary network G. as a 1-skeleton (Munkres, 2018), a simplicial complex comprising only nodes and edges. In the 1-skeleton, there are two types of topological features: connected components (O-dimensional topological features) and cycles (1-dimensional topological features). There are no topological features of higher dimensions in the 1-skeleton, in contrast to well-known Rips (Ghrist, 2008) and clique complexes (Otter et al., 2017). The number of connected components and the number of cycles in the binary network are referred as the 0-th Betti number 30 (G.).) and the 1-st Betti number 31 (G.), respectively. A graph filtration of G is defined as a collection of nested binary networks (Lee et al., 2012):
G. 2 G. 2 ... 2 Gan
where eo S .... E 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 edge and thus is a complete graph consisting of single connected component, while Go has no edges and represents the node set. Figure I illustrates the graph filtration of four-node network and the corresponding Betti numbers. Note that other
2

---

Published as a conference paper at ICLR 2022
.co
Get
G
Gæ3
G
G
Ge6
G
6
e
Bo
C3
B1
e1
22
e3
e4
e5
e6
Figure 1: Graph filtration of four-node network G. As the filtration value increases, the number of connected components 30 monotonically increases while the number of cycles 31 monotonically decreases. Connected components are born the edge weights c32 Es. Eg while cycles die at e1, e22 64-
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 al., 2020).
2.2 BIRTH-DEATH DECOMPOSITION
Persistent homology keeps track of birth and death of connected components and cycles over filtration values c to deduce their persistence, i.e., the lifetime from their birth to death over The persistence represented as a persistence barcode (B( comprising intervals [b;, d:] representing the lifetime of connected component
cycle that appears at the filtration value b; and vanishes at d;.
In the edge-weight threshold graph filtration defined Section 2.1, connected components are born and cycles die as the filtration value increases (Songdechakraiwut et al., 2021). Specifically, So is monotonically increasing from oo = to Bo (o = VV. There are (o - 3o(G- = |V| - connected components that are born over the filtration. Connected components will never die once they are born, implying that every connected component has a death value at co. Thus, represent their persistence as a collection of finite birth values B(G) {b.) [6. On the other hand, Go a complete graph containing all possible cycles; thus, all cycles have birth values at -00 Again, we can represent the persistence of the cycles D(G) {d;}. How many cycles are there? Since the deletion of an edge Wij must result in either the birth of a connected component the death of cycle, every edge weight must be in either B(G) or DGG). Thus, the edge weight set W = {wayh i > j} decomposes into the collection of birth values B(G) and the collection of death values D(G). Since Go is complete graph with !ИК[У--1 edge weights and [V|- 11-1 of these weights are associated with the birth of connected components, the number of cycles in G x is thus equal |V((V[-1) (IV) 1) 1+ [УК[У--3) In the example of Figure 1, we have B(G) {eg, Es, c and D(G) = (e1, C22 64). Other graph filtrations (Carrière al., 2020; Hofer et al., 2020) do necessarily share this monotonicity property and consequently one-dimensional barcode representations are not applicable.
collection of finite death values
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 's and Kruskal's algorithms (Lee al., 2012). Once B(G) known, D(G) simply given as the remaining edge weights. Finding B(G) and D(G) requires only O(n log operations, where n is the number of edges in the network, and thus extremely computationally efficient.
CLUSTERING METHOD
3.1 TOPOLOGICAL DISTANCE SIMPLIFICATION
Use of edge-weight threshold filtration and limiting consideration to connected components and cycles as topological features results in significant simplification of the 2- 2-Wasserstein distance (Rabin al., 2011 1) between barcode descriptors G and H be two given networks that have the same number of nodes. The topological distance drop(G. H) is defined as the optimal matching cost:
et al., 2010) of networks as follows. Let
min
lp (p-T())))) = /min
Σ
[b0 br(o) +
2 [dp dr(m)))) (1)
PCP
p= Pe
3

---

Published as a conference paper at ICLR 2022
where the optimization is over all possible bijections from barcode PB(G) to barcode ( Intuitively, we can think of each interval [b,, de] as a point (b,, de) in 2-mmennsina plane. The topological distance measures the minimal amount of work to move points in (B(G) to (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 connected component point (be, 20) to cycle point (-oo, 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 deop in terms of B(G), D(G), B(H) and (HH)
dzop(G, (G, 1)
min
Σ 16- [o-r([6]]² + min BEB(G)
Σ [d- [d-n(d)]² dED(G)
(2)
where To a bijection from B(G) to B(H) and TI 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 drop has a closed-form solution that allows for efficient computation as follows (Songdechakraivuut et al., 2021).
deop H)
H)= =
Σ
b To (b)]
+
[d - (d)))) DED(G)
Σ
(3)
BEB
where ru maps the I-th smallest birth value in (GG) to the I-th smallest birth value in B (H))& and oं' maps the I-th smallest death value in D(G) to the 1-th smallest death value in D(H) for all I.
proof is provided Appendix 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 deop is On log n), where the number of edges networks.
3.2 TOPOLOGICAL CLUSTERING
Let G (V, w) and H (V, u) be two networks. We define the network dissimilarity & between G and H as a weighted sum of the squared geometric distance and the squared topological distance:
dhes (G, (1 - A) ΣΣ (waj u:j)² + ( (G,
(4)
where E [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 helpful when node identity is meaningful, such as neuroscience applications. Given observed networks with identical node sets, the goal is to partition the networks into & clusters = (Ch H with corresponding cluster centroids or representatives M {Mr such that the sum of the network dissimilarities di from the networks to their representatives is minimized, i.e.,
min L(C, min C.M
Pner(Mp, G). Σ h= GEC.
C.M
The topological clustering formulation given in (5) suggests natural iterative relocation algorithm using coordinate descent (Banerjee 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 while holding M fixed. Minimization of is achieved simply by assigning each observed network to the cluster whose representative Mr, is the nearest in terms of the criterion df In the re-estimation step, the algorithm minimizes L with respect to M while holding fixed. In this case, L is minimized by re-estimating the representatives for each individual cluster:
min
L (Mr, G)
min Σ
diee (Mr, G).
(6)
1=1 GEC
1=1
GeCa
We will consider solving the objective function given in (6) for À A and À (0, 1).
4

---

Published as a conference paper at ICLR 2022
À = 0 describes conventional edge clustering (MacQueen, 1967) since the topologiaal term is excluded.
À = describes clustering based 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 Md. of cluster C₁ minimizes the sum of the squared topological distances, i.e.,
min Mr. GEC₂
Keo (M,, G) min D(MA) GEC, BEB((M)
E(1
Σ
Σ
[b [b]] +
E [d [d- -d)]) (ED())))
(7)
Thus, only need optimize over the topology of the network, i.e., B(Mr) and D(M)), instead of the original network M,, itself. The topology solving (7) is the topological centroid of networks in cluster C₁. Interestingly. the topological centroid has a closed-form solution and can be calculated analytically follows.
Lemma 1. Let GI. Gn be n networks each with m nodes. Let B(G,) : S........ -b;m- and D(G.) d S... S d1, mmmm+11 be the topology of G.. It follows that the 1-th smallest birth value of the topologicul centroid of the n networks is given by the mean of all the 1-th smallest birth values of such networks, i.e., Ei=1 b Similarly, the 1-th smallest death value of the topological centroid is given by Ei=1d ds,1/n.
Since Eq. (7) is quadratic, Lemma can be proved by setting derivative equal to zero. The complete proof is given in Appendix A. The results in (Songdechakraiwat & Chung, 2020; Songdechakraiwut al., 2022) may 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 E (0, 1), we can optimize the objective function given in (6) by gradient descent. Let H (V, u) be cluster representative being estimated given C₁ The gradient of the squared topological distance V dd (H, G) with respect to edge weights u = (u.) is given as a gradient matrix whose ij-th
entry is
(1, (2
[ Uyy To (Uy)]
if usy E B(H);
(8)
Oui
2 Uky - 7 (us;)]
if uy E D(H).
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 Uyj we have the slight adjustment of death value in D(H)), which slightly changes the topology of the
either birth value in [ H)) network H. The gradient computation consists of computing persistence barcodes and finding the optimal matching using the closed-form solution given in (3), requiring On 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.
I
Σ min Σ Hn GECn
(H,, G)
Σ
min (a1 Hn
ΣΣ j>i
(un,is - whis)² Adhop (Hir Mtop.n))
(9)
where Wh (Wh,s)) are edge weights in the sample mean network Ms (V, ()) of cluster Ch. and Mtop.r is the topological centroid of networks in cluster Cp.
Thus, instead of computing the gradient for every network in the set, it is sufficient to compute the gradient at the cluster sample means Ms and topological centroids Mzop. Hence, one only needs to perform topological interpolation between the sample mean network M & and the topological centroid Moop.h of each cluster. That is, the optimal representative is the one whose geometric location is close to M, and topology is similar to Mtop, At each current iteration, we take 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 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 meaningful network.
5

---

Published as a conference paper at ICLR 2022
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 are provided in Appendix A.
4 VALIDATION USING SIMULATED NETWORKS
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 À > O. Clustering using the special case of À = 0 is termed the edge-weight method. Recall the graph filtration defined in section 2.2 decomposes the edge weights into two groups of birth and death values corresponding to connected components and cycles. In order to assess the impact of separating edge weights into birth and death sets, evaluate 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 conventional two-dimensional barcodes (Otter et al., 2017) evaluated. The Wasserstein method performs clustering using k-medoids based on Wasserstein distance between two-dimensional barcodes for connected components and cycles. The computational complexity of the Wasserstein method is managed by utilizing approximation algorithm (Lacombe et al., 2018) to compute the Wasserstein distance. A Wasserstein barycenter clustering algorithm called Bregman Alternating Direction Method of Multipliers (B-ADMM) (Ye et al., 2017) 7) is used to cluster two-dimensional barcodes for cycles. In order to make B-ADMM computationally tractable, each barcode limited to no more than the 50 most persistent cycles.
The Ner Stats clustering approach uses k-means to cluster ftree-dimensions 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 graph kernel based clustering approaches using kernel k-means (Dhillon et al., 2004): the Gruphloopper kernel (Feragen et al., 2013) and the propagation kernel (Neumann et al., 2016). Supplementary description and implementation details of the candidate methods are provided in Appendix B.
Initial clusters for all methods selected at random.
r= 0.9
0.8
Modular network structure Random modular networks X; are sim- ulated 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 = 5 modules such that /V//m 12 nodes are in each module. Edges connecting two nodes within the same module assigned random weight following normal distribution N(,, o²) with probability or otherwise Gaussian noise (0, o²) with probability r. On the other hand, edges connecting nodes in different modules have probability 1 - of being N N(u, o²) and prob- ability of being (V The modular structure becomes more pronounced as the within-module connection probability increases. Any negative edge weights are set to zero. This procedure yields random networks X; that exhibit topological connectedness. We use f = 1 and o = 0.5 universally throughout the study.
2
r 0.7
= 0.6
Figure 2: Example networks with [V| 60 nodes and m = 5 modules exhihit different within- module connection probabilities
r= 0.9, 0.8, 0.7 and 0.6.
Simulation
{X and L3 (X, 1,60 corresponding to m = 2, 3 and modules, respectively, are simulated. This results in 60 networks in the dataset, each of which has a group label L1, L2 or Lzz. We consider 0.9, 0.8, 0.7 and 0.6 to vary the strength of the modular structure, as illustrated in Figure 2.
Three groups of modular networks L1 [X (2 L2
The dataset is partitioned into three clusters C1, C2 and Cs 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 as the fraction of correctly labeled networks,

---

Published as a conference paper at ICLR 2022
0.6
Top (A=1) Edge-weight Sort
Accuracy
0.8
D-value
0.4
Wasserstein
B-ADMM
0.6
0.2
Net Stats
GraphHopper
0.4
0
Propagation
0.9
0.8
0.7
0.6
0.9
0.8
0.7
0.6
Figure 3: Clustering performance comparison for the dataset of simulated networks with [V] 60 nodes and m = 2,3, 5 modules with respect to average accuracy (left) and average p-values (right). Results for within-module connection probabilities (middle horizontal lines) indicate the averages over results for 100 different initial conditions, and vertical error bars indicate standard deviations.
0.6, 0.7, 0.8 and 0.9 are shown. Data points
max, TyyB; where ( denotes the number of common networks in both C, 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 is unknown, a permutation test used 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 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 reported.
Le., 60 Σd
Results Figure 3 indicates that all methods consid- ered perform relatively well with pronounced mod- ularity (r = 0.9). As the modularity strength dimin- ishes with decreasing T. clustering performance also decreases. The proposed topological clustering algo- rithm (A 1) performs relatively well for the more nuanced modularity associated with r = 0.7 and 0.6.
Accuracy
Avall
0.5
0.5
0.5
A
Accuracy
D-value
0.5
Since the dataset purposefully generated to exhibit dependency between the sample networks and their group labels, the p-value indicates the degree of statis- tical significance 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 indicat- ing that its improved accuracy over the baseline meth- ods is significant. The Wasserstein and B-ADMM methods require very high computation costs for the conventional two-dimensional barcodes (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 sparse. Supplementary experimental results including an additional set of module sizes m = 2, 5 and 10 are provided Appendix B.
0.5
0
0.5
0
0.5
1
À
Figure 4: Clustering performance for simulated networks with [V| = 60 nodes and = 3, modules as function of x for wothin-module connection probabilities r = 0.9 (top row) and r= 0.6 (bottom row).
Figure 4 displays topological clustering performance as 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 X. When the within within-module module connection probability is small (r 0.6), increasing the weight of the topological distance by increasing results the best performance. We hypothesize that this case the relatively strong random nature of the edge weights introduces noise into the geometric term that
7

---

Published as a conference paper at ICLR 2022
Wake (W)
Sedated (S)
Unresponsive (U)
0th Betti
150
100
W
Electrode #
50
0.3
50
0.2
0.4
0.6
100
1 Betti
10
150
102
50 100 150 Electrode #
50 100 150
50 100 150 Electrode #
0.2
0.4
(a)
Electrode
(b)
Filtration value
Figure 5: Representative data from a single subject (ID R376). For this subject there are 36 measured networks each of three conditions: wake, sedated, and unresponsive states for a total of 108 networks. (a) Sample mean networks during wake, sedated and unresponsive states of the subject computed using ground truth labels. (b) Betti plots based on ground truth labels. Thick lines represent topological centroids. Shaded areas around the centroids represent standard deviation.
hinders performance as À decreases. Conversely, the topological distance appears less sensitive to this partieular edge weight noise, resulting in the best performance when À = 1.
APPLICATION TO FUNCTIONAL BRAIN NETWORKS
Dataset We evaluate our method using extended brain network dataset from the anesthesia study reported by Banks et al. (2020) (see Appendix C). The measured brain networks are based on alpha band (8- 12 Hz) weighted phase lag index (Vinck et al., 201 applied 10-second segments of resting state intracranial electroencephalographh recordings from eleven neurosurgical patients administered increasing doses of the general anesthetie propofol just prior 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 (W), 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 scored as 1 1.0. For each subject, we calculate these performance metrics by running the algorithm for 100 different initial conditions, resulting in 100) scores which are then averaged. We also average across subjects (11 x 100 scores) to obtain final overall score, which describes the overall output clusters across trials and subjects. We calculate average confusion matrices for each method by assigning each cluster to the state that is most frequent that cluster.
Cluster analysis All baselines used in the sim- ulation study are evaluated on the brain net- work dataset. In addition, ing using k-medoids and three previously pro- posed network distance measures for brain net- work analyses: Gromov-Haasdory (GH) (Lee al., 2012); Kolmogorov-Smirnov (KS) (Chung et al., 2019); and the spectral norm (Banks al., 2020). Supplementary description of the three methods is provided in Appendix B. Ini- tial clusters are selected at random for all meth- ods. Figure reports the ARI of the topological approach for multiple predefined X's including = and À 1. The relative performance of topological clustering is reported Figures and 8 assuming À 0.5, which results in equal weighting of topological and geometric distances.
R369
L372
consider cluster-
0.8
R376
B384
0.6
R399
ARI
L400
L403
0.4
L405
L409
0.2
L423
L514
Avg
0.3
0.5
0.7
1
Figure 6: Average ARI per subject (gray lines) and across all eleven subjects (red line) function of X.
Results Figure indicates that the performance on the brain network data set varies significantly across subjects, but in general varies stably with X. The best performance occurs with À between 0.4
8

---

Published as a conference paper at ICLR 2022
1
0.8
0.6
0.4
0.2
0
R369
L372
R376
B384
R399
L400
L403
L405
L409
L423
L514
Avg
Subject ID
Top (A=0.5)
Edge-weight
Sort KS
Wasserstein
B-ADMM
Net Stats
GraphHopper
Propagation
Spectral
GH
Figure 7: ARI performance for the brain network dataset. Data points (middle horizontal lines) indicate averages over 100 random initial conditions, and error bars indicate standard deviations.
Top (A
Edge-weight
Wasserstein
B-ADMM
GraphHopper
Spectral
GH
cluster
w
1.0
0.7
0.3
.0.05
0.7
0.3 0.1
0.5 0.2
0.5 0.3 0.2
0.6
<0.01
0.6
0.3
S
$0.3
0.5
0.2
0.3 0.6
0.1
0.3
0.6
<0.05
0.3
0.6 0.1
0.2 0.7
0.1
<a.0s
1.0 <0.01
0.1 0.6 0.3
<0.05
0.1
0.9
0.2
0.4
0.4
0.4
0.1 0.6
0.4
0.1
0.5
0.1
0.1
0.8
<0.05
0.4
0.6
0.1
0.3
0.6
W
S
U
W
S
U
W
U
W
S
W
S
U
W
U
W
S
Predicted cluster
Predicted cluster
Predicted cluster
Predicted cluster Predicted cluster
Predicted cluster
Predicted cluster
Figure 8: Average confusion matrices over 100 random initializations for select methods for subject R376 (see Figure 5). Results for the other methods are provided in Appendix B.
and 0.7, suggesting that combination of geometric and topological distances gives the best result and that performance is not sensitive to the exact value chosen for X. Note that different regions of the brain are functionally differentiated, it plausible that topological changes due 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 determine whether to cluster based only on topology (A 1) combination of geometry and topology.
Figure 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 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 the proposed approach is particularly effective at separating wake (W) 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 emror 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 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, of the most important open problems in biomedical science.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is supported in part by the National Institute of General Medical Sciences under award R01 GM109086, and the Lynn H. Matthias Professorship from the University of Wisconsin.
REFERENCES
Martial Agueh and Guillaume Carlier. Barycenters in the Wasserstein space. SIAM Journal Mathematical Analysis, 43(2):904-924, 2011.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with Bregman divergences. Journal of Machine Learning Research, 6(10), 2005.
Matthew Banks, Bryan M Krause, Christopher M Endemann, Declan I Campbell, Christopher K Kovach, Mark Eric Dyken, Hiroto Kawasaki, and Kirill V Nourski. Cortical functional connectivity indexes arousal state during sleep and anesthesia. Neurolmage, 211:116627,, 2020.
Serguei Barannikov. The framed Morse complex and its invariants. Advances in Soviet Mathematics, American Mathematical Sociery, 1994.
Alain Barrat, Mare Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. The architec- ture of complex weighted networks. Proceedings of the National Academy of Sciences, 101(11): 3747-3752, 2004.
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O' O'Bray, and Bastian Alexander Rieck. Graph kernels: State-of-the-ar and future challenges. Foundations and Trends in Machine Learning, 13(5-6):531-713 2020.
Ed Bullmore and Olaf Sporns. Complex brain networks: Graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience, 10(3):186-198 2009.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda.
Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics, pp. 2786-27966 PMLR, 2020.
Moo K Chung, Hyekyoung Lee, Alex DiChristofano. Hernando Ombao, and Victor Solo. Exact topological inference of the resting-state brain networks twins. Network Neuroscience, 3()): 674-694, 2019.
James Clough, Nicholas Byrne, Ilkay Oksuz, Veronika Zimmer, Julia Schnabel, and Andrew King. A topological loss function for deep-learning based image segmentation using persistent homology. IEEE Transactions on Pottern Analysis and Machine Intelligence, 2020.
David SthennSteiner, Herbert Edelsbrunner, John Harer, and Yuriy Mileyko. Lipschitz functions have stpstabl persistence. Foundations of Computational Mathematics, 2010.
Marco Cuturi. Sinkhor distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, -6:00, 2013.
Marco Cuturi and Arnaud Doucet. Fast computation of Wasserstein barycenters. In International Conference on Machine Learning, pp. 685-693, 2014.
Inderjit Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: Spectral clustering and normal- ized cuts. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 551-556, 2004.
Herbert Edelsbrunner and John Harer. Persistent homology-a survey. Contemporary Mathematics, 453:257-282, 2008
Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplifica- tion. In Proceedings st Annual Symposium on Foundations of Computer Science, pp. 454 463. IEEE, 2000.
10

---

Published as a conference paper at ICLR 2022
Aasa Feragen, Niklas Kasenburg. Jens Petersen, Marleen de Bruijne. and Karsten Borgwardt. Scalable kernels for graphs with continuous attributes. Advances in Neural Information Processing Systems, 26, 2013.
Robert Ghrist. Barcodes: The persistent topology of data. Bulletin of the American Mathernatical Society, 45(1);61-75, 2008.
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. International Conference on Machine Learning, pp. 4314 4323, PMLR, 2020.
Christopher Honey, Rolf Kötter, Michael Breakspear, and Olaf Sporns. Network structure of cerebral cortex shapes functional connectivity on multiple time scales. Proceedings of the National Academy of Sciences, 104024):1240--00255 2007.
Xiaoling Hu, Fuxin Li, Dimitris Samaras, and Chao Chen. Topology-preservingg deep image segmen- tation. Advances in Neural Information Processing Systems, 32, 2019.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2(1):193-218, 1985.
Soheil Kolouri, Se Rim Park, Matthew Thorpe, Dejan Slepcev, and Gustavo K. Rohde. Optimal mass transport: Signal processing and machine-learning applications. IEEE Signal Processing Magazine, 34(4):43-55 59, 2017.
Yung- Keun Kwon and Kwang- Hyyn Cho. Analysis of feedback loops and robustness in network evolution based on Boolean models. BMC Bioinformatics, 8(1):1-9, 2007.
Théo Lacombe, Marco Cuturi, and Steve Oudot. Large scale computation of means and clusters for persistence diagrams using optimal transport. Advances in Neural Information Processing Systems, 2018.
Hyekyoung Lee, Hyejin Kang, Moo K Chung, Bung-Nyun Kim, and Dong Soo Lee, Persistent brain network homology from the perspective of dendrogram. IEEE Transactions Medical Imaging, 31(12):226--2277, 2012.
Lingxiao Li, Aude Genevay, Mikhail Yurochkin, and Justin M Solomon. Continuous regularized Wasserstein barycenters. Advances in Neural Information Processing Systems, 33, 2020.
Pedro G Lind, Marta C González, and Hans Herrmann. Cycles and clustering in bipartite networks. Physical Review E, 72(5):056127, 2005.
James MacQueen. Some methods for classification and analysis of multivariate observations. In
Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1967.
Christopher D Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008.
Liang Mi, Wen Zhang, Xianfeng Gu, and Yalin Wang. Variational Wasserstein clustering. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 322-337, 2018.
Dragoslav S Mitrinovic. Analytic Inequalities. Springer, 1970.
James R Munkres. Elements of Algebraic Topology. CRC press, 2018.
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation kernels: Efficient graph kernels from propagated information. Machine Learning, 102(2):209 2009922455111 2016.
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-8882 2006.
Markus Ojala and Gemma C Garriga. Permutation tests for studying classifier performance. Journal of Machine Learning Research, (166), 2010.
Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6:1-38, 2017.
11

---

Published as a conference paper at ICLR 2022
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision. pp. 435-446. Springer. 2011.
Jörg Reichardt and Stefan Bornholdt. Statistical mechanics of community detection. Physical Review E, 7.()):0060 10, 2006.
Vanessa Robins and Katharine Turner. Principal component analysis of persistent homology rank functions with case studies of spatial point patterns, sphere packing and colloids. Physica D: Nonlinear Phenomena, 334:99-117 2016.
Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 3984):8878-1155 2011.
Mikail Rubinov and Olaf Sporns. Complex network measures of brain connectivity: Uses and interpretations. Neurolmage, 125911009--069, 2010.
Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional Wasserstein distances: Efficient optimal transporta- tion on geometric domains. ACM Trunsactions Graphics (TOG), 34(4):1-11, 2015.
Tananun Songdechakraiwut and Moo K Chung. Topological learning for brain networks. arXiv preprint arXiv:2012.00675, 2020.
Tananun Songdechakraiwuu. Li Shen, and Moo Chung. Topological learning and its application to multimodal brain network integration. 24th International Conference on Medical Image Computing and Computer-Assister Intervention (MICCAI), 2021.
Tananun Songdechakraivuut Bryan M Krause, Matthew Banks, Kirill V Nourski, and Barry D Van Veen. Topological classification in Wasserstein distance based vector space. arXiv preprint arXiv:2202.01225, 2022.
Guillaume Staerman, Pierre Laforgue, Pavlo Mozharovskyi, and Florence d' Alché Buc. When OT meets MoM: Robust estimation of Wasserstein distance. In International Conference on Artificial Intelligence and Statistics, pp. 136-144, 2021.
Katharine Turner, Yuriy Mileyko, Sayan Mukherjee, and John Harer. Fréchet means for distributions of persistence diagrams. Discrete & Computational Geometry, 52(1):44-70, 2014.
Jules Vidal, Joseph Budin, and Julien Tierny. Progressive Wasserstein barycenters of persistence diagrams. IEEE Transactions Visualization and Computer Graphicx, 26(1):151-161, 2019.
Martin Vinck, Robert Oostenveld, Marijn Van Wingerden, Franscesco Battaglia, and Cyriel MA
Pennartz. An improved index of phwse-synnhhooeee synchonniztiinn for clectrophyssological data in the presence of volume-conduction, noise and sample-size bias. Neurolmage, (3(4):1548-11 2011.
Kelin Xia and Guo-Wei Wei. Persistent homology analysis of protein structure, flexibility, and folding. International Journal for Numerical Methods in Biomedical Engineering, 30(8):814-844, 2014.
Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. A fast proximal point method for computing exact Wasserstein distance. In Uncertainty in Artificial Intelligence, pp. 433-453, 2020.
Rui Xu and Donald Wunsch. Survey of clustering algorithms. IEEE Transactions Neural Networks, 16(3):645-66) 2005.
Jianbo Ye, Panruo Wu, James Z Wang, and Jia Li. Fast discrete distribution clustering using Wasserstein barycenter with sparse support. IEEE Transactions on Signal Processing, 65(9): 2317-2332 2017.
Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 555-564, 2017.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
A PROOFS
A.1 CLOSED-FORM SOLUTION OF TOPOLOGICAL DISTANCE
The topological distance drop has the closed-fone formm solution follows
dzop AGop(G, (G -
Σ b 1b (6) BEB(G)
E [d-r dED(G)
where To maps the (-th smallest birth value in BGG) to I-th smallest birth value in ((H) and rî maps the I-th smallest death value in D(G) to the I-th smallest death value in D(H) for all l.
Proof. Let G and If be networks with m nodes. The topological distance is originally defined as
drop(G H)
min Σ BEB(G)
b To(b]] min Σ [d [d-<1(0 [d-)
dED(G)
We rewrite the first term as follows.
min
6b 6- [-)0 min Σ
1b2 (b) + + (b)
DEB(G)
BEG)
min Σ
(b) + C2
be bEB
Σ
bro());
BEB(G)
where Cj constant. Note that Ele (b) is equivalent EmERCHY 62, which is a constant over all bijections Ty- Similarly for the second term, we have
min Σ [d- max Σ dd) dED(G)
dED(G)
Let B(G) 11 <... < 4m-1 and B(H): 1/1 S ... ...5Smm.. 5m-1 be the collections of birth values for G and respectively. By the rearrangement inequality (Mitrinovic, 1970), is known that
1191 + ... + 1on-19m-22 2 5 (1) + ................................ (m ()mmm1)))))))))))
for every permutation (x(1), 1) 2 .... Im 1- Thus, optimal bijection Tp maps the 1-th smallest birth value in ( to the 1-th smallest birth value in B(H) Similarly for the second term, we have of that maps the /-th smallest death value in D(G') to the (-th smallest death value in D(H).
A.2 CLOSED-FORM SOLUTION OF TOPOLOGICAL CENTROID
Lemma 1. Let GI,..., Gn be networks each with nodes. Let B(G,) bb,1 .... bi.m-1 and D(G)) d .... S d4,14m(m--)) be the topology of G.. It follows that the 1-th smallest birth value the topological centroid of the n networks is given by the mean all the 1-th smallest birth values of such networks, i.e., Em= b Similarly, the 1-th smallest death value of the topological centroid is given by E d=,/nn
Proof. Let M be a cluster representative. Recall that the topological centroid minimizes the sum of the squared topological distances, i.e.,
min
Kop (M, Gt)
min ((M)
Σ
b bb- (b))
E [d- (d))
1=11
be B(M)
dED(M)
13

---

Published as a conference paper at ICLR 2022
Let B(M) ' .... I mm-1 and ((M) : 01 S ... 61 mmmm33)322 be the topology of M. The first term can be expanded as
12
Σ Σ b- -0)))
Σ
(m b + hm-1 bi bi.m-1l²)
which is quadratic and thus can be solved by setting its derivative equal to zero. The solution is given by n = Σm= bun/n. nn. Similarly, the second term can be expanded as
[d [d- -(0]² - Σ (16. dr,11² .... (01+m(m-s)) 31/2 d, dm (33)mmmmm33 33/22² a
2=1 DE (M)(
which again quadratic. By setting its derivative equal to zero, we find the minimum at 0; - ds./n.
A.3 TOPOLOGICAL INTERPOLATION
Lemma 2.
k
Σ
min Σ
(O G) = Σ
min
(On.s Wn.i)² + ddhp (On, Mtop.h)). J>1
8n
A=1
GECr
h=1
(10)
where Wh = (Wh,ss) are edge weights in the sample mean network M = (V))))& of cluster Ct. and Mtop,r is the topological centroid of networks in cluster Ch.
Proof. Let = (V, E EC and = =V,,), Denote the cardinality of C by m. We will show that
min &
Σ
(9, G) = min (1 A)
ΣΣ (0ig w. 2 + ddl (0, Meon)
9
GEC
J3
We first rewrite the geometric term follows.
ΣΣΣ (0g w1y)² GEC 1 1>$
ΣΣΣ
O0 20 +wi))
GEC
ΣΣ
Σ
(m0²
20
Σ Wij +
Σ
w
GEC
GEC
20
m ΣΣ
(0)
Σ
Wij) + Ci
m
GEC
20
(0
Σ
Wij Σ
wis/m)?) + C2
m
GEC
GEC
(0:s Σ
Wii/ (aamm) 2 + C2
GEC
Σ
E
(0:j
wij)
C2
J>b
where C1 C2 are constants. Similarly for the topological term, we have
Σ
= Σ
Σ
b -
(b)
2 + Σ Id - (d)))
GEC
GEC
BEB())
dED(e)
Σ
mmb2
2h
(b)] + Σ mnd
2d Σ [i( Css
GEC
GEC
bb Σ To (b)mm
2 + Σ
[d Σ (dd)/m] 2) + Ca
GEC
d
GEC
= maltop (0, M.op) C4.
14

---

Published as a conference paper at ICLR 2022
Thus,
min Σ GEC
dner min(1 - A) ΣΣ (0:j wiz)² + +C2) + X (mdhopp (O, (oop))) Cs)
min m (1 A) Σ
EEO (Oig w 2 + dd (O, MMop)) + Cb
5>1
min (1 - A) Σ
(0i w (0,
j>i
A.4 CONVERGENCE TO A LOCALLY OPTIMAL PARTITION
Theorem 1. The topological clustering algorithm monotonically decreases L and terminates finite number of steps at a locally optimal partition.
(1) Th-1 be partition of observed networks with corresponding representatives M (M, Jh=1 after the t-th iteration. Then,
Proof. Let C(²) 1
L(C M Σ
Σ
dnet (M G)
4=1 GEO
d G)
h=1 GEO
(M 1= GEC
Σ
G) = L(C(tt), M((H)),
where (a) follows from the assignment step and (b) follows from applying Lemma (when À = 1) and Lemma (when À E (0, 1) and step size in gradient descent is sufficiently small) to the re-estimation step. Note that À = O describes conventional edge clustering (MacQueen, 1967). This result shows that the algorithm monotonically decreases L. Since the number of distinct partitions finite and L monotonically decreasing, eventually L will not be decreased either by (a) the assignment step (b) re-estimation step and the algorithm terminates.
B EXPERIMENTAL DETAILS
B.1 SUPPLEMENTARY DESCRIPTION FOR CANDIDATE METHODS
METHODS BASED ON TWO-DIMENSIONAL BARCODES
The Wasserstein method clusters conventional two-dimensional barcodes representing connected components and cycles. To this end, two separate Wasserstein distances are needed 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.
Bregman Alternating Direction Method of Multipliers (B-ADMM) (Ye et al., 2017) is Wasserstein barycenter based algorithm for clustering discrete distributions. We follow the standard approach (Turner et al., 2014) to representing underlying discrete distributions on two-dimensional barcodes in the form of Dirac masses. The high computational complexity of B-ADMM is managed by limiting the clustering to no more than the 50 most persistent cycles.
The two methods require computation of two-dimensional persistence barcodes from networks. We compute a wwo-dimensional persistence barcode using the approach of Otter et al. (2017) in which edge weights inverted via the function f(w) 1/ w). Then point cloud is obtained from the shortest path distance between nodes. Finally, we compute Rips filtration (Ghrist, 2008) and its corresponding persistence barcode from the point cloud.
15

---

Published as a conference paper at ICLR 2022
Top (A 0.5)
Edge-weight
Sort
Wasserstein
B-ADMM
Net Stats
w
0.97
<0.01
0.72
0.51
0.67
0.45
True clustor
0.32
0.53
0.15
0.33
0.56
0.11
0.27
0.69
0.04
0.33
0.64
0.03
0.30
0.63
0.07
0.17
0.79
0.04
0.02
0.07
0.91
0.16
0.39
0.44
0.38
0.11
0.50
0.39
0.06
0.55
0.40
0.10
0.50
0.33
0.18
0.50
U
W
Predicted cluster
Predicted cluster
Predicted cluster
Predicted cluster
Predicted cluster
Predicted cluster
GraphHopper
Propegation
KS
W
0.49
0.27
0.24
0.22
0.23
0.55
0.64
0.36
<0.01
0.61
61610
0.31
0.08
0.55
0.21
0.24
True cluster
0.20
0.68
0.11
0.18
0.47
0.35
0.03
0.97
40.01
0.08
0.61
0.31
0.52
0.43
0.05
0.09
0.77
0.18
0.08
0.74
0.39
0.58
0.08
0.31
0.61
0.12
0.64
W
U
W
S
W
S
U
W
S
U
W
S
Predicted
Predicted cluster
cluster
cluster
Supplementary Figure 1: Average confusion matrices over 100 random initializations for subject R376. W: wake, S: sedated, U: unresponsive.
METHODS BASED ON GRAPH KERNELS
The two graph kernel methods based on GraphHopper and propagation kernels require node con- tinuous attributes. We follow the experimental protocol of Borgwardt et al. (2020) in which node attribute is set the sum of edge weights incident to the node.
METHODS BASED ON NETWORK DISTANCE MEASURES FOR BRAIN NETWORK ANALYSES
(GH) distance (Lee et al., 2012) compares dendrogram shape differences in brain networks. GH distance requires brain networks that exhibit metric spaces. To this end, we follow the approach of Otter al. (2017) for converting brain network to metric space. The metric space obtained by first inverting edge weights via the function f(w) = 1/(1 + w) and then using the shortest path distance between nodes as a metric.
Kolmogorov-Sing Soniooooro--Smrroov (KS) distance (Chung et al., 2019) compares topological differences in brain networks using their Betti numbers. Two separate KS distances needed compare 0-th Betti numbers to 0-th Betti numbers and 1-st Betti numbers to 1-st Betti numbers. The sum of the two KS distances is used to compare brain networks.
We follow the approach of Banks et al. (2020) to comparing brain networks using the operator or spectral norm of the difference between network adjacency matrices.
B.2 IMPLEMENTATION OF CANDIDATE METHODS
For all the baseline methods, we used existing implementation codes from authors' publications and publicly available repository websites. We used parameters recommended in the public code without any modification. Code for Wasserstein distance approximation (Lacombe et al., 2018) is available at pottps://gudie
iinniii........ fr/. Code for Bregman Alternating Direction Method of Multipliers (B-ADMM) method (Ye et al., 2017) is available https : / gi github. com/ com/bobye/ MBt_Matlals Code for the three network summary statistics used the Net Stats method is available https: : // hts/sitess.... ttt.sssooggoileee..e///ooooogoee wwwm//ite/btttteeccccocooo propagation graph kermels is available at https: /ttes:://iiiee http://ggttt/bt//// cwwccsiicccccceecccccoo.e.cc...e /
Code for GraphHopper and
B.3 SUPPLEMENTARY RESULTS FOR SIMULATED MEASURED DATASETS
For simulated networks, clustering performance comparison is reported in Supplementary Table 1. For measured brain networks, confusion matrices of all the candidate methods for subject R376 (see Supplementary Table 2) are reported in Supplementary Figure 1.
16

---

Published as a conference paper at ICLR 2022
Supplementary Table 1: Clustering performance comparison for simulated networks with |V| nodes. (a) average accuracy and (b) average p-values for various parameter settings of m (number of modules) and (within-module module connection probability).
60
m
Top (A 1)
Edge-weight
Sort
Wasserstein
B-ADMM
Net Stats
GraphHopper
Propagation
0.6 0.75 0.06
0.46 + 0.04
0.76 = 0.06 0.57 0.06 0.61 = 0.05
0.75 +.06
0.69 = 0.08
0.60 = 0.12
0.7 0.95 = 0.06
0.62 + 0.13
0.94
+ 0.08
0.77 + 0.08
0.81 = 0.08
0.96 0.02
0.90 + 0.12
0.75 = 0.13
2/3/5
0.8 0.97 = 0.10
0.75
0.97
0.10
0,88 + 0.12
0,92
- 0.08
0.98 0.00
0.98 + 0.09
0.80 = 0.16
0.94 = 0.13
0.81
0.17
0.93
0.90
0.15
0.96
1.00
0.95 0.12
0.97 0.13
0.82 0.20
0.6 0.78 0.07
0.78 0.41
0.00
0.07
0.73 0.11
0.65 0.14
0.7 0.85 0.13
0.59
1.910.1100
0.85
1 0.12
0.81
0.00
0.86 0.07
0.89
0.10
0.85
0.21
0.81
0.12
2/5/10
0.8
0.90 0.14
0.72
0.89
+ 0.15
0.88
+ 0.14 0.91 0.13
0.91
+: 0.14
0.85
+ 0.26
0.85 0.15
0.9 0.92
0.14
0.78 + 0.15
0.92 + 0.14 0.92 = 0.14 0.91 = 0.15
0.90 0.15
0.73 = 0.33
0.85 0.17
(a) Average accuracy
Top
1)
Edge-weight
Sort
Wasserstein
B-ADMM
Net Stats
GraphHopper
Propagation
0.001
- 0.26
0.001
0.02 002:0..0 0.12
0.003 = 0.021
0.001
0.02 = 0.14
0.09 0.27
0.7
0.001
0.07 = 0.21
0.001
0.001
0.001
0.001
0.04 0.20
0.01 = 0.10
2/M/
0.8
< 0.001
0.03 1 0.13
0,001
0,001
< 0.001
0.001
0.02 + 0.14
0.04 0.20
0,9
< 0.001
0.01 = 0.09
< 0.001
0,001
< 0.001
0.001
0.04 = 0.20
0.08 = 0.27
0.001
0.37 0.33
0.004
0.034
0.001
0.001
0.06 = 0.24
0.12
0.31
0.001
0.05 0.14
0.001
0.001
0.14 1
0.01
2/5/10
0.8
0.001
0.03 0.15
0.001
0.001
0.001
0.20 0.40
0.03 0.17
0.9
0,001
0.001 = 0.039
0.001
0.001
0.001
0.001
0.41 = 0.49
0.04 0.20
(b) Average p-values
Supplementary Table
Subject
Age
Gender
Network size
R369
30
M
199
L372
34
M
174
R376
48
189
B384
38
M
89
R399
22
175
L400
59
F
126
L403
56
194
L405
19
M
127
L409
31
L423
51
M
152
L514
46
M
118
C BRAIN NETWORK DATASET
Brain network data were obtained from eleven neurosurgical patients (5 female, ages -9- 59 years old, median age 38 years old; Supplementary Table 2). The patients had been diagnosed with medically refractory epilepsy and were undergoing chronic invasive intracranial electroencephalography (iEEG) monitoring identify potentially resectable seizure foci. All human subjects experiments were carried out in accordance with The Code of Ethics of the World Medical Association (Declaration of Helsinki) for experiments involving humans. The research protocols were approved by the University of Iowa Institutional Review Board and the National Institutes of Health. Written informed consent was obtained from all subjects. Research participation did not interfere with acquisition of clinically required data. Subjects could rescind consent at any time without interrupting their clinical evaluation. Recordings were made using subdural and depth electrodes (Ad-Tech Medical, Oak Creek, WI) placed solely on the basis of clinical requirements, determined by the team of epileptologists and neurosurgeons. The brain network dataset was based on recordings made in the operating room prior to electrode removal, before and during induction of general anesthesia with propofol. Details of the experimental procedure, recording, and electrophysiological data analysis are available in (Banks al., 2020).
17

---

Published as a conference paper at ICLR 2022
Iteration
Iteration
Convergence
29
Betti
20
20
Mupp
1.5
Mapp
Mtpp3
1.2
1.2
1.2
C1
20
0.5
300
C2
C3
Bett
200
10
100
20
30
10 20
30
0.2
0.9
0.2
0.9
0.2
0.9
Weight
Weight (b)
Weight
(a)
Supplementary Figure 2: Toy illustration of performing topological clustering using only topological
centroids (A = 1). Clustering is performed on 15 networks: five each with m 2,5 and 10 modules. All networks use V 30, within module connection probability
0.9 and edge weight standard deviation o = 0.1. (a) Network examples for m = 2 (top), 5 (middle) and 10 (bottom) modules. (b) Illustration of topological clustering. Topological centroids Mepp. (thick lines) and individual network topologies are visualized using Betti numbers
function of edge weights (filtration values). The algorithm converges in three iterations and the final partition (last column) perfectly matches the ground truth, i.e., C1, C2 and C3 corresponds to m 2,5 and 10.
D TOY ILLUSTRATION OF TOPOLOGICAI CLUSTERING
Supplementary Figure 2 illustrates cluster analysis of the proposed topological approach using only topological centroids (A 1) on a toy dataset generated using random modular networks described in Section 4 in the main body of the paper.
18


Reviews:
[{"review_id": "rDLTUlTHUq0", "reviewer": "Reviewer_VKeM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method is definitely interesting and the provided scores in the experiments are impressive. Moreover, the algorithm is backed up by not-surprising yet nice theoretical guarantees. However, I also think that the writing and the experiments could be improved.\n\nIn particular, I also have the following comments:\n\n---Section 1, 2nd paragraph: it would be good to add a reference to the PersLay paper (http://proceedings.mlr.press/v108/carriere20a/carriere20a.pdf), which also provides a standard way to use (extended) persistence to characterize graphs. \n\n---Section 1, 3rd paragraph: it would be good to add a reference to the entropic regularization for persistence diagrams (https://papers.nips.cc/paper/2018/hash/b58f7d184743106a8a66028b7a28937c-Abstract.html), which also contains a standard approach for approximating topological distances.\n\n---Section 1, 4th paragraph: \"by projecting the persistence barcodes into one dimension\", it is a bit incorrect, as the proposed approach is not really about projecting 2D barcodes onto lines. The fact that the barcodes are 1D only comes from the data (i.e., graphs) on which they are computed. This should be corrected as otherwise it is confusing with actual projection techniques, such as, e.g., the sliced Wasserstein distance and kernel.\n\n---Section 2.2: \"there are |V|-1 connected components\": in which graph? G_{-\\infty} has one connected components and G_{\\infty} has |V| connected components, so it is unclear to what space this sentence applies to.\n\n---Section 4: the authors compare their method to k-means, but it is unclear on which data k-means is actually run. Is it over the adjacency matrices treated as vectors? But then, how is this different from the authors method applied with lambda=0? Similarly, isn't k-medoids with the bottleneck distance essentially the same than the authors method applied with lambda=1? \n\n---Section 4: all in all, the authors method simply separates the filtration values into two groups based on 0- and 1-dimensional persistent homology, and then compare graphs with the Euclidean distance computed on the sorted groups. So I really wonder (and I think this should be included in the baseline) if the improvements in score could be obtained by simply adding the Euclidean distance on the whole sorted filtration values (without running persistent homology).\n\n---It is always a bit suspicious to see p-values exactly equal to zero as in Table 1 (b). 100 iterations seems a bit low, maybe this number should be increased on a few thousands on these data sets.\n\n---The improvement on the scores is quite impressive, but on the other hand the baseline seems a bit naive. Since the number of networks is not so large in the experiments, I strongly suggest adding fancier methods in the baseline, such as, e.g., kernel methods or neural nets. Indeed, there is quite a lot of graph kernels (https://arxiv.org/pdf/2011.03854.pdf) and graph neural networks (https://arxiv.org/pdf/1812.08434.pdf) in the literature, some of them performing quite well in applications, so it would nice to add some more comparisons.\n\n---The authors distance is only presented on graphs with same number of nodes. Since their method extends naturally to graphs with different sizes (even though running time would probably be worse), it would be nice to discuss this at some point in the article.\n\n[Post rebuttal comment]: the rebuttal was nicely done, and I think that the paper is now good enough for publication.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall I think that the technique proposed in the article is really promising, but that experimental results should be developed a little more before getting accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "esleCMt9Bz", "reviewer": "Reviewer_FgNK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presentation of the paper is clear and the paper is well-written. The problem of clustering persistence diagrams (PDs) has attracted some attention over the recent years and is not a trivial one. To overcome the main computational challenges that arise when having to compute distances/barycenters of PDs, authors propose to consider simpler persistence diagrams that are one-dimensional (that is all points in the PDs have coordinates of the form $(-\\infty,d_i)$ or $(b_i,+\\infty)$). It is well-known that in one dimension, optimal transport essentially boils down to sorting algorithms, so that all the computational tasks (computing distances/barycenters) become trivial. A naive implementation of k-means is then proposed using the distance between PDs, that is able to attain a local minimum of the energy functional at stake.\n\nMy main issue with the article is that they never clearly acknowledge that they work with \"simple\" PDs that have a very particular form, and that this makes the problem much easier to solve. Those simpler PDs appear because the filtration F that they build on top of the weighted graph does not contain any two-dimensional simplices: as such the points of the PDs PD(F) are of the form $(-\\infty,d_i)$. What is usually done is to consider a filtration G with two-dimensional simplices appearing and \"filling\" the loops of the graph at some point, the corresponding PD PD(G) having points of the form $(b_i,d_i)$. To put it another way, we are considering a PD, PD(F), obtained by considering the projection of the points of PD(G) on the y-axis. We are therefore losing information while doing this. I have nothing against considering a simpler object if this allows one to also simplify computations, but this needs to appear explicitly in the paper.\n\nThe question is then: \"What exactly do we lose by considering the simple filtration F instead of G?\". I do not expect a mathematical treatment here, but it would seem fair to compare experimentally the method proposed in the paper with the alternative method with the filtration G used. More precisely, in the case $\\lambda =1$ (considering the topological distance), one could cluster graphs applying the k-mean algorithm on the PDs built with G, computing barycenters of PDs using one of the standard approaches [1,2]. We expect the second method to take more time, but to be more precise. Of course, a good selling point for the paper would be to show that using the filtration G instead of the filtration F (i) takes much more time and (ii) does not make us gain that much accuracy. Such an empirical confirmation should really be at the core of the paper in my opinion.\n \nOverall, the idea of considering simpler objects on which computations can be done is appealing, but this needs to be backed up by either theoretical or empirical evidence. With more experiments, I would be willing to improve my grade.\n\n\nMINOR COMMENTS:\n- p.1 \"Wasserstein distance can be used to interpolate networks while preserving topological structure,\" please give a ref\n- Eq (4): this would rather be d_net^2, if we want d_net to be a distance.\n- p.4 How is this algorithm different from Lloyd's algorithm (in a general metric space)?\n- p.5 bottom: comparing to k-medoids using the W2 distance instead of the bottleneck distance appears to be fairer, as it will be more able to assess the fine structure in the geometry of the points of the PDs.\n- Fig 5: this behavior is interesting, and should be commented on: taking $\\lambda = 0$ is a bad idea, but then, any positive value (that is still not too close to 1) appears to give a similar score. Are there any explanations about why this is the case?\n- On the experiments: it seems weird that they do not exist better alternative methods that are **at least** able to obtain a score similar to the one obtained by the paper's method. \n\n\n[1] Geometry Helps to Compare Persistence Diagrams - Michael Kerber, Dmitriy Morozov, Arnur Nigmetov\n\n[2] Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport - Theo Lacombe, Marco Cuturi, Steve OUDOT", "summary_of_the_paper": "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.\n\nThe relevance of this algorithm is then showcased on synthetic examples and real-world datasets.\n", "summary_of_the_review": "The proposed method to cluster graphs using persistence diagrams is computationally efficient, but at the price of losing some topological information in the process. This can definitely be a good approach in some problems, but I would like to have some empirical evidence that \"we do not lose too much information\" in the process, that is that this procedure competes with the (slower) one where we take into account the complete topological information.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y-ILu20dqfJ", "reviewer": "Reviewer_NiBH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a paper about a timely and highly relevant topic, and I find\nmyself to be very excited about its results and promises. The paper\nstands on firm theoretical footing: the proposed algorithm is described\nin sufficient detail to be reproducible and a brief analysis of the\ntheory behind it is provided as well. The current write-up is already\nvery clear, and only suffers from minor formulation issues or clarity\naspects, on which I shall subsequently comment. The primary weakness of\nthe paper lies in the experimental section; here, I would suggest\nimprovements in terms of the discussion here, because the jump between\nsimulated networks and real-world networks might necessitate some\nexperiment 'in-between.'\n\n## Detailed Comments\n\n- When introducing graph filtrations, consider discussing that such\n  filtrations can also be generated using specific descriptor functions,\n  such as a heat kernel (Carrière et al., [PersLay: A Neural Network\n  Layer for Persistence Diagrams and New Graph Topological\n  Signatures](http://proceedings.mlr.press/v108/carriere20a/carriere20a.pdf)),\n  or they can even be *learned* in a task-specific manner (Hofer et al.,\n  [Graph Filtration\n  Learning](https://proceedings.mlr.press/v119/hofer20b.html)).\n  Moreover, it could e discussed that the presented filtration is only\n  one way of filtering over the network; this could be managed by\n  a brief discussion on sublevel or superlevel set filtrations, for\n  instance.\n\n- Moreover, it should be made clear that, unless I am mistaken, the type\n  of filtration described in the paper is a **highly specific** type of\n  filtration in the sense that not all filtrations will result in the\n  respective creation--destruction tuples (or birth--death tuples,\n  respectively). For instance, if a descriptor function (like the\n  aforementioned heat kernel) is used, creation tuples might be of the\n  generic form $(a, b)$ with $a, b \\in \\mathbb{R}$, as opposed to one of\n  them being infinite. I am mentioning this point not out of pedantry,\n  but because it should be clarified that the simplifications of the\n  Wasserstein distance later on are *contingent* on the tuples being of\n  that form. To some extent, this limits the general applicability of\n  the approach: if higher-dimensional simplices are present in the\n  network, cycles could be assigned finite persistence values (the same\n  holds for the calculation of extended persistence, or the use of\n  another descriptor function that does not necessarily result in\n  a fully-connected graph). It would immensely strengthen the current\n  write-up in the paper if these special properties were at least\n  briefly discussed.\n\n- To add to this, such special properties could also potentially be\n  mentioned in Section 3.1 when discussing how to derive the distance\n  function.\n\n- The notation for solving the optimisation problem could also be\n  improved. At first, the networks are described with a weight function\n  $\\mathbf{w}$ and $\\mathbf{u}$, respectively. Later on, this notation\n  is changed to include $\\mathbf{\\theta}$ for a cluster representative.\n  This should be clarified; I understand that $\\mathbf{\\theta}$ is just\n  another weight function, is this correct?\n\n- How should the regularisation strength $\\lambda$ be chosen in\n  practice? I really like the discussion of the 'extreme cases' that one\n  can obtain, but a more specific discussion later on in the\n  experimental section would be appreciated. I would also suggest to\n  consider the inclusion of a 'target function' plot in which $\\lambda$\n  is being varied; it would be interesting to see how the overall\n  accuracy, for instance, depends on this parameter. Knowledge about the\n  stability of a specific choice for $\\lambda$ would help to instil more\n  trust into the method.\n\n- As for the experimental section, I think it would strengthen the paper\n  if more details were provided, in particular when it comes to the\n  validation experiment. It is astonishing to me that existing methods\n  all *fail* to cluster such networks with pronounced modularities. \n  I would suggest to discuss this.\n\n- I also do not understand how the comparison partner methods are\n  working here; are all weights of the network being vectorised into\n  a feature vector of the same size? This points needs elucidation\n  because although the number of vertices is always the same, such\n  a vectorisation does not account for the fact that a graph-level\n  representation needs to be permutation-invariant here; node $1$ in one\n  network is *not* the same as node $1$ in another network. If the\n  vectorisation strategy does *not* account for this, it might be an\n  explanation for the bad performance of other methods.\n\n- Moreover, when it comes to the comparison of different methods, simple\n  statistical baselines (for instance a feature vector based on degrees,\n  overall modularity of nodes, clustering coefficient, etc.) could also\n  be employed (if they are unsuitable, this should at least be\n  discussed). I would anticipate that $k$-means based on network summary\n  statistics might perform better than $k$-means using vectorised\n  weights? It would also be interesting to see a simple graph kernel\n  being employed here, for instance a graph kernel using a graph-level\n  histogram; since the networks are not excessively large, adding such\n  additional comparison partners should be still be possible.\n\n- The same comments apply, *mutatis mutandis*, to the discussion of the\n  brain network data set. Here, it would be imperative to show different\n  results for different values of $\\lambda$. Moreover, given the large\n  standard deviations, it seems that almost all methods are performing\n  similarly here; is there a reason for such a high variance in the\n  results? This should be briefly discussed.\n\n- Out of curiosity: would such an experiment benefit from a more fuzzy\n  definition of clusters? The method should potentially allow for this,\n  I think, and this might result in better clusters, in particular when\n  it comes to an unclear delineation between wake and sedated states.\n\n## Typos, word-smithing, etc.\n\nOverall, the writing in this paper flows well and the language is clear.\nThere are some cases in which articles are missing or a plural form\nmight be employed, but this does not prevent a clear understanding of\nthe text. Here are two examples of this (additional ones can be found\nthroughout the text; since some of them boil down to personal\npreference, I will refrain from listing them):\n\n- 'cycle structure is ubiquitous' --> 'cycles are ubiquitous'\n\n- 'takes infinitely large amount of work' --> 'takes an infinitely large amount'\n\n", "summary_of_the_paper": "This paper presents a novel algorithm for clustering networks based on\ntheir topological properties. To this end, an algorithm based on\npersistent homology (a method from computational topology that permits\nthe calculation of multi-scale features of unstructured and structured\ndata sets) is introduced. The key feature of the algorithm is that it\nmanages to substantially reduce the cost of 'matching' topological\nfeatures between two different data sets, thus making their comparison\nand similarity assessment computationally feasible. The paper provides\nan algorithm that can employ *both* geometrical and topological features\nof a network (with an appropriate regularisation term); experiments\ndemonstrate the general utility of the algorithm.\n", "summary_of_the_review": "Overall, this is a very interesting paper with a very relevant and\ntimely topic (potentially high impact). The theory is strong and\nwell-explained, even though the current write-up suffers from minor\nformulation issues, which, however, do not detract from the overall\nclarity of the message. I lean towards accepting the paper with the\nproviso that clarity is improved and, most importantly, my comments\nconcerning the experiments are being considered. At present, it is\nslightly unclear for non-expert readers to judge the overall utility of\nthe algorithm since the choice of comparison partners and their training\nhave yet to be clarified.\n\n**Update after rebutall**: I thank the authors for their updates to the paper;\nmy concerns were addressed, and I am happy to raise my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Initially, we had some borderline scores for this paper. After the (indeed very convincing!) rebuttal and a the end of the discussion phase, however, all reviewers agreed that this is a very solid piece of work, with significant methodological and practical contributions. I fully share this positive impression of the paper!.
Decision: Accept (Poster)