論文の概要: Homomorphism distortion: A metric to distinguish them all and in the latent space bind them
- arxiv url: http://arxiv.org/abs/2511.03068v1
- Date: Tue, 04 Nov 2025 23:29:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-06 18:19:32.272417
- Title: Homomorphism distortion: A metric to distinguish them all and in the latent space bind them
- Title（参考訳）: 準同型歪み:それら全てを区別し、潜在空間においてそれらを束縛する計量
- Authors: Martin Carrasco, Olga Zaghen, Erik Bekkers, Bastian Rieck,
- Abstract要約: この測度を、グラフ準同型歪み(英語版)として表す。
グラフをエンフ完全に特徴付けることができ、したがって、エンフ完全グラフ埋め込みであることを示す。
1.) textttBRECデータセットを最大4$-WLの非識別可能なグラフで完全に区別し、2.) emphoutperforms previous method in homomorphisms under the textttZINC-12
- 参考スコア（独自算出の注目度）: 14.333119698384523
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: For far too long, expressivity of graph neural networks has been measured \emph{only} in terms of combinatorial properties. In this work we stray away from this tradition and provide a principled way to measure similarity between vertex attributed graphs. We denote this measure as the \emph{graph homomorphism distortion}. We show it can \emph{completely characterize} graphs and thus is also a \emph{complete graph embedding}. However, somewhere along the road, we run into the graph canonization problem. To circumvent this obstacle, we devise to efficiently compute this measure via sampling, which in expectation ensures \emph{completeness}. Additionally, we also discovered that we can obtain a metric from this measure. We validate our claims empirically and find that the \emph{graph homomorphism distortion}: (1.) fully distinguishes the \texttt{BREC} dataset with up to $4$-WL non-distinguishable graphs, and (2.) \emph{outperforms} previous methods inspired in homomorphisms under the \texttt{ZINC-12k} dataset. These theoretical results, (and their empirical validation), pave the way for future characterization of graphs, extending the graph theoretic tradition to new frontiers.
- Abstract（参考訳）: 長年にわたり、グラフニューラルネットワークの表現性は、組合せ特性の点から「emph{only}」として測定されてきた。
この研究において、我々はこの伝統から離れ、頂点属性グラフ間の類似性を測定するための原則化された方法を提供する。
この測度を \emph{graph homomorphism distortion} と表現する。
グラフを 'emph{completely characterize} で表すことができ、したがって \emph{complete graph embedding} も表す。
しかし、道のどこかで、私たちはグラフのカノン化問題に遭遇します。
この障害を回避するために、サンプリングによってこの測定を効率的に計算し、予測によって \emph{completeness} が保証される。
また,この測定値から測定値を得ることができた。
1.) は \texttt{ZINC-12k} データセットの下での準同型にインスパイアされた以前の方法と4-WL の非識別可能なグラフと、 (2.) \emph{outperforms} 以前の方法とを完全に区別する。
これらの理論結果(およびその実証的検証)は、グラフの将来の特徴づけの道を開き、グラフ理論の伝統を新たなフロンティアへと拡張する。
関連論文リスト
- Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs [50.99881402425112]
グラフニューラルネットワーク(GNN)は、グラフ構造化データをモデリングするための強力なツールとして登場した。
既存のGNNは、接続ノードが異なる特徴やラベルを持つ傾向がある異種グラフとしばしば苦労する。
我々は、グラフ変換を慎重に設計し、グラフをホモフィリーに拡張する、新しい、未探索のパラダイムを提示する。
論文 参考訳（メタデータ） (2025-09-16T00:10:20Z) - Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。
本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
論文 参考訳（メタデータ） (2025-06-19T08:01:00Z) - Generating Graphs via Spectral Diffusion [48.70458395826864]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。
合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - On the Equivalence of Graph Convolution and Mixup [70.0121263465133]
本稿では,グラフ畳み込みと混合手法の関係について検討する。
2つの穏やかな条件の下では、グラフの畳み込みはMixupの特別な形式と見なすことができる。
グラフ畳み込みネットワーク(GCN)と単純化グラフ畳み込み(SGC)をミックスアップの形で表現できることを証明し、数学的にこの等価性を確立する。
論文 参考訳（メタデータ） (2023-09-29T23:09:54Z) - Finding the Missing-half: Graph Complementary Learning for
Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。
ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。
既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
論文 参考訳（メタデータ） (2023-06-13T08:06:10Z) - Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond [36.5554915218563]
ホモフィリー(英: Homophily)は、類似したノードを接続するエッジの傾向を記述するグラフ特性である。
文学において、ホモフィリーの普遍的に合意された尺度は存在しない。
一般的に使用されるホモフィリー測度は、異なるデータセット間でのホモフィリーレベルの比較を防止するために、重大な欠点があることが示される。
論文 参考訳（メタデータ） (2022-09-13T17:28:25Z) - Node Copying: A Random Graph Model for Effective Graph Sampling [35.957719744856696]
本稿では,グラフ上の分布を構成するノードコピーモデルを提案する。
コピーモデルの有用性を3つのタスクで示す。
提案モデルを用いて,グラフトポロジに対する敵攻撃の効果を緩和する。
論文 参考訳（メタデータ） (2022-08-04T04:04:49Z) - Matching recovery threshold for correlated random graphs [9.12788494573002]
共通 ErdHos-R'enyi グラフ $mathbfG(n, p)$ から独立にサブサンプリングされた2つの相関グラフに対して、これらの2つのグラフのアンフィグアウトラベルの観測からそれらのエンフィラテントマッチングを回復したい。
この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。
論文 参考訳（メタデータ） (2022-05-29T13:04:20Z) - Not too little, not too much: a theoretical analysis of graph
(over)smoothing [8.7314407902481]
我々は,各ノードが隣人の特徴量の平均を順次受信する,エンフェメアンアグリゲーションによるグラフの平滑化を解析する。
グラフの平滑化は、主データよりも高速に非主データ方向を縮小し、回帰に役立ち、同時に崩壊するよりも早くコミュニティ内のノードを縮小することを示す。
論文 参考訳（メタデータ） (2022-05-24T15:39:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。