論文の概要: Graph Summarization via Node Grouping: A Spectral Algorithm

• arxiv url: http://arxiv.org/abs/2211.04169v1
• Date: Tue, 8 Nov 2022 11:23:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 17:13:22.419627
• Title: Graph Summarization via Node Grouping: A Spectral Algorithm
• Title（参考訳）: ノードグループ化によるグラフ要約:スペクトルアルゴリズム
• Authors: Arpit Merchant, Michael Mathioudakis, Yanhao Wang
• Abstract要約: ノードグループ化によるグラフの要約は、簡潔なグラフ表現を構築する一般的な方法である。 本稿では,和算における損失最小化問題を等価整数問題に再構成する。 本研究では,現在最先端の要約アルゴリズムと比較して,SpecSummが効率よく高品質な要約を生成することを示す。
• 参考スコア（独自算出の注目度）: 4.967873417059781
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Graph summarization via node grouping is a popular method to build concise graph representations by grouping nodes from the original graph into supernodes and encoding edges into superedges such that the loss of adjacency information is minimized. Such summaries have immense applications in large-scale graph analytics due to their small size and high query processing efficiency. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer maximization problem. By initially allowing relaxed (fractional) solutions for integer maximization, we analytically expose the underlying connections to the spectral properties of the adjacency matrix. Consequently, we design an algorithm called SpecSumm that consists of two phases. In the first phase, motivated by spectral graph theory, we apply k-means clustering on the k largest (in magnitude) eigenvectors of the adjacency matrix to assign nodes to supernodes. In the second phase, we propose a greedy heuristic that updates the initial assignment to further improve summary quality. Finally, via extensive experiments on 11 datasets, we show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms and scales to graphs with millions of nodes.
• Abstract（参考訳）: ノードグループ化によるグラフ要約は、ノードを元のグラフからスーパーノードにグループ化し、エッジをスーパーエッジに符号化することで、隣接情報の損失を最小限に抑えることで、簡潔なグラフ表現を構築する一般的な方法である。 このような要約は、小さなサイズと高いクエリ処理効率のために、大規模なグラフ解析に多大な応用がある。 本稿では,和算における損失最小化問題を等価整数最大化問題に再構成する。 まず、整数最大化のための緩和された(フラクショナルな)解を許容することにより、基底となる接続を隣接行列のスペクトル特性に解析的に公開する。 その結果、2つのフェーズからなるSpecSummと呼ばれるアルゴリズムを設計する。 スペクトルグラフ理論に動機付けられた第1フェーズでは、隣接行列の最大(大きさ)固有ベクトル k に対して k-平均クラスタリングを適用し、スーパーノードにノードを割り当てる。 第2段階では,初期課題を更新し,要約品質をさらに向上する欲求的ヒューリスティックを提案する。 最後に,11のデータセットに関する広範な実験を通じて,specsummは最先端の要約アルゴリズムや数百万ノードのグラフに対するスケールと比較して,高品質な要約を効率的に生成することを示した。

関連論文リスト

• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。 我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。 この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
  論文  参考訳（メタデータ） (2023-03-24T12:37:43Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。 提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。 第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
  論文  参考訳（メタデータ） (2022-12-01T11:49:07Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  本稿では,その構造的依存関係に応じてノード間の相互作用をキャプチャするグラフマルチセットトランス (GMT) を提案する。 実験の結果,GMTはグラフ分類ベンチマークにおいて,最先端のグラフプーリング法を著しく上回っていることがわかった。
  論文  参考訳（メタデータ） (2021-02-23T07:45:58Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling [31.812988573924674]
  グラフニューラルネットワーク(GNN)では、プール演算子は入力グラフの局所的な要約を計算し、そのグローバルな特性をキャプチャする。 グラフトポロジ全体を保存しながら粗いグラフを生成するGNNのためのプール演算子であるNode Decimation Pooling (NDP)を提案する。 NDPは、最先端のグラフプーリング演算子よりも効率的であり、同時に、様々なグラフ分類タスクにおける競合性能にも達する。
  論文  参考訳（メタデータ） (2019-10-24T21:42:12Z)

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

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