Timezone: »
We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under randomly missing observations. Proper PAC learnability under the Discrete-Time Linear Threshold (DLT) and Discrete-Time Independent Cascade (DIC) models is established by reducing incomplete observations to complete observations in a modified graph. Our improper PAC learnability result applies for the DLT and DIC models as well as the Continuous-Time Independent Cascade (CIC) model. It is based on a parametrization in terms of reachability features, and also gives rise to an efficient and practical heuristic. Experiments on synthetic and real-world datasets demonstrate the ability of our method to compensate even for a fairly large fraction of missing observations.
Author Information
Xinran He (USC)
Ke Xu (USC)
David Kempe (USC)
Yan Liu (University of Southern California)
More from the Same Authors
-
2022 : A Synthetic Limit Order Book Dataset for Benchmarking Forecasting Algorithms under Distributional Shift »
Defu Cao · Yousef El-Laham · Loc Trinh · Svitlana Vyetrenko · Yan Liu -
2022 Poster: Sparse Interaction Additive Networks via Feature Interaction Detection and Sparse Selection »
James Enouen · Yan Liu -
2022 Poster: Counterfactual Neural Temporal Point Process for Estimating Causal Influence of Misinformation on Social Media »
Yizhou Zhang · Defu Cao · Yan Liu -
2021 Poster: VigDet: Knowledge Informed Neural Temporal Point Process for Coordination Detection on Social Media »
Yizhou Zhang · Karishma Sharma · Yan Liu -
2020 Poster: Multi-agent Trajectory Prediction with Fuzzy Query Attention »
Nitin Kamra · Hao Zhu · Dweep Trivedi · Ming Zhang · Yan Liu -
2020 Poster: How does This Interaction Affect Me? Interpretable Attribution for Feature Interactions »
Michael Tsang · Sirisha Rambhatla · Yan Liu -
2019 Workshop: Learning with Temporal Point Processes »
Manuel Rodriguez · Le Song · Isabel Valera · Yan Liu · Abir De · Hongyuan Zha -
2018 Poster: Neural Interaction Transparency (NIT): Disentangling Learned Interactions for Improved Interpretability »
Michael Tsang · Hanpeng Liu · Sanjay Purushotham · Pavankumar Murali · Yan Liu -
2017 : Posters 1 »
J.P. Lewis · Housam Khalifa Bashier Babiker · Zhongang Qi · Laura Rieger · Ning Xie · Filip Dabek · Koushik Nagasubramanian · Bolei Zhou · Dieuwke Hupkes · CHUN-HAO CHANG · Pamela K Douglas · Enea Ceolini · Derek Doran · Yan Liu · Fuxin Li · Randolph Goebel -
2016 Workshop: Learning with Tensors: Why Now and How? »
Anima Anandkumar · Rong Ge · Yan Liu · Maximilian Nickel · Qi (Rose) Yu -
2016 Poster: SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling »
Dehua Cheng · Richard Peng · Yan Liu · Kimis Perros -
2014 Poster: Fast Multivariate Spatio-temporal Analysis via Low Rank Tensor Learning »
Mohammad Taha Bahadori · Qi (Rose) Yu · Yan Liu -
2014 Spotlight: Fast Multivariate Spatio-temporal Analysis via Low Rank Tensor Learning »
Mohammad Taha Bahadori · Qi (Rose) Yu · Yan Liu