{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T23:57:47Z","timestamp":1780444667325,"version":"3.54.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS 1845491"],"award-info":[{"award-number":["IIS 1845491"]}]},{"name":"Army Young Investigator Award","award":["W911NF1810397"],"award-info":[{"award-number":["W911NF1810397"]}]},{"name":"Adobe Digital Experience"},{"name":"Amazon, Facebook and Google"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            While most network embedding techniques model the proximity between nodes in a network, recently there has been significant interest in\n            <jats:italic>structural embeddings<\/jats:italic>\n            that are based on node\n            <jats:italic>equivalences<\/jats:italic>\n            , a notion rooted in sociology: equivalences or positions are collections of nodes that have similar roles\u2014i.e., similar functions, ties or interactions with nodes in other positions\u2014irrespective of their distance or reachability in the network. Unlike the proximity-based methods that are rigorously evaluated in the literature, the evaluation of structural embeddings is less mature. It relies on small synthetic or real networks with labels that are not perfectly defined, and its connection to sociological equivalences has hitherto been vague and tenuous. With new node embedding methods being developed at a breakneck pace,\n            <jats:italic>proper evaluation, and systematic characterization of existing approaches will be essential to progress.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            To fill in this gap, we set out to understand\n            <jats:italic>what<\/jats:italic>\n            types of equivalences structural embeddings capture. We are the first to contribute rigorous intrinsic and extrinsic evaluation methodology for structural embeddings, along with carefully-designed, diverse datasets of varying sizes. We observe a number of different evaluation variables that can lead to different results (e.g., choice of similarity measure, classifier, and label definitions). We find that degree distributions within nodes\u2019 local neighborhoods can lead to simple yet effective baselines in their own right and guide the future development of structural embedding. We hope that our findings can influence the design of further node embedding methods and also pave the way for more comprehensive and fair evaluation of structural embedding methods.\n          <\/jats:p>","DOI":"10.1145\/3481639","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T17:31:28Z","timestamp":1636997488000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Toward Understanding and Evaluating Structural Node Embeddings"],"prefix":"10.1145","volume":"16","author":[{"given":"Junchen","family":"Jin","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Heimann","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Di","family":"Jin","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danai","family":"Koutra","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,11,15]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Proceedings of the Deep Learning on Graphs Knowledge discovery in databases","author":"Ahmed Nesreen K.","year":"2019","unstructured":"Nesreen K. Ahmed, Ryan A. Rossi, John Boaz Lee, Theodore L. Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. 2019. role2vec: Role-based network embeddings. In Proceedings of the Deep Learning on Graphs Knowledge discovery in databases."},{"key":"e_1_3_3_3_2","unstructured":"Amir Bakarov. 2018. A survey of word embeddings evaluation methods. arXiv:1801.09536. Retrieved from http:\/\/arxiv.org\/abs\/1801.09536."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00092"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/270991"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(93)90012-A"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.132"},{"key":"e_1_3_3_8_2","unstructured":"Elizabeth Boschee Jennifer Lautenschlager Sean O\u2019Brien Steve Shellman and James Starz. 2018. ICEWS Automated Daily Event Data . DOI:https:\/\/doi.org\/10.7910\/DVN\/QI2T9A"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2496(75)90028-0"},{"issue":"1","key":"e_1_3_3_10_2","first-page":"D637\u2013D640","article-title":"The BioGRID interaction database: 2008 update","volume":"36","author":"Breitkreutz Bobby-Joe","year":"2008","unstructured":"Bobby-Joe Breitkreutz, Chris Stark, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, Michael Livstone, Rose Oughtred, Daniel H. Lackner, J\u00fcrg B\u00e4hler, Valerie Wood, Kara Dolinski, and Mike Tyers. 2008. The BioGRID interaction database: 2008 update. Nucleic Acids Research 36, suppl 1 (2008), D637\u2013D640.","journal-title":"Nucleic Acids Research"},{"key":"e_1_3_3_11_2","volume-title":"Proceedings of the International Conference on Learning Representations Representation Learning on Graphs and Manifolds Workshop","author":"Cai Chen","year":"2019","unstructured":"Chen Cai and Yusu Wang. 2019. A simple yet effective baseline for non-attributed graph classification. In Proceedings of the International Conference on Learning Representations Representation Learning on Graphs and Manifolds Workshop."},{"key":"e_1_3_3_12_2","volume-title":"Proceedings of the Conference on Information and Knowledge Management","author":"Chen Xiyuan","year":"2020","unstructured":"Xiyuan Chen, Mark Heimann, Fatemeh Vahedian, and Danai Koutra. 2020. Consistent network alignment with node embedding. In Proceedings of the Conference on Information and Knowledge Management."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W16-2501"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3191523"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220025"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313660"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(88)90011-1"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2018.03.022"},{"key":"e_1_3_3_19_2","unstructured":"Palash Goyal Di Huang Ankita Goswami Sujit Rokka Chhetri Arquimedes Canedo and Emilio Ferrara. 2019. Benchmarks for graph embedding evaluation. arXiv:1908.06543. Retrieved from http:\/\/arxiv.org\/abs\/1908.06543."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_3_3_21_2","unstructured":"Saket Gurukar Priyesh Vijayan Aakash Srinivasan Goonmeet Bajaj Chen Cai Moniba Keymanesh Saravana Kumar Pranav Maneriker Anasua Mitra Vedang Patel Balaraman Ravindran and Srinivasan Parthasarathy. 2019. Network representation learning: Consolidation and renewed bearing. arXiv:1905.00987. Retrieved from http:\/\/arxiv.org\/abs\/1905.00987."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976700.20"},{"key":"e_1_3_3_24_2","volume-title":"Proceedings of the International Conference on Complex Networks and Their Applications","author":"Heimann Mark","year":"2020","unstructured":"Mark Heimann, Goran Muri\u0107, and Emilio Ferrara. 2020. Structural node embedding in signed social networks: Finding online misbehavior at multiple scales. In Proceedings of the International Conference on Complex Networks and Their Applications."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00039"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339723"},{"key":"e_1_3_3_28_2","volume-title":"Proceedings of the European Conference on Principles and Practice of Knowledge Discovery in Databases","author":"Jin Di","year":"2019","unstructured":"Di Jin, Mark Heimann, Ryan A. Rossi, and Danai Koutra. 2019. Node2BITS: Compact time- and attribute-aware node representations for user stitching. In Proceedings of the European Conference on Principles and Practice of Knowledge Discovery in Databases."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330735"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330992"},{"key":"e_1_3_3_31_2","unstructured":"Thomas N. Kipf and Max Welling. 2016. Variational graph auto-encoders.  arXiv:1611.07308. Retrieved from http:\/\/arxiv.org\/abs\/1611.07308."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357880"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.026120"},{"key":"e_1_3_3_35_2","first-page":"2177","volume-title":"Proceedings of the 27th International Conference on Advances in Neural Information Processing Systems","author":"Levy Omer","year":"2014","unstructured":"Omer Levy and Yoav Goldberg. 2014. Neural word embedding as implicit matrix factorization. In Proceedings of the 27th International Conference on Advances in Neural Information Processing Systems. 2177\u20132185."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1971.9989788"},{"key":"e_1_3_3_37_2","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Mikolov Tomas","year":"2013","unstructured":"Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Proceedings of the International Conference on Advances in Neural Information Processing Systems."},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the International Conference on Learning Representations Graph Representation Learning Workshop","author":"Morris Christopher","year":"2020","unstructured":"Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. 2020. TUDataset: A collection of benchmark datasets for learning with graphs. In Proceedings of the International Conference on Learning Representations Graph Representation Learning Workshop. Retrieved from www.graphlearning.io."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939782"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2947478"},{"key":"e_1_3_3_41_2","volume-title":"The PageRank Citation Ranking: Bringing Order to the Web.","author":"Page Lawrence","year":"1999","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web.Technical Report 1999-66. Stanford InfoLab. Retrieved from http:\/\/ilpubs.stanford.edu:8090\/422\/. Previous number = SIDL-WP-1999-0120."},{"key":"e_1_3_3_42_2","first-page":"2825","article-title":"Scikit-learn: Machine learning in python","volume":"12","author":"Pedregosa F.","year":"2011","unstructured":"F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, and J. Vanderplas. 2011. Scikit-learn: Machine learning in python. Journal of Machine Learning 12 (2011), 2825\u20132830.","journal-title":"Journal of Machine Learning"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098061"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2349913"},{"issue":"5","key":"e_1_3_3_46_2","first-page":"63:1\u201363:37","article-title":"On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications","volume":"14","author":"Rossi Ryan A.","year":"2020","unstructured":"Ryan A. Rossi, Di Jin, Sungchul Kim, Nesreen K. Ahmed, Danai Koutra, and John Boaz Lee. 2020. On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. ACM Transactions on Knowlege Discovery Data 14, 5 (2020), 63:1\u201363:37. Retrieved from https:\/\/dl.acm.org\/doi\/10.1145\/3397191.","journal-title":"ACM Transactions on Knowlege Discovery Data"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D15-1036"},{"key":"e_1_3_3_48_2","first-page":"2539","article-title":"Weisfeiler-Lehman graph kernels","volume":"12","author":"Shervashidze Nino","year":"2011","unstructured":"Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12, Sep (2011), 2539\u20132561.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220068"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_3_3_52_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_3_53_2","volume-title":"Proceedings of the 2019 IEEE International Conference on Data Mining","author":"Xuewei Ma","year":"2019","unstructured":"Ma Xuewei, Geng Qin, Zhiyang Qiu, Mingxin Zheng, and Zhe Wang. 2019. RiWalk: Fast structural node embedding via role identification. In Proceedings of the 2019 IEEE International Conference on Data Mining. IEEE."},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.160"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976700.19"},{"key":"e_1_3_3_56_2","unstructured":"DRNE codebase. Retrieved on February 2019 from github.com\/tadpole\/DRNE."},{"key":"e_1_3_3_57_2","unstructured":"GCN-VAE codebase. Retrieved on May 2019 from https:\/\/github.com\/tkipf\/gae."},{"key":"e_1_3_3_58_2","unstructured":"GraphWave codebase. Retrieved on May 2019 from github.com\/snap-stanford\/graphwave."},{"key":"e_1_3_3_59_2","unstructured":"LINE codebase. Retrieved on May 2019 from github.com\/tangjianpku\/LINE."},{"key":"e_1_3_3_60_2","unstructured":"MultiLENS codebase. Retrieved on September 2019 from github.com\/GemsLab\/MultiLENS."},{"key":"e_1_3_3_61_2","unstructured":"node2vec codebase. Retrieved on May 2019 from github.com\/aditya-grover\/node2vec."},{"key":"e_1_3_3_62_2","unstructured":"RiWalk codebase. Retrieved on September 2019 from github.com\/maxuewei2\/RiWalk."},{"key":"e_1_3_3_63_2","unstructured":"role2vec codebase. Retrieved on May 2019 from github.com\/benedekrozemberczki\/role2vec."},{"key":"e_1_3_3_64_2","unstructured":"SEGK codebase. Retrieved on February 2020 from github.com\/giannisnik\/segk."},{"key":"e_1_3_3_65_2","unstructured":"struc2vec codebase. Retrieved on May 2019 from github.com\/leoribeiro\/struc2vec."},{"key":"e_1_3_3_66_2","unstructured":"Vertex Similarity codebase. Retrieved on May 2019 from github.com\/tadpole\/DRNE\/blob\/master\/test\/test_VS.py."},{"key":"e_1_3_3_67_2","unstructured":"xNetMF codebase. Retrieved on May 2019 from github.com\/GemsLab\/REGAL."},{"key":"e_1_3_3_68_2","volume-title":"UCINET 6 for Windows: Software for Social Network Analysis","author":"Borgatti S. P.","year":"2002","unstructured":"S. P. Borgatti, M. G. Everett, and L. C. Freeman. 2002. UCINET 6 for Windows: Software for Social Network Analysis. Harvard, MA, Analytic Technologies."},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3481639","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3481639","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3481639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:12Z","timestamp":1750193292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3481639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,15]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3481639"],"URL":"https:\/\/doi.org\/10.1145\/3481639","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,15]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}