Explaining predictions made by machine learning models is important and has attracted increased interest. The Shapley value from cooperative game theory has been proposed as a prime approach for computing feature importance towards predictions, especially for images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for graph explanation, where the task is to identify the most important subgraph and constituent nodes for graph-level predictions. We purport 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 propose a scoring function based on a new structure-aware value from the cooperative game theory called the HN value. 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 structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves over strong baselines on chemical graph property prediction, text graph sentiment classification, and synthetic subgraph detection tasks.