TY - GEN
T1 - Compressing data on graphs with clusters
AU - Asadi, Amir R.
AU - Abbe, Emmanuel
AU - Verdú, Sergio
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/8/9
Y1 - 2017/8/9
N2 - This paper investigates the fundamental limits for compressing data on graphs, exploiting dependencies due to community structures in the graph. The source model, referred to as the data block model (DBM), is a mixture of discrete memoryless sources determined by the community structure of a stochastic block model (SBM). The main result gives the optimal expected length of a lossless compressor when the community signal is strong enough, a condition on the edge probabilities and the data distributions, which can take place below the exact recovery threshold of the SBM. This is derived in part by obtaining the threshold for exact recovery in SBMs with strong side information, a result of independent interest, which extends the CH-divergence threshold. Finally we discuss compressing data with almost exact recovery algorithms.
AB - This paper investigates the fundamental limits for compressing data on graphs, exploiting dependencies due to community structures in the graph. The source model, referred to as the data block model (DBM), is a mixture of discrete memoryless sources determined by the community structure of a stochastic block model (SBM). The main result gives the optimal expected length of a lossless compressor when the community signal is strong enough, a condition on the edge probabilities and the data distributions, which can take place below the exact recovery threshold of the SBM. This is derived in part by obtaining the threshold for exact recovery in SBMs with strong side information, a result of independent interest, which extends the CH-divergence threshold. Finally we discuss compressing data with almost exact recovery algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85034081327&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034081327&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2017.8006796
DO - 10.1109/ISIT.2017.8006796
M3 - Conference contribution
AN - SCOPUS:85034081327
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1583
EP - 1587
BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017
Y2 - 25 June 2017 through 30 June 2017
ER -