More Like this

1. BC tree-based spectral sampling for big complex network visualization

   https://doi.org/10.1007/s41109-021-00405-3  

   Hu, Jingming; Chu, Tuan Tran; Hong, Seok-Hee; Chen, Jialu; Meidiana, Amyra; Torkel, Marnijati; Eades, Peter; Ma, Kwan-Liu (December 2021, Applied Network Science)

   Abstract Graph sampling methods have been used to reduce the size and complexity of big complex networks for graph mining and visualization. However, existing graph sampling methods often fail to preserve the connectivity and important structures of the original graph. This paper introduces a new divide and conquer approach to spectral graph sampling based on graph connectivity, called the BC Tree (i.e., decomposition of a connected graph into biconnected components) and spectral sparsification. Specifically, we present two methods, spectral vertex sampling $$BC\_SV$$ B C _ S V and spectral edge sampling $$BC\_SS$$ B C _ S S by computing effective resistance values of vertices and edges for each connected component. Furthermore, we present $$DBC\_SS$$ D B C _ S S and $$DBC\_GD$$ D B C _ G D , graph connectivity-based distributed algorithms for spectral sparsification and graph drawing respectively, aiming to further improve the runtime efficiency of spectral sparsification and graph drawing by integrating connectivity-based graph decomposition and distributed computing. Experimental results demonstrate that $$BC\_SV$$ B C _ S V and $$BC\_SS$$ B C _ S S are significantly faster than previous spectral graph sampling methods while preserving the same sampling quality. $$DBC\_SS$$ D B C _ S S and $$DBC\_GD$$ D B C _ G D obtain further significant runtime improvement over sequential approaches, and $$DBC\_GD$$ D B C _ G D further achieves significant improvements in quality metrics over sequential graph drawing layouts. 

   more » « less
2. An Information-Theoretic Framework for Evaluating Edge Bundling Visualization

   https://doi.org/10.3390/e20090625  

   Wu, Jieting; Zhu, Feiyu; Liu, Xin; Yu, Hongfeng (September 2018, Entropy)

   Edge bundling is a promising graph visualization approach to simplifying the visual result of a graph drawing. Plenty of edge bundling methods have been developed to generate diverse graph layouts. However, it is difficult to defend an edge bundling method with its resulting layout against other edge bundling methods as a clear theoretic evaluation framework is absent in the literature. In this paper, we propose an information-theoretic framework to evaluate the visual results of edge bundling techniques. We first illustrate the advantage of edge bundling visualizations for large graphs, and pinpoint the ambiguity resulting from drawing results. Second, we define and quantify the amount of information delivered by edge bundling visualization from the underlying network using information theory. Third, we propose a new algorithm to evaluate the resulting layouts of edge bundling using the amount of the mutual information between a raw network dataset and its edge bundling visualization. Comparison examples based on the proposed framework between different edge bundling techniques are presented. 

   more » « less
3. Distance-Weighted Graph Neural Networks on FPGAs for Real-Time Particle Reconstruction in High Energy Physics

   https://doi.org/10.3389/fdata.2020.598927  

   Iiyama, Yutaro; Cerminara, Gianluca; Gupta, Abhijay; Kieseler, Jan; Loncar, Vladimir; Pierini, Maurizio; Qasim, Shah Rukh; Rieger, Marcel; Summers, Sioni; Van Onsem, Gerrit; et al (January 2021, Frontiers in Big Data)

   null (Ed.)

   Graph neural networks have been shown to achieve excellent performance for several crucial tasks in particle physics, such as charged particle tracking, jet tagging, and clustering. An important domain for the application of these networks is the FGPA-based first layer of real-time data filtering at the CERN Large Hadron Collider, which has strict latency and resource constraints. We discuss how to design distance-weighted graph networks that can be executed with a latency of less than one μs on an FPGA. To do so, we consider a representative task associated to particle reconstruction and identification in a next-generation calorimeter operating at a particle collider. We use a graph network architecture developed for such purposes, and apply additional simplifications to match the computing constraints of Level-1 trigger systems, including weight quantization. Using the hls4ml library, we convert the compressed models into firmware to be implemented on an FPGA. Performance of the synthesized models is presented both in terms of inference accuracy and resource usage. 

   more » « less
4. DeepGD: A Deep Learning Framework for Graph Drawing Using GNN

   Xiaoqi Wang, Kevin Yen (September 2021, IEEE computer graphics and applications)

   Abstract—In the past decades, many graph drawing techniques have been proposed for generating aesthetically pleasing graph layouts. However, it remains a challenging task since different layout methods tend to highlight different characteristics of the graphs. Recently, studies on deep learning based graph drawing algorithm have emerged but they are often not generalizable to arbitrary graphs without re-training. In this paper, we propose a Convolutional Graph Neural Network based deep learning framework, DeepGD, which can draw arbitrary graphs once trained. It attempts to generate layouts by compromising among multiple pre-specified aesthetics considering a good graph layout usually complies with multiple aesthetics simultaneously. In order to balance the trade-off, we propose two adaptive training strategies which adjust the weight factor of each aesthetic dynamically during training. The quantitative and qualitative assessment of DeepGD demonstrates that it is capable of drawing arbitrary graphs effectively, while being flexible at accommodating different aesthetic criteria. 

   more » « less
5. Visualizing a Moving Target: A Design Study on Task Parallel Programs in the Presence of Evolving Data and Concerns

   https://doi.org/10.1109/TVCG.2019.2934285  

   Williams, Katy; Bigelow, Alex; Isaacs, Katherine E. (August 2019, IEEE Transactions on Visualization and Computer Graphics)

   Common pitfalls in visualization projects include lack of data availability and the domain users' needs and focus changing too rapidly for the design process to complete. While it is often prudent to avoid such projects, we argue it can be beneficial to engage them in some cases as the visualization process can help refine data collection, solving a “chicken and egg” problem of having the data and tools to analyze it. We found this to be the case in the domain of task parallel computing where such data and tooling is an open area of research. Despite these hurdles, we conducted a design study. Through a tightly-coupled iterative design process, we built Atria, a multi-view execution graph visualization to support performance analysis. Atria simplifies the initial representation of the execution graph by aggregating nodes as related to their line of code. We deployed Atria on multiple platforms, some requiring design alteration. We describe how we adapted the design study methodology to the “moving target” of both the data and the domain experts' concerns and how this movement kept both the visualization and programming project healthy. We reflect on our process and discuss what factors allow the project to be successful in the presence of changing data and user needs. 

   more » « less