I'm reading about graph sparsity and I have one problem in a paper I'm reading I don't understand, maybe someone can clarify:

Graph Sparsity:

In graph sparsity, we have a directed acyclic graph $G=(V,E)$ on the index set $I=\{1,2,...,p\}$ of the model parameter $w\in\mathbb{R}^p$, where $V=I$ is the vertex set and $E = \{(i,j)\;|\;i,j\in V\}$ is the edge set. $g$ is a path in the graph of $G$, denoted as $g=(v_1, v_2, ..., v_k)$, where $v_i \in V$, $i=1, ..., k$ and $(v_i, v_{i+1})\in E, i=1, ..., k-1$. Let $\Gamma$ be the set of all paths in the graph $G$. Denote $n_g>0$ as the positive weight of each path $g\in\Gamma$. The graph sparsity regularization is defined as follows:

$$\Omega_{Graph}(w)=\min_{J\subseteq\Gamma} \left\{ \sum_{g\in J} n_g\;s.t.\;Supp(w)\subseteq \bigcup_{g\in J} g \right\}$$

where $Supp(\cdot)$ stands for the nonzero index set of a vector. J is a subset of $\Gamma$ whose union covers the support of $w$.

My problem is understanding $Supp(w)$, what is it? It's not exactly clear to me. What does it contain exactly? A subset of indexes from $I$ such that....what? :)

I understood that we try try to find the subset of paths $J$, such that $\sum_{g\in J} n_g$ is minimized, subject to ...?

Thank you for any help =)

please comment if my questions is unclear


I think that the support ($Supp$) of $w$ are the indices of the nonzero component of $w$.

You can see $w$ as a binary vector identifying a subset of the nodes.

For example, $w=(1,-2,0,34,0,1/2)$ is identifying the set of nodes $\{1,2,4,6\}$

In the definition of sparsity regularization, you are taking the minimum weight over the subsets of path, whose union pass through all the nodes identified by $w$. It's like you're imposing that you have to pass through them.

  • $\begingroup$ P.S. shouldn't your second vector be: $\{1, 2, 4, 6\}$? $\endgroup$ – jjepsuomi Oct 10 '14 at 11:54
  • $\begingroup$ you have six components but index 7? =) $\endgroup$ – jjepsuomi Oct 10 '14 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.