Efficient Network Flow Models for Optimal Homology Problems over the Integers

• OHCP - find a homologous $d$-cycle $\text{x}\sim \text{z}$ that minimizes a weighted sum of its $d$-simplices
• MSFN - find a $d$-cycle $\text{x}$ homologous to $\text{z}$ through a $(d+1)$-chain $\pi$ whose sum of the $d$-dimensional volume of $\text{x}$ and $\lambda$-scaled $(d+1)$-dimensional volume of $\pi$ is minimized.
  • OHCP is a special case of MSFN where $\lambda =0$
  • The $\Lambda$-SFN, or length-scaled SFN, scales the $d$-dimensional volume by $\Lambda =1/\lambda$.
  • Optimal bounding chain problem (OBCP) is special case of $\Lambda$-SFN where $\Lambda =0$
• $(d+1)$-complexes in ${\mathbb{R}}^{d+1}$, with homology over $\mathbb{Z}$, can be solved in polynomial time.
  • Hence, they focus on nontrivial $d$-cyles in a $(d+1)$-complex $\mathcal{K}$ embedded in ${\mathbb{R}}^{d+1}$

Background

• A $d$-complex $\mathcal{K}$ is called pure if every maximal simplex is of dimension $d$.
• A pure $d$-complex $\mathcal{K}$ is a weak $d$-pseudomanifold if each $(d-1)$-simplex has at most two cofaces.
• They consider oriented skeletons:
  • Positive $d$-skeleton: $\overrightarrow{{\mathcal{K}}_d^{+}}=\{{\sigma }_i\mid {\sigma }_i\in {\mathcal{K}}_d\}$
  • Negative $d$-skeleton: $\overrightarrow{{\mathcal{K}}_d^{-}}=\{-{\sigma }_i\mid {\sigma }_i\in {\mathcal{K}}_d\}$
  • Symmetric Directed $d$-skeleton: ${\vec{\mathcal{K}}}_d={\vec{\mathcal{K}}}_d^{+}\cup {\vec{\mathcal{K}}}_d^{-}$
• On directed $d$-complexes, $\mathbb{Z}$-(co)chains are modeled by $\text{x}={\text{x}}^{+}-{\text{x}}^{-}$ where $\text{x}\in \mathcal{C}(\mathcal{K};\mathbb{Z})$ and ${\text{x}}^{+},{\text{x}}^{-}\in \mathcal{C}(\vec{\mathcal{K}};{\mathbb{Z}}_{+})$
• A $d$-cycle $\text{z}$ is called non-bounding or non-trivial if $\text{z}\in {\mathcal{Z}}_d(\mathcal{K})\setminus {\mathcal{B}}_d(\mathcal{K})$
• The $d$-th homology group ${\mathcal{H}}_d(\mathcal{K})={\mathcal{Z}}_d(\mathcal{K})/{\mathcal{B}}_d(\mathcal{K})$
  • Two $d$-cycles $\text{z}$ and $\text{x}$ are homologous, $\text{z}\sim \text{x}$, if there is a $(d+1)$-chain $\mathbf{\pi }\in {\mathcal{C}}_{d+1}(\mathcal{K})$ such that ${\partial }_{d+1}\mathbf{\pi }=\mathbf{z}-\mathbf{x}$.
• A $d$-cochain $\mathbf{f}\in {\mathcal{C}}^d(\mathcal{K};\mathbb{Z})$ is a homomorphism $\mathbf{f}:{\mathcal{C}}_d(\mathcal{K};\mathbb{Z})\to \mathbb{Z}$.

Question: I am unclear on how we are representing $d$-cochains in Figure 2.

• The $d$-coboundary operator is a map ${\delta }_d:{\mathcal{C}}^d(\mathcal{K})\to {\mathcal{C}}^{d+1}(\mathcal{K})$ defined by

$$({\delta }_d\mathbf{\phi })(\mathbf{c})=\mathbf{\phi }({\partial }_d\mathbf{c})\text{ for }\mathbf{c}\in {\mathcal{C}}_d(\mathcal{K}).$$

• The $d$-th cohomology group ${\mathcal{H}}^d(\mathcal{K})={\mathcal{Z}}^d(\mathcal{K})/{\mathcal{B}}^d(\mathcal{K})$
  • Two $d$-cocycles $\mathbf{f}$ and $\mathbf{\varphi }$ are cohomologous, $\mathbf{f}\sim \mathbf{\varphi }$, if there is a $(d-1)$-cochain $\mathbf{\rho }\in {\mathcal{C}}^{d-1}(\mathcal{K})$ such that $\mathbf{\varphi }=\mathbf{f}+{\delta }_d\mathbf{\rho }$.
• ${\mathcal{H}}_d(\mathcal{K})\cong {\mathcal{H}}^d(\mathcal{K})$
• The $d$-th Betti number is given by ${\beta }_d=\text{rank}{\mathcal{H}}_d(\mathcal{K})=\text{rank}{\mathcal{H}}^d(\mathcal{K})$

Hodge Decomposition

${\mathcal{C}}_d(\mathcal{K})\cong {\mathcal{B}}^d(\mathcal{K})\oplus {\mathcal{H}}_d(\mathcal{K})\oplus {\mathcal{B}}_d(\mathcal{K})$

• Due to Hodge theorem: (UNSURE ON THIS)
  1. $d$-cocycles are orthogonal to $d$-boundaries: $\mathbf{f}({\partial }_{d+1}\tau )=({\delta }_{d+1}\mathbf{f})(\tau )=0$ for $\mathbf{f}\in {\mathcal{Z}}^d(\mathcal{K})$ and $\tau \in {\mathcal{K}}_{d+1}$
  2. $d$-cycles are orthogonal to $d$-coboundaries: $({\delta }_d\rho )(\mathbf{z})={\partial }_d\mathbf{z}(\rho )=0$ for $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$ and $\rho \in {\mathcal{K}}_{d-1}$

Question: The phrase ${\partial }_d\mathbf{z}(\rho )$ is confusing me. $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$ is a cycle and can be thought of as a vector, but we are passing in ($d-1$)-simplex $\rho \in {\mathcal{K}}_{d-1}$? Is $\rho$ supposed to be a $(d-1)$-coboundary and it should be $\rho ({\partial }_d\mathbf{z})$ instead? Or, are we thinking of chains as maps $\mathbf{z}:{\mathcal{K}}_d\to \mathbb{Z}$?

• A flow is another name for a $d$-cycle
  • Flow conservation condition: ${\partial }_d\mathbf{z}=0$ which is equivalent to $\mathbf{z}({\delta }_d\sigma )=0$ for all $\sigma \in {\mathcal{K}}_{d-1}$
• A coflow is another name for a $d$-cocycle
  • Circulation conservation condition: ${\delta }_{d+1}\mathbf{f}=0$, i.e., $\mathbf{f}({\partial }_{d+1}\tau )=0$ for all $\tau \in {\mathcal{K}}_{d+1}$
  • One may view a $d$-coflow $\mathbf{f}\in {\mathcal{Z}}^d(\mathcal{K})$ as a function $\mathbf{f}:{\mathcal{Z}}_d(\mathcal{K})\to \mathbb{Z}$ such that ${\mathcal{B}}_d(\mathcal{K})\mapsto 0$ under $\mathbf{f}$
    • Then a $d$-coboundary $\mathbf{g}\in {\mathcal{B}}^d(\mathcal{K})$ is a special case of coflow where ${\mathcal{Z}}_d(\mathcal{K})\mapsto 0$ under $\mathbf{g}$
• The flux of $\mathbf{f}\in {\mathcal{Z}}^d(\mathcal{K})$ through a closed surface $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$ is given by $|\mathbf{f}(\mathbf{z})|\in {\mathbb{Z}}_{+}$
• A $d$-(co)chain is simple if it assigns no more than a unit value to $d$-simplices
  • For chains, their coefficients lie in $\{-1,0,1\}$
  • For cochains, $\mathbf{f}(\sigma )\in \{-1,0,1\}$ for all $\sigma \in {\mathcal{K}}_d$
• Homology Signature:
  • Let $\{{\mathring{\mathbf{w}}}_1,\dots ,{\mathring{\mathbf{w}}}_{{\beta }_d}\}$ be simple cycles that generate ${\mathcal{H}}_d(\mathcal{K})$
  • Let ${\mathring{\mathbf{w}}}_0={\partial }_{d+1}\mathcal{K}+{\sum }_{l=1}^{{\beta }_d}{\mathring{\mathbf{w}}}_l$
  • Then any $d$-cycle $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$ is homologous to

$$\mathbf{z}\sim \sum _{l=0}^{{\beta }_d}{\zeta }_l\cdot {\mathring{\mathbf{w}}}_l\text{ where }{\zeta }_0=0$$

- The homology signature is given by $[\mathbf{z}]=[\zeta_0,\zeta_1,\dots,\zeta_{\beta_d}]$
	- $\mathbf{x}\sim\mathbf{z}$ if and only if $[\mathbf{x}]=[\mathbf{z}]$

Question: Why define ${\mathring{\mathbf{w}}}_0$ if ${\zeta }_0=0$ in the linear combination?

• A $d$-copath between simple $d$-cycles $w^{\prime },w^{\prime \prime }\in {\mathcal{Z}}_d(\mathcal{K})$ is a simple $d$-cochain $\mathbf{p}=\mathbf{p}({\mathbf{w}}^{\prime }⇝{\mathbf{w}}^{\prime \prime })\in {\mathcal{C}}^d(\mathcal{K})$ such that $\mathbf{p}({\mathbf{w}}^{\prime })=-1$ and $\mathbf{p}({\mathbf{w}}^{\prime \prime })=+1$ and is 0 for any other $d$-cycle
  • If ${\mathbf{w}}^{\prime }={\partial }_{d+1}\eta$ and ${\mathbf{w}}^{\prime \prime }={\partial }_{d+1}\tau$, then ${\delta }_{d+1}\mathbf{p}=\tau -\eta$
  • We say the $d$-copath is augmenting if ${\mathbf{w}}^{\prime },{\mathbf{w}}^{\prime \prime }\in {\mathcal{H}}_d(\mathcal{K})$ are non-bounding

Non-negative (co)flow and homology over ${\mathbb{Z}}_{+}$

• Non-zero $d$-cochain ${\Omega }^d$ which maps positively oriented $d$-simplices to $+1$ and negative oriented $d$-simplices to $-1$.
  • $d$-cochains can be viewed as odd functions: $\mathbf{f}(\sigma )={\Omega }_d(\sigma )\mathbf{f}(\sigma )$
• An integral cochain $\mathbf{f}\in {\mathcal{C}}^d(\mathcal{K};\mathbb{Z})$ is modeled by a non-negative function $\vec{\mathbf{f}}:{\vec{\mathcal{K}}}_d^{+}\cup {\vec{\mathcal{K}}}_d^{-}\to {\mathbb{Z}}_{+}$ such that $\mathbf{f}(\sigma )=\vec{\mathbf{f}}({\sigma }_{+})-\vec{\mathbf{f}}({\sigma }_{-})$.

**Chain complex of ${\mathbb{Z}}_{+}$-semimodules

• $\vec{\mathcal{K}}$ is complex of directed skeletons ${\vec{\mathcal{K}}}_d$ for all $d=0,1,\dots ,\text{dim}\mathcal{K}$.
• Construct sequence of ${\mathbb{Z}}_{+}$ semimodules ${\vec{\mathcal{C}}}_d={\mathcal{C}}_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})$ connected by homomorphisms

$$\cdots {\rightrightarrows }_{{\partial }_{d+2}^{-}}^{{\partial }_{d+2}^{+}}{\vec{\mathcal{C}}}_{d+1}{\rightrightarrows }_{{\partial }_{d+1}^{-}}^{{\partial }_{d+1}^{+}}{\vec{\mathcal{C}}}_d{\rightrightarrows }_{{\partial }_d^{-}}^{{\partial }_d^{+}}{\vec{\mathcal{C}}}_{d-1}{\rightrightarrows }_{{\partial }_{d-1}^{-}}^{{\partial }_{d-1}^{+}}\cdots$$

• $\vec{\mathcal{C}}(\vec{\mathcal{K}};{\mathbb{Z}}_{+})$ is a chain complex if (see remark below)

$${\partial }_d^{+}{\partial }_{d+1}^{+}+{\partial }_d^{-}{\partial }_{d+1}^{-}={\partial }_d^{+}{\partial }_{d+1}^{-}+{\partial }_d^{-}{\partial }_{d+1}^{+}$$

Remark: Chain complex typically has ${\partial }_d{\partial }_{d+1}=0$ as the requirement. But here, we have two boundary homomorphisms for positive/negative skeletons. I assume they are defined as follows:

$${\partial }_d(\sigma )={\partial }_d({\sigma }_{+}-{\sigma }_{-})={\partial }_d^{+}{\sigma }_{+}-{\partial }_d^{-}{\sigma }_{-}.$$

If so, the condition becomes

$$\begin{array}{rl}0={\partial }_d{\partial }_{d+1}(\sigma )& ={\partial }_d({\partial }_{d+1}^{+}{\sigma }_{+})-{\partial }_d({\partial }_{d+1}^{-}{\sigma }_{-})\\ & ={\partial }_d^{+}{\partial }_{d+1}^{+}{\sigma }_{+}-{\partial }_d^{-}{\partial }_{d+1}^{+}{\sigma }_{+}-{\partial }_d^{+}{\partial }_{d+1}^{-}{\sigma }_{-}+{\partial }_d^{-}{\partial }_{d+1}^{-}{\sigma }_{-}\end{array}$$

Or rearranged, the condition.

• Define $d$-cycles: ${\mathcal{Z}}_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})=\{\vec{\mathbf{z}}\in {\mathcal{C}}_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})\mid {\partial }_d^{+}(\vec{\mathbf{z}})={\partial }_d^{-}(\vec{\mathbf{z}})\}$
• Define boundary relation ${\rho }_d={\rho }_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})$ on ${\mathcal{Z}}_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})$:

$$\vec{\mathbf{x}}\sim \vec{\mathbf{z}}⟺\exists {\mathbf{\pi }}^{+},{\mathbf{\pi }}^{-}\in {\mathcal{C}}_{d+1}(\vec{\mathcal{K}};{\mathbb{Z}}_{+})\text{ s.t. }\vec{\mathbf{x}}+{\partial }_{d+1}^{+}{\mathbf{\pi }}^{+}+{\partial }_{d+1}^{-}{\mathbf{\pi }}^{-}=\vec{\mathbf{z}}+{\partial }_{d+1}^{+}{\mathbf{\pi }}^{-}+{\partial }_{d+1}^{-}{\mathbf{\pi }}^{+}$$

Question: Usual boundary condition is $\mathbf{x}=\mathbf{z}+{\partial }_{d+1}\mathbf{\pi }$ after splitting into positive/negative we get

$$\begin{array}{rl}\vec{\mathbf{x}}& =\vec{\mathbf{z}}+{\partial }_{d+1}^{+}{\mathbf{\pi }}^{+}-{\partial }_{d+1}^{-}{\mathbf{\pi }}^{-}\end{array}$$

I’m not seeing where this relation is coming from.

• Define the $d$-homology of $\vec{\mathcal{K}}$ by ${\mathcal{H}}_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})={\mathcal{Z}}_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})/{\rho }_d(\vec{\mathcal{K}};{\mathbb{Z}}_{+})$

Optimal homology problems

• $m=|{\mathcal{K}}_d|$, number of $d$-simplices
• $n=|{\mathcal{K}}_{d+1}|$, number of $(d+1)$-simplices
• Length costs: $c:{\mathcal{K}}_d\to {\mathbb{Z}}_{+}$ and Area costs: $\alpha :{\mathcal{K}}_{d+1}\to {\mathbb{Z}}_{+}$
  • Then cost of $d$-chain $\mathbf{x}$ and $(d+1)$-chain $\mathbf{\pi }$ are

$$|c(\mathbf{x})|=\sum _{e\in {\mathcal{K}}_d}c(e_i)\cdot |\mathbf{x}(e_i)|\ge 0\text{ and }|\alpha c(\mathbf{\pi })|=\sum _{{\tau }_j\in {\mathcal{K}}_{d+1}}\alpha ({\tau }_j)\cdot |\mathbf{\pi }({\tau }_j)|\ge 0$$

Definition 2.1 (OHCP)

Find a $d$-cycle $\mathbf{x}\sim \mathbf{z}$ of minimal cost: ${\min }_{\mathbf{x},\mathbf{\pi }}|c(\mathbf{x})|\text{ s.t. }{\partial }_{d+1}\mathbf{\pi }=\mathbf{z}-\mathbf{x},\mathbf{x}\in {\mathcal{Z}}_d(\mathcal{K}),\mathbf{\pi }\in {\mathcal{C}}_{d+1}(\mathcal{K})$

• Below is the OHCP in LP form:

$$\begin{array}{rlr}& \underset{\mathbf{x},\mathbf{\pi }}{\min }& c({\mathbf{x}}^{+})+c({\mathbf{x}}^{-})\\ & \text{s.t.}& [{\partial }_{d+1}]({\mathbf{\pi }}^{+}-{\mathbf{\pi }}^{-})+{\mathbf{x}}^{+}-{\mathbf{x}}^{-}=\mathbf{z}\\ & & {\mathbf{x}}^{+},{\mathbf{x}}^{-}\ge 0_m,{\mathbf{\pi }}^{+},{\mathbf{\pi }}^{-}\ge 0_n\end{array}$$

• The dual LP maximizes flux through $\mathbf{z}$:

$$\begin{array}{rlr}& \underset{\mathbf{f}}{\max }& |\mathbf{f}(\mathbf{z})|\\ & \text{s.t.}& {\delta }_{d+1}\mathbf{f}=0_n\\ & & -\mathbf{c}\le \mathbf{f}\le \mathbf{c}\end{array}$$

Question: I have zero idea how this dual LP was found; perhaps the full paper gives more details?

Definition 2.2 (SFN)

The simplicial flat norm of $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K};\mathbb{Z})$ is given by $\mathbb{F}(\mathbf{z})=\min \{|c(\mathbf{x})|+|\alpha (\mathbf{\pi })|\mid {\partial }_{d+1}\mathbf{\pi }=\mathbf{z}-\mathbf{x}\}$

Definition 2.3 (MSFN)

Given $\lambda \in {\mathbb{Z}}_{+}$ or $\Lambda =1/\lambda \in {\mathbb{Z}}_{+}$, the multiscale simplicial flat norm of $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K};\mathbb{Z})$ is given by ${\mathbb{F}}_{\lambda }(\mathbf{z})=\min \{|c(\mathbf{x})|+\lambda |\alpha (\mathbf{\pi })|\mid {\partial }_{d+1}\mathbf{\pi }=\mathbf{z}-\mathbf{x}\}$ or ${\mathbb{F}}_{\Lambda }(\mathbf{z})=\min \{\Lambda |c(\mathbf{x})|+|\alpha (\mathbf{\pi })|\mid {\partial }_{d+1}\mathbf{\pi }=\mathbf{z}-\mathbf{x}\}$

• We collapse both into the SFN problem and scale $c$ or $\alpha$ appropriately
• Below is the SFN in LP form:

$$\begin{array}{rlr}& \underset{\mathbf{x},\mathbf{\pi }}{\min }& c({\mathbf{x}}^{+})+c({\mathbf{x}}^{-})+\alpha ({\mathbf{\pi }}^{+})+\alpha ({\mathbf{\pi }}^{-})\\ & \text{s.t.}& [{\partial }_{d+1}]({\mathbf{\pi }}^{+}-{\mathbf{\pi }}^{-})+{\mathbf{x}}^{+}-{\mathbf{x}}^{-}=\mathbf{z}\\ & & {\mathbf{x}}^{+},{\mathbf{x}}^{-}\ge 0_m,{\mathbf{\pi }}^{+},{\mathbf{\pi }}^{-}\ge 0_n\end{array}$$

• Below is the dual of the LP:

$$\begin{array}{rlr}& \underset{\tilde{\mathbf{f}}}{\max }& |\tilde{\mathbf{f}}(\mathbf{z})|\\ & \text{s.t.}& -{\mathbf{\alpha }}_n\le {\delta }_{d+1}\tilde{\mathbf{f}}\le {\mathbf{\alpha }}_n\\ & & -{\mathbf{c}}_m\le \tilde{\mathbf{f}}\le {\mathbf{c}}_m\end{array}$$

- The circulation preservation condition no longer holds in this case.

Cohomology of Embedded and Dual Complexes