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. Coarsening Massive Influence Networks for Scalable Diffusion Analysis. NEW!
    Naoto Ohsaka, Tomohiro Sonobe, Sumio Fujita, and Ken-ichi Kawarabayashi.
    ACM SIGMOD International Conference on Management of Data 2017 (SIGMOD 2017).
  2. 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%.
  3. Portfolio Optimization for Influence Spread.
    Naoto Ohsaka, and Yuichi Yoshida.
    International Conference on World Wide Web (WWW 2017) (AC Rate: 17.0%).
  4. 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.
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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