EKEdward K. Kao

Edward K. Kao

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Edward K. Kao has a total of 39 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Top-Down SBP: Turning Graph Clustering Upside Down

    by Frank Wanye, Vitaliy Gleyzer, Edward Kao, Wu-Chun Feng


  • SamBaS: Sampling-Based Stochastic Block Partitioning

    by Frank Wanye, Vitaliy Gleyzer, Edward Kao, Wu-Chun Feng

    Community detection is a well-studied problem with applications in domains ranging from networking to bioinformatics. Due to the rapid growth in the volume of real-world data, there is growing interest in accelerating contemporary community detection algorithms. However, the more accurate and statistically robust methods tend to be hard to parallelize. One such method is stochastic block partitioning (SBP) – a community detection algorithm that works well on graphs with complex and heterogeneous community structure. In this paper, we present a sam pling- ba sed S BP ( SamBaS ) for accelerating SBP on sparse graphs. We characterize how various graph parameters affect the speedup and result quality of community detection with SamBaS and quantify the trade-offs therein. To evaluate SamBas on real-world web graphs without known ground-truth communities, we introduce p artition q uality s core (PQS), an evaluation metric that outperforms modularity in terms of correlation with F1 score. Overall, SamBaS achieves speedups of up to 10× while maintaining result quality (and even improving result quality by over 150% on certain graphs, relative to F1 score).


  • Open Access

    Exact Distributed Stochastic Block Partitioning

    by Frank Wanye, Vitaliy Gleyzer, Edward Kao, Wu-Chun Feng

    Stochastic block partitioning (SBP) is a community detection algorithm that is highly accurate even on graphs with a complex community structure, but its inherently serial nature hinders its widespread adoption by the wider scientific community. To make it practical to analyze large real-world graphs with SBP, there is a growing need to parallelize and distribute the algorithm. The current state-of-the-art distributed SBP algorithm is a divide-and-conquer approach that limits communication between compute nodes until the end of inference. This leads to the breaking of computational dependencies, which causes convergence issues as the number of compute nodes increases, and when the graph is sufficiently sparse. In this paper, we introduce EDiSt - an exact distributed stochastic block partitioning algorithm. Under EDiSt, compute nodes periodically share community assignments during inference. Due to this additional communication, EDiSt improves upon the divide-and-conquer algorithm by allowing it to scale out to a larger number of compute nodes without suffering from convergence issues, even on sparse graphs. We show that EDiSt provides speedups of up to 23.8X over the divide-and-conquer approach, and speedups up to 38.0X over shared memory parallel SBP when scaled out to 64 compute nodes.

  • Top Cited Papers
    Open Access

    Automatic detection of influential actors in disinformation networks

    by Steven T. Smith, Edward K. Kao, Erika D. Mackin, Danelle C. Shah, Olga Simek, Donald B. Rubin

    Significance: Hostile influence operations (IOs) that weaponize digital communications and social media pose a rising threat to open democracies. This paper presents a system framework to automate detection of disinformation narratives, networks, and influential actors. The framework integrates natural language processing, machine learning, graph analytics, and network causal inference to quantify the impact of individual actors in spreading the IO narrative. We present a classifier that detects reported IO accounts with 96% precision, 79% recall, and 96% AUPRC, demonstrated on real social media data collected for the 2017 French presidential election and known IO accounts disclosed by Twitter. Our system also discovers salient network communities and high-impact accounts that are independently corroborated by US Congressional reports and investigative journalism.


  • Influence Estimation on Social Media Networks Using Causal Inference

    by Steven T. Smith, Edward K. Kao, Danelle C. Shah, Olga Simek, Donald B. Rubin

    Estimating influence on social media networks is an important practical and theoretical problem, especially because this new medium is widely exploited as a platform for disinformation and propaganda. This paper introduces a novel approach to influence estimation on social media networks and applies it to the real-world problem of characterizing active influence operations on Twitter during the 2017 French presidential elections. The new influence estimation approach attributes impact by accounting for narrative propagation over the network using a network causal inference framework applied to data arising from graph sampling and filtering. This causal framework infers the difference in outcome as a function of exposure, in contrast to existing approaches that attribute impact to activity volume or topological features, which do not explicitly measure nor necessarily indicate actual network influence. Cramér-Rao estimation bounds are derived for parameter estimation as a step in the causal analysis, and used to achieve geometrical insight on the causal inference problem. The ability to infer high causal influence is demonstrated on real-world social media accounts that are later independently confirmed to be either directly affiliated or correlated with foreign influence operations using evidence supplied by the U.S. Congress and journalistic reports.


  • Open Access

    Influence Estimation on Social Media Networks Using Causal Inference

    by Steven T. Smith, Edward K. Kao, Danelle C. Shah, Olga Simek, Donald B. Rubin

    Estimating influence on social media networks is an important practical and theoretical problem, especially because this new medium is widely exploited as a platform for disinformation and propaganda. This paper introduces a novel approach to influence estimation on social media networks and applies it to the real-world problem of characterizing active influence operations on Twitter during the 2017 French presidential elections. The new influence estimation approach attributes impact by accounting for narrative propagation over the network using a network causal inference framework applied to data arising from graph sampling and filtering. This causal framework infers the difference in outcome as a function of exposure, in contrast to existing approaches that attribute impact to activity volume or topological features, which do not explicitly measure nor necessarily indicate actual network influence. Cram\'er-Rao estimation bounds are derived for parameter estimation as a step in the causal analysis, and used to achieve geometrical insight on the causal inference problem. The ability to infer high causal influence is demonstrated on real-world social media accounts that are later independently confirmed to be either directly affiliated or correlated with foreign influence operations using evidence supplied by the U.S. Congress and journalistic reports.

  • Open Access

    Hybrid Mixed-Membership Blockmodel for Inference on Realistic Network Interactions

    by Edward K. Kao, Steven Thomas Smith, Edoardo M. Airoldi

    This work proposes novel hybrid mixed-membership blockmodels (HMMB) that integrate three canonical network models to capture the characteristics of real-world interactions: community structure with mixed-membership, power-law-distributed node degrees, and sparsity. This hybrid model provides the capacity needed for realism, enabling control and inference on individual attributes of interest such as mixed-membership and popularity. A rigorous inference procedure is developed for estimating the parameters of this model through iterative Bayesian updates, with targeted initialization to improve identifiability. For the estimation of mixed-membership parameters, the Cramér-Rao bound is derived by quantifying the information content in terms of the Fisher information matrix. The effectiveness of the proposed inference is demonstrated in simulations where the estimates achieve covariances close to the Cramér-Rao bound while maintaining good truth coverage. We illustrate the utility of the proposed model and inference procedure in the application of detecting a community from a few cue nodes, where success depends on accurately estimating the mixed-memberships. Performance evaluations on both simulated and real-world data show that inference with HMMB is able to recover mixed-memberships in the presence of challenging community overlap, leading to significantly improved detection performance over algorithms based on network modularity and simpler models.


  • Streaming graph challenge: Stochastic block partition

    by Edward Kao, Vijay Gadepally, Michael Hurley, Michael Jones, Jeremy Kepner, Sanjeev Mohindra, Paul Monticciolo, Albert Reuther, Siddharth Samsi, William Song, et al.

    An important objective for analyzing real-world graphs is to achieve scalable performance on large, streaming graphs. A challenging and relevant example is the graph partition problem. As a combinatorial problem, graph partition is NP-hard, but existing relaxation methods provide reasonable approximate solutions that can be scaled for large graphs. Competitive benchmarks and challenges have proven to be an effective means to advance state-of-the-art performance and foster community collaboration. This paper describes a graph partition challenge with a baseline partition algorithm of sub-quadratic complexity. The algorithm employs rigorous Bayesian inferential methods based on a statistical model that captures characteristics of the real-world graphs. This strong foundation enables the algorithm to address limitations of well-known graph partition approaches such as modularity maximization. This paper describes various aspects of the challenge including: (1) the data sets and streaming graph generator, (2) the baseline partition algorithm with pseudocode, (3) an argument for the correctness of parallelizing the Bayesian inference, (4) different parallel computation strategies such as node-based parallelism and matrix-based parallelism, (5) evaluation metrics for partition correctness and computational requirements, (6) preliminary timing of a Python-based demonstration code and the open source C++ code, and (7) considerations for partitioning the graph in streaming fashion. Data sets and source code for the algorithm as well as metrics, with detailed documentation are available at GraphChallenge.org.


  • Static graph challenge: Subgraph isomorphism

    by Siddharth Samsi, Vijay Gadepally, Michael Hurley, Michael Jones, Edward Kao, Sanjeev Mohindra, Paul Monticciolo, Albert Reuther, Steven Smith, William Song, et al.

    The rise of graph analytic systems has created a need for ways to measure and compare the capabilities of these systems. Graph analytics present unique scalability difficulties. The machine learning, high performance computing, and visual analytics communities have wrestled with these difficulties for decades and developed methodologies for creating challenges to move these communities forward. The proposed Subgraph Isomorphism Graph Challenge draws upon prior challenges from machine learning, high performance computing, and visual analytics to create a graph challenge that is reflective of many real-world graph analytics processing systems. The Subgraph Isomorphism Graph Challenge is a holistic specification with multiple integrated kernels that can be run together or independently. Each kernel is well defined mathematically and can be implemented in any programming environment. Subgraph isomorphism is amenable to both vertex-centric implementations and array-based implementations (e.g., using the Graph-BLAS.org standard). The computations are simple enough that performance predictions can be made based on simple computing hardware models. The surrounding kernels provide the context for each kernel that allows rigorous definition of both the input and the output for each kernel. Furthermore, since the proposed graph challenge is scalable in both problem size and hardware, it can be used to measure and quantitatively compare a wide range of present day and future systems. Serial implementations in C++, Python, Python with Pandas, Matlab, Octave, and Julia have been implemented and their single threaded performance have been measured. Specifications, data, and software are publicly available at GraphChallenge.org.


  • Open Access

    Bayesian Discovery of Threat Networks

    by Steven Thomas Smith, Edward K. Kao, Kenneth D. Senne, Garrett Bernstein, Scott Philips

    A novel unified Bayesian framework for network detection is developed, under which a detection algorithm is derived based on random walks on graphs. The algorithm detects threat networks using partial observations of their activity, and is proved to be optimum in the Neyman–Pearson sense. The algorithm is defined by a graph, at least one observation, and a diffusion model for threat. A link to well-known spectral detection methods is provided, and the equivalence of the random walk and harmonic solutions to the Bayesian formulation is proven. A general diffusion model is introduced that utilizes spatio-temporal relationships between vertices, and is used for a specific space-time formulation that leads to significant performance improvements on coordinated covert networks. This performance is demonstrated using a new hybrid mixed-membership blockmodel introduced to simulate random covert networks with realistic properties.