Research map / Graph learning / Graph self-supervised learning
Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GPL, a bilevel graph PU learning method that learns edge weights via a label propagation loss to down-weight heterophilic edges, improving class-prior estimation and PU classification on homophilic and heterophilic graphs.
Problem
Positive-unlabeled learning on graphs is hampered by edge heterophily, which violates the irreducibility assumption needed for class-prior estimation and degrades latent label inference for unlabeled nodes.
Approach
A learnable edge mask is optimized with a Label Propagation Loss that uses only observed positive nodes (and identified P/N nodes) to strengthen homophilic edges and weaken heterophilic ones; this is combined with class-prior estimation and PU classification in a bilevel optimization (inner: graph structure, outer: GNN classifier).
Key results
- GPL achieves the best F1 on all ten datasets, e.g., 37.9 on Cornell vs. 30.6 for the best prior graph PU method (GRAB) and 82.3 on Wiki-CS vs. 80.4 (LSDAN).
- GPL reduces class-prior estimation error to 0.01 on Cora and 0.04 on Cornell, below TED (0.02 and 0.18 respectively).
- Removing LPL drops GPL's F1 on Cornell from 37.9 to 13.9 (63.3% relative drop).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add LPL (ablation) | GPL · Citeseer | F1: 70.0 -> 74.1 | Helped |
| add LPL (ablation) | GPL · Wiki-CS | F1: 79.6 -> 82.3 | Helped |
| add LPL (ablation) | GPL · Cornell | F1: 13.9 -> 37.9 | Helped |
| add LPL (ablation) | GPL · Chameleon | F1: 17.5 -> 36.2 | Helped |
| use bilevel optimization instead of a two-stage approach (ablation) | GPL · Citeseer | F1: 71.5 -> 74.1 | Helped |
| use bilevel optimization instead of a two-stage approach (ablation) | GPL · Wiki-CS | F1: 80.1 -> 82.3 | Helped |
| use bilevel optimization instead of a two-stage approach (ablation) | GPL · Cornell | F1: 32.4 -> 37.9 | Helped |
| use bilevel optimization instead of a two-stage approach (ablation) | GPL · Chameleon | F1: 28.9 -> 36.2 | Helped |
| include selected nodes in LPL (ablation) | GPL · Citeseer | F1: 71.1 -> 74.1 | Helped |
| include selected nodes in LPL (ablation) | GPL · Wiki-CS | F1: 80.2 -> 82.3 | Helped |
| include selected nodes in LPL (ablation) | GPL · Cornell | F1: 34.6 -> 37.9 | Helped |
| include selected nodes in LPL (ablation) | GPL · Chameleon | F1: 32.4 -> 36.2 | Helped |
Surprising findings
- GCN+TED reaches 80.1 F1 on Cora but only 13.9 on Cornell, showing i.i.d. PU methods collapse under strong heterophily.
- Ablation shows removing the label propagation loss causes the largest drop on highly heterophilic graphs (Cornell, Chameleon).
Limitations
- Assumes a GCN-based backbone with a fixed small hidden size and a fixed label propagation depth K; sensitivity to K shows performance drops when K is too large.
- Relies on a heuristic binary task construction (largest class as positive) and uniform 50% positive labeling, limiting generality of evaluation.
Experimental setup
Datasets: Cora Pubmed Citeseer Wiki-CS Cornell Chameleon Squirrel Actor Wisconsin Texas
Benchmarks: Cora Pubmed Citeseer Wiki-CS Cornell Chameleon Squirrel Actor Wisconsin Texas
Metrics: F1 score absolute class-prior estimation error
Baselines: GCN MLP GCN+TED MLP+TED GCN+NNPU MLP+NNPU LSDAN GRAB PU-GNN KM DEDPUL MPE
Builds on: Positive-unlabeled learning class-prior estimation (TED) NNPU label propagation algorithm GCN GRAB
Closest papers by meaning
- Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating (AAAI 2023 · similarity 0.90)
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.89)
- Understanding Heterophily for Graph Neural Networks (ICML 2024 · similarity 0.87)
- HeterSEED: Semantics–Structure Decoupling for Heterogeneous Graph Learning under Heterophily (NeurIPS 2026 · similarity 0.87)
- Integrating Co-Training with Edge Discrimination to Enhance Graph Neural Networks Under Heterophily (AAAI 2025 · similarity 0.87)
- PC-Conv: Unifying Homophily and Heterophily with Two-Fold Filtering (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.