Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 12447))
Included in the following conference series:
1529Accesses
Abstract
Unsupervised Graph Embedding yields specific importance because it performs well with inputs limited to the graph structure only. Proximity-preserving models, including link-preserving and Skip-Gram models, prove to be good approaches in both efficiency and accuracy on unsupervised tasks, even compared with state-of-the-art deep models. We first show that the optimization problem these models solve is equivalent to a Bayesian Inference problem, however, these models generally assume a uniform distribution for the target node representations, that is, the representations of nodes are not further constrained. In our paper, we elaborate this Bayesian prior resorting to potential concepts underlying a graph. These graph concepts can be communities in a graph, nodes with different interaction patterns et al. We further derive the optimization objective according to this elaborated prior, and proposed our learning objective. Intuitively, graph nodes of the same concept are embedded close to each other. Our paper proposes a flexible framework which is adaptable to any other proximity-based models. Experiments show that our model significantly elevates the baseline performances of proximity-preserving models, yielding state-of-the-art results on unsupervised learning tasks.
X. Ma and Z. Li—Equal Contribution.
This work was supported by the National Natural Science Foundation of China (Grant No. 61876006).
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
While Skip-Gram models including Deepwalk and node2vec [5] optimize a target embedding and a context embedding for each node, for convenience, we use one matrix\(\mathbf {U}\) to denote node embedding vectors following the first-order setup of [17]. Implementing\(\mathbf {U}\) with two different matrics does not influence the overall framework of our paper.
- 3.
- 4.
Empirically, we divide\(O'_2\) by the representation dimensiond because\(O'_2\) is calculated through summing over all the elements in the representation vectors.
- 5.
We choose Deepwalk as a representative of all Skip-Gram based models including node2vec [5]et al., of which the performance is evaluated analogous to Deepwalk and thus not shown.
- 6.
The same parameters are set for Deepwalk baseline.
- 7.
Macro f1s are not shown, in which a trend similar tomicro f1s is observed.
References
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp.2008(10), P10008 (2008)
Bojchevski, A., Günnemann, S.: Deep Gaussian embedding of graphs: unsupervised inductive learning via ranking. arXiv preprinthttps://arxiv.org/abs/1707.03815 (2017)
Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in Neural Information Processing Systems, vol. 29, pp. 3844–3852 (2016)
Du, L., Lu, Z., Wang, Y., Song, G., Wang, Y., Chen, W.: Galaxy network embedding: a hierarchical community structure preserving approach. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, pp. 2079–2085 (2018)
Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, pp. 855–864. ACM (2016)
Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, vol. 30, pp. 1024–1034 (2017)
Henaff, M., Bruna, J., LeCun, Y.: Deep convolutional networks on graph-structured data. arXiv preprinthttps://arxiv.org/abs/1506.05163 (2015)
Huang, W., Zhang, T., Rong, Y., Huang, J.: Adaptive sampling towards fast graph representation learning. arXiv preprinthttps://arxiv.org/abs/1809.05343 (2018)
Kipf, T.N., Welling, M.: Variational graph auto-encoders. In: Proceedings of NIPS Bayesian Deep Learning Workshop (2016)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations, ICLR 2017 (2017)
Levy, O., Goldberg, Y.: Neural word embedding as implicit matrix factorization. In: Advances in Neural Information Processing Systems, vol. 27, pp. 2177–2185 (2014)
Li, Z., Zhang, L., Song, G.: GCN-LASE: Towards adequately incorporating link attributes in graph convolutional networks. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 (2019)
Li, Z., Zhang, L., Song, G.: SepNE: Bringing separability to network embedding. In: Proceedings of the 33rd AAAI’s Conference on Artificial Intelligence, AAAI 2019 (2019)
Oh, S.J., Murphy, K., Pan, J., Roth, J., Schroff, F.: Modeling uncertainty with hedged instance embedding. arXiv preprinthttps://arxiv.org/abs/1810.00319 (2018)
Perozzi, B., Al-Rfou, R., Skiena, S.: DeepWalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014, pp. 701–710. ACM (2014)
Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., Tang, J.: Network embedding as matrix factorization: unifying DeepWalk, LINE, PTE, and node2vec. In: Proceedings of the 11th ACM International Conference on Web Search and Data Mining, WSDM 2018, pp. 459–467 (2018)
Tang, J., Qu, M., Zhang, M., Mei, Q.: LINE: Large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, WWW 2015, pp. 1067–1077 (2015)
Lei, T., Jin, W., Barzilay, R., Jaakkola, T.: Deriving neural architectures from sequence and graph kernels. In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017 (2017)
Tu, C., Zhang, W., Liu, Z., Sun, M.: Max-margin DeepWalk: discriminative learning of network representation. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI 2016 (2016)
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. arXiv preprinthttps://arxiv.org/abs/1710.10903 (2017)
Wang, D., Cui, P., Zhu, W.: Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, pp. 1225–1234 (2016)
Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? In: Proceedings of the 7th International Conference on Learning Representations, ICLR 2019 (2019)
Yang, C., Liu, Z., Zhao, D., Sun, M., Chang, E.Y.: Network representation learning with rich text information. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, pp. 2111–2117 (2015)
Yang, S., Li, L., Wang, S., Zhang, W., Huang, Q.: A graph regularized deep neural network for unsupervised image representation learning. In: Proceedings of IEEE Conference on Computer Vision & Pattern Recognition, CVPR 2017 (2017)
Zhu, D., Cui, P., Wang, D., Zhu, W.: Deep variational network embedding in Wasserstein space. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018, pp. 2827–2836 (2018)
Author information
Authors and Affiliations
Key Laboratory of Machine Perception, Ministry of Education, Peking University, Beijing, China
Xiaojun Ma & Guojie Song
Center for Data Science, Peking University, Beijing, China
Ziyao Li
School of Electronics Engineering and Computer Science, Peking University, Beijing, China
Siwei Wei
- Xiaojun Ma
You can also search for this author inPubMed Google Scholar
- Ziyao Li
You can also search for this author inPubMed Google Scholar
- Siwei Wei
You can also search for this author inPubMed Google Scholar
- Guojie Song
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toGuojie Song.
Editor information
Editors and Affiliations
Northeastern University, Shenyang, China
Xiaochun Yang
School of Data and Computer Science, Guangzhou, China
Chang-Dong Wang
Griffith University, Southport, QLD, Australia
Md. Saiful Islam
School of Computer Science and Technology, Shenzhen, China
Zheng Zhang
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ma, X., Li, Z., Wei, S., Song, G. (2020). Elaborating the Bayesian Priors in Unsupervised Graph Embedding via Graph Concepts. In: Yang, X., Wang, CD., Islam, M.S., Zhang, Z. (eds) Advanced Data Mining and Applications. ADMA 2020. Lecture Notes in Computer Science(), vol 12447. Springer, Cham. https://doi.org/10.1007/978-3-030-65390-3_15
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-65389-7
Online ISBN:978-3-030-65390-3
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative