Unsupervised Multiple Kernel Learning for Graphs via Ordinality Preservation
Authors: Yan Sun
Stanley Kok
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Kernel; Unsupervised Learning; Multiple Kernel Learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: UMKL-G combines multiple graph kernels in an unsupervised way, preserving the ordinal relationships between graphs.

Abstract: Learning effective graph similarities is crucial for tasks like clustering, yet selecting the optimal kernel to evaluate such similarities in unsupervised settings remains a major challenge. Despite the development of various graph kernels, determining the most appropriate one for a specific task is particularly difficult in the absence of labeled data. Existing methods often struggle to handle the complex structure of graph data and rely on heuristic approaches that fail to adequately capture the global relationships between graphs. To overcome these limitations, we propose Unsupervised Multiple Kernel Learning for Graphs (UMKL-G), a model that combines multiple graph kernels without requiring labels or predefined local neighbors. Our approach preserves the topology of the data by maintaining ordinal relationships among graphs through a probability simplex, allowing for a unified and adaptive kernel learning process. We provide theoretical guarantees on the stability, robustness, and generalization of our method. Empirical results demonstrate that UMKL-G outperforms individual kernels and other state-of-the-art methods, offering a robust solution for unsupervised graph analysis.

Published as a conference paper at ICLR 2025
UNSUPERVISED MULTIPLE KERNEL LEARNING FOR GRAPHS VIA ORDINALITY PRESERVATION
Yan Sun Stanley Kok
School Computing, National University of Singapore, Singapore yansung comp. nus. edu.sg sg skckě "kck@comp... nus eduu sg
ABSTRACT
Learning effective graph similarities is crucial for tasks like clustering, yet se- lecting the optimal kernel to evaluate such similarities in unsupervised settings remains a major challenge. Despite the development of various graph kernels, de- termining the most appropriate one for specific task is particularly difficult in the absence of labeled data. Existing methods often struggle to handle the complex structure of graph data and rely on heuristic approaches that fail to adequately cap- ture the global relationships between graphs. To overcome these limitations, we propose Unsupervised Multiple Kernel Learning for Graphs (UMKL-C)) model that combines multiple graph kernels without requiring labels or predefined local neighbors. Our approach preserves the topology of the data by maintaining or- dinal relationships among graphs through a probability simplex, allowing for a unified and adaptive kernel learning process. We provide theoretical guarantees on the stability, robustness, and generalization of our method, Empirical results demonstrate that UMKL-G outperforms individual kernels and other maate-ofthhr art methods, offering robust solution for unsupervised graph analysis.
INTRODUCTION
Graphs are ubiquitously used to represent structured data in diverse domains such bioinformat- ics, chemoinformatics, and social networks. Learning a semantically meaningful similarity between graphs is crucial it captures the essential characteristics and functional properties that distinguish one graph from another. For example, in bioinformatics, the secondary structure of a protein can be regarded as graph where nodes are atoms and edges are chemical bonds. Learning seman- tic similarities between such graphs enables more effective graph-level tasks, such determining enzymatic activity, where subtle structural variations play a key role.
Kernel methods are naturally suited to measuring graph similarity. Graph kernels with the R- convolution framework recursively break down graphs into substructures like paths (Borgwardi & Kriegel| 2005), graphlets (Shervashidze et al.) 2009), walks (Vishwanathan al., (010). and subtrees (Shervashidze et al. 2011)) - and then compare these substructures between two graphs KKiege al. 2018). In addition, there are other types of graph kernels developed from the prin- ciples of optimal assignment (Fröhlich et al.] 20055 Kriege et al. 2016), optimal transport distance Togninalli al. 2019 Chen al.) 2022), and maximum mean discrepancy (Sun & Fan 2023).
Given the abundance of graph kernels, it is not straightforward to determine which one is the most suitable for specific task and dataset. Some works try determine the expressiveness of candidate kernels theoretically (Kriege et al.) 2018)) Oneto et al. 2017).. However, it is still not clear which one would empirically perform the best different from those encountered in previous studies. In reality, the performance of graph kernels varies on case-by-case basis (Kriege et al., 2020). For instance, the Weisfeiler-Lehmann (WL) kernels are theoretically less expressive than the Shortest Path (SP) graph kernels as WL kernels fail to distinguish connectivity (Kriege al. 2018). However, empirically, WL kernels perform better in terms of classification accuracy in certain chemical compound datasets (Kriege et al.) 2020). Similarly, the simple Random Walk (RW) kernels outperform Graphlet kernels (Borgwardt et al.
novel setting, where graphs are not labeled and are
Our code is available at httph::/ggtthbb.co sun-x/Rnsemb) 1e

---

Published as a conference paper at ICLR 2025
2020), even though RW kernels cannot identify triangle freeness (Kriege al. 2018 There several possible reasons for this phenomenon ranging from the match between the graph kernels and the graph structure in particular dataset to the number of isomorphic graphs in the dataset that belong to different classes (Nikolentzos et al., 202T). Given that no single graph kernel dominates all downstream tasks, intriguing question emerges:
Is it possible to ensemble individual graph kernels and perform well in an unsupervised setting?
If so, then we can achieve better performance in graph-level tasks by learning the optimal kernel values in a data-driven manner. To solve this problem, an intuitive solution is to learn an optimal kernel from multiple graph kernels. Previous studies in Multiple Kernel Learning (MKL) provide a supervised framework to learn the kernel directly from data (Gönen & Alpaydın 2011). Specif- ically, MKL leverages pre-specified weak kernels and labels of data points to obtain the optimal kernel as weighted combination of the weak ones. It is worthwhile to note that the existing MKL algorithms fail in the unsupervised setting (c.g.. graph-level clustering, which common in many real-world graph applications (Ju et al. 2023)). Although there exists unsupervised algorithm for MKL (Zhuang et al.) (01T)) based on the locality preserving principle, is designed for Euclidean complex, non-Fuclidean data type that captures both individual node features and their pairwise relationships. Noticing these limitations, |Mariette & Vila--iiaaanex (2018) proposes sparse-UMKL, which aims to preserve local geometry by con- structing k-nearest neighbors. However, this method falls short in practice, as its heuristic approach to approximating neighbors leads to poor generalization in empirical experiments. In summary, given the current algorithms,, we conclude the following for unsupervised MKL: ① preserving the data topology exsential, and achieving effective generalization for gruph data remains a sig- nificant challenge. These insights motivate to directly leverage the ordinal relationship between graphs using kernel values, without the need for learning explicit graph representations.
data. This limits its applicability for graphs,
Input
UMKL-G
g = w/o labels
Preserve Ordinal Relationships
BlueQ Red P As
G
kij > kis
St
w" = arg min [L)
K. [k. (m(m) M m=
03
{q} E AN
[pi) E A
with hyperparameters
13
h
Gj
Kernel Weights
(m)
R M
kij
G.
h (M)
Bey (G.
Gr
Figure 1: Overview of the UMKL-G Model. The model starts with N input graphs, which are processed through M multiple graph kernels with configurable hyperparameters. The learnable kernel weights w combine the kernels into an optimal composite kernel i while preserving the ordinal relationships between graphs. Each graph is represented as a point on the simplex, where Q is the initial probability distribution of graph similarities and P is the powered distribution that emphasizes stronger relationships. The goal is to adjust the positions of these points in the simplex to preserve both local and global graph structures inferred from k. ensuring effective performance in tasks such as clustering. As an illustration, the probability simplex A (N 3) at the center shows the optimization process, indicated by the direction of the arrow.
2

---

Published as a conference paper at ICLR 2025
In this work, we develop a simple yet effective approach to learning optimal kernel for graphs in an unsupervised manner and name it Unsupervised Multiple Kernel Learning for Graphs (UMKL-G; illustrated in Figure D. Our proposed method automates the procedure to select and combine different types of graph kernels as well as configure their respective hyperparameters. Our empirical results show the composite graph kernel learned by UMKL-G has better performances compared to individual kernels and state-of-the-an baseline algorithms in the graph-level clustering task. The main contributions of this work are summarized as follows:
We propose UMKL-G, an efficient unsupervised method that combines multiple graph ker- nels by preserving topological structures through ordinal relationships of the kernel values.
We provide theoretical guarantees and their empirical validation. such as Lipschitz continu- ity for smooth optimization, robustness to kernel perturbations, and generalization stability, ensuring that the algorithm effectively adapts to diverse, noisy, and unseen data.
We empirically evaluate UMKL-G, showing its effectiveness over individual graph kernels and three state-of of-the-rrtttttt baselines on eight benchmark datasets.
2 RELATED WORK
Graph Kernels. Much existing research on graph kernels can be seen as feature engineering efforts, focusing on identifying the most suitable graph aspects for defining graph similarity (Borgwardi et al. 2020). The initial wave of graph kernels, termed as R-convolution, concentrated on decom- posing graphs into smaller, easily comparable substructures. For instance, random walk kernels, in- troduced by Gärtner et al. (2003), count matching random walks in two graphs; shortest path kernels invented by (Borgwardt& & Kriegel (205)) count pairs of shortest paths with the same length; graphlet kernels developed by SShervashidze et al. (2009) further contributed by counting occurrences of small subgraphs. efficiently capturing local structures; and Ceisfeiler-Lehman (WL) graph kernels pro- posed by (Shervashidze et al., 2011), iteratively refine node labels to capture larger substructures, enhancing their discriminative power by capturing edge attributes and multi-resolution structures. Additionally, the concept of optimal matching has been explored in various graph kernels, ranging from the optimal assignment kernel (Fröhlich et al.) (005) to the Weisfeiler-Lehmade optimal assign- ment kernel (Kriege et al., 2016). A notable trend in recent research has been the modification of Weisfeiler-Lehman (WL) kernels using Wasserstein distances (Togninalli et al.) 2019 Chen et al., 2022). Togninalli et al. (2119) integrate the Wasserstein distance into the WL framework, allowing for a more refined comparison of graphs, particularly those with continuous node attributes. Chen al. (2022) propose a novel concept of WL distance, a polynomial
is more sensitive to subtle graph differences than traditional WL. methods. computable metric that graph kernels, such as deep graph kernels by /anaarda & Vishwanathan (2015), combine traditional methods with neural networks to learn latent substructure representations, and GCN-based kernels (Ye al. 2020) integrate graph convolutional networks to capture complex, high-level features. [Sun & Fan (222)) propose deep graph kernel using maximum mean discrepancy (MMD-GF that inte- grates graph kernel learning with graph neural networks, achieving promising performance in graph classification and clustering tasks. In this abundance of graph kernels, each kernel has its strengths and limitations (Borgwardt et al.) (020). both of which are the results of an inherent trade-off be- tween exhaustive feature extraction and computational feasibility, Additionally, many graph kernels (WL) kernels
are restricted by the attributes of graphs they can handle, e.g., Weisfeiler- struggle to distinguish node and edge attributes. In this study, we utilize graph kernels regardless of their time complexity or graph assumptions, provided their kernel matrices can be precomputed. In this study, we concentrate on non-deep kernels, but our method applies to other graph kernels without any loss of generality.
Multiple Kernel Learning. Multiple Kernel Learning (MKL) (Lanckriet et al., 2004) aims to learn a linear combination of set of predefined weak kernels to identify a good kernel for given problem. MKL algorithms have been developed for supervised, semi-supervised and unsupervised learning. In the supervised framework, MKL algorithms are supported by several theoretical results that bound the difference between the true error and the empirical margin error (or, estimation error) (Gönen & Alpaydın| 2011). Beyond the supervised framework, there is a growing interest in exploring MKL approaches for unsupervised scenarios since Zhuang et al. (201T). Most methods seek a kernel that minimizes the distortion between all training data or that minimizes the approximation of the orig-
3

---

Published as a conference paper at ICLR 2025
inal data in the kernel embedding (in et al. 2010 Zhuang al. 2011). Their methods presume that the learned kernel values coincide with the pseudo-ground ground truth of the data's geometry. (In pre- serving the topological structure in unsupervised setting, it is intuitive and appealing to consider the ground truth-the true underlying relationships or labels in the data-similar to its role in super- vised learning. However, since such ground truth is unavailable in unsupervised settings, assume a pseudo-ground truth, such as estimated similarity measures or inferred geometric structures that approximate the inherent relationships among data points.) In addition, they assume that the data is represented as numerical vectors so that it can be directly computed in the input space using the Eu- clidean distance. Unfortunately, such unsupervised methods are not applicable when the inputs are graphs. which are not naturally represented vectors. Furthermore, no explicit kernel embeddings exist for those graph kernels that are not R-convolution. Mariette & Villa- Vialaneix (2018) intro- duced UMKI, which preserves local geometry by constructing a k-nearest neighbor graph for each kernel as a sreudo-ground truth of the data's 's underlying structure. However, this method struggles in practice due to its heuristic approximation of local geometry and rigid objective func- tion, resulting in poor generalization in experiments. Rather than explicitly constructing the local geometry, we tackle the unsupervised multiple kernel learning problem for graphs by learning the complete connectivity on a probability simplex. In this approach, the pseudo-grond ground truth of the topology is implicitly inferred from the data.
BACKGROUND
Before introducing our method, we first present relevant background and notations.
Multiple Kernel Learning for Graphs. Let == {G1.... Gv3 } denote a set of N graphs and K (k(1) .... A.(M) } denote set of M graph kernels, where each graph kernel (((m) is function k((m] 9 x + [0, 1]. With learnable weights w (wi,.... Wm. war) Ra where E Wm and W'm 2 for all m, the pairwise kernel value ki between any pair of graphs Gj E 9 over a set of graph kernels K. is defined as weighted sum of the individual kernel values. Denoting k.j- (((())( Gj),... ".0,0.0),))00)) (Gi, Gý)) IR-M, we have
kij = (w) w Thi kij
Wm (m(m) (Gi, Gj)
Probability Simplex. Each point on probability simplex AN represents a probability distri- bution over a finite number of mutually exclusive events and can be represented by non- negative numbers that sum to 1. We define an N N-probability simplex as the collection of points AN ((11.... .2N) TR-V Σ J; 1, x; O Vi). When N 2, this space is line, when N is filled-in triangle, and when N = 4 it is solid tetrahedron.
METHOD: UMKL-G
In unsupervised multiple kernel learning (MKL), is crucial to preserve the topology of data because this maintains the intrinsic structural properties and relationships between data points. This is even more important in our case, where each data point represents the complex structure of graph. Adhering this first principle, we treat all kernel values {k,, as the pseudo-ground truth structure, without explicitly constructing local geometry for data reconstruction, i.e., graphs in this context. Instead, our method focuses on preserving the data structure through ordinal relationships, through which the pseudo- grouudd truth is implicitly learned. Specifically, we utilize all kernel values ki to construct probability simplex space among the graphs. This strategy ensures that the local topology of the data is maintained while learning the weights w within this space.
4.1 PRESERVING TOPOLOGY
Inspired by Agarwal et al. (2007) and Vankadara et al. (2023), preserve the topology between graphs by maintaining the order of the similarity between graphs. Specifically, we focus on the ordinal relationship that, according to the learned composite kernel kij. graph G, is more similar to Gj than graph G, for any triplet (i.
4

---

Published as a conference paper at ICLR 2025
Definition 1. (Ordinal Relationship) Consider the graph G5 where its similarities to G3 and G+ are respectively given by the learned kernel values kig (i(w) and (w). The ordinal relationship between G2 and G, with respect to G; are preserved if. for any weights w.
(u)(w) (2)(w)
More generally, preserving ordinal relationships for all pairs of graphs ensures that for any graph G,, its most similar graphs remain consistent within the learned kernel space. This approach maintains the local neighborhood structure around each graph, preserving the data's 's intrinsic topology.
4.2 GRAPHS ON A PROBABILITY SIMPLEX
To define feasible probability simplex, we consider probability space over the set of graphs
g : [GI.... .G... The sample space Ω is the set of all ordered pairs of graphs, S2 9 x G. The o-algebra & represents the events over the graph pairs and the probability measure P assigns probabilities to each pair based on its graph kernel value, which measures the similarity between two graphs. For each fixed graph G;, the event of selecting a similar graph G, from 9 is denoted as (G,, Gÿ), where the similarity between G; and Gj is quantified by their kernel value, i.e.,
Rig (Z))
By == (i, Σ (w)
and qi for j. ensuring the axioms of a probability measure are satisfied. The probabilities qi thus normalized kernel values determined via learned weights w, reflecting the relative similarity between G, and all other graphs in G.
where E, 96
Given the probability measure above, each graph could be represented as a point in the probability simplex AN. where G; is associated with the point qi (4.,, "i,,""" (ix) E R. This
representation preserves ordinal relationships since Rú 9s, if and only if kig hir Overall,
define a set of the probability simplex vectors as Q = {q: N C AN.
4.3 TARGET P: POWERED KERNELS
To effectively preserve the ordinal relationships among graphs, we capture key neighborhood struc- tures by amplifying the stronger similarities between graphs towards a set of target probabilities. Specifically, we define a target probability with powered kernel values to reflect these relationships. Definition 2. (Powered Kernel) The target probability is transformed through powered kernel values
(0)
Pi
Σg
R
where the power parameter o N+ On the same probability simplex AN, another set of probability simplex vectors is defined as p(o) = [p. 1N C AN. where p (0) (P., .P.x E R
Note that Q & p(1) (with 1) is special case. For simplicity, denote P as p(o) for an arbitrary parameter o. When the kernel values are raised to a power o for kig kir, the powered kernel values will emphasize the stronger similarity by greater amount than the weaker similarity, i.e., k3 > kg By emphasizing the larger kernel values, we ensure that the ordinal relationships between graphs are preserved (Theorem []. while focusing on the more significant relationships between graphs (Theorem 2) Details of these proofs are provided in Appendix B
Theorem 1. (Ordinality Preservation) Let kug and kir represent the kernel values between graph G and graphs G, and G,, respectively. If the ordinal relationship kus > key holds, then for any power o > 1, the corresponding probabilities in the powered kernel distribution satisfy Pt, > Pi.
(o)
In the same probability simplex space AN, the target probability P is less uniform compared to the original Q. which leads to concentration of probability mass on fewer components for each vector Pi. As such, the concentration effect of the powered kernel is formalized as follows.
5

---

Published as a conference paper at ICLR 2025
Theorem 2. (Concentration Effect) For any graph G. and any 1, the entropy of the powered kernel distribution p is strictly less than the entropy of the original distribution qu i.e,
H(D < H(g)).
(4)
The concentration effect suggests that raising the kernel values to a power o > enhances the contrast between significant and insignificant relationships. Thus, compared to Q. the probability simplex vectors P are more reflective of the underlying structure between graphs. By emphasizing the most meaningful connections, P becomes more accurate representation of the data's inherent geometry. Consequently, by transforming the original probabilities Q towards the target ones P. we implicitly learn a pseudo-ground truth structure k which represents the enhanced composite kernel that reveals the more meaningful patterns in the data.
4.4 OBJECTIVE FUNCTION
To preserve the topological structure during the learning of the weights w, we employ the Kullback- Leibler (KI.) divergence. This divergence quantifies the difference between two probability distribu- tions, P and Q, enabling to align the learned distribution with the underlying graph relationships while minimizing the distortion of ordinal relationships. Specially, we use the reverse divergence:
( = [II( = > E((i, log ti, gi, log p(
(5)
which measures how much information is lost when P is used to approximate Q. This formulation includes a negative entropy term, qt, log 9,, which plays a crucial role in regularizing the learned distribution Q. When minimizing (()), the entropy term penalizes highly concentrated distributions and encourages Q to spread its probability mass more evenly across all graphs. This prevents any single graph from dominating the distribution excessively.
In addition, the reverse divergence tends to be more sensitive to cases where Q has high probability and P assigns low probability, thereby encouraging the learned distribution Q to avoid assigning high probabilities to regions not covered by P. By minimizing the divergence, we ensure that the learned distribution Q closely approximates the target distribution P. thus preserving the topological properties the original graph data.
4.5 PROPOSED ALGORITIM
In this section, we summarize the overall algorithm and how these objective functions are integrated into the learning process. The inputs are groups of N graphs G ;= [GI,-... Gv M graph kernels 37 TR, and the power hyperparameter As outlined in Algorithm|I [ our goal is to Iearn the optimal weights w for combining the graph kernels. Since the composite kernel value is defined in Eq. I where the weights must satisfy the condition
(k-(m) M m== initial weights (0) = M
Σm Wm = I and Wm. 2 0 Vm, we incorporate a projection step (see Algorithm 2 in Appendix D to ensure these conditions are met. Specifically, we project the weights onto the unit simplex, ensuring that the composite kernel retains the properties of the original kernels, such as being positive semi- definite. Although there are other methods ensure unit simplex and non-negativity of weights, our method is efficient with a computational complexity dominated by the sorting step, which is O(M log M). In addition, the algorithm provides an optimal projection terms of the Euclidean distance from the original vector to the simplex. It ensures the smallest adjustment needed to project the vector onto the simplex. We provide more detailed discussion Appendix [ Once the optimal weights w are learned, the resulting composite kernel i can be directly applied to various machine learning tasks, both supervised and unsupervised.
4.6 THEORETICAL ANALYSIS
To support the robustness and effectiveness of UMKL-G, we provide detailed theoretical analysis. Specifically, we establish three key properties: (1) Lipschitz continuity of the gradient of the objec- tive function L(o) (Theorem 3. ensuring smooth optimization and convergence; (2) robustness to

---

Published as a conference paper at ICLR 2025
Algorithm 1: Unsupervised Multiple Kernel Learning for Graphs (UMKL-G)
Input Unlabeled graphs G {G1, Gv base kernels K. (A:0, k(A0), initial weights wh = (M " M power hyperparameter o.
Output: Kernel weights w
Initialize weights w Wo: while not converged do for each pair of graphs (G;, G3) in 9 do
L Kij = -Lm=1 Wm (m(m)() (G,, G5) for each graph G3 in 9 do
// Computa the peirwise kernal value
ki Kis
Rx j=1 Kas)
q:
1/ Compute the reference Q
R
RNN E)= Arg
Pi
// Compute the target
Update weights w by minimizing C());
Aw Project w onto the unit simplex using Algorithm
depends on the eptinizes;
return
kernel perturbations (Theorem 4 guaranteeing the reliability of the solution even in the presence of noise or slight inaccuracies kernel computation; and (3) generalization and stability (Theorems 6), showing the capability of the proposed algorithm to perform well on unseen data. Detailed proof' for these results are provided in Appendix B
Theorem 3. For the set of graphs G with N [ and the graphs G4, G3 G. let ||k Kmax
(keg is defined for Eq. 1. < S E,kis S B, and 0 ô S 9; S 7 < 1. Denote 1/1 as N. t/2 as S+N and tha as z. The gradient of the objective function C(o) is Lipschitz continuous with constant L, such that for any w, w R=; (()) (w) Vw (w')ll L/l w'll with
a=,,
L C1 22 + N K2 max!
(6)
where the constant Ci (1 + (o- 1) log 8 + (2o 1)68))6-115 8-1)- 1/2.
11 + (1 (o- 1)0 + (o+
This result ensures that the gradient of the objective function is Lipschitz continuous, which implies that small changes in the weight vector lead to proportionally small changes in the gradient. This property is crucial for the stability of UMKL-G, allowing for controlled and predictable updates during the optimization process.
Next, we show that UMKL-G is robust to kernel perturbations. Specifically, small variations in the kernel values, whether due to noise, computational inaccuracies, or differences in graph properties, only result in limited changes in the optimal solution.
Theorem 4. Let the perturbed kernel values be kl = kij + Akij. where |Akill S n for any graphs G; and Gy. Assume Ej kay 2 8 I q;; <yy and ||w|| S Denote O(w) 0 as the optimal condition. The magnitude of its change AO due to the kernel perturbations is bounded by
|A0| S C2 7, where the constant C2 ((o- + 1-0 + o) ao +NN).
This result demonstrates that the optimal solution of UMKL-G is robust to small perturbations in the kernel values, ensuring stability even under minor fluctuations in kernel computation.
Before assessing the generalization of UMKL-G, we first define uniform stability for the algo- rithm. Let E N be training set of size N. Our algorithm is symmetric with respect to g, meaning does not depend the order of elements in G. Thus, the modified training set Giv is created by removing any r-th element from g, where E f1, NN. Specifically, we denote g\v = [G....., G,- G. Gx ). Since the loss function (()) is Lipschitz continuous, as a consequence of Theorem 3 UMKL-G is also uniformly w-stable, shown below:

---

Published as a conference paper at ICLR 2025
Theorem 5. Denote Ag as the output of our unsupervised learning algorithm UMKL-G after train- ing on G. UMKL-GG is uniformly w-stable with respect to the loss function ((0) for any G; E X, the following holds:
Ag E X max
(G, ( (G;, (G: sw.
(8)
i=I,",N
Using UMKL-G's uniform w-stability and applying Corollary 1 from Abou-Moustafa & Schuur-
mans 2015), we derive the following generalization bounds for our algorithm:
Theorem 6. Denote A as the algorithm UMKL-G, which is uniformly w-stablle VG E X, and VG E GA Then, for any N 2 1, and any å E (0, 13, the following bounds hold with probability at least 1 - 8 over any G.
log log(1/6)
(i) R(Ag) S REMP (Ag) + 2w + (4Nw v)v
(9)
2N
1og(1/5)
(i) R(Ag) R2oo(Ag) + (4N + +ol
(10)
2N
where B + EM (g,
the leave-one-out (LOO) error estimate.
These bounds provide a guarantee that UMKL-G generalizes well from the training set to unseen data, ensuring consistent performance even in the absence of labeled data. With the aforementioned theoretical foundations of UMKL-G established, it is also important to understand how our method compares to existing approaches in the field of unsupervised multiple kernel learning.
4.7 CONNECTION TO BASELINES (PARTIAL)
Our proposed method shares foundational goal with previous methods, such UMKL (Zhuang eet al. (201T) and SparseUUMKL (Mariette & Villa-Vialanee 2018), which is to preserve the local geometry of the data. These methods have laid significant groundwork in unsupervised multiple kernel learning. In UMKL. the authors propose two main principles: first, for each data point 2;, the optimal kernel should minimize the approximation error ||æ, E, ki,æ,,1 second. the method should minimize the distortion over all training data, Eij kigllææ x,ll², where kij = k(a;, æzj). Similarly, UMML. aims to approximately preserve the local geometry of the data by building k-nearest neighbor graphs for each kernel and defining weight matrix based these graphs. Despite their innovative approaches, both UMKL and sparse-UMKs have limitations in handling graph data and achieving satisfactory empirical performances (see Section for details).
Feature
UMKL
Aparse-UMKE
UMKL-G (Ours)
min XII DII +7 ui(K Do
ming (r KJ Allblla K DN bm Km
min 1 KL(QIP), Ry Eyche
Objective Function
M) ral DIli.
Q
Pg
E, K2
Beyond Euclidean
Global Topology
Theoreticul Guarantees
Topology Preservation Algorithm Complexity
Local reconstruction (D) Alternating minimization OUI (MM22 + X2))
k-NN graph heuristics (W) Quadratic programming solver O(I (M N M)"))
Ordinal relationships
KL divergence
Ou (M M log M))
Table 1: Comparison of UMKL, sparse- UMKL, and UMKL-G.
In Table I we highlight the key features of UMKL-G in comparison the baselines. A detailed analysis can be found in Appendix E
EXPERIMENTS
In this study, evaluate UMKL-G in common unsupervised task graph--eelll clustering.
8

---

Published as a conference paper at ICLR 2025
5.1 DATASETS AND SETUPS
Datasets. We include eight benchmark datasets in our experiments, encompassing diverse types of graph data (Kersting al. 2 These datasets are BZR, COX2, DD, DHER, ENZYMES, IMDB- BINARY, MUTAG, and PTC_FM, as described in Table 5 (Appendix F. Each dataset presents unique characteristics, suitable for testing the robustness and generalizability of our approach.
Configurations. We evaluate our algorithm exhaustively on six state-of-the-ar graph kernels with various hyperparameters, as shown in Table O (Appendix F.. For each dataset, the number of base kernels is 30, i.e., M = 30. Besides, we set the power hyperparameters to {2, 3, 4] to inspect its concentration effect. As for the initial weights, we set them uniformly as 1 1/M by default. For the baseline methods, UMKL and UMML, we trained a Graph Convolutional Network (GCN) (Kipf & Welling 2016) with 10 layers to represent the graphs in vector form. To learn the composite kernel, we explored two approaches: (1) pre-training the GCN to produce fixed graph representa- tions, followed by freezing the GCN parameters during kernel weight updates, and (2) co-training the GCN and kernel weights simultancously. In the following sections, we report the superior perfor- mance obtained from our two approaches. We also consider a set of neighborhood hyperparameters k E {10, 50, 100) for sparse- UMKLL In all experiments, we use the Adam optimizer (Kingma & Ba (0015) at le-3 initial learning rate and le-4 weight decay. The total epochs is set to 500 across all methods. We also include a simple baseline, AverageMKL, where each weight set to 1/M.
Evaluation Metries. We evaluate the empirical performance of our method with three commonly used metrics: clustering accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI), as defined in Appendix [F] These metrics provide a comprehensive evaluation of the clustering performance and the preservation of the topology.
5.2 RESULTS
Overall, we conducted two experiments, comparing (a) the proposed UMKL--C algorithm with base- lines, (b) the proposed UMKL-- algorithm and base graph kernels. All of the findings support the superiority of our method, highlighted below. Please the supplements in Appendix G
UMKL-G consistently outperforms the baseline methods across all datasets. Overall, our pro- posed method demonstrates remarkable improvements in clustering performance. The performance comparison presented in Table 2 underscores the effectiveness of UMKL-G across all metrics. This is evident across various domains, including chemical compounds, biological data, social networks, and protein structures. By focusing on ordinal relationships among graphs, UMKL-G more effec- tively preserves the intrinsic relationships within the data. This approach maintains the relative ordering of similarities, capturing both local and global structural features more accurately than the baseline methods.
Table 2: Comparison with Bascline Methods. The best score is in bold. The second best is under- lined.
Method
BZR
COX2
DD
DHFR
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NMI
ARI
AverageMKI.
0.7341
0.0041
0.0307
0.6167
0.0000
-0.0016
0.5764
0.0060
0.0172
0.6495
0.0000
.0.0021
UMKL
0,7341
0.0041
0.307
06667
0.0000
-0.9016
0,5764
0.0060
0.0172
0.6495
0.0000
-0.0021
Ppars-UUMKLIN (6:
0.7400
030299
0.0001
-0.0010
0.0059
0.6480
spars-UMKLL (k 10=00 50)
0.7415
0.0042
0.0305
0.6180
0.0000
-0,0015
0.5770
0.0061
0.0175
0.6498
0.0000
-0.0022
sparse-UMKI (E 100)
0.7420
0.0041
0.0306
0.6175
0.0000
-0.0016
0.3768
0.0060
0.0172
0.6892
0.0000
-0.0021
UMKL-G
0,9432
0.0279
0.0812
0.8009
0.0045
0.0247
0.5815
0.0098
0.0224
0.6984
0.0111
0.0180
Method
ENZYMES
MMD8-BINARY
MUTAG
PTC.FM
ACC
NMI
ACC
NMI
ACC
NMI
ARI
ACC
NMI
ART
AverageMKL
0.2617
0.0539
0.0220
0.5470
0.0152
0.0083
0.5585
0.1468
0.1946
0.8825
0.0208
0.0343
UMKL
0.2567
0.0517
0.0199
0.5470
0.0152
0.0083
0,5585
0.1469
0.1947
0.8729
0.0208
0.0343
sparse-UNee UUIL-
0.0520
0.5485
0.0153
0.5590
0.1950
0.0210
spars-UMKL Ck 50)
0.2580
0.0518
0.0200
0.5475
0.0154
0.0085
0.5595
0.1470
0.1948
0.8373
0.0211
0.0344
sparse-UMii Prune-UMKL.CC (K 100)
0.2575
0.0521
0.0198
0.5480
0.015T
0.0082
0.5588
0.1468
0.1946
0.8528
0.021
0.0342
UMKL-G
0.2983
0.0648
0.0399
0.5590
0.0159
0.0132
0.8455
0.2950
0.3389
0.8825
0.0394
0.0637
UMKL-G can beat the base graph kernels across all metrics. As demonstrated in Figure 2a
UMKL-G, indicated by the dashed grey lines, consistently surpasses the base graph kernels on the

---

Published as a conference paper at ICLR 2025
DHFR dataset. The base kernels, such as VH, SP, and various iterations of WLOA and WL, exhibit varying degrees of performance. While some kernels achieve relatively high accuracy, they fall short in other metrics such NMI and ARI, indicating imbalance in capturing the overall data structure. This trend consistent across other benchmark datasets, as Figures show.
W64
16.43
16.473
16243
16.4
W.
WL
15.4%
9.3%
W1,1
08
17.2%
10.8%
68.7
16.8%
16.4%
G5,5
(a) Comparison with Base Graph Kernels. The bar plots repre- sent the performance metrics for different kernels. The dashed grey lines indicate the performances UMKL-G.
(b) Learned Kernll Weights of UMKL-G.
Figure 2: Performance on the DHFR dataset. Kernel names are shown with hyperparameters.
UMKL-G automatically select graph kernels and their hyperparameters. This capability is evident from the learned weights, which indicate the relative importance of each kernel in the clus- tering task. As shown in Figure 2b] by assigning higher weights more relevant kernels, UMKL-G effectively prioritizes the kernels that best capture the underlying structure of the data. This auto- matic weighting and selection process not only streamlines the model tuning but also enhances the performance by leveraging the strengths of multiple kernels as shown in the previous finding.
UMKL-G performances are insensitive the hyperparameter full experimental results in Figure TO in Appendix G where UMKL-G reaches stable performance across all power o. The concentration effect insensitive the hyperparameter setting.
2 enough). We provide
CONCLUSION AND FUTURE WORK
In this paper, we propose UMKL-G, an unsupervised algorithm for combining multiple graph ker- nels by focusing on ordinal relationships to preserve the topological structure between graphs. With- out the need to learn a separate graph representation, UMKL-G leverages the concentration effect of powered kernels to maintain the relative ordering of similarities among graphs, effectively captur- ing both local and global structural features. Moreover, we provide theoretical analysis guarantees to ensure the convergence, robustness, and generalization our method, reinforcing reliability in practical applications. Empirically, UMKL-G significantly outperforms two baseline algorithms adapted from GCNs, highlighting its robustness and efficacy in handling graph data where the base- lines fall short.
the future, our work can be extended to other domains by developing UMKL-X, where "X" represents various types of unstructured data. This extension would involve integrating different types of similarity measures suitable for diverse data structures, thereby broadening the applicability and impact of approach. Additionally, exploring the scalability and efficiency of UMKL-G on larger datasets and real-world applications could further validate and enhance its utility.
ACKNOWLEDGEMENTS
We thank all anonymous reviewers for their valuable feedback and constructive suggestions. This work partially supported by the Google PhD Fellowship awarded to Yan Sun.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Karim T' Abou-Moustafa and Dale Schuurmans. Generalization in unsupervised learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 300- 317. Springer, 2015.
Sameer Agarwal, Josh Wills, Lawrence Cayton, Gert Lanckriet, David Kriegman, and Serge Be- longie. Generalized non-metric multidimensional scaling. In Artificial Intelligence and Statistics, pp. 11-18. PMLR, 2007.
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O Bray, Bastian Rieck, et al. Graph kernels: State-of-the-ar and future challenges. Foundations and Trends@ in Machine Learning. 13(5-6):531-712 2020.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. Fifth IEEE international conference on data mining (ICDM'05) pp. 8-pp. IEEE, 2005.
Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Weisfeiler- lehman meets wromov-wasserster In International Conference on Machine Learning, pp. 3371- 3416. PMLR, 2022.
Holger Fröhlich, Jörg Wegner, Florian Sieker, and Andreas Zell. Optimal assignment kernels for attributed molecular graphs. In Proceedings of the 22nd international conference on Machine learning. pp. 225 225-232, 2005.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning The- ory and 7th Kernel Workshop, COtI/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 129-143. Springer, 2003.
Mehmet Gönen and Ethem Alpaydın. Multiple kernel learning algorithms. The Journal of Machine Learning Research, 12:2211-2266 2011.
Wei Ju, Yiyang Gu, Binqi Chen, Gongbo Sun, Yifang Qin, Xingyuming Liu, Xiao Luo, and Ming Zhang. Glee: A general framework for graph-level clustering. In Proceedings of the AAAI Con- ference Artificial Intelligence, volume 37, pp.
2023.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL/Bttp:
tu- cordoruu
de
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua
Bengio and Yann LeCun (eds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015. URL http: 1/arxiv.org/ abs 11122 6980
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 2016.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. Advances in neural information processing systems, 29, 2016.
Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A property testing framework for the theoretical expressivity of graph kernels. In IJCAI, pp. 2348-2354, 2018.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey graph kernels. Applied Network Science, 5:1-42, 2020.
Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine learning re- search, 5(]27):27-72, 2004.
11

---

Published as a conference paper at ICLR 2025
Yen- Yu Lin, Tyng-Luh Liu, and Chiou-Shann Fuh. Multiple kernel learning for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, (346):1147-1166) 2010.
Jéröme Mariette and Nathalie Villa-Vialaneix. Unsupervised multiple kernel learning for heteroge- neous data integration. Bioinformatics, 34(6): 1009-10009-115, 2018.
Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger. Umap: Uniform manifold approximation and projection. Journal of Open Source Software, 3(29), 2018.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey, Journal of Artificial Intelligence Research, 12:943-1027 2021.
Luca Oneto, Nicolo Navarin, Michele Donini, Alessandro Sperduti, Fabio Aiolli, and Davide An- guita. Measuring the expressivity of graph kernels through statistical learning theory, Neurocom- puting, 268:4-16, 2017.
Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2)=117-e118 83, 2007.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488 495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Mahito Sugiyama and Karsten Borgwardt. Halting in random walk kernlss. Advances in neural information processing systems, 28, 2015.
Yan Sun and Jicong Fan. Mmd graph kerne:: Effective metric learning for graphs via maximum mean discrepancy. In The Twelfth International Conference on Learning Representations, 2023.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kernels, Advances in neural information processing systems,
32, 2019.
Leena Chennuru Vankadara, Michael Lohaus, Siavash Haghiri, Faiz UI Wahab, and Ulrike Von Luxburg. Insights into ordinal embedding algorithms: A systematic evaluation. Journal of Machine Learning Rexearch, 24(191):1-83, 2023.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11: 11:1201-1242, 2010.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Wei Ye, Omid Askarisichani, Alex Jones, and Ambuj Singh. Learning deep graph representations via convolutional neural networks. IEEE Transactions Knowledge and Data Engineering, 34 (5):2268-2279, 2020.
Jinfeng Zhuang, Jialei Wang, Steven CH Hoi, and Xiangyang Lan. Unsupervised multiple kernel learning. In Asian Conference on Machine Learning, pp. 129-144. PMLR, 2011.
12

---

Published as a conference paper at ICLR 2025
Appendices
A Motivation and Intuition Behind P
14
Proof of Theorems
15
Algorithm
2
24
D Theorem and Proof for Algorithm 2
24
Connection to Baselines (Full)
26
Description of Benchmark Datasets
27
Datasets
27
F2 Base Kernels
27
Evaluation Metrics
27
Empirical Results
29
G.1
UMKL-G v.s. Base Kernels
29
G.2
Learned Weights from UMKL-G
33
G.3
Sensitivity Analysis
34
G.4
Convergence Analysis
37
G.5
Robustness to Perturbation
38
6.6
Generalization
40
Visualization of Learning Trajectory
42
13

---

Published as a conference paper at ICLR 2025
A MOTIVATION AND INTUITION BEHIND P
To address the intuition behind why the target P provides a more accurate representation of the data's inherent geometry, we include the following example. As explained in Theorem 2 the concentration effect ensures that P has lower entropy compared to Q, as illustrated in Figure I, where P' (red points) spreads further outside Q (blue points). This implies that P focuses more on the most meaningful connections and identifies nearest neighbors in a soft manner. By raising kernel values power > P magnifies the differences between highly similar and less similar graphs. which is crucial for capturing the essential structure of the data.
To make this intuition clear, consider an example with N graphs and their pairwise kernel similarities computed using graph kernel (e.g.. Weisfeiler-Lehmae kernel). The symmetric kernel
matrix K is defined as:
1.0
0.8
0.3
0.2
0.1
0.8
1.0
0.4
0.3
0.2
K
0.3
0.4
1.0
0.7
0.6
(11)
0.2
0.3
0.7
1.0
0.9
0.1
0.2
0.6
0.9
1.0
where each element ki represents the similarity between graphs G; and Gj-
To emphasize differences in similarities, raise the kernel values power o 5. For G₁, the byj
original probability distribution q1 (41, M1. 91s M1 (1a) is computed as 91 Σi=1 b1
(0.4167, 0.3333, 0.1250, 0.0833, 0.0417). After raising the kernel values to the power
5,
the new powered distribution pi (5) (x1 (5) Pis (5) (5)) becomes Pi E; kig
(5)
(5)
ki
(0.7516, 0.2463, 0.0018, 0.0002, 0.0000).
In qı, the probabilities distributed more evenly among the graphs, whereas in P1 ability is heavily concentrated on pi, and pi: This highlights how P helps G₁ find its nearest neighbor G2 by reducing the influence of less similar graphs (G3, G4, Gs).
(5) the prob-
In analogy, P creates "soft cut" of the fully connected network among all graphs, accurately representing the data's inherent geometry. Importantly, the relative ordering of similarities re-
(5) (5)
(5) (5) (5)
mains unchanged: Pl, Pla > Pis > Pl. > Pis Q1 91 Ui, n ns and
kn > h22 > his > b1s > kis-
14

---

Published as a conference paper at ICLR 2025
B PROOF OF THEOREMS
Proof of Theorem 1
Proof. For a given i, if kis [0, represents the similarity between graphs G; and Gj. then for
Diy
ky and for Pi, with > 1, the distribution is: Piy (0) the distribution is qi, Eg kng
(0)
For
Ey by
any ordinal relationship Rig kir and any power
have kij kgg By normalizing,
K
K0 Eg
Eg kig
kig
which implies that p(
Pi. Hence the relationship between (G,, Gj) and (G,, Gy) as reflected (0)
(o)
in ky kip is preserved by the probabilities Pij Psr
(0)
Proof of Theorem
Proof. The entropy of the distribution is given by
N Σ
H(g))
log lig.
(12)
j=1
kig and Ps, Σx b
(0)
Rg for some integer N+. From the definition of giç
Note that Vi, Ey K.j write kij 9b, Ey ka and thus
(9i, Eg )o
(0)
Pi,
Ep(1s Ezer kigo)
Rg (E3 )o
(13)
Ex P.y (Eni kigg))))) )0
E3 P,
Thus, the entropy of (0) can be expressed as
L Ey d
H(p,0)
(0)
log
jr Py.
(14)
N
log qi
+ log S.
S
where S. E E, To analyze the behavior of the entropy for 2 1, will compute the
first-order derivative of H (p)))) with respect
15

---

Published as a conference paper at ICLR 2025
(p,
(0))
0
0
N
Rg
log gi
+ do
log S.
00
80
S
j=1
N
log R:
R Ei j'= R.g.
log Miy
1
N
log 46
log 4b +
Ry
log 4bg
S
So
5
S.
==1
j=1
R log qi
Ry
log Piy
log 4ts
So
5
j=1
B
(log 9: )²
Σ
di log 9;
Σ
gh log Fiy
S
j=l
d==1
(15)
By the Cauchy-Schward inequality, we have
2
N
Σ
oi
log qi
Σ
Σ By (log (108 at;))
(16)
s'=1
Thus, for o 1, the derivative
(0)) 11 (p;
< 0,
(17)
do
meaning that the entropy decreases as o increases. Since H(p,)) = H(g)) when o = 1, the following inequality holds for any graph G, for 1,
H(p))) H(g)).
(18)
Proof of Theorem
3
Proof. As Pi,
qi Ex F.
(see Eq. 13). the loss function (w) can be represented as
L
(( (w) (ww)
Σ
qi log 9:, - qi, log
Eg Lgg.
i
(19)
Σ
Ti log gi, 9-1 + qt, log Σ Pip
Its gradient with respect to the learnable parameters w is
V w (())
Σ
V w Uis log R. ) V.
Gúg log Σ The
3'
(0- (0-1))(lg Szy + 1) + log Σ Py + 4i Eg F.
V Twlliy
(20)
8'
Σ, S Jiy 0-1
- (0 1)(log 9s, + +1 + log Σ Ry +o. 9t
Vwnt,
Σ, P
16

---

Published as a conference paper at ICLR 2025
Given ku = w T kej. we denote 9; ;= qi, (w) = "n le, Zi(w)
where Z((w) = Eg kiy = Eg w key-
The gradient of di, with respect to w is
Kig 7:, (10) - uo ToTH kis Eg kiss
V Vw
[Zi(w)]²
kij
96: Ey Kej
Z,(w)
Zi(w)
(21)
= Z
kij 9i Σ kij
Since we are interested in bounding the difference between the gradient of ((o) at w and w', i.e,
Cw) (w) Enn Tig (w), where
V in which each term involves a sum of the form (w =
-(00- ((0-1) 1) (Lg qi, (w)
)
log Eg (w) Zz(w)
+ 91, (w) Ey Biy (w)
(w)(w))=
+ Z, Ziww)
kis qi (w)(w)
> kig
(zw)
Z,(w) Ey p. (w)
(22)
log 9., (w)
① Let's focus on bounding the difference in the term
which
2:(w)
log qi, (w)
log 9b, (w0' Ze(wr")
log Gi, (w)
log 9b, (w))
log qi (w)
log 96 (w0')
+
7z (ww)
7: (zp")")
7x(w'))
7z(w²")
1
1
log qt, (w)
+
(log q1, (w) log qı, (w
Zi(w)
Zi(w")
Zi(w')
2,(w")
(Z(ww
log qi (w)
(log qi, (w) log qi, (w'))
Zi(w)) (w0)
Ze(wr)
(23)
Since Z,(w') Zi(w) = Exi (wTTiig
Kig - w ((sss)))) we have
[Z,(w)) Z: (w) S ww w' Σ kigr S |/w
w N
(24)
where N is the number of graphs and Kmax is the maximum norm of ||:t among all j, Therefore, we have
7(ww') - (w)) ((w)Z((w') $ (log 0-1) NK
max
log 9b, (w)
w'll
I1-
(25)
a
where a >> 0 is the lower bound for all (ww and log qi S log 8-1, where 8 > 0 is the lower bound for all 4, (w) According to the Mean Value Theorem, we have
llo qi, (w) log qi, (w") (w,) (w) 46, (w")
(26)
Recall that yi, (w)
ky The difference between di (w) and di (w') is 2.(w)
q6 (w) qi (w') wr kis Zi(w'))) w0 kiy (ww
(27)
Z((w)Z,(w)
For the numerator, since wT kij kis S 1, we have
w T kiz Zi(w') - w kis T'Tki, Zi(w)
< |wo' kis w o'ik Zi + TT kay (i(ww') - Zz(w))
< K Kmaxl/wr w'll + 1|w w'IINNnaas
(28)
where 3 is the upper bound for all Z,(w).
17

---

Published as a conference paper at ICLR 2025
Thus, we have
8 + N a²
9ig (w)) Rz (ww')
K max 1 20
(29)
The upper bound of the full second term is
3 + N a²8
Zi(w') (log Yi, (w) log Si, (2o'))
Kmax w w'll
(30)
To sum up @, we denote a 2N 1/1 and denote
D-N at
as 4/2. We have
log Qip (w)
log 4z (ur')
S (1/2 1oogd=) + v/200 Kmax||us w ||-
(31)
(,ww)
(zw'))
We have the bound for the difference in the term Ziww) as below.
7u(w') - (,0)
Z,(w) Zi(w))
Zi Z ( (w')
(32)
S 2 w w o' [|NK max
1/ - Kmax| w w I|-
log En, vl., (w)
Next, we focus on bounding the difference in the term
which
Zz(w)
log Ej (w)
log Ej R. (10')
log Ey Ri (w)
log E, Jh,, (w)
log E, (w))
log E,, R2 (wo)
+
(i(w)
Zi(w')
Z, Z,(w)
2,(w")
2, (w))
(iww')
(33)
As flog Eg. B.ll 1oog(No0~) the first term is bounded
log E, F, (w)
log Ey Ky (w) (,ww')
log(N6-9)NK
max
|/ w
(34)
(ww)
a
For the second term, we use the Mean Value Theorem to get
log E, R. (w)
log E, Sh (w0')
Eg G
99, (w) - 4t (w0))
Zz(w²)
Z(w'))
NNNoo
(35)
0- (B + N) max
[ w'll 11.
3380
where y < 1 the upper bound of all gt,-
To sum up @,, we denote I as thy. We have
log EyR.p R.p, (w)
log Eg RR (w") (wr'))
(wh (oog(No09) + 11 Kmax w'll (36)
(ww)
9; (w) E, 9,, (w)
④ Then, let's focus on bounding the difference in the term
Z, (w) E, p. (w)) which is
d: (w) E3 R. (w)
Ri (w') E3, 0-1 (w') G
((ww) Eg C. (w)
Z((w)) Eg p. (w')
(37)
4g (w)
1, (un')
y' Uig 0-1 (w)
li (wr')
Σ 3' Fig (w)
Ex S (20))
((w)
(z(w))
y P. (wr)
(ww)
ES e Ry (w)
Eg R. (10")
18

---

Published as a conference paper at ICLR 2025
Eq 37 can be split into two terms
9g (w)
9c, (20')
Eg g.y((() (m)
A(w)=
(ww)
Zi(wo))
2nz 92 (w)
(38)
9, (w'')
Σ oe Fi (w)
Σ Fi ((w))
B(w)=
(iw'))
E Fi (20)
yt R. (w0')
By using the bounds in Eq.
24 and 29
we have
9: (w)
R; (w')
44, (w)
9t, (w)
)
9i (w)
9i (20')
+
Zi(w)
(iw'))
(,w))
Zz(w²))
Zi(w")
Z2(2))
-4i (w)
1
Zi(w') (ai,
(qi((t)) (10) - -i; (10')
(,(w) Z,(w"))
(39)
7i(w') 710
=6, (w)
(gi, (w)) 9b, (wo))
2, (,(w) 2
Zz(20')
S <WVL + 1/2) Kmax | w') ||.
Eg
Ej 07 (w)
For any o E No,
Σ, R.g (w) I 1. Thus, we bound the term A(w) as
[A(w) S (W17+ + 422 Kmaxlles w w'll-
(40)
For the term B(w), we formulate it as
qi, (wo)
((w) C(w'))
gi, (w)) C(w)D(wo)) - C(w')((()) D(w) Zi(w')
(41)
(w))
D(w)
D(w')
D(w)
where C(w) E, C ' (w), D(w) Es R. (w). It is obvious to observe that the denominator bounded by
D(w)D(w') 2 22820
(42)
And the numerator can be expressed as follows
D(w) - C(w')((()u))
= =ΣΣ
8' Rg --
(w) (w') - G. (
Ya (w))
-Σ (o J'
(w) (w) d.t (wo)) gh (wo) + ( (2h, (w') oh (w))
(43)
which would be bounded using
{ o (w)) &iy (wo)) 5 (o- 1) 2m/2Kmax -
(44)
Li (w') L. (w) S o anl K Kmax/maleeeeee 1 - w'll
Thus, the numerator can be bounded as follows
2002 (C(w) ((w') C(w''(((W)))))) D(w) < 22 1),20-2 anp 2 Kmax 1/00 w'll, which allows to bound the entire term B(w) by
(45)
[B(w)) (20 1),,0- 1 1/ K
max
le w/ll:
(46)
820
To sum up @ we have
4: (w) Σj F. (w)
qi (w') Ez, gg-((200)
$ (117 + the + (20 - 1) 12-11111111111111 K Kmnax 1/0
w'll
(,w Σn Py (w)
Zi(w') Ex Ry (w')
(47)
19

---

Published as a conference paper at ICLR 2025
L Lastly, obtain upper bound for the term kiy 91 (w) Eg Kay
Since Yi, (w) S for any w. we have
kij 9t, (w)
kis!
I ksyl +
max(qi, (w))
Σ kin' I (1 K
(48)
which is irrelevant to and could be treated as constant.
Combing the steps ① @ c 5, we obtain the upper bound of V (w -on as
Σ (w)) - Tin(w')) SC- SC-N2
K2 max | w'll,
(49)
where we denote the constant C (1 + (o- 1) log8-1 8-1 log(N8 +7) .4 (1 (o + (2o- 1) 1-1) 1/2. Hence, the Lipschitz constant for the gradient of is
= C 22 + yN). K2 Kmax.
(50)
Proof of Theorem
Proof. Recall that the probability 0; is defined as qi; Eg w why. key- Given small perturbation Akij RM with its magnitude || kernel becomes ki = kij + Akij. and the perturbed probability de becomes
(yj( Z.(w)
where Zz(w)
Σ, w kky
7), the new
w T.(( (kij Akis) Σ3 w T (kej -Aksj)
d
(51)
w T kij + ww T Aki
E kig + Akiy)
Then, the change the probability qi, due the perturbation is given by Aqt, 1, - 9bg
w T kij + ww "lisg
kg
Agi, ES w kij' + Akiy)
Σg w kij'
w Akis
w kij
w T kij
+ Ey.(rr kej un T Akij')
Ey(m (w kij' + w Akis.)
Eg kij'
(52)
w Akiy
E, w Akig'
-0 kij
Ey kiy' + Akig.)
Ej.(w kig a Akijy) Ej.(1 220 kige))
Aaisj
Ej w Aliij
9b (w) + Ex w Akuy
Zi(w) + Ey w Akiy'
Since Ej w Aky 2 0, the magnitude of the change Aqt, satisfies that
w T A
Akkj
Σ3 w Akiz
Agi 5
+ 4i,
(53)
Z,(w)
Z,(w)
Given that (,(w) 2 a, |w| S a, and
S 91
S
we can bound Aqg as
Agi
Saa Akولl || + Σ
|
(54)
<aa + +NN
20

---

Published as a conference paper at ICLR 2025
Based on the gradient V in Equation 22 the optimal condition O(w) is expressed
ΣS Σg Ryy. (w)
9i 1-1 (w)
(ww) (o - (log qi, (w) + 1) + log Σ (,, (w) + oqi, (w)
(55)
To analyze how this condition is affected by the perturbation, we bound the change (ww) due to the change in Øi (wr)
Ey Rh (w) Σg Jy (w)
|AO] 5(0- - 1) A log Qi, (w) + A log E
Eky Re (20)
+ A 0gi,(u) (2)
Σ 0.0000 li 1.-1.00 Sggi
A%,
5(0 - 1)
Ois
Ex 41
+ 10. 1./
(56)
<(0 1)
000-180 Aq:,1 0/ Aigl
< ((0 1)6 + 0r 8 +0) a0 + >NN 17
-C.b,
where C ( 1)ō 070 1- +0) a1 +
+ +NN).
Proof of Theorem 5
is deviated from qi original algorithm Ag. Based on 19 we have the following losses on graph G; when processed by the algorithm Ag and Agi,, respectively:
kay Proof. With the algorithm Age,, each 92 Eya, key
vr
Reg in the Eg R.y
(G), Σ j
-4, log
logg;, 9-1 + 9: log Σ Si
(57)
( (G,, Agie) Σ
-h - log(a))) + 03 log Egaiioo
(58)
jfr
j'
Taking the difference between the equations above, we obtain its magnitude as ((0) (G,, Ag) - (G,) Agrr))
-i, log Ni. 0-1 + qt. log Σ
El + Σ
-4g log Ri 0-1 + 44 log Σ
Vi, + 1r
logg(t (p-
Vij log Σ (e
qi, log 9rr
9i. log Σ E
+ Σ
log( (4, )0 log(a))))-1
di log oi
Ii Ap log dr,
96 log Ri
fr
Ti(()
22(6)
T3(0)
lig log
Σ
Dig
log
Σ Tiy
Tig log
P
k2
log EGgD00 S'
j
(2(3)
To (8)
(1) + (1) + (1) + (1) + Ts)
(59)
21

---

Published as a conference paper at ICLR 2025
For simplification, we define (1)), T2()). Ta(t), Ta(t), and break down each term follows.
Ti(1 (1) A -4, log U.,"" qs, log Eot, (o 1)9s, log qs, 9s, log Eg.
Kir log
hir
kir
kig
-0 1)
+
log
Σ 3' kisj
Eg hisg'
Σg kis
Egn Rigg
Riv log
hir
Pir
ES hig
-o - 1)
+
log
Σ
king'
Ej hig
Ej kis
[ 3 Rogi)00
(60)
Te(1) & Σ
/ 1og(9,)) )0- bi
/r log 9i 1-11
)
= (o 100 Σ aly (log(a))) - log 96s)
qi,
jtr
jff
= (o - 1) Σ d
log
lig
Vis
str
Ejjr his
hir
(o 1) Ej' / key
log
1
Ex kig
kir
(o - 1) 1+
Eneee Kis'
(61)
Tb(1) Σ
vr a-1 log gi
qi, log 00,
Σ jfr
9ig 9t:
log 9i, 9-1
jFr
Tess
= (o - 1) Σ
Kis
log
Ejetr Ress
Eg Riss
Eg' Kiss
jzb
Resr
(0 1)
log
Σ Regs
Σ
( (-ke key log log
Egatr kes))
EEgkish
j'yhr
jqt
(62)
(1) 4 Σ
9i log
d
/r Rip
log
Σ
=Σ (9g, itr
923 log Σoe,
3'
5'
(E (E,:kog)) keyg)
-his Tiss jtr
1
log
Exer Kig
E, Rigs
E, hay
(Ejer Kiss
Toor
log
E Riss'
Σ, Riss'
Eg, Rgg.
Tiir
C y Rissy )o
log
Σg Kig
Eg Rolg.
(63)
22

---

Published as a conference paper at ICLR 2025
(1) A
Big
log Σ ni
10 di
log Σ
Σ 5z1
Vi
/
log Σ Fiy. - -log
8'
j'
5
8x
Eg R.
Σ jfr
9i
/2 log
E (
Ej Rig.1 9r Risgr))
= log
Σ E kig.// gi Risgu)
Eg Ki
( kigy)
log
- -log
Σj iiy'
( (i kis
ke
Rir
= =log
+
fr
0. log
1+
Ej' frr kij
Ej Kig
(64)
Therefore, the maximal magnitude of the difference among all graphs "G, is
max ( (G,, Ag) (L (Gi, Agv-)) i=,,", .N
(65)
max (1)) + max T2(1) max Ta (i) + max Ta(1) min Ts(1)
Denote Pu as the upper bound and A as lower bound of kis for all i,j E (i....,NN.i.. 0 p: S kig S Pu S 1. Therefore, each maximum or minimum term above has the following bound. (Note: We use -x log x S c for (1) and (i)))..
max; (i) S (o- - 1)e-1 N PupTi (olog - (0 1) N ologgp
max; T2(1) - (o log( - (N 1)- pappp)
max; Ti( < (o- 1)(N 11-1----1 Pupi Pupp log ((N - 1)pw) (N 1)e-1
(66)
max; T4(1)= - -N11-1pp pupi (olog Pe + (o 1) log N - ooogoooogn pT
N - + 20 log Pi 20 log Pu min; Ts(1) > 2o log
Hence, we can define the w-stability as below:
w: (o- - 1)e + + PuPi 1 (olog Pa - (0 1) log N oolog Pi 1)
+ (o log( 1 + (N - 1) PuPi )
+ (o- I)(N - 1 1 PuPi -2 log ((N 1)pp)) (N 1)e-
(67)
+ -N- Pupi (olog Pu (o log N - olog 11
N
+ 2o N 1
+ 2o log Pi -1 20 20log Pa.
Also, the algorithm UMKL-G is stable wy N
23

---

Published as a conference paper at ICLR 2025
C ALGORITHM 2
Algorithm 2: Projecting Weights onto the Unit Simplex
Input Vector tu
Output: Projected vector
Sort ur in descending order: Wsotedd
Initialize cumulative sum: 5 O:
for i to M do
Update cumulative sum: S = Wsorted [i]; Compute A[i] = 8-1 +
// Justment of each element to unit simplex
for i to M do
if [ 2 Wronted 1] then
a Ali]
// Resign the threahold to the first that satisfles the condition
break
if i M then
L a = {[M - 1]
11 If no break occurs, use the last A
max(w w a. 0);
return w
D THEOREM AND PROOF FOR ALGORITHM 2
Theorem 7. The Algorithm 2 projects any vector x E M onto the unit simplex A-1 ensuring that the projected vector w satisfies: @ Em W; = 1, @ w; 2 0 for all i, @ smallest adjustment in terms of the Euclidean distance needed to project the vector onto the simplex.
Proof. The unit simplex in R is defined as:
M and w; 2 for all i}.
(w E RM
Σ
wi
Let æ RM be the original vector, and let w R.M be the projected vector. The Algorithm
involves the following steps:
Sort æ in descending order to get @sooned
Compute the cumulative sum and the normalized difference to
Ej=1 Usomed [i] 1
Aa
3 Find the largest such that [a[i] 2 Fsomed (i + 1] and set a Aa(()..
4 Project æ onto the simplex by setting
w; max(x; a. 0).
We show that the resulting wo satisfies the properties of the unit simplex as follows.
Sum of Projected Elements.
24

---

Published as a conference paper at ICLR 2025
The sum of the projected elements is
wi (a)
Σ
32
ka.
i=k+1
Since a Aa(A)= Σ 2, -1
we have
ka
Tjj
1.
J=1
Therefore,
M
k
k
Zj
1.
am1
j=
Non-negativity.
By definition of the projection step is
W/s = max(x;; - ar, 0),
which ensures that all wi 2 0.
Optimality Euclidean Distance.
The optimality of the projection in terms of Euclidean distance can be shown by solving the following optimization problem:
min w 2112 subject
w: and w; for all i.
This is constrained quadratic optimization problem, which can be solved using the method of Lagrange multipliers and the optimizality condition are give by the KKT con- ditions: w; max(œ; X, 0). With À in the Algorithm 2 it provides the optimal projection in terms of the Euclidean distance from the original vector to the simplex. This ensures the smallest adjustment needed to project the vector onto the simplex.
25

---

Published as a conference paper at ICLR 2025
E CONNECTION TO BASELINES (FULL)
Our proposed method shares a foundational goal with previous methods, such as UMKL Zhuang al. 2011) and sparse-UMKL (Mariette & Villa-Vialanein 2018), which is to preserve the local geometry of the data. These methods have laid significant groundwork in unsupervised multiple UMKL, the authors propose two main principles: first, for each data point æ;, the optimal kernel should minimize the approximation error ||z; Ej kiy second, the method should minimize the distortion over all training data, Eij kig]laz ||, x,l?? where kij ka xz))- Similarly, sparse- UMKL aims approximately preserve the local geometry of the data by building k-nearest neighbor graphs for each kernel and defining a weight matrix based on these graphs. Despite their innovative approaches, both UMKL and sparse-UMKL. have limitations in handling graph data and achieving satisfactory empirical performances (see Section for details).
kernel learning.
Feature
UMKL
sparse-UMKL
UMKL-G (Ours)
m D 1 XII K D)I +1tt t R 10 vel Pllu.
ming (r( (K( KJ Al|bli, 2 Km
milly L F.
KL(QIIP)
Objective Function
Pg
Eg Aey
Σ b
Beyond Euelidean
Global Topology
Theoreticul Guarantees
Topology Preservation Algorithm Complexity
Local reconstruction Alternating minimization O(1 (M 2 + N*))
k-NN graph heuristics (W) Quadratic programming solver O (MN2 log N M)))
Ordinal relationships Kl. divergence
Ou (MN2 M log M))
Table Comparison of UMKL,, sparse-UMKI, and UMKL-GG
While our method aligns with these foundational principles, also introduces novel perspective by focusing on ordinal relationships to preserve the topology of the data. Unlike UMKL, which primar- ily focuses on minimizing approximation errors, our approach leverages the concentration effect of powered kernels to maintain the local and global topology more effectively. Moreover, compared to sparse- sparse-UMKLL which builds neaeestt neighbor graphs each kernel, our method avoids explicitly constructing local graphs, thereby reducing the computational complexity and potential inaccuracies introduced by thresholding kernel values to obtain the nearest neighbors. Our method also differs in its handling of unsupervised learning for graph data. Whereas traditional UMKL and sparse- UMKL are designed primarily for vector data and rely on approximating local geometry - which can be sensitive to noise, struggle with high-dimensional data, require careful tuning of parameters like k and often fail to capture global structural patterns - our method operates directly on probability simplices. By focusing ordinal relationships, avoid the limitations of local approximations and achieve a more robust and holistic preservation of both local and global topological features.
Dataset
N
UMKL-G (seconds)
UMKL (seconds)
sparse- UMKL (seconds)
MUTAG
188
15.9384
30.9085
21.3190
PTC.FM
344
18.8914
39.5487
23.4447
BZR
405
23.5574
45.8796
29.4764
COX2/DHFR
467
28.9875
71.0475
33.3794
ENZYMES
600
30.2123
93.4008
39,9868
IMDB-BIR BINARY
IMDB-BINARY
1000
43.4140
199.1917
48.4064
DD
1113
43.5285
819.8227
51.8620
Table 4: Runtime comparison of UMKL-G and baselines across benchmark datasets.
26

---

Published as a conference paper at ICLR 2025
F DESCRIPTION OF BENCHMARK DATASETS
F.1 DATASETS
1. BZR: dataset consisting of graphs representing chemical compounds classified based on their bioactivity against certain protein.
2. COX2: Another chemical compound dataset, where the task is to predict the inhibition of the COX2 enzyme.
3. DD: large dataset of protein structures, where the goal is to classify proteins into enzymes and non-enzymes.
4. DHFR: This dataset includes graphs representing compounds tested for their ability hibit dihydrofolate reductase.
5. ENZYMES: Contains graphs of protein tertiary structures categorized into six enzyme classes.
6. IMDB-BINARY: social network dataset where the task is classify movies into two genres based on their actor/actress co-appearance networks.
MUTAG: dataset of chemical compounds labeled according to their mutagenic effect on specific bacterium.
8. PTC_FM: Contains chemical compounds labeled based on their carcinogenicity in male rats.
Table 5: Description of the Benchmark Datasets.
Dataset
BZR
COX2
DD
DHFR
ENZYMES
IMDB BINARY
IMDB-BINARY
MUTAG
PTC_FM
Num. graphs
405
467
1178
188
349
Num. of gruph labels
2
2
Dim. of node attributes
3
18
1
/
Avg. number of nodes
35.75
41.22
284.32
42,43
32,63
19.77
17.93
14.11
Avg. numher edges
38.36
19.79
14.48
Label Proportion
319/86
365/102
691/487
461/295
1/1/1/1/1/1
500/500
125/63
206/143
F.2 BASE KERNELS
Table 6: Description of the Base Graph Kernels.
Graph Kerne
Abbr
Korne Fanction
Hyperpurameter
Values
GGämsrr 2003
Random Welks
RW
kaw G.) 2ap a (yare, A'dl
01,05,,..8
[Borgwarth
Shortes Puth
2005
SP
ksp(S,.3) Enen, Enjer, lractiinn
[Priulj 2007
Sampling
GB
AveuaGG,
#lymapbles,
kvm(G,, G.) (1)
Sugiyama Bargwardt
Woideelle- Subiice Kriege al. 2016
WL
kwr(G. (AGG))
1,
Weisfeile_edmma Lehman Oogmna Assigmment
Weisfeller
Krige of al. 2016
WLAA
Awvoo - (y). s(vl))
1,
F.3 EVALUATION METRICS
Clustering Accuracy (ACC) measures the maximum one-to-one correspondence between la- bels and predicted cluster labels. The Hungarian algorithm is used to determine the optimal map- ping.
ACC
1 n
Σ
If Viuee = map(Upred) (1pred,
(68)
i=1
27

---

Published as a conference paper at ICLR 2025
Normalized Mutual Information (NMI) quantifies the similarity between the ground truth and predicted cluster assignments based on mutual information and entropy.
2 (Yme Xread)
NMI(Y me: Ypres)
(69)
H(Ymee) + ((yrre))
where I(-) denotes the mutual information and H-) represents the entropy.
Adjusted Rand Index (ARI) measures the similarity between the clustering results and ground truth labels, adjusting for chance. is computed as:
1i5 Eij
Σ
Σ; /G)
ARI
(70)
1/
Σ
Σ, (3)
Σ, Σ, (C)
where May is number of samples in both ground truth cluster and predicted cluster j. 0s is number of samples in ground truth cluster i, by is number of samples in predicted cluster j. and is total number of samples.
28

---

Published as a conference paper at ICLR 2025
G EMPIRICAL RESULTS
G.1
UMKL-G V.S. BASE KERNELS
VH
WH
VH
SP
5P
RM
RW_0.8
RM
WLOA 10
WUDA 10
WLSA
VLDA 9
WUDA
WLOA 9
WLDA
WLOA.S
MLGAJ
WLDA
M.DAB
WLDA
WIDALE
MLDA
WLDA
WLOAL
VLOA 4
WLDA
WLDA 4
WLOL
WLDA
WLDA
WL
WL 10
WL
WL 9
WL
WL S
WL_?
WL
WL
WL
WLL5
WLSS
WL
WL
WI
WL
65.8-
65
65.3 8
05.7 7-
65.
G5,
G5_6
0.0
0.2
0.4
0.5
0.8
2.00..bbs.0n0..iss.22.....
-0.02 0.00
0.02
0.06
0.56
0.08
Figure 3: Comparison with Individual Base Kernels on the BZR dataset. The bar plots represent the performance metrics for different kernels. The dashed grey lines indicate the performances of UMKL-G. Kernel names are shown with their respective hyperparameters.
ACC
NMI
ARI
0.5
RM 0.5
RW.0.5
RW,0-1
RW.0.1
RN
WLDA
WLDA
WLDA
VLOA
WLDA
WLDA
VLDA 6
VLDA 6
WUDA 6
WLOA
5
WLDA
WLOO
WLDA
WLDA
VLOA
WLDA
WLDA
MLGA
WUDA
WLDA
WI_10
WL 10
WL.
WL
WL
WL 6
WL
WL
WL. 2
WL.
WL. 2
WL
WL
WL
65.6
65_6
65_6
65.5
G5.5
65.5
65.4
G5.4
65.4
0.2
0.002 ad03
Figure 4: Comparison with Individual Base Kernels the COX2 dataset. The bar plots represent the performance metrics for different kernels. The dashed grey lines indicate the performances of UMKL-G. Kernel names are shown with their respective hyperparameters.
29

---

Published as a conference paper at ICLR 2025
ACC
NMI
ARI
WI
WILAA10
WLDA 10
WLOA 5
WLDA 8
WLOA 8
WLOAA
WLOA
WLOA
VIDAA
WLGA 5
WLDA
VILOA4
WUGA
WIDA
VLOA 2
WUGA 2
WLDA 2
WLOA
WL 10
WL 10
WL 10
WL
WL
WL
WL_6 5
WL 7
WIL7
WL.7
W1 6
WI
W1
WL_ 4
W
W1_4
W1_1
WI_1
W1_1
G5_5
011
0.000 6.002 0.004 0.006 0.088
0.008
0,015
Figure 5: Comparison with Individual Base Kernels the DD dataset. The bur plots represent the performance metrics for different kernels. The dashed grey lines indicate the performances of UMKL-G. Kernel names are shown with their respective hyperparameters.
ACC
NMI
ARI
RW, 0.1
8W 0.1
RW 0.1
WLDA_10
WL
WLGA
WLGA 8
WLDA
MLDA
WLGA
WLDA
VLOOA
WLGA
WLOA
MLDA
VIDA
WLGA 2
WLOA
WLGA_1
WLOA
WI_10
WI_10
WL, 9
WL
WL
WL.
WL
WL7
WL. 6
WL
WL.6
WLS
WI_4
WL
WL
WL.
WL3
WL.
WL_1
WL
65.7
G5.7
65.5
65.4
65.4
65.4
6.5 0.10 nis ado 0.5
0.52 0.03
0.56
0.01
Figure 6: Comparison with Individual Base Kernels on the ENZYMES dataset. The bar plots repre- sent the performance metrics for different kernels. The dashed grey lines indicate the performances of UMKL-G. Kernel names are shown with their respective hyperparameters.
30

---

Published as a conference paper at ICLR 2025
ACC
NMI
ARI
V11
V11
V1-
BW
8.8
NW 0.5
RW 0.5
RW 0.5
RM 0.1
RW
WLDA 10
WUGA 10
WLDA
VLDA
VLOA 7
WLOA
WL04
VLOA 6
WLOALG
WLGA 6
WLOALS
WLGA
VERA
WLOA 2
WLDA
VL.4 2
MUSA 1
WLGA 1
WEDA 14
WL_10
WL_10
WL
WL
WL
WL, 7
VA_7
WL
WL 6
W6_6
WL.
WL5
WL
WL 2
VA
WL
W1, 1-
V6
WL
6
G5
05,
G5.6
G5.6
65_5
65.5
65_5
65
65_4
65_4
0.2
Figure 7: Comparison with Individual Base Kernels on the MUTAG dataset. The bar plots represent the performance metrics for different kernels. The dashed grey lines indicate the performances of UMKL-G G. Kernel names are shown with their respective hyperparameters.
ACC
NMI
ARI
WLDA_10-
VLDA 9-
WLOA
WLDA
MLOA
WLDA
WLDA
WLDA
WLO0
WLDA
WLDA
WLDA
WLDA
WI-A
VLOA
WLD0
W.ON.3
WLGA
MLDA_1
WLDA
WLDA
WI_10
WI, 10_10
W_.10
WL_9
WL_9
WL.9
WL_8 8
WL_
WL.8
WL. 7
WL. 7
WL.7
WL. 5
WL
WL.
WL
WL4
WL.4
W
WL_
WL.
WL
WL_1
WL_1
05.7 7
05.7
05.7
65.4
65.4
65.4
0.b3
ob1
0.04
Figure 8: Comparison with Individual Base Kernels on the PTC.FM dataset. The bar plots represent the performance metrics for different kernels. The dashed grey lines indicate the performances of UMKL-G. Kernel names are shown with their respective hyperparameters.
31

---

Published as a conference paper at ICLR 2025
32

---

Published as a conference paper at ICLR 2025
G.2
LEARNED WEIGHTS FROM UMKL-G
RW_0.8
R.Y
RVV. 0.1
WLOA
WLOA 0
WLGAL
14.2%
65.4
WLDAA7
RIY 0.5
WL
35,4
G8_5
4.5%
4.5%
WLDA
4,4%
68_7
4.5%%
WLDA_
4.5%
GSLS
11.4%
RWV
WLOKLT
WILLn0
WI_1
WL WWLAI
WIL 8YL WL 11
(a) BZR
(b) COX2
68_6
WLOA_1
WL_
17.2%
15.8%
31. 31.9%
G8_7
G5,4 4
31.3%
18.4%
G8_5
as,5
G8_6
(c) DD
(d) DHFR
RW,0.1
WLGA 10
RW 0.5
WLDA_10
WLDA_8
12.5%
1.%
11.2%
WLOA_7
2.3%
WLOA.6
WLOK.5
68.3
22.3%
WLOA, 9
3.2%
W.OA
WLDA 3
WLDA,2
31.8%
WLDA.1
WL
W0L.00
WL_3
(e) ENZYMES
(0 IMDB-BINARY
RW. OW.
WLGA
VH
WLOA
14.2%
RVLO5
28.7%
14.7%
G8.4
15.2%
16.2%
29
14.9%
31.3%
13.3%
7%
WLOAA
WLOA.E B
GS_7
(g)
MUTAG
(h) PTC.FM
Figure 9: Learned Kernel Weights of UMKL-G on All Benchmark Datasets. Kernel names are shown with their respective hyperparameters.
33

---

Published as a conference paper at ICLR 2025
G.3 SENSITIVITY ANALYSIS
In this section, we provide the full sensitivity analysis of hyperparameter and initial weight in the following tables, where we initialize the weights using four different methods:
Each weight is 1/M (default).
2. A where = A - Apl represents the difference between consecutive eigenvalues of the Laplacian matrix derived from each base kernel. Here, & is the presumed number of groups in the dataset.
A/ Σ A, where À is defined above.
4. Weights are drawn randomly from Dirichlet distribution.
Table 7: Sensitivity Analysis BZR Dataset.
Initial
ACC
NMI
ARI
I/M
0.9432
0.0279
0.0811
2
1
1
A
0.9432
0.0279
0,0811
>/Σx
0.9580
0.0260
0.0787
2
Random
0.9418
0.0309
0.0859
3
I/M
0.9432
0.0279
0.0811
1- 1-A/EA
0,9432
0.0279
0.0811
> 0.9580
0.0260
0,0787
Random
0.9418
0.0309
0.0859
4 1/M
0.9432
0.0279
0.0812
1
0.9432
0.0279
0.0811
4
X/Σx 0.9580
0.0260
0.0787
Random
0.9418
0.0309
0.0859
Table 8: Sensitivity Analysis COX2 Dataset.
Initial
ACC
NMI
ARI
2
1/M
0.8009
0.0045
0.0247
1- 1-x/>>
0.8009
0.0045
0.0247
X/ΣX 0.7580
0.0046
0.0247
Random
0.8009
0.0045
0.0247
3
1/M
0.8009
0.0045
0.0247
X/
0.8009
0.0045
0.0247
X/ 0.7580
0.0046
0,0247
Random
0.8009
0.0045
0.0247
1/M
0.8009
0.0045
0.0247
1
~//
0.8009
0.0045
0.0247
0.7580
0.0046
0.0247
Random
0.8009
0.0045
0.0247
34

---

Published as a conference paper at ICLR 2025
Table Sensitivity Analysis on DHFR Dataset.
Initial
ACC
NMI
ARI
1/M
0.6984
0.0111
0.0180
2
1
1-XEx
X
0.6984
0.0111
0.0180
X/ΣA
0.6653
0.0111
0.0180
Random
0.6865
0.0115
0.0187
1/M
0.6984
0.0111
0.0180
1
1-XE
0.6984
0.0111
0.0180
0.6653
0.0111
0.0180
3
Random
0.6865
0.0115
0.0187
4
1/M
0.6984
0.0111
0.0180
1 -
>
0.6984
0.0111
0.0180
4
>E 0.6653
0.0111
0,0180
Random
0.6865
0.0115
0.0187
Table 10: Sensitivity Analysis ENZYMES Dataset.
Initial
ACC
NMI
ARI
1/M
0.2983
0.0645
0.0396
2
1- >/E
A
0.2983
0.0646
0.0393
X/ΣA
0.2833
0.0662
0,0352
2
Random
0.3050
0.0670
0.0400
I/M
0.2983
0.0645
0,0396
1-
1
0.2983
0.0641
0.0393
X/Σx
0.2833
0.0662
0.0338
Random
0,3050
0.0669
0.0398
4 1
1/M
0.2983
0.0648
0.0399
--
0.2983
0.0650
0.0393
4
X/ΣX 0.2833
0.0662
0.0346
Random
0.3050
0.0669
0.0398
Table 11: Sensitivity Analysis MMDB-BINARY Dataset.
Initial
ACC
NMI
ARI
2
1/M
0.5590
0.0159
0.0132
1
1
1-x/E>
A
0.5590
0.0239
0.0132
X/ΣX 0.5620
0.0174
0.0147
Random
0.5600
0.0239
0.0137
3
1/M
0.5590
0.0159
0.0132
X/
0.5590
0.0239
0.0132
X/Σx 0.5620
0.0174
0,0147
Random
0,5600
0.0239
0.0137
1/M
0.5590
0.0159
0.0132
1
-/
0.5580
0.0239
0.0128
X
0.5620
0.0174
0.0147
Random
0.5600
0.0239
0.0137
35

---

Published as a conference paper at ICLR 2025
Table 13: Sensitivity Analysis on PTC. FM Dataset.
Initial
ACC
NMI
ARI
1/M
0.8825
0.0394
0.0637
2
1
1-XEx
X
0.8825
0.0394
0.0637
X/ΣA
0.9112
0.0396
0.0637
Random
0,8711
0.0394
0.0637
1/M
0.8825
0.0394
0.0637
1
1-VE
0,8825
0.0394
0.0637
0.9112
0.0396
0.0637
3
Random
0.8711
0.0394
0.0637
4
1/M
0.8825
0.0394
0.0637
-
>/
0.8797
0.0394
0.0637
4
VE 0.9112
0.0396
0,0637
Random
0.8711
0.0394
0.0637
Table 12: Sensitivity Analysis MUTAG Dataset.
Initial
ACC
NMI
ARI
2
1/M
0.8455
0.2950
0.3389
1
1-x/E>
0.8455
0.2950
0.3389
X/ΣX 0.8239
0.1743
0.2533
Random
0.8340
0.2469
0.3020
3
1/M
0.8455
0.2950
0.3389
-//
0.8455
0.2950
0.3389
X/E 0.8239
0.1743
0.2533
Random
0.8340
0.2469
0.3020
1/M
0.8455
0.2950
0.3389
1
--
0.8455
0.2950
0.3389
X
0.8239
0.1743
0.2533
Random
0.8340
0.2469
0.3020
36

---

Published as a conference paper at ICLR 2025
0.8
0.7
0.7
0.6-
0.5
3pc
0.3
0.2
0.2
0.2
0.1
D3
0.7
0.5
0.6-
0.5-
0.24
AC:
ACC
A
AV
0.2
0.2
0.1-
0.0
BIZYHES
IN06 SPLARY
0.32
0.5
0.22
0.4
0.23-
Tye
ACC
ACC
0.15
0.2
0.13
0.1
0.05
MUTI
0.5
0.82
0.55
0.45
0.
0.35
0.32
0.0
Figure 10: Sensitivity Analysis of Parameter o Across All Benchmark Datasets.
G.4 CONVERGENCE ANALYSIS
In this section, we demonstrate the smooth convergence plots, which validate Theorem 3
37

---

Published as a conference paper at ICLR 2025
0.02
0.45
0.93
3 0.75
0.65
0.55
0.82
0.50
Esscts
Epcora
D3
1340-
5019.4
1344
2019.2
K343
5019.0
6342
#367
3013.0
S018
$334
Easus
Ep207s
BIZTHES
IND6 38.AAY
3052
7150
3054
7100
3852
2012
-4
Estcts
002.2
191.2
2003
2053
2053
000.0
192.5
603.7
2050
Eseche
Eppere
Figure 11: Training Losses Across All Benchmark Datasets.
G.5 ROBUSTNESS TO PERTURBATION
In this section, we provide the robustness analysis across all datasets, where perturb the base kernels by adding Gaussian noise (O, o²). As the tables show below, noise perturbations have negligible effects on performance across datasets, which validate Theorem 4
38

---

Published as a conference paper at ICLR 2025
Table 14: Evaluation of Perturbation No0 o²)
Base Kernels on BZR Dataset.
ACC
NMI
ARI
0.01
0.9432
0.0279
0.0811
0.001
0.9432
0.0279
0.0811
0.9432
0.0279
0.0812
Table 15: Evaluation of Perturbation No0, o²) in Base Kernels on COX2 Dataset.
ACC
NMI
ARI
0.01
0.8030
0.0045
0.0247
0.001
0.8030
0.0045
0.0247
0.8009
0.0045
0.0247
Table 16: Evaluation of Perturbation /\00, o²)
Base Kernels on DD Dataset.
ACC
NMI
ARI
0.01
0.5823
0.0100
0.0215
0.001
0.5815
0.0099
0.0224
0,5815
0.0098
0.0224
Table 17: Evaluation of Perturbation (0, o²) in Base Kernels on DHFR Dataset.
ACC
NMI
ARI
0.01
0.7037
0.0109
0.0173
0.001
0.6997
0.0111
0.0180
0.6984
0.0111
0.0180
Table 18: Evaluation of Perturbation \O o²) in Base Kernels ENZYMES Dataset.
ACC
NMI
ARI
0.01
0.2967
0.0620
0.0373
0.001
0.2983
0.0650
0.0399
0.2983
0.0648
0,0399
Table 19: Evaluation of Perturbation (00 o?) in Base Kernels IMDB-BINARY Dataset.
ACC
NMI
ARI
0.01
0.5590
0.0159
0.0132
0.001
0.5590
0.0159
0.0132
0.5590
0.0159
0.0132
39

---

Published as a conference paper at ICLR 2025
Table 20: Evaluation of Perturbation M00, o²) in Base Kernels on MUTAG Dataset.
ACC
NMI
ARI
0.01
0.8455
0,3028
0.3514
0.001
0.8455
0.2950
0.3389
0.8455
0.2950
0.3389
Table 21: Evaluation of Perturbation (0, o²) in Base Kernels PTC_FM Dataset.
ACC
NMI
ARI
0.01
0.8825
0.0394
0.0637
0.001
0.8825
0.0394
0.0637
0.8825
0.0394
0,0637
G.6 GENERALIZATION
In this section, we demonstrate the generalizability our methods on those unseen data, by splitting out 20% test data. As the tables show below, test performances are closely aligned with those on the full dataset, empirically validating the theoretical bounds in Theorem 6
Table 22: Generalization Evaluation on BZR Dataset.
Dataset
ACC
NMI
ARI
Test All
0.9407
0.0329
0.0886
0.9432
0.0279
0.0812
Table 23: Generalization Evaluation on DD Dataset.
Dataset
ACC
NMI
ARI
Test
0.5658
0.0076
0.0148 0.0224
All
0.5815
0.0098
Table 24: Generalization Evaluation on COX2 Dataset.
Dataset
ACC
NMI
ARI
Test
0.8043
0.0048
0.0258
All
0.8009
0.0045
0.0247
Table 25: Generalization Evaluation on DHFR Dataset.
Dataset
ACC
NMI
ARI
Test
0.7053
0.0125
0.0193
All
0.6984
0.0111
0.0180
40

---

Published as a conference paper at ICLR 2025
Table 26: Generalization Evaluation on ENZYMES Dataset.
Dataset
ACC
NMI
ARI
Test
0.3063 0.2983
0.0785
0.0422
All
0.0648
0.0399
Table 27: Generalization Evaluation on IMDB-BINARY Dataset,
Dataset
ACC
NMI
ARI
Test
0.5550
0.0152
0.0112
All
0.5590
0.0159
0.0132
Table 28: Generalization Evaluation on MUTAG Dataset.
Dataset
ACC
NMI
ARI
Test
0,8392 0.8455
0.1289
0.1756 0.3389
All
0.2950
Table 29: Generalization Evaluation on PTC.FN Dataset.
Dataset
ACC
NMI
ARI
Test All
0.8853 0.8825
0.0568 0.0394
0.0747
0.0637
41

---

Published as a conference paper at ICLR 2025
G.7 VISUALIZATION LEARNING TRAJECTORY
Lmar
Mer
Figure 12: UMAP McInnes al. 2018 Visualization of the Learning Trajectory of Q on the DD Dataset with target pto) Each point represents graph with colors indicating the local connectivity at the initial stage (i.e., epoch = 0). Time points are illustrated at various epochs to depict the progression over time.
42


Reviews:
[{"review_id": "UFWFIHQXdC", "reviewer": "Reviewer_y8qJ", "summary": "The authors propose an unsupervised multiple kernel learning method that produces a weighted sum of kernels given a set of kernels and a dataset.", "questions": "I have severe problems understanding\n> Definition 1:\n> Consider the graph $G_i$ where its similarities to $G_j$ and $G_r$ are respectively given by the learned kernel values $k_{ij}$ and $k_{ir}$. \n> The ordinal relationship between $G_j$ and $G_r$ with respect to $G_i$ are preserved if, for any weights $w$: $k_{ij} > k_{ir}$. \n\nIt seems that this definition is self-referential, as only the learned kernel values $k$ are mentioned. Is there another similarity that should be preserved? If $k$ is to be learned, then it probably should retain the ordinal relationship of another similarity (or similarities?). Or am I missing something? I am sorry, but this does not make sense to me right now and I have to recommend to reject this paper at the current point in time.", "limitations": "", "rating": 3, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "- Multiple kernel learning is a relevant topic. In particular, the unsupervised creation of a suitable kernel from a set of kernels given a dataset is a nontrivial problem.", "weaknesses": "- the basic definition (Def. 1) is imprecise and I could not follow the paper, as it remains unclear (to me) which ordinal relationship is supposed to be maintained", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CPCkVxp95t", "reviewer": "Reviewer_zRfj", "summary": "The article introduces a novel approach for unsupervised multiple kernel learning on graphs. The task is to combine several weak kernels for unsupervised learning scenarios by learning a set of weights. The main idea is to preserve the data topology by maintaining ordinal relationships, i.e., the order of similarities between graphs. This is achieved through a designed probability simplex. The authors provide comprehensive theoretical results, addressing aspects such as robustness to kernel perturbations and generalization capabilities. Finally, the approach is experimentally evaluated by performing graph clustering tasks on standard molecular datasets.", "questions": "1. I would appreciate it if the authors could comment on the limited experimental evaluation (see weaknesses). \n2. Can you explain why any parameter o>1 results in exactly the same performance for the selected clustering metrics? Can this be generalized or is it only the case in the considered experiments?\n3. What ground truth was used e.g. for the clustering accuracy metric (ACC)? \n4. Did the authors consider the simple baseline where each weight is set to 1/M?\n5. It is mentioned in section 4.5 that the learned composite kernel can directly be applied in supervised tasks. Have the authors tested this on graph classification tasks using the molecular benchmark graph datasets? \n6. Can the authors elaborate on the choice of representing graphs using a GCN for the baseline methods?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The approach offers a novel solution to an understudied problem.\n- The technical quality of the theoretical part of the work is high.\n- The theoretical analysis is comprehensive, featuring a range of results on properties and detailed proofs. \n- While the authors present their work in the realm of graph kernels, their approach can be applied to arbitrary kernels.", "weaknesses": "- While most parts of the article are well described, some central intuitions that motivate the approach are not sufficiently addressed. For instance, why is P a more accurate representation of the data's inherent geometry'? \n- The evaluation is fairly limited, relying solely on the clustering task. I understand that due to space limitations, the authors focused on the theoretical parts. However, a more comprehensive evaluation (even if it's on synthetic data) should have been done. Particularly, none of the theorems of section 4.6 are evaluated in the experiments. \n- Some details on the baseline methods, UMKL, and sparse-UMKL, are unclear. For instance, the statement that the authors \"experimented with an approach that learns graph representations and kernel weights simultaneously\" requires further elaboration.\nMinor weaknesses:\n- Some of the numbers in Table 1 do not coincide with the numbers in the supplementary. (E.g., ACC for BZR and MUTAG.)\n- It would be helpful if the authors could include the definitions of the clustering metrics in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z9xMevwPUI", "reviewer": "Reviewer_v1ke", "summary": "The paper introduces Unsupervised Multiple Kernel Learning for Graphs (UMKL-G), a method that combines multiple graph kernels without the need for labeled data. By preserving ordinal relationships among graphs through a probability simplex, UMKL-G aims to provide a unified, adaptive kernel learning approach for unsupervised graph-level clustering.", "questions": "1. How does UMKL-G handle datasets with minimal ordinal relationships, or where graph similarities are uniform across samples?\n2. Could the authors clarify the method’s sensitivity to the initial weight settings and the power hyperparameter o in the kernel concentration step?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents an interesting concept by preserving ordinal relationships among graphs in an unsupervised setting, addressing a unique aspect of unsupervised kernel learning.\n2. The authors provide proofs for stability, robustness, and generalization, which strengthen the theoretical foundation of the method.\n3. The empirical validation across eight datasets provides a reasonable breadth of testing for the proposed approach.", "weaknesses": "1. Although the paper claims novelty in ordinal preservation, the methodology heavily relies on established techniques in probability simplex construction and multiple kernel learning. The main contribution appears to be an incremental adaptation rather than a breakthrough.\n2. The method does not convincingly outperform modern baselines or recent self-supervised clustering methods, especially given that existing techniques like sparse-UMKL and GCN-based methods already achieve comparable results in unsupervised scenarios. This raises questions about the practical impact and added value of UMKL-G.\n3. While the paper proposes potential extensions to broader data types (referred to as UMKL-X), there is no experimental evidence or conceptual framework supporting its effectiveness beyond graph-specific tasks. This reduces confidence in the generalizability and adaptability of the approach across different types of structured data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B5oTQUlYdG", "reviewer": "Reviewer_wiDT", "summary": "The paper proposes a new way to combine multiple graph kernels into a unified kernel value. The algorithm preserves topology through ordinal relations. This is mainly achieved by capturing important neighborhood structures by boosting the stronger similarities between graphs towards a set of target probabilities.", "questions": "- How does UMKL-G really stack up against GNN-based methods for clustering graphs? A more in-depth comparison could be useful to estimate the applicability despite methodological differences.\n- What is the impact of the scalability of the method?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Theoretical results are provided that guarantee stability and robustness of the method (e.g. Lipschitz continuity, robustness to kernel perturbations).\n- UMKL-G outperforms existing methods on graph clustering benchmarks, demonstrating robust performance in unsupervised contexts on real and synthetic datasets.\n- The method is applicable to a variety of datasets, making it versatile and potentially useful for many applications.", "weaknesses": "- It is not entirely clear to me how this work differs significantly from existing MKL approaches, apart from the focus on ordinal relations. That is, the methodology, although well executed, seems to me an incremental extension of existing techniques. \n- Some parts of the paper are technical and dense, which although I appreciate very much, makes the text particularly complicated to follow.\n- Comparisons with other techniques, in particular more recent methods based on Graph Neural Networks (GNN), are limited. This reduces the perception of how competitive UMKL-G is compared to emerging technologies.\n- Perhaps some focus on scalability is lacking, as testing on large datasets limits the evaluation of the method's effectiveness in real, large-scale scenarios.\n- Large parts of the introduction and Section 2 are redundant. \nThe writing is dense and the explanation of concepts complex. Greater clarity could make the work more accessible to a wider range of readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)