ﻻ يوجد ملخص باللغة العربية
Dynamic graph representation learning is a task to learn node embeddings over dynamic networks, and has many important applications, including knowledge graphs, citation networks to social networks. Graphs of this type are usually large-scale but only a small subset of vertices are related in downstream tasks. Current methods are too expensive to this setting as the complexity is at best linear-dependent on both the number of nodes and edges. In this paper, we propose a new method, namely Dynamic Personalized PageRank Embedding (textsc{DynamicPPE}) for learning a target subset of node representations over large-scale dynamic networks. Based on recent advances in local node embedding and a novel computation of dynamic personalized PageRank vector (PPV), textsc{DynamicPPE} has two key ingredients: 1) the per-PPV complexity is $mathcal{O}(m bar{d} / epsilon)$ where $m,bar{d}$, and $epsilon$ are the number of edges received, average degree, global precision error respectively. Thus, the per-edge event update of a single node is only dependent on $bar{d}$ in average; and 2) by using these high quality PPVs and hash kernels, the learned embeddings have properties of both locality and global consistency. These two make it possible to capture the evolution of graph structure effectively. Experimental results demonstrate both the effectiveness and efficiency of the proposed method over large-scale dynamic networks. We apply textsc{DynamicPPE} to capture the embedding change of Chinese cities in the Wikipedia graph during this ongoing COVID-19 pandemic (https://en.wikipedia.org/wiki/COVID-19_pandemic). Our results show that these representations successfully encode the dynamics of the Wikipedia graph.
Network embedding is aimed at mapping nodes in a network into low-dimensional vector representations. Graph Neural Networks (GNNs) have received widespread attention and lead to state-of-the-art performance in learning node representations. However,
There has been an increased interest in discovering heuristics for combinatorial problems on graphs through machine learning. While existing techniques have primarily focused on obtaining high-quality solutions, scalability to billion-sized graphs ha
The potential for machine learning systems to amplify social inequities and unfairness is receiving increasing popular and academic attention. Much recent work has focused on developing algorithmic tools to assess and mitigate such unfairness. Howeve
Timeslices are often used to draw and visualize dynamic graphs. While timeslices are a natural way to think about dynamic graphs, they are routinely imposed on continuous data. Often, it is unclear how many timeslices to select: too few timeslices ca
Graph neural networks (GNN), as a popular methodology for node representation learning on graphs, currently mainly focus on preserving the smoothness and identifiability of node representations. A robust node representation on graphs should further h