3つの要点 ✔️ GNNの表現力の強さから、急速にアプリケーションが進んでいる。 ✔️ GNNの柔軟かつ複雑な構造への、従来深層学習手法の展開についてのレビュー ✔️ 一方で、深層学習に共通、グラフに固有の課題も継続中 Graph Neural Networks: A Review of Methods and Applications written by Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, Maosong Sun (Submitted on 20 Dec 2018 (v1), last revised 9 Apr 2021 (this version, v5)) Comments: Published on AI O
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
棒グラフや折れ線グラフ、どうやって実装していますか？ Charts.cssなら簡単です。データをtableタグで実装し、CSSのクラスをtableに加えるだけで横棒グラフ、棒線グラフ、折れ線グラフ、エリアグラフなどを簡単に実装できるCSSのフレームワークを紹介します。 HTMLは普通の表組みなのでアクセシブル、グラフやチャートはレスポンシブにも完全対応した優れものです。 Charts.css Charts.css -GitHub Charts.cssの特徴 Charts.cssのデモ Charts.cssの使い方 Charts.cssの特徴 Charts.cssはtableで実装した表組みにシンプルなCSSのクラスを加えるだけで、さまざまなグラフやチャートを実装できるフレームワークです。カスタマイズも簡単で、ユーティリティのクラスも豊富に用意されています。 HTMLとCSSだけで実装 セマ
Introduction • Examples • Quick Start • API G6 is a graph visualization engine. It provides basic capabilities for graph visualization and analysis such as drawing, layout, analysis, interaction, animation, themes, and plugins. With G6, users can quickly build their own graph visualization and analysis applications, making relational data simple, transparent, and meaningful. G6, as a professional
The dataset used for this visualization comes from GloVe, and has 6B tokens, 400K vocabulary, 300-dimensional vectors. Distance < 0.9 - In this visualization edge between words is formed when distance between corresponding words' vectors is smaller than 0.9. All words with non-word characters and digits are removed. The final visualization is sparse, yet meaningful. Distance < 1.0 - Similar to abo
There are a few things that contribute to the performance of this library. I'm using heap-based priority queue, built specifically for the path finding. I modified a heap's implementation, so that changing priority of any element takes O(lg n) time. Each path finder opens many graph nodes during its exploration, which creates pressure on garbage collector. To avoid the pressure, I've created an ob
本記事は、2019年夏のインターンシップに参加された中野裕太さんによる寄稿です。 皆様はじめまして。2019 年 PFN 夏季インターンシップに参加していた北海道大学の中野裕太です。本ブログでは、私が夏季インターンで取り組んだテーマである、「Graph Neural Network を用いたグラフの木幅予測」について説明します。 要旨 与えられた無向グラフがどれくらい木に近いかを表す値である木幅は、グラフ上の組み合わせ最適化問題に対するアルゴリズムの効率性や解そのものと深く関係しています。しかし、木幅を計算することは NP 困難なため、木幅を計算するには頂点数に対し指数時間かかってしまいます。そこで、今回 Graph Neural Network を用いた 2 つの方法でこの問題にアプローチしました。1 つ目は、よく知られた既存のアルゴリズムと組み合わせ探索木の枝刈りを行い高速化を図り計算
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
Dgraph is a horizontally scalable and distributed GraphQL database with a graph backend. It provides ACID transactions, consistent replication, and linearizable reads. It's built from the ground up to perform a rich set of queries. Being a native GraphQL database, it tightly controls how the data is arranged on disk to optimize for query performance and throughput, reducing disk seeks and network
ニホンアマガエルの合唱は、個々では鳴くタイミングをずらし、全体では一斉に休む時間がある――筑波大学、大阪大学が1月9日、そんな研究結果を発表した。カエルの合唱の法則性を、IoT機器のネットワークに活用すれば、近くの端末同士のパケット衝突を回避でき、ネットワーク全体の接続性向上やエネルギーの省力化が期待できるという。 研究チームは、オスのカエル3匹を50センチ間隔で並べ、録音した鳴き声を解析。短時間でみると「オス同士は鳴くタイミングをずらしている」という先行研究の結果に加え、長時間でみると「鳴いている区間（時間帯）をそろえる」という性質を確認した。 同チームは、個々のカエルは鳴くたびにエネルギーを失い、疲労度が増すという仮説を立てた。その上で、エネルギーと疲労度、周囲で鳴いているオスの有無によって発声状態（周期的に鳴き声を発する状態）と休止状態（鳴かずにエネルギーの消費を抑える状態）を確率的
Graph Convolutionを自然言語処理に応用するため、何回かに分けて学習した内容をまとめていきます。内容については、最終的にQiitaなどで1記事にまとめる予定です。 Part1では、Graphを扱う過去の手法からGraph Convolutionへと到るまでの過程を解説します。また、Graph Convolutionに着目した理由についても述べておきます。 なぜ自然言語でGraph ConvolutionかGraph Convolutionに着目した理由はTransformerです。Transformerで使用されているSelf-Attentionは、各単語が他の全単語とどれくらい関係しているかの重みを算出します。これは、単語をノードとみなすとまさにグラフ構造のような形になります。 Attention-based Models (DLAI D8L 2017 UPC Deep L
はじめまして。ABEJAでResearcherをやらせていただいている白川です。 先日、化合物の物性推定をDeep Learningをつかって従来手法より300,000倍高速に処理するという論文がでました（[1], [2]）。この論文の手法は、Graph Convolutionというグラフ上に定義されたConvolution演算がベースとなっています。物性推定に限らず、グラフ解析全般を Deep Learning で上手にこなせるようになれば、Deep Learningのアプリケーションの幅がぐっと拡がり、さらなるイノベーションが起きそうな予感がします。 ICMLやNIPSなどの機械学習系の主要国際会議でも数年前からGraph Convolutionについての論文がちらほら出現しはじめており、とくに最近その勢いが増してきている印象があります。個人的にも最近（前から？）にわかにグラフづいてい
僕は、最小全域木を求めるKruskal法をココロから納得するのにとても長い時間が掛かってしまいました。本記事では、備忘録的な目的を兼ねて、少しKruskal法について書いてみたいと思います。 僕は、Kruskal法は今年5月頃初めて知ったのですが、そのときはどうしてコレで最小全域木が求まるのか、不思議でなりませんでした。その後6月頃にアルゴリズムイントロダクションを読んで、ひとまず証明は理解したのですが、イマイチなかなかイメージが掴めませんでした。さらに7月にはマトロイドの触りを勉強し、マトロイドのGreedyアルゴリズムからKruskal法が自然に導かれることを学んだのですが、それでもまだKruskal法をココロから納得するには至れませんでした。 それくらい、Kruskal法を納得するのにとても苦労しました。ようやく自分なりにKruskal法が納得できるようになったのは、マトロイドの交換
最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた． 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という． 最小全域木を求めるアルゴリズムとしては以下の二つが有名である． クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲
この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何故でしょうか？実は、マトロイドは単に「Greedyの一例」として出て来るばかりでなく、「現在効率的なアルゴリズムが知られている問題の殆どはマトロイドが何かしら関わっている」と言える程にイイ構造を持っています。以前、以下のようなツイートをしました。 dpやってていつも思うのが、なんか凸凹してるなーと。凸凹し過ぎてdpじゃなきゃ解けないよな、みたいな感じ。マトロイドは凹んでるところがない凸なイメージ。だから、局所最適狙う貪欲法だけで最適解に辿り着ける。焼き鈍しなんて必要ない。 本記事では、この
グラフ問題とバルク同期並列の常識をGiraphで体得：ビッグデータ処理の常識をJavaで身につける（5）（1/3 ページ） Hadoopをはじめ、Java言語を使って構築されることが多い「ビッグデータ」処理のためのフレームワーク／ライブラリを紹介しながら、大量データを活用するための技術の常識を身に付けていく連載 ソーシャル時代の「グラフ問題」の重要性 「グラフ問題」とは、どのようなものか、ご存じでしょうか？ ご存じでない方でも実は、「グラフ」を活用したシステムを日常的に使っているのです。 その1つは「Google」「Yahoo!」といった、Webの検索システムです。Webの検索システムでは、検索結果の表示順の判断基準の1つとして、Webページの重要度を示す「PageRank（ページランク）」と呼ばれる指標を用います。このPageRankは「注目に値する重要なWebページは、たくさんのページ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
