Many multivariate data such as social and biological data exhibit complex dependencies that are best characterized by graphs. Unlike sequential data, graphs are, in general, unordered structures. This means we can no longer use classic, sequential-based compression methods on these graph-based data. Therefore, it is necessary to develop new methods for graph compression. In this paper, we present universal source coding methods for the lossless compression of unweighted, undirected, unlabelled graphs. We encode in two steps: 1) transforming graph into a rooted binary tree, 2) the encoding rooted binary tree using graph statistics. Our coders showed better compression performance than other source coding methods on both synthetic and real-world graphs. We then applied our graph coding methods for model selection of Gaussian graphical models using minimum description length (MDL) principle finding the description length of the conditional independence graph. Experiments on synthetic data show that our approach gives better performance compared to common model selection methods. We also applied our approach to electrocardiogram (ECG) data in order to explore the differences between graph models of two groups of subjects.


翻译:社会数据和生物数据等许多多变数据表现出以图表为最佳特征的复杂依赖性。 与相继数据不同, 图表一般是无顺序结构。 这意味着我们不能再在这些基于图形的数据中使用经典的、 以顺序为基础的压缩方法。 因此, 有必要开发新的图形压缩方法 。 在本文中, 我们为无损的、 未加权的、 未定向的、 未标签的图形提供了通用源代码方法。 我们分两个步骤编码:1) 将图形转换成根拔的二进制树,2) 使用图表统计的编码根拔的二进制树。 我们的编码器显示, 压缩性能优于合成图和真实世界图的其他源编码方法。 我们随后运用了我们的图形编码方法, 用于使用最小描述长度( MDL) 原则来选择高斯图形模型, 查找有条件的独立图形的描述长度。 合成数据的实验显示, 我们的方法比通用的模型选择方法表现得更好。 我们还采用了电心图(ECG) 数据方法, 以便探索两个主题组的图形模型的差异 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
4+阅读 · 2017年12月5日
Arxiv
10+阅读 · 2021年11月3日
Arxiv
56+阅读 · 2021年5月3日
Compression of Deep Learning Models for Text: A Survey
Arxiv
6+阅读 · 2019年11月14日
Arxiv
5+阅读 · 2017年4月12日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
4+阅读 · 2017年12月5日
Top
微信扫码咨询专知VIP会员