Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
Authors: Jicong Fan
Venue: ICML 2025 poster (2025)
Keywords: clustering; graphs; metric learning
Primary area: general_machine_learning->clustering
TL;DR: The paper proposed new methods of comparing and clustering graphs.

Abstract: Measuring the distance or similarity between graphs is the foundation of many graph analysis tasks, such as graph classification and clustering, but remains a challenge on large datasets. In this work, we treat the adjacency matrices of two graphs as two kernel matrices given by some unknown indefinite kernel function performed on two discrete distributions and define the distance between the two distributions as a measure, called MMFD, of the dissimilarity between two graphs. We show that MMFD is a pseudo-metric. Although the initial definition of MMFD seems complex, we show that it has a closed-form solution with extremely simple computation. To further improve the efficiency of large-scale clustering, we propose an MMFD-KM with linear space and time complexity with respect to the number of graphs. We also provide a generalization of MMFD, called MFD, which is more effective in exploiting the information of factors of adjacency matrices. The experiments on simulated graphs intuitively show that our methods are effective in comparing graphs. The experiments on real-world datasets demonstrate that, compared to the competitors, our methods have much better clustering performance in terms of three evaluation metrics and time cost.

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
Jicong Fan
Abstract
2006), social networks (Aggarwal, 2011), user-item inter- action networks (Resnick & Varian, 1997), transportation networks (Bell & lida, 1997), knowledge graphs (Hogan et al., 2021), and vision graphs (Riesen & Bunke, 2008). In graph data analysis, quantifying the similarity or dissim- ilarity between graphs (or comparing graphs for short) is probably the most fundamental and important problem and has numerous applications such graph search, classifi- cation, and clustering. However, due to the non-Euclidean nature of graph data, comparing graphs remains a challenge especially when the graphs are large, though many tech- niques have been proposed the past decades.
Measuring the distance or similarity between graphs is the foundation of many graph analy- sis tasks, such as graph classification and clus- tering, but remains a challenge on large datasets. In this work, we treat the adjacency matrices of two graphs as two kernel matrices given by some unknown indefinite kernel function performed on two discrete distributions and define the dis- tance hetween the two distributions as a measure, called MMFD, of the dissimilarity between two graphs. We show that MMFD is pseudo-metric. Although the initial definition of MMFD seems complex, we show that it has closed-form so- lution with extremely simple computation. To further improve the efficiency of large-scale clus- tering, we propose an MMFD-KM with linear space and time complexity with respect to the number of graphs. We also provide general- ization of MMFD, called MFD, which is more effective in exploiting the information of factors of adjacency matrices. The experiments on sim- ulated graphs intuitively show that our methods are effective in comparing graphs. The exper- iments on real-world datasets demonstrate that, compared to the competitors, our methods have much better clustering performance in terms of three evaluation metrics and time cost.
Numerous methods for comparing graphs are founded on the principles of graph isomorphism (Kobler et al., 2012) and its related concepts, including subgraph isomorphism and the identification of the largest common subgraph. Although the concept of examining graph isomorphism seems inherently straightforward, no efficient algorithms have been devel- oped for this task. Moreover, graph isomorphism- similarity measures and their derivatives require graphs to be precisely identical to encompass substantial identical subgraphs to be considered similar, which is overly stringent (Shervashidze et al., 201 1). As a result, many researchers attempted to develop more flexible measures of similarity. Representative examples of these more flexible measures in- clude graph edit distance (Bunke, 1997; Neuhaus & Bunke, 2007: Abu-Aisheh et al., 2015; Chang et al., 2022), chemi- cal distance (Jochum al., 1980; Bento & Ioannidis, 2018), 8), various graph kernels (Gärtner et al., 2003; Vishwanathan et al., 2010; Shervashidze et al., 2011; Nikolentzos et al., 2021), and Gromov- Wasoovrtessrr distance (Mémoli, 201 1).
1. Introduction
graph a collection of nodes (or vertices) connected by edges (or links). This structure is used represent complex relationships and interactions between objects or entities. Common examples of graphs include chemical molecules (Rong et al., 2020), biology networks (Agarwal,
Graph edit distance (GED) is calculated by finding the min- imum cost of a sequence of edit operations (e.g.. node and edge insertion/deletion)) that can transform one graph into another. While the computation of GED is NP-hard (Zeng et al., 2009), there are several approximation algorithms (Neuhaus & Bunke, 2007: Riesen & Bunke, 2009; Serratosa, 2014; 2015; Santacruz & Serratosa, 2020). For instance, Riesen & Bunke (2009) proposed a Bipartite algorithm that considers only local edge structure during the optimization process to address the high computational complexity of exact GED computation, meaning that the obtained distance
'School of Data Science, The Chinese University of Hong Kong, Shenzhen, China. Correspondence to: Jicong Fan <fanji- cong @un@@cuk.edu..c...
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
tends be larger than the exact one. Most of these algo- rithms have cubic computational cost with respect to the number of nodes (Serratosa, 2015). Moreover, one major limitation of GED is that it is not effective in comparing graphs with highly diverse sizes. For instance, given two complete graphs with very different numbers of nodes, the GED is very large, although the two graphs have similar topological patterns or practical functions.
two graphs can be compared by first representing them as vectors using unsupervised learning and then calculating the similarity between the two vectors. There have been few unsupervised graph representation learning (UGRL) methods that are based on graph neural networks (Kipf & Welling, 2017; Gilmer et al., 2017; Wu et al., 2024; Wang & Fan, 2024). Many of these methods (Sun et al., 2020; You et al., 2020; 2021; Shen et al., 2023) are based on the Info- Max principle (Linsker, 1988; Hjelm et al., 2019), where the mutual information between the graph-level representation and the representations of substructures of different scales (c.g., nodes and edges) are maximized to learn the neural network parameters. There are also UGRL methods based on other principles such as the Lovász principle proposed by (Sun et al., 2023). More methods of UGRL and more discussion can be found in (Sun et al., 2023). It is worth noting that there have been several end-to-end methods of clustering graphs (Ju et al., 2023; Cai et al., 2024), which also belong to UGRL, but can provide more discriminative representations. While graph kemels often rely on hand- crafted features and have quadratic complexity with respect to the number of graphs N, UGRL methods can learn more flexible features of graphs and have a linear complexity with respect to N. Nevertheless, UGRL methods often have more hyperparameters (e.g., network size, learning rate, weights of terms in the loss function) to tune, which is never easy in practice. Moreover, they are still time-consuming in handling large graphs
Graph kernels are kernel functions that compute an inner product on graphs (Gärtner et al., 2003; Shervashidze et al., 2011; Mémoli, 2011; Bento & Ioannidis, 2018; Sun & Fan, 2024). Many graph kernels are based on the decomposi- tion of graphs into a set of subgraphs or patterns, such as walks, paths, and trees, on which the similarity is measured. Examples of this kind of kernel include the shortest-palts kernel (Borgwardt& & Kriegel, 2005), graphlet kernel (Sher- vashidze et al., 2009), random walk kernel (Vishwanathan et al., 2010), etc. Other types of graph kernels include the neighborhood hash kernel (Hido & Kashima, 2009), Weisfeiler-Lehmal (WL) kernel family (Shervashidze et al., 2011), 1), multiscale Laplacian kernel (Kondor Pan, 2016), Lovász kernel (Johansson et al., 2014), etc. Particularly, the WL kernel and its extensions (Kriege al., 2016) are based on the Weisfeiler-Lehman test of isomorphism (We- isfeiler& & Leman, 1968), making them very effective in comparing graphs. While most graph kernels on two graphs have at least cubic time complexity with respect to the num- ber of nodes n (Nikolentzos et al., 2021), the WL subtree kernel can be computed in time (hl) (Shervashidze et al., 2011), where h is the subtree height and / is the number of edges of the graphs.
In this work, to effectively compare graphs and cluster graphs, we propose a novel distance measure, called min- imum mean factorization distance (MMFD), and several extensions. The main idea behind MMFD is that the ad- jacency matrices of two graphs can be regarded as kernel matrices obtained by performing some unknown kernel func- tion on two discrete distributions. Then, comparing the two distributions is proxy for comparing the two graphs. Our contribution is summarized as follows.
Recently, the Gromov- Wasserstein distance (GWD) (Mémoli, 2011) has shown promising performance in com- paring graphs and the follow-up graph learning problems (Vayer et al., 2020; Xu et al., 2019; 2022). GWD is an extension of the Wasserstein distance (Villani et al., 2009; Cuturi & Doucet, 2014), which is used to compare probabil- ity distributions hand, allows for the comparison of probability distributions defined on different metric spaces. The time complexity of GWD is O(n)) or (n²)) (Peyré et al., 2016), which pro- hibits its applications to large graphs. Several attempts have been made to improve the scalability of GWD. For instance, Vayer et al. (2019) proposed sliced GW, with a complexity of On log n). However, the sliced GW has limited applica- tions because a feature representation is needed to allow the ID projection. Kerdonculf et al. (2021) proposed a sampled GW that uses the current estimate of the transport plan to guide the sampling of cost matrices, leading to a complex- ity of O(n²). However, the sampled GW may suffer from accuracy degradation and inefficiency in real problems.
given metric space. GWD, on the other
We present a novel distance measure MMFD between graphs, from the perspective of comparing distribu- tions. We show that MMFD is a pseudo-metric and analyze its robustness to perturbations.
We provide low-rank approximation for MMFD and analyze the error bound theoretically. The low-rank
MMFD is more efficient than MMFD.
Based on MMFD, we develop a fast clustering method for datasets composed of a large number of graphs.
We generalize MMFD to MFD, which is more effective in exploiting the information of adjacency matrices. Based on MFD, we present an efficient clustering algo- rithm for large datasets of graphs.
Table shows the time complexities of two of our methods and some representative methods of comparing graphs. Our methods are very efficient, especially for a set of graphs.
Besides the aforementioned direct comparison methods,
2

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
Notably, besides the merit of efficiency, as shown in Section 3, our methods have much higher clustering accuracy in comparison to many strong competitors.
feature map induced by the PSD kemnel l: as d R R-M, where M > m. Then we have the following factorization (though not unique)
A $
+
(3)
2. Methodology
2.1. Motivation
where 4. = ((z)) [0 ).... o ]J. = 2, How- ever, graphs with PSD adjacency matrices are rare in real applications, meaning that the factorization (3) often does not exist. To address the challenge, we need to generate some reasonable &, using A., 1, 2, that can preserve the major information of A₃ and A2, or in other words, find PSD proxies for A₁ and A2.
Let Gi = (Vi, and G2 = (V2, Eb) be two undirected graphs in some space G, where V, and E, with = or denote the node set and edge set respectively. We aim to provide function
dist: x G
TR
In this work, we propose to use
to quantify the distance between G1 and G2. We denote the self- self-looped adjacency matrices (possibly weighted) of G1 and G2 as A E IK" xni and A2 E 1== respectivly.
Σ
nly
OT IV
i 1,2,
(4)
Since the entries in an adjacency matrix quantify the affinity or similarity between data points or objects, it is reasonable to assume that 1 and A2 are generated by some kernel function k on two sets of data points denoted as matrices Zi E p and Z2 E R respectively, i.c.,
where X, and v are the j-th eigenvalue and eigenvector of A; (Luss & d' Aspremont, 2007), i = 1. The moti- vation behind this is that we can decompose an indefinite kernel (Ong et al., 2004) as
Jur k(zz.)) 2!),, i =,,2,
(L)
Mz,z') = k- (2, - - (2,z')
(5)
where 2 denotes the u-th column of Z, For instance, in social network i with subjects, if subjects and are very similar to each other in terms of their attributes (denoted as zi and zz ), they are probably connected by an edge. The whole social network is based on matrix Z, of subjects' at- tributes. Z₁ and Ze can be regarded as two discrete distribu- tions or two samples drawn from two unknown continuous distributions, respectively. Note that does not necessar- ily satisfy Mercer's condition (Ong et al., 2004; Hofmann al., 2008) since Ai and A2 could be indefinite matri- ces. Here are some examples of k: kn ( (Zu, 2 = (z. 2.
where both A+ and k are positive semi-definite. Denoting their feature maps as ot and &J respectively, we have
A, $ $ Φ D i 1,2 Thus in (4), we have A + p. where c; [ | ; the row-direction concatenation of D and o;- Note that (4) is equivalent to A = U.S.U,, where U, and S, are the left (or right) singular vectors and singular values of A, respectively.
2.3. Basic MMFD
c)² (a 2n) = exp(- (000-7|lz, 12, Z. 112)) kg kz(Zu, 2n) tanh(z,, z. - 1). (z.. )., 1 ( (Zu. z,,) > T). Partic- ularly, K3 and K4 (with appropriate T) are indefinite kernels, and 1 can produce binary adjacency matrices.
Recall that in (2), we want to define an fZ, Z2) to com- pare Z₁ and Zz. However, both Z, and Zg are unknown. Instead, know o 4 and b. 42. where 4 and d are discrete distributions, given by
To quantify the distance between G1 and G2, we propose to calculate the distance between Z₁ and Ze and let
A + Φ,, i= 1,2.
(6)
Therefore, we propose to compare their mean vectors, i.c.,
dist(G1, G2) = fZ, Zz)
(2)
where f RMXR: x Rm + RR. denotes a function to cal- culate the distance between two discrete distributions. Obvi- ously, when Z, and Ze are identical (or up to permutation), G1 and G2 are isomorphic, where dist G1, G2) = O. See the experiments in Appendix C.I.
14 = (2 i 1
Note that when ni * n2, we can pad zero rows to the smaller one of क and T2 to ensure consistent dimension M. Suppose & can be well approximated by a q-order polynomial feature map, e.g. Ø(z) x [..., 2, 2:2j ................................ J......TT, where the coeffi- cients are omitted for convenience, then μ4; can be regarded as an estimate of moments 1 to g of the distribution. Thus,
2.2. Kernel Feature Map and PSD Matrix Construction
Suppose G1 and G2 have positive semi- demindefinite (PSD) ad- jacency matrices A and A₂ respectively, and denote the
3

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
G1. G2
G1. G2....,,Grr GN
Shortest path kernel (Borgwardt & Kriegel, 2005)
O(n*)
O(N'n*
Random walk kernel (Vishwanathan et al., 2010)
O
O(N2n²
Weisfeiler-Lehmen subtree kernel (Shervashidze et al., 2011)
(hl)
O + N2
Graph Edit Distance (Serratosa, 2014)
O(n))
((N2n)
(Entropic) Wassertesssn (Peyré al., 2016)
O(no)
O(N2n²)
Sampled
(Kerdoncuff et al., 2021)
O
O(N22²)
MMFDER
On (d) d
O(N(n² log (d) d')) +22
MMFDLR-KI KM
On log (d) + dnn)
(NN log + dn) + +NKT)
Table I: Time complexity comparison between MMFD (with d n)) and few representative graph distances similarities on two graphs set of N graphs, each with nodes. See Appendix C.4 for the rumning time comparison.
the distance between μ4 and 22 is an effective measure of the dissimilarity between Z₁ and Zz. However, the diffi- culty is that 1 and 4b are usually not in the same space since they cannot be uniquely determined by Af and A (or A₁ and A₂) respectively. This means that μ, and μ4 not comparable. More precisely, for any orthonormal letting
factorization distance between G1 and G2 is defined as
MMFD(G1, G2)
-min R
1 T1
-
1 n2
R R120
(z)
(11)
j=1
matrices R1, R2 E MMM
We provide the following theory for MMFD.
c R
i= 1,2.
Theorem 2.2 (Pseudo-metric), Let G be the set of all undirected graphs. MMFD satisfies the following axioms.
we have $ Φ Φ R R A. meaning that .. and 9 are equivalent in terms of representing AL. Further discussion about this will be provided in Section 2.5.
(a) MMFD(G1, G22 2 O. MMFD(G1, G2) MMFD(G2, G1), and MMFD(GI,
0 hold for
any G1, G2 in G;
To address the difficultyy mentioned above, we propose align- ing 4 and 4b using two projection matrices R₁ and R₂ to a common space so that we can compare the means of _ and 2, denoted as Pl and Pa respectively, where F. = -R,44, i = 1,2. The question is what R, and Ra we should choose. Given that we want to compare b, and 22 natural principle that R₁ and R2 make the distance between μ and fe small as possible. Therefore, we may solve the following problem
(b) MMFD(G G2) S MMFDD(G, G3) (age:GG)++++))) MMFD Ga) holds for any G1, G2, G3 C.
The theorem shows that MMFD is a pseudo-metric, where MMFD(G,, G2) = + G₁ = G2 cannot be thcoreti-
cally guaranteed. For instance:
Proposition 2.3. For any two complete graphs G1 and G2, whenever n 12 or nn # n2, MMFD(G1, 0.
The following thcorem shows that MMFD has a closed- form solution, which is extremely simple. Although in the motivation, definition, and optimization, we used P, Z;. 1,2, R12,, etc., they not present in the final format of MMFD.
minimize || R2 R2 R
(9)
where R denotes the set of all real orthonormal matrices
of size M x M, i.e., R- = (R& E MM R Iv). In (9), we have [R||4| - R2 = #1 R. Re It means that instead of optimizing two matrices, we can equiv- alently optimize a single matrix Ri2 := R R2, subject to that R12 R. In other words,
Theorem 2.4. Based on Definition 2.1, follows that
learn an R12 to align 2 to the space of 1 which simplifies the computation.
G2)
1 71
Σ
A
1 12
A ux
(12)
Based on (2), (9) and the corresponding analysis, letting
As a distance measure between graphs, it is important to understand the robustness of MMFD to perturbation on the adjacency matrices. Hence, we present the following result.
z(z 2
min R
||| R12/22l
(10)
we achieve the following distance between two graphs. Definition 2.1 (MMFD). Let A = Φ. Φ; and denote the j-th column of $; as ((2)) (z)))). (0)), 1,2. The minimum mean
Theorem 2.5 (Robustness). Given G1, assume n. = n2 = n and let A A2 E Ruxa be perturbations on A1, 1, A2 respectively, resulting in perturbed graphs G¹, G
4

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
respectively, where 01 (A,) s (A,) i 1,2. Then |MMFD (%) - MMFD(G),,2))
A V.S.V. we obtain the following low-rank MMFD
MMFDLR (G1, G2) 1 Ailll
Σ n//2 (5 (A1)) (A) + 55 (A2)) 1/2 where d; = minj bo (A.) - o i 1,2.
V
(14)
which can be extended to the case that n1 * 12. The
time complexity of MMFD is O( log(d)+ddng mainly caused by the randomized SVD (Halko et al., 201 1) of A, Note that MMFDLR is also a pseudo-metric. The proof is similar to that for MMFD and hence is omitted.
The theorem shows that when the graphs are perturbed slightly and the original adjacency matrices have distinct singular values, MMFD does not change significantly. This important for downstream tasks where MMFDs between graphs in the same cluster should be small.
The following theorem shows the bound of the difference between MMFD and MMFDLR-
Figure 2 shows the MMFD matrix seven small graphs. We can see the distance measures are consistent with our intuitive observation on the graphs. For instance, G2 is more similar to G3 than to G1; G7 lies between G5 and Ge: the difference between GG and G7 is less than the difference between Gş and Gg. In sum, MMFD is effective in comparing graphs. Moreover, according to Table 10 of Appendix C.6, MMFD can outperform other methods.
Theorem 2.6. Suppose n nn = n and denote a (A(A) 2 02 (2(A,) 2 ... Z on (A;) the singular values of A i 1,2. It holds that
MMMFDLe(G1, G2) MMFD(GG1,22)
Σ
(((A))+o((A)
n2/2
1=d+1
1/2
+ +2(00 (A (A1) 1/2 (Az) + //2 02)) (f
1/2
0.0914
0.1589
0,2097
0,2528
0,2505
0,2505
0.0914
0.0675
0,1182
0.1614
0.1590
0.1591
We see that when Vd+1(A,) are smaller, the bound becomes tighter. Indeed, the adjacency matrices of large graphs are often approximately low-rank, meaning that a2+1 (A;) are small. Although leading to some information loss, MMFDLR not only improves the computational efficiency but also has the effect of denoising because smaller singular values often correspond the noise in data.
0.1589
0.0675
0,0507
0.0939
0.0915
0.0916
0,2097
0.1182
0.0507
0.0432
0.0408
0.0409
0.2528
0.1614
0.0939
0,0432
0.0024
0.0023
0,2505
0.1590
0.0915
0.0408
0.0024
0.0001
0,2505
0.1591
0.0916
0.0409
0.0023
0.0001
Figure 1 compares MMFDLR of different rank with MMFD on the seven graphs introduced in Table 2. MMFDLR is more effective in distinguishing highly similar graphs.
Table 2: MMFDs between seven synthetic graphs (G1. G....., G7 from left to right). In each row of the matrix, the values of distances to the closest graph and most distant graph are highlighted in red and blue respectively.
03 04
1il rank
rank-6
1214-2
2.4. Low-Rank MMFD
Currently, the time complexity of MMFD is O(n²) with
M1 122 n assumed, mainly due to the eigenvalue de- composition (EVD) or singular value decomposition (SVD) when constructing the PSD) adjacency matrices, though it can be lowered when taking advantage of the sparsity of the adjacency matrices. For large graphs, instead of the full SVD, we perform randomized SVD (Halko et al., 2011) A and A, to obtain the following low-rank approximation
Figure 1: Visualization of MMFDLR (with different rank d) between the seven graphs in Table 2. For clearer visualiza- tion, we showed MMFD
2.5. Comparison with MMD
A U.S.V.
i= 1,2,
(13)
MMFD is closely related to the maximum mean discrep- ancy (MMD) (Gretton et al., 2012), though the latter is not related to graphs. Performing MMD on Z, and Ze using + and $2 directly, we have MMD(Z,, Zz) =
where U. V, Raxd S, E Rdxd and d is much less than n. Now for (11), we let b S. Letting
5

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
ue [4 luv + Euv [4 H $ 22), where H is an n. X n matrix consisting of ones only and we have assumed n1 = n2 = n for simplicity. We see that compared with MMFD, MMD(Z1; Zz) does not involve optimizing an R12. Essentially, in (I1), when we fix R12 an identity matrix MMFD degrades to MMD. The fundamental limi- aation of MMD(Z1 Zz) is that it makes no sense when D and 22 are not in the same space (i.e., the features in 4b and 22 are not comparable), which is always the case and explained as follows.
for exploiting node attributes, e.g., using graph neural net- works.
uv
X
x3=3
x
xx=3
X3
2
G1
G2
3
In EVD (or SVD), though well-established individual eigenvectors (or singular vectors) have arbitrary signs (Bro et al., 2008). This sign ambiguity in i and 22 makes MMD failed to quantify the dissimilarity between 4 and 22
G1
G2
Figure 2: Integration of adjacency matrix and node at- tributes. G1 and G2 are two graphs with the same adjacency matrix but different node attributes (colored), meaning that they are not equal. G1 and G2 are the integrated graphs (without node attributes) using the original adjacency ma- trices and the 1-NN graphs constructed from the nodes' attributes. Nodes 4, 5, correspond to the attributes 21, .2, Tz, respectively. G1 and G2 are different (not isomorphic).
When A; has repeated eigenvalues, eigenvectors sharing a common eigenvalue cannot be determined uniquely even if the sign ambiguity is ignored. The reason is that any set of orthogonal vectors lying in their span are also eigenvectors with that eigenvalue. This means $ and 2 cannot be compared by MMD.
Sorting eigenvectors according to eigenvalues may not be optimal in comparing the adjacency matrices, espe- cially when the adjacent eigenvalues are similar.
For convenience, we show the computation steps of MMFD and MMFDLR in Algorithm 1. As distance measure be- tween graphs, MMFD is useful in many problems, such as graph classification, clustering, and visualization. We can define a graph kernel based on MMFD as follows
2.6. MMFD with Node Attributes
In many applications, the nodes of graphs have inherent attributes, which provide additional information and should be exploited effectively. Let X; E Iixn. be the matrix of nodes' attributes of G., i 2. We may consider augment- ing MMFD or MMFDLR with MMD(X, X2). However, this neglects the correspondence between each node and its attribute vector, which can cause the inability to distin- guish between G1 and G2. To address this problem, we propose to use some technique (e.g. k-nearest neighbor) to
kGG G2) exp ( (-7 7 X MMID3(G1, G2))
(16)
where 7 0 is a hyperparameter, With this kernel, we can conduct kernel density estimation, support vector ma- chine (Cortes & Vapnik, 1995), spectral clustering (Ng et al., 2001), etc.
Algorithm Computation of MMFD between Graphs
Input: Graphs G1, G2 with self-looped adjacency matrices
construct two graphs (denoted as Gi; G2)) from X, and X₂ respectively and append G G2 to the original graphs to obtain two larger graphs G1, G2, where the node of G² is connected to the node j of G. The main idea is
AI, Aa and node attribute matrices X1, X2 (if avail- able) respectively, using low-rank (d). 1: if X1, X2 are available and should be used then
2: Construct graph from X, and append to G, to gener- ate an augmented A,, i = 1,2
G = APPEND(G,, G-CONSTRUCT(X..)
(15)
3: end if
Then we calculate MMFD( (aI, G2) or MMFDER(G1, G2). For instance, the top of Figure shows two simple graphs with the same adjacency matrix but different node attributes. In this case, MMFD(G1, G2) 0 and MMD(X,, X2) = 0. but G1 and G2 are different. In contrast, as shown by the bottom of Figure 2, G1 and G2 are different and we have MMFD(G,, G2) = 0.0026 and MMFD, G2) 0.0032 (d = 3). It is worth mentioning that, for MMFD, compared to (15), there may exist more effective strategies
4: SVD or randomized SVD: A, ~ U,S. ,1 1,2.
5: if using low-rank is True then
PSD: A = V.S.V i = 1,2. (V. vid)
else
8: PSD: A V,S, i = 1,2.
9: end if
10: MMFD =
Σ m. iA Juo
1 ug
V Enp A
Output: MMFD
6

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
2.7. MMFD for Large-Scale Clustering
min RISER
1 Σ
k(
+
Σ
k
k(R120!)) RI2
2
"i n
12
Given a set of N graphs, denoted as GG,,,. Gr). belonging to K classes, if we perform spectral clustering with MMFDLR on G, the space complexity and time complexity are quadratic with N,
2
Σ
K R12Φ("))
1/2
(20)
112
which prevent its applications to very large graph datasets.
where k denotes a nonlinear kernel with feature map Ç.
Inspired by K-means clustering, we may consider finding K graphs, ......, Gk. representing the centers of clusters GI...., GK respectively, such that the sum of the squared distances measure by MMFD1R (or MMFD) between the graphs and their corresponding centers is minimum, i.c.,
The following theorem shows that MFD is a pseudo-metric under some mild assumptions.
Theorem 2.8. When the kernel function in (20) is rotation- invariant kernel (e.g., radial basis function kernel), MFD is pseudo-metric.
minimize
Σ
IMFD (G,, Gÿ)
(17)
Unlike MMFD, MFD has no closed- solution and has a higher computational cost. Letting & in (20) be the Gaussian kernel with parameter /9, we have
GI...GKK j=1 E,E,
However, we cannot obtain GI....,Gi Gk themselves be- cause LMFD is operated on the PSD adjacency matrices. Actually, we do not need to learn GI...., Gr. Based on (14), we can rewrite (17)
MFD(G1, G2)
1
Σ
exp(- - 11.
min RIZER
24,11
K
minimize GK....GK
Σ j=1 G,Eg
1
Σ uv
B
Blu
- 6.2)
lae
2
T4
n
12
uv
u,0
(18)
exp(-31l0 R12e5!1113) (1)) 1/2
2
where Bj and denote the adjacency matrix and the number of nodes of Gj. j 1,...,K K. Letting gi
n1n2
1. Euo [A, Jue and eg = 1 LVV V.n B, we obtain from (18) that
2
Σ exp ( (-3(LA9) Juer + 1Ag
min RizER
C
n1
K Σ
1/2
-((b RI2(((21)) (12o((11))
minimize
Σ
(g: o3
(19)
CL.....K
j=1 G;E8,
(21)
where C
1 EnD exp ( 3((A4)
I Ju + [A
(g-c)" 11 * j}. This is actually K-means on N I-D data points, where we only need to optimize scalars CI...., CK. rather than GI,...,rr, Suppose n1 = .... nn = n, then the to- tal space and time complexity are O(n² + dn + N + K) and O(N (n² log(d)- + d'n) N KKT), both linear with N, where T denotes the number of iterations in K-means. For convenience, we call this clustering method MMFD-KM.
where 9j = IG (
+
1 Eu,o exp 3(IA
+
ng
2 2[44] )lv)) Thus, for MFD, we need to solve the following problem
maximize RISER
Σ auv exp (23(6!))
(1) R120 2 C(R12)
(22)
where aue = exp(- uua (Ag](e)) This is a chal- lenging problem and has no closed-form solution because of the sum-of-exp form and the orthonormality constraint.
MMDD-Beyond Mean Comparison
MMFD compares only the mean vectors of Φ1 and Ø2- To exploit more information of $ and Φb we provide generalized method, called MFD, in the following.
To tackle the difficulty, letting R, (t-1) be the solution at iteration t - 1, we consider the following quadratic approxi- mation at iteration t
Definition 2.7 (MFD). Let A = क o i = 1,2. The minimum factorization distance between G, and G2 de- fined as
C(R12) = ((R((- + (G(t-1) RR12 - R R
(23)
R - R1
MFD Go)
2
1 nJ
1 n2
where (t-
VL(R ((-1)
min R.zER
71
_
Σ (1)
n2
< (R126(20)
2 Σ uv Que exp(23(
R ((((-))
(2)
1 (1) $
and
j=1
i=l
7

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
> is hyperparameter to be determined. Now we solve the following problem at iteration t:
Algorithm 2 Computation of MFD between Graphs
Input: Graphs G1, G2 with self-looped adjacency matrices
1 2 d, B, e, T, p.
C( 1 + (G R12 R2 1
maximize R1
1: Randomized SVD (d): A; ~ U,S, =
(24)
+; =/== 5/'2V VT 1 1,2.
P R12
R12=1
11
2
3: Initialization: R Ia.
(0)
4: while t < <T'do
or the following equivalently
5: t < ++
maximize (G R
pR
(t-1) R12)
(25)
6: Q: (28 Gao exp (23( 12 $!.1)
(1) (t-1))
x
$10 0 (2)
p (t-1)
(1
Letting Q: = (((- + + 1t-1) we rewrite (25)
7: Perform SVD: Q: = USVT.
8: R = UV
maximize (R12, Qi)
(26)
ir | 10
R(= 1F/Vd then
R12ER
10: Break.
Then we have the following closed-form solution
11: end if
12: end while
R = UVT,
(27)
13: Calculate MFD using 2 and (21).
Output: MFD(G1, G2)
where U and are from the SVD of Q i.e., Q USVT.
We summarize the optimization steps for MFD in Algorithm 2, where the utilization of node attributes (if available) is omitted for simplicity. The following theorem provides a theoretical guarantee of the convergence of the optimization.
to lower uncertainty. Finally, our MMFD-KM and MFD- KD are specified for clustering. We consider six large or relatively large datasets of graphs from the TDUdatasets (Morris al., 2020). More details are in Appendix B.
Theorem 2.9. Let {C(R())) }+ and {R l be the se- quences given by Algorithm 2. For any p it holds that:
The proposed methods are compared with three categories of competitors. The first category is graph kernels includ- ing SP (Borgwardt & Kriegel, 2005), GK (Shervashidze et al., 2009), RW (Vishwanathan et al., 2010), WL (Sher- vashidze et al., 2011), LT (Johansson et al., 2014), and WL-OA (Kriege et al., 2016). The second category is unsu- pervised graph representation learning methods including InfoGraph (Sun et al., 2020), GraphCL (You al., 2020), JOAO (You et al., 2021). and GWF (Xu et al., 2022), fol- lowed by K-means or spectral clustering. The last category is the end-to-end GNN-based graph-level clustering meth- ods including GLCC (Ju et al., 2023) and DCGLC (Cai et al., 2024). Besides, we also include MMD (detailed in Section 2.5), Gromov- Wasserstein distance (GWD) with entropic regularization, and graph edit distance (GED) (Serratosa, 2014) in the experiments. More details about the settings are in Appendix B.2. The evaluation metrics for cluster- ing performance are clustering accuracy (ACC), normalized mutual information (NMI), and adjusted rand index (ARI).
(a) {C(R (1) }e is non-decreusing, ie,, ((R
12
C(R 12
" + +
-
(b) (1(2) ) convergent, i.e., R R R((-1) 0 when +
The time complexity of MFD with low-rank approximation is (n² log(d) (d) + + +dn?)) which is much higher than that of MMFDLR. However, in the experiments (see Ta- ble 3 and Figure 11). the performance of MFD is better than that of MMFD, because MFD can utilize more information of 22 and 2.
2.9. MFD for Large-Scale Clustering
Based on MFD, we provide a fast flasterrin algorithm called MFD-KD, which detailed in Appendix A.2.
3. Experiments
Table 3 shows the clustering results on the four datasets with moderate sizes, where for all compared methods ex- cept MMD, GWD, and GED, we just use the results reported in the paper of (Cai et al., 2024). All our methods outper- formed other methods in terms of the three metrics on AIDS, PROTEINS, and REDDIT-MULTIC ZYMES, our MFD performs best. The differences between MMFD, MMFDLR, and MMFD KM are tiny but their per-
Previous studies usually used graph classification evalu- ate graph kernels distances. Differently, in this work, we use clustering, due to the following reasons. First, clustering is more challenging than classification, especially for im- balanced datasets. Second, clustering does not involve data splitting and has fewer hyperparameters to tune, leading
significantly. On EN-
8

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
AIDS (N 2000)
PROTEINS (N
1113)
ENZYMES (N
600)
REDDIT-MULTI-SS SKLTI-KK (V
4599)
Method
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NM1
ARI
ACC
NMI
ARI
SP kemee
79.4920.88
0.3910.62
-0.71=1.13
64,4240.00
6.03
58740000
22,00:20.00
2.57:0000
1.6910.000
20,0240.00
0.05=0.00
0.0010.00
GK kemme
79.95:10.00
0.04.0..00
0.07
99.61110.22
0.2410.18
0.10.10.19
17.07.10.13
0.80:10.25
0,00.10.00
RW kermel
79.90:0.00
0.09:0.00
-0.15=0.00
17.00+00.00
0.66:00000
0.25:10.00
WL kemne
78.50.10.00
1.17.0.00
2,0090..00
60.38.0.00
1.55.0.00
0.8110.00
21.0010.000
3.09:10:00
1.48.10.00
20,0010.000
0.00..0.00
0.00.0.000
LT komel
79.95=0.00
0.04:0.00
-0.07=0.00
17.00=0.09
0.42:0.11
0,00:00000
WL-OA kemnel
80.40110.00
2.46.10.00
2.38.10.00
60.38100000
1.5510000
0.8110.000
20.00100:00
1.35.0.00
0.32:10.00
InfoGrapb++M
92.21:10.81
54.49:3.55
63.7843.84
59,2210.21
3.22
0.0020.00
22.06::0.98
2.40:00455
1.25:1.522
20.1610.002
0.30=0.05
0.0010.00
InfoGrapb+SC
95.65=1.555
72.21=9..0
80. 70.1777.11 1.
64.0242.31
5.17=1.87
7.06+2.65
23.75=0.50
0.64=00.55
2.23=#0.41
0.000=0.00
0.00=0.00
0.00+00000
GraphCL+KM
90,4011.06
46.561:4.31
55.2945.28
59.4740.01
0
0.0010.00
21.50=0.22
1.5520.12
0.9010.09
20.32:0.00
0.56=0000
0.0010.00
GraphCLASC
96.08+1.9
10.97=10.86
81 661+8.11
59, 10
281=00077
3.88+0088
25,28=0.28
4.75+0036
2.03++0.26
20.08=00.00
0.16=0.00
0.00+0.00
JOAO+KM
88.25:20.00
38.02:00.00
44.62:00.00
59.4840.00
0.6420005
-0.06=0.000
21.66:20.37
1660:0001
0,94:10.02
20.34=0.00
0.60=0.00
0.00:00000
JOA0-SC
80.13+00.02
0.84+0.15
0.80=0.14
59.75+0.00
0,47=00.0
0,17+0.00
24.65=0.44
3.85+0:37
2.07+0.18
20.39+0049
0.08=0.00
0.01+0.01
GWF+KM
96.43:11.71
74.48::9.15
84.71=7.02
66.87+2.36
9.07=1.21
11.43=3.19
28.55=0.20
6.02:0.555
3.16:20.20
GWF+SC
96,44+2992
76.01+15.23
83.54+13.61
68.79+2.05
10.17+1.774
13.88+2.72
25.66+11.57
5.24+1128
1.78++0.6
GLOCC
79.02+0.62
4.18++2.11
5.05++2.3
60.65+2..69
2.08+1.43
4.16+-2.28
19,89+1.09
2.42:40.18
0.19+0012
23.50+0.48
6.57-3.56
4.00+0.800
DCGLC
96,7740.33
73,51+2.30
85.74+145
68,8942.00
10.90 35
14.32+2.88
28,43:#1228
6.57:40.0
3,78+00.77
33.2442234
8.81=2228
7.16+1677
MMD
50,10+0.00
0.00++0.0
0.03++0.00
52.56+00.00
0.08+0.00
0.14+0..0
22.90+11:14
1.79:+0.28
0.47+0.22
33.31+0.91
17.68+0.17
11.20+0.84
GWD
88.30110.00
49.73:10.00
56.45
68.8210.00
12.42-10:00
12.37.0.00
23.08100.37
3.9110.69
0.41.0.111
GED
89.55++0.00
43.33++0.00
51 51.02++0.00
52.24+0.07
3.92+0023
-0.23+00.33
25.50++0.00
5.05-+0.18
2.24+0.06
MMFD
98.80:00.00
88.37-+0.00
94.49
72.60+0.00
19.67:40.00
23.68:1.31
5.99:1077
1.96:0033
35.97:10.48
18.1240611
13.74
MMFDLE
98.8010.00
88.37:1.000
94,4910.00
72.4910,13
13.9810.225
19.4920.23
23.62::0.83
6.5510.42
2.13:0,222
36.5411.,56
18.31:0.74
13.99
MMFD
98.96:10.02
89 89.62.10.18
95.25 10.11
71.8710.18
12.74.1..44
18.51
25.67.10.77
6.34.10.8
2.06.0..37
35.62.10.46
19.80-10:06
13.74....0
MED
99.45:0.00
93.82:10.00
97.4710.00
72.601:.00
14.18:0.00
19.67.0.00
30.33:11.16
8.4510226
4.42.1..33
35.35100.01
17.2610.03
14.9010.02
MFD-KD
99.02.10.00
90.01.10.34
95.51
72.39.10.30
14.06.10.40 19.24
26.25 7.54.10.69 2.21
34.86.10.22
19.70.10.29 14.46
Table 3: Clustering results (mean + std of 10 trials) on the four moderate-sizz datasets. The best, second- bbstt, and third-best
results are highlighted in purple, red, and orange respectively. " "_" denotes out-of -o--oor or taking more than 12 hours.
formances are lower than MFD and MFD-KD in most cases, since MFD can exploit more information of distributions.
4. Conclusion
This work proposed MMFD and MFD as efficient and ac- curate distance measures between graphs. For large-scale clustering, we also proposed MMFD- -M and MFD-KD, which has a linear complexity with respect to the number of graphs in dataset. We analyzed the properties of the pro- posed distance measures. We used synthetic graph data to show the effectiveness of MMFD and MFD intuitively. The experiments on real-world graph datasets showed that our methods are not only efficient but also accurate in clustering.
Table 4 compares the time costs of four methods in comput- ing the distance or similarity matrices on two datasets. We see that our MMFDLR R is the fastest while GWD is extremely time-consuming.
AIDS
PROTEINS
Shortest-path kernel
1.51
7.55
WL-subtree kernel
0.81
0.90
Entropic GWD
25544.26 0.26
4549.31
One limitation of the current work is that we haven't 't pro- vided any numerical results of the variant of MFD proposed in Appendix A.3 because the optimization is too costly.
MMFDLR
0.61
Table 4: Time costs (second) comparison.
The Python code of the proposed algorithms is avail- able at https://github.com wttp://...ooooioootnaaoaaiaoc Craph-Wiiinnmm-Pootriiaaaaa Diwiiion---Daneeee
Due to space limitations, the following results are presented in the appendices:
Distribution comparison (Appendix C.1)
A Acknowledgements
Effectiveness of node attributes (Appendix C.2)
This work was supported by the National Natural Science Foundation of China under Grant No. No.62376236.
Hyperparameter analysis (Appendix C.3)
More running time comparison (Appendix C.4)
Impact Statement
Visualization of graphs (Appendix C.5)
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
More results on toy graphs (Appendix C.6)
Experiments on larger datasets (Appendix C.7)
Molecular property prediction (Appendix C.8)

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
References
Gilmer, J., Schoenholz, S. S., Riley, E. Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In ICML, pp. 1263-1272. PMLR, 2017.
Abu-Aisheh, Z., Raveaux, R., Ramel, J.-Y., and Martineau, P. An exact graph edit distance algorithm for solving pattern recognition problems. In 4th International Con- ference on Pattern Recognition Applications and Methods 2015, 2015.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Agarwal, S. Ranking on graph data. In ICML, pp. 25-32, 2006.
Halko, N., Martinsson, P.-G,, and Tropp. J. A. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):117-28) 2011.
Aggarwal, C. C. An introduction to social network data analytics. Springer, 2011.
Hido, S. and Kashima, H. A linear-time graph kernel. In 2009 Ninth IEEE International Conference Data Min- ing, pp. 179-188. IEEE, 2009.
Bell, M. G. and lida, Y. Transportation network analysis. Wiley Online Library, 1997.
Bento, J. and loannidis, S. A family of tractable graph distances. In Proceedings of the 2018 SIAM International Conference on Data Mining, pp. 333-341. SIAM, 2018.
Hjelm, R. D., Fedorov, A., K., Bachman, P., Trischler, A., and Bengio, Learning deep representations by mutual information estimation and maximization. In International Conference on Learn- ing Representations, 2019.
S., Grewal,
Borgwardt, K. M. and Kriegel, H.-P. Shortest-path kernels graphs. In ICDM, pp. 8-pp. IEEE, 2005.
Bro, R., Acar, E., and Kolda, T. G. Resolving the sign ambiguity in the singular value decomposition. Journal of Chemometrics: A Journal of the Chemometrics Society,
Hofmann, T., Schölkopf, B., and Smola, J. Kernel meth- ods machine learning. Ann. Statist., 36(1):1171-1220, 2008.
22(2):35--140, 2008.
Hogan, A., Blomqvist, E., Cochez, M., d' Amato, C., Melo, G. D.. Gutierrez, C., Kirrane, S., Gayo, J. E. L., Nav- igli. R., Neumaier, S., et al. Knowledge graphs. ACM Computing Surveys (Csur), 54(4):1-37, 2021.
Bunke, H. On a relation between graph edit distance and maximum common subgraph. Pattern recognition letters, ((8))689-694 1997.
Cai, J., Zhang, Y., Fan, J., Du, Y., and Guo, W. Dual con- trastive graph-level clustering with multiple cluster per- spectives alignment. In Proceedings of the Thirty-Thin International Joint Conference on Artificial Intellience, IJCAI-24, pp. 3770-3779, 8 2024. Main Track.
Horn, R. and Johnson, C. R. Topics in Matrix Analysis. Cambridge University Press, 1991.
Jochum, C., Gasteiger, J., and Ugi, I. The principle of minimum chemical distance (pmed). Angewandle Chemie International Edition in English, 19(7):495-505 1980.
Chang, L., Feng, X., Yao, K., Qin, L.,, and Zhang, W. Ac- celerating graph similarity search via efficient ged com- putation. IEEE Transactions on Knowledge and Data Engineering. 35(5))4485 2022.
Johansson, F,, Jethava, V., Dubhashi, D., and Bhattacharyya, C. Global graph kernels using geometric embeddings. In ICML, pp. 694-702. PMLR, 2014.
Cortes, C. and Vapnik, V. Support-vector networks. Ma- chine Learning, 00:273-297, 1995.
Ju, W., Gu, Y., Chen, B., Sun, G., Qin, Y., Liu, X., Luo, X., and Zhang, M. Glee: general framework for graph- level clustering. AAAI, volume 37, pp. 4391-4399, 2023.
Cuturi, M. and Doucet, Fast computation of wasserstein barycenters. In International conference on machine learning, pp. 685 693.693.8 PMLR, 2014.
Kerdoncuff, T., Emonet, R., and Sebban, M. Sampled gro- mov wasserstein. Machine Learning, 21112)21 2021.
Davis, C. and Kahan, W. M. The rotation eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
Gärtner, T., Flach, P., and Wrobel, S. On graph kernels: Hardness results and efficient alternatives. In Learn- ing Theory and Kernel Machines, pp. 129-143. Springer, 2003.
Kobler, J., Schöning, U., and Torán, J. The graph iso- morphism problem: its structural complexity. Springer Science & Business Media, 2012.
10

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
Kondor, R. and Pan, H. The multiscale laplacian graph ker- nel. Advances in neural information processing systems, 29, 2016.
Rong, Y., Bian, Y., Xu, T., Xie, W., Wei, Y., Huang, W. and Huang, J. Self-supervised graph transformer large- scale molecular data. NeurIPS, 33: 33:12559-12571, 2020.
Kriege, N. M., Giscard, P.-L., and Wilson, R. On valid optimal assignment kernels and applications to graph classification. NeurIPS, 29, 2016.
Santacruz, P. and Serratosa, F. Error-tolerant graph matching in linear computational cost using an initial small partial matching. Putlern Recognition Letters, 134:10-19 2020.
Linsker, R. Self-organization in a perceptual network. Com-
Schönemann, P. H. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31(1):1-10, 1966.
puter. 21(3):105-117, 1988.
Luss, R. and d' Aspremont, A. Support vector machine classification with indefinite kernels. Advances in neural information processing systems, 20, 2007.
Serratosa, F. Fast computation of bipartite graph matching.
Pattern Recognition Letters, 45:244-250, 2014.
Serratosa, F. Computation of graph edit distance: Reason- ing about optimality and speed-up. Image and Vision Computing, 40:38-48, 2015.
Mémoli, F. Gromov-wasserster distances and the metric approach to object matching. Foundations of computa- tional mathematics, 11:17-487, 2011.
Shen, X., Sun, D., Pan, S., Zhou, X., and Yang, T. Neigh- bor contrastive learning learnable graph augmentation. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 37, pp. 9782-9791, 2023.
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection bench- mark datasets for learning with graphs. arXiv preprint arXiv:2007.0888 07,666,,,, 2020.
Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., and Borgwardt, K. Efficient graphlet kernels for large graph comparison. In AISTATS, pp. 488-495. PMLR, 2009.
Neuhaus, M. and Bunke, H. Bridging the gap between graph edit distance and kernel machines, volume 68. World Scientific, 2007.
Ng, A., Jordan, M., and Weiss, Y. On spectral clustering: Analysis and an algorithm. Advances in neural informa- tion processing systems, 14, 2001.
Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, M. Weisfeiler-lehman graph kernels. JMLR, 12(9), 2011.
Nikolentzos, G., Siglidis, G., and Vazirgiannis, M. Graph kernels: A survey, Journal of Artificial Intelligence Re- search, 72:943-102 1027, 2021.
Sun, F.-Y., Hoffman, J., Verma, V., and Tang. J. Infograph: Unsupervised and semi-supervised graph-level represen- tation learning via mutual information maximization. In ICLR, 2020.
Ong. C. S., Mary, X., Canu, S., and Smola, A. J. Learning with non non-positive kernels. In Proceedings of the twenty- first international conference on Machine learning. pp- 81, 2004.
Sun, Y. and Fan, J. Mmd graph kemnl:: Effective metric learning for graphs via maximum mean discrepancy. In ICLR, 2024.
Peyré, G., Cuturi, M., and Solomon, J. Gromov-wasserstein averaging of kernel and distance matrices. In Interna- tional conference on machine learning, pp. 2664-2672 PMLR, 2016.
Sun, Z., Ding, C., and Fan, J. Lovász principle for unsu- pervised graph representation learning. In Advances in Neural Information Processing Systems, volume 36, pp. 58290-58311. Curran Associates, Inc., 2023.
Resnick, P. and Varian, H. R. Recommender systems. Com- munications of the ACM, 40(3):56-58, 1997.
Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, (111), 2008.
Riesen, K. and Bunke, H. lam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Patlern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings, pp. 287-297. Springer, 2008
Vayer, T., Flamary, R., Tavenard, R., Chapel, L.., and Courty, N. Sliced gromov- arXiv preprint arXiv:/905. 10/24, 2019.
Vayer, T., Chapel, L., Flamary, R., Tavenard, R., and Courty, N. Fused gromov-wasserster distance for structured objects. Algorithms, 13(9):112, 2020.
Riesen, K. and Bunke, H. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing, 27(7):950-955 2009.
Villani, C. et al. Optimal transport: old and new, volume 338. Springer, 2009.

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
Vishwanathan, S. V. N., Schraudolph, N. N., Kondor, R., and Borgwardt, K. M. Graph kernlls. The Journal of Machine Learning Research, 11:1201-1242, 2010.
Wang, and Fan, J. Graph classification via reference distribution learning: Theory and practice. In Advances in Neural Information Processing Systems, volume 37, pp. 137698-137740. Curran Associates, Inc., 2024.
Weisfeiler, B. and Leman, A. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9))12-16, 1968.
Wu, Z., Zhang, Z., and Fan, J. Graph convolutional kernel machine versus graph convolutional networks. NeurlPS, 36, 2024.
Xu, H., Luo, D., Zha, H., and Duke, L. C. Gromov- wasserstein learning for graph matching and node embed- ding. In International conference on machine learning, pp. 1932-6941. PMLR, 2019.
Xu, H., Liu, J., Luo, D., and Carin, L. Representing graphs via gromov-wasserstiin factorization. IEEE 1-PAMI, 2022.
You, Y., Chen, T., Sui, Y., Chen, T., Wang. Z., and Shen, Y. Graph contrastive learning with augmentations. NeurlPS, 33:5812-5823, 2020.
You, Y., Chen, T., Shen, Y., and Wang. Z. Graph contrastive learning automated. In ICMI, pp. 12121-12132. PMLR, 2021.
Yu, Y., Wang, T., and Samworth, R. J. A useful variant of the davis kahan theorem for statisticians. Biometrika, 102(():315-323, 2015.
Zeng, Z., Tung, K., Wang, J., Feng. J., and Zhou, L. Comparing stars: On approximating graph edit distance. Proceedings the VLDB Endowment, 2(1):25-36 2009.
12

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
A. Beyond Mean Comparison: MFD
A.1. Optimization of MFD
Based on Theorem 2.9, we can just let p be a small positive constant such as 10 Figure shows the optimization process of MFD with different p on the G1 and G2 presented by Figure In the experiments of real datasets, we set 10, which sufficient.
0.07
2-0.1
0.05
0.07
2-0.01
0.05
0.00
0=0,001
0.05
0.06
g=0.0001
0.06
change B.
0.00
0.00
0.045
Retstve drange
0.045
Patativs change Rgg
0.00
0.045
Relesive change Rg
0.045
0:04
0.04
8.00
0.04
0.04
0.04
0.00
0.035
0.035
0.005
0.005
0.02
0.03
0.03
0.08
0.00
0.01
025
0.05
30
20
30
20
Iteraion
Ioration
Figure 3: Optimization process of MFD G1 and G2 in Figure 2.
is worth mentioning that we can perform down-sampling on Φ; to reduce the time cost of MFD. Suppose we randomly select n, columns of $, and then compute MFD, then the time complexity becomes O(n log(d) + ddn + T(d dn.)), where n, < This can greatly improve the efficiency of computing the MFDs of N graphs.
A.2. MFD-KD for Large-Scale Clustering
Similar MMFD, we can extend MFD to large-scale clustering by reducing the complexity dependency on N2 to N. Specifically, we propose to solve
K
minimize Gr....Ge
MF, Gi)
(28)
GLES
Instead of solving GI,...,
Ba....,Ge GK we solve their features denoted as M UK E MMn, We have
minimize Σ
min R,ER
2 CR 3
1 n
1 n
Σ
((ubf)) / & R.),
(29)
V Piree WK
n2
G.E9
For convenience, call this method MFD-KD, where 'KD' stands for "K-distributions" The optimization is little bit similar K-means clustering. First, we initialize (/() (0) At iteration I, for each G,, we find its label by solving
(0) argmin min ((D(1-1) R.)
(30)
1SKCK REE
where the corresponding optimal R; are denoted as R ( The optimization for (30) can be similarly solved by Algorithm 2. Base on 18"), i 1,..., N. we have the updated G1,... GK. Next, update each of L 1....., L x by
(t) argmin
Σ C(
(31)
G.EG
This can be solved by any gradient-based methods. We alternate between (30) and (31) until some convergence condition is reached. Specifically, (31) is equivalent to
minimize Mr
Σ
Σ
exp(-Bllub
111
2
Σ
exp(-Bll<b - -R."0 (."
(32)
G.E9
M28
M.P
13

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
Let C be the objective function in (32), have the gradient
4 (Q:
43 (Ø,
Ve, C =
L
diag(1 (0o(("00) (Q:))
R
R
1idiag
(G))
n²
7,7
G:ER
(33)
1
43
Q:)) Q diag(1 (0))) + diag(1 d (TGGGG
43
48
R
(0)
&,G.
n²
74
GRE01
where Q [exp(-Bll<b
b [2]] and G. [exp(- R. (1) w [1)]]
Then we perform the following gradient
descent
v ー 1 Vv
(34)
where 17 = c/ H 2. c S 1 some constant, and Ea,eg, ( - diag(1)Q:))) + - diag Gi)) Note that
here || rough approximation of the Lipschitz constant of the gradient Vv In our experiments, we set c 0.5.
The optimization steps of MFD-KD KD is summarized into Algorithm 3.
Algorithm 3 MFD-KD Clustering
Input: Graphs G1, G2,...,Gr with self-looped adjacency matrices A,, A2,.. Ba....,AN,, ,N, K, d, B. p. T1. T2, T3-
1: for i=1:N do
2: A; Rd U,S, VT (randomized SVD, rank-d).
3: A V,S V.
4: Φ; = S V
5: end for
(0) 6: Initialization: V 1
(0) K
E
MR 1= 0.
7: while / < T; do
8: f 1.
9: for i=1:N do Solve (30) each using Algorithm 2 with T2 iterations.
end for
for 1=1:K do
13:
Solve (31) using gradient descent (e.g., (34)) with T33 iterations.
14: end for
15:
end while
Output: GI GI.22...,9M
A.3. A Variant of MFD based on EMD
In MFD, instead of MMD, we can also use the optimal transportation theory to measure the distance between two distributions. The corresponding distance is the Wasserstein distance or Earth Mover's Distance (EMD). Let's consider cost matrix defined as
C(R12) == cost(#; R12
(35)
where cost Mxn1 x Mx + Xpa, Now let & be the EMD and define P == (P E R2ix02 P.,. 2 0, P 1, 1,z/ /22 Pln, 1n, /n1/ obtain the following distance between G1 and G2
MFD(G1, G2)
min RIDERPPUEP
(C(R12), P1z)
(36)
min RRIER,PIES
(cost( p,, R12 P12)
The optimization of this MFD(G1, G2) ) is challenging, Since there are two blocks of parameters to optimize, propose to use alternating minimization, i.e.,
argmin (cost( Φ1, (t(1) P12)
(37)
12 PiZEP
14

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
R 12 = argmin
P12
(38)
RIzER
Subproblem (37) can be solved by Sinkhorn iteration, while subproblem (38) be solved by method similar to that for (22). Both subproblems are time-consuning. The total time complexity of MFD with EMD is much higher than that of MFD with MMD. In this work, we do not provide more details about this method.
B. Experimental Settings
B.1. Dataset Description
Table 5 presents the basic information of the datasets used in this work. They were downloaded from https: htttps//cchssmrzz chrsmrrs.. github. 1 datassttsss....... All experiments were conducted on computer with Intel Core 19-12900K and RAM 64GB.
Name
Graphs
Average nodes
Average edges
Node Attributes
Classes
Domain
AIDS
2,000
15.69
16.20
4
2
Molecule
PROTEINS
1,113
39.06
72.82
29
2
Biology
ENZYMES
600
32.63
62.14
18
6
Biology
REDDIT-MULTI-SK
4,999
508.52
594.87
5
Social networks
DBLP-v1
19,456
10.48
19.65
2
Social networks
REDDIT-MULTI-I2K
11.929
391.41
456.8
11
Social networks
Table 5: Statistics of the graph datasets used in this work.
B.2. Hyperparameter Settings
Since we just used the results of the graph kernels, graph representation learning, GLCC, and DCGLC reported in the paper of (Cai et al., 2024), the corresponding settings of the hyperparameters or neural network architectures can be found in (Cai et al., 2024). We implement the entropic-regularized GWD using the function of POT https / /pythonot. github. io/index: html, where the loss function is the square loss, the regularization hyperparameter is chosen from (0.01,0.14 the maximum iteration is 100, and the iteration tolerance 0.01. We implement GED using the function of graphkit-learn https: httpas:://gppahitt-teeeg
headthedocs. wt//e//matter///ee//eeeeeeeeeeee index. html, where the edit costs of edge and node insertions and deletions are all set to 1.
we set d 20 on all datasets. In MFD and MFD-KD, we use different rank d = 30 because we do not compare the full rank with low rank for simplicity. For spectral clustering, the 7 in the Gaussian kernel is set as 1/(cu)?, where u denotes the average MMDF (or MMD, GWD, and GED) between all graphs and e = 5 for all datasets. On ENZYMES, we use the node attributes in MMFD, MMFDLR. and MMFDLR-KAN MFD, and MFD-KD, where the graphs based on the attributes are constructed by Gaussian kernel. In MFD and MFD-KD, the hyperparameter 3 chosen from {0.01, 0.1, 1). For MFD (Algorithm 2), we set T 10. For MFD-KD (Algorithm 3), we set T2 T3- = 5, on all datasets, set T3 10 on large datasets (i.e., the two REDDIT datasets), and set Ti 20 other datasets. Particularly, on the REDDIT-MULTI-5K dataset, for MFD, we let d = 5 and use down-sampling on 4; with sampling rate 0.2 to improve the efficiency. which leads to a total time cost of 5.5 hours.
In our MMFDLR and MMFDIR-BR
C. More Results
C.1. Effectiveness of Distribution Comparison to Distinguish Graphs
We randomly generate Z1, Z2 E IR 100 from the same Gaussian distribution with zero mean and unit variance and generate Z3 E 100 from a uniform distribution with zero mean and unit variance. From Z,, Zz, Za we construct three graphs using the kernel function k(z,, 2.) 1 (cxxp(-0.1 I|z. z II?) > 0.5) respectively. We then calculate the MMFDs between the three graphs. For instance, in one experiment, we have MMFD(G,, G2)=0.0038 and MMFD Ga)=0.0276, meaning that G1 is more similar to G2 than to G3. We repeat the experiment 100 times and conduct t-test on the values of MMFD(G,, G2) and MMFD(G, Ga). The p-value is less than 10-6 meaning that the difference significant. When we also generate Zy from the Gaussian distribution and repeat the experiment 100 times, the p-value of t-test between MMFD(G,, G2) and MMFD(G1, G3) is 0.6864, meaning that the difference is not significant. These results demonstrated
15

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
that comparing distributions is an effective proxy of comparing graphs
A 2 Gausssan)
A Z Gaussian)
Ag (:nnnioommm
20
20
20
40
40
40
80
80
60
100
100
100
20
40
60
80
100
20 60
80
100
20
40
60
80
100
Figure 4: Visualization of the adjacency matrices of three graphs G1, G2, G3 constructed from two 10-D Gaussian distributions (zero mean and unit variance) and one 10-D uniform distribution (unit variance) respectively. The kernel function is k(z,, Z,) = (0.1l// 1 > 0.5). We have MMFD(G1, G2)=0.0038 and MMFD(G1, G3)=0.0276.
C.2. Effectiveness of Node Attributes
AIDS, PROTEINS, and ENZYMES have inherent node attributes. Therefore, we use them to evaluate the effectiveness of incorporating node attributes into our proposed methods. For simplicity, we take MMFD as an example. The results are reported in Table 6. We see that using node attributes can improve the clustering performance, and the improvement on PROTEINS most significant.
AIDS
PROTEINS
ENZYMES
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NMI
ARI
without node attributes with node attributes
98.96:00.02 19.62+0.18 95.25==0.11 11
11.87=0.18
12.74+0.34
18.51
23.27=
0.34 0.82+0.09
99.10=10.00
90.68=0000 95.87=00.0
75.19=0005
18.1740.10
24.81+00111
25.67=00.77
6.34=00688 2.06
Table 6: Clustering performance (mean + std of 10 trials) of MMFD KM with or without using node attributes.
C.3. Hyperparameter Analysis
In our MMFD, there is no hyperparameter. In our MMFDIR R and MMFDIR-KM, the only hyperparameter is the rank d. Here we take the datasets PROTEINS and REDDIT-MULTI-SK as examples to show the impact of d on the clustering performance of MMFDLR- The average results of 10 trials are shown in Table 7. On PROTEINS, since the average number of nodes is quite small, we have chosen from 1 to 40 or used full-rank. We see that when d decreases, the performance in rank- 10 performs the best. In general, the performance of MMFDLR not very sensitive to r. Even when the rank is 1, our MMFDLR still outperforms the competitors in Table 3.
terms of the three metries becomes worse. On REDDIT-MUI.TISSK
Dataset
Metrics
rank
full-rank
rank-40
rank-30
rank-20
rank-10
rank-5
rank-3
rank-1
ACC
72.60=00.00
72.60:10.00
72.60:10.00
72.49:10.13
72.31:10.14
72.08:10.04
71.83:10.04
72.13:10.13
PROTEINS
NMI
14.18=00.0
14.18=20.00
14.18=20.00
13.98-+0.25
13.62-+0.29
13.14=:0.10
12.55=+0.07
13.42+0.14
ARI
19.67=0.00
19.67:10000
19.67:10.00
19.29:10.23
19:22:4::24
18.83:10.06
18.49::0.08
18.83::0.26
full-rank
rank-200
rank-100
rank-50
rank-20
rank-10
rank-3
rank-1
35.97:20.48
36.13:1:0.4
06.33:10.56
36.12:10.91
36.18:1:0:00
36.85:10.81
06.60:10.82
05.77::0.59
REDDIT MULTI 5K
NMI ARI
18.12.10.61
18.09 10.62
0...9
18.06.10.61
18.62.10.65
18.83
17.83
1.032
13.74=11977
13.65-2.11
14.57::1.95
12.46:42.12
13.87:::1.96
15.08-
13.56::0.19
12.60-41.32
Table 7: Impact of the rank d on the clustering performance of MMFDLR. The best result in each case is highlighted in bold.
16

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
C.4. Runing Time Comparison
First, we study the time cost of our method and few baselines in comparing two graphs. We generate random graphs with the number of nodes n increasing from 100 to 30000, where the number of edges of each graph is about 0.1n². We compare the time costs (sccond) of MMFDLR. Shortest-paths kernel, WL subtree kernel, and Sromov-Wassersee entropic regularizer. In our MMFDLR, we set d = log(n). The results are reported in Table 8. We see that the Shortest-path kernel is most time-consuming while our MMFD is always the most efficient one.
distance with
100
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
20000
30000
Shortest-pali path kemel
0.035
4.853
25.8
77.8
178.7
317.9
524.8
779.3
1125.0
1520.3
2022.4
WL subtree kernel
0.009
0.393
1.5
3.4
6.6
10.5
15.3
21.1
27.4
34.9
43.4
182.6
449.7
Gromov- Wasserstein
0,021
0.367
0.5
1.2
2.3
3.9
6.4
9.0
12.8
17.1
21.9
169.1
579.7
MMFDLR
0.003
0.095
0.3
0.5
1.1
1.4
2.1
2.6
3.7
4.4
6.4
29.9
78.8
Table 8: Time cost (second) comparison on two random graphs. The number of nodes n. increases from 100 to 30000.
Second, compare the time costs of our method with the three baselines in computing the distance similarity matrices of a set of graphs. We consider AID, PROTEINS, and ENZYMES only because the Saanoo--asssesttenn distance with entropic regularizer is not scalable to larger graphs such as the REDDIT datasets. The results are reported in Table 9. Since the graphs in the datasets are small, the Shortest-pate kernel has a similar time cost as the WL-subtree kernel and our MMFDIR. The Gromov-Wasse Wasserstein distance, though having used the entropic regularizer, is time-consuming.
AIDS (N=2000)
PROTEINS (N=1113)
ENZYMES (N=600)
Shortest-path kernel WL subtree kernel
1.51
7.55
1.34
0.81
0.90
0.38
25544.26
4549.31
1600.87
MMFDLR
0.26
0.61
0.14
Table 9: Time cost (second) comparison on three moderate-size datasets.
C.5. Graph Visualization
According to the final format of MMFD, i.e. (12), we can visualize graphs in one-dimensional space directly using L=V2 Euoi [A]]umr i I,...,,, N. Regarding MFD, we can apply t-SNE (Van der Maaten & Hinton, 2008) to the obtained distance matrix between graphs visualize graphs in 2-D space. As shown in Figure 5, we compare MMFD and MFD with InfoGraph and DCGLC by visualizing graphs of AIDS in 2-D space. For InfoGraph and DCGLC, we just use the t-SNE plots reported in (Cai et al., 2024). We see that among the four methods, MFD has the best separation between the two clusters, which is consistent with its high ACC, NMI, and ARI.
C.6. More Results on Toy Graphs
C. MMFD V.S. OTHER MEASURES ON TOY GRAPHS
We compare MMFD with GED, GWD (without entropic regularizer), and WL--ubbrree kernel on the seven synthetic graphs used in Table 2. We implement the WL-subtree kernel using the function of GraKel https: : /ysssysg..... github. io/ GraKeL/ 0 1a8/ /, where the number of iterations 3 and the node labels are all one. To be consistent with other methods, we regard 1 - &GG,, G,) as the distance between G2 and Gy. The results are shown in Table 10. We have the following observations.
Regarding GED, for each of G2, G4, G7, it cannot provide unique closest graph. To each graph, there are always two graphs with the same distances.
Regarding GWD, the distances of G6 and G7 to G4 are the same. The closest graph to G, is identified as G4. which is not reliable.
17

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
1.5
30
-0
0
30
-0.5
-0
.00
-90
-70
-50
-30
-10
10
30
50
70
90
3
4
2
3
(a) InfoGraph
(b) DCGLC
0.8
0.6
-20
-40
(c) MMFD
(d) MFD
Figure 5: Visualization of graphs in AIDS. Plots (a), (b). and (d) are given by t-SNE, while (c) is the direct visualization of 1-D embedding (expanded 2-D) of MMFD. The number of classes in the dataset is two.
Regarding the WL-subtree kernel, does not distinguish between G1, G2, G3. The distance between Gy and G4 is much less than the distance between G7 and G3 (or Gs), which not reliable.
C.6.2. MFD V.S. MMFD ON Toy GRAPHS
We compare MFD with MMFD four synthetic graphs in Table 11. Intuitively, Gi and G2 more similar each other than to G3 and G₁, and vice versa. MMFD with full rank failed to identify the most similar graphs to G2 and G3. while MFD with rank one succeeded. In contrast, both MFD with full rank and MDF with rank one identified all similarities correctly. These results demonstrated the superiority of MDF over MMFD. The fundamental reason is that MFD can exploit more information of graphs in comparison to MMFD.
C.7. Clustering Results on Larger Datasets
We compare our methods with only three competitors, including WL-subtree kernel, InfoGraph+KM, and DCGLC, on two large datasets DBLP-v1 and REDDIT-MULTI-I2K because other competitors are too time-consuming and often outperformed by the three methods. Nevertheless, we run the three methods only once because they are still costly, while our methods are run 10 times because of their high efficiency. The results are reported in Table 12. Our methods outperformed
18

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
(a) MMFD
GED
0.0914
0.1589
0.2097
0.2528
0.2505
0.2505
6
10
12
0.0914
0.0675
0.1182
0.1614
0.1590
0.1591
4
4
12
10
0.1589
0.0675
0.0507
0.0939
0.0915
0.0916
10
0.2097
0.1182
0.0507
0.0432
0.0408
0.0409
10
2
8
0.2528
0.1614
0.0939
0.0432
0.0024
0.0023
10
4
6
4
0.2505
0.1590
0.0915
0.0408
0.0024
0.0001
12
12
10
8
6
4
0.2505
0.1591
0.0916
0.0409
0.0023
0.0001
12
10
8
4
(c) GWD
(d) WL-subtree kemell
0,4500
0.2500
0.3214
0.5625
0.5625
0.5625
0.2079
0.3610
0.4855
0.3965
0.4500
0.1444
0815
0.2275
0.2275
0.2275
0.2079
0.3610
0.4855
0.3965
0.2500
0.1444
0.1349
0.1806
0.1806
0.1528
0.2079
0.3610
0.4855
0.3965
0.3124
0.1845
0.1349
0.1658
0.1071
0.1071
0.2079
0.2079
0.2079
0.1323
0.1849
0.1083
0.5625
0.2275
0.1806
0.1071
0.0625
0.1250
0.3610
0.3610
0.3610
0.1323
0.2172
0.1693
0.5625
0.2275
0.1806
0.1071
0.0625
0.1250
0.4855
0.4855
0.4855
0.18749
0.2172
0.1401
0.5625
0.2275
0.1528
0.1071
0.1875
0.
1250
0.3965
0.3965
0.3965
0.1083
0.1694
0.1401
Table Comparison between MMFD and other measures on seven synthetic graphs (G1, G2...., G. from left to right). In each of each table, for the corresponding graph, the cell of the value of the numerically closest graph is highlighted in red.
other methods in most cases.
C.8. Chemical Molecular Property Prediction
We combine MMFD with support vector regression and call this combination MMFD+SVR. We apply it to the QM9 dataset. Since kernel SVR is not scalable to very large datasets, we only use 25000 graphs for training and 5000 graphs for testing. Some results of MAE are in Table 13, where the classic MPNN and enn-s2s (Gilmer et al., 2017) are compared. We see MMFD+SVR works well. It still has lot of room for improvement, e.g., by using attributes more effectively, using the extension MFD, or using more training data.
19

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
(a) MMFD (full rank)
(b) MMFD (rank-) 1)
0.0205
0.0364
0.0753
0.0235
0.0599
0.0866
0.0205
0.0159
0.0548
0.0235
0.0365
0.0631
0.3564
0.0159
0.0389
0.0599
0.0365
0.0267
0.0753
0.0548
0.0389
0.0866
0.0631
0.0267
(c) MFD (full rank)
(d) MFD (rank-1) 1)
0.1169
0.2042
0.1773
0.0274
0.0948
0.1023
0.1169
0.1700
0.1506
0.0274
0.0766
0.0770
0.2042
0.1700
0.1162
0.0948
0.0766
0.0390
0.1773
0.1506
0.1162
0.23
0.0770
0.0390
Table 11:
Comparison between MMFD and MFD on four synthetic graphs (G1, G2, G3, G4 from left right). In each row of each table, for the corresponding graph, the cell of the expected closest graph is marked in gray and the value of the numerically closest graph is highlighted in red.
Dataset
DBLP-vl (N 19456)
REDDIT-MULTI-12K (N 11929)
Metric
ACC
NMI
ARI
ACC
NMI
ARI
WL-subtree kernel
55.04
5.41
0.99
25.37
10.98
6.96
InfoGraph+KM
59.47
11.45
3.56
22.20
8.86
2.70
DCGLC
75.73
22.07
26.49
22.03
3.25
0.23
MMFD
76.13=0.00
20.77:10.00
27.31
20.64
10.04:10.46
4.58
MMFD-KM
7.012=0.00
20.76+10.00
27.09
21.01++0.18
12.03+0.110
5.04
MFD-KD
78.95=0.00
20.8
33.53
22.83+0.448
10.49
7.91
Table 12: Clustering performance DBLP-v1 and REDDIT-MULLI-12K. The best, second-best, and third-best results highlighted in purple, red, and orange, respectively.
Target
μ1
Q
HOMO
LUMO
gap
R2
ZPVE
UO
MPNN
1.22
1.55
1.17
1.08
1.70
3.99
2.52
3.02
enn-s2s
0.30
0.92
0.99
0.87
1.60
0.15
1.27
0.45
MMFD+SVR
0.64
0.34
0.64
0.43
0.43
0.54
0.07
0.41
Table 13: Molecular property prediction on QM9 dataset.
20

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
D. Proof for Theorems
D.I. Proof for Theorme 2.2
Proof. It is obvious that MMFD(G1, G2) 2 O, MMFD(G1 (1, G2) 2M G1), and MMFD(G G1) always
hold. So we only need to prove the triangle inequality. Let R.j = argmin I1;4; RijHt and consider an arbitrary matrix W E MRM Then based on the definition of MMFD, we have
MMFD(G1 G2)
I|p RigHal
<
1 Wuzll
(39)
| - RigHy + Right Wazl
MM
Righell + iaH3 W
M G3) + 1 W Ris/sll
Let W Ris R23. which has solution W RR (Ris))
Rig (Ri)). We also have W w
R5g (R13) Ría (Raa] Lrs which means W R. Now letting the W in (39) be W, we obtain
MMFD(GI, < MMFD(G1, Ga) + 2MFD(G2, G3)
(40)
D.2. Proof for Proposition 2.3
Proof. A complete graph is graph in which each vertex is connected every other vertex. Therefore, for two complete graphs, their self-looped adjacency matrices are A; [1] 2. A, are PSD and rank-1. We have &; [4] xm where is -1 1. That means f4, -1 or +1. The rotation matrix R12 is now just scalar equal -1 or +1. Therefore, ER || R12/el = 0, for any (2).))).
D.3. Proof for Theorem 2.4
Proof. Let Ing be the ni-dimmnsionna vector with all entries and H.j I,, In It is easy show that
MMFD(G1, G2)
1
1
min
I Φ
1
1m,
1
R,
12
RIER
122
1/2
(41)
1 Φ R
71
1
2
(R12, $b (1HH2 1/2
min
A 0
Hn)
+
(A H22)
RiZER
12
n1
This indicates that for MMFD, we need to solve
maximize (R12, Q)
(42)
R1zR
where Q H2H Problem (42) (also (10)) is equivalent to the well-known orthogonal Procrustes problem (Schönemann, 1966) and the optimal solution is
R UQ
(43)
21

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
where UQ. QQ are from the SVD of Q i.e. Q (Q)) QQ with oy (Q) denoting the j-th largest
singular value of Q. Since (Ri2- Q) Σj ( Q), it follows from (41) that
MMFD(GI, G2)
Σ
( (
122
2
12
111112
j
2
Σ
[A4] Juv
Σ
(44)
2
71
1
n1
722
The second equality in (44) holds because <b H is rank-one matrix due H. which made M, Jy ( ai ( H 112 + | P21n,11 V 1, + 1//b,,, 1
In $2 22 ((Eur ((un(AAf)m)) Euv (A (u] 17
D.4. Proof for Theorem 2.5
Proof. For convenience, we denote A, == A, + A, i == 1,2, Given the SVDs A, = U.S.V? and A, U.S.V., we have A = V.S.VT and A V.S.V. Letting E; = A, AA, we have
MMFD C32) MMFD(G1, G2)
A + EiJuo
Σl4g
EzJuv
Σ
luv
[
A EiJuw
Σ AAilur +
2 uv
Σ LAg E1
A + EiJue
Σ [A luv
+
A
2 uuv
Σ [4 +
Ez uv
Σ
[A + Eiluc
>
[A
+
Σ
[
Juve
Σ
1.45
Egl uv
7
uv
uv
Ej
luv
+ Σ
E2
/ 111
v E2
V2
/| + |
V2
E || EElle
(45)
3/4
In the above derivation, the third inequality holds due to the fact that IVF v0l S v1x yl is true for any nonnegative x and y.
Now we need to find bounds for ||E, || F and EZ|
| VV,8, V v.S.V lle
$ V v.š,V. 1 V. v.S.V 1rr
(46)
IV. - V1l. - -..1+/IV |VV - -Vile
22

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
is known that According to the Weyl's inequality for singular values, we have
|S (A.,), |S - (1.) toI(A,), || = || = 1
(47)
SS S (A,)
(48)
According to the Corollary of (Yu al., 2015), a variant of the Davis-Kahan Theorem (Davis & Kahan, 1970), we have
IV. Ville s 2v 2no (A.)
(49)
where 6, min (o,(A,) (x((A))- Combining (46), (48), and (49), we have
||:||r S
(A:) + + vnoi (A,)
S 552 Vio (A:)
(50)
- 6v ( (A)))
where the last inequality used the fact that 01 (A,) > 8G Combing (45) and (50), we arrive at
|MFFDC
MMFD(G1,G2) G2)
V2 1 + (A2))) (A2) 1/2
< 2/4 (6V2nd,
(51)
1 1/2
D.5. Proof for Theorem 2.6
Proof. We have the following derivation for the difference between MMFD and MMFD.
MMFDER R (G1, MMFD(GI,
Auo + (Aeluur 2 -200(( n
[Ailuo + [(Aeluv - 2 20,,(
n
1
> uu
Azluv +2 - A Ailae + ΣIA,
uv
1
A Ailue
+ E - Azlee +2 12 ( E9,(9)
ue
A A
Σl
- A2ll
+2 [0,(Q) Σ (q)
(52)
WP
In the above derivation, inequality (a) holds due to the fact that |/ Vol
| y| is true for any nonnegative and y-
In the theorem, the positive semi-definite assumption on A, indicates that the EVD and SVD of A; are exactly the same, which greatly simplifies the subsequent analysis, e.g., 4; = / and +; / We now derive the upper bound
23

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
for each term in the square root of the last inequality of (52). First, we have
Σ A1 AIl = ||
A1llı
(53)
S n A
A1lle
(A
j=d+1
where the equality (a) holds because A is the best rank-d approximation of A. Similarly, have
E A2l
Sn Σ aA(A2)
(54)
j=d+1
S. 0
Regarding
(2) - [ we S,
E Rdxd j 1, and have
0 0
22
Σ (Q) Σ (
1=1
/=1
0j
H 2
Σ
Jj ( H
1
HV 2
Σ
( V /
(a)
( V HV
Σ 0 ( v HV /3
<
Σ
0j (S
1
12
V HV
-s v HV
S 1/2 HV
0j
a
Σ 0, 22 1 -3//2) V
+ $5/22 H/
HV, (S/ -
j=1
(
"
Σ 0 (1 5/ V HV /22 + + o, VV HV, //222 -//25//3
j=l
(s $1 V HV S 1/2
11, + | 1/2
HV ( 1/2 $
$1/2 $1/2| | 12 212 ///
|H].
///22 $1 | ||Vill2 V2112 || H
no 1/2 1/2 (Az) + no 1/2 (A2) (2
(A1))
(55)
In the derivation above, equality (a) holds because padding matrix with zeros does not change the original singular values, inequality (b) holds according to the Theorem 3.4.5 in (Horn Johnson, 1991), inequality (c) holds according to the Corollary 3.4.3 in (Hom & Johnson, 1991), and inequality (d) holds due to the fact that V1lle = |22ll2 = 1 and ||| = n.
24

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering Combining (52), (53), (54), and (55), we arrive at
LMFDLR(GG G2)
MMFD(G1, G2)
oy(An) +n Σ
1/2 (,(2)) 20 (A2)) + (A2)) (A2))
7
1=d+1
j=d+1
(56)
T2 Σ
(o((A)) + + 221(0 (41))
(A2) (A (A11)
1=++1
This completed the proof.
D.6. Proof for Theorem 2.8
Proof. is obvious that MFD(G), G2) 2 O, MFD((G), MFD(G2, Gi), and MFD G1) 0 always hold. Here
only need to prove the triangle inequality. Let R argmin MMD (Φ; R,, +3) and consider arbitrary matrix
W E MMM Then based on the definition of MFD, we have
MFD G2)
MMD (1), R2)
(57)
MMD 1 W
MMD (b), Rig 1b) + MMD (Ri3 P3, W
When the kernel function used in MMD is rotation-invariant kernel (e.g., polynomial kernel, radial basis function
kernel, sigmoid kernel, or their combination), the computation of MMD (Ri.23, W is primarily based on the inner
product 4 Ris W2 Let W Rí; R2g- which has a solution = (R2s (Ris) = Rig (R2x) We also have
WTW (Rja)) Ria (Raa)* T IM. which means W R. It follows that
(Raa))
D Ris
W = P Ris T 22
(58)
This means
MM3 W MMD (R Pa. 42)
(59)
Combining (59) and (57) with W replaced by W, we obtain
MFD(G1, G2) MMD (4,, R 3) + MMD (R3g P3 $2) MFD(G), Gz) + MFD(G2, G3)
(60)
Currently, we cannot prove that MFD(G2, G2) + G Gg. Therefore, MFD a pseudo-metric.
D.7. Proof for Theorem 2.9
Proof. For convenience, we define
[( == C(R((--)) + (G(t-1), R12 R12 ())
(61)
25

---

Graph Minimum Factorization Distance and Its Application to Large-Scale Graph Data Clustering
where G
VL (t-1)) =33 Enn Oue Quv exp (2 R12 (!01) (1)
(t-1)
) " (2) We have the following derivation
12
((R12) - 1(R12)
Σ aue exp (2 R12 - Σ Bue exp (2
(1)
R (6-11) )
0,81
23 (228 Σ aun exp (33 R2 2 (2!") 0 Φ. T
(1)
R12
R (1-1))
12
ur
Σ aue
exp (23(0 (1) R1 - exp _3( R
(1)
12
0,0
(62)
- (2Bexp (23(6_0)
(1)
R
12 ( T
(t-1)
(1) (22)
RR 1
aue exp (23
R
(1-1)
o!.1)) exp (2 RR22
(t- 1) Φ. ((21)
12
- (1 23 (1) R12
Ri Φ )
11-1))
1)
20
where the inequality holds because Cuav exp (23( ([(6-")(??)) (1o1)) and exp(x) > + for any x.
Now we define
-(R12)=[(R))) = [(R12)
2 |R R R |1?
(63)
which is exactly the right-ham hight-hand-side of (23). Note that C(R (t-)(-))) = E(R = ((R((t-1)
Combining (62) and (63) yields
C(R12) 2 ((R12) = [(R12) + 2
R R1
(64)
As the inequality holds for any R12 E R, letting R12 = =R we have
((R(2) (2 (0) P 1
(t)
(t)
1212"112
(65)
Since ( maximize ((R12,, it holds that Combining (66), (65), and the fact L(R ((R((-1))) we arrive at
((R(()) (t) 2 L(R (
(66)
((R(9) 2 ((R(t")) +
R2 | 12
(67)
This proved part (a) of the theorem.
For part (b) of the theorem, we sum up both sides of (67) from to f and obtain
((R()) C(R
12
P
R
R Rff2"11
16-" 11
(68)
Note that C(R(22 (oc) < co and ((R 2 0, according to the definition of C(R12). Therefore,
0 Σ
|
( 12
R
11
(69)
2
i=
Since p > 0, we conclude from (69) that
(f-1) R
+
0
when i + 00
(70)
12
This completed the proof for part (b) of the theorem.
26


Reviews:
[{"review_id": "9hAAQwmQ27", "reviewer": "Reviewer_8oX9", "summary": "The authors study the clustering problem for graph data. They propose a new measure between two graphs called minimum mean factor distance (MMFD) that serves as a kernel function in graph data clustering. MMFD measure the minimum distance (through rotation by a real orthonormal matrix) of the mean vectors of $\\Phi_1$ and $\\Phi_2$ that can be viewed as the feature vectors of nodes from two graphs $G_1$ and $G_2$, respectively. Two variants of MMFD, named Low-Rank MMFD and MF, are given to lower the time complexity and to fully exploit $\\Phi_1$ and $\\Phi_2$, respectively. The experiments evaluate the effectiveness and efficiency of their methods.\n\n=========================\n\nAfter reading the authors' rebuttals and rethinking the significance of MMFD, I agree that MMFD has a certain value, although I still cannot understand why if the original self-looped adjacency matrices are both PSD, the distance could be zero once the sums of elements in two matrices are equal. In this context, MFD seems more reasonable. I can only say that the instance in Table 2 and the experimental results look convincing. Moreover, I hope the authors can reorganize Section 2.3 due to my concern of W1. I decide to raise my score to 3 (Weak accept). Thank the authors for the responses.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Dear Reviewer,\n\nWe sincerely appreciate your insightful comments. They improved our work a lot.\n\n**To W1:**\n\nPreviously, we focused on deriving from Equation (12) and overlooked Equation (11). Your advice has helped us make Section 2.3 more concise, thereby freeing up more space to supplement other important results or discussions. \n\n**To W2:**\n\nWe are trying our best to make the corresponding descriptions clearer and believe that the issues can be addressed by revision easily. Please refer to our responses to your questions. \n\n**To Other Comments Or Suggestions:**\n\nThanks for your careful reading. We have revised our paper to resolve these issues.\n\n**To Q1:**\n\nAs mentioned in Section 3.2, $\\boldsymbol{\\Phi}_1$ and $\\boldsymbol{\\Phi}_2$ cannot be uniquely determined, so their distances are not unique. \nWe used the idea of ``shortest distance\", which is quite general in real problems. Suppose there are three cities A, B, and C, and there exist multiple paths between each pair of them. To compare the distance between A and B and the distance between A and C, we use the shortest path between A and B and the shortest path between A and C, rather than any other longer paths. \n\nBack to our problem, for a graph $G_i$,  $\\boldsymbol{\\Phi}_i$ and $\\bar{\\boldsymbol{\\Phi}}_i:=\\mathbf{R}_i \\boldsymbol{\\Phi}_i$ are equivalent in terms of representing the adjacency matrix, $i=1,2$. The non-uniqueness of $\\boldsymbol{\\Phi}_i$ leads to a set of possible distances, denoted as $\\mathcal{S}:=\\\\{\\Vert \\text{Mean}(\\mathbf{R}_1\\bar{\\boldsymbol{\\Phi}}_1)-\\text{Mean}(\\mathbf{R}_2\\bar{\\boldsymbol{\\Phi}}_2)\\Vert: \\mathbf{R}_1, \\mathbf{R}_2 \\in \\mathcal{R}\\\\}=\\\\{\\Vert \\mathbf{R}_1\\boldsymbol{\\mu}_1-\\mathbf{R}_2\\boldsymbol{\\mu}_2\\Vert: \\mathbf{R}_1, \\mathbf{R}_2 \\in \\mathcal{R}\\\\}$, where the second equality is due to that we can exchange $\\boldsymbol{\\Phi}_i$ and $\\bar{\\boldsymbol{\\Phi}}_i$. We then define the smallest distance in $\\mathcal{S}$ as the final distance between $G_1$ and $G_2$, i.e., $\\text{MMFD}\\left(G_1, G_2\\right)=\\min (S)$; it is equivalent to optimize $\\mathbf{R}_1$ and $\\mathbf{R}_2$ to minimize $\\Vert \\mathbf{R}_1\\boldsymbol{\\mu}_1-\\mathbf{R}_2\\boldsymbol{\\mu}_2\\Vert$. \n\nPlease feel free to let us know if this explanation is not sufficient.\n\n**To Q2:**\n\n1) Eqs. (3) is the ideal case and usually does not hold for real graphs because their adjacency matrices are often not PSD. Eqs. (7) is based on the PSD $\\mathcal{A}_i^\\phi$ and hence always holds for real graphs. $\\mathcal{A}_i^\\phi$ can be regarded as an PSD proxy or approximation of $\\mathbf{A}_i$. \n\n2) Yes. Your understanding is correct. \n\n3) Yes. In Alg.1, $\\mathbf{A}_i$ is the input, and the augmentation $\\mathcal{A}_i^\\phi$ is constructed by line 6 or line 8.\n\n4) Does the \"augmentation\" you mentioned mean the one defined in equation (5)? In the algorithm, we use (5) rather than (4), which is stated in line 171 and line 4-8 of the algorithm. If $\\mathbf{A}_i$ is PSD, $\\mathcal{A}_i^\\phi$ is unnecessary (in this case $\\mathbf{A}_i=\\mathcal{A}_i^\\phi$). However, PSD  $\\mathbf{A}_i$ is rare. For instance, in the dataset AIDS, the number of PSD $\\mathbf{A}_i$ is **ZERO**.\n\n**To Q3:**\n\nWe used the sklearn function: sklearn.utils.extmath.randomized$\\_$svd(M, n$\\_$components=d, random$\\_$state=0). This can be found in the code of the supplementary material. We added these details to the revised paper.\n\n**To Q4:**\n\nWe assume $n_1=n_2=n$ so as to simplify the notations in many formulas or results such as (8), (12), (16), Theorem 2.3, and Theorem 2.4. In the definition of MMFD, i.e. Definition 2.1, we can replace $n$ with $n_1$ and $n_2$ without influencing the meaning of the definition, since it is based on the mean vectors.\nTherefore, we claimed \"without loss of generality\". We will use $n_1$ and $n_2$ throughout the paper if you think it is necessary.\n\nRegarding the MMFD between two complete graphs of different sizes, we provide the following theoretical proof. \n\nA complete graph is a graph in which each vertex is connected to every other vertex. Therefore, for two complete graphs, their self-looped adjacency matrices are $\\mathbf{A} _i=[1] _{n _i\\times n _i}$, $i=1,2$. \n$\\mathbf{A} _i$ are PSD and rank-1. We have $\\boldsymbol{\\Phi} _i=s\\cdot[1] _{1\\times n _i}$, where $s$ is $-1$ or $1$. That means $\\boldsymbol{\\mu} _i=-1$ or $+1$. The rotation matrix $\\mathbf{R} _{12}$ is now just a scalar equal to $-1$ or $+1$. Therefore, $\\min _{\\mathbf{R} _{12}\\in\\mathcal{R}} \\Vert \\boldsymbol{\\mu} _1-\\mathbf{R} _{12}\\boldsymbol{\\mu} _2 \\Vert\\equiv 0$, for any $(n _1,n _2)$.\n\nWe added the above proof to the revised paper.\n\n**To Q5:** \n\nSorry for the confusion. The superscript 0.5 is the square root. We visualize the square root of the distance to make the visual difference clearer. As you know, in many studies, people use a log scale to show the results. Here, we use a square-root scale.\n\n**Thank you again for reviewing our paper. We are looking forward to your feedback.**", "claims_and_evidence": "All claims are supported by evidence, but some descriptions are not so clear. Please refer to the questions below.", "methods_and_evaluation_criteria": "Yes, I think the methods and evaluation criteria make sense.", "theoretical_claims": "I have checked the proofs in the main text. Some parts of the derivation process on the basic MMFD are lengthy and redundant, which makes not too much sense. Please refer to the weakness.", "experimental_designs_or_analyses": "Yes, I have checked the soundness/validity of experimental designs and analyses.", "relation_to_broader_scientific_literature": "This paper fits in the study line of clustering of graphs. It proposes a new kernel function and some variants, which is a contribution to graph clustering and kernel methods.", "essential_references_not_discussed": "I think the related works included in the paper have been essential to understanding the key contributions.", "other_strengths_and_weaknesses": "S1. The MMFD measure performs well in evaluation. The toy example in Table 2 is intuitive and convincing.\n\nW1. The authors have spent much space on showing that MMFD is only related to $\\mathcal{A}_i^\\phi$’s. But it can be observed easily from Eq. (10) or Eq. (11) that MMFD measures actually the difference of the lengths of $\\mu_1$ and $\\mu_2$, that is the absolute value of $\\Vert\\mu_1\\Vert-\\Vert\\mu_2\\Vert$ (when they are parallel by rotation). A plain expansion of $\\left| \\Vert\\mu_1\\Vert-\\Vert\\mu_2\\Vert \\right|$ yields Eq. (16).\n\nW2. There are a lot of unclear descriptions in the main text. Please refer to the questions below. Because of this, I don’t think this paper is suitable for publication with present version.", "other_comments_or_suggestions": "1. Please give the full names of EVD and SVD when they appear for the first time.\n2. Line 206, Column 2, please clarify the inner product $\\langle A, B \\rangle=\\text{trace}(A^T B)$.\n3. “$i=1, 2$” should be deleted in Line 134, Column 2.", "questions_for_authors": "1. Line 212, Column 1, why do you need to make the distance as small as possible and call it a natural principle? This seems the core of MMFD, and I can feel it to some extent, but need more explanations.\n2. What is the difference between Eqs. (3) and (7)? Do you mean that if we have the PSD matrices $A_i$’s, then it’s good, but in real applications we do not have, so you need to construct the PSD matrices $\\mathcal{A}_i^\\phi$’s that approximate of $A_i$’s? Are $A_i$ and its augmentation PSD in Alg. 1? Is $\\mathcal{A}_i^\\phi$ necessary when $A_i$ and its augmentation are PSD?\n3. How do you perform the randomized SVD?\n4. You have assumed $G_1$ and $G_2$ of the same size in Line 134, Column 1. But it seems that $n_1$ and $n_2$ could be different in Alg 1. Do you define MMFD between two graphs of different sizes as that in Line 10 of Alg. 1? Why can you define it like that? Why can you say assuming $n_1=n_2$ is without loss of generality? Why is MMFD between two complete graphs of different sizes (Line 195, Column 2) zero?\n5. What is the $0.5$ in Line 296, Column 1? The probability in randomized SVD? What does it mean?", "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": "", "extra_scores": {"ethical_review_concerns": "No ethical review concern."}}, {"review_id": "bcylehcvf4", "reviewer": "Reviewer_v4JQ", "summary": "This paper introduces a new measurement, named MMFD, for comparing and clustering graph data. By considering the adjacency matrix of graph as a kernel matrix, MMFD transforms the graph comparison problem into distribution comparison. \nThis paper then proposes a low-rank approximation and a generalized version algorithm for large graph efficient clustering.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Dear Reviewer,\n\nIt is our great honor to receive your positive assessment. Our responses to your questions are as follows.\n\n**To Q1:**\n\nYes. Take $G_1$ and $G_3$ in Table 2 of our paper as an example, where $\\text{MMFD}(G_1,G_3)=0.1598$. We add one additional node to $G_1$ and the additional node is only connected with one node. The same operation is conducted on $G_2$. Then we get two noisy graphs $G_1'$ and $G_3'$, where the noises are very strong because the graphs are too small. We compute the low-rank MMFD (with different rank) between $G_1'$ and $G_3'$. The difference between $\\text{MMFD} _{\\text{LR}}(G _1',G _3')$ and $\\text{MMFD}(G _1,G _3)$ are shown in the following table. We see that when the rank decreases from 6 to 3, the difference becomes smaller. This demonstrates the denoising effect. \nAdditionally, as shown in Table 7 of our paper, on dataset REDDIT-MULTI-5K, using a lower rank (but not too low) yields a better clustering performance, which also demonstrates the potential denoising effect.\n\n\\begin{equation}\n\\begin{matrix}\n\\hline\n\\text{rank} & \\text{full} & 5 &4 &3 &2 &1\\\\\\\\ \\hline\n    |\\text{MMFD}(G_1,G_3)-\\text{MMFD}_{\\text{LR}}(G_1',G_3')| & 0.073 & 0.070& 0.049& \\textbf{0.044} & 0.046  & 0.047  \\\\\\\\     \\hline\n\\end{matrix}    \n\\end{equation}\n\n**To Q2:**\n\nOur MMFD is mainly designed for comparing the adjacency matrices of two graphs, though it is able to utilize node attributes, as explained in Section 2.6. To apply MMFD to graphs with incomplete node attribute matrices, we need to do missing data imputation (e.g. matrix completion) in advance. Therefore, MMFD cannot directly handle missing attributes. However, here we provide a possible approach. Let $\\tilde{G}_1$ and $\\tilde{G}_2$ be the two augmented graphs using node attributes, which is explained in Section 2.6. We just denote the missing values of node attribute matrices as $x_1$ and $x_2$, respectively, and write $\\tilde{G} _1=\\tilde{G} _1(x _1)$ and $\\tilde{G} _2=\\tilde{G} _2(x _2)$. Then, according to the definition of MMFD, we can solve $\\min _{x _1,x _2}\\text{MMFD}(\\tilde{G} _1(x _1),\\tilde{G} _2(x _2))$ to impute the missing values and get the minimum distance. Nevertheless, the optimization and effectiveness need further investigation, which could be a future work.\n\n**To Q3(a):**\n\nIn Table 3 of our paper, we compared our MMFD with four pure UGRL methods including InfoGraph, GraphCL, JOAO, and GWF and two clutering-oriented UGRL methods including GLCC and DCGLC. On dataset AIDS, the best NMI of UGRL methods is $76\\%$, while the NMI of our MMFD is $88\\%$, meaning that the gap is significantly large. For convenience, we calculate the average of ACC, NMI, and ARI of each method and take the average over the 2 datasets (PROTEIN and AIDS), the results are compared in the following table. Our MMFD and MFD outperformed the best competitor by $6\\%$.  \n\n\\begin{equation}\n \\begin{matrix}\n \\hline\n\\text{Method} &\\text{InfoGraph} & \\text{GraphCL} & \\text{JOAO} & \\text{GWF} & \\text{GLCC} & \\text{DCGLC} & \\text{MMFD} & \\text{MFD} \\\\\\\\\n\\text{Metric (\\\\%)} &42 &40 &17 &35 &20 &47 &\\textbf{53} &\\textbf{54} \\\\\\\\ \n\\hline \n\\end{matrix}   \n\\end{equation}\n\nWe also compare the time costs of DCGLC (SOTA of graph clustering) and our MMFD-KM and MFD-KD on dataset REDDIT-12K in the following table.\n\n\\begin{equation}\n \\begin{matrix}\n \\hline\n\\text{Method} &\\text{DCGLC} & \\text{MMFD-KM} & \\text{MFD-KD} \\\\\\\\\n\\text{Time cost} & 21\\ hours & 2.2\\ minutes & 3\\ hours \\\\\\\\ \n\\hline \n\\end{matrix}   \n\\end{equation}\n\nBesides the advantage of higher efficiency and accuracy, our MMFD has nearly no hyperparameter to tune (it is not sensitive to $d$), while deep learning methods have quite a few hyperparameters that are very difficult to tune in unsupervised learning. \n\n**To Q3(b):**\n\nRegarding chemical molecular property prediction, we combine MMFD with support vector regression and call this combination MMFD+SVR. We apply it to the QM9 dataset. Since kernel SVR is not scalable to very large datasets, we only use 25000 graphs for training and 5000 graphs for testing. Some results (space limitation) of MAE are in the following table, where the classic MPNN and enn-s2s [1] are compared. We see MMFD+SVR works well. It still has a lot of room for improvement, e.g., by using attributes more effectively, using the extension MFD, or using more training data.\n\n\\begin{equation}\n \\begin{matrix}\n \\hline\n\\text{Target} & \\mu & \\alpha & \\text{HOMO} & \\text{LUMO} & \\text{gap} & \\text{R2} & \\text{ZPVE} &\\text{U0}\\\\\\\\ \\hline\n\\text{MPNN}& 1.22 & 1.55 & 1.17 & 1.08 & 1.70 &3.99 &2.52 & 3.02\\\\\\\\ \n\\text{enn-s2s} & \\textbf{0.30} & 0.92 & 0.99 & 0.87& 1.60& \\textbf{0.15} & 1.27& 0.45\\\\\\\\\n\\text{MMFD+SVR} &0.64 & \\textbf{0.34}& \\textbf{0.64}& \\textbf{0.43}& \\textbf{0.43} & 0.54 & \\textbf{0.07}&\\textbf{0.41}\\\\\\\\\n\\hline \n\\end{matrix}   \n\\end{equation}\n[1] Gilmer et al. Neural Message Passing for Quantum Chemistry.\n\n**Thank you again. We are looking forward to your feedback.**", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I didn't check the proofs for the theoretical claims.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to the broader scientific literature through existing graph comparing methods. The paper builds on past research while offering improvements, particularly in efficiency and scalability.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths\n- highly scalable and suitable for large datasets.\n- superior clustering performance, as evidenced by the experiments on several real-world datasets, outperforming competitors in terms of clustering accuracy and time.", "other_comments_or_suggestions": "No", "questions_for_authors": "- As mentioned by the authors, although the low-order approximation leads to some loss of information, it has a denoising effect. I'm interested if there are relevant toy experiments proving this yet.\n- Can MMFD cope with missing attributes?\n- MMFD is highly efficient and theoretically guaranteed. I would like to know how much its performance gap is compared with UGRL? In addition, I would like to know about the real application tasks of graph comparison, such as chemical molecular property prediction?", "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": "", "extra_scores": {}}, {"review_id": "eWI2KmE2X5", "reviewer": "Reviewer_rKce", "summary": "The paper studies graph distance and graph clustering. It introduced a minimum mean factor distance (MMFD) between graphs and its extensions such as low-rank MMFD, MMFD-KM, and MFD.Theses methods outperformed many baselines on large-scale graph datasets such as REDDIT-5K.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "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": "Dear Reviewer,\n\nWe are grateful for your acknowledgment of our work. Our responses to your comments are as follows.\n\n**To W1:**\n\nThanks for pointing it out. Actually, we have the time cost comparison on much larger datasets (e.g. graphs with 10000 nodes). They are in Table 8 of Appendix C4. By the way, some baselines such as Entropic GWD (shown by Table 2) are too time-consuming and hence cannot be applied to very large datasets such as the two REDDIT datasets.\n\n**To W2:**\n \nThe settings of the hyperparameters are in Appendix B.2. Some results of hyperparameters are in Tables 6 and 7. For instance, our MMFD is not sensitive to the factorization dimension $d$. We will provide more analysis on them. \n\n**To Q1:**\n\nIn Table 1, K is the number of clusters and T is the number of iterations in the clustering algorithm MMFD-KM. We are sorry about the absence of the description.\n\n**To Q2:**\n\nWe think our methods can be applied to directed graphs, though we haven't conducted any experiments related to directed graphs. We may consider the following strategy. Given a directed graph, with adjacency matrix $\\mathbf{A}$, which is asymmetric, we perform SVD $\\mathbf{A}=\\mathbf{USV}^\\top$ and generate the following augmented adjacency matrix $\\bar{\\mathbf{A}}=[\\mathbf{USU}^\\top, \\boldsymbol{0};\\boldsymbol{0},\\mathbf{VSV}^\\top]$. $\\bar{\\mathbf{A}}$ is PSD and hence can be used in our methods such as MMFD and MFD.\n\n**To Q3:**\nDo you mean the $\\gamma$ in (20)? In all experiments, we set it to $1 /(5 u)^2$, where $u$ denotes the average MMDF (or MMD, GWD, and GED) between all graphs. This setting was explained in line 837, Appendix B2. \n\n**To Q4:**\n\nThe following table presents some results of time cost (second) comparison on very large graphs. We can see that the Shortest-path kernel is most time-consuming, while our MMFD is always the most efficient one.\n\\begin{equation}\n    \\begin{matrix}\n\\hline n \\text{(number of nodes)} & 1000 & 2000 & 4000 & 6000  & 8000 & 10000 & 20000 & 30000 \\\\\\\\\n\\hline \\text { Shortest-path kernel }  & 4.853 & 25.8  & 178.7  & 524.8  & 1125.0 & 2022.4 & - & - \\\\\\\\\n\\text {WL subtree kernel}  & 0.393 & 1.5 &  6.6 & 15.3  & 27.4 & 43.4 & 182.6 & 449.7 \\\\\\\\\n\\text {entropic Gromove Wasserstein}  & 0.367 & 0.5 &  2.3 &  6.4  & 12.8 & 21.9 & 169.1 & 579.7 \\\\\\\\\n\\text {MMFD}_{\\text{LR}} & \\mathbf{0 . 0 9 5} & \\mathbf{0 . 3} & \\mathbf{1 . 1} &  \\mathbf{2 . 1} & \\mathbf{3 . 7} & \\mathbf{6 . 4} & \\mathbf{2 9 . 9} & \\mathbf{7 8 . 8} \\\\\\\\\n\\hline\n\\end{matrix}\n\\end{equation}\n\n\n**To Q5:**\n\nThanks for pointing out the mistakes. We have corrected them.\n\n**To Q6:**\n\nOur MMFD has only one hyperparameter $d$. As shown in Table 7, we compared the performance of MMFD with different $d$ on datasets PROTEINS and REDDIT-MULTI-5K. On PROTEINS, a larger $d$ is better since most graphs are very small. On REDDIT-MULTI-5K, A smaller $d$ can improve the clustering performance slightly, since most graphs are very large. In sum, MMFD is not sensitive to $d$.\n\nRegarding the extension method MFD, besides $d$, there is a hyperparameter $\\rho$ in the optimization algorithm and a hyperparameter $\\beta$ in the kernel function.  Figure 3 shows that the optimization is not sensitive to $\\rho$. For $\\beta$, we just set it as the inverse of the squared average distance in the experiments, which works well.\n\n**To Q7:**\n\nIn the revised paper, we have added more discussion about the results. Regarding the improvement on the dataset AIDS, one possible reason is that the distribution information in the dataset is more useful than other datasets, and our methods MMFD and MFD can effectively exploit the information.\n\n**We thank you again for your comments and time. We are looking forward to your response.**", "claims_and_evidence": "The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation make sense.", "theoretical_claims": "Yes, I checked the proofs for theoretical claims such as Theorems 2.2 and 2.3.", "experimental_designs_or_analyses": "Yes, I checked the experimental settings, evaluation metrics, and analysis.", "relation_to_broader_scientific_literature": "Comparing graphs is a fundamental problem in machine learning.", "essential_references_not_discussed": "The literature review seems complete.", "other_strengths_and_weaknesses": "Strengths:\n\n* The paper proposed an effective distance metric MMFD for comparing graphs. MMFD has a closed-form solution and hence is much more efficient than other methods such as graph kernels, GWD, and GED. \n\n* Some extensions such MMFD-KM and MFD were developed.An approach to incorporating node attributes was provided.\n\n* The paper has some theoretical results to support the proposed methods.\n\n* In the experiments, the proposed methods outperformed other methods with a large margin. \n\nWeaknesses:\n\n* The time cost comparison is only conducted on smaller datasets.In Table 4, the two datasets are not large. \n\n* The setting or analysis for the hyperparameters of the proposed methods seems missing.", "other_comments_or_suggestions": "See my questions.", "questions_for_authors": "* In Table 1, what do K and T mean?\n\n* Are the proposed methods applicable to directed graphs? I am just curious about this because Theorem 2.2 mentioned “undirected graphs”.\n\n* In (20), how to set $\\lambda$ for graph classification and spectral clustering?\n\n* It is better to show some time cost comparison on larger datasets.\n\n* In the caption of Table 3, the explanation for the colored text seems wrong. The purple color corresponds to best result in each case?\n\n* How do the hyperparameters of the proposed methods affect their performance?\n\n* It is suggested to provide more discussion about the experimental results in Table 3. For instance, on the AIDS dataset, the NMI and ARI of the proposed methods are 10 or 20 points higher than other methods. What is the possible reason for this phenomenon?", "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": "", "extra_scores": {}}, {"review_id": "a2VMCyrIla", "reviewer": "Reviewer_wUZK", "summary": "The work proposed a distance metric MMFD between graphs through comparing distributions and showed that MMFD is a pseudo metric and has a closed-form solution. The work also proposed several variants of MMFD and analyzed the properties theoretically. The proposed methods were compared with graph kernels, graph neural networks, and other distances in synthetic data analysis and graph clustering and showed improved performance.\n\n## update after rebuttal\nI appreciate the details and clarifications provided by the authors. I have no more concerns and will keep the rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Dear Reviewer,\n\nWe sincerely appreciate your recognition of our work. Our responses to your comments are as follows.\n\n**To Q1:**\n\nIn a dataset, the graphs belonging to the same cluster are usually similar to each other. Therefore, for a pair of very similar graphs, denoted as $G_1$ and $G_2$, we can regard $G_2$ as a perturbed graph from $G_1$， and vice versa. Therefore, $\\text{MMFD}(G_1,G_2)$ will be small. It also means that within-cluster distances are small, which is important for downstream tasks.\n\n**To Q2:**\n\nYour this question is the same as the question 4 asked by Reviewer 8oX9. We provide the following theoretical justification.\n\nA complete graph is a graph in which each vertex is connected to every other vertex. Therefore, for two complete graphs, their self-looped adjacency matrices are $\\mathbf{A} _i=[1] _{n _i\\times n _i}$, $i=1,2$. \n$\\mathbf{A} _i$ are PSD and rank-1. We have $\\boldsymbol{\\Phi} _i=s\\cdot[1] _{1\\times n _i}$, where $s$ is $-1$ or $1$. That means $\\boldsymbol{\\mu} _i=-1$ or $+1$. The rotation matrix $\\mathbf{R} _{12}$ is now just a scalar equal to $-1$ or $+1$. Therefore, $\\min _{\\mathbf{R} _{12}\\in\\mathcal{R}} \\Vert \\boldsymbol{\\mu} _1-\\mathbf{R} _{12}\\boldsymbol{\\mu} _2 \\Vert\\equiv 0$, for any $(n _1,n _2)$.\n\n**To Q3:**\n\nThis is an insightful question. Yes, MMD is always larger than or equal to MMFD. \nIn addition to the listed two issues of SVD, it is indeed possible that the order of singular values has some error caused by noise. We will include this in the revised paper. Regarding $\\mathbf{R} _{12}$, we take the graphs $G_1$ and $G_7$ in Table 2 of our paper as an example. Let $d=4$, we have the following $\\mathbf{R} _{12}$. We can see that it is quite different from an identity matrix or sign-flip matrix.\n\\begin{equation}\n \\begin{matrix}\n \\hline\n     0.9985   & 0.0000  & -0.0087 &  -0.0538 \\\\\\\\\n   -0.0001    &1.0000   &-0.0005  & -0.0001 \\\\\\\\\n    0.0087   & 0.0005   & 1.0000   & 0.0001 \\\\\\\\\n    0.0538   & 0.0001   &-0.0006   & 0.9985  \\\\\\\\ \\hline\n\\end{matrix}   \n\\end{equation}\n\n**To Q4:**\n\nThe time complexity of MFD is $\\mathcal{O}\\left(n^2 \\log (d)+d^2 n+T\\left(d^3+d n^2\\right)\\right)$, where $n$ is the number of nodes, $d$ is the rank, and $T$ is the number of iterations in the optimization. This complexity is much higher than that of MMFD and is mainly due to $Tdn^2$. Actually, we have a faster MFD based clustering algorithm, called MFD-KD. The time complexity of MFD-KD is $\\mathcal{O}\\left(n^2 \\log (d)+d^2 n+T\\left(d^3+d n_s^2\\right)\\right)$, where $n_s$ is much less $n$.\n\n**To Q5:**\n\nThanks for the question. The tiny time costs of WL kernel and MMFD are due to the following reasons:\n * In Table 4, we recorded only the time costs of computing the distance or similarity matrices on the two datasets, which was declared in line 432, column 2. That means we didn't include the time cost of spectral clustering. \n * The experiments were conducted on a computer with Intel Core i9-12900K and RAM 64GB, which has a quite good CPU. \n * The two datasets are not too large. \n * WL kernel and MMFD are both efficient.\n\nThese four reasons make the time costs of WL kernel and MMFD less than one second. We assure that the result is correct and reproducible.\n\n**Thank you again for your comments and suggestions. We are looking forward to your feedback.**", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I briefly checked the proof of the theorems.", "experimental_designs_or_analyses": "Yes. The design and analysis of graph comparing and clustering are reasonable.", "relation_to_broader_scientific_literature": "The proposed distances and clustering algorithms are useful.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1.The algorithms proposed in the paper are novel and elegant.\n2.The presentations like the figures and tables are nice.\n3.The proposed methods are compared with many baselines and the improvements are remarkable. \nWeaknesses:\nThe explanations for several claims or results are not sufficient. Please refer to my questions.", "other_comments_or_suggestions": "The paper will be stronger if my questions could be addressed successfully. In addition, the author may consider shortening the introduction section or other sections and move some results from the appendix to the main paper.", "questions_for_authors": "1.In the text below Theorem 2.3, it was said that “...where MMFDs between graphs in the same cluster should be small...” How does this relate to the perturbations?\n2.On page 4, it is not clear why the MMFD between two complete graphs is always zero. Could the authors provide more explanation or theoretical justification?\n3.Section 2.5 compared MMFD with MMD. Is MMD always greater than MMFD? In addition to the listed two issues of SVD, is it possible that the order of singular values has some error caused by noise? Could the authors provide show some examples of matrix R12? Readers would like to see how R12 differs from an identity matrix or sign-flip matrix, although the final computation of MMFD is not explicitly related to R12.\n4.As the MFD proposed in Section 2.8 has no closed-form solution, it is necessary to analysis its time complexity.\n5.In Table 4, it is surprising that the time costs of the WL kernel and MMFD are less than one second, as the complexity is $O(N2)$ if I understand correctly. Could the authors provide more explanation about these tiny time costs?", "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": "", "extra_scores": {"ethics_expertise_needed": ["Other expertise"]}}]

Author rebuttal:

Meta-review: This paper presents efficient approaches for evaluating graph similarities using the minimum mean factor distance. As all reviewers have provided positive evaluations, I recommend acceptance of the paper.
Decision: Accept (poster)