Tikz Positioning on \draw not working

It is enough to use the Line-To operation (< coordinate > -- < coordinate >) instead of the To-Path operation (< coordinate > to < coordinate >):

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{shadows,arrows,calc,backgrounds,fit,shapes,snakes,shapes.multipart,decorations.pathreplacing,shapes.misc,patterns,positioning}
\usepackage{pgfplots}

\begin{document}
\begin{tikzpicture}[node distance=4mm]
    \node[align=center] (rrhp) { Robust Relational \\ Hyperproperty Preservation};
    \node[align=center, below = of rrhp.south east] (r2rsp) { Robust 2-Relational \\ Safety Preservation};
    \node[align=center, below = of r2rsp.south, yshift=-3em] (fac2) { Fully Abstract\\ Compilation };

    \draw[-] (rrhp.south) to (r2rsp.north west);
    \draw[-, dotted] (r2rsp.south) -- (fac2.north) node [right,align=left,pos=.5] { + determinacy } ;  

\end{tikzpicture}
\end{document}

Second solution: The syntax of the To-Path operation you used does not match that of the manual (p 157 of 3.0.1.a manual)

 \path ... to[options] < nodes > < coordinate or cycle > ...;

The code is

\documentclass{article}

\usepackage{tikz}
\usetikzlibrary{shadows,arrows,calc,backgrounds,fit,shapes,snakes,shapes.multipart,decorations.pathreplacing,shapes.misc,patterns,positioning}
\usepackage{pgfplots}

\begin{document}
\begin{tikzpicture}[node distance=4mm]
    \node[align=center] (rrhp) { Robust Relational \\ Hyperproperty Preservation};
    \node[align=center, below = of rrhp.south east] (r2rsp) { Robust 2-Relational \\ Safety Preservation};
    \node[align=center, below = of r2rsp.south, yshift=-3em] (fac2) { Fully Abstract\\ Compilation };

    \draw[-] (rrhp.south) to (r2rsp.north west);
    \draw[-, dotted] (r2rsp.south) to  node [right,align=left,pos=.5] { + determinacy } (fac2.north);  

\end{tikzpicture}
\end{document}

i would use quotes library and with it slightly simplify the picture code:

\documentclass{article}
\usepackage{pgfplots} % <--- it load `tikz`
\usetikzlibrary{arrows,
                backgrounds,
                decorations.pathreplacing,
                calc,
                fit,
                patterns, positioning,
                quotes, % <--- added
                shadows, shapes, shapes.multipart, shapes.misc, snakes
                }

\begin{document}
\begin{tikzpicture}[node distance=4mm, align=center]
    \node (rrhp) { Robust Relational \\ Hyperproperty Preservation};
    \node [below=of rrhp.south east] (r2rsp) { Robust 2-Relational \\ Safety Preservation};
    \node[below=12mm of r2rsp] (fac2) { Fully Abstract\\ Compilation };
%
    \draw (rrhp.south) -- (r2rsp.north west);          % <--- changed
    \draw[dotted] (r2rsp) to ["+ determinacy"] (fac2); % <--- changed
\end{tikzpicture}
\end{document}