Propagate and Inject: Revisiting Propagation-Based Feature Imputation for Graphs with Partially Observed Features
Authors: Daeho Um
Sunoh Kim
Jiwoong Park
Jongin Lim
Seong Jin Ahn
Seulki Park
Venue: ICML 2025 poster (2025)
Keywords: graph neural networks
graphs
missing features
Primary area: deep_learning->graph_neural_networks
TL;DR: For graphs with missing features, we identify a critical limitation of existing propagation-based imputation methods and propose a novel scheme that overcomes this limitation.

Abstract: In this paper, we address learning tasks on graphs with missing features, enhancing the applicability of graph neural networks to real-world graph-structured data. We identify a critical limitation of existing imputation methods based on feature propagation: they produce channels with nearly identical values within each channel, and these low-variance channels contribute very little to performance in graph learning tasks. To overcome this issue, we introduce synthetic features that target the root cause of low-variance channel production, thereby increasing variance in these channels. By preventing propagation-based imputation methods from generating meaningless feature values shared across all nodes, our synthetic feature propagation scheme mitigates significant performance degradation, even under extreme missing rates. Extensive experiments demonstrate the effectiveness of our approach across various graph learning tasks with missing features, ranging from low to extremely high missing rates. Additionally, we provide both empirical evidence and theoretical proof to validate the low-variance problem. The source code is available at https://github.com/daehoum1/fisf.

Propagate and Inject: Graphs with Partially Observed Features
Revisiting Propagation-Based Feature Imputation for
Daeho Um"
Sunoh Kim? Jiwoong Park?
Jongin Lim
Seong Jin Ahn Seulki Park
5
Abstract
ten include missing features for various reasons (e.g., private information in social networks and measurement failure), which hinders the direct application of GNNs to real-world data. This challenge is especially prevalent in industries, where severe feature missing rates of 97.5%, 99.9%, and 99.98% have been reported in real-world applications (Park et al., 2023; Chai et al., 2020; Kim & Chi, 2018). Conse- quently, applying GNNs graphs with missing features has received great attention with missing features (Chen et al., 2020; Jiang & Zhang, 2020; Taguchi et al., 2021).
In this paper, we address learning tasks on graphs with missing features, enhancing the applicabil- ity of graph neural networks real-world graph- structured data. We identify critical limitation of existing imputation methods based on feature propagation: they produce channels with nearly identical values within each channel, and these low-variance channels contribute very little to performance in graph learning tasks. over- come this issue, we introduce synthetic features that target the root cause of low-variance chan- nel production, thereby increasing variance in these channels. By preventing propagation-basen imputation methods from generating meaning- less feature values shared across all nodes, our synthetic feature propagation scheme mitigates significant performance degradation, even under extreme missing rates. Extensive experiments demonstrate the effectiveness of our approach across various graph learning tasks with missing features, ranging from low to extremely high miss- ing rates. Additionally, we provide both empirical evidence and theoretical proof to validate the low- variance problem. The source code is available https: / giggtut....... com/ daehouml fisf.
task termed graph learning task
Recently, propagation-based imputation methods (Rossi et al., 2022; Um et al., 2023; 2024; 2025), which im- pute missing features by diffusing observed features along edges in a channel-wise manner, have shown promising results. The diffused features, derived from observed features, provide sufficient information for GNNs per- form downstream graph learning tasks (Um al., 2023). The propagation-based methods offer two key advantages over conventional neural network-based imputation meth- ods (Monti et al., 2017; Chen et al., 2020): superior perfor- mance and fast imputation without learnable parameters.
In this paper, we reveal an inherent limitation of the propagation-bused methods: when all observed feature val- ues within a channel are nearly identical, the diffusion pro- cess fills all missing features in the channel with values that are likewise nearly identical. We refer to such chan- nels, where the feature values are nearly identical across nodes (i.e., low-variance), as low-variance channels. As illustrated in Figure 1a, we observe that the majority of channels in the outputs of state-of-the-art propagation-based methods (Rossi et al., 2022; Um et al., 2023) tend to be low-variance channels. Furthermore, we provide theoreti- cal proof that propagation variance channel when the observed features within chan- nel have identical values. Due to their nearly identical values across nodes, variinriecce channels contribute minimally to graph learning tasks that require distinct representations of nodes or node pairs, as demonstrated in Figure 1b.
1. Introduction
Graph neural networks (GNNs) have achieved significant success in graph learning tasks such as node classifica- tion (Kipf & Welling, 2016a; Veličković et al., 2017) and link prediction (Kipf & Welling, 2016b; Salha al., 2019). Since wide range of data contain entities with relations, these data can be represented in graphs and many problems are formulated as graph learning tasks (Wu et al., 2022; Liao et al., 2021). However, real-world graph-structured data of-
methods produce a zero-
'AI Center, Samsung Electronics *Computer Engineering, Dankook University 'Department of Electrical and Computer Engi- necring, Texas A&M University *KAIST" University of Michigan. Correspondence to: Dacho Um <dacho.ume samsung.com>>
To address the aforementioned low-variance channel prob- lem, we propose a new propagation-baset imputation scheme called Feature Imputation with Synthetic Features (FISF). Specifically, FISF consists of two diffusion stages.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Propagate and Inject: Revisiting Propagation-Ban -ased Feature Imputation for Graphs with Partially Observed Features
Accuracy on semi-supervised node classification
83
chumnels
# channels
# channels
# channels
79
5000
3000
3000
3000
2000
2000
2000
75
1000
1000
1000
1000
71
0.1 0.2
0.3 0.4 0.5 0.5 0.7 0.8 0.9 0.99
"19"
var
10 "1""""""""""
Channel removal from the lowest variance Channel removal from the highest variance
Original Features
FP (Rossi et al., 2022)
PCFI (Um et al. 2023)
FISF (Ours)
(a)
(b)
Figure 1. (a) Distributions of variance for each feature channel. The distributions for imputation methods are calculated from imputed matrices for the CiteSeer dataset with 99.5% missing features. While existing propagation- based imputation methods (FP and PCFI) produce outputs with numerous low-variance channels (outlined in red), our FISF effectively addresses the low-variance problem. (b) Accuracy (%) on semi-super node classification tasks while progressively excluding channels from the original feature matrix. The accuracy remains stable despite an increasing proportion of channels being removed in ascending order of variance (blue line). However, removing channels starting from the highest variance results in significant performance degradation.
First, to identify low-variance channels, FISF imputes meth-
(i) GNN Architecture. Several methods propose new GNN architectures to perform learning tasks on graphs with miss- ing features. GCN for missing features (GCNMF) (Taguchi et al., 2021) combines a GCN (Kipf & Welling, 2016a) layer with a Gaussian mixture model that represents missing fea- tures. (Jiang & Zhang, 2020) develops a message passing layer that aggregates only known features. Graph feature neural network (GRAFENNE) (Gupta et al., 2023) consists of three-phase message- paaasggg layers to address heteroge- neous and dynamic features. However, these methods, due to their specially designed layers, cannot take full advantage of off sffflf GNN models.
missing features using existing propagation-base ods (Rossi et al., 2022: Um et al., 2023). In each identified low-variance channel, FISF removes all the imputed fea- tures and generates synthetic feature by injecting random noise into randomly selected node. Finally, FISF diffuses both the observed and synthetic features to produce the final imputed features. Unlike existing propagation-bast based algo- rithms, FISF employs a novel distance encoding scheme to spread synthetic features widely, effectively increasing channel variance. We verify that FISF effectively resolves the low-variance problem, shown in Figure 1a, enabling GNNs to achieve remarkable performance gains in down- stream graph learning tasks.
(ii) Reconstruction. Reconstruction-baase methods train models by minimizing the reconstruction error between ob- served features and their reconstructed values. Recurrent Multi-Graph CNN (RMGCNN) leverages recurrent neural networks to complete a feature matrix (Monti et al., 2017). -at--rrrrrbuuttttaaffreeee (SAT) (Chen et al., 2020) models the joint distribution of graph structures and node features. Max-entropy graph autoencoder (MEGAE) (Gao et al., 2023) maximizes the entropy of latent features in autoencoders alleviate the spectral concentration problem. While these methods aim to accurately reconstruct miss- ing features, achieving accurate reconstructed features does not necessarily guarantee high performance in downstream tasks (Um et al., 2023).
In summary, our key contributions We identify and analyze a phenomenon where exist- ing propagation-based imputation methods produce low- variance channels in their outputs, supported by both em- pirical and theoretical evidence. 2) We propose FISF, a novel propagation- based imputation method that addresses the issue of low- variance channels by leveraging synthetic features. To the best of our knowledge, this is the first work to employ synthetic features for imputation. 3) Through extensive experiments, we demonstrate that FISF effectively eliminates low-variance channels in output matrices, re- sulting in significant performance improvements on both sumi-super node classification and link prediction tasks under various missing feature settings.
follows: 1)
(iii) Propagation. In this paper, propagation based im- putation refers to an approach that imputes missing fea- tures by diffusing known features without trainable param- eters. Propagation-
2. Related Work
imputation is based on feature homophily, the tendency that features of connected nodes are often similar on a graph. While preserving observed fea- tures, missing features are updated by aggregating features from neighboring nodes. Feature propagation (FP) (Rossi et al., 2022) is pioneering work that iteratively propagates known features in a channel-wise manner and fills in miss-
2.1. Learning on Graphs with Missing Features
Dealing with missing data has long been an active re- search field in machine learning (Allison, 2009; Troyan- skaya et al., 2001). Methods for handling missing data in graph-structured data can be categorized into three groups.
2

---

Propagate and Inject: Revisiting Propagation- -aasea Feature Imputation for Graphs with Partially Observed Features
ing features. Preudb-oonfidence-baaeed feature imputation (PCFI) (Um al., 2023) calculates pseudo-confidence of each feature value and leverages pseudo-confidence as the importance of feature values during propagation. These propagation-bart techniques have been favored due to their effectiveness under high rates of missing features. However, they often cause missing features to become overly similar when a small number of observed features are highly alike, leading to minimal feature differences between nodes. Our approach mitigates this issue by encouraging greater fea- ture distinctiveness between nodes, thereby enhancing the performance of downstream GNNs in graph learning tasks,
(a) and x!") are column vectors for the a-th where x(*), x
channel. A (a) and A represent the same graph structure although the node order of A is rearranged from A. We use B.. to denote the z-th column of matrix B.
Problem definition. We address the problem of graph learning tasks with missing features, where our goal is to minimize performance degradation in downstream learning tasks despite high rates of missing features. Formally, graph learning tasks with missing features can be expressed as
Y = f((x J
(2)
where Y represents the predicted output for given task and is the target function be learned. We decompose into two steps, expressed as f ge o h, where h is feature imputation scheme, and go is an off-the-shelf GNN model that operates on the full feature matrix obtained via h.
2.2. Distance Encoding
To widely spread synthetic features, we assign varying im- portance to each feature based on distance encoding. Dis- tance encoding is a technique that utilizes graph-distance measures (e.g., shortest path distance, generalized PageRank scores (Li et al., 2019)) calculated between a node and a des- ignated node set. (You et al., 2019) proposes an aggregation scheme using the computed distance of a given node from sampled anchor node sets. (Zhang& & Chen, 2018) and (Li et al., 2020) leverage encoded distance extra node features for link prediction. Position-aware graph neural network (P-GNN) (Zhang et al., 2021) unifies several techniques, including distance encoding, into a labeling trick.
4. Proposed Method
4.1. Overview of FISF
We present an imputation scheme called feature imputation with synthetic features (FISF), designed to minimize perfor- mance degradation in graph learning tasks despite high rates of missing features. Figure 2 provides an overview of FISE, which consists of two diffusion stages: pre-diffusion and dif- fusion with synthetic features. Using pre-imputed feature matrix obtained through pre-diffusion (see Section 4.2), we calculate the variance of features for each channel. We then create a synthetic feature in each low-variance channel (see Section 4.3). In the second diffusion stage, these synthetic features are widely propagated update the features in low- variance channels (see Section 4.4). This stage produces the final output feature matrix of FISE, which is subsequently fed into go for downstream tasks.
3. Notation and Problem Definition
Notation. An undirected connected graph can be repre- sented as G = EV,E, A) where V = {VI,..., UN } is the set of N nodes, E is the edge set, and A E 10,1)NxN is an adjacency matrix. X = [ E XF denotes a node feature matrix where F is the number of feature channels and Fi,a represents the a-th channel feature value of ug.
Let d((),, 1,|A) be the shortest path distance between the i-th node and the j-th node on G with A. Then, we define a function (-)r()) as dses(ta ")",,) A) = ming, Ev-d(u;, A) where V' C V. That is, we use dees (v; A) to denote the shortest path distance between the i-th node and its nearest node in node set V S V on G with A.
4.2. Pre-diffusion
We adopt channel-wise inter-node diffusion in PCFI (Um et al., 2023) as the pre-diffusion stage, while FP (Rossi et al., 2022) can also be used for pre-diffusion (see Appendix 5.5). For notational convenience, we temporarily rearrange all nodes in a channel-wise manner as described in Section 3. Specifically, for the a-th channel, we reorder the nodes ac-
Partially known (observed) features mean that X has miss- ing elements. Vi denotes a set of nodes whose a-th chan- nel feature values are known. ve denotes set of nodes whose a-th channel feature values are unknown (missing)
cording to Va(() and V!(") i.e., (()) and A (a) are created by reordering A. After the diffusion is completed, we restore the node ordering to its original state.
(i.e., >(()= = V v We refer to vi(e) and ()(() as souree nodes and missing nodes, respectively. By rearranging the whole nodes based whether the feature value is known or
The channel-wise inter-node diffusion calculates and uti- lizes pseudo-confidence (PC) (Um et al., 2023), which acts as the importance of each feature value during the diffu- sion. We use S.,, to denote the shortest path distance be- tween the i-th node and its nearest source node for the a-th channel, ie.,, S., = dser(U;) (vrr(u (1) pre-imputed feature matrix via pre-diffusion. Then, fol- lowing (Um et al., 2023), PC (Eta) of hz,a is assigned by
not for each channel, the whole features and the adjacency
matrix for the a-th channel can be written as
A())). We let X be a
(0)
x
(4)
A (a)
BR A
(a) A
A
ku
(a)
Xa
(1)
uk
A
3

---

Propagate and Inject: Revisiting Propagation- Basood Feature Imputation for Graphs with Partially Observed Features
low-variance channels
?
?
Pre-diffusion
Generate
Diffusion with synthetic features
XT
XT
synthetic features
X
Figure 2. A brief overview of feature imputation with synthetic features (FISF). First, pre-diffusion constructs a full feature matrix X by imputing missing features via channel-wise diffusion. Then, for each low-variance channel in X, we inject one synthetic feature into a randomly chosen node from nodes with missing features. Finally, diffusion with synthetic features produces X which is a final output of FISF. X is fed to downstream GNN which performs given graph learning task.
L.o = a (0 < a < 1) where a hyperparameter. Thereafter, the transition matrix for the pre-diffusion is con- structed using weighted adjacency matrix ((a) RNXN defined as
(see Appendix A). Based on the proof that initial values for x do not affect the steady state, we initialize x with zeros (i.e., O.). We use x-(1) (K) with large enough K to approximate the steady state.
We rearrange {x(*) (K) back to their original order to reorder the nodes considering synthetic features in the second diffusion stage. By stacking the originally ordered vectors in (x(*) (K) along the channels, we obtain pre-imputed feature matrix X, which is the output of the pre-diffusion stage.
W (a)
if A = if A = 0,
(3)
where W (1)
f.j represents the message passing strength from the j-th node to the i-th node during the pre-diffusion pro- cess. For a row-stochastic transition matrix, we normalize W(a) to W (D) (a)) where (()) is diagonal matrix with diagonal entries D( = =E, W.j. Then, to preserve the known features x (a) during the pre-diftusion, replace the first (b( rows in W with one-hot vectors
4.3. Synthetic Feature Generation
When all given known features in the a-th channel (i.e., ele- ments in x({ have the same value c, lim x( (t) becomes
t-000
a vector where all elements are e (see Appendix B). We refer to a channel with the same or nearly the same feature values as a low-variance channel. This low-variance channel does not contribute to distinguishing nodes. In semi-supervised node classification, distinctive node representations sential for classifying nodes into multiple classes. Similarly, in link prediction, uniform representations across nodes re- sult in identical representations for node pairs. To address this, we aim to make imputed features in such channels more distinctive across nodes by injecting synthetic feature that acts as known feature.
indicating y!() As a result of the replacement, we attain the pre-diffusion transition matrix W(a) expressed by
IRk w (a)
Jau (a)
W(a)
(4)
w
where I& E 1 (M is an identity matrix and Opu E
[x((=)) is matrix.
The pre-diffusion is implemented by iterative propagation steps using (o)) as
We first identify low-variance channels inject synthetic features. We calculate the variance of X. (i.e., pre-imputed feature values in the a-th channel) for all E {l..... F}. (5) Then 5% of channels are selected in order of lowest to high- est variance, where r is hyperparameter between 0 and 100. F, denotes the set of low-variance channel indices. For each channel in F,, we randomly select one node with a missing feature inject a synthetic feature. For selected node (6) us in a channel b E Fr, we inject synthetic feature with randomly sampled value x! from uniform distribution
x())() (t) wia) 1), t= 1,...,,.. KK;
(a) (0) = xx
O,,
where (() is imputed feature vector after propaga- tion steps and O,, a zero vector with length of [ After K propagation steps, we obtain x()) As K - oo, the recursion converges and x(a) <(a(()) reaches a steady state

---

Propagate and Inject: Revisiting Propagation-Bal -aaesttdon-Bseed Feature Imputation for Graphs with Partially Observed Features
on [0, 1]. Consequently, [Fy] number of synthetic feature (b) xx=) JoE,, is combined with the result of pre-diffusion (X) for the second diffusion stage called diffusion with synthetic features.
from the whole known nodes. That is, Ei is defined by fi, .8 < 3 < 1) where B is a hyperpa- rameter. As U, is positioned closer to vs 5f, increases. We also use usual PC (57,)) based on distances from the whole known nodes Vi containing us We calculate S7,6 = (b A (b)) and obtain PC calculated by E₁ = a < < 1). While both Σ., and Ei, play role as the importance of each feature value, Ei,6 is de- termined by the distance from only synthetic node w/th) in contrast to Er considering the distances from whole known nodes k. Using the PCs, we define a weighted adjacency matrix ((a) E - by
values are injected and {(vg))
4.4. Diffusion with Synthetic Features
Diffusion with synthetic features (DSF) produces X [ E N which is final output of FISE. DSF receives X from the pre-diffusion and {(vs)) (b) xxd)) HEF,, Then DSF updates X by replacing features in the low-variance chan- nels (i.e., , for all 6 E [Fy). The purpose of DSF is to increase the variance of low-variance channels by using synthetic features.
DSF treats a synthetic feature x as known features xx during diffusion. Then the updated known node set becomes 1 = V U (v!"),
Sip Ei,0
if A (b) =1 if if (b) 0.
}. Thus the updated unknown node set becomes (0() = -v(0) {o."). That is, e is moved from v:(h) to 1lt Similar to pre-diffusion, we first temporarily reorder all the nodes in the order of y(t and w!l)) By reordering, features and the adjacency matrix in the b-th channel in Ft can be expressed as
M 1
=
(7)
[ is the strength of message passing from the j-th node to the i-th node in the DSF.
(b)
The term Ej,// strengthens a message passing from a high-PC feature to a low-PC feature as in the pre-diffusion (see Eq. 3). However, different from the pre-diffusion, the synthetic feature of vs is considered as one of the nodes in 1 Thus the influence of the synthetic feature is very weak compared to that of the many observed similar features. To widely spread the synthetic feature, we introduce the term /g,p/EE,, which strengthens a message passing from a feature of a node near v:(0) to a feature of a node far from (b))) This term makes the synthetic feature spread widely compared to observed features. The design goals of the two terms naturally combine through multiplication in Eq. 7. Ei is 1 for both v E k and x. However, Ei is 1 for x while it is at most 8 for E Va Therefore, in the second stage diffusion, the synthetic feature has a greater influence than observed features.
(b)
A (b)
A
(b)
x (6)
(b) =
k-
(6)
(b)
(b)
k-
ura
where ( and
( are column vectors and x contains
x!") The length of (b) and (+) are | 11 and |100 |-,
respectively.
The preparations above are the same as the pre-diftusion,
except for assuming x (b) as a known feature. However, sim- ply diffusing features of v as pre-diffusion results in x.") influencing only its surroundings. This is because not only x. but also known features with nearly the same values diffuse. For example, if a given graph has 10, 000 nodes and 90% features are missing in the b-th channel, there exist 1, 000 known features with nearly the same feature values in the channel. Known features spread to their surrounding features through diffusion and make the surrounding fea- tures be similar their own value. Thus, it is hard for x!") to exert a wide influence across nodes. This issue hinders the channel from deviating from low variance since most of the features become nearly the same value.
(())
To construct transition matrix, we prepare a row-stochastic
matrix by normalizing ( to (d) (b)
where (* is a diagonal matrix with D((0)
i6 = Σ, M
(+(*) rows in M with one-hot (b)
Then, we replace the first
A- vectors representing 4- to preserve x including x By
To overcome the issue, we design DSF to give more influ- ence to synthetic features than that of known features. For the wide diffusion of (b) we leverage the shortest path distance from u We measure the shortest path distance from ( to all nodes in V. Formally, we use S to denote d(e, 2. (b) A (b) and measure S for all &; V.
the replacement, we obtain a DSF transition matrix ( as follows:
M =
L M k k-
Og-m (b) ="==
(8)
M
Then the PC Ef. of ž. is computed based on the short-
where I E R RD |x
is an identity matrix and
est path distance from only the synthetic node u2 not
(b)
OR E RRP( [
is a zero matrix.
5

---

Propagate and Inject: Revisiting Propagation-Basn Based Feature Imputation for Graphs with Partially Observed Features
Cora
CiteSeeT
PubMed
83
80
+0.34%
+2.12%
+0.27%
5..2%%
+6.10%
68
72
+0.23%
+5.48% +5.48%...443%
+5.3%%
78
77
+0.16%
+0.50%
+0.28%
+3.28%
+3.92%
76
75
74
60
74
Structural missing
0.995
0.999
0.995
0.999
0.995 0.999
Photo
Computers
OGBN-Arxiv
98
+0.37%
+0.35%
87
+0.13%
73
+0.25%
+0.69%
+0.20%
89
0083% %
83
+0.50%
71
2 2.8%%
1 1.66%
+0.48%
2.38%
86
79
1..99%
89
81
0.3
0.5
0.9
0.995
0.999
0
0.3
0.5
0.9
0.995
0.999
0.3
0.5
0.9
0.995 0.999
Cora
CiteSeer
PubMed
83
72
78
1..6% +2.84%
+0.12%
+0.07%
0.22%% 0.35%% +0.84% 255
+0.76%
81
+0.1%
1..2%
68
77
+0.12%
+0.39%
0.344% 2.78%
76
79
75
77
60
74
0.5
0.9
0.985
0.999
0.995
0.999
0.996 0.999
Uniform missing
Photo
Computers
OGBN-Arxiv
93
73
+0. 1414
+0.39%
+0.08%....14%
90
+0.28%
25%
0.96%
84
+0.38%
+0.13%
0.39%
71
+013%
+0.79%
1.4%
+0.87%
87
81
89
84
0.3
0.5
0.9
0.995
0.989
0.3
0.5
0.9
0.995
0.999
0.3
0.5
0.9
0.995
0.999
LP
O
GCNMF O GRAFENNE
& MEGAE O
FP
PCFI
FISF (ours)
Figure 3. Accuracy (%) on supi-supe node classification tasks under structural-missing and uniform- unfform-missing settings with various Tm. Figures highlighted in red indicate performance improvements over the most competitive baseline across each setting, Cases where accuracy cannot be measured due to
errors are not included.
We define diffusion with synthetic features (DSF) by
columns is X, a final output of FISF. X is fed to a GNN to perform a given task. The detailed steps of the proposed FISF algorithm are provided in Algorithm I in Appendix F,
x (b) (t) (a)
x (b) (t - 1), t= I,... K;
(b) k-
(9)
x (0)
Oz-
5. Experiments
where (1) denotes an imputed feature vector after prop- agation steps and O., denotes zero vector of the same length as | I. As K + xo, (K) converges (see the proof in Appendix A). With sufficiently large K, we approximate the steady state lim (t) to x (K). We t- perform DSF in the b-th channel for all b F, and obtain (K)) Since vectors in (x(() (K))EE, have dif- ferent ordering from the original one, we restore ordering of all the vectors according to the original order. To construct X E N we prepare X E IR XxF from the pre-diffusion and replace X., for all b E F, with the corresponding vec- tor in (x (K))BER, The feature matrix with the replaced
We perform comparative evaluation of FISF against state- of-the-art methods on two main graph learning tasks: semi- supervised node classification and link prediction.
5.1. Datasets and Baselines
Datasets. We conduct experiments six benchmark datasets: Cora (McCallum et al., 2000), CiteSeer (Giles et al., 1998), PubMed (Sen et al., 2008), OGBN- Arxiv (Hu et al., 2020)), Amazon-Phoo Computers (Shchur et al., 2018). Detailed information on the datasets is provided in Appendix E.
and Amazon-
Baselines. We compare FISF with LP (Zhuf & Ghahra-
6

---

Propagate and Inject: Revisiting Propagation- Bassed Feature Imputation for Graphs with Partially Observed Features
Table 1. Performance on semi-supervised node classification tasks at Tm = 0.995, measured by accuracy (%). Standard
deviation errors are given. OOM denotes an out- out-of-memory error.
Structural missing
Method
Cora
CITESEER
PURMED
PHOTO
COMPUTERS
OGBN-ARXIV
Full features
81.87 = 1.59
69.32 + 0.57
77.45 2.17
91.69 + 0.78
86.19 0.78
72.30 + 0.10
LP
71.1= 1.79
05.42 4: 1.80
71667 + 4.91
82.27 + 2.72
76.01 + 1.84
67.56 + 0.00
GONMF
31.33 = 2.73
24.84 + 2.44
40.48 + 0.53
25.60 0.17
37.21 0.08
9.00 6.27
GRAFENNE
20.2 10.98
17.38 + 2.94
33.12 + 2.43
21.10 + 17.39
16.31 + 11.84
13.66 12:23
MEGAE
4.76
32.91 + 1.08
00M
68,90 + 9.16
42.37 + 5.03
OOM
FP
71.86 0 2.82
68.61
+ 1.74
71.96 + 3.06
85.42 + 3.16
76.62 + 1.94
68.03 + 0.52
PCFI
74.62 = 1.78
66.06 + 3:26
74.47 +: 2.54
87.49 + 1.50
79.02 + 1.22
68.78 + 0.25
FISF
79.29 + 1.72
69.68 + 2.47
76.90 + 1.50
88.22 + 0.79
79.40 + 1.11
69.92 0.17
Uniform missing
Method
CORA
CITESEER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Full features
81.87 + 1.59
69.32 + 0.57
77.45 + 2.17
91.69 + 0.78
86.19 0.78
72.30 + 0.10
LP
74,54 + 1.79
65.42 + 1.80
71.67 = 4.91
82.27
2.72
76.01 1.84
67.56 = 0.00
GCNMF
34.01 + 8.08
29.71 + 5.12
40.08 + 0.45
25.59 + 0.16
97.20 0.08
5.86 + 0.00
GRAFENNE
20.55 = 13.65
19.32
31.75 -: 4.26
29.96 + 20.92
21.74 15.94
15.52 + 11.70
MEGAE
46.13 +: 9.06
34.32 + 7.65
00M
55.31 # 10.37
41.02 = 4.05
00M
FP
77.58 +: 1.98
68.55
+: 2.33
72.62 4.18
87.50 1.49
80.75 0.70
68.82 + 0.07
PCHI
78.82 +-
68.94
1.95
76.28 2.52
88.00 1.41
81.80 0.71
69.26 0.17
FISF
79.09 +: 1.73 69.52
1.81
77.53
1.28
88.32 1.37
82 12 0.51
69.81 + 0.16
mani'H, 2002) and five state-of-the-ar arr methods for graph learning tasks with missing features. (1) LP that does not use any feature propagates partially given labels for semi- supervised node classification. (2) GCNMF (Taguchi et al., 2021) and (3) GRAFENNE (Gupta et al., 2023) are GNN architecture- bassed methods. (4) MEGAE (Gao et al., 2023) is a reconstruction--ased method. (5) FP (Rossi et al., 2022) and (6) PCFI (Um et al., 2023) is propagation- meth- ods. Since imputation methods (including MEGAE, FP, PCFL, and FISF) combine with GNNs to perform down- stream tasks, we commonly utilize vanilla GCN (Kipf & Welling, 201 models for semi-supervised node classi- fication. In link prediction, we commonly utilize graph auto-encoder (GAE) models for the imputation methods.
For semi-supervised node classification tasks, we randomly create five different training/validationnees node splits for all the datasets except for OGBN-Arxiv which has fixed split according to the specific criteria. For link predic- tion tasks, we also randomly create five different train- ing/validationntest edge splits of each dataset. OGBN-Arxiv is excluded from the link prediction tasks due to out-of- memory errors. Grid search is employed to tune a, B, and 7 the three hyperparameters of FISF, a and 3 are searched within {0.1, 0.3, 0.5, 0.7, 0.9}. y is chosen from (10, 30, 50, 70, 903. For all the methods including FISF, we tune hyperparameters based on validation sets. We utilize the publicly released code for all the baselines. Further im- plementation details including dataset splits, training details, and baseline implementations are provided in Appendix E.
5.2. Experimental Setup
5.3. Semi-supervised Node Classification Results
We follow the missing setting in (Um et al., 2023). To evaluate models on graphs containing missing features, we remove a fixed rate (e.g., 90%) of features in the datasets. missing rate denoted as I' represents the rate of feature removal. We fill the positions where features are removed with NaN values. We remove features in the following two ways: structural missing and uniform missing. First, in the case of structural missing, we randomly select nodes at a ratio of I' from entire nodes and remove all the features of the selected nodes. Second, uniform missing removes randomly selected feature values with a ratio of I'm from a feature matrix X. We report average performance (e.g., accuracy, ROC AUC, and AP) after five runs of experiments under a fixed setting. Therefore, for each missing way, we randomly generate five different binary masks with the same size of X for each dataset. These masks indicate the locations in X where features are missing.
To investigate how T.. affects semi-supervised node classifi- cation accuracy, we conduct experiments by increasing I'm while keeping all other settings fixed. Figure 3 demonstrates accuracy under structural-missing and uniform-missing set- tings with varying Im- The accuracy of L.P remains con- sistent since LP does not utilize features. For all methods except for LP, the accuracy tends to decrease as I'm increases. While propagation -based imputation methods outperform the other methods, FP and PCFI suffer performance degra- dation I' increases. However, FISF shows robust per- formance despite high I'm regardless of the datasets. Note that FISF using only 0. 0.1% of features (i.e., I'm = 0.999) performs similarly to or even outperforms FISF with full features on Cora, CiteSeer, and PubMed. Furthermore, FISF consistently demonstrates superiority across various missing rates (rm), including low T'm regardless of the missing pat-
7

---

Propagate and Inject: Revisiting Propagation-Ban -aaagddtio--Bseed Feature Imputation for Graphs with Partially Observed Features
Table 2. Performance on link prediction tasks at I'm- 0.995, measured by ROC AUC score (%), Standard deviation errors are given. The best result is highlighted in bold and underlined, while the second- best result is highlighted only in bold. OOM denotes an out-of- -e--orr error.
Structural missing
Method
CORA
CITESEER
PUBMED
PHOTO
COMPLTERS
Full features
92.20 = 0.96
90.55 + 1.36
96.41 + 0.25
95.70 + 0.32
93.71 + 0.65
GCNMF
67.44 = 0,45
68.34 1.79
87.20 20 0.28
81.00 0.25
82.92 + 0.19
GRAFENNE
53.79 + 5.26
62.96 + 13.82
60.11 6.10
66.44 + 1.74
67.23 + 1.71
MEGAR
67.13 + 0.75
09.34 + 2.46
0OM
86.53 + 1.97
84.89 + 1.77
FP
83.85 + 1.32
79.83 + 2.18
78.54 + 1.13
94.25 + 0.58
91.27 + 0.71
PCFI
86.75 0.84
79.38 1.81
82.49 0.82
96.65 0.25
94.54 + 0.37
FISF
87.26 1: 1.44
84.12 1 1.17
83.19 +: 0.78
95.86 + 0.21
94.70 1 0.30
FISF+NIP
87.16 1: 1.46
84.20
1.70
83.28 0.42
96.35 1 0.18
95.29 1 0.32
Uniform missing
Method
CORA
CITESEER
PURMED
PHOтO
COMPUTERS
Full features
92.20 + 0.96
90.35 + 1.36
96.41 + 0.25
95.70 0.32
93.71 + 0.65
GCNMF
63.46 = 1.04
63.50 + 3.40
81.73 + 3.13
80.98 0.17
82.95 + 0.11
GRAFENNE
68.49 = 17.00
61.38 + 13.53
65.74 + 11.32
68.53 = 6.57
70.16 + 4.12
MEGAR
65.86 + 1.22
62.21 + 3.18
00M
84.25 1.35
84.95 + 2.20
FP
86.79 + 1.36
81.55 + 2.30
76.87 + 2.89
95.96 0.17
94.10 + 0.33
PCFI
87.35 + 1.28
82.33 + 1.88
84.68 + 0.75
97.05 + 0.16
95.62 + 0.24
FISE
87.44 1 0.80
83. $3.4511
1: 2.53
85.33
0.47
96.64 0.18
95.13 0.35
FISF+NIP
87.70 1 0.77
82.53 1 1.94
85.32 i 0.48
96.67 1 0.21
96 09 0.24
terns. The performance gain obtained with FISF diminishes as the missing rate decreases. This is natural since a smaller I'm means fewer missing features to impute, making it diffi cult to achieve significant improvement solely through the superiority of the imputation method. Nevertheless, FISF consistently shows its effectiveness at even low T'-
10 settings. Even in the remaining three settings, FISF+NIP still demonstrates the second-best scores which are com- parable with the best scores. That is, FISF and FISF+NIP achieve strong performance across all five datasets regard- less of missing ways. As highlighted scores in Table 2 shows, FISF demonstrates its effectiveness on link predic- tion tasks with missing features.
We then investigate how semi-supervised node classification accuracy varies depending on the missing ways (structural and uniform missing) at the same I'm 0.995. Table shows the results. While most nodes have some observed features in uniform-missing settings, (1 - rm) of nodes do not have observed features at all in structural-missing settings. Therefore, the performance of methods tends to be better in uniform- uniform-missing settings than in menettral-missing settings. For both missing ways, FISF outperforms the state- of-the-art methods across all the datasets. Results for the case where the downstream GNN is GIN are provided in Table 33 in Appendix G.
5.5. Complexity Analysis
Here, we discuss the complexity of FISF, which involves two diffusion stages: pre-diffusion and diffusion with syn- thetic features. FISF takes O + (1 + N²) time under miising settings. Under uniform-missing settings, FISF takes [(E) + (1 (1+ N2 time. We ob- serve that the majority of the computation time in FISF is consumed by employing Dijkstra's 's algorithm to calculate the shortest path distance for each channel. The time com- plexity of Dijkstra's 's algorithm is O(N²). In pre-diffusion under structural missing settings, Dijkstra's algorithm is once utilized since nodes with observed features are equal across all the channels. However, under uniform-missing settings, the time complexity of pre-diffusion increases to ((N2 F)), considering the use of Dijkstra's 's algorithm across all channels.
5.4. Link Prediction Results
Table 2 summarizes the ROC AUC score link predic- tion tasks at r.. = 0.995. (The AP comparison results are presented in Appendix G.) NIP denotes node-wise inter- channel propagation included in PCFI (Um et al., 2023), which refines an output matrix from channel-wise diffusion. Since NIP is effective in link prediction tasks, we demon- strate the ROC AUC score of FISF and FISF+NIP (FISF fol- lowed by NIP). FISF and FISF+NIP achieve state-of-the-arr performance in three and four settings, respectively, out of
We can utilize not only channel-wise inter-node diffusion in PCFI but also FP for pre-diffusion. We introduce a variant called FastFISF, which utilizes FP for pre-diffusion, offer- ing efficiency by bypassing the calculation of the shortest path distance. Table 3 demonstrates the results of FastF.
8

---

Propagate and Inject: Revisiting Propagation -Based Feature Imputation for Graphs with Partially Observed Features
Table 3. Performance on semi-supervised node classification tasks at t'm 0.995, measured by accuracy (%),
Structural missing
Method
CoRA
CITESTER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Average
FISF
79.29 + 1.72
69.68 + 2,17
76.90 + 1.50
88.22 + 0.79
79.40 + 1.11
69.92 + 0.17
77.24 77.04
FastFISF
78.94 + 1.92
69.42 + 1.44
77.14 + 0.94
88. 10 + 1.38
79.09 + 1.42
69.53 + 0.21
Uniform missing
Method
CORA
CITESBER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Average
FISF
79.09 + 1.73
69.52 + 1.81
77.53 + 1.28
88.32 + 1.37
82.12 + 0.51
69.81 + 0.16
77.73
FaStFISF
79.29 + 1.84
69.39 + 1.57
77.41 + 1.77
88.03 + 1.46
81.70 + 0.54
69.45 + +.18
77.55
Table 4. Running time of methods. OOM denotes out-of-
uniform-missing settings.
memory error.
5.6. Scalability of FISF
Missing way
structural
uniform
Method
CORA
PUBMED
CORA
PUBMED
In FISF, the bottleneck in terms of computation and memory lies in distance encoding, which requires O(N2. F) compu- tation and O(N2) memory usage. However, the core concept of FISF, adding synthetic features to low-variance channels and diffusing them, is not confined specific distance en- coding methods, enabling the development of scalable yet effective algorithms with minimal modifications. Here, we introduce a lighter version of FISF named ScalableFISF that utilizes FP instead of the distance encoding. FP decreases a computation complexity to O(E)) and is validated as a scal- able algorithm in (Rossi et al., 2022) through an experiment on graph with 225M nodes. Specifically, in ScalableFISF, we utilize FP for pre-diffusion and add syntheric features to low-variance channels. Then, by treating the synthetic features as observed features, we simply reapply FP in these low-variance channels, without distance encoding. Table 5 demonstrates performance on semi-supervised node clas- sification at r. = 0.995 under structural missing settings, measured in accuracy. The results show that ScalableFISF significantly enhances the performance of FP by addressing the low-variance problem. ScalableFISF exhibits decreases in performance compared to FISF, yet ScalableFISF shows reasonable performance and offers advantages in terms of complexity. Therefore, if PCFI reaches its scalability limit on extremely large graphs with high- nigh-dimensional features, ScalableFISF can be a good alternative.
GCNMF
10.3s
19.4s
9.87s
28.3s
GRAFENNE
47.9s
74.7s
51.1s
74.0s
MEGAE
1753s
00M
1801s
OOM
FP
2.36s
3.12s
2.25s
2.90s
PCFI
2.45s
3.23s
11.1s
34.1s
FastFISF
13.4s
34.6s
11.8s
42.5s
FISF
13.4s
34.8s
17.6s
78.2s
Table 5. Performance semi-superrised node classification
tasks at F' = 0.995, measured by accuracy (%).
Dataset
FP
ScalableFISF
FISF
CORA
71.86 + 2.82
78.25 1.38
79.29 + 1.72
CITESEER
58.61 = 1.74
68.52 + 1.82
69.68 + 17
PUBMED
71.96 + 3.06
74.40 + 2.64
76.90 + 1.50
PHOTO
85.42 3.16
86.98 : 1.80
88.22 + 0.79
COMPUTERS
76.62 = 1.94
78.08 = 1.18
79.40 + 111
OGBN- -GXIIAARIV
68.03 + 0.52
68.55
0.42
69.92 + 0.17
ISF compared to the original FISF on semi-supervised node classification tasks. For channels that are not low-variance channels, features obtained via pre-diffusion are maintained until the end of diffusion with synthetic features. There- fore, since PCFI outperforms FP in terms of performance in downstream tasks, FISF shows slightly better performance than FastFISF most cases. However, since the perfor- mance of FastFISF is comparable that of FISP, FastFISF can serve as rapid alternative to FISF without significant loss in performance.
To address the increasing time complexity in uniform- missing settings, we can employ FastFISF where the time complexity is O((E) + ?FN?) regardless of the missing way. Therefore, to address the increasing time complexity of FISF miisorn-missing settings, we can employ FastF- ISF, accompanied by only slight performance loss. Table 4 demonstrates the training time of methods. FP has the low- est training time among the methods. However, FISF brings great performance improvement compared to FP. For in- stance, in structural- achieves significant gains in node classification accuracy over FP, showing improvements of 7.43% and 4.94% on Cora and PubMed, respectively. We can further confirm that FastFISF significantly decreases the training time in
6. Conclusion
In this paper, we identify the problem of low-variance channels, critical limitation of existing propagation-based imputation methods. Building on this key discovery, we propose FISF for graph feature imputation. FISF effec- tively addresses the problem of low- channels by injecting synthetic features, improving performance in both semi cunii-spervieed node classification and link prediction tasks across various missing rates. We believe that our work will be widely applied to diverse real-world scenarios that in- volve graphs with missing features, as synthetic feature scheme is simple to use and consistently offers performance gains regardless of the missing rates.
setups with I'm = 0.995, FISF

---

Propagate and Inject: Revisiting Propagation-Ban BBssd Feature Imputation for Graphs with Partially Observed Features
Impact Statement
of the AAAI Conference on Artificial Intelligence, vol- ume 37, pp. 7651-7659, 2023.
The proposed method could be misused on graph-structured datasets containing missing private or personal data. We strongly advocate for its responsible use to ensure a positive societal impact, particularly in applications such health- care (Ramirez et al., 2020; Li et al., 2022), where graph neural networks are widely employed.
Gasteiger, J., Bojchevski. A., and Günnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: SaXKvv:8110009999 2018.
Giles, C. L.,, Bollacker, K. D., and Lawrence, S. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pp. 89-98, 1998.
References
Allison, P. D. Missing data. The SAGE handbook of quanti- tative methods in psychology, pp. 72-89, 2009.
Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discov- ery and data mining, pp. 855-864, 2016.
Asuncion, A., Newman, D., et al. Uei machine learning repository, 2007.
Berman, A. and Plemmons, R. J. Nonnegative matrices in the mathematical sciences. SIAM, 1994.
Gupta, S., Manchanda, S., Ranu, S., and Bedathur, J. Grafenne: Learning on graphs with heterogeneous and dynamic feature sets. In International Conference on Machine Learning, pp. 12165-12181. PMLR, 2023.
Chai, X., Tang, G., Wang, S., Lin, K., and Peng, R. Deep learning for irregularly and regularly missing 3-d data reconstruction. JEEE Transactions on Geoscience and Remote Sensing, 59())6224 6265, 2020.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 12-22333,, 2020.
Chen, X., Chen, S., Yao, J., Zheng, H., Zhang, Y., and Tsang, I. W. Learning on attribute-missing graphs. IEEE transactions on pattern analysis and machine intelligence, 44(2):740-757, 2020.
Jiang, B. and Zhang, Z. Incomplete graph representation and learning via partial graph neural networks. arXiv preprint arXiv:2003. 10/30, 2020.
Chung, R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Keriven, N. Not little, not too much: theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35:2268-220 2022.
Di Martino, A., Yan, C.-G., Li, Q., Denio, E., Castellanos, F. X.X., Alaerts, K., Anderson, J. S., Assaf, M., Bookheimer, S. Y., Dapretto, M., al. The autism brain imaging data exchange: towards large-scale evaluation of the intrinsic brain architecture in autism. Molecular psychiatry, 19(6): 659-667, 2014.
Kim, Y.J. and Chi, M. Temporal belief memory: Imput- ing missing data during rnn training. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018), 2018
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. In International Confer- ence on Learning Representations, 2022. URL https: / //openreview, net / forum? i --wwddTTTTnnm j.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv:/609.00 metp:0090900000 2016a.
Dwivedi, V. Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43): 2023.
Kipf, T. N. and Welling, M. Variational graph auto-encoders. arXiv preprint 16 1.00300 2016b.
Fey, M. and Lenssen, Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 2019.
Klicpera, J., Weißenbergerr S., and Günnemann, Diffusion improves graph learning. arXiv preprint arXiv: 1911.05485 2019.
Gao, Z., Niu, Y., Cheng, J., Tang, J., Li, L., Xu, T., Zhao, P., Tsung, F., and Li, J. Handling missing data via max- entropy regularized graph autoencoder. Proceedings
Li, M. M., Huang, K., and Zitnik, M. Graph representation learning in biomedicine and healthcare. Nature Biomedi- cal Engineering, 6(12):1353-136) 2022.
10

---

Propagate and Inject: Revisiting Propagation-Bae -aaesa Feature Imputation for Graphs with Partially Observed Features
Li, P., Chien, I., and Milenkovic, O. Optimizing general- ized pagerank methods for seed-expansion community detection. Advances in Neural Information Processing Systems, 32, 2019.
with missing node features. In Learning on Graphs Con- ference, pp. 11-1. PMLR, 2022.
Saha, A., Harowicz, M. R., Grimm, L. Kim, C. Ghate, S. V., Walsh, R., and Mazurowski, M. A. A machine learning approach to radiogenomics of breast cancer: study of 922 subjects and 529 dce-mri features. British journal of cancer, (1((4)5088-51 2018.
Li, P., Wang, Y. Wang, H., and Leskovee, Distance en- coding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
Salha, G., Limmios, S., Hennequin, R., Tran, V.-.., and Vazirgiannis, M. Gravity-inspired graph autoencoders for directed link prediction. In Proceedings of the 28th ACM international conference on information and knowledge management, pp. 589-598, 2019.
Liao, W., Bak-Jensen, B., Pillai, J. R., Wang. Y., and Wang, Y. A review of graph neural networks and their appli- cations in power systems. Journal of Modern Power Systems and Clean Energy, (0(2):345-36) 2021.
Luan, S., Zhao, M., Chang, X.-W., and Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. Advances in neural information processing systems, 32, 2019.
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi Eliassi-Rdd, T. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1.05868, 2018.
Mattei, P.-.. and Frellsen, J. Miwae: Deep generative modelling and imputation of incomplete data sets. In International conference machine learning, pp. 4413- 4423. PMLR, 2019.
Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):19291158, 2014.
McCallum, A. K., Nigam, K., Rennie, J., and Seymore, K.
Automating the construction of internet portals with ma- chine learning. Information Retrieval, 3:127-163, 2000.
Taguchi, H., Liu, X., and Murata, T. Graph convolutional
networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021.
Monti, F., Bronstein, M., and Bresson, X. Geometric matrix completion with recurrent multi-graph neural networks. Advances in neural information processing systems, 30, 2017.
Troyanskaya, O., Cantor, M., Sherlock, G., Brown, P., Hastie, T., Tibshirani, R., Botstein, D., and Altman, R. Missing value estimation methods for dna microarrays. Bioinformatics, 17(6):520-525, 2001.
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. arXiv preprint IrXiv:I905. 10947, 2019.
Um, D., Park, J., Park, S., and young Choi, J. Confidence- based feature imputation for graphs with partially known features. In The Eleventh International Conference on Learning Representations, 2023. URL https:// openreview net forumm 2
Park, S., Lee, K., Jeong, D.-E., Ko, H.-K., and Lee, J. Bayesian nonparametric classification for incomplete data with a high missing rate: an application to semiconductor manufacturing data. IEEE Transactions on Semiconduc- tor Manufacturrnng 2023.
Um, D., Yoon, J. W., Ahn, S. J., and Yeo, Y. Gene-gene re- lationship modeling based on genetic evidence for single- cell rna-seq data imputation. Advances in Neural Infor- mation Processing Systems, 37:18882-18909, 2024.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Um, D., Lee, Y., Park, J., Park, S., Yeo, Y., and Ahn, S. J. Relation-aware diffusion for heterogeneous graphs with partially observed features. In The Thirteenth Interna- tional Conference on Learning Representations, 2025.
Ramirez, R., Chiu, Y.-C., Hererra, A., Mostavi, M., Ramirez,
J., Chen, Y., Huang, Y., and Jin, Y.-F. Classification of cancer types using graph convolutional neural networks.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint arXiv: 1rXiv:1710.111 1710.11010,.33 2017.
Frontiers in physics, 8:203, 2020.
Rossi, E., Kenlay, H., Gorinova, M. I., Chamberlain, B. P., Dong, X., and Bronstein, M. M. On the unreasonable effectiveness of feature propagation in learning on graphs
Von Luxburg, U. A tutorial on spectral clustering. Statistics and computing, 17:395 416, 2007.

---

Propagate and Inject: Revisiting Propagation-Ban saaagd Based Feature Imputation for Graphs with Partially Observed Features
Wang, G., Ying, R., Huang, J., and Leskovec, J. Multi- hop attention graph neural network. arXiv preprint arXiv:2009. 14332, 2020.
Wu, S., Sun, F., Zhang, W., Xie, X., and Cui, Graph neural networks in recommender systems: survey, ACM Computing Surveys, 55(5):1-37, 2022.
Xu, K., Li, C., Tian, Y.. Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. International confer- ence on machine learning, pp. 5453-5462. PMLR, 2018.
Yoon, J., Jordon, J., and Schaar, M. Gain: Missing data imputation using generative adversarial nets. In Interna- tional conference on machine learning, pp. 5689-5698. PMLR, 2018.
You, J., Ying, R., and Leskovec, J. Position-aware graph neural networks. In International conference on machine learning, pp. 7134-7143. PMLR, 2019.
You, J., Ma, X., Ding, Y., Kochenderfer, M. J., and Leskovec, J. Handling missing data with graph repre- sentation learning. Advances in Neural Information Pro- cessing Systems, 33:1 33:19075-19087, 2020.
Zhang, M. and Chen, Y. Link prediction based on graph neu- ral networks. Advances in neural information processing systems, 31, 2018.
Zhang, M., Li, P., Xia, Y., Wang, K., and Jin, L. Label- ing trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems,
2021.
Zhong, J., Gui, N., and Ye, W. Data imputation with iterative graph reconstruction. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 11399- 11407, 2023.
Zhuf, X. and GhahramanifH, Z. Learning from labeled and unlabeled data with label propagation. ProQuest Number: INFORMATION TO ALL USERS, 2002.
12

---

Propagate and Inject: Revisiting Propagation-Ban -aaagddtio--Bsedd Feature Imputation for Graphs with Partially Observed Features
A. Proof of Convergence of Diffusion Stages
in (Berman & Plemmons, 1994), we have p W ( = 1. Moreover, since both W uuo and Wila) share the same non-
Our FISF consists of two diffusion stages: pre-diffusion and DSF. Both stages utilize row stochastic transition matrices for diffusion. We prove the convergence of the two diffusion stages follows.
uw
zero eigenvalues, it follows that p (WWa)) uvo) = p uw ).
((
Ultimately, this leads to the conclusion that p (W p uuO <p(Wl")) =1.
Proposition A.1. The pre-diffusion transition matrix for the a-th channel is defined by
Lemma A.3.
Luu
is invertible where Iuu is the identity matrix.
( X {(()
W Lg
Oeu Wa 10M
W
(a)
ak
Proof. Since I is not an eigenvalue of W by Lemma A.2, O is not an eigenvlaue of I... W (a) Thus Iuu W (a)
where W( is row-stochastic. Using W( the pre- diffusion in the a-th channel is defined by
is
invertible.
x(0) (t) = (l - 1), t= 1,...,, K;
We now prove Propostion A.1 as follows.
x (0) = [x]
O2
Proof. Unfolding the recurrence relation gives us:
Then, lim (K) converges. K-00
(1)
I&s
Oku
(a) (1 1)
x (t)
The proof of Propostion A.1 refers to (Um et al., 2023). After establish the convergence of pre-diffusion, we demonstrate that this proof extends to cover the convergence of DSF. To start, we introduce two lemmas.
X (t)
W uk
(a)
w(()) au
x (t 1)
( (t
w uk k (t - 1) + W
(a)
Xu
(t 1)
nu
Lemma A.2. w is the row-stochastic matrix calculated by ( = (D(a) where ((a) a diagonal ma-
Since x (1) = x (t (t-1) in the first {x rows, it follows
that Xx (K)
(a)
x That is, x(0) (K) retains the
trix that has diagonal entities D((a)= = E,Wi, W us is
values of xx
(a) Therefore, lim ) converges to x K-x
(a)
the [x x |x(e) bottom-right submatrix of W
(a) and let
pl-) denote spectral radius. Then, pl (/W (a))
Now, we focus solely on the convergence of lim (a) (K). K-500
< 1.
uw
When we unroll the recursion for the last (x!! rows,
(a)
Proof. Consider w((a) uud E NNXN where the bottom right submatrix is denoted w zero. That is,
(a) ((a) and all other elements are
(K) = w (a)
(a) (K 1)
uk X
+
- (a)
W (a) uk X
+ W( ((0) - 2))
uk k
(((a und =
lou W
(a)
O
K-1
(a) ak x
+ (W k
where OKk {0)1K) 1x 10
OKe {ollK
t=
and Ouk E (x|8")) Given that W w(1) represents
By Lemma A.2, lim (w
the weighted adjacency matrix of the connected graph G, wi() Fur-
0. Therefore,
w(()) ((()) clement-wise and (=
K-000
un0
ag0
lim (wla) K (a) K-+00 uu
(0) 0, regardless of the initial
thermore, considering that w
ano + W(e) constitutes the
state for x! (0). (we replace x!( (0) with a zero col- umn vector for simplicity.) Hence, our focus shifts to (a)
weighted adjacency matrix of a strongly connected graph,
we conclude that w uwo + wa(a) is irreducible based on Theorem 2.2.7 in (Berman & Plemmons, 1994). Conse-
(a)
lim (EK-l (W K-000
(a)
quently, applying Corollary 1.5 in (Berman & Piemmons, 1994), P ((()) ( < p (W Since the spectral radius of a stochastic matrix is one according to Theorem 2.5.3
Given that Lemma A.2 establishes p( p( ((W()) (a) au < 1, and
Lemma A.3 affirms the invertibility of (Inx W aa
13

---

Propagate and Inject: Revisiting Propagation-Bal Based Feature Imputation for Graphs with Partially Observed Features
Table 6. Ablation study of different variants of FISF on semi-supervised node classification tasks under structural-missing settings at mm = 0.995. Results are reported as accuracy (%) with standard deviation.
Method
CORA
CITESFER
PURMED
PHОTO
COMPUTERS
OGBN--RRXV
FISF-A (only synthetie feature injection)
73.66 = 2.14
65.81 + 2.96
72.93 3.49
87.73 0.97
78.64 + 1.76
66.79 + 0.20
FISU-B (fully synthetic features)
70.21 = 5.10
26 06.06:2 3.25
54.03 2.62
88.05 0.81
79.05 0.86
63.52 1
FISF-C (diffusion only with synthetic feature)
75.23 = 1.26
67.13 4: 2.07
74.92 2.19
87.46 1.40
78.78 4: 1.51
66.70 :: 0.40
FISF
79.29 +: 1.72
69.68 +: 2.47
76.90 1.50
88.22 1: 0.79
79.40 +: 1.11
69.92 = 0.17
Table 7. Comparison of different value assignment strategies for synthetic features in FISF, evaluated on semi-supervised node classification under structural atructuralmmissing settings at I' = 0.995. 'Randomly sampled (Ours)' denotes FISF where synthetic values are sampled from a uniform distribution. Results are reported as accuracy (%) with standard deviation.
Synthetic features
CORA
CITESBER
PUBMED
Рното
COMPUTERS
OGBN-ARXIV
Max
79.15 + 1.57
68.97 + 2.28
76.67 + 0.85
88.02 + 0.86
78.95 + 1.60
69.44 + 0.10
Min
74.05 + 1.69
65.32 = 2.59
73.75 = 2.66
88.16 + 1.00
79.17 + 0.78
69.47 - 0.21
Median
73.87 + 1.59
65.39 = 2.67
73.83 + 2.75
$8.14 1.07
79.28 + 0.84
68.22 = 0.37
Mean
76.00 + 1.75
66.35 + 3.08
73.69 + 2.53
87.79+1.08
78.60 + 1.69
68.28 + 0.20
Channel-wise Mean + Std
77.79 + 1.74
69.10 + 2.64
71.68 + 2.68
87.98 + 1.02
78.54 + 1.68
68.30 + 0.38
Randomly sampled (Ours)
79.29 + 1.72
69.68 + 2.47
76.90 + 1.50
88.22 + 0.79
79.40 = 1.11
69.92 + 0.17
Table 8. Ablation study of FISF. SS node classification de- notes semi-supervised node classification. # denotes the number of synthetic features injected into low-variance channel. denotes the optimal hyperparameter at the set- ting.
B. Proof of the Proposition in Sec 4.3
We refer to the proposition in Sec. 4.3 as Proposition B. Proposition B.1. pre-diffusion (channel-wise inder-node diffusion (Um et al., 2023)), when all given known features in the a-th channel (i.e., elements in x (a) have the same value c, Jim x<() (t) becomes a vector where entire ele- t- ments are equal to c.
Task
SS node classification
Link prediction
Dataset
CORA
CITESEER
y
ACC
AUC
AP
0
74.62
1.78
79.38 + 1.81
82.98 0.86
1
100
78.50 + 1.91
83.63 + 1.69
85.42
1.79
Proof. In accordance with the given assumption, entire el- ements in x have the value of c. Here, we can initialize
78.52
1.94
83.46 + 1.84
85.32
1.59
100
78.78 = 1.51
58.67 13.44
60.27 + 14.40
x(()(0) with the same values as According to the proof of
78.88
1.91
82.11 2.43
83.61 2.50
79.29 1.72
84.12 1.17
85.85
Proposition 1, lim x(a) (K) = (Iu.. wi(a) w((a)
(a) (a)
K-+00
au
uk X
and x x (K) = (a)) This means that initializing & (( with the values of c does not affect the final output, lim (K). Formally, pre-diffusion of which steady K-x
the geometric series converges as follows
K
state is the same as that of Eq. can be expressed as fol- lows:
lim xK)(
lim
W
(a) mu
W
x
K-000
K000
uck
x(()(t) = W(a) 1), t= 1,..., KK;
(Iuu
(a)
[c
(10)
x())(0)
In conclusion, the recursion in the pre-diffusion converges.
Cu.
where C₁ and cu are column vectors with lengths of [0) and [)(a) respectively, filled only with the value
In the case of DSF, the DSF transition matrix (0) in Eq. 8 is also row stochastic. The distinction between ((a) and (b) lies solely in the number of channels where diffuuion is performed and the sizes of each sub-matrix. Therefore, the convergence of the DSF can also be established through the proof of Proposition A.
Since W(a) is row stochastic, KK1 Wa(a)
for all
{I,..., NJ. Therefore, in Eq. 10 i.j
the i-th ele-
ment in (1) is calculated as Σド K- w(a) = c-
Σ Σj= (a) is filled only with the value e, which is the same as (0) (0).
ig for all i i NJ.. That is, x x(a) (1)
14

---

Propagate and Inject: Revisiting Propagation- Bassed Feature Imputation for Graphs with Partially Observed Features
Table 9, Classification results measured by Micro-Fl score (%). OOM denotes an out-of-memory error.
Echocardiogram
ABIDE
Duke Breast Cancer
Diabctes (Tm 4.03%)
Approach
Method
(T' 2.59%)
(Tm = 52.52%)
(Tm 11.94%)
GAIN
68.67 + 4.99
89.30 + 1.81
76.31 + 1.32
53.58 = 0.59
MIWAE
69.43 6.25
64.33 + 0.93
OOM
OOM
Tabular Imputation
GRAPE
75.00 + 0.81
91.61 + 0.89
OOM
OOM
IGRM
69.33 + 8.21
66.38 + 1.85
OOM
00M
GCNMF
86.00 1 2.49
75.05 1 2.94
74.86 + 1.36
52.17 = 0.85
85.67 + 4.67
90.79 + 1.44
75.38 + 2.82
53.03 = 0.85
Graph Imputation
PCFI
86.33 + 2.87
90.56 + 1.21
75.85 + 2.11
52.37 1.36
FISF
86.67 2.36
90.94 + 1.45
76.58 + 0.62
53.77 75 + 1.01
Table 10. Performance in semi-supervee node classification OGBN-Arxiv Pm 0.995, measured by accuracy (%)
Missing setting
I.P
GCNMF
GRAFFENE
FP
PCFI
FISF
MNAR-I
67.56 + 0.00
60.73 0.91
14.60 + 4.68
68.63 + 0.35
68.24
0.67
69.02 + 0.57
MNAR-D
67.56 + 0.00
60.89 + 0.52
14.47 4.54
68.08 + 0.41
67.88 + 0.29
68.51 + 0.25
Thus, even if this recursion repeats, x()) remains the [c same as which results in lim (())(t)
FISF-B (fully synthetic features): All missing features are directly replaced with randomly sampled synthetic values without any diffusion.
[c.
where
C., entire elements are equal to c.
C..
FISF-C (diffusion only with synthetic feature): Dif- fusion performed using only the synthetic feature, with known features removed.
C. Additional Experiments
C.1. Ablation Study
Table 6 presents the results of semi-supervised node classi- fication. As shown in the table, simply injecting synthetic features, or performing diffusion using only the injected synthetic feature without any observed features within the channel, results in significantly worse performance com- pared to the original FISF.
We conduct ablation study investigate the effectiveness of the elements in FISF. We perform both semi-supervised node classification and link prediction. For ablation study on semi-supervised node classification, we conduct exper- iments on Cora under a puuctural-missing setting with I'm = 0.995. For link prediction, we utilize CiteSeer under structural- airustural-missing setting with I'm 0.995. 3 takes role in spreading synthetic features widely and 7 implies the ratio of selected lowvnnriance channels to diffuse with synthetic features. Table 8 demonstrates the results of the ablation study. The results show that the performance gain by introducing synthetic features (ie., 7 * 0) is significant. The optimal /3 and the optimal y synergistically enhance the performance, resulting considerable improvements. The bottom two rows in Table 8 demonstrate that injecting two synthetic features into row-variance channels leads degra- dation in performance. This shows the validity of injecting single synthetic feature into a low-variance channel.
Additionally, we conduct an extensive ablation study com- paring various value assignment strategies for synthetic fea- tures. Since FISF does not involve learning process during imputation, statistical approaches may serve the most rea- sonable alternatives to random sampling. Specifically, compare the performance of FISF variants using different value assignment strategies, including the max, min, mean, and median of the observed features. We also evaluate a variant called Channel-wise Mean + Std, which statistically determines synthetic feature values on a per-channel ba- sis. Specifically, (1) Max: the maximum of the observed feature values within the channel; (2) Min: the minimum of the observed feature values; (3) Median: the median of the observed values; (4) Mean: the mean of the observed values; (5) Channel-wise Mean + Std: the mean of each low- vwr-iariance channel after pre-diffusion, plus the standard deviation of values in non-low-variane channels. The re- sults are presented Table 7. As shown in the table, the
We further conduct an additional ablation study on the use of synthetic features. We compare the performance of FISF and three of its variants, depending on how synthetic fea- tures are injected and utilized within low-variance channel.
FISF-A (only synthetic feature injection): synthetic feature injected but not used the diffusion process.
15

---

Propagate and Inject: Revisiting Propagation-Bal Baaesttdo--Bseddd Feature Imputation for Graphs with Partially Observed Features
Cora
CiteSecr
PubMed
79
66
70
71
54
54
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.99
0.1
0.2
0.3 0.4 0.5 0.6
0.7
0.8 0.9
0.99
0.1
0.2
0.3
0.4 0.5 0.6 0.7 0.8 0.9 0.99
Channel removal from the lowest variance
Channel removal from the highest variance
Figure 4. Accuracy (%) semi-supervised node classification tasks while increasing the proportion of excluded channels from the original feature matrix.
Cora
CiteSeer
PubMed
89
90
92
85
87
87
81
84
0
0.1
0.2
0.3
0.4
0.5
0.8
0.7 0.8 0.9 0.99
0.1
0.2 0.3
0.4 0.5 0.8 0.7 0.8 0.9
0.99
0
0.1
0.2
0.3 0.4 0.5 0.8 0.7 0.8 0.9 0.99
Channel removal from the lowest variance
Channel removal from the highest variance
Figure 5. ROC AUC score (%) on link prediction tasks while increasing the proportion of excluded channels from the original feature matrix.
78.5
78
77
76
75.5
80.5
74
74
α
B
72
Y
0.1
0.3
0.4
0.6
0.7
0.9
0.1
0.2
0.3
0.5
0.8 0.7
0.8 0.9
30
40
70
100
Figure 6. Semi-supervised node classification accuracy with different a, B and 7. The blue dashed lines indicate existing state-of-the-art performance.
original FISF consistently achieves the best performance. We believe this performance gain stems from the increased diversity across feature channels the imputed matrix, fa- cilitated by the use of randomly sampled values.
compare FISF with four imputation methods developed for tabular datasets, including GAIN (Yoon et al., 2018), MI- WAE (Mattii & Frellsen, 2019), GRAPE (You et al., 2020), and IGRM (Zhong et al., 2023). For graph imputation meth- ods, we select the three most competitive baselines: GC- NMF, FP, and PCFI. We simply construct k-nearest neighbor (kNN) graphs apply graph imputation methods including our FISF to tabular datasets. The goal of these experiments is to classify each patients, iee, disease diagnosis.
C.2. Applicability to Medical Tabular Data
To demonstrate the wide applicability of FISF, we conduct experiments in medical classification using medical tabular datasets, which initially contain missing features. We uti- lize four medical tabular datasets: Echocardiogram (Asun- cion et al., 2007), ABIDE (Di Martino et al., 2014), Duke Breast Cancer (Saha et al., 2018), and Diabetes (Asuncion et al., 2007). In addition to graph imputation methods, since we address imputation on tabular data, we further
Table presents the results of medical classification on tab- ular datasets. As shown in the table, FISF consistently ex- hibits the best classification performance among graph data imputation methods. Notably, FISF, developed for graph- structure data, also surpasses tabular imputation methods
16

---

Propagate and Inject: Revisiting Propagation-Bes Based Feature Imputation for Graphs with Partially Observed Features
Table 1I. Accuracy (%) of FISF for different values of m, the scale factor for random noise, on semi-supervised node classification.
0.01
0.1
1 (used)
10
100
CORA
76.83 + 1.38
78.72 = 1.35
79.29 + 1.72
79.65 = 1.11
71.09 + 8.03
CITESEER
68.10 1 2.02
68.69
2.86
69.68 1 2.47
68.95 1 3.38
66.68 1 2.17
PUBMED
75.09 2.12
76.78
76.90 1.50
77.28 0.71
69.19 12.55
PHOTO
87.95 +: 1.20
1.04
88.22 1: 0.79
88.01 + 1.34
87.75 + 1.64
COMPUTERS
78.86 + 0.76
78.93 1.23
79.40 1.11
80.01 + 0.20
80. 0.79
OGBN-ARXIV
68.48 0.17
69.04 + 0.38
69.92 + 0.17
69.82 + 0.15
69.31 + 0.18
Table 12. Accuracy (%) of FISF for different values m on semi-supervised node classification, when normalized features are given.
771
CORA
CITESEER
PUBMED
РHОТО
COMPUTERS
OGBN-ARXIV
0.1
78.68 + 1.78
69.42 2.31
76.93 1.11
87.35 1.64
79.24 0.42
69.56 0.30
1
79.08 + 1.45
69.50 + 2.50
77.16 + 1.11
88.12 + 1.43
80.23 + 0.65
69.88 + 0.21
10
77.99 + 1.58
68.50 + 2.11
76.14 2.05
88.21 0.85
77.61 1.62
69.75 + 0.22
on the Echocardiogram, Duke Breast Cancer, and Diabetes datasets, which do not have predefined connectivity among samples. This indicates the potential for extending graph data imputation to the tabular domain. Furthermore, while MIWAE, GRAPE, and IGRM, which state-of-the-art tabular imputation methods, suffer from scalability issues, graph imputation methods, including our FISF, operate well across all datasets. Throughout these experiments, we con- firm that FISF is effective even in medical classification on tabular datasets initially containing missing values, which are not graph-structur data.
C.4. Contribution of Low-variance Channels in Downstream Tasks
In order to experimentally confirm little contribution of low-variance channels in downstream tasks, we compare performance by excluding partial channels from the original feature matrix using two different ways. The first way (red lines in Figure 4 and Figure 5) is excluding channels in de- scending order of variance, starting from the highest, based on fixed proportion. Then, as the second way (blue lines), we exclude channels from the lowest variance in ascending order, i.e., the low-variance channels are removed first.
C.3. Missing Not at Random Setting
Figure 4 demonstrates the results on semi- cumi-supervised node classification tasks. Since low-variance channel contains nearly identical values that do not aid in distinguishing nodes, the classification accuracy denoted by blue lines persists despite an increasing removal proportion of low- variance channels. However, cases of channel removal from the highest variance suffer significant performance degrada- tion even with low proportion of channel removal.
Our FISF is a generic method that is effective regard- less of missing settings. To further validate the effec- tiveness of FISF beyond the random missing setting, we conduct additional experiments dom' (MNAR) scenarios. In MNAR scenarios, the miss- ing probability depends on the unobserved values them- selves. Thus, for the experiments, we establish two MNAR settings: MNAR-I and MNAR-D. In MNAR- the missing probability of a feature increases as the feature's value increases; conversely, in MNAR-D, the missing probability decreases the feature's value in- creases. For MNAR-I and MNAR-D, we set the miss- ing probability of Vi,a to max(1, exp( (mix()))mmm(x))) )) -Pi and max(1, exp( [max(X)-minn) []]] )) respectively. Table 10 shows classification accuracy in semi-supervised node clas- sification on the CGBN-Arxin dataset under MNAR settings. The results reveal that FISF consistently outperforms the baselines across both MNAR settings, thereby demonstrat- ing its effectiveness even in MNAR scenarios.
'Missing Not At Ran-
As shown in Figure 5, little contribution of low-variance channels is also evident in link prediction tasks. Since identical representations among nodes results in consistent representations across node pairs, low-variance channels also contribute very little to performance link prediction tasks.
Fie
C.5. Effects of Hyperparameters
We further analyze the effects of FISF hyperparameters, (a, 3)). on Cora under structural missing settings with I'm = 0.995. Figure shows the accuracy of FISF models with different a, 3 and y. When varing each hyperparam- eter, the other hyperparameters are set their optimal val- ues. Compared to existing state-of-the-art performance of
17

---

Propagate and Inject: Revisiting Propagation- -Based Feature Imputation for Graphs with Partially Observed Features
Table 13. Performance on semi-supervised node classification tasks at Tm 0.995, measured by accuracy (%).
Structural missing
Method
CORA
CITESBER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Average
FISF FISF*
79.29 + 1.72 78.68 + 1.72
69.68 2.47
76.90 = 1.50
88.22 + 0.79
1.11 79.40 + 1.11
69.92 + 0.17
77.24 77.11
69.68 2.47
76.74 + 1.84
88.22 + 0.79
69.92 + 0.17
Uniform missing
Method
CORA
CiTESBER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Average
FISF FISF#
79.09 + 1.73
69.52 + 1.81
77.53 + 1.28
88.32 + 1.37
82.12 0.51
69.81 + 0.16
77.73
79.09 + 1.73
69.52 1.81
76.89
2.01
88.32 + 1.37
81.56 + 0.47
69.81 + 0.16
77.53
Table 14. Performance on link prediction tasks at mm 0.995, measured in ROC AUC score (%).
Structural missing
Method
CORA
CITESEER
PUBMED
PHOTO
COMPUTERS
Average
FISF FISF#
87.26 + 1.44 86.80 1.27
84.12 1.17
83.19 + 0.78
95.86 + 0.21
94.70 + 0.30
89.03
84.12 1.17
82.46 0.94
95.76 + 0.33
94.39 + 0.82
88.70
Uniform missing
Method
CORA
CITESEER
PUBMED
PHOTO
COMPUTERS
Average
FISF
87.44 + 0.80
83.45 + 2.53
85.33 + 0.47
96.64 + 0.18
95.13 + 0.35
89.60
FISF#
87.56 + 1.29
81.15 + 1.17
82.46 + 0.69
95.68 + 0.42
94.94 + 0.27
88.36
74.62%, all FISF models consistently exceed it by a con- siderable margin regardless of the value of a. Furthermore, significant performance improvement are observed with small A small / results in the performance degradation. This is because too small 3 assigns excessive influence to synthetic features, which hinders the spread of known fea- tures. This result validates the DSF stage, which enables the wide spread of synthetic features, is properly designed.
To generalize the sampling distribution against the magni- tude of values in the feature channel, node-wise normal- ization can be good solution. We apply node-wise 1.2 normalization to pre-imputed features where synthetic fea- tures will be injected. Table 12 shows the results. We can confirm that m = produces maintains robust performance across different datasets. These discussions and experimen- tal results demonstrate that the performance is significantly affected when the magnitude of random noise is either too small or too large. They also suggest that node-wise nor- malization can be good solution to handle various scales of features effectively.
C.6. Effects of the Magnitude of Synthetic Feature Values
To confirm the effects of the magnitude of synthetic feature values, we conduct additional experiments by using scale factor m. The values for the synthetic features are scaled by multiplying them by m. after being sampled from uniform distribution on [o. 1). Table 11 shows the results. As shown in the table, m E {0.1, 10) generally shows similar per- formance, while there is performance decrease in the case of E {0.01, 1003. We believe that the performance drop for 0.01 is due to the fact that it barely increases the variance of the channel. For = 100, after the imputation process, the low-variance channels with injected synthetic features will be on different scale compared to other chan- nels without injected synthetic features, which disrupts the learning process of the downstream GNN.
C.7. Hyperparameter search for FISF
Despite the outperforming performance of FISF, conducting a hyperparameter search for FISF with three hyperparame- ters (a, 3, and 7) can be burdensome in certain situations. However, both a and (0 < a, 3 < 1) play a shared role in base of distance during calculating PC (Lee. Er Si. and & = ,St.... Thus we can combine them into one, i.e., a = B. By doing this, the search complexity can be reduced from 53 to 5² without the performance degrada- tion by setting five search points for each hyperparameter. Table 13 and Table 14 show that the FISF* with the light search does not degrade performance semi-supervised
18

---

Propagate and Inject: Revisiting Propagation-Bal -aased Feature Imputation for Graphs with Partially Observed Features
FP
PCFI
FISF (Ours)
Cora
CiteSeer
Figure 7. t-SNE plot visualizing imputed features.
FP
PCFI
FISF (Ours)
Cora
CiteSeer
Figure 8. t-SNE plot visualizing deep features in GCN.
node classification and link prediction. The version with the light search requires from 20 minutes to 10 hours depend- ing on the datasets, therefore this burden is manageable for practical usage of FISE.
compare the smoothness of output features obtained through imputation methods. For this comparison, we em- ploy Dirichlet energy, a representative criterion for mea- suring smoothness on a graph. As shown in Table 15, FP displays the lowest Dirichlet energy among the imputation methods. contrast, FISF makes Dirichlet energy of the imputed features similar that of the original features. Note that our FISF shows the highest Dirichlet energy (distinc- tiveness) among the methods. Through the outperforming performance of FISF over the existing methods, we can
C.8. Smoothness Analysis
We generate synthetic feature in low-variance channel in order to make features in that channel distinctive across nodes. To investigate smoothness (feature homophily),
19

---

Propagate and Inject: Revisiting Propagation-Bes -aased Feature Imputation for Graphs with Partially Observed Features
Table 15. I)) of imputed features under a structural-missing setting with I' 0.995, where ED is the Dirichlet
energy. Original denotes original given features.
Missing way
Structural
Uniform CITESeER
Method +
CORA
CITESEER
PUBMED
CORA
PUBMED
Original
4.36
4.49
3.11
4.36
4.49
3.11
FP
1.90
1.94
0.798
1.89
1.91
0.805
PCFI
3.14
2.59
1.49
2.52
2.64
1.43
FISF (Ours)
3.25
2.92
4.15
2.69
2.70
4.34
Table 16. Average cosine similarity of imputed features by FISF, under structural-missing setting with fm = 0.995.
Intra-class
Dataset
Inter-class
Ratio
class
class 2
class 3
class
class 5
class 6
class 7
Average
CORA 0.760
0.858
0.902
0.902
0.844
0.691
0.826
0.870
0.842
1.11
CITESEER
0.279
0.267
0.341
0.636
0.282
0.513
0.380
0.403
1.45
PUBMED
0.871
0.893
0.936
0.880
0.903
1.04
Table 17. Average cosine similarity of original features.
Intra-class class
Dataset
Inter-class
Ratio
class
class
class
class
class
class 7
Average
CORA
0.0578
0.841
0.113
0.0896
0.683
0.0690
0.0853
0.109
0,0883
1.53
CITESBER
0.0470
0.655
0.0601
0.0617
0.0650
0.762
0.0581
0.0644
1.37
PUBMED 0.0719
0.112
0.937
0.0779
0.0946
1.32
confirm that features with low dirichlet energy (high feature homophily) does not always ensure good performance in downstream tasks while smoothness is an inductive bias of GNNs.
Table 18. Performance on semi-supervised node classifica- tion tasks at I'm = 0.995, measured by accuracy (%).
Dataset
FISF
FISF-L
CORA
79.29 1.72
78.92 = 1.60
To investigate smoothness within classes, conduct further experiments. Table 16 demonstrates the intra-class cosine similarity calculated from imputed features by FISF. Ratio denotes average similarity/inter-lass similarity. If Ratio is greater than 1, inter-class similarity becomes less than the average intra-class similarity, which means the feature is distinctive enough for classification of node features.
CITESEER
69.68 + 2.47
69.63 + 1.40
PUBMED
76.90 + 1.50
76.70 + 1.62
PHOTO
88.22 + 0.79
88.10 0.97
COMPUTERS
79.40 + 1.11
79.09 - 1.14
OGBN-ARXIV
69.92 0.17
69.03 0.19
Table 17 shows the intra-class cosine similarity calculated from original features. The results indicate that original features also have values of Ratio greater than across the datasets. This means that the datasets also originally have higher intra-class feature similarity compared to inter-class feature similarity. Despite the introduction of synthetic features during diffusion, as shown in Table 16, we can observe that imputed features by scheme consistently maintains higher intra-class feature similarity than inter- class feature similarity.
for both imputed features and deep features than the other imputation methods.
C.9. Synthetic Features Sampled from Non-Uniform Distribution
Our FISF samples the value of a synthetic feature from uniform distribution, because this value only needs to differ from the nearly identical values of observed features within the same channel. Random sampling from a uniform distri- bution is simple yet effective to achieve this goal. In terms of selecting node for placing synthetic feature, we have considered another node sampling scheme that does not rely uniform distribution. We attempted to sample the node from distribution in which the sampling probability varies based on the locations observed features. We aimed to increase the sampling probability for nodes farther from observed features. However, we empirically observe that
We also perform qualitative analysis on imputed features and deep features to compare imputation methods. The qualitative analysis conducted in structural missing set- tings with r' 0.995. Figure 7 and Figure 8 demonstrates the t-SNE plots visualizing imputed features and deep fea- tures, respectively. FISF provides clearer cluster structures
20

---

Propagate and Inject: Revisiting Propagation- -aased Feature Imputation for Graphs with Partially Observed Features
# channels
chumnels
# channels
1000
1000
1900
Zero Initialization
# channels
500
500
500
10 10-32 10.2
var
10-1
10
10 10-35
10
var
503
233
# channels
channels
# channels
10
10
10
10-33
var
1000
1000
1000
2. Random Initialization
Original Features
500
10 10""" 10 10-2
var
1 10 32 10
10 10
var
10 35 10 10
var
FP (Rossi al., 2022)
PCFI (Um et al., 2023)
FISF (Ours)
Figure 9.
Distributions of variances for each feature channel with zero/random initialization for missing features. Cora dataset with 99.5% missing features is commonly used.
Table 19. p-values comparing FISF to the runner-up on SSNC, measured across 50 splits of each dataset under structural-missing settings with I'm = 0.995. min FISF denotes the worst accuracy among 50 runs.
Method
CORA
CITESBER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
FISF (ours)
79.14 + 1.32
68.83 + 1.95
76.97 + 1.44
88.11 + 1.21
79.11 # 1.01
69.91 + 0.22
min FISF
75.95
65.43
74.77
86.56
77.09
69.45 68. 78 + 0.24
runner-up
74.35 + 1.65
66.01 + 2.99
74.53 2.40
87.44 + 1.25
78.72 + 1.31
p-value
1.66 x 10 10-18
6.69 x 10-7
3.13 x 10
2.08 x 10-3
7.87 x 10
1.96 x 10 22
sampling the node from this distribution rather degrades per- formance slightly in downstream tasks, compared to when sampled from uniform distribution. Table 18 shows the comparison results between the original FISF and FISF-L using the aforementioned node sampling strategy. We be- lieve that this degradation comes from biased selected nodes, which damages the diversity across feature channels in an imputed matrix. Consequently, we sample both a node and value for synthetic feature from uniform distributions.
large K, careful consideration needed when determining K, depending on the initialization. In conclusion, low- variance channels initialization for missing features.
mainly caused by the use of zero
C.111 Statistical Analysis
We conduct additional experiments show that our FISF is insensitive random synthetic feature generation and evaluate the statistical significance of FISF's superior per- formance. Table 19 shows p-values comparing FISF to the runner-up in each setting for the results semi-supervised node classification tasks under structural missing settings with missing rate (rm 99.5%). As shown in the table, the p-value indicates the statistical significance of the perfor- mance improvement of our FISF over the runner-up. The results demonstrate that our FISF significantly outperforms the runner-up up in most cases, with p-values much lower than 0.05, suggesting that the performance gains are not due to random chance. Furthermore, even the worst accuracy among 50 runs (min FISF) shows superior or competitive performance compared the runner-up. This demonstrates that our FISF is robust and insensitive to variations in the random generation of synthetic features, thereby confirming the stability and reliability of our method under extreme missing feature scenarios.
C.10. Zero Initialization vs Random Initialization
Do low variance channels occur due to zero initializa- tion use for missing features? We compare the variance distributions when zero initialization and random initial- ization are used for missing features. Figure shows that many low-varince channels persist despite random initial- ization, but there is slight difference between the distri- butions despite using the same setting. This is because all the propagation-based methods approximate the steady state with sufficiently large hyperparameter K, indicating the number of diffusion iteration (c.g., K 40 is used in FP and K = 100 is used in PCFI and FISF). However, we have further confirmed that variance distributions becomes identical with very large values (c.g., K = 1000) regardless of initialization. Although the final approximated results are not affected by initialization for missing features with a
21

---

Propagate and Inject: Revisiting Propagation- Baseed Feature Imputation for Graphs with Partially Observed Features
Low-variance channels
Imputed feature matrix
Figure 10. Diffusing a synthetic feature for each low-variance channel results in distinctive imputed features across nodes.
Table 20. log(Ep) of imputed features on PubMed under structural-missing settings with 0.995.
Table 21.
The distribution of channel variances in fea- tures imputed by PCFI on PubMed according to I' under structural mructural-missing settings.
I'm
0.0
0.3
0.5
0.9
0.995
0.999
channel variance
0.0
0.3
0.5
0.9
0.995
0.999
FP
3.11
3.39
3.29
2.80
0.80
0.77
11033 oo)
13
12
9
1
0
0
PCHI
3.11
3.45
3.39
3.06
1.49
2.12
[10 10-3)
467
435
388
126
FISF (Ours)
3.11
3.45
3.40
3.11
4.15
5.27
10-5, 10-1)
20
53
103
373
163
70
0, 0,10-b)
0
0
318
117
C.12. Investigating the Counterintuitive Performance Trend of FISF under High Missing Rates
Table 22. The distribution of channel variances in features imputed by FP on PubMed according to T' under structural- missing settings.
We conduct additional experiments investigate the un- derlying reason for the counterintuitive performance trend of FISF at high missing rates, observed in the PubMed dataset results in Figure 3. Feature homophily, which can be measured by the Dirichlet energy (Ep), a crucial factor for downstream graph neural networks to perform semi- supervised node classification tasks. Hence, we measure the Dirichlet energy (Ep) of imputed features. Since this trend highlighted on PubMed, perform these experiments PubMed. Table 20 shows the results. These results indicate that our FISF maintains high Dirichlet energy despite high rates of missing features, while other propagation-be bbasd methods suffer from a severe decrease Dirichlet energy. The high levels of feature homophily (i.e., Dirichlet energy) stem from synthetic features, which diffuse their values along edges to overcome the low-variance problem.
channel variance
0.0
0.3
0.5
0.9
0.995
0.999
10 oo)
0
10 10 3)
467
412
6
58
0
0
10 4) 0, 10-5)
79
339
439
25
0
155
3
475
496
its surroundings and creates local spike centered on the node with the synthetic features. Each node has larger dif- ferences in values from the synthetic feature the distance from the central node increases. If we inject synthetic feature into each low variance channel, but place it at different location for each channel. Then the diffused node feature vector containing every low-variance channel feature after diffusion becomes distinctive from those of the other nodes by reflecting the graph structure. Figure 10 illustrates visualization of the distinctiveness the diffused feature vector by scheme.
D. Discussions
D.I. Justification for synthetic feature injection
Conceptual explanation. In low-variance channels, all missing features are filled with nearly the same values re- gardless connectivity, which can not provide any struc- tural information. contrast, in our scheme, for each low- variance channel, the synthetic feature diffuses value to
Channel variance analysis. To clarify why randomly sam- pled values effectively enhance feature distinctiveness, we conduct further experiments that investigate distributions of each channel's 's variance for varying missing rate (rm)). We compare the distributions of the output matrices obtained by
22

---

Propagate and Inject: Revisiting Propagation-Bee BBased Feature Imputation for Graphs with Partially Observed Features
Table 23. Performance in semi-supervised node classification on various datasets, measured by accuracy (%)
Method
CORA
CITESEER
MUBMED
PHOTO
COMPUTERS
node2vec
76.67 + 1.48
64.00 + 1.66
69.50 + 4.09
87.77 + 1.42
78.98 + 1.55
Preliminary diffusion + node2vec
77.20 + 1.38
66.78 + 1.62
70.19 + 4.35
87.81 + 1.74
79.25 0.94
FISF (ours)
79.29 +: 1.72
69.98 2.47
76.90 + 1.50
88.20 + 0.79
79.40 1.11
Table 24.
The distribution of channel variances in fea- tures imputed by FISF on PubMed according to I'm under structural-miss miiiring settings.
mathematically demonstrate that the cause of low variance channels lies in the situation where the values of observed features within a specific channel are identical (as shown in Appendix B). In a nutshell, the low-variance problem arises from identical values of observed features within a specific channel.
channel variance
0.0
0.3
0.5
0.9
0.995
0.999
[10-3, oo)
13
14
12
7
0
[10-1,10 10
467
465
414
380
246
222
10-$,10-1
20
21
74
112
193
205
In contrast, typical GNNs that suffer from the over- smoothing problem have consistent update rules, includ- ing the weights of self-loops, across nodes and features. All nodes update their features by aggregating features from neighboring nodes. The cause of the over-smoothing problem is proven to be the excessive number of GNN layers (Keriven, 2022; Oono & Suzuki, 2019; Luan et al., 2019). The key point in this proof is that the eigenvalues of the graph Laplacian, which is the weighted matrix used in GNN layers for message passing, fall between 0 and 1. In contrast, although the weighted matrix used in propagation- based imputation also has eigenvalues between and 1, the reason why the large number of layers does not lead to the over-smoothing problem is due to the aforementioned unique aggregation rule regarding self-loops.
[0, 90
0
0
0
54
73
our FISF and existing propagation-base based imputation meth- ods. Tables 21, 22 and 24 demonstrate the results. As shown in Tables 21 and 22, the number of low-variance channels in outputs produced by existing propagation imputa- tion methods substantially increases I'm increases. This implies a decrease in the distinctiveness of imputed fea- tures since all features within a low-variance channel have nearly the same values. Unlike these methods, as shown in Table 24, we can confirm that FISF effectively alleviates the occurrence of low-variance channels, indicating signifi- cantly higher feature distinctiveness compared existing methods. From theoretical perspective, vero-variance channel-corresponding to the first eigenvector of the graph Laplacian is regarded in the literature as an example of zero expressiveness, as it is not useful for discriminating between nodes (Chung, 1997; Von Luxburg, 2007).
There are two main approaches designed to address the over-smoothing problem. The first is a self-loop-based approach, including APPNP (Gasteiger et al., 2018) and GDC (Klicpera et al., 2019), which adds self-loops with certain weights to all nodes to prevent excessive smooth- ing. We compare this approach with our FISF by applying APPNP-style diffusion rule, shown in Table 6 of the general response PDF. As illustrated in the table, our FISF consistently outperforms the APPNP- imputation by significant margins across various datasets under structural missing settings with a missing rate of 0.995. The second approach is concatenation- based, where multi-scale features aggregated from neighbors at different hops are concate- nated (Luan al., 2019; Wang et al., 2020). However, since imputation requires output with the same dimension as the original features, the concatenation-basee approach developed to address the over-smoothing problem cannot be applied to imputation.
D.2. Low Variance Problem vs Over-Smoothing Problem
To clarify the distinction between the low variance problem and the over-smoothing problem (Keriven, 2022), we em- phasize a fundamental difference between the two issues from the perspective of self-loops. Propagation-baser im- putation methods (Rossi et al., 2022; Um et al., 2023) and typical GNNs share message passing framework to up- date features using aggregation steps. However, during the aggregation steps of propagation ods, all observed features have self-loops with a weight of while these observed features do not aggregate features from neighboring nodes (i.e., do not consider graph struc- tures). The purpose of this aggregation rule is to preserve the observed features despite multiple aggregation steps, while updating the values of missing features. Due to this different aggregation rule only for observed features, the steady state of overall imputed features is determined by the values of observed features (as shown in Appendix A). We
imputation meth-
D.3. Why not Use graph Positionnl//truutuuall Encoding?
The key distinction of our FISF approach from graph po- sitional/structural encoding is that FISF allows for the in- tegration of feature information and structural information
23

---

Propagate and Inject: Revisiting Propagation-PPs -aasedd Feature Imputation for Graphs with Partially Observed Features
Table 25. Ablation study on the number of additional channels used in PCFI+FISF+ for semi-supervised node classification under structural missing settings at I'm = 0.995. F' and Topt denote the number of channels the feature matrix and the optimal hyperparameter r used by the original FISF, respectively. Results are reported as accuracy (%) with standard deviation.
# Additional Channels
CORA
CITESEER
PUBMED
РHOTO
COMPUTERS
OGBN-ARXIV
0 (Vanilla PCFD)
74.62 + 1.78
66.06 + 3.26
74.47 + 2.54
87.49 = 1.50
79.02 + 1.22
68.78 = 0.25
0.125F. Topi% 0.25F Toop %
77.04 1.42
67.90 2.22
75.84 + 2.33
87.93 1.55
79.04 + 1.90
68.96 = 0.30
77.50 0.92
68.39
77.08 + 2.23
87.69 = 1.00
79.21 1.31
69.01 = 0.17
0.5F Topt %
78.56 + 1.07
2.57
77.17 2.29
87.92
78.47 1.33
69.19 = 0.14
F. Popt min(2F
78.70 0.69
69.13 2.35
77.18 + 1.25
87.94
1.34
79.28 + 1.92
69.15 = 0.27
Top %, F)
78.60 + 1.22
69.23 + 2.38
77.10 1.40
87.96 + 0.65
79.22 + 1.45
69.28 = 0.28
Table 26. Accuracy (%) semi-supervised node classification under auruetuallmmsssngg settings at r' 0.995. LPE and RWPE denote Laplacian postional encoding (Dwivedi et al., 2023) and Random Walk positional encoding (Dwivedi et al., 2022), respectively. OOM and Timeout denote an out-of-memory error and failure caused by exceeding the maximum allowed execution time of 72 hours, respectively.
Method
CORA
CITESEER
PUBMED
РHОТо
COMPUTERS
OGBN-ARXIV
MEGAE
39.96 + 8.73
28.97 + 7.09
OOM
74.47 + 3.85
51.58 + 5.52
OOM
MEGAE*LPE
66.70 + 2.38
50.26 + 5.02
OOM
80.64 + 0.70
71.26 : 2.77
OOM
MEGAE+RWPE
48.91 + 10.50
42.13 = 3.04
OOM
78.01 = 0.78
54.77 + 6.64
OOM
FFGAF+FISFI
78.98 + 1.38
68.45 + 2.23
0OM
86.61 + 1.06
76.52 + 1.27
0OM
FP
71.61 + 3.13
59.13 + 3.15
72.56 3.22
86.69 + 1.94
77.02 1.37
68.24 + 0.24
FP+LPE
73.44 + 5.27
62.71 + 2.30
71.72
3.01
86.79 + 1.99
78.04 + 1.62
Timeout
FP+RWPE
71.55 + 1.90
59.16 + 1.44
70.21 + 3.29
86.90 : 1.82
77.27 + 1.73
68.30 + 0.45
FP+FISF*
78.67 + 1.53
68.32 + 2.23
76.44 + 1.89
87.08 + 2.22
78.33 + 1.20
69.12 = 0.30
PCFI
74.62 + 1.78
66,06 3.26
74.47 + 2.54
87.49 + 1.50
79.02 + 1.22
68.78 + 0.25 Timeout
PCFI+LPE
76.51 2.44
67.39 + 2.28
74.61 1.75
87.95 + 1.07
79.13 1.34
PCFI+RWPE
74.34 + 1.40
65.81 2.81
72.25
2.54
87.96 + 0.91
78.85 1.56
68.89 + 0.18
PCFI+FISF*
78.70 + 0.69
69.13 + 2.35
77.18 + 1.25
89.07 + 1.34
79.28 + 1.92
69.15 + 0.27
within low-variance channels. In FISF, although a synthetic feature with randomly sampled values is injected into a low-variance channel, the channel still contains observed features with nearly identical values. Since FISF preserves all observed features during its diffusion process, the output of FISF retains this feature information, reflecting the nearly identical values within the channel. Simultaneously, the injected synthetic feature with a distinct value makes its sur- rounding nodes similar to its own value, thereby encoding structural information. After the final diffusion stage, the low-variance channels the output will contain both nearly identical observed feature values and feature values similar to the synthetic feature, corresponding to feature informa- tion and structural information, respectively. Thus, FISF can naturally integrate both feature and structural information within low-variance channels.
ble 23 presents the accuracy in semi-supervised node clas- sification under structural-misee rate of 99.5%, where "node2vee" denotes the case where node2vec is used alone as input, and "Preliminary diffusion node2vec" refers to the case where node2vec is used as complementary values. As shown in the table, our FISF con- sistently outperforms both cases using positional//tructural encoding vectors across datasets. These performance gains stem from FISF's ability to integrate feature information and structural information within low-variance channels.
settings with a missing
D.4. Can FISF Be Applied to Other Imputation Methods as Additional Channels?
We conduct additional experiments in which FISF ap- plied to other imputation methods as additional channels (denoted as FISF+). We further compare FISF with Lapla- cian Positional Encoding (LPE) (Dwivedi et al., 2023) and Random Walk Positional Encoding (RWPE) (Dwivedi et al., 2022). Table 25 shows the results. As shown in the table, while LPE and RWPE generally improve the performance
We compare our FISF with the case where a posi- tional/structural encoding vector used as complemen- tary values. We employ node2vec (Grover & Leskovec, 2016), a representative structural encoding method. Ta-
24

---

Propagate and Inject: Revisiting Propagation-Bane Based Feature Imputation for Graphs with Partially Observed Features
Table 27. Dataset statistics.
Table 28. Statistics of medical tabular datasets.
Dataset
#Nodes
#Fdges
#Fcauures
#Classes
Dataset
F
F Fuum
Feat
Y'
CORA
2,485
5,069
1,433
7
Echocardiogram
74
12
3
9
2
2.59%
CITESEER
2,120
3,679
3,703
6
Duke Breast Cancer
907
93
34
59
2
11.94%
PUBMED
19,717
44,324
500
3
ABIDE
1112
104
85
19
2
52.52%
PHOTO
7,487
119,043
745
8
Diahctes
10177
47
11
3
4.03%
COMPUTERS
13,381
245,778
767
10
OGBN-ARXIY
169,343
1,166,243
128
40
ate different training/validationness node splits for each dataset except for OGBN-Arxiv. (The node split of OGBN- Arxiv is fixed according published years of papers (i.e., nodes).) Following the splits in (Klicpera et al., 2019), we assign 20 nodes per class as training nodes. Subsequently, the number of validation nodes is adjusted to ensure that when combined with the training nodes, it totals 500. For test nodes, we include all nodes except those designated as training or validation nodes.
of existing imputation methods by providing structural in- formation, FISF consistently achieves the most significant performance improvements. Unlike positional encodings, our approach can use the feature information preserved in low-variance channels.
We conduct additional experiments to evaluate how many additional channels with synthetic features improve results. For FISF+, do not perform separate hyperparameter tun- ing: instead, we reuse the optimal hyperparameters from the original FISF. Accordingly, the number of additional channels added by FISF* is set to F Topt- Table 26 shows the results. As shown in the table, even a small number of additional channels using FISF+ leads to substantial per- formance improvements. We further observe that, for each dataset, the optimal number of additional channels tends to lie near the number of channels into which the original FISF injects synthetic features.
Vanilla GCN models for imputation methods (MEGAE (Gao et al., 2023), FP (Rossi et al., 2022), PCFI (Um et al., 2023), and our FISF) and GCNMF models are trained as follows. We utilize Adam optimizer (Kingma & Ba, 2014) and set the maximum number of epochs to 10, 000. We use an early stopping strategy based on validation accuracy, with patience of 200 epochs. We apply dropout (Srivastava et al., 2014) with the drop probability p. p and learn- ing rates in all experiments are searched in {0, 0.25, 0.5} and (0.01, 0.005, 0.001, 0.0001), respectively, using grid search on validation sets. We train GRAFENNE models by following the training details specified in (Gupta et al., 2023).
E. Experimental Details
F. Dataset Details
For all the baselines, we follow all the hyperparameters specified in the original papers codes. If hyperparameters (specifically, hidden dimension and the number of layers) for specific dataset are not clarified in the papers, we perform a hyperparameter search using grid search approach. The search ranges of hidden dimension and the number of layers are {16, 32, 64, 128, 256} and {2, 3}. respectively.
Table 27 summarizes the dataset statistics. All the datasets used in this paper are provided in Pytorch Geometric. All the datasets used in our work, including the Cora, Cite- Seer, PubMed, Photo. Computers, and OGBN-arxiv, are MIT-licensed. In the citation networks, nodes and edges represent documents and citation links, respectively. In the case of recommendation networks, nodes represent goods and an edge connects two nodes only when the nodes (i.e., products) are frequently bought together. Following (Rossi al., 2022) and (Um et al., 2023), we conduct all experi- ments the largest connected graph of each dataset. FISF can also handle disconnected graphs by working each connected graph.
Link prediction. For GCNMF and GAE used as down- stream models for imputation methods, models with Adam optimizer for 200 iterations. We apply dropout (Srivastava et al., 2014) with the drop probability p. Through grid search on the validation sets, and learning rates in all experiments are searched within (0, 0.25, 0.5] and {0.1, 0.01, 0.005, 0.001, 0.0001 ), respectively. We ran- domly create 5 different training/validationn for each dataset. For each split, the splits in (Kipf & Welling, 201 we assign 10% edges for the training set, 5% edges for the validation set, and 85% edges for the test set.
train all the
edge splits
E.2. Implementation Details
We conduct all the experiments GeForce RTX 2080 Ti GPU and an Intel Core 15-6600 CPU at 3.30 Hz. All models are implemented in Pytorch (Paszke et al., 2019) and Pytorch Geometric (Fey & Lenssen, 2019). Semi-supervised node classification. We randomly cre-
single NVIDIA
For GAE models for the imputation methods, we commonly train the models as follows. We use Adam optimizer and set
25

---

Propagate and Inject: Revisiting Propagation- Basod Feature Imputation for Graphs with Partially Observed Features
Table 29. FISF hyperparameters used in experiments on semi-supervised node classification tasks.
Missing way
Structural missing
Im
0.3
0.5
0.9
0.995
0.999
Datasets
y
Y
@
B
Y
B
|
Y
CORA
0.7
0.9
10
0.7
0.9
50
0.9
0.7
90
0.9
0.7
90
0.9
0.9
90
CITESEER
0.9
0.7
90
0.7
0.7
30
0.9
0.5
50
0.9
0.9
90
0.9
0.9
90
PUBMED
0.9
0.9
10
0.9
0.7
70
0.9
0.5
10
0.9
0.5
90
0.9
0.5
90
РHOTO
0.5
0.9
0.5
0.7
90
0.1
0.9
70
0.1
0.1
70
0.1
0.1
50
COMPUTERS
0.3
0.9
0.1
0.1
90
0.1
0.7
50
0.1
0.1
50
0.1
0.1
90
OGBN-ARXIV
0.3
0.3
10
0.3
0.3
10
0.1
0.3
30
0.1
0.1
90
0.1
0.1
70
Missing way
Uniform missing
I'
0.3
0.5
0.9
0.995
0.999
Datasets
7
αx
3
7
?
7
?
CORA
0.9
0.9
10
0.9
0.7
30
0.7
0.9
30
0.9
0.7
70
0.7
0.7
70
CITESEER
0.1
0.3
50
0.1
0.3
70
0.9
0.5
70
0.9
0.9
30
0.7
0.7
90
PUBMED
0.3
0.1
10
0.3
0.1
30
0.9
0.5
50
0.9
0.5
50
0.9
0.5
90
PHOTO
0.3
0.3
53
0.3
0.3
50
0.1
0.3
70
0.3
0.1
30
0.1
0.5
90
COMPUTERS
0.5
0.5
10
0.5
0.5
10
0.1
0.3
10
0.1
0.5
50
0.1
0.5
50
OGBN-ARXIV
0.3
0.1
10
0.3
0.1
30
0.9
0.3
30
0.1
0.1
90
0.1
0.1
10
Table 30. FISF hyperparameters used in experiments on link prediction tasks.
training, validation, and testing, with proportions of 10%, 10%, and 80%, respectively. The classification performance is then measured by calculating the average Micro-F1 score across these five splits. We utilize MLP classifiers on the feature matrices imputed by tabular imputation methods to set the
Missing way
Structural missing
Uniform missing
I'
0.995
0.995
Datasets
3
7
7
perform classification. For the MLP classifiers, number of layers and the hidden dimension to 2 and 64, respectively. Table 28 presents the statistics of the medical tabular datasets used in this paper. N refers to the number of samples, while F indicates the number of features. The numerical and categorical features are represented by Fram and Feat, respectively. The numerical features are scaled fixed range of 0 to and categorical features are en- coded using one-hot encoding. C denotes the number of classes, and rm indicates the missing feature rate in each dataset. The value of & in kNN graph construction for graph imputation methods is selected from {1,3,5,10 10) based on the validation set.
CORA
0.5
0.9
90
0.3
CITESEER
0.9
0.9
90
0.1
0.7
10
PUBMED
0.1
0.3
70
0.1
0.5
90
COMPUTERS
0.1
0.9
10
0.1
0.9
70
PHOTO
0.1
0.7
10
0.1
0.7
10
Table 31. URL links for baselines.
Baseline
link
GCNME GRAFENNE
httpss:/github..omm hatpaaabbbccommtaaiiiiirantnnnnn
MEGAE
hntp://///////cctto--aaaa entropy--ge (aamm//ggga22//mma/
FP
FISF implementation. For remi-supervised node classifi- cation tasks, set the number of layers and learning rates to 64 and 0.005, respectively. For link prediction tasks Cora, CiteSeer, and PubMed, we set learning rates to 0.01. We set learning rates to 0.001 for Photo and Computers. In all experiments, we fix K to 100 and dropout applied with p = 0.5. In the case of experiments on OGBN-Aree following (Rossi et al., 2022) and PCFI (Um al., 2023), we leverage GCN layers with skip connections (Xu al.. 2018) and set the hidden dimension 256. Hyperparamters (o,, B3, and 7) of FISF used in experiments are summarized
PCFI
hutps//github..o//deeeouuu
the number of epochs to 200. Learning rates are searched from (0.01, 0.005, 0.001, 0.0001) by grid search vali- dation sets. Following (Kipf& & Welling, 2016b), (Taguchi et al., 2021), and (Um et al., 2023), we leverage GAE mod- els with 32-dimensional hidden layer and 16-dimensional latent variables.
Medical Classification. We create five random splits for
26

---

Propagate and Inject: Revisiting Propagation-Basn BBsed Feature Imputation for Graphs with Partially Observed Features
in Table 29 and Table 30. We will release the code upon publication.
F. Algorithmie Description of FISF
Algorithm Algorithmic procedure of FISE
Implementation of baselines. For LP, we use codes implemented in Pytorch Geometric (Fey & Lenssen, 2019). The hyperparameter a of LP is searched from For the baselines except for LP. we use code released by the authors of papers. The URL links for the baselines are given in Table 31. While the codes for FP and PCFI are licensed under Apache-2.0, and the codes for GCNMF and MEG AE are licensed under MIT, the code for GRAFENNE has no public declaration of license.
1: Input: Adjacency matrix A E (0, 10,1NNx,, input fea- tures RNXF,, known/unknown node sets 1/(
{0.95, 0.9, 0.8, ..7,...,,.... 0.13.
V(() for each channel a, hyperparameters (a, S, r) Output: Imputed feature matrix X RN*F
// Pre-diffusion
4: for each channel a= t F do
5: Compute shortest path distance Si.
dset (vs k A)
Compute PC: Er, a
7: Build weighted matrix W( Si if Aij Si.a
8: Normalize W (D (4)
Wy(a)
Replace top with one-hot encoding = W(a)
(a)
10: Initialize x (*) (0)
x 0,
11: for t to K do
12: xt = W
13: end for
14: end for
15: Stack (x()) to form pre-imputed matrix
16: // Synthetic Feature Generation
17: for each channel
to F do 18: Compute variance of Var Var(X..a)
19: end for
20: Select r% low-variance channels F;;
21: for each E F, do
22: Randomly choose node v.(b) V!!
23: Sample synthetic value ar L(00 1)
24: D
{Us J. 12()) + v(( \ (v
(b)
25: end for
26: // Diffusion with Synthetic Features (DSF)
27: for each E F, do
28: Compute S = duet (1: (2:1) A), Eipb = 8/,
Compute S d(v,, v1 (b) IA), Si
29:
30:
Build weighted matrix (1)
E
if Ai.j 1
Normalize M (b) = ( (M)
31:
32:
Replace top rows with one-hot encoding + (())
(b)
33:
Initialize x x(*) (0)
x
0..
34:
for t = 1 to K do
35:
x x = M1 & (0) 1)
36: end for
37: Replace column X. (K)
38: end for
39: return X <- X
27

---

Propagate and Inject: Revisiting Propagation-Bann -aaasdttoo-Basedd Feature Imputation for Graphs with Partially Observed Features
G. Additional Experimental Results
28

---

Propagate and Inject: Revisiting Propagation-Bal -aaaed Feature Imputation for Graphs with Partially Observed Features
# channels
# channels
channels
channels
Fm
500
500
500
250
250
250
500
MISSING
0 10 $10 3910~"10-"100
0 10 3-10-' 200--00--1
0
10 10010 1100~10---000
250
# channels
# channels
# channels
0
10 10-11--910-- 10-00-00111100 1510-2
I' 99.5 % 1000
1000
1000
Original Features
500
500
500
10 1001
var
10-110-9900 100110000000000000000
10 10-110 10--0000100000000000000 var
m missing rate
FP (Rossi et al., 2022)
PCFI (Um et al., 2023)
FISF (Ours)
Figure 11. Distributions of variances for each feature channel on Cora dataset with 90%/99.5% missing features. FP and PCFI generates output matrices with many low-variance channels outlined in red, whereas FISF resolves the issue of low-variance channels.
channels
# channels
# channels 2000
2000
2000
# channels
Ym 90 %
1000
3000
10 110 -00---0--
var
100111000001110 "10-1000000-----
var
var
2000
MISSING
# chunnels
# channcls
# channels
1000
3000
3000
3000
0 10
100 -10 210
Fm 99.5
2000
2000
2000
Original Features
1000
1000
1000
10
1001100100010--0000 -10---000
0
10-110 1001"00"100011111000000
i missing rate
FP (Rossi et al., 2022)
PCFI (Um et al., 2023)
FISF (Ours)
Figure 12. Distributions of variances for each feature channel on CiteSeer dataset with 90%/99.55 missing features. FP and PCFI generates output matrices with many low-variance channels outlined red, whereas FISF resolves the issue of low-variance channels.
29

---

Propagate and Inject: Revisiting Propagation-Bae -aased Feature Imputation for Graphs with Partially Observed Features
Table 32. Performance link prediction tasks at mm = 0.995, measured by AP (%). Standard deviation errors are given. The best result is highlighted in bold and underlined, while the second-best result is highlighted only in bold. OOM denotes an out-of-memory error.
Structural missing
Method
CORA
CITESEER
MUBMED
PHОTO
COMPUTERS
Full features
92.62 1.13
91.60 1.44
96.59 0.32
95.24 0.39
93.77 0.61
GCNMF
70.20 0.80
69.19 1.78
86.20 0.32
80.58 0.28
83.34 0.17
GRAFENNE
64.70 3.76
72.08 9.71
70.43 3.74
64.78 1 0.84
66.56 + 1.14
MEGAE
69.78 + 0.78
70.85 2.92
OOM
86.46 + 1.65
86.12 1.13
FP
86.40 + 1.26
82.61 1.96
83.98 0.79
93.74 0.57
91.50
PCFI
88.63 1 0.90
82.98 1 0.86
87.07 1 0.42
96.31 0.25
94.58 0.37
FISF
88.81 1.35
85.85 1 1.38
87.55 1 0.35
95.33 1 0.22
94.71 1 0.26
FISF+NIP
89.35 1.24
85.25 + 1.85
87.62 0.12
95.95 0.18
95.41 0.33
Uniform missing
Method
CORA
CITESEER
PUBMED
РHотO
COMPUTERS
Full features
92.62 = 1.13
91.60 1.44
96.59 = 0.32
95.24 = 0.39
93.77 + 0.61
GCNMF
64.21
65.06 2.67
82.64 1 2.17
80.61 1 0.20
83.38 1 0.12
GRAFENNE
75.04 = 13.33
71.39 + 9.71
73.56 + 5.77
68.36 = 7.71
69.79 + 5.81
MEGAE
67.98 + 1.85
63.67 + 2.89
OOM
83.22 = 1.48
85.11 + 2.00
FP
88.67 + 1.26
85.39 1 1.89
82.99 + 2.14
95.51 = 0.19
94.06 1 0.27
PCFT
89.13 + 1.06
85.47 + 1.82
88.20 + 0.38
96.87 + 0.20
95.55 + 0.32
FISE
89.16 + 0.77
85.17 = 2.00
88. 73 + 0.36
96.27 = 0.23
95.12 + 0.32
FISF+NIP
89.23 0.89
84.73 4 2.00
88.72 0.36
96.32 0.26
96.12 0.30
30

---

Propagate and Inject: Revisiting Propagation-Bal Based Feature Imputation for Graphs with Partially Observed Features
Table 33. Performance semi-supervised node classification tasks Fm 0.995, measured by accuracy (%). Standard deviation errors are given. 0OM denotes out-of-memory error. All imputation methods use GIN the downstream network.
Structural missing
Method
CORA
CITESEER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Full features
79.78 1 1.49
68.58 1 1.14
76.24 1: 2.51
87.26 0.76
83.73 1 1.50
70.24 1: 0.26
LP
74.54 1 1.79
65.42 1 1.80
71.67 1 4.94
82.27 2.72
76.01 1 1.84
67.56 1 0.00
GCNMF
31.33 + 2.73
24.84 + 2.44
40.48 + 0.53
25.60 0.17
37.21 + 0.08
9.00 + 6.27
GR GRAFENNE
20.20 10.98
17.58 + 2.94
33. 2.43
21.10 17.39
16.31
11.84
13.66 + 12.23
MEGAE (GIN)
32.79 + 5.64
29.68 3.17
OOM
59.55 9.117
47.94
0OM 67.80 0.57
(GIN)
70.88 3.30
59.68
4.18
70.84 4.28
81.85 1.42
74.28 + 2.51
PCFT (GIN)
73.
+ 3.17
60 + 3.60
72. + 3.92
82.34 1.20
77.50 + 1.39
68.83 0.30
FISF (GIN)
78.15 + 1.45
69.10 2.16
75.31 + 1.82
83.06 1.68
77.96 = 1.36
69.75 + 0.20
Uniform missing
Method
CoRA
CITESEER
PUBMED
PHOTO
COMPUTERS
OGBN-ARXIV
Full features
79.78 1.49
68.58 1.14
76.24 2.51
87.26 + 0.76
83.73 1.50
70.24 +: 0.26
LP
74.34 1.79
65.42 + 1.80
71.67 + 4.94
82.27 2.72
76.01 + 1.84
67.56 + 0.00
GCNMF
34.01 1: 8.08
29.71 1: 5.12
40.08 1 0.45
25.59 0.16
37.20 1: 0.08
5.86 1 0.00
GRAFENNE
20.55 13.65
19.32 7.42
7.42
34.75 4.26
29.96 20.92
21.74 15.94
15.52 1 11.70
MEGAE (GIN)
8.15
32.29 6.70
0OM
52.53
37.20 0.08
OOM 68.61 1 0.14
FP (GIN)
77.48
68.32 2.81
71.56 3.73
83.59 1 0.98
78.27 0.85
PCFI (GIN)
78.38 1.35
68.61 + 1.89
74.62 + 2.59
83.77 + 1.67
79.07 0.91
69.40 + 0.25
FISF (GIN)
79.01
1.42
69.13 1.96
75.05 + 2.09
84.17 2.08
79.50 + 0.76
69.88 + 0.22
31


Reviews:
[{"review_id": "ir3B6xhT7L", "reviewer": "Reviewer_rdYf", "summary": "In this paper, the authors introduce FISF, a novel approach for graph feature imputation. FISF effectively mitigates the low-variance channel problem by strategically injecting synthetic features, thereby enhancing performance in both semi-supervised node classification and link prediction tasks across a wide range of missing rates.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank the reviewer for the detailed feedback and insightful questions that help us further improve our work.\n\n> **Q1.** Since I'm not familiar with this field, are there any other more advanced baselines?\n\nWe appreciate the reviewer’s thoughtful question. **Before submitting the paper, we conducted a thorough investigation of recent methods and included all state-of-the-art baselines relevant to graph learning with missing features**. We have closely followed recent advances and carefully examined the literature in this area. Propagation-based feature imputation methods, including FP and PCFI, have demonstrated exceptional performance, and researchers have recently focused on extending the existing methods to new applications [1, 2]. **In contrast, our study identifies a key limitation of current propagation-based methods and proposes a solution that effectively addresses this issue**, achieving significant performance improvements. We will incorporate very recent work on propagation-based feature imputation, thereby ensuring that our paper reflects the most up-to-date developments in the field.\n\n[1] \"Gene-Gene Relationship Modeling Based on Genetic Evidence for Single-Cell RNA-Seq Data Imputation.\" NeurIPS 2024\\\n[2] \"Relation-Aware Diffusion for Heterogeneous Graphs with Partially Observed Features.\" ICLR 2025.\n\n> **Q2.** Other graph neural networks, such as GIN, can be considered to verify the structural generalizability of the method proposed by the author.\n\nTo verify the structural generalizability of the proposed method, FISF, **we conduct additional experiments using GIN as the downstream network for the imputation methods**. Table 30 presents the semi-supervised node classification results at a missing rate of 0.995. As shown in the table, **FISF consistently outperforms state-of-the-art methods across all datasets and missing settings, demonstrating its strong generalizability** across datasets, missing settings, and downstream network architectures. We will include this table in Section 5 of the revised manuscript to emphasize this important discussion.\n\n**Table 30**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2030.png\n\n> **Q3.** The author has supplemented a lot of experiments. Haven't they considered publishing this research in a journal?\n\nWe greatly appreciate the reviewer’s encouraging comment. We submitted this work to ICML to receive timely feedback and **to make a prompt contribution to the long-standing topic of missing values in the machine learning community**. To demonstrate the generalizability and validity of our method, we conducted extensive experiments and thorough analyses in the submitted paper.\n\n> **Q4.** Are structural missing and uniform missing common in real-world scenarios?\n\nStructural missing and uniform missing, where the features of randomly selected nodes and randomly selected feature values in the feature matrix are removed, respectively, are categorized as Missing Completely At Random (MCAR) among missingness mechanisms. **MCAR is the most commonly assumed setting in the missing data community** [3, 4]. Our proposed FISF consistently demonstrates its effectiveness under both missing settings.\n\nTo further validate the effectiveness of FISF beyond MCAR settings, **we also conducted experiments under Missing Not At Random (MNAR) scenarios in Appendix C.3**. In MNAR, the probability of missingness depends on the unobserved values themselves. For these experiments, we designed two MNAR settings: MNAR-I and MNAR-D. In MNAR-I, the probability that a feature is missing increases as the feature value increases; in MNAR-D, vice versa. Table 5 in the manuscript shows classification accuracy in semi-supervised node classification on the OGBN-Arxiv dataset under MNAR settings. The results reveal that FISF consistently outperforms the baselines across both MNAR settings, thereby **demonstrating its effectiveness even in MNAR scenarios**.\n\n[3] \"Gain: Missing data imputation using generative adversarial nets.\" ICML 2018.\\\n[4] \"Handling missing data via max-entropy regularized graph autoencoder.\" AAAI 2023.\n\n> **Q5.** How long does it actually take to train the model once?\n\nTo address the reviewer's concern, we report the average training and hyperparameter tuning time of the FISF model, measured on a single NVIDIA GeForce RTX 2080 Ti GPU and an Intel Core i5-6600 CPU at 3.30 GHz. As shown in Table 31, **training a single FISF model takes only a few minutes**. Despite using grid search, the efficiency of FISF enables the model for OGBN-Arxiv, which contains 169,343 nodes, to complete hyperparameter tuning in less than a day, while other FISF models require only a few hours. We provide a detailed discussion of the complexity and scalability of FISF in Appendix C.5 and Appendix C.6, respectively. We will add this discussion and table to Appendix C.5 in the revised manuscript.\n\n**Table 31**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2031.png", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The key contributions of the paper is important to the broader scientific literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "1. Through numerous experiments, FISF was evaluated on multiple benchmark datasets. The results show that FISF significantly improves the performance of semi-supervised node classification and link prediction tasks, proving the effectiveness of the method.\n2. The convergence of the diffusion stage was theoretically proven.\n3. The method is novel as it is the first research to apply synthetic features to imputation.", "other_comments_or_suggestions": "1. All the compared baselines are from before 2023. Since I'm not familiar with this field, are there any other more advanced baselines?\n2. Only GCN is used as the backbone. Other graph neural networks, such as GIN, can be considered to verify the structural generalizability of the method proposed by the author.", "questions_for_authors": "1. The author has supplemented a lot of experiments. Haven't they considered publishing this research in a journal?\n2. The generation methods of missing features only consider two situations: structural missing and uniform missing. Are these two situations common in real-world scenarios?\n3. The author uses Grid search to determine the hyperparameters. Since there are quite a lot of hyperparameters and multiple experiments are needed, how long does it actually take to train the model once?", "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": "", "extra_scores": {}}, {"review_id": "12BeuDqIOq", "reviewer": "Reviewer_KGeX", "summary": "This work identifies a limitation of previous works for learning on graphs with missing features, that being the output channels for feature imputation have low-variance. To solve this problem, the authors diffuse the observed features with injected random noise to produce final imputed features. Their method, FISF, is compared to several baselines on standard node classification tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We greatly appreciate the reviewer’s positive feedback on the strength of our empirical results and theoretical justifications. We also appreciate the insightful questions, which provide valuable guidance for further enhancing our paper.\n\n> **Q1.** Is there any theory to corroborate the reason that these low-variance channels are negatively impacting downstream node classification tasks? On a related note, why does the injection of synthetic features improve downstream tasks? Theory on the “why” would make this work incredibly strong.\n\nWe would like to respectfully clarify that our claim is not that low-variance channels produced by propagation-based imputation methods negatively impact downstream node classification tasks, but rather that they contribute little to them. **From a theoretical perspective, a zero-variance channel—corresponding to the first eigenvector of the graph Laplacian—is regarded in the literature as an example of zero expressiveness, as it is not useful for discriminating between nodes** [1, 2]. Based on this, we identify the issue that existing propagation-based imputation methods produce channels with near-zero variance in their output. We experimentally confirm that these low-variance channels contribute very little to downstream tasks, as shown in Figure 1b and Appendix C.7 of the manuscript.\n\nWe theoretically prove that propagation-based feature imputation produces low-variance channels when all observed features in a given channel have the same value. To prevent a group of nearly identical values within a channel from diffusing only themselves and consequently forming a low-variance channel, we inject a synthetic feature with a randomly sampled value that is likely to differ from the existing known values, allowing it to participate in the diffusion process. As a result, our FISF effectively increases the variance of low-variance channels in its output matrix, as shown in Figure 1a, Figure 11, and Figure 12 in the manuscript. This increase in channel variance leads to significant performance improvements across various downstream tasks and diverse domains, as shown in Figure 3, Table 1, Table 2, and Table 4 in the manuscript. In summary, **synthetic feature injection enables low-variance channels to overcome their lack of distinctiveness and recover expressiveness**.\n\nAppendix D.1 in the manuscript provides justification for synthetic feature injection, including conceptual explanation and in-depth analysis on channel variance. We will add this discussion to Appendix D.1 of the revised manuscript, interpreting the low-variance problem through the lens of spectral graph theory.\n\n[1] Chung, Fan RK. Spectral graph theory. Vol. 92. American Mathematical Soc., 1997.\\\n[2] Von Luxburg, Ulrike. \"A tutorial on spectral clustering.\" Statistics and computing 17 (2007): 395-416.\n\n> **Q2**. Why perform channel-wise diffusion? What if all channel features are determined by the synthetic features only? Are there any studies/ablations?\n\nIn Appendix C.1 of the manuscript, we conducted an ablation study by adjusting each hyperparameter of FISF and the number of synthetic features injected per channel to analyze the effectiveness of its components. In addition to this study, and to address the reviewer’s concern, **we further conduct an additional ablation study on the use of synthetic features**. We compare the performance of FISF and three of its variants, depending on how synthetic features are injected and utilized within a low-variance channel.\n* FISF-A (only synthetic feature injection): A synthetic feature is injected but not used in the diffusion process.\n* FISF-B (fully synthetic features): All missing features are directly replaced with randomly sampled synthetic values without any diffusion.\n* FISF-C (diffusion only with a synthetic feature): Diffusion is performed using only the synthetic feature, with known features removed.\n\nTable 32 presents the results of semi-supervised node classification. As shown in the table, simply injecting synthetic features, or performing diffusion using only the injected synthetic feature without any observed features within the channel, results in significantly worse performance compared to the original FISF. The reason for performing channel-wise diffusion using both a synthetic feature and the observed features within a channel is that it **enables the output channel to capture both structural information and the feature information from the observed features simultaneously**. First, since the diffusion process is based on the graph structure, the diffusion of the synthetic feature can encode structural information. In addition, by preserving the original values of the observed features during the diffusion process, the feature information can also be retained.\n\nWe will include this extended ablation study in Appendix C.1 of the revised manuscript.\n\n**Table 32**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2032.png", "claims_and_evidence": "The empirical results support the claims that FISF reduces the number of channels with low-variance as compared to other methods such as FP and PCFI. Furthermore, on the task setting where node features are removed at high rates, FISF demonstrates superior performance on node classification tasks.", "methods_and_evaluation_criteria": "The methods are sound and evaluation is standard for this problem.", "theoretical_claims": "The paper does not emphasize any theoretical claims. However, the work provides sufficient support for their claim in Sec 4.3 within the appendix.", "experimental_designs_or_analyses": "The experimental design is appropriate for the graph learning tasks.", "relation_to_broader_scientific_literature": "Works investigating graph learning using data with missing node features largely depend upon explicitly/implicitly predicting the values of the missing data. This work identifies one of the issues with a naive implementation of feature imputation, where many output channels have low-variance. This understanding will be important in future works.", "essential_references_not_discussed": "To my knowledge, the relevant literature is discussed.", "other_strengths_and_weaknesses": "The empirical results are very strong. The addition of theoretical justifications would make this work even stronger. See questions.", "other_comments_or_suggestions": "See questions.", "questions_for_authors": "(1) Is there any theory to corroborate the reason that these low-variance channels are negatively impacting downstream node classification tasks? On a related note, why does the injection of synthetic features improve downstream tasks? Theory on the “why” would make this work incredibly strong.\n\n(2) Why perform channel-wise diffusion? What if all channel features are determined by the synthetic features only? Are there any studies/ablations?", "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": "", "extra_scores": {}}, {"review_id": "EjA98Cewkg", "reviewer": "Reviewer_41UF", "summary": "This paper addresses the issue of missing features in graph data, which hinders the effectiveness of Graph Neural Networks (GNNs). Existing diffusion-based imputation methods often result in low-variance channels, where feature values across nodes are nearly identical, leading to poor performance in downstream tasks. The paper proposes Feature Imputation with Synthetic Features (FISF), a novel imputation scheme that mitigates the low-variance problem by introducing synthetic features. FISF consists of two diffusion stages: pre-diffusion and diffusion with synthetic features. Pre-diffusion identifies low-variance channels using existing methods like PCFI. Then, FISF injects synthetic features into randomly chosen nodes in these channels, followed by a second diffusion stage that spreads the synthetic features to increase variance and improve node distinctiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank the reviewer for the thoughtful questions and valuable suggestions to further improve our work.\n\n> **Q1.** This work seems to show its advantage in especially large missing rate, such as 0.995 and 0.999. However, such a large missing rate is impractical in real applications.\n\n**Our FISF consistently demonstrates superiority across various missing rates ($r_m$), including low  $r_m$, as shown in Figure 3 in the manuscript**. As the reviewer mentioned, the performance gain obtained with FISF diminishes as the missing rate decreases. However, this is natural since a smaller $r_m$ means fewer missing features to impute, making it difficult to achieve a significant improvement solely through the superiority of the imputation method. Nevertheless, FISF consistently shows its effectiveness at even low $r_m$.\n\nFurthermore, **addressing high rates of missing features is an important issue in real-world scenarios**. As data sources become more diverse and abundant, the prevalence of highly incomplete data is also increasing. Consequently, **handling large missing rates has drawn significant attention across various domains**, including semiconductors [1], healthcare [2], and transportation [3], where datasets often exhibit extreme missing rates of 97.5\\%, 99.98\\%, and 99.99\\%, respectively.\n\n[1] \"Bayesian nonparametric classification for incomplete data with a high missing rate: an application to semiconductor manufacturing data.\" IEEE Transactions on Semiconductor Manufacturing (2023).\\\n[2] \"Temporal Belief Memory: Imputing Missing Data during RNN Training.\" IJCAI 2018.\\\n[3] Li, Jinlong, et al. \"Dynamic adaptive generative adversarial networks with multi-view temporal factorizations for hybrid recovery of missing traffic data.\" Neural Computing and Applications 35.10 (2023): 7677-7696.\n\n> **Q2-1.** There is no comparison regarding scalability and efficiency in the main body.\\\n> **Q2-2.** It is highly recommended to put the analysis in the appendix to the main body. The reorganization of the paper will greatly enhance this paper.\n\nWe agree that scalability and efficiency are important considerations when evaluating imputation methods. To demonstrate the effectiveness and validity of FISF, we conducted extensive and in-depth analyses. However, due to the strict 8-page limit, it was challenging to include these analyses in the main body in addition to presenting the core results. As noted in Appendix C.5 and C.6, we have already provided a complexity analysis and empirical results demonstrating the scalability of FISF. Since the final versions of accepted papers are allowed one additional page, **we will reorganize the paper by incorporating the analyses from Appendix C.5 and C.6 into the main body** in response to the reviewer’s suggestion. We sincerely appreciate the reviewer’s insightful suggestion and believe that this revision will further strengthen the presentation of our paper. If there are any remaining concerns or suggestions for improvement, we would be happy to receive your constructive feedback and are fully prepared to address any remaining points promptly.\n\n> **Q3.** It is better to provide a description of the algorithm in the paper.\n\nWe agree that providing a description of the algorithm is helpful for improving the clarity of the proposed method. In response to the reviewer’s suggestion, **we have written Algorithm 1 and will include it in Section 4 of the revised manuscript**.\n\n**Algorithm 1**: https://anonymous.4open.science/r/ICML12446-AF4E/Algorithm%201.png", "claims_and_evidence": "This paper introduces the low-variance issue in feature imputation. And address the issue by synthetic features.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "no theoretical claims", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "This may benefit the missing issue in the graph-structured data. However, the missing issues have been explored well before.", "essential_references_not_discussed": "I do not find the missing essential references.", "other_strengths_and_weaknesses": "Pros:\n\nFISF introduces a new perspective on feature imputation by addressing the low-variance issue with synthetic features.\n\nThis approach shows promising results in experiments.\n\nCons:\nThis work seems to show its advantage in especially large missing rate, such as 0.995 and 0.999. However, such a large missing rate is impractical in real applications.\n\nThere is no comparison regarding scalability and efficiency in the main body.", "other_comments_or_suggestions": "It is better to provide a description of the algorithm in the paper.\n\nIt is highly recommended to put the analysis in the appendix to the main body.  The reorganization of the paper will greatly enhance this paper.", "questions_for_authors": "See Other Strengths And Weaknesses.", "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": "", "extra_scores": {}}, {"review_id": "AXsQ6RdZzg", "reviewer": "Reviewer_Gbx2", "summary": "This paper targets missing data imputation for graph data. The authors highlighted that existing propagation-based methods produce nearly identical values within each channel and they contribute little to graph learning. To resolve this limitation, the authors propose a propagation-based imputation scheme that consists of two diffusion stages. First, the method imputes the data using existing propagation-based methods in which the data obtain the low-variance channels. Then the method removes all the imputed features in the low-variance channels and generates a synthetic feature by injecting random noise into a randomly selected node. Finally, the method diffuses both the observed and synthetic features to produce the final imputed features which have distinct imputed values for those channels. The experiments show that the methods increase the variance of imputed values for different channels so the graph learning tasks like semi supervised node classification and link prediction.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely appreciate the reviewer’s positive evaluation of our work and the absence of noted weaknesses. We thank the reviewer for recognizing that the claims in our paper are supported by clear and convincing evidence, and for highlighting the clarity of the writing, the soundness of the theoretical analysis, and the comprehensiveness of the experiments, including ablation studies and scalability. That said, we noticed that the reviewer’s overall recommendation was “Weak Accept (i.e., leaning towards accept, but could also be rejected).” If there are any remaining concerns or suggestions for improvement that we may have overlooked, we would greatly appreciate your feedback and are ready to address them promptly.\n\nThroughout the rebuttal period, we have conducted the following additional discussions on our proposed method to further strengthen our paper, all of which will be included in the revised manuscript:\n* Generalizability across downstream GNN architectures\\\n(see **Table 30**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2030.png)\n* Ablation study on the use of synthetic features\\\n(see **Table 32**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2032.png)\n\n* Description of the algorithm\\\n(see **Algorithm 1**: https://anonymous.4open.science/r/ICML12446-AF4E/Algorithm%201.png)\n\n* Applicability to existing imputation methods as additional channels\\\n(see **Table 34**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2034.png)\n\n* Effect of the number of additional channels with synthetic features on performance\\\n(see **Table 35**: https://anonymous.4open.science/r/ICML12446-AF4E/Table%2035.png)\n\nWe hope that these additions and clarifications help address any remaining uncertainties and reinforce your confidence in the significance of our work. If the reviewer finds our responses satisfactory, we would be sincerely grateful if you would consider revisiting your overall recommendation.", "claims_and_evidence": "The claims in the paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the target problem.", "theoretical_claims": "The overall proofs in the supplementary are sound.", "experimental_designs_or_analyses": "The experimental designs is comprehensive with different data set and methods are included mainly for semi supervised node classification and link prediction. And effects of hyperparameter and ablation study are included which are detailed in the supplementary.", "relation_to_broader_scientific_literature": "The study is focus on graph missing data Imputation which is applicable to any domain that have graph data which suffer from missing issues such as social network that contain many missing features for people in the network.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n 1.The writing, visualization and the organization of the paper is clear. And comprehensive experiments includes many data set and methods. In particular, ablation study, effect of hyperparameters and scalability are also included to make the work more solid.\n\n2.Theretical proof is derived to show the convergence of diffusion stages and show why channel-wise inter-node diffusion produce similar imputed values for the channel where the known features have similar values.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "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": "", "extra_scores": {}}, {"review_id": "sExTfmWSX8", "reviewer": "Reviewer_7yBY", "summary": "This paper identifies the problem of having low-variance channels after diffusion with mostly missing values. This happens when the available states are very similar. They propose adding random features to those channels and restarting the diffusion process with these synthetic features and the original low-variance features, which leads to higher-variance features. Experimental results show improvements on downstream tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We greatly appreciate the reviewer’s detailed and perceptive comments. \n\nFirst of all, we would like to clarify that propagation-based imputation methods for graph learning with missing features are designed to assign values to missing features in a way that improves downstream task performance. Accordingly, these **imputation methods preserve the original dimensionality of the feature matrix in their output**. In this context, our work focuses on addressing a limitation of current propagation-based imputation methods identified in this study.\n\n> **Q1.** A channel has some meaning, so why would a random feature at a random node make sense?\n\nYes, each channel has its own meaning. However, when a channel is filled with nearly identical values, such a low-variance channel contributes little to downstream tasks. Our goal is to **make that channel, which has become uninformative for downstream tasks, useful**. As the reviewer pointed out, while the synthetic feature may not preserve the original meaning of the channel, it helps to restore distinctiveness within the channel, leading to performance improvements in downstream tasks.\n\n> **Q2-2.** Evaluate whether removing low-variance channels matters.\\\n> **Q2-1.** If the authors are convinced that the low-variance features are beneficial, an experiment should be conducted to compare it to the case when dropping the low-variance features.\n\nTo show that observed features within a low-variance channel are beneficial in addition to the synthetic feature, we conduct additional experiments comparing FISF to FISF-OSF—a variant that performs the final diffusion process in low-variance channels using only synthetic features, without observed features. Table 33 presents the results; **the superior performance of FISF highlights the importance of using low-variance observed features**. FISF leverages the fact that the observed features within a low-variance channel have nearly identical values by preserving and diffusing them during the diffusion process, thereby making use of the remaining feature information.\n\n**Table 33:** https://anonymous.4open.science/r/ICML12446-AF4E/Table%2033.png\n\n> **Q3-1.** I would not see your method as an imputation method but as adding structural information from which any imputation method can benefit.\\\n> **Q3-2.** Apply FISF to other imputation methods as additional channels.\\\n> **Q3-3.** Compare the additional channels to other positional encodings.\n\nWe agree with the reviewer’s perspective that diffusion with synthetic features can be viewed as a way of adding structural information, and that this approach can also be applied to other imputation methods as additional channels. To address the reviewers’ concerns, **we conduct additional experiments in which FISF is applied to other imputation methods as additional channels** (denoted as FISF$^+$). We **further compare FISF$^+$ with Laplacian Positional Encoding (LPE) [1] and Random Walk Positional Encoding (RWPE) [2]**. Table 34 shows the results. As shown in the table, while LPE and RWPE generally improve the performance of existing imputation methods by providing structural information, **FISF$^+$ consistently achieves the most significant performance improvements**. Unlike positional encodings, our approach can use the feature information preserved in low-variance channels.\n\n**Table 34:** https://anonymous.4open.science/r/ICML12446-AF4E/Table%2034.png\n\n> **Q4.** Evaluate how many additional channels with synthetic features improve results.\n\nIn FISF, the number of channels into which synthetic features are injected is controlled by the hyperparameter $r$, and its effect was analyzed in Appendix C.8. However, in the context of FISF$^+$, **we conduct additional experiments to evaluate how many additional channels with synthetic features improve results**. Table 35 shows the results. As shown in the table, **even a small number of additional channels using FISF$^+$ leads to substantial performance improvements**. We further observe that, for each dataset, the optimal number of additional channels tends to lie near the number of channels into which the original FISF injects synthetic features.\n\n**We will cite the insightful references provided by the reviewer [1, 2] and include all the experimental results presented above in the revised manuscript**.\n\n**Table 35:** https://anonymous.4open.science/r/ICML12446-AF4E/Table%2035.png\n\n> **Q5.** Your method is not permutation equivariant as a random node is chosen, which should be noted but is generally fine for the applications that are considered.\n\nWe agree that, while our method is not permutation equivariant due to the random node selection, this has not posed any practical issues in the applications considered. We will explicitly note this property in the revised manuscript for clarity.\n\n[1] \"Benchmarking graph neural networks.\" JMLR 2023.\\\n[2] \"Graph neural networks with learnable structural and positional representations.\" ICLR 2022.", "claims_and_evidence": "Claims and Evidence are generally fine.", "methods_and_evaluation_criteria": "* There is no clear motivation for injecting random node states into existing channels.\n* A channel has some meaning, so why would a random feature at a random node make sense?\n* To me, the method is more like dropping low-signal channels and then adding new channels with your proposed diffused signal.\n* As your method puts a higher influence on the synthetic features for diffusion, this seems to already be in the same direction, so you do not need the original low-variance features.\n* If the authors are convinced that the low-variance features are beneficial, an experiment should be conducted to compare it to the case when dropping the low-variance features.\n\n* A diffusion process with random features will provide structural information, e.g., which nodes are closely connected and far apart. This is no longer related to the original features.\n* Consequently, the proposed method can be seen as a positional encoding that adds the diffused features as additional channels to a graph.\n* Thus, I would not see your method as an imputation method but as adding structural information from which any imputation method can benefit.\n* Your method is not permutation equivariant as a random node is chosen, which should be noted but is generally fine for the applications that are considered.\n* Experiments should, therefore, compare first and foremost with methods for positional encoding, not with imputation methods.", "theoretical_claims": "Theoretical claims only concern the convergence of diffusion processes, which is always given.", "experimental_designs_or_analyses": "* To me, the experiments do not evaluate the interesting parts of this method.\n\nIt would be interesting to:\n* Apply FISF to other imputation methods as additional channels.\n* Compare the additional channels to other positional encodings.\n* Evaluate whether removing low-variance channels matters and how many additional channels with synthetic features improve results.", "relation_to_broader_scientific_literature": "The paper relates nicely to literature on imputation methods. Connections to positional encodings are essential but are missing.", "essential_references_not_discussed": "References to positional encodings are missing, e.g., the following:\n\n\nLaplacian Positional Encoding: Dwivedi et al., Benchmarking graph neural networks, JMLR 2023.\nRandom Walk positional encoding: Dwivedi et al., Graph neural networks with learnable structural and positional representations, ICLR 2022.", "other_strengths_and_weaknesses": "I like the idea of adding structural information to tasks with missing features. There seems to be a lot of potential, I just wish that this paper went a bit deeper.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Post-rebuttal, all reviewers have converged on an acceptance recommendation, with their primary concerns addressed. After reviewing the paper and rebuttal, I agree that the work makes a meaningful contribution to missing data imputation for graph data. I recommend acceptance. Please ensure that the necessary revisions are incorporated into the final version.
Decision: Accept (poster)