論文の概要: Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets

• arxiv url: http://arxiv.org/abs/2407.16850v1
• Date: Tue, 23 Jul 2024 21:26:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 19:18:45.803871
• Title: Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets
• Title（参考訳）: 三角形リッチ集合による高密度サブグラフファミリグラフの被覆
• Authors: Sabyasachi Basu, Daniel Paul-Pena, Kun Qian, C. Seshadhri, Edward W Huang, Karthik Subbian,
• Abstract要約: 現実世界のグラフは世界規模でスパースであるが、高密度の「ポケット」が多数含まれている。 グラフマイニングの基本的な課題は、これらの密度の高い部分グラフを発見することである。 我々は、正規三角形リッチ(RTR)ファミリーの新しい定義を用いて、この問題の数学的定式化を行う。 証明可能なアルゴリズム RTRExtractor を設計し,任意の RTR 集合をカバーする RTR ファミリーを探索する。
• 参考スコア（独自算出の注目度）: 15.078359519557207
• License:
• Abstract: Graphs are a fundamental data structure used to represent relationships in domains as diverse as the social sciences, bioinformatics, cybersecurity, the Internet, and more. One of the central observations in network science is that real-world graphs are globally sparse, yet contains numerous "pockets" of high edge density. A fundamental task in graph mining is to discover these dense subgraphs. Most common formulations of the problem involve finding a single (or a few) "optimally" dense subsets. But in most real applications, one does not care for the optimality. Instead, we want to find a large collection of dense subsets that covers a significant fraction of the input graph. We give a mathematical formulation of this problem, using a new definition of regularly triangle-rich (RTR) families. These families capture the notion of dense subgraphs that contain many triangles and have degrees comparable to the subgraph size. We design a provable algorithm, RTRExtractor, that can discover RTR families that approximately cover any RTR set. The algorithm is efficient and is inspired by recent results that use triangle counts for community testing and clustering. We show that RTRExtractor has excellent behavior on a large variety of real-world datasets. It is able to process graphs with hundreds of millions of edges within minutes. Across many datasets, RTRExtractor achieves high coverage using high edge density datasets. For example, the output covers a quarter of the vertices with subgraphs of edge density more than (say) $0.5$, for datasets with 10M+ edges. We show an example of how the output of RTRExtractor correlates with meaningful sets of similar vertices in a citation network, demonstrating the utility of RTRExtractor for unsupervised graph discovery tasks.
• Abstract（参考訳）: グラフは、社会科学、バイオインフォマティクス、サイバーセキュリティ、インターネットなどの分野における関係を表現するために使われる基本的なデータ構造である。 ネットワーク科学における中心的な観測の1つは、現実世界のグラフは全世界的に疎らであるが、高密度の「ポケット」が多数含まれていることである。 グラフマイニングの基本的な課題は、これらの密度の高い部分グラフを発見することである。 問題の一般的な定式化は、単一の(あるいは数個の)「最適」な部分集合を見つけることである。 しかし、ほとんどの実アプリケーションでは、最適性は気にしません。 代わりに、入力グラフのかなりの部分集合をカバーするような、高密度な部分集合の集合を見つけたいと思っています。 我々は、正規三角形リッチ(RTR)ファミリーの新しい定義を用いて、この問題の数学的定式化を行う。 これらの族は、多くの三角形を含む高密度な部分グラフの概念を捉え、部分グラフのサイズに匹敵する次数を持つ。 証明可能なアルゴリズム RTRExtractor を設計し,任意の RTR 集合をカバーする RTR ファミリーを探索する。 このアルゴリズムは効率的で、コミュニティのテストやクラスタリングに三角形数を使った最近の結果にインスパイアされている。 RTRExtractorは,様々な実世界のデータセットに対して優れた挙動を示す。 数分で数億のエッジでグラフを処理することができる。 多くのデータセットにまたがって、RTRExtractorは高エッジ密度データセットを使用して高いカバレッジを達成する。 例えば、10M以上のエッジを持つデータセットに対して、出力は(例えば)0.5ドル以上のエッジ密度のサブグラフで頂点の4分の1をカバーする。 本稿では、RTRExtractorの出力が、参照ネットワークにおいて意味のある類似した頂点の集合とどのように相関しているかを示す。

関連論文リスト

• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。 最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。 本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
  論文  参考訳（メタデータ） (2024-01-10T07:58:44Z)
• Jaccard-constrained dense subgraph discovery [2.4511852052357628]
  大きい対のジャカード類似係数を持つ高密度部分グラフを探索する。 我々は,我々のアルゴリズムが効率的であることを実験的に示し,合成データセットに基底真理を見つけ,実世界のデータセットから解釈可能な結果を提供する。
  論文  参考訳（メタデータ） (2023-08-30T10:33:02Z)
• A Robust Stacking Framework for Training Deep Graph Models with Multifaceted Node Features [61.92791503017341]
  数値ノード特徴とグラフ構造を入力とするグラフニューラルネットワーク(GNN)は,グラフデータを用いた各種教師付き学習タスクにおいて,優れた性能を示した。 IID(non-graph)データをGNNに簡単に組み込むことはできない。 本稿では、グラフ認識の伝播をIDデータに意図した任意のモデルで融合するロバストな積み重ねフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-06-16T22:46:33Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)
• COLOGNE: Coordinated Local Graph Neighborhood Sampling [1.6498361958317633]
  グラフノードのような個別の未順序オブジェクトを実数値ベクトルで置き換えることは、グラフデータから学ぶための多くのアプローチの中心である。 ノードベクトル表現の座標がグラフノードであるような離散ノード埋め込みを学習する問題に対処する。 これにより、ノードにもともと存在するすべての属性が保存されているため、グラフの解釈可能な機械学習アルゴリズムを設計する扉が開く。
  論文  参考訳（メタデータ） (2021-02-09T11:39:06Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。 本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
  論文  参考訳（メタデータ） (2020-08-03T08:48:41Z)
• Grale: Designing Networks for Graph Learning [68.23038997141381]
  我々は,数十億のノードを持つグラフのグラフ設計問題に対処するために,スケーラブルなGraleを提案する。 グレールは、(潜在的に弱い)類似性の異なる測度を融合して、そのノード間の高いタスク固有のホモフィリーを示すグラフを作成する。 Googleでは、数千億のノードを持つデータセットや、数十兆の潜在的なエッジを含む、20以上の異なる産業環境にGraleをデプロイしています。
  論文  参考訳（メタデータ） (2020-07-23T13:25:36Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Learning Deep Graph Representations via Convolutional Neural Networks [7.1945109570193795]
  本稿では,グラフ特徴写像の深部表現を学習するためのDeepMapというフレームワークを提案する。 グラフの学習された深部表現は、複雑な高次相互作用をキャプチャする密度で低次元のベクトルである。 我々は、様々なグラフ分類ベンチマークでDeepMapを実証的に検証し、最先端のパフォーマンスを実現することを実証した。
  論文  参考訳（メタデータ） (2020-04-05T08:49:27Z)

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

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