論文の概要: Partition and Code: learning how to compress graphs
- arxiv url: http://arxiv.org/abs/2107.01952v1
- Date: Mon, 5 Jul 2021 11:41:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-06 15:05:13.382875
- Title: Partition and Code: learning how to compress graphs
- Title（参考訳）: 分割とコード:グラフを圧縮する方法を学ぶ
- Authors: Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, Michael M.
Bronstein
- Abstract要約: まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。
提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
- 参考スコア（独自算出の注目度）: 50.29024357495154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 on which we learn a probability distribution, and finally,
an entropy encoder translates the representation into bits. All three steps are
parametric and can be trained with gradient descent. We theoretically compare
the compression quality of several graph encodings and prove, under mild
conditions, a total ordering of their expected description lengths. Moreover,
we show that, under the same conditions, PnC achieves compression gains w.r.t.
the baselines that grow either linearly or quadratically with the number of
vertices. Our algorithms are quantitatively evaluated on diverse real-world
networks obtaining significant performance improvements with respect to
different families of non-parametric and parametric graph compressors.
- Abstract（参考訳）: 機械学習を使ってグラフデータを圧縮できますか?
グラフに順序がないことは、従来の圧縮アルゴリズムにとって大きな課題となり、到達可能なゲインと関連するパターンを見つける能力が制限される。
一方、ほとんどのグラフ圧縮アプローチは、ドメイン依存の手作り表現に依存しており、基礎となるグラフ分布に適応できない。
この研究は、損失のないグラフ圧縮法がエントロピーストレージの下限に近づくために必要な原則を確立することを目的としている。
グラフ分布について厳密な仮定をする代わりに、圧縮器をデータから学び、未知のインスタンスに一般化できる確率モデルとして定式化する。
まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、最後にエントロピーエンコーダが表現をビットに変換する。
3つのステップはすべてパラメトリックであり、勾配降下でトレーニングすることができる。
理論上,複数のグラフエンコーディングの圧縮品質を比較し,穏やかな条件下で,期待される記述長の総順序付けを証明した。
さらに,PnCは,同じ条件下で圧縮ゲインw.r.tを達成することを示す。
頂点の数とともに直線的にまたは二次的に成長する基線。
本アルゴリズムは,非パラメトリックグラフ圧縮機とパラメトリックグラフ圧縮機の異なるファミリーについて,実世界の多様なネットワーク上で定量的に評価される。
関連論文リスト
- Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - Compression of Structured Data with Autoencoders: Provable Benefit of
Nonlinearities and Depth [83.15263499262824]
勾配勾配勾配は入力のスパース構造を完全に無視する解に収束することを示す。
浅層構造にデノナイジング関数を付加することにより,スパースデータの圧縮におけるガウス性能の改善方法を示す。
CIFAR-10 や MNIST などの画像データセットに対して,本研究の成果を検証した。
論文 参考訳（メタデータ） (2024-02-07T16:32:29Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - Graph Pooling with Maximum-Weight $k$-Independent Sets [12.251091325930837]
最大ウェイト$k$非依存集合のグラフ理論的概念に基づくグラフ粗化機構を導入する。
我々は、経路長の歪み境界の理論的保証と、粗化グラフにおける重要な位相特性を保存できることを証明した。
論文 参考訳（メタデータ） (2022-08-06T14:12:47Z) - Bringing Your Own View: Graph Contrastive Learning without Prefabricated
Data Augmentations [94.41860307845812]
Self-supervisionは最近、グラフ学習の新しいフロンティアに力を入れている。
GraphCLは、グラフデータ拡張のアドホックな手作業による選択によって反映されたプレハブ付きプリファブリックを使用する。
グラフ生成器のパラメータ空間における学習可能な連続前処理へと拡張した。
我々は、情報最小化(InfoMin)と情報ボトルネック(InfoBN)の2つの原則を利用して、学習した事前情報を規則化する。
論文 参考訳（メタデータ） (2022-01-04T15:49:18Z) - Intrusion-Free Graph Mixup [33.07540841212878]
グラフニューラルネットワーク(GNN)の一般化を改善するための,単純かつ効果的な正規化手法を提案する。
視覚とテキストのためのMixup regularizerの最近の進歩を利用して、ランダムなサンプルペアとそのラベルを補間して、トレーニング用の合成サンプルを作成する。
提案手法は,グラフ分類学習を効果的に正規化することが可能であり,一般的なグラフ拡張ベースラインよりも予測精度が優れている。
論文 参考訳（メタデータ） (2021-10-18T14:16:00Z) - Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
Graphonは任意のサイズでグラフを生成する非パラメトリックモデルであり、グラフから簡単に誘導できる。
解析可能でスケーラブルなグラフ生成モデルを構築するために,textitgraphon autoencoder という新しいフレームワークを提案する。
線形グルーポン分解モデルはデコーダとして機能し、潜在表現を活用して誘導されたグルーポンを再構成する。
論文 参考訳（メタデータ） (2021-05-29T08:11:40Z) - Graph Coarsening with Neural Networks [8.407217618651536]
本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。
粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
論文 参考訳（メタデータ） (2021-02-02T06:50:07Z) - Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
本稿では,graphonと呼ばれる非パラメトリックグラフモデルを学ぶための新しい原理的手法を提案する。
提案手法は, 従来の最先端手法の欠点を克服し, 合成データと実データの両方でそれを上回る。
論文 参考訳（メタデータ） (2020-12-10T13:04:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。