Introduction
Graph node embeddings are fundamental to modern machine learning on graphs, providing low-dimensional vector representations of structural roles. While continuous embedding methods like node2vec and DeepWalk are prevalent, they often require computationally intensive neural networks and lack interpretability. Discrete embeddings offer a faster, more transparent alternative by using actual node IDs or neighborhood attributes. However, discrete methods have historically lacked rigorous theoretical foundations and faced significant scalability issues due to the "Gram matrix" bottleneck.
LoNe Sampler (Local Neighborhood Sampler) addresses these gaps by introducing a suite of algorithms for generating discrete embeddings with provable theoretical guarantees. By utilizing coordinated local neighborhood sampling, LoNe Sampler preserves node similarity while enabling the use of explicit feature maps for scalable training on massive graphs.
The Scalability Challenge
A primary hurdle for discrete embedding methods is the requirement for kernel-based training. Traditional approaches often necessitate computing a Gram matrix—a similarity table for every pair of training points. For large-scale graphs, this matrix grows quadratically, leading to Out-of-Memory (OOM) errors. LoNe Sampler overcomes this by approximating the Hamming kernel through a hashing technique, transforming discrete embeddings into sparse binary vectors suitable for high-speed linear SVMs.
The LoNe Sampler Framework
The core of LoNe Sampler is a "sketching" approach that summarizes a node's $k$-hop neighborhood through coordinated sampling. Unlike independent random walks, this method ensures that nodes with similar neighborhoods are likely to select the same representative sample node.
The framework offers three primary variants:
- $L_0$ (Uniform) Sampling: Every reachable node in the neighborhood has an equal probability of being sampled.
- $L_1$ and $L_2$ (Frequency-based) Sampling: These variants prioritize nodes based on path frequency, capturing structural similarity more effectively. By weighting nodes that are "easily" reachable via multiple paths, $L_1$ and $L_2$ avoid the "identical embedding" trap common in small-diameter graphs where $L_0$ sampling might cause many nodes to appear identical.
The paper provides formal proofs demonstrating that the probability of two nodes sharing a sample is directly proportional to established similarity measures, such as Jaccard or Cosine similarity, of their respective neighborhoods.
Experimental Evaluation
The researchers evaluated LoNe Sampler across diverse datasets, including citation networks (Cora, Citeseer, Pubmed), social/music networks (LastFM, DeezerEurope), and the large-scale GitWebML developer network.
Performance and Accuracy
The $L_1$ and $L_2$ variants consistently outperformed previous state-of-the-art discrete methods like NodeSketch. In node classification tasks, $L_1/L_2$ sampling achieved superior Micro and Macro AUC scores across nearly all tested datasets.
Scalability and Efficiency
The introduction of explicit feature maps proved critical for large-scale applications. On the GitWebML dataset, traditional kernel-based SVMs failed due to memory constraints (OOM). In contrast, LoNe Sampler’s explicit map allowed for training and inference in under 16 seconds.
Conclusion
LoNe Sampler bridges the gap between the interpretability of discrete embeddings and the theoretical rigor of continuous methods. By leveraging frequency-based coordinated sampling and explicit feature maps, it provides a scalable, high-performance solution for graph machine learning. Future work may explore adapting the framework to inductive settings and integrating advanced graph labeling to better capture complex structural roles.
Summary updated