Search

In this work, we establish theoretical and practical connections between vertex indexing for sparse graph/network compression and matrix ordering for sparse matrix-vector multiplication and variable elimination. We present a fundamental analysis of adjacency access locality in vertex ordering from the perspective of graph composition of, or decomposition into, elementary compact graphs. We introduce an algebraic indexing approach that maintains the advantageous features of existing methods, mitigates their shortcomings, and adapts to the degree distribution. The new method demonstrates superior and versatile performance in graph compression across diverse types of graphs. It also renders proportional improvement in the efficiency of matrix-vector multiplications for subspace iterations in response to random walk queries on a large network., Comment: 7 pages, 5 figures, 1 table

This paper presents a comprehensive analysis of the generalized spectral structure of the modularity matrix $B$, which is introduced by Newman as the kernel matrix for the quadratic-form expression of the modularity function $Q$ used for community detection. The analysis is then seamlessly extended to the resolution-parametrized modularity matrix $B(\gamma)$, where $\gamma$ denotes the resolution parameter. The modularity spectral analysis provides fresh and profound insights into the $\gamma$-dynamics within the framework of modularity maximization for community detection. It provides the first algebraic explanation of the resolution limit at any specific $\gamma$ value. Among the significant findings and implications, the analysis reveals that (1) the maxima of the quadratic function with $B(\gamma)$ as the kernel matrix always reside in the Fiedler space of the normalized graph Laplacian $L$ or the null space of $L$, or their combination, and (2) the Fiedler value of the graph Laplacian $L$ marks the critical $\gamma$ value in the transition of candidate community configuration states between graph division and aggregation. Additionally, this paper introduces and identifies the Fiedler pseudo-set (FPS) as the de facto critical region for the state transition. This work is expected to have an immediate and long-term impact on improvements in algorithms for modularity maximization and on model transformations., Comment: 11 pages, 3 figures, 1 table

We associate all small subgraph counting problems with a systematic graph encoding/representation system which makes a coherent use of graphlet structures. The system can serve as a unified foundation for studying and connecting many important graph problems in theory and practice. We describe topological relations among graphlets (graph elements) in rigorous mathematics language and from the perspective of graph encoding. We uncover, characterize and utilize algebraic and numerical relations in graphlet counts/frequencies. We present a novel algorithm for efficiently counting small subgraphs as a practical product of our theoretical findings., Comment: 25 pages, 8 figures, 2 tables

Aims: Our Gulf War Illness (GWI) study conducts combinatorial screening of many interactive neural and humoral biomarkers in order to establish predictive, diagnostic, and therapeutic targets. We encounter obstacles at every stage of the biomarker discovery process, from sample acquisition, bio-marker extraction to multi-aspect, multi-way interaction analysis, due to the study complexity and lack of support for complex data problem solutions. We introduce a novel data platform, named ROSALIND, to overcome the challenges, foster healthy and vital collaborations and advance scientific inquiries. Main methods: ROSALIND is a researcher-centered, study-specific data platform. It provides vital support of individual creativity and effort in collaborative research. We follow the principles etched in the platform name - ROSALIND stands for resource organisms with self-governed accessibility, linkability, integrability, neutrality, and dependability. We translate, encode and implement the principles in the platform with novel use of advanced concepts and techniques to ensure and protect data integrity and research integrity. From a researcher's vantage point, ROSALIND embodies nuance utilities and advanced functionalities in one system, beyond conventional storage, archive and data management. Key findings: The deployment of ROSALIND in our GWI study in recent 12 months has accelerated the pace of data experiment and analysis, removed numerous error sources, and increased research quality and productivity. Significance: ROSALIND seems the first to address data integrity and research integrity in tandem with digital measures and means. It also promises a new type of distributed research networks with individualized data platforms connected in various self-organized collaboration configurations., Comment: Authorship disagreement

We introduce a new method for temporal pattern analysis of scientific collaboration networks. We investigate in particular virus research activities through five epidemic or pandemic outbreaks in the recent two decades and in the ongoing pandemic with COVID-19. Our method embodies two innovative components. The first is a simple model of temporal collaboration networks with time segmented in publication time and convolved in citation history, to effectively capture and accommodate collaboration activities at mixed time scales. The second component is the novel use of graphlets to encode topological structures and to detect change and persistence in collaboration activities over time. We discover in particular two unique and universal roles of bi-fork graphlet in (1) identifying bridges among triangle clusters and (2) quantifying grassroots as the backbone of every collaboration network. We present a number of intriguing patterns and findings about the virus-research activities., Comment: To appear in the Proceedings of High Performance Extreme Computing (HPEC) 2020

Objective: This study aims to develop and validate a novel framework, iPhantom, for automated creation of patient-specific phantoms or digital-twins (DT) using patient medical images. The framework is applied to assess radiation dose to radiosensitive organs in CT imaging of individual patients. Method: From patient CT images, iPhantom segments selected anchor organs (e.g. liver, bones, pancreas) using a learning-based model developed for multi-organ CT segmentation. Organs challenging to segment (e.g. intestines) are incorporated from a matched phantom template, using a diffeomorphic registration model developed for multi-organ phantom-voxels. The resulting full-patient phantoms are used to assess organ doses during routine CT exams. Result: iPhantom was validated on both the XCAT (n=50) and an independent clinical (n=10) dataset with similar accuracy. iPhantom precisely predicted all organ locations with good accuracy of Dice Similarity Coefficients (DSC) >0.6 for anchor organs and DSC of 0.3-0.9 for all other organs. iPhantom showed less than 10% dose errors for the majority of organs, which was notably superior to the state-of-the-art baseline method (20-35% dose errors). Conclusion: iPhantom enables automated and accurate creation of patient-specific phantoms and, for the first time, provides sufficient and automated patient-specific dose estimates for CT dosimetry. Significance: The new framework brings the creation and application of CHPs to the level of individual CHPs through automation, achieving a wider and precise organ localization, paving the way for clinical monitoring, and personalized optimization, and large-scale research., Comment: Main text: 11 pages, 8 figures; Supplement material: 7 pages, 5 figures, 7 tables

We introduce the computational problem of graphlet transform of a sparse large graph. Graphlets are fundamental topology elements of all graphs/networks. They can be used as coding elements to encode graph-topological information at multiple granularity levels for classifying vertices on the same graph/network as well as for making differentiation or connection across different networks. Network/graph analysis using graphlets has growing applications. We recognize the universality and increased encoding capacity in using multiple graphlets, we address the arising computational complexity issues, and we present a fast method for exact graphlet transform. The fast graphlet transform establishes a few remarkable records at once in high computational efficiency, low memory consumption, and ready translation to high-performance program and implementation. It is intended to enable and advance network/graph analysis with graphlets, and to introduce the relatively new analysis apparatus to graph theory, high-performance graph computation, and broader applications., Comment: To appear in the Proceedings of High Performance Extreme Computing (HPEC) 2020

We introduce a nonlinear method for directly embedding large, sparse, stochastic graphs into low-dimensional spaces, without requiring vertex features to reside in, or be transformed into, a metric space. Graph data and models are prevalent in real-world applications. Direct graph embedding is fundamental to many graph analysis tasks, in addition to graph visualization. We name the novel approach SG-t-SNE, as it is inspired by and builds upon the core principle of t-SNE, a widely used method for nonlinear dimensionality reduction and data visualization. We also introduce t-SNE-$\Pi$, a high-performance software for 2D, 3D embedding of large sparse graphs on personal computers with superior efficiency. It empowers SG-t-SNE with modern computing techniques for exploiting in tandem both matrix structures and memory architectures. We present elucidating embedding results on one synthetic graph and four real-world networks.

This work extends the personalized PageRank model invented by Brin and Page to a family of PageRank models with various damping schemes. The goal with increased model variety is to capture or recognize a larger number of types of network activities, phenomena and propagation patterns. The response in PageRank distribution to variation in damping mechanism is then characterized analytically, and further estimated quantitatively on 6 large real-world link graphs. The study leads to new observation and empirical findings. It is found that the difference in the pattern of PageRank vector responding to parameter variation by each model among the 6 graphs is relatively smaller than the difference among 3 particular models used in the study on each of the graphs. This suggests the utility of model variety for differentiating network activities and propagation patterns. The quantitative analysis of the damping mechanisms over multiple damping models and parameters is facilitated by a highly efficient algorithm, which calculates all PageRank vectors at once via a commonly shared, spectrally invariant subspace. The spectral space is found to be of low dimension for each of the real-world graphs.

Calculation of near-neighbor interactions among high dimensional, irregularly distributed data points is a fundamental task to many graph-based or kernel-based machine learning algorithms and applications. Such calculations, involving large, sparse interaction matrices, expose the limitation of conventional data-and-computation reordering techniques for improving space and time locality on modern computer memory hierarchies. We introduce a novel method for obtaining a matrix permutation that renders a desirable sparsity profile. The method is distinguished by the guiding principle to obtain a profile that is block-sparse with dense blocks. Our profile model and measure capture the essential properties affecting space and time locality, and permit variation in sparsity profile without imposing a restriction to a fixed pattern. The second distinction lies in an efficient algorithm for obtaining a desirable profile, via exploring and exploiting multi-scale cluster structure hidden in but intrinsic to the data. The algorithm accomplishes its task with key components for lower-dimensional embedding with data-specific principal feature axes, hierarchical data clustering, multi-level matrix compression storage, and multi-level interaction computations. We provide experimental results from case studies with two important data analysis algorithms. The resulting performance is remarkably comparable to the BLAS performance for the best-case interaction governed by a regularly banded matrix with the same sparsity.

Purpose: Often, the inverse deformation vector field (DVF) is needed together with the corresponding forward DVF in 4D reconstruction and dose calculation, adaptive radiation therapy, and simultaneous deformable registration. This study aims at improving both accuracy and efficiency of iterative algorithms for DVF inversion, and advancing our understanding of divergence and latency conditions. Method: We introduce a framework of fixed-point iteration algorithms with active feedback control for DVF inversion. Based on rigorous convergence analysis, we design control mechanisms for modulating the inverse consistency (IC) residual of the current iterate, to be used as feedback into the next iterate. The control is designed adaptively to the input DVF with the objective to enlarge the convergence area and expedite convergence. Three particular settings of feedback control are introduced: constant value over the domain throughout the iteration; alternating values between iteration steps; and spatially variant values. We also introduce three spectral measures of the displacement Jacobian for characterizing a DVF. These measures reveal the critical role of what we term the non-translational displacement component (NTDC) of the DVF. We carry out inversion experiments with an analytical DVF pair, and with DVFs associated with thoracic CT images of 6 patients at end of expiration and end of inspiration. Results: NTDC-adaptive iterations are shown to attain a larger convergence region at a faster pace compared to previous non-adaptive DVF inversion iteration algorithms. By our numerical experiments, alternating control yields smaller IC residuals and inversion errors than constant control. Spatially variant control renders smaller residuals and errors by at least an order of magnitude, compared to other schemes, in no more than 10 steps. Inversion results also show remarkable quantitative agreement with analysis-based predictions. Conclusion: Our analysis captures properties of DVF data associated with clinical CT images, and provides new understanding of iterative DVF inversion algorithms with a simple residual feedback control. Adaptive control is necessary and highly effective in the presence of non-small NTDCs. The adaptive iterations or the spectral measures, or both, may potentially be incorporated into deformable image registration methods.

We present a scheme to automatically set the precision of floating point variables in an application. We design a framework that profiles applications to measure undesirable numerical behavior at the floating point operation level. We use this framework to perform mixed precision analysis to heuristically set the precision of all variables in an application based on their numerical profiles. We experimentally evaluate the mixed precision analysis to show that it can generate a range of results with different accuracy and performance characteristics.

We introduce the use of DCTNet, an efficient approximation and alternative to PCANet, for acoustic signal classification. In PCANet, the eigenfunctions of the local sample covariance matrix (PCA) are used as filterbanks for convolution and feature extraction. When the eigenfunctions are well approximated by the Discrete Cosine Transform (DCT) functions, each layer of of PCANet and DCTNet is essentially a time-frequency representation. We relate DCTNet to spectral feature representation methods, such as the the short time Fourier transform (STFT), spectrogram and linear frequency spectral coefficients (LFSC). Experimental results on whale vocalization data show that DCTNet improves classification rate, demonstrating DCTNet's applicability to signal processing problems such as underwater acoustics., Comment: 22 figures

We present a new and effective approach for Hyperspectral Image (HSI) classification and clutter detection, overcoming a few long-standing challenges presented by HSI data characteristics. Residing in a high-dimensional spectral attribute space, HSI data samples are known to be strongly correlated in their spectral signatures, exhibit nonlinear structure due to several physical laws, and contain uncertainty and noise from multiple sources. In the presented approach, we generate an adaptive, structurally enriched representation environment, and employ the locally linear embedding (LLE) in it. There are two structure layers external to LLE. One is feature space embedding: the HSI data attributes are embedded into a discriminatory feature space where spatio-spectral coherence and distinctive structures are distilled and exploited to mitigate various difficulties encountered in the native hyperspectral attribute space. The other structure layer encloses the ranges of algorithmic parameters for LLE and feature embedding, and supports a multiplexing and integrating scheme for contending with multi-source uncertainty. Experiments on two commonly used HSI datasets with a small number of learning samples have rendered remarkably high-accuracy classification results, as well as distinctive maps of detected clutter regions., Comment: 13 pages, 6 figures (30 images), submitted to International Conference on Computer Vision (ICCV) 2015

In this work, we provide energy-efficient architectural support for floating point accuracy. Our goal is to provide accuracy that is far greater than that provided by the processor's hardware floating point unit (FPU). Specifically, for each floating point addition performed, we "recycle" that operation's error: the difference between the finite-precision result produced by the hardware and the result that would have been produced by an infinite-precision FPU. We make this error architecturally visible such that it can be used, if desired, by software. Experimental results on physical hardware show that software that exploits architecturally recycled error bits can achieve accuracy comparable to a 2B-bit FPU with performance and energy that are comparable to a B-bit FPU.