Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning

Yuhao Wu, Jiangchao Yao, Bo Han, Lina Yao, Tongliang Liu
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:53928-53943, 2024.

Abstract

While Positive-Unlabeled (PU) learning is vital in many real-world scenarios, its application to graph data still remains under-explored. We unveil that a critical challenge for PU learning on graph lies on the edge heterophily, which directly violates the irreducibility assumption for Class-Prior Estimation (class prior is essential for building PU learning algorithms) and degenerates the latent label inference on unlabeled nodes during classifier training. In response to this challenge, we introduce a new method, named G_raph P_U Learning with L_abel Propagation Loss (GPL). Specifically, GPL considers learning from PU nodes along with an intermediate heterophily reduction, which helps mitigate the negative impact of the heterophilic structure. We formulate this procedure as a bilevel optimization that reduces heterophily in the inner loop and efficiently learns a classifier in the outer loop. Extensive experiments across a variety of datasets have shown that GPL significantly outperforms baseline methods, confirming its effectiveness and superiority.

Cite this Paper


BibTeX
@InProceedings{pmlr-v235-wu24ad, title = {Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning}, author = {Wu, Yuhao and Yao, Jiangchao and Han, Bo and Yao, Lina and Liu, Tongliang}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {53928--53943}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/wu24ad/wu24ad.pdf}, url = {https://proceedings.mlr.press/v235/wu24ad.html}, abstract = {While Positive-Unlabeled (PU) learning is vital in many real-world scenarios, its application to graph data still remains under-explored. We unveil that a critical challenge for PU learning on graph lies on the edge heterophily, which directly violates the $\textit{irreducibility assumption}$ for $\textit{Class-Prior Estimation}$ (class prior is essential for building PU learning algorithms) and degenerates the latent label inference on unlabeled nodes during classifier training. In response to this challenge, we introduce a new method, named $\textit{$\underline{G}$raph $\underline{P}$U Learning with $\underline{L}$abel Propagation Loss}$ (GPL). Specifically, GPL considers learning from PU nodes along with an intermediate heterophily reduction, which helps mitigate the negative impact of the heterophilic structure. We formulate this procedure as a bilevel optimization that reduces heterophily in the inner loop and efficiently learns a classifier in the outer loop. Extensive experiments across a variety of datasets have shown that GPL significantly outperforms baseline methods, confirming its effectiveness and superiority.} }
Endnote
%0 Conference Paper %T Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning %A Yuhao Wu %A Jiangchao Yao %A Bo Han %A Lina Yao %A Tongliang Liu %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-wu24ad %I PMLR %P 53928--53943 %U https://proceedings.mlr.press/v235/wu24ad.html %V 235 %X While Positive-Unlabeled (PU) learning is vital in many real-world scenarios, its application to graph data still remains under-explored. We unveil that a critical challenge for PU learning on graph lies on the edge heterophily, which directly violates the $\textit{irreducibility assumption}$ for $\textit{Class-Prior Estimation}$ (class prior is essential for building PU learning algorithms) and degenerates the latent label inference on unlabeled nodes during classifier training. In response to this challenge, we introduce a new method, named $\textit{$\underline{G}$raph $\underline{P}$U Learning with $\underline{L}$abel Propagation Loss}$ (GPL). Specifically, GPL considers learning from PU nodes along with an intermediate heterophily reduction, which helps mitigate the negative impact of the heterophilic structure. We formulate this procedure as a bilevel optimization that reduces heterophily in the inner loop and efficiently learns a classifier in the outer loop. Extensive experiments across a variety of datasets have shown that GPL significantly outperforms baseline methods, confirming its effectiveness and superiority.
APA
Wu, Y., Yao, J., Han, B., Yao, L. & Liu, T.. (2024). Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:53928-53943 Available from https://proceedings.mlr.press/v235/wu24ad.html.

Related Material