Let $G(V,E)$ is a weighted simple graph, where $V$ and $E$ are the set of vertices and Edges. The graph is undirected. Let $A \in \{0,1\}^{n\times n}$ and $W \in R_+^{n\times n}$ be the adjacency matrix and the weight matrix of the graph. Note that both both $A$ and $W$ are symmetric. My target is to output a sparse representation of this graph. I am focusing on edge sparsification that means deleting edges from the graph. In particular I am concentrating on degree constraint subgraph of the original graph as a representation of sparsity. Let the new graph is $G_s(V,E_s)$, where the $E_s$ is the edge set of the new graph while the vertex set remains unchanged. My goal in sparsification is to find a degree constraint subgraph $G_s$ of the original graph $G$, optimizing some distance criteria between them.

A vertex $v \in V$ in $G$ can be thought of a vector, say $W_v$ in $R_+^{|V|}$. Here $W_v$ is the $v$'th row of the matrix $W$ which represents the weights of the adjacent edges of $v$. We define a binary matrix $X \in \{0,1\}^{n\times n}$. $X$ would be the adjacency matrix of the new graph $G_s$. We want to solve the following optimization problem.

\begin{align*} \text{min} \quad &\sum_{v \in V}||W_v-W_v \circ X_v||_2 \\ \text{s.t.,}\quad &\sum_{i \in V} X_{vi} \leq b_v \quad \forall v \in V \\ &X_{vi} \leq A_{vi} \quad \forall v \in V, \forall i \in V \\ &X_{vi} = X_{iv} \quad \forall v \in V, \forall i \in V \\ &X_{vv} = 0 \quad \forall v \in V\\ &X_{vi} =\{0,1\}, \quad \forall v \in V, \forall i \in V \end{align*}

The $(W_v-W_v\circ X_v)$ is the difference vector between the original incident vector and the new incident vector for vertex $v$. Note that $W_v\circ X_v$ is the pairwise multiplication between these two vector also known as hadamard operation. The objective function is the summation of the norm of this difference vector over all the vertices in the graph. We wish to minimize this quantity subject to several constraints. The first constraint bounds the degree of the new graph by a user input positive bound defined for each vertex. The second constraint ensure that the new graph is a subgraph of the original graph that is no new edges are created. The third and fourth constraint is necessary to output a loop free symmetric graph.

Now what I need is the simplification of the objective function. Ideally I want to show equivalence of the objective function to something like this $$ {\rm max} \sum_{v \in V} ||W_v \circ X_v||_2 $$

Any idea of how to simplify the objective function?

  • 3
    $\begingroup$ Your objective looks simple to me. What are the qualities of a simple objective function in your mind? Why is this one not simple? $\endgroup$ – Richard Feb 20 '19 at 6:00
  • $\begingroup$ Each individual sum component of the objective function is $||W_v-W_v \circ X_v||_2$. We know that, $||W_v-W_v \circ X_v|| \geq ||W_v|| - ||W_v\circ X_v||$, since $||W_v|| \geq ||W_v \circ X_v||$. Now is it possible to establish equivalence between the initial objective function?That is $$ {\rm min} \sum_{v \in V}||W_v-W_v \circ X_v||_2 $$ to $$ {\rm min} \sum_{v \in V}(||W_v||_2 - ||W_v\circ X_v||_2) $$ which establishes equivalence to $$ {\rm max} \sum_{v \in V}||W_v\circ X_v||_2 $$ $\endgroup$ – user2104150 Feb 21 '19 at 22:46

Your Answer

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

Browse other questions tagged or ask your own question.