Boosting Spectral Clustering on Incomplete Data via Kernel Correction and Affinity Learning
Authors: Fangchen Yu
Runze Zhao
Zhan Shi
Yiwen Lu
Jicong Fan
Yicheng Zeng
Jianfeng Mao
Wenye Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Spectral Clustering
Incomplete Data
Kernel Correction
Self-expressive Affinity Learning
TL;DR: The paper proposes two new approaches to improve spectral clustering on incomplete data using kernel correction and affinity learning.

Abstract: Spectral clustering has gained popularity for clustering non-convex data due to its simplicity and effectiveness. It is essential to construct a similarity graph using a high-quality affinity measure that models the local neighborhood relations among the data samples. However, incomplete data can lead to inaccurate affinity measures, resulting in degraded clustering performance. To address these issues, we propose an imputation-free framework with two novel approaches to improve spectral clustering on incomplete data. Firstly, we introduce a new kernel correction method that enhances the quality of the kernel matrix estimated on incomplete data with a theoretical guarantee, benefiting classical spectral clustering on pre-defined kernels. Secondly, we develop a series of affinity learning methods that equip the self-expressive framework with $\ell_p$-norm to construct an intrinsic affinity matrix with an adaptive extension. Our methods outperform existing data imputation and distance calibration techniques on benchmark datasets, offering a promising solution to spectral clustering on incomplete data in various real-world applications.

Boosting Spectral Clustering on Incomplete Data via Kernel Correction and Affinity Learning
Fangchen Yu', Runze Zhao', Zhan Shi Yiwen Lu Jicong Fan Yicheng Zeng", Jianfeng Mao Wenye Li
The Chinese University of Hong Kong, Shenzhen, China 2 Shenzhen Research Institute of Big Data, Shenzhen, China (fangchenyu, runzezhao, zhanshii, yivenlul) ink. cuhk. edu. cn fanjicong@cuhk, edu. en, statzycdsribd. en, fmaoocuuk. edu, en, wyli@cuhk. edu. cn
Abstract
Spectral clustering has gained popularity for clustering non-convex data due to its simplicity and effectiveness. It is essential to construct similarity graph using high-quality affinity measure that models the local neighborhood relations among the data samples. However, incomplete data lead to inaccurate affinity measures, resulting in degraded clustering performance. To address these issues, we propose imputation-free frree framework with two novel approaches to improve spectral clustering on incomplete data. Firstly, we introduce a new kernel correction method that enhances the quality of the kernel matrix estimated incomplete data with a theoretical guarantee, benefiting classical spectral clustering on pre-defined kernels. Secondly, we develop a series of affinity learning methods that equip the self- expressive framework with no-mm to construct an intrinsic affinity matrix with an adaptive extension. Our methods outperform existing data imputation and distance calibration techniques on benchmark datasets, offering promising solution to spectral clustering on incomplete data in various
applications.
Introduction
has become widely used and effective method for clustering non-convex data and finds diverse applications in computer vision [4]5]. natural language processing [6] 77, and bioinformatics 8 9. Generally, the first step in spectral clustering involves constructing an affinity
Spectral clustering
matrix that captures the similarity between data points, followed by performing normalized cut on the corresponding graph to partition the data into clusters. The quality of the affinity matrix
However, incomplete data is commonly seen in practice, leading to inaccurate affinitics and degraded clustering performance [00 [I [2]. As such, obtaining high-quality affinity matrix with missing data is challenging task that requires specialized techniques. this paper, we aim to improve the quality of affinity matrices, which naturally enhance the performance of spectral clustering incomplete data.
critical factor that determines the effectiveness of the clustering performance [ 3
In recent years, the development of methods to construct affinity matrices with full information for spectral clustering has garnered significant attention. Two types of affinity matrices are typically utilized, namely pre-defined similarity matrices
and self-expressive affinity matrices 19 20). Pre-defined similarity matrices are easy to compute and encompass well-known kernels, including the Gaussian kernel, Exponential kernel, and Polynomial kernel. The Gaussian kernel is the most widely used due to its simplicity and effectiveness (2). Differently, self-expressive affinity matrices learn the affinity matrix C' by representing each data point as
3 15 16
17
18
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

linear combination of other data points, i.e., mine - XCI + XR(C), where the columns
of X E gdxn are data points, R(C') denotes regularization term, and À is hyperparameter. as exemplified by Sparse Subspace Clustering (SSC) [5), Low-Rank Representation (LRR) []6],
and Least-Squares Representation (LSR) 17 [8] Moreover, self-expressive methods have been expanded by integrating kernel functions into the framework, such as kemnel SSC (KSSC) [9) kernel LRR (KLRR) [20), and kernel LSR (KLSR) B.. through minc (X) cX + XR(C),
where (XX is a mapping function and K := (X) denotes kernel matrix. Despite the varying techniques on affinity matrices, the kernel matrix remains a comnerstone of spectral clustering for pre-defined similarities and self-expressive affinities. Nevertheless, constructing a high-quality kernel/affiiity matrix is an ongoing challenge when facing incomplete data. The primary obstacle is the inability to directly calculate a kernel matrix or learn an affinity matrix due to missing values.
To address the challenge of incomplete data, data imputation techniques [21 22 23 such as statistical imputation and matrix completion, are conventional approaches to fill in the missing entries of the data matrix before clustering. Statistical imputation methods [24] 25 such as zero, mean, and
k-nearest neighbors (kNN) imputation [26]. are fast and easy to implement and can flexibly handle
missing data. However, these methods may introduce bias and fail to capture the true underlying data
structure, hindering the accurate affinity measures. Matrix completion methods 27 28
29
30, on
the other hand, aim to accurately recover the underlying structure of the data by finding a low-rank or high-rank approximation of the data matrix. Although they can handle missing data in a principled way, their performance heavily depends on the consistency of data structure and the assumptions being made, easily affected by the data distribution. Most importantly, almost all imputation methods do not offer a guarantee for the quality of the affinity matrix calculated on the imputed data [31.
Distance calibration techniques 32 33 have emerged as an alternative solution by obtaining high-quality distance matrix for incomplete data. These techniques calibrate an initial non-metric distance matrix estimated on incomplete data to a distance metric. Several methods have been proposed, such as the metric nearness model [34, 35 33), which finds the nearest approximation that satisfies all triangle inequalities (37]. The conbeee-cntering algorithm 38] converts the initial non-metric distance matrix into a Euclidean distance matrix, while the Euclidean embedding method ensures the Euclidean embeddable property satisfied through convex optimization. Although some of these methods guarantee the quality of the calibrated distance [3,, they only apply to distance-based affinities like the Gaussian kernel. Moreover, these methods may not generate high-quality affinity matrices based on calibrated distance, making it necessary to develop dedicated methods that can apply to a family of kernels and affinities with theoretical guarantees.
[3 40 4T
To address the above issues, we propose an imputation-free framework to directly learn high-quality affinity matrices via two main techniques, i.c., kernel correction and affinity learning, aiming to improve the spectral clustering performance on incomplete data, with contributions as follows.
We propose an imputation- free framework based on kernel correction and affinity learning with improved clustering performance, providing convenient tools deal with incomplete data. To our best knowledge, this is the first systematical work to discuss spectral clustering on incomplete data, which is commonly seen problem in practice.
We introduce a novel kernel correction method that directly focuses on the kernel matrix estimated from the incomplete data, and corrects it to satisfy specific mathematical properties such as positive semi-definiteness (PSD). We show that the corrected kernel matrix becomes closer to the unknown ground-truth with a theoretical guarantee, which is beneficial to spectral clustering algorithms and cannot be assured by imputation and calibration methods.
We develop a series of new affinity learning methods to equip the self-expressivv framework with the fp-norm to capture the underlying structure of data samples better. Additionally, we combine kernel correction and affinity learning to arrive at an adaptive learning method that simultaneously learns the high-quality kernel and the self-expressive affinity matrix.
We conduct extensive experiments that demonstrate the effectiveness of proposed methods on various benchmark datasets, showing superior results in terms of kernel estimation, spectral clustering, and affinity learning on incomplete data, compared to existing data imputation and distance calibration approaches.

---

2 Related Work
2.1 Spectral Clustering and Aflinity Learning
Standard Spectral Clustering involves three steps (2) first, a Gaussian kernel matrix K E Raxn is calculated to measure the similarity between data points with K, exp( ||, xzg 1| /o²) where o is a hyperparameter. Then, an affinity graph A E gux= is constructed using the kernel matrix, which can take the form of an e-neighborhood graph, a fully connected graph, or a k-nearest neighbors (ANN) graph. An e-neighborhood graph connects pairwise points with a threshold value c, while a fully connected graph connects all points. Empirically, kNN graph the most popular one that connects each point to its k-nearest neighbors, resulting in sparse local relationships and relatively high clustering accuracy []. Finally, the normalized cut algorithm [ is applied to the affinity graph A to partition the data into clusters based on the normalized Laplacian matrix.
Self-expressive Affinity Learning is framework learn affinity matrices by modeling the relation- ships between data points, i.e., minc || - X + XR(C), with different types of regularization terms R(C). Sparse Subspace Clustering (SSC) [15] assumes that the data points lie in a low- dimensional subspace and seeks to find a sparse affinity matrix with R(C) ||C|| Li.j= layl under constraint diag(( ()- 0. Low-Rank Representation (LRR) [16] is another approach that seeks a low-rank affinity matrix with R(C) = ||C]|, (nuclear norm of C). Least-Squares Repre- sentation (LSR) [8] involves solving least-squares problem to find the representation matrix with (CC) = &|| fe. Their kernel variants, i.e., KSSC [19], KLRR (2), and KLSR (3] are used to extend their applicability to non-linearly separable data by applying kernel function to data points with mine 1 _l(((X) ) - (X)CT| + AR(C), showing promising performance in spectral clustering.
2.2 Missing Data Processing Techniques
for dealing with incomplete data by filling in missing values. Statistical imputation methods, such as zero, mean imputation, and k-nearest neighbors (kNN) approach (26]. have been widely used in practice. These methods replace the missing value with a zero, mean, or k-weighted value of non-missing elements in the corresponding feature. Additionally, matrix completion [27 28 29, 30 is machine learning-based technique that fills missing values by solving a matrix factorization problem under assumptions on data structures such as low-rank or high-rank. However, correctly estimating missing values based on observed data difficult, especially for a large missing ratio, and there is no guarantee on the quality of the affinity matrix on imputed data. This motivates us to design imputation-fis frree approaches in Sections 3 and
Data Imputation is a popular technique 21 22 23
Distance Calibration is a specialized approach obtaining valid distance metric from an initial non-metric distance matrix, which can be applied to incomplete data. For any two incomplete data samples 2,, Iy E IRd, a new vector (T) E | is formed by selecting the observed values of x; on the set I, where I is an index set of all features observed in both samples. The pairwise Euclidean distance between z; and i can then be heuristically estimated by (39 [3 41
d = (1xa xx, (T)1l V [7]
However, the initial Euclidean distance matrix D usually not a distance metric due to missing values. Distance calibration methods (34
[db]] R.xx estimated incomplete data is 35
3X 39 can
correct T distance metric by making different assumptions and leveraging various properties. More details of these methods are discussed in Section[3.]
3 Methodology-L. Kernel Correction
3.1 Revisiting Distance Calibration Methods
We begin with the definition of a distance metric 42), then delve into distance calibration methods, discussing the assumptions and properties underlying each method, well as their limitations. Definition 1. A distance metric is defined as a n x n real symmetric matrix D that satisfies
dig dji 2 0, du O, du S di + dyks for all 1 S k, k S n.
3

---

The properties of non nogatiiiiii,,y, reflexivity, symmetry, and triangle inequality ensure that the distance metric produces meaningful and valuable distance measurements.
The Triangle Fixing (TRF) Algorithm
35 to obtain a distance metric is based on the metric
nearness model 34 36], which finds the nearest approximation of non-metric D by solving:
minimize DEREXN
11 subject to dij = dji 2 0, da = 0, d. I d.j + dsk: A i, S n. (2)
However, there are two significant limitations. First, the scalability of the algorithm is severely limited by the matrix size n. Since the number of O(n²) constraints grows rapidly as increases, the optimization time can become lengthy, taking several hours for a few thousand samples. Second, the performance of the algorithm depends on the extent of violation of the triangle inequalities in the initial distance matrix 1 With a small missing ratio of features, D already satisfies most triangle inequalities, i.e., dh S dgs + d2A- then the algorithm typically yields only marginal improvement.
The Double-Centering (DC) Algorithm 38 starts with the Euclidean Distance Matrix (EDM) and utilizes Property | [44] a well-known result in classical Multi- Multi-Dimensiiee Dimensional Scaling (cMDS) to build the connection between the similarity matrix and the EDM.
43
45
Definition 2. A n. x n real symmetric matrix D is called an EDM if there exists 21, Z2...., E Rdd such that daj = |, - 2,11² for i.j 1.2..... n. (Note that it uses squared Euclidean distance.)
Property A n n real symmetric mutrix D is EDM if and only if diag D) = 0, ; JJD
0, == - ee' T /nn, where I is the identity matrix and is the n-dimension vector of all ones.
The DC algorithm first finds the nearest positive semi-definite á by solving
minimize SERnxn
||S - J(D
DI subject to S = 0,
where D is the initial Euclidean distance matrix and a denotes the Hadamard product. The algorithm then transforms Š into an EDM D using dig = $ + ررة 28:j. and obtain the calibrated (non-
squared) distance matrix by D t [dt//1, but unfortunately, the quality of D cannot be guaranteed, and important information may be lost during the transformation [38).
The Euclidean Embedding (EE) Algorithm 339 40, 41 leverages Euclidean embeddable
property 33 46 to obtain a calibrated embeddable distance matrix by solving
minimize DERaxn
||
12 subject to exp( D)p = 0, da 0, d.p d 2 0, A1 vi S n. (4)
Definition 3. in Euclidean space and a distance function such that dij = p(z,, 2 f i.j 1,...,
real symmetric matrix D is said Euclidean embeddable there exists 21. ......, In
Property 2. [Theorem 2, [39]] If n n real symmetric matrix D is Euclidean embeddable, then the kernel K == exp( y D) is positive semi-definite for any > 0.
It is important note that these methods can only provide a calibrated distance matrix with benefits for distance-based kernels and are not a universal solution for dealing with incomplete data in spectral clustering tasks, which motivates us to further design kernel- speccilleei method in Section 3.2
3.2 Kernel Correction Algorithm
To overcome the limitations of distance calibration, we propose a new kernel correction algorithm that directly focuses the construction of high-quality kernel with theoretical guarantee. We consider an incomplete data matrix X E dxxn with missing values and an initial kernel matrix K E Raxx estimated from X. Inspired by our previous work [1 48), our goal is to correct the initial kernel K to improved estimate K that satisfies the PSD property based on the Lemmal 1
49
Lemma 1. A valid kernel matrix is n X n real symmetric matrix that satisfies the PSD property.
Naturally, we recover the PSD property with the minimum cost by solving the following model:
minimize Keaaxn
||
1 subject to K > 0, kig = kiz E (1, v)), V1 S i,j S n,
(5)
where I denote the lower bound and upper bound, respectively.
4

---

It is worth noting that the solution K to Eq. 5 provides an improved estimate of the unknown ground-truth K compared to K as illustrated Theorem The proof comes from Kolmogorov' which characterizes the best estimation in an inner product space, provided
criterion 50
31 47
48
in Appendix
Theorem |
R|FF - K FF The equality holds if and only if K = 0. i.e. K K.
Regarding the kernel type, Gaussian kernel a widely-used non-linear kernel that has elements the range [0, 1]. In this case. the feasible region in Eq. (5) defined as F { R > 0. hy
1, kiy = kyx E [0, 1], A I i,j S n). which a closed convex set. The solution to Eq. ( is the projection of A onto F, denoted by K. However, finding the direct projection is complex, and no closed form of K exists. Thus, we break down FF into two simpler, closed convex subsets Fi and F2: K ž 0}. F22 = {K |R"X" būs = 1, jig = ky; E [0, I], S i, & n). with F = F1 F2. Then K can be efficiently solved by iteratively projecting y onto F1 and F/2
Fi = {K 12ax
31 40
Denote P1, P2 as the projection onto F1, F2. respectively, in the form of
(i(K) ULUT where K UEU Σij max (Eij 0}: P2( = [P2(k;y)] where P2(kss) = median (0, kij, 1}, P2(k;) = 1,
(6)
where USUT gives the spectral decomposition (SD) of K. We use Dykstra's 's projection algorithm 51 find the optimal projection, summarized in Algorithm I
Algorithm Kernel Correction (KC)
Input: K E IRax;; initial (non-PSD) kernel matrix; P1, P2: the projection onto F1 and F2;
mariter: maximum iterations (default 100); tol: tolerence (default 10 5). Output: E g=x"; the optimal corrected kernel matrix.
1: Dykstra's 's Projection: Y, P. Q are auxiliary variables.
2: Initialize Xo = Kdd and Po = Qo = 0nxn-
3: for t 0, ....... mariter do
4: Y = +
5: Pi+1 = P Y,,
6:
X = -Y, Qt),
7:
Q+1 Y, Qt X2+1.
8:
if |X++1 X, /r < tol then
break 10: end if
9:
end for
12: Set K = X
The convergence guarantee of Algorithm Senitthhmmriiee relies on the Boyle-Dykstra's result [52]
Lemma Given real symmetric matrix K E Raxx, the sequence (Xt) generated Algorithm
converges to K minker=Rino, || K as + cc.
3.3 Limitation and Complexity Analysis
The potential limitation primarily stems from the time complexity of Algorithm [ time complexity of the KC algorithm is currently at O(n²), which mainly arises from the spectral decomposition (SD) in the projection operation P1 and poses challenges when dealing with large- scale datasets. To address this issue, a possible solution is to replace the spectral decomposition with a randomized singular value decomposition (rSVD) [53] The rSVD approach seeks top-k singular values and effectively reduces the time complexity to ( log(k) + 2n k²). However, the trade-off between efficiency and efficacy necessitates further investigation. Besides, can transform Dykstra's 's projection into parallel version with cyclic projection [54 to achieve better scalability. The storage complexity is O(n²) to store the dense kernel matrix in memory.
The pre-iteration
5

---

3,4 Discussion on Kernel Correction
The proposed kernel correction approach provides an imputation- free method with several benefits to spectral clustering, compared to data imputation and distance calibration methods.
Differences with Previous Kernel Methods Some literature in kernel learning [55 56 has studied missing data in a supervised manner. However, our work focuses on unsupervised learning and addresses complete but inaccurate (noisy) kernels due the presence of incomplete observations, which is fundamentally different from previous work (57) primarily dealing with incomplete kernels.
Ad Advantages over Data Imputation Our approach eliminates the need for domain knowledge in handling incomplete data by bypassing the imputation step. This enables us to generate a kernel matrix that is theoretically guaranteed, offering potential advantages for various kernel-based applications. Notably, our approach demonstrates significant improvements over imputation methods for spectral clustering when dealing with high proportion of missing data. Additionally, the high-quality kemell produced by our approach can serve as a valuable reference for improving the accuracy of missing value estimation in kerne--based imputation methods (58 [9], which is worth further investigation.
Ad Advantages over Distance Calibration Firstly, our approach can be applied to a wide range of kernels and yields an improved kemell matrix. In contrast, distance calibration methods only benefit distance-based kernels and lack quality guarantees. Moreover, our algorithm, which corrects the Gaussian kernel, can generate a high-quality distance matrix via dij = V-o² log(k:;)) By incorporating the second-order term of di in k. = (x)(- our algorithm becomes more sensitive to changes in distance values, while the Euclidean embedding algorithm relies on using the first-order term of d... Empirical evidence suggests that the corrected
K = distance obtained from our corrected Gaussian kernel is more accurate than the calibrated distance derived from the Euclidean embedding method, benefiting to the ristance-based spectral clustering.
Benefits to Spectral Clustering Our approach is tailored to improve the kernel quality, making it highly advantageous for spectral clustering. This improvement benefits both standard spectral clustering using the Gaussian kernel and affinity learning based on the self-expressive framework. In the case of X-based self-expressive affinity, we can apply the corrected linear kernel == X X to the optimization, i.e., mine 2 || XCII + XR(C)- mine [ (K -KC +C Similarly, for K-based expr-sxpressive affinity, which involves using the Gaussian kernel or other kernels, our approach can be applied to K := o(X) (XX) on ming -llé(X) ((X) +XR(C).
+ (CC++)((C)
4 Methodology-In Affinity Learning
Taking advantage of the corrected kernel matrix, we have further designed series of kernel-based affinity learning algorithms to acquire high-quality affinity matrices with an adaptive extension.
4.1 Kernel Self-expressive Learning with 4--norm
We utilize the kernel self-expressive framework, i.e., minc 2 (X) (X)CII + and propose new affinity learning methods by enhancing the sparsity of the affinity matrix C using the fp norm [60] Specifically, our approach diverges from previous work (19 20 3 by incorporating two forms of -n-ormm, i.e., proximal p-norm and Schatten p-norm (0 < < 1), as regularization terms.
Definition 4 (Kernel Self-expressive Learning with Proximal p-norm).
minimize CERaxa
]l(((X) ((X)CI + 2 Ici... subject 0 S cj S ViSijS (7)
where the proximal p-norm is expressed as ||C||: = Eij legl.
We construct an augmented Lagrangian function (C Z,U) Eq. (8) and solve by using the
Alternating Direction Method of Multipliers (ADMM) approach 61] summarized in Algorithm _
1 12 1 CI (8)
Cp= |x(()) +(X) +Y
max(2 1, (Z-C)) 2p
However, the KSL-Pp algorithm involves numerous hyper-parameters and entails non-convex optimization process during the 7-update step (Line 5 Algorithm()) making it difficult to effectively utilize. Computation speedup needs further investigations. Thus, focus on the Schatten p-norm.

---

Algorithm 2 Kernel Self-expressive Learning with Proximal p-norm (KSL-Pp)
Input: K: kernel; A, P; 7, hyperparameters, mariter: maximum iterations; tol: tolerance.
Output: C' E Ruxx; the optimal affinity matrix of Eq. (7)
1: Initialize Co. Zo, Un-
b Refer to Appendix B. for formula derivations.
2: for 000, ,..,, mariler do
3: C-update: C++1 + (2K + 1 (2K + U2 + Z));
4: Z-update: Zr-1 t DC, Xpzzj p- + 7 (= + ( Ciy) + uej 0: 5: U-update: U141 Ut + pl -
8215
6: if (primal) ||r++1 2411 p S tol and (dual) [| - Z S tol then; break: end if.
7: end for
8: Set C = (IC,l +
1/2..
Definition (Kernel Self-expressive Learning with Schatten p-norm).
2 [llØ( - 6(X) + X |O subject to 0 cij S 1, SiVissj
minimize CER
(9)
2
where Schatten p-norm |[C]ls, = (Ei=) (C)) and (C) denotes the i-th singular value of C.
Drawing from prior research 62 for < < and k: 2 rank the following always holds true:
|1 1 + III
minimize ||C|ss, VEReXt,VEReXe C=UVT
Thus, for < P 1, we define (U. |o(X) (X)UVT 3 + + as
relaxation of the optimization problem in Eq. ( without loss of generality. By employing the ADMM approach (61] and the gradient descent method [63] the U-update step (i.e., Line 4 in Algorithm 3) we design the KSL-Sp algorithm follows with details in the Appendix B.2
Algorithm 3 Kernel Self-expressive Learning with Schatten p-norm (KSL-Sp)
Input: K: a kernel matrix; A: a hyperparameter; maziter: maximum iterations: tol: tolerance.
Output: Ō RoxR; the optimal affinity matrix of Eq. (9) b Refer to Appendix B.2 for formula derivations.
1: Initialize Up, Vo-
2: for 0, 1...,, mariter do
3: U-update: U4+1 + Lv,,, = -KK I)V, + XU = 0;
4: V-update: V2+1 + 2KU++1 KU,+1 AI) by By 0.
5: if ][U++11 - UellF < tol then; break; end if.
6: end for
7: Set C. U.V and Ć (IC, + 1/2
4.2 Adaptive Kernel Self-eppressive Learning
To achieve adaptive affinity learning on incomplete data, we formulate new joint optimization problem by incorporating KLSR [3] and kernel correction learn kernel and affinity matrices
iteratively with the PSD constraint of K:
minimize K=
|| - k Tr(K - 2KC + + (L)CCCC)++ KC) +|[C|
(10)
Firstly, we introduce an auxiliary variable A E Buxn into
minimize K=ERA
|K-- Tr(A 2AC' + CT AC) + X|CCI subject to K= (11)
and then we derive the augmented I. Lagrange function L(K, A, C,U) in preparation for ADMM:
L K 1 Tr(A 2AC + C. AC) >|C Tr(U (K A)) + - All (12)
where U is a Lagrange multiplier and is the updating step size, finally arriving the Algorithm
7

---

Our adaptive learning framework could be combined with other kernel self self-expressive learning algo- rithms; however, due space constraints, further research is required to explore these possibilities:
minimize K=0,CER*X"
|K - 1 + +xllo(X)) o(X)C|) + AgR(CC) where K := x(X) T 6(x). (13)
Algorithm 4 Adaptive Kernel Least-Squares Representation (AKLSR)
Input: K": an initial kernel; X, pt hyperparameters, mariter: maximum iterations; tol: tolerance.
Output: Ö' R=x=; the optimal affinity matrix of Eq. (TO).
1: Initialize Ko. Ao, Co, Vg-
Refer to Appendix B.3 for formula derivations.
2: for = 0, 0....... mariter do
3: K-update: K + p42 (2K) U2 pAi)) by 8K 0:
ac
4: K-PSD: K,+1 + Pi (K) by projecting K onto the PSD set via Eq. 6
5: A-update: A +
p (p + U2 + 2C C.C. 1) by 04 0:
6: C-update: C++1 2(221 + A + A ( A4+ by dc
ac
= 0:
7: U'updaae: U141 + Ut + p(K++1 A(+1).
8:
if [[ - Cillr tol then; break; end if.
9:
end for
10: Set C= (1Cal + 1/2..
5
Experiments
We evaluate the performance on four benchmark datasets, including two face image datasets Yale64 [64] and Umist [65]. a handwritten digit image dataset USPS [66], and speech dataset Isolet [67]. We use a subset of USPS with 1,000 randomly selected samples. All experiments are conducted TtinkStation with 2.1 GHz Intel 17-12700 Core and 32GB RAM.
five times in MATLAB
Various methods dealing with incomplete data are considered for comparison: 1) statistical imputation:
ZERO, MEAN, k- k-nearest neighbors (kNN) (26]. Expectation Maximization (EM) 68]: 2) matrix
completion: Singular Value Thresholding (SVT) [27), Grassmanian Rank-one Update Subspace
Estimation (GR) (28) Kernelized Factorization Matrix Completion (KFMC) [29]: 3) distance
calibration: Centeiin (DC) (38), Triangle Fixing (TRF) (35), Euclidean Embedding (EE)
39
Our KC method uses the spectral decomposition (SD). Details are provided in Appendix C
5.1
Validation of Kernel Correction on Gaussian Kernel and Euclidean Distance
When handling incomplete data that is missing completely at random, the quality of the estimated Gaussian kernel matrix and Euclidean distance matrix is measured using the relative-mean meaes--uraa--uuueee
and the relative error (RE- = ||-1F where A is the naive ker- error (RMSE = || - --
nel/distance matrix obtained by Eq. @.. A is the estimated one using different methods, and A the ground-truth. All Gaussian kernels are calculated by k; = exp(-d?; /o2), where o = median ( dd.;) Our KC algorithm yields Gaussian kernel and Euclidean distance matrices with the lowest RMSES and REs, validating the theoretical guarantee of kernel matrices in Theorem [ as demonstrated in Table 1 Furthermore, the accuracy of the top-10 nearest neighbors evaluated using Recall values (69. The KC algorithm achieves the highest Recalls with improved local relationships, which in turn benefits spectral clustering, particularly for ANN graphs. More numerical results are in Appendix D
Table 1: Quality comparisons of Gaussian kernel and Euclidean distance under a missing ratio 80%.
Dataset Metrie
Naive ZERO
MEAN
ANN
EM
SVT
GR
KFMC
DC
TRF
EE
KC
RMSE-K]
1.000
2,849
1.535
2.451
1.527
2,849 1.797
3.818
1.748 0.923 0.438
0.382
RMSE-DJ,
1.000
20.80
27.64
21.20
27.62
20.80 8.397
14.05
110.4 0.916 0.440 0.431
Umist
RE-K]
0.189
0.319
0,234
0,295
0.233
0.319 0.253
0.369
0,250
0,181 0.125 0.117
RE-DD
0.107
0.487
0.561
0.492
0.561
0.487
0.309
0.400
1.122
0.102 0.071
0.070
Recall
0.726 0.092
0.171
0.119
0.1 0.092 0.596
0.248
0.226 0.740 0.771 0.785
Codes are available at ht hww.lll.iiiiipss///tt....oo/oola http://tttbbccccceeesss/sttaaaaa
on- Iww.onneeeeeeeeee Data.

---

5.2 Comparative Studies on Standard Spectral Clustering
We adopt the Gaussian kernel for standard spectral clustering and obtain its ANN graph (A 10), as the imput for clustering via the normalized cut algorithm [] We evaluate the clustering performance using Accuracy (ACC), Normalized Mutual Information (NMI, Purity (PUR), and Adjusted Rand Index (ARI). Table shows that our KC algorithm, which corrects the Gaussian kernel, achieves the best clustering performance under a large missing ratio 80% (i.e., missing completely random).
Table Performance of standard spectral clustering on incomplete data under missing ratio 80%.
Dataset
Metric
Naive
ZERO
MEAN
KNN
EM
SVT
GR
KFMC
DC
TRF
EE
KC
ACC
0.561
0.218
0.365
0.227
0.374
0.224
0.218
0.259
0.513
0.562
0.573
0.578
NMT
0.588
0.246
0.429
0.257
0.428
0,269
0.264
0.297
0.551
0.587
0.593
0.596
Yale64
PUR
0.572
0.233
0.390
0.241
0.396
0.241
0.232
0.273
0.525
0.570 0.581
0.584
ARI
0.353
0,010
0.137
0.015
0.145 0,017
0,012
0,035
0.293
0,350
0.357
0.366
ACC
0.462
0.220
0.351
0.230
0.349 0.218
0,410
0.314
0.350
0,462 0.461
0.463
NMI
0.669
0.282
0.478
0.314
0.479 0.286
0.597
0.423
0.488
0.667 0.669
0.673
Umist
PUR
0.549
0.245
0.415
0.261
0.419 0.247
0.502
0,366
0,408
0.546 0.551
0.553
ARI
0.373
0.070
0.206
0.082
0.207 0.067 0.304
0.140
0.216
0.370 0.371
0.377
ACC
0.343
0.350
0,362
0.360
0.222 0,353 0.375
0.351
0,418
0.464 0.511
0.523
NMI
0.222
0.228
0.278
0.265
0.104 0.236
0.319
0.358
0.312
0.393 0.457
0.472
USPS
PUR
0.395
0.400
0.434
0,427
0.260 0,402
0.440
0.460
0,473
0.535 0.594
0.609
ARI
0.168
0.164
0.180
0.175
0.051 0.167
0.206
0.178
0.231
0.304 0.344
0.360
ACC
0.495
0.260
0.245
0.297
0.172 0.263
0.357
0.324
0.243
0.515 0.560
0.561
NMI
0.613
0.339
0.330
0.383
0.228 0,342 0.492
0.465
0.323
0.643
0.660
0.672
Isolet
PUR
0.520
0.278
0.261
0.318
0.183 0.277 0.377
0.354
0.260
0.542
0.584 0.593
ARI
0.364
0.126
0.108
0.159
0.055 0.131 0.210
0.177
0.105
0.387 0.429 0.432
We also examine robustness across varying missing ratios. Fig. 1 shows the KC method's 's advantage over imputation, especially at large missingness. Numerical results are in Appendix E
The KC method consistently surpasses others in kernel estimation, evidenced by reduced relative errors (RE-K) and enhanced neighborhood ties in the kNN graph, seen through higher Recall values.
At small missing ratios, the KC method offers incremental improvements over imputation. However, at large missing ratios, imputation methods falter due to scant observed data, leading to increased errors and compromised clustering. Conversely, the KC method maintains stable clustering outcomes.
O ZERO + MEAN A KNN + EM -X SVT +B GR 4 KFMC KC
0.4
1.0
0.4
Y Vale64
0.3
0.8
0.3
RE-K
Recall
0.6g
0.2
0.2
0.4
0.1
0.1
Yale64
Y Yale64
0.0
0.0
0.0
20%
40%
60%
80%
20%
60% Missing Ratio r
40%
80%
20%
40%
60%
80%
Missing Ratio
Missing Ratio r
0.4
1.0
0.5
Umist
0.3
0.8
0.4
RE-K
Recall
0.6
0.3
0.2
0.4
0.2
0.1
0.2
0.1
Umist
Umist
0.0
0.0
0.0
20%
40%
60%
80%
20%
40%
60%
80%
20%
40%
60%
80%
Missing Ratio r
Missing Ratio
Missing Ratio r
Figure 1: Robustness analysis of kernel estimation, neighborhood relationship, and standard spectral clustering on the Yale64 and Umist datasets under wide range of missing ratios, i.e., E [20%, 80%).

---

5.3 Comparative Studies on Self-expressive Affinity Learning
We delve deeper into the advantages of the corrected Gaussian kernel in kemee self- expressiee affinity learning, encompassing methods like KSSC [19, KLSR []. KSL-Sp, and AKLSR, with KSL-Pp excluded due its impracticality, As Table 3 Jillustrates, our KC method excels over baselines in the NMI. Notably, both KSI-Sp and AKLSR algorithms employ corrected kemnels to yield dependable affinity matrices, thereby elevating performance. Furthermore, our imputation-Fi framework could augment spectral clustering using other kernels, such as the Exponential kernel. A comprehensive comparison and in-depth analysis are available in Appendix F. Collectively, our study presents a holistic approach to clustering incomplete data, paving the way for subsequent research.
Table 3: NMI performance of self-expressive affinity on incomplete data under a missing ratio 80%.
Method
Dataset
Naive
ZERO
MEAN
&NN
EM
SVT
GR
KFMC
DC
TRF
EE
KC
Yale64
0.219
0.215
0.167
0.173 0.177 0.218 0.208
0.259
0.588
0.210 0.209
0.616
Umist
0.101
0.151
0.198
0.154
0.178 0.141 0.639
0.254
0.123
0.121 0.139
0.714
KSSC
USPS
0.017
0.196
0.396
0.271
0.222 0.200 0,360
0.359
0.077
0.018 0.025
0.410
Isolet
0.065
0.024
0.153
0.384
0.382 0.022 0.454
0.292
0.171
0.064 0.062
0.582
Yale64
0.606
0.311
0.604
0.320
0,609 0.321 0.327
0,318
0.597
0.603 0,604
0.616
Umist
0.676
0.579
0.640
0.538
0.638 0.576 0.630
0.548
0.647
0.671 0.687
0.696
KLSR
USPS
0.019
0.225
0.417
0.317
0.235 0.231 0.356
0.360
0.418
0.019 0.420
0.485
Isolet
0.215
0.398
0.548
0.463
0.400 0.400 0,551
0,512
0.522 0.306 0,628
0.659
Yale64
0.370
0.315
0.581
0.303
0.579 0.305 0.304
0.295
0.555
0.364 0.599
0.619
Umist
0.144
0.453
0.595
0.485
0,592 0.454 0.672
0.443
0.616
0.152 0.680
0.690
SSL-Sp
USPS
0.073
0.288
0.360
0.342
0.196 0.285 0.331
0.439
0.238
0.055 0.517
0.524
Isolet
0,266
0.410
0,556
0.487
0.364 0,410 0.485
0.557
0,383
0,246 0.624
0.634
Yalc64
0.452
0.327
0.606
0.338
0.605
0.308
0.338
0.312
0.570
0.464
0.575
0.614
Umist
0.379
0.490
0.624
0.498
0.620 0.484
0.691
0.456
0.611
0.350 0.626
0.691
AKLSR
USPS
0.021
0.114
0.336
0.235
0.236
0.115
0.098
0.017
0.327
0.031
0,259
0.365
Isolet
0.100
0.246
0.448
0.381
0.370 0.246 0.069
0.072
0.453
0.119
0,411
0.496
5.4
Spectral Clustering on Block-missing Data: A Case Study
Beyond the experiments addressing data missing completely at random, we generate a block of appro- priate sizes located randomly in images and values in the block are missing where the missingness is systematically related to locations. As illustrated in Table 4 under this block-missing paradigm (70). our KC method persistently outperforms existing data imputation and distance calibration techniques.
Table 4: NMI performance of self-expressive affinity on block- data under a missing ratio 80%. Bold font indicates the best, and underline indicates the second-best,
Dataset
Method
Naive
ZERO
MEAN
ENN
EM
SVT
GR
KFMC
DC
TRF
EE
KC
KSSC
0.217
0.340
0.526
0.379
0.530
0.376
0.342
0.496
0.482
0.207
0.212
0.562
KI.SR
0.592
0.336
0.544
0.365
0.534
0.365
0.338
0.533
0.484
0.596
0.585
0.592
Yale64
KSL-Sp
0.488
0.335
0.540
0.367
0.544
0.366
0.343
0.543
0.481
0.484
0.584
0.591
AKLSR
0.548
0.342
0.544
0.367
0.539
0.378
0.342
0,540
0.467
0.546
0.578
0.605
Conclusion and Future Work
In this paper, we propose an imputation-free framework for spectral clustering on incomplete data. Our framework directly learns high-quality affinity matrices via kernel correction and affinity learning, improving clustering performance. We introduce a novel kernel correction method with theoretical guarantee, new affinity learning methods, and an adaptive extension that simultaneously learns high-quality kernel and affinity matrices. Extensive experiments demonstrate the effectiveness of our proposed methods on various benchmark datasets, showing superior performance compared to existing data imputation and distance calibration approaches. Our work provides a systematic solution to clustering incomplete data, with future work focused on integrating with deep clustering methods for various types of incomplete data and enhancing the speed and scalability of the algorithms.
10

---

Acknowledgments
We appreciate the anonymous reviewers for their insightful feedback that greatly enhanced this paper. The work of Fangchen Yu and Wenye Li was supported in part by Guangdong Basic and Applied Basic Research Foundation (2021A151501822) Teams Fund (20172T07X152) Shenzhen Science and Technology Program (CUHSSZWDZC004)) and Shenzhen Research Institute of Big Data Scholarship Program. The work of Jicong Fan was partially supported by the Youth program 62 62106211 of the National Natural Science Foundation of China The work of Yicheng Zeng was supported by the Shenzhen Science and Technology Program (Grant No. RCBS2022 000002200000930 100809333606)), the Youth Program (Grant No. 12301383) of National Natural Science Foundation of China, and the Internal Project Fund from Shenzhen Research Institute of Big Data (Grant No. J00220230012). The work of Jianfeng Mao was supported in part by the National Natural Science Foundation of China (NSFC) under grant U1733102, in part by the National Natural Science Foundation of China (NSFC) under grant 72394362, in part by the Guangdong Provincial Key Laboratory of Big Data Computing. The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen) under grant B B101202101 17, and in part by CUHK-Shenzher under grant PF.01.00040
Guangdong Introducing Innovative and Entrepreneurial
References
[1] Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001.
[2] Ulrike Von Luxburg. tutorial on spectral clustering. Statistics and Computing, 17:395 416, 2007.
[3] Jicong Fan, Yiheng Tu, Zhao Zhang, Mingbo Zhao, and Haijun Zhang. A simple approach to automated spectral clustering. Advances in Neural Information Processing Systems, 35:9907- 9921, 2022.
[4] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888--9)) 9905, 2000.
[5] Stella X Yu and Jianbo Shi. Multiclass spectral clustering. In IEEE International Conference on Computer vision, volume 2, pages 313-313. IEEE Computer Society, 2003.
[6] Víctor Mijangos, Gerardo Sierra, and Azucena Montes. Sentence level matrix representation for document spectral clustering. Pattern Recognition Letters, 85:29-34, 2017.
[7] Tae Jin Park, Kyu Han, Manoj Kumar, and Shrikanth Narayanan. Auto-tuning spectral clustering for speaker diarization using normalized maximum eigengap. IEEE Signal Processing Letters, 27:381-385 2019.
[8] Marcilio CP De Souto, Ivan G Costa, Daniel SA de Araujo, Teresa B Ludermir, and Alexander Schliep. Clustering cancer gene expression data; a comparative study. BMC Bioinformaties, 91):1-14, 2008.
[9] Seyoung Park and Hongyu Zhao. Spectral clustering based on learning similarity matrix. Bioinformatics, 34(12):2069-20 2076, 2018
[10] Nauman Shahid, Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, and Pierre Van- dergheynst. Robust principal component analysis on graphs. In Proceedings of the IEEE International Conference on Computer Vision, pages 2812-202 2812-2820, 2015.
[11] Jicong Fan and Tommy W.S. Chow. Sparse subspace clustering for data with missing entries and high-rank matrix completion. Neural Networks, 93:36-44, 2017.
[12] Jicong Fan. Large-scale subspace clustering via k-factorization. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 342-352, 2021.
[13] Jicong Fan and Tommy W.S Chow. Exactly robust kernel principal component analysis. IEEE Transactions on Neural Networks and Learning Systems, 31(3):749-761) 2020.

---

[14] Jicong Fan, Chengrun Yang, and Madeleine Udell. Robust non-lineat matrix factorization for dictionary learning, denoising, and clustering. IEEE Transactions on Signal Processing. 69:1755-1770, 2021.
[15] Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applica- tions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(11):2765 -2811, 2013.
[16] Guangean Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, and Yi Ma. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):171-184, 2012.
[17] Can-Yi Yi Lu, Hai Min, Zhong- Qiu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. In European Conference on Computer Vision, pages 347-360. Springer, 2012.
[18) Pan Ji, Mathieu Salzmann, and Hongdong Li. Efficient dense subspace clustering. In IEEE Winter Conference on Applications of Computer Vision, pages 461-466 IEEE, 2014.
[19] Vishal M Patel and René Vidal. Kernel sparse subspace clustering. 2014 IEEE International Conference Image Processing, pages 2849-2853. IEEE, 2014.
[20] Shijie Xiao, Mingkui Tan, Dong Xu, and Zhao Yang Dong. Robust kernel low-rank repre- sentation, IEEE Transactions on Neural Networks and Learning Systems, 27(11):2268-22 22811, 2015.
[21] Bradley Efron. Missing data, imputation, and the bootstrap. Journal of the American Statistical Association, 89(426):463-47, 1994.
[22] Wei-Chao Lin and Chih-Fong Tsai. Missing value imputation: a review and analysis of the literature (2006-2017). Arlificial Intelligence Review, 53:1 13:1499-,, 2020.
[23] Tressy Thomas and Enayat Rajabi. A systematic review of machine learning-basse missing value imputation techniques. Data Technologies and Applications, 55(4):558-585, 2021.
[24] Susanne Rässler, Donald B Rubin, and Elizabeth R Zell. Imputation. Wiley Interdisciplinary Reviews: Computational Statistics, 5(1):20-29, 2013.
[25] Ton De Waal, Jeroen Pannekoek, and Sander Scholtus. Handbook of Statistical Data Editing and Imputation, volume 563. John Wiley Sons, 2011.
[26] Lorenzo Beretta and Alessandro Santaniello. Nearest neighbor imputation algorithms: a critical evaluation. BMC Medical Informatics and Decision Making, 1673):197-208, 2016.
[27] Jian-Feng Cai, Emmanuel J Candès, and Zuowei Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 1956):1956 2010.
[28] Laura Balzano, Robert Nowak, and Benjamin Recht. Online identification and tracking of subspaces from highly incomplete information. In 48th Anmual Allerton Conference on Commu- nication, Control, and Computing, pages 704-711. IEFF, 2010.
[29] Jicong Fan and Madeleine Udell. Online high rank matrix completion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8690-8669 8698, 2019.
[30] Jicong Fan. Dynamic nonlinear matrix completion for time-varying data imputation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6587-6596. 2022.
[31] Fangchen Yu, Yicheng Zeng, Jianfeng Mao, and Wenye Li. Online estimation of similarity matrices with incomplete data. In Uncertainty Artificial Intelligence, pages 2454-2466
PMLR, 2023.
[32] Elzbieta Pekalska and Robert PW Duin. The dissimilarity representation for pattern recognition foundations and applications. Series Machine Perception and Artificial Intelligence, 64, 2005.
12

---

[33] Frank-Michael Schleif and Peter Tino. Indefinite proximity learning: A review. Neural Computation, 27(10):2039-206 2096, 2015.
[34] Suvrit Sra, Joel Tropp, and Inderjit Dhillon. Triangle fixing algorithms for the metric nearness problem. Advances in Neural Information Processing Systems, 17, 2004.
[35]
Justin Brickell, Inderjit S Dhillon, Suvrit Sra, and Joel A Tropp. The metric nearness problem. SIAM Journal on Matrix Analysis and Applications, 30(1):375-396, 2008.
[36]
Wenye Li, Fangchen Yu, and Zichen Ma. Metric nearness made practical. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8648-8656, 2023.
[37] Arijit Biswas and David W Jacobs. An efficient algorithm for learning distances that obey the triangle inequality. In British Machine Vision Conference, pages 10-1, 2015.
[38] Andrej Gisbrecht and Frank-Michael Schleif. Metric and non-metric proximity transformations at linear costs. Neurocomputing, 167:643-657, 2015.
[39] Wenye Li and Fangchen Yu. Calibrating distance metries under uncertainty. In Joint European Conference on Muchine Leurning and Knowledge Discovery in Databases, pages 219-234. Springer, 2022.
[40] Fangchen Yu, Rui Bao, Jianfeng Mao, and Wenye Li. Highly-efficient robinson-foulde distance estimation with matrix correction. In 26th European Conference on Artificial Intelligence, pages 2921, 2023.
[41] Fangchen Yu, Zhan Shi, Yuqi Ma. Jianfeng Mao, and Wenye Li. From incompleteness unity: A framework for multi-view clustering with missing values. International Conference on Neural Information Processing, pages 101-112, 2023.
[42] Liu Yang and Rong Jin. Distance metric learning: A comprehensive survey. Michigan State Universiy, 2(2):4, 2006.
[43] Nathan Krislock and Henry Wolkowiez. Euclidean distance matrices and applications. In Handbook on Semidefinite, Conic and Polynomial Optimization, pages 879-914. 14. Springer, 2012.
[44] John Clifford Gower. Fuclidean distance geometry. Mathematical Scientist, 7(1):1-14, 1982.
[45] Warren S Torgerson. Multidimennsional scaling: I. theory and method. Psychometrika, 17(4):401-
419, 1952.
[46] Isaac Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522-536, 1938.
[47] Wenye Li. Estimating Jaccard index with missing observations: a matrix calibration approach. Advances Neural Information Processing Systems, 28, 2015.
[48] Wenye Li. Scalable calibration of affinity matrices from incomplete observations. In Asian Conference on Machine Learning, pages 753-768. PMLR, 2020.
[49] Rafic Nader, Alain Bretto, Bassam Mourad, and Hassan Abbas. On the positive semi-definite property of similarity matrices. Theoretical Computer Science, 755:13-28, 2019.
[50] Frank R Deutsch. Best Approximation in Inner Product Spaces. Springer Science & Business Media, New York, US, 2012.
[51] Richard L Dykstra. An algorithm for restricted least squares regression. Journal of the American Statistical Association, 78(384):837-88) 1983.
[52] James P Boyle and Richard L Dykstra. A method for finding projections onto the intersection of convex sets in hilbert spaces. In Advances in Order Restricted Statistical Inference, pages 28-47, Springer, 1986.
[53] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review 53(2):217-288, 2.11.
13

---

[54] Norbert Gaffke and Rudolf Mathar. A eyclic projection algorithm via duality. Metrika, 36(1):29- 54, 1989.
[55] Alex J Smola, SVN Vishwanathan, and Thomas Hofmann. Kernel methods for missing variables. In International Workshop on Artificial Intelligence and Statistics, pages 325-332. PMLR, 2005.
[56] Uwe Dick, Peter Haider, and Tobias Scheffer. Learning from incomplete data with infinite imputations. In Proceedings of the 25th International Conference on Machine Learning, pages 232-239, 2008.
[57] Xinwang Liu, Xinzhong Zhu, Miaomiao Li, Lei Wang, En Zhu, Tongliang Liu, Marius Kloft, Dinggang Shen, Jianping Yin, and Wen Gao. Multiple kernel k-means with incomplete kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, (2(5):191-122) 2019.
[58] Shichao Zhang, Zhi Jin, Xiaofeng Zhu, and Jilian Zhang. Missing data analysis: kernel-based multi-imputation approach. Transactions on Computational Science III, pages 122-142, 2009.
[59] Chiu-Hsieh Hsu, Yulei He, Yisheng Li, Qi Long, and Randall Friese. Doubly robust multiple imputation using kernel-based techniques. Biometrical Jourmal, 5863):888-606, 2016.
[60] Xiaojun Chen, Fengmin Xu, and Yinyu Ye. Lower bound theory of nonzero entries in solutions of lz-lp minimization. SIAM Journal on Scientific Computing, 32(5):2832-2855, 2010.
[61] Stephen Boyd, Neal Parikh, Eric Chu, Borja Pelcato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and @rends@ in Machine learning, 3(1):1-12) 2011.
[62] Fanhua Shang, Yuanyuan Liu, and James Cheng. Unified scalable equivalent formulations for schatten quasi-norms, arXiv preprint arXiv:1606.00 00668, 2016.
[63] Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint 1MXXi::609.047400 2016.
[64] Peter N. Belhumeur, Joao P Hespanha, and David J. Kriegman. Eigenfaces vs. fisherfaces: Recognition using class specific linear projection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):711-72M 1997.
[65] Daniel B Graham and Nigel M Allinson.
Characterising virtual cigensignatures for general purpose face recognition. Face Recognition: From Theory To Applications, pages 446-456, 1998.
[66] Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions Pattern Analysis and Machine Intelligence, 16(5):550-554, 1994.
[67] Ron Cole, Yeshwant Muthusamy, and Mark Fanty. The isolet spoken letter database, 1990. algorithm. IEEE Signal Processing Magazine,
[68] Todd K Moon. The 13(6):7760, 1996.
[69] Changyi Ma, Fangchen Yu, Yueyao Yu, and Wenye Li. Learning sparse binary code for maximum inner product search. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 3308-3312, 2021.
[70] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16000-16009, 2022.
[71] Richard V Kadison. The pythagorean theorem: the finite case. Proceedings of the National Academy of Sciences, 99(7):4178 4184, 2002.
[72] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK, 2004.
[73] David Luenberger. Linear and nonlinear programming second edition. Columbus, Ohio: Addison- Addison-Wesley, Wesley, 1984.
14

---

Supplementary Material
Boosting Spectral Clustering on Incomplete Data via Kernel Correction and Affinity Learning
This document serves as supplementary material for the paper entitled "Boosting Spectral Clustering on Incomplete Data via Kernel Correction and Affinity Learning". It contains a theoretical analysis with proofs and formula derivation of theorems and algorithms presented in the main paper, a detailed description of experimental settings, and additional numerical results. Specifically,
Sec. A and provide the proof of Theorem and the formula derivations of Kernel Self-
expressive Learning (KSL) algorithms with adaptive extension, respectively:
Sec. illustrates experimental settings and implementation details;
Sec. D
validates the benefits of the kernel correction algorithm on kerne and distance estimation;
Sec. B
and present comprchensive results and in-depth analysis clustering performance.
A Theoretical Property of Kernel Correction
Theorem | Rll S K Kr The equality holds if and only if K 2 0, ie., K K.
Proof. Denote the feasible region as F, which is a closed convex set. Let K be the initial kernel matrix. Let K be the projection of K onto F (K- minkee ||-|| - - Let K be the unknown ground-truth with positive semi-definiteness (PSD) in the feasible region F. By definition, we have:
| - 1 S I 1
Adding and subtracting K in the right-hand side, we get:
K K- = IK* K K K - 12
By the Pythagorean theorem
we have:
|| k - K - k K 1 + 1 -ok>>11 2(K x - R K R)F,
k01
where F. denotes the Frobenius inner product. Since K is the projection of K onto the feasible
region F, have (K- K R K)F F S for all PSD matrices K in F (72). Therefore, have:
I 1 = パ k k 1 z K
R + K - 1
K is already PSD matrix in F. we have:
K = K and | - k0 1K - RIP
Otherwise, we obtain:
K k0 0,
which implies:
|K* K 1/ K - -
(14)
Thus, we have ||K* K||F S IKK* KºI F. which provides an improved estimate R K*
15

---

B Formula Derivations of Kernel Self-expressive Learning
B.1 Formula Derivations of Kernel Self-expressive Learning with Proximal p-norm
Due to the non-convex nature of the 2 term and the penalty term, finding closed-form solution for the Zuppdate is not straightforward. However, we can relax the matrix optimization to element- wise optimization without loss of generality, thanks to the format of our chosen objective function. Below, we present the deriving process:
1
L = > +
max 1.0) + Tr(U (2 (2- + - IZ - C
2p
A Σ (z1))) + max(=i) - 1,0) + Σ
1
(zij cij) )2 Uiy (zr ci))
2p
1
Σ (Aef) + yل!(zيz1) (215 12i--11 1) +
(2) c,)² + uny (2+g -ct))).
2p
(1, if zgj > is an indicator function and C, C +lx((x o(x)o
where 1(x=>1)
10, otherwise.
We can use solver to find out the Z-update via
Ohp = Ap2y + (l(y)>1) + (z:s cij) + usj = 0.
Ozig
Using the Alternating Direction Method of Multipliers (ADMM) approach 661, we can update the variables as follows.
C-update: Update by minimizing the augmented Lagrangian with respect to C:
C++1 arg min C, Z,
= (2K - 1 (2K + U. + -2),
where K == 5(X)To(X)) 6(X) and I, is the identity matrix of size X n.
Z-update: Update Z via solving
aCp Xp= + ( + 1 (21s csj) + usj
0zij
* U-update:
Update U via
U++1= = U.+ p(z C.+1).
We employ the ADMM process to solve the problem using the augmented Lagrangian function. However, despite the existence of a derivation method for this process, the computation proves to be excessively slow due to the following factors:
Matrix inversion: Inverting (2K 7 11a has a computational complexity of O
Solver for Z-update: The golden-section solver is chosen update 2ij. resulting in an approximate computational complexity of log(L) for each entry 773 which is relatively high.
Additionally, some potential complex solutions may arise when performing the element-wise update. As result, provide the algorithm for future researchers further investigate and optimize.
16

---

B.2 Formula Derivations of Kernel Self-expressive Learning with Schatten p-norm
For <p< < I, we can define relaxation of the optimization problem as:
1 + + - IV
Cs -
With this definition, we can employ gradient descent to update the variables iteratively. The main steps of the algorithm are as follows:
U-update: Compute the gradient of Ls, with respect U::
aLs,
OU 2K(UVT IIV + AU,
where K = ( ((X).
((X)) Update U according to the gradient:
Unew Uold vs
where is the learning rate.
Vuupdtte: Use the closed-form solution
= (2 KU + A7)
Convergence condition:
If the difference between the updated and the old U less than a pre-defined tolerance (|lU Ustal ?- < tol), the algorithm is considered converged, and we can terminate the loop. Otherwise, continue iterating with the new and values.
Upon convergence, the affinity matrix can be computed as A= (IC) + /// where C UVT This algorithm provides an efficient way to update the Schatten p-norm in the proposed KSL-Sp model, enhancing its robustness and clustering accuracy.
B.3 Formula Derivations of Adaptive Kernel Least-Squares Representation
The problem that we are doing with is:
|K - 1 + Tr(K 2KC + CT KC) + Kzu,c
min
Then derive the augmented Lagrange equation in preparation for ADMM
By introducing auxiliary variable A, we have:
min |K - 1 + Tr(A- Tr(A-AAC- + CT AC) + K=
s.t. K
Augmented Lagrange equation is calculated by
((K,ACCU)) = |K K Tr(A - 2AC + CT AC) + AICC
+ TTr A)) + K - Al]
where U is Lagrange multiplier, p is the updating step size.
ADMM consists of iteratively updating K, A, C, and U as follows:
1. K K-update: K arg mink L(K, A., Cr, U.). By First-Order Necessary Condition (FONC),
we have
0C aK = 0 -
2 + PA
2+2
2. K-PSD: K +- PI(K) by projecting K onto the PSD set via Eq. 6
17

---

3. A-update: A++1 - arg mig, [(K++1, C,, Ut). By FONC, we have
Uc
0A - PA + (1 - -C +CC - -p) -0
= pK + U +22 -COT -1
P
4. C-update: C++1 = arg ming L(Ki+1, ALt1, C,U,) By FONC, we have
OC = (2XI + A A 24T
0C
= C = 2(2 + +A+
5. U-update:
U211 U. + p(Kt+1 A(+1).
C Experimental Settings
C.1
Datasets
To evaluate the performance of our proposed approaches, we select four benchmark datasets com- monly used in machine learning and computer vision, including:
The Yale64 dataset consists of face images of 15 different individuals, each with different facial expressions, lighting conditions, and facial details. It contains total of 165 images of size 64 x 64 pixels in (.096-dimension vectors.
Yale64 64
The Umist dataset consists of face images of 20 different individuals, each with different facial expressions, lighting conditions, and facial details. It contains total of 575 images of size 32 x 32 pixels in
Umist 665
vectors.
The USPS dataset consists of handwritten digit images of size 16 x 16 pixels in 10 classes. For the five repeated experiments in this paper, we use five different random seeds to randomly select 1,000 images with 256-dimensional vectors as subset.
USPS [66
The Isolet dataset a speech dataset that contains recordings of 26 different speakers pronouncing the names of the English alphabet. It contains 1 1,560 recordings and each recording is of 617-dimensional vectors.
Isolet 67
C.2 Baselines
The proposed approaches are evaluated against range of baseline methods, including
ZERO:
This statistical imputation method replaces missing values with zeros.
MEAN: This statistical imputation method replaces missing values with the mean value of all observed values the corresponding features.
ANN 26 : This statistical imputation method predicts missing values based on the values of
the k- neneetsst neighbors in the available data. (default value & = 10)
EM 68) This statistical imputation method estimates the missing values based on the Expectation Maximization algorithm.
SVT (27 This matrix completion method uses singular value thresholding algorithm to find the low-rank matrix that best fits the available data.
This matrix completion method uses an online algorithm to estimate the low-rank subspace of the data and then updates the subspace with data points.
GR 28]
hhtps://cs.yu..cduu awweiv/data/mmiss_croppee
"htpps//cs..yu..dd" wwwcis/data/usps_all.oo
'ntt://archive.. www.:iiwwww..iii.eideddeaaeaaaaa wwd..e/d/m//aaatsss//sSLLL
18

---

This matrix completion method uses kernelized factorization approach to estimate the high-rank matrix that best fits the available data. (default: polynomial kernel)
KFMC [2)]
DC [8] This distance calibration method calibrates an initial distance matrix through
double centering algorithm and transformation between similarity and distance.
TRF 35 : This distance calibration method calibrates an initial distance matrix to satisfy
all the triangle inequalities by solving a convex optimization problem.
EE [39] This distance calibration method calibrates an initial distance matrix to Euclidean embeddable matrix by solving a convex optimization problem. (default value ? max (c))
0.02
C.3 Implementation Details
Data Preprocessing. To obtain better clustering performance, we conduct different preprocessing strategies. In the Yale64 and USPS datasets, we use the original data without preprocessing: in the Umist and Isolet datasets, we perform the normalization to normalize all data samples into [-1, 1].
Generation of Incomplete Data. For experiments in Sections 5.1 incomplete data matrix X by randomly replacing each value in the data matrix X E Raxx with an NA value with given probability (missing completely at random). We repeat this process five times and report the average performance of the baseline methods using X as input.
5.2 and 5..
generate an
Data Imputation Methods. We first impute the missing values in X and then calculate the kemell matrix based the imputed matrix X. We then perform spectral clustering the kernel matrix.
Distance Calibration Methods. We first estimate an initial distance matrix D on the incomplete data matrix X via Eq. [I. We then calibrate D to D and calculate the kernel matrix based on D. We finally perform spectral clustering the resulting kernel matrix.
D Validation of Kernel Correction on Kernel and Distance Estimation
Two errors, relative-mean -quare error (RMSE- = - and relative error (RE IIÁ-A
A
||
are used to evaluate the estimation accuracy, where A is the naive kernel/distance matrix obtained by Eq. (T. Á is the estimated one using different methods, and A as the ground-truth. Besides, Recall measures the search accuracy of local relationships, which is defined the overlapping ratio of two sets of top-10 10 similar items obtained by À and A", respectively.
Table 5: Quality comparisons of Gaussian kernel and Euclidean distance under missing ratio 80%.
Dataset Metric
Naive
ZERO
MEAN
ANN
EM
SVT
GR
KFMC
DC
TRF EE
KC
RMSE-K K.
1.000
11.52
3.009
11.46
3.009
11.39
11.13
8,838
2.564 0.994 0.741 0.624
RMSE-D DJ
1,000
12.45
76.82
14.26
76.82 12.52 12.27
11.62
37.97 0.995 0.755 0.674
Yale64
RE-K]
0.113
0.382
0.195
0.381
0.195 0.380 0.376
0.335
0.180
0.112 0.097 0.089
RE-D]
0.064
0.227
0.564
0.243
0,564 0,228
0.225
0,219
0.396
0.064 0,056 0.053
Recall
0.721
0.063
0.275
0.063
0.275 0.066 0.070
0.183
0.571 0.722 0.751 0.767
RMSE-KJ
1.000
2.849
1.535
2,451
1.527 2.849 1.797
3.818
1.748
0.923 0.438 0.382
RMSE-D
1.000
20.80
27.64
21.20
27.62 20.80 8.397
14.05
110.4 0,916 0.440 0.431
Umist
RE-KK.
0.189
0.319
0.234
0.295
0.233 0.319 0.253
0.369
0.250 0.181 0,125 0.117
RE-D..
0.107
0.487
0.561
0.492
0.561 0.487 0.309
0.400
1.122 0.102 0.071 0.070
Recall
0.726
0.092
0.171
0.119
0.172 0.092 0.596
0.248
0.226 0.740 0.771 0.785
RMSE-KJ
1.000
0.471
0.292
0.411
0.393 0.469 0.389
0.475
0.386
0.547 0,262 0.223
RMSE-DJ,
1.000
2.820
4.378
2.936 2.850 2.825 2.003
2.100
67.82
0.501 0.252 0.240
USPS
RE-KJ
0.460
0.316
0.248
0.295
0.287 0.315 0.287
0.317
0.286
0.340 0.235 0.217
RE-DI
0.268
0.451
0.562
0.460
0.445 0.451 0,380
0.389
2.210
0.190 0.135 0.132
Recall
0.071
0.054
0.065
0,069
0.036 0.054
0.122
0.196
0.056
0.161 0,186 0.197
RMSE-K K.
1.000
1.188
0.796
0.966
0.993 1.188 1.001
1.390
0.956
0.817 0.339 0.291
RMSE-D DJ
1.000
7.210
12.35
7.620
9.538 7.210 4.595
4.365
153.5
0.809 0.332 0.309
Isolet
RE-KJ K.
0.282
0.307
0.251
0.277
0.280 0.307 0.282
0.332
0.275
0.255 0.164 0.152
RE-DI
0.160
0.429
0.561
0.441
0.490
0.429
0.342
0.334
1.978
0.144 0.092 0.089
Recall?
0.254
0.045
0.050
0.059
0.034
0.045
0.187
0,225
0.041
0.299 0,270 0.300
19

---

E Comprehensive Experiments on Standard Spectral Clustering
The robustness analysis is depicted in Fig.Di in the main text, with accompanying numerical results in Table 6 Further, Fig. 2 displays clustering performance using ACC, NMI, and PUR metries, underscoring the KC method's superiority over imputation baselines, particularly at large missing ratios. Notably, as the missing ratio escalates, imputation methods' accuracy and clustering efficacy decline sharply. Specifically, missing ratios above 50%, their reliability wanes due to the paucity of data for imputation. In contrast, our KC method maintains consistent, and often superior, performance even with large missingness, exemplified by the results the Yale64 and Umist datasets.
Table 6: Robustness analysis of kernel and distance estimation, neighborhood relationship, and standard spectral clustering on Umist. Bold font indicates best, and underline indicates second-
Metrie
Missing
Naive ZERO
MEAN
ANN
EM
SVT
GR
KFMC
DC
TRF
EE
KC
20%
0.028
0.116
0.072
0.023
0.108
0.106
0.043
0.025
0.072
0.028
0.029
0.028
RE-K4
50%
0.066
0.232
0.157
0.115
0.180
0.232 0.111
0.076
0.162 0.065 0.062
0.057
80%
0.189
0.319
0.234
0.295
0,233 0.319
0.253
0.369
0.250
0.181 0.125
0.117
20%
0.016
0.087
0.112
0.055
0.138 0.088
0.055
0.029
0.110
0.016
0.017
0.016
RE-D|
50%
0.037
0.237
0.302
0.222
0.281
0.237
0.144
0.090
0.372
0.037
0.035
0.033
80%
0.107
0,487
0,561
0.492
0,561 0,487
0.309
0.400
1.122
0.102 0.071
0,070
20%
0.954
0.887
0,912
0.952
0,870 0.887 0,944
0.964
0.932
0.954
0.950
0.956
Recallf
50%
0.899
0.558
0.672
0.778
0.630 0.558
0.856
0.910
0.783
0.899 0.907
0.914
80%
0.726
0.092
0.171
0.119
0.172 0.092 0,596
0.248
0.226
0.740
0.771
0.785
20%
0.455
0.370
0.405
0.451
0.388 0.380 0.436
0.439
0.427
0.456
0.466
0.460
ARI1
50%
0.443
0.258
0.332
0.326
0.325
0.256 0.398
0.448
0.361
0.434
0.450
0.451
80%
0.373
0.070
0.206
0.082
0.207 0.067 0.304
0.140
0.216
0.370
0.371
0.377
G ZERO
+
MEAN
A
KNN
47
EM
-X
SVT
+B
GR
4
KFMC KC
0.6
0.6
0.5
0.6
0.5
ACC
NMI
PUR
0.4
0.4
0.4
0.3
0.3
0.3
Y Yale64
Yale64
Yale64
0.2
0.2
0,2
20%
40%
60%
80%
20%
40%
60%
80%
20%
40%
60%
80%
Missing Ratio
Missing Ratio
Missing Ratio r
0.6
0.8
0.7
0.59
0.6
0.6
ACC
NMI
0.5
0.4
0.4
0.3
0.3
Umist
mmist
Umist
0.2
0.2
0.2
20%
40%
60%
80%
20%
40%
60%
80%
20%
40%
60%
80%
Missing Ratio r
Missing Ratio
Missing Ratio r
Figure 2: Robustness analysis of standard spectral clustering using the Gaussian kernel on the Yale64 and Umist datasets under wide range of missing ratios, i.e., r E (20%, 80%].
F Comprehensive Experiments on Self-expressive Affinity Learning
Hyperparameters of Affinity Learning Algorithms. All kemel self-expressive affinity learning algorithms in this study adhere to a unified framework, i.e., mine } [X) & (xX) + XC(C). where À is regularization hyperparameter. Empirically, we choose X from the interval [0, 30) to roughly achieve better clustering performance, as detailed in Table 7 Note that the optimal À may vary across algorithm implementations under different settings.
20

---

Table 7: Values of the hyperparameter À in all experiments in Section 5.3
Method
Yale64
Umist
USPS
Isolet
KSSC
0,08
0.1
0.07
0.06
KL.S
KSL-Sp
0.6
10
10
AKLSR
0.5
0.4
0.3
0.5
Clustering Performance on the Exponential Kernel. We investigate the benefits of the corrected Exponential kernel for kernel self-expressive affinity learning, including KSSC [19] and KLSR
3]. Tables 8 shows that our KC algorithm outperforms baselines regarding the NMI metric on the
Exponential kernel based clustering, offering a systematic solution to clustering incomplete data.
Table 8: NMI Performance of self-expressive affinity on Exponential kernel with 80% missing.
Method Dataset (A)
Naive ZERO
MEAN
ANN
EM
SVT GR
KFMC
DC
TRF
EE
KC
Yale64 (0.08)
0.209 0.366
0.632
0.371 0.635 0.354 0.362
0.283
0.596 0.203 0.624 0.638
Umist (0.03)
0.115 0.614
0.665
0.583 0.662 0.613 0.669 0.326
0.657 0,110 0.676 0.684
KSSC
USPS (0.05)
0.020 0.039
0.368
0.250 0.227 0.039 0.356
0.348
0.022 0.017 0.479 0.472
Isolet (0.06)
0,064 0.069
0.123
0.085 0.094 0.069 0.120
0.132
0,071 0,060 0,634 0.661
Yale64 (20)
0.614 0.304
0.573
0.309 0.565 0.295 0.312
0.328
0.586 0.618 0.625 0.634
Umist (0.7)
0.127 0.570
0.655
0.557 0.653 0.566 0.682 0.487
0.642 0.130 0.688 0.693
KLSR
USPS (25)
0.083 0,309
0.433
0.354
0.217 0,310 0.341
0.381
0.440
0.217 0.513 0.515
Isolct (20)
0.453 0.413 0.571
0.468 0.417 0.417 0.543 0.510
0.530 0.517 0.659 0.676
Trade-off between Efficiency and Performance of the KC Algorithm. To enhance the efficiency of the KC algorithm, we explore the use of randomized singular value decomposition (rSVD) (33 method that focuses identifying the top-k singular values (refer to Section 3.3 We compare the performance the KC method with SD or rSVD on the USPS dataset. The results, presented in Table reveal that rSVD greatly enhances the operational efficiency of the KC algorithm. However, it is crucial to choose an appropriate value for & (number of top singular values), as it heavily impacts the quality of clustering. Smaller & values (e.g.. 10 20) result in poorer clustering due the loss of important singular value information. On the other hand, selecting a suitable k value (e.g.. 50 or 100) significantly reduces running time while maintaining clustering performance comparable to SD, particularly for the standard spectral clustering algorithm (SC). Striking a trade-off between efficiency and performance remains an intriguing avenue for future research.
Table 9: Comparisons of rSVD and SD in the KC algorithm the USPS with 80% missing.
Method
rSVD
SD
Metric
k 10
k:
20
k: 50
k: 100
RE-K
0.695
0.419
0.262
0.291
0.217
NMI-SC
0.026
0.164
0.431
0.439
0.472
NMI-KSSC
0.021
0.019
0.018
0.019
0.360
NMI-KLSR
0.021
0.122
0.210
0.018
0.485
Time (sec)
1.96
2.12
3.10
5.76
72.97
Comparisons of KSL-Sp and AKLSR. AKLSR outpaces KSL-Sp in execution speed. Algorithm 4 delineates each AKLSR update step explicitly, ensuring quicker convergence, whereas KSL-Sp in Algorithm relies on gradient descent for updates, leading to extended convergence times. Moreover, AKTSR's performance can vary with the presence or absence of PSD constraint. Table T0 showcases the efficiency AKLSR without PSD and its effectiveness with PSD on the Umist dataset.
Table 10: Comparisons of KSL-Sp and AKLSR Umist using the Gaussian kernel obtained by KCC
Metric
SC 0.377
KSL-Sp
AKL.SR w/o PSD
AKLSR w/ PSD
ARI
0.395
0.398
0.403
Time (sec)
12.57
0.04
0.23
21


Reviews:
[{"review_id": "PJDJz2pJa5", "reviewer": "Reviewer_7HKb", "summary": "The paper proposes a new kernel correction method to address the issue of incomplete data. Existing approaches aim to recover the distance matrix of complete data, starting from that of the incomplete data. In contrast, the proposed method (Section 3.2) formulates the problem as finding a positive semi-definite matrix that is closest to kernel matrix of incomplete data. The optimisation is solved using a iterative approach.\nThe paper further extends the approach to (kernel) affinity learning problems to propose 3 further algorithms, and finally, experimentally shows that the proposed methods outperform existing distance completion methods in the setting of kernel spectral clustering.", "questions": "- The fundamental goal of the paper seems to be kernel completion. What is special about spectral clustering (or its affinity learning) in this context? Why cannot one use the methods for supervised learning?\n- It is well known that spectral clustering does not require a positive semi-definite kernel (for instance, one can apply spectral clustering also on a graph adjacency). Then isn't it better to run any other matrix completion approach that does not impose psd?", "limitations": "The paper does not discuss any limitation, and the reported experimental results suggest that the proposed methods clearly outperform existing methods.\nHowever, as noted in weakness, the paper needs comparison with existing kernel completion works and needs discussion on what kind of missing data can drastically impact the proposed methods.\n\nPossible negative societal impact is neither evident nor discussed in the work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed approach is technically sound, and based on a rather intuitively simple idea of projecting onto the space of positive semi-definite matrices.\n- Extensions to affinity learning are proposed\n- The experiments show clear improvement over existing approaches for completing distance matrices", "weaknesses": "Literature:\nThe paper focus only on kernel spectral clustering and affinity learning, and hence, misses the broad and older literature on kernel methods for supervised learning. A quick search of Google scholar reveals a considerable literature on this topic. Few papers are noted but the literature is quite large, and it is not clear why the paper does not compare with such approaches.\n- Smola, Alex J., S. V. N. Vishwanathan, and Thomas Hofmann. \"Kernel methods for missing variables.\" International Workshop on Artificial Intelligence and Statistics. PMLR, 2005.\n- Dick, U., Haider, P., & Scheffer, T. (2008, July). Learning from incomplete data with infinite imputations. In Proceedings of the 25th international conference on Machine learning (pp. 232-239).\n- Liu, X., Zhu, X., Li, M., Wang, L., Zhu, E., Liu, T., ... & Gao, W. (2019). Multiple kernel $ k $ k-means with incomplete kernels. IEEE transactions on pattern analysis and machine intelligence, 42(5), 1191-1204.\nThe paper needs to positioned well in context of this literature, and the proposed algorithm should be compared with existing kernel completion methods.\n\nWeak theory, and insufficient experiments on different missing data:\nTheorem 1 is rather weak since it only guarantees that if the incomplete kernel matrix was derived from a some true psd matrix, then the returned projection is closer to ground truth that the incomplete kernel matrix. However, the algorithm/theorem does not guarantee that the output kernel matrix is significantly better than the given incomplete one. A general guarantee cannot be provided without assumptions. \nHowever, the work would significantly improve if there is a guarantee on recovery of ground truth kernel assuming that incomplete kernel matrix is obtained from data with features missing uniformly at random (setting considered in experiments)\n\nOn a similar note, the experiments only assume that features/values a missing at random. However, in practice, data is often systematically missing (some features tend to have higher missing values rate; there is often correlation between missing entries). Extensive experiments are needed to demonstrate that the proposed methods are robust to different types of missing entries, other than uniformly random.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 7HKb**\n\nThanks very much for your detailed feedback on the contributions of our work. We are delighted to hear that you found *the proposed approach is technically sound* and *the experiments show clear improvement over existing approaches*. Your comments are greatly appreciated and will help us to further improve our work, especially for the presentation of the paper.\n\nDue to technical constraints, we are unable to upload the updated version of our paper at this point. Therefore, we will further polish it in the new version.\n\n---\n\n**Comment 1**: Few papers are noted but the literature is quite large, and it is not clear why the paper does not compare with such approaches. \n\n**Response 1**: Thanks for your feedback. We do realize the literature in kernel learning with missing data under specific settings as in your recommended papers. Meanwhile, our work addresses **complete but inaccurate** (noisy) kernels due to the presence of incomplete observations, which is fundamentally different from most work in the literature primarily dealing with **incomplete** kernels.\n\n---\n\n**Comment 2**: A general guarantee cannot be provided without assumptions. However, the work would significantly improve if there is a guarantee on recovery of ground truth kernel assuming that incomplete kernel matrix is obtained from data with features missing uniformly at random.\n\n**Response 2**: To clarify, Theorem 1 resides on a mild assumption that the true kernel matrix is PSD, which is typically assumed in previous studies. It asserts that if the initial kernel $K^0$ (complete but inaccurate) is not a PSD matrix, we can correct it to a closer estimate $\\hat{K}$ to the unknown ground-truth $K^*$, providing a solid guarantee on the corrected kernel, i.e., $||K^*-\\hat{K}||_F \\le ||K^*-K^0||_F$. In fact, we can even provide a tighter performance bound for $\\hat{K}$ with $||K^*-\\hat{K}||_F \\le 2||K^*-K^0||_2$, where the proof will be included in the revision.\n\n---\n\n**Comment 3**: Extensive experiments are needed to demonstrate that the proposed methods are robust to different types of missing entries, other than uniformly random.\n\n**Response 3**: As you suggested, we have conducted additional experiments with different missing mechanisms, in addition to the setting of missing completely at random (MCAR) in our paper. For a given missing ratio, we generate a block of appropriate sizes located randomly in images and values in the block are missing where the missingness is systematically related to the location. Table 1 shows that our KC algorithm consistently outperforms existing data imputation and distance calibration methods under this block-missing mechansim. More results will be included in our further revision.\n\n**Table 1**: Performance of standard spectral clustering (SC) and self-expressive affinity learning (KSSC and KLSR) on the incomplete Yale64 dataset with the block-missing mechanism under a missing ratio of 80%.\n\n|Method|ZERO|MEAN|kNN|EM|SVT|FNNM|GR|KFMC|DC|EE|KC|\n|-----------------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-----------------|\n|SC-ACC|0.273|0.475|0.297|0.472|0.301|0.502|0.271|0.464|0.410|0.532|**0.535**|\n|SC-NMI|0.330|0.518|0.351|0.517|0.355|0.536|0.329|0.506|0.466|0.558|**0.562**|\n|SC-PUR|0.289|0.492|0.312|0.492|0.319|0.518|0.284|0.476|0.433|0.545|**0.547**|\n|KSSC-ACC|0.278|0.473|0.308|0.479|0.311|0.520|0.281|0.439|0.410|0.192|**0.533**|\n|KSSC-NMI|0.340|0.526|0.379|0.530|0.376|0.555|0.342|0.496|0.482|0.212|**0.562**|\n|KSSC-PUR|0.299|0.498|0.329|0.505|0.330|0.541|0.299|0.468|0.441|0.198|**0.542**|\n|KLSR-ACC|0.274|0.516|0.304|0.500|0.309|0.544|0.276|0.475|0.419|0.558|**0.568**|\n|KLSR-NMI|0.336|0.544|0.365|0.534|0.365|0.572|0.338|0.533|0.484|0.585|**0.592**|\n|KLSR-PUR|0.289|0.529|0.319|0.512|0.325|0.556|0.292|0.493|0.443|0.573|**0.579**|\n\n---\n\n**Comment 4**: 1) The fundamental goal of the paper seems to be kernel completion. 2) What is special about spectral clustering (or its affinity learning) in this context? 3) Why cannot one use the methods for supervised learning?\n\n**Response 4**: **1)** Our work diverges from traditional kernel completion and aims at refining a complete yet inaccurate kernel matrix to yield a more precise estimate. **2)** The performance of spectral clustering algorithms relies heavily on the quality of the affinity matrix, often defined by kernels or self-expressive affinity. Our proposed algorithms are tailored to improve the affinity quality, rendering them particularly suitable for spectral clustering. **3)** Thanks for your suggestion. We agree the approach can be potentially applied to supervised learning tasks, such as nearest neighbor classification and information retrieval tasks. More work will be carried out along this line. \n\n---\n\n**Comment 5**: 1) It is well known that spectral clustering does not require a positive semi-definite kernel. 2) Then isn't it better to run any other matrix completion approach that does not impose psd?\n\n**Response 5**: **1)** As you pointed out, spectral clustering does not necessitate the input to be a PSD kernel. Meanwhile in practice, spectral clustering often employs a Gaussian kernel, which is inherently PSD. Thus, our work adhered to the PSD constraints for the kernel, recognizing that other constraints may warrant further exploration. **2)** In our experimental evaluation, we conducted comparisons with four prevalent matrix completion methods for handling missing data, namely SVT, FNNM, GR, and KFMC. The results showed the superiority of our algorithm, affirming the validity of our approach within the context of spectral clustering.\n\n---\n\n**Comment 6**: The paper does not discuss any limitation.\n\n**Response 6**: Thanks for the suggestion. We will include a discussion of limitation in the revision."}, {"review_id": "5N5qHmaJYU", "reviewer": "Reviewer_7MjD", "summary": "The authors introduce an imputation-free framework for correcting a kernel obtained from incomplete data. They propose the corrected kernel to be a PSD matrix with bounded elements that is closest to the initial kernel (calculated from incomplete data) in Frobenius norm. They show that the corrected kernel is guaranteed to be closer to the ground truth than the initial kernel. In the case of the Gaussian kernel, Dykstra's projection algorithm is presented to obtain the corrected kernel. They then extend the existing self-expressive affinity learning framework by incorporating the proximal p-norm (0 < p < 1) and the Schatten p-norm (½ < p < 1) penalties on the affinity matrix. An algorithm (KSL-Pp) based on augmented Lagrangian and ADMM is proposed for the proximal p-norm penalty. Another algorithm (KSL-Sp) based on gradient descent is proposed for the Schatten p-norm penalty. Finally, the authors combine the kernel correction and the self-expressive affinity learning frameworks to jointly learn the corrected kernel and the affinity matrix. An algorithm (AKLSR) based on augmented Lagrangian and ADDM is proposed to solve the joint optimization problem.\n\nFor numerical experiments, they perform a comparative analysis on synthetic and image datasets and show their proposed method produces a more accurate Gaussian kernel than the existing techniques. The performance of spectral clustering improves when their proposed corrected kernel is used against the corrected kernels obtained by competing techniques. For self expressive affinity learning, they show that more accurate affinity can be estimated when their proposed corrected kernel is used against the corrected kernels obtained by other techniques.", "questions": "Major comments:\n* Line 42. “Incomplete data” - the authors never define what incomplete setting they are solving, I assume missing at random, but this should be clarified.\n* Line 128 “With a small missing ratio of features, $D_0$ already satisfies most triangle inequalities,..., then the algorithm typically yields only marginal improvement” - wouldn’t this be true of all methods? If the ratio of missing features is low, the impact on kernel construction is small and fixing it should yield marginal improvement. \n* line 140, an explanation of “the quality of $\\hat{D}$ cannot be guaranteed” would be helpful.\n* Line 221 “the corrected distance obtained from the corrected Gaussian kernel will also be more accurate than the calibrated distance from the Euclidean embedding method.” is there a proof for this or just empirical evidence in the simulation?  \n* Why do the elements of \\hat{C} on line 11 and 10 of algorithms 2 and 3 lie in [0,1]?\n* The constraints on K in Eq. (9), seem incorrect. Why are they not consistent with those in Eq.(5)? Why is there no constraint that K is PSD?\n* Line 201: O(n^2) storage limits the size of data that can be analyzed. Are the estimated kernels dense or sparse?\n* Is the inverse of the formula for k_{ij} on line 260 used to obtain d_{ij}?\n* The future work on line 287 “with future work on the potential of deep learning clustering techniques” should be made a bit more clear.\n\nSimulations: My main concern is with the experiments. \n1. The asymptotic time complexity provided by the authors is appreciated. It would be helpful if the actual time taken (in seconds) by the kernel correction and the affinity learning algorithms are also reported.\n2. Numerical experiments for KLRR and KSL-Pp in Table 3 are missing.\n3. Numerical experiments for KLRR, KSL-Sp and KSL-Pp in Table 3 and 4 in the supplementary material are missing.\n4. Numerical experiments for the proposed AKLSR algorithm that jointly corrects the kernel and learns the affinity matrix are missing.\n5. Gains are modest compared to EE - how do the two compare in terms of runtime/storage?\n6. A popular measure to evaluate clustering is the adjusted Rand index (ARI). The authors should add this since it is more informative than ACC. \n7. An additional non-image dataset would be useful to add if there is time (word-document, recommendation systems).\n8. std values are missing from all the tables. \n9. the experiments are performed only for 80% missing values. A wider range of missingness should be explored (plot can be used instead of tables) to demonstrate how robust the method is.\n10. How are the hyperparameters of competing methods determined?  \n\nMinor comments:\n* Although it seems intuitive, a reference for line 22 “incomplete data is commonly seen in practice, leading to inaccurate affinities and degraded clustering performance” would be helpful.\n* A minus is missing in the formula for K_{ij} on line 87.\n* The presentation in section 3 of “first method, “second method”,... seems odd. Are these the only relevant algorithms? Also, instead of using “first method” as a paragraph title, it would be better to use the name of the algorithm for the title of the paragraphs starting on lines 122, 130 and 142.\n* A more precise reference (theorem number etc.) of Property 2 on line 146 would be helpful.\n* Theorem 1 on line 193 may be placed after equation 5 as it holds in the general setting.\n* The transition to section 4 is rather abrupt and 1-2 introductory sentences can help better tie the paper together. \n* Which algorithm (SVD or rSVD) in Section 3.3 is used in the numerical experiments?\n* What value of p for KSL-Sp used in Section 5.3?", "limitations": "limitations aren't discussed", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Significance: The Gaussian kernel plays a central role in several tasks including clustering, dimensionality reduction, graph neural networks etc. A comparative analysis on image datasets is provided that showed improved quality of the corrected kernel using the proposed approach against those obtained by existing techniques. The same is also reflected in the improved performance of spectral clustering and the improved quality of self-expressive affinity matrices based on their proposed corrected kernel. On a high level, these improvements could be helpful in downstream applications.\n\nQuality: The authors adapted Dykstra's projection algorithm which comes with linear convergence guarantees, to correct the Gaussian kernel obtained from incomplete data.", "weaknesses": "Quality / clarity:\nThe authors extended the existing self-expressive affinity learning framework by incorporating p-norm based penalties (0 < p < 1). However, it is not clear how p-norm based penalties are more effective than the conventional 1-norm, Frobenius norm and nuclear norm based penalties. The provided empirical analysis seems insufficient to reach any conclusion.\n\nThe authors also proposed an algorithm that jointly optimizes the corrected kernel and the self-expressive affinity matrices using ADMM. However, there seems to be some issue in the formulation (see questions), and no empirical analysis is provided. This gives the sense that the paper is incomplete: the authors propose Adaptive Kernel Self-expressive Learning in 4.2 to tie between the kernel correction in section 3 and the self expressive affinity in 4.1, however do not include any simulations for this approach. Without demonstrating its efficacy, the inclusion of the proposed algorithm AKLSR seems unnecessary, and then the paper is essentially two unrelated approaches (kernel correction, self expressive learning) grouped together.   \n\nMissing references:\n* Gilbert, A. C., & Jain, L. (2017, October). If it ain't broke, don't fix it: Sparse metric repair. In 2017 55th Annual Allerton Conference on Communication, Control, and Computing\n* Shahid, N., Kalofolias, V., Bresson, X., Bronstein, M., & Vandergheynst, P. (2015). Robust principal component analysis on graphs. In Proceedings of the IEEE International Conference on Computer Vision \n* Biswas, Arijit, and David W. Jacobs. \"An Efficient Algorithm for Learning Distances that Obey the Triangle Inequality.\" BMVC. 2015.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 7MjD**\n\nThanks for your valuable comments on our work. We greatly appreciate the time and effort you have dedicated to thoroughly evaluating our paper and providing detailed feedback. We will modify it accordingly.\n\n---\n\n**Comment 1**: It is not clear how p-norm based penalties are more effective than the conventional 1-norm, Frobenius norm and nuclear norm based penalties.\n\n**Answer 1**: Theoretically, p-norm is a generalization of the L1 norm, offering a flexible sparsity control with a range of sparsity levels. Moreover, p-norm penalties exhibit robustness to outliers due to their smooth and continuous penalty term. Additional comparison results of different norms will be included in the revision to further validate these advantageous properties.\n\n---\n\n**Comment 2**: Missing references.\n\n**Answer 2**: We will cite these important references accordingly.\n\n---\n\n**Comment 3-1**: On the results of KSL-Pp and AKLSR algorithm.\n\n**Answer 3-1**: Sorry for any confusion caused by missing results. In practice, the KSL-Pp method requires handling numerous hyper-parameters and involves a non-convex optimization process during the Z-update step, making it difficult to effectively utilize. To address this limitation, we propose two extensions with the KSL-Sp and AKLSR algorithms. We haved conducted the experiments of AKLSR on two datasets as shown in Table 1, which partially validates the effectiveness of KC and AKLSR method. More results will be included in the revision.\n\n**Table 1(a)**: Performance of the AKLSR algorithm on Yale64 and Umist datasets under a missing ratio of 80%.\n\n|Dataset-Metric|ZERO|MEAN|kNN|EM|SVT|FNNM|GR|KFMC|DC|TRF|EE|KC|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|Yale64-NMI|0.332|0.610|0.334|0.602|0.312|0.614|0.341|0.307|0.564|0.385|0.577|**0.617**|\n|Yale64-PUR|0.300|0.591|0.312|0.581|0.281|0.602|0.307|0.290|0.546|0.348|0.555|**0.592**|\n|Yale64-ARI|0.071|0.377|0.079|0.373|0.057|0.382|0.074|0.051|0.321|0.116|0.329|**0.383**|\n|Umist-NMI|0.501|0.632|0.507|0.629|0.503|0.495|0.681|0.466|0.625|0.126|0.642|**0.687**|\n|Umist-PUR|0.428|0.519|0.419|0.521|0.425|0.418|0.567|0.424|0.525|0.145|0.540|**0.590**|\n|Umist-ARI|0.225|0.347|0.217|0.343|0.219|0.224|0.402|0.167|0.344|0.002|0.345|**0.398**|\n\n**Table 1(b)**: Comparison of AKLSR and SC algorithms on Yale64 and Umist datasets under a missing ratio of 80%.\n\n||Yale64-SC|Yale64-AKLSR|Umist-SC|Umist-AKLSR|\n|-|-|-|-|-|\n|NMI|0.596|**0.617**|0.673|**0.687**|\n|PUR|0.584|**0.592**|0.553|**0.590**|\n|ARI|0.366|**0.383**|0.377|**0.398**|\n\n---\n\n**Comment 3-2**: On comparison of EE and KC.\n\n**Answer 3-2**: While the KC method has comparable runtime and storage requirements, it offers the advantage of being applicable to a wide range of kernels. On the other hand, the EE method is limited to Laplacian kernels and relies on stricter assumptions, resulting in a narrower scope of applications.\n\n---\n\n**Comment 3-3**: On the ARI metric, std values, and more missingness.\n\n**Answer 3-3**: Thanks for your suggestion and we will add these results in the revision.\n\n---\n\n**Comment 3-4**: On experiments of a non-image dataset.\n\n**Answer 3-4**: We included an additional speech dataset, Isolet, in the Supplementary and also showed the superiority of our methods.\n\n---\n\n**Comment 4-1**: Line 221. Is there a proof for this or just empirical evidence in the simulation?\n\n**Answer 4-1**: The claim is supported by empirical evidence from our experiments and is an intuitive observation. We will modify the claim more rigorously and seek to find a theoretical proof in future work.\n\n---\n\n**Comment 4-2**: Why do the elements of \\hat{C} on line 11 and 10 of algorithms 2 and 3 lie in [0,1]?\n\n**Answer 4-2**: Taking Algorithm 2 as an example, the constraint of $c_{ij} \\in [0,1]$ in Eq. (6) has been incorporated through the term $\\sum_{i,j} \\max(z_{ij}-1,0)^2$ in the augmented Lagrangian function defined in Eq. (8). Consequently, when solving the augmented Lagrangian function using ADMM, the Z-update step largely guarantees the satisfaction of this constraint.\n\n---\n\n**Comment 4-3**: The constraints on K in Eq. (9), seem incorrect. Why are they not consistent with those in Eq.(5)? Why is there no constraint that K is PSD?\n\n**Answer 4-3**: We apologize for any confusion caused by the inconsistency in Eq. (9). To construct a suitable Lagrangian function, we simplified the formulation and utilized a procedure that starts with an initial estimate $K^0$ without explicitly enforcing the PSD constraint. However, we recognize the need for a more rigorous investigation and a solution that incorporates the PSD constraint appropriately. We appreciate your feedback and will make sure to clarify this in our work.\n\n---\n\n**Comment 4-4**: Line 201: O(n^2) storage limits the size of data that can be analyzed. Are the estimated kernels dense or sparse?\n\n**Answer 4-4**: Thanks for your suggestion. In practice, both the initial estimate $K^0$ and the corrected $\\hat{K}$ are dense.\n\n---\n\n**Comment 4-5**: Is the inverse of the formula for k_{ij} on line 260 used to obtain d_{ij}?\n\n**Answer 4-5**: Exactly. We obtain $d_{ij} = \\sqrt{-\\sigma^2 \\log(k_{ij})}$ due to $k_{ij} = \\exp(-d_{ij}^2/\\sigma^2)$, where $\\sigma = \\text{median}\\\\{d_{ij}\\\\}$.\n\n---\n\n**Comment 4-6**: Which algorithm (SVD or rSVD) in Section 3.3 is used in the numerical experiments?\n\n**Answer 4-6**: In our experiments, we used the spectral decomposition in the KC method. We will clarify it and include results of extensions with rSVD in the revision.\n\n---\n\n**Comment 4-7**: What value of p for KSL-Sp used in Section 5.3?\n\n**Answer 4-7**: In practice, there is no need to explicitly specify the value of $p$ in the KSL-Sp method. Theoretically, we utilized the finding in previous work that for $\\frac{1}{2} < p < 1$, $ ||C||_{S_p} = \\min \\frac{||U||_F^2 + ||V||_F^2}{2} $ with a constraint of $C = UV^{\\top}$ holds true. Based on this, we constructed a relaxed Lagrangian function in Line 235 that does not involve the parameter $p$."}, {"review_id": "N86L74WIBM", "reviewer": "Reviewer_GE1q", "summary": "This paper studies the spectral clustering problem when there is missing data. The paper proposes a new algorithm for correcting the computed kernel matrix by projecting the matrix to the nearest symmetric PSD matrix, and using this corrected kernel for clustering. The paper also combines the new kernel correction algorithm with affinity learning to develop a new technique for learning affinity matrices for incomplete data.\n\nExperimental evaluations show that the newly developed techniques outperform alternative methods for handing incomplete data with respect to standard clustering metrics.", "questions": "Every iteration of the KC algorithm requires computing the spectral decomposition. Given that only the top k eigenvectors are needed for spectral clustering, could it be possible to speed up the algorithm by, for example, computing only k eigenvectors at each iteration? \n\nWhat is the performance experimentally of performing spectral clustering on the naive k-NN graph constructed from the incomplete data? Given that this will be much faster than running KC, it would be interesting to see the trade-off between running time and accuracy.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The newly proposed algorithm for kernel correction is novel and interesting. It has potential applications and could inspire future research directions. The algorithm is conceptually quite simple and captures the theoretical intuition quite naturally. The experimental results suggest that the new algorithm outperforms alternative methods.", "weaknesses": "The running time of the kernel correction algorithm is quite slow - it requires computing the spectral decomposition of the kernel matrix at every iteration. It is good that the authors discuss this limitation in the paper, although it is a weakness of the algorithm. Improving the running time could be a future research direction.\n\nIt would be interesting to compare experimentally the benefit that kernel correction brings over simply doing nothing to correct the missing data (or doing something very naive to construct the k-NN graph for example).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer GE1q**\n\nThanks for your positive feedback on the novelty of our proposed method and its potential applications for future research directions. Your comments are greatly appreciated and will help us further improve our work, especially for convincing empirical evaluation.\n\n---\n\n**Question 1**: Given that only the top k eigenvectors are needed for spectral clustering, could it be possible to speed up the algorithm by, for example, computing only k eigenvectors at each iteration?\n\n**Answer 1**: We appreciate your insightful suggestion. To enhance the efficiency of the KC algorithm, we explored the use of randomized singular value decomposition (rSVD) [1] - a method that focuses on identifying the top-$k$ singular values (refer to Section 3.3). By replacing the spectral decomposition (SD) with rSVD, we were able to significantly reduce the time complexity of the algorithm from $O(n^3)$ to $O(n^2 \\cdot \\log(k) + 2n \\cdot k^2)$ while ensuring accurate decomposition.\n\nWe compared the performance of the KC method with SD or rSVD on two large datasets, USPS-1k and Mfeat-2K. The results, presented in Table 1(a) and 1(b) respectively, reveal that rSVD greatly enhances the operational efficiency of the KC algorithm. However, it is crucial to choose an appropriate value for $k$ (number of top singular values), as it heavily impacts the quality of clustering. Smaller $k$ values (e.g., 10 or 20) result in poorer clustering due to the loss of important singular value information. On the other hand, selecting a suitable $k$ value (e.g., 50 or 100) significantly reduces runtime while maintaining clustering performance comparable to SD, particularly for the standard spectral clustering algorithm (SC). Striking a trade-off between efficiency and performance remains an intriguing avenue for future research.\n\n**Table 1(a)**: Comparison of rSVD and SD on kernel correction and spectral clustering for the incomplete *USPS-1K* dataset under a missing ratio of 80%. Note that *RE_K* denotes the relative error of the corrected Gaussian kernel, *SC* denotes the standard spectral clustering algorithm, and *KLSR* denotes the kernel least-squares representation algorithm.\n\n|Method|rSVD (k=10)|rSVD (k=20)|rSVD (k=50)|rSVD (k=100)|SD|\n|-|-|-|-|-|-|\n|RE_K|0.695|0.419|0.262|0.291|**0.217**|\n|SC-ACC|0.153|0.290|0.494|0.509|**0.523**|\n|SC-NMI|0.026|0.164|0.431|0.439|**0.472**|\n|SC-PUR|0.189|0.332|0.572|0.582|**0.609**|\n|KLSR-ACC|0.147|0.266|0.317|0.148|**0.528**|\n|KLSR-NMI|0.021|0.122|0.210|0.018|**0.485**|\n|KLSR-PUR|0.173|0.296|0.389|0.176|**0.627**|\n|*Time (sec)*|**1.96**|2.12|3.10|5.76|72.97|\n\n\n**Table 1(b)**: Comparison of rSVD and SD on kernel correction and spectral clustering for the incomplete *Mfeat-2K* dataset under a missing ratio of 80%.\n\n|Method|rSVD (k=10)|rSVD (k=20)|rSVD (k=50)|rSVD (k=100)|SD|\n|-|-|-|-|-|-|\n|RE_K|0.681|0.474|0.223|0.201|**0.168**|\n|SC-ACC|0.142|0.201|0.715|0.721|**0.761**|\n|SC-NMI|0.017|0.071|0.667|0.733|**0.758**|\n|SC-PUR|0.148|0.213|0.748|0.777|**0.804**|\n|KLSR-ACC|0.136|0.178|0.629|0.606|**0.705**|\n|KLSR-NMI|0.012|0.045|0.563|0.613|**0.712**|\n|KLSR-PUR|0.140|0.184|0.675|0.686|**0.755**|\n|*Time (sec)*|**6.82**|7.28|9.08|13.98|390.84|\n\n[1] Halko N., et al. \"Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.\" SIAM Review, 2011.\n\n---\n\n**Question 2**: What is the performance experimentally of performing spectral clustering on the naive k-NN graph constructed from the incomplete data?\n\n**Answer 2**: As you suggested, we have compared the naive kNN graph and our KC method on four benchmark datasets. The results, presented in Table 2, show that the KC method surpasses the naive kNN graph across multiple aspects. \n- The KC method demonstrates improved accuracy in distance estimation and kernel estimation, as evidenced by smaller relative errors, i.e., RE_D and RE_K.\n- KC exhibits a better local relationship in the kNN graph, as indicated by a higher Recall value. \n- When applying SC, KSSC, and KLSR clustering algorithms, the KC method consistently outperforms the naive kNN graph in terms of ACC, NMI, and PUR metrics. \n\nNotably, while the naive kNN graph boasts a significantly faster runtime, its clustering performance is unstable and can be notably compromised when utilizing the KSSC or KLSR algorithms due to substantial errors in kernel estimation.\n\n**Table 2**: Comparison of the naive kNN graph and KC method on spectral clustering with standard Gaussian kernels (SC) and self-expressive affinity learning (KSSC, KLSR) for incomplete datasets under a missing ratio of 80%.\n\n| Dataset-Method | Yale64-Naive | Yale64-KC | Umist-Naive | Umist-KC | USPS-Naive | USPS-KC | Mfeat-Naive | Mfeat-KC |\n|-|-|-|-|-|-|-|-|-|\n| RE_D | 0.064 | **0.053** | 0.107 | **0.070** | 0.268 | **0.132** | 0.173 | **0.095** |\n| RE_K | 0.113 | **0.089** | 0.189 | **0.117** | 0.460 | **0.217** | 0.312 | **0.168** |\n| Recall | 0.721 | **0.767** | 0.726 | **0.785** | 0.071 | **0.197** | 0.246 | **0.286** |\n| SC-ACC | 0.561 | **0.578** | 0.462 | **0.463** | 0.343 | **0.523** | 0.728 | **0.761** |\n| SC-NMI | 0.588 | **0.596** | 0.669 | **0.673** | 0.222 | **0.472** | 0.740 | **0.758** |\n| SC-PUR | 0.572 | **0.584** | 0.549 | **0.553** | 0.395 | **0.609** | 0.782 | **0.804** |\n| KSSC-ACC | 0.190 | **0.586** | 0.119 | **0.496** | 0.152 | **0.427** | 0.121 | **0.713** |\n| KSSC-NMI | 0.219 | **0.616** | 0.101 | **0.714** | 0.018 | **0.360** | 0.010 | **0.648** |\n| KSSC-PUR | 0.198 | **0.601** | 0.131 | **0.584** | 0.171 | **0.529** | 0.124 | **0.750** |\n| KLSR-ACC| 0.582 | **0.607** | 0.485 | **0.488** | 0.144 | **0.528** | 0.205 | **0.705** |\n| KLSR-NMI| 0.606 | **0.616** | 0.676 | **0.696** | 0.019 | **0.485** | 0.078 | **0.712** |\n| KLSR-PUR| 0.592 | **0.613** | 0.568 | **0.572** | 0.176 | **0.627** | 0.217 | **0.755** |\n| *Time (sec)*| 0.18 | **0.03** | **0.54** | 8.05 | **0.60** | 72.97 | **3.76** | 390.84 |"}, {"review_id": "XDcv6TB9cB", "reviewer": "Reviewer_hJi1", "summary": "This paper proposes an imputation-free framework with two novel approaches to improve spectral clustering on incomplete data. Firstly, the authors introduce a new kernel correction method that enhances the quality of the kernel matrix estimated on incomplete data with a theoretical guarantee, benefiting classical spectral clustering on pre-defined kernels. Secondly, they develop a new affinity learning method that equips the self-expressive framework with ℓp-norm to construct an intrinsic affinity matrix with adaptive extensions. \n\n\n", "questions": "1. The authors propose an imputation-free framework with two novel approaches to improve spectral clustering on incomplete data. However, the advantages of the proposed method in dealing with incomplete data are not clearly stated based on Section 3, i.e., considering how to recover the missing data. Thus, the authors are expected to analyze the merits of the proposed method in dealing with the incomplete data.\n\n2. In section 3.1, the authors give different methods to provide a calibrated distance matrix with benefits for distance-based kernels and are not a universal solution for dealing with incomplete data in spectral clustering tasks. However, these separated methods may make the novelty of this paper separated and not focused. I think the authors can better stating the revisiting distance calibration methods in this part.\n\n3. The adopted datasets in the paper are almost with small scales in the experiments. The authors can add one or more multi-view datasets with large scales for validating the clustering performance.\n\n4. The improvements of the proposed method compared with other methods are not significant in the experiments, i.e., the RE_K of KC is just 0.217 on USPS.\n\n5. The authors can add one or more recent methods for comparison in the experiment, which make the comparson of experimental results more comprehensively.", "limitations": "1. The authors propose an imputation-free framework with two novel approaches to improve spectral clustering on incomplete data. However, the advantages of the proposed method in dealing with incomplete data are not clearly stated based on Section 3, i.e., considering how to recover the missing data. Thus, the authors are expected to analyze the merits of the proposed method in dealing with the incomplete data.\n\n2. In section 3.1, the authors give different methods to provide a calibrated distance matrix with benefits for distance-based kernels and are not a universal solution for dealing with incomplete data in spectral clustering tasks. However, these separated methods may make the novelty of this paper separated and not focused. I think the authors can better stating the revisiting distance calibration methods in this part.\n\n3. The adopted datasets in the paper are almost with small scales in the experiments. The authors can add one or more multi-view datasets with large scales for validating the clustering performance.\n\n4. The improvements of the proposed method compared with other methods are not significant in the experiments, i.e., the RE_K of KC is just 0.217 on USPS.\n\n5. The authors can add one or more recent methods for comparison in the experiment, which make the comparson of experimental results more comprehensively.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The originality of this paper is satisfying, which proposes an imputation-free framework with two novel approaches to improve spectral clustering on incomplete data and the significance is OK.\n\nThe quality and clarity of this paper are satisfying based on the clear presentation of the imputation-free framework with two novel approaches.", "weaknesses": "1. The authors propose an imputation-free framework with two novel approaches to improve spectral clustering on incomplete data. However, the advantages of the proposed method in dealing with incomplete data are not clearly stated based on Section 3, i.e., considering how to recover the missing data. Thus, the authors are expected to analyze the merits of the proposed method in dealing with the incomplete data.\n\n2. In section 3.1, the authors give different methods to provide a calibrated distance matrix with benefits for distance-based kernels and are not a universal solution for dealing with incomplete data in spectral clustering tasks. However, these separated methods may make the novelty of this paper separated and not focused. I think the authors can better stating the revisiting distance calibration methods in this part.\n\n3. The adopted datasets in the paper are almost with small scales in the experiments. The authors can add one or more multi-view datasets with large scales for validating the clustering performance.\n\n4. The improvements of the proposed method compared with other methods are not significant in the experiments, i.e., the RE_K of KC is just 0.217 on USPS.\n\n5. The authors can add one or more recent methods for comparison in the experiment, which make the comparson of experimental results more comprehensively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer hJi1**\n\nThank you very much for your positive feedback on the originality of our proposed method and its significance. We are delighted to hear that you found *our work satisfying in terms of quality and clarity*. Your comments are greatly appreciated and will help us further improve our work, especially for the presentation and evaluation.\n\n---\n\n**Comment 1**: The advantages of the proposed method in dealing with incomplete data are not clearly stated based on Section 3, i.e., considering how to recover the missing data. Thus, the authors are expected to analyze the merits of the proposed method in dealing with the incomplete data.\n\n**Response 1**: Thanks for the suggestion. We do agree that including a discussion on the merits and challenges between imputation methods and imputation-free methods would be beneficial to the readers. We will try to add such a discussion.\n\n---\n\n**Comment 2**: I think the authors can better stating the revisiting distance calibration methods in this part.\n\n**Response 2**: We appreciate your valuable feedback. It will be revised accordingly.\n\n---\n\n**Comment 3**: The authors can add one or more multi-view datasets with large scales for validating the clustering performance.\n\n**Response 3**: Thanks for your suggestion. We will evaluate the work on larger datasets, including multi-view datasets. (Due to limited time, we were unable to finish such an evaluation in the rebuttal stage.) If any suitable multi-view datasets can be recommended, we will appreciate it.\n\n---\n\n**Comment 4**: The improvements of the proposed method compared with other methods are not significant in the experiments, i.e., the RE_K of KC is just 0.217 on USPS.\n\n**Response 4**: We agree that the improvements under some settings are not that significant, while the improvements are consistent under all settings. \n\n---\n\n**Comment 5**: The authors can add one or more recent methods for comparison in the experiment, which make the comparson of experimental results more comprehensively.\n\n**Response 5**: As you suggested, we included an additional comparison method, Polynomial Matrix Completion (PMC) [1], in our experiments. The results presented in Table 1 demonstrate that our KC method consistently outperforms the PMC method. Specifically, the KC method achieves better distance and kernel estimation with smaller relative errors (RE_D and RE_K), resulting in improved clustering performance with higher ACC, NMI, and PUR scores. These findings further validate the effectiveness of our KC method in comparison to recent imputation techniques.\n\n**Table 1**: Comparison of PMC and KC on distance estimation, kernel estimation and standard spectral clustering (SC) with Gaussian kernels for incomplete datasets under a missing ratio of 80%.\n\n| Dataset-Method | Yale64-PMC | Yale64-KC | Umist-PMC | Umist-KC | USPS-PMC | USPS-KC | Mfeat-PMC | Mfeat-KC |\n|-|-|-|-|-|-|-|-|-|\n|RE_D $\\downarrow$|0.147|**0.053**|0.325|**0.070**|0.314|**0.132**|0.368|**0.095**|\n|RE_K $\\downarrow$|0.152|**0.089**|0.457|**0.117**|0.304|**0.217**|0.360|**0.168**|\n|SC-ACC $\\uparrow$|0.548|**0.578**|0.397|**0.463**|0.476|**0.523**|0.508|**0.761**|\n|SC-NMI $\\uparrow$|0.574|**0.596**|0.508|**0.673**|0.466|**0.472**|0.469|**0.758**|\n|SC-PUR $\\uparrow$|0.555|**0.584**|0.473|**0.553**|0.556|**0.609**|0.526|**0.804**|\n\n[1] Fan, J., et al. \"Polynomial matrix completion for missing data imputation and transductive learning.\" AAAI, 2020."}]

Author rebuttal:

Meta-review: An interesting paper; which has seen an increase of the ratings of several reviewers (7HKb, 7MjD, GE1q) in the course of the discussion phase. Though the additional rebuttal and comments have increased the quality of the paper — assuming they make their way to the revision —, the authors could have done a better job of digging into some important comments; instead of mostly staying on the experimental side and maybe picking technical comments that did not require extensive digging. For example, I would have appreciated a thorough answer to comment 1 of hJi1.

The final impression is very much mitigated: the paper has undoubtedly scored some positive feedback at discussion the but it still stands pretty much on a borderline(+) global score.
Decision: Accept (poster)