2019

Sparse Graph Attention Networks

Ye, Yang, Ji, Shihao

Understand

Graph Neural Networks (GNNs) have proved to be an effective representation learning framework for graph-structured data, and have achieved state-of-the-art performance on many practical predictive tasks, such as node classification, link prediction and graph classification.

Among the variants of GNNs, Graph Attention Networks (GATs) learn to assign dense attention coefficients over all neighbors of a node for feature aggregation, and improve the performance of many graph learning tasks.
However, real-world graphs are often very large and noisy, and GATs are prone to overfitting if not regularized properly.
Even worse, the local aggregation mechanism of GATs may fail on disassortative graphs, where nodes within local neighborhood provide more noise than useful information for feature aggregation.

Built on

W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of Anthropological Research , vol. 33, no. 4, pp. 452–473, 1977
1977
Earlier work this paper cites.
R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” Machine Learning , vol. 8, no. 3-4, pp. 229–256, May 1992
1992
Earlier work this paper cites.
W. W. Zachary, “Assortative mixing in networks,” Physical review letters , vol. 89, no. 20, p. 208701, 2002
2002
Earlier work this paper cites.
P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad, “Collective classification in network data,” AI Magazine , vol. 29, no. 3, pp. 93–106, 2008
2008
Earlier work this paper cites.
L. v. d. Maaten and G. Hinton, “Visualizing data using t-sne,” Journal of Machine Learning Research (JMLR) , vol. 9, no. Nov, pp. 2579–2605, 2008
2008
Earlier work this paper cites.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Transactions on Neural Networks , vol. 20, pp. 61–80, 2009
2009
Earlier work this paper cites.
J. Tang, J. Sun, C. Wang, and Z. Yang, “Social influence analysis in large-scale networks,” in Knowledge Discovery and Data Mining(KDD) , 2009
2009
Earlier work this paper cites.
V. Nair and G. E. Hinton, “Rectified linear units improve restricted boltzmann machines,” in International Conference on Machine Learning (ICML) , 2011
2011
Earlier work this paper cites.
T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in Advances in Neural Information Processing Systems 26 , 2013, pp. 3111–3119
2013
Earlier work this paper cites.
J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” in International Conference on Representation Learning (ICLR) , 2014
2014
Earlier work this paper cites.
B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Knowledge Discovery and Data mining (KDD) , 2014
2014
Earlier work this paper cites.
J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in Empirical Methods in Natural Language Processing (EMNLP) , 2014, pp. 1532–1543
2014
Earlier work this paper cites.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: A simple way to prevent neural networks from overfitting,” Journal of Machine Learning Research , vol. 15, pp. 1929–1958, 2014
2014
Earlier work this paper cites.
J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in International World Wide Web Conference (WWW) , 2015
2015
Earlier work this paper cites.
D. Duvenaud, D. Maclaurin, J. Aguilera-Iparraguirre, R. Gomez-Bombarelli, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in Advances in Neural Information Processing Systems (NIPS) , 2015
2015
Earlier work this paper cites.
S. Cao, W. Lu, and Q. Xu, “Grarep: Learning graph representations with global structural information,” in ACM International on Conference on Information and Knowledge Management (CIKM) , 2015
2015
Earlier work this paper cites.
K. Xu, J. Ba, R. Kiros, K. Cho, A. Courville, R. Salakhutdinov, R. Zemel, and Y. Bengio, “Show, attend and tell: Neural image caption generation with visual attention,” in International Conference on Machine Learning (ICML) , 2015
2015
Earlier work this paper cites.

Similar

D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” in International Conference on Representation Learning (ICLR) , 2015
2015
Cited alongside, same era.
D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in International Conference on Learning Representations (ICLR) , 2015
2015
Cited alongside, same era.
Z. Yang, W. W. Cohen, and R. Salakhutdinov, “Revisiting semi-supervised learning with graph embeddings,” in International Conference on Machine Learning (ICML) , 2016
2016
Cited alongside, same era.
M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in NIPS , 2016
2016
Cited alongside, same era.
M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu, “Asymmetric transitivity preserving graph embedding,” in Knowledge Discovery and Data mining (KDD) , 2016
2016
Cited alongside, same era.
A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Knowledge Discovery and Data mining (KDD) , 2016
2016
Cited alongside, same era.
S. Ji, N. Satish, S. Li, and P. Dubey, “Parallelizing word2vec in multi-core and many-core architectures,” in NIPS workshop on Efficient Methods for Deep Neural Networks , 2016
2016
Cited alongside, same era.
A. Chakeri, H. Farhidzadeh, and L. O. Hall, “Spectral sparsification in spectral clustering,” in International Conference on Learning Representations (ICLR) , 2016
2016
Cited alongside, same era.
M. Zitnik and J. Leskovec, “Predicting multicellular function through multi-layer tissue networks,” Bioinformatics , vol. 33, no. 14, pp. 190–198, 2017
2017
Cited alongside, same era.
R. Van den Berg, T. N. Kipf, and M. Welling, “Graph convolutional matrix completion,” arXiv preprint arXiv:1706.02263 , 2017
Original
2017
Cited alongside, same era.
W. L. Hamilton, R. Ying, and J. Leskovec, “Representation learning on graphs: Methods and applications,” IEEE Data Engineering Bulletin , vol. 40, no. 3, pp. 52–74, 2017
2017
Cited alongside, same era.
T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in International Conference on Learning Representations (ICLR) , 2017
2017
Cited alongside, same era.

Then

D. Calandriello, I. Koutis, A. Lazaric, and M. Valko, “Improved large-scale graph learning through ridge spectral sparsifications,” in International Conference on Machine Learning (ICML) , 2018
2018
Later among the works it cites.
Q. Li, Z. Han, and X.-M. Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” in 32th AAAI Conference on Artificial Intelligence , 2018
2018
Later among the works it cites.
T. Bird, J. Kunze, and D. Barber, “Stochastic variational optimization,” arXiv preprint arXiv:1809.04855 , 2018
Original
2018
Later among the works it cites.
W. Grathwohl, D. Choi, Y. Wu, G. Roeder, and D. Duvenaud, “Backpropagation through the void: Optimizing control variates for black-box gradient estimation,” in International Conference on Learning Representations (ICLR) , 2018
2018
Later among the works it cites.
C. Louizos, M. Welling, and D. P. Kingma, “Learning sparse neural networks through l 0 l_{0} regularization,” in International Conference on Learning Representations (ICLR) , 2018
2018
Later among the works it cites.
O. Shchur, M. Mumme, A. Bojchevski, and S. Gunnemann, “Pitfalls of graph neural network evaluation,” in NeurIPS Workshop on Relational Representation Learning , 2018
2018
Later among the works it cites.
M. Wang, L. Yu, D. Zheng, Q. Gan, Y. Gai, Z. Ye, M. Li, J. Zhou, Q. Huang, C. Ma, Z. Huang, Q. Guo, H. Zhang, H. Lin, J. Zhao, J. Li, A. Smola, , and Z. Zhang, “Deep graph library: Towards efficient and scalable deep learning on graphs,” in ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds , 2019
2019
Closest in time.
D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun, “Measuring and relieving the over-smoothing problem for graph neural networks from the topological view,” in AAAI , 2020
2020
Closest in time.
Y. Rong, W. Huang, T. Xu, and J. Huang, “Dropedge: Towards deep graph convolutional networks on node classification,” in International Conference on Learning Representations (ICLR) , 2020
2020
Closest in time.
A. Hasanzadeh, E. Hajiramezanali, S. Boluki, M. Zhou, N. Duffield, K. Narayanan, and X. Qian, “Bayesian graph neural networks with adaptive connection sampling,” in arXiv preprint arXiv:2006.04064 , 2020
Original
2020
Closest in time.
H. Chen, Y. Xu, F. Huang, Z. Deng, W. Huang, S. Wang, P. He, , and Z. Li, “Label-aware graph convolutional networks,” in Proceedings of the 29th ACM International Conference on Information Knowledge Management , 2020
2020
Closest in time.
C. Zheng, B. Zong, W. Cheng, D. Song, J. Ni, W. Yu, H. Chen, and W. Wang, “Robust graph representation learning via neural sparsification,” in Proceedings of the 37th International Conference on Machine Learning , 2020
2020
Closest in time.
H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang, “Geom-GCN: Geometric graph convolutional networks,” in Knowledge Discovery and Data Mining(KDD) , 2020
2020
Closest in time.
M. Wu, S. Pan, C. Zhou, X. Chang, and X. Zhu, “Unsupervised domain adaptive graph convolutional networks,” in WWW ’20: The Web Conference , 2020
2020
Closest in time.
D. Luo, W. Cheng, W. Yu, B. Zong, J. Ni, H. Chen, and X. Zhang, “Learning to drop: Robust graph neural network via topological denoising,” in Proceedings of the 14th ACM International Conference on Web Search and Data Mining , 2021
2021
Closest in time.
D. Kim and A. Oh, “How to find your friendly neighborhood: Graph attention design with self-supervision,” in International Conference on Learning Representations , 2021
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…