cs.LGNov 12, 2026

Feature-Aware Edge Sampling for Approximate One-Step Laplacian Propagation

Authors: Jonathan Z. Sun, Zheng Wang, Kebin Xu

Organizations: Charleston Southern University · University of Miami · College of Charleston

Abstract

This paper studies how to approximate one-step combinatorial Laplacian messages in graph neural networks using edge sampling. We propose a spanning tree based hybrid sampler that combines feature-conditioned message scores and effective-resistance leverage scores, derive the expected one-step message error and obtain the optimal sampling probabilities and error frontier for a given expected edge budget. Preliminary experiments on synthetic community graphs show that message error decreases, while classification accuracy increases slightly, as the edge budget grows, and performance of the hybrid sampler is in between of optimal selection uniform random sampling. We leave multi-step propagation and evaluation on larger and real graphs for future work.

Figures & tables

Explore similar work

Sep 23, 2026

Scalable Subgraph Sampling via Resistance Curvature

Subgraph sampling reduces the training cost of large-scale graph neural networks, but sampling criteria may overlook the geometric roles of edges. We propose a resistance-curvature-guided sampling framework built on ERC-LG, a curvature approximation method for large-scale graphs. ERC-LG combines Johnson-Lindenstrauss projections with regularized multi-GPU batched conjugate gradient solvers, avoiding explicit Laplacian pseudoinverse computation and full embedding storage. The resulting curvature informs node- and edge-sampling probabilities for constructing GNN training subgraphs. Experiments show numerical agreement with pseudoinverse-based curvature and reduced runtime compared with CG-only computation. ERC-LG-based sampling variants achieve the highest mean accuracy on six of seven real-world datasets in downstream node classification.
Sep 20, 2026

Fast Graph Laplacian Estimation using Effective Resistance

Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.
Sep 24, 2026

Moment-guided edge sampling

Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This creates a fundamental challenge: how can the effect of a local edge edit (i.e., edge addition or removal) on global graph structure be quantified and controlled? We address this challenge with a moment-guided edge sampling framework based on spectral moments of the random-walk transition matrix. We compute exact moment changes through two complementary methods: a combinatorial method with closed-form updates for low-order moments, and a low-rank method that exploits locality and cyclic trace invariance to compress computations to edited endpoints, supporting arbitrary moment orders and batched edits. For single-edge edits at fixed moment orders, the low-rank method reduces the cost from O(mn)O(mn) to O(m)O(m), while the combinatorial method evaluates low-order changes in constant time given maintained local statistics. These moment changes provide interpretable structural signatures of local edge motifs that aggregate into graph-level fingerprints. This structural meaning motivates us to ask whether preserving moments also preserves the graph properties. We further derive and validate that moment-preserving sampling can retain related structural properties, including triangle-weighted clustering coefficient. These structural insights enable analysis and improvement of graph learning: different edge structures have distinct effects on supervised node classification, while moment-guided augmentation is competitive for graph contrastive learning. Together, these findings establish moments as an interpretable and controllable bridge from local edge edits to global graph structure and learning.