Research map / Graph learning / Graph self-supervised learning
Sign Rank Limitations for Inner Product Graph Decoders
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows via sign rank that inner product graph decoders are representationally limited, proves rank lower bounds for grids and stars, and proposes cutoff-augmented decoders (DGAE, m-GAE, CGAE) that reconstruct graphs in low latent dimensions.
Problem
Inner product decoders for latent graph embeddings have limited representation capacity; the minimal latent dimension needed for faithful graph reconstruction under sign rank is not understood theoretically.
Approach
Formalize reconstruction as sign rank, prove lower bounds on real latent dimension (e.g., star graphs, planar grids), show complex latent embeddings reduce star-graph rank to 1, and add learnable diagonal cutoffs to the inner product decoder (sign(Z1 C1 Z1^T - Z2 C2 Z2^T)) to relax the acute-angle connectivity criterion without leaving the inner product framework.
Key results
- Cutoff-augmented DGAE embeds all molecular graphs with more than 27/36/40/60 nodes from QM9, Zinc, TU-Enzymes, TU-Proteins in <=10 latent dimensions, while GAE mostly fails up to h2=80.
- Theorem: the (N-1)-star graph has real sign rank lower bounded by (N+1)/2, but is complex rank 1.
- Long chain of 140 linked 6-cycles is reconstructed flawlessly by augmented architectures for h2>=8, whereas GAE struggles even at high latent dimension.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add learnable decoder cutoffs | GAE/DGAE · Molecular graph datasets (QM-9, Zinc, TU-Enzymes, TU-Protein) | faithful reconstruction at latent dimension | Helped |
| Add cutoff parameters to the decoder | GAE · Grid and chain graphs | faithful reconstruction | Helped |
| Increase ℓ2 regularization | Presented architectures · Graph memorization experiments | reconstruction fidelity | Hurt |
Surprising findings
- Real inner product decoders require latent dimension growing linearly with star size, while complex embeddings represent any star graph in rank 1.
Limitations
- Theoretical lower bounds are proven for specific graph families (stars, planar grids), not general graphs.
- Cutoff architectures evaluated mainly on synthetic pedagogical graphs and small molecular/citation datasets.
- Some reported Cora/CiteSeer errors show high variance and mixed winners across latent dimensions.
Experimental setup
Datasets: Cora CiteSeer QM9 Zinc TU-Enzymes TU-Proteins QM7b
Benchmarks: Cora CiteSeer QM9 Zinc TU-Enzymes TU-Proteins
Metrics: reconstruction error (squared Frobenius norm) adjacency rank log-normalized distance
Baselines: GAE VAE complex GAE (CGAE) Laplacian Eigenmaps
Builds on: Graph Autoencoder (GAE) Variational Graph Autoencoder (VGAE)
Closest papers by meaning
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.83)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.82)
- Self-Explainable Graph Transformer for Link Sign Prediction (AAAI 2025 · similarity 0.82)
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.82)
- Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs (ICML 2024 · similarity 0.82)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.