Dynamic Shortest Path Algorithms for Hypergraphs

A hypergraph is a set V of vertices and a set of non-empty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph.

I. INTRODUCTION
A graph is a basic mathematical abstraction for modeling networks, in which nodes are represented by vertices and pairwise relationships are represented by edges between vertices. A graph is thus given by a vertex set V and an edge set E consisting of cardinality-2 subsets of V . A hypergraph is a natural extension of a graph obtained by removing the constraint on the cardinality of an edge: any non-empty subset of V can be an element (a hyperedge) of the edge set E (see Fig 1). It thus captures group behaviors and higher-dimensional relationships in complex networks that are more than a simple union of pairwise relationships. Examples include communities and collaboration teams in social networks, document clusters in information networks, and cliques, neighborhoods, and multicast groups in communication networks. While the concept of hypergraph has been around since 1920's (see, for example, [1]), many well-solved algorithmic 0 This work was supported by the Army Research Laboratory NS-CTA under Grant W911NF-09- 2-0053. problems in graph theory remain largely open under this more general model. In this paper, we address the shortest path problem in hypergraphs.

A. Shortest Path Problem in Graphs
The shortest path problem is perhaps one of the most basic problems in graph theory. It asks for the shortest path between two vertices or from a source vertex to all the other vertices (i.e., the single-source version or the shortest path tree). Depending on whether the edge weights can be negative, the problem can be solved via Dijkstra's algorithm or Bellman-Ford algorithm [2]. This basic problem finds diverse applications in communication networks, operational research, plant and facility layout, and VLSI design [3].
The dynamic version of the shortest path problem is to maintain the shortest path tree without recomputing from scratch during a sequence of changes to the graph. A typical change to a graph includes weight increase, weight decrease, edge insertion, and edge deletion. The last two types of changes model network topological changes, but they can be conceptually considered as special cases of weight changes by allowing weight to be infinity. Thus, if the sequence of changes contains only weight increase and edge deletion, we call it a decremental problem; if it contains only weight decrease and edge insertion, we call it an incremental problem. Otherwise, we have a fully dynamic problem. If multiple edges change simultaneously, then it is called a batch problem.
There have been a number of studies of the dynamic shortest path problem in graphs. Ramalingam and Reps [4], Frigioni et al. [5,6], and Narvaez et al. [7] proposed several algorithms for the single-change problem. The batch problem was considered in [7][8][9]. Comprehensive experiments on the comparison of different batch algorithms can be found in [9,10].

B. Shortest Path Problem in Hypergraphs
Both the static and dynamic shortest path problems have a corresponding version in hypergraphs. The static shortest hyperpath problem was considered by Knuth [11] and Gallo et al. [12], in which Dijkstra's algorithm was extended to obtain the shortest hyperpaths. Knuth's algorithm is for a special class of hypergraphs while Gallo's algorithm is for a general hypergraph. Ausiello et al. proposed a dynamic shortest hyperpath algorithm for directed hypergraphs, considering only the incremental problem with the weights of all hyperedges limited to a finite set of numbers [13,14]. A dynamic algorithm for the batch problem in a special class of hypergraphs was developed in [8].
With the exception of the above few studies, the shortest hyperpath problem remains largely unexplored. To the best of our knowledge, no algorithms exist for the fully dynamic problem in a general hypergraph.
In this paper, we develop two fully dynamic shortest path algorithms for general hypergraphs. These two algorithms complement each other, with each preferred in different types of hypergraphs and dynamics.
Referred to as the HyperEdge based Dynamic Shortest Path algorithm (HE-DSP), the first algorithm is an extension of the dynamic Dijkstra's algorithm for graphs to hypergraphs (parallel to Gallo's extension of the static Dijkstra's algorithm to hypergraphs in [12]). The extension of the dynamic Dijkstra's algorithm to hypergraphs is more involved than that of the static Dijkstra's algorithm. This is due to the loss of the tree structure (in the original graph sense) in the collection of the shortest hyperpaths from a source to all other vertices. Since the dynamic Dijkstra's algorithm relies on the tree structure to update the shortest paths after an incremental change (weight increase or edge deletion), special care needs to be given when extending it to hypergraphs.
The second algorithm is rooted in the idea of Dimension Reduction and is referred to as DR-DSP. The basic idea is to reduce the problem to finding the shortest path in the underlying graph of the hypergraph. The underlying graph of a hypergraph has the same vertex set and has an edge between two vertices if and only if there is at least one hyperedge containing these two vertices in the original hypergraph. The weight of an edge in the underlying graph is defined as the minimum weight among all hyperedges containing the two vertices of this edge. The shortest hyperpath in the hypergraph can thus be obtained from the shortest path in the underlying graph by substituting each edge along the shortest path with the hyperedge that lent its weight to this edge. The correctness and advantage of this algorithm are readily seen: the definition of weight in the underlying graph captures the minimum cost offered by all hyperedges in choosing a path between two vertices, thus ensuring the correctness of the algorithm; the reduction of a hypergraph to its underlying graph removes many hyperedges from consideration when finding the shortest path, leading to efficiency and agility to dynamic changes.
HE-DSP is more efficient in hypergraphs that are densely connected through high-dimensional hyperedges and for network dynamics where changes often occur to hyperedges that are not on the current shortest hyperpaths. DR-DSP has lower complexity when hyperedge changes often lead to changes in the shortest hyperpaths. This is usually the case in networks where hyperedges in the shortest hyperpaths are more prone to changes due to attacks, frequent use, or higher priority in maintenance and upgrade. Furthermore, DR-DSP leads to an alternative algorithm for solving the static shortest hyperpath problem when the dynamic problem degenerates to the static problem. It has the same complexity as Gallo's algorithm for a general hypergraph and lower complexity for simplicial complexes (a special class of hypergraphs whose hyperedge set is closed under the subset operation). We also point out that both proposed algorithms apply to directed hypergraphs with minor modifications in their implementation details.
A detailed time complexity analysis of these two algorithms is provided to demonstrate their performance in the worstcase change scenario. Using a random geometric hypergraph model and a real data set of a social network (Enron email data set), we study the average performance of these two algorithms in different scenarios and demonstrate the partition of the application space between these two algorithms. In the experiment with Enron email data set, the proposed algorithms successfully identified the most important actor in this social network using the closeness centrality metric.

C. Applications
Shortest path computations on hypergraphs can be applied to communication as well as social networks. An example application in wireless communications, in particular, for multihop wireless networks, is in opportunistic routing schemes such as ExOR [15], GeRaF [16], and MORE [17]. In such schemes, any receiver of a packet is eligible to forward the packet. Receivers typically execute a protocol amongst themselves to decide who should forward it. This naturally leads to a hypergraph model where a node and its neighbors form a hyperedge. The cost of each hyperedge can be defined based on the cardinality of the hyperedge to capture the success rate of forwarding (lower the cardinality, lesser the chance that at least one of the nodes successfully receives the packet) and the associated overhead (higher the cardinality, higher the energy consumption and the overhead in choosing the forwarding node). A shortest hyperpath from the source to the destination is thus a better route than merely the traditional shortest path. And as the network topology changes, a dynamic algorithm is required to maintain the shortest hyperpath.
In social networks, information (results, event reports, opinions, rumors, etc.) propagates through diverse communication means including direct links (e.g., gestures, optical, satcom, regular phone call), social media (e.g., Facebook, Twitter, blogs), mailing lists, and newsgroups. Such a network may be modeled as a hypergraph with the weight of a hyperedge reflecting the cost, credibility, and/or delay for disseminating information among all vertice of this hyperedge. In particular, the weight of a hyperedge can capture the unique effect on the information after it passes through a group of people. For instance, a result can be discussed by overlapping blog collaboration networks as it spreads, and often the discussion yields a better result than if it only spreads through individuals. The minimum cost information passing in social networks can thus be modelled as a shortest hyperpath problem.
Another potential application is that of finding the most important actor in a social network. Under a graph model of social networks, the relative importance of a vertex can be measured by its betweenness and closeness centrality indices. The former is defined based on the number of shortest paths that pass through this vertex, and the latter, the total weight of the shortest paths from this vertex to all the other vertices [18]. In a social network exhibiting hyper-relationships, between-ness and closeness centrality, based on the shortest hyperpaths, would be better indicators of the relative importance of each actor. In Sec. VII, we apply the proposed shortest hyperpath algorithms to the Enron email data set. We propose a weight function that leads to the successful identification of the CEO of Enron as the most important actor under the closeness centrality metric. The distance of each person in the data set to the CEO along the resulting shortest hyperpaths closely reflects the position of the person within the company.

II. BACKGROUND ON DYNAMIC SHORTEST PATH ALGORITHMS FOR GRAPHS
In this section, we present the basic ideas of the dynamic shortest path algorithms developed for graphs in [5]. Some basic techniques in updating and maintaining the shortest path tree will be borrowed in later sections when we develop dynamic shortest hyperpath algorithms.

A. Dynamic Shortest Path Problem
A change δ on a graph G = (V, E) corresponds to one edge modification. There are four types of changes: weight increase, weight decrease, edge insertion, and edge deletion. Weight increase and edge deletion can be similarly treated (with small differences in the required data structures which will be omitted for simplicity), so can weight decrease and edge insertion. The dynamic algorithms are thus presented only for weight increase and weight decrease.
Given a graph G, a source node s, and a sequence of changes C = {δ 1 , δ 2 , . . . , δ l } on G, the dynamic shortest path problem is to find the shortest paths from s to all nodes in each new graph after change δ i . In

B. Weight Decrease
Consider that the weight of edge (ǔ,v) decreases to w new . Without loss of generality, assume that . It is not difficult to see thatǔ will not be affected by this change. The dynamic algorithm starts with determining whetherv will be affected by simply checking the inequality If the inequality does not hold, then this edge with the decreased weight does not provide a shorter path forv; the algorithm ends and the shortest path tree remains unchanged. If the inequality holds, thenv is affected; its new shortest path from s must go through edge (ǔ,v) and D[v] reduces to D[ǔ] + w new . We putv in a priority queue 1 Q, and the rest of the procedure is similar to Dijkstra's algorithm: dequeue the node z with the minimum distance from Q, update the distances of its neighbors, update Q by inserting the new affected vertices among the neighbors to Q and update the ranks of others based on the updated distances. The procedure iterates until Q is empty. A pseudo code presentation of the basic steps is given below.
is not an edge in the shortest path tree, then none of the vertices will be affected, the shortest path tree remain unchanged. Otherwise, the descendants, and only the descendants of this edge in the shortest path tree may be affected. For these vertices, some of them will have increased distances, some of them will go through an alternative path with the same distance (but changed parent), while the rest will not be affected. In order to classify the vertices into these three categories, we introduce the coloring idea in Frigioni's algorithm [5]: remains the same.
It is not difficult to see that if a vertex v is white or pink, all its descendants in the shortest path tree are white; if v is red, all its descendants are either red or pink. Therefore the coloring procedure is clear: we first determine whetheř v is pink or red by checking whether there is an alternative shortest path with the same distance forv (note thatv cannot be white due to the weight change of edge (ǔ,v) that is on its current shortest path); if such a path exists, then we coloř v pink and the algorithm ends, otherwise we color it red and put all its children in a priority queue M . The procedure then iterates for each vertex in M according to an increasing order of the vertex distances.
After the coloring process, we only need to deal with the red vertices. For each red vertex z, we initialize its distance with the distance of the shortest path through one of its non-red neighbors and put z in another priority queue Q (if no nonred neighbor exists, we initialize it with ∞). After this, the procedure is similar to Step 2 in the Graph: Weight Decrease algorithm: at each iteration, we extract the vertex at the top of Q and update its neighbors and Q until Q is empty.
then z is pink 10 else z is red; Enqueue(M , all z's children) 11 end; end Step3.a (Initialize the distance vector for red vertices) 12 for each red vertex z do 13 if z has no nonred neighbor 14 let u be the best nonred neighbor of z 17 end; end; end Step3.b: Step2 of Graph: Weight Decrease The worst-case time complexity for one edge change (either weight decreasing or increasing) is O(|δ| log |δ| + δ ), where |δ| denotes the number of affected vertices and δ the total number of both affected vertices and affected edges.

III. DYNAMIC SHORTEST HYPERPATH PROBLEM
We introduce some basic concepts of hypergraph [1] and define the static and the dynamic shortest hyperpath problems. Some basic properties of the shortest hyperpaths are established and will be used in developing the dynamic algorithms in subsequent sections.

A. Hypergraph and Hyperpath
Let V be a finite set and E a family of subsets of V . If for all elements e i ∈ E, the following conditions are satisfied: In a hypergraph, a hyperpath is defined as follows. Definition 1: A hyperpath between two vertices u and v is a sequence of hyperedges {e 0 , e 1 , . . . , e m } such that u ∈ e 0 , v ∈ e m , and e i ∩ e i+1 = ∅ for i = 0, ..., m − 1. A hyperpath is simple if non-adjacent hyperedges in the path are nonoverlapping, i.e., e i ∩ e j = ∅, ∀j = i, i ± 1.
Let L e = {e 0 , . . . , e m } be a hyperpath in a weighted hypergraph H. We define the weight of L e as:

B. Shortest Hyperpath and Relationship Tree
Given two vertices u and v, a natural question is to find the shortest hyperpath (in terms of the path weight) from u to v. Since the weight function is nonnegative, it suffices to consider only simple hyperpaths. If the shortest hyperpath is not simple, we can always generate a simple hyperpath without increasing the weight by deleting all the hyperedges between two overlapping non-adjacent hyperedges.
The dynamic shortest hyperpath problem can be similarly defined for a sequence C = {δ 1 , δ 2 , . . . , δ l } of hyperedge changes. Hyperedge changes have the same four types as edge changes in a graph: weight increase, weight decrease, hyperedge insertion, and hyperedge deletion. Similarly, weight increase and hyperedge deletion will be treated together, so are weight decrease and hyperedge insertion.
In this paper, we consider the single-source shortest hyperpath problem: find the shortest hyperpaths from a given source s to all other vertices. The presentation of the paper focuses on undirected hypergraphs. However, the two proposed dynamic algorithms apply to directed hypergraphs with minor modifications in their implementation details.
Below, we establish a basic property of shortest hyperpaths. Lemma 1: Let L = {e 1 , e 2 , . . . , e l } be a shortest hyperpath from s ∈ e 1 to z ∈ e l . Then for any vertex v ∈ e i ∩ e i+1 , the hyperpath L v = {e 1 , e 2 , . . . , e i } is a shortest hyperpath from s to v. Furthermore, for any two vertices u, v ∈ e i ∩ e i+1 (if there exist at least two vertices in e i ∩ e i+1 ), Proof: We will prove by contradiction. Assume that Then consider the hyperpath L ′ = {e ′ 1 , e ′ 2 , . . . , e ′ k , e i+1 , e i+2 , . . . , e l }, we have w(L ′ ) < w(L) which contradicts the fact that L is a shortest hyperpath to z. This completes the proof for the first part of the lemma. Furthermore, for any two nodes u, v ∈ e i ∩e i+1 , since L v is the shortest hyperpath for both vertices, Next, we introduce the concept of relationship tree that is needed in the proposed dynamic shortest hyperpath algorithm HE-DSP. Since two adjacent hyperedges in a hyperpath may overlap at more than one vertex, the shortest hyperpaths from s to all other vertices do not generally form a tree in the original graph sense. For the development of the dynamic shortest hyperpath algorithms, we introduce the concept of relationship tree to indicate the parent-child relationship along shortest hyperpaths. The concept can be easily explained in the example given in Fig 2. Let {e 1 , e 2 } be a shortest hyperpath from s to v 4 . By Lemma 1, {e 1 } is a shortest hyperpath for both v 1 and v 2 . As illustrated in Fig 2, there are 4 possible relationship trees to indicate the parent-child relationship in these shortest hyperpaths. We will show in Sec. IV that the choice of the relationship tree does not affect the correctness or performance of the proposed algorithm HE-DSP.

IV. HYPEREDGE BASED DYNAMIC SHORTEST PATH ALGORITHM
In this section, we propose HE-DSP. It is an extension of the dynamic Dijkstra's algorithm to hypergraphs. The extension is more complex than Gallo's extension of the static Dijkstra's algorithm, since the dynamic Dijkstra's algorithm relies on the tree structure of the shortest paths, a structure no longer there for the shortest hyperpaths.

A. Hyperedge Weight Decrease
Consider that the weight of a hyperedgeě decreases to w new . Similar to the case for graphs, we know that the vertex x ∈ě with D[x] = min v∈ě {D[v]} will not be affected. We then check weather the other vertices ině are affected by checking the inequality given in (1), and put all the affected vertices into a priority queue Q. The rest of the procedure is similar to that for graphs, only when we update the distance of a vertex, we check all the hyperedges that contain this vertex.

HE-DSP: Weight Decrease
end Step2 (Iteratively enqueue and update affected vertices) 7 while

B. Hyperedge Weight Increase
The coloring process in the graph case relies on the tree structure of the shortest paths, which is no longer present in the shortest hyperpaths. Our solution is to use a relationship tree for the coloring process, and we prove the correctness of this approach regardless of the choice of the relationship tree.
Consider that the weight of a hyperedgeě increases to w new . First, we redefine the color of a vertex v based on the chosen relationship tree.
With the above modified definitions of colors, the same coloring process as in the graph case can be carried out using a relationship tree. The algorithm is given below. In this section, we propose DR-DSP. When the dynamic problem degenerates to the static problem, DR-DSP leads to an alternative algorithm for solving the static shortest hyperpath problem.

A. The Static Case: DR-SP
We first consider the static version of the algorithm (referred to as DR-SP), which captures the basic idea of dimension reduction.
The proposed DR-SP algorithm is based on the following theorem in which we show that for a general hypergraph H, the weight ω(L * ) of the shortest path L * of H is equal to the shortest path L * G of a weighted graph G derived from H. Specifically, corresponding to every hyperedge e in H, G contains a clique defined on the vertices of e.
Let L * and L * G be the shortest paths from u ∈ V to v ∈ V in H and G, respectively. Then we have that w(L * ) = w G (L * G ).
Proof: First, for each shortest path L * G in G, we can obtain a corresponding hyperpath L in H with the same weight based on (2), therefore we have that Then it suffices to show that there exists a path Assume that L * = {e 0 , e 1 , . . . , e k−1 } is a shortest hyperedge path from v 0 to v k in H where v 0 ∈ e 0 and v k ∈ e k−1 .
Let v i ∈ e i−1 ∩ e i (i = 1, 2, ..., k − 1) be one of the vertices in the intersection of hyperedges e i−1 and e i . Construct a path L G = {v 0 , v 1 , ..., v k } in the graph G. For each edgẽ Thus, i.e., w G (L G ) ≤ w(L * ). It follows from Theorem 3 that the shortest path in a general hypergraph can be obtained by applying Dijkstra's algorithm to the underlying graph G with weights modified as stated in the theorem.

B. The Dynamic Case: DR-DSP
In the dynamic case, a sequence C = {δ 1 , δ 2 , . . . , δ l } of hyperedge changes in the hypergraph H results in a sequence of edge changes in the underlying graph G. For each hyperedge change δ i , DR-DSP first updates the underlying graph G to locate all the changed edges caused by δ i . In the next step, DR-DSP updates the shortest path tree in the underlying graph G.
Consider first the graph update. A change to a hyperedge e only affects those edges in G that are subsets of e, i.e., a hyperedge change is localized in the underlying graph G. Furthermore, since the weight of an edge in G is the minimum weight of all hyperedges containing it, not all edges in G that are subsets of e will change weight. Based on these observations, we propose a special data structure and procedure for updating the underlying graph G without regenerating the graph from scratch using Step 1 of DR-SP.
At the initialization stage of the algorithm, a priority queue M uv for each pair of vertices (u, v) in the hypergraph is established to store the weights of all hyperedges that contain both u and v. When a change occurs to hyperedge e, all the priority queues M uv associated with the pair of vertices (u, v) that are contained in e are updated with the new weight of e. Thus, the top of these priority queues always maintain the weight for edge (u, v) in the underlying graph G for each (u, v). Below is a pseudo code implementation of the proposed procedure.
Graph Update(ě, w new ). After the underlying graph G is updated, we are now facing a dynamic shortest path problem in a graph. However, since a single hyperedge change can result in multiple edge changes in G, we need to handle a batch problem. While existing batch algorithms and iterative single-change algorithms for graphs can be directly applied here, we show that the batch problem we have at hand has two unique properties that can be exploited to improve the efficiency of the algorithm.
Property 1: The edge changes in G caused by a hyperedge change are either all weight decreases or all weight increases.
Property 2: All changed edges in G caused by a hyperedge change belong to a clique in G.

C. Hyperedge Weight Decrease
If the weight of hyperedgeě decreases to w new , by Theorem 3 and Property 1, there are (possibly) several edgeweight decreases in the underlying graph G. Therefore similar to HE-DSP, there is at least one unaffected node x = argmin v∈ě {D[v]}. By Property 2, these affected edges are contained in a clique derived from the changed hyperedge; therefore it is sufficient to determine the distance of every node v (other than x) in the original changed hyperedge e by checking D[x] + w new < D [v]. And we can initialize the priority queue with those nodes whose weight decreases. After that, the procedure is similar to that in the graph case.

VI. TIME COMPLEXITY ANALYSIS
We analyze the time complexity of the two proposed dynamic algorithms. We show that for different scenarios, each algorithm has its own advantage. We also consider the static case and show that the static version of DR-DSP has the same complexity as Gallo's algorithm for a general hypergraph and lower complexity for a simplicial complex.

A. The Static Shortest Hyperpath Problem
Therefore the time complexity for Step 1 is O(d2 d m). The total time complexity thus follows.

B. The Dynamic Shortest Hyperpath Problem
Given a hypergraph H = (V, E, w) and a change to hyperedge e, let |δ| denote the number of affected vertices, δ the number of affected hyperedges plus |δ|, |δ Φ | = e∈E,e is affected |e| 2 , and δ the number of affected edges in the underlying graph plus |δ|. For DR-DSP: Weight Decrease, the total time spent on Graph Update procedure is O(|e| 2 log m). In Step 2, there are |δ| iterations; in each iteration O(log |δ|) time is spent to dequeue z from M . Time spent on updating neighbors over all iterations is O( δ ). Therefore the total time complexity is O(|δ| log |δ|+ δ +|e| 2 log m). For DR-DSP: Weight Increase, Step 2, Step 3.a and Step 3.b take O(|δ| log |δ| + δ ) (similar to the analysis for graphs). The total time complexity thus follows.
From Theorem 5 we see that if δ is small and |e| is large, HE-DSP performs better, since in DR-DSP, the update of the underlying graph has to be done regardless whether there are affected vertices. Thus in a sequence of hyperedge changes, if only a small fraction of them actually have affected nodes, then HE-DSP will outperform DR-DSP. On the other hind, if δ is large, because usually |δ Φ | ≫ δ , then DR-DSP will outperform HE-DSP. Consider the extreme example where every valid hyperedge exists, all nodes are affected and the changed hyperedge contains n vertices. Then |δ| = n, |δ Φ | = O(n 2 2 n ), δ = O(n 2 ), |e| = n, m = O(2 n ). The time complexity of HE-DSP is O(n log n + n 2 2 n ) = O(n 2 2 n ) while the time complexity of DR-DSP is O(n 3 ). We see that the time complexity of DR-DSP can be much lower than that of HE-DSP.

VII. SIMULATION RESULTS
We present simulation results on the running time of the proposed dynamic shortest hyperpath algorithms. We test the proposed algorithms on hypergraphs generated from a random geometric model as well as those generated by the Enron email data set. All simulation code is compiled and run on the same laptop equipped with a 3.0GHz i7-920XM Mobile Processor.

A. Random Geometric Hypergraph
We first consider a random geometric hypergraph model in which n nodes are uniformly distributed in an a×a square. All nodes within a circle with radius r form a hyperedge (circles are centered on a h × h grid). The weight of each hyperedge is given by the average distance between all pairs of vertices of this hyperedge.
A sequence of changes are then generated and the proposed dynamic algorithms are employed to maintain all the shortest hyperpaths from the source s located at a corner of the a × a square. Each change can be a hyperedge insertion (with probability p I ), a hyperedge deletion (with probability p D ), or a weight change (with probability 1−p I −p D ) with new weight chosen uniformly in [w min , w max ]. In the case of a hyperedge deletion or a weight change, the hyperedge to be deleted or to be assigned with a new weight is chosen according to the two models detailed below. Hyperedge insertions are only realized when there are hyperedges that have been deleted, and a randomly chosen one is inserted back. This ensures that all hyperedges satisfy the geometric property determined by r at all time. It also models the practical scenario where a broken link is repaired.
In selecting a hyperedge for deletion or weight change, we consider two different models: the random change model and the targeted change model. In the former, the hyperedge is randomly and uniformly chosen among all hyperedges. In the latter, it is randomly and uniformly chosen from the current shortest hyperpaths. This models the scenarios where hyperedges in the shortest hyperpaths are more prone to changes due to attacks, frequent use, or higher priority in maintenance and upgrade.
In Fig. 3, we show the simulation results on the running time of the two proposed algorithms under a sequence of 10 4 changes. We see that HE-DSP has lower complexity in networks with random topological and weight changes (Fig. 3-Left), whereas DR-DSP should be preferred in networks with targeted changes (Fig. 3-Right). This partition of the application space can be explained from the structures of these two algorithms. Under the random change model, a large fraction of changes do not result in changes in the current shortest hyperpaths. Such changes lead to little computation in maintaining the shortest hyperpaths for both algorithms, but requires about the same amount of computation in the Graph-Update step of DR-DSP for maintaining the underlying graph. On the other hand, under the targeted change model, all hyperedge deletions and weight changes affect the shortest hyperpaths. Updating the shortest hyperpaths can be done more efficiently in DR-DSP since it works on the underlying graph with a much smaller number of edges.

B. Enron Email Data Set
In this example, we consider the application of the shortest hyperpath algorithms in finding the most important actor in a social network. We consider the Enron email data set and use the same hypergraph generation model as in [20]. Specifically, each person is a vertex of the hypergraph, and the sender and recipients of every email form a hyperedge. Our objective is to identify the most important person measured by the closeness centrality index (i.e., the total weight of the shortest hyperpaths from this person to all the other persons). The first step is to assign weight to each hyperedge that reflects "distance". While there is no universally accepted way of measuring distance in a social network observed through email exchanges, certain general rules apply. First, a direct email exchange between two persons indicates a stronger tie than an email sent to a large group. Thus, the weight of an hyperedge should be an increasing function of the cardinality of this hyperedge. Second, more frequent email exchange among a given group of people shows stronger ties. Thus, the weight of an hyperedge should be decreasing with the number of times that this hyperedge appears in the email data set. Considering these two general rules, we adopt the following weight function: where |e| is the cardinality of the hyperedge e, α is the parameter measuring how fast the weight decreases with the number l of times that this hyperedge appears in the data set. We can then apply DR-SP on the resulting (static) hypergraph to find the shortest hyperpaths rooted at each vertex and compute this vertex's closeness centrality index. With the weight function given in (3) using α = 0.6, the identified most important actor is the CEO of Enron. The average distance (along the shortest hyperpath) from the CEO to the other persons at various positions is shown in Fig. 4. We observe that in general, the higher the position, the shorter the distance. These results demonstrate that the adopted hypergraph model and weight function capture the essence of the problem.
Next, we construct a dynamic hypergraph sequence based on the Enron data set. At the beginning, the hypergraph contains only individual vertices. We then consider each email chronologically. Each email either adds a new hyperedge or decrease the weight of an existing hyperedge (due to the increased number of appearances of this hyperedge). The two proposed algorithms are employed to maintain the shortest hyperpaths rooted at the CEO after each change. The running time is given in Fig. 5, which shows the lower complexity of DR-DSP. The reason is that a large fraction of hyperedge changes result in changes in the shortest hyperpaths.

VIII. CONCLUSION
We have presented, to our best knowledge, the first study of the fully dynamic shortest path problem in a general hypergraph. We have developed two dynamic algorithms for finding and maintaining the shortest hyperpaths. These two algorithms complement each other with each one preferred in different types of hypergraphs and network dynamics, as illustrated in the time complexity analysis and simulation experiments. We have discussed and studied via experiments over a real data set the potential applications of the dynamic shortest hyperpath problem in social and communication networks.
The proof is based on the following three lemmas.
, which can be easily seen from the procedure of the algorithm).
We now prove the converse. Assume that Then u i+2 will be enqueued in Step 2 of the algorithm when u i+1 is dequeued if it has not been enqueued before that. Repeating this line of argument, we conclude that there exits u l ∈ e l−1 ∩ e l with d ′ [u l ] < d[u l ] and u l is enqueued into Q. Then v will be enqueued when u l is dequeued if it is not enqueued already. Then based on the fact that distances of the dequeued vertices are monotonically increasing with the order of the dequeueing as shown at the beginning of the proof, u cannot be any vertex dequeued after z l+1 . Since z l+1 ∈ě, it is also clear that u cannot be an unaffected vertex(otherwise, z l+1 will be unaffected, which contradicts Lemma 3). We thus have u ∈ {z 1 , . . . , z l }. Let u = z i . Then when z i is dequeued , D[z l+1 ] will be updated to the shortest distance d ′ [z l+1 ] due to the induction hypothesis of D[z i ] = d ′ [z i ]. This completes the proof. Based on Lemma 3 and 4, the shortest distances of all affected vertices will be updated correctly. Based on Lemma 3, all unaffected vertices will not be enqueued, and their distances remain the same. It is not difficulty to see from the algorithm that P [v] and E[v] are also correctly maintained for all v.

APPENDIX B: PROOF OF THEOREM 2
We first show the correctness of the coloring process as given in the following lemma.
Lemma 5: The coloring process correctly colors all the affected vertices.
Proof: We first state the following simple facts without proof: given a relationship tree, after the hyperedge weight increase, (1) if v is pink or white, then all its descendent in this relationship tree are white; (2) if a v is red, then all its children in the relationship tree are either pink or red; (3) if a v is affected, either v ∈ě or P [v] is red. These facts can be directly obtained from the definition of the color. It is also easy to see that vertices are dequeued from M in a nondecreasing order of their current distance D[·]. This is because each time a vertex z is dequeued from M , the possible new vertices to be enqueued into M are z's children with distances no smaller than D[z].
Then, the proof of the lemma has two parts: first we prove that all affected vertices are enqueued into M ; then we prove by induction that only affected vertices are enqueued into M and their colors are correctly identified.
We prove the first part by contradiction. Assume that there exists an affected vertex v that is not enqueued into M . It is easy to see that v ∈ě because all the affected vertices ině are enqueued in Step 1. Based on the third fact stated above, P [v] is red. Based on the hypothesis, P [v] is not enqueued (otherwise, v will be enqueued in Step 2). Continue this line of arguments, we eventually reach the root of the relationship tree and arrive at the contradiction that the source s is red.
We prove the second part by induction. It is easy to see that all the vertices initially enqueued into M are affected vertices. It remains to show that the first vertex z 1 dequeued from M is colored (pink or red) correctly. To show that, we need to establish that the algorithm correctly determines whether there is an alternative shortest hyperpath to z 1 with the same distance, i.e., d[z 1 ] = d ′ [z 1 ]. The key here is to show that checking the currently non-red neighbors (which may become red in the future) of z 1 will not lead to a false alternative path. This follows from the fact that z 1 has the smallest distance D[·] among all affected vertices (which belong to the set of vertices consisting of the affected vertices ině and their descendents).
Next, assume that vertices z 1 , z 2 , . . . , z l dequeued from M are all affected vertices and are correctly colored. Consider the next dequeued vertex z l+1 . It is an affected vertex because it is either enqueued in Step 1 with E[v] =ě or enqueued in Step 2 with a red parent. To show that z l+1 will be colored correctly, we use a similar argument by showing that the currently nonred neighbors of z l+1 will not give a false alternative path. The latter follows from the fact that all affected vertices will be enqueued and those dequeued after z l+1 have distances no smaller than D[z l+1 ]. This completes the induction.
We now show that D[v], P [v] and E[v] are correctly maintained for all v. For each red vertex v, its distance is set based on the current shortest distance from a non-red neighbor in Step 3.a. The rest of the algorithm is essentially Gallo's extension of Dijkastra's algorithm with the current initial distance. The correctness of the algorithm thus follows. It is not difficult to see that P [·] and E[·] are correctly updated for both red and pink vertices.


System Combination Using Joint, Binarised Feature Vectors

We describe a method for system combination based on joint, binarised feature vectors. Our method can be used to combine several black-box source systems. We first define a total order on given translation output which can be used to partition an n-best list of translations into a set of pairwise system comparisons. Using this data, we explain how an SVM-based classification model can be trained and how this classifier can be applied to combine translation output on the sentence level. We describe our experiments for the ML4HMT-12 shared task and conclude by giving a summary of our findings and by discussing future extensions and experiments using the proposed approach.

Introduction
Research efforts on machine translation (MT) have resulted in many different methods and MT paradigms, each having individual strengths and weaknesses. There exist approaches following linguistic theory as well as data-driven methods relying on statistical processing with only little linguistic knowledge involved. In recent years, there has also been a lot of research on the automatic combination of machine translation output, resulting in so-called hybrid MT engines.
Regardless of the actual method implemented in a given machine translation system, creating translation output usually requires several, often heterogeneous, features. These can be 1) simple scores, e.g., for language model scores, parser or phrase table probabilities; 2) more complex data such as hierarchical parse trees or word alignment links; or 3) even full parse forests or n-best lists.
Given this wide range of heterogenous features and their diversity, it is very difficult to get an intuitive understanding of the inner workings of the MT engine in question; thus, further research work on the combination of machine translation systems into better, hybrid MT systems seems to be of high importance to the field. To overcome the aforementioned problem of incomprehensible feature values, we propose a method based on Machine Learning (ML) tools, leaving the exact interpretation and weighting of features to the ML algorithms.
The remainder of this paper is structured in the following way. After having set the topic in this section, we briefly describe relevant related work in Section 2 before defining and explaining our Machine-Learning-based hybrid MT framework in Section 3. We first give an overview on the basic approach in Subsection 3.1 and then discuss the two most important components: the order on translations is defined in Subsection 3.2 while the notion of joint, binarised feature vectors for ML is introduced in Subsection 3.3. We discuss the experiments conducted for the ML4HMT-12 shared task in Section 4 and then conclude by giving a summary of our findings and by discussing upcoming research in Section 5.

Related Work
Hybrid machine translation methods and system combination approaches have been receiving a lot of research attention over the last decade. Several papers, including seminal work from (Frederking and Nirenburg, 1994), support the general belief that it is possible to combine translation output from different systems achieving an improvement over the individual baseline systems. System combination on the phrasal level can be realised using so-called Confusion Networks. Previous work on this approach are described in more detail in (Federmann et al., 2009;Federmann and Hunsicker, 2011). The algorithm chooses one of the given MT systems as backbone or skeleton of the hybrid translation, while all other translations are connected using word alignment techniques. Together, the systems then form a network with different paths through the network resulting in different translations.
Next to phrasal combination methods, there also are approaches that focus on preserving the syntactic structure of the translation backbone, and hence perform Sentence-based Combination.
Here, several given black-box translations are re-scored or re-ranked in order to determine the best translation for a given sentence in the source text. This is similar to Re-ranking Approaches in SMT. See related work from (Avramidis, 2011), (Gamon et al., 2005), or (Rosti et al., 2007).
Finally, there are Machine-Learning-based Combination approaches which train classifiers to assess the quality of given translation output. Recent work (He et al., 2010) applies such Machine Learning tools to estimate translation quality and re-rank a set of translations on the sentence level.

Classification-Based Hybrid MT
In this Section, we describe our architecture for hybrid machine translation. It is based on classifiers trained using state-of-the-art Machine-Learning tools. Given a set of n translations from several systems that are treated as "black boxes" and a development set including corresponding reference, we perform the following processing steps to generate a hybrid translation for some given test set: 1. Compute a total order of individual system output on the development set using some order relation based on quality assessment of the translations with automatic metrics. This can also be defined to include results from, e.g., manual evaluation; 2. Decompose the aforementioned system ranking into a set of pairwise comparisons for any two pairs of systems A, B. As we do not allow for ties in our system comparisons, the two possible values A > B, A < B also represent our Machine-Learning classes +1/−1, respectively; 3. Annotate the translations with feature values derived from NLP tools such as language models, part-of-speech taggers, or parsers; 4. Create a data set for training an SVM-based classifier that can estimate which of two given systems A, B is better according to the available features; 5. Train an SVM-based classifier model using, e.g., libSVM, see (Chang and Lin, 2011); Steps 1-5 represent the training phase in our framework. The availability of a development set including references is required as this is needed to allow the definition of an ordering relation which subsequently defines the training instances for the SVM-based classifier. After training, we can use the classifier as follows: 6. Apply the resulting classification onto the candidate translations from the given test set. This will produce pairwise estimates +1/−1 for each possible pair of systems A, B; 7. Perform round-robin system elimination to determine the single best system from the set of candidate translations on a per sentence level; 8. Using this data, synthesise the final, hybrid translation output.
Steps 6 − 8 represent the decoding phase in which the trained classifier is applied to a set of unseen translations without any reference text available. By computing pairwise winners for each possible pair of systems and each individual sentence of the test set, we determine the single best system on the sentence level. The methodology is explained in more detail in (Federmann, 2012b,c).

A Total Order on Translations
In order to rank the given source translations, we first need to define an ordering relation over the set of translation outputs. For this, we consider manual judgements wherever available and, as a fallback, also apply three renowned evaluation metrics which are the de-facto standards for automated assessment of machine translation quality: 1. The Meteor score, on the sentence and on the corpus level, see (Denkowski and Lavie, 2011); 2. The NIST n-gram cooccurence score on the corpus level, see (Doddington, 2002); and 3. The BLEU score which is the most widely used evaluation metric, see (Papineni et al., 2002).
While both the BLEU and the NIST scores are designed to have a high correlation with judgements from manual evaluation on the corpus level, the Meteor metric can also be used to meaningfully compare translation output on the level of individual sentences. We make use of this property when defining our order or d(A, B) on translations, as described in (Federmann, 2012c).

Using Joint, Binarised Feature Vectors
Many Machine-Learning-based approaches for system combination use classifiers to estimate the quality of or confidence in an individual translation output and compare it to other translations afterwards. This means that the feature vector for a given translation A is computed solely on information available from features of A, not considering any other translation B as additional source of information, or formally: . . .
We aim to explicitly model pairwise feature comparisons of translations A, B, storing binary values to model if a given feature value f x (A) for system A is better or worse than corresponding feature value f x (B) for the competing system B. Effectively, this means that, in our approach, we compare translations directly when constructing the set of training instances. Equation 2 shows the formal definition of a so-called joint, binarised feature vector: The reason to store binary features values f x ∈ lies in the fact that these can be processed more efficiently during SVM training. Also, previous experiments (Federmann, 2012a;Hunsicker et al., 2012) have shown that the usage of actual feature values f x ∈ in the feature vector does not give any additional benefit so that we decided to switch to binary notation instead 1 . Note that the order in which features for translations A, B are compared does not strictly matter. For the sake of consistency, we have decided to compare feature values using simple A > B operations, leaving the actual interpretation of these values or their polarity to the Machine Learning toolkit.

Creating Translations Using a Classifier
Given an SVM classifier trained on joint, binary feature vectors as previously described, we can now create hybrid translation output. A schematic overview is depicted in Figure 1. We compute the best translation for each sentence in the test set, based on the +1/−1 output of the classifier for a total of n(n−1) 2 unique comparisons.
For each sentence, we create a lookup table that stores for some system X the set of systems which were outperformed by X according to our classifier. Figure 1: Schematic overview illustrating how an SVM classifier can be used to determine the single best translation using round robin playoff elimination. This operates on the sentence level.
classified by the SVM classifier. Only systems winning at least once during these comparisons end up as keys in our table. The cardinality of the resulting set of outperformed systems implicitly represents the number of wins for a system X . There are three cases to consider: 1. There is exactly one top-ranked system which becomes the translation for the current sentence; 2. Two systems are top-ranked, so the decision depends on the comparison of these. As we do not allow for ties in our comparisons, this is guaranteed to determine a single winner; 3. If more than two systems are top-ranked, we check if one of the systems outperforms the others. In rare cases, this may not yield a winner and we have to fall back to a pre-defined winner, usually the best system from training.

Experiments
We worked on a submission for language pair Spanish→English. For this language pair, translation output from four different translation engines was made available by the organisers of the shared task. For each of the systems both translation output and system-specific annotations could be used. As our method relies on comparable features, we decided to extract features for all candidate systems ourselves, hence constraining ourselves to only using the given translation output.
We created the data set for classifier training using the following selection of linguistic features: -number of target tokens, parse tree nodes, and parse tree depth; -ratio of target/source tokens, parse tree nodes, and parse tree depth; -n-gram score for n-gram order n ∈ {1, . . . , 5}; -perplexity for n-gram order n ∈ {1, . . . , 5}.
These features represent a combination of (shallow) parsing and language model scoring and are derived from the set of features that are most often used in the Machine-Learning-based system combination literature.
We use the Stanford Parser (Klein and Manning, 2003) to process the source text and the corresponding translations. For language model scoring, we use the SRILM toolkit (Stolcke, 2002) training a 5-gram language model for English. In this work, we do not consider any source language models.  Figure 2 shows the optimisation grids for linear (left), polynomial (middle), and sigmoid (right) kernels. Note how the decision boundary of the optimal area manifests itself from left to right. We ended up using a sigmoid kernel (C = 2, γ = 0.015625) and observed a prediction rate of 68.9608% on the training instances.

Conclusion
We have described our submission to the ML4HMT-12 shared task which is based on a Machine-Learning-based framework for hybrid Machine Translation. Using so-called joint, binarised feature vectors, we implemented an algorithm that applies an SVM-based classifier to generate hybrid translations for the language pair Spanish→English. Combination is done on the sentence level.
Upcoming work will involve the refinement of our set of linguistic features and subsequent training and tuning of a Machine Learning classifier to improve the proposed method on additional data. We have already achieved promising baseline results in this respect and look forward to further test our approach, e.g., for ML4HMT-12's second language pair Chinese→English.
The total order on translation output described in Section 3 can be altered to also consider results from manual judgements regarding translation quality. This has not yet been used for our submission, but it would be an interesting extension of this paper.


extfieldsofstudy:
Computer Science
Mathematics

text:
A metric learning perspective of SVM: on the relation of SVM and LMNN

Support Vector Machines, SVMs, and the Large Margin Nearest Neighbor algorithm, LMNN, are two very popular learning algorithms with quite different learning biases. In this paper we bring them into a unified view and show that they have a much stronger relation than what is commonly thought. We analyze SVMs from a metric learning perspective and cast them as a metric learning problem, a view which helps us uncover the relations of the two algorithms. We show that LMNN can be seen as learning a set of local SVM-like models in a quadratic space. Along the way and inspired by the metric-based interpretation of SVM s we derive a novel variant of SVMs, epsilon-SVM, to which LMNN is even more similar. We give a unified view of LMNN and the different SVM variants. Finally we provide some preliminary experiments on a number of benchmark datasets in which show that epsilon-SVM compares favorably both with respect to LMNN and SVM.

Introduction
Support Vector Machines, [2], and metric learning algorithms, [15,8,9,16], are two very popular learning paradigms with quite distinct learning biases. In this paper we focus on SVMs and LMNN, one of the most prominent metric learning algorithms, [15]; we bring them into a unified view and show that they have a much stronger relation than what is commonly accepted. We show that SVM can be formulated as a metric learning problem, a fact which provides new insights to it. Based on these insights and employing learning biases typically used in metric learning we propose -SVM, a novel SVM variant which is shown to empirically outperform SVM. -SVM relates, but is simpler, to the radius-margin ratio error bound optimization that is often used when SVM is coupled with feature selection and weighting, [12,5], and multiple kernel learning [1,4,7]. More importantly we demonstrate a very strong and previously unknown connection between LMNN and SVM. Until now LMNN has been considered as the distance-based counterpart of SVM, in the somehow shallow sense that both use some concept of margin, even though their respective margin concepts are defined differently, and the hinge loss function, within a convex optimization problem. We show that the relation between LMNN and SVM is much deeper and demonstrate that LMNN can be seen as a set of local SVM-like classifiers in a quadratic space. In fact we show that LMNN is even more similar to -SVM than SVM. This strong connection has the potential to lead to more efficient LMNN implementations, especially for large scale problems and vice versa, to lead to more efficient schema of multiclass SVM. Moreover the result is also valid for other large margin metric learning algorithms. Finally we use the metric-based view to provide a unified view of SVM, -SVM and LMNN.
Overall the main contribution of the paper is the unified view of LMNN, SVM and the variants of the latter. Along the way we also devise a new algorithm, -SVM, that combines ideas from both SVM and LMNN and finds its support in the SVM error bound.
In the next section we will briefly describe the basic concepts of SVM and LMNN. In section 2 we describe SVM in the metric learning view and the new insights that this view brings. We also discuss some invariant properties of SVM and how metric learning may or may not help to improve SVM. Section 3 describes -arXiv:1201.4714v1 [cs.LG] 23 Jan 2012 SVM, a metric-learning and SVM inspired algorithm. Section 4 discusses the relation of LMNN and SVM, and provides a unified view of the different SVM and LMNN variants. In section 6 we give some experimental results for -SVM and compare it with SVM and LMNN. Finally we conclude in section 7.

Basic SVM and LMNN concepts
We consider a binary classification problem in which we are given a set of n learning instances S = {(x 1 , y 1 ), ..., (x n , y n )}, x i ∈ R d , where y i is the class label of the x i instance and y i ∈ {+1, −1}. We denote by x p the l p norm of the x vector. Let H w be a hyperplane given by SVMs learn a hyperplane H w which separates the two classes and has maximum margin γ, which is, informally, the distance of the nearest instances from H w : [2]. The optimization problem that SVMs solve is: which is usually rewritten to avoid the uniform scaling problem with w, b, as: The margin maximization is motivated by the SVM error bound which is a function of the R 2 /γ 2 ratio; R is the radius of the smallest sphere that contains the learning instances. Standard SVMs only focus on the margin and ignore the radius because for a given feature space this is fixed. However the R 2 /γ 2 ratio has been used as an optimization criterion in several cases, for feature selection, feature weighting and multiple kernel learning [1,12,4,5,7]. The biggest challenge when using the radius-margin bound is that it leads to non convex optimization problems.
In metric learning we learn a Mahalanobis metric parametrized by a Positive Semi-Definite (PSD) matrix M under some cost function and some constraints on the Mahalanobis distances of same and different class instances. The squared Mahalanobis distance has the following form d 2 . M can be rewritten as M = L T L, i.e the Mahalanobis distance computation can be considered as a two-step procedure, that first computes a linear transformation of the instances given by the matrix L and then the Euclidean distance in the transformed space, i.e LMNN, one of the most popular metric learning methods, also works based on the concept of margin which is nevertheless different from that of SVM. While the SVM margin is defined globally with respect to a hyperplane, the LMNN margin is defined locally with respect to center points. The LMNN margin, γ x0 , of a center point, instance x 0 , is given by: where targ(x 0 ) is the set of the target neighbors of x 0 , which is defined as targ( The neighborhood can be defined either as a k nearest neighbors or as a sphere of some radius.
LMNN maximizes the sum of the margins of all instances. The underlying idea is that it learns a metric M or a linear transformation L which brings instances close to their same class center point while it moves away from it different class instances with a margin of one. This learning bias is commonly referred as large margin metric learning [13,15,14,10]. LMNN optimization problem is [15]:

SVM under a metric learning view
We can formulate the SVM learning problem as a metric learning problem in which the learned transformation matrix is diagonal. To do so we will first define a new metric learning problem and then we will show its equivalence to SVM.
We start by introducing the fixed hyperplane H 1 , the normal vector of which is 1 (a d-dimensional vector of ones), i.e. H 1 : We now define the margin γ of two classes with respect to the hyperplane H 1 as the minimum absolute difference of the distances of any two, differentclass instances,x i ,x j , projected to the norm vector of H 1 hyperplane, which can be finally written as: γ = min i,j,yi =yj In fact this is the SVM margin, see equation (17) in Appendix.
We are interested in that linear transformation, diag(W) = w, for which it holds y i (w T x i + b) ≥ 0, i.e. the instances of the two classes lie on two different sides of the hyperplane H 1 , and which has a maximum margin. This is achieved by the following metric-learning optimization problem 1 : Additionally we prefer the W transformation that places the two classes "symmetrically" with respect to the H 1 hyperplane, i.e. the separating hyperplane is at the middle of the margin instances of the two classes: Notice that this can always be achieved by adjusting the translation parameter b by adding to it the γ1−γ2 2 value, where γ 1 and γ 2 are respectively the margins of the y 1 and y 2 classes to the H 1 hyperplane. Hence the parameter b of the H 1 hyperplane can be removed and replaced by an equivalent translation transformation b. From now on, we assume H 1 : 1 T x + 0 = 0 and we add a translation b after the linear transformation W. With this 'symmetry' preference, (6) can be reformulated as (see the detailed proof in Appendix): This optimization problem learns a diagonal transformation W and a translation b which maximize the margin and place the classes 'symmetrically' to the H 1 : 1 T x = 0 hyperplane. However this optimization problem scales with the w (as is the case with the SVM formulation (1)). Therefore we need a way to control the uniform scaling of w. One way is to fix some norm of w e.g. w p = 1, and the optimization problem becomes: Notice that both problems (7) and (8) are still different from the standard SVM formulation given in (1) or (2). However it can be shown that they are in fact equivalent to SVM; for the detailed proof see in the Appendix.
Thus we see that starting from a Mahalanobis metric learning problem (5), i.e learning a linear transformation W, and with the appropriate cost function and constraints on pairwise distances, we arrive to a standard SVM learning problem. We can describe SVM in the metric learning jargon as follows: it learns a diagonal linear transformation W and a translation b which maximize the margin and place the two classes symmetrically in the opposite sides of the hyperplane H 1 : 1 T x = 0. In the standard view of SVM, the space is fixed and the hyperplane is moved around to achieve the optimal margin. In the metric view of SVM, the hyperplane is fixed to H 1 and the space is scaled, W, and then translated, b, so that the instances are placed optimally around H 1 . Introducing a fixed hyperplane H 1 will provide various advantages in relation to the different radius-margin SVM versions and LMNN as we will show soon. It is also worth to note that the SVM metric view holds true for any kernel space, since its final optimization problem is the same as that of standard SVM, i.e we can kernelize it directly as SVM.
From the metric learning perspective, one may think that learning a full linear transformation instead of a diagonal could bring more advantage, however as we will see right away this is not true for the case of SVM. For any linear transformation L (full matrix), the distance of Lx to the hyperplane where D L is a diagonal matrix, in which the k diagonal element corresponds to the sum of the elements of the kth column of L: D Lkk = i L ik . So for any full transformation matrix L there exists a diagonal transformation D L which has the same signed distance to the hyperplane. This is also true for any hyperplane w T x + b where w does not contain any zero elements. Thus learning a full matrix does not bring any additional advantage to SVM.

3
-SVM, an alternative to the radius-margin approach This bias is often implemented through local or global constraints on the pair-wise distances of sameclass and different-class instances which make the between class distance large and the within class distance small. Under the metric view of SVM we see that the learned linear transformation does control the between class distance by maximizing the margin, but it ignores the within class distance. Inspired by the metric learning biases we will extend the SVM under the metric view and incorporate constraints on the within-class distance which we will minimize.
We can quantify the within class distance with a number of different ways such as the sum of instance distances from the centers of their class, as in Fisher Discriminant Analysis (FDA) [11], or by the pairwise distances of the instances of each class, as it is done in several metric learning algorithms [16,3,15]. Yet another way to indirectly minimize the within class distance is by minimizing the total data spread while maximizing the between class distance. One measure of the total data spread is the radius, R, of the sphere that contains the data; so by minimizing the radius-margin ratio, R 2 /γ 2 , we can naturally minimize the within class distance while maximizing the between. Interestingly the SVM theoretical error bound points towards the minimization of the same quantity, i.e. the radiusmargin ratio, thus the proposed metric learning bias finds its theoretical support in the SVM error bound. However optimizing over the margin and the radius poses several difficulties since the radius is computed in a complex form, [12,4,7].
We can avoid the problems that are caused by the radius by using a different quantity to indirectly control the within class distance. We propose to minimize instead of the radius, the sum of the instance distances from the margin hyperplane, this sum is yet another way to control the data spread. We will call the resulting algorithm, which in addition to the margin maximization also minimizes the within-class-distance through the sum of the instance distances from the margin hyperplane, -SVM. The minimization of the sum has a similar effect to the minimization of the SVM radius, Figure 1. In a later section we will show that -SVM can be seen as a bridge between LMNN and SVM.
We define the optimization problem of -SVM as follows: select the transformations, one linear diagonal, diag(W) = w, and one translation, b, which maximize the margin and keep the instances symmetrically and within a small distance from the H 1 hyperplane. This is achieved by the following optimization problem: penalizes instances which lie on the correct side of the hyperplane but are far from the margin. max(0, 1 − y i (w T x i + b) is the SVM hinge loss which penalize instances violating the margin. (9) is equivalent to: where ξ i is the standard SVM slack variable for instance i and η i the distance of that instance from the margin hyperplane. The dual form of this optimization problem is: (11) Note that we have two hyper-parameters C and λ, typically we will assign a higher value to the C since we tolerate less the violations of the margin compared to a larger data spread. The two parameters control the trade off between the importance of the margin and the within data spread.

On the relation of LMNN and SVM
In this section we demonstrate the relation between LMNN and SVM. Lets define a quadratic mapping . We will show that the LMNN margin in the original space is the SVM margin in this quadratic space.
Concretely, the squared distance of an instance x from a center point instance x l in the linearly transformed space that corresponds to the Mahalanobis distance M learned by LMNN can be expressed in a linear form of Φ(x). Let L be the linear transformation associated with the learned Mahalanobis distance M. We have: A more general formulation of the LMNN optimization problem (4) which reflects the same learning bias of LMNN, i.e for each center point, keeps the same-class instances close to the center and pushes different-class instances outside the margin, is: Standard LMNN puts one extra constraint on each γ x l , it sets each of them to one. With this constraint problem (13) reduces to (4). We can rewrite problem (13) as: In this formulation, visualized in fig. 2(a), the target neighbors (marked with ×) of the x l center point are constrained within the C l circle with radius R l and center Lx l while the instances that have a label which is different from that of x l (marked with ) are placed outside the circle C l with center also Lx l and radius R l = R 2 l + γ x l . We denote by β l the difference R l − R l of the radii of the two circles.
If we replace all the d 2 (Lx, Lz) terms in problem (14) with their linear equivalent in the quadratic space, problem (12), and break up the optimization problem to a series of n optimization problems one for each instance x l then we get for each x l the following optimization problem: + λ where w l is not an independent variable but its quadratic and linear components are related as described above (formula (12)).
The instance set B(x l ) = {x i ∈ targ(x l )} ∪ {x i |y i = y l } is the set of all target neighbors and different class instances. In the formula (15) we replace b l by −w T l Φ(x l ) since w T l Φ(x l ) + b l = 0, and b l = b l − (R 2 l + γ x l /2). We denote the hyperplane w T l Φ(x) + b l = 0 by H l , as in fig. 3. Now let y li := y l y i , so y li = 1, ∀x i ∈ targ(x l ) and y lj = −1, ∀(x j |y i = y l ). Therefore −y li (w T l Φ(x i ) + b l ) ≥ γ x l /2 − ξ li , ∀x i ∈ B(x l ). Without loss of generality we can assume that y l = −1 and problem (15) becomes: + λ where w l is still constrained as in (15). It is worth to note that the second constraint of (16) will ensure that d 2 M (x i , x l ) is bigger than or equal to 0, i.e it will almost ensure the PSD of the matrix M 2 . However due to the specific structure of w l , i.e. quadratic and linear part, the PSD constraint of M is guaranteed for any x.
We can think of problem (16) as an extension of an SVM optimization problem. Its training set is the B(x l ) set, i.e. the target neighbors of x l and all instances with different class label from x l . Its cost function includes, in addition to the term that maximizes the margin, also a sum term which forces the target neighbors of x l to have small w T l Φ(x i ) + b l values, i.e. be at small distance from the H l hyperplane.
Minimizing the target neighbor distances from the H l hyperplane makes the distance between support vectors and H l small. It therefore has the effect of bringing the negative margin hyperplane of H l close to H l , bringing thus also the target neighbors close to the negative margin hyperplane. In other words the optimization problem favors a small width for the band that is defined by H l and the negative margin hyperplane described above which contains the target neighbors.
There is an even closer relation of LMNN with a local -SVM applied in the quadratic space that we will describe by comparing the optimization problems given in (9) and (16). -SVM has almost the same learning bias as LMNN, the former maximizes the margin and brings all instances close to the margin hyperplanes, the latter also maximizes the margin but only brings the target neighbors close to the margin hyperplane. For each center point x l the LMNN formulation, problem (16), is very similar to that of -SVM, problem (9), applied in the quadratic space. The second term of the cost function of -SVM together with its constraints force all instances to be close to their respective margin hyperplane, this can be seen more clear in the minimization of the η i in problem (10). In LMNN, problem (16), the third term of the cost function plays a similar role by forcing only the target neighbors to be close to the H l hyperplane. This in turn has the effect, as mentioned above, to reduce the width of the band containing them and bringing them closer to their margin hyperplane; unlike -SVM no such constraint is imposed on the remaining instances. So LMNN is equivalent to n local, modified, -SVMs, one for each instance. -SVM controls the within class distance using the distance to the margin hyperplane and LMNN using the distance to the H l hyperplane.
Note that the n optimization problems are not independent. The different solutions w l have a common component which corresponds to the d(d + 1)/2 quadratic features and is given by the w quad vector. The linear component of w l , w lin l , is a function of the specific x l , as described above. Overall learning a transformation L with LMNN, eq. (4), is equivalent to learning a local SVM-like model, given by H l , for each x l center point in the quadratic space according to problems (15,16). Remember that the w l , b l of the different center points are related, i.e. their common quadratic part is w quad . If we constrain w l , b l to be the same for all x l and drop the PSD constraints on w l then we get the (global) -SVM-like solution.
Visualization: In fig. 2(b) we give a visualization of problem (15) in the quadratic space Φ(x). Figure 2(b) gives the equivalent linear perspective in the quadratic space of the LMNN model in the original space given in fig. 2(a). The center Lx l of the C l circle in fig. 2(a) corresponds to the H l hyperplane in fig. 2(b); the C l circle with center Lx l and radius R l = R l + β l /2 corresponds to the H l separating hyperplane in fig. 2(b). Figure 3(a) illustrates the different local linear models in the quadratic space. We can combine these different local models by employing the metric learning view of SVM and make the relation of LMNN and SVM even more clear. Instead of having many local SVM-like hyperplanes we bring each point Φ(x l ) around the H 1 : 1x + 0 = 0 hyperplane by applying to it first a W l diagonal transformation, W l = w l , and then a translation ( fig. 3(b)). As before with w l the different W l transformations have a common component, which corresponds to the first d(d + 1)/2 elements of the diagonal associated with the quadratic features, given by the w quad vector, and an instance dependent component that corresponds to the linear features which is given by w lin l = −2L T Lx l ; thus the translation transformation is also a function of the spe-cific point x l . Notice that the common component has many more elements than the instance specific component. There is an analogy to multitask learning where models are learned over different tasks-datasets are forced to have parts of their models the same.   Prediction phase Typically after learning a metric through LMNN a k-NN algorithm is used to predict the class of a new instance. Under the interpretation of LMNN as a set of local -SVM linear classifiers this is equivalent to choosing the k local hyperplanes H l : w T l Φ(x) + b l = 0 which are farther away from the new instance and which leave both the new instance and their respective center points on the same side. The farther away the new instance is from an H l local hyperplane the closer it is to the center point associated to H l . In effect this means that we simply choose those hyperplanes-classifiers which are more confident on the label prediction of the new instance, and then we have them vote. In a sense this is similar to an ensemble learning schema in which each time we want to classify a new instance, we select those classifiers that are most confident. Then we have them vote in order to determine the final prediction.

A unified view of LMNN, SVM and its variants
The standard SVM learning problem only optimizes the margin. On the other hand, LMNN, as well as the different variants of radius-margin based SVM under the metric learning view (briefly mentioned in section 3), and -SVM, have additional regularizers that control directly or indirectly the within class distance. LMNN is much closer to a collection of local -SVMs than to local SVMs, since both LMNN and -SVM have that additional regularizer of the within class distance. We briefly summarize the different methods that we discussed: • In standard SVM the space is fixed and the separating hyperplane is moved to find an optimal position in which the margin is maximized. • In standard LMNN we find the linear transformation that maximizes the sum of the local margins of all instances while keeping the neighboring instances of the same class close. • In the metric learning view of SVM we find a linear diagonal transformation W, diag(W) = w plus a translation b that maximize the margin to the fixed hyperplane H 1 , clamping the norm of w to 1, or maximize the norm of w while clamping the margin to 1. • In -SVM we find a linear diagonal transformation and a translation that maximize the margin with respect to the fixed hyperplane H 1 and keep all instances close to H 1 . • Finally in the interpretation of LMNN as a collection of local SVM-like classifiers we find for each instance x a linear transformation and a translation that clamp the margin to one and keep the target neighbors of x within a band the width of which is minimized. These transformations have common components as described in the previous section. LMNN is set of local related -SVMs in the quadratic space.
We will now give a high level picture of the relations of the different methods in the quadratic space Φ(x) by showing how from one method we can move to another by adding or dropping constraints; the complete set of relations is given in Figure 4.
We start with n local non-related SVMs, if we add a constraint on the within-class distance to each of them we get n non-related -SVMs. If we add additional constrains that relate the different local -SVMs, namely by constraining their quadratic components w quad to be the same and PSD, and their linear component w lin l to be a function of w quad and the center point x l then we get LMNN.
If we go back to the original set of non-related SVMs and add a constraint that forces all of them to have the same w l and b l we get the standard global SVM.
Similarly if in the collection of the local -SVMs we add a constraint that forces all of them to have the same optimal hyperplane then we also get the global -SVM. In that case all the component classifiers of the ensemble reduce to one classifier and no voting is necessary.
LMNN constrains the n local -SVMs to have the same quadratic component, w quad , makes the linear components dependent on w quad and their respective center points, accommodating like that the local information, and constrains the quadratic components w quad to reflect the L T L PSD matrix, equation (12). On the other hand both the global SVM and -SVM also constrain their quadratic components to be the same but remove the constraint on the PSD property of w quad ; both constrain all their linear components to be the same, thus they do not incorporate local information. The last constraint is much more restrictive than the additional constrains of LMNN, as a result the global SVM and -SVM models are much more constrained than that of LMNN. Although we demonstrate the relations only for the case of SVM and LMNN they also hold for all other large margin based metric learning algorithms [13,15,14,10].
-SVM builds upon two popular learning biases, namely large margin learning and metric learning and exploits the strengths of both. In addition it finds theoretical support in the radius-margin SVM error bound. -SVM can be seen as a bridge which connects SVM and existing large margin based metric learning algorithms, such as LMNN.

Experiments and results
In addition to studying in detail the relation between the different variants of SVM and metric learning we also examine the performance of the -SVM algorithm.
We experiment with -SVM, eq. (10), and compare its performance to that of a standard l 1 soft margin SVM, and LMNN, with the following kernels: linear, polynomial with degree 2 and 3, Gaussian with σ = 1. C is chosen with 10-fold inner Cross-Validation from the set {0.1, 1, 10, 100, 1000}. For -SVM we choose to set λ  to C/3 reflecting the fact that we tolerate less the margin violations than a larger distance form the margin. We used ten datasets mainly from the UCI repository [6]. Attributes are standardized to have zero mean and one variance; kernels are normalized to have a trace of one. The number of target neighbors for LMNN is set to 5 and its γ parameter is set to 0.5, following the default settings suggested in [15]. We estimated the classification error using 10-fold CV. The results are given in Table 1. Overall each algorithm is applied 40 times (four kernels × ten datasets). Comparing -SVM with SVM we see that the former has a lower error than SVM in 19 out of the 40 applications and a higher error in only nine. A similar picture appears in the -SVM, LMNN, pair where the former has a lower error in 20 out of the 40 applications and a higher in only eight. If we break down the comparison per kernel type, we also see that, i.e. -SVM has a systematic advantage over the other two algorithms no matter which kernel we use.
To examine the statistical significance of the above results we use the McNemar's test of significance, with a significance level of 0.05. Comparing algorithms A and B on a fixed dataset and a fixed kernel algorithm A is credited with one point if it was significantly better than algorithm B, 0.5 points if there was no significance difference between the two algorithms, and zero points otherwise. In Table 2 we report the overall points that each algorithms got and in addition we break them down over the different kernels. -SVM has the highest score with 46 points followed by SVM with 37.5 and LMNN with 36.5. The advantage of -SVM is much more pronounced in the case of the Gaussian kernel. This could be attributed to its additional regularization on the within-class distance which makes it more appropriate for very high dimensional spaces.

Conclusion
In this paper, we have shown how SVM learning can be reformulated as a metric learning problem. Inspired by this reformulation and the metric learning biases, we proposed -SVM, a new SVM-based algorithm in which, in addition to the standard SVM constraints we also minimize a measure of the within class distance. More importantly the metric learning view of SVM helped us uncover a so far unknown connection between the two seemingly very different learning paradigms of SVM and LMNN. LMNN can be seen as a set of local SVM-like classifiers in a quadratic space, and more precisely, as a set of local -SVM-like classifiers. Finally preliminary results show a superior performance of -SVM compared to both SVM and LMNN. Although our discussion was limited to binary classification, it can be extended to the multiclass case. Building on the SVM-LMNN relation, our current work focuses on the full analysis of the multiclass case, a new schema for multiclass SVM which exploits the advantages of both LMNN and kNN in multiclass problems, and finally the exploration of the learning models which are in between the SVM, LMNN models.
With the 'symmetry' preference as described after problem (6), the second constraint of problem (6) can be replaced by the constraint: y i (w T x i + b) ≥ γ/2. Moreover, we can always replace the squared values in problem (6)  If the constraint y i (w T x i + b) ≥ γ/2 is satisfied then w T x i + b and y i have the same sign; therefore any two instances ∀x i , x j which have different labels, (y i = y j ), will lie on the opposite sides of the hyperplane. Hence: Therefore the first constraint of problem (6) is always satisfied if the constraint y i (w T x i + b) ≥ γ/2 is satisfied, thus (6) is equivalent to (7).

Equivalence of (8) to standard SVM formulation
We will show that problem (8) is equivalent to standard SVM. In fact (1) also scales with uniform scaling of w, b and to avoid this problem, w γ is fixed to 1 which lead to the second formula (2). We will show that the two ways of avoiding scaling problem, by forcing w γ = 1 or by forcing w = 1 are equivalent.
Indeed, another way to avoid the scaling problem is to find a quantity which is invariant to the scaling of w. Let γ = t w p , hence t : 0 → ∞, and lets fix w p = 1. Then let P be the feasible set of w which satisfies ( w p = 1 and y i (w T x i + b) ≥ 0, ∀i), and Q = {w| w p = 1 and y i (w T x i + b) ≥ t w p ), ∀i} Notice that, if t = 0 then Q ≡ P , if t > 0 then Q ⊆ P , and if t > t max then Q will be empty. For another value of w p , w p = λ, the corresponding feasible sets are P λ and Q λ . There is a one to one mapping from P to P λ , and from Q to Q λ , and the t max λ which makes Q λ empty is the same as t max . So t max is invariant to the scaling of w. Therefore (8) is equivalent to: The value of the geometric margin here is fixed to 1/ √ d while in standard SVM the geometric margin is γ = 1/ w 2 2 . Using the l 2 norm of w, we get a formulation which is equivalent to that of the hard margin SVM given in (2). Using the l 1 norm of w, we get the 1-norm SVM [17].