mits58のメモ

メモ 参考にしないでください

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

arXiv

読んだ。以下メモ

結局何したん?

  • GNN って Distributed Local Algorithm と関連してるよね
  • なので、Distributed Local Algorithm の理論使って GNN がどれくらいの近似解を算出できるかを解析したよ
  • んで、理論的に一番な GNN である CPNGNN を提案したよ

 

  • Distributed Local Algorithm は GNN の Aggregation っぽいことを行ってグラフ上の組合せ最適化を解くアルゴリズム
  • なので、Distributed Local Algorithm と GNN で解ける問題クラスが同じだよってことを示して解析してる
  • 今回 Input Graph の最大次数を Δ で固定する仮定を置いて解析してる(よくある仮定らしい)

じゃあ、今回の GNN の売りポイントって何っていうと

  • Message Passing において、ノードごとに渡すメッセージを変えている
  • Aggregate した後の各要素を Concatenate する(普通 sum とか max とか ave とっちゃう)

ってところ。でも2つ目は最大次数の仮定がないとできないよね……

ノードごとに渡すメッセージを変える部分は Port numbering と呼ばれるテクニックを用いているらしい。

で、finding single leaf problem って問題に対して適用してみたら GCN とかじゃ溶けなかったけど CPNGNN だとできたよ。

 

コメント

  • 実際に学習してみたらどうなったんだろう…… Empirical な解析がなかった
  • 結構最大次数を Bound する仮定が効いてそう……とは思いました

 

Preferred Networks さんにインターンシップに行きました

Preferred Networks さんにインターンシップに行きました。

何をしたかは下記へどうぞ。

 

簡単に言うと、グラフの計算が難しい統計量である「木幅」を、グラフニューラルネットワークで予測してみようというタスクに取り組みました。

自分がディープラーニングナニモワカラナイ……のと、夏休み中という短い期間だったので、大した成果はないです……(つらい)

 

ということでリサーチブログでは書かなかった諸々を書き連ねます。

選考について

  • 今思い返しても受かった理由が、「メンターさんの興味とかぶった」以外にわからない……(本当に拾っていただきありがとうございます……)
  • 面接でも上手く喋れず、コーディング課題もそこまでできたというわけじゃないですが、インターンでやりたいことは結構明確に書いた記憶があります。
  • なので、来年以降受ける皆さんは、テーマはメンターと相談して決める……というより、自分からメンターを引き寄せる(!?)つもりで行くといいと思います

労働環境とか待遇とか

  • 大手町は昼飯が高いです。「食堂のかけそば(230 yen)」みたいなのは存在しないと思ってください…… 僕自身3000円弱のランチを一度食べてしまいました(極厚ローストビーフでした……美味しかった)
  • 英語ができないとちょっとつらい思いをします(僕はしました)なので、受かってからで良いので英語になれておくといいと思います。
  • あと計算資源が潤沢でした……羨ましい……

今回の研究について

  • 自分としては、Chainer を使って疎行列演算を用いたグラフ畳み込みを実装できたのは良かったです。Chainer-Chemistry の実装は密行列形式で隣接行列を持っているため、実グラフデータに対して不適だよなぁと思っていました。
  • ただ、Max 演算でクソデカ行列くんを生成してしまうので、そこはつらいなぁ…… (Scatter 演算の実装はよ)
  • 後、手法1として提案した、「分類モデルによる誘導部分構造における部分問題に対する解の分類結果を用いた枝刈り」は汎用性が高いと思っています。

 

ということで、2ヶ月弱ほどありがとうございました!

 

 

 

「埋蔵分子」発掘プロジェクト―化学反応経路マップのインタラクティブ可視化に向けて

evernote に埋もれている論文メモをはてなブログへ移行しています。

   

2.分子構造と化学反応経路の探索

2.1トポロジカルな分子構造の数え上げ

  • トポロジカル法:原子と結合のトポロジカルな関係に基づき数学的に列挙する方法。A. Kerber, R. Laneらによるもの→速い、原子価を満たすもののみ、分子構造が平面

2.2量子化学に基づく分子・反応経路探索

  • PES上の極小点と鞍点を結ぶ反応経路を探索
    • 分子構造とその合成方法を得る数え上げ法:ポテンシャル法
    • Scaled Hypersphere Searchという手法により自動的に探索が可能になった
  • Global Reaction Route Mapに実装されている
  • ポテンシャル曲面を超球面探索法により網羅的に探索するらしい
  • トポロジカル法と比べて色々な構造が列挙できるよ

2.3「埋蔵分子」発掘プロジェクト

  • GRRMをつかって反応経路の網羅的探索とリポジトリ化を行う
    • 学情報資源を整備するプロジェクト
  • 効率良い検索しすてむがほしい

3化学者による化学反応経路マップの解析

3.1GRRMからの出力:化学反応経路マップ

  • GRRMから、幾何学情報と物理化学的パラメータが得られる
    • 幾何学情報→分子構造(原子の種類と三次元座標値)     - 物理化学的パラメータ→ポテンシャルエネルギーなど
  • EQ:PES上の極小点 安定な分子構造のこと
  • TS:2つのEQを結ぶ化学反応経路上の最もポテンシャルエネルギーの高い地点 遷移状態
  • DC:1つの分子構造が分解し、2つ以上の分子構造へと変化するときの分離した状態のこと 解離チャネル
  • GRRMは複数のEQ、TS、DCをノードとしてもつ
  • 1つの組成式から得られるネットワーク全体を化学反応経路マップという  

    3.2化学反応解析の基本要件

    注目する属性
    • 分子構造 EQ、TS、DCの構造情報は基本的な属性、平面構造から立体構造まである、化学反応経路を経る過程で分子構造がどのように変化していくかを示す動画も重要らしい
    • EQのポテンシャルエネルギー 分子の内部エネルギー、その化合物がどの程度安定に存在しうるかを示す指標=値が低いほど現実に多く存在しうる可能性高い。逆にこれが高い化合物は高い反応性を持つ=反応設計のキー反応物となるポテンシャルをもつ。必須の基本的な物理化学的数値データ
    • TSのポテンシャルエネルギー あるEQが別のEQに変化するためにはエネルギーの壁を超える必要あり=活性化エネルギー 活性化エネルギー=TSのポテンシャルエネルギーと反応物のポテンシャルエネルギーの差分で表される 1つのEQ構造が複数のEQ構造へ変化する複数の経路が存在するとき→最も低い活性化エネルギーを経る反応が最も起こりやすい
    • 化学反応ステップ数 EQを結ぶ複数の反応経路の解析をするとき→いくつのEQ構造を経ているかの情報=反応ステップ数も大事な情報→よりステップ数の少ない反応経路の方が効率的な合成となる  
  • 反応物を指定した検索 興味のある反応物から出発した検索と各ノードの詳細情報の解析を行う 出発点となる反応物を決める基準
  • 分子構造、ポテンシャルエネルギー値 出発点が反応物→反応予測、生成物→化学合成設計  
  • 反応物と生成物を指定した検索 2つのノードを指定→その間を結ぶ全ての化学反応経路の探索と各ノードの詳細情報の解析を行う →全てのパスのうち、より低い遷移状態を経るものが実際に起こりやすい+反応ステップ数が少ないものが有望な化学反応経路  

    4化学反応経路の可視化

  • ボール&スティック表示と呼ばれる分子モデル図がある→重要な可視化
  • 最もポテンシャル      

    コメント

    ・埋蔵分子の合成方法を得るためにも反応経路ネットワーク解析したいって気持ちになりますね ・GRRMってすごいんや(べた褒めされてるし) ・DCっていう構造もあるのね(あんまりよくわかってないけど) ・3-2あたりはためになった ・結局活性化エネルギーとステップ数が解析の上で重要そう    

Revisiting Graph Neural Networks: All We Have is Low-Pass Filters

arXiv

ちょっと気になりばーっと読んだ。

これはなに?

Graph Convolution って、実はグラフ信号処理における Low-Pass Filter と同じやんけ!なので、単純にグラフ信号に対して Low-Pass Filter かけたやつを MLP で学習させたら GCN と同じくらいになって、人工データだと勝ったよん。

  • まず、既存のデータセットの特徴ベクトルは、低周波の真の特徴ベクトルにノイズを加えたものになっているんじゃないかって仮説を検証している
  • 実際、グラフフーリエ変換とかで確かめてみたら、だいたい下位20%の周波数の特徴要素で十分な精度が出てるし、それより多くすると精度が下がっちゃった
  • で、次に Graph Convolution でよくやる Adjacency Matrix を掛けるって演算は Low Pass Filtering と同じだよってことを、グラフ信号処理におけるグラフフィルタを使って示してる
  • そして、単純に Filter かけたやつと GCN や SGC に対し精度の保証を与えて実験して確認してる

コメント

  • Adjacency Matrix を掛けるってのは Sum Pooling とか Average Pooling と同じなんだけど、Max Pooling ではないんだよね……そこってどうなるんやろ
  • 後これ多層 GNN への拡張してないのでそことか考えてみるとまた違う? でもこれも、Low-Pass Filter の重ねがけみたいな感じになるんやろか……うーん
  • 逆に Graph Convolution は任意の Low-Pass Filter を近似できるってことになるんかな?

IPCO 2019 目を通したリスト

IPCO って思ったより Integer Programming よりなんですね……

1. Integer Programming and Incidence Treedepth - Eduard Eiben, Robert Ganian, Sebastian Ordyniak, Michal Philipczuk and Marcin Wrochna.

  • 整数計画問題の容易さは、制約行列の構造と深く関係しているってのが最近わかった。具体的には、制約行列の Gaifman graph の primal (or dual) treedepth と、絶対値最大の係数に関して FPT ってのがわかった。
  • これを、より広いクラスの整数線形計画問題に対して拡張してみたらどう?ってのがこの論文らしい。結果としては、FPT ではなくて、すべての係数の絶対値が 1 で、incidence treedepth が 5 であるときでさえ NP-hard だったらしい。
  • Gaifman graph とはなんぞや……と思ったら、ノードが変数で、ある制約条件に共起する場合、そのノード間に辺を張ってできるグラフらしい。
  • Treedepth もよくわかっていないので調べたら、TREE-DEPTH AND VERTEX-MINORS に、スターグラフにどれくらい近いかを測る指標っぽい(小さいとスターグラフに近いって感じ)
  • 問題に対応するグラフ構造を使って解析しているのは面白いなぁ、こういうのやってみたい。

2. Strong mixed-integer programming formulations for trained neural networks - Ross Anderson, Joey Huchette, Christian Tjandraatmadja and Juan Pablo Vielma.

  • 訓練済みニューラルネットワークに対応する、高次の区分的線形関数に対する強い混合整数計画定式化を提案。
  • この定式化は、画像分類ネットワークが敵対的入力に対しロバストであることの証明や、機械学習モデルが目的関数である決定問題を解く際に用いることができる。
  • このMIP定式化を ReLU とか Max Pooling とかに適用してみて、画像分類タスクにおけるネットワークで推論時間がかなり改善したっぽい。
  • 正直???という感じだけど、面白そうではある。ただ、Neural Network そのものに対しての解析はかなりやられてそうだし今更感も……?

3. A Bundle Approach for SDPs with Exact Subgraph Constraints - Elisabeth Gaar and Franz Rendl.

  • 厳密部分グラフアプローチってのは、いくつかのグラフ上の NP-hard な問題に対するよりタイトな半正定値計画緩和を得るための階層的なスキーマなんだけど、これを解くのは禁止部分グラフ制約が多すぎてつらい。
  • 部分的なラグランジュ双対を導入して、その評価が2つの独立した部分問題になるという事実を利用するらしい。よくありそうなテク。

arXiv になかったのとかもあって悲しみ。

ICLR 2019 読むリスト

読みます(多すぎ)

  • LanczosNet: Multi-Scale Deep Graph Convolutional Networks
    Renjie Liao · Zhizhen Zhao · Raquel Urtasun · Richard Zemel
    PDF » 
  • Diffusion Scattering Transforms on Graphs
    Fernando Gama · Alejandro Ribeiro · Joan Bruna
    PDF » 
  • Learning To Solve Circuit-SAT: An Unsupervised Differentiable Approach
    Saeed Amizadeh · Sergiy Matusevych · Markus Weimer
    PDF » 
  • Generative Code Modeling with Graphs
    Marc Brockschmidt · Miltiadis Allamanis · Alexander Gaunt · Oleksandr Polozov
    PDF » 
  • Graph Wavelet Neural Network
    Bingbing Xu · Huawei Shen · Qi Cao · Yunqi Qiu · Xueqi Cheng
    PDF » 
  • Conditional Network Embeddings
    Bo Kang · Jefrey Lijffijt · Tijl De Bie
    PDF » 
  • Capsule Graph Neural Network
    xinyi zhang · Lihui Chen
    PDF » 
  • Large Scale Graph Learning From Smooth Signals
    Vassilis Kalofolias · Nathanaël Perraudin
    PDF » 
  • Supervised Community Detection with Line Graph Neural Networks
    Zhengdao Chen · Xiang Li · Joan Bruna
    PDF » 
  • Invariant and Equivariant Graph Networks
    Haggai Maron · Heli Ben-Hamu · Nadav Shamir · Yaron Lipman
    PDF » 
  • Dynamic Sparse Graph for Efficient Deep Learning
    Liu Liu · Lei Deng · Xing Hu · Maohua Zhu · Guoqi Li · Yufei Ding · Yuan Xie
    PDF » 
  • Deep Graph Infomax
    Petar Veličković · William Fedus · William L Hamilton · Pietro Liò · Yoshua Bengio · R Devon Hjelm
    PDF » 
  • DyRep: Learning Representations over Dynamic Graphs
    Rakshit Trivedi · Mehrdad Farajtabar · Prasenjeet Biswal · Hongyuan Zha
    PDF » 
  • Combinatorial Attacks on Binarized Neural Networks
    Elias Khalil · Amrita Gupta · Bistra Dilkina
    PDF » 
  • Neural Graph Evolution: Automatic Robot Design
    Tingwu Wang · Yuhao Zhou · Sanja Fidler · Jimmy Ba
    PDF » 
  • Learning Multimodal Graph-to-Graph Translation for Molecule Optimization
    Wengong Jin · Kevin Yang · Regina Barzilay · Tommi Jaakkola
    PDF »
  • Learning Representations of Sets through Optimized Permutations
    Yan Zhang · Jonathon Hare · Adam Prugel-Bennett
    PDF » 
  • Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs
    Ryan L Murphy · Balasubramaniam Srinivasan · Vinayak Rao · Bruno Ribeiro
    PDF » 
  • Attention, Learn to Solve Routing Problems!
    Wouter Kool · Herke van Hoof · Max Welling
    PDF » 

Descriptors Generation Using the CDK Toolkit and Web Services

Tutorials in Chemoinformatics(Alexandre Varnek)の9章の読書メモ

Molecular Descriptor(分子記述子)の話と分子記述子を生成するソフトウェアだったり、Webサービスだったりの話

 

What's 記述子

  • Molecular Descriptorは、分子情報に由来する、分子の属性や表現である
    例えば: 分子の重さ、原子の個数〜複雑なものまで様々
  • 分子構造のある側面を捉えるために設計されている
    e.g. 定量的構造物性相関(QSPR)とか定量的構造活性相関(QSAR)とかに用いられる
  • 実験結果の値もMolecular Descriptorとして使われるよ
    e.g. 分配係数*1とか、分光学的特性とか(他のアクセスしにくいエンドポイント[???]を予測するのに関連性があるらしい)
  •  本質的な記述子は、分子全体の特性を含む
    i.e. 分子の重みや原子の数、結合の数、回転可能な結合の数、分子量などを含む

記述子の分類

  • Fragment Descriptor: 官能基や前もって決められた部分構造の出現頻度をカウントするもの
  • Topological Descriptor: 分子構造を数学的なグラフとして考え、グラフ理論を用いグラフ不変量を求めそれを用いる
  • Geometrical Descriptor: 分子の三次元構造をエンコードしたもの(特に3D Descriptorと呼ばれる)異なる立体配座*2のもの(conformations)、ジアステレオ異性体*3(diastereoisomers)を区別することができる

分子記述子の例

  • Wiener Index [Topological Descriptor]
    分子内の水素以外の原子に対しペアを考えた際の距離の総和
    距離は2つの原子間に存在する結合の数で定義される
    = 距離行列の全ての要素を加算し2で割ると得られる
    分岐の兆候を示し、ファンデルワールス面に対する簡単なアプローチである(?)
  • 2D autocorrelation vectors [Topological Descriptor]
    原子同士のトポロジカル距離と、それぞれの原子の特性(部分電荷、分極率とか)の値の積により表現される。
  • Radial Distribution Function codeRDF descriptors)[3D Descriptor]
    さっきの2D autocorrelation Descriptorの距離の部分を3次元距離にしたもの

 

あとはソフトウェアの解説なので飛ばす。解説してたのは

  • CDK Descriptor Calculator
  • E-DRAGON Web Service
  • OCHEM Web Service

の3つ。

 

 

 

ジアステレオ異性体とかの話↓

1-2 3) エナンチオマーとジアステレオマー - YAKU-TIK ~薬学まとめました~

こんな風に生物学的活性が異なるようなペアが存在するらしい(すごい)

ってことはQSARとか考えるときは3D Descriptorがよくない?(しらん)

 

*1:水と油のような、2つの混ざり合わない液体を同じ容器に入れ、どちらの液体にも溶ける第三の物質を加えてよく振ると、両方の液体中の第三の物質の濃度の比がある値に一定になる、そのときの値。疎水性を表したりする、あと固体と液体でも定義可能

*2:ぐるぐる動かせる単結合などの結合に関して、その位置が異なる関係の化合物

*3:キラル中心が存在する物質に関して、鏡像関係にあるもの、乳酸とか