Consistency-Aware Padding for Incomplete Multi-Modal Alignment Clustering Based on Self-Repellent Greedy Anchor Search

1 Introduction

Multimodal clustering [Zhao et al., 2024a; Zhou et al., 2024; Wang et al., 2024] is an important research direction in machine learning and data mining, gaining significant attention due to its ability to leverage the features of multimodal data to enhance clustering results. To better describe the encoded features of each modality, multimodal clustering integrates each modality's complete information that is both aligned and complementary. However, a key challenge in multimodal clustering is addressing the incompleteness and misalignment [Tang et al., 2023; Wang et al., 2023] between modalities. Incompleteness refers to data being ignored or mislabeled as missing, often due to sensor failures, annotation errors, or preprocessing flaws. For example, In industrial monitoring, data may be missing due to sensor(infrared cameras and visual sensors) failures or environmental interference. Misalignment refers to the inability to establish a one-to-one correspondence between data items across different modalities, partially due to differing sensor collection frequencies or acquisition times. For example, in road traffic monitoring research [Dai et al., 2021], the system uses multiple images to determine whether a vehicle is violating regulations or speeding. However, the images of the same vehicle are not captured consecutively. Between the capture of two images, the camera continuously captures images of other vehicles. During data acquisition, incompleteness and misalignment occur simultaneously, significantly affecting subsequent multimodal data fusion[Li et al., 2023d; Liu et al., 2024a]. Current research focuses on how to align and fuse multimodal incomplete data with misalignment characteristics.

∗Corresponding Author

A toy example regarding incomplete and misaligned multimodal data clustering is shown in Figure 1, and the same colour represents data of the same class, with solid lines indicating data matching. On the left, the matching of complete, misaligned, and incomplete multimodal data is shown; on the right, the matching of complete multimodal data and data with both incompleteness and misalignment is shown. From the right side of Figure 1, it can be seen that in the incomplete and misaligned, the data order between the two modalities is inconsistent, and the data sizes are imbalanced.

Incompleteness and misalignment present significant challenges to multimodal clustering. To address these challenges, researchers have proposed various methods. In terms of incompleteness [Zong et al., 2021], Yang et al. [Yang et al., 2023] introduced one seminal work, CGMIMC, which effectively integrates structures across different modalities through consistency graph learning, thereby facilitating the completion of missing data. Li et al. [Li et al., 2023b] designed an IMvC method that simultaneously captures clustering information and modality-specific details through a dual-stream model and performs data recovery using prototypes from other modalities and data-prototype relationships in known modalities. Huang et al. [Huang et al., 2024] restored missing data by dynamically learning feature similarity graphs and proposed a dynamic data quality assessment method, UNIFIER, based on semi-quadratic minimization to mitigate the impact of outliers and unreliable recovered data. In terms of misalignment, Huang et al. [Huang et al., 2020] designed a PVC clustering model, introducing a differentiable alignment module that learns the optimal alignment strategy and can be integrated into deep learning models for alignment learning. Yang et al. [Yang et al., 2021] designed a new noise-robust contrastive loss model, MVCLN, which mitigates the impact of noise on data while enhancing the similarity between features of data from the same class using contrastive learning. Zeng et al. [Zeng et al., 2023] designed the clustering model SMILE using information theory, which addresses completely misaligned multimodal data. By combining autoencoders with two crossentropy losses, it reduces cross-modal differences while enhancing semantic distinction between different classes. Zhao et al. [Zhao et al., 2024b] proposed a progressive alignment learning model, DGPPVC, which, based on a Jaccard similarity variant and dynamic structural graph optimization, gradually identifies unknown correspondences between different modalities from simple to complex. He et al. [He et al., 2024] proposed the VITAL model, which models each data sample as a Gaussian distribution in the latent space. By using variational inference and contrastive learning, the model preserves the commonality and specific semantics between modalities, enabling a comprehensive perception of the data. To address both incomplete and misaligned multimodal data clustering, Yang et al. [Yang et al., 2022] designed a model called SURE. The model directly handles zeroed incomplete and misaligned multimodal data using Hungarian alignment and fills missing data by selecting and filling with the same data through KNN [Shi et al., 2018; Li et al., 2023a]. However, this method may lead to large similarity differences between aligned data pairs and lowerquality data pairs, affecting subsequent data fusion.

When addressing the misalignment of multimodal data, the number of data across modalities is consistent. However, multimodal incompleteness leads to an imbalance in the data across modalities, presenting a challenge for multimodal data alignment. To address the misalignment issue caused by data inconsistency and imbalances, enhance the coherence of data similarity-particularly when data missingness leads to misalignment between views, resulting in a sudden drop in similarity between data pairs (as illustrated in Figure 3)-and improve the quality of data fusion, we propose the Consistency-Aware Padding for Incomplete Multimodal Alignment Clustering Based on Self-Repellent Greedy Anchor Search, termed CAPIMAC. The proposed model primarily consists of three components: the self-repellent greedy anchor search module, the model training module, and the consistency-aware padding module. In the SRGASM, we select anchors [Qin et al., 2024; Liu et al., 2024b; Li et al., 2023c] using a self-repellent random walk [Doshi et al., 2023], guided by a greedy algorithm. This method not only captures the complex local structures between data but also integrates the global information of the anchors. Then, we guide the learning of latent feature representations through a noise-contrastive loss [Zhao et al., 2021a] function. Finally, in the CAPM, we introduce an innovative method by applying equal-weight Gaussian kernel interpolation to fill under-sampled modalities, preventing abrupt decreases in data-pair similarity and improving similarity coherence, thereby obtaining high-quality fused features. Experimental results demonstrate that the model effectively utilizes known data information for filling, thereby addressing the issues of incompleteness and misalignment in multimodal data.

The contributions of this paper can be summarized below.

• We design the self-repellent greedy anchor search module to select anchors. This module selects anchors that are more structurally representative, reducing the complexity of subsequent computations. At the same time, the anchor selection process avoids local cycles and enhances the diversity of exploration.
• We introduce noise-contrastive loss to reduce the impact of false negative pairs, thereby guiding the learning of latent feature representations.
• We innovatively design the consistency-aware padding module to address the padding and alignment issue under imbalanced and misordered multimodal data. In this module, the equal-weight Gaussian kernel interpolation enhances the coherence of data-pair similarity, ensuring one-to-one alignment and fusion of the two modality sample data.

2 RelatedWork

2.1 RandomWalk

Random walk is a fundamental statistical model that tracks random activity. The recursive formula for random walk in a multidimensional space is given by,

p(n) = [p1(n), p2(n) . . . , pN(n)] is the visit probability vector of the nodes at the nth step, and p(0) is the initial state vector, representing the visit probabilities of the nodes at the

0th step. P n is the nth power of the transition matrix, representing the system's state after n steps of the random walk.

Random walk has various applications in machine learning. In adjacency graph construction, Wang et al. [Wang et al., 2020] reduced the time overhead in multi-label classification tasks by constructing a KNN-based random walk graph of training data. In combination with anchors, Liu et al. [Liu et al., 2010] adopted an anchor-based random walk strategy, using anchors as "central" nodes for information propagation, optimizing the flow of information and improving learning efficiency. In node embedding features , Aung et al. [Aung and Ohsaki, 2024] combined node embedding techniques with a random walk, enhancing the random walk process by using node embedding vectors. Additionally, random walk has wide applications in graph generation [Cai et al., 2022], graph enhancement [Kim et al., 2023], anomaly detection [Liu et al., 2023], and graph sampling [Wang et al., 2021].

2.2 Gaussian Kernel Interpolation

Gaussian kernel interpolation is commonly used for data smoothing, missing value imputation, or spatial data interpolation. The core idea is to estimate the value of a point using the weighted sum of Gaussian kernel functions. During Gaussian kernel interpolation, for a new interpolation point x∗ , the interpolated value ˆ y∗ can be expressed as,

where wi is the weight, and K(·) denotes the Gaussian kernel function.

Gaussian kernel functions are widely used in multimodal clustering. For example, Liu et al. [Liu et al., 2020] used Gaussian kernel functions to complete incomplete kernel matrices for learning consensus kernel matrices, addressing the issue of incomplete multimodal data. Ye et al. [Ye et al., 2017]calculated the similarity between modalities based on the Gaussian kernel function and handled the nonlinear relationships in the data through the Gaussian kernel matrix, thereby increasing tolerance to missing data.

3 The ProposedMethod

Given a dataset X = {X(1) ,X(2) ,X(3) , . . . ,X(v) } ,X(v) ∈ Rn×dv , represents the data of the vth modality with n samples and dimensionality dv. To simulate the scenarios of misalignment and incompleteness, we introduce a shuffle matrix U = {U(1) ,U(2) ,U(3) , . . . ,U(v) } and a missing indicator matrix C = {C(1) ,C(2) ,C(3) , . . . ,C(v) } to process X,where U(v) ∈ Rn×1 ,C(v) ∈ Rn×1 .

To address the challenge of effectively filling missing values in incomplete and misaligned multimodal data, we propose the CAPIMAC framework, which consists of two key components:(1) the SRGASM, which selects critical data within each class through a self-repellent random walk strategy and utilizes a greedy algorithm to ensure that at least one key data is chosen from each class;(2) the CAPM, which employs an equal-weight Gaussian kernel padding strategy to ensure consistency in the data count across different modalities, thereby enhancing the coherence of data similarity.

3.1 Self-Repellent Greedy Anchor SearchModule

In multimodal datasets, the high feature dimensionality of data leads to significant computational time during graph construction and training. To address this, we introduce anchors to simplify the representation of the original data. To better capture the complex local structures among the data and simultaneously identify the global optimal solution for the anchors, we propose the SRGASM. The module identifies anchors based on node density using a self-repellent random walk, with the number of steps and step size selected for each modality according to its characteristics,

where nw and wl denote the number of steps and step size, respectively, and N represents the number of data. To describe the transition process between states, a state transition probability matrix is defined for each modality.

Specifically, P is a normalized probability matrix with zeros along the diagonal, and cos(·) represents the cosine similarity between data.

To avoid local cycles and enhance the diversity of exploration, we introduce a decay function rui to reduce the probability of visiting previously visited nodes, where

Here, ui represents the mean of the neighbouring data, and the parameter α ≥ 0 can be viewed as the strength of the selfrepellent module in the self-repellent random walk transition kernel. When α > 0, rui(xi) decreases as xi increases, with larger α leading to faster decay. When α = 0, no decay is applied. At the same time, rui(xi) ensures that the probability matrix P exhibits scale invariance.

In the self-random walk sampling process, a smaller value of α improves the mixing property of the sampling, whereas a larger value of α enhances its efficiency. To strike a balance between the two, we set α = 0.5.Based on the transition probability matrix P, we obtain the visit matrix V,

Where w represents the number of random walks, and t denotes the number of steps in each random walk.

However, when all data in a particular class are significantly distant from data in other classes, it becomes challenging to select points from that isolated class during the self-repellent random walk, resulting in anchors that fail to effectively capture global information. To address this issue, we introduce a greedy algorithm in the self-repellent random walk process to expand the selection of anchors.

In the greedy algorithm, an anchor point xi ∈ X is first selected, and all nodes within a radius of d are marked.s

Next, when selecting the next anchor point xk ∈ X, it is required that its distance to all nodes in the previously selected anchor set S exceeds d, meaning that a node outside the radius is chosen.

Here, Sk denotes the set of all anchors selected at the kth step. Once all nodes have been marked, the marks are reset, and the selection process is repeated until the required number of anchor points is reached.

3.2 Model Training

Since the anchors for each modality are selected independently, this results in mismatched anchor indices in the aligned portions. To standardize the representation dimensions across modalities, we unify the indices of the multiple

Iu denotes the deduplicated sum of the indices across multiple modalities.

To standardize the dimensional representation of multimodal data and facilitate improved training and graph construction, we re-represent the original data X(v) using the selected consistency anchors A(v) = X(v) [Iu],i.e.,

where A ∈ Rna×dv , na represents the number of anchors, which is equal to the size of Iu.

Due to the presence of noisy data in real-world multimodal datasets, we introduce noise-contrastive learning to mitigate the impact of noise. In the traditional contrastive loss,

where,

However, the traditional Lcon loss function has two main issues: first, Euclidean distance struggles to effectively measure similarity between high-dimensional data; and second, in the presence of noisy data, false negative pairs may occur, where two data points in a noisy pair actually belong to the same class. To address these issues, we propose an improved noise-contrastive[Yang et al., 2021] loss function,

where Y represents the labels of positive and negative data pairs, Dc represents the cosine distance, and a is a hyperparameter that controls the distance range within which false negative pairs can be mitigated.

3.3 Consistency-Aware PaddingModule

In scenarios with incomplete and misaligned data, incompleteness leads to an imbalance in the number of multimodal data, while misalignment disrupts the order of data, making data padding challenging. To address these issues, we propose the CAPM, as shown in Figure 3.

For X(v) , we sequentially apply misalignment and incompleteness processing to obtain the data ˆX(v) . Taking two modalities as an example,

Where, U is a shuffle index used to reorder the data in X, and C is a 0,1 index, where 0 indicates a missing data and 1 indicates an existing data, used to remove missing data. The resulting X(1) ∈ Rnv1×dv , X(2) ∈ Rnv2×dv ,and nv1 ̸= nv2. Thus, the re-represented incomplete and misaligned data is,

When the data is aligned, we need to compute a distance matrix Z for Hungarian alignment, where

For convenience, we use ns and nl to denote the smaller and larger data sizes, respectively.

We begin by using the Hungarian algorithm to find pairs of data with high similarity starting from the first row. However, due to class imbalance, some data do not form pairs with other data. Additionally, since missing data are randomly selected, there may be cases where data from different classes are aligned in the already aligned pairs, resulting in a significant disparity in similarity between data pairs. To maintain the coherence of data-pair similarity and reduce the occurrence of misaligned pairs from different classes, we rearrange the data-pair similarities, that is,

Here, Ur is a row transformation indicator matrix that rearranges the rows of Z in ascending order based on the data-pair distances. Next, we select nk(nk = nl -ns) index pairs with the largest similarity differences and perform equal-weight Gaussian kernel interpolation between the indexed data. The Gaussian kernel interpolation function is given by,

where,

Through equal-weight interpolation, we obtain the new distance indicator matrix ¯ Zr ∈ Rnl×nl . Subsequently, Hungarian alignment is performed based on ¯ Zr T (Since no interpolation is performed on the modality with a length of nl, virtual labels can be retrieved, which aids in performance evaluation.), followed by data fusion.

4 Experiments

In this section, we extensively evaluate the clustering property of the proposed method on five widely used multimodal benchmark datasets. The performance of CAPIMAC is compared with seven state-of-the-art multimodal methods (PVC[Huang et al., 2020], MvCLN [Yang et al., 2021], EGPVC [Zhao et al., 2023b], SMILE [Zeng et al., 2023], SURE[Yang et al., 2022], AMCP [Zhao et al., 2024c], DGPPVC [Zhao et al., 2024b]) in terms of four clustering evaluation metrics.

4.1 Experimental Settings

Five datasets are used in our experiments, including 3Sources, yale mtv, BBCsports, Prokaryotic and 100leaves. In the experiments, we first perform data shuffling based on alignment rates, then apply missing data treatment to the shuffled portions. Since there are few models for handling incomplete and misaligned data, in the comparative experiments, we first apply missing data treatment to the models addressing misalignment, followed by Gaussian interpolation for filling and, finally, data shuffling.

The experiments were conducted in a Python 3.8 environment, using PyCharm 2022.2.3 as the integrated development environment. The implementation was based on the deep learning framework PyTorch 1.8.2 with CUDA version 11.1. In the experiments, the alignment rate for all methods was set to 0.3, 0.5, and 0.7, while the incompleteness rate was set to 0.5. Since the primary challenge of multimodal incomplete and misaligned problems is alignment, with data filling being secondary, we used these settings to assess the model's performance under low, normal, and high alignment rates in the presence of typical data incompleteness. To validate the effectiveness of CAPIMAC in clustering, we conducted comparative and ablation experiments using ACC, NMI, ARI and F score(weighted) as performance metrics.

4.2 Experimental Results and Analysis

In this experiment, the best-optimized values for each metric are highlighted in bold, and the second-best values are underlined. BBC refers to the BBCsports dataset, Prok to the Prokaryotic dataset, and F1 to the F score (weighted).

Tables 1,2,4 report the experimental results of eight different methods on five multimodal datasets, evaluated using metrics such as ACC, NMI, ARI and F1. These metrics assess the methods' performance in clustering tasks. From these results, we obtain the following conclusions.

• Tables 1,2,4 present the clustering results of eight models on five datasets. Among the four metrics evaluated on these datasets, our model achieved the best performance in the majority of the results, demonstrating its effectiveness in addressing the multimodal incomplete and misaligned data problem.
• As shown in Tables 1,2,4, our model achieves excellent results on the 100leaves dataset under incomplete data conditions with low, medium, and high alignment rates. This demonstrates that our model can maintain strong clustering performance even when dealing with datasets with a large number of classes.
• When addressing the multimodal misalignment and incompleteness problem, the clustering results of our model show a slight decrease as the alignment rate decreases, yet it still achieves the best performance in the majority of clustering results. This demonstrates that our model has strong robustness and can handle incomplete alignment fusion problems under varying alignment rates.
• Since our model requires selecting anchors from complete data for data re-representation, it is unable to handle incomplete and misaligned datasets with excessively low alignment rates. This is why the model's performance shows a slight decline when the alignment rate is 0.3.
• The experimental results demonstrate that the selected anchors effectively capture both the local and global information of the modality data. Additionally, equalweight Gaussian kernel interpolation addressed the issue of incoherent similarity, further improving clustering performance.

4.3 Time Complexity Analysis

After obtaining the similarity graph, KNN needs to find the k nearest neighbors for each data point xi. The k smallest distances are identified through sorting, which has a complexity of O(nlogn), resulting in an overall complexity of O(n2 logn). However, random walk typically explores only within the local neighbourhood, with a complexity of O(nlogn) or O(n · k).

4.4 Ablation Experiment

Table 3 presents the ablation experiment on whether the model incorporates the CAPM. No IPT indicates that missing data is discarded directly without applying equal-weight Gaussian kernel interpolation; IPT indicates that equalweight Gaussian kernel interpolation was applied.

As shown in Table 3, the CAPM has improved clustering performance to some extent under low, medium, and high alignment rates. Essentially, the CAPM not only utilizes all available data information, increasing data utilization, but also addresses the issue of sharp similarity gaps in imbalanced data, ultimately enhancing the quality of multimodal data fusion.

5 Conclusion

In this paper, we propose CAPIMAC to address the feature fusion problem under the conditions of incomplete and misaligned multimodal data. By designing the SRGASM, we select anchors that capture both local and global information from the modalities. We resolve the alignment and padding issue under misaligned and imbalanced multimodal data through the CAPM, thus improving the quality of the fused features. Our method provides a new perspective for solving the filling problem of misordered and imbalanced data. In the future, we plan to extend CAPIMAC to explore the interpolation and alignment issues in cases where multimodal data are completely misaligned and partially incomplete.

Acknowledgments

This work is supported by the Science and Technology Project of Liaoning Province (2024JH2/102600027, 2023JH2/101700363) and the Science and Technology Project of Dalian City (2024JJ12GX025, 2023JJ12SN029 and 2023JJ11CG005).