Learning Representations using Spectral-Biased Random Walks on Graphs

Charu Sharma, Jatin Chauhan, Manohar Kaul

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:

  1. 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.
  2. 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.
  3. 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.

Empirical results across multiple datasets demonstrating that Spectral-Biased Walks (SW) consistently capture more structural information than standard Random Walks (RW).

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.

Detail of packing density: structurally similar nodes appear significantly earlier in spectral-biased walks (SW) compared to random walks (RW).

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

Abstract

Several state-of-the-art neural graph embedding methods are based on short random walks (stochastic processes) because of their ease of computation, simplicity in capturing complex local graph properties, scalability, and interpretibility. In this work, we are interested in studying how much a probabilistic bias in this stochastic process affects the quality of the nodes picked by the process. In particular, our biased walk, with a certain probability, favors movement towards nodes whose neighborhoods bear a structural resemblance to the current node's neighborhood. We succinctly capture this neighborhood as a probability measure based on the spectrum of the node's neighborhood subgraph represented as a normalized laplacian matrix. We propose the use of a paragraph vector model with a novel Wasserstein regularization term. We empirically evaluate our approach against several state-of-the-art node embedding techniques on a wide variety of real-world datasets and demonstrate that our proposed method significantly improves upon existing methods on both link prediction and node classification tasks.
BibTeX
@inproceedings{sharma2020learning,
  author = {Charu Sharma and Jatin Chauhan and Manohar Kaul},
  title = {{Learning Representations using Spectral-Biased Random Walks on Graphs}},
  booktitle = {IJCNN},
  year = {2020},
  url = {https://openreview.net/forum?id=w6NkjdvEj0y},
}
Figure