Heterophily-Aware Personalized PageRank for Node Classification

1 Introduction

Node classification in heterophilous graphs-where linked nodes often exhibit significant dissimilarity in their attributes or class labels-poses unique challenges [Luan et al., 2024]. For example, in a citation network, a groundbreaking paper might be most relevant to works that challenge or diverge from its approach rather than similar papers. The inherent structure of heterophilous graphs presents a key challenge for graph-based learning. A fundamental question emerges:

Can we identify truly relevant neighbors for a node when traditional proximity-based assumptions break down?

Related Work. Research in heterophilous graphs has received significant attention [Luan et al., 2024; Zheng et al., 2022; Platonov et al., 2023b]. Below, we categorize existing approaches most related to our work following Table 1.

1. Multi-hop view: These methods leverage multi-hop neighborhood information. H2GCN [Zhu et al., 2020] separates ego and neighbor embeddings, while FSGNN [Maurya et al., 2022] guides aggregation through feature similarity.
2. Global Homophily: These approaches exploit global graph properties. GloGNN [Li et al., 2022] integrates globallocal information, CPGNN [Zhu et al., 2021] uses compatibility matrices, Geom-GCN [Liu et al., 2021] leverages geometric relationships, and GPNN [Yang et al., 2022] learns neighbors via attention.
3. Discriminative Message Passing: Methods like FAGCN [Bo et al., 2021] and GBK-GNN [Du et al., 2022] focus on adaptive edge-aware techniques and bi-kernel transformations respectively.
4. New Neighbours: Instead of using only original connections, NLGNN [Liu et al., 2021] and OGNN [Pirr`o, 2023] identify non-local neighbours via learnable node orderings.
5. Spectral Approaches: These methods employ various spectral techniques: GPR-GNN [Chien et al., 2021] uses adaptive PageRank weights, BernNet [He et al., 2021] , JacobiConv [Wang and Zhang, 2022], and ChebNetII [He et al., 2022] leverage different types of polynomial filtering.
6. Adaptive Approaches: These methods dynamically adjust to graph properties. Restruct-GCN [Li et al., 2023] learns topology restructuring, ACM-GCN [Luan et al., 2022] adapts frequency bands, ASCG [Chanpuriya and Musco, 2022] uses heterophily-aware coefficients, CDE [Zhao et al., 2023] employs cross-feature diffusion, ACMP [Wang et al., 2023] uses interactive particle systems, and HeterGCL [Wang et al., 2024] applies graph contrastive learning.

Limitations of Existing Approaches. Despite considerable progress, each category of heterophilous graph methods faces specific challenges. Multi-hop view approaches often struggle with computational complexity as the hop count increases.

Global Homophily methods can overlook local structural patterns while introducing significant memory overhead. Discriminative Message Passing techniques require careful feature engineering and often lack theoretical guarantees. New Neighbours strategies introduce computational cost in neighbor discovery and rely heavily on domain-specific heuristics. Spectral methods demand non-trivial parameter tuning for filter orders and can miss localized graph properties. Adaptive approaches typically require complex architectures.

Our Proposal. We introduce HAPPY (Heterophily-Aware Personalized PageRank), which builds upon a key insight: in heterophilous graphs, influential nodes might not be immediate neighbors, but rather nodes that share similar patterns across multiple hops. This observation makes Personalized PageRank (PPR) [Haveliwala, 2002] an attractive foundation, as it naturally measures node importance through random walks while allowing for personalization based on nodespecific characteristics. However, traditional PPR falls short in heterophilous settings due to its inherent homophily assumption in the random walk process. Our approach makes three key contributions to address these challenges:

1. Heterophily-Aware Random Walks: We modify PPR's random walk process to integrate feature diversity directly, enabling the discovery of relevant nodes even when they differ from their neighbors. This adaptation balances structural connectivity with feature diversity.
2. Context-Sensitive Subgraphs: Using our enhanced PPR scores, we develop efficient node-centric subgraph extraction methods that preserve both feature dissimilarity and structural patterns, creating robust local neighborhoods that capture heterophilous relationships.
3. Theoretical Guarantees: We provide a theoretical analysis of how HAPPY preserves both homophilous and heterophilous relationships, making it particularly suitable for graphs with varying structural patterns.
4. Effective and Scalable: By combining our subgraph reasoning with simple feature transformation approaches like SGC [Wu et al., 2019], HAPPY achieves state-of-the-art performance while maintaining high scalability.

Outline. We start with some background (§2). Then, we present H-PPR (§3), the subgraph extraction strategies (§4), the classification pipeline (§5), and the theoretical analysis (§6). We evaluate HAPPY (§7) and then conclude (§8).

2 Background and ProblemFormulation

Let G = (V, E) denote a graph with node features X ∈ RN×NF . We denote by N(u) the neighbors of a node u. For nodes u and v, their feature dissimilarity is: h(u, v) = 1-sim(xu, xv), where sim(·, ·) is a bounded similarity function in [0, 1]. The edge homophily ratio and its adjusted version [Platonov et al., 2023a] are defined as:

where Dk := ∑i:yi=k d(i) for class label k.

Problem: Given G = (V, E) with labeled nodes YL, we aim to learn fp(G,YL)→ ˆYU, where ˆYU are the predicted labels for unlabeled nodes.

HAPPY is motivated by recent advances in graph learning that emphasize the importance of effectively combining structural and feature information while adapting to graph properties [Zhu et al., 2020; Bo et al., 2021; Yang et al., 2021; Li et al., 2022]. This insight stems from a key observation: real-world graphs exhibit varying levels of heterophily, where connected nodes may have either different or similar features. To address this challenge, HAPPY employs a decoupled architecture that leverages both similarity-driven and dissimilarity-driven context. The approach operates in three steps: first computing Heterophily-Aware Personalized PageRank (H-PPR) scores (§ 3), then extracting node-specific contextual subgraphs (§ 4), and finally learning, transforming and feeding node representations to a classifier (§ 5). Through this node-centric approach, HAPPY tailors both structural and feature information to each node's local neighborhood, enabling better pattern identification by combining structural connectivity with relevant feature patterns.

3 Heterophily-Aware Personalized PageRank

H-PPR extends PPR [Haveliwala, 2002] by enabling effective navigation of graphs where connected nodes can be either similar or dissimilar thus proving more robust node classification across diverse graph structures.

Definition 3.1 (H-PPR). We define a transition probability matrix P that adapts to each node's local heterophily level. Specifically, for nodes u ∈ V and neighbors v ∈ N(u), let

where λu ∈ [0, 1] is the local heterophily coefficient of node u (§3.1). Then each entry Puv of P is:

The H-PPR score vector πt satisfies:

where α ∈ (0, 1) is a damping factor, β ∈ [0, 1] a localglobal restart parameter, et a vector that is one-hot at target node t, and radaptive an adaptive restart distribution (§3.2).

3.1 Local Heterophily and Adaptive Transition

HAPPY aims at leveraging both graph structure and features while effectively handling both homophilous and heterophilous relationships. However, with only limited labeled nodes available in real-world graphs, we face two challenges: (1) estimating local heterophily patterns to guide random walks, and (2) measuring neighborhood diversity to enable adaptive transitions. To address these challenges, we leverage pseudo-labels that propagate train labels across the network through both structural connections and feature similarities. We derive pseudo-labels Y via label propagation:

Y(k+1) = D-1ASY(k) where D is the degree matrix, A is the adjacency matrix, and S is a diagonal feature similarity matrix with Sij = sim(Xi,Xj) (e.g., based on cosine) for neighboring nodes. Pseudo-labels enable us to compute essential metrics like local heterophily coefficients and label diversity, which are crucial for guiding adaptive transitions and balancing exploration between diverse and similar regions. Local Heterophily Computation: for each node v ∈ V, we define λv to capture whether its neighbors are more similar

or more dissimilar. We combine two heterophily indicators:

where γ ∈ [0, 1] is a balance parameter. The label-based term hlabel(v) is the fraction of neighbors whose pseudo-label in Y differs from v's own label:

While the feature-based term hfeat(v) is the average dissimilarity w.r.t. features X:

Hence, λv approaches 1 if v's neighborhood is highly heterophilous (different labels or features), and it approaches 0 if neighbors are mostly similar.

Heterophily-Aware Transitions: using each node's local heterophily λu in (3), we define the base transition probability:

If u has λu ≈ 1, it prefers neighbors more dissimilar in features/labels; if λu≈0, it prefers those more similar.

3.2 Adaptive Restart Distribution

In addition to local node-level coefficients, we also estimate a global heterophily level λglobal (e.g., the average of all {λv}). This value governs how the random walk restarts from diverse vs. homogeneous nodes. For each node v we define:

1. Local Diversity: wemeasure label diversity rdiv(v) in v's neighborhood computing pseudo-label entropy as:

where ϵ is a small constant (e.g. 10-10 ) to avoid zero denominators. A higher rdiv(v) indicates that v's neighborhood has a broader distribution of pseudo-labels.

1. Local Similarity: it measures feature homogeneity rsim(v) in v's neighborhood via average similarity:

where Homogeneity(N(v)) can be computed, for instance, as 1 |N (v)| ∑u∈N(v) cos(xv, xu).

We then form the final adaptive restart distribution:

Hence, when λglobal is high (i.e., the graph is largely diverse), the walk restarts more frequently in neighborhoods with high label entropy, and vice versa when λglobal is low. This ensures that the random walk globally balances exploring dissimilar regions against reinforcing neighborhoods of similarity.

Balanced Feedback to Avoid Local Traps

Despite the above mechanisms, a random walk may still converge too quickly into exclusively similar or dissimilar clusters. To mitigate such "traps," we introduce a balanced feedback adjustment to the transition probabilities:

where Vv is the set of nodes visited so far, β ∈ [0, 1] is a feedback strength, and bal(v, Vv, λu) is a function that evaluates whether v has been over- or under-explored under a similar local heterophily context λu. For example, if v has been visited frequently when λu is high, we reduce P ′ (u → v) to encourage more exploration of homophilous regions and vice versa. This can be implemented by tracking the visit counts during the walk and then adjusting P(·) at each iteration.

3.3 Algorithm and Implementation Details

Algorithm 1 illustrates a reference implementation of H-PPR, unifying local and global adaptations, as well as optional balanced feedback if desired.

Algorithm 1 Heterophily-Aware Personalized PageRank

Input:

1: Graph G = (V, E) with node features X and pseudo-labels Y 2: Parameters: damping α ∈ (0, 1), local-global restart β ∈ [0, 1], balance γ ∈ [0, 1] 3: max iter, convergence tolerance ϵ Output: 4: H-PPR score dictionary {πu : u ∈ V} 5: function H-PPR(G,X,Y, α, β, γ,max iter, ϵ) 6: λglobal ← ESTIMATEGLOBALHETEROPHILY(G,Y) 7: λ← COMPUTELOCALHETEROPHILY(G,X,Y, γ) 8: radaptive ← COMPUTEADAPTIVERESTART(G, X, Y, λglobal ) 9: S ← cosine similarity(X) 10: D← 1-S 11: scores ← {} 12: for each source node u ∈ V do 13: // Build transition matrix P 14: P ← 0|V|×|V| 15: for each node v ∈ V do 16: Nv ← neighbors(v) 17: if Nv ̸= ∅ then 18: wv ← λv D[v,Nv] + (1 -λv)S[v,Nv] 19: P[v,Nv] ←wv / ∑(wv) 20: // Power iteration for node u 21: p ← eu // One-hot vector 22: for iter = 1 to max iter do 23: pnew ← α P⊤p + (1 - α)[β eu + (1 - β) radaptive ] 24: if ∥pnew - p∥1 < ϵ then 25: break 26: p ← pnew 27: scores[u] ← p 28: return scores

Interpretation. By incorporating both feature-based and label-based information, H-PPR can rank nodes that are similar in one modality but complementary in another. The adaptive restart further ensures that the random walk explores diverse neighborhoods if the overall graph is heterophilous, or focuses on more homogeneous regions if the graph is highly homophilous. Finally, balanced feedback (§3.2) ensures that the walk does not get "stuck" in only one type of region. Hence, H-PPR provides a robust and flexible ranking mechanism that adapts to graphs spanning the entire homophilyheterophily spectrum.

Complexity Analysis. Algorithm 1 primarily spends its time in three stages for each source node u ∈ V: (1) Feature Similarity and Transition Matrix Construction (e.g., line 9 and 13-19). Computing cosine similarities of dimension d and then forming neighbor-based weights is O(|Nu| d) for node u; (2) Power Iteration (e.g., lines 21-26). Each update of the score vector p takes O(|E|) when the transition matrix is stored in a sparse format. If k is the number of iterations until convergence, this part costs O(k |E|); (3) Local/Global Heterophily Computations. Estimating local heterophily λv and the global level λglobal each require summing over a node's neighborhood, i.e. O(|Nu|) per node. Summed over all nodes, this is O(∑v∈V |Nv|) = O(|E|) in an undirected graph. Hence, for a single source node, the total cost is O(∑u∈V (|Nu| (d + 1)) + k |E|). Because ∑u∈V |Nu| = 2|E|, this simplifies to O(|E| (d + 1)) + O(k |E|) = O(k |E| + d |E|). If every node serves as a source, we multiply by |V|, unless certain computations (e.g., similarity) are reused across different source nodes. In practice, many of these steps (e.g., S and λv) need to be computed only once, amortizing the cost over multiple runs.

Parallelization. Since each node's H-PPR can be computed independently, we can partition the node set V across p processors: V=⋃pi=1 Vi, achieving up to 1p speedup (neglecting communication overhead Ccomm). Both neighbor-weight construction and power iteration steps can be parallelized with sparse matrix operations.

4 Heterophily-Aware Subgraph Extraction

We present four approaches for extracting node-centric subgraphs reflecting meaningful relationships specific to a target node. Balancing structural similarity and diversity based on local heterophily, these strategies produce representations of both homophilous and heterophilous interactions:

1. Adaptive Top-k H-PPR. Given the H-PPR scores {πv[u]} for a node v, we extract nodes with significant scores:

where kv adapts to each node's influence pattern:

Here, ϵ is a significance threshold (10-4 ) filtering negligible relationships, and p (typically 0.4-0.6) controls the proportion of influential nodes to include. This adaptive approach ensures the subgraph size naturally scales with each node's effective influence range.

1. Adaptive Diversity-Aware. This strategy iteratively builds a diverse subgraph by selecting nodes that balance

both structural importance and feature diversity. Starting from a seed node v, each new node u∗ is chosen to maximize the sum of its PPR score and its minimum feature distance d(u, w) from currently selected nodes, weighted by the local heterophily coefficient λv:

where S is the set of selected nodes (initialized with v), d(u,w) measures feature distance between nodes, and λv controls the diversity-similarity trade-off.

1. Adaptive Threshold. Here, the subgraph size depends on the H-PPR score distribution and local properties:

where µv and σv are the mean and standard deviation of {πv[u]}, and αv = δ(1 - λv) + λv with δ > 1 being a hyper-parameter controlling the amplification of the homophilous component. When λv = 1 (high heterophily) we have αv = 1, while for λv = 0 (high homophily) we get maximum amplification αv = δ.

1. Structure-Preserving. We balance H-PPR scores with structural connectivity while adapting to local properties as: (1) Initialize S={argmaxu̸=v πv[u]}; (2) Iteratively select nodes maximizing:

where βv = γ (1 - λv ) + (1 - γ)λv with γ ∈ [0, 1] being a hyperparameter to control how much weight is given to homophilous (1 - λv) versus heterophilous (λv) relationships in the score computation. This produces subgraphs that remain well-connected while balancing homophilous and heterophilous relationships.

5 Feature Transformation and Classifier

We process nodes in batches for efficient feature transformation and classification. For each batch B = {v1, . . . , vb}, we extract node-centric subgraphs {G1, . . . , Gb} using one of the above strategies (§4). Each subgraph Gi = (Vi, Ei) contains up to m nodes most relevant to vi. Although we can use any architecture for feature transformation (§ 7.2), we focus on SGC [Wu et al., 2019] for its effectiveness and efficiency. For subgraph Gi, we define the normalized adjacency ˆAi = D-1/2 i Ai D-1/2 i . The batch transformation is:

where Xi is the subgraph's feature matrix andW is a learnable weight matrix.

Classifier. After obtaining node representations, we perform node classification. Although our framework supports any classifier, we demonstrate its effectiveness using simpler models. This choice highlights that the benefit of our approach stems from the high-quality subgraphs and transformations produced by H-PPR, rather than from a complex classifier. As shown by our experiments (§7), even simple classifiers can yield strong performance.

6 Theoretical Analysis

We now highlight some key theoretical properties of our proposal. Each result shows how local (λv) and global (λglobal) heterophily measures govern the random-walk transition dynamics, ensuring that both similar and dissimilar relationships are preserved. This dual emphasis makes H-PPR particularly well-suited for graphs where homophily is not the dominant pattern or where the structure varies regionally. A more comprehensive discussion is available online 1 .

Theorem 6.1 (Local Heterophily Bounds). For any node v, its local heterophily coefficient λv is bounded by:

where hlabel(v) is the label-based heterophily and hfeat(v) is the feature-based heterophily.

This theorem provides an upper bound on the local heterophily coefficient λv for any node v. The intuition is that since λv is computed as a weighted average of label-based and feature-based heterophily: λv = γ · hlabel(v) + (1 - γ) · hfeat(v) it cannot exceed either component. This shows that our local heterophily measure is well-behaved and bounded by the structural properties of the node's neighborhood.

Lemma 6.2 (Adaptive Restart Property). For a graph with global heterophily level λglobal, the probability of restarting at a structurally diverse node is proportional to λglobal:

This lemma says how the global heterophily level influences the restart distribution. The key insight is that the probability of restarting at diverse nodes (those with high label entropy in their neighborhood) is directly proportional to λglobal.

Theorem 6.3 (Homophily-Heterophily Duality). For any node v with local heterophily coefficient λv and neighborhood N(v), H-PPR's transition probabilities satisfy:

This theorem establishes a fundamental relationship between similarity and dissimilarity in the transition probabilities. It shows that for any node, the expected similarity and dissimilarity of its transitions sum to 1, weighted by its local heterophily coefficient.

Lemma 6.4 (Heterophily Probability). The probability of selecting heterophilous neighbors in H-PPR is locally proportional to λv and globally proportional to λglobal.

This lemma connects local and global heterophily measures to transition probabilities. This is crucial because it shows how H-PPR adapts at different scales.

1 https://github.com/giuseppepirro/happy

Theorem 6.5 (Preservation of Structure). For a graph with heterophily ratio H(G), H-PPR adaptively preserves both heterophilous and homophilous relationships through:

This theorem shows how H-PPR maintains both heterophilous and homophilous patterns. This demonstrates the algorithm's ability to adapt to different graph structures.

7 Experimental Evaluation

We describe the datasets and the experimental setting (§7.1). We compare HAPPY with the state-of-the-art (§7.2) providing also an ablation analysis. Then, we evaluate subgraph extraction strategies (§7.3) and PageRank alternatives (§7.4).

7.1 Datasets and experimental setting

We considered state-of-the-art hetherophilous datasets [Platonov et al., 2023b], which addressed issues in standard benchmarks for heterophily graphs, such as duplicates and imbalances, in datasets like Squirrel, Chameleon, Texas, Wisconsin, and Cornell [Zheng et al., 2022]. These enhanced datasets are larger and cover a broader range of domains, as summarized in Table 2.

Dataset splits. We used the dataset splits provided by [Platonov et al., 2023b] and available online 2 The authors fix 10 random 50%/25%/25% train/validation/test splits. All models' performances are obtained by computing the averaged results and the standard deviation over the splits.

Implementation and Hyperparameters. We implemented1 in PyTorch 3 and MLX 4 and integrated it into the evaluation pipeline provided by Platonov et al. [Platonov et al., 2023b], which includes many baselines and facilitates the overall evaluation process. The pipeline also allows tuning HAPPY's hyperparameters based on the validation performance. We tuned random walk controls (α, β ∈ [0.1, 0.9]), computational settings (max iter ∈ [100, 1000], ϵ ∈ [10-6 , 10-8 ]), and SGC iterations K (2-4). A detailed ablation analysis is discussed below. We ran experiments on a Mac Studio M2 Ultra with a 24-core CPU, 60-core GPU, and 32-core Neural Engine with 192GB of unified memory.

2 https://github.com/yandex-research/heterophilous-graphs

3 https://pytorch.org

4 https://github.com/ml-explore/mlx

7.2 Comparison with the state-of-the-art

For sake of space, we directly consider models specifically crafted for node classification in heterophilous contexts and do not report, for instance, methods such as ResNet [He et al., 2016] and GNN-variants [Kipf and Welling, 2017]) that have been shown to be non-competitive in heterophilous settings as shown in [Platonov et al., 2023b]. We compared HAPPY against 16 state-of-the-art methods using their publicly accessible implementations. Results are in Table 3.

HAPPYbest, our best performing variant, uses SGC (k=3) as feature transformation, adaptive diversity as subgraph extraction mechanism (§4), and a FFW with two layers as classifier. HAPPYbest consistently outperforms state-of-the-art methods across all benchmarks, with particularly notable improvements on challenging heterophilous datasets. On smallscale heterophilous graphs like Squirrel-filtered (2,223 nodes) and Chameleon-filtered (183 nodes), our method achieves significant gains of 4.28% and 4.02% respectively over the best baseline (OGNN). The superiority of HAPPY is even more evident on large-scale datasets: it surpasses CDE by 0.8% on Wiki-cooc (10,000 nodes, Hedge = 0.34) and shows remarkable improvement on highly heterophilous graphs like Questions (48,921 nodes, Hedge = 0.84), outperforming ACM-GCN by 4.06%. These results demonstrate that our heterophily-aware PPR effectively captures both local and global patterns regardless of graph size or heterophily levels (Hedge ranging from 0.05 to 0.84). Notably, HAPPY maintains its strong performance even on challenging datasets, such as Roman-empire (Hadjusted = -0.05), demonstrating its versatility across different graph structures. Our ablation studies provide key insights into the components of HAPPY. In Study 1, we analyze different feature transformation approaches while keeping the classifier fixed. SGC with k=2 generally performs best, achieving superior results across most datasets (e.g., 96.50% on Wiki-cooc). Notably, performance gradually decreases with higher k SGC values or when using more complex architectures like GCN/GAT, suggesting that simpler transformations better preserve heterophilous patterns. Study 2 examines classifier choices while fixing the feature transformation to SGC (k=3). The results show minimal variation across classifiers (e.g., on Wiki-cooc: Logistic 97.18%, SVM 96.98%), with Logistic Regression performing marginally better. This indicates that adaptive diversity-based subgraph extraction captures the graph's structural properties, making the choice of classifier less critical.

7.3 Evaluating subgraph extraction strategies

We now evaluate the effectiveness of each subgraph extraction strategy (§ 4). Fig. 1 provides a comprehensive analysis of our four subgraph extraction strategies across diverse datasets. The Adaptive Diversity-aware approach consistently demonstrates superior performance. This validates our intuition that explicitly balancing structural importance with feature diversity through λv effectively captures heterophilous patterns. The Adaptive Top-k H-PPR strategy shows competitive performance on homophilous datasets, achieving 0.96 accuracy on Minesweeper with p = 0.4, but slightly underperforms on more heterophilous graphs. The Adaptive Threshold approach, controlled by δ(1 - λv) + λv , maintains stable performance across different homophily levels but shows sensitivity to the parameter, visible in the sharp performance drop at δ=3.0. The Structure-Preserving strategy, while ensuring well-connected subgraphs through βv, demonstrates more consistent but generally lower performance across all datasets, suggesting that strictly maintaining structural connectivity might limit the capture of important heterophilous relationships. Notably, all strategies show improved performance compared to traditional homophilybased approaches, with the Adaptive Diversity-aware method providing the best balance between homophilous and heterophilous pattern recognition. These results highlight that subgraph extraction benefits significantly from both nodecentric relevance (via H-PPR) and local heterophily-driven diversification, ensuring that each neighborhood reflects the most informative aspects of the target node's surroundings.

7.4 Comparison with Page Rank variants

We compare HAPPYbest based on our Heterophily-aware PPR (H-PPR) against two baselines: Traditional PPR (TPPR), which uses fixed transition probabilities based solely on graph structure, and Personalized PPR (P-PPR), which introduces node-specific bias terms but still assumes homophily in transitions. As shown in Table 4, H-PPR consistently outperforms both variants across all datasets, with particularly notable improvements on challenging heterophilous graphs. On SquirrelF and ChameleonF, H-PPR achieves gains of +2.17% and +1.77% over P-PPR respectively, demonstrating its effectiveness in capturing heterophilous relationships. The improvement is even more pronounced on large-scale datasets with mixed homophily patterns: H-PPR surpasses P-PPR by +2.69% on AmazonR (Hedge = 0.38) and +2.35% on Questions (Hedge = 0.84). Notably, H-PPR maintains its advantages on homophilous graphs like Wiki-cooc (+1.69%) and Minesweeper (+2.15%), indicating that our heterophilyaware modifications do not compromise performance when homophily dominates. The lower variance in H-PPR's results (e.g., ±0.04 on AmazonR compared to ±0.12 for P-PPR) suggests more stable performance, likely due to its adaptive balancing of structural and feature-based relationships.

These results validate our insights about integrating feature diversity into the random walk process, showing that H-PPR effectively captures both homophilous and heterophilous patterns while maintaining computational efficiency.

8 Concluding Remarks

We presented HAPPY, a framework for node classification in heterophilous graphs that adapts Personalized PageRank to balance structural and feature relationships. By integrating feature diversity into random walks and using adaptive subgraph extraction, HAPPY captures both homophilous and heterophilous patterns efficiently. Experiments show that HAPPY outperforms state-of-the-art methods. Future work could explore self-supervised learning applications and extensions to temporal graphs with evolving structures and features.

Acknowledgments

This work was partially supported by the European Union - Next Generation EU through the MUR Project HypeKG within PRIN 2022 Program (CUP: H53D23003710006), and the MUR PRIN 2022-PNRR project DISTORT (CUP: H53D23008170001) under the Italian PNRR Mission 4 Component 1.