Graph topology generates strong node embeddings without training
Topology-induced Operators Reveal Complementary Graph Representations without Training
Machine LearningSocial and Information Networks
Summary
Graph learning usually uses complex models that learn how to turn networks into numbers you can analyze. This paper shows that you can get useful graph representations without doing any training, just by carefully using random paths in the network. The authors found two ways to create embeddings that capture different information about the graph structure. These simple, training-free methods work well on multiple tasks and often need less computing power. Combining these methods leads to even better results than using either alone.
What this means in practice
- •For data engineers: Generate graph embeddings for network analysis faster and with less computing without training costly models.
- •For cybersecurity analysts: Capture structural patterns in network graphs quickly to detect anomalies or threats without needing model retraining.
Authors
Meng Qin, Jinqiang Cui, Hongwei Zheng, Weihua Li, Sen Pei
Abstract
Graph representation learning has largely focused on designing increasingly sophisticated models to transform graph topology into vector representations, or embeddings. However, the extent to which embedding quality depends on model learning, rather than on the underlying topological transformations, remains unclear. Here, we show that informative embeddings can be derived without complicated model design and gradient-based training. Propagating random features through implicit hierarchical structures induced by random walks and anonymous walks yields embeddings that capture node proximity and structural role, respectively. These two training-free embeddings preserve complementary aspects of graph organization and perform competitively with classic and recent methods across various node-, edge-, and graph-level tasks. They often require substantially less computation, resulting in a favorable quality-efficiency trade-off. Combining the two types of embeddings further improves inference quality of some tasks compared with using either embedding type alone. Our results suggest that informative graph embeddings can arise from carefully chosen topological transformations before any learning operation is applied.