Questions to answer
 Efficient Search / Solving
 Interpretability / Explainability
– Shapley on node, subgraph, hierarchical graph, coupled networks.
1. XAI
General XAI
 CSUR A Survey of Methods for Explaining Black Box Models / Extension
– Excellent benchmarking and survey  2021 Explaining Deep Neural Networks and Beyond: A Review of Methods and Applications
 2021 Pattern Recognition Towards robust explanations for deep neural networks  ScienceDirect
– Minimize Hessian to stabilize local change  NIPS 21 Towards MultiGrained Explainability for Graph Neural Networks  OpenReview
– multigrained, may relate to hierarchical explaination  NIPS 21 Robust Counterfactual Explanations on Graph Neural Networks
– robust explainatin 
Peeking Inside the BlackBox: A Survey on Explainable Artificial Intelligence (XAI)  IEEE Journals & Magazine  IEEE Xplore
– see table 2, a 2018 paper, but with 2k+ citation  [2011.07876] A Survey on the Explainability of Supervised Machine Learning
 Explainable Machine Learning for Scientific Insights and Discoveries  IEEE Journals & Magazine  IEEE Xplore
 [2010.10596] Counterfactual Explanations for Machine Learning: A Review
 Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI  ScienceDirect

ConstraintDriven Explanations of BlackBox ML Models  OpenReview
– see related work only, not a good paper
Alternative for Shapley

If You Like Shapley Then You’ll Love the Core  Proceedings of the AAAI Conference on Artificial Intelligence
– core  Sobol index: easy to calculate
– [KDD question] Shap values vs Sobol indices? · Issue #1382 · slundberg/shap · GitHub
– https://artowen.su.domains/reports/sobolshapley.pdf  cooperative game theory
 sensitivity analysis
 uncertainty quantification
XAI for Graphs
 AI Stat 22 [2102.03322] CFGNNExplainer: Counterfactual Explanations for Graph Neural Networks
– counterfactual explaination for GNN  WWW 22 [2202.08816] Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning
– counterfactual and factual 
[2201.12380] Explaining Graphlevel Predictions with Communication StructureAware Cooperative Games
– rethink alternatives for Shapley value which does not model structural info 
[2203.09258] Explainability in Graph Neural Networks: An Experimental Survey
– a survey paper 
[2111.10037] Explaining GNN over Evolving Graphs using Information Flow
– evolving graph w/ info flow 
FlowX: Towards Explainable Graph Neural Networks via Message Flows  OpenReview
– msg flow of NN 
[2104.10482] GraphSVX: Shapley Value Explanations for Graph Neural Networks
– Shapley value 
[2006.03589] HigherOrder Explanations of Graph Neural Networks via Relevant Walks
– higherorder explanation for GNN
XAI for IM

http://ceurws.org/Vol1893/Paper2.pdf
– not a very good paper, but worth reading
2. Combinatorial Optimization
Basis
Simplex
Network Simplex
 Exploring the Network Simplex Method  CU Denver Optimization Student Wiki
 MIT slides
 Book: network simplex algorithm
integer linear programming (ILP) / mixed linear programming (MIP)
(no work reported to use GNN to handle ILP, but some for MIP)
Stochastic Combinatorial Optimization
 2009 https://link.springer.com/article/10.1007/s1104700890984 (833)
 2015 A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems  ScienceDirect (389)
CO+ML
 CO and ML tutorial / Author Page
 Survey CO w/ GNN: Combinatorial Optimization and Reasoning with Graph Neural Networks  IJCAI [ Journal ]
 Survey [2103.16378] EndtoEnd Constrained Optimization Learning: A Survey
– unsupervised  Survey [2107.01188] Combinatorial Optimization with PhysicsInspired Graph Neural Networks
 Survey IJCAI 20 [2003.00330] Graph Neural Networks Meet NeuralSymbolic Computing: A Survey and Perspective
– Symbolic  IEEE Access 2020: Learning Combinatorial Optimization on Graphs: A Survey With Applications to Networking  IEEE Journals & Magazine  IEEE Xplore (42)
 EJOR 2021: Machine learning for combinatorial optimization: A methodological tour d’horizon  ScienceDirect (476)
 Arxiv 2021: [2102.09544] Combinatorial optimization and reasoning with graph neural networks (51)
 Arxiv 2020: [2011.06069] Ecole: A Gymlike Library for Machine Learning in Combinatorial Optimization Solvers (12)
 NIPS 2017: Learning Combinatorial Optimization Algorithms over Graphs (791)
 NIPS 2018: Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search (238)
 NIPS 2019: Exact Combinatorial Optimization with Graph Convolutional Neural Networks (148)
 NIPS 2019: Learning to Perform Local Rewriting for Combinatorial Optimization (112)
 NIPS 2019: Approximation Ratios of Graph Neural Networks for Combinatorial Problems (54)
 NIPS 2019 End to end learning and optimization on graphs (38)
 NIPS 2020: A Combinatorial Perspective on Transfer Learning (2)
 NIPS 2020: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs (23)
 NIPS 2020: GCOMB: Learning Budgetconstrained Combinatorial Algorithms over Billionsized Graphs (15)
 NIPS 2021: USCOSolver: Solving Undetermined Stochastic Combinatorial Optimization Problems (0)
The randomness in the configuration. Given a weighted graph, finding the IM seed set is deterministic.  NIPS 2021: Matrix encoding networks for neural combinatorial optimization (1)
 NIPS 2021: A BiLevel Framework for Learning to Solve Combinatorial Optimization on Graphs (2)
 NIPS 2021 Learning Hard Optimization Problems: A Data Generation Perspective
3. IM with Linear Optimization
Recent IM
 NIPS 2019 Adaptive Influence Maximization with Myopic Feedback
Adaptive IM greedy algorithm. Approximation ratio.  NIPS 2020 https://papers.nips.cc/paper/2020/hash/4ee78d4122ef8503fe01cdad3e9ea4eeAbstract.html
Distributionally robust optimization  NIPS 2020 https://papers.nips.cc/paper/2020/hash/0d352b4d3a317e3eae221199fdb49651Abstract.html
Online IM where weight is unknown. Use multiarmed bandit.  NIPS 2021 https://papers.nips.cc/paper/2021/hash/58ec72df0caca51df569d0b497c33805Abstract.html
 ICML 2019 https://proceedings.mlr.press/v97/kalimeris19a.html
robust optimization. ML not involved.  ICML 2020 Budgeted Online Influence Maximization
Reduce to set cover problem. Multibandit.  ICML 2021 Network Inference and Influence Maximization from Samples
Network infusion.
Formulate as (linear) optimization
 https://link.springer.com/article/10.1007/s40998019001787
 https://link.springer.com/article/10.1007/s1010702001507z
 https://link.springer.com/article/10.1007/s13278020007040
 https://www.sciencedirect.com/science/article/pii/S0020025519306504
 http://www.optimizationonline.org/DB_FILE/2020/06/7838.pdf
https://myrelated.work/t/awesomenetworkpropagation/188
TBD
 https://arxiv.org/abs/2104.14516
 https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.046204
 https://proceedings.neurips.cc/paper/2019/file/8bd39eae38511daad6152e84545e504dPaper.pdf
Meta Learning
https://arxiv.org/abs/2103.00137
the influence maximization problem [KKT03] have similarity with the Max Cover problem.