Deep Manifold Graph Auto-Encoder For Attributed Graph Embedding

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

TL;DR

The paper introduces DMVGAE/DMGAE, a novel framework that merges Graph Auto-Encoders with Deep Manifold Learning. By preserving node-to-node geodesic similarities and utilizing a t-distribution kernel, the method effectively solves the "crowding problem" in latent spaces, significantly outperforming state-of-the-art models in node clustering and link prediction.

What Problem Does This Paper Address?

Graph embedding is the art of squeezing high-dimensional, non-Euclidean graph data (nodes, edges, and their attributes) into a low-dimensional space. While standard tools like Graph Auto-Encoders (GAE) and Variational Graph Auto-Encoders (VGAE) are popular, they have a major flaw: they focus almost entirely on minimizing reconstruction error.

The authors argue that this narrow focus ignores the underlying topological structure and data distribution. This leads to the "crowding problem"—a phenomenon where nodes from the same class are forced too close together in the latent space, creating artificial "curvature folds." These distortions make the resulting embeddings less stable and less effective for downstream tasks like clustering or recommendation.

Methods

The authors propose the Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE). The core idea is to treat the graph not just as a set of connections, but as a manifold—a topological space that looks like Euclidean space locally but has a complex global structure.

Key Innovations:

  1. Geodesic Similarity Preservation: Instead of just looking at immediate neighbors, the model calculates "graph geodesic distances" (the shortest path between nodes). It does this for both the local neighborhood (the given graph) and the global structure (a fully connected version of the graph).
  2. t-distribution Kernel: Borrowing a page from visualization techniques like t-SNE and UMAP, the authors use a t-distribution to convert distances into similarities. Crucially, they use the "degree of freedom" ($\nu$) of the t-distribution as a tunable tool to control the separation margin between different clusters, preventing the crowding problem.
  3. Dual Loss Function: The model doesn't just throw away the auto-encoder's strengths. It optimizes a joint loss:
  4. Reconstruction Loss: Ensures the latent code can still rebuild the original graph.
  5. Manifold Learning Loss ($L_2$): Ensures that the "geodesic similarity" in the high-dimensional input space is mirrored in the low-dimensional latent space.
  6. Efficiency: To keep the math from exploding on large graphs, they implement a mini-batch training strategy and use prior graphs to reduce computational complexity to $O(K B_s N_n)$.

Datasets

The model was evaluated on four standard benchmark datasets for graph learning:

  • Cora, CiteSeer, and PubMed: Classic citation networks where nodes are papers and edges are citations.
  • Wiki: A network of web pages.

These datasets are widely used because they provide a clear ground truth for node categories, making them ideal for testing clustering and link prediction.

Key Insights and Ideas

  • Structure over Reconstruction: The "aha moment" here is that reconstruction error is a poor proxy for structural integrity. By explicitly forcing the latent space to respect geodesic distances, the model captures the "shape" of the data far better than a standard GAE.
  • The Power of $\nu$: The researchers found that the degree of freedom in the t-distribution isn't just a mathematical detail; it's a "knob" that prevents the training from getting stuck in bad local minima and helps push different manifolds apart.
  • Global vs. Local: By calculating distances on both the sparse input graph and a complete graph, the model balances fine-grained local details with the overall "big picture" of the graph's topology.

Key Results

The results show a significant leap over previous methods:

  • Node Clustering: On the Cora dataset, DMVGAE achieved an Accuracy (ACC) of 0.745, compared to VGAE’s 0.560. It consistently outperformed other advanced methods like GIC and ARGA across all four datasets.
  • Link Prediction: The model achieved the highest average values for Area Under Curve (AUC) and Average Precision (AP), reaching 0.968 AUC on Cora.
  • Visual Proof: Qualitative UMAP visualizations (see Fig. 1 in the paper) show that while competing methods like GIC and AGE produce "crowded" blobs where classes overlap, DMVGAE produces distinct, well-separated clusters.

Limitations and Future Work

While the method is powerful, the authors acknowledge a few areas for growth:

  • Robustness to Noise: Real-world graphs are often messy or subject to adversarial attacks. The current model assumes a relatively clean graph structure.
  • Computational Overhead: Although they optimized the complexity, the initial calculation of geodesic distance matrices on very large graphs (millions of nodes) could still be a bottleneck.
  • Future Direction: The authors plan to introduce different types of noise during training to improve the model's robustness and "defense" capabilities against graph-based attacks.

Summary updated

Abstract

Representing graph data in a low-dimensional space for subsequent tasks is the purpose of attributed graph embedding. Most existing neural network approaches learn latent representations by minimizing reconstruction errors. Rare work considers the data distribution and the topological structure of latent codes simultaneously, which often results in inferior embeddings in real-world graph data. This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) method for attributed graph data to improve the stability and quality of learned representations to tackle the crowding problem. The node-to-node geodesic similarity is preserved between the original and latent space under a pre-defined distribution. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets, which validates our solutions. We promise to release the code after acceptance.
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},
}

Loading related content...

Figure