Confidence-Based Feature Imputation for Graphs with Partially Known Features
Authors: Daeho Um
Jiwoong Park
Seulki Park
Jin young Choi
Venue: ICLR 2023 poster (2023)
Keywords: Graph neural networks
Graphs
Missing features

Abstract: This paper investigates a missing feature imputation problem for graph learning tasks. Several methods have previously addressed learning tasks on graphs with missing features. However, in cases of high rates of missing features, they were unable to avoid significant performance degradation. To overcome this limitation, we introduce a novel concept of channel-wise confidence in a node feature, which is assigned to each imputed channel feature of a node for reflecting the certainty of the imputation. We then design pseudo-confidence using the channel-wise shortest path distance between a missing-feature node and its nearest known-feature node to replace unavailable true confidence in an actual learning process. Based on the pseudo-confidence, we propose a novel feature imputation scheme that performs channel-wise inter-node diffusion and node-wise inter-channel propagation. The scheme can endure even at an exceedingly high missing rate (e.g., 99.5\%) and it achieves state-of-the-art accuracy for both semi-supervised node classification and link prediction on various datasets containing a high rate of missing features. Codes are available at https://github.com/daehoum1/pcfi.

Published as a conference paper at ICLR 2023
CONFIDENCE-BASED FEATURE IMPUTATION FOR GRAPHS WITH PARTIALLY KNOWN FEATURES
Daeho Um, Jiwoong Park, Seulki Park, Jin Young Choi Department of Electrical and Computer Engineering, ASRI Scoul National University (daehouml, ptywoong, seulki, Seulki.park, park, jychoi @snu.ac. kr
ABSTRACT
This paper investigates missing feature imputation problem for graph learning tasks. Several methods have previously addressed learning tasks on graphs with missing features. However, in cases of high rates of missing features, they were unable to avoid significant performance degradation. To overcome this limitation, we introduce novel concept of channel-wise confidence in node feature, which is assigned to each imputed channel feature of a node for reflecting certainty of the imputation. We then design pseudo-confidence using the channel-wise shortest path distance between a miising-featurr node and its nearest known-feature node to replace unavailable true confidence in an actual learning process. Based on the pseudo-confidence, we propose novel feature imputation scheme that performs channel-wise inter-node diffusion and mode-wise inter-channel propagation. The scheme can endure even at an exceedingly high missing rate (e.g., 99.5%) and it achieves state-of-theeart accuracy for both semi-supervised node classification and link prediction various datasets containing high rate of missing features. Codes are available at https: / thub. com/ daahouml /cffi.
INTRODUCTION
In recent years, graph neural networks (GNNs) have received considerable attention and have per- formed outstandingly on numerous problems across multiple fields (Zhou et al., 2020; Wu et al., 2020). While various GNNs handling attributed graphs are designed for node representation (Def- ferrard et al., 2016; Kipf & Welling, 2016a; Veličković et al., 2017; Xu et al., 2018) and graph representation learning (Kipf & Welling, 2016b; Sun et al., 2019; Velickovic et al., 2019), GNN models typically assume that features of all nodes are fully observed. In real-world situations, how- ever, features in graph-structured data are often partially observed, as illustrated the following cases. First, collecting complete data for large graph is prohibitively expensive ble. Second, measurement failure is common. Third, in social networks, most users desire to protect their personal information selectively. As data security regulation continues tighten around the world (GDPR), access to full data is expected to become increasingly difficult. Under these circum- stances, most GNNs cannot be applied directly due incomplete features.
impossi-
Several methods have been proposed to solve learning tasks with graphs containing missing fea- tures (Jiang & Zhang, 2020; Chen et al., 2020; Taguchi et al., 2021), but they suffer from signif- icant performance degradation at high rates missing features. A recent work by (Rossi et al., 2021) demonstrated improved performance by introducing feature propagation (FP), which itera- tively propagates known features among the nodes along edges. However, even FP cannot avoid a considerable accuracy drop an extremely high missing rate (e.g., 99.5%). We assume that it is because FP takes graph diffusion through undirected edges. Consequently. in FP, message passing between two nodes occurs with the same strength regardless of the direction. Moreover, FP only diffuses observed features channel-wisely, which means that it does not consider any relationship between channels.
Therefore, to better impute missing features in a graph, we propose to consider both chaerel and inter-node relationships so that can effectively exploit the sparsely known features. To this end, we design an elaborate feature imputation scheme that includes two processes. The first process is the feature recovery via channel- inter-node diffusion, and the second is the feature

---

Published as a conference paper at ICLR 2023
refinement via node-wise inter-channel propagation. The first process diffuses features by assigning different importance to each recovered channel feature, in contrast to usual diffusion. To this end, we introduce novel concept of channel-wise confidence, which reflects the quality of channel feature recovery. This confidence is also used in the second process for channel feature refinement based on highly confident feature by utilizing the inter-channel correlation.
The true confidence in a missing channel feature is inaccessible without every actual feature. Thus, we define ceeedd-con for use in our scheme instead of true confidence. Using channel-wise confidence further refines the less confident channel feature by aggregating the highly confident channel features in each node or through the highly confident channel features diffused from neigh- boring nodes.
The key contribution of our work is summarized as follows: (1) we propose a new concept of channel-wise confidence that represents the quality of recovered channel feature. (2) We design method to provide pseudo-confidence that can be used in place of unavailable true confidence in a missing channel feature. (3) Based on the pseudo-confidence, we propose a novel feature imputation scheme that achieves the state-of-the-ar performance for node classification and link prediction even in an extremely high rate (e.g.. 99.5%) of missing features.
RELATED WORK
2.1 LEARNING ON GRAPHI WITH MISSING NODE FEATURES
The problem with missing data has been widely investigated in the literature (Allison, 2001; Loh & Wainwright, 2011; Little & Rubin, 2019; You et al., 2020). Recently, focusing graph-structured data with pre-defined connectivity, there have been several attempts to learn graphs with missing node features. (Monti et al., 2017) proposed recurrent multi-graph convolutional neural networks (RMGCNN) and separable RMGCNN (sRMGCNN), a scalable version of RMGCNN. Structure- attribute transformer (SAT) (Chen et al., 2020) models the joint distribution of graph structures and node attributes through distribution techniques, then completes missing node attributes. GCN for missing features (GCNMF) (Taguchi al., 2021) adapts graph convolutional networks (GCN) (Kipf & Welling, 2016a) to graphs that contain missing node features via representing the missing features using the Gaussian mixture model. Meanwhile, a partial graph neural network (PaGNN) (Jiang & Zhang, 2020) leverages a partial message- -paoragggtppaaitioonn scheme that considers only known features during propagation. However, these methods experience large performance degradation when there exists a high feature missing rate. Feature propagation (FP) (Rossi et al., 2021) reconstructs missing features by diffusing known features. However, in diffusion of FP, a missing feature is formed by aggregating features from neighboring nodes regardless of whether feature is known or inferred. Moreover, FP does not consider any interdependency among feature channels. To utilize relation- ships among channels, we construct correlation matrix of recovered features and additionally refine the features.
2.2 DISTANCE ENCODING
Distance encoding (DE) on graphs defines extra features using distance from a node to the node set where the prediction is made. (Zhang & Chen, 2018) extracts local enclosing subgraph around each target node pair, and uses GNN to learn graph structure features for link prediction. (Li et al., 2020) exploits structure-related features called DE that encodes distance between a node and its neigh- boring node set with graph-distance measures (e.g., shortest path distance or generalized PageRank scores (Li al., 2019)). (Zhang et al., 2021) unifies the aforementioned techniques into a labeling trick. Heterogeneous graph neural network (HGNN) (Ji et al., 2021) proposes heterogeneous dis- tance encoding in consideration of multiple types of paths in enclosing subgraphs of heterogeneous graphs. Distance encoding in existing methods improves the representation power of GNNs. We use distance encoding to distinguish missing features based on the shortest path distance from a missing feature to known features in the same channel.
2.3
GRAPH DIFFUSION
Diffusion on graphs spreads the feature of each node to its neighboring nodes along the edges (Coif- man & Lafon, 2006; Shuman et al., 2013; Guille et al., 2013). There are two types of transition matrices commonly used for diffusion on graphs: symmetric transition matrix (Kipf & Welling,
2

---

Published as a conference paper at ICLR 2023
SPD-8
Pseudo-Contidee
channel
Channel-wise
Node-wise Inter-channel
Inter-node
90 9
Diffusion
Propegation
X
Figure I: Overall scheme of the proposed Seee--Coooddeeebbsseee Feature Imputation (PCFI) method. Based on the graph structure and partially known features, we calculate the channel-wise shortest path distance between node with missing feature and its nearest source node (SPD- S). Based on SPD-S, we determine the pseulo-confidence in the recovered feature, using pre- determined hyper-parameter a (0 a 1). Pseudo-confidence plays an important role in the two stages: channel-wise Inter-node diffusion and node-wise inter-channel propagation.
2016a; Klicpera et al., 2019; Rossi al., 2021) and random walk matrix (Page et al., 1999; Chung, 2007; Perozzi et al., 2014; Grover & Leskovec, 2016; Atwood Towsley, 2016; Klicpera et al., 2018; Lim al., 2021). While these matrices work well for each target task, from a node's per- spective, the sum of edge weights for aggregating features is not one in general. Therefore, since features not updated the same scale of original features, these matrices missing feature recovery.
suitable for
PROPOSED METHOD
3.1 OVERVIEW
We address a problem with graph learning tasks containing missing node features. To demon- strate the effectiveness of our feature imputation, we target two main graph learning tasks. The first target task, remi-supervisee node classification, is to infer the labels of the unlabeled nodes from the partially known features/labels and the fully known graph structure. The second target task, link prediction, is to predict whether two nodes are likely to share a link. Figure depicts the overall scheme of the proposed feature imputation. Our key idea is assign different pseudo-confidenee to each imputed channel features. To this end, the proposed imputation scheme includes two processes. feature recovery via channel-wise inder-node diffusion, and the second
The first process feature refinement via node-wise wise inter-channel propagation. The imputed features obtained from the two processes are used for downstream tasks via off-the-shelf GNNs.
In Sec, 3.2, we begin by introducing the notations used in this paper. In Sec. 3.3, we outline the pro- posed PC (pseudo-conte cotilo---coiidenne----eeeee feature imputation (PCFI) scheme that imputes missing node features. We then propose method to determine the pseudo-couee confidence in Sec. 3.4. Sec. 3.5, we present channel-wist inter-node diffusion that iteratively propagates known features with consider- ation of PC. In Sec. 3.6, we present node-wise inter-channel propagation that adjusts features based on correlation coefficients between channels.
3.2 NOTATIONS
Basic notation graphs. An undirected connected graph is represented G = (V, A) where == [u,) is the set of N nodes, E is the edge set with (v,, vy) E E, and A E (0, N NxN denotes an adjacency matrix. X = [x; a] E N is node feature matrix with nodes and channels, ie., Ti,d, the d-th channel feature value of the node v;, A(u,, denotes the set of neighbors of e;- Given an arbitrary matrix M E m we let M,, denote the i-th row vector of M. Similarly, we let M. denote the j-th column vector of M.

---

Published as a conference paper at ICLR 2023
Notation for graphs with missing node features. As assume that partial node features are known, we define bi(d) as set of nodes where the d-th channel feature values are known (I: in (( means 'known"). The set of nodes with the unknown d-th channel feature values denoted by Vi V k. Then v/(4) and y are referred to source nodes and missing nodes, respectively. By reordering the nodes according to whether feature value known not for the d-th channel, we can write graph signal for the d-th channel features and adjacency matrix as:
very few
A
A
Here, (d), _ and æ. are column vectors that represent corresponding graph signal. Since the graph is undirected, A A (4) is symmetric and thus (A)))) uk A due to reordering while they represent the same graph structure. features for X from ) and (F dd=1'
(d) Note that A is different from
X [&r,a] denotes recovered
3.3 BC-BASED FEATURE IMPUTATION
The proposed PC-based feature imputation (PCFI) scheme leverages the shortest path distance be- tween nodes to compute pseudo-confidence. PCFI consists of two stages: channel-wise inter-node diffusion and node-wise inter-channel propagation. The first stage, channel-wise inter-node dif- fusion, finds X (recovered features for X) through PC-based feature diffusion on a given graph G. Then, the second stage, node-wise inter-channel, refines X the final imputed features X by considering PC and correlation between channels.
To perform node classification and link prediction, a GNN is trained with imputed node features X. In this work, PCFI is designed to perform the downstream tasks well. However, since PCFI is independent of the type of learning task, PCFI is not limited to the two tasks. Therfore, it can be applied to various graph learning tasks with missing node features.
Formally, the proposed framework can be expressed
x = [i(( (2) IF Ja (A(4) F
(la)
X fx(X)
(1b)
Y = (x A),
(Ic)
where is channel-wise inter-node diffusion, is node-wise inter-channel propagation, and Y is a prediction for desired output of given task. Here, PCFI is expressed as f2 o fi and any GNN architecture can be adopted as gu according the type of task.
3.4 PSEUDO-CONFIIENC
We begin by defining the concept of confidence in the recovered feature a; of a node o; for channel d in the first process.
Definition 1. Confidence in the recovered channel feature ii.d is defined by similarity between éi,d and true one Fi,d, which is a value between 0 and
Note that the feature Fi,d of source node is observed and thus its confidence becomes 1. When the recovered ă;, is far from the true Ti.d, the confidence in ái,a will decrease towards O. However, it chicken and egg problem to determine ž. and confidence. That is, the confidence in &r,d unavailable before attaining ب, according to Definition 1, whereas the proposed scheme can not yield &, without the confidence.
To navigate this issue, instead of true confidence, we design pseudo-confidence using the shortest path distance between a node and its nearest source node for a specific channel (SPD-S). For in- stance. SPD-S of the i-th node for the d-th channel feature is denoted by Siá- which is calculated via
S ( ( (
4

---

Published as a conference paper at ICLR 2023
where s()) yields the shortest path distance between the i-th node and its nearest source node in V( on A (4), It is notable that, if the i-th node source node, its nearest source node itself, meaning Sid becomes zero. We construct SPD-S matrix S E N of which elements are Sid-
Consider X [aa,a] that represents the recovered features of X with consideration of feature homophily (McPherson et al., 2001) that represents a local property on a graph (Bisgin et al., 2010; Lauw et al., 2010; Bisgin et al., 2012). Due to feature homophily, the feature similarity between any two nodes tends to increase as the shortest path distance between the two nodes decreases.
Based feature homophily, we assume that the recovered feature fi of a node U; more confidently becomes similar to the given feature of its nearest source node as SPD-S of U; (St,a) decreases. According to the assumption, we define pseudo-confidence using SPD-S in Definition 2. Definition 2. Pseudd-confidence (PC) in Ri.d is defined by a function E,,d = Si. where a E (0, is hyper-paraneter
By Definition 2, PC becomes for йi,d Fi,d on source nodes. Moreover, PC decreases expo- nentially for a missing node features as St.d increases. Likewise, PC reflects the tendency toward confidence Definition I. We verified that this tendency exists regardless of imputation methods via experiments on real datasets (see Figure 7 in APPENDIX), Therefore, pseudo-confidence using SPD-S is properly designed to replace confidence. To the best of our knowledge, ours is the first model that leverages distance for graph imputation.
3.5 CHANNEL- WISE INTER-NODE DIFFUSION
To recover missing node features in channel-wise manner via graph diffusion, source nodes inde- pendently propagate their features to their neighbors for each channel. Instead of simple aggregat- ing all neighborhood features with the same weights, our scheme aggregates features with different importance according to their confidences. As result, the recovered features of missing nodes are aggregated in low-confidence and the given features of source nodes are aggregated in high- confidence, which is our design objective. To this end, we design a novel diffusion matrix based on the pseudo-confidence.
For the design, Definition 3 first defines 'Relative PC" that represents amount of PC in particular node fcature relative to another node feature.
Definition 3. Relative PC of ā. relative to ii, is defined by Es/i,d = Ej,a/ S..a-S...
Then, suppose that a missing node feature Iz.d i/ aggregates features from 2/ E (Ne)). If u; and Uj are neighborhoods to each other, the difference between SPD-S of e; and SPD-S of vj cannot exceed Hence, the relative PC node to its neighbor can be determined using Proposition Proposition 1. If Std m 2 1, o2 is a missing node, then fjr vy E (V:)) is given by
Esfi,d a if Si.a > Sj,d-
1 is Sa. = =Sja;
E = a is Si. < Sjad
Otherwise, vi is source node (Si.d = 0), then Esjiaa v, E (Nx)) is given by
Es/i,d = 1 if Uy is a source node Sjdd = 1),
Es/i,d = if Uy is a missing node(S, 0).
The proof of Proposition 1 is given in Appendix A.1.
Before defining a transition matrix, we temporarily reorder nodes according to whether feature value is known for the d-th channel, i.e., (d()) and A are reordered for each channel as Section 3.2 describes. After the feature diffusion stage, we order the nodes according to the original numbering.
Built on Proposition 1, we construct a weighted adjacency matrix (dd) for the d-th channel. (d) E NNN is defined as follows,
ifi (4)
W (d) fJ
0
if A. =0
(3)
ifi=j.
5

---

Published as a conference paper at ICLR 2023
Note that self- are added to W with weight of 1 so that each node can keep some of its own feature.
W is edge weight corresponding to message passing from By vt. Proposition implies that a-1 is assigned high-PC neighbors, I to same-PC, and a to low-PC neighbors. That is, W allows node to aggregate high PC more than low PC channel features from its neighbors. Further- more, consider message passing between two connected nodes v; and V/g s.t. W (.j Esjiad = a.
By Definition 3, Sa/j.d = S/ so that W j = (W(g))- = a- This means that message passing from a high confident node to a low confident node occurs in a large amount, while message passing in the opposite direction occurs in small amount. The hyyper-parameter tunes the strength of message passing depending on the confidence.
To ensure convergence of diffusion process, we normalize W(d) to W (4) (D - Wi() through row-stochastic normalization with (d) Ej Wa.j. Since ø with true feature values should be
preserved, we replace the first | rows of W with one-hot vectors indicating vi!4) Finally,
the channel-wise inter-node diffusion matrix (7(d) for the d-th channel is expressed as
(d)
W (d) uk
W
(4)
where I " is identity matrix and 0k (o).i [x|v!" |X)=1 is zero matrix. Note
that W remains row-stochastic despite the replacement. An aggregation a specific node can be regarded as weighted sum of features neighboring nodes. A row-stochastic matrix for transition matrix means that when a node aggregates features from its neighbors, the sum of the weights is 1. Therefore, unlike symmetric transition matrix (Kipf & Welling, 201 61; Klicpera et al., 2019; Rossi (random walk) transition matrix (Page et al., 1999; Chung, 2007;
et al., 2021) or a column-stochen Perozzi et al., 2014; Grover & Leskovec, 2016; Atwood & Towsley, 2016; Klicpera et al., 2018; Lim et al., 2021), features of missing nodes can form at the same scale of known features. Preserving the original scale allows features to recover close to the actual features.
Now, we define channel-wise inter-node diffusion for the d'th channel as
(d)
(0)
x
0.
(5)
* (1) W (c)) -)--
where (L) is recovered feature vector for (d) after i propagation steps, O,, is zero-column vector of size | and E [1, K]. Here we initialize missing feature values (dd) to zero. As K oc, this recursion converges (the proof is provided in Appendix A.2). We approximate the steady state to ((d) (K), which is calculated by ( (W(d) (d) (0) with large enough K. The diffusion performed for each channel and outputs (a(( (K)
Due to the reordering of nodes for each channel before the diffusion, node indices in (()((") for E {l,...,II F} differ. Therefore, after unifying different ordering each (K) according to the original order in X, we concatenate all (d) (K) along the channels into X, which is the final output in this stage.
3.6 NODE-WIST INTER-CHANNEL PROPAGATION
In the previous stage, we obtained X [ (recovered features for X) via channel-wise inter- node diffusion performed separately for each channel. The proposed feature diffusion enacted based on the graph structure and pseude-confidence, but it does not consider dependency between channels. Since the dependency between channels can be another important factor for imputing missing node features, we develop an additional scheme to refine X to improve the performance of downstream tasks by considering both channel correlation and sesudo-oonfidence. At this stage, within a node, a low-PC channel feature is refined by reflecting high-PC channel feature according to the degree of correlation between the two channels.

---

Published as a conference paper at ICLR 2023
We first prepare correlation coefficient matrix R [Ra
FxF,, giving the correlation
efficient between each pair of channels for the proposed scheme. Ra,b, the correlation coefficient between X., and X is calculated by
N- Di=1(a5, - ma) mb)
Reg
Oa
where my = # >im Li and 08
Li ( mma)²
In this stage, unlike looking across the nodes for each channel in the previous stage, we look across the channels for each node. As the right-hand graph Figure illustrates, define fully connected directed graphs (7()) called node-wise inter-channel propagation graphs from the given graph G. H() for the i-th node in G is defined by
H = (V(0))(), ((,B())
(7)
where D(1) 12 is a set of nodes in H()) g(() is a set of directed edges in H(0, and B E FxF is a weighted adjacency matrix for refining Xt.- To refine ãi,d of the i-th node via inter-channel propagation, assign ăi,d each o/ (d E (1....,F) F)). The weights in (() are given by ( in (8).
scalar node feature for the d-th channel
We design (6) for inter-channel propagation in each node achieve three goals: (1) highly corre- lated channels should exchange more information to each other than less correlated channels, (2) low-PC channel feature should receive more information from other channels for refinement than high-PC channel feature, and (3) high PC channel feature should propagate more information to other node channels than low PC channel feature. Based on these design goals, the weight of
directed edge from the b-th channel to the a-th channel (B(3) a.6 in B is designed by
(1) B
[B a Ra,b 0
if +
(8)
a.b
if = b
where Ra,,, S.b,, and (1 - S...)) are the terms fore meeting design goals (1), (2), and (3), re- spectively. is hyper-parameter for pseudo-confidence in Definition and B3 is the scaling hyper- parameter.
Node-wise inter-channel propagation on ( outputs the final imputed features for X We define node-wise inter-channel propagation
XT + B X - [m,, ,,,...,,, ",,.))
where X,; and X,: are row vectors. Preserving the pre-recovered channel feature values (as self loops), message passing among different channel features is conducted along the directed edges of ( After calculating X, for E [1,..., N}. we obtain the final recovered features by concate- nating them, i.c., X X X 2.:
XT. Moreover, since R is calculated via recovered features X for all nodes in G. channel correlation propagation injects global information into recov- ered features for X. In turn, X is a final output of PC-based feature imputation and is fed to GNN solve downstream task.
EXPERIMENTS
To validate our method, we conducted experiments for two main graph learning tasks: semi- supervised node classification and link prediction.
4.1 EXPERIMENTAL. SETUP
Datasets. We experimented with six benchmark datasets from two different domains: citation net- works (Cora, CiteSeer, PubMed (Sen et al., 2008) and OGBN-Arxiv (Hu et al., 2020)) and rec- ommendation networks (Amazon-Computers and Amazon-Photo (Shchur al., 2018)). For link

---

Published as a conference paper at ICLR 2023
(a) Structural missing
(b) Uniform missing
81
78.5
78.5
76
73.5
73.5
71
0.5
0.9
0.995
0.5
0.9
0.995
+ Raseline
Reacline 2 (1.P)
PIGNN
FP
PCFI (ours)
Figure 2: Average accuracy (%) on the six datasets with I'm E {0, 0.5, 0.9, 0.995). sRMGCNN and GCNMF excepted due to OOM results in certain datasets and the significantly poor performance on all the available datasets, as table shows.
prediction, we evaluated all methods the five benchmark datasets except OGBN-Arxiv that was caused out of memory. The datasets are described in Appendix A.4.1.
Compared Methods. For semi-supervised node classification, we compared our method to two baselines and four state-of-the-art methods. we set Baseline to a simple scheme that directly fed the graph data with missing features to GNN without recovery, where all missing values in a feature matrix were set to zero. We set Baseline to label propagation (LP) (Zhu & Ghahramani, 2002) which does not use node features and propagates only partially-knowy -nnown labels for inferring the remaining labels. That is, LP corresponds the case of 100% feature missing. The four state-of-the- art methods can be categorized into two approaches: GCN-variant model= (GCMMF (Taguchi et al., 2021), PaGNN (Jiang& & Zhang, 2020)) and feature imputation= (sRMGCNN (Monti et al., 2017), FP (Rossi et al., 2021)). While GCN-variant models were designed to perform node classification directly with partially known features, feature imputation methods combine with GNN models for downstream tasks, In Baseline I, sRMGCNN, FP, and our method, we commonly used vanilla GCN (Kipf& & Welling, 201 for the downstream task.
For link prediction, we compared method with sRMGCNN and FP, which the feature impu- tation approach. To perform link prediction on the imputed features by each method, graph auto- encoder (GAE) (Kipf & Welling, 2016b) models were adopted. We used features inferred by each method as input of GAE models. We further compared against GCNMF (Taguchi et al., 2021) for link prediction. We report the detailed implementation in Appendix A.3.
Data Settings. Regardless of task type, we removed features according missing rate I' (0 I'm < 1). Missing features were selected in two ways.
Structural missing. We first randomly selected nodes ratio of rm among nodes. Then, we assigned all features of the selected nodes to missing (unknown) values (zero). Uniform missing. We randomly selected features in ratio of r.. from the node feature matrix X, and we set the selected features to missing (unknown) values (zero).
For semi-supervised node classification, we randomly generated 10 different training/validationnee splits, except OGBN-Arxiv where the split was fixed according to the specified criteria. For link prediction, we also randomly generated 10 different training//alidationnn// splits for each datasets. We describe the generated splits in detail in Appendix A.4.2.
Hyper-parameters. Across all the compared methods, we tuned hyper- ppprmmerreeetrrs based on val- idation set. For PCFI, we analyzed the influence of and / in Appendix A.3.2. We used grid search to find the two hyper-parameters in the range of 0 < < and 0 < B S on validation sets. For the node classification, (a, (3) was determined by the best pair from (a.33)e E 00.1, ... .0.9), E {10-6, 101-1-.. 5.5 ,1]]. For the link prediction, the best 3) was searched from ((a, () E 0.2. ... 009), 3 E {10-6, 1010 ,.... []}] shown in Figure 3, 4 of APPENDIX.
Ablation Study. We present the ablation study to show the effectiveness of each component (row- stochastic transition matrix, whannel-wise inter-node diffusion, and node-wise inter-channel propa- gation) of PCFI in Appendix A.4.4.
8

---

Published as a conference paper at ICLR 2023
Table Node classification accuracy (%) at missing rate I' 0.995. OOM denotes out of memory. denotes incalculable average for six datasets due to OOM results.
Missing type
Dataset
Daseline
Baseline 2 (LP)
sRMGCNN
GCNMF
PaGNN
FP
PCFI
Com
74.02
1.60
8.85
ClteSeer
31,08 = 1.50
65.89
2.29
21.21 1.35
21.50
1.52
25.09
3.98
09.76
2: 2.47
00.18
2.75
Structural missing
PuhMed
48.20 4: 3.65
72.25
1.78
00M
40.19
0.95
50.82
= 4.61
72.69
2.06
74.66
2.26
2.17
2.57
26.10 1.80
66.91
3.50
46.57
87.70
Computers
72.03
1.91
76.28
1.43 67.56
0.12 37.15
9.81 30.50
56.50
3.29
17 45
1.59
79.25
1.19
OGBN-Ame
54.52 = 0.63
0.00
00M
0OM
57.43
0.36
66. 23
0.27
68. 72
0.28
Average
56:04
73-15
47.98
72.92
75.33
Cora
62.63 4: 2.64
74.52 d: 1:60
29.32
0.74
27.85
2.27
53.75 2: 2.03
T7.35 1: 2.01
78.53 =:: 1.39
CiteSeer
63.19 + 1.83
63.89
2:29
24.00
1.90
24.29
1.47
44.95 + 2.50
08.00 2.16
69.40
1.85
Uniform missing
PubMMed
8.78
00M
3.78
Photo
65,40
1.33
82.
2.57
26.58
1.68
25.06
3,90
55.30
1.05
57.75 2: 1.07
60
1.30
Computens
79.49 = 1.21
76.28 1.43
37.16 + 0.12
34.78
4.00
78.04
1.18
$1.47 0.91
81.79 :: 0.70
OGBN-Arxiv
0OM
Average
67.28
73.15
64.6
76.22
77.49
Table 2: Link prediction results (%) missing rate I'm 0.995. OOM denotes out of memory.
Dataset
Full feotures
SENGUKNN
GUNXXF
Stractioral missing
FP
PCF
JRMOUNN
GUNNM
Uniiform missing
FD
PCF
Cora
AUC
AP
02.58 + 0.56
02.05 + 0.75
08.80
06.31
5.78
6:44
71.09
26 1.07
1100++000 0.87
83.74
86.12
1.05
1.04
86.45 + 1:15
88.20 26
0.00
08.67 + 0.36
06:40 5,63
70.78
07 25
173--0..5 0.56
1.10
58.75
96.31
1.40
1.10
87
80
30
24
1.08
1.35
CheSeer
XP
67.75 1:95
08:10 1.355
07.15
1.395
70.74
T:1.5 3.19
66.30 5.85 DOM
83.71
08.00-00
52.02
55.81
82.95
86.25
2:30
1.77
05.62
0:36
00M
77.05
0.36
0.20
05.70=000
0.330
05.07 0.21
0:23
Computers
AUC
AP
93,79 1:09
03.78
51.06 0.24
53.37
0.17
80.62 0.224
30.33-+00.1
00.57
90.92 1.05
94.65
94.67 11 0.43
83.30
93.08 0.22
0.18
83:30
53.05
0.17
0.23
50,00
03.90
03.90-m
2: 0.24
06.03
08
0.21
4.2 SUPEVVUDE NODE CLASSIFICATION RESULTS
Figure 2 demonstrates the trend of an average accuracy of compared methods for node classification on six datasets with different Tm- The performance gain of PCFI is remarkable at I'm 0.995. In contrast, the average accuracy of existing methods rapidly decrease Tm increases and are overtaken by LP which does not utilize features. In the case of uniform missing features, FP exhibits better resistance than LP, but the gap from ours increases r' increases.
Table illustrates the detailed results of node classification with Fm = 0.995. sRMGCNN and GCNMF show significantly low performance for all experiments in this extremely challenging en- vironment. Baseline (LP) outperforms PaGNN in general. and even FP shows worse accuracy than Baseline (LP) in certain settings. For all the datasets, PCFI performed in manner that was superior to the other methods at T' 0.995.
4.3 LINK PREDICTION RESULTS
Table demonstrates the results for the link prediction task =mm99.95. PCFI achieves state-of- the-art performance across all settings except PubMed with structural missing. Based on the results on semi-supervised node classification and link prediction, which are representative graph learning tasks, PCFI shows the effectiveness at a very high rate of missing features.
5 CONCLUSION
We introduced a novel concept of channel-wise confidence to impute highly rated missing features in graph. To replace the unavailable true confidence, we designed pseudo-confidence obtainable from the shortest path distance each channel feature on a node. Using the pseudo-confidence, we developed a new framework for missing feature imputation that consists of channel-wise inter- node diffusion and node-wise inter-channel propagation. As validated experiments, the proposed method demonstrates outperforming performance both node classification and link prediction. The channel- -ise confidence approach for missing feature imputation can be straightforwardly ap- plied to various graph-related downstream tasks with missing node features.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
The intentionally removed private or confidential information can be recovered using the proposed be misused. Therefore, the work is suggested be used
method and the recovered information for positive impacts on society in areas such as health care (Wang et al., 2020; Deng et al., 2020), crime prediction (Wang et al., 2021), and weather forecasting (Han al., 2022).
REPRODUCIBILIITY STATEMENT
For theoretical results, we explained the assumptions and the complete proofs of all theoretical results in Section 3.4, 3.5, and Appendix. In addition, we include the data and implementation details to reproduce the experimental results in Section 4 and Appendix A.3. The codes are available at htttt:::/ /tt:::///////ti hub. com/ maaehhoum/ppcit.
ACKNOWLEDGMENTS
This work supported by IITP grant funded by Korea goverament(MSIT) (No.80101-15-0266 Development of High Performance Visual BigData Discovery Platform for Large-Scale Realtime Data Analysis; N0.2021-0-01344 Artificial Intelligence Graduate School Program (Seoul National University)]
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. (TTensoFFlow): A system for [Large-Scale} machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pp. 265-283, 2016. 19
Paul D Allison. Missing data. Sage publications, 2001.
James Atwood and Don Towsley, Difftusion-convllutionaa neural networks. Advances in neural information processing systems, 29, 2016. 3,6
Abraham Berman and Robert Plemmons. Nonnegative matrices in the mathematical sciences. SIAM, 1994. 15
Halil Bisgin, Nitin Agarwal, and Xiaowei Xu. Investigating homophily in online social networks, In 2010 IEEE/WIC/ACM International Conference Web Intelligence and Intelligent Agent Tech- nology, volume 1, pp. 533-536. IEEE, 2010. 5
Halil Bisgin, Nitin Agarwal, and Xiaowei Xu. study of homophily on social media. World Wide Web, 15(2):213-23) 2012.
Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang. Learning on attribute-missing graphs. IEEE transactions on pattern analysis and machine intelligence, 2020.
1.2
Fan Chung. The heat kernel as the pagerank of graph. Proceedings of the National Academy of Sciences, (04(50):19735-1974) 2007. 3,
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006. 2
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Songgaojun Deng, Shusen Wang, Huzefa Rangwala, Lijing Wang, and Yue Ning. Cola-gnn: Cross- location attention based graph neural networks for long-term ili prediction. In Proceedings the 29th ACM International Conference on Information Knowledge Management, pp. 245-254,
2020. 10
10

---

Published as a conference paper at ICLR 2023
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
arXiv preprint arXiv:1903.0220 2019. 17
GDPR. General data protection regulation. https:///dppr
Accessed: 2022-09-28.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016. 3,
Adrien Guille, Hakim Hacid, Cecile Favre, and Djamel A Zighed. Information diffusion in online social networks: A survey. ACM Sigmod Record, 17(2)) 2013.
Jindong Han, Hao Liu, Haoyi Xiong, and Jing Yang. Semi-supervised air quality forecasting via self-supervised hicrarchical graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022. 10
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 22211882213, 2020. 7
Houye Ji, Cheng Yang, Chuan Shi, and Pan Li. Heterogeneous graph neural network with distance encoding. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 1138-1143. IEEE, 2021.
Bo Jiang and Ziyan Zhang. Incomplete graph representation and learning via partial graph neural networks. arXiv preprini arXiv:2003.10130, 2020. 1, 2, 8, 19
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
1rXiv:1412.69880 2014. 17
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609. 02907, 2016a. 1, 6,
Thomas N Kipf and Max Welling. arXiv:1611.07300, 2016b. 1, 8, 17.20
Variational graph auto-encoders.
arXiv preprint
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 180.0:1810.059977, 2018 3,6 6
Johannes Klicpera, Stefan Weißenbberger, and Stephan Günnemann. Diffusion improves graph learn- ing. arXiv preprint arXiv:1911.0545) 2019. 3. 6, 20
Hady Lauw, John C Shafer, Rakesh Agrawal, and Alexandros Ntoulas. Homophily in the digital world: A livejournal case study. IEEE Internet Computing. 14(2):15-33, 2010. 5
Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. Advances Neural Information Processing Systems, 32, 2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-4478. 2020. 2
Jongin Lim, Daeho Um, Hyung Jin Chang, Dae Ung Jo, and Jin Young Choi. Class-attentive dif- fusion network for semi-supervised classification. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAL, pp. 2-9, 2021. 6.6
Roderick JA Little and Donald Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with con-convexity. Advances in neural information processing systems, 24, 2011. 2
11

---

Published as a conference paper at ICLR 2023
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):415 444, 2001. 5
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recur- rent multi-graph neural networks. Advances in neural information processing systems, 30, 2017.
2, 8, 19
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking:
Bringing order to the web. Technical report, Stanford InfoLab, 1999. 3, 6
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017. 17
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710, 2014. 3,
Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael Bronstein. On the unreasonable effectiveness of feature propagation learning on graphs with missing node features. arXiv preprint
2021. 1, 3, 6, 8, 15, 19
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 001.11111100... 2018. 7
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Hya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-1958, 2014. 17
Fan-Y Yun-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint 1908.0 2019.
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021. 2, 17, 19
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903 2017. 1
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Chenyu Wang, Zongyu Lin, Xiaochen Yang. Jiao Sun, Mingxuan Yuc, and Cyrus Shahabi. Hagen: Homophily-awar graph convolutional recurrent network for crime forecasting. arXiv preprint arXiv:2109.1288. 2021. 10
Ziyu Wang, Nanqing Luo, and Pan Zhou. Guardhealth: Blockchain empowered secure data manage- ment and graph convolutional network enabled anomaly detection in smart healthcare. Journal of Parallel and Distributed Computing, 142:1-12, 2020. 10
Zonghan WI, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEFE transactions on neural networks and learning systems, 32(1):4-22 24, 2020. 1
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462, PMLR, 2018.1 1, 18
12

---

Published as a conference paper at ICLR 2023
Jiaxuan You, Xiaobai Ma. Yi Ding, Mykel J Kochenderfer, and Jure Leskovec. Handling missing data with graph representation learning, Advances in Neural Information Processing Systems, 33: 19075-19087, 2020. 2
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018. 2
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34, 2021.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. AI Open, 1:57-81, 2020.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propa- gation. 2002. 8, 19
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
A. PROOF OF PROPOSITION
Proposition If sd d m 1, 0 a missing node, then fjriaa vy E NV;)) is given by
Es/i.d a= if Sidd Sj,d
E 1 if S jjd
Effid = a if Sid < Sjd
Otherwise, is source node (St,d = 0), then Esjrafor v E (N()) is given by
Ss/L.d 1 if Vj is source node (S 1),
Sy/id or iʃ oj is missing node (S = 0).
Proof. Let and be arbitrary nodes, and let 8(va, 0s) denote the number of edges in the shortest path between 2a and vo. The shortest path distance from v; to its nearest source node for the d-th feature channel, St,d, is given by
= min(s v.)l v. (
Claim 1: St,d = 0 + Us E V Proof: Since is a source node, S.d 0.
Claim Sid 2 + vs & th + i E !!d)) Prooft Since o; is not a known node (u; & (((i))
and only of 0 is unknown node (e, vid"), then Sr, 2 1 is obvious.
Let Ug be a known node such that 8(v,, Ut) = m which exists because St = m. Then d(v., 2₁) S 8(v,, (4) + 8(v,, v,) + holds by the triangle inequality since shortest path distance is metric on the graph. This proves that Sjad I m + 1, and also included the case Sta = as a special case.
Assume that there is some known node V&r such that 5(U,, 0g)) S m Then 8(v,, < 8(2,, 12) + 8(1,, Ug/) < 1 + m - dicts Si.d = m. Therefore, for all source node s', 8(13, 2 m which implies Sjdd 2 m 1...
1 by the triangle inequality. However, this contra-
Then, the following Claim 3 also holds.
Claim 3: If Si m 2 1, then Sja - Stdd E (-1.0.1) for E N(v.). Otherwise, St = O, then Sjd Saa {0.1} for 0j NNcc)
According Claim 3 and Ez/i.d S in Definition 3 of the main text, the proposition holds trivially.
14

---

Published as a conference paper at ICLR 2023
A.2 CONVERGENCE OF CHANNEL- WISE INTER-NODE DIFFUSION
The convergence of the proposed Channel-wise Inter-node Diffusion is presented in the following Proposition.
Proposition A.1. The channel-wise inter-node diffusion matrix for the d-th channel, W is ex- pressed by
I
W
(4)
W wa
ask
where W is the stochacchsticc matrix calculated by normalizing W(d), The recursion in channel- wise inter-node diffusion for the d-th channel is defined by
(d)
a:40 = 3k
O
((1) (d) a (t
Then, lim 2 (K) converges to (I W W (d) (d) uu ub 2k where 2x is the known feature of the
K-000 d-th channel.
The proof of this Proposition follows that of (Rossi et al., 2021) which proves the case of symmetrically-nornaai
diffusion matrix. In proof, the diffusion matrix is not symmetric. For proof of Proposition A.I, we first give Lemma A. and A.2.
Lemma A.1. W is the row-stochastic matrix calculated by normalizing W which is the weighted adjacency matrix of the connected graph G. That is, w(d) (D(d) -W where
D - Ej Wej- Let W (d) be the (a( | bottom-right submatrix of W (d) and let p(-)
denote spectral radius. Then, pl ( (d)
uu < 1.
Proof. Let unl NxN be the matrix where the bottom right submatrix is W uu and all the other elements are zero. That is,
(d) wao
0kk
Oku W (4)
W
Ouk
where O&t E {0)11)
| | 1,00 Oun E {0) [ | x
and Ouk E {0)1e!5) | x
Since W is the weighted adjacency matrix of connected graph G. W und W element-
(4)
wisely and Wild) * ( Moreover, since Wid) uwo strongly connected graph, Wil)
(
is weighted adjacency matrix of
and + W(()) is irreducible due Theorem 2.2.7 of (Berman & Plem-
mons, 1994). Then, by Corollary 2.1.5 of (Berman & Plemmons, 1994), p W (d)
aan) <(W(())
Since the spectral radius of a stochastic matrix is one (Theorem 2.5.3 (Berman & Plemmons, 1994)), p( W
Furthermore, since (i()) and and ((d)
uu share the same non-zero eigenvalues,
p (W wu
(d) p Wi()) m.)). Finally, p( (W)ld) ((Wild) uuo) < 1.
Lemma A.2. I w!lh uu is invertible where the [uu
(d) x au
identity matrix.
Proof. Since is not an eigenvalue of W(() we by Lemma A.1, 0 not an eigenvlaue of I W
Thus W (d) uu is invertible.
In the following, we give the proof of Proposition Proof of Proposition 1. Unfolding the recurrence relation gives us
(())(1) =
1 (t)
Ku
i (1)) (t 1)
x
(d) (t
ta (t)
(d)
=
W
2 (t 1)
(d)
=
W!
(d) a
(t 1) + w uw Bu (t 1)
(d)
wk
15

---

Published as a conference paper at ICLR 2023
(1 1) in the first | (d) Since #6 (4) (1) 3x
(d)
rows, (4) (K) (d)
That is, (K) remains
(4) (K)
k Hence lim 2 (K) converges to k 00000
Now, we just consider the convergence of lim K-000
( (K). Unrolling the recursion of the last | (a))
rows become,
(K)
Wild! (d) us k
+
Wll
au a (K 1)
Wild) (d)
+ W (d)
Wild (d) (d)
(d) (1) uu 2u
uke k
au uk kk
+
W
(K 2))
d) (d) T
W (d)
Since lim W -00
( uu
K
by Lemma A.I, lim
K
(0) = 0 regardless of the initial state Da
K K00
uu
for Du (0). (We replace al. (0) with zero column vector for simplicity.) Thus, it remains to consider lim (C (w (()) uu )d) W (d) (d)
uk k
K+000
by Lemma A.I and (I W uu series converges as follows
Since p
-1 is invertible by Lemma A.2, the geometric
K-1
lim a K
(K)
lim K-yac
(I
W (d) (d) uik 2
uu
uk
uu
Thus, the recursion in channel-wise inter-node diffusion converges.
16

---

Published as a conference paper at ICLR 2023
A.3
IMPLEMENTATION
A.3.1
IMPLEMENTATION DETAILS
We used Pytorch (Paszke et al., 2017) and Pytorch Geometric (Fey & Lenssen, 2019) for the exper- iments on an NVIDIA GTX 2080 Ti GPU with 11GB of memory.
Node classification. We trained GCN-variant models (GCNMF, PaGNN) and GCN models for feature imputation methods (Baseline 1, sRMGCNN, FP, PCFI) as follows. We used Adam op- timizer (Kingma & Ba, 2014) and set the maximal number of epochs 10000. We used early stopping strategy with patience of 200 epochs. By grid search on each validation set, learning rates of all experiments are chosen from {0.01, 0.005, 0.001, 0.0001}, and dropout (Srivastava et al., 2014) was applied with selected in {0.0, 0.25, 0.5}.
Link prediction. For GCNMF and GAE used as common downstream models for feature impu- tation methods, we trained the models with Adam optimizer for 200 iterations. By grid search on the validation set, learning rates of all methods are searched from {0.1, 0.01, 0.005, 0.001, 0.0001) for each dataset, and dropout was applied to each layer with searched from (0.0, 0.25, 0.5}. As specified in (Kipf & Welling, 201 and (Taguchi et al., 2021), we used a 32-dim hidden layer and 16-dim latent variables for the all auto-encoder models.
For the compared methods, we followed all the hyper- peeem-prrmeterr in original papers or codes if feasible. If hyper-parameters (the number of layers and hidden dimension) of model for cer- tain datasets are not clarified in papers, we searched the hyper-parameters using grid search. In that case, {16, 32, 64, 128, 256].
searched the number of layers from {2,3) 3} and the hidden dimension from
We present the pscudo-code of our PCFI in Sec. A.6. Our code will be available upon publication.
A.3.2 PCFI
Accuracy
0.1
60.13
60.27
60.23
59.65
60.16
59.60
59.74
60.03
59.90
60.42
60.34
60.61
60.98
-66
0.2
61.32
61.94
61.27
61.48
61.55
61.42
61.10
61.44
61.39
61.48
62.73
62.03
61.89
65
64
63.23
64.40
63.26
63.48
63.45
63.19
63.34
63.53
63.19
63.45
63.55
63.32
64.03
0.5
64.40
64.40
64.31
64.03
63. 98
64.79
64.65
64.73
64.47
64.73
65.10
64.69
64.26
63
0.6
65.05
65.21
64.90
65.29
0.7
65.24
65.24
65.10
65.47
65.18
65.32
65.10
65.84
65.61
65.82
66
65.31
65.63
-61
0.8
65.71
65.31
65.29
65.35
65.76
65.56
65.65
65.63
65.60
66.13
65.74
65.52
65.81
0.9
65.81
63.81
65.76
65.81
65.73
66.35
65.42
65.58
65.58
65.48
65.81
65.40
65.66
10"4
10-55
10-4
10
10
20-1
10a1
30
10
10-1
10-1
10-11
B
Figure 3: Node classification accuracy on CiteSeer with different and B. The experiments conducted under structural-missingg setting with T. = 0.995.
We set K 100 throughout all the experiments. PCFI has two hyper-parameters a and B. a used to calculate PC for channel-wise inter-node diffusion and node-wise inter-channel propagation. B controls the degree of node-wise inter-channel propagation. To analyze the effects of the hyper- parameter, conducted experiments with various and Figure 3 and Figure 4 demonstrate the influence a and B.
For node classification, we chose a from (0.1, 0.2, 0.9). and / from {10-t 6,- 10 1.55 10 ,,.,,, using a validation set. Then, for link prediction, search range of and same in Figure 4, We selected from
search range of and 8 same in Figure 3. For node classification,
17

---

Published as a conference paper at ICLR 2023
AUC
AP
83.43
83.51
83.39
83.33
83.19
83.57
83.66
0.1
85.76
85.79
85.73
85.74
85.72
85.94
86.16
0.2-83 83.76
83.75
83.65
33.97
83.84
83.83
83.69
02
86.19
86.17
36.09
86.28
86.14
86.26
86.18
-8.5
-8755
0.4
84.47
84.43
84.53
84.52
48
84.33
04
86.65
86.64
86.66
86. 74
86.64
86.76
86.56
a
0.5
94.63
84
61
84.60
84.57
84.54
84.67
88.78
0.5
86.73
86.69
86.69
86, 72
86.54
86.97
86 96.95
87.0
0.6
84.49
84
84.37
84.52
84.42
85.16
866-86.3
86.64
86 86.67
-5.44
166.48
75
87
86.5
-84.0
0.8
84
84 88
154
84.81
58
84. 64
86 0:3
0.8
86 75
86. 78
96.
880 69
86
86 99
-83.5
0.9
19.117.7
84 14
104.10
94.15
84. 35
05. 04
86 45
0.9
86
86.24
86.23
96.20
86 49
87.17
88.26
10
10
10
10
10"*
10
10
10-4
10-4
10-3
10-2
10-1
B
B
Figure 4: Link prediction results Cora with different and B. The experiments are conducted under a structural missing setting with Tmm = 0.995.
Table 3: Jyper-parameters of PCFI used in node classification.
Missing type
Structural missing
Uniform missing
I'm
0.995
0.9
0.5
0.995
0.9
0.5
Cora
a
0.9
0.9
0.6
0.7
0.5
0.5
B
1
10
10
10-1
CiteSeer
a
8
10-1.5
0.8
1.5
10 0.5
0.6
0.5
1
10-0.5
0.8
0.5
0.1
a 0.8
0.9
0.9
0.7
0.8
0.2
PubMed
B
10
10-0.1 0.5
10 0.5
10 1..5.5
1
1
Photo
B
a
10-4
0.2
10-6
0.4
10-2.5
0.6
10-1.5
0.2
10-6
0.2
104.5
0.5
0.1
0.1
0.3
0.1
0.2
0.4
Computers
B
10-3.5
10-4
10-5.5
10-2.5
10-4
10-5.5
OGBN-Arxiv
a
B
10-6
0.1
10-6
0.4
10
0.2
10
0.2
10
0.8
10
10-2.5
0.8
Table 4: Hyper-parameters of PCFI used in link prediction.
missing type
Dataset
Cora
CiteSeer
PubMed
Photo
Computers
Structural
a
0.9
0.9
0.2
0.1
0.1
3
1
10
10
10-1
Uniform
a
0.9
0.6
0.1
3
1
1
To find the best hyper-parametet we used grid search validation set. The detailed setting of hyper-parameters for all datasets used in our paper are listed in Table 3 and Table 4.
(0.1, 0.,. 0.9}. and 3 from {10-6, 10 1001,
1}. ,....
To train downstream GCNs added to PCFI for node classification, we fix learning rate to 0.005. Then, to train downstream GAE added to PCFI for link prediction, we set a learning rate to 0.01 and 0.001 for (Cora, CiteSeer, PubMed) and (Photo, Computers), respectively.
Downstream GCN for node classification. We set the number of layers to 3, and We fix dropout rate p 0.5. The hidden dimension was set to 64 for all datasets except OGBN-Arii where 256 is used. For OGBN-Arávv, as the Jumping Knowledge scheme (Xu al., 2018) with max aggregation was applied to FP, also utilized the scheme.
18

---

Published as a conference paper at ICLR 2023
A.3.3 IMPLEMENTATION OF BASELINES
GCNMF (Taguchi al., 2021). We used publicly released code by the authors. The code for GCNMF is MIT licensed.
FP (Rossi et.,, 2021). We used publicty released code by the authors. The code for FP is Apache- 2.0 licensed.
PaGNN (Jiang & Zhang, 2020). We used re-implemented Apache-2.0-licensce code since could not find officially released code by the authors for PaGNN.
SRMGCNN (Monti et al., 2017). Due the compatibility problem from the old-version Tensor- flow (Abadi et al., 2016) of the code, we only updated the version of publicly released code* to Tensorflow 2.3.0. The code GPL-3.0 licensed.
Label propagation (Zhu & Ghahramani, 2002). We employed re-implemented code in- cluded in MIT-licensed Pytorch Geometric. We tuned hyper-parameter a of LP in {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95) by grid search.
A.4 EXPERIMENTS
A.4.1 DATASETS
All the datasets used in our experiments are publicly available from the MIT-licensed Pytorch Ge- ometric package. We conducted all the experiments on the largest connected component of each given graph. For disconnected graph, we can simply apply PCFI to each connected component independently. The description for the datasets summarized in Table
Table 5: Dataset statistics.
Dataset
Nodes
# Edges
Features
Classes
Cora
2,485
5,069
1,433
7
CiteSeer
2,120
3,679
3,703
6
PubMed
19,717
44,324
500
3
Photo
7,487
119,043
745
8
Computers
13,381
245,778
767
10
OGBN-Arxiv
169,343
1,166,243
128
40
"http:://github...
19

---

Published as a conference paper at ICLR 2023
(a) Graphs with class homophily 0.3
(b) Graphs with class homophily - 0.5
75
40
70
65
30
60
25
55
50
-7.32
-6.71
-6.12
-5.51
4.93
-4.8
-3.95
-7.32
.6.72
PCFI (ours)
FP
Figure 5: Node classification accuracy (%) on the synthetic graphs according to - Iog( where Ed is the Dirichlet energy (An increase in Ea means increase in homophily.). The experiments are conducted under a structural- misssig setting with 7m = 0.995. The proposed PCFI consistently outperforms FP and the performance gap widens homophily increases.
A.4.2 RANDOM SPLIT GENERATION
Node classification. We randomly generated 10 different training/validationness splits, except OGBN-Arxiv where the split was given according the published year of papers. As the setting in (Klicpera et al., 2019), in each generated split, 20 nodes class were assigned to the training nodes. Then, the number of validation nodes is determined by the number that becomes 1500 by adding to the number of the training nodes. As the test nodes, we used all nodes except training and validation nodes.
Link prediction. We randomly generated 10 different training/validaaioonness splits for each datasets. In each split, we applied the same split ratio regardless datasets. As the setting in (Kipf & Welling, 2016b), we commonly used 85% edges for train, 5% edges for validation, and the 10% edges for test.
A.4.3 GAIN OF PCFI ACCORDING TO FEATURE HOMOPHILY
In this section, since pseudo-confidence based on the assumption that linked nodes have similar features, we explored how feature homophily of graphs impacts the performance of PCFL We further analyzed the gain of PCFI over FP in terms of feature homophily. For the experiments, we generated features with different feature homophily contains 5000 nodes that belong to one of 10 classes.
graphs from the synthetic dataset where each graph
We selected two graphs (graphs with class homophily of 0.3 and 0.5) from the dataset. Preserving the graph structure and class distribution, we newly generated multiple sets of node features for each graph that each generated graph has different feature homophily. The features for nodes were sampled from overlapping 10 5-dimensional Gaussians which correspond to each class and the means of the Gaussians are set differently to be the same distance from each other. For the covariance matrix of each Gaussian, diagonal elements were set to the same value and the other elements were set to 0.1 times the diagonal element. That is, the covariance between different channels was set to 0.1 times the variance of a channel. For each feature generation of graph, we changed the scale of the covariance matrix so that features are created with different feature homophily, As the scale of the covariance matrix decreases, the overlapped area between Gaussians decreases. By doing so, more similar features are generated within the same class and the graph has higher feature homophily. Then, for semi-supervised node classification, 10 different validation, and test set to be equal.
randomly generated splits. For each split, we set the numbers of nodes in training,
20

---

Published as a conference paper at ICLR 2023
Figure 5 demonstrates the trend of the accuracy of PCFI and FP under a structural-misite setting with I'm = 0.995. We can confirm that the gain of PCFI over FP exceeds 10% on both graphs with high feature homophily. Furthermore, PCFI shows superior performance regardless of levels of feature homophily. This is because confidence based on feature homophily is the valid concept on graphs with missing features and pseudo-confidence is designed properly to replace confidence.
A.4.4 ABLATION STUDY
To verify the effectiveness of each element of PCFI, we carried out ablation study. We started by measuring the performance of FP that performs simple graph diffusion with a symmetrically- normalized transition matrix. Firstly, we changed the normalization type of the transition matrix. We replaced the symmetrically-noomalizze transition matrix with a row-stochastic transition matrix (row-ST in Table 6 and Table7). The row-stochastic transition matrix leads feature recovery the same scale of actual features. Secondly, we introduced PC to the diffusion process, which means PC-based channel-wise inter-node diffusion was performed (CID in Table 6 and Table7). Lastly, we performed nose-wise channel propagation on recovered features obtained by channel-wise inter- node diffusion (NIP in Table and Table7). We compared the performance of these four cases. In this experiment, for CiteSeer, we performed node classification under structural- missinn setting with T' 0.995. Then, for Cora and PubMed, we performed link prediction with rm 0.995. We applied structural missing and uniform missing to Cora and PubMed, respectively. As shown in Table and Table each component of PCFI contributes to performance improvement throughout the various settings.
Table 6: Ablation study of PCFI. row-ST, CID and, NIP denote a row-stochastic transition matrix, channel-wist -iieel-wiie inter-node diffusion, and node-wise inter-channel propagation, respectively.
row-ST
CID
NIP
CiteSeer
X
X
59.76 + 2.47
X
X
64.80 + 2.60
V
x
65.40 + 2.77
66. 18 + 2.75
Table 7: Ablation study of PCFL, row-ST, CID and, NIP denote a row-stochastic transition matrix, channel-wist inter-node diffusion, and node-wise inter-channel propagation, respectively.
Cora
PubMed
row- ST
CID
NIP
AUC (%)
AP (%)
AUC (%)
AP (%)
X
X
83.74 + 1.05
86.12 + 1.04
77.05 + 3.54
83.26 + 2.24
X
83.96 + 1.02
86.14 + 1.07
80.72 + 1.28
84.99 + 0.68
X
84.16
1.23
86.24 : 1.24
82.88 1.23
87.20 0.40
86.45 1.15
88.26 0.97
85.26 + 0.36
88.52 0.20
A.4.5 RESISTANCE OF PCFI TO MISSING FEATURES
To verify the resistance of PCFI against missing features, we compared the averaged node classifi- cation accuracy for the 6 datasets by increasing I'm as shown in Table. 8. We compared each average accuracy with different 2.23% of relative average accuracy with I'm 0.9, and 4.82% with I'm 0.995. In the case of uniform missing, PCFI loses only 1.81% 1 of relative average accuracy with I' = 0.9, and 2.66% with Fm = 0.995. Note that classification with r. = 0.995 the extremely missing case which only 0.5% of features are known. This result demonstrates that PCFI is robust to missing features.
from I' 0 to I'm = 0.95. For structural missing, PCFI loses only
Even at the same Tm. we observed the average accuracy for structural missing is lower than one for uniform missing. We analyzed this observation in the aspect of confidence. Since features are missing in a node unit for structural missing, all channel features of node have the same SPD- S. i.e., S.1 ... S.F. Hence, in node far from its nearest source node, every channel feature has low confidence. Then, every missing feature of the node can not be improved via node- wise inter-channel propagation due to the absence of highly confident channel features in the node.
21

---

Published as a conference paper at ICLR 2023
Node classification accuracy (%) of PCFI different missing rates of for two missing types. For each experiment, we report the mean with standard deviation (mean + std). For each missing type, we report average accuracy with relative drop (%p) compared a full-feature setting (average (drop)).
Table 8:
Missing type
Dataset
Full features
50% missing
90% missing
99.5% missing
Cora
82.35 + 1.49
80.37 + 1.55
78.88 + 1.43
75.49 = 2.10
CiteSeer
70.98 + 1.46
70.10 + 2.02
69.76 + 1.96
66. = 2.75
PubMed
77.49 + 2.05
75.93 + 1.44
76.12 + 1.87
74.66 = 2.26
Structural missing
Photo
92.14 + 0.62
91.81
+ 0.54
89.96 + 0.68
87.70 = 1.29
Computers
85.67 + 1.41
84.91 + 0.88
82.40 +: 1.38
79.25 1.19
OGBN-Ariv
72.28 + 0.11
71.64 + 0.19
70.39 + 0.19
68.72 = 0.28
Average
80.15
79.13 (-1.02)
77.92 (-2.23)
75.33 4.82)
Cora
82.35 + 1.49
81.28 + 1.59
79.55 + 1.32
78.53 = 1.39
CiteSeer
70.98 + 1.46
71.68 + 1.92
69.92 + 1.68
69.40 = 1.85
PubMed
77.49 + 2.05
76.88 + 2.09
76.56 + 2.08
76.44 = 1.64
Uniform
Photo
92.14 0.62
91.83 + 0.58
89.84 + 1.00
88.60 1.30
missing
Computers
85.67 + 1.41
84.96 + 1.15
83.14 + 0.72
81.79 = 0.70
OGBN-Arxiv
72.28 + 0.11
71.78 1778::00 0.09
70.91 + 0.17
70.19 0.15
Average
80.15
79.73 (-0.42)
78.34(-1.85
77.49 2.66)
Thus, the node is likely to be misclassified. In contrast, for uniform missing, channel features of a node have various PC where known channel features have high confidence and propagate their feature information to unknown channel features in the node. Hence, most nodes can be classified well owing to the recovered features from highly confident channel features. We claim that this observation shows the validity of the concept of channel-wise confidence. The tables containing accuracy at different I'm for the two missing types in Section A.5.
A.4.6 CLASSIFICATION ACCURACY ACCORDING TO PSRUDO-CONFIDENN CONFIDENCE
Accuracy
07
Accuracy
SPD-S
SPD-S
(a) Cora
(b) Citeseer
Figure 6: Node classification accuracy (%) according to SPD-S of test nodes. For both Cora and CiteSeer, structural missing with rm 0.995 is applied. PCFI* denotes PCFI without node-wise inter-channel propagation. PCFI shows a noticeable performance gain especially for nodes with low-PC missing features (large-SPD-S nodes). Also, node-wise inter-channel propagation shows its effectiveness on nodes with low-PC features.
Under a structural missing setting, node features in node have the same SPD-S, i.e., St,
Sia for the i-th node. Since pseudo confidence Çi,d is calculated by &idd S.d, node features within a node also have the same pseudo-confidence (PC) for structural missing, i.c., Ei E.d. We refer to SPD-S of node features within a node as SPD-S of the node. Similarly, we refer to PC node features with node as PC of the node. The test nodes are divided according to SPD-S of the nodes. Then, observe the relationship between PC and classification accuracy, calculated classification accuracy of nodes in each group. We conducted experiments on Cora and CiteSeer under structural missing setting with r.. 0.995. We compared PCFI with sRMGCNN and FP.
22

---

Published as a conference paper at ICLR 2023
Figure 6 shows node classification accuracy according to SPD-S of test nodes. For both datasets, as SPD-S of nodes increases, the accuracy of FP tends to decrease. However, for large-SPD-S. nodes, PCFI gains noticeable performance improvement compared to FP. Furthermore, the results on Cora show that PCFI outperforms PCFI without node-wise inter-channel propagation on large- SPD-S nodes. Since large SPD-S means low PC, observe that PCFI imputes low-PC missing features effectively.
A.4.7 DEGREE OF FEATURE RECOVERY ACCORDING PSEUDO PSEUDO-CONHIE CONFIDENCE
1.0
SRMGCNN
FP
PCF
PCFI
sRMGCNN
FP
PCFN
PCR
0.9
Cosine Similarity
Cosine Simllarity
0.200
0.175
0.20
0.150
0.15
0.125
0.10
0.075
0.050
0.05
12 14
SPD-S
SPD-S
(a) Cora
(b) Citeseer
Figure 7: Cosine similarity between X,, (original features node) and X,, (its recovered fea- tures) according to SPD-S of features within the node. For both datasets, we randomly selected 99.5% nodes and remove all features of the selected nodes (structural missing) so that all channel features within a node have the same SPD-S. The imputed feature similarity between two nodes tends to decrease as the shortest path distance between the two nodes increases.
We further conducted experiments to observe the degree of feature recovery according to SPD-S of nodes. evaluate the degree of feature recovery for each node, we measured the cosine similarity between recovered node features and original node features. The setting for experiments is the same as in section A.4.6.
Figure 7 demonstrates the results on Cora and CiteSeer. As SPD-S of nodes increases from zero, which means PC nodes decreases, the cosine similarity between tends to decreases. In other words, PC of nodes increases, the cosine similarity tends to increase. This shows that the pseudo- confidence is designed properly based on SPD-S, which reflect the confidence.
Unlike the tendency in node classification accuracy, PCFI shows almost the same degree of feature recovery as PCFI without node-wise inter-channel propagation. This means that node-wise inter- channel propagation improves performance with very little refinement. That is, higher classification accuracy on nodes does not necessarily mean higher degree of feature recovery of the nodes. We leave detailed analysis of this observation for future work.
23

---

Published as a conference paper at ICLR 2023
A.4.8
COMPUTATIONAL COST
220.89s
14.20s
4.90s
2.28s
2.63s
sRMGCNN
GCNMF
PaGNN
FP
PCFI
Figure 8: Training time (in seconds) of methods on Cora under structural-missing setting with 0.995.
To compare computational cost, we measured the total training time on single split of Cora. We performed node classification under structural-misiig setting with I' 0.995. The training time of each method shown Figure The training time (sRMGCNN, FP, PCFI) includes both the time for feature imputation and training of downstream GCN. PCFI shows less training time than the other methods except for Even compared to FP, PCFI takes only 15.4% more time than FP. For PCFI under uniform-missing setting, the time for computing SPD-S increases by the number of channels. PCFI outperforms the tate-of-the-an methods with less comparable computational cost to the other methods.
feature imputation methods
24

---

Published as a conference paper at ICLR 2023
A.5
NODE CLASSIFICATION ACCURACY ACCORDING TO MISSING RATE FOR EACH
SETTING
(a) Structural missing
(b) Uniform missing
85
85
Cora
77.5
77.5
73.75
73.75
70
0.5
0.9
0.995
0.5
0.9
0.995
72
CiteSeer
69
66
60
60
0.5
0,9
0.995
80
78
PubMed
75
74
72.5
72
70
0.5
0.995
0.995
94
Photo
91.25
87.5
87
83.75
83.5
80
80
0.5
0.995
0.5
0.9
0.995
Computers
87.5
87
76.25
78
0.995
0.995
OGBN OGBN-arxiv arriiv
70
70.5
67.5
68
65.5
62.5
63
0.5
0.995
0.995
Baseline
Baseline (LP)
P&GNN
PCFR (ours)
Figure 9: Average accuracy (%) for each setting (missing type, dataset).
25

---

Published as a conference paper at ICLR 2023
A.6 PYTORCH-STYER PSEUDO-CODE IMPUTATION (PCFI)
FEATURE
Algorithm PyTorch-style pseudo-code of PCFI
class PCFI (torch. nn [tfoorcc...MModuee))............
def _init_____ (self, K, alpha, beta):
super (PCFI, self) .nt.iinitt_..
self.K - self. alpha
self.beta = beta
edge_iineee _ig_xinexx has shape [2, [8]]
mask is a boolean tensor indicating known features with True def (so,agate x, edge_index, mask, mask_type) :
nv, feat_dim x.shape
# Channel-wise inter-node diffusion out out [mask] = x [mask]
# structural missing case
if mask_type == "structural":
SPDS self.compute SPDS (edge (edge_index, index, mask, mask mask_type) Wbar = self.compute_Mbe.. for t in range
redge_indess mask, mask_type)
out torch.sparse. mm (Wbar, out)
out [mask] x [mask]
SPDS = SPDS. (feat_dim, 1)
# uniform missing case
if mask _ask_type
"uniform":
SPDS self. www..compute_aeeee. SPDS bedgg_inddes mask,
mask_type, feat_dim)
for d in range (feat_dim)
Wbar self. wwwputemmppeaaeeeeeeeeeee for i in range (self.K):
Wbar (edge_index: SPDS[d])
(ut(: torch. mm (Wbar,
out[:, reshape (-1, reshape (-1)
out [mask[;;,)], = x [mask[;,d],d)
# Node-wise inter-channel propagation
cor torch. corrcoef (out _na__to_num fiill_diaagoaa (0)
al (self.alpha SPDS.T) (out torch (out,
dim=0))
a2 torch matmul (al, cor)
outl self.beta * (1 self.alpha ** SPDS.T) a2
out out outl
return out
26

---

Published as a conference paper at ICLR 2023
Algorithm 2 PyTorch-style pseudo-code for SPD-S
get SPD-S of each node by computing the k-hop subgraph around the source nodes
In this code, SPDS has shape [F, N]
def Sampute_SPDSS (self, edge_index, feature _ass,, mask mask_type,
feat_ dim None)
nv = feature_mask. shapee
# structural missing case
if mask_type == "structural";
SPDS torch. (nv, dtype torch.int)
# v_o represents the source nodes
v_0 torch.nonzers (feature_maskll 0)) view
vo to_k = v_0
SPDS [v_0]
k =
while True:
v_k_hop_sub = torch. www.ch.geometrc..ttlll .k_hop Lcthop_subgrahe (v_0, k, edge_index, num_nodes nv) [0]
# v_k represents the nodes of which SPS-S =
torch. from_numpy (np. setdi (v_k_hp__s_)
v_0_to_k)
if (v_kk break
SPDS[v_k]
torch. (lv_0_to_k, v_k), dim=0)
k +=
# uniform missing case
if mask_type == "uniform":
SPDS = torch. (feat dim, nv) for d in range (feat_dim)
v_0 torch. (faarurreeeaaatremaaaaaa (I view (-1)
v_0_to_k = v_0 v_
SPDS(d, v_0] ==
while True:
v_k_hop_sub h.g..uiiss..hhhpuuurrhahhhh torch,
v_0, k, edge_index, num sam__oddes = nv) [0]
v_k torch. @rro__nnumpar (np. (np.setdiff1d
w_k__op_ssth v_0_to_k))
if (e_(v_k) 0:
break
[d, v_k] = k
torch. cat 1v____t_k v_k), dim=0)
k += 1
return SPDS
27

---

Published as a conference paper at ICLR 2023
Algorithm 3 PyTorch-style pseudo-code for W(d)
def compute_Wbar (self, edge_index, SPDS)
# In the propagation, row and column correspond # destination and source, respectively. row, col edge edge_indes indexx[]) edge_indee [1] SPDS_roW SPDS SPDS_col SPDS[col]
edge_weigtt = self.alpha ** (SPDS_Col SPDS_row 1)
# row-wise sum
deg__
torch_scatter.sattee..ee
wedge_weigh,, row,
dim_size= shDs.shape(0)
# normalize W(d) to row-stochastic (4
deq___ine = deg_M.pow_(11.11
deg_ W deq_W_inv.met hww.masked_fill_dde____ W float ("inf"), 0)
norm_edggeweightt edge_weight deg_M_inv(rov)
Wbar torch. Flateeeeo (edge_index, values= norm edge_weeigee__
return Wbar
28


Reviews:
[{"review_id": "oXekSimUF-", "reviewer": "Reviewer_z9Q8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 tackle the problem of imputation in graphs, in which we want to predict missing node features in graph-structured data. Their approach uses a strategy involving pseudo-confidence (PC), where the PC of a given feature is proportional to alpha^S, where S is the corresponding node's nearest labeled neighbor. They combine this with a propagation strategy which shares information between features of the same node and between neighboring nodes. \n\nThe authors evaluate their method on a benchmark data set OGN. They follow (Rossi et al, 2021) in their evaluation. Their primary evaluation is on a data set from arXiv, in which nodes represent papers, edges denote citations between papers and node features are a representation of the words used in the paper's title and abstract. They hold out a subset of features of each node and impute these held-out features. They show that on these tasks their method outperforms existing methods including GCNMF and Feature Propagation. ", "summary_of_the_review": "See above.", "strength_and_weaknesses": "Overall, the paper is understandable, the method is reasonable and the experimental results are good. As described below, I am not sure about the methodological novelty. The application impact seems high, although this is also hard to tell because the benchmarks used are on relatively contrived tasks. \n\nMy main concern is that I could not tell what parts of the proposed method are novel. This is partly because I am not too familiar with graph imputation. The proposed method contains many components and all components are described as though they are novel. In particular, the authors indicate that their main contribution as \"pseudoconfidence\" as alpha^S, where S is the distance in the graph.  They should explain that this is a common strategy used in random walk methods, Monte Carlo reinforcement learning, and many other methods. Similarly, they should explain and cite the inspiration for each other part of their method. It seems likely that there are novel components and novel ways in which preexisting components are combined, but I could not work out what these are. \n\nWhat real-world problems have 99% missing features?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "25AhpEgXhJ", "reviewer": "Reviewer_NNts", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 proposes an imputation method for missing node features in graph neural networks. There is a node-wise diffusion as well as channel-wise diffusion that is based on the \"pseudo confidence\" of a missing feature node, which is inversely proportional to the distance to the closest observed feature node. Semi-supervied learning and link prediction experiments are conducted with good results in the very low sampling regime (0.5%).", "summary_of_the_review": "I think the idea presented in this paper is interesting, and it is explained well. There are also extensive experiments with promising results. But it's not clear why this ~1% gain in accuracy makes this better than the very simple FP.", "strength_and_weaknesses": "Strength: The idea is simple and easy to understand. Performance on the 0.5% sampling setting is impressive. Notations are explicitly defined and derivations are explained well. There are enough implementation details to reproduce the experiments. Extensive hyperparameter search was done (reported in appendix).\n\nWeakness: The advantage compared to feature propagation (FP) is not yet convincing. \nSince some of the concepts are straightforward, some sections (e.g. section 3.4) could be simplified to make room for more experiments that go beyond the benchmark datasets. For example, an experiment with simulated data to understand the model's behavior better could have made the paper's argument stronger.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0f-qSJXgH6", "reviewer": "Reviewer_tfst", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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 paper targets problems with graph learning tasks containing missing node features. \nTheir key idea is to assign different pseudo-confidence to each imputed channel features. \nThe proposed imputation scheme includes two processes.\nThe first one is the feature imputation using channel-wise inter-node diffusion, and the second is the feature refinement via node-wise inter-channel propagation.", "summary_of_the_review": "The work motivates by an interesting and practical problem when the graph learning is conducted in presence of missing node features.\nOverall, the methods look sound and reasonable.", "strength_and_weaknesses": "Strength :\n\nThe problem is clearly described and the methods are well presented.\nThe scheme can even handle at an exceedingly high missing rate (e.g., 99.5%) and achieves state-of-the-art accuracy for both semi-supervised node classification and link prediction on various datasets containing a high rate of missing features.\n\nWeaknesses:\nI did not find notable weaknesses of this paper.", "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": {}}]

Author rebuttal:

Decision: Accept: poster