{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T13:20:40Z","timestamp":1770470440051,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T00:00:00Z","timestamp":1649980800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T00:00:00Z","timestamp":1649980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph is a generic model of various networks in real-world applications. And, graph embedding aims to represent nodes (edges or graphs) as low-dimensional vectors which can be fed into machine learning algorithms for downstream graph analysis tasks. However, existing random walk-based node embedding methods often map some nodes with (dis)similar local structures to (near) far vectors. To overcome this issue, this paper proposes to implement node embedding by constructing a context graph via a new defined ripple distance over ripple vectors, whose components are the hitting times of fully condensed neighborhoods and thus characterize their structures as pure quantities. The distance is able to capture the (dis)similarities of nodes\u2019 local neighborhood structures and satisfies the triangular inequality. The neighbors of each node in the context graph are defined via the ripple distance, which makes the short random walks from a given node over the context graph only visit its similar nodes in the original graph. This property guarantees that the proposed method, named as<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {ripple2vec}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>ripple<\/mml:mi><mml:mn>2<\/mml:mn><mml:mi>vec<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, is able to map (dis)similar nodes to (far) near vectors. Experimental results on real datasets, where labels are mainly related to nodes\u2019 local structures, show that the results of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {ripple2vec}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>ripple<\/mml:mi><mml:mn>2<\/mml:mn><mml:mi>vec<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>behave better than those of state-of-the-art methods, in node clustering and node classification, and are competitive to other methods in link prediction.<\/jats:p>","DOI":"10.1007\/s41019-022-00184-6","type":"journal-article","created":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T12:02:53Z","timestamp":1650024173000},"page":"156-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["ripple2vec: Node Embedding with Ripple Distance of Structures"],"prefix":"10.1007","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3302-3917","authenticated-orcid":false,"given":"Jizhou","family":"Luo","sequence":"first","affiliation":[]},{"given":"Song","family":"Xiao","sequence":"additional","affiliation":[]},{"given":"Shouxu","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Hong","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Yinuo","family":"Xiao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,15]]},"reference":[{"key":"184_CR1","doi-asserted-by":"crossref","unstructured":"Li Enzhi, Le, Zhengyi (2020) Frustrated random walks: a faster algorithm to evaluate node distances on connected and undirected graphs. arXiv:1908.09644v4","DOI":"10.1103\/PhysRevE.102.052135"},{"issue":"9","key":"184_CR2","first-page":"1416","volume":"13","author":"Xuanhe Zhou","year":"2020","unstructured":"Zhou Xuanhe, Sun Ji, Li Guoliang, Feng Jianhua (2020) Query performance prediction for concurrent queries using graph embedding. PVLDB 13(9):1416\u20131428","journal-title":"PVLDB"},{"issue":"9","key":"184_CR3","doi-asserted-by":"publisher","first-page":"1616","DOI":"10.1109\/TKDE.2018.2807452","volume":"30","author":"H Cai","year":"2017","unstructured":"Cai H, Zheng VW, Chang KC (2017) A comprehensive survey of graph embedding: problems, techniques and applications. IEEE Trans Knowledge Data Eng 30(9):1616\u20131637","journal-title":"IEEE Trans Knowledge Data Eng"},{"key":"184_CR4","doi-asserted-by":"crossref","unstructured":"Perozzi B, Al-Rfou R, Skiena S (2014) 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","DOI":"10.1145\/2623330.2623732"},{"key":"184_CR5","doi-asserted-by":"crossref","unstructured":"Tang J, Qu M, Wang M, et al. (2015) Line: Large-scale information network embedding. In: Proceedings of the 24th international conference on world wide web. WWW 2015, pp. 1067-1077","DOI":"10.1145\/2736277.2741093"},{"key":"184_CR6","doi-asserted-by":"crossref","unstructured":"Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks. In: Proceedings of the 22th ACM SIGKDD International conference on Knowledge discovery and data mining. SIGKDD 2016, pp. 855-864","DOI":"10.1145\/2939672.2939754"},{"key":"184_CR7","doi-asserted-by":"crossref","unstructured":"Ribeiro LF, Saverese PH, Figueiredo DR (2017). struc2vec: Learning Node Representations from Structural Identity. In: Proceedings of the 23th ACM SIGKDD international conference on Knowledge discovery and data mining. SIGMOD 2017, pp. 385-394","DOI":"10.1145\/3097983.3098061"},{"key":"184_CR8","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK, Koh E, Kim S, Rao A, Abbasi-Yadkori Y (2020) A structural graph representation learning framework. In: Proceeding of the 13th ACM international conference on web search and data mining. WSDM 2020, pp. 483-491","DOI":"10.1145\/3336191.3371843"},{"key":"184_CR9","doi-asserted-by":"crossref","unstructured":"Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Proceedings of the 22th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM 2016, pp. 1225-1234","DOI":"10.1145\/2939672.2939753"},{"key":"184_CR10","doi-asserted-by":"crossref","unstructured":"2016Cao S, Lu W, Xu Q (2016) Deep neural networks for learning graph representations. In Proceedings of the AAAI conference on artificial intelligence","DOI":"10.1609\/aaai.v30i1.10179"},{"key":"184_CR11","unstructured":"Narayanan A, Chandramohan M, et al. (2017) graph2vec: Learning distributed representations of graphs. arXiv: Artificial Intelligence"},{"issue":"4","key":"184_CR12","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1109\/TCSS.2018.2877083","volume":"5","author":"Palash Goyal","year":"2018","unstructured":"Goyal Palash, Hosseinmardi Homa, Ferrara Emilio, Galstyan Aram (2018) Capturing edge attributes via network embedding. IEEE Trans Comput Soc Syst 5(4):907\u2013917","journal-title":"IEEE Trans Comput Soc Syst"},{"key":"184_CR13","doi-asserted-by":"crossref","unstructured":"Ou M, Cui P, Pei J, Zhang Z, Zhu W (2016). Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM 2016, pp. 1105-1114","DOI":"10.1145\/2939672.2939751"},{"key":"184_CR14","doi-asserted-by":"crossref","unstructured":"Cao S, Lu W, Xu Q (2015). Grarep: Learning graph representations with global structural information. In: Proceedings of the 24th ACM international conference on Information and Knowledge Management. CIKM 2015, pp. 891-900","DOI":"10.1145\/2806416.2806512"},{"key":"184_CR15","doi-asserted-by":"crossref","unstructured":"Park C, Yang C, Zhu Q, Kim D, Yu H, Han J (2020) Unsupervised differentiable multi-aspect network embedding. In: Proceeding of the 26th ACM SIGKDD conference on knowledge discovery and data mining. KDD 2020, pp. 1435-1445","DOI":"10.1145\/3394486.3403196"},{"key":"184_CR16","unstructured":"Chen H, Perozzi B, Hu Y, Skiena S (2017) Harp: Hierarchical representation learning for networks. arXiv preprint arXiv:1706.07845"},{"key":"184_CR17","unstructured":"Chamberlain BP, Clough J, Deisenroth MP (2017) Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359"},{"issue":"12","key":"184_CR18","doi-asserted-by":"publisher","first-page":"2724","DOI":"10.1109\/TKDE.2017.2754499","volume":"29","author":"Q Wang","year":"2017","unstructured":"Wang Q, Mao Z, Wang B, Guo L (2017) Knowledge graph embedding: a survey of approaches and applications. IEEE Trans Knowledge Data Eng 29(12):2724\u20132743","journal-title":"IEEE Trans Knowledge Data Eng"},{"issue":"1","key":"184_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-019-0195-3","volume":"5","author":"Nils M Kriege","year":"2020","unstructured":"Kriege Nils M, Johansson Fredrik D, Morris Christopher (2020) A survey on graph kernels. Appl Netw Sci 5(1):1\u201342","journal-title":"Appl Netw Sci"},{"key":"184_CR20","first-page":"1","volume":"2020","author":"Yanhao Wang","year":"2020","unstructured":"Wang Yanhao, Yuchen Li Ju, Fan Chang Ye, Chai Mingke (2020) A survey of typical attributed graph queries. World Wide Web 2020:1\u201350","journal-title":"World Wide Web"},{"key":"184_CR21","unstructured":"Wu S, Zhang W, Sun F, Cui B (2020) Graph neural networks in recommender systems: a survey. information retrieval. ArXiv Preprint. ArXiv:2011.02260"},{"issue":"1","key":"184_CR22","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00778-019-00556-x","volume":"29","author":"Y Fang","year":"2020","unstructured":"Fang Y, Huang X, Qin L, Zhang Y et al (2020) A survey of community search over big graphs. VLDB J 29(1):353\u201392. https:\/\/doi.org\/10.1007\/s00778-019-00556-x","journal-title":"VLDB J"},{"key":"184_CR23","doi-asserted-by":"crossref","unstructured":"Yu Y, Lu Z, Liu J, Zhao G, Wen J (2019). RUM: Network representation learning using motifs. In: Proceeding of IEEE 35th international conference on data engineering. ICDE 2019, pp. 1382-1393","DOI":"10.1109\/ICDE.2019.00125"},{"issue":"1","key":"184_CR24","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"Shai S Shen-Orr","year":"2002","unstructured":"Shen-Orr Shai S, Milo Ron, Mangan Shmoolik, Alon Uri (2002) Network motifs in the transcriptional regulation network of escherichia coli. Nat Genet 31(1):64\u201368","journal-title":"Nat Genet"},{"issue":"2","key":"184_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3375392","volume":"14","author":"Oh Shin Kijung","year":"2020","unstructured":"Shin Kijung Oh, Sejoon Kim Jisu, Bryan Hooi, Christos Faloutsos (2020) Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans Knowledge Discov Data 14(2):1\u201339","journal-title":"ACM Trans Knowledge Discov Data"},{"key":"184_CR26","doi-asserted-by":"crossref","unstructured":"Grohe M (2020). word2vec, node2vec, graph2vec, X2vec: Towards a theory of vector embeddings of structured data. In: Proceeding of the 39th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems. PODS 2020, pp. 1-16","DOI":"10.1145\/3375395.3387641"},{"issue":"1995","key":"184_CR27","first-page":"212","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial N, London E, Rabinovich Y (1995) The geometry of graphs and some of its algorithmic applications. Combinatorica 15(1995):212\u2013245","journal-title":"Combinatorica"},{"key":"184_CR28","unstructured":"Mikolov, T, Chen K, Corrado G, Dean J (2013). Efficient estimation of word representations in vector space. In: Proceeding of the 1st international conference on learning representations. ICLR 2013. arXiv:1301.3781v3"},{"key":"184_CR29","doi-asserted-by":"crossref","unstructured":"Ohsaka N (2020) The solution distribution of influence maximization: a high-level experimental study on three algorithmic approaches. In: Proceeding of the 2020 international conference on management of data. SIGMOD 2020, pp. 2183-2197","DOI":"10.1145\/3318464.3380564"},{"key":"184_CR30","unstructured":"Rong Y, Huang W, Xu T, Huang J (2020). DropEdge: Towards deep graph convolutional networks on node classification. In: Proceeding of the 8th international conference on learning representations. ICLR 2020"},{"issue":"6","key":"184_CR31","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1162\/089976603321780317","volume":"15","author":"M Belkin","year":"2003","unstructured":"Belkin M, Niyogi P (2003) Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Comput 15(6):1373\u20131396","journal-title":"Neural Comput"},{"issue":"2000","key":"184_CR32","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"J Tenenbaum","year":"2000","unstructured":"Tenenbaum J, De Silva V, Langford J (2000) A global geometric framework for nonlinear dimensionality reduction. Science 290(2000):2319\u20132323","journal-title":"Science"},{"issue":"1","key":"184_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02289565","volume":"29","author":"JB Kruskal","year":"1964","unstructured":"Kruskal JB (1964) Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29(1):1\u201327","journal-title":"Psychometrika"},{"issue":"5500","key":"184_CR34","doi-asserted-by":"publisher","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","volume":"290","author":"ST Roweis","year":"2000","unstructured":"Roweis ST, Saul LK (2000) Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500):2323","journal-title":"Science"},{"key":"184_CR35","doi-asserted-by":"crossref","unstructured":"Fagin R, Lotem A, Naor M (2001) Optimal aggregation algorithm for middleware. In: Proceeding of the 20th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems. PODS 2001","DOI":"10.1145\/375551.375567"},{"key":"184_CR36","unstructured":"Kipf Thomas N, Welling M: (2017) Semi-supervised classification with graph convolutional networks. In: Proceeding of the 5th international conference on learning representation, ICLR 2017"},{"key":"184_CR37","doi-asserted-by":"crossref","unstructured":"Trung HT, Tong VV, Nguyen T, Yin H, Hung N (2020) Adaptive network alignment with unsupervised and multi-order convolutional networks. In: 2020 IEEE 36th international conference on data engineering (icde), IEEE, 2020","DOI":"10.1109\/ICDE48307.2020.00015"},{"key":"184_CR38","doi-asserted-by":"crossref","unstructured":"Singh R, Xu J, Berger B. (2008) Global alignment of multiple protein interaction networks with application to functional orthology detection. In: Proceedings of the National Academy of Sciences of the United States of America. 105.35(2008):12763-12768","DOI":"10.1073\/pnas.0806627105"},{"key":"184_CR39","doi-asserted-by":"crossref","unstructured":"Zhang Si, Tong H. (2016) FINAL: Fast attributed network alignment. In: Acm Sigkdd international conference, ACM 2016","DOI":"10.1145\/2939672.2939766"},{"key":"184_CR40","doi-asserted-by":"crossref","unstructured":"Heimann M et al (2018) REGAL: Representation learning-based graph alignment. ACM 2018","DOI":"10.1145\/3269206.3271788"},{"key":"184_CR41","doi-asserted-by":"crossref","unstructured":"Zhong E, Fan W, Wang J, Xiao L, Li Y (2012). Comsoc: adaptive transfer of user behaviors over composite social network. ACM 2012","DOI":"10.1145\/2339530.2339641"},{"key":"184_CR42","unstructured":"Man T, Shen H, Liu S et al (2016) Predict anchor links across social networks via an embedding approach. AAAI Press, 2016"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00184-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-022-00184-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-022-00184-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T04:58:22Z","timestamp":1675313902000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-022-00184-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,15]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["184"],"URL":"https:\/\/doi.org\/10.1007\/s41019-022-00184-6","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,15]]},"assertion":[{"value":"26 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}