{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T13:52:13Z","timestamp":1718632333661},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100012338","name":"Alan Turing Institute","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012338","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011403","name":"GCHQ","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100011403","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2023,5]]},"abstract":"Abstract<\/jats:title>We propose a decentralised \u201clocal2global<\/jats:italic>\u201d approach to graph representation learning, that one can a-priori use to scale any embedding technique. Our local2global<\/jats:italic> approach proceeds by first dividing the input graph into overlapping subgraphs (or \u201cpatches<\/jats:italic>\u201d) and training local representations for each patch independently. In a second step, we combine the local representations into a globally consistent representation by estimating the set of rigid motions that best align the local representations using information from the patch overlaps, via group synchronization. A key distinguishing feature of local2global<\/jats:italic> relative to existing work is that patches are trained independently without the need for the often costly parameter synchronization during distributed training. This allows local2global<\/jats:italic> to scale to large-scale industrial applications, where the input graph may not even fit into memory and may be stored in a distributed manner. We apply local2global<\/jats:italic> on data sets of different sizes and show that our approach achieves a good trade-off between scale and accuracy on edge reconstruction and semi-supervised classification. We also consider the downstream task of anomaly detection and show how one can use local2global<\/jats:italic> to highlight anomalies in cybersecurity networks.<\/jats:p>","DOI":"10.1007\/s10994-022-06285-7","type":"journal-article","created":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T19:02:34Z","timestamp":1677265354000},"page":"1663-1692","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Local2Global: a distributed approach for scaling representation learning on graphs"],"prefix":"10.1007","volume":"112","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-8941-9227","authenticated-orcid":false,"given":"Lucas G. S.","family":"Jeub","sequence":"first","affiliation":[]},{"given":"Giovanni","family":"Colavizza","sequence":"additional","affiliation":[]},{"given":"Xiaowen","family":"Dong","sequence":"additional","affiliation":[]},{"given":"Marya","family":"Bazzi","sequence":"additional","affiliation":[]},{"given":"Mihai","family":"Cucuringu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"6285_CR1","doi-asserted-by":"crossref","unstructured":"Bojchevski, A., Klicpera, J., Perozzi, B., Kapoor, A., Blais, M., & R\u00f3zemberczki, B., et al. (2020). Scaling graph neural networks with approximate PageRank. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 2464\u20132473). New York: ACM.","DOI":"10.1145\/3394486.3403296"},{"key":"6285_CR2","unstructured":"Busch, J., Pi, J., & Seidl, T. (2020). PushNet: Efficient and adaptive neural message passing. In Proceedings of the 24th European conference on artificial intelligence (pp. 1039\u20131046). The Netherlands: IOS Press."},{"key":"6285_CR3","unstructured":"Chen, J., Ma, T., & Xiao, C. (2018). FastGCN: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the 6th international conference on learning representations"},{"key":"6285_CR4","unstructured":"Chen, J., Zhu, J., & Song, L. (2018). Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th international conference on machine learning (Vol. 80, pp. 942\u2013950). PMLR."},{"key":"6285_CR5","first-page":"14556","volume":"33","author":"M Chen","year":"2020","unstructured":"Chen, M., Wei, Z., Ding, B., Li, Y., Yuan, Y., Du, X., & Wen, J.-R. (2020). Scalable graph neural networks via bidirectional propagation. Advances in Neural Information Processing Systems, 33, 14556\u201314566.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6285_CR6","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3174515","author":"T Chen","year":"2022","unstructured":"Chen, T., Zhou, K., Duan, K., Zheng, W., Wang, P., Hu, X., & Wang, Z. (2022). Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study. IEEE Transactions on Pattern Analysis and Machine Intelligence. https:\/\/doi.org\/10.1109\/TPAMI.2022.3174515","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6285_CR7","doi-asserted-by":"crossref","unstructured":"Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., & Hsieh, C.-J. (2019). Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 257\u2013266). New York: ACM.","DOI":"10.1145\/3292500.3330925"},{"issue":"3","key":"6285_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2240092.2240093","volume":"8","author":"M Cucuringu","year":"2012","unstructured":"Cucuringu, M., Lipman, Y., & Singer, A. (2012). Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Transactions on Sensor Networks, 8(3), 1\u201342.","journal-title":"ACM Transactions on Sensor Networks"},{"issue":"1","key":"6285_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1093\/imaiai\/ias002","volume":"1","author":"M Cucuringu","year":"2012","unstructured":"Cucuringu, M., Singer, A., & Cowburn, D. (2012). Eigenvector synchronization, graph rigidity and the molecule problem. Information and Inference, 1(1), 21\u201367.","journal-title":"Information and Inference"},{"key":"6285_CR10","unstructured":"DARPA OpTC (2020). Darpa operationally transparent cyber (optc) data. https:\/\/github.com\/FiveDirections\/OpTC-data."},{"key":"6285_CR11","doi-asserted-by":"publisher","unstructured":"Dhillon, I. S. (2001). Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining\u2014KDD \u201901. ACM Press. https:\/\/doi.org\/10.1145\/502512.502550","DOI":"10.1145\/502512.502550"},{"key":"6285_CR12","unstructured":"Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the second international conference on knowledge discovery and data mining (pp. 226\u2013231). AAAI Press."},{"key":"6285_CR13","unstructured":"Fey, M., Lenssen, J. E., Weichert, F., & Leskovec, J. (2021). GNNAutoScale: Scalable and expressive graph neural networks via historical embeddings. In M. Meila & T. Zhang (Eds.), Proceedings of the 38th international conference on machine learning (Vol. 139, pp. 3294\u20133304). PMLR. Retrieved from https:\/\/proceedings.mlr.press\/v139\/fey21a.html"},{"key":"6285_CR14","unstructured":"Frasca, F., Rossi, E., Eynard, D., Chamberlain, B., Bronstein, M., & Monti, F. (2020). Sign: Scalable inception graph neural networks. arXiv:2004.11198 [cs.LG]."},{"key":"6285_CR15","first-page":"1025","volume":"31","author":"WL Hamilton","year":"2018","unstructured":"Hamilton, W. L., Ying, R., & Leskovec, J. (2018). Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 31, 1025\u20131035.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6285_CR16","unstructured":"Highnam, K., Arulkumaran, K., Hanif, Z., & Jennings, N. R. (2021). BETH dataset: Real cybersecurity data for anomaly detection research. In ICML 2021 workshop on uncertainty and robustness in deep learning"},{"issue":"7","key":"6285_CR17","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1364\/JOSAA.5.001127","volume":"5","author":"BKP Horn","year":"1988","unstructured":"Horn, B. K. P., Hilden, H. M., & Negahdaripour, S. (1988). Closed-form solution of absolute orientation using orthonormal matrices. Journal of the Optical Society of America A, 5(7), 1127\u20131135.","journal-title":"Journal of the Optical Society of America A"},{"key":"6285_CR18","unstructured":"Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., & Leskovec, J. (2021). OGB-LSC: A large-scale challenge for machine learning on graphs. arXiv:2103.09430 [cs.LG]."},{"key":"6285_CR19","unstructured":"Ioffe, S., & Szegedy, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd international conference on international conference on machine learning\u2013(Vol. 37, pp. 448\u2013456). JMLR.org."},{"key":"6285_CR20","unstructured":"Jeub, L. G. S., Colavizza, G., Dong, X., Bazzi, M., & Cucuringu, M. (2021). Local2global: Scaling global representation learning on graphs via local training. Kdd 2021 workshop on deep learning on graphs."},{"key":"6285_CR21","doi-asserted-by":"crossref","unstructured":"Kairouz, P., & McMahan, H.B. (Eds.). (2021). Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1).","DOI":"10.1561\/2200000083"},{"issue":"1","key":"6285_CR22","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., & Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1), 359\u2013392.","journal-title":"SIAM Journal on Scientific Computing"},{"key":"6285_CR23","unstructured":"Kingma, D.P., & Ba, J.L. (2015). Adam: A method for stochastic optimization. In Proceedings of the 3rd international conference on learning representations."},{"key":"6285_CR24","unstructured":"Kipf, T. N., & Welling, M. (2016). Bayesian deep learning workshop (NIPS: Variational graph auto-encoders)."},{"key":"6285_CR25","unstructured":"Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th international conference on learning representations."},{"key":"6285_CR26","doi-asserted-by":"crossref","unstructured":"Klicpera, J., Bojchevski, A., G\u00fcnnemann, S. (2019). Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the 7th international conference on learning representations.","DOI":"10.1145\/3394486.3403296"},{"key":"6285_CR27","unstructured":"McInnes, L., Healy, J., Melville, J. (2020). Umap: Uniform manifold approximation and projection for dimension reduction. arXiv:1802.03426 [stat.ML]."},{"key":"6285_CR28","unstructured":"Shchur, O., Mumme, M., Bojchevski, A., & G\u00fcnnemann, S. (2019). Pitfalls of graph neural network evaluation. arXiv:1811.05868 [cs.LG]."},{"issue":"1","key":"6285_CR29","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.acha.2010.02.001","volume":"30","author":"A Singer","year":"2011","unstructured":"Singer, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis, 30(1), 20\u201336.","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"6","key":"6285_CR30","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D. A., & Srivastava, N. (2011). Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6), 1913\u20131926.","journal-title":"SIAM Journal on Computing"},{"key":"6285_CR31","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C., Gkantsidis, C., Radunovic, B., Vojnovic, M. (2014). FENNEL: Streaming graph partitioning for massive scale graphs. In Proceedings of the 7th ACM international conference on web search and data mining (pp. 333\u2013342). New Yark: ACM.","DOI":"10.1145\/2556195.2556213"},{"key":"6285_CR32","doi-asserted-by":"publisher","unstructured":"Turcotte, M. J. M., Kent, A. D., & Hash, C. (2018). Unified host and network data set. Security Science and Technology. (pp. 1\u201320). https:\/\/doi.org\/10.1142\/9781786345646001","DOI":"10.1142\/9781786345646001"},{"key":"6285_CR33","unstructured":"Veli\u010dkov\u010d, P., Fedus, W., Hamilton, W. L., Li\u00f3, P., Bengio, Y., & Hjelm, R. D. (2019). Deep graph infomax. In Proceedings of the 7th international conference on learning representations."},{"key":"6285_CR34","unstructured":"Wu, F., Zhang, T., de Souza Jr., A. H., Fifty, C., Yu, T., & Weinberger, K. Q. (2019). Simplifying graph convolutional networks. In Proceedings of the 36th international conference on machine learning (Vol. 97, pp. 6861\u2013 6871). PMLR."},{"issue":"1","key":"6285_CR35","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/tnnls.2020.2978386","volume":"32","author":"Z Wu","year":"2021","unstructured":"Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021). A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1), 4\u201324. https:\/\/doi.org\/10.1109\/tnnls.2020.2978386","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"6285_CR36","unstructured":"Yang, Z., Cohen, W. W., Salakhutdinov, R. (2016). Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd international conference on machine learning (Vol. 48, pp. 40\u201348). PMLR."},{"key":"6285_CR37","doi-asserted-by":"crossref","unstructured":"Zeng, H., Zhou, H., Srivastava, A., Kannan, R., & Prasanna, V. (2019). Accurate, efficient and scalable graph embedding. In 2019 IEEE international parallel and distributed processing symposium (pp. 462\u2013471). New York: IEEE.","DOI":"10.1109\/IPDPS.2019.00056"},{"key":"6285_CR38","unstructured":"Zeng, H., Zhou, H., Srivastava, A., Kannan, R., & Prasanna, V. (2020). Graphsaint: Graph sampling based inductive learning method. In Proceedings of the 8th international conference on learning representations."},{"key":"6285_CR39","unstructured":"Zou, D., Hu, Z., Wang, Y., Jiang, S., Sun, Y., & Gu, Q. (2019). Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in Neural Information Processing Systems (Vol. 32). New York: Curran Associates, Inc."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06285-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06285-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06285-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T16:11:30Z","timestamp":1683303090000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06285-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["6285"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06285-7","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,24]]},"assertion":[{"value":"30 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not Applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not Applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not Applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"All code associated with this paper is publicly available from https:\/\/github.com\/LJeub\/Local2Global_embedding and https:\/\/github.com\/LJeub\/Local2Global.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}