Make Each Step Count: Entropic Walker for Compact and Informative Graph Representation Learning

Learning compact and predictive representations that capture critical substructures is fundamental for effective graph learning. However, existing works either risk critical information loss or suffer from the inclusion of task-irrelevant distractors. In this work, we present an information-theoretic formulation for compact graph learning and introduce a tractable, explicit proxy for quantifying structural redundancy. Concretely, our formulation decouples structural complexity from the mutual-information term that is entangled with subgraph diversity, and further aligns the graph compactness objective with the entropy of random walk sequences. This not only avoids direct mutual-information estimation, but also yields an explicit and tractable objective for learning compact predictive substructures. Building on this formulation, we propose Entropic Walker (EW), a framework for learning compact yet predictive graph representations via entropy-controlled random walks, with scalable formulations for both graph-level and node-level tasks. Experiments on 15 benchmarks across diverse applications show consistent performance gains and strong ablation results, highlight the need to rethink the way to measure structural redundancy of graph data.