\documentclass[utf8x,xcolor=usenames,dvipsnames,svgnames]{beamer}

\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
\usepackage{graphicx,hyperref,url}
\usepackage{amsmath,amssymb}
\usepackage{ru}
\usepackage{pgfplots}
\setbeamercovered{transparent}
\usetikzlibrary{shapes}

\graphicspath{{./}{../paper/}}

\newcommand{\sectionWithTitle}[1]{\sectionWithTitleN{#1}{#1}}

\pgfplotscreateplotcyclelist{mystyle}{%
  mark=,RUBlue,densely dashed\\%
  mark=,RURed\\%
}

\newcommand{\trans}{^\text{T}}

\newcommand{\minput}[1]{\input{#1}}
% \newcommand{\minput}[1]{\addplot+[mark=] coordinates{(0,0)};} % DISABLE for speed reasons


\newcommand{\weight}[3][]{E#1(#2,#3)}
\newcommand{\degree}[1]{s_{#1}}
\newcommand{\vol}[1]{v_{#1}}
\newcommand{\within}[1]{w_{#1}}
\newcommand{\exit}[1]{\vol{#1} - \within{#1}}
\newcommand{\Obj}{Q}
\newcommand{\objpart}{q}
\newcommand{\disjointunion}{\uplus}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\RRnonneg}{\RR_{\ge 0}}
\newcommand{\condense}[2]{#1/\mathord{\sim}_#2}
\DeclareMathOperator{\argmax}{argmax}
\newcommand{\ifrac}[2]{#1/(#2)}
\newcommand{\qmod}{\Obj_\text{modularity}}
\newcommand{\qcoco}{\Obj_\text{coco}}
\newcommand{\qfixed}[1][M]{\Obj_\text{$#1$-fixed}}
\newcommand{\qext}[2]{\Obj_\text{$#1$,$#2$}}
\newcommand{\vamount}{\gamma}
\newcommand{\maxfrac}[1]{f_{#1}}
\newcommand{\indicator}{\mathbf{1}}
\newcommand{\agree}{a}


\tikzset{
  node/.style={circle,draw,inner sep=0,minimum size=5mm},
  snode/.style={circle,draw,inner sep=0,minimum size=3mm},
  lbl/.style={fill=white,inner sep=0.2mm,minimum size=1mm},
}

% % for printing

% =============================================================================

\title[Axioms for graph clustering objective functions]{Axioms for graph clustering objective functions}
\newcommand{\insertlongtitle}{%
  Axioms for graph clustering objective functions%
}
\author{Twan van Laarhoven}

\newcommand{\insertlongauthor}{Twan van Laarhoven}

\institute[Radboud University Nijmegen]{%
  Institute for Computing and Information Sciences\\% -- Intelligent Systems \\
  Radboud University Nijmegen, The Netherlands}

\date[2013-06-28]{28th June 2013}

% =============================================================================
\begin{document}

\begin{frame}%[plain]
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
\end{frame}

% =============================================================================
\section{Introduction}
% \begin{frame}
%   \frametitle{Outline}
%   \tableofcontents[currentsection]
% \end{frame}
\subsection{}

\begin{frame}
  \frametitle{The motivation}
%   \begin{theorem}[Kleinberg 2002]
%     There is no clustering function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
%   \begin{theorem}[Ackerman, Ben-David 2008]
%     There is a clustering quality function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
  \begin{itemize}
    \item There is no strict definition of clustering.
    \item Can we formalize our intuition?
    \item Previous work is about distance based clustering (hierarchical clustering, K-means, etc.)
    \item What about graphs?
  \end{itemize}
\end{frame}
% 
% \begin{frame}
%   \frametitle{Related work}
%   \begin{theorem}[Kleinberg 2002]
%     There is no clustering function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
%   \begin{theorem}[Ackerman, Ben-David 2008]
%     There is a clustering quality function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
% \end{frame}

\begin{frame}
  \frametitle{The setting}
  \begin{definition}[Graph]
    A symmetric weighted \emph{graph} is a pair $(V,E)$ of
    \begin{itemize}
      \item a finite set $V$ of \emph{nodes}, and
      \item a function $E : V \times V \to \RRnonneg$ of \emph{edge weights},
    \end{itemize}
    such that $E(i,j) = E(j,i)$ for all $i,j \in V$.%
  \end{definition}
  \begin{itemize}
    \item Larger weight = stronger connection.
    \item We allow self loops.
  \end{itemize}
\end{frame}
\begin{frame}
  \frametitle{The setting (cont.)}
  \begin{definition}[Clustering]
    A \emph{clustering} $C$ of a graph $G=(V,E)$ is a {partition} of its nodes.
    %That is, $\bigcup C = V$ and for all $c_1,c_2 \in C$, $c_1 \cap c_2 \neq \emptyset$ if and only if $c_1 = c_2$.
  \end{definition}
  \begin{definition}[Clustering function]
    A \emph{graph clustering function} $f$ is a function from graphs $G$ to clusterings of $G$.
  \end{definition}
  \begin{definition}[Objective function]
    A \emph{graph clustering objective function} $\Obj$ is a function from graphs $G$ and clusterings of $G$ to $\RR$.
  \end{definition}
  \begin{itemize}
    \item Larger objective value = better.
  \end{itemize}
\end{frame}

% =============================================================================
\section{Axioms}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{The form of axioms}
  \begin{block}{Things that define clusterings}
    \begin{tabular}{lll}
      & Form & Notation \\
      \cline{2-3}
      1 & Clustering function & $f(G) = \argmax_C Q(G,C)$   \\
      2 & Objective function  & $Q(G,C)$  \\
      3 & Objective relation  & $Q(G,C) \ge Q(G,D)$ or $C \ge_{G} D$ \\
    \end{tabular}
  \end{block}
%   \begin{example}[Scale invariance]
%     \begin{tabular}{lp{0.9\textwidth}}
%       1 & {$f(G) = f(\alpha G)$.}  \\
%       2 & {$\Obj(G,C) = \Obj(\alpha G,C)$.} \\
%       3 & if $\Obj(G,C) \ge \Obj(G,D)$ then $\Obj(\alpha G,C) \ge \Obj(\alpha G,D)$. \\
%        % & (or: if $C \ge_{G} D$ then $C \ge_{\alpha G} D$.) \\
%     \end{tabular}\\[2mm]
%     (for all $\alpha > 0$, all graphs $G$, all clustering $C,D$ of $G$.)
%   \end{example}
\end{frame}

\begin{frame}
  \frametitle{Basic axioms}
  \begin{block}{Axiom 1: Scale invariance (\only<1>{first}\only<2-3>{second}\only<4>{third} form)}
   \begin{overlayarea}{\textwidth}{2.5cm}%
    A graph clustering objective function $\Obj$ is \emph{scale invariant} if
    \begin{itemize}
      \item for all graphs $G=(V,E)$,
      \item all constants $\alpha > 0$,
      \only<2-3>{\item all clusterings $C$ of $G$,}
      \only<4>{\item all clusterings $C_1,C_2$ of $G$,}
    \end{itemize}
    \only<1>{ $f(G) = f(\alpha G)$. }%
    \only<2>{ $\Obj(G,C) = \Obj(\alpha G,C)$. }%
    \only<3>{ $\Obj(G,C) = \alpha \Obj(\alpha G,C)$ ??? }%
    \only<4>{ $\Obj(G,C_1) \ge \Obj(G,C_2)$ if and only if $\Obj(\alpha G,C_1) \ge \Obj(\alpha G,C_2)$. }%
   \end{overlayarea}
    %\ \\[2mm]
    \vspace*{2mm}
    (where $\alpha G=(V,(i,j) \mapsto \alpha E(i,j))$.)
    % is a graph with edge weights scaled by a factor $\alpha$.
  \end{block}
  \begin{example}%
   \begin{overlayarea}{\textwidth}{2.0cm}%
    \only<4>{
     \vspace*{-0.5cm}
     \begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,line width=0.6pt]
        \node[snode,fill=RURed!40] (a) at (0,0.2) {};
        \node[snode,fill=RURed!40] (b) at (1.3,0.7) {};
        \node[snode,fill=RURed!40] (c) at (0.9,-0.8) {};
        \draw[line width=0.8*0.8pt] (a) to (b);
        \draw[line width=0.8*1.6pt] (a) to (c);
        \draw[line width=0.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
      \ge
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,line width=0.6pt]
        \node[snode,fill=DarkGreen!40] (a) at (0,0.2) {};
        \node[snode,fill=RUBlue!40] (b) at (1.3,0.7) {};
        \node[snode,fill=purple!40] (c) at (0.9,-0.8) {};
        \draw[line width=0.8*0.8pt] (a) to (b);
        \draw[line width=0.8*1.6pt] (a) to (c);
        \draw[line width=0.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
      \hfill\Longleftrightarrow\hfill
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,line width=0.6pt]
        \node[snode,fill=RURed!40] (a) at (0,0.2) {};
        \node[snode,fill=RURed!40] (b) at (1.3,0.7) {};
        \node[snode,fill=RURed!40] (c) at (0.9,-0.8) {};
        \draw[line width=1.8*0.8pt] (a) to (b);
        \draw[line width=1.8*1.6pt] (a) to (c);
        \draw[line width=1.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
      \ge
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,line width=0.6pt]
        \node[snode,fill=DarkGreen!40] (a) at (0,0.2) {};
        \node[snode,fill=RUBlue!40] (b) at (1.3,0.7) {};
        \node[snode,fill=purple!40] (c) at (0.9,-0.8) {};
        \draw[line width=1.8*0.8pt] (a) to (b);
        \draw[line width=1.8*1.6pt] (a) to (c);
        \draw[line width=1.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
    \end{equation*}}%
    \only<2-3>{\begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = \visible<3>{\alpha}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=2*0.8pt] (a) to (b);
        \draw[line width=2*1.6pt] (a) to (c);
        \draw[line width=2*1.6pt] (b) to (c);
        \draw[line width=2*0.8pt] (d) to (e);
        \draw[line width=2*0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}}%
    \vspace*{-5mm}
    \only<1>{\begin{equation*}
      f\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node] (a) at (0,0.2) {a};
        \node[node] (b) at (1.3,0.7) {b};
        \node[node] (c) at (0.9,-0.8) {c};
        \node[node] (e) at (2.7,-0.7) {e};
        \node[node] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = 
      f\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node] (a) at (0,0.2) {a};
        \node[node] (b) at (1.3,0.7) {b};
        \node[node] (c) at (0.9,-0.8) {c};
        \node[node] (e) at (2.7,-0.7) {e};
        \node[node] (d) at (3,0.7) {d};
        \draw[line width=2*0.8pt] (a) to (b);
        \draw[line width=2*1.6pt] (a) to (c);
        \draw[line width=2*1.6pt] (b) to (c);
        \draw[line width=2*0.8pt] (d) to (e);
        \draw[line width=2*0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = 
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=2*0.8pt] (a) to (b);
        \draw[line width=2*1.6pt] (a) to (c);
        \draw[line width=2*1.6pt] (b) to (c);
        \draw[line width=2*0.8pt] (d) to (e);
        \draw[line width=2*0.4pt] (c) to (e);
      \end{tikzpicture}%
    \end{equation*}}
   \end{overlayarea}
  \end{example}
\end{frame}

\begin{frame}
  \frametitle{Basic axioms}
  \begin{block}{Axiom 2: permutation invariance}
    A graph clustering objective function $\Obj$ is \emph{permutation invariant} if 
    \begin{itemize}
    \item for all graphs $G=(V,E)$ and
    \item all isomorphisms $f : V \to V'$,
    \end{itemize}
    it is the case that {$\Obj(G,C) = \Obj(f(G),f(C))$}.\\[2mm]
    (where $f$ is extended to graphs and clusterings in the obvious way.)
    %Where $f$ is extended to graphs and clusterings by
    %$f(C) = \{\{f(i)\mid i \in c\} \mid c\in C\}$ and
    %$f((V,E)) = (V',(i,j)\mapsto E(f^{-1}(i),f^{-1}(j)))$.
  \end{block}
  \begin{example}
    \begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[] (a) to (b);
        \draw[ultra thick] (a) to (c);
        \draw[] (b) to (c);
        \draw[ultra thick] (d) to (e);
        \draw[] (c) to (e);
      \end{tikzpicture}
      \right)
      = 
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=teal!40] (a) at (0.1,0.2) {z};
        \node[node,fill=teal!40] (b) at (-0.9,-0.8) {v};
        \node[node,fill=teal!40] (c) at (-1.3,0.7) {y};
        \node[node,fill=purple!40] (e) at (-2.8,0.8) {x};
        \node[node,fill=purple!40] (d) at (-2.7,-0.8) {u};
        \draw[] (a) to (b);
        \draw[ultra thick] (a) to (c);
        \draw[] (b) to (c);
        \draw[ultra thick] (d) to (e);
        \draw[] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}
  \end{example}
\end{frame}

\begin{frame}
  \frametitle{Basic axioms}
  \begin{block}{Axiom 3: Richness}
    A graph clustering objective function $\Obj$ is \emph{rich} if
    \begin{itemize}
      \item for all sets $V$ and
      \item all partitions $C^*$ of $V$,
    \end{itemize}
    there is
    \begin{itemize}
      \item a graph $G=(V,E)$
      \item such that $C^*$ is the optimal clustering of $G$.
    \end{itemize}
%     \emph{for all} sets $V$ and all \emph{partitions} $C^*$ of $V$,
%     \emph{there is a graph} $G=(V,E)$ such that $C^*$ is the optimal clustering of $V$,
%      i.e. $\argmax_{C} \Obj(G,C) = C^*$.
  \end{block}
%   \begin{example}
%     
%   \end{example}
  Intuition:
  \begin{itemize}
    %\item For every clustering there is a graph.
    %\item So no trivial objective functions.
    \item No trivial objective functions.
    \item No fixed number of clusters.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Basic axioms}
  \begin{definition}[Consistent improvement]
    Let
    \begin{itemize}
    \item $G=(V,E)$ and $G'=(V,E')$ be graphs, and
    \item $C$ be a clustering of $G$ and $G'$.
    \end{itemize}
    Then \emph{$G'$ is a $C$-consistent improvement of $G$} if
    \begin{itemize}
    \item $\weight[']{i}{j} \ge \weight{i}{j}$ for all $i \sim_C j$ and
    \item $\weight[']{i}{j} \le \weight{i}{j}$ for all $i \not\sim_C j$.
    \end{itemize}
  \end{definition}
  Intuition:
  \begin{itemize}
    \item Consistent improvements make a clustering fit better.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Basic axioms}
  \begin{block}{Axiom 4: Monotonicity}
    A graph clustering objective function $\Obj$ is \emph{monotonic} if
    \begin{itemize}
    \item for all graphs $G$,
    \item all clusterings $C$ of $G$ and
    \item all $C$-consistent improvements $G'$ of $G$
    \end{itemize}
    it is the case that
    $\Obj(G',C) \ge \Obj(G,C)$.
  \end{block}
  \begin{example}
    \begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=1.8pt] (a) to (b);
        \draw[line width=1.8pt] (a) to (c);
        \draw[] (b) to (c);
        \draw[ultra thick] (d) to (e);
        \draw[line width=0.5pt] (c) to (e);
      \end{tikzpicture}
      \right)
      \ge
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.6
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[] (a) to (b);
        \draw[very thick] (a) to (c);
        \draw[] (b) to (c);
        \draw[very thick] (d) to (e);
        \draw[line width=1.8pt] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}
  \end{example}
\end{frame}

%--------------------

%\subsection{Locality}
\newcommand<>{\raisebox}[2]{%
 \alt#3\beameroriginal{\raisebox{#1}{#2}}{#2}%
}
\begin{frame}
  \frametitle{Local changes}
  \begin{definition}[agreement]
    Let
    \begin{itemize}
      \item $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be two graphs and
      \item $V_\agree \subseteq V_1 \cap V_2$.
    \end{itemize}
    The graphs \emph{agree on $V_\agree$} if
    {$E_1(i,j) = E_2(i,j)$} for all $i,j \in V_\agree$.
  \end{definition}
  \pause
  \begin{definition}[agreement on neighborhood]
    The graphs also \emph{agree on the neighborhood of $V_\agree$} if
    \begin{tabular}{@{\quad}l@{ }l}
    $E_1(i,j) = E_2(i,j)$ &for all $i \in V_\agree$, $j \in V_1 \cap V_2$, and \\
    $E_1(i,j) = 0$ &for all $i \in V_\agree$, $j \in V_1 \setminus V_2$, and \\
    $E_2(i,j) = 0$ &for all $i \in V_\agree$, $j \in V_2 \setminus V_1$.
    \end{tabular}
% 
%     if $E_1(i,j) = E_2(i,j)$ whenever $i \in V_\agree$ \emph{or} $j \in V_\agree$. Here we take $E_1(i,j)=0$ and $E_1(i,j)=0$ for nodes not in the respective graphs.
%      In particular this means that there can be no edges from nodes in $V_\agree$ to nodes not in $V_1 \cap V_2$
  \end{definition}
  What this means:
  \begin{itemize}
    \item For nodes/clusters in $V_\agree$, all incident edges are the same.
  \end{itemize}
\end{frame}
\begin{frame}
  \frametitle{Local changes}
  \begin{block}{Axiom 5: Locality}
    A graph clustering objective function $\Obj$ is \emph{local} if
    \begin{itemize}
    \item for all graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$\\ that agree on a set $V_\agree$ and its neighborhood,
    \item for all clusterings $C_1$ of $V_1 \setminus V_\agree$, $C_2$ of $V_2 \setminus V_\agree$ and $C_\agree,D_\agree$ of $V_\agree$.
    %\begin{tabular}{@{}l@{ }l}$C_\agree,D_\agree$ &of $V_\agree$,\\ $C_1$ &of $V_1 \setminus V_\agree$ and\\ $C_2$ &of $V_2 \setminus V_\agree$,\end{tabular}
    \end{itemize}
    \ \\[3mm]
    \begin{tabular}{@{}l@{ }l@{}}
    if   &$\Obj(G_1, C_\agree \cup C_1) \ge \Obj(G_1, D_\agree \cup C_1)$\\
    then &$\Obj(G_2, C_\agree \cup C_2) \ge \Obj(G_2, D_\agree \cup C_2)$.
    \end{tabular}
  \end{block}
\end{frame}
\begin{frame}
  \frametitle{Local changes}
%   \begin{block}{}
%     ...\\[5mm]
%     \begin{tabular}{@{}l@{ }l@{}}
%     if   &$\Obj(G_1, C_\agree \cup C_1) \ge \Obj(G_1, D_\agree \cup C_1)$\\
%     then &$\Obj(G_2, C_\agree \cup C_2) \ge \Obj(G_2, D_\agree \cup C_2)$.
%     \end{tabular}
%   \end{block}
  \begin{example}
    \begin{equation*}
      % {a,b,c}
      \begin{array}{ccc}
        % a
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.2) {a};
          \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
          \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=gray!40,draw=gray] (d) at (-1.2,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=gray!40,draw=gray] (a1) at (-1.3,0.7) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (f) to (e);
          \draw[draw=gray] (d) to (a1);
        \end{tikzpicture}
        \right)
        & \ge &
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=purple!40] (a) at (0,0.2) {a};
          \node[node,fill=RUBlue!40] (b) at (1.3,0.7) {b};
          \node[node,fill=purple!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=gray!40,draw=gray] (d) at (-1.2,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=gray!40,draw=gray] (a1) at (-1.3,0.7) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (f) to (e);
          \draw[draw=gray] (d) to (a1);
        \end{tikzpicture}
        \right)
        \\
         & \Updownarrow & \\
        %\rotatebox{90}{$\le$} & \Longrightarrow & \rotatebox{90}{$\le$} \\
        Q\left(
        \begin{tikzpicture}
          [baseline=-4.2mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.5) {a};
          \node[node,fill=RURed!40] (b) at (1.5,0.7) {b};
          \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=green!40!gray!40,draw=gray] (d) at (-1,-0.7) {$\cdot$};
          \node[node,fill=black!40!gray!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (a2) at (4,0.0) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a3) at (0.6,-1.9) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a4) at (3,-1.9) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (a2) to (e);
          \draw[draw=gray,very thick] (a2) to (f);
          \draw[draw=gray] (d) to (a3);
          \draw[draw=gray] (e) to (a3);
          \draw[draw=gray,very thick] (a4) to (a3);
          \draw[draw=gray] (a4) to (a2);
        \end{tikzpicture}
        \right)
        & \ge &
        %\delimitershortfall=2pt
        Q\left(
        \begin{tikzpicture}
          [baseline=-4.2mm
          ,scale=0.6
          ,thick]
          \node[node,fill=purple!40] (a) at (0,0.5) {a};
          \node[node,fill=RUBlue!40] (b) at (1.5,0.7) {b};
          \node[node,fill=purple!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=green!40!gray!40,draw=gray] (d) at (-1,-0.7) {$\cdot$};
          \node[node,fill=black!40!gray!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (a2) at (4,0.0) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a3) at (0.6,-1.9) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a4) at (3,-1.9) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (a2) to (e);
          \draw[draw=gray,very thick] (a2) to (f);
          \draw[draw=gray] (d) to (a3);
          \draw[draw=gray] (e) to (a3);
          \draw[draw=gray,very thick] (a4) to (a3);
          \draw[draw=gray] (a4) to (a2);
        \end{tikzpicture}
        \right)
      \end{array}
    \end{equation*}
  \end{example}
\end{frame}
\begin{frame}
  \frametitle{Local changes}
  %\begin{block}{}
  Special cases
    \begin{itemize}
      \item $G_1 = G_2$: change part of a clustering. \\
           In practice: optimize parts separately (divide and conquer).
      \item $V_\agree = \emptyset$: union of two disjoint graphs.
    \end{itemize}
  %\end{block}
%   \begin{example}[Unions]
%     \begin{equation*}
%       % {a,b,c}
%       \begin{array}{ccc}
%         % a
%         Q\left(
%         \right)
%         & \ge &
%         Q\left(
%         \right)
%         \\
%         & \Updownarrow & \\
%         Q\left(
%         \right)
%         & \ge &
%         Q\left(
%         \right)
%       \end{array}
%     \end{equation*}
%   \end{example}
\end{frame}

% ----------------------------
\begin{frame}
  \frametitle{Interlude: Related work}
  \begin{theorem}[Kleinberg 2002]
    There is no clustering function that is permutation invariant, scale invariant, monotonic and rich.
  \end{theorem}
  \begin{theorem}[Ackerman, Ben-David 2008]
    There is a clustering quality function that is permutation invariant, scale invariant, monotonic and rich.
  \end{theorem}
\end{frame}

\begin{frame}
  \frametitle{Discontinuity is magic}
  %\transdissolve<2,3>
  \begin{theorem}
    There is a graph clustering function that is scale invariant, permutation invariant, monotonic, rich and local.
  \end{theorem}
  \pause
  \begin{block}{Connected components}
    \begin{equation*}
      f_\text{coco}(G) = \text{the connected components of $G$}
    \end{equation*}
    \begin{equation*}
      Q_\text{coco}(G,C) = \indicator[\text{$C$ are the connected components of $G$}]
    \end{equation*}
  \end{block}
  \pause
  \begin{block}{Huh!?!?}
    \begin{itemize}
      \item Doesn't this contradict Kleinberg's theorem?
      \item No: edge weight 0 = distance $\infty$.
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}
  \frametitle{Discontinuity is magic}
  \begin{block}{Why I don't like it}
    \begin{itemize}
      \item Adding/removing an edge with tiny weight $\epsilon$ changes the graph slightly, but the clustering completely.
      \item Possibly unstable.
      \item So don't allow it.
    \end{itemize}
  \end{block}
  \begin{block}{Axiom 6: continuity}
    An objective function $\Obj$ is \emph{continuous} if a small change in the graph leads to a small change in the objective value.
    
    %Formally, $\Obj$ is continuous if for every $\epsilon > 0$ and every graph $G=(V,E)$ there exists a $\delta > 0$ such that for all graphs $G'=(V,E')$, if $E(i,j) - \delta < E'(i,j) < E(i,j) + \delta$ for all nodes $i$ and $j$, then $\Obj(G',C) - \epsilon < \Obj(G,C) < \Obj(G',C) + \epsilon$ for all clusterings $C$ of $G$.
  \end{block}
%   \begin{example}
%     \begin{equation*}
%       Q(G+\epsilon,C) \approx Q(G,C)
%     \end{equation*}
%   \end{example}
\end{frame}

% =============================================================================
\section{Modularity}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{An objective function}
  \begin{block}{Modularity}
%In this expression $v_c = \sum_{i \in c}\sum_{j \in V} \weight{i}{j}$ is the volume of a cluster, while $w_c = \sum_{i,j \in c} \weight{i}{j}$ is the within cluster weight. $v_V$ is the volume of the entire graph. Then
    \begin{equation*}
      \qmod(G,C) = \sum_{c \in C}\biggl( \frac{\within{c}}{\vol{V}} - \Bigl( \frac{\vol{c}}{\vol{V}} \Bigr)^2 \biggr).
    \end{equation*}
    \ \\[4mm]Where\\
    \begin{tabular}{@{\quad}ll}
      $v_c = \displaystyle\sum_{i \in c}\sum_{j \in V} \weight{i}{j}$ & volume of cluster \\
      $w_c = \displaystyle\sum_{i \in c}\sum_{j \in c} \weight{i}{j}$ & within cluster weight.
    \end{tabular}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Properties}
  The obvious:
  \begin{itemize}
    \item Modularity is permutation invariant.
    \item Modularity is scale invariant.
    \item Modularity is continuous.
  \end{itemize}
  The less obvious:
  \begin{itemize}
    \item Modularity is rich.
  \end{itemize}
  The bad:
  \begin{itemize}
    \item Modularity is \emph{not} local.
    \item Modularity is \emph{not} monotonic.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{What goes wrong?}
  \begin{proof}[Modularity is not monotonic]
    \begin{align*}
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=DarkGreen!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[] (a) to node[above] {1} (b);
          %\draw[] (b) to node[above] {1} (c);
          \draw[] (c) to node[above] {1} (d);
        \end{tikzpicture}
      \right) &= 0.125 \\
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=DarkGreen!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[line width=0.1*0.8] (a) to node[above] {0.1} (b);
          %\draw[] (b) to node[above] {1} (c);
          \draw[] (c) to node[above] {1} (d);
        \end{tikzpicture}
      \right) &= 0.079 \\
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=DarkGreen!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[] (a) to node[above] {1} (b);
          %\draw[] (b) to node[above] {1} (c);
          \draw[line width=2] (c) to node[above] {10} (d);
        \end{tikzpicture}
      \right) &= 0.079
    \end{align*}
  \end{proof}
\end{frame}

% =============================================================================
\section{Adaptive Modularity}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{Fixed Scale modularity}
  \begin{block}{Idea 1}
    Fix the scale
    \begin{equation*}
      \qfixed(G,C) = \sum_{c \in C}\biggl( \frac{\within{c}}{M} - \Bigl( \frac{\vol{c}}{M} \Bigr)^2 \biggr)
    \end{equation*}
  \end{block}
  Is it monotonic?
  
  \pause
  Take $v_c = w_c + b_c$ (within + between)
  \begin{equation*}
    \frac{\partial \qfixed(G,C)}{\partial w_c}
    %= 1/M - 2 v_c / M^2.
    = \frac{1}{M} - \frac{2 w_c + 2 b_c }{M^2}.
  \end{equation*}
  This is negative when $2 v_c > M$
  \pause
  \\\raggedleft{\huge $\Rightarrow$ not monotonic}
\end{frame}

\begin{frame}
  \frametitle{Adaptive Scale Modularity}
  \begin{block}{Idea 2}
    Add some $v_c$ to the denominator
    \begin{equation*}
      \qext{M}{\gamma}(G,C) = \sum_{c \in C}\biggl( \frac{\within{c}}{M + \vamount\vol{c}} - \Bigl( \frac{\vol{c}}{M + \vamount\vol{c}} \Bigr)^2 \biggr)
  .
    \end{equation*}
  \end{block}
  \pause
  \begin{block}{Theorem}
    Adaptive scale modularity is monotonic for all $M \ge 0$ and $\vamount \ge 2$.
  \end{block}
  \pause
  \begin{block}{Theorem}
    Adaptive scale modularity is rich for all $M \ge 0$ and $\vamount \ge 1$.
  \end{block}
  \pause
  \begin{block}{Theorem}
    Adaptive scale modularity is scale invariant for $M=0$.
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Adaptive Scale Modularity: related objectives}
  \begin{itemize}
    \item When $\gamma = 0$, we get fixed scale modularity.
          \\Equivalent to other modularity variants.
    \item When $\gamma = 0$ and $M = v_V$, we get modularity.
    \item When $M = 0$ we get
    \begin{equation*}
      \qext{0}{\gamma}(G,C) \propto \sum_{c \in C}\Bigl( \frac{\within{c}}{\vol{c}} - \frac1\vamount\Bigr),
    \end{equation*}
    i.e. normalized cut.
    \item When $M \to \infty$ we get
    \begin{equation*}
      \qext{\infty}{\gamma}(G,C) \propto \sum_{c \in C} \within{c},
    \end{equation*}
    i.e. unnormalized cut.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Adaptive Scale Modularity: behavior}
  Take a simple graph: 
    \begin{tikzpicture}[scale=1,baseline=-1mm]
      \node[node] (a) at (0,0) {$w$};
      \node[node] (b) at (1,0) {$w$};
      \draw[] (a) to node[above] {$b$} (b);
    \end{tikzpicture}
  \begin{itemize}
    \item Two cliques each with $w$ within weight
    \item Connected by edges with total weight $b$.
    \item Total volume $2w + 2b$.
    \item What is the behavior of adaptive scale modularity?
  \end{itemize}
\end{frame}
\begin{frame}
  \begin{center}
    \begin{minipage}[c]{0.78\linewidth}
      \includegraphics[width=1\linewidth]{plot-qext-wb}
    \end{minipage}\hspace*{2mm}
    \begin{minipage}[c]{0.15\linewidth}
      \def\legendscale{0.7}
      Legend:
      \begin{align*}
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \path[fill=white] (-0.5,-0.5) rectangle (0.5,0.5);
          \node[node,fill=white] (1) at (0,0) {1};
        \end{tikzpicture}}
        &=
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \node[node,fill=RURed!40] (a) at (0,0) {};
          \node[node,fill=RURed!40] (b) at (1,0) {};
          \draw[] (a) to (b);
        \end{tikzpicture}}
        \\
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \path[fill=blue!40] (-0.5,-0.5) rectangle (0.5,0.5);
          \node[node,fill=white] (1) at (0,0) {2};
        \end{tikzpicture}}
        &=
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \node[node,fill=RURed!40] (a) at (0,0) {};
          \node[node,fill=RUBlue!40] (b) at (1,0) {};
          \draw[] (a) to (b);
        \end{tikzpicture}}
        \\
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \path[fill=red!40] (-0.5,-0.5) rectangle (0.5,0.5);
          \node[node,fill=white] (1) at (0,0) {3};
        \end{tikzpicture}}
        &=
%         \begin{tikzpicture}[scale=0.8,baseline=-1mm]
%           \node[snode,fill=RURed!40] (a) at (0.41,0) {};
%           \node[snode,fill=purple!40] (a1) at (0,-0.23) {};
%           \node[snode,fill=teal!40] (a2) at (0,0.23) {};
%           \node[snode,fill=RUBlue!40] (b) at (1.6-0.41,0) {};
%           \node[snode,fill=DarkGreen!40] (b1) at (1.6,-0.23) {};
%           \node[snode,fill=yellow!40] (b2) at (1.6,0.23) {};
%           \draw[] (a) to (b);
%           \draw[ultra thick] (a) to (a1);
%           \draw[ultra thick] (a) to (a2);
%           \draw[ultra thick] (a1) to (a2);
%           \draw[ultra thick] (b) to (b1);
%           \draw[ultra thick] (b) to (b2);
%           \draw[ultra thick] (b1) to (b2);
%         \end{tikzpicture}
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \draw[thin] (0,0.25) to (1,0.25);
          \draw[thin] (0,0.25) to (1,-0.25);
          \draw[thin] (0,-0.25) to (1,-0.25);
          \draw[thin] (0,-0.25) to (1,0.25);
          \draw[ultra thick] (0,0.25) to (0,-0.25);
          \draw[ultra thick] (1,0.25) to (1,-0.25);
          \node[draw,inner sep=0,minimum width=5mm,semicircle,fill=RURed!40] (a1) at (0,0.25) {};
          \node[draw,inner sep=0,minimum width=5mm,semicircle,shape border rotate=180,fill=yellow!40] (a1) at (0,-0.25) {};
          \node[draw,inner sep=0,minimum width=5mm,semicircle,fill=RUBlue!40] (b1) at (1,0.25) {};
          \node[draw,inner sep=0,minimum width=5mm,semicircle,shape border rotate=180,fill=DarkGreen!40] (b2) at (1,-0.25) {};
%           \draw[thin] (a1) to (b1);
%           \draw[thin] (a1) to (b2);
%           \draw[thin] (a2) to (b1);
%           \draw[thin] (a2) to (b2);
%           \draw[ultra thick] (a1) to (a2);
%           \draw[ultra thick] (b1) to (b2);
        \end{tikzpicture}}
      \end{align*}
    \end{minipage}
  \end{center}
\end{frame}

% -----------------------------------------------------------------------------
\section{Conclusion}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{Summary}
  \begin{itemize}
    \item 6 axioms for graph clustering objectives.
    \item Graph setting allows for locality.
    \item Modularity is not monotonic.
    \item Non-monotonicity leads to splitting of cliques.
    \item Adaptive scale modularity satisfies all axioms (when $M=0$).
    \item Generalizes both modularity and normalized cut.
  \end{itemize}
\end{frame}

% -----------------------------------------------------------------------------
\section{}
\begin{frame}
  %\frametitle{End of talk}
  \vfill
  \begin{beamercolorbox}[sep=12pt,center]{title}
    %\Huge End of talk \\[1em]
    \huge Thank you for your attention.
  \end{beamercolorbox}
  \vskip1.5em
  \vfill
  \begin{beamercolorbox}[sep=8pt]{author}
     \usebeamerfont{author}\Large\insertlongtitle%
  \end{beamercolorbox}%
  \begin{beamercolorbox}[sep=8pt]{author}
    \ifx\insertlongauthor\@empty%
    \usebeamerfont{author}\insertauthor%
    \else%
    \usebeamerfont{author}\insertlongauthor%
    \fi%
  \end{beamercolorbox}
  \begin{beamercolorbox}[sep=8pt]{institute}
    \usebeamerfont{institute}\insertinstitute
  \end{beamercolorbox}
  \begin{beamercolorbox}[sep=8pt]{date}
    \usebeamerfont{date}\insertdate
  \end{beamercolorbox}
  \vfill
\end{frame}

\end{document}