Partition and Code: Learning how to Compress Graphs
Dec 6, 2021
Speakers
Giorgos Bouritsas
Speaker · 0 followers
Andreas Loukas
Speaker · 0 followers
Nikolaos Karalias
Speaker · 0 followers
Michael M. Bronstein
Speaker · 10 followers
About
Can we use machine learning to compress graph data? The absence of ordering in graphs poses a significant challenge to conventional compression algorithms, limiting their attainable gains as well as their ability to discover relevant patterns. On the other hand, most graph compression approaches rely on domain-dependent handcrafted representations and cannot adapt to different underlying graph distributions. This work aims to establish the necessary principles a lossless graph compression method should follow to approach the entropy storage lower bound. Instead of making rigid assumptions about the graph distribution, we formulate the compressor as a probabilistic model that can be learned from data and generalise to unseen instances. Our “"Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary, and finally, an entropy encoder translates the representation into bits. All three steps are parametric and can be trained with gradient descent. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant storage gains with respect to different families of non-parametric and parametric graph compressors.Can we use machine learning to compress graph data? The absence of ordering in graphs poses a significant challenge to conventional compression algorithms, limiting their attainable gains as well as their ability to discover relevant patterns. On the other hand, most graph compression approaches rely on domain-dependent handcrafted representations and cannot adapt to different underlying graph distributions. This work aims to establish the necessary principles a lossless graph compression method…
Organizer
NeurIPS 2021
Account · 1.9k followers
Categories
Mathematics
Category · 2.4k presentations
AI & Data Science
Category · 10.8k presentations
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Optimal Policies Tend To Seek Power
Watch later
Alex Turner, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Shift Invariance Can Reduce Adversarial Robustness
Watch later
Vasu Singla, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
On the Generative Utility of Cyclic Conditionals
Watch later
Chang Liu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
NASA Initiatives & Opportunities Supporting ML in the Physical Sciences
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
Watch later
Shicong Cen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
"Legitimacy" in the Computational Elicitation of PReferences in Mechanism Design
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%