Random Edge Coding: One-Shot Compression of LargeLebeled Graphs
Jul 24, 2023
Sprecher:innen
Daniel Severo
Sprecher:in · 0 Follower:innen
James Townsend
Sprecher:in · 0 Follower:innen
Ashish Khisti
Sprecher:in · 0 Follower:innen
Alireza Makhzani
Sprecher:in · 0 Follower:innen
Über
We present a one-shot method for compressing large labeled graphs called Random Edge Coding. When paired with a parameter-free model based on Pólya's Urn, the worst-case computational and memory complexities scale quasi-linearly and linearly with the number of observed edges, making it efficient on sparse graphs, and requires only integer arithmetic. Key to our method is bits-back coding, which is used to sample edges and vertices without replacement from the edge-list in a way that preserves the structure of the graph. Optimality is proven under a class of random graph models that are invariant to permutations of the edges and of vertices within an edge. Experiments indicate Random Edge Coding can achieve competitive compression performance on real-world network datasets and scales to graphs with millions of nodes and edges.We present a one-shot method for compressing large labeled graphs called Random Edge Coding. When paired with a parameter-free model based on Pólya's Urn, the worst-case computational and memory complexities scale quasi-linearly and linearly with the number of observed edges, making it efficient on sparse graphs, and requires only integer arithmetic. Key to our method is bits-back coding, which is used to sample edges and vertices without replacement from the edge-list in a way that preserves th…
Gefällt euch das Format? Vertraut auf SlidesLive, um euer nächstes Event festzuhalten!
Professionelle Aufzeichnung und Livestreaming – weltweit.
Freigeben
Empfohlene Videos
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind
Exponential Smoothing for Off-Policy Learning
Später ansehen
Imad Aouali, …
PCA-based Multi-Task Learning: a Random Matrix Approach
Später ansehen
On The Global Convergence of Reinforcement Learning Algorithms With Neural Network Parametrization
Später ansehen
Mudit Gaur, …
Panel: LLM Tooling Across Industry and Academia
Später ansehen
Anna Goldie, …
Mentorship Hour
Später ansehen
Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions
Später ansehen
Chenyi Zhang, …