Unsupervised Multiple Kernel Learning for Graphs via Ordinality Preservation
Graph Kernel; Unsupervised Learning; Multiple Kernel Learning
Yes
No ethics review needed.
I have severe problems understanding
> Definition 1:
> 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}$. 
> 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}$. 

It 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.
- 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.
The authors propose an unsupervised multiple kernel learning method that produces a weighted sum of kernels given a set of kernels and a dataset.
- 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
Yes
No ethics review needed.
1. I would appreciate it if the authors could comment on the limited experimental evaluation (see weaknesses). 
2. 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?
3. What ground truth was used e.g. for the clustering accuracy metric (ACC)? 
4. Did the authors consider the simple baseline where each weight is set to 1/M?
5. 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? 
6. Can the authors elaborate on the choice of representing graphs using a GCN for the baseline methods?
- The approach offers a novel solution to an understudied problem.
- The technical quality of the theoretical part of the work is high.
- The theoretical analysis is comprehensive, featuring a range of results on properties and detailed proofs. 
- While the authors present their work in the realm of graph kernels, their approach can be applied to arbitrary kernels.
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.
- 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'? 
- 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. 
- 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.
Minor weaknesses:
- Some of the numbers in Table 1 do not coincide with the numbers in the supplementary. (E.g., ACC for BZR and MUTAG.)
- It would be helpful if the authors could include the definitions of the clustering metrics in the appendix.
Yes
No ethics review needed.
1. How does UMKL-G handle datasets with minimal ordinal relationships, or where graph similarities are uniform across samples?
2. Could the authors clarify the method’s sensitivity to the initial weight settings and the power hyperparameter o in the kernel concentration step?
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.
2. The authors provide proofs for stability, robustness, and generalization, which strengthen the theoretical foundation of the method.
3. The empirical validation across eight datasets provides a reasonable breadth of testing for the proposed approach.
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.
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.
2. 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.
3. 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.
Yes
No ethics review needed.
- 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.
- What is the impact of the scalability of the method?
- Theoretical results are provided that guarantee stability and robustness of the method (e.g. Lipschitz continuity, robustness to kernel perturbations).
- UMKL-G outperforms existing methods on graph clustering benchmarks, demonstrating robust performance in unsupervised contexts on real and synthetic datasets.
- The method is applicable to a variety of datasets, making it versatile and potentially useful for many applications.
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.
- 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. 
- Some parts of the paper are technical and dense, which although I appreciate very much, makes the text particularly complicated to follow.
- 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.
- 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.
- Large parts of the introduction and Section 2 are redundant. 
The writing is dense and the explanation of concepts complex. Greater clarity could make the work more accessible to a wider range of readers.
UMKL-G combines multiple graph kernels in an unsupervised way, preserving the ordinal relationships between graphs.
@inproceedings{
anonymous2024unsupervised,
title={Unsupervised Multiple Kernel Learning for Graphs via Ordinality Preservation},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=6nb2J90XJD},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Graph Kernel; Unsupervised Learning; Multiple Kernel Learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/ae9691ef8f6f0d0b7921772e7ca4e213ec9da5d9.pdf
unsupervised, self-supervised, semi-supervised, and supervised representation learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Unsupervised Multiple Kernel Learning for Graphs via Ordinality Preservation
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission