# Topology-induced Operators Reveal Complementary Graph Representations without Training

arXiv: https://arxiv.org/abs/2609.08152 · HTML: https://mlsanity.com/paper/2609.08152/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 43 of its 78 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 30 of 43)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner](https://mlsanity.com/paper/2304.04779/) (2023)
- [AM-GCN: Adaptive Multi-channel Graph Convolutional Networks](https://mlsanity.com/paper/2007.02265/) (2020)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination](https://mlsanity.com/paper/2206.01535/) (2022)
- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [Anonymous Walk Embeddings](https://mlsanity.com/paper/1805.11921/) (2018)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Deep Graph Anomaly Detection: A Survey and New Perspectives](https://mlsanity.com/paper/2409.09957/) (2024)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [GraLSP: Graph Neural Networks with Local Structural Patterns](https://mlsanity.com/paper/1911.07675/) (2019)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [Temporal Link Prediction: A Unified Framework, Taxonomy, and Review](https://mlsanity.com/paper/2210.08765/) (2022)

## Abstract (arXiv)

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.