Unsupervised Multiple Kernel Learning for Graphs via Ordinality Preservation

W1: It is not entirely clear to me how this work differs significantly from existing MKL approaches, apart from the focus on ordinal relations.

Response: We appreciate your feedback and would like to clarify the distinct contributions and methodological innovations of UMKL-G compared to UMKL [1] and sparse-UMKL [2]. Below, we highlight the key differences and advancements:

1. Conceptual Innovations
   • Ordinal Relations for Topology Preservation:
     • UMKL-G introduces ordinal relationship preservation as a central principle, which ensures that the similarity rankings among graphs remain consistent throughout kernel learning. This is fundamentally different from UMKL’s reliance on explicit Euclidean reconstruction and sparse-UMKL’s use of k-NN heuristics.
     • The ordinal preservation approach is novel in unsupervised MKL and particularly suited for graph data, where preserving structural relationships is more meaningful than explicit geometric reconstruction.
   • Probabilistic Representation via Simplex:
     • UMKL-G represents kernel similarities as distributions on a probability simplex and employs the Kullback-Leibler (KL) divergence for optimization. This probabilistic approach eliminates the need for explicit geometric constraints or heuristic neighbor constructions, offering a more flexible and scalable solution for complex graph data.
2. Substantive Empirical and Theoretical Contributions
   • Empirical Performance:
     • UMKL-G consistently outperforms individual kernels and state-of-the-art baselines across multiple benchmark datasets, demonstrating its effectiveness in real-world scenarios where graph relationships dominate.
     • Sparse-UMKL struggles with generalization due to its rigid sparsity assumptions, while UMKL’s reliance on Euclidean data limits its applicability.
   • Theoretical Guarantees:
     • UMKL-G is equipped with strong theoretical guarantees on robustness, stability, and generalization, which are not explicitly addressed in either UMKL or sparse-UMKL. These guarantees ensure reliable performance under noisy conditions and unseen data.

W1: Although the paper claims novelty in ordinal preservation, the methodology heavily relies on established techniques in probability simplex construction and multiple kernel learning.

Response: Thank you for your feedback. We want to clarify the novelty and significance of our contributions.

Firstly, multiple kernel learning in an unsupervised setting is an understudied and nontrivial problem as agreed by Reviewers y8qj and zRfj. Our approach, ordinal preservation in unsupervised multiple kernel learning (UMKL) adopts a completely different principle from traditional methods. Unlike existing approaches such as UMKL [1], which rely on explicit Euclidean reconstruction, or sparse-UMKL [2], which uses heuristic k-NN constructions, our method directly leverages ordinal relationships to preserve the relative similarity rankings among graphs, which is particularly meaningful for non-Euclidean data (e.g., graphs).

In addition, the application of probability simplex construction in UMKL is novel in this context and setting. By representing kernel similarities as probability distributions and optimizing over the simplex using Kullback-Leibler (KL) divergence, we provide a flexible, scalable, and theoretically grounded framework for unsupervised MKL. This probabilistic approach is the first of its kind in UMKL and eliminates the need for explicit sparsity or heuristic neighborhood constructions.

W1: 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'?

Response: Thank you for your valuable feedback.

As shown in Theorem 2, the concentration effect means that the target $P$ has a lower entropy compared to $Q$, which is consistent with the illustration in Figure 1, where the read points representing $P$ are spread outside the blue points representing $Q$. By raising kernel values to a power $o>1$, $P$ amplifies the differences between highly similar and less similar graphs. This process emphasizes the most meaningful connections and focuses more on the nearest neighbors, reducing the influence of less similar graphs.

To make this intuition clearer, let's consider an example. Suppose we have 5 graphs ($N=5$), and we have computed their pairwise kernel similarities using a graph kernel (e.g., Weisfeiler-Lehman kernel). For simplicity, let's define the following symmetric kernel matrix $\tilde{K}$ as

where each element $\tilde{k}_{ij}$ represents the similarity between graph $G_i$ and graph $G_j$.

We choose a power $o=5$ to amplify the differences in similarities. For $G_1$, the original distribution $\mathbf{q}\_1 = (q\_{1_1}, q\_{1_2}, q\_{1_3}, q\_{1_4}, q\_{1_5}) = (0.4167, 0.3333, 0.1250, 0.0833, 0.0417)$, while its powered distribution $\mathbf{p}\_1^{(5)} = (p\_{1_1}^{(5)}, p\_{1_2}^{(5)}, p\_{1_3}^{(5)}, p\_{1_4}^{(5)}, p\_{1_5}^{(5)}) = (0.7516, 0.2463, 0.0018, 0.0002, 0.0000)$ (all values are rounded to 4 decimal places).

Note that in $\mathbf{q}\_1$, the probabilities are more evenly distributed among the graphs, whereas in $\mathbf{p}\_1^{(5)}$, the probability is heavily concentrated on $(p\_{1_1}^{(5)}, p\_{1_2}^{(5)})$. In this sense, $\mathbf{q}\_1$ helps $G_1$ find its nearest neighbor $G_2$, reducing the influence of less similar graphs $(G\_3, G\_4, G\_5)$.

By amplifying the similarities, we effectively sharpen the focus on the most similar graphs, which better captures the essential structure of the data. Intuitively, $P$ makes a "soft cut" of the fully connected network among all data. Instead of making a hard cut-off (e.g., considering only the top $k$ nearest neighbors), this method smoothly adjusts the influence of other graphs based on their similarity. This approach allows us to consider neighbors in a probabilistic manner, assigning higher importance to closer graphs without entirely discarding others.

Meanwhile, the relative ordering of similarities remains the same: $p\_{1_1}^{(5)}> p\_{1_2}^{(5)}> p\_{1_3}^{(5)}> p\_{1_4}^{(5)}>p\_{1_5}^{(5)}$, $q\_{1_1}> q\_{1_2}> q\_{1_3}> q\_{1_4}>q\_{1_5}$ and $\tilde{k}\_{11}> \tilde{k}\_{12}> \tilde{k}\_{13}> \tilde{k}\_{14}> \tilde{k}\_{15}$.

Again, thank you for this suggestion. We have added this example to Appendix A.

Q1: I have problems understanding Definition 1.

Response: Dear Reviewer,

Thank you for your valuable feedback regarding Definition 1 in our paper. We apologize for any misunderstanding caused by its presentation. We would like to clarify Definition 1 and address your concerns.

First and foremost, we assure you that there is no self-referential issue with the original Definition 1:

Definition 1 (Ordinal Relationship) Consider the graph $G_i$ where its similarities to $G\_j$ and $G\_r$ are respectively given by the learned kernel values $\tilde{k}\_{ij}$ and $\tilde{k}\_{ir}$. The ordinal relationship between $G\_j$ and $G\_r$ with respect to $G\_i$ are preserved if, for any weights $\mathcal{w}$: $\tilde{k}\_{ij} > \tilde{k}\_{ir}.$

The premise of our approach is based on the fixed initial composite kernel values $\tilde{k}\_{ij}(\mathbf{w}\_0)$, which serves as a reference point for defining the ordinal relationships among the graphs. Specifically, $\tilde{k}\_{ij}(\mathbf{w}\_0) = \mathbf{w}_0^{\top}\mathbf{k}\_{ij}$, where $\mathbf{w}\_0 \in \mathbb{R}^{M}$ is the initial set of weights and $\mathbf{k}\_{ij} = (k^{(1)}(G\_i, G\_j), \cdots, k^{(M)}(G\_i, G\_j)) \in \mathbb{R}^M$ are the base kernel values.

During the learning of the kernel weights $\mathbf{w}\_t$ ($t>0$), the ordinal relationships captured by the initial composite kernel $\tilde{k}\_{ij}(\mathbf{w}\_0)$ are preserved in the learned composite kernel $\tilde{k}\_{ij}(\mathbf{w}\_t)$ as shown by Theorem 1 in Section 4.3 of our original paper. Specifically, if graph $G\_i$ is more similar to graph $G\_j$ than to graph $G\_r$ in the initial composite kernel space (i.e., $\tilde{k}_{ij}(\mathbf{w}\_0) > \tilde{k}\_{ir}(\mathbf{w}\_0)$), this relationship continues to hold for any set of weights $\mathbf{w}\_t$ during learning. This preservation ensures that the local neighborhood structure and intrinsic topology of the data remain consistent throughout the optimization process. Thus, there is no self-referential loop.

Kindly note that in our updated experimental results (Appendix G.3), the choice of initial weights does not significantly affect the clustering scores. This provides empirical evidence that UMKL-G is robust to different initializations and preserving the ordinal relationships helps maintain consistent performance across various starting points.

We appreciate your feedback, which has highlighted the need to clarify this aspect of our methodology. In the revised manuscript, we have included the explanation in Section 4.1 to make the purpose of Definition 1 clearer and to address potential misunderstandings. We hope that these clarifications will address your concerns and demonstrate the validity of our approach.

Thank you again for your thoughtful review and for helping us improve the clarity of our paper.