Technical Summary: GRAPHLCP

Problem Statement

Graph Neural Networks (GNNs) are increasingly deployed in high-stakes domains such as drug discovery, weather prediction, and fraud detection, necessitating reliable uncertainty quantification (UQ). Conformal Prediction (CP) offers a distribution-free framework to construct set-valued predictions with finite-sample guarantees. However, applying CP to GNNs presents unique challenges:

1. Structural Dependencies: Nodes in graphs are naturally dependent, violating the standard independent and identically distributed (i.i.d.) assumptions required for classical CP.
2. Embedding Limitations: Existing localized CP methods for graphs often rely on embedding-space proximity (e.g., kernel density estimation on GNN embeddings) to define local neighborhoods. This approach is frequently unreliable due to:
   • Over-smoothing: Deep message passing reduces the variance of similarity measures, making embeddings indiscriminative.
   • Over-squashing: Topological bottlenecks restrict global information flow, particularly under heterophily.
   • Under-confidence: GNNs often exhibit insufficient separability in learned representations.
3. Inefficiency of Existing Solutions: Current graph-specific CP methods either rely on training auxiliary models (increasing computational overhead) or use rigid structural partitions (e.g., hard clustering) that fail to capture fine-grained local heterophily. Consequently, existing methods often yield overly conservative or poorly localized prediction sets in complex topologies.

Methodology: GRAPHLCP

The authors propose GRAPHLCP, a proximity-based localized Conformal Prediction framework designed to explicitly incorporate graph topology and inter-node dependencies into the localization and weighting steps. The method operates in a transductive setting where the GNN is pre-trained and frozen. The framework consists of four key stages:

1. Feature-Aware Densification

To mitigate locality bias in sparse graphs and capture long-range semantic dependencies, the authors introduce a densification step prior to kernel computation.

• PCA Projection: Node embeddings are first projected via Principal Component Analysis (PCA) to decouple correlated feature dimensions and condense the space, addressing the noise and redundancy caused by over-smoothing.
• Adaptive Anisotropic Kernel: An anisotropic Gaussian kernel is constructed using the PCA-transformed embeddings. The bandwidth is adapted based on the eigenvalues of the covariance matrix to account for varying scales across dimensions.
• Edge Augmentation: New edges are added to the graph adjacency matrix if the similarity between non-connected nodes (computed via the Gaussian kernel) exceeds a dynamic threshold $\tau_d$. This threshold is automatically tuned based on the graph's homophily ratio to balance the addition of informative edges against the introduction of noise.

2. Personalized PageRank (PPR) Kernel

Instead of relying solely on embedding distances, GRAPHLCP utilizes PPR to model structural proximity.

• Localization: PPR captures multi-hop influence while maintaining locality via a restart probability ($\beta$). It provides a soft, probabilistic notion of proximity that naturally aligns with weighted CP.
• Sampling: For a test node, an anchor node is sampled from the PPR-induced distribution centered at the test node. This ensures that nearby nodes exert greater influence on the quantile estimation.
• Weighting: Calibration and test nodes are weighted according to their structural proximity to the sampled anchor. The authors exploit the degree-normalized symmetry of PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) to compute weights efficiently, even when the number of calibration samples exceeds the number of test samples.

3. Randomized Localized Conformal Prediction (RLCP) Integration

GRAPHLCP adapts the RLCP framework. By sampling an anchor node $\tilde{u}_{n+1}$ from the PPR distribution of the test node $u_{n+1}$, the method constructs a prediction set based on a weighted quantile of non-conformity scores. The weights are derived from the PPR scores relative to the sampled anchor, allowing the method to adapt to the local graph context.

4. Prediction Construction

The final prediction set $\hat{C}_n(u_{n+1})$ is constructed as the set of labels $y$ such that the non-conformity score $s(u_{n+1}, y)$ is less than or equal to a weighted quantile $\hat{q}_{1-\alpha}$. This quantile is computed using the weights derived from the PPR kernel and the non-conformity scores of the calibration set.

Key Contributions

1. Structure-Aware Localization: The paper bridges the gap between structural and feature-based localization by replacing embedding-only proximity with a PPR-based kernel. This explicitly incorporates graph topology into the conformal weighting process.
2. Feature-Aware Densification: A novel pre-processing step that augments the graph topology using embedding similarity (via PCA and adaptive anisotropic kernels) to mitigate sparsity and capture long-range dependencies without relying on the potentially noisy continuous weighting of embeddings.
3. Efficient Weighting Scheme: The method provides an efficient way to compute PPR-based weights for undirected graphs by leveraging degree-normalized symmetry, avoiding the computational inefficiency of computing full PPR vectors for large calibration sets.
4. Theoretical Validity: The approach maintains the exchangeability guarantees required for marginal coverage in transductive settings while aiming to improve relaxed test-conditional coverage.

Experimental Results

The authors evaluated GRAPHLCP on seven node regression and eight node classification datasets (including citation networks, Amazon co-purchase, and geographic datasets).

• Marginal Coverage: All methods, including GRAPHLCP, satisfied the target miscoverage rate ($\alpha = 0.1$), confirming the validity of the approach.
• Conditional Coverage (WSC): In Worst-Case Slab (WSC) diagnostics, which adversarially seek the minimum coverage across projection directions, GRAPHLCP achieved the best or second-best results across most datasets, outperforming baselines like CalLCP, RLCP, and SCP.
• Group-Based Coverage: GRAPHLCP demonstrated superior coverage across partitions based on homophily, feature clustering, clustering coefficient, and node degree. The method was particularly effective in heterophilous regions where standard methods struggled.
• Prediction Efficiency: While CalLCP often produced overly large prediction sets (over-coverage), GRAPHLCP achieved favorable normalized prediction lengths, offering a better trade-off between coverage and set size.
• Ablation Studies:
  • Replacing the PPR kernel with a Gaussian kernel (GSS) resulted in lower coverage and larger prediction sets, confirming the importance of structure-aware localization.
  • The densification step was identified as the most significant component, particularly for regression tasks.
  • PCA projection was shown to be crucial for mitigating the negative effects of correlated embedding features.

Significance and Claims

The paper claims that GRAPHLCP successfully addresses the limitations of existing graph CP methods by explicitly modeling structural dependencies. By decoupling weights from potentially lossy GNN encoders and utilizing a PPR-based kernel, the method creates a "lower-noise residual pathway" for uncertainty quantification.

The authors assert that GRAPHLCP guarantees marginal coverage with finite samples while efficiently attaining favorable test-conditional coverage across various conditioning scenarios. They highlight that the method is particularly robust in complex topologies where embedding-based similarities fail due to over-smoothing or over-squashing. The work underscores the necessity of structure-aware localization for effective UQ on graphs, moving beyond reliance on feature-space proximity alone. The authors modestly note that future directions include extending this framework to dynamic graphs with evolving topologies.