Message passing neural networks (MPNN) have seen a steep rise in popularity since their introduction as generalizations of convolutional neural networks to graph structured data, and are now considered state-of-the-art tools for solving a large variety of graph-focused problems. We study the generalization error of MPNNs in graph classification and regression. We assume that graphs of different classes are sampled from different random graph models. We show that, when training a MPNN on a dataset sampled from such a distribution, the generalization gap increases in the complexity of the MPNN, and decreases, not only with respect to the number of training samples, but also with the average number of nodes in the graphs. This shows how a MPNN with high complexity can generalize from a small dataset of graphs, as long as the graphs are large. The generalization bound is derived from a uniform convergence result, that shows that any MPNN, applied on a graph, approximates the MPNN applied on the geometric model that the graph discretizes.

In this Appendix we provide additional details about the MSLR-WEB30K data and the experimental protocol that we followed, we prove Lemma 11 of the main paper, and we show additional results on the MSLR-WEB30K and the simulated data.

We study the problem of off-policy evaluation from batched contextual bandit data with multidimensional actions, often termed slates. The problem is common to recommender systems and user-interface optimization, and it is particularly challenging because of the combinatorially-sized action space. Swaminathan et al. (2017) have proposed the pseudoinverse (PI) estimator under the assumption that the conditional mean rewards are additive in actions. Using control variates, we consider a large class of unbiased estimators that includes as specific cases the PI estimator and (asymptotically) its self-normalized variant. By optimizing over this class, we obtain new estimators with risk improvement guarantees over both the PI and the self-normalized PI estimators.

Feature importance (FI) estimates are a popular form of explanation, and they are commonly created and evaluated by computing the change in model confidence caused by removing certain input features at test time. For example, in the standard Sufficiency metric, only the top-k most important tokens are kept. In this paper, we study several under-explored dimensions of FI explanations, providing conceptual and empirical improvements for this form of explanation. First, we advance a new argument for why it can be problematic to remove features from an input when creating or evaluating explanations: the fact that these counterfactual inputs are out-of-distribution (OOD) to models implies that the resulting explanations are socially misaligned. The crux of the problem is that the model prior and random weight initialization influence the explanations (and explanation metrics) in unintended ways.

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing--aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by the WeisfeilerLehman (1-WL) test. Recently, researchers extended 1-hop message passing to K-hop message passing by aggregating information from K-hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of K-hop message passing. In this work, we theoretically characterize the expressive power of K-hop message passing.

A.1 Proof of Proposition 12 Proposition 1 The historical contrastive instance discrimination (HCID) can be modelled as a3 maximum likelihood problem optimized via Expectation Maximization.4 Maximum likelihood (ML) is a concept to describe the theoretic insights of clustering algorithms.6 PN n=1 Z(kn) = 1), and the last step of derivation13 employs Jensen's inequality [6, 7, 4]. Z(kn) log p(xq,kn; θE) (5) Expectation step focuses on estimating the posterior probability p(kn; xq,θE). We first gener-17 ate keys by a historical encoder: kt mn = Et m(xt), and xt Xtgt. Then, We calculate18 p(kn; xq,θE) = p(kt mn; xq,θE) = 1 (xq,kt mn), where 1 (xq,kt mn) = 1 if both belong to the19 positive pair; otherwise, 1 (xq,kt mn) = 0.20 Please note the notation "t m" shows that the k is encoded by a historical encoder.21