# Seq-HyGAN: Sequence Classification via Hypergraph Attention Network

Khaled Mohammed Saifuddin  Georgia State UniversityDowntownAtlantaGeorgia30302
<EMAIL_ADDRESS>,  Corey May  Arkansas Tech University
DowntownRussellvilleArkansas72801<EMAIL_ADDRESS>,  Farhan Tanvir  Oklahoma
State UniversityDowntownStillwaterOklahoma74078<EMAIL_ADDRESS>,
Muhammad Ifte Khairul Islam  Georgia State
UniversityDowntownAtlantaGeorgia30302<EMAIL_ADDRESS>and  Esra Akbas
Georgia State UniversityDowntownAtlantaGeorgia30302<EMAIL_ADDRESS>
###### Abstract.

Sequence classification has a wide range of real-world applications in
different domains, such as genome classification in health and anomaly
detection in business. However, the lack of explicit features in sequence data
makes it difficult for machine learning models. While Neural Network (NN)
models address this with learning features automatically, they are limited to
capturing adjacent structural connections and ignore global, higher-order
information between the sequences. To address these challenges in the sequence
classification problems, we propose a novel Hypergraph Attention Network
model, namely Seq-HyGAN. To capture the complex structural similarity between
sequence data, we first create a hypergraph where the sequences are depicted
as hyperedges and subsequences extracted from sequences are depicted as nodes.
Additionally, we introduce an attention-based Hypergraph Neural Network model
that utilizes a two-level attention mechanism. This model generates a sequence
representation as a hyperedge while simultaneously learning the crucial
subsequences for each sequence. We conduct extensive experiments on four data
sets to assess and compare our model with several state-of-the-art methods.
Experimental results demonstrate that our proposed Seq-HyGAN model can
effectively classify sequence data and significantly outperform the baselines.
We also conduct case studies to investigate the contribution of each module in
Seq-HyGAN.

PVLDB Reference Format:
PVLDB, 16(2): XXX-XXX, 2023.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 16, No. 2 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
https://github.com/khaledmohammedsaifuddin/Seq-HyGAN.

##  1\. Introduction

Sequence data is ubiquitous; it often occurs in biomedical, security, chemical
structure, business, and other miscellaneous domains. A sequence is an ordered
list of events. The sequence can either be defined from numbers as time-series
data, or as a finite list of symbols. For example, a DNA sequence consists of
four types of amino acids A, C, G, T, and these amino acids pose in a
particular order to create a meaningful DNA sequence such as ACCCCCGT. In this
paper, we focus on symbolic sequence data. Extracting characteristics from
sequence data and designing effective similarity measures between sequences is
crucial for sequence data mining tasks including sequence classification.
Sequence classification is the problem of predicting the class of unlabeled
sequences by exploiting the information from labeled sequences. It has
enormous applications such as genomics data classification and its function
prediction, anomaly detection, music chord recognition, cancer detection,
virus-host prediction, etc.

Different machine learning (ML) models have been employed to classify sequence
data. The performance of ML classifiers primarily depends on selecting the
best features. However, there is no explicit feature in sequence data, so
designing an effective ML model for sequence classification is still
challenging. Moreover, the potential features could be failed to express the
sequence data in low dimension space and, therefore, computationally expensive
(XingZhengzheng et al., 2010). The use of neural networks (NN), such as
convolutional neural networks (CNN), recurrent neural networks (RNN) (i.e.,
LSTM, GRU), etc., is also pretty common in this domain. NNs are very promising
in capturing the adjacent structural information but mostly ignore the non-
adjacent information. In addition, high-order, complex relationships among the
sequence data could not be captured using NNs. Furthermore, training NN-based
models demand the availability of large amounts of label data.

A graph is a highly sophisticated data structure that can effectively capture
local and global non-adjacent information from the data (Qian, 2019; Islam et
al., 2021). The graph data structure has been explored in versatile research
domains such as anomaly detection (Akoglu et al., 2015), recommendation
learning (Chang et al., [n.d.]), community detection (Akbas and Zhao, 2017;
Akbas, 2019) etc. Recently, it has also been explored for different types of
sequence data classification tasks such as text classification (Yao et al.,
[n.d.]), DNA-protein binding prediction (Guo et al., [n.d.]), protein function
prediction (Gligorijević et al., 2021), drug-drug interaction prediction
(Tanvir et al., 2022; Bumgardner et al., 2022), etc. The state-of-the-art
sequence-to-graph models can be categorized into similarity-based and order-
based graphs (Compeau et al., 2011; Atkinson et al., 2009; Zola, 2014). In
similarity-based graphs, sequences are represented as nodes, and they are
connected by edges based on their similarity. On the other hand, order-based
graphs decompose sequential data into consecutive subsequences, consider
unique subsequences as the graph’s vertices, and add edges between consecutive
vertices, which results in one graph for each sequence. In (Saifuddin et al.,
2021), multiple graphs are constructed by representing each text sequence with
an individual graph, and vertices are created by applying n-gram, work-
tokenizer, etc. methods, and edges are constructed between consecutive
vertices based on a fixed-size windowing technique.

Although these methods effectively represent sequential data as graphs, they
pose important limitations. For example, order-based graphs create many
vertices in case of a large sequence and many graphs for a large number of
sequences which results in higher complexity for space and processing time.
Also, it cannot capture relationships between sequences beyond the
relationships within a sequence. Moreover, in similarity-based graphs,
similarity calculation between all pairs of sequences is challenging for large
datasets. Also, selecting similarity measures would be hard, and also
considering similarity values to define a relation between sequences causes
information loss. Besides, these graph-based methods mostly operate on a
simple regular graph and only consider the dyadic relationships between nodes.
However, there could be more complex relationships (e.g., triadic, tetradic,
etc.) in sequence data that these models cannot capture.

To address these challenges mentioned above, we present a novel Graph Neural
Network (GNN) based sequence classification model named Hypergraph Attention
Network (Seq-HyGAN). Our method relies on the hypothesis that structurally
similar sequences would be under similar classes, and sequences are similar if
they have similar subsequences. To properly depict the structural-based
similarity between sequences, we present them in a hypergraph setting,
representing sequences as hyperedges connecting their subsequences as nodes.
In this way, we construct a hypergraph from all sequences. A hypergraph is a
unique model of a graph with hyperedges. Unlike a regular graph where the
degree of each edge is 2, hyperedge is degree-free; it can connect an
arbitrary number of nodes (Bretto, [n.d.]; Aktas and Akbas, 2021; Aktas et
al., 2021). Then, we develop a Seq-HyGAN consisting of a novel two-level
attention-based neural network that generates the representations of sequences
as hyperedges. Our proposed Seq-HyGAN can capture complex relationships among
the sequences and generate a robust representation of them by discovering and
emphasizing the important parts of a sequence using a two-level attention
mechanism. Unlike regular NNs (i.e., RNN) that can only capture local
information, Seq-HyGAN is more robust as it can capture both local (within the
sequence) and global (between sequences) information from the sequence data.
Moreover, while traditional GNNs with regular graphs are limited to a passing
message mechanism between two nodes, this hypergraph setting assists GNNs in
learning a much more robust representation of sequences with a message-passing
mechanism not only between two nodes but between many nodes and also between
nodes and hyperedges.

The main contributions of this paper are summarized as follows:

  * •

Hypergraph creation from sequences:

We propose a novel hypergraph model for the sequence dataset that captures the
higher-order structural similarity between sequences. In our sequence
hypergraph, each subsequence extracted from the sequences is represented as a
node. Each sequence, consisting of a set of unique subsequences, is
represented as a hyperedge. This hypergraph can capture the higher-level
connections of subsequences and sequences and help us to define complex
similarities between sequences.

  * •

Hypergraph Attention Network: We propose a novel hypergraph attention network
model, called Seq-HyGAN, for sequence classification with learning the
representation of sequences as hyperedges. It is a two-level architecture. The
first level generates the embedding of nodes via an aggregator function that
aggregates the embedding of hyperedges. Similarly, the second level generates
the embedding of hyperedges (i.e., sequences) via an aggregator that
aggregates the embedding of nodes. Since not all but a few subsequences are
mainly significant to depict similarities of sequences, we use attention
mechanisms to learn the importance of subsequences (i.e., nodes) for sequences
(i.e., hyperedge) and visa versa.

  * •

Extensive experiments: We conduct extensive experiments and compare proposed
Seq-HyGAN with the state-of-the-art baselines for four different datasets and
five different classification problems. The results with different accuracy
measures show that our method significantly surpasses the baseline models.

The rest of the paper is presented as follows. In Section 2, we briefly
summarize the related works on sequence classification and hypergraph GNN.
Then in Section 3, we describe the proposed Seq-HyGAN model, including
hypergraph construction from sequence data and a two-level attention network
for generating sequence representations. Next, in Section 4, we describe the
experimental setting and results, followed by a discussion. Finally, a
conclusion is given in Section 5.

##  2\. Related Work

Various studies have been carried out on the problem of sequence
classification. We broadly categorize them into three different types of
methods: ML-based, Deep Learning (DL)-based, and GNN-based. ML-based methods
such as support vector machine (SVM), naive bayes (NB), decision tree (DT),
etc., have been exploited widely for sequence classification tasks (Parks et
al., 2011; Rätsch et al., 2006; Raj and Mahalekshmi, 2018). Leslie et al.
(Leslie et al., 2001) use the SVM classifier for protein classification. They
employ a k-spectrum kernel in an SVM classifier that transforms a sequence
into a feature vector. Moreover, Saigo et al. (Saigo et al., 2004) exploit a
distance-based local alignment kernel for protein classification. Other widely
used kernels for sequence classification include string kernel, diffusion
kernel, polynomial kernel, etc. (Rätsch et al., 2006; She et al., 2003;
Schölkopf et al., 2004). Nigam et al. (Nigam et al., 2000) present a semi-
supervised sequence classifier for text data. They first use NB to classify
some unlabeled samples; then, they utilize an expectation-maximization process
to adjust the parameter of the NB classifier and re-classify the unlabeled
samples. In (Deneke et al., 2017), authors present a random forest-based novel
bacterial pathogens detection framework named PaPrBag. Authors train the model
on an extensive range of species to overcome genetic divergence.

Applications of DL-based methods are also pretty common in this domain.
Different DL models for protein structure prediction are shown in (Torrisi et
al., 2020). Moreover, in(Nguyen et al., 2016), authors present DNA sequence
classification using a CNN-based model. They represent each input sequence
using a one-hot vector that preserves the positional information. (Eickholt
and Cheng, 2013) presents a framework named DNdisorder to predict protein
disorder. They utilize boosted ensembles of deep networks, and the results
demonstrate that the proposed model is very competitive to the baselines.
Since cancer treatments are costly and unfavorable for the human body,
anticancer peptides are considered future therapeutics against cancer. Timmons
et al. (Timmons and Hewage, 2021) employ a deep NN framework to predict
anticancer activities of the peptides from the amino-acid sequence. In (Min et
al., 2017), a hybrid model consisting of CNN and bidirectional LSTM is used
for chromatin accessibility prediction.

Figure 1. Example of a De-Bruijn graph with 3-mer

Network-based models have also been explored to analyze sequence data. Such as
predicting genomics sub-compartments (Ashoor et al., 2020), and disease gene
prediction (Hwang et al., 2019). A common approach to representing genome
sequence in a network is by using the De-Bruijn graph (Turner et al., [n.d.]).
To construct a De-Bruijn graph, the $k$-mer method is first applied to a
sequence input. Each generated k-mer token is used as a node, and subsequent
k-mers having an overlap in k-1 positions are connected using an edge to
construct the graph. If $V$ is the set of the nodes of a De-Bruijn graph and
$L$ is the length of the corresponding sequence, then the number of nodes in
the graph would be $|V|\leq L-k+1$. An example of constructing a De-Bruijn
graph from a DNA sequence with 3-mer is shown in Figure 1.

GNN is one of the mainstream graph learning paradigms. GNNs have exhibited
great performances in different research fields, such as DDI prediction
(Tanvir et al., 2022), image classification (Quek et al., 2011), etc. Graph
convolutional network (GCN), the most popular variant of GNN, has also been
applied for sequence data analysis. In (Yao et al., [n.d.]), authors apply GCN
for text classification. Authors first construct a heterogeneous text graph
with two types of nodes: document and word nodes from the whole corpus. Word
co-occurrence information is used to build an edge between two nodes, and an
edge between the word and document node is built based on the term frequency-
inverse document frequency (TF-IDF). After that, the authors apply GCN to this
graph and the experiment shows that this model outperforms traditional DL
models. (Guo et al., [n.d.]) et al. employ the same architecture for DNA-
protein binding prediction from sequential data. Their networks have sequence
and token nodes extracted from sequences by applying $k$-mer. In (Huang et
al., [n.d.]) and (Zhang et al., [n.d.]), instead of constructing one corpus-
level text graph, authors create text graphs from each sentence and apply
message passing-based and gated GNN, respectively.

Due to the ability to capture higher-order complex relations, hypergraph and
hypergraph neural networks have recently gotten huge attention in different
research domains (Feng et al., 2018; Kim et al., [n.d.]; Wu et al., 2020).
These works mainly focus on node representation by using hypergraph neural
networks. However, in our proposed Seq-HyGAN, we design a novel two-level
attention network to get the representation of edges instead of nodes.
Moreover, as we know, this paper is the first to address the sequence
classification problem using hypergraph and attention-based hypergraph neural
networks.

##  3\. Methodology

###  3.1. Preliminaries, and settings

Sequence classification is the problem of predicting the class of unlabeled
sequences by leveraging the information from the labeled ones. NN models for
sequence classification are limited to only capturing the local spatial
relationships between the subsequences of a sequence and fail to capture
global relationships between subsequences. Moreover, graph-based models
consider simple graphs having only dyadic relationships between the nodes.
However, in real life, more complex networks exist where an arbitrary number
of nodes may interact as a group. These groups of arbitrary numbers of nodes
can be present by hyperedges (i.e., triadic, tetradic, etc.). Graphs having
hyperedges are known as hypergraphs. Below is a formal definition of a
hypergraph.

###### Definition 3.1.

Hypergraph: A hypergraph is defined as ${G}=({V},{E})$ where
${V}=\\{v_{1},...,v_{i}\\}$ is the set of nodes and
${E}=\\{e_{1},...,e_{j}\\}$ is the set of hyperedges. Hyperedge is a special
kind of edge that consists of any number of nodes.

Similar to the adjacency matrix of a regular graph, a hypergraph can be
denoted by an incidence matrix $H^{nxm}$ where $n$ is the number of nodes, $m$
is the number of hyperedges and

$\displaystyle H_{ij}=\begin{cases}1&\text{if $v_{i}\in e_{j}$}\\\
0&\text{otherwise}\end{cases}$

Our motivation in this work is that patterns as subsequences are important
features of sequences, and if two sequences share many patterns, they have a
higher similarity. Also, it is assumed that similar sequences will have the
same class labels. To define the higher-order pattern-based similarity between
sequences, we construct a hypergraph from the sequence data. After hypergraph
creation, to accomplish the sequence classification task, we propose an
attention-based hypergraph neural network model consisting of a novel two-
level attention mechanism that learns the important subsequences (nodes) and
thus the representation of the sequences (hyperedges). We train the whole
model in a semi-supervised fashion. Our proposed model has two steps: (1)
Hypergraph construction from the sequence data, (2) Sequence classification
using attention-based hypergraph neural networks.

Figure 2. System architecture of the proposed method. The first step is
hypergraph construction where each sequence (e.g., DNA) is a hyperedge, and
the (frequent) subsequences of sequences are the nodes. The second step is an
attention-based hypergraph neural network model for sequence classification
Seq-HyGAN that generates the representations of sequences while giving more
attention to the important subsequences.

###  3.2. Sequence Hypergraph Construction

In order to learn the similarity of sequences for sequence classification, we
need to define the relationship between sequences and also between
subsequences within each sequence. For this goal, we construct a hypergraph
that captures the higher-order similarity of the sequences. First, we
decompose the sequences into a set of subsequences as the important patterns
of the sequences. Then, we represent this set of subsequences as the nodes of
the hypergraph and each sequence including a set of subsequences is a
hyperedge. Each hyperedge may connect with other hyperedges through some
shared nodes as subsequences. Thus, this constructed hypergraph defines a
higher-level connection of sequences and subsequences and helps to capture the
complex similarities between the sequences. Moreover, this hypergraph setting
ensures a better robust representation of sequences with a GNN model having a
message-passing mechanism not only limited to two nodes but rather between the
arbitrary number of nodes and also between edges through nodes. The steps of
hypergraph construction are shown in Algorithm 1.

Input:  $Sequences$

Output: Hypergraph incident matrix: $H$

Subsequence_list¡- $Sequence\\_Decomposition(Sequences)$;

/* Sequence_Decomposition() could be ESPF or $k$-mer that decomposes sequences
into moderated size subsequences. */

for  _each subsequence in Subsequence_list_ do

if  _subsequence is in Sequence_dictionary[sequence]_ then

$H[i,j]=1$ ;

/* i,j is the id of subsequence and sequence, respectively. */

end if

end for

Output:  Hypergraph incident matrix, $H$

Algorithm 1 Sequence Hypergraph Construction

Different algorithms can be used to generate the subsequences such as ESPF
(Huang et al., 2019), $k$-mer (Zhang et al., 2017), strobemers (Sahlin, 2021).
In this paper, we exploit ESPF, and $k$-mer to generate subsequences and
examine their effects on the final results. While $k$-mer uses all the
extracted subsequences for a certain $k$ value, ESPF only selects the most
frequent subsequences from a list of candidate subsequences for a certain
threshold. Below we describe the ESPF and $k$-mer methods.
ESPF: ESPF stands for Explainable Substructure Partition Fingerprint. As for
sub-word mining in the natural language processing domain, ESPF decomposes
sequential inputs into a vocabulary list of interpretable moderate-sized
subsequences. ESPF considers that a specific sequence property is mainly led
by only a limited number of subsequences known as functional groups. We
present the details of ESPF in Algorithm 2. Given a database $S$ of sequences
as input, ESPF generates a vocabulary list of subsequences as frequent
reoccurring customized size subsequences. Starting with tokens as the initial
set, it adds subsequences having a frequency above a threshold, $\beta$ in $S$
to the vocabulary list. Subsequences appear in this vocabulary list in order
of most frequent to least frequent. In our hypergraph, we use this vocabulary
list as nodes and break down any sequence into a series of frequent
subsequences relating to those. For any given sequence as input, we split it
in order of frequency, starting from the highest frequency one. An example of
splitting a DNA sequence is as follows.

GCTGAAAGCAACAGTGCAGACGATGAGACCGACGATCCCAGGAGGTAA

$\Downarrow$

G CTGAAAG CAACAG TGCAGA CGA TGAGA CCGACGA TCCCAG GAGG TAA

Input:  Initial Sequence tokens set ${S}$, tokenized Sequence strings set
${\tau}$, frequency threshold $\beta$, and size threshold ${M}$ for $S$.

for  _${t=1\dots,M}$_ do

$(a,b)$, $f$ $\leftarrow$ scan $\tau$ ;

/* $(a,b)$ is the the most frequent consecutive tokens with frequency $f$. */

if  _$f <\beta$_ then

break ;

/* $(a,b)$’s frequency lower than threshold */

end if

$\tau\leftarrow$ find $(a,b)\in$ $\tau$, replace with $(ab)$ ;

/* update $\tau$ with the combined token $(ab)$ */

$S\leftarrow S\cup(ab)$ ;

/* add $(ab)$ to the token vocabulary set $S$ */

end for

Output:  the updated tokenized sequences, $\tau$; the updated token vocabulary
set, $S$.

Algorithm 2 Explainable Substructure Partition Fingerprint (ESPF)

k-mer: $k$-mer is an effective popular tool widely used in biological sequence
data analysis (e.g., sequence matching). It splits sequential inputs into a
list of overlapping subsequence strings of length $k$. $k$-mer is very similar
to the n-gram model used in natural language processing. To generate all
$k$-mers from an input string, it starts with the first $k$ characters and
then moves by just one character to get the next subsequence, and so on. Thus
it generates subsequences that overlap in k-1 positions. If $t$ is the length
of a sequence, there are $t-k+1$ numbers of $k$-mers and $p^{k}$ total
possible number of $k$-mers, where $p$ is the number of monomers. $k$-mers can
be considered as the words of a sentence. Like words, they help to attain the
semantic features from a sequence. For example, for a sequence ATGT, monomers:
{A, T, and G}, 2-mers: {AT, TG, GT}, 3-mers: {ATG, TGT}.

###  3.3. Attention-based Sequence Hypergraph Neural Network (Seq-HyGAN) for
Sequence Classification

We utilize the Seq-HyGAN for sequence classification that learns the
representation of sequences. Seq-HyGAN has a two-level attention network
optimized with class labels. Moreover, this attention network helps to
discover the important subsequences of a sequence.

Sequence Representation learning using Seq-HyGAN To classify sequences, it is
essential to generate feature vectors that can effectively embed the
structural information. Since in our hypergraph model, we represent each
sequence as a hyperedge, we need to learn hyperedge representation. Therefore,
regular GNN models that generate the embedding of nodes will not work on our
hypergraph. We propose Seq-HyGAN that generates ${f}^{{}^{\prime}}$
dimensional embedding vectors for hyperedges (sequences).

Given the $f$ dimensional hyperedge feature matrix, $X\in R^{E*f}$ and
incidence matrix $H\in R^{V*E}$, the proposed model generates a feature vector
of $f^{\prime}$ dimension via learning a function $F$. A layer (e.g.,
${(l+1)^{th}}$ layer) of Seq-HyGAN can be written as

(1) $X^{l+1}=F(X^{l},H^{T}).$

In our proposed model, we leverage a memory-efficient self-attention mechanism
to capture the high-order relations among data. It has two levels of
attention: (1) hyperedge-level attention (2) node-level attention. Hyperedge-
level attention generates the representation of nodes by aggregating hyperedge
information with attention; similarly, node-level attention aggregates the
node information to generate the representation of hyperedges with attention.
We define edge and node feature aggregation with attention as follows

(2) $\displaystyle
m_{i}^{l}=\mathbf{AG_{E}}^{l}(m_{i}^{l-1},{n_{j}^{l-1}}|\forall e_{j}\in
E_{i}),$ (3) $\displaystyle
n_{j}^{l}=\mathbf{AG_{V}}^{l}(n_{j}^{l-1},{m_{i}^{l}}|\forall v_{i}\in e_{j})$

where AGE aggregates the information of hyperedges to generate the $l$-th
layer representation $m_{i}^{l}$ of node $v_{i}$ and $E_{i}$ is the set of
hyperedges $v_{i}$ is connected with. Similarly, AGV aggregates the
information of nodes to generate the $l$-th layer representation $n_{j}^{l}$
of hyperedge $e_{j}$ and $v_{i}$ is a node that connects to hyperedge $e_{j}$.

Hyperedge-level attention: Though a node may belong to different hyperedges,
all hyperedges may not be equally important for that node. To highlight the
important hyperedges, we design an attention mechanism. While aggregating
hyperedge representations, this attention mechanism ensures more weight to
important hyperedges than others. With the attention mechanism, the node
feature $m_{i}^{l}$ of node $v_{i}$ is defined as

(4)
$m_{i}^{l}=\alpha\left(\sum_{e_{j}\in{E_{i}}}\Gamma_{ij}W_{1}n_{j}^{l-1}\right)$

where $\alpha$ is a nonlinear activation function, $W_{1}$ is a trainable
weight to linearly transform the input hyperedge feature into a high-level,
and $\Gamma_{ij}$ is the attention coefficient of hyperedge $e_{j}$ on node
$v_{i}$. The attention coefficient $\Gamma_{ij}$ is defined as

(5) $\Gamma_{ij}=\frac{\exp({\mathbf{e_{j}}})}{\sum_{e_{k}\in
E_{i}}\exp(\mathbf{e_{k}})}$

(6) $\mathbf{e_{j}}=\beta{(W_{2}n_{j}^{l-1}*W_{3}m_{i}^{l-1})}$

where $E_{i}$ is the set of hyperedges connected to node $v_{i}$, $\beta$ is a
LeakyReLU activation function and $*$ is the element-wise multiplication and
$W_{2}$ and $W_{3}$ are weight matrix.

Node-level attention: Hyperedge is degree-free that consists of an arbitrary
number of nodes. But the contribution of nodes in hyperedge construction may
not be the same. Similar to hyperedge-level attention, to highlight the
important nodes, we design an attention mechanism. While aggregating nodes,
this attention mechanism ensures more weight to important nodes than others.
With the attention mechanism, the hyperedge feature $n_{j}^{l}$ of hyperedge
$e_{j}$ is defined as

(7)
$n_{j}^{l}=\alpha\left(\sum_{v_{i}\in{e_{j}}}\Delta_{ji}W_{4}m_{i}^{l}\right)$

where $\alpha$ is a nonlinear activation function, $W_{4}$ is a trainable
weight to linearly transform the input vertex feature into a high-level, and
$\Delta_{ji}$ is the attention coefficient of node $v_{i}$ in the hyperedge
$e_{j}$. The attention coefficient is defined as

(8) $\Delta_{ji}=\frac{\exp({\mathbf{v_{i}}})}{\sum_{v_{k}\in
e_{j}}\exp(\mathbf{v_{k}})}$

(9) $\mathbf{v_{i}}=\beta{(W_{5}m_{i}^{l}*W_{6}n_{j}^{l-1})}$

where $\beta$ is a LeakyReLU activation function, $v_{k}$ is the node that
belongs to hyperedge $e_{j}$, and $*$ is the element-wise multiplication and
$W_{5}$ and $W_{6}$ are weight matrix.

Seq-HyGAN generates the hyperedge representations by employing this two-level
of attention. Finally, we linearly project the output of Seq-HyGAN with a
trainable weight matrix to generate a $C$ dimensional output for each
hyperedge as $Z=nW_{c}^{T}$, where $C$ is the number of classes, n is the
output of the Seq-HyGAN, and $W_{c}$ is a trainable weight.

Training: We train our entire model using a cross-entropy loss function
defined as

(10)
$L=-\sum_{i=1}^{N}\sum_{c=1}^{C}w_{c}\log\frac{\exp(Z_{i,c})}{\sum_{j=1}^{C}\exp(Z_{i,j})}y_{i,c}$

where $y$ is the target, $w$ is the weight, $C$ is the number of classes, and
$N$ is the number of samples.

###  3.4. Complexity

Seq-HyGAN is an efficient model that can be paralyzed across the edges and the
nodes (Kipf and Welling, 2016). Given the $f$ dimensional initial feature of a
sequence, it exploits a two-level attention network and generates
${f}^{{}^{\prime}}$ dimensional embedding vector for the sequence. Thus, the
time complexity of Seq-HyGAN can be expressed in terms of the cumulative
complexity of the attention networks. From equation 4, we can formulate the
time complexity for the hyperedge-level attention as:
$O(|E|f{f}^{{}^{\prime}}+|V|\kappa{f}^{{}^{\prime}})$, where $\kappa$ is the
average degree of nodes. Similarly, we can formulate the time complexity in
the node-level attention as:
$O(|V|f{f}^{{}^{\prime}}+|E|\chi{f}^{{}^{\prime}})$, where $\chi$ is the
average degree of hyperedges.

##  4\. Experiment

In this section, we perform extensive experiments on four different datasets
and five different research problems to evaluate the proposed Seq-HyGAN model.
We compute three different accuracy metrics, Precision, Recall, and F1-score,
to analyze and compare our proposed model with the state-of-the-art baseline
models. This section starts with a description of our datasets, parameter
settings, and baselines, and then, we present our experimental results.

Table 1. Statistics of Dataset Dataset | # of sample | avg. length
---|---|---
Human DNA | 4380 | 1264
Anticancer peptides | 939 | 17
Cov-S-Protein-Seq | 1238 | 1297
Bach choral | 5665 | 40
Table 2. # of Nodes (N) in the hypergraph for different datasets based on frequency threshold of ESPF method ESPF | Human DNA | Anticancer peptides | Cov-S-Protein-Seq | Bach choral
---|---|---|---|---
| $|N|$ | $|N|$ | $|N|$ | $|N|$
5 | 25207 | 382 | 10776 | 446
10 | 15774 | 225 | 7987 | 347
15 | 11166 | 166 | 6769 | 287
20 | 8871 | 138 | 5971 | 253
25 | 7483 | 110 | 5477 | 198
Table 3. # of Nodes (N) in the hypergraph for different datasets based on size parameters of the $k$-mer method $k$-mer | Human DNA | Anticancer peptides | Cov-S-Protein-Seq | bach choral
---|---|---|---|---
| $|N|$ | $|N|$ | $|N|$ | $|N|$
5 | 1247 | 10301 | 99794 | 3220
10 | 602855 | 6799 | 157399 | 14462
15 | 1449240 | 3103 | 193544 | 16163
20 | 1462963 | - | 223073 | 17909
25 | 1467256 | - | 248938 | 18752

###  4.1. Dataset

We evaluate the performance of our model using four different sequence
datasets. They are (1) Human DNA sequence, (2) Anti-cancer peptides, (3) Cov-
S-Protein-Seq and (4) Bach choral harmony. All these datasets are publicly
available online. Table 1 shows the statistics of the datasets.

  1. (1)

Human DNA sequence dataset has 4,380 DNA sequences, and each sequence belongs
to a particular gene family. A gene family is a set of related genes that
share a common ancestor. This dataset has seven different gene families (i.e.,
seven classes): G protein-coupled receptors, Tyrosine Kinase, Tyrosine
Phosphatase, Synthetase, Synthase, Ion channel, and Transcription factor. Our
goal is to predict the gene family based on the DNA coding sequence. We obtain
this dataset from Kaggle (Chauhan, [n.d.]) , which is a common online platform
for machine learning and data scientists to collaborate between them.

  2. (2)

Anti-cancer peptides (ACPs) are short bioactive peptides typically formed of
10–60 amino acids (Xie et al., 2020). They have the characteristics to hinder
tumor cell expansion and formation of tumor blood vessels and are less likely
to cause drug resistance and low toxicity to normal cells (Huang et al., 2021;
Xie et al., 2020). ACPs are also found to interact with vital proteins to
inhibit angiogenesis and recruit immune cells to kill cancer cells, such as
HNP-110 (Huang et al., 2021). These unique advantages make ACPs the most
promising anti-cancer candidate (Grisoni et al., [n.d.]). The Anti-Cancer
Peptides dataset contains 949 one-letter amino-acid sequences representing
peptides and their four different anti-cancer activities (i.e., very active,
moderately active, experimental inactive, virtual inactive) on breast and lung
cancer cell lines. Given the amino-acid sequence, our goal is to predict the
anti-cancer activities. We get this dataset from UCI Machine Learning
Repository (UCI, [n.d.])

  3. (3)

Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) is the
coronavirus that is responsible to lead the worldwide COVID-19 pandemic (Ali
et al., 2022). One of the most important bio-markers of SARS-CoV-2 is the
existence of spike proteins (S-protein) that let these viruses enter host
cells and yield an infection (Belouzard et al., 2012). Cov-S-Protein-Seq
dataset has 1238 coronavirus (CoV) spike protein sequences belonging to 67
different CoV species. These species are grouped into the most frequent seven
groups: Avian coronavirus, Porcine epidemic diarrhea virus, Betacoronavirus1,
Middle East respiratory syndrome coronavirus, Porcine coronavirus HKU 15, SARS
CoV 2, and all remaining ones are as other-species. This dataset also has
information on host species of the CoVs. There is overall 39 different host
species information in this dataset. These are grouped into the six most
frequent groups: Swine, Avians, humans, Bats, Camels, and other mammals. Given
the spike protein sequences of CoVs, we predict the CoV species and host
specificity. A cleaned and pre-processed version of Cov-S-Protein-Seq data is
collected from (Kuzmin et al., 2020).

  4. (4)

Music is sequences of sounding events. Each event has a specific chord label.
Chords are harmonic sets of pitches also known as frequencies. The Bach choral
harmony dataset is composed of 60 chorales having 5665 events (Radicioni and
Esposito, 2010). Each event of each chorale is labeled using one among 101
chord labels and described through 14 features, including 12 different pitch
classes, Bass, and meter. Given this information, our target is to predict the
chord label. In our experiment, out of 101 chord labels, we select the five
most frequent chord labels. We get this dataset from UCI Machine Learning
Repository (UCI, [n.d.]).

###  4.2. Parameter Settings

We extract subsequences from given sequence datasets using ESPF and $k$-mer
separately to create our hypergraph. With a low-frequency threshold, ESPF
produces more subsequences, and all of them may not be important. But with a
large-frequency threshold, it produces less number of subsequences and there
might be a missing of some vital subsequences. We choose five different
frequency thresholds from 5 to 25 and examine the impact of threshold value on
hypergraph learning. Similarly, in $k$-mer, typically with the increment of
$k$-mer length (i.e., $k$ value), the number of subsequences also increases.
We choose five different $k$ values from 5 to 25 and examine their impact on
hypergraph learning. However, as Anticancer peptide sequences are too small,
we just choose $k$ from 5 to 15. The number of nodes for different threshold
values of ESPF and $k$-mer is given in Table 2 and Table 3 for each dataset.

Table 4. Hyper-parameter Settings Parameter | Values
---|---
Learning rate | 1e-2, 5e-2, 1e-3, 5e-3
Hidden units | 32, 64, 128
Dropout | 0.1, 0.5
Weight decay | 1e-2, 1e-3
Number of epochs | 1000
Patience | 200

We randomly split our datasets into 80:10:10 train: validation: test ratio.
This process is repeated five times, and average accuracy metrics are reported
in the results part. A grid search method is employed to obtain the optimal
hyper-parameters based on the validation set. Table 4 shows the ranges of grid
search used in the experiment.

We utilize a single-layer Seq-HyGAN having a two-level of attention network.
Simple one-hot coding is used as an initial feature of the sequences. A
LeakyReLU activation function is used on the attention networks side. The
model is trained with 1000 epochs and optimized using adam optimizer. An early
stop mechanism is used if the validation loss does not change for 200
consecutive epochs.

The ML classifiers in subsection: 4.3 are taken from sci-kit learn (Pedregosa
et al., 2011). For logistic regression (LR), we set the inverse of
regularization strength, C=2. A linear kernel with polynomial degree 3 is used
in the support vector machine (SVM). Default parameters are used for the
decision tree (DT) classifier. The DL models are implemented from Keras layers
(Chollet et al., 2015). In the DL models, RCNN and BiLSTM, we use relu and
softmax activation functions in the hidden dense layers and dense output
layer, respectively. The models are optimized using adam optimizer, and
dropout layers of 0.2 are used to prevent overfitting. For node2vec, the walk
length, number of walks, and window size are set to 80, 10, and 10,
respectively, and for graph2vec, we use the default parameters following the
source. We follow DGL (Wang et al., 2019) to implement GCN. For DNA-GCN, and
hypergraph neural networks (HGNN, HyperGAT), we use the same hyper-parameters
as mentioned in the source papers.

###  4.3. Baselines

We evaluate our model by comparing its performance with different types of
state-of-the-art models. Based on the data representation style and
methodology, we categorize the baseline models into the below groups.

1\. Machine Learning  LR, SVM, and DT classifiers have been used widely for
sequence classification. We employ these three supervised ML classifiers to
classify the sequences. ML models require explicit features to train and learn
the data classes. We utilize CountVectorizer to generate the features.
CountVectorizer returns a numerical vector for each sequence based on the
count of subsequences in the entire sequence.

2\. Deep Learning  While DL models are successfully employed in different
research applications, their performance broadly relies on the availability of
a large amount of curated data. In this research, we explore two different
hybrid DL models as baselines. They are recurrent convolutional neural
networks (RCNN) and bidirectional long short-term memory (BiLSTM). While RCNN
leverages the advantages of both RNN and CNN, BiLSTM incorporates both past
and future information (i.e., both left and right context) to get the current
representation. We use CountVectorizer as an initial feature.

3\. Node2vec  We represent each sequence in a graph setting by following a
classic method called the De-Bruijn graph as explained in section 2. After
constructing the graph, we apply Node2vec, which is a random walk-based graph
embedding. Node2vec generates the embedding of nodes. To obtain the graph-
level representation, we average the embedding of nodes of that graph.
Finally, the generated embedding is fed as a feature to the ML classifier for
sequence classification.

4\. Graph2vec This is a data-driven unsupervised neural framework that
generates graph representation. It generates task-agnostic generic embedding
without leveraging any task-oriented information. We apply this graph
embedding method to the De-Bruijn graph to generate graph features. Then the
graph features are fed into the ML classifiers for sequence classification.

5\. Graph Neural Network  Nowadays, GNN has become one of the most powerful
tools for learning node and graph representation. Here, we apply GCN (Kipf and
Welling, 2016) on De-Bruijn graphs to learn the node embedding. Then we get
the graph-level embedding using an average pooling-based readout function.

Moreover, We follow DNA-GCN (Guo et al., [n.d.]) to construct a heterogeneous
graph from the entire corpus and the extracted subsequences. This graph has
two types of nodes: sequence node and subsequence node. These nodes are
connected via two types of edges: subsequence-subsequence edge and sequence-
subsequence edge. Subsequence-subsequence edges are constructed based on the
point-wise mutual information (PMI) score, and sequence-subsequence edges are
constructed using the TF-IDF score. After constructing the graph, we apply a
two-layer GCN. Though there are no direct edges between sequence nodes, two-
layer GCN allows information to be passed between the sequence nodes.

6\. Hypergraph Neural Network (HNN) We further compare our model performances
with two state-of-the-art hypergraph neural network models: HGNN (Feng et al.,
2018) and HyperGAT (Ding et al., 2020). HGNN presents a generalized hyperedge
spectral convolution operation for hypergraph learning. HGNN generates the
representation of nodes by aggregating hyperedges. First, we apply HGNN to our
graphs and get the node (i.e., subsequence) representations, and then we
combine the node representations to get the hyperedge representations.
Finally, the hyperedge representations are passed through a classifier.

HyperGAT is an attention-based hypergraph neural network that is presented for
document classification problems. Authors first construct document-level
hypergraphs where each sentence is represented as a hyperedge, and words are
represented as nodes. After that, the authors design an attention network that
learns the node representations. Finally, the node (word) representations are
passed through a mean-pooling layer to get the document representation. We
apply HyperGAT to our sequence hypergraphs and generate the embeddings of
subsequences, and then we apply a mean-pooling layer to get the sequence
embedding. Then, the representation is passed through a classifier. In both
HGNN and HyperGAT, we use one-hot coding of nodes as initial features.

Table 5. Average network density for the datasets for a specific value of $k$-mer Dataset | $k$-mer | Avg. network density
---|---|---
Human DNA | 25 | 0.0100
Anticancer peptides | 5 | 0.3868
CoV-S-Protein-Seq | 25 | 0.0031
Bach choral | 25 | 0.2702
Figure 3. Performance comparison of the proposed model with different
thresholds of ESPF for different datasets. Figure 4. Performance comparison of
the proposed model with different thresholds of $k$-mer for different
datasets.

###  4.4. Results

####  4.4.1. Model Performance

We assess the performance of our proposed model by performing extensive
experiments on four different datasets for five different problems. For each
experiment, we select different threshold values of ESPF and $k$-mer, and we
present the overall performance of our proposed models in Figure 3 and Figure
4.

Table 6.  Performance comparisons of models for Human DNA, Bach choral and Anticancer datasets  Model | Method | Human DNA | Bach choral | Anticancer pept.
---|---|---|---|---
| P | R | F1 | P | R | F1 | P | R | F1
| LR | 92.82 | 90.64 | 90.84 | 88.09 | 76.68 | 78.52 | 77.00 | 83.16 | 77.67
ML | SVM | 90.09 | 85.39 | 85.83 | 89.30 | 80.27 | 82.08 | 83.10 | 86.32 | 83.27
| DT | 92.87 | 80.37 | 83.68 | 86.49 | 70.85 | 73.92 | 78.28 | 85.32 | 81.35
| RCNN | 68.84 | 37.90 | 27.86 | 76.83 | 71.30 | 68.23 | 69.62 | 80.00 | 73.34
DL | BiLSTM | 77.80 | 39.27 | 35.18 | 73.93 | 69.96 | 66.32 | 65.70 | 81.05 | 72.57
| LR | 36.09 | 32.19 | 22.89 | 6.61 | 19.73 | 8.33 | 71.32 | 82.11 | 75.11
Node2vec | SVM | 10.32 | 30.82 | 14.52 | 14.14 | 20.18 | 16.17 | 66.39 | 81.05 | 72.99
| DT | 18.04 | 18.26 | 18.13 | 23.03 | 22.87 | 22.89 | 68.75 | 64.21 | 66.40
| LR | 21.07 | 26.94 | 23.63 | 23.34 | 19.73 | 17.81 | 66.39 | 81.05 | 72.99
Graph2vec | SVM | 10.32 | 30.82 | 14.52 | 3.89 | 19.73 | 06.50 | 71.32 | 82.11 | 75.11
| DT | 19.41 | 19.63 | 19.39 | 25.60 | 25.56 | 25.48 | 77.93 | 73.68 | 75.54
GNN | DNA-GCN | 96.46 | 96.28 | 96.36 | 85.54 | 85.24 | 85.27 | 83.25 | 83.53 | 83.82
| GCN | 10.06 | 32.14 | 16.01 | 4.57 | 19.71 | 7.31 | 73.11 | 85.42 | 78.75
HNN | HGNN | 87.03 | 86.82 | 87.12 | 86.12 | 86.89 | 86.93 | 83.82 | 85.42 | 83.97
| HyperGAT | 85.13 | 85.33 | 84.11 | 88.09 | 87.44 | 87.45 | 85.33 | 88.42 | 86.68
| ESPF | 88.42 | 87.21 | 87.53 | 89.72 | 89.24 | 89.28 | 91.94 | 86.16 | 87.27
Seq-HyGAN |  $k$-mer | 98.72 | 98.68 | 98.73 | 93.18 | 92.83 | 92.85 | 93.03 | 91.58 | 92.00

In Figure 3, we depict the performance of our models for different datasets
with a changing frequency threshold of ESPF from 5 to 25. From this figure, we
can see that generally, with the increase of ESPF frequency threshold, model
performance degrades. Especially it shows that the ESPF frequency threshold
has a comparatively more significant impact on the Human DNA dataset than
others. With the change of frequency threshold from 5 to 25, the precision,
recall, and F1 of the Human DNA dataset have dropped by almost 25%. Since with
the increase of frequency threshold, we get a smaller number of subsequences
(nodes), and it might not be enough to learn hyperedges with those smaller
numbers of nodes (refer Table 2). Generally, frequency threshold 5 yields the
best performance for Human DNA and CoV-S-Protein-Seq (for Host species
classification) datasets. We get the best performance for Bach choral,
Anticancer peptides, and CoV-S-Protein-Seq (for Virus-species classification)
datasets with frequency thresholds of 15, 10, and 15, respectively.

Figure 4 presents the proposed models’ performances on different datasets for
five different $k$ values of $k$-mer ranges from 5 to 25. As of ESPF, the
effect of parameter $k$ on the results is most for Human DNA than other
datasets. When the $k$ value is 5, the F1-score of Human DNA is 33.98%, and
for the $k$ value of 25, it is increased by about 190% to 98.73%. Similar
changes happened for precision and recall values. The next highest changes are
noticed for the Bach choral dataset. With the increase of threshold $k$ from 5
to 25, its accuracy measures are increased by about 27%. The threshold has
comparatively less impact on the results of Cov-S-Protein-Seq datasets.
However, interestingly with the increase of $k$, the results of the Anticancer
peptides dataset decrease. The reasons for these scenarios could be explained
by Table 3. In this table, we can see that with the increase in threshold, the
number of nodes in the Human DNA dataset has markedly increased from 1,247 to
1,467,256. This vast number of nodes might capture better information and thus
improve the overall performance. On the other hand, for Anticancer peptides,
with the increase of $k$, the number of nodes decreases, hence the graph size,
which might degrade the performance.

####  4.4.2. Comparative analysis with Baselines

We compare our model results with several state-of-the-art baseline models for
each dataset. We consider the thresholds for ESPF and $k$-mer that give the
best result for our models for each dataset; as an example, for the Human DNA
dataset, we chose $k=25$ for $k$-mer that gives the highest score for this
data. The experimental results of all models for Human DNA, Bach choral, and
Anticancer peptides (Anticancer pept.) datasets are shown in Table 6, and all
model results for Cov-S-Protein-Seq dataset for both host-species and virus-
species are shown in Table 7. In these tables, we can see our models surpass
all the baselines thoroughly for all the datasets. More specifically, in Table
6 for the Human DNA dataset, our Seq-HyGAN with $k$-mer gives the best
performance with 98.72%, 98.68%, and 98.73% on precision (P), recall (R), and
F1-score (F1). The next best performer is DNA-GCN, which achieves an F1-score
of 96.36%, almost 2.4% lower than our model and similar to other accuracy
measures. The accuracy of ML models is also very promising and competitive
with our models. All the ML models achieve an F1-score above 80%.

Eventually, for all the datasets, the hypergraph-based model gives the best
performance. Specifically, in almost every case, HyperGAT serves as the
superior baseline while HGNN performs as the second-best baseline. The reason
for their success lies in their ability to capture higher-order, intricate
relationships within a hypergraph structure. Additionally, HyperGAT utilizes
attention networks to enhance sequence representation learning, which is
superior to HGNN’s approach. It is worth mentioning that we apply these models
to our hypergraphs and our experiments demonstrate the effectiveness of
representing sequences as hypergraphs.

Table 7.  Performance comparisons of models on Cov-S-Protein-Seq dataset for Host and Virus species prediction  Method | Model | Host species | Virus species
---|---|---|---
| P | R | F1 | P | R | F1
| LR | 92.64 | 91.94 | 91.48 | 96.04 | 95.16 | 95.21
ML | SVM | 94.20 | 93.55 | 93.42 | 96.60 | 95.97 | 96.02
| DT | 92.25 | 91.13 | 91.25 | 95.60 | 94.97 | 95.02
| RCNN | 83.22 | 79.03 | 76.82 | 65.53 | 62.90 | 57.47
DL | BiLSTM | 70.61 | 66.94 | 61.56 | 66.66 | 72.58 | 66.92
| LR | 26.28 | 29.03 | 19.29 | 12.34 | 20.16 | 14.92
Node2vec | SVM | 23.07 | 24.19 | 23.27 | 22.42 | 25.00 | 23.54
| DT | 20.00 | 21.77 | 20.80 | 23.47 | 23.39 | 23.33
| LR | 23.74 | 25.00 | 23.98 | 25.92 | 28.23 | 26.67
Graph2vec | SVM | 7.52 | 27.42 | 11.80 | 17.16 | 22.58 | 16.59
| DT | 22.68 | 22.58 | 22.50 | 22.80 | 22.58 | 22.47
GNN | DNA-GCN | 90.91 | 90.18 | 91.11 | 94.34 | 94.57 | 94.13
| GCN | 10.64 | 31.90 | 15.81 | 4.31 | 19.32 | 6.99
HNN | HGNN | 91.52 | 91.91 | 91.60 | 94.62 | 94.42 | 94.63
| HyperGAT | 93.44 | 93.55 | 93.14 | 95.52 | 95.35 | 95.45
| ESPF | 95.39 | 95.16 | 95.19 | 98.50 | 98.39 | 98.40
Seq-HyGAN |  $k$-mer | 97.23 | 95.97 | 96.78 | 99.40 | 99.19 | 99.24

The overall performance of DNA-GCN is also very competitive with hypergraph-
based approaches. DNA-GCN is based on a heterogenous graph that has both
sequence and subsequence nodes. It allows information to be passed between the
subsequences and also between sequence and subsequence. Moreover, though it
does not have any direct connection between sequence nodes, it employs a two-
layer GCN that allows the information to be passed between the sequences too.
This whole architecture helps it learn a robust representation of sequences.
Out of all ML models, generally, SVM generates better output for all the
datasets. However, ML models cannot learn features automatically and are
limited to external features. In both tables, for all the datasets, the
performances of DL models fail to cross the ML classifiers. For example, in
Bach choral dataset, the F1-score of Seq-HyGAN with $k$-mer is above 92%, and
for ML with SVM classifier, it is above 82%. But the F1-score for RCNN and
BiLSTM are 68.23% and 66.32%, respectively. A similar scenario in all other
datasets. A possible reason behind the poor performance of DL models could be
the size of the data corpus. We know DL models are called data-hungry models.
Their performances largely rely on the availability of a bulk amount of label
data. However, as we show in Table 1, all our datasets are small.

From Table 6, and 7, we can observe that the performance of Node2vec,
Graph2vec, and GCN on the Anticancer peptides dataset is convincing, but their
performances on other datasets are abysmal. One of the reasons may lie in the
network structure of these datasets. Table 5 presents the average network
density of each dataset for a specific $k$-mer. The average network density of
a dataset is calculated by taking the mean of the densities of that dataset’s
graphs. For each dataset, the best $k$-mer is chosen based on the performances
of Seq-HyGAN models on that dataset. From this table, we can see Anticancer
peptides has the highest average network density. The average network density
of Human DNA, Bach Choral, and CoV-S-Protein-Seq are poor. And this could be a
reason behind the unsatisfactory performances of Node2vec, Graph2vec, and GCN
on these datasets.

In brief, Seq-HyGAN with $k$-mer delivers better performances than Seq-HyGAN
with ESPF. This may be because ESPF assumes frequent subsequences are the only
important ones and eliminates many infrequent subsequences. However, some
infrequent subsequences may also be important. Thus using ESPF, we may seldom
lose some infrequent important ones. On the contrary, $k$-mer does not lose
any subsequences; rather it fetches all and lets the attention model discover
the critical ones. In general, a larger $k$-mer is preferable since it
provides greater uniqueness and helps to eliminate the repetitive substrings.

Moreover, we choose the best-performing method from each baseline model for
each dataset; for example, in the case of the Human DNA dataset, we choose LR
from the ML models, BiLSTM from the DL models, LR from Graph2vec, DNA-GCN from
GNN, HyperGAT from HNN and 25-mer from our Seq-HyGAN models. Then, we compare
our models’ performances with the baselines by varying the training data sizes
from 10% to 80%. A comparison of performance in terms of the F1-score is shown
in Fig 5. Results indicate Seq-HyGAN to be the best-performing model, and it
still delivers very good results with small training data. However, decreasing
the training size affects some baseline models significantly.

Figure 5. Performance comparison of models for different training sizes

The hypergraph’s innate ability to capture complex higher-order relationships
has made it an effective model for many scientific studies. Seq-HyGAN
leverages a hypergraph structure and captures higher-order intricate relations
of subsequences within a sequence and between the sequences. Furthermore, it
generates a much more robust representation of sequence by utilizing an
attention mechanism that discovers the important subsequences of that
sequence. While the Graph Attention Network (GAT) (Kipf and Welling, 2016)
also uses an attention mechanism, it is limited to learning important
neighbors of a node and cannot learn significant edges. Additionally, GAT is
unsuitable for complex networks with triadic or tetradic relations. The
primary strength of our proposed model, Seq-HyGAN lies in its novel two-level
attention mechanism, which generates node representations by aggregating
connected hyperedges while placing more attention on important ones.
Similarly, it generates hyperedge representations by aggregating member nodes
while emphasizing crucial ones.

Table 8.  Performance (F1-score) analysis in different scenarios  Dataset | Line graph | Seq-HyGAN
---|---|---
GCN | GAT | w/o attn | w/ attn
Human DNA | 37.08 | 39.19 | 94.13 | 98.73
Bach coral | 75.41 | 77.65 | 91.21 | 92.85
Anticancer peptides | 83.52 | 86.86 | 89.88 | 92.00
Host species | 72.70 | 75.31 | 90.16 | 96.78
Virus species | 80.83 | 86.50 | 95.77 | 99.24

####  4.4.3. Case Study - Impact of hypergraph structure

In contrast to a regular graph, hypergraphs have the ability to capture
higher-order complex relationships that cannot be effectively represented by a
regular graph. This capability is demonstrated by comparing our hypergraph-
based Seq-HyGAN model and regular graphs. In order to perform this comparison,
we construct line graphs from the same datasets. The construction of line
graphs involved representing each sequence as a node and connecting two nodes
if they shared a certain number ($S$) of common subsequences. Here we select
$S$=2. Following the line graph construction, we apply GCN and GAT separately
to learn node representations and classify sequences. The performance results
are presented in Table 8. The table demonstrates that our hypergraph-based
Seq-HyGAN models outperform line graph GCN and GAT models in terms of the
F1-score.

####  4.4.4. Case Study - Impact of Attention Network

In this research paper, we aim to investigate the impact of the attention
network in the proposed Seq-HyGAN model on classification performance. To
achieve this, we train the model separately with and without the attention
network on all datasets and classification problems. The corresponding
F1-scores for the test datasets were recorded and are presented in Table 8.
The results show that the proposed Seq-HyGAN model with the attention network
(w/ attn) outperforms the model without the attention network (w/o attn).
Specifically, for CoV-S-Protein-Seq: Host species (Host species), the F1-score
improved from 90.16% in without the attention network to 96.78% with the
attention network, representing a significant 7.34% improvement. This
improvement can be attributed to the attention network’s ability to discover
crucial subsequences while learning the sequence representation, which
ultimately leads to better performance.

##  5\. Conclusion

This research paper introduces a new framework for symbolic sequence
classification using a graph neural network-based approach. Unlike previous
models, we leverage a unique hypergraph structure to capture complex higher-
order structural similarities among sequences. To achieve this, we propose the
Hypergraph Attention Network model, which includes a two-level attention
network, to learn hyperedge representations as sequences with considering the
importance of subsequences for them. Our extensive experiments demonstrate
that our method surpasses various baseline models in terms of performance.

###### Acknowledgements.

This work has been supported partially by the National Science Foundation
under Grant No 2104720.

## References

  * (1)
  * Akbas (2019) Esra Akbas. 2019\.  Index Based Efficient Algorithms For Closest Community Search. In _2019 IEEE International Conference on Big Data (Big Data)_. IEEE, 701–710.
  * Akbas and Zhao (2017) Esra Akbas and Peixiang Zhao. 2017.  Attributed Graph Clustering: An Attribute-Aware Graph Embedding Approach. In _Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017_ (Sydney, Australia) _(ASONAM ’17)_. Association for Computing Machinery, New York, NY, USA, 305–308.  https://doi.org/10.1145/3110025.3110092
  * Akoglu et al. (2015) Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015\.  Graph based anomaly detection and description: A survey.  _Data Mining and Knowledge Discovery_ 29 (4 2015), 626–688.  Issue 3. https://doi.org/10.1007/S10618-014-0365-Y/FIGURES/5
  * Aktas and Akbas (2021) Mehmet Emin Aktas and Esra Akbas. 2021.  Hypergraph Laplacians in Diffusion Framework.  _Studies in Computational Intelligence_ 1016 (2 2021), 277–288.  https://doi.org/10.48550/arxiv.2102.08867
  * Aktas et al. (2021) Mehmet Emin Aktas, Thu Nguyen, Sidra Jawaid, Rakin Riza, and Esra Akbas. 2021.  Identifying critical higher-order interactions in complex networks.  _Scientific Reports 2021 11:1_ 11 (10 2021), 1–11.  Issue 1. https://doi.org/10.1038/s41598-021-00017-y
  * Ali et al. (2022) Sarwan Ali, Babatunde Bello, Prakash Chourasia, Ria Thazhe Punathil, Yijing Zhou, and Murray Patterson. 2022.  PWM2Vec: An Efficient Embedding Approach for Viral Host Specification from Coronavirus Spike Sequences.  _Biology_ 11 (3 2022).  Issue 3. https://doi.org/10.3390/BIOLOGY11030418
  * Ashoor et al. (2020) Haitham Ashoor, Xiaowen Chen, Wojciech Rosikiewicz, Jiahui Wang, Albert Cheng, Ping Wang, Yijun Ruan, and Sheng Li. 2020\.  Graph embedding and unsupervised learning predict genomic sub-compartments from HiC chromatin interaction data.  _Nature Communications 2020 11:1_ 11 (3 2020), 1–11.  Issue 1. https://doi.org/10.1038/s41467-020-14974-x
  * Atkinson et al. (2009) Holly J Atkinson, John H Morris, Thomas E Ferrin, and Patricia C Babbitt. 2009.  Using sequence similarity networks for visualization of relationships across diverse protein superfamilies.  _PloS one_ 4, 2 (2009), e4345.
  * Belouzard et al. (2012) Sandrine Belouzard, Jean K. Millet, Beth N. Licitra, and Gary R. Whittaker. 2012.  Mechanisms of coronavirus cell entry mediated by the viral spike protein.  _Viruses_ 4 (2012), 1011–1033.  Issue 6. https://doi.org/10.3390/V4061011
  * Bretto ([n.d.]) Alain Bretto. [n.d.].  Hypergraph Theory.  ([n. d.]).  http://www.springer.com/series/8445
  * Bumgardner et al. (2022) Bri Bumgardner, Farhan Tanvir, Khaled Mohammed Saifuddin, and Esra Akbas. 2022.  Drug-Drug Interaction Prediction: a Purely SMILES Based Approach.  (1 2022), 5571–5579.  https://doi.org/10.1109/BIGDATA52589.2021.9671766
  * Chang et al. ([n.d.]) Jianxin Chang, Chen Gao, Yu Zheng, Yiqun Hui, Yanan Niu, Yang Song, Depeng Jin, and Yong Li. [n.d.].  Sequential Recommendation with Graph Neural Networks.  _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ 21 ([n. d.]).  https://doi.org/10.1145/3404835
  * Chauhan ([n.d.]) Nagesh Singh Chauhan. [n.d.].  Demystify DNA Sequencing with Machine Learning — Kaggle.  https://www.kaggle.com/code/nageshsingh/demystify-dna-sequencing-with-machine-learning/notebook
  * Chollet et al. (2015) Francois Chollet et al. 2015\.  _Keras_.  https://github.com/fchollet/keras
  * Compeau et al. (2011) Phillip EC Compeau, Pavel A Pevzner, and Glenn Tesler. 2011\.  Why are de Bruijn graphs useful for genome assembly?  _Nature biotechnology_ 29, 11 (2011), 987.
  * Deneke et al. (2017) Carlus Deneke, Robert Rentzsch, and Bernhard Y. Renard. 2017\.  PaPrBaG: A machine learning approach for the detection of novel pathogens from NGS data.  _Scientific Reports 2017 7:1_ 7 (1 2017), 1–13.  Issue 1. https://doi.org/10.1038/srep39194
  * Ding et al. (2020) Kaize Ding, Jianling Wang, Jundong Li, Dingcheng Li, and Huan Liu. 2020.  Be more with less: Hypergraph attention networks for inductive text classification.  _arXiv preprint arXiv:2011.00387_ (2020).
  * Eickholt and Cheng (2013) Jesse Eickholt and Jianlin Cheng. 2013.  DNdisorder: Predicting protein disorder using boosting and deep networks.  _BMC Bioinformatics_ 14 (3 2013), 1–10.  Issue 1. https://doi.org/10.1186/1471-2105-14-88/FIGURES/6
  * Feng et al. (2018) Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. 2018.  Hypergraph Neural Networks.  _33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019_ (9 2018), 3558–3565.  https://doi.org/10.48550/arxiv.1809.09401
  * Gligorijević et al. (2021) Vladimir Gligorijević, P. Douglas Renfrew, Tomasz Kosciolek, Julia Koehler Leman, Daniel Berenberg, Tommi Vatanen, Chris Chandler, Bryn C. Taylor, Ian M. Fisk, Hera Vlamakis, Ramnik J. Xavier, Rob Knight, Kyunghyun Cho, and Richard Bonneau. 2021.  Structure-based protein function prediction using graph convolutional networks.  _Nature Communications 2021 12:1_ 12 (5 2021), 1–14.  Issue 1. https://doi.org/10.1038/s41467-021-23303-9
  * Grisoni et al. ([n.d.]) Francesca Grisoni, Claudia S Neuhaus, Miyabi Hishinuma, Gisela Gabernet, Jan A Hiss, Masaaki Kotera, and Gisbert Schneider. [n.d.].  De novo design of anticancer peptides by ensemble artificial neural networks.  ([n. d.]).  https://doi.org/10.1007/s00894-019-4007-6
  * Guo et al. ([n.d.]) Yuhang Guo, Xiao Luo, Liang Chen, and Minghua Deng. [n.d.].  DNA-GCN: Graph convolutional networks for predicting DNA-protein binding.  ([n. d.]).  https://github.com/Tinard/dnagcn.
  * Huang et al. (2019) Kexin Huang, Cao Xiao, Lucas Glass, and Jimeng Sun. 2019\.  Explainable substructure partition fingerprint for protein, drug, and more. In _NeurIPS Learning Meaningful Representation of Life Workshop_.
  * Huang et al. (2021) Kai Yao Huang, Yi Jhan Tseng, Hui Ju Kao, Chia Hung Chen, Hsiao Hsiang Yang, and Shun Long Weng. 2021\.  Identification of subtypes of anticancer peptides based on sequential features and physicochemical properties.  _Scientific Reports 2021 11:1_ 11 (6 2021), 1–13.  Issue 1. https://doi.org/10.1038/s41598-021-93124-9
  * Huang et al. ([n.d.]) Lianzhe Huang, Dehong Ma, Sujian Li, Xiaodong Zhang, and Houfeng Wang. [n.d.].  Text Level Graph Neural Network for Text Classification.  ([n. d.]).  https://www.cs.umb.edu/
  * Hwang et al. (2019) Sohyun Hwang, Chan Yeong Kim, Sunmo Yang, Eiru Kim, Traver Hart, Edward M. Marcotte, and Insuk Lee. 2019.  HumanNet v2: human gene networks for disease research.  _Nucleic acids research_ 47 (1 2019), D573–D580.  Issue D1. https://doi.org/10.1093/NAR/GKY1126
  * Islam et al. (2021) Muhammad Ifte Islam, Farhan Tanvir, Ginger Johnson, Esra Akbas, and Mehmet Emin Aktas. 2021\.  Proximity-based compression for network embedding.  _Frontiers in big Data_ 3 (2021), 608043.
  * Kim et al. ([n.d.]) Eun-Sol Kim, † Woo, Young Kang, Kyoung-Woon On, Yu-Jung Heo, Byoung-Tak Zhang, and Kakao Brain. [n.d.].  Hypergraph Attention Networks for Multimodal Learning.  ([n. d.]).  https://spacy.io/
  * Kipf and Welling (2016) Thomas N. Kipf and Max Welling. 2016.  Semi-Supervised Classification with Graph Convolutional Networks.  _5th International Conference on Learning Representations, ICLR 2017 - Conference Track Proceedings_ (9 2016).  https://doi.org/10.48550/arxiv.1609.02907
  * Kuzmin et al. (2020) Kiril Kuzmin, Ayotomiwa Ezekiel Adeniyi, Arthur Kevin DaSouza, Deuk Lim, Huyen Nguyen, Nuria Ramirez Molina, Lanqiao Xiong, Irene T. Weber, and Robert W. Harrison. 2020.  Machine learning methods accurately predict host specificity of coronaviruses based on spike sequences alone.  _Biochemical and Biophysical Research Communications_ 533 (12 2020), 553–558.  Issue 3. https://doi.org/10.1016/J.BBRC.2020.09.010
  * Leslie et al. (2001) Christina Leslie, Eleazar Eskin, and William Stafford Noble. 2001\.  The spectrum kernel: A string kernel for SVM protein classification.  In _Biocomputing 2002_. World Scientific, 564–575.
  * Min et al. (2017) Xu Min, Wanwen Zeng, Ning Chen, Ting Chen, and Rui Jiang. 2017.  Chromatin accessibility prediction via convolutional long short-term memory networks with k-mer embedding.  _Bioinformatics (Oxford, England)_ 33 (7 2017), i92–i101.  Issue 14. https://doi.org/10.1093/BIOINFORMATICS/BTX234
  * Nguyen et al. (2016) Ngoc Giang Nguyen, Vu Anh Tran, Duc Luu Ngo, Dau Phan, Favorisen Rosyking Lumbanraja, Mohammad Reza Faisal, Bahriddin Abapihi, Mamoru Kubo, Kenji Satou, Ngoc Giang Nguyen, Vu Anh Tran, Duc Luu Ngo, Dau Phan, Favorisen Rosyking Lumbanraja, Mohammad Reza Faisal, Bahriddin Abapihi, Mamoru Kubo, and Kenji Satou. 2016\.  DNA Sequence Classification by Convolutional Neural Network.  _Journal of Biomedical Science and Engineering_ 9 (4 2016), 280–286.  Issue 5. https://doi.org/10.4236/JBISE.2016.95021
  * Nigam et al. (2000) Kamal Nigam, Andrew Kachites Mccallum, Sebastian Thrun, and Tom Mitchell. 2000\.  Text Classification from Labeled and Unlabeled Documents using EM.  _Machine Learning 2000 39:2_ 39 (2000), 103–134.  Issue 2. https://doi.org/10.1023/A:1007692713085
  * Parks et al. (2011) Donovan H. Parks, Norman J. MacDonald, and Robert G. Beiko. 2011.  Classifying short genomic fragments from novel lineages using composition and homology.  _BMC Bioinformatics_ 12 (8 2011), 1–16.  Issue 1. https://doi.org/10.1186/1471-2105-12-328/FIGURES/7
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ 12 (2011), 2825–2830.
  * Qian (2019) Yujie. Qian. 2019\.  A graph-based framework for information extraction.  (2019).  https://dspace.mit.edu/handle/1721.1/122765
  * Quek et al. (2011) Alyssa Quek, Zhiyong Wang, Jian Zhang, and Dagan Feng. 2011\.  Structural image classification with graph neural networks.  _Proceedings - 2011 International Conference on Digital Image Computing: Techniques and Applications, DICTA 2011_ (2011), 416–421.  https://doi.org/10.1109/DICTA.2011.77
  * Radicioni and Esposito (2010) Daniele P. Radicioni and Roberto Esposito. 2010.  BREVE: An HMPerceptron-based chord recognition system.  _Studies in Computational Intelligence_ 274 (2010), 143–164.  https://doi.org/10.1007/978-3-642-11674-2_7
  * Raj and Mahalekshmi (2018) N. Nijil Raj and T. Mahalekshmi. 2018.  Multilabel classification of membrane protein in human by decision tree(DT) Approach.  _Biomedical and Pharmacology Journal_ 11 (2018), 113–121.  Issue 1. https://doi.org/10.13005/BPJ/1353
  * Rätsch et al. (2006) Gunnar Rätsch, Sören Sonnenburg, and Christin Schäfer. 2006\.  Learning interpretable SVMs for biological sequence classification.  _BMC Bioinformatics_ 7 (3 2006), 1–14.  Issue SUPPL.1. https://doi.org/10.1186/1471-2105-7-S1-S9/FIGURES/7
  * Sahlin (2021) Kristoffer Sahlin. 2021\.  Strobemers: an alternative to k-mers for sequence comparison.  _bioRxiv_ (2021), 2021–01.
  * Saifuddin et al. (2021) Khaled Mohammed Saifuddin, Muhammad Ifte Khairul Islam, and Esra Akbas. 2021.  Drug Abuse Detection in Twitter-sphere: Graph-Based Approach.  _Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021_ (2021), 4136–4145.  https://doi.org/10.1109/BIGDATA52589.2021.9671532
  * Saigo et al. (2004) Hiroto Saigo, Jean Philippe Vert, Nobuhisa Ueda, and Tatsuya Akutsu. 2004.  Protein homology detection using string alignment kernels.  _Bioinformatics (Oxford, England)_ 20 (7 2004), 1682–1689.  Issue 11. https://doi.org/10.1093/BIOINFORMATICS/BTH141
  * Schölkopf et al. (2004) Bernhard Schölkopf, Koji Tsuda, and Jean-Philippe Vert. 2004\.  _Kernel methods in computational biology_.  MIT press.
  * She et al. (2003) Rong She, Fei Chen, Ke Wang, Martin Ester, Jennifer L Gardy, and Fiona S L Brinkman. 2003.  Frequent-Subsequence-Based Prediction of Outer Membrane Proteins *.  (2003).  http://www.psort.org/dataset
  * Tanvir et al. (2022) Farhan Tanvir, Khaled Mohammed Saifuddin, and Esra Akbas. 2022.  DDI Prediction via Heterogeneous Graph Attention Networks.  (7 2022).  https://doi.org/10.48550/arxiv.2207.05672
  * Timmons and Hewage (2021) Patrick Brendan Timmons and Chandralal M. Hewage. 2021.  ENNAACT is a novel tool which employs neural networks for anticancer activity classification for therapeutic peptides.  _Biomedicine & pharmacotherapy = Biomedecine & pharmacotherapie_ 133 (1 2021).  https://doi.org/10.1016/J.BIOPHA.2020.111051
  * Torrisi et al. (2020) Mirko Torrisi, Gianluca Pollastri, and Quan Le. 2020\.  Deep learning methods in protein structure prediction.  _Computational and Structural Biotechnology Journal_ 18 (1 2020), 1301–1310.  https://doi.org/10.1016/J.CSBJ.2019.12.011
  * Turner et al. ([n.d.]) Isaac Turner, Kiran V Garimella, Zamin Iqbal, and Gil Mcvean. [n.d.].  Integrating long-range connectivity information into de Bruijn graphs.  ([n. d.]).  https://doi.org/10.1093/bioinformatics/bty157
  * UCI ([n.d.]) UCI. [n.d.].  UCI Machine Learning Repository: Data Sets.  https://archive.ics.uci.edu/ml/datasets.php?format=&task=&att=&area=&numAtt=&numIns=&type=seq&sort=nameUp&view=table
  * Wang et al. (2019) Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. 2019.  Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks.  (9 2019).  https://doi.org/10.48550/arxiv.1909.01315
  * Wu et al. (2020) Xiangping Wu, Qingcai Chen, Wei Li, Yulun Xiao, and Baotian Hu. 2020.  AdaHGNN: Adaptive Hypergraph Neural Networks for Multi-Label Image Classification.  _MM 2020 - Proceedings of the 28th ACM International Conference on Multimedia_ (10 2020), 284–293.  https://doi.org/10.1145/3394171.3414046
  * Xie et al. (2020) Mingfeng Xie, Dijia Liu, and Yufeng Yang. 2020.  Anti-cancer peptides: classification, mechanism of action, reconstruction and modification.  _Open Biology_ 10 (7 2020).  Issue 7. https://doi.org/10.1098/RSOB.200004
  * XingZhengzheng et al. (2010) XingZhengzheng, PeiJian, and KeoghEamonn. 2010.  A brief survey on sequence classification.  _ACM SIGKDD Explorations Newsletter_ 12 (11 2010), 40–48.  Issue 1. https://doi.org/10.1145/1882471.1882478
  * Yao et al. ([n.d.]) Liang Yao, Chengsheng Mao, and Yuan Luo. [n.d.].  Graph Convolutional Networks for Text Classification.  ([n. d.]).  www.aaai.org
  * Zhang et al. (2017) Jingsong Zhang, Jianmei Guo, Xiaoqing Yu, Xiangtian Yu, Weifeng Guo, Tao Zeng, and Luonan Chen. 2017.  Mining k-mers of various lengths in biological sequences. In _Bioinformatics Research and Applications: 13th International Symposium, ISBRA 2017, Honolulu, HI, USA, May 29–June 2, 2017, Proceedings 13_. Springer, 186–195.
  * Zhang et al. ([n.d.]) Yufeng Zhang, Xueli Yu, Zeyu Cui, Shu Wu, Zhongzhen Wen, and Liang Wang. [n.d.].  Every Document Owns Its Structure: Inductive Text Classification via Graph Neural Networks.  ([n. d.]).  https://github.com/CRIPAC-DIG/TextING
  * Zola (2014) Jaroslaw Zola. 2014\.  Constructing similarity graphs from large-scale biological sequence collections. In _2014 IEEE International Parallel & Distributed Processing Symposium Workshops_. IEEE, 500–507.