OpenRaiser/Intern-Atlas huggingface dataset:
On Structural Parameterizations of Star Coloring
Venue: arXiv cs.DS 2022
Year: 2022

A Star Coloring of a graph G is a proper vertex coloring such that every path on four vertices uses at least three distinct colors. The minimum number of colors required for such a star coloring of G is called star chromatic number, denoted by χ_s(G). Given a graph G and a positive integer k, the STAR COLORING PROBLEM asks whether $G$ has a star coloring using at most k colors. This problem is NP-complete even on restricted graph classes such as bipartite graphs. In this paper, we initiate a study of STAR COLORING from the parameterized complexity perspective. We show that STAR COLORING is fixed-parameter tractable when parameterized by (a) neighborhood diversity, (b) twin-cover, and (c) the combined parameters clique-width and the number of colors.
Contract Strengthening through Constrained Horn Clause Verification
Venue: arXiv cs.LO 2022
Year: 2022

The functional properties of a program are often specified by providing a contract for each of its functions. A contract of a function consists of a pair of formulas, called a precondition and a postcondition, which, respectively, should hold before and after execution of that function. It might be the case that the contracts supplied by the programmer are not adequate to allow a verification system to prove program correctness, that is, to show that for every function, if the precondition holds and the execution of the function terminates, then the postcondition holds. We address this problem by providing a technique which may strengthen the postconditions of the functions, thereby improving the ability of the verifier to show program correctness. Our technique consists of four steps. First, the translation of the given program, which may manipulate algebraic data structures (ADTs), and its contracts into a set of constrained Horn clauses (CHCs) whose satisfiability implies the validity of the given contracts. Then, the derivation, via CHC transformation performed by the VeriCaT tool, of a new set of CHCs that manipulate only basic sorts (such as booleans or integers) and whose satisfiability implies the satisfiability of the original set of clauses. Then, the construction of a model, if any, of the new, derived CHCs using the CHC solver SPACER for basic sorts. Finally, the translation of that model into the formulas that suitably strengthen the postconditions of the given contracts. We will present our technique through an example consisting of a Scala program for reversing lists. Note that the Stainless verifier is not able to prove the correctness of that program when considering the given contracts, while it succeeds when considering the contracts with the strengthened postconditions constructed by applying our technique.
CHC-COMP 2022: Competition Report
Venue: arXiv cs.LO 2022
Year: 2022

CHC-COMP 2022 is the fifth edition of the competition of solvers for Constrained Horn Clauses. The competition was run in March 2022; the results were presented at the 9th Workshop on Horn Clauses for Verification and Synthesis held in Munich, Germany, on April 3, 2022. This edition featured six solvers, and eight tracks consisting of sets of linear and nonlinear clauses with constraints over linear integer arithmetic, linear real arithmetic, arrays, and algebraic data types. This report provides an overview of the organization behind the competition runs: it includes the technical details of the competition setup as well as presenting the results of the 2022 edition.
Efficient Frequency Domain-based Transformers for High-Quality Image Deblurring
Venue: arXiv cs.CV 2022
Year: 2022

We present an effective and efficient method that explores the properties of Transformers in the frequency domain for high-quality image deblurring. Our method is motivated by the convolution theorem that the correlation or convolution of two signals in the spatial domain is equivalent to an element-wise product of them in the frequency domain. This inspires us to develop an efficient frequency domain-based self-attention solver (FSAS) to estimate the scaled dot-product attention by an element-wise product operation instead of the matrix multiplication in the spatial domain. In addition, we note that simply using the naive feed-forward network (FFN) in Transformers does not generate good deblurred results. To overcome this problem, we propose a simple yet effective discriminative frequency domain-based FFN (DFFN), where we introduce a gated mechanism in the FFN based on the Joint Photographic Experts Group (JPEG) compression algorithm to discriminatively determine which low- and high-frequency information of the features should be preserved for latent clear image restoration. We formulate the proposed FSAS and DFFN into an asymmetrical network based on an encoder and decoder architecture, where the FSAS is only used in the decoder module for better image deblurring. Experimental results show that the proposed method performs favorably against the state-of-the-art approaches. Code will be available at \url{https://github.com/kkkls/FFTformer}.
Relation-dependent Contrastive Learning with Cluster Sampling for Inductive Relation Prediction
Venue: arXiv cs.LG 2022
Year: 2022

Relation prediction is a task designed for knowledge graph completion which aims to predict missing relationships between entities. Recent subgraph-based models for inductive relation prediction have received increasing attention, which can predict relation for unseen entities based on the extracted subgraph surrounding the candidate triplet. However, they are not completely inductive because of their disability of predicting unseen relations. Moreover, they fail to pay sufficient attention to the role of relation as they only depend on the model to learn parameterized relation embedding, which leads to inaccurate prediction on long-tail relations. In this paper, we introduce Relation-dependent Contrastive Learning (ReCoLe) for inductive relation prediction, which adapts contrastive learning with a novel sampling method based on clustering algorithm to enhance the role of relation and improve the generalization ability to unseen relations. Instead of directly learning embedding for relations, ReCoLe allocates a pre-trained GNN-based encoder to each relation to strengthen the influence of relation. The GNN-based encoder is optimized by contrastive learning, which ensures satisfactory performance on long-tail relations. In addition, the cluster sampling method equips ReCoLe with the ability to handle both unseen relations and entities. Experimental results suggest that ReCoLe outperforms state-of-the-art methods on commonly used inductive datasets.
Generalizable Industrial Visual Anomaly Detection with Self-Induction Vision Transformer
Venue: arXiv cs.CV 2022
Year: 2022

Industrial vision anomaly detection plays a critical role in the advanced intelligent manufacturing process, while some limitations still need to be addressed under such a context. First, existing reconstruction-based methods struggle with the identity mapping of trivial shortcuts where the reconstruction error gap is legible between the normal and abnormal samples, leading to inferior detection capabilities. Then, the previous studies mainly concentrated on the convolutional neural network (CNN) models that capture the local semantics of objects and neglect the global context, also resulting in inferior performance. Moreover, existing studies follow the individual learning fashion where the detection models are only capable of one category of the product while the generalizable detection for multiple categories has not been explored. To tackle the above limitations, we proposed a self-induction vision Transformer(SIVT) for unsupervised generalizable multi-category industrial visual anomaly detection and localization. The proposed SIVT first extracts discriminatory features from pre-trained CNN as property descriptors. Then, the self-induction vision Transformer is proposed to reconstruct the extracted features in a self-supervisory fashion, where the auxiliary induction tokens are additionally introduced to induct the semantics of the original signal. Finally, the abnormal properties can be detected using the semantic feature residual difference. We experimented with the SIVT on existing Mvtec AD benchmarks, the results reveal that the proposed method can advance state-of-the-art detection performance with an improvement of 2.8-6.3 in AUROC, and 3.3-7.6 in AP.
Computer Vision for Transit Travel Time Prediction: An End-to-End Framework Using Roadside Urban Imagery
Venue: arXiv cs.CV 2022
Year: 2022

Accurate travel time estimation is paramount for providing transit users with reliable schedules and dependable real-time information. This paper is the first to utilize roadside urban imagery for direct transit travel time prediction. We propose and evaluate an end-to-end framework integrating traditional transit data sources with a roadside camera for automated roadside image data acquisition, labeling, and model training to predict transit travel times across a segment of interest. First, we show how the GTFS real-time data can be utilized as an efficient activation mechanism for a roadside camera unit monitoring a segment of interest. Second, AVL data is utilized to generate ground truth labels for the acquired images based on the observed transit travel time percentiles across the camera-monitored segment during the time of image acquisition. Finally, the generated labeled image dataset is used to train and thoroughly evaluate a Vision Transformer (ViT) model to predict a discrete transit travel time range (band). The results illustrate that the ViT model is able to learn image features and contents that best help it deduce the expected travel time range with an average validation accuracy ranging between 80%-85%. We assess the interpretability of the ViT model's predictions and showcase how this discrete travel time band prediction can subsequently improve continuous transit travel time estimation. The workflow and results presented in this study provide an end-to-end, scalable, automated, and highly efficient approach for integrating traditional transit data sources and roadside imagery to improve the estimation of transit travel duration. This work also demonstrates the value of incorporating real-time information from computer-vision sources, which are becoming increasingly accessible and can have major implications for improving operations and passenger real-time information.
ISIM: Iterative Self-Improved Model for Weakly Supervised Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Weakly Supervised Semantic Segmentation (WSSS) is a challenging task aiming to learn the segmentation labels from class-level labels. In the literature, exploiting the information obtained from Class Activation Maps (CAMs) is widely used for WSSS studies. However, as CAMs are obtained from a classification network, they are interested in the most discriminative parts of the objects, producing non-complete prior information for segmentation tasks. In this study, to obtain more coherent CAMs with segmentation labels, we propose a framework that employs an iterative approach in a modified encoder-decoder-based segmentation model, which simultaneously supports classification and segmentation tasks. As no ground-truth segmentation labels are given, the same model also generates the pseudo-segmentation labels with the help of dense Conditional Random Fields (dCRF). As a result, the proposed framework becomes an iterative self-improved model. The experiments performed with DeepLabv3 and UNet models show a significant gain on the Pascal VOC12 dataset, and the DeepLabv3 application increases the current state-of-the-art metric by %2.5. The implementation associated with the experiments can be found: https://github.com/cenkbircanoglu/isim.
Towards peer-to-peer sharing of wireless energy services
Venue: arXiv cs.NI 2022
Year: 2022

Crowdsourcing wireless energy services is a novel convenient alternative to charge IoT devices. We demonstrate peer-to-peer wireless energy services sharing between smartphones over a distance. Our demo leverages (1) a service-based technique to share energy services, (2) state-of-the-art power transfer technology over a distance, and (3) a mobile application to enable communication between energy providers and consumers. In addition, our application monitors the charging process between IoT devices to collect a dataset for further analysis. Moreover, in this demo, we compare the peer-to-peer energy transfer between two smartphones using different charging technologies, i.e., cable charging, reveres charging, and wireless charging over a distance. A set of preliminary experiments has been conducted on a real collected dataset to analyze and demonstrate the behavior of the current wireless and traditional charging technologies.
Scalable and Effective Conductance-based Graph Clustering
Venue: arXiv cs.DS 2022
Year: 2022

Conductance-based graph clustering has been recognized as a fundamental operator in numerous graph analysis applications. Despite the significant success of conductance-based graph clustering, existing algorithms are either hard to obtain satisfactory clustering qualities, or have high time and space complexity to achieve provable clustering qualities. To overcome these limitations, we devise a powerful \textit{peeling}-based graph clustering framework \textit{PCon}. We show that many existing solutions can be reduced to our framework. Namely, they first define a score function for each vertex, then iteratively remove the vertex with the smallest score. Finally, they output the result with the smallest conductance during the peeling process. Based on our framework, we propose two novel algorithms \textit{PCon\_core} and \emph{PCon\_de} with linear time and space complexity, which can efficiently and effectively identify clusters from massive graphs with more than a few billion edges. Surprisingly, we prove that \emph{PCon\_de} can identify clusters with near-constant approximation ratio, resulting in an important theoretical improvement over the well-known quadratic Cheeger bound. Empirical results on real-life and synthetic datasets show that our algorithms can achieve 5$\sim$42 times speedup with a high clustering accuracy, while using 1.4$\sim$7.8 times less memory than the baseline algorithms.
Zero NeRF: Registration with Zero Overlap
Venue: arXiv cs.CV 2022
Year: 2022

We present Zero-NeRF, a projective surface registration method that, to the best of our knowledge, offers the first general solution capable of alignment between scene representations with minimal or zero visual correspondence. To do this, we enforce consistency between visible surfaces of partial and complete reconstructions, which allows us to constrain occluded geometry. We use a NeRF as our surface representation and the NeRF rendering pipeline to perform this alignment. To demonstrate the efficacy of our method, we register real-world scenes from opposite sides with infinitesimal overlaps that cannot be accurately registered using prior methods, and we compare these results against widely used registration methods.
"Coherent Mode" for the World's Public Square
Venue: arXiv cs.SI 2022
Year: 2022

Systems for large scale deliberation have resolved polarized issues and shifted agenda setting into the public's hands. These systems integrate bridging-based ranking algorithms - including group informed consensus implemented in Polis and the continuous matrix factorization approach implemented by Twitter Birdwatch - making it possible to highlight statements which enjoy broad support from a diversity of opinion groups. Polis has been productively employed to foster more constructive political deliberation at nation scale in law making exercises. Twitter Birdwatch is implemented with the intention of addressing misinformation in the global public square. From one perspective, Twitter Birdwatch can be viewed as an anti-misinformation system which has deliberative aspects. But it can also be viewed as a first step towards a generalized deliberative system, using Twitter's misinformation problem as a proving ground. In this paper, we propose that Twitter could adapt Birdwatch to produce maps of public opinion. We describe a system in five parts for generalizing Birdwatch: activation of a deliberative system and topic selection, population sampling and the role of expert networks, deliberation, reporting interpretable results and finally distribution of the results to the public and those in power.
Modeling System Events and Negative Events Using Thinging Machines Based on Lupascian Logic
Venue: arXiv cs.SE 2022
Year: 2022

This paper is an exploration of the ontological foundations of conceptual modeling that addresses the concept of events and related notions. Development models that convey how things change over space and time demand continued attention in systems and software engineering. In this context, foundational matters in modeling systems include the definition of an event, the types of events, and the kinds of relationships that can be recognized among events. Although a broad spectrum of research of such issues exists in various fields of study, events have extensive applicability in computing (e.g., event-driven programming, architecture, data modeling, automation, and surveillance). While these computing notions are diverse, their event-based nature lets us apply many of the same software engineering techniques to all of them. In this paper, the focus is on addressing the dynamic concepts of system events and negative events. Specifically, we concentrate on what computer scientists would refer to as an event grammar and event calculus. Analyzing the concept of event would further the understanding of the event notion and provide a sound foundation for improving the theory and practice of conceptual modeling. An event in computer science has many definitions (e.g., anything that happens, changes in the properties of objects, and the occurrence of and transition between states). This paper is based upon a different conceptualization using thinging machines and Lupascian logic to define negative events. An event is defined as a time penetrated domain s region, which is described in terms of things and five-action machines. Accordingly, samples from event grammar and event calculus are remodeled and analyzed in terms of this definition. The results point to an enriched modeling technique with an enhanced conceptualization of events that can benefit behavior modeling in systems.
SuperTran: Reference Based Video Transformer for Enhancing Low Bitrate Streams in Real Time
Venue: arXiv cs.CV 2022
Year: 2022

This work focuses on low bitrate video streaming scenarios (e.g. 50 - 200Kbps) where the video quality is severely compromised. We present a family of novel deep generative models for enhancing perceptual video quality of such streams by performing super-resolution while also removing compression artifacts. Our model, which we call SuperTran, consumes as input a single high-quality, high-resolution reference images in addition to the low-quality, low-resolution video stream. The model thus learns how to borrow or copy visual elements like textures from the reference image and fill in the remaining details from the low resolution stream in order to produce perceptually enhanced output video. The reference frame can be sent once at the start of the video session or be retrieved from a gallery. Importantly, the resulting output has substantially better detail than what has been otherwise possible with methods that only use a low resolution input such as the SuperVEGAN method. SuperTran works in real-time (up to 30 frames/sec) on the cloud alongside standard pipelines.
CMOS-compatible Ising and Potts Annealing Using Single Photon Avalanche Diodes
Venue: arXiv cs.ET 2022
Year: 2022

Massively parallel annealing processors may offer superior performance for a wide range of sampling and optimization problems. A key component dictating the size of these processors is the neuron update circuit, ideally implemented using special stochastic nanodevices. We leverage photon statistics using single photon avalanche diodes (SPADs) and temporal filtering to generate stochastic states. This method is a powerful alternative offering unique features not currently seen in annealing processors: the ability to continuously control the computational temperature and the seamless extension to the Potts model, a $n$-state generalization of the two-state Ising model. SPADs also offer a considerable practical advantage since they are readily manufacturable in current standard CMOS processes. As a first step towards realizing a CMOS SPAD-based annealer, we have designed Ising and Potts models driven by an array of discrete SPADs and show they accurately sample from their theoretical distributions.
AutoReply: Detecting Nonsense in Dialogue Introspectively with Discriminative Replies
Venue: arXiv cs.CL 2022
Year: 2022

Existing approaches built separate classifiers to detect nonsense in dialogues. In this paper, we show that without external classifiers, dialogue models can detect errors in their own messages introspectively, by calculating the likelihood of replies that are indicative of poor messages. For example, if an agent believes its partner is likely to respond "I don't understand" to a candidate message, that message may not make sense, so an alternative message should be chosen. We evaluate our approach on a dataset from the game Diplomacy, which contains long dialogues richly grounded in the game state, on which existing models make many errors. We first show that hand-crafted replies can be effective for the task of detecting nonsense in applications as complex as Diplomacy. We then design AutoReply, an algorithm to search for such discriminative replies automatically, given a small number of annotated dialogue examples. We find that AutoReply-generated replies outperform handcrafted replies and perform on par with carefully fine-tuned large supervised models. Results also show that one single reply without much computation overheads can also detect dialogue nonsense reasonably well.
FRE: A Fast Method For Anomaly Detection And Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents a fast and principled approach for solving the visual anomaly detection and segmentation problem. In this setup, we have access to only anomaly-free training data and want to detect and identify anomalies of an arbitrary nature on test data. We propose the application of linear statistical dimensionality reduction techniques on the intermediate features produced by a pretrained DNN on the training data, in order to capture the low-dimensional subspace truly spanned by said features. We show that the \emph{feature reconstruction error} (FRE), which is the $\ell_2$-norm of the difference between the original feature in the high-dimensional space and the pre-image of its low-dimensional reduced embedding, is extremely effective for anomaly detection. Further, using the same feature reconstruction error concept on intermediate convolutional layers, we derive FRE maps that provide pixel-level spatial localization of the anomalies in the image (i.e. segmentation). Experiments using standard anomaly detection datasets and DNN architectures demonstrate that our method matches or exceeds best-in-class quality performance, but at a fraction of the computational and memory cost required by the state of the art. It can be trained and run very efficiently, even on a traditional CPU.