Critical Diffusion: Toward a Self-Organized Critical Principle for Graph Representation Learning

Graph Representation Learning (GRL) has traditionally relied on equilibrium Markovian random walks, such as DeepWalk, to capture structural dependencies in networks. However, these methods operate at a fixed diffusion scale and are inherently biased toward stationary degree-based exploration, potentially overlooking multi-scale and non-equilibrium structural phenomena present in heterogeneous real-world networks. In this work, we introduce SandWalk, a diffusion-based embedding framework grounded in self-organized criticality (SOC). Unlike DeepWalk’s fixed-length random walks, SandWalk generates node sequences from sandpile-induced avalanche cascades. Using the Cora citation network as a case study, we show that the network supports SOC-consistent dynamics, exhibiting heavy-tailed avalanche size and duration distributions. Spectral analysis reveals that SandWalk embeddings display slower singular value decay, higher effective rank, and stronger alignment with the graph Laplacian compared to DeepWalk. Our findings suggest that non-equilibrium critical diffusion provides a principled alternative to equilibrium random-walk sampling in graph representation learning. Beyond theoretical investigations, we evaluate our framework on a practical downstream task, specifically node classification.