$\ell_1$ Latent Distance Based Continuous-Time Graph Representation

Abstract

Continuous-time graph representation (CTGR) is a widely-used methodology in machine learning, physics, bioinformatics, and social networks. The sequential survival process in a latent space with the squared $\ell_2$ distance is an important ultra-low-dimensional embedding for CTGR. However, the squared $\ell_2$ distance violates the triangle inequality, which may cause distortion of the relative node positions in the latent space and thus deteriorates in social, contact, and collaboration networks. Reverting to the $\ell_2$ distance is infeasible because the corresponding integral computation is intractable. To solve these problems, we propose a theoretically-sound $\ell_1$ latent distance based continuous-time graph representation ($\ell_1$LD-CTGR). It facilitates a true latent metric space for the sequential survival process. Moreover, the integral of the hazard function is found to be a closed-form piece-wise exponential integral, which well fits the ultra-low-dimensional embedding. To handle the non-differentiable $\ell_1$ norm, we successfully find a descent direction of the hazard function to replace the gradient, enabling mainstream learning architectures to learn the parameters. Extensive experiments using both synthetic and real-world data show the competitive performance of $\ell_1$LD-CTGR.