F\textsuperscript{2}LP-AP: Fast \& Flexible Label Propagation with Adaptive Propagation Kernel

• URL: http://arxiv.org/abs/2604.20736v1
• Date: Wed, 22 Apr 2026 16:23:17 GMT
• Title: F\textsuperscript{2}LP-AP: Fast \& Flexible Label Propagation with Adaptive Propagation Kernel
• Abstract summary: textbfF$2$LP-AP is a training-free, computationally efficient framework that adapts to local graph topology.<n>textbfF$2$LP-AP achieves competitive or superior accuracy compared to trained GNNs.
• Score: 6.834330245672611
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semi-supervised node classification is a foundational task in graph machine learning, yet state-of-the-art Graph Neural Networks (GNNs) are hindered by significant computational overhead and reliance on strong homophily assumptions. Traditional GNNs require expensive iterative training and multi-layer message passing, while existing training-free methods, such as Label Propagation, lack adaptability to heterophilo\-us graph structures. This paper presents \textbf{F$^2$LP-AP} (Fast and Flexible Label Propagation with Adaptive Propagation Kernel), a training-free, computationally efficient framework that adapts to local graph topology. Our method constructs robust class prototypes via the geometric median and dynamically adjusts propagation parameters based on the Local Clustering Coefficient (LCC), enabling effective modeling of both homophilous and heterophilous graphs without gradient-based training. Extensive experiments across diverse benchmark datasets demonstrate that \textbf{F$^2$LP-AP} achieves competitive or superior accuracy compared to trained GNNs, while significantly outperforming existing baselines in computational efficiency.

Related papers

• Subgraph Filtering for Fair Graph Neural Networks [4.075849063907074]
  Graph neural networks (GNNs) can exhibit unfair behavior even when sensitive attributes are excluded from node features.<n>We propose Subgraph Filtering for Fair Graph Neural Networks (SF-GNN)<n>SF-GNN identifies bias-prone edges by combining sensitive homophily with structural propagation amplifiers.<n>It then incorporates edge filtering into each message-passing step to selectively downweight or remove these edges while preserving the remaining graph structure.
  arXiv  Detail & Related papers  (2026-08-26T22:40:31Z)
• Interpretable and Adaptive Node Classification on Heterophilic Graphs via Combinatorial Scoring and Hybrid Learning [1.2691047660244335]
  Graph neural networks (GNNs) achieve strong performance on homophilic graphs but often struggle underphily, where adjacent nodes frequently belong to different classes.<n>We propose an interpretable and adaptive framework for semi-supervised node classification based on explicit inference rather than deep message passing.<n> Experiments on heterophilic and transitional benchmarks demonstrate competitive performance with modern GNNs while offering advantages in interpretability, tuna, and computational efficiency.
  arXiv  Detail & Related papers  (2025-12-22T20:50:44Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  We propose ReDiSC, a structured diffusion model for structured node classification.<n>We show that ReDiSC achieves superior or highly competitive performance compared to state-of-the-art GNN, label propagation, and diffusion-based baselines.<n> Notably, ReDiSC scales effectively to large-scale datasets on which previous structured diffusion methods fail due to computational constraints.
  arXiv  Detail & Related papers  (2025-07-19T04:46:53Z)
• Adaptive Homophily Clustering: Structure Homophily Graph Learning with Adaptive Filter for Hyperspectral Image [21.709368882043897]
  Hyperspectral image (HSI) clustering has been a fundamental but challenging task with zero training labels.<n>In this paper, a homophily structure graph learning with an adaptive filter clustering method (AHSGC) for HSI is proposed.<n>Our AHSGC contains high clustering accuracy, low computational complexity, and strong robustness.
  arXiv  Detail & Related papers  (2025-01-03T01:54:16Z)
• Degree-Conscious Spiking Graph for Cross-Domain Adaptation [51.58506501415558]
  Spiking Graph Networks (SGNs) have demonstrated significant potential in graph classification.<n>We introduce a novel framework named Degree-Consicious Spiking Graph for Cross-Domain Adaptation (DeSGraDA)<n>DeSGraDA enhances generalization across domains with three key components.
  arXiv  Detail & Related papers  (2024-10-09T13:45:54Z)
• Chasing Fairness in Graphs: A GNN Architecture Perspective [73.43111851492593]
  We propose textsfFair textsfMessage textsfPassing (FMP) designed within a unified optimization framework for graph neural networks (GNNs) In FMP, the aggregation is first adopted to utilize neighbors' information and then the bias mitigation step explicitly pushes demographic group node presentation centers together. Experiments on node classification tasks demonstrate that the proposed FMP outperforms several baselines in terms of fairness and accuracy on three real-world datasets.
  arXiv  Detail & Related papers  (2023-12-19T18:00:15Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Bayesian Graph Neural Networks with Adaptive Connection Sampling [62.51689735630133]
  We propose a unified framework for adaptive connection sampling in graph neural networks (GNNs) The proposed framework not only alleviates over-smoothing and over-fitting tendencies of deep GNNs, but also enables learning with uncertainty in graph analytic tasks with GNNs.
  arXiv  Detail & Related papers  (2020-06-07T07:06:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.