Nautyアルゴリズムの概要と実装例

Nautyアルゴリズムの概要

Nauty（No AUTomorphisms, Yes?）は、グラフ同型性（Graph Isomorphism）判定およびグラフのカノニカルラベリング（Canonical Labeling）を高速に行うためのアルゴリズムとなる。

Nautyは、グラフの構造的性質を解析するための高性能なアルゴリズムライブラリであり、以下の3つの主要機能を提供している。

1. グラフ同型性判定: Nautyは、2つのグラフが構造的に同一（同型：isomorphic）であるかどうかを高速に判定する。これにより、異なる表記でも同じ構造を持つグラフを正確に識別することが可能となる。

2. カノニカルラベリング: 任意のグラフを一意な「正準形（canonical form）」に変換する。これは、グラフを統一的に比較・保存する上で非常に有用で、例えばデータベース内の重複検出や構造の分類に活用される。

3. 自動同型群の計算: グラフの節点の間で許されるすべての置換（対称性）を列挙し、自動同型群（automorphism group）として計算する。これは、グラフの対称性解析や数理化学・組合せ最適化などの応用に重要なアプローチとなる。

このように、Nautyはグラフ構造の識別、正規化、対称性分析を効率的に実行するための強力なツールとなっている。

以下にNautyアルゴリズムの基本的な流れを示す。

1. 分割の精緻化（Partition Refinement）: まず、グラフのノードを構造的な特徴（次数や隣接関係など）に基づいてグループ化し、これを「セル」と呼ばれる部分集合に分ける。アルゴリズムはこの分割を繰り返し細かく精緻化していき、ノードの区別性を高めていく。
2. 探索木の構築（Search Tree）: 精緻化された分割に基づいて、異なるラベル付けの可能性を列挙する探索木を構築する。各ノードは特定のラベル付けの状態を表し、深さ優先的に探索が進む。
3. 枝刈り（Pruning）: 探索中、すでに訪れた構造と同型の構造が現れた場合は、それ以上の探索を打ち切る（枝刈り）。これにより、計算量を大幅に削減し、冗長な処理を回避する。
4. カノニカルフォームへの変換: 最終的に、すべてのラベル付けの中から「もっとも小さい順序（通常は辞書順）」のラベル付けを選び、それを正準形（canonical form）として出力する。これにより、グラフの比較や格納を一意に行えるようになる。

この一連の処理により、Nautyは大規模かつ複雑なグラフに対しても、高速かつ正確に同型性や正準形を判定できるようになる。

Nautyのアルゴリズムは、理論的には最悪ケースで指数時間を要するとされている。これは、グラフ同型性判定という問題自体が、現在のところNP に属するが NP完全とも Pとも判明していない困難な問題（Graph Isomorphism Problem）であるためである。

しかし、実用上は非常に高効率に動作し、特に、ノードの構造的特徴や対称性を巧みに活用した分割精緻化や枝刈り手法により、典型的なグラフ構造に対しては処理時間が大幅に短縮される。

その結果として、Nautyは現実的な計算環境でも数千〜数万ノード規模のグラフに対して同型性判定を高速に実行することが可能で、特に小〜中規模のグラフでは、ほぼ線形〜多項式時間のような実行速度を示すことも多く、実務や研究でも広く利用されている。

Nautyは、グラフ構造の同一性や対称性を高精度かつ高速に判定できるツールとして、以下のようなタスクに特に適している。

1. 多数のグラフの同型性フィルタリング: データベース内の大量のグラフ構造から、同型なものを除外しユニークな構造だけを抽出したい場合に最適。カノニカルラベリングを通じて、同型グラフを同一表現に変換し、高速な重複排除が可能となる。

2. 構造分類・生成タスク: 例えば「すべての非同型なnノードグラフを列挙」といった、構造的に異なるグラフだけを網羅的に収集するタスクにも強力。Nautyは、こうした列挙処理においても、正準形による識別を通じて重複を防ぎながら効率的に探索を行う。

3. グラフを一意なIDで識別したい場合: Nautyは、任意のグラフに対して正準形（canonical form）を与えることができるため、その形式を用いて一意な識別子（ID）を生成できます。これにより、構造ベースの検索やデータ管理において、冗長性のない識別が可能となる。

このように、Nautyは構造重視のグラフ処理タスク全般において、他の手法よりも強力なパフォーマンスと正確性を発揮し、特に、同型性の厳密な扱いが重要となる科学技術・化学情報・グラフデータベース分野などで活躍している。

関連するアルゴリズム

Nautyアルゴリズム（グラフの同型性・カノニカルラベリング判定）に関連するアルゴリズムは以下のように分類される。

1. グラフ同型性判定アルゴリズム（Graph Isomorphism）

グラフ同型性判定は、2つのグラフが構造的に同一かどうかを判断する問題であり、理論・実装ともに奥深い分野となる。以下に代表的なアルゴリズムについて述べる。

2. カノニカルラベリングアルゴリズム（Canonical Labeling）

カノニカルラベリングは、任意のグラフに対して一意な構造表現（正準形）を与える手法であり、重複除去や構造識別に不可欠なものとなる。以下は主要なアルゴリズムの比較となる。

4. 特定分野での応用的アルゴリズム

グラフ同型性や類似性判定は、多様な分野で目的に特化した手法として応用されている。以下はその代表例となる。

5. アルゴリズム選択ガイド（用途別）

グラフ解析では、タスクの目的に応じて最適なアルゴリズムを選ぶことが重要となる。以下に代表的な用途別の推奨手法を示す。

応用実装例

以下に、Nautyアルゴリズムの応用実装例を示す。グラフ同型性の判定とカノニカルラベリングによるグラフの一意化を行う実践例となっている。Nauty本体はC言語で実装されているが、Pythonから使うには以下の2通りの方法がある。

方法1：SageMath（Python環境）でNautyを使う

SageMath は Nauty を内部に組み込んでおり、Pythonライクな記法でグラフ同型性やカノニカルラベリングを実行できる。

1. グラフ同型性判定の例

# SageMath環境（または Jupyter + SageMath Kernel）

G1 = Graph([(1, 2), (2, 3), (3, 1)])  # 三角形
G2 = Graph([(4, 5), (5, 6), (6, 4)])  # ラベル違いだが構造同じ

# 同型性判定（内部でNautyを使用）
print("同型ですか？", G1.is_isomorphic(G2))  # True

2. カノニカルラベリングを使ったグラフの一意表現

G = Graph([(3, 1), (1, 2), (2, 3)])
canon = G.canonical_label()
canon.show() # 構造が同じでもラベル順が統一される

方法2：nauty本体 + コマンドラインツール（labelg, dreadnaut）

以下の手順で使用する。

1. グラフ記述（graph6形式）

ファイル graph1.g6 に graph6 形式で保存：

DQK （← graph6での三角形の符号化）

2. コマンドラインで正準ラベル生成

labelg graph1.g6 -o > canon1.g6

• labelg：Nautyツールで正準ラベルを計算

• -o：出力を標準出力へ送信

3. 同型性チェック（複数グラフの比較）

shortg graphA.g6 graphB.g6

• 同型なグラフは重複を除いて1つだけ出力される（つまり同型性フィルタ）

応用シナリオ例

応用例：非同型グラフの生成と分類（CLI）

geng 4 -c | shortg > unique_graphs.g6

• geng 4 -c：4頂点の連結なグラフをすべて生成

• shortg：同型グラフを1つにまとめる（Nautyが中核処理）

関連ツールまとめ

補足：Python × Nauty（高度な連携）

• SageMath や pygraphblas, igraph, Graphillion などと連携すると、Pythonベースでも高速な正準判定が可能である。

具体的な適用事例

Nautyアルゴリズムは、以下のような実際の分野で応用されている。

1. 化学構造解析（分子グラフの同型性）

概要：

• • 分子をグラフ（原子＝ノード、結合＝エッジ）として表現。

  • 構造式が異なっても同じ化合物であるか（構造同型性）を判定する。

Nautyの役割：

• • 分子グラフにカノニカルラベリングを付与し、構造が同じものを一意に識別。

  • 異性体・異名同物の判別や、化合物データベースの重複除去に利用。

事例：

• • ChEMBL, PubChem, ChemSpider などのデータベースの前処理・正規化処理

  • InChI や Canonical SMILES の生成に類似ロジックが使われる（注：InChI自体はnautyではない）

2. グラフ理論・数学研究（同型なグラフの分類）

概要：

• • n頂点の非同型グラフの数を数える、分類する、可視化する。

  • 教育・研究・論文で頻繁に用いられる。

Nautyの役割：

• • geng と shortg を使い、すべての非同型なグラフを網羅的に生成。

  • グラフ列挙・分類・可視化の前処理。

事例：

• • 「n ≤ 10 の全非同型グラフの図鑑」を作成する学術論文や教材

  • Ramsey理論、彩色問題などの構造列挙

3. SAT/SMT モデル検査・定理証明支援（対称性削減）

概要：

• • モデル検査において、状態空間に存在する「構造的に同型な状態」を排除して計算量を削減。

Nautyの役割：

• • モデル状態をグラフとして表現し、状態の対称性（同型性）を検出・縮約。

  • 状態空間爆発の回避に貢献。

事例：

• • NuSMV, Cadence SMV, Symmetry-Aware SAT Solver での事前処理

  • nauty や saucy を統合して自動同型群を抽出

4. データベースインデックス・重複除去

概要：

• • グラフ構造データベース（例：知識グラフ、ソーシャルグラフ）の中で、構造的に同じエンティティを1つにまとめたい。

Nautyの役割：

• • グラフに正準ラベルを付けることで、一意なID（ハッシュ）化が可能。

  • 再利用可能なグラフデータの高速照合が可能になる。

事例：

• • Neo4j に登録するエンティティ構造の事前整形

  • RDF グラフの構造正規化処理

  • 研究用の構造グラフを比較可能な形式で保存

5. 機械学習・GNN前処理

概要：

• • グラフニューラルネットワーク（GNN）などにおいて、同型性のある構造を別のクラスと誤認しないようにする必要がある。

Nautyの役割：

• • 同型グラフに一貫した入力順序やノードIDを与えることで、学習の安定性が向上。

  • グラフ分類タスクで同型グラフを重複として排除。

事例：

• • TUDataset や OGB (Open Graph Benchmark) における前処理

  • 論文「Graph Isomorphism Networks」などでの実験

参考文献

1. 原典・開発者論文

• McKay, Brendan D. (1981)
  Practical Graph Isomorphism – Nautyの初出論文

• McKay, B. D., & Piperno, A. (2014)
  Practical Graph Isomorphism II – Tracesアルゴリズムを提案

2. 標準的教科書・理論書

• Handbook of Graph Theory
  著者：Jonathan Gross, Jay Yellen（CRC Press）
  → Nautyの理論背景やカノニカルラベリング手法を紹介

• Graph Theory with Applications
  著者：J. A. Bondy and U. S. R. Murty
  → 同型性の基礎理論を網羅

3. 実装・ドキュメントリソース

• Nauty/Traces 公式サイト（Brendan McKay）
  🔗 https://users.cecs.anu.edu.au/~bdm/nauty/
  含まれるツール：

  • geng：非同型グラフの列挙

  • shortg：同型グラフの圧縮・除去

  • labelg：カノニカルラベリング

  • dreadnaut：対話型操作シェル

  • Traces：属性付きグラフ対応強化版

• SageMath ドキュメント（内部でNautyを利用）
  🔗 Sage Graphs API
  → is_isomorphic(), canonical_label() でNautyを利用

4. 応用・実験研究論文

• Junttila, T., & Kaski, P. (2007)
  Engineering an Efficient Canonical Labeling Tool
  → Blissとの比較、Nautyの実測性能分析

• Babai, László (2016)
  Graph Isomorphism in Quasipolynomial Time
  → グラフ同型性問題における理論的ブレイクスルー

5. 関連アルゴリズムとの比較

• Bliss vs Nauty：Junttila & Kaski (2007)

• Traces vs Nauty：McKay & Piperno (2014)

• Saucy vs Nauty：SAT/SMTの対称性削減論文で比較

• VF2 vs Nauty：Cordella et al. (2001), 多数のベンチマークで評価