Fusing Echocardiography Images and Medical Records for Continuous Patient Stratification

Nathan Painchaud, Pierre-Yves Courand, Pierre-Marc Jodoin, Nicolas Duchateau, and Olivier Bernard
Manuscript received January 15, 2024; revised XXXX XX, 2024. This work was supported in part by the NSERC's Discovery Grants and Canada Graduate Scholarships-Doctoral programs, the FRQNT Doctoral Training Scholarships and the French National Research Agency (LABEX PRIMES [ANR-11-LABX-0063] of Université de Lyon, within the program "Investissements d'Avenir" [ANR-11-IDEX-0007], and the MIC-MAC [ANR-19-CE45-0005] and ORCHID [ANR-22-CE45-0029-01] projects). For the purpose of open access, the authors have applied a CC BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.
N. Painchaud, P.-Y. Courand, N. Duchateau, and O. Bernard are with Univ Lyon, INSA‐Lyon, Université Claude Bernard Lyon 1, UJM-Saint Etienne, CNRS, Inserm, CREATIS UMR 5220, U1294, F‐69621, Lyon, France (e-mail: nathan.painchaud@usherbrooke.ca).
N. Painchaud and P.-M. Jodoin are with the Department of Computer Science, University of Sherbrooke, Sherbrooke, QC, Canada.
P.-Y. Courand is also with the Cardiology Dept., Hôpital Croix-Rousse, Hospices Civils de Lyon, Lyon, France, and the Cardiology Dept., Hôpital Lyon Sud, Hospices Civils de Lyon, Lyon, France
N. Duchateau is also with the Institut Universitaire de France (IUF).

Deep learning now enables automatic and robust extraction of cardiac function descriptors from echocardiographic sequences, such as ejection fraction or strain. These descriptors provide fine-grained information that physicians consider, in conjunction with more global variables from the clinical record, to assess patients' condition. Drawing on novel transformer models applied to tabular data (e.g., variables from electronic health records), we propose a method that considers all descriptors extracted from medical records and echocardiograms to learn the representation of a difficult-to-characterize cardiovascular pathology, namely hypertension. Our method first projects each variable into its own representation space using modality-specific approaches. These standardized representations of multimodal data are then fed to a transformer encoder, which learns to merge them into a comprehensive representation of the patient through a pretext task of predicting a clinical rating. This pretext task is formulated as an ordinal classification to enforce a pathological continuum in the representation space. We observe the major trends along this continuum for a cohort of 239 hypertensive patients to describe, with unprecedented gradation, the effect of hypertension on a number of cardiac function descriptors. Our analysis shows that i) pretrained weights from a foundation model allow to reach good performance (83% accuracy) even with limited data (less than 200 training samples), ii) trends across the population are reproducible between trainings, and iii) for descriptors whose interactions with hypertension are well documented, patterns are consistent with prior physiological knowledge.

Multimodal, contrastive learning, transformer, foundation model, cardiac ultrasound, health records, hypertension

§ INTRODUCTION

When assessing their patients' condition, physicians draw upon their expertise to integrate relevant complementary data from various sources such as medical images and Electronic Health Records (EHRs) [1] into an overall picture of the patient's status. Such a clinical workflow is typical in cardiology for the characterization of hypertension (HT), a complex yet multifaceted disease. While HT is the most prevalent cardiovascular disease (CVD), affecting around 1.28 billion adults worldwide [2], it presents a complex pathophysiology involving multiple mechanisms and is associated with other risk factors of CVDs. For these reasons, it is especially challenging to properly assess HT using machine and deep learning methods.

So far, most deep learning methods have focused on the combination of a limited number of modalities to solve highly-specific tasks such as the automatic extraction of shape and motion/deformation parameters from MR and ultrasound images [3, 4, 5]. Furthermore, methods that combine the detail-rich imaging data with other sources often sacrifice lots of information, for example resuming images to a few global biomarkers [1]. Thus, due to the sheer difficulty of combining wide varieties of heterogeneous data, research on comprehensive methods meant to aid higher-level diagnosis has lagged behind [6].

A category of deep learning models that has shown promising results in multimodal applications is transformers. Since the transformer architecture makes no assumptions about the structure of the data, different data sources can be combined naturally inside one framework [7]. On top of their innate suitability for multimodal applications, they are competitive with their domain-specific counterparts [7, 8]. Transformers even broke through in domains where deep learning based approaches previously struggled against simpler machine learning solutions, such as tabular data [9].

However, in practice, the lack of assumptions about the properties of the data means that transformers are trained on larger datasets, allowing them to learn the interactions within the data without any enforced prior [7, 10, 11]. While this adaptability is at the heart of their success, it clashes with more practical concerns about the availability of [labeled] data on which to train the models, especially in healthcare. A recent development that could unlock the potential of transformers for medical applications came with foundation models. These are models pretrained on enormous quantities of broad data to learn generic patterns, and which can adapt to downstream tasks with limited quantities of domain-specific [labeled] data [12].

In this paper, we propose to leverage transformers to tackle the problem of combining a limited amount of EHR data and fine-grained cardiac function descriptors extracted from 2D+time echocardiographic sequences to characterize HT. We build our method around the representation of EHR data in a tabular format, adding a hierarchical component to integrate image-based data to this representation. Additionally, we formulate the supervised objective to take full advantage of the feature-rich input by predicting a position along a pathological continuum, given only a few target classes.

Our main contributions in this work are:

* A framework to fuse tabular data extracted from EHRs with tabular and time-series parameters extracted from 2D+time Apical 4 Chambers (A4C) and A2C echocardiographic sequences[Code is available at URL to be disclosed upon publication];

* A constraint on the supervised training objective to learn a continuous stratification of the pathology despite a few discrete labels;

* A case study on hypertension that highlights valuable properties of our continuous stratification for other medical applications: i) it is reproducible between runs, and ii) it follows tendencies that are coherent w.r.t. prior physiological knowledge.

§ RELATED WORK

§.§ Multimodal Machine Learning

Multimodal learning encompasses multiple techniques for combining heterogeneous data for downstream tasks. For our HT application, we fuse complementary EHR and image data to learn a joint representation from which to make predictions [13]. For other applications, it might be preferable to learn separate coordinated representations for each modality, which are aligned using some similarity measure [13, 14].

While papers on multimodal learning are numerous, most apply to combinations of [non-medical] visual, text and audio data [13], since these modalities are cheap to acquire and abundant. Considering medical applications often target limited tabular and image data, they are ill-suited to apply out-of-the-box methods that are meant to work with more data structured differently. Hager  recently proposed a multimodal framework for medical tabular and imaging data similar to ours [14], but used it for alignment rather than fusion. Despite these differences, we can still draw inspiration from the trends that have emerged across the field.

For multimodal fusion applications, mid-fusion approaches have shown the most favorable results [15]. They consist in first processing modalities separately before their features are joined and processed further. Therefore, our method's tokenization module presented in <ref> is based upon this idea.

Another takeaway from the literature is the intrinsic advantages of transformers for multimodal applications [7]. Indeed, the lack of assumptions regarding the structure of the data allows them to scale well to different modalities, compared to the spatial structure bias of convolutional networks. In light of this, our data fusion pipeline  described in <ref> is built around the transformer framework.

§.§ Patient Stratification

The task of integrating comprehensive patients' data to predict the outcome or pathological stage of patients is known as stratification [16]. Often, stratification models use large quantities of unstructured EHR data or medical images to unveil emerging patterns, as recently demonstrated on the EHRs of more than 1.6 million patients [11]. However, studies have begun to highlight that models with such broad scopes risk under-performing on rare subtypes [17]. This shortcoming of broad models justifies the existence of methods with more targeted applications, for which available data is typically labeled but much more rare.

For applications aimed at CVDs stratification, including HT, most algorithms use exclusively imaging data to quantify patient risk based on reference labels [16, 18]. Parallel to supervised risk prediction, some works tackled unsupervised phenotyping, using representation learning and clustering. Some used tabular data rather than images [19] or specifically targeted HT [20]. While this approach is promising to further our understanding of complex pathologies, from a predictive standpoint it lacks the interpretability of established clinical indices/guidelines. Thus, stratification of HT remains mostly framed as a classification/clustering problem. A drawback of these latter approaches is that they fail to exploit the information from the ordering of the labels, e.g. from best to worst outcome.

This loss of information explains why some works formulate stratification as an ordinal classification — also called ordinal regression — problem, where the ordering of the labels is taken into account. Unfortunately, such methods usually implied more complex models and/or optimizations, and practical implementations were limited to linear models [21]. However, ordinal classification was recently adapted to deep learning in a relevant and simple formulation applicable on top of any feature-extractor architecture [22].

§ METHOD

Schematic representation of our multimodal fusion pipeline. The echocardiograms are segmented (1a) and descriptors are extracted from these segmentations (1b). In parallel, health records data is organized into categorical and scalar descriptors (2). Time-series descriptors (w.r.t. the cardiac cycle) and tabular descriptors are processed into individual embeddings using modality-specific methods (3a,3b). The embeddings are then fed to a transformer encoder (4a) trained to predict a probability distribution that takes into account the ordering of the target classes (5). The learned representation can finally be analyzed w.r.t. the predicted stratification (6) or visualized using the PaCMAP dimensionality reduction algorithm [23].

We provide a schematic description of our pipeline in <ref>. The echocardiograms are first segmented (1a) and numerical and time-series descriptors are extracted (1b). For health records data, we manually extracted categorical (e.g. sex, medical history, etc.) and numerical descriptors (e.g. age, BMI, etc.) from EHRs and a posterior assessment by a cardiologist (2).

Our approach for modeling multimodal interactions is somewhat similar to the hierarchical attention (multi-to-one stream) described in [7]. Each modality is independently processed (3a, 3b), then concatenated and fed to an encoder (4a) that performs data fusion and outputs a joint embedding for downstream tasks.

Since we are interested in learning a meaningful latent representation at the output of the encoder, we use a supervised training pipeline with two adjustments. First, we add a self-supervised contrastive objective (4b) to learn semantically meaningful features in the representation. The second change concerns the supervised prediction of the stratification labels, a pretext task meant to integrate the stratification notion in the latent representation. We formulate this task as an ordinal classification problem (5)
to obtain a continuous value between 0 (healthy) and 1 (severe disease) for each patient, indicating the model's prediction of their position on the pathological continuum.

In the following sections, we describe steps 3 through 5 illustrated in <ref>. Since steps 1-2 and 6 are domain/application-specific and relate to implementation details and post hoc evaluation, they are further explained in <ref>.

§.§ Multimodal Tokenization (Step 3)

From the application's perspective, our framework operates on images and EHR data. As mentioned above, this raw data is pre-processed to extract i) time-series descriptors from images (sequences of scalar values per patient), and ii) tabular descriptors from EHRs and images (global categorical and numerical variables per patient). Given the fundamentally different structures between these data types, we split the tokenization in two streams, one for each modality. After the streams have been tokenized, the sequences of tokens from each stream ($S_{\text{time}}$ and $S_{\text{tab}}$) are concatenated with a token into one sequence of length $S+1$ (cf. Tokens in <ref>).

Time-series Tokenizer

Tabular Tokenizer

Details of the two modality-specific tokenization methods for embedding multimodal data. The output of each method is a sequence of tokens of length equal to the number of input descriptors for each modality: $S_{\text{time}}$ and $S_{\text{tab}}$ for time-series and tabular descriptors, respectively.

§.§.§ Time-Series Tokenizer

Assuming that there are patterns in the evolution of time-series descriptors during the cardiac cycle, they require modality-specific processing. Therefore, we borrowed from how Pellegrini  integrated longitudinal data in their multimodal transformer [1]
for the design of our time-series tokenizer module, detailed in <ref>.

Starting with a vectorized input sequence $\var{t}\in R^T$, each scalar in $\var{t}$ is upscaled to the embedding size $D$ through a linear layer. This $D$-fold increase in dimensionality is not meant to transform the data, but rather to structure it so that downstream attention operations can more meaningfully process it. Thus, the sequence, now made up of $T$ tokens of size $D$, is combined to a positional encoding before being fed to a transformer block. Finally, the $T$ output tokens are reduced to a single $D$-dimensional token — the embedding for the time-series — using sequence pooling, i.e. a dynamic weighted averaging [24]. Since all the time-series descriptors represent the same type of data, i.e. cyclical 1D signals, the weights of their tokenizer are shared between time-steps and descriptors.

§.§.§ Tabular Tokenizer

The recent FT-Transformer by Gorishniy  [9] manages to provide  results on various tasks involving tabular data. Therefore, we adopted their Feature Tokenizer for tabular data, illustrated in <ref>.

Tabular data is represented so that each descriptor/column maps to a token. This means that each patient/row corresponds to a sequence of tokens that can be processed by a transformer. Thus, tokenization upsamples each descriptor to a $D$-dimensional token. For categorical descriptors, the upsampling operation is an embedding layer, i.e. a dictionary of embedding vectors for each label to add to a shared bias. For numerical descriptors, it is a linear layer. To learn distinct embeddings by descriptor, the parameters are not shared between descriptors.

§.§ Transformer Encoder (Step 4)

Given that the tokenization described in <ref> outputs a standard sequence of $D$-dimensional tokens, we use the transformer backbone from FT-transformer [9], described in <ref>, as feature extractor (cf. <ref> - 4a). This backbone is a specific configuration — number of layers, token size, etc. — of a vanilla transformer encoder.

Architecture of the transformer encoder from <ref>. It consists of a few standard transformer blocks in series. For experiments leveraging the XTab foundation model [10], the transformer blocks (encased in green in the figure) are provided pre-trained by XTab, but all other components are initialized randomly.

The combination of the transformer backbone with the tabular data representation grants flexibility to the model. Since input descriptors map to tokens, and transformers adapt to token sequences of various length, the same backbone can be re-used across different configurations of input data.

§.§.§ XTab Foundation Model

XTab's approach to generalization differs from that of other foundation models in domains such as natural language processing (NLP) and CV [10]. Since the meaning and context of tabular data varies between datasets, XTab foregoes learning a universal tokenizer, focusing instead on learning a weight initialization that generalizes well to downstream tasks. The pretrained weights provided by XTab only include the transformer blocks, indicated by the green box in <ref>, since they do not depend on the types and number of input features. Other parameters specific to the task or data, such as tokenizers or the  token, are learned from scratch.

To initialize the weights, XTab is trained, in a self-supervised manner, to reconstruct features from 52 tables from the AutoML benchmark (AMLB) [25]. Between tables, the size of the data varies greatly in terms of numbers of rows (between 10 and 10,000,000) and columns (between 4 and 14,892).

§.§.§ Self-Supervised Training

To mitigate the impact of limited labeled data, on top of pretrained weights, our method also includes a self-supervised contrastive objective, detailed in <ref>. Our contrastive pipeline relies on a mix of the SCARF [26] and MTR [27]
methods, and can be used both for pre-training and as an auxiliary term during finetuning.

Schematic representation of the training process of the transformer encoder from <ref> (4a,4b). In a fully-supervised setting, the training inference only processes the tokens through the encoder and extracts the  token [top]. The training can include a self-supervised contrastive loss, used either on its own for self-supervised pre-training or as an auxiliary term during supervised training [bottom]. In the latter case, we followed the SCARF approach for contrastive learning on tabular data [26], where one view corresponds to the unchanged tokens, and a corrupted view is generated by perturbing randomly sampled tokens. The encoding obtained from the unchanged branch [top] is passed along to be used for supervised classification further in the pipeline (cf.<ref>).

Our contrastive framework follows SCARF [26], where one of the two views of the data is perturbed by corrupting random tokens in the sequence. When used in conjunction with supervised learning, the encoding of the unchanged sequence can be used directly as input features for the downstream prediction head (cf. top of <ref>).

As for the corruption, we use MTR [27] to replace tokens to corrupt with a learnable  token shared by all descriptors. We chose this corruption approach because, while its performance is on par with SCARF's marginal sampling, it has two useful properties. First, since it does not sample random values, there is no risk of introducing incoherent values w.r.t. correlated values in the same row. Also, it standardizes the representation of missing data, so that we can use the same masking procedure to represent truly missing values, making the model robust to partially missing data.

§.§ Ordinal Classification (Step 5)

Details of the ordinal classification from <ref> (5). Given a feature vector $\var{x}$, the goal is to output probabilities over the classes $p(k \mid \var{x})$ following a unimodal distribution, meaning the probabilities should gradually decrease on both sides of the class predicted as most likely. Instead of predicting logits, the model predicts the parameter $p \in [0,1]$ of a binomial distribution. The binomial's probability mass function $B(k,p)$ is used to compute the probabilities for the $K$ classes, ensuring a unimodal distribution. Finally, the probabilities are passed through a softmax that sharpens/flattens the distribution, based on a temperature $\tau$ also learned by the model. In the end, the probabilities $p(k \mid \var{x})$ can be used with standard supervised classification losses.

One of the stated goals of our method is to leverage the feature-rich data to provide a continuous stratification of the HT severity, beyond the discrete labels provided by the expert cardiologist. To achieve this, we use the implicit information in the ordering of the target labels representing the severity assigned to the patients.

Indeed, learning a continuous representation along which the patients are ordered w.r.t. the severity labels would provide the continuous stratification we seek. To constrain our method to learn such a representation, we rely on the ordinal classification formulation proposed by Beckham and Pal [22], detailed in <ref>. Given the patient features extracted by the encoder, the linear prediction head predicts the parameter $p \in [0,1]$ of a binomial distribution, instead of class logits. The logits are computed analytically given $p$ using the binomial probability mass function. This allows the constrained prediction head to be used with traditional classification losses, such as cross-entropy.

Embedding colored w.r.t. the target degrees of hypertension, ordered in the legend by their severity (cf. <ref>). Some patients misclassified as controlled appear outside of their respective regions in the latent space, circled in the colors of their reference labels to highlight them.

Embedding colored w.r.t. the continuous stratification predicted by our method, where 0 (light) corresponds to healthy subjects, and 1 (dark) corresponds to the most hypertensive patients.

2D visualization, using the PaCMAP dimensionality reduction algorithm [23], of the 192D latent space learned by our transformer encoder, each point corresponding to a patient.

This formulation means $p$ directly determines the label with the most probability mass, and reducing/increasing $p$ shifts the center of the probability mass towards earlier/later labels in the ordering, respectively. Therefore, $p$ can be used directly as a continuous stratification value, instead of letting the classification head convert it to probabilities over the labels. <Ref> contrasts an embedding of the patients colored w.r.t. the discrete labels (a) and $p$ (b), illustrating how our method manages to learn a continuous representation structured around the labels. Note that, since the prediction head is linear, it forces a direction along the latent representation to correspond to the order of target labels, clearly visible in <ref>.

§ EXPERIMENTS AND RESULTS

§.§ Dataset

To test our pipeline, we used an in-house dataset of echocardiographic sequences and EHR data collected on a cohort of 239 hypertensive patients, named CARDINAL. The studies involving human participants were reviewed and approved by the local ethics committee. The participants provided their written informed consent to participate in this study. The CARDINAL imaging data was first introduced by Ling  to train a 2D+time nnU-Net using pseudo-labels [5].

For the current study, we included an additional 53 numerical and categorical descriptors, extracted from an EHR server or derived from other descriptors. The descriptors cover various aspects of the patients' condition, from general information (e.g. age, sex, etc.), medical history (e.g. stroke, tobacco, etc.), and results from biological reports (e.g. NT-proBNP, etc.) to measures from hospital stays (e.g. 24-hour ambulatory blood pressure) and transthoracic echocardiograms (e.g. A4C, PLAX, etc.). All the descriptors are listed, with accompanying descriptions, in tables V to VII in the supplementary files.

We used the HT severity descriptor as prediction target. It represents three degrees of hypertension assessed post hoc by an expert cardiologist. The labels, in ascending order of severity, are: i) wht (White coat HyperTension), no positive diagnosis of hypertension, ii) controlled, patients whose hypertension is under the recommended blood pressure level given their treatment, and iii) uncontrolled, patients who remain above the recommended blood pressure level despite treatment.

§.§ Experimental Setup

§.§.§ Echocardiograms Processing

As described in <ref>, the 2D+time echocardiographic images are first segmented, from which global and frame-by-frame cardiac function descriptors are automatically computed. For the segmentations, we use the  masks predicted by the nnU-Net from Ling  [5] as gold-standard. The descriptors, chosen by a cardiologist based on their relevance for HT, are the following:

* (2 descriptors) Left Ventricle (LV) volumes at End-Diastole (ED) and End-Systole (ES), using Simpson's biplane method [28];

* (1) Ejection Fraction (EF) from LV ED/ES;

* (8) Mininum/maximum myocardial curvature of the (A4C: septal/lateral, A2C: inferior/anterior) walls at ED [29], in both A4C and A2C views.

The time-series descriptors measured on both A4C and A2C views are:

* (2 × 1 descriptor) Surface of the LV;

* (2 × 1) LV length along its main axis (base to apex);

* (2 × 3) Global strain and (A4C: septal/lateral, A2C: inferior/anterior) strain;

* (2 × 2) (A4C: septal/lateral, A2C: inferior/anterior) average myocardial thickness;

We define the septal/lateral and inferior/anterior segments used for curvature, strain and myocardial thickness as the first 30% of the myocardium from each side of the base, just as in [29]. Because we are not doing tracking, we split the myocardium into longitudinal segments by sampling equidistant control points along the myocardium and selecting a subset of the control points.

§.§.§ Model Configuration

For models initialized with XTab's pretrained weights for the encoder, we follow their exact configuration [10], including an embedding size of 192. For the finetuning, we use the hyperparameters recommended in the original paper — AdamW, learning rate (LR) of 1e-4, batch size of 128 — over 2000 steps.

For models trained from scratch on CARDINAL, we optimized the most important configuration options, leading to smaller (embedding size of 8 vs 192, 2 attention heads vs 8) but deeper models (6 transformer blocks vs 3) to compensate for the limited data. For the training itself, we still use AdamW and a batch size of 128, but use a LR finder rather than a preset LR and train for 2500 steps. For models pretrained on CARDINAL, the pretraining lasts 2500 steps before finetuning with supervised labels for 500 steps, with other configurations unchanged.

For finetuning, all models use a combination of cross entropy (CE) for the supervised classification and normalized temperature-scaled CE (NT-Xent) for the auxiliary contrastive term. The best combination was determined empirically to be:

\begin{equation}
\label{eq:finetune_objective}
\loss = \alpha \loss_{\text{CE}} + \beta \loss_{\text{NT-Xent}},
\end{equation}

with $\alpha=1$ and $\beta=0.2$.

§.§ Pipeline Ablation Study

<Ref> present the results of an ablation study of the pipeline components w.r.t. stratification prediction results. The results reported correspond to the classification accuracy of the HT severity labels (cf. <ref>) on a hold-out test set of 48 patients, corresponding to around 20% of the dataset. In the following subsections, we analyze the changes in performance given the different configurations of each component, starting with the impactful ones. At the same time, we also discuss the properties of our method highlighted by these performance.

§.§.§ Foundation Model Trumps Domain-Specific Self-Supervised Training

Ablation study of the transformer encoder's weight initialization. Each result corresponds to the mean ± standard deviation over 50 models (5 configurations of inputs [cf. <ref>] ×10 trainings per configuration).

l c c c
Weights init.

Accuracy (%)
61.8 $\pm$ 6.1
60.9 $\pm$ 6.5
78.6 $\pm$ 3.9

The configuration that impacts the classification performance the most is the initialization of the weights, and its impact on the architecture's parameters, as shown by the results in <ref>. Before finetuning the models using the objective from <ref>, the weights are either initialized randomly (random), pretrained on CARDINAL using our contrastive setup on CARDINAL (pretrained), or taken from the XTab foundation model (xtab). For each weight initialization configuration, we also tested 5 different configurations of input descriptors (cf. <ref>), and provide the average results over these 5 configurations.

Models initialized from the xtab foundation model improve accuracy by 17.3 points on average when compared to corresponding configurations using either random or pretrained weights. Self-supervised training by itself does not help models to compete with xtab, with pretrained results close to random ones at only a 0.9 point difference.

These results highlight two messages. On one hand, while self-supervised learning has been proven to help learn useful features, its success on large amounts of data are difficult to replicate to applications with limited data. On the other hand, features learned on large amounts of data do generalize to new applications, i.e. HT stratification, that have nothing to do with the training data, i.e. the datasets from AMLB.

Given these results, in the following subsections, we focused on models initialized with weights from XTab.

§.§.§ Transformer Encoder Scales with Additional Parameters

Ablation study of the descriptors provided as input to the method. Each result corresponds to the mean ± standard deviation over 10 trainings.

l c
Input descriptors     Accuracy (%)

tab-13     71.3 $\pm$ 3.8

tab-13+time-series     74.4 $\pm$ 3.8

records     80.6 $\pm$ 4.2

tabular     83.5 $\pm$ 4.8

tabular+time-series     83.3 $\pm$ 2.8

To study how the predictions are impacted by the presence of certain descriptors, we organized descriptors according to their source and relevance for the application. tabular refers to all the tabular descriptors, and time-series to all the frame-by-frame descriptors. The descriptors can be filtered by leaving out those derived from transthoracic echocardiogram (TTE), noted as records. They can also only include the (13) descriptors most correlated with the target degrees of HT, noted as tab-13, based on statistical tests: Cramér's V and Kruskal-Wallis H for categorical and numerical descriptors, respectively.

<Ref> showcases the performance of the XTab-based models depending on the subsets of descriptors provided as input, here in ascending order of cardinality. The overall trend is that providing more descriptors as input leads to better accuracy, with tabular+time-series marking a 12.0 points improvement over tab-13. While the final addition of time-series to tabular descriptors does not improve results, we would argue that their performance are close enough, at only a 0.2 point difference, to indicate a plateau rather than a significant drop.

These results illustrate that additional tabular descriptors do provide valuable information, up to a ceiling where performance plateau. Once performance plateaus, adding input features does not markedly degrade the results. This is significant since previous models applied to EHR data pruned features to avoid introducing too much noise to the model [19, 30].

Given these results, in the following subsections, we used all the tabular+time-series descriptors, unless specified otherwise.

§.§.§ Modality-specific Processing Before Fusion Improves Results

Ablation study of the time-series modality-specific processing. Each result corresponds to the mean ± standard deviation over 10 trainings.

l cc cc

Accuracy (%)
70.2 $\pm$ 4.4
74.4 $\pm$ 3.8
81.0 $\pm$ 4.7
83.3 $\pm$ 2.8

We stated in <ref> that time-series descriptors require modality-specific processing. Here we validate this assumption experimentally. To do so, we compared our time-series transformer, described in <ref>, to a simple linear projection that adapts the temporal resolution of the time-series $\var{t}$ to the tokens' $D$-dimensional embedding.

The results of this ablation study are provided in <ref>. We ran the comparison on the two sets of input descriptors that include time-series descriptors, tab-13+time-series and tabular+time-series. The linear projection degraded the performance in both cases, for an average drop of 3.3 points. Even though the changes are not as striking as for the weight initialization and input descriptors configurations, they confirm that more complex descriptors, like time-series, benefit from modality-specific processing before being fused in the modality-agnostic backbone.

§.§.§ Similar Accuracy with Ordinal Classification

Ablation study of the ordinal classification. Each result corresponds to the mean ± standard deviation over 10 trainings.

l c c
Probability constraint

Accuracy (%)
83.8 $\pm$ 4.0
83.3 $\pm$ 2.8

The final component left to discuss is ordinal classification. Beckham and Pal warned that their formulation does not systematically outperform a cross-entropy baseline on top-1 accuracy, but rather that it regularizes to ensure good top-$k$ accuracy [22]. <Ref> compares performance when the probability distribution over the labels is obtained using a softmax baseline to when a binomial ordinal constraint (binom) is used. Our results support the findings of Beckham and Pal, with binom being on average 0.5 points behind the softmax baseline. Nonetheless, given the trivial difference in accuracy, the continuous stratification enabled by this formulation, discussed in detail in <ref>, is undoubtedly worth it.

§.§ Continuous Stratification Interpretability

Based on the ablation study in <ref>, we selected the best configuration on average for each component, consisting of i) an XTab-based model, ii) trained on tabular+time-series descriptors, iii) with transformer blocks in the time-series tokenizer, and iv) a binomial constraint on the predicted labels' probabilities. Since we trained each model configuration 10 times, we also selected the most representative of the 10, defined as the model with the smallest MAE between its predicted $p$ for each patient and the average $p$ across the 10 models. We can define this as:

\begin{align}
& e^* = \argmin_{e} \text{score}_{\text{model}}(e), \quad \forall e \in E \label{eq:variability_score:best_model}\\
\text{with} \quad & \text{score}_{\text{model}}(e) = \frac{1}{ | \mathcal{X} |} \sum^{\mathcal{X}}_{\var{x}} \text{score}_{\text{patient}}(e,\var{x}) \,, \label{eq:variability_score:model_score}\\
& \text{score}_{\text{patient}}(e,\var{x}) = \left| e(\var{x}) - \frac{1}{ | E | } \sum^{E}_{e'} e'(\var{x}) \right| \,, \label{eq:variability_score:patient_score}
\end{align}

where $e^*$ is the representative model, $\mathcal{X}$ is the set of all patients, $E$ is the set of (10) encoders $e$ that output a stratification value $p \in [0,1]$ given a patient $\var{x}$.

In the following subsections, we study the properties of this model's latent representation w.r.t. the continuous stratification goal and the application to HT characterization.

§.§.§ Reproducible Stratification Between Trainings

When computing the score defined in <ref> on the best configuration's models, we obtain an average score of 0.054 $\pm$ 0.018, with the most representative model $e^*$ reaching 0.031. Since the score is the MAE between models on the predicted stratification $p \in [0,1]$ for each patient, it means that the models' predictions vary only by around 5%. Given that, to the best of our knowledge, no previous work regarding classifying/phenotyping cardiovascular populations studied the robustness of their representation to random trainings [19, 30, 20], we consider this result significant.

Visualization of the continuous stratification prediction's standard deviation across multiple trainings of the same model w.r.t. the predictions of the most representative model (cf. <ref>). The standard deviation tends to increase for patients near the frontier between 2 labels, especially between controlled (orange) and uncontrolled (green), meaning that the models disagree more on ambiguous patients.

To understand where the variability between models comes from, we use the standard deviation (SD) across models of the result of <ref>, on a per patient basis. <Ref> plots this SD on each patient w.r.t. the stratification predicted by $e^*$. This highlights that the variability is not constant along the stratification domain, e.g. a uniform band. No pattern emerges in the transition from wht to controlled patients. We attribute this to the models not being as confident in their predictions for wht patients to start with, the SD being between 0.06-0.10, at or above the 0.065 on average over the whole dataset. This is most likely a consequence of there being relatively few wht patients (n=21). Nonetheless, looking at controlled and uncontrolled patients, a clear pattern emerges. The variability is higher in the transition zone, i.e. between 0.6 and 0.8 on the x-axis, and gradually decreases the more the model is confident about its prediction, i.e. nearing 1 on the x-axis.

This result is desirable, because it shows that models agree less on patients that fall in between the representations of the target labels, for whom stratification is by definition more ambiguous. It is further proof that the representation learned by our model achieved the stated goal of stratifying the patients beyond the provided target labels.

§.§.§ Coherent Continuum w.r.t. Prior Physiological Knowledge

Finally, in <ref>, we study patterns in time-series descriptors using both the target labels and the continuous stratification. We focus on two descriptors, Global Longitudinal Strain (GLS) and Basal Septal Thickness (BST), that are important parameters of left ventricular function and remodeling [4, 29].

GLS measures the deformation of the myocardium as the [negative] ratio of the contraction along its contour w.r.t. when the ventricle is most dilated at ED. Cardiologists often use the smallest value of the GLS, the peak GLS, as a biomarker of systolic function, along with ejection fraction (EF), i.e. the ratio of the variation of the volume of the ventricle. However, using the full GLS curve, instead of the scalar peak GLS and EF, can provide a more detailed analysis of the specific mechanisms affected by HT [31]. The context is similar for the BST, which measures the thickness of the myocardium at the base of the septum, i.e. the wall between the left and right ventricles. This segment of the myocardium is typically thicker in patients suffering from HT, as a response to the increased pressure (afterload) from the side of the LV. BST is also typically measured statically in clinical workflows (from parasternal acquisitions), but again a study of its evolution during the cardiac cycle could provide additional insights.

Apical 4 Chamber (A4C) Global Longitudinal Strain (GLS) w.r.t. target labels

A4C GLS w.r.t. stratification prediction

Basal Septal thickness (BST - measured in A4C) w.r.t. target labels

BST (measured in A4C) w.r.t. stratification prediction

Embedding using PaCMAP (cf. <ref>) colored w.r.t. stratification prediction bins. The bins are in ascending order of HT severity. They were obtained by dividing the stratification $\in [0,1]$ into $m=6$ equal intervals. Of note is the fact that PaCMAP's non-linearity complicates the visualization of the bins. In the 192-dimensional feature space, there exists a linear direction along which the bins are strictly ordered. In the 2D embedding, some bins overlap each other, explaining why the illustrative isocontour lines group some bins together.

Illustration of the repercussions of HT severity on cardiac function descriptors. Each plot shows the average curve for one cardiac function descriptor by groups of patients (the size of which are specified in the legend). The patient groups are determined either based on the 3-steps gradation provided by a cardiologist [(a) and (c)], or based on bins along the stratification predicted by our method [(b) and (d)]. (e) represents the same embedding as in <ref>, but w.r.t. the stratification bins. Both gradations display the same range of phenotypes, but that the continuous stratification describes in more incremental steps the evolution from normotensive cases (blue in [(a) and (c)], pale pink in [(b) and (d)]) to the severe HT (green in [(a) and (c)], darkest purple in [(b) and (d)]).

<Ref> present average GLS curves over target labels and a discretized version of the continuous stratification, respectively. The continuous stratification highlights that intermediate cases, bins 1-3, have altered post-systolic relaxation while still exhibiting normal peak GLS. The less severe bin 1 eventually catches up to the normotensive bin 0, around 0.7 on the x-axis. The continuous stratification also differentiates between more severe cases of HT that have similarly diminished peak GLS, bins 4 and 5, based on their post-systolic relaxation, which is further slowed in bin 5. While the overall tendencies of diminished peak GLS and slowed post-systolic relaxation can also be observed with the target labels, the latter case lacks the detailed breakdown the continuous stratification affords.

<Ref> show similar curves, but for septal thickness. Similar global tendencies are again observed on both the target labels and the continuous stratification, with the BST being directly correlated to the HT severity. The normotensive bin 0 displays lower BST than the wht target label, where the average includes more borderline subjects. The other point of note is the shift in peak thickness towards later in the cycle, the more severe the HT is. Once again, this is more apparent with the continuous stratification given the slightly earlier/later peaks at both ends of the spectrum.

Thus, overall, it is possible to extract phenotypes from the stratification that are coherent with prior physiological knowledge, i.e. the phenotypes corresponding to the target labels. On top of that, the continuous predictions allow more detailed analysis of the transitions between established phenotypes.

§ DISCUSSION AND CONCLUSION

In this work, we proposed a framework for fusing multimodal tabular and 2D+time echocardiograms to learn a stratification of patients, given limited data with categorical labels. The framework is designed to target difficult-to-characterize pathologies by, on one hand, combining complementary data from multiple sources aggregated in patients' medical records, and, on the other hand, projecting the patients along an interpretable pathological continuum.

We built our approach to multimodal fusion around tabular transformers. Imaging data is integrated as additional scalar descriptors and time-series descriptors that are first processed independently, reminiscent of mid-fusion. We also leveraged a foundation model for tabular data, which vastly outperformed contrastive learning on our limited dataset. Finally, we formulated an ordinal classification objective to integrate the order of the labels in the structure of the latent representation.

Relative to previous works, our approach stands out by working with tabular and imaging data, and by predicting a more precise stratification of patients than it was trained on. The work most similar to ours comes from Hager  [14], which also proposed a contrastive framework for multimodal tabular and imaging data. In their case, they aligned the representations of both modalities to use tabular features to help structure the image representation. They then applied their model to unimodal inference on images. Compared to them, we target a different application. We focus on difficult-to-characterize pathologies, like HT, where imaging data is not sufficient on its own and must be complemented by as much EHR data as possible. This is evidenced by the fact that our performance improved the most with more tabular data, rather then when adding imaging data.

§.§ Limitations

To mitigate the impact of the limited application-specific data at our disposal, we mixed different techniques. We used pretrained weights from a foundation model to transfer knowledge learned on vast amounts of data. We also used a contrastive framework to structure the learned representation with more than the provided labels.

However, while these techniques did reach good prediction performance and a meaningful representation, improvements could still be made to further refine the results. As such, the impact of contrastive learning in our framework is not on par with reports from other works [26, 14]. Future work could look into other self-supervised objectives, such as reconstruction [10].

Another component that did not improve results as much as expected was the addition of time-series descriptors extracted from images. It can partially be explained by the redundancy with tabular descriptors, some of which are derived from images. Still, apart from the modality-specific transformer, parts of how these tokens are combined in the model could be investigated. An example would be implementing mid-fusion in the joint encoder itself, by keeping attention within modalities in the initial blocks.

§.§ Conclusion

We presented a framework that learns a stratification of hypertensive patients by fusing 2D+time echocardiographic images with structured medical records data. We tailored our method to difficult-to-characterize pathologies by using ordinal classification to learn a continuous stratification. We showed that our continuous stratification provides better insights into how hypertension impacts clinically-relevant cardiac shape and motion descriptors than reference labels, which miss subtle alterations of these descriptors. In the end, we hope these insights inspire further works into characterizing full pathological continuums, rather than discrete stages, from all the multimodal data available in healthcare settings.

§ ACKNOWLEDGMENT

The authors thank Elisa Le Maout (ARC, Hôpital Lyon Sud, Hospices Civils de Lyon, Lyon, France) for her help with data collection for the CARDINAL dataset.

[1]
C. Pellegrini, N. Navab, and A. Kazi, “Unsupervised pre-training of graph transformers on patient population graphs,” Med Image Anal, vol. 89, p. 102895, Oct. 2023.

[2]
G. Mancia et al., “en-US2023 ESH Guidelines for the management of arterial hypertension The Task Force for the management of arterial hypertension of the European Society of Hypertension,” en-USJ. Hypertens., vol. 41, p. 1874, Dec. 2023.

[3]
M. Sermesant, H. Delingette, H. Cochet, P. Jaïs, and N. Ayache, “enApplications of artificial intelligence in cardiovascular imaging,” enNat Rev Cardiol, vol. 18, pp. 600–9, Aug. 2021.

[4]
I. M. Salte et al., “Artificial Intelligence for Automatic Measurement of Left Ventricular Strain in Echocardiography,” JACC Cardiovasc Imaging, vol. 14, pp. 1918–28, Oct. 2021.

[5]
H. J. Ling, N. Painchaud, P.-Y. Courand, P.-M. Jodoin, D. Garcia, and O. Bernard, “enExtraction of Volumetric Indices from Echocardiography: Which Deep Learning Solution for Clinical Use?” in enProc. FIMH, 2023, pp. 245–54.

[6]
P. Rajpurkar, E. Chen, O. Banerjee, and E. J. Topol, “enAI in health and medicine,” enNat Med, vol. 28, pp. 31–8, Jan. 2022.

[7]
P. Xu, X. Zhu, and D. A. Clifton, “Multimodal Learning With Transformers: A Survey,” IEEE PAMI, vol. 45, pp. 12 113–32, Oct. 2023.

[8]
Q. Wen et al., “enTransformers in Time Series: A Survey,” in enProc. IJCAI, vol. 6, 2023, pp. 6778–86.

[9]
Y. Gorishniy, I. Rubachev, V. Khrulkov, and A. Babenko, “Revisiting Deep Learning Models for Tabular Data,” in Proc. NeurIPS, vol. 34, 2021.

[10]
B. Zhu, X. Shi, N. Erickson, M. Li, G. Karypis, and M. Shoaran, “enXTab: Cross-table Pretraining for Tabular Transformers,” in enProc. ICML, 2023, pp. 43 181–204.

[11]
I. Landi et al., “enDeep representation learning of electronic health records to unlock patient stratification at scale,” ennpj Digit. Med., vol. 3, pp. 1–11, Jul. 2020.

[12]
S. Zhang and D. Metaxas, “On the challenges and perspectives of foundation models for medical image analysis,” Med Image Anal, vol. 91, p. 102996, Jan. 2024.

[13]
T. Baltrušaitis, C. Ahuja, and L.-P. Morency, “Multimodal Machine Learning: A Survey and Taxonomy,” IEEE PAMI, vol. 41, pp. 423–43, Feb. 2019.

[14]
P. Hager, M. J. Menten, and D. Rueckert, “enBest of Both Worlds: Multimodal Contrastive Learning With Tabular and Imaging Data,” in enProc. CVPR, 2023, pp. 23 924–35.

[15]
A. Nagrani, S. Yang, A. Arnab, A. Jansen, C. Schmid, and C. Sun, “Attention Bottlenecks for Multimodal Fusion,” in Proc. NeurIPS, vol. 34, 2021, pp. 14 200–13.

[16]
D. E. Schlesinger and C. M. Stultz, “enDeep Learning for Cardiovascular Risk Stratification,” enCurr Treat Options Cardio Med, vol. 22, p. 15, Jun. 2020.

[17]
L. Oakden-Rayner, J. Dunnmon, G. Carneiro, and C. Re, “Hidden stratification causes clinically meaningful failures in machine learning for medical imaging,” in Proc. ACM Int. Conf. Inf. Knowl. Manag., 2020, pp. 151–9.

[18]
S. Sanchez-Martinez et al., “Machine Learning for Clinical Decision-Making: Challenges and Opportunities in Cardiovascular Imaging,” Front Cardiovasc Med, vol. 8, 2022.

[19]
S. J. Shah et al., “Phenomapping for Novel Classification of Heart Failure With Preserved Ejection Fraction,” Circulation, vol. 131, pp. 269–79, Jan. 2015.

[20]
F. Loncaric et al., “enAutomated Pattern Recognition in Whole-Cardiac Cycle Echocardiographic Data: Capturing Functional Phenotypes with Machine Learning,” enJASE, vol. 34, pp. 1170–83, Nov. 2021.

[21]
T. Tran, D. Phung, W. Luo, and S. Venkatesh, “enStabilized sparse ordinal regression for medical risk stratification,” enKnowl Inf Syst, vol. 43, pp. 555–82, Jun. 2015.

[22]
C. Beckham and C. Pal, “enUnimodal Probability Distributions for Deep Ordinal Classification,” in enProc. ICML, 2017, pp. 411–9.

[23]
Y. Wang, H. Huang, C. Rudin, and Y. Shaposhnik, “Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMap, and PaCMAP for Data Visualization,” JMLR, vol. 22, pp. 1–73, 2021.

[24]
A. Hassani, S. Walton, N. Shah, A. Abuduweili, J. Li, and H. Shi, “Escaping the Big Data Paradigm with Compact Transformers,” Jun. 2022, arXiv:2104.05704 [cs.CV].

[25]
P. Gijsbers et al., “AMLB: an AutoML Benchmark,” Nov. 2023, arXiv:2207.12560 [cs.LG].

[26]
D. Bahri, H. Jiang, Y. Tay, and D. Metzler, “enScarf: Self-Supervised Contrastive Learning using Random Feature Corruption,” in enProc. ICLR, 2022.

[27]
S. Onishi and S. Meguro, “Rethinking Data Augmentation for Tabular Data in Deep Learning,” May 2023, arXiv:2305.10308 [cs.LG].

[28]
E. D. Folland, A. F. Parisi, P. F. Moynihan, D. R. Jones, C. L. Feldman, and D. E. Tow, “Assessment of left ventricular ejection fraction and volumes by real-time, two-dimensional echocardiography. A comparison of cineangiographic and radionuclide techniques.” Circulation, vol. 60, pp. 760–6, Oct. 1979.

[29]
M. Marciniak et al., “en-USSeptal curvature as a robust and reproducible marker for basal septal hypertrophy,” en-USJ. Hypertens., vol. 39, p. 1421, Jul. 2021.

[30]
Q. Zheng, H. Delingette, K. Fung, S. E. Petersen, and N. Ayache, “Pathological Cluster Identification by Unsupervised Analysis in 3,822 UK Biobank Cardiac MRIs,” Front Cardiovasc Med, vol. 7, 2020.

[31]
M. Cikes, G. R. Sutherland, L. J. Anderson, and B. H. Bijnens, “enThe role of echocardiographic deformation imaging in hypertrophic myopathies,” enNat Rev Cardiol, vol. 7, pp. 384–96, Jul. 2010.


# Upper and Lower Bounds for Generalized Wiener Indices on unicyclic graphs

Álvaro Martínez-Pérez(1) Facultad CC. Sociales de Talavera, Avda. Real Fábrica
de Seda, s/n. 45600 Talavera de la Reina, Toledo, Spain
<EMAIL_ADDRESS>and  José M. Rodríguez(2) Departamento de
Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30,
28911 Leganés, Madrid, Spain<EMAIL_ADDRESS>
###### Abstract.

The aim of this paper is to obtain new inequalities for a large family of
generalizations of the Wiener Index and to characterize the set of extremal
graphs with respect to them. Our main results provide upper and lower bounds
for these topological indices on unicyclic graphs.

(1) Supported in part by a grant from Ministerio de Ciencia, Innovación y
Universidades (PGC2018-098321-B-I00), Spain.

(2) Supported by a grant from Agencia Estatal de Investigación
(PID2019-106433GB-I00 / AEI / 10.13039/501100011033), Spain, and by the Madrid
Government (Comunidad de Madrid-Spain) under the Multiannual Agreement with
UC3M in the line of Excellence of University Professors (EPUC3M23), and in the
context of the V PRICIT (Regional Programme of Research and Technological
Innovation).

##  1\. Introduction

A topological descriptor is a single number that it is computed on the
molecular graph of a compound and represents some chemical structure in terms
of this graph. These descriptors are common and relevant in the field of
mathematical chemistry and especially in the QSPR/QSAR investigations.

When a topological descriptor correlates with a molecular property of certain
chemical compounds, then it is called a topological index. Thus, topological
indices capture some essential physicochemical property into a single number
and this can be used to analyze those properties. This can be very interesting
for practitioners. For example, although only about 1000 benzenoid
hydrocarbons are known, the number of theoretically possible benzenoid
hydrocarbons is huge. If we consider, for instance, the number of possible
benzenoid hydrocarbons with 35 benzene rings, it is $5.85\times 10^{21}$ [26].
Therefore, a good model capable of predicting physico-chemical properties of
currently unknown species is extremely useful.

The main reason for the use of topological indices is to obtain predictions of
some property of certain molecules (see, e.g., [9], [12], [14], [24]).
Whenever a topological descriptor shows a better correlation for some property
on some group of chemical compounds a new topological index appears. This way
hundreds of topological indices have been defined and studied, starting with
the seminal work by Wiener, [27], who found a correlation between his index
and paraffin boiling points.

The _Wiener index_ of $G$ is defined as

$W(G)=\sum_{\\{u,v\\}\subseteq V(G)}d(u,v),$

where $\\{u,v\\}$ runs over every pair of vertices in $G$.

Following this work, several versions of this index have been appearing since
then, each one better adapted for its purpose. Let us mention, for example,
the hyper-Wiener index, see [19, 23] or the Harari index [15, 22].

A natural problem in the study of topological indices is, given some fixed
parameters, to find the graphs that minimize (or maximize) their value on a
certain set of graphs satisfying the restrictions given by the parameters
(see, e.g., [1], [2], [4], [5], [6], [7], [8], [13]).

Herein, instead of doing this individually on each modified version of the
Wiener index we consider a natural generalization of it which encompasses
those mentioned above and try to work as generally as possible. In previous
works we used the same strategy with trees, see [20]. Now, we are considering
unicyclic graphs. A _unicyclic_ graph is a graph containing exactly one cycle
[16, p.41]. It is well known that if $G$ is a unicyclic graph with $n$
vertices, then $G$ has $n$ edges.

The aim of this paper is to obtain new inequalities for a large family of
topological indices restricted to unicyclic graphs, fixing or not the number
of pendant vertices, and to characterize the extremal unicyclic graphs with
respect to them. This problem, for other type of indices, was also addressed
in [21].

Throughout this work, $G=(V(G),E(G))$ denotes a (non-oriented) finite
connected simple (without multiple edges and loops) non-trivial
($E(G)\neq\emptyset$) graph. Note that the connectivity of $G$ is not an
important restriction, since every molecular graph is connected.

##  2\. Wiener index and its generalizations

Motivated by the Wiener index, Randić introduced in [23] an extension of the
Wiener index for trees, and this has come to be known as the _hyper-Wiener
index_. In [19], this extension was generalized to graphs as

$WW(G)=\frac{1}{2}\sum_{\\{u,v\\}\subseteq
V(G)}d(u,v)+\frac{1}{2}\sum_{\\{u,v\\}\subseteq V(G)}d(u,v)^{2}.$

$WW(G)$ has been useful in correlations (see, e.g., [11] and the references
therein). For information about the hyper-Wiener index in mathematics see,
e.g., [3], [11], [17].

Also, it is interesting to generalize the Wiener index in the following way

$W^{\lambda}(G)=\sum_{\\{u,v\\}\subseteq V(G)}d(u,v)^{\lambda},$

with $\lambda\in\mathbb{R}$. Obviously, if $\lambda=1$, then $W^{\lambda}$
coincides with the ordinary Wiener index $W$. Note that $W^{-2}$ is the Harary
index; $W^{-1}$ is the reciprocal Wiener index; the quantity $W^{2}$ is
closely related to the hyper-Wiener index, since $WW=(W^{1}+W^{2})/2$. Another
topological index, proposed in [25] is expressed in terms of $W^{1}$, $W^{2}$
and $W^{3}$ as $(2W^{1}+3W^{2}+W^{3})/6$. See [18] for more connections of the
same kind.

Three different variants of the $q$-Wiener index ($q>0,\,q\neq 1$) were
defined in [28] as

$\displaystyle W_{1}(G,q)$ $\displaystyle=\sum_{\\{u,v\\}\subseteq
V(G)}[d(u,v)]_{q},$ $\displaystyle W_{2}(G,q)$
$\displaystyle=\sum_{\\{u,v\\}\subseteq V(G)}[d(u,v)]_{q}\,q^{L-d(u,v)},$
$\displaystyle W_{3}(G,q)$ $\displaystyle=\sum_{\\{u,v\\}\subseteq
V(G)}[d(u,v)]_{q}\,q^{d(u,v)},$

where $L$ is the diameter of $G$, and

$[k]_{q}=\frac{1-q^{k}}{1-q}=1+q+q^{2}+\cdots+q^{k-1}.$

Since $\lim_{q\to 1}[k]_{q}=k$, we have

$\lim_{q\to 1}W_{1}(G,q)=\lim_{q\to 1}W_{2}(G,q)=\lim_{q\to
1}W_{3}(G,q)=W(G).$

Given any function $h:\mathbb{Z}^{+}\rightarrow\mathbb{R}$, the $h$-_Wiener
index_ of $G$ is defined as

$W_{h}(G)=\sum_{\\{u,v\\}\subseteq V(G)}h\big{(}d(u,v)\big{)},$

This general approach allows to study in a unified way the previous indices.

If $P_{n}$ is the path graph with $n$ vertices, then

$W_{h}(P_{n})=\sum_{1\leq i<j\leq n}h(j-i)=\sum_{k=1}^{n-1}(n-k)h(k).$

If $C_{n}$ is the cycle graph with $n$ vertices, then

  * •

if $n$ is odd,

$W_{h}(C_{n})=\sum_{j=1}^{\frac{n-1}{2}}nh(j),$

  * •

if $n$ is even,

$W_{h}(C_{n})=\sum_{j=1}^{\frac{n}{2}-1}nh(j)+\frac{n}{2}h\Big{(}\frac{n}{2}\Big{)}.$

Given $n\geq 4$, let $J_{n}$ be the graph obtained by identifying a vertex
from a cycle $C_{3}$ and the vertex with degree $n-3$ of a star graph with
$n-2$ vertices, $S_{n-2}$. Then,

$W_{h}(J_{n})=nh(1)+\frac{1}{2}n(n-3)h(2).$

Given $3\leq r\leq n$ and a function $h:\mathbb{Z}^{+}\rightarrow\mathbb{R}$,
let us define the function $F_{h}(r,n)$ as follows:

  * •

if $r$ is odd,

(2.1)
$F_{h}(r,n):=\sum_{j=1}^{\frac{r-1}{2}}rh(j)+\sum_{j=1}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j),$

  * •

if $r$ is even,

(2.2)
$F_{h}(r,n):=\sum_{j=1}^{\frac{r}{2}-1}rh(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=1}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)+\sum_{k=1}^{n-r}h\Big{(}\frac{r}{2}+k\Big{)}.$

Let $G_{r,n}$ be the graph obtained by identifying a vertex from a cycle
$C_{r}$ and a vertex with degree 1 of a path graph $P_{n-r+1}$. Note that
$G_{n,n}=C_{n}$.

As usual, if $a<b$, we use the convention

$\sum_{j=b}^{a}A(j)=0.$

Figure 1. The graph $G_{r,n}$ is obtained by identifying a vertex from a cycle
$C_{r}$ and a vertex with degree 1 of a path graph $P_{n-r+1}$.

######  Proposition 2.1.

Given $3\leq r\leq n$ and a function $h:\mathbb{Z}^{+}\rightarrow\mathbb{R}$,
then

$W_{h}(G_{r,n})=F_{h}(r,n).$

###### Proof.

Consider the graph $G_{r,n}$, let $w_{0}$ be the identified vertex which
belongs to the cycle and the path and let $w_{1},w_{2},\dots,w_{n-r}$ be the
vertices in the path $P_{n-r+1}$ with $d(w_{0},w_{k})=k$. See Figure 1.

Then,

$W_{h}(G_{r,n})=W_{h}(C_{r})+W_{h}(P_{n-r+1})+\sum_{w_{0}\neq v\in
C_{r},\,w_{0}\neq w_{i}\in P_{n-r+1}}h(d(v,w_{i})).$

Suppose $r$ is odd. Then, notice that for every $1\leq k\leq n-r$,

$\sum_{w_{0}\neq v\in C_{r}}h(d(v,w_{k}))=2\sum_{j=1}^{\frac{r-1}{2}}h(j+k).$

Thus,

$W_{h}(G_{r,n})=\sum_{j=1}^{\frac{r-1}{2}}rh(j)+\sum_{j=1}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j).$

In particular,

$F_{h}(3,n)=3h(1)+\sum_{j=1}^{n-3}(n-2-j)h(j)+2\sum_{k=1}^{n-3}h(k+1)=nh(1)+\sum_{j=2}^{n-2}(n-j)h(j).$

Suppose $r$ is even. Then, notice that for every $1\leq k\leq n-r$,

$\sum_{w_{0}\neq v\in
C_{r}}h(d(v,w_{k}))=2\sum_{j=1}^{\frac{r}{2}-1}h(j+k)+h\Big{(}\frac{r}{2}+k\Big{)}.$

Thus,

$W_{h}(G_{r,n})=\sum_{j=1}^{\frac{r}{2}-1}rh(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=1}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)+\sum_{k=1}^{n-r}h\Big{(}\frac{r}{2}+k\Big{)}.$

∎

######  Remark 2.2.

Since any graph with $n$ vertices has $\frac{1}{2}n(n-1)$ pairs of vertices,
we have

$\frac{1}{2}\,n(n-1)=n+\sum_{j=2}^{n-2}(n-j)=\sum_{j=1}^{\frac{r-1}{2}}r+\sum_{j=1}^{n-r}(n-r+1-j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}1$

if $r$ is odd, and

$\frac{1}{2}\,n(n-1)=n+\sum_{j=2}^{n-2}(n-j)=\sum_{j=1}^{\frac{r}{2}-1}r+\frac{r}{2}+\sum_{j=1}^{n-r}(n-r+1-j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}1+\sum_{k=1}^{n-r}1$

if $r$ is even.

######  Lemma 2.3.

Given $4\leq r\leq n$ with $r$ even and a strictly increasing function
$h:\mathbb{Z}^{+}\rightarrow\mathbb{R}$, then $F_{h}(3,n)>F_{h}(r,n)$. If $h$
is a strictly decreasing function, then $F_{h}(3,n)<F_{h}(r,n)$.

###### Proof.

First of all, note that the second statement is a consequence of the first
one, if we consider the function $-h$. Hence, we can assume that $h$ is a
strictly increasing function. We have

$\displaystyle F_{h}(3,n)>F_{h}(r,n)$
$\displaystyle\Leftrightarrow\quad\sum_{j=2}^{n-r}(n-j)h(j)+\sum_{j=n-r+1}^{n-2}(n-j)h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{\frac{r}{2}-1}rh(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}}h(j)+\sum_{j=2}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j).$

Case 1. Suppose $n-r<\frac{r}{2}-1$. Then,

$\displaystyle F_{h}(3,n)>F_{h}(r,n)$
$\displaystyle\Leftrightarrow\quad\sum_{j=n-r+1}^{n-2}(n-j)h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{n-r}h(j)+\sum_{j=n-r+1}^{\frac{r}{2}-1}rh(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}}h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle\Leftrightarrow\quad(n-r)h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}}(n-j-1)h(j)+\sum_{j=n-\frac{r}{2}+1}^{n-2}(n-j)h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{n-r}h(j)+\sum_{j=n-r+1}^{\frac{r}{2}-1}(r-n+j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j).$

Since $n-r<\frac{r}{2}-1$,

$\displaystyle 2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle=2h(2)+4h(3)+\cdots+2(n-r)h(n-r+1)+\cdots+2(n-r)h\Big{(}\frac{r}{2}\Big{)}$
$\displaystyle\quad+2(n-r-1)h\Big{(}\frac{r}{2}+1\Big{)}+\cdots+2h\Big{(}n-\frac{r}{2}-1\Big{)}.$

Let

$M=(n-r-1)+\frac{1}{2}\Big{(}\frac{3r}{2}-n-1\Big{)}\Big{(}\frac{3r}{2}-n\Big{)}+(n-r)(2r-n-1).$

Then, since $h$ is strictly increasing, it follows that

$\displaystyle\sum_{j=2}^{n-r}h(j)\,+$
$\displaystyle\\!\sum_{j=n-r+1}^{\frac{r}{2}-1}(r-n+j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle<Mh\Big{(}\frac{r}{2}\Big{)}+2(n-r-1)h\Big{(}\frac{r}{2}+1\Big{)}+\cdots+2h\Big{(}n-\frac{r}{2}-1\Big{)}$
$\displaystyle=Mh\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}-1}2\Big{(}n-\frac{r}{2}-j\Big{)}h(j).$

Therefore, since in

$(n-r)h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}}(n-j-1)h(j)+\sum_{j=n-\frac{r}{2}+1}^{n-2}(n-j)h(j)$

the function $h$ is evaluated always in numbers greater or equal than
$\frac{r}{2}$ and Remark 2.2 gives

$(n-r)+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}}(n-j-1)+\sum_{j=n-\frac{r}{2}+1}^{n-2}(n-j)=\sum_{j=2}^{n-r}1+\sum_{j=n-r+1}^{\frac{r}{2}-1}(r-n+j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}1,$

it suffices to check that

$\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}-1}2\Big{(}n-\frac{r}{2}-j\Big{)}h(j)<\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}-1}(n-j-1)h(j).$

Hence, it suffices to show for every $\frac{r}{2}+1\leq j\leq n-\frac{r}{2}-1$
that

$2n-r-2j<n-j-1,$

and this is equivalent to $n-r<j-1$, which follows from

$j-1\geq\frac{r}{2}>\frac{r}{2}-1>n-r.$

This finishes the proof of Case 1.

Case 2. Suppose $\frac{r}{2}-1=n-r$. Then,

$\displaystyle F_{h}(3,n)>F_{h}(r,n)$
$\displaystyle\Leftrightarrow\quad\sum_{j=2}^{\frac{r}{2}-1}\Big{(}\frac{3r}{2}-1-j\Big{)}h(j)+\sum_{j=\frac{r}{2}}^{\frac{3r}{2}-3}\Big{(}\frac{3r}{2}-1-j\Big{)}h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{\frac{r}{2}-1}\Big{(}\frac{3r}{2}-j\Big{)}h(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{r-1}h(j)+2\sum_{k=1}^{\frac{r}{2}-1}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle\Leftrightarrow\quad\sum_{j=\frac{r}{2}}^{\frac{3r}{2}-3}\Big{(}\frac{3r}{2}-1-j\Big{)}h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{\frac{r}{2}-1}h(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{r-1}h(j)+2\sum_{k=1}^{\frac{r}{2}-1}\sum_{j=1}^{\frac{r}{2}-1}h(k+j).$

Notice that

$\displaystyle 2\sum_{k=1}^{\frac{r}{2}-1}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle=2h(2)+4h(3)+\cdots+2\Big{(}\frac{r}{2}-1\Big{)}h\Big{(}\frac{r}{2}\Big{)}+2\Big{(}\frac{r}{2}-2\Big{)}h\Big{(}\frac{r}{2}+1\Big{)}+\cdots+2h(r-2)$
$\displaystyle=\sum_{j=2}^{\frac{r}{2}}2(j-1)h(j)+\sum_{j=\frac{r}{2}+1}^{r-2}2(r-1-j)h(j).$

Since $h$ is strictly increasing, it follows that

$\displaystyle\sum_{j=2}^{\frac{r}{2}-1}h(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{r-1}h(j)+2\sum_{k=1}^{\frac{r}{2}-1}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle\qquad<\Big{(}\frac{r}{2}-1\Big{)}\Big{(}\frac{r}{2}+2\Big{)}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{r-1}h(j)+\sum_{j=\frac{r}{2}+1}^{r-2}2(r-1-j)h(j).$

Thus, it suffices to check that for every $\frac{r}{2}+1\leq j$ we have
$2r-1-2j<\frac{3r}{2}-1-j$, which is direct.

Case 3. Suppose $\frac{r}{2}-1<n-r$. Then,

$\displaystyle F_{h}(3,n)>F_{h}(r,n)$
$\displaystyle\Leftrightarrow\quad\sum_{j=2}^{n-r}(r-1)h(j)+\sum_{j=n-r+1}^{n-2}(n-j)h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{\frac{r}{2}-1}rh(j)+\frac{r}{2}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-\frac{r}{2}}h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle\Leftrightarrow\quad\Big{(}\frac{r}{2}-1\Big{)}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-r}(r-2)h(j)+\sum_{j=n-r+1}^{n-2}(n-j)h(j)$
$\displaystyle\qquad\quad>\sum_{j=2}^{\frac{r}{2}-1}h(j)+\sum_{j=n-r+1}^{n-\frac{r}{2}}h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j).$

Since $\frac{r}{2}-1<n-r$,

$\displaystyle 2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle=2h(2)+4h(3)+\cdots+2\Big{(}\frac{r}{2}-1\Big{)}h\Big{(}\frac{r}{2}\Big{)}+\cdots+2\Big{(}\frac{r}{2}-1\Big{)}h(n-r+1)$
$\displaystyle\qquad+2\Big{(}\frac{r}{2}-2\Big{)}h(n-r+2)+\cdots+2h\Big{(}n-\frac{r}{2}-1\Big{)}$
$\displaystyle=\sum_{j=2}^{\frac{r}{2}}2(j-1)h(j)+\sum_{j=\frac{r}{2}+1}^{n-r}(r-2)h(j)+\sum_{j=n-r+1}^{n-\frac{r}{2}-1}(2n-r-2j)h(j).$

Since $h$ is strictly increasing, it follows that

$\displaystyle\sum_{j=2}^{\frac{r}{2}-1}h(j)+\sum_{j=n-r+1}^{n-\frac{r}{2}}h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r}{2}-1}h(k+j)$
$\displaystyle<\Big{(}\frac{r^{2}}{4}-2\Big{)}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=n-r+1}^{n-\frac{r}{2}}h(j)+\sum_{j=\frac{r}{2}+1}^{n-r}(r-2)h(j)+\sum_{j=n-r+1}^{n-\frac{r}{2}-1}(2n-r-2j)h(j).$

Therefore, since in

$\Big{(}\frac{r}{2}-1\Big{)}h\Big{(}\frac{r}{2}\Big{)}+\sum_{j=\frac{r}{2}+1}^{n-r}(r-2)h(j)+\sum_{j=n-r+1}^{n-2}(n-j)h(j)$

the function $h$ is evaluated always in numbers greater or equal than
$\frac{r}{2}$, it suffices to check that for every $n-r+1\leq j$ we have
$2n-r-2j+1\leq n-j$, which is immediate. ∎

######  Lemma 2.4.

Given $5\leq r\leq n$ with $r$ odd and a strictly increasing function
$h:\mathbb{Z}^{+}\rightarrow\mathbb{R}$, then $F_{h}(3,n)>F_{h}(r,n)$. If $h$
is a strictly decreasing function, then $F_{h}(3,n)<F_{h}(r,n)$.

###### Proof.

The second statement is a consequence of the first one, if we consider the
function $-h$. Therefore, we can assume that $h$ is a strictly increasing
function.

Let us recall that

$F_{h}(3,n)=nh(1)+\sum_{j=2}^{n-2}(n-j)h(j).$

Case 1. Suppose $n-r<\frac{r-1}{2}$. Then,

$\displaystyle F_{h}(r,n)=$
$\displaystyle\sum_{j=1}^{n-r}(n+1-j)h(j)+\sum_{j=n-r+1}^{\frac{r-1}{2}}rh(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j).$

Therefore,

$\displaystyle F_{h}(3,n)>F_{h}(r,n)$
$\displaystyle\Leftrightarrow\quad\sum_{j=n-r+1}^{n-2}(n-j)h(j)>\sum_{j=2}^{n-r}h(j)+\sum_{j=n-r+1}^{\frac{r-1}{2}}rh(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)$
$\displaystyle\Leftrightarrow\quad\sum_{j=\frac{r+1}{2}}^{n-2}(n-j)h(j)>\sum_{j=2}^{n-r}h(j)+\sum_{j=n-r+1}^{\frac{r-1}{2}}(j-n+r)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j).$

Since $n-r<\frac{r-1}{2}$,

$\displaystyle 2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)$
$\displaystyle=2h(2)+\cdots+2(n-r)h(n-r+1)+\cdots$
$\displaystyle\quad+2(n-r)h\Big{(}\frac{r+1}{2}\Big{)}+\cdots+2h\Big{(}n-\frac{r}{2}-\frac{1}{2}\Big{)}.$

Let

$N=n-r-1+\frac{1}{2}\frac{(3r-2n-1)}{2}\frac{(3r-2n+1)}{2}+(n-r)(n-r+1)+(3r-2n-1)(n-r).$

Therefore, since $h$ is strictly increasing,

$\displaystyle\sum_{j=2}^{n-r}h(j)+\sum_{j=n-r+1}^{\frac{r-1}{2}}(j-n+r)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)$
$\displaystyle\qquad<Nh\Big{(}\frac{r+1}{2}\Big{)}+\sum_{j=\frac{r+3}{2}}^{n-\frac{r}{2}-\frac{1}{2}}2\Big{(}n-\frac{r}{2}+\frac{1}{2}-j\Big{)}h(j).$

Thus, it suffices to check that for every $\frac{r+3}{2}\leq j\leq
n-\frac{r}{2}-\frac{1}{2}$ we have

$2n-r+1-2j<n-j,$

and this is equivalent to $n-r<j-1$, which is immediate since

$j-1\geq\frac{r+1}{2}>n-r.$

Case 2. Suppose $\frac{r-1}{2}\leq n-r$. Then,

$\displaystyle F_{h}(r,n)$
$\displaystyle=\sum_{j=1}^{\frac{r-1}{2}}rh(j)+\sum_{j=1}^{\frac{r-1}{2}}(n-r+1-j)h(j)+\sum_{j=\frac{r+1}{2}}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)$
$\displaystyle=\sum_{j=1}^{\frac{r-1}{2}}(n+1-j)h(j)+\sum_{j=\frac{r+1}{2}}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j).$

Therefore,

$\displaystyle F_{h}(3,n)>F_{h}(r,n)$
$\displaystyle\Leftrightarrow\quad\sum_{j=\frac{r+1}{2}}^{n-2}(n-j)h(j)>\sum_{j=2}^{\frac{r-1}{2}}h(j)+\sum_{j=\frac{r+1}{2}}^{n-r}(n-r+1-j)h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)$
$\displaystyle\Leftrightarrow\quad\sum_{j=\frac{r+1}{2}}^{n-r}(r-1)h(j)+\sum_{j=n-r+1}^{n-2}(n-j)h(j)>\sum_{j=2}^{\frac{r-1}{2}}h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j).$

Since $\frac{r-1}{2}\leq n-r$,

$\displaystyle 2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)$
$\displaystyle=2h(2)+\cdots+2\Big{(}\frac{r-1}{2}\Big{)}h\Big{(}\frac{r+1}{2}\Big{)}+\cdots$
$\displaystyle\quad+2\Big{(}\frac{r-1}{2}\Big{)}h(n-r+1)+\cdots+2h\Big{(}n-\frac{r}{2}-\frac{1}{2}\Big{)}.$

Let $N^{\prime}=\frac{r^{2}+2r-7}{4}$. Therefore, since $h$ is strictly
increasing,

$\sum_{j=2}^{\frac{r-1}{2}}h(j)+2\sum_{k=1}^{n-r}\sum_{j=1}^{\frac{r-1}{2}}h(k+j)<N^{\prime}h\Big{(}\frac{r+1}{2}\Big{)}+\sum_{j=\frac{r+3}{2}}^{n-r}(r-2)h(j)+\sum_{j=n-r+1}^{n-\frac{r}{2}-\frac{1}{2}}(2n-r+1-2j)h(j).$

Thus, it suffices to check that for every $\frac{r+3}{2}\leq j\leq n-r$ we
have $r-2\leq r-1$, and for every $n-r+1\leq j\leq n-\frac{r}{2}-\frac{1}{2}$
we have

$2n-r+1-2j\leq n-j\quad\Leftrightarrow\quad n-r+1\leq j,$

which is trivial. ∎

######  Example 2.5.

Notice that given $3<r\leq n$ and a strictly increasing function
$h:\mathbb{Z}^{+}\rightarrow\mathbb{R}$, although $F_{h}(3,n)>F_{h}(r,n)$,
$F_{h}(r,n)$ is not necessarily decreasing on $r$. For example, suppose $h$ is
the identity map. Then
$F_{h}(12,13)=13h(1)+14(h(2)+h(3)+h(4)+h(5))+8h(6)+h(7)$ and
$F_{h}(11,13)=13h(1)+14h(2)+15(h(3)+h(4)+h(5))+4h(6)+2h(7)$. Thus,
$F_{h}(12,13)-F_{h}(11,13)=4h(6)-h(3)-h(4)-h(5)-h(7)=24-3-4-5-7=5>0$ and
$F_{h}(12,13)>F_{h}(11,13)$.

Let us recall the following definitions from [10]. A vertex of degree at least
three in a graph $G$ will be called a _major_ vertex of $G$. Any end-vertex (a
vertex of degree one) $u$ of $G$ is said to be a _terminal_ vertex of a major
vertex $v$ of $G$ if $d_{G}(u,v)<d_{G}(u,w)$ for every other major vertex $w$
of $G$. The _terminal degree_ of a major vertex $v$ is the number of terminal
vertices of $v$. A major vertex $v$ of $G$ is called _exterior_ major vertex
if it has positive terminal degree. Let $\mathcal{M}(G)$ be the set of
exterior major vertices of $G$ having terminal degree greater than one.

The following result is elementary.

######  Lemma 2.6.

If $T$ is a tree, then $\mathcal{M}(T)=\emptyset$ if and only if $T$ is a path
graph.

Given a unicyclic graph $G$ and a vertex $v$ let us denote $G_{v}$ the
connected component of $G\setminus v$ intersecting the cycle. Then, the
complement $T_{v}:=G\setminus G_{v}$ is a tree (possibly being the the single
vertex $v$).

######  Theorem 2.7.

Let $G$ be a unicyclic graph with $n\geq 6$ vertices.

  * $(1)$

If $h$ is a strictly increasing function, then

$n\,h(1)+\frac{1}{2}n(n-3)\,h(2)\leq W_{h}(G)\leq F_{h}(3,n),$

the lower bound is attained if and only if $G=J_{n}$ and the upper bound is
attained if and only if $G=G_{3,n}$.

  * $(2)$

If $h$ is a strictly decreasing function, then

$F_{h}(3,n)\leq W_{h}(G)\leq n\,h(1)+\frac{1}{2}n(n-3)\,h(2),$

the lower bound is attained if and only if $G=G_{3,n}$ and the upper bound is
attained if and only if $G=J_{n}$.

###### Proof.

The second statement is a consequence of the first one, if we consider the
function $-h$. Hence, we can assume that $h$ is a strictly increasing
function.

Since $G$ is a unicyclic graph with $n$ vertices, there are $n$ edges and $n$
pairs of adjacent vertices. Thus, there are $\binom{n}{2}-n=\frac{1}{2}n(n-3)$
pairs of vertices at distance at least 2. The lower bound is attained if and
only if $T$ has diameter 2. Notice that this means that the cycle has at most
5 vertices and since $n\geq 6$ and any vertex which is not in the cycle is at
distance at most 2 from any vertex in it, the cycle is necessarily $C_{3}$.
Therefore, the lower bound is attained if and only if $G=J_{n}$.

Assume that $G$ is a unicyclic graph with $n$ vertices such that $W_{h}(G)$ is
maximal and let $C$ be the cycle.

Seeking for a contradiction, consider any vertex $v\in G$ such that $v$ is not
in the unique cycle and $deg(v)\geq 3$ or $v$ is in the cycle and $deg(v)\geq
4$. Then, there is an exterior major vertex $w$ in $T_{v}$ (where possibly
$v=w$). Hence, consider two terminal vertices of $w$, $u_{1},u_{2}$ with
$d(w,u_{1})=k$. Let us define new vertices $\\{v_{1},\dots,v_{k}\\}$ and let

$G^{\prime}:=\big{(}G\setminus[w,u_{1}]\big{)}\cup u_{2}v_{1}\cup
v_{1}v_{2}\cup\cdots\cup v_{k-1}v_{k}.$

Thus, it is immediate to see that, since $h$ is strictly increasing,
$W_{h}(G^{\prime})>W_{h}(G)$ leading to contradiction. Therefore, $deg(v)\leq
2$ for every vertex $v\notin C$, and $deg(v)\leq 3$ for every vertex $v\in C$.

Suppose there exist $v_{1},v_{2}\in C$ with $deg(v_{i})=3$ for $i=1,2$. Then,
$T_{v_{i}}$ is a path $[v_{i},u_{i}]$ with length $d([v_{i},u_{i}])=l_{i}$.
Let $D_{i}:=\sum_{v\in G\setminus\\{T_{v_{1}}\cup T_{v_{2}}\\}}d(v_{i},v)$ for
$i=1,2$. If $D_{i}<D_{j}$ and $l_{i}>l_{j}$, consider the vertex
$w\in[v_{i},u_{i}]$ such that $d(v_{i},w)=l_{j}$, let $s=l_{i}-l_{j}$ and let
us define new vertices $\\{w_{1},\dots,w_{s}\\}$. Then, let

$G^{\prime}:=\big{(}G\setminus[w,u_{i}]\big{)}\cup u_{j}w_{1}\cup
w_{1}w_{2}\cup\cdots\cup w_{s-1}w_{s}.$

Since $D_{i}<D_{j}$ and $h$ is strictly increasing, it follows that
$W_{h}(G^{\prime})>W_{h}(G)$ leading to contradiction. Thus, we may assume,
relabeling if necessary, that $D_{1}\leq D_{2}$ and $l_{1}\leq l_{2}$. Hence,
let us define new vertices $\\{a_{1},\dots,a_{l_{1}}\\}$ and let

$G^{\prime}:=\big{(}G\setminus[v_{1},u_{1}]\big{)}\cup u_{2}a_{1}\cup
a_{1}a_{2}\cup\cdots\cup a_{l_{1}-1}a_{l_{1}}.$

Since $D_{1}\leq D_{2}$, $l_{1}\leq l_{2}$ and $h$ is strictly increasing, it
follows that $W_{h}(G^{\prime})>W_{h}(G)$ leading to contradiction.

Therefore, $G$ is a unicyclic graph with at most one vertex with degree 3 and
$G=G_{r,n}$ where $r$ is the length of the cycle. By lemmas 2.3 and 2.4,
$G=G_{3,n}$. ∎

######  Corollary 2.8.

If $G$ is a unicyclic graph with $n\geq 6$ vertices, then

$n(n-2)\leq W(G)\leq 1+\sum_{k=1}^{n-2}(n-k)\,k=\frac{n^{3}-7n+12}{6},$

the lower bound is attained if and only if $G=J_{n}$ and the upper bound is
attained if and only if $G=G_{3,n}$.

## References

  * [1] B. Bollobás, P. Erdös, Graphs of extremal weights, Ars Comb. 50, 225–233 (1998).
  * [2] B. Bollobás, P. Erdös, A. Sarkar, Extremal graphs for weights, Discr. Math. 200, 5–19 (1999).
  * [3] G. G. Cash, Relationship between the Hosoya polynomial and the hyper-Wiener index, Appl. Math. Lett. 15 (2002) 893–895.
  * [4] R. Cruz, H. Giraldo, J. Rada, Extremal Values of Vertex–Degree Topological Indices Over Hexagonal Systems, _MATCH Commun. Math. Comput. Chem._ 70, 501–512 (2013).
  * [5] K. C. Das, Maximizing the sum of the squares of the degrees of a graph, _Discr. Math._ 285, 57–66 (2004).
  * [6] Z. Du, B. Zhou, N. Trinajstić, Minimum general sum–connectivity index of unicyclic graphs, _J. Math. Chem._ 48, 697–703 (2010).
  * [7] Z. Du, B. Zhou, N. Trinajstić, Minimum sum–connectivity indices of trees and unicyclic graphs of a given matching number, _J. Math. Chem._ 47, 842–855 (2010).
  * [8] C. S. Edwards, The largest vertex degree sum for a triangle in a graph, Bull. London Math. Soc. 9, 203–208 (1977).
  * [9] E. Estrada, L. Torres, L. Rodríguez, I. Gutman, An Atom–bond connectivity index: Modelling the enthalpy of formation of alkanes, _Indian J. Chem._ 37A, 849–855 (1998).
  * [10] A. Estrada-Moreno, J. A. Rodríguez-Velázquez, I. G. Yero, The $k$-metric dimension of a graph, _Appl. Math. Inform. Sci._ 9 (6) 2829–2840 (2015).
  * [11] I. Gutman, Relation between hyper-Wiener and Wiener index, Chem. Phys. Lett. 364 (2002) 352–356.
  * [12] I. Gutman, B. Furtula, Vertex–degree–based molecular structure descriptors of benzenoid systems and phenylenes, _J. Serb. Chem. Soc._ 77, 1031–1036 (2012).
  * [13] I. Gutman, B. Furtula, M. Ivanovic, Notes on Trees with Minimal Atom–Bond Connectivity Index, _MATCH Commun. Math. Comput. Chem._ 67, 467–482 (2012).
  * [14] I. Gutman, J. Tosovic, Testing the quality of molecular structure descriptors. Vertex–degreebased topological indices, _J. Serb. Chem. Soc._ 78(6) (2013) 805–810.
  * [15] O. Ivanciuc, T.S. Balaban, A.T. Balaban, Reciprocal distance matrix, related local vertex invariants and topological indices, J. Math. Chem., 12 (1993) 309–318.
  * [16] F. Harary, Graph Theory. Reading, MA, Addison-Wesley, 1994
  * [17] S. Klavzar, P. Zigert, I. Gutman, An algorithm for the calculation of the hyper-Wiener index of benzenoid hydrocarbons, Comput. Chem. 24 (2000) 229–233.
  * [18] D. J. Klein, I. Gutman, Wiener-Number-Related Sequences, J. Chem. Inf. Comput. Sci. 39 (1999) 534–536.
  * [19] D. J. Klein, I. Lukovits, I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Sci. 35 (1995) 50–52.
  * [20] A. Martínez-Pérez, J. M. Rodríguez, A Unified Approach to Bounds for Topological Indices on Trees and Applications. MATCH Commun. Math. Comput. Chem. 82:3 (2019) 679–698.
  * [21] A. Martínez-Pérez, J. M. Rodríguez, Upper and lower bounds for topological indices on unicyclic graphs. Submitted.
  * [22] D. Plavšić, S. Nikolić, N. Trinajstić, Z. Mihalić, On the Harary index for the characterization of chemical graphs, J. Math. Chem., 12 (1993) 235–250.
  * [23] M. Randić, Novel molecular descriptor for structure-property studies, Chem. Phys. Lett. 211 (1993) 478–483.
  * [24] M. Randić, D. Plavšić, N. Lerš, Variable connectivity index for cycle-containing structures, J. Chem. Inf. Comput. Sci. 41 (2001) 657–662.
  * [25] S. S. Tratch, M. I. Stankevich, N. S. Zefirov, Combinatorial Models and Algorithms in Chemistry. The Expanded Wiener Numbers – A Novel Topological Index, J. Comput. Chem. 11 (1990) 899–908.
  * [26] M. Vöge, A. J. Guttmann, I. Jensen, On the number of benzenoid hydrocarbons, J. Chem. Inf. Comput. Sci. 42 (2002) 456–466.
  * [27] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20.
  * [28] Y. S. Zhang, I. Gutman, J. G. Liu, Z. C. Mu, q-Analog of Wiener index, MATCH Commun. Math. Comput. Chem. 67 (2012) 347–356.
  * [29] S. Zhang, W. Wang, T. C. E. Cheng, Bicyclic graphs with the first three smallest and largest values of the first general Zagreb index, MATCH Commun. Math. Comput. Chem. 55 (2006) 579–592.