Unsupervised Multiple Kernel Learning for Graphs via Ordinality Preservation

Authors: Yan Sun, Stanley Kok
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: Graph Kernel; Unsupervised Learning; Multiple Kernel Learning

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.

Decision: accept (poster)
Reviewer scores: 3, 8, 5, 6

Reviews and discussion:
<thread>
creation date:
1730106993157

thread_type:
official_review

<thread_object>
creator: reviewer_widt

<content>
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.

strengths:
- 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.

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. 
- 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.

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.
- What is the impact of the scalability of the method?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730535152410

thread_type:
official_review

<thread_object>
creator: reviewer_v1ke

<content>
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.

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.
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.

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.
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730664802155

thread_type:
official_review

<thread_object>
creator: reviewer_zrfj

<content>
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.

strengths:
- 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.

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'? 
- 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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730760592735

thread_type:
official_review

<thread_object>
creator: reviewer_y8qj

<content>
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.

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

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731931492446

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank the reviewers for their valuable feedback, which improved our work. Below are the key updates:

1. **Clarity Enhancements**
    - Added comparison table in Section 4.7 to clearly show the novelty and distinction of our model. 
    - Revised Definition 1 to clarify the role of the initial composite kernel.
    - Revised Section 5.1 to make a clear demonstration of the baseline configurations.
    - Added definitions of evaluation metrics (ACC, NMI, ARI) in the Appendix.
    - Added an example in the Appendix to illustrate the intuition of $P$.
2. **Expanded Theoretical and Empirical Evaluation**
    - Validated theoretical guarantees (convergence, robustness, and generalization) with additional experiments in Appendix G.
    - Presented ablation studies showing robustness to noise and hyperparameter variations in Appendix G.
    - Included graph classification results to showcase versatility beyond clustering.
3. **Baseline Comparison**
    - Added AverageMKL as a simple baseline to Table 2 in the manuscript.
    - Added two GNN-based approaches as baselines.
    - Added theoretical and empirical runtime comparison in Appendix E.

*We believe these revisions address all concerns and strengthen our work. Thank all reviewers for their constructive comments!*
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the problem of Multiple kernel learning on Graphs in the unsupervised learning setting. This is a niche problem which has bearing on many problems. The paper seems to be theoretically sound, but maybe lacking in some aspects of experimentation. This paper should  be of interest to ICLR audience, specially those interested in Learning on Graphs.