Sign Rank Limitations for Inner Product Graph Decoders
This work addresses a fundamental bottleneck in graph data analysis for researchers and practitioners using latent embedding methods, though it is incremental as it builds on known limitations.
The paper tackles the limitations of inner product-based decoders in graph reconstruction by providing the first theoretical explanation for their representation capacity issues and proposes simple modifications to address these problems while staying within the inner product framework.
Inner product-based decoders are among the most influential frameworks used to extract meaningful data from latent embeddings. However, such decoders have shown limitations in representation capacity in numerous works within the literature, which have been particularly notable in graph reconstruction problems. In this paper, we provide the first theoretical elucidation of this pervasive phenomenon in graph data, and suggest straightforward modifications to circumvent this issue without deviating from the inner product framework.