Abstract: Several state-of-the-art neural graph embedding methods are based on short random walks because of their ease of computation, simplicity in capturing complex local graph properties, scalability, and interpretability. In this work, we study how a probabilistic bias in this stochastic process affects the quality of the nodes picked. Our biased walk favors movement towards nodes whose neighborhoods bear a structural resemblance to the current node's neighborhood, captured via the spectrum of the node's neighborhood subgraph. We propose a paragraph vector model with a novel Wasserstein regularization term and demonstrate significant improvements on link prediction and node classification tasks across diverse real-world datasets.
Introduction
Graph embedding—the process of representing nodes as dense vectors—is fundamental to modern graph machine learning. Most existing methods either rely on heuristics that struggle with scalability or random walk-based models like DeepWalk and node2vec that primarily capture node proximity. The core challenge is that simple random walks are often "blind" to structural similarity; they assume nodes are similar if they are close in the network, missing nodes that perform identical roles but are located far apart. This paper introduces Spectral-Biased Random Walks to bridge this gap by creating a walk process aware of local graph geometry.
Methodology
The authors propose a three-stage pipeline to generate embeddings that prioritize structural similarity over simple proximity:
- Spectral Fingerprinting: For every node, a $k$-hop neighborhood subgraph is extracted to compute the eigenvalues (spectrum) of its normalized Laplacian matrix. This spectrum acts as a mathematical signature of the local structure that is invariant to node labeling.
- Spectral-Biased Random Walks: Instead of moving to a neighbor at random, the walker uses a biased probability to favor neighbors whose neighborhood spectrum is most similar to its own. Similarity is measured using the Wasserstein distance, providing a robust way to compare probability distributions of eigenvalues.
- Wasserstein-Regularized Learning: The resulting walks are treated as "paragraphs" in a document using a Paragraph Vector model. A novel Wasserstein regularization term in the loss function ensures that nodes with structurally similar neighborhoods are mapped close together in the final embedding space.
Empirical Evaluation
The model was evaluated on a wide array of benchmarks, including link prediction on 10 datasets (e.g., US Power grid, Celegans neural network, USAir, and protein interactions) and node classification on standard citation networks like Cora and Citeseer.
The proposed method consistently outperformed state-of-the-art baselines. In link prediction on the difficult Power dataset, the method achieved a 95.60% AUC, significantly higher than the next best competitor (WYS at 89.37%). On Road-Euro, it improved AUC by nearly 7% over the best baseline. In node classification, the method showed a significant lead on Citeseer, reaching 51.8% accuracy compared to 42.6% for node2vec.
Key Insights and Discussion
A central finding of this work is the concept of packing density. The authors demonstrate that biased walks "pack" more structurally relevant nodes into a fixed-length sequence compared to simple random walks. This makes the training data much higher quality for the underlying neural network.
By treating a node's neighborhood as a probability measure and using the Laplacian spectrum, the model identifies "structural twins" even if they are many hops away. Using Wasserstein distance for both the walk bias and the loss regularization allows the model to handle the "geometry" of the spectral distributions more effectively than standard Euclidean metrics.
While the walks themselves are fast, the initial step requires computing the spectrum for every node's $k$-hop neighborhood, which could be a bottleneck for massive graphs. Future work may focus on generalizing the bias function to capture other specific graph properties, such as motifs or community structures, depending on the end task.
Summary updated