Sketching Very Large-scale Dynamic Attributed Networks More Practically

Real-world networks, particularly those in web and social media, are dynamic with evolving node attributes and structures, often involving billions of nodes and edges. Dynamic attributed network embedding is a powerful tool for capturing these changes, enabling data owners and problem owners to better understand interactions and trends for more effective engagement and decision-making. While some existing algorithms are capable of handling very large-scale dynamic attributed networks with billions of nodes and edges, they often suffer from accuracy loss or high computational overhead. In this paper, we propose a practical and sustainable framework of sketching very large-scale dynamic attributed networks called VLS²ketch, which incorporates incremental embedding updates alongside storage-efficient, binarized representation of both node attributes and topological variations. By the sparse random projection technique in an incremental update manner, VLS²ketch significantly reduces the energy-intensive computational workload while maintaining accuracy. Also, we introduce an information decay mechanism, which adapts to temporally varying topologies and node attributes. This mechanism ensures that outdated information gradually diminishes over time. Extensive experiments on real-world very large-scale datasets demonstrate that our proposed VLS²ketch method delivers comparable embedding quality against the state-of-the-art learning-based competitors with dramatically reduced runtime.