Famá, Martín (2022) Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas / Development of machine learning for network representations. Maestría en Ciencias Físicas, Universidad Nacional de Cuyo, Instituto Balseiro.
![[img]](/style/images/fileicons/application_pdf.png)
| PDF (Tesis) Español 2727Kb |
Resumen en español
Las redes complejas suelen tener un crecimiento no aleatorio, y en muchos casos se pueden describir los mecanismos de crecimiento con modelos. El modelo de crecimiento de redes de Popularidad-Similaridad (PS) asume un espacio hiperbólico de dos dimensiones sobre el cuál crecen las redes. Estas redes sintéticas tienen características estadísticas, específicamente un nivel alto de clustering de los nodos, y también una distribución heterogénea de grados, típico de redes que son scale-free o libres de escala. Una gran variedad de redes reales, como redes de interacciones de proteínas o redes de conexiones entre los routers que distribuyen Internet, muestran cualidades estadísticas similares a las redes sintéticas generadas con el modelo PS. Es entonces un modelo que permite interpretar la información de ciertas redes reales. En ciertos contextos, puede ser de gran utilidad encontrar representaciones compactas de dichas redes complejas. La reducción de dimensionalidad es una herramienta poderosa en el análisis de redes complejas. Trabajando con embeddings, siendo un embedding de nodos de una red un mapeo de los nodos a un espacio vectorial, se puede hacer este mapeo, con particular enfoque en espacios de dimensionalidades bajas. Luego, es posible trabajar sobre este nuevo espacio para inferir información sobre la estructura de la red. Teniendo un modelo que describe una cierta familia de redes, se puede buscar un algoritmo de embedding específico a ese modelo que preserva ciertas propiedades de interés de las redes al mapearlas al nuevo espacio, denominado espacio latente. Que se preserve la estructura viene dado por las posiciones de los vectores en este espacio. Un método que permite inferir información sobre la topología de la red involucra embeddings en donde las distancias vectoriales entre los vectores respectivos de los nodos son representativas de determinados tipos de relación entre esos nodos. Es decir, nodos altamente relacionados en la red tenderán a estar a distancias pequeñas en el espacio latente. Con esta representación, es posible inferir cualidades estadísticas de las redes y aplicaciones como la predicción de enlaces. Este trabajo se enfoca en considerar embeddings a un espacio hiperbólico. Se hace un enfoque en abarcar redes desde el punto de vista del modelo PS. En general, hay un interés creciente en analizar la fuerte relación entre cierto tipos de redes complejas y el espacio hiperbólico. Cuando una red cumple con ciertas cualidades estructurales, es factible modelar y describir dicha red desde el marco de un espacio continuo hiperbólico. Algunas de estas cualidades típicas son por ejemplo tener una distribución de grados de tipo scale-free y tener un nivel alto de clustering, como en el modelo de PS. En particular, se consideran dos algoritmos distintos de embedding, y luego se combinan para lograr que la efectividad de estos embeddings, en cuanto a lograr preservar la micro y macro estructura de la red, sea más alta que cada método por separado, en ciertos casos, considerablemente. El primer método es el Laplacian-based Network Embedding (LaBNE), propuesto por Alanis-Lobato y colaboradores en [1], que asume un espacio inherente hiperbólico para mapear redes a H"2. En particular, asume que las redes son descriptibles por el modelo PS, y se basa en la escala de la distribución de grados para aplicar un re-ordenamiento radial a las coordenadas obtenidas por La- placian Eigenmaps [2], que es un método establecido de reducción de dimensionalidad mediante teoría espectral de grafos. Luego se considera el algoritmo de Poincaré Em-beddings, planteado en [3] por Nickel y Kiela. Este algoritmo se basa en la cualidad hiperbólica de las redes complejas, pero no asume un modelo en particular como el PS. Consiste en actualizar de manera iterada las posiciones de los nodos, en pequeños pasos, asumiendo un geometría diferencial hiperbólica que permite minimizar una función de pérdida, la cual está armada de modo que tiende a decrecer cuando las distancias entre nodos altamente relacionadas son pequeñas en comparación con las distancias entre nodos poco relacionados. El trabajo consiste entonces en una breve introducción al concepto de embeddings en el capítulo 2, con enfoque en el uso del termino referido al análisis de redes complejas en el área de aprendizaje automático. Se presentan los conceptos principales que serían aplicados para vericar la capacidad predictiva de los embeddings, como por ejemplo en hacer predicción de enlaces. Luego, en el capítulo 3 se introducen los aspectos teóricos del espacio hiperbólico que son relevantes para encontrar relaciones entre este espacio y las redes complejas que son de interés. Se ven conceptos como la geometría diferencial del espacio, que luego permite plantear el algoritmo de Poincaré Embeddings, y también equivalencias entre la jerarquía de redes complejas con la forma y estructura de todo el espacio. Al final del capítulo se presenta el modelo de Popularidad-Similaridad, explicando el algoritmo detallado por el modelo para generar redes, junto con una modificación propia de este trabajo generalizando el modelo de 2 dimensiones a n dimensiones, con n arbitrariamente grande. En el capítulo 4 se presentan los dos algoritmos de embedding que se implementan y estudian en este trabajo, LaBNE y Poincaré Embeddings. También se incluye una sección acerca de la implementación en código de todos los algoritmos, con comentarios acerca de las dificultades computacionales de trabajar con redes complejas mayores que cierto tamaño. Finalmente, se tratan resultados en el capítulo 5. En particular, se hace primero un análisis sobre redes sintéticas generadas con PS, vericando el funcionamiento de los algoritmos de embedding y la capacidad de los mismos para preservar la información relevante de las redes. Luego, se pone el enfoque en una red real, en particular la red de Autonomous Systems Internet (ASI). Se generan embeddings de estas redes de distintas características, buscando encontrar los puntos óptimos e indicando las limitaciones de los métodos. Por ultimo, se mencionan líneas de investigación a futuro que se pueden seguir a partir de este trabajo, como por ejemplo estudiar otras redes reales de distintas características y mayor tamaño, y extender los modelos del espacio hiperbólico para encontrar ventajas y desventajas en los distintos modelos.
Resumen en inglés
Complex networks tend to have non-random growth, and in many cases the growth mechanisms can be described with models. The Popularity-Similarity (PS) network growth model assumes a two-dimensional hyperbolic space over which the networks grow. These synthetic networks have statistical characteristics, specifically a high level of node clustering, and also a heterogeneous degree distribution, typical of scale-free networks. A variety of real networks, such as networks of protein interactions or networks of connections between routers that distribute the Internet, exhibit statistical qualities similar to the synthetic networks generated with the PS model. It is therefore a model that allows the interpretation of the information of certain real networks. In certain contexts, it can be very useful to find compact representations of such complex networks. Dimensionality reduction is a powerful tool in the analysis of complex networks. Working with embeddings, being an embedding of nodes of a network a mapping of the nodes to a vector space, this mapping can be done, with particular focus on low dimensionality spaces. Then, it is possible to work on this new space to infer information about the structure of the network. Having a model that describes a certain family of networks, it is possible to find an embedding algorithm specific to that model that preserves certain properties of interest of the networks by mapping them to the new space, called latent space. Whether the structure is preserved is given by the positions of the vectors in this space. One method of inferring information about the topology of the network involves embeddings where the vector distances between the respective vectors of the nodes are representative of certain types of relationships between those nodes. That is, highly related nodes in the network will tend to be at small distances in latent space. With this representation, it is possible to infer statistical qualities of networks and applications such as link prediction. This work focuses on considering embeddings to a hyperbolic space. A focus is made on covering networks from the point of view of the PS model. In general, there is a growing interest in analyzing the strong relationship between certain types of complex networks and hyperbolic space. When a network meets certain structural qualities, it is feasible to model and describe such a network from the framework of a continuous hyperbolic space. Some of these typical qualities are for example having a scale-free degree distribution and having a high level of clustering, as in the PS model. In particular, two different embedding algorithms are considered, and then combined so that the effectiveness of these embeddings, in terms of preserving the micro- and macro-structure of the network, is higher than that of the PS model. The work then consists of a brief introduction to the concept of embeddings in chapter 2, focusing on the use of the term in the analysis of complex networks in the area of machine learning. The main concepts that would be applied to verify the predictive applied to verify the predictive capability of embeddings, such as link prediction. Then, in chapter 3 the theoretical aspects of the hyperbolic space that are relevant to find relationships between this space and the complex networks of interest are introduced. Concepts such as the differential geometry of the space, which then allows the Poincaré Embeddings algorithm to be proposed, and also equivalences between the hierarchy of complex networks with the shape and structure of the whole space, are seen. At the end of the chapter the Popularity-Similarity model is presented, explaining the algorithm detailed by the model to generate lattices, along with a modification specific to this work generalizing the 2-dimensional model ton dimensions, withn arbitrarily large. Chapter 4 presents the two embedding algorithms implemented and studied in this work, LaBNE and Poincaré Embeddings. Also included is a section about the implementation in code of all the algorithms, with comments about the computational difficulties of working with complex networks greater tan a certain size. Finally, results are discussed in Chapter 5. In particular, an analysis is first made on synthetic networks generated with PS, verifying the performance of the embedding algorithms and their ability to preserve the relevant information of the networks. Then, the focus is put on a real network, in particular the Autonomous Systems Internet (ASI) network. Embeddings of these networks of different characteristics are generated, seeking to find the optimal points and indicating the limitations of the methods. limitations of the methods. Finally, future research lines that can be followed from this work are mentioned, such as studying other real networks of different characteristics and larger size, and extending the hyperbolic space models to find advantages and disadvantages in the different models.
| Tipo de objeto: | Tesis (Maestría en Ciencias Físicas) |
|---|---|
| Palabras Clave: | Machine learning; Aprendizaje automático; Algorithms; Algoritmos; [Networks; Redes; ; Hyperbolic; Hiperbólico; Embeddings; Embebidos; Complex networks; Redes complejas] |
| Referencias: | [1] Gregorio Alanis-Lobato, P. M., Andrade-Navarro, M. A. Efficient embedding of complex networks to hyperbolic space via their laplacian. Scientic Reports, 6 (30108), 2016. viii, 3, 21, 29, 44, 53 [2] Belkin, M., Niyogi, P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Neural Information Processing Systems, 14 (14), 585{591, 2001. viii, 21 [3] Nickel, M., Kiela, D. Poincare embeddings for learning hierarchical representations. CoRR, abs/1705.08039, 2017. URL http://arxiv.org/abs/1705.08039. viii, 3, 24, 26, 27, 28, 29, 47, 50, 53 [4] Newman, M. Networks. 2° edicion. Oxford University Press, 2018. 1, 2, 6, 7, 18 [5] Clay, K., Hyun, Y., Keys, K., Fomenkov, M., Krioukov, D. Internet mapping: From art to science. En: 2009 Cybersecurity Applications Technology Conference for Homeland Security, pags. 205{211. 2009. 1, 2 [6] Srinivas V., M. P. Applications of link prediction. En: Link Prediction in Social Networks. SpringerBriefs in Computer Science. Springer, Cham. 2016. 1 [7] Barabasi, A.-L., Albert, R. Emergence of scaling in random networks. Science, 286 (5439), 1999. 2, 17, 18 [8] Papadopoulos, F., et al. Popularity versus similarity in growing networks. Nature, 489 (7417), 537-540, Sep 2012. URL http://dx.doi.org/10.1038/nature11459. 2, 11, 17, 19, 53 [9] Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Boguña, M. Hyperbolic geometry of complex networks. Phys. Rev. E, 82, 036106, Sep 2010. URL https://link.aps.org/doi/10.1103/PhysRevE.82.036106. 2, 16 [10] Krioukov, D., Papadopoulos, F., Vahdat, A., Boguña, M. Curvature and temperature of complex networks. Physical Review E, 80 (3), sep 2009. URL https://doi.org/10.1103%2Fphysreve.80.035101. 2, 16 [11] Muscoloni, A., Thomas, J. M., Ciucci, S., Bianconi, G., Cannistraci, C. V. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature communications, 8 (1), 1615, November 2017. URL https://europepmc.org/articles/PMC5694768. 2 [12] Hamilton, W. L. Graph represenation learning. Synthesis Lectures on Articial Intelligence and Machine Learning, 14 (3), 1-159, 2020. 3, 6 [13] Bernal, E., Rey, A., Villardon, G. Analysis of Madrid Metro Network: From Structural to HJ-Biplot Perspective. Applied Sciences, 10, 08 2020. 3 [14] Insall, M., Rowland, T., Weisstein, E. W. Embedding. URL https://mathworld. wolfram.com/Embedding.html, visitado el 16/11/2022. 5 [15] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., et al. Weisfeiler and leman go neural: Higher-order graph neural networks, 2018. URL https://arxiv.org/abs/1810.02244. 5 [16] Kobourov, S. G. Force-directed drawing algorithms. En: R. Tamassia (ed.) Handbook of Graph Drawing and Visualization, cap. 12. 2013. 6 [17] Fruchterman, T. M. J., Reingold, E. M. Graph drawing by force-directed placement. Software: Practice and Experience, 21 (11), 1129-1164, 1991. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380211102. 7 [18] Biggs, N., Lloyd, E. K., Wilson, R. J. Graph Theory, 1736-1936. USA: Clarendon Press, 1986. 6 [19] Loustau, B. Hyperbolic Geometry (draft). Self-published, 2022. URL https://brice.loustau.eu/book.html. 12 [20] Wikipedia contributors. Heptagrammic-order heptagonal tiling | Wikipedia, The Free Encyclopedia, 2020. URL https://en.wikipedia.org/w/index.php?title=Heptagrammic-order_heptagonal_tiling&oldid=942566442, online; accessed 29-November-2021. 13 [21] Papadopoulos, F., Krioukov, D., Boguña, M., Vahdat, A. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. En: 2010 Proceedings IEEE INFOCOM. IEEE, 2010. URL https://doi.org/10.1109%2Finfcom.2010.5462131. 16 [22] Papadopoulos, F., Psomas, C., Krioukov, D. Network mapping by replaying hyperbolic growth. IEEE/ACM Transactions on Networking, 23 (1), 198-211, Feb 2015. URL http://dx.doi.org/10.1109/TNET.2013.2294052. 16 [23] Kleinberg, R. D. Geographic routing using hyperbolic space. IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, pags. 1902-1909, 2007. 17 [24] Adamic, L. A., Huberman, B. A. Power-law distribution of the world wide web. Science, 287 (2115), 2000. 18 [25] Kovacs, B., Balogh, S. G., Palla, G. Generalised popularity-similarity optimisation model for growing hyperbolic networks beyond two dimensions. Scientic Reports, 12 (1), jan 2022. URL https://doi.org/10.1038%2Fs41598-021-04379-1. 20 [26] Clauset, A., Shalizi, C. R., Newman, M. E. J. Power-law distributions in empirical data. SIAM Review, 51 (4), 661-703, Nov 2009. URL http://dx.doi.org/10.1137/070710111. 21 [27] Bonnabel, S. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 58 (9), 2217-2229, sep 2013. URL https://doi.org/10.1109%2Ftac.2013.2254619. 24 [28] Robbins, H., Monro, S. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22 (3), 400-407, 1951. URL https://doi.org/10.1214/aoms/1177729586. 24 [29] Rumelhart, D. E., Hinton, G. E., Williams, R. J. Learning representations by back-propagating errors. Nature, 323 (6088), 533{536, Oct 1986. URL https://doi.org/10.1038/323533a0. 24 [30] Peng, W., Varanka, T., Mostafa, A., Shi, H., Zhao, G. Hyperbolic deep neural networks: A survey, 2021. URL https://arxiv.org/abs/2101.04562. 25 [31] Understanding ranking loss, contrastive loss, margin loss, triplet loss, hinge loss and all those confusing names. https://gombru.github.io/2019/04/03/ranking_loss/. Accessed: 2022-11-29. 28 [32] Clay, K., Hyun, Y., Keys, K., Fomenkov, M., Krioukov, D. Internet mapping: From art to science. Proceedings - Cybersecurity Applications and Technology Conference for Homeland Security, CATCH 2009, 03 2009. 35, 44, 53 [33] Ross, A. Procrustes analysis. Course report, Department of Computer Science and Engineering, University of South Carolina, 2004. 35 [34] Tabaghi, P., Dokmanic, I. On procrustes analysis in hyperbolic space. IEEE Signal Processing Letters, 28, 1120-1124, 2021. URL https://doi.org/10.1109%2Flsp.2021.3081379. 36 [35] Papadopoulos, F., Aldecoa, R., Krioukov, D. Network geometry inference using common neighbors. Physical Review E, 92 (2), aug 2015. URL https://doi.org/10.1103%2Fphysreve.92.022807. 44 [36] Princeton University "About WordNet.". WordNet. Princeton University. 2010. 50, 54 |
| Materias: | Física > Redes complejas |
| Divisiones: | Gcia. de área de Investigación y aplicaciones no nucleares > Gcia. de Física > Sistemas complejos y altas energías > Física estadística interdisciplinaria |
| Código ID: | 1159 |
| Depositado Por: | Tamara Cárcamo |
| Depositado En: | 08 Mar 2023 15:54 |
| Última Modificación: | 08 Mar 2023 15:54 |
Personal del repositorio solamente: página de control del documento
