F$^2$LP-AP: 適応的传播核を持つ高速かつ柔軟なラベル-propagation

arXiv:2604.20736v1 発表タイプ：new 摘要：半教師付なノード分類は、グラフ機械学習における基礎的なタスクですが、最上流のグラフニューラルネットワーク（GNN）は顕著な計算コストと強いホモフィリア仮定に依存する課題に直面しています。従来の GNN は高価な反復トレーニングとマルチレイヤーメッセージパスを必要とし、一方、既存のトレーニングフリー方法であるラベル-propagation は非ホモフィリアグラフ構造への適応性に欠けます。本論文では、適応的传播核を持つ高速かつ柔軟なラベル-propagation、すなわち F$^2$LP-AP を提示します。我々の方法は、幾何平均点を介して頑健なクラスプロトタイプを構築し、ローカルクラスタリング係数（LCC）に基づき動的に propagation パラメータを調整することで、勾配ベースのトレーニングなしにホモフィリアグラフと非ホモフィリアグラフの両方を実効的にモデル化します。多岐にわたるベンチマークデータセットにわたる大規模実験において、F$^2$LP-AP はトレーニングされた GNN と同等または superior な精度を示し、かつ既存のベースラインと比較して計算効率的性を著しく凌駕しました。

arXiv:2604.20736v1 Announce Type: new 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.