🤖 AI

TRACE: Learning to Compute on Circuit Graphs

本論文は、計算フローを捉えるための階層型Transformerと、グローバルな予測を分離するための関数シフト学習目的関数を採用することで、多様な回路モダリティにおいて既存のアーキテクチャを大幅に上回る、回路グラフの機能を学習するための新しいパラダイムであるTRACEを導入する。

原著者： Ziyang Zheng, Jiaying Zhu, Jingyi Zhou, Qiang Xu

公開日 2026-06-17

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Ziyang Zheng, Jiaying Zhu, Jingyi Zhou, Qiang Xu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

論文「TRACE: Learning to Compute on Circuit Graphs」の解説：シンプルで日常的な例えを用いた説明

大きな問題：「目隠し」をされた計算機

あなたが、複雑な機械（デジタル回路のようなもの）がどのように機能するかをコンピュータに教えようとしている場面を想像してください。この機械は、多くの小さな部品（ゲート）が繋がり、情報を次へと受け渡していくことで成り立っています。

長い間、コンピュータにこれを教えるための最善の方法は、MPNN（メッセージ・パッシング・ニューラル・ネットワーク）と呼ばれる手法でした。しかし、この論文は、この特定の作業においてMPNNという手法は根本的に壊れていると主張しています。

例え：目隠しをされたシェフ
回路を、シェフ（演算子、例えばMUXや論理ゲート）によって材料（入力）が混ぜ合わされる「レシピ」だと考えてみましょう。

従来の方法 (MPNNs): シェフが目隠しをされている状態を想像してください。彼らは材料を一つずつ嗅ぎ分けることはできますが、その「順番」は見ることができません。もし「塩」の次に「コショウ」を渡されたとしても、彼らは「コショウ」の次に「塩」を渡された場合と同じように扱ってしまいます。しかし、回路においては順番が重要です！スイッチ（MUX）は、どのワイヤが制御信号で、どのワイヤがデータであるかによって、全く異なる挙動を示します。従来の方法は、材料を特定のシーケンス（順序）としてではなく、単なる「バラバラの塊」として扱ってしまうため、混乱してしまうのです。
もう一つの従来の方法 (Transformers): テーブルの上に全ての材料が並んでいるのを一度に見ることはできるものの、レシピの「手順」を理解していないシェフを想像してください。彼らは「ステップ2はステップ1の結果に依存する」という事実を見落としてしまいます。彼らは調理プロセスに従うことなく、最終的な料理を予測しようとしてしまうのです。

解決策： TRACE

著者らは、TRACEと呼ばれる新しいシステムを作り上げました。これは、「キッチンのレイアウト（アーキテクチャ）」と「教え方（学習目的）」という2つの主要な要素を変更することで問題を解決しています。

1. 新しいキッチンのレイアウト：「ステップ・バイ・ステップ」のシェフ

従来の「目隠しのシェフ」や「混乱したシェフ」の代わりに、TRACEは**階層型トランスフォーマー（Hierarchical Transformer）**を使用します。

仕組み: 回路を、特定の順序で書かれた文章（例：Add(Multiply(A, B), C) のような数式）のように扱います。
例え: 今やシェフの手元には、明確な指示カードがあります。彼らは単に材料を見るだけでなく、それらが「どのような順序で」渡されたかを見ます。
- まず、「演算子」（「混ぜる」などの動作）を確認します。
- 次に、「入力1」（最初の材料）を確認します。
- そして、「入力2」（二番目の材料）を確認します。
なぜ役立つのか: シェフは順番を把握しているため、どのように混ぜればよいかを正確に理解できます。もしレシピに「コショウの中に塩を混ぜる」とあれば、彼らは「塩の中にコショウを混ぜる」場合とは異なる処理を行います。これにより、コンピュータは回路の正確なロジック（誰が誰に依存しているかという階層構造と、各ワイヤの位置関係）を理解できるようになります。

2. 新しい教え方：「ファンクション・シフト学習（Function Shift Learning）」

優れたシェフであっても、巨大で複雑な料理の「最終的な味」を予測するのは困難です。材料が以前のステップで何度も使われている場合（回路における「再収束（reconvergence）」と呼ばれる現象）、材料同士が予期せぬ形で相互作用することがあるからです。

問題点: もしシェフに「最終的な味はどうなりますか？」と尋ねると、彼らはその複雑さに圧倒されてしまうかもしれません。
TRACEによる解決策: 著者らは、シェフに「最初から全体の味を予測させる」のではなく、単純な予想と正解との間の**「差（シフト）」**を予測するように教えます。
- ステップA（単純な予想）: 全ての材料が独立していると仮定して、素早く予想を出します（例：「塩50%、コショウ50%なら、味は50/50だ」）。これは簡単で高速です。
- ステップB（正解）: 塩とコショウが以前の工程ですでに相互作用している可能性があるため、実際の答えはより複雑になります。
- 課題: モデルは、単純な予想と正解との間の**「ギャップ（シフト）」**を見つけ出すように訓練されます。
例え: これは、数学のテストを受けている学生のようなものです。「ゼロから巨大で恐ろしい方程式を解きなさい」と教える代わりに、「これが簡単な答えです。では、正解に辿り着くために、この答えをどれくらい『調整』すればよいかだけを教えてください」と教えるのです。これにより、学習は格段に容易になり、精度も向上します。

結果：明確な勝利

著者らは、3種類の異なる回路言語（RTL、AIGs、Netlists）を用いてTRACEをテストし、これまでの最高の手法と比較しました。

結果: TRACEはあらゆる場面で勝利しました。以下の点で非常に優れていました：
1. 双子の特定: 見た目が違っても、全く同じ動作をする2つの回路を識別すること。
2. 挙動の予測: 異なる条件下で回路がどのように振る舞うかを正確に予測すること。
なぜ重要なのか: この論文は、古い手法の「盲目さ」を修正し、学習タスクを簡略化することで、電子回路を理解するためのよりスマートなツールを構築できることを示しています。

まとめ

TRACEは、コンピュータが回路の仕組みを学ぶための新しい方法です。

回路の入力をバラバラの塊として扱うのではなく、順序のあるシーケンス（文章のようなもの）として扱うことで、ロジックの流れを理解します。
複雑な答えを一度に予測しようとするのではなく、単純な予想と真実との間の小さな差を予測することを学びます。

この組み合わせにより、TRACEは電子回路の「機能的挙動」を理解するための、現時点で最も正確なツールとなっています。

技術要約: TRACE: 回路グラフ上での計算学習

1. 問題定義

本研究が取り組む根本的な課題は、「計算の学習（learning to compute）」、すなわち回路グラフの機能的振る舞いを正確にモデル化する能力です。回路グラフ（RTLグラフ、AIG、およびポストマッピング・ネットリストを含む）は、演算と変数を表す有向ノードを通じて、計算の流れを捉えています。

著者らは、グラフ表現学習における支配的なパラダイムであるメッセージパッシングニューラルネットワーク（MPNN）とグラフトランスフォーマーは、この特定のタスクに対してアーキテクチャ上の不一致があると考えています。その理由は、以下の3つの決定的な欠陥によるものです。

MPNNは入力間の相互作用をモデル化できない: MPNNは、近傍からのメッセージを独立して結合する置換不変な集約関数（sumやmeanなど）に依存しています。これにより、位置を考慮した演算器固有の相互作用を捉えることができません。例えば、 $MUX(S, A, B) \neq MUX(A, S, B)$ であるマルチプレクサ（MUX）において、集約の過程で入力の順序が失われるため、正しくモデル化することができません。
バニラなTransformerは階層性を無視する: 標準的なTransformerはグラフをシーケンスへと平坦化するため、ステップバイステップの計算に必要な明示的な階層構造と中間依存関係（例： $f(g(a,b), c)$ が中間結果 $g(a,b)$ に依存していること）を破壊してしまいます。
エッジマスク付きTransformerはMPNNの限界を継承する: グラフのトポロジーを尊重するためにアテンションマスクを使用するTransformerは、重み付き和（グラフアテンションネットワークと同様）に帰着してしまうことが多く、複数の入力間の精密かつ非線形な相互作用をモデル化できないという問題を継承します。

さらに、複雑なトポロジーから生じるグローバル関数、特に**再収束依存性（reconvergent dependencies）**を捉えるという、より深い課題が存在します。回路において、あるノードのグローバル関数は、入力の独立性を仮定した単純なローカル近似とは大きく異なる場合があります。グローバル関数を直接教師あり学習する従来の手法は、これらの複雑なコンテキスト効果を埋め込みの中に一括して詰め込んでしまうため、モデルが真の機能的依存性と偽の相関を区別することを困難にしています。

2. 手法

著者らは、TRACE（Algebraic and Computational Expressionsに関する推論のためのTransformer）という、アーキテクチャ的に健全なバックボーンと原理に基づいた学習目的からなる新しいパラダイムを提案しています。

2.1 階層型Transformerバックボーン

従来のモデルのアーキテクチャ上の欠陥を解決するために、TRACEは計算のステップバイステップの流れを反映した階層型Transformerを採用しています。

ロジックレベルの計算: ノードは、トポロジカルなロジック深度に基づいてレベルごとに処理されます。一次入力（PI）はレベル0です。
接頭辞表記（Prefix Notation）による表現: 接頭辞表記に着想を得て、特定のロジックレベルにおける各計算ステップは、順序付けられたシーケンス [演算子, 入力_1, 入力_2, ...] として表現されます。
位置認識エンコーディング: Transformerエンコーダは、これらのシーケンスを位置エンコーディングと共に処理します。これにより、モデルは演算器固有の相互作用と位置認識（例：MUXにおける制御信号とデータ入力の区別）を捉えることができます。
再帰的処理: 演算子ノードの埋め込みは、そのシーケンスの最初のトークンのTransformer出力に基づいて更新されます。この更新された埋め込みは、次のロジックレベルにおける後続の演算子の入力として機能します。
効率性: ロングテールな次数分布を持つ一般的なグラフとは異なり、回路グラフは次数が小さく限定されているため、Transformerに伴う二次的なメモリオーバーヘッドが発生しません。

2.2 関数シフト学習（FSL）

複雑なグローバル関数を直接予測することの難しさに対応するため、TRACEは学習問題を分離する新しい目的関数である**関数シフト学習（Function Shift Learning）**を導入しています。

グローバル関数 ( $y_{global}$ ): すべての依存関係（再収束を含む）を考慮した、ノードがロジック1である真の確率。これを直接計算することは高コストです（ $O(2^k)$ ）。
ローカル関数 ( $y_{local}$ ): 入力の独立性を仮定した単純な近似。計算効率は高い（ $O(1)$ ）ですが、再収束が存在する場合の真の振る舞いを捉えることができません。
関数シフト ( $y_{FSL}$ ): モデルは、グローバル関数とローカル関数の差分のみを予測するように訓練されます。
$y_{FSL} = y_{global} - y_{local}$
訓練: モデルはL1損失を用いて関数シフトを回帰するように訓練されます。グラウンドトゥルースのシフトは、訓練データから事前計算されます。
推論: 推論時には、グローバル関数は反復的に再構成されます。各ノードについて、モデルはシフトを予測し、それをローカル関数（前駆体の推定されたグローバル関数を用いて計算される）に加算することで、最終的なグローバル推定値を得ます。

3. 主な貢献

アーキテクチャの整合性: 置換不変な集約に代わり、位置認識およびシーケンスベースの処理を用いることで、回路グラフの計算フローを忠実に反映する階層型Transformerを導入しました。
分離された学習目的: 再収束による複雑なコンテキスト効果（「シフト」）を単純なローカル近似から分離する関数シフト学習を提案し、学習タスクを簡素化しました。
最先端の性能: この組み合わせたパラダイムが、多様な回路モダリティにおいて既存のMPNNおよびグラフトランスフォーマーを大幅に上回ることを実証しました。

4. 実験結果

著者らは、3つの回路モダリティ（RTL、AIG、PMネットリスト）について、2種類のタスク（対照学習および予測タスク）でTRACEを評価しました。

4.1 対照学習タスク

検索タスク（機能的に等価な回路の特定）において、TRACEは一貫してすべてのベースラインを上回りました。

RTL: Recall@1で94.45%を達成（次点の約88%に対し）。
AIG: Recall@1で92.68%を達成（次点の約88%に対し）。
PMネットリスト: Recall@1で90.81%を達成（次点の約86%に対し）。
特筆すべきは、多くのグラフトランスフォーマーのベースライン（GraphGPS、SGFormerなど）が、AIGやPMネットリストにおいて深刻な性能低下やメモリ不足（OOM）エラーに陥ったのに対し、TRACEは安定していたことです。

4.2 予測タスク

ノードレベルの特性（ロジック1の確率、類似度、遷移確率）を予測するタスクにおいて、TRACEは最小の平均絶対誤差（MAE）と最高の $R^2$ スコアを達成しました。

組合せAIG: ロジック1の確率においてMAE 0.015（DeepGate4の0.027に対し）。
シーケンシャルAIG: ロジック1の確率でMAE 0.009、遷移確率で0.005。
PMネットリスト: ロジック1の確率においてMAE 0.013（GraphSAGEの0.048に対し）。

4.3 アブレーションと分析

関数シフト学習: FSLを除去すると性能が著しく低下しました。例えば、PMネットリストの確率予測において、FSLを除去するとMAEが0.013から0.036へと増加しました（相対誤差で63.9%増加）。
誤差の蓄積: ロジックレベル間の分析により、TRACEは深いロジックレベルにおいても安定した性能を維持していることが示され、反復的な推論プロセスにおける誤差蓄積に対する堅牢性が示されました。

5. 意義

本論文は、TRACEが回路解析における**新たな最先端（State of the Art）**を確立したと主張しています。さらに広く言えば、回路グラフ上での学習において、モデルの誘導バイアスを問題の構造に適合させることが、機能的振る舞いを捉える上で極めて重要であることを示しています。TRACEは、ローカル近似をコンテキスト的なグローバルシフトから分離することが、多様な電子設計自動化（EDA）ドメインにわたる優れた汎化につながるという、原理的な証明となっています。