Sign Rank Limitations for Attention-Based Graph Decoders
Su Hyeong Lee Qingqi Zhang Risi Kondor
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.