Fast and Scalable Incomplete Multi-View Clustering with Duality Optimal Graph Filtering

Authors: liang  du
yukai  shi
yan  chen
peng  zhou
yuhua  qian
Venue: acmmm_org_ACMMM_2024_Conference
Published: 2024-04-07 16:07:07

Abstract: Incomplete Multi-View Clustering (IMVC) is crucial for multi-media data analysis. While graph learning-based IMVC methods have shown promise, they still have limitations. The prevalent first-order affinity graph often misclassifies out-neighborhood intra-cluster and in-neighbor inter-cluster samples, worsened by data incompleteness. These inaccuracies, combined with high computational demands, restrict their suitability for large-scale IMVC tasks. To address these issues, we propose a novel Fast and Scalable IMVC with duality Optimal graph Filtering (FSIMVC-OF).  Specifically, we refine the clustering-friendly structure of the bipartite graph by learning an optimal filter within a consensus clustering framework. Instead of learning a sample-side filter, we optimize an anchor-side graph filter and apply it to the anchor side, ensuring computational efficiency with linear complexity, supported by the provable equivalence between these two types of graph filters. We present an alternative optimization algorithm with linear complexity. Extensive experimental analysis demonstrates the superior performance of FSIMVC-OF over current IMVC methods. The codes of this article are released in https://github.com/sroytik/FSIMVC-OF.

Main paper: 
 introduction: 
 Multi-view clustering (MVC) plays a crucial role in unsupervised learning, seamlessly integrating diverse data types like images, audio, and text found in multimedia content [3, 7, 47] . Despite its importance, real-world applications often grapple with incomplete data, compromising the effectiveness of MVC methods that rely on complete datasets. This has spurred increasing attention on IMVC settings [34, 39] , tackling the widespread challenge of missing data in open environments. IMVC methods encompass matrix learningbased [13, 14, 17, 20, 21, 23, 24, 53] , graph learning-based [16, 18, 22, 36, 37] , and deep learning-based techniques [19, 44, 45] .Among them, graph based methods have demonstrated notable potential in tackling data incompleteness in IMVC by harnessing inter-point relationships to bolster clustering efficacy. They construct affinity graphs that reflect the pairwise similarities among data samples, guiding the clustering process. These graphs leverage connectivity and structural insights to infer and fill in missing data effectively. Moreover, these methods enhance the affinity graph by integrating ancillary data or constraints, which improves clustering outcomes. Techniques such as incorporating global insights or domain-specific knowledge result in more robust graphs that are less affected by incomplete data.While graph learning-based methods have made strides in various applications, they still encounter significant hurdles in largescale IMVC. Firstly, the accuracy of the first-order affinity graph is inherently limited. The first-order sample-sample or sample-anchor [16, 22, 36] affinity graph is a cornerstone of many graph-based clustering methods, but its accuracy is inherently constrained. This limitation often caused in the misclassification of out-of-neighborhood intra-cluster samples as negatives and in-neighborhood inter-cluster samples as positives [25] . The degradation of the graph is further exacerbated by data incompleteness. Meanwhile, accurately imputing missing data for such inaccurate graphs without bringing additional noise and errors also poses significant difficulty [18] . Secondly, the computational cost becomes prohibitive, especially when performing operations like eigen-decomposition or matrix inversion on large datasets. On the one hand, there is an expectation to carefully explore the underlying clustering-friendly structure from incomplete information to improve the quality of affinity graphs, even though this inevitably increases computational complexity. On the other hand, there is a necessity to keep computational costs at a moderate or consistent level. In light of these challenges, there is a imperative demand for the development of innovative approaches capable of simultaneously addressing these conflicting objectives, particularly within the context of large-scale IMVC scenarios.In response to these challenges, we present the Fast and Scalable Incomplete Multi-View Clustering method with duality Optimal graph Filtering (FSIMVC-OF). We begin by constructing viewindependent bipartite graphs to capture the first order affinity between samples and anchors. Next, we introduce a novel samplesample graph filter derived from these bipartite graphs, capable of capturing higher-order interactions between sample-anchorsamples. Crucially, our method dynamically learns the optimal coefficients of different orders during the clustering procedure. We then apply this sample-sample graph filter to the original bipartite graph, enhancing clustering structure clarity through its low-pass properties. To reduce the computational burden of sample-side graph filtering, we rigorously establish the equivalence between samplesample and anchor-side filtering, simplifying optimization with the linear complexity. Additionally, we propose a unified framework to learn a consensus clustering representation from these filtered signals. We offer a convergence-guaranteed optimization algorithm for practical applicability. With a computational complexity of 𝑂 (𝑛), our method is ideal for large-scale datasets. Extensive experiments across various benchmarks demonstrate the superiority of FSIMVC-OF over state-of-the-art IMVC methods.• We propose a novel method to improve the quality of first order bipartite graph by the duality optimal graph filtering. It leverages optimal graph filter learning on the sample-side to encapsulate higher-order interactions, guiding the enhancement of clustering-friendly structures for the first-order bipartite graphs. Meanwhile, it maintains adaptive filter learning on the anchor-side, ensuring computational efficiency with linear complexity, based on the provable equivalence between these two types of graph filters.  
related work: 
 To tackle the IMVC problem, several approaches have been developed [34, 39] . These approaches can be categorized into three groups based on differences of learning frameworks: matrix learningbased IMVC [13, 14, 17, 20, 21, 23, 24, 53] , graph learning-based IMVC [16, 18, 22, 36, 37] , and deep learning-based IMVC [19, 44, 45] . Matrix learning-based IMVC methods interpolate missing terms in partial matrices and fall into three sub-categories: (1) kernel learning-based methods [17, 23, 24] , which handle incomplete kernels using imputation and kernel-based techniques; (2) subspace learning based methods [20, 53] , which project multi-view data onto low-dimensional spaces; and (3) non-negative matrix factorization based methods [13, 14, 21] , aiming to minimize reconstruction error between existing data and factorized matrices.Graph learning-based IMVC represent data using graph structures to mine relationships between views and learn low-dimensional representations from diverse graphs, elucidating relationships among multiple views [38] . Based on the approach used to integrate graph information, graph learning-based IMVC can be categorized into two categories: (1) spectral learning-based methods [37, 40] . These techniques fuse nearest neighbor graph structure and graph regularization into incomplete graph learning, enhancing information exploration. For example, Wen et al. [37] proposed confidence graph learning, inferring missing edges from shared similar-nearest neighbors. (2) adaptive graph learning-based methods [12, 16, 18, 22, 36, 49] . These methods enhance clustering by optimizing graph structures and integrating multi-view information, addressing missing data and learning low-dimensional representations [43] . Through weighting and anchor points strategy, these methods considers the contribution of each view to clustering and reduces the size of data and complexity. For example, Wang et al. [36] constructed individual incomplete bipartite graphs for each view, and treating incomplete samples as unconnected to anchors within the graph. However, despite the advancements in graph-based methods, significant challenges persist in large-scale IMVC. Firstly, the inherent limitation of the first-order affinity graph accuracy leads to misclassification of intra-cluster and inter-cluster samples. Moreover, data incompleteness exacerbates the degradation of the graph, making accurate imputation challenging. Secondly, the computational cost becomes prohibitive, particularly during operations like eigendecomposition or matrix inversion on large datasets.Deep learning-based IMVC utilizes a deep learning model to learn feature representations and is better able to handle missing data. For example, Xu et al. [44] acquired view-specific features through individual auto-encoders and employed a feature projection technique to explore the consensus information among multiple views. 
the proposed method 3.1 notations: 
 Given the incomplete data matrices{X 𝑟 } 𝑣 𝑟 =1 ∈ R 𝑛×𝑑 𝑟, where 𝑣 and 𝑛 is the number of all views and all samples, and 𝑑 𝑟 is the number of feature dimension of the 𝑟 -th view. Since the incomplete multi-view data [46] under discussion is the missing of random samples in each view of multiple views, and each sample is guaranteed to be observable in at least one view, we can divide the data matrix for each view into observed and missing parts, i.e., X 𝑟 = {X 𝑟 𝑜 , X 𝑟 𝑚 }, where X 𝑟 𝑜 ∈ R 𝑛 𝑟 ×𝑑 𝑟 and X 𝑟 𝑚 ∈ R (𝑛-𝑛 𝑟 ) ×𝑑 𝑟 , and 𝑛 𝑟 denote the number of observed samples of the 𝑟 -th view.To leverage the benefits of bipartite graph-based methods for large scale IMVC, we incorporate bipartite graphs to capture the firstorder sample-anchor affinities within the FSIMVC-OF model. This generally involves two subsequent steps: anchor selection and graph construction.Considering that constructing multiple anchor graphs through diversification mechanisms can enhance the performance of subsequent clustering [48] , we adopt a view-independent anchor selection strategy in this paper. Specifically, we employ the cluster centers obtained from k-means applied to complete samples X 𝑟 𝑜 in each incomplete view to form the anchor matrix A 𝑟 ∈ R 𝑚 𝑟 ×𝑑 𝑟 , where 𝑚 𝑟 represents the number of anchors in the 𝑟 -th view. This strategy aims to handle the incompleteness in data across different views while enabling independent anchor selection for each view.With the obtained anchor matrix A 𝑟 , the bipartite graph B 𝑟 ∈ R 𝑛 𝑟 ×𝑚 𝑟 between observed samples and anchors can be learned by solving the following optimization problem,EQUATIONwhere 𝒃 𝑟 𝑖 represents the 𝑖-th row of B 𝑟 , and ℎ x 𝑟 𝑖 , a 𝑟 𝑗 signifies the Euclidean distance between the 𝑖-th sample and the 𝑗-th anchor,𝛾 = 𝑘 2 ℎ(x 𝑟 𝑖 , a 𝑟 (𝑘+1) ) -1 2 𝑘 𝑗=1 ℎ(x 𝑟 𝑖 , a 𝑟 𝑗 )is the trade off parameter. To ensure sparsity in the bipartite graph B 𝑟 and avoid the search of 𝛾, we limit each row to retain only 𝑘 non-zero elements, which is set to 𝑘 = 5 in this paper. The closed-form solution is given by [29] :EQUATIONIt is widely acknowledged that such affinity graphs may still incorrectly assign a zero affinity (𝑏 𝑟 𝑖 𝑗 = 0) to out-of-neighborhood samples within the same cluster, while neighboring inter-cluster samples may be mistakenly treated as positive [26] .To address the inaccuracies of first-order affinities between samples and anchors, we utilize sample-anchor-sample similarities to capture higher-order interactions among sample-sample. Specifically, given the acquired sample-anchor bipartite graphB 𝑟 ∈ R 𝑛 𝑟 ×𝑚 𝑟 , we first introduce a diagonal matrix △ 𝑟 ∈ R 𝑚 𝑟 ×𝑚 𝑟, where its 𝑗-th diagonal element △ 𝑟 𝑗 𝑗 = 𝑛 𝑟 𝑖=1 𝑏 𝑟 𝑖 𝑗 . Next, we obtain a column-normalized affinity graph P 𝑟 = B 𝑟 (△ 𝑟 ) -1 2 , and then the affinity graph between sample-anchor-sample can be derived asS 𝑟 = B 𝑟 △ -1 B 𝑟𝑇 = P 𝑟 P 𝑟𝑇 , where S 𝑟 ∈ R 𝑛 𝑟 ×𝑛 𝑟. It can be verified that S 𝑟 is a doubly stochastic matrix, i.e., P 𝑟 P 𝑟𝑇 1 𝑛 𝑟 = 1 𝑛 𝑟 , 1 𝑇 𝑛 𝑟 P 𝑟 P 𝑟𝑇 = 1 𝑇 𝑛 𝑟 . Smoother graph signals, as indicated by [4, 9, 27, 42, 52] , correlate with a clearer clustering structure. To achieve a smoother graph [32] , we solve the optimization problem:EQUATIONwhere L 𝑟 𝑛 = I 𝑛 𝑟 -P 𝑟 P 𝑟𝑇 ∈ R 𝑛 𝑟 ×𝑛 𝑟 is the normalized Laplacian matrix, and the solution is given by:EQUATIONCompared to P 𝑟 , the induced graph P𝑟 obtained with Eq. ( 4) become more smooth by incorporating sample-sample similarities [5, 6, 50, 51] . However, the operator in Eq.( 4) requires an inverse operation. This approach is suboptimal for the downstream IMVC task and does not leverage complementary information from other views.To avoid the inverse operation, the above solution can be approximated through its first-order Taylor expansion, and we have,EQUATIONRecent studies in [30] emphasize the importance of low-frequency bases in smooth signals. To incorporate this insight, we build the following filtered signalEQUATIONTo circumvent the need for selecting different values of 𝑡, we design a learnable graph filter. This filter dynamically updates during the clustering process:EQUATION)where 𝑡 represents a positive integer that defines the extent of the 𝑡-hop neighborhood relationship within the signal. From Eq. ( 7), it can be seen that the first order bipartite graph P 𝑟 is smoothed by a high-order graph filter H (P 𝑟 , 𝜷 𝒓 ) ∈ R 𝑛 𝑟 ×𝑛 𝑟 with the unknown coefficient 𝜷 𝒓 . Compared to Eq. ( 4), it can be conclude that Eq. ( 7) leverage optimal graph filter learning on the sample side to encapsulate higher-order interactions, guiding the enhancement of clustering-friendly structures for the first-order bipartite graph. However, the computation of Eq. ( 7) is still intensive.It can be further proven by Theorem 3 that the filtering on P 𝑟 by sample-side graph filter can be equivalently represented by the filtering on P 𝑟𝑇 by the anchor-side graph filter. With such equivalence, we propose the following filtering to incorporate the clustering friendly high order sample-sample interactions via the high order anchor-anchor interactions,EQUATIONCompared with the sample-side filtering in Eq. ( 7), the anchor-side filtering in Eq. ( 8) maintains adaptive filter learning on the anchor side, ensuring computational efficiency with linear complexity on the sample size, based on the provable equivalence between these two types of graph filters.Given multiple incomplete first-order bipartite graphs {P 𝑟 } 𝑣 𝑟 =1 with P 𝑟 ∈ R 𝑛 𝑟 ×𝑚 𝑟 , we take the aforementioned anchor-side optimal graph filter to incorporate the higher order interactions among samples. In this subsection, we aim to learn a complete and consensus clustering oriented representation Z ∈ R 𝑛×𝑐 from multiple incomplete bipartite graphs, each enhanced by view-independent graph filters, denoted as {P 𝑟 H (P 𝑟𝑇 , 𝜷 𝒓 )} 𝑣 𝑟 =1 . Based on the indices of observed and missing samples in each view of the incomplete data matrices {X 𝑟 } 𝑣 𝑟 =1 , we can partition the consensus sample matrix Z into two corresponding parts for each view, represented as Z = {Z 𝑜 𝑟 , Z 𝑚 𝑟 }. We propose to project anchor points from different views into a common cluster latent space using projection matrices {W 𝑟 } 𝑣 𝑟 =1 ∈ R 𝑚 𝑟 ×𝑐 , where 𝑐 is the cluster number. These points are linked with 𝑐 prototypes in the latent space using the prototype representation matrix C ∈ R 𝑐 ×𝑐 . The consensus clustering procedure with the enhanced bipartite graphs of FSIMVC-OF can be formulated as follows:min 𝑣 ∑︁ 𝑟 =1 (𝛼 𝑟 ) 2 P 𝑟 t ∑︁ 𝑡 =0 𝛽 𝑟 𝑡 I 𝑚 𝑟 + P 𝑟𝑇 P 𝑟 2 𝑡 -Z 𝑜 𝑟 CW 𝑟𝑇 2 𝐹 (9) s.t. Z ≥ 0, 1 𝑇 𝑛 Z = 1 𝑇 𝑐 , W 𝑟𝑇 W 𝑟 = I 𝑐 , C 𝑇 C = I 𝑐 , 𝜶 𝑇 1 = 1, 0 ≤ 𝛼 𝑟 ≤ 1, 𝜷 𝑟𝑇 1 = 1, 0 ≤ 𝛽 𝑟 𝑡 ≤ 1, where 𝛼 𝑟 is the view weight for the 𝑟 -th view, Z 𝑜 𝑟 represents the similarity between 𝑐 prototypes and 𝑛 𝑟 observed samples from the 𝑟 -th view. To enhance the distinctiveness of the learned prototypes C, we apply orthogonal constraints to C. The prototype graph Z, thus learned, must fulfill Z ≥ 0 and 1 𝑇 𝑛 Z = 1 𝑇 𝑐 conditions.The problem in Eq.( 9) involves five variables: W 𝑟 , C, Z, 𝜷 𝑟 and 𝜶 . We provide an alternative algorithm for optimization.3.5.1 Update W 𝑟 . When other variables are fixed, the problem for W 𝑟 becomes: minEQUATIONwhereEQUATION, which can be further simplified as maxEQUATIONwhere E 𝑟 = F 𝑟𝑇 P 𝑟𝑇 Z 𝑜 𝑟 C, andF 𝑟 = t 𝑡 =0 𝛽 𝑟 𝑡 Q 𝑟 𝑡 .The optimal W 𝑟 can be obtained by Singular Value Decomposition (SVD) on E 𝑟 [34] .3.5.2 Update C. Similar to Eq. ( 11), we seek to optimize C via:EQUATIONwhere R = 𝑣 𝑟 =1 (𝛼 𝑟 ) 2 Z 𝑇 𝑜 𝑟 P 𝑟 F 𝑟 W 𝑟 . Similar to the update of W 𝑟 , the optimization of C can also be performed by the SVD on R.EQUATION)where H 𝑜 𝑟 ∈ R 𝑛 𝑟 ×𝑐 , and H ∈ R 𝑛×𝑐 can be obtained by aggregating all {H 𝑜 𝑟 } 𝑣 𝑟 =1 at the corresponding sample index. Consequently, the optimization problem related to Z can be decomposed row-wise. For the 𝑖-th sample, it is formulated as:EQUATION)The above problem in Eq. ( 14) can be efficiently solved using the Euclidean projection onto the simplex [28] .3.5.4 Update 𝜷 𝑟 . The rest problem w.r.t. 𝜷 𝑟 ∈ R t ×1 can be written as:minEQUATION)where M 𝑟 ∈ R t ×t with M 𝑟 𝑖 𝑗 = tr(Q 𝑟 𝑖 P 𝑟𝑇 P 𝑟 Q 𝑟 𝑗 ), and s 𝑟 ∈ R t ×1 with 𝑠 𝑟 𝑡 = tr(Q 𝑟 𝑡 P 𝑟𝑇 Z 𝑜 𝑟 CW 𝑟𝑇 ). Eq. ( 15) can be readily solved by off-the-shelf quadratic programming solvers.3.5.5 Update 𝜶 . The optimization problem for 𝜶 can be formulated as follows:EQUATIONwhere𝑢 𝑟 = P 𝑟 ( t 𝑡 =0 𝛽 𝑟 𝑡 Q 𝑟 𝑡 ) -Z 𝑜 𝑟 CW 𝑟𝑇 2. The values for 𝜶 can be determined using the Cauchy-Schwarz inequality:EQUATION)The procedure of FSIMVC-OF is encapsulated within Algorithm 1.Algorithm 1 Algorithm for FSIMVC-OF.Input: Incomplete dataset {X 𝑟 } 𝑣 𝑟 =1 ∈ R 𝑛 𝑟 ×𝑑 𝑟, the anchor numbers of each views {𝑚 𝑟 } 𝑣 𝑟 =1 , and the cluster number 𝑐. The objective function of FSIMVC-OF has a lower bound of zero. Through decomposing Eq. ( 9) into convex sub-problems, each with a globally optimal solution, the alternating optimization strategies ensure a monotonic decrease in its objective function value until convergence, in accordance with principles outlined in [2] .The computational complexity of FSIMVC-OF encompasses four aspects, as previously mentioned. Generating anchors and constructing bipartite graphs have complexities of O (𝑡 1 𝑣 𝑟 =1 𝑛 𝑟 𝑚 𝑟 𝑑 𝑟 ) and O (𝑘 𝑣 𝑟 =1 𝑛 𝑟 𝑚 𝑟 ) respectively. Computing the high-order graph filter requires O ( 𝑣 𝑟 =1 (𝑛 𝑟 (𝑚 𝑟 ) 2 ) + t (𝑚 𝑟 ) 3 ) time. Updating all variables entails a complexity of O (𝑡 2 𝑐 2 𝑣 𝑟 =1 𝑛 𝑟 𝑚 𝑟 ). Here, 𝑡 1 and 𝑡 2 denote the numbers of iterations for anchor generation and variable updates. Considering 𝑡 1 , 𝑡 2 , t, 𝑚 𝑟 , 𝑐 ≪ 𝑛 𝑟 < 𝑛, the overall computational complexity of FSIMVC-OF remains O (𝑛). Thereby, our method efficiently attains IMVC through linear complexity. 
theoretical analysis: 
 In this section, we delve into the theoretical underpinnings of how the sample-side optimal graph filter H (P 𝑟 , 𝜷 𝑟 ) and anchor-side optimal graph filter H (P 𝑟𝑇 , 𝜷 𝑟 ) contribute to enhancing clustering performance and prove the equivalence between them.As elucidated in [10] , the eigenvalues of a graph Laplacian matrix are indicative of its structural properties: low eigenvalues correspond to overarching features like clusters, while high eigenvalues capture finer details and noise. Thus, for optimal clustering, it is essential to employ a low-pass graph filter capable of attenuating high eigenvalues while preserving the low ones. Consider a graph with a Laplacian matrix L possessing 𝑛 eigenvalues 𝜆 1 ≤ 𝜆 2 ≤ . . . ≤ 𝜆 𝑛 . Let H (•) : R 𝑛×𝑛 → R 𝑛×𝑛 denote a transformation applied to the Laplacian matrix, resulting in eigenvalues ℎ(𝜆 1 ), . . . , ℎ(𝜆 𝑛 ), where ℎ(•) represents the transformation function. Wai EQUATIONHere, 𝜂 acts as the low-pass coefficient, indicating that for a graph filter H (L), if there exists an integer 1 ≤ 𝐾 < 𝑛 and a coefficient 𝜂 < 1, H (L) is considered a low-pass graph filter. Now, we demonstrate that the sample-side graph filter H (P 𝑟 , 𝜷 𝑟 ) in Eq. ( 7) is a low-pass graph filter, as proven in Theorem 1. 2 ) 𝑡 . Hence, we compute its low-pass coefficient 𝜂 as defined in Definition 1:𝜂 = max t 𝑡 =0 𝛽 𝑟 𝑡 ( 2-𝜆 𝐾 +1 2 ) 𝑡 , • • • , t 𝑡 =0 𝛽 𝑟 𝑡 ( 2-𝜆 𝑛 𝑟 2 ) 𝑡 min t 𝑡 =0 𝛽 𝑟 𝑡 ( 2-𝜆 1 2 ) 𝑡 , • • • , t 𝑡 =0 𝛽 𝑟 𝑡 ( 2-𝜆 𝐾 2 ) 𝑡 (19) = t 𝑡 =0 𝛽 𝑟 𝑡 ( 2-𝜆 𝐾 +1 2 ) 𝑡 t 𝑡 =0 𝛽 𝑟 𝑡 ( 2-𝜆 𝐾 2 ) 𝑡 .Given the non-zero singular values of P 𝑟 , denoted by 𝜎 𝐾 ≥ 0, the corresponding eigenvalues of the matrix L 𝑟 are ordered that 𝜆 𝐾 < 𝜆 𝐾+1 . This ordering implies that for any positive integer 𝑡, the inequality 0 < ( 2-𝜆 𝐾 +1) 𝑡 < ( Next, we further show that the anchor-side optimal graph filter H (P 𝑟𝑇 , 𝜷 𝑟 ) in Eq. ( 8) is also a low-pass graph filter by Theorem 2.Theorem 2. The anchor-side optimal graph filter H (P 𝑟𝑇 , 𝜷 𝑟 ) = t 𝑡 =0 𝛽 𝑟 𝑡 I 𝑚 𝑟 +P 𝑟𝑇 P 𝑟 2with 𝜷 𝑟𝑇 1 = 1 and 0 ≤ 𝛽 𝑟 𝑡 ≤ 1 is also a low-pass graph filter.Proof. Similar to the sample-side graph filter learning, utilizing the anchor-side Laplacian matrix L = I 𝑚 𝑟 -P 𝑟𝑇 P 𝑟 , we establish that the anchor-side graph filterH (P 𝑟𝑇 , 𝜷 𝑟 ) = t 𝑡 =0 𝛽 𝑟 𝑡 I 𝑚 𝑟 +P 𝑟𝑇 P 𝑟 2 𝑡with 𝜷 𝑟𝑇 1 = 1 and 0 ≤ 𝛽 𝑟 𝑡 ≤ 1 is also a low-pass graph filter. Detailed proof is omitted due to space constraints. □ Subsequently, we establish the equivalence between the sampleside graph filter H (P 𝑟𝑇 , 𝜷 𝑟 ) applied to the sample-side of bipartite graph P 𝑟 and the anchor-side graph filter H (P 𝑟𝑇 , 𝜷 𝑟 ) operated on the anchor-side of P 𝑟 in Theorem 3.Theorem 3. The process of filtering the graph through sampleside graph filtering, denoted by H (P 𝑟 , 𝜷 𝑟 )P 𝑟 , yields an equivalent result to that of filtering by anchor-side graph filtering, represented as P 𝑟 H (P 𝑟𝑇 , 𝜷 𝑟 ). This equivalence is formally expressed as:EQUATIONProof. Let the SVD decomposition of P 𝑟 be transforms an anchor-side graph signal on 𝑚 𝑟 vertices using the projection matrix V 𝑟 , with the frequency response function given by ℎ(𝜎P 𝑟 = U 𝑟 𝚺 𝑟 V 𝑟𝑇 , where U 𝑟 ∈ R 𝑛 𝑟 ×𝑛 𝑟 , 𝚺 𝑟 ∈ R 𝑛 𝑟 ×𝑚 𝑟 ,𝐾 ) = t 𝑡 =0 𝛽 𝑟 𝑡 1+𝜎 2 𝐾 2 𝑡 .From the above analysis, the following equation holds:H (P 𝑟 , 𝜷 𝑟 )P 𝑟 (21) =U 𝑟              ℎ (𝜎 1 ) . . . ℎ (𝜎 𝑚 𝑟 ) ℎ (𝜆 𝑚 𝑟 +1 ) . . . ℎ (𝜆 𝑛 𝑟 )              U 𝑟𝑇 U 𝑟             𝜎 1 . . . 𝜎 𝑚 𝑟 0 • • • 0 . . . . . . 0 • • • 0             V 𝑟𝑇 =U 𝑟             ℎ (𝜎 1 )𝜎 1 . . . ℎ (𝜎 𝑚 𝑟 )𝜎 𝑚 𝑟 0 • • • 0 . . . . . . 0 • • • 0             V 𝑟𝑇 = U 𝑟 𝚺 𝑟 V 𝑟𝑇 V 𝑟       ℎ (𝜎 1 ) . . . ℎ (𝜎 𝑚 𝑟 )       V 𝑟𝑇=P 𝑟 H (P 𝑟𝑇 , 𝜷 𝑟 ).This equation emphasizes the symmetry in filtering, suggesting that filtering through either the sample side or the anchor side produces the same result. 
experiments 5.1 benchmark datasets: 
 Nine prevalent multi-view benchmark datasets were utilized in our experiments, comprising COIL20, Handwritten [1] , BDGP, Scene-15 [8] , MNIST-10K [15] , ALOI-100 [11] , Reuters, YTF-10 and FMNIST. YTF-10 is a subset of face videos obtained from YouTube. Table 1 provides a summary of these datasets. To demonstrate the superiority of FSIMVC-OF, we compare it with ten state-of-the-art IMVC algorithms including DAIMC [14] , SRLC [53] , LF-IMVC [24] , EE-R-IMVC [23] , IMVC-CBG [36] , SAGF-IMC [18] , SGC-IMVC [20] , LI-MKKM-MR [17] , PSIMVC-PG [16] and FIMVC-VIA [22] . These methods include NMF-based methods, bipartite graph-based methods, kernel-based methods, graph filterbased methods and so on [39] .For each dataset, we generate incomplete versions with missing ratio 𝜀 = 𝑛-𝑛 𝑝 𝑛 varying as [0.1 : 0.2 : 0.9] according to IMVC-CBG [36] . To ensure consistent and fair evaluation, we employ the original code provided by the authors and rigorously follow the suggested settings and parameter search methods for all baseline approaches. Specifically, for each dataset, we generate 10 unique sets of incomplete data corresponding to each defined missing ratio. We then apply each clustering method to these predefined sets. The effectiveness of these methods is assessed by computing the average clustering performance across these 10 sets.To evaluate the clustering performances of different IMVC methods, we employ four well-established evaluation metrics: accuracy (ACC) [41] , Normalized Mutual Information (NMI) [33] and Purity [31] . For all the aforementioned evaluation metrics, higher values indicate better clustering performance.For FSIMVC-OF, the 𝑘-nearest neighbor parameter 𝑘 is fixed to 5 in the entire experiments. The order of graph filter t is fixed to 6, and for comparison purposes, the number of anchors for different views are set as 𝑚 1 = 𝑚 2 = ... = 𝑚 𝑣 = 𝑚, where 𝑚 is searched in {2𝑐, 4𝑐, 6𝑐, 8𝑐}.The comparative analysis in Table 2 reveals the average clustering performance across different missing data ratios. It presents the mean and standard deviation (std) for each method across all datasets and missing ratios, with the top performers marked in red and the runners-up in blue. Methods exceeding a 24-hour computation time are marked with "-", and out-of-memory (OOM) instances are also indicated.Key observations from the results include: (1) FSIMVC-OF stands out, consistently outperforming other methods in ACC, NMI and Purity metrics for most datasets, with a particularly strong showing on dataset D9, where it significantly outperformed the next best results by 69.92% in ACC, underscoring its strength in large-scale scenarios. (2) Despite being designed for large-scale clustering, bipartite graph-based methods like FIMVC-VIA, PSIMVC-PG, and IMVC-CBG show limited performance, possibly due to their struggle with capturing higher-order data information, an area where FSIMVC-OF excels. (3) While SGC-IMVC demonstrates modest improvements in clustering performance through the application of graph filters on sample-sample graphs, its computational intensity renders it is not suitable for large-scale IMVC tasks. (4) As shown in Figure 1 , the superior performance of FSIMVC-OF is consistent across all missing ratios, demonstrating the method's robustness and reliability..In order to evaluate the computational efficiency of the proposed methods, we recorded the average running times of the baseline algorithms on all benchmark datasets with various missing ratios and report them in Figure 2 . The outcomes of certain baseline algorithms on large-scale datasets remain undisclosed due to memory overflow issues. The results suggest that FSIMVC-OF demonstrates the shortest execution running time among all benchmark algorithms across all benchmark datasets, underscoring its superior computational efficiency.In this section, we delve into the analysis of parameter 𝑚. Figure 3 showcases the ACC metric of FSIMVC-OF on datasets D2 and D5 with different value of 𝑚, with a missing ratio of 0.5. Insights gleaned from Fig. 3 reveal that varying values of 𝑚 demonstrate a limited effect on clustering performance. And with the increase of anchor number, clustering performance shows an upward trend as a whole. Collectively, these findings underscore the reliability and efficacy of FSIMVC-OF across diverse parameter settings.Experiments were conducted on datasets D2 and D5 to assess the convergence behavior of our proposed method. The experimental results in terms of the objective function value and ACC of FSIMVC-OF across these datasets are depicted in Fig. 4 . We set the algorithm to iterate 30 times, with a fixed missing ratio of 0.1. As illustrated in Fig. 4 , the convergence behavior of our algorithm unfolds in a distinct pattern. Initially, the algorithm demonstrates a convergence trend, characterized by a gradual decrease in the objective function value. This is followed by a synchronized pattern between the convergence process and the improvement in ACC values. Remarkably, across various datasets, our method consistently achieves convergence within approximately five iterations, underscoring the remarkable time efficiency of FSIMVC-OF. We evaluate the efficacy of adaptive graph filters in FSIMVC-OF through ablation experiments across various datasets. Comparing against two variants: 1) FSIMVC, where adaptive graph filters are removed, and clustering is based on bipartite graphs {B 𝑟 } 𝑣 𝑟 =1 , and 2) FSIMVC-GD, applying view independent graph filter as Eq. ( 4) on each bipartite graph. The fixed parameter 𝜆 = 1 2 aligns with the 3 highlight the full model's superior clustering efficacy, emphasizing the importance of adaptive graph filters in addressing incomplete multi-view clustering. Notably, FSIMVC-GD outperforms FSIMVC, showcasing the benefits of leveraging higher-order information. However, isolated graph filtering lacks adaptability, particularly evident in datasets D3 and D9, further supporting the superiority of FSIMVC-OF. 
conclusion: 
 In conclusion, FSIMVC-OF leverages duality optimal graph filtering to enhance clustering in incomplete multi-view datasets with linear computational efficiency. We introduce a unified consensus clustering framework, supported by a fast optimization algorithm.Comparative experiments on nine datasets show the superiority of FSIMVC-OF over ten leading IMVC methods, underscoring its scalability and efficacy for large-scale IMVC tasks. 
: 
 ACM Reference Format: Liang Du, Yukai Shi, Yan Chen, Peng Zhou, and Yuhua Qian. 2024. Fast and Scalable Incomplete Multi-View Clustering with Duality Optimal Graph 
 
 Appendix:  


Decision: The paper received 3 reviews, recommending weak accept, borderline accept, borderline accept
The main strengths highlighted by the reviewers are the extensive evaluation of the proposed method and the suitability of the contribution to the conference.
The weaknesses seem to have been addressed in the rebuttal document – also for those reviewers that did not comment of the rebuttal in their reviews
Taking into account  the above, I recommend accepting the  paper for poster presentation.

Reviews: review: paper_summary: paper_summary: This paper proposes a novel method aimed at exploring multi-view missing data clusters based on more advanced graph signals. Initially, it constructs the first-order correlation between samples and anchor points based on the local information of the complete samples. By leveraging the equivalence between the sample-side filtering graph and the anchor-side filtering, it obtains graph signals containing more information. This leads to consistent clustering indicators across multiple views.
strength_weakness: strength_weakness: 1. The experimental results are almost state-of-the-art, demonstrating good time complexity and convergence.
2. The method also exhibits relatively stable performance under different missing rate conditions.
limitations: limitations: However, there are several points that require further clarification and improvement:
1. The authors repeatedly emphasize that the "prevalent first-order affinity graph often misclassifies out-neighborhood intra-cluster and in-neighbor inter-cluster samples," but there is no relevant description explaining how the proposed method addresses this challenge. Including some experiments with toy data might help readers better understand how the method overcomes this specific difficulty.
2. The concept of graph filtering on the sample side and anchor side is intriguing. However, it is not clear how the graph filters capture higher-order information.
3. In the final optimization step, all known information from the views is aggregated, and a probabilistic constraint is applied. It raises the question of why not directly partition the clusters based on the probability sizes for the c clusters in Z. Why is it necessary to perform SVD decomposition followed by k-means clustering to obtain the clustering results?
4. In section 5.2, the authors mention comparison methods based on graph filtering. However, I could not find these methods in the references. Clarifying the differences between the proposed method and other graph filtering-based methods would strengthen the paper.
5. There are also minor errors in the notation. For example, in line 299, it should be $\mathbb{R}$, and in line 324, $\{P^r\}_{r=1}^m$ should be $v$ not $m$, be consistent with the previous notation.
paper_summary: paper_summary: The paper presents a novel approach to addressing the challenge of incomplete multi-view clustering in multimedia data analysis. The authors identify the limitations of existing graph learning-based IMVC methods, particularly their inability to accurately classify samples due to data incompleteness and their high computational demands. To overcome these issues, the paper introduces a new method that employs duality optimal graph filtering within a consensus clustering framework. This approach refines the bipartite graph structure by learning an optimal filter, which is applied to the anchor side for computational efficiency. The authors propose an alternative optimization algorithm with linear complexity, which is well-suited for large-scale tasks. Extensive experiments demonstrate the effectiveness of the proposed method.
strength_weakness: strength_weakness: 1.	The paper introduces a novel method that tackles the problem of incomplete data in multi-view clustering by using duality optimal graph filtering.
2.	The authors have designed an optimization algorithm with linear complexity, making the approach highly scalable and suitable for large datasets.
3.	The authors offer theoretical underpinning for their approach.
limitations: limitations: 1.	While the paper claims linear complexity, the actual implementation and optimization of the proposed method might be complex.
2.	Why does the parameter m have a limited effect on clustering performance?
paper_summary: paper_summary: The paper proposes a fast and scalable incomplete multi-view clustering with duality optimal graph filtering, which refines the clustering-friendly structure of the bipartite graph by learning an optimal filter within a consensus clustering framework. It leverages optimal graph filter learning on the sample side to encapsulate higher-order interactions, guiding the enhancement of clustering-friendly structures for the first-order bipartite graphs.
strength_weakness: strength_weakness: 1. The paper exhibits a well-defined structure with cogent and logical writing throughout.
2. The authors have provided access to the code to facilitate reproducibility, ensuring it is meticulously organized.
3. The experimental section of the study is extensive, benchmarking the proposed approach against a range of state-of-the-art rivals on multiple datasets, notably including those of a large-scale dataset.
limitations: limitations: I would like to see ablation experiments on all datasets.