Relational Compression: A Framework for Relational Fidelity in Constrained Representations

Yaniv Shulman

cs.LGSep 25, 2026

Relational Compression: A Framework for Relational Fidelity in Constrained Representations

Authors: Yaniv Shulman

Abstract

What should a compressed representation preserve when the information of interest lies in relationships among elements rather than in the elements themselves? We formulate relational compression in the classical source-description-reconstruction sense, but with relational structure itself as the fidelity-bearing content. Each instance specifies the source relation, retained description, reconstructed or evaluated relation, fidelity criterion, and constrained resource. We use this interface to situate selected methods from graph summarization, spectral sparsification, similarity-preserving representation, and relational distillation within a common formulation while keeping their different reconstruction and resource assumptions explicit. We develop finite-codeword collision as one concrete realization. Same-codeword probability yields a relational geometry linking pair-specific alignment and separation to aggregate Rényi-2 occupancy and the spherical geometry of categorical assignments, with exact objective correspondences to squared-Euclidean centroid reconstruction and normalized graph association and cut. Graph and image studies illustrate complementary routes within the finite-codeword family: graph- and teacher-defined relational requirements act directly on equality or collision, while reconstruction acts through a joint decoder. Together, these results illustrate how distinct relational requirements can be formulated and tested within a common constrained-representation framework.

Figures & tables

Role	Classical compression	Relational compression
Source	Source object $x$	Relational object $(V,S)$ , with $V$ fixed or shared
Description	Retained message $m$	Retained relational description $m_{S}$
Reconstruction	Reproduced object $\widehat{x}$	Reconstructed relation $\widetilde{S}$
Decoder	Rule mapping $m$ to $\widehat{x}$	Rule constructing $\widetilde{S}$ or evaluating its entries
Fidelity	Distortion $d(x,\widehat{x})$	Relational distortion $\Delta_{V}(S,\widetilde{S})$
Resource	Cost of the description	Cost $\Omega(m_{S})$ in specified units

Table 1: The compression interface for ordinary and relational source objects.

Construction	Source and fidelity	Description and reconstruction	Resource
Graph summaries ( Riondato et al., 2017 )	Adjacency structure; reconstruction or cut-norm error	Vertex groups and superedge values; block-valued relation	Assignments and summary values
Spectral sparsification ( Spielman and Srivastava, 2011 )	Laplacian quadratic forms; relative approximation	Sparse weighted edges; reconstructed Laplacian	Edge count or encoded weighted-edge description
Spectral hashing ( Weiss et al., 2008 )	Source similarities; similarity-weighted code-distance criterion	Binary codes; Hamming geometry	Bits per element
$t$ -SNE ( van der Maaten and Hinton, 2008 )	Pair-affinity distribution; KL discrepancy	Low-dimensional coordinates; normalized pair affinity	Coordinate dimension
Distance-wise relational distillation ( Park et al., 2019 )	Teacher pair distances; relational discrepancy	Student features or student model; induced pair distances	Feature or model representation
Centroid quantization ( Gray and Neuhoff, 1998 )	Squared source distances; within-code pairwise distortion	Assignments and centroid reproductions	Assignments and reproduction vectors

Table 2: Representative methods expressed through the core components of the relational-compression framework: source relation, fidelity criterion, retained description, reconstruction, and resource.

Role	Classical compression	Relational compression	Finite-codeword realization used here
Source / fidelity-bearing content	Source object $x$ and the content reconstructed from it	Relational object $(V,S)$ , with $S$ the fidelity-bearing structure conditional on shared $V$	Explicit point geometry, graph structure, or teacher-defined relations; Study 4 instead uses source-image reconstruction to constrain the finite representation through a joint spatial decoder
Encoder-side observations	Usually the source observation itself	$X_{V}=(x_{v})_{v\in V}$ when encoder-side observations are present	Point coordinates, graph or node structural features, or image pixels mapped to finite assignments
Retained description	Retained message or code $m$	Retained relational description $m_{S}$	The source-specific $m_{S}$ comprises declared finite assignments, codes, or tokens plus any required auxiliary payload; $q_{\theta}(\cdot\mid x)$ is an optimization parameterization where applicable
Reconstruction / evaluation	Reconstructed source $\widehat{x}$	$\widetilde{S}=\mathsf{Dec}_{V}(m_{S})$ , materialized or evaluated on demand	Same-code equality or collision may supply the evaluated relation directly or feed a richer structural or reconstruction decoder
Primitive representation-side relation	No universal analogue is prescribed	Depends on the chosen description mechanism	Hard equality $\mathbb{I}[c_{\theta}(x)=c_{\theta}(x^{\prime})]$ and soft collision $k_{\theta}(x,x^{\prime})$
Fidelity	Distortion $d(x,\widehat{x})$	Relational distortion $\Delta_{V}(S,\widetilde{S})$	Study-specific source fidelity acting on or through collision, including centroid/pairwise, graph, normalized-cut, reconstruction-defined, and signed-teacher criteria

Table 3: Summary of the compression roles used to interpret the experimental realizations. The final column specializes the general relational-compression interface to the finite-codeword constructions used in this paper. Realized codeword organization is reported separately from operational coding rate unless the declared resource convention identifies them.

Source	Importance cosine $(D_{F},D_{C})$	Spearman $(D_{F},D_{C})$	Spearman $(D_{F},D_{H_{2}})$	Spearman $(D_{C},D_{H_{2}})$
MalNet unweighted	0.979	0.975	0.666	0.616
MalNet weighted	0.744	0.724	0.500	0.550
COLLAB	0.833	0.814	0.523	0.774
PROTEINS	0.983	0.981	0.616	0.608

Table 4: Source-fidelity agreement. Importance cosine compares the normalized source-importance vectors for

D_{F}

and

D_{C}

; the remaining columns report Spearman correlations of distortion values over random hard partitions, averaged over graphs. COLLAB correlations involving

D_{H_{2}}

use the 18 sources where that normalized fidelity is defined.

$\lambda_{\mathrm{org}}$	Val Ncut	Test Ncut	Test $D_{F}$	Test median Ncut
0	$1.129\pm 0.063$	$1.160\pm 0.043$	$0.0606\pm 0.0115$	$1.083\pm 0.043$
0.03	$1.137\pm 0.060$	$1.171\pm 0.062$	$0.0657\pm 0.0179$	$1.093\pm 0.061$
0.10	$1.158\pm 0.029$	$1.186\pm 0.033$	$0.0926\pm 0.0055$	$1.116\pm 0.031$
0.20	$1.136\pm 0.039$	$1.170\pm 0.030$	$0.1117\pm 0.0017$	$1.114\pm 0.035$
0.50	$1.285\pm 0.026$	$1.319\pm 0.022$	$0.1475\pm 0.0020$	$1.270\pm 0.017$
Spectral reference	1.143	1.159	0.0805	1.104

Table 5: MalNet-Tiny fidelity results. Learned rows show mean and sample standard deviation across five seeds. Lower is better for all displayed fidelities. The deterministic spectral reference is evaluated once on the same cleaned splits.

D_{F}

is post-hoc.

$\lambda_{\mathrm{org}}$	Largest hard volume fraction	Soft $K_{\mathrm{eff}}$	Soft $D_{2}$
0	$0.840\pm 0.042$	$1.42\pm 0.14$	$1.745\pm 0.093$
0.03	$0.807\pm 0.072$	$1.54\pm 0.26$	$1.679\pm 0.149$
0.10	$0.678\pm 0.023$	$2.00\pm 0.08$	$1.416\pm 0.043$
0.20	$0.544\pm 0.006$	$2.45\pm 0.03$	$1.195\pm 0.012$
0.50	$0.375\pm 0.012$	$3.55\pm 0.10$	$0.820\pm 0.030$
Spectral reference	0.575	–	–

Table 6: Organization of the same MalNet-Tiny solutions. Quantities are computed per graph before averaging. Mean effective count and mean divergence need not obey a nonlinear identity after averaging. The reference has a hard effective count of 2.78; it has no soft-assignment counterpart in these columns.

Setting	Bits	Nominal bpp	PSNR	Hard $H_{2}$	$K_{\mathrm{eff}}$
No organization	16	0.25	19.86	1.98	7.2
Weaker, $10^{-7}$	16	0.25	24.36	7.00	1 098
Baseline, $10^{-6}$	16	0.25	24.83	9.50	13 388
Stronger, $10^{-5}$	16	0.25	24.56	10.29	29 569
Capacity, $10^{-6}$	32	0.50	25.88	12.46	257 753

Table 7: Flowers102 hard-code reconstruction and organization at validation-selected checkpoints. PSNR is in dB and

H_{2}

in nats. Each row is one run. The nominal bpp describes raw latent bits before entropy coding.

Metric	Validation	Test
Representation epoch	146
Teacher loss	0.389	0.389
Favored-pair hard collision	$1.35\times 10^{-2}$	$1.29\times 10^{-2}$
Disfavored-pair hard collision	$1.37\times 10^{-4}$	$1.47\times 10^{-4}$
Aggregate hard collision	$1.03\times 10^{-3}$	$1.04\times 10^{-3}$
Favored-pair enrichment	13.13	12.40

Table 8: DINO-defined relational learning on Flowers102. Representation and secondary decoder checkpoints use separate validation criteria. The encoder is frozen during decoder training. The study uses one seed.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Diagnostic	Observed value
Maximum $\|D_{\mathrm{cent}}-D_{\mathrm{pair}}\|$ , centroid-trained trajectory	$9.54\times 10^{-7}$
Maximum $\|D_{\mathrm{cent}}-D_{\mathrm{pair}}\|$ , pair-trained trajectory	$9.54\times 10^{-7}$
Larger trajectory mean of $\|D_{\mathrm{cent}}-D_{\mathrm{pair}}\|$	$4.20\times 10^{-8}$
Random encoder states: maximum $\|D_{\mathrm{cent}}-D_{\mathrm{pair}}\|$	$1.91\times 10^{-6}$
Random encoder states: mean $\|D_{\mathrm{cent}}-D_{\mathrm{pair}}\|$	$2.64\times 10^{-7}$
Initial gradient cosine / relative error	$1.000\,/\,1.54\times 10^{-7}$

Appendix

Table 9: Synthetic numerical diagnostics. Values near

10^{-6}

reflect single-precision arithmetic.

Component	Setting
Data	768 points in $\mathbb{R}^{2}$ from a six-component Gaussian mixture
Mixture weights	$(0.30,0.22,0.17,0.13,0.10,0.08)$
Realized component counts	$(230,169,131,100,77,61)$
Encoder	MLP with two hidden layers, width 32, $\tanh$ nonlinearities
Code distribution	Exact enumeration of $2^{3}=8$ factorized Bernoulli words
Code temperature	0.7

Appendix

Table 10: Settings for Study 1.

Component	Setting
Collections	20 MalNet-Tiny test LCCs; the same 20 weighted topologies; 20 COLLAB; 20 PROTEINS
Base graph-selection seed	1337; deterministic collection-specific offsets for COLLAB and PROTEINS
Minimum source size	512 nodes for MalNet; 16 nodes for TUDataset, after LCC extraction
Training fidelities	$D_{E}$ , $D_{F}$ , $D_{C}$ , and $D_{H_{2}}$ where defined
Entropy-field exclusions	Omit $D_{H_{2}}$ when its source Dirichlet denominator is zero; two selected COLLAB graphs are excluded from this criterion
Representation	Free graph-local $n\times 8$ categorical logits; no learned encoder

Appendix

Table 11: Settings for Study 2.

Source	Pair	$n$	Mean ARI	$\Delta_{A\to B}$	$\Delta_{B\to A}$
MalNet unweighted	$D_{F}$ / $D_{C}$	20	0.781	-0.0025	0.0060
MalNet unweighted	$D_{F}$ / $D_{H_{2}}$	20	0.166	0.0919	0.0698
MalNet unweighted	$D_{C}$ / $D_{H_{2}}$	20	0.196	0.1068	0.0744
MalNet weighted	$D_{F}$ / $D_{C}$	20	0.714	0.0011	0.0063
MalNet weighted	$D_{F}$ / $D_{H_{2}}$	20	0.116	0.0785	0.0638
MalNet weighted	$D_{C}$ / $D_{H_{2}}$	20	0.157	0.0834	0.0864

Appendix

Table 12: Hard-partition agreement and cross-distortion transfer at target collision occupancy

H_{2}(\bar{q}_{G})=2.0

nats.

n

counts matched graphs. ARI is invariant to code-label permutation.

Source	Training fidelity	Eval. $D_{E}$	Eval. $D_{F}$	Eval. $D_{C}$	Eval. $D_{H_{2}}$
MalNet unweighted	$D_{E}$	0.0000	-0.0017	-0.0020	0.0732
MalNet unweighted	$D_{F}$	0.0163	0.0000	-0.0024	0.0911
MalNet unweighted	$D_{C}$	0.0260	0.0058	0.0000	0.1057
MalNet unweighted	$D_{H_{2}}$	0.0999	0.0690	0.0738	0.0000
MalNet weighted	$D_{E}$	0.0000	0.0033	-0.0023	0.0658
MalNet weighted	$D_{F}$	0.0131	0.0000	0.0011	0.0785

Appendix

Table 13: Cross-distortion transfer, averaged over pairwise hard-

H_{2}

-matched graph–occupancy comparisons. Each entry is excess hard distortion relative to the solution trained for that column’s evaluation fidelity. Compare rows within a column.

Split	Raw graphs	Retained graphs	Excluded below 512 LCC nodes
Train	3500	1995	1505
Validation	500	275	225
Test	1000	584	416

Appendix

Table 14: MalNet-Tiny source selection after cleaning.

Component	Setting
Dataset	MalNet-Tiny, official source splits, labels unused
Cleaning	Undirected edge union, self-loop removal, coalesced duplicates, largest connected component
Minimum graph size	512 vertices after LCC extraction
Node features	Constant and cleaned undirected degree features, original directed degree features and PageRank, deterministic random-walk return estimates
Random-walk estimates	16 steps, 8 Rademacher probes, split/index-dependent deterministic seeds
Assignments	$K=8$ categorical states; $\tau=1.0$

Appendix

Table 15: Settings for Study 3.

Component	Setting
Input	$256\times 256$ RGB, unit-range pixel values
Encoder width	128 hidden channels
Residual stack	Two blocks, 64 residual hidden channels
Downsampling / upsampling	Three stride-2 analysis stages with GDN and three transposed-convolution synthesis stages, with IGDN after the first two synthesis stages, giving a $32\times 32$ latent grid
Spatial collision unit	One $b$ -bit token per latent position
Analysis output	$1\times 1$ convolution producing $b$ logits per spatial position

Appendix

Table 16: Shared settings for Study 4.

Setting	Bits	$\lambda_{\mathrm{org}}$	Nominal bpp	Selected epoch
No organization	16	$0$	0.25	117
Weaker organization	16	$10^{-7}$	0.25	145
Baseline	16	$10^{-6}$	0.25	148
Stronger organization	16	$10^{-5}$	0.25	148
Capacity ablation	32	$10^{-6}$	0.50	150

Appendix

Table 17: Ablations and validation-selected checkpoint epochs.

Setting	Test MSE	Test PSNR (dB)	Test MS-SSIM
No organization	0.01034	19.86	0.738
Weaker organization	0.00367	24.36	0.882
Baseline	0.00329	24.83	0.896
Stronger organization	0.00350	24.56	0.892
Capacity ablation	0.00258	25.88	0.920

Appendix

Table 18: Additional hard-code reconstruction metrics for the same checkpoints as Table 7 . Each setting is a single-seed run.

Component	Setting
Dataset split	6149 train / 1020 validation / 1020 test, as in Study 4
Input	$256\times 256$ RGB
Teacher	Frozen DINO ViT-S/8, final spatial patch tokens, normalized before cosine evaluation
Teacher source	Official facebookresearch/dino
Teacher checkpoint	dino_deitsmall8_pretrain.pth , official release
Teacher grid	$32\times 32$ patch-token embeddings

Appendix

Table 19: Settings for Study 5.

Representation Learning

Representation learning develops data transformations that expose useful structure for prediction, transfer, generation, and control.

See all 813 papers

Relevance-Guided Residual Calibration for Spectral Compression of Dense Retrieval Embeddings
Oct 26, 2026Yongkang Li, Panagiotis Eustratiadis, Evangelos KanoulasEmbedding Compression Dense Retrieval
University of Amsterdam Amsterdam, The Netherlands
Does Graph Compression Preserve Signal Propagation?
Jul 25, 2026Kawshik Banerjee, Khaled Mohammed SaifuddinGraph Signal Processing Graph Coarsening
School of Computing, Southern Illinois University, Carbondale, IL, USA
Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data
Jul 13, 2026Shikai Qiu, Marc Finzi, Yujia Zheng +2Model Compression Neural Network Generalization
New York University · Carnegie Mellon University

Oct 26, 2026J/K move · Enter open · S save

Relevance-Guided Residual Calibration for Spectral Compression of Dense Retrieval Embeddings

Yongkang Li, Panagiotis Eustratiadis, Evangelos Kanoulas

University of Amsterdam Amsterdam, The Netherlands

Embedding Compression Dense Retrieval

Open paper AskPDF arXiv

Spectral compression reduces the storage and scoring costs of dense retrieval by projecting embeddings onto a smaller principal subspace. However, its corpus-derived weighting rules tie all retained directions to a shared spectral trend, without directly accounting for their individual contributions to relevance. To address this, we propose Relevance-Guided Residual Calibration (RRC), a closed-form method for refining spectral weights using relevance judgments. RRC estimates margin-based weights from the means and variances of positive--negative score contributions along each retained direction. It retains directions with positive estimated weights, decomposes their log weights into a fitted power-law trend and a residual, and adds the residual to the compressor's log weights on this support. This allows relevance judgments to adjust individual directions while preserving the compressor's overall spectral trend. RRC applies to PCA, Whitening, and SpecTemp, and incorporates the corrections into the existing transformation shared by documents and queries, without iterative model training or an additional inference stage. Experiments with three encoders on nine datasets covering conventional and reasoning-intensive retrieval show that SpecTemp + RRC achieves the highest mean effectiveness among tested compressors on the BEIR group and BRIGHT at every target dimension. On the five evaluated BRIGHT datasets, it improves over SpecTemp by an average of 2.34 nDCG@10 points at 768 dimensions. The gains also persist under scalar and product quantization, improving the trade-off between per-document storage and retrieval effectiveness. Our code is available at: https://anonymous.4open.science/r/rrc-spectral-compression-B5CE/

Abstract

Representation Learning

Explore similar work

Relevance-Guided Residual Calibration for Spectral Compression of Dense Retrieval Embeddings

Does Graph Compression Preserve Signal Propagation?

Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data