Unsupervised Graph Embedding via Adaptive Graph Learning

Rui Zhang, Yunxing Zhang, Chengjun Lu, Xuelong LiIEEE TPAMI 2023 · OpenReview

TL;DR

This paper introduces two novel unsupervised graph embedding methods, BAGE and VBAGE, that enhance the robustness of Graph Autoencoders (GAEs) by adaptively learning the graph's adjacency matrix. This allows GAEs to perform well even on datasets lacking explicit graph structures or with incomplete/noisy adjacency information, a significant limitation of prior work.

What Problem Does This Paper Address?

Graph Autoencoders (GAEs) are powerful tools for learning low-dimensional representations of nodes in a graph, preserving its structural information. However, their performance is highly sensitive to the quality of the input graph structure, specifically the adjacency matrix. When this matrix is incomplete, noisy, or entirely absent, traditional GAEs struggle, leading to poor embeddings. Existing methods often rely on heuristics like k-Nearest Neighbors (kNN) to initialize the adjacency matrix when it's missing, which can be suboptimal and parameter-sensitive. This paper aims to overcome these limitations by developing unsupervised GAE methods that can adaptively learn or refine the adjacency matrix, making them more versatile and robust.

Methods

The core innovation lies in the adaptive learning of the adjacency matrix. Instead of relying solely on a fixed or kNN-initialized adjacency matrix, BAGE and VBAGE incorporate a mechanism to learn and update it iteratively.

Here's a breakdown of their approach:

  • Graph Convolutional Encoder: Similar to existing GAEs, they use graph convolutional networks (GCNs) to encode node features and the graph structure into latent representations. They propose both a standard GAE (BAGE) and a variational GAE (VBAGE) variant.
  • Decoder: A decoder reconstructs the graph (specifically, the adjacency matrix) from the learned latent representations.
  • Laplacian Graph Structure Integration: A key contribution is embedding the latent representations within the Laplacian graph structure. This loss term encourages nodes with similar latent representations to be close in the embedding space, directly leveraging the graph's topology.
  • Adaptive Adjacency Matrix Learning:
    • Initialization: If no initial graph structure is provided, the adjacency matrix is initialized using a learned approach based on node distances in the latent space, avoiding the need for kNN.
  • Updating: During training, the adjacency matrix is iteratively updated. This update is guided by the learned latent representations and the Laplacian graph structure loss. They propose a method to combine the learned adjacency matrix with the initial one (if available) using a hyperparameter α to balance their influence.
  • Sparsity Control: The number of neighbors (sparsity) for each node in the learned adjacency matrix is adaptively determined, rather than being fixed, addressing a limitation of kNN.
  • Loss Functions: They introduce specific loss functions that penalize reconstruction errors of non-zero elements more heavily and incorporate the Laplacian graph structure loss.

Datasets

The paper evaluates their methods on a variety of datasets for different tasks:

  • Node Clustering:
    • Graph Datasets: Cora and Citeseer. For these, they intentionally introduce "missing ratios" to the adjacency matrix to test robustness.
  • General Datasets: IMM, ATT, UMIST, COIL, USPS, PIE. These datasets are used without an initial graph structure, requiring their adaptive initialization method.
  • Node Classification: The six general datasets listed above are used.
  • Graph Visualization: Cora and Citeseer datasets are used for visualization.

Key Insights and Ideas

  • Robustness to Incomplete Graphs: The most significant insight is that adaptively learning the adjacency matrix makes GAEs remarkably robust to missing or noisy graph structures. This opens up GAEs for use on a much wider range of real-world data where perfect graph structures are rare.
  • Beyond kNN Initialization: The proposed adaptive initialization of the adjacency matrix is a valuable alternative to kNN, which can be sensitive to the choice of k and may not capture complex relationships well.
  • Laplacian Structure for Topology Preservation: Embedding latent representations within the Laplacian graph structure is an effective way to explicitly enforce topological preservation in the embedding space.
  • Self-Learning Graph Structure: The ability to learn the graph structure from scratch (when none is provided) is a powerful capability, enabling GAEs to be applied to datasets that were previously inaccessible.

Key Results

The paper demonstrates strong performance across multiple tasks:

  • Node Clustering: BAGE and VBAGE consistently outperform state-of-the-art baselines (including LGAE, ARGE, GAE, VGAE, SDNE, and Spectral Clustering) on both Cora and Citeseer datasets, especially when the adjacency matrix is incomplete. For instance, on Cora with a high missing ratio, their methods achieved 7-9% higher accuracy than the second-best method.
  • Node Classification: On the six general datasets, BAGE and VBAGE achieved top performance, often outperforming competitors by 3-6%. For example, on the PIE dataset, BAGE reached 95% accuracy, while others were around 91%.
  • Graph Visualization: Visualizations of Cora and Citeseer datasets show that the learned embeddings from BAGE and VBAGE produce more meaningful and well-separated clusters, indicating better preservation of graph topology.

Limitations and Future Work

  • Parameter Sensitivity: While the adaptive learning mechanism reduces sensitivity to some parameters (like k), the paper mentions studying the influence of parameters λ and β. The results suggest their influence on node classification is "small," but this might vary for other tasks or datasets.
  • Computational Complexity: The adaptive learning of the adjacency matrix adds to the computational complexity, with a time complexity of O((dn²)τ) for updating the adjacency matrix.
  • Future Work: The paper implicitly suggests future work could explore more sophisticated adaptive learning mechanisms, investigate the theoretical underpinnings of adaptive graph learning, and apply these methods to a broader range of graph-related tasks. The adaptive learning of the adjacency matrix is highlighted as the paper's "biggest contribution," implying its potential for further research.

Summary updated

Abstract

Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. However, the performance of GAEs is very dependent on the quality of the graph structure, i.e., of the adjacency matrix. In other words, GAEs would perform poorly when the adjacency matrix is incomplete or be disturbed. In this paper, two novel unsupervised graph embedding methods, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">unsupervised graph embedding via adaptive graph learning</i> (BAGE) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">unsupervised graph embedding via variational adaptive graph learning</i> (VBAGE) are proposed. The proposed methods expand the application range of GAEs on graph embedding, i.e, on the general datasets without graph structure. Meanwhile, the adaptive learning mechanism can initialize the adjacency matrix without being affected by the parameter. Besides that, the latent representations are embedded with the Laplacian graph structure to preserve the topology structure of the graph in the vector space. Moreover, the adjacency matrix can be self-learned for better embedding performance when the original graph structure is incomplete. With adaptive learning, the proposed method is much more robust to the graph structure. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, link prediction, and graph visualization tasks.
BibTeX
@article{zhang2023unsupervised,
  author = {Rui Zhang and Yunxing Zhang and Chengjun Lu and Xuelong Li},
  title = {{Unsupervised Graph Embedding via Adaptive Graph Learning}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2023},
  url = {https://openreview.net/forum?id=KLAt8BtksRK},
}
Figure