×

Graph deconvolutional networks. (English) Zbl 1457.68244

Summary: Graphs and networks are very common data structure for modelling complex systems that are composed of a number of nodes and topologies, such as social networks, citation networks, biological protein-protein interactions networks, etc. In recent years, machine learning has become an efficient technique to obtain representation of graph for downstream graph analysis tasks, including node classification, link prediction, and community detection. Different with traditional graph analytical models, the representation learning on graph tries to learn low dimensional embeddings by means of machine learning models that could be trained in supervised, unsupervised or semi-supervised manners. Compared with traditional approaches that directly use input node attributes, these embeddings are much more informative and helpful for graph analysis. There are a number of developed models in this respect, that are different in the ways of measuring similarity of vertexes in both original space and feature space. In order to learn more efficient node representation with better generalization property, we propose a task-independent graph representation model, called as graph deconvolutional network (GDN), and corresponding unsupervised learning algorithm in this paper. Different with graph convolution network (GCN) from the scratch, which produces embeddings by convolving input attribute vectors with learned filters, the embeddings of the proposed GDN model are desired to be convolved with filters so that reconstruct the input node attribute vectors as far as possible. The embeddings and filters are alternatively optimized in the learning procedure. The correctness of the proposed GDN model is verified by multiple tasks over several datasets. The experimental results show that the GDN model outperforms existing alternatives with a big margin.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Eksombatchai, C.; Jindal, P.; Liu, J. Z.; Liu, Y.; Sharma, R.; Sugnet, C.; Ulrich, M.; Leskovec, J., Pixie: a system for recommending 3+ billion items to 200+ million users in real-time, Proceedings of the World Wide Web Conference on World Wide Web, 1775-1784 (2018), International World Wide Web Conferences Steering Committee
[2] Zitnik, M.; Leskovec, J., Predicting multicellular function through multi-layer tissue networks, Bioinformatics, 33, 14, i190-i198 (2017)
[3] Kumar, S.; Hamilton, W. L.; Leskovec, J.; Jurafsky, D., Community interaction and conflict on the web, Proceedings of the World Wide Web Conference on World Wide Web, 933-943 (2018), International World Wide Web Conferences Steering Committee
[4] Ying, R.; He, R.; Chen, K.; Eksombatchai, P.; Hamilton, W. L.; Leskovec, J., Graph convolutional neural networks for web-scale recommender systems, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 974-983 (2018), ACM
[5] Zitnik, M.; Agrawal, M.; Leskovec, J., Modeling polypharmacy side effects with graph convolutional networks, Bioinformatics, 34, 13, i457-i466 (2018)
[6] Hamilton, W. L.; Ying, R.; Leskovec, J., Representation Learning on Graphs: Methods and Applications, IEEE Data Engineering Bulletin, 40, 3, 52-74 (2017)
[7] Yin, H.; Benson, A. R.; Leskovec, J.; Gleich, D. F., Local higher-order graph clustering, Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 555-564 (2017), ACM
[8] Hallac, D.; Vare, S.; Boyd, S.; Leskovec, J., Toeplitz inverse covariance-based clustering of multivariate time series data, Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 215-223 (2017), ACM
[9] Zhang, J.; Hamilton, W. L.; Danescu-Niculescu-Mizil, C.; Jurafsky, D.; Leskovec, J., Community identity and user engagement in a multi-community landscape, Proceedings of the Eleventh International AAAI Conference on Web and Social Media (2017)
[10] Tang, J.; Qu, M.; Wang, M.; Zhang, M.; Yan, J.; Mei, Q., Line: Large-scale information network embedding, Proceedings of the 24th International Conference on World Wide Web, 1067-1077 (2015), International World Wide Web Conferences Steering Committee
[11] Pierson, E.; Corbett-Davies, S.; Goel, S., Fast Threshold Tests for Detecting Discrimination, (Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (2018)), 96-105
[12] Kurashima, T.; Althoff, T.; Leskovec, J., Modeling interdependent and periodic real-world action sequences, Proceedings of the World Wide Web Conference on World Wide Web, 803-812 (2018), International World Wide Web Conferences Steering Committee
[13] Ahmed, A.; Shervashidze, N.; Narayanamurthy, S.; Josifovski, V.; Smola, A. J., Distributed large-scale natural graph factorization, Proceedings of the 22nd International Conference on World Wide Web, 37-48 (2013), ACM
[14] Belkin, M.; Niyogi, P., Laplacian eigenmaps and spectral techniques for embedding and clustering, Proceedings of the Advances in Neural Information Processing Systems, 585-591 (2002)
[15] Ou, M.; Cui, P.; Pei, J.; Zhang, Z.; Zhu, W., Asymmetric transitivity preserving graph embedding, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1105-1114 (2016), ACM
[16] Perozzi, B.; Al-Rfou, R.; Skiena, S., Deepwalk: online learning of social representations, Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 701-710 (2014), ACM
[17] Grover, A.; Leskovec, J., NODE2VEC: scalable feature learning for networks, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 855-864 (2016), ACM
[18] Cao, S.; Lu, W.; Xu, Q., Deep neural networks for learning graph representations, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (2016)
[19] Wang, D.; Cui, P.; Zhu, W., Structural deep network embedding, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1225-1234 (2016), ACM
[20] Hamilton, W.; Ying, Z.; Leskovec, J., Inductive representation learning on large graphs, Proceedings of the Advances in Neural Information Processing Systems, 1024-1034 (2017)
[21] Kipf, T. N.; Welling, M., Semi-Supervised Classification with Graph Convolutional Networks, (5th International Conference on Learning Representations (2017))
[22] Wang, P.; Xu, B.; Wu, Y.; Zhou, X., Link prediction in social networks: the state-of-the-art, Sci. China Inf. Sci., 58, 1, 1-38 (2015)
[23] Zeiler, M. D.; Krishnan, D.; Taylor, G. W.; Fergus, R., Deconvolutional networks., Proceedings of the CVPR, 10, 7 (2010)
[24] Zeiler, M. D.; Taylor, G. W.; Fergus, R., Adaptive deconvolutional networks for mid and high level feature learning., Proceedings of the ICCV, 1, 6 (2011)
[25] Wang, Y.; Yang, J.; Yin, W.; Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1, 3, 248-272 (2008) · Zbl 1187.68665
[26] Z. Yang, W.W. Cohen, R. Salakhutdinov, Revisiting Semi-Supervised Learning with Graph Embeddings, 2016. arXiv:1603.08861.
[27] Hammond, D. K.; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150 (2011) · Zbl 1213.42091
[28] D.I. Shuman, S.K. Narang, P. Frossard, A. Ortega, P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, arXiv:1211.0053 (2012).
[29] Zhang, Z.; Li, M.; Lin, X.; Wang, Y.; He, F., Multistep speed prediction on traffic networks: a deep learning approach considering spatio-temporal dependencies, Transp. Res. Part C: Emerg. Technol., 105, 297-322 (2019)
[30] J. Bruna, W. Zaremba, A. Szlam, Y. LeCun, Spectral Networks and Locally Connected Networks on Graphs, 2013, arXiv:1312.6203.
[31] Defferrard, M.; Bresson, X.; Vandergheynst, P., Convolutional neural networks on graphs with fast localized spectral filtering, Proceedings of the Advances in Neural Information Processing Systems, 3844-3852 (2016)
[32] Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; Bengio, Y., Generative adversarial nets, Proceedings of the Advances in Neural Information Processing Systems, 2672-2680 (2014)
[33] T.N. Kipf, M. Welling, Variational Graph Auto-Encoders 2016, arXiv:1611.07308.
[34] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G.S. Corrado, A. Davis, J. Dean, M. Devin, et al., Tensorflow: Large-scale machine learning on heterogeneous systems, 2015, Software available from tensorflow. org 1(2) (2015).
[35] Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Galligher, B.; Eliassi-Rad, T., Collective classification in network data, AI Mag., 29, 3 (2008), 93-93
[36] Carlson, A.; Betteridge, J.; Kisiel, B.; Settles, B.; Hruschka, E. R.; Mitchell, T. M., Toward an architecture for never-ending language learning, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (2010)
[37] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient Estimation of Word Representations in Vector Space, 2013, arXiv:1301.3781.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.