  Dense subgraph discovery is a fundamental problem in graph mining with a wide
range of applications \cite{gionis2015dense}. Despite a large number of
applications ranging from computational neuroscience to social network
analysis, that take as input a {\em dual} graph, namely a pair of graphs on the
same set of nodes, dense subgraph discovery methods focus on a single graph
input with few notable exceptions
\cite{semertzidis2019finding,charikar2018finding,reinthal2016finding,jethava2015finding}.
In this work, we focus the following problem: given a pair of graphs $G,H$ on
the same set of nodes $V$, how do we find a subset of nodes $S \subseteq V$
that induces a well-connected subgraph in $G$ and a dense subgraph in $H$?
  Our formulation generalizes previous research on dual graphs
\cite{Wu+15,WuZLFJZ16,Cui2018}, by enabling the {\em control} of the
connectivity constraint on $G$. We propose a novel mathematical formulation
based on $k$-edge connectivity, and prove that it is solvable exactly in
polynomial time. We compare our method to state-of-the-art competitors; we find
empirically that ranging the connectivity constraint enables the practitioner
to obtain insightful information that is otherwise inaccessible. Finally, we
show that our proposed mining tool can be used to better understand how users
interact on Twitter, and connectivity aspects of human brain networks with and
without Autism Spectrum Disorder (ASD).
