text:
\section{Conclusion}
We introduced an optimal transport framework for compressing graphs. Our framework can seamlessly encode prior information about the importance of individual nodes, their labels or attributes, and edges in the graph.

Our perspective hinges on several technical contributions. We first extended the notion of optimal transport on graphs to accommodate undirected edges. We then provided a dual characterization of the optimal transport distance in terms of distributions over the nodes. We could thus view compression as the problem of minimizing the transport cost from a fixed initial distribution supported on all vertices to an unknown target distribution with smaller support.

We introduced binary selection variables in our compression problem to exert a direct control on sparsity. Thus, we could avoid iterative tuning that is required to match a target support in methods that enforce an $\ell_1$ penalty. The resulting formulation entailed a novel Euclidean projection step on the probability simplex under a diagonal transformation. We provided an efficient algorithm to solve this problem. Our approach also led to a related smooth saddle point problem that could be solved very efficiently by standard algorithms.

Beyond its theoretical foundations, our method demonstrated strong empirical performance on two separate tasks.  Specifically, it outperformed state-of-the-art REC algorithm on standard datasets for graph classification. Moreover, it produced compressed graphs that preserved key structural details in real and synthetic examples.

\section{Optimal transport for general edges} \label{OTGeneral}
Let $\vec{G} = (V, \vec{E})$ be a directed graph on nodes (or vertices) $V$ and edges $\vec{E}$. We define the signed incidence matrix $\vec{F}$: $\vec{F}(\vec{e}, v) = 1$ if $\vec{e} = (w, v) \in \vec{E} \mbox{ for some } w \in V$, $-1$ if $\vec{e} = (v, w) \in \vec{E} \mbox{ for some } w \in V$, and $0$ otherwise.
Let $c(\vec{e}) \in \mathbb{R}_+$ be the positive cost to transport unit mass along edge $\vec{e} \in \vec{E}$, and $\Delta(V)$ the probability simplex on $V$. The shorthand $a \preceq b$ denotes that $a(i) \leq b(i)$ for each component $i$. Let $\boldsymbol{0}$ be a vector of all zeros and $\boldsymbol{1}$ a vector of all ones.
Let $\rho_0, \rho_1 \in \Delta(V)$ be  distributions over the vertices in $V$. The optimal transport distance $\vec{W}(\rho_0, \rho_1)$ from $\rho_0$ to $\rho_1$ is \cite{ES2018}:
\begin{eqnarray*}
\vec{W}(\rho_0, \rho_1) & = & \displaystyle \min_{\substack{J \in \mathbb{R}^{|\vec{E}|}\\~~ \boldsymbol{0} ~\preceq~ J}}  ~~ \sum_{\vec{e} \in \vec{E}} c(\vec{e}) J(\vec{e})~~ \qquad \text{s.t.} ~~~~~\vec{F}^{\top} J  ~=~ \rho_1 - \rho_0~,
\end{eqnarray*}
where $J(\vec{e})$ is the non-negative mass transfer from tail to head on edge $\vec{e}$. Intuitively, $\vec{W}(\rho_0, \rho_1)$ is the minimum cost of a directed flow from $\rho_0$ to $\rho_1$.  In order to extend this intuition to the undirected graphs, we need to refine the notion of incidence, and let the mass flow in either direction.
Specifically, let $G = (V, E)$ be a connected undirected graph.  We define the incidence matrix pertaining to $G$ as $F(e, v) = 1  \mbox { if  edge } e  \text{ is incident on } v$, and $0$ otherwise.
 \noindent With each undirected edge $e \in E$, having cost $c(e) \in \mathbb{R}_+$, we associate two directed edges $e^+$ and $e^-$, each with cost $c(e)$, and flow variables $J^+(e), J^-(e) \geq 0$. Then, the total {\em undirected flow} pertaining to $e$ is $J^+(e) + J^-(e)$.
 Since we incur cost for flow in either direction, we define the optimal transport cost $W(\rho_0, \rho_1)$ from $\rho_0$ to $\rho_1$ as
\begin{eqnarray}
 \min_{\substack{J^+, J^- \in \mathbb{R}^{|E|} \\ \boldsymbol{0} ~\preceq~ J^+, J^-}} & \displaystyle \sum_{e \in E} c(e) (J^+(e) + J^-(e)) \qquad
\text{s.t.} \quad F^{\top} (J^- - J^+)  =  \rho_1 - \rho_0~~.  \label{UnWass}
\end{eqnarray}
We call a directed edge $e^+$ {\em active} if $J^+(e) > 0$, i.e., there is some positive flow on the edge (likewise for $e^-$). Moreover, by extension, we call an undirected edge $e$ active if at least one of $e^+$ and $e^-$ is active. We claim that at most one of $e^+$ and $e^-$ may be active for any edge $e$.
\begin{theorem}\label{Theorem1}
The optimal solution to \eqref{UnWass} must have  $J^+(e) = 0$ or $J^-(e) = 0$ (or both) $\forall\,e \in E$.
\end{theorem}
The proof is provided in the supplementary material. Thus, like the directed graph setting, we either have flow in only one direction for each edge $e$, or no flow at all. Moreover, Theorem \ref{Theorem1} facilitates generalizing optimal transport distance to mixed graphs $\tilde{G}(V, E, \vec{E})$, i.e., where both directed and undirected edges may be present. In particular, we adapt the formulation in \eqref{UnWass} with minor changes: (a) we associate bidirectional variables with each edge, directed or undirected. For the undirected edges $e \in E$, we replicate the constraints from \eqref{UnWass}. For the directed edges $\vec{e}$, we  follow the convention that $J^{+}(\vec{e})$ denotes the outward flow along $\vec{e}$ whereas $J^{-}(\vec{e})$ denotes the incoming flow (from head to tail), and impose the additional constraints $J^{-}(\vec{e}) = 0$. We will focus on undirected graphs $G = (V, E)$ since the extensions to directed and mixed graphs are immediate due to Theorem \ref{Theorem1}.

\section{Experiments} \label{Experiments}
We conducted several experiments to demonstrate the merits of our method.
We start by describing the experimental setup. We fixed the value of hyperparameters in Algorithm \ref{MPPrimal1} for all our experiments. Specifically, we set the regularization coefficient $\lambda=1$, and the gradient rates $\alpha_\ell=0.1, \beta_\ell=0.1, \gamma_\ell=0.1$ for each $\ell \in \{0, 1, \ldots, T\}$. We also let $\rho_0$ be the stationary distribution by setting $\rho_0(v)$ for each $v \in V$ as the ratio of $deg(v)$, i.e. the degree of $v$, to the sum of degrees of all the vertices. Note that the distribution thus obtained is the unique stationary distribution for connected non-bipartite graphs, and {\em a} stationary distribution for the bipartite graphs. Moreover, for non-bipartite graphs, it has a nice physical interpretation in that any random walk on the graph always converges to this distribution irrespective of the graph structure.

The objective of our experiments is three-fold. Since compression is often employed as a preprocessing step for further tasks, we first show that our method compares favorably, in terms of test accuracy, to the state-of-the-art compression methods on graph classification. We then demonstrate that our method performed the best in terms of the compression time. We finally show that our approach provides qualitatively meaningful compression on synthetic and real examples.

\subsection{Classifying standard graph data} \label{ClassifySection}
We used several standard graph datasets for our experiments, namely, DHFR \cite{SOW2003}, BZR-MD \cite{KM2012}, MSRC-9, MSRC-21C \cite{NGBK2016}, and  Mutagenicity \cite{KMB2005}. We focused on these datasets since they represent a wide spectrum in terms of the number of graphs, number of classes, average number of nodes per graph, and average number of edges per graph (see Table \ref{tab:compare} for details). All these datasets have a class label for each graph, and additionally, labels for each node in every graph.

We compare the test accuracy of our algorithm, OTC (short for Optimal Transport based Compression), to several state-of-the-art methods: REC \cite{LV2018}, Heavy edge matching (Heavy) \cite{DGK2007}, Affinity vertex proximity (Affinity) \cite{LB2012}, and Algebraic distance (Algebraic) \cite{RSB2011, CS2011}.
Amongst these, the REC algorithm is a randomized method that iteratively contracts edges of the graph and thereby coarsens the graph.
Since the method is randomized, REC yields a compressed graph that achieves a specified compression factor, i.e., the ratio of the number of nodes in the reduced graph to that in the original uncompressed graph, only in expectation. Therefore, in order to allow for a fair comparison, we  first run REC on each graph with the compression factor set  to 0.5, and then execute other baselines and our algorithm, i.e. Algorithm \ref{MPPrimal1}, with $k$ set to the number of nodes in the compressed graph produced by REC. Also to mitigate the effects of randomness on the number of nodes returned by REC, we performed 5 independent runs for REC, and subsequently all other methods.

Each collection of compressed graphs was then divided into train and test sets, and used for our classification task. Since our datasets do not provide separate train and test sets, we employed the following procedure for each dataset. We partitioned each dataset into multiple train and test sets of varying sizes. Specifically, for each $p \in \{0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8\}$, we divided each dataset randomly into a train set containing a fraction $p$ of the graphs in the dataset, and a test set containing the remaining $1-p$ fraction. To mitigate the effects of chance, we formed 5 such independent train-test partitions for each fraction $p$ for each dataset. We averaged the results over these multiple splits to get one reading per collection, and thus 5 readings in total for all collections, for each fraction for each method. We averaged the test accuracy across collections for each method and fraction.

We now specify the cost function $c$ for our algorithm. As described in section \ref{SecGraphCompress}, we can leverage the cost function to encode preference for different edges in the compressed graph. For each graph, we set $c=0.01$ for each edge $e$ incident on the nodes with same label, and $c=0.02$ for each $e$ incident on the nodes that have different label. Thus, in order to encourage diversity of labels, we slightly biased the graphs to prefer retaining the edges that have separate labels at their end-points. More generally, one could parameterize and thus learn the costs for edges.

In our experiments, we employed support vector machines (SVMs), with Weisfeiler-Lehman subtree kernel \cite{SSLMB2011} to quantify the similarity between graphs \cite{NGBK2016, VSKB2010,  KP2016}. This kernel is based on the Weisfeiler-Lehman test of isomorphism \cite{WL1968, XHLJ2019}, and thus naturally takes into account the labels of the nodes in the two graphs.
We fixed the number of kernel iterations to 5. We also fixed $T = 25$ for our algorithm. For each method and each train-test split, we used a separate 5-fold cross-validation procedure to tune the coefficient of error term $C$ over the set $\{0.1, 1, 10\}$ for training an independent SVM model on the training portion.
\color{black}
\begin{figure*}[t]
    \begin{subfigure}{}
           \resizebox{.3\textwidth}{!}{\input{ClassificationPlot0.5msrc_21c.tex}}
            \label{fig:Algorithms}

    \end{subfigure}%
    ~~

    \begin{subfigure}{}
           \resizebox{.3\textwidth}{!}{\input{ClassificationPlot0.5dhfr.tex}}
            \label{fig:Algorithms}

    \end{subfigure}%
    ~~
    \begin{subfigure}{}
          \resizebox{.3\textwidth}{!}{\input{ClassificationPlot0.5mutagenicity.tex}}
            \label{fig:Algorithms}

    \end{subfigure}%
    ~~
    \begin{subfigure}{}
          \resizebox{.3\textwidth}{!}{\input{time_msrc_21c.tex}}
            \label{fig:Algorithms}

    \end{subfigure}%
    ~~
    \begin{subfigure}{}
          \resizebox{.3\textwidth}{!}{\input{time_dhfr.tex}}
            \label{fig:Algorithms}

    \end{subfigure}%
    ~~
    \begin{subfigure}{}
          \resizebox{.3\textwidth}{!}{\input{time_mutagenicity.tex}}
            \label{fig:Algorithms}

    \end{subfigure}%

 \caption{{\bf Comparison on standard graph datasets}. The top row shows the average test accuracy and corresponding standard deviation for our method (OTC) and state-of-the-art baselines for different fractions of training data.
 The bottom row compares the corresponding compression times. Our method outperforms the other methods in terms of both accuracy and compression time.
 \label{fig:AlOu}}
\end{figure*}
Table \ref{tab:compare} summarizes the performance of different methods for each fraction of the data. Clearly, as the numbers in bold indicate, our method generally outperformed the other methods across the datasets. We note that on some datasets the discrepancy between the average test accuracy of two algorithms is massive for every fraction.
Further, as Fig. \ref{fig:AlOu} shows, OTC performed best  in terms of compression time as well. We emphasize that the discrepancy in compression times became quite stark for larger datasets (i.e., DHFR and Mutagenicity).
\begin{figure*}[t!]%
\hskip -0.5cm
\subfigure[Synthetic graph]{%
\label{fig:first}%
\includegraphics[width=1.9in, height=2in]{SyntheticOriginal.png}}%
~
\hskip -0.5cm
\subfigure[Compressed graph ($k=20$)]{%
\label{fig:second}%
\includegraphics[width=1.9in, height=2in]{Synthetic_20.png}}%
~
\hskip -0.5cm
\subfigure[Compressed graph ($k=15$)]{%
\label{fig:second}%
\includegraphics[width=1.9in, height=2in]{Synthetic_15.png}}%

\hskip -0.5cm
\subfigure[Compressed graph ($k=5$)]{%
\label{fig:third}%
\includegraphics[width=1.9in, height=2in]{Synthetic_5.png}}%
~
\hskip -0.5cm
\subfigure[Mutagenicity]{%
\label{fig:fourth}%
\includegraphics[width=2in, height=2in]{mutagenicity_sample.png}}%
~
\subfigure[MSRC-21C]{%
\label{fig:sixth}%
\includegraphics[width=1.8in, height=2in]{MSRC_21Csample.png}}
\caption{{\bf Visualizing compression on synthetic and real examples.} (a) A synthetic graph structured as a $4$-ary tree of depth $2$. The root $0$ is connected to its neighbors by edges having $c(e)=0.3$. All the other edges have either $c(e)=0.5$ (thickest) or $c(e)=0.1$ (lightest). The left out portions are shown in gray. (b) Leaf node 13, which is in the same subtree as three nodes with heavy edges 14-16, is the first to go.  (c) Proceeding further, 9 and 10 are left out followed by the remaining nodes (i.e. 5, 6,7) connected by light edges. (d) When the graph is compressed to 5 vertices, only the root and its neighbors remain despite bulkier subtrees, e.g. the one with node 4 and its neighbors, that are discarded. Thus, our method yields meaningful compression on this synthetic example. (e-f) Compressed structures pertaining to some sample graphs from real datasets that have some other interesting motifs. In each case, the compressed graph consists of red edges and the incident vertices, while the discarded parts are shown in gray. All the figures here are best viewed in color.
\label{fig:fig_visual}}
\end{figure*}
\subsection{Compressing synthetic and real examples}
We now describe our second set of experiments with both synthetic and real data to show that our method can be seeded with useful prior information toward preserving interesting patterns in the compressed structures. This flexibility in specifying the prior information makes our approach especially well-suited for downstream tasks, where domain knowledge is often available.

Fig. \ref{fig:fig_visual} demonstrates the effect of compressing a synthetic tree-structured graph. The penultimate level consists of four nodes, each of which has four child nodes as leaves. We introduce asymmetry with respect to the different nodes by specifying different combinations of $c(e)$ for edges $e$ between the leaf nodes and their parents: there are respectively one, two, three and four heavy edges (i.e. with $c(e) = 0.5$) from the internal nodes 1, 2, 3, and 4 to their children, i.e., the leaves in their subtree. As shown in the figure, our method adapts to the hierarchical structure with a change in the amount of compression from just one node to about three-fourths of the entire graph. We also show meaningful compression on some examples from real datasets. The bottom row of Fig. \ref{fig:fig_visual} shows two such examples, one each from Mutagenicity and MSRC-21C. For these graphs, we used the same specification for $c$ as in  section \ref{ClassifySection}. The example from Mutagenicity contains patterns such as rings and backbone structures that are ubiquitous in molecules and proteins. Likewise, the other example is a good representative of the MSRC-21C dataset from computer vision. Thus, our method encodes prior information, and provides fast and effective graph compression for downstream applications.

\section{Introduction}
Graphs are widely used to capture complex relational objects, from social interactions to molecular structures. Large, richly connected graphs can be, however, computationally unwieldy if used as-is, and spurious features present in the graphs that are unrelated to the task can be statistically distracting. A significant effort thus has been spent on developing methods for compressing or summarizing graphs towards graph {\em sketches} \cite{LV2018}. Beyond computational gains, these sketches take center stage in numerous tasks pertaining to graphs such as partitioning  (\cite{DGK2007, WXSW2014}), unraveling complex or multi-resolution structures (\cite{RB2003, SD2011, KTG2014, TMK2016}), obtaining coarse-grained diffusion maps (\cite{LL2006}), including neural convolutions (\cite{BZSL2014, DBV2016, SK2017}). State-of-the-art compression methods broadly fall into two categories: (a) sparsification (removing edges)  and (b) coarsening (merging vertices).  These methods measure spectral similarity between the original graph and a compressed representation in terms of a (inverse) Laplacian quadratic form \cite{RSB2011, CS2011, LB2012, SFV2016, DB2013}. Thus, albeit these methods approximately preserve the graph spectrum, e.g., \cite{LV2018}; they are oblivious to, and thus less effective for, downstream tasks such as classification that rely on labels or attributes of the nodes. Also, the key compression steps in these methods are, typically, either heuristic or detached from their original objective \cite{HG2019}.

We address these issues by taking a novel perspective that appeals to the theory of optimal transport \cite{V2008}, and develops its connections to minimum cost flow on graphs \cite{K2008, CMSV2017}. Specifically, we interpret graph compression as minimizing the transport cost from a fixed initial distribution supported on all vertices to an unknown target distribution whose size of support is limited by the amount of compression desired. Thus, the compressed graph in our case is a subgraph of the original graph, restricted to a subset of the vertices selected via the associated transport problem. The transport cost depends on the specified prior information such as importance of the nodes and their labels or attributes, and thus can be informed by the downstream task. Moreover, we take into account the underlying geometry toward the transport cost, unlike agnostic measures such as KL-divergence \cite{SRGB2016}.

There are several technical challenges that we must address. First, the standard notion of optimal transport on graphs is tailored to directed graphs where the transport cost decomposes as a directed flow along the edge orientations (\cite{ES2018}). To circumvent this limitation, we extend optimal transport on graphs to handle both directed and undirected edges, and derive a dual that directly measures the discrepancy between distributions on the vertices. As a result, we can also compress {\em mixed } graphs \cite{HKW1997, R2007, CDLS2007, BBCJY2015}.
The second challenge comes from the compression itself, enforced in our approach as sparse support of the target distribution.  Optimal transport is known to be computationally intensive, and almost all recent applications of OT in machine learning, e.g., \cite{ACB2017, CFHR2017, RCFT2019, FZMAP2015, AJJ2018, VCFTC2018} rely on entropy regularization \cite{C2013, BCCNP2015, S2015, GCPB2016, SDFCRB2018} for tractability.
However, entropy is not conducive to sparse solutions since it discourages the variables from ever becoming 0 \cite{ES2018}. In principle, one could consider convex alternatives such as enforcing $\ell_1$ penalty (e.g., \cite{T1996}). However, such methods require iterative tuning to find a solution that matches the desired support, and  require strong assumptions such as restricted eigenvalue, isometry, or nullspace conditions for recovery. Some of these issues were previously averted by introducing binary selection variables \cite{TTW2014, PWG2015} and using Boolean relaxations in the context of unconstrained real spaces (regression). However, they do not apply to our setting since the target distribution must reside in the simplex. We introduce {\em constrained} Boolean relaxations that are not only efficient, but also provide exactness certificates.

Our graph compression formulation also introduces new algorithmic challenges. For example, solving our sparsity controlled dual transport problem involves a new subproblem of projecting on the probability simplex $\Delta$ under a diagonal transformation. Specifically, let $D(\epsilon)$ be a diagonal matrix with the diagonal $\epsilon \in [0, 1]^d \setminus \{\boldsymbol{0}\}$. Then, for a given $\epsilon$, the problem is to find the projection $x \in \mathbb{R}^d$ of a given vector $y \in  \mathbb{R}^d$ such that $D(\epsilon) x \in \Delta$. This generalizes well-studied problem of Euclidean projection on the probability simplex (\cite{DSSC2008,WC2013, C2016}), recovered if each $\epsilon_i$ is set to 1. We provide an exact $O(d \log d)$ algorithm for solving this generalized projection. Our approach leads to convex-concave saddle point problems with fast convergence via methods such as Mirror Prox \cite{N2004}.

\textbf{Our contributions.} We propose an approach for graph compression based on optimal transport (OT). Specifically, we (1) extend OT to undirected and mixed graphs (section \ref{OTGeneral}), (2) introduce constrained Boolean relaxations for our dual OT problem, and provide exactness guarantees (section \ref{ConBool}) (3) generalize Euclidean projection onto simplex, and provide an efficient algorithm (section \ref{ConBool}), and (4) demonstrate that our algorithm outperforms state-of-the-art
compression methods, both in accuracy and compression time, on classifying graphs from standard real datasets. We also provide qualitative results that our approach provides meaningful compression in synthetic and real graphs (section \ref{Experiments}).

\iffalse

\section{Introduction}
Graphs model a variety of structured data, and thus find much use in machine learning and elsewhere. Often, these graphs are very large, which makes them impractical for several applications. Thus, compressing or coarsening them to get {\em sketches} or summaries is widely considered a central task in contemporary machine learning (\citet{LV2018}). Beyond the reasons of computational tractability, these sketches serve a predominant role in numerous tasks on graphs such as partitioning or clustering (\citet{DGK2007, WXSW2014}), unraveling complex structures, e.g., hierarchical (\citet{RB2003, SD2011}) or multiresolution (\citet{KTG2014, TMK2016}), obtaining coarse-grained diffusion maps (\citet{LL2006}), multiscale wavelets (\citet{ LNW2008, GNC2010, KTG2014}), or pyramids (\citet{SFV2016}), and performing convolutions in neural networks on graphs (\citet{BZSL2014, DBV2016, SK2017}).
Yet, much of the literature on graph compression is based on heuristics, and the need for theoretically sound methods cannot be overemphasized (\citet{LV2018}).  We combine  optimal transport with Boolean relaxations to bridge the gap between mathematical rigor and practice.

The notion of optimal transport \cite{V2008} is natural for comparing probability  distributions, and has been variously interpreted in multiple fields, e.g., as Mallows distance in statistics (\citet{M1972}) and minimum cost flow in graph theory (\citet{K2008, CMSV2017}). From a learning perspective, recent years have witnessed many applications of this paradigm, e.g., in adversarial learning (\citet{ACB2017}),
domain adaptation (\citet{CFHR2017}),
multi-label prediction (\citet{FZMAP2015}), and structure encoding (\citet{AJJ2018, VCFTC2018}). Many of these advances owe, in part, to entropy regularization that has led to computationally tractable algorithms (\citet{C2013, BCCNP2015}, \citet{S2015, GCPB2016, SDFCRB2018}).

We interpret graph compression as minimizing
the transport cost from a fixed initial distribution that is supported on all vertices to an unknown target distribution whose support is dictated by the extent of compression. Thus, we can naturally view the compressed graph as a subgraph of the original graph restricted to a subset of the vertices. However our perspective poses certain technical challenges. First, the standard notion of optimal transport
is tailored to directed graphs where the transport cost decomposes as a directed flow along the edge orientations (\citet{ES2018}). To circumvent this issue, we extend optimal transport on graphs to handle both directed and undirected edges, and  craft a dual that directly measures the discrepancy between distributions on the vertices. As a lateral benefit, besides directed and undirected graphs, we can also compress {\em mixed } graphs that have important applications in Bayesian inference and job shop scheduling (\citet{HKW1997, R2007, CDLS2007, BBCJY2015}).

Second, in order to accomplish compression, we need to enforce sparsity on support of the target distribution. In principle, sparsity could be induced by incorporating $\ell_1$ penalty, as in Lasso (\citet{T1996}) or Elastic Net (\cite{ZH2005}), however these methods often require extensive tuning to find a solution close to the desired support.
Therefore, to get a finer control over sparsity, we introduce binary variables \cite{TTW2014, PWG2015} and resort to the method of Boolean relaxations  to overcome the computational bottleneck due to binary constraints. A direct application is ruled out, however, since Boolean relaxations are known only for the unconstrained real space and do not apply to our setting where the variable of interest, being a distribution, must reside in the probability simplex.

Our treatment leads to an equivalent problem that requires solving a new subproblem of projecting on the probability simplex $\Delta$ under a diagonal transformation. Specifically, let $D(\epsilon)$ be a diagonal matrix with the diagonal $\epsilon \in [0, 1]^d \setminus \{\boldsymbol{0}\}$. Then, for a given $\epsilon$, the problem is to find the projection $x \in \mathbb{R}^d$ of a given vector $y \in  \mathbb{R}^d$ such that $D(\epsilon) x \in \Delta$. Thus, we generalize the well-studied problem of Euclidean projection on the probability simplex (\citet{DSSC2008,WC2013, C2016}), which is recovered when each component of $\epsilon$ is set to 1. We provide an exact $O(d \log d)$ algorithm for this generalized projection.
In principle, we could then relax our compression problem, and apply methods such as projected gradient descent directly. However, in order to leverage algorithms with provably fast convergence, such as Mirror Prox \cite{N2004}, we focus on a related problem that can be expressed in a convex-concave saddle point form. We specify conditions under which the relaxation of this problem is exact. To summarize, we make the following contributions.

\textbf{Our contributions.} We propose a principled framework for graph compression. Specifically, we (1) extend the scope of optimal transport (OT) to undirected and mixed graphs (section \ref{OTGeneral}), (2) introduce a dual characterization of the optimal transport distance on graphs (section \ref{DualChar}), (3) introduce constrained Boolean relaxations (section \ref{ConBool}), (4) introduce a new optimization problem that generalizes Euclidean projection on the probability simplex, and provide an efficient algorithm (section \ref{ConBool}), and (5)
demonstrate that our algorithm outperforms the state-of-the-art
{\em Randomized Edge Contraction} (REC) method that provably approximates the spectrum \cite{LV2018}, on the task of classifying graphs from standard real datasets. Moreover, we show that
our approach yields compressed graphs that preserve the essential structure in synthetic and real graphs (section \ref{Experiments}).

\fi

\section{Graph compression} \label{SecGraphCompress}
We view graph compression as the problem of minimizing the optimal transport distance from an initial distribution $\rho_0$ having full support on the vertices $V$ to a target distribution $\rho_1$ that is supported only on a subset $S_V(\rho_1)$ of $V$. The compressed subgraph is obtained by restricting the original graph to vertices in $S_V(\rho_1)$ and the incident edges. The initial distribution $\rho_0$ encodes any prior information. For instance, it might be taken as a stationary distribution of random walk on the graph. Likewise, the cost function $c$ encodes the preference for different edges. In particular, a high value of $c(e)$ would inhibit edge $e$ from being active. This flexibility allows our framework to inform compression based on the specifics of different downstream applications by getting to define $\rho_0$ and $c$ appropriately.

\subsection{Dual characterization of the transport distance} \label{DualChar}
Note that \eqref{UnWass} defines an optimization problem over edges. However, our perspective requires quantifying $W(\rho_0, \rho_1)$ as an optimization over the vertices. Fortunately, strong duality comes to our rescue. Let $c = (c(e), e \in E)$ be the column vector obtained by stacking the costs. The dual of \eqref{UnWass} is
\begin{eqnarray}
 \max_{\substack{\boldsymbol{0} \preceq y, \boldsymbol{0} \preceq z \\ - c ~\preceq~ F (y - z) \preceq  c}} & (y-z)^{\top}(\rho_1 - \rho_0),~~~~ \text{or equivalently},~~~  \displaystyle \max_{\substack{t \in \mathbb{R}^{|V|}\\ - c   ~\preceq Ft  \preceq  c}} ~~ t^{\top}(\rho_1 - \rho_0)~~. \label{UnWassDual}
 \end{eqnarray}
This alternative formulation of $W(\rho_0, \rho_1)$ in \eqref{UnWassDual} lets us define compression solely in terms of variables over vertices. Specifically, for a budget of at most $k$ vertices, we solve
\begin{eqnarray} \label{CompressOriginal}
\min_{\substack{\rho_1 \in \Delta(V)\\ ||\rho_1||_0 \leq k}}~~~ \max_{\substack{t \in \mathbb{R}^{|V|}\\ - c \preceq Ft  \preceq c}} \underbrace{t^{\top}(\rho_1 - \rho_0) + \dfrac{\lambda}{2} ||\rho_1||^2}_{\mathcal{L}_\lambda(\rho_1, t;\rho_0)} ~,&&
\end{eqnarray}
where $\lambda > 0$ is a regularization hyperparameter, and  $||\rho_1||_0$ is the number of vertices with positive mass under $\rho_1$, i.e., the cardinality of support set $S_V(\rho_1)$. The quadratic penalty is strongly convex in $\rho_1$, so as we shall see shortly, would help us leverage fast algorithms for a saddle point problem.
Note that a high value of $\lambda$ would encourage $\rho_1$ toward a uniform distribution. We favor this penalty over entropy, which is not conducive to sparse solutions since entropy would forbid $\rho_1$ from having zero mass at any vertex in the graph.

Our next result reveals the structure of optimal solution $\rho_1^*$ in \eqref{CompressOriginal}. Specifically, $\rho_1^*$ must be expressible as an affine function of $\rho_0$ and $F$. Moreover, the constraints on active edges are tight. This reaffirms our intuition that $\rho_1^*$ is obtained  from $\rho_0$ by transporting mass along a subset of the edges, i.e., the active edges. The remaining edges do not participate in the flow.

\begin{theorem} \label{Theorem2}
The optimal $\rho_1^*$ in \eqref{CompressOriginal} is of the form $\rho_1^* = \rho_0 + F^{\top}\eta~,$ where $\eta \in \mathbb{R}^{|E|}$.  Furthermore, for any active edge $e \in E$, we must have $Ft^*(e) \in \{c(e), - c(e)\}$.
\end{theorem}

\subsection{Constrained Boolean relaxations} \label{ConBool}
 The formulation \eqref{CompressOriginal} is non-convex due to the support constraint on $\rho_1$. Since recovery under $\ell_1$ based methods such as Lasso often requires extensive tuning, we resort to the method of Boolean relaxations that affords an explicit control much like the $\ell_0$ penalty. However, prior literature on Boolean relaxations is limited to variables that have no additional constraints beyond sparsity. Thus, in order to deal with the simplex constraints $\rho_1 \in \Delta(V)$, we introduce constrained Boolean relaxations. Specifically, we define the characteristic function $g_V(x) = 0 \mbox{ if }  x \in \Delta(V)$ and $\infty$ otherwise,
and move the non-sparsity constraints inside the objective. This lets us delegate the sparsity constraints to binary variables, which can be relaxed to $[0, 1]$. Using the definition of
$\mathcal{L}_\lambda$, we can write $\eqref{CompressOriginal}$ as
$$\min_{\substack{\rho_1 \in \mathbb{R}^{|V|}\\ ||\rho_1||_0 \leq k}}~~~ \max_{\substack{t \in \mathbb{R}^{|V|}\\ - c \preceq Ft  \preceq c}} \mathcal{L}_\lambda(\rho_1, t;\rho_0) ~+~ g_V(\rho_1) ~.$$
Denoting by $\odot$ the Hadamard (elementwise) product, and introducing  variables $\epsilon \in \{0, 1\}^{|V|}$, we get
\begin{eqnarray*}
\min_{\substack{\epsilon \in \{0, 1\}^{|V|}\\ ||\epsilon||_0 \leq k}} \min_{\rho_1 \in \mathbb{R}^{|V|}} ~~~ \max_{\substack{t \in \mathbb{R}^{|V|}\\ - c \preceq Ft  \preceq c}} \mathcal{L}_\lambda(\rho_1 \odot \epsilon, t;\rho_0) ~+~ g_V(\rho_1 \odot \epsilon) ~.
\end{eqnarray*}
Adjusting the characteristic term as a constraint, we have the following equivalent problem \begin{eqnarray} \label{EqForProj}
\min_{\substack{\epsilon \in \{0, 1\}^{|V|}\\ ||\epsilon||_0 \leq k}}~~~ \min_{\substack{\rho_1 \in \mathbb{R}^{|V|} \\ \rho_1 \odot \epsilon \in \Delta(V)}} \max_{\substack{t \in \mathbb{R}^{|V|}\\ - c \preceq Ft  \preceq c}} \mathcal{L}_\lambda(\rho_1 \odot \epsilon, t;\rho_0) ~.
\end{eqnarray}
\input{simplex.tex}

Theorem \ref{Theorem6} allows us to relax the problem \eqref{EqForProj}, and solve the relaxed problem efficiently since the projection steps on the other constraint sets can be solved by known methods \cite{BT2014, GDX2018}.
Specifically, since $\epsilon$ consists of only zeros and ones, $||\epsilon||_0 =  ||\epsilon||_1 = \epsilon^{\top}\boldsymbol{1}$ and $\epsilon \odot \epsilon = \epsilon$. So, we can write \eqref{EqForProj} as
\begin{eqnarray*}
\min_{\substack{\epsilon \in \mathcal{E}_{k}}}~~~ \min_{\substack{\rho_1 \in \mathbb{R}^{|V|} \\ \rho_1 \odot \epsilon \in \Delta(V)}} \max_{t \in \mathcal{T}_{F, c}} \mathcal{L}_\lambda(\rho_1 \odot \epsilon \odot \epsilon, t;\rho_0) ~,
\end{eqnarray*}
where we denote the constraints for $\epsilon$ and $t$ respectively by \begin{eqnarray} \label{TFCformula} \mathcal{E}_{k} & \triangleq  \{\epsilon \in \{0, 1\}^{|V|} ~|~ \epsilon^{\top}\boldsymbol{1} \leq k\}~,~~~ \text{and} ~~~ \mathcal{T}_{F, c} & \triangleq  \{t \in \mathbb{R}^{|V|} ~|~ - c \preceq Ft  \preceq c \}~.
\end{eqnarray}
We can thus eliminate $\epsilon$ from the regularization term via a change of variable $\rho_1 \odot \epsilon \to \tilde{\rho}_1$
\begin{eqnarray} \label{EqP1_past}
\min_{\substack{\epsilon \in \mathcal{E}_{k}}}~~~ \min_{\substack{\tilde{\rho}_1 \in \mathbb{R}^{|V|} \\ \tilde{\rho}_1 \odot \epsilon \in \Delta(V)}} \max_{t \in \mathcal{T}_{F, c}}~~ \mathcal{L}_0(\tilde{\rho}_1 \odot \epsilon, t;\rho_0) + \dfrac{\lambda}{2} ||\tilde{\rho}_1||^2~~.
\end{eqnarray}

We note that \eqref{EqP1_past} is a mixed-integer program due to constraints $\mathcal{E}_{k}$, and thus hard to solve. Nonetheless, we can relax the hard binary constraints on the coordinates of $\epsilon$ to  $[0, 1]$ intervals to obtain a saddle point formulation with a strongly convex term, and solve the relaxation efficiently, e.g., via customized versions of methods such as Mirror Prox \cite{N2004}, Accelerated Gradient Descent \cite{N2005}, or Primal-Dual Hybrid Gradient \cite{CP2011}.
 \input{MP_algorithm.tex}
An attractive property of our relaxation is that if the solution $\hat{\epsilon}$ from the relaxed problem is integral then $\hat{\epsilon}$ must be optimal for the non-relaxed hard problem \eqref{EqP1_past}, and so the original formulation \eqref{CompressOriginal}. We now pin down the  necessary and sufficient conditions for optimality of $\hat{\epsilon}$.
\begin{theorem} \label{RelaxationExactness}
Let $S_V({\rho_1^*}) = \{v \in V ~|~ \rho_{1}^* (v) > 0 \}$ be the support of optimal $\rho_1$ in the original formulation \eqref{CompressOriginal}. Let the indicator $I_{S_V^*} \in \{0, 1\}^{|V|}$ be such that $I_{S_V^*}(v) = 1$ if $v \in S_V(\rho_1^*)$ and 0 otherwise.
The relaxation of \eqref{EqP1_past} is guaranteed to recover $S_V({\rho_1^*})$   if and only if there exists a tuple $(\gamma, \hat{t}, \hat{\nu}, \hat{\zeta}) \in \mathbb{R}_+ \times \mathbb{R}^{|V|} \times \mathbb{R}_{+}^{|V|} \times \mathbb{R}$ such that the following holds for all vertices $v \in V$,
\begin{equation} \label{RelaxOptConditions}
|\hat{t}(v) - \hat{\nu}(v) + \hat{\zeta}| ~~~~ \begin{cases} >~ \gamma \qquad {\rm if }~~ v \in S_V(\rho_1^*)\\ <~ \gamma \qquad {\rm if }~~ v \notin S_V(\rho_1^*) \end{cases}, ~~~ \text{where}
\end{equation}
\begin{eqnarray} \label{Opthats}
 (\hat{t}, \hat{\nu}, \hat{\zeta}) ~\in~ \arg \max_{t \in \mathcal{T}_{F, c}} \max_{\nu \in \mathbb{R}_+^{|V|}} \max_{\zeta \in \mathbb{R}} ~~- \left(~\dfrac{1}{2\lambda} \big|\big|(t - \nu + \zeta \boldsymbol{1})\odot I_{S_V^*}\big|\big|^2 ~+~ t^{\top} \rho_0 ~+~ \zeta \right)~.
\end{eqnarray}
\end{theorem}
For some applications projecting on the simplex, as required by \eqref{EqP1_past}, may be an expensive operation. We can invoke the minimax theorem to swap the order of $\tilde{\rho}_1$ and $t$,  and proceed with a Lagrangian dual to eliminate $\tilde{\rho}_1$ at the expense of introducing a scalar variable. Thus, effectively, we can replace the projection on simplex by a one-dimensional search. We state this
equivalent formulation below.

\begin{theorem} \label{DualForm}
Problem \eqref{EqP1_past}, and thus the original formulation \eqref{CompressOriginal}, is equivalent to
 \begin{eqnarray} \label{Dual2}
\displaystyle \min_{\epsilon \in  \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}\\\zeta \in \mathbb{R}}}   \underbrace{- \dfrac{1}{2\lambda} \sum_{v: t(v) \leq -\zeta} \left(\epsilon(v) (t(v) + \zeta)^2 ~+~ 2 \lambda t(v) \rho_{0}(v) \right) ~-~ \sum_{v: t(v) > -\zeta} t(v) \rho_{0}(v) -  \zeta}_{\psi_{\rho_0}(\epsilon, t, \zeta)}~
\end{eqnarray}
\end{theorem}

We present a customized Mirror Prox procedure in Algorithm \ref{MPPrimal1}. The  projections ${\rm Proj}_{\mathcal{T}_{F, c}}$ and ${\rm Proj}_{\tilde{\mathcal{E}}_{k}}$  can be computed efficiently, respectively, by \cite{BT2014} and \cite{GDX2018}.  We round the solution $\hat{\epsilon} \in [0, 1]^{|V|}$ returned by the algorithm to have at most $k$ vertices as the estimated support for the target distribution $\rho_1$ if $\hat{\epsilon}$ is not integral.  The compressed graph is taken to be the subgraph spanned by these vertices.

\section{Supplementary Material}
We provide here proofs of all the results from the main text. \\ \\
\textbf{Proof of Theorem \ref{Theorem1}}
\begin{proof}
We will prove the result by contradiction.

Suppose there is some $\hat{e} \in E$ such that the optimal solution assigns $J^+(\hat{e}) > 0$ and $J^-(\hat{e}) > 0$. Then we note that
$$a ~\triangleq~ \min\{J^+(\hat{e}), J^-(\hat{e})\} > 0~.$$
Consider an alternate solution $(\tilde{J}^+, \tilde{J}^-)$ such that $\forall~ e  \in E$,
$$
\tilde{J}^+(e) ~=~
\begin{cases}
J^+(e) - a & \mbox{ if }  e = \hat{e}\\
J^+(e) & \mbox{ if }  e \in E \setminus \{\hat{e}\}\\
\end{cases}~,
$$
$$
\tilde{J}^-(e) ~=~
\begin{cases}
J^-(e) - a & \mbox{ if }  e = \hat{e}\\
J^-(e) & \mbox{ if }  e \in E \setminus \{\hat{e}\}\\
\end{cases}~.
$$
\noindent Clearly, $(\tilde{J}^+, \tilde{J}^-)$ is feasible for \eqref{UnWass}. Moreover, it achieves a lower value of the objective than the  optimal solution $(J^+, J^-)$. Therefore,  $(J^+, J^-)$ cannot be optimal.
\end{proof}

\textbf{Proof of Theorem \ref{Theorem2}}
\begin{proof}
We introduce non-negative Lagrangian vectors $\alpha$ and $\beta$, respectively, for the constraints $Ft \preceq c$ and $-c \preceq Ft$. We consider the terms in the objective that depend on $t$
$$g(t) = t^{\top}(\rho_1 - \rho_0)  + \alpha^{\top} (Ft-c) - \beta^{\top} (Ft+c)~.$$
The gradient $\nabla g(t)$ must vanish at optimality, so
$$\rho_1^* - \rho_0 + F^{\top}(\alpha - \beta)~=~ \boldsymbol{0}~.$$
The first part of the theorem follows immediately by defining $\eta = \beta - \alpha$. A closer look at \eqref{UnWass} reveals that  $\eta = J^{-} - J^+$ is, in fact, the net flow along the edges $e^-$ from \eqref{UnWass}.

Now, we prove the second part. By definition, in order for an edge $e$ to be active, at least one of $e^+$ and $e^-$ must be active, i.e., we must have $J^+(e) + J^-(e) > 0$. On the other hand, Theorem \ref{Theorem1} implies that at least one of $J^+(e)$ and $J^-(e)$ is 0 for each $e \in E$ in the optimal solution. Combining these facts, we have that for any active edge $e$, exactly one of   $e^+$ and $e^-$ is active, i.e.,  exactly one of the inequalities $J^+(e) > 0$ and $J^-(e) > 0$ must hold. This immediately implies, by complementary slackness, that exactly one of $\alpha(e)$ or $\beta(e)$ is 0. Thus, for any active edge $e$, either the lower bound or the upper bound on $Ft^*(e)$ in the constraints $- c(e) \leq Ft^*(e)  \leq  c(e)$ must become tight. Therefore, we must have $Ft^*(e) \in \{\pm c(e)\}$.
 \end{proof}

\textbf{Proof of Theorem \ref{Theorem6}}
\begin{proof}
Note that since at least one coordinate of $\epsilon$ is strictly greater than 0, the feasible region is non-empty, and consequently, a unique projection exists. We introduce variables $\alpha \in \mathbb{R}$ and $\beta \in \mathbb{R}_+^d$, and form the Lagrangian
$$L(x, \alpha, \beta) ~=~   \dfrac{1}{2} ||x - y||^2 - \alpha ((x \odot \epsilon)^{\top} \boldsymbol{1} ~-~1) ~-~ \beta^{\top} (x \odot \epsilon)~.$$
We now write the KKT conditions for the optimal solution $x$. For each $j \in [d]$, we must have
\begin{eqnarray*}
x_j - y_j - \alpha \epsilon_j - \beta_j \epsilon_j & = & ~~0 \\
\epsilon_j x_j & \geq & ~~0 \\
\beta_j & \geq & ~~0 \\
\epsilon_j x_j \beta_j & = & ~~0~.\\
\text {Additionally}, \qquad \sum_{j=1}^d \epsilon_j x_j & = & ~~1~.
\end{eqnarray*}
Clearly, for $j \in [d] \triangleq \{1, 2, \ldots, d\}, \epsilon_j = 0 \implies x_j = y_j$. Therefore, without loss of generality we assume in the rest of the proof that $\epsilon_j > 0$ for all $j$.  Then we can immediately simplify the KKT conditions to
\begin{eqnarray}
x_j - y_j - \alpha \epsilon_j - \beta_j \epsilon_j & = & ~~0 \label{KKT1} \\
x_j & \geq & ~~0 \label{KKT2} \\
\beta_j & \geq & ~~0~~~.  \label{KKT3}\\
x_j \beta_j & = & ~~0~ \label{KKT4} \\
\sum_{j=1}^d \epsilon_j x_j & = & ~~1~ \label{KKT5}
\end{eqnarray}
We note that $x_j > 0 \xRightarrow[{}]{\eqref{KKT4}} \beta_j = 0 \xRightarrow[{}]{\eqref{KKT1}} y_j + \alpha \epsilon_j > 0 \xRightarrow[{}]{\epsilon_j > 0} y_j/\epsilon_j > -\alpha~,$
whereas
\begin{eqnarray*}
x_j = 0 \xRightarrow[{}]{\eqref{KKT1}} y_j + \alpha \epsilon_j = -\beta_j \epsilon_j  \xRightarrow[{\epsilon_j > 0}]{\eqref{KKT3}} y_j + \alpha \epsilon_j \leq 0  \xRightarrow[{}]{\epsilon_j > 0} y_j/\epsilon_j \leq -\alpha ~.
\end{eqnarray*}
This shows that the zero coordinates $x_j$ correspond to smaller values of $y_j/\epsilon_j$. Thus, we can sort the indices $j$ in non-increasing order based on the ratio $y_j/\epsilon_j$, reorder $x$ according to the sorted indices, and find an index $\ell \in [d]$ such that
$x_j > 0$ for $j \in [\ell]$ and 0 for $\ell < j \leq d$.  Without loss of generality, we therefore assume that
\begin{eqnarray} x_1 \geq x_2 \ldots \geq x_{\ell} > 0 = x_{\ell + 1} \ldots = x_{d}~, \text{ and } \nonumber \\  y_1/\epsilon_1 \geq y_2/\epsilon_2 \ldots \geq y_d/\epsilon_d~.  \label{sortedorder} \end{eqnarray}
We then have from \eqref{KKT5} that
\begin{eqnarray}  1 ~=~ \sum_{j=1}^d \epsilon_j x_j ~=~ \sum_{j=1}^{\ell} \epsilon_j x_j ~=~  \sum_{j=1}^{\ell}  \epsilon_j (y_j + \alpha \epsilon_j) \nonumber \\ \implies \alpha = \dfrac{1 - \sum_{j=1}^{\ell}  \epsilon_j y_j}{ \sum_{j=1}^{\ell} \epsilon_j^2}~~. \label{Lang_alpha}
\end{eqnarray}
Thus, our task essentially boils down to finding the number of positive coordinates $\ell$.  We now show that
$$\ell = \max\left\{j \in [d] ~ \bigg| ~ y_j + \epsilon_j \dfrac{(1 - \sum_{i=1}^j \epsilon_i y_i)}{\sum_{i=1}^j \epsilon_i^2} > 0\right\}~.$$
First consider $j < \ell$. Then $y_j/\epsilon_{j} > -\alpha$ for $j \in [\ell]$. Noting that $\epsilon_j > 0$ for all $j$ and using \eqref{Lang_alpha}, we must have
\begin{eqnarray*}
&&  y_j + \epsilon_j \dfrac{(1 - \sum_{i=1}^j \epsilon_i  y_i)}{\sum_{i=1}^j \epsilon_i^2} \\ & = & \dfrac{\epsilon_j}{\sum_{i=1}^j \epsilon_i^2} \left(y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + 1 - \sum_{i=1}^j \epsilon_i y_i \right)\\
&& \\
&&\noindent \text{which has the same sign as}  \\
&  & y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + 1 - \sum_{i=1}^j \epsilon_i y_i \\
& = & y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + \sum_{i=j+1}^{\ell} \epsilon_i y_i  + 1 - \sum_{i=1}^{\ell} \epsilon_i y_i \\
& = & y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + \sum_{i=j+1}^{\ell} \epsilon_i y_i  + \alpha \sum_{i=1}^{\ell} \epsilon_i^2 ~\qquad  \\
& = &  \left(\dfrac{y_j}{\epsilon_j} + \alpha\right) \sum_{i=1}^j \epsilon_i^2  + \sum_{i=j+1}^{\ell} \epsilon_i ^2\left(\dfrac{y_i}{\epsilon_i}  + \alpha \right) \\
& > & 0~.
\end{eqnarray*}
Now consider $j = \ell$. Since $y_{\ell}/\epsilon_{\ell} > -\alpha$ and $\epsilon_{\ell} > 0$, we have $y_\ell + \alpha \epsilon_\ell > 0$. Thus
\begin{eqnarray*}
y_j + \epsilon_j \dfrac{(1 - \sum_{i=1}^j \epsilon_i y_i)}{\sum_{i=1}^j \epsilon_i^2}  & = & y_{\ell} + \epsilon_{\ell} \dfrac{(1 - \sum_{i=1}^{\ell} \epsilon_i y_i)}{\sum_{i=1}^{\ell} \epsilon_i^2} \\ & = &y_{\ell} +  \alpha \epsilon_{\ell} ~>~ 0~.
\end{eqnarray*}
Finally, we consider $\ell < j \leq d$. We note that
\begin{eqnarray*}
&& y_j + \epsilon_j \dfrac{(1 - \sum_{i=1}^j \epsilon_i y_i)}{\sum_{i=1}^j \epsilon_i^2}\\ & = & \dfrac{\epsilon_j}{\sum_{i=1}^j \epsilon_i^2} \left(y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + 1 - \sum_{i=1}^j \epsilon_i y_i \right)~,\\
&& \\
&&\noindent \text{which has the same sign as}  \\
&& y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + 1 - \sum_{i=1}^j \epsilon_i y_i \\
& = & y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + 1 - \sum_{i=1}^\ell \epsilon_i y_i - \sum_{i=\ell + 1}^j \epsilon_i y_i \\
& = & y_j \dfrac{\sum_{i=1}^j \epsilon_i^2}{\epsilon_j}  + \alpha \sum_{i=1}^\ell \epsilon_i^2 - \sum_{i=\ell + 1}^j \epsilon_i y_i ~\qquad \\% (\text{using } \eqref{Lang_alpha})\\
& = & \left(\dfrac{y_j}{\epsilon_j} + \alpha\right) \sum_{i=1}^\ell \epsilon_i^2  + \sum_{i=\ell+1}^{j}  \epsilon_i ^2 \left(\dfrac{y_j}{\epsilon_j} - \dfrac{y_i}{\epsilon_i} \right)~,\\
& \leq & 0~,
\end{eqnarray*}
by leveraging the sorted property in \eqref{sortedorder} and the fact that $y_j/\epsilon_{j}  \leq -\alpha$ for $j \in [\ell]$.

\noindent Therefore, we have shown that $y_j + \epsilon_j \dfrac{(1 - \sum_{i=1}^j \epsilon_i y_i)}{\sum_{i=1}^j \epsilon_i^2} > 0$ for all $j \in [\ell]$, and at most 0 for $\ell < j \leq d$. Algorithm  \ref{ProjectWS} implements this procedure, and that proves its correctness. The $O(d \log d)$ time complexity is due to the cost of sorting the indices $j \in [d]$ based on $y_j/\epsilon_j$.
\end{proof}

\textbf{Proof of Theorem \ref{RelaxationExactness}}
\begin{proof}
Recall the formulation \eqref{EqP1_past}:
$$\min_{\substack{\epsilon \in \mathcal{E}_{k} \\ \tilde{\rho_1} \odot \epsilon \in \Delta(V)}} \max_{t \in \mathcal{T}_{F, c}} \underbrace{t^{\top}(\tilde{\rho}_1 \odot \epsilon - \rho_0) ~+~ \dfrac{\lambda}{2} ||\tilde{\rho}_1||^2}_{\phi(\epsilon, t, \tilde{\rho}_1)}~.$$
Making the constraints $\mathcal{E}_k$ explicit,   we get
\begin{eqnarray} \label{ExactEq1} \min_{\substack{\epsilon \in \{0, 1\}^{|V|} \\ \epsilon^{\top}\boldsymbol{1} \leq k}}~ \left(\min_{\substack{\tilde{\rho}_1 \in \mathbb{R}^{|V|}\\ \tilde{\rho}_1 \odot \epsilon \in \Delta(V)}} ~ \max_{t \in \mathcal{T}_{F, c}}~~ \phi(\epsilon, t, \tilde{\rho}_1)   \right)~.
\end{eqnarray}
Note that for any fixed $\epsilon$ (a) $\{\tilde{\rho}_1 \in \mathbb{R}^{|V|}~|~ (\tilde{\rho_1} \odot \epsilon) \in \Delta(V) \}$ is convex, and  $\mathcal{T}_{F, c}$ is convex and compact, (b)  $\phi(\epsilon, t, \tilde{\rho}_1)$ is continuous, and (c) for every fixed $t$,  $\phi(\epsilon, t, \cdot)$ is convex in $\tilde{\rho}_1$; while for every fixed $\tilde{\rho}_1$, $\phi(\epsilon, \cdot, \tilde{\rho}_1)$ is linear (thus concave) in $t$. Therefore, invoking the Sion's minimax theorem \cite{S1958}, we can swap the order of $\min$ and $\max$ within the parentheses in \eqref{ExactEq1}, and obtain
\begin{eqnarray} \label{EqChange}
\min_{\substack{\epsilon \in \{0, 1\}^{|V|} \\ \epsilon^{\top}\boldsymbol{1} \leq k}}~~~ \left(\max_{t \in \mathcal{T}_{F, c}} \min_{\substack{\tilde{\rho}_1 \in \mathbb{R}^{|V|}\\ \tilde{\rho}_1 \odot \epsilon \in \Delta(V)}} \phi(\epsilon, t, \tilde{\rho}_1)   \right)~.
\end{eqnarray}
We introduce Lagrangian variables $\nu \in \mathbb{R}^{|V|}_+$ and $\zeta \in \mathbb{R}$, respectively, for the simplex constraints (a) $\boldsymbol{0} \preceq \tilde{\rho}_1 \odot \epsilon $ and (b) $(\tilde{\rho}_1 \odot \epsilon)^{\top} \boldsymbol{1} = 1$ to get
\begin{equation}  \label{PhiWithRho}
\Phi(\epsilon, t, \tilde{\rho}_1, \nu, \zeta) \triangleq \phi(\epsilon, t, \tilde{\rho}_1) + \zeta((\tilde{\rho}_1 \odot \epsilon)^{\top} \boldsymbol{1} - 1) - \nu^{\top}(\tilde{\rho}_1 \odot \epsilon)~~.
\end{equation}
Applying the optimality conditions, we note for any fixed pair $(\epsilon, t)$, the corresponding optimal $\tilde{\rho}_1$  must satisfy
\begin{equation*}
\partial_{\tilde{\rho}_1} ~ \Phi(\epsilon, t, \tilde{\rho}_1, \nu, \zeta)  ~=~ 0~,
\end{equation*}
whereby
\begin{equation} \label{hatrho}
\tilde{\rho}_1 ~=~  -~\left(\dfrac{(t - \nu) \odot \epsilon  + \zeta \epsilon}{\lambda}\right)~.
\end{equation}
Plugging in $\tilde{\rho}_1$ from \eqref{hatrho} into  \eqref{PhiWithRho}, we thus have the following equivalent dual formulation for \eqref{EqChange}
\begin{eqnarray*}
\min_{\substack{\epsilon \in \{0, 1\}^{|V|} \\ \epsilon^{\top}\boldsymbol{1} \leq k}}~~\max_{t \in \mathcal{T}_{F, c}} ~~\max_{\nu \in \mathbb{R}^{|V|}_+, \zeta \in \mathbb{R}} ~~\mathcal{M}(\epsilon, t, \nu, \zeta) ~,
\end{eqnarray*}
where
\begin{equation} \label{LagDual}
\mathcal{M}(\epsilon, t, \nu, \zeta) =    \dfrac{-1}{2\lambda} ||(t - \nu + \zeta \boldsymbol{1})\odot \epsilon||^2 - t^{\top} \rho_0 - \zeta~.
\end{equation}
Invoking the first order convex optimality condition for constrained optimization, the $\hat{\epsilon}$ obtained from relaxation of \eqref{EqP1_past} is optimal if and only if
 \begin{equation} \label{PartialE}
 \boldsymbol{0}  ~\in~  \left\{\partial_{\epsilon} \underbrace{\max_{t \in \mathcal{T}_{F, c}} ~~\max_{\nu \in \mathbb{R}^{|V|}_+, \zeta \in \mathbb{R}} ~~\mathcal{M}(\epsilon, t, \nu, \zeta)}_{(A)} ~+~ \mathbb{N}\right\},
 \end{equation}
 where $\mathbb{N}$ is the normal cone of the relaxed constraints
 $$\tilde{\mathcal{E}}_k =
 \left\{\epsilon \in [0, 1]^{|V|} ~\bigg|~ \epsilon^{\top} \boldsymbol{1} \leq k\right\}~.$$

Now we note that for any vector $x$, we can write $x \odot \epsilon =  D(\epsilon) x$, where $D(\epsilon)$ is the diagonal matrix corresponding to $\epsilon$.  Also, since $\epsilon \in \{0, 1\}^{|V|}$, we get $D(\epsilon)^{\top} D(\epsilon) = D(\epsilon)$.
Thus, for any $x$, we have

$$||x \odot \epsilon||^2 =  ||D(\epsilon) x||^2 = (D(\epsilon) x)^{\top} D(\epsilon) x = x^{\top} D(\epsilon)^{\top} D(\epsilon) x = x^{\top}D(\epsilon)x~.$$

In particular, we can simplify $||(t - \nu + \zeta \boldsymbol{1}) \odot \epsilon||^2$ in \eqref{LagDual} when we set $x$ to $t - \nu + \zeta \boldsymbol{1}$. The theorem statement then follows immediately from \eqref{PartialE} by representing $\mathbb{N}$ at the integral point $\epsilon^*$ and leveraging the non-negative dual parameter associated with  the constraint $\epsilon^{\top} \boldsymbol{1} \leq k$.
\end{proof}

\textbf{Proof of Theorem \ref{DualForm}}
\begin{proof}
We will use the shorthand $\tilde{\rho}_{1v}$ for $\tilde{\rho}_1(v)$, and likewise for indexing $t$, $\nu$, and $\epsilon$. Using \eqref{hatrho},
\begin{eqnarray*}
\tilde{\rho}_1 & =   -~\left(\dfrac{(t - \nu) \odot \epsilon  + \zeta \epsilon}{\lambda}\right) & =  -~\left(\dfrac{t - \nu + \zeta \boldsymbol{1}}{\lambda}\right) \odot \epsilon~.
\end{eqnarray*}
Therefore,
\begin{equation}
\label{rhoforKKT}
\tilde{\rho}_1 \odot \epsilon  =  -~\left(\dfrac{t - \nu + \zeta \boldsymbol{1}}{\lambda}\right) \odot \epsilon \odot \epsilon  ~~=~` -~\left(\dfrac{t - \nu + \zeta \boldsymbol{1}}{\lambda}\right) \odot \epsilon~~~ =~~ \tilde{\rho}_1~,
\end{equation}
since $\epsilon \in \{0, 1\}^{|V|}$.  We write one of the KKT conditions for optimality
\begin{eqnarray*}
 \tilde{\rho}_1 \odot \epsilon \odot \nu & = & \tilde{\rho}_1 \odot \nu ~~=~~ \boldsymbol{0}~.
\end{eqnarray*}
We consider the different cases. Note that for $v \in V$, using \eqref{rhoforKKT}, we have
\begin{equation} \label{rho1condition1}
 \tilde{\rho}_{1v}  ~>~ 0  \implies  \nu_v = 0 \implies \tilde{\rho}_{1v} ~=~ - \dfrac{(t_v + \zeta) \epsilon_v }{\lambda}~,
 \end{equation}
\begin{equation} \label{rho1condition2} \tilde{\rho}_{1v}  ~=~ 0  \implies
(t_v - \nu_v + \zeta)\epsilon_v ~=~ 0 \implies \nu_v \epsilon_v ~=~  (t_v + \zeta) \epsilon_v~.\end{equation}
But since $\nu_v \geq 0$, and $\epsilon_v \in \{0, 1\}$, we note that $\nu_v \epsilon_v \geq 0$. Then, by \eqref{rho1condition2}, we have
\begin{equation} \label{rho1condition2a} \nu_v \epsilon_v \geq 0 \implies  - \dfrac{(t_v + \zeta) \epsilon_v }{\lambda} ~\leq~ 0 ~ =~ \tilde{\rho}_{1v}~. \end{equation}
Combining \eqref{rho1condition1} and \eqref{rho1condition2a}, we can write
\begin{eqnarray} \label{rho1final}
\tilde{\rho}_{1v} &=&  \max\left\{-\dfrac{(t_v + \zeta) \epsilon_v}{\lambda}, ~0\right\}~ ~=~
\dfrac{\epsilon_v}{\lambda} \max\left\{-(t_v + \zeta), ~0\right\}~,
\end{eqnarray}
since $\epsilon_v \geq 0$ for all $v \in V$ and $\lambda > 0$.
Therefore, we get $\tilde{\rho}_1 = \dfrac{\epsilon}{\lambda} \odot r_+$, where
$r ~=~ -~(t + \zeta \boldsymbol{1})$, and $r_+$ is computed by setting the negative coordinates of $r$ to 0.\\

Moreover, since $\tilde{\rho}_1 \odot \nu ~=~ \boldsymbol{0}$, we can eliminate $\nu$ from \eqref{PhiWithRho} and write \eqref{ExactEq1} as
\begin{eqnarray*}
\min_{\epsilon \in \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~ t^{\top}(\tilde{\rho}_1 - \rho_0) + \dfrac{\lambda}{2} ||\tilde{\rho}_1||^2 + \zeta(\tilde{\rho}_1^{\top}\boldsymbol{1} - 1)
\end{eqnarray*}
Substituting for $\tilde{\rho}_1$ from \eqref{rho1final},  we obtain the following equivalent problem
\begin{eqnarray*}
& \displaystyle \min_{\epsilon \in \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~  - \dfrac{r^{\top}}{\lambda}(\epsilon \odot r_+)
~+~ \dfrac{1}{2\lambda} r_+^{\top}(\epsilon \odot r_+) ~-~ t^{\top}\rho_0 ~-~ \zeta~,\\
& = \displaystyle \min_{\epsilon \in \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~  \dfrac{-1}{2\lambda} \epsilon^{\top} \left(r_+ \odot \left(2r - r_+\right) \right) - t^{\top} \rho_0 - \zeta~,\\
\end{eqnarray*}
which can be written as
\begin{eqnarray*}
& \displaystyle \min_{\epsilon \in  \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~  - \dfrac{1}{2\lambda} \sum_{v: r_v \geq 0} \epsilon_v r_v^2 - t^{\top} \rho_0 - \zeta~\\
= & \displaystyle \min_{\epsilon \in  \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~  - \dfrac{1}{2\lambda} \sum_{v: t_v \leq -\zeta} \epsilon_v r_v^2 - t^{\top} \rho_0 - \zeta~\\
= & \displaystyle \min_{\epsilon \in  \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~  - \dfrac{1}{2\lambda} \sum_{v: t_v \leq -\zeta} \epsilon_v (t_v + \zeta)^2 - t^{\top} \rho_0 - \zeta~\\
= & \displaystyle \min_{\epsilon \in  \mathcal{E}_{k}}~\max_{\substack{t \in \mathcal{T}_{F, c}}}\max_{\zeta \in \mathbb{R}}  ~~~~  - \dfrac{1}{2\lambda} \sum_{v: t_v \leq -\zeta} \left(\epsilon_v (t_v + \zeta)^2 ~+~ 2 \lambda t_v \rho_{0, v} \right) ~-~ \sum_{v: t_v > -\zeta} t_v \rho_{0,v} -  \zeta~.\\
\end{eqnarray*}

\end{proof}

redpajama_set_name: RedPajamaArXiv


text:
Q: What is wrong when trying to find how much bytes sent(uploaded) so far? I have an event where i'm doing a progress report to backgroundworker1 progresschanged event:
mbSent = ((double)obj.BytesSent) / (1 << 20);
stringProgressReport[2] = mbSent.ToString();
backgroundWorker1.ReportProgress(0, 2);

mbSent is a global double var. And stringProgressReport is string array var.
I have also a var type long called totalBytes that is the file i'm uploading size.
But i'm not using this var here maybe i should.
Then in the backgroundworker progresschanged event i did:
label5.Text = stringProgressReport[2];

The problem is in label5 i see it just counting like int numbers 1,2,3,4,5...when it's getting to 25 in the end i see the number 25 become 25.34543356767 and the totalBytes size is something else at all it's 26.7898 or something.
Something wrong with this: mbSent = ((double)obj.BytesSent) / (1 << 20);
Maybe i need to sue here somehow the totalBytes(The file total size) ?
This is how i'm calculating the totalBytes:
long totalBytes = 0;
        private void button3_Click(object sender, EventArgs e)
        {
            OpenFileDialog openFileDialog1 = new OpenFileDialog();

            openFileDialog1.InitialDirectory = "c:\\";
            openFileDialog1.Filter = "mp4 files (*.mp4)|*.mp4|All files (*.*)|*.*";

            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            {
                FileNameToUpload = openFileDialog1.FileName;
                FileName = openFileDialog1.FileName;

                using (FileStream fileStream = File.OpenRead(FileName))
                {
                    totalBytes = fileStream.Length;
                }
            }
        }

A: There's nothing wrong with your calculation.  If you don't want to see any decimals in your output either don't convert mbSent to a double or use a format string in your ToString() call.
Either:
mbSent = obj.BytesSent / (1 << 20);

Or:
stringProgressReport[2] = mbSent.ToString("D");

And  when totalBytes is 26,789,800, mbSent will be 25.45874420 is completely correct.  20,789,800 / 1,048,576 = 25.45874420.

redpajama_set_name: RedPajamaStackExchange


text:
Searcy County Death Records Index 1914-1923
Return to the Searcy County page
Actkinson, Thomas 12/08/1920
Albert, Lester 11/13/1920
Alexander, Daniel 04/20/1914
Allen, Nora 03/08/1916
Alumbough, 10/23/1914
Anderson, Thomas 07/24/1916
Arms, A J 02/27/1920
Arnold, Alford W 11/21/1917
Arnold, Edma 10/30/1916
Arnold, Guy 05/14/1922
Ashley, Mary S 06/07/1922
Atterberry, Lehman 05/27/1923
Atterberry, Raymon 05/23/1923
Bagland, Ezra W 07/24/1919
Bain, Jack 08/28/1922
Baker, Albert N 04/18/1914
Baker, Drusie E 06/20/1914
Baker, James 03/31/1922
Baker, Jas R 08/20/1918
Baker, John Ril 01/23/1915
Baker, Lendia 10/05/1920
Baker, Leonder J 11/22/1915
Baker, Lorenza D 12/24/1921
Baker, Mary E 09/01/1920
Baker, Nellie May 04/16/1914
Baker, Thelma 06/22/1914
Baker, Troy 11/24/1921
Baker, Wm Has 03/19/1916
Balbinot, F M 09/19/1915
Ballard, Marpa 09/02/1916
Bankam, Dora 09/13/1915
Barnes, Birch 10/19/1915
Barnes, Edgar L 06/03/1921
Barnes, George W 02/12/1923
Barnes, Houston 06/16/1914
Barnes, James B 06/17/1914
Barnes, Mildred 01/07/1918
Barnes, Tenn H 09/29/1914
Barnett, Davis 03/03/1915
Barnett, William H 10/25/1915
Bearden, Troy 02/10/1920
Beavers, Ona 06/04/1922
Beavrs, Barton 02/01/1921
Beck, 07/03/1914
Bell, Roda A 12/19/1918
Bellamy, Lindsay 07/31/1916
Belt, William H 01/31/1917
Bethany, E C 03/22/1922
Betheny, Lorene 01/11/1919
Bexley, Shelley 11/27/1915
Bigley, Bertha Ann 10/24/1915
Bigley, Iva Pea 10/10/1915
Bilyen, Minnie Car 03/27/1914
Bird, Coy 02/02/1916
Blackburn, Clara L 05/13/1916
Blackwell, Harvey F 11/27/1920
Blair, Arther Sil 04/03/1914
Blair, Caroline 09/03/1916
Blair, Elzina C 02/13/1922
Blair, Eva 01/07/1918
Blair, Gideon Dal 12/26/1923
Boggan, W A 05/09/1914
Bohanan, Nancy 06/25/1914
Bolen, Daniel L 04/10/1915
Boyd, Belle 01/22/1916
Boyd, Claudia F 02/06/1920
Boyd, Louise T 02/24/1920
Boyd, Sarah 04/08/1919
Bozman, Bula 11/02/1917
Bradley, 07/13/1916
Bradley, Nancie E 02/02/1916
Bradley, Otie 09/14/1914
Bradshaw, Robert L 03/05/1917
Bradshow, Polly Ann 05/24/1919
Brannum, Minnie Pea 12/08/1918
Branscum, J E 02/19/1923
Branum, Helen 12/23/1918
Bratton, Bunyion Lee 01/31/1919
Bratton, James 03/20/1920
Bratton, John 11/23/1923
Bratton, Mary A 09/20/1920
Bratton, Olevia D 03/12/1916
Bratton, Samuel J 07/16/1918
Brauscum, Locky 10/30/1921
Brazzeal, Nancy Ann 04/25/1914
Brewer, 07/30/1915
Bridges, Alice 08/24/1920
Bridges, Fay 08/21/1920
Bridges, Harris W 08/08/1916
Bridges, Sarah C 01/07/1916
Brittin, Lucy E 01/20/1923
Brittingham, A B 01/20/1916
Britwell, 08/29/1916
Brooks, Floyd 02/27/1914
Brown, 05/02/1916
Brown, Alford F 08/18/1914
Brown, David Cro 07/09/1914
Brown, David M 09/07/1920
Brown, May 05/05/1915
Brumlow, Thomas J 04/15/1919
Bryan, Homer 09/23/1915
Bryan, Lottie 12/15/1918
Bryant, James J 06/10/1923
Bryant, Joseph L 09/29/1922
Buckhart, 01/07/1915
Burnes, Joseph 05/31/1917
Burns, Edgar Cec 10/21/1919
Burton, Belle M 09/18/1917
Burton, Charles How 05/21/1921
Butham, 10/29/1922
Byron, Rath 06/17/1916
Cable, Julius S 09/17/1923
Cable, Malissie 04/09/1918
Cain, Winnie B 06/20/1917
Caldwell, Walter Gar 07/02/1916
Calleyhand, Charles A 04/27/1915
Cames, Randolf W 06/09/1915
Campbell, Andy B 06/20/1918
Campbell, Charles Hen 05/22/1914
Campbell, Jewel 03/09/1918
Campbell, Lola Mar 07/22/1914
Campbell, Murrell 06/03/1916
Canada, Dorkey 11/09/1921
Cannon, Courtney 03/31/1920
Capland, Otto 08/07/1922
Carter, Billie Jea 01/03/1923
Casey, Isabelle 09/05/1917
Cash, Dollie 03/27/1916
Cash, Eliza 01/21/1916
Cash, John M 12/05/1915
Cash, Leoda 12/09/1914
Cassey, Flosa D 05/20/1915
Catherly, James H 05/01/1918
Caulson, Samuel P 01/27/1919
Caulson, William L 05/15/1916
Causey, Nora 09/04/1914
Chandler, 10/18/1914
Chandler, Herbert L 05/26/1915
Clark, 02/26/1923
Clark, Sessi 03/13/1914
Clayton, Edward 06/30/1915
Clemens, Susan E 10/05/1922
Coker, Mansul C 05/04/1920
Colston, Arka D 09/28/1916
Compton, Martin L 12/25/1914
Cooley, Nella 10/20/1918
Cooper, Ada 09/05/1916
Cooper, Alta 01/12/1917
Cooper, Cora B 02/25/1922
Cooper, Loftin 07/15/1915
Cooper, Otto 12/17/1920
Corder, Mary 08/17/1915
Corn, William M 05/12/1916
Cossell, Nancy E 02/19/1918
Cotton, Cecil 10/15/1918
Cotton, Samuel B 10/28/1920
Cotton, Silas 11/23/1918
Cotton, Tallie 09/20/1922
Cotton, Tollie 09/20/1916
Coulson, Clifton E 11/09/1917
Cox, Ruth 06/28/1921
Crawley, Raymond 08/03/1916
Curtis, Harry 01/13/1917
Cypert, James L 11/29/1923
Cypert, Madge 06/21/1915
Cypert, R 03/15/1916
Cyport, Ruie May 03/15/1916
Daenport, Floyd Sea 04/16/1917
Damlif, Sarah 07/04/1923
Daniel, Grace 08/22/1914
Daniel, H Pag 06/19/1915
Daniel, John R 12/13/1915
Daniel, Madge 02/12/1914
Daniels, Dick 02/22/1923
Daniels, Hattie 01/08/1916
Daugherty, Lucy 08/05/1916
Davenport, Miranda 07/04/1915
Davenport, Raymon 11/16/1914
Davidson, Pearl M 07/06/1917
Davis, David 08/30/1914
Davis, Eveline 08/28/1916
Davis, George G 12/13/1922
Davis, Manerva E 05/08/1915
Davis, Myrtle 12/21/1919
Dean, Dan S 07/23/1919
Dean, Logan 11/13/1917
Deckey, John T 04/04/1922
Delk, James A 10/21/1916
Dennis, F M 02/28/1914
Depriest, Mary Jan 10/11/1922
Dickens, Mary P 11/11/1915
Dickey, Harold 08/31/1914
Dodd, John 04/04/1923
Dodson, L A 06/21/1915
Dodson, Margaret J 08/16/1915
Dorain, Francis C 08/08/1916
Draper, Bonney Eli 09/04/1920
Drewry, 11/23/1923
Drewry, Barzelia 01/02/1918
Drewry, Francis M 08/19/1914
Drewry, Tabitha J 03/19/1922
Duncan, Bernell 09/26/1916
Duncan, Faris 04/12/1918
Duncan, Fillman C 09/23/1915
Duncan, James 01/01/1915
Duncan, Lathana 03/29/1920
Duprist, 01/18/1922
Duvall, Minnie 08/15/1917
Dye, Emma J 04/28/1917
Dyer, William P 06/10/1914
Eatherly, George J 01/29/1921
Eatherly, James H 05/01/1918
Ellis, Dora Max 05/27/1919
Estes, Zona Bel 04/08/1919
Evans, Keron Fra 01/19/1916
Evans, Thomas J 12/04/1920
Ezell, Clyde 06/30/1917
Ezell, Ethel May 06/18/1917
Farris, Richard 06/01/1921
Faught, John W 02/23/1918
Fields, Walter H 02/05/1920
Findley, Paul Eug 03/26/1914
Firestone, Martha A 02/20/1923
Firestone, T J 08/03/1920
Floid, Ida And 03/30/1923
Ford, 02/26/1916
Ford, David B 05/21/1916
Foster, George W 05/27/1920
Foster, Mandy 09/22/1920
Fought, Rhoda M 05/17/1923
Fout, Charlie 03/15/1920
Fowler, Dora V 12/31/1914
Fowler, Eugene 02/26/1914
Fox, Ellen 05/23/1916
Fox, Ellers 05/23/1922
Fox, George W 08/14/1916
Fox, Ruba 11/11/1918
Fuller, Marshall L 12/29/1920
Fye, Charles 11/28/1918
Garner, Lucy 03/02/1915
Garner, Vernon 02/19/1917
Garrett, Williams 02/07/1914
Garrison, May 10/17/1916
Garver, Goldie M 03/07/1920
Gary, George F 04/06/1915
Gary, Martha E 04/26/1922
Gary, Sydney C 12/10/1915
Gasaway, Nelli 03/03/1923
Gates, Martha 03/31/1918
Gates, Martha A 08/14/1920
Gatt, Mary E 01/21/1921
George, Cora 11/15/1915
Gerten, Ada Mar 04/19/1914
Gibson, Hiram 02/02/1923
Gibson, Willie 06/01/1916
Gilbert, John S 12/06/1917
Giles, Jessie Gre 11/23/1914
Gladen, Frank D 02/12/1916
Gladen, Jane 01/01/1915
Glines, Lillian C 11/27/1914
Goddard, 04/26/1915
Goff, Martha A 08/12/1921
Good, Abe 01/22/1923
Goodman, James K 10/25/1918
Goodman, Lawson 02/14/1923
Graham, Lindsey L 04/02/1923
Graham, William Tho 09/12/1920
Gray, Harriet 04/19/1914
Gray, Paul 12/27/1916
Gray, Sarah 02/26/1923
Green, 12/20/1914
Greenhaw, Floy O 11/08/1917
Greenhaw, John 03/26/1914
Greenhown, Charley 06/12/1915
Griffin, 01/08/1915
Griffin, Edith 08/12/1919
Griffin, Fanny 06/14/1916
Griffin, Mary P 11/13/1923
Griffin, Nancy 04/27/1920
Griffin, Richard D 07/25/1922
Griffin, Sallie Bel 11/09/1921
Griffin, William W 12/07/1923
Grinder, George 03/24/1915
Gruner, 11/26/1915
Gurmon, Jim A 11/09/1919
Gurnon, Hughey L 12/03/1919
Gustin, Beatrix 04/12/1916
Guthrie, Mable C 06/21/1914
Hale, John T 01/16/1917
Hallabaugh, Monroe 11/24/1918
Hallabaugh, Neely R 11/05/1918
Halsted, John Fra 03/10/1920
Hammock, James G 06/02/1923
Hammon, Russell 04/13/1915
Hammonds, Lettie Jan 09/23/1916
Hampton, Benjamin F 01/09/1917
Hankins, Robert Abr 05/17/1915
Hardin, Sarah B 09/06/1916
Harding, Hazel 03/12/1914
Harness, Mandy 02/27/1919
Harris, Claudice 10/17/1914
Harris, David C 01/19/1917
Harrison, Mabel 11/20/1922
Harton, 05/29/1916
Harton, Isaac W 09/30/1914
Hatchett, Columbus 10/22/1918
Hattenhour, Harry H 07/29/1922
Helmick, Arthur Lee 02/21/1917
Henderson, 10/22/1916
Henderson, Elnora 04/07/1916
Hendrix, 04/01/1915
Henley, Blaine 08/12/1921
Henley, Greenber Sea 11/17/1916
Henley, James A 02/23/1923
Henley, James R 07/25/1923
Hennessee, Roy Lee 07/20/1917
Henry, 05/11/1915
Henry, Lou 11/17/1918
Henry, Martha 11/30/1918
Henry, Phineas 09/22/1919
Henry, Sam 12/02/1918
Henslay, Grace M 08/29/1923
Hensley, Ada 06/20/1920
Hensley, Benjamin W 09/18/1921
Hensley, Drama 10/22/1914
Hensley, Porter 01/03/1920
Hensley, Porter J 06/04/1914
Henson, James 03/07/1914
Herron, Minarva 09/25/1914
Hickman, Martha 03/13/1919
Hightower, Annie C 08/09/1919
Hill, Everett 06/03/1917
Hill, Lillian 06/01/1917
Hill, Mildred 02/08/1918
Hilton, Veria 10/16/1918
Hodges, Lorenzo D 03/21/1917
Hogue, John 01/18/1918
Hogue, Lucille 11/16/1918
Holiman, Dan W 11/19/1922
Hollabaugh, Johnnie 02/26/1919
Holland, 04/24/1923
Holland, Nancy A 01/04/1918
Hollis, J C 12/05/1921
Hollobough, Francis 06/29/1916
Holsted, Clifford 04/25/1922
Holsted, James 01/29/1915
Hopkins, 02/03/1922
Hopkins, Alta G 03/10/1920
Horn, C A 01/28/1922
Horton, Andy 12/02/1922
Horton, F H 11/19/1923
Horton, Odus R 02/13/1921
House, Elizabet 01/29/1923
House, Troy 09/03/1921
Huckabee, John R 05/28/1917
Huckabee, Ora 01/16/1920
Hunley, Lawson 06/14/1916
Hurley, Nancy M 02/24/1916
Hurst, Francis M 06/16/1915
Isaacs, Ulyseses 08/05/1915
Jackson, Lonza 08/11/1914
Jackson, Nora 02/18/1923
Jackson, Robert 05/18/1916
Jacobson, R 05/18/1922
James, Dudley W 06/29/1915
Jameson, John F 01/01/1917
Janis, Mary E 03/24/1914
Jarrett, A L 12/04/1923
Jarrett, James M 04/08/1915
Jerome, William 02/05/1915
Johnson, Ralph 10/07/1921
Johnson, Rebecca H 02/12/1914
Johnson, Roy 09/12/1916
Johnson, Thomas 01/17/1919
Johnson, Zackiara Tay 12/18/1918
Jones, Darsel 03/10/1915
Jones, Millis 11/29/1915
Jones, Travis 01/15/1916
Jones, Walter Haf 11/06/1915
Keeling, David H 08/20/1916
Keeling, Elijah 07/11/1916
Kees, Mary 07/31/1916
Kelley, 01/15/1915
Kelley, Eliza 08/27/1916
Kelley, William J 06/12/1914
Kelly, Eliza 08/27/1916
Kembrough, R S 04/16/1915
Kemp, Estlee 09/24/1923
Kemp, Margret E 08/03/1923
Kile, Ervin 10/18/1919
Killian, Rosco 02/20/1920
Kimbell, John 08/22/1914
Kimbrell, Ella 07/04/1916
King, John T 03/27/1918
Knight, Warder T 11/05/1915
Kuykendall, Elizabet 04/15/1916
Laman, Serrenni 07/24/1915
Lamont, V P 08/22/1920
Lane, Francis 08/12/1917
Lane, Jefferso 03/17/1923
Lasater, Lolie L 08/24/1916
Latham, Fay 09/02/1914
Lathern, December 05/05/1919
Lathern, Morrilto 05/06/1919
Lay, Carl 06/24/1916
Lay, Jane Ann 04/04/1916
Lay, Louisana 03/03/1916
Lay, Napoleon A 04/29/1915
Lay, Sanford 04/22/1916
Lay, Thomas 01/01/1916
Lay, Troy 06/10/1916
Lay, William 04/14/1916
Ledbetter, Brooks 07/31/1917
Leonard, Mammie 12/06/1918
Leslie, 12/23/1919
Leslie, Russell 07/16/1918
Lewis, Andrew 03/31/1915
Lewis, Omer Bel 02/29/1920
Lewis, Ritchard 05/01/1916
Lilly, Elizabet H 11/15/1921
Lon, 05/19/1916
Long, Abraham 01/09/1918
Long, Elizabet E 10/08/1917
Long, Louis 12/05/1914
Louis, John S 04/12/1918
Lovell, 10/30/1919
Lowe, H V 01/31/1921
Loyd, 06/19/1914
Loyd, Jewell J 03/16/1920
Loyd, Lee Ota 04/25/1914
Loyd, Mollie 06/21/1914
Lucy, Clarice N 08/07/1916
Lucy, Hanna C 04/28/1918
Luma, James L 01/23/1918
Luna, George Was 06/05/1921
Lunsford, Norah E 10/24/1918
Luttrell, Franklin 11/16/1919
Luttrell, Joyce 10/30/1920
Mahon, Delbert 10/12/1919
Mahon, Fountain E 09/28/1921
Mahungra, Martha Ann 08/25/1919
Mainord, N J 06/03/1914
Man, James 03/17/1916
Manes, Maude J 02/17/1916
Maniard, Corine 10/06/1914
Manns, William 03/14/1914
Marlin, Dan 12/13/1923
Marshall, 07/15/1920
Marshall, Alexande 05/25/1921
Martain, Mildred 11/19/1922
Martin, Corneliu T 10/12/1921
Martin, Dallas E 09/03/1916
Martin, Della F 05/03/1920
Martin, Nellie May 07/12/1914
Martin, Sarah M 01/18/1915
Martindale, Mary I 05/09/1919
Massey, 02/06/1923
Massey, Richard L 12/08/1918
Matchett, F M 02/19/1923
Maxwell, Jultis 10/01/1916
Mays, Troy 11/19/1919
McAlister, Effie 02/23/1917
McClain, Mattie 09/08/1915
McCling, Jesse H 01/29/1915
McClung, Jesse H 01/29/1915
McCoy, Ervell V 05/31/1921
McCutchen, Angus J 12/24/1915
McCutchen, Aquillon E 01/27/1915
McCutchen, Sarah D 11/16/1914
McCutchen, Susan Tes 05/15/1914
McCutchen, Willis C 12/07/1914
McCutchens, Emily 04/24/1922
McCutcheons, G W 02/22/1923
McCuthen, Vereline 10/25/1915
McDaniel, Mary 12/23/1917
McDaniels, Arthur 07/14/1916
McElroy, 01/10/1917
McIver, Cowy 02/01/1916
McIver, Nellie B 06/25/1918
McKiney, George A 01/02/1923
McKinney, William 11/05/1915
McNinch, Hearl 08/31/1920
McNutt, Leona 08/09/1919
McSherry, Earnest 01/14/1915
Meeler, Dexter H 08/23/1915
Middleton, Liza 02/02/1920
Mills, Guffrey Esk 03/07/1914
Mills, John 07/13/1922
Minner, Henry A 05/05/1920
Misener, Bertha 10/04/1916
Moody, Bonnie 05/11/1915
Moody, Hazel D 11/30/1918
Moore, Gertie M 02/22/1920
Moore, L J 02/03/1920
Moore, Lydia Mer 07/14/1918
Moore, Mary F 05/01/1920
Moore, Winfield S 02/22/1918
Morris, J C 03/02/1922
Morris, James E 07/30/1915
Morrison, Millie 04/23/1917
Motley, John W 01/20/1922
Murry, James Wil 05/12/1915
Myer, Truman 11/25/1914
Napier, W H 05/11/1914
Nash, Mary E 03/14/1917
Nation, Raymond L 06/13/1922
Neaves, Daniel V 10/05/1921
Nelson, Ida L 04/13/1923
Newberry, Henry 02/13/1920
Newton, Rufus D 04/24/1914
Nichles, Paul 09/18/1916
Nichols, Missouri 07/20/1914
Nichols, Sarah 08/12/1917
Nollan, Tom 01/13/1922
Oldham, Ellen 03/26/1920
Oldham, William 03/26/1920
Oldham, Wilmer 03/24/1920
Oliver, Julia A 08/31/1919
Onan, Robert 10/21/1917
Oneal, Donna E 12/30/1922
Oneal, Lina A 04/06/1920
Oran, Willie D 10/10/1917
Orr, James T 12/28/1923
Owens, Craton 07/24/1919
Packard, Roy 09/15/1916
Page, Henry 11/19/1921
Palmer, Bertha Smi 12/08/1918
Palmer, Celia May 10/28/1918
Parker, C L 02/29/1916
Parks, Vernon 03/23/1922
Patterson, Elsia Ann 11/25/1918
Patterson, Sarah 12/30/1920
Patterson, Saraha G 09/27/1915
Perry, John J 12/15/1918
Perry, Lella 10/31/1915
Perry, Martha L 03/29/1915
Peters, Glenn H 07/30/1915
Peterson, Inez Bel 11/25/1918
Phillips, Leanard B 08/20/1918
Phillips, Leonard B 08/20/1918
Phillips, Willie M 02/16/1915
Pierce, J M 06/11/1917
Plant, Berthel 08/28/1914
Plant, Mary Ann 12/07/1916
Plumlee, W C 11/17/1922
Pogue, James 04/05/1922
Polk, Sarah Sik 01/17/1915
Powers, 07/17/1918
Pratt, G A 08/21/1915
Pratt, Mary Din 10/23/1919
Price, Ada Bel 11/17/1923
Price, Leda L 09/12/1919
Price, Viola 06/15/1918
Pruett, Solomon 05/27/1917
Pyron, 06/21/1916
Quillian, Josephin 05/14/1917
Ragland, Annie 04/11/1915
Ragland, Blanch 04/17/1922
Ragland, Ezra W 07/24/1919
Ragland, Jesse B 07/27/1916
Rains, Bulea 03/18/1918
Rains, Daphna 06/28/1917
Rains, Harrison 05/08/1923
Rains, Lila 11/19/1921
Rains, Lula 09/01/1917
Ramsey, Annie 09/21/1922
Ramsey, John W 04/12/1921
Ramsey, Mary F 05/02/1918
Ramsey, R 02/25/1920
Ratchford, Opal 05/08/1921
Ray, 01/06/1921
Reaves, 05/18/1914
Redwine, Cora E 12/07/1918
Reece, Ben R 10/11/1918
Reece, Samuel 01/12/1916
Reed, Flora 11/30/1918
Reed, Nora 08/05/1914
Reetert, James L 07/21/1919
Reeves, Nancy 07/29/1914
Reid, Garvin B 03/16/1920
Renfro, 01/01/1918
Renfro, Joseph 06/22/1914
Renfro, Stella 11/16/1917
Renfroe, Lena 10/27/1915
Renfroe, Silas 12/15/1918
Reynolds, Jack And 02/02/1915
Richardson, John 05/16/1917
Richardson, Maryn W 06/10/1914
Richardson, Nan P 07/01/1915
Richardson, Ona 03/05/1923
Riggan, W H 10/12/1922
Roberts, Bertha 08/12/1920
Roberts, J W 08/18/1918
Robertson, Bruce V 11/05/1920
Robertson, F A 04/07/1914
Robinson, Lillie 05/02/1916
Rodabaugh, Charley 07/29/1922
Roger, Calvin L 09/07/1916
Rogers, Dalph 05/25/1921
Rogers, Irving Dal 11/16/1921
Rogers, Ralph 05/25/1921
Roper, Lee Roy 09/28/1923
Rose, Ida E 05/07/1915
Rose, Millie M 10/20/1914
Rose, Virginia B 12/25/1923
Ross, Justen G 05/11/1916
Rotzell, Alf 03/06/1916
Rowden, Sadie 06/25/1917
Ruff, Earle 08/02/1914
Ruff, Edith 12/11/1918
Ruff, James D 11/07/1922
Russell, Albert C 11/16/1921
Russell, Elizabet J 06/08/1921
Russell, Martha A 08/13/1921
Sanders, Addie 09/11/1921
Sanders, Katie 11/17/1915
Sanders, Manerva 10/22/1918
Sanders, Samuel 06/18/1916
Sanders, Samuel N 01/18/1916
Sauage, David 06/23/1915
Savage, David 06/23/1915
Sawyer, Leita May 10/26/1918
Schlitt, Flora 09/12/1914
Schueneman, August 03/15/1920
Scott, Dotha 04/13/1916
Scott, Elvin 01/04/1918
Scott, Frank D 11/12/1918
Scott, John R 06/14/1917
Scott, Loisa 04/15/1921
Scott, Marshall C 06/30/1923
Scott, Marvin Len 10/02/1914
Scott, Otha 03/21/1916
Seaton, Eideth Lee 04/13/1914
Seavert, Morgan 10/14/1919
Seay, W H 06/07/1914
Shipman, Bessie A 05/30/1921
Shipman, Hazel 11/07/1918
Shipman, James E 08/21/1916
Show, Ardell 09/08/1921
Simmemon, David E 11/13/1915
Simmons, Emma 03/11/1914
Simms, Orian Alf 07/27/1917
Sisne, Veneva C 01/09/1923
Smathers, Elza T 02/25/1922
Smith, Blair 05/31/1917
Smith, Debbie 10/23/1922
Smith, Grace 08/01/1922
Smith, Jackson 04/20/1916
Smith, James L 02/28/1916
Smith, Malinda J 12/31/1923
Smith, Sarah 01/04/1917
Smithers, Elisie R 08/02/1916
Smithers, Gutherie L 08/07/1919
Smithson, 03/19/1923
Smothers, Nellie F 05/06/1914
Smothers, Thomas Jef 05/27/1914
Smythson, Roda 11/09/1920
Snow, Francis 06/30/1918
Southard, Claude Wil 01/14/1920
Spurlock, David 04/20/1915
Steel, William 07/26/1915
Stephenson, Jane 11/07/1915
Stephenson, Margaret 05/27/1918
Stephenson, Roy 09/26/1916
Stephenson, Utawh 09/11/1921
Stewart, John 10/06/1916
Sticker, Claude 11/19/1919
Stickler, Alva 04/23/1915
Still, George Ett 02/04/1918
Still, Steven J 02/06/1918
Stockton, Georgia Ann 09/09/1920
Stone, Claborn 08/17/1918
Stricker, Alva 03/23/1915
Stricker, Claudie 10/17/1919
Strickland, M 05/03/1916
Sullins, Avis O 03/06/1917
Sunber, Henry H 05/08/1914
Sutterfeed, Henry 03/16/1922
Sutterfeed, Lilie 04/15/1923
Sutterfield, A L 04/17/1921
Sutterfield, Green Ber 05/26/1916
Sutterfield, Lois R 08/04/1917
Sutterfield, Loise 10/17/1918
Sutterfield, Martha Ann 02/27/1914
Sutterfield, Olis 11/11/1914
Sutterfield, T 07/02/1922
Swinston, 11/18/1916
Swope, 10/04/1916
Sybert, Etta May 02/07/1916
Talley, Nora M 11/06/1920
Tayler, Lois A 06/20/1917
Taylor, Albert S 11/05/1918
Taylor, Arizella May 08/13/1916
Taylor, Edgar 11/20/1921
Taylor, Henry 10/01/1914
Taylor, Henry All 06/09/1915
Taylor, Jane 11/22/1918
Taylor, Kate 06/08/1921
Taylor, Louisa J 12/16/1919
Taylor, Lowell 10/29/1915
Taylor, Marguret 11/16/1917
Taylor, Mary S 11/16/1915
Taylor, Maud L 05/29/1916
Taylor, Mildred B 01/29/1916
Taylor, Minnie 11/21/1918
Taylor, O E 02/21/1922
Taylor, Paton 01/07/1915
Taylor, Richard M 05/11/1914
Taylor, Ural 05/25/1916
Taylor, Vada 01/10/1921
Thacker, Eliza 09/12/1915
Thacker, John H 10/26/1922
Thomas, Benjamin P 10/28/1914
Thomas, Bertie 01/08/1917
Thomas, Edward R 10/04/1918
Thomas, William D 02/20/1923
Thomas, Willie B 11/04/1916
Thompson, Dewey 08/17/1919
Thompson, Raymond R 12/15/1918
Thurman, Louis 08/26/1915
Tiller, Jim 03/21/1922
Tilley, Jasper 07/15/1923
Tilley, Mary C 05/03/1921
Tilley, Ula 03/08/1914
Tomlinson, Clarence 08/03/1921
Trammel, Arthur Jam 11/10/1918
Trammel, John F 11/07/1918
Trammell, George 07/17/1920
Tramwell, John 08/10/1919
Treat, 01/01/1919
Treat, Gennett Hel 04/23/1921
Treat, Hellen I 09/08/1921
Treat, Mary 12/30/1920
Treat, Minervia 03/23/1918
Treat, Thomas 01/07/1923
Treece, Helen V 01/31/1918
Treece, Margrare 10/26/1922
Truce, Jewel 05/06/1916
Tumbleson, Ollie 09/08/1915
Turner, Hawier E 09/02/1915
Turner, John G 03/30/1918
Turner, Nancy L 01/22/1923
Turney, Flossie 10/17/1915
Turney, Wallis 02/15/1922
Turney, William L 11/30/1916
Twincy, Joseph 07/22/1914
Tyler, Peter A 01/30/1915
Tyler, W B 08/16/1914
Vanmeeter, Martha J 06/10/1914
Vaughn, Andrew 01/27/1920
Vaughn, Dorah G 02/15/1919
Vaughn, George M 02/18/1919
Vernerable, Dottie 06/27/1916
Vick, Clintie 08/13/1916
Vick, Wilse 09/28/1915
Vickers, Reffie 12/08/1922
Wade, John H 10/26/1917
Wade, Mary Jan 03/02/1919
Wadkins, Dora 07/13/1916
Waldon, Mable 02/06/1915
Walker, Hattie 11/16/1915
Wallace, J C 03/01/1916
Wallis, Wilson 03/04/1923
Walls, Minnie 03/19/1914
Walters, Henry 03/17/1917
Waltman, Mattie 08/11/1915
Waltman, William 09/02/1917
Walton, Eula 06/22/1917
Ward, 01/15/1921
Ward, Carson D 03/18/1922
Watkins, Allie 05/18/1914
Watts, Adie 01/23/1917
Watts, Alphey 01/20/1920
Watts, Bertha B 07/31/1921
Watts, Cynthia 03/14/1915
Watts, Elmer 10/23/1914
Watts, James A 07/20/1920
Watts, Jasper N 10/20/1923
Watts, L V 07/25/1915
Watts, Nilrica 02/17/1915
Watts, Samuel Hou 01/15/1918
Watts, Ulas 01/26/1920
Watts, Ura 02/06/1914
Watts, Victor 01/24/1915
Webb, 07/07/1916
Webb, Julia 03/29/1917
Webb, Levy 12/10/1918
Welch, E 07/01/1915
Wellman, Thelma Rut 11/04/1914
Wells, Rachel 03/07/1915
West, Alfred A 02/16/1920
West, Mary Jan 05/30/1920
White, Bernell 10/26/1921
White, Betsey Ann 11/09/1914
White, Helen 02/10/1916
Whitlow, Beth 02/11/1918
Whitlow, Clyde 05/15/1917
Whitlow, Milton J 04/15/1917
Whittington, John 01/24/1922
Wilcox, 01/01/1916
Wilcox, J C 08/22/1914
Wilcox, Mary C 10/07/1917
Wildrick, Amelia A 06/22/1916
Wilkey, Gladys A 02/14/1914
Wilkins, Ladelle 12/18/1915
Willhelm, John 06/23/1920
Willhelm, Mammie 01/27/1919
Willheln, 05/07/1915
Williams, Luther 01/13/1916
Williams, Robbie R 05/10/1918
Williams, Sofa 02/16/1916
Wilson, 08/10/1915
Wilson, Carrieth 10/16/1920
Wilson, Margeret 01/31/1919
Wilson, Virginia L 04/06/1919
Winburne, Casper B 12/12/1918
Winnie, E F 06/22/1916
Winters, Alice 05/20/1923
Withers, Nathan A 09/01/1916
Woodard, Alfred 07/30/1916
Woodard, Soockey 03/02/1919
Woodcock, Henry H 06/27/1923
Wortman, Auda D 12/20/1914
Wortman, Laura M 04/13/1915
Wortman, Roxie 04/16/1918
Wrinkles, L E 09/02/1919
Wrinkles, M 05/28/1917
Wyatt, Floyd S 08/07/1914
Wyatt, Nute 05/20/1914
Wyatt, William A 03/09/1916
Yarbeary, Algarine 10/29/1914
Yarbeary, Bennrel 10/25/1914
Yelverton, Harriet E 05/24/1920
Young, John J 04/11/1917
Young, Sarah J 06/27/1918

redpajama_set_name: RedPajamaCommonCrawl


text:
Vermont leading US in GMO labeling campaign
Vermont could likely be the first state in the country to require labels on genetically modified foods, under a bill approved by both legislative chambers and favored by the governor.
April 24, 2014, 12:56 AM UTC / Source: The Associated Press
By DAVE GRAM
The House voted 114-30 on Wednesday to support the bill, which would require the GMO labels on produce and processed foods and which carries a maximum civil penalty for violators of $1,000 per day per product.
The Senate previously approved the measure, and Gov. Peter Shumlin said he plans to sign it into law. With his signature, the requirements would take effect July 1, 2016, giving food producers time to comply.
Shumlin hailed Wednesday's vote and said he looked forward to signing the bill.
"I am proud of Vermont for being the first state in the nation to ensure that Vermonters will know what is in their food," he said in a statement.
Twenty-nine other states this year and last have proposed bills to require GMO labeling, according to the National Conference of State Legislatures. Two other New England states have passed laws to require GMO labeling but the legislation only takes effect when neighboring states also approve the requirement.
Amid health and environmental concerns over GMO foods, several activist groups lobbied for the Vermont bill and stoked fervor among the public. But the Washington-based Grocery Manufacturers Association sharply criticized the measure, saying that growing GMO food reduces pesticide and water use on the farm and can help feed a growing world population.
Under the bill, GMO labeling would not be required of restaurants, and retailers would not be liable for noncompliance concerning the labeling of processed foods. The civil penalty for "false certification" — $1,000 per day per product — would apply to the general product, not each individual item or package within that category.
Some lawmakers said they were voting for the measure in accordance with their constituents' demands but with trepidation because of the prospects of a legal challenge.
"It's the right thing to do, and to let some big corporation hold us hostage (by threatening to sue) is not OK," Rep. Johannah Leddy Donovan, D-Burlington, said.
The bill includes a $1.5 million fund, to be used to implement the law and provide legal defense against lawsuits expected to be brought by food and biotech industries. If Vermont loses a lawsuit and is forced to pay the plaintiffs' legal costs, the expense could rise to $5 million to $8 million, the state attorney general's office has estimated.
The Grocery Manufacturers' statement called the Vermont bill "legally suspect at best," and said it would consider filing suit. Karen Batra, a spokeswoman for the Biotechnology Industry Organization, declined to comment on whether Vermont should expect to be taken to court if the governor signs the GMO law.
If a Vermont law takes effect ahead of other states, it would mark another instance when the state was a first. Vermont was first to ban slavery, first to allow non-property-owners to vote and first to pass same-sex marriage without a court telling it to do so.
But its record of successfully defending laws that challenge powerful interests is mixed. The state lost a federal court fight over the Legislature's efforts to close Vermont's lone nuclear plant and lost a campaign to require labeling of dairy products from cows treated with biotech growth hormone. However, it successfully defended a law requiring the labeling of consumer products containing mercury.
Republican Rep. Carolyn Branagan suggested Wednesday that her constituents again appear ready to take on big business. She said she had received "dozens and dozens" of emails from constituents supporting the GMO labeling bill and would follow their wishes.
"There have been few things in my 12 years here in the Legislature that my constituents in the town of Georgia have cared more about," she said.


text:
Shergar es una película británica-estadounidense de drama, romance y crimen de 1999, dirigida por Dennis C. Lewiston, que a su vez la escribió, musicalizada por John Scott, en la fotografía estuvo David Lewis y el elenco está compuesto por Alan Barker, Billy Boyle y Mickey Rourke, entre otros. El filme fue realizado por Blue Rider Pictures, Isle of Man Film Commission, Morlaw Films y Sun Chariot Films; se estrenó el 1 de junio de 1999.

Sinopsis
Shergar, el purasangre más premiado de Irlanda y posiblemente el mejor caballo de carreras de la historia, es raptado por integrantes del IRA, para liberarlo quieren 2 millones de dólares. Un mozo de cuadra tendrá que poner a salvo a Shergar y a él mismo lo antes posible.

Referencias

Películas en inglés
Películas de 1999

redpajama_set_name: RedPajamaWikipedia


Which one suits you the best?
Just a quick spread of butter and you're done!
Affectionately known as 'SOS' … 'Same Ole Stuff'; this old-time favorite smothers a slice of toast with creamed chipped beef gravy and is best eaten with a fork.
This one is more for those with a bit of a 'sweet tooth'. Use a 30 to 70 percent mix of cinnamon to sugar and sprinkle over toast after butter is melted.
While many may like this simple combination, add your favorite jam or jelly to take this to the next level. This delightful combination easily works as a mid-morning snack.
Take your pic of the basic breakfast sandwich: bacon & egg, sausage & egg, egg & cheese, etc. and put it on toast.
Pick a cheese, any cheese (cheddar, provolone, Muenster, Monterrey jack) you can't go wrong, but to really mix it up add your favorite vegetable.
This may be the most odd morning ritual, but a surprising number of us dip our toast. Try putting your toast in your morning coffee, tea, milk, soda or juice.
An instant healthy start to anyone's morning that doubles nicely as an after-school snack for the kids. Drizzle chocolate syrup for an extra treat.
There are many varieties to try when it comes to avocado and toast, but the most standard 'protein punch' is mashed avocado spread on toast and topped with a fried egg.
The post In the Kitchen: Toasts & Toppings appeared first on Las Cruces Magazine.
Getting away to the mountains is an easy jaunt from... The post Home Away from Home: Relaxing at Bella Luna Cottage appeared first on Las Cruces Magazine.


Poll: Who do you think will win the 2017 Masters?
The action starts at Augusta today.
How do Ireland's hopefuls compare with the other Masters contenders?
It's hard to argue with Dustin Johnson's stats, but Rory McIlroy isn't too far off him.
The competition has had some fantastic playoffs since it brought in sudden death playoffs.
Paulina Gretzky introduced herself to golf's fans last weekend at Augusta.
It's another 'W' for Stevie; get that man a green jacket.
Can McIlroy roar? Will Sergio wobble? Is it possible to stay on the couch for 10 hours straight?
*'Official' cos Sports Illustrated say he's back, that's why.
He's only a couple of months old, but Caleb Watson is already at home amongst the golfing elite.
Luke Donald's slip-up at the Heritage tournament means the Holywood native wakes up as the world's top golfer again.
The new Masters champion is feeling at home in his green jacket and in the spotlight.
This illustration shows you just how nuts and daring the shot from Watson really was last night.
After kicking off the day with the rare double eagle, Oosthuizen came up short to Bubba Watson in a play-off at the Masters last night.
Padraig Harrington and Phil Mickelson are in contention at Augusta National. Join us for live coverage of the fight for sport's most coveted casualwear.
The Swede shot 7-under 65 to take a one-shot lead over Mickelson, who put on a short-game clinic Saturday to land in good position for a fourth green jacket.
McIlroy may have slipped out of contention but Irish eyes will be on Pádraig Harrington tomorrow. Remember him?
Lee Westwood was getting ready for a morning tee time today, when he'll try to stay on top after shooting 5-under 67 in the opening round.
In the wake of last year's final-round collapse, the Holywood native faced up to some demons yesterday, but came out on the right side.
It's been a contrasting beginnings for Adam Scott and our own Pádraig Harrington at Augusta National today.
It might be billed as a two horse race between Rory and Tiger but there's more runners and riders than ever at Augusta.
Asked repeatedly about whether a woman would become a member at the home of the Masters, the Augusta National chairman budge.
Is Tiger Woods really too old to catch Jack Nicklaus?
As well as Rory McIlroy and the rest of the Augusta field, is old man time in Tiger's way?
He's back on the course where it all unraveled last year, but the Holywood man is ready to put the record straight this weekend.
No tickets, no autographs, no backwards caps and no phones. This sounds likes fun.


Silicon Knights is your online portal to anything and everything related to video games. It is a comprehensive electronic guide – a magazine – for video game players. It is your best resource for news, product launchings and updates, tips, tutorials, and whatever else you need to know about your favorite video games. Silicon Knights provides information that comes from the most reliable sources in the video gaming industry.
According to several online sources, over 150 million Americans play video games three or more hours per week. Video games sales total is pegged at more or less $13 billion. Of course, these numbers can grow in the coming years, as new games are released, and more people discover the wonders of video gaming. This population is the community that Silicon Knights caters to. The video gaming industry is its major client.
Silicon Knights was created in New York with the goal of connecting video game players throughout the country (and the world). It is a well-thought-out online magazine that offers an interesting mix of information and fun activities. It also features reviews and special write-ups submitted by readers. Silicon Knights also conveys its messages through videos and, from time-to-time, podcasts.
As the primary online portal for video game players, Silicon Knights is dedicated to providing only the most relevant and interesting information to its readers. Its content management team gathers materials from some of the most reliable sources in the industry. Likewise, the team always finds time to go out and research, to do interviews, and to try out games for reviews.
Silicon Knights is updated every Saturday and Sunday, so you are guaranteed to get only the freshest news and updates about the video gaming industry.


text:
Superliga — третий сингл датской рок-группы Nephew с их второго альбома USA DSB, вышедшего в 2004 году. Песня обращается  со скрытым сообщением любви, и в песне упоминается много знаменитых людей.

Видеоклип

Видеоклип был выпущен в том же году. Режиссёрами клипа были Jakob Thorbek и Rasmus Meisler. Видео получило приз в номинации «Лучший Видеоклип Года» на Danish Music Award 2005. В самом видеоклипе, младший брат фронтмена Nephew Симона Квамма танцует в футболке, на которой постоянно меняется надпись, описывающая различных знаменитостей, упоминающихся в песне. Цветовая палитра клипа постоянно меняется между синим, красным и жёлтым.

Призы
Песня победила на GAFFA Prize в 2004 году, в номинации «Хит 2004 в Дании».
Видеоклип победил в номинации «Лучший Видеоклип Года» на Danish Music Award.

Примечания

Ссылки
 официальный сайт Nephew

Синглы 2004 года


text:
Baiae var en romersk semesterort i nutidens Bacoli vid Neapelbukten i Italien. Det var en fritidsort för antikens rika romare. Den ansågs vara mera exklusiv än Pompeji, Herculaneum och Capri. De rikaste romarna valde att bygga lyxiga semestervillor i staden. Staden var känd för hedonistiska fester för eliten. Staden blev övergiven senare och till mestadels liggande under vatten efter flera vulkaniska utbrott under renässansepoken.

De allmänna och de privata baden i Baiae fylldes på med hett svavelhaltigt vatten, som kom till bassängerna från underjordiska källor. Romerska ingenjörer konstruerade komplicerade system av bergrum som kanaliserade underjordisk värme till utrymmen som fungerade som bastuer. Förutom som trivselfunktion, tjänade baden som kurbad i romersk medicin för att behandla olika åkommor.

Källor

Noter

Kurorter
Romerska städer
Kampanien


Roma, 1973. To me photography is the synthesis between the representation of reality and the ability to trascend it. Awards: First Prize @ WHERE STREET HAS NO NAME" Finalist @ MSPF (MIAMI STREET PHOTOGRAPHY FESTIVAL) 2013 FInalist @ LEICA TALENT 2014 Finalist @ MSPF (MIAMI STREET PHOTOGRAPHY FESTIVAL) 2014 Winner@ LEICA TALENT 2014 Publications: WSP Photography; Beirut Street Photography; International Street Photographer (ISP) Magazine november/december issue 2013.


text:
Poll: Rape victims partly to blame
More than half of Britons believe some rape victims should take responsibility for being attacked, research suggests
February 15 2010 2:30 PM
More than half of Britons believe some rape victims should take responsibility for being attacked, research has suggested.
https://www.independent.ie/woman/poll-rape-victims-partly-to-blame-26632407.html
https://www.independent.ie/migration_catalog/article25148247.ece/b159e/AUTOCROP/h342/B39929561266234789A0_1
In a new poll, 56% of those questioned felt that there were certain circumstances where the victim should be held partly accountable.
Of those, 28% thought people who wore revealing clothes should take some of the blame if they were sexually assaulted.
Among women, 23% said if someone danced provocatively at a nightclub they should be held partly responsible, and 15% said the same if they had accepted a drink from their attacker.
The research, called Wake Up To Rape, was carried out to mark the 10th anniversary of the Havens, which runs sexual assault referral centres in London.
Dr Jan Welch, clinical director at the Haven in Camberwell, south-east London, said: "Unfortunately, women have bought into the idea that sometimes the rape victim is to blame. Under no circumstances is a woman at fault for being raped.
"Coping with the emotional trauma of rape or sexual assault is made even harder when the victim is made to feel responsible for what's happened."
The poll of more than 1,000 people living in London showed that 18% of those questioned thought most rape claims were false. It also found that 23% of women and 15% of men had been made to have sex when they did not want to.
When asked what action they would take if they were raped, one in 25 respondents said they would do nothing. The most common reason was feeling ashamed.
Many people took risks when it came to personal safety, particularly those aged 18 to 24. Nearly half of those asked had walked home via back streets on their own (46%), while 26% had left their drink unattended in bar. And a fifth had got into a taxi without checking whether it was licensed, and the same number had got so drunk that they could not remember a night out.
PA Media
The wait is over... Prince William and Kate reveal new son's name
Independent.ie Newsdesk Prince William and his wife Kate Middleton have named their newborn son, Louis Arthur Charles.
Four places to have a fabulous farmhouse style hen in Ireland (just like Meghan Markle!)
Karen Birney If there was one thing we could have expected from Meghan Markle in all the furore of royal wedding planning, it's that she would choose a chic, elegant, exclusive place to throw a low-key but...
CLOSED: WIN! A romantic overnight stay plus dinner for two at the fabulous Faithlegg...
To celebrate Faithegg House Hotel's special wedding afternoon of wedding inspiration taking place on Sunday 25th February, we've teamed up with the gorgeous venue to offer our readers (yep that's you!) a most wonderful prize!
The Sexiest Woman of All Time
Rachel Stevens named the Sexiest Woman of All Time by FHM
Kourtney Kardashian 'pregnant with third child'
Kourtney Kardashian is reportedly pregnant.
'First World Problems'
Claudine Keane reveals dress hunt for Rosanna's third wedding
The wait is over... Prince William and Kate reveal new son's...
Prince William and...
Four places to have a fabulous farmhouse style hen in Ireland...
If there was one thing...
CLOSED: WIN! A romantic overnight stay plus dinner for...
To celebrate Faithegg...
Bieber chats to campaigner Malala
Justin Bieber showed his serious side as he spoke to teenage...
Lively reveals anniversary plans
Blake Lively has revealed that she and husband Ryan Reynolds...
Capaldi: Doctor costume for fans
Peter Capaldi has revealed he chose his new Doctor Who...
Stewart: I don't smile for photos
Kristen Stewart has revealed that she doesn't smile for...
Beyonce's post-tour thanks to fans
Beyonce has thanked her fans as she and husband Jay Z wrapped...
MacLachlan for Agents of SHIELD
Kyle MacLachlan is joining the cast of Marvel's Agents Of...
Morrissey peeved at TV indifference
Morrissey claims he has been...
'Tourist' steals Nick Hewer's watch
Nick Hewer has revealed his designer wristwatch has been...
Lady Gaga shares hospital selfie
Lady Gaga is recovering in hospital after suffering from altitude...
Dakota bans parents from 50 Shades
Dakota Johnson has banned...
Batman V Superman brought forward
The eagerly anticipated...
R-Patz's pride at sister's X Factor
Robert Pattinson has revealed he is "ridiculously proud"...
Moss quiet about True Detective
Elisabeth Moss has remained tight-lipped about rumours...
Cotillard 'insisted on more takes'
Marion Cotillard has said that after more than 80 takes on her...
West: I'm not like Britney Spears
Kanye West took a pop at Britney Spears during an...
Holmes shields Suri from celebrity
Katie Holmes has said she doesn't regret becoming...
Owen: Knick more about losing life
Clive Owen has said new medical drama The Knick is...
Jackson to play Black Phantom?
Samuel L Jackson is in talks to play the Black Phantom on the big...
Take That for Secret Service score
Take That are reportedly recording a new hit to feature on the...
Fans can expect a 'fiercer' Doctor
Doctor Who fans can expect a "fiercer" version of...
Moretz talks Beckham skateboard pal
Chloe Grace Moretz has...
JB defends Cheryl X Factor selfie
Cheryl Fernandez-Versini's new husband Jean-Bernard has...
FHM's 10 'Sexiest Women of All Time'
Glamour Women of the Year Awards
The most outrageous red carpet dresses
Kris Jenner Breaks Her Silence On Rob Kardashian's Issues
Momager Kris Jenner opens up about her son Rob Kardashians shock wedding exit and...
Lady Gaga Goes Surfing With Her Dog Asia
Lady Gaga has Instagrammed some shots of her surfing with her dog, Asia, prior to...
Pharrell Scrutinized For Wearing Native American Headdress
Pharrell Williams is on the cover of Elle UK magazine, and...