TACENR: Task-Agnostic Contrastive Explanations for Node Representations

1. Problem Statement

Graph representation learning (e.g., node2vec, GNNs) successfully encodes graph-structured data into latent vector spaces for downstream tasks like classification and link prediction. However, these representations are often opaque.

• Limitation of Existing Methods: Current explainability techniques primarily focus on task-specific scenarios (explaining a specific prediction) or explain individual dimensions of a representation vector.
• The Gap: There is a lack of methods that explain the entire node representation as a holistic entity, independent of any downstream task. Furthermore, existing methods often fail to capture the full spectrum of information encoded in representations, which includes:
  1. Proximity: Neighboring nodes having similar representations.
  2. Structural Similarity: Nodes with similar topological roles sharing representations.
  3. Attribute Similarity: Nodes with similar features clustering together.

2. Methodology: TACENR

The authors propose TACENR (Task-Agnostic Contrastive Explanations for Node Representations), a local explanation method that identifies which features (attributes, proximity, and structure) contribute most to a node's position in the representation space.

Core Architecture

1. Feature Enrichment:
   For a target node $v$, TACENR constructs a combined feature vector $h_{v,u}$ relative to another node $u$. This vector concatenates:

   • Node Attributes ($x_v$): Original input features.
   • Structural Features ($s_v$): Metrics like degree, average neighbor degree, clustering coefficient, and triangle counts.
   • Proximity Features ($p_{v,u}$): Metrics like shortest-path distance or Personalized PageRank (PPR) scores.

2. Contrastive Learning Framework:
   Instead of predicting a label, TACENR learns a similarity function in the representation space.

   • Affinity Set ($S^+_v$): The $k_{aff}$ nodes most similar to $v$ in the representation space.
   • Divergence Set ($S^-_v$): The $k_{div}$ nodes least similar to $v$.
   • Objective: Train an interpretable surrogate model $g$ (e.g., Linear Regression) to predict the similarity $sim(z_v, z_u)$ between the target node and nodes in $S_v$ based on the feature vector $h_{v,u}$.
   • Loss: Minimize the discrepancy between the true similarity and the predicted similarity: $\sum L(sim(z_v, z_u), g(h_{v,u}))$.

3. Weighted Similarity Measure:
   To prioritize informative dimensions, TACENR uses a weighted cosine similarity:
   $$sim(z_v, z_u) = \frac{\sum w_j z_v^{(j)} z_u^{(j)}}{\sqrt{\sum w_j (z_v^{(j)})^2} \sqrt{\sum w_j (z_u^{(j)})^2}}$$

   • Supervised Setting: Weights ($w$) are derived from gradients of the predicted class probability with respect to the representation (highlighting dimensions driving the prediction).
   • Unsupervised Setting: Weights are derived from the global variance of each dimension (highlighting dimensions that distinguish nodes effectively).

3. Key Contributions

• Task-Agnostic Explanation: TACENR explains the representation vector itself, not a downstream task prediction, making it applicable to both supervised and unsupervised models.
• Holistic Feature Attribution: It uniquely integrates and quantifies the contribution of proximity, structural, and attribute features simultaneously, rather than isolating them.
• Contrastive Learning for Interpretability: It introduces a contrastive learning approach to train the surrogate model, forcing it to learn what makes nodes similar or dissimilar in the embedding space.
• Adaptive Weighting: The method adapts its similarity metric based on whether the representation is supervised (gradient-based weights) or unsupervised (variance-based weights).

4. Experimental Results

The authors evaluated TACENR on datasets (Cora, CiteSeer, PubMed, PPI, BA-Shapes) using models like node2vec, role2vec, GCN, GAT, and GraphSAGE.

A. Unsupervised Representation Analysis

• Synthetic Data (BA-Shapes): TACENR successfully distinguished between "house-motif" nodes (driven by local structural features like degree and triangles) and "base" nodes (driven by global proximity features like PPR standard deviation).
• Real-World Data:
  • Cora: High homophily led to attribute features being important alongside structural ones.
  • CiteSeer: Sparse attributes made structural features (neighbor clustering, triangles) dominant.
  • PPI: Dense, high-degree graphs relied heavily on node attributes (biological info) rather than local structure.
  • Model Differences: Random-walk models (node2vec) relied heavily on proximity; GNNs relied on local neighborhood statistics (average neighbor degree).

B. Comparison with Task-Specific Methods

TACENR's supervised variant was compared against GraphLIME, GNNExplainer, GraphSVX, and COMPINEX.

• AOPC Metric (Area Over the Perturbation Curve): TACENR achieved higher AOPC scores, indicating that removing the features it identified caused a larger drop in model performance (proving they are truly important).
• Noise Filtering: When noisy features were added to datasets, TACENR (along with COMPINEX) assigned significantly less importance to them compared to other methods, demonstrating robustness against irrelevant information.

C. Ablation Study

• Feature Selection: Adding explicit distance features improved explanations for real-world graphs (Cora) but had less impact on synthetic motif graphs.
• Weighting: Using weighted similarity (gradient-based for supervised, variance-based for unsupervised) significantly improved the quality of the surrogate model (lower MSE/MAE) compared to unweighted baselines.
• Surrogate Model: Simple Linear Regression performed comparably to or better than complex regularized models (Ridge, Lasso, HSIC Lasso), justifying its use for maximum interpretability.
• Contrastive Ratio: Supervised representations required a high ratio of similar nodes (80% affinity) for best performance, while unsupervised representations required a high ratio of dissimilar nodes (80% divergence) to learn structural patterns effectively.

5. Significance

• Bridging the Interpretability Gap: TACENR moves beyond "why did the model predict X?" to "why does this node look like this in the embedding space?"
• Algorithmic Insight: The method provides a diagnostic tool to understand how different graph learning algorithms (e.g., GNNs vs. Random Walks) encode information. For instance, it confirmed that GNNs heavily encode local neighborhood statistics, while node2vec encodes proximity.
• Generalizability: By being task-agnostic, it offers a unified framework for interpreting any graph representation, regardless of whether it was learned for classification, clustering, or link prediction.
• Practical Utility: The ability to filter out noisy features and identify the true drivers of representation similarity makes it a valuable tool for debugging graph models and understanding complex graph data.