Exploring the Semantic Content of Unsupervised Graph Embeddings: An Empirical Study (2018-06-19T00:00:00.000000Z)

TL;DR

This paper investigates if graph embeddings are approximating something analogous to traditional vertex-level graph features, and demonstrates that several topological features are indeed being approximated in the embedding space, allowing key insight into how graph embeds create good representations.

Abstract

Graph embeddings have become a key and widely used technique within the field of graph mining, proving to be successful across a broad range of domains including social, citation, transportation and biological. Unsupervised graph embedding techniques aim to automatically create a low-dimensional representation of a given graph, which captures key structural elements in the resulting embedding space. However, to date, there has been little work exploring exactly which topological structures are being learned in the embeddings, which could be a possible way to bring interpretability to the process. In this paper, we investigate if graph embeddings are approximating something analogous to traditional vertex-level graph features. If such a relationship can be found, it could be used to provide a theoretical insight into how graph embedding approaches function. We perform this investigation by predicting known topological features, using supervised and unsupervised methods, directly from the embedding space. If a mapping between the embeddings and topological features can be found, then we argue that the structural information encapsulated by the features is represented in the embedding space. To explore this, we present extensive experimental evaluation with five state-of-the-art unsupervised graph embedding techniques, across a range of empirical graph datasets, measuring a selection of topological features. We demonstrate that several topological features are indeed being approximated in the embedding space, allowing key insight into how graph embeddings create good representations.

Authors

References65 items

Network Representation Learning: A Survey

A Survey on Network Embedding

Evaluating the quality of graph embeddings via topological feature reconstruction

Properties of Vector Embeddings in Social Networks

A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications

Representation Learning on Graphs: Methods and Applications

Learning Graph Topological Features via GAN

Inductive Representation Learning on Large Graphs

Neural Embeddings of Graphs in Hyperbolic Space

Poincaré Embeddings for Learning Hierarchical Representations

Graph Embedding Techniques, Applications, and Performance: A Survey

Supervised Learning of Universal Sentence Representations from Natural Language Inference Data

Learning network representations

Deep topology classification: A new approach for massive graph classification

DeepGraph: Graph Structure Predicts Network Growth

WaveNet: A Generative Model for Raw Audio

Semi-Supervised Classification with Graph Convolutional Networks

Benchmarking State-of-the-Art Deep Learning Software Tools

Asymmetric Transitivity Preserving Graph Embedding

Structural Deep Network Embedding

node2vec: Scalable Feature Learning for Networks

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Learning Convolutional Neural Networks for Graphs

GraRep: Learning Graph Representations with Global Structural Information

Evaluation methods for unsupervised word embeddings

Visualizing and Understanding Neural Models in NLP

The Network Data Repository with Interactive Graph Analytics and Visualization

An Experimental Comparison of Pregel-like Graph Processing Systems

{SNAP Datasets}: {Stanford} Large Network Dataset Collection

DeepWalk: online learning of social representations

Spectral Networks and Locally Connected Networks on Graphs

Visualizing and Understanding Convolutional Networks

Distributed Representations of Words and Phrases and their Compositionality

Distributed large-scale natural graph factorization

Efficient Estimation of Word Representations in Vector Space

NetSimile: A Scalable Approach to Size-Independent Network Similarity

A bioimage informatics approach to automatically extract complex fungal networks

Effective graph classification based on topological and label attributes

Transforming Auto-Encoders

Scikit-learn: Machine Learning in Python

Supervised random walks: predicting and recommending links in social networks

Networks: An Introduction

Why Does Unsupervised Pre-training Help Deep Learning?

A survey of cross-validation procedures for model selection

Semantic hashing

Reemergence of Human and Animal Brucellosis, Bulgaria

Some unique properties of eigenvector centrality

An introduction to variable and feature selection

Statistical mechanics of complex networks

Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

The PageRank Citation Ranking : Bringing Order to the Web

On power-law relationships of the Internet topology

Optimizing Classifers for Imbalanced Training Sets

Exploring Large Graphs in 3D Hyperbolic Space

Collective dynamics of ‘small-world’ networks

Principal component analysis

Deep Learning

International Conference on Learning Representations (ICLR)

Transforming autoencoders. In: International conference on artificial neural networks

On Power-Law Relationships of the Internet

Visualizing Data using t-SNE

Euclidean decompositions of noncompact hyperbolic manifolds

This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Tensorflow: a System for Large-scale Machine Learning Tensorflow: a System for Large-scale Machine Learning

2016 Ieee International Conference on Big Data (big Data) Gfp-x: a Parallel Approach to Massive Graph Comparison Using Spark