Tracer Propagation: Interpretable Node Embedding

Abstract

Graph analytics, crucial in various domains from social networks to biological systems, has seen a shift towards embedding graph nodes into low-dimensional spaces followed by applying standard machine learning techniques. This paradigm aims to preserve topological node similarity and global network structure in the latent embedding space. We introduce Tracer Propagation, a novel node embedding algorithm which generates interpretable embeddings by propagating continuous values (tracers) across the network, a mechanism inspired by the community detection algorithm Label Propagation. We evaluate Tracer Propagation’s performance primarily in community detection tasks, utilizing K-means on resulting embeddings and comparing against ground-truth communities as well as standard algorithms like Label Propagation and Leiden. Our experiments show promising results on small graphs, demonstrating Tracer Propagation’s effectiveness in capturing community structures and topological similarities. Beyond being only a node embedding algorithm, Tracer Propagation’s interpretability — perhaps its most significant feature — enables defining novel node similarity measures, which can be be fed into traditional optimization-based node embedding algorithms and potentially enhance their performance. As a bonus, we introduce Principal Component Selection (PCS), a simple algorithm for dimensionality reduction promoting interpretability and reducing dataset redundancy.