Graph embeddings reveal structure without training or complex models
Topology-induced Operators Reveal Complementary Graph Representations without Training
Machine LearningSocial and Information Networks
Summary
The paper explores how graphs—which are networks of connected points—can be represented as numbers without using complex learning algorithms. The authors show that simply using the structure of connections and random paths can create useful summaries of each point in the network. These summaries capture both how close points are to each other and their role in the network, performing well on tasks that identify nodes, edges, or entire graphs. This approach is often faster and combines different perspectives for even better results. It suggests that much useful information is already present in the graph’s shape before any computer learning happens.
graph representation learninggraph embeddingsrandom walksanonymous walksnode proximitystructural roletopological transformationsunsupervised methodsnetwork analysisfeature propagation
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.