research-article

Public Access

Node Classification Beyond Homophily: Towards a General Solution

Authors:

Hanghang TongAuthors Info & Claims

KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 2862 - 2873

https://doi.org/10.1145/3580305.3599446

Published: 04 August 2023 Publication History

Abstract

Graph neural networks (GNNs) have become core building blocks behind a myriad of graph learning tasks. The vast majority of the existing GNNs are built upon, either implicitly or explicitly, the homophily assumption, which is not always true and could heavily degrade the performance of learning tasks. In response, GNNs tailored for heterophilic graphs have been developed. However, most of the existing works are designed for the specific GNN models to address heterophily, which lacks generality. In this paper, we study the problem from the structure learning perspective and propose a family of general solutions named ALT. It can work hand in hand with most of the existing GNNs to handle graphs with either low or high homophily. At the core of our method is learning to (1) decompose a given graph into two components, (2) extract complementary graph signals from these two components, and (3) adaptively integrate the graph signals for node classification. Moreover, analysis based on graph signal processing shows that our framework can empower a broad range of existing GNNs to have adaptive filter characteristics and further modulate the input graph signals, which is critical for handling complex homophilic/heterophilic patterns. The proposed ALT brings significant and consistent performance improvement in node classification for a wide range of GNNs over a variety of real-world datasets.

Supplementary Material

MP4 File (rtfp0347-2min-promo.mp4)

10.1145/3580305.3599446

Download
3.35 MB

References

[1]

Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. 2021. Analyzing the expressive power of graph neural networks in a spectral perspective. In ICLR.

[2]

Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. 2020. Spectral clustering with graph neural networks for graph pooling. In ICML.

[3]

Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. 2021. Beyond Low-frequency Information in Graph Convolutional Networks. In AAAI.

[4]

Aleksandar Bojchevski and Stephan Günnemann. 2018. Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. In ICLR.

[5]

Lei Chen, Zhengdao Chen, and Joan Bruna. 2021. On Graph Neural Networks versus Graph-Augmented MLPs. In ICLR.

[6]

Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference on Learning Representations.

[7]

Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. 2022. Data augmentation for deep graph learning: A survey. ACM SIGKDD Explorations Newsletter, Vol. 24, 2 (2022), 61--77.

Digital Library

[8]

Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. 2022. GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily. In TheWebConf.

[9]

Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. 2019. Learning discrete structures for graph neural networks. In ICML.

[10]

Dongqi Fu and Jingrui He. 2022. Natural and Artificial Dynamics in Graphs: Concept, Progress, and Future. Frontiers Big Data, Vol. 5 (2022). https://doi.org/10.3389/fdata.2022.1062637

[11]

Dongqi Fu, Zhe Xu, Hanghang Tong, and Jingrui He. 2023. Natural and Artificial Dynamics in GNNs: A Tutorial. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM 2023, Singapore, 27 February 2023 - 3 March 2023, Tat-Seng Chua, Hady W. Lauw, Luo Si, Evimaria Terzi, and Panayiotis Tsaparas (Eds.). ACM, 1252--1255. https://doi.org/10.1145/3539597.3572726

Digital Library

[12]

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In ICML.

[13]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. NeurIPS (2017).

[14]

Mingguo He, Zhewei Wei, Hongteng Xu, et al. 2021. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. NeurIPS (2021).

[15]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.

[16]

Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In ICLR.

[17]

Junying Li, Deng Cai, and Xiaofei He. 2017. Learning graph-level representation for drug discovery. arXiv preprint arXiv:1709.03741 (2017).

[18]

Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. arXiv preprint arXiv:2205.07308 (2022).

[19]

Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. 2021. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. NeurIPS (2021).

[20]

Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2021. Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification? arXiv preprint arXiv:2109.05641 (2021).

[21]

Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. 2021. Learning to drop: Robust graph neural network via topological denoising. In WSDM.

[22]

Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. 2021. Is homophily a necessity for graph neural networks? arXiv preprint arXiv:2106.06134 (2021).

[23]

Mark Newman. 2018. Networks. Oxford university press.

[24]

Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2019. Geom-GCN: Geometric Graph Convolutional Networks. In ICLR.

[25]

Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2021. Multi-scale attributed node embedding. Journal of Complex Networks, Vol. 9, 2 (2021), cnab014.

[26]

Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018).

[27]

David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2013. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, Vol. 30, 3 (2013), 83--98.

[28]

Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. 2021. Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns. In KDD.

[29]

Laurens Van Der Maaten. 2014. Accelerating t-SNE using tree-based algorithms. The Journal of Machine Learning Research, Vol. 15, 1 (2014), 3221--3245.

Digital Library

[30]

Petar Velivc ković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In ICLR.

[31]

Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. 2021. Graph Structure Estimation Neural Networks. In TheWebConf.

[32]

Tao Wang, Di Jin, Rui Wang, Dongxiao He, and Yuxiao Huang. 2022a. Powerful Graph Convolutional Networks with Adaptive Propagation Mechanism for Homophily and Heterophily. In AAAI.

[33]

Tao Wang, Rui Wang, Di Jin, Dongxiao He, and Yuxiao Huang. 2022b. Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophily. In AAAI.

[34]

Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying graph convolutional networks. In ICML.

[35]

Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. 2020. Graph Information Bottleneck. NeurIPS (2020).

[36]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How Powerful are Graph Neural Networks?. In ICLR.

[37]

Zhe Xu, Boxin Du, and Hanghang Tong. 2022. Graph sanitation with application to node classification. In Proceedings of the ACM Web Conference 2022. 1136--1147.

Digital Library

[38]

Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. 2021. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462 (2021).

[39]

Liang Yang, Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, et al. 2021. Diverse Message Passing for Attribute with Heterophily. NeurIPS (2021).

[40]

Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semi-supervised learning with graph embeddings. In ICML.

[41]

Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. 2020. Graph Information Bottleneck for Subgraph Recognition. In ICLR.

[42]

Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. NeurIPS (2018).

[43]

Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. 2019. Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI.

[44]

Beidi Zhao, Boxin Du, Zhe Xu, Liangyue Li, and Hanghang Tong. 2022a. Learning Optimal Propagation for Graph Neural Networks. arXiv preprint arXiv:2205.02998 (2022).

[45]

Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. 2022b. Graph Data Augmentation for Graph Machine Learning: A Survey. arXiv preprint arXiv:2202.08871 (2022).

[46]

Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022. Graph Neural Networks for Graphs with Heterophily: A Survey. arXiv preprint arXiv:2202.07082 (2022).

[47]

Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. 2021a. Graph Neural Networks with Heterophily. In AAAI.

[48]

Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS (2020).

[49]

Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. 2021b. Deep graph structure learning for robust representations: A survey. arXiv preprint arXiv:2103.03036 (2021).

Cited By

Das SFerdous SHalappanavar MSerra EPothen ABaeza-Yates RBonchi F(2024)AGS-GNN: Attribute-guided Sampling for Graph Neural NetworksProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671940(538-549)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671940
Zhao HChen ASun XCheng HLi JBaeza-Yates RBonchi F(2024)All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph PretrainingProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671913(4443-4454)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671913
Wang FZhao TXu JWang SSerra ESpezzano F(2024)HC-GST: Heterophily-aware Distribution Consistency based Graph Self-trainingProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679622(2326-2335)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679622
Show More Cited By

Index Terms

Node Classification Beyond Homophily: Towards a General Solution

Recommendations

Node Classification of Graph Neural Networks Based on Graph Degree-Symmetry
AAIA '23: Proceedings of the 2023 International Conference on Advances in Artificial Intelligence and Applications

In order to accurately reflect the information of each node's neighbours and the topological relationship of the graph structure, the graph neural network node classification task aims to treat each node and all of its neighbouring nodes as a subgraph ...
Improved Topology Features for Node Classification on Heterophilic Graphs
Machine Learning and Knowledge Discovery in Databases. Research Track
Abstract
Graph neural networks (GNNs) are one of the most effective techniques for node classification tasks. However, standard GNNs strongly depend on the graph homophily assumption, and their accuracy can degrade substantially on heterophilic graphs. A ...
Generalized heterophily graph data augmentation for node classification
Abstract
Graph data augmentations have demonstrated remarkable performance on homophilic graph neural networks (GNNs). Nevertheless, when transferred to a heterophilic graph, these augmentations are less effective for GNN models and lead to reduced ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2023

5996 pages

ISBN:9798400701030

DOI:10.1145/3580305

General Chairs:
Ambuj Singh
UC Santa Barbara, USA
,
Yizhou Sun
UC Los Angeles, USA
,
Program Chairs:
Leman Akoglu
Carnegie Mellon University, USA
,
Dimitrios Gunopulos
University of Athens, Greece
,
Xifeng Yan
UC Santa Barbara, USA
,
Ravi Kumar
Google, USA
,
Fatma Ozcan
Google, USA
,
Jieping Ye
Alibaba DAMO Academy

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 August 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
DARPA
NIFA
DHS
ARO

Conference

KDD '23

Sponsor:

KDD '23: The 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 6 - 10, 2023

CA, Long Beach, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
834
Total Downloads

Downloads (Last 12 months)598
Downloads (Last 6 weeks)57

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Das SFerdous SHalappanavar MSerra EPothen ABaeza-Yates RBonchi F(2024)AGS-GNN: Attribute-guided Sampling for Graph Neural NetworksProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671940(538-549)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671940
Zhao HChen ASun XCheng HLi JBaeza-Yates RBonchi F(2024)All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph PretrainingProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671913(4443-4454)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671913
Wang FZhao TXu JWang SSerra ESpezzano F(2024)HC-GST: Heterophily-aware Distribution Consistency based Graph Self-trainingProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679622(2326-2335)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679622
Yan YChen YChen HXu MDas MYang HTong HOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)From trainable negative depth to edge heterophily in graphsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669196(70162-70178)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669196
Zhou QDing KLiu HTong HFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Learning Node Abnormality with Weak SupervisionProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3614950(3584-3594)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3614950

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents