Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding

Bozhen Hu, Zelin Zang, Jun Xia, Lirong Wu, Cheng Tan, Stan Z. Li

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:

  1. Reconstruction Loss: Maintains the ability to reconstruct the original graph.
  2. 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.

Node clustering performance comparison across benchmark 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.

UMAP visualizations comparing GIC, AGE, and the Proposed method.

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

BibTeX
@inproceedings{hu2023deep,
  author = {Bozhen Hu and Zelin Zang and Jun Xia and Lirong Wu and Cheng Tan and Stan Z. Li},
  title = {{Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10095904},
}
Figure