Graphon based Clustering and Testing of Networks: Algorithms and Theory
Authors: Mahalakshmi Sabanayagam
Leena Chennuru Vankadara
Debarghya Ghoshdastidar
Venue: ICLR 2022 Poster (2022)
Keywords: Clustering
Networks
Graphs
Two-sample testing
Graphon

Abstract: Network-valued data are encountered in a wide range of applications, and pose challenges in learning due to their complex structure and absence of vertex correspondence. Typical examples of such problems include classification or grouping of protein structures and social networks. Various methods, ranging from graph kernels to graph neural networks, have been proposed that achieve some success in graph classification problems. However, most methods have limited theoretical justification, and their applicability beyond classification remains unexplored. In this work, we propose methods for clustering multiple graphs, without vertex correspondence, that are inspired by the recent literature on estimating graphons---symmetric functions corresponding to infinite vertex limit of graphs. We propose a novel graph distance based on sorting-and-smoothing graphon estimators. Using the proposed graph distance, we present two clustering algorithms and show that they achieve state-of-the-art results. We prove the statistical consistency of both algorithms under Lipschitz assumptions on the graph degrees. We further study the applicability of the proposed distance for graph two-sample testing problems.

Published as a conference paper at ICLR 2022
GRAPHON BASED CLUSTERING AND TESTING OF NET- WORKS: ALGORITHMS AND THEORY
Mahalakshmi Sabanayagam Technical University of Munich maha.. sabanayagamamm t.m.
Leena C. Vankadara
University of Tübingen
leena. whw.nuro--annaaarrraeeeee -tuebingee....nnnn de
Debarghya Ghoshdastidar
Technical University of Munich Munich Data Science Institute
ghoshdas@ i tu.. de
ABSTRACT
Network-valued data are encountered in wide range of applications, and pose challenges in learning due to their complex structure and absence of vertex corre- spondence. Typical examples of such problems include classification or grouping protein structures and social networks. Various methods, ranging from graph kernels to graph neural networks, have been proposed that achieve some success in graph classification problems. However, most methods have limited theoreti- cal justification, and their applicability beyond classification remains unexplored. In this work, we propose methods for clustering multiple graphs, without vertex correspondence, that are inspired by the recent literature estimating graphons- symmetric functions corresponding to infinite vertex limit of graphs. We propose novel graph distance based on sorting-and- and-smoothing graphon estimators. Using the proposed graph distance, we present two clustering algorithms and show that they achieve state-of-the-art results. We prove the statistical consistency of both algorithms under Lipschitz assumptions on the graph degrees. We further study the applicability of the proposed distance for graph two-sample testing problems.
INTRODUCTION
Machine learning on graphs has evolved considerably over the past two decades. The traditional view towards network analysis is limited to modelling interactions among entities of interest, for in- stance social networks world wide web, and learning algorithms based graph theory have been commonly used to solve these problems (Von Luxburg 2007 Yan et al., (006).. However, recent ap- plications in bioinformatics and other disciplines require different perspective, where the networks are the quantities of interest. For instance, it is of practical interest to classify protein structures as enzyme or non-enzyme (Dobson Doig 2003) detect topological changes in brain networks caused by Alzheimer's 's disease (Stam et al. 2007). In this paper, learning from network-valued data refers to clustering where each network is treated as an entity, as opposed to the traditional network analysis problems that involve a single network of interactions (Newman 2003).
Machine learning on network-valued data has been an active area of research in recent years, al- though most works focus on the network classification problem. The generic approach is to convert the network-valued data into a standard representation. Graph neural networks are commonly used for network embedding, that is, finding Euclidean representations of each network that can be fur- ther used in standard machine learning models (Narayanan et al. 2017 7 Xu et al. 2019). In contrast, graph kernels capture similarities between pairs of networks that can be used in kernel based learning algorithms (Shervashidze et al. 2011 Kondor & Pan 2016 Togninalli et al. 2019). In particular, the graph neural tangent kernel defines graph kernel that corresponds to infinitely wide graph
ral networks, and typically outperforms neural networks in classification tasks (Du et al. (2019). A more classical equivalent for graph kernels is define metrics that characterise the distances be-

---

Published as a conference paper at ICLR 2022
tween pairs of graphs (Bunke & Shearer, 1998), but there has been limited research on designing efficient graph distances and developing algorithms for clustering seework-valuee data.
The motivation for this paper stems from two shortcomings in the literature network-valued data analysis: first, the efficacy of existing kernels or embeddings have not been studied beyond net- work classification, and second is the lack of theoretical analysis of these methods, particularly in the small sample setting. Generalisation error bounds for graph kernel based learning exist (Du et al. 2019), but these bounds, based on learning theory, are meaningful only when many networks are available. However, in many applications, one needs to learn from a small population of large networks and, in such cases, an informative statistical analysis should consider the small sample, large graph regime. To address this issue, we take inspiration from the recent statistics literature on graph two-sample
aartingggvved two (populations of) large graphs, the goal to decide if they are from same statistical model or not. Although most theoretical studies in graph two-sample test- ing focus on graph with vertex correspondence (Tang et al.) 2017a| Ghoshdastidar & von Luxburg, 2018), some works address the problem of testing graphs on different vertex sets either by defining distances between graphs (Tang et al. 2017b Agterberg et al. 2020) or by representing networks in terms of pre-specified network statisties (Ghoshdastidar et al.] 2017)_ The use of network statis- ties for clustering network-valued data is studied in Mukkhereee et al. (2017). Another fundamental approach for dealing with graphs of different sizes is graph matching, where the objective is to determine the vertex correspondence. Graph matching is often solved by formulating it as an opti- mization problem (Zaslavskiy et al. 2008 Guo et al.) (019) or defining graph edit distance between the graphs (Riesen & Bunke [009 Gao et al. 2010). Although there is extensive research on graph matching, the efficacy of these methods in clustering network-valued data remains unexplored.
Contribution and organisation. In this work, we follow the approach of defining meaningful graph distances based on statistical models, and use the proposed graph distance in the context of learning from networks without vertex correspondence. In particular, we propose graph distances based on graphons. Graphons are symmetric bivariate functions that represent the limiting structure for a sequence of graphs with increasing number of nodes (Lovász & Szegedy (006). but can be also viewed as a nonparametric statistical model for exchangeable random graphs (Diaconis & Janson, 2007 Bickel & Chen 2009). The latter perspective is useful for the purpose of machine learning since it allows us to view the multiple graphs as random samples drawn from one or more graphon models. This perspective forms the basis of our contributions, which are listed below:
1) In Section 2 we propose a distance between two networks, that do not have vertex correspondence and could have different number of vertices. We view the networks as random samples from (un- known) graphons, and propose a graph distance that estimates the L2-distance between the graphons. The distance is inspired by the aantog-aaddsmoothingg graphon estimator (Chan & Airoldi 2014).
2) In Section 3 we present two algorithms for clustering network-valued data based on the proposed graph distance: a distance-based spectral clustering algorithm, and similarity based semi-definite programming (SDP) approach. We derive performance guarantees for both algorithms under the assumption that the networks are sampled from graphons satisfying certain smoothness conditions.
3) We empirically compare the performance of our algorithms with other clustering strategies based on graph kernels, graph matching, network statistics etc. and show that, on both simulated and real data, our graph distance- spectral clustering algorithm outperforms others while the SDP approach also shows reasonable performance, and they also scale large networks (Section 3.3))
4) Inspired by the success of the proposed graph distance in clustering, we use the distance for graph two-sample testing. In Section 4 we show that the proposed two-sample test is statistically consis- tent for large graphs, and also demonstrate the efficacy of the test through numerical simulation.
We provide further discussion in Section aldd present the proofs of theoretical results in Appendix.
2 GRAPH DISTANCE BASED ON GRAPHONS
Clustering or testing of multiple networks requires a notion of distance between the networks. In this section, present transformation that converts graphs of different sizes into a fixed size representation, and subsequently, propose a graph distance inspired by the theory of graphons. We first provide some background on graphons and graphon estimation. Graphon has been studied in
2

---

Published as a conference paper at ICLR 2022
the literature from two perspectives: limiting structure for infinite sequence of growing graphs (Lovász & Szegedy, 2006), or as exchangeable random graph model. In this paper, we follow the latter perspective. A random graph is said to be exchangeable if its distribution is invariant under permutation of nodes. DDacooni & Janson (2007) showed that any statistical model that generates exchangeable random graphs can be characterised by graphons, introduced by Lovász & Szegedy (2006). Formally, a graphon is a symmetric measurable continuous function w [0, - [0, I] where w(x, y) can be interpreted as the link probability between two nodes of the graph that are as- signed values and y, respectively. This interpretation propounds the following two stage sampling procedure for graphons. To sample a random graph G with nodes from a graphon w, in the first stage, one samples n variables U...... Un uniformly from [0, 1] and constructs a latent mapping be- tween the sampled points and the node labels. In the second stage, edges between any two nodes j are randomly added based on the link probability w(U,, Uz). Mathematically, if we abuse notation to denote the adjacency matrix by G E Ixxn, we have
U1....,U Un
tid Uniform(0, (0, 1]
G3 ~ Bernoulli (w, U)) for all < and
We consider problems involving multiple networks sampled independently from the same (or dif- ferent) graphons. We make the following smoothness assumptions the graphons.
Assumption (Lipschitz continuous) A graphon w is Lipschitz continuous with constant I. if
[w[u, v) - w(u', r²)l S LV (u (u- rd)2 + v1) v²)? for every u, U, u,u, [0, 10.
Assumption (Two-sided Lipsehitz degree) A graphon w has two-sided Lipschitz degree with constants A1 > 0 if its expected degree function defined by g(u) So w(u, v)dv, satisfies Aa a u'| S (z( g(('() Au u'l for every u, u' [0,1].
One of the challenges in graphon estimation is due to the issue of non-identifiabilit, that is, differ- ent graphon functions w can generate the same random graph model. In particular, two graphons w and w' generate the same random graph model if they are weakly isomorphic-there exist two mea- sure preserving transformations d, o' : [0, 1] + [0, 1] such that w((()), ((v) - w' (ø'(u), o' (v)). Moreover, the converse also holds meaning that such transformations
known to be the only source of non-identifiability (Diaconis & Janson 2007). This weak isomorphism induces equiva- lence classes the space of graphons. Since our goal only to cluster graphs belonging random graph models, we simply make the following assumption on our graphons.
Assumption 3 (Equivalence classes) Any reference to K graphons, Wi,..., WK, assumes that, for every i, either W; = w or w; and wi belong to different equivalence classes. Furthermore, with- out loss of generality, we assume that every graphon w; is represented such that the corresponding degree function 9i is non-decreasing.
Remark on the necessity of Assumptions 13 Assumption ! i standard in graphon estimation literature (Klopp et al., 2017) since it avoids graphons corresponding inhomogeneous random graph models. is known that two graphs from widely separated inhomogeneous models (in Lz- distance) are statistically indistinguishable (Ghoshdastidar et al. (020)). and hence, it is essential to ignore such models to derive meaningful guarantees. Assumption 2 ensures that, under a measure- preserving transformation, the graphon has strietly increasing degree function, which is canonical representation of an equivalence class of graphons (Bickel & Chen 2009). Assumption is needed since graphons can only be estimated up to measure- presservii transformation. As noted above, is inconsequential for all practical purposes but simplifies the theoretical exposition.
Graph transformation. In order to deal with multiple graphs and measure distances among pairs of graphs, we require transformation that maps all graphs into common metric space-the space of all no X no symmetric matrices for some integer nlg. While the graphon estimation literature provides several consistent estimators (Klopp et al. 2017 Zhhng al. (017). only the histogram based sorting-ande and-smoothing graphon estimator of Chan & Airoldi (2014) can be adapted to meet the above requirement. We use the following graph transformation, inspired by Chan & Airoldi (201)). The adjacency matrix G of size n x n is first reordered based on a non-unique permutation a, such that the empirical degree based on this permutation is monotonically increasing. The degree
3

---

Published as a conference paper at ICLR 2022
sorted adjacency matrix is denoted by G It is then transformed to 'histogram' A n
1 h
Ag
(G-1)44.00-10+t where h
and [.] is the floor function.
no
Proposed graph distance. Given two directed or undirected graphs G1 and G2 with and nodes, respectively, we apply the transformation T to both the graphs with no S min n2). We propose to use the graph distance
d(1 = || - A2l|r,
where A1 and Ag denote the transformed matrices and || ||e denotes the matrix Frobenius norm. Proposition shows that, if G1 and G2 sampled from two graphons, then the graph dis- tance ( consistently estimates the L2 between the two graphons, which defined as ||- - = -oo So (wi(2, v) (2 y))² dr
Proposition 1 (Graph distance is consistent) Let wi and w2 satisfy Assumptions 3 Let G1 and G2 be random graphs with at least n nodes sampled from the graphons wi and w2, respectively. If O, then with high probability (w.h.p.).
+ 00 and nig is chosen such that "i log a
n
||| w1 - w2 ll,, - ((G1,G2) = 0
Proof sketch. We define a novel technique for approximating the graphon. The proof in Ap- pendix A.I first establishes that the approximation error is bounded using Assumption !I Conse- quently, relation between approximated graphons and transformed graphs is derived using lemmas from Chan Airoldi 2014). Proposition Ti subsequently proved using the above two results. D
Remark on Proposition 1 for sparse graphs. The defined sampling procedure for graphon gen- crates dense graphs, deviating from the real world sparse networks. To adapt to sparse graphs, one may modify the sampling procedure to GaylUs, U, (ernoulli (uU; U,)) where p depends only on n Olhede & Wolfe 2014). Under this process, the consistency result in Proposition [ re- mains unchanged for = 52( log n/n) (proof in Appendix A.2). This bound cannot be improved the expected real world measure where p = S2(log n//n), because of the degree sorting step in (T. Nevertheless, our analysis allows for relatively sparser graphs with strong consistency result.
Notation. For ease of exposition, Proposition [ as well main results are stated asymptotically using the standard (()) and ((-) notations, which subsume absolute and Lipschitz constants. We "with high probability" (w.h.p.) state that the probability of event converges to cc.
GRAPH CLUSTERING
We now present the first application the proposed graph distance (2) in the context clustering Nowork-valleek data. We particularly interested in the setting where needs to cluster small population of large graphs, that is, minimum graph size n grows faster than the sample size m. This scenario is relevant in practice bioinformatics few graphs (see real datasets in Section (.3).. Theoretically, this perspective complements guarantees for (graph) kernels that are applicable only in supervised setting and large sample regime, m - co. In contrast, our guarantees are more conclusive for bounded m and large graph size, + oc.
neuroscience application often deals with very
3.1 DISTANCE BASED SPECTRAL CLUSTERING (DSC)
Given m graphs with adjacency matrices GI.... Gm- we propose a distance based clustering al- gorithm where we apply spectral clustering to an estimated distance matrix. The distance matrix
D E mm is computed on all pairs graphs using the defined estimator function (2). that is D. = dG, G,). Unlike the standard Laplacian based spectral clustering, which is applicable for adjacency similarity matrices, the method suggested by Mukkherjee et al. (2017) that
4

---

Published as a conference paper at ICLR 2022
computes the K leading eigenvectors of Đ (corresponding to the K smallest eigenvalues in magni- tude) and applies k-means clustering to the rows of the eigenvector matrix resulting in K number of clusters. We refer to this distance based clustering algorithm DSC, described in Algorithm [ of Appendix. To derive the statistical consistency of DSC, we consider the problem of clustering m random graphs of potentially different sizes, each sampled from one of K graphons. We establish the consistency in Theorem by proving that the number of misclustered graphs + 0 asymptotically.
Theorem (Consistency of DSC) Consider K graphons satisfying Assumptions 7 and ran- dom graphs Gi...., Gan. each sampled from one of the K graphons (assume there is at least one graph from each graphon). Define the distance matrix D mm such that Dij ||ls wil L2 where wi and Wj are the graphons from which G; and Gj are generated. Let n. be the size of the smallest graph, and be the K-th smallest eigenvalue value of D in magnitude. As n - oc, if no is graphs w.h.p.
chosen such that m²nn log n - O, then DSC misclusters at most O
Proof sketch. The proof, given in Appendix A.3 uses the Davis-Kahan spectral perturbation theorem to bound the error in terms of [ Dl which is further bounded using Proposition 1
While the number of misclustered graphs seem depend on m², note that there is an inverse dependence on 72 which has dependence on m (see Corollary that illustrates it for a specific case). Moreover, our focus is the setting where asymptotically vanishes. It is natural to wonder whether the dependence on m and no is tight in the above bounds. Currently, we do not know the optimal rates, but deriving this would be difficult due the strong dependency of entries in D and slow rate of convergence of the graph distance in Proposition I The presence of y in the above clustering error bound makes Theorem less interpretable. Hence, we also consider the specific case of K (two graphons) in the following result, along with the assumption that equal number of graphs are generated from both graphons.
O(1) and n. no oo, in which case, the error
Corollary Let w f w' be two graphons satisfying Assumptions 7 and m is bounded even number. Assume that equal number of graphs are generated from w and w'. For any no and large enough constant C such that ||l w L 2 C m and m²ng logn as n + co, the number of
graphs misclustered by Algorithm D goes to zero w.h.p.
The corollary implies that given the observed graphs are large enough, and if the choice of no is relatively small, no < /n/log and the graphons are ((2)) 2 apart in Læ-distance, then the clustering is consistent. Intuitively, it can be understood that if we condense large graphs to a small representation (small no),, then the clusters can be identified only if the models are quite dissimilar.
3.2 SIMILARITY BASED SEMI-DEFINITE PROGRAMMING (SSDP)
We propose another algorithm for clustering m graphs based on similarity between pairs of graphs. The pairwise similarity matrix S E mm is computed by applying Gaussian kernel on the distance between the graphs, that S.j = exp (- d.G. where o On are parameters. For theo- 0:0,
retical analysis, assume di ... on is fixed, but in experiments, the parameters chosen adaptively. We use the following semi-definite program (SDP) (Yan et al.; 2018 Perrot et al.) 2020) to find membership of the observed graphs. Let X E mmxx be the normalised clustering matrix, that is Xúj = 1/IC| if and j belong to cluster C, and 0 otherwise. Then, SDP for estimating X is:
max (Sx) X
s.t. X 2 0, X = 0, X1 1, trace(X) K,
(4)
where 2 0, X 2 0 ensure that X is a non-ne non-negative, positive semi-definite matrix, and 1 denotes the vector of all ones. We denote the optimal X from the SDP as X. Once we have X, we apply standard spectral clustering on X to obtain clustering of the graphs. We refer to this algorithm as SSDP, described Agorithmm2os Appendix. We present strong consistency result for SSDP below.
Theorem (Consistency of SSDP) Consider K graphons, Wi...., WK. satisfying Assumptions 7 3 and random graphs, each sampled from one of the K graphons. Let be the size of the smallest
graph. As n. - oc. if nu is chosen such that m² n logn + 0 and min || [e wy wrll ll = Ω m then
191
the number of graphs misclustered by SSDP is zero whh.p.
5

---

Published as a conference paper at ICLR 2022
Proof sketch. The proof in Appendix A.4 adapts Perrot al. (2020) Proposition 1) to the present setting and combines it with Proposition I to derive the stated condition for zero error.
Theorem is slightly stronger than Theorem I or Corollary D since SSDP achieve a zero clustering
error for large enough graphs. This theoretical merit of SDP over spectral clustering is known in the statistics literature. Similar to Corollary the choice of no is important such that it does not violate the minimum Li-distance condition in the theorem to ensure consistency.
Remark the knowledge of K. Above discussions assume that the number of clusters K is known, which is not necessarily the case in practice. To tackle this issue, one can estimate K using Elbow method (Thorndike) (953) approach from Perrot et al. (2020),and then use it as input in our algorithms, DSC and SSDP. One can modify the SDP (4) and Theorem 2 to the case where K adaptively estimated. However, we found the corresponding algorithm, adapted from Perrot al. 20200, to be empirically unstable in the present context. Hence, the knowledge of K is assumed in the following experiments, which also allows the efficacy of the proposed algorithms and graph distance to be evaluated without the error induced by incorrect estimation of K.
3.3 EXPERIMENTAL ANALYSIS
In this section, we evaluate the performance of our algorithms DSC and SSDP, both in terms of accuracy and computational efficacy. We measure the performance of the algorithms in terms of error rate, that is, the fraction of misclustered graphs by using the source of the graphs as labels. Since clustering provides labels up to permutation, match the labels. The performance can also be measured in terms of Adjusted Rand Index (results in Appendix C.3 We use simulated and real datasets for evaluation and obtain all our experimental results using Tesla K80 GPU instance with 12GB memory from Google. Code available in Github
the Hungarian method (Kuhn) 1955) to
Simulated data. We generate graphs of varied sizes from four graphons W1(u, (u, v) ue, W2(u, v) exp {- max(u, e)).76). Vz(,,v) eexp { (00.5 (minnu, v) + 0.55 + ]o.5)} and Wa(u, v) = lu v/. The simulated graphs are dense and the graph sizes are controlled to study how algorithms scale. Their corresponding L2 distances between pairs of graphons is shown later in Figure and the heatmap of the graphons are visualised in Figure in Appendix.
Real data. We use datasets from two contrasting domains: small molecule datasets from Bioin- formatics and large network datasets from Social Networks. We use Proteins (Borgwardt et al.) 2005 KKI (Pan et al. 2016), OHSU (Pan et al. (016)) and Peking_/ (Pan et al. 2016) datasets from Bioinformatics, and Facebook_Ctl (Oettershagen et al.) 2020). ct al. 2020), Ego Nets (Rozemberczki et al. 2020) and Reddit Reddit_Binary (Yanardag & Vish- wanathan 2015) datasets from Social Networks. We sub-sample few graphs from each dataset by setting a minimum number of nodes to validate clustering small number of large graphs (small m, large n). The number (#graphs) and size (#nodes) of the graphs are listed in Figure [ tables. We consider all combinations of the datasets for three and four clusters in both the domains separately.
(Rozemberczki
Choice of ng and 0;. As noted in our algorithms DSC and SSDP, no is an input parameter. Theo- rems] I and show the choice of no O( ((///// /n/log n).. Hence, we set no = /n/ log n where n is the minimum number of nodes. In Appendix C.2 we use simulated data to show that the above choice of no is reasonable (if not the best) for both DSC and SSDP. Furthermore, the similarity matrix Š in SSDP is computed using parameters a; and we set o; = d(G., Gsnn) where Gsmn is the fifth nearest neighbour of G. Hence, apart from knowledge of K, our algorithms are parameter-free.
Performance comparison with existing methods. We compare our algorithms with a range of approaches for measuring similarity or distance among multiple networks. Most methods discussed below provide a kernel or distance matrix to which we apply spectral clustering to obtain the clusters:
1) Network Clustering based on Log- Mog-Mssents (NCLM) is an embedding based clustering strategy for different sized graphs (Mukherjee et al. 2017) that is based on network statistics called log moments. Log moments for a graph with adj adjacency matrix A and number of nodes is obtained by (log (A)) log (mz(A)) ,.... log (m) (A))) where m²(A) = traco(A/nn) and J is parameter.
2) Wasserstein Weisfeiler-Lehman Graph Kernels (WWLGK) is a recent graph kernel that is based on the Wasserstein distance between the node feature vector distributions of two graphs proposed by Togninalli et al. 2019).

---

Published as a conference paper at ICLR 2022
0.6
DSC (eurs]
Ereor rete
SSDP (ours)
GNTK
NCLM
NCGMM
0.2
NCMMD
TLE Time Limit Exceeded
0.0
W,, Ws. W:
Ws. Ws. W.
W.. We
Wi. W/
Wy, Ws. Ws. W4
[trot rate
0.6
Btolnformatics
#graphs
#nodes
0.4
B1
Proteins
KX11
7
7
[273, 6201
[62, 90]
Paking
[86, 134]
0.0
92.
0,.0s.04
P1.02.04
P2.0s.84
By. Bg.
Enorr rele
0.4
Social Networks
Facebook Ctl
#graphs
10
[100. 100]
#nodes
Stargszers
0.2
Daezer Nets
10
[208,
Reddit Binary
12
[3219, 3782]
52.52.5a
So
Sc
Sq. S2.52,9..5
Figure 1: Evaluation of DSC and SSDP with other methods. (row 1) Results on simulated data. (rows 2 and 3) Results on real data from Bioinformatics and Social Networks, respectively. DSC outperforms in majority of the cases. Tables in rows and show details of the considered datasets.
3) Graph Neural Tangent Kernel (GNTK) is another graph kernel that describes infinitely wide graph neural networks derived by Du al. (2019). Both WWLLGK and GNTK provide tate-of-theear performance in graph classification with GNTK outperforming most graph neural networks.
4) Network Clustering algorithm based Maximum Mean Discrepancy (NCMMD) considers graph metric (MMD) to cluster the graphs. MMD distance between random graphs is proposed
efficient test statistic for random dot product graphs (Agterberg al.] 2020). We compute
MMD between the graphs that are represented by latent finite dimensional embedding called spectral adjacency embedding with the dimension as a parameter.
5) In Network Clustering algorithm based on Graph Matching Metric (NCGMM), we match two graphs of different sizes by appending null nodes the small graph (Guo et al. 2019 and compute Frobenius norm between the matched graphs as their distance. Although the graph metrics (MMD and graph matching) are for different purposes, we evaluate their efficacy in the context of clustering.
The parameters in the algorithms are and a; in DSC and SSDP, J in NCLM, number of iterations (#irr) to perform in WWI.GK, number of layers (#layer) graph neural networks for GNTK, in NCMMD and none in NCGMM. We fix in our algorithms using the theoretical bound and a is set adaptively as discussed, whereas use grid search to tune the parameters for other algorithms.
Evaluation on simulated data. We sample 10 graphs of varied sizes between 50 and 100 nodes from each of the four graphons Figure 4 and perform the experiments by considering all com- binations of three and four clusters of the graphons. Based the theoretical bound, ng is fixed to 5 as n = 50. We report the performance for = 8, r 3. #itr = and #layer = as these produce the best results. The first of Figure 1 shows the average performance of the al- gorithms computed over 5 independent runs. We observe that our algorithm DSC outperforms all the other algorithms, achieving nearly zero error in all cases, and SSDP also performs competitively by standing second or third best. The graph kernels, WWLGK and GNTK, and the graph metric based method NCGMM typically do perform well. NCMMD either performs very well or quite poorly. We sample small graphs since otherwise GNTK cannot run due to memory requirement for dense large graphs and NCGMM has high computation time. Appendix C.4 includes evaluation of the algorithms except GNTK and NCGMM on larger graphs, where we observe similar behaviour.
Evaluation on real data. We consider all combinations of three and four clusters of both Bioinfor- matics and Social Networks separately. The second and third rows of [sow the performance with no = 30, / 8, r = 3, #tr = 1 and #layer = 2, and the upper limit of 7200 seconds (2 hours) as rumning time of algorithms. We observe DSC outperforms other algorithms by a large mar- gin in majority of the combinations, while in the other combinations like (Proteins.KKL.Peele KKL,Peking_. DSC performs well with very small margin to the best performing one. Although NCLM and GNTK compare favorably in Social Networks datasets, they typically have high error rate in Bioin- formatics simulated datasets, suggesting that they could be well suited for large networks, whereas

---

Published as a conference paper at ICLR 2022
DSC is more versatile and suitable for all networks. SSDP performs moderately real data, but it achieves the smallest error in some cases, implying that it is suited for certain types of networks.
Computation time comparison. Figure shows the time (measured in seconds) taken by cach al- gorithm for four clusters case, plotted in log scale. Appendix C.5 illustrates similar behavior in three clusters case well. Our algorithms, DSC and SSDP, perform competitively with respect to time as well. In addition, it scales effectively for large graphs unlike other algorithms. It is worth noting that although NCLM takes lesser time than DSC and SSDP for small graphs. it takes longer for large social networks datasets, thus favoring our methods in terms of both aceuracy and scalability, Graph matching based algorithm, NCGMM. has severe scalabil- ity issue showing the inapplicability of such methods to learning problems. We also evaluate the scalability of all algorithms by measuring the time for clustering different sets of varied sized graphs from graphons Wi, W2, W3 and W4. Detailed discussion on high scalability of DSC and SSDP is given Appendix C.6
DSC
NCGMM
55DP
WWLGK
Time Limit
NCLM
GNTK
Exceeded
Log Time 1
6
Wu. We. W.,W B, S,,5,,5.5..
Figure 2: Computation time
4 GRAPH TWO- SAM--E TESTING
Inspired by the remarkable performance of our graph distance 22 in clustering, we analyse its appli- cability in graph two-sample testing. Two-sample testing is usually studied in the large sample case m - oo, and several nonparametric tests are known that could also be applied to graphs. However, it is also relevant to study the small sample setting in graphs, particularly two large graphs are statistically identical or not (Ghoshdastidar et al. 2020; Agterberg et al. 2020).
2, that is, whether
We consider the following formulation of the graph two-sample problem, stated under the assump- tion that the graphs are sampled from graphons. Given two random graphs, G1 sampled from some model (here, graphon w1), and G2 from another model W2, the goal is determine which of the following hypothesis is true: Ho [w) = W2} or H, : { [1 # W2 ||00 W2 w22lz,, 2 Φ) for some >> 0. Existing works consider alternative random graph model, such as inhomogeneous Erdös- Rényi models or random dot product graph models, which are more restrictive. The condition & >> 0 is necessary if one only has access to finitely many independent samples (Ghoshdastidar et al. 2020). A two-sample test T is binary function of the given samples such that T = denotes that the test rejects the null hypothesis Ho and T = 0 implies that the test rejects the alternate hypothesis Ha- The goodness of two-sample test is measured in terms of the Type-I and Type-II errors, which denote the probabilities of incorrectly rejecting the null and alternate hypotheses, respectively. The goal of this section is to show that one can construct a test T that has arbitrarily small Type-I and Type-Il errors. For this purpose, we consider the test
T: I G2)
(5)
for some O, where T(--} is the indicator function and d(Gi, G2) is the proposed graph distance for some choice of integer no- We state the following theoretical guarantee for the test T.
Theorem 3 Assume that the graphons W1, W2 satisfy Assumptions 73 and let the graphs G1 wi and G2 ~ W2 have at least n nodes. As n - co, there is a choice of & such that the Type-l and Type-Il errors of the test T in (5) go if n2 log only on the Lipschitz constants.
0 and @ > C, where the constant C depends no"
Theorem 3 shows that the test T in (5] can distinguish between any pair of graphons that have separation [w - w22l1., ({1/no)) with arbitrarily small error, if the graphs are large enough.
Empirical analysis. We validate the consistency result in Theorem 3 by computing power of the proposed test T, which measures the probability of rejecting the null hypothesis Hy. Intuitively, power of the test for graphs sampled from same graphons should be small (close to a pre-specified significance level) since Ho must not be rejected, whereas, it should be close to for graphs sampled from different graphons. As known in the testing literature, theoretical threshold, & in (5), is typi- cally conservative in practice and the rejection/acceptance is decided based p-values, computed using bootstrap samples. To this end, we follow the bootstrapping strategy in Ghoshdastidar von Luxburg (2018. Boot-ASE algorithm). We also compare the test T by replacing d(G1, in
8

---

Published as a conference paper at ICLR 2022
W:
0.00
0.25
0.22
0.38
W;
0.06
1.00
1.00
1.00
W1
0.04
0.99
0.90
0.05
W;
0.57
1.00
1.00
1.00
W9
0.25
0.00
0.10
0.34
W2
1.00
0.06
0.97
1.00
W9
0.99
0.03
0.26
1.00
W3
1.00
0.64
0.47
1.00
0.00
Wa
1.00
0.03
1.00
99
W3
0.51
1.00
0.38
0.34
0.26
0.00
1.00
1.00
1.00
0.13
0.05
1.00
1.00
0.03
1.00
1.00
1.00
0.77
W:
Ws
W4
W3
W2
Wg
W4
W:
W2
W3
W4
Wi
W9
W3
Wa
distance
Proposed Distance
Log Moments
MMD
Figure 3: (left) Lg distance between the graphons W1. W2. W3 and W4. (other plots) Average power of the test 5 for graph pair of sizes 100 and 200, sampled from every pair of graphons.
with two other statistics, log moments (Mukherjee et al. 2017) and MMD, an efficient test statistics for random dot product graphs (Agterberg et al., 2020). We perform the experiment by sampling graphs G ~ Wi and G2 ~ W2 of size n and 2n, respectively, where w/ and w2 are chosen from graphons W1, W2. Ws, W4. The power of I is computed for n 100 (thus no = 10 from the theo- retical bound) and the significance level 0.05, averaged over 500 trials of bootstrapping 100 samples generated from all pairs of graphons. The plots in Figure show the average power of T with our proposed distance, log moments and MMD as d(G,, G2), respectively. From the results, it is clear that T using our distance can distinguish between graphons that quite close too (smallest L2 distance for W2 and Wa), whereas, other test statistics are weak as log moments statistic accepts Ho even when it wrong (see W1 and Wa) and MMD based test rejects it strongly almost always (see diagonal). Appendix C shows similar result for small and large n, and evaluation on real datasets.
5 CONCLUSION
There has been significant progress in learning on complex data, including network-valued data. However, much of the theoretical and algorithmic development have been in large sample problems, where one has access to m - oo independent samples. Practical applications of cetwork-valued data analysis often leads to small sample, large graph problems setting where the machine learn- ing literature is quite limited. Inspired by graph limits and high-dimensional statistics, this paper proposes a simple graph distance ( based on non parametric graph models (graphons).
Sections B demonstratee that the proposed graph distance leads to provable and practically effective algorithms for clustering (DSC and SSDP) as well as two-sample testing (5). Extensive empirical studies on simulated and real data show that the clustering based on the graph distance 2 out- performs methods based on more complex graph similarities or metrics, both in terms of accuracy and scalability. Figures 1 show that DSC achieves best performance for both small dense graphs (simulated graphons) as well as large sparse graphs (social networks). On the other hand, popular machine learning approaches-grappe kernels or graph matching- in large graphs and their performance may not improve as + co, see WWLGK in Figure 7
be computationally expensive
Statistical approaches, such as the proposed clustering algorithms and two-sample test, show better performance on large graphs (Figures I 3 and Appendix C.4). Theorems TH theoretically support this observation by showing consistency of the clustering and testing methods in the limit of - co. The theoretical results, however, hinge on Assumptions 3 We remark that such smoothness and equivalence assumptions could necessary for meaningful non-parametric approaches, which also supported by the graph testing and graphon estimation literature. Further insights about the necessity of smoothness assumptions would aid in thcoretical and algorithmic development.
The poor performance of graph kernels and graph matching in clustering and small sample problems calls for further studies on these methods, which have shown success network classification. Fundamental research, combining graphon based approaches and kernels, could lead to improved techniques. Instead of sorting-and corting-and-smoottin amd-smoothing graphon estimator, other histogram based methods that reduce graphons to a fixed size by identifying block structures and averaging (Olhede & Wolfe, 2014) can be explored. However, the distance defined on such reduced graphons require alignment of the blocks between the graphons. While such methods do not require Assumption 2 and allow sparse graphs, the computationally inefficient alignment step pose practical challenge. Algorithmic modifications, such estimation of K, would be also useful in practice.

---

Published as a conference paper at ICLR 2022
6 ACKNOWLEDGEMENTS
This work has been supported by the German Research Foundation (Research Training Group GRK 2428) and the Baden-Württebberg Stiftung (Eliteprogram for Postdocs project "Clustering large evolving networks"). The authors thank the International Max Planck Research School for Intelli- gent Systems (IMPRS-IS) for supporting Leena Chennuru Vankadara.
ETHICS STATEMENT
The proposed clustering algorithms for network-valued data can naturally be evaluated real- world data, but no social interpretation about the results will be drawn. Moreover, development of fair clustering algorithms is not the focus of this project.
REPRODUCIBILITY STATEMENT
The assumptions for the theory are stated clearly in Assumptions 1 and all the theoretical re- sults, Proposition [ Theorems Corollary [ are proved in detail in Appendix A The imple- mentation of the considered algorithms with steps to reproduce the results available in Github Datasets used in the experiments are public and the links are pro- vided in downloade www.daaadaasseeeeeaaaaaaaaasasse s function of utils.pp The experimental results can be repro- duced by following graph.clusterie ipynb.
REFERENCES
Joshua Agterberg, Minh Tang, and Carey Priebe. Nonparametric two-sample hypothesis testing for random graphs with negative and repeated eigenvalues. arXiv preprint arXiv:2012.09828, 2020.
Peter Bickel and Aiyou Chen. A nonparametric view of network models and newman-girvan and other modularities. Proceedings of the National Academy of Sciences, 106650):21088-2107, 2009.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(Suppl 1): i47-i56, 2005.
Horst Bunke and Kim Shearer. A graph distance metric based on the maximal common subgraph. Pattern recognition letters, 19(3-4):255255 259, 1998.
Stanley Chan and Edoardo Airoldi. A consistent histogram estimator for exchangeable graph mod- cls. International Conference on Machine Learning, pp. 208-216, 2014.
Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. arXiv preprint arXiv:0712.27499, 2007.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Simon Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 5724-5734, 2019.
Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and applications, 13(1):113-129, 2010.
Debarghya Ghoshdastidar and Ulrike von Luxburg. Practical methods for graph two-sample testing. In Advances in Neural Information Processing Systems, pp. 3019-3028, 2018.
Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, and Ulrike Luxburg. Two- sample tests for large random graphs using network statistics. Conference on Learning Theory, pp. 954-977, 2017.
10

---

Published as a conference paper at ICLR 2022
Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg, et al. Two- sample hypothesis testing for inhomogeneous random graphs. Annals of Statistics, 48(4):2208- 2229, 2020.
Xiaoyang Guo, Anuj Srivastava, and Sudeep Sarkar. A quotient space formulation for generative statistical analysis of graphical data. Journal of Mathematical Imaging and Vision, pp. 735-752, 2019.
Olga Klopp, Alexandre B Tsybakov, Nicolas Verzelen, al. Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics, 45(1):316 13--:344,444 2017.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. In Advances in Neural Infor- mation Processing Systems, pp. 2990-2998, 2016.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933 (167)9333-97990 2006.
Soumendu Sundar Mukherjee, Purnamrita Sarkar, and Lizhen Lin. On clustering network-valued
data. In Advances in neural information processing systems, pp. 7071-7081, 2017.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05005 2017.
Mark EJ Newman. The structure and function of complex networks. SIAM review, 45(2):167-256, 2003.
Lutz Oettershagen, Nils M Kriege, Christopher Morris, and Petra Mutzel. Temporal graph kernels for classifying dissemination processes. In Proceedings of the 2020 SIAM International Confer- on Data Mining, pp. 496 504,,00,40 2020.
Sofia C Olhede and Patrick J Wolfe. Network histograms and universality of blockmodel approxi- mation. Proceedings of the National Academy of Sciences, 111(41):14722-1472)) 2014.
Shirui Pan, Jia Wu, Xingquan Zhu, Guodong Long, and Chengqi Zhang. Task sensitive feature exploration and learning for multitask graph classification. IEEE transactions cybernetics, 47 (3):744-758, 2016.
Michaël Perrot, Pascal Esser, and Debarghya Ghoshdastidar. Near-optimal comparison based clus- tering. In Advances in Neural Information Processing Systems, pp. 19388-15 19399, 2020.
Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing. 27(7):950-99) 2009.
Benedek Rozemberezki, Oliver Kiss, and Rik Sarkar. Karate club: An api oriented open-source python framework for unsupervised learning graphs. In Proceedings of the 29th ACM Inter- national Conference on Information & Knowledge Management, pp. 3125-3132, 2020.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9): 2539,2561, 201
Cornelis J Stam, BF Jones, G Nolte, Breakspear, and Ph Scheltens. Small-world networks and functional connectivity in alzheimer's disease. Cerebral cortex, 17(1):92-99, 2007.
Minh Tang. Avanti Athreya, Daniel L Sussman, Vince Lyzinski, Youngser Park, and Carey E Priebe. A semiparametrie two-sample hypothesis testing problem for random graphs. Journal of Compu- fational and Graphical Statistics, 26(2):344 3544 2017a.
Minh Tang, Avanti Athreya, Daniel L Sussman, Vince Lyzinski, and Carey E Priebe. A nonpara- metric two-sample hypothesis testing problem for random graphs. Bernoulli, 23(3):1599-166 1630, 2017b. 7b..
11

---

Published as a conference paper at ICLR 2022
Robert L Thorndike. Who belongs in the family? Psychometrika, 18(4):267-276 1953.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lchman graph kernels. In Advances in Neural Information Processing Systems, pp. 6439-6449, 2019.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416, 2007.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Bowei Yan, Purnamrita Sarkar, and Xiuyuan Cheng. Provable estimation of the number of blocks in block models. In International Conference Artificial Intelligence and Statistics, pp. 1185- 1194, 2018.
Shuicheng Yan, Dong Xu, Benyu Zhang, Hong-Jiang Zhang, Qiang Yang, and Stephen Lin. Graph embedding and extensions: general framework for dimensionality reduction. JEEE transactions paltern analysis and machine intelligence, 29(1):00-5,, 2006.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12): 2227-2242, 2008.
Yuan Zhang, Elizaveta Levina, and Zhu. Estimating network edge probabilities by neighbourhood smoothing. Biometrika, 104(4):771-783,22) 2017.
12

---

Published as a conference paper at ICLR 2022
A
PROOFS OF THEORETICAL RESULTS
We discuss the proofs of Proposition and Theorems
B with supporting lemmas in this section.
A.1 PROPOSITION
The distance function defined in 2 estimates the Li-diitance between graphons that are continuous. To prove this, we introduce method to discretize the continuous graphons in the following so that it is comparable with the transformed graphs described in the graph distance estimator (2)
Graphon discretization. We discretize the graphon by applying piece-wise constant function ap-
proximation that inspired from Chan Airoldi (2014), similar to the graph transformation. More precisely, any continuous graphon discretized to matrix W of size no no with
10
n0
2) dr dy 710
Wi
1/mo
2
Jo
w
+ no
+
(6)
We make Assumptions structure is follows:
3 to derive the concentration bound stated in Proposition ! The proof
1. We bound the point-wise deviation of graphon with its discretized correspondence using Lipschitzness assumption (Lemmma] D..
2. We derive the error bound between the Le-distance and Frobenius norm of the discretized graphons using Lemma [
(Lemma 2).
3. We establish a relation between Frobenius norm of the histograms of graphons and graphs (Lemma 3).
4. Finally, prove Proposition by combining Lemmas 2 and 3
Lemma (Lipschitz condition) For any graphon w and corresponding discretization W, define
piecewise constant function w(z, v) Wij where E [____ á. 1.1 and y E 1 . the Lipschitz continuous assumption, have
11. Using
mo no na
no no
2/2L
w w(r,y) w(x v) S
120
where L is the Lipschitz constant in Assumption 7
Proof of Lemma (Lipschitz condition). We use Assumption | lemma The following holds for a graphon w with Lipschitz constant L.
Lipschitzness to prove this
- - w(2, v) n10
j2
L
w(x
< L
(8)
7
110
"
11g
We prove Lemma
using ( and the definition of w(x, v)
We where
E
[
+
1
and
mg
ngg
no.
y E j mg.
w(x y) w(x 2)
w(x 3) w (x, y) + w(x y
+
130
w(x,y) w(x +
i y +
2 no
+
w
(x
+
i
2
+
2 w(x no
(v,
2/2L
nio
no
Lemma 2 (Error bound of discretization) For two graphons wh and u2, the error bound between the Læ-distance and the Frobenius norm of the corresponding discretized graphons W1 and W2 satisfies
1
4 n1p
[1 w2 1l.
[ W2llF
ni0
13

---

Published as a conference paper at ICLR 2022
Proof of Lemma 2 (Error bound of the approximation). Lemma | is used to prove this lemma. Let L1 and Le be the Lipschitz constants of W1 and W2.
w1 22 Il2.. = S/,, I/' (wi v) (2, dr
twi (x, v) and # (2;, y) within the square, expand and apply Lipschitzness condition from Lemmal
8
8T3
161, L2
Bo
Ro
(Wi)st (W2)aa)
n n
4v 4v2(L1 + L2)
no
no
(Wi)at (W2)ac
no
k=0
1=0
2/2(L + L2)
2 + L2)
+
2
||
W2ll +
n
I - W2ll1
110
12)
2/2(L1 L2)
1
W
Wells)
(10)
no
no
(a) : ||=/| & v |2:11
Similarly, by twn v2) and L22 (2, v) to
W
W2ll? and applying Lipschitzness condition
no
from Lemma I we get,
22/2(L) + L2)
2
|[1 Wall
+ ||01 w2 121122)
(11)
710
Combining (10) and
we prove
2v2(L1
L2)
(6)
4V2L
w1 W2 || lm
[
Wallr
(b): L = max L1, L2
120
We derive the following relation between histogram of graphs and graphons by adapting lemmas from Chan Airoldi (2014) for our problem and the error bound discretization p
Lemma 3 Let G1 w1 and G2 wa have respective graph transformations A and Az. Let W and Wz be the corresponding discretized graphons of wi and W2 respectively. As n + Do and n log + O, then for any e >> O.
n
Al A2 dellr- W1 Wa 1l S 4e
(12)
with probability converging to
Proof of Lemma 3 The proof of this lemma is inspired from Chan & Airoldi 2014). For i {1, 2). let matrix W; of size vig ng be the discretized graphon w, and let matrix A, of size no no be another transformation of graph G; based on the true permutation ã; that is, o denotes the ordering of the graph G, based on the corresponding graphon wi. In other words, the discretized graphon W; the expectation of A,. The reordered graph is denoted by G. and then A, is obtained by,
h
h
(A.)
(G)))AAkii where h = 11_ and [.] is the floor function. k
Σ
h2
no
We bound ||A, A2l1F using A,, Az. W, and We
|
A2l1F < ||A,| Âill= + || AzllF F + ||A, -zllF
22 max (1,22
||A: Â.lIF + ||Ā - ĀzlIF
2 (1,2))
||A ÂllF +2 max || WillF + [| - WellF =(1,2]
(13)
14

---

Published as a conference paper at ICLR 2022
We have the following for all using Assumption 2 on Lipschitzness of the expected degree function g(u), of graphon wy and Lemma 3 of Chan & Airoldi (2014).
E| A.lid -
no
2+ 224C LC
log
4 log 14 no
: C depends on Lipschitz constants of g
n
n4
$ 2 n
+
n
A
L
logn
n
+ n
AC
L.
logn
log n0
(14)
n²
n²
n
Applying Markov's ' inequality to bound the probability P
max [=
||A
A 1
2 2
using (4).
IA
Arl
P max ||A, [=11,
111 7
14
O
nb log n
(a)
Union bound
e
cin
(1,2)
(15)
Thus asymptotically, as n + 0o and n logn + O, for all and any 61 0. |4, - Aelle < 61 with
probability converging 1.
From Lemma 4 of Chan & Airoldi 2014)) we have the following for all i,
E A,
no
ng n
(16)
Applying Markov's inequality to bound the probability PP
max (1.2)
|| - W 2 &
using (6
A - W.ll.
16
2n e2n²
P max (1.2))
A
W.ll
22
: :(a) Union bound
(1.2)
(17)
Again asymptotically as n + xo, for all i and any > 0. |14, W,
< 62 with probability
converging to 1. Lets assume 62 = é1 = e. Substituting (15) and 117 in
||4, A2l1 - 4e + [| W2ll
(18)
ni log 0. with probability converging to 1 as and
n
The lower bound can similarly be obtained,
|| - A2llF 2 || Wallr - 2 max
1A W. - max >= ==12)
|1 - Aillr
i= (1,2)
[[ - W2ll
(19)
with probability converging to 1 as n + 0o and n log n n
+ 0.
Thus, |||A1 - Agl1= F [[ W2l1s| < 4e satisfy for any > with probability converging to n logn
as n + 00 and
+ from equations 18) and 19
n
Proof of Proposition I (Graph distance is consistent). Proposition immediately follows from Jfter a simple decomposition step as shown below.
Lemmas 2 and
3
w1 w2 ||ا,- d(G1, G2)
w1 w2 L. d(G1, G2)
I|W WellF
71
1
w2
1z2
WallF
|| W2llF Wall=-d(Gr ((,
710
ni
4 4
4e
n log n
0
holds for any e > 0 as n - xo and
- 0.0
70
n
15

---

Published as a conference paper at ICLR 2022
A.2 PROPOSITION [FOR SPARSE GRAPHS
To adapt the dense graph model, graphon, to sparse graphs, the sampling procedure is modified Geyl U, Uj Bernoulli (p (U,, (u(U,,U)) U,)) where p depends only on n. With this modification, equation 14 will be changed to
no
n n²
log A0,
log O
log n Rop
B|I|A, A11 <
n L
(20)
n
n
and the proof involves modification Lemma 2 of Chan & Airoldi (2014). We state the modified lemma and briefly sketch the proof below.
Modified Lemma 2 of Chan & Airoldi
2014). Let (i) be the oracle permutation such that (
o(j) 1
log n
Uo(1) < Uo(2) ... Uo(n)- Then, if
then
n
m
6Tap
n
log n
(d(())
docill
(21)
log 18L7 p²
with probability at least
8 exp
Conversely, if 21
holds with probability at
log m
least 1 - exx
then
18L7
p²
(1)
1
log n
1
<
+
(22)
p
3L1
3L1L2
L2
1
log n p²
with probability at least
40 exp
18L7
Changes Proof in Chan & Airoldi
(2014). Suppose
a(t)
a(1)
for 0 and 8 p.
Then, (luo() - Unii > 34 S exp
-2n
Consequently,
(1orc) Un(i) 3 - 4 exp (-2n 82
P ((9(Uo(()) 9(U 3T16) <P
p
Following their proof, have P ((do() docil 6Lg8 Un(n;Uoi5))
< 4exp 122300 4exp
5²
8² -2n
-2n
< 8 8xxp
(23)
p²
p2
when > 3L. Note that there is a small mistake in their proof when Hoeffding's inequality is applied, where factor of n² is written in place of n. Putting d
log and considering
GL.
lox since depends on n and < p, we get
p =
log n V
(- 1 logn
IP [d(i)) -do))
Uo(1), (o(1))UG())
< <8exp
188
/²
Converse can similarly be proved.
can derived by substituting the above changed lemma in their proof. Consequently, Propo- sition still holds under this formulation, with slight change to the condition as - co and
20
m log n + for p
(v llg
We will not consider sparsity for analysing consistency of
n
algorithms in the next sections.
16

---

Published as a conference paper at ICLR 2022
A.3 DISTANCE BASED SPECTRAL CLUSTERING (DSC)
We make Assumptions T on the K graphons to analyse the Algorithm 1 We establish the consis- tency of this algorithm by deriving the number of misclustered graphs M through the following steps.
1. We establish deviation bound between the estimated distance matrix H and the ideal dis- tance matrix D (Lemma 4).
2. We formulate Davis- theorem in terms of the deviation bound using the result from Mukherjee et al. (2017) (Lemma55)
3. We derive the number of misclustered graphs from Lemma
As stated previously, D in Algorithm | is an estimate of D R where define Dij ||w; Wy -ل Note that is block matrix with rank K, since Dij for all G,, G, generated from same graphon, and equals the distance between the graphons and otherwise.
We derive the deviation bound for the distance matrix using Lemma and the result is as follows.
ng ng log
Lemma 4 (Distance deviation bound) As - and
n 0, we establish
| D = 0
m
(24)
with probability converging to 1.
Proof of Lemma (Distance deviation bound). From Proposition I
and the definitions of Dey and
Dij, it is easy to see that [Di - Dig = no
with probability converging to as n + oo and
ng log n
0.
n
Using Lemmas
and
and the definitions of Dig and Dij. we have
Dis Diy
||A: A,l1r ||w; w/ llea
72
||A -A,ll A, r = 120
I|: W,ll l|w. - wyll
74p
A;
A
IW: W, + ||m mylles
I|W W,llr
nop
71
12
4c
4 2L
with prob. + asymptotically
710
no
Thus asymptotically, Dij - Dis = o (
with probability converging to 1. nio
Hence, 1 D1[r 0
m no
with probability converging to 1 as n. - co and m22nn log n
0.
variant of Davis-Kahan theorem (Mukherjee et al. 2017) and the derived deviation bound 24 are used to prove the following lemma.
Lemma 5 (Davis-Kahan theorem) Let V and V be the mxx K matrices whose columns correspond to the leading K eigenvectors of D and D, respectively. Let r be the K-th smallest eigenvalue value
of D in magnitude. As n + and n log n + O. there exists an orthogonal matrix Ô such that,
V0 v - m
(25)
yno
with probability converging to 1.
17

---

Published as a conference paper at ICLR 2022
Proof of Lemma 5 (Davis- Kahan theorem). A variant of Davis Kahan theorem from Proposition A.2 of Mukherjee al. (017)) states the following for matrix D of rank K. Let V and V be K matrices whose columns correspond the leading K eigenvectors of D and D, respectively, and y be the K-th smallest eignenvalue of D in magnitude, then there exists an orthogonal matrix Ô of size K K such that,
4 D
D
m²n log
|
as n2 - OC and
0.
ymo
π
The number of misclustered graphs is | < 8Mu IVO V VI where mr is the maximum number of graphs generated from a single graphon (Mukherjee et al., 2017). Since mr = O(m), [M]
O m
by substituting 25 in MM] Hence proving Theorem
? 2
8mT VÔ vl from
Proof of Theorem
The number of misclustered graphs |M|
Mukherjee et al. (217). Thus, we prove the theorem using Lemma
That is, as 00 and
m m²ng log O,
MM S Smr V7 v
m 7
Proof of Corollary 1 This corollary deals with special case where K = 2 and equal number of graphs are generated from the two graphons w and w'. Therefore, my in the number of misclustered graphs IM] is m/2. The ideal distance matrix D will be of size m m with 0 and |w w/ [| as entries depending on whether the samples are generated from the same graphon or not. For such a
block matrix D, the two non zero cigenvalues are + -2 ||! w' w'llz, Therefore, 7 is 2 || w lZz- 2
Corollary can be derived by substituting the derived y in the number of misclustered graphs (.M] in Theorem D as shown below.
M O
171
1
w/ 12, n0
m n log
Let us assume ||w w/ll L,, C no
where C is a large constant, then as - 0C.
0,
n
[.M] + O.
A.4 SIMILARITY BASED SEMI-DEFING PROGRAMMING (SSDP)
We make Assumptions 3 on the K graphons study the recovery of clusters from Algorithm The proof structure for cluster recovery stated in Theorem is as follows:
1. We establish deviation bound between the estimated similarity matrix and the ideal sim- ilarity matrix S (Lemma 6)
2. We derive the recoverability condition by adapting Proposition 1 of Perrot et al. 2020 and the obtained deviation bound (Lemma)
The ideal similarity matrix S E R is symmetric with K x K block structure, and S = ZΣZT where E {0, 10,1k be the clustering membership matrix and Σ E RK*K such that Enr repre- sents ideal pairwise similarity between graphs from clusters C₁ and Cy. From the definition of Sij,
||wy willle))
Ex exp
where and wi are graphons corresponding to clusters C₁ and Cy,,
respectively. S the estimated similarity matrix of S as mentioned earlier. Since X R Kx K is the
normalised clustering matrix, X = ZN- TT where N a diagonal matrix with C Cxl
We derive the deviation bound for the similarity matrices using Lemma and the result is as follows.
18

---

Published as a conference paper at ICLR 2022
n log
Lemma (Similarity deviation bound) As n - 00,
- 0, we establish
72
-
|S. Sty
(26)
n1
with probability converging 1. Hence, from the result ||S converging to 1.
S =0 m
with probability
7g
Proof of Lemma (Similarity deviation bound). We derive the bound using Lemmas and and the definitions of Siy and Siz-
|A AgllF)
Sij = exp
Consider o, = oj = σ
Ro0,o3
[W W + 4E
cxp
with probability + asymptotically
ngo²
110 - w/l Lo
4E + 4v
exp
exp
exp(-x) 2 1 2x for x > 0
o²
nyo²
8(e V2L)
2 Siy
noo²
8(c + V2L)
Sij
Sis
Sig [0,
200²
8(c + V2L)
Sij
(27)
ngo²
| - Ajlle
S1g exp
Roo²
W
W de
exp
with probability 1 asymptotically
n0o2
[w
Wj Willza 1/2
4e + 4V2L
exp
exp
exp(x) I 1 2r for
noo²
8(c + V2L)
< Sig
1+
2n0
8(E + /2L)
< Sig + Sis
Si E 10.1]
2g
8(e V2L)
I Sig +
(28)
noo²
8(E + v2L)
-0 for any e, with probability
Thus, from 27 and 28
we get [S. - S.yl
=
ng0
n1
converging to as n and n log
Sm(e + v2L)
0. Hence, ||S S1F
O
n
nno
m m2ng log 0.
with probability converging to 1 as n oo and
n
The condition for exact recovery of clusters is derived by adapting Proposition 1 of Perrot et al. 2020).. The proposition states the recoverability condition for such an SDP defined in (4) in terms of the similarity deviation bound. Thus, the derived bound in Lemma 6 and establish condition on the Li-distance to satisfy the proposition from Perrot et al. (2020). First, we state the adapted proposition.
19

---

Published as a conference paper at ICLR 2022
We define A1 and A2 as,
A
min Ew)
and
A2 max |Sij Ssyl-
171
Then, the following should be satisfied for X to be the unique optimal solution of the SDP (4
{ { A1
A
|| Si|F S min |C|] min
6A2 1h--622
The minimum cluster size min [C]] our case 1. Consequently, the recoverability condition is derived and as follows.
m2n log 0, the min
Lemma (Recoverability clusters) As + 00, be that X is the unique optimal solution of the SDP
17l ||lI
w/ I1, should
n
nip
Proof of Lemma 7 (Recoverability of clusters). We derive the condition satisfy the stated proposition.
A max Eg and A₂ min 18 Styl- The minimum cluster size in our be 1.
1/
The analyses of the two cases of the Proposition is follows.
Case 1. Let us assume A
then min
A A - 6A2} will be A 2.
Therefore,
12
8mn(E
2LL
1
|w wr Lea
max exp
100
2
2 (pl'
o²
wy L2
16m(c + V2L
exp
min 19ft
<
noo2
|/w
wr
16m(c + V2L)
min (gl
log
ngo
16m(e + v2L)
min ||wy
wi
11
2 2
ago2
k=1
m
min [wj wy |11,, Ω
(29)
710
A
Case 2. Let assume A2
then min
( A,
6D2}
will be A, -64g. Therefore,
12"
8m(e + V2L)
|mm wp 11ke
6 8(c + V2L)
< 1
max exp 181
with probability aymptotically
no00
0² 8(m + 6)( + V2L)
agg2
min
-lo
1
ng02
8(m + 6) V2L)
min |wy wr
2 2
2o002
K
k=
min Iuy wy 11 52
(30)
no
Thus, from 29 and 30
for the Proposition to hold. Consequently, Theorem 2 is the direct reflection of this lemma.
we must satisfy mingar ||w - wy Il2, = Ω
20

---

Published as a conference paper at ICLR 2022
A.5 GRAPH TWO-SAMPLL TESTING
Theorem of two-sample testing is proved by deriving the probability of Type-1 and Type-2 errors. We make Assumptions [ for this case. Let Wi and W2 be the no X no discretized graphons of wn and W2. respectively, obtained using (6) Then, the alternate hypothesis Ha can be rewritten using Lemma 2 in the following way,
4v2L
9
W1 W2llr
74
W1
W2llF 2 nop - 4V21 p
(31)
We derive the probability of the errors using Lemmal and is stated in the following lemmas.
Lemma 8 (Probability of Type-1 error) The probability of Type-1 error, i.e. rejecting the null hy- pothesis when it is actually true, is
C log
P(T 1|H True)
(32)
52 n
where C. depends only on the Lipschitz constants.
Proof Lemma (Probability of Type-1 error). The Type-1 error is rejecting Hg when it is
true. Therefore, in this scenario, |[ Walle 0. Thus, from Lemma 15) and 177. have
||A| A2llF 4e with C' n log probability. Therefore, the probability of Type-1 error is,
2
P(T Ho True) P(d((G1, G2) 2 2)
A1 A2l1 2 noE) C ng log n
err only when not S 4e
22ng
n
Lemma (Probability of Type-2 error) The probability of Type-2 error, i.e. accepting the null hypothesis when the alternate hypothesis is actually true, is
C1
log
P(T Ha -Tuue) S
(33)
1v2C2
n
Thp
where Ci and C2 depend only the Lipschitz constants.
Proof of Lemma when the alternate hypothesis is true. Therefore, from 31 W Wellp 2 From Lemma and 17
of Type-2 error). The Type-2 error is evaluating to null hypothesis
[5
C1
no log
|| A2l1 W1 W2llF 4e
with probability 1
22
n
p 4e
The probability of Type-2 error is.
P(T = 0. : True) = P(d(Gi, G2) < <)
P([IA1 A2llF noC)
err only when no S p 4e; let not 4e
0
< P(IIAI A2llr
2
C1 nă log
n
4/2L
P =
We get the probability by substituting
from 31) in the above equation. Theorem
7g
3 can be proved by asymptotic analysis of Lemmas and
21

---

Published as a conference paper at ICLR 2022
B DSC AND SSDP ALGORITHMS
The proposed algorithms DSC and SSDP described follows:
Algorithm 1: Distance based Spectral Clus- tering (DSC)
Algorithm 2: Similarity based Spectral Clus- tering (SSDP)
input : Adjacency matrices ..., Gms
input Adjacency matrices GI, Gm histogram size
histogram size
output: K clusters Ci,... CK
output: K clusters CI,..., Ck
Construct distance matrix Compute D E Im where Dij = d(G,, Gÿ)
Construct similarity matrix Compute 3 E R where Sig - exp
d(Gr,G,)
0:03
with 01 Clustering Find X using 4 and apply standard spectral clustering to X resulting in C1...., J.....CK.
Clustering Apply spectral clustering to D with K number of clusters resulting in Ci.... CK
C EXPERIMENTAL DETAILS
In this section, present experimental details and additional experiments.
C.I SIMULATED DATA HEATMAP GRAPHONS
Figure shows the heatmap of the considered four graphons W1, W2, W3 and Wa. We sample graphs from these graphons for the experiments.
W)(uvv)
W2(u,v)
Ws(u, v)
W4
Figure 4: Heatmaps of graphons W1, W2, W3 and W4.
C.2 CHOICE OF
We validate the theoretically deduced bound for no Ol log n)) by sampling 5 graphs with a fixed number nodes n from each of the four graphons. in total 20 graphs, and measuring the performance of DSC and SSDP for different no (5, 10, 15, 20, 25. 30). We perform three simu- lations with n = (50, 100, 500} and fix neighbourhood of one SSDP. Figure shows the average error of both the algorithms over 5 independent trials. Based on the theoretical considerations for vi (& /n/ log ri), evaluate no (5, 15) for {50, 100, 500). respectively. The experi- mental results show that the derived bound for van serves as reasonable choice (if not the best) for both DSC and SSDP irrespective of Hence, the choice of no can be deterministic and adaptive with respect to thus making our algorithms parameter-free.
C.3 EXPERIMENTAL RESULTS USING ADJUSTED RAND INDEX (ARI)
In this section, provide the results for evaluation of algorithms simulated and real data under the same setting as described Section 3.3 Figure 6 shows the evaluation of all the discussed algorithms using ARI, where the observations made from error rate hold.
22

---

Published as a conference paper at ICLR 2022
n==5
n= 50
n ==100
15
= 500
0.4
Error rate
DSC (ours)
SSDP (ours)
0.2
0.0
5
10
15 20 25 30
5 10
15 20
25
30
5 10 15
20
25
30
Histogram size no
Histogram size no
Histogram size no
Figure 5: Validation of the bound for ng- The plot shows the average error rate (percentage of misclustered graphs) of the proposed algorithms DSC and SSDP for different (50, 100, 500).
0.2
0.0
DSC (ours)
Ws.
Wa. Wy.
Wi. Ws.
Wa. W2. W4
Ws. Wg. Wy.
SSDP (ours)
1.0
NCLM
0.8
NCMMD
0.6
WWLGK
GNTK
NCGMM
TLE Time Limit Exceeded
Bg. By. Bg
Bs. Ba
8,.
82.05.64
B1. Bs,4
1.0
0.8
ABU
0.6
0.4
0.2
0.0
52
S4
Sy,
Sy,
Figure 6: Evaluation of DSC and SSDP with other methods. (row 1) Results on simulated data using ARI. (rows and 3) Results on real data from Bioinformatics and Social Networks, respectively.
C.4 EVALUATION ON LARGE SIMULATED DATA
As mentioned in Section 3.3 we evaluate algorithms except GNTK and NCGMM on large graphs sampled from the four graphons Wi, W2, W3 and W4 with nodes between 100 and 1000. Figure shows the results measured using average eттоr rate and average ARI, respectively. The proposed algorithm DSC outperforms the others all the case and SSDP stands second third best, as observed in simulated data with small graphs.
0.6
Eiror rate
0.4
0.5
0.2
0.0
0.0
W.
W.
Ws. W., W.
W. W., We
W.. W., Wa Wi, W.,
Wy. W.
W,. We. We
W., W.
We W. Wy.
DSC (ours)
SSDP (ours)
NCLM
NCMMD
WWLGK
Figure 7: Evaluation of all algorithms except GNTK and NCGMM using average error rate and average ARI for large simulated data.
23

---

Published as a conference paper at ICLR 2022
C.5 COMPUTATION TIME OF ALGORITHMS
Table shows the time (measured in seconds) taken for the algorithms on the considered dataset combinations. Three clusters also show similar behavior to four clusters.
Table 1: Time measured in seconds for algorithms on different datasets combinations
Dataset
DSC
SSDP
NCLM
NCMMD
WWLGK
GNTK
NCGMP
W1, 22 W3
0.13
0.22
0.17
11.66
0.66
225.46
15.43
W2, W3, W4
0.14
0.23
0.18
12.98
0.70
199.98
16.27
W1, Ws, W4
0.13
0.25
0.19
12.93
0.71
200.85
16.98
W1. W2. W1
0.13
0.24
0.18
12.55
0.68
198.38
16.54
W1, W2, W3, W4
0.20
0.38
0.28
22.05
1.19
390.07
30.18
B1, B,, B3
1.10
1.25
0.17
20.72
2.54
28.21
219.58
B1, B3, B4
0.99
1.18
0.16
21.51
2.85
32.22
225.02
B1, B2, Ba
1.01
1.08
0.14
15.61
1.92
19.49
174.25
B2, B3, B4
1.04
1.13
0.13
11.99
0.78
13.38
21.47
B1, B3, B4
1.33
1.46
0.183
28.66
3.19
40.18
278.80
S1,
1.50
1.65
8.21
1125.71
454.19
1609.78
TLE
S2,
1.25
1.34
0.36
77.67
15.32
294.53
TLE
S4,
1.52
1.64
8.07
1001.52
348.25
1485.90
TLE
S2, Sa,
1.48
1.69
8.88
1035.98
440.87
1757.06
TLE
S2, S3, S4
1.97
2.22
9.47
1069.28
437.21
2060.68
TLE
C.6 SCALABILITY EXPERIMENT
We evaluate the scalability of the considered algorithms using simulated data by measuring the time taken for clustering 40 random graphs, 10 sampled from each of the graphons Wi, W2, Wa and Wy. We did 7 experiments in which the size of the sampled graphs where max_size = {100, 200, 300, 400, 500, 600, 700}. Figure g shows the experimental results which illustrates high scalability DSC. SSDP and NCLM over other algorithms. Note that the experiment shows NCLM as scalable as DSC and SSDP since the sampled graphs are small.
varied as (50, max_size]
(ours)
SSDP (ours)
NCMMD
GNTK
Time Limit Exceaded
TLE
100
20.0
300
400
500
600
700
Max graph size
Figure 8: Computation time of algorithms different sets of simulated data for four clusters demonstrating the scalability of each algorithm. Computation time is plotted in log scale.
C.7 TWO-SAMPLE TESTING
In this section, we evaluate the efficacy of the proposed test T' with different d(G G2) by varying the graph sizes n. We consider n (50, 100, 150} and fix my 10 from the theoretical bound for evaluating the test T. The power is computed using the test T for the significance level 0.05, and the plots in Figure 9 show the average power computed over 500 trials bootstrapping 100 samples generated from all pairs of graphons for d(G1, G2) our proposed distance, log moments
24

---

Published as a conference paper at ICLR 2022
graph sizes (50, 100)
graph sizes (100, 200)
graph sizes (150, 300)
Praposed Distance
0.07
1.00
1.00
1.00
W1
0.06
1.00
1.00
1.00
0.04
1.00
1.00
1.00
W2
1.00
0.06
0.39
1.00
W2
1.00
0.06
0.97
1.00
W2
1.00
0.08
1.00
1.00
1.00
0.39
0.05
0.91
W3
1.00
0.97
0.03
1.00
1.00
1.00
0.05
1.00
1.00
1.00
0.91
0.17
1.00
1.00
1.00
0.13
1.00
1.00
1.00
0.13
W1
W2
W3
0.02
0.85
0.69
0.03
W1
0.04
0.99
0.90
0.05
0.05
1.00
0.99
0.05
Log Moments
W2
0.85
0.04
0.12
1.00
W2
0.99
0.26
1.00
W2
1.00
0.03
0.46
1.00
W/
0.69
0.12
0.04
0.96
Wa
0.90
0.26
0.05
1.00
W3
0.99
0.46
0.04
1.00
0.03
1.00
0.96
0.03
W4
0.05
1.00
1.00
0.03
0.05
1.00
1.00
0.04
W1
W2
W3
W1
W4
W2
W3
W4
0.52
1.00
1.00
0.93
W3 0.57
1.00
1.00
1.00
0.70
1.00
1.00
1.00
W2
1.00
0.45
0.54
0.96
W2
1.00
0.64
0.47
1.00
1.00
0.87
0.85
1.00
MMD
W/3
1.00
0.54
0.51
0.87
W3-
1.00
0.47
0.51
1.00
Wg
1.00
0.85
0.98
1.00
W4
0.93
0.96
0.87
0.61
W4
1.00
1.00
1.00
0.77
1.00
1.00
1.00
0.99
W1 W2
W3
W1
W4
W2 W3 W4
Figure 9: Illustration of two-sample testing with the proposed distance log moments and MMD on varying n in graph pairs of size (n, 2n). The plots show the average power of the test T. Test based on the proposed distance is consistent for sufficiently large graphs and efficient compared to other methods in distinguishing even closer graphons.
and MMD, respectively. From the result for graph sizes (50, 100), we observe that the graphon pair (W2, Ws) is not easily distinguishable (low Hu rejection probability). which can be explained by their respective L2 distance that is shown in the left plot of Figure 3 This issue does not arise in testing larger graphs as the result shows for graph sizes (100, 200) and (150, 300). Therefore, test T' with the proposed distance can distinguish between pairs of graphons that are quite close provided that the observed graphs are sufficiently large, thus proving be consistent. On the other hand, log moments and MMD based tests show weakness in distinguishing the graphons, where log moments based test T accepts the null hypothesis in most cases different for all graph sizes. For instance, the result for graphon pair W1 and Wa is indistinguishable using log moments statistic for any graph size. On the contrary, MMD based test 7 rejects the null hypothesis almost always for larger graphs (diagonal values in all graph cases). Thus, we conclude that the proposed test 7 in 5 is consistent and this experiment illustrates the efficiency of the test T compared to other plausible test statistics.
when the graphons
Subsequently, we evaluate the efficacy of the above tests on the discussed real datasets Bioinfor- matics and Social Networks. We consider graphs from a dataset to belong to population and hence the objective of the test statistic is to distinguish graphs from different populations, that is, graphs from two different datasets. Since the populations are not known and the real graphs are treated as representatives of the population, we compute p-value of the test instead of power to measure the efficacy. The p-value is the evidence for rejecting the null hypothesis which implies that the smaller the p-value, the stronger the evidence that the null hypothesis should be rejected. Therefore, the p- value should be high (greater than the significance level) for graphs from same population and low (zx 0) for graphs from different populations. Figure I0 shows the result for both the dataset cases and different tests. From the results, it is clear that the log moments and MMD based tests poor
25

---

Published as a conference paper at ICLR 2022
Proposed Distance
Log Moments
MMD
1.00
81
81
B1
Bioinformatic
0.75
82
82
82
0.50
83
83
83
0.25
B4
B4
Ba
B1
82
8g
B4
B1
B2
83
B4
B1
B2
B3
B4
1.00
5
S1
5
Social Networks
0.75
52
52
52
0.50
53
0.25
54
54
54
51
52
53
S4
51
S2
5g
51
52
53
Sa
Figure 10: Illustration of two-sample testing with the proposed distance vs log moments and MMD on real datasets Bioinformatics and Social Networks. The plots show the p-value of the test T. Test based on the proposed distance better than the other two tests.
and inefficient on real datasets as log moments based test has high acceptance of null hypothesis for almost all the pair graphs from any population and MMD based test rejects the null hypothesis always except when the graphs are the same. Whereas, the test using our proposed distance perform well on large graphs from Social Networks datasets, for instance, Sa with other datasets and within itself. This test performs well even for small graphs when compared to the other two tests.
26


Reviews:
[{"review_id": "ob5KUjYiZvX", "reviewer": "Reviewer_1avZ", "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": "__Strengths__:\n\nThe paper is easy to read and follow, well-grounded, and theoretically sound in most of its parts. \nThe authors also try to give intuition about the choices they made.\nThe developed method is applicable and effective to small samples of graphs and it appears novel to me.\n\n__Weaknesses__:\n1. The authors claim there are no studies beyond network classification and a lack of theoretical support for the available methods. In my opinion, the claim is not correct. Many papers include different graph-level tasks in their experiments and several of them provide also theoretical support about the proposed architecture; I can refer the authors to some of them below. The authors also claim \"the efficacy of these methods [on graph matching] in learning from network-valued data remains unexplored\". The authors should be more precise about what remains unexplored. Nevertheless, I may agree that extra studies and theoretical analyses can positively contribute to the research in this field, and I recognize the value of considering the small sample size setting.\n    * https://ogb.stanford.edu/\n    * Dwivedi, Vijay Prakash, et al. 2020. Benchmarking graph neural networks\n    * Bouritsas, Giorgos, et al. 2020. Improving graph neural network expressivity via subgraph isomorphism counting.\n    * Zambon, D., Alippi, C., & Livi, L. 2020. Graph Random Neural Features for Distance-Preserving Graph Representations.\n    * Sato, Ryoma. 2020. A survey on the expressive power of graph neural networks. \n    * Maron, Haggai, Heli Ben-Hamu, and Yaron Lipman. 2019. Open problems: Approximation power of invariant graph networks.\n    * Loukas, Andreas. 2019. What graph neural networks cannot learn: depth vs width.\n    * Kriege, Nils M., et al. 2018. A Property Testing Framework for the Theoretical Expressivity of Graph Kernels.\n    * Chen, Hao, and Jerome H. Friedman. 2017. A new graph-based two-sample test for multivariate and object data.\n2. The graph transformation of G to G^\\sigma seems to be ill-defined. Although the graphon can have unique node degrees, graphs sampled from it can result in nodes with the same degree, so 1) there might not exist a monotonically _increasing_ permutation but only _non-decreasing_, and 2) the permutation is not unique, in general. \n3. The claim \"NCLM is the only known clustering strategy for graphs of different sizes\" is incorrect. Basically, any kernel-based and distance-based clustering method that does not require explicit vector embeddings can be applied to graphs. It is customary to choose the most appropriate distance or kernel that better fits the problem at hand; a simple example is k-means. The claims seem unjustified to me also because, as far as I can tell, NCLM constructs vector representations of graphs.\n4. The methods chosen for the comparison can give only limited insights. The considered methods appear to be more or less arbitrarily chosen combinations of graph functions with clustering methods. For example, this approach does not allow us to understand whether it is the proposed distance or the considering clustering method that brings the most advantages. I might be wrong, but it seems to me that there is no limitation in performing experiments with the proposed graphon-based distance with other clustering methods, and the considered clustering methods with other distances/kernels.\n5. Regarding the two-sample hypothesis test, it is unclear how a critical region of a given significance level can be constructed without having knowledge about the underlying graphons. From what I see, in the paper, the critical region is computed by sampling from the original graphons. I would to have some clarifications in this respect.\n\n\nQuestions and unclear parts:\n- The sorting-and-smoothing estimator is mentioned even in the abstract, but never introduced in the paper. Why is it the only one that can meet the above requirements? Moreover, the above requirements (I guess the authors refer to Assumptions 1-3) are about the graphons, not their estimators.\n- Theorem 1. It is counterintuitive for me that for a bounded number of nodes, the more graphs we have, the larger the _rate_ of erroneous clustered graph increases. I would expect that for m -> infinity, the rate of misclustered graphs converges to the optimal value (which is not necessarily zero), and the variance of such observed rate decreases. Could you comment on that? \n- It is not clear to me to what extent the discussed clustering methods had to be adapted to work with the proposed distance. It is also unclear whether or not these clustering methods would be consistent regardless of the specific graph distance, provided that the graph distance is sufficiently expressive (eg, it is metric).\n- Because the considered method is based on edge histograms, I wonder if there are known limitations or important differences when considering sparse graphs instead of denser ones. Are there different best practices to operate in the two regimes? \n\n__Other comments and suggestions__:\n- Say explicitly that graphs are symmetric and without node or edge attributes (if this is the case).\n- Expand the comment about indistinguishable inhomogeneous random graph models. What is the argument to show that although different, they are indistinguishable? What are we losing by ignoring such graphs, in what cases are we interested in considering also them?\n- Prop 1. Please, expand the discussion about the variable n which seems to be undefined.\n- Cor 1. Shouldn't it be: given m, n_0 and |w-w'|, we need to find a _small_ enough constant C?\n", "summary_of_the_paper": "The paper proposes a graph distance based on graphons that can operate on the small sample size regime; this is possible by exploiting a large number of nodes.\nThe proposed paper is meant to address two shortcomings that the authors have found in the literature: \n- a lack of study of current graph processing methods beyond graph-level classification, and \n- a lack of theoretically sound methods.  \n\nThe paper also shows theoretical guarantees associated with two existing clustering methods and a two-sample statistical tests when operating with the proposed distance.\n\n", "summary_of_the_review": "Overall the paper is well written. The proposed solutions are novel to me and address an extremely challenging problem related to the small sample size regime. However, a few negative aspects are present: there seem to be incorrect claims, the graph transformation appears not well-defined, and the experimental setup does not bring decisive conclusions.\nGiven the points raised in the main review section and unless it turns out I misunderstood those parts of the paper, I am afraid to say that the paper is ready for publication in its current state. However, I encourage the authors to carry on the research in this direction, because it appears promising and only few (yet, important) aspects need to be improved.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "iMAE3vHuZR3", "reviewer": "Reviewer_QUvS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "\nThe paper is very interesting, well written and understandable.\n\nThe proposed heory only works when graphs are sampled from graphons and the vertices are kept in the same order.  On the one hand, I understand that anything involving graph isomrophisms (and hence vertex permutations) will be untractable.  On the other hand, in practical applications we don't know the order of the vertices, hence there is a lot of work on graph isomorphism, graphon cut norms, and other tools to deal with that issue.  Assuming instead 'ordered' graph sampling with L2 graphon norms is interesting from a theory point of view but is quite far from practical applications where clustering and testing becomes relevant.\n\nThe experimental section could devote more attention to the runtime of the algorithms and experiments.\n\nNevertheless, the paper has some original ideas which could form a first step into more mature results.\n\n\nSome details:\n* Assumption 2: I dislike the term \"degree distribution\" in this context.  Usually, \"degree distribution\" is used for a probability distribution f which gives for a input degree d the probability f(d) that a randomly selected vertex has degree d.\n\n* In Equation (1), it seems the index i of A_{i,j} starts from 0 until n_0-1 rather than from 1 to n_0 as usual.  Alos, vertices with index larger than n_0*\\lfloor n/n_0 \\rfloor aren't taken into account.\n\nat some places articles are missing, e.g.,\n* page 5 first line: Davis-Kuhan theorem -> the Davis-Kuhan theorem\n* Sec 3.2 second line: Gaussian kernel -> the Gaussian kernel\n\n\n\n", "summary_of_the_paper": "\nThis paper presents an interesting approach to clustering of graphs sampled from graphons.  The papers presents a number of guarantees for the quality of obtained clusterings and a few preliminary experiments.\n", "summary_of_the_review": "\n\nThe paper is interesting and sound, while the result on itself is not yet very practical it could form a good first step.\n\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "V9kozqf1arM", "reviewer": "Reviewer_fKkm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths:\n- Deals with the issue of vertex correspondence for clustering of a population of graphs. A large proportion of existing methods developed for clustering assume vertex matched collection of graphs. Thus the idea is to first employ graph matching algorithms and subsequently use these techniques. As a consequence, these existing works do not provide clarity on the actual performance of clustering methods which may vary depending on the choice of graph matching algorithm used in the first step. This paper studied the clustering problem exactly as encountered in practice.\n\n- Theoretical guarantees are provided for the proposed clustering algorithms and testing framework\n\nWeaknesses:\n- The Bernoulli exchangeable model for graph only allows dense graphs (as the probability of edges does not depend on the number of nodes n). Most real world networks are sparse and thus I find this model restrictive. \n- Assumption of strict degree monotonicity is a restrictive one which is not satisfied in many real data examples. It appears that other existing histogram methods for graphon estimation such as by Airoldi, Costa and Chan, 2013 or Olhede and Wolfe, 2014 might be better suited for the clustering task given this practical concern. \n- Number of clusters K is assumed to be known for the numerical experiments whereas in practice this must be suitably determined from the data itself\n-Simulation study does not report performance for the case of sparse networks\n- Not clear how robust the techniques are to the assumption on strict monotonicity of the degree not being satisfied and to the choice of metric used to define the graph distance\n- A discussion on the consequences of Assumptions 2 and 3 specifically wrt clustering (the main objective of the paper) would have been helpful \n\nOther minor comments:\n- From reading the introduction it was not clear what 'clustering' meant exactly : in general for a  population of graphs, it could mean clustering of nodes in each graph or clustering across graphs or both. \n .- What sort of graphs are considered? Directed/self-loops? Not mentioned in the paper. \n- What exactly is Assumption 3? Is it assuming that each w_i is an element of an equivalence class unrelated to the equivalence class of w_j? How is the equivalence class defined?", "summary_of_the_paper": "Motivated by the sort-and-smooth graphon estimator of Chan and Airoldi, 2014, this paper proposes two new clustering algorithms (graph distance based spectral clustering and similarity based semidefinite programming) for multiple graphs observed without vertex correspondence. The idea is to use the graphon approximation method to obtain a histogram estimator with the same number of bins for each graph and subsequently apply an existing spectral clustering approach on the graphon based distance matrix.\nTheoretical properties of their approach are studied (under reasonable smoothness assumptions on the generating process i.e. graphon) and consistency is established. The graph distance metric is applied to test for similarity of two collections of graphs. \n", "summary_of_the_review": "Overall, the proposed idea combines existing approaches on graphon estimation and spectral clustering to lead to the proposed clustering and testing approach. It is a neat idea and comes with theoretical guarantees, however, I find the setting of dense networks and the strict assumptions on degree sequence as required for graphon estimation, restrictive. The performance of the clustering algorithms and the testing approach when these assumptions fail and when the number of clusters is unknown, is not clear from the paper. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new method for clustering multiple graphs, without vertex correspondence, by combing existing approaches on graphon estimation and spectral clustering. All reviewers agree that this is a neat paper with new theoretical and empirical results. The main concerns were also properly addressed during rebutal. Overall, it is a good paper.
Decision: Accept (Poster)