Exploring the Representational Power of Graph Autoencoder

Abstract

While representation learning has yielded a great success on many graph learning tasks, there is little understanding behind the structures that are being captured by these embeddings. For example, we wonder if the topological features, such as the Triangle Count, the Degree of the node and other centrality measures are concretely encoded in the embeddings. Furthermore, we ask if the presence of these structures in the embeddings is necessary for a better performance on the downstream tasks, such as clustering and classification. To address these questions, we conduct an extensive empirical study over three classes of unsupervised graph embedding models and seven different variants of Graph Autoencoders. Our results show that five topological features: the Degree, the Local Clustering Score, the Betweenness Centrality, the Eigenvector Centrality, and Triangle Count are concretely preserved in the first layer of the graph autoencoder that employs the SUM aggregation rule, under the condition that the model preserves the second-order proximity. We supplement further evidence for the presence of these features by revealing a hierarchy in the distribution of the topological features in the embeddings of the aforementioned model. We also show that a model with such properties can outperform other models on certain downstream tasks, especially when the preserved features are relevant to the task at hand. Finally, we evaluate the suitability of our findings through a test case study related to social influence prediction.

References in corpus (10)

• DeepWalk: Online Learning of Social Representations
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Instance Normalization: The Missing Ingredient for Fast Stylization
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Variational Graph Auto-Encoders
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• DeepInf: Social Influence Prediction with Deep Learning
• Beyond Product Quantization: Deep Progressive Quantization for Image Retrieval
• Deep Recurrent Quantization for Generating Sequential Binary Codes

Cited by in corpus (2)

• A Deep Latent Space Model for Graph Representation Learning
• TopoDetect: Framework for Topological Features Detection in Graph Embeddings