Showing 1–50 of 54 results for author: Mukherjee, D

Standard compliant video coding using low complexity, switchable neural wrappers

Authors: Yueyu Hu, Chenhao Zhang, Onur G. Guleryuz, Debargha Mukherjee, Yao Wang

Abstract: The proliferation of high resolution videos posts great storage and bandwidth pressure on cloud video services, driving the development of next-generation video codecs. Despite great progress made in neural video coding, existing approaches are still far from economical deployment considering the complexity and rate-distortion performance tradeoff. To clear the roadblocks for neural video coding,… ▽ More The proliferation of high resolution videos posts great storage and bandwidth pressure on cloud video services, driving the development of next-generation video codecs. Despite great progress made in neural video coding, existing approaches are still far from economical deployment considering the complexity and rate-distortion performance tradeoff. To clear the roadblocks for neural video coding, in this paper we propose a new framework featuring standard compatibility, high performance, and low decoding complexity. We employ a set of jointly optimized neural pre- and post-processors, wrapping a standard video codec, to encode videos at different resolutions. The rate-distorion optimal downsampling ratio is signaled to the decoder at the per-sequence level for each target rate. We design a low complexity neural post-processor architecture that can handle different upsampling ratios. The change of resolution exploits the spatial redundancy in high-resolution videos, while the neural wrapper further achieves rate-distortion performance improvement through end-to-end optimization with a codec proxy. Our light-weight post-processor architecture has a complexity of 516 MACs / pixel, and achieves 9.3% BD-Rate reduction over VVC on the UVG dataset, and 6.4% on AOM CTC Class A1. Our approach has the potential to further advance the performance of the latest video coding standards using neural processing with minimal added complexity. △ Less

Submitted 10 July, 2024; originally announced July 2024.

Comments: Accepted by IEEE ICIP 2024

On the estimation rate of Bayesian PINN for inverse problems

Authors: Yi Sun, Debarghya Mukherjee, Yves Atchade

Abstract: Solving partial differential equations (PDEs) and their inverse problems using Physics-informed neural networks (PINNs) is a rapidly growing approach in the physics and machine learning community. Although several architectures exist for PINNs that work remarkably in practice, our theoretical understanding of their performances is somewhat limited. In this work, we study the behavior of a Bayesian… ▽ More Solving partial differential equations (PDEs) and their inverse problems using Physics-informed neural networks (PINNs) is a rapidly growing approach in the physics and machine learning community. Although several architectures exist for PINNs that work remarkably in practice, our theoretical understanding of their performances is somewhat limited. In this work, we study the behavior of a Bayesian PINN estimator of the solution of a PDE from $n$ independent noisy measurement of the solution. We focus on a class of equations that are linear in their parameters (with unknown coefficients $θ_\star$). We show that when the partial differential equation admits a classical solution (say $u_\star$), differentiable to order $β$, the mean square error of the Bayesian posterior mean is at least of order $n^{-2β/(2β+ d)}$. Furthermore, we establish a convergence rate of the linear coefficients of $θ_\star$ depending on the order of the underlying differential operator. Last but not least, our theoretical results are validated through extensive simulations. △ Less

Submitted 20 June, 2024; originally announced June 2024.

Comments: 35 Pages, 3 figures, and 2 tables

Transfer Learning Under High-Dimensional Graph Convolutional Regression Model for Node Classification

Authors: Jiachen Chen, Danyang Huang, Liyuan Wang, Kathryn L. Lunetta, Debarghya Mukherjee, Huimin Cheng

Abstract: Node classification is a fundamental task, but obtaining node classification labels can be challenging and expensive in many real-world scenarios. Transfer learning has emerged as a promising solution to address this challenge by leveraging knowledge from source domains to enhance learning in a target domain. Existing transfer learning methods for node classification primarily focus on integrating… ▽ More Node classification is a fundamental task, but obtaining node classification labels can be challenging and expensive in many real-world scenarios. Transfer learning has emerged as a promising solution to address this challenge by leveraging knowledge from source domains to enhance learning in a target domain. Existing transfer learning methods for node classification primarily focus on integrating Graph Convolutional Networks (GCNs) with various transfer learning techniques. While these approaches have shown promising results, they often suffer from a lack of theoretical guarantees, restrictive conditions, and high sensitivity to hyperparameter choices. To overcome these limitations, we propose a Graph Convolutional Multinomial Logistic Regression (GCR) model and a transfer learning method based on the GCR model, called Trans-GCR. We provide theoretical guarantees of the estimate obtained under GCR model in high-dimensional settings. Moreover, Trans-GCR demonstrates superior empirical performance, has a low computational cost, and requires fewer hyperparameters than existing methods. △ Less

Submitted 26 May, 2024; originally announced May 2024.

DPHGNN: A Dual Perspective Hypergraph Neural Networks

Authors: Siddhant Saxena, Shounak Ghatak, Raghu Kolla, Debashis Mukherjee, Tanmoy Chakraborty

Abstract: Message passing on hypergraphs has been a standard framework for learning higher-order correlations between hypernodes. Recently-proposed hypergraph neural networks (HGNNs) can be categorized into spatial and spectral methods based on their design choices. In this work, we analyze the impact of change in hypergraph topology on the suboptimal performance of HGNNs and propose DPHGNN, a novel dual-pe… ▽ More Message passing on hypergraphs has been a standard framework for learning higher-order correlations between hypernodes. Recently-proposed hypergraph neural networks (HGNNs) can be categorized into spatial and spectral methods based on their design choices. In this work, we analyze the impact of change in hypergraph topology on the suboptimal performance of HGNNs and propose DPHGNN, a novel dual-perspective HGNN that introduces equivariant operator learning to capture lower-order semantics by inducing topology-aware spatial and spectral inductive biases. DPHGNN employs a unified framework to dynamically fuse lower-order explicit feature representations from the underlying graph into the super-imposed hypergraph structure. We benchmark DPHGNN over eight benchmark hypergraph datasets for the semi-supervised hypernode classification task and obtain superior performance compared to seven state-of-the-art baselines. We also provide a theoretical framework and a synthetic hypergraph isomorphism test to express the power of spatial HGNNs and quantify the expressivity of DPHGNN beyond the Generalized Weisfeiler Leman (1-GWL) test. Finally, DPHGNN was deployed by our partner e-commerce company for the Return-to-Origin (RTO) prediction task, which shows ~7% higher macro F1-Score than the best baseline. △ Less

Submitted 26 May, 2024; originally announced May 2024.

Comments: Accepted in SIGKDD'24 -- Research Track

Optimal Aggregation of Prediction Intervals under Unsupervised Domain Shift

Authors: Jiawei Ge, Debarghya Mukherjee, Jianqing Fan

Abstract: As machine learning models are increasingly deployed in dynamic environments, it becomes paramount to assess and quantify uncertainties associated with distribution shifts. A distribution shift occurs when the underlying data-generating process changes, leading to a deviation in the model's performance. The prediction interval, which captures the range of likely outcomes for a given prediction, se… ▽ More As machine learning models are increasingly deployed in dynamic environments, it becomes paramount to assess and quantify uncertainties associated with distribution shifts. A distribution shift occurs when the underlying data-generating process changes, leading to a deviation in the model's performance. The prediction interval, which captures the range of likely outcomes for a given prediction, serves as a crucial tool for characterizing uncertainties induced by their underlying distribution. In this paper, we propose methodologies for aggregating prediction intervals to obtain one with minimal width and adequate coverage on the target domain under unsupervised domain shift, under which we have labeled samples from a related source domain and unlabeled covariates from the target domain. Our analysis encompasses scenarios where the source and the target domain are related via i) a bounded density ratio, and ii) a measure-preserving transformation. Our proposed methodologies are computationally efficient and easy to implement. Beyond illustrating the performance of our method through a real-world dataset, we also delve into the theoretical details. This includes establishing rigorous theoretical guarantees, coupled with finite sample bounds, regarding the coverage and width of our prediction intervals. Our approach excels in practical applications and is underpinned by a solid theoretical framework, ensuring its reliability and effectiveness across diverse contexts. △ Less

Submitted 16 May, 2024; originally announced May 2024.

eScope: A Fine-Grained Power Prediction Mechanism for Mobile Applications

Authors: Dipayan Mukherjee, Atul Sandur, Kirill Mechitov, Pratik Lahiri, Gul Agha

Abstract: Managing the limited energy on mobile platforms executing long-running, resource intensive streaming applications requires adapting an application's operators in response to their power consumption. For example, the frame refresh rate may be reduced if the rendering operation is consuming too much power. Currently, predicting an application's power consumption requires (1) building a device-specif… ▽ More Managing the limited energy on mobile platforms executing long-running, resource intensive streaming applications requires adapting an application's operators in response to their power consumption. For example, the frame refresh rate may be reduced if the rendering operation is consuming too much power. Currently, predicting an application's power consumption requires (1) building a device-specific power model for each hardware component, and (2) analyzing the application's code. This approach can be complicated and error-prone given the complexity of an application's logic and the hardware platforms with heterogeneous components that it may execute on. We propose eScope, an alternative method to directly estimate power consumption by each operator in an application. Specifically, eScope correlates an application's execution traces with its device-level energy draw. We implement eScope as a tool for Android platforms and evaluate it using workloads on several synthetic applications as well as two video stream analytics applications. Our evaluation suggests that eScope predicts an application's power use with 97% or better accuracy while incurring a compute time overhead of less than 3%. △ Less

Submitted 5 April, 2024; originally announced May 2024.

ACM Class: C.4

VISION: Toward a Standardized Process for Radiology Image Management at the National Level

Authors: Kathryn Knight, Ioana Danciu, Olga Ovchinnikova, Jacob Hinkle, Mayanka Chandra Shekar, Debangshu Mukherjee, Eileen McAllister, Caitlin Rizy, Kelly Cho, Amy C. Justice, Joseph Erdos, Peter Kuzmak, Lauren Costa, Yuk-Lam Ho, Reddy Madipadga, Suzanne Tamang, Ian Goethert

Abstract: The compilation and analysis of radiological images poses numerous challenges for researchers. The sheer volume of data as well as the computational needs of algorithms capable of operating on images are extensive. Additionally, the assembly of these images alone is difficult, as these exams may differ widely in terms of clinical context, structured annotation available for model training, modalit… ▽ More The compilation and analysis of radiological images poses numerous challenges for researchers. The sheer volume of data as well as the computational needs of algorithms capable of operating on images are extensive. Additionally, the assembly of these images alone is difficult, as these exams may differ widely in terms of clinical context, structured annotation available for model training, modality, and patient identifiers. In this paper, we describe our experiences and challenges in establishing a trusted collection of radiology images linked to the United States Department of Veterans Affairs (VA) electronic health record database. We also discuss implications in making this repository research-ready for medical investigators. Key insights include uncovering the specific procedures required for transferring images from a clinical to a research-ready environment, as well as roadblocks and bottlenecks in this process that may hinder future efforts at automation. △ Less

Submitted 29 April, 2024; originally announced April 2024.

Consensus-driven Deviated Pursuit for Guaranteed Simultaneous Interception of Moving Targets

Authors: Abhinav Sinha, Dwaipayan Mukherjee, Shashi Ranjan Kumar

Abstract: This work proposes a cooperative strategy that employs deviated pursuit guidance to simultaneously intercept a moving (but not manoeuvring) target. As opposed to many existing cooperative guidance strategies which use estimates of time-to-go, based on proportional-navigation guidance, the proposed strategy uses an exact expression for time-to-go to ensure simultaneous interception. The guidance de… ▽ More This work proposes a cooperative strategy that employs deviated pursuit guidance to simultaneously intercept a moving (but not manoeuvring) target. As opposed to many existing cooperative guidance strategies which use estimates of time-to-go, based on proportional-navigation guidance, the proposed strategy uses an exact expression for time-to-go to ensure simultaneous interception. The guidance design considers nonlinear engagement kinematics, allowing the proposed strategy to remain effective over a large operating regime. Unlike existing strategies on simultaneous interception that achieve interception at the average value of their initial time-to-go estimates, this work provides flexibility in the choice of impact time. By judiciously choosing the edge weights of the communication network, a weighted consensus in time-to-go can be achieved. It has been shown that by allowing an edge weight to be negative, consensus in time-to-go can even be achieved for an impact time that lies outside the convex hull of the set of initial time-to-go values of the individual interceptors. The bounds on such negative weights have been analysed for some special graphs, using Nyquist criterion. Simulations are provided to vindicate the efficacy of the proposed strategy. △ Less

Submitted 8 February, 2024; originally announced February 2024.

Significance of Anatomical Constraints in Virtual Try-On

Authors: Debapriya Roy, Sanchayan Santra, Diganta Mukherjee, Bhabatosh Chanda

Abstract: The system of Virtual Try-ON (VTON) allows a user to try a product virtually. In general, a VTON system takes a clothing source and a person's image to predict the try-on output of the person in the given clothing. Although existing methods perform well for simple poses, in case of bent or crossed arms posture or when there is a significant difference between the alignment of the source clothing a… ▽ More The system of Virtual Try-ON (VTON) allows a user to try a product virtually. In general, a VTON system takes a clothing source and a person's image to predict the try-on output of the person in the given clothing. Although existing methods perform well for simple poses, in case of bent or crossed arms posture or when there is a significant difference between the alignment of the source clothing and the pose of the target person, these methods fail by generating inaccurate clothing deformations. In the VTON methods that employ Thin Plate Spline (TPS) based clothing transformations, this mainly occurs for two reasons - (1)~the second-order smoothness constraint of TPS that restricts the bending of the object plane. (2)~Overlaps among different clothing parts (e.g., sleeves and torso) can not be modeled by a single TPS transformation, as it assumes the clothing as a single planar object; therefore, disregards the independence of movement of different clothing parts. To this end, we make two major contributions. Concerning the bending limitations of TPS, we propose a human AnaTomy-Aware Geometric (ATAG) transformation. Regarding the overlap issue, we propose a part-based warping approach that divides the clothing into independently warpable parts to warp them separately and later combine them. Extensive analysis shows the efficacy of this approach. △ Less

Submitted 4 January, 2024; originally announced January 2024.

Comments: arXiv admin note: substantial text overlap with arXiv:2208.08076

Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization

Authors: Neelkamal Bhuyan, Debankur Mukherjee, Adam Wierman

Abstract: We study the smoothed online quadratic optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t$ in response to a quadratic hitting cost and an additional squared $\ell_2$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management, where sw… ▽ More We study the smoothed online quadratic optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t$ in response to a quadratic hitting cost and an additional squared $\ell_2$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management, where switching-efficient algorithms are highly sought after. We study the SOQO problem in both adversarial and stochastic settings, and in this process, perform the first stochastic analysis of this class of problems. We provide the online optimal algorithm when the minimizers of the hitting cost function evolve as a general stochastic process, which, for the case of martingale process, takes the form of a distribution-agnostic dynamic interpolation algorithm (LAI). Next, we present the stochastic-adversarial trade-off by proving an $Ω(T)$ expected regret for the adversarial optimal algorithm in the literature (ROBD) with respect to LAI and, a sub-optimal competitive ratio for LAI in the adversarial setting. Finally, we present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal stochastic performance. △ Less

Submitted 23 March, 2024; v1 submitted 31 October, 2023; originally announced November 2023.

Comments: 48 pages, 9 figures

Systematic Adaptation of Communication-focused Machine Learning Models from Real to Virtual Environments for Human-Robot Collaboration

Authors: Debasmita Mukherjee, Ritwik Singhai, Homayoun Najjaran

Abstract: Virtual reality has proved to be useful in applications in several fields ranging from gaming, medicine, and training to development of interfaces that enable human-robot collaboration. It empowers designers to explore applications outside of the constraints posed by the real world environment and develop innovative solutions and experiences. Hand gestures recognition which has been a topic of muc… ▽ More Virtual reality has proved to be useful in applications in several fields ranging from gaming, medicine, and training to development of interfaces that enable human-robot collaboration. It empowers designers to explore applications outside of the constraints posed by the real world environment and develop innovative solutions and experiences. Hand gestures recognition which has been a topic of much research and subsequent commercialization in the real world has been possible because of the creation of large, labelled datasets. In order to utilize the power of natural and intuitive hand gestures in the virtual domain for enabling embodied teleoperation of collaborative robots, similarly large datasets must be created so as to keep the working interface easy to learn and flexible enough to add more gestures. Depending on the application, this may be computationally or economically prohibitive. Thus, the adaptation of trained deep learning models that perform well in the real environment to the virtual may be a solution to this challenge. This paper presents a systematic framework for the real to virtual adaptation using limited size of virtual dataset along with guidelines for creating a curated dataset. Finally, while hand gestures have been considered as the communication mode, the guidelines and recommendations presented are generic. These are applicable to other modes such as body poses and facial expressions which have large datasets available in the real domain which must be adapted to the virtual one. △ Less

Submitted 20 July, 2023; originally announced July 2023.

Cyber Framework for Steering and Measurements Collection Over Instrument-Computing Ecosystems

Authors: Anees Al-Najjar, Nageswara S. V. Rao, Ramanan Sankaran, Helia Zandi, Debangshu Mukherjee, Maxim Ziatdinov, Craig Bridges

Abstract: We propose a framework to develop cyber solutions to support the remote steering of science instruments and measurements collection over instrument-computing ecosystems. It is based on provisioning separate data and control connections at the network level, and developing software modules consisting of Python wrappers for instrument commands and Pyro server-client codes that make them available ac… ▽ More We propose a framework to develop cyber solutions to support the remote steering of science instruments and measurements collection over instrument-computing ecosystems. It is based on provisioning separate data and control connections at the network level, and developing software modules consisting of Python wrappers for instrument commands and Pyro server-client codes that make them available across the ecosystem network. We demonstrate automated measurement transfers and remote steering operations in a microscopy use case for materials research over an ecosystem of Nion microscopes and computing platforms connected over site networks. The proposed framework is currently under further refinement and being adopted to science workflows with automated remote experiments steering for autonomous chemistry laboratories and smart energy grid simulations. △ Less

Submitted 12 July, 2023; originally announced July 2023.

Comments: Paper accepted for presentation at IEEE SMARTCOMP 2023

Supportive Fintech for Individuals with Bipolar Disorder: Financial Data Sharing Preferences to Support Longitudinal Care Management

Authors: Jeff Brozena, Johnna Blair, Thomas Richardson, Mark Matthews, Dahlia Mukherjee, Erika F. H. Saunders, Saeed Abdullah

Abstract: Financial stability is a key challenge for individuals living with bipolar disorder (BD). Symptomatic periods in BD are associated with poor financial decision-making, contributing to a negative cycle of worsening symptoms and an increased risk of bankruptcy. There has been an increased focus on designing supportive financial technologies (fintech) to address varying and intermittent needs across… ▽ More Financial stability is a key challenge for individuals living with bipolar disorder (BD). Symptomatic periods in BD are associated with poor financial decision-making, contributing to a negative cycle of worsening symptoms and an increased risk of bankruptcy. There has been an increased focus on designing supportive financial technologies (fintech) to address varying and intermittent needs across different stages of BD. However, little is known about this population's expectations and privacy preferences related to financial data sharing for longitudinal care management. To address this knowledge gap, we have deployed a factorial vignette survey using the Contextual Integrity framework. Our data from individuals with BD (N=480) shows that they are open to sharing financial data for long term care management. We have also identified significant differences in sharing preferences across age, gender, and diagnostic subtype. We discuss the implications of these findings in designing equitable fintech to support this marginalized community. △ Less

Submitted 28 February, 2024; v1 submitted 27 June, 2023; originally announced June 2023.

Comments: 15 pages, 4 figures, Proceedings of the CHI Conference on Human Factors in Computing Systems, May 11-16, 2024, Honolulu, HI, USA

Optimal Rate-Matrix Pruning For Large-Scale Heterogeneous Systems

Authors: Zhisheng Zhao, Debankur Mukherjee

Abstract: We present an analysis of large-scale load balancing systems, where the processing time distribution of tasks depends on both the task and server types. Our study focuses on the asymptotic regime, where the number of servers and task types tend to infinity in proportion. In heterogeneous environments, commonly used load balancing policies such as Join Fastest Idle Queue and Join Fastest Shortest Q… ▽ More We present an analysis of large-scale load balancing systems, where the processing time distribution of tasks depends on both the task and server types. Our study focuses on the asymptotic regime, where the number of servers and task types tend to infinity in proportion. In heterogeneous environments, commonly used load balancing policies such as Join Fastest Idle Queue and Join Fastest Shortest Queue exhibit poor performance and even shrink the stability region. Interestingly, prior to this work, finding a scalable policy with a provable performance guarantee in this setup remained an open question. To address this gap, we propose and analyze two asymptotically delay-optimal dynamic load balancing policies. The first policy efficiently reserves the processing capacity of each server for ``good" tasks and routes tasks using the vanilla Join Idle Queue policy. The second policy, called the speed-priority policy, significantly increases the likelihood of assigning tasks to the respective ``good" servers capable of processing them at high speeds. By leveraging a framework inspired by the graphon literature and employing the mean-field method and stochastic coupling arguments, we demonstrate that both policies achieve asymptotic zero queuing. Specifically, as the system scales, the probability of a typical task being assigned to an idle server approaches 1. △ Less

Submitted 15 June, 2023; v1 submitted 31 May, 2023; originally announced June 2023.

Comments: 38 pages

Deep Learning for Automated Experimentation in Scanning Transmission Electron Microscopy

Authors: Sergei V. Kalinin, Debangshu Mukherjee, Kevin M. Roccapriore, Ben Blaiszik, Ayana Ghosh, Maxim A. Ziatdinov, A. Al-Najjar, Christina Doty, Sarah Akers, Nageswara S. Rao, Joshua C. Agar, Steven R. Spurgeon

Abstract: Machine learning (ML) has become critical for post-acquisition data analysis in (scanning) transmission electron microscopy, (S)TEM, imaging and spectroscopy. An emerging trend is the transition to real-time analysis and closed-loop microscope operation. The effective use of ML in electron microscopy now requires the development of strategies for microscopy-centered experiment workflow design and… ▽ More Machine learning (ML) has become critical for post-acquisition data analysis in (scanning) transmission electron microscopy, (S)TEM, imaging and spectroscopy. An emerging trend is the transition to real-time analysis and closed-loop microscope operation. The effective use of ML in electron microscopy now requires the development of strategies for microscopy-centered experiment workflow design and optimization. Here, we discuss the associated challenges with the transition to active ML, including sequential data analysis and out-of-distribution drift effects, the requirements for the edge operation, local and cloud data storage, and theory in the loop operations. Specifically, we discuss the relative contributions of human scientists and ML agents in the ideation, orchestration, and execution of experimental workflows and the need to develop universal hyper languages that can apply across multiple platforms. These considerations will collectively inform the operationalization of ML in next-generation experimentation. △ Less

Submitted 4 April, 2023; originally announced April 2023.

Comments: Review Article

Exploiting Data Locality to Improve Performance of Heterogeneous Server Clusters

Authors: Zhisheng Zhao, Debankur Mukherjee, Ruoyu Wu

Abstract: We consider load balancing in large-scale heterogeneous server systems in the presence of data locality that imposes constraints on which tasks can be assigned to which servers. The constraints are naturally captured by a bipartite graph between the servers and the dispatchers handling assignments of various arrival flows. When a task arrives, the corresponding dispatcher assigns it to a server wi… ▽ More We consider load balancing in large-scale heterogeneous server systems in the presence of data locality that imposes constraints on which tasks can be assigned to which servers. The constraints are naturally captured by a bipartite graph between the servers and the dispatchers handling assignments of various arrival flows. When a task arrives, the corresponding dispatcher assigns it to a server with the shortest queue among $d\geq 2$ randomly selected servers obeying the above constraints. Server processing speeds are heterogeneous and they depend on the server-type. For a broad class of bipartite graphs, we characterize the limit of the appropriately scaled occupancy process, both on the process-level and in steady state, as the system size becomes large. Using such a characterization, we show that data locality constraints can be used to significantly improve the performance of heterogeneous systems. This is in stark contrast to either heterogeneous servers in a full flexible system or data locality constraints in systems with homogeneous servers, both of which have been observed to degrade the system performance. Extensive numerical experiments corroborate the theoretical results. △ Less

Submitted 29 November, 2022; originally announced November 2022.

Comments: 52 pages, 10 figures

Enabling Autonomous Electron Microscopy for Networked Computation and Steering

Authors: Anees Al-Najjar, Nageswara S. V. Rao, Ramanan Sankaran, Maxim Ziatdinov, Debangshu Mukherjee, Olga Ovchinnikova, Kevin Roccapriore, Andrew R. Lupini, Sergei V. Kalinin

Abstract: Advanced electron microscopy workflows require an ecosystem of microscope instruments and computing systems possibly located at different sites to conduct remotely steered and automated experiments. Current workflow executions involve manual operations for steering and measurement tasks, which are typically performed from control workstations co-located with microscopes; consequently, their operat… ▽ More Advanced electron microscopy workflows require an ecosystem of microscope instruments and computing systems possibly located at different sites to conduct remotely steered and automated experiments. Current workflow executions involve manual operations for steering and measurement tasks, which are typically performed from control workstations co-located with microscopes; consequently, their operational tempo and effectiveness are limited. We propose an approach based on separate data and control channels for such an ecosystem of Scanning Transmission Electron Microscopes (STEM) and computing systems, for which no general solutions presently exist, unlike the neutron and light source instruments. We demonstrate automated measurement transfers and remote steering of Nion STEM physical instruments over site networks. We propose a Virtual Infrastructure Twin (VIT) of this ecosystem, which is used to develop and test our steering software modules without requiring access to the physical instrument infrastructure. Additionally, we develop a VIT for a multiple laboratory scenario, which illustrates the applicability of this approach to ecosystems connected over wide-area networks, for the development and testing of software modules and their later field deployment. △ Less

Submitted 18 October, 2022; originally announced October 2022.

Comments: 11 pages, 16 figures, accepted at IEEE eScience 2022 conference

Significance of Skeleton-based Features in Virtual Try-On

Authors: Debapriya Roy, Sanchayan Santra, Diganta Mukherjee, Bhabatosh Chanda

Abstract: The idea of \textit{Virtual Try-ON} (VTON) benefits e-retailing by giving an user the convenience of trying a clothing at the comfort of their home. In general, most of the existing VTON methods produce inconsistent results when a person posing with his arms folded i.e., bent or crossed, wants to try an outfit. The problem becomes severe in the case of long-sleeved outfits. As then, for crossed ar… ▽ More The idea of \textit{Virtual Try-ON} (VTON) benefits e-retailing by giving an user the convenience of trying a clothing at the comfort of their home. In general, most of the existing VTON methods produce inconsistent results when a person posing with his arms folded i.e., bent or crossed, wants to try an outfit. The problem becomes severe in the case of long-sleeved outfits. As then, for crossed arm postures, overlap among different clothing parts might happen. The existing approaches, especially the warping-based methods employing \textit{Thin Plate Spline (TPS)} transform can not tackle such cases. To this end, we attempt a solution approach where the clothing from the source person is segmented into semantically meaningful parts and each part is warped independently to the shape of the person. To address the bending issue, we employ hand-crafted geometric features consistent with human body geometry for warping the source outfit. In addition, we propose two learning-based modules: a synthesizer network and a mask prediction network. All these together attempt to produce a photo-realistic, pose-robust VTON solution without requiring any paired training data. Comparison with some of the benchmark methods clearly establishes the effectiveness of the approach. △ Less

Submitted 6 January, 2024; v1 submitted 17 August, 2022; originally announced August 2022.

Estimating Emotion Contagion on Social Media via Localized Diffusion in Dynamic Graphs

Authors: Trisha Mittal, Puneet Mathur, Rohan Chandra, Apurva Bhatt, Vikram Gupta, Debdoot Mukherjee, Aniket Bera, Dinesh Manocha

Abstract: We present a computational approach for estimating emotion contagion on social media networks. Built on a foundation of psychology literature, our approach estimates the degree to which the perceivers' emotional states (positive or negative) start to match those of the expressors, based on the latter's content. We use a combination of deep learning and social network analysis to model emotion cont… ▽ More We present a computational approach for estimating emotion contagion on social media networks. Built on a foundation of psychology literature, our approach estimates the degree to which the perceivers' emotional states (positive or negative) start to match those of the expressors, based on the latter's content. We use a combination of deep learning and social network analysis to model emotion contagion as a diffusion process in dynamic social network graphs, taking into consideration key aspects like causality, homophily, and interference. We evaluate our approach on user behavior data obtained from a popular social media platform for sharing short videos. We analyze the behavior of 48 users over a span of 8 weeks (over 200k audio-visual short posts analyzed) and estimate how contagious the users with whom they engage with are on social media. As per the theory of diffusion, we account for the videos a user watches during this time (inflow) and the daily engagements; liking, sharing, downloading or creating new videos (outflow) to estimate contagion. To validate our approach and analysis, we obtain human feedback on these 48 social media platform users with an online study by collecting responses of about 150 participants. We report users who interact with more number of creators on the platform are 12% less prone to contagion, and those who consume more content of `negative' sentiment are 23% more prone to contagion. We will publicly release our code upon acceptance. △ Less

Submitted 14 July, 2022; originally announced July 2022.

Predictor-corrector algorithms for stochastic optimization under gradual distribution shift

Authors: Subha Maity, Debarghya Mukherjee, Moulinath Banerjee, Yuekai Sun

Abstract: Time-varying stochastic optimization problems frequently arise in machine learning practice (e.g. gradual domain shift, object tracking, strategic classification). Although most problems are solved in discrete time, the underlying process is often continuous in nature. We exploit this underlying continuity by developing predictor-corrector algorithms for time-varying stochastic optimizations. We p… ▽ More Time-varying stochastic optimization problems frequently arise in machine learning practice (e.g. gradual domain shift, object tracking, strategic classification). Although most problems are solved in discrete time, the underlying process is often continuous in nature. We exploit this underlying continuity by developing predictor-corrector algorithms for time-varying stochastic optimizations. We provide error bounds for the iterates, both in presence of pure and noisy access to the queries from the relevant derivatives of the loss function. Furthermore, we show (theoretically and empirically in several examples) that our method outperforms non-predictor corrector methods that do not exploit the underlying continuous process. △ Less

Submitted 23 February, 2023; v1 submitted 26 May, 2022; originally announced May 2022.

Comments: Accepted in ICLR 2023

Image Gradient Decomposition for Parallel and Memory-Efficient Ptychographic Reconstruction

Authors: Xiao Wang, Aristeidis Tsaris, Debangshu Mukherjee, Mohamed Wahib, Peng Chen, Mark Oxley, Olga Ovchinnikova, Jacob Hinkle

Abstract: Ptychography is a popular microscopic imaging modality for many scientific discoveries and sets the record for highest image resolution. Unfortunately, the high image resolution for ptychographic reconstruction requires significant amount of memory and computations, forcing many applications to compromise their image resolution in exchange for a smaller memory footprint and a shorter reconstructio… ▽ More Ptychography is a popular microscopic imaging modality for many scientific discoveries and sets the record for highest image resolution. Unfortunately, the high image resolution for ptychographic reconstruction requires significant amount of memory and computations, forcing many applications to compromise their image resolution in exchange for a smaller memory footprint and a shorter reconstruction time. In this paper, we propose a novel image gradient decomposition method that significantly reduces the memory footprint for ptychographic reconstruction by tessellating image gradients and diffraction measurements into tiles. In addition, we propose a parallel image gradient decomposition method that enables asynchronous point-to-point communications and parallel pipelining with minimal overhead on a large number of GPUs. Our experiments on a Titanate material dataset (PbTiO3) with 16632 probe locations show that our Gradient Decomposition algorithm reduces memory footprint by 51 times. In addition, it achieves time-to-solution within 2.2 minutes by scaling to 4158 GPUs with a super-linear strong scaling efficiency at 364% compared to runtimes at 6 GPUs. This performance is 2.7 times more memory efficient, 9 times more scalable and 86 times faster than the state-of-the-art algorithm. △ Less

Submitted 16 December, 2022; v1 submitted 12 May, 2022; originally announced May 2022.

Journal ref: Proceedings of the SC 22. IEEE Press, Article 8, 1-13 (2022)

Domain Adaptation meets Individual Fairness. And they get along

Authors: Debarghya Mukherjee, Felix Petersen, Mikhail Yurochkin, Yuekai Sun

Abstract: Many instances of algorithmic bias are caused by distributional shifts. For example, machine learning (ML) models often perform worse on demographic groups that are underrepresented in the training data. In this paper, we leverage this connection between algorithmic fairness and distribution shifts to show that algorithmic fairness interventions can help ML models overcome distribution shifts, and… ▽ More Many instances of algorithmic bias are caused by distributional shifts. For example, machine learning (ML) models often perform worse on demographic groups that are underrepresented in the training data. In this paper, we leverage this connection between algorithmic fairness and distribution shifts to show that algorithmic fairness interventions can help ML models overcome distribution shifts, and that domain adaptation methods (for overcoming distribution shifts) can mitigate algorithmic biases. In particular, we show that (i) enforcing suitable notions of individual fairness (IF) can improve the out-of-distribution accuracy of ML models under the covariate shift assumption and that (ii) it is possible to adapt representation alignment methods for domain adaptation to enforce individual fairness. The former is unexpected because IF interventions were not developed with distribution shifts in mind. The latter is also unexpected because representation alignment is not a common approach in the individual fairness literature. △ Less

Submitted 15 October, 2022; v1 submitted 1 May, 2022; originally announced May 2022.

Comments: Published at NeurIPS 2022

Multilingual and Multimodal Abuse Detection

Authors: Rini Sharon, Heet Shah, Debdoot Mukherjee, Vikram Gupta

Abstract: The presence of abusive content on social media platforms is undesirable as it severely impedes healthy and safe social media interactions. While automatic abuse detection has been widely explored in textual domain, audio abuse detection still remains unexplored. In this paper, we attempt abuse detection in conversational audio from a multimodal perspective in a multilingual social media setting.… ▽ More The presence of abusive content on social media platforms is undesirable as it severely impedes healthy and safe social media interactions. While automatic abuse detection has been widely explored in textual domain, audio abuse detection still remains unexplored. In this paper, we attempt abuse detection in conversational audio from a multimodal perspective in a multilingual social media setting. Our key hypothesis is that along with the modelling of audio, incorporating discriminative information from other modalities can be highly beneficial for this task. Our proposed method, MADA, explicitly focuses on two modalities other than the audio itself, namely, the underlying emotions expressed in the abusive audio and the semantic information encapsulated in the corresponding textual form. Observations prove that MADA demonstrates gains over audio-only approaches on the ADIMA dataset. We test the proposed approach on 10 different languages and observe consistent gains in the range 0.6%-5.2% by leveraging multiple modalities. We also perform extensive ablation experiments for studying the contributions of every modality and observe the best results while leveraging all the modalities together. Additionally, we perform experiments to empirically confirm that there is a strong correlation between underlying emotions and abusive behaviour. △ Less

Submitted 3 April, 2022; originally announced April 2022.

Comments: Submitted to Interspeech 2022

3MASSIV: Multilingual, Multimodal and Multi-Aspect dataset of Social Media Short Videos

Authors: Vikram Gupta, Trisha Mittal, Puneet Mathur, Vaibhav Mishra, Mayank Maheshwari, Aniket Bera, Debdoot Mukherjee, Dinesh Manocha

Abstract: We present 3MASSIV, a multilingual, multimodal and multi-aspect, expertly-annotated dataset of diverse short videos extracted from short-video social media platform - Moj. 3MASSIV comprises of 50k short videos (20 seconds average duration) and 100K unlabeled videos in 11 different languages and captures popular short video trends like pranks, fails, romance, comedy expressed via unique audio-visua… ▽ More We present 3MASSIV, a multilingual, multimodal and multi-aspect, expertly-annotated dataset of diverse short videos extracted from short-video social media platform - Moj. 3MASSIV comprises of 50k short videos (20 seconds average duration) and 100K unlabeled videos in 11 different languages and captures popular short video trends like pranks, fails, romance, comedy expressed via unique audio-visual formats like self-shot videos, reaction videos, lip-synching, self-sung songs, etc. 3MASSIV presents an opportunity for multimodal and multilingual semantic understanding on these unique videos by annotating them for concepts, affective states, media types, and audio language. We present a thorough analysis of 3MASSIV and highlight the variety and unique aspects of our dataset compared to other contemporary popular datasets with strong baselines. We also show how the social media content in 3MASSIV is dynamic and temporal in nature, which can be used for semantic understanding tasks and cross-lingual analysis. △ Less

Submitted 27 March, 2022; originally announced March 2022.

Comments: Accepted in CVPR 2022

ADIMA: Abuse Detection In Multilingual Audio

Authors: Vikram Gupta, Rini Sharon, Ramit Sawhney, Debdoot Mukherjee

Abstract: Abusive content detection in spoken text can be addressed by performing Automatic Speech Recognition (ASR) and leveraging advancements in natural language processing. However, ASR models introduce latency and often perform sub-optimally for profane words as they are underrepresented in training corpora and not spoken clearly or completely. Exploration of this problem entirely in the audio domain h… ▽ More Abusive content detection in spoken text can be addressed by performing Automatic Speech Recognition (ASR) and leveraging advancements in natural language processing. However, ASR models introduce latency and often perform sub-optimally for profane words as they are underrepresented in training corpora and not spoken clearly or completely. Exploration of this problem entirely in the audio domain has largely been limited by the lack of audio datasets. Building on these challenges, we propose ADIMA, a novel, linguistically diverse, ethically sourced, expert annotated and well-balanced multilingual profanity detection audio dataset comprising of 11,775 audio samples in 10 Indic languages spanning 65 hours and spoken by 6,446 unique users. Through quantitative experiments across monolingual and cross-lingual zero-shot settings, we take the first step in democratizing audio based content moderation in Indic languages and set forth our dataset to pave future work. △ Less

Submitted 16 February, 2022; originally announced February 2022.

Smoothed Online Optimization with Unreliable Predictions

Authors: Daan Rutten, Nico Christianson, Debankur Mukherjee, Adam Wierman

Abstract: We examine the problem of smoothed online optimization, where a decision maker must sequentially choose points in a normed vector space to minimize the sum of per-round, non-convex hitting costs and the costs of switching decisions between rounds. The decision maker has access to a black-box oracle, such as a machine learning model, that provides untrusted and potentially inaccurate predictions of… ▽ More We examine the problem of smoothed online optimization, where a decision maker must sequentially choose points in a normed vector space to minimize the sum of per-round, non-convex hitting costs and the costs of switching decisions between rounds. The decision maker has access to a black-box oracle, such as a machine learning model, that provides untrusted and potentially inaccurate predictions of the optimal decision in each round. The goal of the decision maker is to exploit the predictions if they are accurate, while guaranteeing performance that is not much worse than the hindsight optimal sequence of decisions, even when predictions are inaccurate. We impose the standard assumption that hitting costs are globally $α$-polyhedral. We propose a novel algorithm, Adaptive Online Switching (AOS), and prove that, for a large set of feasible $δ> 0$, it is $(1+δ)$-competitive if predictions are perfect, while also maintaining a uniformly bounded competitive ratio of $2^{\tilde{\mathcal{O}}(1/(αδ))}$ even when predictions are adversarial. Further, we prove that this trade-off is necessary and nearly optimal in the sense that \emph{any} deterministic algorithm which is $(1+δ)$-competitive if predictions are perfect must be at least $2^{\tildeΩ(1/(αδ))}$-competitive when predictions are inaccurate. In fact, we observe a unique threshold-type behavior in this trade-off: if $δ$ is not in the set of feasible options, then \emph{no} algorithm is simultaneously $(1 + δ)$-competitive if predictions are perfect and $ζ$-competitive when predictions are inaccurate for any $ζ< \infty$. Furthermore, we discuss that memory is crucial in AOS by proving that any algorithm that does not use memory cannot benefit from predictions. We complement our theoretical results by a numerical study on a microgrid application. △ Less

Submitted 26 October, 2022; v1 submitted 7 February, 2022; originally announced February 2022.

Comments: 38 pages, 4 figures

MSC Class: 68Q25 (Primary) 68T20; 68W27 (Secondary) ACM Class: G.1.6; I.2.8; F.2.2

Reduction of Two-Dimensional Data for Speeding Up Convex Hull Computation

Authors: Debashis Mukherjee

Abstract: An incremental approach for computation of convex hull for data points in two-dimensions is presented. The algorithm is not output-sensitive and costs a time that is linear in the size of data points at input. Graham's scan is applied only on a subset of the data points, represented at the extremal of the dataset. Points are classified for extremal, in proportion with the modular distance, about a… ▽ More An incremental approach for computation of convex hull for data points in two-dimensions is presented. The algorithm is not output-sensitive and costs a time that is linear in the size of data points at input. Graham's scan is applied only on a subset of the data points, represented at the extremal of the dataset. Points are classified for extremal, in proportion with the modular distance, about an imaginary point interior to the region bounded by convex hull of the dataset assumed for origin or center in polar coordinate. A subset of the data is arrived by terminating at until an event of no change in maximal points is observed per bin, for iteratively and exponentially decreasing intervals. △ Less

Submitted 10 February, 2022; v1 submitted 27 January, 2022; originally announced January 2022.

Comments: 12 pages, 6 figures

Post-processing for Individual Fairness

Authors: Felix Petersen, Debarghya Mukherjee, Yuekai Sun, Mikhail Yurochkin

Abstract: Post-processing in algorithmic fairness is a versatile approach for correcting bias in ML systems that are already used in production. The main appeal of post-processing is that it avoids expensive retraining. In this work, we propose general post-processing algorithms for individual fairness (IF). We consider a setting where the learner only has access to the predictions of the original model and… ▽ More Post-processing in algorithmic fairness is a versatile approach for correcting bias in ML systems that are already used in production. The main appeal of post-processing is that it avoids expensive retraining. In this work, we propose general post-processing algorithms for individual fairness (IF). We consider a setting where the learner only has access to the predictions of the original model and a similarity graph between individuals, guiding the desired fairness constraints. We cast the IF post-processing problem as a graph smoothing problem corresponding to graph Laplacian regularization that preserves the desired "treat similar individuals similarly" interpretation. Our theoretical results demonstrate the connection of the new objective function to a local relaxation of the original individual fairness. Empirically, our post-processing algorithms correct individual biases in large-scale NLP models such as BERT, while preserving accuracy. △ Less

Submitted 26 October, 2021; originally announced October 2021.

Comments: Published at NeurIPS 2021, Code @ https://github.com/Felix-Petersen/fairness-post-processing, Video @ https://www.youtube.com/watch?v=9PyKODDewPA

Three-agent Time-constrained Cooperative Pursuit-Evasion

Authors: Abhinav Sinha, Shashi Ranjan Kumar, Dwaipayan Mukherjee

Abstract: This paper considers a pursuit-evasion scenario among three agents -- an evader, a pursuer, and a defender. We design cooperative guidance laws for the evader and the defender team to safeguard the evader from an attacking pursuer. Unlike differential games, optimal control formulations, and other heuristic methods, we propose a novel perspective on designing effective nonlinear feedback control l… ▽ More This paper considers a pursuit-evasion scenario among three agents -- an evader, a pursuer, and a defender. We design cooperative guidance laws for the evader and the defender team to safeguard the evader from an attacking pursuer. Unlike differential games, optimal control formulations, and other heuristic methods, we propose a novel perspective on designing effective nonlinear feedback control laws for the evader-defender team using a time-constrained guidance approach. The evader lures the pursuer on the collision course by offering itself as bait. At the same time, the defender protects the evader from the pursuer by exercising control over the engagement duration. Depending on the nature of the mission, the defender may choose to take an aggressive or defensive stance. Such consideration widens the applicability of the proposed methods in various three-agent motion planning scenarios such as aircraft defense, asset guarding, search and rescue, surveillance, and secure transportation. We use a fixed-time sliding mode control strategy to design the control laws for the evader-defender team and a nonlinear finite-time disturbance observer to estimate the pursuer's maneuver. Finally, we present simulations to demonstrate favorable performance under various engagement geometries, thus vindicating the efficacy of the proposed designs. △ Less

Submitted 17 January, 2022; v1 submitted 3 June, 2021; originally announced June 2021.

Comments: The most recent version of this article can be viewed at https://doi.org/10.1007/s10846-022-01570-y

Journal ref: published in Journal of Intelligent & Robotic Systems (2022)

Online Capacity Scaling Augmented With Unreliable Machine Learning Predictions

Authors: Daan Rutten, Debankur Mukherjee

Abstract: Modern data centers suffer from immense power consumption. As a result, data center operators have heavily invested in capacity scaling solutions, which dynamically deactivate servers if the demand is low and activate them again when the workload increases. We analyze a continuous-time model for capacity scaling, where the goal is to minimize the weighted sum of flow-time, switching cost, and powe… ▽ More Modern data centers suffer from immense power consumption. As a result, data center operators have heavily invested in capacity scaling solutions, which dynamically deactivate servers if the demand is low and activate them again when the workload increases. We analyze a continuous-time model for capacity scaling, where the goal is to minimize the weighted sum of flow-time, switching cost, and power consumption in an online fashion. We propose a novel algorithm, called Adaptive Balanced Capacity Scaling (ABCS), that has access to black-box machine learning predictions. ABCS aims to adapt to the predictions and is also robust against unpredictable surges in the workload. In particular, we prove that ABCS is $(1+\varepsilon)$-competitive if the predictions are accurate, and yet, it has a uniformly bounded competitive ratio even if the predictions are completely inaccurate. Finally, we investigate the performance of this algorithm on a real-world dataset and carry out extensive numerical experiments, which positively support the theoretical results. △ Less

Submitted 20 April, 2022; v1 submitted 28 January, 2021; originally announced January 2021.

Comments: 47 pages, 9 figures. Changed related works, model description and numerical experiments. Strengthened Lemma 2.5, Proposition 4.17 and Lemma 7.1. Added remarks 4.6, 4.9, 4.10, 4.13 and 6.2

MSC Class: 68M20 ACM Class: C.4; I.2.8

Study On Coding Tools Beyond Av1

Authors: Xin Zhao, Liang Zhao, Madhu Krishnan, Yixin Du, Shan Liu, Debargha Mukherjee, Yaowu Xu, Adrian Grange

Abstract: The Alliance for Open Media has recently initiated coding tool exploration activities towards the next-generation video coding beyond AV1. With this regard, this paper presents a package of coding tools that have been investigated, implemented and tested on top of the codebase, known as libaom, which is used for the exploration of next-generation video compression tools. The proposed tools cover s… ▽ More The Alliance for Open Media has recently initiated coding tool exploration activities towards the next-generation video coding beyond AV1. With this regard, this paper presents a package of coding tools that have been investigated, implemented and tested on top of the codebase, known as libaom, which is used for the exploration of next-generation video compression tools. The proposed tools cover several technical areas based on a traditional hybrid video coding structure, including block partitioning, prediction, transform and loop filtering. The proposed coding tools are integrated as a package, and a combined coding gain over AV1 is demonstrated in this paper. Furthermore, to better understand the behavior of each tool, besides the combined coding gain, the tool-on and tool-off tests are also simulated and reported for each individual coding tool. Experimental results show that, compared to libaom, the proposed methods achieve an average 8.0% (up to 22.0%) overall BD-rate reduction for All Intra coding configuration a wide range of image and video content. △ Less

Submitted 24 December, 2020; originally announced December 2020.

Comments: 6 pages, 3 figures and 3 tables

Does enforcing fairness mitigate biases caused by subpopulation shift?

Authors: Subha Maity, Debarghya Mukherjee, Mikhail Yurochkin, Yuekai Sun

Abstract: Many instances of algorithmic bias are caused by subpopulation shifts. For example, ML models often perform worse on demographic groups that are underrepresented in the training data. In this paper, we study whether enforcing algorithmic fairness during training improves the performance of the trained model in the \emph{target domain}. On one hand, we conceive scenarios in which enforcing fairness… ▽ More Many instances of algorithmic bias are caused by subpopulation shifts. For example, ML models often perform worse on demographic groups that are underrepresented in the training data. In this paper, we study whether enforcing algorithmic fairness during training improves the performance of the trained model in the \emph{target domain}. On one hand, we conceive scenarios in which enforcing fairness does not improve performance in the target domain. In fact, it may even harm performance. On the other hand, we derive necessary and sufficient conditions under which enforcing algorithmic fairness leads to the Bayes model in the target domain. We also illustrate the practical implications of our theoretical results in simulations and on real data. △ Less

Submitted 26 October, 2021; v1 submitted 5 November, 2020; originally announced November 2020.

An Unsupervised Approach towards Varying Human Skin Tone Using Generative Adversarial Networks

Authors: Debapriya Roy, Diganta Mukherjee, Bhabatosh Chanda

Abstract: With the increasing popularity of augmented and virtual reality, retailers are now focusing more towards customer satisfaction to increase the amount of sales. Although augmented reality is not a new concept but it has gained much needed attention over the past few years. Our present work is targeted towards this direction which may be used to enhance user experience in various virtual and augment… ▽ More With the increasing popularity of augmented and virtual reality, retailers are now focusing more towards customer satisfaction to increase the amount of sales. Although augmented reality is not a new concept but it has gained much needed attention over the past few years. Our present work is targeted towards this direction which may be used to enhance user experience in various virtual and augmented reality based applications. We propose a model to change skin tone of a person. Given any input image of a person or a group of persons with some value indicating the desired change of skin color towards fairness or darkness, this method can change the skin tone of the persons in the image. This is an unsupervised method and also unconstrained in terms of pose, illumination, number of persons in the image etc. The goal of this work is to reduce the time and effort which is generally required for changing the skin tone using existing applications (e.g., Photoshop) by professionals or novice. To establish the efficacy of this method we have compared our result with that of some popular photo editor and also with the result of some existing benchmark method related to human attribute manipulation. Rigorous experiments on different datasets show the effectiveness of this method in terms of synthesizing perceptually convincing outputs. △ Less

Submitted 30 October, 2020; originally announced October 2020.

Comments: Accepted in International Conference on Pattern Recognition 2020

Self-Learning Threshold-Based Load Balancing

Authors: Diego Goldsztajn, Sem C. Borst, Johan S. H. van Leeuwaarden, Debankur Mukherjee, Philip A. Whiting

Abstract: We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality-of-service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the flui… ▽ More We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality-of-service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions which guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments which support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns. △ Less

Submitted 11 September, 2023; v1 submitted 29 October, 2020; originally announced October 2020.

Comments: 52 pages, 6 figures

MSC Class: 60F17; 60K25 (Primary) 68M20 (Secondary) ACM Class: C.4; G.3

Journal ref: INFORMS Journal on Computing, 34(1):39-54, 2022

An Empirical Study on User Reviews Targeting Mobile Apps' Security & Privacy

Authors: Debjyoti Mukherjee, Alireza Ahmadi, Maryam Vahdat Pour, Joel Reardon

Abstract: Application markets provide a communication channel between app developers and their end-users in form of app reviews, which allow users to provide feedback about the apps. Although security and privacy in mobile apps are one of the biggest issues, it is unclear how much people are aware of these or discuss them in reviews. In this study, we explore the privacy and security concerns of users usi… ▽ More Application markets provide a communication channel between app developers and their end-users in form of app reviews, which allow users to provide feedback about the apps. Although security and privacy in mobile apps are one of the biggest issues, it is unclear how much people are aware of these or discuss them in reviews. In this study, we explore the privacy and security concerns of users using reviews in the Google Play Store. For this, we conducted a study by analyzing around 2.2M reviews from the top 539 apps of this Android market. We found that 0.5\% of these reviews are related to the security and privacy concerns of the users. We further investigated these apps by performing dynamic analysis which provided us valuable insights into their actual behaviors. Based on the different perspectives, we categorized the apps and evaluated how the different factors influence the users' perception of the apps. It was evident from the results that the number of permissions that the apps request plays a dominant role in this matter. We also found that sending out the location can affect the users' thoughts about the app. The other factors do not directly affect the privacy and security concerns for the users. △ Less

Submitted 10 October, 2020; originally announced October 2020.

Load Balancing Under Strict Compatibility Constraints

Authors: Daan Rutten, Debankur Mukherjee

Abstract: We study large-scale systems operating under the JSQ$(d)$ policy in the presence of stringent task-server compatibility constraints. Consider a system with $N$ identical single-server queues and $M(N)$ task types, where each server is able to process only a small subset of possible task types. Each arriving task selects $d\geq 2$ random servers compatible to its type, and joins the shortest queue… ▽ More We study large-scale systems operating under the JSQ$(d)$ policy in the presence of stringent task-server compatibility constraints. Consider a system with $N$ identical single-server queues and $M(N)$ task types, where each server is able to process only a small subset of possible task types. Each arriving task selects $d\geq 2$ random servers compatible to its type, and joins the shortest queue among them. The compatibility constraint is naturally captured by a fixed bipartite graph $G_N$ between the servers and the task types. When $G_N$ is complete bipartite, the meanfield approximation is proven to be accurate. However, such dense compatibility graphs are infeasible due to their overwhelming implementation cost and prohibitive storage capacity requirement at the servers. Our goal in this paper is to characterize the class of sparse compatibility graphs for which the meanfield approximation remains valid. To achieve this, first, we introduce a novel graph expansion-based notion, called proportional sparsity, and establish that systems with proportionally sparse compatibility graphs match the performance of a fully flexible system, asymptotically in the large-system limit. Furthermore, for any $c(N)$ satisfying $$\frac{Nc(N)}{M(N)\ln(N)}\to \infty\quad \text{and}\quad c(N)\to \infty,$$ as $N\to\infty$, we show that proportionally sparse random compatibility graphs can be designed, so that the degree of each server is at most $c(N)$. This reduces the server-degree almost by a factor $N/\ln(N)$, compared to the complete bipartite compatibility graph, while maintaining the same asymptotic performance. Extensive simulation experiments are conducted to corroborate the theoretical results. △ Less

Submitted 23 August, 2020; v1 submitted 17 August, 2020; originally announced August 2020.

Comments: 51 pages, 5 figures. 08/23/2020: Minor errors fixed in the proof of Theorem 4.3

MSC Class: 60J27 (Primary) 60G55 (Secondary) ACM Class: G.3.5; G.3.16

Two Simple Ways to Learn Individual Fairness Metrics from Data

Authors: Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, Yuekai Sun

Abstract: Individual fairness is an intuitive definition of algorithmic fairness that addresses some of the drawbacks of group fairness. Despite its benefits, it depends on a task specific fair metric that encodes our intuition of what is fair and unfair for the ML task at hand, and the lack of a widely accepted fair metric for many ML tasks is the main barrier to broader adoption of individual fairness. In… ▽ More Individual fairness is an intuitive definition of algorithmic fairness that addresses some of the drawbacks of group fairness. Despite its benefits, it depends on a task specific fair metric that encodes our intuition of what is fair and unfair for the ML task at hand, and the lack of a widely accepted fair metric for many ML tasks is the main barrier to broader adoption of individual fairness. In this paper, we present two simple ways to learn fair metrics from a variety of data types. We show empirically that fair training with the learned metrics leads to improved fairness on three machine learning tasks susceptible to gender and racial biases. We also provide theoretical guarantees on the statistical performance of both approaches. △ Less

Submitted 19 June, 2020; originally announced June 2020.

Comments: To appear in ICML 2020

An error reduced and uniform parameter approximation in fitting of B-spline curves to data points

Authors: Debashis Mukherjee

Abstract: Approximating data points in three or higher dimension space based on cubic B-spline curve is presented. Representations for planar curves, are merged and extended to the higher dimension. The curve is fitted to the order of data points, or uniform parameter values are assumed for the points. Tangents are assumed at the data points, corresponding to the property used in cardinal splines, for shape… ▽ More Approximating data points in three or higher dimension space based on cubic B-spline curve is presented. Representations for planar curves, are merged and extended to the higher dimension. The curve is fitted to the order of data points, or uniform parameter values are assumed for the points. Tangents are assumed at the data points, corresponding to the property used in cardinal splines, for shape preserving and visually pleasing fit. Control points of piecewise continuous cubic bezier curves, meeting the boundary conditions of cardinal spline segments, are used for b-spline curve in corresponding coordinate planes. Approximation using error computed in the least square sense, based on a fraction of data points, is also presented. △ Less

Submitted 18 May, 2020; originally announced May 2020.

Comments: 14 pages, 6 figures

Heterogeneous Edge Embeddings for Friend Recommendation

Authors: Janu Verma, Srishti Gupta, Debdoot Mukherjee, Tanmoy Chakraborty

Abstract: We propose a friend recommendation system (an application of link prediction) using edge embeddings on social networks. Most real-world social networks are multi-graphs, where different kinds of relationships (e.g. chat, friendship) are possible between a pair of users. Existing network embedding techniques do not leverage signals from different edge types and thus perform inadequately on link pre… ▽ More We propose a friend recommendation system (an application of link prediction) using edge embeddings on social networks. Most real-world social networks are multi-graphs, where different kinds of relationships (e.g. chat, friendship) are possible between a pair of users. Existing network embedding techniques do not leverage signals from different edge types and thus perform inadequately on link prediction in such networks. We propose a method to mine network representation that effectively exploits heterogeneity in multi-graphs. We evaluate our model on a real-world, active social network where this system is deployed for friend recommendation for millions of users. Our method outperforms various state-of-the-art baselines on Hike's social network in terms of accuracy as well as user satisfaction. △ Less

Submitted 7 February, 2019; originally announced February 2019.

Comments: To appear in ECIR, 2019

Understanding Chat Messages for Sticker Recommendation in Messaging Apps

Authors: Abhishek Laddha, Mohamed Hanoosh, Debdoot Mukherjee, Parth Patwa, Ankur Narang

Abstract: Stickers are popularly used in messaging apps such as Hike to visually express a nuanced range of thoughts and utterances to convey exaggerated emotions. However, discovering the right sticker from a large and ever expanding pool of stickers while chatting can be cumbersome. In this paper, we describe a system for recommending stickers in real time as the user is typing based on the context of the… ▽ More Stickers are popularly used in messaging apps such as Hike to visually express a nuanced range of thoughts and utterances to convey exaggerated emotions. However, discovering the right sticker from a large and ever expanding pool of stickers while chatting can be cumbersome. In this paper, we describe a system for recommending stickers in real time as the user is typing based on the context of the conversation. We decompose the sticker recommendation (SR) problem into two steps. First, we predict the message that the user is likely to send in the chat. Second, we substitute the predicted message with an appropriate sticker. Majority of Hike's messages are in the form of text which is transliterated from users' native language to the Roman script. This leads to numerous orthographic variations of the same message and makes accurate message prediction challenging. To address this issue, we learn dense representations of chat messages employing character level convolution network in an unsupervised manner. We use them to cluster the messages that have the same meaning. In the subsequent steps, we predict the message cluster instead of the message. Our approach does not depend on human labelled data (except for validation), leading to fully automatic updation and tuning pipeline for the underlying models. We also propose a novel hybrid message prediction model, which can run with low latency on low-end phones that have severe computational limitations. Our described system has been deployed for more than $6$ months and is being used by millions of users along with hundreds of thousands of expressive stickers. △ Less

Submitted 24 November, 2019; v1 submitted 7 February, 2019; originally announced February 2019.

Finite-time Heterogeneous Cyclic Pursuit with Application to Target Interception

Authors: Dwaipayan Mukherjee, Shashi Ranjan Kumar

Abstract: This paper presents a finite-time heterogeneous cyclic pursuit scheme that ensures consensus among agents modelled as integrators. It is shown that for the proposed sliding mode control, even when the gains corresponding to each agent are non-identical, consensus results within a finite-time provided all the gains are positive. An algorithm is presented to compute the consensus value and consensus… ▽ More This paper presents a finite-time heterogeneous cyclic pursuit scheme that ensures consensus among agents modelled as integrators. It is shown that for the proposed sliding mode control, even when the gains corresponding to each agent are non-identical, consensus results within a finite-time provided all the gains are positive. An algorithm is presented to compute the consensus value and consensus time for a given set of gains and initial states of the agents. The set of values where consensus can occur, by varying the gains, has been derived and a second algorithm aids in determining the gains that enable consensus at any point in the aforementioned set, within a given finite-time. As an application, the finite-time consensus in line-of-sight (LOS) rates, over a cycle digraph, for a group of interceptors is shown to be effective in ensuring co-operative collision-free interception of a target, for both kinematic and realistic models of the interceptors. Simulations vindicate the theoretical results. △ Less

Submitted 28 November, 2018; v1 submitted 27 November, 2018; originally announced November 2018.

Comments: 12 pages, 9 figures

Scalable Load Balancing Algorithms in Networked Systems

Authors: Debankur Mukherjee

Abstract: A fundamental challenge in large-scale networked systems viz., data centers and cloud networks is to distribute tasks to a pool of servers, using minimal instantaneous state information, while providing excellent delay performance. In this thesis we design and analyze load balancing algorithms that aim to achieve a highly efficient distribution of tasks, optimize server utilization, and minimize c… ▽ More A fundamental challenge in large-scale networked systems viz., data centers and cloud networks is to distribute tasks to a pool of servers, using minimal instantaneous state information, while providing excellent delay performance. In this thesis we design and analyze load balancing algorithms that aim to achieve a highly efficient distribution of tasks, optimize server utilization, and minimize communication overhead. △ Less

Submitted 6 September, 2018; originally announced September 2018.

Comments: Ph.D. thesis

Scalable load balancing in networked systems: A survey of recent advances

Authors: Mark van der Boor, Sem C. Borst, Johan S. H. van Leeuwaarden, Debankur Mukherjee

Abstract: The basic load balancing scenario involves a single dispatcher where tasks arrive that must immediately be forwarded to one of $N$ single-server queues. We discuss recent advances on scalable load balancing schemes which provide favorable delay performance when $N$ grows large, and yet only require minimal implementation overhead. Join-the-Shortest-Queue (JSQ) yields vanishing delays as $N$ grows… ▽ More The basic load balancing scenario involves a single dispatcher where tasks arrive that must immediately be forwarded to one of $N$ single-server queues. We discuss recent advances on scalable load balancing schemes which provide favorable delay performance when $N$ grows large, and yet only require minimal implementation overhead. Join-the-Shortest-Queue (JSQ) yields vanishing delays as $N$ grows large, as in a centralized queueing arrangement, but involves a prohibitive communication burden. In contrast, power-of-$d$ or JSQ($d$) schemes that assign an incoming task to a server with the shortest queue among $d$ servers selected uniformly at random require little communication, but lead to constant delays. In order to examine this fundamental trade-off between delay performance and implementation overhead, we consider JSQ($d(N)$) schemes where the diversity parameter $d(N)$ depends on $N$ and investigate what growth rate of $d(N)$ is required to asymptotically match the optimal JSQ performance on fluid and diffusion scale. Stochastic coupling techniques and stochastic-process limits play an instrumental role in establishing the asymptotic optimality. We demonstrate how this methodology carries over to infinite-server settings, finite buffers, multiple dispatchers, servers arranged on graph topologies, and token-based load balancing including the popular Join-the-Idle-Queue (JIQ) scheme. In this way we provide a broad overview of the many recent advances in the field. This survey extends the short review presented at ICM 2018 (arXiv:1712.08555). △ Less

Submitted 4 November, 2021; v1 submitted 14 June, 2018; originally announced June 2018.

Comments: To appear in SIAM Review. arXiv admin note: substantial text overlap with arXiv:1712.08555

Journal ref: SIAM Rev. 64 3 (2022) 554-622

Join-Idle-Queue with Service Elasticity: Large-Scale Asymptotics of a Non-monotone System

Authors: Debankur Mukherjee, Alexander Stolyar

Abstract: We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17, arXiv:1703.08373), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work,… ▽ More We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17, arXiv:1703.08373), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability. △ Less

Submitted 20 March, 2018; originally announced March 2018.

Comments: 30 pages

Journal ref: Stoch. Syst. 9 4 (2019)

Scalable Load Balancing in Networked Systems: Universality Properties and Stochastic Coupling Methods

Authors: Mark van der Boor, Sem C. Borst, Johan S. H. van Leeuwaarden, Debankur Mukherjee

Abstract: We present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of $N$ single-server… ▽ More We present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of $N$ single-server queues. A popular class of load balancing algorithms are so-called power-of-$d$ or JSQ($d$) policies, where an incoming task is assigned to a server with the shortest queue among $d$ servers selected uniformly at random. This class includes the Join-the-Shortest-Queue (JSQ) policy as a special case ($d = N$), which has strong stochastic optimality properties and yields a mean waiting time that vanishes as $N$ grows large for any fixed subcritical load. However, a nominal implementation of the JSQ policy involves a prohibitive communication burden in large-scale deployments. In contrast, a random assignment policy ($d = 1$) does not entail any communication overhead, but the mean waiting time remains constant as $N$ grows large for any fixed positive load. In order to examine the fundamental trade-off between performance and implementation overhead, we consider an asymptotic regime where $d(N)$ depends on $N$. We investigate what growth rate of $d(N)$ is required to match the performance of the JSQ policy on fluid and diffusion scale. The results demonstrate that the asymptotics for the JSQ($d(N)$) policy are insensitive to the exact growth rate of $d(N)$, as long as the latter is sufficiently fast, implying that the optimality of the JSQ policy can asymptotically be preserved while dramatically reducing the communication overhead. We additionally show how the communication overhead can be reduced yet further by the so-called Join-the-Idle-Queue scheme, leveraging memory at the dispatcher. △ Less

Submitted 22 December, 2017; originally announced December 2017.

Comments: Survey paper. Contribution to the Proceedings of the ICM 2018

Asymptotically Optimal Load Balancing Topologies

Authors: Debankur Mukherjee, Sem C. Borst, Johan S. H. van Leeuwaarden

Abstract: We consider a system of $N$ servers inter-connected by some underlying graph topology $G_N$. Tasks arrive at the various servers as independent Poisson processes of rate $λ$. Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in $G_N$. Tasks have unit-mean exponential service times and leave the system up… ▽ More We consider a system of $N$ servers inter-connected by some underlying graph topology $G_N$. Tasks arrive at the various servers as independent Poisson processes of rate $λ$. Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in $G_N$. Tasks have unit-mean exponential service times and leave the system upon service completion. The above model has been extensively investigated in the case $G_N$ is a clique. Since the servers are exchangeable in that case, the queue length process is quite tractable, and it has been proved that for any $λ< 1$, the fraction of servers with two or more tasks vanishes in the limit as $N \to \infty$. For an arbitrary graph $G_N$, the lack of exchangeability severely complicates the analysis, and the queue length process tends to be worse than for a clique. Accordingly, a graph $G_N$ is said to be $N$-optimal or $\sqrt{N}$-optimal when the occupancy process on $G_N$ is equivalent to that on a clique on an $N$-scale or $\sqrt{N}$-scale, respectively. We prove that if $G_N$ is an Erdős-Rényi random graph with average degree $d(N)$, then it is with high probability $N$-optimal and $\sqrt{N}$-optimal if $d(N) \to \infty$ and $d(N) / (\sqrt{N} \log(N)) \to \infty$ as $N \to \infty$, respectively. This demonstrates that optimality can be maintained at $N$-scale and $\sqrt{N}$-scale while reducing the number of connections by nearly a factor $N$ and $\sqrt{N} / \log(N)$ compared to a clique, provided the topology is suitably random. It is further shown that if $G_N$ contains $Θ(N)$ bounded-degree nodes, then it cannot be $N$-optimal. In addition, we establish that an arbitrary graph $G_N$ is $N$-optimal when its minimum degree is $N - o(N)$, and may not be $N$-optimal even when its minimum degree is $c N + o(N)$ for any $0 < c < 1/2$. △ Less

Submitted 6 April, 2019; v1 submitted 18 July, 2017; originally announced July 2017.

Comments: A few relevant results from arXiv:1612.00723 are included for convenience

Journal ref: Proc. ACM Meas. Anal. Comput. Syst. 2 1 (2018)

Optimal Service Elasticity in Large-Scale Distributed Systems

Authors: Debankur Mukherjee, Souvik Dhara, Sem Borst, Johan S. H. van Leeuwaarden

Abstract: A fundamental challenge in large-scale cloud networks and data centers is to achieve highly efficient server utilization and limit energy consumption, while providing excellent user-perceived performance in the presence of uncertain and time-varying demand patterns. Auto-scaling provides a popular paradigm for automatically adjusting service capacity in response to demand while meeting performance… ▽ More A fundamental challenge in large-scale cloud networks and data centers is to achieve highly efficient server utilization and limit energy consumption, while providing excellent user-perceived performance in the presence of uncertain and time-varying demand patterns. Auto-scaling provides a popular paradigm for automatically adjusting service capacity in response to demand while meeting performance targets, and queue-driven auto-scaling techniques have been widely investigated in the literature. In typical data center architectures and cloud environments however, no centralized queue is maintained, and load balancing algorithms immediately distribute incoming tasks among parallel queues. In these distributed settings with vast numbers of servers, centralized queue-driven auto-scaling techniques involve a substantial communication overhead and major implementation burden, or may not even be viable at all. Motivated by the above issues, we propose a joint auto-scaling and load balancing scheme which does not require any global queue length information or explicit knowledge of system parameters, and yet provides provably near-optimal service elasticity. We establish the fluid-level dynamics for the proposed scheme in a regime where the total traffic volume and nominal service capacity grow large in proportion. The fluid-limit results show that the proposed scheme achieves asymptotic optimality in terms of user-perceived delay performance as well as energy consumption. Specifically, we prove that both the waiting time of tasks and the relative energy portion consumed by idle servers vanish in the limit. At the same time, the proposed scheme operates in a distributed fashion and involves only constant communication overhead per task, thus ensuring scalability in massive data center operations. △ Less

Submitted 24 March, 2017; originally announced March 2017.

Comments: Accepted in ACM SIGMETRICS, Urbana-Champaign, Illinois, USA, 2017

Journal ref: Proc. ACM Meas. Anal. Comput. Syst. 1 1 (2017)

Phase transitions of extremal cuts for the configuration model

Authors: Souvik Dhara, Debankur Mukherjee, Subhabrata Sen

Abstract: The $k$-section width and the Max-Cut for the configuration model are shown to exhibit phase transitions according to the values of certain parameters of the asymptotic degree distribution. These transitions mirror those observed on Erdős-Rényi random graphs, established by Luczak and McDiarmid (2001), and Coppersmith et al. (2004), respectively. The $k$-section width and the Max-Cut for the configuration model are shown to exhibit phase transitions according to the values of certain parameters of the asymptotic degree distribution. These transitions mirror those observed on Erdős-Rényi random graphs, established by Luczak and McDiarmid (2001), and Coppersmith et al. (2004), respectively. △ Less

Submitted 16 October, 2017; v1 submitted 9 November, 2016; originally announced November 2016.

MSC Class: 05C80; 68R10; 68Q87

Journal ref: Electron.J.Probab. 22 1 (2017)

Independent Set Reconfiguration Thresholds of Hereditary Graph Classes

Authors: Mark de Berg, Bart M. P. Jansen, Debankur Mukherjee

Abstract: Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps that preserve feasibility of the intermediate solutions. In this paper, rather than asking this question from an algorithmic perspective, we analyze the combinatorial structure behind it. We consider the problem of reconfi… ▽ More Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps that preserve feasibility of the intermediate solutions. In this paper, rather than asking this question from an algorithmic perspective, we analyze the combinatorial structure behind it. We consider the problem of reconfiguring one independent set into another, using two different processes: (1) exchanging exactly $k$ vertices in each step, or (2) removing or adding one vertex in each step while ensuring the intermediate sets contain at most $k$ fewer vertices than the initial solution. We are interested in determining the minimum value of $k$ for which this reconfiguration is possible, and bound these threshold values in terms of several structural graph parameters. For hereditary graph classes we identify structures that cause the reconfiguration threshold to be large. △ Less

Submitted 12 October, 2016; originally announced October 2016.

Comments: 31 pages, 3 figures, accepted in 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2016

ACM Class: G.2.1

Journal ref: Discrete.Appl.Math. 250 (2018) 165-182

Testing for Characteristics of Attribute Linked Infinite Networks based on Small Samples

Authors: Koushiki Sarkar, Diganta Mukherjee

Abstract: The objective of this paper is to study the characteristics (geometric and otherwise) of very large attribute based undirected networks. Real-world networks are often very large and fast evolving. Their analysis and understanding present a great challenge. An Attribute based network is a graph in which the edges depend on certain properties of the vertices on which they are incident. In context of… ▽ More The objective of this paper is to study the characteristics (geometric and otherwise) of very large attribute based undirected networks. Real-world networks are often very large and fast evolving. Their analysis and understanding present a great challenge. An Attribute based network is a graph in which the edges depend on certain properties of the vertices on which they are incident. In context of a social network, the existence of links between two individuals may depend on certain attributes of the two of them. We use the Lovasz type sampling strategy of observing a certain random process on a graph locally , i.e., in the neighborhood of a node, and deriving information about global properties of the graph. The corresponding adjacency matrix is our primary object of interest. We study the efficiency of recently proposed sampling strategies, modified to our set up, to estimate the degree distribution, centrality measures, planarity etc. The limiting distributions are derived using recently developed probabilistic techniques for random matrices and hence we devise relevant test statistics and confidence intervals for different parameters / hypotheses of interest. We hope that our work will be useful for social and computer scientists for designing sampling strategies and computational algorithms appropriate to their respective domains of inquiry. Extensive simulations studies are done to empirically verify the probabilistic statements made in the paper. △ Less

Submitted 4 October, 2015; originally announced October 2015.

Comments: Working Paper (To be presented in LSCNA, in conjunction with IEEE ANTS, ISI Kolkata)