# OntoMerger: An Ontology Integration Library for Deduplicating and Connecting
Knowledge Graph Nodes

David Geleta  AstraZenecaUnited Kingdom ,  Andriy Nikolov  AstraZenecaUnited
Kingdom ,  Mark O’Donoghue  AstraZenecaUnited Kingdom ,  Benedek Rozemberczki
AstraZenecaUnited Kingdom ,  Anna Gogleva  AstraZenecaUnited Kingdom ,
Valentina Tamma  The University of LiverpoolUnited Kingdom and  Terry R. Payne
The University of LiverpoolUnited Kingdom

###### Abstract.

Duplication of nodes111For example, the concept of the disease Asthma may be
represented as $\mathsf{MONDO:0004979}$ or $\mathsf{DOID:2841}$ in two
different datasets. is a common problem encountered when building knowledge
graphs (KGs) from heterogeneous datasets, where it is crucial to be able to
merge nodes having the same meaning. OntoMerger is a Python ontology
integration library whose functionality is to deduplicate KG nodes. Our
approach takes a set of KG nodes, mappings and disconnected hierarchies and
generates a set of merged nodes together with a connected hierarchy. In
addition, the library provides analytic and data testing functionalities that
can be used to fine-tune the inputs, further reducing duplication, and to
increase connectivity of the output graph. OntoMerger can be applied to a wide
variety of ontologies and KGs. In this paper we introduce OntoMerger and
illustrate its functionality on a real-world biomedical KG.

##  1\. Introduction

Complex knowledge graphs (KGs) (Geleta et al., 2021; Sinha et al., 2015) are
often built from multiple overlapping but heterogeneous data sets. For
example, a biomedical KG can include separate data sets providing information
about genes, diseases, compounds and relations between these entities (Geleta
et al., 2021; Himmelstein et al., 2017; Zitnik et al., 2018; Breit et al.,
2020; Walsh et al., 2020; Barisevičius et al., 2018). Typically, these data
sets rely on diverse ontologies to refer to the same concepts with no obvious
mapping or alignment between them (Bonner et al., 2021). Furthermore, data
version discrepancy can also lead to duplication when concepts get deprecated
and identifiers reassigned. On a large scale, these issues may cause syntactic
and semantic heterogeneity in the resulting graph; which in turn can lead to
fragmented knowledge that can negatively impact downstream applications
(Hamilton, 2020) due to possible incompatibilities between the hierarchies,
that in turn may lead to logical inconsistencies. Thus, organising concepts of
the same domain into a hierarchy (Wang et al., 2021) might improve the
accuracy of machine learning models, e.g. pattern recognition.

Figure 1. An example HTML report generated by OntoMerger.

OntoMerger tackles these challenges by using a scaffolding ontology, together
with mappings and concept hierarchies, to produce an integrated domain
ontology with a single DAG (Directed Acyclic Graph) hierarchy. By design, this
ontology is not intended to retain complete knowledge for all the integrated
concepts (such as hierarchical connections and the granularity of the original
conceptualisation), but rather relies on additional mappings provided by the
users, that are then used to infer new ones. The library is open
source222https://github.com/AstraZeneca/onto_merger, implemented in Python
(Van Rossum and Drake, 2009), and is available to
download333https://pypi.org/project/onto_merger as a package via PyPi. The
library processes data in tabular format using Pandas (McKinney et al., 2011).
OntoMerger produces the hierarchy by converting hierarchy triples into graph
objects and by running queries for finding paths (using NetworKit (Staudt et
al., 2016)), as well as for counting sub-graphs (using NetworkX (Hagberg et
al., 2008)). To ensure stable performance, input and output data is tested
using the Great Expectations (Gong and Campbell, 2021) validation framework.
In addition, the library provides an in-depth analysis by using the the Pandas
Profiling package444https://github.com/ydataai/pandas-profiling/ to profile
all the data that is consumed and produced. Insights about the  (i) input,
(ii) intermediate and produced data (i.e. the domain ontology),  (iii) results
of data profiling and data validation, and  (iv) metrics about the inner
workings of the library  are presented in an HTML report, shown in Figure 1.

##  2\. Related work

Ontology integration has been the focus of the research community for several
years (Osman et al., 2021). Whilst _ontology matching_ (Euzenat et al., 2013)
focuses on the automated alignment, or generation of sets of mappings between
the corresponding elements of different ontologies, the use of these mappings
to produce a coherent, integrated ontology is non-trivial. This is due to the
need to satisfy _merge requirements_ (Pottinger and Bernstein, 2003) such as:
preserving correctness and coherence; maintaining acyclicity; and avoiding
redundancy. To satisfy these requirements, existing algorithms either modify
the generated alignments (Stoilos et al., 2018a; Jimenez-Ruiz et al., 2016;
Solimando et al., 2017; Udrea et al., 2007) or the ontologies themselves
(Jiménez-Ruiz et al., 2009; Raunich and Rahm, 2014; Fahad et al., 2012).

Despite the significant effort invested in the ontology integration problem,
existing methods do not always satisfy the requirements of real-world use
cases in the context of large scale data science, which can compromises their
pragmatic use. For example, existing systems usually rely on OWL semantics and
on the explicit constraints defined in source ontologies. However, implicit
constraints may also exist; for example, two concepts in the same ontology may
not be explicitly declared as disjoint, but this may be implicitly desirable
to avoid them being merged as a result of ontology integration.

##  3\. Preliminaries

In this paper, we assume familiarity with basic notions of RDF (Klyne, 2004),
ontology alignment and integration (Euzenat et al., 2013).

###### Definition 0 (Concept Name Set).

The symbol $\mathsf{C}$ denotes a set of concept names
$\mathsf{C=\\{c_{1},...,c_{n}\\}}$ where $|\mathsf{C}|=n$. A set of concept
names from the same ontology is denoted as $\mathsf{C}_{\mathcal{O}}$.

###### Definition 0 (Mapping and Mapping Set).

A concept mapping is a triple
$\mathsf{m}=\left\langle\mathsf{c},\mathsf{r},\mathsf{c^{\prime}}\right\rangle$,
asserting that some relation $\mathsf{r}$ holds between concepts $\mathsf{c}$
and $\mathsf{c^{\prime}}$, where either
$\\{\mathsf{c},\mathsf{c^{\prime}}\\}\in\mathsf{C}_{\mathcal{O}}$, or
$\mathsf{c}\in\mathsf{C}_{\mathcal{O}}$ and
$\mathsf{c}^{\prime}\in\mathsf{C}_{\mathcal{O}^{\prime}}$, given the
ontologies $\mathcal{O}$ and $\mathcal{O}^{\prime}$. The symbol $\mathsf{M}$
denotes a set of concept mappings $\mathsf{M=\\{m_{1},...,m_{n}\\}}$,
$|\mathsf{M}|=n$.

The semantics of a mapping relation $\mathsf{r}$ may vary due to the diversity
of input mappings that originate from different sources in real world
scenarios. The may be formally defined (Euzenat et al., 2013);
$\mathsf{r\in\\{\equiv,\sqsubseteq,\sqsupseteq,\perp\\}}$, or may be loosely
defined, such as $\mathsf{r}\in\\{\approxeq,\textsc{db\\_xref}\\}$, etc. The
concepts $\mathsf{c}$ and $\mathsf{c}^{\prime}$ refer to the _source_ and
_target_ concepts respectively.

###### Definition 0 (Hierarchy Edge and Hierarchy Edge Set).

Given two ontologies, $\mathcal{O}$ and $\mathcal{O}^{\prime}$, a concept
hierarchy edge is a triple
$\mathsf{h}=\left\langle\mathsf{c},\sqsubseteq,\mathsf{c^{\prime}}\right\rangle$,
which asserts that a subsumption relation ($\sqsubseteq$) holds between
concepts $\mathsf{c}$ and $\mathsf{c^{\prime}}$, where either
$\\{\mathsf{c},\mathsf{c^{\prime}}\\}\in\mathcal{O}$, or
$\mathsf{c}\in\mathcal{O}$ and $\mathsf{c}^{\prime}\in\mathcal{O}^{\prime}$.
The symbol $\mathsf{H}$ denotes the concept hierarchy edge set
$\mathsf{H=\\{h_{1},...,h_{n}\\}}$, with $|\mathsf{H}|=n$.

###### Definition 0 (Merge and Merge Set).

A concept merge is a triple
$\mathsf{x}=\left\langle\mathsf{c},\Rightarrow,\mathsf{c^{\prime}}\right\rangle$,
asserting that a concept $\mathsf{c}$ can be replaced by $\mathsf{c}^{\prime}$
in a concept, mapping or in a hierarchy edge set. The symbol $\mathsf{X}$
denotes the set of merges $\mathsf{X=\\{x_{1},...,x_{n}\\}}$, with
$|\mathsf{X}|=n$.

###### Definition 0 (Stable Merge Set).

A merge set is $\mathsf{X}$ is stable if a concept only appears in one merge
$\mathsf{x}\in\mathsf{X}$ and only as a source concept.

In the definitions of mapping, hierarchy edge, and merge triples, we refer to
$\mathsf{c}$ as the source and $\mathsf{c}^{\prime}$ as the target concept.
The function Sig returns the source ($\textsc{Sig}_{source}$), target
($\textsc{Sig}_{target}$) or both (Sig) set of concept names from either an
individual mapping or from a set of mappings, merges, hierarchy edges or
paths.

##  4\. Integration design

The integration design process requires the following input sets: concept
names $\mathsf{C}_{in}$, obsolete (i.e. deprecated) concept names
$\mathsf{C}_{obs}$ ($\mathsf{C}_{obs}\subseteq\mathsf{C}_{in}$ and
$0\leq|\mathsf{C}_{obs}|\leq|\mathsf{C}_{in}|$), mappings $\mathsf{M}_{in}$,
and hierarchy edges $\mathsf{H}_{in}$; where each set may contain members from
different ontologies. In addition, a configuration must specify the concept
names in a Seed ontology, such that
$\mathsf{C}_{\mathcal{O}_{\textsc{Seed}}}\subseteq\mathsf{C}_{in}$ and
$\mathsf{H}_{\mathcal{O}_{\textsc{Seed}}}\subseteq\mathsf{H}_{in}$. No other
ontology must be fully contained in the input sets other than the Seed
ontology.

The optional preference order in which the concepts are de-duplicated and
connected (denoted as Sources) can also be specified. If it is omitted, it
will be computed by taking the frequency of each ontology concept set of
$\mathsf{C}_{in}$ in decreasing order. In either case, the Seed ontology will
be the first item in Sources. The configuration must also contain the
MappingGroups list that categorises the mapping types of $\mathsf{M}_{in}$
into a minimum of two categories: equivalence and reference (where the
equivalence group must have at least one member, and the other groups can be
empty sets). These categories represent the strength of the mapping relations
and are handled in sequence (in decreasing order starting from the strongest
group) during the deduplication stage.

Input : $\mathsf{C}_{in}$: input concepts; $\mathsf{C}_{obs}$: obsolete
concepts of $\mathsf{C}_{in}$; $\mathsf{M}_{in}$: input mappings;
$\mathsf{H}_{in}$: input hierarchy edges; Seed: name of the seed ontology
(i.e.$\mathcal{O}_{\textsc{Seed}}$); Sources: preference order; MappingTypes:
mapping type groups;

Intermediate : $\mathsf{C}_{unm}$: unmerged concepts;

Output : $\mathsf{C}_{dom}$: domain concepts; $\mathsf{M}_{dom}$: domain
mappings; $\mathsf{X}_{can}$: concept merges with canonical target concepts;
$\mathsf{H}_{dom}$: domain hierarchy edge set;

1
$\mathsf{C}_{dom},\mathsf{C}_{unm},\mathsf{X}_{can},\mathsf{M}_{dom}\leftarrow\textsc{DeduplicateConcepts}(\newline
\hskip
20.00003pt\mathsf{C}_{in},\mathsf{C}_{obs},\mathsf{M}_{in},\textsc{Seed},\textsc{Sources},\textsc{MappingTypes})$

2 $\mathsf{H}_{dom}\leftarrow\textsc{ConnectConcepts}(\newline \hskip
20.00003pt\mathsf{C}_{unm},\mathsf{X}_{can},\mathsf{H}_{in},\textsc{Seed},\textsc{Sources})$

3 return $\mathsf{C}_{dom},\mathsf{M}_{dom},{X}_{can},\mathsf{H}_{dom}$

Algorithm 1 ComputeDomainOntology

The main part of OntoMerger produces the domain ontology by first
deduplicating concepts (Section 4.1) and then connecting the remaining
unmerged concepts (i.e. concepts without an accepted mapping) together to form
a single DAG, i.e. concept hierarchy (4.2). This process is formalised by
Algorithm 1.

###  4.1. Deduplication

Input : $\mathsf{C}_{in}$; $\mathsf{C}_{obs}$; $\mathsf{M}_{in}$; Seed;
Sources; MappingTypes

Output : $\mathsf{C}_{dom}$; $\mathsf{C}_{unm}$: unmerged concepts;
$\mathsf{X}_{can}$; $\mathsf{M}_{dom}$;

/* Pre-processing */

1
$\mathsf{X}_{obs},\mathsf{M}_{internal}\leftarrow\textsc{ComputeObsoleteMerges}(\mathsf{M}_{in},\mathsf{C}_{obs})$

2
$\mathsf{M}_{in}^{\prime}\leftarrow\textsc{UpdateMappings}((\mathsf{M}_{in}\setminus\mathsf{M}_{internal}),\mathsf{X}_{obs})$

3

/* Deduplication */

4 $\mathsf{X}\leftarrow\mathsf{X}_{obs}\cup\textsc{ComputeMerges}(\newline
\hskip
20.00003pt\mathsf{C}_{in},\mathsf{M}_{in}^{\prime},\textsc{Seed},\textsc{Sources},\textsc{MappingTypes})$

5

/* Post-processing */

6
$\mathsf{X}_{can}\leftarrow\textsc{AggregateMerges}(\mathsf{X},\textsc{Sources})$

7
$\mathsf{C}_{dom}\leftarrow\textsc{ApplyMerges}(\mathsf{C}_{in},\mathsf{X}_{can})$

8
$\mathsf{M}_{dom}\leftarrow\textsc{ApplyMerges}(\mathsf{M}_{dom},\mathsf{X}_{can})$

9
$\mathsf{C}_{unm}\leftarrow\mathsf{C}_{in}\setminus(\mathsf{C}_{obs}\cup\mathsf{Sig}_{source}(\mathsf{X}_{can}))$

10 return $\mathsf{C}_{dom},\mathsf{C}_{unm},{X}_{can},\mathsf{M}_{dom}$

Algorithm 2 DeduplicateConcepts

The deduplication stage, formalised by Algorithm 2, reduces the input set of
concepts ($\mathsf{C}_{in}$) by processing mappings to create a stable concept
merge set ($\mathsf{X}_{can}$).

####  4.1.1. Pre-processing.

First, we compute the merges for obsolete concepts. Some mappings assert a
relation between concepts of the same ontology to describe internal concept
renaming, i.e. when a concept is deprecated and assigned to a new name. Using
the set of obsolete concepts, the function ComputeObsoleteMerges computes
merges $\mathsf{X}_{obs}$ from the relevant input mappings
$\\{\mathsf{m}=\left\langle\mathsf{c},\equiv,\mathsf{c^{\prime}}\right\rangle\in\mathsf{M}_{in}|\\{\mathsf{c},\mathsf{c^{\prime}}\\}\in\mathcal{O},\mathsf{r}=\left\langle\mathsf{c},\Rightarrow,\mathsf{c^{\prime}}\right\rangle$
where
$\mathsf{c}\in\mathsf{C}_{obs}\wedge\mathsf{c^{\prime}}\not\in\mathsf{C}_{obs}\\}$.
Next, we update the mappings by applying the obsolete concept merges
$\mathsf{X}_{obs}$, so the output $\mathsf{M}_{in}^{\prime}$ now only contains
current concept names.

Input : $\mathsf{C}_{in}$; $\mathsf{M}_{updated}$: mappings with current
concept names; $\mathsf{X}_{obs}$; Seed; Sources; MappingTypes;

Output : $\mathsf{X}$: concept merges

1
$\mathsf{C}_{unm}\leftarrow\mathsf{C}_{in}\setminus\textsc{GetConcepts}(\mathsf{C}_{in},\textsc{Seed})$

2 $\mathsf{X}\leftarrow\emptyset$

3 for  _each $\textsc{M\\_Type}\in\textsc{MappingTypes}$_ do

4 for  _each $\textsc{Source}\in\textsc{Sources}$_ do

5
$\mathsf{M}_{Source}\leftarrow\textsc{GetMps}(\mathsf{M}_{updated},\textsc{M\\_Type},\textsc{Source})$

6
$\mathsf{M}_{Source}^{\prime}\leftarrow\textsc{Filter}(\mathsf{M}_{Source},\mathsf{C}_{unm})$

7
$\mathsf{M}_{Source}^{\prime\prime}\leftarrow\textsc{OrientTo}(\mathsf{M}_{Source}^{\prime},\textsc{Source})$

8
$\mathsf{M}_{Source}^{\prime\prime\prime}\leftarrow\textsc{Get1Or*SourceTo1Target}(\mathsf{M}_{Source}^{\prime\prime})$

9
$\mathsf{X}\leftarrow\mathsf{X}\cup\textsc{ConvertToMerges}(\mathsf{M}_{Source}^{\prime\prime\prime})$

10
$\mathsf{C}_{unm}\leftarrow\mathsf{C}_{unm}\setminus\mathsf{Sig}_{source}(\mathsf{X})\;$

11 end for

12

13 end for

14return ${X}$

Algorithm 3 ComputeMerges

####  4.1.2. Alignment.

Algorithm 3 computes the stable merge set. The set of concepts
$\mathsf{C}_{unm}$ keeps track of unmerged (i.e. not merged) concepts; this
initially contains all input concepts, excluding concepts of the seed
ontology. The alignment process loops through the mapping type groups and the
ontology alignment order. In each iteration, we attempt to align every
remaining unmerged concept to concepts of the given
$\textsc{Source}\in\textsc{Sources}$. The function GetMps returns all mappings
that are in the specified type group M_Type and map concepts of the given
Source; this ($\mathsf{M}_{Source}$) is filtered by the function Filter, so
the resulting mapping set $\mathsf{M}_{Source}^{\prime}$ only contains those
mappings that align unmerged concepts. These mappings focus on the current
Source such that the target of mappings the is always from
$\mathsf{M}_{Source}$. Finally, the oriented mapping set
$\mathsf{M}_{Source}^{\prime\prime}$ is further filtered by multiplicity with
the function Get1Or*SourceTo1Target such that in the produced mapping set
($\mathsf{M}_{Source}^{\prime\prime\prime}$) every source concept is mapped to
exactly one target concept (but one target may be mapped to many source
concepts). The mappings are then converted to merges and stored in
$\mathsf{X}$, and the mapped concepts are removed from $\mathsf{C}_{unm}$.

####  4.1.3. Post-processing.

The function AggregateMerges groups the merge set $\mathsf{X}$ and rewrites
them such that the target concept is always the canonical concept name of the
given merge cluster. Concepts of each merge group form a cluster, where only
one of these concepts is the canonical concept; this is determined by the
preference order (Sources). For example, given the merge group
$\\{\left\langle\mathsf{S_{1}:001},\Rightarrow,\mathsf{S_{2}:001}\right\rangle,\left\langle\mathsf{S_{2}:001},\Rightarrow,\mathsf{S_{3}:001}\right\rangle\\}$
and the priority order $(\mathsf{S_{3}},\mathsf{S_{2}},\mathsf{S_{1}})$,
$\\{\left\langle\mathsf{S_{1}:001},\Rightarrow,\mathsf{S_{3}:001}\right\rangle,\left\langle\mathsf{S_{2}:001},\Rightarrow,\mathsf{S_{3}:001}\right\rangle\\}$
is the canonical merge set, where $\mathsf{S_{3}:001}$ is the canonical
concept. Finally, we compute the domain concept (${C}_{dom}$) and mapping sets
(${M}_{dom}$) by applying the canonical merges (${X}_{can}$) to replace each
concept name with the corresponding canonical concept (using function
ApplyMerges), and compute the set of final unmerged concepts (${C}_{unm}$).

###  4.2. Connectivity

BEFOREDomain OntologyOther OntologyAFTERMerged
OntologyTopTopTopD1C1C2D1/C1C2NodesHierarchy edgeMapping edge

Figure 2. Integrating an unmapped concept via its original hierarchy path and
a mapped parent.

Input : $\mathsf{C}_{unm}$; $\mathsf{H}_{in}$; $\mathsf{X}_{can}$; Seed;
Sources;

Output : $\mathsf{H}_{dom}$: output hierarchy edge set;

1
$\mathsf{H}_{dom}\leftarrow\textsc{GetHierarchy}(\textsc{Seed},\mathsf{H}_{in})$

2
$\mathsf{C}_{connected}\leftarrow\textsc{Sig}(\mathsf{H}_{dom})\cup\textsc{Sig}_{source}(\textsc{GetMergesToSource}(\textsc{Seed},\mathsf{X}_{can}))$

3 for  _each $\textsc{Source}\in\textsc{Sources}$_ do

4
$\mathsf{H}_{\textsc{Source}}\leftarrow\textsc{GetHierarchy}(\textsc{Source},\mathsf{H}_{in})$

5
$\mathsf{C}_{\textsc{UnmappedSource}}\leftarrow\textsc{GetConcepts}(\mathsf{C}_{unm},\textsc{Source})$

6 for  _each $\mathsf{c}\in\mathsf{C}_{\textsc{UnmappedSource}}$_ do

7
$\mathsf{Path}_{\mathsf{c}}\leftarrow\textsc{GetShortestPathToRoot}(\mathsf{c},\mathsf{H}_{\textsc{Source}})$

8 if
_$\textsc{Sig}(\mathsf{Path}_{\mathsf{c}})\cap\mathsf{C}_{connected}\not=\emptyset$_
then

9
$\mathsf{Path}_{\mathsf{c}}^{\prime}\leftarrow\textsc{Prune}(\mathsf{Path}_{\mathsf{c}},\mathsf{C}_{connected})$

10
$\mathsf{H}_{\mathsf{c}}\leftarrow\textsc{ConvertToEdges}(\mathsf{Path}_{\mathsf{c}})$

11
$\mathsf{C}_{connected}\leftarrow\mathsf{C}_{connected}\cup\textsc{Sig}(\mathsf{H}_{\mathsf{c}})$

12 $\mathsf{H}_{dom}\leftarrow\mathsf{H}_{dom}\cup\mathsf{H}_{\mathsf{c}}$

13

14 end if

15

16 end for

17

18 end for

19return $\mathsf{H}_{domain}$

Algorithm 4 ConnectConcepts

After concept deduplication, the remaining concepts ($\mathsf{H}_{unm}$) are
organised into a DAG, i.e. a concept hierarchy using the input hierarchy edge
set ($\mathsf{H}_{in}$). This process is formalised by Algorithm 4, and the
main idea, which is a simplified version of the approach presented in (Stoilos
et al., 2018a; Juric et al., 2021), is depicted in Figure 1. First, we add the
seed ontology hierarchy to the domain hierarchy set ($\mathsf{H}_{dom}$) and
initialise the set of connected nodes with the seed hierarchy concepts and the
concepts that were merged to seed concepts. Then we iterate through each
source in the priority order and filter out the corresponding hierarchy
fragment from the input set with the function
$\textsc{GetHierarchy}(\textsc{Source},\mathsf{H}_{in})$ (because path finding
performs better on smaller inputs). Next, for each unmerged concept in
$\mathsf{H}_{\textsc{Source}}$, we check whether there is a path to the root
concept that contains a connected concept (i.e. an anchor point that is either
a seed concept, is merged to a seed concept, or has already been connected to
$\mathsf{H}_{dom}$). If there is, we prune the path by dropping those
intermediate concepts that are not in $\mathsf{C}_{\textsc{UnmappedSource}}$
and convert the pruned path to a set of hierarchy edges. Finally, we update
$\mathsf{C}_{connected}$ and $\mathsf{H}_{dom}$ before proceeding to the next
unmerged concept. The result is a crude approximation where we may lose
concept classification granularity (i.e. the dropped intermediate concepts) in
order to establish a connection that does not increase the size of the domain
concept set but maximises the hierarchy coverage of $\mathsf{C}_{unm}$ by
$\mathsf{H}_{dom}$.

##  5\. Experimental Evaluation

We conducted an experimental evaluation on a real-life data set: the disease
concepts of BIKG (Geleta et al., 2021) in order to assess the effectiveness of
our approach in reducing duplication and creating connectivity. A comparative
evaluation was not possible since currently there are no other systems that
operate with the same requirements as OntoMerger 555one of the main
requirements being availability in Python. Here we only include a brief
evaluation; however, the library produces an in-depth analysis report
666https://htmlpreview.github.io/?https://github.com/AstraZeneca/onto_merger/blob/main/data/example_report/index.html,
as depicted in Figure 1, using several metrics (Stoilos et al., 2018b) to
evaluate the KG integration.

Metric | Count (Input) | Count (Output)
---|---|---
Concept sources (ontologies) | 16 | 16
Concepts | 187,717 | 152,021
Concept merges | n/a | 35,696
Mappings | 439,389 | 133,496
Connected subgraphs | 4 | 1
Hierarchy edges | 272,824 | 60,621
Table 1. Input and output (domain ontology) comparison

Table 1 shows a comparison of the input and output data, while Table 2
presents the results of the deduplication of concepts and the creation of the
concept hierarchy. 30.79% of input concepts (of 16 sources) were merged, and
41.11% were successfully integrated into a DAG using only 4 hierarchies. The
overall run time of the process was 25 minutes on an average machine (6 core
CPU, 32GB memory). The majority of the run time was the generation of the
concept hierarchy (72%) and the result analysis (13%).

Stage | Concept set | Count | Ratio (%)
---|---|---|---
Input | 187,717 | 100.00%
Deduplication | (Mapped) Seed | 21,910 | 11.78%
(Mapped) to Seed | 34,333 | 18.28%
(Mapped) to other (excluding to seed) | 1,363 | 0.72%
Unmapped | 129,912 | 69.21%
Connectivity | (Connected) Seed + Mapped to Seed | 56,442 | 30.06%
(Connected) | 20,740 | 11.05%
Disconnected | 109,172 | 58.16%
Table 2. Concept deduplication and connectivity status

##  6\. Conclusions

In this paper we have presented OntoMerger, an ontology integration library
that deduplicates KG concepts of the same domain, and organises them into a
single DAG, i.e. a concept hierarchy. Furthermore, we have empirically
evaluated the approaches that perform deduplication of concepts and the
formation of the concept hierarchy. In this section, we address the
limitations of the library and outline directions for our future work.

Limitations. The library does not directly consume traditional RDF formats but
requires the additional step of parsing and transforming concept names,
mappings, and hierarchy edges into a columnar data structure. Moreover, the
output is also in a columnar format. The library handles all data in-memory,
posing several limitations regarding the scalability of the system. Firstly,
processing tables with Pandas becomes challenging for large datasets.
Secondly, hierarchy path computation slows down significantly due to using in-
memory graphs. Currently, only the shortest path is computed for each concept
when we attempt to connect them to the domain hierarchy. However, in many
ontologies, there are often multiple possible paths to the root of the
ontology. Using only one path could lead to missing out on paths that contain
an anchor point, i.e. a connected concept.

Future Directions. In order to get a better view of the effectiveness of this
approach, we plan to conduct a comparative evaluation of our system with
several available (Java) ontology integration libraries. The library could use
a mediator step to consume RDF formats directly and translate them into the
internal columnar data structures. There are several libraries available that
perform RDF to table translation, for instance KGTK (Ilievski et al., 2020).

To address scalability when handling large tables, the system could use
distributed data processing such as Spark (Zaharia et al., 2016). Path
computation could be scaled by using an external triple store, where path
computation is optimised (this is often achieved by the full materialisation
of hierarchy triples) (Pokorný, 2015). Offloading path computation would also
enable us to use more than one path during the hierarchy formation process.
However, this could also be improved by either implementing a greedy strategy
(keep looking for paths until a suitable one is found) or providing the
ability to specify the path computation strategy in the OntoMerger
configuration file. Finally, OntoMerger may merge concepts of the same
ontology when it may be more appropriate to convert these merges into
hierarchy edges.

## References

  * (1)
  * Barisevičius et al. (2018) Gintaras Barisevičius, Martin Coste, David Geleta, Damir Juric, Mohammad Khodadadi, Giorgos Stoilos, and Ilya Zaihrayeu. 2018\.  Supporting Digital Healthcare Services Using Semantic Web Technologies. In _The Semantic Web – ISWC 2018_ , Denny Vrandečić, Kalina Bontcheva, Mari Carmen Suárez-Figueroa, Valentina Presutti, Irene Celino, Marta Sabou, Lucie-Aimée Kaffee, and Elena Simperl (Eds.). Springer International Publishing, Cham, 291–306.
  * Bonner et al. (2021) Stephen Bonner, Ian P Barrett, Cheng Ye, Rowan Swiers, Ola Engkvist, Andreas Bender, Charles Tapley Hoyt, and William Hamilton. 2021.  A review of biomedical datasets relating to drug discovery: A knowledge graph perspective.  _arXiv preprint arXiv:2102.10062_ abs/2102.10062 (2021), 1–34.
  * Breit et al. (2020) Anna Breit, Simon Ott, Asan Agibetov, and Matthias Samwald. 2020\.  OpenBioLink: a benchmarking framework for large-scale biomedical link prediction.  _Bioinformatics_ 36, 13 (2020), 4097–4098.
  * Euzenat et al. (2013) Jérôme Euzenat, Pavel Shvaiko, et al. 2013\.  _Ontology matching_.  Springer, Berlin, Heidelberg.
  * Fahad et al. (2012) Muhammad Fahad, Néjib Moalla, and Abdelaziz Bouras. 2012.  Detection and resolution of semantic inconsistency and redundancy in an automatic ontology merging system.  _J. Intell. Inf. Syst._ 39, 2 (2012), 535–557.  https://doi.org/10.1007/s10844-012-0202-y
  * Geleta et al. (2021) David Geleta, Andriy Nikolov, Gavin Edwards, Anna Gogleva, Richard Jackson, Erik Jansson, Andrej Lamov, Sebastian Nilsson, Marina Pettersson, Vladimir Poroshin, et al. 2021\.  Biological Insights Knowledge Graph: an integrated knowledge graph to support drug development.  _bioRxiv_ bioRxiv 2021.10.28.466262 (2021), 1–24.  https://doi.org/10.1101/2021.10.28.466262 arXiv:https://www.biorxiv.org/content/early/2021/11/01/2021.10.28.466262.full.pdf
  * Gong and Campbell (2021) Abe Gong and James Campbell. 2021.  Great Expectations.  https://github.com/great-expectations/great_expectations.
  * Hagberg et al. (2008) Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008\.  _Exploring network structure, dynamics, and function using NetworkX_.  Technical Report. Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  * Hamilton (2020) William L Hamilton. 2020\.  Graph representation learning.  _Synthesis Lectures on Artifical Intelligence and Machine Learning_ 14, 3 (2020), 1–159.
  * Himmelstein et al. (2017) Daniel Scott Himmelstein, Antoine Lizee, Christine Hessler, Leo Brueggeman, Sabrina L Chen, Dexter Hadley, Ari Green, Pouya Khankhanian, and Sergio E Baranzini. 2017.  Systematic integration of biomedical knowledge prioritizes drugs for repurposing.  _Elife_ 6 (2017), e26726.
  * Ilievski et al. (2020) Filip Ilievski, Daniel Garijo, Hans Chalupsky, Naren Teja Divvala, Yixiang Yao, Craig Milo Rogers, Ronpeng Li, Jun Liu, Amandeep Singh, Daniel Schwabe, and Pedro A. Szekely. 2020.  KGTK: A Toolkit for Large Knowledge Graph Manipulation and Analysis.  _CoRR_ abs/2006.00088 (2020), 16 pages.  https://doi.org/10.48550/arXiv.2006.00088 arXiv:arXiv:2006.00088
  * Jiménez-Ruiz et al. (2009) Ernesto Jiménez-Ruiz, Bernardo Cuenca Grau, Ian Horrocks, and Rafael Berlanga Llavori. 2009.  Ontology Integration Using Mappings: Towards Getting the Right Logical Consequences. In _The Semantic Web: Research and Applications, 6th European Semantic Web Conference, ESWC 2009, Heraklion, Crete, Greece, May 31-June 4, 2009, Proceedings_ _(Lecture Notes in Computer Science, Vol. 5554)_. Springer, Berlin, Heidelberg, 173–187.  https://doi.org/10.1007/978-3-642-02121-3_16
  * Jimenez-Ruiz et al. (2016) Ernesto Jimenez-Ruiz, Terry R. Payne, Alessandro Solimando, and Valentina Tamma. 2016.  Limiting Logical Violations in Ontology Alignment Through Negotiation. In _Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR)_. AAAI Press, Cambridge, MA, USA, 217–226.
  * Juric et al. (2021) Damir Juric, David Geleta, Gregory McKay, and Giorgos Stoilos. 2021.  A Platform and Algorithms for Interoperability Between Clinical Coding Systems.  _Procedia Computer Science_ 192 (2021), 563–572.
  * Klyne (2004) Graham Klyne. 2004\.  Resource description framework (RDF): Concepts and abstract syntax.  http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/
  * McKinney et al. (2011) Wes McKinney et al. 2011\.  pandas: a foundational Python library for data analysis and statistics.  _Python for high performance and scientific computing_ 14, 9 (2011), 1–9.
  * Osman et al. (2021) Inès Osman, Sadok Ben Yahia, and Gayo Diallo. 2021\.  Ontology Integration: Approaches and Challenging Issues.  _Information Fusion_ 71 (2021), 38–63.  https://doi.org/10.1016/j.inffus.2021.01.007
  * Pokorný (2015) Jaroslav Pokorný. 2015\.  Graph Databases: Their Power and Limitations. In _Computer Information Systems and Industrial Management_ , Khalid Saeed and Wladyslaw Homenda (Eds.). Springer International Publishing, Cham, 58–69.
  * Pottinger and Bernstein (2003) Rachel A. Pottinger and Philip A. Bernstein. 2003.  Merging Models Based on Given Correspondences. In _Proceedings 2003 VLDB Conference_ , Johann-Christoph Freytag, Peter Lockemann, Serge Abiteboul, Michael Carey, Patricia Selinger, and Andreas Heuer (Eds.). Morgan Kaufmann, San Francisco, 862–873.  https://doi.org/10.1016/B978-012722442-8/50081-1
  * Raunich and Rahm (2014) Salvatore Raunich and Erhard Rahm. 2014.  Target-driven merging of taxonomies with Atom.  _Information Systems_ 42 (2014), 1–14.  https://doi.org/10.1016/j.is.2013.11.001
  * Sinha et al. (2015) Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. 2015.  An Overview of Microsoft Academic Service (MAS) and Applications. In _Proceedings of the 24th international conference on world wide web_. Association for Computing Machinery, New York, NY, USA, 243–246.
  * Solimando et al. (2017) Alessandro Solimando, Ernesto Jiménez-Ruiz, and Giovanna Guerrini. 2017.  Minimizing conservativity violations in ontology alignments: algorithms and evaluation.  _Knowledge and Information Systems_ 51, 3 (2017), 775–819.  https://doi.org/10.1007/s10115-016-0983-3
  * Staudt et al. (2016) Christian L Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. 2016.  NetworKit: A tool suite for large-scale complex network analysis.  _Network Science_ 4, 4 (2016), 508–530.
  * Stoilos et al. (2018a) Giorgos Stoilos, David Geleta, Jetendr Shamdasani, and Mohammad Khodadadi. 2018a.  A novel approach and practical algorithms for ontology integration. In _The Semantic Web – ISWC 2018_. Springer International Publishing, Cham, 458–476.
  * Stoilos et al. (2018b) Giorgos Stoilos, David Geleta, Szymon Wartak, Sheldon Hall, Mohammad Khodadadi, Yizheng Zhao, Ghadah Alghamdi, and Renate A Schmidt. 2018b.  Methods and Metrics for Knowledge Base Engineering and Integration.. In _Proceedings of the 9th Workshop on Ontology Design and Patterns (WOP 2018) co-located with 17th International Semantic Web Conference (ISWC 2018), Monterey, USA, October 9th, 2018_. CEUR-WS.org, Monterey, USA, 72–86.
  * Udrea et al. (2007) Octavian Udrea, Lise Getoor, and Renée J. Miller. 2007\.  Leveraging data and structure in ontology integration. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007_ , Chee Yong Chan, Beng Chin Ooi, and Aoying Zhou (Eds.). Association for Computing Machinery, New York, NY, USA, 449–460.  https://doi.org/10.1145/1247480.1247531
  * Van Rossum and Drake (2009) Guido Van Rossum and Fred L. Drake. 2009.  _Python 3 Reference Manual_.  CreateSpace, Scotts Valley, CA.
  * Walsh et al. (2020) Brian Walsh, Sameh K Mohamed, and Vít Nováček. 2020\.  Biokg: A knowledge graph for relational learning on biological data. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. Association for Computing Machinery, New York, NY, USA, 3173–3180.
  * Wang et al. (2021) Sheng Wang, Angela Oliveira Pisco, Aaron McGeever, Maria Brbic, Marinka Zitnik, Spyros Darmanis, Jure Leskovec, Jim Karkanias, and Russ B Altman. 2021\.  Leveraging the Cell Ontology to classify unseen cell types.  _Nature communications_ 12, 1 (2021), 1–11.
  * Zaharia et al. (2016) Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. 2016\.  Apache Spark: A Unified Engine for Big Data Processing.  _Commun. ACM_ 59, 11 (oct 2016), 56–65.  https://doi.org/10.1145/2934664
  * Zitnik et al. (2018) Marinka Zitnik, Rok Sosic, Sagar Maheshwari, and Jure Leskovec. 2018.  BioSNAP Datasets: Stanford Biomedical Network Dataset Collection.  http://snap.stanford.edu/biodata.


# On the sufficient conditions for the S-shaped Buckley–Leverett function

N. V. Rastegaev
St. Petersburg State University
7/9 Universitetskaya nab., St. Petersburg, 199034 Russia
<EMAIL_ADDRESS>
###### Abstract

The flux function in the Buckley–Leverett equation, that is, the function
characterizing the ratio of the relative mobility functions of the two phases,
is considered. The common conjecture stating that any convex mobilities result
in an S-shaped Buckley–Leverett function is analyzed and disproved by a
counterexample. Additionally, sufficient conditions for the S-shaped
Buckley–Leverett function are given. The class of functions satisfying those
conditions is proven to be closed under multiplication. Some functions from
known relative mobility models are confirmed to be in that class.

##  1 Introduction

In fluid dynamics, the Buckley–Leverett equation is one of the simplest
conservation laws used to model two-phase flow in porous media. The equation
is given by:

$s_{t}+f(s)_{x}=0,$

where $s=s(x,t)$ is the water saturation and $f$ is the fractional flow
function, also known as the Buckley–Leverett function. This function
characterizes the ratio of relative mobilities of the two phases, which is
expressed as:

$f(s)=\dfrac{m_{a}(s)}{m_{a}(s)+m_{b}(1-s)},$

where $m_{a}$ and $m_{b}$ represent the relative phase mobilities, typically
water and oil mobilities in the context of petroleum sciences. These mobility
functions are often increasing and convex.

The assumption that the Buckley–Leverett function is S-shaped is prevalent.
This is likely due to the fact that an S-shaped function is used as the only
example in the principal work by Buckley and Leverett [1], and this assumption
is repeated in many papers thereafter. This assumption is no longer critical
in the case of the Buckley–Leverett equation, since the Riemann problem for it
can be solved analytically for any function $f$ by the convex hull
construction given by Oleinik (see [2, 3]). Nonetheless, it is still often
important in more general conservation systems that include more phases or
components, or have additional parameters such as temperature (see [4, 5, 6,
7, 8, 9]). However, there is no comprehensive research on when $f$ is actually
S-shaped. The prevalent conjecture among engineers is that convex mobilities
result in an S-shaped fractional flow function. Some mathematicians hold
similar expectations. The only paper known to the author (and the one that
inspired this work) investigating sufficient conditions for the S-shaped
function is the paper by Castañeda [10]. That paper proves that when relative
phase mobilities are convex power functions, the resultant Buckley–Leverett
function is S-shaped. It also states that the author could not find a
counterexample to the convex conjecture. Also noteworthy is [6, Claim 17]. It
does not give any conditions for when $f$ is S-shaped, but instead allows us
to circumvent the question altogether and find the solution to the Riemann
problem regardless, but only when the initial discontinuity connects pure or
almost pure states ($s=0$ and $s=1$).

In this paper, we present a counterexample where convex relative phase
mobilities produce a fractional flow function that has more than one
inflection point. Furthermore, we provide sufficient conditions for the
S-shaped Buckley–Leverett function. The paper has the following structure:
Section 2 defines the class of convex mobilities and proves the theorem
asserting that mobilities from that class always give an S-shaped fractional
flow function. Additionally, it proves the proposed class of convex functions
is closed under multiplication. Section 3 presents the counterexample of two
functions outside the previously defined class that produce a fractional flow
function that is not S-shaped. Appendix A contains the graphs illustrating the
counterexamples provided in this paper. Appendix B applies the proposed
conditions to some known relative mobility models.

##  2 Sufficient conditions for the S-shaped function

######  Definition 1.

Let $\mathcal{M}$ be a set of functions $m\in\mathcal{C}^{2}[0,1]$ such that

  * (C1)

$m(s)>0$ for $s>0$, $m(0)=0$;

  * (C2)

$m^{\prime}(s)>0$ for $s>0$, $m^{\prime}(0)=0$;

  * (C3)

$m^{\prime\prime}(s)>0$ for $s>0$;

  * (C4)

$\dfrac{m^{\prime\prime}}{m^{\prime}}$ is a decreasing function on $(0,1)$.

######  Remark 1.

Any power function $m(s)=As^{a}$ with $A>0$ and power $a>1$ is in
$\mathcal{M}$, since $\dfrac{m^{\prime\prime}}{m^{\prime}}=\dfrac{a-1}{s}$ is
decreasing. Thus Theorem 1 below covers the result of [10, Theorem 409].

######  Lemma 1.

Let $m\in\mathcal{M}$. Then $\dfrac{m^{\prime}}{m}$ is also a decreasing
function. Therefore, for all $m\in\mathcal{M}$ the following variation of (C4)
holds:

  * (C4*)

$\dfrac{m^{\prime}}{m}$ and $\dfrac{m^{\prime\prime}}{m^{\prime}}$ are
decreasing functions on $(0,1)$.

###### Proof.

To prove $\dfrac{m^{\prime}}{m}$ is a decreasing function we need to
demonstrate

$\left(\dfrac{m^{\prime}}{m}\right)^{\prime}=\dfrac{m^{\prime\prime}m-m^{\prime
2}}{m^{2}}<0,$

which, considering (C1)–(C3), is equivalent to

$\dfrac{m^{\prime}}{m}>\dfrac{m^{\prime\prime}}{m^{\prime}},$

which, considering (C4), follows from Cauchy’s Mean Value Theorem:

$\dfrac{m^{\prime}(x)}{m(x)}=\dfrac{m^{\prime}(x)-m^{\prime}(0)}{m(x)-m(0)}=\dfrac{m^{\prime\prime}(\widetilde{x})}{m^{\prime}(\widetilde{x})}>\dfrac{m^{\prime\prime}(x)}{m^{\prime}(x)}$

holds for all $x\in(0,1)$ and certain $\widetilde{x}\in(0,x)$. ∎

######  Remark 2.

Though we require only $\mathcal{C}^{2}$ smoothness from our functions, in the
proof below we will operate the third derivative as if it is regular, but only
in the context of examining the local monotonicity of the second derivative.
Any such argument could be easily modified to avoid the mention of the third
derivative, but that would make the proof needlessly cumbersome.

######  Theorem 1.

Let $m_{a}$ and $m_{b}$ be two mobility functions from the class
$\mathcal{M}$. Then the fractional flow function
$f(s)=\dfrac{m_{a}(s)}{m_{a}(s)+m_{b}(1-s)}$ is S-shaped, that is, there
exists a unique inflection point $s^{*}\in(0,1)$, such that
$f^{\prime\prime}(s^{*})=0$.

###### Proof.

We note that $(m_{b}(1-s))^{\prime}=-m^{\prime}_{b}(1-s)$, thus $m_{b}$
changes sign with every derivative. Keeping that in mind, we omit the
variables $s$ and $1-s$ in the notation hereafter, implying that $m_{b}$ and
its derivatives are applied to the variable $1-s$.

Denote $m=m_{a}+m_{b}$. We solve the equation

$f^{\prime\prime}=\dfrac{(m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b})m-2m^{\prime}(m^{\prime}_{a}m_{b}+m_{a}m^{\prime}_{b})}{m^{3}}=0,$
(1)

and aim to demonstrate that it has a unique solution on $(0,1)$. Note
immediately that if $m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}$ and
$-m^{\prime}$ have the same sign, then $f^{\prime\prime}$ has it too. Thus,
any solution of (1) must satisfy

$(m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b})m^{\prime}>0\quad\text{or}\quad
m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}=m^{\prime}=0.$ (2)

Note also that $m^{\prime}$ is increasing due to (C3), since
$m^{\prime\prime}=m^{\prime\prime}_{a}+m^{\prime\prime}_{b}>0$, and it changes
sign exactly one time from negative to positive. Denote by $s_{1}$ the sign
change point:

$m^{\prime}<0,\quad s<s_{1};\qquad m^{\prime}>0,\quad s>s_{1}.$

Similarly, due to (C4*) we deduce that
$\dfrac{m_{a}^{\prime\prime}}{m_{a}}=\dfrac{m_{a}^{\prime\prime}}{m^{\prime}_{a}}\dfrac{m_{a}^{\prime}}{m_{a}}$
is decreasing and, keeping in mind the difference in the variable,
$\dfrac{m_{b}^{\prime\prime}}{m_{b}}=\dfrac{m_{b}^{\prime\prime}}{m^{\prime}_{b}}\dfrac{m_{b}^{\prime}}{m_{b}}$
is increasing. Thus,
$\dfrac{m_{a}^{\prime\prime}}{m_{a}}-\dfrac{m^{\prime\prime}_{b}}{m_{b}}$ is a
decreasing function and has a single sign change from positive to negative.
Denote the sign change point $s_{2}$ and note that

$m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}>0,\quad s<s_{2};\qquad
m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}<0,\quad s>s_{2}.$

Due to the restriction (2), we know that any solution of (1) must be between
$s_{1}$ and $s_{2}$. If $s_{1}=s_{2}$, then $s^{*}=s_{1}=s_{2}$ is the unique
solution of (1), and the theorem is proved. Otherwise, we consider separately
the cases $s_{1}<s_{2}$ and $s_{1}>s_{2}$.

Case $s_{1}<s_{2}$. On $(s_{1},s_{2})$ we have

$m^{\prime}>0,\quad m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}>0.$

It is clear that $f^{\prime\prime}(s_{1})>0$ and $f^{\prime\prime}(s_{2})<0$,
thus the solution exists. In order to prove its uniqueness, we denote

$h=m_{a}^{\prime}m_{b}+m_{a}m^{\prime}_{b},$

keeping in mind that in the current case
$h^{\prime}=m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}>0$. Using this
new notation, we rewrite

$f^{\prime}=\dfrac{h}{m^{2}},\qquad
f^{\prime\prime}=\dfrac{h^{\prime}m-2m^{\prime}h}{m^{3}}.$ (3)

Note that

$\dfrac{h^{\prime}}{m_{a}^{\prime}m_{b}^{\prime}}=\dfrac{m_{a}^{\prime\prime}m_{b}-m_{a}m^{\prime\prime}_{b}}{m_{a}^{\prime}m_{b}^{\prime}}=\dfrac{m_{a}^{\prime\prime}}{m_{a}^{\prime}}\dfrac{m_{b}}{m_{b}^{\prime}}-\dfrac{m_{b}^{\prime\prime}}{m_{b}^{\prime}}\dfrac{m_{a}}{m_{a}^{\prime}}$

is decreasing due to (C4*), thus

$m_{a}^{\prime}m_{b}^{\prime}\left(\dfrac{h^{\prime}}{m_{a}^{\prime}m_{b}^{\prime}}\right)^{\prime}=h^{\prime\prime}-h^{\prime}\left[\dfrac{m_{a}^{\prime\prime}}{m_{a}^{\prime}}-\dfrac{m_{b}^{\prime\prime}}{m_{b}^{\prime}}\right]<0.$

Note also that

$\dfrac{m^{\prime\prime}}{m^{\prime}}+\dfrac{m^{\prime}}{m}>\dfrac{m^{\prime\prime}}{m^{\prime}}=\dfrac{m^{\prime\prime}_{a}+m^{\prime\prime}_{b}}{m^{\prime}_{a}-m^{\prime}_{b}}>\dfrac{m_{a}^{\prime\prime}}{m_{a}^{\prime}}>\dfrac{m_{a}^{\prime\prime}}{m_{a}^{\prime}}-\dfrac{m_{b}^{\prime\prime}}{m_{b}^{\prime}},$

thus combining these relations we obtain

$h^{\prime\prime}-h^{\prime}\left[\dfrac{m^{\prime\prime}}{m^{\prime}}+\dfrac{m^{\prime}}{m}\right]<0.$
(4)

Let $s=s^{*}$ be a solution of (1), that is, $f^{\prime\prime}(s^{*})=0$. Then
from (3) we have $h^{\prime}(s^{*})m(s^{*})=2m^{\prime}(s^{*})h(s^{*})$.
Therefore,

$f^{\prime\prime\prime}(s^{*})=\left.\dfrac{(h^{\prime}m^{2}-2mm^{\prime}h)^{\prime}}{m^{4}}\right|_{s=s^{*}}-\dfrac{4m^{\prime}(s^{*})}{m(s^{*})}f^{\prime\prime}(s^{*}).$

The second term is zero, and the first could be estimated using (4):

$\displaystyle\left.\dfrac{(h^{\prime}m^{2}-2mm^{\prime}h)^{\prime}}{m^{2}}\right|_{s=s^{*}}$
$\displaystyle={}h^{\prime\prime}(s^{*})-2\dfrac{m^{\prime}(s^{*})}{m(s^{*})}h(s^{*})\left[\dfrac{m^{\prime\prime}(s^{*})}{m^{\prime}(s^{*})}+\dfrac{m^{\prime}(s^{*})}{m(s^{*})}\right]$
$\displaystyle{}=h^{\prime\prime}(s^{*})-h^{\prime}(s^{*})\left[\dfrac{m^{\prime\prime}(s^{*})}{m^{\prime}(s^{*})}+\dfrac{m^{\prime}(s^{*})}{m(s^{*})}\right]<0.$

Therefore, $f^{\prime\prime\prime}(s^{*})<0$ and $f^{\prime\prime}$ changes
sign from positive to negative at $s^{*}$. There could only be one solution
with that property, so $s^{*}$ is unique.

Case $s_{1}>s_{2}$. In this case on $(s_{2},s_{1})$ we have

$m^{\prime}<0,\quad
h^{\prime}=m^{\prime\prime}_{a}m_{b}-m_{a}m^{\prime\prime}_{b}<0.$

Now $f^{\prime\prime}(s_{2})>0$ and $f^{\prime\prime}(s_{1})<0$, thus the
solution exists. The steps of the uniqueness proof are the same. We note that

$\dfrac{m^{\prime\prime}}{m^{\prime}}+\dfrac{m^{\prime}}{m}<\dfrac{m^{\prime\prime}}{m^{\prime}}=\dfrac{m^{\prime\prime}_{a}+m^{\prime\prime}_{b}}{m^{\prime}_{a}-m^{\prime}_{b}}<-\dfrac{m_{b}^{\prime\prime}}{m_{b}^{\prime}}<\dfrac{m_{a}^{\prime\prime}}{m_{a}^{\prime}}-\dfrac{m_{b}^{\prime\prime}}{m_{b}^{\prime}},$

therefore (4) still holds. Other than that, no modifications are required,
thus the theorem is proved.

∎

In practice, the following theorem is very helpful in verifying condition (C4)
for some common functions.

######  Theorem 2.

Let $m_{1}$ and $m_{2}$ be positive and increasing functions on $(0,1)$
satisfying (C4*). Then their product $m_{1}m_{2}$ also satisfies (C4*).

###### Proof.

In this proof, we will use the notation $i=1,2$. Note that since
$\dfrac{m_{i}^{\prime}}{m_{i}}$ and
$\dfrac{m_{i}^{\prime\prime}}{m_{i}^{\prime}}$ are decreasing, their product
$\dfrac{m_{i}^{\prime\prime}}{m_{i}}$ is also decreasing. Consider the
derivatives of these fractions and we obtain

$m_{i}^{\prime\prime}m_{i}-(m_{i}^{\prime})^{2}<0,\quad
m_{i}^{\prime\prime\prime}m_{i}^{\prime}-(m_{i}^{\prime\prime})^{2}<0,\quad
m_{i}^{\prime\prime\prime}m_{i}-m_{i}^{\prime\prime}m_{i}^{\prime}<0.$

It is easy to see that

$\left(\dfrac{(m_{1}m_{2})^{\prime}}{m_{1}m_{2}}\right)^{\prime}=(\ln(m_{1}m_{2}))^{\prime\prime}=(\ln
m_{1})^{\prime\prime}+(\ln
m_{2})^{\prime\prime}=\left(\dfrac{m_{1}^{\prime}}{m_{1}}\right)^{\prime}+\left(\dfrac{m_{2}^{\prime}}{m_{2}}\right)^{\prime}<0.$

Sadly, the same simple trick does not work for the second fraction. Instead,
we prove that $\dfrac{(m_{1}m_{2})^{\prime\prime}}{(m_{1}m_{2})^{\prime}}$ is
decreasing by expanding the derivatives and grouping some terms to achieve a
similar estimate:

$\displaystyle(m_{1}m_{2})^{\prime\prime\prime}$
$\displaystyle(m_{1}m_{2})^{\prime}-((m_{1}m_{2})^{\prime\prime})^{2}$
$\displaystyle{}=(m_{1}^{\prime\prime\prime}m_{2}+3m_{1}^{\prime\prime}m_{2}^{\prime}+3m_{1}^{\prime}m_{2}^{\prime\prime}+m_{1}m_{2}^{\prime\prime\prime})(m_{1}^{\prime}m_{2}+m_{1}m_{2}^{\prime})$
$\displaystyle{}-(m_{1}^{\prime\prime}m_{2}+2m_{1}^{\prime}m_{2}^{\prime}+m_{1}m_{2}^{\prime\prime})^{2}$
$\displaystyle{}=m_{2}^{2}(m_{1}^{\prime\prime\prime}m_{1}^{\prime}-(m_{1}^{\prime\prime})^{2})+m_{1}^{2}(m_{2}^{\prime\prime\prime}m_{2}^{\prime}-(m_{2}^{\prime\prime})^{2})$
$\displaystyle{}+m_{2}^{\prime}m_{2}(m_{1}^{\prime\prime\prime}m_{1}-m_{1}^{\prime\prime}m_{1}^{\prime})+m_{1}^{\prime}m_{1}(m_{2}^{\prime\prime\prime}m_{2}-m_{2}^{\prime\prime}m_{2}^{\prime})$
$\displaystyle{}+(m_{2}^{\prime})^{2}(m_{1}^{\prime\prime}m_{1}-(m_{1}^{\prime})^{2})+(m_{1}^{\prime})^{2}(m_{2}^{\prime\prime}m_{2}-(m_{2}^{\prime})^{2})$
$\displaystyle{}-2(m_{1}^{\prime\prime}m_{1}-(m_{1}^{\prime})^{2})(m_{2}^{\prime\prime}m_{2}-(m_{2}^{\prime})^{2})<0.$

∎

######  Corollary 1.

$\mathcal{M}$ is closed under multiplication.

##  3 Counterexample for the convex conjecture

The first counterexample we constructed goes as follows. Consider the phase
mobilities

$m_{a}(s)=m_{b}(s)=s^{1.1}e^{s^{10}}.$

It is easy to calculate the derivatives:

$m_{a}^{\prime}(s)=1.1s^{0.1}e^{s^{10}}+10s^{10.1}e^{s^{10}}>0,$
$m_{a}^{\prime\prime}(s)=0.11s^{-0.9}e^{s^{10}}+112s^{9.1}e^{s^{10}}+100s^{19.1}e^{s^{10}}>0,$

and it is clear that these mobilities admit (C1), (C2) and (C3). However,
function

$\dfrac{m_{a}^{\prime\prime}}{m_{a}}=0.11s^{-2}+112s^{8}+100s^{18}$

changes monotonicity, since

$\left(\dfrac{m_{a}^{\prime\prime}}{m_{a}}\right)^{\prime}=s^{-3}(1800s^{20}+896s^{10}-0.22)=0$

has a solution $s\approx 0.4355$, thus (C4) is not upheld. That leads to $f$
having $3$ inflection points: $s=0.5$ is an inflection point due to symmetry,
but it has the wrong monotonicity, that is, $f^{\prime\prime\prime}(0.5)>0$.
Thus there must exist two additional inflection points, one before $0.5$ and
one after. Though it is clear on the graph of $f^{\prime\prime}$ that it has
three zeroes, the graph of $f$ is less obvious, barely deviating from the
diagonal (see Fig.2 and Fig.2 in Appendix A). But the first counterexample
allowed us to find a family of similar functions with more pronounced graphs.
One of them is

$m_{a}(s)=m_{b}(s)=s^{1.1}(1+15s^{10}).$

See Fig.4 and Fig.4 in Appendix A for the corresponding plots. The principles
upon which these examples were constructed are generalized in the following
theorem.

######  Theorem 3.

Let $m_{a}=m_{b}$ be mobility function satisfying (C1)–(C3) from Definition 1.
Additionally, let

$\left.\left(\dfrac{m_{a}^{\prime\prime}}{m_{a}^{3}}\right)^{\prime}\right|_{s=0.5}>0.$
(5)

Then the corresponding fractional flow function has more than one inflection
point and therefore is not S-shaped.

###### Proof.

Note that due to symmetry, we have

$m^{\prime}(0.5)=h^{\prime}(0.5)=0.$

Therefore

$f^{\prime\prime}(0.5)=\left.\dfrac{h^{\prime}m-2m^{\prime}h}{m^{3}}\right|_{s=0.5}=0,$

thus, $s=0.5$ is an inflection point. However,

$\displaystyle f^{\prime\prime\prime}(0.5)$
$\displaystyle=\left.\left(\dfrac{h^{\prime}m-2m^{\prime}h}{m^{3}}\right)^{\prime}\right|_{s=0.5}=\left.\dfrac{h^{\prime\prime}m-2m^{\prime\prime}h}{m^{3}}\right|_{s=0.5}$
$\displaystyle{}=\left.\dfrac{m_{a}^{\prime\prime\prime}m_{a}^{2}-3m_{a}^{\prime\prime}m_{a}^{\prime}m_{a}}{2m_{a}^{3}}\right|_{s=0.5}=\dfrac{m_{a}^{2}}{2}\left.\left(\dfrac{m_{a}^{\prime\prime}}{m_{a}^{3}}\right)^{\prime}\right|_{s=0.5}>0,$

so $f^{\prime\prime}$ changes sign from negative to positive at $s=0.5$,
therefore it cannot be a unique inflection point and there must exist at least
two more inflection points, one before $0.5$ and one after. ∎

It is a fairly straightforward task to check that (5) holds for both
counterexamples provided above. It is also clear that (5) contradicts (C4).
But the class of functions satisfying neither (C4) nor (5) is vast, and it
leads to questions on the rigidity of (C4). Is it possible to construct a
wider class $\mathcal{M}$, for which Theorem 1 holds, by weakening the (C4)
restriction? We leave it an open problem for now. What is clear is that (5) is
not the only way to construct a counterexample, just the most direct one. It
is possible to construct mobilities that do not satisfy (5) but still lead to
additional inflection points. To give an example, functions
$m_{a}(s)=m_{b}(s)=s^{1.1}(1+15s^{30})$ result in
$f^{\prime\prime\prime}(0.5)<0$, but $f$ still has $5$ inflection points, as
clearly shown on Fig. 6 and Fig. 6.

## Appendix A

The graphs for the counterexample $m_{a}(s)=m_{b}(s)=s^{1.1}e^{s^{10}}$:

Figure 1: Function $f$.

Figure 2: $f^{\prime\prime}$ with $3$ zeroes.

The graphs for the counterexample $m_{a}(s)=m_{b}(s)=s^{1.1}(1+15s^{10})$:

Figure 3: Function $f$.

Figure 4: $f^{\prime\prime}$ with $3$ zeroes.

The graphs for the counterexample $m_{a}(s)=m_{b}(s)=s^{1.1}(1+15s^{30})$:

Figure 5: Function $f$.

Figure 6: $f^{\prime\prime}$ with $5$ zeroes.

## Appendix B

In this appendix, we check various known relative mobility models against the
conditions (C1)–(C4).

###  B.1 Modified Brooks and Corey model

The simplest and the most commonly used relative mobility model (see [11]) is
the power law model

$m_{a}(s)=As^{a},\quad m_{b}(s)=Bs^{b},$

where $A,B>0$, $a,b>1$. As we already noted in Remark 1, any power function
with power greater than $1$ satisfies (C1)–(C4), therefore
$m_{a},m_{b}\in\mathcal{M}$.

###  B.2 Brooks and Corey model

The original model proposed by Corey (see [12]) is

$m_{a}(s)=s^{4},\quad m_{b}(s)=s^{2}(1-(1-s)^{2}).$

Later, Brooks and Corey introduce a parameter to generalize that model (see
[13]). That resulted in the following functions:

$m_{a}(s)=s^{\frac{2+3\lambda}{\lambda}},\quad
m_{b}(s)=s^{2}\left(1-(1-s)^{\frac{2+\lambda}{\lambda}}\right),$

where $\lambda$ is the pore size distribution index. This was further
generalized in [14] to include an additional parameter:

$m_{a}(s)=s^{\eta+\frac{2+\lambda}{\lambda}},\quad
m_{b}(s)=s^{\eta}\left(1-(1-s)^{\frac{2+\lambda}{\lambda}}\right).$

In all variations, $m_{a}$ is a power function, and thus already considered
previously. To study $m_{b}$ we first analyze the expression in the brackets.

######  Lemma 2.

Function $n_{\alpha}(s)=1-(1-s)^{\alpha}$ on $(0,1)$ is positive, increasing
and satisfies (C4*) for all $\alpha>1$.

###### Proof.

$n^{\prime}_{\alpha}(s)=\alpha(1-s)^{\alpha-1}>0,\quad
n^{\prime\prime}_{\alpha}(s)=-\alpha(\alpha-1)(1-s)^{\alpha-2}<0.$

Therefore,

$n^{\prime\prime}_{\alpha}n_{\alpha}-(n^{\prime}_{\alpha})^{2}<0,$

so $n^{\prime}_{\alpha}/n_{\alpha}$ is decreasing and

$\dfrac{n^{\prime\prime}_{\alpha}}{n_{\alpha}}=\dfrac{1-\alpha}{1-s}$

is also a decreasing function. ∎

Therefore, due to Theorem 2 we obtain (C1), (C2) and (C4) for $m_{b}$ for all
$\eta>1$ and $\lambda>0$. The only condition left to check is (C3). Denote
$\alpha=\frac{2+\lambda}{\lambda}$.

$m^{\prime\prime}_{b}(s)=\eta(\eta-1)s^{\eta-2}\left(1-(1-s)^{\alpha}\right)+2\eta\alpha
s^{\eta-1}(1-s)^{\alpha-1}-\alpha(\alpha-1)s^{\eta}(1-s)^{\alpha-2}.$

It is clear that for $1<\alpha<2$ or $\lambda>2$ the last term blows up near
$s=1$, thus (C3) is broken. Otherwise, we can prove $m_{b}$ is convex.

######  Lemma 3.

Let $\alpha,\eta\geqslant 2$. Then
$m_{b}(s)=s^{\eta}\left(1-(1-s)^{\alpha}\right)$ is convex on $(0,1)$.

###### Proof.

We rewrite

$m^{\prime\prime}_{b}(s)=s^{\eta-2}\Big{[}\eta(\eta-1)-P(s)(1-s)^{\alpha-2}\Big{]},$
(6)

where

$P(s)=\eta(\eta-1)-2\eta\gamma
s+\gamma(\gamma+1)s^{2},\qquad\gamma=\eta+\alpha-1.$

It is clear that $m^{\prime\prime}_{b}$ is positive near $0$ and $1$. It is
also easy to see that

$(\eta(\eta-1)-P(s)(1-s)^{\alpha-2})^{\prime}=(1-s)^{\alpha-3}((\alpha-2)P(s)-(1-s)P^{\prime}(s)),$

and

$(\alpha-2)P(s)-(1-s)P^{\prime}(s)=\alpha\left(\gamma(\gamma+1)s^{2}-2\gamma(\eta+1)s+\eta(\eta+1)\right)=0$
(7)

has at most two zeroes on $(0,1)$. Therefore, the expression in the brackets
in (6) has at most two extremums on $(0,1)$, and if we show them to be
positive, the proof will be concluded. Let $z\in(0,1)$ be a root of (7). Note
that (7) gives us

$P(z)=2\gamma z-2\eta.$

Using this and Bernoulli’s inequality, we estimate

$\displaystyle\eta(\eta-1)(1-z)^{2-\alpha}-P(z)$
$\displaystyle\geqslant\eta(\eta-1)+\eta(\eta-1)(\alpha-2)z-2\gamma z+2\eta$
$\displaystyle{}=(\eta-2z)(\eta+1)+(\alpha-2)(\eta-2)(\eta+1)z>0.$

∎

Therefore, $m_{b}\in\mathcal{M}$ for all $\alpha,\eta\geqslant 2$ (or
equivalently $0<\lambda\leqslant 2,\eta\geqslant 2$).

###  B.3 Chierici model

Chierici (see [15]) proposed an exponential law for the relative mobility
functions:

$m_{a}(s)=A\exp\left[-B\left(\dfrac{s}{1-s}\right)^{-M}\right].$

This expression is often not convex, so we are going to provide an example of
Chierici functions satisfying our conditions. Let $M=1$, $B>2$. Then

$m_{a}(s)=A\exp\left[-B\dfrac{1-s}{s}\right],\quad
m_{a}^{\prime}(s)=\dfrac{AB}{s^{2}}\exp\left[-B\dfrac{1-s}{s}\right]>0,$
$m_{a}^{\prime\prime}(s)=\dfrac{AB^{2}-2ABs}{s^{4}}\exp\left[-B\dfrac{1-s}{s}\right]>0,$
$\left(\dfrac{m^{\prime}_{a}}{m_{a}}\right)^{\prime}=-\dfrac{2B}{s^{3}}<0,\quad\left(\dfrac{m^{\prime\prime}_{a}}{m^{\prime}_{a}}\right)^{\prime}=\left(\dfrac{B-2s}{s^{2}}\right)^{\prime}=\dfrac{2s-2B}{s^{3}}<0.$

Therefore $m_{a}\in\mathcal{M}$ for $M=1$ and all $B>2$.

## Acknowledgements

The author thanks F. Bakharev, A. Enin, A. Nazarov and Yu. Petrova for the
fruitful discussions of the problem.

The work is supported by the Ministry of Science and Higher Education of the
Russian Federation (agreement no. 075-15-2022-287).

## References

  * [1] Buckley, S. E. and Leverett, M., 1942. Mechanism of fluid displacement in sands. Transactions of the AIME, 146(01), pp. 107-116.
  * [2] Oleinik, O. A., 1957. Discontinuous solutions of non-linear differential equations. Uspekhi Matematicheskikh Nauk, 12(3)(75), pp. 3-73 (in Russian). English translation in American Mathematical Society Translations, 26(2), 1963, pp. 95-172.
  * [3] Gelfand, I. M., 1959. Some problems in the theory of quasilinear equations. Uspekhi Matematicheskikh Nauk, 14(2), pp. 87-158 (in Russian). English translation in Transactions of the American Mathematical Society, 29(2), 1963, pp. 295-381.
  * [4] Johansen, T. and Winther, R., 1988. The solution of the Riemann problem for a hyperbolic system of conservation laws modeling polymer flooding. SIAM journal on mathematical analysis, 19(3), pp. 541-566.
  * [5] Bakharev, F., Enin, A., Petrova, Y. and Rastegaev, N., 2021. Impact of dissipation ratio on vanishing viscosity solutions of the Riemann problem for chemical flooding model. arXiv preprint arXiv:2111.15001.
  * [6] Castañeda, P., Furtado, F. and Marchesin, D., 2013. The convex permeability three-phase flow in reservoirs. IMPA Preprint Série E-2258, pp. 1-34.
  * [7] Castañeda, P., Abreu, E., Furtado, F. and Marchesin, D., 2016. On a universal structure for immiscible three-phase flow in virgin reservoirs. Computational Geosciences, 20, pp. 171-185.
  * [8] Tang, J., Castañeda, P., Marchesin, D. and Rossen, W. R., 2019. Three-Phase Fractional-Flow Theory of Foam-Oil Displacement in Porous Media With Multiple Steady States. Water Resources Research, 55(12), pp. 10319-10339.
  * [9] Wahanik, H., Eftekhari, A. A., Bruining, J., Marchesin, D. and Wolf, K. H., 2010, October. Analytical solutions for mixed CO2-water injection in geothermal reservoirs. In Canadian Unconventional Resources and International Petroleum Conference. OnePetro.
  * [10] Castañeda, P., 2016. Dogma: S-shaped. The Mathematical Intelligencer, 38, pp. 10-13.
  * [11] Lake, L.W., 1989. Enhanced oil recovery, Chapter 3.
  * [12] Corey, A. T., 1954. The interrelation between gas and oil relative permeabilities. Producers Monthly 19 (November), pp. 38-41.
  * [13] Brooks, R. H. and Corey, A. T., 1964. Hydraulic Properties of Porous Media. Hydrology Papers, No. 3, Colorado State U., Fort Collins, Colorado.
  * [14] Chen, D., Pan, Z., Liu, J. and Connell, L. D., 2013. An improved relative permeability model for coal reservoirs. International Journal of Coal Geology, 109, pp. 45-57.
  * [15] Chierici, G. L., 1984. Novel relations for drainage and imbibition relative permeabilities. Society of Petroleum Engineers Journal, 24(03), pp. 275-276.