論文の概要: Efficient NPN Classification for Large Functions using Graph Neural Network

• arxiv url: http://arxiv.org/abs/2611.00339v1
• Date: Fri, 30 Oct 2026 20:13:30 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:43:17.158004
• Title: Efficient NPN Classification for Large Functions using Graph Neural Network
• Title（参考訳）: グラフニューラルネットワークを用いた大規模関数の効率的なNPN分類
• Abstract要約: 効率的なNPN分類は論理合成、量子コンピューティング、情報理論などの分野において有用である。 本稿では,NPN行動予測として再キャストすることで,NPN分類のための学習に基づく最初の定式化を提案する。
• 参考スコア（独自算出の注目度）: 9.396710924455531
• License:
• Abstract: Two Boolean functions are considered NPN equivalent if one can be transformed into the other by negating inputs, permuting inputs, or negating the output. Efficient NPN classification is valuable in fields such as logic synthesis, quantum computing, and information theory. However, exact NPN classification demands exhaustive enumeration of all possible input permutations and negations. Its complexity grows exponentially, making it impractical for larger functions with more inputs. In this paper, we introduce the first learning-based formulation for NPN classification by recasting it as NPN action prediction. Our method represents Boolean functions as AND-Inverter Graphs (AIGs) and applies a bidirectional heterogeneous graph neural network to predict input negations, output negation, and input permutations. To mitigate the non-canonicity of logic networks, we further introduce graph rewriting techniques that reduce structural ambiguity and recover useful symmetries before prediction. Experimental results show that NPN action prediction is learnable, that the resulting canonicalization quality improves over heuristic baselines, and that on practical benchmarks our method approaches exact methods on tractable cases while scaling to functions with up to 16 inputs.
• Abstract（参考訳）: 2つのブール関数がNPN同値であるとは、入力を否定したり、入力を置換したり、出力を否定したりすることで、一方を他方に変換することができることをいう。 効率的なNPN分類は論理合成、量子コンピューティング、情報理論などの分野において有用である。 しかし、正確なNPN分類は、全ての可能な入力置換と否定の徹底的な列挙を要求する。 その複雑さは指数関数的に増大し、より多くの入力を持つより大きな関数に対しては実用的でない。 本稿では,NPN行動予測として再キャストすることで,NPN分類のための学習に基づく最初の定式化を提案する。 本手法は, ブール関数をAND-Inverter Graphs (AIGs) として表現し, 入力否定, 出力否定, 入力置換の予測に双方向不均一グラフニューラルネットワークを適用した。 論理ネットワークの非正準性を緩和するために、構造的曖昧さを低減し、予測の前に有用な対称性を回復するグラフ書き換え手法を導入する。 実験の結果,NPNの動作予測は学習可能であり,結果の正準化品質はヒューリスティックなベースラインよりも向上し,実際のベンチマークでは,最大16個の入力を持つ関数にスケールしながら,抽出可能なケースの正確な手法にアプローチすることが示唆された。

関連論文リスト

• Fast Exact NPN Classification with Influence-aided Canonical Form [4.210634768624388]
  ブール関数解析の基本的な概念であるNPN分類にブール効果を導入する。 インフルエンサーは入力ネゲーション非依存であり、入力パーミューテーション依存であり、以前のシグネチャとは別の構造情報を持っていることを示す。 ABCで実装された最先端のアルゴリズムと比較すると,NPN分類の精度は5.5倍に向上する。
  論文  参考訳（メタデータ） (2023-08-23T01:50:09Z)
• Classification with Deep Neural Networks and Logistic Loss [25.56187933090708]
  このロジスティック損失で訓練されたディープニューラルネットワーク(DNN)は、バイナリ分類タスクにおいて目覚ましい進歩を遂げた。 本稿では,新規でエレガントなオラクル型不等式を確立し,対象関数の有界性制限に対処する。 完全に連結されたReLU DNN分類器に対して,ロジスティック損失を訓練したシャープ収束率を導出する。
  論文  参考訳（メタデータ） (2023-07-31T15:58:46Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• Neural Greedy Pursuit for Feature Selection [72.4121881681861]
  我々は,非線形予測問題に対する$P$入力機能のうち,$N$重要な特徴を選択するための欲求アルゴリズムを提案する。 ニューラルネットワークをアルゴリズムの予測子として使用し、損失を計算します。
  論文  参考訳（メタデータ） (2022-07-19T16:39:16Z)
• Learning First-Order Rules with Differentiable Logic Program Semantics [12.360002779872373]
  微分型一階規則学習者(DFOL)と呼ばれる微分型帰納的論理プログラミングモデルを導入する。 DFOLは、LPの解釈可能な行列表現を探索することにより、関係事実から正しいLPを見つける。 実験結果から,DFOLは精度が高く,堅牢で,スケーラブルで,安価で微分可能なICPモデルであることが示唆された。
  論文  参考訳（メタデータ） (2022-04-28T15:33:43Z)
• Learning Frequency Domain Approximation for Binary Neural Networks [68.79904499480025]
  フーリエ周波数領域における符号関数の勾配を正弦関数の組み合わせを用いて推定し,BNNの訓練を行う。 いくつかのベンチマークデータセットとニューラルネットワークの実験により、この手法で学習したバイナリネットワークが最先端の精度を達成することが示されている。
  論文  参考訳（メタデータ） (2021-03-01T08:25:26Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• A Neural Network Approach for Online Nonlinear Neyman-Pearson Classification [3.6144103736375857]
  論文の中では,オンラインと非線形の両方で初となる新しいNeyman-Pearson(NP)分類器を提案する。 提案する分類器は、オンライン方式でバイナリラベル付きデータストリーム上で動作し、ユーザが指定し、制御可能な偽陽性率の検出能力を最大化する。 提案アルゴリズムは大規模データアプリケーションに適しており,実時間処理による偽陽性率制御性を実現している。
  論文  参考訳（メタデータ） (2020-06-14T20:00:25Z)

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

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