OpenRaiser/Intern-Atlas huggingface dataset:
Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Deep learning's performance has been extensively recognized recently. Graph neural networks (GNNs) are designed to deal with graph-structural data that classical deep learning does not easily manage. Since most GNNs were created using distinct theories, direct comparisons are impossible. Prior research has primarily concentrated on categorizing existing models, with little attention paid to their intrinsic connections. The purpose of this study is to establish a unified framework that integrates GNNs based on spectral graph and approximation theory. The framework incorporates a strong integration between spatial- and spectral-based GNNs while tightly associating approaches that exist within each respective domain.
CGuard: Efficient Spatial Safety for C
Venue: arXiv cs.CR 2023
Year: 2023

Spatial safety violations are the root cause of many security attacks and unexpected behavior of applications. Existing techniques to enforce spatial safety work broadly at either object or pointer granularity. Object-based approaches tend to incur high CPU overheads, whereas pointer-based approaches incur both high CPU and memory overheads. SGXBounds, an object-based approach, is so far the most efficient technique that provides complete out-of-bounds protection for objects. However, a major drawback of this approach is that it can't support address space larger than 32-bit. In this paper, we present CGuard, a tool that provides object-bounds protection for C applications with comparable overheads to SGXBounds without restricting the application address space. CGuard stores the bounds information just before the base address of an object and encodes the relative offset of the base address in the spare bits of the virtual address available in x86_64 architecture. For an object that can't fit in the spare bits, CGuard uses a custom memory layout that enables it to find the base address of the object in just one memory access. Our study revealed spatial safety violations in the gcc and x264 benchmarks from the SPEC CPU2017 benchmark suite and the string_match benchmark from the Phoenix benchmark suite. The execution time overheads for the SPEC CPU2017 and Phoenix benchmark suites were 42% and 26% respectively, whereas the reduction in the throughput for the Apache webserver when the CPUs were fully saturated was 30%. These results indicate that CGuard can be highly effective while maintaining a reasonable degree of efficiency.
Throttling Equilibria in Auction Markets
Venue: arXiv cs.GT 2023
Year: 2023

Throttling is a popular method of budget management for online ad auctions in which the platform modulates the participation probability of an advertiser in order to smoothly spend her budget across many auctions. In this work, we investigate the setting in which all of the advertisers simultaneously employ throttling to manage their budgets, and we do so for both first-price and second-price auctions. We analyze the structural and computational properties of the resulting equilibria. For first-price auctions, we show that a unique equilibrium always exists, is well-behaved and can be computed efficiently via tatonnement-style decentralized dynamics. In contrast, for second-price auctions, we prove that even though an equilibrium always exists, the problem of finding an equilibrium is PPAD-complete, there can be multiple equilibria, and it is NP-hard to find the revenue maximizing one. We also compare the equilibrium outcomes of throttling to those of multiplicative pacing, which is the other most popular and well-studied method of budget management. Finally, we characterize the Price of Anarchy of these equilibria for liquid welfare by showing that it is at most 2 for both first-price and second-price auctions, and demonstrating that our bound is tight.
What Is The Internet? Partial Connectivity in the Internet Core
Venue: arXiv cs.NI 2023
Year: 2023

"A collection of interconnected networks" defines what the Internet is, but not what it is not. Events threaten Internet fragmentation: politics suggest countries or ISPs may secede or be de-peered, disputes between ISPs result in persistent unreachability between their customers, and architectural changes risk breaking the "one" Internet. Understanding such threats benefits from a testable definition of what the Internet is and is not, enabling discussion and quantification of partial connectivity. We provide a conceptual definition giving an idealized asymptote of connectivity. It implies peninsulas of persistent, partial connectivity, and islands when one or more computers are partitioned from the main Internet. We provide algorithms to measure, operationally, the number, size, and duration of peninsulas and islands. We apply these algorithms in rigorous measurement from two complementary measurement systems, one observing 5M networks from a few locations, and the other a few destinations from 10k locations. Results show that peninsulas (partial connectivity) are about as common as Internet outages, quantifying this long-observed problem. Root causes show that most peninsula events (45%) are routing transients, but most peninsula-time (90%) is from a few long-lived events (7%). Our analysis helps interpret DNSmon, a system monitoring the DNS root, separating measurement error and persistent problems from underlying differences and operationally important transients. Finally, our definition confirms the international nature of the Internet: no single country can unilaterally claim to be "the Internet", but countries can choose to leave.
Spatio-Temporal Lattice Planning Using Optimal Motion Primitives
Venue: arXiv cs.RO 2023
Year: 2023

Lattice-based planning techniques simplify the motion planning problem for autonomous vehicles by limiting available motions to a pre-computed set of primitives. These primitives are then combined online to generate more complex maneuvers. A set of motion primitives t-span a lattice if, given a real number t at least 1, any configuration in the lattice can be reached via a sequence of motion primitives whose cost is no more than a factor of t from optimal. Computing a minimal t-spanning set balances a trade-off between computed motion quality and motion planning performance. In this work, we formulate this problem for an arbitrary lattice as a mixed integer linear program. We also propose an A*-based algorithm to solve the motion planning problem using these primitives. Finally, we present an algorithm that removes the excessive oscillations from planned motions -- a common problem in lattice-based planning. Our method is validated for autonomous driving in both parking lot and highway scenarios.
On relating one-way classical and quantum communication complexities
Venue: arXiv cs.CC 2023
Year: 2023

Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function $f(x,y)$, where $x$ is given to Alice and $y$ is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results. Let $f: \mathcal{X} \times \mathcal{Y} \rightarrow \mathcal{Z} \cup \{\bot\}$ be a partial function and $μ$ be a distribution with support contained in $f^{-1}(\mathcal{Z})$. Denote $d=|\mathcal{Z}|$. Let $\mathsf{R}^{1,μ}_ε(f)$ be the classical one-way communication complexity of $f$; $\mathsf{Q}^{1,μ}_ε(f)$ be the quantum one-way communication complexity of $f$ and $\mathsf{Q}^{1,μ, *}_ε(f)$ be the entanglement-assisted quantum one-way communication complexity of $f$, each with distributional error (average error over $μ$) at most $ε$. We show: 1) If $μ$ is a product distribution, $η> 0$ and $0 \leq ε\leq 1-1/d$, then, $$\mathsf{R}^{1,μ}_{2ε-dε^2/(d-1)+ η}(f) \leq 2\mathsf{Q}^{1,μ, *}_ε(f) + O(\log\log (1/η))\enspace.$$ 2)If $μ$ is a non-product distribution and $\mathcal{Z}=\{ 0,1\}$, then $\forall ε, η> 0$ such that $ε/η+ η< 0.5$, $$\mathsf{R}^{1,μ}_{3η}(f) = O(\mathsf{Q}^{1,μ}_{ε}(f) \cdot \mathsf{CS}(f)/η^3)\enspace,$$ where \[\mathsf{CS}(f) = \max_{y} \min_{z\in\{0,1\}} \vert \{x~|~f(x,y)=z\} \vert \enspace.\]
Convergence of Deep ReLU Networks
Venue: arXiv cs.LG 2023
Year: 2023

We explore convergence of deep neural networks with the popular ReLU activation function, as the depth of the networks tends to infinity. To this end, we introduce the notion of activation domains and activation matrices of a ReLU network. By replacing applications of the ReLU activation function by multiplications with activation matrices on activation domains, we obtain an explicit expression of the ReLU network. We then identify the convergence of the ReLU networks as convergence of a class of infinite products of matrices. Sufficient and necessary conditions for convergence of these infinite products of matrices are studied. As a result, we establish necessary conditions for ReLU networks to converge that the sequence of weight matrices converges to the identity matrix and the sequence of the bias vectors converges to zero as the depth of ReLU networks increases to infinity. Moreover, we obtain sufficient conditions in terms of the weight matrices and bias vectors at hidden layers for pointwise convergence of deep ReLU networks. These results provide mathematical insights to the design strategy of the well-known deep residual networks in image classification.
MKConv: Multidimensional Feature Representation for Point Cloud Analysis
Venue: arXiv cs.CV 2023
Year: 2023

Despite the remarkable success of deep learning, an optimal convolution operation on point clouds remains elusive owing to their irregular data structure. Existing methods mainly focus on designing an effective continuous kernel function that can handle an arbitrary point in continuous space. Various approaches exhibiting high performance have been proposed, but we observe that the standard pointwise feature is represented by 1D channels and can become more informative when its representation involves additional spatial feature dimensions. In this paper, we present Multidimensional Kernel Convolution (MKConv), a novel convolution operator that learns to transform the point feature representation from a vector to a multidimensional matrix. Unlike standard point convolution, MKConv proceeds via two steps. (i) It first activates the spatial dimensions of local feature representation by exploiting multidimensional kernel weights. These spatially expanded features can represent their embedded information through spatial correlation as well as channel correlation in feature space, carrying more detailed local structure information. (ii) Then, discrete convolutions are applied to the multidimensional features which can be regarded as a grid-structured matrix. In this way, we can utilize the discrete convolutions for point cloud data without voxelization that suffers from information loss. Furthermore, we propose a spatial attention module, Multidimensional Local Attention (MLA), to provide comprehensive structure awareness within the local point set by reweighting the spatial feature dimensions. We demonstrate that MKConv has excellent applicability to point cloud processing tasks including object classification, object part segmentation, and scene semantic segmentation with superior results.
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Venue: arXiv cs.DS 2023
Year: 2023

In the classical Subset Sum problem we are given a set $X$ and a target $t$, and the task is to decide whether there exists a subset of $X$ which sums to $t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time $O(n \cdot |\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of $X$ that are smaller than $t$. Furthermore, all known pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set $\mathcal{S}(X,t)$. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time $\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether $\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time $\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$. Central to our approach is the study of top-$k$-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest $k$ non-zero monomials of their product. We design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets.
MLMOD: Machine Learning Methods for Data-Driven Modeling in LAMMPS
Venue: arXiv cs.LG 2023
Year: 2023

MLMOD is a software package for incorporating machine learning approaches and models into simulations of microscale mechanics and molecular dynamics in LAMMPS. Recent machine learning approaches provide promising data-driven approaches for learning representations for system behaviors from experimental data and high fidelity simulations. The package faciliates learning and using data-driven models for (i) dynamics of the system at larger spatial-temporal scales (ii) interactions between system components, (iii) features yielding coarser degrees of freedom, and (iv) features for new quantities of interest characterizing system behaviors. MLMOD provides hooks in LAMMPS for (i) modeling dynamics and time-step integration, (ii) modeling interactions, and (iii) computing quantities of interest characterizing system states. The package allows for use of machine learning methods with general model classes including Neural Networks, Gaussian Process Regression, Kernel Models, and other approaches. Here we discuss our prototype C++/Python package, aims, and example usage. The package is integrated currently with the mesocale and molecular dynamics simulation package LAMMPS and PyTorch. For related papers, examples, updates, and additional information see https://github.com/atzberg/mlmod and http://atzberger.org/.
Sequoia: A Software Framework to Unify Continual Learning Research
Venue: arXiv cs.LG 2023
Year: 2023

The field of Continual Learning (CL) seeks to develop algorithms that accumulate knowledge and skills over time through interaction with non-stationary environments. In practice, a plethora of evaluation procedures (settings) and algorithmic solutions (methods) exist, each with their own potentially disjoint set of assumptions. This variety makes measuring progress in CL difficult. We propose a taxonomy of settings, where each setting is described as a set of assumptions. A tree-shaped hierarchy emerges from this view, where more general settings become the parents of those with more restrictive assumptions. This makes it possible to use inheritance to share and reuse research, as developing a method for a given setting also makes it directly applicable onto any of its children. We instantiate this idea as a publicly available software framework called Sequoia, which features a wide variety of settings from both the Continual Supervised Learning (CSL) and Continual Reinforcement Learning (CRL) domains. Sequoia also includes a growing suite of methods which are easy to extend and customize, in addition to more specialized methods from external libraries. We hope that this new paradigm and its first implementation can help unify and accelerate research in CL. You can help us grow the tree by visiting www.github.com/lebrice/Sequoia.
Variational Actor-Critic Algorithms
Venue: arXiv cs.LG 2023
Year: 2023

We introduce a class of variational actor-critic algorithms based on a variational formulation over both the value function and the policy. The objective function of the variational formulation consists of two parts: one for maximizing the value function and the other for minimizing the Bellman residual. Besides the vanilla gradient descent with both the value function and the policy updates, we propose two variants, the clipping method and the flipping method, in order to speed up the convergence. We also prove that, when the prefactor of the Bellman residual is sufficiently large, the fixed point of the algorithm is close to the optimal policy.
Evaluating the Tradeoff Between Abstractiveness and Factuality in Abstractive Summarization
Venue: arXiv cs.CL 2023
Year: 2023

Neural models for abstractive summarization tend to generate output that is fluent and well-formed but lacks semantic faithfulness, or factuality, with respect to the input documents. In this paper, we analyze the tradeoff between abstractiveness and factuality of generated summaries across multiple datasets and models, using extensive human evaluations of factuality. In our analysis, we visualize the rates of change in factuality as we gradually increase abstractiveness using a decoding constraint, and we observe that, while increased abstractiveness generally leads to a drop in factuality, the rate of factuality decay depends on factors such as the data that the system was trained on. We introduce two datasets with human factuality judgements; one containing 10.2k generated summaries with systematically varied degrees of abstractiveness; the other containing 4.2k summaries from five different summarization models. We propose new factuality metrics that adjust for the degree of abstractiveness, and we use them to compare the abstractiveness-adjusted factuality of previous summarization works, providing baselines for future work.
Topological Art in Simple Galleries
Venue: arXiv cs.CG 2023
Year: 2023

Let $P$ be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in $P$. We say two points $a,b\in P$ can see each other if the line segment $seg(a,b)$ is contained in $P$. We denote by $V(P)$ the family of all minimum guard placements. The Hausdorff distance makes $V(P)$ a metric space and thus a topological space. We show homotopy-universality, that is for every semi-algebraic set $S$ there is a polygon $P$ such that $V(P)$ is homotopy equivalent to $S$. Furthermore, for various concrete topological spaces $T$, we describe instances $I$ of the art gallery problem such that $V(I)$ is homeomorphic to $T$.
Semantics-Native Communication with Contextual Reasoning
Venue: arXiv cs.IT 2023
Year: 2023

Spurred by a huge interest in the post-Shannon communication, it has recently been shown that leveraging semantics can significantly improve the communication effectiveness across many tasks. In this article, inspired by human communication, we propose a novel stochastic model of System 1 semantics-native communication (SNC) for generic tasks, where a speaker has an intention of referring to an entity, extracts the semantics, and communicates its symbolic representation to a target listener. To further reach its full potential, we additionally infuse contextual reasoning into SNC such that the speaker locally and iteratively self-communicates with a virtual agent built on the physical listener's unique way of coding its semantics, i.e., communication context. The resultant System 2 SNC allows the speaker to extract the most effective semantics for its listener. Leveraging the proposed stochastic model, we show that the reliability of System 2 SNC increases with the number of meaningful concepts, and derive the expected semantic representation (SR) bit length which quantifies the extracted effective semantics. It is also shown that System 2 SNC significantly reduces the SR length without compromising communication reliability.
A Self-Distillation Embedded Supervised Affinity Attention Model for Few-Shot Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Few-shot segmentation focuses on the generalization of models to segment unseen object with limited annotated samples. However, existing approaches still face two main challenges. First, huge feature distinction between support and query images causes knowledge transferring barrier, which harms the segmentation performance. Second, limited support prototypes cannot adequately represent features of support objects, hard to guide high-quality query segmentation. To deal with the above two issues, we propose self-distillation embedded supervised affinity attention model to improve the performance of few-shot segmentation task. Specifically, the self-distillation guided prototype module uses self-distillation to align the features of support and query. The supervised affinity attention module generates high-quality query attention map to provide sufficient object information. Extensive experiments prove that our model significantly improves the performance compared to existing methods. Comprehensive ablation experiments and visualization studies also show the significant effect of our method on few-shot segmentation task. On COCO-20i dataset, we achieve new state-of-the-art results. Training code and pretrained models are available at https://github.com/cv516Buaa/SD-AANet.
Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data
Venue: arXiv cs.LG 2023
Year: 2023

Bregman proximal point algorithm (BPPA) has witnessed emerging machine learning applications, yet its theoretical understanding has been largely unexplored. We study the computational properties of BPPA through learning linear classifiers with separable data, and demonstrate provable algorithmic regularization of BPPA. For any BPPA instantiated with a fixed Bregman divergence, we provide a lower bound of the margin obtained by BPPA with respect to an arbitrarily chosen norm. The obtained margin lower bound differs from the maximal margin by a multiplicative factor, which inversely depends on the condition number of the distance-generating function measured in the dual norm. We show that the dependence on the condition number is tight, thus demonstrating the importance of divergence in affecting the quality of the learned classifiers. We then extend our findings to mirror descent, for which we establish similar connections between the margin and Bregman divergence, together with a non-asymptotic analysis. Numerical experiments on both synthetic and real-world datasets are provided to support our theoretical findings. To the best of our knowledge, the aforementioned findings appear to be new in the literature of algorithmic regularization.