Discrete Embedding for Attributed Graphs

Abstract

Attributed graphs refer to graphs where both node links and node attributes are observable for analysis. Attributed graph embedding enables joint representation learning of node links and node attributes. Different from classical graph embedding methods such as Deepwalk and node2vec that first project node links into low-dimensional vectors which are then linearly concatenated with node attribute vectors as node representation, attributed graph embedding fully explores data dependence between node links and attributes by either using node attributes as class labels to supervise structure learning from node links, or reversely using node links to supervise the learning from node attributes. However, existing attributed graph embedding models are designed in continuous Euclidean spaces which often introduce data redundancy and impose challenges to storage and computation costs. In this paper, we study a new problem of discrete embedding for attributed graphs that can learn succinct node representations. Specifically, we present a Binarized Attributed Network Embedding model (BANE for short) to learn binary node representation by factorizing a Weisfeiler-Lehman proximity matrix under the constraint of binary node representation. Furthermore, based on BANE, we propose a new Low-bit Quantization for Attributed Network Representation learning model (LQANR for short) to learn even more compact node representation of bit-width values. Theoretical analysis and empirical studies on real-world datasets show that the new discrete embedding models outperform benchmark methods.