Interpretable CO for IM

[Oates9895]

Questions to answer

1. Efficient Search / Solving
2. 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 Multi-Grained Explainability for Graph Neural Networks | OpenReview
  – multi-grained, may relate to hierarchical explaination
• NIPS 21 Robust Counterfactual Explanations on Graph Neural Networks
  – robust explainatin
• Peeking Inside the Black-Box: 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
• Constraint-Driven Explanations of Black-Box ML Models | OpenReview
  – see related work only, not a good paper

GitHub - wangyongjie-ntu/Awesome-explainable-AI: A collection of research...

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] CF-GNNExplainer: 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 Graph-level Predictions with Communication Structure-Aware 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] Higher-Order Explanations of Graph Neural Networks via Relevant Walks
  – higher-order explanation for GNN

XAI for IM

• http://ceur-ws.org/Vol-1893/Paper2.pdf
  – not a very good paper, but worth reading

---

2. Combinatorial Optimization

Basis

Simplex

• Chapter 29 Introduction to Algorithms - Wikipedia
• 线性规划-单纯形算法详解 | 细语呢喃

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)

• [2012.13349] Solving Mixed Integer Programs Using Neural Networks | Blog

Stochastic Combinatorial Optimization

• 2009 https://link.springer.com/article/10.1007/s11047-008-9098-4 (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] End-to-End Constrained Optimization Learning: A Survey
  – unsupervised
• Survey [2107.01188] Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Survey IJCAI 20 [2003.00330] Graph Neural Networks Meet Neural-Symbolic 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 Gym-like 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 Budget-constrained Combinatorial Algorithms over Billion-sized Graphs (15)
• NIPS 2021: USCO-Solver: 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 Bi-Level 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/4ee78d4122ef8503fe01cdad3e9ea4ee-Abstract.html
  Distributionally robust optimization
• NIPS 2020 https://papers.nips.cc/paper/2020/hash/0d352b4d3a317e3eae221199fdb49651-Abstract.html
  Online IM where weight is unknown. Use multi-armed bandit.
• NIPS 2021 https://papers.nips.cc/paper/2021/hash/58ec72df0caca51df569d0b497c33805-Abstract.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. Multi-bandit.
• ICML 2021 Network Inference and Influence Maximization from Samples
  Network infusion.

Formulate as (linear) optimization

• https://link.springer.com/article/10.1007/s40998-019-00178-7
• https://link.springer.com/article/10.1007/s10107-020-01507-z
• https://link.springer.com/article/10.1007/s13278-020-00704-0
• https://www.sciencedirect.com/science/article/pii/S0020025519306504
• http://www.optimization-online.org/DB_FILE/2020/06/7838.pdf

https://myrelated.work/t/awesome-network-propagation/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/8bd39eae38511daad6152e84545e504d-Paper.pdf

Meta Learning

https://arxiv.org/abs/2103.00137

the influence maximization problem [KKT03] have similarity with the Max Cover problem.