ネットワーク構造の知的処理

深層学習

コミュニティ抽出のための変分グラフオートエンコーダ

variational autoencoder (VAE)は深層学習におけるモデルの一つであり、画像認識などにおいて画像 の生成モデルを学習することによって、画像の分類をしたり、与えられた画像に似た人工的な画像を生成 したりすることが可能になります。この考え方をグラフ構造に応用したvariational graph autoencoder (VGAE) に注目します。VGAEにおいては、encoderとしてはGraph Convolutional Networkを用い、decoderとしては 内積を用いています。本研究では、ネットワーク中の複数のコミュニティに対応する複数のGaussianの分布に よってグラフ構造をencodeするネットワーク生成モデルvariational graph autoencoder for community detection (VGAECD)を提案し、関連手法とコミュニティ抽出の精度を比較することによって提案手法の有効性 を示しました。

Jun Jin Choong, Xin Liu, Tsuyoshi Murata, "Learning Community Structure with Variational Autoencoder", Proceedings of IEEE ICDM 2018 (IEEE International Conference on Data Mining), pp.69-78, November, 2018. (採択率:8.86%)

Jun Jin Choong, Xin Liu, Tsuyoshi Murata, "Variational Approach for Learning Community Structures", Complexity, Vol. 2018, Article ID 4867304, 13 pages, 2018.

深層学習による火山噴火分類と早期予測

近年、音声認識、画像認識、自然言語処理などの様々な分野において深層学習が優れた性能を示しています。しかしながら、時系列データの学習に適用した例は比較的少ないです。この研究では時系列データとして、特に火山の観測機器から得られる時系列データに対して深層学習を適用しました。火山の観測機器から得られる時系列データは現在と将来の噴火と大きな関係があります。しかしデータは複雑で、専門家にとっても分析は容易ではありません。我々は火山噴火分類と火山噴火予測の二つの問題に注目しました。 前者(火山噴火分類)の目標は、100分間の時系列データからその100分間の火山の状態(噴火か否か)を認識することです。また後者(火山噴火予測)の目標は、100分間の時系列データから兆候を認識してその直後の60分間の火山の状態(噴火か否か)を予測することです。 複数モーダルを融合した提案手法であるVolNetは畳み込みニューラルネットワーク(CNN)に基づいて火山噴火分類を行い、F-scoreで90%の精度を達成しました。火山噴火予測については、Attentional Stacked Long Short-Term Memoryに基づく提案手法のPredictNetはsensitivityが66%、また警告システムでの一番危険度の高いカテゴリでの予測精度が64%と高い性能を示しています。我々は火山の研究者との協力のもと、火山に関する最大級の規模と質の時系列データを用いた実験によって、提案手法の有効性を示しています。

Hiep V. Le, Tsuyoshi Murata, Masato Iguchi, "Deep Modular Multimodal Fusion on Multiple Sensors for Volcano Activity Recognition", Proceedings of ECML-PKDD 2018 (European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases), September, 2018. (16 pages)

リンクマイニング

ネット上の様々なソーシャルサイト(delicious, twitter,...)は、今や情報共 有やコミュニケーションのインフラとして必要不可欠なものになっています。 このようなサイトを含め、ネット上で世界中のユーザが発信する膨大な情報を 有効活用するための試みが幅広く行われています。村田研究室では、ネット上 の情報のネットワーク構造に注目し、関連する要素の発見(コミュニティ抽出) や、要素の重要性の判定(ランキング、スパム検出)、将来のネットワーク構造 の推定(リンク予測)などを行っています。

セマンティックWebの単語間の関係予測

Knowledge Graph などの大規模なセマンティックWebを構築する上で、単語間の関係を予測することは重要です。Resource Description Framework(RDF)上の単語間の関係を高い精度で予測することを目標に、主語と目的語を入力として、それらの関係を出力するDeep Neural NetworkであるRDFDNNを構築しました。RDFDNNは、既存手法であるTransEやTransRよりも高精度な予測を実現できました。

大貫 陽平, 貫井 駿, 村田 剛志, 稲木 誓哉, 邱 シュウレ, 渡部 雅夫, 岡本 洋, "DNNを用いたRDF上の単語間の関係の予測", 第41回セマンティックウェブとオントロジー(SWO)研究会, SIG-SWO-041-02, 8 pages, 2017. (2016年度人工知能学会研究会優秀賞受賞)

Tsuyoshi Murata, Yohei Onuki, Shun Nukui, Seiya Inagi, Xule Qiu, Masao Watanabe, and Hiroshi Okamoto, "Predicting relations between RDF entities by Deep Neural Network", Workshop on Semantic Deep Learning (SemDeep), 12 pages, collocated with ESWC 2017, 2017.(SemDeep Best Paper Nomination)

Yohei Onuki, Tsuyoshi Murata, Shun Nukui, Seiya Inagi, Xule Qiu, Masao Watanabe, and Hiroshi Okamoto, "Predicting relations of embedded RDF entities by Deep Neural Network", The 16th International Semantic Web Conference, poster (4 pages), 2017.

コードをGitHubで公開しています。

異種頂点ネットワークの高精度な分類

論文、著者、会議名などの複数種類の頂点が結びついたheterogeneousネットワークで、一部の頂点のラベルが与えられたときに、残りの頂点を分類するtransductive classificationを高精度化するアプローチを提案しました。edge betweenness の定義を改良することで、最新の手法(GNetMine)よりも5%程度の精度向上を実現しました。

Phiradet Bangcharoensap, Tsuyoshi Murata, Hayato Kobayashi, Nobuyuki Shimizu, "Transductive Classification on Heterogeneous Information Networks with Edge Betweenness-based Normalization",Proceedings of the 9th ACM International Conference on Web Search and Data Mining (WSDM2016), pp.437-446, 2016.

制約付きコミュニティ抽出の高速化

ネットワークからコミュニティを抽出する手法は数多く提案されていますが、トポロジーだけに注目するのではなく人間が持つ背景知識を用いることで、直観に合った結果にすることができます。背景知識を積極的に活用しようと試みる制約付きコミュニティ抽出手法として、モジュラリティを一般化して制約項を付加した制約付きハミルトニアンを最適化する手法がEatonらによって提案されていますが、速度が遅く大規模なネットワークには不向きです。本研究では、Eatonらが用いた擬似焼きなまし法ではなく、目的関数を高速に最適化するLouvain法を用いて、制約付きハミルトニアンを最適化し、制約付きコミュニティ抽出を高速化しています。

Keisuke Nakata and Tsuyoshi Murata, "Fast Optimization of Hamiltonian for Constrained Community Detection", Proceedings of the 6th Workshop on Complex Networks (CompleNet 2015), Studies in Computational Intelligence, Vol. 597, pp.79-89, Springer, 2015.

仲田圭佑, 村田剛志, "ハミルトニアンに基づいた制約付きコミュニティ抽出の高速化" 人工知能学会論文誌 Vol.30, No.1, pp.96-101, 2015.

江口幸司, 村田剛志, "マルチスライスネットワークにおける制約付きコミュニティ抽出法", 人工知能学会論文誌, Vol.32, No.1, WII-C, pp.1-9, 2017.

Koji Eguchi and Tsuyoshi Murata, "Constrained Community Detection in Multiplex Networks", Proceedings of the 9th International Conference on Social Informatics (SocInfo 2017), pp.75-87, 2017.

動的ネットワークの影響最大化

影響最大化問題は、社会ネットワーク上での情報伝搬や病気の感染において、情報や病気が最も広く拡散する頂点集合を見つける問題です。従来法の多くは中心性の高い頂点集合を求めていましたが、これでは影響を最大化する頂点集合は得られません。また厳密解を求めるのは静的ネットワークであっても計算量的に困難です。本研究では、動的ネットワークの影響最大化問題において、貪欲法とヒューリスティクスを用いることによって、厳密解と遜色ない精度の近似解を高速に求めることに成功しました。

Shogo Osawa and Tsuyoshi Murata, "Selecting Seed Nodes for Influence Maximization in Dynamic Networks", Proceedings of the 6th Workshop on Complex Networks (CompleNet 2015), Studies in Computational Intelligence, Vol. 597, pp.91-98, Springer, 2015.

大澤翔吾, 村田剛志, "動的ネットワークにおける影響最大化" 人工知能学会論文誌 Vol.30, No.6, pp.693-702, 2015.

3部ネットワークからのコミュニティ抽出

現実の多くのソーシャルメディアは、様々な種類の頂点や辺を含んだヘテロなネットワークとして表現できます。例えばYouTubeはユーザ、タグ、動画の3種類の頂点から構成される3部ネットワークとみなすことができます。我々はこのようなネットワークから密な部分(コミュニティ)を抽出する手法を開発しました。

Pythonのプログラムはここからダウンロードできます。

Kyohei Ikematsu and Tsuyoshi Murata, "A Fast Method for Detecting Communities from Tripartite Networks", Proceedings of the 5th International Conference on Social Informatics (SocInfo 2013), pp.192-205, 2013.

池松恭平, 村田剛志, "3部モジュラリティの改善とその最適化手法" 人工知能学会論文誌, Vol.29, No.2, pp.245-258, 2014.

Signed Networksからのコミュニティ抽出

Signed networkは友人関係と敵対関係という二種類の辺を含んだネットワークです。我々はネットワーク分割の評価指標であるモジュラリティをSigned Networkに拡張しました。その結果、現実の社会ネットワークで見受けられるような派閥内派閥を見出すことに成功しました。

デモンストレーションはこちら

杉原貴彦, 劉欣, 村田剛志, "Signedネットワークからのコミュニティ抽出", 人工知能学会論文誌, Vol.28, No.1, pp.67-76, 2013.

離れたメンバーからなるコミュニティの抽出

距離的に近い人は関係が密になりやすい傾向があります。そのような傾向を排除することによって、距離的に遠くに散らばった友人グループを見つけることができます。従来のコミュニティ評価指標を統合した新たな指標(Dist-Modularity)によって、地理的に散らばったコミュニティを見つけることができます。

Xin Liu, Tsuyoshi Murata, Ken Wakita, "Detecting network communities beyond assortativity-related attributes", Physical Review E 90, 012806, 2014..

この指標を用いて、テロリストのコミュニティを見つける試みも米国の研究者によってなされています。

Paulo Shakarian, Patrick Roos, Devon Callahan, Cory Kirk, "Mining for Geographically Disperse Communities in Social Networks by Leveraging Distance Modularity", KDD2013.

スケールフリーネットワークからのコミュニティ抽出

現実世界における多くのネットワークはスケールフリー性をもっています。我々はそのようなスケールフリーネットワークからのコミュニティ抽出手法を開発しました。

Sorn Jarukasemratana, Tsuyoshi Murata, Xin Liu, "Community detection algorithm based on centrality and node distance in scale-free networks", Proceedings of the 24th ACM Conference on Hypertext and Social Media (Hypertext 2013), pp.258-262, 2013.

Sorn Jarukasemratana, Tsuyoshi Murata, Xin Liu, "Community Detection Algorithm based on Centrality and Node Closeness in Scale-Free Networks", 人工知能学会論文誌, Vol.29, No.2, pp.234-244, 2014.

大規模ネットワーク可視化ツールのサーベイ 大規模ネットワークを可視化するツールは数多く開発されています。以下のサーベイ論文では、最近のツールとしてigraph, Gephi, Cytoscape, Tulip, WiGis, CGV, VisANT, Pajek, In Situ Framework, Honeycomb, JavaScript InfoVis Toolkit, GraphGLを紹介しています。

Sorn Jarukasemratana, Tsuyoshi Murata,"Recent Large Graph Visualization Tools : A Review"コンピュータソフトウェア, Vol. 30, No. 2 pp.159-175, 2013.

スピーチ中の単語の構造の可視化

偉大なスピーチは意味的に良い構造をしていると考えられます。与えられたスピーチの質を自動的に測るための第一歩として、我々はスピーチ中の単語の構造を、英単語の意味的関係を表す辞書であるWordNetと、単語感情極性対応表を用いて可視化しました。

デモンストレーションは こちら

Yu Sakamoto and Tsuyoshi Murata, "Visualizing the Structure of Great Speeches", Poster Proceedings of IEEE Pacific Visualization Symposium , pp.21-22, 2014.

2部ネットワークのコミュニティ抽出・可視化

Webの掲示板と、それに書き込みをするユーザの関係は、2種類の頂点からなる2部ネットワークとして表現することができます。そのような2部ネットワークから密な部分ネットワーク(コミュニティ)を抽出することで、類似した内容の掲示板や、興味の似通ったユーザを見つけることができます。2種類の頂点のコミュニティを抽出し可視化するとともに、コミュニティ間の対応関係の尺度を定義しました。

村田 剛志, 池谷 智行, "異種頂点ネットワークで表現されたインターネットQA掲示板の分析と視覚化", 人工知能学会論文誌, Vol.23, No.5 pp.293-302, 2008.

オンラインQAサイトにおけるリンク予測

人を頂点、その友人関係を辺として表すと、人間関係を社会ネットワークとして表すことができます。社会ネットワークの現在の構造から、将来の構造を予測することができたら、新たな人間関係の発展を見出したり重要人物を同定したりすることができます。ネットワーク上の頂点間の距離関数を改良することで、予測の精度を向上させました。

Tsuyoshi Murata and Sakiko Moriyasu, “Link Prediction based on Structural Properties of Online Social Networks”, New Generation Computing, Vol.26, No.3, pp.245-257, 2008.

大規模ネットワークからの高速コミュニティ抽出

一般にネットワークから最適なコミュニティを抽出する計算はNP困難であり、ネットワークが大規模になるほど現実的な時間での計算が困難になります。コミュニティ抽出の手法は数多くありますが、比較的高速な手法と、高精度な手法を組み合わせることで、頂点数が100万程度の2部ネットワークでのコミュニティ抽出を可能にしました。

劉欣, 村田剛志, "Community Detection in Large-scale Bipartite Networks", 人工知能学会論文誌, Vol.25, No.1, pp.16-24, 2010.

異種頂点ネットワークのコミュニティ抽出の評価指標

与えられたネットワークを分割してコミュニティを抽出するにあたり、その分割の良さを測る指標として、Newman-Girvanのモジュラリティがあります。モジュラリティは非常に幅広く使われていますが、異種頂点ネットワークに対しては適切ではありません。モジュラリティの定義を2部ネットワークに拡張し、コミュニティの対応関係が1対多であるような分割も許す新たな評価指標を提案し実験を行いました。

Tsuyoshi Murata and Tomoyuki Ikeya, "A New Modularity for Detecting One-to-Many Correspondence of Communities in Bipartite Networks", Advances in Complex Systems, World Scientific, Vol. 13, No. 1, pp.19-31, 2010.

タイトル: K-Partite K-Uniform (ハイパー)ネットワークからのコミュニティ抽出

説明: 一般のK-Partite K-Uniform (ハイパー)ネットワークからのコミュニティ抽出の手法を提案しました。この手法は従来手法の欠点を克服するとともに、理解しやすさ、適合性、パラメータ設定の必要性、精度、スケーラビリティの点で望ましい性質を有しています。

ポスターはここ

Web利用データのマイニング

ユーザがWebにアクセスすることで、アクセスログ、ブックマーク、検索語など、様々なデータが生じます。そのようなデータをもとに、ユーザの興味を抽出したりする研究を行っています。
Web閲覧履歴からのユーザ興味の抽出

ユーザが閲覧したサイトと、検索時に入力した検索語からなるネットワーク(サイト-キーワードグラフ)の頂点のランキングを行い、中心的な部分を抽出することで、そのユーザの興味を推定する手法を考案し、8,000人程度のユーザデータを用いて実験を行いました。

村田剛志, 齋藤皓太:サイト・キーワードグラフを用いたWebユーザの興味の抽出と視覚化, 知能と情報, Vol.18, No.5, pp.701-710, 2006.



戻る