# Semantic Textual Similarity Assessment in Chest X-ray Reports Using a
Domain-Specific Cosine-Based Metric

Sayeh GHOLIPOUR PICHA
Univ. Grenoble Alpes,
CNRS, Grenoble INP, GIPSA-lab,
38000 Grenoble, France
<EMAIL_ADDRESS>
& Dawood AL CHANTI
Univ. Grenoble Alpes,
CNRS, Grenoble INP, GIPSA-lab,
38000 Grenoble, France
<EMAIL_ADDRESS>
& Alice CAPLIER
Univ. Grenoble Alpes,
CNRS, Grenoble INP, GIPSA-lab,
38000 Grenoble, France
<EMAIL_ADDRESS>

(February, 2024)

###### Abstract

Medical language processing and deep learning techniques have emerged as
critical tools for improving healthcare, particularly in the analysis of
medical imaging and medical text data. These multimodal data fusion techniques
help to improve the interpretation of medical imaging and lead to increased
diagnostic accuracy, informed clinical decisions, and improved patient
outcomes. The success of these models relies on the ability to extract and
consolidate semantic information from clinical text. This paper addresses the
need for more robust methods to evaluate the semantic content of medical
reports. Conventional natural language processing approaches and metrics are
initially designed for considering the semantic context in the natural
language domain and machine translation, often failing to capture the complex
semantic meanings inherent in medical content. In this study, we introduce a
novel approach designed specifically for assessing the semantic similarity
between generated medical reports and the ground truth. Our approach is
validated, demonstrating its efficiency in assessing domain-specific semantic
similarity within medical contexts. By applying our metric to state-of-the-art
Chest X-ray report generation models, we obtain results that not only align
with conventional metrics but also provide more contextually meaningful scores
in the considered medical domain.

_Keywords_ Semantic Similarity, Medical Language Processing, Biomedical Metric

##  1 INTRODUCTION

Advancements in deep learning for medical language processing have
significantly improved healthcare clinical analysis, particularly in the
domain of medical imaging applications. Notably, there has been substantial
progress in generating chest X-ray reports comparable to those written by
radiologists. However, a critical challenge persists in the chest X-ray
application—assessing the semantic similarity between generated reports and
the ground truth.

Identifying semantic similarities in medical texts is a difficult task within
the language processing domain Alam et al. (2020). This task necessitates a
comprehensive grasp of the entire medical text corpus, the ability to
recognize key content, and a profound understanding of the semantic
relationships between these critical keywords at an expert level. While
existing metrics and approaches for capturing semantic similarity in natural
language are effective, they are not designed for the complexities of medical
content. The need for a robust metric to assess semantic similarity in medical
texts has become increasingly evident, particularly in applications like chest
X-ray report generation, and continues to be an active area of research Endo
et al. (2021), Miura et al. (2021), Yu et al. (2022).

State-of-the-art chest X-ray report generation models Chen et al. (2020),
Miura et al. (2021), Endo et al. (2021) still rely on conventional Natural
Language Processing (NLP) methods like BLEU Papineni et al. (2002), METEOR
Banerjee and Lavie (2005), and ROUGE Lin (2004) to evaluate the generated
reports against ground truth references. However, these metrics produce
unreliable results due to their inability to comprehend and compare the
semantic similarity of key medical terms. A medical semantic similarity metric
would not only provide more significant evaluation scores but could also be
incorporated into the training process to improve model performance,
potentially leading to enhanced diagnostic accuracy and decision-making.
Additionally, as part of our ongoing research, our goal is to focus on
providing visual interpretations of chest X-ray reports using text-to-image
localization. As a consequence, a robust semantic similarity evaluation metric
suitable for medical content will ensure the reliability of generated reports
and will enable us to achieve more accurate localization and interpretation of
image content.

In this context, we propose a new metric designed to assess and assign scores
about the semantic similarity of medical texts. Our metric consists of two
sequential steps: first, we identify the primary clinical entities, and
subsequently, we evaluate the similarity between these entities using the
domain-specific Cosine similarity score. Notably, our approach considers the
presence of negations and detailed descriptions associated with medical
entities during the evaluation process. To this end, our contributions
include:

  * •

Introduction of a novel system for clinical entity extraction from medical
texts.

  * •

Proposition of a new scoring system for the evaluation of semantic similarity
that suits medical and natural texts.

  * •

Presentation of a validation method for scoring verification.

This paper is structured as follows: Section 2 discusses related works;
Section 3 presents the theoretical and mathematical part of the novel metric;
Section 4 validates the metric; Section 5 discusses the results; Finally,
Section 6 concludes the paper.

##  2 RELATED WORKS

Recent studies have addressed the challenge of similarity evaluation between
generated medical reports and the ground truth through various approaches
other than conventional NLP metrics. Researchers have often introduced
innovative metrics in the process.

In the CXR-RePaiR model by Endo et al. Endo et al. (2021) a unique approach
for automatically evaluating chest X-ray report generation is proposed by
introducing the CheXbert vector similarity metric, using the CheXbert labeler
Smit et al. (2020) — a specialized tool for chest X-ray report labeling. The
process involves extracting labels from generated reports, comparing them with
ground truth labels, and presenting the final score using cosine similarity.
While this approach outperforms the BLEU metric, its applicability is limited
to the specific context of chest X-ray reports and does not readily extend to
other medical applications. The limitations arise from Chexbert being
exclusively trained for chest X-ray reports. Moreover, the Chexpert labels
Irvin et al. (2019) (Atelectasis, Cardiomegaly, Consolidation, Edema, Enlarged
Cardiomediastinum, Fracture, Lung Lesion, Lung Opacity, No Finding, Pleural
Effusion, Pleural Other, Pneumonia, Pneumothorax) are specific to the chest
X-ray dataset, further limiting the generalizability of the approach to other
medical contexts.

In a separate study, Yu et al. Yu et al. (2022) introduced a novel metric
targeting the quantification of overlap of clinical entities between ground
truth and generated reports in chest X-ray report generation. They use the
RadGraph model Jain et al. (2021), a language model trained on a limited
subset of reports from the MIMIC-CXR dataset Johnson et al. (2019). The MIMIC-
CXR dataset consists of chest X-ray images with corresponding reports, and the
RadGraph dataset includes medical entities from chest X-ray reports annotated
by radiologists. The approach by Yu et al. is similar to the BLEU score,
exclusively considering the exact matches among the primary entities in
generated and ground truth reports, overlooking the semantic similarity of
these entities. Furthermore, the generalizability of this approach to other
medical applications is constrained by the RadGraph model’s specialization in
extracting only chest X-ray related entities. Nonetheless, while the RadGraph
model acknowledges negations in the texts, they are treated merely as labels
to the entities, and the details of entity descriptions are not factored into
the evaluation process.

In a recent study, Patricoski et al. Patricoski et al. (2022) conducted an
evaluation of seven BERT models to assess semantic similarity in clinical
trial texts. Notably, the pre-trained BERT model known as SciBERT Beltagy et
al. (2019) demonstrated better performance compared to the other BERT models,
even outperforming the standard BERT model, which secured the second position
in this evaluation. This study underlines the promising potential of BERT
models in semantic similarity evaluation. However, it has a drawback
associated with using BERT models without preprocessing. BERT models operate
at a token-by-token level, evaluating semantic similarity by comparing all
tokens with each other, a computationally intensive process that gives
relatively low scores. Despite this computational challenge, it is important
to consider the significant potential in SciBERT, particularly due to its huge
clinical dictionary. This finding underscores the need for careful
consideration of preprocessing strategies to maximize the effectiveness of
BERT models in semantic similarity evaluations.

Notably, the absence of a comprehensive, general semantic similarity
evaluation metric for medical content persists. Consequently, we introduce a
novel metric for Medical Corpus Similarity Evaluation (MCSE) to
comprehensively address and resolve these challenges.

##  3 METHODOLOGY

We developed a novel metric for Medical Corpus Similarity Evaluation (MCSE),
by exclusively extracting key medical entities and employing a pretrained BERT
model to assess the semantic similarity of these entities within chest X-ray
reports. This targeted approach allows BERT to concentrate solely on important
information and reduces the computational load during comparison. Importantly,
our methodology goes beyond extracting main entities, we also consider the
negations and detailed descriptions associated with the primary medical
entities in chest X-ray reports. Our MCSE metric consists of two essential
steps:

  1. 1.

Clinical Entity Extraction.

  2. 2.

Domain Similarity Evaluation.

###  3.1 Clinical Entity Extraction

The most important part of comprehending semantic similarity evaluation in
text relies on identifying the key elements, often referred to as clinical
entities, within medical texts. These entities typically fall into categories
related to anatomical body parts, symptoms, laboratory equipment, and
diagnoses. Each category is typically signaled by certain words within a
sentence. However, there are additional words that precede or follow these
main entities, offering descriptions.

To address these complexities, we employ the Scispacy model Neumann et al.
(2019) for extracting primary clinical entities from medical text using the
embedded clinical dictionary in this model (BC5CDR: a corpus comprising 1500
PubMed articles with 4409 annotated chemicals, 5818 diseases, and 3116
chemical-disease interactions Li et al. (2016)). Subsequently, we
automatically process the entire text to identify associated negations and
adjectives related to these key entities. These elements are then integrated
to provide a comprehensive representation of the considered text. In the
context of this research, the category of laboratory equipment is deliberately
excluded, aligning with the specific focus of our application. Table 1
presents an example of medical text and the extracted entities using our
method and the Scispacy method without any cleaning process. While we employ
the Scispacy model for initial entity extraction, it is evident that this
model alone may not suffice. An additional automated post-processing step is
needed to refine and integrate related entities. The post-processing steps
involve eliminating a single adjective or non-medical entities, excluding
entities categorized as lab equipment, identifying and adding the relevant
adjective to the remaining medical entities, including the existing negation
into these primary entities, and screening out any reported diagnostic
procedures terms. These processes are essential to ensure that the final
output is presented as a cohesive set of primary medical entities, ready for
practical use.

Table 1: In the right column there is an example of medical text. In the left column, there are clinical entities extracted using the Scispacy model without any cleaning process, and In the middle column, there are clinical entities extracted using our method. Medical Text |  Extracted Entities using our method |  Extracted Entities using Scispacy Neumann et al. (2019)
---|---|---
1\. Interval clearance of left basilar consolidation. 2. Patchy right basilar opacities, which could be seen with minor atelectasis, but given the context clinical correlation is suggested regarding any possibility for recurrent or new aspiration pneumonitis at the right lung base. 3. Increased new interstitial abnormality, suggesting recurrence of fluid overload or mild-to-moderate pulmonary edema; aspiration could also be considered. Inflammation associated with atypical infectious process is probably less likely given the waxing and waning presentation. |  fluid overload, inflammation, aspiration pneumonitis, minor atelectasis, mild to moderate pulmonary edema, left basilar consolidation, patchy right basilar opacities, interstitial abnormality |  Interval, clearance, left basilar, consolidation, Patchy, right basilar, opacities, minor, atelectasis, clinical, recurrent, aspiration, pneumonitis, right lung base, Increased, interstitial abnormality, recurrence, fluid, overload, mild-to-moderate pulmonary edema, aspiration, Inflammation, associated with, atypical, infectious process, waxing, waning, presentation

###  3.2 Domain Similarity Evaluation

Having successfully extracted and shifted our focus to the primary entities
within the medical corpus, the next step involves assessing their semantic
similarities by assigning corresponding scores.

After processing entity extraction, we calculate a similarity score for the
sequences of entities. Let $T=(t_{1},\dots,t_{N})$ represent the reference
text entities and $\hat{T}=(\hat{t}_{1},\dots,\hat{t}_{M})$ represent the
generated text or candidate text entities. Initially, we identify the exact
same medical entities in both sequences and determine the total count
($|C^{(i)}|$). For the remaining entities, we construct a similarity matrix,
where each element represents the similarity score between entities, as
illustrated in table 2.

$\displaystyle S_{i}=\frac{\max y_{i,j}}{\max
y_{i,j}+\overline{y_{i,j}}}\mkern 12.0mui=(0,1,\dots,M)\mkern
3.0muj=(0,1,\dots,N)$ (1) $\displaystyle
y_{i,j}=Similarity(r_{i},\hat{r}_{j})$ (2)
$\begin{cases}C^{(i)}=t_{i},&\text{if }t_{i}=\hat{t}_{j}\\\
r_{i}=t_{i}\And\hat{r}_{j}=\hat{t}_{j}&\text{if
}t_{i}\neq\hat{t}_{j}\end{cases}$ (3)

Where $M$ is the number of total candidate entities, $r_{i}$ and $\hat{r}_{j}$
are the sequence between no matched entities as in equation (3), and $S_{i}$
is a normalized similarity score between $r_{i}$ and $\hat{r}_{j}$. The
similarity score $Similarity(r_{i},\hat{r}_{j})$ in equation (2) is derived
from spaCy Honnibal et al. (2020), a BERT model trained on word2vec, to
evaluate similarities using domain cosine similarity.

To evaluate the similarity of candidate entities with the reference entities,
we compute the maximum score for each column and normalized it with the
column’s average ($S_{i}$). We then sum these scores for each column, adding
them to $|C^{(i)}|$. To obtain the final similarity score between the two
corpora, we divide this sum by the total number of candidate entities. This
process is explained in Equation (4).

$MCSE:=\frac{|C^{(i)}|+\sum_{i=1}^{M}S_{i}}{M}$ (4)

Where $|C^{(i)}|$ is the number of exactly matched entities between the two
corpora of $T$ and $\hat{T}$.

For instance, Table 2 provides an example of the probable similarity score
that two sets of entities can receive. These entities have been extracted
using our medical entity extraction procedure.

In the table, the two corpora received a score of 0.55 according to our MCSE
metric. However, the calculated BLEU score for them is approximately zero.
Upon analyzing the two medical texts, it becomes evident that although the
candidate text does refer to the same side of the chest as in the reference
text and that both texts indicate the presence of pulmonary edema and
pulmonary masses, their overall similarity is relatively limited. The score of
0.55 carries a more meaningful value in this context compared to the nearly
zero score generated by BLEU.

Table 2: An example of a medical similarity score between entities. Each score
is calculated from equation (2), with the final row $S_{i}$ being computed
using equation (1). The scores highlighted in blue indicate the maximum value
within each respective column. Reference: 1\. Interval clearance of left
basilar consolidation. 2. Patchy right basilar opacities, which could be seen
with minor atelectasis, but given the context clinical correlation is
suggested regarding any possibility for recurrent or new aspiration
pneumonitis at the right lung base. 3. Increased new interstitial abnormality,
suggesting recurrence of fluid overload or mild-to-moderate pulmonary edema;
aspiration could also be considered. Inflammation associated with atypical
infectious process is probably less likely given the waxing and waning
presentation.
---
Candidate: Stable multiple bilateral pulmonary masses and right middle lobe
collapse due to hilar adenopathy.
| Candidate Medical Entities
| pulmonary masses | right middle lobe | hilar adenopathy
|  fluid overload | 0.61 | 0.49 | 0.45
|  inflammation | 0.64 | 0.48 | 0.55
|  aspiration pneumonitis | 0.65 | 0.39 | 0.50
|  minor atelectasis | 0.62 | 0.47 | 0.53
Reference Medical Entities |  mild to moderate pulmonary edema | 0.78 | 0.31 | 0.51
|  left basilar consolidation | 0.52 | 0.66 | 0.32
|  patchy right basilar opacities | 0.64 | 0.66 | 0.49
|  interstitial abnormality | 0.69 | 0.63 | 0.59
$S_{i}$ | 0.548 | 0.563 | 0.545

##  4 VALIDATION

While the underlying logic of this metric is reasonable, it is imperative that
we validate the results robustly. Given the use of chest X-ray reports for
this particular application, we have conducted an extensive search within
existing datasets to identify an appropriate validation method. After a
comprehensive review of various datasets, we concluded that it would be more
effective to conduct separate validations for the different steps of the
proposed metric.

###  4.1 Clinical Entity Extraction Process

In order to rigorously validate our clinical entity extraction process, we
employ the RadGraph dataset Jain et al. (2021). This dataset is a valuable
resource in which radiologists thoroughly annotated the primary clinical
entities in chest X-ray reports as either "definitely present" within the
report or "definitely absent". Importantly, in cases where a negation is
associated with a particular entity, it is annotated as "definitely absent."

To achieve our validation objectives, we executed our entity extraction
process on the reports within this dataset. Subsequently, we compare the
number of similar entities extracted through our method with the annotations
provided by radiologists, particularly focusing on the two categories of
"definitely present" and "definitely absent". This systematic comparison
allows us to assess the accuracy and effectiveness of our clinical entity
extraction methodology in the context of chest X-ray reports, aligning with
radiological standards. Throughout the validation process, covering all
reports in our study, our method consistently achieves a high level of
accuracy. On average, it accurately recognizes 75% of entities marked as
"definitely present" and successfully identifies 76% of entities labeled as
"definitely absent". In our entity extraction process, we deliberately omit
anatomical entities like "chest" or "lung," as they are redundant to the chest
X-ray application and do not contribute significantly to the process. This
selective exclusion is one of the factors contributing to the approximately
75% accuracy in our results. Nevertheless, these results affirm the
reliability and consistency of our methodology.

###  4.2 Domain Similarity Score

In contrast to the initial phase of clinical entity extraction, validating the
domain similarity score is more challenging. The scoring system itself is more
controversial and subject to debate, and creating an automated validation
method, free from reliance on radiologists, necessitates a creative and
innovative approach. Nevertheless, through the available tools and databases,
we establish a dedicated system for the validation of this scoring method for
the application of chest X-rays.

In the chest X-ray application, the MIMIC-CXR dataset Johnson et al. (2019),
is one of the biggest available databases for chest X-ray images and their
corresponding reports. Notably, this dataset provides us with Chexpert labels
(Medical Observation), including Atelectasis, Cardiomegaly, Consolidation,
Edema, Enlarged Cardiomediastinum, Fracture, Lung Lesion, Lung Opacity, No
Finding, Pleural Effusion, Pleural Other, Pneumonia, Pneumothorax, and Support
Devices labels Irvin et al. (2019). The values of each label are 1 (definitely
present), 0 (definitely absent), -1 (ambiguous), or it carries no value at
all. Table 3 presents a sample of Chexpert labels extracted from chest X-ray
reports of five patients from the MIMIC-CXR database. The reports
corresponding to these subjects are presented in Table 4.

Table 3: A sample table featuring Chexpert labels (1. Atelectasis, 2.
Cardiomegaly, 3. Consolidation, 4. Edema, 5. Enlarged Cardiomediastinum, 6.
Fracture, 7. Lung Lescion, 8. Lung Opacity, 9. No Finding, 10. Pleural
Effusion, 11. Pleural Other, 12. Pneumonia, 13. Pneumothorax, 14. Support
Devices) extracted from chest X-ray reports of five patients (Subject ##) from
the MIMIC-CXR database Johnson et al. (2019).

Subject ## Atelectasis Cardiomegaly Consolidation Edema Enlarged
Cardiomediastinum Fracture Lung Lescion Lung Opacity No Finding Pleural
Effusion Pleural Other Pneumonia Pneumothorax Support Devices 01 0 1 1 -1 02 1
1 03 1 0 04 1 0 -1 0 1 05 1 1

Table 4: Reports corresponding to the subjects listed in Table 3 from the MIMIC-CXR dataset Johnson et al. (2019). Subject_## |  Report
---|---
01 |  Lung volumes remain low. There are innumerable bilateral scattered small pulmonary nodules which are better demonstrated on recent CT. Mild pulmonary vascular congestion is stable. The cardio mediastinal silhouette and hilar contours are unchanged. Small pleural effusion in the right middle fissure is new. There is no new focal opacity to suggest pneumonia. There is no pneumothorax.
02 |  A triangular opacity in the right lung apex is new from prior examination. There is also fullness of the right hilum which is new. The remainder of the lungs are clear. Blunting of bilateral costophrenic angles, right greater than left, may be secondary to small effusions. The heart size is top normal.
03 |  Mild to moderate enlargement of the cardiac silhouette is unchanged. The aorta is calcified and diffusely tortuous. The mediastinal and hilar contours are otherwise similar in appearance. There is minimal upper zone vascular redistribution without overt pulmonary edema. No focal consolidation, pleural effusion or pneumothorax is present. The osseous structures are diffusely demineralized.
04 |  The endotracheal tube tip is 6 cm above the carina. Nasogastric tube tip is beyond the GE junction and off the edge of the film. A left central line is present in the tip is in the mid SVC. A pacemaker is noted on the right in the lead projects over the right ventricle. There is probable scarring in both lung apices. There are no new areas of consolidation. There is upper zone redistribution and cardiomegaly suggesting pulmonary venous hypertension. There is no pneumothorax.
05 |  A moderate left pleural effusion is new. Associated left basilar opacity likely reflect compressive atelectasis. There is no pneumothorax. There are no new abnormal cardiac or mediastinal contour. Median sternotomy wires and mediastinal clips are in expected positions.

Our approach involves two distinct strategies. Firstly, we seek to identify
reports sharing the same sequence of labels and values. For instance, we
search for reports from subjects with Chexpert label sequences similar to that
of Subject_01 in Table 3. For these reports with matching label sequences, we
proceed to similarity scores computation for each pair of reports.
Simultaneously, we identify reports featuring only one or two labels and with
a value of "definitely present" for these labels resembling Subject_02 in
Table 3 and assess the similarity of these reports with the reports with
different label sequences. As an example, we calculate the similarity between
the reports of Subject_02 and Subject_05 from Table 3, given their entirely
distinct label sequences. This two-fold method allows us to analyze the
semantic similarity scores for both similar and contrasting reports in terms
of their labels.

Figure 1: Semantic Evaluation of Chest X-ray reports. Each blue dot represents
the mean score of semantic evaluation for reports with similar label
sequences, while each orange dot signifies the mean score of semantic
evaluation for reports with opposing labels. The red horizontal line
represents the classification boundary.

Figure 1 presents the results of the two-fold validation for our scoring
method. Within the figure, blue dots represent the average scores for semantic
evaluation of reports with similar label sequences, while orange dots show the
mean scores for reports with contrasting labels. The red horizontal line
within the figure serves as the dividing line distinguishing between similar
and opposite evaluations. Upon reviewing these results, it becomes evident
that a distinct boundary exists between reports sharing the same clinical
diagnoses and those with entirely dissimilar diagnoses. Notably, there are no
blue dots below a 70% similarity threshold, whereas six orange dots have
scores above 70% across 70 label sequences, which is certainly not very high.
Nevertheless, despite this differentiation between similar and opposite
evaluations, some level of similarity, exceeding 50%, persists within the
opposing category. This can be attributed to the implemented cosine similarity
within the medical domain, which introduces a certain bias towards tokens in
the same medical domain. Unfortunately, this bias cannot be entirely
eliminated, as it plays a substantial role in the evaluation process. However,
a clear boundary remains between similar and contrasting reports.

##  5 RESULTS AND DISCUSSION

In our original application of chest X-ray report generation, we incorporate
our metric to assess the outputs of various models. We compare our results
with the BLEU scores evaluated by these models, specifically, the CXR-RePaiR
Endo et al. (2021) and R2Gen Chen et al. (2020) models, both being state-of-
the-art models for generating chest X-ray reports. Our evaluation focuses on
measuring the semantic similarity between the generated reports and the ground
truth. Table 5 presents the BLEU scores obtained from these models and our
metric’s semantic evaluation. As anticipated, the BLEU scores are relatively
low, signifying a substantial dissimilarity between the generated results and
the ground truth for both the CXR-RePaiR and R2Gen models despite being
regarded as state-of-the-art models for chest X-ray report generation. These
models still employ the BLEU metric for evaluation, primarily due to the
scarcity of more suitable metrics and the need for a standardized evaluation
process for comparative purposes. Conversely, our metric produces more
promising results for both of these models. While our metric’s scores align
with the BLEU scores, indicating higher scores for both BLEU and our MCSE
metric in the case of the R2Gen model compared to the CXR-RePaiR, our metric
provides a deeper evaluation. It suggests a degree of similarity to the ground
truth rather than outright dissimilarity in BLEU, thus making the generated
reports more reliable and trustworthy, which is a crucial advancement in the
field.

Table 5: The result of BLEU score of 2-gram for state-of-the-art models and the result of our novel metric on these models outcomes. Models | BLEU | Our MCSE
---|---|---
R2Gen Chen et al. (2020) | 0.212 | 0.71
CXR-RePair Endo et al. (2021) | 0.069 | 0.64

Table 6 provides an example of medical text generated and evaluated using both
a BLEU score and our MCSE metric. It’s evident that, according to the BLEU
score, these two texts appear vastly different, even though they share the
same primary medical entities. However, when we delve into the context, we can
notice that "moderately severe" serves as a description for the main entity,
"pulmonary edema", in the generated text. Similarly, in the second part of the
text, the main medical entity is "pleural effusions", and terms like "likely"
and "no large" are used to describe this entity, which may not be identical
but share semantic similarities. This subtle context evaluation is precisely
what our metric considers, yielding a similarity score of 0.64 for these
texts, which we argue is a more accurate reflection compared to the BLEU
score.

Table 6: A comparative example of using the BLEU score and our adapted metric with medical reference and generated text. | BLEU | MCSE
---|---|---
Reference Sentence: "Pulmonary edema, cardiomegaly, likely pleural effusions." Generated Sentence: "Moderately severe bilateral pulmonary edema with no large pleural effusion." | 0.047 | 0.64

Lastly, the significant benefit of employing this metric lies in its capacity
for comparative analysis alongside other evaluation measures. For instance,
when examining the outcomes of the BLEU score, with its word-by-word analysis,
situations may arise where the results are totally inaccurate, casting doubt
on their reliability, despite the models performing well overall. Integrating
the results of our novel MCSE metric into the evaluation process allows us to
semantically analyze and ascertain the dependability of the models’ textual
outputs within the context of medical content.

##  6 CONCLUSION

In our research, we tackle the challenge of semantic similarity scoring in
medical corpora, driven by the inadequacy of existing metrics that, while
suitable for machine translation evaluation, fall short in the field of
medical semantic assessment. Our innovative metric draws inspiration from how
humans comprehend text, centering on the extraction of key terms and their
relational context. It introduces a novel approach for extracting clinical
entities from medical text, considering not only the entities themselves but
also the associated descriptions and negations. Additionally, we created a new
method for scoring the semantic relationships between these entities by using
the domain cosine similarity. The validation process allowed us to analyze and
validate each of these steps individually, unraveling a clear distinction
between reports sharing the same diagnosis and those diverging in this regard.

For our research, we focused on the application of chest X-rays, a critical
domain where a robust semantic evaluation metric is highly valuable. We
applied our metric to some of the latest state-of-the-art models, and the
results harmonized with other evaluation metrics, affirming their reliability.

While our validation process and implementation yielded successful outcomes,
we encountered the challenge of an inherent bias in domain cosine similarity.
This challenge has illuminated a promising direction for our future research,
as we explore ways to mitigate this bias and advance the field of medical
semantic evaluation.

#### Material, codes, and Acknowledgement:

Results can be reproduced using the code available in the GitHub repository
https://github.com/sayeh1994/Medical-Corpus-Semantic-Similarity-
Evaluation.git. All the computations presented in this paper were performed
using the Gricad  infrastructure (https://gricad.univ-grenoble-alpes.fr),
which is supported by Grenoble research communities.

## References

  * Alam et al. [2020] Fakhare Alam, Muhammad Afzal, and Khalid Mahmood Malik.  Comparative analysis of semantic similarity techniques for medical text.  In _2020 International Conference on Information Networking (ICOIN)_ , pages 106–109, 2020.  doi:10.1109/ICOIN48656.2020.9016574.
  * Endo et al. [2021] Mark Endo, Rayan Krishnan, Viswesh Krishna, Andrew Y. Ng, and Pranav Rajpurkar.  Retrieval-based chest x-ray report generation using a pre-trained contrastive language-image model.  In _Proceedings of Machine Learning for Health_ , volume 158 of _Proceedings of Machine Learning Research_ , pages 209–219, 2021.
  * Miura et al. [2021] Yasuhide Miura, Yuhao Zhang, Emily Tsai, Curtis Langlotz, and Dan Jurafsky.  Improving factual completeness and consistency of image-to-text radiology report generation.  In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5288–5304, Online, June 2021. Association for Computational Linguistics.  doi:10.18653/v1/2021.naacl-main.416.  URL https://aclanthology.org/2021.naacl-main.416.
  * Yu et al. [2022] Feiyang Yu, Mark Endo, Rayan Krishnan, Ian Pan, Andy Tsai, Eduardo Pontes Reis, Eduardo Kaiser Ururahy Nunes Fonseca, Henrique Min Ho Lee, Zahra Shakeri Hossein Abad, Andrew Y. Ng, Curtis P. Langlotz, Vasantha Kumar Venugopal, and Pranav Rajpurkar.  Evaluating Progress in Automatic Chest X-Ray Radiology Report Generation.  preprint, Radiology and Imaging, August 2022.  URL http://medrxiv.org/lookup/doi/10.1101/2022.08.30.22279318.
  * Chen et al. [2020] Zhihong Chen, Yan Song, Tsung-Hui Chang, and Xiang Wan.  Generating radiology reports via memory-driven transformer.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1439–1449, Online, November 2020. Association for Computational Linguistics.  doi:10.18653/v1/2020.emnlp-main.112.  URL https://aclanthology.org/2020.emnlp-main.112.
  * Papineni et al. [2002] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics.  doi:10.3115/1073083.1073135.  URL https://aclanthology.org/P02-1040.
  * Banerjee and Lavie [2005] Satanjeev Banerjee and Alon Lavie.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72, Ann Arbor, Michigan, June 2005. Association for Computational Linguistics.  URL https://aclanthology.org/W05-0909.
  * Lin [2004] Chin-Yew Lin.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain, July 2004. Association for Computational Linguistics.  URL https://aclanthology.org/W04-1013.
  * Smit et al. [2020] Akshay Smit, Saahil Jain, Pranav Rajpurkar, Anuj Pareek, A. Ng, and Matthew P. Lungren.  Chexbert: Combining automatic labelers and expert annotations for accurate radiology report labeling using bert.  In _Conference on Empirical Methods in Natural Language Processing_ , 2020.  URL https://api.semanticscholar.org/CorpusID:215827807.
  * Irvin et al. [2019] Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ilcus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, Jayne Seekins, David A. Mong, Safwan S. Halabi, Jesse K. Sandberg, Ricky Jones, David B. Larson, Curtis P. Langlotz, Bhavik N. Patel, Matthew P. Lungren, and Andrew Y. Ng.  Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):590–597, Jul. 2019.  doi:10.1609/aaai.v33i01.3301590.  URL https://ojs.aaai.org/index.php/AAAI/article/view/3834.
  * Jain et al. [2021] Saahil Jain, Ashwin Agrawal, Adriel Saporta, Steven Truong, Du Nguyen Duong, Tan Bui, Pierre Chambon, Yuhao Zhang, Matthew P. Lungren, Andrew Y. Ng, Curtis Langlotz, and Pranav Rajpurkar.  Radgraph: Extracting clinical entities and relations from radiology reports.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_ , 2021.  URL https://openreview.net/forum?id=pMWtc5NKd7V.
  * Johnson et al. [2019] Alistair E. W. Johnson, Tom J. Pollard, Seth J. Berkowitz, Nathaniel R. Greenbaum, Matthew P. Lungren, Chih-ying Deng, Roger G. Mark, and Steven Horng.  Mimic-cxr, a de-identified publicly available database of chest radiographs with free-text reports.  _Scientific Data_ , 6(1):317, Dec 2019.  ISSN 2052-4463.  doi:10.1038/s41597-019-0322-0.  URL https://doi.org/10.1038/s41597-019-0322-0.
  * Patricoski et al. [2022] Jessica Patricoski, Kory Kreimeyer, Archana Balan, Kent Hardart, Jessica Tao, Valsamo Anagnostou, Taxiarchis Botsis, Johns Hopkins Molecular Tumor Board Investigators, et al.  An evaluation of pretrained bert models for comparing semantic similarity across unstructured clinical trial texts.  _Stud Health Technol Inform_ , 289:18–21, 2022.
  * Beltagy et al. [2019] Iz Beltagy, Kyle Lo, and Arman Cohan.  SciBERT: A pretrained language model for scientific text.  In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3615–3620, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi:10.18653/v1/D19-1371.  URL https://aclanthology.org/D19-1371.
  * Neumann et al. [2019] Mark Neumann, Daniel King, Iz Beltagy, and Waleed Ammar.  ScispaCy: Fast and Robust Models for Biomedical Natural Language Processing.  In _Proceedings of the 18th BioNLP Workshop and Shared Task_ , pages 319–327, Florence, Italy, August 2019. Association for Computational Linguistics.  doi:10.18653/v1/W19-5034.  URL https://www.aclweb.org/anthology/W19-5034.
  * Li et al. [2016] Jiao Li, Yueping Sun, Robin J. Johnson, Daniela Sciaky, Chih-Hsuan Wei, Robert Leaman, Allan Peter Davis, Carolyn J. Mattingly, Thomas C. Wiegers, and Zhiyong Lu.  BioCreative V CDR task corpus: a resource for chemical disease relation extraction.  _Database_ , 2016:baw068, 05 2016.  ISSN 1758-0463.  doi:10.1093/database/baw068.  URL https://doi.org/10.1093/database/baw068.
  * Honnibal et al. [2020] Matthew Honnibal, Ines Montani, Sofie Van Landeghem, and Adriane Boyd.  spaCy: Industrial-strength Natural Language Processing in Python.  2020\.  doi:10.5281/zenodo.1212303.
  * [18] Gricad.  infrastructure supported by grenoble research communities.  URL https://gricad.univ-grenoble-alpes.fr.


# Gransformer: Transformer-based Graph Generation

Ahmad Khajenezhad and Seyed Ali Osia and Mahmood Karimian and Hamid Beigy The
authors are with the Department of Computer Engineering, Sharif University of
Technology, Tehran, Iran.
E-mails: {khajenezhad, osia<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

Transformers have become widely used in modern models for various tasks such
as natural language processing and machine vision. This paper proposes
Gransformer, an algorithm for generating graphs based on the Transformer. We
extend a simple autoregressive Transformer encoder to exploit the structural
information of the given graph through efficient modifications. The attention
mechanism is modified to consider the presence or absence of edges between
each pair of nodes. We also introduce a graph-based familiarity measure
between node pairs that applies to both the attention and the positional
encoding. This measure of familiarity is based on message passing algorithms
and contains structural information about the graph. Furthermore, the proposed
measure is autoregressive, which allows our mode to acquire the necessary
conditional probabilities in a single forward pass. In the output layer, we
also use a masked autoencoder for density estimation to efficiently model the
sequential generation of dependent edges. Moreover, since we use BFS node
orderings, we propose a technique to prevent the model from generating
isolated nodes without connection to preceding nodes. We evaluate this method
on two real-world datasets and compare it with other state-of-the-art
autoregressive graph generation methods. Experimental results have shown that
the proposed method performs comparatively to these methods, including
recurrent models and graph convolutional networks.

###### Index Terms:

Graph generation, Transformers, autoregressive models, masked autoencoders.

##  I Introduction

Deep graph generation models are currently being used for several
applications, ranging from biology to drug discovery to social network
analysis. From a general point of view [1], these models can be divided into
autoregressive models [2, 3, 4, 5, 6, 7], autoencoder-based models [8, 9, 10],
adversarial models [11, 12, 13], reinforcement learning-based methods [14,
15], and flow-based models [16, 17, 18]. There are various models for task-
specific graph generation, although autoregressive methods are state-of-the-
art for generating large general graphs. The first autoregressive model, which
was introduced by Li et al. [2], used the graph neural networks (GNN) in a
very time-consuming manner to generate graphs. You et al. [3] used recurrent
neural networks to generate larger graphs in an autoregressive manner. Despite
exploiting the structural properties of the graph by using breath-first search
(BFS) orderings of nodes, their method did not explicitly benefit from this
structure. A method using graph convolutional networks (GCN) was proposed by
Liao et al. [4] to address this shortcoming by reducing training and
generation time complexity.

Transformers are used instead of recurrent neural networks in modern natural
language processing and machine vision models. However, they are not yet
widely used for the graph generation. Fan and Huang [7] used a simple
transformer model for conditional graph generation, where the goal is to
generate a graph, having another graph as input. The difficulty is
incorporating the structural properties of the graph into the transformer
model while preserving the autoregressive property. Kawai et al. [6] proposed
a model that combines graph convolutional models with a transformer encoder.
For each node, their model performs a separate forward pass to satisfy the
autoregressive property.

Finally, we address the problem of generating autoregressive graphs using
transformers instead of recurrent neural networks [3]. A common method for
exploiting the structural properties of the input data is to use graph
convolutional networks. Since the graph convolutional layer collects the data
from all neighboring nodes of a given node, it violates the autoregressive
property. Thus, when we use graph convolutional layers, we need a separate
forward pass on a subset of the input graph to compute each conditional
probability [4, 6]. Our goal is to propose an alternative model for injecting
structural information into our Transformer-based model that retains the
autoregressive property and can compute all conditional probabilities in a
single forward pass for the entire graph. In the following sections, we will
discuss that the method for injecting structural properties is based on random
walks and inspired by message passing.

We propose Gransformer, which is an autoregressive transformer-based graph
generation model. Gransformer uses a single transformer encoder to compute all
the required conditional probabilities in one forward pass. As with some other
autoregressive models, such as the models in [3], we use the BFS ordering of
the nodes and then reorder the adjacency matrix based on this ordering. Nodes
in the network are represented by their masked adjacency vectors, that is, the
vectors that indicate their connections to the preceding nodes. There is a
unit corresponding to each graph node in each self-attention layer of the
transformer encoder. To determine the output of each unit, we apply a lower
triangular mask to the layers of self-attention, so that only the information
from the preceding nodes is taken into account. In addition, we use a shared
Masked Autoencoder for Distribution Estimation (MADE) [19] in the output layer
to model the sequential dependency between the edge probabilities of a given
node. MADE is a well-known and efficient autoregressive model that has
inspired other generative models such as [20, 21]; MADE helps us easily model
the dependency of edge generation and efficiently generate edge probabilities
all at once.

While You et al. [3] benefit the graph structure by using BFS orderings of the
nodes, they do not explicitly utilize the structural properties of the graph.
Liao et al. [4] and Kawai et al. [6] use graph convolutional networks to solve
this problem. However, for satisfying the autoregressive property, they need
to perform $\mathcal{O}(n)$ forward passes to compute the likelihood of the
graph. To integrate the structural properties of the graph to the single
forward pass of a transformer encoder, we use the following two techniques:
first, we change the attention formulation of the model according to the
presence or absence of edges between each pair of nodes. Second, we introduce
a measure of familiarity between each pair of nodes and use it to modify the
attention mechanism and the positional encoding formula. This measure is
derived from the message passing algorithm and represents the structural
proximity between two nodes. This measure is also autoregressive since the
familiarity function of nodes $j$ and $i$ ($j\geq i$) is computed only from
the subgraph that contains the first $j$ nodes of the graph. Finally, since we
are using the BFS order, we prevent our model from generating isolated nodes
by manipulating the probability distribution to assign zero probabilities to
zero vectors; we then address how to sample from this manipulated
distribution.

Our contribution can be summarized as follows:

  * •

We propose a graph generation model with a single transformer encoder that
utilizes the graph’s structural properties.

  * •

To model edge dependencies efficiently, we propose using a shared MADE in the
output layer.

  * •

With the help of the presence or absence of edges between each pair of nodes,
we modify the attention mechanism of the transformer model.

  * •

An autoregressive familiarity measure between nodes is introduced to represent
the structural properties of the graphs. In both attention layers and
positional encoding, we use this measure.

  * •

The model is prevented from generating isolated nodes using a proper sampling
method based on the corresponding probability distribution.

In this paper we tackle the problem of generating simple undirected graphs,
with no self loops, no duplicate edges and no node or edge labels. However,
Gransformer can be easily extended to handle these cases.

The rest of this paper is organized as follows: In Section III we present the
proposed method. First, we discuss the transformer and the basic skeleton of
the model. Then we state how MADE is used for dependent edge generation,
explain our ideas for integrating graph structural properties, and discuss the
strategy to avoid generating all zeros adjacency vectors. Experimental results
are presented in Section IV. Finally, Section V concludes the paper.

##  II Related Work

In this section, we briefly review research in graph generation. Existing
models for generating deep graphs can be categorized from different points of
view. Some models generate an entire graph at once [8, 9, 22], while others
generate a graph node by node [23, 24, 3], edge by edge [25, 26, 27], or block
by block [4, 28].

As mentioned in the previous section, graph generation models can be divided
into autoencoder models [8, 9, 10], adversarial models [11, 12, 13],
reinforcement learning methods [14, 15], flow-based models [16, 17, 18], and
autoregressive models [2, 3, 4, 5, 6, 7].

The models can also be classified by the type of graphs they can generate.
Some models can generate graphs with node or edge features [23, 24, 27, 6],
while some others only aim to generate graphs without features [3, 25, 26, 4].
In addition, some models may incorporate specific constraints in their
construction process to generate graphs with certain features, such as
chemical rules in molecule generation [14].

Another distinguishing feature is how these models use the structural
properties of the input graphs. Some models use either the graph convolutional
layers [8, 9, 4] or other graph neural networks [2], and some other ones use
random walk [11, 29]. The models that generate the graph sequentially also
benefit from the structural information by using node orders based on specific
graph traversals such as BFS [3, 4].

Furthermore, autoencoder-based graph generators can be divided into methods
that use a single graph as training data [8, 30, 31] and those that use a
collection of graphs as training data [9, 22].

It is worth noting that the graph generation problem is closely related to the
node embedding problem, as many graph generation models use node embedding as
an intermediate step [32, 14]. Furthermore, many graph generation models use
similar graph processing techniques as node embedding models. For example,
there are deep node embedding models based on random walks [33, 34, 35] and
graph convolutional networks [36, GCNGraphSage].

##  III Proposed Method

In this section, we first discuss transformers and how they are related to
graph neural networks. Then we present how a transformer can be used for the
task of graph generation. Two main challenges are the generation of dependent
edges and the usage of structural information, which we will address. Finally,
we discuss how to prevent the model from generating isolated nodes.

###  III-A Transformer and Graph Generation

Transformer adopts an encoder-decoder architecture. The encoder transforms the
input sequence into another sequence. Utilizing the encoder’s output, the
decoder generates the output sequence in an autoregressive manner. Encoders
and decoders can also be used independently to solve different problems. For
instance, BERT is a transformer encoder for language understanding [37], while
GPT-3 is a state-of-the-art natural language generative model based on a
transformer decoder [38]. Transformer decoder takes two sequences, the output
of the encoder and the target sequence that it aims to generate. Since we have
a single sequence in our task that works both as the input and output of the
model, we use the encoder of the transformer structure, but we use the
decoder’s mask to satisfy the autoregressive property. This mask restricts the
$i$-th unit in each layer to be computed just from the first $i$ units of the
previous layer.

The Transformer adopts an encoder-decoder architecture. The encoder part
transforms the input sequence into another sequence. The decoder generates the
output sequence in an autoregressive manner by utilizing the encoder’s output.
Encoders and decoders can also be used independently to solve different
problems. For instance, BERT is a transformer encoder for language
understanding [37], while GPT-3 is a state-of-the-art natural language
generative model based on a transformer decoder [38]. The Transformer decoder
takes two sequences, the output of the encoder and the target sequence that it
aims to generate. Since we have a single sequence in our task that works both
as the input and output of the model, we use the encoder of the transformer
structure. But we use the decoder’s mask to satisfy the autoregressive
property. This mask restricts the $i$-th unit in each layer to be computed
just from the first $i$ units of the previous layer.

The main building block of encoder and decoder is the self-attention layer
that learns a weighting function, computing the weighted sum of input values
$V$ and provides the output. Also the weights assigned to $V$ is computed by a
compatibility function between queries $Q$, and the corresponding keys $K$
[39]. For the $t$-th attention layer, input vectors
$v_{1}^{(t)},v_{2}^{(t)},\ldots,v_{n+1}^{(t)}$ (the rows of matrix $V^{(t)}$)
will be transformed to output vectors
$v_{1}^{(t+1)},v_{2}^{(t+1)},\ldots,v_{n+1}^{(t+1)}$ (the rows of matrix
$V^{(t+1)}$) through the following equations.

$\displaystyle Att^{(t)}$
$\displaystyle=M\odot\text{softmax}\left(\frac{Q^{(t)}\times
K^{(t)T}}{\sqrt{d_{k}}}\right),$ (1) $\displaystyle Q^{(t)}$
$\displaystyle=V^{(t)}\times W_{Q}^{(t)}+b_{Q}^{(t)},$ (2) $\displaystyle
K^{(t)}$ $\displaystyle=V^{(t)T}\times W_{K}^{(t)}+b_{K}^{(t)},$ (3)
$\displaystyle V^{(t+1)}$ $\displaystyle=Attn^{(t)}\times\left(V^{(t)}\times
W_{V}^{(t)}+b_{V}^{(t)}\right),$ (4)

where $Attn^{(t)}$ is the attention of the units in the $t+1$-th layer to the
units in the $t$-th layer, $W_{Q}^{(t)}$, $W_{K}^{(t)}$, $W_{V}^{(t)}$,
$b_{V}^{(t)}$, $b_{Q}^{(t)}$ and $b_{K}^{(t)}$ are trainable parameters of the
model. $M$ is the mask matrix, and $\odot$ denotes the element wise
multiplication.

Based on the graph convolutional networks paradigm, the Transformer encoder is
similar to an attention-based graph convolutional network on a fully connected
graph. In each self-attention layer of this network, the attention of each
unit to another unit assumes a hypothetical edge between the corresponding
pair of nodes, regardless of the existence of an edge between them in the
original graph. Since without considering a mask, every unit in the encoder
has attention to all the units, this structure is similar to the graph
convolution on a fully connected layer. Using the decoder’s mask, this
structure would be similar to graph convolution on a directed graph in which
there are edges from each node to all subsequent nodes.

$v_{1}^{(t)}$$v_{2}^{(t)}$$v_{n-1}^{(t)}$$v_{n}^{(t)}$$v_{1}^{(t+1)}$$v_{2}^{(t+1)}$$v_{n-1}^{(t+1)}$$v_{n}^{(t)}$……….……….$0.1$$0.2$$0.0$$0.3$$k_{1}^{(t)}$$k_{2}^{(t)}$$k_{n-1}^{(t)}$$k_{n}^{(t)}$$q_{2}^{(t)}$

Figure 1: The schema of the self-attention layer of the transformer encoder.
As illustrated in this figure, for each $1\leq i\leq n$, the value
$v_{i}^{(t+1)}$ is computed from values $v_{j}^{(t)}$ for all $1\leq j\leq n$.
From this point of view, this layer is similar to a graph convolutional layer
on a fully connected graph. When we are using an autoregressive mask,
$v_{i}^{(t+1)}$ would be computed from values $v_{j}^{(t)}$ for all $1\leq
j\leq i$. This operation is similar to a graph convolutional layer on a fully
connected directed acyclic graph.

Let us now discuss how to use the Transformer encoder to generate graphs. The
autoregressive model generates a graph by generating an edge by edge, and a
node by node, in a sequential manner. Given an incomplete graph of $k-1$
nodes, the proposed model must be able to decide about the $k$-th node. It has
to estimate the probability of connecting the $k$-th node to any of the
preceding $k-1$ nodes. To generate a graph $G$, we first estimate the number
of nodes, $n$, using an empirical estimation of the graph sizes. Moreover,
similar to previous autoregressive models, we use a node ordering $\pi$ of
nodes for the sequential graph generation. Therefore we have

$P(G)=P(n)\displaystyle\sum_{\pi}P(\pi)P(G|\pi).$ (5)

We use the empirical estimation of $P(n)$ for the graph generation. In
addition, in the training phase, the network is fed by training graphs, which
are naturally sampled from $P(n)$. Therefore, it remains to learn
$\displaystyle\sum_{\pi}P(\pi)P(G|\pi)$.

Moreover, using a uniform distribution, $P(\pi)$ can be ignored on all BFS
orders, and all that remains is to learn a model to estimate $P(G|\pi)$.
Assuming any order $\pi$ of nodes, we use the probability chain rule for graph
generation and graph density estimation.

Let $A^{\pi}$ be the adjacency matrix of the graph of size $n$ under the
ordering $\pi$. Let $L^{\pi}$ be the lower triangular form of $A^{\pi}$. Let
$L_{i}^{\pi}$ also be the $i$-th row of $L^{\pi}$. We encode a graph with the
sequence of vectors $L_{1}^{\pi},L_{2}^{\pi},\ldots,L_{n}^{\pi}$. We need a
model that can generate $L_{i+1}^{\pi}$ using
$L_{1}^{\pi},L_{2}^{\pi},\ldots,L_{i}^{\pi}$. In other words, by following the
probability chain rule, we will find that:

$P(G|\pi)=P(A^{\pi}|\pi)=\prod_{i}P(L_{i}^{\pi}|L_{1}^{\pi},\ldots,L_{i-1}^{\pi})$
(6)

Therefore, we need the transformer model to estimate every one of these $n$
conditional probabilities. The sequence of the input vectors to the
transformer encoder would be
$Start,L_{1}^{\pi},L_{2}^{\pi},\ldots,L_{n}^{\pi}$ and its output vectors
would be $y_{1}^{\pi},y_{2}^{\pi},\ldots,y_{n}^{\pi},End$, where $Start$ and
$End$ are the padding vectors. The $i$-th element of $y_{k}$ ($i<k$)
determines the probability of putting an edge between the $k$-th node and the
$i$-th node. Therefore, since $L_{1}^{\pi},\ldots,L_{n}^{\pi}$ are binary
vectors, the target sequence of the vectors in the output layer is
$L_{1}^{\pi},L_{2}^{\pi},\ldots,L_{n}^{\pi},End$. We use a lower triangular
matrix as the mask matrix i.e., $M$ in Equation (1), to guarantee that $y_{k}$
is computed only from the first $k$ inputs i.e., from
$L_{1}^{\pi},\ldots,L_{k-1}^{\pi}$. Figure 2 shows the schema of the proposed
model. The model described so far is similar to the encoder part of the
transformer network. However, it uses the decoder’s mask, so that unit $i$ in
each layer would be allowed to have attended only to the first $i$ units of
the previous layer. In the following subsection, we describe the proposed
extensions for the task of graph generation.

($Start,L_{1},L_{2},\ldots,L_{n-1}$)InputsLinear ProjectionPositional
Encoing+$T\times$Self-Attention Layer+Feed
Forward+SigmoidMADEn(binaryrepresentation)Target Vector($L_{i}$)Output
Probabilities$i=1,\ldots,n$

$i$-th

output

Figure 2: Schema of the Gransformer model. Notice that the autoregressive
(MADE) network used at the output layer is shared between all the $n$ output
vectors of the transformer encoder.

###  III-B Dependent Edge Generation

$1$$2$$3$$n$$0$$0$$0$$0$$0$$0$Sigmoid$L_{i,1}$$L_{i,2}$$L_{i,3}$$L_{i,i-1}$$\bar{L}_{i,1}$$\bar{L}_{i,2}$$\bar{L}_{i,3}$$\bar{L}_{i,i-1}$$\underbrace{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color<EMAIL_ADDRESS>184.9429pt{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}.}}$$\underbrace{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color<EMAIL_ADDRESS>184.9429pt{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color<EMAIL_ADDRESS>representation of
}n}$$\underbrace{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color<EMAIL_ADDRESS>227.62204pt{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color<EMAIL_ADDRESS>vector}}$$i$-th output of the transformer
encoder………………$3$$2$$10$$1$$2$$1$$n-1$$2$$1$$2$$3$$n$

Figure 3: Here is an example of a MADE network appearing at the output layer.
Numbers written on the network units and inputs are the tags. Masked
connections have been removed in this figure. The $i$-th output of the
transformer encoder contains the information from the $i-1$ preceding nodes of
the graph. Therefore, it is tagged by zero to be used by all the output units.
The target vector contains the information of the edges connecting the $i$-th
node to the preceding nodes. The network masks guarantee that the $j$-th
output unit uses only the first $j-1$ elements of the target vector. It is
worth noting that only the first $i-1$ elements of $\bar{L}_{i}$ are of our
interest, and the rest will be treated as zero. To keep the figure simple and
sparse, we ignored drawing direct links from the input layer to the output
layer.

Suppose that we only use a masked transformer encoder, without using any extra
layers at its output layer. Then, the output sequence of the vectors from the
transformer encoder will act as the probability estimation of the adjacency
vectors. In other words, the first $i-1$ elements of the $i$-th output vector
would represent the probability of the presence of the edges between node $i$
and nodes $1,2,\ldots,i-1$. All these $i-1$ values are computed from the first
$i-1$ input vectors. Therefore, the resulted probability for connecting node
$i$ to node $j$ ($j<i$Suppose we use only a masked transformer encoder without
using additional layers on the output layer. Then the output sequence of
vectors from the transformer encoder serves as the probability estimate for
the adjacency vectors. In other words, the first $(i-1)$ elements of the
$i$-th output vector would represent the probability of the presence of edges
between node $i$ and nodes $1,2,\ldots,(i-1)$. All of these $(i-1)$ values are
calculated from the first $(i-1)$ input vectors. Therefore, the resulting
probability of connecting node $i$ to node $j$ ($j$) depends only on the edges
such as $\langle t,s\rangle$ that $t,s<i$. However, it is obvious that knowing
the existence or absence of the edges $\langle 1,i\rangle$, $\langle
2,i\rangle$, $\langle(j-1),i\rangle$ has a significant impact on the decision
about the existence of the edge $\langle j,i\rangle$. Therefore, we can extend
the equation (6) to also capture the sequential generation of edges:

$P(G|\pi)=\prod_{i=1}^{n}\prod_{j=1:i-1}P(L_{ij}^{\pi}|L_{1}^{\pi},\ldots,L_{i-1}^{\pi},L_{i,1}^{\pi},\ldots,L_{i,j-1}^{\pi})$
(7)

To model this dependency, You et al. used an additional recurrent neural
network in their model for sequential edge generation, which means additional
training time [3]. Also, Liao et al. proposed using a mixture to capture the
correlation between edges [4]. However, this only increases the ability of
their method to model more complex edge distributions. However, it does not
fully model the dependence between edges of individual nodes (or blocks in
their proposed approach).

We propose to use the Masked Autoencoder for Density Estimation (MADE) [19]
for sequential edge generation. MADE is a fully connected feed-forward
autoencoder where each unit has a tag in $\\{1,2,\ldots,n\\}$. Also, the $n$
units in the input layer and the $n$ units in the output layer have labels
$1,2,\ldots,n$. Connection from a node with label $i$ to another node labeled
$j$ in the following layer will be masked if $i>j$. All paths from input nodes
that have labels $j+1,j+2,\ldots,n$ to nodes with labels $j$ in the following
layers will be blocked using this mask set. In the same way, it can be shown
that the label of each node determines the subset of input units that are
allowed to have a path to that node. Therefore, this masking strategy
satisfies the autoregressive property.

We use a single MADE with shared parameters for generating the edges of all
nodes. In the original MADE network, the input is exactly the target vector,
which is supposed to be estimated in the output layer. Here, the target vector
for the $i$-th node is the adjacency vector of the node $i$ that we want to
see in the output layer of MADE. Therefore, for node $i$, we feed $L_{i}$ into
the MADE network, and it tries to estimate $L_{i}$ in the output. But, as
shown in figure 2, in addition to the target vector, we feed two more inputs
to the MADE network: $n$, which is the number of nodes and the $i$-th output
vector of the transformer encoder. Additional information from the other two
inputs can be incorporated fully into the reconstruction of the target vector
in the output layer, so they are tagged as $0$ in the input layer, despite the
target vector in the input layer which should have tags from 1 to $n$. The
experimental results show that adding direct links from the input units of
MADE to the output units with larger tags has a significant impact on the
results. Figure 3 illustrates how we use the MADE network to generate the
$i$-th output vector.

###  III-C Using Graph Structural Properties

As mentioned earlier, the Gransformer is based on the Transformer, which was
originally proposed for natural language processing. In NLP tasks, the input
text to the Transformer model is represented by a sequence of one-hot vectors.
Similarly, we represent an input graph for our model by a sequence of vectors,
$L_{1}^{\pi},L_{2}^{\pi},\ldots,L_{n}^{\pi}$. However, this representation
does not explicitly specify the structural information of the graph that can
be used during the training and generation process.

In previous work, graph convolutional networks have been used for this purpose
[2, 6, 4]. To infer a new node (or a new block of nodes) and its connecting
edges to the previous nodes, these models consider the subgraph of the
existing nodes and apply multiple graph convolutional layers on it. Therefore,
$\mathcal{O}(n)$ forward passes are needed to compute the loss
function.However, we intend to combine the structural graph information with
our transformer-based model such that the loss function can be calculated in a
single forward pass.

In Sections III-C1 and III-C2 we will discuss two techniques we have proposed
for this goal.

####  III-C1 Using Presence/Absence of Edges

In a regular transformer encoder, each node can attend to all the nodes in the
previous layer. As with the transformer decoder, we restrict it to have
attention to the preceding nodes using autoregressive masks. But even in this
way, we do not use the structural information of the graph and ignore the
edges.

Using different sets of key/query/value parameters for pairs of nodes with an
edge between them and pairs of nodes without an edge between them allows us to
import the structural information of the graph into our proposed model. To be
more specific, we can rewrite the Equations (1), (2), (3) and (4) in the
following form:

$\displaystyle Att_{1}^{(t)}$
$\displaystyle=M\odot\text{softmax}\left(\frac{Q_{1}^{(t)}\times
K_{1}^{(t)T}}{\sqrt{d_{k}}}\right),$ (8) $\displaystyle Att_{2}^{(t)}$
$\displaystyle=M\odot\text{softmax}\left(\frac{Q_{2}^{(t)}\times
K_{2}^{(t)T}}{\sqrt{d_{k}}}\right),$ (9) $\displaystyle Q_{1}^{(t)}$
$\displaystyle=V_{1}^{(t)}\times W_{Q1}^{(t)}+b_{Q1}^{(t)},$ (10)
$\displaystyle Q_{2}^{(t)}$ $\displaystyle=V_{2}^{(t)}\times
W_{Q2}^{(t)}+b_{Q2}^{(t)},$ (11) $\displaystyle K_{1}^{(t)}$
$\displaystyle=V_{1}^{(t)}\times W_{K1}^{(t)}+b_{K1}^{(t)},$ (12)
$\displaystyle K_{2}^{(t)}$ $\displaystyle=V_{2}^{(t)}\times
W_{K2}^{(t)}+b_{K2}^{(t)},$ (13) $\displaystyle V_{1}^{(t+1)}$
$\displaystyle=Att_{1}^{(t)}\times(V^{(t)}\times W_{V1}^{(t)}+b_{V1}^{(t)}),$
(14) $\displaystyle V_{2}^{(t+1)}$
$\displaystyle=Att_{2}^{(t)}\times(V^{(t)}\times W_{V2}^{(t)}+b_{V2}^{(t)}),$
(15) $\displaystyle V^{(t+1)}(i,j)$
$\displaystyle=\begin{cases}V_{1}^{(t+1)}&ifA(i,j)=1\\\
V_{2}^{(t+1)}&ifA(i,j)=0\end{cases}$ (16)

This concept duplicates the computation time without changing the order of
time complexity.

####  III-C2 Autoregressive Graph-based Familiarities

This section aims to define a familiarity function $K$ with desired properties
between pairs of nodes. To be more precise, $K$ would be

  1. 1.

based on the graph structure; or represent the graph structural information,

  2. 2.

autoregressive; i.e., if $i>j$ then $K(i,j)$ is a constant value and if $i\leq
j$ then $K(i,j)$ is computed only from the subgraph of the first $j$ nodes.

  3. 3.

efficiently computable for all the node pairs.

We define $K$ as follows:

$\displaystyle K(i,j)$
$\displaystyle=sigmoid\left(f\left(g_{0}(i,j),\ldots,g_{n_{k}}(i,j)\right)\right),$
(17) $\displaystyle g_{k}(i,j)$ $\displaystyle=log(1+m_{k}(i,j)),$ (18)

where $f(.)$ is a two-layers MLP with a ReLU activation function in the first
layer and a linear activation function in the second layer. $m_{k}(i,j)$
denotes the number of paths of length $k$ from node $i$ to node $j$ in the
subgraph containing nodes $1$ to $j$. The path means any sequence of nodes in
which every two consecutive nodes are connected (so a node can appear more
than once in a path). It is clear that if $j<i$, then according to the
definition $m_{k}(i,j)=0$ for all values of $k$, and consequently $K(i,j)$
will be a constant value, independent of $i$ and $j$. We used the logarithm in
(18) for two reasons: first, it bounds the input values to network $f$;
otherwise, it faces numerical overflows for its parameter values during the
training process. Second, it intuitively makes sense that as the number of
paths increases, the difference between two values for the number of paths is
less important. For example, one path between two nodes versus no paths is
more informative than the existence of $21$ paths between two nodes versus
$20$ paths. On the other hand, the logarithm function is concave and satisfies
this condition.

Here we briefly justify why the number of paths of length $k$ between pairs of
nodes is an appropriate value to represent the structural information of the
graph. We consider a process of message passing on a subgraph of the first $j$
nodes in which each node passes its value to all its neighbors at each step.
Following this algorithm, the initial message on node $i$ is received exactly
$m_{k}(i,j)$ times by the $j$-th node in step $k$. It is worth noting that
most graph convolutional layers and graph kernels based on random walks can be
restated by special forms of message passing.In spatial graph convolutional
layers, for example, the vector at each node is computed by aggregating the
vectors (or equivalent messages) from its neighboring nodes, followed by a
nonlinear activation function.

We now explain how to calculate $m_{0}(.,.),\ldots,m_{n_{k}}(.,.)$
efficiently. We define $M_{k}$ as an upper triangular matrix whose elements in
the $i$-th row and $j$-th column equals to $m_{k}(i,j)$. Clearly, $M_{0}$ is
an identity matrix. Let $A$ be the adjacency matrix of the graph and $A(i,j)$
be the element in row $i$ and column $j$. Assume that we have computed the
function $m_{k-1}(.,.)$ or equivalently $M_{k-1}$. Obviously, each path of
length $k$ from $i$ to $j$ that uses only the first $j$ nodes, constitutes of
a first step from node $i$ to a node $t\in\\{1,2,\ldots,j\\}$ and a path of
length $k-1$ from node $t$ to node $j$ that uses only the first $j$ nodes.
Therefore for $i\leq j$ we have:

$\displaystyle m_{k}(i,j)$ $\displaystyle=\sum_{1\leq t\leq j}A(i,t)\times
m_{k-1}(t,j)$ $\displaystyle=\sum_{1\leq t\leq n}A(i,t)\times m_{k-1}(t,j)$
$\displaystyle=\left[A\times M_{k-1}\right](i,j)\hskip
14.22636pt\text{if}\hskip 5.69046pti\leq j$ (19)

The second line of the above equation is because for $t>j$, we have
$m_{k-1}(t,j)=0$. Similarly, for $m_{k}$ we must have $i>j\Rightarrow
m_{k}(i,j)=0$. Therefore

$M_{k}=tri\\_up(A\times M_{k-1}),$ (20)

where the operator $tri\\_up$ converts its input matrix to an upper triangular
matrix.

Computing this measure for all node pairs needs $k$ multiplications of
$n\times n$ matrices, which can theoreticly be run either in
$\mathcal{O}(kn^{2.3728596})$ [40], but practically in
$\mathcal{O}(kn^{2.8074})$ [41] or $\mathcal{O}(kne)$ for sparse graphs, where
$e$ is the number of edges (because one of the matrices in each multiplication
is the adjacency matrix). In addition, $n_{k}$ is an integer parameter in the
familiarity measure, which we set to $16$ in our experiments.

Finally, we will indicate the utilization of the familiarity measure (17) in
our model. We multiply the familiarity function to the attention in each
layer. In other words we modify the attention defined in Equation (1) in the
following form:

$Att^{(t)}\leftarrow Att^{(t)}\odot\mathcal{K}^{T},$ (21)

where $\mathcal{K}$ is an $n\times n$ matrix containing $K(i,j)$ for all
values of $i$ and $j$. It is worth noting that the familiarity function
defined in Equation (17) contains a two-layer neural network $f$. This neural
network can have different parameter values in different layers of our model.
These parameters will be learned with other network parameters through the
training process.

Similarly, we propose a positional encoding for the nodes based on
$m_{k}(.,.)$ for $k\in\\{0,2,\ldots,n_{k}\\}$. The intuition is that if we put
a one-hot vector on each vector representing its index and let these vectors
propagate over the subgraph of the first $j$ nodes for $k$ times, then the
$i$-th element of the final vector (after $k$ steps of message passing) on the
$j$-th node will be $m_{k}(i,j)$. So we define the positional encoding of node
$j$ as follows:

$\displaystyle pos\\_enc(j)$
$\displaystyle=f_{1}\left(h_{0}(j),h_{1}(j),\ldots,h_{n_{k}}(j)\right),$ (22)
$\displaystyle h_{k}(j)$
$\displaystyle=f_{2}\left(g_{k}(1,j),g_{k}(2,j),\ldots,g_{k}(j,j)\right),$
(23)

where $f_{1}$ is a one-layer MLP (a linear projection with a bias) and $f_{2}$
is a two layers MLP with a ReLU activation function in the first layer and a
sigmoid activation function in the second layer. Also, $g_{k}$ is given in
Equation (18).

###  III-D Avoiding Isolated Nodes

When generating the $k$-th node, our model should decide its connection to the
preceding $(k-1)$ nodes. In other words, it should try to estimate the first
$(k-1)$ elements of $L_{k}^{\pi}$ (because the other elements of this vector
are equal to zero according to the definition.) Since we use BFS orders for
training, we should generate graphs in the BFS sequences. However, when we
consider a BFS ordering of the nodes of a graph, each node like $v$ (except
the root node) has a parent node in the BFS tree ($p_{v}$). In this ordering,
$p_{v}$ appears at a position before $v$. Therefore, adding an isolated node,
which does not connect to any of the preceding nodes, is not allowed. However,
our model so far has nothing to satisfy this condition. You et al. [3] allows
the isolated nodes to be generated and remove them after generating the graph.
However, it will disturb the distribution of the generated graph sizes. In
this section, we tackle this problem by distributing the probability of the
all-zeros vector among valid vectors. Let the binary vector
$\textbf{y}=\langle y_{1},y_{2},\ldots,y_{k-1}\rangle$ denote the model
estimation of the first $k-1$ bits of $L_{k}^{\pi}$, and $P(\textbf{y})$
denote the probability of generation of y.

We define the new density function $\tilde{P}$ over $k-1$-bits binary vectors
as follows:

$\tilde{P}(\textbf{y})=\begin{cases}0&\text{if $y_{1}=\ldots=y_{k-1}=0$}\\\
\frac{P(\textbf{y})}{1-P(\overline{0})}&\text{otherwise}\end{cases}$ (24)

Computation of the new loss function (the new negative log-likelihood) during
the training process is easy; it just needs an extra computation of
$P(\overline{0})$. However, generation is a bit challenging. A simple method
for generating samples from $\tilde{P}$ is generating samples from $P$ and
reject all-zeros samples. But this sampling method is likely to be trapped in
long-lasting rejection loops, especially for generating sparse graphs.

In order to sample from $\tilde{P}(\textbf{y})$ sequentially, it is sufficient
to compute $\tilde{P}(Y_{i}|y_{1},y_{2},\ldots,y_{i-1}$). We prove the
following theorem to show how we can efficiently sample binary vectors from
$\tilde{P}$.

######  Theorem 1.

For a fixed set of values for $y_{1}$, $y_{2}$, …, $y_{i-1}$, if we denote
$P(Y_{i}=1|y_{1},\ldots,y_{i-1})$ by $P_{i}$ then

$\displaystyle\tilde{P}(Y_{i}=1|y_{1},\ldots y_{i-1})=$
$\displaystyle\begin{cases}P_{i}&\text{if}\hskip 5.69046pt\exists
j<i:y_{j}=1\\\ P_{i}\times\frac{\prod\limits_{1\leq
j<i}P(y_{j}|y_{1},\ldots,y_{j-1})}{\prod\limits_{1\leq
j<i}P(y_{j}|y_{1},\ldots,y_{j-1})-P(\overline{0})}&\text{otherwise.}\end{cases}$
(25)

For the special case of $i=1$,

$\tilde{P}(Y_{1}=1)=P(Y_{1}=1)\times\frac{1}{1-P(\overline{0})}.$ (26)

###### Proof.

We first define the following sets:

$\displaystyle A_{y}^{(i)}$ $\displaystyle\triangleq\\{\langle
a_{1},\ldots,a_{k-1}\rangle\in\\{0,1\\}^{k-1}|\forall j<i:a_{j}=y_{j}\\}$ (27)
$\displaystyle A_{0}^{(i)}$ $\displaystyle\triangleq\\{\langle
a_{1},\ldots,a_{k-1}\rangle\in\\{0,1\\}^{k-1}|a_{i}=0\\}$ (28) $\displaystyle
A_{1}^{(i)}$ $\displaystyle\triangleq\\{\langle
a_{1},\ldots,a_{k-1}\rangle\in\\{0,1\\}^{k-1}|a_{i}=1\\}$ (29)

In other words, $A_{y}$ is the set of all binary sequences of length $k-1$
whose first $(i-1)$ elements are equal to $y_{1},y_{2},\ldots,y_{i=1}$.
$A_{0}$ represents all binary sequences of length $k-1$ whose $i$-th element
is equal to $0$, and $A_{1}$ represents all binary sequences of length $k-1$
whose $i$-th element is equal to $1$. As a result, it follows that

$\displaystyle\tilde{P}(Y_{i}=1|y_{1},\ldots y_{i-1})$
$\displaystyle=\frac{\tilde{P}(A_{y}^{(i)}\cap
A_{1}^{(i)})}{\tilde{P}(A_{y}^{(i)})}$ (30)
$\displaystyle=\frac{\tilde{P}(A_{y}^{(i)}\cap
A_{1}^{(i)})}{\tilde{P}(A_{y}^{(i)}\cap A_{0}^{(i)})+\tilde{P}(A_{y}^{(i)}\cap
A_{1}^{(i)})}.$

Since $A_{y}^{(i)}\cap A_{1}^{(i)}$ does not include the zero vector, and
respecting the definition of distribution $\tilde{P}(.)$ in Equation (24), we
infer that

$\displaystyle\tilde{P}(A_{y}^{(i)}\cap A_{1}^{(i)})=\displaystyle\sum_{c\in
A_{y}^{(i)}\cap A_{1}^{(i)}}\tilde{P}(c)$ $\displaystyle=\sum_{c\in
A_{y}^{(i)}\cap
A_{1}^{(i)}}\frac{P(c)}{1-P(\overline{0})}=\frac{P(A_{y}^{(i)}\cap
A_{1}^{(i)})}{1-P(\overline{0})}$
$\displaystyle=\frac{P(Y_{i}=1|y_{1},\ldots,y_{i-1})\prod\limits_{1\leq
j<i}P(y_{j}|y_{1},\ldots,y_{j-1})}{1-P(\overline{0})}.$ (31)

If at least one of $y_{1},\ldots,y_{i-1}$ is equal to $1$, then
$A_{y}^{(i)}\cap A_{0}^{(i)}$ does not include the zero vector as well, and we
can infer in a similar way that

$\displaystyle\tilde{P}(A_{y}^{(i)}\cap A_{0}^{(i)})=$
$\displaystyle\frac{P(Y_{i}=0|y_{1},\ldots,y_{i-1})\prod\limits_{1\leq
j<i}P(a_{j}|y_{1},\ldots,y_{j-1})}{1-P(\overline{0})}.$ (32)

Hence, respecting Equation (30) we conclude that

$\displaystyle\text{if}\hskip 5.69046pt\exists j<i:y_{j}=1\hskip
5.69046pt\text{then}\hskip 5.69046pt\tilde{P}(Y_{i}=1|y_{1},\ldots y_{i-1})=$
$\displaystyle\hskip 5.69046ptP(Y_{i}=1|y_{1},\ldots y_{i-1})=P_{i}.$ (33)

But if $A_{y}^{(i)}\cap A_{0}^{(i)}$ contains the zero vector, it means that

$y_{1}=y_{2}=\ldots=y_{i-1}=0.$ (34)

In this case we have:

$\displaystyle\tilde{P}(A_{y}^{(i)}\cap A_{0}^{(i)})=\sum_{c\in
A_{y}^{(i)}\cap A_{0}^{(i)}}\tilde{P}(c)=$
$\displaystyle\sum_{\begin{subarray}{c}c\in A_{y}^{(i)}\cap A_{0}^{(i)},\\\
c\neq\overline{0}\end{subarray}}\frac{P(c)}{1-P(\overline{0})}=\frac{P(A_{y}^{(i)}\cap
A_{0}^{(i)})-P(\overline{0})}{1-P(\overline{0})}=$
$\displaystyle\frac{P(Y_{i}=0|y_{1},\ldots,y_{i-1})\prod\limits_{1\leq
j<i}P(y_{j}|y_{1},\ldots,y_{j-1})-P(\overline{0})}{1-P(\overline{0})}.$ (35)

Putting Equations (31) and (35) into Equation (30), it follows that when
$y_{1}=\ldots=y_{i-1}=0$, then we have

$\displaystyle\tilde{P}(Y_{i}=1|y_{1},\ldots y_{i-1})$
$\displaystyle=\frac{P_{i}\prod\limits_{1\leq
j<i}P(y_{j}|y_{1},\ldots,y_{j-1})}{\prod\limits_{1\leq
j<i}P(y_{j}|y_{1},\ldots,y_{j-1})-P(\overline{0})}$ (36)

For the special case of $i=1$, it is clear that

$\tilde{P}(Y_{1}=1)=\tilde{P}(A_{1}^{(i)}),$ (37)

and since $A_{1}^{(i)}$ does not include the zero vector, according to the
definition of distribution $\tilde{P}(.)$ in Equation (24) we have

$\displaystyle\tilde{P}(A_{1}^{(i)})$ $\displaystyle=$
$\displaystyle\sum_{c\in A_{1}^{(i)}}\tilde{P}(c)$ (38) $\displaystyle=$
$\displaystyle\sum_{c\in A_{1}^{(i)}}P(c)\times\frac{1}{1-P(\bar{0})}$
$\displaystyle=$ $\displaystyle P(Y_{1}=1)\times\frac{1}{1-P(\bar{0})}$

∎

Therefore, it is obvious that using theorem 1 the model can sequentially
sample $k-1$ bits $y_{1},\ldots,y_{k-1}$ in a total time of $\mathcal{O}(k)$.

##  IV Experimental results

TABLE I: MMD scores of different generative models | Ego dataset | Protein dataset
---|---|---
Method | Deg. | Clus. | Orbit | Deg. | Clus. | Orbit
GraphRNN-S | 0.16 (0.08) | 0.06 (0.06) | 0.13 (0.09) | 0.21 (0.02) |  0.19 (0.05) | 0.15 (0.02)
GraphRNN | 0.13 (0.03) | 0.50 (0.03) |  0.03 (0.001) |  0.03 (0.004) | 1.05 (0.007) | 0.53 (0.02)
GRAN | 0.29 (0.03) |  0.05 (0.02) | 0.06 (0.01) | 0.05 (0.01) | 0.23 (0.05) | 0.13 (0.12)
Gransformer |  0.04 (0.01) | 0.19 (0.05) |  0.03 (0.01) | 0.06 (0.02) | 0.50 (0.13) |  0.10 (0.02)
| Train | Gransformer | GRAN | GraphRNN | GraphRNN-S
---|---|---|---|---|---
Ego |  |  |  |  |
Ego |  |  |  |  |
Protein |  |  |  |  |
Protein |  |  |  |  |
Figure 4: Sample graphs from training set and generated by different methods. TABLE II: Improvements caused by different parts of Gransformer - Ego dataset Method | Train NLL | Test NLL
---|---|---
Gransformer without graph structural information and MADE | 886.73 | 1021.68
Gransformer without graph structural information | 821.68 | 949.75
Gransformer | 789.33 | 907.12

This section presents our experiments to compare Gransformer with state-of-
the-art methods. The implementation of the proposed model and the datasets
used in our experiments are available anonymously from
https://github.com/Gransformer/Gransformer.

###  IV-A Datasets

We run our experiments on the following two real-world datasets used in [3].
We used 20% of each dataset as test data and the other 80% as the training
set.

Ego

A dataset containing 757 graphs representing documents (as nodes) and their
citations (as edges) extracted from the Citeseer network [42]. Graphs have
from 50 up to 399 nodes.

Protein

A dataset of 918 protein graphs [43]. Nodes are amino acids and geometrically
close nodes are connected in the graph. Graph sizes vary from 100 to 500.

For these datasets, we used models with $T=6$ attention layers with the hidden
size of $400$.

###  IV-B Evaluation Metrics

To compare the generated set of graphs with the actual test data, You et al.
[3] suggested using the Maximum Mean Discrepancy (MMD) of several graph
statistics to compare all moments of the empirical distribution of the graphs.
Similar to [3], we report MMD score for degree and cluster coefficient
distributions, as well as average orbit, counts statistics.

In addition, to study the effect of different ideas proposed in this paper, we
report training and test the negative log-likelihood of Gransformer, and
Gransformer without some of its modules.

###  IV-C Comparison With Other Generative Methods

In this section, we compare the statistical performance of Gransformer with
GraphRNN, GraphRNN-S [3], and GRAN [4] as three state-of-the-art graph
generation models. All of these three models are autoregressive. GraphRNN and
GraphRNN-S are based on recurrent neural networks, GRAN is designed based on
graph convolutional networks, and Gransformer is transformer-based. Table I
represents the results of different methods. It reports the mean and the
standard deviation of the MMD scores for the graphs generated by each method
after 2600, 2800, and 3000 training epochs. The statistical performance of
Gransformer is competitive with other methods according to these MMD scores,
especially MMD of degree distribution and average orbit counts.

Moreover, Table I shows that neither GraphRNN nor GraphRNN-S outperforms the
others by achieving lower MMD values in all cases. There are some cases where
their MMD values differ by an order of magnitude, e.g., the MMD of the
clustering coefficients for the two datasets Ego and Protein.

From the table I, it can be seen that although GRAN did not achieve the lowest
MMD values in many cases, it was very close to the lowest MMD values of the
other methods in most cases.

Also, the MMD values obtained by Gransformer are either better or close to the
lowest values in all cases except for the MMD values for the cluster
coefficients in both datasets. Moreover, Gransformer is the only method that
does not achieve the largest MMD value in any of the six columns.

Figure 4 illustrates several samples from the training set and some similar
ones from the set of generated graphs by different methods.

###  IV-D Effect of Different Parts

To study the impact of the different ideas proposed in this paper, we compare
the negative log-likelihood of Gransformer with and without using some of its
modules in training and testing. We consider the structural information of the
graph (proposed in Section III-C) as a module and evaluate the model without
this module. Also, we consider the MADE in the output layer (proposed in
Section LABEL:sec:_MADE) as another module and evaluate the model without this
module as well. Since the autoregressive models use the negative log-
likelihood as the loss function, we expect that removing any part of
Gransformer would increase the value of the negative log-likelihood for both
the training and test data. Table II indicates the results of the models after
3000 epochs of training on the Ego dataset. As anticipated, it confirms that
both the ideas of using MADE in the output layer and importing graph
structural properties into the model cause significant improvements on the
values of negative log-likelihood on both train and test data.

##  V Conclusion

In this paper, we proposed Gransformer, an autoregressive graph generation
model based on a single transformer encoder. We extended the transformer
encoder using several techniques. We put an autoregressive mask on the encoder
and modified the attention mechanism to utilize the presence or absence of
edges between nodes. We also imported graph structural properties to the model
by defining a familiarity measure between node pairs inspired by message
passing algorithms. We used the proposed familiarity measure both in the
attention layer and for graph-based positional embedding. Our experiments
showed that our method is competitive with other methods respecting the MMD
scores, especially for degree distribution and average orbit counts
statistics.

## References

  * [1] F. Faez, Y. Ommi, M. S. Baghshah, and H. R. Rabiee, “Deep graph generators: A survey,” _IEEE Access_ , vol. 9, pp. 106 675–106 702, 2021.
  * [2] Y. Li, O. Vinyals, C. Dyer, R. Pascanu, and P. Battaglia, “Learning deep generative models of graphs,” _arXiv preprint arXiv:1803.03324_ , 2018.
  * [3] J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec, “Graphrnn: Generating realistic graphs with deep auto-regressive models,” in _International conference on machine learning_. PMLR, 2018, pp. 5708–5717.
  * [4] R. Liao, Y. Li, Y. Song, S. Wang, W. Hamilton, D. K. Duvenaud, R. Urtasun, and R. Zemel, “Efficient graph generation with graph recurrent attention networks,” _Advances in Neural Information Processing Systems_ , vol. 32, pp. 4255–4265, 2019.
  * [5] H. Dai, A. Nazi, Y. Li, B. Dai, and D. Schuurmans, “Scalable deep generative modeling for sparse graphs,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 2302–2312.
  * [6] W. Kawai, Y. Mukuta, and T. Harada, “Scalable generative models for graphs with graph attention mechanism,” _arXiv preprint arXiv:1906.01861_ , 2019\.
  * [7] S. Fan and B. Huang, “Attention-based graph evolution,” _Advances in Knowledge Discovery and Data Mining_ , vol. 12084, p. 436, 2020.
  * [8] T. N. Kipf and M. Welling, “Variational graph auto-encoders,” _NIPS Workshop on Bayesian Deep Learning_ , 2016.
  * [9] M. Simonovsky and N. Komodakis, “Graphvae: Towards generation of small graphs using variational autoencoders,” in _International conference on artificial neural networks_. Springer, 2018, pp. 412–422.
  * [10] B. Samanta, A. De, G. Jana, V. Gómez, P. K. Chattaraj, N. Ganguly, and M. Gomez-Rodriguez, “Nevae: A deep generative model for molecular graphs,” _Journal of machine learning research. 2020 Apr; 21 (114): 1-33_ , 2020.
  * [11] A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann, “Netgan: Generating graphs via random walks,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 610–619.
  * [12] C. Yang, P. Zhuang, W. Shi, A. Luu, and P. Li, “Conditional structure generation through graph variational generative adversarial nets.” in _NeurIPS_ , 2019, pp. 1338–1349.
  * [13] N. De Cao and T. Kipf, “MolGAN: An implicit generative model for small molecular graphs,” _ICML 2018 workshop on Theoretical Foundations and Applications of Deep Generative Models_ , 2018.
  * [14] J. You, B. Liu, R. Ying, V. Pande, and J. Leskovec, “Graph convolutional policy network for goal-directed molecular graph generation,” _Advances in Neural Information Processing Systems_ , 2018.
  * [15] R. Trivedi, J. Yang, and H. Zha, “Graphopt: Learning optimization models of graph formation,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 9603–9613.
  * [16] J. Liu, A. Kumar, J. Ba, J. Kiros, and K. Swersky, “Graph normalizing flows,” _arXiv preprint arXiv:1905.13177_ , 2019.
  * [17] K. Madhawa, K. Ishiguro, K. Nakago, and M. Abe, “Graphnvp: An invertible flow model for generating molecular graphs,” _arXiv preprint arXiv:1905.11600_ , 2019.
  * [18] C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, and J. Tang, “Graphaf: a flow-based autoregressive model for molecular graph generation,” _arXiv preprint arXiv:2001.09382_ , 2020.
  * [19] M. Germain, K. Gregor, I. Murray, and H. Larochelle, “Made: Masked autoencoder for distribution estimation,” in _International Conference on Machine Learning_. PMLR, 2015, pp. 881–889.
  * [20] G. Papamakarios, T. Pavlakou, and I. Murray, “Masked autoregressive flow for density estimation,” _arXiv preprint arXiv:1705.07057_ , 2017.
  * [21] A. Khajenezhad, H. Madani, and H. Beigy, “Masked autoencoder for distribution estimation on small structured data sets,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2020.
  * [22] D. Flam-Shepherd, T. Wu, and A. Aspuru-Guzik, “Graph deconvolutional generation,” _arXiv preprint arXiv:2002.07087_ , 2020.
  * [23] Y. Li, L. Zhang, and Z. Liu, “Multi-objective de novo drug design with conditional graph generative model,” _Journal of cheminformatics_ , vol. 10, no. 1, pp. 1–24, 2018.
  * [24] M. Popova, M. Shvets, J. Oliva, and O. Isayev, “Molecularrnn: Generating realistic molecular graphs with optimized properties,” _arXiv preprint arXiv:1905.13372_ , 2019.
  * [25] D. Bacciu, A. Micheli, and M. Podda, “Graph generation by sequential edge prediction,” in _27th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN 2019_. ESANN (i6doc. com), 2019, pp. 95–100.
  * [26] ——, “Edge-based sequential graph generation with recurrent neural networks,” _Neurocomputing_ , vol. 416, pp. 177–189, 2020.
  * [27] N. Goyal, H. V. Jain, and S. Ranu, “Graphgen: a scalable approach to domain-agnostic labeled graph generation,” in _Proceedings of The Web Conference 2020_ , 2020, pp. 1253–1263.
  * [28] S. A. Shah and V. Koltun, “Auto-decoding graphs,” _arXiv preprint arXiv:2006.02879_ , 2020.
  * [29] A. Gamage, E. Chien, J. Peng, and O. Milenkovic, “Multi-motifgan (mmgan): Motif-targeted graph generation and prediction,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 4182–4186.
  * [30] J. Li, J. Yu, J. Li, H. Zhang, K. Zhao, Y. Rong, H. Cheng, and J. Huang, “Dirichlet graph variational autoencoder,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 5274–5283, 2020.
  * [31] A. Grover, A. Zweig, and S. Ermon, “Graphite: Iterative generative modeling of graphs,” in _International conference on machine learning_. PMLR, 2019, pp. 2434–2444.
  * [32] R. Assouel, M. Ahmed, M. H. Segler, A. Saffari, and Y. Bengio, “Defactor: Differentiable edge factorization-based probabilistic graph generation,” _arXiv preprint arXiv:1811.09766_ , 2018.
  * [33] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2014, pp. 701–710.
  * [34] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2016, pp. 855–864.
  * [35] M. Khajehnejad, “Simnet: Similarity-based network embeddings with mean commute time,” _PloS one_ , vol. 14, no. 8, p. e0221172, 2019.
  * [36] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_ , 2017.
  * [37] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [38] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _arXiv preprint arXiv:2005.14165_ , 2020.
  * [39] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 5998–6008.
  * [40] J. Alman and V. V. Williams, “A refined laser method and faster matrix multiplication,” in _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, 2021, pp. 522–539.
  * [41] V. Strassen, “Gaussian elimination is not optimal,” _Numerische mathematik_ , vol. 13, no. 4, pp. 354–356, 1969.
  * [42] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, “Collective classification in network data,” _AI magazine_ , vol. 29, no. 3, pp. 93–93, 2008.
  * [43] P. D. Dobson and A. J. Doig, “Distinguishing enzyme structures from non-enzymes without alignments,” _Journal of molecular biology_ , vol. 330, no. 4, pp. 771–783, 2003.

|  Ahmad Khajehnejad received his B.Sc. in software engineering and his M.Sc.
and Ph.D. degrees in Artificial Intelligence from Sharif University of
Technology, in 2010, 2012 and 2022, respectively. His research interests
include learning probabilistic models, deep generative models, and graph
machine learning.
---|---
|  Seyed Ali Osia received his B.Sc. degree in Software Engineering from
Sharif University of Technology in 2014, and his Ph.D. degree in Artificial
Intelligence from Sharif University of Technology in 2019. He is currently
Data Scientist at InnoBrain AB and Business Intelligence advisor at Cobel
Darou.
---|---
|  Mahmood Karimian is currently a Ph.D. Candidate of Artiﬁcial Intelligence
in Sharif University of Technology. He is also graduated with an M.Sc. degree
in Computer Engineering from the Department of Computer Engineering at Sharif
University of Technology. His main Research Interests are, Machine Learning,
Data Stream Classiﬁcation and transfer learning.
---|---
|  Hamid Beigy received the B.Sc. and M.Sc. degrees in computer engineering
from the Shiraz university in Iran, in 1992 and 1995, respectively. He also
received the Ph.D. degree in computer engineering from the Amirkabir
university of technology, Iran, in 2004. Currently, he is an Associate
Professor in department of computer engineering at the Sharif university of
Technology, Tehran, Iran. His research interests include theoretical machine
learning, large scale machine learning, and social networks.
---|---