Showing 1–35 of 35 results for author: Ko, K

VideoMamba: Spatio-Temporal Selective State Space Model

Authors: Jinyoung Park, Hee-Seon Kim, Kangwook Ko, Minbeom Kim, Changick Kim

Abstract: We introduce VideoMamba, a novel adaptation of the pure Mamba architecture, specifically designed for video recognition. Unlike transformers that rely on self-attention mechanisms leading to high computational costs by quadratic complexity, VideoMamba leverages Mamba's linear complexity and selective SSM mechanism for more efficient processing. The proposed Spatio-Temporal Forward and Backward SSM… ▽ More We introduce VideoMamba, a novel adaptation of the pure Mamba architecture, specifically designed for video recognition. Unlike transformers that rely on self-attention mechanisms leading to high computational costs by quadratic complexity, VideoMamba leverages Mamba's linear complexity and selective SSM mechanism for more efficient processing. The proposed Spatio-Temporal Forward and Backward SSM allows the model to effectively capture the complex relationship between non-sequential spatial and sequential temporal information in video. Consequently, VideoMamba is not only resource-efficient but also effective in capturing long-range dependency in videos, demonstrated by competitive performance and outstanding efficiency on a variety of video understanding benchmarks. Our work highlights the potential of VideoMamba as a powerful tool for video understanding, offering a simple yet effective baseline for future research in video analysis. △ Less

Submitted 11 July, 2024; originally announced July 2024.

Comments: ECCV 2024. code available at http://github.com/jinyjelly/VideoMamba

MR-RawNet: Speaker verification system with multiple temporal resolutions for variable duration utterances using raw waveforms

Authors: Seung-bin Kim, Chan-yeong Lim, Jungwoo Heo, Ju-ho Kim, Hyun-seo Shin, Kyo-Won Koo, Ha-Jin Yu

Abstract: In speaker verification systems, the utilization of short utterances presents a persistent challenge, leading to performance degradation primarily due to insufficient phonetic information to characterize the speakers. To overcome this obstacle, we propose a novel structure, MR-RawNet, designed to enhance the robustness of speaker verification systems against variable duration utterances using raw… ▽ More In speaker verification systems, the utilization of short utterances presents a persistent challenge, leading to performance degradation primarily due to insufficient phonetic information to characterize the speakers. To overcome this obstacle, we propose a novel structure, MR-RawNet, designed to enhance the robustness of speaker verification systems against variable duration utterances using raw waveforms. The MR-RawNet extracts time-frequency representations from raw waveforms via a multi-resolution feature extractor that optimally adjusts both temporal and spectral resolutions simultaneously. Furthermore, we apply a multi-resolution attention block that focuses on diverse and extensive temporal contexts, ensuring robustness against changes in utterance length. The experimental results, conducted on VoxCeleb1 dataset, demonstrate that the MR-RawNet exhibits superior performance in handling utterances of variable duration compared to other raw waveform-based systems. △ Less

Submitted 11 June, 2024; originally announced June 2024.

Comments: 5 pages, accepted by Interspeech 2024

Confidence-Aware Sub-Structure Beam Search (CABS): Mitigating Hallucination in Structured Data Generation with Large Language Models

Authors: Chengwei Wei, Kee Kiat Koo, Amir Tavanaei, Karim Bouyarmane

Abstract: Large Language Models (LLMs) have facilitated structured data generation, with applications in domains like tabular data, document databases, product catalogs, etc. However, concerns persist about generation veracity due to incorrect references or hallucinations, necessitating the incorporation of some form of model confidence for mitigation. Existing confidence estimation methods on LLM generatio… ▽ More Large Language Models (LLMs) have facilitated structured data generation, with applications in domains like tabular data, document databases, product catalogs, etc. However, concerns persist about generation veracity due to incorrect references or hallucinations, necessitating the incorporation of some form of model confidence for mitigation. Existing confidence estimation methods on LLM generations primarily focus on the confidence at the individual token level or the entire output sequence level, limiting their applicability to structured data generation, which consists of an intricate mix of both independent and correlated entries at the sub-structure level. In this paper, we first investigate confidence estimation methods for generated sub-structure-level data. We introduce the concept of Confidence Network that applies on the hidden state of the LLM transformer, as a more targeted estimate than the traditional token conditional probability. We further propose Confidence-Aware sub-structure Beam Search (CABS), a novel decoding method operating at the sub-structure level in structured data generation. CABS enhances the faithfulness of structured data generation by considering confidence scores from the Confidence Network for each sub-structure-level data and iteratively refining the prompts. Results show that CABS outperforms traditional token-level beam search for structured data generation by 16.7% Recall at 90% precision averagely on the problem of product attribute generation. △ Less

Submitted 30 May, 2024; originally announced June 2024.

Signing in Four Public Software Package Registries: Quantity, Quality, and Influencing Factors

Authors: Taylor R Schorlemmer, Kelechi G Kalu, Luke Chigges, Kyung Myung Ko, Eman Abu Isghair, Saurabh Baghi, Santiago Torres-Arias, James C Davis

Abstract: Many software applications incorporate open-source third-party packages distributed by public package registries. Guaranteeing authorship along this supply chain is a challenge. Package maintainers can guarantee package authorship through software signing. However, it is unclear how common this practice is, and whether the resulting signatures are created properly. Prior work has provided raw data… ▽ More Many software applications incorporate open-source third-party packages distributed by public package registries. Guaranteeing authorship along this supply chain is a challenge. Package maintainers can guarantee package authorship through software signing. However, it is unclear how common this practice is, and whether the resulting signatures are created properly. Prior work has provided raw data on registry signing practices, but only measured single platforms, did not consider quality, did not consider time, and did not assess factors that may influence signing. We do not have up-to-date measurements of signing practices nor do we know the quality of existing signatures. Furthermore, we lack a comprehensive understanding of factors that influence signing adoption. This study addresses this gap. We provide measurements across three kinds of package registries: traditional software (Maven, PyPI), container images (DockerHub), and machine learning models (Hugging Face). For each registry, we describe the nature of the signed artifacts as well as the current quantity and quality of signatures. Then, we examine longitudinal trends in signing practices. Finally, we use a quasi-experiment to estimate the effect that various factors had on software signing practices. To summarize our findings: (1) mandating signature adoption improves the quantity of signatures; (2) providing dedicated tooling improves the quality of signing; (3) getting started is the hard part -- once a maintainer begins to sign, they tend to continue doing so; and (4) although many supply chain attacks are mitigable via signing, signing adoption is primarily affected by registry policy rather than by public knowledge of attacks, new engineering standards, etc. These findings highlight the importance of software package registry managers and signing infrastructure. △ Less

Submitted 14 April, 2024; v1 submitted 25 January, 2024; originally announced January 2024.

Comments: Accepted at IEEE Security & Privacy 2024 (S&P'24)

ZIGNeRF: Zero-shot 3D Scene Representation with Invertible Generative Neural Radiance Fields

Authors: Kanghyeok Ko, Minhyeok Lee

Abstract: Generative Neural Radiance Fields (NeRFs) have demonstrated remarkable proficiency in synthesizing multi-view images by learning the distribution of a set of unposed images. Despite the aptitude of existing generative NeRFs in generating 3D-consistent high-quality random samples within data distribution, the creation of a 3D representation of a singular input image remains a formidable challenge.… ▽ More Generative Neural Radiance Fields (NeRFs) have demonstrated remarkable proficiency in synthesizing multi-view images by learning the distribution of a set of unposed images. Despite the aptitude of existing generative NeRFs in generating 3D-consistent high-quality random samples within data distribution, the creation of a 3D representation of a singular input image remains a formidable challenge. In this manuscript, we introduce ZIGNeRF, an innovative model that executes zero-shot Generative Adversarial Network (GAN) inversion for the generation of multi-view images from a single out-of-domain image. The model is underpinned by a novel inverter that maps out-of-domain images into the latent code of the generator manifold. Notably, ZIGNeRF is capable of disentangling the object from the background and executing 3D operations such as 360-degree rotation or depth and horizontal translation. The efficacy of our model is validated using multiple real-image datasets: Cats, AFHQ, CelebA, CelebA-HQ, and CompCars. △ Less

Submitted 5 June, 2023; originally announced June 2023.

TypeScript's Evolution: An Analysis of Feature Adoption Over Time

Authors: Joshua D. Scarsbrook, Mark Utting, Ryan K. L. Ko

Abstract: TypeScript is a quickly evolving superset of JavaScript with active development of new features. Our paper seeks to understand how quickly these features are adopted by the developer community. Existing work in JavaScript shows the adoption of dynamic language features can be a major hindrance to static analysis. As TypeScript evolves the addition of features makes the underlying standard more and… ▽ More TypeScript is a quickly evolving superset of JavaScript with active development of new features. Our paper seeks to understand how quickly these features are adopted by the developer community. Existing work in JavaScript shows the adoption of dynamic language features can be a major hindrance to static analysis. As TypeScript evolves the addition of features makes the underlying standard more and more difficult to keep up with. In our work we present an analysis of 454 open source TypeScript repositories and study the adoption of 13 language features over the past three years. We show that while new versions of the TypeScript compiler are aggressively adopted by the community, the same cannot be said for language features. While some experience strong growth others are rarely adopted by projects. Our work serves as a starting point for future study of the adoption of features in TypeScript. We also release our analysis and data gathering software as open source in the hope it helps the programming languages community. △ Less

Submitted 17 March, 2023; originally announced March 2023.

Backward Curriculum Reinforcement Learning

Authors: KyungMin Ko

Abstract: Current reinforcement learning algorithms train an agent using forward-generated trajectories, which provide little guidance so that the agent can explore as much as possible. While realizing the value of reinforcement learning results from sufficient exploration, this approach leads to a trade-off in losing sample efficiency, an essential factor impacting algorithm performance. Previous tasks use… ▽ More Current reinforcement learning algorithms train an agent using forward-generated trajectories, which provide little guidance so that the agent can explore as much as possible. While realizing the value of reinforcement learning results from sufficient exploration, this approach leads to a trade-off in losing sample efficiency, an essential factor impacting algorithm performance. Previous tasks use reward-shaping techniques and network structure modification to increase sample efficiency. However, these methods require many steps to implement. In this work, we propose novel backward curriculum reinforcement learning that begins training the agent using the backward trajectory of the episode instead of the original forward trajectory. This approach provides the agent with a strong reward signal, enabling more sample-efficient learning. Moreover, our method only requires a minor change in the algorithm of reversing the order of the trajectory before agent training, allowing a straightforward application to any state-of-the-art algorithm. △ Less

Submitted 4 September, 2023; v1 submitted 29 December, 2022; originally announced December 2022.

Comments: In the proceedings of the 32nd IEEE International Conference on Robot and Human Interactive Communication (IEEE RO-MAN 2023)

Single Cell Training on Architecture Search for Image Denoising

Authors: Bokyeung Lee, Kyungdeuk Ko, Jonghwan Hong, Hanseok Ko

Abstract: Neural Architecture Search (NAS) for automatically finding the optimal network architecture has shown some success with competitive performances in various computer vision tasks. However, NAS in general requires a tremendous amount of computations. Thus reducing computational cost has emerged as an important issue. Most of the attempts so far has been based on manual approaches, and often the arch… ▽ More Neural Architecture Search (NAS) for automatically finding the optimal network architecture has shown some success with competitive performances in various computer vision tasks. However, NAS in general requires a tremendous amount of computations. Thus reducing computational cost has emerged as an important issue. Most of the attempts so far has been based on manual approaches, and often the architectures developed from such efforts dwell in the balance of the network optimality and the search cost. Additionally, recent NAS methods for image restoration generally do not consider dynamic operations that may transform dimensions of feature maps because of the dimensionality mismatch in tensor calculations. This can greatly limit NAS in its search for optimal network structure. To address these issues, we re-frame the optimal search problem by focusing at component block level. From previous work, it's been shown that an effective denoising block can be connected in series to further improve the network performance. By focusing at block level, the search space of reinforcement learning becomes significantly smaller and evaluation process can be conducted more rapidly. In addition, we integrate an innovative dimension matching modules for dealing with spatial and channel-wise mismatch that may occur in the optimal design search. This allows much flexibility in optimal network search within the cell block. With these modules, then we employ reinforcement learning in search of an optimal image denoising network at a module level. Computational efficiency of our proposed Denoising Prior Neural Architecture Search (DPNAS) was demonstrated by having it complete an optimal architecture search for an image restoration task by just one day with a single GPU. △ Less

Submitted 12 December, 2022; originally announced December 2022.

Discriminatory and orthogonal feature learning for noise robust keyword spotting

Authors: Donghyeon Kim, Kyungdeuk Ko, David K. Han, Hanseok Ko

Abstract: Keyword Spotting (KWS) is an essential component in a smart device for alerting the system when a user prompts it with a command. As these devices are typically constrained by computational and energy resources, the KWS model should be designed with a small footprint. In our previous work, we developed lightweight dynamic filters which extract a robust feature map within a noisy environment. The l… ▽ More Keyword Spotting (KWS) is an essential component in a smart device for alerting the system when a user prompts it with a command. As these devices are typically constrained by computational and energy resources, the KWS model should be designed with a small footprint. In our previous work, we developed lightweight dynamic filters which extract a robust feature map within a noisy environment. The learning variables of the dynamic filter are jointly optimized with KWS weights by using Cross-Entropy (CE) loss. CE loss alone, however, is not sufficient for high performance when the SNR is low. In order to train the network for more robust performance in noisy environments, we introduce the LOw Variant Orthogonal (LOVO) loss. The LOVO loss is composed of a triplet loss applied on the output of the dynamic filter, a spectral norm-based orthogonal loss, and an inner class distance loss applied in the KWS model. These losses are particularly useful in encouraging the network to extract discriminatory features in unseen noise environments. △ Less

Submitted 20 October, 2022; originally announced October 2022.

Comments: Published in SPL

Positive-Unlabeled Learning using Random Forests via Recursive Greedy Risk Minimization

Authors: Jonathan Wilton, Abigail M. Y. Koay, Ryan K. L. Ko, Miao Xu, Nan Ye

Abstract: The need to learn from positive and unlabeled data, or PU learning, arises in many applications and has attracted increasing interest. While random forests are known to perform well on many tasks with positive and negative data, recent PU algorithms are generally based on deep neural networks, and the potential of tree-based PU learning is under-explored. In this paper, we propose new random fores… ▽ More The need to learn from positive and unlabeled data, or PU learning, arises in many applications and has attracted increasing interest. While random forests are known to perform well on many tasks with positive and negative data, recent PU algorithms are generally based on deep neural networks, and the potential of tree-based PU learning is under-explored. In this paper, we propose new random forest algorithms for PU-learning. Key to our approach is a new interpretation of decision tree algorithms for positive and negative data as \emph{recursive greedy risk minimization algorithms}. We extend this perspective to the PU setting to develop new decision tree learning algorithms that directly minimizes PU-data based estimators for the expected risk. This allows us to develop an efficient PU random forest algorithm, PU extra trees. Our approach features three desirable properties: it is robust to the choice of the loss function in the sense that various loss functions lead to the same decision trees; it requires little hyperparameter tuning as compared to neural network based PU learning; it supports a feature importance that directly measures a feature's contribution to risk minimization. Our algorithms demonstrate strong performance on several datasets. Our code is available at \url{https://github.com/puetpaper/PUExtraTrees}. △ Less

Submitted 16 October, 2022; originally announced October 2022.

Comments: Accepted at NeurIPS 2022

Evaluating histopathology transfer learning with ChampKit

Authors: Jakub R. Kaczmarzyk, Tahsin M. Kurc, Shahira Abousamra, Rajarsi Gupta, Joel H. Saltz, Peter K. Koo

Abstract: Histopathology remains the gold standard for diagnosis of various cancers. Recent advances in computer vision, specifically deep learning, have facilitated the analysis of histopathology images for various tasks, including immune cell detection and microsatellite instability classification. The state-of-the-art for each task often employs base architectures that have been pretrained for image clas… ▽ More Histopathology remains the gold standard for diagnosis of various cancers. Recent advances in computer vision, specifically deep learning, have facilitated the analysis of histopathology images for various tasks, including immune cell detection and microsatellite instability classification. The state-of-the-art for each task often employs base architectures that have been pretrained for image classification on ImageNet. The standard approach to develop classifiers in histopathology tends to focus narrowly on optimizing models for a single task, not considering the aspects of modeling innovations that improve generalization across tasks. Here we present ChampKit (Comprehensive Histopathology Assessment of Model Predictions toolKit): an extensible, fully reproducible benchmarking toolkit that consists of a broad collection of patch-level image classification tasks across different cancers. ChampKit enables a way to systematically document the performance impact of proposed improvements in models and methodology. ChampKit source code and data are freely accessible at https://github.com/kaczmarj/champkit . △ Less

Submitted 14 June, 2022; originally announced June 2022.

Comments: Submitted to NeurIPS 2022 Track on Datasets and Benchmarks. Source code available at https://github.com/kaczmarj/champkit

ACM Class: J.3; I.4.9; D.2.13

Vision Transformer Equipped with Neural Resizer on Facial Expression Recognition Task

Authors: Hyeonbin Hwang, Soyeon Kim, Wei-Jin Park, Jiho Seo, Kyungtae Ko, Hyeon Yeo

Abstract: When it comes to wild conditions, Facial Expression Recognition is often challenged with low-quality data and imbalanced, ambiguous labels. This field has much benefited from CNN based approaches; however, CNN models have structural limitation to see the facial regions in distant. As a remedy, Transformer has been introduced to vision fields with global receptive field, but requires adjusting inpu… ▽ More When it comes to wild conditions, Facial Expression Recognition is often challenged with low-quality data and imbalanced, ambiguous labels. This field has much benefited from CNN based approaches; however, CNN models have structural limitation to see the facial regions in distant. As a remedy, Transformer has been introduced to vision fields with global receptive field, but requires adjusting input spatial size to the pretrained models to enjoy their strong inductive bias at hands. We herein raise a question whether using the deterministic interpolation method is enough to feed low-resolution data to Transformer. In this work, we propose a novel training framework, Neural Resizer, to support Transformer by compensating information and downscaling in a data-driven manner trained with loss function balancing the noisiness and imbalance. Experiments show our Neural Resizer with F-PDLS loss function improves the performance with Transformer variants in general and nearly achieves the state-of-the-art performance. △ Less

Submitted 5 April, 2022; originally announced April 2022.

Comments: Accepted to IEEE ICASSP 2022

Context-Aware Unsupervised Clustering for Person Search

Authors: Byeong-Ju Han, Kuhyeun Ko, Jae-Young Sim

Abstract: The existing person search methods use the annotated labels of person identities to train deep networks in a supervised manner that requires a huge amount of time and effort for human labeling. In this paper, we first introduce a novel framework of person search that is able to train the network in the absence of the person identity labels, and propose efficient unsupervised clustering methods to… ▽ More The existing person search methods use the annotated labels of person identities to train deep networks in a supervised manner that requires a huge amount of time and effort for human labeling. In this paper, we first introduce a novel framework of person search that is able to train the network in the absence of the person identity labels, and propose efficient unsupervised clustering methods to substitute the supervision process using annotated person identity labels. Specifically, we propose a hard negative mining scheme based on the uniqueness property that only a single person has the same identity to a given query person in each image. We also propose a hard positive mining scheme by using the contextual information of co-appearance that neighboring persons in one image tend to appear simultaneously in other images. The experimental results show that the proposed method achieves comparable performance to that of the state-of-the-art supervised person search methods, and furthermore outperforms the extended unsupervised person re-identification methods on the benchmark person search datasets. △ Less

Submitted 4 October, 2021; originally announced October 2021.

IceNet for Interactive Contrast Enhancement

Authors: Keunsoo Ko, Chang-Su Kim

Abstract: A CNN-based interactive contrast enhancement algorithm, called IceNet, is proposed in this work, which enables a user to adjust image contrast easily according to his or her preference. Specifically, a user provides a parameter for controlling the global brightness and two types of scribbles to darken or brighten local regions in an image. Then, given these annotations, IceNet estimates a gamma ma… ▽ More A CNN-based interactive contrast enhancement algorithm, called IceNet, is proposed in this work, which enables a user to adjust image contrast easily according to his or her preference. Specifically, a user provides a parameter for controlling the global brightness and two types of scribbles to darken or brighten local regions in an image. Then, given these annotations, IceNet estimates a gamma map for the pixel-wise gamma correction. Finally, through color restoration, an enhanced image is obtained. The user may provide annotations iteratively to obtain a satisfactory image. IceNet is also capable of producing a personalized enhanced image automatically, which can serve as a basis for further adjustment if so desired. Moreover, to train IceNet effectively and reliably, we propose three differentiable losses. Extensive experiments show that IceNet can provide users with satisfactorily enhanced images. △ Less

Submitted 25 December, 2021; v1 submitted 13 September, 2021; originally announced September 2021.

Comments: 11 pages, 9 figures, 3 tables. This paper has been accepted for publication in IEEE Access. Copyright may change without notice

Confined Gradient Descent: Privacy-preserving Optimization for Federated Learning

Authors: Yanjun Zhang, Guangdong Bai, Xue Li, Surya Nepal, Ryan K L Ko

Abstract: Federated learning enables multiple participants to collaboratively train a model without aggregating the training data. Although the training data are kept within each participant and the local gradients can be securely synthesized, recent studies have shown that such privacy protection is insufficient. The global model parameters that have to be shared for optimization are susceptible to leak in… ▽ More Federated learning enables multiple participants to collaboratively train a model without aggregating the training data. Although the training data are kept within each participant and the local gradients can be securely synthesized, recent studies have shown that such privacy protection is insufficient. The global model parameters that have to be shared for optimization are susceptible to leak information about training data. In this work, we propose Confined Gradient Descent (CGD) that enhances privacy of federated learning by eliminating the sharing of global model parameters. CGD exploits the fact that a gradient descent optimization can start with a set of discrete points and converges to another set at the neighborhood of the global minimum of the objective function. It lets the participants independently train on their local data, and securely share the sum of local gradients to benefit each other. We formally demonstrate CGD's privacy enhancement over traditional FL. We prove that less information is exposed in CGD compared to that of traditional FL. CGD also guarantees desired model accuracy. We theoretically establish a convergence rate for CGD. We prove that the loss of the proprietary models learned for each participant against a model learned by aggregated training data is bounded. Extensive experimental results on two real-world datasets demonstrate the performance of CGD is comparable with the centralized learning, with marginal differences on validation loss (mostly within 0.05) and accuracy (mostly within 1%). △ Less

Submitted 27 April, 2021; originally announced April 2021.

ColdPress: An Extensible Malware Analysis Platform for Threat Intelligence

Authors: Haoxi Tan, Mahin Chandramohan, Cristina Cifuentes, Guangdong Bai, Ryan K. L. Ko

Abstract: Malware analysis is still largely a manual task. This slow and inefficient approach does not scale to the exponential rise in the rate of new unique malware generated. Hence, automating the process as much as possible becomes desirable. In this paper, we present ColdPress - an extensible malware analysis platform that automates the end-to-end process of malware threat intelligence gathering inte… ▽ More Malware analysis is still largely a manual task. This slow and inefficient approach does not scale to the exponential rise in the rate of new unique malware generated. Hence, automating the process as much as possible becomes desirable. In this paper, we present ColdPress - an extensible malware analysis platform that automates the end-to-end process of malware threat intelligence gathering integrated output modules to perform report generation of arbitrary file formats. ColdPress combines state-of-the-art tools and concepts into a modular system that aids the analyst to efficiently and effectively extract information from malware samples. It is designed as a user-friendly and extensible platform that can be easily extended with user-defined modules. We evaluated ColdPress with complex real-world malware samples (e.g., WannaCry), demonstrating its efficiency, performance and usefulness to security analysts. △ Less

Submitted 11 March, 2021; originally announced March 2021.

Comments: The code is open source at https://github.com/uqcyber/ColdPress

A Vision Based Deep Reinforcement Learning Algorithm for UAV Obstacle Avoidance

Authors: Jeremy Roghair, Kyungtae Ko, Amir Ehsan Niaraki Asli, Ali Jannesari

Abstract: Integration of reinforcement learning with unmanned aerial vehicles (UAVs) to achieve autonomous flight has been an active research area in recent years. An important part focuses on obstacle detection and avoidance for UAVs navigating through an environment. Exploration in an unseen environment can be tackled with Deep Q-Network (DQN). However, value exploration with uniform sampling of actions m… ▽ More Integration of reinforcement learning with unmanned aerial vehicles (UAVs) to achieve autonomous flight has been an active research area in recent years. An important part focuses on obstacle detection and avoidance for UAVs navigating through an environment. Exploration in an unseen environment can be tackled with Deep Q-Network (DQN). However, value exploration with uniform sampling of actions may lead to redundant states, where often the environments inherently bear sparse rewards. To resolve this, we present two techniques for improving exploration for UAV obstacle avoidance. The first is a convergence-based approach that uses convergence error to iterate through unexplored actions and temporal threshold to balance exploration and exploitation. The second is a guidance-based approach using a Domain Network which uses a Gaussian mixture distribution to compare previously seen states to a predicted next state in order to select the next action. Performance and evaluation of these approaches were implemented in multiple 3-D simulation environments, with variation in complexity. The proposed approach demonstrates a two-fold improvement in average rewards compared to state of the art. △ Less

Submitted 10 March, 2021; originally announced March 2021.

Comments: 12 pages, 6 figures

An Analytics Framework for Heuristic Inference Attacks against Industrial Control Systems

Authors: Taejun Choi, Guangdong Bai, Ryan K L Ko, Naipeng Dong, Wenlu Zhang, Shunyao Wang

Abstract: Industrial control systems (ICS) of critical infrastructure are increasingly connected to the Internet for remote site management at scale. However, cyber attacks against ICS - especially at the communication channels between humanmachine interface (HMIs) and programmable logic controllers (PLCs) - are increasing at a rate which outstrips the rate of mitigation. In this paper, we introduce a ven… ▽ More Industrial control systems (ICS) of critical infrastructure are increasingly connected to the Internet for remote site management at scale. However, cyber attacks against ICS - especially at the communication channels between humanmachine interface (HMIs) and programmable logic controllers (PLCs) - are increasing at a rate which outstrips the rate of mitigation. In this paper, we introduce a vendor-agnostic analytics framework which allows security researchers to analyse attacks against ICS systems, even if the researchers have zero control automation domain knowledge or are faced with a myriad of heterogenous ICS systems. Unlike existing works that require expertise in domain knowledge and specialised tool usage, our analytics framework does not require prior knowledge about ICS communication protocols, PLCs, and expertise of any network penetration testing tool. Using `digital twin' scenarios comprising industry-representative HMIs, PLCs and firewalls in our test lab, our framework's steps were demonstrated to successfully implement a stealthy deception attack based on false data injection attacks (FDIA). Furthermore, our framework also demonstrated the relative ease of attack dataset collection, and the ability to leverage well-known penetration testing tools. We also introduce the concept of `heuristic inference attacks', a new family of attack types on ICS which is agnostic to PLC and HMI brands/models commonly deployed in ICS. Our experiments were also validated on a separate ICS dataset collected from a cyber-physical scenario of water utilities. Finally, we utilized time complexity theory to estimate the difficulty for the attacker to conduct the proposed packet analyses, and recommended countermeasures based on our findings. △ Less

Submitted 28 January, 2021; originally announced January 2021.

Cyber Autonomy: Automating the Hacker- Self-healing, self-adaptive, automatic cyber defense systems and their impact to the industry, society and national security

Authors: Ryan K L Ko

Abstract: This paper sets the context for the urgency for cyber autonomy, and the current gaps of the cyber security industry. A novel framework proposing four phases of maturity for full cyber autonomy will be discussed. The paper also reviews new and emerging cyber security automation techniques and tools, and discusses their impact on society, the perceived cyber security skills gap/shortage and national… ▽ More This paper sets the context for the urgency for cyber autonomy, and the current gaps of the cyber security industry. A novel framework proposing four phases of maturity for full cyber autonomy will be discussed. The paper also reviews new and emerging cyber security automation techniques and tools, and discusses their impact on society, the perceived cyber security skills gap/shortage and national security. We will also be discussing the delicate balance between national security, human rights and ethics, and the potential demise of the manual penetration testing industry in the face of automation. △ Less

Submitted 8 December, 2020; originally announced December 2020.

Comments: 15 pages, 5 figures, preprint of chapter in edited book "Emerging Technologies and International Security: Machines, the State, and War" edited By Reuben Steff, Joe Burton, Simona R. Soare

ACM Class: I.2.2; I.2.m; K.4.0; K.4.1

Hardness of Approximate Nearest Neighbor Search under L-infinity

Authors: Young Kun Ko, Min Jae Song

Abstract: We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the $\ell_\infty$ norm with two simple reductions. Our first reduction shows that hardness of a special case of the Shortest Vector Problem (SVP), which captures many provably hard instances of SVP, implies a lower bound for ANN with polynomial preprocessing time under the same norm. Combined with a recent quantitative… ▽ More We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the $\ell_\infty$ norm with two simple reductions. Our first reduction shows that hardness of a special case of the Shortest Vector Problem (SVP), which captures many provably hard instances of SVP, implies a lower bound for ANN with polynomial preprocessing time under the same norm. Combined with a recent quantitative hardness result on SVP under $\ell_\infty$ (Bennett et al., FOCS 2017), our reduction implies that finding a $(1+\varepsilon)$-approximate nearest neighbor under $\ell_\infty$ with polynomial preprocessing requires near-linear query time, unless the Strong Exponential Time Hypothesis (SETH) is false. This complements the results of Rubinstein (STOC 2018), who showed hardness of ANN under $\ell_1$, $\ell_2$, and edit distance. Further improving the approximation factor for hardness, we show that, assuming SETH, near-linear query time is required for any approximation factor less than $3$ under $\ell_\infty$. This shows a conditional separation between ANN under the $\ell_1/ \ell_2$ norm and the $\ell_\infty$ norm since there are sublinear time algorithms achieving better than $3$-approximation for the $\ell_1$ and $\ell_2$ norm. Lastly, we show that the approximation factor of $3$ is a barrier for any naive gadget reduction from the Orthogonal Vectors problem. △ Less

Submitted 11 November, 2020; originally announced November 2020.

Comments: 16 pages

Neural Audio Fingerprint for High-specific Audio Retrieval based on Contrastive Learning

Authors: Sungkyun Chang, Donmoon Lee, Jeongsoo Park, Hyungui Lim, Kyogu Lee, Karam Ko, Yoonchang Han

Abstract: Most of existing audio fingerprinting systems have limitations to be used for high-specific audio retrieval at scale. In this work, we generate a low-dimensional representation from a short unit segment of audio, and couple this fingerprint with a fast maximum inner-product search. To this end, we present a contrastive learning framework that derives from the segment-level search objective. Each u… ▽ More Most of existing audio fingerprinting systems have limitations to be used for high-specific audio retrieval at scale. In this work, we generate a low-dimensional representation from a short unit segment of audio, and couple this fingerprint with a fast maximum inner-product search. To this end, we present a contrastive learning framework that derives from the segment-level search objective. Each update in training uses a batch consisting of a set of pseudo labels, randomly selected original samples, and their augmented replicas. These replicas can simulate the degrading effects on original audio signals by applying small time offsets and various types of distortions, such as background noise and room/microphone impulse responses. In the segment-level search task, where the conventional audio fingerprinting systems used to fail, our system using 10x smaller storage has shown promising results. Our code and dataset are available at \url{https://mimbres.github.io/neural-audio-fp/}. △ Less

Submitted 10 February, 2021; v1 submitted 22 October, 2020; originally announced October 2020.

Comments: ICASSP 2021 (accepted)

Pandora: A Cyber Range Environment for the Safe Testing and Deployment of Autonomous Cyber Attack Tools

Authors: Hetong Jiang, Taejun Choi, Ryan K. L. Ko

Abstract: Cybersecurity tools are increasingly automated with artificial intelligent (AI) capabilities to match the exponential scale of attacks, compensate for the relatively slower rate of training new cybersecurity talents, and improve of the accuracy and performance of both tools and users. However, the safe and appropriate usage of autonomous cyber attack tools - especially at the development stages fo… ▽ More Cybersecurity tools are increasingly automated with artificial intelligent (AI) capabilities to match the exponential scale of attacks, compensate for the relatively slower rate of training new cybersecurity talents, and improve of the accuracy and performance of both tools and users. However, the safe and appropriate usage of autonomous cyber attack tools - especially at the development stages for these tools - is still largely an unaddressed gap. Our survey of current literature and tools showed that most of the existing cyber range designs are mostly using manual tools and have not considered augmenting automated tools or the potential security issues caused by the tools. In other words, there is still room for a novel cyber range design which allow security researchers to safely deploy autonomous tools and perform automated tool testing if needed. In this paper, we introduce Pandora, a safe testing environment which allows security researchers and cyber range users to perform experiments on automated cyber attack tools that may have strong potential of usage and at the same time, a strong potential for risks. Unlike existing testbeds and cyber ranges which have direct compatibility with enterprise computer systems and the potential for risk propagation across the enterprise network, our test system is intentionally designed to be incompatible with enterprise real-world computing systems to reduce the risk of attack propagation into actual infrastructure. Our design also provides a tool to convert in-development automated cyber attack tools into to executable test binaries for validation and usage realistic enterprise system environments if required. Our experiments tested automated attack tools on our proposed system to validate the usability of our proposed environment. Our experiments also proved the safety of our environment by compatibility testing using simple malicious code. △ Less

Submitted 24 September, 2020; originally announced September 2020.

Comments: 20 pages, 10 figures, to be published in SSCC 2020

MSC Class: 68M25 ACM Class: D.4.6; D.2.5; K.3

Edge Network-Assisted Real-Time Object Detection Framework for Autonomous Driving

Authors: Seung Wook Kim, Keunsoo Ko, Haneul Ko, Victor C. M. Leung

Abstract: Autonomous vehicles (AVs) can achieve the desired results within a short duration by offloading tasks even requiring high computational power (e.g., object detection (OD)) to edge clouds. However, although edge clouds are exploited, real-time OD cannot always be guaranteed due to dynamic channel quality. To mitigate this problem, we propose an edge network-assisted real-time OD framework~(EODF). I… ▽ More Autonomous vehicles (AVs) can achieve the desired results within a short duration by offloading tasks even requiring high computational power (e.g., object detection (OD)) to edge clouds. However, although edge clouds are exploited, real-time OD cannot always be guaranteed due to dynamic channel quality. To mitigate this problem, we propose an edge network-assisted real-time OD framework~(EODF). In an EODF, AVs extract the region of interests~(RoIs) of the captured image when the channel quality is not sufficiently good for supporting real-time OD. Then, AVs compress the image data on the basis of the RoIs and transmit the compressed one to the edge cloud. In so doing, real-time OD can be achieved owing to the reduced transmission latency. To verify the feasibility of our framework, we evaluate the probability that the results of OD are not received within the inter-frame duration (i.e., outage probability) and their accuracy. From the evaluation, we demonstrate that the proposed EODF provides the results to AVs in real-time and achieves satisfactory accuracy. △ Less

Submitted 17 August, 2020; originally announced August 2020.

Comments: This paper will be published in IEEE Network

BMBC:Bilateral Motion Estimation with Bilateral Cost Volume for Video Interpolation

Authors: Junheum Park, Keunsoo Ko, Chul Lee, Chang-Su Kim

Abstract: Video interpolation increases the temporal resolution of a video sequence by synthesizing intermediate frames between two consecutive frames. We propose a novel deep-learning-based video interpolation algorithm based on bilateral motion estimation. First, we develop the bilateral motion network with the bilateral cost volume to estimate bilateral motions accurately. Then, we approximate bi-directi… ▽ More Video interpolation increases the temporal resolution of a video sequence by synthesizing intermediate frames between two consecutive frames. We propose a novel deep-learning-based video interpolation algorithm based on bilateral motion estimation. First, we develop the bilateral motion network with the bilateral cost volume to estimate bilateral motions accurately. Then, we approximate bi-directional motions to predict a different kind of bilateral motions. We then warp the two input frames using the estimated bilateral motions. Next, we develop the dynamic filter generation network to yield dynamic blending filters. Finally, we combine the warped frames using the dynamic blending filters to generate intermediate frames. Experimental results show that the proposed algorithm outperforms the state-of-the-art video interpolation algorithms on several benchmark datasets. △ Less

Submitted 17 July, 2020; originally announced July 2020.

Comments: Accepted to ECCV 2020

PrivColl: Practical Privacy-Preserving Collaborative Machine Learning

Authors: Yanjun Zhang, Guangdong Bai, Xue Li, Caitlin Curtis, Chen Chen, Ryan K L Ko

Abstract: Collaborative learning enables two or more participants, each with their own training dataset, to collaboratively learn a joint model. It is desirable that the collaboration should not cause the disclosure of either the raw datasets of each individual owner or the local model parameters trained on them. This privacy-preservation requirement has been approached through differential privacy mechanis… ▽ More Collaborative learning enables two or more participants, each with their own training dataset, to collaboratively learn a joint model. It is desirable that the collaboration should not cause the disclosure of either the raw datasets of each individual owner or the local model parameters trained on them. This privacy-preservation requirement has been approached through differential privacy mechanisms, homomorphic encryption (HE) and secure multiparty computation (MPC), but existing attempts may either introduce the loss of model accuracy or imply significant computational and/or communicational overhead. In this work, we address this problem with the lightweight additive secret sharing technique. We propose PrivColl, a framework for protecting local data and local models while ensuring the correctness of training processes. PrivColl employs secret sharing technique for securely evaluating addition operations in a multiparty computation environment, and achieves practicability by employing only the homomorphic addition operations. We formally prove that it guarantees privacy preservation even though the majority (n-2 out of n) of participants are corrupted. With experiments on real-world datasets, we further demonstrate that PrivColl retains high efficiency. It achieves a speedup of more than 45X over the state-of-the-art MPC/HE based schemes for training linear/logistic regression, and 216X faster for training neural network. △ Less

Submitted 14 July, 2020; originally announced July 2020.

Comments: 20 pages, 3 figures, to be published in 25th European Symposium on Research in Computer Security (ESORICS) 2020

Local Editing in LZ-End Compressed Data

Authors: Daniel Roodt, Ulrich Speidel, Vimal Kumar, Ryan K. L. Ko

Abstract: This paper presents an algorithm for the modification of data compressed using LZ-End, a derivate of LZ77, without prior decompression. The performance of the algorithm and the impact of the modifications on the compression ratio is evaluated. Finally, we discuss the importance of this work as a first step towards local editing in Lempel-Ziv compressed data. This paper presents an algorithm for the modification of data compressed using LZ-End, a derivate of LZ77, without prior decompression. The performance of the algorithm and the impact of the modifications on the compression ratio is evaluated. Finally, we discuss the importance of this work as a first step towards local editing in Lempel-Ziv compressed data. △ Less

Submitted 12 July, 2020; originally announced July 2020.

Comments: 12 pages, 1 Figure, 2 Tables

Multi-scale Domain-adversarial Multiple-instance CNN for Cancer Subtype Classification with Unannotated Histopathological Images

Authors: Noriaki Hashimoto, Daisuke Fukushima, Ryoichi Koga, Yusuke Takagi, Kaho Ko, Kei Kohno, Masato Nakaguro, Shigeo Nakamura, Hidekata Hontani, Ichiro Takeuchi

Abstract: We propose a new method for cancer subtype classification from histopathological images, which can automatically detect tumor-specific features in a given whole slide image (WSI). The cancer subtype should be classified by referring to a WSI, i.e., a large-sized image (typically 40,000x40,000 pixels) of an entire pathological tissue slide, which consists of cancer and non-cancer portions. One diff… ▽ More We propose a new method for cancer subtype classification from histopathological images, which can automatically detect tumor-specific features in a given whole slide image (WSI). The cancer subtype should be classified by referring to a WSI, i.e., a large-sized image (typically 40,000x40,000 pixels) of an entire pathological tissue slide, which consists of cancer and non-cancer portions. One difficulty arises from the high cost associated with annotating tumor regions in WSIs. Furthermore, both global and local image features must be extracted from the WSI by changing the magnifications of the image. In addition, the image features should be stably detected against the differences of staining conditions among the hospitals/specimens. In this paper, we develop a new CNN-based cancer subtype classification method by effectively combining multiple-instance, domain adversarial, and multi-scale learning frameworks in order to overcome these practical difficulties. When the proposed method was applied to malignant lymphoma subtype classifications of 196 cases collected from multiple hospitals, the classification performance was significantly better than the standard CNN or other conventional methods, and the accuracy compared favorably with that of standard pathologists. △ Less

Submitted 2 April, 2020; v1 submitted 6 January, 2020; originally announced January 2020.

Comments: Accepted to CVPR2020

ACM Class: I.2.1; I.5.4

An Adaptive Step Toward the Multiphase Conjecture

Authors: Young Kun Ko, Omri Weinstein

Abstract: In 2010, Pǎtraşcu proposed the following three-phase dynamic problem, as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures: I: Preprocess a collection of sets $\vec{S} = S_1, \ldots , S_k \subseteq [n]$, where $k=\operatorname{poly}(n)$. II: A set $T\subseteq [n]$ is revealed, and the data structure updates its memory. III: An index… ▽ More In 2010, Pǎtraşcu proposed the following three-phase dynamic problem, as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures: I: Preprocess a collection of sets $\vec{S} = S_1, \ldots , S_k \subseteq [n]$, where $k=\operatorname{poly}(n)$. II: A set $T\subseteq [n]$ is revealed, and the data structure updates its memory. III: An index $i \in [k]$ is revealed, and the data structure must determine if $S_i\cap T=^? \emptyset$. Pǎtraşcu conjectured that any data structure for the Multiphase problem must make $n^ε$ cell-probes in either Phase II or III, and showed that this would imply similar unconditional lower bounds on many important dynamic data structure problems. Alas, there has been almost no progress on this conjecture in the past decade since its introduction. We show an $\tildeΩ(\sqrt{n})$ cell-probe lower bound on the Multiphase problem for data structures with general (adaptive) updates, and queries with unbounded but "layered" adaptivity. This result captures all known set-intersection data structures and significantly strengthens previous Multiphase lower bounds, which only captured non-adaptive data structures. Our main technical result is a communication lower bound on a 4-party variant of Pǎtraşcu's Number-On-Forehead Multiphase game, using information complexity techniques. We also show that a lower bound on Pǎtraşcu's original NOF game would imply a polynomial ($n^{1+ε}$) lower bound on the number of wires of any constant-depth circuit with arbitrary gates computing a random $\tilde{O}(n)\times n$ linear operator $x \mapsto Ax$, a long-standing open problem in circuit complexity. This suggests that the NOF conjecture is much stronger than its data structure counterpart. △ Less

Submitted 29 October, 2019; originally announced October 2019.

Comments: 26 pages, 4 figures

2-gram-based Phonetic Feature Generation for Convolutional Neural Network in Assessment of Trademark Similarity

Authors: Kyung Pyo Ko, Kwang Hee Lee, Mi So Jang, Gun Hong Park

Abstract: A trademark is a mark used to identify various commodities. If same or similar trademark is registered for the same or similar commodity, the purchaser of the goods may be confused. Therefore, in the process of trademark registration examination, the examiner judges whether the trademark is the same or similar to the other applied or registered trademarks. The confusion in trademarks is based on t… ▽ More A trademark is a mark used to identify various commodities. If same or similar trademark is registered for the same or similar commodity, the purchaser of the goods may be confused. Therefore, in the process of trademark registration examination, the examiner judges whether the trademark is the same or similar to the other applied or registered trademarks. The confusion in trademarks is based on the visual, phonetic or conceptual similarity of the marks. In this paper, we focus specifically on the phonetic similarity between trademarks. We propose a method to generate 2D phonetic feature for convolutional neural network in assessment of trademark similarity. This proposed algorithm is tested with 12,553 trademark phonetic similar pairs and 34,020 trademark phonetic non-similar pairs from 2010 to 2016. As a result, we have obtained approximately 92% judgment accuracy. △ Less

Submitted 10 February, 2018; originally announced February 2018.

Comments: 10 pages, 6 figures, 10 tables

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Authors: Umang Bhaskar, Yu Cheng, Young Kun Ko, Chaitanya Swamy

Abstract: We study the optimization problem faced by a perfectly informed principal in a Bayesian game, who reveals information to the players about the state of nature to obtain a desirable equilibrium. This signaling problem is the natural design question motivated by uncertainty in games and has attracted much recent attention. We present new hardness results for signaling problems in (a) Bayesian two-pl… ▽ More We study the optimization problem faced by a perfectly informed principal in a Bayesian game, who reveals information to the players about the state of nature to obtain a desirable equilibrium. This signaling problem is the natural design question motivated by uncertainty in games and has attracted much recent attention. We present new hardness results for signaling problems in (a) Bayesian two-player zero-sum games, and (b) Bayesian network routing games. For Bayesian zero-sum games, when the principal seeks to maximize the equilibrium utility of a player, we show that it is NP-hard to obtain an additive FPTAS. Our hardness proof exploits duality and the equivalence of separation and optimization in a novel way. Further, we rule out an additive PTAS assuming planted clique hardness, which states that no polynomial time algorithm can recover a planted clique from an Erdős-Rényi random graph. Complementing these, we obtain a PTAS for a structured class of zero-sum games (where obtaining an FPTAS is still NP-hard) when the payoff matrices obey a Lipschitz condition. Previous results ruled out an FPTAS assuming planted-clique hardness, and a PTAS only for implicit games with quasi-polynomial-size strategy sets. For Bayesian network routing games, wherein the principal seeks to minimize the average latency of the Nash flow, we show that it is NP-hard to obtain a (multiplicative) $(4/3 - ε)$-approximation, even for linear latency functions. This is the optimal inapproximability result for linear latencies, since we show that full revelation achieves a $(4/3)$-approximation for linear latencies. △ Less

Submitted 30 October, 2016; v1 submitted 11 December, 2015; originally announced December 2015.

Approximation Algorithm for Minimum Weight Connected $m$-Fold Dominating Set

Authors: Zhao Zhang, Jiao Zhou, Ker-I Ko, Ding-zhu Du

Abstract: Using connected dominating set (CDS) to serve as a virtual backbone in a wireless networks can save energy and reduce interference. Since nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone has some fault-tolerance. A $k$-connected $m$-fold dominating set ($(k,m)$-CDS) of a graph $G$ is a node set $D$ such that every node in $V\setminus D$ has at… ▽ More Using connected dominating set (CDS) to serve as a virtual backbone in a wireless networks can save energy and reduce interference. Since nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone has some fault-tolerance. A $k$-connected $m$-fold dominating set ($(k,m)$-CDS) of a graph $G$ is a node set $D$ such that every node in $V\setminus D$ has at least $m$ neighbors in $D$ and the subgraph of $G$ induced by $D$ is $k$-connected. Using $(k,m)$-CDS can tolerate the failure of $\min\{k-1,m-1\}$ nodes. In this paper, we study Minimum Weight $(1,m)$-CDS problem ($(1,m)$-MWCDS), and present an $(H(δ+m)+2H(δ-1))$-approximation algorithm, where $δ$ is the maximum degree of the graph and $H(\cdot)$ is the Harmonic number. Notice that there is a $1.35\ln n$-approximation algorithm for the $(1,1)$-MWCDS problem, where $n$ is the number of nodes in the graph. Though our constant in $O(\ln \cdot)$ is larger than 1.35, $n$ is replaced by $δ$. Such a replacement enables us to obtain a $(6.67+\varepsilon)$-approximation for the $(1,m)$-MWCDS problem on unit disk graphs. △ Less

Submitted 12 March, 2017; v1 submitted 20 October, 2015; originally announced October 2015.

MSC Class: 68W25; 05C85 ACM Class: G.2.1; G.2.2

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

Authors: Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

Abstract: We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tildeΩ(n/r + r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound was $Ω(n/r^2 + r)$ due to Jain, Radhakrishnan and Sen… ▽ More We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tildeΩ(n/r + r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound was $Ω(n/r^2 + r)$ due to Jain, Radhakrishnan and Sen [JRS03]. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function $f$ is at most $2^{O(QIC(f))}$, where $QIC(f)$ is the prior-free quantum information complexity of $f$ (with error $1/3$). △ Less

Submitted 12 May, 2015; originally announced May 2015.

Comments: 41 pages

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

Authors: Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

Abstract: We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all k-subgraphs have density at most $1-ε$, requires $n^{\tilde Ω(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an addi… ▽ More We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all k-subgraphs have density at most $1-ε$, requires $n^{\tilde Ω(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an additive PTAS for Densest $k$-Subgraph. We further strengthen this result by showing that our lower bound continues to hold when, in the soundness case, even subgraphs smaller by a near-polynomial factor ($k' = k 2^{-\tilde Ω(log n)}$) are assumed to be at most ($1-ε$)-dense. Our reduction is inspired by recent applications of the "birthday repetition" technique [AIM14,BKW15]. Our analysis relies on information theoretical machinery and is similar in spirit to analyzing a parallel repetition of two-prover games in which the provers may choose to answer some challenges multiple times, while completely ignoring other challenges. △ Less

Submitted 30 April, 2015; originally announced April 2015.

From Linked Data to Relevant Data -- Time is the Essence

Authors: Markus Kirchberg, Ryan K L Ko, Bu Sung Lee

Abstract: The Semantic Web initiative puts emphasis not primarily on putting data on the Web, but rather on creating links in a way that both humans and machines can explore the Web of data. When such users access the Web, they leave a trail as Web servers maintain a history of requests. Web usage mining approaches have been studied since the beginning of the Web given the log's huge potential for purposes… ▽ More The Semantic Web initiative puts emphasis not primarily on putting data on the Web, but rather on creating links in a way that both humans and machines can explore the Web of data. When such users access the Web, they leave a trail as Web servers maintain a history of requests. Web usage mining approaches have been studied since the beginning of the Web given the log's huge potential for purposes such as resource annotation, personalization, forecasting etc. However, the impact of any such efforts has not really gone beyond generating statistics detailing who, when, and how Web pages maintained by a Web server were visited. △ Less

Submitted 25 March, 2011; originally announced March 2011.

Comments: 1st International Workshop on Usage Analysis and the Web of Data (USEWOD2011) in the 20th International World Wide Web Conference (WWW2011), Hyderabad, India, March 28th, 2011

Report number: WWW2011USEWOD/2011/kirkolee

Towards Solving the Inverse Protein Folding Problem

Authors: Yoojin Hong, Kyung Dae Ko, Gaurav Bhardwaj, Zhenhai Zhang, Damian B. van Rossum, Randen L. Patterson

Abstract: Accurately assigning folds for divergent protein sequences is a major obstacle to structural studies and underlies the inverse protein folding problem. Herein, we outline our theories for fold-recognition in the "twilight-zone" of sequence similarity (<25% identity). Our analyses demonstrate that structural sequence profiles built using Position-Specific Scoring Matrices (PSSMs) significantly outp… ▽ More Accurately assigning folds for divergent protein sequences is a major obstacle to structural studies and underlies the inverse protein folding problem. Herein, we outline our theories for fold-recognition in the "twilight-zone" of sequence similarity (<25% identity). Our analyses demonstrate that structural sequence profiles built using Position-Specific Scoring Matrices (PSSMs) significantly outperform multiple popular homology-modeling algorithms for relating and predicting structures given only their amino acid sequences. Importantly, structural sequence profiles reconstitute SCOP fold classifications in control and test datasets. Results from our experiments suggest that structural sequence profiles can be used to rapidly annotate protein folds at proteomic scales. We propose that encoding the entire Protein DataBank (~1070 folds) into structural sequence profiles would extract interoperable information capable of improving most if not all methods of structural modeling. △ Less

Submitted 29 August, 2010; originally announced August 2010.

Comments: 22 pages, 11 figures