Gene-Gene Relationship Modeling Based on Genetic Evidence for Single-Cell RNA-Seq Data Imputation
Authors: Daeho Um
Ji Won Yoon
Seong Jin Ahn
Yunha Yeo
Venue: NeurIPS 2024 poster (2024)
Keywords: scRNA-seq
imputation
bioinformatics
Primary area: machine_learning_for_healthcare
TL;DR: We propose a novel scRNA-seq data imputation scheme based on genetic evidence.

Abstract: Single-cell RNA sequencing (scRNA-seq) technologies enable the exploration of cellular heterogeneity and facilitate the construction of cell atlases. However, scRNA-seq data often contain a large portion of missing values (false zeros) or noisy values, hindering downstream analyses. To recover these false zeros, propagation-based imputation methods have been proposed using $k$-NN graphs. However they model only associating relationships among genes within a cell, while, according to well-known genetic evidence, there are both associating and dissociating relationships among genes. To apply this genetic evidence to gene-gene relationship modeling, this paper proposes a novel imputation method that newly employs dissociating relationships in addition to associating relationships. Our method constructs a $k$-NN graph to additionally model dissociating relationships via the negation of a given cell-gene matrix. Moreover, our method standardizes the value distribution (mean and variance) of each gene to have standard distributions regardless of the gene. Through extensive experiments, we demonstrate that the proposed method achieves exceptional performance gains over state-of-the-art methods in both cell clustering and gene expression recovery across six scRNA-seq datasets, validating the significance of using complete gene-gene relationships in accordance with genetic evidence. The source code is available at https://github.com/daehoum1/scCR.

Gene-Gene Relationship Modeling Based on Genetic Evidence for Single-Cell RNA-Seq Data Imputation
Daeho Um"
Won Yoon
Samsung Advanced Institute of Technology (SAIT) daeho. um@samsung. com
Chung-Ang University j iiwonyoon@cau. ac.
Seong Jin Ahn
Yunha Yeo
Korca Advanced Institute of Science and Technology (KAIST) 8ja1015@kaist.acc ac.
Korea University
serinahyeo@korea.accu kr
Abstract
Single-cell RNA sequencing (scRNA-seq) technologies enable the exploration of cellular heterogeneity and facilitate the construction of cell atlases. However, scRNA-seq data often contain large portion of missing values (false zeros) or noisy values, hindering downstream analyses. To recover these false zeros, propagation-base imputation methods have been proposed using k--N graphs. However they model only associating relationships among genes within a cell, while, according to well-known genetic evidence, there are both associating and dissociating relationships among genes. To apply this genetic evidence to gene-gene relationship modeling, this paper proposes novel imputation method that newly employs dissociating relationships in addition to associating relationships. Our method constructs a k-NN graph to additionally model dissociating relationships via the negation of given cell-gent -ele matrix. Moreover, method standardizes the value distribution (mean and variance) each gene to have standard distributions regardless of the gene. Through extensive experiments, demonstrate that the proposed method achieves exceptional performance gains over state-of-the-an methods in both cell clustering and gene expression recovery across six ScRNA-seq datasets, validating the significance of using complete gene-gene relationships in accordance with genetic evidence. The source code is available at https; //github. com/ sggithuub.coo//aahhou///t/t dawhhom/schomc
1 Introduction
Single-cell RNA sequencing (scRNA-seq) has become one of the most widely used technologies in biomedical research due to its ability to measure genome-wide gene expression at the single-cell level 113 ScRNA-seq enables
discover novel cell types [4), analyze cellular
trajectories [5], and improve understanding human disease [6] 77. How- ever, scRNA-seq analysis encounters significant challenges due to the high rate of zero values in scRNA-seq data represented by cell-gene matrix. Specifically, owing the low RNA capture rate, scRNA-seq data often contain zero values. These zero values represent unobserved gene expression resulting from both technical omissions (referred dropouts 8) and true biological absence. Moreover, even non-zero val- ues in scRNA-seq data suffer from various sources of noise, such cell cycle effects and batch effects I0].
O: Gene
Associate (co-occur)
Dissociate (avoid)
Figure 1: Within a cell, there are two types of re- lationships among genes.
Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

To deal with the missing or noisy gene expression in scRNA-sey data, diverse imputation methods have been proposed. which can be categorized into non-graph-basee graph neural network (GNN)- based, and propagation-baser methods. Among these methods, propagation-baser methods [1] 12 have been favored due to their outstanding performance. The propagation- hased methods construct a k-nearest neighbor (k-NN) graph on scRNA-seq data represented as a cell-gene matrix, and fill in missing values by propagating nonzero values on the k-NN graph. Despite their effectiveness, they overlook well-known genetic evidence [13 [14], which means that there are two types of relationships between genes: associating relationship and dissociating one. As shown in Figure | associating relationships represent genes that co-occur, whereas dissociating relationships represent genes that avoid co-occurrence.
However, the existing methods cannot model the dissociating gene-gen cene-gene relationship by constructing simple k-NN graph to connect only the associating genes with similar occurrence patterns. Conse- quently, these methods fail to connect dissociating genes. Within cell, when considering the value to be imputed for gene Q, the value for its associating gene can assist in inferring the value for gene Q. However, its dissociating gene can also provide crucial information: if its dissociating gene has a high value, the value for gene Q may be low, as they tend to avoid each other. Additionally, the value distribution of a gene often differs significantly from that of other genes [T]. Therefore, the sum of propagated values from other genes may lead to the mixing of values at various scales, which is not suitable for data recovery.
To resolve the aforementioned problems, we propose a novel propagation called Single-Cell Complete Relationship (scCR) for scRNA-seo data, which models both associating and dissociating gene-gene relationships. scCR concatenates a given cell-gene matrix and its negation, then standardizes the value distribution (mean and variance) in each column (i.e., gene) of the concatenated matrix. Subsequently, we construct a k-NN graph on this concatenated and standardized matrix to connect both associating and dissociating genes within cell. Through a propagation process on this k-NN graph, scCR effectively denoises scRNA-seq data by capturing complete gene- gene relationships. Extensive experimental results demonstrate that scCR significantly outperforms state-of-the-as methods in both gene expression recovery and cell clustering. Through experiment, we further confirm that seCR model dissociating gene-gene relationships inherent in scRNA-seq data.
imputation scheme
The main contributions of our work are summarized as follows: (1) We newly propose an effective imputation method for scRNA-seq data, which is based on the genetic evidence. Our method can model complete gene-gent gene-gene relationships, including both associating and dissociating relationships; (2) We employ standardization step before propagation among genes for additional performance improvement in downstream tasks on scRNA-seq data; (3) By modeling dissociating gene-gent gene relationships and utilizing the standardization step, our scCR significantly improves performance in various downstream tasks, outperforming the state-of-thh-aar methods by a large margin.
2 Related Work
Handling noise in scRNA-seq data. Approaches for handling noise in scRNA-seq data can be categorized into non-graph-based, GNN-based, and propagation-basee methods. As pioneering efforts to impute zero values, con-graph-basee methods predominantly employ either statistical techniques [16 17 or autoencoder frameworks [17,18 Building on this foundation, graph- based approaches, including baN-based and propagation based methods, have received significant at- tention due to their ability to model relationships among cells and genes through graph structures. scGNN 19 leverages cell-cell relationships by constructing a cell-cell similarity matrix within a graph autoencoder framework. SeGCL [20] a graph autoencoder framework that exploits contrastive learning to capture cell-cell relationships. scTAG [21 is clustering method that employs graph autoencoder framework using a cell-cell K-NN graph, which jointly optimizes clustering loss and reconstruction loss.
Propagation-base based imputation in scRNA-seq data. Propagation- based imputation methods have shown their superiority scRNA-seg seq data imputation. They promote greater similarity in gene ex- pression among cells that are already similar through iterative propagation steps. While MAGIC [22] utilizes a diffusion mechanism to denoise ScRNA-seq data, updating values through the diffusion of both zero values and observed nonzero values may be significantly affected by false zero val- ues (i.e., dropouts). To address this issue, Feature Propagation (FP) (23] can be good solution because FP preserves observed values during diffusion while updates unobserved values through
2

---

X
X
resoale
(X-m))
geneggnn weing K
X
OK
cell
row R-NN graph construction
tweighted avenge
Standaciiztion
X
Stuge Pre-imputation
Concatenation
Stage 2: Complete Relationship
Gones
cell-eall TP Amiii)
Cells
cell-eall FP using A
X
cillooall Soll FP using A
X
A
Stage 3: Denoising
AWOS
Figure 2: A brief overview of Single- Complete Relationship (scCR).
diffusion. Propagation- based imputation methods have shown their superiority in scRNA-seq data imputation. scFP [11] adopts FP developed for graph-structured data to resolve imputation for scRNA-seq data. scFP constructs cell-cell k-NN graph and applies FP for the imputation of zero values. Very recently, [12] proposes scBFP to utilize gene-gene relationships as well as cell-cell relationships. scBFP consists of two stages, and in each stage, applies FP using gene-gene k-NN graph and a cell-cell k-NN graph, respectively. Although scBFP is designed to leverage gene-gene relationships, the simple addition of FP using a gene-gene k-NN graph cannot effectively exploit gene-gene relationships due to the following two reasons: (1) a gene-gene k-NN graph can connect only associating genes which have co-occurrence relationships while overlooking the presence of dissociating gene-gene relationships; (2) Since the distributions for each gene significantly varies, propagation without additional processing will degrade recovery performance.
Preliminaries
Notation. A graph can be represented G = (V,E), where V = (ui,..., uN) is the set of N nodes and the set of edges. The connectivity of G can be represented by the adjacency matrix A E 10,1] with Ai 1 iff (vi, vT) & and Aij 0 otherwise. Given arbitrary matrix B E Raxb we let kNN(.) Raxb > {R] jaaa be function that generates normalized adjacency matrix A of the row-row k-NN graph based on cosine similarity. Here, the normalized adjacency matrix A is obtained by A = D 1/2 AD 1/2 where A is the adjacency matrix of the k-NN graph and D is a degree matrix with diagonal entries D,,: Σ, Ar,, Consequently, while (NN(X) yields
-cel < (0, 10 1)xC of the cell-cell k-NN graph from X, ANN(XT) produces gene E {0. GGG of the gene-gene k-NN graph from X. We let B,, and B.j denote the i-th row vector of B and the j-th column vector of B, respectively.
24 are proposed to impute missing features in graph-structured data. The core idea FP is to impute missing values by diffusing observed values while preserving these observed values. Assume that given graph (V,E) has feature matrix X E R N with missing values, where rows and columns correspond to nodes and F feature channels, respectively. We use A E N denote normalized adjacency matrix of the graph. To preserve known features during the diffusion process, mark the positions of the features to be
Feature Propagation. FP-based algorithms 23

---

preserved with in the mask matrix M E 10,1) here. values of in M indicate the location of observed features. We express FP as function by =P(X, A, M) where X E F. x is an oulput matrix. A detailed explanation of FP provided in Appendix A In summary, FP fills in missing values in X through diffusion using A while preserving features corresponding to values of 1 M. It noteworthy that FP(X, A, M) performs propagation among the rows of X. In scRNA-seq data imputation, FP-based imputation methods treat zero values as missing values to be imputed via features diffused from non-zero values.
4 Proposed Method
4.1 Overview of scCR
In this paper, we design novel imputation framework for scRNA-seq data, namely scCR, which utilizes complete gene-gene relationships. Unlike existing work, scCR exploits both associating and dissociating relationships, which contain valuable biological information. Given highly noisy scRNA-seq data, especially having high number of false zeros, the goal of scCR is recover scRNA-seq data by imputing zero values, As shown in Figure our proposed framework consists of three stages: pre-imputation, complete relation, and denoising. Throughout these three stages, we enhance gene expression matrix by gradually integrating complete gene-gens and cell-cell relationships.
4.2 Pre-Imputation Stage
We consider cell-gene matrix X E RCG where C' and G represent the number of cells and genes, respectively. We cell E 10, denote an adjacency matrix of a cell-cell graph. Similarly, we let gene E {0, 1)GxG denote adjacency matrix of a gene-gene graph. Building k-NN graph directly on X can lead to performance degradation in downstream tasks due to the noisy nature of X. Therefore, scCR begins with the pre-imputation stage, which creates pre-imputed matrix to be used for k-NN graph construction in the complete relationship stage. In this stage, scCR imputes zero values through intercellular (i.e, cell-cell) propagation.
Cell-cell FP. We first construct a cell-cell k--N graph by c = ANN(X). seCR then employs FP to impute be a mask matrix with M = iff x;j # and M = O otherwise, which indicates the positions
values by the diffusion of nonzero values among cells. We let MX (0, 1
of the nonzero features in X to be preserved during the diffusion. Cell-cell FP using A cel((1 is performed as follows,
X (1)
FP A cel((1) .M²)
(1)
where X (1) E RRCG is an output of the pre-imputation stage, which is utilized the following complete relationship stage.
4.3 Complete Relationship Stage
In the complete relationship stage, we refine X through gene-gene and cell-cell propagation. ScBFP (12) adopts gene-gene FP on the k-NN graph constructed based on cosine similarity. However, it over- looks key issues: (1) The similarity- gene-gene k-NN graph can connect only associating (or co-occurring) genes, excluding highly correlated dissociating (or avoiding) genes, which can offer important biological information for imputation. This occurs because associating genes may have high cosine similarity due to their co-occurrence. These genes with high cosine similarity may become connected in the cosine- similarity-basee k-NN graph (2) As shown in Figure 3 since each gene has the distinct distribution within gene expression matrix [15]. the value distribution for a gene varies significantly among genes. Al- though imputation methods for ScRNA-seq generally normalize a gene expression matrix in a cell-wise manner, varying scales across genes still remain after the cell-wise normalization. Therefore, propagation across genes may degrade accurate recovery by mixing values with different scales.
Genes
Calls
3500
3000
1000
500
INS SST PPY PXN
Figure 3: A subset of the gene expression matrix in the Baron Human dataset.

---

High cosine similarity
Strongly dissociating genes
connected in k-NN gruph
j-th
(G+j)-th
0.5
1.6
1.4
8.3
0.0
0.3
0.3
0.2
0.3
0.6
0.2
Concatenation
0.1
1.8
0.1
7.3
9.7
&
-13
-12
0.8
1.3
0.1
-1.3
0.8
Cells
Column-wise Standardization
0.8
1.7
...
0.4
6.8
8.4
1.0
0.1
-1.1
0.2
-1.0
0.1
..
-1.1
0.2
0.2
2.5
4.5
0.7
4.0
-1.0
1.7
0.8
1.9
1.0
-.7
0.8
1.9
0.9
1.1
5.6
0.3
9.5
1.3 -1.4
1.3
0.7
-1.3
1.4
1.0
-0.7
Mean: 0.5
1.7
3.3
Mean:
0.0
0.0
0.0
Std:
0.4
0.5
2.5
3,5
2.3
Std: 1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
X
R DxG
X E RCGG
Figure 4: An illustration of the concatenation and standardization processes in the complete relation- ship stage. Std denotes standard deviation.
Concatenation. To address these key issues, we propose novel propagation scheme called gene-geng standardized FP. The cene-gene standardized FP first produces X Xcom RCx2G by concatenating x and its negative matrix along columns, i.e., X [X
Standardization. Subsequently, enable every gene to have the same scale during propagation among genes, we standardize Xcom in a column-wise manner. For b , ,G}, we standardize ccom to X com pCx2G follows,
(X
(4) where 1bb
X
com a,b
com a.b
comn a
12)
(2)
a=1
a=1
Here, (b and Tr denote the mean and standard deviation of the b-th column (i.e., gene) of com Since all the columns Xoom are standardized, SFP can effectively perform propagation based imputation without the mixing of values various scales, addressing the aforementioned issue (2).
Furthermore, by concatenating x(" with its negative matrix before the construction of X SFP can connect not only associating but also dissociating gene-gene relationships. As demonstrated in Figure assume that the i-th gene and the j-th gene have strong dissociating relationships, where
i,j E ( G}. Within any a-th cell (a E {I,...,O), X a, will be very high when x())
2. is very low and vice versa. After the standardization, the cosine similarity between the i-th gene and the j-th will have large negative value, which cannot be connected in a k-NN graph. However, through
the concatenation, (G++j corresponds to - Thus, the cosine similarity between X and xcom (((+)) has a large positive value, which will be connected a k-NN graph. Therefore, through
gene-gene propagation using this k-NN graph constructed by using com we can effectively exploit complete gene-gene relationships, including associating and dissociating relationships.
Gene-gene FP. We build gene-gene k-NN graph (Xcom)T T by A gene A.NNNN (XXN(()) where
A gene 2GGx2G We then perform the gene-gen gene standardized FP using A gene follows:
X
com
( A [MX Ix
where X X E
Since each gene in com does not have its original scale due to the standardization, we return all the columns in ccom to their original scale follows:
R Cx26
com a.b
c 0 0.b
+ Lbb
where com CC20 is the rescaled matrix. We then reduce ccm by retaining the first columns, and we denote this reduced matrix as X" RxxG X' is final output of the gene-gent gene standardized FPP.
Cell-cell FP. X containing information from complete gene-gene relationships plays a erucial role in seCR by contributing the formation of all subsequent cell-gene matrices. To perform additional
5

---

Table 1: Performance cell clustering, measured by ARI, NMI, and CA. Standard deviation errors are given. Figures highlighted in green indicate performance improvements over the most competitive baseline at each setting.
Danavl
Buron Mouse
Panercas
Mouse Blacker
Method
ARI
NMI
CA
ARI
NMI
CA
ARI
NMI
CA
0668
0.678:u0
ICA
0.710
0.002_0.00
0. 0.506:10.007
0.78819001
0.727 von
0.44720
0.71020000
0. 0.562230.00
AuroClass
0.40810000
0.600
0.525_...01
0.5644.0.m3
0.73G10.00e
0.72412.000
0.5061
0.732 1000
0.61310.030
scGNN 2.0
0.734a9.co9
0.575...00
0.5022n.054
0.753
0.728
0.488
0.717 10:1
0.500
scGCL
8.478a9.0c1
0.72Msa.com
0.645=0.00
0.045
0.755so.042
0.747a3.c0
0.529
0.725
0.598
MAGIC
0.712ea.co7
0.557=6.015
0.595=10007
0.803
0.765ea.022
0.5
xFFP
0:817
0.703
0. 802=
8.872
0.878
0.635
0. 730
scRFP
0.66010000
0.813
0.763-20000
0 888440000 080
1.900 40.
0.918_00
0.604 000
0. 7.761 20000
0.779 2770.
scCR (Ouns)
0.827 50.130
(125.3 3%)
0.847
(13.7%)
(1
0.81230000
0.85110000
0.704
1.7%%
0. 0.77810
(11.4%)
0. 0.701100000
Dataver
Zeisel
Worm Noaron
Baron Human
Methol
NMI
ARI
NMI
ARI
CA
TcTAG
0.7223m0
017
0.71220.00
0. 4.532 134
8.64
0.61220 ore
0. 0.610go.11 8.718
IXCA
0.603300 oes
0.730g3:006
0.764_20001
0.502
0.60020.0 6
0.700g na
0.546 on
0.76322000
0. 0.55810.00
AusoClass
0.67310 oce
0.714
0.746_..00
0.488
0.6380.3.001 001
0.528
0.743..om
0.503,0.023
scGNN 2.0
0.50330.050
0.657
0.866.0.041
0.453.n.00:
0.63Vaa..a
0:633a3.051
0.525....m
0.744:0027
0.549
scGCL
0.066300.ac3
0.715ea.:36
0.717=0.0m
8.676sn.cc
0.754x..002
0.593=o
0.7dd=oame
s.671
MAGIC
0.747ex.oz
0.705-0.0z2
0.512=mume
0.719
0.770e
0.502=z00z
0.788-20
0.396
scP
0 0.812 01848200000
0.5 0.524ausse
7.731 as
0. 0.7662000
0.670
0 1.826
0. 0.722000
scRFP
0.83550 one
0. 2.792200000
0 86900-0000 0o0
0 608 oso
0.71650000
0. 0.79220000
0.677.0000
0.827
0. 7.7335000
scCR (Ouns)
(+6.43))
0.952a0000 0.803=2.000
(+0.3%)
(+7.5%)
0.320
(-21.6%)
(+3.8%)
(+12 85%)
cell-cell FP using complete gene-gene relationships inherent in X construct cell-cell k-NN
graph by A ccl((2) XN". We perform cell-cell FP using X and A cell(2) as follows,
FP(X, A cell(2) .M
(5)
where (22) is an output of this cell-cell FP.
Weighted sum. X which is a final output of complete relationship stage is produced by the
weighted sum of x and x (1) as follows:
ox + (1-
(6)
where 0 < < 1 is hyperparameter. X
incorporate valuable biological information since
complete gene-gene relationships are delivered by x(2)
4.4 Denoising Stage
Cell-cell Soft FP. While the pre-imputation and complete relationship stages focus on imputing zero values, the denoising stage aims to remove noise in the overall values of X via propagation based
smoothing. To exploit complete gene-gene relationships, the denoising stage utilizes X (3) containing
them. We first build a cell-cell i--N graph by A (e)((3) ANN(X(()) (3)) To denoise X, we adopt
Soft FP [II] that does not maintain zero values during propagation. We apply Soft FP [1] to X as follows,
(t)
(t) = 3A
1)+ (1- 1= K,
where K is the total number of propagation steps, X ()) x,) (1) gCxa is the updated cell-gene matrix after propagation steps, and < 3 < 1 is hyperparameter. An output of the denoising stage, denoted by X (4) (K), is obtained after K steps.
Weighted sum. The final output of our seCR, X, is the weighted sum of X and X (K) as follows:
X
(1 7) (K).
(8)
where and 0 < 1 is hyperparameter. In summary, unlike existing propagation- bassd methods, our scCR enables the use of complete gene-gene relationships in denoising ScRNA-seq.

---

Baron Mouse
Pancreas
Mouse Bladder
1
0.8
0.8
0.6
0.6
RMSE
0.2 (-13.0%)
0.4
(-13.1%)
(-12.6%)
0.3
0.5
20%
(.44%
40%
80%
0.2
0.4
20%
40%
(1.7%)
(-11.2%)
80%
8
Zeisel
Worm Neuron
Baron
1.2
0.75
0.8
0.9
0.6
0.6
0.6
0.45
(-6.7%)
0.4
0.3
(9.4%)
(-9-7%)
(-10.8%)
0.3
(13.1%)
(-12-2%6
0.2
(-7.2%
(-6.8%)
(-1199%
20%
Dropout 80%
20%
40%
80%
20%
80%
Dropout rate
Dropout rate
DCA
AutoClass
ScGNN 2.0
scGCL
MAGIC
ScFP
scBFP
scCR
Figure 5: Performance dropout recovery, measured by RMSE. Figures highlighted in green indicate reduction rates from the most competitive baseline at each setting.
5 Experiments
5.1 Experimental Setup
We performed comparative evaluation of scCR on six widely used scRNA-seq datasets with gold- standard cell type information: Baron Mouse [25] Pancreas [26). Mouse Bladder (27), Zeisel (2),
Worm Neuron [28], and Baron Human (25). We compared our seCR with eight state-of-the-art meth-
ods handling noise in seRNA-seq data: (1) non-graph-based methods: DCA 17] and AutoClass (18);
(2) GNN-based methods: scTAG [21], scGNN 2.0 [19]. and scGCL 20 (3) propagation-base
methods: MAGIC (22], scFP [1I. and scBFP 12), We evaluated scTAG only cell clustering, since scTAG is clustering method. To evaluate the cell clustering of scCR and baselines, we utilized three standard evaluation metrics: Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), and Clustering Accuracy (CA). We used KMeans clustering to compare the clustering performance of various imputation methods, including scCR. For dropout recovery, employed two standard evaluation metrics: Root Mean Square Error (RMSE) and Median LI Distance.
Implementation. For fair comparisons, we set the hyperparameters of baselines according specifi- cations in the papers and official codes. We reported the average performance across three independent runs. Experimental details regarding datasets, baselines, evaluation metrics, and hyperparameter settings are provided in Appendix G
5.2 Results
scCR enables improved cell clustering. To validate the effectiveness of scCR in cell clustering, we evaluated its clustering performance. Table presents performance comparison. While FP-based baselines, including scFP and scBFP, outperformed other baselines, scCR delivered the best or competitive cell clustcring performance across all datascts. Specifically, scCR improved ARI by 25.3%. 1.7%. 6.4%, and 21.6% compared to previous state-of-the-ar results Baron Mouse, Mouse Bladder, Zeisel, and Baron Human, respectively.
seCR effectively recovers dropout values. Since dropouts can occur at various rates, we generated false zeros (i.e., dropouts) at non-zero values in datasets by applying varying dropout rates. As shown in Figure [ seCR significantly improved dropout recovery performance in various dropout rates across the datasets. We confirmed that scCR effectively reduced RMSE between imputed values and their original values with large reduction rates, only except for the Pancreas dataset with 40% dropout. We provided recovery performance comparison, measured by the median I.1 distance in Appendix H.2 which also demonstrates the effectiveness of scCR.
7

---

Raw
DCA
SCFP
ScBF
scCRR (ours)
Cell Type
LPORT
Epaiton
Gamma
UMA
LMAP1
Mast
Macrphage
Quasssonnt abelltte
Schwern
Dropout
Figure 6: UMAP visualization using the Baron Human dataset, comparing scCR with the three most competitive imputation methods. The first row shows the visualization of the raw data and their imputed results. The second row displays the visualization of data subjected to an 80% dropout rate and their imputed results.
Real
0.5
0
Baron Mouse
Pancreas
Mouse Bladder
Zeisel
Worm Neuron
Baron Human
K-NN graph in seBFP
0.5
Baron Mouse
Pancreas
Mouse Bladder
Zeisel
Worm Neuron Baron Human
k-NN graph in scCR
0.5
Baron Mouse
Pancreas
Mouse Bladder
Zeisel
Worm Neuron
Baron Human
Associating
Diisociiatnng
Figure 7: The first row indicates the percentages of associating and dissociating gene-gene relation- ships in datasets. The second and third rows represents the percentages of associating and dissociating relationships within gene-gene k-NN graph in each method.
scCR identifies rare cell types well. verify the effectiveness of seCR in identifying rare cell types, we conducted in-depth analysis using the Baron Human dataset. We visualized the two-dimensional UMAP (29] repesentations of the raw data and the data with an 80% dropout rate applied. As shown in the first row in Figure scCR effectively identified rare cell types with few cells, such 'gamma' and 'Macrophaee,. It is noteworthy that even under severe dropouts, scCR separated cell types well (in the second row), whereas compared methods failed.
Does seCR really model dissociating relationships? show that scCR models both associating and dissociating gene-gene relationships, we first investigated the ratio of dissociating relationships to associating relationships. For this investigation, we define that associating or dissociating relationships exist when the absolute values of the correlation coefficients between genes exceed the top 25%. We determine that positive sign in the correlation coefficients indicates associating relationships, while negative sign indicates dissociating relationships. We then measured the percentages of

---

100
Running Time (8)
80
60
40
20
2000
4000
6000
8000
# Cells
DCA
AutoClass
scGNN 2.0
SeGCL
MAGIC
scFP
scBFP
scCR
Figure
Running time comparison scCR and baselines according to the number of cells.
associating and dissociating relationships within gene-gene k-NN graphs in scBFP and our scCR. As shown in Figure 7 scBFP hardly models dissociating gene-gene relationships. contrast, scCR effectively models dissociating relationships, enabling the of complete gene-gene relationships in its imputation.
seCR is even faster than existing imputation methods. To show the advantage of scCR in terms of imputation time, we measured the running time of seCR and imputation methods on datasets. As shown in Figure 8 scCR showed the lowest running time across all the datasets, regardless of the number cells.
An ablation study (See Appendix C), further experimental results (See Appendix and the proof of convergence of FP (See Appendix are provided in Appendix.
6 Conclusion
In this paper, we proposed a novel imputation framework called Single-Cell Complete Relationship (scCR) for scRNA-seq data imputation. scCR utilized complete gene-gene relationships by con- catenating a given cell-gene matrix with its negation and facilitated effective gene-gene propagation through the standardization of the cell-gene matrix in gene-wise manner. These processes, grounded in genetic evidence, led to significant performance improvements over titte-offthe-att methods in various downstream tasks on scRNA-seg data, with fast imputation times. Furthermore, our work is not limited to simply utilizing genetic evidence to design a framework. We validated this evidence within real scRNA-seq datasets, and confirmed that our seCR effectively leveraged this insight. Like other scRNA-seq imputation methods, scCR is specifically designed for scRNA-seq data. However, since scRNA-seq data are inherently matrix-formatier scCR can extended to general tabular data imputation. We expect that the concatenation process will be effective even for general tabular data, as there are often both positive and negative correlation coefficients between channels in such data. The extension of seCR to other domains is left for future work.
Broader Impacts
Our work provides an important insight that, when applying machine learning the biomedical domain, it is crucial to approach with biological grounding rather than focusing solely on applying existing cutting-edge machine learning techniques. Since scRNA-seq has opened new frontier for understanding biological systems [5 30 31), we believe that our work will contribute to the
biomedical domain by enhancing the analysis of human diseases and the discovery of new genetic observations. We have not identified any negative impacts of our work society.

---

Acknowledgements
This work was supported by Institute of Information & communications Technology Planning Evaluation (IITP) grant funded by the Korea Graduate School Program(Chung-A University)).
Intelligence
References
[1] Evan Z Macosko, Anindita Basu, Rahul Satjja, James Nemesh, Karthik Shekhar, Melissa Goldman, Itay Tirosh, Allison R Bialas, Nolan Kamitaki, Emily M Martersteck, et al. Highly parallel genome-wide expression profiling of individual cells using nanoliter droplets. Cell, 161 (5):1202-1214, 2015.
[2] Amit Zeisel, Ana B Muñoz-Manchadoo Simone Codeluppi. Peter Lönnerberg, Gioele La Manno, Anna Juréus, Sueli Marques, Hermany Munguba, Liqun He, Christer Betsholtz, et al. Cell types in the mouse cortex and hippocampus revealed by single-cell ma-seq. Science, 347(6226); 1138-11 1142, 2015.
[3] Michael JT Stubbington, Orit Rozenblatt-Rosee Aviv Regev, and Sarah Teichmann. Single- cell transcriptomics to explore the immune system in health and disease. Science, 358(6359): 58-63, 2017.
[4] Hadas Keren-Shaul, Amit Spinrad, Assaf Weiner, Orit Matcovitch-Natan, Raz Dvir- Sitr-zteenfeld, Tyler Ulland, Eyal David, Kuti Baruch, David Lara-Astaiso, Beata Toth, et al. unique microglia type associated with restricting development of alzheimer's disease. Cell, 169(7):
1290, 2017.
[5] Cole Trapnell, Davide Cacchiarelli, Jonna Grimsby, Prapti Pokharel, Shuqiang Li, Michael Morse, Niall Lennon, Kenneth J Livak, Tarjei S Mikkelsen, and John L. Rinn. Pseudo-temporal ordering of individual cells reveals dynamics and regulators of cell fate decisions. Nature biotechnology, 32(4):381, 2014. 2014.
[6] Monika M Gladka, Bas Molenaar, Hesther De Ruiter, Stefan Van Der Elst, Hoyee Tsui, Danielle Versteeg, Grègory PA Lacraz, Manon MH Huibers, Alexander Van Oudenaarden, and Eva Van Rooij. Single-cell sequencing of the healthy and diseased heart reveals cytoskeleton- associated protein 4 as new modulator of fibroblasts activation. Circulation, 138(2):166-18) 2018.
[7] William Stephenson, Laura Donlin, Andrew Butler, Cristina Rozo, Bernadette Bracken, Ali Rashidfarrokhi, Susan M Goodman, Lionel B Ivashkív, Vivian P Bykerk, Dana E Orange, et al. Single-cell ma-see rheumatoid arthritis synovial tissue using low-cost microfluidic instrumentation. Nature communicationss 9(1):791, 2018. 2018.
[8] Stephanie C Hicks, F William Townes, Mingxiang Teng, and Rafael A Irizarry. Missing data and technical variability in single-cell rna-sequencing experiments. Biostatistics, 19aitii,,,19444)))) 19(4):562-578 2018.
[9] Florian Buettner, Kedar N Natarajan, F Paolo Casale, Valentina Proserpio, Antonio Scialdone, Fabian J Theis, Sarah A Teichmann, John C Marioni, and Oliver Stegle. Computational analysis of cell-to-cell heterogeneity single-cell ma-sequencing data reveals hidden subpopulations of cells. Nature biotechnology. 33(2): 2015.
[10] Uri Shaham, Kelly P Stanton, Jun Zhao, Huamin Li, Khadir Raddassi, Ruth Montgomery, and Yuval Kluger. Removal of batch effects using distribution-matchingg residual networks. Bioinformatics, 33(16)2553922 2546, 2017.
[11] Sukwon Yun, Junseok Lee, and Chanyoung Park. Single-cell ma-seq data imputation using feature propagation. arXiv preprint arXiv:2307.10037 2023.
[12] Junseok Lee, Sukwon Yun, Yeongmin Kim, Tianlong Chen, Manolis Kellis, and Chanyoung Park. Single-cell ra sequencing data imputation using bi-level feature propagation. Briefings in Bioinformatics, bbb)) 2024.
10

---

[13] Fiona Jane Whelan, Martin Rusilowicz, and James Oscar McInerney. Coinfinder: detecting significant associations and dissociations in pangenomes. Microbial genomics, 6(3)x3003 2020.
[14] Rebecca J Hall, Fiona Whelan, Elizabeth A Cummins, Christopher Connor, Alan McNally, and James O McInerney. Gene-gene relationships an escherichia coli accessory genome are linked to function and mobility. Microbial Genomics, 7(9):000650, 2021.
[15] Anoop Patel, Itay Tirosh, John Trombetta, Alex K Shalek, Shawn M Gillespie, Hiroaki Wakimoto, Daniel P Cahill, Brian V Nahed, William T Curry. Robert L Martuza, et al. Single- cell ma-seq highlights intratumoral heterogeneity in primary glioblastoma. Science, 344(6190): 1396-1401 2014.
[16] Wei Vivian Li and Jingyi Jessica Li. An accurate and robust imputation method scimpute for single-cell ma-seq data. Nature communicationss 9():9997, 2018
[17] Gökcen Eraslan, Lukas M Simon, Maria Mircea, Nikola S Mueller, and Fabian J Theis. Single- cell ma-seq denoising using deep count autoencoder. Nature communications, 10(1):390, 2019.
[18] Hui Li, Cory R Brouwer, and Weijun Luo. A universal deep neural network for in-depth cleaning single-cell ma-seq data. Nature Communications, 13(1):1901 2022.
[19] Juexin Wang, Anjun Ma, Yuzhou Chang, Jianting Gong, Yuexu Jiang, Ren Qi, Cankun Wang, Hongjun Fu, Qin Ma, and Dong Xu. segnn is novel graph neural network framework for single-cell ma-seq analyses. Nature communications, 12(1))1882, 2021.
[20] Zehao Xiong, Jiawei Luo, Wanwan Shi, Ying Liu, Zhongyuan Xu, and Bo Wang. segel: an imputation method for scrna-seq data based on graph contrastive learning. Bioinformatics, 39 (3):btad098, 2023.
[21] Zhuohan Yu, Yifu Lu, Yunhe Wang, Fan Tang, Ka-Chun Wong, and Xiangtao Li. Zinb-based graph embedding autoencoder for single-cell ma-seq interpretations. In Proceedings of the AAAI conference artificial intelligence, volume 36, pages 4671 1-7699, 2022.
[22] David Van Dijk, Roshan Sharma, Juozas Nainys, Kristina Yim, Pooja Kathail, Ambrose J Carr, Cassandra Burdziak, Kevin R Moon, Christine L Chaffer, Diwakar Pattabiraman, et al. Recovering gene interactions from single-cell data using data diffusion. Cell, 174(3):716-229, 2018.
[23] Emanuele Rossi, Henry Kenlay, Maria Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. On the unreasonable effectiveness of feature propagation in learning graphs with missing node features. In Learning Graphs Conference, pages 11-1. PMLR. 2022.
[24] Daeho Um, Jiwoong Park, Seulki Park, and Jin young Choi. Confidence-based feature imputation for graphs with partially known features. In The Eleventh International Con- ference on Learning Representations, 2023. URL https://openrevieee net/ net/forumiidt YPKBIILy-Kt
[25] Maayan Baron, Adrian Veres, Samuel Wolock, Aubrey Faust, Renaud Gaujoux, Amedeo Vetere, Jennifer Hyoje Ryu, Bridget K Wagner, Shai S Shen-Orr, Allon M Klein, et al. A single-cell transcriptomic map of the human and mouse pancreas reveals inter-and intra-cell population structure. Cell systems, (44):3463600 2016.
[26] Malte D Luecken, Maren Büttner, Kridsadakom Chaichoompu, Anna Danese, Marta Interlandi, Michaela F Müller, Daniel C Strobl, Luke Zappia, Martin Dugas, Maria Colomé et al. Benchmarking atlas-level data integration in single-cell genomics. Nature methods, 19(1): 41-50, 2022.
[27] Xiaoping Han, Renying Wang. Yincong Zhou, Lijiang Fei, Huiyu Sun, Shujing Lai, Assieh Saadatpour, Ziming Zhou, Haide Chen, Fang Ye, al. Mapping the mouse cell atlas by microwell-seq. Cell, 1091-110911 2018.

---

[28] Junyue Cao, Jonathan S Packer. Vijay Ramani, Darren A Cusanovich, Chau Huynh, Riza Daza, Xiaojie Qiu, Choli Lee, Scott N Furlan, Frank J Steemers, al. Comprehensive single-cell transcriptional profiling of a multicellular organism. Science, 357 2017.
[29] Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger. Umap: Uniform manifold approximation and projection. Journal of Open Source Software, 3(29), 2018.
[30] Diego Adhemar Jaitin, Ephraim Kenigsberg, Hadas Keren-Shaul, Naama Elefant, Franziska Paul, Irina Zaretsky, Alexander Mildner, Nadav Cohen, Steffen Jung, Amos Tanay, al. Massively parallel single-cell ma-seq for marker-free decomposition of tissues into cell types. Science, 343(6172:776-779, 2014.
[31] Nicholas Schaum, Jim Karkanias, Norma F Neff, Andrew P May, Stephen R Quake, Tony Wyss-Coray, Spyros Darmanis, Joshua Batson, Olga Botvinnik, Michelle B Chen, et al. Single- cell transcriptomics of 20 mouse organs creates a tabula muris: The tabula muris consortium. Nature, 56277727)366, 2018.
[32] Abraham Berman and Robert J Plemmons. Nonnegative matrices in the mathematical sciences. SIAM, 1994.
[33]
Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[34] Yunqing Liu, Jiayi Zhao, Taylor S Adams, Ningya Wang, Jonas C Schupp. Weimiao Wu, John E McDonough, Geoffrey L Chupp, Naftali Kaminski, Zuoheng Wang, et al. idese: identifying differential expression single-cell ma sequencing data with multiple subjects. BMC bioinformatics, 24(1):318, 2023.
[35] Alexander Wolf, Philipp Angerer, and Fabian Theis. Scanpy: large-scale single-cell gene expression data analysis. Genome biology, 19:1-5, 2018.
12

---

A Feature Propagation
Assume that a given graph g = &V,&) has feature matrix X E NXF with missing values, where rows and columns correspond to nodes and F feature channels, respectively. We use A E TR-NXN to denote normalized adjacency, which is input for feature propagation (FP). To preserve known features during the diffusion process, we mark the positions of the features to be preserved with in the mask matrix M {0, 1 NNF Here, values of in M indicate the location of observed features, where feature values will be preserved.
To formally explain the diffusion process of FP in detail, we temporarily reorder nodes for notational convenience. Since observed values may differ across channels, we reorder the nodes for each channel. When consider the a-th channel, based the values of 1 in M. we let 1% be the set of nodes whose a-th values are known (observed). Similarly, by examining zero values in M. Va denotes the set of nodes whose a-th values are unknown (missing). By reordering the nodes in the order of V and u. the entire feature values and the adjacency matrix for the a-th channel can be expressed as
X
(a)
Rk
(9)
(
uk
where x" a column vector representing features for the a-th channel in in the order of Vg and Vu Here, xg E RI and x E R Similarly, A (a) consists of four sub- matrices related Vi and Va is noteworthy that although A E RR- and A E RNNN is different due reordering. they represent the same graph structure.
To preserve observed values during the diffusion process, we replace the first [V]] rows in A (a) one-hot vectors indicating V/. Consequently, we obtain transition matrix A (a) E N expressed by
with
L&
Oeu (a)
A
(10)
where In E R V Mell is an identity matrix and Onz E [RIVIII" is zero matrix. The diffusion process of FP is implemented by iterative propagation steps utilizing A (a) as
x (t) = (o) x 1), 1.... K; x (0) =
(11)
where (t) is an imputed feature vector after propagation steps and 0,, denotes a zero vector of the
same length as [. As K > xo, this recursion converges and x* (() reaches a steady state (the proof
can be found in Appendix Bb. We use x*KK with large enough K to approximate the steady state.
After this diffusion process for the entire channels, we attain (K)) ) Since these vectors have different ordering due channel-wise reordering, we rearrange (K)) in the original order and construct X IR N F by stacking the originally ordered vectors in (X*(K) along the channels. In summary, FP fills in missing values in X through diffusion using A while preserving features corresponding to values of 1 in M.
B Proof of Convergence of Feature Propagation
Feature propagation (FP) 23 utilize symmetrically normalized transition matrix for the diffusion process implemented by iterative propagation steps. We prove the convergence of this diffusion process as follows.
Proposition The transition matrix for the a-th channel is defined by
LEA (0)
O
A (a)
(a)
uk
uu
13

---

where (1) is symmetrically normalized. Using A the diffusion process in the a-th channel is defined by
(1) = (o) x 1), t= 1
x
x (0) =
0
Then, lim (K) converges. K-00
The proof of Proposition refers to 23 We begin with two lemmas.
Lemma 1. A (a)
is the symmetrically normalized matrix calculated by A (o) [D (a) 111/2 where D(a) is diagonal matrix that has diagonal entities
(D(a))- 1/2
(oa))-1/2A
D (a)
A. A (a) is the (x [()] (x( bottom-right submatrix of A (0) and let p(-)
denote spectral radius. Then, p(A (m) 1.
Proof. Consider A A und E N.N where the bottom right submatrix is equal to A elements are zero. That is,
Aa)) uu and all other
(a)
Jex
un0
=
Ouk
A
where O&k (0)12) OKu (0)14/")x18 and Ouk (0) (x( Given that A (a)
represents the weighted adjacency matrix of the connected graph G, A A S
A (a) element-wise
and A ( * A (a) Furthermore, considering that A ( + A (a) constitutes the weighted adjacency
matrix of a strongly connected graph, we can conclude that A (())
(a)
+ AAA
is irreducible based (a)
on Theorem 2.2.7 in 32) Consequently, applying Corollary 2.1.5 in 32 p( (A uno) < p(A (")) Furthermore, p(A (a)
A (a) 1/2 where (a) (D(a))-1/AA() -1/2 has eigenvalues in the range [0, 2) 333 Note that since both A uwo and A (a)
< 1 since we can write A = I
(D (a)
1/2
share the same non-zero eigenvalues, follows that pl A (c)
wun) ( Ultimately, combining
these inequalities leads to the result p ( (0) p (1)))) p(A (n))
Lemma 2. Iga A (a) is invertible where Luu is the (x
[x (a) identity matrix.
Proof. Since is not an eigenvalue of A (a) by Lemma not an eigenvlaue I A (a) Thus I Iux A (a)
is invertible.
We now prove Propostion Tas follows.
Proof. The recursive relation can be written as
x x(() (t) = (1)
k
TEA
Ogw
1) =
x
(
(1 - ]
ab) (t
A ( A
(e)
(a)
X
uk
uu
Xu
Since xx
(0) (t) = x (t 1) in the first
x Therefore, lim x(2) (K) converges to x
(a) (a) rows, follows that xx
(K)
= =... = x
(a)
That is,
x()) (K) retains the values of x (a)
(0)
K-000
14

---

Table 2: Ablation study. Con and Sta denote the concatenation and standardization, respectively,
which enable capturing dissociating gene-gene relationships.
Mouse
Zeinel
Humsan
x
0.625
0.
0.719ex.cus
0.789
0.738anm
0.851
0.805 200
0.037 e0.00s
0.81 Ses,coo
0.625
0.785
0.710=n.c0
8.898es.00
0.850
0.9
0.816+9.00
0. 0.846600002
0.8 9esu.om
0.6220:0000
0.831
0.7
0.827
0.847
0.846=2.04
0.902:0.000
0.803:00ce
s..c2
0.823
0.8 0.858
0.827e0.000
Table Further ablation study of scCR on cell clustering measured by ARI PRE. COM, and DEN denote the pre-imputation stage, the complete relation stage, and the denosing stage, respectively.
PRE
COM
DEN
Baron Mouse
Zeisel
Baron Human
0.437 + 0.061
0.682 +: 0.024
0.580 0.036
0.409 + 0.008
0.732 + 0.001
0.571 + 0.007
x
0.584 + 0.000
0.822 + 0.000
0.681 + 0.000
0.827 0.093
0.902
0.000
0.823 0.000
We now focus solely on the convergence of lim Xx (K). When unroll the recursion for the last rows,
(x
(a)
x
(K)
A
(a) (a)
+ A xK 1)
uk &
uk & ua
(a) (a)
uk X/
(a) (a)
+ A
(a) un
x(a) (K 2)) x
K-1
(a)
(A xx(0) (0)
X
By Lemma
lim
K = 0. Therefore,
lim K -00
(0) = 0, regardless of the initial
K-000
state for x (0). (we replace (a) (0) with zero column vector for simplicity.) Hence, our focus
shifts to lim (-K-1 uu uk
(a)) (a)
K Koo
Given that Lemma establishes p(A (a) (() < 1, and Lemma affirms the invertibility of (Iuu
[4)) un
-1, the geometric series converges as follows
lim (K) lim -00
(A ) (a) (a) (In. ) (a) (a) X
K-000
In conclusion, the recursion in FP converges.
C Ablation Study
We conducted an ablation study to analyze the effectiveness of each component in scCR. We performed cell clustering the Baron Mouse, Zeisel, and Baron Human datasets. As shown in Table both concatenation and standardization contributed to performance improvement, and the combination of the two components led significant performance improvement.
We conducted an additional ablation study to assess the effectiveness of each stage of scCR. Table presents the results of the ablation study in terms of cell clustering, measured by ARI. As shown in the table, adding the complete relation stage and the denoising stage significantly improved performance compared to using only the pre-imputation stage. These results confirm that the complete relation and denoising stages contributed substantially to the high performance of scCR, underscoring the well-foundes design of our approach.
15

---

Table 4: Performance on dropout recovery under Missing Not At Random (MNAR) settings, measured by RMSE.
Dataset
scFP
scBFP
scCR (ours)
Baron Mouse
0,517 = 0.000
0.465 = 0.000
0.304 = 0.000
Pancreas
0.537 + 0.001
0.506
0.001
0.352 0.000
Mouse Bladder
0.374 + 0.000
0.374 + 0.001
0.170
0.000
Zeisel
0,580 = 0.001
0.538 = 0.000
0.489 = 0.000
Worm Neuron
0.330 + 0.000
0.190 0.000
0.049 0.000
Baron Human
0.493 = 0.000
0.475 = 0.000
0.328 = 0.000
D Missing Not at Random Settings
Existing studies 11 simulate dropout by randomly sampling non-zero values in cell-gene matrix from uniform distribution and setting them zero (i.e., missing completely random (MCAR)). However, in real scRNA-seq data, dropouts occur more frequently in genes with low expression levels rather than those with high variance (34] This is because the probability of capturing RNA transcripts of low-expression-lewe we selected the 1,000 genes with the lowest expression levels and simulated dropout only these genes. We randomly sampled non-zero values of these genes from a uniform distribution and replaced the sampled values with zero (i.e., missing not at random (MNAR)).
genes during sequencing is lower. Based on this dropout pattern,
Table|4pressen the performance comparison under the aforementioned MNAR settings in terms of data recovery, measured by RMSE. We compared scCR to the two most competitive baselines, scFP [1]] and scBFP [2]. The dropout rate was set to 20% of the total number of values in the cell-gene matrix. As shown in the table, seCR outperformed the compared methods by significant margins in the realistic dropout settings, demonstrating the robustness of scCR in realistic scenarios. Considering realistic dropout simulation can help pre-assess the generalizability of techniques in practical scRNA-seq applications.
E Memory Usage Analysis
Table 5: Comparison of input and memory complexity. E RGCC denote a cell-gene matrix, where C' and G represent the number of cells and genes, respectively. A E CCCC and Agene E G denote cell-cell and gene-gene adjacency matrices, respectively. 8 denotes trainable parameters. B represents the batch size for batch-wise K-NN graph construction.
Method
Input
Big-O
scTAG
X, A cell
O(GC) + 0(Era)) (())
DCA
X.
OGGC) (
AutoClass
X.
OGGC) + O(0)
scGNN 2.0
X, 0
O O(E.a)) 0
scGCL
X, A cell
OGGC) O(E.n)) 0(8)
MAGIC
X, cell
O(GC) - O(Eau)
scFP
X, A
O(BC) + O(E.a))
scBFP
X, A cell
A genu
O(BC) + (EEgeme) O(BG) ( O(BC) + (Eggnn) O(BG) O(Eca)
scCR (Ours)
X. A
A gemu
We analyzed the memory complexity of all methods used in this paper and conducted additional experiments to examine the memory usage of our scCR. Table 5 compares the input and memory complexity of scCR with other state-of-the-art methods. To alleviate the high memory demands during k-NN graph construction, we adopted the batch-wist wischh-wieee k-NN graph construction strategy from
12 When constructing k-NN graphs among genes, we divided the genes into batches of size B and computed k-nearest neighbors for each batch. We applied the same batch-wise strategy when constructing k-NN graphs among cells. This approach reduces memory requirements by avoiding the need to store distances between all points in the entire dataset simultaneously. Specifically, in the memory complexity of scCR, batch-wise k-NN graph construction changes Ó(G²) and ((C²) to OBB)) and O(BC), respectively. Consequently, patch-wise k-NN graph construction enables
16

---

Table 6: Memory usage of scCR for different datasets, measured by gigabytes (GB).
Baron Mouse
Pancreas
Mouse Bladder
Zeisel
Worm Neuron
Baron Human
Memory usage (GB)
1.811
1.837
1.957
2.037
1.927
3.861
processing of large datasets that would otherwise be infeasible due to memory constraints, Moreover, scCR does not require any trainable parameters, unlike other deep-learning-aase methods.
We further measured the memory usage scCR across various datasets, as shown in Table 6 The results in the table indicate that the advantages of scCR extend beyond its superior performance and time efficiency, showcasing its scalability as well.
Hyperparameter Sensitivity
Table 7: Performance of scCR on cell clustering measured by ARI for different values of a.
a
Baron Mouse
Zeisel
Baron Human
0.01
0.627 + 0.000
0.903 + 0.000
0.823 + 0.000
0.05 (used)
0.827 + 0.093
0.902 : 0.000
0.823 1 0.000
0.1
0.727 + 0.141
0.904 + 0.000
0.824 + 0.000
0.5
0.701 0.000
0.901 = 0.000
0.681 0.000
0.9
0.448 0.001
0.825 + 0.000
0.683 + 0.001
Table Performance scCR on cell clustering measured by ARI for different values B
8
Baron Mouse
Zeisel
Baron Human
0.1
0.440 + 0.046
0.659 + 0.058
0.553 + 0.040
0.5
0.476 + 0.049
0.724 + 0.000
0.560 + 0.001
0.9
0.509 + 0.004
0.740 + 0.000
0.657 + 0.000
0.95
0.498 + 0.002
0.910 - 0.000
0.666 1 0.011
0.99 (used)
0.827 + 0.093
0.902 + 0.000
0.823 + 0.000
0.999
0.925 + 0.000
0.900 = 0.000
0.819 + 0.000
Table 9: Performance of scCR on cell clustering measured by ARI for different values of 7.
Baron Mouse
Zeisel
Baron Human
0.001
0.927 0.001
0.902 + 0.000
0.824 0.000
0.01 (used)
0.827 0.093
0.902 + 0.000
0.823 + 0.000
0.635 0.000
0.903 1 0.000
0.822 + 0.000
0.1
0.595 + 0.000
0.903 - 0.000
0.667 + 0.001
0,5
0.469 0.003
0.740 = 0.000
0.627 + 0.011
0.9
0.409 + 0.009
0.749 + 0.000
0.586 + 0.006
Table 10: Performance of scCR on cell clustering measured by ARI for different values of k.
k
Baron Mouse
Zeisel
Baron Human
1
0.628 + 0.000
0.905
0.000
0.827 + 0.000
(used)
0.827 + 0.093
0.902 + 0.000
0.823 0.000
3
0.631 + 0.000
0.903 + 0.000
0.819 + 0.000
5
0.625 + 0.002
0.902
0.818 + 0.000
10
0.621 + 0.000
0.818 0.000
15
0.630 + 0.000
0.902 0.000
0.817 + 0.000
We conducted additional experiments to provide comprehensive analysis of the impact of different hyperparameters, including a, 33, 7, and k; on the performance of scCR. We report ARI in cell clustering on three datasets by varying B, 7 and & within the ranges of (0.01, 0.05, 0.1. 0.5,
17

---

that every cell had 0.9), 10.1, 0.5, 0.9, 0.95, 0.99, 0.999), {0.001, 0.01, 0.05, 0.1, 0.5, 0.9,, and [1, 2, 3, 5, 10, 15), respectively. When varying target parameter, other hyperparameters were fixed to their default settings. T T Table | and Table Tolitustratee how these hyperparameter choices impact scCR performance. As shown in the tables, the values of a, B3 7, and used in this study generally resulted in strong performance.
In terms of sensitivity, when the runner-up ARI scores 0.660 0.848 and 0.677 for Baron Mouse, Zeisel, Baron Human, respectively, scCR demonstrated robustness against hyper- parameter variations. Specifically, a (0.05, 0.1, 0.5). 8 E {0.99, 0. 0.999), and y E {0.001, 0.013 yielded state-of saae--ofthee of-the-art performance across the datasets. For k. scCR showed strong performance across all values, except in the case of Baron Human. Additionally, some parameter adjustments led to performance surpassing that of the default settings. However, given the unsupervised nature of single-cell analysis, we retain default hyperparameter settings that generally perform well.
G Experimental Details
G.1 Implementation Details
We conducted the experiments on single NVIDIA GeForee RTX 2080 GPU and an Intel Core 15-6600 CPU 3.30 Hz. The number of neighbors (k) in cell-cell and gene-gene k-NN graphs were set to 15 and 2, respectively. The total number of propagation steps K was set to 40 for both cell-cell and gene-gene FP. We set a, 3, and to 0.05, 0.99, and 0.01, respectively. We found that the choice between row-stochastic normalization and symmetric normalization applied to A cel((3) within Soft FP [T] affected performance, and we reported the best result. For dropout recovery, we excluded the denoising stage (i.e, 1).
G.2 Datasets
For our experiments, we utilized six real scRNA-seq datasets, including Baron Mouse 25 Pan-
creas [26). Mouse Bladder (27). Zeisel (2). Worm Neuron [28). and Baron Human [25). Table
summarizes the dataset statistics. We downloaded all the datasets from the GitHub repository"
for [1]. These publicly available datasets and the repository have no public declaration of license.
We leveraged commonly used pre-processing procedure for scRNA-seq data described in recent studies 11 [2]. We performed minimal quality control (QC) using SCANPY 35]. a toolkit for scRNA-seq analyses. Cells and genes exhibiting no gene expression (i.e., with all zero values) were removed from a given cell-gene matrix. We retained the 2,000 genes with the highest variance in each dataset. We then normalized each cell by total counts over all genes an equal total count of 1.0. That is, every row vector was divided by its library size, which the sum of its values. After scaling by the median library size, log(2: + 1) transformation applied to all values in the cell-gene matrix, resulting in a pre-processed cell-gene matrix.
Table 11: Dataset statistics.
Dataset
Protocol
#Cells
#Genes
#Cell Type
Baron Mouse
inDrop
1,886
14,861
13
Pancreas
inDrop
1,937
15,575
14
Mouse Bladder
Microwell-seq
2,746
19,771
16
Zeisel
STRT-seq UMI
3,005
19,972
7
Worm Neuron
sci-RNA-seq
4,186
13,488
10
Baron Human
inDrop
8,569
17,499
14
18

---

G.3 Baselines
For all the baselines, we used the code released by the author of the respective papers. Table 12 shows the URL links for the baselines. scTA and scGNN 2.0 are under the MIT license. The licenses of DCA, AutoClass, and MAGIC are Apache-2.0, GPL-3.0, and GPL-2.0, respectively. The code for scGCL, scFP, and scBFP has no public declaration of license. For each baseline, we adhered the hyperpametee/parammterr setting the released code or respective paper.
Table 12: URL links for baselines.
Baseline
URL Link
scTA
DCA
https//gittbb.com//heeibbbbbaa
AutoClass
https//ghttbb..oomdddssppaauuuuu
scGNN 2.0
scGCL
https//gghhubbboomm//cccoonoogon
MAGIC
scFP
https//ggthbbbcoomm/mussco22227
scBFP
httss//ghthbbb.com//mmsooo000//2
G.4
Evaluation Metries
G.4.1
Clustering
Higher ARI, NMI, and CA indicate better performance in cell clustering.
ARL The Adjusted Rand Index (ARI) is the sureeted-for-chanee version of the Rand Index (RI). RI
computed as follows:
RI TP + TN
(12)
where TP is the number of true positives and TN is the number of true negatives. True positive indicates the number of cell pairs correctly assigned to the same cluster, and TP indicates the number of cell pairs correctly assigned to different clusters. ART can be calculated as follows:
RI E(RI)
ART
(13)
max RT) E[R
While RI produces a value between 0 and 1, ARI can produce negative values the index less than the expected index.
NML Normalized Mutual Information (NMI) is a normalization of Mutual Information (MI) score to scale the scores between 0 and 1. NMI is computed as follows:
x T(S:C)
NMT H(S) H(C)
(14)
where S is ground-truth cell types, ((.,)) :) is the mutual information between two input distributions, and (-)) is the entropy function. Here, all logs base-2. Higher NMI indicates the distribution of predicted cluster distribution is more similar to ground-true -ttnh cell type distribution.
CA. Clustering Accuracy is calculated as follows:
ΣN sm
(15) where 8; is the ground-truth cell type the i-th cell, e; is predicted cluster assignment the i-th cell, and m(.) is the matching function responsible for mapping predicted cluster assignments to ground-trun truth cell types.
CA max
N
G.4.2 Recovery
Lower Median L.1 Distance and RMSE indicate better performance in data recovery. Consider two set X' (I1, ... #n) and y = (y),..., yn). where the set of imputed values and y is the set of their ground-truth values.
19

---

Median L1 Distance. Median LI Distance is calculated as follows:
Median L1 Distance = mediam ( - -y1l- vtl...., I mnl).
(16)
RMSE. Root Mean Square Error (RMSE) is computed follows:
N Ei=1 (a; y6)
RMSE(X.))
(17)
N
H
Additional Experimental Results
H.1 Varying Scales across Genes
4000
3000
2000
1000
PSMAS
PON
CTRB2
WP
CELAJA
ARS
PEGJA
000
SST
NS
Figure 9: An heatmap of the cell-gene matrix in the Baron Human dataset. We randomly selected 10
genes (columns).
20

---

H.2
Dropout Recovery
Baron Mouse
Puncreas
Mouse Bladder
0.85
0.7
0.8
Median L1 Distance
0.5
0.55
0.8
0.4
0.25
20%
5.7%%
40% 40%67-9%)
(-7.0%)
80%
(-6.2%)
0.2
20%
(1.3%%)
(344%)
0.1 (11.%)
40%
(-1.%%
80%
Zeisel
Worm Neuron
Baron Human
1.2
0.8
0.95
0.8
0.4
0.45
(-899%)
(-77%%)
(-7,6%)
(-10.4%)
0.2
(9.2%)
(-10.8%)
(-0.4%)
(-1.2%) 40%
(-744%)
20%
40%
80%
20%
40%
80%
20%
80%
Dropout rate
Dropout rate
Dropout rate
DCA
D
AutoClass
SoGNN 2.0
soGCL
MAGIC
ScFP
scBFP
scCR
Figure 10: Performance on dropout recovery, measured by LI Median Distance. Figures highlighted in green indicate reduction rates from the most competitive baseline at each setting.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clarified the scope of our work in the abstract and Sec. The contributions of our paper are summarized in Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations of our work in Sec. 6 as follows: Like other scRNA-seq imputation methods, seCR specifically designed for scRNA-seq data.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification:
We provide the proof of convergence of FP in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce the main experimental results of our work. See Appendix G.I and Appendix G.2
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
23

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the publicly available sources of datasets and baselines Ap- pendix G.2 and Table 12 in Appendix G.3 respectively.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccppllligggddeeeeeeeeeeee Coaee//dddeSebmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details in Sec. 5.1 and Appendix G.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide the average performance with standard deviation errors across independent three runs. See Table 1 and Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide detailed information on the computer resources in Appendix G.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discussed both potential positive societal impacts and negative societal impacts of our work in the Broader Impacts section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We specify the sources and licenses for all the baselines and datasets in Appendix G.3land and Appendix G.2 respectively.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [Yes]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "1KvaR2N2Je", "reviewer": "Reviewer_NnmD", "summary": "The paper proposes an approach for single-cell RNA-seq data imputation. The data comes as a matrix capturing relationship between cells and genes. Zero values in that matrix represent unobserved gene expression that can result from technical omissions (known as dropouts) and true biological absence. The non-zero values also suffer from noise such as cell and batch effects. The goal is to impute and de-noise observed single-cell RNA-seq data.\n\nAn effective prior approach is based on kNN graphs, where one first builds an adjacency matrix between cells or genes using cosine similarity and kNN neighborhoods relative to RNA-seq data. In contrast to prior work that focuses on adjacency matrices informed by “association” links, the proposed approach aims at modelling “dissociation” links that have negative cosine similarity. The approach proceeds in multiple stages: \n- Pre-imputation stage where kNN graph is built on the input matrix and similar to Markov chains, starting from random state (i.e., feature matrix of dimension $N_{cell} \\times N_{gene}$) one “diffuses” to the stationary distribution (Appendix A for details). \n- The second stage appends negated pre-imputed matrix making the feature matrix $N_{cell} \\times 2N_{gene}$ that allows for kNN graphs accounting for both “association” and “disassociation” relationships to be reflected in the adjacency matrix. This is followed by gene-to-gene and cell-to-cell propagation (i.e., stationary distribution of the Markov chain given by these matrices) with resulting matrices convexly combined into imputed “complete relationship”. \n- Final step is de-noising where now propagation of information involves convex combination with the original feature matrix and adjacency matrix build using kNN graph on the back of “complete relationship” from step ii). The final output is a convex combination of steps ii) and iii).\n\nExperiments involve cell clustering, recovery of dropout rates, robustness relative to dropouts, identification of rare cell types, modelling disassociation rates, etc.", "questions": "M is of dimension N x F (line 112)?\n\nHow do you decide that cell row is “unknown” from observed data?\n\nDropout rates? How was this done exactly?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This is an interesting problem that relates nicely to link prediction in graph neural networks. It has been clearly presented with strong motivation by noise and dropouts. The paper is also clearly written and well-organized. I would hope that there will be follow up from the community focusing on link prediction.\n\nThe approach is not straightforward and involves several “propagation” steps and, contrary to past work, incorporates the disassociation and negative correlations into kNN adjacency matrices. \n\nEmpirical performance in some cell clustering tasks is not incrementally but significantly improved. The method also appears to be more robust relative to dropouts than the alternatives.", "weaknesses": "An ablation is missing relative to different steps (pre-imputation, complete relationship, de-noising stage). Hence, it is unclear if they are needed and to what extent they contribute to the performance improvement.\n\nImputation metrics might be dependent on dropout strategy and it would be good to discuss what kind of “random” strategies have been used and how likely they are to reflect the corruptions specific to single-cell RNA-seq. Is there any way to generate “challenging” splits that are better at reflecting the “generalization” and \"robustness\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Imputation metrics might be dependent on dropout strategy and it would be good to discuss what kind of “random” strategies have been used and how likely they are to reflect the corruptions specific to single-cell RNA-seq. Is there any way to generate “challenging” splits that are better at reflecting the “generalization” and \"robustness\"?\n\n**Yes, there is a specific pattern of dropouts in real scRNA-seq data, and we perform additional experiments applying a realistic dropout strategy** reflecting this pattern. Existing studies [1, 2] simulate dropout by randomly sampling non-zero values in a cell-gene matrix from a uniform distribution and setting them to zero (i.e., missing completely at random (MCAR)). However, in real scRNA-seq data, dropouts occur more frequently in genes with low expression levels rather than those with high variance [3]. This is because the probability of capturing RNA transcripts of low-expression-level genes during sequencing is lower. Based on this pattern of dropouts, we select the 1000 genes with the lowest expression levels and simulate dropout only in these genes. We randomly sample non-zero values of these genes from a uniform distribution and replace the sampled values with zero (i.e., missing not at random (MNAR)).\n\nTable 1 in the PDF of the global response shows the performance comparison under the aforementioned MNAR settings in terms of data recovery, measured by RMSE. We compare our scCR to the two most competitive baselines, scFP [1] and scBFP [2]. The number of dropouts is set to $20\\%$ of the total number values in a cell-gene matrix. As shown in the table, **scCR outperforms the compared methods by significant margins in the realistic dropout settings, demonstrating the robustness of scCR in realistic scenarios.** We believe the reviewer has highlighted a very important aspect of dropout recovery in scRNA-seq data research. The consideration of realistic dropout simulation can help pre-assess the generalizability of techniques in real-world scRNA-seq application. We will include this important discussion and the experimental results in our final version.\n\n> An ablation is missing relative to different steps (pre-imputation, complete relationship, de-noising stage).\n\nAlthough we have conducted an ablation study analyzing the effectiveness of concatenation and standardization processes in the complete relation stage of scCR as shown in Table 2 in the manuscript, **we conduct an additional ablation study to explore the effectiveness of each stage of scCR.** Table 2 in the PDF of the global response shows the results of the ablation study in terms of cell clustering, measured by ARI. As shown in the table, the addition of the complete relation stage and the denoising stage notably enhance the performance compared to when the pre-imputation stage is used alone. We can confirm that **the complete relation stage and the denoising stage significantly contribute to the outstanding performance of scCR.** This ablation study emphasizes the well-founded design of our scCR.\n\n> How do you decide that cell row is “unknown” from observed data?\n\n**We do not decide known or unknown values from a given observed cell-gene matrix when using our scCR.** In this paper, the terms known and unknown are used solely to explain the process of Feature Propagation (FP) [4], which addresses missing feature imputation on graph-structured data. FP assumes that the locations of both observed (known) and unobserved (unknown) values in a feature matrix are given. FP imputes unobserved values by diffusing observed values while preserving these observed values. In contrast, in scRNA-seq data recovery, all values are observed (i.e., known) in a given cell-gene matrix. Thus, to apply FP to scRNA-seq data, FP-based imputation methods treat zero values as unknown values to be imputed via features diffused from non-zero values. For clarity, we will add this explanation to our final version.\n\n> Dropout rates? How was this done exactly?\n\nFollowing conventional dropout recovery research, given a cell-gene matrix, we randomly sampled non-zero values from a uniform distribution at dropout rates of $ \\{ 0.2, 0.4, 0.8 \\} $. We then set these sampled non-zero values to zero, creating false zeros.\n\n> M is of dimension N x F (line 112)?\n\nYes, we thank you for pointing out the typo. As the reviewer mentioned, $\\mathbf{M}$ has the same dimension as a given feature matrix $\\mathbf{X}\\in \\mathbb{R}^{N \\times F}$, where $N$ is the number of nodes and $F$ is the number of feature channels. \n\n\n[1] S. Yun et al., \"Single-cell RNA-seq data imputation using feature propagation,\" arXiv preprint arXiv:2307.10037, 2023. \\\n[2] J. Lee et al., \"Single-cell RNA sequencing data imputation using bi-level feature propagation,\" Briefings in Bioinformatics, 2024. \\\n[3] Y. Liu, et al., \"iDESC: identifying differential expression in single-cell RNA sequencing data with multiple subjects,\" BMC bioinformatics, 2023. \\\n[4] E. Rossi et al. \"On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features,\" Learning on graphs conference,” PMLR, 2022.", "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": "DNbB2K9ORA", "reviewer": "Reviewer_49oE", "summary": "This paper introduces a novel imputation method for scRNA-seq data that accounts for both associating and dissociating gene relationships by using a k-NN graph and negating the cell-gene matrix. The method standardizes gene value distributions and shows significant performance improvements in cell clustering and gene expression recovery across six datasets, outperforming existing methods.", "questions": "1.\tThere are now many methods using large models for cell clustering, such as SCGPT and GeneFormer. How do these methods compare in terms of effectiveness?", "limitations": "None", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper introduces a new imputation method named Single-Cell Complete Relationship (scCR) that addresses the limitations of current propagation-based approaches for scRNA-seq data by modeling both associating and dissociating gene-gene relationships.\n2.\tThe extensive experiments conducted by the authors show that scCR significantly outperforms existing methods in gene expression recovery and cell clustering, highlighting its effectiveness in capturing complete gene-gene relationships and improving the quality of scRNA-seq data analysis. \n3.\tThe paper is well-structured and clearly written.", "weaknesses": "1.\tThe proposed method appears too simple and lacks significant innovation.\n2.\tThe paper does not clearly articulate the motivation behind the proposed method. Specifically, it does not adequately explain what dissociating relationships among genes are or why identifying these relationships is effective for addressing the research problem. \n3.\tThe experiments lack biological validation, and relevant case studies are needed to support the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> How do large models for cell clustering, such as SCGPT and GeneFormer, compare in terms of effectiveness?\n\nOur method and large-scale models have **clearly different objectives; while our method tackles denoising scRNA-seq data, large-scale models (e.g., scGPT and Geneformer) targets learning gene and cell embeddings using neural networks pre-trained on large-scale datasets for transfer learning.**\n\nTherefore, our method and large-scale models are **not in a relationship where their effectiveness can be compared, but rather in a relationship where they can collaborate to create synergy.** Our scCR can provide denoised scRNA-seq data to large-scale models. To confirm that scCR can improve the performance of large-scale models, we conduct an additional experiment using scGPT [1]. We measure the cell type annotation performance of an scGPT model on the Multiple Sclerosis dataset [2] when we apply our scCR to the input data of scGPT compared to when we do not apply it (i.e., when using raw data). Table 3 in the PDF of the global response shows the cell type annotation performance of the scGPT model fine-tuned on the dataset, averaged across three independent runs. As shown in the table, **our scCR improves the cell type classification performance of the scGPT model.** This result demonstrates that our scCR effectively addresses noise contained in scRNA-seq data and can assist the large-scale models.\n\n> The experiments lack biological validation and relevant case studies\n\nTo verify whether scCR can provide biological insights, we confirm that **scCR enriches relevant genes in lupus, a chronic autoimmune disease.** Specifically, we conduct an in-depth analysis on the PBMCs dataset [3] obtained from lupus patients. We perform GSEA enrichment tests [4] that identify pathways related to specific conditions. In this case, the condition corresponds to interferon-stimulated CD16 Monocytes. We use both raw data and data imputed by scCR, and compare the results from them. When comparing the top 20 most significantly enriched pathways, **scCR newly identifies four SARS_COV-related pathways in interferon-stimulated CD16 monocytes.** Since lupus is an autoimmune disease characterized by an overactive immune system that attacks the body's own tissues, the activation of SARS_COV-related pathways may indicate an overactive or abnormally activated immune response in lupus patients, reacting excessively to viral infections. This suggests that the pathways identified through **scCR's denoising process provide new and important biological insights that were previously obscured by noise**, highlighting the utility of scCR in revealing relevant gene interactions and pathways. We will include this experimental result regarding biological validation in our final version.\n\n> Too simple and lacks significant innovation.\n\nWe believe that **utilizing biomedical evidence and domain-specific knowledge is crucial for the development of machine learning for healthcare.** Furthermore, we expect that **our work will lead subsequent frameworks to take into account the existence of two types of gene-gene relationships** in scRNA-seq data. While **designing sophisticated and complex methods is also important**, we believe that **biomedical evidence can drive significant progress in machine learning for healthcare**, and our work can serve as a good example.\n\n> Motivation and adequate explaination of what dissociating relationships among genes are or why identifying these relationships is effective for addressing the research problem.\n\n**Associating genes refer to genes that co-occur**, while **dissociating genes refer to genes that avoid each other** [6]. Mathematically speaking, associating relationships and dissociating relationships correspond to positive and negative correlation coefficients, respectively. The core idea of previous work, scBFP [7] is to impute false zeros (dropouts) in a gene based solely on associating genes with high cosine similarity. **Although scRNA-seq data imputation is a very challenging task due to severe noise, scBFP overlooks the presence of dissociating genes.** Within a cell, when considering the value to be imputed for gene Q, the value for its associating gene can assist in inferring the value for gene Q. However, its dissociating gene can also provide crucial information. **If its dissociating gene has a high value, the value for gene Q may be low because they avoid each other.** Unlike scBFP, our scCR can leverage dissociating gene-gene relationships via the negation of a cell-gene matrix. Despite its simplicity, our scCR successfully models dissociating gene-gene relationships as shown in Figure 8 in the manuscript. Furthermore, scCR significantly outperforms state-of-the-art methods in various downstream tasks, as shown in Table 1, Figure 5, Figure 6, and Figure 7 in the manuscript. We will add this detailed explanation regarding associating and dissociating relationships, as well as the clear motivation behind scCR, to our final version.\n\n\n[1] H. Cui et al., “scGPT: toward building a foundation model for single-cell multi-omics using generative AI,” Nature Methods, 2024. \\\n[2] L. Schirmer et al., “Neuronal vulnerability and multilineage diversity in multiple sclerosis,” Nature, 2019. \\\n[3] H. M. Kang et al., “Multiplexed droplet single-cell RNA-sequencing using natural genetic variation,” Nature biotechnology, 2018. \\\n[4] A. Subramanian et al., “Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles,” PNAS, 2005.\\\n[5] E. Rossi et al., “On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features,” LoG, 2021. \\\n[6] F. J. Whelan et al., “Coinfinder: detecting significant associations and dissociations in pangenomes,” Microbial genomics, 2020. \\\n[7] J. Lee et al., “Single-cell RNA sequencing data imputation using bi-level feature propagation,” Briefings in Bioinformatics, 2024.", "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": "Pim7jYRgJq", "reviewer": "Reviewer_wZRo", "summary": "This paper introduced a new scRNA-seq imputation method, scCR, utilizing both associating and dissociating gene-gene relationships to improve the accuracy of scRNA-seq imputation, especially on noisy dataset. \nThe method constructed comprehensive k-NN graph for both cell-cell and gene-gene. Standardize the value distribution of each gene to enhance gene-gene relationship modeling. \nComprehensive analysis on multiple datasets demonstrates the advantage of scCR compared with state-of-the-art methods in two tasks, gene expression recovery and cell clustering, especially on rare cell types.", "questions": "The overall paper is quite complete and comprehensive. \nOnly a few questions, 1. the impact of hyperparameter selection, additional set of experiments would be perfect. But due to the time limit, theoretical analysis would also be very helpful to understand how sensitive the model is and make the method easier to use.\n2. The memory usage of this method on different scales gives potential users a better sense of its applicability and resource requirements.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper tackles an important problem, scRNA-seq data imputation, with extra information from negatively correlated gene relationships. The idea itself is straightforward yet effective. \nThe paper includes extensive and solid experiments on multiple datasets. The experiments show solid performance improvement compared to multiple baseline methods. The paper explores the variance on dataset selection and dropout rate. \nThis paper also includes a scalability study to demonstrate its advantage on runtime.", "weaknesses": "Though the paper explores variance on dataset selection and dropout rate, yet the variance is mainly focus on dataset. It would be helpful to include a detailed sensitivity analysis of key hyperparameters, such as k for k-NN, \\alpha, \\beta, and \\gamma. \nThe paper includes a runtime analysis, but not a memory usage analysis. The paper can be more comprehensive to include memory usage analysis to show its advantage on scalability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It would be helpful to include a detailed sensitivity analysis of key hyperparameters, such as k for k-NN, \\alpha, \\beta, and \\gamma. The impact of hyperparameter selection, additional set of experiments would be perfect. But due to the time limit, theoretical analysis would also be very helpful to understand how sensitive the model is and make the method easier to use.\n\nWe conduct additional experiments to address the reviewer’s concerns and **provide a comprehensive analysis of the impact of different hyperparameters, including $\\alpha$, $\\beta$, $\\gamma$ and $k$**, on the performance of scCR. We report ARI in cell clustering on three datasets by varying $\\alpha$, $\\beta$, $\\gamma$, and $k$ in the ranges of \\{$ 0.01, 0.05, 0.1, 0.5, 0.9$\\}, \\{$ 0.1, 0.5, 0.9, 0.95, 0.99, 0.999$\\}, \\{$ 0.001, 0.01, 0.05, 0.1, 0.5, 0.9$\\}, and \\{$ 1, 2, 3, 5, 10, 15$\\}, respectively. When varying a target parameter, we fix the other hyperparameters to their default settings. Table 4, Table 5, Table 6, and Table 7 in the PDF of the global response demonstrate how the choice of hyperparameters impacts the performance of scCR. As shown in the tables, $\\alpha=0.05$, $\\beta=0.99$, $\\gamma=0.01$, $k=2$, which are values used in this work, generally show good performance. In terms of sensitivity, when the runner-up’s ARI is $0.660\\pm0.00$, $0.848\\pm0.00$, and $0.677\\pm0.00$ on Baron Mouse, Zeisel, Baron Human, respectively, **scCR show its robustness against hyperparameter variations.** Specifically, $\\alpha \\in $\\{$ 0.05, 0.1, 0.5 $\\}, $\\beta \\in$ \\{$  0.99, 0.999 $\\}, and $\\gamma \\in $ \\{$ 0.001, 0.01 $\\} result in state-of-the-art performance across the datasets. In the case of $k$, except for Baron Human, scCR shows outstanding performance regardless of values for $k$. We can also observe that varying a hyperparameter results in superior performance to that of the default hyperparameter. Nevertheless, considering the unsupervised nature of the single-cell analysis, we set the hyperparameters of scCR to default settings by fixing the hyperparameters that generally work well. We will add this discussion and the experimental results regarding the hyperparameter sensitivity of scCR to our final version.\n\n> The paper includes a runtime analysis, but not a memory usage analysis. The paper can be more comprehensive to include memory usage analysis to show its advantage on scalability.\nThe memory usage of this method on different scales gives potential users a better sense of its applicability and resource requirements.\n\n**We investigate the memory complexity of all methods used in this paper** and conduct additional experiments to analyze the memory usage of our scCR. Table 8 in the PDF of the general response compares the inputs and memory complexity of scCR with other state-of-the-art methods. To mitigate the heavy memory usage during $k$-NN graph construction, we utilize a batch-wise $k$-NN graph construction strategy. When constructing $k$-NN graphs among genes, we divide genes into batches with batchsize $B$, and compute $k$-nearest neighbors for each batch. Similarly, we apply the same batch-wise strategy when constructing $k$-NN graphs among cells. This strategy reduces the memory requirement because it avoids the need to store distances between all points in the entire dataset at once. Specifically, in the memory complexity of scCR, batch-wise $k$-NN graph construction changes $O(G^2)$ and $O(C^2)$ to $O(BG)$ and $O(BC)$, respectively. Thus, batch-wise $k$-NN graph construction can handle large datasets that would otherwise be infeasible to process due to memory constraints. Additionally, scCR does not require any trainable parameters used by other deep-learning-based models.\n\n**We further measure the memory usage of scCR across various datasets**, as shown in Table 9 in the PDF of the general response. The results in the table indicate that the advantages of scCR extend beyond its superior performance and time efficiency, showcasing its scalability as well. We will include this detailed memory usage analysis in the final version of our manuscript to provide a more comprehensive evaluation of scCR.", "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:
We 1) propose a novel imputation method that newly employs dissociating relationships in addition to associating relationships, 2) standardizes the value distribution of each gene to have standard distributions regardless of the gene, and 3) demonstrate that the proposed method 
achieves exceptional performance gains in both cell clustering and gene expression recovery.

We appreciate the reviewers’ thoughtful comments of our work. 
Especially, we thank the reviewers for the positive feedbacks about "clear and strong motivation", "straight forward yet effective approach", and "well organized paper".

Meta-review: The reviewers consider the simplicity and effectiveness of the method, solid empirical evaluation, and biological significance of the task as notable strengths. Some critical comments were also raised related to simplicity of the method and its motivation.

The authors provided thorough rebuttals that seem to address all critical comments, and no further specific criticism was presented during the discussion period, so we conclude that everyone is satisfied.
Decision: Accept (poster)