| 8月3日（月） | 8月4日（火） |
秋葉 拓哉 （ＮＩＩ）
Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark (AAAI’15)
2 頂点間の関連度や類似度を推定することは，ソーシャルネットワークをはじめとする大規模グラフデータにおける最も重要な処理の1つであり，ネットワーク構造予測やネットワークを考慮した情報検索などの重要な応用を持つ．本論文では (1) 関連度や類似度の新たな指標としてTop-k距離を用いることを提案し (2) Top-k距離を高速に求めるための索引付け手法を提案する．提案する索引付け手法は，通常の距離に対する索引付け手法である枝刈りラベリング法に基づいているが，Top-k距離への拡張を行うために経路の数を新たに考慮する必要が生じる．特に，同じ経路を 2度数えないための工夫やその正しさの証明は非自明なものとなる．また応答性能やスケーラビリティの低下を防ぐための高速化手法も複数提案する．実データを用いて比較実験を行い，提案手法が索引を用いない既存の手法より最大で百万倍程度高速にTop-k 距離の計算が行えることを確認した．さらに，応用先の 1 つとしてリンク予測問題を取り上げ，提案手法によって計算した Top-k距離が精度の向上に寄与することから，Top-k距離が関連度指標として有用であることを確認した．
We propose an indexing scheme for top-k shortest-path distance queries on graphs, which is useful in a wide range of important applications such as network-aware searches and link prediction. While many efficient methods for answering standard (top-1) distance queries have been developed, none of these methods are directly extensible to top-k distance queries. We develop a new framework for top-k distance queries based on 2-hop cover and then present an efficient indexing algorithm based on the recently proposed pruned landmark labeling scheme. The scalability, efficiency and robustness of our method is demonstrated in extensive experimental results. Moreover, we demonstrate the usefulness of top-k distance queries by applying them to link prediction, the most fundamental graph problem in the AI and Web communities.
波多野 大督 （ＮＩＩ）
Lagrangian Decomposition Algorithm for Allocating Marketing Channels (AAAI’15)
本発表では，オンライン広告に関連する新しい問題の定式化とその解法について紹介する．この問題では，マッチメーカーの視点から広告媒体（TV，新聞，ウェブサイトなど）を複数の広告主に割り当てることを考える．この問題は影響最大化問題と深く関連しているが，マッチメーカーの導入はこれまで考慮されてこなかった．そこで、本研究ではマッチメーカーの観点から各広告媒体の枠が限られた状況下で各広告主が目標とする顧客数に影響を与えられるような広告媒体の割当を探すことを目的とする．この問題に対し，我々はラグランジュ分解に基づくアルゴリズムを提案する．また評価実験により，提案アルゴリズムは，既存アルゴリズムより良質な解が得られること，1000万頂点のグラフまで拡張できること，そして，並列化により効率的に問題を解けることを示す．
In this paper, we formulate a new problem related to the well-known influence maximization in the context of computational advertising. Our new problem considers allocating marketing channels (e.g., TV, newspaper, and websites) to advertisers from the view point of a match maker, which was not taken into account in previous studies on the influence maximization. The objective of the problem is to find an allocation such that each advertiser can influence some given number of customers while the slots of marketing channels are limited. We propose an algorithm based on the Lagrangian decomposition. We empirically show that our algorithm computes better quality solutions than existing algorithms, scales up to graphs of 10M vertices, and performs well particularly in a parallel environment.
吉田 悠一 （ＮＩＩ）
Distributed Multiplicative Weights Methods for DCOP (AAAI’15)
本研究では，分散制約最適化問題に対して乗算型重み更新法を利用したアルゴリズムを二つ提案する．一つは線形計画問題に基づくアルゴリズムで，得られる解は線形緩和の最適解に収束する．もう一つはゲームに基づくアルゴリズムで，得られる解は粗い相関均衡に収束する．実験により，提案手法が既存の非厳密手法より良質な解を効率的に得ることを示す．
In this work, we propose two algorithms for distributed constraint optimization problems that exploits the multiplicative weights method. The first one is based on linear programming, and the obtained solution converges to an LP optimum. The second one is based on cost-minimization game, and the obtained solution converges to a coarse correlated equilibrium. We experimentally demonstrate that our methods outperform existing non-exact algorithms in terms of solution quality and efficiency.
Marcel Roeloffzen （ＮＩＩ）
A linear-time algorithm for the geodesic center of a simple polygon (SOCG’15)
Let $P$ be a closed simple polygon with $n$ vertices.
For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $P$. The geodesic center of $P$ is the unique point in $P$ that minimizes the largest geodesic distance to all other points of $P$. In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an $O(n\log n)$-time algorithm that computes the geodesic center of $P$.
Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]).
In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
高口 太朗 （ＮＩＩ）
Sufficient conditions of endemic threshold on metapopulation networks
（Journal of Theoretical Biology）
ネットワーク上の感染症伝播に関して、感染力の閾値は最も重要な量の１つである。一般のネットワークに対して感染閾値を解析的に求めることは困難なので、より良い精度で推定することが重要となる。本発表では、従来ネットワーク構造についての近似を基に与えられていた感染閾値の上界が任意のネットワークについて成り立つことを示す。また、現実のネットワークによく見られる性質に注目することにより、より精度のよい上界を与える。
In this talk, sufficient conditions of the endemic threshold of epidemic process on networks are theoretically studied. We prove that the sufficient condition based on mean-field approximation holds true for arbitrary networks. We also give an improved upper bound in case the network exhibits so-called rich-club property, which is often observed in empirical complex networks.
佐藤 一誠 （東京大学）
Latent Dirichlet allocation (LDA)の汎化能力の高い決定論的学習アルゴリズムとして，0次周辺化変分ベイズ法が知られている。
0次周辺化変分ベイズ法の欠点として，非常に多くのメモリを消費することが挙げられている。
本研究では，LDAの0次周辺化変分ベイズ法を確率的情報量最小化問題として定式化することでこれらの問題を解決する。
The collapsed variational Bayes zero (CVB0) inference is known as a deterministic learning algorithm with high generalization ability for latent Dirichlet allocation.
A drawback of the CVB0 inference is the memory requirements.
We reformulate the CVB0 inference by using the stochastic divergence minimization problem, which can reduce the memory requirements.
則 のぞみ （京都大学）
Simultaneous Modeling of Multiple Diseases for Mortality Prediction in Acute Hospital Care (KDD’15)
集中治療室（ICU）入室患者の死亡リスク予測問題は，死亡リスクの高い患者にアラートを出すといった診療支援への応用等にも繋がる重要な問題である．これまでも死亡リスク予測のための様々なモデルが探求されてきたが，従来は“疾病によって死亡リスクを説明するルールが異なる”というような “ 疾病コンテキスト”が考慮されてこなかった．本研究ではICU入室患者の死亡リスク予測における疾病コンテキストを考慮するために，リスク予測問題を疾病を単位としたマルチタスク学習として定式化する．特に，疾病ごとに個別化した予測モデルの構築にあたって課題となるデータの疎性に対処するために，疾病の分類と電子健康記録（Electronic Health Record: EHR）の分類に関するドメイン知識を正則化項により取り込む．医療機関における実データを用いた実験により提案手法の有効性を示す．
One of the salient features of ICU is the diversity of patients: clinicians are faced by patients with a wide variety of diseases at a time. However, mortality prediction for ICU patients has typically been conducted by constructing one common predictive model for all the diseases. In this paper, we incorporate disease-specific contexts into mortality modeling by formulating the mortality prediction problem as a multi-task learning problem where a task corresponds to a disease. Our method effectively incorporates medical domain knowledge relating to the similarity among diseases and the similarity among Electronic Health Records (EHRs) into a data-driven approach by incorporating graph Laplacians into the regularization term to encode these similarities. Using a real dataset from a hospital, we show the effectiveness of our proposed method.
鈴木 大慈 （東京工業大学）
Convergence rate of Bayesian tensor estimator and its minimax optimality (ICML’15)
低ランクテンソルのベイズ推定量について考察し，その予測誤差の収束レートを導出する．また，低ランクテンソル推定におけるミニマックス最適レートを導出する．問題設定として回帰係数が低ランクテンソルである回帰問題を考える．このような問題は応用上様々な問題に現れる．
我々の解析は，予測誤差に注目しているためデザインの（制限）強凸性が必要ないという点で特徴的である．
また，解析より真のランクを知らなくてもそれに応じた適応的な推定が可能であることが示される．
さらにテンソル推定の予測誤差についてそのミニマックス最適レートを導出し，上で導いた結果がほぼミニマックスレートを達成することを示す．
We investigate the statistical convergence rate of a Bayesian low-rank tensor estimator, and derive the minimax optimal rate for learning a low-rank tensor. Our problem setting is the regression problem where the regression coefficient forms a tensor structure.
The convergence rate of the Bayes tensor estimator is analyzed in terms of both in-sample and out-of-sample predictive accuracies. It is shown that a fast learning rate is achieved without any strong convexity of the observation. Moreover, we show that the method has adaptivity to the unknown rank of the true tensor.
Finally, we show the minimax optimal learning rate for the tensor estimation problem, and thus show that the derived bound of the Bayes estimator is tight and actually near minimax optimal.
平原 秀一 （東京大学）
Identifying an honest EXP^NP oracle among many (CCC’15)
関数fに対する選択者という概念を定式化することにより、短いアドバイスを除去するための一般的な枠組みを与える。少なくとも一方は正直である（すなわち、fを正しく計算する）ような二つのオラクルと、入力xが与えられる。選択者の仕事は、それらのオラクルの助けを借りて乱択多項式時間でf(x)を正しく計算することである。 選択者の概念によって短いアドバイスを除去できるという性質を特徴付ける。すなわち、水増し可能な問題に対して選択者が存在することと、任意の相対化された世界において、その問題を解く確率的機械に与えられた短いアドバイスが除去できることが同値となることを示す。
これまでは、個例検査器が短いアドバイスを除去するために用いられてきた。個例検査器の存在は、アドバイスを除去するための性質よりも強い性質であることを示す。具体的には、個例検査器は(EXP^NP = NEXPでない限り)EXP^NP完全問題に対しては存在しないが、EXP^NP完全問題に対する選択者が存在することを示す。
We provide a general framework to remove short advice by formulating the following computational task for a function f: given two oracles at least one of which is honest (i.e. correctly computes f on all inputs) as well as an input, the task is to compute f on the input with the help of the oracles by a probabilistic polynomial-time machine, which we shall call a selector. We characterize the languages for which short advice can be removed by the notion of selector: a paddable language has a selector if and only if short advice of a probabilistic machine that accepts the language can be removed under any relativized world.
Previously, instance checkers have served as a useful tool to remove short advice of probabilistic computation. We indicate that existence of instance checkers is a property stronger than that of removing short advice: although no instance checker for EXP^NP-complete languages exists unless EXP^NP = NEXP, we prove that there exists a selector for any EXP^NP-complete language, by building on the proof of MIP = NEXP by Babai, Fortnow, and Lund (1991).
山口 勇太郎 （東京大学）
Finding a Path in Group-Labeled Graphs with Two Labels Forbidden (ICALP’15)
群ラベル付きグラフにおける$s$–$t$パスのラベルがちょうど2種類となる必要十分条件を示す．
また，その特徴付けに基づき，群ラベル付きグラフにおいて，2つのラベルを禁止して$s$–$t$パスを見つける多項式時間アルゴリズムを与える．
この問題は，無向グラフにおける2点素パス問題の一般化にもなっている．
We give a necessary and sufficient condition for a group-labeled graph to have exactly two possible labels of $s$–$t$ paths.
Based on this characterization, we also provide a polynomial-time algorithm to find an $s$–$t$ path in a group-labeled graph with two labels forbidden.
This problem in fact generalizes the 2-disjoint paths problem in undirected graphs.
小関 健太 （ＮＩＩ）
Spanning closed walks and TSP in 3-connected planar graphs
（Journal of Combinatorial Theory, Series B 2014.）
4-connected projective-planar graphs are Hamiltonian-connected
（Journal of Combinatorial Theory, Series B 2015.）
閉曲面上のグラフのハミルトン性に関しては，
Tutte による 「任意の 4-連結平面グラフはハミルトン閉路を持つ」 という結果以来，様々な拡張がなされてきたが，その一方で関連する予想も残されている．
この一連の研究で，以下の二つの予想を解決した．
[1] 任意の 4-連結射影平面グラフはハミルトン連結である (Dean の予想)
[2] 任意の 3-連結平面グラフ G は長さ 4|G|/3 以下の全域閉歩道を持つ (Goemans の予想)
Tutte showed that every 4-connected planar graph is Hamiltonian.
Since then, many researchers have investigated the Hamiltonicity of graphs on surfaces,but, there still remain some related interesting conjectures.
In this talk, we give positive solutions to two of such conjectures.
[1] Every 4-connected graph on the projective plane is Hamiltonian-connected. (Dean’s conjecture)
[2] Every 3-connected planar graph G has a spanning closed walk of length 4|G|/3. (Goemans’ conjecture)
河原林 健一 （ＮＩＩ）
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time (STOC’15)
本論文では、シンプルグラフの辺連結度をほぼ線形で計算する「決定的アルゴリズム」を与えている。
現在までのベストな結果は、STOC’91のGABOWによるもので、O(m+k^2n)時間必要になっていた（kは最悪nである）。
STOC’96において、Kargerは、グラフ辺連結度に関して、ほぼ線形時間のモンテカルロ乱拓アルゴリズムを与えた。しかしながらこのアルゴリズムからでは、最小カットであることの「certificate」は残念ながらできなかった。その点で「決定的アルゴリズム」は、はるかに強い帰結を与えている。
We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem.
The previous fastest deterministic algorithm by Gabow from STOC’91 took ~O(m+k^2 n), where k is the edge connectivity, but k could be Omega(n).
At STOC’96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow’s slower deterministic algorithm and compare sizes.
The Directed Grid Theorem (STOC’15)
1986年に発表されたundirected graphの「グリッド定理」は、グラフマイナー理論の根幹であり、現在でも多くの応用が計算機科学、数学の両分野で発見されている。
しかしながらdirected graphに関するグリッド定理は、20年前から、Alon, Reed, Robertson, Seymour, Thomasによって提唱された大きな未解決問題であった。
本論文ではこの予想を完全解決している。
The grid theorem, originally proved by Robertson and Seymour in Graph Minors V in 1986, is one of the most central results in the study of graph minors.
However, the corresponding theorem for directed graphs is much harder.
In fact, 20 years ago, Alon, Reed, Robertson, Seymour, Thomas have conjectured that this is possible. The main result is to confirm this conjecture.
Beyond the Euler Characteristic: Approximating the Genus of General Graphs (STOC’15)
グラフの種数を求める問題（どの曲面に埋め込めるか？）は、グラフ理論、離散幾何においても重要な問題である。
しかしながらこの問題は、非常に難しい問題であることが知られている。実際NP－困難であることは知られているが（Thomassen ’89）、そのほかはほとんど何も知られていない。
本論文では、まったくTRIVIALでない近似アルゴリズムを初めて与えた。
Computing the Euler genus of a graph is a fundamental problem in graph theory and topology. It has been shown to be NP-hard by [Thomassen ’89] and a linear-time fixed-parameter algorithm has been obtained by [Mohar ’99].
Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of O(1)-approximation is not ruled out, the currently best-known upper bound is a trivial O(n/g) -approximation that follows from bounds on the Euler characteristic. In this paper, we give the first non-trivial approximation algorithm for this problem.
