論文の概要: 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を達成することを示す。 頂点の数とともに直線的にまたは二次的に成長する基線。 本アルゴリズムは,非パラメトリックグラフ圧縮機とパラメトリックグラフ圧縮機の異なるファミリーについて,実世界の多様なネットワーク上で定量的に評価される。

関連論文リスト

• Generalized Graphon Process: Convergence of Graph Frequencies in Stretched Cut Distance [30.279435887366578]
  スパースグラフ列は、従来のカット距離の定義の下で自明なグラフオンに収束する。 我々は、スパースグラフ列の収束を記述するために、一般化グラフと拡張カット距離の概念を利用する。 その結果,スパースグラフ間の移動学習の可能性が示唆された。
  論文  参考訳（メタデータ） (2023-09-11T06:34:46Z)
• Graph Pooling with Maximum-Weight $k$-Independent Sets [12.251091325930837]
  最大ウェイト$k$非依存集合のグラフ理論的概念に基づくグラフ粗化機構を導入する。 我々は、経路長の歪み境界の理論的保証と、粗化グラフにおける重要な位相特性を保存できることを証明した。
  論文  参考訳（メタデータ） (2022-08-06T14:12:47Z)
• Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
  機械学習モデルのデータ並列最適化では、労働者はモデルの推定値を改善するために協力する。 本稿では、労働者が同じデータ分散を共有するとき、疎結合な分散最適化の正確な図面を描くことを目的とする。 我々の理論は深層学習における経験的観察と一致し、異なるグラフトポロジーの相対的メリットを正確に記述する。
  論文  参考訳（メタデータ） (2022-06-07T08:19:06Z)
• 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)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。