Self-supervised graph representation learning (GRL) typically generates paired graph augmentations from each graph to infer similar representations for augmentations of the same graph, but distinguishable representations for different graphs. While effective augmentation requires both semantics-preservation and data-perturbation, most existing GRL methods focus solely on data-perturbation, leading to suboptimal solutions. To fill the gap, in this paper, we propose a novel method, Explanation-Preserving Augmentation (EPA), which leverages graph explanation for semantics-preservation. EPA first uses a small number of labels to train a graph explainer, which infers the subgraphs that explain the graph’s label. Then these explanations are used for generating semantics-preserving augmentations for boosting self-supervised GRL. Thus, the entire process, namely EPA-GRL, is semi-supervised. We demonstrate theoretically, using an analytical example, and through extensive experiments on a variety of benchmark datasets, that EPA-GRL outperforms the state-of-the-art (SOTA) GRL methods that use semantics-agnostic augmentations.

Graph Neural Networks (GNNs) are essential for processing graph-structured data and have wide applications in critical domains. The increasing use of GNNs in high-stakes scenarios requires robust explainability to ensure trust and transparency in decision-making. A common approach to explaining GNNs is to identify subgraphs, a.k.a. explanations, that significantly influence model predictions. However, this task is challenging due to the distribution shifts from the original training graphs to the explanation subgraphs, a factor that is largely overlooked in the existing research. These shifts arise because GNNs are trained on original graphs, while explanation subgraphs often differ in properties such as the number of nodes or structural patterns. As a result, GNNs may struggle to generalize to explanation subgraphs with a different distribution from its training data. In this paper, we systematically investigate the Out-Of-Distribution (OOD) problem through theoretical analysis and empirical studies. To address this challenge, we first develop a theoretical framework that formalizes the notion of explanation subgraphs through sufficiency and minimality criteria, ensuring both prediction preservation and structural compactness. Our analysis reveals a fundamental distributional disparity between explanation subgraphs and original graphs, leading to a novel concept of proxy graphs proposed in this work. Proxy graphs maintain the essential explanatory information while conforming to the original data distribution through a combination of parametric and non-parametric optimization approaches. Empirical evaluations on diverse datasets show that our method improves the quality and reliability of GNN explanations, advancing the field of GNN explainability.

This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source ($X^{d}, Y^{d}$) generated based on the joint distribution$P_{X, Y}$. The agents wish to produce a pair of discrete random variables$\left(U_{d}, V_{d}\right)$with joint distribution$P_{U_{d}, V_{d}}$, such that$P_{U_{d}, V_{d}}$converges in total variation distance to a target distribution$Q_{U, V}$. Two variations of the standard NISS scenario are considered. In the first variation, in addition to$\left(X^{d}, Y^{d}\right)$, the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with$\left(X^{d}, Y^{d}\right)$to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit$Z$, in addition to ($X^{d}, Y^{d}$). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences$X^{d}$and$Y^{d}$drawn according to a joint distribution$P_{X^{d}Y^{d}}$. The agents aim to generate outputs$U=f_{d}(X^{d})$and$V=g_{d}(Y^{d})$with a joint distribution sufficiently close in total variation to a target distribution$Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is$O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)$. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is$\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)$, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions$(f_{d}(X^{d}),g_{d}(Y^{d}))$. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.