MG2Vec+: A multi-headed graph attention network for multigraph embedding
Pages 111 - 132
Abstract
Representation learning of graphs in the form of graph embeddings is an extensively studies area, especially for simple networks, to help with different downstream applications such as node clustering, link prediction, and node classification. In this paper, we propose MG2Vec+, a method that generates node embeddings for a multigraph, a network structure comprising multiple types of edges between pairs of nodes. MG2Vec+ uses multi-headed attention layers to aggregate multiple types of edge-relations that can exist among nodes. The parameters are learned using a graph likelihood loss function which ensures that the sum of attention scores for high-priority nodes is larger as compared to low-priority nodes. We compare MG2Vec+ with nine existing baseline methods after modifying them to our setting on four real-world datasets. MG2Vec+ outperforms the competing methods when evaluated on two downstream tasks: (1) link prediction, and (2) multi-class node classification. It is able to achieve a 5.88% higher AUC-ROC score than the best baseline for link prediction and 9.52% higher classification accuracy than the best baseline for the multi-class node classification task. The superiority of MG2Vec+ can be explained by its principled way of capturing multi-relational contexts and learning them in an unsupervised manner with the same set of parameters using graph likelihood loss.
References
[1]
Abu-El-Haija S, Perozzi B, Al-Rfou R, Alemi A (2017a) Watch your step: learning graph embeddings through attention. CoRR. arXiv:1710.09599
[2]
Adamic LA and Adar E Friends and neighbors on the web Soc Netw 2001 25 211-230
[3]
Backstrom L, Leskovec J (2011) Supervised random walks: predicting and recommending links in social networks. In: WSDM, pp 635–644
[4]
Bhatia V and Rani R Dfuzzy: a deep learning-based fuzzy clustering model for large graphs Knowl Inf Syst 2018 57 1 159-181
[5]
Bruna J, Zaremba W, Szlam A, LeCun Y (2013) Spectral networks and locally connected networks on graphs. CoRR. arXiv:1312.6203
[6]
Chakraborty T, Kumar S, Goyal P, Ganguly N, Mukherjee A (2014) Towards a stratified learning approach to predict future citation counts. In: JCDL, pp 351–360
[7]
Chang S, Han W, Tang J, Qi GJ, Aggarwal CC, Huang TS (2015) Heterogeneous network embedding via deep architectures. In: ACM SIGKDD, pp 119–128
[8]
Chen S, Niu S, Akoglu L, Kovačević J, Faloutsos C (2017) Fast, warped graph embedding: unifying framework and one-click algorithm. arXiv:1702.05764
[9]
Chen H, Yin H, Wang W, Wang H, Nguyen QVH, Li X (2018) PME: projected metric embedding on heterogeneous networks for link prediction. In: ACM SIGKDD, ACM, pp 1177–1186
[10]
Cui Z, Park N, and Chakraborty T Incremental community discovery via latent network representation and probabilistic inference Knowl Inf Syst 2020 62 6 2281-2300
[11]
Dong Y, Chawla NV, Swami A (2017) Metapath2vec: scalable representation learning for heterogeneous networks. In: ACM SIGKDD, pp 135–144
[12]
Grover A, Leskovec J (2016) Node2vec: scalable feature learning for networks. In: ACM SIGKDD, New York, NY, USA, pp 855–864
[13]
Guo Q, Cozzo E, Zheng Z, Moreno Y (2016) Lévy random walks on multiplex networks. Sci Rep 6
[14]
Hamilton WL, Ying R, Leskovec J (2017) Inductive representation learning on large graphs. CoRR. arXiv:1706.02216
[15]
Kipf TN, Welling M (2016) Variational graph auto-encoders. NIPS 2016. arXiv:1611.07308
[16]
Li Y, Tarlow D, Brockschmidt M, Zemel R (2015) Gated graph sequence neural networks. arXiv:1511.05493
[17]
Liao L, He X, Zhang H, and Chua T Attributed social network embedding IEEE Trans Knowl Data Eng 2018 30 12 2257-2270
[18]
Liben-Nowell D and Kleinberg J The link-prediction problem for social networks JASIST 2007 58 7 1019-1031
[19]
Liu W, Chen PY, Yeung S, Suzumura T, Chen L (2017) Principled multilayer network embedding. In: ICDMW pp 134–141
[20]
Liu G, Guo J, Zuo Y, Wu J, and Ry Guo Fraud detection via behavioral sequence embedding Knowl Inf Syst 2020 62 7 2685-2708
[21]
Ma Y, Ren Z, Jiang Z, Tang J, Yin D (2018) Multi-dimensional network embedding with hierarchical structure. In: WSDM, pp 387–395
[22]
Mikolov T, Chen K, Corrado G, Dean J (2013a) Efficient estimation of word representations in vector space. CoRR. arXiv:1301.3781
[23]
Mikolov T, Sutskever I, Chen K, Corrado G, Dean J (2013b) Distributed representations of words and phrases and their compositionality. In: NIPS, pp 3111–3119
[24]
Newman MEJ Clustering and preferential attachment in growing networks Phys Rev E 2001 64 025102
[25]
Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: online learning of social representations. In: ACM SIGKDD, New York, NY, USA, pp 701–710
[26]
Roy A, Kumar V, Mukherjee D, Chakraborty T (2020) Learning multigraph node embeddings using guided lévy flights. In: Pacific–Asia conference on knowledge discovery and data mining. Springer, Berlin, pp 524–537
[27]
Schlichtkrull M, Kipf TN, Bloem P, van den Berg R, Titov I, and Welling M Gangemi A, Navigli R, Vidal ME, Hitzler P, Troncy R, Hollink L, Tordai A, and Alam M Modeling relational data with graph convolutional networks The semantic web 2018 Cham Springer 593-607
[28]
Shi C, Hu B, Zhao WX, and Philip SY Heterogeneous information network embedding for recommendation IEEE TKDE 2019 31 2 357-370
[29]
Snijders TA, Pattison PE, Robins GL, and Handcock MS New specifications for exponential random graph models Sociol Methodol 2006 36 1 99-153
[30]
Tang L and Liu H Leveraging social media networks for classification Data Min Knowl Discov 2010 23 447-478
[31]
Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) Line: large-scale information network embedding. In: WWW, pp 1067–1077
[32]
Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y (2018) Graph attention networks. CoRR. arXiv:1710.10903
[33]
Verbrugge LM Multiplexity in adult friendships Soc Forces 1979 57 4 1286-1309
[34]
Verma J, Gupta S, Mukherjee D, Chakraborty T (2019) Heterogeneous edge embeddings for friend recommendation. arXiv:1902.03124
[35]
You J, Ying R, Ren X, Hamilton WL, Leskovec J (2018) Graphrnn: a deep generative model for graphs. CoRR. arXiv:1802.08773
[36]
Zhang H, Qiu L, Yi L, Song Y (2018) Scalable multiplex network embedding. In: IJCAI, pp 3082–3088
Recommendations
Improving node embedding by a compact neighborhood representation
AbstractGraph Embedding, a learning paradigm that represents graph vertices, edges, and other semantic information about a graph into low-dimensional vectors, has found wide applications in different machine learning tasks. In the past few years, we have ...
Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
Consider an undirected multigraph G = ( V,E ) with n vertices and m edges, and let N i denote the number of connected spanning subgraphs with i ( m ≥ i ≥ n ) edges in G . Recently, we showed in [3] the validity of ( m - i + 1) N i -1 > ( i-n + ⌊3+√9+...
Space-invariant projection in streaming network embedding
AbstractThe introduction of new nodes in dynamic networks gradually leads to drift in the node embedding space, and the retraining of node embeddings and downstream models is indispensable. The exact threshold of these new nodes, below which ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 26 September 2022
Accepted: 30 April 2022
Revision received: 24 April 2022
Received: 28 October 2020
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in