Skip to content

HACK TO THE FUTURE 2023 予選 (AtCoder Heuristic Contest 016)

問題概要

  • 整数Mとエラー率εが与えられる
  • 予め整数N(4 <= N <= 100)を決めておき、頂点数がすべてNであるM個の無向グラフを作成する
  • 各クエリ(100回)では、M個のうちのどれか1つから「エラー率で辺が反転」かつ「頂点をランダムに並び替えた」グラフHが与えられる
  • クエリごとに、どのグラフから生成されたかを予測せよ
    • スコアは、Nが小さいほど、かつ、間違いが少ないほど高くなる

時間

  • 216 時間

個人的メモ

  • Nをできるだけ小さくしつつ、ノイズとラベルなしグラフの対処をするのが難しい問題
  • 素直に、ノイズなしのケースから考えて、それをベースに発展させていくのがよかったかも

問題固有の性質

  • 「M個のグラフをどう用意するか？」と「Mクラス分類問題」
    • 分類問題：グラフHが与えられて、どのクラスGに属するかを当てる問題
  • Nをできるだけ小さくしたいが、Nが小さい場合は全探索可能
  • 埋め込むグラフは前もって計算しておくことが可能
    • できるだけ都合のよいグラフを探索

アプローチ

  • 今回、いろんなアプローチが適用できた
  • 手法ごとに得意不得意があるようで、可能ならεなどに応じて複数の手法を組み合わせたほうがよかった模様

全ケース埋め込み系

ブロック行列系

  • εが大きい場合に有効(最上位)だった手法な模様
  • k個のクラスタを持つようにして、クラスタ内、クラスタ間に辺を貼る
    • 頂点をグループ(クラスタ)に分ける
    • k=5でも、クラスタ内の辺(自己ループ、対角要素のところ)をどうするかも含めて区別すればM=100に足りる
    • 他にも、補グラフを考える、など
  • または、クラスタの頂点数を変えたクリーク(完全グラフ)やスターグラフを埋め込む
    • 頂点数の違いで区別する
      • サイズ8が2個＋サイズ10が1個とか、個数も考慮するとN進数にできる
  • どちらの場合でも、隣接行列を拡大したような感じになって、冗長性があり、ノイズに耐性ができる
  • ただ、頂点の(クラスタへの)対応付けが必要で、それは山登りや焼きなまし、クラスタリング、マッチング(最小費用流)？などで行う
    • ただし、ここはあんまり単純ではないかも(目的関数の工夫や多点スタートなど必要かも。ref:解説放送)
    • 解説放送では、隣接行列で見たとき、各ブロック内は「辺なし」か「全部辺がある」感じになるので、各ブロック内の頂点数をd、辺のある本数をkとしてmin(k,d^2-k)を全ブロックについて和を求めたものを目的関数にする感じの方法が説明されていた
    • ただ、この関数はd^2/2本付近でどっち側に行くかが急激に変わるのでなめらかではなく、最適化が難しい
      • 初期解(山をできるだけ超えなくてすむようにグルーピング)を作ってから最適化
    • さらに、何回かやって求める感じにする場合は、似た接続状況の頂点があるときに過小評価されやすい問題もあるので、補正なども
    • 4クラスタでも100パターン作れるが5クラスタにしているのは、このあたりの問題も考慮してできるだけ成功率が高いグラフを選ぶため？

ベイズ系

  • データHが与えられたときにクラスGのどれか？(Mクラス分類)
  • ベイズの定理からP(G|H) = P(H|G)P(G)/P(H) ～ P(H|G)
    • P(G)は等確率で選ばれる、P(H)は他のGでも共通
  • P(H|G)はGからHが生成される確率で、これは計算可能
    • ラベル付きグラフとして考えると、Hを固定してGの頂点を入れ替えて辺の対応関係を見ると、1/N! * Σ_{頂点の入れ替え方すべて} p^(変化した辺の数) * (1-p)^(変化してない辺の数)
    • Nが小さければ普通に計算しても間に合う
      • εが小さい場合に有効(admin解など)だった手法な模様
    • または、サンプリングで生成、など
  • Gの選び方で分類成功率が変わるので、Nと分類成功率で一番スコアが高くなるように(前もって)選ぶ
  • 選んだグラフ以外のありえるグラフすべてについても考慮

グラフ間の距離を使う系

  • 距離が十分離れたGを選んで使うのが重要
  • ただし、解説放送で言及されていたが、距離として、単純にGとHとの最小誤差(異なっている辺の数、ハミング距離、編集距離)的なものを見てしまうと、(だいたい)同じ距離の別のGと誤判定してしまう可能性がある
    • たとえ、その誤判定したGからHが生成される可能性が低かったとしても
  • 生成確率(上のベイズの定理)を考慮することで、より可能性が高いGを選ぶことができる
  • https://twitter.com/satanic0258/status/1594281359539073024

次数列間の距離を使う系

特定のグラフを埋め込む系

  • 特定のグラフを埋め込んで、それを取り出して、その数などで判断
  • ノイズがのったあとに区別しやすい/取り出しやすいとは限らないので、埋め込むグラフをどうするかはいろいろ考える余地がある
    • かなり近いグラフを埋め込むことになりがちで、それらの区別に失敗しやすい
    • 完全グラフ(クリーク)
    • スターグラフ
    • k-正則グラフ
    • 二部グラフ
    • 補グラフ
    • 複数種類の混ぜ合わせ
    • その他
  • 複数グラフを入れる場合、それらのグラフ間は独立にしたりしがちなので、ノイズ耐性をもたせようとすると、どんどんNが大きくなり得る
    • そのためいろいろうまく噛み合わないとこのアプローチでは100位以内も難しかった模様
  • ノイズ耐性のもたせ方として、Mが小さい場合は、3倍するなどすれば、取り出し時にプラマイ1ずれても大丈夫になる
  • 数の表現の仕方は、いろいろ
    • そのまま個数で表現
    • ビットに割り当てて表現
    • 同じものを複数個入れる場合は、n進数的に扱いにする
    • など
  • 取り出し方(クラスタリング)はいろいろ
    • ルールベース
    • 山登り、焼きなまし
    • グラフクラスタリング
    • ノンパラベイズ
  • クラスタリングでも、そのグラフがあるかどうか、だと自由度が高くて探しにくい
    • クラスタ数はk個、と固定して頂点のクラスタ番号を考える方が扱いやすかった模様(ブロック行列系)

GNN系

  • グラフの分類問題なので、GNNが考えられる
    • 1位のnagissさんやeivourさんはこの方向な模様
  • GNNの代表的なタスクとしては、ノード単位かグラフ単位
  • ざっくり、隣接行列とεを入力に、頂点ごとのchannelをベクトルとして出力して、各Gごとに、GとHの頂点間の割当コストをベクトルの内積にして割当問題で最小となるものを求めている模様(ネットワークはGraph Attention Network(GATs)？Transformer-Encoderライクな模様)
  • (基本、推論コードだけ提出になるので、グラフの選び方や学習の部分とかはコードからはわからなそう → 解説記事参照)

諦める系

  • εが0.4に近いほどノイズが大きすぎて正解するのが難しい
    • (とはいえ、上位はかなり正解している、、、)
  • 下手に手法を適用するよりもN=4で適当に解答したほうがスコアが出うる
  • https://twitter.com/yuusanlondon/status/1594306814807789568

ソースコードに埋め込む

パラメータを埋め込む

  • 今回は、Mやεによって最適なパラメータ(Nなど)を前もって計算しておきソースコードに埋め込むことができた
  • また、G自体も埋め込んでおくこともでき、計算時間削減ができた
  • 分類モデルなどを埋め込んでいた人も結構いた模様
    • ただし、ソースコードのサイズが増大して制限に引っかかる可能性も
  • バイナリ埋め込みはbase64などで
  • バイト列埋め込みは罠がある

コードを埋め込んで複数の言語を使う

  • コンパイル時間や実行時間、入出力時間が含まれてしまうが、言語をpythonにしてC++コードを吐き出してビルドしてファイルを生成して参照などができる
    • 逆にC++コードでpythonを使う、なども
  • 利点として、c++は高速な実行、pythonはnumpy,scipy,scikit-learn,networkx等が利用できるので、高速な行列演算や実装が難しい関数、ライブラリ等での結果をc++で使うことができる、など
import os

os.system("g++ --version")

#include <iostream>

int main(){
  system("python3.8 --version");
  return 0;
}

関連する話題

2元対称通信路(Binary Symmetric Channel)

反復符号(繰り返し符号, Repetition code)

  • wikipedia
  • ビットの情報をn回繰り返すことで冗長性を持たせる
    • 今回でいうと、複数の辺に同じ情報を持たせる感じ
  • decodeは、多数決を取ることで、多少のノイズがあっても正しく情報を得られることを狙う
  • たとえば、n=5の場合は、入力が0なら00000を送る感じで、5つのうち3個or4個or5個が反転してしまうと誤りになってしまうので、エラー率はp_e = Comb(5,3) * p^3 * (1-p)^2 + Comb(5,4) * p^4 * (1-p) + Comb(5,5) * p^5
  • 今回、p=0.4までありえるため、エラー率を小さくしようとすると、かなり大きなnが必要なことがわかる

Stochastic Block Model

スペクトラルクラスタリング

Markov Cluster Algorithm(MCL)

Weisfeiler-Lehman Graph Kernels

Stoer-Wagner Algorithm

最大クリーク

次数列からグラフ生成

QRコード

その他

解説

(100位まで&発言を見つけられた方のみ)