論文の概要: Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
- arxiv url: http://arxiv.org/abs/2510.05494v1
- Date: Tue, 07 Oct 2025 01:24:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-08 17:57:08.054015
- Title: Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
- Title（参考訳）: 結晶等変グラフニューラルネットワークの基本極限:回路複雑度の観点から
- Authors: Yang Cao, Zhao Song, Jiahao Zhang, Jiale Zhao,
- Abstract要約: グラフネットワーク(GNN)は、ニューラルネットワークを学ぶためのコアパラダイムとなっている。
本研究は,回路複雑度レンズを用いた結晶構造予測のためのEGNNの固有計算および表現限界を特徴付ける。
- 参考スコア（独自算出の注目度）: 15.44186249263113
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph neural networks (GNNs) have become a core paradigm for learning on relational data. In materials science, equivariant GNNs (EGNNs) have emerged as a compelling backbone for crystalline-structure prediction, owing to their ability to respect Euclidean symmetries and periodic boundary conditions. Despite strong empirical performance, their expressive power in periodic, symmetry-constrained settings remains poorly understood. This work characterizes the intrinsic computational and expressive limits of EGNNs for crystalline-structure prediction through a circuit-complexity lens. We analyze the computations carried out by EGNN layers acting on node features, atomic coordinates, and lattice matrices, and prove that, under polynomial precision, embedding width $d=O(n)$ for $n$ nodes, $O(1)$ layers, and $O(1)$-depth, $O(n)$-width MLP instantiations of the message/update/readout maps, these models admit a simulation by a uniform $\mathsf{TC}^0$ threshold-circuit family of polynomial size (with an explicit constant-depth bound). Situating EGNNs within $\mathsf{TC}^0$ provides a concrete ceiling on the decision and prediction problems solvable by such architectures under realistic resource constraints and clarifies which architectural modifications (e.g., increased depth, richer geometric primitives, or wider layers) are required to transcend this regime. The analysis complements Weisfeiler-Lehman style results that do not directly transfer to periodic crystals, and offers a complexity-theoretic foundation for symmetry-aware graph learning on crystalline systems.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、リレーショナルデータを学ぶためのコアパラダイムとなっている。
材料科学において、同変GNN(EGNN)はユークリッド対称性と周期境界条件を尊重する能力のため、結晶構造予測の魅力的なバックボーンとして登場した。
強い経験的性能にもかかわらず、周期的、対称性に制約された設定における表現力はあまり理解されていない。
本研究は,回路複雑度レンズを用いた結晶構造予測のためのEGNNの固有計算および表現限界を特徴付ける。
ノードの特徴, 原子座標, 格子行列に作用するEGNN層によって実行される計算を解析し, 多項式精度で, $d=O(n)$ for $n$ node, $O(1)$ layer, and $O(1)$-depth, $O(n)$-width MLP instantiations of the message/update/readout map, これらのモデルは, 多項式サイズの均一な$\mathsf{TC}^0$しきい値回路ファミリーによるシミュレーション(定値境界付き)を認める。
EGNNを$\mathsf{TC}^0$に設定することは、現実的なリソース制約の下でそのようなアーキテクチャで解決可能な決定と予測の問題に関する具体的な天井を提供し、アーキテクチャの変更(例えば、より深い深さ、よりリッチな幾何学的プリミティブ、より広い層)が、この体制を超越するために要求されるかを明確にする。
この分析は、Weisfeiler-Lehmanスタイルの結果を補完し、周期性結晶に直接転移せず、結晶系の対称性を考慮したグラフ学習のための複雑性理論の基礎を提供する。
関連論文リスト
- Theory of periodic convolutional neural network [2.5288763663662883]
我々は、周期境界条件を畳み込み層に組み込んだ、長周期CNNと呼ばれる新しい畳み込みニューラルネットワークアーキテクチャを導入する。
周期的CNNは、$d-1$の線形変数に依存するリッジ関数を$d$次元の入力空間で近似することができる。
この結果から, 周期的CNNは, 高内在次元の隆起構造が自然に認められる問題に特に適していることが示唆された。
論文 参考訳（メタデータ） (2025-09-23T07:43:02Z) - Learning Identifiable Structures Helps Avoid Bias in DNN-based Supervised Causal Learning [56.22841701016295]
Supervised Causal Learning (SCL)はこの分野で新興パラダイムである。
既存のディープニューラルネットワーク(DNN)ベースの手法では、"Node-Edgeアプローチ"が一般的である。
論文 参考訳（メタデータ） (2025-02-15T19:10:35Z) - The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
連続状態と行動空間を持つ非線形力学系の一般設定におけるオンライン強化学習のサンプル複雑性について検討した。
我々のアルゴリズムは、$mathcalO(N epsilon2 + Mathrmln(m(epsilon)/epsilon2)$のポリシーを後悔する。
力学がコンパクトで実数値のパラメータ集合によってパラメータ化される特別な場合、$mathcalO(sqrt)のポリシー後悔を証明する。
論文 参考訳（メタデータ） (2025-01-27T10:01:28Z) - On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。
本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。
具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
論文 参考訳（メタデータ） (2025-01-11T05:54:10Z) - E(n) Equivariant Topological Neural Networks [10.603892843083173]
グラフニューラルネットワークはペアインタラクションのモデリングに優れていますが、高階インタラクションや機能に柔軟に対応できません。
トポロジカルディープラーニング(TDL)がこの問題に対処するための有望なツールとして最近登場した。
本稿では,E(n)-同変トポロジカルニューラルネットワーク(ETNN)を紹介する。
ETNNは回転、反射、翻訳を尊重しながら幾何学的ノードの特徴を取り入れている。
論文 参考訳（メタデータ） (2024-05-24T10:55:38Z) - An Implicit GNN Solver for Poisson-like problems [2.675158177232256]
$Psi$-GNNは、境界条件の混合でユビキタスなPoisson PDE問題を解決するための新しいグラフニューラルネットワーク(GNN)アプローチである。
Implicit Layer Theoryを活用することで、$Psi$-GNNは"無限の"ディープネットワークをモデル化する。
論文 参考訳（メタデータ） (2023-02-06T10:08:42Z) - Deep Architecture Connectivity Matters for Its Convergence: A
Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。
接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文 参考訳（メタデータ） (2022-05-11T17:43:54Z) - Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach [47.19265172105025]
グラフ構造化データのための新しいハイブリッド量子古典アルゴリズムを提案し、これをEgo-graph based Quantum Graph Neural Network (egoQGNN)と呼ぶ。
egoQGNNはテンソル積とユニティ行列表現を用いてGNN理論フレームワークを実装し、必要なモデルパラメータの数を大幅に削減する。
このアーキテクチャは、現実世界のデータからヒルベルト空間への新しいマッピングに基づいている。
論文 参考訳（メタデータ） (2022-01-13T16:35:45Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。