アーカイブ / AI Agent
合成で形が変わった回路から、同じ論理機能を探す部分回路照合
Functional Subgraph Matching
Functional Subgraph Matchingの原論文から掲載した図です。細部はクリックして拡大できます。
原論文の図の説明を読む
Figure 3: The pipeline of Stage #2. Left : Our data processing pipeline. For a given 𝒢 p m \mathcal{G}_{pm} , we replace each node in 𝒢 p m \mathcal{G}_{pm} with the AIG implementation according to the functionality in the library. Then, we randomly sample a subgraph 𝒢 s u b \mathcal{G}_{sub} from 𝒢 a i g \mathcal{G}_{aig} . Finally, we annotate the nodes in 𝒢 p m \mathcal{G}_{pm} if one of the corresponding AIG nodes still exist in 𝒢 s u b \mathcal{G}_{sub} . Right : Our training pipeline for fuzzy boundary identification via graph segmentation. Given the query graph 𝒢 s u b \mathcal{G}_{sub} and the target graph 𝒢 p m \mathcal{G}_{pm} , we first use E n c a i g Enc_{aig} to obtain the graph embedding of 𝒢 s u b \mathcal{G}_{sub} and E n c p m Enc_{pm} to obtain the node embeddings of 𝒢 p m \mathcal{G}_{pm} . These embeddings are then concatenated and passed to a task head to determine whether a node in 𝒢 p m \mathcal{G}_{pm} lies within the fuzzy boundary of 𝒢 s u b \mathcal{G}_{sub} .
概要
- 対象回路と機能が等しい別表現に小回路が現れる場合まで、機能の含有を判定する。
- AIGとマッピング後ネットリストを数値表現で照合し、該当領域のノードも推定する。
- 著者らは3データセット平均の正解率を、合成後94.5%、マッピング後93.1%と報告した。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、Functional Subgraph Matchingの仕組み
- 01AIGの小回路と対象回路
- 02回路を数値表現に変換
- 03機能の含有を判定
- 04各ノードの領域を推定
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
論理回路から特定の小回路を探す作業は、算術回路の検証や設計の最適化に使われる。電子設計自動化（EDA）は、こうした設計作業を計算機で支える技術である。従来の照合は、回路をノードと接続で表したときの形を主に比べる。
論理合成や技術マッピングでは、回路の働きを保ったまま素子や接続が変わる。そのため、設計の前段階で定義した小回路を後段階の回路から探す際、形の一致だけでは機能上の関係を見落とし得る。
手法
入力は問い合わせ用の小回路と探索先の回路である。AIGはAND演算と反転で論理を表すグラフ、ネットリストは素子と接続の記述を指す。著者らはAIGと技術マッピング後のネットリストに別々の符号化器を使い、回路を数値表現へ変換する。同じ機能を持つ合成前後の回路の表現を近づけ、小回路の機能が対象に含まれるかを判定する。
次に、問い合わせ回路の表現と対象回路の各ノードの表現を組み合わせ、該当領域に属するノードを推定する。例えば小さな加算機能を組み替え後の回路から探す場合、有無の判定に加え、確認対象となるノード群を出す。この領域は、問い合わせ機能を含む最小の領域として定義される。
新規性
著者らは、対象回路と同じ機能を持つ別の回路に問い合わせ回路が部分として現れる関係を「機能的部分回路」と定義した。対象回路そのものに同じ形や機能の部分が見えなくても、含有関係を扱える。
さらに、機能の有無を判定した後、該当領域をノードごとに推定する。領域の判定には入出力ノードだけでなく、内部ノードの情報も使う。
従来手法との違い
構造照合は、問い合わせ回路と対象回路のノードや接続の一致を探す。機能等価な部分回路の照合も、対象内に対応する部分が存在する場合を扱う。論理合成で回路全体が組み替わると、どちらも機能の含有を捉えにくい。
本手法は、対象と同じ機能を持つ別表現まで考えて含有を判定する。実験では構造照合のNeuroMatch、HGCNと比較し、境界検出向けのGamora、ABGNNはNeuroMatchの枠組みに組み込んで比較した。
実験結果
著者らはITC99、OpenABCD、ForgeEDAのAIG回路を使い、小回路から合成後または技術マッピング後の回路を探す課題を評価した。ABCの複数の合成フローを使い、構造が変わった回路を対象にした。表の値は独立した3回の実行の平均と標準偏差である。
著者らの報告では、3データセット平均の正解率は合成後の照合で94.5%、マッピング後で93.1%。ITC99のマッピング後は本手法が93.1±0.3%、NeuroMatchが49.8±0.2%だった。要旨の93.8%は両課題をまとめた値と読めるが、集計方法は明記されていない。境界推定のDice値は要旨で91.3%と報告される。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：乗算回路の検証で、半加算器に相当する小さな論理機能が技術マッピング後の回路に含まれるかを調べる。入力はAIG形式の問い合わせ回路と、対象のマッピング後ネットリスト。出力は有無の予測と、担当者が確認するノード群とする。
適用には、合成前後で対応する回路、含有の正解ラベル、領域のノードラベル、セルの機能情報が必要になる。追加センサーは使わず、自社の合成手順とセル表現に合わせて学習データを作り、モデルを適応させる。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：自社回路からAIGの小回路と合成・マッピング後の対象回路を集め、機能を含む組と含まない組に正解ラベルを付ける。領域評価には、セルの機能情報を使ってAIGとの対応を取り、対象ノードのラベルを作る。必要なのは回路データとセル情報で、追加センサーは使わない。
学習用と評価用の回路を分け、自社の合成手順とセル表現に合わせてモデルを適応させる。同じ評価組でNeuroMatchを基準に、有無の正解率、誤検出、見逃し、領域のDice値を測る。予測されたノード群が検証作業に使えるかも個別に確認する。
限界と課題
著者らの実験は複数入力・単一出力の回路を対象とし、ノードや辺を除いても機能が保たれる回路は想定していない。境界のDice値は要旨で報告されているが、確認できた本文の範囲では境界評価の条件別結果を確認できない。
編集上の検証事項は、実設計で正解領域をどう定めるか、未学習の合成手順やセル群でも予測が保たれるか、誤検出と見逃しを担当者が許容できるかである。平均値だけで個々の回路の取り逃しは判断できない。
出典
元のタイトル・要旨を確認する（英語）
Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism
Subgraph matching in logic circuits is foundational for numerous Electronic Design Automation (EDA) applications, including datapath optimization, arithmetic verification, and hardware trojan detection. However, existing techniques rely primarily on structural graph isomorphism and thus fail to identify function-related subgraphs when synthesis transformations substantially alter circuit topology. To overcome this critical limitation, we introduce the concept of functional subgraph matching, a novel approach that identifies whether a given logic function is implicitly present within a larger circuit, irrespective of structural variations induced by synthesis or technology mapping. Specifically, we propose a two-stage multi-modal framework: (1) learning robust functional embeddings across AIG and post-mapping netlists for functional subgraph detection, and (2) identifying fuzzy boundaries using a graph segmentation approach. Evaluations on standard benchmarks (ITC99, OpenABCD, ForgeEDA) demonstrate significant performance improvements over existing structural methods, with average $93.8\%$ accuracy in functional subgraph detection and a dice score of $91.3\%$ in fuzzy boundary identification. The source code and implementation details can be found at https://github.com/zyzheng17/Functional_Subgraph_Matching-Neurips25.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01