Structured Information Loss in Network Embeddings

Low-dimensional network embeddings (e.g., DeepWalk [1], LINE [2], and many others [3, 4]) are known to be very powerful tools for doing machine learning tasks on graph or network data (for an overview, see [5]). These techniques have shown extremely strong performance in all sorts of tasks including link prediction, community detection, node classification, etc. However, our theoretical understanding of these methods lags behind their empirical success. This is unsurprising: deep-learning algorithms learn very delicate and complex graph properties from real network data and tasks (prediction, classification, etc.); it is difficult to capture these complex properties in a theoretically-sound generative model, let alone determine whether said properties are faithfully reproduced by any given low-dimensional representation. Furthermore, most network embedding methods rely on minimizing a loss function over subsamples of the graph; it is rare to find analytic characterizations of what these methods converge to. Recent work has shown theoretical limits on the representation power of arbitrary low-dimensional embeddings [6, 7, 8]. Davison et al [9] show that these representation limits persist even for graphons, a generative model for graphs that can be thought of as probabilistic generalizations of simple graphs. They prove that inner-product-based embeddings "restrict the class of networks for which an informative embedding can be learned, and networks generated from distinct probabilistic models (graphons) can have embeddings which are asymptotically indistinguishable." 1