Publications

Refine Results

(Filters Applied) Clear All

By

GraphChallenge.org triangle counting performance [e-print]

September 22, 2020
  |
Conference Paper
Author:
Siddharth S. Samsi
…
Published in:
2020 IEEE High Performance Computing Conf., HPEC, 22-24 September 2020.
Topic:
graph processing
R&D area:
R&D group:

Summary

The rise of graph analytic systems has created a need for new ways to measure and compare the capabilities of graph processing systems. The MIT/Amazon/IEEE Graph Challenge has been developed to provide a well-defined community venue for stimulating research and highlighting innovations in graph analysis software, hardware, algorithms, and systems. GraphChallenge.org provides a wide range of preparsed graph data sets, graph generators, mathematically defined graph algorithms, example serial implementations in a variety of languages, and specific metrics for measuring performance. The triangle counting component of GraphChallenge.org tests the performance of graph processing systems to count all the triangles in a graph and exercises key graph operations found in many graph algorithms. In 2017, 2018, and 2019 many triangle counting submissions were received from a wide range of authors and organizations. This paper presents a performance analysis of the best performers of these submissions. These submissions show that their state-of-the-art triangle counting execution time, Ttri, is a strong function of the number of edges in the graph, Ne, which improved significantly from 2017 (Ttri \approx (Ne/10^8)^4=3) to 2018 (Ttri \approx Ne/10^9) and remained comparable from 2018 to 2019. Graph Challenge provides a clear picture of current graph analysis systems and underscores the need for new innovations to achieve high performance on very large graphs
READ LESS

Summary

The rise of graph analytic systems has created a need for new ways to measure and compare the capabilities of graph processing systems. The MIT/Amazon/IEEE Graph Challenge has been developed to provide a well-defined community venue for stimulating research and highlighting innovations in graph analysis software, hardware, algorithms, and systems...

READ MORE
GraphChallenge.org triangle counting performance [e-print]

GraphChallenge.org: raising the bar on graph analytic performance

September 25, 2018
  |
Conference Paper
Author:
Siddharth S. Samsi
…
Published in:
IEEE High Performance Extreme Computing Conf., HPEC, 25-27 September 2018.
Topic:
high performance computing
R&D area:
R&D group:

Summary

The rise of graph analytic systems has created a need for new ways to measure and compare the capabilities of graph processing systems. The MIT/Amazon/IEEE Graph Challenge has been developed to provide a well-defined community venue for stimulating research and highlighting innovations in graph analysis software, hardware, algorithms, and systems. GraphChallenge.org provides a wide range of preparsed graph data sets, graph generators, mathematically defined graph algorithms, example serial implementations in a variety of languages, and specific metrics for measuring performance. Graph Challenge 2017 received 22 submissions by 111 authors from 36 organizations. The submissions highlighted graph analytic innovations in hardware, software, algorithms, systems, and visualization. These submissions produced many comparable performance measurements that can be used for assessing the current state of the art of the field. There were numerous submissions that implemented the triangle counting challenge and resulted in over 350 distinct measurements. Analysis of these submissions show that their execution time is a strong function of the number of edges in the graph, Ne, and is typically proportional to N4=3 e for large values of Ne. Combining the model fits of the submissions presents a picture of the current state of the art of graph analysis, which is typically 108 edges processed per second for graphs with 108 edges. These results are 30 times faster than serial implementations commonly used by many graph analysts and underscore the importance of making these performance benefits available to the broader community. Graph Challenge provides a clear picture of current graph analysis systems and underscores the need for new innovations to achieve high performance on very large graphs.
READ LESS

Summary

The rise of graph analytic systems has created a need for new ways to measure and compare the capabilities of graph processing systems. The MIT/Amazon/IEEE Graph Challenge has been developed to provide a well-defined community venue for stimulating research and highlighting innovations in graph analysis software, hardware, algorithms, and systems...

READ MORE
GraphChallenge.org: raising the bar on graph analytic performance

Streaming graph challenge: stochastic block partition

September 12, 2017
  |
Conference Paper
Author:
Edward K. Kao
…
Published in:
HPEC 2017: IEEE Conf. on High Performance Extreme Computing, 12-14 September 2017.
Topic:
supercomputing
R&D area:
R&D group:

Summary

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.
READ LESS

Summary

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...

READ MORE
Streaming graph challenge: stochastic block partition

Static graph challenge: subgraph isomorphism

September 12, 2017
  |
Conference Paper
Author:
Siddharth S. Samsi
…
Published in:
HPEC 2017: IEEE Conf. on High Performance Extreme Computing, 12-14 September 2017.
Topic:
supercomputing
R&D area:
R&D group:

Summary

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.
READ LESS

Summary

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...

READ MORE
Static graph challenge: subgraph isomorphism

Collaborative Data Analysis and Discovery for Cyber Security

June 22, 2016
  |
Conference Paper
Author:
Diane P. Staheli
…
Published in:
Proceedings of the 12th Symposium on Usable Privacy and Security (SOUPS 2016)
Topic:
visualization
R&D area:
R&D group:

Summary

In this paper, we present the Cyber Analyst Real-Time Integrated Notebook Application (CARINA). CARINA is a collaborative investigation system that aids in decision making by co-locating the analysis environment with centralized cyber data sources, and providing next generation analysts with increased visibility to the work of others.
READ LESS

Summary

In this paper, we present the Cyber Analyst Real-Time Integrated Notebook Application (CARINA). CARINA is a collaborative investigation system that aids in decision making by co-locating the analysis environment with centralized cyber data sources, and providing next generation analysts with increased visibility to the work of others.

READ MORE
Collaborative Data Analysis and Discovery for Cyber Security

BubbleNet: A Cyber Security Dashboard for Visualizing Patterns

June 6, 2016
  |
Conference Paper
Author:
Sean P. McKenna
…
Published in:
Proceeding of 2016 Eurographics Conference on Visualization (EuroVis)
Topic:
visualization
R&D area:
R&D group:

Summary

The field of cyber security is faced with ever-expanding amounts of data and a constant barrage of cyber attacks. Within this space, we have designed BubbleNet as a cyber security dashboard to help network analysts identify and summarize patterns within the data.
READ LESS

Summary

The field of cyber security is faced with ever-expanding amounts of data and a constant barrage of cyber attacks. Within this space, we have designed BubbleNet as a cyber security dashboard to help network analysts identify and summarize patterns within the data.

READ MORE
BubbleNet: A Cyber Security Dashboard for Visualizing Patterns

Cloudbreak: answering the challenges of cyber command and control

January 1, 2016
  |
Journal Article
Author:
Diane P. Staheli
…
Published in:
Lincoln Laboratory Journal, Vol. 22, No. 1, 2016, pp. 60-73.
Topic:
visualization
R&D area:
R&D group:

Summary

Lincoln Laboratory's flexible, user-centered framework for the development of command-and-control systems allows the rapid prototyping of new system capabilities. This methodology, Cloudbreak, effectively supports the insertion of new capabilities into existing systems and fosters user acceptance of new tools.
READ LESS

Summary

Lincoln Laboratory's flexible, user-centered framework for the development of command-and-control systems allows the rapid prototyping of new system capabilities. This methodology, Cloudbreak, effectively supports the insertion of new capabilities into existing systems and fosters user acceptance of new tools.

READ MORE
Cloudbreak: answering the challenges of cyber command and control

Unlocking user-centered design methods for building cyber security visualizations(3.93 MB)

October 26, 2015
  |
Conference Paper
Author:
Sean P. McKenna
…
Published in:
Proceedings of 2015 IEEE Symposium on Visualization for Cyber Security (VizSec)
Topic:
visualization
R&D area:
R&D group:

Summary

User-centered design can aid visualization designers to build better, more practical tools that meet the needs of cyber security users. In this paper, we discuss three design methods and illustrate how each method informed two real-world cyber security visualization projects which resulted in successful deployments to users.
READ LESS

Summary

User-centered design can aid visualization designers to build better, more practical tools that meet the needs of cyber security users. In this paper, we discuss three design methods and illustrate how each method informed two real-world cyber security visualization projects which resulted in successful deployments to users.

READ MORE
Unlocking user-centered design methods for building cyber security visualizations

VAST Challenge 2015: Mayhem at Dinofun World(757.94 KB)

October 25, 2015
  |
Conference Paper
Author:
Mark Whiting
…
Published in:
Proceedings of 2015 IEEE Conference on Visual Analytics Science and Technology (VAST)
Topic:
visualization
R&D area:
R&D group:

Summary

A fictitious amusement park and a larger-than-life hometown football hero provided participants in the VAST Challenge 2015 with an engaging yet complex storyline and setting in which to analyze movement and communication patterns.
READ LESS

Summary

A fictitious amusement park and a larger-than-life hometown football hero provided participants in the VAST Challenge 2015 with an engaging yet complex storyline and setting in which to analyze movement and communication patterns.

READ MORE
VAST Challenge 2015: Mayhem at Dinofun World

Visualization evaluation for cyber security: trends and future directions(1.22 MB)

November 10, 2014
  |
Conference Paper
Author:
Diane P. Staheli
…
Published in:
Proceedings of the Eleventh Workshop on Visualization for Cyber Security
Topic:
visualization
R&D area:
R&D group:

Summary

The Visualization for Cyber Security research community (VizSec) addresses longstanding challenges in cyber security by adapting and evaluating information visualization techniques with application to the cyber security domain. In this paper, we survey and categorize the evaluation metrics, components, and techniques that have been utilized in the past decade of VizSec research literature.
READ LESS

Summary

The Visualization for Cyber Security research community (VizSec) addresses longstanding challenges in cyber security by adapting and evaluating information visualization techniques with application to the cyber security domain. In this paper, we survey and categorize the evaluation metrics, components, and techniques that have been utilized in the past decade of...

READ MORE
Visualization evaluation for cyber security: trends and future directions
1-10 of 10