TL;DR
This paper introduces SANNE, a novel unsupervised node embedding model that leverages self-attention mechanisms from Transformers to learn node representations. SANNE excels at the "inductive setting," meaning it can generate embeddings for nodes not seen during training, a crucial capability for real-world dynamic graph applications.
What Problem Does This Paper Address?
In many real-world scenarios, data is structured as graphs (e.g., social networks, citation networks). Learning "node embeddings" – dense vector representations of nodes – is vital for downstream tasks like classification or link prediction. However, most existing methods operate in a "transductive setting," requiring the entire graph structure during training. This is problematic for applications where new nodes are constantly added, as these models struggle to generate embeddings for these unseen nodes. The paper addresses this gap by proposing a model that can effectively learn embeddings for both existing and new nodes.
Methods
The core of SANNE is its adaptation of the Transformer's self-attention mechanism for graph data. The process involves:
- Random Walks: Similar to models like DeepWalk, SANNE generates random walks on the graph. Each walk is treated as a sequence of nodes.
- Self-Attention Aggregation: These sequences of nodes (represented by their initial feature vectors) are fed into a stack of Transformer-style attention layers. The self-attention mechanism allows each node in a walk to attend to other nodes in the same walk, effectively aggregating information from its neighbors (and neighbors of neighbors, etc., depending on the walk length and number of attention layers).
- Positional Embeddings: To capture the sequential information within the random walks, positional embeddings are added to the node features.
- Inductive Capability: The model is trained to predict node embeddings for sampled neighbors within the random walks. Crucially, the learned attention mechanism and the inference process (Algorithm 2) allow SANNE to generate embeddings for new nodes by processing their random walks.
Datasets
The paper evaluates SANNE on three standard citation network datasets:
- CORA: 2,708 nodes, 5,429 edges.
- CITESEER: 3,327 nodes, 4,732 edges.
- PUBMED: 19,717 nodes, 44,338 edges.
The data splits follow established practices for fair comparison, with specific sampling strategies for training, validation, and testing sets.
Key Insights and Ideas
- Transformer for Graphs: The paper demonstrates the power of applying self-attention, a technique highly successful in NLP, to the problem of node embedding in graphs.
- Inductive Learning is Key: The ability to generate embeddings for unseen nodes is highlighted as a critical advantage for real-world applications, and SANNE effectively addresses this.
- Random Walks as Sequences: Treating random walks as sequences for a Transformer-like architecture provides a novel way to capture local and structural information.
- Positional Embeddings Matter: Incorporating positional information within the random walks significantly improves performance, suggesting that the order of nodes in a walk carries valuable structural cues.
Key Results
- State-of-the-Art Performance: SANNE achieves state-of-the-art results on node classification tasks for both transductive and inductive settings across the CORA, PUBMED, and CITESEER datasets.
- Inductive Advantage: In the inductive setting, SANNE significantly outperforms previous models like GCN and GAT, showing relative error reductions of over 14%.
- Comparable to Supervised Methods: SANNE's unsupervised approach achieves competitive results, often matching or exceeding semi-supervised methods like GCN and GAT in the transductive setting.
- Robustness: The model shows a smaller performance drop from the transductive to the inductive setting compared to GCN and GAT, underscoring its inductive capability.
Limitations and Future Work
- Ablation Study: The ablation study shows that while the feed-forward sub-layer has a minor impact, the multi-head self-attention sub-layer is crucial for performance. Removing it leads to a significant accuracy drop.
- Hyperparameter Sensitivity: The paper investigates the effects of hyperparameters like the number of random walks (T), attention layers (K), and attention heads (H). While SANNE is generally robust, optimal settings can vary across datasets and settings (transductive vs. inductive).
- Future Work: The paper's success in the inductive setting suggests potential for further exploration in dynamic graph learning and scenarios with evolving network structures. The authors also provide their code for further research.
Summary updated