論文の概要: Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information Theoretic Measures

• arxiv url: http://arxiv.org/abs/2305.07138v1
• Date: Thu, 11 May 2023 21:03:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-05-15 14:35:42.856215
• Title: Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information Theoretic Measures
• Title（参考訳）: 情報理論による最適輸送グラフ要約の約束と限界
• Authors: Sepideh Neshatfar, Abram Magner, Salimeh Yasaei Sekeh
• Abstract要約: グラフ要約は、入力グラフデータセットのより小さなグラフ表現を生成する問題である。 本稿では,教師付きグラフ要約の問題点を考察し,情報理論を用いてクラスラベルに関する関連情報を保存することを目的とする。 サンプルグラフとクラスラベルに関連付けられた確率変数間の相互情報推定を最適輸送圧縮フレームワークに組み込んだ要約手法を提案する。
• 参考スコア（独自算出の注目度）: 3.179831861897336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph summarization is the problem of producing smaller graph representations of an input graph dataset, in such a way that the smaller compressed graphs capture relevant structural information for downstream tasks. There is a recent graph summarization method that formulates an optimal transport-based framework that allows prior information about node, edge, and attribute importance (never defined in that work) to be incorporated into the graph summarization process. However, very little is known about the statistical properties of this framework. To elucidate this question, we consider the problem of supervised graph summarization, wherein by using information theoretic measures we seek to preserve relevant information about a class label. To gain a theoretical perspective on the supervised summarization problem itself, we first formulate it in terms of maximizing the Shannon mutual information between the summarized graph and the class label. We show an NP-hardness of approximation result for this problem, thereby constraining what one should expect from proposed solutions. We then propose a summarization method that incorporates mutual information estimates between random variables associated with sample graphs and class labels into the optimal transport compression framework. We empirically show performance improvements over previous works in terms of classification accuracy and time on synthetic and certain real datasets. We also theoretically explore the limitations of the optimal transport approach for the supervised summarization problem and we show that it fails to satisfy a certain desirable information monotonicity property.
• Abstract（参考訳）: グラフ要約は、入力グラフデータセットのより小さなグラフ表現を生成する問題であり、より小さな圧縮グラフが下流タスクの関連する構造情報をキャプチャする。 最近のグラフ要約法では、ノード、エッジ、属性の重要性(その作業で定義されていない)をグラフ要約プロセスに組み込むために、最適なトランスポートベースのフレームワークを定式化している。 しかし、この枠組みの統計的性質についてはほとんど分かっていない。 この問題を解明するために,クラスラベルに関する関連情報を保持するための情報理論的手法を用いて,教師付きグラフ要約の問題を考える。 教師付き要約問題そのものに関する理論的視点を得るため、まず、要約グラフとクラスラベルの間のシャノン相互情報の最大化の観点から定式化する。 本稿では,この問題に対する近似結果のnp-hardnessを示し,提案する解に対して何を期待すべきかを制約する。 次に,サンプルグラフとクラスラベルに関連付けられた確率変数間の相互情報推定を最適輸送圧縮フレームワークに組み込んだ要約手法を提案する。 我々は,合成データと特定の実データ集合の分類精度と時間の観点から,従来よりも性能が向上していることを示す。 また, 教師付き要約問題に対する最適輸送手法の限界についても理論的に検討し, 所望の情報単調性を満足できないことを示す。

関連論文リスト

• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  既存のグラフ凝縮法は、凝縮グラフ内のノードと構造の合同最適化に依存している。 我々は、大規模グラフを小さなグラフノード集合に蒸留する、SFGCと呼ばれる新しい構造自由グラフ凝縮パラダイムを提唱する。
  論文  参考訳（メタデータ） (2023-06-05T07:53:52Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Unbiased Graph Embedding with Biased Graph Observations [52.82841737832561]
  基礎となるバイアスのないグラフから学習することで、バイアスのない表現を得るための、原則化された新しい方法を提案する。 この新たな視点に基づいて、そのような基礎となるグラフを明らかにするための2つの補完的手法を提案する。
  論文  参考訳（メタデータ） (2021-10-26T18:44:37Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• A Graph Data Augmentation Strategy with Entropy Preserving [11.886325179121226]
  本稿では,グラフ間の特徴情報を評価するための定量的指標として,新しいグラフエントロピー定義を提案する。 グラフエントロピーの保存を考慮し、摂動機構を用いてトレーニングデータを生成する効果的な方法を提案する。 提案手法はトレーニング過程におけるGCNの堅牢性と一般化能力を大幅に向上させる。
  論文  参考訳（メタデータ） (2021-07-13T12:58:32Z)
• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks [7.398195748292981]
  本稿では, グラフと入力グラフ間の相互情報の最大化に基づく, グラフニューラルネットワークのための新しいプーリング層を提案する。 プール層への入力グラフはノイズの多い通信チャネルの表現として見ることができることを示す。 最大相互情報に到達することは、グラフの最大重み独立集合を見つけることと等価であることを示す。
  論文  参考訳（メタデータ） (2021-07-03T11:19:28Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。 従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
  論文  参考訳（メタデータ） (2021-05-12T06:47:34Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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