以前はcupyをインストールしましたが、今回もなかなかに面倒でした… xuzijian629.hatenablog.com バージョンについて 最近のpytorchをビルドするにはCUDA 9.0以上が必要なのですが、CUDA 9.0以上にした状態でcupyをインストールしようとすると、nvccのエラー…

team omorisuJoe(@omochana2, @risujiroh. @xuzijian629)で参加して5位（オンサイト2位）でした！ もともとteam Girigiriで参加すると思っていたのですが、ぼく以外のteam GirigiriのメンバーはTTPC2019募集開始日からすでに相手を決めていたらしく、会場で…

（追記）こんにちは、社会人の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の場合も自然にエンコードできるのは強そう。 ところで…

github.com オリジナルの説明が全然役に立たないのでまとめ直す。 1. Build 1.1 git clone --recursive https://github.com/Hanjun-Dai/graph_comb_opt 唯一そのままでうまく動く 1.2 Build graphnn github.com 一応こちらの説明に沿ってやる 1.2.1 CUDAをht…

基本構文 <target>: <files> <commands> <target>: <commands> 実行 makeとやると、Makefileに定義された最初のターゲットが実行される。他のターゲットを実行するにはmake clean, make installなど臨機応変にターゲット名を入力。 特別なターゲット名 .PHONY .PHONY test とかよくみる。コマンド名とフ</commands></target></commands></files></target>…

Persistent Homologyをまったく知らない人は先にhttps://xuzijian629.hatenadiary.jp/entry/2019/07/20/192722を読んでください。 Super Simplified Overview あまりに本質な画像なんですが、グラフのNodeにWeisfeiler-Lemanの方法に従ってラベルを付けてい…

黄色になりました！！！！！ pic.twitter.com/05lnFYtuV4— Joe@ジャッジを見る (@xuzijian629) 2019年7月20日 伝統に従って記事を書きます。 やったこと AtCoder, CodeForces, Topcoderのコンテストに（撤退することもあるけどとりあえず）出続ける 短期間で…

A Persistent Weisfeiler–Lehman Procedure for Graph Classificationを読んでいてPersistent Homologyとは？となったので、調べた内容をまとめる。 Motivation [1] 目標として、データの幾何学的構造を捉えたい。リング状になっているデータ点の集合あった…

4完24位でした。 感想 この一戦だけに絞って感想を言うなら、「Eをもう少し落ち着いて確実に合わせに行きたかった」となるのですが、さすがに今回のICPCは自分にとって最後のICPCであり、チームGirigiriとはこの一戦のみならず人としての付き合いが長いので…

2つのデータがどれだけ似ているかを返す関数です。 非負実数を返し、似ていれば値は大きく、似ていないと小さいです。 以上！ カーネルトリックについて たいてい回帰問題の文脈で現れると思いますが、元のデータ点を直線（もしくは超平面）で回帰することは…

ガウス過程 (Gaussian Process; GP)を簡潔に説明します。日本語の類書や類ウェブページ？はたくさんありますが以下の差別化を図りました できるだけ数式による説明を心がけます 定義をスムーズにするために関数空間の観点からGPによる回帰を説明し、実は線形…

知り合いからおもしろい問題を聞いたので解いてみました。おもしろいかは人によると思いますが、数え上げ方がおもしろかったのでまとめます。 タイトルを解法のキーワードにしようと思ったんですが非常にもったいないネタバレをしてしまいそうなので先に問題…

これは自分が学部生のときに気になっていたことなので紹介します。卒論が人生初論文になりそうな人を想定します。 時系列を追って書いていこうかなと思います。後半は経験していないので理解している範囲で想像で書いてます 卒論テーマを決める これがだいぶ…

研究でpytorchを初めて使ったんですが、いろいろつまづきました。3つ紹介します。top 3と書きましたがtopじゃないかもしれません torchのtensorのサイズはintではなくtorch.Size型 まあ基本中の基本なので知ってる人は多いと思いますが、arr.size() == 1とか…

起きました。さーて研究研究といいながらvscodeを開いてターミナル実行しようとしたら一瞬でターミナルが落ちます。 このままじゃエラーメッセージすら読めないので一瞬のすきを突いてスクショをしてみると なにこれ！？！？！？！？ 検索されやすいようにエ…

またポエム記事です。お付き合いください。 最近、ちょっとはマシになったとはいえ、まだまだ機械学習の人気は絶えません。 本屋に行けば機械学習の本は相変わらずたくさんありますし、Qiitaの機械学習の記事も増え続けています。 ぼくは、競争的な分野がす…

最近けんきう＋競プロで忙しいんですが、こういうとき却ってブログ書きたくなりますね。 なんか専門の分野があるってかっこいいなという話です。 ぼくは東京大学の理学部情報科学科出身ですが、多分他大学や他学科の情報系とは一線を画する雰囲気があると思…