As machine learning becomes more widely adopted across domains, it is critical that researchers and ML engineers think about
the inherent biases in the data that may be perpetuated by the model. Recently, many studies have shown that such biases are
also imbibed in Graph Neural Network (GNN) models if the input graph is biased, potentially to the disadvantage of underserved
and underrepresented communities. In this work, we aim to mitigate the bias learned by GNNs by jointly optimizing two different
loss functions: one for the task of link prediction and one for the task of demographic parity. We further implement three different
techniques inspired by graph modification approaches: the Global Fairness Optimization (GFO), Constrained Fairness Optimization
(CFO), and Fair Edge Weighting (FEW) models. These techniques mimic the effects of changing underlying graph structures within
the GNN and offer a greater degree of interpretability over more integrated neural network methods. Our proposed models emulate
microscopic or macroscopic edits to the input graph while training GNNs and learn node embeddings that are both accurate and fair
under the context of link recommendations. We demonstrate the effectiveness of our approach on four real world datasets and show
that we can improve the recommendation fairness by several factors at negligible cost to link prediction accuracy.
more »
« less
PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous Link Prediction
Transparency and accountability have become major concerns
for black-box machine learning (ML) models. Proper explanations
for the model behavior increase model transparency and help researchers
develop more accountable models. Graph neural networks
(GNN) have recently shown superior performance in many graph
ML problems than traditional methods, and explaining them has
attracted increased interest. However, GNN explanation for link
prediction (LP) is lacking in the literature. LP is an essential GNN
task and corresponds to web applications like recommendation and
sponsored search on web. Given existing GNN explanation methods
only address node/graph-level tasks, we propose Path-based
GNN Explanation for heterogeneous Link prediction (PaGE-Link)
that generates explanations with connection interpretability, enjoys
model scalability, and handles graph heterogeneity. Qualitatively,
PaGE-Link can generate explanations as paths connecting a node
pair, which naturally captures connections between the two nodes
and easily transfer to human-interpretable explanations. Quantitatively,
explanations generated by PaGE-Link improve AUC for
recommendation on citation and user-item graphs by 9 - 35% and
are chosen as better by 78.79% of responses in human evaluation.
more »
« less
- NSF-PAR ID:
- 10464426
- Date Published:
- Journal Name:
- WWW '23: Proceedings of the ACM Web Conference 2023
- Page Range / eLocation ID:
- 3784 to 3793
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Graph Neural Networks (GNNs) have shown satisfying performance in various graph analytical problems. Hence, they have become the de facto solution in a variety of decision-making scenarios. However, GNNs could yield biased results against certain demographic subgroups. Some recent works have empirically shown that the biased structure of the input network is a significant source of bias for GNNs. Nevertheless, no studies have systematically scrutinized which part of the input network structure leads to biased predictions for any given node. The low transparency on how the structure of the input network influences the bias in GNN outcome largely limits the safe adoption of GNNs in various decision-critical scenarios. In this paper, we study a novel research problem of structural explanation of bias in GNNs. Specifically, we propose a novel post-hoc explanation framework to identify two edge sets that can maximally account for the exhibited bias and maximally contribute to the fairness level of the GNN prediction for any given node, respectively. Such explanations not only provide a comprehensive understanding of bias/fairness of GNN predictions but also have practical significance in building an effective yet fair GNN model. Extensive experiments on real-world datasets validate the effectiveness of the proposed framework towards delivering effective structural explanations for the bias of GNNs. Open-source code can be found at https://github.com/yushundong/REFEREE.more » « less
-
more » « less
In recent years, analyzing the explanation for the prediction of Graph Neural Networks (GNNs) has attracted increasing attention. Despite this progress, most existing methods do not adequately consider the inherent uncertainties stemming from the randomness of model parameters and graph data, which may lead to overconfidence and misguiding explanations. However, it is challenging for most of GNN explanation methods to quantify these uncertainties since they obtain the prediction explanation in a
post-hoc and model-agnostic manner without considering the randomness ofgraph data andmodel parameters . To address the above problems, this paper proposes a novel uncertainty quantification framework for GNN explanations. For mitigating the randomness of graph data in the explanation, our framework accounts for two distinct data uncertainties, allowing for a direct assessment of the uncertainty in GNN explanations. For mitigating the randomness of learned model parameters, our method learns the parameter distribution directly from the data, obviating the need for assumptions about specific distributions. Moreover, the explanation uncertainty within model parameters is also quantified based on the learned parameter distributions. This holistic approach can integrate with anypost-hoc GNN explanation methods. Empirical results from our study show that our proposed method sets a new standard for GNN explanation performance across diverse real-world graph benchmarks. -
Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs. GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. However, incorporating both graph structure and feature information leads to complex models and explaining predictions made by GNNs remains unsolved. Here we propose GNNEXPLAINER, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task. Given an instance, GNNEXPLAINER identifies a compact subgraph structure and a small subset of node features that have a crucial role in GNN’s prediction. Further, GNNEXPLAINER can generate consistent and concise explanations for an entire class of instances. We formulate GNNEXPLAINER as an optimization task that maximizes the mutual information between a GNN’s prediction and distribution of possible subgraph structures. Experiments on synthetic and real-world graphs show that our approach can identify important graph structures as well as node features, and outperforms alternative baseline approaches by up to 43.0% in explanation accuracy. GNNEXPLAINER provides a variety of benefits, from the ability to visualize semantically relevant structures to interpretability, to giving insights into errors of faulty GNNs.more » « less
-
Explaining machine learning models is an important and increasingly popular area of research interest. The Shapley value from game theory has been proposed as a prime approach to compute feature importance towards model predictions on images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for GNN explanation, where the task is to identify the most important subgraph and constituent nodes for GNN predictions. We claim that the Shapley value is a non-ideal choice for graph data because it is by definition not structure-aware. We propose a Graph Structure-aware eXplanation (GStarX) method to leverage the critical graph structure information to improve the explanation. Specifically, we define a scoring function based on a new structure-aware value from the cooperative game theory proposed by Hamiache and Navarro (HN). When used to score node importance, the HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, resembling message passing in GNNs, so that node importance scores reflect not only the node feature importance, but also the node structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity over strong baselines on chemical graph property prediction and text graph sentiment classification.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3543507.3583511
