# SparGE: Sparse Coding-based Patient Similarity Learning via Low-rank
Constraints and Graph Embedding

Xian Wei ∗, See Kiong Ng 1, Tongtong Zhang 2, Yingjie Liu 3

<EMAIL_ADDRESS>∗<EMAIL_ADDRESS>1<EMAIL_ADDRESS>2,
<EMAIL_ADDRESS>)

###### Abstract

Patient similarity assessment (PSA) is pivotal to evidence-based and
personalized medicine, enabled by analyzing the increasingly available
electronic health records (EHRs). However, machine learning approaches for PSA
has to deal with inherent data deficiencies of EHRs, namely missing values,
noise, and small sample sizes. In this work, an end-to-end discriminative
learning framework, called _SparGE_ , is proposed to address these data
challenges of EHR for PSA. _SparGE_ measures similarity by jointly sparse
coding and graph embedding. First, we use low-rank constrained sparse coding
to identify and calculate weight for similar patients, while denoising against
missing values. Then, graph embedding on sparse representations is adopted to
measure the similarity between patient pairs via preserving local
relationships defined by distances. Finally, a global cost function is
constructed to optimize related parameters. Experimental results on two
private and public real-world healthcare datasets, namely SingHEART and MIMIC-
III, show that the proposed _SparGE_ significantly outperforms other machine
learning patient similarity methods.

##  1 INTRODUCTION

Evidence-based and personalized medicine is crucial for healthcare
transformation in quality, for which patient similarity assessment (PSA) plays
a prominent part. Measuring how similar a pair of patients are according to
their health records, PSA helps to improve the quality of clinical decision
making without incurring additional efforts from doctors. In fact, PSA is
practised by experienced human doctors who often make their clinical decisions
by incorporating their medical knowledge, with their prior experience on
patients who are diagnosed with similar diseases or showing similar symptoms.

The increasing availability of electronic health records (EHRs) which are now
collected as part of routine care provides an unprecedented opportunity for
patient similarity assessment through machine learning, which can further
enable the automation of personalized medicine [1, 2], disease classification
[3], trajectory prediction [4], cohort study [5], medical diagnosis [6] and
more. Patient similarity learning involves learning an effective mathematical
representation of the patients based on the information in the EHRs, and
learning a reliable similarity metric between the patients.

However, as EHRs consist of heterogeneous and high-dimensional multi-source
data elements, including diagnosis codes, lab results, prescription data,
patient-reported symptoms, and so on, there are inherent data challenges of
EHRs that patient similarity learning needs to address, specifically: i)
Missing values: EHR data typically consist of a high rate of missing values,
as patients have different sets of lab tests and medical conditions; ii)
Noise: EHRs are also innately noisy, especially when patient-reported data;
and iii) Sparsity: EHR consist of data elements that are high-dimensional
which require large patient sample sizes especially with data-hungry machine
learning methods.

To tackle these challenges, we construct the patient similarity metric by
appealing to the principle of sparsity, using an end-to-end discriminative
learning framework that jointly learns low rank constrained _Spar_ se coding
and _G_ raph _E_ mbedding (_SparGE_) for patient similarity. _SparGE_ learns a
similarity measurement by sequentially performing low-rank constrained sparse
coding and graph embedding: low-rank constrained sparse coding is used for
finding and weighting similar patients, as well as denoising against missing
values, while graph embedding on sparse representation is used for
constructing distances to measure the similarity between patient pairs.

###  1.1 Related Works

Various approaches have been proposed for patient similarity. The classical
approaches used standard metrics such as Euclidean distance in raw data space
to measure the similarity among patients [3, 7], but the raw data often have
rich redundant and heterogeneous information with unknown distribution.

As such, most works transformed the raw data into a novel representation
space, where various types of similarity metrics are constructed to describe
the similarity between patients. The typical transformations include kernel
function [8], and dimensionality reduction methods, such as Principal
Component Analysis (PCA), and factor analysis [9]. For example, [10] learned a
distance metric in low-dimensional embedding of data where the data points
that are to be linked are pushed as close as possible, while the points that
are not to be linked are pulled away as far as possible. Similar approaches
were also proposed in [11, 12, 13, 14, 15]. These approaches relied on the
construction of relation matrix in raw data space, and then convey it from
high-dimensional raw data space to lower dimensions. Finding an optimal
distance metric is then equivalent to finding an optimal dimension reduction
projection matrix. However, these approaches often suffer from low efficiency
in extracting nonlinear discrimination among data due to their shallow linear
projection architecture.

Recent developments in deep learning have shown that constructing metrics in
deep representation space can improve discriminative patient similarity
learning [16, 17, 18, 19]. However, such approaches often require not only
special computing hardware which may not (yet) be available in a traditional
hospital setting, but also a very large amount of training data and
prohibitive training efforts as compared to shallow learning approaches. The
aforementioned methods are also vulnerable to noise and missing values, which
are prevalent in EHR data.

Some researchers have looked into measuring patient similarity based on the
concept of sparsity. For example, the methods in [20, 21, 22] imposed the
sparse regularization on dimension reduction projection to reduce irrelevant
and redundant information, but they did not consider the robustness to noise
corruption. Also, most of the methods mentioned above are not competent in
handling incomplete input matrices[23]. Most research [24, 25] opt to fill the
data matrix with imputation approaches. On the other hand, low-rank matrix
completion methods have been developed for solving missing value problem [26,
27], which inspire us to utilize low-rank tools for this work.

Another common inadequacy of the current models is that they neglect the
underlying relationships between the data elements during the learning
process. Many of the coded values in EHRs using standards such as the ICD-9
code[23] have underlying relationships but these useful relationships are not
captured and exploited by most of metric learning methods. We propose to
capture the underlying structural relationships between the various data value
elements using graph embedding to exploit the structural relationship to
address the innate data challenges for patient similarity learning. In short,
this paper proposes a similarity learning scheme SparGE using low-rank sparse
coding to handle the problem of noise and missing values, while preserving the
innate relational structure of the data elements by graph-embedding
constraint.

##  2 FINDING SIMILAR PATIENTS VIA LOW RANK CONSTRAINED SPARSE CODING

As mentioned previously, patient similarity learning involves two aspects: i)
finding and weighting similar patients, which is discussed in this section,
and ii) explicitly measuring the distance between similar patients, which will
be discussed in Section 3 and Section 3.3.

In this work, we find similar patients by applying sparse coding with low-rank
approximation of the dictionary. The low-rank approximation of the dictionary
prevents the outliers and missing values from degrading the model, while the
sparse representation is for selecting similar patients while being robust to
random Gaussian noise.

Let the vector
$\mathbf{x}_{i}=[\mathbf{x}_{i}^{1},\mathbf{x}_{i}^{2},\cdots,\mathbf{x}_{i}^{m}]\in\mathbb{R}^{m}$
contain all measurable EHR variables for the $i^{\text{th}}$ patient, with $m$
being the number of all biomarkers. Let
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}]\in\mathbb{R}^{m\times
n}$ be a collection of $n$ patients’ raw EHR data points, potentially with
excessive noises.

The low-rank approximation approach aims to find a low-rank matrix
$\mathbf{Z}$ that is as close to $\mathbf{X}$ as possible [28, 29], by
optimizing the following minimization problem

$\mathop{\arg\min}_{\mathbf{Z}}\|\mathbf{Z}_{\Omega}-\mathbf{X}_{\Omega}\|_{F}^{2}+\lambda\|\mathbf{Z}\|_{*},$
(1)

where $\|\mathbf{Z}\|_{*}$ denotes the nuclear norm of the matrix
$\mathbf{Z}$, $\lambda\in\mathbb{R}^{+}$ weights the low-rank regularization
against the reconstruction error,

$\mathbf{Z}_{\Omega}=\mathbf{H}_{\Omega}\odot\mathbf{X}+\mathbf{N}.$

Therein, $\odot$ is the element-wise multiplication operator, ${\Omega}$
indicates the support of observed entries, $\mathbf{H}_{\Omega}$ and
$\mathbf{N}$ are the sampling matrix and noise matrix, respectively.

Various works have observed that data can have strong self-expressiveness
property [30, 31, 32, 33], i.e., each data point can be efficiently
represented as a linear or affine combination of some selected points in the
dataset. The underlying assumption of self-expressiveness property is that an
incoming new data point can be embedded into a subspace spanned by a selected
subset of the dataset. In this work, we follow the observation and assume that
the EHR data of a patient can be expressed by other patients, which
encapsulates the fundamental assumption of patient similarity assessments.

Let $\mathbf{Z}$, i.e., the low-rank approximated matrix of $\mathbf{X}$, be a
self-expressive dictionary for all patients except the test patient, in which
each column vector (or point) contains the EHR data for a patient, and that
each column vector can be written as a linear combination of the other column
vectors. Given a new unlabelled test patient $\mathbf{z}$, we wish to
represent it in a subspace spanned by a subset from $\mathbf{Z}$, i.e.,
finding only a few elements in $\mathbf{Z}$ to approximate $\mathbf{z}$.
Formally, this can be described as

$\mathbf{z}=\mathbf{Z}\bm{\phi},$ (2)

where $\bm{\phi}\in\mathbb{R}^{n}$ is the sparse representation of
$\mathbf{z}$, i.e.,most entries are zero in $\bm{\phi}$. Hereby, $\bm{\phi}$
corresponds to adaptively select and weight a few elements from $\mathbf{Z}$.
Each absolute value in $\bm{\phi}$ reflects the importance of the selected
element (patient) for approximating the test patient $\mathbf{z}$, i.e., the
similarity between the selected patient and the test patient.

With a fixed dictionary $\mathbf{Z}$, there are several ways of finding the
sparse representation $\bm{\phi}$. One popular solution of the sparse learning
problem above is given by solving the following minimization problem

$\bm{\phi}^{*}:=\operatorname*{argmin}_{\bm{\phi}\in\mathbb{R}^{n}}\tfrac{1}{2}\|\mathbf{z}-\mathbf{Z}\bm{\phi}\|_{2}^{2}+g(\bm{\phi}).$
(3)

Therein, the first term penalizes the reconstruction error of sparse
representations, and the second term is a sparsity promoting regularizer.
Often, the function $g$ is chosen to be separable, i.e., its evaluation is
computed as the sum of functions of the individual components of its argument.
There are many choices for $g$ in the literature, such as the
$\ell_{0}$-(quasi-)norm, $\ell_{1}$-(quasi-)norm and their variations [34,
35], which have promoted the global sparse structures of $\bm{\phi}$.

Finally, given input data $\mathbf{X}$, by combining the Eq. (1) and Eq. (3),
the low-rank approximation based sparse coding problem can be formulated as

$\operatorname*{min}_{\bm{\phi}\in\mathbb{R}^{n},\mathbf{Z}}\tfrac{1}{2}\|\mathbf{z}-\mathbf{Z}\bm{\phi}\|_{2}^{2}+g(\bm{\phi})+\lambda_{1}\|\mathbf{Z}_{\Omega}-\mathbf{X}_{\Omega}\|_{F}^{2}+\lambda_{2}\|\mathbf{Z}\|_{*}.$
(4)

The two goals of (4) are to: i) Reconstruct the clean data $\mathbf{Z}$ from
raw input $\mathbf{X}$; ii) Given a query patient $\mathbf{z}$, find minimal
number of patients (the sparsity of $\bm{\phi}$), to express the query
patient. The non-zero entries in $\bm{\phi}$ denote the indices of similar
patients and their values reveal the linear dependence between the query
patient and selected similar patients.

##  3 JOINT LEARNING OF LOW-RANK CONSTRAINED DICTIONARY AND GRAPH EMBEDDING

In Section 2, we treat data as the predefined dictionary, and the success of
Eq. (2) and Eq. (3) is thus heavily dependent on the self-expressiveness
property of the data. However, there is no guarantee that predefined basis
vectors (dictionary) will be well-matched to the structure of test patient
data. In Section in Section 3.1, we propose that a low-rank constrained
dictionary be learned from the data so as to have more flexibility to adapt
the sparse representation to the patients’ EHR data. Then, in Section 3.2, we
apply dimension reduction on the sparse representations to calculate the
distance of patient pairs in low-dimensional space, in order to explicitly
measure the similarity between patients. Finally, in Section 3.3, a global
cost function is constructed to jointly learn a low-rank constrained
dictionary and a projection for graph embedding.

###  3.1 Low-rank Constrained Dictionary Learning

Formally, let
$\mathbf{D}:=[\mathbf{d}_{1},\ldots,\mathbf{d}_{k}]\in\mathbb{R}^{m\times k}$
be a shared dictionary that adaptively represents a signal as a sparse vector
${\bm{\phi}}\in\mathbb{R}^{k}$, i.e.,

$\mathbf{z}=\mathbf{D}{\bm{\phi}}.$ (5)

Dictionary learning aims to find a collection of _atoms_
$\mathbf{d}_{i}\in\mathbb{R}^{m}$ for $i=1,\ldots,k$, such that each data
point can be approximated by a linear combination of a small subset of atoms
in $\mathbf{D}$. Given a collection of $n$ data points in $\mathbb{R}^{m}$ as
$\mathbf{Z}:=[\mathbf{z}_{1},\ldots,\mathbf{z}_{n}]\in\mathbb{R}^{m\times n}$,

$\mathbf{Z}=\mathbf{D}\bm{\Phi},$ (6)

with $\bm{\Phi}:=[\bm{\phi}_{1},\ldots,\bm{\phi}_{n}]\in\mathbb{R}^{k\times
n}$. Based on Eq. (6),

$\text{rank}(\mathbf{Z})=\min\\{\text{rank}(\mathbf{D}),\text{rank}(\bm{\Phi})\\}.$

In other words, the low rank of $\mathbf{D}$ results in the low rank of
$\mathbf{Z}$. The solution of the above dictionary learning problem,
associated with the low-rank approximation, is given by solving the following
minimization problem:

$\operatorname*{min}_{\mathbf{Z},\mathbf{D},\bm{\Phi}}\tfrac{1}{2}\|\mathbf{Z}-\mathbf{D}\bm{\Phi}\|_{F}^{2}+\sum_{i=1}^{n}g(\bm{\phi}_{i})+\lambda_{1}\|\mathbf{Z}_{\Omega}-\mathbf{X}_{\Omega}\|_{F}^{2}+\lambda_{2}\|\mathbf{D}\|_{*},$
(7)

Therein, the weighting factors $\lambda_{1},\lambda_{2}\in\mathbb{R}^{+}$
control the influence of two parts on the final solution,
$\mathbf{D}\in\mathcal{D}$ with

$\displaystyle\mathcal{D}:=\left\\{\mathbf{D}\in\mathbb{R}^{m\times
k}\big{|}\|\mathbf{d}_{i}\|_{2}\leq 1\right\\}.$

Once $\mathbf{D}$ is given, Problem (7) can be rewritten as the following
decoupled sample-wise _sparse regression_ problem. Specifically, for each
sample $\mathbf{z}$, we have:

$\min_{\bm{\phi}\in\mathbb{R}^{k},\mathbf{Z}}f_{\mathbf{x}}(\bm{\phi},\mathbf{Z}):=\tfrac{1}{2}\|\mathbf{z}-\mathbf{D}\bm{\phi}\|_{2}^{2}+g(\bm{\phi})+\lambda_{1}\|\mathbf{Z}_{\Omega}-\mathbf{X}_{\Omega}\|_{F}^{2}.$

The solution of the sample-wise sparse regression problem can be treated as a
function in $\mathbf{z}$, i.e.,

$\bm{\phi}_{\mathbf{D}}(\mathbf{x},\mathbf{z}):=\operatorname*{argmin}_{\bm{\phi}\in\mathbb{R}^{k}}f_{\mathbf{x}}(\bm{\phi},\mathbf{Z})$
(8)

The implicit function $\bm{\phi}_{\mathbf{D}}(\mathbf{x},\mathbf{z})$ is
locally differentiable with respect to $\mathbf{D}$, $\mathbf{x}$ and
$\mathbf{z}$. We refer the reader to the Supplementary Materials for more
details. Such a property allows us to integrate
$\bm{\phi}_{\mathbf{D}}(\mathbf{x},\mathbf{z})$ into a larger learning
architecture.

Furthermore, as suggested by the works of [36, 32, 37], the sparse
representation above can be further processed to reveal the underlying
discriminative information which benefits both supervised and unsupervised
learning tasks. In other words, once the sparse representations are calculated
for all patients’ EHR data via Eq. (24), we can assume that similar patients
have similar sparse structures. However, the explicit measurement of the
pairwise similarity is not clearly constructed. In the next section, we show
how to learn an explicit similarity measurement in the sparse domain.

###  3.2 Learning Similarity Measurement in Sparse Domain

With the sparse representations of all samples at hand, specific similarity
learning algorithms can be directly applied to these sparse coefficients to
extract further discriminative information between patients. We can learn a
patient similarity measurement in the sparse domain as follows.

The generalized Mahalanobis distance is often used for the patient similarity
problem [20, 13, 15]. In this work, we construct a generalized Mahalanobis
distance in the sparse domain

$d^{2}(\bm{\phi}_{i},\bm{\phi}_{j})=(\bm{\phi}_{i}-\bm{\phi}_{j})^{\top}\mathbf{P}(\bm{\phi}_{i}-\bm{\phi}_{j})$
(9)

to measure the similarity between $\bm{\phi}_{i}$ and $\bm{\phi}_{j}$.
Therein, ${\mathbf{P}}\in\mathbb{R}^{k\times k}$ is a Symmetric Positive Semi-
Definite (SPSD) matrix to be learned.

In consideration of the difficulty of directly learning ${\mathbf{P}}$, it is
reasonable to assume that the similarity is measured in an embedded space of
sparse representations via

$\mathbf{y}_{i}=\mathbf{U}^{\top}\bm{\phi}_{i},$ (10)

where $\mathbf{U}\in\mathbb{R}^{k\times l}$ is an dimension reduction
transformation with $l\ll k$, $\mathbf{y}_{i}\in\mathbb{R}^{l}$ is a
representation in the low-dimensional embedded space. Since ${\mathbf{P}}$ is
a SPSD matrix, $\mathbf{U}$ could be viewed as a component for approximating
${\mathbf{P}}$ with

${\mathbf{P}}=\mathbf{U}\mathbf{U}^{\top}.$

Then, the Eq. (9) could be rewritten as

$\begin{split}d^{2}(\bm{\phi}_{i},\bm{\phi}_{j})&=(\mathbf{U}^{\top}\bm{\phi}_{i}-\mathbf{U}^{\top}\bm{\phi}_{j})^{\top}(\mathbf{U}^{\top}\bm{\phi}_{i}-\mathbf{U}^{\top}\bm{\phi}_{j})\\\
&=(\mathbf{y}_{i}-\mathbf{y}_{j})^{\top}(\mathbf{y}_{i}-\mathbf{y}_{j})\\\
&=\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{2}^{2}\\\
&=d^{2}(\mathbf{y}_{i},\mathbf{y}_{j})\end{split}$ (11)

The generalized Mahalanobis distance in sparse domain could be obtained by
computing the Euclidean distance in $\mathbb{R}^{l}$. Once
$\\{\bm{\phi}_{i}\\}$ and $\mathbf{U}$ are given, $\\{\mathbf{y}_{i}\\}$ are
computed by Eq. (10). Hence, finding $k$ similar patients is achieved by
applying Nearest Neighbourhood method on $\\{\mathbf{y}_{i}\\}$. Note that
from Eq. (27), the key is to learn the parameters $\mathbf{Z}$, $\mathbf{D}$
and $\mathbf{U}$. We will propose a unified cost function, for jointly
learning $\mathbf{Z}$, $\mathbf{D}$ and $\mathbf{U}$, with both the supervised
and the unsupervised settings in the next section.

###  3.3 The Proposed _SparGE_ Method

The previous sections introduce the low-rank constrained dictionary and the
patient similarity measurement. In this section, we design a cost function
that jointly learns both the low-rank constrained dictionary and an orthogonal
transformation, to efficiently extract low-dimensional features on sparse
representations.

####  3.3.1 A Generic Joint Learning Framework

Let us denote by
$\mathbf{X}:=[\mathbf{x}_{1},\ldots,\mathbf{x}_{n}]\in\mathbb{R}^{m\times n}$
the given data matrix containing $n$ high-dimensional data samples, and
$\mathbf{Y}:=[\mathbf{y}_{1},\ldots,\mathbf{y}_{n}]\in\mathbb{R}^{{l}\times
n}$ with ${l}<m$ being its corresponding unknown low-dimensional
representation via some mapping

$\mathcal{L}\colon\mathbf{x}_{i}\mapsto\mathbf{z}_{i}\mapsto\bm{\phi}_{i}\mapsto\mathbf{y}_{i},\quad\qquad\text{for
all~{}}i=1,\ldots,n,$ (12)

where $\mathbf{x}_{i},\mathbf{z}_{i},\bm{\phi}_{i},\mathbf{y}_{i}$ denote the
input signal, the recovered clean signal, the sparse vector, and the low-
dimensional representation, respectively.

To achieve computational efficiency, many classic linear dimension reduction
methods restrict the row vectors in $\mathbf{U}$ to be orthonormal, i.e.,
$\mathbf{U}$ belongs to the Stiefel manifold

$\mathcal{U}:=\\{\mathbf{U}\in\mathbb{R}^{k\times
l}|\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_{l}\\}.$ (13)

The loss introduced by the mapping
$\mathcal{L}\colon\mathbf{x}_{i}\mapsto\mathbf{z}_{i}\mapsto\bm{\phi}_{i}\mapsto\mathbf{y}_{i},\forall
i$ can then be measured by the function

$\begin{split}&\operatorname*{argmin}_{\mathbf{Z},\mathbf{D},\mathbf{U}}\;\mathcal{L}_{(\mathbf{Z},\mathbf{D},\mathbf{U})}(\mathbf{X};\mathbf{Y})\\\
&\text{subject
to},\;\bm{\phi}_{\mathbf{D}}(\mathbf{x},\mathbf{z}):=\operatorname*{argmin}_{\bm{\phi}\in\mathbb{R}^{k}}f_{\mathbf{x}}(\bm{\phi},\mathbf{Z})\end{split}$
(14)

which jointly learns the clean data, the dictionary and the linear orthogonal
projection, combining the Graph Embedding formulation in Eq. (18) and the
sparse coding formulation in Eq. (7) to be described in the next section.
Graph Embedding is well known as an efficient tool to extract local similarity
of data points. In this way, _SparGE_ jointly learns low-rank constrained
sparse coding and graph embedding for patient similarity.

In the next section, we give two examples to evaluate the
problem(LABEL:eq_trace_quotient_dictLearn), but it is important to note that
the proposed _SparGE_ is a flexible and generic joint learning framework and
thus not limited to two methods described.

Considering that $\mathcal{L}$ in (LABEL:eq_trace_quotient_dictLearn) is a
smooth function and has the first-order derivatives to
$\mathbf{D},\mathbf{U}$, the simple gradient method can be used for optimizing
the function. In the work, we apply the alternating optimization framework
[38] to solve the proposed minimization problem
(LABEL:eq_trace_quotient_dictLearn), i.e., solve for one of parameters if the
others are considered fixed. A generic gradient algorithm is summarized in
Algorithm 1. We refer the reader to the Supplementary Materials for more
details.

The formulations in Eq. (1), Eq. (4) and Eq. (7) involve minimizing the
nuclear norm $\min\|\mathbf{Q}\|_{*}$, i.e., computing the low-rank
approximation $\mathbf{Q}^{\star}$ to a given matrix $\mathbf{Q}$. It can be
decomposed using the famous nuclear norm minimization [28, 29], which
repeatedly shrinks the singular values of an appropriate matrix. One simple
method is Singular Value Thresholding (SVT) [39, 40]. Formally, let
$\mathbf{Q}$ admit an economic singular value decomposition (SVD) as
$\mathbf{Q}=\mathbf{U}\Sigma\mathbf{V}^{\top}$ where $\mathbf{U}$ are the left
singular vectors, $\mathbf{V}$ are the right singular vectors, and $\Sigma$ is
a diagonal matrix and has singular values on the diagonal. Performing SVT on
$\mathbf{Q}$ is denoted by

$SVT(\mathbf{Q})=\mathbf{U}S_{\zeta}(\Sigma)\mathbf{V}^{\top},$

where

$\displaystyle S_{\zeta}(x):=\left\\{\begin{array}[]{ll}x-\zeta,\mbox{ if
$x>\zeta$}\\\ 0,\mbox{otherwise}\\\ \end{array}\right.$ (17)

with $\zeta$ being a constant as threshold for singular values.

Input : Given training set $\textbf{X}\in\mathbb{R}^{m\times n}$, parameters
$\lambda_{1}$, $\lambda_{2}$, $\gamma$, $\zeta$ ;

Output: $\mathbf{Z}^{*},\mathbf{D}^{*},\bm{\Phi}^{*},{\mathbf{U}}^{*}$;

Step 1: Initialize $\mathbf{Z}^{(0)}$ by applying SVT on $\mathbf{X}$. Then,
learn $\mathbf{D}^{(0)}$ from $\mathbf{Z}^{(0)}$. Finally, compute
$\bm{\Phi}^{(0)}$, ${{\mathbf{U}}}^{(0)}$, given fixed $\mathbf{Z}^{(0)}$ and
$\mathbf{D}^{(0)}$ ;

Step 2: Set $j=j+1$ , fix $\mathbf{Z}^{(j)}$, $\mathbf{D}^{(j)}$, compute
sparse coefficients ${\bm{\Phi}}^{(j+1)}$ via Eq. (24) ;

Step 3: Compute the search direction
$\mathbf{H}^{(j)}=\text{grad}_{\mathcal{L}}(\mathbf{D}^{(j)},{{\mathbf{U}}}^{(j)})$
;

Step 4: Update
$({\hat{\mathbf{D}}}^{(j+1)},{\hat{\mathbf{U}}}^{(j+1)})\\!\leftarrow\\!({{\mathbf{D}}}^{(j)},{{\mathbf{U}}}^{(j)})\\!+\\!\gamma\mathbf{H}^{(j)}$.
$\hat{{\mathbf{D}}}^{(j+1)}=SVT(\hat{{\mathbf{D}}}^{(j+1)})$. Project
${\hat{\mathbf{D}}}^{(j+1)},{\hat{\mathbf{U}}}^{(j+1)}$ onto
${{\mathbf{D}}}^{(j+1)}\in\mathcal{D},{{\mathbf{U}}}^{(j+1)}\in\mathcal{U}$ ;

Step 5: Update $\mathbf{Z}^{(j+1)}={{\mathbf{D}}}^{(j+1)}{\bm{\Phi}}^{(j+1)}$
;

Step 6: If $\big{\|}\mathbf{H}^{(j)}\big{\|}$ is small enough, stop.
Otherwise, go to Step 2;

Algorithm 1 A _SparGE_ Algorithm.

####  3.3.2 Unsupervised Graph Embedding

Given a data set
$\mathbf{X}_{i}=[\mathbf{x}_{i1},\ldots,\mathbf{x}_{in_{i}}]\in\mathbb{R}^{m\times
n_{i}}$, $i=1,\ldots,c$, where $c>1$ denotes the class number and $n_{i}$
denotes the number of data samples belonging to $i$-th class. The
corresponding sparse coefficients are denoted by
${{\bm{\Phi}}}_{i}=[\bm{\phi}_{i1},\ldots,\bm{\phi}_{in_{i}}]\in\mathbb{R}^{k\times
n_{i}}$, and
${\bm{\Phi}}=[{{\bm{\Phi}}}_{1},\ldots,{{\bm{\Phi}}}_{c}]\in\mathbb{R}^{k\times
n}$. Let ${d}_{ij}:=\exp(-\|{\bm{\phi}}_{i}-{\bm{\phi}}_{j}\|_{2}^{2}/t)$
denotes the Laplacian similarity between two sparse vectors ${\bm{\phi}}_{i}$
and ${\bm{\phi}}_{j}$ with constant $t>0$.

For the whole dataset $\mathbf{X}$, let us define the local Laplacian matrix
and the non-local Laplacian matrix
$\mathbf{L}_{L}={\bm{\Xi}_{L}}-\mathbf{M}_{L}$ in $\mathbb{R}^{n\times n}$,
$\mathbf{L}_{N}={\bm{\Xi}_{N}}-\mathbf{M}_{N}$ in $\mathbb{R}^{n\times n}$,
respectively. $\mathbf{M}_{N}:=\\{\mathbf{d}_{ij}\\}$ and
$\mathbf{M}_{N}:=\\{0\\}$ when $\bm{\phi}_{i}$, $\bm{\phi}_{j}$ are adjacent.
$\mathbf{M}_{L}:=\\{0\\}$ and $\mathbf{M}_{L}:=\\{\mathbf{d}_{ij}\\}$ when
$\bm{\phi}_{i}$, $\bm{\phi}_{j}$ are non-adjacent. Both ${\bm{\Xi}_{L}}$ and
${\bm{\Xi}_{N}}$ are diagonal with ${\bm{\Xi}_{L}}_{ii}:=\sum_{j\neq
i}{\mathbf{M}_{L}}_{ij},\forall j$ and ${\bm{\Xi}_{N}}_{ii}:=\sum_{j\neq
i}{\mathbf{M}_{N}}_{ij},\forall j$. Both $\mathbf{L}_{L}$ and $\mathbf{L}_{N}$
are Symmetric Positive Semi-Definite (SPSD). We utilize a generic algorithmic
framework with supervised form to find optimal ${\mathbf{U}}\in\mathcal{U}$ is
formulated as a minimization problem of the so-called _trace quotient_ or
_trace ratio_ , i.e.,

$\operatorname*{argmin}_{{\mathbf{U}},\mathbf{Z},\mathbf{D}}\;\frac{\operatorname{tr}({\mathbf{U}}^{\top}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}\mathbf{L}_{L}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}^{\top}{\mathbf{U}})}{\operatorname{tr}({\mathbf{U}}^{\top}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}\mathbf{L}_{N}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}^{\top}{\mathbf{U}})},$
(18)

####  3.3.3 Supervised Graph Embedding

It is possible to develop supervised versions of the graph embedding (18) by
taking the class labels into account. Assume that there are $c$ classes of
patients.

Let
$\mathbf{X}_{i}=[{\mathbf{x}}_{i1},\ldots,{\mathbf{x}}_{in_{i}}]\in\mathbb{R}^{m\times
n_{i}}$ for $i=1,\ldots,c$ with $n_{i}$ being the number of samples in the
$i^{\mathrm{th}}$ class. The corresponding sparse coefficients are denoted by
${{\bm{\Phi}}}_{i}:=[{\bm{\phi}}_{i1},\ldots,{\bm{\phi}}_{in_{i}}]\in\mathbb{R}^{r\times
n_{i}}$, and
${{\bm{\Phi}}}:=[{{\bm{\Phi}}}_{1},\ldots,{{\bm{\Phi}}}_{c}]\in\mathbb{R}^{r\times
n}$ with $n=\sum\limits_{i=1}^{c}n_{i}$.

The main idea in supervised methods is to maintain the original neighbor
relations of points from the same class while pushing apart the neighboring
points of different classes and the class labels are used to build the graph.
It aims to preserve localities in such a supervised graph, will result in
samples from the same class being projected close-by in the reduced space.

Let $\mathfrak{N}_{k_{1}}^{+}({\bm{\phi}}_{i})$ denote the set of $k_{1}$
nearest neighbors which share the same label with ${\bm{\phi}}_{i}$, and
$\mathfrak{N}_{k_{2}}^{-}({\bm{\phi}}_{i})$ denote the set of $k_{2}$ nearest
neighbors among the data points whose labels are different to that of
${\bm{\phi}}_{i}$. We construct two matrices
$\mathbf{Z}^{+}:=\\{z_{ij}^{+}\\}\in\mathbb{R}^{n\times n}$ and
$\mathbf{Z}^{-}:=\\{z_{ij}^{-}\\}\in\mathbb{R}^{n\times n}$ with

$z_{ij}^{+}=\left\\{\\!\\!\begin{array}[]{ll}d(\bm{\phi}_{i},\bm{\phi}_{j}),&{\bm{\phi}}_{j}\in\mathfrak{N}_{k_{1}}^{+}({\bm{\phi}}_{i})~{}\text{or}~{}{\bm{\phi}}_{i}\in\mathfrak{N}_{k_{1}}^{+}({\bm{\phi}}_{j}),\\\
0,&\text{otherwise},\end{array}\right.$ (19)

and

$z_{ij}^{-}=\left\\{\\!\\!\begin{array}[]{ll}d(\bm{\phi}_{i},\bm{\phi}_{j}),&{\bm{\phi}}_{j}\in\mathfrak{N}_{k_{1}}^{-}({\bm{\phi}}_{i})~{}\text{or}~{}{\bm{\phi}}_{i}\in\mathfrak{N}_{k_{1}}^{-}({\bm{\phi}}_{j}),\\\
0,&\text{otherwise}.\end{array}\right.$ (20)

Then, the Laplacian matrices for characterizing the inter-class and intra-
class locality are defined as

$\mathbf{L}^{-}=\mathbf{Y}^{-}-\mathbf{Z}^{-},\quad\text{and}\quad\mathbf{L}^{+}=\mathbf{Y}^{+}-\mathbf{Z}^{+},$
(21)

where $\mathbf{Y}^{+}$ and $\mathbf{Y}^{-}$ are two diagonal matrices defined
as

$y^{+}_{ii}=\sum_{j\neq i}z_{ij}^{+},\quad\text{and}\quad
y^{-}_{ii}=\sum_{j\neq i}z_{ij}^{-}.$ (22)

Then, we construct the following functions , i.e.,

$\operatorname*{argmin}_{{\mathbf{U}},\mathbf{Z},\mathbf{D}}\;\frac{\operatorname{tr}({\mathbf{U}}^{\top}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}\mathbf{L}^{+}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}^{\top}{\mathbf{U}})}{\operatorname{tr}({\mathbf{U}}^{\top}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}\mathbf{L}^{-}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}^{\top}{\mathbf{U}})},$
(23)

Once $\mathbf{Z}$, $\mathbf{D}$ and $\mathbf{U}$ are computed, the common
metric, such as Euclidean distance, can be used for finding similar patients
in low-dimensional embedded space, via sequentially performing Eq. (5) and Eq.
(10).

##  4 EXPERIMENT

In this section, we investigate the performance of proposed methods on two
real EHR datasets.

###  4.1 Experimental Settings

For unsupervised learning experiments, we employ the K-SVD algorithm [41] to
compute an empirically optimal data-driven dictionary, and initialize _SparGE_
algorithms. For supervised learning experiments, we adopt the same approach to
generate a sub-dictionary for each class, and then concatenate all sub-
dictionaries to form a common dictionary.

With the given dictionary $\mathbf{D}^{(0)}\in\mathcal{D}$ initialized, the
original orthogonal projection $\mathbf{U}^{(0)}\in\mathcal{U}$ can be
directly obtained by applying classic TQ maximization algorithms on the sparse
representations of the samples with respect to $\mathbf{D}^{(0)}$. Apparently,
when the number of training samples is huge, it is unnecessary and impractical
to perform a TQ maximization for initialization. Thus we employ only a subset
of random samples to compute the initial orthogonal projection
$\mathbf{U}^{(0)}$.

More concretely, in all experiments, we set $\gamma=10^{-3}$ and $\zeta=0.1$
by hand in Eq. (LABEL:eq_trace_quotient_dictLearn) and Eq. (17), the
parameters for $\lambda_{1},\lambda_{2}$ in Eq.
(LABEL:eq_trace_quotient_dictLearn) could be well tuned via performing cross
validation.

Specially, for datasets without a pre-construction of training set and testing
set, all experiments are repeated ten times with different randomly
constructed training set and test set, and the average of per-class
recognition rates is recorded for each run. Besides, considering that each
kind of data has different measurement units, all columns are presented as
$m$-dimensional vectors, and normalized to have unit norm, to avoid the errors
caused by different physical units.

###  4.2 Singapore SingHEART Dataset

The Singapore SingHEART dataset[42] is a private dataset that contains $683$
male and female subjects carrying $467$ biomarkers from $7$ groups, with ages
between $21$–$69$ years old, between $2015$ and $2017$.

In our experiments, after preprocessing data by merging synonyms and
repetitive biomarkers, the total number of clinical features changes from a
total of $457$ symptoms to $383$ after data preprocessing by merging synonyms
and repetitive biomarkers, and excluding subjects who lose more than $10\%$
data of their data. However, our dataset still with a lot of incomplete data,
we calculate metrics for each label, and find their average weights by
supporting the number of true instances for each label, the missing data are
replaced by the weighted mean of their $10$ nearby measurements in each
column. Note that the data are collected from multiple and heterogeneous
sources, varying from digital numbers to texts. Thereby, as part of the data
preprocessing, we encode all kinds of data into digital form. Some examples of
data integer encoding results are shown in Table 1.

Table 1:  Integer Encoding examples for some multi-source _SingHEART_ biomarkers.  | Biomarker
---
| Digital encoding
---
| Country of birth
---
“Singaporean” $=1$, “Others” $=2$
| Marital Status
---
“Single” $=1$, “Married” $=2$, “Widowed” $=3$
| Religion
---
| “Christian/Catholic” $=1$, “Free thinker” $=2$, “Buddhist” $=3$,
---
“Islam” $=4$, “Hindu” $=5$, “Taoist” $=6$,“Others” $=7$
|  | Diabetes, Hypertension,
---
Heart Attack Block, Heart Disease,
Hyperlipidemia, $\cdots$
“Unknown” $=0$, “Yes” $=1$, “No” $=2$
| Smoking, Cigarettes
---
“Yes” $=1$, “No” $=2$, “Previously” $=3$
| Home/Work Smoke
---
“Never” $=1$, “Sometimes” $=2$, “Most of the times” $=3$, “Never” $=4$
| Alcohol, Beer, Red/White Wine
---
“Yes” $=1$, “No” $=2$
| Coffee/Tea Weekly
---
| “Never/rarely” $=1$, “$<1$ cup a week” $=2$,
---
“$>=1$ cup a week but $<=1$ cup a day” $=3$, “Others” $=4$

###  4.3 MIMIC-III Dataset

MIMIC-III (Medical Information Mart for Intensive Care) [43] is a large public
database comprised of information of patients in critical care units at a
large tertiary care hospital. The dataset is used to evaluate proposed method
for large-scale time series data, associated with $53,423$ distinct hospital
admissions for adult patients (aged $16$ years or above) admitted to critical
care units between $2001$ and $2012$.

The task of experiments on MIMIC-III is also to predict patient mortality,
according to patient similarity. The challenges are in two aspects: i) more
than $30\%$ missing values and ii) the temporal structure of the data. In the
experiments, only a subset of the MIMIC-III dataset is compiled. We picked
about $21,142$ samples, and the first $70$ time steps of all samples that are
in 48 hours. By using the one hot coding to the raw $17$ dimensional features,
we get the $48\times 76$ for each patient. Finally, this feature matrix are
reshaped as a fixed length vector to feed the machine learning algorithms.

Table 2:  Baseline classifiers. ’KNN’ |  $k-$Nearest Neighbor
---|---
’LR’ | Logistic Regression
’RF’ | Random Forest
’DT’ | Decision Tree
’SVM’ | Support Vector Machines
’GBDT’ | Gradient Boosting Decision Tree

###  4.4 Results

Figure 1:  This figure shows the comparison between applying Baseline
classifiers on raw SingHEART data and on their representations achieved by
SparGE Figure 2:  Comparing the results on selected $14$ features from
SingHEART dataset

This section shows the experimental results on both datasets. By applying the
classifiers, shown in Table 2, on raw SingHEART data, we obtain the baseline
results. For comparison, we then apply the classifiers on low-dimensional
representations that are achieved by _SparGE_. Figure 1 and Figure 2 compare
the their results with same experimental settings. The results indicate that
our proposed _SparGE_ exactly improves the performance on both the accuracy
and the recall rate. With $14$ selected features from raw dataset, the
experiments results are shown in Figure 2 , the _SparGE_ still achieves better
performance.

Experimental results on MIMIC-III are collated in Figure 3 and Table 3. The
proposed _SparGE_ also show the promising advantages in comparison with
baselines. Table 3 shows applying the classifiers on representations achieved
by _SparGE_ has less computation time.

Table 3:  Mean time(s) on classifying raw data and the representations achieved by _SparGE_ |  SparGE (s) |  raw data (s)
---|---|---
KNN | 0.01627 | 0.056865
LR | 0.018702 | 0.160339
RF | 0.037244 | 0.094995
DT | 0.028631 | 0.257378
SVM | 0.373386 | 1.789594
GBDT | 5.37456 | 11.09086
Figure 3:  Comparing the results on selected $17$ fea-tures from MIMIC-III
dataset

##  5 CONCLUSION

In this work, we presented a joint end-to-end discrimination learning
approach, called _SparGE_ , in order to find and weight similar patients from
multi-class EHR data with noise corruption. At first, sparsity is utilized
with low-rank tools to exploit the sparse nature of EHR data with huge amount
of missing value. Then, in order to extract the local similarity from learned
sparse coefficients, a graph embedding based dimension reduction is applied in
sparse domain. Finally, explicit measurements are constructed in embedded low-
dimensional representations. By using the differentiability of sparse
regression solutions, the _SparGE_ could be efficiently solved by a proposed
gradient descent algorithm. The experimental results show stronger competitive
performance of the proposed _SparGE_ , in comparison with other machine
learning approaches. Moreover, the proposed _SparGE_ is flexible and can be
extended to deeper architectures, applying in more general cases of
dimensionality reduction.

## References

  * [1] Ping Zhang, Fei Wang, Jianying Hu, and Robert Sorrentino,  “Towards personalized medicine: leveraging patient similarity and drug similarity analytics,”  AMIA Summits on Translational Science Proceedings, vol. 2014, pp. 132, 2014.
  * [2] Joon Lee, David M Maslove, and Joel A.PLoS One Dubin,  “Personalized mortality prediction driven by electronic medical data and a patient similarity metric,”  PLoS One, vol. 10, no. 5, pp. e0127428, 2015.
  * [3] Anis Sharafoddini, Joel A Dubin, and Joon Lee,  “Patient similarity in prediction models based on health data: a scoping review,”  JMIR medical informatics, vol. 5, no. 1, pp. e7, 2017.
  * [4] Shahram Ebadollahi, Jimeng Sun, David Gotz, Jianying Hu, Daby Sow, and Chalapathy Neti,  “Predicting patient’s trajectory of physiological data using temporal trends in similar patients: a system for near-term prognostics,”  in AMIA annual symposium proceedings. American Medical Informatics Association, 2010, vol. 2010, p. 192.
  * [5] Chao Che, Cao Xiao, Jian Liang, Bo Jin, Jiayu Zho, and Fei Wang,  “An rnn architecture with dynamic temporal matching for personalized predictions of parkinson’s disease,”  in Proceedings of the 2017 SIAM International Conference on Data Mining. SIAM, 2017, pp. 198–206.
  * [6] Assaf Gottlieb, Gideon Y Stein, Eytan Ruppin, Russ B Altman, and Roded Sharan,  “A method for inferring medical diagnoses from patient similarities,”  BMC medicine, vol. 11, no. 1, pp. 1–10, 2013.
  * [7] Zheng Jia, Xian Zeng, Huilong Duan, Xudong Lu, and Haomin Li,  “A patient-similarity-based model for diagnostic prediction,”  International Journal of Medical Informatics, vol. 135, pp. 104073, 2020.
  * [8] LWC Chan, T Chan, LF Cheng, and WS Mak,  “Machine learning of patient similarity: A case study on predicting survival in cancer patient after locoregional chemotherapy,”  in IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW). IEEE, 2010, pp. 467–470.
  * [9] Enea Parimbelli, Simone Marini, Lucia Sacchi, and Riccardo Bellazzi,  “Patient similarity for precision medicine: A systematic review,”  Journal of biomedical informatics, vol. 83, pp. 87–96, 2018.
  * [10] Fei Wang,  “Semisupervised metric learning by maximizing constraint margin,”  IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 41, no. 4, pp. 931–939, 2011.
  * [11] Jimeng Sun, Daby Sow, Jianying Hu, and Shahram Ebadollahi,  “Localized supervised metric learning on temporal physiological data,”  in 20th International Conference on Pattern Recognition, 2010, pp. 4149–4152.
  * [12] Jimeng Sun, Fei Wang, Jianying Hu, and Shahram Edabollahi,  “Supervised patient similarity measure of heterogeneous patient records,”  Acm Sigkdd Explorations Newsletter, vol. 14, no. 1, pp. 16–24, 2012\.
  * [13] Fei Wang, Jimeng Sun, Jianying Hu, and Shahram Ebadollahi,  “imet: interactive metric learning in healthcare applications,”  in Proceedings of the 2011 SIAM International Conference on Data Mining. SIAM, 2011, pp. 944–955.
  * [14] Fei Wang, Jianying Hu, and Jimeng Sun,  “Medical prognosis based on patient similarity and expert feedback,”  in Proceedings of the 21st International Conference on Pattern Recognition (ICPR2012). IEEE, 2012, pp. 1799–1802.
  * [15] Fei Wang and Jimeng Sun,  “Psf: A unified patient similarity evaluation framework through metric learning with weak supervision,”  IEEE Journal of Biomedical and Health Informatics, vol. 19, no. 3, pp. 1053–1060, 2015.
  * [16] Riccardo Miotto, Li Li, Brian A Kidd, and Joel T Dudley,  “Deep patient: an unsupervised representation to predict the future of patients from the electronic health records,”  Scientific reports, vol. 6, no. 1, pp. 1–10, 2016.
  * [17] Shraddha Pai and Gary D Bader,  “Patient similarity networks for precision medicine,”  Journal of molecular biology, vol. 430, no. 18, pp. 2924–2938, 2018\.
  * [18] Zihao Zhu, Changchang Yin, Buyue Qian, Yu Cheng, Jishang Wei, and Fei Wang,  “Measuring patient similarities via a deep architecture with medical concept embedding,”  in IEEE 16th International Conference on Data Mining (ICDM). IEEE, 2016, pp. 749–758.
  * [19] Shraddha Pai, Shirley Hui, Ruth Isserlin, Muhammad A Shah, Hussam Kaka, and Gary D Bader,  “netdx: interpretable patient classification using integrated patient similarity networks,”  Molecular Systems Biology, vol. 15, no. 3, pp. e8497, 2019.
  * [20] Qiuling Suo, Weida Zhong, Fenglong Ma, Yuan Ye, Mengdi Huai, and Aidong Zhang,  “Multi-task sparse metric learning for monitoring patient similarity progression,”  in IEEE International Conference on Data Mining (ICDM). IEEE, 2018, pp. 477–486.
  * [21] Mengting Zhan, Shilei Cao, Buyue Qian, Shiyu Chang, and Jishang Wei,  “Low-rank sparse feature selection for patient similarity learning,”  in IEEE 16th International Conference on Data Mining (ICDM). IEEE, 2016, pp. 1335–1340.
  * [22] Jiayu Zhou, Jun Liu, Vaibhav A Narayan, and Jieping Ye,  “Modeling disease progression via fused sparse group lasso,”  in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 1095–1103.
  * [23] Yuqi Si, Jingcheng Du, Zhao Li, Xiaoqian Jiang, Timothy Miller, Fei Wang, W Jim Zheng, and Kirk Roberts,  “Deep representation learning of patient data from electronic health records (ehr): A systematic review,”  arXiv e-prints, pp. arXiv–2010, 2020.
  * [24] Jimeng Sun, Daby Sow, Jianying Hu, and Shahram Ebadollahi,  “A system for mining temporal physiological data streams for advanced prognostic decision support,”  in IEEE International Conference on Data Mining (ICDM). IEEE, 2010, pp. 1061–1066.
  * [25] Subhagata Chattopadhyay, P Ray, HS Chen, MB Lee, and HC Chiang,  “Suicidal risk evaluation using a similarity-based classifier,”  in International Conference on Advanced Data Mining and Applications. Springer, 2008, pp. 51–61.
  * [26] Elad Hazan, Roi Livni, and Yishay Mansour,  “Classification with low rank and missing data.,”  in Proceedings of the Twenty-Fifth International Conference (ICML), 2015, pp. 257–266.
  * [27] Aude Sportisse, Claire Boyer, and Julie Josse,  “Imputation and low-rank estimation with missing not at random data,”  Statistics and Computing, vol. 30, no. 6, pp. 1629–1643, 2020.
  * [28] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright,  “Robust principal component analysis?,”  Journal of the ACM (JACM), vol. 58, no. 3, pp. 1–37, 2011.
  * [29] Xiao Peng Li, Lei Huang, Hing Cheung So, and Bo Zhao,  “A survey on matrix completion: perspective of signal processing,”  arXiv preprint arXiv:1901.10885, 2019.
  * [30] John Wright, Allen Y Yang, Arvind Ganesh, S Shankar Sastry, and Yi Ma,  “Robust face recognition via sparse representation,”  IEEE transactions on pattern analysis and machine intelligence, vol. 31, no. 2, pp. 210–227, 2009.
  * [31] Junbin Gao, Qinfeng Shi, and Tibério S Caetano,  “Dimensionality reduction via compressive sensing,”  Pattern Recognition Letters, vol. 33, no. 9, pp. 1163–1170, 2012\.
  * [32] Ehsan Elhamifar and Rene Vidal,  “Sparse subspace clustering: Algorithm, theory, and applications,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 11, pp. 2765–2781, 2013.
  * [33] Xian Wei, Hao Shen, and Martin Kleinsteuber,  “Trace quotient with sparsity priors for learning low dimensional image representations,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1–1, 2020.
  * [34] Francis R. Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski,  “Structured sparsity through convex optimization,”  Statistical Science, vol. 27, no. 4, pp. 450–468, 2012.
  * [35] Xian Wei,  Learning Image and Video Representations Based on Sparsity Priors,  Shaker Verlag GmbH, Aachen, Germany, 2017.
  * [36] Julien Mairal, Francis Bach, and Jean Ponce,  “Task-driven dictionary learning,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 4, pp. 791–804, 2012.
  * [37] Xian Wei, Hao Shen, and Martin Kleinsteuber,  “Trace quotient meets sparsity: A method for learning low dimensional image representations,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016, pp. 5268–5277.
  * [38] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein,  “Distributed optimization and statistical learning via the alternating direction method of multipliers,”  Machine Learning, vol. 3, no. 1, pp. 1–122, 2010.
  * [39] Jian-Feng Cai, Emmanuel J Candès, and Zuowei Shen,  “A singular value thresholding algorithm for matrix completion,”  SIAM Journal on Optimization, vol. 20, no. 4, pp. 1956–1982, 2010\.
  * [40] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo,  “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,”  SIAM review, vol. 52, no. 3, pp. 471–501, 2010.
  * [41] Michal Aharon, Michael Elad, and Alfred Bruckstein,  “K-SVD: Design of dictionaries for sparse representation,”  Proceedings of SPARS, vol. 5, pp. 9–12, 2005.
  * [42] Jonathan Yap, Weng Khong Lim, Anders Sahlén, Calvin Woon-Loong Chin, Kenneth Michael Yun-Chi Chew, Sonia Davila, John Allen, Vera Goh, Swee Yaw Tan, Patrick Tan, et al.,  “Harnessing technology and molecular analysis to understand the development of cardiovascular diseases in asia: a prospective cohort study (singheart),”  BMC cardiovascular disorders, vol. 19, no. 1, pp. 259, 2019.
  * [43] Hrayr Harutyunyan, Hrant Khachatrian, David C Kale, Greg Ver Steeg, and Aram Galstyan,  “Multitask learning and benchmarking with clinical time series data,”  Scientific data, vol. 6, no. 1, pp. 1–18, 2019.

SparGE: Sparse Coding-based Patient Similarity Learning via Low-rank
Constraints and Graph Embedding:
Supplementary Materials

##  Appendix A THE FIRST-ORDER DERIVATIVE OF COST FUNCTION

Let
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}]\in\mathbb{R}^{m\times
n}$ be a collection of $n$ patients’ raw EHR data points, potentially with
excessive noises, and let the vector
$\mathbf{x}_{i}=[\mathbf{x}_{i}^{1},\mathbf{x}_{i}^{2},\cdots,\mathbf{x}_{i}^{m}]\in\mathbb{R}^{m}$
contain all measurable EHR variables for the $i^{\text{th}}$ patient, with $m$
being the number of all biomarkers.
$\mathbf{Z}:=[\mathbf{z}_{1},\ldots,\mathbf{z}_{n}]\in\mathbb{R}^{m\times n}$
is the low-rank approximated matrix of $\mathbf{X}$. We donate by
$\mathbf{D}:=[\mathbf{d}_{1},\ldots,\mathbf{d}_{k}]\in\mathbb{R}^{m\times k}$
a shared dictionary and $\mathbf{Z}=\mathbf{D}\bm{\Phi}$ with
$\bm{\Phi}:=[\bm{\phi}_{1},\ldots,\bm{\phi}_{n}]\in\mathbb{R}^{k\times n}$.

For each given sample $\mathbf{z},$ we denote by $\phi^{*}$ the sparse
representation with respect to a dictionary $\mathbf{D}^{*}$, we have the
unique solution of the sample-wise sparse regression problem as in Eq. (24),

$\begin{split}f_{\mathbf{x}}(\bm{\phi},\mathbf{Z}):=\tfrac{1}{2}\|\mathbf{z}-\mathbf{D}\bm{\phi}\|_{2}^{2}+g(\bm{\phi})+\lambda_{1}\|\mathbf{Z}_{\Omega}-\mathbf{X}_{\Omega}\|_{F}^{2},\;\text{with}\;g(\bm{\phi})=r_{1}\|\phi\|_{1}+\frac{r_{2}}{2}\|\phi\|_{F}^{2},\end{split}$

$\bm{\phi}_{\mathbf{D}}(\mathbf{x},\mathbf{z}):=\operatorname*{argmin}_{\bm{\phi}\in\mathbb{R}^{k}}f_{\mathbf{x}}(\bm{\phi},\mathbf{Z}).$
(24)

where $r1$ and $r2$ are the regularization parameters.

Fix $\mathbf{D}$, the solution of $\bm{\phi}^{*}$ and the derivative of
$\bm{\phi}^{*}$ to $\mathbf{D}$ are computed by

$\begin{split}\frac{\partial
f}{\partial\bm{\phi}}=0:\bm{\phi}^{*}&=\mathop{\arg\min}_{\phi\in\mathbb{R}^{k}}\frac{1}{2}\|\mathbf{z}-\mathbf{D}\bm{\phi}\|_{2}^{2}+r_{1}\|\phi\|_{1}+\frac{r_{2}}{2}\|\phi\|_{F}^{2}\\\
&=(\mathbf{D}^{\top}\mathbf{D}+r_{2}\mathbf{I})^{-1}(\mathbf{D}^{\top}\mathbf{z}-r_{1}s_{\Lambda})\end{split}$
(25)

$\begin{split}\frac{\partial\phi^{*}}{\partial\mathbf{D}}=&-\mathbf{D}(\mathbf{D}^{\top}\mathbf{D}+r_{2}\mathbf{I})^{-1}(\mathbf{D}^{\top}\mathbf{z}-\lambda_{1}s_{\Lambda})(\mathbf{D}^{\top}\mathbf{D}+r_{2}\mathbf{I})^{-1}\\\
&-\mathbf{D}(\mathbf{D}^{\top}\mathbf{D}+r_{2}\mathbf{I})^{-1}(\mathbf{D}^{\top}\mathbf{z}-\lambda_{1}s_{\Lambda})^{\top}(\mathbf{D}^{\top}\mathbf{D}+r_{2}\mathbf{I})^{-1}+\mathbf{z}(\mathbf{D}^{\top}\mathbf{D}+r_{2}\mathbf{I})^{-1}\end{split}$
(26)

In order to explicitly measure the similarity of patient pairs, we already
know the generalized Mahalanobis distance between $\phi_{i}$ and $\phi_{j}$ in
sparse domain could be obtained by computing the Euclidean distance in
$\mathbb{R}^{l}$ as follows:

$\begin{split}d^{2}(\bm{\phi}_{i},\bm{\phi}_{j})&=(\bm{\phi}_{i}-\bm{\phi}_{j})^{\top}\mathbf{P}(\bm{\phi}_{i}-\bm{\phi}_{j})\\\
&=(\mathbf{U}^{\top}\bm{\phi}_{i}-\mathbf{U}^{\top}\bm{\phi}_{j})^{\top}(\mathbf{U}^{\top}\bm{\phi}_{i}-\mathbf{U}^{\top}\bm{\phi}_{j})\\\
&=d^{2}(\mathbf{y}_{i},\mathbf{y}_{j})\end{split}$ (27)

where $\mathbf{U}\in\mathbb{R}^{m\times l}$ is an dimension reduction
transformation with $l\ll m$, $\mathbf{y}_{i}\in\mathbb{R}^{l}$ is a
representation in the low-dimensional embedded space. Since ${\mathbf{P}}$ is
a Symmetric Positive Semi-Definite(SPSD) matrix, $\mathbf{U}$ could be viewed
as a component for approximating ${\mathbf{P}}=\mathbf{U}\mathbf{U}^{\top}$.
Now, the key is to learn an approximate $\mathbf{U}$, as follows.

Let $\mathfrak{N}_{k_{1}}^{+}({\bm{\phi}}_{i})$ denote the set of $k_{1}$
nearest neighbors which share the same label with ${\bm{\phi}}_{i}$, and
$\mathfrak{N}_{k_{2}}^{-}({\bm{\phi}}_{i})$ denote the set of $k_{2}$ nearest
neighbors among the data points whose labels are different to that of
${\bm{\phi}}_{i}$. We construct two matrices
$\mathbf{Z}^{+}:=\\{z_{ij}^{+}\\}\in\mathbb{R}^{n\times n}$ and
$\mathbf{Z}^{-}:=\\{z_{ij}^{-}\\}\in\mathbb{R}^{n\times n}$ with

$z_{ij}^{+}=\left\\{\\!\\!\begin{array}[]{ll}d(\phi_{i},\phi_{j}),&{\bm{\phi}}_{j}\in\mathfrak{N}_{k_{1}}^{+}({\bm{\phi}}_{i})~{}\text{or}~{}{\bm{\phi}}_{i}\in\mathfrak{N}_{k_{1}}^{+}({\bm{\phi}}_{j}),\\\
0,&\text{otherwise},\end{array}\right.$ (28)

$z_{ij}^{-}=\left\\{\\!\\!\begin{array}[]{ll}d(\phi_{i},\phi_{j}),&{\bm{\phi}}_{j}\in\mathfrak{N}_{k_{1}}^{-}({\bm{\phi}}_{i})~{}\text{or}~{}{\bm{\phi}}_{i}\in\mathfrak{N}_{k_{1}}^{-}({\bm{\phi}}_{j}),\\\
0,&\text{otherwise}.\end{array}\right.$ (29)

$y^{+}_{ii}=\sum_{j\neq i}z_{ij}^{+},\quad\text{and}\quad
y^{-}_{ii}=\sum_{j\neq i}z_{ij}^{-},$ (30)

Then, we have intra-class locality $\mathbf{L}^{+}$ and inter-class locality
$\mathbf{L}^{-}$:

$\mathbf{L}^{+}=\mathbf{Y}^{+}-\mathbf{Z}^{+},\quad\text{and}\quad\mathbf{L}^{+}=\mathbf{Y}^{-}-\mathbf{Z}^{-}.$
(31)

The final jointly cost function for our generic algorithmic framework can be
formulated as a problem of the so-called trace quotient, i.e.,

$\operatorname*{\operatorname*{argmin}}_{\mathbf{U},\mathbf{Z},\mathbf{D}}\;\mathcal{L}_{(\mathbf{P},\mathbf{Z},\mathbf{D})}.$
(32)

with

$\mathcal{L}_{(\mathbf{U},\mathbf{Z},\mathbf{D})}:=\frac{\operatorname{tr}(\mathbf{U}^{\top}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}\mathbf{L}^{+}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}^{\top}\mathbf{U})}{\operatorname{tr}(\mathbf{U}^{\top}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}\mathbf{L}^{-}{\bm{\Phi}_{\mathbf{X}}(\mathbf{Z},\mathbf{D})}^{\top}\mathbf{U})},$
(33)

The derivatives of $\mathcal{L}_{(\mathbf{U},\mathbf{Z},\mathbf{D})}$ with
respect to $\mathbf{P}$ and $\mathbf{D}$ are computed as

$\begin{split}\frac{\partial\mathcal{L}}{\partial\mathbf{U}}=2[\frac{\bm{\Phi}\mathbf{L}^{+}\bm{\Phi}^{T}\mathbf{U}+\bm{\Phi}^{\top}\mathbf{U}\mathbf{U}^{\top}\bm{\Phi}\frac{\partial\mathbf{L}^{+}}{\partial\mathbf{U}}}{\operatorname{tr}(\mathbf{U}^{\top}\bm{\Phi}_{\mathbf{X}}\mathbf{L}^{-}\bm{\Phi}^{\top}\mathbf{U})}-&\frac{(\bm{\Phi}\mathbf{L}^{-}\bm{\Phi}^{T}\mathbf{U}+\bm{\Phi}^{\top}\mathbf{U}\mathbf{U}^{\top}\bm{\Phi}\frac{\partial\mathbf{L}^{-}}{\partial\mathbf{U}})\operatorname{tr}(\mathbf{U}^{\top}\bm{\Phi}\mathbf{L}^{+}\bm{\Phi}^{\top}\mathbf{U})}{\operatorname{tr}^{2}(\mathbf{U}^{\top}\bm{\Phi}_{\mathbf{X}}\mathbf{L}^{-}\bm{\Phi}^{\top}\mathbf{U})}],\end{split}$
(34)

$\begin{split}\frac{\partial\mathcal{L}}{\partial\mathbf{D}}=\frac{\partial\mathcal{L}}{\partial\bm{\Phi}}\frac{\partial\bm{\Phi}}{\partial\mathbf{D}}=2[\frac{\mathbf{U}\mathbf{U}^{\top}\bm{\Phi}(\mathbf{L}^{+})^{\top}}{\operatorname{tr}(\mathbf{U}^{\top}\bm{\Phi}_{\mathbf{X}}\mathbf{L}^{-}\bm{\Phi}^{\top}\mathbf{U})}-\frac{\mathbf{U}\mathbf{U}^{\top}\bm{\Phi}(\mathbf{L}^{-})^{\top}\operatorname{tr}(\mathbf{U}^{\top}\bm{\Phi}_{\mathbf{X}}\mathbf{L}^{+}\bm{\Phi}^{\top}\mathbf{U})}{\operatorname{tr}^{2}(\mathbf{U}^{\top}\bm{\Phi}_{\mathbf{X}}\mathbf{L}^{-}\bm{\Phi}^{\top}\mathbf{U})}]\frac{\partial\bm{\Phi}}{\partial\mathbf{D}}.\end{split}$
(35)

Therein, $\frac{\partial\mathbf{L}^{+}}{\partial\mathbf{U}}$ is computed by

$\frac{\partial\mathbf{L}^{+}}{\partial\mathbf{U}}=\sum^{n}_{i,j=1}\left\\{\\!\\!\begin{array}[]{ll}\frac{\partial
L_{ij}^{+}}{\partial\mathbf{U}},&{L_{ij}^{+}}\neq 0,\\\
0,&\text{otherwise},\end{array}\right.$ (36) $\frac{\partial
L_{ij}^{+}}{\partial\mathbf{U}}=\left\\{\\!\\!\begin{array}[]{ll}-\frac{\partial\mathbf{z}_{ij}^{+}}{\partial\mathbf{U}},&i\neq
j,\\\
\sum_{t=1}^{n}\frac{\partial\mathbf{z}_{it}^{+}}{\partial\mathbf{U}}.&i=j\end{array}\right.$
(37)

$\frac{\partial\mathbf{z}_{ij}^{+}}{\partial\mathbf{U}}=2(\bm{\phi}_{i}-\bm{\phi}_{j})^{\top}(\bm{\phi}_{i}-\bm{\phi}_{j})\mathbf{U}$
(38)

with

$\begin{split}\frac{\partial\bm{\Phi}}{\partial\mathbf{D}}=\sum^{n}_{i=1}\frac{\partial\bm{\phi}_{i}}{\partial\mathbf{D}}\end{split}$
(39)

where $\frac{\partial\bm{\phi}_{i}}{\partial\mathbf{D}}$ is computed by Eq.
(26). The similar computation is for
$\frac{\partial\mathbf{L}^{-}}{\partial\mathbf{U}}$.

With $\frac{\partial\mathcal{L}}{\partial\mathbf{D}}$,
$\frac{\partial\mathcal{L}}{\partial\mathbf{U}}$ at hand, the updates for
$\mathbf{D}$ and $\mathbf{U}$ are described in Algorithm $1$, where the
projections from ${\hat{\mathbf{D}}}^{(j+1)},{\hat{\mathbf{U}}}^{(j+1)}$ onto
${{\mathbf{D}}}^{(j+1)}\in\mathcal{D},{{\mathbf{U}}}^{(j+1)}\in\mathcal{U}$
are computed by the unit normalization and the QR decomposition, respectively.

##  Appendix B EXPERIMENTS

In the experiments, we set $70\%$ as training data, and $30\%$ as testing
data. The following charts are supplementary to the two datasets used in the
experiments.

###  B.1 SingHeart Dataset

Table 4 shows biomarkers in _SingHEART_ dataset and the number of
corresponding variables.

Table 4:  _SingHEART_ biomarkers from Singapore Health Services, SingHealth, with multi-source sensors [42] Measurement method | Number of variables
---|---
Calcium Score | 7
APB Biofourmis | 101
Lab Tests | 35
MRI Features | 29
Proforma | 88
General Questionnaire | 189
Lifestyle Questionnaire | 18

###  B.2 MIMIC-III Dataset

Considering the large size of MIMIC-III dataset, after selecting samples, 17
features are selected from them. The first column of Table 5 shows the $17$
features corresponding to clinical variables. In Table 5, the source tables of
a variable from MIMIC-III database are shown in the second column. There are
two main source tables, ’chartevents’ and ’Labevents’. The third column lists
the “normal” values we used in our baselines during the imputation step, and
the fourth column describes how baselines and our models treat the variables.

Table 5: The $17$ selected clinical variables. The second column shows the source table(s) of a variable from MIMIC-III database. The third column lists the “normal” values we used in our baselines during the imputation step, and the fourth column describes how models treat the variables. Variables | MIMIC-III table | Impute value | Modeled as
---|---|---|---
Capillary refill rate | chartevents | 0.0 | categorical
Diastolic blood pressure | chartevents | 59.0 | continuous
Fraction inspired oxygen | chartevents | 0.21 | continuous
Glasgow coma scale eye opening | chartevents | 4 spontaneously | categorical
Glasgow coma scale motor response | chartevents | 6 obeys commands | categorical
Glasgow coma scale total | chartevents | 15 | categorical
Glasgow coma scale verbal response | chartevents | 5 oriented | categorical
Glucose | chartevents, Labevents | 128.0 | continuous
Heart Rate | chartevents | 86 | continuous
Height Rate | chartevents | 170.0 | continuous
Mean blood pressure | chartevents | 77.0 | continuous
Oxygen saturation | chartevents, Labevents | 98.0 | continuous
Respiratory rate | chartevents | 19 | continuous
Systolic blood pressure | chartevents | 118.0 | continuous
Temperature | chartevents | 36.6 | continuous
Weight | chartevents | 81.0 | continuous
PH | chartevents, Labevents | 7.4 | continuous

The value of $17$ channels are given including e.g., normal values which
provides a normal standard, and $5$ categorical channels, which are capillary
refill rate, glasgow coma scale eye opening, glasgow coma scale motor
response, glasgow coma scale total and glasgow coma scale verbal response.

For glasgow coma scale eye opening, we divide it into 4 grades according to
medical standards. Respectively, 4 points means patients can open their eyes
spontaneously. 3 points means the patient can open his eyes when called. 2
points means the patient can open his eyes when pained. 1 point means the
patient has no response.

We divide glasgow coma scale motor response into 6 grades according to medical
standards. Respectively, 6 points means that the patient can obey commands to
make a motor response, which demonstrates the patient is a normal person. 5
points indicate that stimulation of the patient can localize pain. 4 points
means the patient has flex withdraws. 3 points means the patient has abnormal
flexion. 2 points means the patient has abnormal extension. 1 point means the
patient has no response.

As for glasgow coma scale verbal response, we divide it into 6 grades
according to medical standards. Respectively, 5 points indicates that the
patient is organized. 4 points means the patient is confused. 3 points means
that the patient speaks inappropriate words. 2 points means the patient can
only make incomplete sounds. 1 point means the patient has no response.