research-article

Open access

Recurrent Attention Walk for Semi-supervised Classification

Authors:

Uchenna Akujuobi,

Xiangliang ZhangAuthors Info & Claims

WSDM '20: Proceedings of the 13th International Conference on Web Search and Data Mining

Pages 16 - 24

https://doi.org/10.1145/3336191.3371853

Published: 22 January 2020 Publication History

Abstract

In this paper, we study the graph-based semi-supervised learning for classifying nodes in attributed networks, where the nodes and edges possess content information. Recent approaches like graph convolution networks and attention mechanisms have been proposed to ensemble the first-order neighbors and incorporate the relevant neighbors. However, it is costly (especially in memory) to consider all neighbors without a prior differentiation. We propose to explore the neighborhood in a reinforcement learning setting and find a walk path well-tuned for classifying the unlabelled target nodes. We let an agent (of node classification task) walk over the graph and decide where to move to maximize classification accuracy. We define the graph walk as a partially observable Markov decision process (POMDP). The proposed method is flexible for working in both transductive and inductive setting. Extensive experiments on four datasets demonstrate that our proposed method outperforms several state-of-the-art methods. Several case studies also illustrate the meaningful movement trajectory made by the agent.

References

[1]

Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alex Alemi. 2017. Watch your step: Learning graph embeddings through attention. arXiv preprint arXiv:1710.09599 (2017).

[2]

Uchenna Akujuobi, Ke Sun, and Xiangliang Zhang. 2018. Mining top-k Popular Datasets via a Deep Generative Model. In IEEE BigData. IEEE, 584--593.

[3]

Uchenna Akujuobi, Han Yufei, Qiannan Zhang, and Xiangliang Zhang. 2019. Collaborative Graph Walk for Semi-supervised Multi-Label Node Classification. In ICDM.

[4]

Basmah Altaf, Uchenna Akujuobi, Lu Yu, and Xiangliang Zhang. 2019. Dataset Recommendation via Variational Graph Autoencoder. In ICDM.

[5]

Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2018. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering, Vol. 30, 9 (2018), 1616--1637.

Digital Library

[6]

Jie Chen, Tengfei Ma, and Cao Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247 (2018).

[7]

Yujun Chen, Yuanhong Wang, Yutao Zhang, Juhua Pu, and Xiangliang Zhang. 2019. AMENDER: an Attentive and Aggregate Multi-layered Network for Dataset Recommendation. In ICDM.

[8]

Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning phrase representations using RNN encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078 (2014).

[9]

Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. 1990. Indexing by latent semantic analysis. Journal of the American society for information science, Vol. 41, 6 (1990), 391--407.

[10]

Issam Falih, Nistor Grozavu, Rushed Kanawati, and Younès Bennani. 2018. Community detection in attributed network. In Companion Proceedings of the The Web Conference. 1299--1306.

Digital Library

[11]

Hongchang Gao and Heng Huang. 2018. Deep Attributed Network Embedding. In IJCAI. 3364--3370.

[12]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In SIGKDD. ACM, 855--864.

[13]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS. 1024--1034.

[14]

Yedid Hoshen. 2017. Vain: Attentional multi-agent predictive modeling. In NIPS. 2701--2711.

[15]

Xiao Huang, Jundong Li, and Xia Hu. 2017. Label informed attributed network embedding. In WSDM. ACM, 731--739.

[16]

Jiechuan Jiang, Chen Dun, and Zongqing Lu. 2018. Graph Convolutional Reinforcement Learning for Multi-Agent Cooperation. arXiv preprint arXiv:1810.09202 (2018).

[17]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).

[18]

John Boaz Lee, Ryan Rossi, and Xiangnan Kong. 2018a. Graph classification using structural attention. In SIGKDD. ACM, 1666--1674.

[19]

John Boaz Lee, Ryan A Rossi, Sungchul Kim, Nesreen K Ahmed, and Eunyee Koh. 2018b. Attention models in graphs: A survey. arXiv preprint arXiv:1807.07984 (2018).

[20]

John Boaz Lee, Ryan A Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. 2018c. Higher-order Graph Convolutional Networks. arXiv preprint arXiv:1809.07697 (2018).

[21]

Jure Leskovec, A Krevl, and SNAP Datasets. 2014. Stanford large network dataset collection, 2014. URL: http://snap. stanford. edu/data/index. html (2014).

[22]

Lizi Liao, Xiangnan He, Hanwang Zhang, and Tat-Seng Chua. 2018. Attributed social network embedding. IEEE Transactions on Knowledge and Data Engineering, Vol. 30, 12 (2018), 2257--2270.

Digital Library

[23]

Zaiqiao Meng, Shangsong Liang, Hongyan Bao, and Xiangliang Zhang. 2019. Co-Embedding Attributed Networks. In WSDM.

[24]

Bryan Perozzi, Leman Akoglu, Patricia Iglesias Sánchez, and Emmanuel Müller. 2014a. Focused clustering and outlier detection in large attributed graphs. In SIGKDD. ACM, 1346--1355.

[25]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014b. Deepwalk: Online learning of social representations. In SIGKDD. ACM, 701--710.

Digital Library

[26]

Ryan A Rossi, Nesreen K Ahmed, and Eunyee Koh. 2018a. Higher-order network representation learning. In Companion Proceedings of the The Web Conference 2018. 3--4.

Digital Library

[27]

Ryan A Rossi, Rong Zhou, and Nesreen K Ahmed. 2018b. Estimation of Graphlet Counts in Massive Networks. IEEE Transactions on Neural Networks and Learning Systems (2018).

[28]

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. Line: Large-scale information network embedding. In WWW. 1067--1077.

Digital Library

[29]

Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: extraction and mining of academic social networks. In SIGKDD. ACM, 990--998.

[30]

Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. 2018. Attention-based Graph Neural Network for Semi-supervised Learning. arXiv preprint arXiv:1803.03735 (2018).

[31]

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

[32]

Jianlong Wang, Sridhar Rao, Jianlin Chu, Xiaohua Shen, Dana N Levasseur, Thorold W Theunissen, and Stuart H Orkin. 2006. A protein interaction network for pluripotency of embryonic stem cells. nature, Vol. 444, 7117 (2006), 364.

[33]

Ronald J Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, Vol. 8, 3--4 (1992), 229--256.

Digital Library

[34]

Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017. Deeppath: A reinforcement learning method for knowledge graph reasoning. arXiv preprint arXiv:1707.06690 (2017).

[35]

Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Chang. 2015. Network representation learning with rich text information. In IJCAI.

[36]

Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. arXiv preprint arXiv:1603.08861 (2016).

Digital Library

[37]

Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. 2004. Learning with local and global consistency. In NIPS. 321--328.

[38]

Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2018. Graph Neural Networks: A Review of Methods and Applications. arXiv preprint arXiv:1812.08434 (2018).

[39]

Xiaojin Zhu and Zoubin Ghahramani. 2002. Learning from labeled and unlabeled data with label propagation. (2002).

[40]

Chenyi Zhuang and Qiang Ma. 2018. Dual graph convolutional networks for graph-based semi-supervised classification. In WWW. 499--508.

Cited By

Taha K(2023)Semi-supervised and un-supervised clusteringInformation Systems10.1016/j.is.2023.102178114:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.is.2023.102178
Duarte JBerton L(2023)A review of semi-supervised learning for text classificationArtificial Intelligence Review10.1007/s10462-023-10393-856:9(9401-9469)Online publication date: 31-Jan-2023
https://doi.org/10.1007/s10462-023-10393-8
Zhang TShan HLittle M(2022)Causal GraphSAGE: A robust graph method for classification based on causal samplingPattern Recognition10.1016/j.patcog.2022.108696128(108696)Online publication date: Aug-2022
https://doi.org/10.1016/j.patcog.2022.108696
Show More Cited By

Index Terms

Recurrent Attention Walk for Semi-supervised Classification
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Partially-observable Markov decision processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
      2. Semi-supervised learning

Recommendations

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 ...
Multi-view semi-supervised classification via auto-weighted submarkov random walk
Abstract
Semi-supervised classification aims to leverage a small amount of labeled data for learning tasks. Multi-view semi-supervised classification has attracted widespread attention because it can exploit multi-view data to optimize the classification ...
Highlights
- Introduce submarkov random walk to semi-supervised classification.
- A closed-form solution is applied to handle semi-supervised classification.
- Ideal weights are automatically designed for better label indicator.
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '20: Proceedings of the 13th International Conference on Web Search and Data Mining

January 2020

950 pages

ISBN:9781450368223

DOI:10.1145/3336191

General Chairs:
James Caverlee
Texas A&M University
,
Xia "Ben" Hu
Texas A&M University
,
Program Chairs:
Mounia Lalmas
Spotify
,
Wei Wang
University of California, Los Angeles

Copyright © 2020 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: 22 January 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

King Abdullah University of Science and Technology

Conference

WSDM '20

Sponsor:

WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining

February 3 - 7, 2020

TX, Houston, USA

Acceptance Rates

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
555
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)10

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Taha K(2023)Semi-supervised and un-supervised clusteringInformation Systems10.1016/j.is.2023.102178114:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.is.2023.102178
Duarte JBerton L(2023)A review of semi-supervised learning for text classificationArtificial Intelligence Review10.1007/s10462-023-10393-856:9(9401-9469)Online publication date: 31-Jan-2023
https://doi.org/10.1007/s10462-023-10393-8
Zhang TShan HLittle M(2022)Causal GraphSAGE: A robust graph method for classification based on causal samplingPattern Recognition10.1016/j.patcog.2022.108696128(108696)Online publication date: Aug-2022
https://doi.org/10.1016/j.patcog.2022.108696
Gui SZhang XZhong PQiu SWu MYe JWang ZLiu J(2021)PINE: Universal Deep Embedding for Graph Nodes via Partial Permutation Invariant Set FunctionsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2021.3061162(1-1)Online publication date: 2021
https://doi.org/10.1109/TPAMI.2021.3061162

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