-
Balanced Butterfly Counting in Bipartite-Network
Authors:
Apurba Das,
Aman Abidi,
Ajinkya Shingane,
Mekala Kiran
Abstract:
Bipartite graphs offer a powerful framework for modeling complex relationships between two distinct types of vertices, incorporating probabilistic, temporal, and rating-based information. While the research community has extensively explored various types of bipartite relationships, there has been a notable gap in studying Signed Bipartite Graphs, which capture liking / disliking interactions in r…
▽ More
Bipartite graphs offer a powerful framework for modeling complex relationships between two distinct types of vertices, incorporating probabilistic, temporal, and rating-based information. While the research community has extensively explored various types of bipartite relationships, there has been a notable gap in studying Signed Bipartite Graphs, which capture liking / disliking interactions in real-world networks such as customer-rating-product and senator-vote-bill. Balance butterflies, representing 2 x 2 bicliques, provide crucial insights into antagonistic groups, balance theory, and fraud detection by leveraging the signed information. However, such applications require counting balance butterflies which remains unexplored. In this paper, we propose a new problem: counting balance butterflies in a signed bipartite graph. To address this problem, we adopt state-of-the-art algorithms for butterfly counting, establishing a smart baseline that reduces the time complexity for solving our specific problem. We further introduce a novel bucket approach specifically designed to count balanced butterflies efficiently. We propose a parallelized version of the bucketing approach to enhance performance. Extensive experimental studies on nine real-world datasets demonstrate that our proposed bucket-based algorithm is up to 120x faster over the baseline, and the parallel implementation of the bucket-based algorithm is up to 45x faster over the single core execution. Moreover, a real-world case study showcases the practical application and relevance of counting balanced butterflies.
△ Less
Submitted 9 August, 2023;
originally announced August 2023.
-
Integrative Imaging Informatics for Cancer Research: Workflow Automation for Neuro-oncology (I3CR-WANO)
Authors:
Satrajit Chakrabarty,
Syed Amaan Abidi,
Mina Mousa,
Mahati Mokkarala,
Isabelle Hren,
Divya Yadav,
Matthew Kelsey,
Pamela LaMontagne,
John Wood,
Michael Adams,
Yuzhuo Su,
Sherry Thorpe,
Caroline Chung,
Aristeidis Sotiras,
Daniel S. Marcus
Abstract:
Efforts to utilize growing volumes of clinical imaging data to generate tumor evaluations continue to require significant manual data wrangling owing to the data heterogeneity. Here, we propose an artificial intelligence-based solution for the aggregation and processing of multisequence neuro-oncology MRI data to extract quantitative tumor measurements. Our end-to-end framework i) classifies MRI s…
▽ More
Efforts to utilize growing volumes of clinical imaging data to generate tumor evaluations continue to require significant manual data wrangling owing to the data heterogeneity. Here, we propose an artificial intelligence-based solution for the aggregation and processing of multisequence neuro-oncology MRI data to extract quantitative tumor measurements. Our end-to-end framework i) classifies MRI sequences using an ensemble classifier, ii) preprocesses the data in a reproducible manner, iii) delineates tumor tissue subtypes using convolutional neural networks, and iv) extracts diverse radiomic features. Moreover, it is robust to missing sequences and adopts an expert-in-the-loop approach, where the segmentation results may be manually refined by radiologists. Following the implementation of the framework in Docker containers, it was applied to two retrospective glioma datasets collected from the Washington University School of Medicine (WUSM; n = 384) and the M.D. Anderson Cancer Center (MDA; n = 30) comprising preoperative MRI scans from patients with pathologically confirmed gliomas. The scan-type classifier yielded an accuracy of over 99%, correctly identifying sequences from 380/384 and 30/30 sessions from the WUSM and MDA datasets, respectively. Segmentation performance was quantified using the Dice Similarity Coefficient between the predicted and expert-refined tumor masks. Mean Dice scores were 0.882 ($\pm$0.244) and 0.977 ($\pm$0.04) for whole tumor segmentation for WUSM and MDA, respectively. This streamlined framework automatically curated, processed, and segmented raw MRI data of patients with varying grades of gliomas, enabling the curation of large-scale neuro-oncology datasets and demonstrating a high potential for integration as an assistive tool in clinical practice.
△ Less
Submitted 6 October, 2022;
originally announced October 2022.
-
Automatic Feature Highlighting in Noisy RES Data With CycleGAN
Authors:
Nicholas Khami,
Omar Imtiaz,
Akif Abidi,
Akash Aedavelli,
Alan Goff,
Jesse R. Pisel,
Michael J. Pyrcz
Abstract:
Radio echo sounding (RES) is a common technique used in subsurface glacial imaging, which provides insight into the underlying rock and ice. However, systematic noise is introduced into the data during collection, complicating interpretation of the results. Researchers most often use a combination of manual interpretation and filtering techniques to denoise data; however, these processes are time…
▽ More
Radio echo sounding (RES) is a common technique used in subsurface glacial imaging, which provides insight into the underlying rock and ice. However, systematic noise is introduced into the data during collection, complicating interpretation of the results. Researchers most often use a combination of manual interpretation and filtering techniques to denoise data; however, these processes are time intensive and inconsistent. Fully Convolutional Networks have been proposed as an automated alternative to identify layer boundaries in radargrams. However, they require high-quality manually processed training data and struggle to interpolate data in noisy samples (Varshney et al. 2020).
Herein, the authors propose a GAN based model to interpolate layer boundaries through noise and highlight layers in two-dimensional glacial RES data. In real-world noisy images, filtering often results in loss of data such that interpolating layer boundaries is nearly impossible. Furthermore, traditional machine learning approaches are not suited to this task because of the lack of paired data, so we employ an unpaired image-to-image translation model. For this model, we create a synthetic dataset to represent the domain of images with clear, highlighted layers and use an existing real-world RES dataset as our noisy domain.
We implement a CycleGAN trained on these two domains to highlight layers in noisy images that can interpolate effectively without significant loss of structure or fidelity. Though the current implementation is not a perfect solution, the model clearly highlights layers in noisy data and allows researchers to determine layer size and position without mathematical filtering, manual processing, or ground-truth images for training. This is significant because clean images generated by our model enable subsurface researchers to determine glacial layer thickness more efficiently.
△ Less
Submitted 25 August, 2021;
originally announced August 2021.
-
Searching Personalized $k$-wing in Large and Dynamic Bipartite Graphs
Authors:
Aman Abidi,
Lu Chen,
Rui Zhou,
Chengfei Liu
Abstract:
There are extensive studies focusing on the application scenario that all the bipartite cohesive subgraphs need to be discovered in a bipartite graph. However, we observe that, for some applications, one is interested in finding bipartite cohesive subgraphs containing a specific vertex. In this paper, we study a new query dependent bipartite cohesive subgraph search problem based on $k$-wing model…
▽ More
There are extensive studies focusing on the application scenario that all the bipartite cohesive subgraphs need to be discovered in a bipartite graph. However, we observe that, for some applications, one is interested in finding bipartite cohesive subgraphs containing a specific vertex. In this paper, we study a new query dependent bipartite cohesive subgraph search problem based on $k$-wing model, named as the personalized $k$-wing search problem. We introduce a $k$-wing equivalence relationship to summarize the edges of a bipartite graph $G$ into groups. Therefore, all the edges of $G$ are segregated into different groups, i.e. $k$-wing equivalence class, forming an efficient and wing number conserving index called EquiWing. Further, we propose a more compact version of EquiWing, EquiWing-Comp, which is achieved by integrating our proposed $k$-butterfly loose approach and discovered hierarchy properties. These indices are used to expedite the personalized $k$-wing search with a non-repetitive access to $G$, which leads to linear algorithms for searching the personalized $k$-wing. Moreover, we conduct a thorough study on the maintenance of the proposed indices for evolving bipartite graphs. We discover novel properties that help us localize the scope of the maintenance at a low cost. By exploiting the discoveries, we propose novel algorithms for maintaining the two indices, which substantially reduces the cost of maintenance. We perform extensive experimental studies in real, large-scale graphs to validate the efficiency and effectiveness of EquiWing and EquiWing-Comp compared to the baseline.
△ Less
Submitted 4 January, 2021; v1 submitted 4 January, 2021;
originally announced January 2021.
-
Summary of Topological Study of Chaotic CBC Mode of Operation
Authors:
Abdessalem Abidi,
Samar Tawbi,
Christophe Guyeux,
Belgacem Bouallègue,
Mohsen Machhout
Abstract:
In cryptography, block ciphers are the most fundamental elements in many symmetric-key encryption systems. The Cipher Block Chaining, denoted CBC, presents one of the most famous mode of operation that uses a block cipher to provide confidentiality or authenticity. In this research work, we intend to summarize our results that have been detailed in our previous series of articles. The goal of this…
▽ More
In cryptography, block ciphers are the most fundamental elements in many symmetric-key encryption systems. The Cipher Block Chaining, denoted CBC, presents one of the most famous mode of operation that uses a block cipher to provide confidentiality or authenticity. In this research work, we intend to summarize our results that have been detailed in our previous series of articles. The goal of this series has been to obtain a complete topological study of the CBC block cipher mode of operation after proving his chaotic behavior according to the reputed definition of Devaney.
△ Less
Submitted 9 August, 2017;
originally announced August 2017.
-
Lyapunov Exponent Evaluation of the CBC Mode of Operation
Authors:
Abdessalem Abidi,
Christophe Guyeux,
Jacques Demerjian,
Belagacem Bouallègue,
Mohsen Machhout
Abstract:
The Cipher Block Chaining (CBC) mode of encryption was invented in 1976, and it is currently one of the most commonly used mode. In our previous research works, we have proven that the CBC mode of operation exhibits, under some conditions, a chaotic behavior. The dynamics of this mode has been deeply investigated later, both qualitatively and quantitatively, using the rigorous mathematical topolog…
▽ More
The Cipher Block Chaining (CBC) mode of encryption was invented in 1976, and it is currently one of the most commonly used mode. In our previous research works, we have proven that the CBC mode of operation exhibits, under some conditions, a chaotic behavior. The dynamics of this mode has been deeply investigated later, both qualitatively and quantitatively, using the rigorous mathematical topology field of research. In this article, which is an extension of our previous work, we intend to compute a new important quantitative property concerning our chaotic CBC mode of operation, which is the Lyapunov exponent.
△ Less
Submitted 25 June, 2017;
originally announced June 2017.
-
Proving chaotic behaviour of CBC mode of operation
Authors:
Abdessalem Abidi,
Qianxue Wang,
Belgacem Bouallegue,
Mohsen Machhout,
Christophe Guyeux
Abstract:
The cipher block chaining (CBC) block cipher mode of operation was invented by IBM (International Business Machine) in 1976. It presents a very popular way of encrypting which is used in various applications. In this paper, we have mathematically proven that, under some conditions, the CBC mode of operation can admit a chaotic behaviour according to Devaney. Some cases will be properly studied in…
▽ More
The cipher block chaining (CBC) block cipher mode of operation was invented by IBM (International Business Machine) in 1976. It presents a very popular way of encrypting which is used in various applications. In this paper, we have mathematically proven that, under some conditions, the CBC mode of operation can admit a chaotic behaviour according to Devaney. Some cases will be properly studied in order to put in evidence this idea.
△ Less
Submitted 20 August, 2016;
originally announced August 2016.
-
The dynamics of the CBC Mode of Operation
Authors:
Abdessalem Abidi,
Christophe Guyeux,
Bechara Al Bouna,
Belgacem Bouallègue,
Mohsen Machhout
Abstract:
In cryptography, the Cipher Block Chaining (CBC), one of the most commonly used mode in recent years, is a mode of operation that uses a block cipher to provide confidentiality or authenticity. In our previous research work, we have shown that this mode of operation exhibits, under some conditions, a chaotic behaviour. We have studied this behaviour by evaluating both its level of sensibility and…
▽ More
In cryptography, the Cipher Block Chaining (CBC), one of the most commonly used mode in recent years, is a mode of operation that uses a block cipher to provide confidentiality or authenticity. In our previous research work, we have shown that this mode of operation exhibits, under some conditions, a chaotic behaviour. We have studied this behaviour by evaluating both its level of sensibility and expansivity. In this paper, we intend to deepen the topological study of the CBC mode of operation and evaluate its property of topological mixing. Additionally, other quantitative evaluations are performed, and the level of topological entropy has been evaluated too.
△ Less
Submitted 10 May, 2016;
originally announced May 2016.
-
Quantitative Evaluation of Chaotic CBC Mode of Operation
Authors:
Abdessalem Abidi,
Qianxue Wang,
Belgacem Bouallègue,
Mohsen Machhout,
Christophe Gyeux
Abstract:
The cipher block chaining (CBC) block cipher mode of operation presents a very popular way of encrypting which is used in various applications. In previous research work, we have mathematically proven that, under some conditions, this mode of operation can admit a chaotic behavior according to Devaney. Proving that CBC mode is chaotic is only the beginning of the study of its security. The next st…
▽ More
The cipher block chaining (CBC) block cipher mode of operation presents a very popular way of encrypting which is used in various applications. In previous research work, we have mathematically proven that, under some conditions, this mode of operation can admit a chaotic behavior according to Devaney. Proving that CBC mode is chaotic is only the beginning of the study of its security. The next step, which is the purpose of this paper, is to develop the quantitative study of the chaotic CBC mode of operation by evaluating the level of sensibility and expansivity for this mode.
△ Less
Submitted 29 January, 2016;
originally announced January 2016.
