Initializing Then Refining: A Simple Graph Attribute Imputation Network

1 Introduction

Graph data, which models the relationships between entities, is ubiquitous in practical scenarios. To handle these data, graph representation learning (GRL) has increasingly become a popular research topic and achieved remarkable success in many real-world applications such as social network analysis [Hu et al., 2017], knowledge graph completion [Wu et al., 2020], etc. It has long been proved that integrating the attribute and structure information while conducting the representation learning is essential for improving the quality of sample embeddings [Kipf and Welling, 2017;

∗Corresponding author

Chen et al., 2022]. However, in most real-world graph applications, only a small portion of samples have complete attribute information. For example, in a co-purchase graph of Amazon, consumers tend to selectively (or entirely not) provide their feedback for specific items due to privacy concerns. Consequently, graph representation learning on incompleteattribute graphs is becoming an increasingly important task.

Data imputation is a straightforward mechanism to handle incomplete-attribute graphs. Existing efforts combine the imputation-oriented machine learning techniques, e.g., matrix completion [van den Berg et al., 2017; Zhang and Chen, 2020], generative adversarial network [Spinelli et al., 2020], Gaussian mixture model (GMM) [Taguchi et al., 2021], with graph neural networks (GCNs) and propose various attributeincomplete graph representation learning methods with impressive performance. Although significant progress has been made, the performance of these methods drops drastically when handling attribute-missing graphs, i.e., graphs whose all attribute information of a specific portion of samples is missing. To solve the problem of representation learning on attribute-missing graphs, a recent advanced method named SAT [Chen et al., 2022] introduces a shared-latent space assumption to impute the attribute-missing values at the first attempt. Specifically, SAT first learns the latent representations of attribute and structure spaces independently and then conducts a distribution alignment technique to recover the unknown features of attribute-missing samples. Although SAT achieves encouraging success, when conducting the data imputation, it 1) isolates the learning processes of attribute and structure information embeddings; 2) forces both types of latent variables to align with a common in-discriminative normal distribution. Hence, the negotiation between attribute and structure information tends to get overly rigid, resulting in inaccurate imputation and less discriminative representations.

To overcome the aforementioned issues, this work proposes a novel graph attribute imputation network termed Initializing Then Refining (ITR). To forbid the adverse effect of inaccurate simple initialization and the limitation of rigid assumption, the main idea of our strategy is to make full use of the trustworthy visible information to conduct the sample embeddings for data imputation. As a consequence, on the one hand, we pick out the nodes with complete attributes and learn the sample embeddings by sufficiently combining the attribute and structure information of these samples. On the other hand, we take all the nodes and learn the sample embeddings only according to the structure information. These two processes are illustrated as the upper and underneath pathways in Fig. 1, respectively. The two mentioned operations ensure the quality of latent representations of the nodes with complete attributes, and in the meantime, provide a reasonable initialization to those nodes with missing attributes. After that, to achieve better attribute-missing graph representation learning, the structure embeddings of attribute-missing samples are taken as initial imputed variables and then refined with an adaptively updated affinity structure for embedding refinement. This is illustrated as imputation refinement in Fig. 1. Unlike the prior distribution alignment-based imputation strategy in SAT, our proposed ITR is more general and flexible, since both types of information (i.e., graph structure and node attributes) are allowed to sufficiently negotiate with each other for reliable attribute restoration. The main contributions of this paper are three-fold:

• We propose a simple yet powerful graph attribute imputation network called ITR that can jointly conduct attribute-missing graph representation learning and data imputation without any prior distribution assumption.
• We develop an initializing then refining strategy to have two-source information (i.e., graph structure and node attributes) to sufficiently negotiate with each other for accurate data imputation. By this means, more discriminative latent features could be adaptively collected and preserved to perform high-quality attribute restoration.
• Through experimental results on four benchmarks, we have demonstrated that ITR significantly and consistently outperforms the state-of-the-art counterparts on both profiling and node classification tasks.

2 RelatedWork

Graph Representation Learning. Early solutions to graph representation learning (GRL) mainly include random walkbased methods [Perozzi et al., 2014; Grover and Leskovec, 2016], which first generate the random walk sequences over the network structure properties and then utilize a Skip-Gram model to learn graph representations. These methods heavily rely on structure information and overlook other available properties in the graph, such as attribute information. More recently, since the powerful neighborhood aggregation capacity of graph neural networks (GNNs), many efforts have been made to design GNN-based representation learning methods. These methods can be approximately divided into generative/predictive learning-based methods [Kipf and Welling, 2016; Tu et al., 2021; Liu et al., 2022] and contrastive learning-based methods [Hassani and Ahmadi, 2020; Peng et al., 2020; Zhu et al., 2021]. One underlying assumption commonly adopted by these methods is that the attributes of all nodes are complete. While in real-world scenarios, they may suffer significant performance degradation when handling incomplete graphs.

Data Imputation for Incomplete Graphs. To handle incomplete graphs, data imputation has been widely integrated with machine learning techniques, such as matrix completion, generative adversarial network, and Gaussian mixture model (GMM). For example, NMTR [Gao et al., 2019] and GRAPE [You et al., 2020], the popular matrix completion methods, first regard the user-item rating matrix, users (or items), and the observed ratings as a bipartite graph, node attributes, and linkage relations, respectively. Then these methods employ a GNN-based framework to estimate the probabilities (viewed as imputed values) of absent linkage relations. More recently, GINN [Spinelli et al., 2020] first initializes the incomplete values by a binary mask matrix before network training, and then learns a graph adversarially-trained framework to perform attribute restoration. GCNMF [Taguchi et al., 2021] employs GMM to estimate the incomplete information based on the available one, and in the meanwhile, jointly optimizes GMM and GNN in a united framework. Despite their significant progress, these methods 1) are not suitable for attributemissing scenarios, or 2) disconnect the processes of data imputation and algorithm optimization. To address these issues, an advanced method called SAT [Chen et al., 2022] puts forward to unify data imputation and network learning processes into a single optimization procedure, where two-source information embeddings are learned in a decoupled scheme and then aligned with the Gaussian noise for data imputation. However, to complete the missing values, SAT isolates the learning processes of two-source information embeddings and imposes too strict a distribution assumption on the latent variables, resulting in inaccurate imputation.

3 The ProposedMethod

3.1 Notations

Given an undirected graph G = {V, E} with C classes, where V = {v1, v2, . . . , vN}, E, and N are the node set, edge set, and the number of nodes, respectively. In classic graph learning, a graph is usually characterized by its attribute matrix X ∈ RN×D and normalized adjacency matrix ˜A ∈ RN×N , where D is the node attribute dimension [Kipf and Welling, 2017]. Specially, in the attribute-missing case, with the existence of missing values, we further define V o = {vo 1 , vo 2 , . . . , voN o} and V m = {vm 1 , vm 2 , . . . , vm N m} to be the set of attribute-observed samples and the set of attribute-missing samples, respectively. Accordingly, V = V o ∪ V m, V o ∩ V m = ∅, and N = N o + N m.

3.2 Two-source Information Extraction

Unlike most current imputation-based GRL methods that perform data imputation before network training, our goal is to make full use of all trustworthy observations, i.e., attributeobserved sample information and graph structure information, to accurately impute and restore the unknown features by unifying imputation and network learning into a single optimization procedure. To this end, as shown in Fig. 1, we introduce a pseudo-Siamese architecture, which employs two identical 2-layer graph convolution networks (GCNs) as graph encoders, denoted as Ea(·) and Es(·), respectively. Here we take Ea(·) as an example to introduce the learning process of attribute-observed sample embeddings, and the learning procedure of Es(·) is similar. Specifically, the encoder Ea(·) initially accepts a given observed sub-graph G sub = {Xo , ˜Ao } as input, where Xo ∈ RN o×D and ˜Ao ∈ RN o×N o denote the observed attribute matrix and the corresponding normalized adjacency matrix. Then we compute l-th latent representations of attribute-observed samples Zo(l) a :

whereW(l) indicates the encoder network parameters of the l-th layer. σ(·) denotes the ReLU activation function. Similarly, the encoder Es(·) receives a given structural graph G s = {I, ˜A} and outputs Z(l) s , where I ∈ RN×N is identity matrix and Z(l) s denotes l-th latent representations of G s .

3.3 Initializing Then Refining

Imputation Initialization. Since only partial samples with complete attributes exist, assigning initial values to the attribute-missing ones should be considered before network training. A commonly adopted way is classic data imputation, e.g., zero-filling and mean value-filling. However, in the attribute-missing case, these tricks may introduce much irrelevant information that readily diffuses through the network, resulting in semantically biased representations. To avoid this issue, an underlying solution is to leverage the graph structure information of attribute-missing samples to implement the initial imputation in the latent space. Since the structural properties of the entire graph data are complete, the initialization for attribute-missing samples is reliable. Specifically, after obtaining two-source embeddings, i.e., Zoa ∈ RN o×d and Zs ∈ RN×d , we first select the structure embeddings of attribute-missing samples Zms ∈ RN m×d from Zs, and then combine them with observed attribute embeddings Zoa using Concat function C(·). As illustrated in Fig. 1, the concatenation operation to construct Zi is not the classic channel concatenation. In this operation, we fill the embeddings of attribute-observed samples with Zoa and the embeddings of attribute-missing samples with Zms :

where we denote the initially imputed embeddings as Zi ∈ RN×d . d is the embedding dimension. Please note that the position of each sample is kept unchanged within the graph. Imputation Refinement. As known, the attributes preserve the graph semantics while the structures describe the linkage relations among nodes. Hence, the discriminative capacities of both types of information exhibit differences to some extent. To verify whether our assumption holds, we compare three methods and present analyses on Cora and Citeseer. Ours-Z, Ours-S, and Ours-S-A are methods where we impute the attribute-missing part in the latent space with zero values, the structure embeddings merely, and the structureattribute embeddings, respectively. From the results in Table 1, we observe that the Ours-S method consistently outperforms the Ours-Z method but is not comparable to the OursS-A method. These results hold our expectation and clearly illustrate that although the structure embeddings could effectively serve the initial imputation task, there still exists noise in Zms that would affect the discriminative capacity of latent representations, thus leading to sub-optimal performance. To address this limitation, we try to refine the imputation process by transferring the available semantics Zoa into Zms via an affinity structure H ∈ RN×N . The intuition behind this is that the sample embeddings Zoa are reliable since the attribute information of all attribute-observed samples is complete. In this way, the semantic gap between Zoa and Zms could be narrowed to boost the expressive capacity of the whole embeddings. The above learning process can be formulated as below (i.e., a graph convolution-like operation):

where we denote the imputed embeddings as Z ∈ RN×d , here we set the affinity structure H to ˜A for initialization.

In Eq.(3), we observe that the noise information in Zms can also diffuse across the attribute-observed part, which would make the representations of Zoa less discriminative. In this circumstance, conducting the embeddings of both attribute-observed and attribute-missing samples simultaneously would undermine the quality of sample embeddings and the reconstruction accuracy of available samples, which would in turn affect the subsequent data imputation tasks and even distort the original graph. To overcome this issue, we introduce an information recomposing scheme. Firstly, we merely select the latent variables of attribute-missing samples Zm ∈ RN m×d from Z, and then recompose them with Zoa :

where we denote the recomposed embeddings as ˜Z ∈ RN×d . In our settings, the information recomposing operation replaces the adjusted embeddings of attribute-observed samples with more reliable Zoa . By doing this, we reduce the adverse effect of inaccurate information passing from the embeddings of attribute-missing samples. Moreover, the embeddings of attribute-observed samples are fixed as Zoa in the final step, as shown in Fig, 1. This provides the most trustworthy information of those samples for subsequent data imputation tasks.

It is worth noting that the initial affinity matrix H (i.e., ˜A) is not the ground truth. The errors within this matrix are twofold: 1) noisy connections. Besides inner connections within clusters, inappropriate connections could exist between clusters in the matrix; 2) missing connections. In ˜A, only the firstorder connections are recorded, the higher-order connections could be missing. Both would cause the inaccurate reconstruction of observed attributes and missing attributes. To overcome these issues, we seek to refine H to further improve the imputation quality via an affinity structure updating scheme. Specifically, we first generate a normalized selfcorrelated matrix S ∈ RN×N according to ˜Z as below:

where N(Y) = D- 1 2 Y YD- 12 Y denotes the structural normalization function, DY ∈ RN×N is the degree matrix of Y. ˜zj (˜zk) indicates the embedding of node vj (vk). Then we update the affinity structure H every t iterations via Eq.(6), and adopt it to refine the subsequent imputation process:

where α is a balanced coefficient, and we initialize it as 0.5. In this way, the affinity structure updating operation allows the network to construct the embeddings of attribute-missing samples with not only the first-order but also the higher-order connections from the original graph. Since the embeddings of attribute-observed samples become more reliable and the embeddings of attribute-missing samples become more informative, the quality of the overall graph embeddings is boosted.

3.4 Decoding andModel Training

Finally, we directly feed ˜Z with ˜A into the denoder D(·) to complete the attribute restoration, which is formulated as:

where ˜W(l) indicates the decoder network parameters of the l-th layer. ˜Z(0) and ˜Z(2) denote the recomposed embeddings ˜Z and the rebuilt attribute matrix ̂X ∈ RN×D , respectively. The overall objective of ITR consists of two parts:

In Eq.(10), La refers to the mean square error (MSE) between the attribute-observed part of both X and ̂X. Ls refers to the binary cross-entropy (BCE) between the normalized adjacency matrix ˜A and the rebuilt adjacency matrix ̂A ∈ RN×N , where ̂A = Ω(Zs ˜ZT), Ω(·) is a sigmoid activation function. λ and γ are two balanced coefficients.

4 Experiments

4.1 Experimental Setup

Benchmark Datasets. We conduct experiments to evaluate the proposed ITR on four benchmark datasets, including Cora [McCallum et al., 2000], Citeseer [Sen et al., 2008], Amazon Computer (Amac), and Amazon Photo (Amap) [Shchur et al., 2018]. Table 2 summarizes the dataset information.

Parameters Setting. For all compared methods except for GINN [Spinelli et al., 2020] and GCNMF [Taguchi et al., 2021], the experimental results are acquired according to the paper of SAT [Chen et al., 2022]. For GINN and GCNMF methods, we run their public code by following the settings of the original papers, and then report the corresponding performance. For our proposed ITR, we strictly follow the principle of data splits as was done in SAT [Chen et al., 2022], including the split ratio of attribute-observed/-missing samples and the split ratio of train/test sets. Specifically, 1) in the profiling task, we randomly sample 40% nodes with attributes as the training set, and manually mask all attributes of the rest of 10% and 50% nodes (i.e., attribute-missing samples) as the validation set and the test set, respectively. We employ a symmetric backbone framework consisting of 4-layer GCNs and optimize it with the Adam optimization algorithm, where we set the learning rate to 1e-3. During the training phase, we transfer all samples into our ITR to restore missing attributes by merely reconstructing the attribute-observed samples (i.e., training set). After training, we directly generate the rebuilt attribute matrix over the well-trained model via forwarding propagation; 2) in the node classification task, the restored attributes are randomly split into 80% and 20% for training and testing. We train the classifier with five-fold validation for 1000 iterations and repeat the experiments 10 times. Moreover, the learning rate, the latent dimension, the dropout rate, and the weight decay are set to 1e-3, 64, 0.5, and 5e-4, respectively. Please note that we do not carefully tune these parameters for the ease of training as was done in SAT.

4.2 Performance Comparison

In the profiling task, for fairness, we follow the baseline settings of SAT and compare ITR with nine methods using Recall and NDCG as metrics, including a classical profiling method NeighAggre [ ¨Ozg¨ur Simsek and Jensen, 2008]; an auto-encoder-based method VAE [Kingma and Welling, 2014]; three typical GCN-based methods, i.e., GCN [Kipf and Welling, 2017], GraphSage [Hamilton et al., 2017], and GAT [Velickovic et al., 2018]; two attributed random walkbased methods, i.e., GraphRNA [Huang et al., 2019] and ARWMF [Chen et al., 2019]; a cold-start recommendation method Hers [Hu et al., 2019]; an attribute-missing GRL method SAT [Chen et al., 2022]. In addition, we compare ITR with two attribute-incomplete GRL methods, i.e, GINN [Spinelli et al., 2020], GCNMF [Taguchi et al., 2021], and report their accuracy performance for node classification.

As shown in Table 3, we can see that ITR outperforms all compared methods in terms of six metrics on four datasets. Taking the results of Recall@50 and NDCG@50 for example, SAT has been considered the strongest attribute-missing GRL method. The proposed ITR exceeds it by 2.18%/2.48%, 3.07%/4.22%, 1.06%/1.86%, and 0.46%/0.91% on four datasets, respectively. Moreover, Table 4 illustrates the node classification performance of all compared methods. "X" or "X+A" indicates that we perform the node classification task to estimate the quality of the attribute restoration using merely attribute or both structure-attribute information. From the results on four datasets, we observe that 1) the recently proposed attribute-incomplete GRL methods ( i.e., GINN and GCNMF) are not comparable to ours, ITR exceeds them by at least 15.26%, 4.69%, 6.38%, and 4.08% accuracy increment; 2) ITR gains 4.99%, 7.05%, 9.78%, and 3.13% performance enhancement over the state-of-the-art method SAT. The above results on two tasks have solidly verified the effectiveness of ITR. These benefits can be attributed to the following merits: 1) different from the compared methods, for handling attribute-missing graphs, we develop a more expressive imputation network that avoids the reliance on any prior distribution assumption; 2) ITR can make full use of the trustworthy visible information to conduct the sample embeddings for high-quality attribute restoration; 3) we introduce a more general and flexible imputation strategy, which can facilitate the negotiation between attribute and structure information for accurate data imputation.

4.3 Ablation Study

Effect of Each Component. To verify the benefit of each component, we conduct ablation studies on four datasets for ITR and two ITR variants, each of which has one of the key components removed. ITR w/o IR and ITR w/o ASU indicate the method with information recomposing and affinity structure updating being masked, respectively. From the results in Fig. 2, we observe that the accuracy of ITR on the four datasets would degrade without one of the key components. Specifically, for the "X" task, ITR exceeds ITR w/o IR by 2.54%, 1.53%, 2.24%, and 1.64% accuracy increment, and ITR w/o ASU by 0.69%, 0.30%, 0.98%, and 0.55% accuracy increment on Cora, Citeseer, Amac, and Amap, respectively. We find that the information recomposing scheme plays a more important role than the information refining scheme. To visually illustrate this point, we present the mean square error (MSE) comparison of ITR and ITR w/o IR at the last training iteration. As seen in Fig. 3, it is obvious that, with the information recomposing scheme, the method can achieve a good convergence as well as a high-quality attribute restoration.

Analysis of the Observed Ratio. To further show the superiority of ITR, we compare it with the strongest baseline SAT on Cora and Citeseer by varying the observed ratio from 20% to 80%. As shown in Table 5, taking the results of Recall@10

on Citeseer for example, our ITR outperforms SAT by 1.10%, 1.85%, 2.29%, and 2.63% with the variation of observed ratio from 20% to 80%. The improvement is more significant with the increase in the observed ratio. This observation has well verified the robustness of our ITR.

Hyper-parameter Analysis. Fig. 4 reports the NDCG@10 performance variation of ITR on Cora and Citeseer when λ and γ vary from 0.1 to 0.9 and 1 to 20, respectively. From the figures, we observe that 1) for a specific γ value, the performance shows a trend of first rising and then dropping slightly with the variation of λ. This indicates that our ITR needs a proper coefficient for auxiliary loss to rebuild the adjacency matrix. The observations of γ are similar; 2) ITR tends to perform well by setting λ and γ to 0.5 and 10, respectively.

5 Conclusion

In this work, we have designed a novel graph attribute imputation approach called ITR toward attribute-missing graph representation learning. In our method, an initializing then refining strategy is carefully designed to perform data imputation in an adaptive manner. By this means, two-source information is allowed to sufficiently negotiate with each other in the latent space. Thus the expressive capacity of imputed variables can be improved for high-quality attribute restoration. Extensive experimental results have verified the superiority and effectiveness of our proposed ITR.

Acknowledgments

This work is supported by the National Key R&D Program of China (Grant No. 2018YFB1800202, 2020YFC2003400, and 2020AAA0107100), the National Natural Science Foundation of China (Grant No. 61922088, 62006237, 62072465, 62162024, and 62162022).