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, [0.9em] Xidian University, Xi’an, China · 2026

Read FSD-CAP: Fractional Subgraph Diffusion with Class-Aware Propagation for Graph Feature Imputation by Xin Qiao, Shijie Sun , Anqi Dong , Cong Hua, Xia Zhao, Longfei Zhang, Guangming Zhu, Liang Zhang, [0.9em] Xidian University, Xi’an, China (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18938.txt.

Introduction

Xin Qiao and seven co-authors fill in missing node features in graphs when most data is gone. Graphs store facts as node features, but real graphs often lose many of them. Older methods, built on hidden features or broad spread, give shaky guesses and can pass errors along the graph.

Their method, FSD-CAP, works in two stages to lift the quality of the filled in values. It spreads facts across parts of the graph while staying aware of each node's class. Better fills under extreme sparsity matter wherever graphs are built from patchy records, from social data to molecule sets.

Catalog record

CREATORXin Qiao, Shijie Sun , Anqi Dong , Cong Hua, Xia Zhao, Longfei Zhang, Guangming Zhu, Liang Zhang, [0.9em] Xidian University, Xi’an, China
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18938

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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, [0.9em] Xidian University, Xi’an, China 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 % 99.5\% of features missing across five benchmark datasets, FSD-CAP achieves average accuracies of 80.06 % 80.06\% (structural) and 81.01 % 81.01\% (uniform) in node classification, close to the 81.31 % 81.31\% achieved by a standard GCN with full features. For link prediction under the same setting, it reaches AUC scores of 91.65 % 91.65\% (structural) and 92.41 % 92.41\% (uniform), compared to 95.06 % 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 . 1 Introduction Graph Neural Networks (GNNs) are widely used for learning from graph-structured data, with successful applications in social networks ( 2 ) , biology ( 22 ) , and recommendation systems ( 13 ) . GNN architectures ( 4 ; 8 ) always assume nodal features are fully observed, allowing information to be aggregated effectively from neighboring nodes. In practice, this assumption often fails. Node attributes are frequently missing due to privacy constraints, sensor failures, or incomplete data collection. High missing rates disrupt the message-passing process and significantly degrade model performance. A variety of methods have been proposed for imputing missing features, including statistical estimators ( 29 ) , machine learning models ( 5 ) , and generative approaches ( 34 ) . Recent work has shifted toward deep learning techniques that model the distribution of node attributes. These include latent space models that align observed features with learned embeddings ( 6 ; 37 ) , and GNN-based architectures designed to operate on incomplete inputs ( 30 ) . These approaches, which rely on correlations in both feature and graph structure, are effective under moderate missing rates but experience significant performance degradation as sparsity increases, ultimately falling below simple baselines like zero-filling or mean imputation in highly incomplete settings ( 39 ) . An alternative class of methods, based on diffusion, propagates observed features across the graph under the assumption of node homophily ( 26 ; 33 ; 35 ) . These methods are typically lightweight, parameter-free, and more robust under high missing rates. However, most diffusion approaches apply uniform propagation across all nodes, without accounting for local structure or propagation order. As a 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-CAP), a 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-neighbor selection, allowing it to adapt to varied connectivity. Second, to reduce error accumulation from global diffusion, we introduce a graph-distance-guided subgraph expansion strategy. This mechanism begins with observed nodes and progressively includes less certain regions, enabling early reliable estimates and improved stability. Third, a class-aware refinement step uses pseudo-labels and neighborhood entropy to enhance the imputed features, promoting intra-class consistency and inter-class separation. In the tasks of semi-supervised node classification and link prediction on five benchmark datasets, this method consistently outperforms state-of-the-art imputation approaches and maintains robustness across a wide range of missing rates. Notably, on datasets such as CiteSeer and PubMed, FSD-CAP exhibits higher performance under extreme missing conditions compared to when utilizing fully observed features, thereby demonstrating its effectiveness in sparse scenarios. Furthermore, when compared to other models, FSD-CAP also achieves superior performance on two large-scale datasets and four heterophilous datasets, showcasing its strong adaptability (Appendix A.2.7 and Appendix A.2.8 ). Figure 1: FSD-CAP Pipeline: Given graph \mathcal{G} and partially observed feature matrix X , FSD-CAP recovers the full matrix \hat{X} . (i) FSD: Starting from observed nodes, it gradually expands the radius of the subgraph and performs progressive subgraph diffusion using fractional diffusion operators \mathbf{A}^{\gamma,0} , \mathbf{A}^{\gamma,1} , \mathbf{A}^{\gamma,2} , producing a preliminary imputed feature matrix. (ii) CAP: Based on the FSD-imputed features, pseudo-labels are assigned by a classifier to form class-wise graphs, each associated with class-specific X^{c} and \mathbf{W}^{c} . Feature propagation within each class graph yields the final output \hat{X} . 2 Proposed Method 2.1 Preliminaries and overview Our objective is to learn from graphs with incomplete node features, focusing on two common settings: structural missing , where some nodes have no observed features, and uniform missing , where entries are randomly missing across the feature matrix. The goal is to impute missing attributes in a way that enables robust representation learning, especially under high missing rates where standard GNNs fail. To this end, we propose a two-stage imputation framework designed to stabilize learning and adapt to local graph structure. The overall architecture is shown in Figure 1 and consists of the following three key components. (i) Fractional diffusion operator. We generalize the standard diffusion matrix ( 11 ) 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 information 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 to unobserved nodes (Section 2.3 ), instead of global diffusion ( 26 ) . At each step, only a localized subgraph is updated, thereby reducing error accumulation and improving stability. It prioritizes easy-to-complete 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 2.4 ) to improve the discriminability of features. These signals are propagated within intra-class graphs to refine feature estimates and improve semantic consistency. 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 \mathcal{G}=(\mathcal{V},\mathcal{E}) denote an undirected graph, where \mathcal{V}=\{v_{1},v_{2},\dots,v_{N}\} is the set of N nodes and \mathcal{E}\subseteq\mathcal{V}\times\mathcal{V} is the set of edges. Each node v_{k} is associated with a feature vector in \mathbb{R}^{F} , and we collect all node features in a matrix X\in\mathbb{R}^{N\times F} , where X_{[k,:]} denotes the feature vector of node v_{k} . The topology of the graph is represented by an adjacency matrix A\in\{0,1\}^{N\times

Read the complete text