Representation learning on networks offers a powerful alternative to the oft painstaking process of manual feature engineering, and, as a result, has enjoyed considerable success in recent years. However, all the existing representation learning methods are based on the first-order network, that is, the network that only captures the pairwise interactions between the nodes. As a result, these methods may fail to incorporate non-Markovian higher order dependencies in the network. Thus, the embeddings that are generated may not accurately represent the underlying phenomena in a network, resulting in inferior performance in different inductive or transductive learning tasks. To address this challenge, this study presents higher order network embedding (HONEM), a higher order network (HON) embedding method that captures the non-Markovian higher order dependencies in a network. HONEM is specifically designed for the HON structure and outperforms other state-of-the-art methods in node classification, network reconstruction, link prediction, and visualization for networks that contain non-Markovian higher order dependencies.
Get full access to this article
View all access options for this article.
References
1.
LichtenwalterRN, LussierJT, ChawlaNV. New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010. pp. 243–252.
2.
GoyalP, FerraraE. Graph embedding techniques, applications, and performance: A survey. Knowl Based Syst, 2018; 151:78–94.
3.
CuiP, WangW, PeiJ, ZhuW. A survey on network embedding. IEEE Trans Knowl Data Eng, 2018; 31:833–852.
4.
RossiRA, JinD, KimS, et al.From community to role-based graph embeddings. arXiv preprint arXiv: 1908.08572, 2019.
5.
GroverA, LeskovecJ. node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016. pp. 855–864.
6.
TangJ, QuM, WangM, et al. Line: Large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015. pp. 1067–1077.
7.
ZhangZ, CuiP, WangX, et al. Arbitrary-order proximity preserved network embedding. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2018. pp. 2778–2786.
8.
OuM, CuiP, PeiJ, et al. Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016. pp. 1105–1114.
9.
RossiRA, AhmedNK, KohE. Higher-order network representation learning. In: Companion of the Web Conference 2018 on the Web Conference 2018. International World Wide Web Conferences Steering Committee, 2018. pp. 3–4.
RosvallM, EsquivelAV, LancichinettiA, et al.Memory in network flows and its effects on spreading dynamics and community detection. Nat Commun, 2014; 5:1–13.
BensonAR, GleichDF, LeskovecJ. Tensor spectral clustering for partitioning higher-order network structures. In: Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 2015. pp. 118–126.
14.
ZhouD, ZhangS, YildirimMY, et al. A local algorithm for structure-preserving graph cut. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017. pp. 655–664.
15.
ZhouD, HeJ, DavulcuH, MaciejewskiR. Motif-preserving dynamic local graph cut. In: 2018 IEEE International Conference on Big Data (Big Data). IEEE, 2018. pp. 1156–1161.
16.
ScholtesI, WiderN, GarasA. Higher-order aggregate networks in the analysis of temporal networks: Path structures and centralities. Eur Phys J B, 2016; 89:61.
17.
ScholtesI, WiderN, PfitznerR, et al.Causality-driven slow-down and speed-up of diffusion in non-markovian temporal networks. Nat Commun, 2014; 5:5024.
18.
SaebiM, XuJ, GreyEK, et al. Higher-order patterns of aquatic species spread through the global shipping network. BioRxiv, p. 704684, 2019.
19.
XuJ, SaebiM, RibeiroB, et al.Detecting anomalies in sequential data with higher-order networks. arXiv preprint arXiv: 1712.09658, 2017.
20.
ScholtesI. When is a network a network? Multi-order graphical model selection in pathways and temporal networks. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2017. pp. 1037–1046.
21.
LambiotteR, RosvallM, ScholtesI. Understanding complex systems: From networks to optimal higher-order models. arXiv preprint arXiv: 1806.05977, 2018.
22.
CaoS, LuW, XuQ. Grarep: Learning graph representations with global structural information. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, 2015. pp. 891–900.
23.
KullbackS, LeiblerRA. On information and sufficiency. Ann Math Stat, 1951; 22:79–86.
24.
PerozziB, Al-RfouR, SkienaS. Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014. pp. 701–710.
25.
EckartC, YoungG. The approximation of one matrix by another of lower rank. Psychometrika, 1936; 1:211–218.
26.
WestR, LeskovecJ. Human wayfinding in information networks. In: Proceedings of the 21st International Conference on World Wide Web. ACM, 2012. pp. 619–628.
27.
AhmedA, ShervashidzeN, NarayanamurthyS. et al. Distributed large-scale natural graph factorization. In: Proceedings of the 22nd International Conference on World Wide Web. ACM, 2013. pp. 37–48.
28.
BelkinM, NiyogiP. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput, 2003; 15:1373–1396.
29.
MaatenLvd, HintonG. Visualizing data using t-SNE. J Mach Learn Res, 2008; 9:2579–2605.
30.
ArenasA, FernandezA, FortunatoS, GomezS. Motif-based communities in complex networks. J Phys A Math Theor, 2008; 41:224001.
KruskalJB, WishM. Multidimensional scaling. In: Sage University Paper Series on Quantitative Applications in the Social Sciences, No. 07-011. Newbury Park: Sage Publications, 1978.
37.
MikolovT, SutskeverI, ChenK, et al.Distributed representations of words and phrases and their compositionality. In: Advances in Neural Information Processing Systems.2013. pp. 3111–3119.
38.
YuH, KulkarniV, WangW. Mohone: Modeling higher order network effects in knowledgegraphs via network infused embeddings. arXiv preprint arXiv: 1811.00198, 2018.
39.
AhmedNK, RossiRA, LeeJB. et al. role2vec: Role-based network embeddings. In: Proceedings of the DLG KDD, 2019.
QiuJ, DongY, MaH, et al. Network embedding as matrix factorization: Unifying deepwalk, line, PTE, and node2vec. In: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. ACM, 2018. pp. 459–467.
42.
TangJ, QuM, MeiQ. PTE: Predictive text embedding through large-scale heterogeneous text networks. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2015. pp. 1165–1174.
RibeiroLF, SaveresePH, FigueiredoDR. struc2vec: Learning node representations from structural identity. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017. pp. 385–394.
45.
HamiltonW, YingZ, LeskovecJ. Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, 2017. pp. 1024–1034.
46.
WangD, CuiP, ZhuW. Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016. pp. 1225–1234.
47.
CaoS, LuW, XuQ. Deep neural networks for learning graph representations. In: AAAI, 2016. pp. 1145–1152.
MaJ, CuiP, ZhuW. Depthlgp: Learning embeddings of out-of-sample nodes in dynamic networks. In: The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), 2018.
52.
YinH, BensonAR, LeskovecJ, GleichDF. Local higher-order graph clustering. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2017. pp. 555–564.
53.
ZuoY, LiuG, LinH, et al. Embedding temporal network via neighborhood formation. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2018. pp. 2857–2866.
54.
ZhouL-K, YangY, RenX, et al.Dynamic network embedding by modeling triadic closure process. In: The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), 2018.
55.
SankarA, WuY, GouL, et al. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In: Proceedings of the 13th International Conference on Web Search and Data Mining, 2020. pp. 519–527.
NguyenGH, LeeJB, RossiRA, et al. Dynamic network embeddings: From random walks to temporal random walks. In: 2018 IEEE International Conference on Big Data (Big Data). IEEE, 2018. pp. 1085–1092.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
