TOTF: Missing-Aware Encoders for Clustering on Multi-View Incomplete Attributed Graphs

1 Introduction

As network data in real-world applications exhibit multimodal and multi-relational characteristics [Qu et al.2017], multi-view attributed graphs [Lin and Kang2021, Lin et al.2023, Pan and Kang2021] have attracted considerable attention in practical domains such as social networks [Lu et al.2024], citation networks [Greenberg2009], and biological networks [Kermani et al.2022]. Notably, clustering on multiview attributed graphs [Jin et al.2023, Fettal et al.2023] is a critical task aimed at finding a unified partition that divides nodes into several disjoint clusters. It plays a significant role in various applications, including recommendation systems, community detection, social network analysis, and ride-hailing demand prediction.

∗Corresponding author

Although there are abundant researches about multi-view attributed graph clustering, they ignore incomplete attribute scenarios ragarding privacy concerns, system malfunctions, malicious attacks, or inadvertent omissions. Incomplete attributes are prevalent in many real-life applications [Jiang et al.2024]. For example, the research on Italian social networks about users interested in pharmaceutical products and health shows that there is a prevalence of missing values equal to 64.7% considering all social pages [Mariani et al.2024]. Additionally, in the U.S. healthcare information system, between 13.6% and 81% of data is outdated or lacking completeness [Jr. et al.2005].

In this paper, we focus on multi-view attributed graph clustering with incomplete attributes.

Example 1. Fig. 1 illustrates an example of the multi-view incomplete attributed graph in the social network, containing V views with incomplete attributes. The first view depicts the co-focus relationships on the Weibo platform, where Bob accidentally omits his favorite animal when filling out the form. The V -th view illustrates the colleague relationships, with Tom concealing his home address for privacy reasons. These incomplete attributes may affect the accuracy of clustering, thereby complicating the friend recommendation on the Weibo platform.

PriorWork and Limitations. Existing researches fall into three classes. We list detailed differences in Table 1.

• Multi-view attributed graph clustering. Numerous works like MAGC [Lin et al.2023], MCGC [Pan and Kang2021], and MvAGC [Fan et al.2020] have been proposed for multi-view attributed graph clustering, however, these methods always assume ideal conditions and fail to effectively address incomplete attribute scenarios. As shown in Subsection 5.2, as the miss rate on the ACM dataset increases from 0.1 to 0.7, the accuracy of MvAGC decreases from 0.82 to 0.38, highlighting their struggle with incomplete attributes.
• Single-view incomplete attributed graph learning methods. This class of methods like ASD-VAE [Jiang et al.2024] and GCNMF [Taguchi et al.2021] involves incomplete attribute scenarios. However, they belong to supervised learning and rely on label information of node classification or link prediction. So they are not suitable for unsupervised tasks like clustering. Moreover, these methods are designed for single-view graphs and fail to deal with complex multi-view information.
• Incomplete multi-view clustering methods. This class of methods, like ProImp [Li et al.2023] and ICMVC [Chao et al.2024], is designed for multi-view Euclidean data, whose characteristics are totally different from graphs. Moreover, they focus on the incomplete view which means some samples are missing in several views, as a specific case of incomplete attributes. They are difficult to extend to deal with the more general problem (incomplete attributes).

Challenges and Contributions. Incomplete attributes bring new grim challenges. First, incomplete attributes may distort the inherent patterns and relationships within the data, making it challenging to accurately capture the true distribution of attributes and further affect clustering results. Second, although multi-view graphs can provide more complementary information, the coordination of different views poses a significant challenge. It is crucial to overcome the inconsistencies between these views, as well as those arising from incomplete attributes, to discover the consensus information that is essential for clustering.

In this paper, we propose the TOTF framework to address the problem of multi-view incomplete attributed graph clustering. To our knowledge, this is the first work focusing on this area. Firstly, we train a series of encoders that mitigate the impact of incomplete attributes. We design the Correlation Strength-Aware Graph Neural Network (CSAGNN) based on inherent relationships among attributed graphs. Incomplete attributes occur when some node attributes are missing; thus, while recovering these attributes, we extract information from both neighboring nodes and existing attributes within the node. However, few studies have explored dimensional relationships within graph neural networks. Therefore, we investigate the relationships among attributes via experiments to provide a rationale for CSAGNN. Additionally, we introduce a missing position reminder mechanism to address traditional GAN limitations in handling incomplete attributes and ensure real distribution acquisition. Secondly, we develop a clustering-driven common extractor to integrate multi-view information and learn consensus information essential for clustering tasks from viewspecific information.

In summary, we highlight the contributions as follows:

• To the best of our knowledge, this is the first work to focus on multi-view attributed graph clustering with incomplete attributes.
• We design the TOTF (Train Once Then Freeze) framework to deal with multi-view incomplete attributed graph clustering which trains missing-aware encoders first and then freezes their parameters to further discover common information driven by clustering.
• We propose the correlation strength-aware graph neural network based on the findings of the inherent relationships among attributes through experiment investigation.
• We introduce the missing position reminder mechanism to discriminators and prove that the distribution of generated attributes is the same as the real distribution of attributes when achieving equilibrium.
• Extensive experimental results demonstrate that our method achieves significant accuracy improvements across different levels of incompleteness and is less affected by incomplete attributes.

The rest of this paper is organized as follows. In Section 2, we review related works. Section 3 gives the problem formulation. Section 4 describes our method in detail. Then, we conduct extensive experiments and analyze results in Section 5. Finally, Section 6 concludes this paper.

2 RelatedWork

In this section, we review related works. Incomplete multiview clustering methods are typically designed for Euclidean data with missing samples and are difficult to extend to this general problem with incomplete attributes. Thus, we mainly focus on two other tasks: multi-view attributed graph clustering and incomplete single-view attributed graph learning.

2.1 Multi-ViewAttributed Graph Clustering

Recently, numerous studies have emerged on multi-view attributed graph clustering. MAGC [Lin et al.2023] utilizes the self-expressiveness property to integrate different views. MCGC [Pan and Kang2021] learns a consensus graph regularized by the graph contrastive loss. MvAGC [Lin and Kang2021] accelerates clustering by introducing sampled anchors. LMGEC [Fettal et al.2023] takes clustering and representation learning within a unified framework, reducing the overall time consumption. These methods always assume an ideal scenario where all nodes have complete attributes. However, attributes may be incomplete in real-world scenarios due to various factors, such as personal privacy concerns, accidental damage, or intentional deletion. They fail to effectively address incomplete attribute scenarios.

2.2 Single-View Incomplete Attributed Graph Learning

Single-view incomplete attributed graph learning has been extensively researched. GCNMF [Taguchi et al.2021] utilizes the Gaussian Mixture Model to represent missing features. ASD-VAE [Jiang et al.2024] learns a shared latent space from which the missing values can be imputed. However, these methods are unsuitable for multi-view incomplete attributed graph clustering. First, most methods belong to supervised learning methods, and rely on label information of classification and link prediction, making them unsuitable for unsupervised tasks like clustering. Second, these methods are specifically designed for single-view incomplete attributed graphs and cannot handle the complexities of multiple views.

3 ProblemFormulation

In this section, we introduce our new problem formulation: Multi-view incomplete attributed graph and Multi-view incomplete attributed graph clustering.

Definition 1. (Multi-view incomplete attributed graph) A multi-view incomplete attributed graph can be defined as G = {Φ,A1 , ...,AV ,X1 , ...,XV ,M1 , ...,MV }, where Φ represents the node set. Xv ∈ Rdv×n denotes the attribute matrix for v-th view with dv dimensions. And Av represents the adjacency matrix where Av = {avi,j} ∈ Rn×n and if there exists an edge between nodes vi and vj in the v-th view, avi,j = 1, otherwise, avi,j = 0. Mv is the missing marker matrix in the v-th view, where Mv i,j = 0 if the j-th attribute of the node vi in the v-th view is unknown.

Definition 2. (Multi-view incomplete attributed graph clustering)

Given a multi-view incomplete attributed graph G= {Φ,A1 , ...,AV ,X1 , ...,XV ,M1 , ...,MV }, clustering on multi-view attributed graph aims to find a unified partition fitting all views to divide the nodes of the graph G into k clusters (C1, C2, ..., Ck).

4 ProposedMethod

To cluster on the multi-view incomplete attributed graph, we design a novel framework in which we train the missingaware encoders first and then freeze their parameters. In this section, we describe our model in detail. We summarize the frequently used notations in Appendix A.1 3 .

4.1 Overall Framework of TOTF

The TOTF framework consists of two stages: Missing-aware View-Specific Encoder Training and Clustering-Driven Common Information Discovery, as shown in Fig. 2. In Stage 1, we train a series of missing-aware, view-specific encoders that effectively capture the true distribution in each view while disregarding missing attributes. To address incomplete attributes, we design the Correlation Strength-Aware Graph Neural Network (CSAGNN), which imputes missing values from neighboring nodes and existing dimensions within the same node. Additionally, we implement a missing position reminder mechanism in our intra-view adversarial games to enhance view-specific encoders accurately capturing real attribute distributions despite incompleteness. In Stage 2, we freeze the parameters of the trained encoders and utilize the common extractor with clustering-driven self-supervised loss to derive common information beneficial for clustering.

3 https://anonymous.4open.science/r/TOTF-main

4.2 Correlation Strength-aware Graph Neural Network

Graph neural networks (GNNs) [Lu et al.2024] have been widely applied. However, conventional GNNs like GCN and GAT primarily focus on message passing among neighboring nodes, neglecting the inherent relationships within attribute dimensions. This raises several pertinent questions: Is there a relationship between the dimensions of node attributes? Can the remaining dimensions be utilized to recover any missing dimensions for the same node?

Observation. To address these questions, we employ the Kendall coefficient [Valencia et al.2019] to analyze inherent correlations between different dimensions in attributed graph datasets, as illustrated in Fig. 3. The larger the absolute value of the coefficient, the stronger the correlation. We find that there exist correlations between different dimensions, and the degree of correlation varies across these dimensions.

For instance, in Fig. 3(a), the correlation coefficient between the 702nd and 235th dimensions in Wiki dataset is 0.64, indicating a strong relationship between two dimensions. And the correlation coefficient between the 702nd and 860th dimensions is only 0.10, suggesting a weak relationship. Therefore, if the 702nd dimension is missing, the 235th dimension of the same node can offer more valuable information for recovery compared to that from the 860th dimension.

Inspired by this observation, we propose the Correlation Strength-Aware Graph Neural Network (CSAGNN), which both incorporates messages between attribute dimensions and neighboring nodes, as shown in Fig. 2. In our method, each encoder and decoder contain three layers of CSAGNN, and the 1-th layer of CSAGNN in the v-th view is defined as

where Xv and Av denote the attributed matrix and the adjacency matrix in the v-th view. W v 1 ∈ Rdv×dv is the dimension interaction matrix in the v-th view. W v 2 ∈ Rdv׈ dv1 is the weighted matrix mapping into the hidden space in the v-th view where ˆ dv1<n is the output dimension in the in the 1-th layer. λ2 and λ1 denote weight factors for original features and enhanced features, subject to the constraint λ1 +λ2 = 1. Tnn(∗) is the Tanh activation function. CSAGNN can not only integrate information from neighbors, but also capture the relationships among attribute dimensions, enabling it to use existing attributes for each node. It can initially impute missing attributes and obtain enhanced features, mitigating noise interference before mapping to latent spaces. As a result, compared with traditional GNNs, CSAGNN is more suitable for scenarios with incomplete attributes.

4.3 Intra-viewAdversarial Games with the Missing Position Reminder Mechanism

Intra-viewAdversarial Games. The autoencoder, consisting of a view-specific encoder and decoder, acts as the generator in the intra-view adversarial game, with the discriminator functioning as the opposing entity. The autoencoder aims to generate data closely matching the true distribution, while the discriminator attempts to distinguish between real and imputed data. However, incomplete attributes pose a challenge for autoencoders in capturing the unique true distribution within each view. In Subsection 4.7, Theorem 1 shows that incomplete attributes lead to multiple data distributions satisfying the condition in equilibrium, bringing difficultity to capture the unique true data distribution.

Missing Position Reminder Mechanism. Inspired by [Yoon et al.2018] and [Miao et al.2021], we equip discriminators with the missing position reminder mechanism to address the above issue. We design the missing position reminder matrix Rv ∈ Rn×dv to indicate positions of missing attributes in each view. This allows discriminators to effectively differentiate between real and generated data, while enabling the autoencoder to accurately capture the true data distribution. However, a high reminder rate has drawbacks; for instance, if all missing locations are indicated, the discriminator may make accurate judgments without any training. Thus, the missing position reminder matrix only indicates some locations of missing attributes. The missing position reminder matrix Rv ∈ Rn×dv in the v-th is defined as follows:

where Kv ∈ Rn×dv is a matrix of random variables consisting of 0 and 1, where the number of 1 is decided by the reminder rate h. When Rv ij = 0, we have Mv ij = 0, indicating a missing attribute at this position. When Rv ij = 1, we have M v ij = 1, indicating the attribute exists. However, when Rv ij = 0.5, it is unclear whether the attribute is missing. The missing position reminder matrix helps the autoencoder capture true distribution within each view, disregarding the impact of incomplete attributes. In Subsection 4.7, we prove that with reminder matrices, the distribution of generated attributes is the same as the real distribution at equilibrium.

4.4 Clustering-driven Common Extractor

After Stage 1, we obtain encoders that capture view-specific features while are insulated from incomplete attributes. In Stage 2, instead of using imputed data from Stage 1, we utilize the original data with missing values as input. The original data is passed through frozen encoders to generate viewspecific representations. The clustering-driven common extractor consists of two fully connected layers and exponential linear units, designed to discover common information from view-specific representations.

Inspired by [Chen et al.2022], we introduce the clusteringdriven loss to guide the common extractor to discover common information conducive to clustering. First, we perform the k-means to obtain cluster centers in each view and use the student's t-distribution [Chen et al.2022] to compute similarity scores Q1, ...,QV and Qcom among node representations and cluster centers in each view and consensus view. Then, we calculate the common category assignment distribution Pcom by regularizing the similarity score in the consensus view. After that, the clustering-driven loss is defined as:

where KL(∗||∗) is the KL divergence. The first item aims to pull the common category assignment distribution close to the similarity score of each view. The second item tries to minimize the distance between the similarity scores and the category assignment distribution in the consensus view, then we can utilize clustering information to optimize Zcom.

4.5 Training Strategy

Training Strategy in Stage 1. To capture the view-specific information, we utilize the reconstruction loss and the intraview adversarial game loss. The reconstruction loss for the v-th view, which attempts to minimize differences between the reconstructed and original attributes, is as follows:

whereMv is the missing marker matrix in the v-th view, ˆXv is the reconstructed attributed matrix in the v-th view. || ∗ ||2 represents the L2 norm. In the intra-view adversarial game, the training loss of the discriminator in the v-th view with the missing position reminder mechanism is as follows:

where Dv is the discriminator in the v-th view. Xv is the imputed data via Xv = (1 -Mv ) ˆXv +MvXv . The loss of the autoencoder in the v-th view for Stage 1 is as follows:

In this stage, we first optimize the discriminator and then optimize the autoencoder until the intra-view adversarial game achieves the equilibrium state.

Training Strategy in Stage 2. After Stage 1, we can obtain a series of encoders that capture view-specific features effectively while mitigating the impact of missing information. Then we utilize the trained missing-aware view-specific encoders in Stage 1 to generate view-specific representations.

Algorithm 1: The TOTF Algorithm

Input: Multi-view incomplete attributed graph {A1 , ...,AV ,X1 , ...,XV ,M1 , ...,MV }, the number of clusters k.

Output: k clusters.

• 1 Initialization: Randomly initialization.

// Stage-1: Missing-aware View-Specific Encoder Training

• 2 while not converged do

• 3 Obtain Zv via encoders and reconstruct ˆXv .
• 4 Impute data from Xv = (1 -Mv ) ˆXv +MvXv .
• 5 Calculate Rv via Eq. (2).
• 6 Distinguish imputed data Xv via discriminators.
• 7 Calculate LvD and update discriminators.
• 8 Calculate LvG and update generators.

9 end

// Stage-2: Clustering-Driven Common Information Discovery

10 while not converged do

• 11 Generate Zv of each view via frozen encoders.
• 12 Generate Zcom via common extractor.
• 13 Employ K-means to obtain cluster centers for each view and the consistent view.
• 14 Calculate {Q1, ...,QV ,Qcom} and Pcom.
• 15 Calculate LCE and update common extractor.

16 end

• 17 Perform k-means on Zcom to get the k clusters.
• 18 return k clusters.

The clustering-driven common extractor can capture common information Zcom that is conducive to clustering via the common loss Lcom = ∑Vv=1 ||Zcom - Zv||2 and the clusteringdriven self-supervised loss:

where LCE is the loss of common extractor in Stage 2.

4.6 The TOTF Algorithm

In Stage 1, we train the missing-aware view-specific encoders. Each encoder converts incomplete data to latent embeddings Zv, while decoders reconstruct specific information ˆXv . By combining original and reconstructed data, we obtain imputed data. Then, discriminators differentiate between imputed and original data via the missing position reminder matrix. We calculate losses for discriminators and generators and update them sequentially. Upon convergence, we achieve view-specific encoders that are insensitive to missing information. In Stage 2, we freeze the encoder parameters and generate common representations Zcom through a common extractor. We apply k-means to obtain cluster centers and compute similarity scores for each view and the consistent view. After that, we calculate the common category assignment distribution Pcom. Then, we update the common extractor until convergence. Finally, k-means is performed on common representations Zcom to obtain k clusters.

Comparison Algorithms. The comparison methods contain multi-view attributed graph clustering methods (MAGC [Lin et al.2023] and MvAGC [Lin and Kang2021]) with zero filling and mean filling, single-view attributed graph clustering methods (SDCN [Bo et al.] and AGCN [Peng et al.]) with zero filling and mean filling, and single-view incomplete attributed graph learning methods (ASD-VAE [Jiang et al.2024]). For single-view methods, we execute them on each view and calculate the average results across all views. For ASD-VAE, we remove label-dependent components to adapt for unsupervised clustering tasks.

5.2 Comparison Experiments

We evaluate advanced methods on five datasets across different missing rates. Due to space constraints, we only present results for the Cora, ACM, and Wiki datasets in Table 2. Results for the Aminer and Citeseer datasets are available in Appendix B.2. The detailed observations are as follows.

Firstly, our method performs better than other advanced methods across different miss rates. When the miss rate is 0.1, the accuracy of TOTF is 5% higher than other methods in the ACM dataset, indicating TOTF has an excellent ability to discover common information via the clustering-driven loss. In Table 2, our method achieves at least a 40% improvement in accuracy over the Cora dataset compared to ASDVAE, which shows that as a single-view incomplete attributed graph learning method, ASD-VAE is not well-suited for addressing multi-view incomplete attributed graphs. It may derive from two reasons: First, most of these are designed for supervised tasks that require labeling information, and without labeling information, their accuracy drops significantly.

4.7 Theoretical Analysis

Theorem 1. In intra-view adversarial games, incomplete attributes can hinder the generator from generating the desired distribution (the unique true attributed distribution) when achieving the equilibrium state, as multiple data distributions may satisfy the equilibrium conditions.

Proof. Based on [Yoon et al.2018] and [Miao et al.2021], we give the proof in Appendix A.2.

Theorem 2. Given the missing position reminder matrix Rv , the equilibrium of each view in intra-view adversarial games can be uniquely determined, where the distribution of generated attributes ˆ p(Xv |M v ) is the same as the real distribution ˆ p(Xv |1) in each view, that is ˆ p(Xv |M v ) = ˆ p(Xv |1).

Proof. We prove Theorem 2 based on [Yoon et al.2018] and [Miao et al.2021] in Appendix A.2.

Time complexity analysis. The time complexity of the TOTF algorithm is near O(n2 ) shown in Appendix A.3.

5 Experiments

5.1 Experiment Setting

Metrics and Datasets. We use four evaluation metrics: ACC, F1-score, NMI, and ARI [Fan et al.2020]. We conduct experiments on five datasets-ACM [Lin and Kang2021], AMiner [Hong et al.2020], Cora, Citeseer, and Wiki [Fettal et al.2023] datasets. Details about datasets, hardware platform, and model parameters are shown in Appendix B.1.

Second, single-view methods struggle with complex multiview graphs and are unable to leverage the complementary information across different views effectively.

Secondly, our method is less affected by miss rates compared with other methods and performs well even in high missing rates. As for MAGC and MvAGC, they cannot handle multi-view incomplete attributed graphs effectively. In Table 2, as the missing rate increases, their accuracy declines sharply. On the ACM dataset, as the missing rate increases from 0.1 to 0.7, the ACC metric of MAGC decreases by more than 20%. AGCN and SDCN perform poorly across different rates because they are designed for single-view attributed graphs with complete attributes and are unable to effectively handle these complex scenarios. For our method, on the ACM dataset, when the miss rate reaches 0.7, the accuracy of our method remains above 80%, which is approximately 17% higher than other methods. This indicates that our method can effectively deal with incomplete attributes, and the trained missing-aware, view-specific encoder can capture features accurately and is insensitive to missing information.

5.3 Ablation Studies

To evaluate the significance of each component in our method, we have designed ablation experiments as follows: Case A: W/o (With/Without) Rv . Table 3 shows that discriminators with the missing position reminder mechanism outperform traditional discriminators, improving accuracy by 4% to 6% based on the ARI metric. This indicates that the missing position reminder mechanism allows the discriminator to distinguish between real and fake data more effectively, thereby guiding the generator to produce data that aligns with the true distribution more closely.

Case B: W/o CSAGNN. Table 3 shows that CSAGNN performs better than classical GNNs, improving accuracy by 4% to 9% on the ARI metric. It indicates that CSAGNN is more effective for incomplete attributed graphs as it can combine the information between dimensions and neighbors.

Case C: W/o Lre. Table 3 indicates that the reconstruction loss has a greater impact on all datasets. By minimizing the difference between the reconstructed data and the original data, encoders can better capture view-specific information.

Case D: W/o LC. The results in Table 3 indicate that the clustering-driven self-supervised loss can improve clustering results 2% to 6% according to ARI metric. The combination of LC and Lcom makes the captured consensus information more beneficial for clustering tasks.

Case E: W/o Lcom. Lcom can improve clustering results 2% to 6% according to ARI metric. Lcom can obtain the consensus information from the view-specific information.

Case F: W/o Xv . As shown in Table 3, we find that we do not need to utilize the imputed data from Stage 1. The trained missing-aware view-specific encoders can effectively capture view-specific information while being insensitive to missing data, achieving better results than with imputed data.

5.4 Parameter Sensitivity Analysis

We analyze the parameter sensitivity of the missing position reminder mechanism and the CSAGNN. Figs. 4(a), (c), and (e) illustrate the variation in accuracy across different reminder rates when the missing rate is 0.1. There are only slight differences at varying reminder rates h. Notably, when h = 0.4, the clustering performance is generally optimal. However, when h = 1, there is a noticeable drop in the ARI metric on the ACM and Cora datasets, compared to h = 0.4. Thus, we set the reminder rate to 0.4 in our model. Figs. 4(b), (d), and (f) illustrate the variation in accuracy for different dimensional interaction coefficients when the missing rate is 0.1. Excessively large coefficients result in suboptimal outcomes, while the optimal performance is attained when λ1 = 0.1. Thus, we adopt λ1 = 0.1 for most datasets.

6 Conclusion

In this paper, we first focus on multi-view incomplete attributed graph clustering. We propose the TOTF framework which trains missing-aware encoders first to capture viewspecific information and then freezes their parameters to discover common information available for clustering. Furthermore, we propose the correlation strength-aware graph neural network to discover inherent relationships of attributes. Also, we introduce the missing position reminder mechanism for discriminators. Experiments illustrate that our method can perform excellent performances across all incomplete rates.

Acknowledgments

The research was supported by the Major Research Plan of National Natural Science Foundation of China (Grant No. 92055213), the National Natural Science Foundation of China (Grant Nos. U23A20317, 62172146, 62402481), the Natural Science Foundation of Hunan Province (Grant No. 2023JJ10016, 2023JJ30083), and the Provincial Key R&D Program of Hunan (2024AQ2025).