Active Sampling for Node Attribute Completion on Graphs
Authors: Benyuan Liu
Xu Chen
Yanfeng Wang
Ya Zhang
Zhi Cao
Ivor Tsang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Network
Node Attribute Completion
Active Sampling

Abstract: Node attribute is one kind of crucial information on graphs, but real-world graphs usually face attribute-missing problem where attributes of partial nodes are missing and attributes of the other nodes are available. It is meaningful to restore the missing attributes so as to benefit downstream graph learning tasks. Popular GNN is not designed for this node attribute completion issue and is not capable of solving it. Recent proposed Structure-attribute Transformer (SAT) framework decouples the input of graph structures and node attributes by a distribution matching technique, and can work on it properly. However, SAT leverages nodes with observed attributes in an equally-treated way and neglects the different contributions of different nodes in learning. In this paper, we propose a novel active sampling algorithm (ATS) to more efficiently utilize the nodes with observed attributes and better restore the missing node attributes. Specifically, ATS contains two metrics that measure the representativeness and uncertainty of each node's information by considering the graph structures, representation similarity and learning bias. Then, these two metrics are linearly combined by a Beta distribution controlled weighting scheme to finally determine which nodes are selected into the train set in the next optimization step. This ATS algorithm can be combined with SAT framework together, and is learned in an iterative manner. Through extensive experiments on 4 public benchmark datasets and two downstream tasks, we show the superiority of ATS in node attribute completion.

Under review as a conference paper at ICLR 2023
ACTIVE SAMPLING FOR NODE ATTRIBUTE COMPLE- TION ON GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Node attribute is one kind of crucial information on graphs, but real-world graphs usually face attribute-missin problem where attributes of partial nodes are miss- ing and attributes of the other nodes are available. It is meaningful the missing attributes so as to benefit downstream graph learning tasks. Popular GNN is not designed for this node attribute completion issue and is not capable of solving it. Recent proposed siructure-attribur Transformer (SAT) framework de- couples the input of graph structures and node attributes by a distribution matching technique, and can work it properly. However, SAT leverages nodes with ob- served attributes in an equally- way and neglects the different contributions of different nodes in learning. In this paper, propose novel active sampling algorithm (ATS) to more efficiently utilize the nodes with observed attributes and better restore the missing node attributes. Specifically, ATS contains two metrics that measure the representativeness and uncertainty of each node's information by considering the graph structures, representation similarity and learning bias. Then, these two metrics are linearly combined by a Beta distribution controlled weighting scheme to finally determine which nodes are selected into the train set in the next optimization step. This ATS algorithm can be combined with SAT framework together, and is learned in an iterative manner. Through extensive ex- periments 4 public benchmark datasets and two downstream tasks, we show the superiority of ATS in node attribute completion.
restore
INTRODUCTION
Node attribute, known as a kind of important information on graphs, plays vital role in many graph learning tasks. It boosts the performance of Graph Neural Network (GNN) Defferrard et al. (2016): Kipf & Welling (2017); Xu et al.] (2019b); Veličković et al. (2018) in various domains, e.g. node classification Jin et al. (2021); Xu et al. (201a)) and community detection (Sun et al. (202
Chen et al. (2177). Meanwhile, node attribute provides human-perceppive demonstrations for the non-Euclidean structured data Zhang al. (2019: Li et al. (2021). In spite of its indispensability, real-world graphs may have missing node attributes due to kinds of reasons CCen et al. (2022).
For example, in citation graphs, key terms detailed content of some papers may be inaccessible because of copyright protection. In social networks, profiles of some users may be unavailable due to privacy protection. When observing the attributes of partial nodes on graphs, significant to restore the missing attributes of the other nodes so as to benefit the downstream graph learning tasks. Namely, this the goal of node attribute completion task.
Currently, there are limited works on the node attribute completion problem. Recent graph learning algorithms such as network embedding Cui et al. (2018) and GNN are not targeted for this problem and are limited in solving it. Random walk based methods Perozzi et al. (2014); Tang et al. (2015);
Grover Leskovec (2016) are effective in learning node embeddings on large-scale graphs. While they only take the graph structures into consideration and ignore the rich information from node attributes. Attributed random walk models Huang et al. (2019); Lei Chen & Bronstein (2019) can potentially deal with this problem but they rely on high-quality random walks and carefully designed sampling strategies which are hard to be guaranteed Yang et al. (019). The popular GNN framework takes graph structures and node attributes a coupled input and can work the node attribute completion problem by some attribute-fillin filling tricks, while these tricks introduce noise learning and bring worse performance. In last few years, researchers begin concentrate the learning

---

Under review as a conference paper at ICLR 2023
problem on the serributemisssng graphs. Chen et al. transformer (SAT) framework that can handle the node attribute completion case. SAT leverages structures and attributes in decoupled scheme and achieves the joint distribution modeling by matching the latent codes of structures and attributes.
(2022) propose novel structure-attribute
Although SAT has shown great promise on node attribute completion problem, it leverages the nodes with observed attributes in an equally-treated manner and ignores the different contributions of nodes in the learning schedule. Given limited nodes with observed attributes, is more important to notice that different nodes have different information (e.g. degrees, neighbours. etc.) and should have different importance in the learning process. Importance re-weighting [Wang et al.] (2017); Fang et al. (2020); Byrd & Lipton (2019) on the optimization objective may come to mind to be a potential solution. Whereas, the information of nodes influenced by each other and has more complex patterns. The importance distribution is implicit, intractable and rather complicated, raising great difficulties design its formulation. It's challenging to find a more practical way to exert the different importance of the partial nodes with observed attributes at different learning stages.
In this paper, we propose an active sampling algorithm named ATS to better leverage the partial nodes with observed attributes and help SAT model converge to more desirable state. In particular, ATS measures the representativeness and uncertainty of node information on graphs to adaptively and gradually select nodes from the candidate set to the train set after each training epoch, and thus encourage the model to consider the node's importance in learning. The representativeness and uncertainty are designed by considering the graph structures, representation similarity and learning bias. Furthermore, it is interesting to find that the learning prefers nodes of high representative- ness and low uncertainty the early stage while low representativeness and high uncertainty the late stage. Thereby, we proposes a Beta distribution controlled weighting scheme to exert adaptive learning weights on representativeness and uncertainty. In this way, these two metrics are linearly combined as the final score to determine which nodes are selected into the train set in next opti- mization epoch. The active sampling algorithm (ATS) and the SAT model are learned in an iterative manner until the model converges. Our contributions are summarized follows:
In node attribute completion, to better leverage the partial nodes with observed attributes, we advocate to use active sampling algorithm to adaptively and gradually select samples into the train set in each optimization epoch and help the model converge to a better state.
We propose a novel ATS algorithm to measure the importance of nodes by designed rep- resentativeness and uncertainty metrics. Furthermore, when combining these two metrics as the final score function, we propose Beta distribution controlled weighting scheme to better exert the power of representativeness and uncertainty in learning.
We combine ATS with SAT, a newly node attribute completion model, and conduct exten- sive experiments on 4 public benchmarks. Through the experimental results, we show that our ATS algorithm can help SAT reach better optimum, and restore higher-quality node attributes that benefit downstream node classification and profiling tasks.
2 RELATED WORK
2.1 DEEP GRAPH LEARNING
With the development of deep representation learning in the Euclidean vision domain Voulodi- mos et al. (2018), researchers have studied a lot of deep learning methods on the non-Euclidean graphs Zhang et al.] (2022b). Random walk based methods can learn node embeddings by random walks which only considers the structural information and cannot generalize to new graphs. To tackle this problem. the attributed random walk based methods (c.g. GraphRNA Huang et al. (2119) apply random walks on both structures and attributes. These random walk based methods are prac- tical, but they demand hardly-acquin Graph Neural Network (GNN) Scarselli et al. realizes 'graph-in, graph-out that transforms the embeddings of node attributes while maintaining the connectivity Meanchez-Lengelineg is reminiscent of standard convolution in Graph Convolutional Networks (GCN) Kipf & Welling (2017). GNN can infer the distribution of nodes based on node attributes and edges and achieve impressive results on graph-related tasks. There are also numerous creative modifications in GNN.
high-quality random walks to guarantee good performance.
et al. (2016); Kipf & Welling (2017)
et al. (2021) GNN performs a message passing scheme, which
2

---

Under review as a conference paper at ICLR 2023
GAT Velicković et al. (2018) introduces multi head attention into GNN. GraphSAGE/Hamill et al. (017 moves to the inductive learning setting to deal with large-scale graphs
Recently, more works have emphasized the importance of node attributes in graph-related down- stream tasks. Both SEAL Pan et al.] (2022) and WalkPool Zhang & Chen (2018) encode node representations with node attributes to achieve superior link prediction performance. In most real-
world scenarios, attributes of some nodes may be inaccessible, so the node attribute completion task appears. Despite GNN's success, there are few works on this task. Recent SAT [Chen al. (2022) assumes a shared-latent space assumption on graphs and proposes a novel GNN-based distribution matching algorithm. It decouples structures and attributes and simultancously matches the distribu- tion of respective latent vectors. WGNN developed by [hen et al. (202T) learns node representa- tions Wasserstein space without any imputation. Jin et al. (2021) propose the HGNN-AC model to learn topological embedding and attribute completion with weighted aggregation. PaGNNs Piang & Zhang (2020) can reconstruct the missing attributes based on partial message-propagee scheme. Among them, SAT performs well and has open-source implementations, we refer to SAT primary base model for completing missing node attributes.
2.2 ACTIVE SAMPLING ON GRAPHS
Active learning assists the model to achieve as better performance possible while labeling few samples as possible Ren et al. (202I). It's usually combined with deep learning model to select the most influential samples from unlabeled dataset and then label them for training reduce the annotation cost Yoo & Kweon 2019). There are also some works of active learning on graph data.
Early works Gadde et al. (2014); y Gu et al. (2013); Ji & Han (2012) mainly take graph structures
into consideration and design the query strategy regardless of node attributes. With the development of deep learning, many active learning algorithms are designed based on GNN. The query strategy of AGE Cai et al. (2017) measures the amount of the information contained in different nodes to select the most informative candidate node. Similar to AGE, ANRMAB Gao et al. (2018) adopts the weighted sum of different heuristics, but it adjusts the weights based on a multi- bandit frame- work. Caramalau et al. (202I) discuss two novel sampling methods: UncertainGCN and CoreGCN, which are based uncertainty sampling and CoreSet (Sener & Savarese (2017). respectively.
Nevertheless, most of today's popular active sampling algorithms on graphs aim to resolve the node classification task and focus how reduce the annotation cost. For this node attribute comple- tion task, since the attribute-observer nodes are limited and the dimension of node attributes is much higher than node classes, we demand a more advanced active sampling algorithm help the primary model utilize the attribute-observed nodes more efficiently and learn the complicated attribute dis- tribution better. In addition, the current query strategies measure the uncertainty by an unsupervised manner, but we propose supervised one to make the sampling closer to the primary model.
PRELIMINARY
3.1 PROBLEM DEFINITION
For node attribute completion task, we denote G (V, X) as graph with node set V {Ui, U2,... J. the adjacency matrix A E A and the node attribute matrix X E RN
Vo {09, 02, og,... J is the of attribute-observed nodes. The attribute information of vo is X = (29, -2y... NN. and the structural information of yo is A {af, ag. --.. 2% )- n" {of,, ui ...,, oN is the set of attribute-mise miising nodes. The attribute information of ' is X {2", xx ..., 2% and the structural information of yd is A"
aa" a". .... a }. More specifically, we have V V" U Vo, y" n vo 0, and N N. + Nu. We expect to complete the missing node attributes X" based on the observed node attributes X and structural information A.
For active sampling algorithm, we denote the total training set as T, in which the node attributes are known. The current training set of SAT model is T and the set containing the candidate nodes is denoted as T We have T h U T.. We design reasonable sampling strategy named ATS which iteratively transfers the most suitable candidate nodes from T to T to boost the training efficiency of SAT until T 0 and the model converges.
3

---

Under review as a conference paper at ICLR 2023
3.2 STRUCTUUR-ATTRRIBUT TRANSFORMER
Dx
Advenartsi Dietibbttin Matching
piat
Ex
DA
Figure 1: The general architecture of SAT. The attributes and the structure encoded by Ex and EA and reconstructed by Dx and DA- Meanwhile, SAT matches the latent codes of structures and attributes prior distribution by adversarial distribution matching.
Since we combine SAT with our ATS to demonstrate how ATS works, we briefly introduce SAT in this part. The general architecture of SAT is shown in Figure ! SAT inputs structures and attributes in decoupled manner, and matches the joint distribution of structures and attributes by a paired structure-attrinn matching and an adversarial distribution matching. During the paired matching, have structure encoder E (a two-layer GNN such GCN) and an attribute encoder Ex (a two-layer MLP) that encodes the structural information a; and the attribute information v; into Zn and Zn, respectively. Then two decoders Da and Dx decode za and ze as the structures ag and attributes v; in both parallel and cross ways. Encoders and decoders are parameterized by and respectively. The joint reconstruction loss L, of SAT can be written as:
min Ba.a::a
C. =
2 Ex,, [e (z, (m.) log Pe_ (2 [x)]] Ba, [B (ea (a.) [lg po. (a. =a)]]
2 do Es, [B (sala:) la.) [log (xi|=a)]] 2 Ex, (2. (o.) log pa. (a: [z,]]] (1)
where Pes and psa are the encoders, as and Pse are the decoders. The first two terms in Eq. represent the self-reconstruction stream. The latent variable āz. 2a are decoded Xo, Å by two- layer MLP decoders Dx, DA respectively. The last two terms indicate the rroostecconttttttioo stream, where 2, and za decoded to Á and X respectively.
During the adversarial distribution matching, SAT expects to match the posterior distributions 9a. (2;) and qo. (zala;) Gaussian prior p(2) ~ NO 1). Inspired by Makhzani et al. (2015), SAT adopts an efficient adversarial matching approach between Zn. 2a and samples from the Gaus- sian distribution. The adversarial distribution matching loss Lado be written a minimax game:
min max Ladv = E =x,>(()) log ((pp) Ez,rgs (z, (a.) Dlg(1 D(2x))1
V Pa
Ex,))(=) log D(zp)l Exa (z (sola.)llog(1 D(=.))]
where v is the parameters of the shared discriminator D. In summary, the objective function of SAT is:
min max L L, Ladv
6 +
where θ {0., 0a. Pz. Pe. 3) + (Φ., }. In the training phase of the node attribute com- pletion task, SAT aims to minimize the reconstruction loss between Á, X and A, X in Eq. | as well as the adversarial loss in Eq.2) 2 In testing, it encodes the structural information A of attribute- missing nodes by the encoder EA and then restore their missing attributes X" by the decoder Dx.
METHOD
We design the query strategy of ATS by measuring the representativeness and uncertainty of the candidate nodes. Then combine the scores of uncertainty and representativeenss the final score by an adaptive reweighting scheme and select the nodes with the highest scores for next learning epoch. We will explain these more in the following parts.
4

---

Under review as a conference paper at ICLR 2023
4.1 QUERY STRATEGY OF ATS
The major and typical patterns among the nodes are vital for the model to converge the right direction. In this section, we introduce the concept of representativeness as a sampling metric. This metric is composed of two parts: 1) information density @density and 2) structural centrality Pcentrality. The former mainly focuses on measuring the similarity between the corresponding latent vectors of attributes and structures. The latter indicates how closely a node connected to its neighbours on graph. In other words, the information density is inspired by the good representation learning ability of SAT and the structural centrality is natural to mine the information on the graph structures. These two aspects offer us a comprehensive analysis of the representativeness in both implicit and explicit ways.
Representativeness:
We first focus on the information density. SAT proposes a shared-latent space assumption for node attribute completion. We can study the node similarities through the implied features learned by the model. If there is a dense distribution of representation vectors in a local region of the latent space, the corresponding nodes will have more similar features and this region will contain further mainstream information, so we expect to train these more representative nodes in priority. For node attribute completion task, although there are attribute embeddings and structure embeddings in shared-latent space, our ATS only uses the structure embeddings žn, to calculate the @density as shown in Eq. 4 since we rely on the structural representations restore the missing node attributes. In order to find the central node located in high-density region, we employ the K-means algorithm in the latent space and calculate the Euclidean distance between each node and its clustering center. Given d as the metric of Fuclidean distance in 12-norm and Cza, as the clustering center of 2a, in latent space, the formulation of @density is written as:
Odensity 1 dZ Co..) U/ T
The larger the @density is, the more representative the node is, and the node contains more represen- tative features that are worthy of the model's 's attention.
Besides the feature analysis in latent space, the node representativeness can also be inferred from the explicit graph structures. We can study the connections between nodes and develop a metric to calculate the node centrality based on the structural information. Intuitively, the centrality can have a positive correlation with the number of neighbours. At the early stage of training, if we can focus on these nodes, the model will learn the approximate distribution of the data faster and reduce the influence caused by the noisy ones. PageRank Page et al. (1999) algorithm is an effective random- walk method to acquire the visiting probabilities of nodes. We utilize the PageRank score as the structural centrality Qcentrality which is shown as below:
Qcentratity (t:) ΣA; Aij (centrolity(()) -
1-p NU T
(5)
Ee Ask
where N is the number of nodes in T p is the damping parameter. The larger ccentrality is, the more representative the node is, and the node is more closely associated with its neighbours.
Uncertainty: Uncertainty reflects the learning state of the current model towards the nodes. When the model is reliable, it's reasonable to pay more attention the nodes that have not been sufficiently learned. Uncertainty is a commonly-used query criterion in active learning. However, as mentioned before, the uncertainty in other sampling algorithms Cai al. (2017); Caramalau al. (2021) /Zhang eet al. (2022a) usually works for node classifications and is designed in an unsupervised manner to reduce the annotation cost. In this paper, for the node attribute completion task, in order to know the training status of the model more accurately, we consider the observed attributes and structures as supervision, and use the learning loss in SAT as the uncertainty metric, noted as Dentropy (1;).
Pentropy (v:) = (v:) + (1)) vn E T
We can input the attributes of candidate nodes and the corresponding graph structures into SAT, and then obtain their loss values. The larger Centropy (v;) is, the more uncertainty of node U; has. From the perspective of information theory, nodes with greater uncertainty contain more information. Sampling these nodes can help the model get the information that has not been learned in previous training, thus enhancing the training efficiency.
5

---

Under review as a conference paper at ICLR 2023
4.2 SCORE FUNCTION AND BETA DISTRIBUTION CONTROLLED WEIGHTING SCHEME
We have presented three metrics of our query strategy. Then, question arises: How to combine these metrics to score each node? Combing the metrics with a weighted sum is a possible solution but still faces great difficulties. First, the values of different metrics incomparable because of the distinct dimensional units. Second, the different metrics may take different effects at different learn- ing stages. To solve these issues, we introduce percentile evaluation and design Beta-distribution controlled re-weighting scheme to exert the functions of each metric, since Beta distribution is suitable model for the random behavior of percentages and proportions Gupta Nadarajah (2004)
Denote Pol (o(us TV) as the percentage of the candidate nodes T which have smaller values than the node i, with metric ø. For example, if there are 5 candidate nodes and the scores of one metric is [1, 2, 3, 4. 5], the percentile of the corresponding 5 nodes will be [0, 0.2, 0.4, 0.6, 0.8). We apply the percentile to three metrics and define the final score function ATS as:
S(v:) = a Pentropy (vi, 12) + 3.Peetttt (vi, T + y P Poentrality (vi, T
where a + 3 + 1. At the sampling stage, ATS will select one or several nodes with the largest and add them to the training set T for the next training epoch of SAT.
ALGORITHM 1: ATS algorithm
Input: SAT parameters, G, T. T iniiialization of Th and hyper-parameters:
while n. < total_epoch do
// Training stage
loss 4- SAT(T");
// Update SAT
loss. bossbbackward))
updale(SAAT parramss))) // Sampling stage
if #T > then
// SAT returns the Loss values and latent representations
Za; Pentropy <- SAT(TTTTT))) Qdensity + getDensity(sa)) Qcentrality < gefCentralltt(())
7 + Beta(1,n.);
1-;; a Pentropy 3- + Peentrality
11 select the node with the highest score
T +- ucliveSample(S.7"))
1/ zenew the training set of SAT Th +- UTS:
/ renew the candidate set T +- TU T8;
end
end
Further, it is worth noting that the uncertainty and the information density are determined by the training result returned from SAT. an early training stage, the model is unstable and the returned training result may not be quite reliable. A sampling process based on inaccurate model-returned results may lead to undesirable results. Hence, we set the weights to time-sensitive ones. The structure-related weight is more credible so it can be larger initially. As the training epoch in- creases, the model can pay more attention to Dentropy and @densitys while the weight 7 will decrease gradually. We formalize this by sampling 7 from Beta distribution, of which the expectation be- comes smaller with the increase of training epoch. The weighting values are defined as:
The and
1 1-7
Beta(1,
74
(8)
where is one of the determinants in Beta distribution; is used to control the expectation of o; ne denotes the current number of epochs. We obtain the expectation by calculating the average value of 10,000 random samples.

---

Under review as a conference paper at ICLR 2023
4.3 ITERATIVE TRAINING AND IMPLEMENTATION
In general, our method consists of two stages: one is SAT. responsible for the training stage; the other is ATS, responsible for the sampling stage. Before the training, we divide total training set T into T and TL. We randomly sample 1% of the nodes in 7 as the initial nodes of T and the rest composes TV_ SAT will be trained on the changeable TV. Once SAT accomplishes a single training epoch, ATS starts the sampling process. We sample the most representative and informative candidate nodes from T according to the query strategy. These selected nodes are added to T and removed from T Then SAT will be trained on the renewed 7 at next epoch. The training stage and the sampling stage alter iteratively until T is null. Finally ATS is terminated and SAT will continue training to convergence. We clarify the learning process in Algorithm [
EXPERIMENTS AND ANALYSIS
5.1 DATASETS
We utilize public benchmarks whose node attributes are categorical vectors. The information of used datasets is as follows: 1) Cora. Cora McCallum et al. (2000) is citation graph with 2,708 papers as nodes and 10,556 citation links as edges. Each node has a multi-hot attribute vector with 1,433 dimensions. The attribute vectors consist of different word tokens to determine whether they appear or not. 2) Citeseer. Citeseer Sen et al. (2008) is another citation graph which is larger than Cora. It contains 3,327 nodes and 9, 9,228 edges. Like Cora, each node has multi-hot attribute vector with 3,703 dimensions. 3) Amazon-Computer and 4) Amazon-Phota
These two datasets are generated from Amazon co-purchase graph. The node represents the item and the edge represents the two items are usually purchased at the same time. The node attribute is multi-hot vector with the set of words involved in the item description. Amazon-Computer Compuuerrruuurrhhhuhr Shchur al. (2018) has 13,752 items and 245,861 edges. Amazon-Photo Shchur et al. (2018) has 7,650 nodes and 119,081 edges.
5.2 EXPERIMENTAL SETUP
Baselines: We compare SAT model combined with ATS with other baselines introduced in Chen ct al. (2022): NeighAggre Şimşek & Jensen| (2008), VAE Kingma Welling (2013), GCN Kipl & Welling (2017) GraphSage Hamilton al. (2017), GAT Veličković et al. (2018). Hers Hu et al.
(2019), GraphRNA Huang et al. (2019). ARWMF Lei Chen & Bronstein (2019) and original SAT.
Details about how they work on node attribute completion are illustrated in Appendix A.1
Evaluation metrics: In node attribute completion, the restored attributes can provide side infor- mation for nodes and benefit downstream tasks. By following SAT [Cen al. (2022), the effect of ATS on two downstream tasks including node classification task in the node level and profiling task in the attribute level. In node classification, the restored attributes serve as one kind of data augmentation and supply more information to the down-stream classification task. In profiling, we aim to predict the possible profile (e.g. key terms of papers Cora) in each attribute dimension.
study
Parameters setting: In the experiment, we randomly sample 40% nodes with attributes as training data, 10% nodes as validation data and the rest as test data. The attributes of validation and test nodes are unobserved in training. For the baselines, the parameters setting and the experiment results refer to Chen et al. (2022). For our ATS method, the SAT's setting remains the same, such as Aç- We mainly have two hyper-parameters: in the weighting scheme and cluster numbers in the estimation of density Qxtensity. Considering the objective of the Beta distribution weighting scheme, e should be larger than the total sampling times. Hence in Cora and Citeseer, comes to Amazon Leauzon_PPooo and SemazonnCCmmuttee we set e = 2000. In addition, we set the cluster number 10, 15, 10, 155 for Cora, Citeseer, Amazon Photo and Amazon Computer.
set 1500 and when it
5.3
OVERALL COMPARISON
5.3.1 NODE CLASSIFICATION
Classification is an effective downstream task to test the quality of the recovered attributes. In node classification task, the nodes with restored attributes are split into 80% training data and 20%
7

---

Under review as a conference paper at ICLR 2023
test data. Then conduct five-fold cross-validation in 10 times and take the average results of evaluation metrics as the model performance. We use two supervised classifiers: MLP and GCN. The MLP classifier is composed by two fully-connected layers, which classifies the nodes based on attributes. The GCN classifier an end-to-end graph representation learning model, which can learn the structure and attributes simultaneously. Results shown in Table
According to the results of "X" row where only node attributes are used, the optimized SAT model with proposed ATS algorithm achieves obvious improvement than original SAT model. Our ATS can also adapt to SAT with different GNN backbones (e.g. GCN and GAT) and achieve higher classification accuracy than the original models. For the results of "A+X" row where both structures and node attributes are used by GCN classifier, our method achieves the highest score in Cite- seer and Amazon-Computer with 0. 0.84% and 0.56% respectively, because ATS contains the density metric and can help the model better learn the inner semantic structures.
Table 1: Node classification of the node-level evaluation for node attribute completion. "X" indicates the MLP classifier that only considers the node attributes. " "A+X" indicates the GCN classifier that considers both the structures and node attributes.
Method
Cora
Citeseer
Comzun-Computer Amazon-Phott
NeighAggre
0.6248
0.5539
0.8365
0.8846
VAF
0.2826
0.2551
0.3747
0.2598
X
GCN
0.3945
0.3768
0.3660
0.2683
GraphSage
0.4852
0.3933
0.3747
0.2598
GAT
0.4143
0.2129
0.3747
0.2598
Hers
0.3046
0.2585
0.3747
0.2598
GraphRNA
0.7581
0.6320
0.6968
0.8407
ARWMF
0.7769
0.2267
0.5608
0.4675
SAT(GON)
0.7644
0.6010
0.7410
0,8762
SAT(GAT)
0.7937
0.8201
0.8976
ATSS +S GCTG
0.7850
0.6370
0.8198
0.8827
A
0.8065
0.6662
0.8402
0,9028
NeighAggre
0.6494
0.5413
0.8715
0.901
VAE
0.3011
0.2663
0.4023
0.3781
A+X
GCN 0,4387
0.4079
0.3974
0.3656
GraphSage
0.5779
0.4278
0,4019
0.3784
GAT
0.4525
0.2688
0,4034
0.3789
Hers
0. 3404
0.3229
0.4025
0.3794
GraphRNA
0.8198
0.6394
0.8650
0.9207
ARWMF
0.8025
0.2764
0.7400
0.6146
SAT(GCN)
0.8327
0.6599
0.8519
0.9163
SAT(GAT)
0.8579
0,6767
0,8766
0.9260
A
0.8366
0.6750
0.8752
0.9181
ATS ATS+
0.8573
0.6851
0.8822
0.9251
5.3.2 PROFILING
The model outputs the restored attributes in different dimensions with probabilities. Higher corre- sponding probabilities ground -ooth attributes signify better performance. In this section, we use two common metrics Recall @k and NDCG@k to evaluate the profiling performance. The experi- ment results are shown in Table
According to the profiling results in Table 2 on the basis of the advantages established by the SAT model towards other baselines, the combination of the ATS algorithm and SAT model (ATS+SAT) obtains even higher performance in almost all the evaluation metrics and almost all the datasets. For example, ATS+SAT(GAT) obtains a relative 13.5% gain of Recall 10 and a relative 13.3% gain of NDCG@ 10 on Citeseer compared with SAT(GAT). The main reason of these results is that the active sampling algorithm ATS helps SAT model to realize different importance of different nodes in learning, and thus facilitates better distribution modeling of the high-dimensional node attributes.
5.4 STUDY THE WEIGHTING SCHEME
Besides the active sampling metrics, the Beta distribution controlled weighting scheme is also a highlight of the ATS algorithm. We will verify the effectiveness of our proposed scheme in com- parison with other weighting schemes, such as the fixed weighting scheme and the linear variation weighting scheme. For the fixed one, the values of y are 0.2, J. 0.6, and a = 3 - For the linear variation one, 7 decreases linearly from to 0.5 from to 0.
8

---

Under review as a conference paper at ICLR 2023
Table 2: Profiling of the attribute-level evaluation for node attribute completion.
Method
|Recallé
Recall@: @ccall
NDCG@10
NDCG@20
NDCG@50
NeighAugre
0.0906
0.1413
0.1961
0.1217
0.1548
0,1850
Cora
GON
VAF
0.1271
0,0887
0.177
0.1228
0.216
0 2.692
0.1236
0. 11224
0.2076
1452
012702
0.1924
GriphSage
0.1284
0.1784
0.2972
0.1768
0.2102
0.2728
GAT
0.1350
0.1812
0 2072
0.1791
0.2099
0
0.100
GrapERNA
0.1395
0,3142
0.2038
ARWME
0.1291
0.296
0,7700
SAT(OCN)
0.1508
0,2182
0. 0.3422
0.2112
0,2546
0.3212
SAT(GAT)
0.1653
0.2345
0.3612
0,2250
0.2723
D.3394
ATSASATIGON)
0.1560
0,2259
0. 3527
0.2161
0.2628
O. 0.3298
ATSASATIGATI
0.1640
0.2355
0.3616
0.2258
0.2733
0.3405
NggehAgre
DXB51
DAPAUS
0.1501
0.1155
Citesoer
GON
YAE
0.0582
0.0020
0 11907
0 0,0688
0. 1296
0 2252
0.0001
0.1020
0. 1423
0.030
0 2049
12
GraphSage
0.0012
0.1097
0
0003
0.1301
GAT
0.056]
0 1012
0
0 227
1979
0.0004
1000
GraphRNA
0.0777
0.1272
0.2271
0.1291
0.1703
0.2358
MR
0,0552
0.1015
0.1952
0.0859
1.1245
0.1858
SATTOCN)
0.0764
0.1280
0.2577
0.1298
0.1729
0.2447
SAT(GAT)
0.0811
0.1349
0.2431
0,1385
0.1834
0.2545
ATS+SATIGCN)
0.0854
0.1400
0,2580
U.144]
0.1896
0.2672
AISHSAI
0.0921
0.1487
0.2635
0.1570
0.2037
0.2791
NorhhAggre
01032]
035993
0.1300
01788
0
0.1925
Amazon-Computerr
VAB
0.0255
0,052
0.1 199
0.0332
0.0970
0.122
GCN
0,0273
D.013
0 0.1275
0.677
1027
1824
GraphSage
0530
0
Hers
0.0275
0 05335
0.1275
0.0676
0. 1025
0.1815
GraphRNA
0.0386
0 00690
0.1465
00831
0.1333
0.2155
ARWME
0.0280
0.0544
0.1 0.1289
0,0694
0. 1051
0.1851
SATIGCN)
0.0391
0.0703
0.1514
0.0963
0.1379
0,2243
SAT(GAT)
0.0421
0.0746
0.1577
0.1030
0.1463
0.2346
ATS+SATIGCN]
0.0421
0.0746
0.1575
0,1032
0.1464
0,2347
ATS4SATYGAT
0.0440
0.0775
0.1617
0,1074
0.1519
0.2412
NeighAugre
0X0329
D/616
0.1661
0181
0.1996
0,1988
Amazon- Photo
VAB
0.0276
0.058
0. 1279
0.675
1051
0830
GraphSagge
0.0295
0.0562
0.1322
0
0.1079
8,1896
GAT
0.0294
0.0573
113
0.0705
1083
0.1892
Hers
0.0292
0.0574
0.1328
0.0714
1094
0.1 1900
GraphRNA
0.0390
0.0703
0.150 111508
0.0959
0.1377
0.2232
ARWME
0.0294
0.0568
0.1327
0.0727
0.1098
0.1915
SATYGCN)
0.0410
0
0.1597
0.100K
0,1450
SAT(GAT)
0.0427
0.1047
0.1498
STIGGA
ATS+SATTGAT
0.0438
0.1067
2313
Receng28
+315
4200
Frear905
Frean665
8308
26
20
20
Epech
Spech
(a) Cora
(b) Citeseer
(c) LrAAmmam_phott
Figure 2: Visualization of profiling performance of different weighting schemes on test data during training process. We compare our Beta distribution controlled weighting scheme with other weight- ing schemes(e.g. fixed weight, linear variation).
From Figure we see our proposed weighting scheme outperforms other schemes because Beta distribution changes the weights dynamically during the sampling process and meanwhile remains some randomness to improve the robustness the algorithm.
CONCLUSION
In this paper, we propose a novel active sampling algorithm ATS better solve the node attribute completion problem. In order to distinguish the differences in the amount of information among nodes, ATS utilizes the proposed uncertainty and representativennss metrics to select the most in- formative nodes and renew the training set after each training epoch. Further, the Beta distribution controlled weighting scheme is proposed to adjust the metric weights dynamically according to the training status. The sampling process increases the running time of each epoch within an afford- able cost, but meanwhile helps the base model achieve superior performance on profiling and node classification tasks. Therefore, ATS is effective in boosting the quality of restored attributes.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pp. 872-881 PMLR, 2019.
Hongyun Cai, Vincent W Zheng. and Kevin Chen-Chuan Chang. Active learning for graph embed- ding. arXiv preprint arXiv: 1705 05085, 2017.
Razvan Caramalau, Binod Bhattarai, and Tae-Ke Tac-Kyun Kim. Sequential graph convolutional network for active learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 3583-9592, 2021.
Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W. Tsang. Learning on attribute- missing graphs. IEEE Trans. Pattern Anal. Mach. Intell., 44(2)740-7757, feb 2022. ISSN 0162 8828. doi: 10. 10.110//PAMM.2000000022
TPAMI 203211111118
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks. arXiv preprint arXiv: / 700.00845 2017.
Zhixian Chen, Tengfei Ma, Yangqiu Song, and Yang Wang. Wasserstein diffusion on graphs with missing attributes. arXiv preprint 1rXiv:2102.03450, 2021.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE Transac- fions Knowledge and Data Engineering, 31(5):833-852, 2018
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. Advances in Neural Information Processing Systems, 33: 11996-12007, 2020.
Akshay Gadde, Aamir Anis, and Antonio Ortega. Active semi-supervised learning using sampling theory for graph signals. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 492-501, 2014.
Li Gao, Hong Yang, Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network representation learning. IJCAI International Joint Conference on Artificial Intelligence, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Quanquan Gu, Charu Aggarwal, Jialu Liu, and Jiawei Han. Selective sampling graphs for clas- sification. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 131-139, 2013.
Arjun K Gupta and Saralees Nadarajah. Handbook of beta distribution and its applications. CRC press, 2004.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Liang Hu, Songlei Jian, Longbing Cao, Zhiping Gu, Qingkui Chen, and Artak Amirbekyan. Hers: Modeling influential contexts with heterogeneous relations for sparse and cold-start recommenda- tion. In Proceedings the AAAI Conference Artificial Intelligence, volume 33, pp. 3830-3837, 2019.
Xiao Huang, Qingquan Song, Yuening Li, and Xia Hu. Graph recurrent networks with attributed random walks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 732-740, 2019.
10

---

Under review as a conference paper at ICLR 2023
Ming Ji and Jiawei Han. A variance minimization criterion to active learning on graphs. In Artificial Intelligence and Statistics, pp. 556-564. PMLR, 2012.
Bo Jiang and Ziyan Zhang. Incomplete graph representation and learning via partial graph neural networks. arXiv preprini urXiv:2003. 10130, 2020.
Di Jin, Cuiying Huo, Chundong Liang, and Liang Yang. Heterogeneous graph neural network via attribute completion. In Proceedings of the Web Conference 2021, pp. 391-400, 2021.
Diederik P Kingma and Max Welling. 1rXiv:1312.6114 14, 2013.
Auto-encoding variational bayes.
arXiv preprint
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Joan Bruna Lei Chen, Shunwang Gong and Michael M. Bronstein, Attributed random walk as matrix factorization. Graph Representation Learning Workshop NeurIPS, 2019.
Xiaoxiao Li, Yuan Zhou, Nicha Dvomek, Muhan Zhang, Siyuan Gao, Juntang Zhuang, Dustin Scheinost, Lawrence H Staib, Pamela Ventola, and James S Duncan. Braingnn: Interpretable brain graph neural network for fmrr analysis. Medical Image Analysis, 74:102233, 2021.
Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, lan Goodfellow, and Brendan Frey, Adversarial autoencoders. arXiv preprint arXiv: urXiv:1511.0560 1.06644, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 32):127-1633 2000.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Liming Pan, Cheng Shi, and Ivan Dokmanić. Neural link prediction with walk pooling. In Interna- tional Conference on Learning Representations, 2022.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po- Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang, A survey of deep active learning. ACM Computing Surveys (CSUR), 54(9):1-40, 2021.
Benjamin Sanchez-Lengelingg Emily Reif, Adam Pearce, and Alexander B. Wiltschko. A gentle introduction to graph neural networks. Distill, 2021. doi:
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3)933-93, 2008
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 100. 7088.00489 2017.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint
2018.
Özgür Şimşek and David Jensen. Navigating networks by using homophily and degree. Proceedings of the National Academy of Sciences, 105(35): 2008.
Jianyong Sun, Wei Zheng, Qingfu Zhang, and Zongben Xu. Graph neural network encoding for community detection in attribute networks. IEEE Transactions on Cybernetics, 2021.

---

Under review as a conference paper at ICLR 2023
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang. Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067-1077. International World Wide Web Conferences Steering Commit- tee, 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018. id= rd=r accepted as poster.
URL https: httpps///ppeneeiew..oo http:/wwwwwwwe.eeeee.eeeeeeee T
Athanasios Voulodimos, Nikolaos Doulamis, Anastasios Doulamis, Eftychios Protopapadakis, and Diego Andina. Deep learning for computer vision: brief review. Intell. Neuroscience, 2018, jan 2018. ISSN 1687-5265.
doi: (0.1155/201870668449 URL https:: httpps://ee..org1....1
2018/7068344
Yixin Wang, Alp Kucukelbir, and David M Blei. Robust probabilistic modeling with bayesian data reweighting. In International Conference on Machine Learning, pp. 3646-3655, PMLR, 2017.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Yameng Gu, Xiao Liu, Jingchao Ni, Bo Zong, Haifeng Chen, and Xiang Zhang. Adaptive neural network for node classification in dynamic networks. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 1402-1407. IEEE, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019b. URL https: //openreview. www.ffootooooooo www.ooodddrnaoo..........
Qiang Yang. Zhi-Hua Zhou, Zhiguo Gong, Min-Ling Zhang, and Sheng-Jun Huang. Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, volume 11441. Springer, 2019.
Donggeun Yoo and In So Kweon. Learning loss for active learning. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 93-102, 2019.
Chuxu Zhang. Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 793-803, 2019.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Wentao Zhang, Yexin Wang, Zhenbang You, Meng Cao, Ping Huang, Jiulong Shan, Zhi Yang, and Bin Cui. Information gain propagation: new way to graph active learning with soft labels. arXiv preprint arXiv:2203.01093 2022a.
Z. Zhang, P. Cui, and W. Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge amp; Data Engineering, 34(01):249-270, jan 2022b. ISSN 1558-2191. doi: 10.1109/TKDE. 2020.298 1333.
12

---

Under review as a conference paper at ICLR 2023
0,330
9,1500
9.060
5.2275
0,3475
3.073
9.220
1.201
0.3450
9,225
9.1425
Necalla20
2,076
92200
9.450
1IM
9:3375
Query Stritegy
Query Strategy
Query Strategy
(a) Cora
(b) Citeseer
(c) Ahazon_photo
Figure 3: Ablation study of different metrics ATS. We show the recall 20 result of different combinations of the sampling metrics on 3 benchmarks. The horizontal coordinate refers to the different sampling criteria combinations. 'E' indicates the entropy metric; 'D' indicates the density metric; 'C' indicates the centrality metric; 'E+D+C' indicates ATS algorithm.
A APPENDIX
A.1 DETAILS ABOUT THE BASELINES
NeighAggre is an intuitive attribute aggregation algorithm. It completes one node's missing at- tributes by averaging its neighbour nodes' attributes, which is a simple but efficient method to take advantage of the structural information. VAE is a famous generative model, which consists of an encoder and a decoder. For test nodes without the attributes, the encoder will generate the corre- sponding latent code through the neighbour aggregation. Then the decoder will restore the missing attributes. GCN, GraphSage and GAT are three typical graph representation learning methods. For attribute-missing scenario, only the graph structure will be encoded to latent codes. The missing attributes will be recovered by the decoders of these GNN methods from the latent code generated by the encoders. Hers is cold-start recommendation method. GraphRNA and ARWMF two attributed random walk based methods to learn the node representations, which can be extended to deal with the missing attributes problems. They separate the graph structure and node attributes and learn the node embeddings by random walks.
A.2 ABLATION STUDY OF DIFFERENT METRICS IN ATS
In this section, we conduct the ablation study to investigate the effects of three different metrics in ATS. The experimental settings remain the same as the profiling task. We use Recall @ 20 to evaluate the performance of different metric combinations. The results are shown in Figure S
Cora, centrality-only sampling method hurts the profiling performance. Different metrics focus different aspects and the result shows that they can complement each other. The uncertainty metric focuses on the training status the model, while the representativeness metric focuses on the implied information from both the structure and attribute aspects. Generally, any subgroup of the sampling criteria is inferior to the results achieved by the complete ATS.
A.3 EMPIRICAL TIME COMPLEXITY ANALYSIS
Our ATS is an active sampling procedure based on the SAT model, so it's critical to study the extra processing time cost by the ATS. Thus we conduct an experiment count the running time of different parts of the ATS compared with the original SAT. These different parts are forward process, uncertainty and representativeness. The forward process means the forward propagation, which essential to caleulate the uncertainty score. We implement the experiment on machine with one Nvidia 1080Ti GPU.
According to the running time shown in Figure the forward propagation in ATS is much faster than SAT due to the time-consuming back propagation in SAT. Although the processing time of uncertainty metric and representativeness metric is relatively higher than SAT because of the clus- tering and percentile calculations, it's comparable with the time of SAT. With the addition of the ATS algorithm, the time required for each epoch will increase within acceptable range.
13

---

Under review as a conference paper at ICLR 2023
Meder compenent
Rood onng compenerty
Plocel comperennt
(a) Cora
(h) Citeseer
(c) Amazon_Photo
(d) Amazon_Computer
Figure 4: The comparison among the average processing GPU time per epoch of different model components. 'Forward' indicates the forward propagation that is a part of the calculation in uncer- tainty metric.
A.4 SENSITIVITY OF THE HYPERPARAMETERS
As mentioned Section 5.2, cluster number a vital tion density of each node. We conduct the experiments on both the profiling and classification tasks with different cluster numbers.
that determines the informa-
0.229
C300
come
cmw
cKm
(a) Recall on Cora
(b) Recall Citeseer
(c) Recall on Amazon Photo
cas
4.79
100%%
cace
Claster number
Cluster numbers
Cluster numbers
(d) X Cora
(e) X Citeseer
(f) X Amazon_Phor
C106
<00
com
Clacter numbers
Clarter numbere
Clurter numbers
A+X -Cora
(h) A+X Citeseer
(i) A+X Amazon_
Figure 5: Results with different cluster numbers when calculating the density score in the represen- tativeness metric. (a-c) show the Recall @ 20 results for profiling task. (d-f) show the attribute-onje classification accuracy with the of MLP classifier. (g-h) show the classification accuracy sidering both the structure and attribute information.
The results of Figure 5 show that too large too small cluster numbers not conducive to the training. there are not enough cluster centers, the sampling algorithm not robust to extract the density of the embedding distribution. On the other hand, if there many cluster centers, it will
14

---

Under review as a conference paper at ICLR 2023
introduce more disturbance and might separate the nodes belonging to the same class. We determine the value of parammeer based on the Recall 20 results in the profiling task.
15


Reviews:
[{"review_id": "sfZmDT_D9mj", "reviewer": "Reviewer_Yxf6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "While the completion of missing node attributes is an important problem, the Structure-Attribute Transformer (SAT) is recent work that tackles that problem with leveraging all the observed attributes equally. The authors challenge the part of using all the observed attributes in an equal manner, and propose the SAT learning strategy based on active node sampling. For the active sampling, authors propose the the representativeness and the uncertain measurements for nodes on a graph and use them for active sampling. When the proposed sampling strategy is combined with SAT, it shows better performance in node classification tasks compared to the other baseline models, including the original SAT.", "summary_of_the_review": "Despite the clearness and fair performance of the proposed method, the proposed method needs to be 1) more generalized, 2) evaluated on the matters of interests, and 3) more studied to the role of each strategy part to understand the impact of proposed methods better.", "strength_and_weaknesses": "* Strengths\n- The proposed node measurements are clear and reasonable to represent the importance for active sampling.\n- The manuscript is easy to follow.\n- The proposed method combined with SAT shows the better performance compared to baseline models\n\n* Weakness\n- The objective of the active sampling-based strategy would be great if it is clearly defined. The efficiency is described as the objective, but it needs to be further clarified and better-defined.\n- Despite aiming the efficiency, the experiments or evaluations with respect to efficiency or training time are missing.\n- The proposed active sampling is very tightened with SAT. It is not clear why the sampling should be coupled with SAT, not some general embedding-based learning. More generalization of the proposed method or clear explanation specific to SAT would be great to have. \n- Experiments could be more enforced. The ablation study with respect to learning speed would be great to have. For example, when the same learning strategy is applied (starting from 1% training and expanding the training size over epochs), how soon does the proposed method achieve a reasonable performance as opposed to the uniform sampling? Or, how different is the learning algorithm's convergence speed when gradually expanding the training node set as opposed to directly training on the entire dataset?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nHLqL1sLC8j", "reviewer": "Reviewer_P86Z", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed an active sampling method to improve an existing approach called SAT for graph node attribute completion. It claims that the observed nodes are not equally important, and they designed several metrics to measure the nodes’ representativeness and uncertainty and use them for active sampling. To better control the weighting scheme, it further proposed to use Beta distribution to adjust the metric weights. Experiments show that the proposed method achieve superior performance on node classification and profiling tasks. ", "summary_of_the_review": "The solved problem is not significant, and the approach and evaluation have something unreasonable. ", "strength_and_weaknesses": "There are some interesting points in the paper, e.g. the importance metric of the nodes. However, its overall quality is not good enough for ICLR. \n1.\tMotivation. First of all, the scope of the paper is too small. Node attribute completion is not a standard task, and SAT is not a well-known base model. Only designing a specific sampling method to improve the SAT model looks very trivial.   \n2.\tI do not see the necessity of active sampling. As described in the related works, active sampling is originally used for sampling new data to label, but this paper mainly used it to adjust the training sample weights. I do not understand why they should start from a small portion of observations. They can just train a SAT using the full data, and then resample all the data to adjust the weights. \n3.\tDatasets. All datasets are manually made but not from a real problem (the four datasets all have full attributes). That makes the “node attribute completion” task look like a toy problem. But we know that in real world there should be such tasks. If possible real data and tasks will be much better.\n4.\t Evaluation. Using the node classification task for evaluation is not reasonable. Take a very simple example, for each label we just generate a one-hot vector and use it as the missing node feature, the node classification accuracy will be 100%, but that does not mean the feature completion is good.\n5.\tAblation study. The node metric has three components. I think an ablation study which removes one or two components will be necessary to show the importance of each metric component.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "csYKfA7k-pr", "reviewer": "Reviewer_TF65", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a technique to prioritize which samples to select next in an active learning setting for node attribute completion in graphs. The proposed method uses metrics related to the \"density\" of a data point as well as its centrality in the graph. The proposed approach is used as input to SAT, a previously-proposed model for node attribute learning.", "summary_of_the_review": "I think that the proposed approach is rather incremental in the literature of learning node attributes in graphs. My main criticism of the paper is that the authors rely on an existing model for the bulk of the machine learning task, and their contribution can be summarized as a heuristic method to suggest new data points in an active learning framework. \n\nSince the work is empirical in nature, I also think that the authors could provide more evaluation on why their particular metric is of value over potential alternatives. While I agree with the authors that density and centrality are important criteria for this task, there are numerous metrics that one could come up with. For instance, instead of PageRank, we could consider node centrality or betweeness centrality.\nThe authors instead spend decide to report a comparison of competitors for SAT. In my opinion, this takes away from their contribution, since it makes SAT the focus of the paper. I would reframe the experiments to show how the proposed metric is superior to other density/centrality alternatives, all in the context of SAT (and potentially GAT).\n\nLastly, as I mentioned above, the empirical results are not surprising, since the authors are choosing points in an intelligent way. It is obvious that one should expect an improvement from this, and I don't see how the proposed work or results add much to the existing literature.\n\nI would recommend this work to be published as a short paper, but I cannot recommend it to be featured as a full research paper.", "strength_and_weaknesses": "Strengths:\n- The criteria designed by the authors to select the next point to train on is well-motivated\n- The authors leverage on a state of the art model for node attribute detection\n\nWeaknesses:\n- Lack of novelty. The main contribution is a method to prioritize training points in an active learning setting. However, the model that actually learns node attributes (which is arguably the crux of the problem) has been proposed before.\n- Incremental empirical results. It is not surprising that the proposed approach marginally improves performance over SAT and GAT. Any sensible heuristic to select data points would be better than not doing anything.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y6IAQ5hrmW1", "reviewer": "Reviewer_RsqE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of imputing the missing attributes of nodes in a network.This is done by identifying the most informative nodes for renewing the training set after each training epoch. Some uncertainty and representativeness metrics are proposed to achieve the task of identification. Their method achieves improved performance on node classification and profiling tasks with 4 real datasets.\n\n", "summary_of_the_review": "The paper tackles an interesting problem and leads to improved performance, however, the assumptions and choices made for the implementation (e.g. why these are optimal/intuitive in any way) of the proposed method are not clear. Also links with existing literature on networks seems to have been ignored. ", "strength_and_weaknesses": "Strengths: the paper tackles an important problem known to be of interest in practice (e.g. attributes of individuals are often missing due to confidentiality or privacy settings); improved performance compared to some state of the art techniques. \n\nWeaknesses: Specifically, what is the ` node attribute completion problem' - this is clear at a high level but the complexities concerning the exact problem are never discussed (type of missing attributes, proportion of missing attributes and how it links with properties of the network). The intuition and reasoning behind some of the key choices and assumptions is not explained and remains unclear. For example, why is a shared latent space assumption required for the node attribute completion problem (second para in Section 4.1)? What do you mean by 'information density'? Is this somehow linked to network edge density? Is `structural centrality' linked to network centrality measures commonly studied in this area?\nThere are many vague statements here, for example (second para in Section 4.1, line 3): `If there is a dense distribution of representation vectors in a local region of the latent space, the corresponding nodes will have more similar features ..'\nWhat does this mean exactly and why? Some mathematical notation here could have helped in stating things more precisely. \nUnder equation (4): 'The larger \\phi_density is, the more representative the node is ....' : How does this follow from the formula above and what exactly is the node representative of and why? \nWhy is the PageRank score specifically used as structural centrality?\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject