Meta-Path Explanations

Operates exclusively on heterogeneous information networks (HINs) containing multiple node types (e.g., Author, Paper, Venue) and edge types (e.g., writes, published_in, cites). Unlike homogeneous GNN explainers that treat all nodes identically, meta-path methods leverage schema-level semantics to produce explanations that map directly to domain concepts. A meta-path is formally defined as a sequence T1 --R1--> T2 --R2--> ... --Rn--> Tn+1 where T represents node types and R represents relationship types.

A meta-path is a template at the schema level; its instances are concrete paths in the graph. For example, the meta-path Author → Paper → Venue (APV) captures the semantic relationship 'authors who publish in certain venues.' The explanation mechanism identifies which specific path instances contributed most to a prediction. Key operations include:

• Path sampling: Random walks constrained by the meta-path pattern
• Path aggregation: Combining signals from multiple path instances via attention or pooling
• Relevance scoring: Assigning importance weights to each meta-path based on its predictive contribution

Modern architectures like HAN (Heterogeneous Graph Attention Network) and MAGNN employ hierarchical attention mechanisms to learn meta-path importance. The process operates at two levels:

• Node-level attention: Learns the importance of neighbors within a single meta-path instance
• Semantic-level attention: Learns the relative importance of different meta-paths for the downstream task

The final explanation is derived by inspecting these learned attention weights, revealing which semantic relationships the model found most discriminative.

Extends meta-path explanations by asking: 'Would removing this meta-path change the prediction?' The methodology involves:

• Path masking: Systematically ablating specific meta-path instances and measuring prediction shift
• Minimal sufficient paths: Identifying the smallest set of meta-paths that preserve the original prediction
• Contrastive explanations: Generating statements like 'The prediction is Author X → Paper Y because of the APV path; removing the APT (Author→Paper→Topic) path would not change the outcome' This provides actionable recourse by showing which semantic relationships are necessary versus incidental.

Rather than relying on predefined meta-paths, ProtGNN and similar frameworks automatically discover explanatory meta-paths during training. The model learns a set of prototype meta-paths that serve as canonical reasoning patterns. Each prediction is explained by measuring similarity between the input's meta-path instances and these learned prototypes. Benefits include:

• Case-based reasoning: Explanations take the form 'This prediction is similar to prototype P because both exhibit meta-path M'
• Domain-agnostic: No manual schema engineering required
• Interpretable latent space: Prototypes reside in the same semantic space as the input, enabling direct inspection

Meta-path explanations are evaluated on two primary axes:

• Simulatability: Can a human domain expert correctly predict the model's output given only the meta-path explanation? Higher simulatability indicates the explanation captures the model's true reasoning in human-understandable terms.
• Fidelity: Measured by the Fidelity+ metric—the accuracy of the original model when given only the explanatory meta-path subgraph as input. High fidelity means the explanation faithfully represents the model's decision process.
• Sparsity: The number of meta-paths in the explanation; fewer paths with high fidelity indicate concise, high-quality explanations.

A graph structure containing multiple types of nodes and multiple types of edges (relations). Unlike homogeneous graphs, these networks model complex real-world systems where entities and their interactions are fundamentally different.

• Nodes: Can represent authors, papers, venues, or drugs, proteins, and diseases.
• Edges: Represent distinct relationships like 'cites,' 'writes,' or 'treats.'
• Meta-paths rely on this diversity to define meaningful traversal patterns across types.

A similarity measure designed specifically for heterogeneous information networks that evaluates the similarity between two same-typed nodes based on the meta-paths connecting them.

• Core Logic: Two nodes are similar if they share highly visible, symmetric meta-path neighbors.
• Visibility: Defined by the number of path instances between them.
• Use Case: Often serves as a baseline or feature input before applying more complex meta-path explanation techniques to GNNs.

A seminal GNN architecture that uses hierarchical attention mechanisms to process heterogeneous graphs. It first aggregates node-level neighbors based on specific meta-paths, then aggregates semantic-level information across multiple meta-paths.

• Node-Level Attention: Learns the importance of neighbors within a single meta-path instance.
• Semantic-Level Attention: Learns the importance of different meta-paths for the final task.
• Interpretability: The learned semantic attention weights provide a natural, built-in form of meta-path explanation.

A specific, concrete sequence of nodes and edges that follows a defined meta-path schema. While a meta-path is the abstract pattern (e.g., Author-Paper-Author), an instance is a real path in the graph.

• Example: For meta-path Author → Paper → Author, an instance is John → Paper_X → Mary.
• Explanation Role: Meta-path explanation methods often rank these specific instances to show exactly which relational chain most influenced a prediction.

An architecture that applies the Transformer's self-attention mechanism directly to graph-structured data. It treats nodes as tokens and uses structural or positional encodings to capture graph topology.

• Global Attention: Unlike message-passing GNNs, it can directly attend to all nodes, naturally capturing long-range meta-path dependencies.
• Attention Weights: The raw attention scores can be analyzed post-hoc to extract the most relevant node-to-node interactions, effectively revealing the meta-path instances the model prioritized.

An extension of the Graph Transformer designed natively for heterogeneous graphs. It projects different node and edge types into a unified space using type-specific linear projections and attention parameters.

• Mutual Attention: Computes attention between node pairs by factoring in their types and the relationship between them.
• Meta-Relation Triplets: The attention is parameterized by <source node type, edge type, target node type>, making the model inherently aware of the meta-path components it is traversing.