More Web Proxy on the site http://driver.im/

research-article

Hashing Graph Convolution for Node Classification

Authors:

Jian YangAuthors Info & Claims

CIKM '19: Proceedings of the 28th ACM International Conference on Information and Knowledge Management

Pages 519 - 528

https://doi.org/10.1145/3357384.3357922

Published: 03 November 2019 Publication History

Abstract

Convolution on graphs has aroused great interest in AI due to its potential applications to non-gridded data. To bypass the influence of ordering and different node degrees, the summation/average diffusion/aggregation is often imposed on local receptive field in most prior works. However, the collapsing into one node in this way tends to cause signal entanglements of nodes, which would result in a sub-optimal feature and decrease the discriminability of nodes. To address this problem, in this paper, we propose a simple but effective Hashing Graph Convolution (HGC) method by using global-hashing and local-projection on node aggregation for the task of node classification. In contrast to the conventional aggregation with a full collision, the hash-projection can greatly reduce the collision probability during gathering neighbor nodes. Another incidental effect of hash-projection is that the receptive field of each node is normalized into a common-size bucket space, which not only staves off the trouble of different-size neighbors and their order but also makes a graph convolution run like the standard shape-gridded convolution. Considering the few training samples, also, we introduce a prediction-consistent regularization term into HGC to constrain the score consistency of unlabeled nodes in the graph. HGC is evaluated on both transductive and inductive experimental settings and achieves new state-of-the-art results on all datasets for node classification task. The extensive experiments demonstrate the effectiveness of hash-projection.

References

[1]

James Atwood and Don Towsley. 2016. Diffusion-convolutional neural networks. In Advances in Neural Information Processing Systems. 1993--2001.

[2]

Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014. Spectral Networks and Locally Connected Networks on Graphs. International Conference on Learning Representations (2014).

[3]

John A Bullinaria and Joseph P Levy. 2007. Extracting semantic representations from word co-occurrence statistics: A computational study. Behavior research methods, Vol. 39, 3 (2007), 510--526.

[4]

Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. 2010. Toward an architecture for never-ending language learning. In Twenty-Fourth AAAI Conference on Artificial Intelligence .

Digital Library

[5]

Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In International Conference on Learning Representations .

[6]

Fan RK Chung. 1997. Spectral graph theory . Number 92. American Mathematical society.

[7]

Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. 2010. A sparse johnson: Lindenstrauss transform. In Proceedings of the forty-second ACM symposium on Theory of computing. ACM, 341--350.

Digital Library

[8]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems. 3844--3852.

[9]

Aristides Gionis, Piotr Indyk, Rajeev Motwani, et almbox. 1999. Similarity search in high dimensions via hashing. In International Conference on Very Large Data Bases, Vol. 99. 518--529.

[10]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. 1024--1034.

[11]

Mikael Henaff, Joan Bruna, and Yann LeCun. 2015. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163 (2015).

[12]

Hervé Jégou, Matthijs Douze, Cordelia Schmid, and Patrick Pérez. 2010. Aggregating local descriptors into a compact image representation. In Conference on Computer Vision and Pattern Recognition. IEEE Computer Society, 3304--3311.

[13]

Jiatao Jiang, Zhen Cui, Chunyan Xu, and Jian Yang. 2019. Gaussian-Induced Convolution for Graphs. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence .

[14]

William B Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, Vol. 26, 189--206 (1984), 1.

[15]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (2016).

[16]

Omer Levy and Yoav Goldberg. 2014. Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems. 2177--2185.

[17]

Chaolong Li, Zhen Cui, Wenming Zheng, Chunyan Xu, Rongrong Ji, and Jian Yang. 2018b. Action-attending graphic neural network. IEEE Transactions on Image Processing, Vol. 27, 7 (2018), 3657--3670.

[18]

Chaolong Li, Zhen Cui, Wenming Zheng, Chunyan Xu, and Jian Yang. 2018a. Spatio-temporal graph convolution for skeleton based action recognition. In Thirty-Second AAAI Conference on Artificial Intelligence .

[19]

Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018c. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence .

[20]

Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. 2019. Label Efficient Semi-Supervised Learning via Graph Filtering. In Conference on Computer Vision and Pattern Recognition .

[21]

Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. 2017. Geometric deep learning on graphs and manifolds using mixture model cnns. In Conference on Computer Vision and Pattern Recognition. 5115--5124.

[22]

Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016. Learning convolutional neural networks for graphs. In International conference on machine learning . 2014--2023.

Digital Library

[23]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining . ACM, 701--710.

Digital Library

[24]

Tong Zhang Wenting Zhao Zhen Cui Rong Liu, Chunyan Xu and Jian Yang. 2019. Si-GCN: Structure-induced Graph Convolution Network for Skeleton-based Action Recognition. International Joint Conference on Neural Networks (2019).

[25]

Jorge Sánchez and Florent Perronnin. 2011. High-dimensional signature compression for large-scale image classification. In Conference on Computer Vision and Pattern Recognition. IEEE, 1665--1672.

Digital Library

[26]

Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, Alex Strehl, and Vishy Vishwanathan. 2009. Hash kernels. In Artificial intelligence and statistics . 496--503.

[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]

Tengfei Song, Wenming Zheng, Peng Song, and Zhen Cui. 2018. EEG emotion recognition using dynamical graph convolutional neural networks. IEEE Transactions on Affective Computing (2018).

[29]

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, 1067--1077.

Digital Library

[30]

Andrea Vedaldi and Andrew Zisserman. 2012. Sparse kernel approximations for efficient classification and detection. In Conference on Computer Vision and Pattern Recognition. IEEE, 2320--2327.

[31]

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017).

[32]

Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. 2012. Semi-supervised hashing for large-scale search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 34, 12 (2012), 2393--2406.

Digital Library

[33]

Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et almbox. 2018. A survey on learning to hash. IEEE transactions on pattern analysis and machine intelligence, Vol. 40, 4 (2018), 769--790.

[34]

Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature Hashing for Large Scale Multitask Learning. In Proceedings of the 26th Annual International Conference on Machine Learning. ACM, 1113--1120.

Digital Library

[35]

Bo Wu, Yang Liu, Bo Lang, and Lei Huang. 2017. DGCNN: Disordered Graph Convolutional Neural Network Based on the Gaussian Mixture Model. arXiv preprint arXiv:1712.03563 (2017).

[36]

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation learning on graphs with jumping knowledge networks. arXiv preprint arXiv:1806.03536 (2018).

[37]

Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. 2016. Revisiting Semi-supervised Learning with Graph Embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning, Vol. 48. 40--48.

[38]

Tong Zhang, Wenming Zheng, Zhen Cui, and Yang Li. 2018. Tensor graph convolutional neural network. CoRR, Vol. abs/1803.10071 (2018).

[39]

Chenyi Zhuang and Qiang Ma. 2018. Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification. In Proceedings of the 2018 World Wide Web Conference on World Wide Web. WWW, 499--508.

Digital Library

[40]

Marinka Zitnik and Jure Leskovec. 2017. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, Vol. 33, 14 (2017), i190--i198.

Cited By

Qi QChen S(2023)HV-GCN: Hybrid View Feature Fusion for Graph Convolutional Networks2023 4th International Conference on Computer Engineering and Application (ICCEA)10.1109/ICCEA58433.2023.10135511(884-888)Online publication date: 7-Apr-2023
https://doi.org/10.1109/ICCEA58433.2023.10135511
Luo DZhao DKe QYou XLiu LMa H(2022)Spatiotemporal Hashing Multigraph Convolutional Network for Service-Level Passenger Flow Forecasting in Bus Transit SystemsIEEE Internet of Things Journal10.1109/JIOT.2021.31162419:9(6803-6815)Online publication date: 1-May-2022
https://doi.org/10.1109/JIOT.2021.3116241
Yang DChen CZheng YZheng ZLiao SDemartini GZuccon GCulpepper JHuang ZTong H(2021)Node2GridsProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482456(2281-2290)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482456
Show More Cited By

Index Terms

Hashing Graph Convolution for Node Classification
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Semi-supervised learning

Recommendations

Multi-label graph node classification with label attentive neighborhood convolution
Highlights
- A novel neural network-based method for multi-label graph node classification.
- ...
Abstract
Learning with graph structured data is of great significance for many practical applications. A crucial and fundamental task in graph learning is node classification. In reality, graph nodes are often encoded with various attributes. ...
Label-Consistency based Graph Neural Networks for Semi-supervised Node Classification
SIGIR '20: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval

Graph neural networks (GNNs) achieve remarkable success in graph-based semi-supervised node classification, leveraging the information from neighboring nodes to improve the representation learning of target node. The success of GNNs at node ...
GraFN: Semi-Supervised Node Classification on Graph with Few Labels via Non-Parametric Distribution Assignment
SIGIR '22: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval

Despite the success of Graph Neural Networks (GNNs) on various applications, GNNs encounter significant performance degradation when the amount of supervision signals, i.e., number of labeled nodes, is limited, which is expected as GNNs are trained ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '19: Proceedings of the 28th ACM International Conference on Information and Knowledge Management

November 2019

3373 pages

ISBN:9781450369763

DOI:10.1145/3357384

General Chairs:
Wenwu Zhu
Tsinghua University, China
,
Dacheng Tao
University of Massachusetts, USA
,
Xueqi Cheng
Institute of Computing Technology, CAS, China
,
Program Chairs:
Peng Cui
Tsinghua University, China
,
Elke Rundensteiner
Worcester Polytechnic Institute, USA
,
David Carmel
Amazon Research, USA
,
Qi He
LinkedIn, USA
,
Jeffrey Xu Yu
Chinese University of Hong Kong, China

Copyright © 2019 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 ACM 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: 03 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '19

Sponsor:

CIKM '19: The 28th ACM International Conference on Information and Knowledge Management

November 3 - 7, 2019

Beijing, China

Acceptance Rates

CIKM '19 Paper Acceptance Rate 202 of 1,031 submissions, 20%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
541
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qi QChen S(2023)HV-GCN: Hybrid View Feature Fusion for Graph Convolutional Networks2023 4th International Conference on Computer Engineering and Application (ICCEA)10.1109/ICCEA58433.2023.10135511(884-888)Online publication date: 7-Apr-2023
https://doi.org/10.1109/ICCEA58433.2023.10135511
Luo DZhao DKe QYou XLiu LMa H(2022)Spatiotemporal Hashing Multigraph Convolutional Network for Service-Level Passenger Flow Forecasting in Bus Transit SystemsIEEE Internet of Things Journal10.1109/JIOT.2021.31162419:9(6803-6815)Online publication date: 1-May-2022
https://doi.org/10.1109/JIOT.2021.3116241
Yang DChen CZheng YZheng ZLiao SDemartini GZuccon GCulpepper JHuang ZTong H(2021)Node2GridsProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482456(2281-2290)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482456
Jiang JXu CCui ZZhang TZheng WYang J(2020)Walk-Steered Convolution for Graph ClassificationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2019.295609531:11(4553-4566)Online publication date: Nov-2020
https://doi.org/10.1109/TNNLS.2019.2956095
Zhang XZhang THong XCui ZYang J(2020)Graph Wasserstein Correlation Analysis for Movie RetrievalComputer Vision – ECCV 202010.1007/978-3-030-58595-2_26(424-439)Online publication date: 20-Nov-2020
https://doi.org/10.1007/978-3-030-58595-2_26

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents