FSD-CAP: Fractional Subgraph Diffusion with Class-Aware Propagation for Graph Feature Imputation
Authors: Xin Qiao
Shijie Sun
Anqi Dong
Cong Hua
Xia Zhao
Longfei Zhang
Guangming Zhu
zhang liang
Venue: ICLR 2026 Poster (2026)
Keywords: incomplete graph learning
graph feature imputation
feature propagation
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a two-stage framework for graph feature imputation, comprising fractional subgraph diffusion and class-aware propagation steps, enabling robust representation learning, particularly in scenarios with high missing rates.

Abstract: Imputing missing node features in graphs is challenging, particularly under high missing rates. Existing methods based on latent representations or global diffusion often fail to produce reliable estimates, and may propagate errors across the graph. We propose FSD-CAP, a two-stage framework designed to improve imputation quality under extreme sparsity. In the first stage, a graph-distance-guided subgraph expansion localizes the diffusion process. A fractional diffusion operator adjusts propagation sharpness based on local structure. In the second stage, imputed features are refined using class-aware propagation, which incorporates pseudo-labels and neighborhood entropy to promote consistency. We evaluated FSD-CAP on multiple datasets. With 99.5% of features missing across five benchmark datasets, FSD-CAP achieves average accuracies of 80.06% (structural) and 81.01% (uniform) in node classification, close to the 81.31% achieved by a standard GCN with full features. For link prediction under the same setting, it reaches AUC scores of 91.65% (structural) and 92.41% (uniform), compared to 95.06% for the fully observed case. Furthermore, FSD-CAP demonstrates superior performance on both large-scale and heterophily datasets when compared to other models. Codes are available at https://github.com/ssjcode/FSD-CAP.

Published as a conference paper at ICLR 2026
FSD-CAP: FRACTIONAL SUBGRAPH DIFFUSION WITH CLASS-AWARE PROPAGATION FOR GRAPH FEATURE IMPUTATION
Xin Qiao'; Shijie Sun'; Anqi Dong²; Cong Hua', Xia Zhao', Longfei Zhang', Guangming Zhu', Liang Zhang'
Xidian University, Xi'an China
2KTH Royal Institute of Technology, Stockholm, Sweden
Hunan Institute of Advanced Technology, Hunan, China
(x iking singiia,, ssJ, dr chua } @stu. x xidian edu. en, angidong. andy@gma com (zhaoxia, a, gmzhu, 1i Hingzhang| @xidian. edu. cn
ABSTRACT
Imputing missing node features in graphs is challenging, particularly under high missing rates. Existing methods based on latent representations or global diffu- sion often fail to produce reliable estimates, and may propagate errors across the graph. We propose FSD-CAP, two-stage framework designed improve impu- tation quality under extreme sparsity. In the first stage, graph-distance dit-tate---ggudeed subgraph expansion localizes the diffusion process. A fractional diffusion oper- ator adjusts propagation sharpness based on local structure. In the second stage, imputed features are refined using class- aware propagation, which incorporates pseudo-labet and neighborhood entropy to promote consistency. We evaluated FSD-CAP on multiple datasets. With 99.5% of features missing across five bench- mark datasets, FSD-CAP achieves average accuracies of 80.06% (structural) and 81.01% (uniform) in node classification, close to the 81.31% achieved by a stan- dard GCN with full features. For link prediction under the same setting, reaches AUC scores of 91.65% (structural) and 92.41% (uniform), compared to 95.06% for the fully observed case. Furthermore, FSD-CAP demonstrates superior per- formance on both large-scale and heterophily datasets when compared to other models. Codes are available at httpss///tttub.ccm////oo/////saf
INTRODUCTION
Graph Neural Networks (GNNs) are widely used for learning from graph-structured data, with suc- cessful applications in social networks (Bian et al. 2020), biology (Li et al. (022). and recommen- dation systems (He et al. 2020). GNN architectures(Chen et al., 2023] Chien et al. 2020) always assume nodal features neighboring nodes. In practice, this assumption often fails. Node attributes are frequently missing due to privacy constraints, sensor failures, incomplete data collection. High missing rates disrupt the message-passing process and significantly degrade model performance.
fully observed, allowing information to be aggregated effectively from
A variety of methods have been proposed for imputing missing features, including statistical timators (Srebro et al.] 2004), machine learning models (Chen & Guestrin (0166), and generative approaches (Vincent al. 2008). Recent work has shifted toward deep learning techniques that model the distribution of node attributes. These include latent space models that align observed fea- architectures designed to operate on incomplete inputs (Taguchi et al. 2021). These approaches, which rely on correlations in both feature and graph structure, are effective under moderate missing rates but ex- perience significant performance degradation as sparsity increases, ultimately falling below simple basclines like zero-filling or mean imputation in highly incomplete settings/You et al. 2020).
tures with learned embeddings (Chen et al.] [2020] Yoo et al.) (002). and
"Equal contribution. Corresponning author.

---

Published as a conference paper at ICLR 2026
Input:
g
X
Output: X
FSD ATM
A 7 A
CAP
X
W
?
W
? ...
?
W
?
Known
W
Completed
?
Missing
Figure 1: FSD-CAP Pipeline: Given graph 9 and partially observed feature matrix X, FSD-CAP
recovers the full matrix X. (i) FSD: Starting from observed nodes, it gradually expands the radius of the subgraph and performs progressive subgraph diffusion using fractional diffusion operators A 7.0 A A 7.2 producing preliminary imputed feature matrix. (ii) CAP: Based on the FSD-imputed features, pseudo-labels are assigned by classifier to form class-wise graphs, each associated with class-specific X and W Feature propagation within each class graph yields the final output X.
An alternative class of methods, based on diffusion, propagates observed features across the graph under the assumption of node homophily (Rossi al.] [002]] Um et al. 2023] Wang et al. 2024). These methods are typically lightweight, parameter-frees and more robust under high missing rates. However, most diffusion approaches apply uniform propagation across nodes, without accounting for local structure propagation order. As result, nearby reliable signals may be underused, particularly in sparse or large-scale graphs. Additionally, these methods often ignore variation in connectivity and feature distribution, leading to over-smoothing and reduced discriminative power in the imputed features.
We propose Fractional Subgraph Diffusion with Class-Aware Propagation (FSD-CAPP, diffusion- based framework for imputing missing features on graphs. The method is designed to improve robustness under feature sparsity and adapt to local structural variation. FSD-CAP consists of three components. First, a fractional diffusion operator modulates the sharpness of propagation based on local graph structure. This operator generalizes standard normalization by interpolating between uniform averaging and dominant- neiihbr selection, allowing it to adapt to varied connectivity. Second, to reduce error accumulation from global diffusion, we introduce a graph-distance-guidde subgraph expansion strategy. This mechanism begins with observed nodes and progressively in- cludes less certain regions, enabling early reliable estimates and improved stability. Third, class- aware refinement step uses pseudo-labels and neighborhood entropy to enhance the imputed fea- tures, promoting intra-class consistency and inter-class separation. In the tasks of semi-supervised node classification and link prediction five benchmark datasets, this method consistently out- performs state-of-the-ar imputation approaches and maintains robustness across a wide range of missing rates. Notably, datasets such CiteSeer and PubMed, FSD-CAP exhibits higher per- formance under extreme missing conditions compared to when utilizing fully observed features, thereby demonstrating its effectiveness sparse scenarios. Furthermore, when compared other models, FSD-CAP also achieves superior performance on two large-scale datasets and four het- erophilous datasets, showcasing its strong adaptability (Appendix A.2.7 and Appendix A.2.8)
PROPOSED METHOD
2.1 PRELIMINARIES AND OVERVIEW
Our objective is to learn from graphs with incomplete node features, focusing two common set- tings: structural missing, where some nodes have no observed features, and uniform missing, where entries are randomly missing across the feature matrix. The goal is impute missing attributes in way that enables robust representation learning especially under high missing rates where standard GNNs fail. To this end, propose two-stage imputation framework designed to stabilize learning and adapt to local graph structure. The overall architecture is shown Figure T and consists of the following three key components.
2

---

Published as a conference paper at ICLR 2026
(i) Fractional diffusion operator. We generalize the standard diffusion matrix (Gasteiger et al. 2019) by introducing a fractional exponent that controls the sharpness of propagation (Section 2.2 This operator interpolates between uniform averaging and nearest-neighbor routing, allowing infor- mation to diffuse adaptively according to local graph structure and thus emphasizes reliable signals and mitigates over-smoothing.
(ii) Progressive subgraph diffusion. We propagate information through a structured, layer-wise expansion from observed unobserved nodes (Section(2.3), instead of global diffusion (Rossi al. 2022]. At each step, only a localized subgraph is updated, thereby reducing error accumulation and improving stability. It prioritizes say-tto-ommplee nodes in early stages and gradually expands to uncertain regions.
(iii) Class-level feature refinement. We construct synthetic class-level features using pseudo-labels and neighborhood entropy (Section (.4) to improve the discriminability of features. These signals are propagated within intra-class graphs to refine feature estimates and improve semantic consis- tency. This step promotes intra-class coherence and preserves inter-class distinctiveness, reducing over-smoothing across class boundaries.
Before presenting the technical details, we introduce the notation used throughout this section. Let (V.E) denote an undirected graph, where V = {81, "2,,...,,N' the set of N nodes and E V V is the set of edges. Each node is associated with a feature vector in IR and collect all node features in a matrix X RNFF where X[k.] denotes the feature vector of node Vk- The topology of the graph is represented by an adjacency matrix A E {0, 1)NxN where otherwise. The corresponding degree matrix D e ENNN is diagonal, with entries D = Σソー A.j. To represent missing features, we define a binary mask matrix M (0, 1)NF,, where M& 1 if the f-th feature of node vk is observed, and MR otherwise. Proofs of theoretical results in this section are included in the supplementary material.
V
A.j 1 U,) E & and Ay
2.2 FRACTIONAL DIFFUSION OPERATOR
Diffusion-based imputation methods typically rely on the symmetrically normalized adjacency ma- trix A D- 1/2 AD-1/2 which defines lazy random walk over the graph (Rossi et al. 2022 Malitesta et al. 2024 Chen et al. 2016 Dong et al. 20226b a). This operator assumes uniform mix-
ing across neighbors, failing to account for differences in node distributions (Ji al. 2023). which may result in over-smoothing and diminished feature discriminability. To address this, we introduce fractional diffusion operator that adjusts the propagation behavior using tunable sharpness pa- rameter y >> O. The key idea is to amplify or suppress the relative influence of neighboring nodes through elementwise exponentiation followed by row normalization. Specifically, the fractional dif- fusion matrix A E RNXN is defined as
N
AJ, = (AU) Σ (An)))
(1)
This transformation preserves the row-stochastic property of A while reweighting neighbor contri- butions based on edge strength. For y < 1, weaker edges are amplified, resulting in smoother, more uniform propagation. For 7 > stronger edges are emphasized, leading to sharper, more localized diffusion. The standard normalized diffusion is recovered when 7 =
Proposition 1 (Limiting behavior of A"). Let A be the symmetric normalized adjacency matrix of connected graph, and A as in equation] 7
We have
if Aig > 0
A1 = {1 if j arg max, Aik
lim AG 7-0
and
lim 70000
(2)
otherwise
(0 otherwise
where (ii) = [ A, > 0} denotes the set of neighbors of node i.
Proposition [ demonstrates that acts as a locality parameter, i.e., small values encourage broad, uniform mixing across neighbors, while large values concentrate diffusion along the most prominent edge, resulting in highly localized propagation.
Remark (Super-diffusion and neirbst- routing). For 7 >> 1, the diffusion process enters super-diffusion regime, where high-weight edges exert disproportionately strong influence.
3

---

Published as a conference paper at ICLR 2026
As increases, the weights in A become increasingly concentrated around the largest entry, leading to highly localized propagation. In the limit 7 - oc, the process reduces to deterministic routing, where each node transfers its mass entirely to its strongest neighbor.
The effect of the fractional exponent on the propagated features X == A where X is the input feature matrix, is formalized Theorem !
Theorem (Fractional diffusion on feature propagation). Let A and A denote the lazy transi- tion and fractional diffusion operator as defined in equation 7 respectively. For any feature matrix X TR. XxF, define the propagated features by X" A X. Then for each node i, have
1
lim 7-01
Σ JEN())
Xb
and
lim X1.1 [
[e.:]
IV(1)
7
where (i) ti Aij 0} the neighborhood of and j arg maxk An is the index of its strongest neighbor.
2.3 PROGRESSIVE SUBGRAPH DIFFUSION
In graph learning, nodes that are closer in the graph topology are generally considered to exhibit stronger feature similarity (You et al. 2019 Zhang & Chen, 2018). Motivated by this principle, we design progressive subgraph diffusion strategy that replaces global propagation with a distance- aware, layer-wise process. Rather than diffusing information uniformly, the method propagates features hierarchically from observed regions to unobserved ones. Nodes closer to observed features are imputed more accurately (see, e.g., Appendix A.2.3), reinforcing the design choice of localized, incremental expansion to preserve reliable signals and limit early error propagation.
We now define subgraph construction at the level of individual feature dimensions. For each feature f, let V4 = {ux E Mat = 1} denote the set of nodes with observed values, and V := V V denote the set with missing values. The initial subgraph ( is formed over V using adjacency relations inherited from the original graph G. Since observed features may be spatially sparse or fragmented, (()) typically consists of multiple disconnected components. Next, to complete the feature progressively, we expand the subgraph in layers by incorporating nodes from V based on their shortest-path distance to VL. At layer m, the subgraph ((m) includes all nodes within distance of VL. forming the radius-m neighborhood p(m), along with all edges among those nodes. As m increases, the subgraph expands outward and disconnected regions gradually merge. In the limit, when m equals the graph diameter, the subgraph (1") recovers the full graph G.
At each layer-m subgraph, we apply fractional diffusion described in Theorem I jndeppendently to each connected component. Let G.(²) denote the i-th connected component of g(m)), with corre- sponding adjacency matrix A The fractional diffusion operator this component is defined as A 7.m = A x (g(")), using the formulation in equation Let (m)) (t) denote the value of node ;; in each feature channel at iteration the diffusion update is thus given by
(m)) (t) = Σ
A m
(m) 1),
(3)
(6)
where (1mm is the neighborhood of node in ((m).
As the subgraph expands with increasing m. it gradually includes more distant nodes, which may carry unreliable or noisy information. This expansion can degrade the accuracy of features imputed in earlier layers. To address this, we introduce a retention mechanism that stabilizes updates by blending new estimates with those from previous layers. Additionally, we enforce a boundary con- dition to preserve observed features throughout the diffusion process. Let M denote the binary mask matrix. At each iteration L,..., K, the channel-wite wise update rule for node U; is given by
[m) (t)
(0) 3 M, +
x (m)) (t) Az; 1) (K) @ -,),
(4)
where @ denotes the Hadamard (element (iemmnntwwise product and z (m-1) (K) represents the converged result of node 22 from the previous layer after K iterations that weighted by X.
4

---

Published as a conference paper at ICLR 2026
This update ensures that observed features remain fixed across all iterations, while missing values are updated based on a blend of current estimates and the previous layer's ' outputs. As m increases, this retention mechanism promotes stability and gradual refinement, improving the reliability of imputed features across the diffusion process. After propagation steps using the update rules in equation 3 and equation 4 obtain refined estimate z²t") (K) for each node u v(m) in each feature channel, corresponding to the m-th layer subgraph G(mm), As K + oc, the recursive updates converge to a fixed point. The following result establishes convergence of this process under fractional diffusion.
Theorem (Convergence of subgraph diffusion). Let A(m) be the adjacency matrix of the m-th layer subgraph G(m), and let A ym denote its fractional diffusion matrix as defined equation / Let (m)) E Ik (vl' be the feature vector in channel f, where missing entries are initialized to zero. Let X > denote the retention coefficient, and M be the binary mask vector for observed entries in channel f. Define the update sequence by
am(m) x.)) MMM++ (A3.m) (1- (1-1) 1) + Xa (mx (K) o (1 (1- 1=1,..., K
Then, for sufficiently large K, the sequence x x!")(t) converges to a fixed (unique) state.
Theorem guarantees that the iterative update process each subgraph leads well-defined steady-state solution for missing features. By incorporating a retention factor, the method balances the influence of prior estimates and newly propagated information, thereby limiting error accumu- lation across layers. As the subgraph expands with increasing radius, progressively more nodes are included, and more structural context is captured. Theorem 3 shows that under mild assumptions, this layer-wise refinement converges to the solution that would have been obtained by applying the diffusion update over the entire graph at once. In this way, the global behavior of the model recovered as the natural limit of consistent local operations.
Theorem 3 (Global convergence via progressive subgraph expansion). Let G(m) be the m-hop expansion of the observed node set Vi. in channel f, and let x!(m) be the corresponding feature estimate after applying the masked fractional diffusion update defined in Theorem 2 Assume the graph G is connected and the diffusion sharpness parameter y is finite. Then, as m - Mmax and g(m) G. the final estimate z. 2=(m) converges to the steady-stare solution of the full full-graph diffusion update.
2.4 CLASS-LEVEL FEATURE REFINEMENT
After computing the feature matrix using fractional and subgraph diffusion (Sections 2.2 and 2.3) we perform a class-guided refinement step. This stage is motivated by the observation that, under high missing rates, most features must inferred from a sparse set of observed values. Diffu- sion alone tends to blur discriminative patterns, especially when semantic boundaries are inherently weak. Class-level propagation addresses this issue by injecting semantic structure into the imputa- tion process to improve feature quality under severe sparsity.
We begin by assigning pseudo-labels to unlabeled nodes using a semi-supervised classifier based on standard GCN architecture (Kipf & Welling 2016a). Let V, C V denote the set of labeled nodes with ground-trume truth labels y, and let Vaz = V be the set of unlabeled nodes. For each predict a pseudo-label
node in Vuz. class e E C, we construct a class-specific graph by introducing a synthetic class node connected to all nodes in G with missing features and predicted label c. Feature propagation within each class graph is then performed, with the synthetic node serving as a class-level anchor. This step promotes intra-class consistency and strengthens inter-class separation, resulting in more robust downstream representations.
while preserving the true labels in Vz. Then, for each
To account for potential errors in pseudo-label assignments, we introduce a credibility weight based on the entropy of neighborhood label distributions. This score modulates each node's 's contribution its class feature according to the consistency of local labels.
Definition (Neighborhood label information entropy). Let NGU denote the extended neighhorhood of node ii including itself. For each class E C, with 1() is the indicator function,
5

---

Published as a conference paper at ICLR 2026
define the normalized label entropy
S = -1/11o (WVI))
P((c) log (P.(c)) with P.(c) = (1/Waa) JEN;
Σ
1 (ūs m))
(5)
AEC
The entropy score S; lies in the range [0, 1J. where lower values indicate greater label consistency in the neighborhood of node i, and higher values reflect uncertainty. When S; is small, the node more representative of its assigned class and should contribute more when computing the class feature. Conversely, nodes with high entropy may not provide reliable class information and are thus down-weighted. To capture this, we assign each node a confidence weight of S and compute class-specific feature ((a) as weighted average of features from all nodes assigned to class c by
(1 S.) zi) (1 (1)).).
(1
(
where T; the observed/imputed feature of node Us and d(o) is the aggregated class feature for class c.
To incorporate class-specific information into node features, introduce a virtual class node v(() for each class c, initialized with an aggregated class feature vector zie). For each class, we construct
a class graph g(e) = (Vic), ()()), where the node set D(e) includes the class node y(*) and the set y(e) of nodes in G with missing features and pseudo-label Each class graph includes self-loops for all nodes and directed edges from the class node (()) to every node in ylo). These edges allow class- level information to flow toward incomplete nodes, guiding feature refinement. The corresponding
feature matrix X for ((+) is defined by X [x(s) =ig]"", wherein x(e)
e < X contains
the features of nodes in (())) imputed during the earlier stage, and stc) E IRIF is the class anchor feature assigned the virtual node e(()
In the gre-clasifiicatio GCN, the final layer maps each node embedding 2; to a class probability distribution y,. These probabilities reflect the discriminative confidence of the node across classes and can be used to guide class-level propagation. We apply a temperature-scaled softmax to control the sharpness of this distribution y; softmax(z:/" (T), where T 0 is temperature parameter. The scalar value y; assigned to the predicted class serves as the self-loop weight, while (1 - y:) is used for the incoming edge from the class node.
We construct weighted adjacency matrix W()) to perform diffusion within each class graph (()). The class node is placed last in the node ordering. For each node in v(e) the diagonal entry w set its predicted class probability ý.. The entry (e Lels set 1 1- û.. allowing class-level information to flow toward uncertain nodes. The class node has self-loop with weight 1. All other entries zero Feature refinement performed using single propagation step (e) ((e) (e), where (e) contains the imputed node features and the class anchor. After processing all class graphs, the refined features are mapped back to their original node indices. Observed features are then restored to produce the final output matrix X, and passed to the downstream GNN for prediction.
EXPERIMENTS
3.1 EXPERIMENTAL. SETUP
Datasets. We evaluate our method on five benchmark datasets: three citation networks (Cora, CiteSeer, and PubMed) (Sen al. 2008), where nodes represent papers and edges indicate citation links; and Amazon co-purchase networks (Photo and Computers) (Shchur et al. 2018), where
nodes are products and edges connect items frequently bought together. Additional dataset details
For example, the matrix with incomplete nodes reads Wie)
D
1 61
where the class
node corresponds the last row and column.

---

Published as a conference paper at ICLR 2026
To simulate missing features, randomly remove node attributes according to a missing rate parameter my, under two settings: Uniform Missing. A random my percentage of feature entries in the matrix X is masked and set to zero, simulating cases where nodes have partially missing attributes; Structural Missing. A random mr percentage nodes is selected, and all features associated with those nodes masked, modeling cases where some nodes lack features entirely.
provided in Appendix A.3.1
Baselines. We compare against three baseline models and four state-of-the-ard methods from both deep learning- -based and ttffusion-based approaches. Zero (Baselinel) sets all missing feature val- ues to zero and applies a standard GCN (Kipf & Welling, (2016a). PaGCN (Baseline2) (Zhang et al. 2024) uses partial graph convolution over observed features without modeling missingness. FP (Baseline3) (Rossi et al., 2022) performs direct feature propagation using the normalized ad-
jacency matrix. Among state-of-the-ar methods, GRAFENNE (Gupta et al. (002) constructs three-phase message-passing framework to learn on graphs. ITR (Tu et al., 2022) and ASD-VAE [Jang al., 2024) utilize the distribution relationship between attributes and structures for feature completion. PCFI (Um et al., 2023) incorporates inter-node and inter-channel correlations through confidence-aware diffusion.
Evaluation settings and implemenntatin.. We evaluate FSD-CAP on semi-supervised node clas- sification and link prediction tasks. For node classification, we follow the setup in Gasteiger et al. (2019), selecting 20 nodes per class from a random pool of 1500 nodes used for training and valida- tion; the remaining nodes are used for testing. Classification accuracy is used to assess imputation quality. For link prediction, we adopt the edge split from Kipf & Welling (2016b), using 85% of edges for training, 5% for validation, and 10% for testing. AUC and AP are used as evaluation metries.
We average results over 10 random data splits and report the mean and standard deviation of accu- racy, AUC, and AP. Hyperparameters are selected by grid search on the validation set. For baselines, adopt the settings from the authors' released code or papers; when such settings are unavailable, we run a grid search over a reasonable range. Additional details are provided in Appendix(A.3. A.3.5 and Appendix A.3.6
3.2 SEMI-SUPERVISED NODE CLASSIFICATION
We evaluate how classification accuracy varies with the missing rate mr in the semi-supervised node classification task. The missing rate is increased from 0.6 to 0.995, and all methods are tested under both structural and uniform missing scenarios. Re- sults for the Cora and CiteSeer datasets are shown in Figure 2 additional results for PubMed, Photo, and Computers are provided in Appendix A.4.1
(Btructura))
(Struduraa)
Accusssy (16)
0381
87
11
631
1
Cara (Uniform)
CiteSeer (Unifor))
Accusscy (10)
As mr increases, the accuracy of all methods de- clines. Latent-space approaches (TTR and ASD-
VAE) exhibit significant performance degradation high missing rates. In contrast, FSD-CAP re- mains robust across datasets and maintains compet- itive accuracy even at mr 0.995. Diffusion- based methods generally outperform latent-space methods, with FSD-CAP consistently achieving the best performance. Compared to the strongest bascline, PCFI, our method shows larger gains as the missing rate increases.
Mixxing fenture
Missing festure ratio
Zero
PAGCN
ITR
GRAPENNE
ASD- VAE
FBD-GAP
Figure 2: Node classification accuracy (%) comparison on Cora and CiteSeer datasets with mr E {0.6, 0.7, 0.8, 0.9, 0.95, 0.995). The top row displays results for structural missing, while the bottom row shows results for uniform missing. Methods that encounter out-of-memory errors or are not applicable to specific missing scenarios are excluded from the corresponding plots.
As shown in Table I we report node classification accuracy for all methods across five datasets fixed missing rate mr = 0.995. ITR is designed specifically for structural missing scenarios, where
7

---

Published as a conference paper at ICLR 2026
Table I: Accuracy (%) comparison for node classification mr 0.995. Bold values indicate the best performance; underlined values indicate the second-best. "OOM" denotes out-of-memory errors. "_" indicates methods that are not applicable under the given missing setting.
Structural Missing
Dataset
Fuull Features
Zera
PaGCN
GRAFENNE
ITR
ASD VAB
PCF
FSD CAP
82.72
8.69
5.29
59.37
30011 0.55
75.36
1.86
CiteSoer
70.00 : 1.35
31.29 1504
24.24
1.63
2
23.43
33.83
1.44
27.85 + 3.93
66.06
2.778
71.94
1.32
PubMed
77.46
5.00
41.84
00M
OOM
2.11
Photo
91.63 0.62
79.04
2.26
64.31
86.34
1.09
50.73
7
3.98 30,85 + 8.95
87.38
1.04
89.18
0.97
Computers
84.72 1.25
71.71
77.19 2.36
2.16
40.31 6.26
00M
OOM
78.71
1.49
81.64
1.21
Average
88131 + 1,38
54,34 4:554
48.54
73.68 + 2.36 3
OOM
OOM
76.39
1.86
80,06 1.21
Uniform Missing
Dataset
Full Features
Zero
PaGCN
FP
GRAFENNE
II
VAE
PCFI
FSD USDD-CAP
Cora
82.72 1.61
63.37
2.02
62.21
1.83
78.36
1.76
39.86
4.81
33.22 + 5.27
78.55 + 1.37
81.49
1.95
CitcSear
70.00 1.35
53.66 2.65
28.58
65,31
29.65
2.76
41.65 8.90
1.87
73.15
0.98
PubMed
77 2.09
54,26
2.68
41
2.00
73.74
2.18
44,43
1.39
0OM
76.01 + 1.64
77.46
1.15
Photo
91.63
84.96
1.25
85.61
0.69
88.04 + 1.53
51.39
5:21
32.45 + 14,95
88.55
1,26
89.40
0.94
Computers
84.72 1.25
78.99
1.04
77.58 a 1.66
80.67
a 1.46
36.98
2.25
OOM
81.64
a 1.05
83.57
0.95
Average
81,31
66.005 3.08
40.46
OOM
78.77 1.44 81.01 1.19
nodes are either fully observed or entirely missing, and cannot be applied to uniform missing set- tings. We therefore report its performance only under structural missing.
Our method consistently achieves the highest accuracy across all datasets at 0.995. In ex- treme missing scenarios, several deep learning-baad based methods such as GRAFENNE and ASD-VAE perform worse than the simple zero-filling baseline (Baselinel). On large-scale datasets like Photo and Computers, both ASD-VAR and ITR fail with out-of-memory errors, highlighting their limited scalability. In the structural missing setting, FSD-CAP outperforms the best-performing baseline (PCFI) with a relative improvement of 6.90% on Cora, computed as (80.56 - /5.36)/75. /7..66 x 100% 6.90%. It also achieves gains of 8.90%, 3.41%, 2.06%, and 3. 3.72% on CiteSeer, PubMed, Photo, and Computers, respectively. Under the uniform missing setting, where only 0.5% of node features are retained, FSD-CAP reaches average accuracy comparable a GCN trained on fully ob- served features. Notably, on CiteSeer, it even surpasses the performance of the GCN with complete features.
3.3 LINK PREDICTION
Table reports AUC and AP scores for the link prediction task on five datasets at mrr 0.995. Due to severe performance degradation of some methods under high missing rates, we restrict the comparison to ITR and the diffusion- methods FP and PCFI. As before, ITR is applicable only to structural missing and fails with of-momory errors on large-scale datasets.
Our method consistently outperforms both FP and PCFI across all datasets and missing types, with the sole exception of the AP metric on PubMed. These results confirm that our approach remains effective under extreme feature sparsity in both classification and link prediction tasks.
0.995. OOM denotes out of memory- The bold and underlined represent the best and the suboptimal performance (%), respectively.
Table 2: Performance comparison for link prediction
Datasct
Metric
Full Features
Structural Missing
Uniform Missing
ITR
FF
PCFI
FSD-CAP
FF
PCF
FSD-CAP
AIC
92.12
82.01
2.73
84.79 + 1.99
85.94
1.49
87.97
1.24
87.02
1.26
86.85
1.69
90.01
1.10
Cora
AP
92.45
0.72
83.76
2.87
87
2.46
8795
: 1.20
88.50
1.18
89.17
0.83
88.86
1.15
90.66
0.75
CiteSeer
AUC
91.022
71.35
3.25
81.40
1.32
80.13
1.80
87.48 = 0.96
82.44
2 1.50
82.98
1.78
87.70
= 1.09
AP
91.59 1.20
73.30 +
83.62
+ 1.52
83.72
1.58
87.82
1.19
86.11
1.60
88.23
1.16
AUC
0.200
0OM
00.43
82.68
0.70
88.39
= 0.57
86.32220.2
84.46
88.50
= 0.45
PubMed
9.21
0OM
83.24
0.77
86.03
83,33
0.39 86.80
Photo
AUC
0.11
97.11 0.44
91.44
4.558
96.41
= 0.47
97.55 = 0.16
94.97
+ 3.06
97.07
0.19
98.16 = 0.05
97.61
0.55
94,51
96.90
Computers
AUC.
97.44
COM
90.01 + 3,57
94.44 = 01.34
96.85 0.13
92.95
3.60
95.59
0.2.
97.69 = 0.07
a 0.25
OOM
J0.44
0.34
93.00
0.29 95.56
Average
AUC
95.06 1 0.49
COM
86.76 2.38
87.92
0.96
91.65 0.61
88.74 + 1.93
89.39
0.95
92.41 0.55
95.23 4 0.53
0OM
$7.09 + 2.43
89.63 = 0.80
91.26 = 0.70
88.98
1.68
90.85
0.75
92.06 = 0.50
8

---

Published as a conference paper at ICLR 2026
3.4 ABLATION STUDY AND EVALUATION ON LARGE-SCALL AND HETEROPHILOUS DATASETS
We evaluate the contribution of each component in the framework, namely the fractional diffusion operator, progressive subgraph diffusion, and class-level feature refinement. Ablation results and discussion appear in Appendix [..2. We then test FSD-CAP on large-scale datasets and on datasets with heterophily. Across these settings, the method remains competitive and adapts well. Detailed results and analysis are provided in Appendix A.2.7 and Appendix A.2.8
4 RELATED WORKS
4.1 GRAPH FEATURE IMPUTATION
Learning from incomplete data due to missing attributes or partial observations a common chal- lenge in real-world graph applications (Little & Rubin (019)). Existing approaches fall into two main paradigms: end-to-end models, which integrate feature completion directly into the learning pipeline, and imputation-then-traiiii models, which treat imputation as separate preprocessing step (You et al. 2020) Huo et al.) (023). End-to-end methods aim to jointly learn node repre- sentations and impute missing features within a unified architecture. PaGCN (Zhang et al., 2024) introduces a partial graph convolution that aggregates only observed features but struggles under high missing rates. GRAFENNE. (Guptaa et al., 2023) constructs a three-phase message-passing framework enabling dynamic feature acquisition, though its scalability is limited. Although expres- sive, these methods often require significant training data and computational resources. On the other hand, imputation tiniiiionn-tee-ttaiinggg approaches estimate missing values first utilizing statistical methods
(Liu et al., 2219:) Batista & Monard (002) or learned generative models (Kingma & Welling 2013
Yoon al. [2018) before applying standard GNNs to the completed data. SAT (Chen et al. 2020)
optimizes distributional discrepancies between graph structure and node attributes, while ITR (Tu
al., 2022) and RITR (Tu et al. (024) refine the input by amplifying trustworthy observed features.
These models benefit from modularity but remain vulnerable to bias when missing rates are high. A
recent survey provides a comprehensive overview of this landscape (Xia al. 2025).
4.2 GRAPH DIFFUSION
Diffusion-based graph representation learning (Gasteiger et al. 2019 Chamberlain et al. 2021 has been widely explored as a mechanism for neighborhood smoothing. Recent developments have extended classical diffusion beyond standard message- message-passing schemes. For example, ADC (Zhao al. 202T) improves over GDC (Gasteiger et al., 2019) by learning adaptive neighhorhood sizes from data, eliminating the need for manual tuning and enhancing both flexibility and generalization. In the context of imputation, diffusion can be viewed as a heat kernel process (Kondor & Lafferty) 2002). where observed features propagate through graph to estimate missing values. The process assumes feature homophily (i.e., neighboring nodes are likely to share similar attributes) and is often analyzed via Dirichlet energy, which decreases smoothness increases (Zhou et al. 2021 Zhang, 2023 Zhang et al., 2023). FP (Rossi et al.) (022) formalizes this by directly minimizing Dirichlet energy, yielding simple and effective iterative algorithm for feature diffusion under high sparsity. However, it does not incorporate feature correlations or relational context. Recent work addresses this limitation by integrating richer structural signals. PCFI (Um et al., 2023) guides diffusion using feature-level confidence across nodes and channels, while SGHFP (Lei et al. 2023) models higher- order relationships using hypergraph structure (Dong al. 2025a). Nonetheless, most existing methods apply uniform diffusion across nodes, ignoring variations in completion difficulty. As a result, poorly estimated nodes may contaminate their neighbors.
CONCLUSION
In this paper, we propose novel diffusion-based feature imputation approach for incomplete graph learning. By introducing a fractional diffusion operator and distance-guide progressive subgraph diffusion, we are able to adjust the propagation sharpness according to local graph structure and propagate information from observed to missing nodes hierarchically, thereby improving the stabil- ity of the diffusion process and the reliability of the imputed features. We further design class-

---

Published as a conference paper at ICLR 2026
level refinement mechanism to enhance feature quality under severe feature sparsity. Extensive experiments conducted on a variety of benchmark datasets demonstrate that our method not only consistently outperforms state-of-the-arr approaches in semi-supervised node classification and link prediction tasks, with particularly notable improvements under extreme feature missingness, but also exhibits remarkable adaptability to diverse graph structures.
ETHICS STATEMENT
FSD-CAP improves the robustness of GNNs under high feature-missin rates and may benefit ap- plications in domains such as social networks and recommender systems. However, as with any imputation technique, there is risk of misuse, partieularly in inferring sensitive or private attributes from partial data. We encourage responsible use, including proper access controls and ethical over- sight, especially when applying the model contexts involving personal or sensitive information.
REPRODUCIBILITY STATEMENT
The proposed imputation framework is introduced in detail in Section 2 with summary of the experimental setup provided in Section 3 Further details, including data splitting strategies and hyperparameter settings, are given in the appendix. For reproducibility, we make the code and corresponding random seeds publicly available.
ACKNOWLEDGMENTS
This work was supported by grants from the Natural Science Foundation of Shanxi Province (2024JCCCON-66), Science and Technology Commission of Shanghai Municipality (NO.2451 106900), Key R&D Program of Zhejiang (2024SSYS0091).
REFERENCES
Gustavo Enrique Batista and Maria Carolina Monard. A Study of K-Nearest Neighbour an Impu- tation Method. His, 87(251-260):48, 2002.
Tian Bian, Xi Xiao, Tingyang Xu, Peilin Zhao, Wenbing Huang, Yu Rong, and Junzhou Huang. Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networks. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 34, pp. 549-556, 2020.
Ben Chamberlain, James Rowbottom, Maria I. Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: Graph Neural Diffusion. In International Conference on Machine Learning, pp. 1407-1418. PMLR, 2021.
Jie Chen, Zilong Li, Yin Zhu, Junping Zhang, and Jian Pu. From Node Interaction to Hop Inter- action: New Rffective and Scalable Graph Learning Paradigm. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 7876-7885, 2023.
Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785-794, 2016.
Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Zhang, and Ivor W. Tsang. Learning Attribute-Missing Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(2):740-757, 2020.
Yongxin Chen, Tryphon T. Georgiou, Michele Pavon, and Allen Tannenbaum. Robust transport over networks. JEEE Transactions on Automatic Control, 62(9):4675-466 2016.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. arXiv preprint arXiv:2006.07958 2020.
Anqi Dong, Tryphon T. Georgiou, and Allen Tannenbaum. Data Assimilation for Sign-indefinite Priors: A generalization of Sinkhorn's algorithm. Automatica, 177:1 12283, 2025a.
10

---

Published as a conference paper at ICLR 2026
Anqi Dong, Tryphon T. Georgiou, and Allen Tannenbaum. Negative Probabilities and the Sinkhorn Algorithm: Promotiom/lnhibttin Interactions Networks. EDITORIAL COMMITTEE, pp. 61, 2025b.
Johannes Gasteiger, Stefan Weißenbergerr and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
Shubham Gupta, Sahil Manchanda, Sayan Ranu, and Srikanta J. Bedathur. GRAFENNE: Learn- ing on Graphs with Heterogeneous and Dynamic Feature Sets. In International Conference on Machine Learning, pp. 12165-12181. PMLR, 2023.
Xiangnan He, Kuan Deng. Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 639 648, 2020.
Cuiying Huo, Di Jin, Yawen Li, Dongxiao He, Yubin Yang, and Lingfei Wu. T2-GNN: Graph Neural Networks for Graphs with Incomplete Features and Structure via Seacher-Student Distillation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4339-4346, 2023.
Feng Ji. See Hian Lee, Hanyang Meng, Kai Zhao, Jielong Yang, and Wee Peng Tay. Leverag- ing Label Non-uniformity for Node Classification in Graph Neural Networks. In International Conference on Machine Learning, pp. 14869-14888 PMLR, 2023.
Xinke Jiang, Zidi Qin, Jiarong Xu, and Xiang Ao. Incomplete Graph Learning via Attribute- Structure Decoupled Variational Auto-Encoder. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp. 304-312, 2024.
Diederik P. Kingma and Max Welling, arXiv:1312.6114 2013.
Auto-Encoding Variational Bayes. arXiv preprint
Thomas N. Kipf and Max Welling. Semi-Super Classification with Graph Convolutional Net- works. arXiv preprint arXiv: 1609.02900 2016a.
Thomas N. Kipf and Max Welling. Variational Graph Auto-Encoders. 16X 2016b.
arXiv preprint
Risi Imre Kondor and John Lafferty. Diffusion Kernels on Graphs and Other Discrete Structures. In Proceedings of the 19th international conference on machine learning, volume 2002, pp. 315- 322, 2002.
Chengxiang Lei, Sichao Fu, Yuetian Wang, Wenhao Qiu, Yachen Hu, Qinmu Peng, and Xinge You. supe-super Guided Hypergraph Feature Propagation for Semi-super Classification with Missing Node Features. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEBE, 2023.
Michelle M. Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, 1(12):1353-1369) 2022.
Roderick J.A. Little and Donald B. Rubin. Statistical Analysis with Missing Data. John Wiley & Sons, 2019.
Xinwang Liu, Xinzhong Zhu, Miaomiao Li, Lei Wang, En Zhu, Tongliang Liu, Marius Kloft, Ding- gang Shen, Jianping Yin, and Wen Gao. Multiple Kernel k-Means with Incomplete Kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(5):1191-122) 2019.
Daniele Malitesta, Emanuele Rossi, Claudio Pomo, Fragkiskos D. Malliaros, and Tommaso Di Noia. Dealing with Missing Modalities in Multimodal Recommendation: Feature Propagation-bal Approach. CORR, 2024.
Emanuele Rossi, Henry Kenlay, Maria I. Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features. In Learning on graphs conference, pp. 11-1. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2026
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective Classification in Network Data. Al Magazine, 29(3):93- 930333-9333333 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation. arXiv preprint arXiv: 2018.
Nathan Srebro, Jason Rennie, and Tommi S. Jaakkola. Maximum-Margin Matrix Factorization. Advances in Neural Information Processing Systems, 17, 2004.
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph Convolutional Networks for Graphs Contain- ing Missing Features. Future Generation Computer Systems, 117:155-168, 2021.
Wenxuan Tu, Sihang Zhou, Xinwang Liu, Yue Liu, Zhiping Cai, En Zhu, Changwang Zhang, and Jieren Cheng. Initializing Then Refining: A Simple Graph Attribute Imputation Network. In IJCAI, pp. 3494-3500, 2022.
Wenxuan Tu, Bin Xiao, Xinwang Liu, Sihang Zhou, Zhiping Cai, and Jieren Cheng. Revisiting Initializing Then Refining: An Incomplete and Missing Graph Imputation Network. IEEE Trans- actions on Neural Networks and Learning Systems, 2024.
Daeho Um, Jiwoong Park, Seulki Park, and Jin Young Choi. Beniidnnc-Bassee Feature Imputation for Graphs with Partially Known Features. In The Eleventh International Conference on Learning Representations, 2023. URL httpapsse/eeerreeeeeeeeeeeeerrrs wttp://wweweotoo.e.oooeoe..e
Kt
Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and Composing Robust Features with Denoising Autoencoders. In Proceedings of the 25th Interna- tional Conference on Machine Learning, pp. 1096-1103, 2008.
Yuanyi Wang, Haifeng Sun, Jiabo Wang, Jingyu Wang, Wei Tang, Qi Qi, Shaoling Sun, and Jianxin Liao. Towards Semantic Consistency: Dirichlet Energy Driven Robust Multi-Modal Entity Align- ment. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 3559-3572. IEEE, 2024.
Riting Xia, Huibo Liu, Anchen Li, Xueyan Liu, Yan Zhang, Chunxu Zhang, and Bo Yang. Incom- plete Graph Learning: A Comprehensive Survey. arXiv preprint 202 2025.
Jaemin Yoo, Hyunsik Jeon, Jinhong Jung, and U. Kang. Accurate Node Feature Estimation with Structured Variational Graph Autoencoder. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2336-2346, 2022.
Jinsung Yoon, James Jordon, and Mihaela Van der Schaar. GAIN: Missing Data Imputation using
Generative Adversarial Nets. In International conference on machine learning, pp. 5689-5698. PMLR, 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awand Graph Neural Networks. In International Conference on Machine Learning, pp. 7134-7143. PMLR, 2019.
Jiaxuan You, Xiaobai Ma, Yi Ding, Mykel J. Kochenderfer, and Jure Leskovec. Handling Missing Data with Graph Representation Learning. Advances in Neural Information Processing Systems, 13:19775-19087. 2020.
Cheng Zhang. Learnable Topological Features for Phylogenetic Inference via Graph Neural Net- works. In The Eleventh International Conference Learning Representations, 2023. URL
/ttp::///ppeeeeieew net./ http://wwwweeeeeeeeeeeeeeeee. wow.mmid=swvuuY/// 4WL
Muhan Zhang and Yixin Chen. Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems, 31, 2018.
Xiaochuan Zhang, Mengran Li, Ye Wang, and Haojun Fei. AmGCL: Feature Imputation of Attribute
Missing Graph via Self-supervised Contrastive Learning. arXiv preprint 0001::2300.03744,.0000
Ziyan Zhang, Bo Jiang, Jin Tang. Jinhui Tang, and Bin Luo. Incomplete Graph Learning via Partial Graph Convolutional Network. IEEE Transactions Artificial Intelligence, 2024.
12

---

Published as a conference paper at ICLR 2026
Jialin Zhao, Yuxiao Dong, Ming Ding, Evgeny Kharlamov, and Jie Tang. Adaptive Diffusion in Graph Neural Networks. Advances in Neural Information Processing Systems, 2021.
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet Energy Constrained Learning for Deep Graph Neural Networks. Advances in neural information processing systems, 34:21834-21 21846, 2021.
13

---

Published as a conference paper at ICLR 2026
A
APPENDIX
OUTLINE OF THE SUPPLEMENTARY MATERIAL
Section Proofs of main results: Formal proofs for the theoretical results stated in the main paper.
Section 2 Experimental analyses: We present additional evaluations to support the effectiveness and robustmess of FSD-CAP. First, ablation studies show that removing any single com- ponent leads to consistent drop in performance
all datasets. Second, sensitivity analyses demonstrate the stability of the framework with respect to key parameters. A comparison with FP, a global diffusion baseline, highlights FSD-CAP's ability main- tain accuracy at greater distances from observed nodes, validating the progressive diffusion mechanism.
We also analyze class-level characteristics of imputed features and visualize the outputs of FP and PCFI to show that FSD-CAP better preserves inter-class separability. We fur- ther validate FSD-CAP's strong practical scope and generality through comparative exper- iments large-scale and heterophily datasets. Finally, report classification accuracy under missing rates from 60% to 99.5%, showing that FSD-CAP is highly robust to both the rate and structure of missing data. Under uniform missing with mrr 0.995, the average performance drop is just 0.3% relative to the fully observed case; in some cases, perfor- mance even improves. FSD-CAP consistently achieves higher node classification accuracy than the state-of tiite-of-hhe-eee ff-thhe-rt art baseline PCFI under varying levels of feature missingness.
Section - -lmleeeentatinn and hyperparameters: Experimental setup for both node classification and link prediction tasks, including dataset statistics, data splits, evaluation metrics, model architectures. and hyperparameter configurations for all baselines and FSD-CAP.
Section Supplementary figures and tables: Additional results comparing node classifica- tion accuracy PubMed, Photo, and Computers across multiple missing rates (mer 0.6, 0.7, 0.8, 0.9, 0.95, 0.995). These results extend Section 3.2 of the main paper and fur- ther validate the robustness of FSD-CAP.
Section Declaration of L.LM usage: We make full disclosure regarding the utilization of the
large language model (LLM) throughout the process of completing this thesis.
Section -
Pseudocode of FSD-CAP: We provide the pseudocode for Fractional Subgraph Diffu- sion (Algorithm T and Class-Aware Propagation (Algorithm) 2
A.1 PROOFS MAIN RESULTS
Proposition A.1 (Limiting behavior of A?). Let A be the symmetric normalized adjacency matrix of connected graph, and A E NNN is defined as
N E(Au))
A = (Ais)7
(7)
We have
if Aij >
(1 if j E arg A otherwise
lim A
lim A
(8)
7-00
otherwise
where N(i) = Aij > 0} denotes the set of neighbors of node i.
Proof. Let i be fixed row index. By definition, the entries of A are given by
A
A
(9)
ΣXENTO A
where the is taken over the neighborhood Niii) k A > 0. Since A is symmetric normalized adjacency matrix, all its entries are nonnegative and satisfy Aij E [0, 1].
We consider limiting cases:
14

---

Published as a conference paper at ICLR 2026
Case 1: + 0+. For all j Mi),, we have A + 1 as y 0+. Therefore, the numerator tends to for each neighbor, and the denominator tends [V(i) As result,
lim 7-++
if (()),
(10)
W(ii
and zero otherwise. Thus, the row converges to uniform distribution over the neighbors of node i.
Case 2: 7 In this case, the exponentiation amplifies differences between entries. Specif- ically, the largest value As dominates the sum the denominator, and the softmax approaches one-hot distribution centered the maximum. Let j E arg max; Ask- Then,
lim A = { j j 7-000
(11)
otherwise
which completes the proof.
Theorem A.1 (Fractional diffusion on feature propagation). Let A and A denote the lazy tran- sition and fractional diffusion operator defined in equation 7 respectively. For any feature mafrix
X E N XF define the propagated features by X" = A Then for each node i, we have
lim (la
Σ JEN())
X
and
lim Xla X13=,
7-0+
[W(1]
70000
where ((1)
{i Aij > 0} the neighborhood of us and j E arg maxt Ais is the index of its
strongest neighbor.
Proof. The propagated feature vector at node is defined by
Xh. Σ A X 64
the limiting regimes of thus read
Case 1: y + 0+. As y approaches zero, we have A? + 1//N(1)) for all j E Ni),, and zero otherwise. Therefore,
R.
Σ
X
JEN(
which corresponds to uniform averaging over the neighborhood node
Case 2: 7 + ac. The largest entry in row of dominates the normalization. Specifically, j* arg max; Ask. then A 1 j", and zero otherwise. Hence,
X
which corresponds to selecting the feature vector of the strongest neighbor.
Theorem A.2 (Convergence of subgraph diffusion). Let (m)) be the adjacency matrix of the m-th t- layer subgraph G(m)), and let 7m denote its fractional diffusion matrix as defined in equation 7
Let x (m)) E R p be the feature vector in channel f, where missing entries are initialized to zero.
Let X > denote the retention coefficient, and M be the binary mask vector for observed entries in
channel Define the update sequence by
(mm) (t) (m)) (0) 2 M (A (. 1) (aamm-1)( (1- M), t= K
Then, for sufficiently large K, the sequence x (m)) (1) converges fixed (unique) state.
15

---

Published as a conference paper at ICLR 2026
Proof. Fix feature channel É, and consider the m-th subgraph layer ((m) with ()(m) nodes. Let (m)) denotes the vector of E-th feature values across all nodes in this subgraph
(m))
(m)
122
(m)
[e]
Recall M E {0, 10 be the full binary feature mask. Define the channel-wise mask vector M 10 by M, M[i. [], which indicates whether node u,'s feature in channel is observed.
Let A (m) be the symmetric normalized adjacency matrix of the subgraph g(m), and define the fractional diffusion operator A E Raxx as
(A (ms)
A m.
El (A
Since > O, this defines a row-stochastic matrix with nonnegative entries. Its support coincides with that of (m)) and thus matches the topology of the subgraph. If g(())) is connected, then A 7, the transition matrix of irreducible and aperiodic Markov chain.
From standard results Markov chain theory, for any initial vector v(0), the iterates
ett) = (A 7.m ( (x(()
converge to the unique stationary distribution.
Now consider the masked and retained update. Define the diagonal projection matrices
P = diag(M (M((), Q I P diag(1 M())).
Then the update rule can be written as
(m)) (m)) (t) (m) (0) + Q A 7. (mm)(t (t 1) (m
is the retention factor and mm (K) is the converged estimate from the previous layer. This is a linear, inhomogeneous recurrence of the form
where >
x (m)) = Gr (m)) (t 1) bb
with
G 7m vm
b:= Pa (0) + (m-(m-)((K)))
Since A is row-stochastic and Q is diagonal with entries in [0, 1]. the matrix G is sub-stochastic its rows have nonnegative entries and sum at most 1. Furthermore, any row corresponding an observed feature (i.e., M((e) = 1) satisfies Qū = 0, so the corresponding row of G all zeros. If at least one feature is observed (i.e., (4) + 0), then G has at least one row with sum strictly less than and thus its spectral radius satisfies p(G) 1.
Since p() < 1, the recurrence converges to unique fixed point, i.e.,
(m) (oo) = GI-G)-1B
This proves that the update converges for each feature channel E, in every subgraph layer m, long as the underlying subgraph is connected and ? co.
Theorem A.3 (Global convergence via progressive subgraph expansion). Let (mm) be the m- hop expansion of the observed node set V in channel f, and let (! be the corresponding feature estimate after applying the masked fractional diffusion update defined in Theorem A.2 Assume the graph G is connected and the diffusion sharpness parameter y is finite. Then where ((m) - G, the final estimate (m) (oc) converges to the steady- state solution of the tull-graph diffusion update.
Maaso
16

---

Published as a conference paper at ICLR 2026
Proof. Fix a feature channel and consider sequence of subgraphs {g(m)) defined by expanding the observed node set V in increasing m-hop neighborhoods. Each subgraph G(m) (V(m), E(m) satisfies
mm C p(m+1)
{(m) C g(m+1)
and Uglm) G.
Let (e(m) denote the steady-state solution obtained by applying the masked and retained update on G(m), which exists by Theorem A.2 Since each update only modifies nodes in v(m)) and each
y(m) is strictly contained in the next, the sequence (x1mm (oc) defines an expanding approxima- tion of the solution on the full graph.
We now define the full-graph update. Let = (V,E) be the complete graph, and let A E BNN be the full fractional diffusion matrix defined over all N nodes
(Aiy)"
A
Σ (As)))
where A is the symmetric normalized adjacency matrix of G. Let x= be the solution to the global masked and retained update
x = Px(0) + QA7 + Axprev),
where P = diag(M()), Q= - P. and r00) is the initial feature vector for this channel.
Now, observe that for any fixed node i, there exists minimal radius m, such that i E y(m) for all m my, Beyond this point, the update for (/(")) (cc) is computed using the same local topology, diffusion weights, and mask structure as in the full graph. Hence, for each node i, the local solution
on ((m) matches the restriction the global solution, up to boundary conditions that vanish as the subgraph expands.
Furthermore, the retention mechanism ensures that values propagated from earlier layers remain sta- ble and reinforce prior estimates. Because the number of nodes is finite and each node is eventually included in some G(m), conclude that
lim max
(p0) = x²,
where xf is the fixed point of the global masked diffusion update.
A.2 EXPERIMENTAL ANALYSES:
A.2.1 ABLATION STUDY
To evaluate the contribution of each component in FSD-CAP, we perform ablation studies under the structural missing setting with a 99.5% missing rate. Experiments are conducted on both semi- supervised node classification and link prediction tasks across all datasets. We compare the full model the following variants, each with one component removed
1. W/o_Frac_oppe Removes the fractional diffusion operator.
2. w/o Boo_Prog_suue subg: Removes the progressive subgraph diffusion.
3. w/o_Class_refiinn refine: Removes the class-level feature refinement.
The results of the ablation studies are reported in Table for node classification and Table 4 for link prediction. In both tasks, removing any single component from FSD-CAP results in consistent drop in performance across all datasets, confirming the contribution of each module. The performance degradation is especially pronounced in the link prediction setting.
w/o Frac Frac_oper. Removing the fractional diffusion operator results in an average accuracy drop of 2.02% in node classification, with larger effect observed denser co-purchase datasets such as Photo and Computers (Table 3). Its impact is even more pronounced in link prediction, where the average AUC decreases by 5.60% across five datasets (Table 4). These results highlight the
17

---

Published as a conference paper at ICLR 2026
role of the fractional operator in adapting diffusion sharpness to local structure and demonstrate its importance in both tasks.
w/ Prog subg. Eliminating the progressive subgraph diffusion mechanism results in a smaller average performance loss compared to the other two components. However, as shown in Table 4 it leads to noticeable degradation on link prediction for datasets such as Cora and CiteSeer. The progressive expansion strategy helps reduce error accumulation during diffusion by gradually incor- porating nodes, improving stability and overall performance.
w/o_Class__ Leaaser The class-level refinement has the most significant impact on node classification performance (Table 3). Its removal particularly affects sparse graphs with multiple classes, such as Cora (7 classes) and CiteSeer (6 classes). By constructing class-specific anchor nodes and propagat- ing within class-specific graphs, this component enhances inter-class separation and strengthens the discriminative power of imputed features.
Together, these results demonstrate that all three components play complementary roles. Their com- bination is essential for achieving robust and accurate imputation under extreme sparsity.
Table 3: Ablation study on semi-supervised node classification. Best values are in bold.
Cora
CiteSeer
PuhMed
Photo
Computers
Average
FSD-CAP
80.56%
71.94%
76.98% %
89.18%
81.64%
80.06%
_lo_Frac_opp Frac_oper
79.95% (-0.61%) 71.82% (-0.12%)
75.54% (-1.44%)
86.27% (-2.91%)
76.60% (-5.04%)
78.04% (-2.02%)
Prog__oougggg
79.34% (-1 (-1.22%)
70.84% (-1.10%)
75.97% (-1.01 St)
88.07% (-1.11%)
79.14% (-2.50%)
78.67% (-1.39%)
w/o_Class Class_refiine
76.43% (-4.13%)
63.65 (-3.295)
75.52% (-1.46%)
88. 10% (-1.08%)
78.06% (-3.58%)
77.35% (-2.71%)
Table 4: Ablation study on link prediction, with best performance highlighted in bold.
Metric
Cora
CiteSeer
PuhMed
Photo
Computers
Average
AUC
87.97%
87.48%
88.39%
97.55
96.85%
91.65%
FSD-CAP
AP
88.80% %
87 97.82%
85,54%
97.32%
96.83%
91.26%
AUC
80.54% (.7.43%)
79.07% (-8.41%)
85.32%
(-3.07%)
95.94%
(-1.61%)
89.39% (-7.46%)
86.05% (-5.60%)
vra_Frac_oper
82.65% (-6.15%)
81.74% (-6.08%)
84.81 (-0.73%)
95.46%
(-1.86%)
89.99% (-6.84%)
86.93% (-4.33%%
AUC
82.67% (-5.30%)
79.71% (-7.77%) 86.10% (-2.29%%
96.47% (-1.08%)
95.75% (-1.10%)
88, 18%
14% (-3.51%%
w/o Wo_Prog_subg
AP
84.48% (-4.32%)
80.67% (-7.15%) 84.71% (-0.83%)
96.16%
(-1.16%)
95.68% (-1.15%)
88.34% (-2.92%)
AUC
83.00% (-4.97%)
79.58%
(-7.90%)
84.90%
(-3.49%
96.49%
(-1.06%)
94.71%
(-2.14%%)
87.74% (-3.915%
w/o Boo_CClsss_eeeee
84.69% (-4.11%) 80.76% (-7.06%)
83.00%
(-2.54%)
96.26%
(-1.06%)
94.63%
(-2.20%)
87.87% (-3.39%
A.2.2 PARAMETER ANALYSIS
To assess the sensitivity of FSD-CAP its key parameters (7, X, and T),, we conduct controlled experiments on both semi-supervised node classification and link prediction. We use the structural missing setting with a 99.5% feature missing rate, evaluating on Cora and the denser Photo dataset.
In the fractional subgraph diffusion (FSD) stage, information is propagated progressively from ob- served to unobserved nodes by expanding the subgraph. The fractional exponent ? controls the sharpness of diffusion: higher values lead to more localized propagation. The retention coefficient determines the weight of previous estimates in the update. The temperature T is used in the class-aware refinement stage to modulate the influence of class-level anchors.
We examine the joint effect of the fractional diffusion parameter 7 and the retention coefficient on model performance, with temperature T fixed. Figure 3 shows classification accuracy on Cora and Photo as these parameters vary. On Cora, y swept from 0.6 to 1.6 (step size 0.2), while on Photo it ranges from 2.0 to 4.0 with the same step. In both cases, À is varied from 0 to 1 in increments of 0.1. Results indicate that Cora achieves higher accuracy when À E [0.2, 0.4] and 7 E [1.2, 1.4], suggesting that incorporating estimates from previous diffusion layers improves imputation quality. On the denser Photo dataset, accuracy improves when y is set around 2.6 to 3.0, reflecting the benefit of sharper, edge-cone conceettnntt diffusion in dense graphs.
Figures 4 and 55 present AUC and AP scores for link prediction on Cora and Photo, respectively.
The trends consistent with those observed in node classification, confirming that performance
18

---

Published as a conference paper at ICLR 2026
0.0
0.0
0.1
80.4
89.0
0.2
80.2
0.3
0.4
0.5
79.8
0.3
0.6
0.6
0.7
79.6
0.7
88.4
0.8
0.8
0.9
0.9
00.2
79.2
Fractional operator
1.0
2.0
Fractional operator
2.8 2.8
3.0
3.6 3.8
(a) Cora
(b) Photo
Figure 3: Sensitivity of node classification accuracy the retention coefficient À and fractional exponent y on Cora and Photo datasets,
AUC
AP
0.0
0.0
0.1
87.0
0.2
0.2
0.3
86.5
0.3
00.5
85.5
8 0.5
86.0
5 0.6
0.6
85.0
85.0
0.8
0.8
84.0
0.9
84.0
1.0
83.5
0.6 0.8 1.0 1.2 1.6 Fractional operator Y
0.6 0.8 1.0 1.2 1.4 1.6 Fractional operator Y
Figure 4: Sensitivity of link prediction performance the retention coefficient À and fractional
exponent y on the Cora dataset.
AUC
AP
0.1
0.1
97.50
0.2
deentoonn coefficent>
Ratention coeffident
0.3
97.48
0.3
0.4
0.4
97.25
0.5
0.5
0.6
97.44
0.6
97.20
97.42
0.7
0.8
0.8
97.40
97.15
1.0
1.0
4.0 5.0.5. 5.6 6.0
5.8
4.0 4.2 4.4 4.6
4.8 5.0 5.2 5.4 5.6 5.8 6.0
Fractional operator
Fractional operator
Figure 5: Sensitivity of link prediction performance to the retention coefficient À and fractional exponent 7 on the Photo dataset.
sensitive to the choice of À and 7. Cora, smaller values of À yield better results. On Photo, higher values of improve performance more noticeably than in the classification setting, suggesting that localized diffusion captures structure relevant to link formation. Modulating diffusion strength across local neighborhoods allows FSD-CAP to better exploit available information. These sensi- tivity results further validate the role each component in FSD-CAP. The retention mechanism stabilizes the diffusion process by preserving accurate estimates from earlier layers, reducing error propagation. The fractional operator adjusts the relative influence of neighboring nodes based on local graph structure, helping mitigate over-smoothing and improve overall imputation quality.
19

---

Published as a conference paper at ICLR 2026
In the class-aware propagation (CAP) step, GCN-based classifier assigns pseudo-labels unla- beled nodes. These labels are used to construct class-specific features and class-wise graphs for targeted feature refinement. The temperature parameter T is applied to the softmax function to control the sharpness of the output distribution. Lower values of 7 produce sharper, more confi- dent predictions; higher values yield smoother distributions. When T 1, the standard softmax is recovered.
Cora
Photo
100
Accuracy (%)
80
97
91
80
85
74
82
5
25
100
250
1000
0.001
0.01
0.1
10
25
50
0.001
0.01
0.1
10
25
50
temperature
temperature
temperature
Figure 6: Sensitivity of node classification and link prediction performance temperature parameter on the Cora and Photo datasets.
Figure 6 shows the effect of the temperature parameter I' on model performance across accuracy, AUC, and AP metries for the Cora and Photo datasets. On Cora, both node classification and link prediction achieve optimal performance near T 5. On the denser Photo dataset, the optimal value 25 yields the best node classification accuracy, while T 0.001 gives the highest link prediction scores. At low T, the pscudo-label distribution becomes sharply peaked, resulting in high-confidence weights during class-aware propagation. This reduces the influence of class-level features and increases the emphasis on individual node characteristics. For link prediction on dense graphs, this behavior is beneficial, as rich local structure can guide accurate edge inference. In contrast, node classification benefits from smoother pseudo-labels (higher T), which reduce intra- class noise and improve class-level separation. These results highlight the importance of tuning T: relative the default 7" 1, appropriate values can significantly improve performance on both tasks.
of differs by task:
A.2.3 ACCURACY COMPARISON ON DIFFERENT DISTANCE
To assess how distance from observed features impacts classification accuracy, we evaluate perfor- mance under the structural missing setting with a 99.5% missing rate. Nodes are grouped by their shortest-path distance to the nearest node with observed features, and average accuracy is computed for each group. We compare FSD-CAP to the global diffusion baseline FP across five datasets. Figures and present accuracy function of distance for sparse and dense graphs, respectively.
100
Cora-FSD-CAP
90
CiteSeer-FSD-CAP
Accuracy
70
PubMed-FSD-CAP
Cora-FP
50
CiteSeer-FP
PubMed-FP
30
3
4
5
9
10
11
12
Distance
Figure 7: Node classification accuracy (%) of and FSD-CAP grouped by shortest-path path distance to the nearest node with observed features, evaluated Cora, CiteSeer, and PubMed.
20

---

Published as a conference paper at ICLR 2026
100
90
Accuracy (%)
Photo-FSD-CAP
70
CoMPuter
60
Photo-FP
Computers-FP
40
30
0
Distance
Figure 8: Node classification accuracy (%)
FSD-CAP as a function of shortest-pate dis- tance to the nearest observed node, evaluated on the Photo and Computers datasets.
As shown in Figure 8 the Photo and Computers datasets are relatively dense, with most missing- feature nodes located within five hops observed nodes. contrast, the sparser datasets Cora, CiteSeer, and PubMed (Figure exxhbbtt much larger maximum distances between missing and observed nodes. Across all datasets, both FP and FSD-CAP show a general decline in accuracy as distance increases. In some cases, accuracy temporarily rises longer distances. This is explained by the node distribution: most nodes lie within a few hops of observed regions, while distant nodes few (Figure 9). which inflates the average accuracy of these small groups.
This trend confirms that diffusion-based methods perform better for nodes near observed features. Compared FP, which applies global propagation, FSD-CAP reduces accuracy degradation greater distances and improves performance for nearby nodes. These results support the effective- ness of progressive subgraph diffusion, which focuses propagation on reliable local neighborhoods and limits error accumulation, leading to more stable and accurate imputation.
10000
8000
Cora
Number of Nodes
CiteSeer
6000
PubMed
4000
Photo
Computers
0
3
6
9
10
11
12
Distance
Figure 9: Number of nodes at each shortest-path distance from the nearest node with observed features across the five datasets.
A.2.4 CLASS-LEVEL FEATURE SIMILARITY ANALYSIS
To analyze the class-level structure of features imputed by FSD-CAP, we perform experiments under the structural missing setting with 99.5% missing rate. Cosine similarity is used to measure both intra-class and inter-class feature similarity. We compute these metrics on the imputed features and compare them to those obtained from the original, fully observed features.
Tables 5 and 6 report intra-class and inter-class cosine similarity for the original and imputed fea- tures, respectively. "Average" denotes the mean intra-class similarity across all classes. The "Ratio"
21

---

Published as a conference paper at ICLR 2026
Table 5: Inter-class and intra-class cosine similarities of original features.
Intra-class
Dutaset
Inter-class
Average
Ratio
classl
class2
class3
class4
class5
classó class7 class8 class9 class10
Cora
0.054
0.087
0.117
0.092
0.070
0.071
0.089 0.116
0.091
1.70
CiteSeer
0.042
0.053
0.063
0.063
0.067
0.078
0.061
0.064
1.54
PubMed
0.063
0.112
0.094
0.078
0.094
1.51
Photo 0.337
0.282
0.495
0.331
0.435
0.354
0.381
0.289
0.354
0.365
1.08
Computers
0.348
0.371
0.347
0.442
0.390
0.300
0.449
0.534
0.455
0.393
0.414
0.409
1.17
Table 6: Inter-class and intra-class cosine similarities of features imputed by FSD-CAP under the structural missing setting with a missing rate of 99.5%.
Intra-class
Dataset
Inter-class
Average
Ratio
class
class2
class3
class4 class5 class6 class7 class8 class9 class10
Cora
0.827
0.937
0.986
0,992
0.907
0.828
0.887 0.950
0.926
1.12
CiteSeer
0.671
0.854
0.817
0.947 0.868
0.962
0.958
0.901
1.34
PubMed
0,905
0.930
0.961
0.938
0.943
1.04
Photo 0.884
0.983
0.984
0.987
0.992
0.995
0.978
0.991
0.992
0.988
1.12
Computers
0.868
0.994
0.867
0.982
0.923
0.928
0.979
0.973
0.966
0.920
0.975
0.946
1.09
defined as the average intra-class similarity divided by the inter-class similarity. ratio greater than indicates better class separability.
As shown in Table 5 the original features consistently yield higher intra-class similarity than inter- class similarity across all datasets, confirming their strong class-discriminatii structure. Table 6 shows that FSD-CAP preserves this structure even under 99.5% feature missing. In all cases, the ratio remains above 1, indicating that the imputed features retain meaningful class-level separation.
These results confirm that FSD-CAP maintains discriminative feature geometry under extreme spar- sity. As shown in Table [T] (Appendix A.2.9). the resulting classification performance is comparable to, and in some cases exceeds, that of the fully observed setting.
A.2.5 T-SNE VISUALIZATION
Under the structural missing setting with 99.5% feature missing rate, reconstruct node features using two diffusion-basee baselines (FP and PCFI) and our proposed FSD-CAP. We then apply I-SNE project the imputed features into dimensions for qualitative comparison.
Figures 10 and 11 show the t-SNE visualizations across five datasets, with nodes colored by ground- truth class labels. FSD-CAP produces more compact and well-separated clusters than FP and PCFI. Nodes from the same class form cohesive groups with clearer boundaries between classes. These visual patterns align with the similarity analysis in Appendix [A.2.4] further demonstrating FSD- CAP's ability to preserve class structure and support downstream tasks such as node classification.
A.2.6 COMPLEXITY ANALYSIS
Computational complexity. FSD-CAP consists of two stages: fractional subgraph diffusion (FSD) and class-aware propagation (CAP).
To make the cost concrete, we report wall-clock time (in seconds), including both the time for feature imputation and training of downstream GCN for FSD-CAP and baseline models in the Table 7 We measure a single split per dataset under a structural missing setting with a 99.5% missing rate. All experiments
40-core Intel Xeon Silver 4210R CPU with one NVIDIA RTX 4090 GPU.
As shown in the table, deep learning-bast based methods incur significantly higher computational costs compared to diffusion-basee imputation approaches. For FSD-CAP, the vast majority of the time is
22

---

Published as a conference paper at ICLR 2026
FP
PCFI
FSD-CAP
Cora
CiteSeer
PubMed
Figure 10: t-SNE visualizations of imputed node features on Cora, CiteSeer, and PubMed under the structural missing setting with 99.5% missing rate. Nodes are colored by ground-truth class labels.
spent on training the downstream model. The actual feature completion stage, in contrast, is highly efficient, requiring only 0.38s on Cora, 0.76s on CiteSeer, 0.75s on PubMed, 0.57s on Photo, and 1.09s on Computers. Among diffusion-based models, FSD-CAP requires more imputation time than FP and PCFI, yet the cost remains moderate. The extra time comes from the multi-step subgraph expansion, which improves reconstruction under extreme missingness. With only 0.5% of features available, FSD-CAP improves over PCFI by 1.80% to 5.88% on Cora, CiteSeer, PubMed, Photo, and Computers, with average gain of 3.67%. This yields favorable trade-off between accuracy and efficiency and is practical for real-world settings with severe feature scarcity.
Table 7: Training time (in seconds) of methods under structural missing setting with 99.5% missing rate.
Cora
CiteSeer
PubMed
Photo
Computers
PaGCN
3.442s
6.035s
11.297s
12.643s
26.635s
GRAFENNE
78.285s
30.133s
225.987s
160.739s
223.767s
ASD-VAN VAE FP
328.785s
132.977s
00M
468.35s
0OM
2.251s
2.282s
2.911s
3.267s
7.545s
PCFI
2.959s
2.797s
3.763s
3.769s
8.327s
FSD-CAP
3.276s
3.103s
4.022s
4.329s
8.992s
23

---

Published as a conference paper at ICLR 2026
FP
PCFI
FSD-CAP
Photo
Computers
Figure 11: t-SNE visualizations of imputed node features Photo and Computers under the struc- tural missing setting with 99.5% missing rate. Nodes are colored by ground-trute -ouun class labels.
Memory complexity. Table g reports the actual memory usage (in MB) of FSD-CAP for both semi-supervised node classification and link prediction under the structural missing setting with a 99.5% missing rate. Results are shown across five datasets, along with the average memory sumption for each task.
Table 8: Memory usage (in MB) of FSD-CAP for semi-supervised node classification and link prediction under the structural missing setting with 99.5% feature missing rate.
Cora
CiteSeer
PubMed
Photo
Computers
Average
Semi-supervised node classification
690
816
3638
1014
2044
1640.4
Link prediction
658
876
2560
1108
2274
1495.2
A.2.7 ACCURACY COMPARISON ON LARGE-SCALE DATASETS
We include results on the large-scale OGBN-ArXiv dataset and a subgraph with 50,000 nodes ex- tracted from OGBN-Products. The OGBN-ArXiv graph has 169,343 nodes, 1,166,234 edges, and 128-dimensional features.
We evaluate node classification accuracy under both structural and uniform missing settings. As shown in Table 9 several deep learning models, including GRAFENNE, ITR, and ASD-VAE, run out of memory on two graphs. FSD-CAP attains the best performance among all evaluated meth- ods in both settings. It reaches 69. 11% under structural missingness and 70.16% under uniform missingness, outperforming FP and PCFL. In the uniform case, the gap to the full feature model at 72.27% is 2.11 percentage points. These results indicate that the framework scales to large graphs and maintains strong reconstruction quality at extreme sparsity.
A.2.8 ACCURACY COMPARISON ON HETEROPHILY DATASETS
We evaluate heterophily explicitly. The benchmarks are Cornell, Texas, and Wisconsin from We- ЫKB, and Chameleon from Wikipedia. Their edge homophily ratios are 0.30, 0.11, 0.21, and 0.23, defined as the fraction of edges that connect nodes of the same class.
24

---

Published as a conference paper at ICLR 2026
Table 9: Accuracy comparison OGBN-Arxiv and OGBN-Products for node classification with
99.5% missing rate.
OGBN-Arxiv
OGBN-Products
structural missing
uniform missing
structural missing uniform missing
Full Features
72.27 = 0.11
72.27 = 0.11
69.04 = 0.07
69.04 + 0.07
Zero
56.36 + 0.63
57.70 # 0.70
51.66 1.30
58,70 0.70
PaGCN
47.46 + 0.51
56.92 + 0.34
55.00 + 0.55
56.00 + 0.56
GRAFENNE
OOM
OOM
OOM
OOM
ITR ASD-VAE
OOM
OOM
OOM
OOM
OOM 68.13 + 0.41 68.59 + 0.29
OOM 68.52 + 0.18 69.39 = 0.29
0OM
OOM
FP
67.53 0.64
68.66 + 0.35
PCFI
68.18 0.30
68.39 0.29
FSD-CAP
69.11 + 0.33
70.16 + 0.27
69.03 0.41
69.26 0.27
We test node classification at 99.5% missing rate under structural and uniform masks. We compare with biffee completion methods FP and PCFI, and with two heterophily-orienter GNN, Hop GNN and GPR GNN, under the same settings.
As shown in Table 10. when features are extremely sparse, the heterophily GNNs degrade, while completion first helps by reconstructing informative representations. Under structural missingness, Hop GNN averages 94,97, and FSD-CAP reaches 36.22%. Under uniform missingness, FSD-CAP averages 58.85% and outperforms all baselines.
These findings are consistent with our design. Progressive subgraph diffusion limits early cross- class leakage, and fractional diffusion allows milder mixing weak homophily. The class-aware refinement then pulls uncertain nodes toward class prototypes and downweights boundary nodes by entropy. Together, the table demonstrates that the framework generalizes well to weak homophily.
Table 10: Accuracy heterophily graphs for semi-supervised node classification task at 99.5%
missing rate. The best results are highlighted in bold.
Structural Missing
Chameleon
Texas
Cornell
Wisconsin
Average
Hop-GNN
26.65% = 9.66
57.11% 6.56
47.11% 6.56
49.02% + 5.95
44.97%
GPR-GNN
21.90% = 1.75
58.42% 1 6.09
48.42% = 6.09
46.08% = 5,49
43.70%
FP
39.40% # 2.97
61.07%
8.81
55.36% # 12.12
55.53%
7.20
52.84%
PCFI
41.44% # 7.32
64.00%
8.11
55.17% # 12.04
55.32%
7.46
53.98%
FSD-CAP
43.23% 8.30
66.79 % 6.60 57.24% = 11.14
57.63%
9.00
56.22%
Uniform Missing
Chameleon
Texas
Corell
Wisconsin
Average
Hop-GNN
25.19% 6.75
57.11% + 6.56
47.11% + 6.56
49.02% + 5.95
44.61%
GPR-GNN
23.00% + 1.68
58.42% # 6.09
48.42% + 6.09
46.08% + 5.49
43.98%
FP
40.36% 4.47
61.43%
#857 62.50%
55.86%
12.12
58.16% 4.92
53.95%
PCFI
40.54%
4.08
+9.5
55.86% + 12.12
$7.37%
54.07%
FSD-CAP
47.84% 5.21
71.07% = 8.06
57.55% 11.66
58.95% # 5.79
58.85%
A.2.9 ROBUSTNESS ANALYSIS AGAINST DIFFERENT DATA MISSING LEVELS
To evaluate the robustness FSD-CAP under varying levels of feature missingness, we perform node classification experiments five datasets under both structural and uniform missing settings. The missing rate is gradually increased from 60% to 99.5%, and results are compared to the full- feature setting assess how performance degrades with increased sparsity. Table [I reports the classification accuracy at each missing rate, along with the relative change compared to the fully observed setting.
25

---

Published as a conference paper at ICLR 2026
Table 11: Node classification accuracy (%) of FSD-CAP at different missing rates. Relative perfor- mance changes are reported with respect to the fully observed (full-feature) setting.
Structural Missing
Dataset
Full Features
60% Missing
70% Missing
80% Missing
90% Missing
95% Missing
99.5% Missing
Com
82.72%
82.75% (+0.03%)
82.77% (+0.029)
82.28% (-0.445)) 82.45% (-0.27%)
82.01%: 82.015 (.0.71%)
80.56% (.0.16%)
CheSeer
70.00%
71.29% (+1.29%)
71.19% (+1.19%)
71.40% (+1.40%)
71.97%
(+1.97%)
72.85%
(+2.85%)
71.94% (+1.94%)
PubMed
77.46%
77.13% (.0.33%)
76.96% (-0.50%)
76.89% (-0.57%)
77.22% (-0.24%)
77.19%
(7.19%(-0.27%)
76.98%
(:0.48%)
Photo
91.63%
91.67% (+0.04%)
91.58%
(-0.05%)
91.34% (-0.29%)
90.79%
(-0.84%)
90.37%-(-1.2655 (-1.26%)
89.18% (-2.45%)
Computers
84.72%
85.00% (+0.28%)
84.70%
(-0.02%)
84.13% (-0.59%)
84.08% (40.64%)
84.17% (-0.55%)
81.64% (-3.08%)
Average
81.31%
81.57% (+0.26%)
81.44% (+0.13%) 81.21% (-0. (0.10% 81,30% (-0.01%)
81.32% (+0.01%)
80.06% (-1.25%)
Uniform Missing
Dataset
Full Features
60% Missing
70% Missing
80% Missing
90% Missing
95% Missing
90.5% Missing
82.72%
52.84% (+0.125) 82.61% (.0.11%) 82.63% (-0.09%) 82.61% (-0.118)
82.39% (-0.33%)
81.49% (-1.23%%
CitsSeer
70.00%
71,34% (+1.34%)
71.31% (+1.319)
72.21% (+2.21%)
72.26% (+2.26%)
72.61% (+2.61%)
73.15% (+3.15%)
PubMed
77.46%
77.33% (-0.13%)
77.21% (-0.25%)
77.38% (-0.08%)
77.33% (-0.13%)
76.96% (.0.50%)
77.46% (.0.00%)
Photo
91.63%
91.63% (-0.00%)
91.39% (-0.24%)
91.02%
(-0.619) 90.77% (-0.86%)
90.375-(11.2655 (-1.26%)
89, 89.40% (-2.23%)
Computers
84.72%
84.54% (-0.18%)
84.83% (+0.11%)
84.30% (-0.42%) 84.38% (-0.34%)
84.14% (-0,58%)
83.57% (-1.15%)
Average
81.31%
81.54% (+0.23%) 81.47% (+0.16%) 81.51% (+0.20%) 81.47% (+0.16%)
81.29% (-0.02%)
81.01% (-0.30%)
In the structural missing setting, FSD-CAP maintains or exceeds the performance of the full-feature setting when the missing rate below 95%, demonstrating its ability to handle substantial feature loss. When the missing rate reaches 99.5%, with only 0.5% of features observed, the average ac- curacy decreases by just 1.25% relative to the fully observed case. In the uniform missing setting, the performance drop is even smaller. At a 99.5% missing rate, the average decline is only 0.3%, confirming the robustness of FSD-CAP under extreme sparsity. On the CiteSeer dataset, FSD-CAP consistently outperforms the full-feature setting across all tested missing rates. Under the 99.5% uniform missing condition, it improves accuracy by 3. 3.15%, indicating that the reconstructed fea- tures can be more beneficial for downstream tasks than the original input. These results show that FSD-CAP remains effective and reliable across a wide range of missing levels and patterns.
A.2.10 ACCURACY COMPARISON WITH SOTA
We further evaluate the performance of FSD-CAP against the current state-of-the-art method (PCFT) on node classification accuracy at different missing rates across five datasets, results are shown in Table 12 FSD-CAP consistently outperforms PCFI across all missing patterns. Notably, as the miss- ing rate increases, the performance gap between FSD-CAP and PCFI becomes more pronounced. Specifically, when the missing rate reaches 99.5%, FSD-CAP achieves average accuracy im- provement of 3.67% across all datasets under the structure missing setting, and 2.24% under the uniform missing setting. On CiteSeer dataset with 99.5% structural missing rate, FSD-CAP achieves a performance gain of 5.88%, demonstrating its robustness to high levels of feature incompleteness compared to PCFI.
Compared to denser graphs such as Photo and Computers, FSD-CAP shows more significant im- provements on the sparser datasets (Cora, CiteSeer, and PubMed), with the highest gains observed on the Cora dataset. As revealed by the ablation study in Appendix [A.2. the second-stage class- aware propagation mechanism plays a critical role in enhancing performance, particularly in sparse graph scenarios. By incorporating class-level feature information, this module effectively enhances inter-class discrimination, thereby improving classification accuracy. In contrast, while the frac- tional subgraph diffusion stage offers certain improvements over conventional symmetrically nor- malized diffusion, its overall contribution to performance relatively modest. On a denser graph with better connectivity, the FSD stage benefits performance by emphasizing local neighborhood influence through a higher fractional exponent 7, leading to more localized diffusion and improved model behavior.
A.2.11 SENSITIVITY TO LABEL RATE
To investigate the impact of label availability, we evaluate the performance of FSD-CAP under varying label rates and feature missingness settings. Specifically, vary the number of labeled nodes per class as 5, 10, 20, 30, and 40, and test under three structural missing rates: 70%, 90%, 99.5%.
26

---

Published as a conference paper at ICLR 2026
Table 12: Node classification accuracy (%) of PCHI and FSD-CAP under different feature missing rates. The performance changes of FSD-CAP relative to PCFI are given in parentheses.
Structural Missing
Datavet
60% Missing
2056 Mixeing
80% Missing
90% Missing
2556 Missing
50.5% Missing
PCPI
FSD-CAP
PCF
FSD-CAP
PCFI
FSD-CAP
PCR
PSD-CAP
PCF
FSD:CAP
PCF
FSD-CAP
Cora
80.57%
82.75%xc22.1 1866:
80.15
(2.77%(42.7668)
19, 56% 82 22.228222))
78.8
42.558
77.54%
H2 (1.119))))
60.56 2075)
Chicseer
70.10%
71.299 19%8
69.699
71.19% (109))
10.214% 71. 1999))))..19%)
69.2668
(1.
69.58%
72 (3.27%)
66,05%
PuhMal
26.02% 77. 139 10%)
76.99%
76 26.969((0887777
75 877 76 76.99((-1.09) (99%
90.00%
77: (+) 12%)
76.07%
77. 195
4444
76.98%
Phono
91.41% 91.679 166)
80.88%
91.589((40.7005)
00.425 91 (1134((0925)
89.46%
90.799
35%)
80.009
90 00.376((11.288
(289))
87.38 3..
40.188((-) 8075)
Computer
84.91%
83,639
84.709((+10055)
K3.15% 84 84.139(40,998)
X2.40F
$4.0953
68%)
$1.50%
(4.1722)
78.71%
(1.648((229955)
Average
80.62% 81 5485
800065
81.4499(11 3.89) 19.799 81 81.215((11425)) 79.28%
51. (1..0((42.0668)
78.50%
81 (226(-244288
76, 99% (0.069(-3677)
Uniform Missing
Datuset
50% Missing
70% Missag
8U%
90% Missing
95% Missing
50.0%
PCF
FSD CAP
PCTT
USP-CAP
PCF]
FSD CAP
PCF
USD CAP
PCTT
FSD CAP
PCTI
FSD CAP
Cora
81.01%
82.84%c+1.886111
1802556
62.61%(+2265))
50.19%
826556(-24458)
79.55%
$2,619(63.065)
78.59
82 (3.3633
T8 18.55%
11,49%(-2.9458
Cieeeeer
71.10% 213365
69.97%
71.31%(+1.3445
10.12%
222116-2200%)
69.92% 72 02.299e22.3865
68.85%
72 72.615(337766)
11%
13.15% (+4.0)6))
PuhMed
76.29% 77.33% (.96)
15.90% 77.21%(--.315)
16.18%
77.38%((-1.27) (77)
76.58% 77.33% 7555)
76.26%
76 (0.766)
76.0
77,46 (-164
Phono
90.88% 91.59%)
90.97%
91.99%((00425))
91.02%((00007)
19.73%
90.778
59.00%
90.37%(
888.55%
89,
Computers
83.62%
34.549
93.40%
53.89%
84.30%(-0,119)
54.389
52.42%
(4.17%())..25)
81.64% 63.57%((+19955
80.58% 31.549(60099688 100100 (1.78% 81.51%((1.45%) 79.78% 81.478((1 (9,048 21.295)) 78.77% 31.015((222488)
Table 13: Accuracy(%) of FSD-CAP on Cora for node classification task under varying feature missing rates and label rates.
10
20
30
40
70% missing
76.41 3.21
78.42
1.29
80.49 # 1.86
81.33 # 1.97
81.39 + 1.86
90% missing
75.59 2.98
78.25 + 1.73
80.27 # 1.16
81,43 + 1.54
81.27 # 1.16
99.5% missing
#
78.07 # 1.87
79.55 # 1.57
79.89 = 2.01
79.95 + 1.65
Table 14: Accuracy(%) of FSD-CAP on Photo for node classification task under varying feature missing rates and label rates.
5
10
20
30
40
70% missing
86.84 = 1.98
88.18 1,71
91.35 # 0.56
91.57 # 0.35
91.43 + 0.48
90% missing
86.39 1.98
87.01 2.08
90.60 # 0.54
91.17 # 0.44
90.80 = 0.52
99.5% missing
84.52 2.32
84.93
88.98 # 1.01
89.42 # 0.92
88.88 + 0.97
Table 13 and Table report node classification accuracy on Cora and Photo under the structural missing setting, respectively. The results show that the performance of FSD-CAP consistently im- proves as the number of labeled nodes per class increases from to 30, and the gains begin to saturate when reaching 30-40 labels per class, indicating that the model has effectively leveraged the available supervision and approached convergence under the current configuration.
We further evaluate FSD-CAP in an extreme low-label setting (5 labels per class), combined with 99.5% feature missingness. We compare FSD-CAP against several recent state-of-the-arr baselines in this challenging setting. As shown in Table 15 while all methods suffer performance degradation due to the scarcity of supervision signals, CAP still significantly outperforms all competitors. This demonstrates the effectiveness of the class-level prior construction, which enables more robust propagation even when labeled data are extremely limited.
Table 15: Classification accuracy (%) under 99.5% structural missingness and 5 labeled nodes per class, The best results are highlighted in bold.
Cora
CiteSeer
PubMed
Photo
Computers
Average
FP PCFI FSD-CAP
74.45 + 3.16 67.05 2.64
64.71 9.10 82.01 3.06
71.07 = 4.56
71.86
67.76 # 3.46
58.68 # 4.55
66.91 # 6.46
81.26 # 2.02
73.30 # 2.09
69.58
74.49 + 2.94
68.26
2.59
68.79 3.13
84.52
2.32
75.71 + 1.86
74.35
27

---

Published as a conference paper at ICLR 2026
A.3
IMPLEMENTATION AND HYPERPARAMETERS
A.3.1 DATASETS
We evaluate FSD-CAP on five benchmark datasets: three citation networks (Cora, CiteSeer, and PubMed) and two Amazon co-purchase networks (Photo and Computers).
In the citation networks, nodes represent academic papers and edges indicate citation links. Node features are bag-of-wordh representations of paper abstracts, and each node is labeled according its research topic.
In the Amazon co-purchase networks, nodes correspond to products and edges connect items frequently purchased together. Node features are derived from bag-of-words encod- ings of product reviews, and labels reflect product categories.
All datasets are publicly available through the MITT-licened PyTorch Geometric library. We evaluate on the largest connected component of each graph. Dataset statisties provided in Table T6 using the setup in FP and PCFI.
Table 16: Dataset statistics and data splits used for semi-supervised node classification.
Dataset
Nodes
Edges
Attributes
Classes
Train/Valid/Test Nodes
Cora
2,485
5,069
1,433
7
0,0/1,360/985
CiteSeer
2.120
3,679
3,703
6
120/1,380/620
PubMed
19,717
44,324
500
3
00/1,440/18,21
Photo
7,487
119,043
745
8
160/1 (60/1,340/5,98
Computers
13,381
245,778
767
10
200/1,300/11,88
A.3.2 DATA SPLIT
For node classification, we follow a two-step data split. First, 1500 nodes are randomly selected as the development set, with the remainder used for testing. Within the development set, 20 nodes per class are randomly sampled for training, and the rest form the validation set, following the setup in FP and PCFI. Table T6 summarizes the data split for each dataset.
For link prediction, we adopt the edge split protocol from PCFI, allocating 85% of edges for training, 5% for validation, and 10% for testing. To ensure robust evaluation, all experiments with 10 random seeds. For each seed, we generate independent data splits and feature mask matrices M to simulate missing attributes. The final results reported the mean and standard deviation over these 10 runs.
repeated
The feature mask matrix M is initialized as an all-ones matrix with the same shape as the original feature matrix. Under uniform missing, m% of the entries are randomly set to zero. Under structural missing, % of the rows are randomly selected and set entirely to zero, simulating nodes with fully missing features.
A.3.3 BASELINE DETAILS
We compare FSD-CAP with the following methods:
i. Zero. A standard GCN trained the feature matrix with missing values replaced by zeros. We use the implementation from the PyTorch Geometric library (MIT License).
ii PaGCN. PaGCN applies partial graph convolution over observed features without explicitly modeling missingness. We use the authors' MIT-licensed code
iii. ITR. ITR performs adaptive imputation through two-stage process: initialization from graph structure followed by refinement using affinity updates. We use the Apache-2.0 licensed implemen- tation
https://github..o
28

---

Published as a conference paper at ICLR 2026
iv. ASD- VAE. ASD-VAD -AE learns shared latent space by maximizing the joint likelihood of attribute and structure views, then reconstructs features via decoupled decoding. We use the authors' publicly released code
FP. FP reconstructs features through iterative propagation using the normalized adjacency matrix. We use the Apache-2.0 licensed code
vi. PCFL. PCFI imputes missing values by performing inter-node and inter-channel diffusion weighted by pseudo-confidemm We use the official Apache-2.0 licensed implementation 8
vii. GRAFENNE. GRAFENNE uses a Shree-phase cressage-passingg framework on an allotropically transformed graph to learn from streaming features. We use the authors' released code 7
A.3.4 EVALUATION METRICS
We evaluate FSD-CAP on two standard graph learning tasks: semi-supervised node classification and link prediction.
Semi-supervised Node Classification. Given a graph with partially labeled nodes, the objective is to predict labels for the unlabeled nodes. Performance is measured by classification accuracy, defined as the proportion correctly predicted labels across all nodes. Higher accuracy indicates better generalization in the semi-supervised setting.
This task involves predicting missing edges between node pairs using learned feature representations. We use AUC (area under the ROC curve) and AP (average precision) as evaluation metrics. AUC quantifies the model's ability to rank existing edges above non-edges, while AP measures the area under the precision-recall curve, reflecting the balance between precision and recall.
Link Prediction.
A.3.5 EXPERIMENTAL SETTINGS
Semi-supervised Node Classification. All experiments use a consistent data split strategy with 10 random seeds per dataset. All models, except ASD-VAE and PaGCN, are implemented ing a three-layer GCN trained with the Adam optimizer. ASD-VAE uses the Katz-GCN archi- tecture as proposed in its original work, and PaGCN employs modified GCN designed for in- complete inputs. For methods with reported hyperparameters (ITR, GRAFENNE, ASD-VAR VAE), we follow the original configurations. For the remaining models, the learning rate is selected from (0.1, 0.01, 0.005, 0.001, 0.0005), and dropout from (0.0. 0.25, 0.5]. based on validation perfor- mance. All experiments are run on a 40-core Intel Xeon Silver 4210R CPU with 4 NVIDIA RTX 4090 GPUs (24GB each).
methods are evaluated under both structural and uniform missing settings across varying missing rates wrr except ITR, which is applicable only to structural missing where node features are either fully observed or fully missing.
Link Prediction. We adopt the same 10-split strategy across all datasets. All models are imple- mented using two-layer Graph Autoencoder and trained with Adam. Hyperparameters are tuned on the validation set, with the same learning rate and dropout search space used the node classifi- cation task.
A.3.6 FSD-CAP IMPLEMENTATION
For semi-supervised node classification, set the GCN learning rate to 0.01 with dropout 0.5 on Cora, CiteSeer, and Computers. On PubMed and Photo, the learning rate is 0.005, with dropout values of 0.5 and 0.25, respectively. The pre-trained GCN used for pseudo-label generation adopts the same settings. Following PCFI, the number of propagation steps K is fixed at 100, sufficient for convergence.
httposs//hhhaboooo///iggghhhhh/s
httpas//aaibbb..co//deemm//////
29

---

Published as a conference paper at ICLR 2026
We tune the hyperparameters (fractionnl diffusion exponent). À (feature retention coefficient), and (temperature) using grid search. For sparse datasets (Cora, CiteSeer, PubMed), y is selected from [0.6, 1.6]; for dense datasets (Photo, Computers), from [2.0, 4.0). both with step size of 0.2. À is searched in [o, 1] with step 0.1. is selected from {1, 5, 25, 100, 250, 1000).
In the link prediction task, the GCN classifier uses the same configuration above. For the down- stream Graph Autoencoder, the dropout rate is fixed at 0.5. Learning rates are set to 0.005 for Cora and CiteSeer, 0.1 for PubMed, and 0.0005 for Photo and Computers. Hyperparameter tuning fol- lows the same protocol: À E [0, 1J with step 0.1, T E {0.001, 0.01, 0.1, 1, 5, 10, 25, 50). For we use [4.0, 6.0] on dense datasets and [0.6, 1.6] on sparse datasets, both with step 0.2.
We report the selected hyperparameter configurations for semi-supervised node classification and link prediction under 99.5% feature missing rate in Table 17 and Table respectively. Additional parameter sensitivity analysis is presented in Appendix A.2.2
Table 17: Hyperparameter configurations for FSD-CAP on semi-supervised node classification task.
Parameter
Cora
CiteSeer
PubMed
Photo
Computers
?
1.2
1.2
1.6
2.8
3.8
Structural Missing
0,2
0.9
0.6
0.3
0.4
T
250
100
1.2
1.2
1.2
2.8
4.0
Uniform Missing
0.2
0.7
0.0
0.3
T
250
250
5
25
100
Table 18: Hyperparameter configurations for FSD-CA CAP on link prediction task.
Parameter
Cora
CiteSeer
PubMed
Photo
Computers
1.4
1.4
1.4
4.2
5.0
Structural Missing
0.2
0.3
0.0
0.0
T
5
25
10
0.001
0,001
1.2
1.6
1.6
4.4
5.6
Uniform Missing
0.0
0.0
0.0
0.0
0.0
5
25
25
0.01
0.001
The implementation of FSD-CAP (Apache-2.0 licensed) will made publicly available upon pub- lication.
A.3.7 ADDITIONAL DISCUSSION
Limitations. This work focuses solely on missing node attributes and does not address missing or uncertain edges. In many practical settings, both node features and graph topology may be incom- plete. Extending FSD-CAP to handle joint feature and structure imputation remains an open and important direction for future research.
Societal Impacts. FSD-CAP improves the robustness of GNNs under high feature-missing rates and may benefit applications in domains such social networks and recommender systems. How- ever, as with any imputation technique, there a risk misuse, particularly in inferring sensitive or private attributes from partial data. We encourage responsible use, including proper access controls and ethical oversight, especially when applying the model to contexts involving personal or sensitive information.
30

---

Published as a conference paper at ICLR 2026
PubMed (Structural)
Photo (Structural)
Computers (Structural)
80
77
Zero
02
74
PaGCN
FP
65
0.5
0.7
0.8
0.9
0.85
0.995
0.6
0.7
0.8
0.8
0.95
0.965
0.6
0.7
08
0.9
0.06
0.995
PubMed (Uniform)
Photo (Uniform)
Computers (Uniform)
80
GRAFENNE
77
62
ASD-VAE
74
PCFI
-FSD-CAP
0.5
0.7
0.9
0.86
0.995
0.6
0.7
0.8
0.8
0:85
0.965
06
0.7 Missing
08
0.9
6.86
0.895
Missing
Figure 12: Node classification accuracy (%) PubMed, Photo and Computers for {0.6, 0.7, 0.8, 0.9, 0.95, 0.995). The top row shows structural missing; the bottom row shows uni- form missing. Methods that are inapplicable result in out-of-memory errors omitted.
A.4 SUPPLEMENTARY FIGURES AND TABLES
A.4.1 ACCURACY ON PUBMED, PHOTO AND COMPUTERS UNDER VARYING MISSING RATES.
This subsection presents the classification accuracy results for the PubMed, Photo and Computers datasets under structural and uniform missing scenarios, with missing rates (mr) ranging from 0.6 0.995. The corresponding figure is shown Figures [2
A.5 DECLARATION OF LLM USAGE
The of large language models (LLMs) is only for editing purposes such grammar, spelling, and formatting checks, and does not influence the core methodology. scientific rigor, or originality of this research. LLMs not involved in the design, analysis, interpretation of the study.
A.6 PSEUDOCODE FRACTIONAL SUBGRAPH DIFFUSION WITH CLASS-AWARE PROPAGATION (FSD-CAP)
A.6.1 PSEUDOCODE OF FRACTIONAL SUBGRAPH DIFFUSION (ALGORITHM)
A.6.2 PSEUDOCODE OF CLASS- AWARE PROPAGATION (ALGORITIMM 2
31

---

Published as a conference paper at ICLR 2026
Algorithm FSD algorithm
Input: Graph g = {X, A}, Known/unknown node sets V +//- for each channel e, Binary mask
matrix M, True labels Number of channels F and node N, Hyper- parameters (%, K, X)
for channel = ... Fd
2: Initialize sub-graph g(
3: Keep starting m (Initialize the number of sub-layers)
4: Read subgraphs (m)) =k-hopSuubgrah( (14p A. m) (Extract of m- hop subgraph)
5: while (m)) # do
6: Normalize A (m) D 1/2 1-1 A(m) D-1/2 (Symmetric normalized adjacency matrix) 7: Fractional weighted matrix A)j = (Aij (mm) // (A )²)
8: for = to K do
9: x (1) x (m) (0) O M + x (1. 1) + Ax (m (K)) M)
end for
11:
+ 1 (Enter the next level of subgraph)
12: Extended subgraphs (m) =k-hopSubgraph m)
13: end while
14:
(K) (Update final features of the current channel)
end for
16: Stack {x*) to form pre-imputed X
17: return Pre-imputed feature matrix X
Algorithm CAP algorithm
Input: Graph G = {X, A}, Knowa/unknown node sets V / for each channel E, Binary mask
matrix M, True labels Number of node N and classes C, Hyper-parameters
1: Get pseudo-labels ý and predicted class probability ý using GNN with (A, X, y) and tempera- ture T
2: for -= = 1 to N do
do 4: P.(cc) - (1/Wal ESEN, (()==))
3: for
5: end for
6: information entropy 8; = -11/l08 (IVa))) Eneo P.(c) log (Pi(c)
7: end for
8: for c= to C do
9: compute class-specific feature: m7e) = (E 5:) . xii) (E - -:))
10: Define virtual class node vl() and class subset V(e) = (u(d) up!e)
( extract_matrixXX v(() (x(e) contains imputed features of nodes in v(e))
11:
12: Feature Matrix for yle); (c) [x sto)"" (row-wise concatenation)
Initialize W(() zero matrix of size | x |Vle|
for each node y(c) do
W! Bi. (self-loop weight: confidence in class c)
15:
(e r. = Úi. from node v; class node n
17: end for
Class Propagation (c) (c)
19: Class feature matrix X, = extract cerractmatrix(2a5 vy()))
20: X combine matbine_matrixxx.... Xx, M) (restore known features and update refined features)
21: end for
22: return Imputed feature matrix X
32


Reviews:
[{"review_id": "B7ilk0Fc2b", "reviewer": "Reviewer_Wp9X", "summary": "The authors present FSD-CAP, a novel method for missing feature imputation within graph representation learning by applying a 1) Factional diffusion operator, 2) Progressive subgraph diffusion, and 3) Class-level feature refinement. The authors introduce the mechanisms through a series of propositions and theorems that details the nuance between needing to extrapolate from coarser to finer features within subgraph diffusion. Notably, FSD-CAP outperforms the current SOTA method PCF1 by a fairly-significant margin and shows improvement over standard baselines on the CiteSeer dataset.", "questions": "* In regards to Remark 1, is a super-diffusion regime something that other diffusion models remain in since they do not have a class-refinement mechanism?\n* Lines 184-187: Given that much of this is step-by-step instructions of FSD-CAP function, this seems better formatted in an algorithm? \n* Lines 214-215: equation 3, equation 4 ==> uppercase?\n* Theorem 2: The idea that you need Equation 3 for updates and Equation 4 for maintaining stability makes sense. However, I am confused by the notation in Theorem 2. Does $x^{(x)}(t)$ apply both Equation 3 and Equation 4 per-layer in sequence (Equation 3 - top to Equation 4 - bottom), as expected with piece-wise functions (indicated by the brackets)? I can certainly see that it would be a 'layer-wise' function, but it still seems confusing that $x^{(x)}(t)$ is the same regardless of the right-hand side of the function. This could be a mistake on my part as a reviewer, but I want to clarify with the authors, is this intended? If so, wouldn't an algorithmic description provide more clarity on the order of operations?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The authors provide concise yet clear details about the uniqueness of the operators and diffusion refinement stages for FSD-CAP. Further explanations detail clarifying insights about the practical considerations from moving between localized and distant updates.\n2) The writing of the paper flows well, transitions between sections make sense and are not abrupt. This eases understanding of more technical concepts.\n3) FSD-CAP significantly outperforms current SOTA methods like PCF1, indicating a potentially broad-level of promise for subgraph diffusion models in other applications of graph representation learning.", "weaknesses": "1) Although this is common within existing graph-diffusion feature imputation literature, FSD-CAP only tests on Cora, CiteSeer, PubMed, and Amazon-Photo, Amazon-Computers. Further tests on smaller synthetic datasets with defined local and global structures could indicate the power of Theorem 2 in potentially more-difficult scenarios\n2) There are no algorithms within the paper to describe the process of FSD-CAP. Although this is partially-abated by the inclusion of code, the pseudo-code seems important for clarity when detailing how the equations within the paper function in-practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PiU68WNRif", "reviewer": "Reviewer_66Pn", "summary": "This paper proposes FSD-CAP (Fractional Subgraph Diffusion with Class-Aware Propagation), a diffusion-based framework for imputing missing node features in graphs with partially observed features. The first stage, fractional subgraph diffusion, introduces a tunable fractional operator that adjusts propagation sharpness according to local graph structure, and progressively expands diffusion from observed to unobserved nodes to limit error accumulation. The second stage, class-aware propagation, refines the imputed features using pseudo-labels and neighborhood-entropy weighting to promote intra-class consistency and inter-class separation. Experiments demonstrate the effectiveness of FSD-CAP on semi-supervised node classification and link prediction at a high missing rate.", "questions": "Q1. Could the authors provide performance comparisons with state-of-the-art methods [1, 2] for both node classification and link prediction tasks?\n\nQ2. Since the proposed method leverages label information, could the authors show how performance changes when the label rate is lower than the current experimental setting?\n\nQ3. The Fractional Diffusion Operator appears to down-weight the participation of nodes with higher degrees during diffusion. Could the authors clarify the motivation or empirical rationale (not resulting performance) behind this design choice?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The authors present a new diffusion mechanism for imputation on graph-structured data.\n2. The paper is clearly written and organized.", "weaknesses": "1. State-of-the-art methods [1, 2] are missing from the comparison. It appears that the state-of-the-art methods [1,2] achieve better performance than the proposed method, raising questions about the claimed performance advantages. Futhermore, [2] adopts a similar idea of leveraging label information during propagation.\n2. Since the proposed method leverages label information, its performance is likely to depend on label availability; however, no experiments are provided to analyze sensitivity to different label rates.\n3. In link prediction, it is generally assumed that only graph connectivity is available, but the paper additionally utilizes node labels.\n4. The motivation or empirical observation behind the design of the Fractional Diffusion Operator is insufficiently explained.\n5. It would be preferable to represent matrices and vectors in italicized bold.\n\n[1] Um, Daeho, et al. \"Propagate and Inject: Revisiting Propagation-Based Feature Imputation for Graphs with Partially Observed Features.\" ICML 2025.\\\n[2] Yun, Sukwon, et al. \"Oldie but Goodie: Re-illuminating Label Propagation on Graphs with Partially Observed Features.\" KDD 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "12jkp0qld2", "reviewer": "Reviewer_rfQB", "summary": "This paper proposes FSD-CAP, a two-stage framework for imputing missing node features in graphs under high missing rates. The first stage uses fractional subgraph diffusion (FSD). The second stage applies class-aware propagation (CAP) using pseudo-labels and neighborhood entropy for feature refinement.", "questions": "The authors should address the concerns raised in the weakness section above.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The fractional diffusion operator provides principled control over propagation sharpness, interpolating between uniform averaging and dominant-neighbor selection.\n\nProgressive subgraph expansion reduces error accumulation compared to global diffusion.\n\nAchieves competitive results across multiple datasets and missing patterns.", "weaknesses": "Table 11 shows counterintuitive performance gains with increasing missing rates: CiteSeer achieves 71.94% accuracy at 99.5% structural missing versus 70.00% with full features. Similar anomalies appear across multiple datasets and missing types, violating basic expectations that more missing information should degrade performance.\n\nCritical absence of recent self-supervised graph learning methods for feature reconstruction (e.g., GRACE, GraphCL, MVGRL).\n\nMissing comparisons with masked graph modeling approaches that follow BERT-style pre-training paradigms for graph feature completion.\n\nNo evaluation against graph contrastive learning methods (SimGRACE, GraphMAE, MaskGAE) that have shown strong performance on incomplete graphs.\n\nLacks comparison with recent graph pre-training methods and foundation models that can handle missing features through representation learning.\n\nMissing recent diffusion-based graph generation methods that could serve as feature completion baselines.\n\nProgressive subgraph expansion assumes feature similarity decreases with graph distance, but this may not hold for heterophilous graphs or when class boundaries cross multiple hops.\n\nConvergence analysis (Theorems 2-3) relies on strong connectivity assumptions that may be violated in practice when 99.5% of features are missing.\n\nCode availability promises may be insufficient given the complexity of the two-stage framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u8QFkBHuSL", "reviewer": "Reviewer_vLJV", "summary": "This paper introduces FSD-CAP, a two-stage framework for imputing missing node features, especially in the cases with high sparsity of node metadata. The framework performs an initial imputation based on \"fractional diffusion operator\" to adjust propagation sharpness based on local structure, with \"progressive subgraph diffusion\" mechanism that expands layer-by-layer from observed nodes, localizing diffusion and limiting error propagation. Then, Class-Aware Propagation (CAP) refines the imputed features by applying a standard GCN to the FSD-imputed features to generate synthetic class labels. CAP then creates one vector for each class, and this class-specific vectors are formed based on the nodes inside each class but not those in the boundaries (though the \"credibility\" weight calculated by the faction of neighbors sharing the same label with each focal node in a class.) By down-weighting the features from the boundary nodes and imputing these class-specific vectors into the nodes in its class, this class-specific vectors serve as counteractive mechanism against over-smoothing. The effectiveness is demonstrated using the node classification and link prediction benchmarks, confirming that the proposed method is robust against the missing features of nodes.", "questions": "Q1: What are the underlying premise for the proposed solution?\n\nQ2: What are the performance gain of the proposed imputation methods against traditional but well-accepted generic imputation methods (i.e., global mean and k-nn based method)?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The authors introduced a practical solution to balance imputation and over-smoothing though the fractional diffusion operator and CAP as two counteracting mechanisms. The authors also demonstrated the effectiveness in node classification and link prediction problems, which demonstrate the generalizability of the proposed solution for the missing feature problem.", "weaknesses": "W1 \nThe paper would be clearer if it explicitly stated the key assumptions underlying the proposed solution. In essence, the methods succeed only when three conditions hold: (1) the node features are informative for the task at hand; (2) the features are homophilic (adjacent nodes tend to share similar values); and (3) the graph exhibits community structure in which each community is dominated by nodes with the same feature label. It is important to note that node metadata do not always reflect the network topology, and not every metadata type is useful for a given application (see [1]). If condition (2) fails (i.e., neighboring nodes are likely to have different features), the diffusion process will incorrectly impute missing values. Moreover, the CAP framework relies on the premise that node features and community structure are strongly coupled. The fractional diffusion operator is built from the normalized adjacency matrix, and its mixing behavior is largely dictated by the community structure (as captured by the Fiedler vector). When node features are not correlated with the community structure, the diffusion does not remain localized; consequently, many nodes have similar feature values, and CAP loses its ability to distinguish clusters within the network.\n\nI'm overall positive about the ideas from the authors but suggest them to make it very explicit about the key premises the method is based on, and clarify when the proposed solution works and do not work. \n\n[1] Peel, Leto, Daniel B. Larremore, and Aaron Clauset. \"The ground truth about metadata and community detection in networks.\" Science advances 3.5 (2017): e1602548.\n\nW2\nI appreciate the authors to include GCN as a baseline, with missing features imputed with zeros. The paper could be benefit from providing other common heuristics and the comparisons against more recent convolution based graph neural networks. For example, another common imputation method is to fill the missing feature with a global mean. Alongside is the k-nearest neighbor methods. These are pretty common imputation methods that do not require graph structure (and thus are less prone to the violation of the assumptions discussed above). Also GCN (Kipf & Welling, 2017) is already primitive, and the GNN field has advanced significantly since 2017. I suggest the authors to include advanced and commonly used models (not necessarily the state-of-the-art models, such as GAT) to demonstrate the broader applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oy8UoUhMGN", "reviewer": "Reviewer_fH1t", "summary": "This paper addresses the challenge of graph feature imputation under extreme missing rates—a limitation of existing methods that fail to produce reliable estimates or propagate errors in sparse graphs. The authors propose FSD-CAP, a two-stage diffusion-based framework designed to enhance imputation robustness and adaptability:", "questions": "1. How would FSD-CAP need to be modified to handle both missing node features and missing edges? For example, could the subgraph expansion stage incorporate edge confidence scores to avoid propagating information through uncertain edges?\n2. Most experiments use static graphs. Would FSD-CAP’s progressive subgraph expansion adapt to dynamic graphs (e.g., evolving social networks with new nodes/edges), or would frequent subgraph recomputation be computationally prohibitive?", "limitations": "", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. FSD-CAP combines three components (fractional diffusion, progressive subgraphs, class-aware refinement) in a cohesive framework, avoiding the \"black-box\" nature of many deep learning-based imputers.\n2. The method’s two-stage pipeline is visualized and described in plain terms, making it accessible to researchers new to graph diffusion. Appendices provide implementation code details, hyperparameter ranges, and extra experiments (e.g., accuracy vs. distance from observed nodes).", "weaknesses": "1.  The paper only addresses missing node attributes, ignoring missing or noisy edges—a common real-world scenario (e.g., incomplete social network connections). Extending FSD-CAP to joint feature-structure imputation is mentioned as future work but is a key limitation for broader applicability.\n2.  Experiments focus on standard benchmarks (citation networks, product co-purchase graphs) but lack a real-domain application (e.g., imputing missing gene features in biological networks, user attributes in recommendation systems). A case study would strengthen the paper’s practical impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)