Timezone: »
Poster
Scalable Influence Estimation in Continuous-Time Diffusion Networks
Nan Du · Le Song · Manuel Gomez Rodriguez · Hongyuan Zha
Fri Dec 06 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
If a piece of information is released from a media site, can it spread, in 1 month, to a million web pages? This influence estimation problem is very challenging since both the time-sensitive nature of the problem and the issue of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with $|\Vcal|$ nodes and $|\Ecal|$ edges to an accuracy of $\epsilon$ using $n=O(1/\epsilon^2)$ randomizations and up to logarithmic factors $O(n|\Ecal|+n|\Vcal|)$ computations. When used as a subroutine in a greedy influence maximization algorithm, our proposed method is guaranteed to find a set of nodes with an influence of at least $(1 - 1/e)\operatorname{OPT} - 2\epsilon$, where $\operatorname{OPT}$ is the optimal value. Experiments on both synthetic and real-world data show that the proposed method can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence.
Author Information
Nan Du (Georgia Tech)
Le Song (Georgia Institute of Technology)
Manuel Gomez Rodriguez (Max Planck Institute for Software Systems)
Hongyuan Zha (Georgia Tech)
Related Events (a corresponding poster, oral, or spotlight)
-
2013 Oral: Scalable Influence Estimation in Continuous-Time Diffusion Networks »
Fri. Dec 6th 05:50 -- 06:10 PM Room Harvey's Convention Center Floor, CC
More from the Same Authors
-
2021 : Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning »
Jiani Huang · Ziyang Li · Binghong Chen · Karan Samel · Mayur Naik · Le Song · Xujie Si -
2021 : Large Scale Coordination Transfer for Cooperative Multi-Agent Reinforcement Learning »
Ethan Wang · Binghong Chen · Le Song -
2021 : Reinforcement Learning Under Algorithmic Triage »
Eleni Straitouri · Adish Singla · Vahid Balazadeh Meresht · Manuel Rodriguez -
2022 Poster: Counterfactual Temporal Point Processes »
Kimia Noorbakhsh · Manuel Rodriguez -
2022 Spotlight: Lightning Talks 1A-3 »
Kimia Noorbakhsh · Ronan Perry · Qi Lyu · Jiawei Jiang · Christian Toth · Olivier Jeunen · Xin Liu · Yuan Cheng · Lei Li · Manuel Rodriguez · Julius von Kügelgen · Lars Lorch · Nicolas Donati · Lukas Burkhalter · Xiao Fu · Zhongdao Wang · Songtao Feng · Ciarán Gilligan-Lee · Rishabh Mehrotra · Fangcheng Fu · Jing Yang · Bernhard Schölkopf · Ya-Li Li · Christian Knoll · Maks Ovsjanikov · Andreas Krause · Shengjin Wang · Hong Zhang · Mounia Lalmas · Bolin Ding · Bo Du · Yingbin Liang · Franz Pernkopf · Robert Peharz · Anwar Hithnawi · Julius von Kügelgen · Bo Li · Ce Zhang -
2022 Spotlight: Counterfactual Temporal Point Processes »
Kimia Noorbakhsh · Manuel Rodriguez -
2022 Poster: Uncovering the Structural Fairness in Graph Contrastive Learning »
Ruijia Wang · Xiao Wang · Chuan Shi · Le Song -
2021 Workshop: Human Centered AI »
Michael Muller · Plamen P Angelov · Shion Guha · Marina Kogan · Gina Neff · Nuria Oliver · Manuel Rodriguez · Adrian Weller -
2021 Poster: A Biased Graph Neural Network Sampler with Near-Optimal Regret »
Qingru Zhang · David Wipf · Quan Gan · Le Song -
2021 Poster: Locality Sensitive Teaching »
Zhaozhuo Xu · Beidi Chen · Chaojian Li · Weiyang Liu · Le Song · Yingyan Lin · Anshumali Shrivastava -
2021 Poster: Multi-task Learning of Order-Consistent Causal Graphs »
Xinshi Chen · Haoran Sun · Caleb Ellington · Eric Xing · Le Song -
2021 Poster: RoMA: Robust Model Adaptation for Offline Model-based Optimization »
Sihyun Yu · Sungsoo Ahn · Le Song · Jinwoo Shin -
2021 Poster: Bridging Explicit and Implicit Deep Generative Models via Neural Stein Estimators »
Qitian Wu · Rui Gao · Hongyuan Zha -
2021 Poster: Differentiable Learning Under Triage »
Nastaran Okati · Abir De · Manuel Rodriguez -
2021 Poster: Counterfactual Explanations in Sequential Decision Making Under Uncertainty »
Stratis Tsirtsis · Abir De · Manuel Rodriguez -
2021 Poster: Random Noise Defense Against Query-Based Black-Box Attacks »
Zeyu Qin · Yanbo Fan · Hongyuan Zha · Baoyuan Wu -
2021 Poster: Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning »
Jiani Huang · Ziyang Li · Binghong Chen · Karan Samel · Mayur Naik · Le Song · Xujie Si -
2020 Poster: Understanding Deep Architecture with Reasoning Layer »
Xinshi Chen · Yufei Zhang · Christoph Reisinger · Le Song -
2020 Poster: Learning to Incentivize Other Learning Agents »
Jiachen Yang · Ang Li · Mehrdad Farajtabar · Peter Sunehag · Edward Hughes · Hongyuan Zha -
2020 Poster: Network Diffusions via Neural Mean-Field Dynamics »
Shushan He · Hongyuan Zha · Xiaojing Ye -
2020 Poster: Decisions, Counterfactual Explanations and Strategic Behavior »
Stratis Tsirtsis · Manuel Gomez Rodriguez -
2020 Poster: Differentiable Top-k with Optimal Transport »
Yujia Xie · Hanjun Dai · Minshuo Chen · Bo Dai · Tuo Zhao · Hongyuan Zha · Wei Wei · Tomas Pfister -
2020 Poster: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He -
2020 Poster: Learning Strategic Network Emergence Games »
Rakshit Trivedi · Hongyuan Zha -
2020 Spotlight: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He -
2019 Workshop: Learning with Temporal Point Processes »
Manuel Rodriguez · Le Song · Isabel Valera · Yan Liu · Abir De · Hongyuan Zha -
2019 Workshop: Workshop on Human-Centric Machine Learning »
Plamen P Angelov · Nuria Oliver · Adrian Weller · Manuel Rodriguez · Isabel Valera · Silvia Chiappa · Hoda Heidari · Niki Kilbertus -
2019 Poster: Neural Similarity Learning »
Weiyang Liu · Zhen Liu · James Rehg · Le Song -
2019 Poster: Meta Architecture Search »
Albert Shaw · Wei Wei · Weiyang Liu · Le Song · Bo Dai -
2019 Poster: Exponential Family Estimation via Adversarial Dynamics Embedding »
Bo Dai · Zhen Liu · Hanjun Dai · Niao He · Arthur Gretton · Le Song · Dale Schuurmans -
2019 Poster: Teaching Multiple Concepts to a Forgetful Learner »
Anette Hunziker · Yuxin Chen · Oisin Mac Aodha · Manuel Gomez Rodriguez · Andreas Krause · Pietro Perona · Yisong Yue · Adish Singla -
2019 Poster: Retrosynthesis Prediction with Conditional Graph Logic Network »
Hanjun Dai · Chengtao Li · Connor Coley · Bo Dai · Le Song -
2019 Poster: Meta Learning with Relational Information for Short Sequences »
Yujia Xie · Haoming Jiang · Feng Liu · Tuo Zhao · Hongyuan Zha -
2018 : Manuel Gomez Rodriguez - Enhancing the Accuracy and Fairness of Human Decision Making »
Manuel Rodriguez -
2018 Poster: Learning Loop Invariants for Program Verification »
Xujie Si · Hanjun Dai · Mukund Raghothaman · Mayur Naik · Le Song -
2018 Spotlight: Learning Loop Invariants for Program Verification »
Xujie Si · Hanjun Dai · Mukund Raghothaman · Mayur Naik · Le Song -
2018 Poster: Deep Reinforcement Learning of Marked Temporal Point Processes »
Utkarsh Upadhyay · Abir De · Manuel Gomez Rodriguez -
2018 Poster: Coupled Variational Bayes via Optimization Embedding »
Bo Dai · Hanjun Dai · Niao He · Weiyang Liu · Zhen Liu · Jianshu Chen · Lin Xiao · Le Song -
2018 Poster: Enhancing the Accuracy and Fairness of Human Decision Making »
Isabel Valera · Adish Singla · Manuel Gomez Rodriguez -
2018 Poster: Learning Temporal Point Processes via Reinforcement Learning »
Shuang Li · Shuai Xiao · Shixiang Zhu · Nan Du · Yao Xie · Le Song -
2018 Spotlight: Learning Temporal Point Processes via Reinforcement Learning »
Shuang Li · Shuai Xiao · Shixiang Zhu · Nan Du · Yao Xie · Le Song -
2018 Poster: Learning towards Minimum Hyperspherical Energy »
Weiyang Liu · Rongmei Lin · Zhen Liu · Lixin Liu · Zhiding Yu · Bo Dai · Le Song -
2017 : Learning from Conditional Distributions via Dual Embeddings (poster). »
Le Song -
2017 Poster: From Parity to Preference-based Notions of Fairness in Classification »
Muhammad Bilal Zafar · Isabel Valera · Manuel Rodriguez · Krishna Gummadi · Adrian Weller -
2017 Poster: A Dirichlet Mixture Model of Hawkes Processes for Event Sequence Clustering »
Hongteng Xu · Hongyuan Zha -
2017 Poster: Predicting User Activity Level In Point Processes With Mass Transport Equation »
Yichen Wang · Xiaojing Ye · Hongyuan Zha · Le Song -
2017 Poster: Learning Combinatorial Optimization Algorithms over Graphs »
Elias Khalil · Hanjun Dai · Yuyu Zhang · Bistra Dilkina · Le Song -
2017 Spotlight: Learning Combinatorial Optimization Algorithms over Graphs »
Elias Khalil · Hanjun Dai · Yuyu Zhang · Bistra Dilkina · Le Song -
2017 Poster: Deep Hyperspherical Learning »
Weiyang Liu · Yan-Ming Zhang · Xingguo Li · Zhiding Yu · Bo Dai · Tuo Zhao · Le Song -
2017 Poster: On the Complexity of Learning Neural Networks »
Le Song · Santosh Vempala · John Wilmes · Bo Xie -
2017 Spotlight: Deep Hyperspherical Learning »
Weiyang Liu · Yan-Ming Zhang · Xingguo Li · Zhiding Yu · Bo Dai · Tuo Zhao · Le Song -
2017 Spotlight: On the Complexity of Learning Neural Networks »
Le Song · Santosh Vempala · John Wilmes · Bo Xie -
2017 Poster: Wasserstein Learning of Deep Generative Point Process Models »
Shuai Xiao · Mehrdad Farajtabar · Xiaojing Ye · Junchi Yan · Xiaokang Yang · Le Song · Hongyuan Zha -
2016 Poster: Multistage Campaigning in Social Networks »
Mehrdad Farajtabar · Xiaojing Ye · Sahar Harati · Le Song · Hongyuan Zha -
2016 Poster: Coevolutionary Latent Feature Processes for Continuous-Time User-Item Interactions »
Yichen Wang · Nan Du · Rakshit Trivedi · Le Song -
2016 Poster: Learning and Forecasting Opinion Dynamics in Social Networks »
Abir De · Isabel Valera · Niloy Ganguly · Sourangshu Bhattacharya · Manuel Gomez Rodriguez -
2015 Poster: Time-Sensitive Recommendation From Recurrent User Activities »
Nan Du · Yichen Wang · Niao He · Jimeng Sun · Le Song -
2015 Poster: Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients »
Bo Xie · Yingyu Liang · Le Song -
2015 Poster: Efficient Learning of Continuous-Time Hidden Markov Models for Disease Progression »
Yu-Ying Liu · Shuang Li · Fuxin Li · Le Song · James Rehg -
2015 Poster: COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution »
Mehrdad Farajtabar · Yichen Wang · Manuel Rodriguez · Shuang Li · Hongyuan Zha · Le Song -
2015 Oral: COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution »
Mehrdad Farajtabar · Yichen Wang · Manuel Rodriguez · Shuang Li · Hongyuan Zha · Le Song -
2015 Poster: M-Statistic for Kernel Change-Point Detection »
Shuang Li · Yao Xie · Hanjun Dai · Le Song -
2014 Poster: Active Learning and Best-Response Dynamics »
Maria-Florina F Balcan · Christopher Berlind · Avrim Blum · Emma Cohen · Kaushik Patnaik · Le Song -
2014 Poster: Learning Time-Varying Coverage Functions »
Nan Du · Yingyu Liang · Maria-Florina F Balcan · Le Song -
2014 Poster: Shaping Social Activity by Incentivizing Users »
Mehrdad Farajtabar · Nan Du · Manuel Gomez Rodriguez · Isabel Valera · Hongyuan Zha · Le Song -
2014 Poster: Scalable Kernel Methods via Doubly Stochastic Gradients »
Bo Dai · Bo Xie · Niao He · Yingyu Liang · Anant Raj · Maria-Florina F Balcan · Le Song -
2013 Poster: Robust Low Rank Kernel Embeddings of Multivariate Distributions »
Le Song · Bo Dai -
2012 Workshop: Confluence between Kernel Methods and Graphical Models »
Le Song · Arthur Gretton · Alexander Smola -
2012 Workshop: Spectral Algorithms for Latent Variable Models »
Ankur P Parikh · Le Song · Eric Xing -
2012 Poster: Learning Networks of Heterogeneous Influence »
Nan Du · Le Song · Alexander Smola · Ming Yuan -
2012 Spotlight: Learning Networks of Heterogeneous Influence »
Nan Du · Le Song · Alexander Smola · Ming Yuan -
2012 Poster: Waveform Driven Plasticity in BiFeO3 Memristive Devices: Model and Implementation »
Christian Mayr · Paul Stärke · Johannes Partzsch · Love Cederstroem · Rene Schüffny · Yao Shuai · Nan Du · Heidemarie Schmidt -
2009 Poster: Dirichlet-Bernoulli Alignment: A Generative Model for Multi-Class Multi-Label Multi-Instance Corpora »
Shuang Yang · Hongyuan Zha · Bao-Gang Hu -
2008 Poster: Convergence and Rate of Convergence of A Manifold-Based Dimension Reduction »
Andrew Smith · Xiaoming Huo · Hongyuan Zha -
2007 Poster: A General Boosting Method and its Application to Learning Ranking Functions for Web Search »
Zhaohui Zheng · Hongyuan Zha · Tong Zhang · Olivier Chapelle · Keke Chen · Gordon Sun