More Like this

1. Large Scale Subject Category Classification of Scholarly Papers With Deep Attentive Neural Networks

   https://doi.org/10.3389/frma.2020.600382  

   Kandimalla, Bharath ; Rohatgi, Shaurya ; Wu, Jian ; Giles, C. Lee ( February 2021 , Frontiers in Research Metrics and Analytics)

   null (Ed.)

   Subject categories of scholarly papers generally refer to the knowledge domain(s) to which the papers belong, examples being computer science or physics. Subject category classification is a prerequisite for bibliometric studies, organizing scientific publications for domain knowledge extraction, and facilitating faceted searches for digital library search engines. Unfortunately, many academic papers do not have such information as part of their metadata. Most existing methods for solving this task focus on unsupervised learning that often relies on citation networks. However, a complete list of papers citing the current paper may not be readily available. In particular, new papers that have few or no citations cannot be classified using such methods. Here, we propose a deep attentive neural network (DANN) that classifies scholarly papers using only their abstracts. The network is trained using nine million abstracts from Web of Science (WoS). We also use the WoS schema that covers 104 subject categories. The proposed network consists of two bi-directional recurrent neural networks followed by an attention layer. We compare our model against baselines by varying the architecture and text representation. Our best model achieves micro- F 1 measure of 0.76 with F 1 of individual subject categories ranging from 0.50 to 0.95. The results showed the importance of retraining word embedding models to maximize the vocabulary overlap and the effectiveness of the attention mechanism. The combination of word vectors with TFIDF outperforms character and sentence level embedding models. We discuss imbalanced samples and overlapping categories and suggest possible strategies for mitigation. We also determine the subject category distribution in CiteSeerX by classifying a random sample of one million academic papers. 

   more » « less
2. On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

   Cohen-Addad, Vincent ; Filtser, Arnold ; Klein, Philip N ; Le, Hung ( October 2020 , Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science)

   null (Ed.)

   Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion ϵD. Namely, given a minor-free graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidth-Oϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth). 

   more » « less
3. High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games

   https://doi.org/10.1137/1.9781611977073.47  

   Bafna, Mitali ; Hopkins, Max ; Kaufman, Tali ; Lovett, Shachar ( January 2022 , Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass (ITCS 2016), yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders (Dinur and Kaufman FOCS 2017), which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight ℓ2-characterization of edge-expansion, as well as to a new understanding of local-to-global graph algorithms on HDX. Towards the latter, we introduce a novel spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof for the former ℓ2-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearly-exponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the q-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an ℓ∞-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture (Khot, Minzer, and Safra FOCS 2018). We give a reduction from a related ℓ∞-variant to our ℓ2-characterization, but it loses factors in the regime of interest for hardness where the gap between ℓ2 and ℓ∞ structure is large. Nevertheless, our results open the door for further work on the use of HDX in hardness of approximation and their general relation to unique games. 

   more » « less
4. SmartDeal: Remodeling Deep Network Weights for Efficient Inference and Training

   https://doi.org/10.1109/TNNLS.2021.3138056  

   Chen, Xiaohan ; Zhao, Yang ; Wang, Yue ; Xu, Pengfei ; You, Haoran ; Li, Chaojian ; Fu, Yonggan ; Lin, Yingyan ; Wang, Zhangyang ( March 2022 , IEEE Transactions on Neural Networks and Learning Systems)

   The record-breaking performance of deep neural networks (DNNs) comes with heavy parameter budgets, which leads to external dynamic random access memory (DRAM) for storage. The prohibitive energy of DRAM accesses makes it nontrivial for DNN deployment on resource-constrained devices, calling for minimizing the movements of weights and data in order to improve the energy efficiency. Driven by this critical bottleneck, we present SmartDeal, a hardware-friendly algorithm framework to trade higher-cost memory storage/access for lower-cost computation, in order to aggressively boost the storage and energy efficiency, for both DNN inference and training. The core technique of SmartDeal is a novel DNN weight matrix decomposition framework with respective structural constraints on each matrix factor, carefully crafted to unleash the hardware-aware efficiency potential. Specifically, we decompose each weight tensor as the product of a small basis matrix and a large structurally sparse coefficient matrix whose nonzero elements are readily quantized to the power-of-2. The resulting sparse and readily quantized DNNs enjoy greatly reduced energy consumption in data movement as well as weight storage, while incurring minimal overhead to recover the original weights thanks to the required sparse bit-operations and cost-favorable computations. Beyond inference, we take another leap to embrace energy-efficient training, by introducing several customized techniques to address the unique roadblocks arising in training while preserving the SmartDeal structures. We also design a dedicated hardware accelerator to fully utilize the new weight structure to improve the real energy efficiency and latency performance. We conduct experiments on both vision and language tasks, with nine models, four datasets, and three settings (inference-only, adaptation, and fine-tuning). Our extensive results show that 1) being applied to inference, SmartDeal achieves up to 2.44x improvement in energy efficiency as evaluated using real hardware implementations and 2) being applied to training, SmartDeal can lead to 10.56x and 4.48x reduction in the storage and the training energy cost, respectively, with usually negligible accuracy loss, compared to state-of-the-art training baselines. Our source codes are available at: https://github.com/VITA-Group/SmartDeal. 

   more » « less
5. Carleson embedding on tri-tree and on tri-disc

   Mozolyako, Pavel ; Psaromiligkos, Georgios ; Volberg, Alexander ; Zorin-Kranich, Pavel ( May 2022 , Revista matemática iberoamericana)

   We prove multi-parameter dyadic embedding theorem for Hardy operator on the multi-tree. We also show that for a large class of Dirichlet spaces in bi-disc and tri-disc this proves the embedding theorem of those Dirichlet spaces of holomorphic function on bi- and tri-disc. We completely describe the Carleson measures for such embeddings. The result below generalizes embedding result of [AMPVZ] from bi- tree to tri-tree and from Carleson–Chang condition to Carleson box condition. One of our embedding description is similar to Carleson–Chang–Fefferman condition and involves dyadic open sets. On the other hand, the unusual feature is that embedding on bi-tree and tri-tree turned out to be equivalent to one box Carleson condition. This is in striking difference to works of Chang–Fefferman and well known Carleson quilt counterexample. Finally, we explain the obstacle that prevents us from proving our results on poly-discs of dimension four and higher. 

   more » « less