Recursive Spectral Graph Partitioning Coding for Index Assignment in Semantic Communications

Transmitting quantized semantic embeddings over a bit-flip channel requires a binary mapping that minimizes expected reconstruction distortion. The classical Binary Switching Algorithm (BSA) ($\mathcal{O}(K^3 \log K)$ for $K$ centroids) yields locally optimal assignments but ignores hierarchical bit significance, making it incompatible with Unequal Error Protection (UEP). We propose Recursive Spectral Graph Partitioning (RSGP), which recursively bisects the centroid affinity graph along the Fiedler eigenvector so that early bits separate semantically distant groups while later bits refine local structure. RSGP runs in $\mathcal{O}(K^3)$ with no iterative outer loop, and is the only method studied to show a systematic positive UEP gain: protecting early bits over later ones improves accuracy for RSGP, while being neutral or harmful for unstructured assignments. Experiments on the Banking77 dataset and the Massive Text Embedding Benchmark (MTEB) confirm that RSGP consistently matches or exceeds BSA accuracy across codebook sizes and error profiles.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21238
Primary Topic
Advanced Data Compression Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Recursive Spectral Graph Partitioning Coding for Index Assignment in Semantic Communications

Mohamad Assaad, Louis-Adrien Dufréne, Grégoire Lefebvre, Quentin Lampin et al.
arXiv (Cornell University)
Advanced Data Compression Techniques
preprint

Recursive Spectral Graph Partitioning Coding for Index Assignment in Semantic Communications

Mohamad Assaad, Louis-Adrien Dufréne, Grégoire Lefebvre, Quentin Lampin, Leonardo Roque
preprint en

Abstract

Transmitting quantized semantic embeddings over a bit-flip channel requires a binary mapping that minimizes expected reconstruction distortion. The classical Binary Switching Algorithm (BSA) ($\mathcal{O}(K^3 \log K)$ for $K$ centroids) yields locally optimal assignments but ignores hierarchical bit significance, making it incompatible with Unequal Error Protection (UEP). We propose Recursive Spectral Graph Partitioning (RSGP), which recursively bisects the centroid affinity graph along the Fiedler eigenvector so that early bits separate semantically distant groups while later bits refine local structure. RSGP runs in $\mathcal{O}(K^3)$ with no iterative outer loop, and is the only method studied to show a systematic positive UEP gain: protecting early bits over later ones improves accuracy for RSGP, while being neutral or harmful for unstructured assignments. Experiments on the Banking77 dataset and the Massive Text Embedding Benchmark (MTEB) confirm that RSGP consistently matches or exceeds BSA accuracy across codebook sizes and error profiles.

arXiv (Cornell University)
Advanced Data Compression Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon