KDD '15 タイトルだけ見て気になったやつ

論文読み

  • (Paper ID: 40) Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages

  • Riondato, E. Upfal. Brown University

アブストを読んでみたがタイトル内容以上のことを理解できなかった.　知識のなさを感じる・・・

  • (Paper ID: 53) Panther: Fast Top-k Similarity Search on Large Networks

Jing Zhang, Tsinghua university; Jie Tang*, Tsinghua University; Cong Ma, Tsinghua; Hanghang Tong, ASU; Yu Jing, Tsinghua; Juanzi Li, Tsinghua University

  • (Paper ID: 77) Online Influence Maximization

　S. Lei, S. Maniu, L. Mo, R. Cheng, P. Senellart.

通常の影響最大化問題とは異なり,「情報が伝達する確率が事前には与えられずseedを一つずつ選んでいく過程で得られていく」という問題設定を扱うためのフレームワークを扱っている.

  • (Paper ID: 80) Robust Treecode Approximation for Kernel Machines

　Wi. March, B. Xiao, S. Tharakan, C. Yu, G. Biros. University of Texas at Austin

機械学習にでてくるKernelは訓練データ数nに対して \Sigma(n)のサイズになってしまうが,それをtreecodeを利用してうまく低ランク近似する方法を提案.

  • (Paper ID: 91) Probabilistic Community and Role Model for Social Networks

　Y. Han, J. Tang.

ソーシャルネットワークのコミュニティに対して確率モデルを定義し,辺の情報からEMアルゴリズムとギブスサンプリングを用いて学習を行う.様々な実ネットワークでの応用においてモデルを変更することなくベースラインの手法よりも良いパフォーマンスを実現した. 手法の時間計算量にO(NM)とか見えるのでスケーラビリティは良くないのかもしれない.

  • (Paper ID: 116) On the Discovery of Evolving Truth 　Y. Li, Q. Li, J. Gao, L. Bo Zhao, W. Fan, J. Han

多くのデータが存在するときには,複数の情報源から得られたデータが存在してそれらが互いに矛盾しているということが起こりうる.そのため各情報源から得られる情報の信頼度を求めるというのはhot-topicであるが,この論文ではデータがincrementalに追加されていく中で信頼度を動的に更新するということをやる.

  • (Paper ID: 117) Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier

　W. Xie, D. Bindel, A. Demers, J. Gehrke. Cornell University

PPRにおいて問い合わせ行列ではなくて遷移行列がpersonalizedされている場合についての高速な計算方法を提案している. そのような場合に対する手法はあまり提案されてこなかったらしい. 前計算として遷移行列を低ランク近似するらしいが詳細は知らない.

  • (Paper ID: 118) Stream Sampling for Frequency Cap Statistics

Edith Cohen*, Tel Aviv University

  • (Paper ID: 127) Adaptive Message Update for Fast Affinity Propagation

　Y. Fujiwara, M. Nakatsuji, H. Shiokawa, Y. Ida, M. Toyoda, NTT

Affinity Propagationというクラスタリング手法の高速化. 他の単純なクラスタリング手法よりも精度が良いらしい. 愚直なAffinity Propagationでは一回の反復ですべての頂点間でavailabilityとresponsibilityの２つの指標をやりとりしているが,　提案手法では既存の手法よりも強力なavailability/responsibilityの上限・下限を定義し更新していくことによってやりとりが必要な頂点対を限定し,　一回の反復に必要な時間を大幅に減らすことに成功している.　ただ,　最初に全頂点対間の類似度を見る必要があるためスケーラビリティという面では厳しいように思える.　近似方法もあまり思いつかない.

  • (Paper ID: 228) Efficient PageRank Tracking in Evolving Networks

Naoto Ohsaka*, The University of Tokyo; Takanori Maehara, Shizuoka University; Ken-ichi Kawarabayashi, National Institute of Informatics

  • (Paper ID: 236) Locally Densest Subgraph Discovery 　Lu Qin, R.-H. Li, L. Chang.

Top-Kの最密部分グラフを求めるとグラフの一つの密な領域だけからK個とってきてしまうので,　より多様な部分グラフをマイニングするためにlocally densest subgraphというものを定義する. これは最密部分グラフ同様良い性質を持っていて多項式時間で計算できる.　さらに高速化するテクニックを導入して１００万頂点規模のネットワークで動かす.

  • (Paper ID: 252) Community Detection based on Distance Dynamics

Junming Shao*, UESTC; Zhichao Han, UESTC; Qinli Yang, UESTC; tao Zhou, UESTC

  • (Paper ID: 316) Network Lasso: Clustering and Optimization in Large-Scale Graphs

David Hallac*, Stanford University; Jure Leskovec, Stanford University; Stephen Boyd, Stanford University

  • (Paper ID: 321) Set Cover at Web Scale

Stergios Stergiou*, Yahoo! Labs; Kostas Tsioutsiouliklis, Yahoo! Labs

10 billion頂点規模のネットワークにおける分散近似アルゴリズムを提案. さらに提案手法を構成部品として従来の４倍の速度でWebクローリングを行うシステムを開発した.（強い）

  • (Paper ID: 411) Integrating Vertex-centric Clustering with Edge-centric Clustering for Meta Path Graph Analysis

Yang Zhou*, Georgia Institute of Technology; Ling Liu, Georgia Institute of Technology; David Buttler

  • (Paper ID: 431) Warm Start for Parameter Selection of Linear Classifiers

　B. Chu, C.-H. Ho, C.-H. Tsai, C.-Y. Lin, C.-J. Lin, National Taiwan University

線形識別器の正規化項のパラメタを効率良く自動決定する手法を扱う.

  • (Paper ID: 720) Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling

Michael Mitzenmacher, Harvard University; Jakub Pachocki, Carnegie Mellon University; Richard Peng, MIT; Charalampos (Paper ID: Babis) Tsourakakis*, Harvard University; Shen Xu , Carnegie Mellon University

  • (Paper ID: 896) Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs

Ethan Elenberg*, University of Texas at Austin; Karthikeyan Shanmugam, University of Texas at Austin; Michael Borokhovich, University of Texas at Austin; Alexandros Dimakis, University of Texas at Austin