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, Bunkyo-ku, Tokyo, Japan.
Email: ohsaka (at) is.s.u-tokyo.ac.jp
Japanese Version

Research Interests

Algorithms, Graphs, Network Diffusion, Uncertain Graphs


  1. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. NEW!
    Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka.
    35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018).
  2. 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 tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in $$O(\mathrm{td}\cdot m)$$ time or $$O(\mathrm{td}\cdot (m+n\log n))$$ time, where $$\mathrm{td}$$ is the tree-depth of the input graph. Because any graph of tree-width $$\mathrm{tw}$$ has tree-depth 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 tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by Fomin et al.
  3. Coarsening Massive Influence Networks for Scalable Diffusion Analysis.
    Naoto Ohsaka, Tomohiro Sonobe, Sumio Fujita, and Ken-ichi Kawarabayashi.
    ACM SIGMOD International Conference on Management of Data 2017 (SIGMOD 2017) (AC Rate: 19.6%).
    Abstract Slide Code
  4. 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 real-world 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 vertex-weighted 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 speed-oriented implementation which runs in linear time with linear space and a scalability-oriented 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 real-world networks demonstrate that the proposed algorithm can scale to billion-edge graphs and reduce the graph size to up to 4%. In addition, our influence maximization framework achieves four times speed-up of a state-of-the-art D-SSA algorithm, and our influence estimation framework cuts down the computation time of a simulation-based method to 3.5%.
  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
  6. 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 real-world social networks, we demonstrate that the portfolio computed by our algorithm has a significantly better CVaR than seed sets computed by other baseline methods.
  7. Maximizing Time-Decaying Influence in Social Networks.
    Naoto Ohsaka, Yutaro Yamaguchi, Naonori Kakimura, and Ken-ichi Kawarabayashi.
    European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2016).
    Paper Slide
  8. Dynamic Influence Analysis in Evolving Networks.
    Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi.
    Proceedings of the VLDB Endowment (PVLDB 16).
    Paper Slide Code
  9. 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
  10. Efficient PageRank Tracking in Evolving Networks.
    Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi.
    ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2015) (Research track paper, AC Rate: 19.4%).
    Paper Slide
  11. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations.
    Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi.
    AAAI Conference on Artificial Intelligence (AAAI 2014) (Main technical track paper, AC Rate: 28.3%).
    Paper Slide Code
  12. 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).


Programming Contests

Fox photos taken by me