🤖 machine learning

Explaining Graph Neural Networks for Node Similarity on Graphs

This paper investigates explainable similarity search on graphs by evaluating mutual information and gradient-based explanation methods for Graph Neural Networks, demonstrating that gradient-based approaches offer superior actionable, consistent, and sparsifiable explanations for node similarity scores.

Original authors: Daniel Daza, Cuong Xuan Chu, Trung-Kien Tran, Daria Stepanova, Michael Cochez, Paul Groth

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Daza, Cuong Xuan Chu, Trung-Kien Tran, Daria Stepanova, Michael Cochez, Paul Groth

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, complex map of connections, like a massive social network or a web of scientific citations. You've built a smart computer program (a Graph Neural Network, or GNN) that looks at this map and says, "Hey, these two people (or papers) are very similar."

Usually, when these programs make a decision, we want to know why. But most of the time, the "why" only works for clear-cut answers like "Is this a cat or a dog?" or "Will this person click this ad?"

This paper asks a different question: What if the computer just says, "These two things are 85% similar"? How do we explain why it thinks that?

The authors realized that the usual tools for explaining AI don't work well for this "similarity" task. So, they built a new set of tools to test which explanation methods actually make sense. Here is how they did it, using some everyday analogies.

The Problem: The "Black Box" Similarity Score

Think of the GNN as a chef who has tasted two dishes and declared, "These two soups are very similar."

The Old Way (Supervised Learning): If the chef said, "This is soup," we could ask, "Did you taste the carrots?" or "Was it the salt?" We know the target (Soup vs. Not Soup).
The New Problem (Similarity): The chef just says, "Soup A and Soup B are 90% alike." If we ask, "Why?", the old tools might point to random ingredients that don't actually explain the similarity. They might say, "It's the salt!" but then if you remove the salt, the similarity score doesn't change much. That's a bad explanation.

The Solution: Three Rules for a Good Explanation

The authors came up with three rules (criteria) that a good explanation for similarity must follow. They tested these rules by playing "what if" games with the graph (the map).

1. Actionable (The "What If" Test)

The Analogy: Imagine the explanation says, "The reason these two soups are similar is the basil."
The Test: If you take the basil out of both soups, the similarity score should drop. If you add more basil, the score should go up.
The Claim: A good explanation must let you change the input (the graph) in a predictable way. If the explanation says "basil" but removing it does nothing, the explanation is useless.

2. Consistent (The "Opposite Sides" Test)

The Analogy: Imagine the explanation splits the ingredients into two piles: "Good for similarity" (Pile A) and "Bad for similarity" (Pile B).
The Test: If you keep only the "Good" pile, the soups should become more similar. If you keep only the "Bad" pile, they should become less similar.
The Claim: The two piles must do opposite things. If keeping the "Good" pile makes them similar, but keeping the "Bad" pile also makes them similar (or does nothing), the explanation is confusing and inconsistent.

3. Sparse (The "Essentials Only" Test)

The Analogy: A good explanation shouldn't say, "The similarity is because of every single grain of salt in the ocean." It should say, "It's because of these three specific herbs."
The Test: Can you throw away 90% of the ingredients the explanation pointed to, and still get the same result?
The Claim: A good explanation should be able to be shrunk down to a tiny, essential list without losing its power.

The Experiment: Who Passed the Test?

The authors took two popular types of AI explainers and tested them against these three rules on various maps (datasets like citation networks and knowledge graphs).

Team A: The "Mutual Information" Explainers (The Guessers)

How they work: They try to find a small subgraph that "contains" the answer, kind of like guessing which part of the soup recipe is most important by trial and error.
The Result: They failed the tests.
- They weren't Actionable: Removing the ingredients they pointed to didn't reliably change the similarity score.
- They weren't Consistent: Sometimes keeping the "important" ingredients made the score go up, and sometimes it went down. It was a coin flip.
- They weren't Sparse: You couldn't easily shrink their list of ingredients.

Team B: The "Gradient-Based" Explainers (The Calculators)

How they work: They use math to calculate exactly how much every single edge (connection) in the map pushes the similarity score up or down. It's like a precise scale measuring the weight of every ingredient.
The Result: They passed all three tests!
- Actionable: If they said an edge increases similarity, removing it made the score drop. If they said it decreases similarity, removing it made the score rise.
- Consistent: The "up" edges and "down" edges did exactly opposite things.
- Sparse: You could throw away 90% of the edges they pointed to, and the remaining few still explained the similarity perfectly.

The Big Takeaway

The paper concludes that when you are trying to explain why two things are similar (a continuous score), the "Gradient-Based" methods are the winners. They give you a clear, reliable, and compact map of why the computer thinks two nodes are alike.

The "Mutual Information" methods, which work great for simple "Yes/No" questions (like "Is this a cat?"), get confused when the question is "How much do these two things resemble each other?"

In short: If you want to know why two people in a network are similar, don't ask the AI to guess which connections matter. Ask it to calculate the exact push and pull of every connection. That gives you a clear, trustworthy answer.

Technical Summary: Explaining Graph Neural Networks for Node Similarity on Graphs

Problem Definition

The paper addresses a critical gap in the explainability of Graph Neural Networks (GNNs). While extensive research exists on explaining GNNs for supervised tasks (e.g., node classification, link prediction), the problem of explaining node similarity in unsupervised settings remains largely unaddressed. In many applications, such as citation networks or knowledge graphs, GNNs are trained to learn node embeddings where similarity is computed via metrics like cosine similarity. Unlike discrete classification labels, similarity is a continuous quantity, and existing evaluation protocols for explainability do not directly apply. The authors investigate how to attribute values to edges in a graph to explain why two specific nodes have a high or low similarity score, distinguishing this from tasks where the goal is to justify a discrete prediction.

Methodology

Framework and Criteria

The authors propose a framework to evaluate explanations of node similarity based on three criteria derived from general Explainable AI (XAI) principles:

Actionability: An explanation should allow for interventions (e.g., adding or removing edges) that result in a predictable change in the similarity score.
Consistency: The effect of keeping edges above an explanation threshold must be distinct from the effect of discarding them (i.e., keeping edges below the threshold). The two sets of edges should not produce overlapping or indistinguishable effects on the score.
Sparsity: An explanation should be compressible; a small subset of the most relevant edges should retain the majority of the explanatory effect observed in the full set.

Intervention-Based Metrics

To operationalize these criteria, the authors introduce model-agnostic, intervention-based metrics:

Fidelity ($Fid$): Measures the change in the similarity score after intervening on the graph based on the explanation. Specifically, they compute $Fid_a$ (change when keeping edges above a threshold) and $Fid_b$ (change when keeping edges below the threshold).
Effect Overlap (EO): A generalized Jaccard similarity metric that quantifies the overlap between the signs of the fidelity values for the two interventions. A low EO indicates that the two interventions have distinct, complementary effects (e.g., one increases similarity, the other decreases it), satisfying the consistency criterion.
Sparsity Evaluation: The authors simulate increasing sparsity levels by removing the least relevant edges from the explanation masks and re-evaluating fidelity and EO. A robust explanation maintains its actionable and consistent properties even as the number of edges is reduced.

Experimental Setup

The study evaluates two families of explanation methods:

Mutual Information (MI) Methods: Specifically, GNNExplainer, which seeks a subgraph maximizing mutual information with the prediction.
Gradient-Based (GB) Methods: Direct gradient computation with respect to the adjacency matrix and Integrated Gradients.

These methods are applied to node embeddings generated by four unsupervised learning algorithms: Graph Autoencoders (GAE), Variational Graph Autoencoders (VGAE), Deep Graph Infomax (DGI), and Graph Contrastive Representation Learning (GRACE). Experiments are conducted on six datasets: citation networks (Cora, Citeseer, Pubmed), heterophilic graphs (Chameleon, Squirrel, Actor), and a knowledge graph (DBpedia50k).

Key Results

The experiments yield three primary findings regarding the performance of GB versus MI methods in the context of node similarity:

Actionability: Gradient-based explanations are consistently actionable. Interventions based on GB explanations (keeping edges above the threshold) predictably increase the similarity score, while interventions based on edges below the threshold predictably decrease it. In contrast, GNNExplainer (MI) shows inconsistent behavior; the effect of keeping high-value edges often depends on the specific embedding model and dataset, failing to produce a predictable direction of change across all scenarios.
Consistency: GB methods achieve significantly lower Effect Overlap (EO) scores (often near 0 or < 0.1) compared to MI methods (often > 0.4 or > 0.5). This indicates that GB explanations clearly distinguish between edges that increase similarity and those that decrease it. MI explanations frequently result in overlapping effects where both high and low-value edges produce similar changes in the score, failing the consistency criterion.
Sparsity: The actionable and consistent properties of GB explanations are preserved even when the explanation is pruned to retain only the top 10% of edges (90% sparsity). This suggests that GB explanations can be significantly simplified without losing their explanatory power, whereas MI explanations do not exhibit this robustness.

The authors also note that while MI methods sometimes show lower EO in specific cases (e.g., DGI with GraphSAGE), this is often due to near-zero effects (low actionability) rather than true consistency. In such regimes, the lack of significant impact on the score makes sign-based separation difficult for any explainer.

Significance and Claims

The paper claims to be the first to formally define and evaluate the problem of explaining node similarity in GNNs. Its significance lies in:

Bridging a Gap: It moves beyond the dominant focus on supervised tasks to address the explainability of continuous, unsupervised similarity scores.
Evaluation Framework: It provides a set of quantitative, intervention-based metrics (Fidelity, EO, Sparsity) that are necessary for assessing the quality of similarity explanations, which standard classification-based metrics cannot capture.
Methodological Insight: The results demonstrate that gradient-based methods are superior to mutual-information-based methods for this specific task. GB methods provide explanations that are not only actionable and consistent but also sparse, offering a more practical and interpretable tool for understanding why nodes are similar.
Generalizability: The proposed metrics are model-agnostic and applicable to any similarity function defined over node embeddings (e.g., Euclidean distance), offering a foundation for future development of explainable similarity search systems.

The authors conclude that while computational cost is a factor (GB methods are generally more efficient than the iterative optimization required by MI methods), the primary advantage of GB methods in this setting is their ability to provide reliable, directional, and sparse explanations for node similarity.