arXiv CSopen access

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

F2 LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

arXiv:2604.20736v1 [cs.LG] 22 Apr 2026

Beijing University of Technology *Corresponding author

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 trainingfree methods, such as Label Propagation, lack adaptability to heterophilous graph structures. This paper presents F2 LP-AP (Fast and Flexible Label Propagation with Adaptive Propagation Kernel), a trainingfree, 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 gradientbased training. Extensive experiments across diverse benchmark datasets demonstrate that F2 LP-AP achieves competitive or superior accuracy compared to trained GNNs, while significantly outperforming existing baselines in computational efficiency. Our code will be found at https: //anonymous.4open.science/r/F2LP-AP-C811 Keywords: Training-free node classification, Adaptive propagation, Heterophily adaptation, Computational efficiency, Geometric median prototype.

1

Introduction

Semi-supervised node classification is a foundational task in graph machine learning with broad applications in social networks and bioinformatics [11, 18]. Graph Neural Networks (GNNs), such as GCNs and GATs, have become the mainstream approach by utilizing message-passing mechanisms to aggregate neighborhood information [28, 30]. However, as graph scales expand and application scenarios become more complex, traditional GNNs face two critical bottlenecks in practical deployment. The first is computational efficiency. Most GNNs rely on gradient-based iterative training and backpropagation, which demand substantial GPU memory and time on large-scale graphs [36, 22]. While techniques like graph coarsening offer acceleration, they often sacrifice expressive power. The second is the

2

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

Fig. 1. Adaptive vs. Uniform Propagation. (Left) Uniform Propagation: Traditional GNNs and Label Propagation (LP) employ fixed rules or global parameters, often overlooking granular local structures and gradient-driven constraints. (Right) Adaptive Propagation (F2 LP-AP): By leveraging the Local Clustering Coefficient (LCC), our method dynamically tunes node-specific propagation settings, ensuring precise adaptation to both homophilous and heterophilous neighborhoods.

structural homophily assumption. Traditional GNNs implicitly assume that connected nodes share similar labels [6, 38, 20, 40]. While effective in homophilic graphs, this assumption leads to severe performance degradation in heterophilic graphs (e.g., fraud networks) where connected nodes are often dissimilar. Existing attempts to mitigate this through adaptive weighting still largely depend on expensive supervised training [24, 37]. To address these challenges, training-free methods have gained attention for their ability to avoid optimization overhead. However, classical Label Propagation (LP) and feature-smoothing approaches typically adopt fixed propagation strategies [7, 16]. These methods fail to adapt to local node structures, resulting in over-smoothing in dense communities or noise amplification in heterophilic regions. To this end, we propose F2 LP-AP (Free-from-training Label Propagation with Adaptive Propagation), a novel training-free framework. By introducing an adaptive propagation kernel based on local clustering coefficients, our method enables personalized information propagation without gradient optimization. Combined with a geometric median-based prototype construction and metric-based classification, it enhances robustness to heterophily and noise while maintaining high inference efficiency. The main contributions of this paper are summarized as follows: – Structure-Adaptive Mechanism: We propose a propagation kernel that mitigates over-smoothing in homophilic regions and noise in heterophilic structures. – Robust Pipeline: We design a prototype construction and classification workflow that completely avoids parameter optimization. – Efficiency and Generality: We achieve training-free inference that performs comparably to mainstream GNNs while providing significant speedups across multiple benchmarks.

F2 LP-AP

2

Related Work

2.1

Decoupled GNNs and Label Propagation

3

Decoupled Graph Neural Networks aim to separate feature transformation from the message-passing process to enhance computational efficiency on large-scale graphs [33, 5]. Currently, mainstream methods like APPNP leverage the Personalized PageRank (PPR) mechanism to redistribute features through fixed iteration counts K and teleport probabilities α [19, 34, 21]. In this domain, there exist both classical training-free baselines, such as Label Propagation (LP), and recent attempts like TFGNN that introduce training-free mechanisms by utilizing labels as features [27, 7]. However, these methods generally suffer from a lack of computational flexibility: traditional GNNs rely on heavy backpropagation, while existing training-free approaches often merely shift the computational burden and remain rigid in their propagation schemes by applying uniform aggregation rules to all nodes [39]. Our F2 LP-AP addresses the contradiction between computational overhead and structural rigidity by introducing a three-stage analytical pipeline that completely eliminates gradients and dynamically adjusts propagation parameters based on the Local Clustering Coefficient (LCC). 2.2

Adaptivity to Graph Homophily and Heterophily

Learning algorithms for graphs must possess the capability to handle diverse topological structures, accommodating both homophilous graphs (where connected nodes share similar labels) and heterophilous graphs (where linked nodes belong to different classes) [26]. Current mainstream methods typically rely on global learned parameters or complex attention mechanisms to capture structural variations, such as GPR-GNN, which decouples propagation via learned weights [8, 15]. Existing literature includes improvements like GraphSAGE, which assumes strong homophily, and methods like GPR-GNN or APPNP that strive for robustness across broader scenarios [8, 12, 13]. Yet, these methods face a distinct “homophily bottleneck” as their parameters are often global or require training, failing to achieve granular, node-wise adaptive adjustment [17]. This leads to drastic performance degradation on complex graphs with mixed structures. F2 LP-AP bridges this gap by coupling the propagation kernel with the Local Clustering Coefficient (LCC), enabling node-level adaptivity where the algorithm automatically determines the degree of “trust” in neighbors based on local density, thus balancing homophilous and heterophilous regions without any training. 2.3

Robust Prototype Representation Learning

The core of prototype representation learning lies in constructing stable and representative class centers to serve as benchmarks for downstream classification tasks [3]. Most mainstream approaches employ the arithmetic mean of features as class prototypes and incorporate supervised training with a Softmax

4

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

layer [25, 23, 32]. While some methods have begun exploring metric learning for node classification, most implementations remain vulnerable to noise or outliers in real-world data [14, 10]. Such mean-based prototype construction is highly susceptible to interference from “straggler” nodes or mislabeled examples, causing the classification baseline to shift and compromising predictive accuracy [29, 4, 2]. In contrast, F2 LP-AP employs a robust prototype construction scheme based on the Geometric Median and performs analytical classification via cosine distance. This significantly enhances the system’s resistance to data noise and anomalies, providing a solid foundation for accurate classification in a trainingfree environment.

3

Method

3.1

Overview of F2 LP-AP Pipeline

In this section, we present the overall framework of the proposed F2 LP-AP. Given a graph G = (V, E) with an associated node feature matrix X ∈ Rn×d where n = |V|, let VL ⊂ V denote the set of training nodes with labels YL . The core philosophy of F2 LP-AP is to construct a predictive pipeline that is entirely decoupled from gradient-based training and capable of adaptive evolution based on local topological structures. The entire framework consists of three tightly coupled stages. The first stage involves Robust Prototype Construction. Instead of using arithmetic means which are susceptible to noise, we derive the cluster center for each class by computing the geometric median of the training features: Pc = arg min µ

X

∥xi − µ∥2

(1)

vi ∈VL,c

where Pc denotes the robust prototype for class c. This is followed by the core Adaptive Feature Propagation stage. Departing from the limitation of globally uniform parameters in traditional methods, we introduce the Local Clustering Coefficient (LCC) as a structure-aware indicator to dynamically map individualized propagation parameters for each node vi : ϕ : LCCi → {Ki , αi }

(2)

This mapping mechanism enables the model to achieve precise feature smoothing control for both homophilous regions (high LCC) and heterophilous regions (low LCC). Finally, the features X̂ transformed by the adaptive kernel enter the Analytical Classification stage. We generate the final predictions by directly calculating the cosine similarity between the evolved node representations and the class prototypes: x̂i · Pc (3) ŷi = arg max ∥x̂ i ∥∥Pc ∥ c∈{1,...,C}

F2 LP-AP

5

Unlike conventional Graph Convolutional Networks, all computational steps in F2 LP-AP consist of deterministic algorithms, completely eliminating the burdensome backpropagation process. Such an analytical design not only grants the model superior inference efficiency but also endows it with intrinsic topological robustness through node-wise adaptive adjustment. 3.2

Robust Prototype Construction

Following the initial representation of the graph, the primary objective is to establish stable reference points for each class. Traditional paradigms typically rely on the weight matrices of linear layers or simple arithmetic means to represent class centers. However, these approaches are inherently fragile when encountering feature noise or structural outliers common in real-world graph data. To mitigate this, F2 LP-AP constructs the class prototypes Pc by solving for the geometric median as defined in Eq. (1). Unlike the arithmetic mean, which minimizes the sum of squared Euclidean distances, the geometric median is robust against extreme outliers. From a statistical perspective, while the arithmetic mean shifts drastically towards outliers, the geometric median possesses a breakdown point of up to 50%. This implies that as long as the majority of nodes in a class maintain a consistent distribution, the resulting prototype Pc will remain anchored at the true manifold center of the class. Since Eq. (1) represents a non-differentiable optimization problem, we derive the solution using the Weiszfeld algorithm, an iterative re-weighted least squares procedure. In the k-th iteration, the class prototype and its corresponding weights are updated simultaneously as follows: X  (k+1) (k) = Pc wi xi     vi ∈VL,c  (4) (k)  ∥xi − Pc ∥−1  (k) 2   wi = P (k) −1 vj ∈VL,c ∥xj − Pc ∥2 As illustrated by the derivation, the contribution of each training node is inversely proportional to its distance from the current center. This weighting mechanism naturally suppresses the influence of noisy nodes distant from the cluster core, thereby ensuring the purity of the prototype Pc . In practice, this iterative process typically converges within 3 to 5 iterations. Its computational complexity scales linearly with the feature dimension, which is substantially lower than any gradient-based optimization cost. The resulting set of robust prototypes P = {P1 , . . . , PC } serves as a collection of reliable ”anchors” for the subsequent adaptive propagation stage, ensuring high performance even in the presence of label noise. 3.3

Node-wise Adaptive Propagation

Upon establishing the robust class prototypes P, it is essential to capture highorder dependencies within the graph topology through an effective feature prop-

6

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

Algorithm 1: F2 LP-AP Inference Procedure Input: G(V, E), X ∈ Rn×d , VL = Output: ŷ ∈ {1, . . . , C}n .

SC

c=1 VL,c , Hyperparameters θ = {fα , gK }.

(k+1)

∀c ∈ {1, . . . , C} : Pc = GM(XVL,c ) via Pc

=

(k)

∥xi −Pc ∥−1 xi ; P (k) ∥xi −Pc ∥−1

P

θ

i| − → {αi , Ki }; ∀vi ∈ V : LCCi = di 2|E (di −1)

H(0) = X; for k = 0 to max(Ki ) − 1 do H(k+1) = (I − diag(α))ÃH(k) + diag(α)X; (k+1) ∀i s.t. Ki = k + 1 : x̂i = hi ; S = L2Norm(X̂out ) · L2Norm(P)⊤ ∈ Rn×C ; ∀vi ∈ V : ŷi = arg maxc Si,c ; return ŷ

agation mechanism. Conventional decoupled Graph Neural Networks (GNNs), such as APPNP, typically employ globally uniform propagation parameters, which often overlook the significant diversity of local structures in real-world graph data. To address this, F2 LP-AP introduces an adaptive propagation mechanism centered on the Local Clustering Coefficient (LCC), utilizing topological signatures to dynamically guide the information flow. The LCC measures the degree to which triangles are closed in a node’s neighborhood, effectively reflecting the local topological environment. For any node vi ∈ V, the LCC is defined as: LCCi =

2|Ei | di (di − 1)

(5)

where di denotes the degree of node vi and |Ei | represents the number of actual edges between its neighbors. A high LCCi typically indicates that a node resides within a dense, homophilous community, whereas a low LCCi suggests that the node is situated at a topological boundary or an interface of heterophilous connections. To balance the preservation of local features with the assimilation of global structural information, we construct mapping functions that bridge the gap between LCCi and the propagation dynamics, specifically the depth Ki and the teleport probability αi . Regarding the propagation depth Ki , nodes in dense clusters (high LCC) can achieve information aggregation through fewer steps, while nodes in sparse regions (low LCC) require deeper propagation to acquire sufficient contextual information. Simultaneously, for the teleport probability αi , we decrease αi in highly homophilous regions to allow for more thorough feature smoothing, while increasing αi in regions with high heterophily risk to retain the node’s intrinsic feature anchors. The joint mapping system is formulated as follows:

F2 LP-AP

  αi = σ(fα (LCCi ))  

7

(6)

Ki = round(gK (LCCi ))

where fα and gK are predefined heuristic functions that require no parametric training. Based on the generated node-wise parameter set {αi , Ki }ni=1 , the initial feature matrix X is transformed into the final predictive representation X̂. In this phase, the state evolution of each node follows a personalized iterative path: (k+1)

hi

= (1 − αi ) · Ãi,: H(k) + αi · xi

(7)

where à denotes the normalized adjacency matrix, and the iteration terminates upon reaching the node-specific depth Ki . This mechanism ensures that each node can adapt its degree of feature smoothing ”according to local conditions” based on its structural role in the graph. By significantly enhancing the model’s adaptability to complex graph structures without adding any training overhead. 3.4

Analytical Inference and Label Assignment

Following the topology-aware adaptive feature propagation, each node vi obtains an evolved representation x̂i that encapsulates local structural characteristics. To achieve the final label assignment, these evolved features must be mapped back to the discrete label space. Unlike conventional deep learning models that rely on linear layers or Softmax functions with learnable parameters, F2 LP-AP employs a purely analytical matching mechanism. This process is formalized as finding the optimal alignment between node representations and the robust class prototypes P ∈ RC×d on the feature manifold. To eliminate potential bias caused by variance in feature vector magnitudes and to focus on the alignment of high-dimensional semantic directions, we define the prediction logic through a normalized inner product. Let X̂out ∈ Rn×d denote the evolved feature matrix for all nodes. The final confidence score matrix S ∈ Rn×C is derived in the following matrix form:    ⊤ − 21 ⊤ − 12 S = diag(X̂out X̂⊤ ) X̂ P · diag(PP ) out out

(8)

Each entry Si,c essentially represents the cosine similarity between node vi and the prototype of class c projected onto a hypersphere. This analytical formulation avoids the exponential computational overhead of Softmax operations on largescale graphs. Furthermore, by enforcing geometric consistency in the feature space through non-parametric alignment, it effectively suppresses representation collapse, particularly in label-scarce scenarios. Upon obtaining the confidence matrix S, the final discrete label for each node is determined by applying a maximization operator across the class dimension.

8

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

This process involves no re-parameterization of probability distributions but rather a hard assignment based on geometric membership: ŷi = arg

max c∈{1,...,C}

Si,c

(9)

This closed-form assignment mechanism ensures that F2 LP-AP maintains superior computational efficiency while exhibiting intrinsic model robustness. Since the entire inference pipeline, from the robust estimation of prototypes, is independent of gradient updates, the algorithm demonstrates significantly stronger generalization stability than traditional parametric GNNs when handling structurally noisy or dynamically evolving graph data.

4

Experiments

4.1

Experimental Setup

Datasets and Benchmarks. To comprehensively evaluate the robustness of F2 LP-AP across diverse topological properties, we select eight representative graph datasets. Following the standard literature, these datasets are categorized into two groups based on their homophily ratios: (1) Strongly homophilous networks (Cora, CiteSeer, and PubMed ), where the probability of nodes sharing labels with their neighbors exceeds 0.8; and (2) Heterophilous networks (Texas, Wisconsin, Cornell, Chameleon, and Squirrel ), with homophily ratios below 0.4. This selection spans various domains, including citation networks, WebKB, and Wikipedia pages, with scales ranging from hundreds to tens of thousands of nodes, aiming to stress-test the model’s generalization capability under extreme structural polarization. [35, 1, 26] Baselines. We compare F2 LP-AP against seven competitive baselines across several technical trajectories: – Prototypical Learning Variants: Includes standard mean prototypes (PrototypeOnly-Mean), geometric median prototypes (PrototypeOnly-GeoMed) without propagation, and a non-adaptive variant utilizing fixed-parameter APPNP (FixedAPPNP-Proto). These methods are regarded as ablation comparison. – Classical and SOTA Models: Covers the representative Graph Convolutional Network (GCN), traditional non-parametric methods (LabelPropagation and kNN), and the state-of-the-art (SOTA) GNN-free baseline (CoHOp). [31, 18, 41, 9] Configurations. All experiments are implemented in PyTorch, with the random seed fixed to 0 to ensure reproducibility. Performance is evaluated using Classification Accuracy and Macro-F1 score. For F2 LP-AP, the number of propagation steps K is constrained within [2, 15], and the teleport probability α is dynamically adjusted within [0.05, 0.2]. All baselines strictly follow the optimal hyperparameter configurations reported in their original papers, and all methods are executed in a unified hardware environment to ensure a fair comparison of computational efficiency.

F2 LP-AP

9

Table 1. Performance comparison on 8 datasets categorized by homophily ratio (H). We report Accuracy (Acc.), Macro-F1 (F1), and Execution Time (Time in seconds). Bold indicates the best performance among training-free/non-parametric methods; underline indicates the overall state-of-the-art (SOTA). ∗ denotes supervised GNN baselines. Dataset Method

Cora (H = .85) CiteSeer (H = .81) PubMed (H = .84) Chameleon (H = .26) Acc. F1 Time Acc. F1 Time Acc. F1 Time Acc. F1 Time

GCN∗ CoHOp

0.821 0.809 1.350 0.719 0.691 0.637 0.635 0.605 0.605 0.575

1.210 0.643

0.798 0.794 1.485 0.561 0.552 0.711 0.702 0.690 0.371 0.288

1.124 0.676

LabelProp 0.710 0.719 0.013 0.483 0.496 kNN@5 0.464 0.458 0.107 0.504 0.498 Proto-GeoMed 0.597 0.575 0.024 0.619 0.596 FixedAPPNP 0.658 0.637 0.039 0.658 0.633 F2 LP-AP 0.835 0.821 0.056 0.708 0.685

0.013 0.135 0.031 0.088 0.092

0.723 0.709 0.646 0.643 0.725 0.728 0.741 0.745 0.782 0.779

0.012 0.139 0.021 0.179 0.089

0.015 0.716 0.027 0.086 0.044

0.331 0.327 0.360 0.342 0.430 0.431 0.414 0.411 0.395 0.391

Dataset Method

Texas (H = .31) Wisconsin (H = .37) Cornell (H = .34) Acc. F1 Time Acc. F1 Time Acc. F1 Time

GCN∗ CoHOp

0.553 0.365 1.015 0.608 0.269 0.421 0.148 0.524 0.490 0.156

1.053 0.536

0.500 0.203 1.014 0.322 0.242 0.579 0.149 0.537 0.248 0.195

2.466 1.348

LabelProp 0.132 0.076 0.013 0.314 0.189 kNN@5 0.684 0.599 0.010 0.804 0.517 Proto-GeoMed 0.842 0.787 0.010 0.706 0.498 FixedAPPNP 0.816 0.759 0.008 0.725 0.514 F2 LP-AP 0.842 0.787 0.016 0.825 0.589

0.013 0.012 0.008 0.011 0.024

0.263 0.202 0.711 0.385 0.763 0.519 0.737 0.503 0.763 0.519

0.022 0.343 0.036 0.987 0.069

4.2

0.013 0.009 0.009 0.011 0.018

Squirrel (H = .23) Acc. F1 Time

0.262 0.253 0.227 0.198 0.303 0.301 0.293 0.290 0.288 0.285

Multi-method Performance Evaluation Across Diverse Graph Homophily Levels

Experimental Evaluation. To assess the generalizability of F2 LP-AP across varying graph topologies, we benchmark our proposed framework against seven mainstream baselines using eight representative datasets. Discussion and Key Insights. As shown in Table 1, experimental results demonstrate that F2 LP-AP exhibits exceptional robustness and generalization capabilities across the entire homophily spectrum. On heterophilous graphs, F2 LP-AP achieves state-of-the-art (SOTA) performance on Texas (0.842), Wisconsin (0.825), and Cornell (0.763), effectively mitigating the performance degradation seen in conventional GNNs like GCN due to over-smoothing. Remarkably, this superiority extends to homophilous environments, where F2 LPAP yields the overall SOTA on Cora (0.835), surpassing even supervised models. Furthermore, it maintains the top performance among all training-free methods on CiteSeer (0.708) and PubMed (0.782). Efficiency-Performance Trade-off. As a training-free framework, F2 LP-AP substantially reduces computational overhead while delivering dominant accuracy. On large-scale networks like PubMed, its inference latency is approximately 3% of that required by GCN, achieving a significant speedup without sacrificing classification precision. Compared to non-adaptive variants like FixedAPPNP and high-complexity baselines such as CoHOp, F2 LP-AP yields superior results across all tested benchmarks, validating the necessity of dynamically adjusting

10

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

Fig. 2. F2 LP-AP Confusion Matrices. Results for Texas (Left), Cora (Center), and CiteSeer (Right). The dark, sharp diagonals confirm robust performance across varying homophily levels.

Fig. 3. The ablation results for prototype computation methods, comparing the geometric median (GeoMedian, blue) and the arithmetic mean (Mean, green) across eight datasets. The results indicate that GeoMedian achieves classification accuracy superior or equivalent to the Mean across all benchmarks. Notably, the performance gains are more pronounced on low-homophily datasets, such as Chameleon, Cornell, and Squirrel, thereby validating its efficacy as a robust prototype estimation strategy.

propagation steps K and teleport probability α. These results position F2 LPAP as a compelling, high-performance solution for graph learning tasks where both accuracy and resource efficiency are paramount. 4.3

Ablation study

Experimental Setup. To rigorously evaluate the efficacy of the core components within F2 LP-AP, we conducted 2 comprehensive sets of ablation studies across all eight benchmark datasets, encompassing a wide spectrum of graph homophily levels and network scales, with classification accuracy serving as the primary evaluation metric. The first set investigates the effectiveness of the adaptive propagation strategy by benchmarking the full F2 LP-AP framework, characterized by its adaptive K and α parameters, against the non-adaptive variant FixedAPPNPProto (with fixed K = 5 and α = 0.1) and the propagation-free baseline PrototypeOnlyGeoMed. The second set validates the robustness of utilizing the geometric median for prototype computation by comparing our proposed PrototypeOnlyGeoMed against PrototypeOnly-Mean, which relies on the

F2 LP-AP

11

Fig. 4. We present the t-SNE visualizations grouped by the Cora and Texas datasets to compare the distributions of the raw features against the features processed by F2 LP-AP. While the raw features exhibit significant overlap and noise, the features refined by F2 LP-AP demonstrate much clearer clustering patterns and tighter intraclass cohesion. This qualitative improvement across both high-homophily (Cora) and low-homophily (Texas) scenarios further validates the capability of our framework to learn more discriminative representations.

standard arithmetic mean for prototype initialization. Collectively, these experiments quantify the performance gains attributed to our structure-aware adaptive strategy and robust prototype estimation across diverse graph topologies. Result. As shown in Table 1, the ablation studies across eight datasets yield the following insights: (1) High-Homophily Scenarios: F2 LP-AP consistently outperforms non-adaptive baselines. Specifically, on Cora, it achieves an accuracy of 0.835, representing a significant improvement of 26.9% and 39.9% over FixedAPPNP and Proto-GeoMed, respectively. Similar trends are observed on CiteSeer and PubMed, with gains reaching up to 14.4% and 7.9%, validating the advantage of adaptive propagation in smooth topologies. (2) Low-Homophily Scenarios: Our framework demonstrates superior adaptability in complex structures, outperforming FixedAPPNP by 13.8% on Wisconsin, while matching the state-of-the-art performance of Proto-GeoMed on Texas. (3) Efficiency: Despite the dynamic parameter adjustment, the execution time of F2 LP-AP (0.016s–0.089s) remains within a reasonable range, incurring only a marginal increase compared to FixedAPPNP and thus achieving an optimal trade-off between performance and computational overhead. As shown in Figure 3 and Table 1, the ablation results demonstrate that the geometric median consistently outperforms the arithmetic mean across all eight datasets, with an average accuracy improvement of 5.8%, particularly showing more pronounced gains on low-homophily datasets such as Chameleon (12.8%) and Squirrel (14.3%), thereby validating its superior robustness and versatility as a prototype estimation method. 4.4

Impact of Graph Homophily on Performance Stabilit

Experimental Design. To quantify the influence of graph homophily on the classification efficacy and robustness of F2 LP-AP, we evaluate the framework across eight datasets with varying homophily levels. We report the mean accuracy and standard deviation (σ) over 10 independent runs to assess stability.

12

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

Table 2. Performance and stability analysis of F2 LP-AP. H denotes the homophily ratio. Category

Dataset

Hom. (H)

Accuracy (µ ± σ)

High-H.

Cora CiteSeer PubMed

0.85 0.81 0.84

0.835 ± 0.004 0.708 ± 0.006 0.782 ± 0.002

Low-H.

Texas Wisconsin Chameleon Cornell Squirrel

0.31 0.37 0.26 0.34 0.23

0.842 ± 0.012 0.825 ± 0.011 0.395 ± 0.015 0.763 ± 0.013 0.288 ± 0.018

The standard deviation, serving as the core metric for dispersion, is defined as: v u n u1 X σ=t (xi − µ)2 (10) n i=1 where xi denotes the accuracy of each individual run, µ represents the mean accuracy, and n is the total number of experimental trials. Result. The experimental results, summarized in Table 2, demonstrate that F2 LP-AP maintains exceptional performance and stability across the entire homophily spectrum. In high-homophily scenarios (e.g., Cora), the framework exhibits minimal variance (σ = 0.004), confirming the consistency of our adaptive propagation in smooth topologies. In extreme low-homophily settings (e.g., Texas), despite a slight increase in dispersion (σ = 0.012) due to structural complexity, the mean accuracy remains remarkably high at 0.842. The combination of low volatility and high predictive accuracy underscores the effectiveness of our structure-aware strategy in mitigating heterophilous noise and providing reliable classifications regardless of graph topology.

5

Parameter Sensitivity Analysis

Experimental Design. To systematically evaluate the performance stability and parameter sensitivity of the proposed F2 LP-AP model, we conduct an extensive sensitivity analysis. Two benchmark datasets with distinct network properties are selected: Cora, a high-homophily citation network (0.8488), and Texas, a low-homophily WebKB dataset (0.3078). This selection ensures a robust assessment of model adaptability across diverse topological structures. We focus on four pivotal hyper-parameters: the propagation step range (Kmin , Kmax ) and the diffusion coefficient range (αmin , αmax ). Specifically, a grid search is performed over Kmin ∈ {1, 2, 3}, Kmax ∈ {5, 10, 15}, αmin ∈ {0.05, 0.1}, and αmax ∈ {0.1, 0.2}. Following a 60/20/20 train-validation-test split, we report

F2 LP-AP

13

Fig. 5. Parameter sensitivity analysis of F2 LP-AP. The left panel illustrates the performance growth trend on the Cora dataset as the maximum propagation steps Kmax increases, where different line styles denote varying minimum constraints Kmin . The right panel presents the accuracy fluctuations on the Texas dataset, clearly highlighting the impact of the diffusion coefficient range [αmin , αmax ] on model efficacy.

accuracy, Macro-F1 score, and execution time. All experiments are executed in a controlled hardware environment to ensure rigorous comparability. Results Analysis. The empirical results demonstrate that F2 LP-AP exhibits substantial robustness while revealing distinct sensitivity patterns across datasets. On the Cora dataset, performance scales positively with parameter complexity, peaking at an accuracy of 83.60% and a Macro-F1 of 81.54%. This suggests that in homophilous networks, broader propagation horizons and diffusion ranges effectively capture informative structural dependencies. Conversely, the Texas dataset exhibits higher stability, with accuracy fluctuating minimally between 81.58% and 84.21%. The performance plateau in Texas indicates that for smaller, heterophilous networks, the model is less sensitive to parameter variations but benefits from a constrained αmax (0.1), highlighting the computational efficiency and scalability of the proposed method. Optimal Parameter Configurations. Synthesizing the results, the optimal parameter configuration for F2 LP-AP is identified as Kmin = 3, Kmax = 15, αmin = 0.1, αmax = 0.2. This setting achieves peak performance on Cora while maintaining high-tier accuracy on Texas. Such a configuration effectively balances local fine-grained information with global topological context by calibrating the lower and upper bounds of propagation and diffusion. Consequently, this optimal setup enhances the model’s generalization capabilities and classification efficacy across varied complex network environments.

6

Conclusion

This paper presents F 2 LP -AP , a training-free framework that achieves adaptive propagation via the Local Clustering Coefficient (LCC), effectively balanc-

14

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

ing performance and efficiency across homophilous and heterophilous graphs. Despite its efficacy, the model has limitations: the adaptive mechanism relies on the single metric LCC, which may compromise precision in extremely sparse or noisy structures. Furthermore, the heuristic mapping functions are not datadriven, and the performance upper bound remains constrained by the quality of raw features and empirical hyper-parameter settings. Future work will explore multi-dimensional structural descriptors and lightweight learning mechanisms to further enhance generalization.

References 1. Webkb datasets (cornell, texas, wisconsin). https://www.cs.cmu.edu/afs/cs. cmu.edu/project/theo-20/www/data/ 2. Abbahaddou, Y., Malliaros, F.D., Lutzeyer, J.F., Vazirgiannis, M.: Admp-gnn: Adaptive depth message passing gnn. In: Proceedings of the 34th ACM International Conference on Information and Knowledge Management (CIKM) (2025) 3. Chen, L., Song, Y., Cai, Y., Lu, J., Li, Y., Xie, Y., Wang, C., He, G.: Multiprototype space learning for commonsense-based scene graph generation. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). vol. 38, pp. 1129–1137 (2024) 4. Chen, W., Li, S., Yu, X., Wang, H., Chen, W., Wang, T.: Automatic de-biased temporal-relational modeling for stock investment recommendation. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI). pp. 1999–2008 (2024) 5. Chen, X., Zhou, J., Chen, J., Yu, S., Xuan, Q.: Mixture of experts meets decoupled message passing: Towards general and adaptive node classification. In: Proceedings of the ACM Web Conference (WWW) (2025) 6. Chen, Y., Yang, C., Wang, Y., Guo, Y., Shi, Q., Wang, X., Zhang, Y., Shen, C.: What is missing in homophily? disentangling graph homophily for graph neural networks. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 36 (2023) 7. Cheng, Y., et al.: Resurrecting label propagation for graphs with heterophily and label noise. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (2024) 8. Chien, E., Peng, J., Li, P., Milenkovic, O.: Adaptive universal generalized pagerank graph neural network. In: International Conference on Learning Representations (ICLR) (2021) 9. Cover, T., Hart, P.: Nearest Neighbor Pattern Classification, vol. 13 (1967) 10. Ding, P., Chen, J., Dai, H., Zhu, J.: MGU: Re-understanding Graph Unlearning through Memorization. In: Proceedings of the ACM Web Conference 2026 (WWW ’26). pp. 1–12 (2026) 11. Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., Yin, D.: Graph neural networks for social recommendation. In: The World Wide Web Conference (WWW). pp. 417–426. ACM (2019) 12. Gasteiger, J., Bojchevski, A., Günnemann, S.: Predict then propagate: Graph neural networks meet personalized pagerank. In: International Conference on Learning Representations (ICLR) (2019)

F2 LP-AP

15

13. Hamilton, W.L., Ying, R., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems (NeurIPS). pp. 1024–1034 (2017) 14. Hayler, A., Bießmann, F., Harmeling, S., Pascual, D.: TabGFM: Of Graphs and Tables: Zero-Shot Node Classification with Tabular Foundation Models. In: Advances in Neural Information Processing Systems 37 (NeurIPS 2025) (2025) 15. He, M., Wei, Z., Wen, J.R.: Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 34, pp. 14239–14251 (2021) 16. Huang, Q., He, H., Singh, A., Lim, S., Benson, A.R.: Combining label propagation and simple models out-performs graph neural networks. In: International Conference on Learning Representations (ICLR) (2021) 17. Huang, S., Song, Y., Zhou, J., Lin, Z.: Cluster-wise graph transformer with dualgranularity kernelized attention. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 37 (2024) 18. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: International Conference on Learning Representations (ICLR) (2017) 19. Klicpera, J., Bojchevski, A., Günnemann, S.: Predict then propagate: Graph neural networks meet personalized pagerank. In: International Conference on Learning Representations (ICLR) (2019) 20. Li, W., Li, Q., Wu, X., Chen, H., He, Y., Zhang, F., Pan, S.: Classic gnns are strong baselines: Reassessing gnns for node classification. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 37 (2024) 21. Liu, M., Gao, H., Ji, S.: Towards deeper graph neural networks. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 33, pp. 15775–15785 (2020) 22. Liu, Z., Zhou, K., Yang, F., Li, L., Chen, R., Hu, X.: Exact: Scalable graph neural networks training via extreme activation compression. In: International Conference on Learning Representations (ICLR) (2022) 23. Lu, Z., Yang, Y., Zhu, X., Liu, C., Song, Y.Z., Xiang, T.: Stochastic classifiers for unsupervised domain adaptation. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 9111–9120 (2020) 24. Luan, S., Zhang, X., Di, S., Shi, Z., Zhou, D., Chen, G.: Re-evaluating the advancements of heterophilic graph learning. In: Advances in Neural Information Processing Systems (NeurIPS) (2025) 25. Luo, Y., Wang, Z., Huang, Z., Baktashmotlagh, M.: Progressive graph learning for open-set domain adaptation. In: International Conference on Machine Learning (ICML). pp. 6468–6478. PMLR (2020) 26. Platonov, O., Kuznedelev, D., Babenko, A., Prokhorenkova, L.: Characterizing graph datasets for node classification: Homophily-heterophily dichotomy and beyond. In: Advances in Neural Information Processing Systems (NeurIPS) (2023) 27. Sato, R.: Training-free graph neural networks and the power of labels as features. Transactions on Machine Learning Research (2024) 28. Sun, J., Yang, C., Ji, X., Huang, Q., Wang, S.: Towards dynamic message passing on graphs. In: Advances in Neural Information Processing Systems (NeurIPS) (2024) 29. Tian, H., Chen, Y., Wang, X., Chen, J., Li, H., Wang, Z.: Mind the gap between prototypes and images in cross-domain finetuning. vol. 37 (2024) 30. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks. In: International Conference on Learning Representations (ICLR) (2018)

16

Yutong Shen*, Ruizhe Xia, Jingyi Liu, Yinqi Liu

31. Wang, H., Shi, C., Xu, C., Yan, S., Xie, R., Tang, P.: Enhancing homophily in heterogeneous graph contrastive learning via connection strength and multi-view self-expression. In: Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’25) (2025) 32. Wang, Y., Huang, W., Sun, F., Xu, T., Rong, Y., Huang, J.: Deep multimodal fusion by channel exchanging. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 34, pp. 193–205 (2021) 33. Wei, T., Li, Z., Wang, Z., et al.: Dpar: Decoupled graph neural networks with nodelevel differential privacy. In: Proceedings of the ACM Web Conference (WWW). pp. 1170–1181 (2024) 34. Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., Weinberger, K.: Simplifying graph convolutional networks. In: International Conference on Machine Learning (ICML). pp. 6861–6871 (2019) 35. Yang, Z., Cohen, W.W., Salakhutdinov, R.: Revisiting semi-supervised learning with graph embeddings. In: ICML (2016) 36. Yu, H., Wang, L., Wang, B., Liu, M., Yang, T., Ji, S.: Graphfm: Improving largescale gnn training via feature momentum. In: International Conference on Machine Learning (ICML). pp. 25684–25701. PMLR (2022) 37. Zhang, S., Wang, H., Lin, J., Li, P., Liu, J., Wang, X.: Herofilter: Adaptive spectral graph filter for varying heterophilic relations. In: International Conference on Learning Representations (ICLR) (2025) 38. Zhao, T., Wang, X., Yang, X., Zhang, D., Sui, K., Jiang, Y.: Opengsl: A comprehensive benchmark for graph structure learning. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 36 (2023) 39. Zhao, Y., Liu, Y., Li, S., Chen, Q., Zheng, Y., Pan, S.: Freegad: A training-free yet effective approach for graph anomaly detection. In: Proceedings of the 34th ACM International Conference on Information and Knowledge Management (CIKM) (2025) 40. Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., Koutra, D.: Beyond homophily in graph neural networks: Current limitations and effective designs. In: Advances in Neural Information Processing Systems (NeurIPS). vol. 33, pp. 7793–7804 (2020) 41. Zhu, X., Ghahramani, Z.: Learning from labeled and unlabeled data with label propagation. Tech. rep., Carnegie Mellon University (2002), technical Report