Structured Information Loss in Network Embeddings
This work highlights limitations in network embeddings for tasks like link prediction, which is important for researchers and practitioners in graph learning, but it is incremental as it builds on existing theoretical analysis.
The paper analyzes a network embedding algorithm, characterizing when it fully, partially, or fails to encode the graph's generative model, and finds that information loss preserves community structure but loses density details, impacting tasks like link prediction.
We analyze a simple algorithm for network embedding, explicitly characterizing conditions under which the learned representation encodes the graph's generative model fully, partially, or not at all. In cases where the embedding loses some information (i.e., is not invertible), we describe the equivalence classes of graphons that map to the same embedding, finding that these classes preserve community structure but lose substantial density information. Finally, we show implications for community detection and link prediction. Our results suggest strong limitations on the effectiveness of link prediction based on embeddings alone, and we show common conditions under which naive link prediction adds edges in a disproportionate manner that can either mitigate or exacerbate structural biases.