SDM '15 タイトルだけ見てきになったやつ
グラフアルゴリズムっぽいやつらだけ。それにしても最近論文読めてない...
A Divide‐and‐Conquer Algorithm for Betweenness Centrality Dora Erdos*, Boston University; Vatche Ishakian, IBM ; Evimaria Terzi, Boston University; Azer Bestavros
Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs Liangyue Li*, Arizona State University; Hanghang Tong, ASU; Yanghua Xiao, Fudan University; Wei Fan, Huawei Noahs Ark Lab
Community Detection for Emerging Networks Jiawei Zhang*, UIC; Philip S. Yu, University of Illinois at Chicago
Efficient Algorithms for a Robust Modularity‐Driven Clustering of Attributed Graphs Patricia Iglesias Sanchez*, KIT; Emmanuel Müller, Karlsruhe Institute of Technology (KIT); Uwe Leo Korn, KIT; Klemens Boehm, KIT; Andrea Kappes, KIT; Tanja Hartmann, ; Dorothea Wagner, KIT
Fast Eigen‐Functions Tracking on Dynamic Graphs Chen Chen*, Arizona State University; Hanghang Tong , Arizona State University]
Functional Node Detection on Linked Data Kang Li*, State University of New York at Buffalo; Jing Gao, SUNY at Buffalo; Suxin Guo, University at Buffalo, The State University of New York; Nan Du, University at Buffalo, The State University of New York; Aidong Zhang, State University of New York at Buffalo
On Influential Nodes Tracking in Dynamic Social Networks Xiaodong Chen*, Peking University
Rare Class Detection in Networks Karthik Subbian*, University of Minnesota; Charu Aggarwal, IBM Watson Research; Jaideep Srivastava, University of Minnesota; Vipin Kumar, UMN
Vertex Clustering of Augmented Graph Streams Ryan McConville*, Queen's University Belfast; Weiru Liu, Queen's University Belfast; Paul Miller, Queen's University Belfast
Where Graph Topology Matters: The Robust Subgraph Problem Hau Chan, Stony Brook University; Shuchu Han, Stony Brook University; Leman Akoglu*, SUNY Stony Brook
SIGMOD '15 タイトルだけ見て気になったやつ
内容把握したら色をつける
- GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks
Hui Li (Xidian University); Sourav S Bhowmick (Nanyang Technological University); Jiangtao Cui (Xidian University); Yunjun Gao (Zhejiang University);
- BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs
Kijung Shin (Seoul National University); Jinhong Jung (KAIST); Sael Lee (The State University of New York (SUNY) Korea); U Kang (KAIST);
* Minimum Spanning Trees in Temporal Graphs
S. HUANG, A. W.-C. Fu, R. Liu.
シュタイナー木に帰着. temporal graphの問題はそもそもよさ気な問題を見つけること自体が難しそう.
*LASH: Large-Scale Sequence Mining with Hierarchies
Kaustubh Beedkar (University of Mannheim); Rainer Gemulla (University of Mannheim);
- Indexing Metric Uncertain Data for Range Queries
Lu Chen (Zhejiang University); Yunjun Gao (Zhejiang University); Xinhan Li (Zhejiang University); Christian S. Jensen (Aalborg University); Gang Chen (Zhejiang University); Baihua Zheng (Singapore Management University);
- Efficient Similarity Join and Search on Multi-Attribute Data
Guoliang Li (Tsinghua University); Jian He (Tsinghua University); Dong Deng (Tsinghua University); Jian Li (Tsinghua University);
- Influence Maximization in Near-Linear Time: A Martingale Approach
Youze Tang (Nanyang Technological University); Yanchen Shi (Nanyang Technological University); Xiaokui Xiao (Nanyang Technological University);
- Community Level Diffusion Extraction
Zhiting Hu ( Peking University & Carnegie Mellon University); Junjie Yao (East China Normal University); Bin Cui (Key Lab of High Confidence Software Technologies (MOE), School of EECS, Peking University); Eric Xing (Language Technologies Institute, Carnegie Mellon University);
- Divide & Conquer: I/O Efficient Depth-First Search
Zhiwei Zhang (The Chinese University of Hong Kong); Jeffrey Xu Yu ( The Chinese University of Hong Kong); Lu Qin ( University of Technology, Sydney); Zechao Shang ( The Chinese University of Hong Kong);
- Efficient Enumeration of Maximal k-Plexes
Devora Berlowitz (The Hebrew University of Jerusalem); Sara Cohen (The Hebrew University of Jerusalem); Benny Kimelfeld (Technion, Israel Institute of Technology);
- Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates
Xiaoyang Wang (The University Of New South Wales); Ying Zhang (University of Technology, Sydney); Wenjie Zhang (The University Of New South Wales); Xuemin Lin (The University Of New South Wales); Muhammad Aamir Cheema (Monash University);
- Exact Top-k Nearest Keyword Search in Large Networks
Minhao Jiang (The Hong Kong University of Science and Technology); Ada Fu (The Chinese University of Hong Kong); Raymond Wong (The Hong Kong University of Science and Technology);
- Updating Graph Indices with a One-Pass Algorithm
Dayu Yuan (Google); Prasenjit Mitra (QCRI); Huiwen Yu (Google); C. Lee Giles (Penn State University)
The Minimum Wiener Connector Problem
Ruchansky, F. Bonchi, D. Soriano, F. Gullo, N. Kourtellis.
与えられるクエリ頂点集合Qに対してwiener indexが最小になるようなQを含む部分グラフを求める問題. クエリ頂点付近で重要そうな頂点をみつけることができるようだ. 解析では理論的な成果を組み合わせて定数近似のアルゴリズムであることを示しているが,定数がめちゃくちゃでかい.まさか理論系の会議以外でこんなに大きな定数をみるとは・・・
- Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach
Nikos Armenatzoglou (Hong Kong University of Science and Technology); Huy Pham (University of Southern California); Vasilis Ntranos (University of Southern California); Dimitris Papadias (Hong Kong University of Science and Technology); Cyrus Shahabi (University of Southern California);
* COMMIT : A Scalable Approach to Mining Communication Motifs from Dynamic Networks
S. Gurukar. S. Ranu. B. Ravindran.
- Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time
Michael Cochez (University of Jyvaskyla); Hao Mou (University of Jyvaskyla);
- Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity
Lijun Chang (University of New South Wales); Xuemin Lin (University of New South Wales); Lu Qin (University of Technology, Sydney); Jeffrey Xu Yu (The Chinese University of Hong Kong); Wenjie Zhang (University of New South Wales);
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に対してのサイズになってしまうが,それを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
WWW '15 アブスト読み
いくつかの論文のアブストだけ読んだ。
Provably Fast Inference of Latent Features from Networks
Charalampos Tsourakakis.
概要
ソーシャルネットワーク上において、各エージェントは自分と似た性質を持つエージェントと関係を持つ傾向があることが知られており、結果としてコミュニティが出現する。また、複数のコミュニティに属するエージェントというのも存在する。
無向グラフGが与えられて、ある確率的生成モデルを仮定したときに各頂点の特徴を推測したい。 この論文では二つの頂点が多くの特徴を共有するほど高い確率で辺がはられる確率的生成モデルと、高速に混合するマルコフ連鎖を用いて頂点の特徴を推定する手法を提案する。
実データに対する実験によって機械学習に基づく手法より2,400倍高速に質の良い推定を行うことができることを示した。
Network A/B Testing: From Sampling to Estimation
Huan Gui, Ya Xu, Anmol Bhasin and Jiawei Han.
概要
A/Bテストは新しいサービスに対するユーザの反応を測る手法として知られている。 A/Bテストを行うときには、ユーザ同士がソーシャルネットワークで相互に関係している場合でも、ユーザ同士が互いに影響を与えないものとしてユーザをサンプルするが多い。しかし実際にはそうではないということを示し、ユーザ同士の干渉がある場合でも精度をおとさずに推測を行う方法を提案した。
Querying Web-Scale Information Networks Through Bounding Matching Scores
Jiahui Jin, Samamon Khemmarat, Lixin Gao and Junzhou Luo.
概要
Web-scale informationネットワークへのクエリはsubgraph matchingとして見ることができるが、現実のデータは不完全であり多くのノイズを含んでいる。この論文では与えられたクエリに対して前処理なしで、Top-Kの答えを出力する手法を提案する。グラフ同士の類似度を定義し、分散処理でも動かせる枝刈り手法を用いて高速化する。
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment
Anshumali Shrivastava and Ping Li.
概要
Minwise hashingは集合同士の演算を近似的に行うための乱択データ構造であるが元々の対称なMinwise hashingには集合を小さめに見積もってしまうというバイアスが存在する。本論文ではそのバイアスを克服するための非対称なMinwise hashingを提案する。
Efficient Densest Subgraph Computation in Evolving Graphs (WWW '15)
Efficient Densest Subgraph Computation in Evolving Graphs (WWW '15)
Alessandro Epasto, Silvio Lattanzi and Mauro Sozio.
概要
Densest subgraphを動的なグラフで効率良く計算する。densest subgraphと動的なグラフという流行りと流行りを合わせた感じがする。厳密なdensest subgraphの計算は非常に時間がかかるので \(2 + \epsilon \)近似のsubgraphを保持してそれを \( polylog (n + r) \)のならし計算時間で更新していく。 このとき辺の挿入は最悪ケースを考慮していて辺の削除は一様ランダムであることを仮定している。
実際の時系列データのタイムウィンドウ内の辺からなるグラフを考えることでインスタンスに対する辺の挿入削除のベンチマークを作っている。実験結果より1B辺のグラフに対する更新が数百マイクロ秒でできることが示された。
Replacing the Irreplaceable : Fast Algorithms for Team Member Recommendation (WWW '15)
Replacing the Irreplaceable : Fast Algorithms for Team Member Recommendation (WWW '15)
Liangyue Li, Hanghang Tong, Nan Cao, Kate Ehrlich, Yu-Ru Lin and Norbou Buchler.
概要
チームメンバが諸事情により欠けてしまい新しいメンバをチームに加えるときにチームとしてのパフォーマンスが落ちないようにしたい。このとき新しいメンバは、(1) 前のメンバと似たようなスキルセットを持っていて、(2)他のメンバとの関係がいなくなるメンバと似ている、という条件を満たしていることが望ましい。
今まで(1), (2)の両方を同時に満たすようなメンバを求める方法は提案されてこなかったので、今回は良い感じのグラフカーネルを定義して定式かすることで(1), (2)を両立する新メンバを求める。
ナイーブに全てのメンバに対してグラフカーネルを計算すると1M頂点のグラフだと6,000秒くらいかかってしまうので枝刈りを用いて高速化した厳密手法と近似手法を提案する。
ユーザ実験により提案手法が良いチームメンバを推薦していることを確かめた。 また計算機実験により１０人程度のチームであれば20秒程度で結果を出せることを示した。
Scalable Methods for Adaptively Seeding a Social Network (WWW '15)
Scalable Methods for Adaptively Seeding a Social Network (WWW '15)
Thibaut Horel and Yaron Singer.
概要
Influence maximizationの亜種について考える。多くの応用において情報を拡散させるためのシードとして選べる人（core set）は限られており、core setに属する人が高い影響力（例えば次数）を持っているとは限らない。 なので、まず第一段階としてまず与えられた予算の一部を用いてcore setの部分集合に対して彼らの友達に情報を拡散してもらうよう頼む、第二段階ではOKしてくれた人達に対して残りの予算を用いて情報の拡散を最大化してくれる人の部分集合を選ぶという方法を考える。２段階でやるというアイデアは多くの人は自分自身は影響力が強くなくても影響力が強いひとを知っているという事実 (Friendship paradox)に基づいている。
- 使用する情報拡散のモデルはvoter modelのように部分集合の影響力が各要素の影響力の和になるものなら良い。
- サンプリングによらない手法
- Core setがランダムに選ばれたものでない場合に対しても実験
- ２つのアルゴリズムを提案して、どちらも近似率は \(1 - \frac{1}{e} \)。サブモジュラ最大化っぽい。
