# A Frequency-Based Learning-To-Rank Approach for Personal Digital Traces

Daniela Vianna  Dept. of Computer ScienceRutgers UniversityNew JerseyUSA
<EMAIL_ADDRESS>and  Amélie Marian  Dept. of Computer ScienceRutgers
UniversityNew JerseyUSA<EMAIL_ADDRESS>
###### Abstract.

Personal digital traces are constantly produced by connected devices, internet
services and interactions. These digital traces are typically small,
heterogeneous and stored in various locations in the cloud or on local
devices, making it a challenge for users to interact with and search their own
data. By adopting a multidimensional data model based on the six natural
questions — what, when, where, who, why and how — to represent and unify
heterogeneous personal digital traces, we can propose a learning-to-rank
approach using the state of the art LambdaMART algorithm and frequency-based
features that leverage the correlation between content (what), users (who),
time (when), location (where) and data source (how) to improve the accuracy of
search results. Due to the lack of publicly available personal training data,
a combination of known-item query generation techniques and an unsupervised
ranking model (field-based BM25) is used to build our own training sets.
Experiments performed over a publicly available email collection and a
personal digital data trace collection from a real user show that the
frequency-based learning approach improves search accuracy when compared with
traditional search tools.

††copyright: rightsretained

##  1\. Introduction

Digital traces of our lives are constantly being produced and saved by users,
as personal files, emails, social media interactions, multimedia objects,
calendar items, contacts, GPS tracking of mobile devices, records of financial
transactions, etc. Digital traces are usually small, heterogeneous and stored
in various locations in the cloud or on local devices making it hard for users
to access and search their own data.

Search of personal data is usually focused on retrieving information that
users know exists in their own dataset, even though most of the time they do
not know in which source or device they have seen the desired information.
Personal search have been throughout studied in specific real-life scenarios
as desktop search (stuff, ) and email search (halawi2015, ). In this work, we
tackle search over an integrated personal dataset comprised by a multitude of
heterogeneous personal digital traces from a variety of data sources. In this
scenario, each personal digital trace is a source of knowledge and can be
related to different data traces by shared common information. The richness of
contextual information attached to the digital data can be of great help to
users searching for information they remember having stored and accessed in
the past. This information can naturally be modeled following the six
contextual dimensions: _what_ , _who_ , _when_ , _where_ , _why_ and _how_.

Learning-to-rank approaches have been very successful in solving real-world
ranking problems. However, the existing models for ranking are trained on
either explicit relevance judgments (crowdsourced or expert-labeled) or
clickthrough logs. For personal digital traces, none of these is available nor
pursuable, in addition, there is a dearth of synthetic personal datasets and
benchmarks. To overcome those challenges, we propose a learning-to-rank
approach that relies on a combination of known-item query generation
techniques and an unsupervised ranking model (field-based BM25) to
heuristically build training sets. Furthermore, since personal digital traces
are results of actions and events of users, the correlation between objects
can be leverage to improve the accuracy of search results. In this regard, we
represent the input data by a set of frequency-based features that takes into
consideration the correlation between content (_what_), users (_who_), time
(_when_), location (_where_) and data source (_how_). In this work, we use a
state-of-the-art learning-to-rank algorithm based on gradient boosted decision
trees, LambdaMART (Burges2010, ), to learn a ranking model to map feature
vectors to scores. The work presented in this paper is developed as part of a
series of tools to let user retrieve, store and organize their digital traces
on their own devices guaranteeing some clear privacy and security benefits.

In this paper, we make the following contributions:

  * •

A representative feature set to represent query-matching object pairs built
upon a novel frequency-based feature space that leverages entities
interactions within and across dimensions in the dataset,

  * •

A novel combination of known-item query generation techniques and an
unsupervised ranking model to heuristically generate labeled training sets,

  * •

A quantitative evaluation of the proposed search technique, as well as
comparison with two popular search methodologies: _BM25_ and _field-based
BM25_. Our results show that moderately large datasets can benefit from
learning techniques when combined with a compact frequency-based feature set.

##  2\. Data Model

Considering the fact that contextual cues are strong trigger for
autobiographical memories ( (brewer88, ; PIMbook, ; sevensinsmemory, ;
Wagenaar86, )), and that personal data is rich in contextual information, in
the form of metadata, application data, or environment knowledge, personal
digital traces can be represented following a combination of dimensions that
naturally summarize various aspects of the data collection: _who_ , _when_ ,
_where_ , _what_ , _why_ and _how_. In this work, we use an intuitive
multidimensional data model that relies on these six dimensions as the
unifying features of each personal digital trace object, regardless of its
source (asist2019, ). Below is a list of dimensional data that can be
extracted from a user’s personal digital traces:

  * •

what: content
Messages, messages subjects, description of events/users, publications, list
of interests of a user

  * •

who: with whom, from whom, to whom
User names, senders, recipients, event owners, list of friends, authors

  * •

where: physical or logical, in the real-world and in the system
Hometown, location, event venues, URLs, file/folder paths

  * •

when: time and date, but also what was happening concurrently
Birthday, file/message/event created-/modified- time

  * •

why: sequences of data/events that are connected

  * •

how: application, author, environment

Figure 1. Simplified example of a user email message classified according to
the 6 contextual dimensions model.

Figure 1 shows a digital trace from a Gmail message with each piece classified
as belonging to one of the six contextual dimensions: _what, who, where, when,
why and how_. By using the six proposed dimensions, multiple digital traces
are unified and can be linked to each other, even though they could be from
different sources and have their own data schema. For instance, the email
message from Figure 1 can be linked to different data traces that have John
Smith under the same dimension _who_. Those traces could be, for example, a
Facebook post tagging John Smith or a Calendar entry shared with John Smith.

Having defined the multidimensional data model, it is still necessary to find
an effective mechanism to automatically translate the heterogeneous set of
personal data into the six dimensions. To this end, we use a machine learning
multi-class classifier using a combination of LSTM (Long Short-Term Memory)
and Dense layers (asist2019, ). Given a sentence, the classifier will output a
label (_who_ , _when_ , _where_ , _what_ , _why_ and _how_). For instance, the
subject in an email is a sentence with label _what_. During the classification
process, the _when_ dimension is normalized allowing dates from different
sources to be matched. Normalization also makes possible partial matches. For
instance, a query searching for June, will match objects with time June 2016
and June 2017 regardless of the original format of the data. Entity resolution
is applied to the parsed _who_ and _where_ dimensions identifying separate
instances of the same entity in data traces coming from the same sources, and
across sources. We use the classifier to translate raw data retrieved from
third-party sources into the 6 dimension model, without the need of human
intervention.

##  3\. Scoring Model

Unlike Web search, where the focus is often on discovering new relevant
information, search in personal datasets is typically focused on retrieving
data that the user knows exists in their dataset. Besides, users have unique
habits and interpretations of their own data. In this scenario, standard
search techniques are not ideal as they do not leverage the additional
knowledge the user is likely to have about the target object, or the
connections between objects pertaining to a given user. This extra knowledge,
represented by the six dimensional model introduced in Section 2, can be
leveraged to provide rich and accurate search capabilities over personal
digital traces.

As personal digital traces are very specific to each user and are constantly
evolving over time, it is necessary to find a scoring model that can
generalize well over user-specific datasets. Learning-to-rank approaches have
proved to be very efficient to solve ranking problems. However, learning
algorithms require a huge amount of data to generalize well given the large
feature space usually employed (from thousands to tens of thousands of
features), due to the curse of dimensionality (bellman, ). To be able to
employ a learning approach on available personal datasets, which are typically
not very large, we adopted a compact feature set based on a representation of
the input data using the six contextual dimensions presented in Section 2.

In Section 3.1, we define matching objects and queries in our personal search
scenario. The 34 features proposed are detailed in Section 3.2. In Section 3.3
we continue to discuss the frequency score focusing on the _what_ dimension
that is comprised mostly of text. Section 3.4 describes the learning-to-rank
algorithm used in this work to generate our ranking model and validate the
feature space proposed.

###  3.1. Scoring Methodology

In this work, we consider each digital trace from a personal dataset to be a
distinct object that can be returned as the result to a query.

###### Definition 3.1 (Object in the Integrated Dataset).

An object $O$ in the dataset is a structure that has fields corresponding to
the 6 dimensions mentioned earlier. Each of these dimensions contains 0 or
more items (corresponding to text, entities identified by entity resolution,
times, locations, etc).

Formal queries have the same structure as objects in the unified dataset.

###### Definition 3.2 (Query).

A query $Q$ over the dataset is represented as an object as defined in
Definition 3.1.

Given objects Q and O, O is considered as an answer to object Q treated as a
query if it contains at least one dimension/item specified in Q. Unfortunately
users’ memories are notoriously unreliable (sevensinsmemory, ; croft, ), and
fully trusting their recollection of contextual information can lead to miss
relevant results. In looking for (partially) matching objects to a given
query, each dimension will be searched separately, and the results will be
combined generating a list of candidates with some partial order. With the
intention of finding an optimal order for this list of candidates, in the
following sections we introduce our learning-to-rank approach on top of a
representative feature set built from our novel frequency-based feature space.

###  3.2. Frequency-based Features

Because personal digital traces are byproducts of actions and events of users,
they are not independent objects. Our intuition is that the correlation
between traces (objects) can be leveraged to improve the accuracy of search
results. With that in mind, we explore how the correlations between users
(_who_), time (_when_), location (_where_), topics (_what_) and data sources
(_how_) can be used to improve search over personal data. We exploit those
interactions and correlations by way of a frequency score. For each dimension
and combination of dimensions we compute a score that will be used later as
features to represent the input data in our learning-to-rank approach.

Frequencies can be computed for individual users or group of users. They can
be associated with multiple times, multiple data sources, and also with a set
of locations. For example, from a set of emails exchanged between a group of
users, we can extract the frequency (number of interactions) with which those
users communicated, and in which time period those interactions occurred. In
short, frequency expresses the strength of relationships, based on users,
time, location, content and data sources (_who, when, where, what, how_). To
keep it simple, every time an interaction occurs, the frequency is increased
by one; however, in practice, the frequency function allows us to weigh
differently distinct types of interactions. For example, likes or comments on
a Facebook post could be weighed differently, giving more relevance to
interactions coming from comments than likes. Different roles, e.g. From and
To in an email, can also be weighed differently.

To take advantage of the strong correlation between group of users, which is
an important feature of personal corpora, we also compute the frequency
between group of users, source, times and location. Other application
scenarios could also benefit from our six-dimension model, with other groups
highlighted in a dedicated frequency-based scoring. In this work, we use a set
of 34 features to represent the input data. The feature set is comprised by 30
features resulting from all possible combinations between the dimensions _who,
what, when, where_ and _how_ plus 4 extra features that model the correlation
between group of users (_who groups_); group of users and time (_who groups,
when_); group of users and data source (_who groups, how_); and finally, group
of users, time and location (_who groups, when, where_). The feature vector is
defined in Definition 3.3.

###### Definition 3.3 (Feature Vector).

x = $[x_{1}\ldots x_{34}]$ is a feature vector comprised by 34 frequency-based
features. Each feature $x_{i}$ is computed by a frequency function
$f(S_{i},Q,O)$, where $S_{i}\in\mathcal{S}$. $\mathcal{S}$ represents all
possible combinations between the 5 dimensions _who, what, when, where_ and
_how_ , plus the 4 extra features that model the correlation between group of
users. $Q$ is a query (Definition 3.2) and $O$ is an object in the user
dataset (Definition 3.1).

To illustrate our query and scoring methodology consider the following search
scenario: the user is interested in a message from 2018 (_when_), sent by John
(_who_), about the topic “Lunch” (_what_). We can define query $Q_{1}$ as
(_when_ : 2018, _who_ : John, _what_ : Lunch). By Definition 3.1, the object
in Figure 1 ($O_{1}$) is a matching to the given query ($Q_{i}$) containing
all dimension/item specified in the query – _when_ :2018, _who_ :John, and
_what_ :“Lunch”. The query-object pair ($Q_{1},O_{1}$) can be represented by a
34 frequency-based feature vector $\textbf{x}=[x_{1}\ldots x_{34}]$ as
introduced in Definition 3.3. Each feature $x_{i}$ represents the frequency
score for a set of dimensions $S_{i}$, query $Q_{i}$ and object $O_{i}$:

  * $x_{1}=f((\text{what:Lunch}),Q_{1},O_{1})$

  * $x_{2}=f((\text{who:John}),Q_{1},O_{1})$

  * $x_{3}=f((\text{when:2018}),Q_{1},O_{1})$

  * $x_{6}=f((\text{what:Lunch, who:John}),Q_{1},O_{1})$

  * $x_{7}=f((\text{what:Lunch, when:2018}),Q_{1},O_{1})$

  * $x_{9}=f((\text{what:Lunch, how:Gmail}),Q_{1},O_{1})$

  * $x_{10}=f((\text{who:John, when:2018}),Q_{1},O_{1})$

  * $x_{12}=f((\text{who:John, how:Gmail}),Q_{1},O_{1})$

  * $x_{16}=f((\text{what:Lunch,who:John, when:2018}),Q_{1},O_{1})$

  * $x_{18}=f((\text{what:Lunch,who:John, how:Gmail}),Q_{1},O_{1})$

  * $x_{20}=f((\text{what:Lunch,when:2018, how:Gmail}),Q_{1},O_{1})$

  * $x_{23}=f((\text{who:John, when:2018, how:Gmail}),Q_{1},O_{1})$

  * $x_{27}=f((\text{what:Lunch,who:John,when:2018,how:Gmail}),Q_{1},O_{1})$

If a set of dimensions $S_{i}$ is not present in query $Q_{1}$ and object
$O_{i}$, the frequency score $f(S_{i},Q,O)=0$. When a query $Q$ contain
multiple values for a dimension e.g., Q = (who: John, Alice), the values for
each feature $x_{i}$ will be the summation of the frequencies for each
individual value.

To understand how frequencies ($f(S_{i},Q,O)$) are computed, consider the
following example: lets assume a dataset $D$ containing 10 objects that
mention John under the _who_ dimension, being 4 of those 10 objects from
Facebook and the remaining 6 from Gmail. Given object $O_{1}$ and query
$Q_{1}$ from the previous example, we can say that the frequency of John
((who:John)) in dataset $D$ for query $Q_{1}$ and matching object $O_{1}$ is
$x_{2}=f((\text{who:John}),Q_{1},O_{1})$, where
$f((\text{who:John}),Q_{1},O_{1})=10$. We can also say that the frequency of
John in Gmail ((who:John,how:Gmail)) in dataset $D$ for query $Q_{1}$ and
matching object $O_{1}$ is $x_{12}=f((\text{who:John,
how:Gmail}),Q_{1},O_{1})$, where $f((\text{who:John,
how:Gmail}),Q_{1},O_{1})=6$.

Notice that the _why_ dimension is not explored in this paper, but is the
topic of related work (odbase, ; cikmdemo, ). This dimension can be derived by
inference and could be used to connect different fragments of data that derive
from a common real-life task, or episode.

###  3.3. Scoring the _What_ Dimension

The _what_ dimension in the six-dimension model is composed of content
information comprising mostly of text. Based on that fact, we use two standard
text approaches to link and score objects for the _what_ dimension: field-
based BM25 (used to score the what dimension alone) and topic modeling
(steyvers_griffiths07, ) (used to link the what dimension with the other
dimensions).

Field-based BM25. A field-based BM25 is a state-of-the-art TF-IDF type of
ranking function that takes into consideration the document structure. In our
scenario, the fields in the field-based BM25 correspond to the 5 dimensions
proposed, _what, who, when, where_ and _how_. To compute the field-based BM25
score for the _what_ dimension, we use a popular full-text search platform
from the Apache Lucene project, Solr (ApacheSolr, ). All data retrieved for a
user is unified and parsed according with the six dimensions (Section 2) and
then, exported to Solr. For each user query, we search Solr using the values
from the _what_ dimension, getting as a result a partial list of matching
documents with its respective field-based BM25 score. Even though Solr
contains the data for all 5 dimensions, we are only interested in use field-
based BM25 to score the _what_ dimension, since this dimension contains most
of the content of an object. For the remaining dimensions, we use our
frequency-based function as introduced in Section 3.2.

Topic Modeling. A “Topic” consists of a cluster of words that frequently occur
together. Topic models use contextual cues to find connections between words
with similar meanings and to distinguish between use of words with multiple
meanings. Given a document, we would like to identify what possible topics
have generated that data. In our case, topic modeling would be an important
feature to connect different objects, including objects from different data
sources. The association between topics (_what_), user (_who_), times
(_when_), location (_where_) and source (_where_) could shed some light on
finding objects that could be a better matching to the user query. To define
topics for each object in the user data set, we use a topic model package
called MALLET and a text collection built from the content classified under
the _what_ dimension for each object in the user data set. The MALLET
(McCallumMALLET, ) topic model package includes a fast and scalable
implementation of Gibbs sampling. The Gibbs Sampling algorithm considers each
word token in the text collection in turn, and estimates the probability of
assign the current word token to each object, conditioned on the topic
assignments to all other word tokens. For each object in the user data set,
MALLET computes the topic composition of documents. We use the most relevant
topic for each document to cluster documents per topic. For each document in a
topic, we extract the person/entity mentioned in _who_ dimension, the times
from _when_ , location from _where_ and source from _how_. With that
information, we are able to build the correlation between person/entity,
times, location and source for each topic (_what_). Also, we are able to
estimate the frequency of those correlation/interactions using the frequency
function presented in Section 3.2. Besides the topic composition of documents,
MALLET also outputs the words in the corpus with their topic assignments and
frequencies. We use this list of words per topic and the words specified in
the user query (for the _what_ dimension), to find the topic that are a more
close representative of the user query. Then, we can use the topic that
matches the query to find out a partial list of documents that are matching
candidates to the query, based solely on the contents of the _what_ dimension.

To illustrate how topic modeling can support our search, consider $T$ a topic
composed by the following key words: hotel, lunch, street, trip, miles, view,
lake, ride, restaurant and conference. Assuming that topic $T$ is the most
relevant topic for object $O_{1}$ in Figure 1, and object $O_{2}$ in Figure 2,
we can say that objects $O_{1}$ and $O_{2}$ are correlated by their _what_
dimension. By considering all objects (documents) clustered under the same
topic $T$, we can learn how strong person/entity (_who_), times (_when_),
location (_where_) and source (_how_) are connected with relation to a topic
(_what_). Again, this strength is measured by a way of a frequency score as
presented in Section 3.2.

Figure 2. Simplified example of a user Facebook post classified according to
the 6 contextual dimensions model.

###  3.4. Learning-to-Rank Model

In the previous sections, we explained how query-document pairs are
represented by a feature vector built upon our frequency-based feature space.
To map the feature vector to a real-valued score we need to train a ranking
model. Our choice of learning-to-ranking algorithm is the state-of-the-art
LambdaMART (Burges2010, ). LambdaMART uses gradient boosted decision trees,
which incrementally builds regression trees trying to correct the leftover
error from the previous trees. At the end, the prediction model is an ensemble
of weaker prediction models that complement each other for robustness. During
a training phase, we must define the best set of parameters that results in a
robust and accurate model. For this cross-validation stage, we will consider
the following parameters:

  * •

tree: number of trees in the ensemble

  * •

leaf: maximum number of leaves per tree

  * •

mls: minimum number of samples each leaf has to contain

  * •

shrinkage: learning rate

  * •

metric: training metric to be optimized for

In the next section, we will discuss how training and evaluation sets can be
built for personal data search, a scenario where publicly available personal
training data does not exist.

##  4\. Query Sets

In a learning-to-rank algorithm, each pair of query-document(object) is
represented by a vector of numerical features. In addition to the feature
vector, pairs of query-documents could be augmented with some relevance
information. Then, a model has to be trained to map the feature vector to a
score. One of the challenges of using learning-to-rank for personal data
search is to be able to build a training set without human intervention or any
external information (e.g., expert labeling or click data). To this end, in
this section we present a combination of heuristics that given a user dataset
is able to simulate a human-labeled training set to tailor the learning model
to each specific user dataset.

Search of personal data is usually focused on retrieving information that
users know exists in their own data set. Considering the fact that personal
data search is a known-item type of search, simulated queries can be
automatically generated, using known-item query (Elsweiler07towardstask-based,
) generation techniques such as the ones presented in (Azzopardi:2007, ) and
(Kim:2009, ). In this work, queries are created by randomly choosing a set of
dimensions (_who, what, when, where, how_) and values/items (e.g. email’s
Subject, Facebook post’s content) from a target object, as described in
Algorithm 1. Each call to Algorithm 1 will result in a query-target object
pair.

Algorithm 1 Known-item query generation algorithm.

1:procedure Build–Query(dataset D)

2: $Q=()$ /* Initialize query Q. */

3: /* Randomly choose a target object $O_{i}$ from the dataset D */

4: $O_{i}=$ random(D)

5: /* Select dimensions */

6: $d=$ select_dimensions({what, who, when, where, how})

7: for each $d_{i}\in d$ do

8: /* Randomly choose $v$ values from target object $O_{i}$ and dimension
$d_{i}$ */

9: $v$ = select_values($d_{i}$)

10: /* Add dimension and values to the query $Q$ */

11: $Q(d_{i})=v$

12: end for

13: return $Q$

14:end procedure

By using the proposed known-item query generation technique, we are able to
build a list of query-target object pairs. However, a learning-to-rank
training set is composed not only by pairs of query-known document, but also
by a list of matching documents per query. In (Dehghani2017, ), the authors
use classic unsupervised information retrieval models, such as BM25, as a weak
supervision signal for training deep neural ranking models. In a similar
fashion, we adopt an unsupervised ranking model, field-based BM25, to retrieve
matching objects to a given query. In Section 3.3, we explained how the data
retrieved for a user is unified and parsed according with the six dimensions
(Section 2) and then, the parsed data is exported to Solr where it can be
searched using a field-based BM25 approach. Given a query generated by
Algorithm 1, a call to Solr will retrieve a list of matching documents to this
query — the list is ranked using field-based BM25. Now, for each query, we
have a list of matching documents that includes the (generated) target object
and its corresponding feature vector as described in Section 3.2. Since the
target object is known for this query, a relevance label of $1$ is assigned to
it; otherwise, the relevance label will be $0$.

##  5\. Case Studies 1: Personal Digital Data Traces

We evaluate the efficacy of the proposed learned ranking model by comparing
its performance with two popular scoring methodologies: _BM25_ and _field-
based BM25_. Experiments are performed over real user data from a variety of
data sources.

###  5.1. Methodology

####  5.1.1. Data Set.

Data Source | #Objs | Size
---|---|---
Facebook | 3875 | 28Mb
Gmail | 28318 | 3Gb
Dropbox | 573 | 32Mb
Foursquare | 55 | 59Kb
Twitter | 3929 | 22Mb
Google Calendar | 330 | 620Kb
Google+ | 110 | 367Kb
Google Contacts | 525 | 629Kb
Bank | 412 | 415Kb
Firefox | 181921 | 63Mb
Total | 219,993 | 3.6Gb
Table 1. Personal dataset.

There is a dearth of synthetic data sets and benchmarks to evaluate search
over personal data. Thus, we perform our evaluation using a real dataset
collected by a personal data extraction tool (DataExtraction, ) containing
approximately two hundred thousand objects.

Table 1 shows the composition of our real user dataset, including the number
and size of objects retrieved from different sources over different periods of
time. The dataset was automatically classified according with the 6 contextual
dimensions: _what, who, when, where, why_ and _how_ (Section 2). We used this
unified dataset to evaluate the frequency-based learning-to-rank approach
proposed.

####  5.1.2. Training and Evaluation query sets.

We train and evaluate our model on the user’s own device using heuristically
generated samples. As detailed in Section 4, each query is automatically
created by randomly choosing a target object from the evaluation data set. We
then choose _d_ dimensions, from which we randomly select $v$ random values.
For this set of experiments, we built a training set comprised by 19000
queries over our personal dataset (Table 1). To built the query sets, we use
$v=1$ and 4 different values for parameter $d$: {_what, who_}, {_what, who,
when_}, {_what, who, when, how_}, and {_what, who, how_}. The evaluation set
was built in a similar fashion. Approximately 6000 queries were heuristically
generated using the same combination of parameters as the training set. Since
less than 2% of objects in the user dataset have location, the dimension
_where_ was not included in the query sets.

####  5.1.3. Evaluation Techniques and Metrics.

We evaluate the efficacy of the proposed approach by comparing it with two
popular scoring methodologies: _BM25_ and _field-based BM25_.

BM25 is a state-of-the-art type of TF-IDF function that ranks a list of
matching documents based on the query content that appears in each document.
To be able to use BM25 with the retrieved dataset (Section 5.1.1), the
heterogeneous and decentralized digital traces have to be integrated in one
unified collection. It is done by exporting the data retrieved to a unified
data collection in Solr (ApacheSolr, ), a popular open source full-text search
platform from the Apache Lucene project. This approach allows user to search
for information across the entire set of retrieved digital traces, which is
already a significant step forward from the current state, where users have to
search each data source individually.

Field-based BM25 is a version of BM25 that takes into consideration the
structure of a document. In our scenario, the fields in the field-based BM25
correspond to the five dimensions proposed: _what, who, when, where, how_. As
described in Section 3.3, before being exported to Solr, the retrieved dataset
(Section 5.1.1) is unified and parsed according with the six dimensions
(Section 2). It allows for the dataset to be searched using field-based BM25
with each field corresponding to a respective dimension. Note that by using
the five dimensions, we are giving the field-based BM25 approach the advantage
of using our multidimensional data model to unify and organize the user data.

The scoring model proposed is evaluated using 4 standard evaluation metrics:
Mean Reciprocal Rank (MRR) of the top-ranked 50 documents, success (precision)
of the top 1 retrieved document (success@1), success of the top 3 retrieved
document (success@3), and success of the top 10 retrieved document
(success@10). Wilcoxon signed-rank test with $p\\_value<0.05$ is used to
determine statistically significant differences.

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.3629 | 0.2701 | 0.4104 | 0.5350
Field-based BM25 | 0.5082 | 0.4252 | 0.5502 | 0.6690
w5h-l2r | 0.5184 | 0.4406 | 0.5601 | 0.6900
Table 2. MRR, s@1 (success@1), s@3 (success@3), s@10 (success@10) for all
$6000$ queries (groups $1$ to $4$) from the Personal Digital Data Traces
dataset (Table 1). Compared against the baseline (_BM25_), the results are
statistically significant (Wilcoxon signed-rank test).

####  5.1.4. Ranking Model.

To train and evaluate our model, we use the LambdaMART implementation provided
by the RankLib library (ranklib, ). RankLib is a library of learning to rank
algorithms that is part of The Lemur Project (lemur, ).

The first step in our evaluation was to define the best set of parameters that
would give us a more robust and accurate model. The parameters evaluated are:
number of trees (tree); number of leaves for each tree (leaf); minimum leaf
support (mls), minimum number of samples each leaf has to contain; and,
training/evaluation metric (metric). In our evaluation we considered the
following parameters:

  * •

tree: 50, 100, 250 and 500

  * •

leaf: 10, 15, 35 and 45

  * •

mls: 10, 20 and 50

  * •

shrinkage: 0.01, 0.03, 0.1, 0.3, 0.5, 1.0

  * •

metric: MRR (Mean Reciprocal Rank)

We adopted a 5-fold cross validation process to estimate the performance of
each model. After the validation process, we selected the model that shows the
best performance on the training set, also taking into account the spread
between training and testing metrics. The model selected, that we will call
_w5h-l2r_ , has the following parameters: number of trees $=50$; number of
leaves $=15$; minimum leaf support $=10$; shrinkage $=0.1$.

###  5.2. Results.

In Table 2 we compare the ranking performance of the baseline (_BM25_),
_field-based BM25_ and learned ranking model (_w5h-l2r_) with respect to the
entire evaluation set composed by approximately 6000 queries heuristically
generated as described in Section 5.1.2. The results show that both search
models using the data parsed according to the multidimensional data model
(Section 2), _field-based BM25_ and _w5h-l2r_ , outperform the keyword-based
approach, _BM25_ , for MRR, success@1, success@3 and success@10. It shows that
traditional keyword-based search methods are not appropriate in a setting
where users may remember valuable contextual cues to guide the search. Observe
that the learned ranking model, _w5h-l2r_ , outperform the _field-based BM25_
approach for all 4 evaluation metrics, showing that moderately large datasets
can also benefit from learning-to-rank techniques when paired with a
representative feature set built from our novel frequency-based feature space.

We now conduct a more thorough evaluation by dividing the evaluation set
(Section 5.1.2) in four different groups by the dimensions in each query as
described in Table 3.

Groups | Dimensions
---|---
Group 1 | what, who
Group 2 | what, who, when
Group 3 | what, who, when, how
Group 4 | what, who, how
Table 3. Dimensions used to generate four groups of queries.

---

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.3435 | 0.2450 | 0.3939 | 0.5290
Field-based BM25 | 0.4407 | 0.3605 | 0.4809 | 0.6000
w5h-l2r | 0.4432 | 0.3730 | 0.4851 | 0.6430
(a) Group 1: what, who

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.3759 | 0.2875 | 0.4224 | 0.5370
Field-based BM25 | 0.5760 | 0.4850 | 0.6261 | 0.7420
w5h-l2r | 0.5970 | 0.5084 | 0.6465 | 0.7660
(b) Group 2: what, who, when

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.4213 | 0.3223 | 0.4614 | 0.5870
Field-based BM25 | 0.6168 | 0.5215 | 0.6417 | 0.7810
w5h-l2r | 0.6331 | 0.5272 | 0.6618 | 0.7940
(c) Group 3: what, who, when, how

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.3484 | 0.2591 | 0.3888 | 0.5200
Field-based BM25 | 0.4621 | 0.3863 | 0.4974 | 0.6150
w5h-l2r | 0.4632 | 0.3964 | 0.4902 | 0.6000
(d) Group 4: what, who, how

Table 4. MRR, s@1 (success@1), s@3 (success@3), s@10 (success@10) for groups
$1$,$2$,$3$, and $4$ from the Personal Digital Data Traces dataset (Table 1).
Compared against the baseline (_BM25_), the results are statistically
significant (Wilcoxon signed-rank test).

Table 4a-d, show the MRR, success@1, success@3 and success@10 of each search
approach, _BM25_ (baseline), _field-based BM25_ , and _w5h-l2r_ , for Group 1
to 4 of queries. For all 4 groups, the search approaches that use the data
classified according with our multidimensional data model are considerably
more accurate than the keyword-based approach, _BM25_ , confirming the
importance of including contextual information to improve search accuracy when
searching personal data. When compared against each other, _field-based BM25_
and _w5h-l2r_ , the learned ranking model outperform the _field-based BM25_
model for all four groups; however, the improvements were more relevant for
Group 2 (_what, who, when_) and Group 3 (_what, who, when, how_), showing that
for this dataset, using the proposed learning model and training data, the
_when_ dimension and all related features played an important role in scoring
query-document pairs. The results for _w5h-l2r_ when compared with _field-
based BM25_ are statistically significant (Wilcoxon signed-rank test,
$p\\_value<0.05$) for Groups 2 and 3, evaluation metric MRR and success@k. For
Group 1 the results are not statistically significant for MRR and success@3.
For Group 4, the results are not statistically significant for MRR, success@1
and success@3.

Figure 3 presents the performance (MRR) of the learning model, _w5h-l2r_ , for
Group 1 to 4 of queries as the number of training samples increases. We
observe that the performance of the learned ranking model (_w5h-l2r_) clearly
improves as the size of the training set increases just modestly, showing the
validity of our training set generation techniques.

|
---|---
|
(a) Group 1 (b) Group 2 (c) Group 3 (d) Group 4

Figure 3. Performance (MRR) of the learning model, _w5h-l2r_ , for groups 1,
2, 3 and 4 of queries from the Personal Digital Data Traces dataset (Table 1)
as the number of training samples increases.

The importance of a feature in a gradient boosted decision tree model such as
LambdaMART can be conveyed by the number of times such feature appears in the
internal (non-leaf) nodes of the decision trees that form the tree ensemble.
Since our model has 50 trees, each having 15 leaves (and 14 internal nodes),
there are 700 branches overall. In Table 5 we present the feature frequency
distributions for the trained _w5h-l2r_ model. The most frequent feature in
our model is the _what_ dimension, that represents the content of an object
and is scored using _field-based BM25_. Then, features (_who,when_),
(_who,how_), and (_who_) appear next, all of them related to the _who_
dimension, which is expected since personal digital traces are byproduct of
actions and events of users (_who_), and are typically focused on user
interactions.

Feature | Freq.
---|---
what | 217
who, when | 91
who, how | 80
who | 75
what, how | 72
what, who, how | 51
what, when | 40
what, who | 28
who, when, how | 23
when | 16
what, who, when, |
how | 4
what, when, how | 2
how | 1
Table 5. Feature frequencies for the _w5h-l2r_ model and the Personal Data
Traces dataset.

The results presented in this section indicates that personal data search can
improve greatly by taking into consideration the knowledge the user has about
the object being searched. The multidimensional data model, based on the 6
contextual dimensions, proved to be an intuitive and efficient model to unify
and link heterogeneous personal digital traces. The advantage of using a
learning approach to re-rank search results can be seen by the improvement
presented by the _w5h-l2r_ approach when compared against both methods, _BM25_
and _field-based BM25_. Including a compact feature space based on frequency
information resulted in significant improvements.

##  6\. Case Studies 2: Enron Email Dataset

###  6.1. Methodology

####  6.1.1. Data Set.

To verify the validity of our frequency-based learning-to-rank approach over
other domains, we have implemented it over an email dataset: the Enron
(enrondataset, ) dataset. The Enron email dataset contains a total of about
0.5M emails from 158 employees of the Enron Corporation, obtained by the
Federal Energy Regulatory Commission after the company collapsed into
bankruptcy resulting in a federal investigation.

####  6.1.2. Training and Evaluation Query Sets.

To train and validate our model we use heuristically generated samples as we
did in Section 4. Each query is automatically created by randomly choosing a
target object from the evaluation data set. We then choose _d_ dimensions,
from which we randomly select $v$ random values. For this set of experiments,
the training set is comprised by 48000 queries over the Enron dataset and the
evaluation set is comprised by 2000 queries. Training and evaluation query
sets were built using $v=1$ and 4 different values for parameter $d$: {_what,
who_}, {_what, who, when_}, {_what, who, when, how_}, and {_what, who, how_}.

####  6.1.3. Evaluation Techniques and Metrics.

To evaluate the efficacy of the proposed approach for the Enron dataset, we
use the same metrics adopted to validate the Personal Digital Data Traces
dataset (Section 5.1.3). The proposed approach is compared against _BM25_ and
_field-based BM25_ and 4 standard evaluation metrics are used: Mean Reciprocal
Rank (MRR) of the top-ranked 50 documents, success (precision) of the top 1
retrieved document (success@1), success of the top 3 retrieved document
(success@3), and success of the top 10 retrieved document (success@10).
Wilcoxon signed-rank test with $p\\_value<0.05$ is used to determine
statistically significant differences.

####  6.1.4. Ranking Model.

To train and evaluate our model, we use the same parameters and steps
presented in Section 5.1.4. We selected the model that shows the best
performance on the training set, also taking into account the spread between
training and testing metrics. The model selected, that we will call _w5h-l2r_
, has the following parameters: number of trees $=50$; number of leaves $=15$;
minimum leaf support $=20$; shrinkage $=0.3$.

###  6.2. Results.

As with the Personal Digital Data Traces dataset, for the Enron dataset the
evaluation set was divided in four different groups by the dimensions in each
query: Group 1 $=$ what, who; Group 2 $=$ what, who, when; Group 3 $=$ what,
who, when, how; Group 4 $=$ what, who, how.

---

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.2591 | 0.1320 | 0.1120 | 0.0502
Field-based BM25 | 0.2549 | 0.1260 | 0.1053 | 0.0510
w5h-l2r | 0.2688 | 0.1560 | 0.1020 | 0.0504
(a) Group 1: what, who

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.2346 | 0.1220 | 0.0980 | 0.0450
Field-based BM25 | 0.4139 | 0.2360 | 0.1767 | 0.0732
w5h-l2r | 0.4218 | 0.2495 | 0.1790 | 0.0727
(b) Group 2: what, who, when

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.2422 | 0.1328 | 0.0979 | 0.0449
Field-based BM25 | 0.4090 | 0.2314 | 0.1791 | 0.0736
w5h-l2r | 0.4213 | 0.2575 | 0.1764 | 0.0744
(c) Group 3: what, who, when, how

Method | MRR | s@1 | s@3 | s@10
---|---|---|---|---
BM25 | 0.2442 | 0.1060 | 0.1087 | 0.0478
Field-based BM25 | 0.2585 | 0.1140 | 0.1133 | 0.0492
w5h-l2r | 0.2477 | 0.1220 | 0.1020 | 0.0492
(d) Group 4: what, who, how

Table 6. MRR, s@1 (success@1), s@3 (success@3), s@10 (success@10) for groups
$1$,$2$,$3$, and $4$ from the Enron dataset.

Table 6a-d, show the MRR, success@1, success@3 and success@10 of each search
approach, _BM25_ (baseline), _field-based BM25_ , and _w5h-l2r_ , for Group 1
to 4 of queries. For Group $1$ (Table 6a), the search approach _w5h-l2r_ is
slight better than _BM25_ (baseline) and _field-based BM25_ for MRR and
success@1. For Group $2$ (Table 6b) and Group $3$ (Table 6c), the search
approaches that use the data classified according with our multidimensional
data model are considerably more accurate than the keyword-based approach,
_BM25_ , and the results are statistically significant (Wilcoxon signed-rank
test, $p\\_value<0.05$). For those groups, the learned ranking model,
_w5h-l2r_ , outperforms the _field-based BM25_ model for all metrics, the
exceptions being success@10 for Group $2$ and success@3 for Group $3$. For
Group $4$, all approaches had a similar performance. For most scenarios in
this group of queries, the features based on the _how_ dimension are not
contributing to differentiate Enron results.

Table 7 shows the feature frequency distributions for the learned ranking
model _w5h-l2r_. The two most frequent features in our model are based on the
_what_ dimension, that represents the content of an object and is scored using
field-based BM25. Then, features related to the _who_ dimension appear next,
representing the frequency of users (_who_) and the interactions between
user/time (_who, when_) and user/topic (_who, what_).

Feature | Freq.
---|---
what | 273
what, how | 118
who, when | 97
who | 77
what, who | 56
what, when | 25
what, when, who | 19
when | 18
what, when, who, |
how | 15
how | 2
Table 7. Feature frequencies for the _w5h-l2r_ model and the Enron dataset.

The results discussed in this section show that even though the data and
scoring model were proposed with the Personal Digital Data Traces dataset in
mind, it can be extended to different domains with promising results.

##  7\. Related Work

Bell has pioneered the field of life-logging with the project MyLifeBits
(mylifebits, ; bell-total-recall, ) for which he has digitally captured all
aspects of his life. digi.me (digime, ) is a commercial tool that aims at
extending Bell’s vision to everyday users. The motivations behind digi.me are
very close to ours; however digi.me currently only offers a keyword- or
navigation-based access to the data; search results can be filtered by
service, data type or/and date.

The case for a unified data model for personal information was made in
(haystack, ; xu03towards, ). deskWeb (deskweb, ) looks at the social network
graph to expand the searched data set to include information available in the
social network. Stuff I’ve Seen (stuff, ) indexes all of the information the
user has seen, regardless of its location or provenance, and uses the
corresponding metadata to improve search results. Our work is related to the
wider field of Personal Information Management (PIMbook, ), in particular,
search behavior over personal digital traces is likely to mimic that of
searching data over personal devices. Unlike traditional information seeking,
which focuses on discovering new information, the goal of search in Personal
Information systems is to find information that has been created, received, or
seen by the user.

Email search is a type of personal search that has been well studied.
(halawi2015, ) presents a learning-to-rank approach that improves the default
ranked-by-time search by taking into consideration time recency and textual
similarity to the query. (Wang2016, ) addresses the problem of learning-to-
rank from click data in personal search. (Zamani2017, ) explores how to
effectively leverage situational contextual features (e.g. time of a search
request and the location of the user while submitting the request) to improve
personal search quality. In (Bendersky2017, ) the authors leverage user
interaction data in a privacy preserving manner for personal search by
aggregating non-private query and document attributes across a large number of
user interactions. In our scenario, each dataset is comprised by data from
only one user, and so it is private by design, not being possible for us to
leverage interactions from other users.

In (Dehghani2017, ) the authors use classic unsupervised IR models, such as
BM25, as a weak supervision signal for training deep neural ranking models. In
this context, weak supervision refers to a learning approach that creates it
own training data by heuristically retrieving documents for a large query set.
Three different neural network-based ranking models are presented, a point-
wise ranking model and two pair-wise models. Combinations of neural models
with different training objectives and input representations are compared
against each other and against the baseline, BM25. The experiments showed that
their best performing model significantly outperforms the BM25 model. In our
work, we use a similar approach to retrieve matching objects to a given query.

##  8\. Conclusions and Future Work

In this work, we proposed a learning-to-rank approach that uses a compact and
efficient frequency-based feature space to rank query results over personal
digital traces. The learning model relies on our multidimensional data model
to unify and link heterogeneous digital traces using six contextual
dimensions: _what, who, when, where, why_ and _how_. To overcome the lack of
human-labeled training sets, we proposed a combination of known-item query
generation techniques and an unsupervised ranking model (_field-based BM25_)
to generate our query sets. Experiments over a publicly available email
collection and a personal dataset composed by data from a variety of data
sources indicates that our frequency-based learning approach can significantly
improve the accuracy of search results when compared with a traditional
keyword-based approach, _BM25_ , and a field-based approach that uses the data
parsed according to our multidimensional data model, _field-based BM25_.

Our work shows that using contextual information to model and integrate
personal data can lead to more accurate scoring and searching methodologies.
By introducing a compact feature set, we made it possible for moderately large
datasets to take advantage of modern learning-to-rank techniques that are
usually employed with very large datasets. In addition, we have designed a
known-item query generation approach that allowed us to generate query sets on
the fly for a type of application (personal search) in which datasets and
training sets are non existent; such approach is private by design, allowing
for the end-to-end machine learning pipeline to run on the device of the user.
In the future, the same techniques could be applied to different sets of
applications, as we have done with the Enron dataset.

## References

  * [1] Apache solr.  http://lucene.apache.org/solr/.
  * [2] L. Azzopardi, M. de Rijke, and K. Balog.  Building simulated queries for known-item topics: An analysis using six european languages.  In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’07, pages 455–462, New York, NY, USA, 2007. ACM.
  * [3] G. Bell and J. Gemmell.  Total Recall: How the E-Memory Revolution Will Change Everything.  Penguin, 2009.
  * [4] R. E. Bellman.  Adaptive Control Processes.  Princeton University Press, 1961.
  * [5] M. Bendersky, X. Wang, D. Metzler, and M. Najork.  Learning from user interactions in personal search via attribute parameterization.  In Proceedings of the 10th ACM International Conference on Web Search and Data Mining (WSDM), pages 791–800, 2017.
  * [6] W. Brewer.  Memory for randomly sampled autobiographical events, page 21–90.  Cambridge University Press, 1988.
  * [7] C. J. Burges.  From ranknet to lambdarank to lambdamart: An overview.  Technical report, June 2010.
  * [8] W. B. Croft, P. Krovetz, and H. Turtle.  Interactive retrieval of complex documents.  Information Processing and Management, 26(5), 1990.
  * [9] M. Dehghani, H. Zamani, A. Severyn, J. Kamps, and W. B. Croft.  Neural ranking models with weak supervision.  In Proceedings of The 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017.
  * [10] digi.me.  https://www.digi.me.
  * [11] S. Dumais, E. Cutrell, J. J. Cadiz, G. Jancke, R. Sarin, and D. C. Robbins.  Stuff i’ve seen: A system for personal information retrieval and re-use.  In Proceedings of the 26th International ACM SIGIR Conference (SIGIR’03), 2003.
  * [12] D. Elsweiler and I. Ruthven.  Towards task-based personal information management evaluations.  In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’07, pages 23–30, New York, NY, USA, 2007. ACM.
  * [13] Enron email dataset.  http://www.cs.cmu.edu/~enron/.
  * [14] J. Gemmell, G. Bell, and R. Lueder.  Mylifebits: a personal database for everything.  Communications of the ACM, 49(1):88–95, 2006.
  * [15] G. Halawi and A. Raviv.  Rank by time or by relevance?: Revisiting email search.  In Proceedings of CIKM 2015: 24th ACM CONFERENCE ON INFORMATION AND KNOWLEDGE MANAGEMENT, 2015.
  * [16] W. Jones and J. Teevan, editors.  Personal Information Management.  University of Washington Press, 2007.
  * [17] V. Kalokyri, A. Borgida, and A. Marian.  Yourdigitalself: A personal digital trace integration tool.  In Proc. 27th ACM International Conference on Information and Knowledge Management, CIKM ’18, pages 1963–1966, 2018.
  * [18] V. Kalokyri, A. Borgida, A. Marian, and D. Vianna.  Semantic modeling and inference with episodic organization for managing personal digital traces.  In Proc. 16th International Conference on Ontologies, DataBases, and Applications of Semantics (ODBASE’17), pages 273–280, 2017.
  * [19] D. R. Karger, K. Bakshi, D. Huynh, D. Quan, and V. Sinha.  Haystack: A general-purpose information management tool for end users based on semistructured data.  In CIDR, pages 13–26, 2005.
  * [20] J. Kim and W. B. Croft.  Retrieval experiments using pseudo-desktop collections.  In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM ’09, pages 1297–1306, New York, NY, USA, 2009. ACM.
  * [21] A. K. McCallum.  Mallet: A machine learning for language toolkit.  http://mallet.cs.umass.edu, 2002.
  * [22] Ranklib.  http://www.lemurproject.org/ranklib.php.
  * [23] D. Schacter.  The seven sins of memory: How the mind forgets and remembers. Houghton Mifflin, 2001.
  * [24] M. Steyvers and T. Griffiths.  Latent Semantic Analysis: A Road to Meaning, chapter Probabilistic topic models.  Laurence Erlbaum, 2007.
  * [25] The lemur project.  http://www.lemurproject.org.
  * [26] D. Vianna, V. Kalokyri, A. Borgida, A. Marian, and T. Nguyen.  Searching heterogeneous personal digital traces.  In ASIST’19: Proceedings of the 82nd ASIS&T Annual Meeting, Melbourne, AU, 2019.
  * [27] D. Vianna, A.-M. Yong, C. Xia, A. Marian, and T. Nguyen.  A tool for personal data extraction.  In Data Engineering Workshops (ICDEW) 2014 IEEE 30th International Conference on, pages 80–83, 2014.
  * [28] W. A. Wagenaar.  My memory: A study of autobiographical memory over six years.  Cognitive Psychology, 18(2):225 – 252, 1986.
  * [29] X. Wang, M. Bendersky, D. Metzler, and M. Najork.  Learning to rank with selection bias in personal search.  In Proc. of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 115–124, 2016.
  * [30] Z. Xu, M. Karlsson, C. Tang, and C. Karamanolis.  Towards a Semantic-Aware File Store.  In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS’03), 2003.
  * [31] H. Zamani, M. Bendersky, M. Zhang, and X. Wang.  Situational context for ranking in personal search.  In WWW, 2017.
  * [32] S. Zerr, E. Demidova, and S. Chernov.  deskweb2.0: Combining desktop and social search.  In Proc. of Desktop Search Workshop, In conjunction with the 33rd Annual International ACM SIGIR 2010, 23 July 2010, Geneva, Switzerland, 2010\.


A note on edge irregularity strength of Dandelion graph

H. M. Nagesh
Department of Science & Humanities,

PES University - Electronic City Campus,

Hosur Road, Bangalore – 560 100, India.

e-mail<EMAIL_ADDRESS>
Abstract: For a simple graph $G$, a vertex labeling
$\phi:V(G)\rightarrow\\{1,2,\ldots,k\\}$ is called $k$-labeling. The weight of
an edge $xy$ in $G$, written $w_{\phi}(xy)$, is the sum of the labels of end
vertices $x$ and $y$, i.e., $w_{\phi}(xy)=\phi(x)+\phi(y)$. A vertex
$k$-labeling is defined to be an edge irregular $k$-labeling of the graph $G$
if for every two different edges $e$ and $f$, $w_{\phi}(e)\neq w_{\phi}(f)$.
The minimum $k$ for which the graph $G$ has an edge irregular $k$-labeling is
called the edge irregularity strength of $G$, written $es(G)$. In this note,
we find the exact value of edge irregularity strength of Dandelion graph when
$\Delta(G)\geq\lceil\frac{|E(G)|+1}{2}\rceil$; and determine the bounds when
$\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$.
Keywords: Irregular assignment, Irregularity strength, Irregular total
$k$-labeling, Edge irregularity strength, Dandelion graph.
2020 Mathematics Subject Classification: 05C38, 05C78.

##  1 Introduction

Let $G$ be a connected, simple and undirected graph with vertex set $V(G)$ and
edge set $E(G)$. By a labeling we mean any mapping that maps a set of graph
elements to a set of numbers (usually positive integers), called labels. If
the domain is the vertex-set (the edge-set), then the labeling is called
_vertex labelings_ (_edge labelings_). If the domain is $V(G)\cup E(G)$, then
the labeling is called _total labeling_. Thus, for an edge $k$-labeling
$\delta:E(G)\rightarrow\\{1,2,\ldots,k\\}$ the associated weight of a vertex
$x\in V(G)$ is $w_{\delta}(x)=\sum\delta(xy)$, where the sum is over all
vertices $y$ adjacent to $x$.

Chartrand et al. [4] defined irregular labeling for a graph $G$ as an
assignment of labels from the set of natural numbers to the edges of $G$ such
that the sums of the labels assigned to the edges of each vertex are
different. The minimum value of the largest label of an edge over all existing
irregular labelings is known as the _irregularity strength_ of $G$ and it is
denoted by $s(G)$. Finding the irregularity strength of a graph seems to be
hard even for simple graphs [4].

Motivated by this, Baca et al. [3] investigated two modifications of the
irregularity strength of graphs, namely _total edge irregularity strength_ ,
denoted by $tes(G)$; and _total vertex irregularity strength_ , denoted by
$tvs(G)$. Motivated by the work of Chartrand et al. [4], Ahmad et al. [1]
introduced the concept of edge irregular $k$-labelings of graphs.

A vertex labeling $\phi:V(G)\rightarrow\\{1,2,\ldots,k\\}$ is called
$k$-labeling. The weight of an edge $xy$ in $G$, written $w_{\phi}(xy)$, is
the sum of the labels of end vertices $x$ and $y$, i.e.,
$w_{\phi}(xy)=\phi(x)+\phi(y)$. A vertex $k$-labeling of a graph $G$ is
defined to be an _edge irregular $k$-labeling_ of the graph $G$ if for every
two different edges $e$ and $f$, $w_{\phi}(e)\neq w_{\phi}(f)$. The minimum
$k$ for which the graph $G$ has an edge irregular $k$-labeling is called the
_edge irregularity strength_ of $G$, written $es(G)$.

##  2 Preliminary results

The authors in [1] estimated the bounds of the edge irregularity strength and
then determined its exact value for several families of graphs namely, paths,
stars, double stars, and Cartesian product of two paths. Ahmad et al. [2]
determined the edge irregularity strength of Toeplitz graphs. Tarawneh et al.
[7] determined the exact value of edge irregularity strength of corona product
of graphs with paths. Tarawneh et al. [8] determined the exact value of edge
irregularity strength of disjoint union of graphs. Recently, Nagesh et al. [6]
determined the edge irregularity strength of line graph and line cut-vertex
graph of comb graph.

The following theorem in [1] establishes the lower bound for the edge
irregularity strength of a graph $G$.

######  Theorem 2.1.

Let $G=(V,E)$ be a simple graph with maximum degree $\Delta(G)$. Then

$es(G)\geq\max\\{\lceil\frac{|E(G)|+1}{2}\rceil,\Delta(G)\\}.$

##  3 Edge irregularity strength of Dandelion graph

The authors in [5] introduced the concept of Dandelion graph while studying
the Wiener inverse interval problem.

######  Definition 3.1.

A _star graph_ , written $s_{n-1}$, is a graph on $n$ vertices, consisting of
some vertex, connected to $n-1$ leaves.

######  Definition 3.2.

The _Dandelion graph_ , written $D(n,l)$, is a graph on $n$ vertices,
consisted of a copy of the star $S_{n-1}$ and copy of a path $p_{l}$ on
vertices $p_{0},p_{1},p_{2},\ldots,p_{l-1}$, where $p_{0}$ is identified with
a star center.

Figure 1 shows an example of $D(17,8)$.

Figure 1

In the next theorem, we find the exact value of edge irregularity strength of
Dandelion graph when $\Delta(G)\geq\lceil\frac{|E(G)|+1}{2}\rceil$; and
determine the bounds when $\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$.

######  Theorem 3.3.

Let $G=D(n,l)$ be the Dandelion graph. Then

$es(G)=n-l+1\hskip 14.22636pt\text{for \
}\Delta(G)\geq\lceil\frac{|E(G)|+1}{2}\rceil$

For $\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$,

$\lceil\frac{n}{2}\rceil\leq es(G)\leq n-l+\lceil\frac{l}{2}\rceil$.

###### Proof.

Let $G=D(n,l)$ be the Dandelion graph. Let us consider the vertex set and the
edge set of $G$:

$\displaystyle V(G)$ $\displaystyle=\\{x_{i}:1\leq i\leq
n-l\\}\cup\\{p_{j}:0\leq j\leq l-1\\},$ $\displaystyle E(G)$
$\displaystyle=\\{p_{0}x_{i},p_{j}p_{j+1}:1\leq i\leq n-l,0\leq j\leq l-2\\}.$

We consider the following three cases.

Case 1: When $\Delta(G)>\lceil\frac{|E(G)|+1}{2}\rceil$. Clearly, $|V(G)|=n$,
$|E(G)|=n-1$, and the maximum degree $\Delta=n-l+1$. According to the Theorem
2.1, $es(G)\geq\max\\{\lceil\frac{n}{2}\rceil,n-l+1\\}$. Since
$n-l+1>\lceil\frac{n}{2}\rceil$, $es(G)\geq n-l+1$.

To prove the equality, it suffices to prove the existence of an edge irregular
$(n-l+1)-$labeling. Define a labeling on vertex set of $G$ as follows:

Let $\phi:V(G)\rightarrow\\{1,2,\ldots,n-l+1\\}$ such that $\phi(x_{i})=i$ for
$1\leq i\leq n-l$; $\phi(p_{0})=1$; $\phi(p_{1})=n-l+1$; $\phi(p_{2})=4$;
$\phi(p_{2i+1})=\phi(p_{2i})=n-l-j$ for $i=1,2,3,\ldots,$ and
$j=0,1,2,\ldots$.

The edge weights are as follows:

$w_{\phi}(p_{0}x_{i})=i+1\hskip 5.69054pt\text{for }1\leq i\leq n-l$;

$w_{\phi}(p_{0}p_{1})=n-l+2$,

$w_{\phi}(p_{1}p_{2})=n-l+5$;

$w_{\phi}(p_{2}p_{3})=n-l+4$;

$w_{\phi}(p_{i}p_{i+1})=2n-2l-j$ for $3\leq i\leq l-2$ and $j=0,1,2,\ldots$.

On the basis of above calculations we see that the edge weights are distinct
for all pairs of distinct edges. Therefore, $es(G)=n-l+1$.

Figure 2 shows the edge irregularity strength of the Dandelion graph
$D(13,5)$, where the maximum degree $\Delta=9$ and $|E(D(13,5))|=12$.

Figure 2

Case 2: When $\Delta(G)=\lceil\frac{|E(G)|+1}{2}\rceil$. Note that
$\Delta(G)=\lceil\frac{|E(G)|+1}{2}\rceil$ for the Dandelion graphs
$D(2i+3,i+2)$ and $D(2i+4,i+3)$ for $i\geq 1$.

Since $|E(G)|=n-1$ and the maximum degree $\Delta=n-l+1$, according to the
Theorem 2.1, $es(G)\geq n-l+1$.

To prove the equality, it suffices to prove the existence of an edge irregular
$(n-l+1)-$labeling.

Let $\phi:V(G)\rightarrow\\{1,2,\ldots,n-l+1\\}$ such that $\phi(x_{i})=i$ for
$1\leq i\leq n-l$; $\phi(p_{0})=1$; $\phi(p_{1})=\phi(p_{2})=n-l+1$;
$\phi(p_{2i+1})=\phi(p_{2i+2})=n-l-j$ for $i=1,2,3,\ldots,$ and
$j=0,1,2,\ldots$.

The edge weights are as follows:

$w_{\phi}(p_{0}x_{i})=i+1\hskip 5.69054pt\text{for }1\leq i\leq n-l$;

$w_{\phi}(p_{0}p_{1})=n-l+2$,

$w_{\phi}(p_{1}p_{2})=2n-2l+2$;

$w_{\phi}(p_{2}p_{3})=2n-2l+1$;

$w_{\phi}(p_{i}p_{i+1})=2n-2l-j$ for $3\leq i\leq l-2$ and $j=0,1,2,\ldots$.

On the basis of above calculations we see that the edge weights are distinct
for all pairs of distinct edges. Therefore, $es(G)=n-l+1$.

Figure 3 shows the edge irregularity strength of the Dandelion graph $D(9,5)$,
where the maximum degree $\Delta=5$ and $|E(D(9,5))|=8$.

Figure 3

Finally, we have to prove that $\lceil\frac{n}{2}\rceil\leq es(G)\leq
n-l+\lceil\frac{l}{2}\rceil$ for $\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$

Case 3: When $\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$. According to the
Theorem 2.1, $es(G)\geq\max\\{\lceil\frac{n}{2}\rceil,n-l+1\\}$. Hence
$es(G)\geq\lceil\frac{n}{2}\rceil$. For the upper bound, we define a vertex
labeling $\phi$ as follows:

Let $\phi:V(G)\rightarrow\\{1,2,\ldots,n-l+\lceil\frac{l}{2}\rceil\\}$ such
that $\phi(x_{i})=i$ for $1\leq i\leq n-l$; $\phi(p_{0})=1$;
$\phi(p_{i})=\phi(p_{i+1})=n-l+i$ for $i=1,2,3,\ldots$.

The edge weights are as follows:

$w_{\phi}(p_{0}x_{i})=i+1\hskip 5.69054pt\text{for }1\leq i\leq n-l$;

$w_{\phi}(p_{0}p_{1})=n-l+2$;

$w_{\phi}(p_{i}p_{i+1})=2n-2l+i+1$ for $i=1,2,3,\ldots$.

On the basis of above calculations we see that the edge weights are distinct
for all pairs of distinct edges. Therefore, the vertex labeling $\phi$ is an
edge irregular $n-l+\lceil\frac{l}{2}\rceil-$labeling, i.e., $es(G)\leq
n-l+\lceil\frac{l}{2}\rceil$ for $\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$.
This completes the proof. ∎

Figure 4 shows the edge irregularity strength of the Dandelion graph $D(7,5)$,
where the maximum degree $\Delta=3$ and $|E(D(7,5))|=6$.

Figure 4

##  4 Conclusion

In this note, we have found the exact value of edge irregularity strength of
an important class of graph, namely, Dandelion graph $D(n,l)$, when
$\Delta(G)\geq\lceil\frac{|E(G)|+1}{2}\rceil$; and determine the bounds when
$\Delta(G)<\lceil\frac{|E(G)|+1}{2}\rceil$. However, to find the exact value
of edge irregularity strength of many other important class of graphs still
remain open.

## References

  * [1]  Ahmad, A., Al-Mushayt, O., & Baca, M. (2014). On edge irregularity strength of graphs. Applied Mathematics and Computation, 243, 607–610.
  * [2]  Ahmad, A., Baca, M., & Nadeem, M. F. (2016). On the edge irregularity strength of Toeplitz graphs. Scientific Bulletin-University Politehnica of Bucharest, 78, 155–162.
  * [3]  Baca, M., Jendrol, S., Miller, M., & Ryan, J. (2007). On irregular total labellings. Discrete Mathematics, 307, 1378–1388.
  * [4]  Chartrand, G., Jacobson, M. S., Lehel, J., Oellermann, O. R., & Saba, F. (1988). Irregular networks. Congressus Numerantium, 64, 187–192.
  * [5]  Matjaž Krnca & Riste Škrekovski. (2016). On Wiener Inverse Interval Problem. _MATCH Commun. Math. Comput. Chem_ , 75, 71-80.
  * [6]  Nagesh, H, M., & Girish, V. R. (2022). On edge irregularity strength of line graph and line cut-vertex graph of comb graph. _Notes on Number Theory and Discrete Mathematics_ , 28(3), 517-524.
  * [7]  Tarawneh, I., Hasni, R., & Ahmad, A. (2016). On the edge irregularity strength of corona product of graphs with paths. Applied Mathematics E-Notes, 16, 80–87.
  * [8]  Tarawneh, I., Hasni, R., Asim, M. A., & Siddiqui, M. A. (2019). On the edge irregularity strength of disjoint union of graphs. Ars Combinatoria, 142, 239–249.