論文の概要: A pseudo-inverse of a line graph

• arxiv url: http://arxiv.org/abs/2508.09412v1
• Date: Wed, 13 Aug 2025 01:04:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-14 20:42:00.719772
• Title: A pseudo-inverse of a line graph
• Title（参考訳）: 線グラフの擬逆
• Authors: Sevvandi Kandanaarachchi, Philip Kilby, Cheng Soon Ong,
• Abstract要約: 線グラフの空間に小さな摂動が存在する場合について検討し、対応するルートグラフの復元を試みる。 本稿では,線グラフの最小のエッジを編集し,ルートグラフの発見を可能にする線形整数プログラムを提案する。
• 参考スコア（独自算出の注目度）: 7.4250687861347995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Line graphs are an alternative representation of graphs where each vertex of the original (root) graph becomes an edge. However not all graphs have a corresponding root graph, hence the transformation from graphs to line graphs is not invertible. We investigate the case when there is a small perturbation in the space of line graphs, and try to recover the corresponding root graph, essentially defining the inverse of the line graph operation. We propose a linear integer program that edits the smallest number of edges in the line graph, that allow a root graph to be found. We use the spectral norm to theoretically prove that such a pseudo-inverse operation is well behaved. Illustrative empirical experiments on Erd\H{o}s-R\'enyi graphs show that our theoretical results work in practice.
• Abstract（参考訳）: 線グラフは、元の(ルート)グラフの各頂点がエッジとなるグラフの代替表現である。 しかしながら、すべてのグラフが対応するルートグラフを持つわけではないので、グラフから線グラフへの変換は可逆ではない。 線グラフの空間に小さな摂動が存在する場合について検討し、線グラフ演算の逆を本質的に定義して対応する根グラフの復元を試みる。 線形整数プログラムを提案し、線グラフの最小のエッジを編集し、ルートグラフの発見を可能にする。 このような擬似逆演算がうまく振る舞うことを理論的に証明するためにスペクトルノルムを用いる。 Erd\H{o}s-R\'enyi グラフに関する実証実験は、我々の理論結果が実際に動作することを示している。

関連論文リスト

• Theoretical Insights into Line Graph Transformation on Graph Learning [3.0574700762497744]
  線グラフ変換はグラフ理論において広く研究されており、線グラフの各ノードは元のグラフのエッジに対応する。 これは、変換された線グラフに適用された一連のグラフニューラルネットワーク(GNN)にインスピレーションを与え、様々なグラフ表現学習タスクに有効であることが証明された。 本研究では,Weisfeiler-Leman (WL) テストに挑戦することが知られている2種類のグラフ,Cai-F"urer-Immerman (CFI) グラフと強い正則グラフに着目した。
  論文  参考訳（メタデータ） (2024-10-21T16:04:50Z)
• Graphons of Line Graphs [6.822247359790484]
  スパースグラフのサブセットに光を放つ簡単な方法を示す。 グラフが特定の性質を満たすことを示し、この2次性質はスパースであるが、密度の高い線グラフをもたらす。 特に、星グラフは、密度の高い直線グラフと直線グラフのゼロでないグラフを生じる2次特性を満たす。
  論文  参考訳（メタデータ） (2024-09-03T06:50:03Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  我々は、非ユークリッドグラフを学習可能なグラフワードに変換するGraph2Seqエンコーダを特徴とするGraphsGPTを紹介する。 GraphGPTデコーダは、元のグラフをGraph Wordsから再構成し、情報等価性を保証する。
  論文  参考訳（メタデータ） (2024-02-04T12:29:40Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  グラフ機械学習のための微粒なグラフ合理化(FIG)を提案する。 私たちのアイデアは、入力ノード間のリッチなインタラクションを提供するセルフアテンションメカニズムによって推進されます。 実験では,実世界の7つのデータセットを対象とし,提案したFIGは,13のベースライン手法と比較して大きな性能上の優位性を示した。
  論文  参考訳（メタデータ） (2023-12-13T02:56:26Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。 ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。 既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
  論文  参考訳（メタデータ） (2023-06-13T08:06:10Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。 これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。 我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
  論文  参考訳（メタデータ） (2022-12-15T22:11:34Z)

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

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