Graph Neural Networks (GNNs) have emerged as powerful tools for learning over structured data, including text-attributed graphs (TAGs), which are common in domains such as citation networks, social platforms, and knowledge graphs.GNNs are not inherently interpretable and thus, many explanation methods have been proposed.However, existing explanation methods often struggle to generate interpretable, fine-grained rationales, especially when node attributes include rich natural language.In this work, we introduce GSPELL, a lightweight, post-hoc framework that uses large language models (LLMs) to generate faithful and interpretable explanations for GNN predictions.GSPELL projects GNN node embeddings into the LLM embedding space and constructs hybrid prompts that interleave soft prompts with textual inputs from the graph structure.This enables the LLM to reason about GNN internal representations and to produce natural-language explanations, along with concise explanation subgraphs.Our experiments across real-world TAG datasets demonstrate that GSPELL achieves a favorable tradeoff between fidelity and sparsity, while improving human-centric metrics such as insightfulness.GSPELL sets a new direction for LLMbased explainability in graph learning by aligning GNN internals with human reasoning.

Ehrenfeucht-Fraïssé (EF) games are a basic tool in finite model theory for proving definability lower bounds, with many applications in complexity theory and related areas. They have been applied to study various logics, giving insights on quantifier rank and other logical complexity measures. In this paper, we present an EF game to capture formula size in counting logic with a bounded number of variables. The game combines games introduced previously for counting logic quantifier rank due to Immerman and Lander, and for first-order formula size due to Adler and Immerman, and Hella and Väänänen. The game is used to prove an extension of a formula size lower bound of Grohe and Schweikardt for distinguishing linear orders, from 3-variable first-order logic to 3-variable counting logic.

Graph neural networks (GNNs) have been widely used in various domains such as social networks, molecular biology, or recommendation systems. Concurrently, different explanations methods of GNNs have arisen to complement its blackbox nature. Explanations of the GNNs’ predictions can be categorized into two types—factual and counterfactual. Given a GNN trained on binary classification into “accept” and “reject” classes, a global counterfactual explanation consists in generating a small set of “accept” graphs relevant to all of the input “reject” graphs. The transformation of a “reject” graph into an “accept” graph is called a recourse. A common recourse explanation is a small set of recourse, from which every “reject” graph can be turned into an “accept” graph. Although local counterfactual explanations have been studied extensively, the problem of finding common recourse for global counterfactual explanation remains unexplored, particularly for GNNs. In this paper, we formalize the common recourse explanation problem, and design an effective algorithm, COMRECGC, to solve it. We benchmark our algorithm against strong baselines on four different real-world graphs datasets and demonstrate the superior performance of COMRECGC against the competitors. We also compare the common recourse explanations to the graph counterfactual explanation, showing that common recourse explanations are either comparable or superior, making them worth considering for applications such as drug discovery or computational biology.

Large Language Models (LLMs) have demonstrated capabilities across a wide range of tasks, including natural language understanding, language generation and generating basic reasoning. To improve the accuracy and reliability of these models, various prompting, augmentation, and fine-tuning strategies have been employed. In this paper, we use context augmentation and Chain-of-Thought (CoT) instructions to generate legal arguments for specific landlord-tenant problems using OpenAI’s GPT-4o. We test this approach using ten hypothetical landlord-tenant scenarios, five provided by a legal aid organization, four generated with Anthropic’s Claude, and one crafted by us. We evaluate each argument for accuracy, factuality, comprehensiveness, and relevance to the scenario. This method of generating legal reasoning with LLMs offers the advantage of being verifiable by legal professionals, while also providing valuable assistance to laypersons in drafting documents such as demand letters, which can help expand access to justice.

Computationally intensive simulations have made analog circuit sizing challenging for complicated analog circuit performance characterization. Accurate yet computationally efficient data-driven models of circuit performance can potentially accelerate the design and verification process. However, as analog circuits are designed under strict functional and technology constraints, there is a scarcity of data for analog circuit performance classification, posing challenges to data-driven approaches; acquiring more data typically involves running expensive and time consuming simulations. We propose Bayesian Deep Active Learning (BDAL) to learn models using fewer simulations, by iteratively selecting a small number of informative samples to label based on the model uncertainty. Bayesian neural networks used in the BDAL framework are better able to model weight uncertainty while being sufficiently expressive to model complex circuits. Compared with the state-of-the-art approaches, the proposed BDAL method can obtain better classification performance with much fewer number of simulations. Experiments on four diverse analog circuits demonstrate BDAL can achieve significant reduction in data requirement and obtain similar performance with much less labeled data for analog circuit performance classification.