Explaining Node Embeddings
Authors: Zohair Shafi
Ayan Chatterjee
Tina Eliassi-Rad
Venue: Accepted by TMLR ()

Abstract: Node embedding algorithms produce low-dimensional latent representations of nodes in a graph. These embeddings are often used for downstream tasks, such as node classification and link prediction. In this paper, we investigate the following two questions: (Q1) Can we explain each embedding dimension with human-understandable graph features (e.g. degree, clustering coefficient and PageRank). (Q2) How can we modify existing node embedding algorithms to produce embeddings that can be easily explained by human-understandable graph features? We find that the answer to Q1 is yes and introduce a new framework called XM (short for eXplain eMbedding) to answer Q2. A key aspect of XM involves minimizing the nuclear norm of the generated explanations. We show that by minimizing the nuclear norm, we minimize the lower bound on the entropy of the generated explanations. We test XM on a variety of real-world graphs and show that XM not only preserves the performance of existing node embedding methods, but also enhances their explainability.

Published in Transactions on Machine Learning Research (04/2025)
Explaining Node Embeddings
Zohair Shafi
shaf..2@hnorthhasteev...d
Northeastern University Boston, MA, USA
Ayan Chatterjee Northeastern University Boston, MA, USA
chatterjee.oy ay@hoottheatterr.cco edu
Tina Eliassi-Rad Northeastern University Boston, MA, USA
t. telinssinaddhhorthheseeee
Reviewed on OpenReview: https: httpe://openrevieel net/ permf id= QQ28uPaFb3
openreview.
Abstract
Node embedding algorithms produce low-dinensional latent representations of nodes in a graph. These embeddings are often used for downstream tasks, such as node classification and link prediction. In this paper, investigate the following two questions: (Q1) Can explain each embedding dimension with
graph features (e.g. degrec, clustering coelficient and PageRank). (Q2) How can we modily existing node embedding algorithms to produce embeddings that can be easily explained by uumaan-undestanddable graph features? We find that the answer to Q1 is yes and introduce a now framework called XM (short for EXPLAIN EMBEDDING) to answer Q2. A key aspect of XM involves minimizing the nuclear norm of the generated explanations. We show that by minimizing the nuclear norm, we minimize the lower bound on the entropy of the generated explanations. We test XM on variety of real-world graphs and show that XM not only preserves the performance of existing node embedding methods, but also enhances their explainability.
1 Introduction
Graph datasets are ubiquitous from social, to physical, and biological networks. The abundance of graph data has inspired the development of models and algorithms the field of graph machine learning (Chami et al. 2022), a popular task being node embedding[] where nodes are embedded in a low-dimensional latent space. Many algorithms exist for embedding a graph's nodes into a low-dinensional space. Zhang al. (2021a) compared variety of such algorithms attention has been devoted to explainable graph machine learning (Burkart & Huber 2021), in part because the performance of such models can often be misleading (Stolman et al.) 2022), Meenad & Seshadhrij 2024). Recent work on explaining graph machine learning revolves around explaining decisions made on downstream tasks (Pope et al.) 2019)) (Baldassarre & Azizpour 2019), (Ying et al. 2019). (Luo et al. 2020), (Vu & Thai 2020), Yuan et al. (2021). (Liu et al.J [2018]] An outlier here Gogoglou et al.] (2019)'s work. They investigate individual dimensions of embedding and define an interpretability score for each dimension to measure how well each dimension defines subgroup of nodes (see Section for details).
tasks such greedy routing and link prediction. Recently, much
In this work, our aim is to bridge the gap between Human--nderstandabll features and node embeddings in graphs. In natural language processing (NLP), each dimension of an embedding can often be associated with a well-defined, interpretable concept. For example, a dimension might capture the concept gender, as demonstrated by the famous "king and queen" analogy (Ethayarajh al. 2018 However, transferring
Somet imes node embedding is referred to graph embedding.

---

Published in Transactions on Machine Learning Research (04/2025)
this idea to graph data is not straightforward. For example, consider network of academic collaborations, such as the PubMed citation network (Roberts 2001). If we embed this network into three dimensions using a traditional method, the first dimension might group nodes with many connections (high node de- gree), the second might cluster nodes by shared research topics (communitics), and the third could isolate interdisciplinary nodes (high node centrality). However, interpreting these dimensions in terms of concrete and numan-understandable features is not trivial, as each dimension typically encodes a complex mixture of several attributes. This lack of interpretability presents significant obstacle, especially when understanding and trusting the model's output is just as important prediction.
To address this, we use glossary for graphs, comprising of well-cstabliseed graph features such as node degree, clustering coefficient, node betweenness centrality, and other topological features. These features are the cornerstone of characterizing any graph dataset (Albert & Barabási 2002
Newman 2003] and have
previously been used graph machine learning tasks (Henderson et al.) 2012 Khoshraftar et al.) 2021 Rossi et al., 2018). These fcatures serve as building blocks that can help explain the dimensions graph embeddings. For example, a person node with high degree is person with many friends. We introduce framework called X.M (short for EXPLAIN EMBEDDING) that makes node embeddings explainable by associating cach dimension of the embodding with these well-defined, human-understandabll graph features. Following Henderson et al. (0022), we refer to these features as "sense" features. For example, one embedding dimension might correspond to the node's degree, while another might relate to its clustering coefficient or centrality. These features can be tailored to specific domains.
Problem Definition
We are given the following:
A graph G = (V, E, where V represents the set of vertices (nodes), E' represents the set of edges (links), and X represents the node feature matrix (with [V] = n nodes)
A graph-embeddinng algorithm y (G) E Raxd that maps each node k E V to a ad d-dimensional vector parameterized by 0
A list of sense features: Vk E V, V R//1
For each node & E V, XM learns an Explain matrix Es E Rdxf, Each row of the Explain matrix corresponds a dimension and each column corresponds to a sense feature. Table summarizes the notation used throughout this work.
Concretely, present our investigation of the following two questions. Q1: Can we explain dimensions of node embedding method with human-understandall features are degree, clustering coefficient, eccentricity, and PageRank. These features can be any set of features that a practitioner decides to use and are not limited to graph features. We will refer to them as "sense" features. Q2: Can we modify existing node embedding algorithms to produce embeddings that are explained with sense features? If so, how? We present a new framework called XM (short for EXPLAIN EMBEDDING) to answer this question. XM adds two constraints to existing objective function for node embedding: (a) sparsity w.r.t. explaining embedding dimensions. We provide an ablation study to analyze the impact of each constraint. XM outputs explainable node embeddings that are tested on a variety of real-world graphs, achieving downstream task performances comparable to the state of the art.
graph features? Examples of such
embedding dimension and (b) orthogonality between
Our main contributions are as follows:
We present a method for understanding what each dimension of a node embedding method means, with respect to a set of undrstadddertt sense features defined on nodes. This helps us to understand the placement of a node in the embodding space. These explanations are independent of any downstream task and are in the form of an Explain matrix, whose rows represent embedding dimensions and whose columns represent sense features.
2

---

Published in Transactions on Machine Learning Research (04/2025)
Symbol
Description
Graph
V
Set of vertices of graph G Set of edges of graph G Node feature matrix for graph G
X
Number of dimensions used to embed graph G d- d-dimensional embedding vector of graph G' for node i
Number of sense features Sense feature vector for node Explain matrix for node i Von Neumann entropy of matrix A Bregman Divergence between matrices A and B
fr
E, H(A)
D(A
Table Notation Table
To evaluate Explain matrices, we use their nuclear norms and show that minimizing the nuclear norm of an Explain matrix removes noise and reduces the lower bound of its entropy, which is a desirable property.
We introduce the XM framework, which modifies the objective function of any existing node em- bedding method to produce embeddings that provide better quality explanations. We analyze the impact of each of XM's constraints (sparsity and orthogonality) through an ablation study and show that using both constraints leads the largest reduction in nuclear norms. We demonstrate the effectiveness of XM by modifying number of embedding algorithms different real-world datasets and evaluating them the downstream lask of link prediction.
2 Related Work
Interest in explaining machine learning models has attracted much attention in recent years, in part because the performance of such models can often be misleading (Burkart & Huber 2021 With the increasing application of machine learning to graph data, the development explainable models on graphs becoming necessity. Figure provides laxonomy of various explanation methods on graph machine leaning models. We divide the existing literature into supervised and unsupervised methods.
Supervised Methods Most of the work on explainable models for graph machine learning falls into this category and focuses on explaining predictions for downstream tasks (such as link prediction or node clas- sification). We further divide supervised methods into two categories: (1) gradient-based explanations and (2) subgraph-based explanations. Examples of gradient-based explanations include the works Pope eet al. (2019) and Baldassarre & Azizpour (2019). They extend the concept. of explainable predictions from image data network data by using gradient-based approaches to visualize and understand the predictions of Graph Convolutional Networks (GCNs). There numerous methods under subgraph-based expla- nations. These methods focus on finding subgraph that contributes to particular classification. We divide these methods into three groups:
Direct subgraph extraction:
Ying et al. (2019) introduce GNNExplainer, which tries to find the minimal subgraph and the most relevant. subset of node features that key to the prediction of the GNN for given instance. GNNExplainer maximizes the mutual information between the original prediction and the prediction of the extracted subgraph. Since the explanations of GNNEmplainer are customized for each instance, it cannot provide explanations for a set of instances.
Luo et (2020) extend GNNExplainer by introducing PGEzplainer, which uses genera- tive probabilistic model for graph data to learn the underlying structures from the observed
3

---

Published in Transactions on Machine Learning Research (04/2025)
Gradient-based explanations
Pope et al.
2019 Baldas- Azizpour 2019
Ying et al.
2019: Luo et al. (2020):
Supervised methods
Direct subgraph extraction
Lin al.
[2000 : Spineeli al.
2022 : Vu & Thai (020)] Yuan et al.
2021 Sch licttkull et al. 2021
Subgraph- based explanations
Perturbation- based explanations
Gui
2022
Duval & Malliaros 2021
Huang
2022
2021
Subgraph ex- traction using surrogate models
Li et al.
(002b) ; Duval Malliaros
Graph explanation methods
2022
Zhang ct al. (2021b)
Taxonomy- based explanations
Liu 2018
Objective- function based explanations
Duong et
2019
Explanations per embedding dimension
Unsupervised Methods
Gogoglou al.
2019
Khoshraftar al.
2021
Node-property explanations
Dalmia et al.
2018 Bonner al.
2019
XM
Embedding- ex- planations
Rossi al.
2018
XM
Figure 1: Taxonomy of various graph explanation methods. Section 2 method.
provides brief description for each

---

Published in Transactions on Machine Learning Research (04/2025)
data. PGEaplatner uses these underlying structures explanations and models the underly- ing structure edge distributions, sampling the explanatory graph. The generative model in PGExplainer is parameterized with deep neural network to jointly explain the predictions of multiple instances.
Spinelli et al. (2022) propose meta-explainer to improve the quality of explanations during training time. Their goal is to steer the optimization procedure towards minima that allow post-hoc explainers such as GNNFxplainer and PGEsplainer to achieve better results.
Vu & Thai (2020) introduce TGM-Baplainer, which has similar goals as GNNExplainer:: iden- tify subgraphs and relevant features for the prediction of particular instance. In contrast GNNExplainer PGM-Eaplasie uses probabilistic graphical models to explain substructures in network. This allows PGM-Baplainer to model uncertainty and provide probabilistic expla- nations.
Yuan et al. 2021 use Monte Carlo tree search to search all possible subgraphs and identify sub- structures that are important to the downstream prediction task. To compute the importance of each subgraph to the prediction task, they use Shapley values (Lundberg & Lee 2017).
Schlichtkrull et al. (2021) learn a simple classifier that predicts if an edge can be dropped without deteriorating the model's performance. The remaining edges are then analyzed for interpretability.
2. Perturbation-based explanations: These methods primarily extend LIME (Ribeiro et al. 2016 and SHAP [Lundberg & Lee 2017) to GNN.
Gui et al. (2022) propose FlowX, which is a method for explaining the predictions of a GNN by identifying important message flows using Shapley values. A flow is defined as the set of T messages that are passed around in a message- gressage-passin GNN with layers. Each flow for a given node is then treated as player for the Shapley formulation.
Huang et al. (0022) propose GraphLIMF. which aims to explain the predictions of a GNN by (i) extending LIME (Ribeiro et al. 2016) to operate on graph data and (ii) using a surrogate model (c.g., a linear regression). GraphLIME provides local explanations because its perturbations are limited to the local neighborhood of nodes.
Duval & Malliaros (2021) propose GraphSVX, whose goal is provide explanations for the predictions of GNN by using Shapley values and surrogate model (e.g., linear regression). Shapley values determine the "fair contributions" of each node, edge, or feature to the prediction of the model.
3. Subgraph extraction using surrogate models:
Li et al. (002bb) student-teacher model to distill knowledge from large pre-trained GNN to shallow GNN, while explicitly learning the contribution weights between two nodes using attention mechanism.
Zhang et al. (2021b) propose RelEz, which identifies important nodes and links in the prediction of a given node. It treats the graph machine-learnnn model as black box and learns relational explanations. Explanations come in the form of a mask matrix with sparsity constraints.
Lin et al. (2200) also use sparsity raints. They propose GISST, which combines an attention mechanism and sparsity regularization to yield the subgraph and node features that are key to the downstream task.
Schnake et al. (2021) propose GNN-LRP, which uses layer-wise relevance propagation and outputs collection of walks that are relevant for given prediction.
A useful tool under supervised methods is GraphXAI (Agarwal el al. 2023 It provides a framework for GNN explainers. In particular, GraphXAI provides a synthetic graph generator called Shape graph generator. Their generator generates ground-trute -trth explanations for homophilic, hetcrophilic, and attributed graphs. We refer the reader to survey by Li et al. (202aa) on supervised methods for explaining graph machine learning models.
5

---

Published in Transactions on Machine Learning Research (04/2025)
Unsupervised Methods Our work is independent of the downstream task. Under unsupervised methods, we have five calegories:
Taxonomy-basee explanations: Liu et al. (2018) use network homophily and hierarchically cluster nodes based on the emboddings to create a taxonomy. Explanations come in the form of items the generated laxonomy.
2. Objective-lunction based explanations: Duong et al. (2019) propose loss function that minimizes the number of connections between communitics, and in doing so, the nodes in community are embedded closer to each other. Explainability comes in the form of each dimension defining the degree of membership to a community.
3. Explanations per embedding dimension:
Gogoglou et al.
(201)) define an interpretability score for each dimension in node embedding.
Tt measures how well dimension is associated with a subgroup of nodes.
Khoshraftar et al. 2021 define the interpretability of an embedding algorithm as the extent to
which its embedding dimensions can represent "important" nodes in a category with extreme values, where "importance" is based on centrality measures.
4. Node-property explanations: Dalmia et al. 20188 and Bonner et al. (0019) study how good an embedding algorithm is explaining certain node properties such as node degree or node centrality, This is akin to what we have referred to "sense features'.
5. Embeddingg-aase based explanations: Rossi et al. (2018) use features akin to what we refer to as "sense features" " as base features, to which relational feature operators are applied to generate embeddings. Explainability comes in the form of examining which relational operators were used to generate the embeddings.
Compared with existing literature, our proposed method XM is independent of any particular downstream task, can be used to extend any existing embedding algorithm, and works with any set of sense features. It also provides explanations on the node- and dimension-level.
3 Explaining embeddings
3.1 Sense-making
In order explain each embedding dimension, we define set of luman--nddesstandlble node features, called "sense" features. We use global and local properties of the network as our "sense" features. Following Ghasemian et al. (2020), we look at the following 15 features: degroe, weighted degree (if the edges are weighted), clustering coefficient (Barabási 2016), average of the personalized PageRank vector, standard deviation of the personalized PageRank vector, average degree of the neighboring nodes, average clustering coefficient of neighboring nodes, number of edges in the ego net, structural hole constraint (Burt) 2004). betweenness centrality (Freeman 1977), eccentricity, PageRank, degree centrality, Katz contrality (attz 1953) and eigenvector centrality Newman 2010). These features are well-established, easily computable, and provide comprehensive glossary for graph analysis providing insights into the overall structure of the graph (e.g., average degree, clustering coefficient, number of triangles) well detailed information at the individual node level (e.g., degree, betweenness centrality). Since some of these features are highly correlated, we choose to focus on the following subset of them throughout this work: degree, clustering coefficient, standard deviation of the personalized PageRank, average degree of the neighboring nodes, average clustering coefficient of neighboring nodes, eccentricity and Katz centrality.
Given an embedding vector for a node k. Th E Rdxl and corresponding sense feature vector f R (where the number of dimensions of the embedding space and is the number of sense features used, each being normalized between O and 1), we compute the element-wise similarity between the embedding

---

Published in Transactions on Machine Learning Research (04/2025)
vector for node and its corresponding sense feature vector follows:
Uk & P
ER
(1)
1 f
We call E E Rdx the Explain matrix (we drop the subscript k corresponding to node k, for brevity). Normalized to a range of 0 and 1, each row of the Explain matrix corresponds to a dimension in the embedding space and each column j corresponds to a sense feature. The value Eig corresponds to how much the dimension is defined by the sense feature j. This matrix E, helps us to investigate the linear relationships between the sense feature vectors and the embedding vector.
3.1.1 Real world example
We look at the Karate Club Network for concrete real-world example. We chose this network for brevity and pedagogy and discuss larger networks in the Results section. Figure 2 A) shows the original Karate Club Network (Zachary 1977). We embed the Karate Club graph into 16 dimensions using DGI Velickovic et al. (2019). We then visualize these embeddings by projecting them into 2 dimensions using UMAP (Melnnes jet al. 2018) (shown in Figure 2 B))- For a detailed node-wise view, we look at the president of the club (node 34), the instructor (node 1), and a random student (node 12). We use Equation (1 to compute the Explain matrix for each node. Figure 2 C) corresponds to the Explain matrix for the instructor (node 1), Figure 2DD) corresponds to the random student (node 12), and Figure 2 to the president (node 34). Examining the Explain matrices for nodes 1 and 34 (Figures 2 C) and (D)), we see similar sense features (like degree, the standard deviation of the personalized PageRank, Katz centrality and average neighbor clustering) stand out and are explained most by dimensions 14 and 15 (note that the specific dimensions are not constant). Also, observe that these two nodes are placed close together in the embedding space low-dinensional visualization in Figure B)). We also see that the Explain matrix for node 12 (Figure DD) is different, and has average neighbor degree and eccentricity as its distinguishing features.
3.1.2 Choice of Sense Features
The set of features defined earlier is not exhaustive but was chosen to ensure consistency across different datasets and are well-established in domains that represent data as graphs (Albert & Barabási] 2002 New- man 2003). For datasets that already have inherent node features, we deliberately exclude them and instead use sense features to enable fair comparisons and analysis across various datasets.
Here, we explore the impact of using different sense features. Observe how the sense features defined above are primarily structural, meaning they capture the neighborhood structure of nodes without considering their specific positions within the network. Consequently. nodes with similar neighborhood structures in the same network will have similar sense feature vectors. The explanations produced by these sense features would therefore be more role-based, i.e. would emphasize the role of a node in the network (e.g. gatekeeper node or hubs).
However, if the explanations one is looking for are more positional in nature i.e., explanations that focus on a node's location relative others in the network, structural sense features might not be as effective. To demonstrate the differences in sense features, of "positional" sense features. We follow You et al. (0119) in defining the concept of anchor nodes and use simple features such as the number of hops to the anchor node as our positional sense features. As before, we embed the Karate club network using DGI into 16 dimensions and generate the Explain matrices for each node in the graph following Equation [
well as what the Explain matrix contains, we define a set
Figure g visualizes the Explain matricos for nodes (instructor), 12 (random node), and 34 (president). We select four nodes as anchor nodes. Nodes 3 and 9 behave as bridge nodes between the communities of the instructor and the president. Nodes 5 and 33 only have connections to the instructor and president communities, respectively. We compute the features for each node i in the graph, as the number of hops from
Positional explanations look the role of node instead of its community.
7

---

Published in Transactions on Machine Learning Research (04/2025)
(A)
(B)
22
10
11
29
25
14
20
26
32
24
(C) Node (Instructor)
(D) Node 12 (Random Node]
(E) Node 34 (President)
44
Dimensions
Dimersions ons
144
Dighte
FRt Stansue
Eart Conratoy
Ehnlering
Jaen Eccornictt
Custer Couficaiit
Den (004
Cerraay
Big
Sense Features
Sense Features
Sense Features
Figure (A) Karate Club Network Zachary
1977
(B) We embed the Karate Club network into 16
dimensions using DGT and visualize it in 2 dimensions using UMAP (McInnes al. 2018). (C) Explain
matrix for the instructor (node 1). (D) Explain matrix for random student node (node 12). (E) Explain
matrix for the president (node 34). Examining the Explain matrices for each of these nodes gives
understanding of their plaaeeent in the embeddingg space. Observe how features such as degree, personalized page rank etc., stand out for nodes and 34 (subplots (C) and (E)) and features like average neighbor degree stands out for the random student node (subplot (D)).
(A) Node (Instructor)
Node (Random Node)
(C) Node (President)
Dimensions
Limensions
Dimensions
Arres Hodee 13
CHOS Hodfe
HOBS to Logal Hoode
Hodi Sohul (M000
tridc food
Wops Mosee Toaal
(Noee
Sense Featurres
Sense Features
Sense Features
Figure 3: Visualization of Explain matricos for three nodes in the Karate Club network node 1 (instructor, A), node 12 (random node, B), and node 34 (president, C) based on positional sense features defined as number of hops to 4 anchor nodes (nodes 3, 5, 9 and 33). The matrices highlight the similarity between nodes and 12 due to their relative positions in the network and distances from the four anchor nodes, in contrast the structural feature- baature-based similarities observed in Figure 2
the given node to these four anchor nodes. While in Figure 2 nodes and 34 displayed similar Explain matrices due to their comparable structural features, Figure reveals greater similarity between nodes 1 and 12. This similarity due their relative positions in the graph and their respective distances from each of the anchor nodes. This contrast illustrates how positional sense features can yield different insights compared to structural features.
8

---

Published in Transactions on Machine Learning Research (04/2025)
3.2
Our Proposed Framework: XM (eXplain eMbedding)
3.2.1
Quantifying the Quality of Explanations
Given a method lor generating explanations, we quantify the quality of these explanations. The (potentially) large number of dimensions and sense features drives us use heatmaps visualize their relationships. Figure 2 shows the heatmap visualization of the Explain matrix. Notice that noisy Explain matrix is hard to interpret, but sparser Explain matrices with each dimension being defined by unique sets of sense features are easier to interpret.
Since this translates to a denoised Explain matrix, we draw inspiration from the work on image denoising using nuclear norm minimization Gu et al. (2014), Xu et al. (2017)] ). In this context, the muclear norm serves as quantitative metric, with lower muclear norms indicating coherent and interpretable explanations.
3.2.2 The Importance of Rank: Interpreting Rank Reduction through Nuclear Norms
Given a matrix of rank r, one can reconstruct it using r rank-1 matrices. The nuclear norm of a matrix is the tightest convex bound of the rank function over the unit ball of matrices with bounded spectral norm Thus, the difference in muclear norms of two matrices gives us a lower bound on how many more rank-1 matrices are nceded to reconstruct the matrices.
For example, SDNE the EU Email dataset (with d = 128) produces Explain matrix whose nuclear norm is = 0.97 (see Figure 12]. However, its Explain matrix has nuclear norm of ~ 1.8 + 0.26 when the sparsity constraint is used, ~ 2.1 + 0.29 when the orthogonality constraint is used, and ~ 1.6 + 0.39 when both constraints are used. This means that the Explain matrix for the EU Email dataset can be approximated with two rank-1 matrices when the sparsity and orthogonality constraints are used, instead of oight rank-1 matrices with no constraints used. (The error bars in these measurements represent the standard error, underscoring the statistical significance of the improvements observed.)
3.2.3 Augmenting Embeddings
It is important to avoid a perfect one-to-one mapping between the embedding dimensions and the sense leatures. If one-to-one correspondence is imposed, then the network information beyond that contained in the simple node sense features is lost while creating the embeddings. Such embeddings would not capture higher-order network properties that contribute to downstream tasks (Ghasemian et al. 2020). resulting in poor performance. Using sense features themselves embedding vectors performing dimensionality reduction on large set of sense features suffers from the same issue of not capturing higher-order network properties. To that end, we propose XM, framework for augmenting existing embedding algorithms that includes sense feature information, as well as information that the underlying algorithm captures.
XM incorporates sense features and achieves a less noisy Explain matrix by imposing a sparsity constraint along the columns of the Explain matrix. This aims zero-out features with small contributions to the definition of a dimension. Following recent advances in dimensional contrastive learning by Nguuee et al.] (202)), XM also imposes orthogonality constraint along the rows of the Explain matrix which aims to have embedding dimensions that are defined by different sets of sense features. XM uses the two constraints, sparsity and orthogonality, instead of directly minimizing the nuclear norm for added control over the objective function (see section 4.5). The loss terms for the two constraints can be written as follows.
Tsparse |:
Vj columns
(2)
Lortho ||E 11l
Vi E rows Vjj E columns
(3)
These two additional loss terms are then addod to the objective functions of existing embedding algorithms. As an example, the objective for SDNE consists of 3 loss terms a first order loss term, a reconstruction
Note that the rank of matrix non-convex function, which makes optimization problems involving the rank hard solve. The nuclear norm serves as convex proxy for the rank.
9

---

Published in Transactions on Machine Learning Research (04/2025)
error term and regularization term:
LSDNE = aLifirat + B + vLregg
(4)
where a, and tunable hyperparameters.
We augment this objective as follows:
LSDNE aL1 + 3I2 + v.reeg + tosppree + 8Lortho
(5)
which refer to as SDNE+XM. Here, and 5 are hyperparameters for the sparsity and orthogonality constraints, respectively.
3.2.4 Nuclear Norm and Matrix Entropy
For given node, assume there exists embedding y" (we drop the vector notation y for brevity), which is the optimal embedding. Let y*m be the embedding for the same node found by XM. Recall that we define the Explain matrix E as:
E" 12' f
(6)
11 ||
fl
Fm f7
ETm
(7)
Let
A E E B E Eum?
(8)
(9)
Observe that and B are now symmetric matrices and therefore have an orthonormal basis of eigenvectors with real eigenvalues.
We then have
A = U
where Uis orthonormal and Σ is diagonal
(10)
AA IT USUT
Vz 2 0 R"
(11)
A = Σ 2)
(12)
2 Az 0
(13)
This shows that A a positive semi-definite (PSD) matrix. The same proof applies for the matrix B. Given that A and are PSD, Yu (2033) and Bach (0022 show that when the Von Neumann entropy of PSD matrix defined as
H(A) -tr(A log A]
(14)
and its associated Bregman Divergence is definod as
D(A = tr[A(log A - log B)] tr(A) + (r(B)
(15)
the following extension of Pinsker's inequality holds true:
D(AIIB) > - |I I| B1
(16)
10

---

Published in Transactions on Machine Learning Research (04/2025)
Table 2: Embedding algorithms used. Classification of these algorithms was adopted from Chami et al. Chami et al. (2022), where we pick two algorithms that allow for a node feature matrix, and two algorithms that do not. Providing sense features as node attributes is a simple method of incorporating the sense features into the embeddings. XM variants outperform the original versions in terms of nuclear norms.
Algorithm
Node Features
Sub Type Autoencoder Skip Gram
SDNE
Wang et al.
(0016
No (X = I)
LINE
Tang et al. 20055]
No (X = I)
DGI Ve iccovicc et al. (2019)
Yes (X +
Message Passing
GMI Peng et 2020
Yes (X + I)
Message Passing
We also know that the nuclear norm is an upper bound on the L2 norm, i...
|||||- 2 ||A||2
(17)
This gives
1
D(AIIB) 2 2 51A--BIB
2 II B13
(18)
D(A 2 I11 11 2 2 2 B + |B
(19)
Recall that
B= B= Ezm?
(20)
which is explicitly minimized the orthogonality constraint in the XM framework. Notice that the || term is constant since it is the optimal solution. Thus, by minimizing the L2 norm of B, we reduce the lower bound in the entropy between an optimal explanation E" and the explanation Eum found by XM. The relationship between entropy and prediction has been well known for a long time (hannon (151)). More recently, the impact of entropy reduction on machine learning explanations has gained importance. Amanova et al. 2024) present a method for image explainability that identifies input features affecting the model's output entropy. Reducing prediction entropy can improve explanations by making the model's decisions more confident. Press al. (2024) and Waan et al. (2020) demonstrate that entropy minimization during test time optimizes model confidence and accuracy, revcaling strong correlation between lower output entropy and higher accuracy. As entropy decreases, model predictions become more decisive, leading to clearer and more accurate explanations of the model's behavior.
4 Experiments
In order to demonstrate our method, we apply our augmentation to 4 unsupervised embedding algorithms across 6 different networks. We look at the (axonomy of machine learning on graphs by Chami et al.] (202)) and pick two algorithms from the branch where X = I, (i.e. these algorithms do not incorporate node attributes) and two algorithms from the branch where X * (i.c. these algorithms do allow node attributes). We choose these algorithms because providing sense features as node attributes is a simple and straightforward method to incorporate the sense features into the embeddings. However, achieve lower nuclear norms by augmenting the objective function.
shown below,
Table 2 shows the algorithms selected and Table B summarizes the datasets used. These have been chosen to span a range of average degrees and clustering coefficients.
We start by visualizing the Explain matrices for the Karate Club network embodded using DGL. We then discuss quantitative metries for the networks listed in Table g embedded using each of the four embedding algorithms from Table g and their XM variants. Following this, dive into case study on the largest
11

---

Published in Transactions on Machine Learning Research (04/2025)
Table 3: Real-world networks used our experiments. (k) refers to the average degree, 9 refers to the standard deviation of the degroe, r refers to the degree assortativity and refers the average clustering coefficient. These networks were picked to span range of average degrees and clustering coefficients.
Network
Nodes
Edges
(k)
0k
Transitivity
EU Email Leskovec et al. [2007]
986
16687
33.84
37.81
-0.01
0.40
0.26
US Airport Zhu et al. [2021
1186
13597
22.92
40.49
0.03
0.50
0.42
Squirrel Rozemberczki et a.
2021
5201
198493
76.32
161.45
-0.23
0.42
0.34
Citeseer Bollacker et al.
[998]
3327
4676
2.81
3.38
0.05
0.14
0.13
FB15K-237 Toutanova
Chen
2015
14951
261581
34.99
111.43
-0.10
0.213
0.02
PubMed Roberts [2001
19717
44327
4.49
7.43
-0.04
0.06
0.05
network in our datasets, PubMed, to demonstrate practical application of our approach and compare our results against other explanation methods. Finally, present ablation study that explores the impact of different constraints of XM.
4.1 Explanations Visual Evaluation
(C) and (E), the three Figure shows the Explain matrix for the Karate Club network. As in Figure 2
subplots of Figure 1 show the Explain matrices for the instructor node (node 1, Fig 4 A)), a random student node (node 12, Fig 4 B)) and the president node (node 34, Fig 4 C)). To stay consistent across experiments, these plots were generated using 16-dimensional embeddings that were generated from DGI+XM. Observe that the Explain matrices shown in Figure (B) and (C), while highlighting similar sense features, are sparser than the respective plots in Figure (D) and (E) and each sense feature is defined by fewer dimensions, i.e. the dimensions are orthogonal in their explanations when compared to the standard DGL.
For each of our six real world datasets, we also compute an Explain matrix for the entire graph by aggregating the node embeddings into a graph-level embedding, using mean readout. Similarly, we compute the mean of the sense feature matrix. Using Equation] | we derive a graph-level Explain matrix, as shown in Figure 5 For brevity, we only show results computed using DGI+XM and 32 dimensional emboddings. In particular, Katz centrality emerges the most prominent feature for networks such as Citeseer and Pubmed, which is intuitively consistent with the nature of citation networks, Katz centrality measures the degree of influence of nodes within network Katz [1553) In contrast, the salient features for the EU Email data are clustering and average neighbor clustering, which is consistent with social networks.
(A) Node (Instructor)
(B) Node 12 (Random Node)
(C) Node 34 (President)
Dimens-on ons
Dimeersoon ons
Degrte
mR Standirrs
Averoo Meightr
Kab Corcrlty
Neightr
gater
Eccernictty
Dogse
Custeing Sastiount
Standord
boo
Casleingg
Sense Features
Sense Features
Sense Features
Figure 4: Explain matrices for the Karate Club network (aahary 1977 generated using DGI-XM for (A) the instructor (node 1), (B) random student (node 12), and (C) the president (node 34). Compare each of (A), (B), and (C) to Figure 2 (D), and (E), respectively. Observe that the Explain matrices in this figure (generated by DGI+XM) are sparser and each sense feature is explained by fewer dimensions, when compared to the Explain matrices from Figure (generated by the standard DGI).
12

---

Published in Transactions on Machine Learning Research (04/2025)
50 Enst
(f) US Airport
[CI Squime!
IDH Choszer
IEI FB15K
[F] PubMod
423
Figure Graph-level Explain matrices for six real-world datasets, based on mean readout of all node embeddings computed using DGI+XM and mean sense features. The prominent features across different networks are highlighted, with Katz centrality emerging the dominant fcature in citation networks like Citeseer and Pubmed, while clustering and average neighbor clustering stand out in social networks like the EU Email network.
4.2 Explanations Quantitative Evaluation
We examine the nuclear norms of the Explain matrices as a quantitative metric to evaluate and compare the standard and XM variants of the algorithms. For each dataset, we use each of the four algorithms shown in Table 2 and compute the mean of the nuclear norm of the Explain matrices across all nodes in the dataset. We embed every dataset into 128 dimensions for consistency across datasets and algorithms and pass in sense features node attributes when rumning DGI and GMI.
As discussed in Section 3.2.2 lower muclear norms result in sparser Explain matrices, meaning fewer rank-1 matrices are required to reconstruct the given matrix. This sparsity is indicative of interpretable explanations. Figure B demonstrates that for each node of a graph, the nuclcar norm of its Explain matrix reducod when using SDNE+XM versus SDNE. The distribution of nuclear norm values shifts leftward (i.e. lower), indicating that the XM framework successfully reduces muclear norms (thereby, ranks) across all datasets.
Similar results for other algorithms can be found in the appendix in Figures 13 14 and 15
4.3 Link Prediction Performance
By adding additional loss terms to the objective function, we modily the embeddings themselves to generate a less noisy Explain matrix. We use link prediction as our downstream task and sample an equal number of positive and negative edges from the graph. We use 60% of the edges as training data and the remaining as test data. The embeddings are passed through a simple 2 layer fully connected neural network. We repeat the entire process times to create a three-fold cross- validation setup. We use 128-dimensional embeddings across all algorithms and networks for consistency.
Figure depicts the results with nuclear norm (averaged across all nodes in the graph) shown the y-axis and the AUC shown on the x-axis with error bars denoting the standard error. We observe that across all algorithrss, AUC scores are comparable to the original version, with the corresponding nuclear norms being lower leading to denoised Explain matrices.
We also examine differences runtime due to the additional constraints in Figure More specifically, we examine the time (in seconds) per epoch for each of the 4 algorithms we test for the EU Email network. We observe that the XM variants comparable in runtime to their original versions. Results shown are
13

---

Published in Transactions on Machine Learning Research (04/2025)
(A) EU Email Network
[B] Airport
(C) Squirel
0.25
0.200
0.30
0.175
0.15
0.325
20,20
0.100
0.15
0.10
0.075
0.10
3.050
0.05
0.025
0.05
Nudear Norm (E) FB15k
Nuckaar Norm
(D) Citeseer
(F) PubMed
0.7
0.5
0.6
0.4
0.5
Probabiitt
0.3
Probabilty
Probabaity
0.4
0.2
0.2
0.3
0.1
0.1
0.1
0.0
10
Nucicar Norm
Nudcar Norm
Nucicar Norm
SDNE
SDNE+XM
Figure 6: Distribution of nuclear norms of the Explain matrices for cach node for SDNE and SDNE+XM Observe how the distribution of SDNE+XM is shilted to the left with a lower mean across each of the 6 datasets. See Section A.2 in the appendix for results on the other methods.
averaged across five runs with error bars showing standard error. Similar runtime comparisons for other datasets are shown in the appendix (Figures 16 through 20
4.4 Case Study PubMed Network
To illustrate concrete use case, we focus on the PubMed network and use DGI as the embedding algorithm. The nodes in PubMed are classified into three categorics- Diabetes Mcllitus, Exporimental (Class 0), Diabctes Mellitus Type 1 (Class 1) and Diabetes Mellitus Type (Class 2). It important to note that DGI does not take these class labels into account while training. For this study, we embed the network into 32 dimensions using DG1+XM for brevity. We then randomly select eight nodes, ensuring a variety of connections and degrees, including nodes that are both connected and disconnected, with both matching and differing class labels. Details of these nodes are presented in Table J The resulting Explain matrices for these eight nodes are presented in Figure g Each matrix illustrates the key sense features responsible for positioning these nodes within the embedding space, allowing for a clear interpretation of the role each node and feature plays.
We next compare the explanations generated by DGT and its augmented variant, DGI+XM, focusing on the importance of cach dimension across nodes. Unlike prior experiments that utilized structural sense features, we employ PubMed's 500 inherent node features to showcase an application with non-structural features. Specifically, compute the average of each in the Explain matrix, where this average reflects the relative significance of each dimension in explaining the inherent features of the nodes in PubMed.
In Figure 10 the y-axis represents the mean dimensional importance for each of the 32 dimensions shown on the x-axis. The top row of the figure illustrates the results from DGI+XM, while the bottom row shows results from the standard DGI variant. Notably, DGI+XM provides clearer and interpretable results. For example, for connected nodes within the same class (first column), the important dimensions stand out more distinctly in DGI+XM compared to the noisier and less discernible results from DGL. These differences
14

---

Published in Transactions on Machine Learning Research (04/2025)
SDNE SONE+XM MONE++XM
LINE LINE-XM
17.5
15.0
8
Nuclear Norm
Nuclear Norn
12.5
6
10.0
2.5
0.0
0.5
0.6
0.7
0.8
0.9
1.0
0.70
0 0.75
0.80
0.85
90
0.95
1.00
AUC
AUC
DG
GMI
10
DG -M
18:
GMI+XM
16
UB 08-epp
Nuclear Norm
Nuclear Norm
144
12:
Noorr
4-
10
TOAk
Scard
Fmall
0.6
0.7
0.B
0.9
0.92
0.94
0.96
0.98
1.00
AUC
AUC
Figure 7: AUC scores for link prediction across 4 embedding algorithms SDNE, LINE, DGI, GMI shown in cach subplot, on the 6 networks defined in Table 3 Error bars show standard crror. AUC scores for the XM variants are comparable to the original algorithms with nuclear norms of the XM variants being lower. The XM variants also follow the original algorithms in terms of standard error, for example, SDNE has large variance in AUC for the PubMed dataset, which can also be seen for SDNE+XM. Results are from three-fold cross validation experiment with 128 dimensional embeddings.
become even more pronounced in other scenarios, such when nodes belong to different classes or are disconuected. As another example, with DGI+XM, dimensions 14, 27 and 28 are highlighted as particularly important for nodes in Class 2 across nodes, while similar insights are difficult to obtain from the standard DGI approach due to its noisier nature, even considering non-identifiability issues.
We now compare our approach with two widely-usod graph explanation methods: GNNExplainer (Ying al. 2019) and GraphMask Explainer (Schlichtkrull et al. 20221. Both of these methods focus on explaining the decisions of trained model, particularly in node classification tasks. In contrast, XM is not designed to explain specific classification outcomes or generate subgraphs for explanations. For the sake of comparison however, we analyze the Explain matrix of node by averaging across its columns to identify the most important features.
For GNNExplainer and GraphMask Explainer, we train 2-layer GCN with hidden units each for node classification and apply the explainers post-hoc to generate node feature importance scores. It is important to note that GNNExplainer and Graph Mask Explainer specifically target explaining node classification in
15

---

Published in Transactions on Machine Learning Research (04/2025)
52h2
0.020
Run Time per Epoch (5)
Run Time per Epoch (s)
0.015
20
0.010
0.005
0.000
16
128
256
32
256
Dimensions
# Dimensions
0.014
0.20
Run Time per Epoch (s)
Run Time per Epoch (s)
0.15
0.008
0.10
0.004
0.05
16
32
128
256
16
32
128
256
# of Dimensions
# of Dimensions
Figure EU email network: runtimes per epoch (in seconds) for SDNE, LINE, DGI, GMI, and their corresponding XM variants. Results averaged across 5 runs. Observe that the runtimes per epoch are comparable to the original versions. Error bars show standard error. See Section A.3 in the Appendix for the resutls other networks.
Node
Degree
Clustering Coefficient.
# Triangles
Class
Paper
1
0.000
0
2
Malhotra et al.
1992
19
0.046
2
Pelrovsky et al.
2002
171
0.006
96
Group al.
1998
D
33
0.075
40
0
Obrosova
2005
E
10
0.044
2
2
Stay et al.
2008
F
5
0.100
1
2
Cline al.
1994
G
1
0.000
0
0
Sima & Sugimoto (199
H
1
0.000
0
2
Badenhoop & Boehm (2004)
Table 4: Description of randomly selected nodes for the PubMed case study. Here class 0 corresponds to papers regarding Experimental treatments for Diabetes Mellitus, class 1 about Diabetes Mellitus Type 1 and classs about Diabetes Mellitus Type
the context a trained model, whereas XM (specifically DGI+XM as used before) remains task-agnosth and focuses explaining embedding dimensions.
16

---

Published in Transactions on Machine Learning Research (04/2025)
Mode (Dlnna |2| Degrewe
Nocw B (Clema 2| Degree: 19)
hode (Clans: 2 DDegree -333)
Node 12 (Clesa DI Degree (33)
Nodez (Ulass:2 2 Dogroe:
radie IC 2 Doggnoe
mode (Class :0] Uogres 3)
Mode H ICloss: 2 Doegroe
School wer
8000
Figure 9: This figure illustrates the Explain matrices for eight randomly selected nodes from the PubMed network, highlighting the sense features responsible for their positioning within the embedding space. Each row corresponds to a dimension of the embedding, while each column represents a human- understandable feature.
Ridees Same Class
Diconnected
Disconneccted Differeet Class
Siffrert Class
Same Clars
Class (01
Depor
Steas Dapper
D02-000
001
Figure 10: Comparison of dimensional importance, computed as the row wise mean of the Explain matrices, for randomly selected nodes in the PubMed network using DG1+XM (top row) and DG1 (bottom row). Observe the clarity of the explanations provided by DGI+XM, particularly in identifying important dimen- sions for nodes with the same or different. class labels and varying connection statuses as opposed to noisier explanations provided by the standard DG1 variant.
For the 8 nodes previously discussed, we identify the top 25 features that each explainer model highlights significant. To quantify the similarity between these feature sets, we compute the Jaccard similarity across the top 25 features identified by each method, as illustrated in I Interestingly, despite XM not being tailored for feature importance, it still identifies many of the same features highlighted by GNNExplainer and Graph Mask Explainer in their top 25. We also observe higher degree of alignment between XM and GNNExplainer potentially due to GNNExplainer's explicit focus on maximizing mutual information between feature subsets and the original feature set.
17

---

Published in Transactions on Machine Learning Research (04/2025)
hodel A rtlass Deggee::
Mode S TCNO5 Deggne 290
Nodt C (Clos
(egres 3731
Node O rCuss
00 Degree
20V30
D0H
Noze 1Diea
Deggnnr: 100
Nhals I /Chen: 2| Degres (5)
Tocir G Iilea
Degrner
Napu Pn (das 22 Degrae
1007
290
044
06-
04:-0
000-00 Fucidey
PM
Pooteer
Figure 11: Comparison of the top 25 features identified as important for the task of node classification by XM, GNNExplainer, and GraphMask Explainer across 8 randomly selected nodes, representing different classes and degrees. To quantify the similarity between these feature sets, we compute the Jaccard similarity between the list of features highlighted by each method. Despite XM not being specifically designed for explaining node classification outcomes, it still highlights many of the same features identified by GNNFxplainer and GraphMask Explainer, with higher alignment with GNNExplainer than GraphMask Explainer.
4.5 Ablation Study
We add two constraints, orthogonality and sparsity, while computing the augmented node embeddings. We study how each contributes to the reduction of nuclear norms. Figure 12 shows nuclear norms for each network embedded in 128 dimensions using each the four embeddings algorithms, averaged across five runs. We see that the orthogonality constraint alone reduces the nuclear norm more than the sparsity constraint alone. We see that across all algorithms, using both constraints together achieves the lowest nuclear norm.
5 Discussion
The XM framework generates explanations the granularity of each dimension for individual nodes. While this level of detail is valuable for examining specific nodes, deriving a comprehensive understanding of large network requires further analysis of multiple Explain matrices.
As is common in works on explainability, the use of the XM framework leads to a marginal reduction in performance scores for downstream tasks. However, note that the reduction in performance can be controlled through the choice of hyperparameters. For this study, we chose to prioritize the quantitative value of the nuclear norm to obtain the largest possible reduction. amount of denoising of the Explain matrices the desired level of performance in downstream tasks by setting the hyperparameters accordingly. (Our choices for the hyperparameters are available in our online code repository at littps:/ http://ggttttbbt/ wtt.tttb.coommm.eeee com zohairshaaii ExxpaaiingNNoeemmmeerr
actual use, the practitioner can balance the
The offectiveness of XM is also influenced by the choice of sense features. As discussed in Section 3.1.2 different sense features can yield different results. Domain knowledge plays role in selecting the appropriate features, depending on the specific goals of the explanation task. We chose to use structural sense features throughout this work because they provide rcasonable and human-interpretable basis for understanding graphs across various domains, such as sociology and biology, using features like node degree and clustering
coefficient (Albert Barabási 2002 Newman 2003
18

---

Published in Transactions on Machine Learning Research (04/2025)
(A] EU Email Network
(8) US Airport
(C) Squirel
163
17.5
16.
16-
156
15.0
144
12.5
125
10.0
5.6
7.5
5.0
5.0
2.5
2,5-
0.0
S0NE
LINE
BEa
GAR
0.0
SONE
LBNE
PGI
GMI
SONE
DGI Emocdding Algortive
LINE
CR
Emoosdiig
(D) Citeseer
[EI FB1
(F) PubMed
1.
12
12-
10
Norm
64
Posdewer Parm
humm
25
50
b81 Embedding Algeritive
LINE
SONE
Ddl Embedding Algonthm
59AE
Dia Emiwdding Algenitivn
UhE
Original Method
Sparse Constraint Only
Orthogonality Constraint Orly
Both Constraints
Figure 12: Ablation study examining the impact of each term in the loss function. Observe that the orthogonality constraint alone reduces nuclear using both constraints leads to the lowest nuclear norms. The plot shows average values over 5 runs. Results shown are for 128 dimensional embeddings but hold true across various dimensions. (We tried = 16, 32, 64, 128, 256.) We do not find a correlation between the number of embedding dimensions and the reduction the nuclear norm values. Error bars show standard error.
than the sparsity constraint alone. However,
6 Conclusion and Future Work
We present method for generating explanations for each node in the form of an Explain matrix using set of human-understandable "sense" fcatures. These features can be based on the graph structure (such degree, clustering coefficient, and PageRank) or other user-defined features. We use the nuclear norm of the generated Explain matrices to quantify their usefulness. The choice of nuclear norm due to its relationship with the entropy of matrix. In particular, reducing the nuclear norm leads to the reduction of the lower bound of the entropy of the Explain matrices. Moreover, we introduce the XM framework, which modifies existing embedding algorithms to produce embeddings with low nuclear norms Explain matrices, while maintaining downstream task performance. We demonstrate the effectiveness of XM across four embedding algorithms and six real-world datasets and analyze the impact of XM's constraints through an ablation study. XM is independent of any downstream task and can be used with any existing embedding algorithm and any set sense features.
Future work. We noticed that the Explain matrices tend to have dimensions that do not contribute to explaining any sense features i.c. the rows corresponding these dimensions the Explain matrix are near zero. Such information can be used for model selection i.c. set the hyperparameter associated with the number of embedding dimensions.
19

---

Published in Transactions on Machine Learning Research (04/2025)
References
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Réka. Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47 97, 2002.
Narbota Amanova, Jörg Martin, and Clemens Elster. Finding the imput features that reduce the entropy of a neural network's prediction. Applied Intelligence, 54(():1922-139) 19366, 2024.
Francis Bach. Playing with positive definite matrices ii: entropy edition. htttps:/fraaciisacch.cmm com/
von-newwn -en-nemman-- -etorny//ttr//// 2022.
K Badenhoop and BO Boehm. Genetic susceptibility and immunological synapse in type 1 diabetes and thyroid autoimmune discase. Experimental and clinical endocrinology & diabetes, 112(08):407-415, 2004.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiu:1905. 13686, 2019.
Albert-László Barabási. Network Science. Cambridge University Press, 2016. ISBN 9781107076266.
Kurt D. Bollacker, Steve Lawrence, and C. Lee Giles. Citeseer: An autonomous web agent for automatic retricval and identification of interesting publications. In International Conference on Autonomous Agents, 1998.
Stephen Bonner, Ibad Kureshi, John Brennan, Georgios Theodoropoulos, Andrew Stephen McGough, and Boguslaw Obara. Exploring the semantic content of unsupervised graph embeddings: An empirical study. Data Science and Engineering, 4:269 --299-289, 2019.
Nadia Burkart and Marco F Huber. A survey on the explainability of supervised machine learning. JAIR, 70:245 317, 2021.
Ronald S Burt. Structural holes and good ideas. Am. J. Sociol, 110(2):349-399, 2004.
Ines Chami, Sami Abu-EI-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: A model and comprehensive taxonomy. JMLR, 23(89):1 64, 2022.
GW Cline, DL Rothman, Magnusson, LD Katz, GI Shulman, et al. 13c-nuclear magnetic resonance spectroscopy studies of hepatic glucose metabolism in normal subjects and subjects with insulin-dependent diabetes mellitus. The Journal of clinical investigation, (4(6):2369-22) 2226992376, 1994.
Ayushi Dalmia, Ganesh J, and Manish Gupta. Towards interpretation of node embeddings. In WWW, pp. 945 902,552,22 2018.
Chi Thang Duong, Quoe Viet Hung Nguyen, and Karl Aberer. Interpretable node embeddings with mincut loss. In ICML (Workshop), 2019.
Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In ECML PKDD, pp. 302 318, 2021.
Kawin Ethayarajh, David Duvenaud, and Graeme Hirst. Towards understanding lincar word analogies. arXiv preprint orXic:1810.04888 2018.
Linton C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35 41, 1977.
Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M Airoldi, and Aaron Clauset. Stacking models for nearly optimal link prediction in complex networks. PNAS, 117(38):23393 234000 2020.
Antonia Gogoglou, C Bayan Bruss, and Keegan Hines. On the interpretability and evaluation of graph representation learning. Xix preprint 1r100:1910.00003 2019.
20

---

Published in Transactions on Machine Learning Research (04/2025)
UK Prospective Diabetes Study (UKPDS) Group al. Intensive blood-glueose control with sulphonylureas insulin compared with conventional treat ment and risk of complications in patients with type 2 diabetes (ukpds 33). The lancet, 352(9131):887 853, 1998.
Shuhang Gu, Lei Zhang, Wangmeng Zuo, and Xiangchu Feng. Weighted nuclear norm minimization with application to image denoising. In JEEE CVPR, pp. 2862 2869, 2014.
Shurui Gui, Hao Yuan, Jie Wang, Qicheng Lao, Kang Li, and Shuiwang Ji. Flowx: Towards explainable graph neural networks via message flows. arxic preprint or arxiv:200.. 02922006129990 12987, 2022.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. In ACM SIGKDD, pp. 1231 1239, 2012.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang, Graphlime: Local interpretable model explanations for graph neural networks. IEEE TKDE, 35(7):6968-699)) 6972, 2022.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39 43, 1953.
Shima Khoshraftar, Sedigheh Mahdavi, and Aijun An. Centrality-based interpretability measures for graph embeddings. In IEEE DSAA, pp. 1 1-10, 2021.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diam- eters. ACM TKDD, 1(1):2-es, 2007.
Yiqiao Li, Jianlong Zhou, Sunny Verma, and Fang Chen. survey of explainable graph neural networks: Taxonomy and evaluation metrics. Xiviv preprint arXio:2207.15500 2022a.
Yuan Li, Li Liu, Guoyin Wang, Yong Du, and Penggang Chen. Egnn: Constructing explainable graph neural networks via knowledge distillation. Knowledge-Baud Based Systems, 241:108345, 2022b.
Chris Lin, Gorald J Sun, Krishna Bulusu, Jonathan R Dry, and Marylens Hernandez. Graph neural networks including sparse interpretability. arXiv preprint arXiv:2007.00112 2020.
Ninghao Liu, Xiao Huang, Jundong Li, and Xia Hu. On interpretation of network embedding via laxonomy induction. In ACM STGKDD, pp. 1812-1820, 2018.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In NeurIPS, pp- 2017.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong. Haifeng Chen, and Xiang Zhang. Pa- rameterized explainer for graph neural network. NewrIPS, 33:19620 19631, 2020.
C Malhotra, RICHARD Spielman, and PATRICK Concannon. Variability in cell receptor v beta gene usage in human peripheral blood lymphocyles. studies of identical twins, siblings, and insulin-dependent diabetes mellitus patients. Journal of Immunology (Baltimore, Md.: 1950), 149(5):1802-15)) -808, 1992.
Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger. UMAP: Uniform manifold approxima-
tion and projection. Journal of Open Source Software, 3(29):861, 2018
Nicolas Menand and C Seshadhri. Link prediction using low-dimensional node embeddings: The measure- ment problem. PNAS, 121()):=231222712) 2024.
M. Newman. Networks: An Introduction. OUP Oxford, 2010.
M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167-256, 2003.
Thanh Nguyen, Trung Xuan Pham, Chaoning Zhang, Tung M Luu, Thang Vu, and Chang Yoo. Dimel: Dimensional contrastive learning for improving self-supervisod learning. IEEE Access, 11:21534-21545, 2023.
21

---

Published in Transactions on Machine Learning Research (04/2025)
Irina G Obrosova, Pal Pacher, Csaba Szabo, Zsuzsanna Zsengeller, Hiroko Hirooka, Martin J Stevens, and Mark A Yorek. Aldose reductase inhibition counteracts oxidative-nitrosativv stress and poly (adp-ribose) polymerase activation in tissue sites for diabetes complications. Diabetes, 54(1):234 242, 2005.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang.
Graph representation learning via graphical mutual information maximization. In WWW, pp. 259-270, 2020.
Nikolai Petrovsky, Kirsten O Kyvik, Vagn Bonnevic-Nielsen, Henning Beck-Niclsen, Anders Green, and Leonard C Harrison. Evidence from twins for acquired cellular immune hyperactivity in type diabetes. Immomology, 106(4):584-58) 2002.
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability
methods for graph convolutional neural networks. In IEEE CVPR, pp.
2019.
Ori Press, Ravid Shwartz-Ziv, Yann LeCun, and Matthias Bethge. The entropy enigma: Success and failure of entropy minimization. In ICML, 2024.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you? explaining the predictions of any classifier. In ACM SIGKDD, pp. 1135 1144, 2016.
Richard J Roberts. Pubmed central: The genbank of the published literature, 2001.
Ryan A Rossi, Rong Zhou, and Nesreen K Ahmed. Deep inductive graph representation learning. IEEE TKDE, 32(3):438 452, 2018.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, (2)ccnab011, 2021.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nlp with diffcrentiable edge masking. In ICLR, 2021.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof Schütt, Klaus- Robert Muller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):5511-7596 2021.
Claude E Shannon. Prediction and entropy of printed english. Bell system technical journal, 30(1):50 64, 1951.
AAF Sima and K Sugimoto. Experimental diabetic neuropathy: an update. Diabetologia, 42:773-788, 1999.
Indro Spinelli, Simone Scardapane, and Aurclio Uncini. A meta-learning approach for training explainable graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 35(4):4647 4655, 2022.
Andrew Stolman, Caleb Levy, Seshadhrr, and Aneesh Sharma. Classic graph structural feat ures outperform factorization- based graph embedding methods on community labeling. In SDM, pp. 388 188-396,44 2022.
Julie Stoy, Siri Atma W Greeley, Veronica P Paz, Honggang Ye, Ashley N Pastore, Kinga B Skowron, Rebecca B Lipton, Fran R Cogen, Graeme T Bell, Louis H Philipson, et al. Diagnosis and treatment of nconatal diabetes: an united states experience. Pediatric diabetes, 9(5):450-459, 2008.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qinozhu Mei. Line: Large-scale information network embedding. In WWW, pp. 1067 1077, 2015.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop Continuous Vector Space Models and their Compositionality, pp. 57-66, 2015.
Petar Velickovic, William Fedus, William L Hamilton, Pictro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
22

---

Published in Transactions on Machine Learning Research (04/2025)
Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. NewrIPS, 33:12225-1222 12235, 2020.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In ACM SIGKDD, pp. 1225-1234, 2016.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. arXiv preprint arXiu:2006110726 2020.
Jun Xu, Lei Zhang, David Zhang, and Xiangehu Feng. Multi-channel weighted muclear norm minimization for real color image denoising. In IEEE ICCV, pp. 1096-1104, 2017.
Zhitao Ying, Dylan Bourgcois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. NewrIPS,
2019.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In ICML, pp. 7134-7143, 2019.
Yao-Liang Yu. The strong convexity of von neumann's entropy. Unpublished note, 2013.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, volume 139, pp. 12241 12252, 2021.
Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthro- pological Research, 33(4):452 -473, 1977.
Yi-Jiao Zhang, Kai-Cheng Yang, and Filippo Radicchi. Systematic comparison of graph embedding methods in practical tasks. Phys. Rev. E, 104(4):044315, 2021a.
Yue Zhang, David Defazio, and Arti Ramesh. Relex: A model-agnostic relational model explainer. In AIES, pp. 1042-1049, 2021b.
Jing Zhu, Xingyu Lu, Mark Heimann, and Danai Koutra. Node Procimily Is All You Need: Unified Structural and Positional Node and Graph Embedding, pp. 163-171. 2021.
A Appendix
A.1 Variations to the Objective Function
Recall that we define the Explain matrix for a node k:
Dk 60 fr
E.
(21)
1 1f
Thus, the sparsity and orthogonality constraints (as defined Equations 2 and 3 respectively) are on nodes. To add pairwise constraints on nodes, we investigate variations to Equation Specifically, implement the following variations for any node pair i and j
1. Minimize E,l F. This constrains the E matrices of cach pair of nodes i,j to be similar if they are connected by an edge (i.e. if azy = 1), where the similarity is captured in terms of the Frobenius norm of the difference between their two Explain matrices.
2. Minimize |E.EE - ftff
Here, we move away from asking whether or not two nodes are connected by an edge. We compute the dimension- wise similaritics between the Explain matrices and the similaritics between sense feature vectors for all possible node pairs and obtain two distance matrices, each of dimension R=*=, We then minimize the Frobenius norm of the difference between these two matrices.
23

---

Published in Transactions on Machine Learning Research (04/2025)
We find that adding pairwise constraints to the objective function is not good idea. The outcome is very sensitive to the choice of hyperparameters and the reduction in nuclear norm is not significant. We posit that this may be due to opposing components of the objective function. For example, consider high- degree node (a.k.a. a hub) that connected to a low-degrce node. In this case, most algorithms place the embeddings of the two nodes close to each other (since the nodes are connected) even though their sense features are different. To summarize, we find that using the formulation defined in Equations (2) and (3) leads to the most stable setup with the largest reduction in nuclear norms among the ones described above.
A.2 Nuclear Norm Distributions for Explain Matrices
Recall that each node has corresponding Explain matrix. Thus, for each algorithm and dataset, we calculate
the nuclear norm distribution across the Explain matrices of nodes. Figures 13 14 and [5] respectively, show the nuclear norm distributions between LINE and LINE+XM, DGI and DGI+XM, and GMI and GMI+XM for all 6 datasets. We observe that the XM variants produce Explain matrices whose nuclear norms are lower than the original versions.
(A) Email
Airport
Squireel
0.08
0.08
0.04
0.06
Prbabblly
0.05
Probbiiity
0.03
ProbsbilAy
0.02
0.02
Nudear
Norm (F) PubMed
(D)
0.200
0.200
0.12
0.350
Pobabiity
0.08
Wolaboto
0.125
0.125
0.06
0.100
0.050
6.02
0.025
LINE
LINE
Figure 13: Nuclear norm distribution across the Explain matrices for LINE and LINE+XM. Observe how the distribution of LINE+XM is shifted to the left with a lower mean across each of the 6 datasets.
A.3 Runtime Analysis
We examine differences in runtime per epoch (in seconds) between the original algorithms and the XM variants across different embedding dimensions. Figure [ooure[6]shorre shows the runtime comparison for the US Airport network, Figure 17 for the Squirrel network, Figure [8] for the Citesoer network, Figure 10 for the FB15k network, and Figure 20 for the PubMed network. We observe that the XM variants are comparable in runtime to their original versions.
24

---

Published in Transactions on Machine Learning Research (04/2025)
(A)
[B] Airport
(C) Squirel
0.16
0.030
0.14
Pobalaliy
0.10
Pobabiit
0.35
0.08
0.20
0.015
6.010
0.04
0.05
0.005
6.02
12
1.4
(D) Citeseer
(E) FB15k
(F) PubMed
0.06
0.40
0.14
Probabiity
Probabiity
0.04
Probubiity
0.08
0.03
0.15
0.10
0.02
0.05
0.25
0.50
0.75
1,00
1.25
1.50
10
12
0.5
1.0
1.5
2.0
25
GMI GMIIXMM
Figure 14: Nuclear norm distribution across the Explain matrices for DGI and DGI+XM. Observe how the distribution of DGI+XM is shifted to the left with a lower mean across each of the 6 datasets.
A.4 Nuclear Norm Minimization
Figure 21a looks at all networks in Table 3 embedded using cach the algorithms from Table 2 Rosults are averaged across 5 runs. We see that the nuclear norms of the Explain matrices are lower for the XM variants across each network. These differences are statistically significant with p-values less than 0.05. Table 21b lists the p-values.
25

---

Published in Transactions on Machine Learning Research (04/2025)
(A) EU Email Network
(B) US Airport
(C) Squirrel
0.03
Prub abilk
Probsbllty
0.03
0.63
0,02
0.01
20
35
5.0
7.5
10.0
32.5
35.0
17.5
20.0
Norm
(D) Citeseer
(E) FB15k
(F) PubMed
0.20
0.18
0.08
0.12
hybbabiity
0.10
Probability
0.06
0.04
0.06
0,02
0.00
10
14
0.00
5.5
75
10.0
12.5
15.0
17.5
0.00
8
1.0
12
14
Nuthear
Norm
GMI
GMi+XM
Figure 15: Nuclear norm distribution across the Explain matrices for GMI and GMI+XM. Observe how the distribution of GMI+XM is shifted to the left with lower mean across each of the 6 datasets.
0.32
0.30
Run Tine Epoch b0
0.4
0.3
0.04
0.2
0.02
0.1
0.00
1.6
64
128
256
0.0
32
65
128
254
Dimeniiors
Dimersions
Run Time o4 Epoot 1
0.008
0.3
0.006
per
0.004
0.002
0.1
of Dimendooss
of Dimonstons
Figure 16: US Airport network: runtimes per epoch (in seconds) for SDNE, LINE, DGI, GMI, and their corresponding XM variants. Results are averaged across 5 runs. Observe that the runtimes per epoch are comparable to the original versions. Error bars show standard error.
26

---

Published in Transactions on Machine Learning Research (04/2025)
077
Dur Time par Epnch bi
720
Dimenatona
7.02
3.52
3.02
1.5
1.73
132
0.2
5.2
200
52
1.00
Figure 17: Squirrel network: runtimes per epoch (in seconds) for SDNE, LINE, DGI, GMI, and their corresponding XM variants. Results are averaged across 5 runs. Observe that the runtimes per epoch are comparable to the original versions. Error bars show standard error.
0.0
6.35
15
50
1.0
216
0.6
32.
240
236
2.004
3.00
1030
0.50
15
Figure 18: Citeseer network: runtimes per epoch (in seconds) for SDNE, LINE, DGI, GMI, and their corresponding XM variants. Results averaged across 5 runs. Observe that the runtimes per epoch comparable to the original versions. Error bars show standard error.
27

---

Published in Transactions on Machine Learning Research (04/2025)
3007
Ran Time Opoch
200
100
of Cemrorsions
22.b
0.0
2.0
0.0
0.0
Figure 19: FB15k network: runtimes per epoch (in seconds) for SDNE, LINE, DGI, GMI, and their cor- responding XM variants. Results are averaged across 5 runs. Observe that the runtimes per epoch are comparable to the original versions. Error bars show standard error.
220
Spoch
Sun TonTreppe per Toach
8 Dmerrarr
4.0
3.5
2.0-
1.A4
0.5
2.0
0.0
0. D.eeeions
Figure 20: PubMed network: runtimes per epoch (in seconds) for SDNE, LINE, DGI, GMI, and their corresponding XM variants. Results are averaged across 5 runs. Observe that the runtimes per epoch are comparable to the original versions. Error bars show standard error.
28

---

Published in Transactions on Machine Learning Research (04/2025)
SOME SOME-X4
17.5
LINE LIKE++XM
8.05
15.0
1.3
12.52
12.5
10.77
Naciear Noma
Nom
10.0
7.5
3233
4.45
4.12
253
EU Email US Airport Squire
Citeseer
FB15k
PubMed
EU Email US Airport
Squirrel Citeseer Networks
F015k
PueMed
10
DC1-XM
15.31
CNI-KON
12:24
12.5
11.5
Nuctoar Norm
Norm
0.02
10.0
7.5
5.0
1.5
2.5
5A7
Airport Squiral
PubMed
Squimal Networks
(a) We average the nuclcar normu of the Explain matrices of each node in the network. The experiment is repeated times and average results are shown. Error bars depict standard error. Observe that the mean nuclear norms for the XM variants are lower than the original versions. The differences in means are statistically significant with pvluuess less than 0.05.
EU Email
US Airport
Squirrel
Citeseer
FB15k
PubMed
SDNE vs. SDNE XM
2.13e- 10
9.78e-11 11
1.65e- 10
7.76e- 10
4.44e-1 11
3.96e- 11
LINE LINE XM
1.96e-07
8.86e-06
6.72e-05
8.30e-06
1.38e-07
3.92e-06
DGI vs. DGI + XM
1.62e-03
1.47e-04
2.62e-04
4.88e-04
1.93e-07
5.03e-07
GMI vs. GMI + XM
1.80e-06
6.59e-06
3.81e-06
1.02e-07
2.88e-05
1.60e-07
(b) pvaauues associated with Figure statistically significant.
21a
The muclear norms between the original versions and the XM variants are
Figure 21: Quantitative evaluation of the Explain matrices based on their muclear norms across networks, original methods and their XM variants. The lower the norm, the better the Explain matrix.
29


Reviews:
[{"review_id": "VmeKI577MC", "reviewer": "Reviewer_5ybi", "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": "## **Strengths**\n\n-  The XM algorithm introduces a novel use of sparsity and orthogonality constraints to align graph embeddings with human-understandable sense features, providing a significant contribution to the field of interpretable graph representation learning. \n\n## **Weakness**\n\n- **Fixed sense features**\n     - The XM framework chooses a fixed type of sense features and with that the explanation makes sense. The accuracy of XM is highly dependent on these sense features and as per the author, poor choice of sense features might degrade the explanation. For users, it could have been helpful on the best practices to select these predefined sense features along with defining “new” type of features depending on the use-case for example, what can help with multi-modality.\n\n- **Nuclear Norm Reduction is the \"only\" Interpretability Method**\n   - The author is completely relying on nuclear norm reduction for interpretability, but the nuclear norm reduction doesn’t ensure the “quality” or meaningfulness of each embedding. So complementing the nuclear norms with other matrices (defining the usefulness of embedding for each use-case) might provide a more robust solution.", "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": "# Contribution \nCreated a framework called XM (Explain Embedding) to improve existing node embeddings (can be any 3P embedding methods: using DGI in paper) to be as close as possible to human-understandable embeddings. The XM framework is not purely a post-hoc method for human-understandable embeddings but also manipulates the generated embeddings to incorporate interpretability during the embedding process.\n\n## **XM as post-hoc** \n\n- **Input**\n   -  Graph Embeddings using any 3rd party embedding methods such as DGI\n\n- **Sense Features**\n   - Define a set of “sense” features which are human-understandable that describes the graph: {degree, clustering coefficient, Katz centrality.}\n\n- **Correlation of Embeddings with sense features**\n  - Compare the precomputed embeddings of graph nodes with these sense features to understand how each embedding dimension correlates with specific graph properties\n\n- **Explain Matirx (E)**\n   - Outputs an Explain Matrix (E) that shows how each embedding dimension aligns with each sense feature, making the embedding interpretable: how graph nodes are connected based on these sense features.\n\n## **XM as Embedding Manipulator**\n\n XM as an Embedding Manipulator (with sense features) to generate embeddings for Nuclear Norm Minimization  (to keep the \n embeddings as human-understandable) to keep the simpler relationship between the sense features and embedding but at the same \n  time avoiding a linear connection:\n\n- **Select Embedding Methods**\n    - for demonstration, the author is using  4 unsupervised embedding algorithms: 2 with node attributes and 2 without node attributes\n\n- **Define Sense Features**\n\n- **Augment EMbeddings**\n    - Augment original embedding with sense features with two constraints to reach nuclear norm minimization\n    - Sparsity: each embedding dimension focuses on the subset of features to remove noise\n    - Orthogonality:  Ensure embedding dimensions are diverse\n\n- **Reduce Nuclear Norm**\n   - Train the embeddings to reduce the nuclear norm to explain Metrix.\n\nThe paper presents a good amount of examples/case studies on XM.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Conduct some experiments on how the selection of sense features   might impact the interpretability \n- To diversify the approach, provide some guidelines on how these sense features are directly connected to the use case and depending on the use case how a user should select these features. \n-  If there are any examples that showcase the sensitivity of the nuclear norm with different hyperparameter choices: are there any scenarios where focusing on reducing the nuclear norm might also be removing the important embeddings", "broader_impact_concerns": "- **Bias In Sense Feature selection**\n   - The XM frameworks rely on the selection of sense features, poorly chosen sense features will lead to irrelevant explanations.\n   - Recommend having \"Best Practices\" on choosing these sense features and how to adopt these features when the usecase is different for example: multimodality (text, videos, images)\n\n- **Interoperability vs accountability**\n     - XM depends heavily on sense features and that might improve the interoperability but fail to guarantee accountability. Example: A biased sense feature may incorrectly highlight certain groups or nodes as \"less central\" or \"less connected,\" influencing decisions in hiring, credit scoring, or law enforcement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gk0cCimwQu", "reviewer": "Reviewer_czVb", "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": "This is an interesting are of research study that could be highly useful for future research in the field and model development since human interpretability is one component lost in the learning process for machine learning models. \n\nThat said, the paper needs to be organized in a more effective manner. If the Related Work section is moved after the Introduction, the clarity of the work improves. Moreover, the authors should consider including Tables to summarize the key properties that their model contributes, and the properties of other baseline models in terms of challenges and what they accomplish. This would help to better motivate the work. \n\nThere needs to be a problem formulation section to summarize what the graph looks like namely by what do the nodes/edges represent. \nThe sense features of this work are interesting, but it just seems like engineered features which one can directly compute based on the structure of the graph e.g., by degree, and betweenness centrality.\n\nFurthermore, it is unclear how we know the 15 hand-selected features are the best explainable or observed features for the task, since latent embeddings are more flexible to learn but can also learn hidden properties or correlations in the dataset that do not map to any observed feature.", "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 presents a method for understanding what each dimension of a node embedding method means, with respect to a set of human-understandable sense features defined on nodes. To evaluate Explain matrices, their nuclear norms are minimized.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the comments above for details.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qzqy3dir8C", "reviewer": "Reviewer_ZtPJ", "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": "STRENGHTS:\nModel interpretability is a valuable area of study.  This approach shows general reduction in the nuclear norm and higher AUC with minimal computation time for several different embedding algorithms.\n\nTrials are run multiple times to produce errorbars.\n\n\nWEAKNESSES:\nThe text needs to be cleaned up to flow better and remove redundancy, particularly in the introduction.  Each sentence is largely well structured, but the overall arc to the content could be improved.  Other sections of the next need improvements to clarity and explanation as well (see Requested Changes).  In general, the text needs to do a better job bringing the reader along on the journey- we did X, we saw Y result, this demonstrates Z.\n\nThe benefit of this approach is supposed to be around interpretability, but this is never explored- the results are never interpreted.  It's unclear after reading the paper what the user of this approach can do that they couldn't do without it.  \n\nIt's mentioned that the choice of features is very important, but this is not explored.  There needs to be a set of experiments which shows how the choice of features impacts the results.\n\nComparison to other methods is not explored.  All comparisons are shown in terms of Embeddings w/wo this approach.  Some of the other fundamentally different approaches such as those covered in the related works should be shown.", "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": "The authors introduce a framework for producing explainable node embeddings by minimizing the nuclear norm.  This approach can be shown to reduce the nuclear norm for a number of embedding approaches with comparable computational performance to other methods.  This approach is said to produce more explainable node embeddings, however, this is not well explored or demonstrated in the paper.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Allowing the text to wrap on the x-axis of Figure 1 would make it more readable.\n\nThe barbell and karate club examples may be too much of toy examples- I would suggest picking one of them, and one actual real world example- the Karate Club Network is a fine dataset, but it's really not a \"real world\" dataset.  Actual real world graph problems have hundreds or thousands of nodes.  I would suggest keeping the karate club as the toy example and dropping the dumbbell example as I don't know that it is that illuminating.  \n\nThe discussion in \"Structural vs. Positional Sense Features\" is hard to follow.  In part this is because of the formatting which puts the Figure on the next page.  However, the text could also be improved.  The sentence such as \"We define a second set of positional features\" seems out of nowhere- where was the first set of defined (do we assume it's the full subset up in the first paragraph of 2.1)? What are they for this example?\n\nThe subset of chosen sense features was selected because of the correlation among the broader set.  However, from Figures 1 and 2, the remaining features still appear to be highly redundant.\n\nI would consider leading with some kind of tangible example in the introduction.  Perhaps pick a network, show what the embeddings look like by current approaches, show what can be understood given the approach used in this method.  In its current formulation, interpretability is the key advantage, but what can be interpreted and what value that offers does not come until the very end of the paper.\n\n3.2 needs further explanation.  It's shown that the distribution shifts and narrows, but what does this tell the reader?  Essentially this result needs to be interpreted.  Similarly 3.3 needs better explanation.  It is stated that the nuclear norms are lower- explain the \"so what\" to the reader.  \n\nThe opening of the discussion is entirely unclear- \"the explanations are granular\".  I don't understand what this means.  \n\nWhile it can go anywhere, I think putting the related works after the intro might help the narrative in this case.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As I mentioned, I am marking the paper as "Accept" but I would encourage authors to use the opportunity to polish the paper a bit more before uploading camera-ready version.
Decision: Accept (poster)