This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/\epsilon^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $\epsilon$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrt{\alpha})$ such linear systems, where $\alpha$ is the damping factor. When $1/\epsilon^2\ll m$, this implies the existence of an algorithm that computes an $\epsilon$-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}(R^2 / (\sqrt{\alpha}\epsilon^2))$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.

Efficient computation of graph diffusion equations (GDEs), such as Personalized PageRank, Katz centrality, and the Heat kernel, is crucial for clustering, training neural networks, and many other graph-related problems. Standard iterative methods require accessing the whole graph per iteration, making them time-consuming for large-scale graphs. While existing local solvers approximate diffusion vectors through heuristic local updates, they often operate sequentially and are typically designed for specific diffusion types, limiting their applicability. Given that diffusion vectors are highly localizable, as measured by the participation ratio, this paper introduces a novel framework for approximately solving GDEs using a local diffusion process. This framework reveals the suboptimality of existing local solvers. Furthermore, our approach effectively localizes standard iterative solvers by designing simple and provably sublinear time algorithms. These new local solvers are highly parallelizable, making them well-suited for implementation on GPUs. We demonstrate the effectiveness of our framework in quickly obtaining approximate diffusion vectors, achieving up to a hundred-fold speed improvement, and its applicability to large-scale dynamic graphs. Our framework could also facilitate more efficient local message-passing mechanisms for GNNs.

Given the damping factor $\alpha$ and precision tolerance $\epsilon$, \citet{andersen2006local} introduced Approximate Personalized PageRank (APPR), the \textit{de facto local method} for approximating the PPR vector, with runtime bounded by $\Theta(1/(\alpha\epsilon))$ independent of the graph size. Recently, Fountoulakis \& Yang asked whether faster local algorithms could be developed using $\tilde{\mathcal{O}}(1/(\sqrt{\alpha}\epsilon))$ operations. By noticing that APPR is a local variant of Gauss-Seidel, this paper explores the question of *whether standard iterative solvers can be effectively localized*. We propose to use the *locally evolving set process*, a novel framework to characterize the algorithm locality, and demonstrate that many standard solvers can be effectively localized. Let $\overline{\operatorname{vol}}{ (\mathcal S_t)}$ and $\overline{\gamma_t}$ be the running average of volume and the residual ratio of active nodes $\textstyle \mathcal{S_t}$ during the process. We show $\overline{\operatorname{vol}}{ (\mathcal S_t)}/\overline{\gamma_t} \leq 1/\epsilon$ and prove APPR admits a new runtime bound $\tilde{\mathcal{O}}(\overline{\operatorname{vol}}(\mathcal S_t)/(\alpha\overline{\gamma_t}))$ mirroring the actual performance. Furthermore, when the geometric mean of residual reduction is $\Theta(\sqrt{\alpha})$, then there exists $c \in (0,2)$ such that the local Chebyshev method has runtime $\tilde{\mathcal{O}}(\overline{\operatorname{vol}}(\mathcal{S_t})/(\sqrt{\alpha}(2-c)))$ without the monotonicity assumption. Numerical results confirm the efficiency of this novel framework and show up to a hundredfold speedup over corresponding standard solvers on real-world graphs.

The Area Under the ROC Curve (AUC) is an important model metric for evaluating binary classifiers, and many algorithms have been proposed to optimize AUC approximately. It raises the question of whether the generally insignificant gains observed by previous studies are due to inherent limitations of the metric or the inadequate quality of optimization. To better understand the value of optimizing for AUC, we present an efficient algorithm, namely AUC-opt, to find the provably optimal AUC linear classifier in R2, which runs in O(n+n- log n+n-) where n+ and n- are the number of positive and negative samples respectively. Furthermore, it can be naturally extended to Rd in O(n+n-d-1 log (n+n-)) by recursively calling AUC-opt in lower-dimensional spaces. We prove the problem is NP-complete when d is not fixed, reducing from the open hemisphere problem. Compared with other methods, experiments show that AUC-opt achieves statistically significant improvements between 17 to 40 in R2 and 4 to 42 in R3 of 50 t-SNE training datasets. However, generally, the gain proves insignificant on most testing datasets compared to the best standard classifiers. Similar observations are found for nonlinear AUC methods under real-world datasets.

This paper studies the online node classification problem under a transductive learning setting. Current methods either invert a graph kernel matrix with $\mathcal{O}(n^3)$ runtime and $\mathcal{O}(n^2)$ space complexity or sample a large volume of random spanning trees, thus are difficult to scale to large graphs. In this work, we propose an improvement based on the online relaxation technique introduced by a series of works (Rakhlin et al., 2012; Rakhlin & Sridharan, 2015; 2017). We first prove an effective regret $\mathcal{O}(\sqrt{n^{1+\gamma}})$ when suitable parameterized graph kernels are chosen, then propose an approximate algorithm FastONL enjoying $\mathcal{O}(k\sqrt{n^{1+\gamma}})$ regret based on this relaxation. The key of FastONL is a generalized local push method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the per-prediction cost is $\mathcal{O}(\operatorname{vol}{\mathcal{S}}\log 1/\epsilon)$ locally dependent on the graph with linear memory cost. Experiments show that our scalable method enjoys a better tradeoff between local and global consistency.

Personalized PageRank Vectors are widely used as fundamental graph-learning tools for detecting anomalous spammers, learning graph embeddings, and training graph neural networks. The well-known local FwdPush algorithm[5] approximates PPVs and has a sublinear rate of O(1 over αε). A recent study [51] found that when high precision is required, FwdPush is similar to the power iteration method, and its run time is pessimistically bounded by O(m over α log 1 over ε). This paper looks closely at calculating PPVs for both directed and undirected graphs. By leveraging the linear invariant property, we show that FwdPush is a variant of Gauss-Seidel and propose a Successive Over-Relaxation based method, FwdPushSOR to speed it up by slightly modifying FwdPush. Additionally, we prove FwdPush has local linear convergence rate O(vol (S) over α log 1 over ε) enjoying advantages of two existing bounds. We also design a new local heuristic push method that reduces the number of operations by 10-50 percent compared to FwdPush. For undirected graphs, we propose two momentum-based acceleration methods that can be expressed as one-line updates and speed up non-acceleration methods by O (1 / √ α). Our experiments on six real-world graph datasets confirm the efficiency of FwdPushSOR and the acceleration methods for directed and undirected graphs, respectively.

In this paper, we consider approximate Frank-Wolfe (FW) algorithms to solve convex optimization problems over graph-structured support sets where the linear minimization oracle (LMO) cannot be efficiently obtained in general. We first demonstrate that two popular approximation assumptions (additive and multiplicative gap errors) are not applicable in that no cheap gap-approximate LMO oracle exists. Thus, approximate dual maximization oracles (DMO) are proposed, which approximate the inner product rather than the gap. We prove that the standard FW method using a $\delta$-approximate DMO converges as $O((1-\delta) \sqrt{s}/\delta)$ in the worst case, and as $O(L/(\delta^2 t))$ over a $\delta$-relaxation of the constraint set. Furthermore, when the solution is on the boundary, a variant of FW converges as $O(1/t^2)$ under the quadratic growth assumption. Our empirical results suggest that even these improved bounds are pessimistic, showing fast convergence in recovering real-world images with graph-structured sparsity.

Tracking a targeted subset of nodes in an evolving graph is important for many real-world applications. Existing methods typically focus on identifying anomalous edges or finding anomaly graph snapshots in a stream way. However, edge-oriented methods cannot quantify how individual nodes change over time while others need to maintain representations of the whole graph all the time, thus computationally inefficient.

Dynamic graph representation learning is a task to learn node embeddings over dynamic networks, and has many important applications, including knowledge graphs, citation networks to social networks. Graphs of this type are usually large-scale but only a small subset of vertices are related in downstream tasks. Current methods are too expensive to this setting as the complexity is at best linear-dependent on both the number of nodes and edges.

In this paper, we aim to develop stochastic hard thresholding algorithms for the important problem of AUC maximization in imbalanced classification. The main challenge is the pairwise loss involved in AUC maximization. We overcome this obstacle by reformulating the U-statistics objective function as an empirical risk minimization (ERM), from which a stochastic hard thresholding algorithm (SHT-AUC) is developed. To our best knowledge, this is the first attempt to provide stochastic hard thresholding algorithms for AUC maximization with a per-iteration cost O(bd) where d and b are the dimension of the data and the minibatch size, respectively. We show that the proposed algorithm enjoys the linear convergence rate up to a tolerance error. In particular, we show, if the data is generated from the Gaussian distribution, then its convergence becomes slower as the data gets more imbalanced. We conduct extensive experiments to show the efficiency and effectiveness of the proposed algorithms.

The Area Under the ROC Curve (AUC) is a widely used performance measure for imbalanced classification arising from many application domains where high-dimensional sparse data is abundant. In such cases, each d dimensional sample has only k non-zero features with k ≪ d, and data arrives sequentially in a streaming form. Current online AUC optimization algorithms have high per-iteration cost O(d) and usually produce non-sparse solutions in general, and hence are not suitable for handling the data challenge mentioned above. In this paper, we aim to directly optimize the AUC score for high-dimensional sparse datasets under online learning setting and propose a new algorithm, FTRL-AUC. Our proposed algorithm can process data in an online fashion with a much cheaper per-iteration cost O(k), making it amenable for high-dimensional sparse streaming data analysis. Our new algorithmic design critically depends on a novel reformulation of the U-statistics AUC objective function as the empirical saddle point reformulation, and the innovative introduction of the “lazy update” rule so that the per-iteration complexity is dramatically reduced from O(d) to O(k). Furthermore, FTRL-AUC can inherently capture sparsity more effectively by applying a generalized Follow-The-Regularized-Leader (FTRL) framework. Experiments on real-world datasets demonstrate that FTRL-AUC significantly improves both run time and model sparsity while achieving competitive AUC scores compared with the state-of-the-art methods. Comparison with the online learning method for logistic loss demonstrates that FTRL-AUC achieves higher AUC scores especially when datasets are imbalanced. Experiments on real-world datasets demonstrate that FTRL-AUC significantly improves both run time and model sparsity while achieving competitive AUC scores compared with the state-of-the-art methods. Comparison with the online learning method for logistic loss demonstrates that FTRL-AUC achieves higher AUC scores especially when datasets are imbalanced.

The motives and means of explicit state censorship have been well studied, both quantitatively and qualitatively. Self-censorship by media outlets, however, has not received nearly as much attention, mostly because it is difficult to systematically detect. We develop a novel approach to identify news media self-censorship by using social media as a sensor. We develop a hypothesis testing framework to identify and evaluate censored clusters of keywords and a near-linear-time algorithm (called GraphDPD) to identify the highest scoring clusters as indicators of censorship. We evaluate the accuracy of our framework, versus other state-of-the-art algorithms, using both semi-synthetic and real-world data from Mexico and Venezuela during Year 2014. These tests demonstrate the capacity of our framework to identify self-censorship, and provide an indicator of broader media freedom. The results of this study lay the foundation for detection, study, and policy-response to self-censorship.

Stochastic optimization algorithms update models with cheap per-iteration costs sequentially, which makes them amenable for large-scale data analysis. Such algorithms have been widely studied for structured sparse models where the sparsity information is very specific, e.g., convex sparsity-inducing norms or $\ell^0$-norm. However, these norms cannot be directly applied to the problem of complex (non-convex) graph-structured sparsity models, which have important application in disease outbreak and social networks, etc. In this paper, we propose a stochastic gradient-based method for solving graph-structured sparsity constraint problems, not restricted to the least square loss. We prove that our algorithm enjoys a linear convergence up to a constant error, which is competitive with the counterparts in the batch learning setting. We conduct extensive experiments to show the efficiency and effectiveness of the proposed algorithms.

Online learning algorithms update models via one sample per iteration, thus efficient to process large-scale datasets and useful to detect malicious events for social benefits, such as disease outbreak and traffic congestion on the fly. However, existing algorithms for graph-structured models focused on the offline setting and the least square loss, incapable for online setting, while methods designed for online setting cannot be directly applied to the problem of complex (usually non-convex) graph-structured sparsity model. To address these limitations, in this paper we propose a new algorithm for graph-structured sparsity constraint problems under online setting, which we call GraphDA. The key part in GraphDA is to project both averaging gradient (in dual space) and primal variables (in primal space) onto lower dimensional subspaces, thus capturing the graph-structured sparsity effectively. Furthermore, the objective functions assumed here are generally convex so as to handle different losses for online learning settings. To the best of our knowledge, GraphDA is the first online learning algorithm for graph-structure constrained optimization problems. To validate our method, we conduct extensive experiments on both benchmark graph and real-world graph datasets. Our experiment results show that, compared to other baseline methods, GraphDA not only improves classification performance, but also successfully captures graph-structured features more effectively, hence stronger interpretability.

The area of anomaly detection has recently been expanded in the graph-based data. Anomalous vertices are often exhibited as a connected subgraph. Few works, however, have focused on connected anomalous subgraph detection because of the challenge of optimizing graph functionals under connectivity constraints. We employ Non-Parametric Graph Scan (NPGS) statistics for detecting anomalies within graph-based data. Based on the NPGS statistics, we proposed an efficient approximate approach to the connected anomalous subgraph detection problem that provides provable guarantees on performance and quality. In particular, we first decompose the problem into a sequence of subproblems, each of which can be reduced to a Budget Price-Collecting Steiner Tree (BPCST) problem, and then develop efficient exact and approximate algorithms for a special category of graphs in which the anomalous subgraphs can be reformulated in a fixed tree topology. Our method has a wide variety of applications, such as disease outbreak detection, road traffic congestion detection, and event detection in social media, because the NPGS statistics is free of distribution assumptions and can be applied to heterogeneous graph data.

Recently, some picture-embedding schemes have been proposed to improve the aesthetic appearance of 2D barcodes. However, these aesthetic 2D barcodes are not robust to the distortions incurred by the print/display-and-capture channel under limited rendering space and resolution. In this paper, a picture-embedding 2D barcode named the Robust and Aesthetic (RA) Code is proposed to counter the channel impairments, such as downsampling error and inter-symbol interference. Experimental results demonstrate that the proposed RA Code is more robust than the existing picture-embedding 2D barcodes, especially under limited printing/displaying space. The RA Code of a size as small as 1.5 × 1.5 cm2can be successfully decoded with a demodulated bit error probability of less than 0.1, which corresponds to more than 50% improvement over those of the state-of-the-art picture-embedding 2D barcodes. In addition, the correct decoding probability is improved significantly from as low as 0 to more than 0.8650. The decoding algorithm has been implemented on the Android platform, and the practicality of the RA Code has been successfully demonstrated.

Detection of interesting (e.g., coherent or anomalous) clusters has been studied extensively on plain or univariate networks, with various applications. Recently, algorithms have been extended to networks with multiple attributes for each node in the real-world. In a multi-attributed network, often, a cluster of nodes is only interesting for a subset (subspace) of attributes, andthis type of clusters is called subspace clusters. However, in the current literature, few methods are capable of detecting subspace clusters, which involves concurrent feature selection and network cluster detection. These relevant methods are mostly heuristic-driven and customized for specific application scenarios. In this work, we present a generic and theoretical framework for detection of interesting subspace clusters in large multi-attributed networks. Specifically, we propose a subspace graph-structured matching pursuit algorithm, namely, SG-Pursuit, to address a broad class of such problems for different scorefunctions (e.g., coherence or anomalous functions) and topology constraints (e.g., connected subgraphs and dense subgraphs). We prove that our algorithm 1) runs in nearly-linear time on the network size and the total number of attributes and 2) enjoys rigorous guarantees (geometrical convergence rate and tight error bound) analogous to those of the state-of-the-art algorithms for sparse feature selection problems and subgraph detection problems. As a case study, we specialize SG-Pursuit to optimizea number of well-known score functions for two typical tasks, including detection of coherent dense and anomalous connected subspace clusters in real-world networks. Empirical evidence demonstrates that our proposed generic algorithm SG-Pursuit is superior over state-of-the-art methods that are designed specifically for these two tasks.

Summary For the many application domains concerning entities and their connections, often their data can be formally represented as graphs and an important problem is detecting an anomalous subgraph within it. Numerous methods have been proposed to speed‐up anomalous subgraph detection; however, each incurs non‐trivial costs on detection accuracy. In this paper, we formulate the anomalous subgraph detection problem as the maximization of a non‐parametric scan statistic and then approximate it to a submodular maximization problem. We propose two parallel algorithms: non‐coordination anomalous subgraph detection (NCASD) and under‐coordination anomalous subgraph detection (UCASD)for the anomalous subgraph detection. To the best of our knowledge, this paper is the first to solve this problem in parallel. NCASD emphasizes speed at the expense of approximation guarantees, while UCASD achieves a higher approximation factor through additional coordination controls and reduced parallelism. The experiments demonstrate the effectiveness and efficiency of our proposed approaches in a real‐world application domain (water pollution detection), comparing them with five other state‐of‐the‐art methods. Copyright © 2016 John Wiley & Sons, Ltd.

Non-parametric graph scan (NPGS) statistics are used to detect anomalous connected subgraphs on graphs, and have a wide variety of applications, such as disease outbreak detection, road traffic congestion detection, and event detection in social media. In contrast to traditional parametric scan statistics (e.g., the Kulldorff statistic), NPGS statistics are free of distributional assumptions and can be applied to heterogeneous graph data. In this paper, we make a number of contributions to the computational study of NPGS statistics. First, we present a novel reformulation of the problem as a sequence of Budget Price-Collecting Steiner Tree (B-PCST) sub-problems. Second, we show that this reformulated problem is NP-hard for a large class of nonparametric statistic functions. Third, we further develop efficient exact and approximate algorithms for a special category of graphs in which the anomalous subgraphs can be reformulated in a fixed tree topology. Finally, using extensive experiments we demonstrate the performance of our proposed algorithms in two real-world application domains (water pollution detection in water sensor networks and spatial event detection in social media networks) and contrast against state-of-the-art connected subgraph detection methods.

In the scenario of random linear network coding, the channel input and output are matrices over a finite field related by a multiplicative channel matrix. Such channels are called the multiplicative finite-field matrix channels (MFFMC). To communicate over such channels, subspace coding is a promising non-coherent network coding approach which does not require the estimation of the channel matrix. The capacity of subspace coding over the general MFFMC is still unknown (except for some special cases, such as the purely random channel and the uniform full rank channel). In this paper, for a given rank distribution, a class of worst-case channels is characterized and proved to achieve the minimum capacity of subspace coding. Hence the capacity of such a class of channels can serve as the tightest lower bound on the capacity of subspace coding over the MFFMC. Interestingly, for the purely random channel, the uniform full rank channel and the uniform given rank channel, our bound gives the exact value of the capacity of subspace coding. Numerical results show that our bound is tighter than some existing bound at small-to-moderate packet lengths.

The compute-and-forward scheme for wireless relay networks can achieve higher transmission rates than other existing relaying schemes, such as decode-and-forward. The compute-and-forward (CF) design involves finding an integer-valued coefficient vector at each relay so that the set of coefficient vectors form a full rank matrix allowing the destination to perform decoding. The CF design problem is relevant to an instance of the famous shortest lattice vector problem and has attracted much recent research attention. Two representative CF designs, the so-called local optimization scheme and the Wei-Chen scheme, have been introduced in the literature. However, they either achieve relatively low transmission rate, or require a relatively high communication overhead. In this paper, we propose a new compute-and-forward design that can achieve a significantly higher transmission rate than the local optimization scheme and requires a much lower communication overhead than the Wei-Chen scheme. In particular, the new scheme does not require a list of candidate coefficient vectors and their computation rates to be forwarded from each relay to the destination, and hence avoids the heavy communication overhead incurred. Simulation results for a 2-hop wireless relay network with channel vectors consisting of i.i.d. Gaussian entries are presented to demonstrate the transmission rate improvement of the proposed scheme relative to the local optimization scheme. For example, it is shown that the proposed scheme can achieve about 2.5dB gain at moderate SNR in the case of 8 sources/relays.

Spatial event detection is an important and challenging problem. Unlike traditional event detection that focuses on the timing of global urgent event, the task of spatial event detection is to detect the spatial regions (e.g. clusters of neighboring cities) where urgent events occur. In this paper, we focus on the problem of spatial event detection using textual information in social media. We observe that, when a spatial event occurs, the topics relevant to the event are often discussed more coherently in cities near the event location than those far away. In order to capture this pattern, we propose a new method called Graph Topic Scan Statistic (Graph-TSS) that corresponds to a generalized log-likelihood ratio test based on topic modeling. We first demonstrate that the detection of spatial event regions under Graph-TSS is NP-hard due to a reduction from classical node-weighted prize-collecting Steiner tree problem (NW-PCST). We then design an efficient algorithm that approximately maximizes the graph topic scan statistic over spatial regions of arbitrary form. As a case study, we consider three applications using Twitter data, including Argentina civil unrest event detection, Chile earthquake detection, and United States influenza disease outbreak detection. Empirical evidence demonstrates that the proposed Graph-TSS performs superior over state-of-the-art methods on both running time and accuracy.

Structured sparse optimization is an important and challenging problem for analyzing high-dimensional data in a variety of applications such as bioinformatics, medical imaging, social networks, and astronomy. Although a number of structured sparsity models have been explored, such as trees, groups, clusters, and paths, connected subgraphs have been rarely explored in the current literature. One of the main technical challenges is that there is no structured sparsity-inducing norm that can directly model the space of connected subgraphs, and there is no exact implementation of a projection oracle for connected subgraphs due to its NP-hardness. In this paper, we explore efficient approximate projection oracles for connected subgraphs, and propose two new efficient algorithms, namely, Graph-IHT and Graph-GHTP, to optimize a generic nonlinear objective function subject to connectivity constraint on the support of the variables. Our proposed algorithms enjoy strong guarantees analogous to several current methods for sparsity-constrained optimization, such as Projected Gradient Descent (PGD), Approximate Model Iterative Hard Thresholding (AM-IHT), and Gradient Hard Thresholding Pursuit (GHTP) with respect to convergence rate and approximation accuracy. We apply our proposed algorithms to optimize several well-known graph scan statistics in several applications of connected subgraph detection as a case study, and the experimental results demonstrate that our proposed algorithms outperform state-of-the-art methods.

Nowadays, 2D barcodes have been widely used as an interface to connect potential customers and advertisement contents. However, the appearance of a conventional 2D barcode pattern is often too obtrusive for integrating into an aesthetically designed advertisement. Besides, no human readable information is provided before the barcode is successfully decoded. This paper proposes a new picture-embedding 2D barcode, called PiCode, which mitigates these two limitations by equipping a scannable 2D barcode with a picturesque appearance. PiCode is designed with careful considerations on both the perceptual quality of the embedded image and the decoding robustness of the encoded message. Comparisons with the existing beautified 2D barcodes show that PiCode achieves one of the best perceptual qualities for the embedded image, and maintains a better tradeoff between image quality and decoding robustness in various application conditions. PiCode has been implemented in the MATLAB on a PC and some key building blocks have also been ported to Android and iOS platforms. Its practicality for real-world applications has been successfully demonstrated.

We consider the problem of finding the optimal coefficient vector that maximizes the computation rate at a relay in the compute-and-forward scheme. Based on the idea of sphere decoding, we propose a highly efficient algorithm that finds the optimal coefficient vector. First, we derive a novel algorithm to transform the original quadratic form optimization problem into a shortest vector problem (SVP) using the Cholesky factorization. Instead of computing the Cholesky factor explicitly, the proposed algorithm realizes the Cholesky factorization with only O(n) flops by taking advantage of the structure of the Gram matrix in the quadratic form. Then, we propose some conditions that can be checked with O(n) flops, under which a unit vector is the optimal coefficient vector. Finally, by considering some useful properties of the optimal coefficient vector, we modify the Schnorr-Euchner search algorithm to solve the SVP. We show that the estimated average complexity of our new algorithm is O(n1.5p0.5) flops for independent identically distributed (i.i.d.) Gaussian channel entries with SNR P based on the Gaussian heuristic. Simulations show that our algorithm is not only much more efficient than the existing ones that give the optimal solution, but also faster than some best known suboptimal methods. Besides, we show that our algorithm can be readily adapted to output a list of L best candidate vectors for use in the compute-and-forward design. The estimated average complexity of the resultant list-output algorithm is O(n2.5p0.5+ n1.5p0.5log(L) + nL) flops for i.i.d. Gaussian channel entries.

We consider the compute-and-forward protocol design problem with the objective being maximizing the computation rate at a single relay, and propose an efficient method that finds the optimal solution based on sphere decoding. The problem can be transformed into a shortest vector problem (SVP), which can be solved in two steps. First, by fully exploiting the specific structure of the associated Gram matrix using the hyperbolic transformation, the Cholesky factor can be computed with only n2/2 + O(n) flops. Then, taking into account of some useful properties of the optimal solution, we modify the Schnorr-Euchner search algorithm to solve the SVP. Numerical results show that our proposed branch-and-bound method is much more efficient than the existing one that gives the optimal solution. Besides, compared with the suboptimal methods, our method offers the best performance at a cost lower than that of the LLL based method and similar to that of the quadratic programming relaxation method.

In wireless networks, the compute-and-forward strategy is a promising physical layer network coding scheme that can achieve high rates by effectively exploiting the interference between users. However, the design of the optimal integer-valued equation coefficient vectors in a compute-and-forward scheme turns out to be a shortest vector problem, which is known to be NP hard. In this work, we consider the problem of designing the equation coefficient vector for each relay with the objective being maximizing the computation rate at that relay. By taking advantage of some useful properties, we show that the problem can be relaxed to a series of equality-constrained quadratic programmings and their closed-form solutions are derived by use of the Lagrange multiplier method, which is the key to the efficiency of our method. A quantization algorithm is then proposed to transform the real-valued approximations to the set of required integer-valued vectors, from which a suboptimal equation coefficient vector is obtained. Numerical results demonstrate that relative to existing methods, our method can offer comparable performance at an impressively low complexity.