（追記）こんにちは、社会人のJoeです。この当時はいろいろ未熟なところが多く、記事の内容がかなり過激なのですが、当時の気持ちを尊重したいという考えもあって、残しておきます。記事の最後に社会人目線での今の感想も載せておくのでよければそこまで目を…

b-matchingというものを知った。 グラフが与えられたとき、次の条件を満たす辺集合はb-matchingであるという。 各頂点のdegree restrictionをとし、各辺のcapacity が与えられる。このとき各辺についてcapacity以下の重みをとって、各頂点について隣接する辺…

A separator theorem for minor-closed classes を読むと、minor-closedなグラフはのseparatorを持つのでは？という話がされている。この論文では実際に、をminorとして含まないようなグラフについて、のseparatorを持つことを証明している。 したがって、bo…

A Separator Theorem for Planar GraphsとOn Sparse Graphs with Dense Long Pathsを読む。 ちょっとずつまとめていく。 On Sparse Graphs with Dense Long Paths 論文の主定理は以下の通り どんな頂点を取り除いても長さのPathが残るようなDAGの辺数をとし…

e-archive.informatik.uni-koeln.de を読んだ。 https://icpc-girigiri.slack.com/archives/GJM417MNV/p1566016527000100 にファイルがある。 概要 平面グラフのmax-cutをmaximum weighted matchingに帰着させて解いている。平面グラフのmaximum weighted ma…

次数行列をかけて正規化してやらないとだめ。 証明したい

数学的なグラフは頂点の接続情報だけが重要だけど、分子は、立体的な構造を伴う。 ラベル付きグラフの重み（頂点間距離）を学習したり、頂点間距離からラベル（原子）を学習したりできる。 pre-trainingにいいかもしれない。

これやってる人いるかな。普通に気になる。 平面グラフ from yutaka1999 www.slideshare.net yutaka1999氏のスライドがあり、平面グラフ判定は本気を出すとでできるなどと書かれていてびっくりする。 Max-Cut e-archive.informatik.uni-koeln.de 平面グラフ…

https://arxiv.org/pdf/1905.12265.pdf 読んだ。大抵のGNNのタスクはnode classificationだけど、化学や生物の分野だとlocal similarityやgraph全体の特徴が重要になることが多い。 この論文では、自然言語処理で行われるような、Context PredictionやMaskin…

えー。また競プロとは全然関係のない記事です。同じことをやっていそうな人が少なくてエラーが出てこなかったのでまとめます。 手順1: CUDA対応MacBook Proを購入する えー。MacBook Mid 2012-2014 15 inchしか対応していないと思います。しかも15 inchじゃ…

Quadratic Assignment Problem (NP-hard) Given , () ただしはとの要素ごとの積の和 Graph Isomorphism 図は省略するが、同型なグラフがあったときに、頂点のラベル付けの置換行列をとすると、はとなる。 同型ならとなる。 Subgraph Isomorphism 頂点の個数…

https://arxiv.org/pdf/1905.10947.pdf PFNで著者と話したのでメモ GCNの表現能力についての問題。畳み込みの際に用いるの特異値が小さい場合、レイヤー数に対して指数的に表現能力が落ちてしまうという問題。 連結成分数に対応して大きさが決まる特定の空間…

https://arxiv.org/pdf/1904.12787.pdfを読む。 Contribution GNNで1つのグラフを入力とし、similarity判定に使えるvectorを出力する方法 Graph Matching Networkと呼ばれる、入力は2つのグラフで、出力がそのsimilarity scoreのネットワークを提唱。Cross-g…

S2V-DQNがZhuwenの論文に書かれていたよりもずっと強力であることがわかった。 細かく追えていないがaggregateがGNNよりも一般的に見えるし普通にGNNより強いのでは？という気分になってきた。 Weightedの場合も自然にエンコードできるのは強そう。 ところで…