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

CardsList
  1. Scalable Subgraph Sampling via Resistance Curvature

    Sep 23, 2026Chaoqun Fei, Tinglve Zhou, Tianyong Hao +1Graph Neural NetworksImportance Sampling

  2. Fast Graph Laplacian Estimation using Effective Resistance

    Sep 20, 2026Christoffer Kjellson, Claudio Altafini, Emma TeglingGraph Structure LearningProbabilistic Graphical Models

  3. Moment-guided edge sampling

    Sep 24, 2026Weibin Cai, Reza ZafaraniSpectral Methods