$\ell_1$ Latent Distance based Continuous-time Graph Representation

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 ℓ 2 distance is an important ultra-low-dimensional embedding for CTGR. However, the squared ℓ 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 ℓ 2 distance is infeasible because the corresponding integral computation is intractable. To solve these problems, we propose a theoretically-sound ℓ 1 latent distance based continuous-time graph representation (ℓ 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 closedform piece-wise exponential integral, which well fits the ultra-low-dimensional embedding. To handle the non-differentiable ℓ 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 ℓ 1 LD-CTGR. * Corresponding author. RELATED WORKS AND UNSOLVED PROBLEMS We introduce the preliminary framework based on (C ¸elikkanat et al., 2024), then raise some problems of the currently-used squared ℓ 2 distance. CONTINUOUS-TIME GRAPH REPRESENTATION Denote G := (V, E) as a graph, where V := 1, 2, • • • , N represents the vertex set, and E := ∪ i,j∈V E ij represents the edge set. Here, E ij := (i, j) ∈ V 2 denotes that nodes i and j are connected by an edge. In the continuous-time interval scenario, the time interval [T ] := [0, T ) must also be considered. Correspondingly, a connection between nodes i and j may last from t k ∈ [T ] to t k+1 ∈ [T ]. Therefore, the edge set should be extended to the following set of tuples An event time e m is defined as the time when an edge gets connected or disconnected, with e 0 = 0 always being an event time. If a node pair undergoes M events e 0 = 0 < e 1 < e 2 < • • • < e M -1 < T , then there are M consecutive intervals [e m , e m+1 ) M -1 m=0 , each with different states. The state