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.

The web ecosystem is a fast-paced environment. In this dynamic landscape, new security features are offered one after another to enhance the security and robustness of web applications and the operations they handle. This paper focuses on a fragile but still in-use security feature, text-based CAPTCHAs, that had been wildly used by web applications in the past to protect against automated attacks such as credential stuffing and account hijacking. The paper first investigates what it takes to develop automated scanners that can solve previously unseen text-based CAPTCHAs. We evaluated the possibility of developing and integrating a pre-trained CAPTCHA solver in the automated web scanning process without using a significantly large training dataset. We also perform an analysis of the impact of such autonomous scanners on CAPTCHA-enabled websites. Our analysis shows that solvable text-based CAPTCHAs on login, contact, and comment pages of websites are not uncommon. In particular, we identified over 3,100 text-based CAPTCHA websites in critical sectors such as finance, government, and health with hundreds of thousands of users. We showed that a web scanner with a pre-trained solver could solve more than 20% of previously unseen CAPTCHAs in just one single attempt. This result is worrisome considering the substantial potential to autonomously run the operation across thousands of websites on a daily basis with minimal training. The findings suggest that the integration of autonomous scanning with pre-training and local optimization of models can significantly increase adversaries' asymmetric power to launch their attacks cheaper and faster.