Welcome to my homepage !!
Naoto Ohsaka
Photo by JST ERATO Kawarabayashi Large Graph Project
Curriculum Vitae
Ph.D. student
Department of Computer Science, Graduate School of Information Science and Technology,
The University of Tokyo, Bunkyoku, Tokyo, Japan.
Email: ohsaka (at) is.s.utokyo.ac.jp
Japanese Version
Research Interests
Algorithms, Graphs, Network Diffusion, Uncertain Graphs
Publications

On the Power of TreeDepth for Fully Polynomial FPT Algorithms. NEW!
Yoichi Iwata,
Tomoaki Ogasawara,
Naoto Ohsaka.
35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018).
Abstract
There are many classical problems in P whose time complexities have not been improved over the past decades.
Recent studies of ``Hardness in P'' have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions.
To bypass this difficulty, Fomin et al. (SODA 2017) introduced the concept of fully polynomial FPT algorithms.
For a problem with the current best time complexity $$O(n^c)$$, the goal is to design an algorithm running in $$k^{O(1)}n^{c'}$$ time for a parameter $$k$$ and a constant $$c'
In this paper, we investigate the complexity of graph problems in P parameterized by treedepth, a graph parameter related to treewidth.
We show that a simple divideandconquer method can solve many graph problems, including
Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2hop Cover,
in $$O(\mathrm{td}\cdot m)$$ time or $$O(\mathrm{td}\cdot (m+n\log n))$$ time, where $$\mathrm{td}$$ is the treedepth of the input graph.
Because any graph of treewidth $$\mathrm{tw}$$ has treedepth at most $$(\mathrm{tw}+1)\log_2 n$$, our algorithms also run in $$O(\mathrm{tw}\cdot m\log n)$$ time or $$O(\mathrm{tw}\cdot (m+n\log n)\log n)$$ time.
These results match or improve the previous best algorithms parameterized by treewidth.
Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by treewidth posed by Fomin et al.

Coarsening Massive Influence Networks for Scalable Diffusion Analysis.
Naoto Ohsaka,
Tomohiro Sonobe,
Sumio Fujita, and
Kenichi Kawarabayashi.
ACM SIGMOD International Conference on Management of Data 2017 (SIGMOD 2017) (AC Rate: 19.6%).
Abstract
Slide
Code
Fueled by the increasing popularity of online social networks, social influence analysis has attracted a great deal of research attention in the past decade.
The diffusion process is often modeled using influence graphs, and there has been a line of research that involves algorithmic problems in influence graphs.
However, the vast size of today's realworld networks raises a serious issue with regard to computational efficiency.
In this paper, we propose a new algorithm for reducing influence graphs.
Given an input influence graph, the proposed algorithm produces a vertexweighted influence graph, which is compact and approximates the diffusion properties of the input graph.
The central strategy of influence graph reduction is coarsening, which has the potential to greatly reduce the number of edges by merging a vertex set into a single weighted vertex.
We provide two implementations; a speedoriented implementation which runs in linear time with linear space and a scalabilityoriented implementation which runs in practically linear time with sublinear space.
Further, we present general frameworks using our compact graphs that accelerate existing algorithms for influence maximization and influence estimation problems, which are motivated by practical applications, such as viral marketing.
Using these frameworks, we can quickly obtain solutions that have accuracy guarantees under a reasonable assumption.
Experiments with realworld networks demonstrate that the proposed algorithm can scale to billionedge graphs and reduce the graph size to up to 4%.
In addition, our influence maximization framework achieves four times speedup of a stateoftheart DSSA algorithm, and
our influence estimation framework cuts down the computation time of a simulationbased method to 3.5%.

Portfolio Optimization for Influence Spread.
Naoto Ohsaka, and
Yuichi Yoshida.
International Conference on World Wide Web (WWW 2017) (AC Rate: 17.0%).
Abstract
Paper
Slide
Motivated by viral marketing, stochastic diffusion processes that model influence spread on a network have been studied intensively. The primary interest in such models has been to find a seed set of a fixed size that maximizes the expected size of the cascade from it. Practically, however, it is not desirable to have the risk of ending with a small cascade, even if the expected size of the cascade is large. To address this issue, we adopt conditional value at risk (CVaR) as a risk measure, and propose an algorithm that computes a portfolio over seed sets with a provable guarantee on its CVaR. Using realworld social networks, we demonstrate that the portfolio computed by our algorithm has a significantly better CVaR than seed sets computed by other baseline methods.

Maximizing TimeDecaying Influence in Social Networks.
Naoto Ohsaka,
Yutaro Yamaguchi,
Naonori Kakimura, and
Kenichi Kawarabayashi.
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2016).
Paper
Slide

Dynamic Influence Analysis in Evolving Networks.
Naoto Ohsaka,
Takuya Akiba,
Yuichi Yoshida, and
Kenichi Kawarabayashi.
Proceedings of the VLDB Endowment (PVLDB 16).
Paper
Slide
Code

Monotone $$k$$Submodular Function Maximization with Size Constraints.
Naoto Ohsaka, and
Yuichi Yoshida
Annual Conference on Neural Information Processing Systems (NIPS 2015) (Poster presentation, AC Rate: 21.9%).
Paper
Poster

Efficient PageRank Tracking in Evolving Networks.
Naoto Ohsaka,
Takanori Maehara, and
Kenichi Kawarabayashi.
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2015) (Research track paper, AC Rate: 19.4%).
Paper
Slide

Fast and Accurate Influence Maximization on Large Networks with Pruned MonteCarlo Simulations.
Naoto Ohsaka,
Takuya Akiba,
Yuichi Yoshida, and
Kenichi Kawarabayashi.
AAAI Conference on Artificial Intelligence (AAAI 2014) (Main technical track paper, AC Rate: 28.3%).
Paper
Slide
Code

A Reinforcement Learning Method to Improve the Sweeping Efficiency for an Agent.
Naoto Ohsaka,
Daisuke Kitakoshi, and
Masato Suzuki.
IEEE International Conference on Granular Computing (GrC 2011).
Paper
Talks
Programming Contests

14th: ACM ICPC 2013 World Finals
Fox photos taken by me