  Analysing and explaining relationships between entities in a graph is a
fundamental problem associated with many practical applications. For example, a
graph of biological pathways can be used for discovering a previously unknown
relationship between two proteins. Domain experts, however, may be reluctant to
trust such a discovery without a detailed explanation as to why exactly the two
proteins are deemed related in the graph. This paper provides an overview of
the types of solutions, their associated methods and strategies, that have been
proposed for finding entity relatedness explanations in graphs. The first type
of solution relies on information inherent to the paths connecting the
entities. This type of solution provides entity relatedness explanations in the
form of a list of ranked paths. The rank of a path is measured in terms of
importance, uniqueness, novelty and informativeness. The second type of
solution relies on measures of node relevance. In this case, the relevance of
nodes is measured w.r.t. the entities of interest, and relatedness explanations
are provided in the form of a subgraph that maximises node relevance scores.
This paper uses this classification of approaches to discuss and contrast some
of the key concepts that guide different solutions to the problem of entity
relatedness explanation in graphs.
