research-article

Free access

Learning Strong Graph Neural Networks with Weak Information

Authors:

Shirui PanAuthors Info & Claims

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

Pages 1559 - 1571

https://doi.org/10.1145/3580305.3599410

Published: 04 August 2023 Publication History

Abstract

Graph Neural Networks (GNNs) have exhibited impressive performance in many graph learning tasks. Nevertheless, the performance of GNNs can deteriorate when the input graph data suffer from weak information, i.e., incomplete structure, incomplete features, and insufficient labels. Most prior studies, which attempt to learn from the graph data with a specific type of weak information, are far from effective in dealing with the scenario where diverse data deficiencies exist and mutually affect each other. To fill the gap, in this paper, we aim to develop an effective and principled approach to the problem of graph learning with weak information (GLWI). Based on the findings from our empirical analysis, we derive two design focal points for solving the problem of GLWI, i.e., enabling long-range propagation in GNNs and allowing information propagation to those stray nodes isolated from the largest connected component. Accordingly, we propose D²PT, a dual-channel GNN framework that performs long-range information propagation not only on the input graph with incomplete structure, but also on a global graph that encodes global semantic similarities. We further develop a prototype contrastive alignment algorithm that aligns the class-level prototypes learned from two channels, such that the two different information propagation processes can mutually benefit from each other and the finally learned model can well handle the GLWI problem. Extensive experiments on eight real-world benchmark datasets demonstrate the effectiveness and efficiency of our proposed methods in various GLWI scenarios.

Supplementary Material

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

This is a short promo video to introduce our paper.

Download
38.20 MB

References

[1]

Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. 2020. Scaling graph neural networks with approximate pagerank. In SIGKDD. 2464--2473.

[2]

Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020b. Simple and deep graph convolutional networks. In ICML. 1725--1735.

[3]

Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang. 2020a. Learning on attribute-missing graphs. IEEE TPAMI (2020).

[4]

Yu Chen, Lingfei Wu, and Mohammed Zaki. 2020c. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In NeurIPS, Vol. 33. 19314--19326.

[5]

Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. 2019. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In SIGKDD. 257--266.

Digital Library

[6]

Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In ICLR.

[7]

Kaize Ding, Elnaz Nouri, Guoqing Zheng, Huan Liu, and White Ryen. 2022a. Toward robust graph semi-supervised learning against extreme data scarcity. arXiv preprint arXiv:2208.12422 (2022).

[8]

Kaize Ding, Jianling Wang, James Caverlee, and Huan Liu. 2022b. Meta propagation networks for graph few-shot semi-supervised learning. AAAI.

[9]

Kaize Ding, Yancheng Wang, Yingzhen Yang, and Huan Liu. 2023. Eliciting Structural and Semantic Global Knowledge in Unsupervised Graph Contrastive Learning. In AAAI.

[10]

Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. 2022c. Data augmentation for deep graph learning: A survey. ACM SIGKDD Explorations Newsletter (2022).

Digital Library

[11]

Kaize Ding, Chuxu Zhang, Jie Tang, Nitesh Chawla, and Huan Liu. 2022d. Toward Graph Minimally-Supervised Learning. In SIGKDD.

[12]

Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. 2021. SLAPS: Self-supervision improves structure learning for graph neural networks. In NeurIPS, Vol. 34. 22667--22681.

[13]

Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. 2020. Graph random neural networks for semi-supervised learning on graphs. In NeurIPS, Vol. 33. 22092--22103.

[14]

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

[15]

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

[16]

Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. 2019b. Diffusion improves graph learning. In NeurIPS, Vol. 32.

[17]

Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, et al. 2021. Utilizing graph machine learning within drug discovery and development. Briefings in bioinformatics, Vol. 22, 6 (2021).

[18]

Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. 2020. Grale: Designing networks for graph learning. In SIGKDD. 2523--2532.

Digital Library

[19]

William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS. 1025--1035.

[20]

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, Vol. 33. 22118--22133.

[21]

Cuiying Huo, Di Jin, Yawen Li, Dongxiao He, Yu-Bin Yang, and Lingfei Wu. 2023. T2-GNN: Graph Neural Networks for Graphs with Incomplete Features and Structure via Teacher-Student Distillation. In AAAI.

[22]

Di Jin, Cuiying Huo, Chundong Liang, and Liang Yang. 2021b. Heterogeneous graph neural network via attribute completion. In WWW. 391--400.

[23]

Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. 2021a. Node similarity preserving graph convolutional networks. In WSDM. 148--156.

[24]

Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020. Graph structure learning for robust graph neural networks. In SIGKDD. 66--74.

[25]

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

[26]

Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. 2019a. Deepgcns: Can gcns go as deep as cnns?. In ICCV. 9267--9276.

[27]

Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI.

[28]

Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. 2019b. Label efficient semi-supervised learning via graph filtering. In CVPR. 9582--9591.

[29]

Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. 2023 a. GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection. In WSDM. 339--347.

[30]

Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. 2022. Towards unsupervised deep graph structure learning. In WWW. 1392--1403.

[31]

Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan. 2023 b. Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating. In AAAI.

[32]

Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. 2021. Tail-gnn: Tail-node graph neural networks. In SIGKDD. 1109--1119.

Digital Library

[33]

Linhao Luo, Gholamreza Haffari, and Shirui Pan. 2023 a. Graph Sequential Neural ODE Process for Link Prediction on Dynamic and Sparse Graphs. In WSDM. 778--786.

[34]

Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. 2023 b. Normalizing Flow-based Neural Process for Few-Shot Knowledge Graph Completion. In SIGIR.

[35]

Peter V Marsden. 1990. Network data and measurement. Annual review of sociology (1990), 435--463.

[36]

Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine, Vol. 29, 3 (2008), 93--93.

[37]

Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of graph neural network evaluation. In NeurIPS Workshop.

[38]

Indro Spinelli, Simone Scardapane, and Aurelio Uncini. 2020. Missing data imputation with adversarially-trained graph convolutional networks. Neural Networks, Vol. 129 (2020), 249--260.

[39]

Ke Sun, Zhouchen Lin, and Zhanxing Zhu. 2020. Multi-stage self-supervised learning for graph convolutional networks on graphs with few labeled nodes. In AAAI, Vol. 34. 5892--5899.

[40]

Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. 2021. Graph convolutional networks for graphs containing missing features. FGCS, Vol. 117 (2021), 155--168.

[41]

Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang. 2023. Federated Learning on Non-IID Graphs via Structural Knowledge Sharing. In AAAI.

[42]

Yue Tan, Guodong Long, Lu Liu, Tianyi Zhou, Qinghua Lu, Jing Jiang, and Chengqi Zhang. 2022a. Fedproto: Federated prototype learning across heterogeneous clients. In AAAI, Vol. 36. 8432--8440.

[43]

Yue Tan, Guodong Long, Jie Ma, Lu Liu, Tianyi Zhou, and Jing Jiang. 2022b. Federated Learning from Pre-Trained Models: A Contrastive Learning Approach. In NeurIPS.

[44]

Laurens Van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE. Journal of machine learning research, Vol. 9, 11 (2008).

[45]

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

[46]

Sheng Wan, Yibing Zhan, Liu Liu, Baosheng Yu, Shirui Pan, and Chen Gong. 2021. Contrastive graph poisson networks: Semi-supervised learning with extremely limited labels. In NeurIPS, Vol. 34. 6316--6327.

[47]

Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. 2019. A semi-supervised graph attentive network for financial fraud detection. In ICDM. IEEE, 598--607.

[48]

Hongwei Wang and Jure Leskovec. 2021. Combining graph convolutional neural networks and label propagation. ACM TOIS, Vol. 40, 4 (2021), 1--27.

Digital Library

[49]

Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. 2021. Graph structure estimation neural networks. In WWW. 342--353.

[50]

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

[51]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks. IEEE TNNLS, Vol. 32, 1 (2021), 4--24.

[52]

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

[53]

Jiaxuan You, Xiaobai Ma, Yi Ding, Mykel J Kochenderfer, and Jure Leskovec. 2020. Handling missing data with graph representation learning. In NeurIPS, Vol. 33. 19075--19087.

[54]

Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. In ICLR.

[55]

He Zhang, Bang Wu, Xiangwen Yang, Chuan Zhou, Shuo Wang, Xingliang Yuan, and Shirui Pan. 2021. Projective ranking: A transferable evasion attack method on graph neural networks. In CIKM. 3617--3621.

[56]

He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. 2022c. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint arXiv:2205.07424 (2022).

[57]

He Zhang, Xingliang Yuan, Chuan Zhou, and Shirui Pan. 2022 e. Projective Ranking-based GNN Evasion Attacks. IEEE TKDE (2022).

[58]

Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In NeurIPS, Vol. 31.

[59]

Wentao Zhang, Zheyu Lin, Yu Shen, Yang Li, Zhi Yang, and Bin Cui. 2022a. Deep and Flexible Graph Neural Architecture Search. In ICML, Vol. 162. PMLR, 26362--26374.

[60]

Wentao Zhang, Zeang Sheng, Ziqi Yin, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. 2022b. Model Degradation Hinders Deep Graph Neural Networks. In SIGKDD. 2493--2503.

[61]

Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. 2022d. Graph Attention Multi-Layer Perceptron. In SIGKDD. 4560--4570.

[62]

Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022a. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082 (2022).

[63]

Xin Zheng, Miao Zhang, Chunyang Chen, Chaojie Li, Chuan Zhou, and Shirui Pan. 2022c. Multi-relational graph neural architecture search with fine-grained message passing. In ICDM. 783--792.

[64]

Xin Zheng, Miao Zhang, Chunyang Chen, Qin Zhang, Chuan Zhou, and Shirui Pan. 2023 a. Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs. In WWW.

[65]

Yizhen Zheng, Shirui Pan, Vincent Lee, Yu Zheng, and Philip S Yu. 2022b. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In NeurIPS, Vol. 35. 10809--10820.

[66]

Yizhen Zheng, He Zhang, Vincent Lee, Yu Zheng, Xiao Wang, and Shirui Pan. 2023 b. Finding the Missing-half: Graph Complementary Learning for Homophily-prone Graphs and Heterophily-prone Graphs. In ICML.

[67]

Yizhen Zheng, Yu Zheng, Xiaofei Zhou, Chen Gong, Vincent CS Lee, and Shirui Pan. 2022d. Unifying Graph Contrastive Learning with Flexible Contextual Scopes. In ICDM. 793--802.

[68]

Hao Zhu and Piotr Koniusz. 2021. Simple spectral graph convolution. In ICLR.

[69]

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. In NeurIPS, Vol. 33. 7793--7804.

[70]

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

[71]

Marinka Zitnik, Rok Sosivc, and Jure Leskovec. 2018. Prioritizing network communities. Nature communications, Vol. 9, 1 (2018), 1--9.

Cited By

Wang LJin D(2024)A Time-Sensitive Graph Neural Network for Session-Based New Item RecommendationElectronics10.3390/electronics1301022313:1(223)Online publication date: 3-Jan-2024
https://doi.org/10.3390/electronics13010223
Ding KNouri EZheng GLiu HWhite R(2024)Toward Robust Graph Semi-Supervised Learning Against Extreme Data ScarcityIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2024.335193835:9(11661-11670)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2024.3351938
Zhang HWu BYuan XPan STong HPei J(2024)Trustworthy Graph Neural Networks: Aspects, Methods, and TrendsProceedings of the IEEE10.1109/JPROC.2024.3369017112:2(97-139)Online publication date: Feb-2024
https://doi.org/10.1109/JPROC.2024.3369017
Show More Cited By

Index Terms

Learning Strong Graph Neural Networks with Weak Information
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Neural networks
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks
Learning and Intelligent Optimization
Abstract
The graph colouring problem consists of assigning labels, or colours, to the vertices of a graph such that no two adjacent vertices share the same colour. In this work we investigate whether deep reinforcement learning can be used to discover a ...
On Graph Learning with Neural Networks
Machine Learning, Optimization, and Data Science
Abstract
Graphs are ideal for modeling natural systems where relations may be intrinsic among data objects. With massive data available, learning graph models from data has become potentially feasible as well as necessary. Yet from the traditional machine ...
Streaming Graph Neural Networks
SIGIR '20: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval

Graphs are used to model pairwise relations between entities in many real-world scenarios such as social networks. Graph Neural Networks(GNNs) have shown their superior ability in learning representations for graph structured data, which leads to ...

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

Amazon Research Award
Australian Research Council

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

6
Total Citations
View Citations
794
Total Downloads

Downloads (Last 12 months)693
Downloads (Last 6 weeks)54

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang LJin D(2024)A Time-Sensitive Graph Neural Network for Session-Based New Item RecommendationElectronics10.3390/electronics1301022313:1(223)Online publication date: 3-Jan-2024
https://doi.org/10.3390/electronics13010223
Ding KNouri EZheng GLiu HWhite R(2024)Toward Robust Graph Semi-Supervised Learning Against Extreme Data ScarcityIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2024.335193835:9(11661-11670)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2024.3351938
Zhang HWu BYuan XPan STong HPei J(2024)Trustworthy Graph Neural Networks: Aspects, Methods, and TrendsProceedings of the IEEE10.1109/JPROC.2024.3369017112:2(97-139)Online publication date: Feb-2024
https://doi.org/10.1109/JPROC.2024.3369017
Qiang BZhou YXu HShi JLin JGao Y(2024)MI-GNN: Multi-Interaction GNN for Various Weak Information Learning on Graphs2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10650021(1-9)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10650021
Zhong MLin MZhang CXu Z(2024)A survey on graph neural networks for intrusion detection systemsComputers and Security10.1016/j.cose.2024.103821141:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cose.2024.103821
Feng ZWu RYang YGao HWang XLiu XHu Q(2024)Multi-level Contrastive Learning on Weak Social Networks for Information Diffusion PredictionDatabase Systems for Advanced Applications10.1007/978-981-97-5572-1_6(84-100)Online publication date: 31-Aug-2024
https://doi.org/10.1007/978-981-97-5572-1_6
Li JXing QWang QChang Y(2023)CVTGAD: Simplified Transformer with Cross-View Attention for Unsupervised Graph-Level Anomaly DetectionMachine Learning and Knowledge Discovery in Databases: Research Track10.1007/978-3-031-43412-9_11(185-200)Online publication date: 18-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43412-9_11

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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