Título:
Tracking the adjacency spectral embedding for streaming graphs
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Larroca, Federico
Bermolen, Paola
Fiori, Marcelo
Marenco, Bernardo
Mateos, Gonzalo
Bermolen, Paola
Fiori, Marcelo
Marenco, Bernardo
Mateos, Gonzalo
Tutor:
Tipo de documento:
Ponencia
Editor:
Palabras clave:
Computers
Wireless networks
Estimation
Minimization
Proposals
Matrix decomposition
Iterative methods
Graph representation learning
Node embeddings
Graph sequence
Wireless networks
Estimation
Minimization
Proposals
Matrix decomposition
Iterative methods
Graph representation learning
Node embeddings
Graph sequence
Descriptores:
Año de publicación:
2022
Contenido:
Resumen:
The popular Random Dot Product Graph (RDPG) generative model postulates that each node has an associated (latent) vector, and the probability of existence of an edge between two nodes is their inner-product (with variants to consider directed and weighted graphs). In any case, the latent vectors may be estimated through a spectral decomposition of the adjacency matrix, the so-called Adjacency Spectral Embedding (ASE). Assume we are monitoring a stream of graphs and the objective is to track the latent vectors. Examples include recommender systems or monitoring of a wireless network. It is clear that performing the ASE of each graph separately may result in a prohibitive computation load. Furthermore, the invariance to rotations of the inner product complicates comparing the latent vectors at different time-steps. By considering the minimization problem underlying ASE, we develop an iterative algorithm that updates the latent vectors' estimation as new graphs from the stream arrive. Differently to other proposals, our method does not accumulate errors and thus does not requires periodically re-computing the spectral decomposition. Furthermore, the pragmatic setting where nodes leave or join the graph (e.g. a new product in the recommender system) can be accommodated as well. Our code is available at https://github.com/marfiori/efficient-ASE
Descripción:
Trabajo presentado y publicado en 2022 56th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, 31 oct. - 02 nov. 2022.
metadata.articulos.dc.description.uri:
Editorial:
EN:
Financiadores:
Citación:
Larroca, F., Bermolen, P., Fiori, M. y otros. Tracking the adjacency spectral embedding for streaming graphs [en línea]. Publicado en 2022 56th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, 31 oct. - 02 nov. 2022, pp. 847-851. DOI: 10.1109/IEEECONF56349.2022.10051861.
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Telecomunicaciones
Grupo de investigación:
Análisis de Redes, Tráfico y Estadísticas de Servicios
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| LBFMM22.pdf | Versión final | 406.39 KB | Adobe PDF |