Since its inception, Facebook has become an integral part of the online social community. People rely on Facebook to connect with others and build communities. As a result, it is paramount to protect the integrity of such a large network in a fast and scalable manner. In this paper, we present our efforts to protect various social media entities at Facebook from people who try to abuse our platform. We present a novel Temporal Interaction EmbeddingS (TIES) model that is designed to capture rogue social interactions and flag them for further suitable actions. TIES is a supervised, deep learning, production ready model at Facebook-scale networks. Prior works on integrity problems are mostly focused on capturing either only static or certain dynamic features of social entities. In contrast, TIES can capture both these variant behaviors in a unified model owing to the recent strides made in the domains of graph embedding and deep sequential pattern learning. To show the real-world impact of TIES, we present a few applications especially for preventing spread of misinformation, fake account detection, and reducing ads payment risks in order to enhance Facebook platform's integrity.

The belief propagation (BP) or sum-product algorithm is a widely used message-passing method for computing marginal distributions in graphical models. At the core of the BP message updates, when applied to a graphical model involving discrete variables with pairwise interactions, lies a matrix-vector product with complexity that is quadratic in the state dimensiond, and requires transmission of a (d-1)-dimensional vector of real numbers (messages) to its neighbors. Since various applications involve very large state dimensions, such computation and communication complexities can be prohibitively complex. In this paper, we propose a low-complexity variant of BP, referred to as stochastic belief propagation (SBP). As suggested by the name, it is an adaptively randomized version of the BP message updates in which each node passes randomly chosen information to each of its neighbors. The SBP message updates reduce the computational complexity (per iteration) from quadratic to linear ind, without assuming any particular structure of the potentials, and also reduce the communication complexity significantly, requiring only log2dbits transmission per edge. Moreover, we establish a number of theoretical guarantees for the performance of SBP, showing that it converges almost surely to the BP fixed point for any tree-structured graph, and for any graph with cycles satisfying a contractivity condition. In addition, for these graphical models, we provide nonasymptotic upper bounds on the convergence rate, showing that thel∞norm of the error vector decays no slower thanO(1/√t) with the number of iterationston trees and the normalized mean-squared error decays asO(1/t) for general graphs. This analysis, also supported by experimental results, shows that SBP can provably yield reductions in computational and communication complexities for various classes of graphical models.

Belief propagation (BP) is a widely used algorithm for computing the marginal distributions in graphical models. However, in applications involving continuous random variables, the messages themselves are real-valued functions, which leads to significant computational bottlenecks. In this paper, we propose a low complexity method for performing belief propagation for continuous state space problems. Our algorithm, which we refer to as quantized stochastic belief propagation (QSBP), is a randomized variant of BP in which each node only passes stochastically chosen information at each round. The most attractive feature of QSBP is its significant gain in computational and communication efficiencies. In addition, we provide some theoretical guarantees including almost sure convergence and the rate of convergence for the case of tree-structured graphical models.

We introduce an efficient family of exact regenerating codes for data storage in large-scale distributed systems. We refer to these new codes as Distributed Replication-based Exact Simple Storage (DRESS) codes. A key property of DRESS codes is their very efficient distributed and uncoded repair and growth processes that have minimum bandwidth, reads and computational overheads. This property is essential for large-scale systems with high reliability and availability requirements. DRESS codes will first encode the file using a Maximum Distance Separable (MDS) code, then place multiple replicas of the coded packets on different nodes in the system. We propose a simple and flexible randomized scheme for placing those replicas based on the balls-and-bins model. Our construction showcases the power of the probabilistic approach in constructing regenerating codes that can be efficiently repaired and grown.

The problem of network-constrained averaging is to compute the average of a collection of a set of values distributed throughout a network using an algorithm that can pass messages only along edges of the network. We study this problem in the noisy setting, in which the communication along each link is modeled by an additive white Gaussian noise channel. We propose a two-phase decentralized stochastic algorithm, and we use stochastic approximation methods to analyze how the number of iterations required to achieve mean-squared error d scales as the number of nodes n in the graph. Previous results provided guarantees with the number of iterations scaling inversely with the spectral gap of the graph (second smallest eigenvalue of the Laplacian). In this paper, we prove that our proposed algorithm reduces this graph dependence, up to logarithmic conditions, to the graph diameter, which cannot be improved upon by any algorithm.