In contrast to time series, graphical data is data indexed by the vertices and edges of a graph. Modern applications such as the internet, social networks, genomics and proteomics generate graphical data, often at large scale. The large scale argues for the need to compress such data for storage and subsequent processing. Since this data might have several components available in different locations, it is also important to study distributed compression of graphical data. In this paper, we derive a rate region for this problem which is a counterpart of the Slepian-Wolf theorem. We characterize the rate region when the statistical description of the distributed graphical data can be modeled as being one of two types - as a member of a sequence of marked sparse Erdos-Renyi ensembles or as a member of a sequence of marked configuration model ensembles. Our results are in terms of a generalization of the notion of entropy introduced by Bordenave and Caputo in the study of local weak limits of sparse graphs. Furthermore, we give a generalization of this result for Erdos-Renyi and configuration model ensembles with more than two sources.


翻译:与时间序列相对照,图形数据是用图表的脊椎和边缘进行索引的数据。现代应用,如互联网、社交网络、基因组学和蛋白质组学等,往往大规模地生成图形数据。大比例表示需要压缩这些数据用于储存和随后的处理。由于这些数据在不同地点可能有几个组件,研究分布式图形数据压缩也很重要。在本文中,我们为这一问题得出一个比率区域,这是Slepian-Wolf 理论的对应区域。当分布式图形数据的统计描述可以建模为两种类型之一时,我们给这个比率区域定性,即分布式图形数据的统计描述可以建模为两种类型之一――作为有标记的稀薄 Erdos-Renyi ensengembles 序列的成员,或者作为有标记的配置模型组合序列的成员。我们的结果是,Bordenave和Caputo在研究本地稀薄图形的弱限值时,将这种结果概括为两种类型之一。此外,我们用两个比模型来源更宽泛的Erdos-Renyi和配置模型来源。

0
下载
关闭预览

相关内容

【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Facebook PyText 在 Github 上开源了
AINLP
7+阅读 · 2018年12月14日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
38+阅读 · 2021年8月31日
Arxiv
19+阅读 · 2020年7月13日
A Survey of Deep Learning for Scientific Discovery
Arxiv
29+阅读 · 2020年3月26日
Arxiv
45+阅读 · 2019年12月20日
Arxiv
4+阅读 · 2019年1月14日
Arxiv
6+阅读 · 2018年1月29日
VIP会员
相关VIP内容
【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
Facebook PyText 在 Github 上开源了
AINLP
7+阅读 · 2018年12月14日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
38+阅读 · 2021年8月31日
Arxiv
19+阅读 · 2020年7月13日
A Survey of Deep Learning for Scientific Discovery
Arxiv
29+阅读 · 2020年3月26日
Arxiv
45+阅读 · 2019年12月20日
Arxiv
4+阅读 · 2019年1月14日
Arxiv
6+阅读 · 2018年1月29日
Top
微信扫码咨询专知VIP会员