GraphLCP : Structure-Aware Localized Conformal Prediction on Graphs Peyman Baghershahi, Fangxin Wang, Debmalya Mandal, Sourav Medya Abstract Conformal prediction (CP) provides a distribution-free approach to uncertainty quantification with finite-sample guarantees. However, applying CP to graph neural networks ( Gnn s) remains challenging as the combinatorial nature of graphs often leads to insufficiently certain predictions and indiscriminative embeddings. Existing methods primarily rely on embedding-space proximity for localization, which can be unreliable for graphs and yield inefficient prediction sets. We propose GraphLCP , a proximity-based localized CP framework that explicitly incorporates graph topology and inter-node dependencies into localization and weighting. Our approach introduces a feature-aware densification step to mitigate locality bias in sparse graphs, followed by a Personalized PageRank-based kernel computation to model structural proximity. This enables topology-dependent anchor sampling and calibration weighting that captures both local and long-range dependencies. Extensive experiments on several regression and classification datasets demonstrate that GraphLCP guarantees marginal coverage with finite samples while efficiently attaining favorable test conditional coverage across various conditioning scenarios. 1 Introduction Graph neural networks ( Gnn s) are increasingly deployed for drug discovery feinberg2018potential , weather prediction ma2023histgnn , and fraud detection in financial networks cheng2025graph . In these high-stakes applications, relying solely on point predictions is risky and the practitioners require reliable uncertainty quantification (UQ) of Gnn s to assess the trustworthiness of predictions. Conformal Prediction (CP) is an effective distribution-free framework for constructing set-valued predictions that guarantees covering the ground-truth values using a finite sample of data points shafer2008tutorial ; angelopoulos2021gentle . Consequently, CP has emerged as a widely adopted approach for post-hoc reliability, applied to graph tasks such as standard regression, link prediction, and out-of-distribution detection oodcpgnn2025 ; linkfdr2023 ; cplinprediction2024 . Classical CP guarantees marginal coverage on average over the test distribution. However, in many practical settings, uncertainty is heterogeneous, requiring reliability specific to subpopulations or local contexts ( validadaptiveacoverage2020 ; validconfidenseset2021 ) . Achieving exact conditional coverage per sample is known to be impossible in finite samples infeasiblecondcp2020 . This limitation has motivated a growing body of work on relaxed notions of conditional coverage, leveraging localization and weighting strategies to improve validity ( wcp2019 ; beyondexchangeability2022 ) . A central requirement across these approaches is the availability of a meaningful notion of proximity between the test sample and the calibration data. In graphs, predictive reliability varies across regions with different homophily patterns ( naps2023 ) . Besides, applying CP on graphs is challenging because nodes are naturally dependent, violating standard i.i.d assumptions ( networkcp2023 ; naps2023 ) . In practice, CP for GNNs often leverages the embedding space, using learned representations as proxies for instances ( codrug2023 ) . However, this proxy can be unreliable as message passing can suffer from a graph-topological bottleneck (over-squashing), restricting global information flow and exacerbating noise under heterophily ( oversmoothingoversquashingtradeoff2023 ) . Meanwhile, deeper message passing causes over-smoothing, reducing the variance of similarity measures ( oversmoothingsurvey2023 ) . Also, Gnn s generally exhibit under-confidence, suggesting insufficient separability in the learned representation ( cagcn2021 ; gats2022 ) . These effects complicate the core requirement of having a stable proximity kernel for localized CP, which reweights calibration data based on their similarity to the test instance ( rlcp2024 ) . Recent work has extended conformal prediction to Gnn s to address structural dependencies, with approaches ranging from handling inductive covariate shift ( inductivecpgnn2024 ; naps2023 ) to developing diffusion-based scores ( cpforgnn2023 ) . Built on findings which preserve exchangeability under permutation-invariant transformation ranklist2021 ; networkcp2023 ; networkassistedcp2025 , recent studies have also applied CP to Gnn s in transductive settings cfgnn2023 ; rrgnn2025 . Additional related work is provided in the Appendix A.1 . However, several limitations remain in the existing approaches. A few methods rely on training auxiliary models to calibrate residuals cfgnn2023 ; rrgnn2025 or fine-tuning the base predictor codrug2023 . These increase computational overhead and reduce sample efficiency by necessitating data splitting, effectively deviating from the lightweight, post-hoc nature that makes CP useful. Also, the methods based on localized CP typically rely either on embedding-space weighting (e.g., kernel density estimation) codrug2023 or on purely structural partitioning (e.g., hard clustering of communities) rrgnn2025 . These strategies can be fragile because embedding-based similarities may become indiscriminative due to smoothing, while rigid structural clusters may fail to capture fine-grained local heterophily in graphs. As a result, existing graph CP methods typically perform best under strong homophily and may yield overly conservative or poorly localized prediction sets in complex topologies. In this work, we bridge the gap between structural and feature-based localization. We propose GraphLCP , a proximity-based localized CP framework for Gnn s that explicitly incorporates graph topology and inter-node dependencies into localization-based weighting for conformal quantile computation. Our approach replaces embedding-only proximity with a structure-aware proximity kernel based on Personalized PageRank (PPR), enabling topology-dependent anchor sampling and calibration weighting. To mitigate locality bias in sparse graphs and capture long-range dependencies, we introduce a feature-aware densification step that augments the graph using embedding similarity prior to kernel computation. Together, these enable GraphLCP to maintain marginal coverage while achieving efficient approximate conditional coverage across node-level regression and classification tasks. Through experiments on seven regression and eight classification datasets, we demonstrate the efficacy of GraphLCP based on marginal coverage and favorable approximate conditional coverage, with efficient prediction length (size). 2 Preliminaries and Problem Setup 2.1 Graph Neural Network ( Gnn ) In this work, we focus on the canonical form of GNNs, which use a message-passing mechanism. We denote a graph as \mathcal{G}(\mathcal{V},\mathbf{A},\textbf{X}) where \mathcal{V} is the set of vertices or nodes with |\mathcal{V}|=N_{G} ; \textbf{X}\in\mathbb{R}^{N_{G}\times d} and \mathbf{A}\in\{0,1\}^{N_{G}\times N_{G}} are the features and the adjacency matrix of the graph. According to mpnn2017 , an L -layer pretrained message-passing model \phi derives a node’s l -th layer state or representation, \mathbf{x}_{u}^{(l)}(\forall u\in\mathcal{V},\,l\leq L ) using three functions – (i) a message-passing function M_{\phi} that propagates the l -th layer state of every node in the neighborhood \mathcal{N}_{u}=\{v:v\in\mathcal{V},\,\mathbf{A}_{uv}=1\} , (ii) an aggregate function C_{\phi} to combine the messages from M_{\phi} , and (iii) an update function U_{\phi} to derive the node’s latest state integrating its (l-1) -th layer state and the aggregated message. Formally, \mathbf{x}_{u}^{(l)}=U_{\phi}(C_{\phi}(\{M_{\phi}(\mathbf{x}_{v}^{(l)});v\in\mathcal{N}_{u}\}),\mathbf{x}_{u}^{(l-1)}). Given a downstream task, most GNNs use a simple function (e.g., a linear neural network) to decode the latest embeddings or states to prediction logits as \hat{y}_{u}=f(\mathbf{x}_{u}^{(L)}) . Also, for the ease of notation, we use: \mathbf{x}_{i}:\,\forall i\in[N_{G}] instead of \mathbf{x}_{u}^{(L)}:\,\forall u\in\mathcal{V} , and also y_{i} instead of \hat{y}_{u} for i\in[N_{G}] . In contrast to standard conformal prediction, where samples are assumed to be exchangeable, conformal validity on graphs is not trivial because node samples are generally dependent, particularly in inductive settings. However, in the node-level transductive setting with a random train/calibration/test split, calibration and test nodes remain exchangeable as long as their labels are not used during training. Once the GNN is trained and frozen, it induces a deterministic transformation from each node and its topological context to an embedding representation, which is then used for conformal prediction. Since conventional GNNs are permutation equivariant and the resulting nonconformity scores are permutation-invariant with respect to calibration and test node permutations, standard conformal prediction guarantees marginal node-level coverage under this transductive setup cfgnn2023 ; networkcp2023 . 2.2 Conformal Prediction (CP) Split Conformal Prediction (SCP). Given a dataset \mathcal{D}=\{(\mathbf{x}_{i},y_{i}):(\mathbf{x}_{i},y_{i})\sim\mathcal{P}=\mathcal{P}_{X}\times\mathcal{P}_{Y|X},\ \mathbf{x}_{i}\in\mathcal{X},\ y_{i}\in\mathcal{Y}\}_{i=1}^{N_{G}} (e.g., \mathbf{x}_{i} are the nodes or their embeddings), we first split the dataset to three disjoint sets: 1) \mathcal{D}_{tr} with labels for supervised training, 2) \mathcal{D}_{cal} with labels as holdout calibration set, and 3) \mathcal{D}_{test} purposefully made without labels as test point. After training the message-passing ( \phi ) and decoder ( f ) modules on \mathcal{D}_{tr} , we freeze the model for CP. Having n labeled samples \{z_{i}=(\mathbf{x}_{i},y_{i})\in\mathcal{D}_{cal}:\forall i\in[n]\} , the problem is to construct a prediction interval \widehat{C}_{n}(\mathbf{x}_{n+1}) for an unlabeled sample \mathbf{x}_{n+1}\in\mathcal{D}_{test} that contains or “covers” the groundtruth label y_{n+1} of the test sample with probability at least 1-\alpha , where \alpha is the miscoverage rate. In order to achieve the desired coverage, every calibration sample and the test sample are assigned a non-conformity as S_{i}=s(\mathbf{x}_{i},y_{i}),\forall i\in[n] and S_{n+1}=s(\mathbf{x}_{n+1},y):y\in\mathcal{Y} , where s(x,y) is a non-conformity score function. For example, absolute residual, s(x,y)=|y-f(x)| , is a commonly used function. Additionally, let \hat{q}=\text{Quantile}_{1-\alpha}(\sum_{i=1}^{n}\frac{1}{n+1}\delta_{s(z_{i})}+\frac{1}{n+1}\delta_{+\infty}) , where \delta_{x} is the probability distribution that places probability 1 on the value x , and 0 everywhere else. If S_{n+1} is exchangeable with \{S_{i}\}_{i=1}^{n} , then by constructing \widehat{C}_{n}(\mathbf{x}_{n+1})=\{y\in\mathcal{Y}:s(\mathbf{x}_{n+1},y)\leq\hat{q}\} we have \mathbb{P}\{y_{n+1}\in\widehat{C}_{n}(\mathbf{x}_{n+1})\}\geq 1-\alpha maincp2005 . This, being averaged over all random draws of the calibration and the test samples, is called marginal coverage . However, if the coverage is guaranteed for every specific instance of \mathbf{x}_{n+1} , it is called conditional coverage , requiring \mathbb{P}\{y_{n+1}\in\widehat{C}_{n}(\mathbf{x}_{n+1})\mid\mathbf{x}_{n+1}\}\geq 1-\alpha . infeasiblecondcp2020 shows that achieving such test conditional coverage is infeasible. Therefore, test conditional coverage is commonly relaxed and measured for a test sample \mathbf{x}_{n+1}\in B where B\in\mathcal{B} and \mathcal{B} is a collection of subsets of feature space, i.e. \mathcal{B}\subseteq\mathcal{X} , and the guarantee requires \mathbb{P}\{y_{n+1}\in\widehat{C}_{n}(\mathbf{x}_{n+1})\mid\mathbf{x}_{n+1}\in B:B\in\mathcal{B}\}\geq 1-\alpha . Weighted Conformal Prediction (WCP). Weighted Conformal Prediction (WCP) is one of the ways to attain the above notion of relaxed test conditional coverage wcp2019 . Suppose we are given a kernel function H(\mathbf{x},\mathbf{x}^{\prime}) , e.g. H(\mathbf{x},\mathbf{x}^{\prime})=\frac{1}{(2\pi h^{2})^{{d}/{2}}}\exp\left(-\frac{\|\mathbf{x}-\mathbf{x}^{\prime}\|^{2}_{2}}{2h^{2}}\right) . Then we can apply WCP for local coverage by using the kernel centered at \mathbf{x}=\mathbf{x}_{n+1} , and obtain coverage for a nearby (synthetic) sample \tilde{\mathbf{x}}_{n+1}=\mathbf{x}_{n+1}+h\cdot\mathbf{w} s.t. \mathbf{w}\sim H(\mathbf{x}_{n+1,.}) , but not necessarily for \mathbf{x}_{n+1} itself, i.e. \mathbb{P}\{y_{n+1}\in\widehat{C}_{n}(\tilde{\mathbf{x}}_{n+1})\mid\mathbf{x}_{n+1}=\tilde{\mathbf{x}}_{n+1}+h\cdot\mathbf{w}\}\geq 1-\alpha . This locally-weighted method, for some small bandwidth h , approximately guarantees exact coverage at \mathbf{x}_{n+1} . Randomly Localized Conformal Prediction (RLCP). Unlike WCP, the Randomly Localized Conformal Prediction (RLCP) method rlcp2024 guarantees relaxed test conditional coverage for the test sample \tilde{\mathbf{x}}_{n+1} , rather than a point \tilde{\mathbf{x}}_{n+1} in its proximity. RLCP simply apples WCP to a randomly sampled point \tilde{\mathbf{x}}_{n+1} in the proximity of \mathbf{x}_{n+1} , i.e. \tilde{\mathbf{x}}_{n+1}|\mathbf{x}_{n+1}\sim H(\mathbf{x}_{n+1,\cdot}) , which ensures \mathbb{P}\{Y_{n+1}\in\widehat{C}_{n}^{\text{RLCP}}(\mathbf{x}_{n+1},\tilde{\mathbf{x}}_{n+1})\}\geq 1-\alpha . Suppose there is a kernel function as H:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0} such that \int_{\mathcal{X}}H(x,x^{\prime})dv(x^{\prime})=1,\ \forall x\in\mathcal{X} . Now, for a test sample (\mathbf{x}_{n+1},Y_{n+1}) exchangeable with the calibration samples (\mathbf{x}_{i},Y_{i}):i\in[n] , RLCP samples an anchor point \tilde{\mathbf{x}}_{n+1}\sim\mathcal{P}_{\mathbf{x}}\circ H(\cdot,\mathbf{x}_{n+1}) and construct the CP interval/set of \mathbf{x}_{n+1} as \widehat{C}_{n}^{\text{RLCP}}(\mathbf{x}_{n+1},\tilde{\mathbf{x}}_{n+1})=\{y\in\mathcal{Y}:s(\mathbf{x}_{n+1},y)\leq\hat{q}_{1-\alpha}(\mathbf{x}_{n+1},\tilde{\mathbf{x}}_{n+1})\} where \displaystyle\hat{q}_{1-\alpha} \displaystyle(\mathbf{x}_{n+1},\tilde{\mathbf{x}}_{n+1})=\text{Quantile}_{(1-\alpha)}\sum_{i=1}^{n}\tilde{w}_{i}\delta_{s(z_{i})}+\tilde{w}_{n+1}\delta_{+\infty} (1) and the weights are derived as \tilde{w}_{i}=\frac{H(\mathbf{x}_{i},\tilde{\mathbf{x}}_{n+1})}{\sum_{j=1}^{n+1}H(\mathbf{x}_{j},\tilde{\mathbf{x}}_{n+1})} . Our Objective. We address the problem of CP for GNNs by explicitly incorporating structural proximity into the weighting step. By decoupling weights from potentially lossy encoders, we create a lower-noise residual pathway that leverages embedding proximity while controlling its influence. Our goal is to satisfy marginal coverage with efficient prediction interval sizes while achieving strong test conditional coverage. We motivate this with an empirical analysis (Appendix A.2 ) of the existing embedding-based localized methods (e.g., RLCP) failing for GNNs because indiscriminative embeddings cause feature-based proximity weights to collapse into non-informative extremes. This either completely isolates the test point or reduces to a uniform standard CP. 3 Our Method: GraphLCP Recent studies attempted to incorporate structural covariates into GNN-based conformal prediction (CP) naps2023 ; rrgnn2025 , yet they have failed to significantly improve conditional coverage. While graph structures are implicitly encoded in Gnn embeddings, lossy encoders or sparse topologies can create bottlenecks, and over-smoothing in denser graphs often diminishes topological dependencies oversquashingeffect2024 ; skipconnection2023 ; oversmoothingsurvey2023 . To mitigate this, we propose GraphLCP , a structure-aware CP method that ensures marginal coverage while achieving high relaxed test conditional coverage. Our approach utilizes a localized kernel and a weighting strategy, illustrated in Figure 1 , which remains resilient to embedding suboptimality by explicitly incorporating underlying structural dependencies (empirical evidence demonstrating the strong correlation between node homophily and coverage is provided in Appendix A.3 ). Figure 1 : GraphLCP . Given the embeddings of a frozen GNN for an input graph, GraphLCP goes through four stages: 1) PCA Transformation : high-dimensional embeddings are decorrelated and largest eigenvalues (corresponding to directions of highest variance) yield an adaptive bandwidth for an anisotropic Gaussian kernel; 2) Graph Densification : adding informative edges via a homophily-based dynamic threshold; 3) PPR Integration : utilizing the PPR kernel to sample anchor nodes (for each test sample) and weight calibration samples; and 4) Conformal Prediction : a weighted quantile is computed from calibration samples to construct the final prediction set/interval. 3.1 Sampling and Weighting with Personalized PageRank (PPR) To model structural proximity, we adopt Personalized PageRank (PPR) ppr2003 as our localization kernel. PPR captures multi-hop influence while maintaining locality via a restart probability, effectively modeling uncertainty propagation in heterogeneous graphs trustyourneighbor2021 . Unlike shortest-path or k-hop neighborhoods, PPR provides a soft, probabilistic notion of proximity that naturally aligns with weighted CP. Importantly, PPR yields a valid probability distribution over nodes, allowing it to be directly used as a randomized localization kernel compatible with RLCP. PPR is formally defined as \boldsymbol{\pi}=\beta\mathbf{s}(I-(1-\beta)\mathbf{M})^{-1} , where \beta is the restart/teleportation probability, \mathbf{s} is the seed distribution vector, with \sum_{i=1}^{|\mathcal{V}|}[\mathbf{s}]_{i}=1 , and \mathbf{M}=\mathbf{D}^{-1}\mathbf{A} is the transition matrix, with \mathbf{D} being the diagonal degree matrix. Let \mathbf{e}_{i} be a one-hot vector, s.t. [\mathbf{e}_{i}]_{i}=1 and [\mathbf{e}_{i}]_{j}=0:\forall j\in[\mathcal{V}],\,i\neq j . For a seed node u_{i} , denoted as \boldsymbol{\pi}_{i} , PPR yields a vector representing the stationary distribution of a random walk that, at each step, restarts at u_{i} with probability \beta . The value [\boldsymbol{\pi}_{i}]_{j} denotes the long-run probability of the walk being at node u_{j} if started at node u_{i} . Since, we have to use the kernel both for sampling and weighting, we use a compatible definition of PPR. Let k\sim\text{Geom}(\beta) be the length of a random walk sampled from a geometric distribution \text{Geom}(\beta) , where \beta is the probability of success (e.g., restart probability).The PPR vector is the expected position of a random walker after k steps: \boldsymbol{\pi}=\mathop{\mathbb{E}}_{L\sim\text{Geom}(\beta)}\left[\mathbf{s}\mathbf{M}^{k}\right]=\sum_{k=0}^{\infty}\beta(1-\beta)^{k}\mathbf{s}\mathbf{M}^{k} (2) Using the power iteration method, appnp2019 approximates the above PPR by K iterations rather than infinite summation so we have \boldsymbol{\pi}^{(k)}=(1-\beta)\mathbf{M}\boldsymbol{\pi}^{(k-1)}+\beta\mathbf{s} , and this converges to exact PPR once K\rightarrow\infty . Finally, we have \boldsymbol{\pi}\simeq\boldsymbol{\pi}^{(K)} . The above definition helps us sample from the distribution induced by \boldsymbol{\pi}_{u} with node u as the seed. We decompose sampling the anchor nodes into two independent steps. First, we sample a random walk length k\sim\text{Geom}(\beta) . Second, we chose the landing node the k -step random walk starting from u . Moreover, because we use the method in appnp2019 to estimate the PPR vectors, we also avoid random walks beyond K steps during sampling. This imposes a loss of probability mass (1-\beta)^{K+1} , which is negligible for a sufficiently large value of K or \beta , e.g. in our experiments, we fix K=30 . Anchor Sampling. Analogous to RLCP, in graph space, we construct prediction sets by sampling an anchor node in the neighborhood of the test node and computing conformal scores relative to this anchor. In GraphLCP , anchor nodes are sampled from the PPR-induced distribution centered at the test node, so the nearby nodes exert greater influence on the quantile estimation. Given a test node u_{n+1} , we sample the anchor node as \tilde{u}_{n+1}|u_{n+1}\sim H(u_{n+1},\cdot) . Replacing H(u_{n+1},\cdot) with distribution \boldsymbol{\pi}_{n+1} , for the seed vector \mathbf{s}_{n+1} one-hot at u_{n+1} we have: \tilde{u}_{n+1}|u_{n+1}\sim H(u_{n+1},\cdot)\rightarrow\tilde{u}_{n+1}|u_{n+1}\sim\boldsymbol{\pi}_{n+1} (3) Structural Weighting. Once the anchor node is sampled, calibration and test nodes are weighted according to their structural proximity to the anchor. Unlike Gaussian kernels, PPR is asymmetric, meaning structural influence is direction-dependent. Essentially, we have H(u_{i},u_{j})\neq H(u_{j},u_{i}) , and \tilde{w}_{i}\sim H(u_{i},\tilde{u}_{n+1}) which requires computing \boldsymbol{\pi}_{i}:\forall i\in[n] . In cases where we have n calibration samples and m test samples s.t. nm (e.g., in a single-sample/pointwise case), this approach is inefficient. To resolve this issue for undirected graphs, we compute weights efficiently by exploiting the degree-normalized symmetry property of PPR, such that d_{i}H(u_{i},u_{j})=d_{j}H(u_{j},u_{i}) , where d_{i} denotes the degree of node u_{i} . To keep the consistency of notation, we write d_{i}[\boldsymbol{\pi}_{i}]_{j}=d_{j}[\boldsymbol{\pi}_{j}]_{i} . Letting \tilde{\boldsymbol{\pi}}_{n+1} denote the PPR-based induced distribution with sampled anchor \tilde{u}_{n+1} as the center, the calibration and test nodes are weighted according to the anchor node as follows \tilde{w}_{i}=\frac{d_{i}^{-1}[\tilde{\boldsymbol{\pi}}]_{i}}{\sum_{j=1}^{n+1}d_{j}^{-1}[\tilde{\boldsymbol{\pi}}]_{j}},\quad\forall i\in[n+1] (4) Intuitively, nodes that exert stronger structural influence on the anchor node contribute more to the conformal quantile, adapting the graph context. This topological control of nodes’ contributions particularly helps with conditional coverage by filtering out noisy information and focusing on structurally proximal nodes. Remark. While the PPR-based kernel effectively captures structural similarity between nodes, it does not incorporate node attributes. At the same time, although GNN embeddings are imperfect and can be noisy due to information bottlenecks and over-smoothing, they determine the prediction logits and therefore remain an important source of information for uncertainty quantification. In addition, the PPR-based proximity measure behaves differently depending on graph density. In dense graphs, PPR explores many paths via random walks and captures global structure, whereas in sparse graphs it performs poorly due to strong localization stronglocalizationppr2015 , since the random walk probability mass drops rapidly, leading to negligible scores for distant nodes. This causes biased or overly localized weighting. To address these limitations, we introduce a feature-aware graph densification step prior to PPR kernel computation. This augments the topology with embedding similarity, mitigating the inherent localization bias and allowing the random walk to bridge sparse regions and capture long-range semantic dependencies. We note that GNN over-smoothing collapses the embedding distance scales, so a kernel in feature space weights samples uniformly. Although continuous distances degrade in the suboptimal embedding space, the relative proximity of nodes remains robust, letting a thresholded densification extract the highest-confidence similarities. However, PPR, as a multi-hop topological diffusion process, is more robust to noise than a continuous feature-space kernel. In short, embeddings are more reliable for discrete edge creation, but too noisy for continuous weighting. 3.2 Densification to Address Local Bias To address the above limitation, we propose densifying the graph before applying the kernel. The densification procedure consists of three stages: (i) automatic selection of a densification threshold guided by graph homophily, (ii) dimensionality reduction of node embeddings via PCA to concentrate the informative signal and decouple the correlated feature dimensions, and (iii) construction of an anisotropic Gaussian similarity kernel with adaptive bandwidths to add informative edges. Together, these steps expand the effective neighborhood used by the structural kernel while avoiding excessive noise or over-densification. To achieve densification, we exploit the embedding similarities in the encoder embedding space using a Gaussian kernel. This kernel has two advantages: (i) unlike other similarity measures (e.g., cosine), it captures the non-linearity of the embeddings; and ii) the bandwidth controls the range of effect to adjust for local or global densification. To densify the graph, we construct a new adjacency matrix \tilde{\mathbf{A}} : [\tilde{\mathbf{A}}]_{ij}=\begin{cases}1&\text{if }[\mathbf{A}]_{ij}=1\\ k_{h}(\mathbf{x}_{i},\mathbf{x}_{j})&\text{if }[\mathbf{A}]_{ij}=0\text{ and }k_{h}(\mathbf{x}_{i},\mathbf{x}_{j})\geq\tau_{d}\\ 0&\text{o.w.}\end{cases} (5) where k_{h}(\mathbf{x}_{i},\mathbf{x}_{j})=\frac{1}{(2\pi h^{2})^{\frac{d}{2}}}\exp(-\frac{\|\mathbf{x}_{i}-\mathbf{x}_{j}\|^{2}_{2}}{2h^{2}}) is the Gaussian kernel with bandwidth h , and \tau_{d} is a similarity threshold for densification. Then, for the transition matrix of the PPR-based kernel, we have \mathbf{M}=\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}} , where \tilde{\mathbf{D}} is a diagonal matrix with \tilde{\mathbf{D}}_{ii}=\sum_{j=1}^{|\mathcal{V}|}[\tilde{\mathbf{A}}]_{ij} . The densification threshold \tau_{d} effectively determines the number of edges added. Small threshold values result in a nearly complete graph, increasing computational time. Moreover, the message-passing embeddings generated may be insufficiently discriminative; thus, smaller thresholds may allow the addition of potentially noisy edges. Conversely, large thresholds may hinder the addition of new edges, thereby missing informative edges that can overcome the sparsity barrier in applying the PPR-based kernel. Inspired by our empirical observations (Appendix A.3 ), we propose an automatic method to set the threshold in Appendix A.5 . Note that the edge augmentation is applied uniformly to the entire graph before conformal weighting and sampling, independent of the train, calibration, or test split. Thus, the calibration–test symmetry required for conformal validity is preserved. Dimensionality Reduction. Two pivotal issues with Gnn embeddings are as follows: (i) dimensional information redundancy resisitoversmoothing2024 , i.e., feature dimensions are highly correlated, and (ii) the lack of discriminative power due to over-smoothing oversmoothingsurvey2023 . These accumulate noise and errors in similarity measures derived from the raw, high-dimensional, ill-posed space. To address this, we use PCA pca2014 to decouple feature correlations and condense the embedding space. Formally, PCA solves the optimization problem \mathbf{V}^{pca}=\arg\max_{\mathbf{V}}\mathbf{V}^{T}\mathbf{C}_{X}\mathbf{V} , where \mathbf{V}\in\mathbb{R}^{d_{x}\times d_{z}} is an orthogonal matrix. This yields the eigenvector matrix \mathbf{V}^{pca}=[\mathbf{v}_{1},\dots,\mathbf{v}_{d}]^{T} associated with the diagonal eigenvalue matrix \mathbf{\Lambda}^{pca}=\text{diag}(\lambda_{1},\lambda_{2},\dots,\lambda_{d}) , where eigenvalues are arranged in descending order, i.e., \lambda_{i}\geq\lambda_{j} for all i