論文の概要: Graphons of Line Graphs

• arxiv url: http://arxiv.org/abs/2409.01656v1
• Date: Tue, 3 Sep 2024 06:50:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-06 02:43:06.861881
• Title: Graphons of Line Graphs
• Title（参考訳）: 線グラフのグラフ
• Authors: Sevvandi Kandanaarachchi, Cheng Soon Ong,
• Abstract要約: グラフンは収束グラフ列の極限である。 スパースグラフはゼログラフに収束し、生成されたグラフは空か端なしとなる。 スパースグラフの特定の部分集合に光を放つ簡単な方法を示す。
• 参考スコア（独自算出の注目度）: 6.822247359790484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A graphon is the limit of a converging graph sequence. Graphons of dense graphs are useful as they can act as a blueprint and generate graphs of arbitrary size with similar properties. But for sparse graphs this is not the case. Sparse graphs converge to the zero graphon, making the generated graphs empty or edgeless. Thus, the classical graphon definition fails for sparse graphs. Several methods have been proposed to overcome this limitation and to understand sparse graphs more deeply. However, the fragile nature of sparse graphs makes these methods mathematically complex. In this paper we show a simple method that can shed light on a certain subset of sparse graphs. The method involves mapping the original graphs to their line graphs. Line graphs map edges to vertices and connects edges when edges in the original graph share a vertex. We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs. In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs. Similarly, superlinear preferential attachment graphs give rise to dense line graphs almost surely. In contrast, dense graphs, including Erdos-Renyi graphs make the line graphs sparse, resulting in the zero graphon.
• Abstract（参考訳）: グラフンは収束グラフ列の極限である。 密度グラフのグラフは、ブループリントとして機能し、同様の性質を持つ任意の大きさのグラフを生成することができるため、有用である。 しかし、スパースグラフではそうではない。 スパースグラフはゼログラフに収束し、生成されたグラフは空か端なしとなる。 したがって、古典的なグラフ定義はスパースグラフでは失敗する。 この制限を克服し、スパースグラフをより深く理解するために、いくつかの方法が提案されている。 しかし、スパースグラフの脆弱な性質は、これらの手法を数学的に複雑にする。 本稿では,スパースグラフの特定の部分集合に光を放つ簡単な方法を示す。 この手法では、元のグラフを行グラフにマッピングする。 線グラフはエッジを頂点にマッピングし、元のグラフのエッジが頂点を共有するときにエッジを接続する。 グラフが特定の性質を満たすことを示し、この2次性質はスパースであるが、密度の高い線グラフをもたらす。 特に、星グラフは、密度の高い直線グラフと直線グラフのゼロでないグラフを生じる2次特性を満たす。 同様に、超線型優越アタッチメントグラフは、ほぼ確実に高密度な直線グラフをもたらす。 対照的に、エルドス=レーニグラフを含む密度グラフは線グラフをスパースにし、結果としてゼログラフとなる。

関連論文リスト

• Parametric Graph Representations in the Era of Foundation Models: A Survey and Position [69.48708136448694]
  グラフは、包括的なリレーショナルデータをモデル化するために、過去数十年間、ビッグデータとAIで広く使われてきた。 有意義なグラフ法則の同定は、様々な応用の有効性を著しく向上させることができる。
  論文  参考訳（メタデータ） (2024-10-16T00:01:31Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  我々は、非ユークリッドグラフを学習可能なグラフワードに変換するGraph2Seqエンコーダを特徴とするGraphsGPTを紹介する。 GraphGPTデコーダは、元のグラフをGraph Wordsから再構成し、情報等価性を保証する。
  論文  参考訳（メタデータ） (2024-02-04T12:29:40Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。 ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。 既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
  論文  参考訳（メタデータ） (2023-06-13T08:06:10Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
  我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。 我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
  論文  参考訳（メタデータ） (2023-06-07T15:04:58Z)
• A Graph Convolution for Signed Directed Graphs [0.0]
  署名付き有向グラフのグラフ畳み込みはまだ多くは提供されていない。 複素数を介してグラフ情報を符号化する複素エルミート隣接行列を提案する。 私たちの知る限りでは、これは標識のあるグラフに対する初めてのスペクトル畳み込みである。
  論文  参考訳（メタデータ） (2022-08-23T01:58:35Z)
• G-Mixup: Graph Data Augmentation for Graph Classification [55.63157775049443]
  Mixupは、2つのランダムサンプル間の特徴とラベルを補間することにより、ニューラルネットワークの一般化とロバスト性を改善する上で優位性を示している。 グラフ分類のためのグラフを増補するために$mathcalG$-Mixupを提案し、グラフの異なるクラスのジェネレータ(すなわちグラフ)を補間する。 実験により、$mathcalG$-MixupはGNNの一般化とロバスト性を大幅に改善することが示された。
  論文  参考訳（メタデータ） (2022-02-15T04:09:44Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。 グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。 幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-12-30T18:51:06Z)
• High-Order Relation Construction and Mining for Graph Matching [36.880853889521845]
  高次情報を記述するために、反復線グラフが最初に導入された。 本稿では,HGMN(High-order Graph Matching Network)と呼ばれる新しいグラフマッチング手法を提案する。 実用的な制約を課すことで、HGMNは大規模グラフに拡張性を持たせることができる。
  論文  参考訳（メタデータ） (2020-10-09T03:30:02Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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