Random Walk with Centrality and Reversibility for Graph Representation Learning

The application of deep learning methods for modeling graph-structured data has achieved significant theoretical and experimental results. Among these methods, Graph Transformers (GTs) have garnered increasing attention due to their powerful global attention mechanism. However, the existing topological encodings at the node pair level, which provide GTs with rich topological information, still overlook certain graph properties. These oversights can hinder the ability of GTs to learn specific graph inductive biases, ultimately leading to a decline in performance. To address this issue, based on random walk algorithm, we propose Topology Inspired Probabilities (TIP), a novel topological encoding of node pairs that not only contains rich topological information but also directly reflects graph properties. Furthermore, we have designed a powerful injection mechanism to inject TIP into the underlying model. Experimental results demonstrate that our proposed methods assist the base model in achieving higher accuracy.