Search

Deep learning models have achieved great success in automating skin lesion diagnosis. However, the ethnic disparity in these models' predictions needs to be addressed before deploying them. We introduce a novel approach, PatchAlign, to enhance skin condition image classification accuracy and fairness by aligning with clinical text representations of skin conditions. PatchAlign uses Graph Optimal Transport (GOT) Loss as a regularizer to perform cross-domain alignment. The representations obtained are robust and generalize well across skin tones, even with limited training samples. To reduce the effect of noise and artifacts in clinical dermatology images, we propose a learnable Masked Graph Optimal Transport for cross-domain alignment that further improves fairness metrics. We compare our model to the state-of-the-art FairDisCo on two skin lesion datasets with different skin types: Fitzpatrick17k and Diverse Dermatology Images (DDI). PatchAlign enhances the accuracy of skin condition image classification by 2.8% (in-domain) and 6.2% (out-domain) on Fitzpatrick17k, and 4.2% (in-domain) on DDI compared to FairDisCo. Additionally, it consistently improves the fairness of true positive rates across skin tones. The source code for the implementation is available at the following GitHub repository: https://github.com/aayushmanace/PatchAlign24, enabling easy reproduction and further experimentation., Comment: MICCAI 2024. Early Accept Paper (amongst the top 11% of 2869 papers submitted)

In this work, we propose a novel dimensionality reduction technique, DiffRed, which first projects the data matrix, A, along first $k_1$ principal components and the residual matrix $A^{*}$ (left after subtracting its $k_1$-rank approximation) along $k_2$ Gaussian random vectors. We evaluate M1, the distortion of mean-squared pair-wise distance, and Stress, the normalized value of RMS of distortion of the pairwise distances. We rigorously prove that DiffRed achieves a general upper bound of $O\left(\sqrt{\frac{1-p}{k_2}}\right)$ on Stress and $O\left(\frac{(1-p)}{\sqrt{k_2*\rho(A^{*})}}\right)$ on M1 where $p$ is the fraction of variance explained by the first $k_1$ principal components and $\rho(A^{*})$ is the stable rank of $A^{*}$. These bounds are tighter than the currently known results for Random maps. Our extensive experiments on a variety of real-world datasets demonstrate that DiffRed achieves near zero M1 and much lower values of Stress as compared to the well-known dimensionality reduction techniques. In particular, DiffRed can map a 6 million dimensional dataset to 10 dimensions with 54% lower Stress than PCA.

Several distributed frameworks have been developed to scale Graph Neural Networks (GNNs) on billion-size graphs. On several benchmarks, we observe that the graph partitions generated by these frameworks have heterogeneous data distributions and class imbalance, affecting convergence, and resulting in lower performance than centralized implementations. We holistically address these challenges and develop techniques that reduce training time and improve accuracy. We develop an Edge-Weighted partitioning technique to improve the micro average F1 score (accuracy) by minimizing the total entropy. Furthermore, we add an asynchronous personalization phase that adapts each compute-host's model to its local data distribution. We design a class-balanced sampler that considerably speeds up convergence. We implemented our algorithms on the DistDGL framework and observed that our training techniques scale much better than the existing training approach. We achieved a (2-3x) speedup in training time and 4\% improvement on average in micro-F1 scores on 5 large graph benchmarks compared to the standard baselines., Comment: 8 pages, 3 figures, 5 tables, accepted at ICDM'23

The traditional framework of federated learning (FL) requires each client to re-train their models in every iteration, making it infeasible for resource-constrained mobile devices to train deep-learning (DL) models. Split learning (SL) provides an alternative by using a centralized server to offload the computation of activations and gradients for a subset of the model but suffers from problems of slow convergence and lower accuracy. In this paper, we implement PFSL, a new framework of distributed split learning where a large number of thin clients perform transfer learning in parallel, starting with a pre-trained DL model without sharing their data or labels with a central server. We implement a lightweight step of personalization of client models to provide high performance for their respective data distributions. Furthermore, we evaluate performance fairness amongst clients under a work fairness constraint for various scenarios of non-i.i.d. data distributions and unequal sample sizes. Our accuracy far exceeds that of current SL algorithms and is very close to that of centralized learning on several real-life benchmarks. It has a very low computation cost compared to FL variants and promises to deliver the full benefits of DL to extremely thin, resource-constrained clients., Comment: To be published in : THE 23RD IEEE/ACM INTERNATIONAL SYMPOSIUM ON Cluster, Cloud and Internet Computing. Granted: Open Research Objects (ORO) and Research Objects Reviewed (ROR) badges. See https://www.niso.org/publications/rp-31-2021-badging for definitions of the badges. Code available at: https://github.com/mnswdhw/PFSL

In today's modern digital world, we have a number of online Question and Answer platforms like Stack Exchange, Quora, and GFG that serve as a medium for people to communicate and help each other. In this paper, we analyzed the effectiveness of Stack Overflow in helping newbies to programming. Every user on this platform goes through a journey. For the first 12 months, we consider them to be a newbie. Post 12 months they come under one of the following categories: Experienced, Lurkers, or Inquisitive. Each question asked has tags assigned to it and we observe that questions with some specific tags have a faster response time indicating an active community in that field over others. The platform had a steady growth up to 2013 after which it started declining, but recently during the pandemic 2020, we can see rejuvenated activity on the platform., Comment: 12 pages, International Conference on Sustainable Future: Innovations in Education

Computer architecture design space is vast and complex. Tools are needed to explore new ideas and gain insights quickly, with low efforts and at a desired accuracy. We propose Calipers, a criticality-based framework to model key abstractions of complex architectures and a program's execution using dynamic event-dependence graphs. By applying graph algorithms, Calipers can track instruction and event dependencies, compute critical paths, and analyze architecture bottlenecks. By manipulating the graph, Calipers enables architects to investigate a wide range of Instruction Set Architecture (ISA) and microarchitecture design choices/"what-if" scenarios during both early- and late-stage design space exploration without recompiling and rerunning the program. Calipers can model in-order and out-of-order microarchitectures, structural hazards, and different types of ISAs, and can evaluate multiple ideas in a single run. Modeling algorithms are described in detail. We apply Calipers to explore and gain insights in complex microarchitectural and ISA ideas for RISC and EDGE processors, at lower effort than cycle-accurate simulators and with comparable accuracy. For example, among a variety of investigations presented in the paper, experiments show that targeting only a fraction of critical loads can help realize most benefits of value prediction.

With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.

Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1)) ln(m) (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1)) ln(m) + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.

Innovation in hardware is slowing due to rising costs of chip design and diminishing benefits from Moore's law and Dennard scaling. Software innovation, on the other hand, is flourishing, helped in good measure by a thriving open-source ecosystem. We believe that open source can similarly help hardware innovation, but has not yet due to several reasons. We identify these reasons and how the industry, academia, and the hardware community at large can come together to address them., Comment: To appear in IEEE Computer. IEEE copyright notice, and DOI to be added. 7 pages, 5 figures

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop traffic and the one-hop interference model. The objective is twofold: 1) maximizing the throughput when the flow sources continuously inject packets into the network, and 2) minimizing the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we propose a novel Node-based Service-Balanced (NSB) online scheduling algorithm. NSB aims to give scheduling opportunities to heavily congested nodes in a balanced manner, by maximizing the total weight of the scheduled nodes in each scheduling cycle, where the weight of a node is determined by its workload and whether the node was scheduled in the previous scheduling cycle(s). We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results., Comment: This paper was accepted for publication in IEEE Transactions on Mobile Computing. A preliminary version of the paper was presented at IEEE INFOCOM 2016

In this paper, we study the scheduling problem for downlink transmission in a multi-channel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general non-asymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of $O(n^{2.5} \log n)$, where $n$ is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of $O(n^5)$. Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results., Comment: Accepted for publication by the IEEE/ACM Transactions on Networking. arXiv admin note: text overlap with arXiv:1212.1638

In this paper, we focus on the scheduling problem in multi-channel wireless networks, e.g., the downlink of a single cell in fourth generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of $O(n^{2.5} \log n)$-complexity hybrid scheduling policies are recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a \lower complexity $2n^2+2n$, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, we show that the rate-function attained by D-SSG for any delay-violation threshold $b$, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold $b-1$. Thus, we are able to achieve a reduction in complexity (from $O(n^{2.5} \log n)$ of the hybrid policies to $2n^2 + 2n$) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the $O(\cdot)$ notation. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that D-SSG not only guarantees a near-optimal rate-function, but also empirically is virtually indistinguishable from delay-optimal policies., Comment: Accepted for publication by the IEEE/ACM Transactions on Networking, February 2014. A preliminary version of this work was presented at IEEE INFOCOM 2013, Turin, Italy, April 2013

This paper proposes a new class of online policies for scheduling in input-buffered crossbar switches. Our policies are throughput optimal for a large class of arrival processes which satisfy strong-law of large numbers. Given an initial configuration and no further arrivals, our policies drain all packets in the system in the minimal amount of time (providing an online alternative to the batch approach based on Birkhoff-VonNeumann decompositions). We show that it is possible for policies in our class to be throughput optimal even if they are not constrained to be maximal in every time slot. Most algorithms for switch scheduling take an edge based approach; in contrast, we focus on scheduling (a large enough set of) the most congested ports. This alternate approach allows for lower-complexity algorithms, and also requires a non-standard technique to prove throughput-optimality. One algorithm in our class, Maximum Vertex-weighted Matching (MVM) has worst-case complexity similar to Max-size Matching, and in simulations shows slightly better delay performance than Max-(edge)weighted-Matching (MWM)., Comment: To appear in Sigmetrics 2009