Friend or Faux: Graph-Based Early Detection of Fake Accounts on Social Networks
Adam Breuer, Roee Eilat (Facebook Research), Udi Weinsberg (Facebook Research)
Published + Oral Presentation in the 29th ACM The Web Conference 2020 (WWW’20)
*Download PDF*

Summary: Fake accounts are the main source of fake news on social networks, and Facebook disabled over 6 billion fake accounts in 2019. We present the first social network-based algorithm capable of reliably detecting fake accounts (AUC>0.9) among new social network users before they have made many connections. We implement this algorithm at scale at Facebook and show that it outperforms state-of-the-art algorithms.

Memes, narratives and the emergent US–China security dilemma
Adam Breuer and Alastair Iain Johnston
Published in Cambridge Review of International Affairs vol. 32.4
*Download PDF*

Summary: The US–China rivalry is associated with a prominent meme that describes China as ‘challenging the international rules-based order’ (RBO). We theorize that tracking the speed and spread of such memes provides both a useful indicator of security dilemma dynamics and a basis on which to theorize the process by which security narratives emerge in international relations. We assemble a database of the full texts of virtually every online English-language article published about China, and we use plagiarism analysis to reconstruct the network of inter-media and government-media influences responsible for the spread of the RBO meme over time. We provide preliminary evidence that the RBO meme may be crowding out other, less malign narratives about China’s rise.

The FAST Algorithm for Submodular Maximization
Adam Breuer, Eric Balkanski, and Yaron Singer
Published in ICML 2020
*Download PDF* *Link to talk available July 18* Code & Replication

Summary: Across machine learning, social network analysis, and algorithms, many fundamental objectives we care to optimize are submodular, such as influence, innovation diffusion, clustering, mutual information, feature selection, and data summarization. Recently, there has been a great deal of research on parallel algorithms for submodular maximization whose theoretical runtime on an idealized parallel machine is exponentially faster than algorithms used over the past 40 years. However, it is computationally infeasible to use these algorithms in practice even on small data sets. In this paper, we a new parallel algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint k. The design principles behind the FAST algorithm are a significant departure from recent theoretically fast algorithms. These principles yield theoretic guarantees that are competitive with recent theoretically fast algorithms, but superior practical performance. Specifically, we show that FAST is orders of magnitude faster than any known algorithm for submodular maximization, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets.

Non-monotone Submodular Maximization in Exponentially Fewer Iterations
Eric Balkanski, Adam Breuer, and Yaron Singer
Published in NeurIPS/NIPS 2018
*Download PDF*

Summary: We introduce an algorithm that achieves an approximation to constrained non-monotone submodular maximization exponentially faster than any previously studied algorithm. We show applications to several domains in machine learning and optimization.