Yang Hua

Karteek Alahari

Cordelia Schmid

Online Object Tracking with Proposal Selection

Tracking-by-detection approaches are some of the most successful object trackers in recent years. Their success is largely determined by the detector model they learn initially and then update over time. However, under challenging conditions where an object can undergo transformations, e.g., severe rotation, these methods are found to be lacking. In this paper, we address this problem by formulating it as a proposal selection task and making two contributions. The first one is introducing novel proposals estimated from the geometric transformations undergone by the object, and building a rich candidate set for predicting the object location. The second one is devising a novel selection strategy using multiple cues, i.e., detection score and edgeness score computed from state-of-the-art object edges and motion boundaries. We extensively evaluate our approach on the visual object tracking 2014 challenge and online tracking benchmark datasets, and show the best performance.

Introduction

Over the past few years, the tracking-by-detection framework has emerged as one of the successful paradigms for tracking objects [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF][START_REF] Pang | Finding the best from the second bests -inhibiting subjective bias in evaluation of visual tracking algorithms[END_REF][START_REF] Song | Tracking revisited using RGBD camera: Unified benchmark and baselines[END_REF][START_REF] Wu | Online object tracking: A benchmark[END_REF]. It formulates the tracking problem as the task of detecting an object, which is likely to undergo changes in appearance, size, or become occluded, over time [START_REF] Avidan | Ensemble tracking[END_REF][START_REF] Babenko | Robust object tracking with online multiple instance learning[END_REF][START_REF] Godec | Hough-based tracking of non-rigid objects[END_REF][START_REF] Grabner | Semi-supervised on-line boosting for robust tracking[END_REF][START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Kalal | Tracking-learningdetection[END_REF][START_REF] Leibe | Coupled object detection and tracking from static cameras and moving vehicles[END_REF][START_REF] Ramanan | Tracking people by learning their appearance[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF][START_REF] Wu | Detection and tracking of multiple, partially occluded humans by Bayesian combination of edgelet based part detectors[END_REF]. These approaches begin by training an object detector with an initialization (in the form of a bounding box) in the first frame, and then update this model over time. Naturally, the choice of exemplars used to update and improve the object model is critical [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF][START_REF] Zhang | MEEM: robust tracking via multiple experts using entropy minimization[END_REF]].

Consider the motocross example shown in Figure 1. Here, the target (biker and his motorbike) undergoes several deformations as the biker performs an acrobatics routine, which leads to significant changes in the aspect ratio as well as the rotation angle of the bounding box. State-ofthe-art tracking methods, e.g., [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF], rely on axis-aligned bounding boxes and thus are ill-equipped to capture the accurate extents of the object in such scenarios. In this paper, Figure 1. Sample frames (cropped) from the jogging (top row) and motocross (bottom row) sequences [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF]. The ground truth annotation (green) in the first frame (left) is used to train our tracker and the winner [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] of VOT2014 challenge [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF]. We show these two tracking results (right) on another frame in the sequence. Our method (yellow) successfully tracks objects undergoing deformations unlike [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] (red). Best viewed in pdf.

we aim to address this issue by treating the tracking problem as the task of selecting the best proposal containing the object of interest from several candidates. To this end, we propose a novel method to generate candidates which capture the extents of the object accurately, by estimating the transformation(s) undergone by the object.

The focus of this paper is the problem of tracking a single target in monocular video sequences. The target is provided as a ground truth annotation in the first frame, as in a standard tracking-by-detection setup [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Kalal | Tracking-learningdetection[END_REF]. We learn an object detector model from this annotation and evaluate it in subsequent frames to propose candidate locations that are likely to contain the target. While these proposals are sufficient to track objects undergoing a small subset of transformations over time, such as translation shown in Figure 1-top, they cannot handle generic transformations, e.g., similarity transformation shown in Figure 1-bottom. We address this problem by: (i) introducing novel additional proposals to improve the candidate location set, and (ii) using multiple cues to select the proposal that is most likely to contain the target. Additional proposals are computed by robustly estimating the parameters of similarity transformation (i.e., scaling, translation, rotation) that the target is likely to have undergone, with a Hough transform voting scheme on the optical flow. With these parameters, we propose several candidate locations for the target. Thus, for every frame of the video sequence, our candidate set consists of object detector boxes as well as geometry estimation proposals. Note that state-of-the-art tracking-by-detection approaches are limited to detector proposals alone. The second contribution we make is in selecting the best proposal from the candidate set using multiple cues -objectness scores [START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF] computed with edge responses [START_REF] Dollár | Structured forests for fast edge detection[END_REF] and motion boundaries [START_REF] Weinzaepfel | Learning to detect motion boundaries[END_REF], and the detection score.

We evaluate the performance of our approach exhaustively on two recent benchmark datasets, namely the visual object tracking (VOT) 2014 challenge dataset [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF] and the online tracking benchmark (OTB) [START_REF] Wu | Online object tracking: A benchmark[END_REF]. Furthermore, we compare with all the 38 trackers evaluated as part of the VOT2014 challenge, and with the best performers [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF][START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF] among the 29 methods analyzed in the OTB comparison paper [START_REF] Wu | Online object tracking: A benchmark[END_REF]. Our method shows the top performance on both these challenging datasets, and is in particular 29.5% better than the current leader [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] of the VOT2014 challenge.

The remainder of the paper is organized as follows. In Section 2 we discuss related work. The details of our novel proposals and the multiple cues to select the best candidate are explained in Section 3. Section 4 discusses the implementation details of the methods. In Section 5 we present an extensive evaluation of the proposed method and compare it with the state of the art. This section also discusses the datasets and evaluation protocols. Concluding remarks are made in Section 6.

Related Work

Two of the key elements of any tracking algorithm are, how the object of interest is represented, and how this representation is used to localize it in each frame. Several methods have been proposed on these two fronts. Object representation has evolved from classical colour histograms [START_REF] Comaniciu | Kernel-based object tracking[END_REF] to models learned from generative [START_REF] Lee | Visual tracking and recognition using probabilistic appearance manifolds[END_REF][START_REF] Mei | Robust visual tracking and vehicle classification via sparse representation[END_REF][START_REF] Ross | Incremental learning for robust visual tracking[END_REF] or discriminative [START_REF] Avidan | Ensemble tracking[END_REF][START_REF] Collins | Online selection of discriminative tracking features[END_REF][START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF] approaches. In the context of localizing the object given a representation, methods such as [START_REF] Badrinarayanan | Probabilistic color and adaptive multi-feature tracking with dynamically switched priority between cues[END_REF][START_REF] Birchfield | Elliptical head tracking using intensity gradients and color histograms[END_REF][START_REF] Isard | ICONDENSATION: Unifying lowlevel and high-level tracking in a stochastic framework[END_REF][START_REF] Park | Robust visual tracking using autoregressive hidden Markov model[END_REF][START_REF] Pérez | Data fusion for visual tracking with particles[END_REF][START_REF] Spengler | Towards robust multi-cue integration for visual tracking[END_REF][START_REF] Stenger | Learning to track with multiple observers[END_REF] have incorporated multiple cues and fused their results with Markov chain Monte Carlo [START_REF] Park | Robust visual tracking using autoregressive hidden Markov model[END_REF] or particle filtering [START_REF] Isard | ICONDENSATION: Unifying lowlevel and high-level tracking in a stochastic framework[END_REF]. More recently, inspired by the success of object detection algorithms [START_REF] Everingham | The PASCAL visual object classes (VOC) challenge[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], the trackingby-detection approach [START_REF] Avidan | Ensemble tracking[END_REF][START_REF] Babenko | Robust object tracking with online multiple instance learning[END_REF][START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Kalal | Tracking-learningdetection[END_REF][START_REF] Leibe | Coupled object detection and tracking from static cameras and moving vehicles[END_REF][START_REF] Ramanan | Tracking people by learning their appearance[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF][START_REF] Zhang | MEEM: robust tracking via multiple experts using entropy minimization[END_REF] has gained popularity. In fact, methods based on this paradigm are ranked among the top performers on evaluation benchmarks [START_REF] Pang | Finding the best from the second bests -inhibiting subjective bias in evaluation of visual tracking algorithms[END_REF][START_REF] Wu | Online object tracking: A benchmark[END_REF].

Tracking-by-detection methods learn an initial discriminative model of the object from the first frame in the sequence (e.g., with a support vector machine (SVM) [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF]), evaluate it to detect the most likely object location in subsequent frames, and then update the object model with these new detections. Struck [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF] is an interesting variant of this general framework, using a structured output formulation to learn and update the detector. This shows state-ofthe-art results in several scenarios, but lacks the capability of handling severe occlusions and suffers from drift, as discussed in [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF].

To avoid the well-known problem of drift [START_REF] Matthews | The template update problem[END_REF], some methods explicitly detect tracking failures and occlusions with heuristics [START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF], combine detector-and tracker-based components [START_REF] Kalal | Tracking-learningdetection[END_REF], control the training set with learning [START_REF] Supancic | Self-paced learning for long-term tracking[END_REF], or maintain a pool of trackers [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF][START_REF] Kwon | Tracking by sampling trackers[END_REF][START_REF] Zhang | MEEM: robust tracking via multiple experts using entropy minimization[END_REF]. Kalal et al. [START_REF] Kalal | Tracking-learningdetection[END_REF] combine predictions from a variant of the Lukas-Kanade tracker and an incrementally updated detector. More specifically, the results of the tracker provide training data to update the detector model, and the detector re-initializes the tracker when it fails. This interleaving of tracker and detector, although interesting, is restrictive as the object model is a set of fixed-size template patches, and thus, not robust to severe changes in object size.

Supancic and Ramanan [START_REF] Supancic | Self-paced learning for long-term tracking[END_REF] propose a self-paced learning scheme to select training examples for updating the detector model. A pre-fixed number of (top k) frames are chosen carefully according to an SVM objective function to avoid corrupting the training set. In other words, only frames with confident detections are used to update the model. This approach, however, lacks the ability to handle commonly-occurring scenarios where the object is undergoing a geometric transformation, such as the rotation shown in Figure 1-bottom. Hua et al. [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF] address this by using long-term trajectories to estimate the transformations undergone by the object. However, their approach is: (i) inherently offline, requiring all the frames in the video sequence to track, (ii) not robust to significant changes in scale, (iii) maintains a pool of trackers, all of which need to be evaluated independently in every frame.

Despite the general success of tracking-by-detection approaches, they have an important shortcoming. They all rely solely on a detector, and are thus unable to cope with transformations an object can undergo. On the other hand, key point based trackers like CMT [START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF] detect key points in a frame, match them to the next frame and can estimate transformations, such as changes in scale and rotation. However, they are highly sensitive to the success of key point detection algorithms and lack a learned model. Indeed, this is evident from the poor performance on the VOT dataset (see Section 5.2). The main focus of this paper is to address the gap between these two paradigms. Inspired by successful object proposal methods for segmentation and detection [START_REF] Alexe | Measuring the objectness of image windows[END_REF][START_REF] Carreira | Constrained parametric min-cuts for automatic object segmentation[END_REF], we pose the tracking problem as the task of finding the best proposal from a candidate set. In contrast to previous work, we introduce novel proposals estimated from the geometric transformations undergone by the object of interest, and build a rich candidate set for predicting the object location, see Figure 2. In essence, our candidate set consists of proposals from the detector as well as the geometry estimation model. We then devise a novel scoring mechanism using standard object detector score, together with object edgeness [START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF] computed from state-of-the-art edge detector SED [START_REF] Dollár | Structured forests for fast edge detection[END_REF] and motion boundary detector [START_REF] Weinzaepfel | Learning to detect motion boundaries[END_REF] to find the most likely location of the object.

Proposal Selection for Tracking

The main components of our framework for online object tracking are: (i) learning the initial detector, (ii) building a rich candidate set of object locations in each frame, consisting of proposals from the detector as well as the estimated geometric transformations, (iii) evaluating all the proposals in each frame with multiple cues to select the best one, and (iv) updating the detector model. We now present all these components and then provide implementation details in Section 4.

Initial detector

We learn the initial detector model with a training set consisting of one positive sample, available as a bounding box annotation in the first frame, and several negative bounding box samples which are automatically extracted from the entire image. We use HOG features [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] computed for these bounding boxes and learn the detector with a linear SVM, similar to other tracking-by-detection approaches [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF]. The detector is then evaluated on subsequent frames to estimate the candidate locations of the object. Rather than make a suboptimal decision by choosing the best detection as the object location in a frame, we extract the top k detections and build a candidate set. We augment this set with proposals estimated from the transformations undergone by the object, as described in the following section.

Estimating geometry and proposals

In the examples shown in Figure 2, the object of interest is undergoing a geometric transformation (rotation in these examples). None of the top detector proposals can capture the object accurately in this case. To address this issue, we explicitly estimate the transformation undergone by the object and then use it to enrich the candidate set with additional geometric proposals.

We represent the geometric transformation with a similarity matrix [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. Note that other transformations like homography can also be used. The similarity transformation is defined by four parameters -one each for rotation and scale, and two for translation. In this work, we estimate them with a Hough transform voting scheme using frame-to-frame optical flow correspondences. We begin by computing the optical flow between frames t -1 and t with a state-of-the-art flow estimation method [START_REF] Brox | Large displacement optical flow: Descriptor matching in variational motion estimation[END_REF]. The pixels within the object Figure 2. Two sequences from the VOT dataset [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF]. In each row, we show the ground truth (in green) in the first frame (left) and the best geometry proposal in a subsequent frame (in yellow in the right image). We show a vertical line on each box to visualize the rotation angle with respect to image edges.

bounding box with flow values in frame t -1 then give us corresponding pixels in frame t. With a pair of these matches, given by two pixels in t -1 which are sufficiently distant from each other, we estimate the four scalar parameters in the similarity matrix [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. Every choice of a pair of corresponding matches gives us an estimate of the four parameters. We then use the Hough transform [START_REF] Hough | Method and means for recognizing complex patterns[END_REF], wherein each pair of point-matches votes for a (4D) parameter set, to find the top k consistent parameter sets. This voting scheme allows us to filter out the incorrect correspondences due to common errors in optical flow estimation.

To sum up, we estimate the k most likely geometric transformations undergone by the object as the parameters with the top k votes. Each one of these transformations results in a candidate location of the object in t, by applying the corresponding similarity matrix to the object bounding box in t -1. Before adding all these k proposals to the candidate set, we perform an additional filtering step to ensure further robustness. To this end, we discard all the proposals: (i) which have a low confidence, given by the number of votes, normalized by the total number of point-matches, and (ii) those where the estimated angle is significantly different from estimations in earlier frames. We determine both these threshold values with Kalman filtering [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF]. A threshold τ t , used for filtering proposals in frame t + 1, is given by:

τ t = ατ t-1 + k t (d t -αβτ t-1 ),
(1)

k t = (p t-1 + q)/(p t-1 + q + r), (2)
p t = (1 -k t )(p t-1 + q), (3)
where α, β, q, r are scalar parameters set empirically (see Section 4), k t is the Kalman gain, p t is the error estimate.

The filter is initialized with τ 0 = 0, p 0 = 0.1. Here, d t is either the confidence score or the estimated angle of the selected proposal in frame t to determine the respective threshold.

Selecting proposals

At the end of the geometry estimation step, we have k proposals from the detector and (at most) k proposals from the similarity transformation in frame t. Now, the task is to find the best proposal most likely to contain the object in this frame. We use three cues, detection confidence score, objectness measures computed with object edges and motion boundaries, for this task. We first use the (normalized) detection confidence score computed for each proposal box with the SVM learned from the object annotation in the first frame and updated during tracking. This provides information directly relevant to the object of interest in a given sequence.

In cases where the detection scores of all the candidate boxes are statistically similar, we use cues extracted from object edges [START_REF] Dollár | Structured forests for fast edge detection[END_REF] and motion boundaries [START_REF] Weinzaepfel | Learning to detect motion boundaries[END_REF] in the image, referred to as edgeness scores. In other words, when the detection scores are inconclusive to choose the best proposal, we rely on edgeness measure. Here, all the top candidates contain the object of interest to some extent, and the task is to choose the one that best contains the object-a scenario well-suited for edgeness cue because a proposal box which accurately localizes the entire object has a stronger edge response compared to a box which overlaps partially with the object, thus resulting in a weaker edge score. The edgeness score is given by the number of edges (or motion boundaries) within a proposal box after discarding contours that intersect with the box's boundary, as in [START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF]. We compute edgeness scores with edges and motion boundaries separately and use the one with a stronger response. As shown in the examples in Figure 3, these two cues are complementary. Then, the proposal with the best edgeness score is selected.

We follow this approach, rather than using a combined score, e.g., a weighted combination of SVM and edgeness scores, because setting this weight manually is suboptimal, and learning it is not possible due to the lack of standard training-validation-test datasets for tracking. In contrast, our approach uses object-specific SVM and generic edgeness scores effectively, and circumvents the need for a manually set weight to combine scores.

Updating the detector

Having computed the best proposal containing the object, box t , we use it as a positive exemplar to learn a new object model. In practice, we update the current model incrementally with this new sample; see Section 4. This new detector is then evaluated in frame t+1, to continue tracking the object. Algorithm 1 summarizes our overall approach.

Implementation Details

Detector. The initial detector is trained with the one positive sample (provided as ground truth box in the first frame) and several negative examples extracted from the frame. We harvest bounding boxes that overlap less than 50% with the ground truth for the negative set. The regularization parameter in the SVM cost function is set to 0.1 in all our experiments. This cost function is minimized with LIBLIN-EAR [START_REF] Fan | LIBLINEAR: A library for large linear classification[END_REF]. We perform three rounds of hard negative mining to refine the detector. The detector scores are calibrated with Platt's method [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF] using jittered versions of the positive sample (100 positive and negative samples each). For the VOT dataset, an additional step is introduced to train with rotated bounding box annotations. We estimated the rotation angle between one edge of the box and the corresponding image axis,1 rectified the image with this angle, and extracted an axis-aligned box as the positive sample.

The detector was evaluated at seven scales: {0.980, 0.990, 0.995, 1.000, 1.005, 1.010, 1.020}, in every frame. This is done densely in each scale, with a step size of 2 pixels. In the rotated bounding box case, we rectify the image with the angle estimated during training, before evaluating the detector. We set k = 5 to select the top 5 detection results and also (at most) 5 geometry proposals to form the candidate set. The best proposal box t selected from all the candidates in a frame is used to update the detector with a warm-start scheme [START_REF] Fan | LIBLINEAR: A library for large linear classification[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF]. We then perform hard negative mining and calibrate the scores to complete the detector update step. For computational efficiency, the detector is evaluated in a region around the previously estimated object location, instead of the entire image.

Hough voting. The geometric transformation is estimated only when the mean 2 norm of optical flow in box t-1 is larger than 0.5. This ensures that there is sufficient motion in the frame to justify estimating a transformation. We use two pixels in t-1 and their corresponding points in t to vote for the geometric transformation parameters. In practice, pixels that are at least 25 pixels apart from each other in t -1 were chosen randomly for a reliable estimation. To aggregate the votes, a pseudo-random hash function of bin values is used to vote into a one-dimensional hash table, instead of a four-dimensional array, similar to [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The bin size for scale is set to 0.1, and 2.0 for angle and the two translation parameters. Finally, we take the least-squares solution of all the candidates that vote for a particular bin, making our geometry estimation further robust.

Pruning proposals. The parameters of the Kalman filter to discard weak geometry proposals are set as: α = 1, β = 1, process error variance q = 0.001, and measurement error variance r = 0.01 in all our experiments. To find the best proposal from a candidate set, we propose two cues: detection and edgeness scores. Edgeness scores are used to determine the best proposal when the detection scores are inconclusive, i.e., when one or more proposals differ from the best detection score by at most 1%. However, edgeness scores can often be corrupted by noise, e.g., low-quality images that are common in benchmark datasets. We ensure that these scores are used only when they are comparable to the mean score of the previous 5 frames, i.e., the difference between the highest edgeness score and the mean is less than twice the variance. This filtering step is performed separately for edgeness computed with object edges and motion boundaries.

Experiments

We now present our empirical evaluation on two state-ofthe-art benchmark datasets and compare with several recent methods. The results of all the methods we compare with are directly taken from the respective toolkits. Additional results and videos are provided on the project website [1].

Datasets and Evaluation

Much attention has been given to developing benchmark datasets and measures to evaluate tracking methods in the past couple of years [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF]. For example, Wu et al. [START_REF] Wu | Online object tracking: A benchmark[END_REF] and Song and Xiao [START_REF] Song | Tracking revisited using RGBD camera: Unified benchmark and baselines[END_REF] introduced benchmark datasets and evaluated several state-of-the-art tracking algorithms. Kristan et al. [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF] have organized visual object tracking (VOT) challenges in 2013 and 2014, where several challenging se-quences were used to evaluate methods. We have evaluated our method on the VOT2014 [START_REF] Kristan | A Novel Performance Evaluation Methodology for Single-Target Trackers[END_REF] and the online tracker benchmark (OTB) [START_REF] Wu | Online object tracking: A benchmark[END_REF] datasets, following their original protocols.

VOT2014 dataset. As part of the visual object tracking challenge held at ECCV 2014 [START_REF] Kristan | The visual object tracking VOT2014 challenge results[END_REF], the organizers released a set of 25 challenging video sequences. They were chosen from a candidate set of 394 sequences, composed of examples used in several previous works such as VOT2013 benchmark dataset, ALOV [START_REF] Smeulders | Visual tracking: An experimental survey[END_REF], OTB [START_REF] Wu | Online object tracking: A benchmark[END_REF], as well as a few unpublished ones. This choice was made by: (i) discarding sequences shorter than 200 frames, and (ii) ensuring that the selected sequences contain well-defined targets and represent challenging scenarios, e.g., clutter, object deformation, change in aspect ratio. The frames in all the sequences are manually annotated. In a departure from annotations in other datasets, where the bounding box enclosing the target is axis-aligned, this benchmark uses rotated boxes in order to handle targets that are deforming, rotating or elongated, as shown in Figure 2. This new annotation makes the dataset a more challenging setting to evaluate trackers. In addition to this, all the frames are labelled with visual attributes: occlusion, illumination change, object motion, object size change, camera motion and neutral.

We follow the protocol described in [START_REF] Kristan | A Novel Performance Evaluation Methodology for Single-Target Trackers[END_REF] to evaluate our tracking algorithm, and compare it with several state-of-theart trackers. This evaluation scheme uses accuracy and robustness measures to compare trackers. Accuracy is computed as the mean intersection over union score with the ground truth bounding box over the entire sequence (while discarding a few frames immediately following a tracking failure), and robustness is the number of times the tracker has failed. A tracking failure is signalled in a frame s if the predicted box does not overlap with the ground truth annotation. In this case, the tracker is restarted from scratch with the ground truth annotation in frame s + 5.

The scores are averaged over several runs of the tracker to account for any stochastic behaviour. The overall rank of a tracker is determined by first ranking trackers on accuracy and robustness separately on each attribute set, then averaging the rank over the attributes, and then taking the mean rank over the two performance measures. If a set of trackers show similar performance (which is measured with statistical significance and practical difference tests), their ranks are averaged. This rank correction is performed separately for accuracy and robustness, and the overall average rank is recomputed as mentioned above. We used the toolkit2 provided by the organizers of the challenge to compute the scores and the ranking, allowing us to compare with 38 methods. The interested reader can find more details of the evaluation protocol in [START_REF] Kristan | A Novel Performance Evaluation Methodology for Single-Target Trackers[END_REF].

No. Method Acc. Robust.

Avg. 1 Our-ms-rot We show the ranking on accuracy (Acc.) and robustness (Robust.) measures, as well as the overall rank (Avg.). The top performer in each measure is shown in red, and the second and third best are in blue and green respectively. We show three variants of our method -Our-ms-rot: uses multiscale detector and geometry proposals, Our-ms: uses only multiscale detector proposals, and Our-ss: uses only single-scale detector proposals. The performance of other methods from the VOT2014 challenge is shown on the project website [1].

OTB dataset. The online tracking benchmark dataset [START_REF] Wu | Online object tracking: A benchmark[END_REF] is a collection of 50 of the most commonly used tracking sequences, which are fully annotated. It contains sequences where the object varies in scale, has fast motion, or is occluded. The tracking performance on this benchmark is evaluated with a precision score and area under the curve (AUC) of a success plot, as defined in [START_REF] Wu | Online object tracking: A benchmark[END_REF]. Precision score is measured as the percentage of frames whose predicted object location (center of the predicted box) is within a distance of 20 pixels from the center of the ground truth box. Precision plots are also computed by varying the distance threshold between 0 and 50. Success plots show the percentage of frames whose intersection over union overlap with the ground truth annotation is over a threshold varying between 0 and 1. We used the toolkit 3 provided by Wu et al. [START_REF] Wu | Online object tracking: A benchmark[END_REF] to generate the plots and compute the scores.

Results

VOT. The results in Table 1 correspond to the baseline experiment in the toolkit, where each tracker is executed 3 https://sites.google.com/site/trackerbenchmark/benchmarks/v10 15 times with the same ground truth annotation in the first frame, and the overall rank is computed as described in Section 5.1. Overall, our proposal selection method using detector and geometry proposals ("Our-ms-rot" in the table) performs significantly better than DSST [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF], the winner of the VOT2014 challenge, with an average rank of 7.33 vs 10.39. We also evaluated two variants of our approach. The first one "Our-ms" uses only the multiscale detector proposals and the second variant "Our-ss" is limited to proposals from the detector evaluated only at a single scale. The overall rank of these two variants is lower than our full method: 7.43 and 15.29 respectively. The variant based on multiscale detector proposals performs better on the accuracy measure compared to the full method, but is significantly worse on the robustness measure. In other words, this variant fails on many more frames than the full method, and benefits from the resulting reinitializations. Due to significant changes in scale that occur in several frames in the dataset, the variant based on a single-scale detector performs rather poorly. CMT [START_REF] Nebehay | Consensus-based matching and tracking of keypoints for object tracking[END_REF], the key point based tracker which estimates rotation and scale of the object, has an average rank of 24.43 and is ranked 28th on the list (see [1]).

With the evaluation protocol of reinitializing the tracker when it fails, we found that using edgeness measure did not show a significant difference compared to the detection score. Thus, to keep the comparison with respect to the large number of trackers (38) reasonable, we show a subset of variants of our methods on VOT. On the accuracy measure, our approaches ("Our-ms-rot" and "Our-ms") are ranked first and second. KCF [START_REF] Henriques | Highspeed tracking with kernelized correlation filters[END_REF] is third, with SAMF and DSST [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF] also performing well. The AR ranking plot in Figure 4 shows the similar performance of KCF, SAMF and DSST, where they form a cluster. KCF is a correlation filter based tracker. It is essentially a regression method trained with HOG features computed on several patches densely sampled around the object. This method, however, is significantly inferior on robustness measure (16.71 compared to our result 8.58) as it cannot handle object deformations other than translation. SAMF and DSST are extensions of the KCF approach. SAMF proposes an adaptive scale for the patches and also integrates HOG and colour attribute features. It is more robust than KCF, but still poorer than our result (15.65 vs 8.58). DSST [START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF], the VOT2014 challenge winner, improves the correlation filtering scheme by estimating the scale of the target and combining intensity and HOG features. It trains two separate filters: one for estimating translation and another for scale. While DSST shows better performance than both SAMF and KCF, it also cannot handle cases where the target is rotating. Our method addresses this issues and significantly improves over DSST (8.58 vs 13.99 in robustness rank).

Our tracker is ranked third on the robustness measure. PLT 14 and PLT 13 , which are two variants of Struck [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF], are first and second respectively. PLT 13 , the winner of the VOT2013 challenge, uses object-background colour histograms to weight the features within the bounding box during SVM training. In essence, it attempts to refine the object representation from an entire bounding box to an object segmentation. PLT 14 is the multiscale version of PLT 13 , and it shows better accuracy at the cost of a lower robustness. The segmentation cue used in these methods makes them accurate because it provides a more precise object representation than a bounding box. However, in many situations, e.g., fast motion, lack of strong object-background colour priors, it is likely to fail. This is evident from the significantly lower accuracy of the PLT methods -16.04, 19.74 compared to 6.07 of our approach (see Table 1).

We present a sample qualitative result in Figure 5, see [1] for additional results. The motocross sequence is considered as one of the most challenging sequences in this benchmark, based on the number of trackers that fail on it. Our approach performs significantly better other methods. We compare to the results of DSST and PLT 14 , which performed well on the VOT2014 challenge, and also Struck, the top performer on several datasets.

OTB. The results in Figure 6 correspond to the one-pass evaluation (OPE) of the toolkit [START_REF] Wu | Online object tracking: A benchmark[END_REF]. The trackers are tested on more than 29,000 frames in this evaluation. We show the success and precision plots of our method in Figure 6 and compare it with the top 10 methods. Comparison with all the 28 trackers evaluated is shown in [1]. Our overall method "Our-ms-rot-em" and its four variants outperform all the trackers on both the measures. More precisely, our tracker achieves 0.798 precision score compared to 0.656 of Struck [START_REF] Hare | Struck: Structured output tracking with kernels[END_REF], and 0.580 AUC of success plot compared to 0.499 of SCM [START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF] -the top two performers on this benchmark dataset [START_REF] Wu | Online object tracking: A benchmark[END_REF].

Our single-scale tracker "Our-ss" is inferior to the other four variants: 0.733 precision score and 0.523 AUC of success plot due to significant changes in scale and/or rotation in several sequences. The performance of our multiscale version without geometry proposals "Our-ms", and the multiscale one with geometry proposals "Our-ms-rot" is very similar. This is expected, despite "Our-ms-rot" performing better than "Our-ms" on the VOT dataset, because the ground truth annotations in the OTB dataset are axis-aligned and not rotated boxes, as is the case in VOT. Thus, a rotating object can be enclosed (although imprecisely) by a larger axis-aligned box. This makes "Our-ms" as effective as "Our-ms-rot" following the OTB evaluation protocol. In Figure 6 we also show the influence of scores computed with edges "e" and motion boundaries "m". The precision result using (multiscale) detector confidence alone to select from the candidate set ("Our-ms-rot") is 0.754. Incorporating the measure computed with edges ("Ours-ms-rot-e") improves this by 2.1% to 0.770, and the cue computed with motion boundary ("Our-ms-rot-em") gives a further 3.6% improvement to 0.798. A similar improvement pattern can be seen on the success plot.

A couple of recent papers [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF][START_REF] Supancic | Self-paced learning for long-term tracking[END_REF] also evaluated their trackers on the OTB dataset. However, they are not online trackers, in that they use the information for subsequent frames to infer the object location in the current frame. We, nevertheless, compare to them using mean F 1 score (with 50% overlap threshold), following the protocol in [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF]. Our tracker ("Our-ms-rot-em") performs significantly better with a score of 0.757 compared to 0.657 and 0.661 of [START_REF] Hua | Occlusion and motion reasoning for long-term tracking[END_REF] and [START_REF] Supancic | Self-paced learning for long-term tracking[END_REF] respectively.

In Figure 7 we evaluate the performance of our approach ("Our-ms-rot-em") with respect to the number of candidate proposals on the OTB dataset. Here, we measure the performance as mean overlap between the predicted and the ground truth bounding boxes over the entire sequence. We observe that the mean overlap score increases initially with the number of proposals, but then quickly saturates. In other words, we require a minimum number of proposals (5 each for detection and geometry, which we use in this paper) for tracking an object effectively. Adding further candidate proposals beyond this does not affect the performance, as the new candidates are either very similar to or less accurate than those already in the proposal set.

Computation time. Our Matlab and mex implementation is un-optimized and not real-time. It performs as follows (average fps on VOT+OTB datasets): our-ss: 6.4, our-ms: 4.1, our-ms-rot: 3.1, our-ms-rot-e: 2.1, our-ms-rotem: 1.9 on a cluster node with 20 cores. The last three variants require pre-computed optical flow [START_REF] Brox | Large displacement optical flow: Descriptor matching in variational motion estimation[END_REF], which runs at 0.3 fps on a GPU. Our implementation can certainly be sped up in several ways, e.g., by scaling the images down, speeding up the feature extraction process.

Summary

In this paper, we present a new tracking-by-detection framework for online object tracking. Our approach begins with building a candidate set of object location proposals extracted using a learned detector model. It is then augmented with novel proposals computed by estimating the geometric transformation(s) undergone by the object. We localize the object by selecting the best proposal from this candidate set using multiple cues: detection confidence score, edges and motion boundaries. The performance of our tracker is evaluated extensively on the VOT2014 challenge and the OTB datasets. We show state-of-the-art results on both these benchmarks, significantly improving over the top performers of these two evaluations.

Figure 3 .

 3 Figure 3. Two examples of edge and motion boundary responses. In each row, from left to right, we show the original image (with the object in a green box), edges and motion boundaries. The edges provide a stronger response in the example in the first row while motion boundaries are more effective in the example in the second row.

Figure 4 .

 4 Figure 4. AR ranking plot of all the trackers from the VOT2014 challenge as well as our approaches. Trackers close to the top right corner of the plot are among the top performers. Our multiscale approaches ("Our-ms-rot" and "Our-ms") are closest to the topright corner compared to all the other methods.

Figure 5 .

 5 Figure5. Sample result on the motocross sequence. We compare with several state-of-the-art trackers. Ground truth: green, Our result: yellow, DSST[START_REF] Danelljan | Accurate scale estimation for robust visual tracking[END_REF]: red, PLT14: cyan, Struck[START_REF] Hare | Struck: Structured output tracking with kernels[END_REF]: blue. Best viewed in pdf.

Figure 6 .

 6 Figure 6. Precision (left) and success rate (right) plots on the OTB dataset. For clarity we compare to the top 10 algorithms in each figure. The complete plots are on the project website [1]. The precision plots are summarized with the precision score at 20 pixel error threshold and the success plots with the area under the curve. These values are shown in the legend. Best viewed in pdf.

Figure 7 .

 7 Figure 7. Influence of the number of (detection and geometry) proposals on the tracking performance on the OTB dataset.

  Algorithm 1 : Our approach for online object tracking. Data: Image frames 1 . . . n, Ground truth box 1 in frame 1 Result: Object location box t in frames t = 2 . . . n Learn initial detector model in frame 1 ( §3.1) for t = 2 . . . n do candidate set C t ← Top-k detections in frame t ( §3.1) H t ← Geometry proposals in frame t ( §3.2) C t ← C t ∪ H t box t ← Best proposal in C t ( §3.3) Update detector model with box t ( §3.4) end

Table 1 .

 1 Performance of the top 20 methods on the VOT2014 dataset.

		6.07	8.58	7.33
	2 Our-ms	4.73	10.13	7.43
	3 DSST [12]	6.78	13.99 10.39
	4 SAMF	6.46	15.65 11.06
	5 DGT	12.67	10.13	11.4
	6 KCF [21]	6.16	16.71 11.44
	7 PLT 14	16.04	6.98 11.51
	8 PLT 13	19.74	4.00 11.87
	9 eASMS	15.37	15.1 15.24
	10 Our-ss	16.11	14.47 15.29
	11 ACAT	15.1	16.78 15.94
	12 MatFlow	23.82	9.67 16.74
	13 HMMTxD 11.08	22.51	16.8
	14 MCT	18.47	15.14 16.81
	15 qwsEDFT	19.06	21.15 20.11
	16 ACT	22.68	18.1 20.39
	17 ABS	22.34	20.49 21.42
	18 VTDMG	23.22	19.94 21.58
	19 LGTv1	31.05	12.68 21.87
	20 BDF	24.92	19.39 22.15

Note that this estimation was done only in the first frame or whenever the tracker is restarted after a failure, i.e., when we have access to the ground truth box.

http://www.votchallenge.net/howto/perfeval.html

Acknowledgements. This work was supported in part by the MSR-Inria joint project, Google Faculty Research Award, and the ERC advanced grant ALLEGRO.


Michael Dinitz
email: mdinitz@cs.jhu.edu

Jeremy Fineman
email: jfineman@cs.georgetown.edu

Seth Gilbert
email: seth.gilbert@comp.nus.edu.sg

Calvin Newport
email: cnewport@cs.georgetown.edu

Smoothed Analysis of Dynamic Networks

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Dynamic network models describe networks with topologies that change over time (c.f., [START_REF] Kuhn | Dynamic networks: models and algorithms[END_REF]). They are used to capture the unpredictable link behavior that characterize challenging networking scenarios; e.g., connecting and coordinating moving vehicles, nearby smartphones, or nodes in a widespread and fragile overlay. Because fine-grained descriptions of link behavior in such networks are hard to specify, most analyses of dynamic networks rely instead on a worst-case selection of graph changes. This property is crucial to the usefulness of these analyses, as it helps ensure the results persist in real deployment.

A problem with this worst case perspective is that it often leads to extremely strong lower bounds. These strong results motivate a key question: Is this bound robust in the sense that it captures a fundamental difficulty introduced by dynamism, or is the bound fragile in the sense that the poor performance it describes depends on an exact sequence of adversarial changes? Fragile lower bounds leave open the possibility of algorithms that might still perform well in practice. By separating fragile from robust results, we can expand the algorithmic tools available to those seeking useful guarantees in these challenging environments.

In the study of traditional algorithms, an important technique for explaining why algorithms work well in practice, despite disappointing worst case performance, is smoothed analysis [START_REF] Spielman | Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time[END_REF][START_REF] Spielman | Smoothed analysis: an attempt to explain the behavior of algorithms in practice[END_REF]. This approach studies the expected performance of an algorithm when the inputs are slightly perturbed. If a strong lower bound dissipates after a small amount of smoothing, it is considered fragile-as it depends on a carefully constructed degenerate case. Note that this is different from an "average-case" analysis, which looks at instances drawn from some distribution. In a smoothed analysis, you still begin with an adversarially chosen input, but then slightly perturb this choice. Of course, as the perturbation grows larger, the input converges to something entirely random. (Indeed, in the original smoothed analysis papers [START_REF] Spielman | Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time[END_REF][START_REF] Spielman | Smoothed analysis: an attempt to explain the behavior of algorithms in practice[END_REF], the technique is described as interpolating between worst and average case analysis.)

In this paper, we take the natural step of adapting smoothed analysis to the study of distributed algorithms in dynamic networks. Whereas in the traditional setting smoothing typically perturbs numerical input values, in our setting we define smoothing to perturb the network graph through the random addition and deletion of edges. We claim that a lower bound for a dynamic network model that improves with just a small amount of graph smoothing of this type is fragile, as it depends on the topology evolving in an exact manner. On the other hand, a lower bound that persists even after substantial smoothing is robust, as this reveals a large number of similar graphs for which the bound holds.

Results. We begin by providing a general definition of a dynamic network model that captures many of the existing models already studied in the distributed algorithms literature. At the core of a dynamic network model is a dynamic graph that describes the evolving network topology. We provide a natural definition of smoothing for a dynamic graph that is parameterized with a smoothing factor k ∈ {0, 1, ..., n 2 }. In more detail, to k-smooth a dynamic graph H is to replace each static graph G in H with a smoothed graph G sampled uniformly from the space of graphs that are: (1) within edit distance5 k of G, and (2) are allowed by the relevant dynamic network model. (E.g., if the model requires the graph to be connected in every round, smoothing cannot generate a disconnected graph.)

We next argue that these definitions allow for useful discernment between different dynamic network lower bounds. To this end, we use as case studies three well known problems with strong lower bounds in dynamic network models: flooding, random walks, and aggregation. For each problem, we explore the robustness/fragility of the existing bound by studying how it improves under increasing amounts of smoothing. Our results are summarized in Table 1. We emphasize the surprising variety in outcomes: these results capture a wide spectrum of possible responses to smoothing, from quite fragile to quite robust.

Graph k-Smoothed Algorithm k-Smoothed Lower Bound 0-Smoothed Lower Bound Flooding Connected O(n 2/3 log n/k 1/3 ) Ω(n 2/3 /k 1/3 ) Ω(n) Hitting Time Connected O(n 3 /k) Ω(n 5/2 /( √ k log n) Ω(2 n ) Aggregation Paired O(n)-competitive Ω(n)-competitive Ω(n)-competitive
For the minimal amount of smoothing (k = 1), for example, the Ω(2 n ) lower bound for the hitting time of a random walk in connected dynamic networks (established in [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF]) decreases by an exponential factor to O(n 3 ); the Ω(n) lower bound for flooding time in these same networks (well-known in folklore) decreases by a polynomial factor to O(n 2/3 log n); and the Ω(n) lower bound on the achievable competitive ratio for token aggregation in pairing dynamic graphs (established in [START_REF] Cornejo | Aggregation in dynamic networks[END_REF]) decreases by only a constant factor.

As we increase the smoothing factor k, our upper bound on random walk hitting time decreases as O(n 3 /k), while our flooding upper bound reduces more slowly as O(n 2/3 log n/k 1/3 ), and our aggregation bound remains in Ω(n) for k values as large as Θ(n/ log 2 n). In all three cases we also prove tight or near tight lower bounds for all studied values of k.

Among other insights, these results indicate that the exponential hitting time lower bound for dynamic walks is extremely fragile, while the impossibility of obtaining a good competitive ratio for dynamic aggregation is quite robust. Flooding provides an interesting intermediate case. While it is clear that an Ω(n) bound is fragile, the claim that flooding can take a polynomial amount of time (say, in the range n 1/3 to n 2/3 ) seems well-supported.

Full Version. Due to space constraints, we omit proofs from this extended abstract. Full details for our results can be found in the full version [START_REF] Dinitz | Smoothed analysis of dynamic networks[END_REF].

Next Steps. The definitions and results that follow represent a first (but far from final) step toward the goal of adapting smoothed analysis to dynamic networks. There are many additional interesting dynamic network bounds that could be subjected to a smoothed analysis. Moreover, there are many other reasonable definitions of smoothing beyond the ones herein. While our definition is natural and our results suggestive, for other problems or models other definitions might be more appropriate. Rather than claiming that our approach here is the "right" way to study the fragility of dynamic network lower bounds, we instead claim that smoothed analysis generally speaking (in all its various possible formulations) is an important and promising tool when trying to understand the fundamental limits of distributed behavior in dynamic network settings. Related Work. Smoothed analysis was introduced by Spielman and Teng [START_REF] Spielman | Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time[END_REF][START_REF] Spielman | Smoothed analysis: an attempt to explain the behavior of algorithms in practice[END_REF], who used the technique to explain why the simplex algorithm works well in practice despite strong worst-case lower bounds. It has been widely applied to traditional algorithm problems (see [START_REF] Spielman | Smoothed analysis: an attempt to explain the behavior of algorithms in practice[END_REF] for a good introduction and survey). Recent interest in studying distributed algorithms in dynamic networks was sparked by Kuhn et al. [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF]. Many different problems and dynamic network models have since been proposed; e.g., [START_REF] Kuhn | Coordinated consensus in dynamic networks[END_REF][START_REF] Haeupler | Faster information dissemination in dynamic networks via network coding[END_REF][START_REF] Dutta | On the complexity of information spreading in dynamic networks[END_REF][START_REF] Clementi | Information spreading in dynamic graphs[END_REF][START_REF] Augustine | Towards robust and efficient computation in dynamic peer-to-peer networks[END_REF][START_REF] Denysyuk | Random walks on evolving graphs with recurring topologies[END_REF][START_REF] Newport | Lower bounds for structuring unreliable radio networks[END_REF][START_REF] Ghaffari | The cost of radio network broadcast for different models of unreliable links[END_REF] (see [START_REF] Kuhn | Dynamic networks: models and algorithms[END_REF] for a survey). The dynamic random walk lower bound we study was first proposed by Avin et al. [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF], while the dynamic aggregation lower bound we study was first proposed by Cornejo et al. [START_REF] Cornejo | Aggregation in dynamic networks[END_REF]. We note other techniques have been proposed for exploring the fragility of dynamic network lower bounds. In recent work, for example, Denysyuk et al. [START_REF] Denysyuk | Random walks on evolving graphs with recurring topologies[END_REF] thwart the exponential random walk lower bound due to [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF] by requiring the dynamic graph to include a certain number of static graphs from a well-defined set, while work by Ghaffari et al. [START_REF] Ghaffari | The cost of radio network broadcast for different models of unreliable links[END_REF] studies the impact of adversary strength, and Newport [START_REF] Newport | Lower bounds for structuring unreliable radio networks[END_REF] studies the impact of graph properties, on lower bounds in the dynamic radio network model.

Dynamic Graphs, Networks, and Types

There is no single dynamic network model. There are, instead, many different models that share the same basic behavior: nodes executing synchronous algorithms are connected by a network graph that can change from round to round. Details on how the graphs can change and how communication behaves given a graph differ between model types.

In this section we provide a general definition for a dynamic network models that captures many existing models in the relevant literature. This approach allows us in the next section to define smoothing with sufficient generality that it can apply to these existing models. We note that in this paper we constrain our attention to oblivious graph behavior (i.e., the changing graph is fixed at the beginning of the execution), but that the definitions that follow generalize in a straightforward manner to capture adaptive models (i.e., the changing graph can adapt to behavior of the algorithm).

Dynamic Graphs and Networks. Fix some node set V , where n = |V |. A dynamic graph H, defined with respect to V , is a sequence G 1 , G 2 , ..., where each G i = (V, E i ) is a graph defined over nodes V . If this is not an infinite sequence, then the length of H is |H|, the number of graphs in the sequence. A dynamic network, defined with respect to V , is a pair, (H, C), where H is a dynamic graph, and C is a communication rules function that maps transmission patterns to receive patterns. That is, the function takes as input a static graph and an assignment of messages to nodes, and returns an assignment of received messages to nodes. For example, in the classical radio network model C would specify that nodes receive a message only if exactly one of their neighbors transmits, while in the LOCAL model C would specify that all nodes receive all messages sent by their neighbors. Finally, an algorithm maps process definitions to nodes in V .

Given a dynamic network (H, C) and an algorithm A, an execution of A in (H, C) proceeds as follows: for each round r, nodes use their process definition according to A to determine their transmission behavior, and the resulting receive behavior is determined by applying C to H[r] and this transmission pattern.

Dynamic Network Types. When we think of a dynamic network model suitable for running executions of distributed algorithms, what we really mean is a combination of a description of how communication works, and a set of the different dynamic graphs we might encounter. We formalize this notion with the concept of the dynamic network type, which we define as a pair (G, C), where G is a set of dynamic graphs and C is a communication rules function. For each H ∈ G, we say dynamic network type (G, C) contains the dynamic network (H, C).

When proving an upper bound result, we will typically show that the result holds when our algorithm is executed in any dynamic network contained within a given type. When proving a lower bound result, we will typically show that there exists a dynamic network contained within the relevant type for which the result holds. In this paper, we will define and analyze two existing dynamic network types: (1-interval) connected networks [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] Kuhn | Coordinated consensus in dynamic networks[END_REF][START_REF] Haeupler | Faster information dissemination in dynamic networks via network coding[END_REF][START_REF] Dutta | On the complexity of information spreading in dynamic networks[END_REF], in which the graph in each round is connected and C describes reliable broadcast to neighbors in the graph, and pairing networks [START_REF] Cornejo | Aggregation in dynamic networks[END_REF], in which the graph in each round is a matching and C describes reliable message passing with each node's neighbor (if any).

Smoothing Dynamic Graphs

We now define a version of smoothed analysis that is relevant to dynamic graphs. To begin, we define the edit distance between two static graphs G = (V, E) and G = (V, E ) to be the minimum number of edge additions and removals needed to transform G to G . With this in mind, for a given G and k ∈ {0, 1, ..., n 2 }, we define the set:

editdist(G, k) = {G | the edit distance between G and G is no more than k}.
Finally, for a given set of dynamic graphs G, we define the set:

allowed(G) = {G | ∃H ∈ G such that G ∈ H}.
In other words, allowed describes all graphs that show up in the dynamic graphs contained in the set G. Our notion of smoothing is always defined with respect to a dynamic graph set G. Formally: Definition 1. Fix a set of dynamic graphs G, a dynamic graph H ∈ G, and smoothing factor k ∈ {0, 1, ..., n 2 }. To k-smooth a static graph G ∈ H (with respect to G) is to replace G with a graph G sampled uniformly from the set editdist(G, k) ∩ allowed(G). To k-smooth the entire dynamic graph H (with respect to G), is to replace H with the dynamic graph H that results when we k-smooth each of its static graphs.

We will also sometimes say that G (resp. H ) is a k-smoothed version of G (resp. H), or simply a k-smoothed G (resp. H). We often omit the dynamic graph set G when it is clear in context. (Typically, G will be the set contained in a dynamic network type under consideration.) Discussion. Our notion of k-smoothing transforms a graph by randomly adding or deleting k edges. A key piece of our definition is that smoothing a graph with respect to a dynamic graph set cannot produce a graph not found in any members of that set. This restriction is particularly important for proving lower bounds on smoothed graphs, as we want to make sure that the lower bound results does not rely on a dynamic graph that could not otherwise appear. For example, if studying a process in a dynamic graph that is always connected, we do not want smoothing to disconnect the graph-an event that might trivialize some bounds.

Connected and Pairing Dynamic Network Types

We now define two dynamic network types: the connected network type [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] Kuhn | Coordinated consensus in dynamic networks[END_REF][START_REF] Haeupler | Faster information dissemination in dynamic networks via network coding[END_REF][START_REF] Dutta | On the complexity of information spreading in dynamic networks[END_REF], and the pairing network type [START_REF] Cornejo | Aggregation in dynamic networks[END_REF]. We study random walks (Section 6) and flooding (Section 5) in the context of the connected network type, whereas we study token aggregation (Section 7) in the context of the pairing type.

Connected Network

The connected network type [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF][START_REF] Kuhn | Coordinated consensus in dynamic networks[END_REF][START_REF] Haeupler | Faster information dissemination in dynamic networks via network coding[END_REF][START_REF] Dutta | On the complexity of information spreading in dynamic networks[END_REF] is defined as (G conn , C conn ), where G conn contains every dynamic graph (defined with respect to our fixed node set V ) in which every individual graph is connected, and where C conn describes reliable broadcast (i.e., a message sent by u in rounds r in an execution in graph H is received by every neighbor of u in H[r]).

Properties of Smoothed Connected Networks. For our upper bounds, we show that if certain edges are added to the graph through smoothing, then the algorithm makes enough progress on the smoothed graph. For our lower bounds, we show that if certain edges are not added to the graph, then the algorithm does not make much progress. The following lemmas bound the probabilities that these edges are added. The proofs roughly amount to showing that sampling uniformly from editdist(G, k) ∩ allowed(G conn ) is similar to sampling from editdist(G, k).

The first two lemmas are applicable when upper-bounding the performance of an algorithm on a smoothed dynamic graph. The first lemma states that the ksmoothed version of graph G is fairly likely to include at least one edge from the set S of helpful edges. The second lemma, conversely, says that certain critical edges that already exist in G are very unlikely to be removed in the smoothed version.

Lemma 2. There exists constant c 1 > 0 such that the following holds. Consider any graph G ∈ allowed(G conn ). Consider also any nonempty set S of potential edges and smoothing value k ≤ n/16 with k |S| ≤ n 2 /2. Then with probability at least c 1 k |S| /n 2 , the k-smoothed graph G of G contains at least one edge from S. Lemma 3. There exists constant c 2 > 0 such that the following holds. Consider any graph G = (V, E) ∈ allowed(G conn ). Consider also any nonempty set S ⊆ E of edges in the graph and smoothing value k ≤ n/16. Then with probability at most c 2 k |S| /n 2 , the k-smoothed graph G removes an edge from S.

Our next lemma is applicable when lower-bounding an algorithm's performance on a dynamic graph. It says essentially that Lemma 2 is tight-it is not too likely to add any of the helpful edges from Lemma 4. There exists constant c 3 > 0 such that the following holds. Consider any graph G = (V, E) ∈ allowed(G conn ). Consider also any set S of edges and smoothing value k ≤ n/16 such that S ∩ E = ∅. Then with probability at most c 3 k |S| /n 2 , the k-smoothed graph G of G contains an edge from S.

Pairing Network

The second type we study is the pairing network type [START_REF] Cornejo | Aggregation in dynamic networks[END_REF]. This type is defined as (G pair , C pair ), where G pair contains every dynamic graph (defined with respect to our fixed node set V ) in which every individual graph is a (not necessarily complete) matching, and C pair reliable communicates messages between pairs of nodes connected in the given round. This network type is motivated by the current peer-to-peer network technologies implemented in smart devices. These low-level protocols usually depend on discovering nearby nodes and initiating one-on-one local interaction.

Properties of Smoothed Pairing Networks. In the following, when discussing a matching G, we partition nodes into one of two types: a node is matched if it is connected to another node by an edge in G, and it is otherwise unmatched. The following property concerns the probability that smoothing affects (i.e., adds or deletes at least one adjacent edge) a given node u from a set S of nodes of the same type. It notes that as the set S containing u grows, the upper bound on the probability that u is affected decreases. The key insight behind this not necessarily intuitive statement is that this probability must be the same for all nodes in S (due to their symmetry in the graph). Therefore, a given probability will generate more expected changes as S grows, and therefore, to keep the expected changes below the k threshold, this bound on this probability must decrease as S grows.

Flooding

Here we consider the performance of a basic flooding process in a connected dynamic network. In more detail, we assume a single source node starts with a message. In every round, every node that knows the message broadcasts the message to its neighbors. (Flooding can be trivially implemented in a connected network type due to reliable communication.) We consider the flooding process complete in the first round that every node has the message. Without smoothing, this problem clearly takes Ω(n) rounds in large diameter static graphs, so a natural alternative is to state bounds in terms of diameter. Unfortunately, there exist dynamic graphs (e.g., the spooling graph defined below) where the graph in each round is constant diameter, but flooding still requires Ω(n) rounds.

We show that this lower bound is somewhat fragile by proving a polynomial improvement with any smoothing. Specifically, we show an upper bound of O(n 2/3 log(n)/k 1/3 ) rounds, with high probability, with k-smoothing. We also exhibit a nearly matching lower bound by showing that the dynamic spooling graph requires Ω(n 2/3 /k 1/3 ) rounds with constant probability.

Lower Bound

We build our lower bound around the dynamic spooling graph, defined as follows. Label the nodes from 1 to n, where node 1 is the source. The spooling graph is a dynamic graph where in each round r, the network is the min {r, n -1}-spool graph. We define the i-spool graph, for i ∈ [n -1] to be the graph consisting of: a star on nodes {1, . . . , i} centered at i called the left spool, a star on nodes {i + 1, . . . , n} centered on i + 1 called the right spool, and an edge between the two centers i and i + 1. We call i + 1 the head node.

With node 1 as the source node, it is straightforward to see that, in the absence of smoothing, flooding requires n-1 rounds to complete on the spooling network. (Every node in the left spool has the message but every node in the right spool does not. In each round, the head node receives the message then moves to the left spool.) We generalize this lower bound to smoothing. The main idea is that in order for every node to receive the message early, one of the early heads must be adjacent to a smoothed edge. Theorem 6. Consider the flooding process on a k-smoothed n-vertex spooling graph, with k ≤ √ n and sufficiently large n. With probability at least 1/2, the flooding process does not complete before the Ω(n 2/3 /k 1/3 )-th round.

5.2 An O(n 2/3 log n/k 1/3 ) Upper Bound for General Networks Next, we show that flooding in every k-smoothed network will complete in O(n 2/3 log n/k 1/3 ) time, with high probability. When this result is combined with the Ω(n 2/3 /k 1/3 ) lower bound from above, this shows this analysis to be essentially tight for this problem under smoothing. Support Sequences. The core idea is to show that every node in every network is supported by a structure in the dynamic graph such that if the message can be delivered to anywhere in this structure in time, it will subsequently propagate to the target. In the spooling network, this structure for a given target node u consists simply of the nodes that will become the head in the rounds leading up to the relevant complexity deadline. The support sequence object defined below generalizes a similar notion to all graphs. It provides, in some sense, a fat target for the smoothed edges to hit in their quest to accelerate flooding. Definition 7. Fix two integers t and , 1 ≤ < t, a dynamic graph H = G 1 , . . . , G t with G i = (V, E i ) for all i, and a node u ∈ V . A (t, )-support sequence for u in G is a sequence S 0 , S 1 , S 2 , ..., S , such that the following properties hold: (1) For every i ∈ [0, ]:

S i ⊆ V . (2) S 0 = {u}. (3) For every i ∈ [1, ]: S i-1 ⊂ S i and S i \ S i-1 = {v}, for some v ∈ V such that v is adjacent to at least one node of S i-1 in G t-i .
Notice that the support structure is defined "backwards" with S 0 containing the target node u, and each subsequent step going one round back in time. We prove that every connected dynamic graph has such a support structure, because the graph is connected in every round. Lemma 8. Fix some dynamic graph H ∈ G conn on vertex set V , some node u ∈ V , and some rounds t and , where 1 ≤ < t. There exists a (t, )-support sequence for u in H.

The following key lemma shows that over every period of Θ(n 2/3 /k 1/3 ) rounds of k-smoothed flooding, every node has a constant probability of receiving the message. Applying this lemma over Θ(log n) consecutive time intervals with a Chernoff bound, we get our main theorem. Lemma 9. There exists constant α ≥ 3 such that the following holds. Fix a dynamic graph H ∈ G conn on vertex set V , any node u ∈ V , and a consecutive interval of αn 2/3 /k 1/3 rounds. For smoothing value k ≤ n/16, node u receives the flooded message in the k-smoothed version of H with probability at least 1/2. Theorem 10. For any dynamic graph H ∈ G conn and smoothing value k ≤ n/16, flooding completes in O(n 2/3 log n/k 1/3 ) rounds on the k-smoothed version of H with high probability.

Random Walks

As discussed in Section 1, random walks in dynamic graphs exhibit fundamentally different behavior from random walks in static graphs. Most notably, in dynamic graphs there can be pairs of nodes whose hitting time is exponential [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF], even though in static (connected) graphs it is well-known that the maximum hitting time is at most O(n 3 ) [START_REF] Lovász | Random walks on graphs: A survey[END_REF]. This is true even under obvious technical restrictions necessary to prevent infinite hitting times, such as requiring the graph to be connected at all times and to have self-loops at all nodes.

We show that this lower bound is extremely fragile. A straightforward argument shows that a small perturbation (1-smoothing) is enough to guarantee that in any dynamic graph, all hitting times are at most O(n 3 ). Larger perturbations (k-smoothing) lead to O(n 3 /k) hitting times. We also prove a lower bound of Ω(n 5/2 / √ k), using an example which is in fact a static graph (made dynamic by simply repeating it). In some sense, it is not surprising that the lower bound on random walks is fragile, as there exist algorithms for accomplishing the same goals (e.g., identifying a random sample) in dynamic graphs in polynomial time [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF][START_REF] Sarma | Fast distributed computation in dynamic networks via random walks[END_REF].

Preliminaries

We begin with some technical preliminaries. In a static graph, a random walk starting at u ∈ V is a walk on G where the next node is chosen uniformly at random from the set of neighbors on the current node (possibly including the current node itself if there is a self-loop). The hitting time H(u, v) for u, v ∈ V is the expected number of steps taken by a random walk starting at u until it hits v for the first time. Random walks are defined similarly in a dynamic graph H = G 1 , G 2 , . . . : at first the random walk starts at u, and if at the beginning of time step t it is at a node v t then in step t it moves to a neighbor of v t in G t chosen uniformly at random. Hitting times are defined in the same way as in the static case.

The definition of the hitting time in a smoothed dynamic graph is intuitive but slightly subtle. Given a dynamic graph H and vertices u, v, the hitting time from u to v under k-smoothing, denoted by H k (u, v), is the expected number of steps taken by a random walk starting at u until first reaching v in the (random) k-smoothed version H of H (either with respect to G conn or with respect to the set G all of all dynamic graphs). Note that this expectation is now taken over two independent sources of randomness: the randomness of the random walk, and also the randomness of the smoothing (as defined in Section 3).

Upper Bounds

We first prove that even a tiny amount amount of smoothing is sufficient to guarantee polynomial hitting times even though without smoothing there is an exponential lower bound. Intuitively, this is because if we add a random edge at every time point, there is always some inverse polynomial probability of directly jumping to the target node. We also show that more smoothing decreases this bound linearly.

Theorem 11. In any dynamic graph H, for all vertices u, v and value k ≤ n/16, the hitting time H k (u, v) under k-smoothing (with respect to G all ) is at most O(n 3 /k). This is also true for smoothing with respect to G conn if H ∈ G conn .

A particularly interesting example is the dynamic star, which was used by Avin et al. [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF] to prove an exponential lower bound. The dynamic star consists of n vertices {0, 1, . . . , n-1}, where the center of the start at time t is t mod (n-1) (note that node n -1 is never the center). Every node also has a self loop. Avin et al. [START_REF] Avin | How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)[END_REF] proved that the hitting time from node n -2 to node n -1 is at least 2 n-2 . It turns out that this lower bound is particularly fragile -not only does Theorem 11 imply that the hitting time is polynomial, it is actually a factor of n better than the global upper bound due to the small degrees at the leaves.

Theorem 12. H k (u, v) is at most O(n 2 /k) in the dynamic star for all k ≤ n/16
and for all vertices u, v (where smoothing is with respect to G conn ).

Lower Bounds

Since the dynamic star was the worst example for random walks in dynamic graphs without smoothing, Theorem 12 naturally leads to the question of whether the bound of O(n 2 /k) holds for all dynamic graphs in G conn , or whether the weaker bound of O(n 3 /k) from Theorem 11 is tight. We show that under smoothing, the dynamic star is in fact not the worst case: a lower bound of Ω(n 5/2 / √ k) holds for the lollipop graph. The lollipop is a famous example of graph in which the hitting time is large: there are nodes u and v such that H(u, v) = Θ(n 3 ) (see, e.g., [START_REF] Lovász | Random walks on graphs: A survey[END_REF]). Here we will use it to prove a lower bound on the hitting time of dynamic graphs under smoothing: Theorem 13. There is a dynamic graph H ∈ G conn and nodes u, v such that

H k (u, v) ≥ Ω(n 5/2 /( √ k ln n)) for all k ≤ n/16
(where smoothing is with respect to G conn ).

In the lollipop graph L n = (V, E) the vertex set is partitioned into two pieces

V 1 and V 2 with |V 1 | = |V 2 | = n/2.
The nodes in V 1 form a clique (i.e. there is an edge between every two nodes in V 1 ), while the nodes in V 2 form a path (i.e., there is a bijection π : [n/2] → V 2 such that there is an edge between π(i) and π(i + 1) for all i ∈ [(n/2) -1]). There is also a single special node v * ∈ V 1 which has an edge to the beginning of the V 2 path, i.e., there is also an edge {v * , π(1)}. The dynamic graph H in Theorem 13 is the dynamic lollipop: G i = L n for all i ≥ 1. The starting point of the random walk u is an arbitrary node in V 1 , and the target node v = π(n/2) is the last node on the path.

The intuition for the 1-smoothing case is relatively straightforward: if the random walk is on the path then every Θ(n) rounds it will follow one of the randomly added smoothed edges, which will (with probability 1/2) lead it back to the clique. So in order to hit v, it has to spend less than n time in the path. A standard analysis of the one-dimensional random walk then implies that it will only move O( √ n) positions from where it started, so it needs to start in the final O( √ n) nodes of the path. In each round, it will only see an edge from its current location to this final set of nodes with probability O(1/n 3/2 ), and will follow it with probability only O(1/n) (since it will likely be in the clique). Hence the total hitting time is Ω(n 5/2 ). This idea can be formalized and extended to k-smoothing.

If we do not insist on the dynamic graph being connected at all times, then in fact Theorem 11 is tight via a very simple example: a clique with a single disconnected node. Theorem 14. There is a dynamic graph H and vertices u, v such that H k (u, v) ≥ Ω(n 3 /k) for all k ≤ n where smoothing is with respect to G all .

Aggregation

Here we consider the aggregation problem in the pairing dynamic network type. Notice, in our study of flooding and random walks we were analyzing the behavior of a specific, well-known distributed process. In this section, by contrast, we consider the behavior of arbitrary algorithms. In particular, we will show the pessimistic lower bound for the aggregation problem for 0-smoothed pairing graphs from [START_REF] Cornejo | Aggregation in dynamic networks[END_REF], holds (within constant factors), even for relatively large amounts of smoothing. This problem, therefore, provides an example of where smoothing does not help much.

The Aggregation Problem. The aggregation problem, first defined in [START_REF] Cornejo | Aggregation in dynamic networks[END_REF], assumes each node u ∈ V begins with a unique token σ[u]. The execution proceeds for a fixed length determined by the length of the dynamic graph. At the end of the execution, each node u uploads a set (potentially empty) γ[u] containing tokens. An aggregation algorithm must avoid both losses and duplications (as would be required if these tokens were actually aggregated in an accurate manner). Formally: Definition 15. An algorithm A is an aggregation algorithm if and only if at the end of every execution of A the following two properties hold: [START_REF] Augustine | Towards robust and efficient computation in dynamic peer-to-peer networks[END_REF] No Loss:

u∈V γ[u] = u∈V {σ[u]}. (2) No Duplication: ∀u, v ∈ V, u = v : γ[u] ∩ γ[v] = ∅.
To evaluate the performance of an aggregation algorithm we introduce the notion of aggregation factor. At at the end of an execution, the aggregation factor of an algorithm is the number of nodes that upload at least one token (i.e., |{u ∈ V : γ[u] = ∅}|). Because some networks (e.g., a static cliques) are more suitable for small aggregation factors than others (e.g., no edges in any round) we evaluate the competitive ratio of an algorithm's aggregation factor as compared to the offline optimal performance for the given network.

The worst possible performance, therefore, is n, which implies that the algorithm uploaded from n times as many nodes as the offline optimal (note that n is the maximum possible value for an aggregation factor). This is only possible when the algorithm achieves no aggregation and yet an offline algorithm could have aggregated all tokens to a single node. The best possible performance is a competitive ratio of 1, which occurs when the algorithm matches the offline optimal performance. Results Summary. In [START_REF] Cornejo | Aggregation in dynamic networks[END_REF], the authors prove that no aggregation algorithm can guarantee better than a Ω(n) competitive ratio with a constant probability or better. In more detail: Theorem 16 (Adapted from [START_REF] Cornejo | Aggregation in dynamic networks[END_REF]). For every aggregation algorithm A, there exists a pairing graph H such that with probability at least 1/2: A's aggregation factor is Ω(n) times worse than the offline optimal aggregation factor in H.

Our goal in the remainder of this section is to prove that this strong lower bound persists even after a significant amount of smoothing (i.e., k = O(n/ log 2 n)). We formalize this result below (note that the cited probability is with respect to the random bits of both the algorithm and the smoothing process):

Theorem 17. For every aggregation algorithm A and smoothing factor k ≤ n/(32 • log 2 n), there exists a pairing graph H such that with probability at least 1/2: A's aggregation factor is Ω(n) times worse than the offline optimal aggregation factor in a k-smoothed version of H (with respect to G pair ).

Lower Bound

Here we prove that for any smoothing factor k ≤ (cn)/ log 2 n (for some positive constant fraction c we fix in the analysis), k-smoothing does not help aggregation by more than a constant factor as compared to 0-smoothing. To do so, we begin by describing a probabilistic process for generating a hard pairing graph. We will later show that the graph produced by this process is likely to be hard for a given randomized algorithm. To prove our main theorem, we will conclude by applying the probabilistic method to show this result implies the existence of a hard graph for each algorithm.

The α-Stable Pairing Graph Process. We define a specific process for generating a pairing graph (i.e., a graph in allowed(G pair )). The process is parameterized by some constant integer α ≥ 1. In the following, assume the network size n = 2 for some integer ≥ 1 that is also a power of 2. 6 For the purposes of this construction, we label the 2 nodes in the network as a 1 , b 1 , a 2 , b 2 , ..., a , b . For the first α rounds, our process generates graphs with the edge set: {(a i , b i ) : 1 ≤ i ≤ }. After these rounds, the process generates bits, q 1 , q 2 , ..., q , with uniform randomness. It then defines a set S of selected nodes by adding to S the node a i for every i such that q i = 0, and adding b i for every i such that q i = 1. That is, for each of our (a i , b i ) pairs, the process randomly flips a coin to select a single element from the pair to add to S.

For all graphs that follow, the nodes not in S will be isolated in the graph (i.e., not be matched). We turn our attention to how the process adds edges between the nodes that are in S. To do so, it divides the graphs that follow into phases, each consisting of α consecutive rounds of the same graph. In the first phase, this graph is the one that results when the process pairs up the nodes in S by adding an edge between each such pair (these are the only edges). In the second phase, the process defines a set S 2 that contains exactly one node from each of the pairs from the first phase. It then pairs up the nodes in S 2 with edges as before. It also pairs up all nodes in S \ S 2 arbitrarily. Every graph in the second phase includes only these edges. In the third phase, the process defines a set S 3 containing exactly one node from each of the S 2 pairs from the previous pairs. It then once again pairs up the remaining nodes in S arbitrarily. The process repeats this procedure until phase t = log 2 |S| at which point only a single node is in S t , and we are done.

The total length of this dynamic graph is α(log 2 (|S|) + 1). It is easy to verify that it satisfies the definition of the pairing dynamic network type.

Performance of the Offline Optimal Aggregation Algorithm. We now show that the even with lots of smoothing, a graph generated by the stable pairing graph process, parameterized with a sufficiently large α, yields a good optimal solution (i.e., an aggregation factor of 1). Lemma 18. For any k ≤ n/32, and any pairing graph H that might be generated by the (log n)-stable pairing graph process, with high probability in n: the offline optimal aggregation algorithm achieves an aggregation factor of 1 in a k-smoothed version of H.

Performance of an Arbitrary Distributed Aggregation Algorithm. We now fix an arbitrary distributed aggregation algorithm and demonstrate that it cannot guarantee (with good probability) to achieve a non-trivial competitive ratio in all pairing graphs. In particular, we will show it has a constant probability of performing poorly in a graph generated by our above process.

Lemma 19. Fix an online aggregation algorithm A and smoothing factor k ≤ n/(32 • log 2 n). Consider a k-smoothed version of a graph H generated by the (log n)-stable pairing graph process. With probability greater than 1/2 (over the smoothing, adversary, and algorithm's independent random choices): A has an aggregation factor in Ω(n) when executed in this graph.

A final union bound combines the results from Lemmas 18 and 19 to get our final corollary. Applying the probabilistic method to the corollary yields the main theorem-Theorem 17.

Corollary 20. Fix an aggregation algorithm A and smoothing factor k ≤ n/(32• log 2 n). There is a method for probabilistically constructing a pairing graph H, such that with probability greater than 1/2 (over the smoothing, adversary, and algorithm's independent random choices): A's aggregation factor in a k-smoothed version of H is Ω(n) times larger than the offline optimal factor for this graph.

Lemma 5 .

 5 Consider any graph G = (V, E) ∈ allowed(G pair ) and constant δ > 1. Let S ⊆ V be a set of nodes in G such that: (1) all nodes in S are of the same type (matched or unmatched), and (2) |S| ≥ n/δ. Consider any node u ∈ S and smoothing factor k < n/(2 • δ). Let G be the result of k-smoothing G. The probability that u's adjacency list is different in G as compared to G is no more than (2 • δ • k)/n.

Table 1 .

 1 A summary of our main results. The columns labelled "k-smoothed" assume k > 0. Different results assume different upper bounds on k.

Edit distance, in this paper, is the number of edge additions/deletions needed to transform one graph to another, assuming they share the same node set.

We can deal with odd n and/or not a power of 2 by suffering only a constant factor cost to our final performance. For simplicity of presentation, we maintain these assumptions for now.

Supported in part by NSF grant #1464239. Supported in part by NSF grants CCF-1218188 and CCF-1314633. Supported in part by Singapore MOE Tier 2 ARC project 2014-T2-1-157. † Supported in part by NSF grant CCF 1320279.