Introduction
Graph embedding aims to map high-dimensional, non-Euclidean graph data into a low-dimensional latent space. Traditional methods like Graph Auto-Encoders (GAE) and Variational Graph Auto-Encoders (VGAE) primarily focus on minimizing reconstruction error. However, this narrow objective often neglects the underlying topological structure, leading to the "crowding problem"—where nodes from the same class are forced too close together, creating artificial distortions in the latent space.
Methodology: DMVGAE/DMGAE
The proposed Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) addresses these limitations by treating the graph as a manifold.
Geodesic Similarity and t-distribution
The framework preserves node-to-node geodesic similarities, calculating shortest paths for both local and global structures. To convert these distances into similarities, the authors utilize a t-distribution kernel. By tuning the "degree of freedom" ($\nu$), the model controls the separation margin between clusters, effectively mitigating the crowding problem.
Dual Loss Optimization
The model optimizes a joint loss function consisting of:
- Reconstruction Loss: Maintains the ability to reconstruct the original graph.
- Manifold Learning Loss ($L_2$): Ensures that the high-dimensional geodesic similarity is preserved in the low-dimensional latent space.
To ensure scalability, a mini-batch training strategy is employed, reducing computational complexity to $O(K B_s N_n)$.
Experimental Evaluation
The model was evaluated on four benchmark datasets: Cora, CiteSeer, PubMed, and Wiki. These datasets provide ground truth node categories for clustering and link prediction tasks.
Results and Discussion
The proposed methods, DMGAE and DMVGAE, significantly outperform state-of-the-art models in both quantitative metrics and qualitative visualization.
Quantitative Performance
As shown in the table below, DMVGAE achieves substantial gains in node clustering accuracy. For instance, on the Cora dataset, it reaches an ACC of 0.745, a significant improvement over VGAE's 0.560. It consistently outperforms other advanced methods like GIC and ARGA across all four datasets.
Qualitative Visualization
The effectiveness of the manifold learning approach is further evidenced by UMAP visualizations. While competing methods like GIC and AGE result in overlapping clusters or "crowded" blobs, the proposed method produces distinct, well-separated groupings, capturing the true shape of the data.
Conclusion
DMVGAE/DMGAE successfully integrates manifold learning into the graph auto-encoder framework. By prioritizing structural integrity over simple reconstruction, the model achieves superior performance in node clustering and link prediction. Future work will focus on enhancing robustness against noisy data and adversarial attacks.
Summary updated