Heterophily-Aware Personalized PageRank for Node Classification

Giuseppe PirròIJCAI 2025 · DOI

TL;DR

This paper introduces HAPPY, a novel framework for node classification in heterophilous graphs (where connected nodes often have different characteristics). HAPPY enhances Personalized PageRank (PPR) by incorporating both feature and label diversity into random walks and uses this to extract context-aware subgraphs, achieving state-of-the-art results on challenging heterophilous benchmarks.

What Problem Does This Paper Address?

Node classification is a fundamental task in graph machine learning, aiming to predict the labels of nodes in a graph. Traditional methods often assume homophily, meaning connected nodes tend to share similar attributes or labels. However, many real-world graphs exhibit heterophily, where connections often link dissimilar nodes (e.g., a groundbreaking paper might be cited by works that challenge its ideas). This heterophily breaks the assumptions of standard graph learning algorithms, making accurate node classification difficult. Existing methods struggle with challenges like computational complexity, memory overhead, or a lack of theoretical guarantees when dealing with these complex, heterophilous structures.

Methods

HAPPY tackles heterophily through a three-pronged approach:

  1. Heterophily-Aware Personalized PageRank (H-PPR): This is the core innovation. It modifies the standard Personalized PageRank (PPR) algorithm to account for heterophily. Instead of just following structural connections, H-PPR's random walks consider both feature similarity and dissimilarity. It uses local heterophily coefficients (derived from pseudo-labels and feature similarity) to adapt transition probabilities, allowing walks to explore both similar and dissimilar neighbors. It also incorporates adaptive restart distributions, balancing global and local graph properties.
  2. Context-Sensitive Subgraphs: Using the H-PPR scores, HAPPY extracts node-specific subgraphs. These subgraphs are designed to preserve both feature dissimilarity and structural patterns relevant to each node. Four strategies are proposed:
  3. Adaptive Top-k H-PPR: Selects nodes with the highest H-PPR scores.
  4. Adaptive Diversity-Aware: Iteratively selects nodes that maximize a combination of H-PPR score and minimum feature distance to already selected nodes, weighted by local heterophily.
  5. Adaptive Threshold: Selects nodes based on H-PPR scores relative to local mean and standard deviation, with a parameter that amplifies homophilous or heterophilous components.
  6. Structure-Preserving: Balances H-PPR scores with structural connectivity, adapting to local heterophily.
  7. Feature Transformation and Classifier: The extracted subgraphs are then processed. The paper highlights the effectiveness of simple feature transformation methods like SGC (Simple Graph Convolution) and notes that even basic classifiers can achieve strong performance, indicating the primary contribution comes from the H-PPR and subgraph extraction.

Datasets

The paper evaluates HAPPY on several standard heterophilous graph datasets, including:

  • Squirrel-filtered
  • Chameleon-filtered
  • Wiki-cooc
  • Roman-empire
  • Amazon-ratings
  • Minesweeper
  • Tolokers
  • Questions
  • arXiv-year

These datasets are noted to address issues in older benchmarks by being larger and covering a broader range of domains, with specific attention paid to duplicates and imbalances.

Key Insights and Ideas

  • Heterophily is not just about dissimilarity: The paper emphasizes that heterophilous graphs can contain both homophilous and heterophilous relationships, and a successful method must balance these. HAPPY's H-PPR explicitly models this duality.
  • Personalized PageRank is a strong foundation: By adapting PPR, which naturally measures node importance through random walks, the authors leverage a well-understood mechanism and extend it to handle heterophily.
  • Local context is crucial: The H-PPR's local heterophily coefficients and the node-centric subgraph extraction are key to capturing the nuanced relationships around each node.
  • Subgraph quality matters more than classifier complexity: The experiments show that HAPPY's strength lies in its ability to generate informative subgraphs, allowing even simple classifiers to perform well.

Key Results

  • HAPPY consistently outperforms 16 state-of-the-art methods across all tested heterophilous benchmarks.
  • Significant gains are observed on challenging datasets, such as Squirrel-filtered (+4.28% over OGNN) and Chameleon-filtered (+4.02% over OGNN).
  • On large-scale datasets, HAPPY surpasses baselines like CDE and ACM-GCN.
  • The Adaptive Diversity-aware subgraph extraction strategy generally yields the best performance.
  • H-PPR consistently outperforms traditional PPR and Personalized PPR variants, showing improvements of up to +2.69% on AmazonR and +2.35% on Questions.
  • H-PPR also demonstrates more stable performance with lower variance in results compared to P-PPR.

Limitations and Future Work

  • Limitations: The paper acknowledges that while HAPPY achieves state-of-the-art results, multi-hop view approaches can still face computational complexity with increasing hop counts. Discriminative message passing methods may require careful feature engineering.
  • Future Work: The authors suggest exploring self-supervised learning applications and extending the framework to temporal graphs with evolving structures and features.

Summary updated

BibTeX
@inproceedings{pirro2025heterophily,
  author = {Giuseppe Pirrò},
  title = {{Heterophily-Aware Personalized PageRank for Node Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/676},
}
Figure