Explaining Graph Neural Networks for Node Similarity on Graphs
Authors: Daniel Daza
Cuong Xuan Chu
Trung-Kien Tran
Daria Stepanova
Michael Cochez
Paul Groth
Venue: Accepted by TMLR ()

Abstract: Similarity search is a fundamental task for exploiting information in various applications dealing with graph data, such as citation networks or knowledge graphs.
Prior work on the explainability of graph neural networks (GNNs) has focused on supervised tasks, such as node classification and link prediction. However, the challenge of explaining similarities between node embeddings has been left unaddressed.
We take a step towards filling this gap by formulating the problem, identifying desirable properties of explanations of similarity, and proposing intervention-based metrics that qualitatively assess them.
Using our framework, we evaluate the performance of representative methods for explaining GNNs, based on the concepts of mutual information (MI) and gradient-based (GB) explanations. We find that unlike MI explanations,
GB explanations have three desirable properties. First, they are actionable: selecting particular inputs results in predictable changes in similarity scores of corresponding nodes. Second, they are consistent: the effect of selecting certain inputs hardly overlaps with the effect of discarding them. Third, they can be pruned significantly to obtain sparse explanations that retain the effect on similarity scores. These important findings highlight the utility of our metrics as a framework for evaluating the quality of explanations of node similarities in GNNs.

Published in Transactions on Machine Learning Research (03/2026)
Explaining Graph Neural Networks for Node Similarity on Graphs
Daniel Daza" Vrije Universiteit Amsterdam, The Netherlands
d.dazacrue@vu.l
Cuong Xuan Chu Bosch Center for Artificial Intelligence, Germany
cuongrun..chulde.. wwt.ruaancc.huaae www.:ld...bbbb...o....
Trung-Kien Kien Tran Bosch Center for Artificial Intelligence, Germany
trungkien.tran www.
Daria Stepanova
daria. deria.stepanonn www.ssstpaaaaaaaeoo boscchhhheeebbbbb.oooooo bosch. com
Bosch Center for Artificial Intelligence, Germany
Michael Cochez
michael, cow.eess...ccccaaoooooooo
ELLIS Institute Finland & Abo Akademi University, Turku, Finland Elsevier discovery lab, Amsterdom
Paul Groth
p.l.groth@uvo.nl
University of Amsterdam, The Netherlands
Reviewed on OpenReview: https: openneeviee. net/ forum? 2DEul4zidP
Abstract
Similarity search is fundamental task for exploiting information in various applications dealing with graph data, such citation networks or knowledge graphs. Prior work on the explainability of graph neural networks (GNNs) has focused on supervised tasks, such as node classification and link prediction. However, the challenge of explaining similarities between node embeddings has boen left unaddressed. We take a step towards filling this gap by formulating the problem, identifying desirable properties of explanations similarity, and proposing intervention-bae based metrics that qualitatively assess them. Using our framework, evaluate the performance of representative methods for explaining GNNs, based on the concepts of mutual information (MI) and gradient-based (GB) explanations. We find that unlike MI explanations, GB explanations have three desirable properties. First, they are actionable: selecting particular inputs results in predictable changes in similarity scores of corresponding nodes. Second, they are consistent: the effect of selecting certain inputs hardly overlaps with the effect of discarding them. Third, they can be pruned significantly to obtain sporse explanations that retain the effect on similarity scores. These important findings highlight the utility of our metrics framework for evaluating the quality of explanations of node similarities in GNNs.
Our implementation is available at
1 Introduction
Graphs provide powerful and expressive data structure for modeling relations between objects across diverse domains, such as social networks, biological systems, and knowledge bases (Newman, 2018; Hamilton el. al., 2017a; Nickel et al., 2016; Hogan et al., 2021). Additionally, their ability to represent entities and their
* Work done during internship the Bosch Center for AT.

---

Published in Transactions on Machine Learning Research (03/2026)
GNN
Similarity coof
Explainer
Unsupervised Learning
Node Embeddings
Node Similurity
Explanation
Figure 1: ration of the problem we investigate in our work. Given nodes and a graph, unsupervised learning methods can be used to train GNN to learn node embeddings, where a score of similarity can be estimated by cosine similarity. We investigate how to create explanations for such scores, that assign values of attributions to edges in the graph. In this example, a positive influence on the similarily score is shown in blue, and negative influence is shown in red.
interactions makes them natural representation for machine learning methods that seek to learn structural patterns and use them in downstream tasks.
A fundamental problem that arises across domains is similarity search, where the goal is to identify objects that resemble a given query object according to structural or semantic notions of similarity. In particular, we are concerned with similarity search over graphs, where given a query node, the goal is to retrieve a ranked list of similar nodes. Several methods to solve this problem have been proposed in the literature, ranging from heuristic-based methods to data-driven machine lcarning methods. Hcuristics for similarity search on graphs exploit various graph statisties techniques based hashing to solve the problem (Shimomura et al., 2021; Shi et al., 2021).
Machine learning methods, on the other hand, avert the need to design handcrafted hcuristics or features. Instead, they seek to exploit domain-specific patterns in the graph to learn node representations, or embed- dings, after which similarities are captured via metrics such as cosine similarity on these representations. Graph neural networks (GNNs), in particular, have become a standard machine learning approaches that process graph-structured data (Kipf & Welling, 2017; Schlichtkrull et al., 2018; Gilmer al., 2017).
While GNNs offer several advantages due to their capacity to adapt to specific properties of the graph hand, these benefits may be compromised when interpretability becomes necessity (Burkart & Huber, 2021; Arrieta et al., 2020). Given their demonstrated effectiveness on different tasks, there are compelling motivations to explore methods for explaining their predictions (Yuan et al., 2023), which would enable applications that require accountable decision-making to leverage their predictive power.
While extensive works on explaining GNNs exist, the majority of the methods focus on supervised learning problems, where the predicted target well-defined based on some ground-truth data, as in the case of node classification (Ying et al., 2019; Luo et al., 2020; Lucic et al., 2022; Mino et al., 2022). To the best of our knowledge, the applicability of such methods to the problem of explaining node similarities remains open question.
Fig. 1 illustrates this problem, where a learning algorithm used to train a GNN for computing embeddings for nodes 1 and 2. The embeddings are used to compute the cosine similarity that we aim at explaining. The explanation consists of an attribution of values to edges, depending on their influence on the similarity score. In the example, blue edges result in increasing similarity scores and red edges result in decreasing the score. Depending the explanation method used, the effect of attribution values similarity scores be different.
Our work takes step towards understanding what it means to explain node similarity in graph neural networks. This setting differs fundamentally from the supervised tasks for which existing GNN explainers were designed (Yuan al., 2023). While prior work focuses on discrete prodictions, such as node classification or link prediction, explaining continuous similarity scores fundamentally different problem that has not been addressed by current evaluation protocols. We bridge this gap and provide the following contributions:
2

---

Published in Transactions on Machine Learning Research (03/2026)
We introduce and study the problem of explaining node similarity in GNNs, which to the best of our knowledge, has not been addressed in prior work.
Building on principles from explainable AI, we derive three criteria for explanations of node similarity, We then propose modcl-agnostic metrics that quantify these criteria by measuring how explanations behave under controlled interventions on the graph.
We retenstrate the utility of our framework by applying it to represenlative mutual-informatioo and muddent--bsed methods, yielding several important insights that demonstrate the practical benefits of our criteria and metries.
2 Related work
Similarity learning. The problem of computing node similarities on graphs has been addressed in previous methods that rely on heuristics, rather than representations learned from the data. Some examples of such methods rely on statistics of connectivity (Brin, 1998; Haveliwala, 2002), co-occurrence statistics (Jeh & Widom, 2002); meta-paths in heterogeneous networks (Sun al., 2011), and metrics for measuring structural similarities (Xu et al., 2007). Other methods employ ideas from hashing techniques to compute vector representations useful for similarity search (Gionis et al., 1999; Zadeh & Goel, 2013; Shimomura et al., 2021). Such heuristics are beneficial when they are broad enough to be applicable to different graphs. Graph neural networks, on the other hand, are able to adapt to specific signals present in the data, such as domain-specific topological properties and rich multi-modal features like text and images (Markowitz et al., 2022; Gao et al., 2020). Their demonstrated effectiveness for different tasks thus warrants an investigation on how explanations can be provided for them, in the event applications where rationales for predictions of GNNs are valuable, which is the open question we address in this work.
Unsupervised learning on graphs. In contrast to tasks like node classification or regression where labeled data is available, similarity learning is rarely accompanied by ground truth data. An alternative is concerned with learning representations that capture patterns already present in the graph (Liu et al., 2023a; Xie et al., 2023; Liu et al., 2023b). In the absence of labels that could be used for training, learning in this setting relies optimization algorithms that produce representations useful for pretext task. Examples of pretext tasks are maximizing the mutual information between different views of a graph (Velickovic et al., 2019; Sun et al., 2020; Peng et al., 2020), embedding shortest path distances (Bojchevski & Gümnemann, 2018; Frogner et al., 2019), reconstructing parts the input (Kipf & Welling, 2016; Wang et al., 2017a), or maintaining invariance with respect to small changes in the input (Thakoor et al., 2022; Xie et al., 2022b). The resulting representations can then be employed in tasks such as clustering and similarity search.
Most of the research in this area has focused studying different ways of designing pretext tasks. However, the area of explainability in unsupervised learning on graphs is underexplored (Xie et al., 2023; Tiu et al., 2023b). A recently proposed method is Agnkstig Graph Explanations (TAGE) (Xie et al., 2022a), which proposes explaining specific dimensions of embeddings obtained via unsupervised learning. The motivation for explaining embedding dimensions is transferring the explainer module of TAGE to supervised learning tasks. The performance of TAGE for generating explanations for problems where labeled data is not available, such similarity computations, has been so far left unexplored.
In our work, we focus on evaluating explanations of similarity in the unsupervised learning setting, which is the problem that has not been explored in TAGE or any prior work on unsupervised learning on graphs, and has also been acknowledged in comprehensive reviews in this area (Liu et al., 2023b; Xie et al., 2023).
Explaining graph neural networks. Graph neural networks (GNNs) are neural networks tailored to the irregular structure of graphs, that are able to learn representations of a node in a graph taking into consideration arbitrary subgraphs around it (Zhou et al., 2020; Wu et al., 2021; Ye et al., 2022). A growing number of methods have been proposed in the literature that provide explanations to predictions computed by GNNs, in the form of edges and features responsible for a prediction (Yuan al., 2023). Existing methods assume trained GNN and provide post hoc mechanisms for explaining their predictions (Ying et al., 2019;
3

---

Published in Transactions on Machine Learning Research (03/2026)
Luo et al., 2020; Duval & Malliaros, 2021; Yuan et al., 2021; Muschalik et al., 2025), propose methods that are explainable priori (Miao et al., 2022; Lee et al., 2023). Fundamentally, these methods focus on devising mechanisms for explaining supervised tasks, such as node or graph classification. In our work, we instead focus on how this problem differs from the task of node similarity, and how to evaluate such methods for the respective task.
Orthogonally, approaches for data valuation have proposed methods for identifying how "valuable" certain parts of graph (e.g., nodes edges) are for GNN, which can be defined in terms of changes to its learned weights (Chen et al., 2023); or its performance for node classification (Song et al., 2023; Chi et al., 2025). Our goal is complementary to these works: rather than studying the effect of graph components on GNN parameter updates or classification performance, we analyze how they influence the computation of individual similarity scores. This constitutes a fundamentally different, label-free setting, where similarity is a continuous quantity and standard notions of prediction correctness or task utility are not as well defined as in accuracy metrics for node classification.
More recently, Piaggesi et al. (2025) proposed metrics for evaluating the interpretability of unsupervised node embeddings. These metrics are designed to assess the semantic structure of the latent space produced by a specific representation learning method, and require ground-truth graph annotations (e.g., communities or motifs). In contrast, our objective is not to evaluate embeddings but rather to evaluate explanations of similarity scores produced by arbitrary GNNss Our metrics are model-agnostic and operate by measuring the effect of graph interventions; therefore, they quantify the quality of explanations when defined over the structure of the graph rather than the embedding space. As such, the two sets of metrics address complementary but fundamentally different questions.
Knowledge graph embeddings and entity similarity. Knowledge graph embeddings are representa- tions of entities and relation types, which are commonly trained for the link prediction task (Nickel et al., 2016; Wang et al., 2017b): Given a query entity and a relation, the embeddings are used to predict a target entity that is likely to form valid triple with the query entity and relation. KG embeddings have been applied in similarity computations via functions like cosine similarity the dot product (Liu et al., 2019; Yamada et al., 2020; Gerritse et al., 2020; Daza el al., 2021; Khan et al., 2022), which are not designed to be explainable.
Prior work has explored the problem of explainability for KG embeddings. Some methods have proposed learning embeddings with a predefined structure, such as a set of interpretable concepts (Chandrahas el al., 2020; Xie et al., 2017; Zhang et al., 2021), or via sparsity constraints (Zulaika et al., 2022). The result is an embedding space, where it is possible to identify distinct semantic regions, e-g.; "professions" "cities". This differs from the problem of grounding similarities computed between pairs of entities on known attributes of the entities, which is the focus of our work.
In several other works, given an existing set of KG embeddings trained for link prediction, explanations have taken the form of a subset of supporting triples (Zhang et al., 2019; Pezeshkpour et al., 2019; Betz et al., 2022; Rossi et al., 2022), paths (Gusmão et al., 2018), or Horn rules (Gad- (Gad-Elrab et al., 2020). While there is empirical evidence for KG embeddings being able to capture notions of similarity (Gad-Elral et al., 2020), some works have suggested that the link prediction objective is sub-optimal for this task (Ristoski & Paulheim, 2016; Cochez et al., 2017; Ristoski et al., 2019). This motivates our use of GNNs that operate directly on node features and subgraphs, which can serve as explanations for predicted similarity scores.
Another line of work (Petrova et al., 2017; 2019) focused on identifying the reasons behind the similarity of two given entities by extracting SPARQL queries, which have both entities as answers. However, unlike in our proposal, in (Petrova et al., 2017: 2019) the authors did not aim at explaining the similarity scores computed by a machine learning method, but rather exclusively relied the graph structure.
3 Learning and explaining similarities
Let G = (A,X) be a graph with n nodes, where A is an n x n adjacency matrix with A, = 1 if nodes and are connected, and 0 otherwise, and X Ruxm is feature matrix, where the i-th row x, contains the
4

---

Published in Transactions on Machine Learning Research (03/2026)
m-dimensional feature vector of the node i. In the following sections, we discuss the problems of learning representations of nodes for the similarity task, and our proposals on how similarity scores can be explained.
3.1 Learning representations for similarity
Graph neural networks have become a standard architecture for processing graph-structured data, due to their ability to incorporate arbitrary neighborhoods around node (Kipf & Welling, 2017; Gilmer et al., 2017; Xu et al., 2019; Marón et al., 2019; Corso et al., 2020). They can easily be extended to graphs with rich edge features and multimodal data (Schlichtkrull et al., 2018; Saqur & Narasimhan, 2020; Galkin et al., 2020; Ektefaie et al., 2023). Furthermore, the fact that GNNs implement an explicit function that maps node neighborhoods and features an embedding offers the opportunity for determining which parts of the input are responsible for certain output. This is desirable properly when explaining computations such as similarity scores.
A prominent example of a graph neural network is the Graph Convolutional Network (GCN) (Kipf & Welling, 2017). A single layer of the GCN implements the following propagation rule:
GCN(X, A) = a (AXO),
where Å is the normalized adjacency matrix, Á = AD 4. Let I, be the n x n identity matrix. Then A = A + In is the adjacency matrix, adding self-loops, and D is the degree matrix after adding self loops, such that D. =
E, E,A,.
The weight matrix O in Eq. contains the paramcters of the layer to be learned during training. When composing logether multiple GCN layers, we obtain a function fo(X, A) Z E Raad that maps each node and its features to embedding, conditioned on the features of nodes in its neighborhood.
We approach the problem of training a GNN to learn node embeddings from the perspective of unsupervised learning: In the absence of labeled data containing ground-trutt similarity information, we resort to methods that learn node embeddings by capturing patterns existing in the graph, such as communitics or structural roles (Hamilton et al., 2017a). The resulting node embeddings are vectors z, E Rd, with = I,... ni where such patterns are preserved by the geometry of the space. This allows us to address the problem of similarity search for given query node i, by ranking the rest of the nodes in the graph according to function such cosine similarity:
2, 22
v(i,j)
(2)
[z,
where j = 1,..., and ||z,|| is the e of z,.
Several mothods are available in the literature for unsupervised lcarning on graphs (Hamilton et al., 2017a; Liu et al., 2023b; Ju et al., 2023). Examples include Graph Autoencoders and Variational Graph Autoen- coders (Kipf & Welling, 2016), which optimize node embeddings so that they are able to reconstruct the adjacency matrix; Deep Graph Infomax (Velickovic et al., 2019), that learns node embeddings by maximizing the mutual information between them and summarized representation of the graph; and Graph Contrastive Represent ation Learning (Zhu et al., 2020), which compares different views of a node by perturbing its neigh- borhood and features.
3.2 Explaining GNNs
The success of GNNs at various tasks has been accompanied by increased interest in explaining the predictions they provide (Yuan et al., 2023). Informally, methods for explaining GNNs aim to determine i) which parts of the input graph G = [X, A) are responsible for a particular prediction, and ii) how they are responsible. The mechanisms used to answer these questions vary with each method.
A recent survey (Yuan et al., 2023) classifies methods for explaining GNNs into two main groups: instance- level and movel-level methods. Instance-level methods produce distinct explanation for particular pre-
5

---

Published in Transactions on Machine Learning Research (03/2026)
diction (such as the label predicted for specific node in the graph), while model-level methods aim to understand the behavior of the GNN under different inputs. Since we are interested in explaining similarity scores computed for specific pairs of nodes, we focus on the class of instance-level explanations.
Examples of instance-level methods are perturbation methods and gradient- based methods (Yuan et al., 2023). They represent an explanation as an assignment of values to parts of the input (for example, edges in the graph or node features), where the values indicate a degree of importance for computing the output of the GNN, we illustrate in Fig. 1. In this work, the parts of the inputs to the GNN that we consider for explanations are edges between nodes, but our discussion can be easily extended to consider node features.
Formally, we assume that we have access to an already trained GNN. The output fo(X, A) of the GNN is used to compute a prediction (X, A)), and we wish to compute an explanation for it that describes the degree of influence of an edge in a prediction. For similarity search the prediction is the cosine similarity between two specific node embeddings as defined in Eq. 2.
Explanations over edges in the graph can be defined as function that maps a prediction to matrix M E |=x* containing explanation values for each of the (non-zero) entries of the adjacency matrix. For the majority of perturbation methods, the explanation values in M lic in the interval [o, 1], and they can be interpreted as a mask, where values of 1 indicate relevant edges and 0 irrelevant ones. Gradient-basee methods, on the other hand, are unconstrained, providing explanation values over the real numbers that not only carry the magnitude with which an edge influences a prediction, but also its direction (positive or negative) via the sign of the gradient.
Given a matrix M of explanation values, subset of the edges in the graph can be selected by defining an explonation threshold t. The subset is defined by the entries in the adjacency matrix Ai such that Mi >> t. The meaning of the selected edges for an explanation of the similarity score depends on whether the matrix is interpreted as mask, or as a gradient.
Explaining node similarities. Prior work on explaining GNNss has primarily focused on supervised tasks like node classification and link prediction (Yuan et al., 2023), where the goal is to justify a discrete out label. In contrast, node similarity is a continuous, unsupervised quantity, and existing GNN explainers do not come with criteria which a good similarity explanation should satisfy. To address this gap, we revisit principles from the general explainable AI literature and adapt them to the problem of explaining similarity scores. We identify set of criteria that such explanations should meet and introduce metrics that allow us to quantitatively evaluate them.
4 Criteria for explanations of similarity
Several works in the literature have highlighted the importance of explainability in artificial intelligence systems, particularly when they face human users that could benefit from an understanding of their pre- dictions (Ras et al., 2018; Mueller et al., 2019; Miller, 2019; Arrieta, et al., 2020; Yang et al., 2023). These works define a scries of properties that explanations should have. For example, they should "produce details or reasons to make ils functioning clear or easy to understand" (Arrieta et al., 2020), they should be useful for debugging algorithms (Yang et al., 2023), they should provide answers to why questions (Miller, 2019) (e.g., why is this the similarity score?); and they should have properties such as fidelity (i.e., how much the explanation agrees with the input-output map of the prediction under explanation), low ambiguity, and low complexity, among others (Ras et. al., 2018). In the context of node similarity in GNNs, several explanation methods assign relevance value to each edge involved in the computation. We derive three criteria that such explanations should meet:
1. Actionable explanations. We can use the edges whose explanation value is above or below the threshold t to make interventions in the graph that result in a predictable effect on the original similarity score. This facilitates an understanding of the specific effect of some edges on the similarity score, and follows requirements on understanding model decisions (Miller, 2019; Arrieta et al., 2020), interactivity via interventions (Arrieta et al., 2020), model debugging (Yang et al., 2023), and fidelity (Ras et al., 2018).
6

---

Published in Transactions on Machine Learning Research (03/2026)
2. Consistent explanations. Actionability alone does not guarantee that the two sides of the threshold capture distinct explanatory behavior. An explanation can be actionable yet non-diseriminative both edges above and below a threshold t may produce the same effect (e.g., both increase similarity). Thus, explanations should be consistent: the effect of keeping edges above the threshold is distinct from the effect of discarding them. This implies that the explanations capture specific behaviors of the similarity under explanation, indicating fidelity and low ambignity (Ras al., 2018).
3. Sparse explanations. Explanations should admit principled reduction to small subsct, c.g-- selecting the smallest subset that preserves 90% of the elfect attribuled to the intervention. This does not follow from actionability or consistency, an explanation may satisfy both yet distribute its effect uniformly across many edges, making it impossible to reduce. Sparsity, therefore, captures the compressibility of an explanation while maintaining the effects that define its actionability and consistency. This leads to simpler, parsimonious explanations (Ras et al., 2018) that users can interpret (Miller, 2019).
We now introduce concrete, intervention-based metrics that operationalize these criteria and allow us to evaluate explanation methods quantitatively.
4.1 Metrics for intervention- evaluation
Given a trained GNN fo, we evaluate the properties of explanations for node similarities by measuring quantities that assess changes the similarity score, after performing interventions the graph on the basis of the explanation. More coneretely, let (i,j) be pair of nodes in the graph. Given the set of node embeddings Z fx(X, A), we select the embeddings of i and j from it and compute the cosine similarity y(i,j) as defined in Eq. 2. The explanation method is then executed on this value, which results in an explanation matrix M.
Given M, we compule two matrices M, and M, that select values above or below a threshold 4, respectively, such that
Maji = My if Mej 2 L else
(3)
M My if My & else 0,
(4)
where the threshold for G.Nexplainer is 0.5 and for Gradient Based (GB) methods.
We use these matrices to intervene in the graph, by computing the element-wise multiplication of these matrices with the adjacency matrix, and re-computing the node embeddings, which yields
Z, = f
(5)
Z, = fo (X A M&).
(6)
Given these embeddings, we then re-compute the similarity scores, which for each case we denote as ya (i, and (i,j) respectively.
Measuring actionability. Based these similarity scores, first compute a fidelity metric (Ribeiro et al., 2016), which measures the change in the similarity score after the intervention with respect to the original similarity score:
Fid, = va(i,) v(i,) Fid, = (). v(.
(7)
(8)
Positive values of Fid, and Fid, indicate an increase in similarity, negative values indicate a decrease. If either intervention produces effects a predictable direction, the explanation actionable. Importantly, Fid, and Fid, capture absolute, independent changes, and they do not reveal how the two interventions relate.

---

Published in Transactions on Machine Learning Research (03/2026)
Measuring consistency. To evaluate whether explanations induce distinct effects above vs. below the threshold, we consider only the signs of the fidelity values. For each node pair, we count a1: times where Fid, is positive; 42: times where Fid, is negative; and 6n and b2 defined similarly for Fids. We then define the Effect Overlap (EO) as the generalized Jaccard similarity between these counts:
i=l min(a,, bi)
BO
(9)
max b.)
An explanation method with an EO of zero indicates that the effect observed in Fid, is always positive, and al always negative in Fid, (or vice versa). This indicates that the effects are distinct and thus the explanations are consistent. The maximum value of EO is 1 and it occurs if the effect is always positive or always negative, leading to an undistinguishable effect. Values between 0 and 1 indicate partial overlap.
EO thus resolves a limitation of fidelity: even if both Fid, and Fid, suggest actionability, EO determines whether the two interventions imply complementary effects on node similarity.
Measuring sparsity. Sparsity evaluates whether an explanation can be reduced to smaller subset of edges while preserving the intervention effects that determine actionability and consistency. Given the explanation matrix M and the thresholded masks M, and Ma, we simulate different sparsity levels by removing a fraction s E [0, 1] of the least relevant edges: in M, we drop the smallest s-fraction of nonzero values, and in M, we drop the largest s-fraction. We then recompute the same fidelity and effect-overlap metrics across increasing values of s.
An explanation satisfies the sparsity criterion if its actionable and consistent behaviors preserved as increases, indicating that the explanatory signal can be concentrated in compact subset of edges.
5 Experiments
In our experiments, we aim to evaluate the proposed criteria and metrics in practice. To demonstrate this, we apply our framework to representative explanation methods from two major families of methods in the related work: mutual-informatio methods and gradient-based methods.
5.1
Explainability methods
5.1.1 Mutual information methods
A common approach for identifying explanations for GNNs consists of determining what edges are relevant for computing a prediction, by relying on the concept of Mutual Information (MT)(Ying et al., 2019; Luo et al., 2020; Wang et al., 2021; Miao et al., 2022). Existing works have proposed explaining a prediction y == (XX, A)) by finding a subgraph from the original graph that has high mutual information with the prediction. This implies that only region of the graph is relevant for computing prediction, whereas the rest be discarded without affecting it. This mechanism for finding explanation can be formalized by assuming that the matrix M of explanation values is sample of a random variable M with values in {0, 1), and then maximizing the mutual information between the original prediction (now a random variable Y) and the prediction after "masking" the adjacency matrix with the values in M:
max [gI[ A(x M))) M
(10)
where O indicates element-wing wise multiplication.
In practice, the problem in Eq. 10 is not tractable. Instead, an approximation leads to the problem of finding matrix that minimizes the cross-entropy loss (Ying al., 2019):
MMI == arg min - By (log
(11)
M
This problem is solved by randomly initializing My and updating it via gradient descent in the direction that minimizes the cross-entropy loss (Ying et al., 2019; Luo al., 2020; Miao et al., 2022).
8

---

Published in Transactions on Machine Learning Research (03/2026)
Interpreting the explanation matrix. Given the formulation of MI-based methods for explaining GNNs, entries of MMI with a value of 1 indicate edges that are relevant for the prediction, and 0 if they are irrelevant. When the matrix contains values in the continuous interval [0, 1], an appropriate threshold for selecting or discarding edges is then t = 0.5.
In our experiments, we employ GNNExplainer (Ying et al,, 2019) as an instance of MT methods.
5.1.2 Gradient-based methods
An early approach for identifying parts of the inputs relevant for a prediction computed by a neural network is to compute the gradient of the output with respect to the input (Simonyan et al., 2014; Shrikumar et al., 2017; Selvaraju et al., 2017; Sundararajan et al., 2017). This is motivated by the fact that the gradient indicates the direction and rate with which the outputs change with respect the inputs.
In gradient- (GB) methods, the extension of this approach to explaining GNNs is natural: the expla- nation matrix is equal to the gradient of the prediction with respect to the adjacency matrix,
MGB == V))(fo(X,A)).
(12)
Relying on the gradient alone might become problematic in deep neural networks using non-linearities like the ReLU activation function, whose derivative is zero over half of its domain. To address this issue, more advanced methods based on the gradient have been proposed, such as Guided Backpropagation (Springen- berg al., 2015), which ignores zero gradients, or Integrated Gradients (Sundararajan et al., 2017), which computes the total change from different values of the gradient, rather than relying on a single gradient.
Interpreting the explanation matrix. The values in the explanation matrix MGB are unconstriine, and they can take positive or negative values, depending on the sign of the gradient. This means that for each edge in the graph, GB explanations provide a magnitude and direction of influence. In this case, an appropriate threshold for selecting or discarding edges is 1=100 0.
When explaining predictions of node similarity, the (i.j) entry of the explanation matrix indicates i) how much the presence of an edge between nodes and j influences the similarity score, via the magnitude of the gradient, and ii) the direction of influence -positive or negative- via the sign. Unlike explanations from MT methods, note that GB explanations are therefore more fine-grained, by providing additional information about how inputs affect changes in similarity scores.
In our experiments with GB methods, we consider direct gradient computation with respect to the adjacency matrix (as defined in Eq. 12), and Integrated Gradients (Sundararajan et al., 2017).
5.2 Node embedding methods
We implement the following unsupervised methods for learning node emboddings: Graph Autoencoders (GAE) and Variational Graph Autoencoders (VGAE) (Kipf & Welling, 2016), Deep Graph Infomax
(DGT) (Velickovic al., 2019), and Graph Contrastive Representation Learning (GRACE) (Zhu et al., 2020). We use them to train a 2-layer GCN (Kipf & Welling, 2017) as defined in Eq. 1. We tune hyperparameters via grid search, selecting the values with the lowest training loss.
5.3 Datasets
We run experiments with six graph datasets of different sizes and domains: Cora, Citeseer, and Pubmed (Sen et al., 2008; Namata et al., 2012; Yang et al., 2016) are citation networks from the computer science and medical domains, where each node corresponds to a scientific publication and an edge indicates that there is a citation from one publication to another. These graphs are known to exhibit high homophily: similar nodes (such as publications within the same field) are very likely to be connected (McPherson et al., 2001).
To consider graphs with different structural propertics, we also carry out experiments with heterophilic graphs where connected nodes are not necessarily similar. Chamelcon and Squirrel are graphs obtained from Wikipedia, where each node is web page and edge denotes hyperlink between pages (Rozemberzzki
9

---

Published in Transactions on Machine Learning Research (03/2026)
Table 1: Statistics of graphs used in our experiments.
Dataset
Nodes
Edges
Features
Cora
2,708
5,429
1,433
Citeseer
3,327
4,732
3,703
Pubmed
19,717
44,338
500
Chamelcon
2,277
36,101
2,325
Actor
7,600
33,544
931
Squirrel
5,201
217,073
2,089
DBpedia50k
30,449
57,161
N/A
Table 2: Results of fidelity metrics (Fida and Fids) and effect overlap (EO, lower is better) when applying different explanation methods to multiple unsupervised learning methods and graphs. As explanation meth- ods we consider GNNExplainer (Ying et al., 2019) (MT), and two gradient-based methods based on direct computation of the gradient (GB1), and Integrated Gradients (Sundararajan et al., 2017) (GB2).
Coca
Citeacer
Pabmed
Charaeoon
Actor
Squirrel
Method
Fid.
Fidy
ED
Fid.
Firly
BD
Fid.
Fid,
EO
Fld,
Fid,
E0O
Fid,
Fid,
EO
Fid,
Fid,
EO
0.133
0.4451
0.130
0.406
0.202
0.532
0.353
0.134
0.200
0.521
0.356
0.357
GAB
GB8
0.118
-0.076
0.033
0.114
-0.026
0.129
0.236
-0.064
0.141
0.355
-0.107
0.125
0.442
-0.145
0.120
0.520
-0 -0.126
0.160
GB2
0.279
-0.067
0.013
0.306
-0.025
0.098
-0.144
0.011
0.718
-0.150
0.055
-0.392
0.008
0.755
-0.317
M1
0.103
0.039
0.501
0.156
0.001
0.397
0.140
0.149
0.502
0.311
0.103
0.540
0.102
0.176
0.506
0.363
0.399
0.450
VGAE
GB1
0.149
-0.087
0.045
0.078
-0.054
0.049
0,250
-0.121
0.008
0.412
-0.156
0.105
0.423
-0.203
0.081
0.577
-0.172
0.150
0.392
0.007
0.185
0.045
0.023
0.180
0.017
00:218
0.030
0.522
00338
0.009
-0:00
0.042
M1
0.015
0.882
0.5:46
0.009
0.029
01.088
0.061
0.008
0.152
0.322
0.441
0.539
00.009
00.00
0.552
0.142
0.162
0.561
DGI
GB1
0.218
-0.118
0.060
0.082
-0.055
0.254
-0.196
0.326
-0.009
-0,012
0.511
0.119
-0.400
GB2
0.283
00.101
0.053
0.149
-0.122
0.056
0.029
0.043
0.182
0.399
0.259
0.258
-0.057
00373
0.491
0.210
00.49
0.273
M1
0.075
0.007
0.536
0.102
0.010
0.476
0.222
0.086
0.513
0.254
0.132
0.533
0.016
-0.185
0.511
0.112
0.020
0.504
GRACE
0.142
-0.057
0.01G
0.113
40.000
0.062
-0016
0.158
-0.149
0.124
-0.622
0.155
0.253
-0.276
0.046
(392
0.155
-0.071
0.017
0.140
-0.028
0.063
0.235
-0.041
0.052
0.392
-0.164
0.055
0.012
-0.44
0.217
0.133
-0.382
0.151
et al., 2021). Actor is a graph where each node is an actor, and an edge indicates that two actors co-occur on a Wikipedia page (Tang et al., 2009). Furthermore, we also experiment with the DBpedia50k knowledge graph (Shi & Weninger, 2018), subset of the DBpedia knowledge graph (Auer al., 2007). The DBpedia50k graph does not contain node features; therefore, for this dataset we also train input node embeddings for the GNN. Statisties of all datasets is presented in Table 1.
5.4 Results
We present the results of the fidelity (Equation (7) and Equation (8)) and effect overlap (Equation (9)) metries Tables for the homophilic and heterophilic graphs, and Table for DBpodia50k. We denote GNNExplainer as MI, directly using the gradient GB1, and Integrated Gradients as GB2.
GB explanations are actionable. The values of Fid, and Fid, for GB methods show that across all unsupervised learning methods and datasets, keeping edges above the explanation threshold always results an increase of the similarity score, while keeping the edges below the threshold always results in lower score. This means that GB explanations effect on the similarity score. Relying these explanations would allow to determine what edges contribute to increase (or decrease) in the score, and to interact with them by re-computing the similarity score with the knowledge provided by the explanation. This property is not observed with GNNExplainer, where the effect of keeping edges above the threshold not clear, and certain patterns seem to depend on factors such as the model used to learn the embeddings, and the dataset. For example, for GAE and VGAE embeddings, keeping the edges above the threshold increases the similarity score more than keeping the edges below the threshold Cora and Citeseer, but the opposite happens in the remaining datasets.
actionable, they allow interventions that result in predictable
10

---

Published in Transactions on Machine Learning Research (03/2026)
Table 3: Results of fidelity metrics (Fid, and Fids) and effect overlap (EO, lower is better) when applying different explanation methods multiple unsupervised learning methods on the DBpedia50k knowledge graph.
DBpedia50k
Method
Fida
Fidg
EO
MI
0.057
-0.073
0.564
GAE
GB1
0.148
-0.190
0.050
GB2
0.149
-0.213
0.028
MI
0.059
-0.054
0.614
VGAE
GBI
0.149
-0.185
0.059
GB2
0.182
-0.187
0.037
M1
-0.035
-0.044
0.618
DGI
GB1
0.107
-0.189
0.065
GB2
0.121
-0.215
0.030
MI
-0.120
-0.002
0.541
GRACE
GB1
0.055
-0.071
0.043
GB2
0.033
-0.081
0.046
GB explanations are consistent. GB methods result in the lowest effect overlap across all learning methods and datasets. In the majority of the cases the overlap is around 0.1 or lower, indicating that the effect of keeping edges above the threshold distinct from the effect of keeping the edges below the threshold, thus showing that GB explanations are consistent. Interestingly, this behavior is not as clear when using DGI embeddings on the heterophilic datasets (Chameleon, Actor, and Squirrel), where the overlap increases. This could be an effect of how the performance of DGI degrades in heterophilic graphs (Xiao et al., 2022), lowering the quality of its embeddings in graphs with these properties and thus becoming sensitive to the interventions required to compute the fidelity and effect overlap metrics. In the case of GNNExplainer, in the majority of the cases, the effect overlap is around 0.4 or even larger than 0.5, indicating that in almost half of the cases keeping the edges above the threshold increases the score, and in the other half the score decreases. We thus cannot rely on its explanations for a consistent effect on similarity scores.
We present further extended results in Appendix A, where experiment with four additional GNN archi- tectures. These results are consistent with our prior observations, while also showing that in some cases overlap can be low while actionability is limited, indicating the importance of assessing jointly our proposed metrics for explaining node similarities.
Sparse GB explanations preserve effects. We next evaluate whether explanations preserve their prop- erties when made increasingly sparse. Since previous experiments showed that Integrated Gradients yields actionable and consistent explanations, we focus our study on this method.
To carry out this study, instead of taking all values of the explanation matrix above the threshold (as outlined in Eqs. and 4), we drop fraction 8 of the smallest values in Ma, and a fraction of the largest values Mg. where is the sparsity level taking values in the interval [o, 1]. When s 0 all values in the explanation matrix are used, and we obtain the results previously described in Table As increases, only the edges with the largest the smallest values are kept in M. and M,.
We compute the fidelity and effect overlap metrics for different values of sparsity from 0 up to 0.9 with increments of 0.1, when using GAE to learn embeddings. The results are shown in Fig. 2. We observe that the actionable and consistent properties GB explanations remain almost constant across all datasets. This implics that when obtaining GB explanations, we can further reduce the of odges the explanation by up 90%, and the different effects on the similarity scores will be preserved. This is beneficial for applications in which more compact explanation is desired.
11

---

Published in Transactions on Machine Learning Research (03/2026)
Fida
Fidn
EO
Cora
Citeseer
Pubmed
-0.5
00.5
-0.5
1.0
1.0
1.0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Sparsity
Sparsity
Sparaity
Chameleon
Actor
Squirrel
1.0
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5
-0.5
-1.0
-1.0
-1.0
0.2
0.3
0.5 Sparsity
0.1
0.7
0.8
0.9
0.0
0.1
0.3
0.4 0.5 0.6
0.8
0.9
0.0
0.1
0.2
0.5 0.6
0.7
Sparsity
Sparsity
Figure 2: Influence of sparse explanations on fidelity metrics (Fida and Fids) and effect overlap (EO), evaluated with GAE embeddings across different datascts. At zero sparsity, all edges above (or below) the explanation threshold are kept and used to compute the change in similarity scores Fid, (or Fs), as well the effect overlap (EO). Larger values of sparsity indicate the fraction of edges discarded before computing the change in similarity scores. Confidence intervals are shown indicating two standard deviations over 10 runs.
Examples. We present concrete examples of the explanations obtained by GNNExplainer and Integrated Gradients Fig. For this case study, we train node embeddings using GAE on the DBpedia50k knowledge graph (Shi & Weninger, 2018). We then select the most relevant edges according to the explanation values assigned by each method. We consider two entities in the graph: Lilium and Dendrobium, which two genera of flowering plants. Their similarity is reflected in cosine similarity value of 0.705. We denote the effect altributed to each edge with colors, with blue indicating increase in the similarity, red decrease, and gray indicating little or no effect. When we obtain explanations with GNNExplainer, we observe that a few edges increase the similarity score, and none of them are the 1-hop neighborhood of the entitios, where their similarities are apparent. Both entities belong to the Plant kingdom and the Flowering Plant division. With gradient-based explanations, we observe that edges containing this information contribute the increase of the similarity score, with the highest contributions (illustrated with the thickness of the edges) assigned to the relationships with Plant and Flowering Plant. Conversely, this analytical framework also enables the identification of specific informational elements that exert ivgative influence on the calculated similarity score, thereby facilitating diagnostic assessment of dissimilarity factors. Overall, we note that gradient-based explanations are intuitive, by indicating both the magnitude and direction in which inputs affect similarity scores.
6
Conclusion
We have studied the problem of explaining node similarities computed by graph neural networks, a setting relevant in practice but largely overlooked by prior work on GNN explainability. Building on principles from explainable AI, we introduced criteria that explanations of similarity should satisfy, and we operationalized them through intervention-based metrics. We have demonstrated the utility of our framework by applying
12

---

Published in Transactions on Machine Learning Research (03/2026)
Pitcheri
Scutellaria
Peniocereus
Cucurbitaccae
Chayote
Hippomane
Popowia
Ormosia
Lilim
Plant
Dendrobium
Lihum
Plant
Dendrobium
Flowering
Hoodia
Flowering
Hoodia
Plant
Gordonii
Plant
Gordonii
(a) GNNExplainer explanation.
(b) Gradient-basee explanation.
Figure 3: Example of explanations provided by GNNExplainer (3a) and Integrated Gradients (3b) for the similarity computed between two entities in the DBpedia50k knowledge graph: Lilium and Dendrobium, two genera of flowering plants. Edge thickness indicates magnitude, while the color of the edges associated with the score, i.e,, blue edges reflect the score increase, red edges decrease, and gray edges have little effect.
it to representative mutual-inforrmtion and gradient-based methods. Our results reveal that unlike prior results on supervised lasks like node classification (Ying el al., 2019; Luo al., 2020; Yuan et al., 2023), gradient-based methods more suitable in the setting of node similarity, by providing explanations with predictable and consistent effect of increasing or decrcasing similarity scores. Furthermore, we observe that the complexity of the explanations can be reduced while maintaining their desirable properties.
this work, we focused on evaluating explanation methods based on how graph interventions derived from them affect similarity scores. An additional important aspect be taken into account in the practical choice of an explanation method its computational complexity. Gradient-based explanations require computing the gradient of a scalar similarity score with respect. the input graph, which amounts to single backward pass through the GNN and scales linearly with the size of the graph up to constant factors. In contrast, mutual-inte www-innnootooobbiieee
methods such as GNNExplainer rely on an iterative optimization procedure that repeatedly evaluates and differentiates the GNN over multiple steps, making them strictly more expensive in practice. While computational cost was not the main focus of our empirical study, it represents an additional crilerion that may further favor gradient- based explanations in large-scale similarity search settings.
Beyond the specific methods examined here, our criteria and evaluation methodology offer general founda- tion for evaluating explanations of similarity graphs. They inform the development of new methods for node similarity, and the design of methods that are explainable priori. Moreover, based on proposed methodology, further explainers (e.g., PGExplainer Luo et al. (2020), SubgraphX Yuan et al. (2021), PGM- Explainer Vu & Thai (2020)) could be analyzed, which an interesting direction left for future rescarch.
While we focused on cosine similarity, as it is the standard choice for fast dense similarity search over learned embeddings, our proposed intervention-based metries are not specific to cosine similarity. They only require similarity function defined over node embeddings, and can be applied to alternatives such Euclidean distance without modification. The intervention logic, which measures how explanations predictably affect similarity under controlled graph perturbations, remains the same. We expect the qualitative behavior observed in our study to extend to other commonly used similarity measures without modification. We view those directions as promising avenues for future work.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Acknowledgments
For this work, Michael Cochez is partially funded by the Elsevier Discovery Lab, partially funded by the Graph-Massivizer project, funded by the Horizon Europe programme of the European Union (grant 101093202), and supported by gift from Accenture LLP. His work on this publication is in part based upon work from COST Action CA23147 GOBLIN - Global Network on Large-Scale, Cross-domain and Mul- tilingual Open Knowledge Graphs, and COST Action CA24121 Knowledge Graphs in the Era of Large Language Models (KGELL), both supported by COST (European Cooperation Science and Technology, https///ww.cost.com cost.cu). Daniel Daza performed a large portion of this work during an internship at the Bosch Center for Artificial Intelligence, Germany. Besides, he was funded by the Elsevier discovery lab and gift from Accenture LLP.
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Haru- tyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 21 29. PMLR, 09 15 Jun 2019. URL attps://proceedings mlr. wtt..mml..ereeeeeee press/v97/ abu-el-haijaa9a.hta html.
Alejandro Barredo Arricta, Natalia Díaz Rodríguez, Javier Del Scr, Adrien Bennetot, Siham Tabik, Al- berto Barbado, Salvador García, Sergio Gil-Lopez, Daniel Molina, Richard Benjamins, Raja Chatila, and Francisco Herrera. Explainable artificial intelligence (XAI): concepts, taxonomies, opportunities and challenges toward responsible Al. Inf. Fusion, 58:82 115, 2020. doi: h0..006/...nffuus2011..... https://doi. org/ 10. 1016/j inffus..u.... 20f.fuss.01..... 12.012.
URL
Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. Dbpe- dia: A nucleus for web of open data. In international semantic web conference, pp. 722 735. Springer, 2007.
Patrick Betz, Christian Meilicke, and Heiner Stuckenschmidt. Adversarial explanations for knowledge graph embeddings. In Lue De Raedt (ed.), Proceedings of the Thirty Pirst International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pp. 2820-2828 ijeai.org, 2022. doi: 10.24963 /tt/:////caai//// 2092/391. URL sttps://dole /tg///o.oogo////////// org/10. 10. 24963/1jcai.2222/339. 2022/391.
Aleksandar Bojchevski and Stephan Günnemann. Deep Gaussian embedding of graphs: Unsupervised in- ductive learning via ranking. In 6th International Conference on Learning Representations, ICLR 2018, Vancowver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https://openrevieee www.:/oormmddd 11dk-ZZ..
Sergey Brin. The pagerank cilation ranking: bringing order to the web. Proceedings of ASIS, 1998, 98: 161-172, 1998.
Nadia Burkart and Marco F. Huber. A survey on the explainability of supervisod machine learning. J. Artif. Intell. Res., 70:245 317, 2021. doi: (.11613/jair.112222 URL /tt.:hccee///o...oo//0....//////
12228.
Chandrahas, Tathagata Sengupta, Cibi Pragadeesh, and Partha Talukdar. Inducing interpretability in knowledge graph embeddings. Proceedings of the 17th International Conference on Natural Language Processing (ICON), pp. 70 75, Indian Institute of Technology Palna, Palna, India, December 2020. NLP Association of India (NLPAT). URL https: httppss//aallatttlllc/ httpa//caatttoooy..oooo wwwp:/00.o../0000...
Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. In The Eleventh International Conference on Learning Representations, 2023. URL pttpps://pperreiies net/Eforum/idd551XXyyya
14

---

Published in Transactions on Machine Learning Research (03/2026)
Hongliang Chi, Wei Jin, Charu C. Aggarwal, and Yao Ma. Precddence-oonstrained winter value for effective graph data valuation. In The Thirleenth International Conference on Learning Representations, 2025. URL
Michael Cochez, Petar Ristoski, Simone Paolo Ponzetto, and Heiko Paulheim. Global RDF vector space embeddings. In Claudia d' d'Amato, Miriam Fernández, Valentina A. M. Tamma, Freddy Lécué, Philippe Cudré-Mauroux, Juan F. Sequeda, Christoph Lange, and Jeff Heflin (eds.), The Semantic Web ISWC 2017- 16th International Semantic Web Conference, Vienna, Austria, October 21-25, 2017, Proceedings, Part 1, volume 10587 of Lecture Notes in Computer Science, pp. 190 207. Springer, 2017. doi: 10.1007/ 978-3-319-60 -1118-4-888-4 12. URL attpss///oot http:///oo.oogg////// org/o0..//0
10. 11.110.00000 1007 /978- 3-19----1---11 1--11-68288-----888-------888882
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liö, and Petar Velickovic. Principal neigh- bourhood aggregation for graph nets. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL https: https://proceediins. wwweddiinnnnnnuuuispe www.ripssccpppppr////0/ h/ahh// 99922666118822221111000000000000 Att.0//000000000000taaaatat html.
Daniel Daza, Michael Cochez, and Paul Groth. Inductive entity representations from text via link prediction. Tn Jure Leskovec, Marko Grobelník, Mare Najork, Jie Tang, and Leila Zia (eds.), WWW '21: The Web Conference 2021, Virtual Event Ljubljana, Slovenia, April 19-23, 2021, pp. 798-808 ACM / IW3C2, URL
2021. doi: 10.1145/33 44445//344288133350
3450141.
Alexandre Duval and Fragkiskos D Malliaros. GraphSVX: Shapley value explanations for graph neural networks. In Joint European conference on machine learning and knowledge discovery in databases, pp. 302 212.318.60 Springer, 2021.
Yasha Ektefaie, George Dasoulas, Ayush Noori, Maha Farhat, and Marinka Zitnik. Multimodal learning with graphs. Nat. Mac. Intell., 5(4):340-350, 2023. doi: 10.1008/442255--003000002 URL https: //doi. org/10. /tte//0.103//////
Charlic Frogner, Farzanch Mirzazadeh, and Justin Solomon. Learning emboddings into entropic Wasscrstein spaces. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, net, 2019. URL https: https:/ http://www.....toooooooooooooa..
Mohamed H. Gad-Elrab, Daria Stepanova, Trung-Kien Tran, Heike Adel, and Gerhard Weikum. Excut: Explainable embedding- based clustering over knowledge graphs. In Jeff Z. Pan, Valentina A. M. Tamma, Claudia d' A'ato, Krzysztof Janowicz, Bo Fu, Axel Polleres, Oshani Seneviratne, and Lalana Kagal (eds.), The Semantic Web ISWC 2020 19th International Semantic Web Conference, Athens, Greece, November 2-6, 2020, Proceedings, Part 1, volume 12506 of Lecture Notes in Computer Science pp. 218-237. Springer, 2020. doi:
0100//99788-000-22449 _ 13. URL https: /ttp///oi...// org/ 10.
Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. Message passing for hyper-relational knowledge graphs. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp- 7346-7359, 7359. Association for Computational Linguistics, 2020. doi: 10.18653/vv wwtp///...e./m/-//e. 596. URL attps://dol http://ddo..ogg.///// wtwpg//.....././/// 18653/v1/2020 emnlp-main. 596.
Difei Gao, Ke Li, Ruiping Wang, Shiguang Shan, and Xilin Chen. Multi-modal graph neural net- work for joint reasoning on vision and scene text. In 2020 IEEE/CVF Conference on Com- puler Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 12743-12788 Computer Vision Foundation / IEFF, 2020. doi: N..109/CVPR42000 20..00..2200027700 URL https://openaccesss thecvf. com/content. Setpiteett_tR_____ ___R__CV2022000 20w0000022//eeee Network_fod forrk_fo___oool wwwoonneeesooinnn..toee on Vision wan__vvP______ WWVPP_2020_____2___ html.
Emma Gerritso, Facgheh Hasibi, and Arjen de Vries. Graph-cmbedding empowered entity retricval. In Joemon M. Jose, Emine Yilmaz, João Magalhães, Pablo Castells, Nicola Ferro, Mário J. Silva, and Flávio Martins (eds.), Advances in Information Retrieval 42nd European Conference on IR Research,
15

---

ECIR 2020, Lisbon, Portugal, April 14-17, 2020, Proceedings, Part I, volume 12035 of Lecture Notes in Computer Science, pp. 97-110. Springer, 2020. doi: 10.1007/977-33-0044454--4 7. URL https: Published in Transactions on Machine Learning Research (03/2026)
// 10001100///77---000----------3-
Justin Gilmer, Samnel S. Schocnholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1263 1272. PMLR, 2017. URL http:// proceedings mlr. Twees//yTo/gilmrrr11 html.
Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing, In Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdoník, and Michael L. Brodic (eds.), VLDB'9g 99, Proceedings of 25th International Conference on Very Large Dala Bases, Seplember 7- Morgan Kaufmann, 1999. URL http:///twtt vldb. org/
10, 1999, Edinburgh, Scotland, UK, pp. conf 2tt///999////// pdf.
Arthur Colombini Gusmão, Alvaro Henrique Chaim Corrcia, Glauber De Bona, and Fabio Gagliardi Coz- man. Interpreting embedding models of knowledge bases: pedagogical approach. ar preprinl arXiv:1806.0055 2018.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017a. URL http://sites computer org org/debul// A17sept/p52.pdt
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017b. URL https: hetps://pccceenssseeeeee prroceedings.nnuripp. cc/paper/2017/nest Abstract html.
Taher H. Haveliwala. Topic-sensitive pagerank. In David Lassner, David De Roure, and Arun Iyengar (eds.), Proceedings of the Eleventh International World Wide Web Conference, WWW 2002, May 7-11, 2002, Honolulu, Haweïi USA, pp. 517-526. ACM, 2002. doi: 10.1145551446:5115555 URL https:
//doi. httpe/oo//....1//114411.100 111551511146.511111
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' Amato, Gerard de Mclo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, et al. Knowledge graphs. ACM Computing Surveys (CSUR), 54(4):1-37, 2021.
Glen Jeh and Jennifer Widom. Simrank: measure of structural-context similarity. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23- 26, 2002, Edmonton, Alberta, Canada, pp. 538 543. ACM, 2002. doi: (0.1145/7750477775)) URL https://doi.
10111/115577..... 775126.
Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, Junwei Yang, Jingyang Yuan, Yusheng Zhao, Xiao Luo, and Ming Zhang, A comprehensive survey on deep graph representation learning. CoRR, 05055.
2023. doi:
10.48550/ aavi. 0005://aaXXi.224.5555555 2304.05055. URL https://ddo .eriiiiorg11000 (8555//rXiv...0
Nasrullah Khan, Zongmin Ma, Aman Ullah, and Kemal Polat. Similarity attributed knowledge graph embedding enhancement for item recommendation. Inf. Sci., 613:69 95, 2022. doi: 10.1016/j ins.22......0222.00. 2022.08. 124. URL attps:///oi.. http://0...../1....0....0. 1016/J .022.22222..22 08. 124.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/16l 1611.07308, 2016. URL http://arxiv.
16

---

Published in Transactions on Machine Learning Research (03/2026)
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, TCLR 2017, Toulon, France, April 24-20 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https:/ httpa/////peeeveeeeeee pppeereviee.nee/frruuuee wet/ffoummiic SJU4ayYgl.
Namkyeong Lee, Dongmin Hyun, Gyoung S. Na, Sungwon Kim, Junseok Lee, and Chanyoung Park. Condi- tional graph information bottleneck for molecular relational learning. CoRR, abs/2305.01520, 2023. doi: 10.48550/ ..v................... 2305.01520.. URL atttps://doi org/11 10. 48550/arXiv 2ww..33355.0000
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self-supervised learning: Generative or contrastive. TEEE Trans. Knowl. Data Eng., 35(1) (5(1):857-876 2023a. doi: 10.1109/ VKDEE2222.3000866. URL
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philipp S. Yu. Graph self-supervised lcarning: A survey. IEEE Trans. Knowl. Data Eng., 35(6):5879-5500, 2023b. doi: 10.1109/KDD..022. 3172903. URL https://doi.co ottp//...r111... wttg//0..109/TKIII
2022 3172903.
Zhenghao Liu, Chenyan Xiong, Maosong Sun, and Zhiyuan Liu. Explore entity embedding effectiveness in entity retrieval. In Maosong Sun, Xuanjing Huang, Heng Ji, Zhiyuan Liu, and Yang Liu (eds.), Chinese Computational Linguistics- 18th China National Conference, CCL 2019, Kunming, China, October 18-20, 2019, Proceedings, volume 11856 of Lecture Notes in Computer Science, pp. 105 116. Springer, 2019. doi: 10.1007 (0.1007/978-33 00-----03-3300 1880032381-3- 9. URL atttps://dol org/10 10. 0000079978-3--10 1/00//988-3-000--21------13
Ana Lucic, Maartje A. ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf- gnnexplainer: Counterfactual explanations for graph neural networks. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), International Conference on Artificial Intelligence and Statistics, AIS- TATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, mlr. aar.pen crress/vi51/luiic/ee hhmm.....
Pp. 4499 4511. PMLR, 2022. URL bttcps://proceeeeee
Dongshong Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang, Parameterized explainer for graph neural network. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (ods.), Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https://proceeeeeee Abstract html.
ceorrips.ccppape//// hatppr/r//////hhh//
Elan Markowitz, Keshav Balasubramanian, Mehrnoosh Mirtaheri, Murali Annavaram, Aram Galstyan, and Greg Ver Stocg. Statik: Structure and text for inductive knowledge graph completion. In Marine Carpuat, Marie-Catherine de Marneffe, and Iván Vladimir Meza Ruíz (eds.), Findings of the Associa- tion for Computational Linguistics: NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pp. 604 615. Association for Computational Linguistics, 2022, doi: 10.18653/vb /2022 fendifinnnng---ei findings-nacl.466 na.c1.66. URL attps:///ol org/ 10. 10.18555/11/2222...nn.. naac1.46.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph net- works. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annuul Con- ference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancow- ver, BC, Canada, pp. 2153 2164, 2019. URL attps://proceedings. Annual review of sociology, Abaataat....... html.
Miller McPherson, Lynn Lovth, and James M Cook. Birds of feather: Homophily in social networks. 2001.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (ods.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 15524 15543. PMLR, 2022. URL btctps:/pproceeding: mlr, pwtps//162/mmmo22222 htmll
17

---

Published in Transactions on Machine Learning Research (03/2026)
Tim Miller. Explanation in artificial intelligence: Insights from the social sciences. Artif. Intell., 267:1-38, 2019. doi: 10.1016/..artmm2208..80 201.00000 URL https://doi.org/// org/10. 1016/ w.atiit....tt............reei.i. art.at...tt........... 0011800.007,
Shane T Mueller, Robert R Hoffman, William Clancey, Abigail Emrey, and Gary Klein. Explanation in human-ai systems: A literature meta-review, synopsis of key ideas and publications, and bibliography for explainable ai. arXiv preprint arXio: 1rXi::1902.00 902.01876 2019.
Maximilian Muschalik, Fabian Fumagalli, Paolo Frazzetio, Janine Strotherm, Luca Hermes, Alessandro Sperduti, Eyke Hüllermeier, and Barbara Hammer. Exact computation of any-order shapley interactions for graph neural networks. In The Thirteenth International Conference on Learning Representations, 2025. URL pttps://openreveee
net net/forumm wwt.orrmddddddoosss...
Galilco Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, pp.
1, 2012.
Mark Newman, Networks. Oxford university press, 2018.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proc. IEEE, 104(1):11-33, 2016. doi: 10.109//PRRC..2055222282 2483592. URL httpss//doii org/ 10. 1109/JPROCCC 2015. 2483592.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang, Graph representation learning via graphical mutual information maximization. In Yennun Huang, Irwin King, Tie- Yan Liu, and Maarten van Steen (eds.), WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pp. 259 270. ACM/ / IW3C2, 2020. doi: 10.1145/3366422.388812 URL https: //doi.org//a 10. 1145/3366423 3380112.
Alina Petrova, Evgeny Sherkhonov, Bernardo Cuenca Grau, and lan Horrocks. Entity comparison in RDF graphs. In The Semantic Web ISWC 2017, volume 10587, pp. 526-541. Springer, 2017.
Alina Petrova, Egor V. Kostylev, Bernardo Cuenca Grau, and Ian Horrocks. Query-basod entity comparison in knowledge graphs revisited. In The Semantic Web ISWC 2019 18th International Semantic Web Conference, volume 11778, pp. 658-575. Springer, 2019.
Pouya Pezeshkpour, Yifan Tian, and Samcer Singh. Invostigating robustness and intcrpretability of link prediction via adversarial modifications. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 3336-3344 Association for Computational Linguistics, 2019. doi: 10.1 13653/vl/n// 1337. URL. https::/ddae org/10. 10. 18653/v1/n19-1337.
Simone Piaggesi, André Panisson, and Megha Khosla. Disentangled and self-explainable node representation learning. Trans. Mach. Learn. Res., 2025, 2025.
Gabriëlle Ras, Marcel van Gerven, and Pim Haselager. Explanation methods in deep learning: Users, values, concerns and challenges. Explainable and interpretable models in computer vision and machine learning, pp. 19-66,2200 2018.
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. 'why should I trust you?": Explaining the pre- dictions of any classifier. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pp. 1135-1144. ACM, 2016. doi: 10.1145 10.1145/2939672.mo 29999672.2997777777 URL https://aoi.oon org/ 10. /141//939/777 2939778.
Petar Ristoski and Heiko Paulheim. Rdf2vec: RDF graph embeddings for data mining, In Paul Groth, Elena Simperl, Alasdair J. G. Gray, Marta Sabou, Markus Krötzsch, Freddy Lécué, Fabian Flöck, and Yolanda Gil (cds.), The Semantic Web ISWC 2016 - 15th International Semantic Web Conference, Kobe, Japan, October 17-21, 2016, Proceedings, Part I, volume 9981 of Lecture Notes in Computer Science, pp. 498-514, 2016. doi: 10.1007 0910/9978---1--523---- 30. URL https: http:://///..///////-----------0
18

---

Published in Transactions on Machine Learning Research (03/2026)
Petar Ristoski, Jessica Rosati, Tommaso Di Noia, Renato De Leone, and Heiko Paulheim. Rdf2vec: RDF graph embeddings and their applications. Semantic Web, (0(4):721-752 2019. doi: 10.3233/SW-180317.
URL https://doi. wtt../////...3///511100003
3233/5M-180317.
Andrea Rossi, Donatella Firmani, Paolo Mcrialdo, and Tommaso Tcofili. Explaining link prodiction systems based on knowledge graph embeddings. In Zachary G. Ives, Angela Bonifati, and Amr El Abbadi (eds.); SIGMOD '22 International Conference on Monagement of Data, Philadelphia, PA, USA, June 12 17, 2022, pp. 2062 2075. ACM, 2022. doi: 10.1145/3514221.35177888 URL https://dod: org/10.10 1145/ 3514221.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021. doi: h0/9////mmet/caaaa URL https://dbi..rg: org/10. 1093/ wwtnet/ cnab014.
Racid Saqur and Karthik Narasimhan. Multimodal graph networks for compositional generaliza- tion in visual question answering. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin (eds.), Advances in Neurol Information Processing Sys- tems 33: Annual Conference on Newral Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL https://procediins.nee wewiiinngnneuuiss... www.new.../eppppeeeeeee http:////norrrro..ocppp///////// Abstract. html.
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In Aldo Gangemi, Roberto Navigli, Maria-Fsther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mehwish Alam (ods.): The Semantic Web 15th International Conference, ESWC 2018, Herakkinn Crete, Greece, June 3-7, 2018, Proceedings, volume 10843 of Lecture Noles in Compuler Science, pp. 593 607. Springer, 2018. doi: 10.1007 1978-9--8888 3-319-93417-4, 38. URL bttcps://do..oo 0tg/10.1/// wtt......0///977...3333
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Ilaly, Oclober 22-29, 2017, pp. 618 626. IEEE Computer Society, 2017. doi: 10.1109/1CCV.2011 20017.4. URL https://doi.orr/10... 1109/ ICCV. 2017.0077
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Col- lective classification in network data. Al Mag., (9)3)) 106, 2008 doi: 10.1609/ /tt///amm.g222/ w29.3.21111 2157. URL attps:://ol. orw..oog////o..... 1609/ 160.//mmag..... v2913. 2157..
Baoxu Shi and Tim Weninger. Open-world knowledge graph completion. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirly-Scoond AAAT Conference on Artificial Intelligence, (AAAT- 18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 1957 1964. AAAI Press, 2018. doi: 10. 11..60//aaai.v32.111113.. URL attpp://doi.com org/10.. 1609/ 1609/aaai. aaai, v3211. 11535.
Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Jie Tang, and Evgeny Kharlamov. Keyword-based knowledge graph exploration based on quadratic group steiner trees. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAT, pp. 1562, 2021.
Larissa Capobianco Shimomura, Rafael Seidi Oyamada, Marcos R. Vieira, and Daniel S. Kaster. A survey on grsph-based mothods for similarity scarches in metric spaces. Inf. Syst., 95:101507, 2021. doi: 10.1016/ 2iis.2020.11100 URL attps:///olt org. 1016/..00./..................../ is.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In Doina Precup and Yoe whye Tch (ods.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Reseorch, pp. 3145-3153. PMLR, 06-11 Aug 2017. URL https:
mwr. prw.ss////////////////// grress/70/shrrkumae htto///rrrrrrrrrre 1 17a html.
19

---

Published in Transactions on Machine Learning Research (03/2026)
Karen Simonyan, Andrea. Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Workshop Track Proceedings, 2014. URL http:///arxivv www.iii.oog/bbb..oo wtgg/bs///////a.////////// 6034.
Jaeyun Song, Sung Yub Kim, and Eunho Yang. RGE: A repulsive graph rectification for node classification via influence. In International Conference on Machine Learning, pp. 12331-32345 PMLR, 2023.
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin A. Riedmiller. Striving for simplic- ity: The all convolutional net. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learnång Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. URL http:/ htttp://arxiie htt///xxvv..rrgg//e org/ abs// at//aaas/////// /////1112.66901 6806.
Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-lovel reprosentation learning via mutual information maximization. In 8th International Conference on Learning Represenlations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nen net,, 2020. URL https:/ btstps://openreeeeee http://pppeeeeeeeeeeeee net/
Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proc. VLDB Endow., 4(11):992 1003, 2011. URL http:://tttt wldd. wrddb.og//o....... pwtppp/oo1///99222/s pdf.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, 1CML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 3319 3328. PMLR, 2017. URL http: http://proceedinggs mlr. press/v70 sundararajan178r html.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In John F. Flder IV, Françoise Fogelman-Soulié, Peter A. Flach, and Mohammed Javeed Zaki (eds.), Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28- July 1, 2009, pp. 807-816. ACM, 2009. doi: 10.1145/115701191555110. URL https: //doi.org/// 1145/1557019 1557108.
Shantamu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Velickovic, and Michal Valko. Large-scale representation lcarning on graphs via bootstrapping. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview net, 2022. URL /tttps://operreet http://p//pppppoooo...oooooooooa wttp//orrrrddooO0/rrrrrrr
Petar Velickovie, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In 7th International Conference on Learning Representations, ICLR 2019, New Orleons, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL attps:// http:::///ppeeeriss.neeee//////e wwwp:eviiiiiitttennnnnnuuaeeeeee rklz9iAcKQ.
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6- 6-12, 2020, virtual, 2020.
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. MGAE: marginalized graph autoencoder for graph clustering. In Fe-Peng Tim, Marianne Winslett, Mark Sanderson, Ada Wai-Chee Fu, Jimeng Sun, J. Shane Culpepper, Eric Lo, Joyce C. Ho, Debora Donato, Rakesh Agrawal, Yu Zheng, Carlos Castillo, Aixin Sun, Viucent S. Tseng, and Chenliang Li (eds.). Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06- - 10, 2017, pp. 889- 3132967.
898. ACM, 2017a. doi: 10.1145/3 041114/31328441 /3/33311338733 31329677
URL https://ddo..or//0000 100..114555
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE Trans. Knowl. Data Eng., 29(12)) 2743, 2017b. doi: 10.1109/TKDE.2017. 2754499. URL https://doi. http:///doi.rrg////00 1119 2017 2754499.
20

---

Published in Transactions on Machine Learning Research (03/2026)
Xiang Wang, Ying-Xin Xin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained ex- plainability for graph neural networks. In Mare' Aurelio Ranzato, Alina Beygekimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pp. 18458, 2021. URL sttps://proceedinge wwwpiiiinnnnnuuiis..mm piiiipsscc//appe/22////asss Abstract. html.
Felix Wu, Amauri H. Souza Jr., Tiany Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinor (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6861 6871. PMLR, 2019. URL http://proceedings mlr. Apress/v9//wu190 html.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst. 32(1):4-24 2021. doi: 201109/TNNLLS
URL attps://doi... http//di..ogg//g///// 1t1/111..1111/// 1109/TNNLS. 2020. 2978386.
Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for graphs. In NewrIPS, 2022. URL http:://ppppeeee nips htpp.cc/ppppr...../ htt.ccaaperfilllesppppeeeeeeeeee / html.
Qizhe Xie, Xuezhe Ma, Zihang Dai, and Eduard Hovy. An interpretable knowledge transfer model for knowledge base completion. In Proceedings of the 55th Annual Meeling of the Associalion for Compula- tional Linguistics (Volume 1: Long Papers), pp. 550-962, Vancouver, Canada, July 2017. Association for URL
Computational Linguistics. doi: 10.18653/w1/P17-110
http://cclaatthoooooor///////
Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward W. Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. Task-agnostic graph explanations. In NewrIPS, 2022a. URL http: .iis.. cc/ htt.raaeeeeeeeeteeeeeee---eteeee
paper paper_files/papeeeeeepeeeeeeeeep
html.
Yaochen Xie, Zhao Xu, and Shuiwang Ji. Self-supervised representation learning via latent graph prediction. In Kamalika. Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 24460 24477. PMLR, 2022b. URL https: //proceedings wmr.iins.mmrr...mmm.mm.....e..e. www.mmeer...eeeee. wwwppp/wss/eeeeeeeeepeppepeeeeee http///112xxxeeeeeee xie22e. html.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. IEEE Trans. Pattern Anal. Mach. Intell., 45(2):2412 2429, 2023. doi: 10. (P0009/TPAM..022....
URL https: http://doo.oo/////////
org/10. 10. 10.111//TPPMMM 2022. 3170559.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.ne,, 2019. URL https:// /ttpp/////peeeviiee.ee wetpeeewwwweeeeeeeeeeeeeeeeeeeee peet//forum?ddrrGaaii...
Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J. Schweiger. SCAN: a structural clustering algorithm for networks. In Pavel Berkhin, Rich Caruana, and Xindong Wu (eds.), Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, August 12- 2007, pp. 824 833. ACM, 2007. doi: (0.1145/1281192.1281 1281280.
URL https://doi.
12/1192811912 100.111151228192 org/10 10. 1145 105//10.114//121
Ikuya Yamada, Akari Asai, Jin Sakuma, Hiroyuki Shindo, Hidcaki Takeda, Yoshiyasu Takefuji, and Yuji Matsumolo.. Wikipedia2vec: An elficient toolkit for learning and visualizing the embeddings of words and entities from wikipedia. In Qun Liu and David Schlangen (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, EMNLP 2020- Demos, Online, November 16-20, 2020, pp. 23-30. Association for Computational Linguistics, 2020. doi: 10.18653/ v1 /22000eemmlppdemmm URL https://daait http::////oo.o//////// 10. 10113/00/06633////200... emnlp-demos... .4.
21

---

Published in Transactions on Machine Learning Research (03/2026)
Wenli Yang, Yuchen Wei, Hanyu Wei, Yanyu Chen, Guan Huang, Xiang Li, Renjie Li, Naimeng Yao, Xinyi Wang, Xiaotong Gu, Muhammad Bilal Amin, and Byeong Kang. Survey on explainable AI: from approaches, limitations and applications aspects. Hum. Centric Intell. Syst., 3(3):161 188, 2023. doi: 10.1007/544230--23--0000
URL https: http::://doi.org/111// wtg/100.000/8442200023 /20///22200000000008-0-0
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedinggs of the 33nd International Conference on Machine Learning, 1CML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 40-48. JMLR.org, 2016. URL html.
mlr. paress/48/yange
Zi Ye, Yogan Jaya Kumar, Goh Ong Sing, Fengyan Song, and Junsong Wang. A comprehensive survey of graph neural networks for knowledge graphs IEEE Access, (177779-777447 2022. doi: 10.1109/ACCESS. 2022.3191784. URL https: http:////oo..o/....../ 1109/ /A////CC....../ 2022.3191784 3191784.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Flo- rence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Newral Information Processing Systems 2019, NeurIPS 2019, Decem- ber 8-14, 2019, Vancouver, BC, Canada, pp. 9240 9251, 2019. URL atttps://ppt http://eeeiigg......m. neurips.co. /tt0//////////000000000000000000
www.tffttbttttt.....ooooooo html.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12241 12252. PMLR, 2021. URL v139/yuan21c html.
somiiiiinnnmmm.......mm. mlr press/
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Trans. Pattern Anal. Mach. Intell., 45(5):5782-3783 2023. doi: 3204236. URL https:///dl org/10. 1109/TPAMI 2022. 3204236.
Reza Bosagh Zadeh and Ashish Goel. Dimension independent similarity computation. J. Mach. Learn. Res., 14(1):1605 1626, 2013. doi: 10.5555 10.5555/25677099 2567///777799..7715.. URL https://dl acm. org/doi/10 5555/ 0867709.2567777
Hengtong Zhang, Tianhang Zheng, Jing Gao, Chenglin Miao, Lu Su, Yaliang Li, and Kui Ren. Data poisoning allack against knowledge graph embedding. In Sarit Kraus (ed.), Proceedings of the Twenly- Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 4853-4859. ijeai.org, 2019. doi: 10.24963 11/96//jcaii./ 2019/67. ijcai.2011 2019/674.
URL https://dol https://ddo.oor/0000 209633.249633 24963/
Zhao Zhang, Fuzhen Zhuang, Meng Qu, Zheng- Yu Niu, Hui Xiong, and Qing He. Knowledge graph embed- ding with shared latent semantic units. Neural Networks, 139:140-148, 2021. doi: 10.1016/).neumet2222 02.013. URL attps://dol. 001/10.00001101// neunet. 2021 02.00....13.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57 81, 2020. doi: 10.1016/j.aioppe catoopen.2221.000 2021.01.001.
URL https:///oi.co org/ 10. 1016/j aiopen. 2021 01. 001.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive represen- 04131.
(ation learning. CoRR, abs/2006.04133 04131,,,,,, 2020. URL
Unai Zulaika, Aitor Almeida, and Diego López-de Ipiña. Regularized online tensor factorization for sparse knowledge graph embeddings. Neural Comput. Appl, 35(1):787 sep 2022. ISSN 0941- 0643. doi: 1000//000511-02-0777000 500521-022-07796-22
URL https://doi-ore vu-nl. idm. wolc.org//1..1000
22

---

Published in Transactions on Machine Learning Research (03/2026)
Table 4: Results of fidelity metrics (Fida and Fids) and effect overlap (EO, lower is better) when using an
SGC (Wu et al., 2019) as the base GNN architocture.
Com
Citesees
Palased
Chameccon
Actor
Squirel
Method
F5l.
Fids
EX0
Fid.,
Ficls
80
Fid.,
Fids
80
Fid.,
Fida
EO
Fide.
Fids
130
F5d.
Fids
BD
M1
0.020
-0.005
0.916
0.185
0.005
0.852
0.090
0.231
0.978
0:231
-0.060
0.668
0.161
-0.053
0.676
0.042
0.250
0.802
GAR
GR1
0.048
-0.036
0.067
0.075
-0.048
0.030
0.214
-3.009
0.232
0.137
-0.101
0.034
0.253
-0.254
0.052
0.281
-0.005
0.251
GB2
0.060
000400
0.074
0.299
-0.033
0.049
0.453
-0.120
0.012
0.185
-0.169
0.117
0,209
-0.221
0.085
0.561
-0.233
0.010
MI
0.072
0.135
0.957
0.129
0.010
0.006
0.355
0.797
0.312
-0.041
0.678
0.225
-0.44
0.733
-0.014
0.346
0.516
VGAR
GR1
0.177
-8.060
0.105
0.008
-0.044
0.076
0.261
-0.043
0.206
0.233
-0.283
0.030
0.362
-0:357
0.039
0.355
0.013
0.307
GB2
0.530
0.063
0.015
0.280
0.035
0.072
0.479
0.166
0.017
0.280
-0.245
0.065
0.315
0.521
0.098
0
0.324
0.018
MI
0.018
0.000
0.355
-0.079
0.350
-0.089
-1.027
0.417
-0.010
0.134
0.374
0.017
0.042
0.479
.0.015
0.823
DGI
GB1
0.017
-6.010
0.015
-0.013
-0.104
0.353
-0.112
-0.095
0.914
0.200
-0.213
0.110
0.088
-0.053
0.055
-0.208
00:287
0.682
GB2
0.018
0.011
0.006
0.085
00,388
0.527
0.110
0.218
0.553
0.310
-0.261
0.125
0.079
0.009
0.068
0.265
00403
0.650
0.007
-0.005
0.010
-0.002
0.908
0.118
0.106
0.729
0.140
-0.017
0.813
-0.005
-0.064
0.963
0.075
-0.008
0.608
GRACE
GB1
0.047
00.040
0.074
0.030
-0.021
0.085
0.115
-0.045
0.162
0.096
-0.107
0.033
0.085
-0.244
0.027
0.070
-0.064
0.262
GR2
0.067
-0:047
0.050
0.041
-0.024
0.085
0.221
-0.060
0.045
0.124
-0.101
0.047
0.015
-0.321
0.200
0.080
-0.189
0.185
A Additional results
Our main experimental results aim to investigate the effect of the metrics we proposed on different embedding learning algorithms and datasets when the architecture is designed from GCN layers (Kipf & Welling, 2017).
To determine whether results generalize to other architectures, here present extended results where we repeat the experiments using four additional architectures: SGC (Wu et al., 2019), simplified variant of the GCN that reformulates message passing in multi-layer GNNs as a single matrix multiplication with powers of the adjacency matrix; GraphSAGE (Hamilton et al., 2017b), which for a given node, concatenates embeddings of the node from previous layers during the neighborhood aggregation process (in contrast to the GCN which mixes only embeddings from the same layer); MixHop (Abu-El-Haija et al., 2019), which is designed to capture higher-order patlerns by computing at each layer representations from powers of the adjacency matrix; and R-GCN (Schlichtkrull et al., 2018), a variant of the GCN that learns different weight matrices for heterogeneous relation types that arisc in knowledge graphs
We present results with SGC in Table 4, GraphSAGE in Table 5, and MixHop in Table 6. On the DBPedia50k knowledge graph, we present additional results using these three architectures plus the R-GCN in Table 7. The extended results indicate that the behaviour observed with our proposed metrics remains under changes in the architecture in the majority of the cases: gradient-based explanations are actionable, as interventions based them produce predictable effects on the score (either increasing it or decreasing it); and they are consistent, as these effects are distinct, which is demonstrated by the low effect overlap.
A special case is found in the combination of DGI as a learning algorithm, and GraphSAGE as the base GNN (shown in Table 5). Here we note that in virtually all cases, any intervention results in decreasing the similarity between two nodes (denoted by the negative values of Fid, and Fidz) but the magnitude of changes is larger when using gradient-based explanations, resulting in higher actionability In contrast, the mutual information (MI) method results in smaller changes, thereby indicating low actionability. In spite of this, the MI method results in lower overlap in several cases, indicating higher consistency than gradient-based methods.
We conclude that EO must be interpreted jointly with fidelity: the lower EO of MI here follows from ncar-zero effects, whereas gradient-based explanations result in substantially stronger interventions (higher actionability) even though their effects are not sign-separated, which raises EO. Despite occasional cases where MT attains lower EO, gradient-based explanations are preferable for similarity explanation because they provide stronger, controllable interventions; MI's improved overlap in this regime is largely explained by its limited impact on the similarity score. This suggests that on DGI+GraphSAGE, the similarity function is globally fragile (interventions mostly reduce similarity), making sagn-based separation difficult for any explainer despite differences in actionability.
23

---

Published in Transactions on Machine Learning Research (03/2026)
Table 5: Results of fidelity metrics (Fid, and Fids) and effect overlap (EO, lower is better) when using GraphSAGE (Hamilton et al., 2017b) as the base GNN architecture.
Ctasserr
Pulmee
Chandeeon
Acsze
Squireel
Methoo
Fid.
Pid.
EXO
Fid.
Fiel,
RO
Firl
Fidy
Fid.
Fide
RO
Fir.
Fvi.
Fid..
Fid,
M1
0.000
0.002
0.436
0.001
0.000
0.724
0.081
0.074
0.905
0.035
0.029
0.720
0.060
0.031
0.810
0.007
0.037
0.969
GAE
GB1
0.012
-0.008
0.150
-0,022
0.149
-0.041
0.234
0.082
0.102
0.094
-0.036
0.344
0.113
(382
0.018
-0.014
0.080
0.000
-0.025
0.083
0.264
-0.130
0.046
0.123
-0.030
0.070
0.104
-0.075
0.105
0.188
-0.121
0.028
M1
0.057
0.061
0.802
0.056
0.058
0.832
0.070
0.121
0.944
0.041
0.005
0.898
0.007
0.055
0.967
0.005
0.043
0.910
VGAE
GB1
0.116
-0.087
0.202
-0.020
0.151
0.106
-0.077
00.106
0.116
GB32
0.183
-0.058
0.026
0.168
-0.042
0.082
0.343
-0.142
0.053
0.257
-0.126
0.022
0.338
-0.157
0.088
0.208
-0.154
0.030
M1
-0.15 -0.105
-0, 232
0.720
-0.038
-0.365
0.626
0.005
-0.000
0.960
0.000
-0. 0.0027
0.708
0.013
-0.000
0.373
-0 0.038
-0.017
0.242
DGI
GB1
0.303
00.410
0.945
00,454
00.25
0.878
0.651
0.004
0.970
00.276
-0. 00.33
0.500
-0.133
00.39
0.654
0..18
0.218
0.845
GB3
-0447
06660
0.950
-0.420
-0.783
0.672
00.170
-0.213
0.953
-0.385
-0.6 02.27
0.001
-0.317
-0.556
0.807
-0.251
-0.365
0.862
M1
0.001
-0.002
0.754
-0.004
-0.002
0.676
0.013
-0.00
0.459
0.027
-0.002
0.576
0.016
-0.005
0.536
-0.001
-0.000
0.645
GRACE
GB1
0.020
0.079
40.016
0.075
0
-0.56
0.087
0,050
-0.043
0.057
0.054
-0.064
0.045
0.080
-0.106
0.085
GB2
0.029
0.028
0.046
0.011
0.017
0.068
0.048
0.081
0.026
0.071
00.050
0.035
0.088
0.077
0.026
0.107
0.116
0.026
Table 6: Results of fidelity metrics (Fid, and Fida) and effect overlap (EO,, lower is better) when using MixHop (Abu-El-Haija et al., 2019) as the base GNN architecture
Cora
Ciseseer
Pubmed
Chamelleu
Ausor
Squiree)
Method
Fid.
E0
Fid,
Fid,
BO
F'd.
Fid,
Fid.
Fide
ED
15d.
Fid,
E0
Fid.
Fid,,
M1
0.002
-0.002
0.558
0.013
0.003
0.004
0.080
0.165
0.912
0.000
-0.008
0.860
0.029
-0.038
0.032
0.0G7
0.048
0.878
GAB
GB3
0.047
-0.038
0.065
0.027
-0.016
0.098
0.198
0.047
0.428
0.113
-0.302
0.043
0.170
-0.198
0.052
0.230
-0.023
0.204
GB2
0.055
0.042
0.059
0.052
0.018
0.117
0.363
0.141
0.050
0.114
0.226
0.071
0.152
00.222
0.060
0.272
0.230
0.033
M1
0.011
-0.011
0.900
0.006
-0.004
0.508
0.088
0.279
0.942
0.112
0.086
0.921
0.171
0.190
0.800
0.101
0.111
0.784
VGAE
GBI
0.070
-0.070
0.072
0.055
-0.029
0.148
0,248
0.026
0.555
0.268
-0.150
0.062
0.380
-0.110
0.119
0.272
0.035
0.420
GB2
0.083
00.075
0.064
0.038
0.007
0.107
0.425
00.18
0.057
0.361
-0.170
0.021
0.399
-0.247
0.024
0.376
0.031
M1
-0.023
0.002
0.342
-0.051
0.011
0.386
0.065
0.023
0.757
0.004
0.006
0.596
-0.079
-0.010
0.370
0.000
-0.030
0.656
DGI
GB1
0.142
0.2455
0.817
00.211
0..59
0.696
0.007
0.129
0.652
-0.005
-0.214
0.360
-0.227
00.524
0.762
00,505
-0.17
0.808
GB2
-0070
-0.205
0.711
-0.189
-0.351
0.001
-0.019
-0.087
0.541
-0.009
-0.331
0.407
-0.032
-0.128
0.377
-0.212
-0.376
0.773
M1
-0.016
-0.024
0.500
-0.014
-0.010
0.584
-0.021
-0.026
0.567
-3.021
-0.033
0.608
-0.114
-0.091
0.587
-0.034
-0.069
0.742
GRACE
GB1
0,032
0.072
0.083
0.090
0.051
0.153
0,006
0.081
0.521
0.061
-0.149
0.077
0.027
00.257
0.164
0.017
0..10
0.211
CB2
0.031
-0.081
0.100
0.028
40.188
0.142
0.012
-0.084
0.304
0.062
40.156
0.086
-0.047
-0.308
0.382
0.008
-0.153
0.296
Table 7: Results of fidelity metrics (Fid, and Fidz) and effect overlap (EO, lower is better) on the DBPPedia50k dataset, when using SGC (Wu et al., 2019), GraphSAGE (Hamilton et al., 2017b), MixHop (Abu-El-Haija et al., 2019), and R-GCN (Schlichtkrull et al., 2018) as the base GNN architecture.
SGC
GraphSAGE
MixHop
R-GCN
Method
Fid,
Fid,
EO
Fid,
Fid,
EO
Fid,
Fid,
EO
Fid,
Fid,
EO
MI
0.006
-0.112
0.914
0.013
-0.037
0.874
-0.029
-0.079
1.000
-0.014
-0.019
0.970
GAE
GB1
0.124
-0.172
0.089
0.051
-0.084
0.241
0.096
-0.166
0.127
0.095
-0.114
0.198
GB2
0.155
-0.184
0.129
0.094
-0.092
0.159
0.110
-0.211
0.087
0.116
-0.132
0.137
MI
-0.009
0.071
0.711
0.012
-0.052
0.833
0.005
-0.055
0.976
-0.014
-0.025
0.929
VGAE
GB1
0.166
-0.128
0,153
0.067
-0.081
0,242
0.137
-0.172
0.083
0.071
-0.114
0.186
GB2
0.375
-0.160
0.114
0.081
-0.114
0.135
0.156
-0.206
0.041
0.089
-0.136
0.091
MI
-0.037
0.273
0.252
-0.087
-0.017
0.753
-0.082
-0.020
0.239
-0.041
-0.054
0.850
DGI
GB1
0.264
-0.080
0.140
0.123
-0.324
0.357
-0.146
-0.213
0.843
0.057
-0.171
0.331
GB2
0.345
-0.113
0.095
0.093
-0.508
0.234
-0.095
-0.211
0.612
0.064
-0.215
0.230
MI
0.010
-0.022
0.813
-0.001
-0.007
0.546
-0.015
-0.010
0.373
-0.022
-0.024
0.813
GRACE
GB1
0.108
-0.083
0.058
0.017
-0.024
0.074
0.021
-0.043
0.085
0.077
-0.072
0.203
GB2
0.107
-0.089
0.048
0.019
-0.030
0.046
0.017
-0.045
0.099
0.057
-0.072
0.201
24


Reviews:
[{"review_id": "S7hX4Mi7r5", "reviewer": "Reviewer_5HUx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of explaining node similarity scores produced by Graph Neural Networks trained in an unsupervised manner. While most prior work on explainable GNNs focuses on supervised tasks such as node classification, this submission correctly identifies that similarity search constitutes a different setting, where predictions are continuous and sensitive to small changes in graph structure. The authors analyze two prominent families of explanation methods, namely mutual information–based approaches and gradient-based approaches, and assess their suitability for explaining cosine similarity between node embeddings. They introduce three desiderata tailored to similarity explanations—actionability, consistency, and sparsity—and propose quantitative metrics to evaluate them through graph interventions. Through extensive experiments across multiple datasets and unsupervised learning methods, the paper shows that gradient-based explanations satisfy these desiderata more reliably than mutual information–based methods, which often yield ambiguous or inconsistent effects. A key strength of the paper is the clarity with which it motivates why relevance-based explanations are insufficient for similarity tasks, as well as the breadth of the experimental evaluation. A limitation is that the analysis is restricted to cosine similarity and edge-level explanations, which narrows the generality of the conclusions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims made in the paper are supported by clear and systematic empirical evidence. The authors operationalize their proposed desiderata using well-defined metrics based on controlled interventions on the graph and consistently apply these metrics across multiple datasets, graph structures, and unsupervised learning methods. The experimental results strongly support the central claim that gradient-based explanations are actionable and consistent, while mutual information–based explanations are not well suited to similarity tasks. The inclusion of both homophilic and heterophilic graphs, as well as a knowledge graph without node features, further strengthens the evidence by demonstrating robustness across different graph regimes. Qualitative examples complement the quantitative results and illustrate how gradient-based explanations align with intuitive semantic interpretations. While the evaluation focuses on a specific similarity function, within this scope the evidence is convincing and clearly presented.", "audience_yn": "Yes", "audience_explanation": "The findings of this paper are likely to be of interest to a significant portion of the TMLR audience, particularly researchers working on graph representation learning, unsupervised learning, and explainable machine learning. Similarity search on graphs is a foundational task with applications in recommendation systems, information retrieval, and knowledge graphs, yet explainability in this setting has received limited attention. By highlighting the mismatch between common explanation paradigms and similarity-based objectives, the paper provides insights that are broadly relevant beyond the specific methods evaluated. The work also offers practical guidance on which explanation techniques are more appropriate for similarity tasks, which is valuable for both researchers and practitioners designing explainable graph-based systems.", "requested_changes": "While the paper is generally strong, it would benefit from a more explicit discussion of how the conclusions depend on the choice of cosine similarity. In particular, it would be valuable to clarify whether the proposed desiderata and the empirical findings are expected to hold for alternative similarity or distance measures, such as dot product similarity or Euclidean distance. Including such a discussion, or a limited comparison, would help assess the generality of the conclusions and strengthen the overall contribution, although this change is not strictly critical for acceptance.", "broader_impact_concerns": "The paper does not raise immediate ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iQaAztHTJP", "reviewer": "Reviewer_y8Xx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript explores an underexplored issue in the field of GNN interpretability: how to explain similarity between nodes. To this end, the authors propose an evaluation framework with three key criteria. Comparative experiments on multiple datasets between mutual-information-based and gradient-based methods yield certain insights.\n\n**Strengths**\n1) Explaining node similarity appears to be the first work of its kind, advancing the field.  \n2) The authors employ a wide range of datasets, including both homophilic and heterophilic graphs.  \n3) The authors highlight specific advantages of gradient-based methods over mutual-information-based methods, providing heuristic guidance for future research.  \n4) The proposed evaluation metrics are reasonable, particularly the consistency criterion, which effectively distinguishes between positive and negative contributions of explanations.  \n\n**Weaknesses**\n1) In page 3, the authors claim that their proposed metrics are model-agnostic, but in the experiments, only GCN is used as the encoder. Could the authors employ more GNNs (e.g., SGC, APPNP, GraphSAGE, etc.) to verify whether explanations for node similarity are consistent or follow similar trends across models?\n2) In the experiments, the authors only consider GNNExplainer as a representative mutual-information-based method. It is recommended that the authors include more methods (e.g., PGExplainer, SubgraphX, PGM-Explainer) to better support their arguments.  \n3) The authors show experimentally that gradient-based methods generally provide better explanations, but an analysis of computational overhead is lacking.\n4) Interpretability is closely related to data attribution or data valuation. It is suggested that the authors discuss in the related work the connections between interpretability and relevant studies [1-5].\n\nIn summary, i think this is a very interesting paper. The authors have identified a meaningful and valuable research problem, but the experimental study lacks breadth. If the above issues can be adequately addressed, I am inclined to accept this manuscript.\n\n[1] GraphSVX: Shapley Value Explanations for Graph Neural Networks. ECML, 2021.  \n[2] Characterizing the Influence of Graph Elements. ICLR, 2023.  \n[3] RGE: ARepulsive Graph Rectification for Node Classification via Influence. ICML, 2023.  \n[4] Precedence-Constrained Winter Value for Effective Graph Data Valuation. ICLR, 2025.  \n[5] Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks. ICLR, 2025.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors propose three critical metrics and conduct relatively comprehensive experiments on multiple datasets.", "audience_yn": "Yes", "audience_explanation": "This manuscript explores an underexplored issue in the field of GNN interpretability. I believe this will advance interpretability in areas such as recommendation systems, community detection, epidemic analysis, and complex networks.", "requested_changes": "Please refer  to **Weaknesses**.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hxid8MWAYO", "reviewer": "Reviewer_mZ83", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores how to interpret the node similarity scores computed by GNNs. It proposes three core criteria for evaluating similarity explanations, including actionability, consistency, and sparsity. The paper operationalizes them via intervention-based metrics: fidelity, effect overlap, and sparsity preservation. The authors compared two explanatory methods (i.e., MI based methods and GB based methods) on six datasets (homogeneous graphs, heterogeneous graphs, and knowledge graphs) and four unsupervised node embedding methods (GAE, VGAE, DGI, and GRACE). The key finding is that gradient-based methods outperform MI-based methods in satsfying the three criteria.", "claims_and_evidence_yn": "No", "claims_explanation": "1. This paper relies on only GCN as the backbone for node embedding. However, this message passing architecture can not be effectively applied to heterogeneous graphs and knowledge graphs. The bad interpretation performance of MI may be due to the embedding learning process itself rather than the interpretability method. Therefore, the experimental results on heterogeneous graphs and knowledge graphs are not convincing.\n2. Another thing is that different message passing methods create node embeddings with different properties. For example, GCN tends to create smooth node embeddings, while the Transformer based GNN (e.g., graph transformer [`1`]) and the GNNs motivated by Weisfeiler and Leman test (e.g., k-GNN [`2`] and MPSN [`3`] ) capture longer-range dependencies. The conclusions that GB performs better than MI drawn from GCN may not generalize to other message passing architectures.\n\n---\n**Reference**\n\n[1] Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35, 14501-14515.\n\n[2] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019, July). Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence (Vol. 33, No. 01, pp. 4602-4609).\n\n[3] Bodnar, C., Frasca, F., Wang, Y., Otter, N., Montufar, G. F., Lio, P., & Bronstein, M. (2021, July). Weisfeiler and lehman go topological: Message passing simplicial networks. In International conference on machine learning (pp. 1026-1037). PMLR.", "audience_yn": "Yes", "audience_explanation": "Yes, some individuals in TMLR's audience would be interested in the findings of this paper. However, the scope of interest may be limited to researchers who are specifically focused on interpretability methods for graph neural networks and unsupervised node embeddings. Its appeal may not extend to those working on more general graph learning or supervised based graph learning tasks.", "requested_changes": "1. Please consider my concern raised above.\n2. No explicit justification for threshold choices (t=0.5 for MI, t=0 for GB methods).\n3. Why edge-only explanations are prioritized over node features? I think both edge and node feature explanations are not human-understandable.\n4. While Section 2 categorizes prior work, it fails to clearly link gaps in existing literature to the specific contributions of this paper.", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)